圖的基本操作與實(shí)現(xiàn)的課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：圖的基本操作與實(shí)現(xiàn)專業(yè)班 級(jí)學(xué) 生學(xué) 號(hào)指導(dǎo)教師起止時(shí)間年 學(xué)期1. 問題描述： 實(shí)現(xiàn)圖的一些基本操作2. 基本要求： (2) 求每個(gè)頂點(diǎn)的度, 輸出結(jié)果； 3. 測試數(shù)據(jù)： 4. 算法思想： (1) 自選存儲(chǔ)結(jié)構(gòu)創(chuàng)建一個(gè)圖： (2) 求每個(gè)頂點(diǎn)的度： (3) 圖的深度優(yōu)先遍歷： (4) 圖的廣度優(yōu)先遍歷： (5) 判斷有向圖的強(qiáng)連通性： (6) 用鄰接矩陣的信息生成鄰接表：6. 數(shù)據(jù)結(jié)構(gòu)： 7. 功能模塊圖 8. 源程序： 9. 心得體會(huì)： 1. 問題描述 ： 實(shí)現(xiàn)圖的一些基本操作2. 基本要求：(1) 自選存儲(chǔ)結(jié)構(gòu) , 輸入含 n 個(gè)頂點(diǎn)(用字符表示頂點(diǎn))和

2、e 條邊的圖G；(2) 求每個(gè)頂點(diǎn)的度, 輸出結(jié)果；(3)指定任意頂點(diǎn)x為初始頂點(diǎn)，對(duì)圖G作DFS遍歷，輸出DFS1點(diǎn)序列(提示: 使用一個(gè)棧實(shí)現(xiàn)DFS)；(4)指定任意頂點(diǎn)x為初始頂點(diǎn)，對(duì)圖G作BFS遍歷，輸出BFS頂點(diǎn)序列(提示:使用一個(gè)隊(duì)列實(shí)現(xiàn)BFS)；(5)輸入頂點(diǎn)x,查找圖G:若存在含x的頂點(diǎn)，則刪除該結(jié)點(diǎn)及與之相關(guān)連的邊， 并作DFS遍歷(執(zhí)行操作3);否則輸出信 息“無x” ；(6)判斷圖G是否是連通圖，輸出信息“ YE6 / “NO;(7) 如果選用的存儲(chǔ)結(jié)構(gòu)是鄰接矩陣 , 則用鄰接矩陣的信息生成圖G 的鄰接表,即復(fù)制圖G,然再執(zhí)行操作(2);反之亦然。3. 測試數(shù)據(jù)：有向圖的

3、頂點(diǎn)數(shù)n 和有向圖的邊數(shù)e 由用戶從鍵盤敲入4. 算法思想：(1) 自選存儲(chǔ)結(jié)構(gòu)創(chuàng)建一個(gè)圖： 通過用戶從鍵盤敲入的兩個(gè)數(shù)值分別確定圖的頂點(diǎn)數(shù)和邊數(shù)， 選擇鄰接矩陣存儲(chǔ)結(jié)構(gòu)將圖的結(jié)點(diǎn)信息存儲(chǔ)在一個(gè)順序表中， 圖的 邊信息存儲(chǔ)在一個(gè)二維數(shù)組中。(2) 求每個(gè)頂點(diǎn)的度：1 .鄰接矩陣存儲(chǔ)結(jié)構(gòu)下求每個(gè)頂點(diǎn)的度： 利用圖的鄰接矩陣， 每個(gè)頂點(diǎn)所在行和所在列的邊的權(quán)值如果存在則該頂點(diǎn)的度+1， 依次算出每個(gè)頂點(diǎn)的度， 并且記錄在一個(gè)數(shù)組中輸出。2 . 鄰接表存儲(chǔ)結(jié)構(gòu)下求每個(gè)頂點(diǎn)的度： 定義一個(gè)鄰接邊指針循環(huán)指向頂點(diǎn)的鄰接邊單鏈表頭結(jié)點(diǎn)，當(dāng)結(jié)點(diǎn)不空時(shí)，該頂點(diǎn)的出度+1, 鄰接邊弧頭結(jié)點(diǎn)的入度+1，依次求出每

4、個(gè)頂點(diǎn)的出度和入度之和就為該頂點(diǎn)的度。(3) 圖的深度優(yōu)先遍歷： 采取鄰接矩陣結(jié)構(gòu)，指定任意頂點(diǎn) x 為初始頂點(diǎn)1 .訪問結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v已訪問；2 . 查找結(jié)點(diǎn) v 的第一個(gè)鄰接結(jié)點(diǎn)w；3 .若結(jié)點(diǎn)v的鄰接結(jié)點(diǎn)w存在，則繼續(xù)執(zhí)行，否則算法結(jié)束；4 . 若結(jié)點(diǎn)w 尚未被訪問，則遞歸訪問結(jié)點(diǎn)w；5 .查找結(jié)點(diǎn)v的w鄰接結(jié)點(diǎn)的下一個(gè)鄰接結(jié)點(diǎn)w,轉(zhuǎn)到步驟3。(4) 圖的廣度優(yōu)先遍歷： 采取鄰接矩陣結(jié)構(gòu)，指定任意頂點(diǎn) x 為初始頂點(diǎn)，利用順序循環(huán)隊(duì)列以保持訪問過的結(jié)點(diǎn)的順序1. 首先訪問初始結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v為已訪問；2. 結(jié)點(diǎn) v 入隊(duì)列；3. 當(dāng)隊(duì)列非空時(shí)則繼續(xù)執(zhí)行，否則算法結(jié)束；4. 出隊(duì)列取

5、得隊(duì)頭結(jié)點(diǎn) u；5. 查找 u 的第一個(gè)鄰接結(jié)點(diǎn)w；6. 若u的鄰接結(jié)點(diǎn)w不存在則轉(zhuǎn)到步驟3,否則循環(huán)執(zhí)行下列步驟：若結(jié)點(diǎn)w尚未被訪問，則訪問結(jié)點(diǎn) w并標(biāo)記結(jié)點(diǎn)w為已訪問；結(jié)點(diǎn)w入隊(duì)列；查找結(jié)點(diǎn)u的w鄰接結(jié)點(diǎn)的下一個(gè)鄰接結(jié)點(diǎn)w,轉(zhuǎn)到步驟6。(5) 判斷有向圖的強(qiáng)連通性： 采取鄰接表結(jié)構(gòu)，在圖中尋找一個(gè)包含所有頂點(diǎn)且首尾相連的環(huán)，若這樣的環(huán)存在，則該圖為強(qiáng)連通圖，否則不為強(qiáng)連通圖。(6) 用鄰接矩陣的信息生成鄰接表： 定義一個(gè)鄰接表的邊信息結(jié)構(gòu)體，將鄰接矩陣的邊信息轉(zhuǎn)換成鄰接表的邊信息存儲(chǔ)到鄰接邊的單鏈表中。5. 模塊劃分：mian(): 主函數(shù)模塊。在主函數(shù)模塊中調(diào)用以下函數(shù)：(1) void

6、 CreatGraph(AdjMGraph *G,DataType v,int n,RowColWeight E,int e) ： 創(chuàng)建一個(gè)鄰接矩陣存儲(chǔ)結(jié)構(gòu)的圖；(2) void Print(AdjMGraph *G)： 輸出圖的鄰接矩陣；(3) void MVertices(AdjMGraph *G,DataType a) ：求出鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的每個(gè)頂點(diǎn)的度；(4) void CreatLGraph(AdjLGraph *G,DataType v,int n,RowCol d,int e) ：用鄰接矩陣的信息生成鄰接表；(5) void LVertices(AdjLGraph *G,D

7、ataType a) ：求出鄰接表存 儲(chǔ)結(jié)構(gòu)下圖的每個(gè)頂點(diǎn)的度；(6) int LianTong(AdjLGraph *G,DataType a) ：判斷有向圖的強(qiáng)連通性；(7) voidDepthFirstSearch(AdjMGraphG,voidVisit(DataTypeitem):對(duì)圖作DFS遍歷，輸出DFS1點(diǎn)序列；(8) voidBroadFirstSearch(AdjMGraphG,voidVisit(DataTypeitem):對(duì)圖作BFS遍歷，輸出BFS頂點(diǎn)序列；(9) int ChaZhao(AdjMGraph *G,int v) ：查找頂點(diǎn) v；(10) void MD

8、elete(AdjMGraph *G,int v) ：刪除查找到的結(jié)點(diǎn) v 并刪 除該結(jié)點(diǎn)及與之相關(guān)的邊；6. 數(shù)據(jù)結(jié)構(gòu)：(1) 有向圖頂點(diǎn)的數(shù)據(jù)類型DataType 定義如下：typedef int DataType ；(2) 鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定義如下：typedef structSeqList Vertices ； 能模塊圖：8.源程序：源程序存放在八個(gè)文件夾中，文件是順序表的結(jié)構(gòu)體定義和操作函數(shù)，文件是順序循環(huán)隊(duì)列的結(jié)構(gòu)體定義和操作函數(shù)，文件是鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定 義和操作函數(shù)，文件是鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的創(chuàng)建函數(shù)，文件是鄰接表存儲(chǔ)結(jié)構(gòu)下圖的結(jié)構(gòu)體定義和操作函數(shù)，文

9、件是鄰接表存儲(chǔ)結(jié)構(gòu)下圖的創(chuàng)建函數(shù)，文件是鄰接矩陣存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷操作函數(shù)，文件圖的基本操作與實(shí)現(xiàn).c是主函數(shù)。(1)/* 文件 */ typedef struct DataType listMaxSize; int size;SeqList;void ListInitiate(SeqList *L)L->size=0;int ListLength(SeqList L)return ;int ListInsert(SeqList *L,int i,DataType x)int j;if(L->size>=MaxSize)printf(" 數(shù)組已

10、滿無法插入！ n");return 0;else if(i<0|i>L->size)printf(" 參數(shù)不合法！ n");return 0;elsefor(j=L->size;j>i;i-)L->listj=L->listj-1;L->listi=x;L->size+;return 1;int ListDelete(SeqList *L,int i,DataType *x)int j;if(L->size<=0)n");printf(" 順序表已空無數(shù)據(jù)元素可刪！return

11、0;else if(i<0|i>L->size-1)printf(" 參數(shù) i 不合法！ n");return 0;else*x=L->listi;for(j=i+1;j<=L->size-1;j+)L->listj-1=L->listj;L->size-;return 1;int ListGet(SeqList L,int i,DataType *x)if(i<0|i>printf(" 參數(shù) i 不合法！ n");return 0;else*x=i;return 1;(2)/* 文件 *

12、/typedef structDataType queueMaxQueueSize;int rear;int front;int count;SeqCQueue;void QueueInitiate(SeqCQueue *Q)Q->rear=0;Q->front =0;Q->count =0;int QueueNotEmpty(SeqCQueue Q)if !=0) return 1;else return 0;int QueueAppend(SeqCQueue *Q,DataType x)if(Q->count>0&&Q->rear=Q-&

13、gt;front)printf(" 隊(duì)列已滿無法插入!");return 0;elseQ->queue Q->rear=x;Q->rear =(Q->rear +1)%MaxQueueSize;Q->count +;return 1;int QueueDelete(SeqCQueue *Q,DataType *d)if(Q->count =0)printf(" 隊(duì)列已空無數(shù)據(jù)出隊(duì)列 !n");return 0;else*d=Q->queueQ->front;Q->front=(Q->front+

14、1)%MaxQueueSize;Q->count -;return 1;int QueueGet(SeqCQueue Q,DataType*d)if =0)printf(" 隊(duì)列已空無數(shù)據(jù)出隊(duì)列 !n");return 0;else*d= ;return 1;(3)/* 文件 */#include""typedef structSeqList Vertices; ow,Ek.col,Ek.weight); orce=i; G->ai.adj=NULL;dj;while(p!=NULL)q=p->next;free(p); p=q;ata

15、=vertex; dj; dj=p; dj;while(curr!=NULL&&curr->dest!=v2)dj=curr->next;free(curr);G->numOfEdges-;else if(curr!=NULL&&curr->dest=v2&&pre!=NULL) dj;if(p!=NULL)return p->dest; dj;while(p!=NULL) dj; dj;while(q!=NULL)bi+;q=q->next;for(i=0;i<G->numOfVerts;i+)i

16、f(bi=1)k+;p=G->aG->numOfVerts-1.adj;if(k=G->numOfVerts&&p->dest=a0)return 1;elsereturn 0;(6)/* 文件 */typedef structint row; ow,dk.col);(7)/* 文件 */void Visit(DataType item)printf("%d ",item);void DepthFSearch(AdjMGraph G,int v,int visited,void Visit(DataType item)*/#include<>#include<>#include<>typedef int DataType;ow,&rcwi.col,&rcwi.weight);CreatGraph(&g1,a,n,rcw,e);ol=rcwi.col;rwci.row=rcwi.row;CreatLGraph(&g2,a, 得體會(huì)：在本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)中我設(shè)計(jì)的題目是圖的基本操作與實(shí)現(xiàn)，經(jīng)過