1、 计算机科学与技术系 课程设计报告 2009 20010 学年第 二 学期 课程课程 数据结构与算法 课 程 设 计 名 称课 程 设 计 名 称 汽车牌照的排序与查找问题 学生姓名学生姓名 学号学号 专业专业班级班级 08 计本（2）班 指导教师指导教师 20010 年 6 月 - 1 - 题目：题目：汽车牌照的排序与查找问题，实现对汽车牌照按多关键字排序及快速查找。其中汽车 牌照有汉字、字母和数字混合排列，例如：皖 A12345。使用基数排序方法进行排序，并在 排序的基础上，利用二分查找思想实现对汽车牌照按多关键字的查找。 一、问题问题分析和任务定义分析和任务定义 此程序要完成如下要求：选
2、择一种数据结构来存储每个车辆的信息（如车主姓名,汽车 等） ，在此基础上进行基数排序，而汽车牌照是由汉字、字母以及数字组成，即多关键字， 其中字母和数字的比较是比较容易实现的， 考虑到汉字的存储等各方面原因， 对汉字的排序 并不是很容易就能完成的，故不能直接对汉字排序。经过分析可知，汽车牌照中的汉字是各 个省市自治区的简称，共有 34 个。这些汉字可以根据其汉语拼音的规则进行排序，然后预 先存放到字符串数组中， 这样每个汉字就对应着一个数组下标， 只要对数组下标进行排序就 可以实现对汉字的排序了。在对车牌号进行查找时，先对车牌号进行排序，然后将车牌号中 的汉字及字符均转换成一个长整形数据存储在
3、一个预先定义的一个一维数组中并把需要查 找的车牌号码也转换成一个长整型数据， 然后在原先的一维数组中使用二分查找来查找该车 牌号码对应的车辆信息。 二、数据结构的选择和概要设计数据结构的选择和概要设计 1、数据结构的选择： 程序要求实现对汽车牌照的排序与查找， 而如果仅仅进行牌照的排序与查找， 则显得程序没 有太大的实用性， 所以考虑在程序中加入例如车主的姓名以及车子的品牌等内容来增加程序 的实用性。为了能够更好的完成这些功能，在这里选用链表来存储所有车辆的信息，用链表 中的单个节点来存储一辆汽车的信息，而对应的各个节点的域中则存储其对应的车辆信息 （如车牌号码、车主姓名、车的品牌等信息） 。
4、在存储汽车牌照中的汉字时，由于汉字在内 存中占用两个字节，需要使用字符串数据来存储。其中的 26 个字母则使用一个一维字符数 组来存储。车主的姓名及车子的品牌则使用一维字符数组来存储。在基数排序时，每趟的数 据收集由两个链队列来完成， 链队列的个数为基数的个数， 两个链队列的队列指针分别指向 每组链队列的队头和队尾。 2、概要设计 为了实现上述功能，需要使用一下函数： main()：主函数 Setlist()：添加车辆函数 Distribute()：进行基数排序每一趟的分配函数 Collect()：进行基数排序每一趟的收集函数 find()：二分查找函数 menu()：菜单函数 print()：输出所有车辆信息函数 insort()：基数排序函数 - 2 - 图 1 各函数间关系如下： 图 2 主函数 main()流程图 main() Distribute() menu() print() Collect() Setlist() find() insort() n=1 n=p n=c 调用子函数 SetList(p) 调用子函数 print() 调用子函数 find(p
