數(shù)據(jù)結(jié)構(gòu)課程設(shè)計圖的建立與遍歷_第1頁
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計圖的建立與遍歷_第2頁
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計圖的建立與遍歷_第3頁
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計圖的建立與遍歷_第4頁
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計圖的建立與遍歷_第5頁
已閱讀5頁,還剩17頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

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è)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論