下载可编辑
课程设计报告
一. 问题的分析与定义
题目：汽车拍照的排序与查找问题
此题目主要要求对汽车牌照进行基数排序，和用二分查找的思想进行查找，这两
种方法思想并不难，但是要对汽车牌照进行排序和查找，此问题涉及到的主要问题是： 首先的问题就是，用何种存储结构对汽车信息和汽车牌照进行存储汽车牌照，然后汽车牌照不是单单是数字，而且是汉字、字母与数字混合排列的，这就不仅仅对数字进行基数排序了，还要对字母进行相关处理，方可用基数排序的方法进行排序。经过最后查找资料、分析将汉字、字母转化为数字处理，汉字代表汽车牌照的地区，共有34个省市自治区简称，即34个汉字，26个英语大写字母，分别用数组存储这34个汉字和26个大写字母，将他们转化为数字，最后再用基数排序，方可达到题目要求。在二分查找问题中，是对汽车牌进行查找，首先将要查找的汽车牌转换为数字形式，再用二分查找递归算法，找不到返回一个值，找到再返回一个值，再找到这个位置，输出查找的所有信息，即可达到题目要求。
二．数据结构的选择和概要设计
1.数据结构的选择
对于汽车牌照进行排序和查找，为了使程序尽可能的实用性，我将定义，车主，车牌号，车色，车型为一个结构类型，用链表的形式存储这些信息，为了方便对汽车牌照进行排序，在定义一个数组存储将汉字、字母转化后的长数据类型，汉字和字母都用两个字符来表示。在基数排序中，基数排序每趟的收集由两个链队列收集，链队列的个数为基数的个数。在二分查找中，是对汽车牌号进行查找，首先将汽车牌号转化为数字，再用递归算法查找。最后再将所有车辆信息输出，达到题目要求。
2.概要设计
为了实现上述功能，需要的函数及其功能如下： 1).主函数main()
2)车辆信息录入函数Setlist()
3)基数每一趟的分配函数Distribute() 4)基数每一趟的收集函数Collect() 5)基数排序函数paixu() 6)二分查找函数search() 7)输出函数print() 各函数关系如下：
Setlist Distribute Collect main search print Twsearch paixu .专业.整理.
下载可编辑
主函数流程图：
开始 输入n n=1 Y 调用子函数SetList(p) N n=2 Y 调用子函数paixu(p) N n=3 N Y 调用子函数search(p) n=4 N Y 调用子函数print() N n=5 Y 结束
.专业.整理.
下载可编辑
三．详细设计和编码
1.汽车节点类型 typedef struct node{
int keynum[M]; //汽车牌照转换为十进制后的数据 char key[10]; //汽车牌照号 char color[10]; //汽车颜色 char type[10]; //汽车类型 char name[10]; //车主姓名
struct node *next; //指向下一个节点的指针域 }Rnode;
2.基数排序的过程
链式基数排序就是在链式存储结构下通过反复的分配、收集运算来进行排序的。 首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次低位关键字进一步排序，以此类推，由低位到高位，由此关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键对记录进行排序后，基数排序完成。车牌号是由一个汉字、一个大写字母和五个数字组成，由于有34个省自治区简称，字母有26个，本来基数应该是34，但这样一来太麻烦，而且不好分析，故将汉字、字母转换为十进制数再进行基数排序，这样做的好处是，基数都是从0~9，比较简便，而且易懂。为了更好的分析此算法，举一个例子：
一组记录的关键字为：83，8，184，505，930，589，63，109，278 采用基数排序方法对其进行排序。
上述这组关键字的值都在0≦K≦99的范围内，我们可以把每一个数位上的十进制数字看
0120
成是一个关键字，即将关键字K看成由3个关键字K，K，K组成。其中，K是百位上的数
12
字，K是十位上的数字，K是个位上的数字。因为十进制的基数是10，所以，每个数位上的
22
数字都可能是0~9中的任何一个。先按关键字K来分配所有参与排序的元素，将K=0的元
222
素放在一组、K=1的元素放在一组、……、K=9的元素放在一组。再按K的值由0到9的顺序收集各组元素，形成序列（930，063，083，184，505，278，008，109，589，269）。
11
对上述序列中的元素再按关键字K来分配，也分成10组。然后再按K的值由0到9的顺序收集各组元素，形成序列（505，008，109，930，063，269，278，083，184，589）。
00
对该序列中的元素再按关键字K来分配。然后按K的值由0到9的顺序收集各组元素，形成序列（008，063，083，109，184，267，278，505，589，930）。基数排序完成。
分析该例，可以看出基数排序的思想是：首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次地位关键字进一步排序。依次类推，由低位到高位，由次关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键字对记录进行排序后，基数排序完成。
因此，在汽车牌照的基数排序中，首先将汽车牌照的汉字、字母全部转化为十进制数，以便于基数排序。汉字和字母是由两个字符表示，转换好后方可进行基数排序。
接下来就是如何收集各组记录。从上述例子可看出，各组记录的收集遵循“先进入该组的记录将先被收集”的原则可知，各组序列以列来描述较为精确。因为要进行多次的分配与收集，为节省存储空间及运算方便，采用链队列来存储各组序列。链队列的数量与基数一致，若基数为RAX，则令f[0]~f[RAX-1]分别指向RAX个链队列的队头节点，令r[0]~r[RAX-1]分别指向RAX个队列的队尾节点。每次分配前，将RAX个链队列置空，即
for(i=0;i .专业.整理.
汽车牌照课程设计报告
