【導(dǎo)讀】第1章問題描述·························································································4. 交通咨詢系統(tǒng)設(shè)計·····································································4. 一元高次多項式的加、減、乘運算····

　　

【正文】 [13][15]=260。 [15][13]=260。 [5][13]= [13][5]= [11][21]=210。 [21][11]=210。 [24][21]=190。 [21][24]=190。 北華航天工業(yè)學(xué)院課程報告 37 [12][25]=230。 [25][12]=230。 [23][15]=232。 [15][23]=232。 [6][25]=225。 [25][6]=225。 [22][11]=70。 [11][22]=70。 [9][1]=230。 [1][9]=230。 [24][23]=95。 [23][24]=95。 [18][16]=240。 [16][18]=240。 [8][2]=72。 [2][8]=72。 [10][3]=380。 [3][10]=380。 [14][12]=74。 [12][14]=74。 [19][24]=185。 [24][19]=185。 [13][15]=260。 [15][13]=260。 [5][13]= [13][5]= [11][21]=210。 [21][11]=210。 [24][21]=190。 [21][24]=190。 [1][18]=55。 [18][1]=55。 [16][4]= [4][16]= [7][3]=330。 [3][7]=330。 [7][10]=225。 [10][7]=225。 [7][25]=310。 [25][7]=310。 [19][25]=145。 [25][19]=145。 [13][25]=105。 [25][13]=105。 [6][17]=265。 [17][6]=265。 //時間的賦值 [1][18]=1。 [18][1]=1。 [1][24]=13。 [24][1]=13。 [5][13]=10。 [13][5]=10。 [6][25]=11。 [25][6]=11。 [6][17]=14。 [17][6]=14。 [7][3]=21。 [3][7]=21。 [7][10]=11。 [10][7]=11。 [7][12]=10。 [12][7]=10。 [7][25]=20。 [25][7]=20。 [8][2]=2。 [2][8]=2。 [9][1]=12。 [1][9]=12。 北華航天工業(yè)學(xué)院課程報告 38 [9][11]=24。 [11][9]=24。 [10][3]=23。 [3][10]=23。 [11][21]=5。 [21][11]=5。 [12][25]=11。 [25][12]=11。 [13][25]=4。 [25][13]=4。 [13][15]=14。 [15][13]=14。 [14][12]=2。 [12][14]=2。 [16][2]=3。 [2][16]=3。 [18][16]=13。 [16][18]=13。 [18][23]=5。 [23][18]=5。 [21][3]=15。 [3][21]=15。 [19][24]=4。 [24][19]=4。 [23][15]=12。 [15][23]=12。 [22][11]=2。 [11][22]=2。 [24][23]=3。 [23][24]=3。 [24][21]=11。 [21][24]=11。 [16][4]=7。 [4][16]=7。 [19][25]=3。 [25][19]=3。 [20][11]=32。 [11][20]=32。 //里程的賦值 [1][9]=668。 [9][1]=668。 [1][18]=137。 [18][1]=137。 [1][24]=695。 [24][1]=695。 [2][8]=242。 [8][2]=242。 [2][16]=305。 [16][2]=305。 [3][7]=967。 [7][3]=967。 [3][10]=1100。 [10][3]=1100。 [4][16]=397。 [16][4]=397。 [5][13]=622。 [13][5]=622。 [6][17]=140。 [17][6]=140。 [6][25]=675。 [25][6]=675。 [7][10]=639。 [10][7]=639。 [7][12]=607。 [12][7]=607。 [7][25]=902。 [25][7]=902。 [9][11]=1145。 [11][9]=1145。 北華航天工業(yè)學(xué)院課程報告 39 [11][20]=1892。 [20][11]=1892。 [11][21]=676。 [21][11]=676。 [12][25]=672。 [25][12]=672。 [13][25]=367。 [25][13]=367。 [13][15]=825。 [15][13]=825。 [14][12]=255。 [12][14]=255。 [18][16]=704。 [16][18]=704。 [18][23]=674。 [23][18]=674。 [19][24]=534。 [24][19]=534。 [19][25]=409。 [25][19]=409。 [21][3]=842。 [3][21]=842。 [23][15]=651。 [15][23]=651。 [22][11]=216。 [11][22]=216。 [24][23]=349。 [23][24]=349。 [24][21]=511。 [21][24]=511。 } //迪杰斯特拉算法 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。 } 北華航天工業(yè)學(xué)院課程報告 40 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。 } 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。 北華航天工業(yè)學(xué)院課程報告 41 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)過的路徑： 。 cout[d[i].sign]。 pre=p[d[i].sign]。 while(pre0) { cout[pre]。 pre=p[pre]。 } coutendl。 } } } //迪杰斯特拉一城至諸城最少花費 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++) { final[v]=0。 d[v].spend=[v0][v]。 北華航天工業(yè)學(xué)院課程報告 42 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++) { k=i。 for(j=i+1。j=。j++) 北華航天工業(yè)學(xué)院課程報告 43 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) { int i,v,pre,w,min,k,j。 int final[max]。 北華航天工業(yè)學(xué)院課程報告 44 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。 p[w]=v。 } 北華航天工業(yè)學(xué)院課程報告 45 } } //選擇排序法 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]。 } coutendl。 } 北華航天工業(yè)學(xué)院課程報告 46 } } //弗洛伊德算法 void shortestdistance2(mgraph g) { int v,w,u,m,n,k。 int p[max][max],d[max][max]。 //后繼結(jié)點、最短距離的二維數(shù)組 for(v=1。v=。v++) for(w=1。w=。w++) { d[v][w]=[v][w]。 if(d[v][w]MAX) p[v][w]=w。 else if(v!=w) p[v][w]=2。 else p[v][w]=1。 } //修改后繼結(jié)點和最短里程 for(u=1。u=。u++) { for(v=1。v=。v++) for(w=1。w=。w++) if(d[v][u]+d[u][w]d[v][w]) { d[v][w]=d[v][u]+d[u][w]。 p[v][w]=p[v][u]。 } } cout 請輸入查詢的代碼： 。 cinmn。 while(m1||m25||n1||n25) { cout 無此代碼的城市！請重新輸入： endl。 北華航天工業(yè)學(xué)院課程報告 47 cinmn。 } cout 從 setw(2)m 到 setw(2)n 最短距離是：setw(4)d[m][n]endl。 cout 兩個城市的最短路徑是： 。 cout[m]。 k=p[m][n]。 while(k!=n) { cout[k]。 k=p[k][n]。 } cout[n]endl。 } //弗洛伊德兩城最少花費 void shortestcost2(mgraph g) { int v,w,u,m,n,k。 int p[max][max],d[max][max]。 //后繼結(jié)點、最短距離的二維數(shù)組 for(v=1。v=。v++) for(w=1。w=。w++) { d[v][w]=[v][w]。 if(d[v][w]MAX) p[v][w]=w。 else if(v!=w) p[v][w]=2。 else p[v][w]=1。 }