看数据结构写代码（65）基数排序数据结构

欢迎指出代码不足
参考书本：严蔚敏《数据结构 .C语言版》

// RadixSort.cpp : 定义控制台应用程序的入口点。 //#include "stdafx.h" #define MAX_SIZE 1000//最大空间 #define RADIX10//关键字基数 #define KEY_NUM 3//关键字个数struct SLNode{//静态链表节点 int key; int next; }; struct SLList{//静态链表 SLNode base[MAX_SIZE]; int keyNum; //关键字数量 int len; }; typedef int Arrtype [RADIX]; //指针数组void initList(SLList * list,int * array,int num){ for (int i = 0; i < num; i++){ list->base[i].next = i + 1; list->base[i+1].key = array[i]; } list->base[num].next = 0; list->len = num; list->keyNum = 3; }int ord(int key,int i){//获取地址 (0~9 ) if (i == 0){ return key % 10; } else if(i == 1){ return key % 100 / 10; } else{ return key / 100; } }//分配函数 //i : 关键字次数 //f: 队头指针数组 //e:队尾指针数组 void distribute(SLList * list,int i,Arrtype * f,Arrtype * e){ for (int j = 0; j < RADIX; j++) (*f)[j] = 0; //清空队头数据 int next = list->base[0].next; for (; next != 0; next = list->base[next].next){ int index = ord(list->base[next].key,i); if ((*f)[index] == 0){ (*f)[index] = next; } else{ list->base[(*e)[index]].next = next; } (*e)[index] = next; } printf("\n"); }int getNext(Arrtype f,int i){ for ( ; i < RADIX; i++) { if (f[i] != 0){ return i; } } return -1; }//收集函数(分配函数已经将需要排序的数组分块了，现在需要将这些块链接起来） void collect(SLList * list,Arrtype f,Arrtype e){ int first = getNext(f,0); if (first != -1){ list->base[0].next = f[first]; //设置头指针的后继 int next = getNext(f,first+1); int pre = first; for (; next != -1; ){ list->base[e[pre]].next = f[next]; pre = next; next = getNext(f,next+1); } list->base[e[pre]].next = 0; //设置最后节点的后继为 0 }}void printList(SLList list){ printf("------------------打印静态链表--------------------\n"); int next = list.base[0].next; while (next != 0){ SLNode nextNode = list.base[next]; printf("%d\t",nextNode.key); next = nextNode.next; } printf("\n"); }void radixSort(SLList * list){ Arrtype f; Arrtype e; for (int i = 0; i < list->keyNum; i++){ distribute(list,i,&f,&e); //分配,时间复杂度 O(n),n为排序数组的大小 collect(list,f,e); //收集... printList(*list); } }static int testArray[] = {656,301,305,998,999,875,832,423,432,565}; int _tmain(int argc, _TCHAR* argv[]) { SLList list; initList(&list,testArray,10); radixSort(&list); return 0; }

运行截图：打印了 3次静态链表，分别是对 “个位”，“十位”，“百位” 分配，收集之后静态链表的情况。
【看数据结构写代码（65）基数排序】