《数据结构课程设计报告航班信息查询与检索》由会员分享，可在线阅读，更多相关《数据结构课程设计报告航班信息查询与检索（22页珍藏版）》请在金锄头文库上搜索。
1、学院名称数据结构课程设计报告题目一一航班信息查询与检索班 级：姓 名：时 间： 2012/12/29-2013/1/5二。一二年十二月二十九日课程设计任务书及成绩评定课题名称航班信息查询与检索I、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解， 最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正 确求解过程并编写代码实现。2、设计题目要求：问题描述:该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点
2、站、 到达站、起飞时间以及到达时间等信息进行查询。任务要求:对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排 序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查 找可采用最简单的顺序查找方法进行，因此他们用得较少。每个航班记录包括八项，分 别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等， 假设航班信息表（8条记录）航班号起点站终点站班期起飞时间到达时间机型票价CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.608551035733
3、1010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青岛海口1.3.619202120DH41630其中航班号一项的格式为：K0K1K2K3 K4K5CZ3869其中K0和K1的输入值是航空公司的别称，用两个大写字母标示，后4位为航班号, 这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的 核心，因此除了票价为数值型外，均定义为字符串即可。II、设计
4、进度及完成情况日期内容12.29选取参考书，查阅有关文献资料，完成资料搜集和系统分析工 作。12.30创建相关数据结构,录入源程序。12.31调试程序并记录调试中的问题，初步完成课程设计报告。1.4上交课程设计报告打印版并进行课程设计答辩，要求每个同学 针对自己的设计回答指导教师3-4个问题。1.5考核结束后将课程设计报告和源程序的电子版父班长统一刻 光盘上交。111、主要参考文献及资料1 严蔚敏数据结构（C语言版）清华大学出版社19992 严蔚敏数据结构题集（C语言版）清华大学出版社19993 谭浩强C语言程序设计清华大学出版社4 与所用编程环境相配套的C语言或C+相关的资料IV、成绩评定：
5、设计成绩：（教师填写）指导老师：（签字）二。一三年一月五日目录一、概述6二、系统分析6三、概要设计6四、详细设计71. 定义数据类型72. 算法实现8五、测试数据10六、收获与体会13七、参考文献13/八、附录14概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课 程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所 学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门 重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选 择和应用、算法的设计及其实现等方面，加深对
6、课程基本内容的理解。同时，在程 序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。本课程设计主要是对排序及查找等进行练习，以链式基数排序为主线，利用二 分查找和顺序查找等知识，并建立静态链表，完成对航班信息的查询与检索。我们 可以利用航班的这些信息，通过其中的任意一个信息，找出我们所需要的查找的航 班的所有信息，所以，我们可以采用基数排序法对一组具有结构特点的飞机航班号 进行排序，利用二分查找法对排序好的航班记录按航班号实现快速查找，并按其他 关键字的查找可以采用最简单的顺序查找方法进行。二、系统分析1设计要求(1) 提供对航班信息的排序功能(2) 提供对航班信息的输入输
7、出记录功能找出我们所需要的查找的航班的所有信 息(3) 提供按关键字(航班号)快速查询或顺序查询功能2设计分析对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利 用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找 可采用最简单的顺序查找方法进行，因为它们用得比较少。每个航班记录包括八项，分别是：航班号，起点站，终点站，班期，起飞时间, 到达时间，飞机型号以及票价等。其中航班号一项的格式为：K0 k1 k2 k3 k4 k5CZ3869航班关键字可分为两段，即字母和数字。其中k0和k1是航空公司的别称，用两个 大写字母表示，后4位为航班编号。三、概要设计
8、1、设计思路根据题目所要求，程序必须实现航班信息的录入和查询。程序首先定义了一个 用于储存航班信息的数据类型，再由用户录入航班数据，在录入的同时并对数据进 行排序，最后执行数据查询和检索。在查询设计中，使用二分查找法对排好序的航 班数据按航班号实现快速查找，按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。2、流程/起点站终点站航班期起飞时间到达时间机型/票价/航班记录类型关键字、详细设计1 .定义数据类型根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关的数 据类型：1typedef struct char start6;char end6;char sche10;
9、char time15;char time25;char model4;int price;infotype;typedef structkeytype keyskeylen;infotype others;int next;slnode;表结点typedef struct(slnode slmaxspace;静态链表，s10为头结点int keynum;关键字长int length;当前表长sllist;静态链表类型为了进行基数排序，需要定义在分配和收集操作时用到的指针数组：typedef int arrtype_n10;十进制数字指针数组typedef int arrtype_c26;/2
10、6 个字母指针数组2 .算法实现(1) 一趟分配算法2void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e)int j,p;for(j=0;jradix_n;j +)fj=ej=0;for(p=sl0.next;p;p=slp.next) j=slp.keysi%48;将数字字符转化为对应的数值型数字if(!fj) fj=p; else slej.next=p; ej=p;将p指向的结点插入到第j个结点(2) 一趟收集算法void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)int
11、 j,t;for(j=0;!fj;j +);找第一个非空子表s10.next=fj;t=ej;while(jradix_n-1)for(j=j + 1;jradix_n-1&!fj;j +); / 找下一个非空子表 if(fj)s1t.next=fj; t=ej;slt.next=0;(3)链式基数排序算法3 void radixsort(sllist &l) int i;arrtype_n fn,en;arrtype_c fc,ec;for(i=0;i=2;i-)distribute(l.sl,i,fn,en);collect(l.sl,i,fn,en);for(i=1;i=0;i-)dis
12、tribute_c(l.sl,i,fc,ec);collect_c(l.sl,i,fc,ec);void arrange(sllist &l)int p,q,i;slnode temp;p=l.sl0.next;for(i=1;il.length;i +)while(pi)p=l.slp.next;q = l.slp.next;链接两个非空子表将普通的线性表改为静态链表按最低位优先依次对各关键字收 集按指针链表整理静态链表if(p! = i)temp=l.slp;l.slp=l.sli;l.sli=temp;交换记录l.sli.next=p;p=q;(4)二分查找函数定义4int binsea
13、rch(sllist l,keytype key)int low,high,mid;low=1;high = l.length;while(low = high)mid=(low+high)/2;if(strcmp(key,l.slmid.keys)=0) return mid;else if(strcmp(key,l.slmid.keys)0)high=mid-1;elselow=mid+1;return 0;五、测试数据航班信息输入如图:II 皆（Z 二 % V1 xi-dlow e .-cy -L4a32S.il aliiiia g% mh .曲宅。舶刘站站州站乱站 占A5W1.圳点京-*HA 终北莓广蓼深蓍蓼南薯蜀笞莹5 站溶rrrs站带r厂 猫窖雨TW.Mfflg莓l?rJw_r祈X 底瞿上n碧OTII起广禁AII必省航班期起飞时间1.2.4.5 1055螭期起切寸间J 1 47 W
