数据结构基数排序C语言

基数排序是一种非比较排序算法，它根据数据元素的每个位上的值进行排序。下面是基于顺序队列的基数排序的C语言实现：

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

// 定义数据元素的数据结构
typedef struct {
    int key;
} DataType;

// 定义队列的数据结构
typedef struct {
    DataType *data;
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *queue, int size) {
    queue->data = (DataType *)malloc(size * sizeof(DataType));
    queue->front = queue->rear = 0;
}

// 入队操作
void enqueue(Queue *queue, DataType element) {
    queue->data[queue->rear++] = element;
}

// 出队操作
DataType dequeue(Queue *queue) {
    return queue->data[queue->front++];
}

// 判断队列是否为空
int isEmpty(Queue *queue) {
    return queue->front == queue->rear;
}

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

// 基数排序
void radixSort(DataType *data, int size, int digit) {
    int i, j, k;
    Queue *queues = (Queue *)malloc(10 * sizeof(Queue)); // 创建10个队列，用于存放每个位上的数据元素

    // 初始化队列
    for (i = 0; i < 10; i++) {
        initQueue(&queues[i], size);
    }

    // 根据每个位上的值将数据元素入队
    for (i = 1; i <= digit; i++) {
        for (j = 0; j < size; j++) {
            int digitValue = getDigit(data[j].key, i);
            enqueue(&queues[digitValue], data[j]);
        }

        // 将队列中的数据元素按顺序出队，更新原数组
        k = 0;
        for (j = 0; j < 10; j++) {
            while (!isEmpty(&queues[j])) {
                data[k++] = dequeue(&queues[j]);
            }
        }
    }

    // 释放队列的内存空间
    for (i = 0; i < 10; i++) {
        free(queues[i].data);
    }
    free(queues);
}

int main() {
    int size = 10;
    int digit = 3;
    DataType data[] = {{710}, {342}, {45}, {686}, {6}, {841}, {429}, {134}, {68}, {264}};

    radixSort(data, size, digit);

    // 输出排序结果
    for (int i = 0; i < size; i++) {
        printf("%d ", data[i].key);
    }
    printf("\n");

    return 0;
}

运行以上代码，输出结果为：6 45 68 134 264 342 429 686 710 841