圖生成樹(shù)實(shí)驗(yàn)報(bào)告--上海電機(jī)學(xué)院

1、目錄1課程設(shè)計(jì)內(nèi)容11.1課程設(shè)計(jì)目的11.2課程設(shè)計(jì)耍求11.3課程設(shè)計(jì)背景12概要設(shè)計(jì)22. 1程序功能模塊結(jié)構(gòu)圖22.2菜單界面說(shuō)明22.3讀入文件說(shuō)明22.4輸出孩子鏈表結(jié)構(gòu)說(shuō)明23詳細(xì)設(shè)計(jì)33. 1鄰接矩陣的定義和孩子鏈表表示法定義33.1從文件中讀入無(wú)向圖的結(jié)點(diǎn)和邊的信息并創(chuàng)建無(wú)向圖43.2輸出圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)73. 3深度優(yōu)先遍歷83. 4創(chuàng)建樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu) 93. 5輸出樹(shù)的孩了鏈表存儲(chǔ)結(jié)構(gòu) 104遇到的問(wèn)題與解決方案 12小結(jié)13參考文獻(xiàn)141課程設(shè)計(jì)內(nèi)容1.1課程設(shè)計(jì)目的課程設(shè)計(jì)題目：圖生成樹(shù)隨機(jī)輸入一個(gè)無(wú)向圖，通過(guò)深度優(yōu)先遍歷或廣度優(yōu)先遍歷輸出該圖的生成樹(shù)，并將

2、該 生成樹(shù)以二叉鏈表形式或孩了鏈表表示法存儲(chǔ)。若使用二叉鏈表存儲(chǔ)，則對(duì)此存儲(chǔ)結(jié)構(gòu)進(jìn) 行遍歷，如果使用孩子鏈表表示法，則輸出生成樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)。1. 2課程設(shè)計(jì)要求程序要求實(shí)現(xiàn)的功能有：（1）輸入的頂點(diǎn)與弧的信息通過(guò)鄰接表或鄰接矩陣構(gòu)建一個(gè)無(wú)向圖；（2）通過(guò)圖的dfs或bfs過(guò)程得到該無(wú)向網(wǎng)的一棵生成樹(shù)。（3）使用孩子鏈表表示法或二叉鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)生成樹(shù)。（4）對(duì)存儲(chǔ)樹(shù)的二義鏈表進(jìn)行遍歷或者輸出生成樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)；1. 3課程設(shè)計(jì)背景無(wú)向圖的生成樹(shù)是在網(wǎng)絡(luò)和回路分析中經(jīng)常遇到的重要問(wèn)題，功能強(qiáng)大、可靠的網(wǎng)絡(luò) 需要有效地傳輸流量，提供兀余和故障的快速恢復(fù)功能。在第2層網(wǎng)絡(luò)中，路由協(xié)議

3、不可 用，牛成樹(shù)協(xié)議通過(guò)從軟件層面修改網(wǎng)絡(luò)物理拓?fù)浣Y(jié)構(gòu)來(lái)構(gòu)建一個(gè)無(wú)環(huán)路邏輯轉(zhuǎn)發(fā)拓?fù)浣Y(jié) 構(gòu)，提供了物理線路的兀余連接，消除了網(wǎng)絡(luò)風(fēng)暴，從而提高網(wǎng)絡(luò)的穩(wěn)定性和減少網(wǎng)絡(luò)故 障的發(fā)生率。生成樹(shù)協(xié)議（spanning tree protocol）是在網(wǎng)絡(luò)有環(huán)路時(shí)，通過(guò)一定的算法將 交換機(jī)的某些端口進(jìn)行阻塞，從而使網(wǎng)絡(luò)形成一個(gè)無(wú)環(huán)路的樹(shù)狀結(jié)構(gòu)。在實(shí)踐中理解面向 對(duì)象語(yǔ)言的設(shè)計(jì)方式。2概要設(shè)計(jì)2.1程序功能模塊結(jié)構(gòu)圖2. 2菜單界面說(shuō)明本次課程設(shè)計(jì)，按照要求，需要的完成的有創(chuàng)建圖的存儲(chǔ)結(jié)構(gòu)，圖生成樹(shù)，樹(shù)的存儲(chǔ)。 為了使菜單更加美化以及程序功能更加完善，木代碼增加了輸出鄰接矩陣功能、輸出圖生 成樹(shù)的定義、清屏

4、以及退岀程序的功能。2. 3讀入文件說(shuō)明為了使程序具有更大的適用件和方便程序調(diào)試，本課程設(shè)計(jì)代碼采取從文件屮讀入圖 的頂點(diǎn)和邊的信息來(lái)創(chuàng)建圖的存儲(chǔ)結(jié)構(gòu)，為了使生成樹(shù)的根節(jié)點(diǎn)為第一個(gè)讀入的頂點(diǎn)，在 創(chuàng)建樹(shù)的存儲(chǔ)結(jié)構(gòu)中同樣使用從同一個(gè)文件屮讀入各頂點(diǎn)建立定點(diǎn)數(shù)組。2.4輸出孩子鏈表結(jié)構(gòu)說(shuō)明由孩了鏈表存儲(chǔ)結(jié)構(gòu)的輸出要清楚地顯示圖的存儲(chǔ)結(jié)構(gòu)則需要將圖的孩了鏈表輸出。和圖的鄰接表結(jié)構(gòu)輸出類(lèi)似，故采用同樣的方法輸出孩子鏈表。3詳細(xì)設(shè)計(jì)3.1鄰接矩陣的定義和孩子鏈表表示法定義要想創(chuàng)建圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)和生成樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)，必須先進(jìn)行和關(guān)的定 義。鄰接矩陣和孩了鏈表表示法定義代碼如下：typedefs

5、tructarccellintadj;char *info;arccell,adjmatrix2020;typedefstructchar vexsmaxsize;adjmatrix arcs;in tvex nu m,arc num;jagraph;樹(shù)的孩子鏈表表示法定義權(quán)值指向該邊相關(guān)信息的指針描述頂點(diǎn)的數(shù)組鄰接矩陣圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)typedefstructctnodeint child;結(jié)點(diǎn)的編號(hào)structctnode *next; 指針域，指向下一個(gè)孩子結(jié)點(diǎn) *childptr;typedefstructchar data;childptrfirstchild; ctbox;ty

6、pedefstruct結(jié)點(diǎn)的信息指向孩子鏈表的首個(gè)表結(jié)點(diǎn)樹(shù)結(jié)構(gòu)ctbox nodesmaxsize;頭結(jié)點(diǎn)數(shù)組int n;樹(shù)的總結(jié)點(diǎn)數(shù)和樹(shù)根 ctree;3.1從文件中讀入無(wú)向圖的結(jié)點(diǎn)和邊的信息并創(chuàng)建無(wú)向圖為了節(jié)省調(diào)試時(shí)間，以及方便調(diào)試工作，木代碼采用了從文件中讀取無(wú)向圖的頂點(diǎn)和 邊的信息的方法，采用鄰接矩陣存儲(chǔ)圖的方法創(chuàng)建無(wú)向圖。無(wú)向圖結(jié)點(diǎn)和邊信息g.dat文件如下圖3-1所示：圖3t g. dat文件讀入文件構(gòu)建無(wú)向圖的結(jié)果如下圖3-2所示：八rir圖3-2創(chuàng)建圖 實(shí)現(xiàn)以上操作的實(shí)現(xiàn)代碼如下：6 0 7 5 68114511 bcedcfcf amanbbbeedp：我的文欄2專(zhuān)業(yè)課c &

7、amp;c _ 辭結(jié)構(gòu)數(shù)搖結(jié)也朗i漳三次設(shè)計(jì) ah .圖生成樹(shù)（無(wú)向圖）1創(chuàng)建圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)2 輸出圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)3 深度優(yōu)先遍歷斗創(chuàng)建樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)5 輸出樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)6 生成樹(shù)的定義了 清屏 退出程序請(qǐng)輸入菜單項(xiàng)：1請(qǐng)輸入圖中頂點(diǎn)的個(gè)數(shù)和邊數(shù)：6 9 請(qǐng)輸入圖中6個(gè)頂點(diǎn)的標(biāo)志： 圖中的6個(gè)頂點(diǎn)依次為：f c b d a e 請(qǐng)輸入第1條?。?請(qǐng)輸入第2條弧： 請(qǐng)輸入第3條?。?請(qǐng)輸入第坤條?。?請(qǐng)輸入第5條?。?請(qǐng)輸入第6條?。?請(qǐng)輸入第了條?。?請(qǐng)輸入第8條弧：請(qǐng)輸入第9條?。篸,c,14 圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)創(chuàng)建成功！void creatagraph(agra

8、ph&g)char vlzv2,vex;intijw,k;file *fp;if(null=(fp=fopen(,g.dat,/ “)/打開(kāi)存儲(chǔ)圖結(jié)點(diǎn)和邊信息的文件printf（“圖的存儲(chǔ)文件打開(kāi)失敗，請(qǐng)檢查文件g.dat是否存在！ ”）; exit（-l）;printf(“請(qǐng)輸入圖中頂點(diǎn)的個(gè)數(shù)和邊數(shù):“);fscanf(fp, "%d%d", &g.vexnum, &g.arcnum);printf("%d %dh, g.vexnum, g.arcnum);printf("n請(qǐng)輸入圖中d個(gè)頂點(diǎn)的標(biāo)志:n”, g.vexnum);

9、for(i=0; i<g.vexnum; i+)vex=fgetc(fp);while(!isalpha(vex)vex=fgetc(fp);g.vexsi =vex;printf(n圖中的d個(gè)頂點(diǎn)依次為:叭g.vexnum);for(i=0; i<g.vexnum; i+)printf(,%2c,/ g.vexsi);for(i=0;i<g.vexnum;+i)for(j=0;j<g.vex nu m;+j)g.arcsij.adj=int_max;/將鄰接矩陣所有元素賦值g.=null;for(k=0;k<g.arc num;k+)get

10、c(fp);/讀取文件中的字符fflush(stdin);printf(mn 請(qǐng)輸入第(1 條弧:n,k+l);fscanf(fp, “c,%c,%d： &vl,&v2,&w); /輸入一條邊依附的兩點(diǎn)及權(quán)值 printf("%c/%c/%d,/ vl,v2,w);i=localvex(g,vl);確定頂點(diǎn)vi和v2在圖中的位置j=localvex(g,v2);g.arcsij.adj二w;將權(quán)值賦給相應(yīng)的邊g.arcsji.adj=w;fclose(fp);關(guān)閉文件32輸出圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)為了驗(yàn)證該圖的是否創(chuàng)建成功，可以輸出該圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)。圖屮0

11、代表兩頂 點(diǎn)之間沒(méi)有邊，其余數(shù)字為兩頂點(diǎn)之間邊的權(quán)值，輸出鄰接矩陣只需一個(gè)兩層for()循環(huán)即 可。輸出該圖的鄰接矩陣結(jié)果如圖3-3所示：id:我的文欄2專(zhuān)業(yè)課結(jié)構(gòu)數(shù)搞結(jié)呦實(shí)illlv回|請(qǐng)輸入菜單項(xiàng)：20001505004148170010g16151000008600051716000彳rrr圖3-3圖的鄰接矩陣 實(shí)現(xiàn)該輸出圖飛鄰接矩陣的代碼如下： void ijjzprint(agraph g)intij;for(i=0;i<g.vex nu m;+i)for(j=0;j<g.vex num;+j)printf("%6d",g.arcsij.adj); p

12、rintf(hn");3. 3 深度優(yōu)先遍歷要想實(shí)現(xiàn)圖生成樹(shù)的目的，必須通過(guò)某種方法遍歷所有頂點(diǎn)然后記錄其路徑，本程序 采用深度優(yōu)先遍歷（dfs）的方法實(shí)現(xiàn)生成樹(shù)。程序小定義了外部變量，目的是記錄遍歷 該圖的遍歷路徑，通過(guò)這些頂點(diǎn)記錄來(lái)創(chuàng)建樹(shù)的存儲(chǔ)結(jié)構(gòu)。深度優(yōu)先遍歷的結(jié)果如下圖34所示：實(shí)現(xiàn)深度優(yōu)先遍歷的代碼如下:void dfs_matrix(agraphg,intkzint visited)intj;visitedk=l;printfcscg.vexsfk);輸出遍歷的路徑for(j=0;j<g.vex nu m;j+)if(g.arcskj.adj!=o)&&am

13、p;o=visitedj)am=k;記錄遍歷頂點(diǎn)位置m+;bt=j;記錄遍歷頂點(diǎn)位置t+；dfs_matrix(g,j,visited);void dfstra_matrix(agraph g)int k;int visitedmaxsize=0;設(shè)置頂點(diǎn)標(biāo)記m=0;t=0;for(k=0;k<g.vex nu m;k+)if(visitedk=o) 若編號(hào)為k的頂點(diǎn)未被訪問(wèn)過(guò)，則以該頂點(diǎn)為出發(fā)頂點(diǎn)dfs_matrix(g,k,visited);3. 4創(chuàng)建樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)通過(guò)圖的深度優(yōu)先遍歷生成了和應(yīng)的樹(shù),由于采用外部變量記錄了遍歷各頂點(diǎn)的先后順序，即通過(guò)兩個(gè)數(shù)組分別存放了除最后一

14、個(gè)頂點(diǎn)外的所有頂點(diǎn)編號(hào)以及除第一個(gè)頂點(diǎn)外的所有頂點(diǎn)編號(hào)。創(chuàng)建該樹(shù)同樣采用讀取文件的方式，由于創(chuàng)建圖的存儲(chǔ)結(jié)構(gòu)時(shí)，就對(duì)所 有頂點(diǎn)進(jìn)行了編號(hào)，第一個(gè)讀入的頂點(diǎn)就是生成樹(shù)的根節(jié)點(diǎn)，因此，創(chuàng)建該樹(shù)同樣讀取了 g.dat屮的頂點(diǎn)信息，將讀入的頂點(diǎn)信息放入一個(gè)數(shù)組屮，然后，將外部變量記錄的頂點(diǎn)編 號(hào)插入到數(shù)組（和鄰接表的構(gòu)造方法類(lèi)似）就創(chuàng)建了孩子鏈表存儲(chǔ)結(jié)構(gòu)。創(chuàng)建樹(shù)的存儲(chǔ)結(jié)構(gòu)如圖3-5所示:d:我的文欄2專(zhuān)業(yè)諜c &c數(shù)有結(jié)構(gòu)數(shù)揭結(jié)構(gòu)實(shí)請(qǐng)輸入菜單項(xiàng)：4請(qǐng)輸入圖中頂點(diǎn)的個(gè)數(shù)圖中的6頂點(diǎn)依次為：f c b d a e樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)創(chuàng)建成功！nr圖3-5創(chuàng)建樹(shù)的存儲(chǔ)結(jié)構(gòu) 樹(shù)的孩子鏈表存儲(chǔ)實(shí)現(xiàn)代碼如

15、下：void creat_tree(ctree&t)inti;char vex;childptr p;file *fp;if(null=(fp=fopen(,g.dat", "r") printfc*樹(shù)的存儲(chǔ)文件打開(kāi)失敗，請(qǐng)檢杳文件g.dat是否存在！“); exit(-l);printf(”請(qǐng)輸入圖中頂點(diǎn)的個(gè)數(shù):”);fscanf(fpz "%d", &t.n);printf("%dn, t.n);for(i=0; ivt.n; i+)vex=fgetc(fp);while(!isalpha(vex)vex=fget

16、c(fp);t.no desi.data=vex;t.n odesi.firstchild=null;printf(u圖中的d頂點(diǎn)依次為:nt.n);for(i=0; i<t.n; i+)printf("%3c",t. nodesi.data);for(m=0,t=0;m<6&&t<5;m+,t+) p = (childptr)malloc (sizeof(childptr);p->child =bt;p->next=null;p->n ext=t. no desam.firstchild;t.no desam.first

17、child=p;fclose(fp);3. 5輸出樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)為了能清楚的知道該樹(shù)的結(jié)構(gòu)，所以需要輸出牛成樹(shù)的存儲(chǔ)結(jié)構(gòu)，輸出孩子鏈表存儲(chǔ) 結(jié)構(gòu)和輸出圖的鄰接表存儲(chǔ)結(jié)構(gòu)類(lèi)似。樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)如圖3-6所示：»p：馳如2專(zhuān)業(yè)諜c&c一笑結(jié)構(gòu)數(shù)強(qiáng)訥劇m三次i g 回請(qǐng)輸入菜單項(xiàng)，5孩于鏈表中的數(shù)蠶爲(wèi)（頂點(diǎn)下標(biāo)邊的權(quán)值指針）下標(biāo)頂點(diǎn) aana-4 anr圖3-6輸出樹(shù)的孩子鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)輸出樹(shù)的孩了鏈表存儲(chǔ)結(jié)構(gòu)的代碼如下：void outctree(ctree t)inti;childptr p;printf("n孩了鏈表中的數(shù)據(jù)如下：nh);printf(&

18、quot;%3s %s鏈表結(jié)點(diǎn)(頂點(diǎn)下標(biāo)邊的權(quán)值指針)n”,“下標(biāo)蔦”頂點(diǎn)”);for(i=0; i<t.n; i+)printf("%3d | %c", i, t.nodesi.data);p = t.no desi.firstchild;while(p)printf(n %d"z p->child);p = p>next;printfc* ann);4遇到的問(wèn)題與解決方案在編寫(xiě)代碼時(shí)遇到的一些問(wèn)題及各個(gè)問(wèn)題的解決方案如下：（1）在創(chuàng)建圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)時(shí)，無(wú)法從文件中讀取字符？解決：未從文件屮讀入頂點(diǎn)的數(shù)，在文件屮添加頂點(diǎn)數(shù)，然后讀取即可。

19、（2）怎樣將遍歷的頂點(diǎn)編號(hào)記錄下來(lái)，？解決：記錄遍歷路徑并且要利用此記錄創(chuàng)建樹(shù)的存儲(chǔ)結(jié)構(gòu)，則設(shè)置全局變量，存儲(chǔ)遍 歷圖時(shí)經(jīng)過(guò)的各頂點(diǎn)的編號(hào)。（3）怎樣讓生成樹(shù)的根節(jié)點(diǎn)為圖遍歷的第一個(gè)節(jié)點(diǎn)？解決：由于圖的各頂點(diǎn)的信息存在文件屮，同樣的，可以從該文件中讀取各頂點(diǎn)，則 建立的孩子鏈表即為以第一個(gè)圖遍歷的頂點(diǎn)為根節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)。（4）怎樣利用記錄的頂點(diǎn)編號(hào)創(chuàng)建樹(shù)的存儲(chǔ)結(jié)構(gòu)？解決：因?yàn)橛涗浀捻旤c(diǎn)編號(hào)存儲(chǔ)在全局變量中，血沮在創(chuàng)建孩子鏈表存儲(chǔ)結(jié)構(gòu)時(shí)已經(jīng) 從文件中讀取定點(diǎn)數(shù)組，故根據(jù)全局變量帶冋的頂點(diǎn)編號(hào)記錄，即可創(chuàng)建孩了鏈表（類(lèi) 似于鄰接表的創(chuàng)建）。（4）怎樣將樹(shù)的存儲(chǔ)結(jié)構(gòu)輸出？解決：由于孩子鏈表創(chuàng)建過(guò)程類(lèi)似于圖的鄰接表創(chuàng)建，故在輸出過(guò)程中也具有很多的 相似性，故可以根據(jù)圖的鄰接表輸出方法輸出樹(shù)的孩了鏈表存儲(chǔ)結(jié)構(gòu)。小結(jié)這次課程設(shè)計(jì)，感受頗多，選好題目后我就開(kāi)始了自己的課設(shè)之旅，一開(kāi)始沒(méi)有什么 思緒，由于對(duì)圖和樹(shù)的知識(shí)掌握的不夠全面