1、算法与数据结构课程设计 1 xxxx 大学大学 课课 程程 设设 计计 实实 践践 报报 告告 学学 院：院：计算机与信息工程学院 课程名称：课程名称： 算法与数据结构 任课教师：任课教师： xxx 班班 级：级： xx 班 学学 号：号： xxx 姓姓 名：名： xxx 同组学生：同组学生： 实践地点实践地点: xx 大学 实践时间：实践时间：2010 年 8 月 19 日至 2010 年 9 月 3 日 算法与数据结构课程设计 2 一、 实验题目：汽车牌照的快速查找 二、 实验要求： 利用链式基数排序和折半查找对一批汽车牌照进行排序和查找 三、 问题分析： 想要完成题目要求，需要选择链表对
2、汽车信息（包括汽车牌照、汽车颜色、 汽车商标、汽车的注册时间、汽车所有者等）进行存储，并在此基础上进行多关 键字排序，因为汽车牌号是汉字、字母和数字的组合。考虑到对汉字进行排序是 一件不可能的事，因此对各省市的简称可以放到字符串数组中，也就可以通过数 组下标进行排序， 字母可以选择同汉字一样的处理方法， 数字却很容易进行排序。 因此，排好序的汽车牌照其实就是一组长整型数组，例如根据行政规划对各省市 的简称进行存储，如汽车牌照京 C0123，转换为长整型数组后为 00020123 如何对排好序的车辆信息进行折半查找呢？因为存储好的汽车信息其实就 是一组长整型数组，而所输入的信息就是一个长整型数据
3、，然后再那个数组中进 行折半查找既可以实现。 四、 设计思路及流程： 为了完成所需的功能，需要的函数及其功能如下： main()：主函数模块 SetList()：添加车辆函数 Distribute()：进行基数排序每一趟的分配函数 Collect()：进行基数排序每一趟的收集函数 find()：二分查找函数 menu()：主函数显示菜单模块 print()：输出所有车辆信息函数 paixu()：基数排序函数 以下为各函数流程图 主函数流程图： 汽车信息函数 SetList(p)流程图： 算法与数据结构课程设计 3 排序子函数 paixu(p)的流程图 ： 查找子函数 find(p)的流程图 开
4、始 结束 申请一结点 p 并为其分配内存空 间。 head=NULL head=p 输入汽车的相应信息，经过相应 的处理后存入结点 p 相应的域。 将该结点按尾插法插入到链表 的相应位置 返回该链表的头指针 Y N 开始 结束 n=t 输入 n n=c n=q 调用子函数 SetList(p) 调用子函数 print() 调用子函数 find(p) n=s Y N Y Y Y N N N 算法与数据结构课程设计 4 五、 详细算法思想： 1、基数排序的过程： 首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对 记录进行初步排序；在此基础上，再按次低位关键字进一步排序，以此类推，由 低位到高位，由此关键字到主关键字，每一趟排序都在前一趟排序的基础上，直 到按最高位关键对记录进行排序后，基数排序完成。 在基数排序中，基数是各个关键只的取值范围。若待排序的记录是十进制， 则基数是 10；若待排序的记录是由若干个字母组成的单词，则基数为 26，也就 是说，从最右边的字母开始对记录
