-
图的邻接矩阵存储及遍历操作
第1关：图的邻接矩阵存储及求邻接点操作
任务描述
本关任务：要求从文件输入顶点和边数据，包括顶点信息、边、权值等，编写程序实现以下功能。
1）构造无向网G的邻接矩阵和顶点集，即图的存储结构为邻接矩阵。
2）输出无向网G的各顶点和邻接矩阵。
3）输出无向网G中顶点H的所有邻接顶点。测试说明
平台会对你编写的代码进行测试：
测试输入：
3
lt.txt
武汉输入说明：
第一行输入3，表示输入图的类型为无向网。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
6
9
武汉
上海
长沙
南京
成都
广州
武汉 长沙 9
武汉 成都 2
长沙 上海 2
长沙 南京 2
上海 南京 5
上海 广州 4
上海 成都 3
南京 广州 8
成都 广州 6第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；
最后输入一个顶点的数据预期输出：
无向网
6个顶点9条边。顶点依次是: 武汉 上海 长沙 南京 成都 广州
图的邻接矩阵:
∞ ∞ 9 ∞ 2 ∞
∞ ∞ 2 5 ∞ ∞
9 2 ∞ 2 ∞ ∞
∞ 5 2 ∞ ∞ ∞
2 ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞
长沙 成都输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后一行输出输入顶点的所有邻接点。代码如下
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<limits.h> typedef int VRType; // 顶点关系类型 typedef char VertexType[20]; // 顶点类型 // 图的数组(邻接矩阵)存储表示 #define INFINITY INT_MAX // 用整型最大值代替∞ #define MAX_VERTEX_NUM 20 // 最大顶点个数 typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向图,有向网,无向图,无向网} typedef struct { VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组 typedef struct // 图的数组(邻接矩阵)存储 { VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum,arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 }MGraph; void visit(VertexType i); void CreateGraphF(MGraph &G);// 采用数组(邻接矩阵)表示法，由文件构造无向网G void Display(MGraph G); // 输出邻接矩阵存储表示的图G int LocateVex(MGraph G,VertexType u);//若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 VertexType* GetVex(MGraph G,int v); // v是G中某个顶点的序号，返回v的值 int FirstAdjVex(MGraph G,VertexType v);//v是图G中某个顶点，返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 void DestroyGraph(MGraph &G); // 销毁图G int main() { MGraph g; VertexType v1,v2; CreateGraphF(g); // 利用数据文件创建邻接矩阵表示的图 Display(g); // 输出图 int i,j,k,n; //printf("请输入顶点的值: "); scanf("%s",v1); //printf("输出图G中顶点%s的所有邻接顶点: ",v1); k=FirstAdjVex(g,v1); while(k!=-1) { strcpy(v2, g.vexs[k] ); visit(v2); k=NextAdjVex(g,v1,v2); } printf("\n"); return 0; } void visit(VertexType i) { printf("%s ",i); } void CreateGraphF(MGraph &G) { // 采用数组(邻接矩阵)表示法，由文件构造无向网G /********** Begin **********/ int i,j,k,w; char filename[13]; VertexType va,vb; FILE * graphlist; scanf("%d",&G.kind); scanf("%s",filename); graphlist=fopen(filename,"r"); fscanf(graphlist,"%d",&G.vexnum); fscanf(graphlist,"%d",&G.arcnum); for(i=0;i<G.vexnum;i++) fscanf(graphlist,"%s",G.vexs[i]); for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j){ if(G.kind%2) G.arcs[i][j].adj=INFINITY; else G.arcs[i][j].adj=0; } for(k=0;k<G.arcnum;++k){ if(G.kind%2) fscanf(graphlist,"%s%s%d",va,vb,&w); else fscanf(graphlist,"%s%s",va,vb); i=LocateVex(G,va); j=LocateVex(G,vb); if(G.kind==0) G.arcs[i][j].adj=1; else if(G.kind==1) G.arcs[i][j].adj=w; else if(G.kind==2) G.arcs[i][j].adj=G.arcs[j][i].adj=1; else G.arcs[i][j].adj=G.arcs[j][i].adj=w; } fclose(graphlist); /********** End **********/ } void Display(MGraph G) { // 输出邻接矩阵存储表示的图G /********** Begin **********/ int i,j; switch(G.kind){ case DG:printf("有向图\n");break; case DN:printf("有向网\n");break; case UDG:printf("无向图\n");break; case UDN:printf("无向网\n"); } printf("%d个顶点%d条边。顶点依次是: ",G.vexnum,G.arcnum); for(i=0;i<G.vexnum;++i) printf("%s ",G.vexs[i]); printf("\n图的邻接矩阵:\n"); for(i=0;i<G.vexnum;i++){ for(j=0;j<G.vexnum;j++) if(G.kind%2){ if(G.arcs[i][j].adj==INFINITY) printf("%s\t","∞"); else printf("%d\t",G.arcs[i][j].adj); }else printf("%d\t",G.arcs[i][j].adj); printf("\n"); } /********** End **********/ } int LocateVex(MGraph G,VertexType u) { //初始条件：图G存在，u和G中顶点有相同特征 // 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 /********** Begin **********/ int i; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) return i; return -1; /********** Begin **********/ } VertexType* GetVex(MGraph G,int v) { // 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值 /********** Begin **********/ if(v>=G.vexnum || v<0) exit(0); return &(G.vexs[v]); /********** End **********/ } int FirstAdjVex(MGraph G,VertexType v) { // 初始条件：图G存在，v是G中某个顶点 // 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 /********** Begin **********/ int i,j,k; if(G.kind%2) j=INFINITY; else j=0; k=LocateVex(G,v); for(i=0;i<G.vexnum;i++) if(G.arcs[k][i].adj!=j) return i; return -1; /********** End **********/ } int NextAdjVex(MGraph G,VertexType v,VertexType w) { // 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 // 操作结果：返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 /********** Begin **********/ int i,j,k1,k2; if(G.kind%2) j=INFINITY; else j=0; k1=LocateVex(G,v); k2=LocateVex(G,w); for(i=k2+1;i<G.vexnum;i++) if(G.arcs[k1][i].adj!=j) return i; return -1; /********** End **********/ } void DestroyGraph(MGraph &G) { // 初始条件：图G存在。操作结果：销毁图G /********** Begin **********/ int i,j,k=0; if(G.kind%2) k=INFINITY; G.vexnum=0; G.arcnum=0; /********** End **********/ }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
第2关：图的深度优先遍历
任务描述
本关任务：以邻接矩阵存储图，要求编写程序实现图的深度优先遍历
测试说明
平台会对你编写的代码进行测试：
测试输入：
0
lt2.txt输入说明：
第一行输入0，表示输入图的类型为有向图。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；预期输出：
有向图
7个顶点9条边。顶点依次是: 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统
图的邻接矩阵:
0 0 1 1 0 0 0
0 0 1 0 1 0 0
0 0 0 0 1 0 0
0 0 0 0 1 1 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
深度优先遍历序列：
高等数学 C语言 数据结构 编译原理 操作系统 离散数学 程序设计基础输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后一行为从“高等数学”出发进行深度优先遍历的序列。代码如下
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<limits.h> #include"MGraph.h" void DFS(MGraph G,int v);// 从第v个顶点出发递归地深度优先遍历图G void DFSTraverse(MGraph G);// 图G存在，从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数visit一次且仅一次 int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) int main() { MGraph g; VertexType v1,v2; CreateGraphF(g); /* 利用数据文件创建无向图*/ Display(g); /* 输出无向图*/ printf("深度优先遍历序列：\n"); DFSTraverse(g); return 0; } void DFS(MGraph G,int v) { // 从第v个顶点出发递归地深度优先遍历图G /********** Begin **********/ int w; visited[v]=1; visit(G.vexs[v]); for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w])) if(!visited[w]) DFS(G,w); /********** End **********/ } void DFSTraverse(MGraph G) { //图G存在，从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数visit一次且仅一次 /********** Begin **********/ int v; for(v=0;v<G.vexnum;v++) visited[v]=0; for(v=0;v<G.vexnum;v++) if(!visited[v]) DFS(G,v); printf("\n"); /********** End **********/ }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
第3关：图的广度优先遍历
任务描述
本关任务：以邻接矩阵存储图，要求编写程序实现图的广度优先遍历。
测试说明
平台会对你编写的代码进行测试：
测试输入：
0
lt2.txt输入说明：
第一行输入0，表示输入图的类型为有向图。
第二行输入文件名，该文件里保存了图的数据信息，内容如下：
第1行为图的顶点的个数n；
第2行为图的边的条数m；
第3行至第n+2行是n个顶点的数据；
第n+3行至第n+m+2行是m条边的数据；预期输出：
有向图
7个顶点9条边。顶点依次是: 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统
图的邻接矩阵:
0 0 1 1 0 0 0
0 0 1 0 1 0 0
0 0 0 0 1 0 0
0 0 0 0 1 1 0
0 0 0 0 0 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
广度优先遍历序列：
高等数学 C语言 离散数学 数据结构 编译原理 操作系统 程序设计基础输出说明：
第一行输出图的类型。
第二行起输出图的顶点和边的数据信息。
最后一行为从“高等数学”出发进行广度优先遍历的序列。代码如下
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<limits.h> #include"MGraph.h" #include"sqqueue.h" void BFSTraverse(MGraph G);// 图G存在，从第1个顶点起，按广度优先非递归遍历图G,并对每个顶点调用函数visit一次且仅一次 int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) int main() { MGraph g; VertexType v1,v2; CreateGraphF(g); // 利用数据文件创建图 Display(g); // 输出图 printf("广度优先遍历序列：\n"); BFSTraverse(g); return 0; } void BFSTraverse(MGraph G) { // 图G存在，从第1个顶点起，按广度优先非递归遍历图G,并对每个顶点调用函数visit一次且仅一次 /********** Begin **********/ int v,u,w; SqQueue Q; for(v=0;v<G.vexnum;v++) visited[v]=0; InitQueue(Q); for(v=0;v<G.vexnum;v++) if(!visited[v]){ visited[v]=1; visit(G.vexs[v]); EnQueue(Q,v); while(!QueueEmpty(Q)){ DeQueue(Q,u); for(w=FirstAdjVex(G,G.vexs[u]);w>=0;w=NextAdjVex(G,G.vexs[u],G.vexs[w])) if(!visited[w]){ visited[w]=1; visit(G.vexs[w]); EnQueue(Q,w); } } } printf("\n"); /********** End **********/ }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
辅助文件
lt.txt6 9 武汉 上海 长沙 南京 成都 广州 武汉 长沙 9 武汉 成都 2 长沙 上海 2 长沙 南京 2 上海 南京 5 上海 广州 4 上海 成都 3 南京 广州 8 成都 广州 6- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
lt2.txt7 9 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统 高等数学 C语言 高等数学 离散数学 程序设计基础 数据结构 程序设计基础 C语言 C语言 数据结构 离散数学 数据结构 离散数学 编译原理 数据结构 编译原理 数据结构 操作系统- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
MGraph.h#ifndef __MGraph_H__ #define __MGraph_H__ typedef int VRType; // 顶点关系类型 typedef char VertexType[20]; // 顶点类型 // 图的数组(邻接矩阵)存储表示 #define INFINITY 4270000 // 用整型最大值代替∞ #define MAX_VERTEX_NUM 20 // 最大顶点个数 typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向图,有向网,无向图,无向网} typedef struct { VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组 typedef struct // 图的数组(邻接矩阵)存储 { VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum,arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 }MGraph; /*邻接矩阵的8个基本操作函数声明*/ int LocateVex(MGraph G,VertexType u);//若图G中存在顶点u，则返回该顶点在图中位置；否则返回-1 VertexType* GetVex(MGraph G,int v);// 根据图G中某个顶点的序号v，返回该顶点的值 void visit(VertexType i);// 访问输出顶点的值 int FirstAdjVex(MGraph G,VertexType v);// v是图G中某个顶点，返回v的第一个邻接顶点的序号。若顶点v在G中没有邻接顶点，则返回-1 int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是图G中某个顶点，w是v的邻接顶点，返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 void CreateGraphF(MGraph &G);//采用数组(邻接矩阵)表示法，由文件构造无向网G void DestroyGraph(MGraph &G);//销毁图G void Display(MGraph G);//输出邻接矩阵存储表示的图G #endif- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
MGraph.cpp#include<stdio.h> #include<stdlib.h> #include<string.h> #include"MGraph.h" /*邻接矩阵的8个基本操作函数定义*/ int LocateVex(MGraph G,VertexType u) { //初始条件：图G存在，u和G中顶点有相同特征 // 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 int i; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i]) == 0) return i; // VertexType是char [16]类型 return -1; } VertexType* GetVex(MGraph G,int v) { // 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值 if( v>=G.vexnum || v<0 ) exit(0); return &(G.vexs[v]); } void visit(VertexType i) { printf("%s ",i); } int FirstAdjVex(MGraph G,VertexType v) { // 初始条件：图G存在，v是G中某个顶点 // 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 int i,j=0,k; k=LocateVex(G,v); // k为顶点v在图G中的序号 if(G.kind%2) // 网 j=INFINITY; for(i=0;i<G.vexnum;i++) if(G.arcs[k][i].adj!=j) return i; return -1; } int NextAdjVex(MGraph G,VertexType v,VertexType w) { // 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 // 操作结果：返回v的(相对于w的)下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1 int i,j=0,k1,k2; k1=LocateVex(G,v); // k1为顶点v在图G中的序号 k2=LocateVex(G,w); // k2为顶点w在图G中的序号 if(G.kind%2) // 网 j=INFINITY; for(i=k2+1;i<G.vexnum;i++) if(G.arcs[k1][i].adj!=j) return i; return -1; } void CreateGraphF(MGraph &G) { // 采用数组(邻接矩阵)表示法，由文件构造无向网G int i,j,k,w; char filename[13]; VertexType va,vb; FILE *graphlist; //printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): "); scanf("%d",&G.kind); //printf("请输入数据文件名："); scanf("%s",filename); graphlist=fopen(filename,"r"); // 以graphlist指针 打开数据文件 fscanf(graphlist,"%d",&G.vexnum); fscanf(graphlist,"%d",&G.arcnum); for(i=0;i<G.vexnum;++i) // 构造顶点向量 fscanf(graphlist,"%s",G.vexs[i]); for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵 for(j=0;j<G.vexnum;++j) { if(G.kind%2) // 网 G.arcs[i][j].adj=INFINITY; else // 图 G.arcs[i][j].adj=0; } for(k=0;k<G.arcnum;++k) { if(G.kind%2) // 网 fscanf(graphlist,"%s%s%d",va,vb,&w); else // 图 fscanf(graphlist,"%s%s",va,vb); i=LocateVex(G,va); j=LocateVex(G,vb); if(G.kind == 0) // 有向图 G.arcs[i][j].adj =1; else if(G.kind == 1) G.arcs[i][j].adj=w; // 有向网 else if(G.kind == 2) // 无向图 G.arcs[i][j].adj = G.arcs[j][i].adj=1; else G.arcs[i][j].adj = G.arcs[j][i].adj = w; } fclose(graphlist); // 关闭数据文件 } void DestroyGraph(MGraph &G) { // 初始条件：图G存在。操作结果：销毁图G int i,j,k=0; if(G.kind%2) // 网 k=INFINITY; // k为两顶点之间无边或弧时邻接矩阵元素的值 G.vexnum=0; // 顶点数为0 G.arcnum=0; // 边数为0 } void Display(MGraph G) { // 输出邻接矩阵存储表示的图G int i,j; switch(G.kind) { case DG: printf("有向图\n"); break; case DN: printf("有向网\n"); break; case UDG:printf("无向图\n"); break; case UDN:printf("无向网\n"); } printf("%d个顶点%d条边。顶点依次是: ",G.vexnum,G.arcnum); for(i=0;i<G.vexnum;++i) // 输出G.vexs printf("%s ",G.vexs[i]); printf("\n图的邻接矩阵:\n"); // 输出G.arcs.adj for(i=0;i<G.vexnum;i++) { for(j=0;j<G.vexnum;j++) if(G.kind%2) { if(G.arcs[i][j].adj==INFINITY) printf("%s\t","∞"); else printf("%d\t",G.arcs[i][j].adj); } else printf("%d\t",G.arcs[i][j].adj); printf("\n"); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
sqqueue.h#ifndef __SQQUEUE_H__ #define __SQQUEUE_H__ #include"symbol.h" #define MAX_QSIZE 20 // 最大队列长度+1 typedef int VRType; // 顶点关系类型 typedef VRType QElemType; struct SqQueue { QElemType *base; // 初始化的动态分配存储空间 int front; // 头指针，若队列不空，指向队列头元素 int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置 }; void InitQueue(SqQueue &Q); // 构造一个空循环队列Q void DestroyQueue(SqQueue &Q); // 销毁循环队列Q，Q不再存在 void ClearQueue(SqQueue &Q); // 将Q清为空循环队列 int QueueEmpty(SqQueue Q); // 若循环队列Q为空队列，则返回TRUE；否则返回FALSE int QueueLength(SqQueue Q); // 返回Q的元素个数，即循环队列的长度 int GetHead(SqQueue Q,QElemType &e); // 若循环队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR int EnQueue(SqQueue &Q,QElemType e); // 插入元素e为循环队列Q的新的队尾元素 int DeQueue(SqQueue &Q,QElemType &e); // 若循环队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR void QueueTraverse(SqQueue Q,void(*vi)(QElemType)); // 从队头到队尾依次对队列Q中每个元素调用函数vi() #endif- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
sqqueue.cpp#include<stdio.h> #include<stdlib.h> #include"sqqueue.h" typedef int QElemType; void InitQueue(SqQueue &Q) { Q.base=(QElemType *)malloc(MAX_QSIZE*sizeof(QElemType)); if(!Q.base) // 存储分配失败 exit(OVERFLOW); Q.front=Q.rear=0; } // 销毁循环队列Q，Q不再存在 void DestroyQueue(SqQueue &Q) { if(Q.base) free(Q.base); Q.base=NULL; Q.front=Q.rear=0; } // 将Q清为空循环队列 void ClearQueue(SqQueue &Q) { Q.front=Q.rear=0; } // 若循环队列Q为空队列，则返回TRUE；否则返回FALSE int QueueEmpty(SqQueue Q) { if(Q.front==Q.rear) // 队列空的标志 return TRUE; else return FALSE; } // 返回Q的元素个数，即循环队列的长度 int QueueLength(SqQueue Q) { return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE; } // 若循环队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR int GetHead(SqQueue Q,QElemType &e) { if(Q.front==Q.rear) // 队列空 return ERROR; e=Q.base[Q.front]; return OK; } // 插入元素e为循环队列Q的新的队尾元素 int EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAX_QSIZE==Q.front) // 队列满 return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAX_QSIZE; return OK; } // 若循环队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR int DeQueue(SqQueue &Q,QElemType &e) { if(Q.front==Q.rear) // 队列空 return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAX_QSIZE; return OK; } // 从队头到队尾依次对队列Q中每个元素调用函数vi() void QueueTraverse(SqQueue Q,void(*vi)(QElemType)) { int i; i=Q.front; while(i!=Q.rear) { vi(Q.base[i]); i=(i+1)%MAX_QSIZE; } printf("\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
symbol.h#ifndef __SYMBOL_H__ #define __SYMBOL_H__ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #endif- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
-
相关阅读:
git版本管理的使用
ubuntu编写makefile编译c++程序
【C++】C++的类型转换
Qt_C++读写FM1208 CPU卡源码、支持windows、Linux系统
C语言基础5：操作符详解：算术、移位、赋值、单目、关系、逻辑、条件、逗号表达式、下标引用、表达式求值
EasyRecovery15非常好用的电脑数据恢复软件
linux--LVS负载均衡 DR模式 rr
echarts 柱状堆叠图（图例和x轴都是动态的）
四、java版 SpringCloud分布式微服务云架构之Java 对象和类
python习题002--字符串处理
- 原文地址：https://blog.csdn.net/qq_45917176/article/details/125627754