《數(shù)據(jù)結(jié)構(gòu) 二維碼文件第4章主要算法的C++代碼.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu) 二維碼文件第4章主要算法的C++代碼.doc（16頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、第4章主要算法的C+代碼實(shí)驗(yàn)1：圖的存儲(chǔ)1圖的鄰接矩陣存儲(chǔ)及輸出。#include using namespace std; typedef char VertexType; /頂點(diǎn)類型應(yīng)由用戶定義typedef int EdgeType; /邊上的權(quán)值類型應(yīng)由用戶定義 #define MAXVEX 10 /最大頂點(diǎn)數(shù)，應(yīng)由用戶定義 typedef struct VertexType vexsMAXVEX; /頂點(diǎn)表 EdgeType arcMAXVEXMAXVEX; /鄰接矩陣，可看作邊 int numVertexes, numEdges; /圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)Graph; int lo

2、cates(Graph *g, char ch) /定位 int i = 0; for(i = 0; i numVertexes; i+) if(g-vexsi = ch) break; if(i = g-numVertexes) return -1; return i;/建立一個(gè)無向網(wǎng)圖的鄰接矩陣表示void CreateGraph(Graph *g) int i, j, k, w; cout輸入頂點(diǎn)數(shù)和邊數(shù):g-numVertexesg-numEdges; cout請輸入頂點(diǎn)名稱，每個(gè)頂點(diǎn)用單個(gè)字母或單個(gè)數(shù)字表示，并以回車鍵結(jié)束：endl; for(i = 0; i numVertexes

3、; i+) g-vexsi = getchar(); while(g-vexsi = n) g-vexsi = getchar(); cout你輸入的頂點(diǎn)是：; for(i = 0; i numVertexes; i+) coutvexsi; coutendl; for(i = 0; i numEdges; i+) for(j = 0; j numEdges; j+) g-arcij = 0; /鄰接矩陣初始化 for(k = 0; k numEdges; k+) char p, q; cout輸入邊(vi,vj)上的頂點(diǎn)i名稱，頂點(diǎn)j名稱和權(quán)值,每個(gè)輸入后面以回鍵結(jié)束:w; int m =

4、-1; int n = -1; m = locates(g, p); n = locates(g, q); if(n = -1 | m = -1) fprintf(stderr, there is no this vertex.n); return; g-arcmn = w; g-arcnm = g-arcmn; /因?yàn)槭菬o向圖，矩陣對稱 /打印圖void printGraph(Graph g) int i, j; cout這個(gè)鄰接矩陣為：endl; for(i = 0; i g.numVertexes; i+) for(j = 0; j g.numVertexes; j+) cout g.a

5、rcij; coutendl; int main(int argc, char *argv) Graph g; CreateGraph(&g); /鄰接矩陣創(chuàng)建圖 printGraph(g); return 0;2圖的鄰接表存儲(chǔ)及輸出。/* 鄰接表表示的圖結(jié)構(gòu) */#include using namespace std; #define DEBUG#define MAXVEX 1000 /最大頂點(diǎn)數(shù)typedef char VertexType; /頂點(diǎn)類型應(yīng)由用戶定義typedef int EdgeType; /邊上的權(quán)值類型應(yīng)由用戶定義 typedef struct EdgeNode /

6、邊表結(jié)點(diǎn) int adjvex; /鄰接點(diǎn)域，存儲(chǔ)該頂點(diǎn)對應(yīng)的下標(biāo) EdgeType weigth; /用于存儲(chǔ)權(quán)值，對于非網(wǎng)圖可以不需要 struct EdgeNode *next; /鏈域，指向下一個(gè)鄰接點(diǎn)EdgeNode; typedef struct VertexNode /頂點(diǎn)表結(jié)構(gòu) VertexType data; /頂點(diǎn)域，存儲(chǔ)頂點(diǎn)信息 EdgeNode *firstedge; /邊表頭指針VertexNode, AdjListMAXVEX; typedef struct AdjList adjList; int numVertexes, numEdges; /圖中當(dāng)前頂點(diǎn)數(shù)和邊

7、數(shù)GraphList; int Locate(GraphList *g, char ch) int i; for(i = 0; i adjListi.data) break; if(i = MAXVEX) fprintf(stderr,there is no vertex.n); return -1; return i; /建立圖的鄰接表結(jié)構(gòu)void CreateGraph(GraphList *g) int i, j, k; EdgeNode *e; EdgeNode *f; coutg-numVertexesg-numEdges; cout請輸入少于10個(gè)頂點(diǎn),每個(gè)頂點(diǎn)用單個(gè)字母或單個(gè)數(shù)字

8、表示，并以回車鍵結(jié)束:endl; for(i = 0; i numVertexes; i+) g-adjListi.data = getchar(); /輸入頂點(diǎn)信息 g-adjListi.firstedge = NULL; /將邊表置為空表 while(g-adjListi.data = n) g-adjListi.data = getchar(); for(k = 0; k numEdges; k+) /建立邊表 cout輸入邊(vi,vj)上的頂點(diǎn)序號及權(quán)值:w; int m, n; m = Locate(g, p); n = Locate(g, q); if(m = -1 | n =

9、-1) return; /向內(nèi)存申請空間，生成邊表結(jié)點(diǎn) e = (EdgeNode *)malloc(sizeof(EdgeNode); if(e = NULL) fprintf(stderr, malloc() error.n); return; e-adjvex = n; /鄰接序號為n /將e指針指向當(dāng)前頂點(diǎn)指向的結(jié)構(gòu) e-weigth=w; /權(quán)值為w e-next = g-adjListm.firstedge; /將當(dāng)前頂點(diǎn)的指針指向e g-adjListm.firstedge = e; f = (EdgeNode *)malloc(sizeof(EdgeNode); if(f =

10、NULL) fprintf(stderr, malloc() error.n); return; f-adjvex = m;f-weigth=w; f-next = g-adjListn.firstedge; g-adjListn.firstedge = f; void printGraph(GraphList *g) int i = 0; while(g-adjListi.firstedge != NULL & i numVertexes) cout頂點(diǎn):adjListi.data; EdgeNode *e = NULL; e = g-adjListi.firstedge; while(e

11、!= NULL) cout ; cout(adjvex; cout,weigthnext; i+; coutendl; int main(int argc, char *argv) GraphList g; CreateGraph(&g); printGraph(&g); return 0;實(shí)驗(yàn)2 ：圖的遍歷#include #include using namespace std;#define MAXVEX 100 /最大頂點(diǎn)數(shù)typedef int Boolean; /Boolean 是布爾類型，其值是TRUE 或FALSEBoolean visitedMAXVEX; /訪問標(biāo)志數(shù)組#d

12、efine TRUE 1#define FALSE 0 typedef char VertexType; /頂點(diǎn)類型應(yīng)由用戶定義typedef int EdgeType; /邊上的權(quán)值類型應(yīng)由用戶定義 typedef struct VertexType vexsMAXVEX; /頂點(diǎn)表 EdgeType arcMAXVEXMAXVEX; /鄰接矩陣，可看作邊 int numVertexes, numEdges; /圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)Graph; int locates(Graph *g, char ch) /定位 int i = 0; for(i = 0; i numVertexes; i

13、+) if(g-vexsi = ch) break; if(i = g-numVertexes) return -1; return i;/建立一個(gè)無向網(wǎng)圖的鄰接矩陣表示void CreateGraph(Graph *g) int i, j, k; cout輸入頂點(diǎn)數(shù)和邊數(shù):g-numVertexesg-numEdges; cout請輸入頂點(diǎn)名稱，每個(gè)頂點(diǎn)用單個(gè)字母或單個(gè)數(shù)字表示，并以回車鍵結(jié)束：endl; for(i = 0; i numVertexes; i+) g-vexsi = getchar(); while(g-vexsi = n) g-vexsi = getchar(); cou

14、t你輸入的頂點(diǎn)是：; for(i = 0; i numVertexes; i+) coutvexsi; coutendl;for(i = 0; i numEdges; i+) for(j = 0; j numEdges; j+) g-arcij = 0; /鄰接矩陣初始化 for(k = 0; k numEdges; k+) char p, q; cout輸入邊(vi,vj)上的頂點(diǎn)i名稱，頂點(diǎn)j名稱,每個(gè)輸入后面以回鍵結(jié)束:arcmn = 1; g-arcnm = g-arcmn; /因?yàn)槭菬o向圖，矩陣對稱 void DFS(Graph g, int i) /鄰接矩陣的深度優(yōu)先遞歸算法 in

15、t j; visitedi = TRUE; coutg.vexsi; /打印頂點(diǎn)，也可以其他操作 for(j = 0; j g.numVertexes; j+) if(g.arcij = 1 & !visitedj) DFS(g, j); /對為訪問的鄰接頂點(diǎn)遞歸調(diào)用 /鄰接矩陣的深度遍歷操作void DFSTraverse(Graph g) int i; for(i = 0; i g.numVertexes; i+) visitedi = FALSE; /初始化所有頂點(diǎn)狀態(tài)都是未訪問過狀態(tài) cout深度優(yōu)先遍歷次序?yàn)椋?for(i = 0; i g.numVertexes; i+) if(!

16、visitedi) /對未訪問的頂點(diǎn)調(diào)用DFS，若是連通圖，只會(huì)執(zhí)行一次 DFS(g,i); coutendl;/鄰接矩陣的廣度遍歷算法void BFSTraverse(Graph g) int i, j; queueq;for(i = 0; i g.numVertexes; i+) visitedi = FALSE; cout廣度優(yōu)先遍歷次序?yàn)椋? for(i = 0; i g.numVertexes; i+) /對每個(gè)頂點(diǎn)做循環(huán) if(!visitedi) /若是未訪問過 visitedi = TRUE; coutg.vexsi; /打印結(jié)點(diǎn) q.push(i); /將此結(jié)點(diǎn)入隊(duì)列 whi

17、le(!q.empty() /將隊(duì)中元素出隊(duì)列，賦值給 int m; m=q.front();q.pop(); for(j = 0; j g.numVertexes; j+) /判斷其他頂點(diǎn)若與當(dāng)前頂點(diǎn)存在邊且未訪問過 if(g.arcmj = 1 & !visitedj) visitedj = TRUE; coutg.vexsj; q.push(j); int main(int argc, char *argv) Graph g; CreateGraph(&g); /鄰接矩陣創(chuàng)建圖 DFSTraverse(g);BFSTraverse(g); return 0;Prim算法實(shí)現(xiàn)：#inclu

18、de using namespace std;typedef char VertexType; /頂點(diǎn)類型應(yīng)由用戶定義typedef int EdgeType; /邊上的權(quán)值類型應(yīng)由用戶定義 #define MAXVEX 100 /最大頂點(diǎn)數(shù)，應(yīng)由用戶定義#define MAX 65535 /以65535代表無窮大typedef struct VertexType vexsMAXVEX; /頂點(diǎn)表 EdgeType arcMAXVEXMAXVEX; /鄰接矩陣，可看作邊 int numVertexes, numEdges; /圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)Graph;typedef structint top,tail;/用于存儲(chǔ)選中邊的兩個(gè)頂點(diǎn)下標(biāo)EdgeType lowcost; /最小邊值Edges; /邊結(jié)構(gòu)三元組/定位int locates(Graph *g, char ch) int i = 0; for(i = 0; i numVertexes; i+) if(g-vexsi = ch) break; if(i = g-numVertexes) return -1; return i;/建立一個(gè)無向網(wǎng)圖的鄰接矩陣表示void CreateGraph(Graph *g) int i, j, k, w; cout輸入頂點(diǎn)數(shù)和邊數(shù):endl;