完善下列函数,#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 18:09:09 浏览: 65
#include <malloc.h>
4星 · 用户满意度95%
以下是完善后的函数:
```c++
#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100 //最大顶点数
using namespace std;
typedef struct ArcNode {//边结点
int adjvex; //邻接点域:该边所指向的顶点的位置
int data; //数据域:存储和边相关的信息
…
}ArcNode;
typedef struct VNode {//头结点
int data; //数据域:存储顶点相关信息
ArcNode *firstarc; //指针域:指向第一条依附该顶点的边
}VNode, AdjList[MVNum];
typedef struct {//图
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;
int LocateVex(ALGraph G, int u) {//定位顶点u在邻接表中的位置
for (int i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == u) {
return i;
}
}
return -1;
}
int DeleteVex(ALGraph &G, int f) {//删除G中顶点f及其相关的弧
// 定位f在邻接表中的位置
int f_pos = LocateVex(G, f);
if (f_pos == -1) {
return ERROR;
}
// 删除顶点f及其相关的边
ArcNode *p, *q;
for (int i = 0; i < G.vexnum; i++) {
if (i == f_pos) { // 删除顶点f
continue;
}
p = G.vertices[i].firstarc;
if (p != NULL && p->adjvex == f_pos) { // 第一条边就是指向顶点f的
G.vertices[i].firstarc = p->nextarc; // 修改头结点指向的第一条边
free(p); // 释放p
continue;
}
while (p != NULL && p->adjvex != f_pos) { // 查找指向顶点f的边
q = p;
p = p->nextarc;
}
if (p != NULL) {
q->nextarc = p->nextarc; // 修改指向p的前一条边的nextarc
free(p); // 释放p
}
}
// 删除顶点f
for (int i = f_pos; i < G.vexnum - 1; i++) {
G.vertices[i] = G.vertices[i + 1];
}
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].firstarc;
while (p != NULL) {
cout << p->adjvex + 1 << " ";
p = p->nextarc;
}
cout << endl;
}
return OK;
}
int main() {
ALGraph G;
int n, m, h, k, f;
while (cin >> n >> m && n != 0 && m != 0) {
// 初始化邻接表
G.vexnum = n;
G.arcnum = m;
for (int i = 0; i < n; i++) {
G.vertices[i].data = i + 1;
G.vertices[i].firstarc = NULL;
}
// 插入边
for (int i = 0; i < m; i++) {
cin >> h >> k;
int h_pos = LocateVex(G, h);
int k_pos = LocateVex(G, k);
if (h_pos == -1 || k_pos == -1) {
cout << "ERROR" << endl;
return 0;
}
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = k_pos;
p->nextarc = G.vertices[h_pos].firstarc;
G.vertices[h_pos].firstarc = p;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = h_pos;
p->nextarc = G.vertices[k_pos].firstarc;
G.vertices[k_pos].firstarc = p;
}
// 删除顶点
cin >> f;
DeleteVex(G, f);
// 输出邻接表
PrintGraph(G);
}
return 0;
}
```
阅读全文