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

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

3、.510551240733960MU5341上海廣州每日14201615M901280CZ3869重慶深圳085510357331010MU3682桂林南京.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都廈門.5.715101650CRJ1060MU4594昆明西安.6101511403281160SC7425青島海口19202120DH41630其中航班號一項的格式為： k0 k1 k3 k4 k5 k6C Z 3 8 6 9其中k0和k1的輸入值是航空公司的別稱，用兩個大寫字母表示，后4位為航班表號，這種航班號關(guān)鍵字可分成兩段，即

4、字母和數(shù)字。其余七項輸入內(nèi)容因為不涉及本設(shè)計的核心，因此除了票價為數(shù)值型外，均定義為字符串型即可。2.2設(shè)計分析定義數(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 others;Int next;SLNode;Typedef struct SLNode s1M

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

6、e *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)鍵字進行分配和收集，分兩端實現(xiàn)（4）二分查找函數(shù)：Int BinSerach(SLList L,KeyType key);/L為待查找的表，key為待查找的關(guān)鍵字，按二分查找的思想實現(xiàn)查找（5）主控函數(shù)：Void main() 初始化； 數(shù)據(jù)輸入； 排序處理； 接受查找要求及查找關(guān)鍵字； 查找處理； 輸出查找結(jié)果；第3章 算法實現(xiàn)3.

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

8、-1) For(j=j+1;jRADIX-1&!fj;j+); If(fj)s1t.next=fj;t=ej;S1t.next=0;/主函數(shù)程序#include#include#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ù)錯誤，程序終止執(zhí)行！ntypedef char KeyType;typedef struct char start6;char end6;char sche6;char ti

9、me16;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_

10、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 SeqSe

11、arch(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;

12、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

13、 &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;

14、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

15、.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; retur

16、n 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; Displa

17、y(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.ot

18、hers.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);

19、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)

20、; 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.按起點站查詢 *n);printf( * 3.按終點站查詢 *n);printf( * 4.按起飛時間查詢 *n);printf( * 5.按到達時間查詢 *n);printf( * 0.退出系統(tǒng) *n);printf(*n);bool InputData(SLList

21、&L) int i=+L.length; char yn=y; printf(n請依次錄入航班信息數(shù)據(jù)（航班號由2位大寫字母和4位數(shù)字組成）:); 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); fflus

22、h(stdin); if(!Check_HangBanHao(L.sli.keys) return false; +i; printf(繼續(xù)輸入嗎? 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)ret

23、urn 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 鏈?zhǔn)交鶖?shù)排序算法Void RadixSort(SLList &L)ArrType_n fn,en;ArrType_c fc,en;For(i=0;k=2;i-)/需分為兩段完成，因為自負的那個分關(guān)鍵字要

24、單獨做 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中的當(dāng)前位置 Q=L.s1p.next; If(p!=i) Temp=L.s1p;L.s1p=L.s1i;L.s1i=

25、temp; L.s1i.next=p; P=q; /AArrange3.4 二分查找的函數(shù)定義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

26、#define SHOW_MSG_ERROR n錯誤信息：航班號須由2位大寫字母和4位數(shù)字組成。n輸入數(shù)據(jù)錯誤，程序終止執(zhí)行！ntypedef char KeyType;/* 航班記錄數(shù)據(jù)結(jié)構(gòu)描述 */typedef struct char start6; /起點char end6; /終點char sche6; /班期char time16; /起飛時間char time26; /到達時間char model3; /機型int price; /票價InfoType;/* 靜態(tài)鏈表結(jié)點類型 */typedef struct KeyType keyskeylen; /關(guān)鍵字（航班號）InfoTy

27、pe others;int next;SLNode;/* 靜態(tài)鏈表類型 */typedef struct 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(SL

28、Node *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);v

29、oid 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. 數(shù)字字符分配函數(shù) */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;

30、 p=slp.next)j=slp.keysi%48; /將數(shù)字字符映射為十進制數(shù)字if(!fj)fj=p;else /將p指向的結(jié)點插入到第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é)點t=ej;while(jRADIX_n-1)for(j=j+1;jRADIX_n-1 & !fj;j+); /找下一個非空子表if(

31、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;jRADIX_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é)點插入到第j個子表中slej.next=p;ej=p;/* 4. 字母字符收集函數(shù) */void Collec

32、t_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é)點while(jRADIX_c-1)for(j=j+1;jRADIX_c-1 & !fj;j+); /找下一個非空子表if(fj) slt.next=fj;t=ej; /鏈接到主鏈表slt.next=0;/* 5. 鏈?zhǔn)交鶖?shù)排序函數(shù) */void RadixSort(SLList &L) int i; ArrType_n fn,en; ArrType_c fc

33、,ec; for(i=0; i=2;i-) /對低四位數(shù)字部分進行分配和收集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指向第一個結(jié)點for(i=1;iL.length;i+)while(pi) /查找第i個結(jié)點，并用p指向此結(jié)點

34、p=L.slp.next;q=L.slp.next;if(p!=i) /若第i個結(jié)點不在當(dāng)前位置，交換結(jié)點數(shù)據(jù)temp=L.slp;L.slp=L.sli;L.sli=temp;L.sli.next=p;p=q; /p指向下一個未調(diào)整結(jié)點/* 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(strc

35、mp(key,L.slmid.keys)0) high=mid-1; else low=mid+1; return 0;/* 8.順序查找函數(shù) */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);bre

36、ak; case 5:k=strcmp(key,L.slj.others.time2);break; if(k=0) m=1; Display(L,j); if(m=0) printf(很抱歉，無此航班信息。n);/* 9. 打印班次信息函數(shù) */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);DisplayS

37、tyle(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. 調(diào)整對齊格式函數(shù) */void DisplayStyle(int i, char *s)int j;i -= strlen(s);for(j=0; j=1 & i=5)printf(n請選擇命令代號(0-5): );scanf(%d

38、, &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: print

39、f(輸入要查詢的航班起飛時間: ); 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( ); /循環(huán)顯示主菜單/* 12. 顯示主菜單 */void Prompt( )printf(*n);printf( * 航班信息查詢與檢索系統(tǒng) *n);printf(*n);printf( * 1.按航班號查詢 *n);printf( * 2.按起點站查詢 *n);printf( * 3.按終點站查詢 *n);printf( * 4.按起飛時間查詢 *n);printf( * 5.按到達時間查詢 *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航班號 起點站 終點站