汽车牌照课程设计报告.doc

课程设计报告一. 问题的分析与定义题目：汽车拍照的排序与查找问题此题目主要要求对汽车牌照进行基数排序，和用二分查找的思想进行查找，这两种方法思想并不难，但是要对汽车牌照进行排序和查找，此问题涉及到的主要问题是：首先的问题就是，用何种存储结构对汽车信息和汽车牌照进行存储汽车牌照，然后汽车牌照不是单单是数字，而且是汉字、字母与数字混合排列的，这就不仅仅对数字进行基数排序了，还要对字母进行相关处理，方可用基数排序的方法进行排序。经过最后查找资料、分析将汉字、字母转化为数字处理，汉字代表汽车牌照的地区，共有34个省市自治区简称，即34个汉字，26个英语大写字母，分别用数组存储这34个汉字和26个大写字母，将他们转化为数字，最后再用基数排序，方可达到题目要求。在二分查找问题中，是对汽车牌进行查找，首先将要查找的汽车牌转换为数字形式，再用二分查找递归算法，找不到返回一个值，找到再返回一个值，再找到这个位置，输出查找的所有信息，即可达到题目要求。二数据结构的选择和概要设计1.数据结构的选择 对于汽车牌照进行排序和查找，为了使程序尽可能的实用性，我将定义，车主，车牌号，车色，车型为一个结构类型，用链表的形式存储这些信息，为了方便对汽车牌照进行排序，在定义一个数组存储将汉字、字母转化后的长数据类型，汉字和字母都用两个字符来表示。在基数排序中，基数排序每趟的收集由两个链队列收集，链队列的个数为基数的个数。在二分查找中，是对汽车牌号进行查找，首先将汽车牌号转化为数字，再用递归算法查找。最后再将所有车辆信息输出，达到题目要求。2.概要设计为了实现上述功能，需要的函数及其功能如下：1).主函数main()2)车辆信息录入函数Setlist()3)基数每一趟的分配函数Distribute()4)基数每一趟的收集函数Collect()5)基数排序函数paixu()6)二分查找函数search()7)输出函数print()各函数关系如下：mainSetlistpaixusearchprintDistributeCollectTwsearch主函数流程图：开始结束n=1输入nn=2n=3n=5调用子函数SetList(p)调用子函数print()调用子函数search(p)调用子函数paixu(p)n=4YNNYYYYNNNNNNNN三详细设计和编码1.汽车节点类型typedef struct nodeint keynumM; /汽车牌照转换为十进制后的数据char key10; /汽车牌照号char color10; /汽车颜色char type10; /汽车类型char name10; /车主姓名struct node *next; /指向下一个节点的指针域Rnode;2.基数排序的过程 链式基数排序就是在链式存储结构下通过反复的分配、收集运算来进行排序的。首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次低位关键字进一步排序，以此类推，由低位到高位，由此关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键对记录进行排序后，基数排序完成。车牌号是由一个汉字、一个大写字母和五个数字组成，由于有34个省自治区简称，字母有26个，本来基数应该是34，但这样一来太麻烦，而且不好分析，故将汉字、字母转换为十进制数再进行基数排序，这样做的好处是，基数都是从09，比较简便，而且易懂。为了更好的分析此算法，举一个例子：一组记录的关键字为：83，8，184，505，930，589，63，109，278采用基数排序方法对其进行排序。 上述这组关键字的值都在0K99的范围内，我们可以把每一个数位上的十进制数字看成是一个关键字，即将关键字K看成由3个关键字K0，K1，K2组成。其中，K0是百位上的数字，K1是十位上的数字，K2是个位上的数字。因为十进制的基数是10，所以，每个数位上的数字都可能是09中的任何一个。先按关键字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来分配。然后按K0的值由0到9的顺序收集各组元素，形成序列（008，063，083，109，184，267，278，505，589，930）。基数排序完成。分析该例，可以看出基数排序的思想是：首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次地位关键字进一步排序。依次类推，由低位到高位，由次关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键字对记录进行排序后，基数排序完成。因此，在汽车牌照的基数排序中，首先将汽车牌照的汉字、字母全部转化为十进制数，以便于基数排序。汉字和字母是由两个字符表示，转换好后方可进行基数排序。接下来就是如何收集各组记录。从上述例子可看出，各组记录的收集遵循“先进入该组的记录将先被收集”的原则可知，各组序列以列来描述较为精确。因为要进行多次的分配与收集，为节省存储空间及运算方便，采用链队列来存储各组序列。链队列的数量与基数一致，若基数为RAX，则令f0fRAX-1分别指向RAX个链队列的队头节点，令r0rRAX-1分别指向RAX个队列的队尾节点。每次分配前，将RAX个链队列置空，即for(i=0;iRAX-1;i+)fi=ri=NULL;Rnode *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;in;i+)cout请输入第count个车主的所有信息endl;coutendl;cout车辆的车牌号是由一个汉字，一个大写字母和五个数字组成!endl;coutp-key;string key1=(string)p-key;string key2=key1.substr(0,2);for(t=0;t=0;t+)for(j=0;jkeynum0=s;s=k%10;p-keynum1=s;for(int h=0;hkey2=a2h)m=h;s=m/10;p-keynum2=s;s=m%10;p-keynum3=s;for(int n=3;nkeyn-48;p-keynumn+1=c; ;count+;p-next=L;L=p;return L;2).基数排序若关键字为整型数据，则存放待排序记录的单链表可以这样构造： #define N 8 /N为待排记录的个数 Rnode *L，*p； L = NULL； /链表L初始化为空 for(i = 1；i=N；+i) /头插法建单链表L p = malloc(sizeof(Rnode)； for (j = 0；jp-key; p-next = L；L = p； void Distribute(Rnode *L,int i)Rnode *p;int j,k;for(k=0;knext;j=p-keynumi; /用记录中第i位关键字的值即为相应的队列号if(fj=NULL) /将结点*p分配到相应的链队列fi中fj=p;elserj-next=p;/队尾指针向后移动一位 rj=p; rj-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；knext=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)，整个排序进行M趟分配和收集，所需辅助空间为RAX个队列指针。当然，由于需要链表作为存储结构， 则相对于其它以顺序结构存储记录的排序方法而言， 还增加了个指针域空间。3)二分查找的算法思想当汽车牌照号都转换为数字形式后，需要用一个long int elementMAX进行存储，以便进行查找。(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； 第一步：将amid与key比较，我们发现a midkey，此时再令high=mid-1=5；mid=（low+high）/2=5； 第三步：将amid与key比较，此时amid=key，查找结束，返回mid； 第四步：如果仍未找到，则继续进行，直到lowhigh，此时返回-1，查找失败；对于该程序最严重的问题就是如何对链表进行二分查找，经过查找资料以及思考，要想纯粹的输入一个车牌号不做相应的变换就进行查找，这种思路虽然很清晰，但运行起来不太方便，因为这不仅要对数字进行查找，而且还对汉字、字母进行查找。因此，这种思路不合理。最后，我想到用一个长整型的数组来存储变换后的车牌号，对这组车牌号再进行相关查找和相关操作，最后具体实现。该部分的具体代码为：return L;int Twsearch(Rnode *L,long int key,int low,int high) /递归二分查找算法int mid;if(lowhigh)return -1;elsemid=(high+low)/2;if(elementmid=key)return mid;else if(keyd;string key1=(string)d;string key2=key1.substr(0,2);for(int g=0;g=0;g+)for(int j=0;jN;j+)string key3=(string)a1j;if(key2=key3) k=j;s=k/10*100000000+k%10*10000000;for(int h=0;hK;h+)if(d2=a2h)m=h; s=s+m/10*1000000+m%10*100000;s=s+(long int)d3-48)*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抱歉,没有您要查找的记录!endlendl;elsecout查找成功,此车的详细信息为:endl;cout车主 车牌号 车色 车型endl;for(int i=0;inext;coutname key color typeendl;coutendl;四上机调试刚开始着手做这个程序的时候，因为对数进行基数排序，我还以为很好做，但是要进行汉字、字母和数字混排的数进行基数排序，不知道该如何进行处理，修改多次程序都不能正确满足要求，最后，通过查找资料，可以把汉字、字母转换为十进制数在进行基数排序，最后得以实现。在进行基数排序时，由于基数排序算法在书本中有详细介绍，因此没有出现太大的问题。在调试过程中若输入的车辆牌照有皖A12345，但在查找此车牌号时确显示没有您要查找的记录，经过一步一步的调试发现输入要查找的车牌号是存储在一个一维字符数组中的，例如char a=3，使用强制类型转换int b=（int）a，得到的b是等于51的。这是因为一个数字以字符形式存储和以整型数据存储它们的ASCII码是不同的。只要将上述的强制类型转换语句改为int b=（int）a-48即可得到正确的结果，此问题得以解决。在实现车辆信息查找时，如果在查找前并没有进行排序,不会输出结果的。因此，在进行查找时，先进行排序，这样一来很麻烦了。经过修改，将排序函数直接加到查找函数中，这样不管怎么样，都排序了。五测试结果及其分析1.添加车辆首先会提示输入要添加的车辆数2.选择你要执行的菜单功能 33.退出六用户使用说明按提示操作，首先将弹出一个菜单，按提示输入你要执行的菜单功能，选择1，添加车辆，会提示添加的车辆数，再按提示输入相关数据信息，输入结束后，会提示一行字，flag=0,继续操作，否则退出。选择flag=0，继续执行菜单功能，选择2，进行排序，选择3，按车牌号进行查找，选择4，是输出所有车辆信息，5退出程序。七参考文献1.王昆仑、李红主编. 数据结构与算法. 出版地：中国地道出版社，2007年2.李红、王昆仑主编.“数据结构与算法”设计指导 2009年2.郑莉等著. C+语言程序设计（第三版）. 北京:清华大学出版社,2003.八.附录源代码：#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;char key10;char color10;char type10;char name10;struct node *next;Rnode;string a1N=澳,川,鄂,甘,赣,港,贵,桂,黑,沪,吉,津,晋,京,辽,鲁,闽,内,宁,青,琼,山,陕,苏,台,皖,湘,新,冀,渝,豫,云,藏,浙; char a2K=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,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;in;i+)cout请输入第count个车主的所有信息endl;coutendl;cout车辆的车牌号是由一个汉字，一个大写字母和五个数字组成!endl;coutp-key;string key1=(string)p-key;string key2=key1.substr(0,2);for(t=0;t=0;t+)for(j=0;jkeynum0=s;s=k%10;p-keynum1=s;for(int h=0;hkey2=a2h)m=h;s=m/10;p-keynum2=s;s=m%10;p-keynum3=s;for(int n=3;nkeyn-48;p-keynumn+1=c;coutp-color;coutp-type;coutp-name;coutnext=L;L=p;return L;void Distribute(Rnode *L,int i)Rnode *p;int j,k;for(k=0;knext;j=p-keynumi;if(fj=NULL)fj=p;elserj-next=p;/队尾指针向后移动一位 rj=p; rj-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;knext=fk;j=k;return L;int Twsearch(Rnode *L,long int key,int low,int high)int mid;if(lowhigh)return -1;elsemid=(high+low)/2;if(elementmid=key)return mid;else if(keyd;string key1=(string)d;string key2=key1.substr(0,2);for(int g=0;g=0;g+)for(int j=0;jN;j+)string key3=(string)a1j;if(key2=key3) k=j;s=k/10*100000000+k%10*10000000;for(int h=0;hK;h+)if(d2=a2h)m=h; s=s+m/10*1000000+m%10*100000;s=s+(long int)d3-48)*10000+(int)d4-48)*1000+(int)d5-48)*100+(int)d6-48)*10+(int)d7-48;int c= Twsearch(p,s,0,b);if(c=-1)cout抱歉,没