数据结构 二维码文件第4章主要算法的C++代码.doc

《数据结构 二维码文件第4章主要算法的C++代码.doc》由会员分享，可在线阅读，更多相关《数据结构 二维码文件第4章主要算法的C++代码.doc（16页珍藏版）》请在汇文网上搜索。

1、第4章主要算法的C+代码实验1：图的存储1图的邻接矩阵存储及输出。#include using namespace std; typedef char VertexType; /顶点类型应由用户定义typedef int EdgeType; /边上的权值类型应由用户定义 #define MAXVEX 10 /最大顶点数，应由用户定义 typedef struct VertexType vexsMAXVEX; /顶点表 EdgeType arcMAXVEXMAXVEX; /邻接矩阵，可看作边 int numVertexes, numEdges; /图中当前的顶点数和边数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;/建立一个无向网图的邻接矩阵表示void CreateGraph(Graph *g) int i, j, k, w; cout输入顶点数和边数:g-numVertexesg-numEdges; cout请输入顶点名称，每个顶点用单个字母或单个数字表示，并以回车键结束：endl; for(i = 0; i numVertexes

3、; i+) g-vexsi = getchar(); while(g-vexsi = n) g-vexsi = getchar(); cout你输入的顶点是：; 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)上的顶点i名称，顶点j名称和权值,每个输入后面以回键结束: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; /因为是无向图，矩阵对称 /打印图void printGraph(Graph g) int i, j; cout这个邻接矩阵为：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); /邻接矩阵创建图 printGraph(g); return 0;2图的邻接表存储及输出。/* 邻接表表示的图结构 */#include using namespace std; #define DEBUG#define MAXVEX 1000 /最大顶点数typedef char VertexType; /顶点类型应由用户定义typedef int EdgeType; /边上的权值类型应由用户定义 typedef struct EdgeNode /

6、边表结点 int adjvex; /邻接点域，存储该顶点对应的下标 EdgeType weigth; /用于存储权值，对于非网图可以不需要 struct EdgeNode *next; /链域，指向下一个邻接点EdgeNode; typedef struct VertexNode /顶点表结构 VertexType data; /顶点域，存储顶点信息 EdgeNode *firstedge; /边表头指针VertexNode, AdjListMAXVEX; typedef struct AdjList adjList; int numVertexes, numEdges; /图中当前顶点数和边

7、数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; /建立图的邻接表结构void CreateGraph(GraphList *g) int i, j, k; EdgeNode *e; EdgeNode *f; coutg-numVertexesg-numEdges; cout请输入少于10个顶点,每个顶点用单个字母或单个数字

8、表示，并以回车键结束:endl; for(i = 0; i numVertexes; i+) g-adjListi.data = getchar(); /输入顶点信息 g-adjListi.firstedge = NULL; /将边表置为空表 while(g-adjListi.data = n) g-adjListi.data = getchar(); for(k = 0; k numEdges; k+) /建立边表 cout输入边(vi,vj)上的顶点序号及权值:w; int m, n; m = Locate(g, p); n = Locate(g, q); if(m = -1 | n =

9、-1) return; /向内存申请空间，生成边表结点 e = (EdgeNode *)malloc(sizeof(EdgeNode); if(e = NULL) fprintf(stderr, malloc() error.n); return; e-adjvex = n; /邻接序号为n /将e指针指向当前顶点指向的结构 e-weigth=w; /权值为w e-next = g-adjListm.firstedge; /将当前顶点的指针指向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顶点: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;实验2 ：图的遍历#include #include using namespace std;#define MAXVEX 100 /最大顶点数typedef int Boolean; /Boolean 是布尔类型，其值是TRUE 或FALSEBoolean visitedMAXVEX; /访问标志数组#d

12、efine TRUE 1#define FALSE 0 typedef char VertexType; /顶点类型应由用户定义typedef int EdgeType; /边上的权值类型应由用户定义 typedef struct VertexType vexsMAXVEX; /顶点表 EdgeType arcMAXVEXMAXVEX; /邻接矩阵，可看作边 int numVertexes, numEdges; /图中当前的顶点数和边数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;/建立一个无向网图的邻接矩阵表示void CreateGraph(Graph *g) int i, j, k; cout输入顶点数和边数:g-numVertexesg-numEdges; cout请输入顶点名称，每个顶点用单个字母或单个数字表示，并以回车键结束：endl; for(i = 0; i numVertexes; i+) g-vexsi = getchar(); while(g-vexsi = n) g-vexsi = getchar(); cou

14、t你输入的顶点是：; 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)上的顶点i名称，顶点j名称,每个输入后面以回键结束:arcmn = 1; g-arcnm = g-arcmn; /因为是无向图，矩阵对称 void DFS(Graph g, int i) /邻接矩阵的深度优先递归算法 in

15、t j; visitedi = TRUE; coutg.vexsi; /打印顶点，也可以其他操作 for(j = 0; j g.numVertexes; j+) if(g.arcij = 1 & !visitedj) DFS(g, j); /对为访问的邻接顶点递归调用 /邻接矩阵的深度遍历操作void DFSTraverse(Graph g) int i; for(i = 0; i g.numVertexes; i+) visitedi = FALSE; /初始化所有顶点状态都是未访问过状态 cout深度优先遍历次序为：;for(i = 0; i g.numVertexes; i+) if(!

16、visitedi) /对未访问的顶点调用DFS，若是连通图，只会执行一次 DFS(g,i); coutendl;/邻接矩阵的广度遍历算法void BFSTraverse(Graph g) int i, j; queueq;for(i = 0; i g.numVertexes; i+) visitedi = FALSE; cout广度优先遍历次序为：; for(i = 0; i g.numVertexes; i+) /对每个顶点做循环 if(!visitedi) /若是未访问过 visitedi = TRUE; coutg.vexsi; /打印结点 q.push(i); /将此结点入队列 whi

17、le(!q.empty() /将队中元素出队列，赋值给 int m; m=q.front();q.pop(); for(j = 0; j g.numVertexes; j+) /判断其他顶点若与当前顶点存在边且未访问过 if(g.arcmj = 1 & !visitedj) visitedj = TRUE; coutg.vexsj; q.push(j); int main(int argc, char *argv) Graph g; CreateGraph(&g); /邻接矩阵创建图 DFSTraverse(g);BFSTraverse(g); return 0;Prim算法实现：#inclu

18、de using namespace std;typedef char VertexType; /顶点类型应由用户定义typedef int EdgeType; /边上的权值类型应由用户定义 #define MAXVEX 100 /最大顶点数，应由用户定义#define MAX 65535 /以65535代表无穷大typedef struct VertexType vexsMAXVEX; /顶点表 EdgeType arcMAXVEXMAXVEX; /邻接矩阵，可看作边 int numVertexes, numEdges; /图中当前的顶点数和边数Graph;typedef structint top,tail;/用于存储选中边的两个顶点下标EdgeType lowcost; /最小边值Edges; /边结构三元组/定位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;/建立一个无向网图的邻接矩阵表示void CreateGraph(Graph *g) int i, j, k, w; cout输入顶点数和边数:endl;