汽车牌照课程设计报告

1、下载可编辑课程设计报告一 . 问题的分析与定义题目：汽车拍照的排序与查找问题此题目主要要求对汽车牌照进行基数排序，和用二分查找的思想进行查找，这两种方法思想并不难， 但是要对汽车牌照进行排序和查找， 此问题涉及到的主要问题是：首先的问题就是，用何种存储结构对汽车信息和汽车牌照进行存储汽车牌照，然后汽车牌照不是单单是数字，而且是汉字 、字母与数字混合排列的，这就不仅仅对数字进行基数排序了，还要对字母进行相关处理，方可用基数排序的方法进行排序。经过最后查找资料 、分析将汉字 、字母转化为数字处理，汉字代表汽车牌照的地区，共有 34个省市自治区简称，即 34 个汉字 ， 26 个英语大写字母，分别用

2、数组存储这34 个汉字和 26 个大写字母 ，将他们转化为数字 ，最后再用基数排序 ，方可达到题目要求 。 在二分查找问题中 ，是对汽车牌进行查找 ，首先将要查找的汽车牌转换为数字形式 ，再用二分查找递归算法 ，找不到返回一个值 ，找到再返回一个值 ，再找到这个位置 ，输出查找的所有信息 ，即可达到题目要求 。二数据结构的选择和概要设计1.数据结构的选择对于汽车牌照进行排序和查找，为了使程序尽可能的实用性，我将定义 ，车主 ，车牌号 ，车色，车型为一个结构类型，用链表的形式存储这些信息，为了方便对汽车牌照进行排序 ，在定义一个数组存储将汉字、字母转化后的长数据类型，汉字和字母都用两个字符来表示

3、 。在基数排序中，基数排序每趟的收集由两个链队列收集，链队列的个数为基数的个数 。 在二分查找中，是对汽车牌号进行查找，首先将汽车牌号转化为数字，再用递.专业 .整理 .下载可编辑归算法查找 。 最后再将所有车辆信息输出，达到题目要求。2.概要设计为了实现上述功能，需要的函数及其功能如下：1).主函数 main()2) 车辆信息录入函数 Setlist()3) 基数每一趟的分配函数 Distribute()4) 基数每一趟的收集函数 Collect()5) 基数排序函数 paixu()6) 二分查找函数 search()7) 输出函数 print()各函数关系如下：Setlistpaixuse

4、archmainprint主函数流程图：DistributeCollectTwsearch.专业 .整理 .下载可编辑开始输入 nn=1NY调用子函数SetList(p)n=2NY调用子函数paixu(p)n=3NY调用子函数search(p)n=4NY调用子函数print()Nn=5Y结束三详细设计和编码.专业 .整理 .下载可编辑1.汽车节点类型typedef struct nodeint keynumM;/ 汽车牌照转换为十进制后的数据char key10;/ 汽车牌照号char color10;/ 汽车颜色char type10;/ 汽车类型char name10;/ 车主姓名stru

5、ct node *next;/ 指向下一个节点的指针域Rnode;2.基数排序的过程链式基数排序就是在链式存储结构下通过反复的分配、收集运算来进行排序的。首先将待排序的记录分成若干个子关键字，排序时 ，先按最低位的关键字对记录进行初步排序 ；在此基础上 ，再按次低位关键字进一步排序，以此类推 ，由低位到高位，由此关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键对记录进行排序后 ，基数排序完成 。 车牌号是由一个汉字、一个大写字母和五个数字组成，由于有34个省自治区简称，字母有26 个，本来基数应该是34，但这样一来太麻烦，而且不好分析， 故将汉字、字母转换为十进制数再进行基

6、数排序，这样做的好处是，基数都是从09 ，比较简便 ，而且易懂 。 为了更好的分析此算法，举一个例子 ：一组记录的关键字为： 83， 8，184 ， 505 ， 930 ， 589 ， 63， 109 ，278采用基数排序方法对其进行排序。上述这组关键字的值都在0 K99 的范围内 ，我们可以把每一个数位上的十进制数字看成是一个关键字，即将关键字K 看成由 3 个关键字 K0， K1， K2 组成 。 其中 ， K0 是百位上.专业 .整理 .下载可编辑的数字 ， K1 是十位上的数字，K2 是个位上的数字。因为十进制的基数是10 ，所以 ，每个数位上的数字都可能是09中的任何一个。先按关键字

7、K2 来分配所有参与排序的元素，将K2=0 的元素放在一组、 K2 =1 的元素放在一组、 、K2=9 的元素放在一组。再按 K2 的值由 0 到 9 的顺序收集各组元素 ，形成序列 （ 930 ， 063 ， 083 ， 184 ， 505 ， 278 ， 008 ，109， 589 ， 269 ）。对上述序列中的元素再按关键字K1 来分配 ，也分成 10 组。然后再按 K1 的值由 0 到 9的顺序收集各组元素 ，形成序列 （ 505 ， 008 ， 109 ， 930 ， 063 ， 269 ， 278 ， 083 ， 184，589）。对该序列中的元素再按关键字K0 来分配 。 然后按

8、 K0 的值由0 到 9 的顺序收集各组元素，形成序列 （ 008 ， 063 ， 083 ，109 ， 184 ， 267 ， 278 ， 505 ，589 ， 930 ）。 基数排序完成。分析该例 ，可以看出基数排序的思想是：首先将待排序的记录分成若干个子关键字，排序时 ，先按最低位的关键字对记录进行初步排序；在此基础上 ，再按次地位关键字进一步排序 。 依次类推 ，由低位到高位，由次关键字到主关键字，每一趟排序都在前一趟排序的基础上 ，直到按最高位关键字对记录进行排序后，基数排序完成。因此 ，在汽车牌照的基数排序中，首先将汽车牌照的汉字、字母全部转化为十进制数，以便于基数排序。汉字和字母

9、是由两个字符表示，转换好后方可进行基数排序。接下来就是如何收集各组记录。从上述例子可看出，各组记录的收集遵循“先进入该组的记录将先被收集”的原则可知 ，各组序列以列来描述较为精确。因为要进行多次的分配与收集 ，为节省存储空间及运算方便，采用链队列来存储各组序列。链队列的数量与基数一致 ， 若 基 数 为RAX ， 则 令f0fRAX-1分 别 指 向RAX个 链 队 列 的 队 头 节 点 ， 令r0rRAX-1分别指向RAX 个队列的队尾节点。每次分配前 ，将 RAX 个链队列置空 ，即.专业 .整理 .下载可编辑for(i=0;i<RAX-1;i+)fi=ri=NULL;Rnode

10、*fRAX,*rRAX;/*fRAX,*rRAX分别为链队列的队头指针和队尾指针long int elementMAX;/ 数组存储转换后的车牌号主要算法 :1).数据录入函数Rnode *SetList(Rnode *L,int n)Rnode *p;int m,j,k,i;int t=0,count=1;string r;L=NULL;for(i=0;i<n;i+)cout<<"请输入第 "<<count<<"个车主的所有信息"<<endl;cout<<endl;cout<<

11、;"车辆的车牌号是由一个汉字，一个大写字母和五个数字组成!"<<endl;cout<<"请输入该车的车牌号"p=(Rnode *)malloc(sizeof(Rnode);cin>>p->key;string key1=(string)p->key;string key2=key1.substr(0,2);for(t=0;t<=0;t+).专业 .整理 .下载可编辑for( j=0;j<N;j+)string key3=(string)a1j;/ 将汉字 、字母转化为十进制数if(key2=ke

12、y3)k=j;int s=k/10;p->keynum0=s;s=k%10;p->keynum1=s;for(int h=0;h<K;h+)if(p->key2=a2h)m=h;s=m/10;p->keynum2=s;s=m%10;p->keynum3=s;for(int n=3;n<M-1;n+)int c=p->keyn-48;p->keynumn+1=c;count+;p->next=L;L=p;return L;.专业 .整理 .下载可编辑2).基数排序若关键字为整型数据，则存放待排序记录的单链表可以这样构造：#defineN

13、8/N为待排记录的个数Rnode *L ， *p ；L = NULL ；/ 链表 L 初始化为空for(i = 1； i<=N ； +i)/ 头插法建单链表Lp = malloc(sizeof(Rnode)；for ( j = 0 ； j<= M-1； +j)/ 分别输入 M 个子关键字cin>>p->key;p->next = L；L = p ；void Distribute(Rnode *L,int i)Rnode *p;int j,k;for(k=0;k<=RAX-1;k+)fk=rk=NULL;/ 将 RAX 个链队列初始化为空p=L;whil

14、e(p!=NULL)L=L->next;j=p->keynumi;/ 用记录中第i 位关键字的值即为相应的队列号if(f j=NULL)/ 将结点 *p 分配到相应的链队列fi 中f j=p;.专业 .整理 .下载可编辑elser j->next=p;/队尾指针向后移动一位rj=p;r j->next=NULL;p=L;Rnode *Collect()/ 从链队列f0 开始 ，依次收集各链队列中的节点 Rnode *L ；int i = 0， j；while(fi= =NULL) i+； / 查找第一个不空的链队列L=fi ；for (j=i， k=i+1 ； k<

15、;=RAX-1 ； +k)if(fk!=NULL) rj->next=fk；j = k ； return L ；Rnode*paixu(Rnode *L)/ 排序函数Rnode *q;int a=0;q=L;for(int i=M-1;i>=0;i-)Distribute(L,i);L=Collect();.专业 .整理 .下载可编辑到此基数排序算法结束。从算法中容易看出，对于 个记录 （每个记录含M 个子关键字 ，每个子关键字的取值范围为RAX 个值 ）进行链式排序的时间复杂度为 (M( +RAX) ，其中每一趟分配算法的时间复杂度为 ( )，每一趟收集算法的时间复杂度为(RAX

16、)，整个排序进行M 趟分配和收集，所需辅助空间为×RAX 个队列指针 。 当然 ，由于需要链表作为存储结构， 则相对于其它以顺序结构存储记录的排序方法而言， 还增加了个指针域空间。3) 二分查找的算法思想当汽车牌照号都转换为数字形式后，需要用一个long int elementMAX进行存储 ，以便进行查找 。(1.)将表中间位置记录的关键字与给定K 值比较 ，如果两者相等，则查找成功 。（ 2）、 如果两者不等，利用中间位置记录将表分成前、后两个子表 ，如果中间位置记录的关键字大于给定K 值，则进一步查找前一子表，否则进一步查找后后一子表。（ 3）、 重复以上过程 ，直到找到满足条

17、件的记录 ，则查找成功 ，或者直到分解出的子表不存在为止 ，此时查找不成功 。例如对一有序的数组 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 ；.专业 .

18、整理 .下载可编辑第三步 ：将 amid 与 key 比较 ，此时 amid=key，查找结束 ，返回 mid ；第四步 ：如果仍未找到，则继续进行 ，直到 low>high，此时返回 -1 ，查找失败 ；对于该程序最严重的问题就是如何对链表进行二分查找，经过查找资料以及思考，要想纯粹的输入一个车牌号不做相应的变换就进行查找，这种思路虽然很清晰，但运行起来不太方便 ，因为这不仅要对数字进行查找，而且还对汉字、字母进行查找。因此 ，这种思路不合理 。 最后， 我想到用一个长整型的数组来存储变换后的车牌号，对这组车牌号再进行相关查找和相关操作，最后具体实现。该部分的具体代码为：return

19、L;int Twsearch(Rnode *L,long int key,int low,int high)/ 递归二分查找算法int mid;if(low>high)return -1;elsemid=(high+low)/2;if(elementmid=key)return mid;else if(key<elementmid)return (BinSrch(L,key,low,mid-1);elsereturn (BinSrch(L,key,mid+1,high);.专业 .整理 .下载可编辑void search(Rnode *L)/ 将要查找的车牌号转换为十进制数Rnod

20、e *p;p=L;int k,m;char d8;long int s;cin>>d;string key1=(string)d;string key2=key1.substr(0,2);for(int g=0;g<=0;g+)for(int j=0;j<N;j+)string key3=(string)a1j;if(key2=key3)k=j;s=k/10*100000000+k%10*10000000;for(int h=0;h<K;h+)if(d2=a2h)m=h;s=s+m/10*1000000+m%10*100000;s=s+(longint)d3-48

21、)*10000+(int)d4-48)*1000+(int)d5-48)*100+(int)d6-48)*10+(int)d7-48;.专业 .整理 .下载可编辑int c= BinSrch(p,s,0,b);if(c=-1)cout<<"抱歉 ,没有您要查找的记录!"<<endl<<endl;elsecout<<"查找成功 ,此车的详细信息为:"<<endl;cout<<"车主 "<<""<<" 车牌号 &q

22、uot;<<""<<" 车色 "<<""<<" 车型 "<<endl;for(int i=0;i<c;i+)p=p->next;cout<<p->name<<""<<p->key<<""<<p->color<<""<<p->type<<endl;cout<<

23、;endl;四上机调试刚开始着手做这个程序的时候，因为对数进行基数排序，我还以为很好做，但是要进行汉字、字母和数字混排的数进行基数排序，不知道该如何进行处理，修改多次程序都不能正确满足要求 ，最后 ，通过查找资料，可以把汉字 、字母转换为十进制数在进行基数排序，最后得以实现。在进行基数排序时，由于基数排序算法在书本中有详细介绍，因此没有出现太大的问题 。 在调试过程中若输入的车辆牌照有皖A12345 ，但在查找此车牌号时确显示没有您要查找的记录，经过一步一步的调试发现输入要查找的车牌号是存储在一个一维字符数组中的 ，例如 char a= 3，使用强制类型转换int b= （ int ） a，得

24、到的 b 是等于 51 的 。这是因为一个数字以字符形式存储和以整型数据存储它们的ASCII 码是不同的 。 只要将上述的强制类型转换语句改为int b=（int ） a-48 即可得到正确的结果，此问题得以解决。在.专业 .整理 .下载可编辑实现车辆信息查找时，如果在查找前并没有进行排序,不会输出结果的。因此 ，在进行查找时，先进行排序 ， 这样一来很麻烦了。经过修改 ，将排序函数直接加到查找函数中，这样不管怎么样 ，都排序了 。五测试结果及其分析1.添加车辆首先会提示输入要添加的车辆数2.选择你要执行的菜单功能3.专业 .整理 .下载可编辑3.退出六用户使用说明按提示操作 ，首先将弹出一个

25、菜单，按提示输入你要执行的菜单功能，选择1，添加.专业 .整理 .下载可编辑车辆 ，会提示添加的车辆数，再按提示输入相关数据信息，输入结束后 ，会提示一行字，flag=0, 继续操作 ，否则退出 。 选择flag=0 ，继续执行菜单功能，选择2 ，进行排序 ，选择3，按车牌号进行查找，选择 4 ，是输出所有车辆信息，5 退出程序 。七参考文献1.王昆仑 、李红主编 . 数据结构与算法. 出版地 ：中国地道出版社，2007 年2.李红 、王昆仑主编 .“数据结构与算法”设计指导2009 年2.郑莉等著 . C+ 语言程序设计（第三版 ） . 北京 :清华大学出版社,2003.专业 .整理 .下载

26、可编辑八 .附录源代码 ：#include "stdio.h"#include "iostream"#include "malloc.h"#include "string"#define NULL 0using namespace std;#define M 9/ 关键字的个数#define N 34/ 省市自治区的个数#define K 26/ 大写字母的个数#define RAX 10/ 基数的个数#define MAX 100 /最大能够处理的车辆数typedef struct nodeint keynumM

27、;char key10;char color10;char type10;char name10;struct node *next;Rnode;.专业 .整理 .下载可编辑stringa1N=" 澳 "," 川 "," 鄂 "," 甘 "," 赣"," 港 "," 贵 "," 桂 "," 黑 "," 沪 "," 吉 "," 津 "," 晋&quo

28、t;," 京 "," 辽 "," 鲁 ","闽"," 内 "," 宁 "," 青"," 琼 "," 山 ","陕 "," 苏 "," 台"," 皖 "," 湘 "," 新"," 冀 "," 渝 "," 豫"," 云 ",

29、" 藏 ","浙 " chara2K='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V

30、9;,'W','X','Y','Z'Rnode *fRAX,*rRAX;/*fRAX,*rRAX分别为链队列的队头指针和队尾指针long int elementMAX;int b;/汽车牌照转换为数字后最后一个汽车牌照的数组中的下标Rnode *SetList(Rnode *L,int n)Rnode *p;int m,j,k,i;int t=0,count=1;string r;L=NULL;for(i=0;i<n;i+)cout<<"请输入第 "<<count<<&

31、quot;个车主的所有信息"<<endl;cout<<endl;cout<<"车辆的车牌号是由一个汉字，一个大写字母和五个数字组成!"<<endl;cout<<"请输入该车的车牌号"p=(Rnode *)malloc(sizeof(Rnode);cin>>p->key;string key1=(string)p->key;string key2=key1.substr(0,2);.专业 .整理 .下载可编辑for(t=0;t<=0;t+)for( j=0;

32、j<N;j+)string key3=(string)a1j;if(key2=key3)k=j;int s=k/10;p->keynum0=s;s=k%10;p->keynum1=s;for(int h=0;h<K;h+)if(p->key2=a2h)m=h;s=m/10;p->keynum2=s;s=m%10;p->keynum3=s;for(int n=3;n<M-1;n+)int c=p->keyn-48;p->keynumn+1=c;cout<<"请输入该车的颜色:"cin>>p-&

33、gt;color;cout<<"请输入该车的车型:".专业 .整理 .下载可编辑cin>>p->type;cout<<"请输入该车的车主姓名:"cin>>p->name;cout<<endl;count+;p->next=L;L=p;return L;void Distribute(Rnode *L,int i)Rnode *p;int j,k;for(k=0;k<=RAX-1;k+)fk=rk=NULL;p=L;while(p!=NULL)L=L->next;j=

34、p->keynumi;if(f j=NULL)f j=p;elser j->next=p;/队尾指针向后移动一位rj=p;.专业 .整理 .下载可编辑r j->next=NULL;p=L;Rnode *Collect()Rnode *L;int i=0,j,k;while(fi=NULL)i+;L=fi;for( j=i,k=i+1;k<=RAX-1;k+)if(fk!=NULL)r j->next=fk;j=k;return L;int Twsearch(Rnode *L,long int key,int low,int high)int mid;if(low&

35、gt;high)return -1;elsemid=(high+low)/2;if(elementmid=key)return mid;else if(key<elementmid).专业 .整理 .下载可编辑return (Twsearch(L,key,low,mid-1);elsereturn (Twsearch(L,key,mid+1,high);void search(Rnode *L)Rnode *p;p=L;int k,m;char d8;long int s;cin>>d;string key1=(string)d;string key2=key1.substr

36、(0,2);for(int g=0;g<=0;g+)for(int j=0;j<N;j+)string key3=(string)a1j;if(key2=key3)k=j;s=k/10*100000000+k%10*10000000;for(int h=0;h<K;h+)if(d2=a2h)m=h;s=s+m/10*1000000+m%10*100000;.专业 .整理 .下载可编辑s=s+(longint)d3-48)*10000+(int)d4-48)*1000+(int)d5-48)*100+(int)d6-48)*10+(int)d7-48;int c= Twsear

37、ch(p,s,0,b);if(c=-1)cout<<"抱歉 ,没有您要查找的记录!"<<endl<<endl;elsecout<<"查找成功 ,此车的详细信息为:"<<endl;cout<<"车主 "<<""<<" 车牌号 "<<""<<" 车色 "<<""<<" 车型 "&

38、lt;<endl;for(int i=0;i<c;i+)p=p->next;cout<<p->name<<""<<p->key<<""<<p->color<<""<<p->type<<endl;cout<<endl;void print(Rnode *L)Rnode *p;p=L;cout<<"车主 "<<""<<" 车牌号 "<<""<<" 车色 "<<""<<" 车型"<<endl; while(p!=NULL)cout<<p->name<<""<<