數(shù)據(jù)結(jié)構(gòu)課程設(shè)計圖的建立與遍歷

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(論文)圖的建立與遍歷 院（系）名稱電子與信息工程學(xué)院 專業(yè)班級物聯(lián)網(wǎng)141 學(xué)號 學(xué)生姓名 指導(dǎo)教師 起 止 時 間： 2016.1.42016.1.15課程設(shè)計（論文）任務(wù)及評語院（系）：電子與信息工程學(xué)院 教研室：軟件工程學(xué) 號學(xué)生姓名專業(yè)班級物聯(lián)網(wǎng)141 課程設(shè)計（論文）題目圖的建立與遍歷課程設(shè)計（論文）任務(wù)任務(wù)要求：圖的建立與遍歷實現(xiàn)以下幾個功能：（1）創(chuàng)建圖的存儲結(jié)構(gòu)并保存；（2）對圖進行廣度優(yōu)先搜索（3）對圖進行深度優(yōu)先搜索。（4）輸出遍歷結(jié)果。技術(shù)要求：1、數(shù)據(jù)的邏輯結(jié)構(gòu)采用圖狀結(jié)構(gòu)，物理結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)（鄰接表）。2、軟件能正常運行，界面清晰，操作要簡單。

2、3、系統(tǒng)要有主界面設(shè)計，調(diào)用各個功能項。4、采用viscal c+編寫代碼，可讀性強。5、數(shù)據(jù)類型用typedef 定義。指導(dǎo)教師評語及成績平時成績： 答辯成績： 論文成績： 總成績： 指導(dǎo)教師簽字： 年 月 日注：平時成績占20%，答辯成績占40%，論文成績占40%。摘 要隨著信息時代的快速發(fā)展，大數(shù)據(jù)大流量對數(shù)據(jù)的存儲有了更為苛刻的要求，數(shù)據(jù)之間的關(guān)系越來越復(fù)雜。圖形結(jié)構(gòu)的存儲方式也就應(yīng)運而生，因為圖節(jié)點之間的關(guān)系可能是任意的，圖中任意2個元素之間都可能相關(guān)。由此，圖的應(yīng)用更為廣泛，特別是今年來的迅速發(fā)展，已滲透到諸如語言學(xué)、邏輯學(xué)、物理學(xué)化學(xué)、電訊工程、計算機科學(xué)以及數(shù)學(xué)的其他分支中。在

3、此課程設(shè)計中，程序設(shè)計語言采用visual c+window 7環(huán)境。在程序設(shè)計中主要解決的是給出一個圖如何用多中方法完成圖的遍歷的問題，也包括如何創(chuàng)建一個圖，深度優(yōu)先遍歷和廣度優(yōu)先遍歷一個圖。程序最終通過調(diào)試運行，初步實現(xiàn)了設(shè)計目標(biāo)。關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；有向圖；無向圖；鄰接表目 錄第1章 緒論11.1系統(tǒng)的開發(fā)背景11.2開發(fā)工具及語言1第2章 概要設(shè)計22.1模塊劃分22.2 各模塊的設(shè)計22.3 數(shù)據(jù)結(jié)構(gòu)的選擇3第3章 系統(tǒng)詳細(xì)設(shè)計與編碼53.1完整的源程序53.2程序的輸入和輸出113.3調(diào)試程序中遇到的問題及解決方案12第4章 思考題解析134.1 思考題的選擇134.2類c算法134

4、.3程序分析14第5章 總結(jié)15參考文獻(xiàn)16第1章 緒論1.1系統(tǒng)的開發(fā)背景圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前去和一個和直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間沒有明顯的層次關(guān)系，并且每一層的數(shù)據(jù)元素可能和下一層中的多個元素相關(guān)，但是你只能和上一層的一個元素相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點之間的關(guān)系可能是任意的，圖中任意2個元素之間都可能相關(guān)。由此，圖的應(yīng)用更為廣泛，特別是今年來的迅速發(fā)展，已滲透到諸如語言學(xué)、邏輯學(xué)、物理學(xué)、化學(xué)、電訊工程、計算機科學(xué)以及數(shù)學(xué)的其他分支中。1.2開發(fā)工具及語言本系統(tǒng)使用viscal c+語言開發(fā)，主界

5、面清晰顯示所有功能項，使用簡單。各個功能項均定義一個函數(shù)來實現(xiàn)，在主函數(shù)中調(diào)用各個子函數(shù)實現(xiàn)不同的功能。第2章 概要設(shè)計2.1模塊劃分題目應(yīng)實現(xiàn)的具體功能：按照自己的需要從有向向圖不帶權(quán)圖、有向帶權(quán)圖、無向不帶權(quán)圖和有向帶權(quán)圖中選擇建立一種圖的結(jié)構(gòu)，輸入具體的頂點數(shù)目、頂點值、邊的數(shù)目和權(quán)值，選擇要開始遍歷的頂點，并按照深度優(yōu)先遍歷和廣度優(yōu)先遍歷輸出該圖。系統(tǒng)的功能模塊圖如圖2.1所示。圖2.1 系統(tǒng)功能模塊圖2.2 各模塊的設(shè)計 題目應(yīng)該實現(xiàn)的具體功能： a.有向不帶權(quán)圖的建立，從任意節(jié)點開始廣度和深度遍歷 b.有向不帶權(quán)圖的建立，從任意節(jié)點開始廣度和深度遍歷 c.有向不帶權(quán)圖的建立，從任意

6、節(jié)點開始廣度和深度遍歷 d.有向不帶權(quán)圖的建立，從任意節(jié)點開始廣度和深度遍歷 開始 出隊訪問訪問標(biāo)志數(shù)組初始化尋找第一個鄰接點 第一個定點入隊 是否訪問過隊列是否為空 否 是 否 定點入隊 結(jié)束 尋找下一個鄰接點 是圖2.2 廣度遍歷模塊程序流程圖2.3 數(shù)據(jù)結(jié)構(gòu)的選擇系統(tǒng)數(shù)據(jù)的邏輯結(jié)構(gòu)采用圖狀結(jié)構(gòu)，物理結(jié)構(gòu)采用鄰接表的存儲結(jié)構(gòu)。存儲結(jié)構(gòu)定義如下：typedef struct arcnodeint adjvex; struct arcnode *nextarc; arctextype info; arcnode;typedef struct vnodevertextype data; arcn

7、ode *firstarc; vnode,adjlistmac_vertex_num;typedef structadjlist vertices;int vexnum,arcnum; int kind; graph;第3章 系統(tǒng)詳細(xì)設(shè)計與編碼3.1完整的源程序#include stdafx.h#include #include #define mac_vertex_num 10#define null 0#define true 1#define false 0#define overflow -2#define ok 1#define error 0#define arctextype i

8、nttypedef struct arcnodeint adjvex; struct arcnode *nextarc; arctextype info; arcnode;typedef char vertextype5;typedef struct vnodevertextype data; arcnode *firstarc; vnode,adjlistmac_vertex_num; typedef structadjlist vertices; int vexnum,arcnum; int kind; graph;int visitedmac_vertex_num; int greatv

9、ex(graph *g); int print(graph g); int adjfound(graph g,vertextype c); int dfs(graph g,int v); int bfstraverse(graph g,vertextype vex); int dfstraverse(graph g,vertextype vex); int firstadjvex(graph g,int v); int nextadjvex(graph g,int v,int w); int greatvex(graph *g) int i=0;printf(請輸入頂點數(shù)：);scanf(%d

10、,&g-vexnum);while(g-vexnummac_vertex_num)printf(定點數(shù)最大為10！n);printf(請重新輸入：);scanf(%d,&g-vexnum);printf(請輸入邊數(shù)：);scanf(%d,&g-arcnum);printf(輸入各頂點的值：);for(i=0;ivexnum;i+) scanf(%s,g-verticesi.data);g-verticesi.firstarc=null;return ok;int greatudg(graph *g) int i=0,start,end;vertextype b,e;arcnode *d1,*d

11、2;for(i=0;iarcnum;i+)printf(請輸入第%d個相連的兩個頂點，格式：頂點1 頂點2（中間用空格隔開）：,i+1);scanf(%s%s,b,e);start=adjfound(*g,b); end=adjfound(*g,e); d1=(arcnode *)malloc(sizeof(arcnode); d1-adjvex=end;d1-nextarc=g-verticesstart.firstarc;g-verticesstart.firstarc=d1;d2=(arcnode *)malloc(sizeof(arcnode); d2-adjvex=start;d2-

12、nextarc=g-verticesend.firstarc;g-verticesend.firstarc=d2;return ok;int greatdg(graph *g) int i=0,start,end;vertextype b,e;arcnode *d1;for(i=0;iarcnum;i+)printf(請輸入第%d個相連的兩個頂點，格式：頂點1頂點2：（中間用逗號隔開）,i+1);scanf(%s%s,b,e);start=adjfound(*g,b);end=adjfound(*g,e);d1=(arcnode *)malloc(sizeof(arcnode);d1-adjv

13、ex=end;d1-nextarc=g-verticesstart.firstarc;g-verticesstart.firstarc=d1;return ok;int greatudn(graph *g) int i=0,start,end;vertextype b,e;arcnode *d1,*d2;for(i=0;iarcnum;i+)d1=(arcnode *)malloc(sizeof(arcnode); printf(請輸入第%d個相連的兩個頂點，格式：頂點1 權(quán)值 頂點2（中間用空格隔開）：,i+1);scanf(%s%d%s,b,&(d1-info),e);start=adjf

14、ound(*g,b);end=adjfound(*g,e);d1-adjvex=end;d1-nextarc=g-verticesstart.firstarc;g-verticesstart.firstarc=d1;d2=(arcnode *)malloc(sizeof(arcnode);d2-adjvex=start;d2-nextarc=g-verticesend.firstarc;g-verticesend.firstarc=d2;return ok;int greatdn(graph *g) int i=0,start,end;vertextype b,e;arcnode *d1;fo

15、r(i=0;iarcnum;i+)d1=(arcnode *)malloc(sizeof(arcnode); printf(請輸入第%d個相連的兩個頂點，格式：頂點1 權(quán)值 頂點2（中間用逗號隔開）：,i+1);scanf(%s%d%s,b,&(d1-info),e);start=adjfound(*g,b);end=adjfound(*g,e);d1-adjvex=end;d1-nextarc=g-verticesstart.firstarc;g-verticesstart.firstarc=d1;return ok;int print(graph g) int i=0;while(g.ve

16、rticesi.data!=null&ig.vexnum)printf(%s,g.verticesi.data);i+;return ok;int adjfound(graph g,vertextype c) int i=0;while(strcmp(g.verticesi.data,c)!=0&ig.vexnum)i+;if(i,g.verticesv.data);visitedv=true; if(g.verticesv.firstarc) for(w=firstadjvex(g,v);w=0;w=nextadjvex(g,v,w)if(!visitedw)dfs(g,w);return

17、ok;int dfstraverse(graph g,vertextype vex) /深度遍歷int v,i;i=adjfound(g,vex); for(v=0;vadjvex;return -1;int nextadjvex(graph g,int v,int w) /廣度遍歷調(diào)用的查找下一條邊arcnode *p; p=(arcnode *)malloc(sizeof(arcnode);p=g.verticesv.firstarc;while(p-adjvex!=w)p=p-nextarc;if(p-nextarc)return (p-nextarc)-adjvex;elseretur

18、n -1;int bfstraverse(graph g,vertextype vex) 廣度遍歷int a=0,b=0; int *queue;int v,i,w;i=adjfound(g,vex); queue=(int *)malloc(g.vexnum*2)*sizeof(int);queueb=i,b+; for(v=0;v,g.verticesqueuea.data);visitedqueuea=true; for(w=firstadjvex(g,queuea);w=0;w=nextadjvex(g,queuea,w)if(w!=-1&!visitedw) queueb=w,b+;

19、a+; return ok;void main()graph *g=null;vertextype n;int again=1;g=(graph *)malloc(sizeof(graph);while(1)printf( 圖的建立與遍歷 n n); printf( 1:有向不帶權(quán)圖n 2:有向帶權(quán)圖n 3:無向不帶權(quán)圖n 4:無向帶權(quán)圖n 請選擇要建立的圖的類型:); scanf(%d,&(g-kind);switch(g-kind) case 1:greatvex(g);greatdg(g);break;case 2:greatvex(g);greatdn(g);break; case 3

20、:greatvex(g);greatudg(g);break; case 4:greatvex(g);greatudn(g);break; default:printf(輸入錯誤，請重新輸入: n); printf(該圖的所有頂點：);print(*g);printf(n請輸入從哪個頂點開始遍歷：);while(again!=0)scanf(%s,n);printf(深度優(yōu)先遍歷為：);dfstraverse(*g,n);printf(n廣度優(yōu)先遍歷為：);bfstraverse(*g,n);printf(n從其他頂點開始遍歷請輸入頂點值，退出請輸入0：);scanf(%d,&again);f

21、ree(g); 3.2程序的輸入和輸出程序運行主界面：圖3.1 主界面圖3.2 圖的建立 圖3.3廣度遍歷和深度遍歷3.3調(diào)試程序中遇到的問題及解決方案 問題：圖的鄰接表廣度遍歷是只能顯示第一個鄰接點。 解決方案：后來經(jīng)過大量排查發(fā)現(xiàn)在節(jié)點入隊是吧v寫成v0了，雖然都是很小的錯誤，但是充分暴露了自己的粗心大意，在以后的試驗中一低昂要改正。第4章 思考題解析4.1 思考題的選擇所選擇的思考題：數(shù)組a中有n個值，根據(jù)其編寫一個算法，構(gòu)造一棵哈夫曼樹，并求出其帶權(quán)路徑長度。4.2類c算法struct btreenode *createhuffman(elemtype a,int n)int i,j;

22、struct btreenode *b,*q;b=malloc(n*sizeof(struct btreenode);for(i=0;idata=ai;bi-left=bi-right=null;for(i=1;in;i+) int k1=-1;k2; /k1for(j=0;jn;j+) if(bj!=null&k1=-1)k1=j;continue;if(bj!=null)k2=j;break;for(j=k2;jdatadata)k2=k1;k1=j;else if(bj-datadata)k2=j;q=malloc(sizeof(struct btreenode); q-left=bk1

23、;q-right=bk2;free(q);elemtype weightpathlength(struct btreenode *fbt,int len) if(fbt=null) return 0;elseif(fbt-left=null&fbt=null) return fbt-data*len;else return weightpathlength(fbt-left,len+1)+weighpathlength(fbt-right,len+1);4.3程序分析elemtype weightpathlength函數(shù)是求哈夫曼樹的帶權(quán)路徑長度的，fbt是對哈夫曼樹逐個訪問的指針，len是當(dāng)前結(jié)點到根結(jié)點的路徑長度，每次調(diào)用elemtype weightpathlength函數(shù)，len加1。由于遞歸調(diào)用，當(dāng)fbt為空樹時，返回，從而求出帶權(quán)路徑長度。第5章 總結(jié)轉(zhuǎn)眼，為期兩周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)