.PAGE.學院名稱《數(shù)據(jù)結構》課程設計報告題目——航班信息查詢與檢索班級：__時間：2012/12/292013/1/5二○一二年十二月二十九日課程設計任務書及成績評定課題名稱航班信息查詢與檢索Ⅰ、題目的目的和要求：1、設計目的鞏固和加深對數(shù)據(jù)結構的理解,通過上機實驗、調(diào)試程序,加深對課本知識的理解,最終使學生能夠熟練應用數(shù)據(jù)結構的知識寫程序?！?通過本課程的學習,能熟練掌握幾種基本數(shù)據(jù)結構的基本操作?！?能針對給定題目,選擇相應的數(shù)據(jù)結構,分析并設計算法,進而給出問題的正確求解過程并編寫代碼實現(xiàn)。2、設計題目要求：問題描述:該設計要求對飛機航班信息進行排序和查找?？砂春桨嗟暮桨嗵?、起點站、到達站、起飛時間以及到達時間等信息進行查詢。任務要求:對于本設計,可采用基數(shù)排序法對一組具有結構特點的飛機航班號進行排序,利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找,按其他次關鍵字的查找可采用最簡單的順序查找方法進行,因此他們用得較少。每個航班記錄包括八項,分別是：航班號、起點站、終點站、班期、起飛時間、到達時間、飛機型號以及票價等,假設航班信息表〔8條記錄航班號起點站終點站班期起飛時間到達時間機型票價CA1544XX北京.510551240733960MU5341上海XX每日14201615M901280CZ3869XXXX085510357331010MU3682XXXX.6.720502215M901380HU1836上海北京每日094011207381250CZ3528XXXX.5.715101650CRJ1060MU4594XXXX.6101511403281160SC7425XXXX19202120DH41630其中航班號一項的格式為：K0K1K2K3K4K5CZ3869其中K0和K1的輸入值是航空公司的別稱,用兩個大寫字母標示,后4位為航班號,這種航班號關鍵字可分成兩段,即字母和數(shù)字。其余七項輸入內(nèi)容因為不涉及本設計的核心,因此除了票價為數(shù)值型外,均定義為字符串即可。Ⅱ、設計進度及完成情況日期內(nèi)容12.29選取參考書,查閱有關文獻資料,完成資料搜集和系統(tǒng)分析工作。12.30創(chuàng)建相關數(shù)據(jù)結構,錄入源程序。12.31調(diào)試程序并記錄調(diào)試中的問題,初步完成課程設計報告。1.4上交課程設計報告打印版并進行課程設計答辯,要求每個同學針對自己的設計回答指導教師3-4個問題。1.5考核結束后將課程設計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。Ⅲ、主要參考文獻及資料[1]嚴蔚敏數(shù)據(jù)結構〔C語言版清華大學出版社1999[2]嚴蔚敏數(shù)據(jù)結構題集〔C語言版清華大學出版社1999[3]譚浩強C語言程序設計清華大學出版社[4]與所用編程環(huán)境相配套的C語言或C++相關的資料Ⅳ、成績評定：設計成績：〔教師填寫指導〔簽字二○一三..目錄6211一、概述……………610268二、系統(tǒng)分析………6三、概要設計………6四、詳細設計………71.定義數(shù)據(jù)類型…………………72.算法實現(xiàn)………8五、測試數(shù)據(jù)………10六、收獲與體會……………………13七、參考文獻………13八、附錄……………14一、概述課程設計是實踐性教學中的一個重要環(huán)節(jié),它以某一課程為基礎,可以涉及和課程相關的各個方面,是一門獨立于課程之外的特殊課程。課程設計是讓同學們對所學的課程更全面的學習和應用,理解和掌握課程的相關知識?！稊?shù)據(jù)結構》是一門重要的專業(yè)基礎課,是計算機理論和應用的核心基礎課程。數(shù)據(jù)結構課程設計,要求學生在數(shù)據(jù)結構的邏輯特性和物理表示、數(shù)據(jù)結構的選擇和應用、算法的設計及其實現(xiàn)等方面,加深對課程基本內(nèi)容的理解。同時,在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。本課程設計主要是對排序及查找等進行練習,以鏈式基數(shù)排序為主線,利用二分查找和順序查找等知識,并建立靜態(tài)鏈表,完成對航班信息的查詢與檢索。我們可以利用航班的這些信息,通過其中的任意一個信息,找出我們所需要的查找的航班的所有信息,所以,我們可以采用基數(shù)排序法對一組具有結構特點的飛機航班號進行排序,利用二分查找法對排序好的航班記錄按航班號實現(xiàn)快速查找,并按其他關鍵字的查找可以采用最簡單的順序查找方法進行。二、系統(tǒng)分析1設計要求<1>提供對航班信息的排序功能<2>提供對航班信息的輸入輸出記錄功能找出我們所需要的查找的航班的所有信息<3提供按關鍵字〔航班號快速查詢或順序查詢功能2設計分析對于本設計,可采用基數(shù)排序法對一組具有結構特點的飛機航班號進行排序,利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找,按其他次關鍵字的查找可采用最簡單的順序查找方法進行,因為它們用得比較少。每個航班記錄包括八項,分別是：航班號,起點站,終點站,班期,起飛時間,到達時間,飛機型號以及票價等。其中航班號一項的格式為：K0k1k2k3k4k5CZ3869CZ3869航班關鍵字可分為兩段,即字母和數(shù)字。其中k0和k1是航空公司的別稱,用兩個大寫字母表示,后4位為航班編號。三、概要設計1、設計思路根據(jù)題目所要求,程序必須實現(xiàn)航班信息的錄入和查詢。程序首先定義了一個用于儲存航班信息的數(shù)據(jù)類型,再由用戶錄入航班數(shù)據(jù),在錄入的同時并對數(shù)據(jù)進行排序,最后執(zhí)行數(shù)據(jù)查詢和檢索。在查詢設計中,使用二分查找法對排好序的航班數(shù)據(jù)按航班號實現(xiàn)快速查找,按起點站、終點站、起飛時間、到達時間查找的則采用順序查詢方法。定義數(shù)據(jù)類型2、流程圖定義數(shù)據(jù)類型接受查找條件、查找關鍵字數(shù)據(jù)輸入、排序接受查找條件、查找關鍵字數(shù)據(jù)輸入、排序輸出查找結果輸出查找結果四、詳細設計1.定義數(shù)據(jù)類型根據(jù)設計要求,設計中所用到的數(shù)據(jù)記錄只有航班信息,因此要定義相關的數(shù)據(jù)類型：[1]typedefstruct{charstart[6];//起點站charend[6];//終點站charsche[10];//航班期chartime1[5];//起飛時間chartime2[5];//到達時間charmodel[4];//機型intprice;//票價}infotype;//航班記錄類型typedefstruct{keytypekeys[keylen];//關鍵字infotypeothers;intnext;}slnode;//表結點typedefstruct{slnodesl[maxspace];//靜態(tài)鏈表,s1[0]為頭結點intkeynum;//關鍵字長intlength;//當前表長}sllist;//靜態(tài)鏈表類型為了進行基數(shù)排序,需要定義在分配和收集操作時用到的指針數(shù)組：typedefintarrtype_n[10];//十進制數(shù)字指針數(shù)組typedefintarrtype_c[26];//26個字母指針數(shù)組2.算法實現(xiàn)〔1一趟分配算法[2]voiddistribute<slnode*sl,inti,arrtype_nf,arrtype_ne>{intj,p;for<j=0;j<radix_n;j++>{f[j]=e[j]=0;}for<p=sl[0].next;p;p=sl[p].next>{j=sl[p].keys[i]%48;//將數(shù)字字符轉化為對應的數(shù)值型數(shù)字if<!f[j]>f[j]=p;elsesl[e[j]].next=p;e[j]=p;//將p指向的結點插入到第j個結點}}〔2一趟收集算法voidcollect<slnode*sl,inti,arrtype_nf,arrtype_ne>{intj,t;for<j=0;!f[j];j++>;//找第一個非空子表s1[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]>{s1[t].next=f[j];t=e[j];}//鏈接兩個非空子表}sl[t].next=0;}〔3鏈式基數(shù)排序算法[3]voidradixsort<sllist&l>{inti;arrtype_nfn,en;arrtype_cfc,ec;for<i=0;i<l.length;i++>l.sl[i].next=i+1;l.sl[l.length].next=0;//將普通的線性表改為靜態(tài)鏈表for<i=l.keynum-1;i>=2;i-->//按最低位優(yōu)先依次對各關鍵字收集{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>//按指針鏈表整理靜態(tài)鏈表{intp,q,i;slnodetemp;p=l.sl[0].next;for<i=1;i<l.length;i++>{while<p<i>p=l.sl[p].next;q=l.sl[p].next;if<p!=i>{temp=l.sl[p];l.sl[p]=l.sl[i];l.sl[i]=temp;//交換記錄l.sl[i].next=p;}p=q;}}〔4二分查找函數(shù)定義[4]intbinsearch<sllistl,keytypekey[]>{intlow,high,mid;low=1;high=l.length;while<low<=high>{mid=<low+high>/2;if<strcmp<key,l.sl[mid].keys>==0>returnmid;elseif<strcmp<key,l.sl[mid].keys><0>high=mid-1;elselow=mid+1;}return0;}五、測試數(shù)據(jù)航班信息輸入如圖：按航班號查詢：輸入航班號錯誤則顯示如下圖：按航班起點站查詢：按航班起點查詢：按起飛時間查詢：顯示查詢主菜單,退出查詢系統(tǒng)：六、收獲與體會通過本實驗,我了解了基數(shù)排序是作為一種內(nèi)部排序方法,當關鍵字位數(shù)較少而排序序列較長時,該排序算法有一定的優(yōu)越性。而對于有序序列的查找算法,二分查找是一種效率比較高的方法。在本實驗中,對這兩種算法的應用,我加深了對他們的理解,掌握了他們的實現(xiàn)方法。在本次實驗過程中,輸入錯誤還是存在的問題,但能很快的通過編譯解決,一些編譯不能發(fā)現(xiàn)的問題,在組建過程中也能發(fā)現(xiàn)并解決。這次實驗的過程中遇到了很多問題,定義的過程中存在定義不清楚的問題,還有一些模糊定義和重定義的問題出現(xiàn)。在程序的定義過程中,存在著函數(shù)的調(diào)用失敗的問題,在調(diào)用過程中不能正常調(diào)用,通過把調(diào)用的函數(shù)直接用在程序中,不通過調(diào)用的方法,使得程序正常運行。本次實驗的問題只要通過調(diào)試和對整個程序的理解,便可以解決所有的發(fā)現(xiàn)的問題本次實驗利用二分查找法很快的完成了對航班信息的查找,使我們對二分查找有了一個很好的掌握。其查找過程是先確定待查記錄所在的范圍〔區(qū)間,然后逐步縮小范圍直到找到或找不到該記錄為止。在實驗過程中,程序中許多定義需要我們有一個很仔細的了解,比如上述的對字符長度的定義,這需要對所定義的對象給一個合理的字符長度,在輸入的過程中才不會出現(xiàn)因輸入的字符長度過長而不能識別。本次實驗中用到了靜態(tài)鏈表,定義靜態(tài)鏈表的過程中,需要有一個很熟悉的了解,知道靜態(tài)鏈表是如何定義以及如何實現(xiàn)。通過這次實驗,使得對于查找以及檢索有了一個很好的掌握,讓我們在以后的程序設計過程中對于類似的函數(shù)定義有一個很清晰的過程以及了解。七、參考文獻[1]徐孝凱,魏榮《數(shù)據(jù)結構》,機械工程出版社[2]譚浩強《程序設計》,北京大學出版社[3]楊路明《C語言程序設計教程》,北京郵電大學出版社.[4]耿國華《數(shù)據(jù)結構-C語言描述》,高等教育出版社八、附錄源程序清單：#include<stdio.h>#include<string.h>#defineMaxSpace100#definekeylen7#defineRADIX_n10#defineRADIX_c26typedefcharKeyType;typedefstruct{charstart[6];//起點charend[6];//終點charsche[10];//班期chartime1[5];//起飛時間chartime2[5];//到達時間charmodel[4];//機型intprice;//票價}InfoType;//航班記錄類型typedefstruct{KeyTypekeys[keylen];//關鍵字〔航班號InfoTypeothers;intnext;}SLNode;//靜態(tài)鏈表結點類型typedefstruct{SLNodesl[MaxSpace];//靜態(tài)鏈表,s1[0]為頭結點intkeynum;//記錄當前關鍵字字符個數(shù)intlength;//當前表長}SLList;//靜態(tài)鏈表類型typedefintArrType_n[RADIX_n];//十進制數(shù)字指針數(shù)組typedefintArrType_c[RADIX_c];//26個字母指針數(shù)組//一趟數(shù)字字符分配函數(shù)voidDistribute<SLNode*sl,inti,ArrType_nf,ArrType_ne>{intj,p;for<j=0;j<RADIX_n;j++>{//各子表置為空表f[j]=e[j]=0;}for<p=sl[0].next;p;p=sl[p].next>{j=sl[p].keys[i]%48;//將數(shù)字字符轉換成相對應的數(shù)值型數(shù)字if<!f[j]>f[j]=p;elsesl[e[j]].next=p;e[j]=p;//將p指向的結點插入到第j個子表中}}//一趟數(shù)字字符的收集函數(shù)voidCollect<SLNode*sl,inti,ArrType_nf,ArrType_ne>{intj,t;for<j=0;!f[j];j++>//找第一個非空子表sl[0].next=f[j];//s1[0].next指向第一個非空子表中的一個結點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;//t指向最后一個非空子表中的最后一個結點}//一趟字母字符分配函數(shù)voidDistribute_c<SLNode*sl,inti,ArrType_cf,ArrType_ce>{intj,p;for<j=0;j<RADIX_c;j++>{//各子表置為空表f[j]=e[j]=0;}for<p=sl[0].next;p;p=sl[p].next>{j=sl[p].keys[i]%65;//將字母字符轉換成在字母集中相應的序號〔0-25if<!f[j]>f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}//一趟字母字符收集voidCollect_c<SLNode*sl,inti,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;}//鏈式基數(shù)排序函數(shù)voidRadixSort<SLList&L>//鏈式{inti;ArrType_nfn,en;ArrType_cfc,ec;for<i=0;i<L.length;i++>L.sl[i].next=i+1;//0號單元僅存放指針,不存儲內(nèi)容L.sl[L.length].next=0;//將普通的線性表改造為靜態(tài)鏈表for<i=L.keynum-1;i>=2;i-->{//按最低位優(yōu)先次序?qū)Ω麝P鍵字進行分配和收集,先做低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.sl[0].next;//p指向第一個記錄的當前位置for<i=1;i<L.length;i++>//l.s1[1…i-1]已按關鍵字有序化{while<p<i>p=L.sl[p].next;//找到第i個記錄,并用p指向其在L中當前位置q=L.sl[p].next;//q指向尚未調(diào)整的表尾if<p!=i>{temp=L.sl[p];L.sl[p]=L.sl[i];L.sl[i]=temp;L.sl[i].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.sl[mid].keys>==0>returnmid;elseif<strcmp<key,L.sl[mid].keys><0>high=mid-1;elselow=mid+1;}return0;}//順序查找函數(shù)voidSeqSearch<SLListL,KeyTypekey[],inti>{intj,k,m=0;printf<"*************************************************************\n">;printf<"*航班號起點站終點站航班期起飛時間到達時間機型票價*\n">;for<j=1;j<=L.length;j++>{switch<i>{case2:k=strcmp<key,L.sl[j].others.start>;break;case3:k=strcmp<key,L.sl[j].others.end>;break;case4:k=strcmp<key,L.sl[j].others.time1>;break;case5:k=strcmp<key,L.sl[j].others.time2>;break;}if<k==0>{m=1;printf<"*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*\n",L.sl[j].keys,L.sl[j].others.start,L.sl[j].others.end,L.sl[j].others.sche,L.sl[j].others.time1,L.sl[j].others.time2,L.sl[j].others.model,L.sl[j].others.price>;}}if<m==0>printf<"*無此航班信息,可能是輸入錯誤！*\n">;printf<"*************************************************************\n">;}//查詢檢索菜單控制程序voidsearchcon<SLListL>{KeyTypekey[keylen];inti=1,k;while<i>=1&&i<=5>{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">;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">;else{printf<"*航班號起點站終點站航班期起飛時間到達時間機型票價*\n">;printf<"*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*\n",L.sl[k].keys,L.sl[k].