圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)建立

1、課程名稱: 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目:圖的鄰接矩陣存儲(chǔ) 結(jié)構(gòu)建立姓名:XXX院系:計(jì)算機(jī)學(xué)院專業(yè):計(jì)算機(jī)科學(xué)技術(shù) 年級(jí):11級(jí)學(xué)號(hào):XXXXXXXX指導(dǎo)教師:XXX2013年9月28日目錄1 課程設(shè)計(jì)的目的32需求分析33 課程設(shè)計(jì)報(bào)告內(nèi)容 3 3.1 概要設(shè)計(jì)3 3.2 詳細(xì)設(shè)計(jì)4 3.3 調(diào)試分析5 3.4 用戶手冊(cè)5 3.5 程序清單5 3.6 測(cè)試結(jié)果104 小結(jié)125 參考文獻(xiàn)121.課程設(shè)計(jì)的目的(1) 熟練使用 C 語言編寫程序，解決實(shí)際問題;(2) 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力;(3) 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、

2、測(cè)試等基本方法和技能;(4) 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力;2.需求分析 問題描述:建立圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)(圖的類型可以是有向圖或有向網(wǎng)、無向圖或無向網(wǎng)，學(xué)生可以任選一種類型)，能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后給出圖的 DFS,BFS次序。要求：先任意創(chuàng)建一個(gè)圖；圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)。3.課程設(shè)計(jì)報(bào)告內(nèi)容3.1概要設(shè)計(jì) 1.函數(shù)主函數(shù)：main( )創(chuàng)建無向圖：CreateGraph( )深度優(yōu)先遍歷圖：DFS( )廣度優(yōu)先遍歷圖：BFS( )3.2詳細(xì)設(shè)計(jì)1.使用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，程序中主要用到的抽

3、象數(shù)據(jù)類型：typedef struct char vexsMAX; /頂點(diǎn)向量 int arcsMAXMAX; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) Graph;2.程序流程圖：主函數(shù)main( )創(chuàng)建無向圖數(shù)據(jù)輸入功能選擇深度優(yōu)先遍歷退出程序廣度優(yōu)先遍歷數(shù)據(jù)輸出程序結(jié)束數(shù)據(jù)輸出3.3調(diào)試分析程序的設(shè)計(jì)嚴(yán)格遵循結(jié)構(gòu)化的程序設(shè)計(jì)思想，由簡(jiǎn)單到復(fù)雜，注意規(guī)范。在此次程序運(yùn)行中，出現(xiàn)了很多的錯(cuò)誤，開始的時(shí)候，不能很好的創(chuàng)建一個(gè)圖，后來改進(jìn)了算法，使得程序能夠正確的運(yùn)行。3.4用戶手冊(cè)進(jìn)入程序后，您會(huì)看到以下提示：“無向圖的創(chuàng)建及DFS和BFS的遞歸和非遞歸實(shí)現(xiàn)!

4、”1.“創(chuàng)建無向圖!”；2.“圖的深度優(yōu)先遍歷!”；3.“圖的廣度優(yōu)先遍歷!”；4.“退出!”；請(qǐng)選擇相應(yīng)的數(shù)字鍵實(shí)現(xiàn)相應(yīng)的功能。在執(zhí)行圖的遍歷前必須先創(chuàng)建圖，創(chuàng)建圖時(shí)，按照系統(tǒng)的提示進(jìn)行操作即可。3.5程序清單#include<stdio.h>#include<malloc.h>#define MAX 20int visitedMAX; /訪問標(biāo)志數(shù)組typedef struct char vexsMAX; /頂點(diǎn)向量int arcsMAXMAX; /鄰接矩陣int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)Graph;typedef struct Qnod

5、eint data;struct Qnode *next;Qnode,*Queueptr;typedef structQueueptr front;Queueptr rear; Linkqueue;void InitQueue(Linkqueue &Q)Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode);if(Q.front)Q.front->next=NULL;void EnQueue(Linkqueue &Q,int e) Queueptr p;p=(Queueptr)malloc(sizeof(Qnode);if(p)p-&g

6、t;data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;int DeQueue(Linkqueue &Q)int e;Queueptr p;if(Q.rear!=Q.front)p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear=p)Q.rear=Q.front; free(p);if(Q.front=p)Q.rear=Q.front;return e;int Locatevex(Graph G,char v) /返回元素v的位置 int i;f

7、or(i=0;i<G.vexnum;i+) if(G.vexsi=v)return i; return -1; void CreateGraph(Graph &G)/創(chuàng)建無向圖的鄰接矩陣 int i,j,w,m,n; char a,b,c; printf("請(qǐng)輸入圖G的頂點(diǎn)數(shù)和弧數(shù):"); scanf("%d%d",&G.vexnum,&G.arcnum); getchar(); for(i=0;i<G.vexnum;i+) visitedi=0;for(i=0;i<G.vexnum;i+)printf(&quo

8、t;請(qǐng)輸入第%d個(gè)頂點(diǎn)信息:",i+1); scanf("%c",&G.vexsi); getchar(); for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsij=0; for(i=0;i<G.arcnum;i+) printf("請(qǐng)輸入第%d條弧依附的兩個(gè)頂點(diǎn)及權(quán)值: ",i+1); scanf("%c %c %d%c",&a,&b,&w,&c); m=Locatevex(G,a); n=Locatevex(G

9、,b); G.arcsmn=w;G.arcsnm=w; void PrintMatrix(Graph G) /輸出鄰接矩陣int i,j;printf("n由圖G生成的鄰接矩陣如下:n");for(i=0;i<G.vexnum;+i)for(j=0;j<G.vexnum;+j)printf("%-2d",G.arcsij);printf("n");int FirstAdiVex(Graph G,int v)/圖G中頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn) int i;if(v>=0&&v<G.vexnum) fo

10、r(i=0;i<G.vexnum;i+) if(G.arcsvi!=0) return i; return -1; int NextAdVex(Graph G,int i,int j) /圖G中頂點(diǎn)i的第j個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)int k;if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum) for(k=j+1;k<G.vexnum;k+) if(G.arcsik!=0) return k; return -1; void DFS(Graph G,int v) /從第v個(gè)頂點(diǎn)出發(fā)深度

11、遞歸遍歷圖 int u;printf("%2c",G.vexsv);visitedv=1;u=FirstAdiVex(G,v);while(u>=0)if(!visitedu)DFS(G,u); u=NextAdVex(G,v,u);void BFS(Graph G)/廣度非遞歸遍歷 int i,w,k; Linkqueue Q; InitQueue(Q);for(i=0;i<MAX;i+) visitedi=0; for(i=0;i<G.vexnum;i+) if(!visitedi) visitedi=1; printf("%2c"

12、,G.vexsi); EnQueue(Q,i); while(Q.front!=Q.rear) k=DeQueue(Q); for(w=FirstAdiVex(G,k);w>=0;w=NextAdVex(G,k,w) if(!visitedw) visitedw=1; printf("%2c",G.vexsw); EnQueue(Q,w); int main()int m;Graph G;printf("無向圖的創(chuàng)建及DFS和BFS的遞歸和非遞歸實(shí)現(xiàn)!nn");while(1)printf("1.創(chuàng)建無向圖!n"); print

13、f("2.圖的深度優(yōu)先遍歷!n"); printf("3.圖的廣度優(yōu)先遍歷!n"); printf("4.退出!n"); printf("請(qǐng)選擇功能:"); scanf("%d",&m); if(m=1)CreateGraph(G); PrintMatrix(G); else if(m=2) printf("圖G的深度遞歸優(yōu)先遍歷序列為:n"); DFS(G,0); printf("n"); else if(m=3) printf("圖G的廣度非遞歸優(yōu)先遍歷序列為:n"); BFS(G); printf("n"); else if(m=4) printf("成功退出!n"); break; else printf("重新輸入!n");return 0;3.6測(cè)試結(jié)果測(cè)試數(shù)據(jù)如下： ABCED深度優(yōu)先遍歷序列：A->B->D->C->E廣度優(yōu)先遍歷序列：A->B->C->E-&