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

《车牌号管理系统数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《车牌号管理系统数据结构课程设计报告.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、车牌号管理系统数据结构课程设计报告 XX 学 院 计算机工程学院 课程设计报告 设计名称： 数据结构课程设计 选题名称： 车牌号管理系统 姓 名： 学 号： 专业班级： 软件工程 系 （院）： 计算机工程学院 设计时间： 2011.12.192011.12.30 设计地点： 软件工程试验室、教室 成果： 指导老师评语： 签名： 年 月 日 1课程设计目的 1、训练学生敏捷应用所学数据结构学问，独立完成问题分析，结合数据结构理论学问，编写程序求解指定问题。 2.初步驾驭软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论学问和方法独立分析和解决问题的实力

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

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

4、编排格式统一、规范、内容充溢，不少于10页（代码不算）； 6、课程设计实践作为培育学生动手实力的一种手段，单独考核。 3课程设计说明书 一 需求分析 1功能需求： 本程序利用基数排序的思想对一批具有结构特征的汽车牌照进行排序，并且利用二分查找的思想对排好序的汽车牌照进行查找。 2性能需求： 运行程序时，输入一组要求的数据后，按要求操作，进行排序，查询时程序查找到匹配的数据，输出该关键字的其他信息。3数据需求： 数据包括3项，分别为牌照的号码，车的型号，车主的姓名，其中牌照的一项输入形式为01B7328，前两位代表地区，字母代表车的运用类型，后四位代表车号，查询时要求输入正确的车牌号码。 二 概

5、要设计 1设计静态查找表的抽象数据类型 ADT RecordType char name20; 车主名字 char carname20; 车名 KeyType key7; 子关键字 ADT RecordType ADT SLinkList 数据元素：关键字，是一个RecordType类型的数组，存放车牌号。 数据之间的关系是线性关系； 2.本程序包含三个模块。主程序中的内容有 Void main 1初始化加入数据； 2.遍历表； 3排序； 4折半查找； 5.退出； 系统中的子程序及功能要求。1.Void Distribute(RecordType r,int i,pvector head,pv

6、ector tail) 记录 数组r中已按低位关键字keyi+1,keyd进行低位优先排序，本算法 按第i个关键字keyi建立10个队列，同一个队列中记录的keyi相同。Headj和tailj分别指向各自队列中第一个和最终一个记录（j=0,1,2,9）.headj=0表示相应队列为空队列。2.Void collect(RecordType r,pvctor head,pvctor tail) 本算法从0到9扫描个队列将全部非空队列首尾相接，重新链接成一个链表。3.Void RadixSort(Record r,int length) Length 个记录存放在数组r中，执行本算法进行基数排序后

7、，链表中的记录将按关键字从小到大的依次链接。5. void arrange(SLinkList *l) 对静态表进行整序 6.int search_bin(SLList l,char key) 二分查找 7. void GetData(SLinkList *L) 从键盘获得数据。8. void SLListTraverse(SLinkList *L) 遍历静态表 9. int Equal(char key1,char key2) 推断相等 10. int Little(char key1,char key2) 推断较小 模块之间调用关系 主函数调,（3,5）,6,7,8 3调用1,2 6调用

8、9,10 三 具体设计 主要函数 void Distribute_n(RecordType r,int i,shuzi head,shuzi tail) /数字安排 int j,p; for(j=0;j<=队列的个数;j+) /初始化队列 队列的头指针=0;全部为0 对列的尾指针=0;全部为0 p=第一个数据在数组中的位置 while(第一个数据在数组中的位置!=0) j=第一个数据的第i位在第几个队列 if(头指针=0) 头指针=第一个数据载表中的位置; else 该队列已有数据的下一个位置=p 否则将该数在静态链表中的位置放在在同一个队列的数据之后 尾指针=p; tialj=该数在静

9、态链表中的位置 p=下一个数据的位置值; void Collect_n(RecordType r,shuzi head,shuzi tail) /收集重新构成链表 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=0 void radixsort(SLin

10、kList *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; 使最终一个数的next等于0 for(i=6;i>2;i-) Distribute_n(l->r,i,heads,tails); 调用安排函数 Collect_n(l->r,heads,tails); 调用收集函数 Distribute_c(l->r,

11、2,head,tail); 调用安排函数 Collect_c(l->r,head,tail); 调用收集函数 for(i=1;i>=0;i-) Distribute_n(l->r,i,heads,tai 调用安排函数 Collect_n(l->r,heads,tails); 调用收集函数 void arrange(SLinkList *l) /整序 int p,q; RecordType buf; 建立中间变量 p=第一个元素在表中的位置; p指向第一个元素在表中的位置 for(int i=1;i<表的长度;i+) while(p<i)p=第p个元素的下一个

12、数在表中的位置; q=第p个元素的下一个数在表中的位置; if(p!=i) buf=第p个元素的地址; 第p个元素的地址=第i个元素的地址; 交换第i个元素的地址与第p个元素的地址 第i个元素的地址=buf; 第i个元素的下一个数在表中的位置=p; p=q; void GetData(SLinkList *L) /获得数据 char key=0; int j=1; cout<<“请输入车牌号码及车名与车主名,用#结束“<<endl; cout<<“例如: 01B3456“<<endl; cout<<“车牌号=“; for(int i=

13、0;i<7;i+) cin>>key; 输入数据 第一个数据的车牌号码=key; cout<<“车名:“; cin>>第一个数据的车名; cout<<“车主名:“; cin>>第一个数据的车主名; while(key!=#) j+; cout<<endl<<“车牌号=“; for(int i=0;i<7;i+) cin>>key; 输入第j个数据的车牌号码 if(key=#) j-;break; 第j个数据的车牌号码=key; if(key=#) break; cout<<“

14、车名:“; cin>>L->rj.carname; cout<<“车主名:“; cin>>L->rj.name; L->length=j; int binsearch(SLinkList *L,char s7) /折半查找 int k=0,sum=0,ss=0,mid,high,low=1; high=L->length; while(low<=high) mid=(high+low)/2; if(Equal(s,L->rmid.key)return(mid); 调用推断相等函数 else if(Little(s,L-&g

15、t;rmid.key)high=mid-1; 调用比较大小函数 else low=mid+1; return(0); 四 设计与调试分析 1.车牌号管理 1.1 初始化输入数据，车牌号码，车主名以及车名。从键盘输入须要的数据。如 车牌号：20W4521 车名bmw 车主名 zzx 车牌号：11F4587 车名lanbogine 车主名 zzp 车牌号：55F1254 车名benz 车主名 xcl 初始化胜利。1.2将表中的内容输出 遍历胜利。车牌号：20W4521 车名bmw 车主名 zzx 车牌号：11F4587 车名lanbogine 车主名 zzp 车牌号：55F1254 车名benz

16、车主名 xcl 与输入结果一样。1.3对车牌号进行排序，用基数排序的方法。 11F4587 lanbogine zzp 20W4521 bmw zzx 55F1254 benz xcl 与预期结果一样。 1.4折半查找须要的车牌号码，输出此车牌号码的车主及车名 与预期结果一样。查找胜利。1.5退出 五 用户手册 1.运行程序，首先出现主界面，选项一，初始化表加入数据。选项二，遍历表。选项三，对车牌号排序。选项四，查找。选项五，退出。运行查找之前肯定要进行排序，因为是折半查找，所以要先进行排序。2.输入数据，输入车牌号码，例如01B3456,及车主的姓名，车的名字。3.遍历，依次输出全部的数据

17、4，按基数排序的方法进行排序 5，查找，输入要查找的车牌号码，若查找胜利则返回须要的车牌号及车主名与车名，若没有此信息则返回没有此车牌号。六 测试成果 七 附录（源程序清单） #define KEY_SIZE 7 #define LIST_SIZE 10 #include <iostream> using namespace std; typedef struct char keyKEY_SIZE; char name10; char carname20; int next; RecordType; typedef struct RecordType rLIST_SIZE; int

18、 length; int keynum; SLinkList; typedef int shuzi10; typedef int zimu26; void InitSLList(SLinkList *L) /链表初始化 L->length=0; L->keynum=7; void Distribute_n(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(h

19、eadj=0) headj=p; else rtailj.next=p; tailj=p; p=rp.next; void Distribute_c(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_n(RecordType

20、 r,shuzi head,shuzi tail) /收集重新构成链表 int j=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; void Collect_c(RecordType r,zimu head,zimu tail) /字母类型收集重新构成链表 int j=0,t; while(headj=0) +j; r0.next=headj;t=tailj; wh

21、ile(j<25) +j; while(j<25)(headj=0) +j; if(headj!=0) rt.next=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_n(l->r,i,heads,tails);

22、 /调用安排函数 Collect_n(l->r,heads,tails); /调用收集函数 Distribute_c(l->r,2,head,tail); /调用安排函数 Collect_c(l->r,head,tail); /调用收集函数 for(i=1;i>=0;i-) Distribute_n(l->r,i,heads,tails); /调用安排函数 Collect_n(l->r,heads,tails); /调用收集函数 void arrange(SLinkList *l) /整序 int p,q; RecordType buf; p=l->r

23、0.next; /p指向第一个记录的当前位置 for(int i=1;i<l->length;i+) while(p<i)p=l->rp.next; /找到第i个记录，并用p指示其在表中的当前位置。 q=l->rp.next; if(p!=i) buf=l->rp; l->rp=l->ri; l->ri=buf; /交换p与i l->ri.next=p; /使得被移走的记录使得以后可以由while循环找回 p=q; void GetData(SLinkList *L) /获得数据 char key=0; int j=1; cout&l

24、t;<“请输入车牌号码及车名与车主名,用#结束“<<endl; cout<<“例如: 01B3456“<<endl; cout<<“车牌号=“; for(int i=0;i<7;i+) cin>>key; L->r1.keyi=key; cout<<“车名:“; cin>>L->r1.carname; cout<<“车主名:“; cin>>L->r1.name; while(key!=#) j+; cout<<endl<<“车牌号=“

25、; for(int i=0;i<7;i+) cin>>key; if(key=#) j-;break; L->rj.keyi=key; if(key=#) break; cout<<“车名:“; cin>>L->rj.carname; cout<<“车主名:“; cin>>L->rj.name; L->length=j; void SLListTraverse(SLinkList *L) /遍历静态表 int i,j; cout<<endl; cout<<“车牌号“<<

26、“ “<<“车名“<<“ “<<“车主名“<<endl<<endl; for(i=1;i<=L->length;i+) for(j=0;j<7;j+) cout<<L->ri.keyj; cout<<“ “<<L->ri.carname<<“ “; cout<<L->ri.name<<endl; int Equal(char key1,char key2) /推断相等 for(int i=0;i<7;i+) if(key1

27、i!=key2i) return 0; return 1; int Little(char key1,char key2) /推断较小 for(int i=0;i<7;i+) if(key1i<key2i) return 1; else if(key1i>key2i) return 0; return 0; int binsearch(SLinkList *L,char s7) /折半查找 int k=0,sum=0,ss=0,mid,high,low=1; high=L->length; while(low<=high) mid=(high+low)/2; if

28、(Equal(s,L->rmid.key)return(mid); else if(Little(s,L->rmid.key)high=mid-1; else low=mid+1; return(0); void main() int i; SLinkList l; do cout<<“请选择 1.初始化表加入数据 2.遍历表 3.对车牌号排序 4.折半查找(必需先排好序) 5退出 “<<endl; cin>>i; switch(i) case 1:InitSLList(l); GetData(l); break; case 2:SLListTr

29、averse(l);break; case 3:radixsort(l); arrange(l); SLListTraverse(l); break; case 4: int find; char s7; cout<<“请输入要查找的车牌号码“<<endl; cin>>s; find=binsearch(l,s); if(find) cout<<“在表中的位置为“<<binsearch(l,s)<<endl; cout<<“车名“; cout<<l.rfind.carname<<endl

30、; cout<<“车牌号码“; for(int i=0;i<7;i+) cout<<l.rfind.keyi; cout<<endl; cout<<“车主名“; cout<<l.rfind.name<<endl; else cout<<“没有此车牌号“<<endl; break; case 5:break; while(i!=5); 4.课程设计心得 本次课程设计我选择的是一个车牌号的管理系统，功能少，只有两个功能，一个是排序，一个是查找，排序要用到基数的排序的方法，就是一种多关键字的排序，

31、而查找用到的则是二分查找。虽然程序的内容少，看似简洁，但是基数排序是个很难的排序，也是一个让我理解了好久才弄懂的，这个排序特别的经典，当我看到这个排序的思想的时候我就感觉这个排序实在是绝，它与其他的排序的方法都不同，别的排序方法都是比较，移动关键字，但是它是比较关键字中的子关键字，从最终一位关键字起先比较，假如是数字就依据关键字中的组后一个子关键字分别放入十个队列中，假如是字母则类似，放入二十六个队列中。在收集函数则是将队列的首尾相连，重新构成一个链表，如此反复的调用这些函数，最终就会形成以个有序的静态链表，但是此时的静态链表只是逻辑结构中的有序，而不是储存结构中的有序，还要在进行一次整序，使链表真正的有序。在调试过程中参考书中的代码以及自己在图书馆中的借的相关书籍，最终在对程序进行了进一步的调整，完成了代码的调试。 在折半查找中，调用了比较跟推断相等的函数，依据书上的折半查找的算法进行改进，就可以胜利了。本次课程设计中最重要的一点就是驾驭基数排序，对于折半查找进行肯定的改进，最终的遍历自己随意怎么写都行。通过本次课程设计，我对排序的方法上又多了一种相识，多了一种理解，对程序的把握上更加精确了。增加了自己的编程实力，也对数据结构这门课程有了更深的相识。今后将更加的努力学习相关学问来弥补自己在许多方面的不足，缩小跟别人的差距。