#include<iostream>
using namespace std;
const int MVN = 21;
typedef char VexType;//顶点元素类型
typedef struct ArcNode
{
	int adjvex;//弧指向的顶点位置
	int adj;//权
	ArcNode *nextarc;//指向下一条弧的顶点
}*ArcPtr;
struct VexNode
{
	VexType data;//顶点数据
	ArcPtr firstarc;//指向第一条依附于该顶点的弧
	bool visited;//是否被访问过
};
struct ALGraph
{
	VexNode vexs[MVN];
	int kind, vexnum, arcnum;//类型，顶点数，弧数
};
int LocateVex(ALGraph &G, VexType v);//查找顶点
bool InsertArc(ALGraph &G, VexType u, VexType v, int w = 1);//插入弧
void CreateGraph(ALGraph &G, int Kind, char v[]);
void GraphPrint(ALGraph &G);
int Outdegree(ALGraph &G, VexType u);//求一个顶点的出度
int Indegree(ALGraph &G, VexType u);//求一个顶点的入度
int* degree(ALGraph &G);//求全部顶点的入度

int main()
{
	char g[] = "sbcd#sbscsdbcbdcd#";
	cout << "序列为 "<< endl<<g<< endl;
	int Kind = 1;
	ALGraph G;
	CreateGraph(G, Kind, g);
	GraphPrint(G);
	VexType u = 's';
	int n = Outdegree(G, u);
	cout << "顶点"<<u<<"的出度为" << n << endl;
	VexType v = 'c';
	int m = Indegree(G, v);
	cout << "顶点"<<v<<"的入度为" << m << endl;
	int *a = degree(G);
	cout << "各个顶点的入度依次为:";
	for (int j = 1; j <= G.vexnum; j++)
	{
		cout << a[j] << "  ";
	}
	cout << endl;

	return 0;
}
int LocateVex(ALGraph &G, VexType v)
{
	int i;
	for (i = G.vexnum; i>0 && G.vexs[i].data != v; i--);
	return i;
}
bool InsertArc(ALGraph &G, VexType u, VexType v, int w )
{
	ArcPtr p;
	int i, j;
	bool found;
	i = LocateVex(G, u);
	if (i == 0)
	{
		return false;
	}
	j = LocateVex(G, v);
	if (j == 0 || j == i)
	{
		return false;
	}
	for (found = false, p = G.vexs[i].firstarc; p && !found; p = p->nextarc)
	{
		if (p->adjvex == j)
		{
			found = true;
		}
	}
	if (found)
	{
		return false;
	}
	G.arcnum++;
	p = new ArcNode;
	p->adjvex = j;
	p->adj = w;
	p->nextarc = G.vexs[i].firstarc;
	G.vexs[i].firstarc = p;
	if (G.kind <= 2)
	{
		return true;
	}
	G.arcnum++;
	p = new ArcNode;
	p->adjvex = i;
	p->adj = w;
	p->nextarc = G.vexs[j].firstarc;
	G.vexs[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.vexs[i].data = v[i - 1];
		G.vexs[i].firstarc = NULL;
	}
	G.vexnum = 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 << "邻接表" << endl;
	for (int i = 1; i <= G.vexnum; i++)
	{
		cout << G.vexs[i].data;
		for (p = G.vexs[i].firstarc; p; p = p->nextarc)
		{
			cout << "->" << p->adjvex;
		}
		cout << endl;
	}
}
int Outdegree(ALGraph &G, VexType u)
{
	int i = LocateVex(G, u);
	int n = 0;
	ArcPtr p;
	for (p = G.vexs[i].firstarc; p; p = p->nextarc)
	{
		n++;
	}
	return n;
}
int Indegree(ALGraph &G, VexType u)
{
	int i = LocateVex(G, u);
	int n = 0;
	ArcPtr p;
	for (int j = 1; j <= G.vexnum; j++)
	{
		if (j == i)
		{
			continue;
		}
		for (p = G.vexs[j].firstarc; p; p = p->nextarc)
		{
			if (p->adjvex == i)
			{
				n++;
				break;
			}

		}
	}
	return n;
}
int* degree(ALGraph &G)
{
	int *a;
	a = new int[G.vexnum + 1];
	for (int i = 1; i <= G.vexnum; i++)
	{
		a[i] = 0;
	}
	ArcPtr p;
	for (int j = 1; j <= G.vexnum; j++)
	{
		for (p = G.vexs[j].firstarc; p; p = p->nextarc)
		{
			a[p->adjvex]++;
		}
	}
	return a;
}