东北大学信息科学与工程学院数据结构课程设计报告 题目 汽车牌照的快速查询课题组长 肖瑶课题组成员 陈果 张帅专业名称 计算机科学与技术班级 计算机1307指导教师 杨雷 2015 年 1月课程设计任务书题目： 汽车牌照的快速查询问题描述：在汽车数据的信息模型中，汽车牌照是具有结构特点的一类关键字。汽车牌照是字母和数字混编的，例如01B7238。利用查找和排序算法，实现辽宁省内汽车牌照的快速查找。设计要求：设计汽车牌照的快速查询程序。（1）采用顺序表、静态链表等数据结构。（2）利用静态链表对汽车牌照进行链式基数排序。（3）采用折半查找汽车牌照。（4）可以按城市进行分块索引查找。（5）其它完善性功能。指导教师签字：2014年12月24日 目录1 课题概述11.1 课题任务11.2 课题原理11.3 相关知识32 需求分析22.1 课题调研22.2 用户需求分析23 方案设计23.1 总体功能设计23.2 数据结构设计23.3 函数原型设计23.4 主算法设计34 方案实现74.1 开发环境与工具74.2 程序设计关键技术74.3 个人设计实现（按组员分工）4.3.1 肖瑶设计实现74.3.1 张帅设计实现104.3.1 陈果设计实现145 测试与调试125.1 个人测试（按组员分工）125.1.1 肖瑶测试125.1.2 张帅测试145.1.3 测试155.2 组装与系统测试156 课题总结176.1 课题评价176.2 团队协作176.3 下一步工作176.4 个人设计小结（按组员分工）186.4.1 肖瑶设计小结186.4.2 陈果设计小结186.4.3 张帅设计小结197 附录A 课题任务分工20A-1 课题程序设计分工20A-2 课题报告分工21 附录B 课题设计文档（光盘）22B-1课程设计报告（电子版）22B-2源程序代码（*.H，*.CPP）22B-3工程与可执行文件）22 B-4屏幕演示录像文件（可选）22 附录C 用户操作手册（可选）22C.1 运行环境说明22C.2 操作说明22课题概述1.1课题任务 在汽车数据的信息模型中，汽车牌照是具有结构特点的一类关键字。汽车牌照是字母和数字混编的，例如01B7238。利用查找和排序算法，实现辽宁省内汽车牌照的快速查找。设计汽车牌照的快速查询程序。（1）采用顺序表、静态链表等数据结构。（2）利用静态链表对汽车牌照进行链式基数排序。（3）采用折半查找汽车牌照。（4）可以按城市进行分块索引查找。（5）其它完善性功能。1.2 课题原理 通过输入汽车牌照信息，保存在一个文件中。程序从文件中读入信息，把车牌号码转换成相应的关键字并把车牌信息和关键字保存在链表中。再通过链式基数排序算法整理这些信息便于查找，最后通过折半查找算法实现快速查找功能。1.3 相关知识 一个汽车牌照相当于一辆汽车的身份证,因此通过查询汽车牌照便可知道这辆汽车的主人、品牌等信息。汽车牌照是由汉子、字母及数字组成，即多关键字，其中数字和字母的比较1容易实现的，考虑到汉字的存储等各方面的原因，对汉字的排序并不是很容易就能完成的，因此不能直接对汉字排序。但特殊的是，汽车牌照中的汉字是各个省、直辖市及自治区的简称（比如辽代表辽宁，京代表北京），一共34个。但是由于汉语拼音可以和英文字母相互转换，因此可以按照汉语拼音的规则进行排序。 需求分析2.1 课题调研 汽车牌照由汉子、字母、数字组成，一汉字+字母+数字方式呈现。要实现对车牌号码的排序与查找就得想办法把汉字和字母转换成数字。2.2 用户需求分析 能对车牌号码实现链式基数排序，并能用查找算法让用户户能根据车牌号码查到相关信息，能够输出车牌信息。 方案设计3.1 总体功能设计1.从文件读入数据保存进链表2.对车牌进行基数排序3二分查找查询汽车牌照4.输出车牌信息3.2 数据结构设计 程序要求实现对汽车牌照的排序与查找，而如果仅仅进行牌照的排序与查找，则显得程序没有太大的实用性，所以考虑在程序中加入例如车主的姓名以及车子的品牌等内容来增加程序的实用性。为了能够更好的完成这些功能，在这里选用链表来存储所有车辆的信息，用链表中的单个节点来存储一辆汽车的信息，而对应的各个节点的域中则存储其对应的车辆信息（如车牌号码、车主姓名、车的品牌等信息）。在存储汽车牌照中的汉字时，由于汉字在内存中占用两个字节，需要使用字符串数据来存储。其中的26个字母则使用一个一维字符数组来存储。车主的姓名及车子的品牌则使用一维字符数组来存储。在基数排序时，每趟的数据收集由两个链队列来完成，链队列的个数为基数的个数，两个链队列的队列指针分别指向每组链队列的队头和队尾。 3.3 函数原型设计main()：主函数；Rnode *Setlist()：添加车辆函数；void Distribute(Rnode *q,int j)：进行基数排序每一趟的分配函数；void Collect()：进行基数排序每一趟的收集函数；int Search_Bin(Rnode *q,long int k,int low,int high)；void find(Rnode *q)：二分查找函数；void menu()：菜单函数；void print()：输出所有车辆信息函数；Rnode *RadixSort(Rnode *p)：基数排序函数；3.4 主算法设计建立链表，添加汽车牌照信息：开始结束申请一结点p并为其分配内存空间head=NULLhead=p输入汽车的相应信息，经过相应的处理后存入结点p相应的域。将该结点按尾插法插入到链表的相应位置返回该链表的头指针YN对车牌号码进行基数排序：开始结束i=M-1i=0调用Distribute及Collect函数i+遍历排序好的链表将每个车辆的牌照号转换为长整型数据存于一个一维数组AMAX中。YN按车牌号码查询：开始结束输入需要查找的牌照将待查找的牌照号处理后，存于一整型变量中调用二分查找函数并返回cc=-1没有查找成功查找成功并输出该车的信息YN各函数间的关系：main()Distribute()menu()print()Collect()Setlist()find()RadixSort()Search_Bin()菜单界面，选择功能：n=1n=pn=c调用子函数SetList(p)调用子函数print()调用子函数find(p)调用子函数paixu(p)n=sYNNYYNN开始输入nNNYn=qNNY结果NN 方案实现4.1 开发环境与工具 Windows 7，CodeBlocks4.2 程序设计关键技术 1. 把车牌号码转换成用于比较和排序的关键字：设立一个字符数组存26各大写字母，再设一个string类型数组存34省、直辖市、自治区各地的简称。那么汉字和字母就可转化成它们在数组中的位序数字； 2.递归实现二分查找算法； 3.链式基数排序的实现；4.3 个人设计实现（按组员分工）4.3.1 肖瑶设计实现Rnode *SetList()/头插法建立链表，从文件中读取信息保存到链表中 FILE *f1; Rnode *head,*p,*l; int m,j,k; string r; if(f1=fopen(汽车管理.txt,r)=NULL) printf(不能打开文件!); head=NULL; p=(Rnode *)malloc(sizeof(Rnode); while(fscanf(f1,%s%s%s,p-key ,p-name ,p-paizi)!=EOF) /头插法建链表 if(head=NULL) l=head=p; else l-next=p; l=p; p=(Rnode *)malloc(sizeof(Rnode); p-next=NULL; p=head; while(p!=NULL) string key1=(string)p-key; string key2=key1.substr(0,2); for(j=0;j33|k0) cout=您输入的车牌号码错误,请重新选择输入!keynum0=s; s=k%10; p-keynum1=s; for(int h=0;hkey2=name2h) m=h; if(m25|m0) cout=您输入的车牌号码错误,请重新选择输入!endl; break; s=m/10;