數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)書1

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)書 （共13題）一、課程設(shè)計(jì)的目的課程設(shè)計(jì)的目的是培養(yǎng)學(xué)生綜合程序設(shè)計(jì)的能力，訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問題分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)和編程實(shí)現(xiàn)等軟件開發(fā)全過(guò)程的綜合實(shí)踐能力。鞏固、深化學(xué)生的理論知識(shí)，提高編程水平，并在此過(guò)程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的學(xué)習(xí)作風(fēng)。為今后學(xué)習(xí)其他計(jì)算機(jī)課程打下基礎(chǔ)。課程設(shè)計(jì)為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，獨(dú)立實(shí)踐的機(jī)會(huì)，將書本上的理論知識(shí)和工作、生產(chǎn)實(shí)際有機(jī)地結(jié)合起來(lái)，從而鍛煉學(xué)生分析問題、解決實(shí)際問題的能力，提高學(xué)生的編程序能力和創(chuàng)新意識(shí)。二、課程設(shè)計(jì)的要求在處理每個(gè)題目時(shí)，要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、構(gòu)思

2、算法、通過(guò)算法的設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完整的課程設(shè)計(jì)與程序分析報(bào)告。前期準(zhǔn)備工作完備與否直接影響到后序上機(jī)調(diào)試工作的效率。三、課程設(shè)計(jì)的學(xué)生分組情況每組三至五人，共同研究、共同討論，可以共同編寫算法，但必須各自獨(dú)立完成各自的程序。四、課程設(shè)計(jì)的時(shí)間安排課程設(shè)計(jì)前兩周：將各項(xiàng)任務(wù)及問題進(jìn)行講解、分析。課程設(shè)計(jì)一周： 星期一：學(xué)生對(duì)任務(wù)進(jìn)行討論、研究與分析，初步設(shè)計(jì)出算法。 星期二到星期四：設(shè)計(jì)出詳細(xì)算法，并上機(jī)調(diào)試程序。 星期五到星期六：寫出課程設(shè)計(jì)報(bào)告并考核。五、課程設(shè)計(jì)的主要內(nèi)容【課程設(shè)計(jì)題目一】一元稀疏多項(xiàng)式加法、乘法器【問題描述】設(shè)計(jì)一個(gè)

3、一元稀疏多項(xiàng)式加法、乘法器用于計(jì)算兩個(gè)多項(xiàng)式的加法和乘法。例如（x2+4x5+2x9）+(x+3x4)或（7x4+4x6+2x9）*(x4+3x9)【基本要求】（1） 輸入并建立兩個(gè)多項(xiàng)式f(x)和g(x)；（2） 輸出每個(gè)多項(xiàng)式，要求輸出時(shí)按指數(shù)從小到大輸出。（3） 兩個(gè)多項(xiàng)式完成加法、乘法運(yùn)算。（4） 輸出兩個(gè)多項(xiàng)式的加法之和及乘積的結(jié)果。（5） 寫出課程設(shè)計(jì)報(bào)告【實(shí)現(xiàn)提示】用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。【測(cè)試數(shù)據(jù)】分別選定三組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目二】局域網(wǎng)的架設(shè)問題【問題描述】若要在8個(gè)城市（A、B、C、D、E、F、G、H）之間架設(shè)局域網(wǎng)，如何以最低的經(jīng)濟(jì)

4、代價(jià)架設(shè)這個(gè)局域網(wǎng)?！净疽蟆浚?） 利用三種方法（Prim算法、克魯斯卡爾（Kruskual和矩陣運(yùn)算）算法生成局域網(wǎng)的架設(shè)方案（2） 寫出課程設(shè)計(jì)報(bào)告?！緶y(cè)試數(shù)據(jù)】分別對(duì)每種方法選定一組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目三】二叉樹的創(chuàng)建、二叉樹的遍歷【問題描述】創(chuàng)建一棵二叉樹，并對(duì)二叉樹進(jìn)行中序、前序、后序和層次遍歷，分別寫出它們的遞歸、非遞歸遍歷算法?！净疽蟆縿?chuàng)建多種（五種以上）不同形態(tài)的二叉樹，驗(yàn)證上述算法?！菊n程設(shè)計(jì)題目四】校園導(dǎo)游咨詢系統(tǒng)【問題描述】設(shè)計(jì)一個(gè)你所在學(xué)校的校園導(dǎo)游程序，為來(lái)訪的客人提供各種信息查詢服務(wù)。【基本要求】（1） 設(shè)計(jì)你所在學(xué)校的校園平面

5、圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱，代號(hào)，簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。（2） 為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。（3） 為來(lái)訪客人提供圖中任意景點(diǎn)的問路查詢，即查出任意兩個(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。（4） 寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】選定一組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性。【課程設(shè)計(jì)題目五】通信網(wǎng)絡(luò)的架設(shè)問題【問題描述】若要在n（10）個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可，如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題?！净疽蟆浚?）利用三種方法（Prim算法、克魯斯卡爾（Kruskual和矩陣

6、運(yùn)算）生成網(wǎng)中的最小生成樹（2）寫出課程設(shè)計(jì)報(bào)告?！緶y(cè)試數(shù)據(jù)】分別對(duì)每種方法選定三組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性。【課程設(shè)計(jì)題目六】?jī)?nèi)部排序的比較【問題描述】比較內(nèi)部排序冒泡排序、插入排序、二分插入排序、選擇排序的運(yùn)行時(shí)間。給出算法執(zhí)行的時(shí)間階或每個(gè)程序的運(yùn)行時(shí)間，精確到秒。【基本要求】（1）比較下列幾種內(nèi)部排序：冒泡排序、插入排序、二分插入排序、選擇排序的運(yùn)行時(shí)間。要求隨機(jī)生成20000個(gè)測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，并輸出每個(gè)程序的運(yùn)行時(shí)間，精確到秒。（2）寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】選定一批測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性并對(duì)計(jì)算時(shí)間進(jìn)行比較?！菊n程設(shè)計(jì)題目七】算法表達(dá)式的求值演算【問題描述

7、】以字符序列的形式從終端輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教科書給出的算符優(yōu)先關(guān)系，加上乘方()和求除（%）運(yùn)算符，實(shí)現(xiàn)對(duì)算術(shù)混合運(yùn)算表達(dá)式的求值?！净疽蟆浚?） 用順序棧實(shí)現(xiàn)（2） 含有乘方()、加(+)、減(-)、乘(*)、除(/)、求除（%）等運(yùn)算；并含有括號(hào)。（3） 分別以五組不同的表達(dá)式作為測(cè)試實(shí)例，每個(gè)實(shí)例中含有上述所有運(yùn)算符，測(cè)試其結(jié)果的正確性。（4） 寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】選定五組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目八】設(shè)計(jì)一個(gè)矩陣運(yùn)算器【問題描述】設(shè)計(jì)一個(gè)矩陣運(yùn)算器，對(duì)矩陣進(jìn)行乘方()、加(+)、減(-)、乘(*)運(yùn)算；【基本要求】（1） 參見

8、數(shù)據(jù)結(jié)構(gòu)題集P136頁(yè)4.1（2） 求含有乘方()、加(+)、減(-)、乘(*)運(yùn)算；。（3） 寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】分別選定一組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性。【課程設(shè)計(jì)題目九】自來(lái)水管理架設(shè)問題【問題描述】若要在揚(yáng)州大學(xué)的八個(gè)居民區(qū)（A區(qū)、B區(qū)、C區(qū)、D區(qū)、E區(qū)、F區(qū)、G區(qū)、H區(qū)）之間架設(shè)自來(lái)水管道，如何以最低的經(jīng)濟(jì)代價(jià)架設(shè)這個(gè)自來(lái)水管道?！净疽蟆浚?）利用三種方法（Prim算法、克魯斯卡爾Kruskual和矩陣運(yùn)算）算法生成自來(lái)水管道的架設(shè)方案（2）寫出課程設(shè)計(jì)報(bào)告?！緶y(cè)試數(shù)據(jù)】分別對(duì)每種方法選定三組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目十】校園網(wǎng)架設(shè)的方案設(shè)計(jì)

9、問題【問題描述】若要在揚(yáng)州大學(xué)的八個(gè)校區(qū)（江陽(yáng)路南校區(qū)、江陽(yáng)路北校區(qū)、鹽阜校區(qū)、瘦西湖校區(qū)、農(nóng)學(xué)院校區(qū)、工學(xué)院校區(qū)、水利學(xué)院校區(qū)、醫(yī)學(xué)院校區(qū)）之間架設(shè)校園網(wǎng)，如何以最低的經(jīng)濟(jì)代價(jià)架設(shè)這個(gè)校園網(wǎng)?！净疽蟆浚?）利用三種方法（Prim算法、克魯斯卡爾（Kruskual）和矩陣運(yùn)算）算法生成校園網(wǎng)的架設(shè)方案（2）寫出課程設(shè)計(jì)報(bào)告。【測(cè)試數(shù)據(jù)】分別對(duì)每種方法選定一組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目十一】學(xué)生成績(jī)管理系統(tǒng)【問題描述】現(xiàn)有學(xué)生成績(jī)信息文件1（1.txt），內(nèi)容如下姓名    學(xué)號(hào)   語(yǔ)文  數(shù)學(xué) 

10、  英語(yǔ)     張明明  01     67    78      82李成友  02     78    91      88張輝燦  03     68    82   &#

11、160;  56王露    04     56    45      77陳東明  05     67    38      47.      .      .    

12、.       學(xué)生成績(jī)信息文件2（2.txt）,內(nèi)容如下:姓名    學(xué)號(hào)   語(yǔ)文  數(shù)學(xué)   英語(yǔ)     陳果    31     57    68      82李華明  32     88 

13、0;  90      68張明東  33     48    42      56李明國(guó)  34     50    45      87陳道亮  35     47    58 

14、0;    77.      .      .     .       【基本要求】試編寫一管理系統(tǒng),要求如下:1) 實(shí)現(xiàn)對(duì)兩個(gè)文件數(shù)據(jù)進(jìn)行合并,生成新文件3.txt2) 抽取出三科成績(jī)中有補(bǔ)考的學(xué)生并保存在一個(gè)新文件4.txt3) 對(duì)合并后的文件3.txt中的數(shù)據(jù)按總分降序排序(至少采用兩種排序方法實(shí)現(xiàn))4) 輸入一個(gè)學(xué)生姓名后,能查找到此學(xué)生的信息并輸出結(jié)果(至少

15、采用兩種查找方法實(shí)現(xiàn))5) 要求使用結(jié)構(gòu)體和鏈表實(shí)現(xiàn)上述要求.【課程設(shè)計(jì)題目十二】學(xué)生成績(jī)管理系統(tǒng)【問題描述】現(xiàn)有學(xué)生成績(jī)信息文件1（1.txt），內(nèi)容如下姓名    學(xué)號(hào)   語(yǔ)文  數(shù)學(xué)   英語(yǔ)     張明明  01     67    78      82李成友  02     78

16、60;   91      88張輝燦  03     68    82      56王露    04     56    45      77陳東明  05     67  &

17、#160; 38      47.      .      .     .       學(xué)生成績(jī)信息文件2（2.txt）,內(nèi)容如下:姓名    學(xué)號(hào)   語(yǔ)文  數(shù)學(xué)   英語(yǔ)     陳果    3

18、1     57    68      82李華明  32     88    90      68張明東  33     48    42      56李明國(guó)  34   &#

19、160; 50    45      87陳道亮  35     47    58      77.      .      .     .       【基本要求】試編寫一管理系統(tǒng),要求如

20、下:1) 實(shí)現(xiàn)對(duì)兩個(gè)文件數(shù)據(jù)進(jìn)行合并,生成新文件3.txt2) 抽取出三科成績(jī)中有補(bǔ)考的學(xué)生并保存在一個(gè)新文件4.txt3) 對(duì)合并后的文件3.txt中的數(shù)據(jù)按總分降序排序(至少采用兩種排序方法實(shí)現(xiàn))4) 輸入一個(gè)學(xué)生姓名后,能查找到此學(xué)生的信息并輸出結(jié)果(至少采用兩種查找方法實(shí)現(xiàn))5) 要求使用結(jié)構(gòu)體和數(shù)組實(shí)現(xiàn)上述要求.【課程設(shè)計(jì)題目十三】算法表達(dá)式的求值演算【問題描述】以字符序列的形式從終端輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教科書給出的算符優(yōu)先關(guān)系，加上乘方()和求除（%）等運(yùn)算符，實(shí)現(xiàn)對(duì)算術(shù)混合運(yùn)算表達(dá)式的求值?！净疽蟆?1) 用鏈棧實(shí)現(xiàn)(2) 含有乘方()、加(+)、減(-

21、)、乘(*)、除(/)、求除（%）等運(yùn)算；并含有括號(hào)。(3) 分別以五組不同的表達(dá)式作為測(cè)試實(shí)例，每個(gè)實(shí)例中含有上述所有運(yùn)算符，測(cè)試其結(jié)果的正確性。(4) 寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】選定五組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性。六、課程設(shè)計(jì)報(bào)告的主要內(nèi)容課程設(shè)計(jì)報(bào)告主要包括以下幾方面的內(nèi)容：（1） 課程設(shè)計(jì)的題目（2） 課程設(shè)計(jì)的目的（3） 分析系統(tǒng)的主要功能及用途（4） 分析和描述系統(tǒng)的基本要求（5） 問題實(shí)現(xiàn)的主要算法與分析（6） 源程序（7） 使用方法與說(shuō)明（8） 課程設(shè)計(jì)的小結(jié)（9） 參考文獻(xiàn)七、課程設(shè)計(jì)的考核結(jié)合學(xué)生的動(dòng)手能力，獨(dú)立分析解決問題的能力和創(chuàng)新精神，總結(jié)報(bào)告和答辯水平以及

22、學(xué)習(xí)態(tài)度綜合考評(píng)。考核成績(jī)分優(yōu)、良、中、及格和不及格五等?？己酥饕韵聨追矫鎯?nèi)容：1） 運(yùn)行所設(shè)計(jì)的系統(tǒng)2） 回答相關(guān)題目的問題3） 提交課程設(shè)計(jì)報(bào)告4） 提交軟盤（含源程序、執(zhí)行程序和課程設(shè)計(jì)報(bào)告）5） 內(nèi)容要有創(chuàng)新。八、附錄(課程設(shè)計(jì)報(bào)告示例)數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計(jì) 報(bào) 告課題名稱最小生成樹問題 姓名× × × 學(xué)院 廣陵學(xué)院 系科班級(jí) 計(jì)科81101 指導(dǎo)老師 陳宏建 日期2013年1月12日 目錄l 一、問題描述 2l 二、概要設(shè)計(jì) 2n 1抽象數(shù)據(jù)類型定義2n 2程序包含模塊 2n 3函數(shù)調(diào)用關(guān)系 3l 三、詳細(xì)設(shè)計(jì) 3n 1頂點(diǎn)、邊、圖和集合

23、類型 3n 2圖的基本操作 4n 3程序詳細(xì)代碼 5n 4函數(shù)調(diào)用關(guān)系圖 15l 四、設(shè)計(jì)和調(diào)試分析15l 五、用戶手冊(cè)16l 六、測(cè)試結(jié)果18l 七、附件19l 八、心得體會(huì)20最小生成樹問題一、 問題描述1、 要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)絡(luò)，是一個(gè)網(wǎng)的最小生成樹問題。2、 利用克魯斯卡爾算法求網(wǎng)的最小生成樹。假設(shè)連通網(wǎng)N=（V，E），則令最小生成樹的的初始狀態(tài)為只有n個(gè)結(jié)點(diǎn)而無(wú)邊的非連通圖T=（V，），圖中每一個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去

24、此邊選擇下一條代價(jià)最小的邊。依次類推，直至T中所有頂點(diǎn)都在同一連通分量上為止。3、 使用Mfset類表示構(gòu)造生成樹過(guò)程中的連通分量。4、 測(cè)試數(shù)據(jù)（附后）。二、 概要設(shè)計(jì)1、 抽象數(shù)據(jù)類型定義如下：ADT Graph數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R=VRVR=(v,w)|v,wV,(v,w)表示v和w之間存在路徑基本操作P：CreatGraph(&G);操作結(jié)果：初始化一個(gè)圖。Initial(&S,n,x1,x2,xn);操作結(jié)果：初始化操作。構(gòu)造一個(gè)由n個(gè)子集（每個(gè)子集只含單個(gè)成員Xi）構(gòu)成的集合S。Find(S,v);初始條件：S是已

25、經(jīng)存在的集合，v是某個(gè)子集成員。操作結(jié)果：查找函數(shù)。返回S中v所屬子集Si。Merge(&S,i,j);初始條件：Si和Sj是S中兩個(gè)互不相交的非空集合。操作結(jié)果：歸并操作。將Si和Sj中的一個(gè)并入另一個(gè)。Kruskal(void);初始條件：圖G存在。操作結(jié)果：求圖G的最小生成數(shù)。Output(void);初始條件：已經(jīng)生成圖G的最小樹。操作結(jié)果：輸出操作。將最小生成樹以文本形式輸出到文件中。ADT Graph2、 本程序包含5個(gè)模塊1） 主程序模塊，其中主函數(shù)為main() 初始化圖形界面； 讀入用戶選擇信息； 根據(jù)用戶選擇執(zhí)行相應(yīng)模塊； 關(guān)閉文件及圖形界面； ；2） 漢字顯示模塊

26、實(shí)現(xiàn)DOS模式下的漢字顯示；3） 隨機(jī)圖單元模塊實(shí)現(xiàn)隨機(jī)生成圖；4） 讀圖模塊實(shí)現(xiàn)從指定文件中讀圖；5） 圖形輸出模塊實(shí)現(xiàn)圖的仿真輸出。6） 集合操作模塊實(shí)現(xiàn)集合的查找合并。7） 求最短路徑模塊實(shí)現(xiàn)Kruskal算法求圖最短路徑。3、 函數(shù)調(diào)用關(guān)系：三、 詳細(xì)設(shè)計(jì)1、 頂點(diǎn)、邊、圖和集合類型#define change(a,b) a=a+b,b=a-b,a=a-b;/交換兩個(gè)變量值/值#define NYAN /是否演示樹的生成過(guò)程typedef struct int x,y;/該城市的縱橫坐標(biāo) int tag;/該城市的訪問標(biāo)志 char name64;/城市名verType;/頂點(diǎn)類型ty

27、pedef struct int bg,ed;/邊的兩端頂點(diǎn)號(hào) int wt;/邊的權(quán)值 int tag;/邊的訪問標(biāo)志edgType;/邊類型typedef struct verType *v;/指向頂點(diǎn)集合 edgType *e;/指向邊集合 int vn,en;/頂點(diǎn)及邊的數(shù)目 char name64;/圖名字GType;/圖類型GType g;/圖全局變量FILE *fp;/文件指針變量2、 圖的基本操作void initgph(void);/初始化函數(shù)。將系統(tǒng)設(shè)置為圖形工作模式。void getdot(unsigned char c,unsigned char n8);/將c分解為二

28、進(jìn)制01串，存放在n中。int pnthz(int x,int y,int fcolor,int bcolor,char os);/x,y是屏幕坐標(biāo)，fcolor和bcolor是前景色及背景色，os是漢字字符串；在x,y位置輸出漢字串os。void copyedg(edgType *e1,edgType *e2)/ e1和e2是圖的兩條邊。將e1的內(nèi)容賦給e2。void randomedg(void)/初始化。對(duì)邊集進(jìn)行隨機(jī)賦值。void randomver(void)/初始化。對(duì)頂點(diǎn)集進(jìn)行隨機(jī)賦值。void readver(void)/讀入信息。將存放在文件里的圖頂點(diǎn)信息讀入內(nèi)存。void

29、readedg(void)/讀入信息。將存放在文件里的圖邊信息讀入內(nèi)存。void drawver(void)/繪圖操作。在屏幕上繪制結(jié)點(diǎn)。void drawedg(void)/繪圖操作。在屏幕上繪制邊。void initial(void)/初始化操作。構(gòu)造一個(gè)由n個(gè)子集（每個(gè)子集只含單個(gè)成員Xi）構(gòu)成的集合S。int find(int v)/S是已經(jīng)存在的集合，v是某個(gè)子集成員。返回S中v所屬子集Si。void merge(int v1,int v2)/S1和S2是S中兩個(gè)互不相交的非空集合。將S1和S2中的一個(gè)并入另一個(gè)。void kruskal(int v1,int v2)/求圖G的最小生

30、成樹。void output(void)/輸出操作。將最小生成樹以文本形式輸出到文件中。void fromfile(char fname)/fname是圖文件名。打開文件操作。打開圖信息文件，為讀圖做準(zhǔn)備。void userinput(void)/由用戶輸入圖文件名。void randomimage(void)/調(diào)用Randomedg()和Randomver()函數(shù)對(duì)邊集和頂點(diǎn)集進(jìn)行隨機(jī)賦值。int choose(void)/由用戶選擇圖信息的生成方式。返回選擇項(xiàng)的序號(hào)。3、 程序詳細(xì)代碼#include<stdio.h>#include<stdlib.h>#inclu

31、de<string.h>#include<time.h>#include<math.h>#include<graphics.h>#define change(a,b) a=a+b,b=a-b,a=a-b;#define NYANtypedef struct int x,y,tag; char name64;verType;typedef struct int bg,ed,wt,tag;edgType;typedef struct verType *v; edgType *e; int vn,en; char name64;GType;GType

32、g;FILE *fp;void initgph(void)int gmode,gdrive; printf("nntInitializtion graph mode, please wait."); gmode=DETECT; initgraph(&gmode,&gdrive,"C:Tc");void getdot(unsigned char c,unsigned char n8)char i; for(i=0;i<8;i+) ni=(c>>(7-i)&1);int pnthz(int x,int y,int f

33、color,int bcolor,char os)FILE *hzk=NULL; unsigned int j,k,cn2,cx,cy; unsigned long i,len,p; unsigned char c32,n8,ch2,s128; for(i=0,j=0,len=0;osj!='0'i+,j+,len+) if(osj>32) si+=0xAA; si=0xA1+(osj-33); len+; else if(osj=32) si+=0xA1; si=0xA1; len+; else si=osj; if(len=0) return(0); len/=2;

34、if(hzk=fopen("C:WindowsCommandChs16.fon","rb")=NULL) return(1); for(i=0;i<len;i+) ch0=si*2; ch1=si*2+1; cn0=(ch0-0xA1); cn1=(ch1-0xA1); p=(cn0*94L+cn1)*32L; rewind(hzk); fseek(hzk,p,0); fread(&c,sizeof(char),32,hzk); for(j=0;j<32;j+) getdot(cj,n); for(k=0;k<8;k+) cx=

35、(k+(j%2)*8+i*16+x)%640;cy=j/2+y+(k+(j%2)*8+i*16+x)/640)*16;if(nk=1) putpixel(cx,cy,fcolor);else if(bcolor!=-1) putpixel(cx,cy,bcolor); fclose(hzk); return(cx);void copyedg(edgType *e1,edgType *e2)e1->bg=e2->bg; e1->ed=e2->ed; e1->wt=e2->wt; e1->tag=e2->tag;void randomedg(void

36、)int i,j,tag; edgType re; if(g.e!=NULL) free(g.e); g.e=(edgType *)malloc(sizeof(edgType)*g.en); if(g.e=NULL) printf("nMalloc Error!"); return; for(i=0;i<g.en;i+) re.bg=random(g.vn); re.ed=random(g.vn); for(j=0,tag=0;j<i;j+) if(g.ej.bg=re.bg&&g.ej.ed=re.ed)|(g.ej.bg=re.ed&

37、&g.ej.ed=re.bg) tag=1; break; if(re.bg=re.ed|tag=1) i-; continue; re.wt=random(99)+1; re.tag=(-1); for(j=i;(g.ej-1.wt>re.wt)&&(j>0);j-) copyedg(&(g.ej),&(g.ej-1); copyedg(&(g.ej),&re); void randomver(void)int i,xc,yc,r; float dg,st,x,y; if(g.v!=NULL) free(g.v); g.v=

38、(verType *)malloc(sizeof(verType)*g.vn); if(g.v=NULL) printf("nMalloc Error!"); return; dg=0.0; st=Pi/g.vn*2.0; xc=getmaxx()/2; yc=getmaxy()/2; r=xc<yc?xc:yc-10; for(i=0,dg=0;i<g.vn;i+,dg+=st) x=xc+r*cos(dg); y=yc+r*sin(dg); g.vi.x=x; g.vi.y=y; g.vi.tag=0; sprintf(,"%02

39、d",i+1); void readver(void)int i,ord; if(g.v!=NULL) free(g.v); g.v=(verType *)malloc(sizeof(verType)*g.vn); if(g.v=NULL) printf("nMalloc Error in readver!"); return; for(i=0;i<g.vn;i+) fscanf(fp,"%d%s%d%d",&ord,,&g.vi.x,&g.vi.y); g.vi.tag=0; void read

40、edg(void)int i,j; edgType re; if(g.e!=NULL) free(g.e); g.e=(edgType *)malloc(sizeof(edgType)*g.en); if(g.e=NULL) printf("nMalloc Error in read edg!"); return; for(i=0;i<g.en;i+) fscanf(fp,"%d%d%d",&re.bg,&re.ed,&re.wt); re.tag=(-1); for(j=i;(g.ej-1.wt>re.wt)&

41、;&(j>0);j-) copyedg(&(g.ej),&(g.ej-1); copyedg(&(g.ej),&re); void drawver(void)int i,x1,y1,x2,y2; char s64; sprintf(s,"%s結(jié)點(diǎn)數(shù)：%d邊數(shù)：%d",,g.vn,g.en); pnthz(640-8*strlen()/3,0,12,-1,s); for(i=0;i<g.vn;i+) setcolor(12); setfillstyle(1,12); fillellipse(g.vi.

42、x,g.vi.y,4,4); pnthz(g.vi.x+8,g.vi.y,15,-1,); void drawedg(void)int i,x1,y1,x2,y2; char s10; for(i=0;i<g.en;i+) if(g.ei.tag<0) setcolor(7); else if(g.ei.tag=0) setcolor(8); else if(g.ei.tag=1) setcolor(10); else setcolor(g.ei.tag); x1=g.vg.ei.bg.x; y1=g.vg.ei.bg.y; x2=g.vg.ei.ed.x; y2

43、=g.vg.ei.ed.y; line(x1,y1,x2,y2); sprintf(s,"%d",g.ei.wt); outtextxy(x1+x2)/2+4,(y1+y2)/2-10,s); void initial(void) g.e0.tag=1;int find(int v)int i; for(i=0;(i<g.en)&&(g.ei.tag>=0);i+) if(g.ei.tag=0) continue; if(g.ei.bg=v|g.ei.ed=v) return g.ei.tag; return -1;void merge(int

44、v1,int v2)int i; if(v1>v2) change(v1,v2); for(i=0;(i<g.en)&&(g.ei.tag>=0);i+) if(g.ei.tag=v2) g.ei.tag=v1;void kruskal(void)int i,j=2,v1,v2; initial(); for(i=1,j=2;i<g.en;i+) v1=find(g.ei.bg); v2=find(g.ei.ed); if(v1=v2&&v1!=(-1) g.ei.tag=0; else if(v1=v2&&v1=(-1)

45、 g.ei.tag=j+; else if(v1*v2<0) g.ei.tag=(v1<0?v2:v1); else if(v1!=v2) merge(v1,v2); g.ei.tag=(v1<v2)?v1:v2; #ifdef YAN drawedg(); if(getch()=27) return; #endif void output(void)FILE *fout; int i; fout=fopen("OUTFILE.TXT","w"); if(fout=NULL) printf("nCan not open out

46、 file!"); getch(); return; fprintf(fout,"%sn",); for(i=0;i<g.en;i+) if(g.ei.tag=1) fprintf(fout,"%s - %st%dn", ,,g.ei.wt); fclose(fout);void fromfile(char fname)fp=fopen(fname,"r"); if(fp=NULL) pnthz(20,30,15,-1,"無(wú)法打開圖文件：

47、"); outtextxy(144,30,fname); pnthz(20,50,15,-1,"任意鍵返回"); getch(); cleardevice(); return; fscanf(fp,"%d%d%s",&g.vn,&g.en,); readver(); readedg(); kruskal(); drawedg(); drawver(); output(); pnthz(16,getmaxy()-20,15,0,"任意鍵返回"); getch();void userinput(voi

48、d)char name128; int i; char help848="圖文件結(jié)構(gòu)要求如下", "結(jié)點(diǎn)數(shù)邊數(shù)圖名", "結(jié)點(diǎn)序號(hào)坐標(biāo)坐標(biāo)名稱", "其他結(jié)點(diǎn)信息", "起始結(jié)點(diǎn)序號(hào)終止結(jié)點(diǎn)序號(hào)權(quán)值", "其他邊信息", "詳細(xì)示例參看附帶文件" for(i=0;i<8;i+) pnthz(36,100+i*20,15,-1,helpi); pnthz(40,30,15,-1,"圖形文件名："); gotoxy(18,3); ge

49、ts(name); cleardevice(); fromfile(name);void randomimage(void)int tag=1; randomize(); while(tag) cleardevice(); pnthz(120,95,15,-1,"輸入圖的結(jié)點(diǎn)數(shù)："); gotoxy(32,7); scanf("%d",&g.vn); pnthz(136,125,15,-1,"輸入圖的邊數(shù)："); gotoxy(32,9); scanf("%d",&g.en); if(g.en<

50、;=(g.vn*(g.vn-1)/2)&&g.vn>2&&g.vn<30&&g.vn<g.en) tag=0; else pnthz(136,150,15,-1,"數(shù)據(jù)錯(cuò)誤，請(qǐng)重新輸入！"); getch(); strcpy(,"隨機(jī)圖形"); cleardevice(); randomver(); randomedg(); kruskal(); drawedg(); drawver(); output(); pnthz(16,getmaxy()-20,15,0,"任

51、意鍵返回"); getch();int choose(void)int tag=2,key,i; char s632= "最小生成樹問題黃健制作", "請(qǐng)選擇：","【、演示圖（城市通信網(wǎng)絡(luò)）】", "【、用戶輸入圖文件】","【、隨機(jī)生成圖信息】", "【、退出系統(tǒng)（）】" cleardevice(); while(1) for(i=0;i<6;i+) pnthz(100,20*i+40,15,(i=tag?7:0),si); key=getch(); if

52、(key=13) break; else if(key=27) return(0); else if(key>'0'&&key<'5') tag=key-'0'+1; else if(key=0) key=getch(); switch(key) case 72: tag-; break; case 80: tag+; break; if(tag<2) tag=2; else if(tag>5) tag=5; while(kbhit() getch(); cleardevice(); return tag-

53、1;main()int i,tag=1; initgph(); settextstyle(1,0,1); do tag=choose(); switch(tag) case 1: fromfile("ChinaMap.txt"); break; case 2: userinput(); break; case 3: randomimage(); break; case 4: tag=0; break; while(tag); fcloseall(); closegraph();函數(shù)調(diào)用關(guān)系圖四、設(shè)計(jì)和調(diào)試分析1. 考慮到需要使用集合的并等運(yùn)算，故圖的存儲(chǔ)方式選用了以存儲(chǔ)邊（

54、帶權(quán)）的數(shù)組表示。原設(shè)計(jì)另外建立一個(gè)數(shù)組用來(lái)保存集合以及子集。后來(lái)發(fā)現(xiàn)實(shí)現(xiàn)比較困難。只好給邊增加一個(gè)tag域，其值為所屬該邊集合的序號(hào)。未訪問的邊賦值-1，已經(jīng)訪問的但不包含在最小生成樹中的邊賦值0。2. 在從文件中讀入邊的時(shí)候，考慮到后面要對(duì)邊進(jìn)行升序排序，故采用直接插入排序方式，每讀入一條邊就進(jìn)行一次插入排序。算法的時(shí)間復(fù)雜度為O(n2).3. 集合的并運(yùn)算需要遍歷全部已經(jīng)訪問過(guò)的邊，修改其tag值。故復(fù)雜度為O(n)?？唆斔箍査惴▽?duì)en條邊各掃描一次，時(shí)間復(fù)雜度為可以達(dá)到O(n)。4. 在實(shí)現(xiàn)漢字顯示時(shí)，涉及漢字的區(qū)位碼和機(jī)內(nèi)碼轉(zhuǎn)換問題，在進(jìn)行了多次嘗試后得到轉(zhuǎn)換公式。另外還涉及到文件

55、的二進(jìn)制讀，以及二進(jìn)制移位操作等。由于每一個(gè)漢字都是由256個(gè)像素構(gòu)成，所以顯示一個(gè)長(zhǎng)度為n的漢字串的時(shí)間復(fù)雜度為O(n3).五、用戶手冊(cè)1. 本程序運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為Image.exe。2. 進(jìn)入系統(tǒng)后顯示選擇菜單：圖13. 使用上下鍵或數(shù)字鍵選擇一個(gè)項(xiàng)目，則進(jìn)入選項(xiàng)。1.選項(xiàng)一運(yùn)行結(jié)果如下圖2所示：圖2其中顏色為亮綠色（該處為深灰色）的是在最小生成樹中的邊。2.進(jìn)入選項(xiàng)二后用戶會(huì)看到提示如圖3（見下頁(yè)）。按要求輸入圖文件名，例如輸入Ceshi.txt并回車，調(diào)用附帶的測(cè)試文件，可以看到的輸出畫面見圖4。其中顏色為亮綠色（該處為深灰色）的是在最小生成樹中的邊。3.選項(xiàng)三的運(yùn)行效果和選項(xiàng)一類似。4.程序運(yùn)行后會(huì)將運(yùn)行結(jié)果以文本形式輸出到文件OutFile.txt中，供用戶查詢使用。圖3圖45.由于圖文件的格式要求比較高，故提供了兩個(gè)示例文件ChinaMap.txt和CeShi.txt，用戶可以參考創(chuàng)建其他圖文件。其含義如圖3中所示。六、測(cè)試結(jié)果測(cè)試文件ChinaMap.