綜合實(shí)踐1數(shù)據(jù)結(jié)構(gòu)與算法分析

1、綜合實(shí)踐1 (數(shù)據(jù)結(jié)構(gòu)與算法分析)實(shí)踐報(bào)告題目：航班信息的查詢與檢索系統(tǒng)班級： 計(jì)本054班姓名：張海一學(xué)號：2004024055指導(dǎo)教師：張敬2007年6月綜合實(shí)踐1評分表班級計(jì)本054姓名張海舶指導(dǎo)教師張敬題目：航班信息的檢索與查詢評分標(biāo)準(zhǔn)評分標(biāo)準(zhǔn)分?jǐn)?shù)權(quán)重評分的依據(jù)得分AC選題10選題符合大綱要求，題 目較新穎，工作量大選題基本符合大綱要 求，工作量適中工作態(tài)度10態(tài)度端正，能主動(dòng)認(rèn)真 完成各個(gè)環(huán)節(jié)的工作， 不遲到早退，出勤好。能夠完成各環(huán)節(jié)基本 工作，出勤較好。存儲結(jié)構(gòu)、算 法描述20能止確選擇存儲結(jié)構(gòu)， 定義準(zhǔn)確，算法流程圖 或類C諦言描述的算 法準(zhǔn)確無誤能止確選擇存儲結(jié)構(gòu)， 算法流程

2、圖或類C語 言描述的算法基本準(zhǔn) 確獨(dú)立解決問題 的能力10具有獨(dú)立分析、解決問 題能力，有f的創(chuàng)造 性，能夠獨(dú)立完成軟件 的設(shè)計(jì)與調(diào)試工作，程 序結(jié)構(gòu)清晰，邏輯嚴(yán) 謹(jǐn)，功能完善。有一定的分析、解決問 題能力。能夠在老師指 導(dǎo)下完成軟件的設(shè)計(jì) 與調(diào)試工作，程序功能 較完善。答辨問題回答20能準(zhǔn)確回答老師提出 的問題能基本準(zhǔn)確回答老師 提出的問題程序運(yùn)行情況10程序運(yùn)行正確、界面清 晰，測試數(shù)據(jù)設(shè)計(jì)合 理。程序運(yùn)行止確、界面較 清晰，能給出合適的測 試數(shù)據(jù)。綜合實(shí)踐報(bào)告20格式規(guī)范，層次清晰， 設(shè)計(jì)思想明確，解決問 題方法合理，體會(huì)深 亥人格式較規(guī)范，設(shè)計(jì)思想 基本明確，解決問題方 法較合理?？偡?/p>

3、指導(dǎo)教師（簽字）：注：介于A和C之間為B級，低于C為D級和E級。按各項(xiàng)指標(biāo)打分后，總分在90100 為優(yōu)，8089為良，7079為中，6069為及格，60分以下為不及格。航班信息的查詢與檢索系統(tǒng)設(shè)計(jì)說明1、問題描述與分析排序和查找是數(shù)據(jù)信息處理中使用頻度極高的操作。為了加快查找的速度，需要先對 數(shù)據(jù)記錄按關(guān)鍵字排序。當(dāng)今乘飛機(jī)旅行的人越來越多，人們需要關(guān)心了解各類航班的班 次、時(shí)間、價(jià)格及機(jī)型等信息。在這個(gè)飛機(jī)航班數(shù)據(jù)的信息模型中，航班號是關(guān)鍵字，而 且是具有結(jié)構(gòu)特點(diǎn)的一類關(guān)鍵字。因?yàn)楹桨嗵柺亲帜笖?shù)字混編的，例如： CZ1234這種記 錄集合是一個(gè)適合于多關(guān)鍵字排序的例子。2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和基

4、本算法設(shè)計(jì)方法的選擇該設(shè)計(jì)要求對飛機(jī)航班信息進(jìn)行排序和查找?？砂春桨嗟暮桨嗵?、起點(diǎn)站、到達(dá)站、 起飛時(shí)間以及到達(dá)時(shí)間等信息進(jìn)行查詢。對于本設(shè)計(jì)，可采用基數(shù)排序法對一組具有結(jié)構(gòu)特點(diǎn)的飛機(jī)班號進(jìn)行排序，利用二分 查找法對排好序的航班記錄按航班號實(shí)現(xiàn)快速查找，按其他關(guān)鍵字的查找可采用最簡單的 順序查找方法進(jìn)行，因?yàn)樗鼈冇玫妮^少。每個(gè)航班記錄包括8項(xiàng)，分別是：航班號、起點(diǎn)站、到達(dá)站、班期、起飛時(shí)間、到達(dá) 時(shí)間、飛機(jī)型號以及票價(jià)等，本設(shè)計(jì)儲存的航班信息如下：航班號起點(diǎn)站終點(diǎn)站班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)CA1544合肥北京1. 2. 4. 510551240733960MU5341上海廣州每日14201

5、615M901280CZ3869重慶深圳2. 4. 6085510357331010MU3682桂林南京2. 3. 4. 6. 720502215M901380HU1836上海北京每日094011207381250CZ3528成都廈門1. 3. 4. 5. 715101650CRJ1060MU4594昆明西安1. 3. 5. 6101511403281160SC7425青島?？? . 3. 619202120DH41630其中航班號一項(xiàng)的格式為：k0 k1 k2 k3 k4 k5CZ3869其中k0和k1的輸入值是航空公司的別稱，用兩個(gè)大寫字母表示，后4位為航班編號 這種航班號關(guān)鍵字可分成兩段

6、，即字母和數(shù)字。其余七項(xiàng)輸入內(nèi)容因?yàn)椴簧婕氨驹O(shè)計(jì)的核 心，因此除了票價(jià)為數(shù)值型外，均為字符串即可。3、軟件結(jié)構(gòu)設(shè)計(jì)航班信息查詢與檢索圖3-1結(jié)構(gòu)框圖4、算法設(shè)計(jì)源程序：#include#include#include#define N 8 / 航班數(shù)/航班信息typedef struct flightchar flight_number10; / 航班號char start_address10; / 起飛站char arrived_address10; / 終點(diǎn)站char work_date10;/班期int start_time; /起飛時(shí)間int arrived_time; /到達(dá)時(shí)間ch

7、ar FlightType4; 機(jī)型 int fare; /票價(jià)DataType;struct flight FlightN;/按航班號進(jìn)行基數(shù)排序typedef char KeyType;#define D 7/D#define R a/Rstruct Node;/為SF序碼的最大位數(shù)為基數(shù)，這里為小于字母a代表的整型值 單鏈表結(jié)點(diǎn)類型typedef struct Node RadixNode;struct NodeKeyType keyD; /關(guān)鍵字DataType info; /數(shù)據(jù)信息RadixNode *next;typedef RadixNode * RadixList;typed

8、ef struct QueueNodeRadixNode *f;/RadixNode *e;/對列的頭指針對列的尾指針Queue;Queue queueR;void radixSort(RadixList * plist, int d, int r)(int i,j,k;RadixNode *p, *head;head=(*plist)-next;for(j=d-1; j=0; j-) /進(jìn)彳T d次分配和收集(p=head;for(i=0; ikeyj; /按排序碼的第jif(queuek.f=NULL) queuek.f=p; / else (queuek.e)-next=p; / que

9、uek.e=p; p=p-next; i=0; while(queuei.f=NULL) i+;/p=queuei.e; head=queuei.f;/headfor(i+; inext=queuei.f; p=queuei.e; / p-next=NULL;清隊(duì)列個(gè)分量進(jìn)行分配若第k個(gè)堆為空，則當(dāng)前記錄為隊(duì)頭 否則當(dāng)前記錄鏈接到第k隊(duì)的隊(duì)尾從r個(gè)隊(duì)列中找出第一個(gè)非空的隊(duì)列 為收集鏈表的頭指針收集非空隊(duì)列(*plist)-next=head;/初始化航班信息表頭struct Node elementN+1=,0,0, ,0,NULL,CA1544,CA1544, 合肥,北京,1245”,105

10、5,1240,733”,960,NULL,MU5341,MU5341,上海,廣州,每日,1420,1615,M90,1280,NULL,CZ3869,CZ3869,重慶,深圳,246”,855,1035,733”,1010,NULL,MU3682,MU3682,桂林南京,23467”,2050,2215,M90,1380,NULL,HU1836,HU1836, 上海,北京,每日,940,1120,738”,1250,NULL, CZ3528,CZ3528, 成都,廈門,13457”,1510,1650,CRJ”,1060,NULL, MU4594, MU4594,昆明,西安,1356”,101

11、5,1014,328”,1160,NULL,SC7425, SC7425,青島,?？?,136”,1920,2120,DH4,1630,NULL,;/信 息顯/按表的格式輸出某個(gè)航班信息/顯小頭部信息void Cout_info1()cout”*nendl;cout”cout”*nendl;航班信息表 *nendl;cout 航班號起飛時(shí)間到達(dá)時(shí)間起飛站 終點(diǎn)站 班期 機(jī)型 票價(jià) nendl;/顯示主體信息 void Cout_info2_1(Node p)/ 方式一 cout info.flight_number;cout info.start_time;cout info.arrived_

12、time;cout info.start_address;cout info.arrived_address;cout info.work_date;cout info.FlightType;cout info.fare 元endl;void Cout_info2_2(flight F,int i)/方式二(cout Fi.flight_number;cout Fi.start_time;cout Fi.arrived_time;cout Fi.start_address;cout Fi.arrived_address;cout Fi.work_date;cout Fi.FlightType;

13、cout Fi.fare 元next;while(p!=NULL) ( Cout_info2_1(p);p=p-next; coutendl;void output_ALL_info2(flight F口)方式二(Cout_info1();for(int i=0;iN;i+) (Cout_info2_2(F,i);) coutnext;int i;for(i=0;iinfo.flight_number);Fi.start_time=p-info.start_time;Fi.arrived_time=p-info.arrived_time;strcpy(Fi.start_address,p-in

14、fo.start_address);strcpy(Fi.arrived_address,p-info.arrived_address);strcpy(Fi.work_date,p-info.work_date);strcpy(Fi.FlightType,p-info.FlightType);Fi.fare=p-info.fare;p=p-next;) )/服務(wù)菜單void F_By_Time(flight F,int);void F_By_Address(flight F,int);void F_By_fare(flight F);void F_By_FN(flight F);/主菜單void

15、 mainmenu()char ch;主菜單 nendl;int y;coutcout=nendl;cout令)nendl;Please choose: (input the number)(輸入查詢/排序命c(diǎn)out0.show the mainmenu (cout1.Find by flight number(cout2.Find by start time(cout3.Find by arrived time(cout4.Findbcout5.詢)nendl;cout6.Find by the fare(startFindcout按票價(jià)范圍查詢）nendl;顯示主菜單）nendl;按航班號

16、查詢）nendl;按起飛時(shí)間查詢）nendl;按到達(dá)時(shí)間查詢）nendl;address（按起飛地點(diǎn)查詢）nendl;by arrived address（按目 的地點(diǎn)查其他鍵退出endl;cout=nendl; while(1)couty;switch(y)case 0: mainmenu();break;case 1:F_By_FN(Flight);break;case 2:F_By_Time(Flight,1);break;case 3:F_By_Time(Flight,2);break;case 4:F_By_Address(Flight,1);break;case 5:F_By_Ad

17、dress(Flight,2);break;case 6:F_By_fare(Flight);break;default :cout謝謝惠顧！ endl;break;coutch;if(ch=Y|ch=y) break;/查 詢系統(tǒng)/通過航班號實(shí)現(xiàn)二分查找法查找void F_By_FN(flight F口)int low=0,high=N,mid;char Num10;coutNum;Cout_info1();while(low=high)mid=(low+high)/2;if(strcmp(Num,Fmid.flight_number)=0) Cout_info2_2(F,mid);brea

18、k;else if(strcmp(Num,Fmid.flight_number)0) high=mid-1;else low=mid+1;/通過起飛/到達(dá)時(shí)間查詢void F_By_Time(flight F口,int Time) int T,i;coutT;Cout_info1();for(i=0;iN;i+) if(Time=1) /按起飛時(shí)間查詢if(T=Fi.start_time) Cout_info2_2(F,i);if(Time=2) /按抵達(dá)時(shí)間查詢if(T=Fi.arrived_time) Cout_info2_2(F,i); /通過站點(diǎn)查詢void F_By_Address(

19、flight F口,int AD) char str10;coutstr;Cout_info1();for(int i=0;iN;i+) if(AD=1) / 按起點(diǎn)站查詢if(strcmp(str,Fi.start_address)=0) Cout_info2_2(F,i); if(AD=2) / 按目的站查詢 if(strcmp(str,Fi.arrived_address)=0) Cout_info2_2(F,i);) ) )/通過票價(jià)范圍查詢void F_By_fare(flight F)(int T1,T2,i;coutT1;coutT2;Cout_info1();for(i=0;i

20、N;i+)(if(T1=Fi.fare) Cout_info2_2(F,i);)/主 函數(shù)int main()(RadixList p=element;for(int i=0;iN;i+)elementi.next=&elementi+1;element10.next=NULL;radixSort(&p, D, R); /基數(shù)排序output_ALL_info1(element); /輸出排序后的有序序列(航班信息)copy(Flight,element); /另存儲排序后的航班信息mainmenu(); / 給出主菜單 return 0;Radixsort 函數(shù)Copy函數(shù)Mainmenu

21、函數(shù)5.調(diào)試分析1.主菜單程序Flo act cch40DO ： 上海134E7P4fi每日CHJ733738letGTC 10107_ 1250JL有關(guān)于時(shí)間和空間復(fù)雜度的分析因?yàn)楸驹O(shè)計(jì)采用的是基數(shù)排序算法，時(shí)間復(fù)雜度的任何情況都為O（d*n）,空間復(fù)雜度為O (n)6、綜合實(shí)踐總結(jié).綜合實(shí)踐過程的收獲.通過本次綜合實(shí)踐，讓我更好的了解和認(rèn)識了 CS言和C+,經(jīng)過自己編程的鍛煉讓我 鞏固了自己在C語言和C+坊面的基礎(chǔ)知識，現(xiàn)將本次綜合實(shí)踐過程中的學(xué)習(xí)收獲總結(jié)如下： 數(shù)據(jù)說明次序應(yīng)當(dāng)規(guī)范化，使數(shù)據(jù)屬性容易查找，也有利于測試、排錯(cuò)和維護(hù)。說明 的先后次序應(yīng)固定，應(yīng)按邏輯功能排序，邏輯功能塊內(nèi)建議

22、采用下列順序：整型說明、實(shí) 型說明、字符說明、邏輯量說明。如果設(shè)計(jì)了一個(gè)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，應(yīng)當(dāng)通過注釋對其變 量的含義、用途進(jìn)行說明。程序注釋是程序員與日后的程序讀者之間通信的重要手段之一， 注釋分為文件注釋、函數(shù)注釋和功能注釋。正規(guī)程序的注釋應(yīng)注意：注釋行的數(shù)量占到整 個(gè)源程序的1/3到1/2。文件注釋位于整個(gè)源程序的最開始部分，注釋后空兩行開始程序正文。它包括：程序標(biāo)題。目的、功能說明。文件作者、最后修改日期等說明。函數(shù)注釋通 常置于每函數(shù)或過程的開頭部分，它應(yīng)當(dāng)給出函數(shù)或過程的整體說明對于理解程序本身具 有引導(dǎo)作用。功能性注釋嵌在源程序體中，用于描述其后的語句或程序段做什么工作，也 就是解

23、釋下面要做什么，或是執(zhí)行了下面的語句會(huì)怎么樣。而不要解釋下面怎么做，因?yàn)?解釋怎么做常常與程序本身是重復(fù)的。.遇到問題以及解決問題的思路和方法在編程中，經(jīng)常會(huì)因?yàn)橐恍┬∶?dǎo)致程序無法調(diào)試通過，總結(jié)一下經(jīng)驗(yàn)，還是主要 因?yàn)樽约浩綍r(shí)馬虎，缺少編程經(jīng)驗(yàn)造成的，下面總結(jié)幾個(gè)自己在編程中出現(xiàn)的錯(cuò)誤和解決 的經(jīng)驗(yàn)：if語句對出錯(cuò)的處理：If語句是我最喜歡用的用語句，因?yàn)樗唵巍⒅庇^，只有兩種選擇，但就是這樣簡單 的語句，在本次編程中，讓我感覺到它的深?yuàn)W。當(dāng)我們遇到if語句出錯(cuò)的時(shí)候，首先先檢測輸入量的合法性，然后再正常處理。這樣做的好處是突出了錯(cuò)誤的條件，讓別人在使用 你的函數(shù)的時(shí)候，第一眼就能看到不合

24、法的條件，于是就會(huì)更下意識的避免。另外還要注 意不要使用空的if else 語句。如 if(cMychar =A) TOC o 1-5 h z if(cMychar =Z)printf(This is a letter”)；elseprintf(This is not a letter”)；else到底是否定哪個(gè)if容易引起誤解?？赏ㄟ^加避免誤解。盡量減少使用“否定”條件的條件語句。如：把 if( !( (cMychar 9)改為 if( (cMychar= 0 ) & (cMychar= 9)scanf語句問題也許這個(gè)問題很多人注意到了， 但卻都沒有理會(huì)它，scanf存在讀取空格的錯(cuò)誤，我在 調(diào)試一個(gè)程序時(shí)發(fā)現(xiàn)由scanf語句下，建立輸入的文本文件時(shí)，第一行竟然是空白的，而 當(dāng)我換用C+叫言中的cin時(shí)，該問題被解決了。getch函數(shù)問題其實(shí)這個(gè)是跟上面scanf語句問題相關(guān)的，scanf讀取了空格，而與getch連用時(shí)，getch 接收到了空格信息，使getch語句無效這些都是小問題，但卻會(huì)導(dǎo)致程序無法運(yùn)行或者運(yùn)行錯(cuò)誤。解決這些問題的最基本的 方法就是在編