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

1、淮海工学院计算机工程学院课程设计报告设计名称：数据结构课程设计选题名称：汽车牌照治理系统姓名：学号：专业班级：计算机科学与应用G计111系院：计算机工程学院设计时间：2021.12.242021.1.4设计地点：软件工程实验室、教室成绩:指导教师评语:签名：1 .课程设计目的1、练习学生灵活应用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求解指定问题.2 .初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等根本方法和技能；3 .提升综合运用所学的理论知识和方法独立分析和解决问题的水平；4 .练习用系统的观点和软件开发一般标准进行软件开发,稳固、深化学生的理论知识,

2、提升编程水平,并在此过程中培养他们严谨的科学态度和良好的工作作风.2 .课程设计任务与要求：任务根据教材?数据结构-C语言描述?耿国华主编和参考书?数据结构题集C语言版?严蔚敏、吴伟民主编选择课程设计题目,要求通过设计,在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程根本内容的理解和综合运用.设计题目从任务书所列选题表中选取,每班每题不得超过2人.学生自选课题学生原那么上可以结合个人爱好自选课题,要求课题有一定的深度与难度,有一定的算法复杂性,能够稳固数据结构课程所学的知识.学生自选课题需在18周前报课程设计指导教师批准方可生效.要求：1、在处理每个题目时

3、,要求从分析题目的需求入手,按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等假设干步骤完成题目,最终写出完整的分析报告.前期准备工作完备与否直接影响到后序上机调试工作的效率.在程序设计阶段应尽量利用已有的标准函数,加大代码的重用率.2、.设计的题目要求到达一定工作量300行以上代码,并具有一定的深度和难度.3、程序设计语言推荐使用C/C+,程序书写标准,源程序需加必要的注释；4、每位同学需提交可独立运行的程序；5、每位同学需独立提交设计报告书每人一份,要求编排格式统一、标准、内容充实,不少于10页代码不算；6、课程设计实践作为培养学生动手水平的一种手段,单独考核

4、.3 .课程设计说明书一需求分析问题描述排序和查找是在数据处理中使用频度极高的操作,为加快查找的速度需现对数据记录按关键字排序.在汽车数据的信息模型中,汽车牌照是关键字,而且是具有结构特点的一类关键字,因为汽车牌照号是数字和字母混编的,例如01B7328,这种记录集合是一个适于利用多关键字进行排序的典型例子.根本要求(1)首先利用链式基数排序方法实现排序,然后利用折半查找方法,实现对汽车记录按关键字进行查找.(2)汽车记录集合可以人工录入,也可以按自动方式随机生成.本人采用的人工录入.二概要设计1 .有关的数据#defineKEY_SIZE8#defineLIST_SIZE100typedef

5、struct将车牌号以字符的形式存储车主的名字车的品牌charkeyKEY_SIZE;charname10;charcarname20;intnext;RecordType;typedefstruct是一个RecordType类型的数组RecordTyperLIST_SIZE;intlength;intkeynum;SLinkList;2 .为了实现上述功能,需要使用一下函数:main():主函数noun():输出提示信息菜单GetData():从键盘添加车辆函数Distribute.：进行基数排序每一趟的分配函数Collect.：进行基数排序每一趟的收集函数Binsrch():二分查找函数p

6、rint():输出所有车辆信息函数Radixsort():基数排序函数Zl()：基数排序后的整理o上图为各函数之间根本关系下列图为程序执行的流程图.输入i调用子函数GetData()调用子函数print()调用子函数Radixsort()调用子函数Binsrch()c一结果一好三详细设计1、基数排序的过程:首先将待排序的记录分成假设干个子关键字,排序时,先按最低位的关键字对记录进行初步排序；在此根底上,再按次低位关键字进一步排序,以此类推,由低位到高位,由此关键字到主关键字,每一趟排序都在前一趟排序的根底上,直到按最高位关键对记录进行排序后,基数排序完成.在基数排序中,基数是各个关键只的取值范

7、围.假设待排序的记录是十进制,那么基数是10;假设待排序的记录是由假设干个字母组成的单词,那么基数为26,也就是说,从最右边的字母开始对记录进行排序,每次排序都将待排序记录分成26组,但在此问题中,车牌号是由汉字,字母以及数字组成,假设直接进行排序,那么需要分成34组,为了提升算法的空间性能,可以将汉字及字母转换为十进制数后再进行基数排序.例如：一组记录的关键字为：(278,109,63,930,589,184,505,269,8,83)可以看出,这组关键字与以前说过的用来排序的关键字并无差异,且也是针对但关键字对一组记录进行排序.但在基数排序中,我们可以将单关键字看成由假设干个关键字复合而成

8、.上述这组关键字的值都在0999的范围内,我们可以把一个数位上的十进制数字看成是一个关键字,即将关键字K看成由3个关键K0,K,K2组成.其中,K0是百位上的数字,K是十位上白数字,K2是个位上的数字.由于十进制的基数是10,所以,每个苏伟山的数字都可能是09中的任何一个.我们先将关键字/来分配所有参与排序的元素,将Y=0的元素防在一组、K2=1的元素放在一组、Y=9的元素放在一组.这样,将上述一组元素分成10组,如下(a)图所示.然后,再将K2的值由0到9的顺序收集各组元素,形成序列(930,063,083,184,505,278,008,109,589,269).对上述序列中的元素再按关键

9、字K1来分配,也分成10组,如下(b)图所示.然后,再按K1的值由0到9的顺序收集各组元素,形成序列(505,008,109,930,063,269,278,083,184,589).对该序列中的元素再按关键字K0来分配,分成如下(c)图所示的10组.然后按K0的值由09的顺序收集各组元素,形成序列(008,063,083,109,184,267,278,505,589,930).这时,该序列已经变成了一个有序序列.一趟分配前的一组元素(008,063,083,109,184,267,278,505,589,930)269083008589930063184505278109k2=0k2=1k

10、2=2k2=3k2=4k2=5k2=6k2=7k2=8k2=9(a)、按个位数大小将元素分成10组一趟分配后的一组元素(930,063,083,184,505,278,008,109,589,269)109589008269184505930063278083k=0k1=1k1=2k1=3k1=4k1=5k1=6k1=7k1=8k1=9(b)、按十位数大小将元素分成10组二趟收集后的元素序列(505,008,109,930,063,269,278,083,184,589)063184278589008109269505K0=0k0=1k0=2k0=3k0830=4930k0=5k0=6k0=7

11、k0=8k0=9(c)、按百位数大小将元素分成10组三趟收集后的元素序列(008,063,084,109,184,269,278,505,589,930)2、二分查找的算法思想：(1)、将表中间位置记录的关键字与给定K值比拟,如果两者相等,那么查找成功.(2)、如果两者不等,利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于给定值,那么进一步查找前一子表,否那么进一步查找后后一子表.(3)、重复以上过程,直到找到满足条件的记录,那么查找成功,或者直到分解出的子表不存在为止,此时查找不成功.例如对一有序的数组a(1,2,3,4,5,6,7,8,9)进行查找数key=6;首先定义

12、low=0,high=8,mid=(low+high)/2=4;第一步：将amid与key比拟,我们发现amid<key,令low=mid+1=5;mid=(low+high)/2=6第二步：将amid与key比拟,我们发现amid>key,此时再令high=mid-1=5;mid=(low+high)/2=5第三步：将amid与key比拟,此时amid=key,查找结束,返回mid;第四步：如果仍未找到,那么继续进行,直到low>high,此时返回-1,查找失败；3、主要函数及功能1 .voidRadixsort(SLinkList*l)/基数排序/Length个记录存放在

13、数组r中,执行本算法进行基数排序后,链表中的记录将按关键字从小到大的顺序链接.intn=l->length;zimuhead,tail;shuziheads,tails;for(inti=0;i<=n-1;i+)l->ri.next=i+1;l->rn.next=0;for(i=6;i>2;i-)/下标大的为低位,从低位开始调用分配函数/调用收集函数调用分配函数调用收集函数Distribute_s(l->r,i,heads,tails);/Collect_s(l->r,heads,tails);Distribute_z(l->r,2,head,t

14、ail);/Collect_z(l->r,head,tail);/for(i=1;i>=0;i-)Distribute_s(l->r,i,heads,tails);Collects(l->r,heads,tails);2 .VoidDistribute_s(RecordTyper,inti,shuzihead,shuzitail)/记录数组r中已按低位关键字keyi+1,keyd进行低位优先排序,本算法按第i个关键字keyi建立10个队列,同一个队列中记录的keyi相同.Headj和tailj分别指向各自队列中第一个和最后一个记录(j=0,1,2,-9).headj=0

15、表示相应队列为空队列./*_s表示对数字进行的操作.在程序中还有_z表示对字母的操作*intj,p;for(j=0;j<=队列的个数;j+)初始化队列队列的头指针=0;全部为0对歹的尾指针=0;全部为0)p=第一个数据在数组中的位置while(第一个数据在数组中的位置！=0)上=第一个数据的第i位在第几个队列if(头指针二=0)头指针二第一个数据载表中的位置；else该队列已有数据的下一个位置=p否那么将该数在静态链表中的位置放在在同一个队列的数据之后尾指针=p;tialj=该数在静态链表中的位置p=下一个数据的位置值;)voidDistribute_z(RecordTyper,inti

16、,zimuhead,zimutail)intp,j;for(j=0;j<=25;j+)(headj=0;tailj=0;)p=r0.next;while(p!=0)(j=int(int(rp.keyi)-'A');if(headj=0)headj=p;elsertailj.next=p;tailj=p;p=rp.next;)3 .Voidcollect_s(RecordTyper,shuzihead,shuzitail)/本算法从.IU9扫描个队列将所有非空队列首尾相接,重新链接成一个链表(intj=0,t;while(headj=0)+j;/找第一个不为空的队列r0.n

17、ext=headj;t=tailj;/把headj给第一个数据的位置while(j<9)(+j;while(j<9)&&(headj=0)找到不为0的队列+j;if(headj!=0)(rt.next=headj;)rt.next=0;/使最后一个数的next=0)voidCollect_z(RecordTyper,zimuhead,zimutail)字母类型收集重新构成链表(intj=0,t;while(headj=0)+j;r0.next=headj;t=tailj;while(j<25)(+j;while(j<25)&&(headj

18、=0)+j;if(headj!=0)(rt.next=headj;t=tailj;)rt.next=0;)4 .voidzl(SLinkList*l)整理链表顺序(intp,q;RecordTypebuf;p=第一个元素在表中的位置；for(inti=1;i<表的长度;i+)while(p<i)p=第p个元素的下一个数在表中的位置；4=第p个元素的下一个数在表中的位置；if(p!=i)(皿£=第p个元素的地址；第p个元素的地址=第i个元素的地址；交换第i个元素的地址与第p个元素的地址第i个元素的地址=buf;第i个元素的下一个数在表中的位置=p;)p=q；)1. intB

19、insrch_bin(SLListl,chars)/二分查找,s为要找的内容(定义整形三个位置变量mid,high,low,并能后两个赋初值；(mid表示中间,high表示高位,low表示低位)While(low<=high)(用mid=(high+low)/2求得mid的值；如果L->rmid.key=s(要查找的内容)；那么返回它在表中的位置mid如果L->rmid.key<s;那么将最低位变为mid+1;如果L->rmid.key>s;那么将最高位变为mid1)执行到些证实在表中没找到要查找的内容,返回0；)6. voidGetData(SLinkLi

20、st*L)/从键盘获得数据,存在表L中.(定义输入的状态变量x;x不为0既认为要输入定义记录个数的整型变量j;输出输入的提示信息；scanf("%d",&x);输入x的状态；while(x)x=0;printf("t车牌号：");输出提示scanf("%s",&(L->rj.key);输入节点中对应的量printf("t车主名：");scanf("%s",&(L->);printf("t车名：");scanf("%s

21、",&(L->rj.carname);printf("*按任意不为0'的数字继续录入*:");scanf("%d",&x);if(x)j+;L->length=j;将个数赋给表的长度7. voidprint(SLinkList*L)遍历静态表(inti;printf("t");printf("车牌号车主名车名n");for(i=1;i<=链表的长度;i+)(输出各局部对应的值；)8. intEqual(charkey1口,charkey2)/折半查找辅助比拟,判断

22、是否想等,只比拟前7位,第八位是结束符(for(inti=0;i<7;i+)(if(key1i!=key2i)任意一个不相等就不相等,返回0return0;)return1;执行到这说明都相等,返回不为0的值)9. intxiao(charkey1口,charkey2口)/折半查找辅助比拟,判断较小(for(inti=0;i<7;i+)(if(key1i<key2i)return1;elseif(key1i>key2i)return0;)return0;四设计与调试分析1 .调试输出菜单：这局部执行成功,为了能够输出对称、格式整洁,所以要不断的调试、修改直到满意.2 .

23、调试功能1添加车辆信息：从键盘输入以下几组数据；车牌号车主名车名按提示输入,以0结束轮作输入输入成功,退出输入功能也成功,但是要注意在输入时,每个量中间不能输入空格.这样会使程序默认下个量输入结束.3 .实现功能2输出所有车辆信息：输出的车辆信息与输入和一致.此部部执行成功.4 .实现功能3按车牌号进行排序从小到大根据2.进行输入：在这里也套用了功能2,从结果可以看出排序成功.5 .实现功能4按车牌号查找车辆：在上面的根底上分别查找01A1234和02A1234由此可能看出两局部都执行成功6 .实现功能5退出程序退出程序成功.五用户手册1、运行程序,根据菜单项选择择要实现的功能,输入相应的数字

24、.1:输入数据；2:输出所有元素3:实现链式基数排序；4:用二分查找在表中按车牌号查找；0:退出程序2、中选择功能1后,根据提示输入相应的信息,在输入时,每个字符串之间不要有空格.按0退出输入.在输入时输入2位数字,一个大写字母,然后再输入四位数字3、中选择功能2后,会按格式输出所有节点信息.4、中选择功能3后.会输出进行链式排序后的所有节点信息.5、领先择功能4后,请输入您要查找车辆的车牌号.程序会输入相应信息.6、在没有执行第4步前,不能执行第五步.7、退出程序请按0,然后安任意键会关闭运行窗口.六测试成果七附录源程序清单#include<stdio.h>#defineKEY_

25、SIZE8#defineLIST_SIZE100typedefstruct(charkeyKEY_SIZE;charname10;charcarname20;intnext;RecordType;typedefstruct(RecordTyperLIST_SIZE;intlength;intkeynum;SLinkList;typedefintshuzi10;typedefintzimu26;voidInitSLList(SLinkList*L)(L->length=0;L->keynum=7;voidDistribute_s(RecordTyper,inti,shuzihead,

26、shuzitail)/数字分酉己(intj,p;for(j=0;j<=9;j+)(p=r0.next;while(p!=0)(j=int(rp.keyi-'0');if(headj=0)headj=p;elsertailj.next=p;tailj=p;p=rp.next;)voidDistribute_z(RecordTyper,inti,zimuhead,zimutail)(intp,j;for(j=0;j<=25;j+)(headj=0;tailj=0;)p=r0.next;while(p!=0)(j=int(int(rp.keyi)-'A')

27、;if(headj=0)headj=p;elsertailj.next=p;tailj=p;p=rp.next;voidCollect_s(RecordTyper,shuzihead,shuzitail)收集重新构成链表intj=0,t;while(headj=0)+j;r0.next=headj;t=tailj;while(j<9)+j;while(j<9)&&(headj=0)+j;if(headj!=0)rt.next=headj;t=tailj;rt.next=0;voidCollect_z(RecordTyper,zimuhead,zimutail)字母类

28、型收集重新构成链表intj=0,t;while(headj=0)+j;r0.next=headj;t=tailj;while(j<25)+j;while(j<25)&&(headj=0)+j;if(headj!=0)rt.next=headj;t=tailj;rt.next=0;voidRadixsort(SLinkList*l)基数排序intn=l->length;zimuhead,tail;shuziheads,tails;for(inti=0;i<=n-1;i+)l->ri.next=i+1;l->rn.next=0;for(i=6;i

29、>2;i-)/下标大的为低位,从低位开始Distribute_s(l->r,i,heads,tails);/调用分配函数Collect_s(l->r,heads,tails);/调用收集函数Distribute_z(l->r,2,head,tail);调用分配函数Collect_z(l->r,head,tail);调用收集函数Distribute_s(l->r,i,heads,tails);Collect_s(l->r,heads,tails);)voidzl(SLinkList*l)(intp,q;RecordTypebuf;p=l->r0.n

30、ext;for(inti=1;i<l->length;i+)(while(p<i)p=l->rp.next;q=l->rp.next;if(p!=i)(buf=l->rp;l->rp=l->ri;l->ri=buf;l->ri.next=p;)p=q;)/进行排序后整理顺序/p指向第一个记录的当前位置/找到第i个记录,并用p指示其在表中的当前位置/交换p与i/使得被移走的记录使得以后可以由while循环找回voidGetData(SLinkList*L)/从键盘获得数据intx;intj=1;printf("请输入车牌号及车

31、主名与车名n");printf("例如：01B1234");printf("n");printf("如要录入请按任意不为0'的数字,退出此功能请按0':");scanf("%d",&x);printf("n");while(x)x=0;printf("t车牌号：");scanf("%s",&(L->rj.key);printf("t车主名：");scanf("%s",&

32、amp;(L->);printf("t车名：")；scanf("%s",&(L->rj.carname);printf("*按任意不为0'的数字继续录入*:");scanf("%d",&x);if(x)j+;L->length=j;voidprint(SLinkList*L)输出出所有元素inti;printf("t");printf("车牌号车主名车名)printf("n");for(i=1;i<=L-

33、>length;i+)printf("t%s",L->ri.key);printf("%s",(L->);printf("%sn",L->ri.carname);intEqual(charkey1口,charkey2)/折半查找辅助比拟,判断是否想等,只比拟前7位,第八位是结束符for(inti=0;i<7;i+)if(key1i!=key2i)return0;return1;intxiao(charkey1口,charkey2)/折半查找辅助比拟,mid位的数据小于查找的数for(inti

34、=0;i<7;i+)if(key1i<key2i)return1;elseif(key1i>key2i)return0;return0;intBinsrch(SLinkList*L,chars8)按车牌号,(.key)折半查找intmid,high,low;low=1;high=L->length;while(low<=high)(mid=(high+low)/2;if(Equal(s,L->rmid.key)return(mid);elseif(xiao(s,L->rmid.key)high=mid-1;elselow=mid+1;return(0)

35、;voidnoun()/输出提示操作(printf("ttn");printf("tt|车牌信息治理系统In");printf("tt|n");printf("tt|1)添加车辆信息In");printf("tt|n");printf("tt|2)输出所有车辆信息|n");printf("tt|n");printf("tt|3)按车牌号进行排序|n");printf("tt|n");printf("tt|4

36、)按车牌号查找车辆|n");printf("tt|n");printf("tt|0)退出程序|n");printf("ttn");voidmain()(inti;SLinkListl;noun();提示doprintf("*n");printf"*请选择相应功能对应的数字*:"scanf("%d",&i);switch(i)(case 1:InitSLList(&l);GetData(&l);break;case 2:print(&l);break;case 3:Radixsort(&l);zl(&l);printf("*排序后的顺序为：*、);printf("n");print(&l);break;case 4:intf;chars7;I*printf("*请输入要查找的车牌号*");scanf("%s",&s);f=Binsrch(&l,s);if(f)(printf("t查找的车在表中的位置为：%dn",Binsrch(&l,s);printf(&q