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