int InsertVex(ALGragh &G) {//在以邻接表形式存储的无向图G上插入顶点v /**************begin************/
时间: 2023-12-04 09:42:02 浏览: 45
以下是在以邻接表形式存储的无向图G上插入顶点v的代码实现:
```c
int InsertVex(ALGraph &G, VertexType v)
{
// 判断图是否已满
if (G.vexnum == MAX_VERTEX_NUM)
{
return ERROR;
}
// 在图中查找是否已存在该顶点
int i = LocateVex(G, v);
if (i != -1)
{
return ERROR;
}
// 在邻接表中增加新顶点
G.xlist[G.vexnum].data = v;
G.xlist[G.vexnum].firstin = NULL;
G.xlist[G.vexnum].firstout = NULL;
G.vexnum++;
return OK;
}
```
相关问题
int InsertVex(ALGragh &G) {//在以邻接表形式存储的无向图G上插入顶点v
插入顶点v的过程可以按照以下步骤进行:
1. 创建一个新的顶点节点,表示顶点v的信息。
2. 将新的顶点节点添加到邻接表的末尾,并将其指针设置为NULL。
3. 对于每个已有的顶点节点,创建一个新的邻接点节点,并将其指针设置为NULL。
4. 将新的邻接点节点添加到邻接表末尾,并将其指针设置为NULL。
5. 将新的邻接点节点添加到该顶点节点的邻接点列表的末尾。
6. 将该顶点节点的指针设置为新的邻接点节点。
7. 在无向图中,需要同时修改与该顶点相邻的其他顶点节点的邻接点列表,将新的邻接点节点添加到其末尾,并将其指针设置为新的顶点节点。
8. 最后,修改无向图的顶点数加1。
具体的代码实现如下:
```C++
int InsertVex(ALGraph &G, VertexType v)
{
if(G.vexnum == MAX_VERTEX_NUM) // 图的顶点数已经达到最大值
return ERROR;
G.vertices[G.vexnum].data = v; // 创建新的顶点节点
G.vertices[G.vexnum].firstarc = NULL;
// 初始化邻接点列表
for(int i = 0; i < G.vexnum; i++)
{
ArcNode *p = new ArcNode;
p->adjvex = G.vexnum;
p->nextarc = NULL;
// 将新的邻接点节点添加到该顶点节点的邻接点列表的末尾
ArcNode *q = G.vertices[i].firstarc;
if(q == NULL)
G.vertices[i].firstarc = p;
else
{
while(q->nextarc != NULL)
q = q->nextarc;
q->nextarc = p;
}
}
// 在无向图中,需要同时修改与该顶点相邻的其他顶点节点的邻接点列表
ArcNode *p = new ArcNode;
p->adjvex = G.vexnum;
p->nextarc = NULL;
ArcNode *q = G.vertices[G.vexnum-1].firstarc;
if(q == NULL)
G.vertices[G.vexnum-1].firstarc = p;
else
{
while(q->nextarc != NULL)
q = q->nextarc;
q->nextarc = p;
}
G.vexnum++; // 修改顶点数加1
return OK;
}
```
其中,ALGraph 是邻接表存储结构的图类型,VertexType 是顶点数据类型。在这里,我们假设邻接表存储结构中的顶点节点和邻接点节点的数据类型分别为:
```C++
typedef struct ArcNode { // 邻接点
int adjvex; // 邻接点的位置
ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode { // 顶点
VertexType data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的当前顶点数和边数
} ALGraph;
```
#include<iostream> #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MVNum 100 //最大顶点数 using namespace std; typedef struct ArcNode {//边结点 int adjvex; //邻接点域:该边所指向的顶点的位置 int data; //数据域:存储和边相关的信息 struct ArcNode* nextarc; //链域:指向下一条边的指针 }ArcNode; typedef struct VNode {//顶点信息 int data; //顶点结点的数据域 ArcNode *firstarc; //链域:指向第一条依附该顶点的边的指针 }VNode,AdjList[MVNum]; //AdjList表示邻接表类型 typedef struct {//邻接表 AdjList vertices; int vexnum,arcnum; //图的当前顶点数和边数 }ALGragh; int CreateUDG(ALGragh &G,int vexnum,int arcnum) {//采用邻接表表示法,创建无向图G } int InsertVex(ALGragh &G) {//在以邻接表形式存储的无向图G上插入顶点v } int PrintGraph(ALGragh G) {//输出图G }补全代码
下面是补全代码的示例:
```
#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100 //最大顶点数
using namespace std;
typedef struct ArcNode {//边结点
int adjvex; //邻接点域:该边所指向的顶点的位置
int data; //数据域:存储和边相关的信息
struct ArcNode* nextarc; //链域:指向下一条边的指针
}ArcNode;
typedef struct VNode {//顶点信息
int data; //顶点结点的数据域
ArcNode *firstarc; //链域:指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct {//邻接表
AdjList vertices;
int vexnum,arcnum; //图的当前顶点数和边数
}ALGragh;
int CreateUDG(ALGragh &G,int vexnum,int arcnum) {//采用邻接表表示法,创建无向图G
G.vexnum = vexnum;
G.arcnum = arcnum;
for(int i=0;i<G.vexnum;i++){
G.vertices[i].data = i+1; //顶点信息
G.vertices[i].firstarc = NULL; //边表头指针
}
for(int k=1;k<=G.arcnum;k++){
int i,j;
cout << "请输入第" << k << "条边的两个顶点的编号(空格分隔):" << endl;
cin >> i >> j;
//插入边<i,j>
ArcNode *p = new ArcNode;
p->adjvex = j-1;
p->nextarc = G.vertices[i-1].firstarc;
G.vertices[i-1].firstarc = p;
//插入边<j,i>
ArcNode *q = new ArcNode;
q->adjvex = i-1;
q->nextarc = G.vertices[j-1].firstarc;
G.vertices[j-1].firstarc = q;
}
return OK;
}
int InsertVex(ALGragh &G) {//在以邻接表形式存储的无向图G上插入顶点v
if(G.vexnum == MVNum){
cout << "图的顶点数已达到最大值,无法插入!" << endl;
return ERROR;
}
G.vexnum++;
G.vertices[G.vexnum-1].data = G.vexnum;
G.vertices[G.vexnum-1].firstarc = NULL; //边表头指针
return OK;
}
int PrintGraph(ALGragh G) {//输出图G
cout << "图的邻接表表示如下:" << endl;
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 << "NULL" << endl;
}
return OK;
}
int main(){
ALGragh G;
int vexnum,arcnum;
cout << "请输入无向图的顶点数和边数(空格分隔):" << endl;
cin >> vexnum >> arcnum;
CreateUDG(G,vexnum,arcnum);
PrintGraph(G);
InsertVex(G);
PrintGraph(G);
return 0;
}
```
其中,CreateUDG函数用于创建无向图,InsertVex函数用于在无向图中插入新的顶点,PrintGraph函数用于输出无向图的邻接表表示。