编辑代码

#include <stdio.h>
#include <stdlib.h>

// 定义散列表的节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 散列表的大小
#define HASH_SIZE 10

// 初始化散列表
void initHashTable(Node** hashTable) {
    for (int i = 0; i < HASH_SIZE; i++) {
        hashTable[i] = NULL;
    }
}

// 向散列表中插入节点
void insertNode(Node** hashTable, int data) {
    // 计算散列值
    int hashValue = data % HASH_SIZE;
    
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    
    // 链接节点
    if (hashTable[hashValue] == NULL) {
        hashTable[hashValue] = newNode;
    } else {
        Node* currentNode = hashTable[hashValue];
        while (currentNode->next != NULL) {
            currentNode = currentNode->next;
        }
        currentNode->next = newNode;
    }
}

// 从散列表中删除节点，并返回节点值
int deleteNode(Node** hashTable, int data) {
    // 计算散列值
    int hashValue = data % HASH_SIZE;
    
    // 查找并删除节点
    Node* currentNode = hashTable[hashValue];
    Node* prevNode = NULL;
    while (currentNode != NULL) {
        if (currentNode->data == data) {
            // 删除节点
            if (prevNode == NULL) {
                hashTable[hashValue] = currentNode->next;
            } else {
                prevNode->next = currentNode->next;
            }
            int deletedData = currentNode->data;
            free(currentNode);
            return deletedData;
        }
        prevNode = currentNode;
        currentNode = currentNode->next;
    }
    
    // 没有找到匹配的节点
    return -1;
}

// 基数排序算法
void radixSort(int arr[], int n) {
    // 初始化散列表
    Node* hashTable[HASH_SIZE];
    initHashTable(hashTable);
    
    // 找到数组中的最大值
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 计算最大值的位数
    int digit = 1;
    while (max / digit > 0) {
        // 将数组元素插入散列表
        for (int i = 0; i < n; i++) {
            insertNode(hashTable, arr[i]);
        }
        
        // 从散列表中依次取出元素，并放回原数组
        int index = 0;
        for (int i = 0; i < HASH_SIZE; i++) {
            while (hashTable[i] != NULL) {
                arr[index++] = deleteNode(hashTable, hashTable[i]->data);
            }
        }
        
        // 更新位数
        digit *= 10;
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前：");
    printArray(arr, n);
    
    radixSort(arr, n);
    
    printf("排序后：");
    printArray(arr, n);
    
    return 0;
}