数据结构和算法（图结构）

数据结构和算法（图结构）"/>

数据结构和算法（图结构）

假设无向、非加权图的数据元素为字符，采用邻接表存储结构。图的创建、存储结构输出等大部分操作的实现代码操作已经给出，请分别补充写出操作插入边、删除边的实现函数代码。
有关说明：
（1）插入边， int Insert_Edge(g,vi,vj)
输入：图g，要插入边的两个顶点元素vi，vj；
输出：返回插入的状态（成功、错误：边顶点不存在、错误：边重复），根据不同的状态会输出：
Error:Vertex does not exist! 或
Error:Edge repetition! 或
Edge insertion succeeded!
注：为了统一，邻接点链入链表时，链入在前面（表头位置）
（2）删除边， int Delete_Edge(g,vi,vj)
输入：图g，要删除边的两个顶点元素vi，vj；
输出：返回删除的状态（成功、错误：边顶点不存在、错误：边不存在），根据不同的状态会输出：
Error:Vertex does not exist!
Error:Edge does not exist!
Edge deletion succeeded!
（3）主函数中操作的控制： 1—创建图 2—输出图的存储结构 3—插入边 4—删除边 0—退出
创建图时，需要输入顶点个数、各个顶点元素、各条边，具体见样例；
输出存储结构时，输出格式见样例；
插入或删除边时，需要输入边的两个顶点元素；
例如：
1 //创建图操作
5 //图顶点的个数
abcde //顶点元素
** //输入边，**表示边输入结束
2 //输出图结构操作
3 //插入边操作
ab //边顶点
3
bc
4 //删除边操作
de
2
0
输入

1
5
abcde
**
2
3
ab
3
bc
4
de
2
0

输出

Adjacency List is:
a:
b:
c:
d:
e:
Edge insertion succeeded!
Edge insertion succeeded!
Error:Edge does not exist!
Adjacency List is:
a:-->b
b:-->c-->a
c:-->b
d:
e:

给出的代码如下： （请注意要求补充的函数的注释说明）

#define _CRT_SECURE_NO_WARNINGS

#include < iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

#define Max_VertexNum 50 //允许图的顶点个数的最大值

typedef char VertexType; //定义数据元素(顶点)类型为char

//********************************************************************************

//邻接表存储结构

struct EdgeNode //定义边存储结点

{ int adjvex; //邻接点的存储位置

EdgeNode *next; //指向下邻接点

};

struct VertexNode //定义顶点存储结点

{ VertexType vertex; //数据元素

struct EdgeNode *link; //第一个邻接点

};

typedef struct Graph //定义邻接表图结构

{ int VexNum; //图的顶点个数

VertexNode Nodetable[Max_VertexNum]; //一维数组-邻接表

} Graphlnk; //定义邻接表存储的图类型

//**********************************************************************************

// 基于邻接表存储的 无向、非加权图的各种操作的实现

//** 创建图

void create_graph(Graphlnk &g)

{ VertexType v1, v2;

int i, j;

struct EdgeNode *p, *q;

cin >> g.VexNum; //读入图的顶点个数

while (g.VexNum < 0)

cin >> g.VexNum;
for (i = 0; i < g.VexNum ; i++)
{ cin >> g.Nodetable[i].vertex; //输入顶点元素

g.Nodetable[i].link = NULL; //邻接表初始化

}

cin >> v1 >> v2; //输入边的两个顶点

while (v1 != ‘’&&v2 != '’)

{ for (i = 0; i < g.VexNum; i++)

if (g.Nodetable[i].vertex == v1) break;

for (j = 0; j < g.VexNum; j++)

if (g.Nodetable[j].vertex == v2) break;

if (i >= g.VexNum || j >= g.VexNum) cin >> v1 >> v2;
//边顶点不正确，重新读

else //链入邻接点

{ p = (struct EdgeNode *)malloc(sizeof(struct EdgeNode));

p->adjvex = j;

p->next = g.Nodetable[i].link;

g.Nodetable[i].link = p;

q = (struct EdgeNode *)malloc(sizeof(struct EdgeNode));

q->adjvex = i;

q->next = g.Nodetable[j].link;

g.Nodetable[j].link = q;

cin >> v1 >> v2;

}

}

}

void print_graph(Graphlnk g)

{ int i;

struct EdgeNode *p;

cout << “Adjacency List is:” << endl;

for (i = 0; i < g.VexNum; i++)

{ cout << g.Nodetable[i].vertex << “:”;

p = g.Nodetable[i].link;

while (p != NULL)

{ cout << “–>” << g.Nodetable[p->adjvex].vertex;

p = p->next;

}

cout << endl;

}

}

//**********************************************************************
补充 插入边、删除边的函数
//**********************************************************************

int main()

{ Graphlnk g;

int ic;

VertexType vi, vj;

int k;

while (1)

{ //请输入要执行的操作:";

cin >> ic;

while (ic < 0 || ic>4)

cin >> ic;

if (ic == 1) create_graph(g); //创建图

if (ic == 2) print_graph(g); //输出图结构

if (ic == 3) //插入边

{ cin >> vi >> vj;

k = Insert_Edge(g, vi, vj);

if (k == -1) cout << “Error:Vertex does not exist!” << endl;

if(k==0) cout << “Error:Edge repetition!” << endl;

if(k==1) cout << “Edge insertion succeeded!” << endl;

}

if (ic == 4) //删除边

{ cin >> vi >> vj;

k = Delete_Edge(g, vi, vj);

if (k == -1) cout << “Error:Vertex does not exist!.” << endl;

if (k == 0) cout << “Error:Edge does not exist!” << endl;

if (k == 1) cout << “Edge deletion succeeded!” << endl;

}

if (ic == 0) break;

}

return 0;

}

使用结点前一定要new一个结点！
使用结点前一定要new一个结点！
使用结点前一定要new一个结点！

int f(Graphlnk&g,char u)
{for(int i=0;i<g.VexNum;i++){if(g.Nodetable[i].vertex==u)return i;}return -1;
}
int Insert_Edge(Graphlnk&g,char u,char v)
{if(f(g,u)==-1)return -1;//结点超出范围if(f(g,v)==-1)return -1;int f1=f(g,u),f2=f(g,v);EdgeNode*t=new EdgeNode;t=g.Nodetable[f1].link;while(t!=NULL){if(t->adjvex==f2)return 0;//要插入的边已存在，不能重复插入t=t->next;}t=g.Nodetable[f2].link;while(t!=NULL){if(t->adjvex==f1)return 0;//要插入的边已存在，不能重复插入t=t->next;}EdgeNode*t1=new EdgeNode;//无向图插入一对边t1->adjvex=f2;t1->next=g.Nodetable[f1].link;g.Nodetable[f1].link=t1;EdgeNode*t2=new EdgeNode;t2->adjvex=f1;t2->next=g.Nodetable[f2].link;g.Nodetable[f2].link=t2;return 1;
}
int Delete_Edge(Graphlnk&g,char u,char v)
{if(f(g,u)==-1)return -1;if(f(g,v)==-1)return -1;//结点超出范围int f1=f(g,u),f2=f(g,v);EdgeNode*t=new EdgeNode;t=g.Nodetable[f1].link;int f3=-1,f4=-1;while(t!=NULL){if(t->adjvex==f2)f3=0;t=t->next;}if(f3==-1)return 0;//要删除的边不存在t=g.Nodetable[f2].link;while(t!=NULL){if(t->adjvex==f1)f4=0;t=t->next;}if(f4==-1)return 0;//要删除的边不存在EdgeNode*t1=new EdgeNode;EdgeNode*last;t1=g.Nodetable[f1].link;EdgeNode*t2=new EdgeNode;t2=g.Nodetable[f2].link;last=t1;//设置一个指向当前结点的前一结点的指针，如果不设置的话你会发现无法删除最后一个结点（需要再遍历链表，费时间，不推荐）while(t1!=NULL&&t1->adjvex!=f2){last=t1;t1=t1->next;}if(last==t1)//第一个结点就是要删除的边所在结点{g.Nodetable[f1].link=t1->next;delete t1;}else//这种情况下last指针始终指向t1指针指向的结点的前一个结点{last->next=t1->next;delete t1;}last=t2;//设置一个指向当前结点的前一结点的指针，如果不设置的话你会发现无法删除最后一个结点（需要再遍历链表，费时间，不推荐）while(t2!=NULL&&t2->adjvex!=f1){last=t2;t2=t2->next;}if(last==t2)//第一个结点就是要删除的边所在结点{g.Nodetable[f2].link=t2->next;delete t2;}else//这种情况下last指针始终指向t2指针指向的结点的前一个结点{last->next=t2->next;delete t2;}return 1;
}