蔡霖《汽车牌照管理系统》

1、学号2015-2016学年 第一学期1308210102数据结构课程设计报告题目：车牌管理系统专业：计算机科学与技术班级：13计科2班姓名：蔡霖指导教师：邓明成绩：计算机学院2015年11月16日目录1.设计内容及要求11.1 概述11.2 主要功能11.3 目的和要求12.概要设计12.1数据设计12.2 所需函数及框架23.设计过程或程序代码43.1基数排序的过程43.2 二分查找的算法思想63.3主要函数及功能64.设计结果与分析124.1调试过程124.2用户手册135.参考文献14附：源程序15计算机学院数据结构课程设计报告1.设计内容及要求1.1 概述排序和查找是在数据处理中使用频

2、度极高的操作，为加快查找的速度需现对数据记录按关键字排序。在汽车数据的信息模型中，汽车牌照是关键字，而且是具有结构特点的一类关键字，因为汽车牌照号是数字和字母混编的，例如01B7328，这种记录集合是一个适于利用多关键字进行排序的典型例子。 1.2 主要功能（1）首先利用链式基数排序方法实现排序，然后利用折半查找方法，实现对汽车记录按关键字进行查找。 （2）汽车记录集合可以人工录入，也可以按自动方式随机生成。本人采用的人工录入。1.3 目的和要求1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终

3、写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;2.概要设计2.1数据设计#define KEY_SIZE 8#define LIST_SIZE 100typedef structchar keyKEY_SIZE; 将车牌号以字符的形式存储char name10; 车主的名字char carname20; 车的品牌int next;RecordType;type

4、def struct RecordType rLIST_SIZE; 是一个RecordType类型的数组 int length;int keynum;SLinkList;2.2 所需函数及框架main()：主函数noun()：输出提示信息菜单GetData()：从键盘添加车辆函数Distribute()：进行基数排序每一趟的分配函数Collect()：进行基数排序每一趟的收集函数Binsrch ()：二分查找函数print()：输出所有车辆信息函数Radixsort ()：基数排序函数Zl（）：基数排序后的整理 main()Distribute()noun ()print()Collect()

5、GetData()Radixdort()zl()Binsrch()图1各函数之间基本关系n=1i=2i=3调用子函数GetData ()调用子函数Binsrch ()调用子函数Radixsort ()调用子函数print()i=4YNNYYNN开始输入iNNYi=0NNY结果NN图2程序执行的流程图3.设计过程或程序代码 3.1基数排序的过程首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次低位关键字进一步排序，以此类推，由低位到高位，由此关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键对记录进行排序后，基数排序完成。在基

6、数排序中，基数是各个关键只的取值范围。若待排序的记录是十进制，则基数是10；若待排序的记录是由若干个字母组成的单词，则基数为26，也就是说，从最右边的字母开始对记录进行排序，每次排序都将待排序记录分成26组，但在此问题中，车牌号是由汉字，字母以及数字组成，若直接进行排序，则需要分成34组，为了提高算法的空间性能，可以将汉字及字母转换为十进制数后再进行基数排序。例如：一组记录的关键字为：（278，109，63，930，589，184，505，269，8，83）可以看出，这组关键字与以前说过的用来排序的关键字并无差别，且也是针对但关键字对一组记录进行排序。但在基数排序中，我们可以将单关键字看成由若

7、干个关键字复合而成。上述这组关键字的值都在0999的范围内，我们可以把一个数位上的十进制数字看成是一个关键字，即将关键字K看成由3个关键K0，K1，K2组成。其中，K0是百位上的数字，K1是十位上的数字，K2是个位上的数字。因为十进制的基数是10，所以，每个苏伟山的数字都可能是09中的任何一个。我们先将关键字K2来分配所有参与排序的元素，将K2=0的元素防在一组、K2=1的元素放在一组、 、K2=9的元素放在一组。这样，将上述一组元素分成10组，如下（a）图所示。然后，再将K2的值由0到9的顺序收集各组元素，形成序列（930，063，083，184，505，278，008，109，589，26

8、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） 269 083 008 589930 063

9、 184 505 278 109k2=0 k2=1 k2=2 k2=3 k2=4 k2=5 k2=6 k2=7 k2=8 k2=9（a）、按个位数大小将元素分成10组一趟分配后的一组元素（930，063，083，184，505，278，008，109，589，269）109 589 008 269 184 505 930 063 278 083K1=0 k1=1 k1=2 k1=3 k1=4 k1=5 k1=6 k1=7 k1=8 k1=9 （b）、按十位数大小将元素分成10组二趟收集后的元素序列（505，008，109，930，063，269，278，083，184，589）083 063

10、184 278 589 008 109 269 505 930K0=0 k0=1 k0=2 k0=3 k0=4 k0=5 k0=6 k0=7 k0=8 k0=9（c）、按百位数大小将元素分成10组三趟收集后的元素序列（008，063，084，109，184，269，278，505，589，930）3.2 二分查找的算法思想（1）、将表中间位置记录的关键字与给定K值比较，如果两者相等，则查找成功。（2）、如果两者不等，利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于给定K值，则进一步查找前一子表，否则进一步查找后后一子表。（3）、重复以上过程，直到找到满足条件的记录，则查找成

11、功，或者直到分解出的子表不存在为止，此时查找不成功。例如对一有序的数组a（1，2 ，3，4，5，6，7，8，9）进行查找数key=6；首先定义low=0，high=8，mid=（low+high）/2=4；第一步：将amid与key比较，我们发现a mid<key，令low=mid+1=5；mid=（low+high）/2=6第二步：将amid与key比较，我们发现a mid>key，此时再令high=mid-1=5；mid=（low+high）/2=5；第三步：将amid与key比较，此时amid=key，查找结束，返回mid;第四步：如果仍未找到，则继续进行，直到low>

12、high，此时返回-1，查找失败；3.3主要函数及功能（1）void Radixsort(SLinkList *l) /基数排序/Length 个记录存放在数组r中，执行本算法进行基数排序后，链表中的记录将按关键字从小到大的顺序链接。/ int n=l->length;zimu head,tail;shuzi heads,tails;for(int i=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)

13、; /调用分配函数 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中已按低位关键字keyi+1

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

15、有数据的下一个位置=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 col

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

17、Type r,zimu head,zimu tail) /字母类型收集重新构成链表 int j=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;（4）.void zl(SLinkList *l) /整理链表顺序 int p,q;RecordType buf; p=第一个元素在表中的位置; for(int i=1;i<表的长度;i+) while(p<

18、i)p=第p个元素的下一个数在表中的位置; q=第p个元素的下一个数在表中的位置;if(p!=i) buf=第p个元素的地址;第p个元素的地址=第i个元素的地址; 交换第i个元素的地址与第p个元素的地址第i个元素的地址=buf;第i个元素的下一个数在表中的位置=p;p=q;（5）int Binsrch_bin(SLList l,char s) /二分查找,s为要找的内容 定义整形三个位置变量 mid ,high,low,并能后两个赋初值；(mid表示中间，high表示高位，low表示低位) While(low<=high) 用mid=(high+low)/2求得mid的值； 如果L-&g

19、t;rmid.keys(要查找的内容)；则返回它在表中的位置mid 如果L->rmid.key<s;则将最低位变为mid+1; 如果L->rmid.key>s;则将最高位变为mid1 执行到些证明在表中没找到要查找的内容，返回0；（6） void GetData(SLinkList *L) /从键盘获得数据，存在表L中。 定义输入的状态变量x;x不为0既认为要输入 定义记录个数的整型变量j;输出输入的提示信息;scanf("%d",&x);输入x的状态； while(x) x=0;printf("t车牌号："); 输出提示

20、scanf("%s",&(L->rj.key);输入节点中对应的量printf("t车主名：");scanf("%s",&(L->);printf("t车 名：");scanf("%s",&(L->rj.carname);printf("*按任意不为0的数字继续录入*:");scanf("%d",&x);if(x)j+;L->length=j;将个数赋给表的长度（7） void prin

21、t(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;i<7;i+)if(key1i!=key2i) 任意一个不相等就不相等 ，返回0return 0;return 1;执行到这说明都相等，返回不为0的值（9）. int xiao(char key1,char k

22、ey2) /折半查找辅助比较，判断较小for(int i=0;i<7;i+)if(key1i<key2i)return 1;else if(key1i>key2i) return 0;return 0;4.设计结果与分析4.1调试过程图3程序主界面这部分执行成功，为了能够输出对称、格式整齐，所以要不断的调试、修改直到满意。（1）调试功能1添加车辆信息：从键盘输入以下几组数据； 车牌号 车主名 车名（按提示输入，以0结束轮作输入）输入成功，退出输入功能也成功，但是要注意在输入时，每个量中间不能输入空格。这样会使程序默认下个量输入结束。（2）实现功能 2输出所有车辆信息：输出的车

23、辆信息与输入和一致。此部部执行成功。（3）实现功能3按车牌号进行排序（从小到大）按照2.进行输入：在这里也套用了功能2，从结果可以看出排序成功。（4）实现功能4按车牌号码查找车辆：在上面的基础上分别查找01A1234和02A1234图4查询过程由此可能看出两部分都执行成功。（5）实现功能5，即退出程序。图5退出程序退出程序成功。4.2用户手册（1）运行程序，根据菜单选择要实现的功能，输入相应的数字。（1：输入数据；2:输出所有元素3：实现链式基数排序；4：用二分查找在表中按车牌号查找；0：退出程序）（2）当选择功能1后，根据提示输入相应的信息，在输入时，每个字符串之间不要有空格。按0退出输入。

24、（在输入时输入2位数字，一个大写字母，然后再输入四位数字）（3）当选择功能2后，会按格式输出所有节点信息。（4）当选择功能3后。会输出进行链式排序后的所有节点信息。（5）当先择功能4后，请输入您要查找车辆的车牌号码。程序会输入相应信息。（6）在没有执行第4步前，不能执行第五步。退出程序请按0，然后安任意键会关闭运行窗口。5.参考文献1 严蔚敏，吴伟民，米宁等.数据结构（C语言版）M .北京：清华大学出版社，20072 谭浩强著.C程序设计（第三版）M .北京：清华大学出版社，20053 耿国华.数据结构C语言描述M.北京：高等教育出版社，20104 严蔚敏,吴伟民，米宁等.数据结构题集（C语言

25、版）M .北京：清华大学出版社，20115 严蔚敏,李冬梅等. 数据结构（C语言版）（第2版）M .北京：清华大学出版社，2014附：源程序#include<stdio.h>#define KEY_SIZE 8#define LIST_SIZE 100typedef structchar keyKEY_SIZE;char name10;char carname20;int next;RecordType;typedef struct RecordType rLIST_SIZE;int length;int keynum;SLinkList;typedef int shuzi10;t

26、ypedef int zimu26;void InitSLList(SLinkList *L) L->length=0;L->keynum=7;void Distribute_s(RecordType r,int i,shuzi head,shuzi tail) /数字分配 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;else rtailj.next=p;tailj=p;p=rp.next;void Di

27、stribute_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;void Collect_s(RecordType r,shuzi head,shuzi tail) /收集重新构成链表 int j=0,t;while(headj=0)+j;r0.nex

28、t=headj;t=tailj;while(j<9) +j;while(j<9)&&(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=0)+j;r0.next=headj;t=tailj;while(j<25) +j;while(j<25)&&(headj=0)+j;if(headj!=0) rt.next=

29、headj;t=tailj;rt.next=0;void Radixsort(SLinkList *l) /基数排序 int n=l->length;zimu head,tail;shuzi heads,tails;for(int i=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_

30、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); void zl(SLinkList *l) /进行排序后整理顺序 int p,q;RecordType buf;p=l->r0.next; /p指向第一个记录的当前位置for(int i=1;i<l->length;i+) while(p<i)p=l->r

31、p.next; /找到第i个记录，并用p指示其在表中的当前位置。 q=l->rp.next;if(p!=i) buf=l->rp;l->rp=l->ri;l->ri=buf; /交换p与il->ri.next=p; /使得被移走的记录使得以后可以由while循环找回p=q;void GetData(SLinkList *L)/从键盘获得数据int x;int j=1;printf("请输入车牌号码及车主名与车名n");printf("例如: 01B1234"); printf("n");printf

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

33、.carname);printf("*按任意不为0的数字继续录入*:");scanf("%d",&x);if(x)j+;L->length=j;void print(SLinkList *L) /输出出所有元素 int i;printf("t");printf("车牌号 车主名 车名");printf("n");for(i=1;i<=L->length;i+) printf("t%s",L->ri.key);printf(" %s&q

34、uot; , (L->);printf(" %sn",L->ri.carname);int Equal(char key1,char key2) /折半查找辅助比较，判断是否想等，只比较前7位，第八位是结束符for(int i=0;i<7;i+)if(key1i!=key2i) return 0;return 1;int xiao(char key1,char key2) /折半查找辅助比较，mid位的数据小于查找的数for(int i=0;i<7;i+)if(key1i<key2i)return 1;else if(key1i>key2i) return 0;return 0;int Binsrch(SLinkList *L,char s8) /按车牌号，(.key)折半查找 int mid,high,low; low=1;high=L->length;while(low<=high) mid=(high+low)/2;if(Equal(s,L->rmid.key)return(mid);else if(xiao(s,L->rmid.key)high=mid-1;elselow=mid+1;return(0);void noun() /输出提示操作 printf("ttn