航班信息的查询与检索数据结构程序设计实验报告.docx
《航班信息的查询与检索数据结构程序设计实验报告.docx》由会员分享，可在线阅读，更多相关《航班信息的查询与检索数据结构程序设计实验报告.docx（26页珍藏版）》请在冰点文库上搜索。
航班信息的查询与检索数据结构程序设计实验报告
实验报告
课程名称数据结构综合设计实验
实验项目航班信息的查询与检索
系别____计算机学院_______
专业___网络工程___
班级/学号_网工1202/2012011411___
学生姓名_______王宇涵__________
实验日期_2014年6月17日
成绩_______________________
指导教师黄改娟田英爱
1.1课程设计名称
航班信息的查询与检索
1.2课程设计目的
通过本次实验，掌握数据结构中的几种排序算法和查找算法，了解静态链表的运用，利用上述的算法完成航班信息的查询与检索。
2系统分析
2.1课程设计内容
本课程设计主要是对排序及查找等进行练习，以链式基数排序为主线，利用二分查找和顺序查找等知识，并建立静态链表，完成对航班信息的查询与检索。
我们可以利用航班的这些信息，通过其中的任意一个信息，找出我们所需要的查找的航班的所有信息，所以，我们可以采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排序好的航班记录按航班号实现快速查找，并按其他关键字的查找可以采用最简单的顺序查找方法进行。
2.2设计要求
1）提供对航班信息的排序功能
2提供对航班信息的输入输出记录功能找出我们所需要的查找的航班的所有信息
3）提供按关键字（航班号）快速查询或顺序查询功能
2.3设计分析
对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用得比较少。
每个航班记录包括八项，分别是：
航班号，起点站，终点站，班期，起飞时间，到达时间，飞机型号以及票价等。
其中航班号一项的格式为：
K0k1k2k3k4k5
航班关键字可分为两段，即字母和数字。
其中k0和k1是航空公司的别称，用两个大写字母表示，后4位为航班编号.
3概要设计
3.1系统总流程图
3.2定义数据类型
根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关的数据类型：
typedefstruct{
charstart[7];//起点
charend[7];//终点
charsche[12];//班期
chartime1[5];//起飞时间
chartime2[5];//到达时间
charmodel[4];//机型
intprice;//票价
}InfoType;//航班记录类型
typedefstruct{
KeyTypekeys[keylen];//关键字
InfoTypeothers;
intnext;
}slnode;//表结点
typedefstruct{
SLNodesl[MaxSpace];//静态链表，s1[0]为头结点
intkeylen;//关键字长
intlength;//当前表长
}SLList;//静态链表类型
为了进行基数排序，需要定义在分配和收集操作时用到的指针数组：
typedefintArrType_n[10];//十进制数字指针数组
typedefintArrType_c[26];//26个字母指针数组
3.3实现排序的各函数的说明
1）一趟分配函数：
voidDistribute（SLNode*s1,inti,ArrTypef,ArrTypee）;
//本算法是按关键字key[i]建立RADIX个子表，使同一个子表中记录的keys[i]
//相同，f[0..RADIX]和e[0..RADIX]分别指向各子表中的第一个和最后一个记录
2）一趟搜集函数：
voidCollect（SLNode*s1,inti,ArrTypef,ArrTypee）;
//本算法是按关键字keys[i]从小到大将[0..RADIX]所指的各子表依次链接成一个链表
3）链式基数排序函数：
voidRadixSort（SLList&L）;
//本算法是按关键字从低位到高位依次对各关键字进行分配和收集，分两段实现
4）二分查找函数：
intBinSearch（SLListL,KeyTypekey[]）;
//L为待查找的表，key[]为待查找的关键字，按二分查找的思想实现查找
5）主控函数
voidmain（）
{
初始化；
数据输入；
排序处理；
接受查找要求及查找关键字；
查找处理；
输出查找结果；
}
4详细设
4.1数据类型的定义
根据设计要求我们知道所用的记录中只有航班信息因此要定义相关的数据类型其源程序如下
typedefstruct
{
charstart[6];//起点
charend[6];//终点
charsche[10];//班期
chartime1[5];//起飞时间
chartime2[5];//到达时间
charmodel[4];//机型
intprice;//票价
}infotype;//航班记录类型
typedefstruct{
keytypekeys[keylen];//关键字航班号
infotypeothers;
intnext;
}slnode;//静态链表类型
typedefstruct{
slnodesl[maxspace];//静态链表
sl[0]为头结点
intkeynum;//记录当前关键字字符个数
intlength;//当前表长
}sllist;//静态链表类型
typedefintarrtype_n[radix_n];//十进制数字指针
typedefintarrtype_c[radix_c];//26个字母指针
4.2链式基数排序
否
是
4.3重新整理静态链表
重新整理静态链表，P指示第一个记录的当前位置，L.s1[1..i-1]已按关键字有序排列，第一个记录在L中的当前位置应不小于i，使用while循环，找到第i个记录，并用p指示其在L中的当前位置，而q指示尚未调整的表尾，若if（p!
=i）则p指向被移走的记录，使得以后可由while循环找回，当p=q时，p指向尚未调整的表尾，为找到第i+个记录做准备
4.4查找算法实现
4.4.1二分查找函数
否
否
是是
4.4.2顺序查找函数
voidSeqSearch（SLListL,KeyTypekey[],inti）
{intj,k,m=0;
for（j=1;j{switch（i）{
case2:
k=strcmp（key,L.s1[j].others.start）;break;
case3:
k=strcmp（key,L.s1[j].others.end）;break;
case4:
k=strcmp（key,L.s1[j].others.time1）;break;
case5:
k=strcmp（key,L.s1[j].others.time2）;break;
}
if（k==0）
{m=1;Display（L,j）;}
}
if（m==0）
printf（"无此航班信息，可能是输入错误！
\n"）;
}
4.5输入输出函数
serachcon（SLListL）
{
inti=1,k,k1;
while（i>=1&&i<=5）{
printf（"*****************************\n"）;
printf（"*航班信息查询系统*\n"）;
printf（"*1航班号*\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）;
Display（L,k）;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",k1）;SeqSearch（L,k1,i）;
break;
case5:
printf（"输入要查询的航班到达时间：
"）;
scanf（"%s",k1）;SeqSearch（L,k1,i）;
break;
case0:
printf（"再见！
\n"）;
return0;
}
}
}
voidInputData（SLList&L）
{inti=++L.length;
charyn='y';
while（yn=='y'||yn=='Y'）
{printf（"航班号起点站终点站航班期起飞时间到达时间机型票价\n"）;
scanf（"%s%s%s%s%s%s%s%d",L.s1[i].keys,L.s1[i].others.start,
L.s1[i].others.end,L.s1[i].others.sche,L.s1[i].others.time1,
L.s1[i].others.time2,L.s1[i].others.model,&L.s1[i].others.price）;
++i;
printf（"继续输入吗？
y/n:
\n"）;
scanf（"%c",&yn）;
}
L.length=i-1;
}
5运行与测试
航班信息输入如图：
按航班号查询：
输入航班号错误则显示如下图：
按航班起点站查询：
按起飞时间查询：
显示查询主菜单，退出查询系统：
6总结与心得
通过本实验，我了解了基数排序是作为一种内部排序方法，当关键字位数较少而排序序列较长时，该排序算法有一定的优越性。
而对于有序序列的查找算法，二分查找是一种效率比较高的方法。
在本实验中，对这两种算法的应用，我加深了对他们的理解，掌握了他们的实现方法。
在本次实验过程中，输入错误还是存在的问题，但能很快的通过编译解决，一些编译不能发现的问题，在组建过程中也能发现并解决。
这次实验的过程中遇到了很多问题，定义的过程中存在定义不清楚的问题，还有一些模糊定义和重定义的问题出现。
在程序的定义过程中，存在着函数的调用失败的问题，在调用过程中不能正常调用，通过把调用的函数直接用在程序中，不通过调用的方法，使得程序正常运行。
本次实验的问题只要通过调试和对整个程序的理解，便可以解决所有的发现的问题
本次实验利用二分查找法很快的完成了对航班信息的查找，使我们对二分查找有了一个很好的掌握。
其查找过程是先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
在实验过程中，程序中许多定义需要我们有一个很仔细的了解，比如上述的对字符长度的定义，这需要对所定义的对象给一个合理的字符长度，在输入的过程中才不会出现因输入的字符长度过长而不能识别。
本次实验中用到了静态链表，定义静态链表的过程中，需要有一个很熟悉的了解，知道静态链表是如何定义以及如何实现。
通过这次实验，使得对于查找以及检索有了一个很好的掌握，让我们在以后的程序设计过程中对于类似的函数定义有一个很清晰的过程以及了解。
8附录（程序源代码）
#include
#include
#defineMaxSpace100
#definekeylen7
#defineRADIX_n10
#defineRADIX_c26
typedefcharKeyType;
typedefstruct
{
charstart[6];//起点
charend[6];//终点
charsche[10];//班期
chartime1[5];//起飞时间
chartime2[5];//到达时间
charmodel[4];//机型
intprice;//票价
}InfoType;//航班记录类型
typedefstruct
{
KeyTypekeys[keylen];//关键字（航班号）
InfoTypeothers;
intnext;
}SLNode;//静态链表结点类型
typedefstruct
{
SLNodesl[MaxSpace];//静态链表，s1[0]为头结点
intkeynum;//记录当前关键字字符个数
intlength;//当前表长
}SLList;//静态链表类型
typedefintArrType_n[RADIX_n];//十进制数字指针数组
typedefintArrType_c[RADIX_c];//26个字母指针数组
//一趟数字字符分配函数
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;//将数字字符转换成相对应的数值型数字
if（!
f[j]）
f[j]=p;
else
sl[e[j]].next=p;
e[j]=p;//将p指向的结点插入到第j个子表中
}
}
//一趟数字字符的收集函数
voidCollect（SLNode*sl,inti,ArrType_nf,ArrType_ne）
{
intj,t;
for（j=0;!
f[j];j++）//找第一个非空子表
sl[0].next=f[j];//s1[0].next指向第一个非空子表中的一个结点
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;//t指向最后一个非空子表中的最后一个结点
}
//一趟字母字符分配函数
voidDistribute_c（SLNode*sl,inti,ArrType_cf,ArrType_ce）
{
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]%65;//将字母字符转换成在字母集中相应的序号（0-25）
if（!
f[j]）
f[j]=p;
else
sl[e[j]].next=p;
e[j]=p;
}
}
//一趟字母字符收集
voidCollect_c（SLNode*sl,inti,ArrType_cf,ArrType_ce）
{
intj,t;
for（j=0;!
f[j];j++）;
sl[0].next=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;
}
//链式基数排序函数
voidRadixSort（SLList&L）//链式
{
inti;
ArrType_nfn,en;
ArrType_cfc,ec;
for（i=0;iL.sl[i].next=i+1;//0号单元仅存放指针，不存储内容
L.sl[L.length].next=0;//将普通的线性表改造为静态链表
for（i=L.keynum-1;i>=2;i--）
{//按最低位优先次序对各关键字进行分配和收集，先做低4位数字部分
Distribute（L.sl,i,fn,en）;
Collect（L.sl,i,fn,en）;
}
for（i=1;i>=0;i--）
{//对高位的2位大写字母进行分配和收集
Distribute_c（L.sl,i,fc,ec）;
Collect_c（L.sl,i,fc,ec）;
}
}
//按指针链重新整理静态链表
voidArrange（SLList&L）//重新整理
{
intp,q,i;
SLNodetemp;
p=L.sl[0].next;//p指向第一个记录的当前位置
for（i=1;i{
while（pp=L.sl[p].next;//找到第i个记录，并用p指向其在L中当前位置
q=L.sl[p].next;//q指向尚未调整的表尾
if（p!
=i）
{
temp=L.sl[p];L.sl[p]=L.sl[i];L.sl[i]=temp;L.sl[i].next=p;}//交换记录
p=q;//p指向尚未调整的表尾，为找第i+1个记录做准备
}
}
//二分查找函数
intBinSearch（SLListL,KeyTypekey[]）
{
intlow,high,mid;
low=1;
high=L.length;
while（low<=high）
{
mid=（low+high）/2;
if（strcmp（key,L.sl[mid].keys）==0）
returnmid;
elseif（strcmp（key,L.sl[mid].keys）<0）
high=mid-1;
else
low=mid+1;
}
return0;
}
//顺序查找函数
voidSeqSearch（SLListL,KeyTypekey[],inti）
{
intj,k,m=0;
printf（"*************************************************************\n"）;
printf（"*航班号起点站终点站航班期起飞时间到达时间机型票价*\n"）;
for（j=1;j<=L.length;j++）
{
switch（i）
{
case2:
k=strcmp（key,L.sl[j].others.start）;break;
case3:
k=strcmp（key,L.sl[j].others.end）;break;
case4:
k=strcmp（key,L.sl[j].others.time1）;break;
case5:
k=strcmp（key,L.sl[j].others.time2）;break;
}
if（k==0）
{
m=1;
printf（"*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*\n",L.sl[j].keys,L.sl[j].others.start,L.sl
[j].others.end,L.sl[j].others.sche,L.sl[j].others.time1,L.sl[j].others.time2,L.sl
[j].others.model,L.sl[j].others.price）;
}
}
if（m==0）
printf（"*无此航班信息，可能是输入错误！
*\n"）;
printf（"*************************************************************\n"）;
}
//查询检索菜单控制程序
voidsearchcon（SLListL）
{
KeyTypekey[keylen];
inti=1,k;
while（i>=1&&i<=5）
{
printf（"********************\n"）;
printf（"*航班信息查询系统*\n"）;
printf（"********************\n"）;
printf（"*1.航班号*\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",L.sl[k].keys,L.sl[k].others.start,L.sl
[k].others.end,L.sl[k].others.sche,L.sl[k].others.time1,L.sl[k].others.time
升级会员 