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

1、淮海 工学院 计算机工程学院课程设计报告设计名称：数据结构课程设计选题名称：汽车牌照管理系统姓 名：学 号：专业班级：计算机科学与应用G计111系（院）： 计算机工程学院设计时间： 2012.12.242013.1.4设计地点：软件工程实验室、教室成绩:指导教师评语:签名：1 .课程设计目的a 一* X!一1!*B-Fl|一空一土！一|1 、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解 指定问题。2 .初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3 .提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4 .训练用系

2、统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平, 并在此过程中培养他们严谨的科学态度和良好的工作作风。2 .课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、 算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课

3、题需在18周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现 抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作 完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的 重用率。2、 .设计的题目要求达到一定工作量（ 300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用 C/C+,程序书写规范，源程序需加必要的注释；4、每位同学需提交可独立运行的程序；5、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范

4、内容充实，不少于 10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。3 .课程设计说明书r k n btb ar wm h wh av em nra gm n ra 一 ar h av 1一需求分析问题描述排序和查找是在数据处理中使用频度极高的操作，为加快查找的速度需现对数据记录按关键字 排序。在汽车数据的信息模型中，汽车牌照是关键字，而且是具有结构特点的一类关键字，因 为汽车牌照号是数字和字母混编的，例如 01B7328,这种记录集合是一个适于利用多关键字进行 排序的典型例子。基本要求(1)首先利用链式基数排序方法实现排序，然后利用折半查找方法，实现对汽车记录按

5、关键字 进行查找。(2)汽车记录集合可以人工录入，也可以按自动方式随机生成。本人采用的人工录入。二概要设计1 .有关的数据#define KEY_SIZE 8#define LIST_SIZE 100 typedef struct将车牌号以字符的形式存储 车主的名字车的品牌char keyKEY_SIZE;char name10;char carname20; int next;是一个RecordType类型的数组RecordType; typedef struct RecordType rLIST_SIZE;int length;int keynum;SLinkList;2 .为了实现上述功

6、能，需要使用一下函数: main():主函数noun():输出提示信息菜单GetData():从键盘添加车辆函数Distribute。：进行基数排序每一趟的分配函数Collect。：进行基数排序每一趟的收集函数Binsrch ():二分查找函数print():输出所有车辆信息函数Radixsort ():基数排序函数Zl ():基数排序后的整理noun ()上图为各函数之间基本关系 下图为程序执行的流程图。UN调用子函数 Binsrch ()首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此 基础上，再按次低位关键字进一步排序，以此类推，由低位到高位，由此

7、关键字到主关键字，每一趟排序 都在前一趟排序的基础上，直到按最高位关键对记录进行排序后，基数排序完成。在基数排序中，基数是各个关键只的取值范围。若待排序的记录是十进制，则基数是10;若待排序的记录是由若干个字母组成的单词，则基数为26,也就是说，从最右边的字母开始对记录进行排序，每次排序都将待排序记录分成 26组，但在此问题中，车牌号是由汉字，字母以及数字组成，若直接进行排序，则 需要分成34组，为了提高算法的空间性能，可以将汉字及字母转换为十进制数后再进行基数排序。例如：一组记录的关键字为：(278, 109, 63, 930, 589, 184, 505, 269, 8, 83)可以看出，

8、这组关键字与以前说过的用来排序的关键字并无差别，且也是针对但关键字对一组记录进行排 序。但在基数排序中，我们可以将单关键字看成由若干个关键字复合而成。上述这组关键字的值都在0999的范围内，我们可以把一个数位上的十进制数字看成是一个关键字，即将关键字K看成由3个关键K5, k, K2组成。其中，Y是百位上的数字，K1是十位上的数字，K2是个位上的数 字。因为十进制的基数是 10,所以，每个苏伟山的数字都可能是09中的任何一个。我们先将关键字K2来分配所有参与排序的元素，将Y=0的元素防在一组、K2=1的元素放在一组、Y=9的元素放在一组。这样，将上述一组元素分成10组，如下(a)图所示。然后，

9、再将K2的值由0到9的顺序收集各组元素，形成序列(930, 063, 083, 184, 505, 278, 008, 109, 589, 269)。对上述序列中的元素再按关键字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)。

10、这时，该序列已经变 成了一个有序序列。一趟分配前的一组元素(008, 063, 083, 109, 184, 267, 278, 505, 589, 930) 269083008589930063 184505278109k2=0k2=1k2=2k2=3k2=4k2=5k2=6k2=7k2=8k2=9(a)、按个位数大小将元素分成10组一趟分配后的一组元素(930, 063, 083, 184, 505, 278, 008, 109, 589, 269)109589008269184505930063 278083k=0 k 1=1 k 1=2 k 1=3 k 1=4k 1=5 k 1=6 k

11、 1=7 k 1=8 k 1=9(b)、按十位数大小将元素分成10组二趟收集后的元素序列(505, 008, 109, 930, 063, 269, 278, 083, 184, 589)083063 184278589008 109269505930K0=0 k 0=1k 0=2 k0=3 k 0=4k 0=5 k 0=6 k 0=7 k 0=8k0=9(c)、按百位数大小将元素分成10组三趟收集后的元素序列(008, 063, 084, 109, 184, 269, 278, 505, 589, 930)2、二分查找的算法思想：(1)、将表中间位置记录的关键字与给定K值比较，如果两者相等，

12、则查找成功。(2)、如果两者不等，利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于给定K值，则进一步查找前一子表，否则进一步查找后后一子表。(3)、重复以上过程，直到找到满足条件的记录，则查找成功，或者直到分解出的子表不存在为止，此时查找不成功。例如对一有序的数组 a (1, 2 , 3, 4, 5, 6, 7, 8, 9)进行查找数key=6;首先定义 low=0, high=8 , mid= (low+high ) /2=4 ;第一步：将 amid与 key 比较，我们发现 a midkey ,此时再令 high=mid-1=5 ; mid= (low+high ) /

13、2=5 ;第三步：将 amid与key比较，此时amid=key ,查找结束，返回 mid;第四步：如果仍未找到，则继续进行，直到 lowhigh ,此时返回-1 ,查找失败；3、主要函数及功能1 . void Radixsort(SLinkList *l)/基数排序/Length个记录存放在数组r中，执行本算法进行基数排序后，链表中的记录将按关键字 从小到大的顺序链接。int n=l-length;zimu head,tail;shuzi heads,tails;for(int i=0;iri.next=i+1;l-rn.next=0;for(i=6;i2;i-)/下标大的为低位，从低位开始

14、调用分配函数/调用收集函数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); /调用收集函数for(i=1;i=0;i-) Distribute_s(l-r,i,heads,tails); Collect s(l-r,heads,tails); 2 .Void Distribute_s（RecordType r,int i,shuzi head,shuzi tail）/记录 数组r中已按低位关键字

15、keyi+1, ,keyd进行低位优先排序，本算法 按第i 个关键字keyi建立10个队列，同一个队列中记录的keyi相同。Headj和tailj 分别指向各自队列中第一个和最后一个记录（j=0,1,2,与）.headj=0表示相应队列为空队列。/*_s表示对数字进行的操作。在程序中还有 _z表示对字母的操作* int j,p;for（j=0;j=队列的个数;j+） 初始化队列 队列的头指针=0;全部为0对歹1的尾指针=0；全部为0）p=第一个数据在数组中的位置while（第一个数据在数组中的位置！=0） 上=第一个数据的第i位在第几个队列if（头指针二=0）头指针二第一个数据载表中的位置；e

16、lse该队列已有数据的下一个位置=p否则将该数在静态链表中的位置放在在同一个 队列的数据之后尾指针=p;tialj=该数在静态链表中的位置p=下一个数据的位置值;）void Distribute_z（RecordType r,int i,zimu head,zimu tail） int p,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;else rtailj.next=p;tailj=p；p=rp.next;/3 .Void collect_s(Re

17、cordType r口,shuzi head,shuzi tail)/本算法从0 .1U 9扫描个队列将所有非空队列首尾相接，重新链接成一个链表 int j=0,t;while(headj=0)+j;/找第一个不为空的队列r0.next=headj;t=tailj;/把 headj给第一个数据的位置while(j9)+j;while(j9)&(headj=0)找到不为 0 的队列+j;if(headj!=0)rt.next=headj;t=tailj；rt.next=0;/使最后一个数的 next=0void Collect_z(RecordType r口,zimu head,zimu tai

18、l)字母类型收集重新构成链表int j=0,t;while(headj=0)+j；r0.next=headj;t=tailj;while(j25)+j;while(j25)&(headj=0)+j;if(headj!=0)rt.next=headj;t=tailj;rt.next=0;4 . void zl(SLinkList *l)整理链表顺序int p,q;RecordType buf;p=第一个元素在表中的位置；for(int i=1;i 表的长度;i+)while(pi)p=第p个元素的下一个数在表中的位置；4=第p个元素的下一个数在表中的位置；if(p!=i)buf=第p个元素的地址

19、第p个元素的地址=第i个元素的地址；交换第i个元素的地址与第p个元素的地址第i个元素的地址=buf;第i个元素的下一个数在表中的位置=p;p=q;1. int Binsrch_bin(SLList l,char s) /二分查找,s 为要找的内容定义整形三个位置变量 mid ,high,low,并能后两个赋初值；(mid表示中间，high表示 高位，low表示低位)While(lowrmid.key=s(要查找的内容)；则返回它在表中的位置 mid如果L-rmid.keyrmid.keys;则将最高位变为mid 1执行到些证明在表中没找到要查找的内容，返回 0；6. void GetData

20、SLinkList *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-rj.name);printf(t 车名：)； scanf(%s”,&(L-rj.carname);printf(*按任意不为0的数字继续录入*:);scanf(%d,&x);if(x) j+； L-length=j;将

21、个数赋给表的长度7. void print(SLinkList *L)遍历静态表(int i; printf(t);printf( 车牌号 车主名 车名n);for(i=1;i=链表的长度;i+)(输出各部分对应的值；)8. int Equal(char key1,char key2)/折半查找辅助比较，判断是否想等，只比较前7位，第八位是结束符(for(int i=0;i7;i+)( if(key1i!=key2i)任意一个不相等就不相等，返回0return 0;)return 1;执行到这说明都相等，返回不为 0的值)9. int xiao(char key1口,char key2)/折半

22、查找辅助比较，判断较小(for(int i=0;i7;i+) (if(key1ikey2i) return 0; ) return 0;西一设讦一写调试分析1 .调试输出菜单：车牌信息管理系统退出程序添加车辆信息输出所有车辆信息HC 与看告Ad mi nistrdtor D tskto pDftbu g、车牌按车牌号码进行排序五国国这部分执行成功，为了能够输出对称、格式整齐，所以要不断的调试、修改直到满意。2 .调试功能1）添加车辆信息：从键盘输入以下几组数据；车牌号 车主名 车名（按提示输入，以0结束轮作输入）输入成功，退出输入功能也成功，但是要注意在输入时，每个量中间不能输入空格。这样会使

23、 程序默认下个量输入结束。3 .实现功能2）输出所有车辆信息：输出的车辆信息与输入和一致。此部部执行成功。4 .实现功能3）按车牌号进行排序（从小到大）按照2.进行输入：在这里也套用了功能2）,从结果可以看出排序成功。5 .实现功能4）按车牌号码查找车辆：在上面的基础上分别查找 01A1234和02A1234-i-r f .目在：密六 车码： 的号一应祠青选择相应功能对应的数字*： 4 建耦献卢*请选择相应功首自对应的数字*： W由此可能看出两部分都执行成功6 .实现功能5）退出程序退出程序成功。五用户手册1、运行程序，根据菜单选择要实现的功能，输入相应的数字。 （1:输入数据；2:输出所有元

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

25、 100typedef structchar keyKEY_SIZE;char name10;char carname20;int next;RecordType;typedef structRecordType rLIST_SIZE;int length;int keynum;SLinkList;typedef int shuzi10;typedef int zimu26;void InitSLList(SLinkList *L)L-length=0;L-keynum=7;void Distribute_s(RecordType r,int i,shuzi head,shuzi tail)

26、/数字分酉己 int j,p;for(j=0;j=9;j+)headj=0;tailj=0；p=r0.next;while(p!=0)j=int(rp.keyi-0);if(headj=0)headj=p;elsertai皿next=p;tailj=p； p=rp.next;void Distribute_z(RecordType r,int i,zimu head,zimu tail)int p,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;els

27、e rtai皿next=p;tailj=p；p=rp.next;void Collect_s(RecordType r,shuzi head,shuzi tail)收集重新构成链表int j=0,t;while(headj=0)+j；r0.next=headj;t=tailj;while(j9)+j；while(j9)&(headj=0)+j；if(headj!=0)rt.next=headj;t=tailj；rt.next=0;void Collect_z(RecordType r口,zimu head,zimu tail)字母类型收集重新构成链表int j=0,t;while(headj=

28、0)+j;r0.next=headj;t=tailj;while(j25)+j；while(jlength;zimu head,tail;shuzi heads,tails;for(int i=0;iri.next=i+1;l-rn.next=0;for(i=6;i2;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);调用收集函数for(i=

29、1;i=0;i-)Distribute_s(l-r,i,heads,tails);Collect_s(l-r,heads,tails);void zl(SLinkList *l)int P,q；RecordType buf;p=l-r0.next;for(int i=1;ilength;i+)while(prp.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

30、循环找回void GetData(SLinkList *L)/从键盘获得数据int x;int j=1;printf(请输入车牌号码及车主名与车名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”,&(L-rj.name);printf(t 车 名：)；scanf(%s”,&(L-rj.carname);printf(*按任意

31、不为0的数字继续录入*:);scanf(%d,&x);if(x)j+；L-length=j;void print(SLinkList *L)输出出所有元素int i;printf(t);printf(车牌号车主名 车名)printf(n);for(i=1;ilength;i+)printf(t%s,L-ri.key);printf(%s , (L-ri.name);printf(%sn,L-ri.carname);7位,int Equal(char keyl口,char key2口)/折半查找辅助比较，判断是否想等，只比较前第八位是结束符for(int i=0;i7;i+)if(key1i!=

32、key2i)return 0;return 1;int xiao(char key1口,char key2口)/折半查找辅助比较，mid位的数据小于查找的数for(int i=0;i7;i+)if(key1ikey2i) return 0;return 0;int Binsrch(SLinkList *L,char s8)按车牌号，(.key)折半查找int mid,high,low;low=1;high=L-length;while(lowrmid.key)return(mid);else if(xiao(s,L-rmid.key)high=mid-1;elselow=mid+1;retur

33、n(0);void noun()/输出提示操作printf(tt n);printf(tt |车牌信息管理系统I n);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)按车牌号码查找车辆|n);printf(tt|n);printf(tt|0)退出程序|n);printf(tt n);void main()int i;SLinkList l;noun(); 提示doprint

34、f(*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:int f;char s7;I* printf(*请输入要查找的车牌号码*);scanf(%s,&s);f=Binsrch(&l,s);if(f)printf(t查找的车在表中的位置为：%dn,Binsrc

35、h(&l,s);printf(t 车牌号码：);printf(%s,l.rf.key);printf(n);printf(t 车主名：);printf(%sn,l.rf.name);printf(t 车 名：)；printf(%sn,l.rf.carname);elseprintf(此车牌号不在列表中);printf(n);break;case 0:break;while(i!=0);4.课程设计心得1、对于我选的这个课题主要就是进行链式基数排序和二分查找（折半查找），链式基数排序是一种多关键字排序，在多关键排序中它又属于“低位优先”排序法，对于车牌号来说不全是数字，而且较长，显然用整型存储没

36、有用字符型存储来的方便，所在在这里我采用字符 数组的形式来存储关键字，这样对于排序和查找都更为简便。2、对于车牌号这里采用7位进行表示，前两位为数字，第三位为一个大字的英文字母，后面 的三位为数字，如同上面所说的它们都按照字符的形式存储，所以输入的时侯要小心不要 输错。3、虽然车牌号只有7位，但是我对于关键字字符数组定义了 8位，因为在添加车辆信息时， 我是按照字符串的形式输入的（“），所有要留出一位结束符的位，以避免不必要的错误4、我之所以采用字符串的形式进行输入是因为在对车牌号使用循环语名进行输入时（例如 for（int i =0;i7;i+）,按照常理来说这样就可以控制办入一个完整的车牌

37、号，但是在 测试的时候我去发现这样它只能正常接收前 6位，所以后面的数据所受其影响。因此我选 用了成用的输入。5、在输入时，因为不论是车牌号还是车主名、车名，都是采用字符串进行输入的，虽然空格 也是字符串，但是在C语言中，有些时候当进行整用输入时，特别是没有加一些有效的控 制语句时，如果输入空格，系统则认为些用输入结束，并且下一个申也会受其影响（有可 能被跳过，不接收数据）。所以使用VC时输入字符串尽量不要使用到空格，对于整型的来 说它到是没有太大的影响。6、静态链表是借助数组来描述的。7、虽然对车牌号进行了链式基数排序但当遍历链表时，你会发现它还是排序前的顺序，经过 多种方式的查找资料后，这里我采用了 zl（）这个函数进行顺序的整理。8、对于这次的课程设计有很多控制格式的输出，特别是空格，看不见也不好数，但是要使程 序在使用时可读性更高又必须使用，要想一次就将输出格式控制好那几乎是不可能事件， 所以要反复的修改、调试，直到满意为止。这也许是一个乏味而复杂的过程，但当你得到 想要的效果的那一瞬间，那种喜悦是无法形容的，那种成就感会在下一次遇到困难时给我 们面对、克服它的勇气。9、经过这次课程设计后我又发现了很多新的问题，它们一些已经得到解决，而一些还在努力 中。所以在以后的日子要继续努力、更加努力才能有所进步，才能更加完善自己。