数据结构课程设计-航班信息的查询与检索.doc

目录第1章 概述2第2章 设计要求与分析22.1设计要求22.2设计分析32.2.1定义数据类型32.2.2实现排序的个函数说明4第3章 算法实现43.1 一趟分配算法43.2 一趟收集算法53.3 链式基数排序算法53.4 二分查找的函数定义6第4章 程序代码7第5章 运行与测试7第6章 实验反思10参考文献11第1章 概述排序和查找是在数据信息处理中使用频度极高的操作。为了加快查找的速度，需要先对数据记录按关键字排序。当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班次、时间、价格及机型等信息。在这个飞机航班数据的信息模型中，航班号是关键字，而且是具有结构特点的一类关键字。因为航班号是字母数字混变的，例如CZ3869，这种记录集合是一个适合与多关键字排序的例子。第2章 设计要求与分析2.1设计要求该设计要求对飞机航班信息进行排序和查找.可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他词关键字的查找可采用最简单的顺序查找方法进行，因为他们用的较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表如下表所示：航班信息表航班号起点站终点站班期起飞时间到达时间机型票价CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青岛海口1.3.619202120DH41630其中航班号一项的格式为： k0 k1 k3 k4 k5 k6C Z 3 8 6 9其中k0和k1的输入值是航空公司的别称，用两个大写字母表示，后4位为航班表号，这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串型即可。2.2设计分析2.2.1定义数据类型根据设计要求，我们知道设计中所用到的数据记录只有航班信息，因此要定义行管的数据类型：Typedef struct Char start7; Char end7;Char sche12;Char time15;Char time25;Char model4;Int price;InfoType;Typedef struct KeyType keyskeylen;InfoType others;Int next;SLNode;Typedef struct SLNode s1MaxSpace; Int keylen; Int length;SLList;为了进行基数排列，需要定义在分配和手机操作使用到的指针数组：Typedef int ArrType_n10;Typedef int ArrType_.c26;2.2.2实现排序的个函数说明（1）一趟分配函数：Void Distribute(SLNode *s1,int I,ArrType f,ArrType e);/本算法是按关键字keysi建立RADIX个子集，是同一个子集中记录的keysi相同，/f0.RADIX和e0.RADIX分别指向各自表中的第一个和最后一个记录（2）一趟搜集函数：Void Collect(SLNode *s1,int i,ArrType f,ArrType e);/本算法是按关键字keysi从小到大将0.RADIX所指的各子表一次连接成一个链表（3）链式基数排序函数：Void RadixSort(SLList &L);/本算法是按关键字从低位到高位依次对各关键字进行分配和收集，分两端实现（4）二分查找函数：Int BinSerach(SLList L,KeyType key);/L为待查找的表，key为待查找的关键字，按二分查找的思想实现查找（5）主控函数：Void main() 初始化； 数据输入； 排序处理； 接受查找要求及查找关键字； 查找处理； 输出查找结果；第3章 算法实现3.1 一趟分配算法Void Distribute(SLNode *s1,int I,ArrType f,ArrType e)Int j,p;For(j=0;jRADIX;j+)/分子表初始化为空表 Fj=0; Ej=0;For(p=s10.next;p;p=s1p.next) J=s1p.keysi%48;If(!fj) Fj=p;Else S1ej.next=p;Ej=p;3.2 一趟收集算法Void Colect(SLNode *s1,int I,ARRType f,ArrType e)Int j,t;For(j=0;!fj;j+);S10.next=fj;t=ej;While(jRSDIX-1) For(j=j+1;jRADIX-1&!fj;j+); If(fj)s1t.next=fj;t=ej;S1t.next=0;/主函数程序#include#include#define MaxSpace 100#define keylen 6#define RADIX_n 10#define RADIX_c 26#define SHOW_MSG_ERROR n错误信息：航班号须由2位大写字母和4位数字组成。n输入数据错误，程序终止执行！ntypedef char KeyType;typedef struct char start6;char end6;char sche6;char time16;char time26;char model3;int price;InfoType;typedef struct KeyType keyskeylen;InfoType others;int next;SLNode;typedef struct SLNode slMaxSpace;int keynum;int length;SLList;typedef int ArrType_nRADIX_n; typedef int ArrType_cRADIX_c;KeyType keykeylen,kl4;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);void Arrange(SLList &L);int BinSearch(SLList L, KeyType key);void SeqSearch(SLList L, KeyType key,int i);void DisplayStyle(int i, char *s);void Display(SLList L, int i);void searchcon(SLList L);void Prompt( );bool InputData(SLList &L);bool Check_HangBanHao(char *HangBanHao);void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e)int j,p; for(j=0;jRADIX_n;j+)fj=0;for(p=sl0.next; p; p=slp.next)j=slp.keysi%48; if(!fj)fj=p;elseslej.next=p;ej=p;void Collect(SLNode *sl, ArrType_n f, ArrType_n e) int j,t; for(j=0;!fj;j+);sl0.next=fj;t=ej;while(jRADIX_n-1)for(j=j+1;jRADIX_n-1 & !fj;j+);if(fj)slt.next=fj;t=ej;slt.next=0;void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e) int j,p;for(j=0;jRADIX_c;j+)fj=0;for(p=sl0.next; p!=0; p=slp.next)j=slp.keysi%65;if(!fj)fj=p;elseslej.next=p;ej=p;void Collect_c(SLNode *sl, ArrType_c f, ArrType_c e) int j,t;for(j=0;!fj; j+);sl0.next=fj;t=ej;while(jRADIX_c-1)for(j=j+1;jRADIX_c-1 & !fj;j+);if(fj) slt.next=fj;t=ej;slt.next=0;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,fn,en);for(i=1;i=0;i-)Distribute_c(L.sl,i,fc,ec);Collect_c(L.sl,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;int BinSearch(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; else low=mid+1; return 0;void SeqSearch(SLList L, KeyType key,int i) int j,k,m=0; for(j=1;j=L.length;j+) switch(i) case 2:k=strcmp(key,L.slj.others.start);break; case 3:k=strcmp(key,L.slj.others.end); break; case 4:k=strcmp(key,L.slj.others.time1);break; case 5:k=strcmp(key,L.slj.others.time2);break; if(k=0) m=1; Display(L,j); if(m=0) printf(很抱歉，无此航班信息。n);void Display(SLList L, int i)printf(航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价n);DisplayStyle(6, L.sli.keys);DisplayStyle(7, L.sli.others.start);DisplayStyle(7, L.sli.others.end);DisplayStyle(7, L.sli.others.sche);DisplayStyle(9, L.sli.others.time1);DisplayStyle(9, L.sli.others.time2);DisplayStyle(5, L.sli.others.model);printf(%6dn,L.sli.others.price);printf(n);void DisplayStyle(int i, char *s)int j;i -= strlen(s);for(j=0; j=1 & i=5)printf(n请选择命令代号(0-5): );scanf(%d, &i);switch(i)case 1: printf(输入要查询的航班号(字母要大写): ); scanf( %s, key);k=BinSearch(L, key);if(k)Display(L,k);elseprintf(很抱歉，无此航班信息。n);break;case 2: printf(输入要查询的航班起点站名: ); scanf( %s, key); SeqSearch(L, key, i);break;case 3: printf(输入要查询的航班终点站名: ); scanf(%s, key); SeqSearch(L, key, i);break;case 4: printf(输入要查询的航班起飞时间: ); scanf(%s, kl); SeqSearch(L, kl, i);break;case 5: printf(输入要查询的航班到达时间: ); scanf(%s, kl); SeqSearch(L, kl, i);break;case 0: printf(再见!n);return;Prompt( ); void Prompt( )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);bool InputData(SLList &L) int i=+L.length; char yn=y; printf(n请依次录入航班信息数据（航班号由2位大写字母和4位数字组成）:); do printf(n航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价n); scanf(%s%s%s%s%s%s%s%d, L.sli.keys, L.sli.others.start, L.sli.others.end, L.sli.others.sche, L.sli.others.time1, L.sli.others.time2, L.sli.others.model, &L.sli.others.price); fflush(stdin); if(!Check_HangBanHao(L.sli.keys) return false; +i; printf(继续输入吗? y/n:); scanf(%c,yn); while(yn=y | yn=Y); printf(n); L.length = i-1; RadixSort(L); Arrange(L); return true;bool Check_HangBanHao(char *HangBanHao)if (strlen(HangBanHao) != 6)return false;else if (HangBanHao0Z| HangBanHao1Z)return false;for(int i=2; i=5; i+)if (HangBanHaoi9)return false;return true;int main( )SLList L;L.keynum=6;L.length=0;Prompt( );if(!InputData(L)printf(SHOW_MSG_ERROR);return 1;searchcon(L);return 0;3.3 链式基数排序算法Void RadixSort(SLList &L)ArrType_n fn,en;ArrType_c fc,en;For(i=0;k=2;i-)/需分为两段完成，因为自负的那个分关键字要单独做 Distribute_n(L.s1,i,fn,en); Collect_n(L.s1,i,fn,en);For(i=1;i=0;i-) Distribute_c(L.s1,i,fc,ec);Collect_c(L.s1,i,fc,ec);/RadixSort/按指针链整理链表Void Arrange(SLList &L) p=L.s10.next;For(i=1;iL.length;i+) While(pi)p=L.s1p.next; /找到第i个记录，并用p指示其在L中的当前位置 Q=L.s1p.next; If(p!=i) Temp=L.s1p;L.s1p=L.s1i;L.s1i=temp; L.s1i.next=p; P=q; /AArrange3.4 二分查找的函数定义Int BinSearch(SLList L,KeysType key) While(low=high) Mid=(low+high)/2; If(strcmp(key,L.s1mid.keys)=0) Return mid; Else low=mid+1;Return 0;/BinSearch第4章 程序代码#include#include/* 宏定义 */#define MaxSpace 100#define keylen 6#define RADIX_n 10#define RADIX_c 26#define SHOW_MSG_ERROR n错误信息：航班号须由2位大写字母和4位数字组成。n输入数据错误，程序终止执行！ntypedef char KeyType;/* 航班记录数据结构描述 */typedef struct char start6; /起点char end6; /终点char sche6; /班期char time16; /起飞时间char time26; /到达时间char model3; /机型int price; /票价InfoType;/* 静态链表结点类型 */typedef struct KeyType keyskeylen; /关键字（航班号）InfoType others;int next;SLNode;/* 静态链表类型 */typedef struct SLNode slMaxSpace; /静态链表int keynum; /关键字字符数int length; /表长SLList;typedef int ArrType_nRADIX_n; /数字字符typedef int ArrType_cRADIX_c; /字母字符KeyType keykeylen,kl4;/* 功能函数声明 */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);void Arrange(SLList &L);int BinSearch(SLList L, KeyType key);void SeqSearch(SLList L, KeyType key,int i);void DisplayStyle(int i, char *s);void Display(SLList L, int i);void searchcon(SLList L);void Prompt( );bool InputData(SLList &L);bool Check_HangBanHao(char *HangBanHao);/* 1. 数字字符分配函数 */void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e)int j,p; for(j=0;jRADIX_n;j+)fj=0;for(p=sl0.next; p; p=slp.next)j=slp.keysi%48; /将数字字符映射为十进制数字if(!fj)fj=p;else /将p指向的结点插入到第j个子表中slej.next=p;ej=p;/* 2. 数字字符收集函数 */void Collect(SLNode *sl, ArrType_n f, ArrType_n e) int j,t; for(j=0;!fj;j+); /找第一个非空子表sl0.next=fj; /将sl0.next指向第一个非空子表的第一个结点t=ej;while(jRADIX_n-1)for(j=j+1;jRADIX_n-1 & !fj;j+); /找下一个非空子表if(fj)slt.next=fj;t=ej; /链接到主链表slt.next=0;/* 3. 字母字符分配函数 */void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e) int j,p;for(j=0;jRADIX_c;j+)fj=0;for(p=sl0.next; p!=0; p=slp.next)j=slp.keysi%65; /将字母字符映射为字母集中的相应序号if(!fj)fj=p;else /将p指向的结点插入到第j个子表中slej.next=p;ej=p;/* 4. 字母字符收集函数 */void Collect_c(SLNode *sl, ArrType_c f, ArrType_c e) int j,t;for(j=0;!fj; j+); /找第一个非空子表sl0.next=fj;t=ej; /将sl0.next指向第一个非空子表的第一个结点while(jRADIX_c-1)for(j=j+1;jRADIX_c-1 & !fj;j+); /找下一个非空子表if(fj) slt.next=fj;t=ej; /链接到主链表slt.next=0;/* 5. 链式基数排序函数 */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,fn,en);for(i=1;i=0;i-) /对高位的2位字母进行分配和收集Distribute_c(L.sl,i,fc,ec);Collect_c(L.sl,fc,ec);/* 6. 按指针链整理线性表 */void Arrange(SLList &L) int p,q,i; SLNode temp;p=L.sl0.next; /p指向第一个结点for(i=1;iL.length;i+)while(pi) /查找第i个结点，并用p指向此结点p=L.slp.next;q=L.slp.next;if(p!=i) /若第i个结点不在当前位置，交换结点数据temp=L.slp;L.slp=L.sli;L.sli=temp;L.sli.next=p;p=q; /p指向下一个未调整结点/* 7. 二分查找函数 */int BinSearch(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; else low=mid+1; return 0;/* 8.顺序查找函数 */void SeqSearch(SLList L, KeyType key,int i) int j,k,m=0; for(j=1;j=L.length;j+) switch(i) case 2:k=strcmp(key,L.slj.others.start);break; case 3:k=strcmp(key,L.slj.others.end); break; case 4:k=strcmp(key,L.slj.others.time1);break; case 5:k=strcmp(key,L.slj.others.time2);break; if(k=0) m=1; Display(L,j); if(m=0) printf(很抱歉，无此航班信息。n);/* 9. 打印班次信息函数 */void Display(SLList L, int i)printf(航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价n);DisplayStyle(6, L.sli.keys);DisplayStyle(7, L.sli.others.start);DisplayStyle(7, L.sli.others.end);DisplayStyle(7, L.sli.others.sche);DisplayStyle(9, L.sli.others.time1);DisplayStyle(9, L.sli.others.time2);DisplayStyle(5, L.sli.others.model);printf(%6dn,L.sli.others.price);printf(n);/* 10. 调整对齐格式函数 */void DisplayStyle(int i, char *s)int j;i -= strlen(s);for(j=0; j=1 & i=5)printf(n请选择命令代号(0-5): );scanf(%d, &i);switch(i)case 1: printf(输入要查询的航班号(字母要大写): ); scanf( %s, key);k=BinSearch(L, key);if(k)Display(L,k);elseprintf(很抱歉，无此航班信息。n);break;case 2: printf(输入要查询的航班起点站名: ); scanf( %s, key); SeqSearch(L, key, i);break;case 3: printf(输入要查询的航班终点站名: ); scanf(%s, key); SeqSearch(L, key, i);break;case 4: printf(输入要查询的航班起飞时间: ); scanf(%s, kl); SeqSearch(L, kl, i);break;case 5: printf(输入要查询的航班到达时间: ); scanf(%s, kl); SeqSearch(L, kl, i);break;case 0: printf(再见！n);return;Prompt( ); /循环显示主菜单/* 12. 显示主菜单 */void Prompt( )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);/* 13. 输入航班记录函数 */bool InputData(SLList &L) int i=+L.length; char yn=y; printf(n请依次录入航班信息数据（航班号由2位大写字母和4位数字组成）:); do printf(n航班号 起点站 终点