“”数据结构与算法”平时测验四

“”数据结构与算法”平时测验四

“数据结构与算法”平时测验四
假设无向、非加权图的数据元素为字符，采用邻接表存储结构。图的创建、存储结构输出等大部分操作的实现代码操作已经给出，请分别补充写出操作插入边、删除边的实现函数代码。

有关说明：

（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

输出如下：

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:

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

```cpp```cpp
#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;}

答案：

```cpp
int GetLoc(Graphlnk g,VertexType v)
{for(int i=0;i<=g.VexNum-1;i++){if(g.Nodetable[i].vertex==v){return i;}}return -1;
}int Insert_Edge(Graphlnk &g,VertexType vi, VertexType vj)
{int vii=GetLoc(g,vi),vjj=GetLoc(g,vj);if(vii==-1||vjj==-1) return -1;EdgeNode *p,*q;p=g.Nodetable[vii].link;while(p!=NULL){if(p->adjvex==vjj){return 0;}p=p->next;}p=(struct  EdgeNode *)malloc(sizeof(struct  EdgeNode));p->adjvex=vii;p->next=g.Nodetable[vjj].link;g.Nodetable[vjj].link=p;q=(struct  EdgeNode *)malloc(sizeof(struct  EdgeNode));q->adjvex=vjj;q->next=g.Nodetable[vii].link;g.Nodetable[vii].link=q;return 1;}int Delete_Edge(Graphlnk &g,VertexType vi,VertexType vj)
{int vii=GetLoc(g,vi),vjj=GetLoc(g,vj);if(vii==-1||vjj==-1) return -1;EdgeNode *p,*q;int flag=0;p=g.Nodetable[vii].link;while(p!=NULL){if(p->adjvex==vjj){flag=1;break;}p=p->next;}if(!flag) return 0;p=g.Nodetable[vii].link;if(p->adjvex==vjj){g.Nodetable[vii].link=p->next;}else{p=g.Nodetable[vii].link;while(p->next!=NULL){if(p->next->adjvex==vjj){p->next=p->next->next;break;}p=p->next;}}q=g.Nodetable[vjj].link;if(q->adjvex==vii){g.Nodetable[vjj].link=q->next;}else{q=g.Nodetable[vjj].link;while(q->next!=NULL){if(q->next->adjvex==vii){q->next=q ->next->next;break;}q=q->next;}}return 1;}