车牌号管理系统数据结构课程设计报告.pdf

文档介绍：该【车牌号管理系统数据结构课程设计报告 】是由【青山代下】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【车牌号管理系统数据结构课程设计报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..__院计算机工程学院课程设计报告设计名称:数据结构课程设计选题名称:车牌号管理系统姓名:学号:专业班级:软件工程系(院):计算机工程学院设计时间:~:软件工程实验室、教室成绩:指导教师评语:签名:、训练学生灵活应用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求解指定问题。、系统设计、程序编码、测试等基本方法和技能;;,巩固、深化学生的理论知识,提高编程水平,并在此过程中培养他们严谨的科学态度和良好的工作作风。:..2任务根据教材《数据结构-C语言描述》(耿国华主编)和参考书《数据结构题集(C语言版)》(严蔚敏、吴伟民主编)选择课程设计题目,要求通过设计,在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取,每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题,要求课题有一定的深度与难度,有一定的算法复杂性,能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。要求:1、在处理每个题目时,要求从分析题目的需求入手,按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目,最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数,加大代码的重用率。2、.设计的题目要求达到一定工作量(300行以上代码),并具有一定的深度和难度。3、程序设计语言推荐使用C/C++,程序书写规范,源程序需加必要的注释;4、每位同学需提交可独立运行的程序;5、每位同学需独立提交设计报告书(每人一份),要求编排格式统一、规范、内容充实,不少于10页(代码不算);:..:本程序利用基数排序的思想对一批具有结构特征的汽车牌照进行排序,并且利用二分查找的思想对排好序的汽车牌照进行查找。:运行程序时,输入一组要求的数据后,按要求操作,进行排序,查询时程序查找到匹配的数据,输出该关键字的其他信息。:数据包括3项,分别为牌照的号码,车的型号,车主的姓名,其中牌照的一项输入形式为01B7328,前两位代表地区,字母代表车的使用类型,后四位代表车号,查询时要求输入正确的车牌号码。{charname;车主名字charcarname;车名KeyTypekey;子关键字}ADTRecordTypeADTSLinkList{数据元素:关键字,是一个RecordType类型的数组,存放车牌号。数据之间的关系是线性关系;}。主程序中的内容有Voidmain{1初始化加入数据;;;;;:..}(RecordTyper[],inti,pvectorhead,pvectortail)记录数组r中已按低位关键字key[i+1],。,key[d]进行低位优先排序,本算法按第i个关键字key[i]建立10个队列,同一个队列中记录的key[i]相同。Head[j]和tail[j]分别指向各自队列中第一个和最后一个记录(j=0,1,2,。9).head[j]=0表示相应队列为空队列。(RecordTyper[],pvctorhead,pvctortail)本算法从0到9扫描个队列将所有非空队列首尾相接,重新链接成一个链表。(Recordr[],intlength)Length个记录存放在数组r中,执行本算法进行基数排序后,链表中的记录将按关键字从小到大的顺序链接。(SLinkList*l)(SLListl,charkey[])(SLinkList*L)从键盘获得数据。(SLinkList*L)(charkey1[],charkey2[])(charkey1[],charkey2[])判断较小模块之间调用关系主函数调,(3,5),6,7,83调用1,26调用9,10三详细设计主要函数voidDistribute_n(RecordTyper[],inti,shuzihead,shuzitail)//数字分配{intj,p;for(j=0;j=队列的个数;j++)//初始化队列{队列的头指针=0;全部为0对列的尾指针=0;全部为0}p=第一个数据在数组中的位置while(第一个数据在数组中的位置!=0){j=第一个数据的第i位在第几个队列if(头指针==0)头指针=第一个数据载表中的位置;else该队列已有数据的下一个位置=p否则将该数在静态链表中的位置放在在同一个:..尾指针=p;tial[j]=该数在静态链表中的位置p=下一个数据的位置值;}}voidCollect_n(RecordTyper[],shuzihead,shuzitail)//收集重新构成链表{intj=0,t;while(head[j]==0)++j;//=head[j];t=tail[j];//把head[j]给第一个数据的位置while(j9){++j;while((j9)(head[j]==0))找到不为0的队列++j;if(head[j]!=0){r[t].next=head[j];t=tail[j];}}r[t].next=0;//使最后一个数的next=0}voidradixsort(SLinkList*l)//基数排序{intn=l-length;数组的长度zimuhead,tail;shuziheads,tails;for(inti=0;i=n-1;i++)l-r[i].next=i+1;初始化静态链表,确定静态链表的各个元素的位置l-r[n].next=0;使最后一个数的next等于0for(i=6;ii__){Distribute_n(l-r,i,heads,tails);调用分配函数Collect_n(l-r,heads,tails);调用收集函数}Distribute_c(l-r,2,head,tail);调用分配函数Collect_c(l-r,head,tail);调用收集函数for(i=1;ii__){Distribute_n(l-r,i,heads,tai调用分配函数Collect_n(l-r,heads,tails);调用收集函数}}voidarrange(SLinkList*l)//整序{intp,q;RecordTypebuf;建立中间变量p=第一个元素在表中的位置;p指向第一个元素在表中的位置for(inti=1;i表的长度;i++){while(pi)p=第p个元素的下一个数在表中的位置;q=第p个元素的下一个数在表中的位置;if(p!=i){buf=第p个元素的地址;第p个元素的地址=第i个元素的地址;交换第i个元素的地址与第p个元素的地址第i个元素的地址=buf;第i个元素的下一个数在表中的位置=p;}p=q;}}voidGetData(SLinkList*L)//获得数据{charkey='0';intj=1;cout“请输入车牌号码及车名与车主名,用'#'结束“endl;cout“例:..:01B3456“endl;cout“车牌号=“;for(inti=0;ii++){cinkey;输入数据第一个数据的车牌号码=key;}cout“车名:“;cin第一个数据的车名;cout“车主名:“;cin第一个数据的车主名;while(key!='#'){j++;coutendl“车牌号=“;for(inti=0;ii++){cinkey;输入第j个数据的车牌号码if(key=='#'){j__;break;}第j个数据的车牌号码=key;}if(key=='#')break;cout“车名:“;cinL-r[j].carname;cout“车主名:“;cinL-r[j].name;}L-length=j;}intbinsearch(SLinkList*L,chars)//折半查找{intk=0,sum=0,ss=0,mid,high,low=1;high=L-length;while(low=high){mid=(high+low)/2;if(Equal(s,L-r[mid].key))return(mid);调用判断相等函数elseif(Little(s,L-r[mid].key))high=mid-1;调用比较大小函数elselow=mid+1;}return(0);},车牌号码,车主名以及车名。从键盘输入需要的数据。如车牌号:20W4521车名bmw车主名zzx车牌号:11F4587车名lanbogine车主名zzp车牌号:55F1254车名benz车主名xcl初始化成功。。车牌号:20W4521车名bmw车主名zzx车牌号:11F4587车名lanbogine车主名zzp车牌号:55F1254车名benz车主名xcl与输入结果一致。,用基数排序的方法。11F4587lanboginezzp20W4521bmwzzx55F1254benzxcl与预期结果一致。:..。查找成功。,首先出现主界面,选项一,初始化表加入数据。选项二,遍历表。选项三,对车牌号排序。选项四,查找。选项五,退出。运行查找之前一定要进行排序,因为是折半查找,所以要先进行排序。,输入车牌号码,例如01B3456,及车主的姓名,车的名字。,顺序输出所有的数据4,按基数排序的方法进行排序5,查找,输入要查找的车牌号码,若查找成功则返回需要的车牌号及车主名与车名,若没有此信息则返回没有此车牌号。六测试成果七附录(源程序清单)#defineKEY_SIZE7#defineLIST_SIZE10#includeiostreamusingnamespacestd;typedefstruct{charkey[KEY_SIZE];charname;charcarname;intnext;}RecordType;typedefstruct{RecordTyper[LIST_SIZE];intlength;intkeynum;}SLinkList;typedefintshuzi;typedefintzimu;voidInitSLList(SLinkList*L)//链表初始化{L-length=0;L-keynum=7;}voidDistribute_n(RecordTyper[],inti,shuzihead,shuzitail)//数字分配{intj,p;for(j=0;jj++){head[j]=0;tail[j]=0;}p=;while(p!=0){j=int(r[p].key[i]-'0');if(head[j]==0)head[j]=p;elser[tail[j]].next=p;tail[j]=p;p=r[p].next;}}voidDistribute_c(RecordTyper[],inti,zimuhead,zimutail)//字母分配{intp,j;for(j=0;jj++){head[j]=0;tail[j]=0;}:..p=;while(p!=0){j=int(int(r[p].key[i])-A');if(head[j]==0)head[j]=p;elser[tail[j]].next=p;tail[j]=p;p=r[p].next;}}voidCollect_n(RecordTyper[],shuzihead,shuzitail)//收集重新构成链表{intj=0,t;while(head[j]==0)++j;=head[j];t=tail[j];while(j9){++j;while((j9)(head[j]==0))++j;if(head[j]!=0){r[t].next=head[j];t=tail[j];}}r[t].next=0;}voidCollect_c(RecordTyper[],zimuhead,zimutail)//字母类型收集重新构成链表{intj=0,t;while(head[j]==0)++j;=head[j];t=tail[j];while(j25){++j;while((j25)(head[j]==0))++j;if(head[j]!=0){r[t].next=head[j];t=tail[j];}}r[t].next=0;}voidradixsort(SLinkList*l)//基数排序{intn=l-length;zimuhead,tail;shuziheads,tails;for(inti=0;i=n-1;i++)l-r[i].next=i+1;l-r[n].next=0;for(i=6;ii__){Distribute_n(l-r,i,heads,tails);//调用分配函数Collect_n(l-r,heads,tails);//调用收集函数}Distribute_c(l-r,2,head,tail);//调用分配函数Collect_c(l-r,head,tail);//调用收集函数for(i=1;ii__){Distribute_n(l-r,i,heads,tails);//调用分配函数Collect_n(l-r,heads,tails);//调用收集函数}}voidarrange(SLinkList*l)//整序{intp,q;RecordTypebuf;p=l-;//p指向第一个记录的当前位置for(inti=1;il-length;i++){while(pi)p=l-r[p].next;//找到第i个记录,并用p指示其在表中的当前位置。q=l-r[p].next;if(p!=i){buf=l-r[p];l-r[p]=l-r[i];l-r[i]=buf;//交换p与il-r[i].next=p;//使得被移走的记录使得以后可以由while循环找回}p=q;}}voidGetData(SLinkList*L)//获得数据{charkey='0';intj=1;cout“请输入车牌号码及车名与车主名,用'#'结束“endl;cout“例如::..01B3456“endl;cout“=“;for(inti=0;ii++){cinkey;L-[i]=key;}cout“车名:“;cinL-;cout“车主名:“;cinL-;while(key!='#'){j++;coutendl“车牌号=“;for(inti=0;ii++){cinkey;if(key=='#'){j__;break;}L-r[j].key[i]=key;}if(key=='#')break;cout“车名:“;cinL-r[j].carname;cout“车主名:“;cinL-r[j].name;}L-length=j;}voidSLListTraverse(SLinkList*L)//遍历静态表{inti,j;coutendl;cout“车牌号““““车名““““车主名“endlendl;for(i=1;i=L-length;i++){for(j=0;jj++)coutL-r[i].key[j];cout““L-r[i].carname““;coutL-r[i].nameendl;}}intEqual(charkey1[],charkey2[])//判断相等{for(inti=0;ii++){if(key1[i]!=key2[i])return0;}return1;}intLittle(charkey1[],charkey2[])//判断较小{for(inti=0;ii++){if(key1[i]key2[i])return1;elseif(key1[i]key2[i])return0;}return0;}intbinsearch(SLinkList*L,chars)//折半查找{intk=0,sum=0,ss=0,mid,high,low=1;high=L-length;while(low=high){mid=(high+low)/2;if(Equal(s,L-r[mid].key))return(mid);elseif(Little(s,L-r[mid].key))high=mid-1;elselow=mid+1;}return(0);}voidmain(){inti;SLinkListl;do{cout“(必须先排好序)5退出“endl;cini;switch(i){case1:InitSLList(GetData(break;case2:SLListTraverse(break;case3:radixsort(arrange(SLListTraverse(break;case4:intfind;chars;cout“请输入要查找的车牌号码“endl;cins;find=binsearch(l,s);if(find){cout“在表中的位置为“binsearch(l,s)endl;cout“车名“;[find].carnameendl;cout“车牌号码“;for(inti=0;ii++)[find].key[i];coutendl;cout“车主名“;:..[find].nameendl;}elsecout““endl;break;case5:break;}}while(i!=5);},功能少,只有两个功能,一个是排序,一个是查找,排序要用到基数的排序的方法,就是一种多关键字的排序,而查找用到的则是二分查找。虽然程序的内容少,看似简单,但是基数排序是个很难的排序,也是一个让我理解了好久才弄懂的,这个排序非常的经典,当我看到这个排序的思想的时候我就感觉这个排序实在是绝,它与其他的排序的方法都不同,别的排序方法都是比较,移动关键字,但是它是比较关键字中的子关键字,从最后一位关键字开始比较,如果是数字就根据关键字中的组后一个子关键字分别放入十个队列中,如果是字母则类似,放入二十六个队列中。在收集函数则是将队列的首尾相连,重新构成一个链表,如此反复的调用这些函数,最后就会形成以个有序的静态链表,但是此时的静态链表只是逻辑结构中的有序,而不是储存结构中的有序,还要在进行一次整序,使链表真正的有序。在调试过程中参考书中的代码以及自己在图书馆中的借的相关书籍,最后在对程序进行了进一步的调整,完成了代码的调试。在折半查找中,调用了比较跟判断相等的函数,根据书上的折半查找的算法进行改进,就可以成功了。本次课程设计中最重要的一点就是掌握基数排序,对于折半查找进行一定的改进,最后的遍历自己随便怎么写都行。通过本次课程设计,我对排序的方法上又多了一种认识,多了一种理解,对程序的把握上更加准确了。增加了自己的编程能力,也对数据结构这门课程有了更深的认识。今后将更加的努力学****相关知识来弥补自己在很多方面的不足,缩小跟别人:..