地鐵建設(shè)問(wèn)題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(編輯修改稿)
2025-04-21 12:40 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 !=0){if(a[i].lowcosta[k].lowcost)k=i。}}return k。} PRIM算法及輸出void MiniSpanTree_PRIM(Graph g,char a[10]){struct tree closedge[M]。 int i,j,k,money=0。 k=locatevex(amp。g,a)。for(i=0。i。i++) {if(i!=k) { closedge[i].lowcost=[k][i]。 //兩轄區(qū)k，i之間的距離closedge[i].weizhi=k。 //與轄區(qū)i相鄰的最近的轄區(qū)設(shè)為轄區(qū)k}} closedge[k].lowcost=0。//初始化，U={u}printf(********根據(jù)您的輸入建立鄰接表為:********\n)。 for(i=0。i。i++) {for(j=0。j。j++) { printf(|%d| ,[i][j])。 } printf(\n\n)。 } printf(****得到應(yīng)建設(shè)地鐵的轄區(qū)及之間權(quán)值為:****\n)。 for(i=1。i。i++) { k=minimun(closedge,g)。 //求出最小生成樹T的下一個(gè)結(jié)點(diǎn)，第k結(jié)點(diǎn) money+=closedge[k].lowcost。 printf(%d:%s %s %d\n,i,[closedge[k].weizhi],[k],closedge[k].lowcost)。 //輸出生成樹的邊 closedge[k].lowcost=0。 //第k頂點(diǎn)并入U(xiǎn)集 for(j=0。j。j++) { if([k][j]closedge[j].lowcost) //新頂點(diǎn)并入集后，選擇新的邊，將小的邊放到輔助數(shù)組中{ closedge[j].weizhi=k。 closedge[j].lowcost=[k][j]。 }}}printf(******據(jù)統(tǒng)計(jì)地鐵的總建設(shè)路程為：%d *******\n,money)。}4,3,6主函數(shù)模塊void main(){int i。 Graph g。 char a[10]。 i=creatgraph(amp。g)。 if(i){printf(***********請(qǐng)輸入起始地點(diǎn)為：************\n)。 scanf(%s,a)。 MiniSpanTree_PRIM(g,a)。}printf(**********感謝使用本程序，謝謝！*********\n)。}測(cè)試數(shù)據(jù)：圖 3，如圖4所示：圖 4，依次輸入各個(gè)區(qū)域代號(hào)和邊的權(quán)值，如圖5所示：圖 5，輸入地鐵站的起始地點(diǎn)如圖6所示：圖 6，如圖7所示：圖 7在設(shè)計(jì)之初，我對(duì)于整個(gè)算法的思路的理解并不清晰。最首要的任務(wù)就是選擇合適的計(jì)算思路，并加以實(shí)現(xiàn)。經(jīng)過(guò)查閱，我發(fā)現(xiàn)解決此類問(wèn)題的核心思想就是最小生成樹的生成。于是我選用普利姆算法和簡(jiǎn)潔明了的鄰接矩陣存儲(chǔ)結(jié)構(gòu)。在實(shí)驗(yàn)過(guò)程中遇到的最大難題是普里姆算法的編寫。通過(guò)在書上和網(wǎng)上查閱資料，詢問(wèn)同學(xué)老師，結(jié)合之前上機(jī)實(shí)驗(yàn)的經(jīng)驗(yàn)，我理清思路。經(jīng)過(guò)編寫，調(diào)試，最終完成了程序的設(shè)計(jì)。本程序算法的時(shí)間復(fù)雜度為O(n^3)，空間復(fù)雜度為O(2n) 表達(dá)是求值，主要是運(yùn)用棧的相關(guān)知識(shí)解決的問(wèn)題。在此問(wèn)題之中要運(yùn)用到函數(shù)的多次調(diào)用等等。，作出相應(yīng)的應(yīng)對(duì)措施：如輸入轄區(qū)之間的權(quán)值時(shí)，當(dāng)輸入錯(cuò)誤的轄區(qū)時(shí)會(huì)有報(bào)錯(cuò)提示，如圖8所示：圖8 附錄源程序：include include include include defin
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1