计算机等级考试C语言程序设计例解(01)

文章作者 100test 发表时间 2007:03:10 17:18:56
来源 100Test.Com百考试题网

01. 试按以下给出的基数排序算法思想为整数链表编写一个排序函数
解：
基数排序是按表元键值的各位值进行排序。
设有一个整数链表，其中表元的键值为不超过三位数的整数，不妨设键值形式ABC。其中A表示键值的百位数，B为十位数，C为个位数。首先按键值中的个位值C对链表作分拆和链接，先把链表分拆成多至10个队列链表，然后以C的值从0至9的顺序把分拆后的十个队列链表重新收集成一个链表。接着依次对键值中的B和A进行同样的分拆和链接操作，则最后收集起来的链表是按键值从小到大排序链接的。如有一个链表按它们的键值其表元的链接顺序依次为：
153 678 56 288 457 653 721 876 433 254
按它们的键值的个位分拆，得到十个队列链表，列出它们的键值顺序有：
0： 空链表
1： 721
2： 空链表
3： 153 653 433
4： 254
5： 空链表
6： 56 876
7： 457
8： 678 288
9： 空链表
顺序将它们收集一起后，链表的键值顺序有：
721 153 653 433 254 56 876 457 678 288
再按它们键值的十位分拆，得到十个队列链表，列出它们的键值顺序有：
0： 空链表
1： 空链表
2： 721
3： 433
4： 空链表
5： 153 653 254 56 457
6： 空链表
7： 876 678
8： 288
9： 空链表
顺序将它们收集在一起后，链表的键值顺序有：
721 433 153 653 254 56 457 876 678 28

再按它们键值的百位分拆，得到十个队列链表，列出它们的键值顺序有：
0： 56
1： 153
2： 254 288
3： 空链表
4： 433 457
5： 空链表
6： 653 678
7： 721
8： 876
9： 空链表
顺序将它们收集一起后，链表的键值顺序有：
56 153 254 288 433 457 653 678 721 876
这是一个按键值从小到大链接的链表。