數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告—管道鋪設(shè)問題-文庫吧資料
2025-03-31 03:01本頁面
【正文】 應(yīng)改動(dòng)，將新表結(jié)點(diǎn)插入到vi的邊表頭部這里的操作是雙向的才能保證圖是無向的，即，插入到vi后一次，插入到vj后一次，如這段代碼所示 ssrc = i。(E G ) 輸入完畢直接輸出“建立的圖鄰接表表示為：08721202460313542465235834642776808570” 輸出“應(yīng)用prim算法，得到的最小生成樹是：AH HI AB BC CD CE EG IF”初始界面為：輸入數(shù)據(jù)時(shí)的界面：輸出界面：八、遇到的問題和解決方法：1．最初拿到這個(gè)題目時(shí)還不會(huì)普利姆算法的具體內(nèi)容，只知道求最小生成樹的兩個(gè)方法叫普利姆算法和克里斯卡爾算法，但不理解也不會(huì)寫代碼。(D F )。(C E )。(H G )。(A I )。(A C )。(C D )。} 五、調(diào)試分析 程序?qū)⑿^(qū)的相關(guān)信息輸入存儲(chǔ)在圖的鄰接表結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)與小區(qū)一一對(duì)應(yīng)，權(quán)值與小區(qū)之間的距離一一對(duì)應(yīng)，只需要輸入節(jié)點(diǎn)符號(hào)，以及相應(yīng)的權(quán)值，程序會(huì)自動(dòng)輸出相應(yīng)的最小生成樹即相應(yīng)的管道鋪設(shè)線路。rawtime2)。rawtime2)。 struct tm * timeinfo2。//輸出最小生成樹 return 0。 char kong。 } printf(應(yīng)用prim算法，得到的最小生成樹是：)。 p = pnext。 printf(%d, i)。i Gn。 cout 建立的圖鄰接表表示為：endl。 ALGraph* G = (ALGraph*)malloc(sizeof(ALGraph))。rawtime1)。rawtime1)。 struct tm * timeinfo1。 printf(=========================================================\n)。 printf(學(xué)號(hào)：031350103\n)。//輸出這條最小權(quán)重的表 visitedNodes[visitedIndex++] = minEdgeadjvex。 chosen[edgeIndex++] = *minEdge。 } p = pnext。 pcost minCost) { minCost = pcost。 while (p != NULL) { if (isExists(visitedNodes, visitedIndex, padjvex) == 0 amp。i visitedIndex。 float minCost = 9999。 float totalMinCost = 0。 EdgeNode chosen[MaxEdgeNum]。 int visitedIndex = 0。 } } return exists。 i n。 }}3. 用普利姆算法生成最小生成樹int isExists(int * visited, int n, int vex) //判斷vex是否在visited數(shù)組里{ int exists = 0。 snext = Gadjlist[j].firstedge。 sadjName = Gadjlist[i].vertex。 ssrcName = Gadjlist[j].vertex。 s = (EdgeNode*)malloc(sizeof(EdgeNode))。 snext = Gadjlist[i].firstedge。 sadjName = Gadjlist[j].vertex。 ssrcName = Gadjlist[i].vertex。 //將輸入的vivj這條邊插入到鄰接表頭部 s = (EdgeNode*)malloc(sizeof(EdgeNode))。 j = cj 39。//讀入邊vi,vj的頂點(diǎn)對(duì)應(yīng)名稱 //將輸入的節(jié)點(diǎn)名(A,B,C...)轉(zhuǎn)化成內(nèi)部的下標(biāo) i = ci 39。 int i=1, j=1。 cout 請(qǐng)輸入邊的信息（頂點(diǎn)1 頂點(diǎn)2 權(quán)值）。kGe。 //頂點(diǎn)表的邊表頭指針設(shè)為空 } printf(建立邊表\n)。 //讀入頂點(diǎn)信息 Gadjlist[i].vertex = c。 char c。iGn。 cin Gn Ge。 EdgeNode *s。//頂點(diǎn)數(shù)和邊數(shù)}ALGraph。//AdjList是鄰接表類型typedef struct{ AdjList adjlist。//邊表頭指針}VertexNode。typedef struct //頂點(diǎn)表節(jié)點(diǎn) { char vertex。 float cost。//鄰接點(diǎn)域 node* next。 //邊端的序號(hào) char srcName。輸出這個(gè)最小權(quán)重的表。創(chuàng)建鄰接表存儲(chǔ)無向圖并輸出這一鄰接表。 這時(shí)T（E）中有n1條邊，T=（U，T（E））就是一一顆最小生成樹。即U={k0，k1}，同時(shí)將該邊加入集合T（E）中。（2）算法過程描述： 在圖G=（V，E）（V是頂點(diǎn)，E是邊）中，從集合V中任取一個(gè)頂點(diǎn)，如k0放入集合U中，這
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1