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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)航班信息的查詢與檢索數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)航班信息的查詢與檢索數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)航班信息的查詢與檢索資料僅供參考文件編號(hào)：2022年4月數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)航班信息的查詢與檢索版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：目錄第1章概述 2第2章設(shè)計(jì)要求與分析 2設(shè)計(jì)要求 2設(shè)計(jì)分析 3定義數(shù)據(jù)類型 3實(shí)現(xiàn)排序的個(gè)函數(shù)說(shuō)明 4第3章算法實(shí)現(xiàn) 4一趟分配算法 4一趟收集算法 5鏈?zhǔn)交鶖?shù)排序算法 5二分查找的函數(shù)定義 6第4章程序代碼 7第5章運(yùn)行與測(cè)試 7第6章實(shí)驗(yàn)反思 10參考文獻(xiàn) 11第1章概述排序和查找是在數(shù)據(jù)信息處理中使用頻度極高的操作。為了加快查找的速度，需要先對(duì)數(shù)據(jù)記錄按關(guān)鍵字排序。當(dāng)今乘飛機(jī)旅行的人越來(lái)越多，人們需要關(guān)心了解各類航班的班次、時(shí)間、價(jià)格及機(jī)型等信息。在這個(gè)飛機(jī)航班數(shù)據(jù)的信息模型中，航班號(hào)是關(guān)鍵字，而且是具有結(jié)構(gòu)特點(diǎn)的一類關(guān)鍵字。因?yàn)楹桨嗵?hào)是字母數(shù)字混變的，例如CZ3869，這種記錄集合是一個(gè)適合與多關(guān)鍵字排序的例子。第2章設(shè)計(jì)要求與分析設(shè)計(jì)要求該設(shè)計(jì)要求對(duì)飛機(jī)航班信息進(jìn)行排序和查找.可按航班的航班號(hào)、起點(diǎn)站、到達(dá)站、起飛時(shí)間以及到達(dá)時(shí)間等信息進(jìn)行查詢。對(duì)于本設(shè)計(jì)，可采用基數(shù)排序法對(duì)一組具有結(jié)構(gòu)特點(diǎn)的飛機(jī)航班號(hào)進(jìn)行排序，利用二分查找法對(duì)排好序的航班記錄按航班號(hào)實(shí)現(xiàn)快速查找，按其他詞關(guān)鍵字的查找可采用最簡(jiǎn)單的順序查找方法進(jìn)行，因?yàn)樗麄冇玫妮^少。每個(gè)航班記錄包括八項(xiàng)，分別是：航班號(hào)、起點(diǎn)站、終點(diǎn)站、班期、起飛時(shí)間、到達(dá)時(shí)間、飛機(jī)型號(hào)以及票價(jià)等，假設(shè)航班信息表如下表所示：航班信息表航班號(hào)起點(diǎn)站終點(diǎn)站班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)CA1544合肥北京上海廣州每日14201615M901280CZ3869重慶深圳桂林南京上海北京每日094011207381250CZ3528成都廈門(mén)昆明西安青島?？谄渲泻桨嗵?hào)一項(xiàng)的格式為：k0k1k3k4k5k6CZ3869其中k0和k1的輸入值是航空公司的別稱，用兩個(gè)大寫(xiě)字母表示，后4位為航班表號(hào)，這種航班號(hào)關(guān)鍵字可分成兩段，即字母和數(shù)字。其余七項(xiàng)輸入內(nèi)容因?yàn)椴簧婕氨驹O(shè)計(jì)的核心，因此除了票價(jià)為數(shù)值型外，均定義為字符串型即可。設(shè)計(jì)分析定義數(shù)據(jù)類型根據(jù)設(shè)計(jì)要求，我們知道設(shè)計(jì)中所用到的數(shù)據(jù)記錄只有航班信息，因此要定義行管的數(shù)據(jù)類型：Typedefstruct{Charstart[7];Charend[7];Charsche[12];Chartime1[5];Chartime2[5];Charmodel[4];Intprice;}InfoType;Typedefstruct{KeyTypekeys[keylen];InfoTypeothers;Intnext;}SLNode;Typedefstruct{SLNodes1[MaxSpace];Intkeylen;Intlength;}SLList;為了進(jìn)行基數(shù)排列，需要定義在分配和手機(jī)操作使用到的指針數(shù)組：TypedefintArrType_n[10];Typedefint[26];實(shí)現(xiàn)排序的個(gè)函數(shù)說(shuō)明（1）一趟分配函數(shù)：VoidDistribute(SLNode*s1,intI,ArrTypef,ArrTypee);RADIX]和e[0..RADIX]分別指向各自表中的第一個(gè)和最后一個(gè)記錄（2）一趟搜集函數(shù)：VoidCollect(SLNode*s1,inti,ArrTypef,ArrTypee);RADIX]所指的各子表一次連接成一個(gè)鏈表（3）鏈?zhǔn)交鶖?shù)排序函數(shù)：VoidRadixSort(SLList&L);ext;p;p=s1[p].next){J=s1[p].keys[i]%48;If(!f[j])F[j]=p;ElseS1[e[j]].next=p;E[j]=p;}}一趟收集算法VoidColect(SLNode*s1,intI,ARRTypef,ArrTypee){Intj,t;For(j=0;!f[j];j++);S1[0].next=f[j];t=e[j];While(j<RSDIX-1){For(j=j+1;j<RADIX-1&&!f[j];j++);If(f[j]){s1[t].next=f[j];t=e[j];}}S1[t].next=0;}ext;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; }}voidCollect(SLNode*sl,ArrType_nf,ArrType_ne){ intj,t;for(j=0;!f[j];j++); sl[0].next=f[j]; t=e[j]; while(j<RADIX_n-1) { for(j=j+1;j<RADIX_n-1&&!f[j];j++); if(f[j]) { sl[t].next=f[j];t=e[j]; } } sl[t].next=0;}voidDistribute_c(SLNode*sl,inti,ArrType_c&f,ArrType_c&e){ intj,p; for(j=0;j<RADIX_c;j++) f[j]=0; for(p=sl[0].next;p!=0;p=sl[p].next) { j=sl[p].keys[i]%65; if(!f[j]) f[j]=p; else sl[e[j]].next=p; e[j]=p; }}voidCollect_c(SLNode*sl,ArrType_cf,ArrType_ce){ intj,t; for(j=0;!f[j];j++); sl[0].next=f[j];t=e[j]; while(j<RADIX_c-1) { for(j=j+1;j<RADIX_c-1&&!f[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;i<;i++) [i].next=i+1; [].next=0; for(i=;i>=2;i--) { Distribute,i,fn,en); Collect,fn,en); } for(i=1;i>=0;i--) { Distribute_c,i,fc,ec); Collect_c,fc,ec); }}voidArrange(SLList&L){ intp,q,i;SLNodetemp; p=[0].next; for(i=1;i<;i++) { while(p<i) p=[p].next; q=[p].next; if(p!=i) { temp=[p];[p]=[i];[i]=temp; [i].next=p; } p=q; }}intBinSearch(SLListL,KeyTypekey[]){intlow,high,mid;low=1;high=; while(low<=high){ mid=(low+high)/2; if(strcmp(key,[mid].keys)==0) returnmid; elseif(strcmp(key,[mid].keys)<0) high=mid-1; elselow=mid+1; } return0;}voidSeqSearch(SLListL,KeyTypekey[],inti){intj,k,m=0;for(j=1;j<=;j++){ switch(i){ case2:k=strcmp(key,[j].;break; case3:k=strcmp(key,[j].;break; case4:k=strcmp(key,[j].;break;case5:k=strcmp(key,[j].;break; } if(k==0) { m=1; Display(L,j); }}if(m==0) printf("很抱歉，無(wú)此航班信息。\n");}voidDisplay(SLListL,inti){ printf("航班號(hào)起點(diǎn)站終點(diǎn)站航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)\n"); DisplayStyle(6,[i].keys);DisplayStyle(7,[i].; DisplayStyle(7,[i].;DisplayStyle(7,[i].; DisplayStyle(9,[i].;DisplayStyle(9,[i].; DisplayStyle(5,[i].;printf("%6d\n",[i].; printf("\n");}voidDisplayStyle(inti,char*s){ intj; i-=strlen(s); for(j=0;j<i;++j)printf(""); printf("%s,",s);}voidsearchcon(SLListL){ inti=1,k; while(i>=1&&i<=5){ printf("\n請(qǐng)選擇命令代號(hào)(05):"); scanf("%d",&i); switch(i){ case1:printf("輸入要查詢的航班號(hào)(字母要大寫(xiě)):"); scanf("%s",key);k=BinSearch(L,key); if(k) Display(L,k); else printf("很抱歉，無(wú)此航班信息。\n"); break; case2:printf("輸入要查詢的航班起點(diǎn)站名:"); scanf("%s",key);SeqSearch(L,key,i); break; case3:printf("輸入要查詢的航班終點(diǎn)站名:"); scanf("%s",key);SeqSearch(L,key,i); break; case4:printf("輸入要查詢的航班起飛時(shí)間:"); scanf("%s",kl);SeqSearch(L,kl,i); break; case5:printf("輸入要查詢的航班到達(dá)時(shí)間:"); scanf("%s",kl);SeqSearch(L,kl,i); break; case0:printf("再見(jiàn)!\n"); return; } Prompt(); }}voidPrompt(){ printf("***************************************************\n"); printf("*航班信息查詢與檢索系統(tǒng)*\n"); printf("***************************************************\n"); printf("*1.按航班號(hào)查詢*\n"); printf("*2.按起點(diǎn)站查詢*\n"); printf("*3.按終點(diǎn)站查詢*\n"); printf("*4.按起飛時(shí)間查詢*\n"); printf("*5.按到達(dá)時(shí)間查詢*\n"); printf("*0.退出系統(tǒng)*\n"); printf("***************************************************\n");}boolInputData(SLList&L){ inti=++; charyn='y'; printf("\n請(qǐng)依次錄入航班信息數(shù)據(jù)（航班號(hào)由2位大寫(xiě)字母和4位數(shù)字組成）:"); do { printf("\n航班號(hào)起點(diǎn)站終點(diǎn)站航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)\n"); scanf("%s%s%s%s%s%s%s%d",[i].keys,[i]., [i].,[i].,[i]., [i].,[i].,&[i].; fflush(stdin); if(!Check_HangBanHao[i].keys)) returnfalse; ++i; printf("繼續(xù)輸入嗎y/n:"); scanf("%c",yn); } while(yn=='y'||yn=='Y'); printf("\n"); =i-1; RadixSort(L); Arrange(L); returntrue;}boolCheck_HangBanHao(char*HangBanHao){ if(strlen(HangBanHao)!=6) returnfalse; elseif(HangBanHao[0]<'A'||HangBanHao[0]>'Z' ||HangBanHao[1]<'A'||HangBanHao[1]>'Z') returnfalse; for(inti=2;i<=5;i++) { if(HangBanHao[i]<'0'||HangBanHao[i]>'9') returnfalse; } returntrue;}intmain(){ SLListL; =6;=0; Prompt(); if(!InputData(L)) { printf(SHOW_MSG_ERROR); return1; } searchcon(L); return0;}鏈?zhǔn)交鶖?shù)排序算法VoidRadixSort(SLList&L){ArrType_nfn,en;ArrType_cfc,en;For(i=0;k<;i++)[i].next=i+1;[].next=0;For(i=;i>=2;i--){ext;For(i=1;i<;i++){While(p<i)p=[p].next;ext;If(p!=i){Temp=[p];[p]=[i];[i]=temp;[i].next=p;}P=q;}}eys)==0)Returnmid;Elselow=mid+1;}Return0;}數(shù)字字符分配函數(shù)*/voidDistribute(SLNode*sl,inti,ArrType_n&f,ArrType_n&e){ intj,p;for(j=0;j<RADIX_n;j++) f[j]=0; for(p=sl[0].next;p;p=sl[p].next) { j=sl[p].keys[i]%48;ext=p; e[j]=p; }}/*2.數(shù)字字符收集函數(shù)*/voidCollect(SLNode*sl,ArrType_nf,ArrType_ne){ intj,t;for(j=0;!f[j];j++); ext=f[j]; ext指向第一個(gè)非空子表的第一個(gè)結(jié)點(diǎn) t=e[j]; while(j<RADIX_n-1) { for(j=j+1;j<RADIX_n-1&&!f[j];j++); ext=f[j];t=e[j]; ext=0;}/*3.字母字符分配函數(shù)*/voidDistribute_c(SLNode*sl,inti,ArrType_c&f,ArrType_c&e){ intj,p; for(j=0;j<RADIX_c;j++) f[j]=0; for(p=sl[0].next;p!=0;p=sl[p].next) { j=sl[p].keys[i]%65; ext=p; e[j]=p; }}/*4.字母字符收集函數(shù)*/voidCollect_c(SLNode*sl,ArrType_cf,ArrType_ce){ intj,t; for(j=0;!f[j];j++); ext=f[j];t=e[j]; ext指向第一個(gè)非空子表的第一個(gè)結(jié)點(diǎn) while(j<RADIX_c-1) { for(j=j+1;j<RADIX_c-1&&!f[j];j++); ext=f[j];t=e[j]; ext=0;}/*5.鏈?zhǔn)交鶖?shù)排序函數(shù)*/voidRadixSort(SLList&L){ inti;ArrType_nfn,en;ArrType_cfc,ec;for(i=0;i<;i++) ext=i+1; [].next=0; 按指針鏈整理線性表*/voidArrange(SLList&L){ intp,q,i;SLNodetemp; p=[0].next; ext; q=[p].next; if(p!=i) ext=p; } p=q; 二分查找函數(shù)*/intBinSearch(SLListL,KeyTypekey[]){intlow,high,mid;low=1;high=; while(low<=high){ mid=(low+high)/2; if(strcmp(key,[mid].keys)==0) returnmid; elseif(strcmp(key,[mid].keys)<0) high=mid-1; elselow=mid+1; } return0;}/*8.順序查找函數(shù)*/voidSeqSearch(SLListL,KeyTypekey[],inti){intj,k,m=0;for(j=1;j<=;j++){ switch(i){ case2:k=strcmp(key,[j].;break; case3:k=strcmp(key,[j].;break; case4:k=strcmp(key,[j].;break;case5:k=strcmp(key,[j].;break; } if(k==0) { m=1; Display(L,j); }}if(m==0) printf("很抱歉，無(wú)此航班信息。\n");}/*9.打印班次信息函數(shù)*/voidDisplay(SLListL,inti){ printf("航班號(hào)起點(diǎn)站終點(diǎn)站航班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)\n"); DisplayStyle(6,[i].keys);DisplayStyle(7,[i].; DisplayStyle(7,[i].;DisplayStyle(7,[i].; DisplayStyle(9,[i].;DisplayStyle(9,[i].; DisplayStyle(5,[i].;printf("%6d\n",[i].; printf("\n");}/*10.調(diào)整對(duì)齊格式函數(shù)*/voidDisplayStyle(inti,char*s){ intj; i-=strlen(s); for(j=0;j<i;++j)printf(""); printf("%s,",s);}/*11.交互界面函數(shù)*/voidsearchcon(SLListL){ inti=1,k; while(i>=1&&i<=5){ printf("\n請(qǐng)選擇命令代號(hào)(05):"); scanf("%d",&i); switch(i){ case1:printf("輸入要查詢的航班號(hào)(字母要大寫(xiě)):"); scanf("%s",key);k=BinSearch(L,key); if(k) Display(L,k); else printf("很抱歉，無(wú)此航班信息。\n"); break; case2:printf("輸入要查詢的航班起點(diǎn)站名:"); scanf("%s",key);SeqSearch(L,key,i); break; case3:printf("輸入要查詢的航班終點(diǎn)站名:"); scanf("%s",key);SeqSearch(L,key,i); break; case4:printf("輸入要查詢的航班起飛時(shí)間:"); scanf("%s",kl);SeqSearch(L,kl,i); break; case5:printf("輸入要查詢的航班到達(dá)時(shí)間:"); scanf("%s",kl);SeqSearch(L,kl,i); break; case0:printf("再見(jiàn)！\n"); return; } Prompt();顯示主菜單*/voidPrompt(){ printf("***************************************************\n"); printf("*航班信息查詢與檢索系統(tǒng)*\n"); printf("***************************************************\n"); printf("*1.按航班號(hào)查詢*\n"); printf("*2.按起點(diǎn)站查詢*\n"); printf("*3.按終點(diǎn)站查詢*\n"); printf("*4.按起飛時(shí)間查詢*\n"); printf("