数据结构与算法课程设计报告计算机学院软件工程摘要3第一章绪论41.1课程设计选题41.1.1选题描述41.1.2选题要求4第二章系统需求分析42.1输入/输出形式和输出值42.2功能需求42.3数据流图52.4 用户特点52.4 假定和约束5第三章概要设计53.1设计思想53.2基本设计概念和处理流程63.3存储结构设计8第四章详细设计94.1程序设计说明94.2算法设计与分析94.2.1基数排序：94.2.2二分查找94.3算法实现104.4函数说明10第五章测试115.1核心算法复杂性分析115.2测试数据及结果11第六章总结11摘要本课程设计目的在于检验数据结构及算法设计与分析两门课程的学习成果，从而加深对所学的知识的进一步理解与巩固。本次课程设计过程中本人主要根据课本中的理论与算法编写程序，体现以课本知识的应用为主，在学习了数据结构的基础上，以能够更加熟练的应用所学知识，并能结合一些著名算法来实现对一些实际问题的应用，从而更为深刻理解数据结构与算法的内涵。本次课程设计利用C+语言编写程序，实现对飞机航班信息进行排序和查找。第一章 绪论随着信息产业的飞速发展，信息化管理及查询已经引入并应用到各行各业，影响着人们的价值观念与生活方式。因此，要提升企业竞争力，就要大力推进企业信息化建设，利用先进的办公自动化系统来实现企业内部信息管理、共享及交流，从而提高企业综合实力。1.1课程设计选题1.1.1选题描述该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、终点站、起飞时间以及到达时间等信息进行查询。1.1.2选题要求（1）每个航班记录包括8项，分别是：航班号、起点站、终点站、航班期、起飞时间、到达时间、机型以及票价，如下给出一个航班记录的例子： 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价CA1544 合肥 北京 1.2.4.5 1055 1240 M90 960（2）从键盘输入各记录。（3）采用基数排序方法对飞机航班号进行排序，然后利用二分查找的方法对排好序的航班记录按航班号实现快速查找。（4）按其它次关键字的查找可采用最简单的顺序查找方法进行，因为它们用得较少。第二章 系统需求分析2.1输入/输出形式和输出值进入系统后，首先提示输入航班信息，包括：航班号、起点站、终点站、航班期、起飞时间、到达时间、票价。除票价为整型外，其他均为字符型。每个信息以回车键输入。当输入完一个航班信息后，会提示是否继续输入，若要继续输入则重复上述步骤，否则显示主菜单。根据主菜单输入功能序号，若用户输入的值超过给定范围，则提示错误并要求重新输入。2.2功能需求（1）输入航班信息（2）按不同类型查询航班信息：输入航班号，显示相应信息；输入起点站，显示相应信息；输入终点站，显示相应信息；输入起飞时间，显示相应信息；输入到达时间，显示相应信息；（3）退出系统2.3数据流图2.4 用户特点本系统的最终用户是航空公司，操作人员只需具备基本的计算机操作技巧即可。2.4 假定和约束本系统在开发过程中，由于技术原因可能会影响到系统的某方面，如有错误或未实现的功能，可以另选其他可行方案。第三章 概要设计3.1设计思想对航班信息实现基数排序，利用折半查找（二分查找）的方法根据航班号实现查询，利用顺序查找的方法对根据其他信息实现查询。3.2基本设计概念和处理流程3.3存储结构设计本系统采用链式存储的存储结构，分别定义三个结构体。 typedef struct /定义航班信息的结构体,静态链表类型char terminal6; /定义起点站char end6; /定义终点站char flightNo10; /定义航班期char startTime5; /定义起飞时间char endTime5; /定义到达时间char type10; /定义机型int price; /定义票价infotype;typedef structkeytype keyskeylen; /航班号，动态链表infotype others;int next;slnode;typedef struct/定义存储信息的结构体slnode slMAX;int keynum; /信息数量，最大表长int length; /信息长度，当前表长sllist; /顺序表类型第四章 详细设计4.1程序设计说明1、利用起点站、终点站、起飞时间、到达时间为关键字来查询航班信息。该查找算法使用最简单的顺序查找方法进行。即按照航班信息的结构体数组依次与被查找信息作比较，若找到，则输出结果即可。若没找到，则输出相关提示信息。2、利用航班号作为关键字进行查询由于设计内容要求使用基数排序对这组航班信息进行排序，并利用二分查找法对排好序的航班记录按航班号实现快速查找，因此次算法设计需包括基数排序和二分查找。4.2算法设计与分析4.2.1基数排序：基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法，其是通过“分配”和“收集”两种操作对相应关键字进行排序。算法思路是按照排序关键字的每一位字符进行排序。排序前，先定义一个队列数组，每个队列数组与某个关键字位对应，某队列中只能存放与该关键字位对应的元素。首先先从关键字的最后一位字符进行判断，根据关键字位，把这个元素放入相应的队列中去，这就是“分配”过程。等到所有元素均被分配到相应队列中之后，在把各个队列中的元素，按照队列数组顺序，依次重新放回原元素数组中，这就是“收集”过程。经过“分配”和“收集”后，一次排序完成。接着再以关键字的倒数第二位字符作为关键字位进行上述排序过程，直到按照关键字的所有位全部进行排序过后，整个序列就成为有序序列，排序完成。4.2.2二分查找二分查找是对有序序列进行快速查找的一种有效方法。它的基本思想是，每次都与这个有序序列的中间元素进行比较，若找到，则输出元素信息，若没找到，则判断这个中间元素比待查找的元素大还是小，如果大，那么查找工作继续在该有序序列的前半段进行；反之，则继续查找该有序序列的后半段。如此一直查找，直到找到该元素或者查找到只剩下一个元素而这个元素与待查找元素不相符时，查找结束。前一种情况找到了待查找元素，输出该元素，后一种没有找到，输出相应提示信息。4.3算法实现1、顺序查找对于根据起点站、终点站、航班期、起飞时间、到达时间来进行航班查找的函数，只需将这个查找关键字与结构体数组中相应的键值进行比较，因为每个关键字查找不一定是唯一的，所以如果想要查找到所有的相关信息，则必须将结构体查找到底。当找到相应航班信息时，只要将其输出即可。2、基数排序最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。3、二分查找设置标志位left，right，mid。其中left表示查找序列的左端第一个元素下标，right表示查找序列的右端第一个元素下标。mid等于（left+right）/2。函数使用while循环，循环条件是left=right。在循环体内，首先判断待查找信息的航班号是否与以mid为下标的数组内指针所指向的结构体变量一致，若一致，则输出该航班信息，若比该结构体变量小，则令rihgt=mid-1，继续进入下一轮循环，若比较大，则令left=mid+1，继续循环。这样查找到最后，若找到，则会输出相应航班信息，若没有找到，需要输出提示信息。4、主函数在主函数中，依然是以while循环的方式列出该程序的操作清单。该程序的菜单是请用户选择以什么作为查找关键字来查找航班信息。查找菜单如下：1.航班号，2.起点站，3.终点站，4.起飞时间，5.到达时间，0.退出。选择不同菜单项，将会提示不同信息让用户输入，然后程序根据各自的查找方法进行查找。4.4函数说明（1）一趟数字字符分配函数void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e)（2）一趟数字字符收集函数void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)（3）一趟字母字符分配函数void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)（4）一趟字母字符收集函数void collect_c(slnode *sl,int i,arrtype_c f,arrtype_c e)（5）链式基数排序函数void radixsort(sllist &l)（6）按指针链重新整理静态链表void arrange(sllist &l)（7）二分查找函数int binsearch(sllist l,keytype key)（8）顺序查找函数void seqsearch(sllist l,keytype key,int i)（9）查询检索菜单void searchcon(sllist l)（10）录入航班数据函数void inputdata(sllist &l)（11）主函数void main()第五章 测试5.1核心算法复杂性分析（1）基数排序复杂性分析设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix)，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(n)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。（2）折半查找复杂性分析问题规模为n，其算法复杂度为o（log（n）5.2测试数据及结果略第六章 总结本设计的重点和难点在于对航班数据的排序和查找，以链式基数排序为主，用到了二分查找和顺序查找、建立静态链表等知识。通过本次课程设计，使我对数据结构和算法设计有了新的认识，能够独立分析问题，选择所需的数据结构，仔细分析算法。