C语言，基数计数排序代码利用链表实现

对于基数计数排序，我们需要先将待排序的数组转化为链表。下面是一个示例代码，实现了将数组转换为链表的功能：

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

typedef struct node {
    int data;
    struct node* next;
} Node;

Node* createList(int* arr, int len) {
    Node* head = NULL;
    Node* tail = NULL;
    for (int i = 0; i < len; i++) {
        Node* newNode = (Node*) malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

接下来，我们可以利用链表实现基数计数排序。具体的实现步骤如下：

1. 找出待排序数组中最大的数，确定最大位数。
2. 以个位数为基准，将链表中的数字放入对应的桶中。
3. 将桶中的数字按照顺序重新放回链表中。
4. 重复2-3步骤，直到完成最高位数的排序。

下面是一个示例代码，实现了基数计数排序：

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

typedef struct node {
    int data;
    struct node* next;
} Node;

// 创建链表
Node* createList(int* arr, int len) {
    Node* head = NULL;
    Node* tail = NULL;
    for (int i = 0; i < len; i++) {
        Node* newNode = (Node*) malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

// 获取数字的某一位数
int getDigit(int num, int digit) {
    int pow = 1;
    for (int i = 0; i < digit; i++) {
        pow *= 10;
    }
    return (num / pow) % 10;
}

// 基数计数排序
void radixSort(Node** headPtr, int maxDigit) {
    for (int digit = 0; digit < maxDigit; digit++) {
        // 初始化桶
        Node* bucket[10] = { NULL };

        // 将链表中的数字放入桶中
        Node* node = *headPtr;
        while (node != NULL) {
            int digitNum = getDigit(node->data, digit);
            if (bucket[digitNum] == NULL) {
                bucket[digitNum] = node;
            } else {
                Node* tail = bucket[digitNum];
                while (tail->next != NULL) {
                    tail = tail->next;
                }
                tail->next = node;
            }
            node = node->next;
        }

        // 将桶中的数字按照顺序重新放回链表中
        Node* newHead = NULL;
        Node* tail = NULL;
        for (int i = 0; i < 10; i++) {
            if (bucket[i] != NULL) {
                if (newHead == NULL) {
                    newHead = bucket[i];
                    tail = bucket[i];
                } else {
                    tail->next = bucket[i];
                    tail = tail->next;
                }
            }
        }
        tail->next = NULL;
        *headPtr = newHead;
    }
}

// 打印链表
void printList(Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

int main() {
    int arr[] = { 120, 23, 56, 89, 234, 542, 24, 9 };
    int len = sizeof(arr) / sizeof(arr[0]);

    Node* head = createList(arr, len);
    printList(head);

    radixSort(&head, 3);
    printList(head);

    return 0;
}

这段代码可以将待排序的数组转换为链表，并且实现了基数计数排序。需要注意的是，我们需要传入链表指针的指针，因为在排序过程中我们需要修改链表头指针的指向。