汽车牌照的排序与查找问题.doc

合肥学院 计算机科学与技术系 课程设计报告 2009～2010 学年第二学期 课程 数据结构与算法课程设计名称汽车牌照的排序与查找问题学生姓名学号专业班级指导教师李红 沈亦军2010 年 6月 题目：（汽车牌照的排序与查找问题）实现对汽车牌照按多关键字排序及快速查找。 一、问题分析与任务定义 程序要求能够对汽车牌照进行排序与查找，要对汽车牌照进行排序与查找，首先要清楚汽车牌照有哪几个部分组成。汽车牌照由3个部分组成，第一部分为全国34个省及直辖市的简称，第二部分为26个英文字母中的一个大写字母，第三部分由5个数字组成。汽车牌照有多个关键字组成，因此在对汽车牌照排序的时候可使用基数排序的方法。在进行基数排序时对于汉字和英文字母的操作十分的麻烦且会占用大量的时间，因此先将34个汉字和26个英文字母安一定的顺序分别存放在两个数组中，然后根据汉字和英文字母在数组中所在的位置将汉字和英文字母转化为对应的2个数字。在汉字和英文字母转换为数字后和将其汽车牌照中余下的5个数字依次存放在一个整形的数组中，然后对多个这样的数组可对数组中的9个关键字进行基数排序。因为程序可将汽车牌照进行基数排序，对于一组有序的数进行查找用二分查找会比较节省时间，因此在进行查找的时候使用二分查找的方法。 二、数据结构的选择和概要设计 在程序中自定义一个汽车类型，汽车类型有多个分量组成如：汽车车牌号、车主姓名、汽车品牌、汽车颜色。除了自定义一个汽车类型外还应定义一个顺序表类型，该类型有两个分量，一个为整形的变量，另一个为顺序表栈最后元素的下标。 这两种数据类型描述如下: typedef struct node{ char number[10];//初始输入的汽车牌照号 char name[10];//车主姓名 char chepai[10];//汽车品牌 char color[10];//汽车颜色 int key[M];//处理后的车牌号 struct node *next; }car; int r[10]; int last; }sequenlist; 在程序中新建的car节点应存储在一个单链表中，以便在对节点中的元素进行基数排序和新增节点。采用单链表还能有很好的空间性能，不会照成空间浪费。 定义的顺序表类型主要方便对汽车牌照进行二分查找，将有序的汽车牌照依次转换为数据存放在顺序表中，因此顺序表中的元素是有序序列，在调用查找函数时以顺序表为变量 在顺序表中查找是否存在某个汽车牌照。 本程序要能够实现汽车牌照的排序与查找需要进行多步操作：1:创建一个单链表；2:对单链表中元素进行排序；3:显示排序后的结果4:创建顺序表；5:在顺序表中按汽车牌照进行查找6显示查找结果。 本程序包含6个函数： 1主函数:main(); 2创建单链表函数:creatlist(); 3对单链表排序函数：paixu(); 4创建顺序表函数：sqlset(); 5按汽车牌照进行查找函数：search(); 6输出单链表中所有节点信息函数：print（）； 主函数流程图为： 运行程序 进入主菜单 增加新的汽车信息 退出 输出系统中所有汽车信息 对系统中所有的车按车牌号排序 按车牌号查找 调用creatlist()函数 调用paixu(p)函数 调用sqlset()、search()函数 调用print(p)函数 i=1 i=2 i=3 i=4 i=5 输入i 图1 主函数流程 三、详细设计和编码 1创建单链表算法 在创建一个单链表时，首先要创建节点。创建一个节点的过程为先从键盘输入一个车牌号将其存于节点中的number[10]数组中，然后调用substr(0,2)函数取出车牌号中的第一部分即汉字进行处理，查询该汉字在34省及直辖市中的位置，将其转换为两个数字并存于节点car中key[M]数组中。其具体算法如下： for(j=0;j34;j++){ k3=mark1[j]; if(k2==k3){ b=j; }} k=b/10; f1-key[0]=k; m=b%10; f1-key[1]=m;} 同理将第二部分即英文字母部分转换为两个数字并存于节点car中key[M]数组中。最后将第三部分中的5个数字依次存入节点car中key[M]数组中，并输入节点其它一些信息即完成节点的创建。创建完节点后，将节点插入到链表中。 2基数排序算法 首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次低位关键字进一步排序，以此类推，由低位到高位，由此关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键对记录进行排序后，基数排序完成。 在进行