航班信息排序与检索.pdf-资料库

数据结构课程设计实验报告 ( 2007-- 2008 年度第 1 学期) 实验名称：程序设计题目：航班信息排序与检索院系：计算机与电子信息学院班级：2005 级网络 1 班学号：0507100411 学生姓名：王小花指导教师：陈宁江设计周数： 2 周日期：2007 年 9 月 13 日

一、实验的目的与要求： 1．实验目的：通过对航班信息查询系统的设计，熟练掌握数据结构关于基数排序与二分法查找的算法，以增深对数据结构这门专业课的了解。 2．实验要求：排序和查找是在数据信息处理中使用频度极高的操作。为了加快查找的速度，需要先对数据记录按关键字排序。当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班次、时间、价格及机型等信息。在这个飞机航班数据的信息模型中，航班号是关键字，而且是具有结构特点的一类关键字。二、需求分析：该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用得较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表（8 条记录）如下表 8 所示。 ┌────┬───┬───┬─────┬────┬────┬──┬─ │航班号 │起点站│终点站│班期 │起飞时间│到达时间│机型│票价 │ ├────┼───┼───┼─────┼────┼────┼──┼── ┤ │CA 1544 │合肥 │北京 │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.6.7 │2050 │2215 │M90 │1380│ ├────┼───┼───┼─────┼────┼────┼──┼── ┤ │HU1836 │上海 │北京 │每日 │0940 │1120 │738 │1250│ ├────┼───┼───┼─────┼────┼────┼──┼── ┤ │CZ3528 │成都 │厦门 │1.3.4.5.7 │1510 │1650 │CRJ │1060│ ├────┼───┼───┼─────┼────┼────┼──┼── ┤ │MU4594 │昆明 │西安 │1.3.5.6 │1015 │1140 │328 │1160│

├────┼───┼───┼─────┼────┼────┼──┼── ┤ │SC7425 │青岛 │海口 │1.3.6 │1920 │2120 │DH4 │1630│ └────┴───┴───┴─────┴────┴────┴──┴── ┘ 其中航班号一项的格式为： ┌─┬─┬─┬─┬─┬─┐ │C │Z │3 │8 │6 │9 │ └─┴─┴─┴─┴─┴─┘ 其中 k0 和 k1 的输入值是航空公司的别称，用两个大写字母表示，后 4 位为航班编号，这种航班号关键字可分成两段，即字母和数字。其余七项输人内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串型即可。三、概要设计： 1．根据实验要求，我们需要了解所用到的数据纪录和实现功能，并且定义相关的数据类型。数据类型定义为： typedef struct { char start[6];//起点 char end[6]; //终点 char sche[6];//班期 char time1[4];//起飞时间 char time2[4];//到达时间 }InfoType; typedef struct { int next; }SLNode; typedef struct { }SLList; typedef int ArrType_n[REDIX_n];//十进制指针数组 typedef int ArrType_c[REDIX_c];//字母指针数组 2．为了实现排序的功能，定义一系列的函数： SLNode sl[MaxSpace];//静态链表 int keynum;//纪录关键字字数 int length;//当前表长 char model[3];//机型 int price;//票价 keyType keys[keylen]; InfoType others;

void Distribute(SLNode *sl,int i,ArrType_n f,ArrType_n e)//一趟数字字符分配函数 void Collect(SLNode *sl,int i,ArrType_n f,ArrType_n e)//一趟数字字符收集 void Distribute_c(SLNode *sl,int i,ArrType_c f,ArrType_c e)//一趟字符分配函数 void Collect_c(SLNode *sl,int i,ArrType_c f,ArrType_c e)//一趟字符收集 void RadixSort(SLList &L)//链式基数排序函数 3．为了实现航班信息的输出，定义输出函数： void Display(SLList L,int i)//输出 4．为了实现航班查找，定义查找函数： int BinSearch(SLList L,keyType key[])//二分查找，用于主键查找 void SeqSearch(SLList L,keyType key[],int i)//用于其他内容查找 5．为了测试程序，定义主函数： void main(); 6．各函数间关系如下： InputData(L);//输入数据 RadixSort(L);//基数排序 searchcon(L);//查询 BinSearch( L, key)//二分查找 main SeqSearch(L, key, i)//其他查找 7．主程序模块流程图

开始输入数据信息 1.航班号 2.起点站 3.终点站 4.起飞时间 5.到达时间 6.退出系统 Y 航班号查询 N 是否为 1 是否为 2 Y 起点站查询 N Y N N 是否为 4 Y 起飞时间查询是否为 3 Y 终点站查询是否为 6 Y 退出系统 N 是否为 5 Y 到达时间查询四、详细设计：详细设计： #include #include #include #define MaxSpace 100 #define keylen 6

#define REDIX_n 10 #define REDIX_c 26 typedef char keyType; typedef struct { char start[6];//起点 char end[6]; //终点 char sche[6];//班期 char time1[4];//起飞时间 char time2[4];//到达时间 }InfoType; typedef struct { int next; }SLNode; typedef struct { }SLList; typedef int ArrType_n[REDIX_n];//十进制指针数组 typedef int ArrType_c[REDIX_c];//字母指针数组 void Display(SLList L,int i)//输出 { } void Distribute(SLNode *sl,int i,ArrType_n f,ArrType_n e)//一趟数字字符分配函数 { int j,p; for(j=0;j

e[j]=0; f[j]=p; sl[e[i]].next=p; int j,t; for(j=0;!f[j];j++) //找第一个非空子表 sl[0].next=f[j]; t=e[j]; while(j

if(f[j]) { sl[t].next=f[j];t=e[j];} int i; ArrType_n fn,en; ArrType_c fc,ec; for(i=0;i=2;i--)//按照最低位优先次序对关键字进行分配和收集， int j,t; for(j=0;!f[j];j++) sl[0].next=f[j]; t=e[j]; while(j=0;i--)//对高位的 2 个进行分配和收集 } int BinSearch(SLList L,keyType key[])//二分查找 { int low,high,mid; low=1; high=L.length; while(low<=high) { mid=(low+high)/2; { Distribute_c(L.sl,i,fc,ec); } Collect_c(L.sl,i,fc,ec); { Distribute(L.sl,i,fn,en); } Collect(L.sl,i,fn,en); if(strcmp(key,L.sl[mid].keys)==0) return mid; else if(strcmp(key,L.sl[mid].keys)<0)

资料库

航班信息排序与检索.pdf

相关推荐

课程资源

热门标签

最新资料