數(shù)據(jù)結(jié)構(gòu)課程設(shè)計航班信息的查詢與檢索

1、目錄第1章 概述2第2章 設(shè)計要求與分析22.1設(shè)計要求22.2設(shè)計分析32.2.1定義數(shù)據(jù)類型32.2.2實(shí)現(xiàn)排序的個函數(shù)說明4第3章 算法實(shí)現(xiàn)43.1 一趟分配算法43.2 一趟收集算法53.3 鏈?zhǔn)交鶖?shù)排序算法53.4 二分查找的函數(shù)定義6第4章 程序代碼7第5章 運(yùn)行與測試7第6章 實(shí)驗(yàn)反思10參考文獻(xiàn)11第1章 概述排序和查找是在數(shù)據(jù)信息處理中使用頻度極高的操作。為了加快查找的速度，需要先對數(shù)據(jù)記錄按關(guān)鍵字排序。當(dāng)今乘飛機(jī)旅行的人越來越多，人們需要關(guān)心了解各類航班的班次、時間、價格及機(jī)型等信息。在這個飛機(jī)航班數(shù)據(jù)的信息模型中，航班號是關(guān)鍵字，而且是具有結(jié)構(gòu)特點(diǎn)的一類關(guān)鍵字。因?yàn)楹桨嗵?/p>

2、是字母數(shù)字混變的，例如CZ3869，這種記錄集合是一個適合與多關(guān)鍵字排序的例子。第2章 設(shè)計要求與分析2.1設(shè)計要求該設(shè)計要求對飛機(jī)航班信息進(jìn)行排序和查找.可按航班的航班號、起點(diǎn)站、到達(dá)站、起飛時間以及到達(dá)時間等信息進(jìn)行查詢。對于本設(shè)計，可采用基數(shù)排序法對一組具有結(jié)構(gòu)特點(diǎn)的飛機(jī)航班號進(jìn)行排序，利用二分查找法對排好序的航班記錄按航班號實(shí)現(xiàn)快速查找，按其他詞關(guān)鍵字的查找可采用最簡單的順序查找方法進(jìn)行，因?yàn)樗麄冇玫妮^少。每個航班記錄包括八項(xiàng)，分別是：航班號、起點(diǎn)站、終點(diǎn)站、班期、起飛時間、到達(dá)時間、飛機(jī)型號以及票價等，假設(shè)航班信息表如下表所示：航班信息表航班號起點(diǎn)站終點(diǎn)站班期起飛時間到達(dá)時間機(jī)型票價

3、CA1544合肥北京1.2.4.510551240733960MU5341上海廣州每日14201615M901280CZ3869重慶深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都廈門1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青島?？?.3.619202120DH41630其中航班號一項(xiàng)的格式為： k0 k1 k3 k4 k5 k6C Z 3 8 6 9其中k0和k1的輸入值是航空

4、公司的別稱，用兩個大寫字母表示，后4位為航班表號，這種航班號關(guān)鍵字可分成兩段，即字母和數(shù)字。其余七項(xiàng)輸入內(nèi)容因?yàn)椴簧婕氨驹O(shè)計的核心，因此除了票價為數(shù)值型外，均定義為字符串型即可。2.2設(shè)計分析2.2.1定義數(shù)據(jù)類型根據(jù)設(shè)計要求，我們知道設(shè)計中所用到的數(shù)據(jù)記錄只有航班信息，因此要定義行管的數(shù)據(jù)類型：Typedef struct Char start7; Char end7;Char sche12;Char time15;Char time25;Char model4;Int price;InfoType;Typedef struct KeyType keyskeylen;InfoType oth

5、ers;Int next;SLNode;Typedef struct SLNode s1MaxSpace; Int keylen; Int length;SLList;為了進(jìn)行基數(shù)排列，需要定義在分配和手機(jī)操作使用到的指針數(shù)組：Typedef int ArrType_n10;Typedef int ArrType_.c26;2.2.2實(shí)現(xiàn)排序的個函數(shù)說明（1）一趟分配函數(shù)：Void Distribute(SLNode *s1,int I,ArrType f,ArrType e);/本算法是按關(guān)鍵字keysi建立RADIX個子集，是同一個子集中記錄的keysi相同，/f0.RADIX和e0.RA

6、DIX分別指向各自表中的第一個和最后一個記錄（2）一趟搜集函數(shù)：Void Collect(SLNode *s1,int i,ArrType f,ArrType e);/本算法是按關(guān)鍵字keysi從小到大將0.RADIX所指的各子表一次連接成一個鏈表（3）鏈?zhǔn)交鶖?shù)排序函數(shù)：Void RadixSort(SLList &L);/本算法是按關(guān)鍵字從低位到高位依次對各關(guān)鍵字進(jìn)行分配和收集，分兩端實(shí)現(xiàn)（4）二分查找函數(shù)：Int BinSerach(SLList L,KeyType key);/L為待查找的表，key為待查找的關(guān)鍵字，按二分查找的思想實(shí)現(xiàn)查找（5）主控函數(shù)：Void main()

7、初始化； 數(shù)據(jù)輸入； 排序處理； 接受查找要求及查找關(guān)鍵字； 查找處理； 輸出查找結(jié)果；第3章 算法實(shí)現(xiàn)3.1 一趟分配算法Void Distribute(SLNode *s1,int I,ArrType f,ArrType e)Int j,p;For(j=0;j<RADIX;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,ArrTy

8、pe e)Int j,t;For(j=0;!fj;j+);S10.next=fj;t=ej;While(j<RSDIX-1) For(j=j+1;j<RADIX-1&&!fj;j+); If(fj)s1t.next=fj;t=ej;S1t.next=0;/主函數(shù)程序#include<stdio.h>#include<string.h>#define MaxSpace 100#define keylen 6#define RADIX_n 10#define RADIX_c 26#define SHOW_MSG_ERROR "n錯誤信息

9、：航班號須由2位大寫字母和4位數(shù)字組成。n輸入數(shù)據(jù)錯誤，程序終止執(zhí)行！n"typedef 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;typede

10、f 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 *

11、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(SLLis

12、t &L);bool Check_HangBanHao(char *HangBanHao);void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e)int j,p; for(j=0;j<RADIX_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

13、(j=0;!fj;j+);sl0.next=fj;t=ej;while(j<RADIX_n-1)for(j=j+1;j<RADIX_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;j<RADIX_c;j+)fj=0;for(p=sl0.next; p!=0; p=slp.next)j=slp.keysi%65;if(!fj)fj=p;e

14、lseslej.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(j<RADIX_c-1)for(j=j+1;j<RADIX_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<

15、L.length;i+)L.sli.next=i+1;L.slL.length.next=0;for(i=L.keynum-1;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;i<L.length;i+)while(p<i)p=L.slp.ne

16、xt;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;

17、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=

18、1; Display(L,j); if(m=0) printf("很抱歉，無此航班信息。n");void Display(SLList L, int i)printf("航班號 起點(diǎn)站 終點(diǎn)站 航班期 起飛時間 到達(dá)時間 機(jī)型 票價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.other

19、s.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<i; +j) printf(" ");printf("%s,", s);void searchcon(SLList L)int i

20、=1,k;while(i>=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("輸入要查詢的航班起

21、點(diǎn)站名: "); scanf(" %s", key); SeqSearch(L, key, i);break;case 3: printf("輸入要查詢的航班終點(diǎn)站名: "); scanf("%s", key); SeqSearch(L, key, i);break;case 4: printf("輸入要查詢的航班起飛時間: "); scanf("%s", kl); SeqSearch(L, kl, i);break;case 5: printf("輸入要查詢的航班到達(dá)時間:

22、 "); scanf("%s", kl); SeqSearch(L, kl, i);break;case 0: printf("再見!n");return;Prompt( ); void Prompt( )printf("*n");printf(" * 航班信息查詢與檢索系統(tǒng) *n");printf("*n");printf(" * 1.按航班號查詢 *n");printf(" * 2.按起點(diǎn)站查詢 *n");printf(" * 3.

23、按終點(diǎn)站查詢 *n");printf(" * 4.按起飛時間查詢 *n");printf(" * 5.按到達(dá)時間查詢 *n");printf(" * 0.退出系統(tǒng) *n");printf("*n");bool InputData(SLList &L) int i=+L.length; char yn='y' printf("n請依次錄入航班信息數(shù)據(jù)（航班號由2位大寫字母和4位數(shù)字組成）:"); do printf("n航班號 起點(diǎn)站 終點(diǎn)站 航班期 起

24、飛時間 到達(dá)時間 機(jī)型 票價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("繼續(xù)輸入嗎?

25、 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 (HangBanHao0<'A' | HangBanHao0>'Z'

26、;| HangBanHao1<'A' | HangBanHao1>'Z')return false;for(int i=2; i<=5; i+)if (HangBanHaoi<'0' | HangBanHaoi>'9')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);retur

27、n 0;3.3 鏈?zhǔn)交鶖?shù)排序算法Void RadixSort(SLList &L)ArrType_n fn,en;ArrType_c fc,en;For(i=0;k<L.length;i+)L.s1i.next=i+1;L.s1L.lsength.next=0;For(i=L.keynum-1;i>=2;i-)/需分為兩段完成，因?yàn)樽载?fù)的那個分關(guān)鍵字要單獨(dú)做 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(

28、L.s1,i,fc,ec);/RadixSort/按指針鏈整理鏈表Void Arrange(SLList &L) p=L.s10.next;For(i=1;i<L.length;i+) While(p<i)p=L.s1p.next; /找到第i個記錄，并用p指示其在L中的當(dāng)前位置 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 二分查找的函數(shù)定義Int BinSearch(SLList L,KeysType key) While(low<

29、=high) Mid=(low+high)/2; If(strcmp(key,L.s1mid.keys)=0) Return mid; Else low=mid+1;Return 0;/BinSearch第4章 程序代碼#include<stdio.h>#include<string.h>/* 宏定義 */#define MaxSpace 100#define keylen 6#define RADIX_n 10#define RADIX_c 26#define SHOW_MSG_ERROR "n錯誤信息：航班號須由2位大寫字母和4位數(shù)字組成。n輸入數(shù)據(jù)錯誤，

30、程序終止執(zhí)行！n"typedef char KeyType;/* 航班記錄數(shù)據(jù)結(jié)構(gòu)描述 */typedef struct char start6; /起點(diǎn)char end6; /終點(diǎn)char sche6; /班期char time16; /起飛時間char time26; /到達(dá)時間char model3; /機(jī)型int price; /票價InfoType;/* 靜態(tài)鏈表結(jié)點(diǎn)類型 */typedef struct KeyType keyskeylen; /關(guān)鍵字（航班號）InfoType others;int next;SLNode;/* 靜態(tài)鏈表類型 */typedef stru

31、ct SLNode slMaxSpace; /靜態(tài)鏈表int keynum; /關(guān)鍵字字符數(shù)int length; /表長SLList;typedef int ArrType_nRADIX_n; /數(shù)字字符typedef int ArrType_cRADIX_c; /字母字符KeyType keykeylen,kl4;/* 功能函數(shù)聲明 */void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e);void Collect(SLNode *sl, int i, ArrType_n f, ArrType_n e)

32、;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, ch

33、ar *s);void Display(SLList L, int i);void searchcon(SLList L);void Prompt( );bool InputData(SLList &L);bool Check_HangBanHao(char *HangBanHao);/* 1. 數(shù)字字符分配函數(shù) */void Distribute(SLNode *sl, int i, ArrType_n &f, ArrType_n &e)int j,p; for(j=0;j<RADIX_n;j+)fj=0;for(p=sl0.next; p; p=slp.nex

34、t)j=slp.keysi%48; /將數(shù)字字符映射為十進(jìn)制數(shù)字if(!fj)fj=p;else /將p指向的結(jié)點(diǎn)插入到第j個子表中slej.next=p;ej=p;/* 2. 數(shù)字字符收集函數(shù) */void Collect(SLNode *sl, ArrType_n f, ArrType_n e) int j,t; for(j=0;!fj;j+); /找第一個非空子表sl0.next=fj; /將sl0.next指向第一個非空子表的第一個結(jié)點(diǎn)t=ej;while(j<RADIX_n-1)for(j=j+1;j<RADIX_n-1 && !fj;j+); /找下一個

35、非空子表if(fj)slt.next=fj;t=ej; /鏈接到主鏈表slt.next=0;/* 3. 字母字符分配函數(shù) */void Distribute_c(SLNode *sl, int i, ArrType_c &f, ArrType_c &e) int j,p;for(j=0;j<RADIX_c;j+)fj=0;for(p=sl0.next; p!=0; p=slp.next)j=slp.keysi%65; /將字母字符映射為字母集中的相應(yīng)序號if(!fj)fj=p;else /將p指向的結(jié)點(diǎn)插入到第j個子表中slej.next=p;ej=p;/* 4. 字母字

36、符收集函數(shù) */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指向第一個非空子表的第一個結(jié)點(diǎn)while(j<RADIX_c-1)for(j=j+1;j<RADIX_c-1 && !fj;j+); /找下一個非空子表if(fj) slt.next=fj;t=ej; /鏈接到主鏈表slt.next=0;/* 5. 鏈?zhǔn)交鶖?shù)排序函數(shù) */void RadixSort(SLList &

37、;L) int i; ArrType_n fn,en; ArrType_c fc,ec; for(i=0; i<L.length;i+) /將線性表改造為靜態(tài)鏈表L.sli.next=i+1;L.slL.length.next=0; /"0"表示空指針 /按最低位優(yōu)先依次對各關(guān)鍵字進(jìn)行分配和收集for(i=L.keynum-1;i>=2;i-) /對低四位數(shù)字部分進(jìn)行分配和收集Distribute(L.sl,i,fn,en);Collect(L.sl,fn,en);for(i=1;i>=0;i-) /對高位的2位字母進(jìn)行分配和收集Distribute_c(

38、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指向第一個結(jié)點(diǎn)for(i=1;i<L.length;i+)while(p<i) /查找第i個結(jié)點(diǎn)，并用p指向此結(jié)點(diǎn)p=L.slp.next;q=L.slp.next;if(p!=i) /若第i個結(jié)點(diǎn)不在當(dāng)前位置，交換結(jié)點(diǎn)數(shù)據(jù)temp=L.slp;L.slp=L.sli;L.sli=temp;L.sli.next=p;p=q; /p指向下一個未調(diào)

39、整結(jié)點(diǎn)/* 7. 二分查找函數(shù) */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.順序查找函數(shù) */void SeqSearch(SLList L, KeyType k

40、ey,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("很抱歉，無

41、此航班信息。n");/* 9. 打印班次信息函數(shù) */void Display(SLList L, int i)printf("航班號 起點(diǎn)站 終點(diǎn)站 航班期 起飛時間 到達(dá)時間 機(jī)型 票價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

42、.sli.others.time2);DisplayStyle(5, L.sli.others.model);printf("%6dn",L.sli.others.price);printf("n");/* 10. 調(diào)整對齊格式函數(shù) */void DisplayStyle(int i, char *s)int j;i -= strlen(s);for(j=0; j<i; +j) printf(" ");printf("%s,", s);/* 11. 交互界面函數(shù) */void searchcon(SLList

43、 L)int i=1,k;while(i>=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("輸

44、入要查詢的航班起點(diǎn)站名: "); scanf(" %s", key); SeqSearch(L, key, i);break;case 3: printf("輸入要查詢的航班終點(diǎn)站名: "); scanf("%s", key); SeqSearch(L, key, i);break;case 4: printf("輸入要查詢的航班起飛時間: "); scanf("%s", kl); SeqSearch(L, kl, i);break;case 5: printf("輸入要查詢

45、的航班到達(dá)時間: "); scanf("%s", kl); SeqSearch(L, kl, i);break;case 0: printf("再見！n");return;Prompt( ); /循環(huán)顯示主菜單/* 12. 顯示主菜單 */void Prompt( )printf("*n");printf(" * 航班信息查詢與檢索系統(tǒng) *n");printf("*n");printf(" * 1.按航班號查詢 *n");printf(" * 2.按起點(diǎn)站

46、查詢 *n");printf(" * 3.按終點(diǎn)站查詢 *n");printf(" * 4.按起飛時間查詢 *n");printf(" * 5.按到達(dá)時間查詢 *n");printf(" * 0.退出系統(tǒng) *n");printf("*n");/* 13. 輸入航班記錄函數(shù) */bool InputData(SLList &L) int i=+L.length; char yn='y' printf("n請依次錄入航班信息數(shù)據(jù)（航班號由2位大寫字母和4位數(shù)字組成）:"); do printf("n航班號 起點(diǎn)站 終點(diǎn)站 航班期 起飛時