数据结构课程设计航班信息查询与检索.docx
《数据结构课程设计航班信息查询与检索.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计航班信息查询与检索.docx（17页珍藏版）》请在冰点文库上搜索。
数据结构课程设计航班信息查询与检索
学院名称
《数据结构》课程设计报告
题目——航班信息查询与检索
班级：
姓名：
时间：
2012/12/29---2013/1/5
二○一二年十二月二十九日
课程设计任务书及成绩评定
课题名称
航班信息查询与检索
Ⅰ、题目的目的和要求：
1、设计目的
巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
2、设计题目要求：
问题描述:
该设计要求对飞机航班信息进行排序和查找。
可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。
任务要求:
对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。
每个航班记录包括八项，分别是：
航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表（8条记录）
航班号
起点站
终点站
班期
起飞时间
到达时间
机型
票价
CA1544
合肥
北京
1.2.4.5
1055
1240
733
960
MU5341
上海
广州
每日
1420
1615
M90
1280
CZ3869
重庆
深圳
2.4.6
0855
1035
733
1010
MU3682
桂林
南京
2.3.4.
2050
2215
M90
1380
HU1836
上海
北京
每日
0940
1120
738
1250
CZ3528
成都
厦门
1.3.4.
1510
1650
CRJ
1060
MU4594
昆明
西安
1.3.5.6
1015
1140
328
1160
SC7425
青岛
海口
1.3.6
1920
2120
DH4
1630
其中航班号一项的格式为：
K0K1K2K3K4K5
C
Z
3
8
6
9
其中K0和K1的输入值是航空公司的别称，用两个大写字母标示，后4位为航班号，这种航班号关键字可分成两段，即字母和数字。
其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。
Ⅱ、设计进度及完成情况
日期
内容
选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。
创建相关数据结构,录入源程序。
调试程序并记录调试中的问题，初步完成课程设计报告。
上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。
考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。
Ⅲ、主要参考文献及资料
[1]严蔚敏数据结构（C语言版）清华大学出版社1999
[2]严蔚敏数据结构题集（C语言版）清华大学出版社1999
[3]谭浩强C语言程序设计清华大学出版社
[4]与所用编程环境相配套的C语言或C++相关的资料
Ⅳ、成绩评定：
设计成绩：
（教师填写）
指导老师：
（签字）
二○一三年一月五日
三、概要设计………………………………………………………6
四、详细设计………………………………………………………7
1.定义数据类型…………………………………………………7
2.算法实现………………………………………………………8
五、测试数据………………………………………………………10
六、收获与体会……………………………………………………13
七、参考文献………………………………………………………13
八、附录……………………………………………………………14
一、概述
课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。
课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。
《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。
同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
本课程设计主要是对排序及查找等进行练习，以链式基数排序为主线，利用二分查找和顺序查找等知识，并建立静态链表，完成对航班信息的查询与检索。
我们可以利用航班的这些信息，通过其中的任意一个信息，找出我们所需要的查找的航班的所有信息，所以，我们可以采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排序好的航班记录按航班号实现快速查找，并按其他关键字的查找可以采用最简单的顺序查找方法进行。
二、系统分析
1设计要求
（1）提供对航班信息的排序功能
（2）提供对航班信息的输入输出记录功能找出我们所需要的查找的航班的所有信息
（3）提供按关键字（航班号）快速查询或顺序查询功能
2设计分析
对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用得比较少。
每个航班记录包括八项，分别是：
航班号，起点站，终点站，班期，起飞时间，到达时间，飞机型号以及票价等。
其中航班号一项的格式为：
K0k1k2k3k4k5
航班关键字可分为两段，即字母和数字。
其中k0和k1是航空公司的别称，用两个大写字母表示，后4位为航班编号。
三、概要设计
1、设计思路
根据题目所要求，程序必须实现航班信息的录入和查询。
程序首先定义了一个用于储存航班信息的数据类型，再由用户录入航班数据，在录入的同时并对数据进行排序，最后执行数据查询和检索。
在查询设计中，使用二分查找法对排好序的航班数据按航班号实现快速查找，按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。
2、流程图
四、详细设计
1.定义数据类型
根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关的数据类型：
[1]
typedefstruct{
charstart[6];算法实现
（1）一趟分配算法[2]
voiddistribute（slnode*sl,inti,arrtype_nf,arrtype_ne）
{
intj,p;
for（j=0;j{
f[j]=e[j]=0;
}
for（p=sl[0].next;p;p=sl[p].next）
{
j=sl[p].keys[i]%48;ext=p;
e[j]=p;ext=f[j];
t=e[j];
while（j{
for（j=j+1;jf[j];j++）;ext=f[j];
t=e[j];
}ext=0;
}
（3）链式基数排序算法[3]
voidradixsort（sllist&l）
{
inti;
arrtype_nfn,en;
arrtype_cfc,ec;
for（i=0;i<;i++）
[i].next=i+1;
[].next=0;ext;
for（i=1;i<;i++）
{
while（pp=[p].next;
q=[p].next;
if（p!
=i）
{
temp=[p];
[p]=[i];
[i]=temp;ext=p;
}
p=q;
}
}
（4）二分查找函数定义[4]
intbinsearch（sllistl,keytypekey[]）
{
intlow,high,mid;
low=1;
high=;
while（low<=high）
{
mid=（low+high）/2;
if（strcmp（key,[mid].keys）==0）
returnmid;
elseif（strcmp（key,[mid].keys）<0）
high=mid-1;
else
low=mid+1;
}
return0;
}
五、测试数据
航班信息输入如图：
按航班号查询：
输入航班号错误则显示如下图：
按航班起点站查询：
按航班起点查询：
按起飞时间查询：
显示查询主菜单，退出查询系统：
六、收获与体会
通过本实验，我了解了基数排序是作为一种内部排序方法，当关键字位数较少而排序序列较长时，该排序算法有一定的优越性。
而对于有序序列的查找算法，二分查找是一种效率比较高的方法。
在本实验中，对这两种算法的应用，我加深了对他们的理解，掌握了他们的实现方法。
在本次实验过程中，输入错误还是存在的问题，但能很快的通过编译解决，一些编译不能发现的问题，在组建过程中也能发现并解决。
这次实验的过程中遇到了很多问题，定义的过程中存在定义不清楚的问题，还有一些模糊定义和重定义的问题出现。
在程序的定义过程中，存在着函数的调用失败的问题，在调用过程中不能正常调用，通过把调用的函数直接用在程序中，不通过调用的方法，使得程序正常运行。
本次实验的问题只要通过调试和对整个程序的理解，便可以解决所有的发现的问题
本次实验利用二分查找法很快的完成了对航班信息的查找，使我们对二分查找有了一个很好的掌握。
其查找过程是先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
在实验过程中，程序中许多定义需要我们有一个很仔细的了解，比如上述的对字符长度的定义，这需要对所定义的对象给一个合理的字符长度，在输入的过程中才不会出现因输入的字符长度过长而不能识别。
本次实验中用到了静态链表，定义静态链表的过程中，需要有一个很熟悉的了解，知道静态链表是如何定义以及如何实现。
通过这次实验，使得对于查找以及检索有了一个很好的掌握，让我们在以后的程序设计过程中对于类似的函数定义有一个很清晰的过程以及了解。
七、参考文献
[1]徐孝凯，魏荣《数据结构》，机械工程出版社
[2]谭浩强《程序设计》，北京大学出版社
[3]杨路明《C语言程序设计教程》，北京邮电大学出版社.
[4]耿国华《数据结构-C语言描述》，高等教育出版社
八、附录
源程序清单：
#include<>
#include<>
#defineMaxSpace100
#definekeylen7
#defineRADIX_n10
#defineRADIX_c26
typedefcharKeyType;
typedefstruct
{
charstart[6];ext;p;p=sl[p].next）
{
j=sl[p].keys[i]%48;ext=p;
e[j]=p;ext=f[j];ext指向第一个非空子表中的一个结点
t=e[j];
while（j{
for（j=j+1;jf[j];j++）ext=f[j];t=e[j];}ext=0;ext;p;p=sl[p].next）
{
j=sl[p].keys[i]%65;ext=p;
e[j]=p;
}
}
ext=f[j];
t=e[j];
while（j{
for（j=j+1;jf[j];j++）;
if（f[j]）
{
sl[t].next=f[j];
t=e[j];
}
}
sl[t].next=0;
}
ext=i+1;ext=0;ext;ext;ext;ext=p;}eys）==0）
returnmid;
elseif（strcmp（key,[mid].keys）<0）
high=mid-1;
else
low=mid+1;
}
return0;
}
break;
case3:
k=strcmp（key,[j].;break;
case4:
k=strcmp（key,[j].;break;
case5:
k=strcmp（key,[j].;break;
}
if（k==0）
{
m=1;
printf（"*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*\n",[j].keys,[j].,
[j].,[j].,[j].,[j].,
[j].,[j].;
}
}
if（m==0）
printf（"*无此航班信息，可能是输入错误！
*\n"）;
printf（"*************************************************************\n"）;
}
班号*\n"）;
printf（"*2.起点站*\n"）;
printf（"*3.终点站*\n"）;
printf（"*4.起飞时间*\n"）;
printf（"*5.到达时间*\n"）;
printf（"*0.退出系统*\n"）;
printf（"********************\n"）;
printf（"请选择（0-5）:
\n"）;
scanf（"%d",&i）;
switch（i）
{
case1:
printf（"输入要查询的航班号（字母要大写）:
"）;
scanf（"%s",key）;
k=BinSearch（L,key）;
printf（"*************************************************************\n"）;
if（k==0）
printf（"无此航班信息，可能是输入错误！
\n"）;
else
{
printf（"*航班号起点站终点站航班期起飞时间到达时间机型票价*\n"）;
printf（"*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*\n",[k].keys,[k].,
[k].,[k].,[k].,[k].,
[k].,[k].;
}
printf（"*************************************************************\n"）;
break;
case2:
printf（"输入要查询的航班起点站名:
"）;
scanf（"%s",key）;
SeqSearch（L,key,i）;
break;
case3:
printf（"输入要查询的航班终点站名:
"）;
scanf（"%s",key）;
SeqSearch（L,key,i）;
break;
case4:
printf（"输入要查询的航班起飞时间:
"）;
scanf（"%s",key）;
SeqSearch（L,key,i）;
break;
case5:
printf（"输入要查询的航班到达时间:
"）;
scanf（"%s",key）;
SeqSearch（L,key,i）;
break;
case0:
printf（"再见\n"）;
}
}
}
eys,[i].,[i].,
[i].,[i].,[i].,[i].,&
[i].;
++i;getchar（）;
RadixSort（L）;
Arrange（L）;
printf（"继续输入吗y/n:
"）;
scanf（"%c",&yn）;
}
=i-1;
}
voidmain（）
{
//inti,k;
SLListL;
//KeyTypekey[keylen];
=6;=0;//输入航班记录
InputData（L）;//基数排序
RadixSort（L）;
Arrange（L）;
searchcon（L）;
return;
}
升级会员 