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

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

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

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

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

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

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

7、pe data; arcnode *firstarc; vnode,adjlistmac_vertex_num;typedef structadjlist vertices;int vexnum,arcnum; int kind; graph;第3章 系統(tǒng)詳細(xì)設(shè)計(jì)與編碼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

8、 arctextype inttypedef 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_nu

9、m; int greatvex(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(請(qǐng)輸入頂

10、點(diǎn)數(shù)：);scanf(%d,&g-vexnum);while(g-vexnummac_vertex_num)printf(定點(diǎn)數(shù)最大為10！n);printf(請(qǐng)重新輸入：);scanf(%d,&g-vexnum);printf(請(qǐng)輸入邊數(shù)：);scanf(%d,&g-arcnum);printf(輸入各頂點(diǎn)的值：);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;a

11、rcnode *d1,*d2;for(i=0;iarcnum;i+)printf(請(qǐng)輸入第%d個(gè)相連的兩個(gè)頂點(diǎn)，格式：頂點(diǎn)1 頂點(diǎn)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-adj

12、vex=start;d2-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(請(qǐng)輸入第%d個(gè)相連的兩個(gè)頂點(diǎn)，格式：頂點(diǎn)1頂點(diǎn)2：（中間用逗號(hào)隔開）,i+1);scanf(%s%s,b,e);start=adjfound(*g,b);end=adjfound(*g,e);d1=(arcnode *)malloc(sizeof(arc

13、node);d1-adjvex=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(請(qǐng)輸入第%d個(gè)相連的兩個(gè)頂點(diǎn)，格式：頂點(diǎn)1 權(quán)值 頂點(diǎn)2（中間用空格隔開）：,i+1);scanf(%s%d%s,b,&(d1-info),

14、e);start=adjfound(*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;a

15、rcnode *d1;for(i=0;iarcnum;i+)d1=(arcnode *)malloc(sizeof(arcnode); printf(請(qǐng)輸入第%d個(gè)相連的兩個(gè)頂點(diǎn)，格式：頂點(diǎn)1 權(quán)值 頂點(diǎn)2（中間用逗號(hào)隔開）：,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

16、=0;while(g.verticesi.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

17、(g,w);return 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)-adj

18、vex;elsereturn -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)

19、 queueb=w,b+;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 請(qǐng)選擇要建立的圖的類型:); scanf(%d,&(g-kind);switch(g-kind) case 1:greatvex(g);greatdg(g);break;case 2:greatvex(g);greatdn(g);

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

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

22、nt n)int i,j;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

23、); q-left=bk1;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)路徑長(zhǎng)度的，fbt是對(duì)哈夫曼樹逐個(gè)訪問的指針，len是當(dāng)前結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度，每次調(diào)用elemtype weightpathlength函數(shù)，len加1。由于遞歸調(diào)用，當(dāng)fbt為空樹時(shí)，返回，從而求出帶權(quán)路徑長(zhǎng)度。第5章 總結(jié)轉(zhuǎn)眼，為期兩周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)學(xué)習(xí)即