青岛大学王卓老师数据结构——C++实现邻接表表示法创建无向图

#include <iostream>
using namespace std;
#include <string>
#define MVNum 100
//最大顶点数
//顶点的节点结构
typedef struct VNode
{
string data;
//顶点信息
ArcNode *firstarc;
//指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];
//AdjList v;相当于VNode v[MVNum];
//弧（边）的节点结构
typedef struct ArcNode
{
int adjvex;
//该边所指向的顶点位置
struct ArcNode *nextarc;
//指向下一条边的指针
}ArcNode;
//图的结构定义
typedef struct ALGraphy
{
AdjList vertices;
//图中所包含的顶点
int vexnum, arcnum; //图的当前顶点数和弧数
}ALGraphy;
//邻接表表示法创建无向网图
int CreateUDG(ALGraphy &G)
{
cin >> G.vexnum >> G.arcnum;
//输入总顶点数，总边数
for (int i = 0; i < G.vexnum; i++)
//构造表头节点表
{
cin >> G.vertices[i].data;
//输入顶点值;
G.vertices[i].firstarc = NULL;
//初始化表头节点指针域
}
for (int k = 0; k < G.arcnum; k++)
//构造邻接表
{
string v1, v2;
int
i, j;
cin >> v1 >> v2;
//输入边所依附的两个顶点，例如ab边
i = LocateVex(G, v1);
//找出ab顶点在图中所存储的下标位置，并将其赋值给ij，以便下一步进行插入
j = LocateVex(G, v2);
ArcNode *p1 = new ArcNode;
ArcNode *p2 = new ArcNode;
//创建两个新的边节点；
p1->adjvex = j;
//邻接点序号
p1->nextarc = G.vertices[i].firstarc; //头插法
G.vertices[i].firstarc = p1;
//头插法将新节点插入顶点的边表头部
//因为所创建的是无向图，所以ab边也是ba边，故需要将ba边进行插入，如果是有向图，则可以省略这一步
p2->adjvex = i;
p2->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p2;
}
return 0;
}
//在图G中查找顶点u，找到则返回u在顶点表中的下标
int LocateVex(ALGraphy G, string u)
{
int i;
for (i = 0; i < G.vexnum; i++)
{
if (u == G.vertices[i].data)return i;
}
return -1;
}

最后

以上就是单纯橘子为你收集整理的青岛大学王卓老师数据结构——C++实现邻接表表示法创建无向图的全部内容，希望文章能够帮你解决青岛大学王卓老师数据结构——C++实现邻接表表示法创建无向图所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。