按照注释中的要求,完善下列函数#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 }
时间: 2024-02-29 11:51:42 浏览: 61
由于函数中用到了ALGraph这个结构体,我们需要先定义ALGraph:
```
typedef struct ArcNode {//边结点
int adjvex; //邻接点域:该边所指向的顶点的位置
int data; //数据域:存储和边相关的信息
struct ArcNode *next; //链域,指向下一个邻接点
}ArcNode;
typedef struct VNode {//顶点结点
int data; //数据域:存储和顶点相关的信息
ArcNode *first; //链域,指向第一条依附该顶点的边
}VNode,ALGraph[MVNum];//ALGraph是邻接表类型
```
接下来,我们可以写出函数体:
```
int LocateVex(ALGraph G, int f) {//查找顶点f在G中的位置
for (int i = 0; i < G.vexnum; ++i) {
if (G.vertices[i].data == f) {
return i;
}
}
return -1;
}
int DeleteVex(ALGraph &G, int f) {//删除G中顶点f及其相关的弧
int k = LocateVex(G, f);
if (k == -1) {
return ERROR;
}
//删除以f为头的所有边
ArcNode *p = G.vertices[k].first, *q;
while (p != NULL) {
q = p;
p = p->next;
delete q;
}
//删除以f为尾的所有边
for (int i = 0; i < G.vexnum; ++i) {
if (i != k) {
p = G.vertices[i].first;
while (p != NULL && p->adjvex != k) {
q = p;
p = p->next;
}
if (p != NULL) {
q->next = p->next;
delete p;
}
}
}
//删除f顶点
for (int i = k + 1; i < G.vexnum; ++i) {
G.vertices[i - 1] = G.vertices[i];
}
--G.vexnum;
//删除以f为头的边
p = G.vertices[k].first;
while (p != NULL) {
q = p;
p = p->next;
delete q;
}
G.vertices[k].first = NULL;
//删除以f为尾的边
for (int i = 0; i < G.vexnum; ++i) {
p = G.vertices[i].first;
while (p != NULL) {
if (p->adjvex == k) {
q = p;
p = p->next;
delete q;
}
else {
p = p->next;
}
}
}
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 << "(" << p->data << ")" << "->";
p = p->next;
}
cout << "NULL" << endl;
}
return OK;
}
```
其中,LocateVex函数是用来查找顶点f在G中的位置的,DeleteVex函数是用来删除G中顶点f及其相关的弧的,PrintGraph函数是用来输出图G的。注意在删除顶点f时,我们需要分别删除以f为头的边和以f为尾的边,以及顶点f本身。
阅读全文