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

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

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

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

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

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

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

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

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

9、件是鄰接表存儲結(jié)構(gòu)下圖的創(chuàng)建函數(shù)，文件是鄰接矩陣存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷操作函數(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(" 隊列已滿無法插入!");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(" 隊列已空無數(shù)據(jù)出隊列 !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(" 隊列已空無數(shù)據(jù)出隊列 !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, 得體會：在本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計中我設(shè)計的題目是圖的基本操作與實現(xiàn)，經(jīng)過