邻接多重表C++实现

邻接多重表是面向无向图的另一种链式存储结构，从边出发构建整个图，方便访问标记，删除边等操作，存储空间最少。易判断顶点之间的关系。

#include<iostream>
using namespace std;
const int maxnum = 100;
typedef struct edgeNode {
	int i;
	int j;
	struct edgeNode* ilink;
	struct edgeNode* jlink;
}edgeNode;
typedef struct vexNode {
	char data;
	edgeNode* firstedge;
}vexNode;
typedef struct {
	vexNode vexs[maxnum];
	int vexnum, edgenum;
}AMLGraph;
AMLGraph g;
int LocateVex(char c) {
	for (int i = 0; i < g.vexnum; i++)
	{
		if (g.vexs[i].data == c)
		{
			return i;
		}
	}
	return -1;
}
void insertedge(char a,char b) { //无向图a-b
	edgeNode* en = new edgeNode;
	en->ilink = NULL;
	en->jlink = NULL;
	int ai = LocateVex(a);
	int bi = LocateVex(b);
	en->i = ai;
	en->j = bi;
	edgeNode* curedge;
	//构建顶点a的同顶点边关系 
	if (g.vexs[ai].firstedge == NULL)
	{
		g.vexs[ai].firstedge = en;
	}
	else //(由于不知道顶点是在左边ilink还是右边jlink，所以需要进行一次查找)
	{
		curedge = g.vexs[ai].firstedge;
		while (curedge->i==ai&&curedge->ilink != NULL)
		{
			curedge = curedge->ilink;
		}
		while (curedge->j == ai && curedge->jlink != NULL)
		{
			curedge = curedge->jlink;
		}
		if (curedge->i == ai)
			curedge->ilink = en;
		else
			curedge->jlink = en;	
	}
	//构建顶点b的同顶点边关系
	if (g.vexs[bi].firstedge == NULL)
	{
		g.vexs[bi].firstedge = en;
	}
	else
	{
		curedge = g.vexs[bi].firstedge;
		while (curedge->i == bi && curedge->ilink != NULL)
		{
			curedge = curedge->ilink;
		}
		while (curedge->j == bi && curedge->jlink != NULL)
		{
			curedge = curedge->jlink;
		}
		if (curedge->i == bi)
			curedge->ilink = en;
		else
			curedge->jlink = en;
	}
}
void CreateAMLGraph() {
	cout << "输入需要的顶点数量和边数量:" << endl;
	cin >> g.vexnum >> g.edgenum;
	cout << "输入对应的顶点:" << endl;
	for (int i = 0; i < g.vexnum; i++)
	{
		cin >> g.vexs[i].data;
		g.vexs[i].firstedge = NULL;
	}
	cout << "输入对应的边:" << endl;
	for (int i = 0; i < g.edgenum; i++)
	{
		char a, b;
		cin >> a >> b;
		insertedge(a, b);
	}
}
void PrintAMLGraph() 
{
	for (int i = 0; i < g.vexnum; i++)
	{
		cout << g.vexs[i].data << " : ";
		edgeNode* curedge = g.vexs[i].firstedge;
		while (curedge != NULL)
		{
			cout << curedge->i << "-" << curedge->j << " ";
			if (curedge->i == i)
				curedge = curedge->ilink;
			else
				curedge = curedge->jlink;
		}
		cout << endl;
	}
}
int main() 
{
	CreateAMLGraph();
	PrintAMLGraph();
	return 0;
}