汽车牌照的排序与查找问题数据结构与算法课程设计报告.pdf

合肥学院 计算机科学与技术系 课程设计报告 2009 20010 学年第 二 学期 课程 数据结构与算法 课 程 设 计 名 称 汽车牌照的排序与查找问题 学生姓名 闵晓龙 学号*专业班级 08 计本（2）班 指导教师 王昆仑 -1-20010 年 6 月 题目：汽车牌照的排序与查找问题，实现对汽车牌照按多关键字排序及快速查找。其中汽车牌照有汉字、字母和数字混合排列，例如：皖 A12345。使用基数排序方法进行排序，并在排序的基础上，利用二分查找思想实现对汽车牌照按多关键字的查找。一、问题分析和任务定义 此程序要完成如下要求：选择一种数据结构来存储每个车辆的信息（如车主姓名,汽车等），在此基础上进行基数排序，而汽车牌照是由汉字、字母以及数字组成，即多关键字，其中字母和数字的比较是比较容易实现的，考虑到汉字的存储等各方面原因，对汉字的排序并不是很容易就能完成的，故不能直接对汉字排序。经过分析可知，汽车牌照中的汉字是各个省市自治区的简称，共有 34 个。这些汉字可以根据其汉语拼音的规则进行排序，然后预先存放到字符串数组中，这样每个汉字就对应着一个数组下标，只要对数组下标进行排序就可以实现对汉字的排序了。在对车牌号进行查找时，先对车牌号进行排序，然后将车牌号中的汉字及字符均转换成一个长整形数据存储在一个预先定义的一个一维数组中并把需要查找的车牌号码也转换成一个长整型数据，然后在原先的一维数组中使用二分查找来查找该车牌号码对应的车辆信息。二、数据结构的选择和概要设计 1、数据结构的选择：程序要求实现对汽车牌照的排序与查找，而如果仅仅进行牌照的排序与查找，则显得程序没有太大的实用性，所以考虑在程序中加入例如车主的姓名以及车子的品牌等内容来增加程序的实用性。为了能够更好的完成这些功能，在这里选用链表来存储所有车辆的信息，用链表中的单个节点来存储一辆汽车的信息，而对应的各个节点的域中则存储其对应的车辆信息（如车牌号码、车主姓名、车的品牌等信息）。在存储汽车牌照中的汉字时，由于汉字在内存中占用两个字节，需要使用字符串数据来存储。其中的 26 个字母则使用一个一维字符数组来存储。车主的姓名及车子的品牌则使用一维字符数组来存储。在基数排序时，每趟的数据收集由两个链队列来完成，链队列的个数为基数的个数，两个链队列的队列指针分别指向每组链队列的队头和队尾。2、概要设计 为了实现上述功能，需要使用一下函数：main()：主函数 Setlist()：添加车辆函数 Distribute()：进行基数排序每一趟的分配函数 Collect()：进行基数排序每一趟的收集函数 find()：二分查找函数 menu()：菜单函数 print()：输出所有车辆信息函数 insort()：基数排序函数 -2-图 1 各函数间关系如下：main()Distribute()menu()print()Collect()Setlist()find()insort()n=1 n=p n=c 调用子函数 SetList(p)调用子函数 print()调用子函数 find(p)调用子函数 paixu(p)n=s Y N Y Y N 开始 输入 n N Y n=q N Y 结果 N -3-图 2 主函数 main()流程图 图 3 添加车辆函数 SetList(p)流程图 开始 结束 i=M-1 i=0 调用 Distribute 及 Collect函数 i+遍历排序好的链表将每个车辆的牌照号转换为长整型数据存于一个一维数组AMAX中。Y N 开始 结束 申请一结点 p 并为其分配内存空间 head=NULL head=p 输入汽车的相应信息，经过相应的处理后存入结点 p 相应的域。将该结点按尾插法插入到链表的相应位置 返回该链表的头指针 Y N -4-图 4 排序子函数 paixu(p)的流程图 图 5 查找子函数 find(p)的流程图 三、详细设计和编码 1、文件的的读取：在这个程序当中采取了文件的读取，主要实现的功能是从文件当中读取所要处理的数据，即为车牌的信息资料。如一个车牌的信息包括：车牌号（皖 A12345）、车主姓名（张三）和车的品牌（宝马）三个内容，在程序的操作过程过程是对文件进行一个一个读取，用fscanf(f1,”%s%s%s”,p-key,p-name,p-paizi)语句来实现，就是将车牌号（皖 A12345）读入到 p-key 当中，将车主姓名读入到 p-name 当中，将车的品牌读入到 p-paizi 当中。读入之后就可以对其进行操作了。由于文件尾默认为-1 结束，所以对文件读取的控制采用while(fscanf(f1,%s%s%s,p-key,p-name,p-paizi)!=EOF)来实现 还有就是读入方法，这个程序是采用链表的存储方式来存取信息的，所以读入方式可以采取头插法建立链表的方法来对每个文件进行读取。头插法的具体操作为 head=NULL;开始 结束 输入需要查找的牌照 将待查找的牌照号处理后存于一整型变量中 调用二分查找函数并返回 c c=-1 没有查找成功 查找成功并输出该车的信息 Y N -5-p=(Rnode*)malloc(sizeof(Rnode);p-next=NULL;while(fscanf(f1,%s%s%s,p-key,p-name,p-paizi)!=EOF)if(head=NULL)l=head=p;else l-next=p;l=p;p=(Rnode*)malloc(sizeof(Rnode);p-next=NULL;2、基数排序的过程：首先将待排序的记录分成若干个子关键字，排序时，先按最低位的关键字对记录进行初步排序；在此基础上，再按次低位关键字进一步排序，以此类推，由低位到高位，由此关键字到主关键字，每一趟排序都在前一趟排序的基础上，直到按最高位关键对记录进行排序后，基数排序完成。在基数排序中，基数是各个关键只的取值范围。若待排序的记录是十进制，则基数是10；若待排序的记录是由若干个字母组成的单词，则基数为 26，也就是说，从最右边的字母开始对记录进行排序，每次排序都将待排序记录分成 26 组，但在此问题中，车牌号是由汉字，字母以及数字组成，若直接进行排序，则需要分成 34 组，为了提高算法的空间性能，可以将汉字及字母转换为十进制数后再进行基数排序。例如：一组记录的关键字为：（278，109，63，930，589，184，505，269，8，83）可以看出，这组关键字与以前说过的用来排序的关键字并无差别，且也是针对但关键字对一组记录进行排序。但在基数排序中，我们可以将单关键字看成由若干个关键字复合而成。上述这组关键字的值都在 0999 的范围内，我们可以把一个数位上的十进制数字看成是一个关键字，即将关键字 K 看成由 3 个关键 K0，K1，K2组成。其中，K0是百位上的数字，K1是十位上的数字，K2是个位上的数字。因为十进制的基数是 10，所以，每个苏伟山的数字都可能是 09 中的任何一个。我们先将关键字 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的值由 09 的顺序收集各组元素，形成序列（008，063，083，109，184，267，278，505，589，930）。这时，该序列已经变成了一个有序序列。一趟分配前的一组元素（008，063，083，109，184，267，278，505，589，930）269 083 008 589 -6-930 063 184 505 278 109 k2=0 k2=1 k2=2 k2=3 k2=4 k2=5 k2=6 k2=7 k2=8 k2=9 （a）、按个位数大小将元素分成 10 组 一趟分配后的一组元素（930，063，083，184，505，278，008，109，589，269）109 589 008 269 184 505 930 063 278 083 K1=0 k1=1 k1=2 k1=3 k1=4 k1=5 k1=6 k1=7 k1=8 k1=9 （b）、按十位数大小将元素分成 10 组 二趟收集后的元素序列（505，008，109，930，063，269，278，083，184，589）083 *008 109 269 505 930 K0=0 k0=1 k0=2 k0=3 k0=4 k0=5 k0=6 k0=7 k0=8 k0=9 （c）、按百位数大小将元素分成 10 组 三趟收集后的元素序列（008，063，084，109，184，269，278，505，589，930）3、链式基数排序算法实现的技术要点：要实现上述基数排序的过程，需要解决 3 个问题。问题一：如何描述由待排序关键字分成的若干个子关键字？问题二：每次分配记录所形成的各组序列以何种结构存储？问题三：如何收集各组记录？其实，当问题三得以解决后，问题二也就解决了；因为问题三运算方式决定了问题二的存储结构。由上例可以看出，各组记录的收集是本着“先进入该组的记录将首先被收集”的原则。这与队列的“先进先出”的原则相一致。这样，各组序列就以队列来描述。因为要进行多次的分配与收集，为节省存储空间及运算方便，我们采用链队列来存储各组序列。其实，当问题三得以解决后，问题二也就解决了；因为问题三运算方式决定了问题二的存储结构。链队列的数量与基数一致，若基数为 RAX，则令 f0fRAX-1分别指向 RAX 个链队列的队头节点，令 r0rRAX-1分别指向 RAX 个队列的队尾节点。每次分配前，将 RAX 个链队列置空：for(i=0i=RAX-1+i)-7-fi=ri=NULL；对各链队列所表示的序列进行收集时，应从链队列 f0开始，当链队列 fj+1不为 NULL时，将链队列 fj与其首尾相接：i=0；while(fi=NULL)i+；/查找第一个不空的链队列 for(j=i，k=i+1；knext=fk；j=k；对于问题一，一个简单的方法是，在存储待排序记录时，就将关键字按分成子关键字来存储。为了运算方便，我们采用与链队列中节点一致的节点结构，以单链表来存储待排序的一组记录及收集后的记录序列。节点的类型可以定义为：#define M 3 /M 为待排记录中子关键字的个数 typedef struct node keytype keyM；struct node *next；Rnode；若关键字为整型数据，则存放待排序记录的单链表可以这样构造：#define N 8 /N 为待排记录的个数 Rnode*L，*p；L=NULL；/链表 L 初始化为空 for(i=1；i=N；+i)/头插法建单链表 L p=malloc(sizeof(Rnode)；for(j=0；jkeyj)；p-next=L；L=p；综上所述，以链表来存储待排序记录，基数排序算法如下：#define M 3 /M 为待排记录中子关键字的个数#define RAX 10 /RAX 为基数 typedef struct node keytype keyM；struct node *next；Rnode；Rnode*fRAX，*rRAX；Rnode*SetList()/建待排序记录组成的单链表 L Rnode*L，*p；int i，j；L=NULL；/链表 L 初始化为空 for(i=1；i=n；+i)/头插法建单链表 L，n 为待排序记录个数 p=(Rnode*)malloc(sizeof(Rnode)；for(j=0；jkeyj)；-8-p-next=L；L=p；return L；void Distribute(Rnode*L，int i)/扫描链表 L，按第 i 个关键字将各记录分配到相应的链队列中 Rnode*p；int i，j；for(i=0；inext；j=p-keyi；/用记录中第 i 位关键字的值即为相应的队列号 if(fj=NULL)fj=p；/将节点*p 分配到相应的链队列中 fj else rj-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*RadixSort(int n)/对 n 个记录进行基数排序 Rnode*L；L=SetList()；/建待排序记录组成的单链表 L for(i=M-1；i=0；-i)/分别按 M 个子关键字对待排序列进行分配和收集 Distribute(L，i)；L=Collect()；return L；从算法中容易看出，对于个记录（每个记录含 M 个子关键字，每个子关键字的取值范围为 RAX 个值）进行链式排序的时间复杂度为(M(+RAX)，其中每一趟分配算法的时间复杂度为()，每一趟收集算法的时间复杂度为(RAX)，整个排序进行 M 趟分配和收集，所需辅助空间为RAX 个队列指针。当然，由于需要链表作为存储结构，则相对于其它以顺序结构存储记录的排序方法而言，还增加了个指针域空间。-9-4、对于此题目，车牌号是由汉字，字母和数字组成，而输入的时候是以字符的形式接收的，首先应该在链表的各个结点中申请一个整型数组用于存储将汉字和字母转换为整型数据的数字，以便基数排序的顺利进行。针对此题目具体代码段为：Rnode *insort(Rnode*p)Rnode*q;int a=0;for(int i=M-1;i=0;i-)Distribute(p,i);q=p=Collect();cout排序已完成!keynum0*100000000+q-keynum1*10000000+q-keynum2*1000000+q-keynum3*100000+q-keynum4*10000+q-keynum5*1000+q-keynum6*100+q-keynum7*10+q-keynum8;q=q-next;b=a;a+;flag=0;return p;void Distribute(Rnode*L,int j)Rnode*p;int i,k=0;for(i=0;inext;k=p-keynumj;if(fk=NULL)fk=p;else rk-next=p;/队尾指针向后移动一位 rk=p;rk-next=NULL;p=L;Rnode*Collect()/每一趟的收集函数 -10-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;5、二分查找的算法思想：（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；1 2 3 4 5 6 7 8 9 low mid high 查找成功，此时返回 mid 1 2 3 4 5 6 7 8 9 low mid high amidkey high=mid-1=5 mid=(low+high)/2=5 1 2 3 4 5 6 7 8 9 low mid high amidhigh，此时返回-1，查找失败；6、对于该程序最严重的问题就是如何对链表进行二分查找，经过查找资料以及大量的思考，这种想法对于我的能力来说几乎不可能，最后我使用这样一种思路，在每次的基数排序后就将链表中每个结点的车牌号关键字存于一个全局一维长整型数组中，并记录数组中最后一个元素的下标。这样再进行二分查找就可以实现了。该部分的具体代码为：int BinSrch(Rnode*q,long int k,int low,int high)int mid;if(lowhigh)return-1;else mid=(high+low)/2;if(Amid=k)return mid;else if(kAmid)return(BinSrch(q,k,low,mid-1);else return(BinSrch(q,k,mid+1,high);void find(Rnode*q)Rnode*p;p=q;int k,m,c,g;char d8;long int s;cout=欢迎来到车辆牌照查询系统=endl;cout=请注意车辆的牌照号是由一个汉字，一个大写字母和五个数字组成!endl;cout请输入您要查找的车辆的汽车牌照:d;string key1=(string)d;string key2=key1.substr(0,2);for(g=0;g=0;g+)for(int j=0;j33|k0)cout对不起,您输入的车牌号不合法,请重新输入!endl;break;-13-s=k/10*100000000+k%10*10000000;for(int h=0;h25|m0)cout对不起,您输入的车牌号不合法,请重新输入!endl;break;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;c=BinSrch(q,s,0,b);if(-1=c)cout=对不起,没有找到您要查找的车辆信息,请重新输入!endlendl;else cout=查找成功,该车的详细信息为:endl;cout车牌号码t车主姓名t车辆品牌endl;for(int i=0;inext;coutkeytnamettoemendl;coutnext=NULL;while(fscanf(f1,%s%s%s,p-key,p-name,p-paizi)!=EOF)/头插法建链表 if(head=NULL)l=head=p;else l-next=p;l=p;p=(Rnode*)malloc(sizeof(Rnode);p-next=NULL;p=head;while(p!=NULL)string key1=(string)p-key;string key2=key1.substr(0,2);for(j=0;j33|k0)cout=您输入的车牌号码错误,请重新选择输入!keynum0=s;s=k%10;p-keynum1=s;for(int h=0;hkey2=name2h)m=h;if(m25|m0)cout=您输入的车牌号码错误,请重新选择输入!keynum2=s;s=m%10;p-keynum3=s;for(int n=3;nkeyn-48;p-keynumn+1=c;p=p-next;flag=1;return head;void Distribute(Rnode*q,int j)Rnode*p;int i,k=0;for(i=0;inext;k=p-keynumj;if(fk=NULL)fk=p;else rk-next=p;/队尾指针向后移动一位 rk=p;rk-next=NULL;p=q;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 BinSrch(Rnode*q,long int k,int low,int high)/递归调用折半查找 int mid;if(lowhigh)return-1;else mid=(high+low)/2;if(Amid=k)return mid;-20-else if(kAmid)return(BinSrch(q,k,low,mid-1);else return(BinSrch(q,k,mid+1,high);void find(Rnode*q)Rnode*p;p=q;int k,m,c;char d8;long int s;cout请输入您要查找的车辆的汽车牌照:d;string key1=(string)d;string key2=key1.substr(0,2);for(int j=0;j33|k0)cout对不起,您输入的车牌号不合法,请重新输入!endl;s=k/10*100000000+k%10*10000000;for(int h=0;h25|m0)cout对不起,您输入的车牌号不合法,请重新输入!endl;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;c=BinSrch(q,s,0,b);if(-1=c)cout=对不起,没有找到您要查找的车辆信息,请重新输入!endlendl;else couttt车牌号码t车主姓名t车牌endl;for(int i=0;inext;coutttkeytnamettpaiziendl;coutendl;void print(Rnode*p)cout=所有车辆的信息如下:endlendl;-21-cout车牌照号t车主姓名t车牌endl;while(p!=NULL)coutkeytnamettpaizinext;cout=0;i-)Distribute(p,i);q=p=Collect();cout=完成对车辆信息的排序!keynum0*100000000+q-keynum1*10000000+q-keynum2*1000000+q-keynum3*100000+q-keynum4*10000+q-keynum5*1000+q-keynum6*100+q-keynum7*10+q-keynum8;q=q-next;b=a;a+;flag=0;return p;void menu()couttttendl;coutttt 车辆信息管理系统 endl;couttttendl;coutttt 1)添加车辆信息 endl;couttttendl;coutttt 2)按车牌号码进行排序 endl;couttttendl;coutttt 3)按车牌号码查找车辆 endl;couttttendl;coutttt 4)输出所有车辆信息 endl;couttttendl;coutttt 0)退出程序 endl;couttttendl;-22-void main()Rnode*p;int n;menu();coutn;while(n!=0)switch(n)case 1:system(cls);menu();cout文件已录入！endl;p=SetList();break;case 2:system(cls);menu();p=paixu(p);break;case 3:system(cls);menu();if(flag!=0)cout对不起，您还没有进行排序，所以现在不能进行二分查找!endl;break;else find(p);break;case 4:system(cls);menu();print(p);break;case 0:break;default:system(cls);cout=您的输入有误,请重新输入!endl;break;coutn;