數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)(2013級(jí)

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)高級(jí)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)與算法課程組紹興文理學(xué)院教務(wù)處二零一三年二月版目 錄數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)步驟、規(guī)范的要求與建議 - 2數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)時(shí)間安排 - 3數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告示例 - 4實(shí)驗(yàn)一、大整數(shù)加法- 10實(shí)驗(yàn)二、棧序列匹配 - 14實(shí)驗(yàn)三、二叉排序樹(shù) - 17實(shí)驗(yàn)四、最小生成樹(shù) - 21附錄：VC有關(guān)操作的提示 - 27數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)步驟、規(guī)范的要求與建議從以往教學(xué)實(shí)驗(yàn)的經(jīng)驗(yàn)來(lái)看，在初學(xué)階段嚴(yán)格按實(shí)驗(yàn)步驟的要求去做，有助于養(yǎng)成良好的程序編制風(fēng)格，培養(yǎng)嚴(yán)謹(jǐn)、科學(xué)、高效的工作方式。經(jīng)常發(fā)現(xiàn)很多學(xué)生抱怨說(shuō)，化了兩個(gè)小時(shí)才找出一個(gè)錯(cuò)誤，甚至一無(wú)所獲。他們不明白造成這種情況的原因，正是他們自己。有

2、的學(xué)生不屑于按實(shí)驗(yàn)步驟去做，甚至對(duì)于實(shí)驗(yàn)步驟的要求看都不看一遍，認(rèn)為那是浪費(fèi)時(shí)間，這是極其有害的。有的學(xué)生甚至主要是抄襲別人的，以應(yīng)付檢查，這是學(xué)習(xí)上的墮落，是很危險(xiǎn)的！實(shí)驗(yàn)題目配合課程的進(jìn)度，請(qǐng)同學(xué)們務(wù)必自己獨(dú)立完成。為了鍛煉自己的應(yīng)用各種不同的數(shù)據(jù)結(jié)構(gòu)的能力，盡可能的多做一些題目是非常必要的。在完成各種不同題目的過(guò)程中，加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解和把握，提高編程和實(shí)踐能力，從而幫助你在更高的角度解決各種應(yīng)用問(wèn)題。按實(shí)驗(yàn)步驟進(jìn)行實(shí)驗(yàn)，不但可以培養(yǎng)科學(xué)化的工作作風(fēng)，而且還能有效地避免錯(cuò)誤，提高實(shí)驗(yàn)效率，達(dá)到實(shí)驗(yàn)?zāi)康?。具體的要求如下：1、問(wèn)題分析與系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)：充分地分析和理解問(wèn)題本身，弄清要求作什

3、么，限制條件是什么。按照以數(shù)據(jù)結(jié)構(gòu)和功能模塊為中心的原則劃分模塊，即定義數(shù)據(jù)結(jié)構(gòu)及其在這些結(jié)構(gòu)之上的操作，使得對(duì)數(shù)據(jù)結(jié)構(gòu)的存取通過(guò)這些操作加以實(shí)現(xiàn)。在這個(gè)過(guò)程中，要考慮系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單并且易于調(diào)試。最后寫出每個(gè)子程序(過(guò)程或函數(shù))的規(guī)格說(shuō)明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計(jì)。2、詳細(xì)設(shè)計(jì)和編碼詳細(xì)設(shè)計(jì)的目的是對(duì)子程序(過(guò)程或函數(shù))的進(jìn)一步求精。可以用IF、WHILE等偽代碼等自然語(yǔ)言寫出算法的框架，以避免陷入細(xì)節(jié)。在編碼時(shí)，可以對(duì)詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精，用高級(jí)語(yǔ)言表示出來(lái)。也可以直接用高級(jí)語(yǔ)言來(lái)描述算法。程序的每一行最好不超過(guò)60個(gè)字

4、符。每個(gè)子程序(或過(guò)程、函數(shù))通常不要太長(zhǎng)，以不超過(guò)40行為宜。子程序(或過(guò)程、函數(shù))包含的程序行數(shù)太多，易于造成理解的困難?？刂蒲h(huán)和判斷等語(yǔ)句的連續(xù)嵌套的深度。程序的目的性必須明確。對(duì)每一段程序完成的作用，除非常明顯的除外，盡可能加以注釋。這會(huì)對(duì)程序的調(diào)試提供很多方便。另外，根據(jù)情況可以設(shè)立若干調(diào)試點(diǎn)，即輸出若干信息，用于驗(yàn)證和你的設(shè)想是否一致。3、上機(jī)調(diào)試程序自底向上，先調(diào)試底層模塊，再調(diào)試上層模塊。最后，整個(gè)程序進(jìn)行聯(lián)調(diào)。調(diào)試正確后將源程序和運(yùn)行結(jié)果加以輸出。4、實(shí)驗(yàn)報(bào)告的書(shū)寫(1) 需求分析問(wèn)題描述，求解的問(wèn)題是什么。包括實(shí)驗(yàn)的任務(wù)、輸入、輸出、功能、測(cè)試數(shù)據(jù)等。(2) 概要設(shè)計(jì)設(shè)計(jì)

5、思想：存儲(chǔ)結(jié)構(gòu)、主要的算法思想。設(shè)計(jì)表示：主程序、子程序(過(guò)程或函數(shù))的規(guī)格說(shuō)明，通過(guò)調(diào)用關(guān)系圖表示它們之間的調(diào)用關(guān)系。(3) 詳細(xì)設(shè)計(jì)數(shù)據(jù)類型。主程序和其他模塊的算法或算法框架。(4) 調(diào)試分析問(wèn)題是如何解決的，討論與分析、改進(jìn)設(shè)想、經(jīng)驗(yàn)與體會(huì)、時(shí)空復(fù)雜度等。至少寫三點(diǎn)。(5) 測(cè)試結(jié)果列出你的測(cè)試結(jié)果，包括輸入的測(cè)試數(shù)據(jù)和輸出的結(jié)果。測(cè)試數(shù)據(jù)應(yīng)該完整和嚴(yán)格，必要時(shí)用多組數(shù)據(jù)進(jìn)行測(cè)試。(6) 用戶手冊(cè)：使用說(shuō)明。即說(shuō)明你的程序在什么環(huán)境下運(yùn)行，怎么運(yùn)行等。(7) 附錄源程序文件名，實(shí)驗(yàn)結(jié)束時(shí)源程序的電子稿要?dú)w檔。數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)時(shí)間安排(32學(xué)時(shí))實(shí)驗(yàn)內(nèi) 容學(xué)時(shí)數(shù)起止周實(shí)驗(yàn)一 大整數(shù)相加1

6、618實(shí)驗(yàn)二棧序列匹配8912實(shí)驗(yàn)三二叉排序樹(shù)81316實(shí)驗(yàn)四最小生成樹(shù)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)時(shí)間安排(16學(xué)時(shí))實(shí)驗(yàn)內(nèi) 容學(xué)時(shí)數(shù)起止周實(shí)驗(yàn)一 大整數(shù)相加1618實(shí)驗(yàn)二棧序列匹配8912實(shí)驗(yàn)三二叉排序樹(shù)81316實(shí)驗(yàn)四最小生成樹(shù)實(shí)驗(yàn)內(nèi) 容學(xué)時(shí)數(shù)起止周實(shí)驗(yàn)一 大整數(shù)相加818實(shí)驗(yàn)二棧序列匹配4912實(shí)驗(yàn)三二叉排序樹(shù)41316實(shí)驗(yàn)四最小生成樹(shù)實(shí)驗(yàn)內(nèi) 容學(xué)時(shí)數(shù)起止周實(shí)驗(yàn)一 大整數(shù)相加1618實(shí)驗(yàn)二棧序列匹配8912實(shí)驗(yàn)三二叉排序樹(shù)81316實(shí)驗(yàn)四最小生成樹(shù)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告示例約瑟夫環(huán)一、需求分析1、實(shí)驗(yàn)任務(wù)是用循環(huán)單鏈表(不帶頭結(jié)點(diǎn))來(lái)實(shí)現(xiàn)約瑟夫環(huán)。循環(huán)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)中包含環(huán)內(nèi)代表人的編號(hào)和密碼。2、

7、對(duì)于輸入的人數(shù)(n)和n個(gè)密碼，建立不帶頭結(jié)點(diǎn)的單循環(huán)鏈表。3、對(duì)于密碼m，從相對(duì)的第一個(gè)人開(kāi)始報(bào)到第m個(gè)人，輸出相對(duì)于開(kāi)始報(bào)數(shù)的第m個(gè)人的信息。4、輸出過(guò)程及輸出完n個(gè)人的信息，即實(shí)現(xiàn)了約瑟夫環(huán)的功能。5、測(cè)試數(shù)據(jù)m的初值設(shè)為6；(1) 對(duì)于n=7，7個(gè)人的密碼依次為：3，1，7，2，4，8，4進(jìn)行測(cè)試。(2) 對(duì)于從鍵盤輸入的n和n個(gè)人的密碼進(jìn)行測(cè)試。二、概要設(shè)計(jì)1、數(shù)據(jù)類型(1) n個(gè)人的編號(hào)和密碼的數(shù)據(jù)元素結(jié)構(gòu)typedef struct / 用于接收數(shù)據(jù)的輸入int num; int m;data;(2) 單向循環(huán)鏈表結(jié)點(diǎn)結(jié)構(gòu)typedef struct node int num;

8、int m; node *next;node,*link;2、算法思想(1) 輸入n個(gè)人的密碼，分別和依次按1到n的編號(hào)，輸入到一個(gè)結(jié)構(gòu)體數(shù)組，以便為建立單循環(huán)鏈表作數(shù)據(jù)準(zhǔn)備； (2) 根據(jù)結(jié)構(gòu)體數(shù)組中的數(shù)據(jù)，建立單循環(huán)鏈表； (3) 由得到的單向循環(huán)鏈表，根據(jù)約瑟夫問(wèn)題的要求，構(gòu)造約瑟夫函數(shù)，該函數(shù)中設(shè)置2個(gè)指針p和 q，p指向當(dāng)前報(bào)數(shù)的結(jié)點(diǎn)，q指向p結(jié)點(diǎn)后面的結(jié)點(diǎn)，開(kāi)始時(shí)，q應(yīng)指向單向循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)。對(duì)于出列的人(結(jié)點(diǎn))，在該函數(shù)中輸出其編號(hào)。該函數(shù)被主函數(shù)調(diào)用。(4) 在主函數(shù)中設(shè)置結(jié)構(gòu)體數(shù)組，調(diào)用輸入模塊，把輸入的n個(gè)人的密碼和依次按1到n的編號(hào)，存儲(chǔ)到一個(gè)結(jié)構(gòu)體數(shù)組，然后調(diào)用

9、建立有n個(gè)結(jié)點(diǎn)構(gòu)成的單向循環(huán)鏈表的函數(shù)，最后調(diào)用約瑟夫函數(shù)，實(shí)現(xiàn)約瑟夫問(wèn)題的求解。3、各子模塊(1) 輸入數(shù)據(jù)模塊該模塊中輸入n及n個(gè)人的編號(hào)和密碼，依次存儲(chǔ)于data類型的結(jié)構(gòu)體數(shù)組；(2) 建立單循環(huán)鏈表模塊該模塊中根據(jù)結(jié)構(gòu)數(shù)組中的數(shù)據(jù)，建立不帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其結(jié)點(diǎn)中的數(shù)據(jù)是人的編號(hào)和密碼；(3) 約瑟夫問(wèn)題求解模塊該模塊中根據(jù)單向循環(huán)鏈表，從第一個(gè)人(結(jié)點(diǎn))開(kāi)始報(bào)數(shù)，報(bào)到密碼m時(shí)(初始密碼m可為6)該(人)結(jié)點(diǎn)出列，并輸出相應(yīng)的信息和得到新的密碼，為下一次報(bào)數(shù)做準(zhǔn)備，直至每個(gè)人(結(jié)點(diǎn))全部出列，輸出的信息即為約瑟夫問(wèn)題的求解。4、主模塊及與子模塊的調(diào)用關(guān)系(1) 主模塊設(shè)置data

10、類型的結(jié)構(gòu)體數(shù)組和有關(guān)變量，然后依次調(diào)用輸入數(shù)據(jù)模塊、建立單循環(huán)鏈表模塊和約瑟夫問(wèn)題求解模塊。(2) 各模塊之間的調(diào)用關(guān)系 主程序模塊 輸入數(shù)據(jù)模塊 建立單循環(huán)鏈表模塊 約瑟夫問(wèn)題求解模塊三、詳細(xì)設(shè)計(jì)1、數(shù)據(jù)結(jié)構(gòu)typedef structint num; int m;data;typedef struct nodeint num; int m; struct node *next;node,*link;2、輸入數(shù)據(jù)模塊(用源代碼也可以，但以偽代碼比較好,下同)void inputdata(int n，data man) 輸入n；for i=0 to n-1 輸入密碼m; mani.numi+

11、1; mani.dm; 3、建立單循環(huán)鏈表模塊void createlinklist(int n, data man,link &l) link l,p,q; lnew node; l-num=man0.num;l-mman0.m; q=l; for i=1 to n-1 p=new node; p-num=mani.num;p-mmani.m; q-nextp;qp; q-nextl;4、約瑟夫問(wèn)題求解模塊void joseph(link l,int n)link q,p,s;m=6; ql-next; while(q-nextl) qq-next; pl; for i=0 to n-1 /

12、 重復(fù)n次 for j=1 to m-1 / 找第m個(gè)人 qp; pp-next; sp; q-nextp-next; pp-next; output s-num; ms-m; delete s; 5、主程序模塊 void main()link l; int n;data man100; input n; inputdata(n，man); createlinklist(n,man,l); joseph(l,n); 四、調(diào)試分析1、由于建立的是帶頭結(jié)點(diǎn)的單循環(huán)鏈表，導(dǎo)致輸出的結(jié)果許多是錯(cuò)的，刪除頭結(jié)點(diǎn)，即建立的是不帶頭結(jié)點(diǎn)的單循環(huán)鏈表解決。2、由于開(kāi)始時(shí)沒(méi)有指針指向要開(kāi)始報(bào)數(shù)結(jié)點(diǎn)后的指針，導(dǎo)致

13、當(dāng)開(kāi)始密碼是1時(shí)不能刪除第一個(gè)結(jié)點(diǎn)，出現(xiàn)輸出亂的現(xiàn)象，經(jīng)檢查發(fā)現(xiàn)該錯(cuò)誤，采用在joseph函數(shù)的開(kāi)始就掃描單循環(huán)鏈表，使指針其指向單循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)，以便需要時(shí)能刪除第一個(gè)結(jié)點(diǎn)，也就是說(shuō)，在數(shù)結(jié)點(diǎn)時(shí)后面要跟一個(gè)指針，以便當(dāng)數(shù)到要?jiǎng)h除那個(gè)結(jié)點(diǎn)時(shí)，通過(guò)對(duì)后面跟著的指針?biāo)附Y(jié)點(diǎn)的操作能刪除數(shù)到的結(jié)點(diǎn)，這樣就解決了這個(gè)問(wèn)題。這一點(diǎn)也提醒我們，單戀表中的操作，要?jiǎng)h除結(jié)點(diǎn)，必須有指向其“前驅(qū)”結(jié)點(diǎn)的指針，否則是不能刪除要?jiǎng)h除的結(jié)點(diǎn)的。3、由于先刪除了結(jié)點(diǎn)空間，沒(méi)有把被刪結(jié)點(diǎn)中的密碼保存，出現(xiàn)得到的密碼不是被刪結(jié)點(diǎn)的密碼，而是被刪結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)的密碼，導(dǎo)致輸出的信息不正確，修改成在刪除結(jié)點(diǎn)空間前先保存

14、其密碼而解決。4、算法的時(shí)間復(fù)雜度設(shè)約瑟夫問(wèn)題中的人數(shù)為n,則建立單鏈表的時(shí)間復(fù)雜度是(n)，約瑟夫問(wèn)題的求解模塊中，要n次出列人，而每次出列人要走m個(gè)結(jié)點(diǎn)，設(shè)密碼的平均值為m，則約瑟夫問(wèn)題求解模塊的時(shí)間復(fù)雜度為(nm)。 所以算法的時(shí)間復(fù)雜度為(n)。五、測(cè)試結(jié)果第一組：Input73 1 7 2 4 8 4Output6 1 4 7 2 3第二組：Input105 2 9 6 8 3 11 4 7 10Output6 9 7 2 4 5 3 1 8 10測(cè)試通過(guò)。六、用戶使用說(shuō)明1、本程序的運(yùn)行環(huán)境為windows操作系統(tǒng)下命令執(zhí)行方式，執(zhí)行文件為：exp1.exe；也可在VC集成環(huán)境下執(zhí)

15、行。2、運(yùn)行程序后輸入人數(shù)n后，按提示依次輸入n個(gè)密碼即可。輸出的是約瑟夫問(wèn)題的求解過(guò)程中出列人的編號(hào)。見(jiàn)下圖。七、附錄源程序文件名清單：exp1.cpp。實(shí)驗(yàn)結(jié)束后上交。實(shí)驗(yàn)一、大整數(shù)加法一、問(wèn)題描述給定兩個(gè)非負(fù)整數(shù)A和B, 計(jì)算出A+B的值。整數(shù)A和B的位數(shù)可能超過(guò)整數(shù)類型數(shù)據(jù)能存儲(chǔ)的范圍。要求計(jì)算并輸出A+B的值。二、基本要求1、正確輸入兩個(gè)大整數(shù)；2 利用兩個(gè)單鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)兩個(gè)大整數(shù)；3 對(duì)存儲(chǔ)于單鏈表的兩個(gè)大整數(shù)，根據(jù)數(shù)據(jù)加法的要求，通過(guò)對(duì)鏈表的操作，使兩個(gè)大整數(shù)的和存儲(chǔ)于單鏈表，并考慮盡量使用原單鏈表存儲(chǔ)空間；4 輸出兩個(gè)大整數(shù)的和，即輸出和單鏈表中的內(nèi)容。三、測(cè)試數(shù)據(jù)第一組1

16、第二組321第三組四、實(shí)現(xiàn)提示1、算法思路(1) 正確輸入兩個(gè)整數(shù)，由于其整數(shù)位數(shù)可能超過(guò)整數(shù)數(shù)據(jù)類型可以存儲(chǔ)的范圍，所以要用字符串的數(shù)據(jù)類型來(lái)接受輸入的兩個(gè)整數(shù)?？梢栽谥骱瘮?shù)里完成。(2) 對(duì)于存儲(chǔ)在字符串里的整數(shù)，依次根據(jù)字符串中從高位到低位的數(shù)值位，可以用前插法建立單鏈表的方法，將整數(shù)存儲(chǔ)于帶頭結(jié)點(diǎn)的單鏈表中(每個(gè)結(jié)點(diǎn)存放一位數(shù)字，也可存放多位數(shù)字，前者簡(jiǎn)單一點(diǎn)。本指導(dǎo)按前者的處理方法描述)，這時(shí)，從單鏈表的第一個(gè)結(jié)點(diǎn)到尾結(jié)點(diǎn)依次是從個(gè)位到最高位的整數(shù)，以便相加運(yùn)算。也可依次根據(jù)字符串中從低位(字符串的右端)到高位(字符串的左端)的數(shù)值位，用后插法建立單鏈表的方法，將整數(shù)存儲(chǔ)于帶頭結(jié)點(diǎn)的

17、單鏈表中。也可依次根據(jù)字符串中從高位(字符串的左端)的數(shù)值位到低位(字符串的右端)的數(shù)值位，用后插法建立單鏈表的方法，將整數(shù)存儲(chǔ)于帶頭結(jié)點(diǎn)的單鏈表中，這時(shí)，從單鏈表的第一個(gè)結(jié)點(diǎn)到尾結(jié)點(diǎn)依次是從最高位到個(gè)位的整數(shù)，然后再逆置這個(gè)單鏈表，使從單鏈表的第一個(gè)結(jié)點(diǎn)到尾結(jié)點(diǎn)依次是從個(gè)位到最高位的整數(shù)。以上過(guò)程可用一個(gè)函數(shù)完成。(3) 對(duì)兩個(gè)從單鏈表的第一個(gè)結(jié)點(diǎn)到尾結(jié)點(diǎn)依次是從個(gè)位到最高位存儲(chǔ)的兩個(gè)整數(shù)，從第一個(gè)結(jié)點(diǎn)開(kāi)始，依次掃描到長(zhǎng)度短的單鏈表的尾結(jié)點(diǎn)，每次把掃描到的兩個(gè)結(jié)點(diǎn)中的數(shù)值及前面相加留下的進(jìn)位相加，把和的個(gè)位存儲(chǔ)到長(zhǎng)度長(zhǎng)的單鏈表對(duì)應(yīng)的結(jié)點(diǎn)中，同時(shí)記錄進(jìn)位；然后把可能有的進(jìn)位依次與長(zhǎng)單鏈表還未相

18、加過(guò)的結(jié)點(diǎn)依次相加，若到最后一個(gè)結(jié)點(diǎn)相加后仍有進(jìn)位，則要新增加一個(gè)結(jié)點(diǎn)，以存放進(jìn)位。至此，兩個(gè)整數(shù)的和已經(jīng)存儲(chǔ)在原來(lái)長(zhǎng)的單鏈表中了。這個(gè)過(guò)程可以一個(gè)函數(shù)完成。(4) 對(duì)于已經(jīng)存儲(chǔ)好的和的單鏈表，其第一個(gè)結(jié)點(diǎn)到尾結(jié)點(diǎn)依次是和的個(gè)位到最高位，要對(duì)該單鏈表進(jìn)行逆置，這個(gè)過(guò)程可用以函數(shù)完成。然后可將其單鏈表中結(jié)點(diǎn)的值輸出，這也可用一函數(shù)完成。(5) 在主函數(shù)中要設(shè)置相關(guān)的數(shù)據(jù)結(jié)構(gòu)，以存放兩個(gè)整數(shù)和單鏈表，輸入兩個(gè)整數(shù)后，依次可調(diào)用單鏈表初始化模塊、建立單鏈表模塊、兩個(gè)整數(shù)相加模塊、單鏈表逆置模塊和輸出單鏈表中結(jié)點(diǎn)的值的模塊。中間可確定好較長(zhǎng)整數(shù)所對(duì)應(yīng)的單鏈表指針，以供兩個(gè)整數(shù)相加模塊使用。2、數(shù)據(jù)結(jié)構(gòu)

19、存放輸入的整數(shù)可用string類型字符串，也可用char類型一維字符數(shù)組。存放整數(shù)的單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)可以是：typedef struct nodeint data; node *next;*linklist;3、基本操作(1) 構(gòu)造一個(gè)空的帶頭結(jié)點(diǎn)的單鏈表l，用單鏈表中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域存放每一個(gè)整數(shù)位。initlist(linklist &l) 該函數(shù)可在主函數(shù)中調(diào)用。(2) 依次根據(jù)存放整數(shù)的字符串s1中從高位到低位的數(shù)值位，前插法建立帶表頭結(jié)點(diǎn)的單鏈表。createlist_f(linklist l,string s1) for(s1中的每一個(gè)數(shù)字字符) 轉(zhuǎn)化成數(shù)值； 存于結(jié)點(diǎn)并連接到單

20、鏈表的頭部； 該函數(shù)可在主函數(shù)中調(diào)用。(3) 單鏈表逆置。以便把單鏈表轉(zhuǎn)換成所需要的從第一個(gè)結(jié)點(diǎn)到尾結(jié)點(diǎn)依次是從最高位到個(gè)位整數(shù)(要相反順序也一樣)。inverse(linklist l) 該函數(shù)可在主函數(shù)或相關(guān)函數(shù)中調(diào)用。(4) 輸出單鏈表中的元素值。print(linklist l) 該函數(shù)可在主函數(shù)中調(diào)用。(5) 整數(shù)相加。其中l(wèi)1、l2是存放兩個(gè)整數(shù)的單鏈表，l是較長(zhǎng)整數(shù)的單鏈表。add(linklist l1,linklist l2,linklist l) 指針指向存放較長(zhǎng)整數(shù)單鏈表的第一個(gè)結(jié)點(diǎn)； 指針指向兩個(gè)整數(shù)單鏈表的第一個(gè)結(jié)點(diǎn)；while(指向兩個(gè)整數(shù)單鏈表均不空) 計(jì)算兩個(gè)整

21、數(shù)單鏈中的數(shù)值和進(jìn)位的和；記錄進(jìn)位；把和的個(gè)位存儲(chǔ)于較長(zhǎng)整數(shù)單鏈表的結(jié)點(diǎn)； 各指針均向后移動(dòng)一個(gè)結(jié)點(diǎn)； while(有進(jìn)位且較長(zhǎng)整數(shù)單鏈表不空)計(jì)算較長(zhǎng)整數(shù)單鏈表中的數(shù)值和進(jìn)位的和；記錄進(jìn)位；把和的個(gè)位存儲(chǔ)于較長(zhǎng)整數(shù)單鏈表的結(jié)點(diǎn)；指向較長(zhǎng)整數(shù)單鏈表的結(jié)點(diǎn)指針向后移動(dòng)一個(gè)結(jié)點(diǎn)； if(還有進(jìn)位) 較長(zhǎng)整數(shù)單鏈表增加結(jié)點(diǎn)，存放最后的進(jìn)位。 該函數(shù)可在主函數(shù)中調(diào)用。4、主程序main() 輸入兩個(gè)整數(shù)； 調(diào)用相關(guān)模塊，將單鏈表初始化后將兩個(gè)整數(shù)存儲(chǔ)于單鏈表； 確定較長(zhǎng)整數(shù)的單鏈表； 調(diào)用整數(shù)相加模塊進(jìn)行整數(shù)相加； 調(diào)用鏈表逆置模塊對(duì)單鏈表的數(shù)位進(jìn)行逆置； 調(diào)用輸出模塊輸出和單鏈表；五、測(cè)試與輸出結(jié)果

22、Sample Input391321Sample Output10642實(shí)驗(yàn)二、棧序列匹配一、問(wèn)題描述對(duì)于給出的入棧序列和出棧序列，判斷這兩個(gè)序列是否相容。即能否利用棧操作將入棧序列轉(zhuǎn)換為出棧序列。二、基本要求入棧序列和出棧序列均為字符型數(shù)據(jù)，由鍵盤輸入，其長(zhǎng)度不超過(guò)10個(gè)字符。若入棧序列和出棧序列相容(即能利用棧操作將入棧序列轉(zhuǎn)換為出棧序列)，則輸出yes，否則輸出no。在判斷棧序列的匹配過(guò)程中，輸出入棧、出棧的過(guò)程和棧中的元素。三、測(cè)試數(shù)據(jù)輸入數(shù)據(jù)的第一行為一個(gè)正整數(shù)T, 表示測(cè)試數(shù)據(jù)的組數(shù)。然后是T組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)的輸入是在同一行中用一個(gè)空格分隔的兩個(gè)字符串(其長(zhǎng)度均不超過(guò)10)

23、，依次表示入棧序列和出棧序列。輸出格式為每入棧(或)出棧一次輸出一行：push(或pop):c stack:棧頂?shù)綏５椎男蛄校渲衏為入棧(或)出棧的字符，最后一行個(gè)根據(jù)入棧序列和出棧序列是否匹配輸出yes或no，匹配則輸出yes，否則輸出no(參見(jiàn)Sample Output)。四、實(shí)現(xiàn)提示1、算法思路設(shè)置鏈?zhǔn)綏；蝽樞驐，作為入棧序列的?？臻g，設(shè)置top為其棧頂指針(或下標(biāo))。對(duì)入棧序列從第一個(gè)元素開(kāi)始考慮入棧，在依次掃描出棧序列元素的過(guò)程中進(jìn)行如下的處理：若?？涨胰霔Ｐ蛄杏形慈霔５脑?，則當(dāng)前入棧序列中的元素入棧，并輸出相應(yīng)的信息；若棧不空且棧頂?shù)脑貫槌鰲Ｐ蛄械漠?dāng)前元素，則棧頂元素出棧，

24、并輸出相應(yīng)的信息，否則，若入棧序列有未入棧的元素，則當(dāng)前入棧序列中的元素入棧，并輸出相應(yīng)的信息；否則可以確定輸入的入棧序列和出棧序列不相容(即不匹配)。最后判斷：若入棧序列和出棧序列均已掃描完且棧為空，則可以確定輸入的入棧序列和出棧序列相容(即匹配)。2、數(shù)據(jù)結(jié)構(gòu)typedef struct node / 鏈?zhǔn)綏中的結(jié)點(diǎn)結(jié)構(gòu)char data; struct node *next;StackNode,*LinkStack;3、基本操作LinkStack push(LinkStack top,char e) / 入棧操作，e為棧中元素類型LinkStack pop(LinkStack top,

25、 char *e) / 出棧操作,e為指向棧中元素的指針類型，為的使其值在函數(shù)外面可用 void list(LinkStack top) / 顯示棧中元素int judge(string str1,string str2) / 判斷是否匹配主模塊，str1和str2為入棧序列和出棧序列 棧初始化；從出棧序列的第一個(gè)元素開(kāi)始； while(出棧序列還未掃描完) if(棧空且入棧序列有未入棧的元素)當(dāng)前入棧序列中的元素入棧，并輸出相應(yīng)的信息；if(若棧不空且棧頂?shù)脑貫槌鰲Ｐ蛄械漠?dāng)前元素)棧頂元素出棧，并輸出相應(yīng)的信息，else if(若入棧序列有未入棧的元素)當(dāng)前入棧序列中的元素入棧，并輸出相應(yīng)

26、的信息；else 確定輸入的入棧序列和出棧序列不相容(即不匹配)。 if(若入棧序列和出棧序列均已掃描完且棧為空)確定輸入的入棧序列和出棧序列相容(即匹配)。 else 確定輸入的入棧序列和出棧序列不相容(即不匹配)。4、主程序int main() 輸入入棧序列和出棧序列； 調(diào)用判斷是否匹配主模塊judge()；根據(jù)其返回的值輸出yes或no。五、測(cè)試與輸出結(jié)果第一組：輸入：ABCDEF DCEFAB輸出：push:A stack:Apush:B stack:BApush:C stack:CBApush:D stack:DCBApop:D stack:CBApop:C stack:BApush

27、:E stack:EBApop:E stack:BApush:F stack:FBApop:F stack:BAno第二組：輸入：ABCDEF ACEDBF輸出：push:A stack:Apop:A stack:push:B stack:Bpush:C stack:CBpop:C stack:Bpush:D stack:DBpush:E stack:EDBpop:E stack:DBpop:D stack:Bpop:B stack:push:F stack:Fpop:F stack:yes實(shí)驗(yàn)三、二叉排序樹(shù)一、問(wèn)題描述輸入一個(gè)整數(shù)關(guān)鍵字序列L，生成一棵用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的二叉排序樹(shù)，對(duì)該二叉

28、排序樹(shù)能進(jìn)行查找和插入結(jié)點(diǎn)的操作，并對(duì)該二叉排序樹(shù)中結(jié)點(diǎn)的關(guān)鍵字按遞增和遞減順序輸出。二、基本要求輸入數(shù)據(jù)的第一行為一個(gè)正整數(shù)T, 表示測(cè)試數(shù)據(jù)的組數(shù)。然后是T組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)的第一行輸入正整數(shù)n(5n20)，第二行輸入n個(gè)整數(shù)，要求依次完成以下工作：(1) 以這n個(gè)整數(shù)生成(建立)一棵用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的二叉排序樹(shù)；(2) 按遞增順序輸出該二叉排序樹(shù)中的整數(shù)(關(guān)鍵字)；(3) 輸入一個(gè)整數(shù)key，對(duì)該二叉排序樹(shù)進(jìn)行查找，若在該二叉排序樹(shù)中存在這個(gè)整數(shù)key，則輸出find，否則輸出not find。(4) 輸入一個(gè)整數(shù)key，若該二叉排序樹(shù)中不存在這個(gè)整數(shù)key，則將key插入到該二

29、叉排序樹(shù)中，使插入后仍為原性質(zhì)的二叉排序樹(shù)；否則不必插入；(5) 在(4)的基礎(chǔ)上，按遞減順序輸出該二叉排序樹(shù)中的整數(shù)(關(guān)鍵字)。三、測(cè)試數(shù)據(jù)輸入數(shù)據(jù)的第一行為一個(gè)正整數(shù)T, 表示測(cè)試數(shù)據(jù)的組數(shù)。然后是T組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)的第一行輸入正整數(shù)n(5n20)，第二行輸入n個(gè)整數(shù)，第三和第四行均輸入整數(shù)key。每組輸出的第一行為按遞增順序輸出該二叉排序樹(shù)中的整數(shù)(關(guān)鍵字)，每?jī)蓚€(gè)整數(shù)之間一個(gè)空格；第二行為find或not find；第三行為按遞減順序輸出該二叉排序樹(shù)中的整數(shù)(關(guān)鍵字)。第一組：810 79 6 81 43 75 26 694369第二組：1094 22 25 24 20 42

30、39 71 53 57881四、實(shí)現(xiàn)提示1、算法思路(1) 首先要建立二叉排序樹(shù)。我們要建立的二叉排序樹(shù)，其關(guān)鍵字要求是各不相同的，則對(duì)于輸入的關(guān)鍵字(整數(shù))序列中的每一個(gè)整數(shù)，要在正在建立的二叉排序樹(shù)中去查找是否已經(jīng)存在該整數(shù)，不存在時(shí)，由查找模塊(其算法思路后述)返回要增加(插入)結(jié)點(diǎn)位置的雙親結(jié)點(diǎn)，根據(jù)要建立的二叉排序樹(shù)的性質(zhì)(左小右大)，當(dāng)要增加的整數(shù)比雙親結(jié)點(diǎn)的整數(shù)小的話就插(掛)到其左孩子的位置，否則插(掛)到其右孩子的位置。這樣重復(fù)，直到輸入結(jié)束(輸入的整數(shù)為-1)，這樣，二叉排序樹(shù)就建好了。(2) 查找算法是從二叉排序樹(shù)的根結(jié)點(diǎn)開(kāi)始，根據(jù)要查找的整數(shù)，若比其當(dāng)前二叉排序樹(shù)結(jié)點(diǎn)中

31、的整數(shù)小就進(jìn)入其左孩子所在的左子樹(shù)中繼續(xù)搜索，否則進(jìn)入其右左孩子所在的右子樹(shù)中繼續(xù)搜索，這過(guò)程中，每進(jìn)入子樹(shù)前，保存當(dāng)前結(jié)點(diǎn)(指針)，以便帶回要增加(插入)結(jié)點(diǎn)的雙親結(jié)點(diǎn)。搜索直至找到要查找的整數(shù)，用一指針帶回；或搜索直至葉子結(jié)點(diǎn)的下方，找不到要查找的整數(shù)而使空指針帶回，以便判斷要查找的整數(shù)是否找到。(3) 按遞增順序輸出該二叉排序樹(shù)中的整數(shù)(關(guān)鍵字)，可直接用某種二叉樹(shù)的遍歷算法實(shí)現(xiàn)；按遞減順序輸出該二叉排序樹(shù)中的整數(shù)(關(guān)鍵字)，只要對(duì)某種二叉樹(shù)的遍歷算法稍作修改即可。(4) 插入算法思路和建立二叉排序樹(shù)時(shí)增加一個(gè)整數(shù)的思路是一樣的。2、數(shù)據(jù)結(jié)構(gòu)typedef struct node / 二

32、叉排序樹(shù)中的結(jié)點(diǎn)結(jié)構(gòu)int data; / 整數(shù)(關(guān)鍵字)數(shù)據(jù)域 struct node *lchild,*rchild; / 指向左右孩子的指針nodeb,*bitree;3、基本操作(1) 查找算法void searchbst(bitree t,bitree *f,bitree *p,int key) / 在二叉排序樹(shù)t中查找整數(shù)為key的結(jié)點(diǎn)，若找到，則p指向該結(jié)點(diǎn)，否則p為空。f 為/指向雙親結(jié)點(diǎn)的while(t不空且t中的整數(shù)不是要找的整數(shù)key) 用f記錄當(dāng)前結(jié)點(diǎn)； if(要找的整數(shù)key小于t中的整數(shù)) t進(jìn)入其左孩子所在的左子樹(shù)；else t進(jìn)入其右孩子所在的右子樹(shù)； (2)

33、建立二叉排序樹(shù)算法bitree createbintree(int n) /* 建立有n個(gè)整數(shù)的二叉排序樹(shù)，其二叉排序樹(shù)t，用函數(shù)值返回樹(shù)根*/ 置t為空樹(shù)；while(n次) 輸入整數(shù)； 查找該整數(shù)；if(該整數(shù)在當(dāng)前的二叉排序樹(shù)中不存在) 申請(qǐng)結(jié)點(diǎn)； 對(duì)該結(jié)點(diǎn)賦以該整數(shù)；該結(jié)點(diǎn)的左右指針賦空值； 根據(jù)查找的結(jié)果，把該結(jié)點(diǎn)掛到某結(jié)點(diǎn)的左孩子或右孩子位置 / 注意當(dāng)二叉排序樹(shù)還是空樹(shù)時(shí)情況的處理 返回建好的二叉排序樹(shù)t；(3) 插入(增加)整數(shù)算法int insertbst(bitree *t,int key) /* 在二叉排序樹(shù)t中插入整數(shù)key的結(jié)點(diǎn)，是否插入成功用函數(shù)值返回 */ 在二叉

34、排序樹(shù)t中查找整數(shù)key；if(整數(shù)key在二叉排序樹(shù)t中不存在) 申請(qǐng)結(jié)點(diǎn)； 對(duì)該結(jié)點(diǎn)賦以該整數(shù)；該結(jié)點(diǎn)的左右指針賦空值； 根據(jù)查找的結(jié)果，把該結(jié)點(diǎn)掛到某結(jié)點(diǎn)的左孩子或右孩子位置 / 注意當(dāng)二叉排序樹(shù)還是空樹(shù)時(shí)情況的處理else 插入不成功；4、主程序int main() 重復(fù)m組：調(diào)用createbintree()算法建立二叉排序樹(shù)t；調(diào)用某種二叉樹(shù)遍歷算法按遞增順序輸出該二叉排序樹(shù)中的整數(shù)(關(guān)鍵字)；輸入要查找的整數(shù)，調(diào)用searchbst()算法查找要查找的整數(shù)；根據(jù)查找的結(jié)果輸出相應(yīng)的信息；輸入要插入的整數(shù)，調(diào)用insertbst()算法將整數(shù)插入到二叉排序樹(shù)中；根據(jù)插入的結(jié)果輸出相

35、應(yīng)的信息；調(diào)用稍作修改的某種二叉樹(shù)遍歷算法按遞減順序輸出該二叉排序樹(shù)中的整數(shù)(關(guān)鍵字)；五、測(cè)試與輸出結(jié)果第一組：Sample Input810 79 6 81 43 75 26 694369Sample Output6 10 26 43 69 75 79 81find81 79 75 69 43 26 10 6第二組：Sample Input1094 22 25 24 20 42 39 71 53 57881Sample Output20 22 24 25 39 42 53 57 71 94not find94 71 57 53 42 39 25 24 22 20 1實(shí)驗(yàn)四、最小生成樹(shù)一、問(wèn)

36、題描述給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kruskal算法生成最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。要求顯示得到的最小生成樹(shù)中包括了哪些城市間的道路，并顯示得到的最小生成樹(shù)的代價(jià)。表示城市間距離網(wǎng)要求至少6個(gè)城市，8條邊。二、基本要求從鍵盤輸入n個(gè)頂點(diǎn)和m條邊(6n15，n-1m20)，建立圖的鄰接表(鄰接矩陣也可)存儲(chǔ)圖，然后輸出該鄰接表(鄰接矩陣)，用Prim(或Kruskal)算法求出其最小生成樹(shù)，輸出最小生成樹(shù)中的城市、城市間的道路及距離和最小生成樹(shù)的代價(jià)。輸入輸出的形式可參見(jiàn)“五、測(cè)試與輸出結(jié)果”。三、測(cè)試數(shù)據(jù)用下圖所示的圖建立鄰接矩陣進(jìn)行測(cè)試。111492513

37、7212854610ACBEDFGH四、實(shí)現(xiàn)提示1、算法思路(1) 首先要建立圖的鄰接表，這部分的算法思路見(jiàn)高級(jí)語(yǔ)言課程設(shè)計(jì)指導(dǎo)書(shū)中的圖的存儲(chǔ)這一設(shè)計(jì)中的指導(dǎo)。有關(guān)對(duì)應(yīng)的操作均給出了指導(dǎo)(這里略)。只是這里輸入邊的同時(shí)還要輸入這條邊上所帶的權(quán)值，并存儲(chǔ)好，這只是在鄰接鏈表的結(jié)點(diǎn)中增加了一個(gè)數(shù)據(jù)域(weight)。并設(shè)定要求最小生成樹(shù)的圖為無(wú)向連通圖，圖中有n(n2)個(gè)頂點(diǎn)。(2) 在鄰接表方式存儲(chǔ)圖的基礎(chǔ)上，用Prim算法生成最小生成樹(shù)的主模塊分以下兩個(gè)部分：第一部分(初始化)： 設(shè)計(jì)結(jié)構(gòu)體數(shù)組，其元素有兩個(gè)成員，一個(gè)是存放圖中頂點(diǎn)的前驅(qū)頂點(diǎn)的序號(hào)(下標(biāo))；另一個(gè)是存放圖中頂點(diǎn)到正在生成的最小

38、生成樹(shù)(中頂點(diǎn))的最短距離； 對(duì)結(jié)構(gòu)體數(shù)組中存放圖中頂點(diǎn)到正在生成的最小生成樹(shù)(中頂點(diǎn))的最短距離初始均置為無(wú)窮大(可用一大正數(shù))； 在圖中任取一起始頂點(diǎn)k(可選取存儲(chǔ)的第一個(gè)頂點(diǎn))作為正在生成的最小生成樹(shù)的第一個(gè)頂點(diǎn)，然后掃描該頂點(diǎn)所對(duì)應(yīng)的鄰接鏈表中的每一個(gè)頂點(diǎn)，把k作為該頂點(diǎn)的前驅(qū)頂點(diǎn)；把該頂點(diǎn)中的權(quán)值作為該頂點(diǎn)到正在生成的最小生成樹(shù)的最短距離。 把頂點(diǎn)k做上已在正在生成的最小生成樹(shù)中的記號(hào)(可置其到正在生成的最小生成樹(shù)的最短距離為0，因?yàn)轫旤c(diǎn)間的距離不可能為0)第二部分(用Prim算法思想求出最小生成樹(shù))：除初始頂點(diǎn)已在正在生成的最小生成樹(shù)中外，對(duì)于其余的n-1個(gè)頂點(diǎn)，重復(fù)下面的n-1步

39、，每一步選取和正在生成的最小生成樹(shù)中相連接的一個(gè)頂點(diǎn)和一條邊加入到正在生成的最小生成樹(shù)中： 找。找和正在生成的最小生成樹(shù)連接的距離最短的一個(gè)頂點(diǎn)u。這個(gè)過(guò)程可以從余下的頂點(diǎn)到正在生成的最小生成樹(shù)的最短距離中去找； 輸出。依次輸出頂點(diǎn)u的前驅(qū)頂點(diǎn)、u的前驅(qū)頂點(diǎn)到u 的距離和頂點(diǎn)u，累加好u的前驅(qū)頂點(diǎn)到u 的距離。這就是要輸出的最小生成樹(shù)中的一條邊，并設(shè)置該頂點(diǎn)u和相應(yīng)的邊已連接在正在生成的最小生成樹(shù)中； 調(diào)整。隨著頂點(diǎn)u和相應(yīng)的邊已連接在正在生成的最小生成樹(shù)中，其他還不在正在生成的最小生成樹(shù)中的頂點(diǎn)到正在生成的最小生成樹(shù)(中的頂點(diǎn))的最短距離可能變小，這樣就需要對(duì)這些頂點(diǎn)到正在生成的最小生成樹(shù)的

40、最短距離進(jìn)行可能的調(diào)整。這個(gè)過(guò)程可以與剛連接到正在生成的最小生成樹(shù)的頂點(diǎn)u連接的頂點(diǎn)中去比較和調(diào)整。第三部分(輸出最小生成樹(shù)的代價(jià))：輸出生成的最小生成樹(shù)中每條邊上權(quán)值的累加值，即為所要求的最小生成樹(shù)的代價(jià)。2、數(shù)據(jù)結(jié)構(gòu)#define infinity 1000 / 設(shè)置權(quán)值的無(wú)窮大typedef struct linknode / 鄰接鏈表中的結(jié)點(diǎn)結(jié)構(gòu)int adjvex; / 鄰接的頂點(diǎn)的序號(hào)(下標(biāo)) int weight; / 鄰接頂點(diǎn)間的距離(權(quán)值) struct linknode *nextarc; / 指向下一個(gè)鄰接頂點(diǎn)的指針lnode,*link;typedef struct h

41、aednode / 鄰接表表頭數(shù)組中的元素結(jié)構(gòu)char data; / 頂點(diǎn)元素 link firstarc; / 頂點(diǎn)元素所指向鄰接結(jié)點(diǎn)所構(gòu)成的鄰接鏈表的指針hnode,*adj;Struct / 用Prim算法生成最小生成樹(shù)的主模塊分中用到的結(jié)構(gòu)體數(shù)組 int adjvex; / 存放圖中頂點(diǎn)的前驅(qū)頂點(diǎn)的序號(hào)(下標(biāo))； int lowcost; / 存放圖中頂點(diǎn)到正在生成的最小生成樹(shù)(中頂點(diǎn))的最短距離；closedge20;3、基本操作int locatevex(adj adjlist,char ch,int n) / 同高級(jí)語(yǔ)言課程設(shè)計(jì)中的圖的存儲(chǔ) / 在有n個(gè)頂點(diǎn)的表頭數(shù)組adjli

42、st中查找字符ch所代表的頂點(diǎn)在表頭數(shù)組的序號(hào)(下標(biāo))link locateedge(adj adjlist,int i,int j) 同高級(jí)語(yǔ)言課程設(shè)計(jì)中的圖的存儲(chǔ) / 從表頭數(shù)組adjlist中序號(hào)i所對(duì)應(yīng)的鄰接鏈表中查找是否有對(duì)應(yīng)序號(hào)j所對(duì)應(yīng)的邊adj inputnode(int *n) / 輸入n個(gè)頂點(diǎn)，同高級(jí)語(yǔ)言課程設(shè)計(jì)中的圖的存儲(chǔ) 申請(qǐng)表頭數(shù)組空間；; 輸入一頂點(diǎn)v； while(v不是結(jié)束標(biāo)記) if(v在表頭數(shù)組中不存在)v加入到表頭數(shù)組中； else / 可不做處理 輸出相應(yīng)信息； 輸入一頂點(diǎn)v； 返回表頭數(shù)組；void createadjlist(adj adjlist,i

43、nt n) / 在有n個(gè)頂點(diǎn)的表頭數(shù)組adjlist中輸入邊， / 建立圖的鄰接表，和高級(jí)語(yǔ)言課程設(shè)計(jì)中的圖/ 的存儲(chǔ)基本相同 輸入邊所在的頂點(diǎn)對(duì)； while(頂點(diǎn)對(duì)不是結(jié)束標(biāo)記) if(頂點(diǎn)對(duì)存在且邊不重復(fù)) 申請(qǐng)兩個(gè)鄰接鏈表中結(jié)點(diǎn)的空間； 在結(jié)點(diǎn)中分別存入邊所代表的兩個(gè)頂點(diǎn)在表頭數(shù)組中的序號(hào)(下標(biāo))；在表頭數(shù)組的序號(hào)(下標(biāo))所對(duì)應(yīng)的兩個(gè)鄰接鏈表的前面插入這兩條邊； else / 可不做處理 對(duì)于不符合要求的輸入，對(duì)應(yīng)輸出不符合要求的情況；輸入邊所在的頂點(diǎn)對(duì)；void list(adj ht,int n) / 和高級(jí)語(yǔ)言課程設(shè)計(jì)中的圖的存儲(chǔ)基本相同 / 輸出圖的鄰接表 / 可用V-U(權(quán)值

44、)的方式輸出邊void minispantree_prim(adj ht,int n) / 主模塊。用Prim算法生成最小生成樹(shù) / ht為圖的鄰接表的表頭數(shù)組，n為圖中的頂點(diǎn)數(shù)struct int adjvex; int lowcost;closedge20;對(duì)n個(gè)頂點(diǎn)到正在生成的最小生成樹(shù)(中頂點(diǎn))的最短距離closedgei.lowcost初始均置為無(wú)窮大infinity;任取一起始頂點(diǎn)k(可選取存儲(chǔ)的第一個(gè)頂點(diǎn))作為正在生成的最小生成樹(shù)的第一個(gè)頂點(diǎn)； p指向頂點(diǎn)k所對(duì)應(yīng)的鄰接鏈表； while(p不空) p所指頂點(diǎn)的前驅(qū)頂點(diǎn)置為k； p所指頂點(diǎn)到正在生成的最小生成樹(shù)的最短距離置為p所指

45、頂點(diǎn)的權(quán)值； p指向下一個(gè)頂點(diǎn)； 置頂點(diǎn)k為已在正在生成的最小生成樹(shù)中的標(biāo)志；/ 可把對(duì)應(yīng)的最短距離置為0 for(余下的n-1個(gè)頂點(diǎn)) 置min為無(wú)窮大infinity； / 在正在生成的最小生成樹(shù)外的頂點(diǎn)中找距離正在 for(圖中的所有頂點(diǎn)j) / 生成的最小生成樹(shù)最短的頂點(diǎn) if(頂點(diǎn)j的最短距離小于min且頂點(diǎn)j不在正在生成的最小生成樹(shù)中) min取頂點(diǎn)j的最短距離； 用k記錄頂點(diǎn)j； 用適當(dāng)?shù)母袷捷斴敵鲰旤c(diǎn)k的前驅(qū)頂點(diǎn)、k的前驅(qū)頂點(diǎn)到k 的距離和頂點(diǎn)k；/ 輸出用sum累加好k的前驅(qū)頂點(diǎn)到k 的距離； 置頂點(diǎn)k為已在正在生成的最小生成樹(shù)中的標(biāo)志； p指向頂點(diǎn)k所對(duì)應(yīng)的鄰接鏈表； / 調(diào)整while(p不空) if(p所指頂點(diǎn)的權(quán)值小于p所指頂點(diǎn)到正在生成的最小生成樹(shù)的最短距離) p所指頂點(diǎn)的前驅(qū)頂點(diǎn)置為k； p所指頂點(diǎn)到正在生成的最小生成樹(shù)的最短距離置為p所指頂點(diǎn)的權(quán)值； p指向下一個(gè)頂點(diǎn)； 輸出生成的最小生成樹(shù)中每條邊上權(quán)值的累加值sum；4、主程序int main() 調(diào)用inputnode()函數(shù)，輸入圖中的頂點(diǎn)，用ht得到鄰接表表頭數(shù)組，返回頂點(diǎn)的個(gè)數(shù)n； 調(diào)用createadjlist()函數(shù)，建立圖的鄰接表； 調(diào)用list()函數(shù)，顯示鄰接表； 調(diào)用minispan