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

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