车牌管理系统数据结构课程设计报告Word文件下载.doc
- 文档编号:6955108
- 上传时间:2023-05-07
- 格式:DOC
- 页数:25
- 大小:209KB
车牌管理系统数据结构课程设计报告Word文件下载.doc
《车牌管理系统数据结构课程设计报告Word文件下载.doc》由会员分享,可在线阅读,更多相关《车牌管理系统数据结构课程设计报告Word文件下载.doc(25页珍藏版)》请在冰点文库上搜索。
5、每位同学需独立提交设计报告书(每人一份),要求编排格式统一、规范、内容充实,不少于10页(代码不算);
6、课程设计实践作为培养学生动手能力的一种手段,单独考核。
3.课程设计说明书
一需求分析
[问题描述]
排序和查找是在数据处理中使用频度极高的操作,为加快查找的速度需现对数据记录按关键字
排序。
在汽车数据的信息模型中,汽车牌照是关键字,而且是具有结构特点的一类关键字,因
为汽车牌照号是数字和字母混编的,例如01B7328,这种记录集合是一个适于利用多关键字进行
排序的典型例子。
[基本要求]
(1)首先利用链式基数排序方法实现排序,然后利用折半查找方法,实现对汽车记录按关键字
进行查找。
(2)汽车记录集合可以人工录入,也可以按自动方式随机生成。
本人采用的人工录入。
二概要设计
1.有关的数据
#defineKEY_SIZE8
#defineLIST_SIZE100
typedefstruct
{
charkey[KEY_SIZE];
将车牌号以字符的形式存储
charname[10];
车主的名字
charcarname[20];
车的品牌
intnext;
}RecordType;
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
开始
输入i
i=0
结果
三详细设计
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]<
key,令low=mid+1=5;
mid=(low+high)/2=6
第二步:
将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;
=0;
i--)
{
Distribute_s(l->
}
}
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;
p=第一个数据在数组中的位置
while(第一个数据在数组中的位置!
=0)
{
j=第一个数据的第i位在第几个队列
if(头指针==0)
头指针=第一个数据载表中的位置;
else
该队列已有数据的下一个位置=p否则将该数在静态链表中的位置放在在同一个队列的数据之后
尾指针=p;
tial[j]=该数在静态链表中的位置
p=下一个数据的位置值;
voidDistribute_z(RecordTyper[],inti,zimuhead,zimutail)
intp,j;
=25;
j++)
head[j]=0;
tail[j]=0;
p=r[0].next;
while(p!
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)
{
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)//字母类型收集重新构成链表
{
25)
25)&
(head[j]==0))
4.voidzl(SLinkList*l)//整理链表顺序
intp,q;
RecordTypebuf;
p=第一个元素在表中的位置;
for(inti=1;
表的长度;
while(p<
i)
p=第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
r[mid].key<
s;
则将最低位变为mid+1;
如果L->
r[mid].key>
则将最高位变为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("
r[j].name));
printf("
\t车名:
r[j].carname));
***按任意不为‘0’的数字继续录入***:
if(x)
j++;
L->
length=j;
将个数赋给表的长度
7.voidprint(SLinkList*L)遍历静态表
inti;
printf("
\t"
车牌号车主名车名\n"
=链表的长度;
{
输出各部分对应的值;
8.intEqual(charkey1[],charkey2[])//折半查找辅助比较,判断是否想等,只比较前7位,第八位是结束符
7;
if(key1[i]!
=key2[i])任意一个不相等就不相等,返回0
return0;
return1;
执行到这说明都相等,返回不为0的值
9.intxiao(charkey1[],charkey2[])//折半查找辅助比较,判断较小
if(key1[i]<
key2[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,然后安任意键会关闭运行窗口。
六测试成果
七附
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 车牌 管理 系统 数据结构 课程设计 报告