#include<iostream>
using namespace std;
const int MVN = 21;
typedef char VeuType;//顶点元素类型
typedef struct ArcNode
{
	int adjveu;//弧指向的顶点位置
	int adj;//权
	ArcNode *neutarc;//指向下一条弧的顶点
}*ArcPtr;
struct VeuNode
{
	VeuType data;//顶点数据
	ArcPtr firstarc;//指向第一条依附于该顶点的弧
	bool visited;//是否被访问过
};
struct ALGraph
{
	VeuNode veus[MVN];
	int kind, veunum, arcnum;//类型，顶点数，弧数
};
int LocateVeu(ALGraph &G, VeuType v);//在图G中查找顶点
bool InsertArc(ALGraph &G, VeuType u, VeuType v, int w = 1);
void CreateGraph(ALGraph &G, int Kind, char v[]);
void GraphPrint(ALGraph &G);
bool insertdian(ALGraph &G, VeuType u);//插入一个顶点
bool DeleteHu(ALGraph &G, VeuType u, VeuType v);//删除一条弧
bool Deletedian(ALGraph &G, VeuType u);
int main()
{
	char g[] = "sacd#sascsdacadcd#";
	cout << "原始序列为 "<< endl<<g <<endl;
	int Kind = 1;
	ALGraph G;
	CreateGraph(G, Kind, g);
	GraphPrint(G);
	VeuType v = 'c';
	Deletedian(G, v);
	cout << "删除顶点" <<v<< endl;
	GraphPrint(G);
	VeuType u = 'e';
	insertdian(G, u);
	cout << "插入顶点" <<u<< endl;
	GraphPrint(G);
	VeuType v1 = 's';
	VeuType v2 = 'a';
	cout << "删除弧<"<<v1<<","<<v2<<">" << endl;
	DeleteHu(G, v1, v2);
	GraphPrint(G);
	return 0;
}

int LocateVeu(ALGraph &G, VeuType v)
{
	int i;
	for (i = G.veunum; i > 0 && G.veus[i].data != v; i--);
	return i;
}
bool InsertArc(ALGraph &G, VeuType u, VeuType v, int w )
{
	ArcPtr p;
	int i, j;
	bool found;
	i = LocateVeu(G, u);
	if (i == 0)
	{
		return false;
	}
	j = LocateVeu(G, v);
	if (j == 0 || j == i)
	{
		return false;
	}
	for (found = false, p = G.veus[i].firstarc; p && !found; p = p->neutarc)//若弧存在，插入失败
	{
		if (p->adjveu == j)
		{
			found = true;
		}
	}
	if (found)
	{
		return false;
	}
	G.arcnum++;
	p = new ArcNode;
	p->adjveu = j;
	p->adj = w;
	p->neutarc = G.veus[i].firstarc;
	G.veus[i].firstarc = p;//表头插入弧，假设对弧的次序无要求
	if (G.kind <= 2)
	{
		return true;
	}
	G.arcnum++;
	p = new ArcNode;
	p->adjveu = i;
	p->adj = w;
	p->neutarc = G.veus[j].firstarc;
	G.veus[j].firstarc = p;
	return true;
}
void CreateGraph(ALGraph &G, int Kind, char v[])
{
	int i, w;
	G.kind = Kind;
	G.arcnum = 0;
	i = 0;
	while (true)
	{
		if (v[i] == '#')
		{
			break;
		}
		i++;
		G.veus[i].data = v[i - 1];
		G.veus[i].firstarc = NULL;
	}
	G.veunum = i;
	i++;
	while (true)
	{
		if (v[i] == '#')
		{
			break;
		}
		if (G.kind == 1 || G.kind == 3)
		{
			w = 1;
		}
		else
		{
			w = v[i + 2] - 48;
		}
		InsertArc(G, v[i], v[i + 1], w);
		i = i + 2;
		if (w == 2 || w == 4)
		{
			i++;
		}
	}
	
}
void GraphPrint(ALGraph &G)
{
	ArcPtr p;
	cout << "顶点数：" << G.veunum << "       " << "弧数：" << G.arcnum << endl;;
	cout << "邻接表" << endl;
	for (int i = 1; i <= G.veunum; i++)
	{
		cout << G.veus[i].data;
		for (p = G.veus[i].firstarc; p; p = p->neutarc)
		{
			cout << "->" << p->adjveu;
		}
		cout << endl;
		
	}
}
bool insertdian(ALGraph &G, VeuType u)
{
	int i;
	i = LocateVeu(G, u);
	if (i != 0)
	{
		return false;
	}
	G.veunum++;
	G.veus[G.veunum].data = u;
	G.veus[G.veunum].firstarc = NULL;
	return true;
}
bool DeleteHu(ALGraph &G, VeuType u, VeuType v)
{
	ArcPtr p,q; int i, j; bool found;
	i = LocateVeu(G, u);
	if (i == 0) return false;
	j = LocateVeu(G, v); 
	if (j == 0 || j == i)return false;
	found = false;
	p = NULL;
	q = G.veus[i].firstarc;
	while (q && !found)
	{
		if (q->adjveu == j)found = true;
		else {
			p = q;
			q = q->neutarc;
		}
	}
	if (!found)return false;//没有该弧
	if (p) p->neutarc = q->neutarc;
	else G.veus[i].firstarc = q->neutarc;
	
	delete q; G.arcnum--;
	if (G.kind <= 2) return true;
	//无向图的情况
	found = false;           
	p = NULL;
	q = G.veus[j].firstarc;
	while (q && !found)
	{
		if (q->adjveu == i)found = true;
		else {
			p = q;
			q = q->neutarc;
		}
	}
	if (p) p->neutarc = q->neutarc;
	else G.veus[j].firstarc = q->neutarc;
	delete q;
	G.arcnum--;
	return true;
	
}
bool Deletedian(ALGraph &G, VeuType u)
{
	ArcPtr p, q; int i,j; bool found;
	i = LocateVeu(G, u);
	if (i == 0) return false;
	
	//删除出弧，弧数对应减少
	p = G.veus[i].firstarc;
	while (p)
	{
		q = p;
		p = p->neutarc;
		delete q;
		G.arcnum--;
	}
	//删除入弧,弧数对应减少
	for ( j = 1; j <= G.veunum; j++)
	{
		if (j != i)
		{
			found = false;
			p = NULL;
			q = G.veus[j].firstarc;
			while (q && !found)
			{
				if (q->adjveu == i) found = true;
				else
				{
					p = q;
					q = q->neutarc;
				}
			}
			if (!found)
				continue;
			if (p)
				p->neutarc = q->neutarc;
			else
				G.veus[j].firstarc = q->neutarc;
			delete q;
			G.arcnum--;
		}
	}
	G.veus[i] = G.veus[G.veunum];
	for ( j = 1; j <= G.veunum; j++)
	{
		
		for (p= G.veus[j].firstarc;p;p=p->neutarc)
		{
			if (p->adjveu == G.veunum)
			{
				p->adjveu = i;
				break;
			}
		} 
	}
	G.veunum--;
	return true;
	
}