圖的遍歷課程設(shè)計

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計報告題 目： 圖的遍歷 學生姓名： 劉再科 學 號： 0213 專業(yè)班級： 計科10102班 同組姓名: 蔡雙 指導教師： 孫葉楓 設(shè)計時間： 2011年下學期第18周 指導老師意見: 評定成績: 簽名: 日期:目 錄一前言1. 課程設(shè)計的目的.32. 課程設(shè)計的基本要求.4二課程設(shè)計內(nèi)容.5三系統(tǒng)（項目）設(shè)計.6四源程序.8五程序的調(diào)試及測試結(jié)果.18六小結(jié).21七參考文獻.21一前言1、課程設(shè)計的目的數(shù)據(jù)結(jié)構(gòu)主要介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計算機中的存儲表示，以及在其上進行各種運算時的實現(xiàn)算法，并對算法的效

2、率進行簡單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應用于信息學、系統(tǒng)工程等各種領(lǐng)域。學習數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學生的思維能力，促進學生的綜合應用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達到以下目的：n 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；n 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；n 提高綜合運用所學的理論知識和方法獨立分析和解決問題的

3、能力；n 訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。2、課程設(shè)計的基本要求1.問題分析和任務定義：根據(jù)設(shè)計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？ 2.邏輯設(shè)計：對問題描述中涉及的操作對象定義相應的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計的結(jié)果應寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；3.詳細設(shè)計：定義相應的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)

4、功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；4.程序編碼：把詳細設(shè)計的結(jié)果進一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚；5.程序調(diào)試與測試：采用自底向上，分模塊進行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調(diào)試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結(jié)果；二課程設(shè)計內(nèi)容題目：圖的遍歷功能：實現(xiàn)圖的深度優(yōu)

5、先, 廣度優(yōu)先遍歷算法，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。分步實施：1) 初步完成總體設(shè)計，搭好框架；2） 完成最低要求：兩種必須都要實現(xiàn)，寫出畫圖的思路；3）進一步要求：畫出圖的結(jié)構(gòu)，有興趣的同學可以進一步改進圖的效果。要求：1）界面友好，函數(shù)功能要劃分好2）總體設(shè)計應畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的。三 系統(tǒng)（項目）設(shè)計用戶登錄錄入圖信息進入主菜單更改數(shù)據(jù)深度優(yōu)先遍歷廣度優(yōu)先遍歷退出程序 圖一、系統(tǒng)功能模塊圖登錄開始CreatueMGraph(G)ch1='y'ch1='

6、;y'輸入ch2CreatueMGraph(G)DFSTraverseM(G)BFSTraverseM(G)ch1='n'break結(jié)束程序ch2真1假230圖二、主函數(shù)流程圖四源程序#include<stdio.h>#include<stdlib.h>#define Max 10#define FALSE 0#define TRUE 1#define Error printf #define QueueSize 30typedef struct char vexsMax; int edgesMaxMax;int n,e;MGraph;/以鄰接矩

7、陣作為圖的存儲結(jié)構(gòu)int visited Max;/將visitedMax;/定義為全局變量并分配最大空間typedef struct int front ;int rear;int count;int dataQueueSize;CirQueue;/定義隊列的數(shù)據(jù)結(jié)構(gòu)/初始化隊列void InitQueue(CirQueue *Q )Q->front=Q->rear=0;Q->count=0;/隊列空int QueueEmpty(CirQueue *Q) return Q->count=QueueSize;/返回隊列 的最大長度/隊列滿int QueueFull(Ci

8、rQueue *Q) return Q->count=QueueSize;/返回隊列 的最大長度/進隊void EnQueue(CirQueue *Q,int x)if(QueueFull(Q)/隊列滿則出錯Error("Queue overflow");elseQ->count+;/否則count+,將x進隊Q->dataQ->rear=x;Q-> rear=(Q->rear+1)%QueueSize;/出隊int DeQueue (CirQueue *Q)int temp;/定義整型的變量if (QueueEmpty(Q)/若為真則出

9、錯Error("Queuue underflow"); return 0;else/為假澤count-,將隊員出對temp=Q->dataQ-> front;Q-> count-;Q-> front=(Q-> front+1)%QueueSize;return temp;/返回出對元素值/建立一個圖void CreatueMGraph(MGraph *G) int i,j,k;/定義整形變量char ch1,ch2;/定義字符型變量printf("n請輸入定點數(shù),邊數(shù)(格式:4,5)");scanf("%d,%d&

10、quot;,&(G->n),&(G->e);/輸入圖的頂點數(shù)華和邊數(shù)for(i=0;i<G->n ;i+)getchar();printf("n請輸入第%d的頂點序號",i+1);scanf("%c",&(G->vexsi);/輸入頂點的序號 for(i=0;i<G-> n;i+)for(j=0;j<G-> n;j+)G->edgesij=0;/初始化矩陣for(k=0;k<G->e ;k+)getchar();printf("n請輸入第%d條邊的頂

11、點序號(格式:i,j):",k+1);scanf("%c,%c",&ch1,&ch2);/輸入邊的頂點序號for(i=0;ch1!=G->vexsi;i+);for(j=0;ch2!=G-> vexsj;j+);G-> edgesij=1;/有邊則賦值為1/深度優(yōu)先遍歷遞歸void DFSM(MGraph *G,int i) int j;printf("%c",G->vexs i);visitedi=TRUE;/標記visitedi/依次優(yōu)先搜索訪問visitedi的每個領(lǐng)結(jié)點for(j=0;j<G

12、-> n;j+)/若visitedi的一個有效鄰接點visitedi未被訪問過,則/visitedi出發(fā)進行遞歸調(diào)用if(G->edgesij=1&&visitedj)DFSM(G,j);/廣度優(yōu)先遍歷遞歸void BFSM(MGraph *G,int k)int i,j;CirQueue Q;/定義一個隊列Q,初始化隊列為空InitQueue(&Q);printf("%c ",G->vexsk);/訪問初始點,并將其標記已訪問visitedk=TRUE;EnQueue(&Q,k);/將以訪問過的初始點序號k入隊while(

13、!QueueEmpty(&Q)/隊列非空進行循環(huán)i=DeQueue(&Q);/隊首元素出隊for(j=0;j<G->n;j+)/依次搜索vexsk的可能鄰接點if(G->edgesij=1&&!visitedj)visitedj=TRUE;/標記vexsj已訪問過EnQueue(&Q,j);/頂點序號j入隊/深度優(yōu)先遍歷void DFSTraverseM(MGraph *G)int i;printf("n 深度優(yōu)先遍歷序列:" );for(i=0;i<G->n;i+)visitedi=FALSE;/訪問標

14、志數(shù)組初始化for(i=0;i<G->n;i+)if(!visitedi)/對尚未訪問的的頂點調(diào)用DFSMDFSM(G,i);/廣度優(yōu)先遍歷void BFSTraverseM(MGraph *G)int i;printf("n 廣度優(yōu)先遍歷序列:" );for(i=0;i<G->n;i+)visitedi=FALSE;/訪問標志數(shù)組初始化for(i=0;i<G->n;i+)if(!visitedi)/對尚未訪問的的頂點調(diào)用BFSMBFSM(G,i);void main()MGraph *G,a;char ch1;int ch2;G=&am

15、p;a;printf("ntt 深度優(yōu)先遍歷和廣度優(yōu)先遍歷 n");CreatueMGraph(G);/調(diào)用創(chuàng)建圖矩陣函數(shù)getchar();ch1='y'/控制語句標志while(ch1='y'|ch1='Y') printf("n");printf(" 主菜單 ");printf("ntt=n");printf("tt = 更改數(shù)據(jù)請按:1 =n");printf("tt = 深度優(yōu)先遍歷請按:2 =n");printf(&

16、quot;tt = 廣度優(yōu)先遍歷請按:3 =n");printf("tt = 退出程序請按:0 =n");printf("ntt=n");printf("ntt請選擇: ");scanf("%d",&ch2);getchar();switch(ch2)case 1:CreatueMGraph(G);/選擇1創(chuàng)建一個新的圖矩陣break;case 2:DFSTraverseM(G);/選擇深度優(yōu)先遍歷break;case 3: BFSTraverseM(G);/選擇廣度優(yōu)先遍歷 break;case

17、 0: /選擇0退出程序 ch1='n' break;default:system("cls");printf("ntt輸入錯誤!n");break;if(ch2=1|ch2=2|ch2=3)printf("nntt ");/控制格式五程序的調(diào)試及測試結(jié)果5.1、開始進入程序。5.2、輸入頂點和邊數(shù)后，進入頂點的序號編號。 5.3、將頂點編號后，輸入邊的頂點序號。5.4、輸入邊的頂點序號后，進入主菜單進行選擇。5.5、選擇2進行深度優(yōu)先遍歷，再次進入主菜單進行選擇。 5.6、選擇1更改數(shù)據(jù)，重新創(chuàng)建一個圖。 5.7、選擇0退出程序。六小結(jié)通過為期一周的課程設(shè)計使我對圖的遍歷有了更深的認識和理解，也使我更加明白圖的遍歷在數(shù)據(jù)結(jié)構(gòu)