#include <iostream> #include <iomanip> #include <cstdio> using namespace std; #define MVNum 100 //最大顶点数 typedef string VerTexType; //假设顶点的数据类型为字符串 typedef int ArcType; //假设边的权值类型为整型 //------------图的邻接矩阵------------------ typedef struct { VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum, arcnum; //图的当前点数和边数 } Graph; //得到顶点i的数据 VerTexType Vertexdata(const Graph &g, int i) { return g.vexs[i]; } int LocateVex(const Graph &g, VerTexType v) { //确定点v在G中的位置 for(int i = 0; i < g.vexnum; ++i) if(g.vexs[i] == v) return i; return -1; }//LocateVex int FirstAdjVex(const Graph &g, int v) { //返回v的第一个邻接点编号,没有返回-1 /****在此下面完成代码***************/ /***********************************/ }//FirstAdjVex int NextAdjVex(const Graph &g, int v, int w) { //返回v相对于w的下一个邻接点,没有返回-1 /****在此下面完成代码***************/ /***********************************/ }//NextAdjVex void CreateUDG(Graph &g) { //采用邻接矩阵表示法,创建无向图G /****在此下面完成代码***************/ /***********************************/ }//CreateUDN void DestroyUDG(Graph &g) { //you should do this } //输出邻接矩阵 void PrintUDG(const Graph& g) { int i, j; cout << " "; for(i = 0; i < g.vexnum; i++) { cout << setw(4) << g.vexs[i] ; } cout << endl; for(i = 0; i < g.vexnum; i++) { cout << setw(4) << g.vexs[i]; for(j = 0; j < g.vexnum; j++) { cout << setw(4) << g.arcs[i][j]; } cout << endl; } } int main() { Graph g; CreateUDG(g); //输出各个顶点的邻接点 for(int i = 0; i < g.vexnum; i++) { cout << Vertexdata(g, i) << ":"; for(int w = FirstAdjVex(g, i); w >= 0; w = NextAdjVex(g, i, w)) { cout << ' ' << Vertexdata(g, w); } cout << endl; } PrintUDG(g); DestroyUDG(g); return 0; }//mai来将这个代码补充完整
时间: 2023-06-29 15:10:54 浏览: 116
这段代码的作用是使用邻接矩阵表示法来创建无向图,并且实现了以下几个函数:
- Vertexdata: 返回顶点i的数据
- LocateVex: 确定点v在G中的位置
- FirstAdjVex: 返回v的第一个邻接点编号,没有返回-1
- NextAdjVex: 返回v相对于w的下一个邻接点,没有返回-1
- CreateUDG: 创建无向图G
- DestroyUDG: 销毁图G
- PrintUDG: 输出邻接矩阵
但是,在代码中有一些函数的实现是缺失的,需要你来完成。
这里提供一份完整的代码,你可以参考一下:
```
#include <iostream>
#include <iomanip>
#include <cstdio>
using namespace std;
#define MVNum 100 //最大顶点数
typedef string VerTexType; //假设顶点的数据类型为字符串
typedef int ArcType; //假设边的权值类型为整型
//------------图的邻接矩阵------------------
typedef struct {
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //图的当前点数和边数
} Graph;
//得到顶点i的数据
VerTexType Vertexdata(const Graph &g, int i) {
return g.vexs[i];
}
//确定点v在G中的位置
int LocateVex(const Graph &g, VerTexType v) {
for(int i = 0; i < g.vexnum; ++i)
if(g.vexs[i] == v)
return i;
return -1;
}
//返回v的第一个邻接点编号,没有返回-1
int FirstAdjVex(const Graph &g, int v) {
for(int i = 0; i < g.vexnum; ++i)
if(g.arcs[v][i] != 0)
return i;
return -1;
}
//返回v相对于w的下一个邻接点,没有返回-1
int NextAdjVex(const Graph &g, int v, int w) {
for(int i = w+1; i < g.vexnum; ++i)
if(g.arcs[v][i] != 0)
return i;
return -1;
}
//采用邻接矩阵表示法,创建无向图G
void CreateUDG(Graph &g) {
cin >> g.vexnum >> g.arcnum;
for(int i = 0; i < g.vexnum; ++i)
cin >> g.vexs[i];
for(int i = 0; i < g.vexnum; ++i)
for(int j = 0; j < g.vexnum; ++j)
g.arcs[i][j] = 0;
for(int i = 0; i < g.arcnum; ++i) {
int v1, v2;
cin >> v1 >> v2;
g.arcs[v1][v2] = 1;
g.arcs[v2][v1] = 1;
}
}
//销毁图G
void DestroyUDG(Graph &g) {
g.vexnum = g.arcnum = 0;
}
//输出邻接矩阵
void PrintUDG(const Graph& g) {
int i, j;
cout << " ";
for(i = 0; i < g.vexnum; i++) {
cout << setw(4) << g.vexs[i] ;
}
cout << endl;
for(i = 0; i < g.vexnum; i++) {
cout << setw(4) << g.vexs[i];
for(j = 0; j < g.vexnum; j++) {
cout << setw(4) << g.arcs[i][j];
}
cout << endl;
}
}
int main() {
Graph g;
CreateUDG(g);
//输出各个顶点的邻接点
for(int i = 0; i < g.vexnum; i++) {
cout << Vertexdata(g, i) << ":";
for(int w = FirstAdjVex(g, i); w >= 0; w = NextAdjVex(g, i, w)) {
cout << ' ' << Vertexdata(g, w);
}
cout << endl;
}
PrintUDG(g);
DestroyUDG(g);
return 0;
}
```