车牌管理系统数据结构课程设计报告.doc
《车牌管理系统数据结构课程设计报告.doc》由会员分享，可在线阅读，更多相关《车牌管理系统数据结构课程设计报告.doc（25页珍藏版）》请在冰点文库上搜索。
淮海工学院计算机工程学院
课程设计报告
设计名称：
数据结构课程设计
选题名称：
汽车牌照管理系统
姓名：
学号：
专业班级：
计算机科学与应用G计111
系（院）：
计算机工程学院
设计时间：
2012.12.24~2013.1.4
设计地点：
软件工程实验室、教室
成绩：
指导教师评语：
签名：
年月日
数据结构课程设计报告第24页，共25页
1．课程设计目的
1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
2．课程设计任务与要求：
任务
根据教材《数据结构-C语言描述》（耿国华主编）和参考书《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。
设计题目从任务书所列选题表中选取，每班每题不得超过2人。
学生自选课题
学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。
学生自选课题需在18周前报课程设计指导教师批准方可生效。
要求：
1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。
前期准备工作完备与否直接影响到后序上机调试工作的效率。
在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。
2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。
3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释;
4、每位同学需提交可独立运行的程序；
5、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；
6、课程设计实践作为培养学生动手能力的一种手段，单独考核。
3．课程设计说明书
一需求分析
[问题描述]
排序和查找是在数据处理中使用频度极高的操作，为加快查找的速度需现对数据记录按关键字
排序。
在汽车数据的信息模型中，汽车牌照是关键字，而且是具有结构特点的一类关键字，因
为汽车牌照号是数字和字母混编的，例如01B7328，这种记录集合是一个适于利用多关键字进行
排序的典型例子。
[基本要求]
（1）首先利用链式基数排序方法实现排序，然后利用折半查找方法，实现对汽车记录按关键字
进行查找。
（2）汽车记录集合可以人工录入，也可以按自动方式随机生成。
本人采用的人工录入。
二概要设计
1．有关的数据
#defineKEY_SIZE8
#defineLIST_SIZE100
typedefstruct
{
charkey[KEY_SIZE];将车牌号以字符的形式存储
charname[10];车主的名字
charcarname[20];车的品牌
intnext;
}RecordType;
typedefstruct
{
RecordTyper[LIST_SIZE];是一个RecordType类型的数组
intlength;
intkeynum;
}SLinkList;
2.为了实现上述功能，需要使用一下函数：
main（）：
主函数
noun（）：
输出提示信息菜单
GetData（）：
从键盘添加车辆函数
Distribute（）：
进行基数排序每一趟的分配函数
Collect（）：
进行基数排序每一趟的收集函数
Binsrch（）：
二分查找函数
print（）：
输出所有车辆信息函数
Radixsort（）：
基数排序函数
Zl（）：
基数排序后的整理
main（）
Distribute（）
noun（）
print（）
Collect（）
GetData（）
Radixdort（）
zl（）
Binsrch（）
上图为各函数之间基本关系。
下图为程序执行的流程图。
n=1
i=2
i=3
调用子函数GetData（）
调用子函数Binsrch（）
调用子函数Radixsort（）
调用子函数print（）
i=4
Y
N
N
Y
Y
N
N
开始
输入i
N
N
Y
i=0
N
N
Y
结果
N
N
三详细设计
1、基数排序的过程：
首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次低位关键字进一步排序，以此类推，由低位到高位，由此关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键对记录进行排序后，基数排序完成。
在基数排序中，基数是各个关键只的取值范围。
若待排序的记录是十进制，则基数是10；若待排序的记录是由若干个字母组成的单词，则基数为26，也就是说，从最右边的字母开始对记录进行排序，每次排序都将待排序记录分成26组，但在此问题中，车牌号是由汉字，字母以及数字组成，若直接进行排序，则需要分成34组，为了提高算法的空间性能，可以将汉字及字母转换为十进制数后再进行基数排序。
例如：
一组记录的关键字为：
（278，109，63，930，589，184，505，269，8，83）
可以看出，这组关键字与以前说过的用来排序的关键字并无差别，且也是针对但关键字对一组记录进行排序。
但在基数排序中，我们可以将单关键字看成由若干个关键字复合而成。
上述这组关键字的值都在0~999的范围内，我们可以把一个数位上的十进制数字看成是一个关键字，即将关键字K看成由3个关键K0，K1，K2组成。
其中，K0是百位上的数字，K1是十位上的数字，K2是个位上的数字。
因为十进制的基数是10，所以，每个苏伟山的数字都可能是0~9中的任何一个。
我们先将关键字K2来分配所有参与排序的元素，将K2=0的元素防在一组、K2=1的元素放在一组、……、K2=9的元素放在一组。
这样，将上述一组元素分成10组，如下（a）图所示。
然后，再将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的值由0~9的顺序收集各组元素，形成序列（008，063，083，109，184，267，278，505，589，930）。
这时，该序列已经变成了一个有序序列。
一趟分配前的一组元素（008，063，083，109，184，267，278，505，589，930）
269
083008589
930063184505278109
k2=0k2=1k2=2k2=3k2=4k2=5k2=6k2=7k2=8k2=9
（a）、按个位数大小将元素分成10组
一趟分配后的一组元素（930，063，083，184，505，278，008，109，589，269）
109589
008269184
505930063278083
K1=0k1=1k1=2k1=3k1=4k1=5k1=6k1=7k1=8k1=9
（b）、按十位数大小将元素分成10组
二趟收集后的元素序列（505，008，109，930，063，269，278，083，184，589）
083
063184278589
008109269505930
K0=0k0=1k0=2k0=3k0=4k0=5k0=6k0=7k0=8k0=9
（c）、按百位数大小将元素分成10组
三趟收集后的元素序列（008，063，084，109，184，269，278，505，589，930）
2、二分查找的算法思想：
（1）、将表中间位置记录的关键字与给定K值比较，如果两者相等，则查找成功。
（2）、如果两者不等，利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于给定K值，则进一步查找前一子表，否则进一步查找后后一子表。
（3）、重复以上过程，直到找到满足条件的记录，则查找成功，或者直到分解出的子表不存在为止，此时查找不成功。
例如对一有序的数组a（1，2，3，4，5，6，7，8，9）进行查找数key=6；
首先定义low=0，high=8，mid=（low+high）/2=4；
第一步：
将a[mid]与key比较，我们发现a[mid]第二步：
将a[mid]与key比较，我们发现a[mid]>key，此时再令high=mid-1=5；mid=（low+high）/2=5；
第三步：
将a[mid]与key比较，此时a[mid]=key，查找结束，返回mid;
第四步：
如果仍未找到，则继续进行，直到low>high，此时返回-1，查找失败；
3、主要函数及功能
1.voidRadixsort（SLinkList*l）//基数排序
//Length个记录存放在数组r中，执行本算法进行基数排序后，链表中的记录将按关键字从小到大的顺序链接。
//
{
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;i>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）;//调用收集函数
for（i=1;i>=0;i--）
{
Distribute_s（l->r,i,heads,tails）;
Collect_s（l->r,heads,tails）;
}
}
2.VoidDistribute_s（RecordTyper[],inti,shuzihead,shuzitail）
//记录数组r中已按低位关键字key[i+1],…,key[d]进行低位优先排序，本算法按第i个关键字key[i]建立10个队列，同一个队列中记录的key[i]相同。
Head[j]和tail[j]分别指向各自队列中第一个和最后一个记录（j=0,1,2,…9）.head[j]=0表示相应队列为空队列。
//
*_s表示对数字进行的操作。
在程序中还有_z表示对字母的操作*
{
intj,p;
for（j=0;j<=队列的个数;j++） //初始化队列
{
队列的头指针=0;全部为0
对列的尾指针=0;全部为0
}
p=第一个数据在数组中的位置
while（第一个数据在数组中的位置!
=0）
{
j=第一个数据的第i位在第几个队列
if（头指针==0）
头指针=第一个数据载表中的位置;
else
该队列已有数据的下一个位置=p否则将该数在静态链表中的位置放在在同一个队列的数据之后
尾指针=p;tial[j]=该数在静态链表中的位置
p=下一个数据的位置值;
}
}
voidDistribute_z（RecordTyper[],inti,zimuhead,zimutail）
{
intp,j;
for（j=0;j<=25;j++）
{
head[j]=0;
tail[j]=0;
}
p=r[0].next;
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;
}
}
3.Voidcollect_s（RecordTyper[],shuzihead,shuzitail）
//本算法从0到9扫描个队列将所有非空队列首尾相接，重新链接成一个链表。
//
{
intj=0,t;
while（head[j]==0）
++j;//找第一个不为空的队列
r[0].next=head[j];t=tail[j];//把head[j]给第一个数据的位置
while（j<9）
{
++j;
while（（j<9）&&（head[j]==0））找到不为0的队列
++j;
if（head[j]!
=0）
{
r[t].next=head[j];
t=tail[j];
}
}
r[t].next=0;//使最后一个数的next=0
}
voidCollect_z（RecordTyper[],zimuhead,zimutail）//字母类型收集重新构成链表
{
intj=0,t;
while（head[j]==0）
++j;
r[0].next=head[j];t=tail[j];
while（j<25）
{
++j;
while（（j<25）&&（head[j]==0））
++j;
if（head[j]!
=0）
{
r[t].next=head[j];
t=tail[j];
}
}
r[t].next=0;
}
4.voidzl（SLinkList*l）//整理链表顺序
{
intp,q;
RecordTypebuf;
p=第一个元素在表中的位置;
for（inti=1;i<表的长度;i++）
{
while（pp=第p个元素的下一个数在表中的位置;
q=第p个元素的下一个数在表中的位置;
if（p!
=i）
{
buf=第p个元素的地址;
第p个元素的地址=第i个元素的地址;交换第i个元素的地址与第p个元素的地址
第i个元素的地址=buf;
第i个元素的下一个数在表中的位置=p;
}
p=q;
}
}
5.intBinsrch_bin（SLListl,chars[]）//二分查找,s为要找的内容
{
定义整形三个位置变量mid,high,low,并能后两个赋初值；（mid表示中间，high表示高位，low表示低位）
While（low<=high）
{
用mid=（high+low）/2求得mid的值；
如果L->r[mid].key＝s（要查找的内容）；则返回它在表中的位置mid
如果L->r[mid].key如果L->r[mid].key>s;则将最高位变为mid－1
}
执行到些证明在表中没找到要查找的内容，返回0；
}
6.voidGetData（SLinkList*L）//从键盘获得数据，存在表L中。
{定义输入的状态变量x;x不为0既认为要输入
定义记录个数的整型变量j;
输出输入的提示信息;
scanf（"%d",&x）;输入x的状态；
while（x）
{
x=0;
printf（"\t车牌号：
"）;输出提示
scanf（"%s",&（L->r[j].key））;输入节点中对应的量
printf（"\t车主名：
"）;
scanf（"%s",&（L->r[j].name））;
printf（"\t车名：
"）;
scanf（"%s",&（L->r[j].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[]）//折半查找辅助比较，判断是否想等，只比较前7位，第八位是结束符
{
for（inti=0;i<7;i++）
{
if（key1[i]!
=key2[i]）任意一个不相等就不相等，返回0
return0;
}
return1;执行到这说明都相等，返回不为0的值
}
9.intxiao（charkey1[],charkey2[]）//折半查找辅助比较，判断较小
{
for（inti=0;i<7;i++）
{
if（key1[i] return1;
elseif（key1[i]>key2[i]）return0;
}
return0;
}
四设计与调试分析
1.调试输出菜单：
这部分执行成功，为了能够输出对称、格式整齐，所以要不断的调试、修改直到满意。
2．调试功能1）添加车辆信息：
从键盘输入以下几组数据；
车牌号车主名车名（按提示输入，以0结束轮作输入）
输入成功，退出输入功能也成功，但是要注意在输入时，每个量中间不能输入空格。
这样会使程序默认下个量输入结束。
3.实现功能2）输出所有车辆信息：
输出的车辆信息与输入和一致。
此部部执行成功。
4.实现功能3）按车牌号进行排序（从小到大）
按照2.进行输入：
在这里也套用了功能2），从结果可以看出排序成功。
5.实现功能4）按车牌号码查找车辆：
在上面的基础上分别查找01A1234和02A1234
由此可能看出两部分都执行成功。
6.实现功能5）退出程序
退出程序成功。
五用户手册
1、运行程序，根据菜单选择要实现的功能，输入相应的数字。
（1：
输入数据；2:
输出所有元素3：
实现链式基数排序；4：
用二分查找在表中按车牌号查找；0：
退出程序）
2、当选择功能1后，根据提示输入相应的信息，在输入时，每个字符串之间不要有空格。
按0退出输入。
（在输入时输入2位数字，一个大写字母，然后再输入四位数字）
3、当选择功能2后，会按格式输出所有节点信息。
4、当选择功能3后。
会输出进行链式排序后的所有节点信息。
5、当先择功能4后，请输入您要查找车辆的车牌号码。
程序会输入相应信息。
6、在没有执行第4步前，不能执行第五步。
7、退出程序请按0，然后安任意键会关闭运行窗口。
六测试成果
七附
升级会员 