链式基数排序 c语言

链式基数排序是一种基于链表的排序算法，用于对数据进行多关键字排序。它的基本思想是将单个关键字拆分成若干项，并将每一项作为一个新的关键字进行排序。对于整数或字符串类型的关键字，可以将其拆分为单个数字或单个字母。

链式基数排序的具体步骤如下：
1. 定义链结构和链队列结构。
2. 初始化带头结点的链队列。
3. 判断带头结点的链队列是否为空，如果为空则说明排序完成。
4. 从最低位的关键字开始，将序列中的数据根据关键字的不同值分配到不同的队列中。
5. 按关键字从小到大（升序）收集起来。
6. 重复上述步骤，直到最高位分配—收集完成，此时序列有序。

下面是一个示例代码的实现：

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

#define MAX_DIGIT 10  // 假设关键字的最大位数为10

// 定义链结构
typedef struct node {
    int data;
    struct node* next;
} Node;

// 定义链队列结构
typedef struct queue {
    Node* front;  // 队头指针
    Node* rear;   // 队尾指针
} Queue;

// 初始化带头结点的链队列
void initQueue(Queue* q) {
    q->front = q->rear = (Node*)malloc(sizeof(Node));
    q->front->next = NULL;
}

// 判断带头结点的链队列是否为空
int isQueueEmpty(Queue* q) {
    return (q->front == q->rear);
}

// 带头结点的链队列入队操作
void enqueue(Queue* q, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    q->rear->next = newNode;
    q->rear = newNode;
}

// 带头结点的链队列出队操作
int dequeue(Queue* q) {
    if (isQueueEmpty(q)) {
        printf("Error: Queue is empty\n");
        exit(EXIT_FAILURE);
    }
    Node* temp = q->front->next;
    int data = temp->data;
    q->front->next = temp->next;
    if (q->rear == temp) {  // 若删除的是最后一个结点，则修改队尾指针
        q->rear = q->front;
    }
    free(temp);
    return data;
}

// 取关键字的某一位的值
int getDigit(int num, int digit) {
    int i;
    for (i = 0; i < digit; i++) {
        num /= 10;
    }
    return num % 10;
}

// 检索表中最大的值是几位数
int getMaxDigit(int* arr, int length) {
    int maxDigit = 1;
    int i;
    for (i = 1; i < length; i++) {
        if (arr[i > arr[i - 1]) {
            maxDigit = arr[i];
        }
    }
    int digit = 0;
    while (maxDigit) {
        maxDigit /= 10;
        digit++;
    }
    return digit;
}

// 基数排序算法的实现
void radixSort(int* arr, int length) {
    int maxDigit = getMaxDigit(arr, length);
    int i, j, k;
    Queue queues