【正文】 學(xué) 號： 課 程 設(shè) 計題 目 最便宜航空線路求解學(xué) 院管理學(xué)院專 業(yè)信息管理與信息系統(tǒng)班 級姓 名指導(dǎo)教師2014年07月03日課程設(shè)計任務(wù)書學(xué)生姓名： 專業(yè)班級： 信管 指導(dǎo)教師： 工作單位： 管理學(xué)院 題 目：最便宜航空線路求解初始條件：【問題描述】飛機(jī)是遠(yuǎn)途旅行必不可少的工具，但是高昂的價格也令人頗費(fèi)思量，因此人們往往寧愿用時間來換金錢而選擇較慢的交通工具。不過，當(dāng)航班線路變得豐富之后，人們也發(fā)現(xiàn)很多時候選擇直達(dá)航班往往并非最省錢的路徑，比如飛往美國選擇從韓國轉(zhuǎn)機(jī)就比直飛要便宜多了（雖然這樣有墜機(jī)的危險）。這樣一來，當(dāng)采用曲線行進(jìn)能達(dá)到省錢也省時間的目的時，坐飛機(jī)還是可以接受的。為了能夠更好地解決路徑的選擇問題，我們模擬一下通過合適的算法來選出最優(yōu)航空線路。參考，自選至少10個城市和至少20條航線（不含中轉(zhuǎn)），要求任意兩城市間都可達(dá)（這并不意味著兩個城市之間就一定有直飛航班，比如大陸到臺灣），且至少有2條可選飛行路線。預(yù)先定義每條航線的最高定價，航線票價每季度都有折扣機(jī)會，但并非必須。每條線路每季度的折扣率由隨機(jī)函數(shù)產(chǎn)生，～（小數(shù)點(diǎn)后取兩位）。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求、說明書撰寫等具體要求）本程序不考慮機(jī)場建設(shè)費(fèi)和燃油附加費(fèi)，只計算機(jī)票價格，將其作為路徑上的權(quán)值處理，耗費(fèi)矩陣存儲結(jié)構(gòu)自行選擇。在真實(shí)的情形中，同一線路每天可能有許多航班，也可能每周只有一兩趟航班，即便同一天的航班早晚價格也可能有所不同。為簡便計，假定每條線路每天只有一趟航班，不考慮航空公司的差別。 時間安排：序號設(shè)計內(nèi)容所用時間1問題分析和任務(wù)定義2數(shù)據(jù)類型和系統(tǒng)設(shè)計3編碼實(shí)現(xiàn)和靜態(tài)檢查3天4上機(jī)準(zhǔn)備和上機(jī)調(diào)試2天5總結(jié)和整理設(shè)計報告1天合 計7天指導(dǎo)教師簽名： 2014年 06月25日 系主任（或責(zé)任教師）簽名： 2014年06月25日最便宜航空線路求解1. 需求分析 基本要求（1）所有原始數(shù)據(jù)一律事先用文本文件保存，讀入數(shù)據(jù)時從文件獲取。（2）航班價格可以用隨機(jī)函數(shù)生成，但建議從網(wǎng)上直接復(fù)制真實(shí)數(shù)據(jù)。（3）可輸出所有城市名稱以及每一城市所有可直飛到達(dá)的城市列表。（4）可輸出任一指定直飛線路（若沒有則顯示無直飛航班）四個季度的全票和折扣價格。（5）輸入月份、起始城市和目的城市名稱，程序能顯示出最經(jīng)濟(jì) 的中轉(zhuǎn)路線選擇方案。 輸入 （1）（共10個城市）不同航線（共24條航線）的最高價格輸入，四個季度有相同的最高價格。 （2）每條線路每季度的折扣率由隨機(jī)函數(shù)產(chǎn)生，～（小數(shù)點(diǎn)后取兩位），四個季度有不同的折扣。 （3）運(yùn)行程序時需根據(jù)要求從鍵盤輸入相應(yīng)指令，保證程序的正確運(yùn)行。（1）輸出所有城市名以及每一城市所有可直飛到達(dá)的城市列表（按城市名拼音升序排列）：始發(fā)地 可直飛目的地北京 長春 廣州 杭州 昆明 上海 首爾 武漢 香港……首爾 北京 上海 臺北 香港……（2）輸出指定線路四個季度的折扣和全價：輸入：北京臺北輸出：無直飛航班輸入：北京廣州輸出：季度 全票價格 折扣 折后價格（不計小數(shù)，四舍五入） 1 1240 806 2 1192 834 3 1475 679 4 1230 1070（3）輸入月份、起始城市和目的城市名稱，輸出最佳方案：輸入：5 北京臺北輸出：最佳線路：北京香港，1503，香港臺北，791，合計2294輸入：7 廣州首爾輸出：最佳線路：廣州上海，880，上海首爾，773，合計1653輸入：10 武漢上海輸出：最佳線路：武漢上海，278，合計278……：（1） 。若文件名輸入正確且文件無錯誤，則顯示主菜單。若文件名輸入錯誤或文件有錯誤，則顯示“打開輸入文件出錯”。（2） 根據(jù)主菜單提示選擇需要執(zhí)行的功能。若輸入功能序號在0—4之間，則執(zhí)行相應(yīng)的功能。若輸入功能序號不在0—4之間，則顯示“出錯啦!!!請在04之間選擇!!”和主菜單，需重新選擇。（3） 選擇1，輸出城市列表及相應(yīng)代碼。（4） 選擇2，輸出所有城市名以及每一城市所有可直飛到達(dá)的城市列表（按城市名拼音升序排列）。（5） 選擇3，先顯示城市列表及相應(yīng)代碼，方便后面的輸入操作，根據(jù)提示“請輸入起始城市和目的城市的代碼，中間以空格隔開，范圍(1 10)”輸入兩個城市代碼，若兩城市間有直飛航班則顯示指定線路四個季度的折扣和全價。若兩城市間無直飛航班則顯示“無直飛航班”。（6） 選擇4，顯示“請輸入月份(請在112之間選擇)：”若月份輸入正確，則先顯示城市列表及相應(yīng)代碼，方便后面的輸入操作，根據(jù)提示“請輸入起始城市和目的城市的代碼，中間以空格隔開，范圍(1 10)”輸入兩個城市代碼，若代碼輸入正確，則顯示最佳方案。若月份輸入錯誤，則顯示“輸入出錯”。若城市代碼輸入錯誤，則顯示“出錯啦!!!”。（7） 選擇0，則直接退出程序。（8） 在每一個功能執(zhí)行完后，都會提示繼續(xù)執(zhí)行還是返回主菜單。12191584武漢箭頭流程廈門北京261115751573743大連鄭州廣州1006長沙11301903612上海1461天津深圳23462. 概要設(shè)計 抽象數(shù)據(jù)類型定義本程序運(yùn)用了關(guān)于圖這種數(shù)據(jù)結(jié)構(gòu)，它的抽象數(shù)據(jù)類型定義如下：typedef struct unDiGraph{ int numVerts。 //結(jié)點(diǎn) costAdj cost。 //鄰接矩陣}unDiGraph,*UNG。基本操作：unDiGraph* CreateCostG()操作結(jié)果：構(gòu)造帶權(quán)(費(fèi)用)圖。PathMat *Floyed(unDiGraph *D) 操作結(jié)果：Floyed函數(shù) 求任意兩點(diǎn)的最短路徑。 主程序流程及各程序模塊之間的層次（調(diào)用）關(guān)系 Main函數(shù) 輸出方式1 f_money1()pri() 查看城市 輸出方式3 f_money3() 輸出方式2 f_money2() 退出程序 pr(i,0) Floyed() Floyed() pr(Bcity,0) pr(Bcity,0) prn_pass(Bcity,Ecity) prn_pass(Bcity,Ecity) pr(Ecity,0) pr(Ecity,0)3. 詳細(xì)設(shè)計 數(shù)據(jù)類型（1）主界面包括 （按城市名拼音升序排列） ，輸出指定線路四個季度的折扣和全價 4. 輸入月份、起始城市和目的城市名稱，輸出最佳方案 （2）程序的模塊為include include include //需引用的頭文件define INF 65535 //定義一個最大數(shù)為無窮值,表示兩城市之間無直飛航班define MAX 23typedef int costAdj[MAX+1][MAX+1]。//圖鄰接矩陣從1開始記數(shù)int Path[MAX+1][MAX+1]。//圖鄰接矩陣從1開始記數(shù)typedef struct unDiGraph{ int numVerts。 //結(jié)點(diǎn) costAdj cost。 //鄰接矩陣}unDiGraph,*UNG。 //圖的定義costAdj B,L。void pr(int i)//選擇城市void pri()//輸出城市unDiGraph *CreateCostG()//構(gòu)造帶權(quán)(費(fèi)用)圖 返回首地址G：void Floyed(unDiGraph *D,unDiGraph *M) //Floyed函數(shù) 求任意兩點(diǎn)的最短路徑：void prn_pass(int i,int j) //為了求從i到j(luò)的最短路徑，只需要調(diào)用如下的過程void f_money1()//輸出所有城市名及所有可直飛到達(dá)的城市列表（按城市名拼音升序排列）void f_money2()//輸入起始城市和目的城市名稱，輸出指定線路四個季度的折扣和全價 void f_money4()//輸入月份、起始城市和目的城市名稱，輸出最佳方案int LineNumStat(FILE *fp)//統(tǒng)計文本文件的行數(shù)void main()//main函數(shù) 偽碼算法（1）pr() 選擇城市begin0=hIf j