【文章內(nèi)容簡介】 83。 34 北華航天工業(yè)學院課程報告 4 第 1 章 問題描述 題目內(nèi)容 交通咨詢系統(tǒng)設(shè)計 設(shè)計一個交通咨詢系統(tǒng)，能讓旅客咨詢從任一城市頂點到另一城市頂點之間的最短路徑（里程）或最低 花費或最少時間等問題。對于不同咨詢要求，可輸入城市間的路程或所需時間或所需費用。 一元高次多項式的加、減、乘運算 用鏈表表示一元高次多項式，實現(xiàn)兩個多項式的加、減、乘運算。 基本要求 交通咨詢系統(tǒng)設(shè)計 1．創(chuàng)建圖的存儲結(jié)構(gòu)使用鄰接矩陣。 2．查詢分為兩類。一類是能讓旅客咨詢從一個城市 到另外所有城市的 最短路徑（要求使用迪杰斯特拉算法），顯示出所有路徑，按升序排列。第二類是任意兩個城市間的最短路徑（要求使用弗洛伊德算法），顯示最短路徑。 3．按給定交通地圖完成以上功能。 一元高次多項式的加、減、乘運算 ，將每個子項看成是由系數(shù)和指數(shù)兩部分組成。 ，以鏈表作為存儲結(jié)構(gòu)。 、相減和相乘運算。 ，查看運算結(jié)果。 ： 創(chuàng)建 加法 減法 乘法 顯示 退出 北華航天工業(yè)學院課程報告 5 測試數(shù)據(jù) 交通咨詢系統(tǒng)設(shè)計 任意輸入 所需要查找的一個 或兩個城市，然后查找最短距離、最少花費和最短時間。 一元高次多項式的加、減、乘運算 2X^4+3X^4=5X^4 6X^3+3X^5=6X^3+3X^5 7X^9*4X^5=28X^45 北華航天工業(yè)學院課程報告 6 第 2 章 需求分析 功能說明 交通咨詢系統(tǒng)設(shè)計 查詢分為兩類。一類是能讓旅客咨詢從一個城市 到另外所有城市的 最短路徑，顯示出所有路徑，按升序排列。第二類是任意兩個城市間的最短路徑，顯示最短路徑。 一元高次多項式的加、減、乘運算 描述多項式時，將每個子項看成是由系數(shù)和指數(shù)兩部分組成。 輸入并創(chuàng)建一元多項式，以鏈表作為存儲結(jié)構(gòu)。 實現(xiàn)兩個多項式的相加、相減和相乘運算。 顯示多項式，查看運算結(jié)果。 輸入說明 交通咨詢 系統(tǒng)設(shè)計 用戶根據(jù)自己所需要的利用交通系統(tǒng)查詢的功能自己進行查詢。 一元高次多項式的加、減、乘運算 程序運行后顯現(xiàn)提示信息，由用戶輸入兩個多項式，由用戶自行選擇加減乘功能進行運算。 輸出說明 交通咨詢系統(tǒng)設(shè)計 根據(jù)用戶不同的選擇功能輸出不同。 北華航天工業(yè)學院課程報告 7 一元高次多項式的加、減、乘運算 用戶輸入數(shù)據(jù)完畢，程序?qū)⑤敵鲞\算結(jié)果 。 測試數(shù)據(jù) 交通咨詢系統(tǒng)設(shè)計 用戶自行選擇功能，可進行按序號查找和按名稱查找。 一元高次多項式的加、減、乘運算 測試數(shù)據(jù)應 為兩組整數(shù)，正負都沒有關(guān)系。 北華航天工業(yè)學院課程報告 8 第 3 章 概要設(shè)計 抽象數(shù)據(jù)類型定義 交通咨詢系統(tǒng)設(shè)計 為實現(xiàn)上程序功能，應 創(chuàng)建圖的存儲結(jié)構(gòu)并使用鄰接矩陣 表示集合 。 1． 建圖的存儲結(jié)構(gòu) typedef struct { int vexs[max]。 string name[max]。 int cost[max][max]。 int distance[max][max]。 int time[max][max]。 int vnm,enm。 }mgraph。 2． 鄰接矩陣 void create(mgraph amp。g,int n,int e) { int i,j。 =n。 =e。 for(i=1。i=。i++) [i]=i。 //對應數(shù)組下標即為城市代號 for(i=1。i=。i++) {//初始化 for(j=1。j=。j++) { 北華航天工業(yè)學院課程報告 9 if(i==j) { [i][j]=0。 [i][j]=0。 [i][j]=0。 } else { [i][j]=MAX。 [i][j]=MAX。 [i][j]=MAX。 } } } 一元高次多項式的加、減、乘運算 鏈表和數(shù)組的使用，下面是鏈表的定義 ： typedef struct{ double xishu。 double zhishu。 }LNode,*LinkList。 數(shù)組的定義： LNode a[2],b[3]。 程序模塊結(jié)構(gòu) 交通咨詢系統(tǒng)設(shè)計 本程序包含 主程序、 最少花費、最短距離、最少時間模塊和迪杰斯特拉算法、弗洛伊德算法 模塊等 三個模塊 。 最少花費、最短距離、最少時間模 塊實現(xiàn) 判斷兩城市之間信息。 迪杰斯特拉算法、弗洛伊德算法 模塊實現(xiàn) 兩城市之間的各種信息的具體計算。 三個模塊間的調(diào)用關(guān)系如圖 31 所示。 北華航天工業(yè)學院課程報告 10 圖 31 模塊間的調(diào)用關(guān)系 圖 一元高次多項式的加、減、乘運算 本程序包含主程序、加減乘運算函數(shù)模塊 顯示模塊三個模塊。 加減乘模塊 是用來計算一元高次多項式的加減乘的核心模塊。 顯示模塊是用來顯示計算結(jié)果的模塊。 三個模塊間的調(diào)用關(guān)系如圖 32 所示。 圖 32 模塊間的調(diào)用關(guān)系圖 北華航天工業(yè)學院課程報告 11 第 4 章 詳細設(shè)計 定義的數(shù)據(jù)類型 交通咨詢系統(tǒng)設(shè)計 1．元素類型、結(jié)點類型和指針類型 typedef struct { int vexs[max]。 string name[max]。 int cost[max][max]。 int distance[max][max]。 int time[max][max]。 int vnm,enm。 }mgraph。 st。 2． 圖和鄰接矩陣的定義 //圖的有關(guān)信息 typedef struct { int sign。 int len。 int hour。 int spend。 }save。 //存放城市代號和距離 void create(mgraph amp。g,int n,int e) { int i,j。 =n。 =e。 北華航天工業(yè)學院課程報告 12 for(i=1。i=。i++) [i]=i。 //對應數(shù)組下標即為 城市代號 for(i=1。i=。i++) {//初始化 for(j=1。j=。j++) { if(i==j) { [i][j]=0。 [i][j]=0。 [i][j]=0。 } else { [i][j]=MAX。 [i][j]=MAX。 [i][j]=MAX。 } } } 3． 迪杰斯特拉算法 和弗洛伊德算法 利用 迪杰斯特拉算法和弗洛伊德算法計算最少花費、最短距離、最少時間。 其 基本操作的偽碼算法如下： 迪杰斯特拉一城至諸城最少花費 void shortestcost(mgraph g,int v0) { int i,v,pre,w,min,k,j。 int final[max]。 int p[max]。 save d[max]。 int m,n。 for(v=1。v=。v++) 北華航天工業(yè)學院課程報告 13 { final[v]=0。 d[v].spend=[v0][v]。 d[v].sign=v。 p[v0]=1。 if(d[v].spendMAXamp。amp。v!=v0) p[v]=v0。 if(d[v].spend==MAX) p[v]=2。 } d[v0].spend=0。 final[v0]=1。 for(i=2。i=。i++) { min=MAX。 for(w=1。w=。w++) if(!final[w]) if(d[w].spendmin) { v=w。 min=d[w].spend。 } final[v]=1。 for(w=1。w=。w++) {//修改 d 中存放的最短距離和前驅(qū)結(jié)點 if(!final[w]amp。amp。(min+[v][w]d[w].spend)) { d[w].spend=min+[v][w]。 d[w].sign=w。 p[w]=v。 } } } //選擇排序法 for(i=1。i。i++) 北華航天工業(yè)學院課程報告 14 { k=i。 for(j=i+1。j=。j++) if(d[j].spendd[k].spend) k=j。 if(k!=i) { n=d[k].sign。 d[k].sign=d[i].sign。 d[i].sign=n。 m=d[k].spend。 d[k].spend=d[i].spend。 d[i].spend=m。 } } for(i=1。i=。i++) { if(d[i].sign!=v0) { cout 從 setw(2)v0到 setw(2)d[i].sign城市最少花費：setw(4)d[i].spend 。 cout 所經(jīng)過的路徑： 。 cout[d[i].sign]。 pre=p[d[i].sign]。 while(pre0) { cout[pre]。 pre=p[pre]。 } coutendl。 } } //迪杰斯特拉一城至諸城最短時間 void shortesttime(mgraph g,int v0) { 北華航天工業(yè)學院課程報告 15 int i,v,pre,w,min,k,j。 int final[max]。 int p[max]。 save d[max]。 int m,n。 for(v=1。v=。v++) { final[v]=0。 d[v].hour=[v0][v]。 d[v].sign=v。 p[v0]=1。 if(d[v].hourMAXamp。amp。v!=v0) p[v]=v0。 if(d[v].hour==MAX) p[v]=2。 } d[v0].hour=0。 final[v0]=1。 for(i=2。i=。i++) { min=MAX。 for(w=1。w=。w++) if(!final[w]) if(d[w].hourmin) { v=w。 min=d[w].hour。 } final[v]=1。 for(w=1。w=。w++) {//修改 d 中存放的最短距離和前驅(qū)結(jié)點 if(!final[w]amp。amp。(min+[v][w]d[w].hour)) { d[w].hour=min+[v][w]。 d[w].sign=w。 北華航天工業(yè)學院課程報告 16 p[w]=v。 } } } //選擇排序法 for(i=1。i。i++) { k=i。 for(j=i+1。j=。j++) if(d[j].hourd[k].hour) k=j。 if(k!=i) { n=d[k].sign。 d[k].sign=d[i].sign。 d[i].sign=n。 m=d[k].hour。 d[k].hour=d[i].hour。 d[i].hour=m。 } } for(i=1。i=。i++) { if(d[i].sign!=v0) { cout 從 setw(2)v0到 setw(2)d[i].sign城市最短時 間：setw(2)d[i].hour 。 cout 所經(jīng)過的路徑： 。 cout[d[i].sign]。 pre=p[d[i].sign]。 while(pre0) { cout[pre]。 pre=p[pre]。 } 北華航天工業(yè)學院課程報告 17 coutendl。 } } } //迪杰斯特拉算法 void shortestdistance(mgraph g,int v0) { int i,v,pre,w,min,k,j。 int final[max]。 int p[max]。 save d[max]。 int m,n。 for(v=1。v=。v++) { final[v]=0。 d[v].len=[v0][v]。 d[v].sign=v。 p[v0]=1。 if(d[v].lenMAXamp。amp。v!=v0) p[v]=v0。 if(d[v].len==MAX) p[v]=2。 } d[v0].len=0。 final[v0]=1。 for(i=2。i=。i++) { min=MAX。 for(w=1。w=。w++) if(!final[w]) if(d[w].lenmin) { v=w。 min=d[w].len。 } 北華航天工業(yè)學院課程報告 18 final[v]=1。 for(w=1。w=。w++) {//修改 d 中存放的最短距離和前驅(qū)結(jié)點 if(!final[w]amp。amp。(min+[v][w]d[w].len)) { d[w].len=min+[v][w]。 d[w].sign=w。 p[w]=v。 } } } //選擇排序法 for(i=1。i。i++) { k=i。 for(j=i+1。j=。j++) if(d[j].lend[k].len) k=j。 if(k!=i) { n=d[k].sign。 d[k].sign=d[i].sign。 d[i].sign=n。 m=d[k].len。 d[k].len=d[i].len。 d[i].len=m。 } } for(i=1。i=。i++) { if(d[i].sign!=v0) { cout 從 setw(2)v0到 setw(2)d[i].sign城市最短路徑：setw(4)d[i].len 。 cout 所經(jīng)過的路徑： 。 北華航天工業(yè)學院課程報告 19 cout[d[i].sign]。 pre=p[d[i].sign]。 while(pre0) { cout[pre]。 pre=p[pre]。 } coutendl。 } } } 4．主函數(shù)的偽碼算法 void main() { mgraph g。 create(g,25,30)。 int num。 string name。 do { cout 交通咨詢系統(tǒng) endl。 cout ++++++++++++++++++++++ 城 市 名 稱 及 代 碼+++++++++++++++++++++++ endl。 cout 1 ：北京 2 ：長春 3 ：成都 4 ：大連 5 ：福州 6 ：廣州 7 ：貴陽 endl。 cout 8 ：哈爾濱 9 ：呼和浩特 10：昆明 11：蘭州 12：柳州 13：南昌endl。 cout 14：南寧 15：上海 16：沈陽 17：深圳 18：天津 19：武漢endl。 cout 20：烏魯木齊 21：西安 22：西寧 23：徐州 24：鄭州 25：株州endl。 cout ++