1、精選優(yōu)質文檔-傾情為你奉上 數(shù)據(jù)結構實驗報告二級學院： 計算機學院 專 業(yè)： 指導教師： 班級學號： 姓 名： 實驗四1、題目：圖的設計2、問題描述： （1）定義鄰接矩陣存儲結構。（2）按照建立一個帶權有向圖的操作需要，編寫在鄰接矩陣存儲結構下，帶權有向圖基本操作的實現(xiàn)函數(shù)（如初始化圖、在圖中插入一個結點、在圖中插入一條邊、在圖中尋找序號為v的結點的第一個鄰接結點、在圖中尋找序號為v1結點的鄰接結點v2的下一個鄰接結點、圖的深度優(yōu)先遍歷或圖的廣度優(yōu)先遍歷等）。（3）設計一個測試主函數(shù)，首先創(chuàng)建一個圖（以圖9-5為例），然后打印圖的n個結點信息和e條邊信息，最后打印出圖的深度優(yōu)先遍歷或廣度優(yōu)先遍

2、歷的結點信息序列。3、基本要求：（1）為統(tǒng)一起見，創(chuàng)建一個以圖9-5為例的圖。（2）在鄰接矩陣存儲結構下，帶權有向圖基本操作的實現(xiàn)函數(shù)。（3）打印圖的n個結點信息和e條邊信息，打印出圖的深度優(yōu)先遍歷或廣度優(yōu)先遍歷的結點信息序列。（4）提交實驗報告。4、測試數(shù)據(jù)：5、算法思想：結點結構體：存放頂點的順序表，存放邊的鄰接矩陣（二維數(shù)組），邊的條數(shù)。初始化函數(shù)：令鄰接矩陣的元素為MaxWeight，邊的條數(shù)置為0，順序表初始化。插入結點函數(shù)：在圖G中插入頂點vertex即在順序表表尾插入頂點。插入邊函數(shù)：在圖G中插入邊<v1, v2>，邊<v1, v2>的權為weight。刪

3、除邊函數(shù)：在圖G中刪除邊<v1, v2>，即令對應的鄰接矩陣的元素為MaxWeight。取第一個鄰接頂點：在圖G中尋找序號為v的頂點的第一個鄰接頂點，就是鄰接矩陣的頂點v行中從第一個矩陣元素開始的非0且非無窮大的頂點，如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1。取下一個鄰接頂點：在圖G中尋找v1頂點的鄰接頂點v2的下一個鄰接頂點，就是鄰接矩陣的頂點v行中從第v2+1個矩陣元素開始的非0且非無窮大的頂點，如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1，這里v1和v2都是相應頂點的序號。創(chuàng)建圖函數(shù)：在圖G中插入n個頂點信息V和e條邊信息E，包括頂點順序表初始

4、化，插入頂點，插入邊。連通圖的深度優(yōu)先遍歷函數(shù)：1）訪問頂點v并標記頂點v已訪問。2）查找頂點v的第一個鄰接頂點w。3）若頂點v的鄰接頂點w存在，則繼續(xù)執(zhí)行，否則算法結束。4)若頂點w尚未被訪問，則深度優(yōu)先遍歷遞歸訪問頂點w。5）查找頂點v的w鄰接頂點的下一個鄰接頂點w，轉到步驟3）。非圖的深度優(yōu)先遍歷函數(shù)：訪問標記初始均為0，以每個頂點為初始頂點進行調用（調用連通圖的深度優(yōu)先遍歷函數(shù)）。連通圖的廣度優(yōu)先遍歷函數(shù)：1）訪問初始頂點v并標記頂點v為已訪問。2）頂點v入隊列。3）若隊列非空，則繼續(xù)執(zhí)行，否則算法結束。4)出隊列取得隊頭頂點u。5）查找頂點u的第一個鄰接頂點w。6）若頂點u的鄰接頂點

5、w不存在，則轉到步驟3），否則循環(huán)執(zhí)行：(a)若頂點w尚未被訪問，則訪問頂點w并標記頂點w為已訪問；(b)頂點w入隊列；(c)查找頂點u的w的鄰接頂點后的下一個鄰接頂點w，轉到步驟6）。 非圖的廣度優(yōu)先遍歷函數(shù)：訪問標記初始均為0，以每個頂點為初始頂點進行調用（調用連通圖的廣度優(yōu)先遍歷函數(shù)）。6、模塊劃分：1）定義圖的結點結構體。2）初始化操作函數(shù)。3）插入結點操作函數(shù)。4）插入邊操作函數(shù)。5）刪除邊操作函數(shù)。6）取第一個鄰接頂點。7）取下一個鄰接頂點。8）圖的深度優(yōu)先遍歷函數(shù)。9）圖的廣度優(yōu)先遍歷函數(shù)。10）定義邊信息結構體。11）創(chuàng)建圖函數(shù)。12）設計主函數(shù)進行測試。7、數(shù)據(jù)結構： 8、源

6、程序：#include <stdio.h>#include <stdlib.h>#include <malloc.h>typedef char DataType;#define MaxSize 100#define MaxVertices 10#define MaxEdges 100#define MaxWeight 10000#define MaxQueueSize 100#include "SeqList.h"#include "SeqCQueue.h"typedef struct SeqList Vertices

7、;/*存放頂點的順序表*/int edgeMaxVerticesMaxVertices;/*存放邊的鄰接矩陣*/int numOfEdges;/*邊的條數(shù)*/AdjMWGraph;/*圖的結構體定義*/void Initiate(AdjMWGraph *G, int n)/*初始化*/int i, j;for(i = 0; i < n; i+)for(j = 0; j < n; j+)if(i = j) G->edgeij = 0;else G->edgeij = MaxWeight;G->numOfEdges = 0;/*邊的條數(shù)置為0*/ListInitiat

8、e(&G->Vertices);/*順序表初始化*/void InsertVertex(AdjMWGraph *G, DataType vertex)/*在圖G中插入頂點vertex*/ListInsert(&G->Vertices, G->Vertices.size, vertex);/*順序表表尾插入*/void InsertEdge(AdjMWGraph *G, int v1, int v2, int weight)/*在圖G中插入邊<v1, v2>，邊<v1, v2>的權為weight*/if(v1 < 0 | v1 &g

9、t; G->Vertices.size | v2 < 0 | v2 > G->Vertices.size)printf("參數(shù)v1或v2越界出錯!n");exit(1);G->edgev1v2 = weight;G->numOfEdges+;void DeleteEdge(AdjMWGraph *G, int v1, int v2)/*在圖G中刪除邊<v1, v2>*/if(v1 < 0 | v1 > G->Vertices.size | v2 < 0 | v2 > G->Vertices.

10、size | v1 = v2)printf("參數(shù)v1或v2越界出錯!n");exit(1);G->edgev1v2 = MaxWeight;G->numOfEdges-;void DeleteVertex(AdjMWGraph *G, int v)/刪除結點vint n = ListLength(G->Vertices), i, j;DataType x;for(i = 0; i < n; i+)for(j = 0; j < n; j+)if(i = v | j = v) && G->edgeij > 0 &

11、;& G->edgeij < MaxWeight)G->numOfEdges-;/被刪除邊計數(shù)for(i = v; i < n; i+)for(j = 0; j < n; j+)G->edgeij = G->edgei+1j;/刪除第v行for(i = 0; i < n; i+)for(j = v; j < n; j+)G->edgeij = G->edgeij+1;/刪除第v列ListDelete(&G->Vertices, v, &x);/刪除結點vint GetFirstVex(AdjMWGr

12、aph G, int v)/*在圖G中尋找序號為v的頂點的第一個鄰接頂點*/*如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1*/int col;if(v < 0 | v > G.Vertices.size)printf("參數(shù)v1越界出錯!n");exit(1);for(col = 0; col <= G.Vertices.size; col+)if(G.edgevcol > 0 && G.edgevcol < MaxWeight) return col;return -1;int GetNextVex(AdjMWG

13、raph G, int v1, int v2)/*在圖G中尋找v1頂點的鄰接頂點v2的下一個鄰接頂點*/*如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1*/*這里v1和v2都是相應頂點的序號*/int col;if(v1 < 0 | v1 > G.Vertices.size | v2 < 0 | v2 > G.Vertices.size)printf("參數(shù)v1或v2越界出錯!n");exit(1);for(col = v2+1; col <= G.Vertices.size; col+)if(G.edgev1col > 0

14、&& G.edgev1col < MaxWeight) return col;return -1;typedef struct int row;/*行下標*/int col;/*列下標*/int weight;/*權值*/RowColWeight;/*邊信息三元組結構體定義*/void CreatGraph(AdjMWGraph *G, DataType V, int n, RowColWeight E, int e)/*在圖G中插入n個頂點信息V和e條邊信息E*/int i, k;Initiate(G, n);/*頂點順序表初始化*/for(i = 0; i <

15、n; i+)InsertVertex(G, Vi);/*頂點插入*/for(k = 0; k < e; k+)InsertEdge(G, Ek.row, Ek.col, Ek.weight);/*邊插入*/void DepthFSearch(AdjMWGraph G, int v, int visited)/*連通圖G以v為初始頂點的深度優(yōu)先遍歷*/*數(shù)組visited標記了相應頂點是否已訪問過，0表示未訪問，1表示已訪問*/int w;printf("%c ", G.Vertices.listv);/*輸出頂點字母*/visitedv = 1;w = GetFirs

16、tVex(G, v);while(w != -1)if(! visitedw) DepthFSearch(G, w, visited);w = GetNextVex(G, v, w);void DepthFirstSearch(AdjMWGraph G)/*非連通圖G的深度優(yōu)先遍歷*/int i;int *visited = (int *)malloc(sizeof(int)*G.Vertices.size);for(i = 0; i < G.Vertices.size; i+)visitedi = 0;for(i = 0; i < G.Vertices.size; i+)if(!

17、 visitedi) DepthFSearch(G, i, visited);free(visited);void BroadFSearch(AdjMWGraph G, int v, int visited)/*連通圖G以v為初始頂點的廣度優(yōu)先遍歷*/*數(shù)組visited標記了相應頂點是否已訪問過，0表示未訪問，1表示已訪問*/DataType u, w;SeqCQueue queue;printf("%c ", G.Vertices.listv);/*輸出頂點字母*/visitedv = 1;QueueInitiate(&queue);QueueAppend(&a

18、mp;queue, v);while(QueueNotEmpty(queue)QueueDelete(&queue, &u);w = GetFirstVex(G, u);while(w != -1)if(!visitedw)printf("%c ", G.Vertices.listw);/*輸出頂點字母*/visitedw = 1;QueueAppend(&queue, w);w = GetNextVex(G, u, w);void BroadFirstSearch(AdjMWGraph G)/*非連通圖G的廣度優(yōu)先遍歷*/int i;int *vi

19、sited = (int *)malloc(sizeof(int)*G.Vertices.size);for(i = 0; i < G.Vertices.size; i+)visitedi = 0;for(i = 0; i < G.Vertices.size; i+)if(!visitedi) BroadFSearch(G, i, visited);free(visited);void main(void)AdjMWGraph g1;DataType a = 'A','B','C','D','E'RowColWeight rcw = 0,1,1,0,2,1,0,3,1,0,4,1,2,4,1,3,1,1;