完善下列函数,#include<iostream> #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MVNum 100 //最大顶点数 using namespace std; typedef struct ArcNode {//边结点 int adjvex; //邻接点域:该边所指向的顶点的位置 int data; //数据域:存储和边相关的信息 …int DeleteVex(ALGragh &G) {//删除G中顶点f及其相关的弧 } int PrintGraph(ALGragh G) {//输出图G },要求如下:任务描述 给定一个无向图,在此无向图中删除一个顶点。 编程要求 输入 多组数据,每组m+2行。第一行有两个数字n和m,代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k,代表边依附的两个顶点。第m+2行有一个数字f,代表删除的顶点编号。当n和m都等于0时,输入结束。 输出 每组数据输出n-1行。为删除顶点后的邻接表。每两个数字之间用空格隔开。
时间: 2024-02-12 16:09:16 浏览: 80
这是一个删除图中顶点的问题,需要对邻接表进行修改。
首先,需要找到需要删除的顶点f,并删除其在邻接表中的所有边。然后,需要遍历整个邻接表,删除所有指向f的边。
具体实现可以参考以下代码:
```c++
#include<iostream>
#include<cstring>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100 //最大顶点数
using namespace std;
typedef struct ArcNode {//边结点
int adjvex; //邻接点域:该边所指向的顶点的位置
int data; //数据域:存储和边相关的信息
struct ArcNode *next; //链域:指向下一个邻接点
}ArcNode;
typedef struct VNode {//顶点结点
int data; //数据域:存储和顶点相关的信息
ArcNode *first; //链域:指向第一个邻接点
}VNode, AdjList[MVNum];
typedef struct {//邻接表结构
AdjList vertices; //邻接表
int vexnum, arcnum; //顶点数和边数
}ALGraph;
int LocateVex(ALGraph G, int f) {//查找顶点f在邻接表中的位置
for (int i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == f)
return i;
}
return -1;
}
int DeleteArc(ALGraph &G, int i, int j) {//删除G中顶点i和j之间的边
ArcNode *p = G.vertices[i].first, *q;
if (p == NULL)
return ERROR;
if (p->adjvex == j) {//第一个结点就是要删除的边
G.vertices[i].first = p->next;
delete p;
return OK;
}
while (p->next != NULL && p->next->adjvex != j)
p = p->next;
if (p->next == NULL)
return ERROR;
else {
q = p->next;
p->next = q->next;
delete q;
return OK;
}
}
int DeleteVex(ALGraph &G, int f) {//删除G中顶点f及其相关的弧
int i = LocateVex(G, f), j;
ArcNode *p, *q;
if (i == -1)
return ERROR;
while (G.vertices[i].first != NULL) {//删除从f出发的所有边
j = G.vertices[i].first->adjvex;
DeleteArc(G, i, j);
}
for (int k = 0; k < G.vexnum; k++) {//删除到f的所有边
p = G.vertices[k].first;
while (p != NULL) {
if (p->adjvex == i) {
if (p == G.vertices[k].first) {//第一个结点就是要删除的边
G.vertices[k].first = p->next;
delete p;
p = G.vertices[k].first;
}
else {
q->next = p->next;
delete p;
p = q->next;
}
}
else {
q = p;
p = p->next;
}
}
}
G.vertices[i].data = G.vertices[G.vexnum - 1].data;//将最后一个顶点覆盖到f的位置
G.vertices[i].first = G.vertices[G.vexnum - 1].first;
G.vexnum--;
return OK;
}
int PrintGraph(ALGraph G) {//输出图G
for (int i = 0; i < G.vexnum; i++) {
cout << G.vertices[i].data << " ";
ArcNode *p = G.vertices[i].first;
while (p != NULL) {
cout << p->adjvex + 1 << " ";
p = p->next;
}
cout << endl;
}
return OK;
}
int main() {
int n, m, h, k, f;
while (cin >> n >> m && n != 0 && m != 0) {
ALGraph G;
G.vexnum = n;
G.arcnum = m;
for (int i = 0; i < n; i++) {//建立邻接表
cin >> G.vertices[i].data;
G.vertices[i].first = NULL;
}
for (int i = 0; i < m; i++) {//添加边
cin >> h >> k;
ArcNode *p = new ArcNode;
p->adjvex = k - 1;
p->next = G.vertices[h - 1].first;
G.vertices[h - 1].first = p;
p = new ArcNode;
p->adjvex = h - 1;
p->next = G.vertices[k - 1].first;
G.vertices[k - 1].first = p;
}
cin >> f;
DeleteVex(G, f);
PrintGraph(G);
}
return 0;
}
```
注意:代码中的邻接表是无向图的邻接表,每条边需要在两个顶点之间建立。在输入边时,需要同时在两个顶点的邻接表中添加这条边。在输出时,顶点的编号从1开始,需要将其减1才能与数组下标对应。
阅读全文