數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告撰寫要求

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告撰寫要求（一）紙張與頁面設(shè)置1 采用國際標(biāo)準(zhǔn) A4 型打印紙或復(fù)印紙，縱向打印。2 頁邊距：上 3.5cm、下 2.5cm、左邊距 3.0cm，右邊距 2.5cm。3頁眉 2.5cm、頁腳 1.8cm、對稱頁邊距。（二）頁眉“沈陽航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告” ，五號楷體，居中。（三）頁腳標(biāo)頁碼，五號宋體，居中。（四）題目、摘要、關(guān)鍵詞題目：小二號黑體，居中。（五）標(biāo)題一級標(biāo)題，三號粗宋體，居中，用“1 ”、“ 2 ”、“3 ”等表示序號。二級標(biāo)題，小三號粗宋體，左對齊，用“1.1 ”、“ 1.2 ”、“1.3 ”等表示序號。三級標(biāo)題，四號粗宋體，左對齊，用“”、“”、“”等表

2、示序號。（六）正文小四號宋體，兩端對齊，1.5 倍行距。（七）圖、表1 表頭包括：表標(biāo)識及表名兩部分，表頭在表上，居中，用五號宋體字。2圖頭包括：圖標(biāo)識及圖名兩部分，圖頭在圖下，居中，用五號宋體字。（八）參考文獻(xiàn)格式： 序號 作者 . 譯者 . 書名 . 版本 . 出版社，出版時間（九）報(bào)告封頁及模版見下頁沈陽航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目： PRIM算法求最小生成樹院（系）：計(jì)算機(jī)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級：7401102班學(xué)號：200704011030姓名：指導(dǎo)教師：鄭志勇目錄沈陽航空工業(yè)學(xué)院.-2 -1需求分析 .11.1題目內(nèi)容及要求 .11.

3、2題目分析 .12系統(tǒng)設(shè)計(jì) .32.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) .32.2函數(shù)設(shè)計(jì) .42.2.1 系統(tǒng)流程 .5main( )Huitu( )prim （）結(jié)束GraphicVer()圖 2.2.1 系統(tǒng)流程.52.2.2 PRIM 函數(shù)流程 .52.2.3 Huitu 函數(shù)流程 .62.2.4 GraphicVer函數(shù)輸出鄰接矩陣 .63調(diào)試分析 .73.1調(diào)試初期 .73.2調(diào)試中期 .73.3調(diào)試后期 .94測試及運(yùn)行結(jié)果 .104.1歡迎界面 .104.2獲取輸入，繪制無向圖 .104.3輸出鄰接矩陣 .134.4. 演示 PRIM算法生成最小生成樹 .134.5用戶退出 .14參考文獻(xiàn) .15

4、附錄（關(guān)鍵部分程序清單）. 161 需求分析1.1題目內(nèi)容及要求以合適方便的方式輸入一個帶權(quán)值的無向圖，采用合適的存儲結(jié)構(gòu)存儲該無向圖。然后根據(jù)PRIM算法求該無向圖的最小生成樹并輸出。要求： 1. 輸入無向圖的方法盡量簡單方便2. 要能夠形象方便地觀察無向圖的圖形結(jié)構(gòu)3. 要能夠形象地演示 PRIM算法求最小生成樹的過程1.2題目分析剛拿到題目，乍看一下題目很簡短，貌似很簡單，但是細(xì)看之后就發(fā)現(xiàn)了很多隱藏在簡短語句后的更深一層次的要求。首先是“以合適方便的方式輸入” ，短短十個字就向你提出了兩方面要求：首先是“輸入”，即代表你最好可以得到一種通用的算法讓你對一定范圍內(nèi)的數(shù)據(jù)進(jìn)行運(yùn)算后從而得到

5、正確的結(jié)果； “合適方便” 即提示你要從輸入方便且有利于運(yùn)算的輸入數(shù)據(jù)的方法；采用合適的存儲結(jié)構(gòu)必然是本次課設(shè)當(dāng)之無愧的重點(diǎn)，亦是此題目的第三方面要求；最后就是用PRIM算法求無向圖的最小生成樹。PRIM算法在理解與實(shí)現(xiàn)方面不是很困難，但要求能夠形象的演示該算法就不是那么簡單了。無論從算法角度，還是從輸入方便、存儲安全角度，數(shù)組都是此次課設(shè)的不二選擇，即采用鄰接矩陣的存儲方式來存儲無向帶權(quán)圖。雖然鄰接表的動態(tài)存儲可以令該算法使用更大規(guī)模的數(shù)據(jù)并在一定范圍內(nèi)比數(shù)組更加節(jié)省空間并有更高的效率，但此次課設(shè)另一個重點(diǎn)就是演示算法而非真正的應(yīng)用于實(shí)際問題，所以只需要較少的數(shù)據(jù)量來完成PRIM 算法的演示

6、即可。故數(shù)組的便于操作及更加穩(wěn)定、方便的優(yōu)勢便凸顯出來。在畫圖這個問題上，我曾一度找錯了方向。剛拿到題目時，我只是望文生義的認(rèn)為我需要演示的是最小生成樹一步一步的演示過程，這讓我一度選擇VC6.0中的 MFC來演示過程。但后來，當(dāng)我因?yàn)镸FC當(dāng)量調(diào)用 WINDOWS的程序并有較多的頭文件而焦頭爛額的時候，重讀課設(shè)要求的時候我才發(fā)現(xiàn)，過于注重細(xì)枝末節(jié)的我竟沒有抓住此題目真正要求！ “模擬 PRIM算法最小生成樹的過程”即是讓你顯示 PRIM算法在更接近計(jì)算機(jī)可以理解的方式上顯示其具體過程。Turbo C 的超強(qiáng)的圖像處理讓我明白，它就是我這次課設(shè)的系統(tǒng)環(huán)境了。2 系統(tǒng)設(shè)計(jì)2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)對于

7、無向圖的任何操作，無疑都必須依賴于數(shù)據(jù)的存儲結(jié)構(gòu)。這里的存儲結(jié)構(gòu)不僅僅指的是數(shù)據(jù)在計(jì)算機(jī)中的物理內(nèi)存，更多的是抽象程度更高的抽象數(shù)據(jù)結(jié)構(gòu)。圖的存儲結(jié)構(gòu)主要有兩種: 鄰接矩陣和鄰接表。鄰接表以一個一維數(shù)組作表頭節(jié)點(diǎn)存儲圖的頂點(diǎn)，然后利用表頭引出所有以該點(diǎn)為箭尾的鄰接邊的信息；而鄰接矩陣則是單獨(dú)建立一個一維數(shù)組來存儲頂點(diǎn)的信息，并以頂點(diǎn)的個數(shù)來建立一個相應(yīng)的 N階對稱矩陣，以二維數(shù)組存儲單元來存儲相應(yīng)邊的權(quán)值。由于 PRIM算法需要多次修改closeedge 中的 adjvex 和 lowcost 值，且此次數(shù)據(jù)規(guī)模較小，只需達(dá)到演示部分?jǐn)?shù)據(jù)即可，所以統(tǒng)一采用數(shù)組的存儲結(jié)構(gòu)，即亦采用鄰接矩陣的存儲

8、結(jié)構(gòu)來存儲無向帶權(quán)圖更利于實(shí)現(xiàn)及操作。鄰接矩陣的抽象數(shù)據(jù)結(jié)構(gòu)定義：#defineINFINITYINT_MAX/最大值#defineMAX_ERTEX_NUM20/最大頂點(diǎn)數(shù)typedef enum DG , DN , UDG , UDN GraphKind;/有向圖，有向網(wǎng)，無向網(wǎng)，無向圖 typedef struct Arc CellVRTypeadj ;/VRType是頂點(diǎn)關(guān)系的類型。對無權(quán)圖，用1 和0表示相鄰否；對 / 帶權(quán)圖則為權(quán)值類型InfoType * info;/該弧相關(guān)信息的指針ArcCell , AdjMatrix MAX_VERTEX_NUMMAX_VERTEX_NUM

9、；Typedef struct VertexType vexs MAX_VERTEX_NUM ;/頂點(diǎn)向量AdjMatrixarcs ;/鄰接矩陣intvexnum , arcnum ;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKindkind ;/圖的種類標(biāo)志Mgraph ;2.2 函數(shù)設(shè)計(jì)本系統(tǒng)所使用的函數(shù)見表2.2.1表 2.2.1 本系統(tǒng)所使用的函數(shù)函數(shù)名稱函數(shù)原型功能描述main()int main(void)系統(tǒng)調(diào)用主函數(shù)Huiru()Void Huitu ()繪制無向圖GraphicVervoid GraphicVer(Graph *G)輸出鄰接矩陣()prim()void prim(Gr

10、aph *G)PRIM算法演示本系統(tǒng)所調(diào)用函數(shù)調(diào)用的關(guān)系見圖main( )Huitu( )GraphicVer()prim （）結(jié)束圖 2.2.2本系統(tǒng)的函數(shù)調(diào)用關(guān)系2.2關(guān)鍵流程流程圖能直觀和系統(tǒng)地把主函數(shù)的各個執(zhí)行步驟和調(diào)用的子函數(shù)以及調(diào)用先后表示出來，子函數(shù)中也有調(diào)用其他子函數(shù)的情況，畫出子函數(shù)的流程圖能清楚地看出子函數(shù)中各步語句的執(zhí)行，下面是關(guān)于主函數(shù)流程和關(guān)鍵的子函數(shù)流程圖的直觀表示。系統(tǒng)流程main( )Huitu( )prim （）GraphicVer()圖系統(tǒng)流程函數(shù)流程開始聲明輸出兩數(shù)組值標(biāo)記上一頂點(diǎn)lowcost,closest 數(shù)組在lowcost中尋初始化 lowcos

11、t找最小值并記錄其輸出兩數(shù)組值并標(biāo)記 lowcost1對應(yīng)點(diǎn)表函數(shù)流程結(jié)束更新 lowcost結(jié)束函數(shù)流程開始在相應(yīng)位置繪制圓圖形初始化并涂上顏色，在圓心處添加頂點(diǎn)獲取用戶輸入定義變量坐標(biāo)、頂點(diǎn)獲取用戶輸入判斷用戶輸坐標(biāo)、頂點(diǎn)入是否為 0退出表函數(shù)流程GraphicVer 函數(shù)輸出鄰接矩陣開始按頂點(diǎn)數(shù)初清屏始化二維數(shù)組輸入頂點(diǎn)按邊數(shù)重復(fù)獲取邊權(quán)值輸出矩陣內(nèi)的權(quán)值或無數(shù)、邊數(shù)輸入鄰接矩陣內(nèi)窮大結(jié)束圖函數(shù)輸出鄰接矩陣3 調(diào)試分析3.1調(diào)試初期由于編寫的程序具有模塊化的特性，且VC的熟練程度遠(yuǎn)優(yōu)于 TC等方面，我選擇先在VC 6.0 的調(diào)試顯然由于TC及個人對VC6.0 環(huán)境下完成除圖形化演示算法過

12、程函數(shù)的其他過程。由于數(shù)據(jù)結(jié)構(gòu)選擇的較合理， 且對 PRIM算法理解的較為深刻， 所以在此環(huán)境下的調(diào)試并沒有太多困難，只是簡單的筆誤。添加了畫圖函數(shù)后，我就不得不使用TC編程環(huán)境。本人使用的是 vista 系統(tǒng)，剛運(yùn)行 TC就發(fā)現(xiàn)提示：該操作系統(tǒng)不支持 16 bit MS-DOS系統(tǒng)。上網(wǎng)查看幫助，安裝了 DOSBOX軟件虛擬出 DOS系統(tǒng)運(yùn)行，才開始之后的調(diào)試。3.2 調(diào)試中期由于 Turbo C 2.0不支持鼠標(biāo)，更沒有剪切、粘貼等常用快捷的操作，且本人對計(jì)算機(jī)圖形學(xué)、 TC的圖形函數(shù)了解甚少，本人電腦更是不兼容TC全屏模式，所以這段時期成為最讓本人備受煎熬的時期。首先，由于TC 操作復(fù)雜

13、，更因?yàn)楸救俗兂闪?xí)慣不好，導(dǎo)致經(jīng)常一運(yùn)行就死機(jī)還沒保存過的代碼就又 “恢復(fù)出廠化”，讓所見之人無不扼腕惋惜， 本人亦是痛心疾首，苦不堪言。編譯過程出現(xiàn)過的錯誤有把自定義函數(shù)的名字與TC 圖形化函數(shù)其中一個的關(guān)鍵字相同， TC顯示“該函數(shù)定義了多重特性”或“該函數(shù)數(shù)值過多”等類似提示的錯誤排除。圖初始化錯誤將自定義的 initgraph函數(shù)重新命名為void huitu( ),即可排除此錯誤。再次編譯，又發(fā)現(xiàn)指針錯誤：圖指針錯誤Outtextxy(int x,inty ,*p) ，即要求最后一項(xiàng)為指向一字符串的指針。數(shù)組就是指針，如果這里出錯，那只應(yīng)該是我定義的 lowcose 存儲的數(shù)不是字符

14、串。所以我曾試圖用 strcpy() 將數(shù)組內(nèi)數(shù)據(jù)一一進(jìn)行傳拷貝到一指針，然后再調(diào)用 outtextxy （）。但是結(jié)果依然錯誤！后來，在同學(xué)的幫助下， 我終于弄明白是因?yàn)槲覕?shù)組內(nèi)存儲的是整數(shù)型數(shù)據(jù)，必 然無 法 通過strcpy()轉(zhuǎn)換 成 指針 。后來 ， 我改 用vsprintf(tmp,"%d",&lowcostvex-i)，即現(xiàn)將整型轉(zhuǎn)化為字符串，此錯誤即可3.3調(diào)試后期圖 3.3連接錯誤這是經(jīng)過多次修改后，最后一個編譯錯誤。該名定義是你所使用的視頻顯示模式，影響的是圖形化后的屏幕像素及可支持的最大色彩。經(jīng)試驗(yàn)，此程序在另一臺XP 電腦上可編譯成功，故本人

15、認(rèn)為是由于VISTA的兼容性導(dǎo)致 TC無法調(diào)用該定義， 即使使用虛擬機(jī)也無法排除。 考慮到此語句對輸出結(jié)果影響不大，故將此語句刪除，即使得TC自動獲取其他可用的視頻模式。編譯成功！4 測試及運(yùn)行結(jié)果4.1歡迎界面運(yùn)行程序，首先進(jìn)入用戶的歡迎界面。 模擬界面向?qū)?IRIS 采用互動式的方法提示用戶進(jìn)入 PRIM算法演示界面。首先 IRIS 會先詢問用戶是否愿意看 PRIM算法演示，若此時用戶選擇“ y”，用戶即可順利進(jìn)入模擬 PRIM的程序（見圖）；圖用戶歡迎界面及正常進(jìn)入算法演示界面否則 , 向?qū)в亚樘崾究梢灾苯油顺龀绦?，其效果圖見圖。圖用戶選擇退出算法演示的界面4.2 獲取輸入，繪制無向圖創(chuàng)

16、建無向圖， 動態(tài)顯示在屏幕上， 并輸出其存儲結(jié)構(gòu)， 即無向網(wǎng)的鄰接矩陣。首先按照提示，收入先要創(chuàng)建頂點(diǎn)的坐標(biāo)及其名。其效果圖見圖圖動態(tài)建立無向圖輸入時需要注意的是，由于該程序時默認(rèn)添加一點(diǎn)則連接相應(yīng)的直線，所以在一點(diǎn)多線的時候，像例子中的A 點(diǎn)，就要重新返回A 后再連接其他點(diǎn)。具體操作見圖。圖建立一點(diǎn)多線時的具體操作方法圖創(chuàng)建無線圖的最終效果圖4.3輸出鄰接矩陣向?qū)Э梢宰詣舆M(jìn)入輸出鄰接矩陣的界面圖鄰接矩陣的開始界面由于“”無法被TC識別，故該位置改用可以識別的其他特殊符號“-”。圖輸入邊信息圖鄰接矩陣的輸出4.4.演示 PRIM算法生成最小生成樹向?qū)容敵鰧υ撍惴ǖ慕榻B，然后提示用戶開始算法的

17、演示。圖算法的介紹用戶確認(rèn)后開始算法的每個步驟。其生成過程見圖圖第一次查找后lowcost和 closest數(shù)組值的變化圖第二次查找后lowcost和 closest數(shù)組值的變化圖第三次查找后lowcost和 closest數(shù)組值的變化圖相關(guān)算法4.5用戶退出演示完成后，向?qū)Э商崾咀詣油顺觥D 4.5退出界面參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民 . 數(shù)據(jù)結(jié)構(gòu) (C 語言版 )M. 北京 : 清華大學(xué)出版社 ,20062 呂國英 . 算法設(shè)計(jì)與分析 M. 北京 : 清華大學(xué)出版社 ,20063 李蘭友 .Turbo C 實(shí)用圖形程序設(shè)計(jì) M. 北京 . 科技翻譯出版公司， 19944 侯風(fēng)巍 . 數(shù)據(jù)結(jié)構(gòu)

18、要點(diǎn)精析 C 語言版 M. 北京：北京航空航天大學(xué)出版社，20075 亦歐 .TURBO C+運(yùn)行庫函數(shù)源程序與參考大全 M. 北京 . 學(xué)院出版社， 19936 謝明與 .Borland C+/Turbo C+ 編程實(shí)例剖析 M. 北京 . 科學(xué)出版社 .19937 衛(wèi)寧 .Turbo C+ for DOS 入門 .M. 北京 . 學(xué)院出版社， 1994附錄（關(guān)鍵部分程序清單）#include<graphics.h>#include <stdio.h>#include <string.h>#include <stdlib.h>#include

19、<conio.h>#define MaxVertexNum 50#define INF 32767typedef struct Graphicchar vexsMaxVertexNum;int edgesMaxVertexNumMaxVertexNum;int v,e;Graph;char tmp10;voidHuitu()/* 無向圖的圖形生成 */char buffer100;int graphdriver = DETECT, graphmode;int i,xbefore,ybefore;int x1,y1; char c;/*registerbgidriver(EGAVGA

20、_driver);*/*使用EGAVGA顯卡模式，分辨率為 640*480*/ initgraph(&graphdriver, &graphmode, ""); cleardevice(); /*/*圖形初始化 */清屏 */printf("input pot (300<x<610,y<400):ninput 0 to halt!n");setfillstyle(1,WHITE);setcolor(WHITE);scanf("%d,%d,%s",&xbefore,&ybefore,bu

21、ffer);circle(xbefore,ybefore,15);floodfill(xbefore,ybefore,WHITE);setcolor(BLUE);outtextxy(xbefore, ybefore, buffer);setcolor(WHITE);moveto(xbefore,ybefore);while(1)scanf("%d,%d,%s",&x1,&y1,buffer);if(x1=0) break;circle(x1,y1,15);floodfill(x1,y1,WHITE);setcolor(BLUE);outtextxy(x1,

22、y1, buffer);setcolor(WHITE);line(xbefore,ybefore,x1,y1);xbefore=x1;ybefore=y1;system("pause");void GraphicVer(Graph *G)/*build and output the adjMatrix*/int i,j,k,weight;int v1,v2;printf("input vertex's and edges's number :");scanf("%d,%d",&G->v,&G-&g

23、t;e);for(i=1;i<=G->v;i+)for(j=1;j<=G->v;j+)if(i=j)G->edgesij=0;else G->edgesij=INF; /* 初始化矩陣，全部元素設(shè)為無窮大 */ for(k=1;k<=G->e;k+)printf("input %dth edge :",k); scanf("%d,%d,%d",&v1,&v2,&weight); G->edgesv1v2=G->edgesv2v1=weight;for(i=1;i<=

24、G->v;i+)printf("n");for(j=1;j<=G->v;j+)printf(G->edgesij=INF)?" t":"%dt",G->edgesij);printf("n");system("pause");/*prim*/void prim(Graph *G)算法生成最小生成樹int lowcostMaxVertexNum,closestMaxVertexNum; int i,j,k,min;for(i=2;i<=G->v;i+)/*

25、n個頂點(diǎn)， n-1條邊*/lowcosti=G->edges1i;/*初始化 */closesti=1;/*頂點(diǎn)未加入到最小生成樹中*/lowcost1=0;for(i=2;i<=G->v;i+)/*/*標(biāo)志頂點(diǎn) 1 加入 U 集合 */形成 n-1 條邊的生成樹*/min=INF;k=0;for(j=2;j<=G->v;j+)/*尋找滿足邊的一個頂點(diǎn)在U,另一個頂點(diǎn)在 V 的最小邊 */if(lowcostj<min)&&(lowcostj!=0)min=lowcostj;k=j;printf("(%d,%d)%2dt"

26、,closestk,k,min); /*輸出最 小生成樹的邊及對應(yīng)的權(quán)值*/lowcostk=0;/*頂點(diǎn)k 加入U*/for(j=2;j<=G->v;j+)/*修改由頂點(diǎn)k 到其他頂點(diǎn)邊的權(quán)值*/if(G->edgeskj<lowcostj)lowcostj=G->edgeskj;closestj=k;printf("n");void drawwapicture(int lowcost,int closest,int vex)int i=0,x=0,datax=0;setviewport(150,140,630,310,1);cleardev

27、ice();setcolor(GREEN);rectangle(10,10,470,160);line(10,60,470,60);line(10,110,470,110);for(i=0;i<vex;i+)x=470-40*i;datax=470-20*i;line(x,10,x,160);if(vex-i)!=0)outtextxy(datax,35,"(vex-i)0");vsprintf(tmp,"%d",&lowcostvex-i);outtextxy(datax,85,tmp);vsprintf(tmp,"%d&quo

28、t;,&closestvex-i);outtextxy(datax,135,tmp);elseouttextxy(datax,35,"i0");outtextxy(datax,85,"lowcost0");outtextxy(datax,135,"closest0");getche();closegraph();/*prim算法生成最小生成樹*/void primyanshi(Graph *G)void drawwapicture(int *p,int*q,int k);int lowcostMaxVertexNum,clos

29、estMaxVertexNum; int i,j,k,min;cleardevice();for(i=2;i<=G->v;i+)/*n個頂點(diǎn)， n-1條邊*/lowcosti=G->edges1i;/*初始化 */closesti=1;/*頂點(diǎn)未加入到最小生成樹中*/drawwapicture(lowcost,closest,G->v);lowcost1=0;/*drawwapicture(lowcost,closest,G->v);for(i=2;i<=G->v;i+)/*標(biāo)志頂點(diǎn) 1 加入 U 集合 */形成 n-1 條邊的生成樹*/min=INF

30、;k=0;for(j=2;j<=G->v;j+)/*尋找滿足邊的一個頂點(diǎn)在U,另一個頂點(diǎn)在V 的最小邊*/if(lowcostj<min)&&(lowcostj!=0)min=lowcostj;k=j;drawwapicture(lowcost,closest,G->v);cprintf("(%d,%d)%2dt",closestk,k,min); /*輸出最小生成樹的邊及對應(yīng)的權(quán)值*/lowcostk=0;/*drawwapicture(lowcost,closest,G->v);for(j=2;j<=G->v;j

31、+)/*頂點(diǎn) k 加入 U*/修改由頂點(diǎn) k 到其他頂點(diǎn)邊的權(quán)值*/if(G->edgeskj<lowcostj)lowcostj=G->edgeskj;closestj=k;drawwapicture(lowcost,closest,G->v);printf("n");int main()Graph *G=NULL;int flag=1;printf("/*/n");printf("/*Welcome to the world of IRIS*/n");printf("/*200704011030*/n");while(fla