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

1、學院名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目一一航班信息查詢與檢索班級：姓名：時間：2012/12/29-2013/1/5教育資料二。一二年十二月二十九日課程設(shè)計任務(wù)書及成績評定課題名稱航班信息查詢與檢索I、題目的目的和要求：1、設(shè)計目的鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機實驗、調(diào)試程序，加深對課本知識的理解,最終使學生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識寫程序。(1)通過本課程的學習，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。(2)能針對給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計算法，進而給出問題的正確求解過程并編寫代碼實現(xiàn)。2、設(shè)計題目要求：問題描述：該設(shè)計要求對飛機航班信息進行排序和查找?？砂春桨嗟暮桨嗵?、起點站、

2、到達站、起飛時間以及到達時間等信息進行查詢。任務(wù)要求：對于本設(shè)計，可采用基數(shù)排序法對一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找，按其他次關(guān)鍵字的查找可采用最簡單的順序查找方法進行，因此他們用得較少。每個航班記錄包括八項，分別是：航班號、起點站、終點站、班期、起飛時間、到達時間、飛機型號以及票價等，假設(shè)航班信息表(8條記錄)航班號起點站終點站班期起飛時間到達時間機型票價CA1544合肥北京1.2.4.510551240：733960MU5341上海廣州每日14201615M901280CZ3869重慶深圳2.4.6085510357331010MU

3、3682桂林南京2.3.4.6.7205022151M901380HU1836上海北京每日094011207381250CZ3528成都廈門1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.611015114013281160SC7425青島?？?.3.619202120DH41630其中航班號一項的格式為：K0K1K2K3K4K5CZ3869教育資料其中K0和K1的輸入值是航空公司的別稱，用兩個大寫字母標示，后4位為航班號,這種航班號關(guān)鍵字可分成兩段，即字母和數(shù)字。其余七項輸入內(nèi)容因為不涉及本設(shè)計的核心，因此除了票價為數(shù)值型外，均定義為字符串即可。n、設(shè)計進度及

4、完成情況日期內(nèi)容12.29選取參考書，查閱有關(guān)文獻資料，完成資料搜集和系統(tǒng)分析工作。12.30創(chuàng)建相關(guān)數(shù)據(jù)結(jié)構(gòu)，錄入源程序。12.31調(diào)試程序并記錄調(diào)試中的問題，初步完成課程設(shè)計報告。1.4上交課程設(shè)計報告打印版并進行課程設(shè)計答辯，要求每個同學針對自己的設(shè)計回答指導(dǎo)教師3-4個問題。1.5考核結(jié)束后將課程設(shè)計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。田、主要參考文獻及資料1嚴蔚敏數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學出版社19992嚴蔚敏數(shù)據(jù)結(jié)構(gòu)題集（C語言版）清華大學出版社19993譚浩強C語言程序設(shè)計清華大學出版社4與所用編程環(huán)境相配套的C語言或C+#目關(guān)的資料教育資料IV、成績評定:設(shè)計成績：（教

5、師填寫）指導(dǎo)老師：（簽字）教育資料目錄一、概述6二、系統(tǒng)分析6三、概要設(shè)計6四、詳細設(shè)計71,定義數(shù)據(jù)類型72.算法實現(xiàn)8五、測試數(shù)據(jù)10六、收獲與體會13七、參考文獻13八、附錄14教育資料概述課程設(shè)計是實踐性教學中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個方面，是一門獨立于課程之外的特殊課程。課程設(shè)計是讓同學們對所學的課程更全面的學習和應(yīng)用，理解和掌握課程的相關(guān)知識。數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課，是計算機理論和應(yīng)用的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，要求學生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程

6、序設(shè)計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓(xùn)練。本課程設(shè)計主要是對排序及查找等進行練習，以鏈式基數(shù)排序為主線，利用二分查找和順序查找等知識，并建立靜態(tài)鏈表，完成對航班信息的查詢與檢索。我們可以利用航班的這些信息，通過其中的任意一個信息，找出我們所需要的查找的航班的所有信息，所以，我們可以采用基數(shù)排序法對一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二分查找法對排序好的航班記錄按航班號實現(xiàn)快速查找，并按其他關(guān)鍵字的查找可以采用最簡單的順序查找方法進行。二、系統(tǒng)分析1設(shè)計要求(1)提供對航班信息的排序功能(2)提供對航班信息的輸入輸出記錄功能找出我們所需要的查找的航班的所有信息

7、(3)提供按關(guān)鍵字(航班號)快速查詢或順序查詢功能2設(shè)計分析對于本設(shè)計，可采用基數(shù)排序法對一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找，按其他次關(guān)鍵字的查找可采用最簡單的順序查找方法進行，因為它們用得比較少。每個航班記錄包括八項，分別是：航班號，起點站，終點站，班期，起飛時間，到達時間，飛機型號以及票價等。其中航班號一項的格式為：K0k1k2k3k4k5CZ3869航班關(guān)鍵字可分為兩段，即字母和數(shù)字。其中k0和k1是航空公司的別稱，用兩個大寫字母表示，后4位為航班編號。三、概要設(shè)計1、設(shè)計思路根據(jù)題目所要求，程序必須實現(xiàn)航班信息的錄入和查詢。程序首

8、先定義了一個教育資料用于儲存航班信息的數(shù)據(jù)類型，再由用戶錄入航班數(shù)據(jù)，在錄入的同時并對數(shù)據(jù)進行排序，最后執(zhí)行數(shù)據(jù)查詢和檢索。在查詢設(shè)計中，使用二分查找法對排好序的航班數(shù)據(jù)按航班號實現(xiàn)快速查找，按起點站、終點站、起飛時間、到達時間查找的則采用順序查詢方法。2、流程圖起點站終點站航班期起飛時間到達時間機型票價航班記錄類型關(guān)鍵字表結(jié)點靜態(tài)鏈表，s10為頭結(jié)關(guān)鍵字長四、詳細設(shè)計1,定義數(shù)據(jù)類型根據(jù)設(shè)計要求，設(shè)計中所用到的數(shù)據(jù)記錄只有航班信息，因此要定義相關(guān)的數(shù)據(jù)類型：1typedefstructcharstart6;/charend6;/charsche10;/chartime15;/chartime

9、25;/charmodel4;/intprice;/infotype;/typedefstructkeytypekeyskeylen;/infotypeothers;intnext;slnode;/typedefstructslnodeslmaxspace;/八、intkeynum;/教育資料intlength;/當前表長sllist;/靜態(tài)鏈表類型為了進行基數(shù)排序，需要定義在分配和收集操作時用到的指針數(shù)組：typedefintarrtype_n10;/十進制數(shù)字指針數(shù)組typedefintarrtype_c26;/26個字母指針數(shù)組2.算法實現(xiàn)(1) 一趟分配算法2voiddistribut

10、e(slnode*sl,inti,arrtype_nf,arrtype_ne)intj,p;for(j=0;j<radix_n;j+).fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48;/將數(shù)字字符轉(zhuǎn)化為對應(yīng)的數(shù)值型數(shù)字if(!fj)fj=p;elseslej.next=p;ej=p;/將p指向的結(jié)點插入到第j個結(jié)點(2) 一趟收集算法voidcollect(slnode*sl,inti,arrtype_nf,arrtype_ne)intj,t;for(j=0;!fj;j+);/找第一個非空子表s10.next=fj;t=ej;whil

11、e(j<radix_n-1)for(j=j+1;j<radix_n-1&&!fj;j+);/找下一個非空子表if(fj)s1t.next=fj;t=ej;/鏈接兩個非空子表教育資料將普通的線性表改為靜態(tài)按最低位優(yōu)先依次對各關(guān)鍵字收集按指針鏈表整理靜態(tài)鏈)slt.next=0;)(3)鏈式基數(shù)排序算法3voidradixsort(sllist&l)(inti;arrtype_nfn,en;arrtype_cfc,ec;for(i=0;i<l.length;i+)l.sli.next=i+1;l.sll.length.next=0;/鏈表for(i=l.k

12、eynum-1;i>=2;i-)/(distribute(l.sl,i,fn,en);collect(l.sl,i,fn,en);)for(i=1;i>=0;i-)(distribute_c(l.sl,i,fc,ec);collect_c(l.sl,i,fc,ec);).)voidarrange(sllist&l)/表(intp,q,i;slnodetemp;p=l.sl0.next;for(i=1;i<l.length;i+)(while(p<i)p=l.slp.next;q=l.slp.next;if(p!=i)(temp=l.slp;l.slp=l.sli

13、;教育資料l.sli=temp;/交換記錄l.sli.next=p;)p=q；)(4)二分查找函數(shù)定義4intbinsearch(sllistl,keytypekey)(intlow,high,mid;low=1;high=l.length;while(low<=high)(mid=(low+high)/2;if(strcmp(key,l.slmid.keys)=0)returnmid;elseif(strcmp(key,l.slmid.keys)<0)high=mid-1;elselow=mid+1;)return0;)五、測試數(shù)據(jù)航班信息輸入如圖：教育資料按航班號查詢:輸入航班

14、號錯誤則顯示如下圖:按航班起點站查詢:教育資料航班信息查詢系統(tǒng)-*M-K-*Fm三間間沅班點點航遠終一-一123450請選擇£0T”曾入要查詢的航班起點站名;上海*航班號起點站終點站隨班期起飛時間到達時間機型票價*MU5341上海廣州每日14201615M901280*MM8923上海南寧1.3.51201512877400*按航班起點查詢:*C：WindovsVsysteiii3ZDebiigBH.exe*航班信息查詢系統(tǒng)*口京站昌統(tǒng)朝點只飛達出冬123450請選擇,舊-SX翁人要查詢的航班起點站等南昌按起飛時間查詢:教育資料顯示查詢主菜單，退出查詢系統(tǒng):*航班信息查詢系統(tǒng)*-ia

15、|x|n冢站間間啰班點點需終起患123450M-請選擇:p見Pressanykeytocontinue六、收獲與體會通過本實驗，我了解了基數(shù)排序是作為一種內(nèi)部排序方法，當關(guān)鍵字位數(shù)較少而排序序列較長時，該排序算法有一定的優(yōu)越性。而對于有序序列的查找算法，二分查找是一種效率比較高的方法。在本實驗中，對這兩種算法的應(yīng)用，我加深了對他們的理解，掌握了他們的實現(xiàn)方法。在本次實驗過程中，輸入錯誤還是存在的問題，但能很快的通過編譯解決，一些編譯不能發(fā)現(xiàn)的問題，在組建過程中也能發(fā)現(xiàn)并解決。這次實驗的過程中遇到了很多問題，定義的過程中存在定義不清楚的問題，還有一些模糊定義和重定義的問題出現(xiàn)。在程序的定義過程中

16、，存在著函數(shù)的調(diào)用失敗的問題，在調(diào)用過程中不能正常調(diào)用，通過把調(diào)用的函數(shù)直接用在程序中，不通過調(diào)用的方法，使得程序正常運行。本次實驗的問題只要通過調(diào)試和對整個程序的理解，便可以解決所有的發(fā)現(xiàn)的問題本次實驗利用二分查找法很快的完成了對航班信息的查找，使我們對二分查找教育資料有了一個很好的掌握。具查找過程是先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。在實驗過程中，程序中許多定義需要我們有一個很仔細的了解，比如上述的對字符長度的定義，這需要對所定義的對象給一個合理的字符長度，在輸入的過程中才不會出現(xiàn)因輸入的字符長度過長而不能識別。本次實驗中用到了靜態(tài)鏈表，定義靜態(tài)鏈

17、表的過程中，需要有一個很熟悉的了解，知道靜態(tài)鏈表是如何定義以及如何實現(xiàn)。通過這次實驗，使得對于查找以及檢索有了一個很好的掌握，讓我們在以后的程序設(shè)計過程中對于類似的函數(shù)定義有一個很清晰的過程以及了解。七、參考文獻1徐孝凱，魏榮數(shù)據(jù)結(jié)構(gòu)，機械工程出版社2譚浩強程序設(shè)計，北京大學出版社3楊路明C語言程序設(shè)計教程，北京郵電大學出版社4耿國華數(shù)據(jù)結(jié)構(gòu)-C語言描述，高等教育出版社八、附錄源程序清單：#include<stdio.h>#include<string.h>#defineMaxSpace100#definekeylen7#defineRADIX_n10#defineRA

18、DIX_c26typedefcharKeyType;typedefstruct(charstart6;/起點charend6;/終點charsche10;/班期教育資料chartime15;/chartime25;/charmodel4;/intprice;/InfoType;/typedefstruct起飛時間到達時間機型票價航班記錄類型KeyTypekeyskeylen;/關(guān)鍵字（航班號）intnext;SLNode;/typedefstructSLNodeslMaxSpace;/intkeynum;/intlength;/SLList;/靜態(tài)鏈表結(jié)點類型靜態(tài)鏈表，s10為頭結(jié)點記錄當前關(guān)

19、鍵字字符個數(shù)當前表長靜態(tài)鏈表類型InfoTypeothers;typedefintArrType_nRADIX_n;/十進制數(shù)字指針數(shù)組typedefintArrType_cRADIX_c;/26個字母指針數(shù)組/一趟數(shù)字字符加己函數(shù)一voidDistribute(SLNode*sl,inti,ArrType_nf,ArrType_ne)intj,p;for(j=0;j<RADIX_n;j+)/各子表置為空表fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48;/將數(shù)字字符轉(zhuǎn)換成相對應(yīng)的數(shù)值型數(shù)字if(!fj)fj=p;elseslej.ne

20、xt=p;ej=p;/將p指向的結(jié)點插入到第j個子表中/一趟數(shù)字字符的收集函數(shù)voidCollect(SLNode*sl,inti,ArrType_nf,ArrType_ne)intj,t;教育資料for(j=0;!fj;j+)/找第一個非空子表sl0.next=fj;/s10.next指向第一個非空子表中的一個結(jié)點t=ej;while(j<RADIX_n-1)找下一個非空子表(for(j=j+1;j<RADIX_n-1&&!fj;j+)/if(fj)/鏈接兩個非空子表指向最后一個非空子表中的最后一個結(jié)點(slt.next=fj;t=ej;slt.next=0;/t

21、/一趟字母字符分配函數(shù)voidDistribute_c(SLNode*sl,inti,ArrType_cf,ArrType_ce)(-intj,p;for(j=0;j<RADIX_c;j+)/各子表置為空表fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%65;/將字母字符轉(zhuǎn)換成在字母集中相應(yīng)的序號(0-25)if(!fj)fj=p;elseslej.next=p;ej=p;/一趟字母字符收集voidCollect_c(SLNode*sl,inti,ArrType_cf,ArrType_ce)intj,t;for(j=0;!fj;j+);sl

22、0.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;/鏈式基數(shù)排序函數(shù)voidRadixSort(SLList&L)/inti;ArrType_nfn,en;ArrType_cfc,ec;for(i=0;i<L.length;i+)L.sli.next=i+1;/0L.slL.length.next=0;/for(i=L.keynum-1;i>=2;i-)鏈式號單兀僅存放指針，不存儲內(nèi)容將普通的線

23、性表改造為靜態(tài)鏈表/按最低位優(yōu)先次序?qū)Ω麝P(guān)鍵字進行分配和收集，先做低4位數(shù)字部分Distribute(L.sl,i,fn,en);Collect(L.sl,i,fn,en);for(i=1;i>=0;i-)/對高位的2位大寫字母進行分配和收集Distribute_c(L.sl,i,fc,ec);Collect_c(L.sl,i,fc,ec);/按指針鏈重新整理靜態(tài)鏈表voidArrange(SLList&L)/intp,q,i;SLNodetemp;p=L.sl0.next;/pfor(i=1;i<L.length;i+)/l.s11重新整理指向第一個記錄的當前位置i-1已

24、按關(guān)鍵字有序化while(p<i)p=L.slp.next;q=L.slp.next;if(p!=i)/q找到第i個記錄，并用p指向其在L中當前位置指向尚未調(diào)整的表尾教育資料temp=L.slp;L.slp=L.sli;L.sli=temp;L.sli.next=p;/交換記錄p=q;/p指向尚未調(diào)整的表尾，為找第i+1個記錄做準備/二分查找函數(shù)intBinSearch(SLListL,KeyTypekey)(intlow,high,mid;low=1;high=L.length;while(low<=high)(mid=(low+high)/2;if(strcmp(key,L.s

25、lmid.keys)=0)returnmid;elseif(strcmp(key,L.slmid.keys)<0)high=mid-1;elselow=mid+1;return0;/順序查找函數(shù)voidSeqSearch(SLListL,KeyTypekey,inti)(intj,k,m=0;prnfS*N');printf("*航班號起點站終點站航班期起飛時間到達時間機型票價*n");for(j=1;j<=L.length;j+)(switch(i)(case2:k=strcmp(key,L.slj.others.start);break;case3:

26、k=strcmp(key,L.slj.others.end);break;case4:k=strcmp(key,L.slj.others.time1);break;case5:k=strcmp(key,L.slj.others.time2);break;if(k=0)(教育資料m=1;printf("*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*n",L.slj.keys,L.slj.others.start,L.slj.others.end,L.slj.others.sche,L.slj.others.time1,L.slj.others.time2

27、,L.slj.others.model,L.slj.others.price);if(m=0)printf("*無此航班信息，可能是輸入錯誤！*n");prnfS*N');/查詢檢索菜單控制程序voidsearchcon(SLListL)KeyTypekeykeylen;inti=1,k;while(i>=1&&i<=5)printf("*n");printf("*航班信息查詢系統(tǒng)*n");printf("*號站站即班點點2航起終4.*n")*n")*n")起

28、飛時間*n")printf("*5.printf("*0.到達時間*n")退出系統(tǒng)*n")printf("*n");printf("請選擇(0-5):n");scanf("%d",&i);switch(i)case1:printf("輸入要查詢的航班號(字母要大寫):")；scanf("%s",key);k=BinSearch(L,key);printf("*n");教育資料if(k=0)printf("無此航班信息，可能是輸入錯誤！n");elseprintf("*航班號起點站終點站航班期起飛時間到達時間機型票價*n");printf("*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*n",L.slk.keys,L.slk.others.start,L.slk.others.end,L.slk.others.sche,L.slk.others.time1,L.slk.others.time2,L.slk.others.model,L.slk.others.price);prnfS*N');break