數(shù)據(jù)結(jié)構(gòu)實驗報告—管道鋪設(shè)問題(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內(nèi)容簡介】 的所有邊中挑出權(quán)重最小的一條邊 { EdgeNode * p = Gadjlist[visitedNodes[i]].firstedge。 while (p != NULL) { if (isExists(visitedNodes, visitedIndex, padjvex) == 0 amp。amp。 pcost minCost) { minCost = pcost。 minEdge = p。 } p = pnext。 } } totalMinCost += minCost。 chosen[edgeIndex++] = *minEdge。 cout minEdgesrcName minEdgeadjName endl。//輸出這條最小權(quán)重的表 visitedNodes[visitedIndex++] = minEdgeadjvex。 }}4. 主函數(shù)int main(){ printf(試驗名稱：管道鋪設(shè)施工的最佳方案問題\n)。 printf(學(xué)號：031350103\n)。 printf(姓名：\n)。 printf(=========================================================\n)。 time_t rawtime1。 struct tm * timeinfo1。 time (amp。rawtime1)。 timeinfo1 = localtime (amp。rawtime1)。 //時間函數(shù)； printf (程序運行開始,當(dāng)前日期和時間: %s, asctime(timeinfo1))。 ALGraph* G = (ALGraph*)malloc(sizeof(ALGraph))。 create(G)。 cout 建立的圖鄰接表表示為：endl。 for (int i = 0。i Gn。i++) { EdgeNode *p = Gadjlist[i].firstedge。 printf(%d, i)。 //輸出建立的鄰接表 while (p != NULL) { printf(%d, padjvex)。 p = pnext。 } printf(\n)。 } printf(應(yīng)用prim算法，得到的最小生成樹是：)。 prime(G, 0)。 char kong。 cin kong。//輸出最小生成樹 return 0。 time_t rawtime2。 struct tm * timeinfo2。 time (amp。rawtime2)。 timeinfo2 = localtime (amp。rawtime2)。 printf (程序運行結(jié)束,當(dāng)前日期和時間: %s, asctime(timeinfo2))。} 五、調(diào)試分析 程序?qū)⑿^(qū)的相關(guān)信息輸入存儲在圖的鄰接表結(jié)構(gòu)中，每個節(jié)點與小區(qū)一一對應(yīng)，權(quán)值與小區(qū)之間的距離一一對應(yīng)，只需要輸入節(jié)點符號，以及相應(yīng)的權(quán)值，程序會自動輸出相應(yīng)的最小生成樹即相應(yīng)的管道鋪設(shè)線路。算法的時空分析：(1)由于 create(ALGraph* G)程序中讀入頂點的操作執(zhí)行了n次，讀入邊的操作執(zhí)行了e次，故其時間復(fù)雜度為O（n+2e）（2）prime(ALGraph * G, int from)的時間復(fù)雜度為O（n^2），n是頂點個數(shù)；（3）所有算法的空間復(fù)雜度都是O(1).六、使用說明 用戶首先根據(jù)提示輸入節(jié)點數(shù)n和邊數(shù)e，應(yīng)輸入整數(shù)，用空格隔開，如：9 15；再根據(jù)提示輸入n個結(jié)點的名稱，分n次輸入； 再根據(jù)提示輸入邊的信息，即兩個端點的名稱及該邊的權(quán)值，名稱為字符，權(quán)值為實數(shù)，用空格隔開，如：A B ，分e次輸入 輸入完成后不需操作，自動輸出所建立的鄰接表及最小生成樹的結(jié)果七、調(diào)試結(jié)果 輸入節(jié)點數(shù)邊數(shù)：9 15 輸入九個結(jié)點的名稱：A B C D E F G H I 輸入邊的信息，即兩個端點的名稱及該邊的權(quán)值：（A B ）；（B C ）。(C D )。(D E )。(A C )。(A H )。(A I )。(H I )。(H G )。(C G )。(C E )。(E F )。(D F )。(I F )。(E G ) 輸入完畢直接輸出“建立的圖鄰接表表示為：08721202460313542465235834642776808570” 輸出“應(yīng)用prim算法，得到的最小生成樹是：AH HI AB BC CD CE EG IF”初始界面為：輸入數(shù)據(jù)時的界面：輸出界面：八、遇到的問題和解決方法：1．最初拿到這個題目時還不會普利姆算法的具體內(nèi)容，只知道求最小生成樹的兩個方法叫普利姆算法和克里斯卡爾算法，但不理解也不會寫代碼。于是我上網(wǎng)查閱了相關(guān)資料，還請教了上機(jī)時給我們輔導(dǎo)的研究生學(xué)長，學(xué)會了prim算法?！盾浖夹g(shù)基礎(chǔ)教程》課本上給的鄰接表存儲有向圖的代碼修改的，想讓它存儲無向圖，但開始只是在創(chuàng)建邊
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1