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

jk_ing-4939235-汽车牌照的排序与查找问题-数据结构与算法课程设计报告.doc.pdf-第1页.png

第1页 / 共23页

jk_ing-4939235-汽车牌照的排序与查找问题-数据结构与算法课程设计报告.doc.pdf-第2页.png

第2页 / 共23页

jk_ing-4939235-汽车牌照的排序与查找问题-数据结构与算法课程设计报告.doc.pdf-第3页.png

第3页 / 共23页

jk_ing-4939235-汽车牌照的排序与查找问题-数据结构与算法课程设计报告.doc.pdf-第4页.png

第4页 / 共23页

jk_ing-4939235-汽车牌照的排序与查找问题-数据结构与算法课程设计报告.doc.pdf-第5页.png

第5页 / 共23页

jk_ing-4939235-汽车牌照的排序与查找问题-数据结构与算法课程设计报告.doc.pdf-第6页.png

第6页 / 共23页

jk_ing-4939235-汽车牌照的排序与查找问题-数据结构与算法课程设计报告.doc.pdf-第7页.png

第7页 / 共23页

jk_ing-4939235-汽车牌照的排序与查找问题-数据结构与算法课程设计报告.doc.pdf-第8页.png

第8页 / 共23页

合肥学院计算机科学与技术系课程设计报告 2009 ～20010 学年第二学期课程数据结构与算法课程设计名称学生姓名学号专业班级指导教师汽车牌照的排序与查找问题闵晓龙 0804012025 08 计本（2）班王昆仑 20010 年 6 月

题目：汽车牌照的排序与查找问题，实现对汽车牌照按多关键字排序及快速查找。其中汽车牌照有汉字、字母和数字混合排列，例如：皖 A12345。使用基数排序方法进行排序，并在排序的基础上，利用二分查找思想实现对汽车牌照按多关键字的查找。一、问题分析和任务定义此程序要完成如下要求：选择一种数据结构来存储每个车辆的信息（如车主姓名,汽车等），在此基础上进行基数排序，而汽车牌照是由汉字、字母以及数字组成，即多关键字，其中字母和数字的比较是比较容易实现的，考虑到汉字的存储等各方面原因，对汉字的排序并不是很容易就能完成的，故不能直接对汉字排序。经过分析可知，汽车牌照中的汉字是各个省市自治区的简称，共有 34 个。这些汉字可以根据其汉语拼音的规则进行排序，然后预先存放到字符串数组中，这样每个汉字就对应着一个数组下标，只要对数组下标进行排序就可以实现对汉字的排序了。在对车牌号进行查找时，先对车牌号进行排序，然后将车牌号中的汉字及字符均转换成一个长整形数据存储在一个预先定义的一个一维数组中并把需要查找的车牌号码也转换成一个长整型数据，然后在原先的一维数组中使用二分查找来查找该车牌号码对应的车辆信息。二、数据结构的选择和概要设计 1、数据结构的选择：程序要求实现对汽车牌照的排序与查找，而如果仅仅进行牌照的排序与查找，则显得程序没有太大的实用性，所以考虑在程序中加入例如车主的姓名以及车子的品牌等内容来增加程序的实用性。为了能够更好的完成这些功能，在这里选用链表来存储所有车辆的信息，用链表中的单个节点来存储一辆汽车的信息，而对应的各个节点的域中则存储其对应的车辆信息（如车牌号码、车主姓名、车的品牌等信息）。在存储汽车牌照中的汉字时，由于汉字在内存中占用两个字节，需要使用字符串数据来存储。其中的 26 个字母则使用一个一维字符数组来存储。车主的姓名及车子的品牌则使用一维字符数组来存储。在基数排序时，每趟的数据收集由两个链队列来完成，链队列的个数为基数的个数，两个链队列的队列指针分别指向每组链队列的队头和队尾。 2、概要设计为了实现上述功能，需要使用一下函数： main()：主函数 Setlist()：添加车辆函数 Distribute()：进行基数排序每一趟的分配函数 Collect()：进行基数排序每一趟的收集函数 find()：二分查找函数 menu()：菜单函数 print()：输出所有车辆信息函数 insort()：基数排序函数 - 1 -

main() menu() Setlist() insort() find() print() Distribute() Collect() N N N N 图 1 各函数间关系如下：开始输入 n n=1 Y 调用子函数 SetList(p) n=p Y 调用子函数 paixu(p) n=c Y 调用子函数 find(p) n=s Y 调用子函数 print() n=q 结果 Y 图 2 主函数 main()流程图 - 2 - N

开始申请一结点 p 并为其分配内存空间 head=NULL Y head=p N 输入汽车的相应信息，经过相应的处理后存入结点 p 相应的域。将该结点按尾插法插入到链表的相应位置返回该链表的头指针结束图 3 添加车辆函数 SetList(p)流程图开始 i=M-1 i>=0 Y 调用 Distribute 及 Collect N 函数 i++ 遍历排序好的链表将每个车辆的牌照号转换为长整型数据存于一个一维数组 A[MAX]中。结束图 4 排序子函数 paixu(p)的流程图 - 3 -

开始输入需要查找的牌照将待查找的牌照号处理后存于一整型变量中调用二分查找函数并返 Y 没有查找成功回 c c=-1 结束 N 查找成功并输出该车的信息图 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; p=(Rnode *)malloc(sizeof(Rnode)); p->next=NULL; while(fscanf(f1,"%s%s%s",p->key,p->name,p->paizi)!=EOF) { if(head==NULL) { - 4 -

} else{ l=head=p; 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）可以看出，这组关键字与以前说过的用来排序的关键字并无差别，且也是针对但关键字对一组记录进行排序。但在基数排序中，我们可以将单关键字看成由若干个关键字复合而成。上述这组关键字的值都在 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） 930 k2=0 k2=1 k2=2 083 063 k2=3 184 k2=4 505 k2=5 k2=6 k2=7 008 278 k2=8 269 589 109 k2=9 （a）、按个位数大小将元素分成 10 组 - 5 -

一趟分配后的一组元素（930，063，083，184，505，278，008，109，589，269） 109 008 505 K1=0 k1=1 k1=2 930 k1=3 k1=4 k1=5 269 063 k1=6 278 k1=7 589 184 083 k1=8 k1=9 （b）、按十位数大小将元素分成 10 组二趟收集后的元素序列（505，008，109，930，063，269，278，083，184，589） 083 063 008 K0=0 184 109 k0=1 278 269 k0=3 k0=4 589 505 k0=5 k0=2 k0=6 k0=7 k0=8 930 k0=9 （c）、按百位数大小将元素分成 10 组三趟收集后的元素序列（008，063，084，109，184，269，278，505，589，930） 3、链式基数排序算法实现的技术要点：要实现上述基数排序的过程，需要解决 3 个问题。问题一：如何描述由待排序关键字分成的若干个子关键字？问题二：每次分配记录所形成的各组序列以何种结构存储？问题三：如何收集各组记录？其实，当问题三得以解决后，问题二也就解决了；因为问题三运算方式决定了问题二的存储结构。由上例可以看出，各组记录的收集是本着“先进入该组的记录将首先被收集”的原则。这与队列的“先进先出”的原则相一致。这样，各组序列就以队列来描述。因为要进行多次的分配与收集，为节省存储空间及运算方便，我们采用链队列来存储各组序列。其实，当问题三得以解决后，问题二也就解决了；因为问题三运算方式决定了问题二的存储结构。链队列的数量与基数一致，若基数为 RAX，则令 f[0]～f[RAX-1]分别指向 RAX 个链队列的队头节点，令 r[0]～r[RAX-1]分别指向 RAX 个队列的队尾节点。每次分配前，将 RAX 个链队列置空： for(i=0i<=RAX-1++i) f[i=r[i]=NULL；对各链队列所表示的序列进行收集时，应从链队列 f[0]开始，当链队列 f[j+1]不为 NULL 时，将链队列 f[j]与其首尾相接： i=0； - 6 -

while(f[i]==NULL) i++； //查找第一个不空的链队列 for(j=i，k=i+1；k<= RAX-1；++k) if( f[k]!= NULL) { r[j]->next = f[k]；j=k；} 对于问题一，一个简单的方法是，在存储待排序记录时，就将关键字按分成子关键字来存储。为了运算方便，我们采用与链队列中节点一致的节点结构，以单链表来存储待排序的一组记录及收集后的记录序列。节点的类型可以定义为： #define M 3 typedef struct node{ //M 为待排记录中子关键字的个数 keytype struct node key[M]； *next； } Rnode；若关键字为整型数据，则存放待排序记录的单链表可以这样构造： //N 为待排记录的个数 8 N #define Rnode *L，*p； L = NULL； //链表 L 初始化为空 for(i = 1；i<=N；++i){ //头插法建单链表 L p = malloc(sizeof(Rnode))； for (j = 0；j<= M-1；++j) //分别输入 M 个子关键字 scanf(“%d”，&(p->key[j]))； p->next = L；L = p； } 综上所述，以链表来存储待排序记录，基数排序算法如下： //M 为待排记录中子关键字的个数 3 M #define #define RAX 10 typedef struct node{ // RAX 为基数 keytype key[M]； struct node *next； }Rnode； Rnode *f[RAX]，*r[RAX]； Rnode *SetList(){ //建待排序记录组成的单链表 L Rnode *L，*p； int i，j； L=NULL； for (i=1；i<=n；++i){ //链表 L 初始化为空 //头插法建单链表 L，n 为待排序记录个数 p=(Rnode *)malloc(sizeof(Rnode))； for (j=0；j<=M-1；++j) scanf("%d"，&(p->key[j]))； //分别输入 M 个子关键字 p->next=L；L=p； } return L； } - 7 -

资料库

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

相关推荐

课程资源

热门标签

最新资料