//用結構體定義鄰接表中邊的信息
struct Edge
{
	int dist;//下標
	WType weight;//權值
	Edge *next;//指向下一個領接邊的指針
	Edge(){};
	Edge(int n,WType w)//構造函數
	{
		dist=n;
		weight=w;
		next=NULL;
	}
};
//定義結點信息
struct VerticeType
{
	VerType data;//結點內容
	Edge*firstAdj;//第一條鄰接邊
};
class AdjList
{
private:	
	VerticeType Vertice[MaxNode];//MaxNode為定義的最大結點數
	int numOfVertice;//結點數目
	int numOfEdge;//邊數
	int typeFlag;//區分有向圖還是無向圖，定義0為無向圖，1 為有向圖
public:
	AdjList(int flag=0);//構造函數
	~AdjList(void);//析構函數
	int AdjListEmpty()//鄰接表判空
	{
		return (numOfVertice==0);
	}
	int AdjListFull()//鄰接表判滿
	{
		return(numOfVertice==MaxNode);
	}
	int NumOfVer()
	{
		return numOfVertice;
	}
	int NumOfEdge()
	{
		return numOfEdge;
	}
	VerType GetItem(const int i);//獲取序號為i的結點內容
	WType GetWeight(int v1,int v2);//獲取邊<v1,v2>的權
	void InsertVertice(VerType item);//插入一個結點
	void InsertEdge(int v1,int v2,WType w);//插入邊<v1,v2>權值為w
	void DeleteVertice(int v);//刪除下標為v的結點
	void DeleteEdge(int v1,int v2);//刪除邊<v1,v2>
	int GetFirstNeighbor(const int v);//返回結點v第一條相鄰邊的下標，無相鄰邊返回-1
	int GetNextNeighbor(const int v1,const int v2);//返回結點v1除了<v1,v2>下一條鄰接邊的結點下標，無則返回-1
	void DepthFirstSearch(const int v,int visited[],void visit(VerType item));//從結點v開始深度優先遍歷連通圖
	void BroadFirstSearch(const int v,int visited[],void visit(VerType item));//從結點v開始廣度優先遍歷連通圖
	void DepthFirstSearch(void visit(VerType item));//從結點v開始深度優先遍歷非連通圖
	void BroadFirstSearch(void visit(VerType item));//從結點v開始廣度優先遍歷非連通圖
	Edge*GetAdj(int v);//獲得指向序號v的結點的第一鄰接邊的指針
	
};
AdjList::AdjList(int flag)
{
	typeFlag=flag;
	for(int i=0;i<MaxNode;i++)
		Vertice[i].firstAdj=NULL;
	numOfVertice=0;
	numOfEdge=0;
}
AdjList::~AdjList(void)
{
	for(int i=0;i<numOfVertice;i++)
	{
		Edge*p,*q;
		p=Vertice[i].firstAdj;
		while(p)
		{
			q=p->next;
			delete p;
			p=q;
		}
	}
}
VerType AdjList:: GetItem(const int i)//獲取序號為i的結點內容
	{
		if (i<0||i>=numOfVertice)
		{
			cout<<"結點序號i有誤！";
			exit(0);
		}
		return Vertice[i].data;
	}
	WType AdjList:: GetWeight(int v1,int v2)//獲取邊<v1,v2>的權
	{
		if(v1<0||v1>=numOfVertice||v2<0||v2>=numOfVertice)
		{
			cout<<"v1和v2的值不合法，無法找到邊<v1,v2>的權";
				exit(0);
		}
		Edge*first;
		first=Vertice[v1].firstAdj;
		while(first->next!=NULL && first->dist!=v2)
		{
			first=first->next;
		}
		if(first->dist==v2)
			return first->weight;
		else
		{
			cout<<"邊<v1,v2>的權不存在";
			exit(0);
		}
	}
void AdjList::InsertVertice(VerType item)
{
	if(AdjListFull())
	{
		cout<<"鄰接表已滿，無法插入新的頂點";
		exit(0);
	}
	Vertice[numOfVertice++].data=item;
}
void AdjList::InsertEdge(int v1,int v2,WType w)
{
	if(v1<0||v1>=numOfVertice||v2<0||v2>=numOfVertice)
		{
			cout<<"v1和v2的值不合法，無法插入邊<v1,v2>";
				exit(0);
		}
	Edge*p;
	if(!typeFlag)//無向圖
	{
		p=new Edge(v2,w);//插入邊(v1,v2)
		if(Vertice[v1].firstAdj==NULL)//第一次插入
			Vertice[v1].firstAdj=p;
		else
		{	
			Edge*curr=Vertice[v1].firstAdj,*pre=NULL;
			while(curr!=NULL&&curr->dist<v2)
			{
				pre=curr;
				curr=curr->next;
			}
			if(pre==NULL)//插在第一個結點之后
			{
				p->next=Vertice[v1].firstAdj;
				Vertice[v1].firstAdj=p;
			}
			else//插在pre之后
			{
				p->next=pre->next;
				pre->next=p;
			}
		}
		p=new Edge(v1,w);//插入邊(v2,v1)
		if(Vertice[v2].firstAdj==NULL)//第一次插入
			Vertice[v2].firstAdj=p;
		else
		{	
			Edge*curr=Vertice[v2].firstAdj,*pre=NULL;
			while(curr!=NULL&&curr->dist<v1)
			{
				pre=curr;
				curr=curr->next;
			}
			if(pre==NULL)//插在第一個結點之后
			{
				p->next=Vertice[v2].firstAdj;
				Vertice[v2].firstAdj=p;
			}
			else//插在pre之后
			{
				p->next=pre->next;
				pre->next=p;
			}
		}

		numOfEdge++;

	}
	else//有向圖
	{
		 p=new Edge(v2,w);//插入邊<v1,v2>
		if(Vertice[v1].firstAdj==NULL)//第一次插入
			Vertice[v1].firstAdj=p;
		else
		{	
			Edge*curr=Vertice[v1].firstAdj,*pre=NULL;
			while(curr!=NULL&&curr->dist<v2)
			{
				pre=curr;
				curr=curr->next;
			}
			if(pre==NULL)//插在第一個結點之后
			{
				p->next=Vertice[v1].firstAdj;
				Vertice[v1].firstAdj=p;
			}
			else//插在pre之后
			{
				p->next=pre->next;
				pre->next=p;
			}
		}
		numOfEdge++;
	}
}
void AdjList::DeleteVertice(int v)
{
	if (v<0||v>=numOfVertice)
		{
			cout<<"序號為v的結點不存在，無法刪除！";
			exit(0);
		}
		//刪除鄰接表中其它頂點與v的關聯邊
	Edge*p,*q;
	p=Vertice[v].firstAdj;//刪除v結點關聯的邊
	for(int i=v;i<numOfVertice-1;i++)//刪除結點
	{
		Vertice[i].data=Vertice[i+1].data;
		Vertice[i].firstAdj=Vertice[i+1].firstAdj;
	}
	numOfVertice--;
	while(p!=NULL)
	{
		numOfEdge--;
		q=p->next;
		delete p;
		p=q;
	}
	//刪除包含頂點vv的邊，需要注意的是原有鄰接邊的序號發生改變
	//即所有鄰接邊序號中比貝刪除結點序號大的都要減去1
	Edge*temp;
    for(int j=0;j<numOfVertice;j++)
	{
		p=Vertice[j].firstAdj;
		q=NULL;
		while(p!=NULL&&p->dist<v)
		{
			q=p;
			p=p->next;
		}
		if(q==NULL&&p->dist==v)//刪除的是第一個鄰接邊
		{
			Vertice[j].firstAdj=p->next;
			delete p;
			if(typeFlag)
				numOfEdge--;
		}
		else if(p!=NULL&&p->dist==v)
		{
			q->next=p->next;
			delete p;
			if(typeFlag)
				numOfEdge--;
		}
	}
	for(j=0;j<numOfVertice;j++)
		{
			p=Vertice[j].firstAdj;
			q=NULL;
			while(p!=NULL&&p->dist<=v)
			{
				q=p;
				p=p->next;
			}
			if(p!=NULL)
			{
				temp=p;
				while(temp!=NULL)
				{
					temp->dist--;
					temp=temp->next;
				}
			}
	}
}
void AdjList::DeleteEdge(int v1,int v2)
{
	if(v1<0||v1>=numOfVertice||v2<0||v2>=numOfVertice)
		{
			cout<<"v1和v2的值不合法，無法刪除邊<v1,v2>";
				exit(0);
		}
	if(typeFlag)//有向圖刪除邊<v1,v2>
	{
		Edge*p,*q;
		q=NULL;
		p=Vertice[v1].firstAdj;
		while(p&&p->dist!=v2)
		{
			q=p;
			p=p->next;
		}
		if(q==NULL&&p->dist==v2)//刪除第一個結點
		{
			Vertice[v1].firstAdj=p->next;
			delete p;
				numOfEdge--;
		}
		if(q!=NULL&&p->dist==v2)//刪除p
		{
			q->next=p->next;
			delete p;
			numOfEdge--;
		}
	}
	else//無向圖
	{
		Edge*p,*q;
		q=NULL;
		p=Vertice[v1].firstAdj;//刪除邊(v1,v2)
		while(p&&p->dist!=v2)
		{
			q=p;
			p=p->next;
		}
		if(q==NULL&&p->dist==v2)
		{
			Vertice[v1].firstAdj=p->next;
			delete p;
		}
		if(q!=NULL&&p->dist==v2)
		{
			q->next=p->next;
			delete p;
		}
		numOfEdge--;
		q=NULL;
		p=Vertice[v2].firstAdj;//刪除邊(v2,v1)
		while(p&&p->dist!=v1)
		{
			q=p;
			p=p->next;
		}
		if(q==NULL&&p->dist==v1)
		{
			Vertice[v2].firstAdj=p->next;
			delete p;
		}
		if(q!=NULL&&p->dist==v1)
		{
			q->next=p->next;
			delete p;
		}
	}
}
int AdjList::GetFirstNeighbor(const int v)
{
	if (v<0||v>=numOfVertice)
		{
			cout<<"序號為v的結點不存在，無法找到他的第一條鄰接邊！";
			exit(0);
		}
	Edge*p=Vertice[v].firstAdj;
	if(p)
		return p->dist;
	return -1;
}
int AdjList::GetNextNeighbor(const int v1,const int v2)
{
	if(v1<0||v1>=numOfVertice||v2<0||v2>=numOfVertice)
		{
			cout<<"v1和v2的值不合法，無法找到<v1,v2>的下一鄰接邊";
				exit(0);
		}
	Edge*p=Vertice[v1].firstAdj;
	while (p)
	{
		if(p->next&&p->dist==v2)
			return p->next ->dist ;
		else
			p=p->next ;
	}
	return -1;
}
void AdjList::DepthFirstSearch(const int v,int visited[],void visit(VerType item))
{
	visit(GetItem(v));
	visited[v]=1;//作標記，表示該點已經訪問過了
	int adjV=GetFirstNeighbor(v);
	while(adjV!=-1)
	{
		if(!visited[adjV])
			DepthFirstSearch(adjV,visited,visit);//以adjV點進行深度優先遍歷
		adjV=GetNextNeighbor(v,adjV);
	}
}
void AdjList::BroadFirstSearch(const int v,int visited[],void visit(VerType item))
{
	int u,adjV;
	SeqQueue queue;
	visit(GetItem(v));
	visited[v]=1;
	queue.QInsert(v);
	while(!queue.QueueEmpty())
	{
		u=queue.QDelete();
		adjV=GetFirstNeighbor(u);
		while(adjV!=-1)
		{
			if(!visited[adjV])
			{
				visit(GetItem(adjV));
				visited[adjV]=1;
				queue.QInsert(adjV);
			}
			adjV=GetNextNeighbor(u,adjV);
		}
	}
}
void AdjList::DepthFirstSearch(void visit(VerType item))//有向圖和非連通圖深度優先遍歷
{
	int *visited=new int[NumOfVer()];
	for(int i=0;i<NumOfVer();i++)
		visited[i]=0;
	for(i=0;i<NumOfVer();i++)
		if(!visited[i])
			DepthFirstSearch(i,visited,visit);
		delete []visited;
}
void AdjList:: BroadFirstSearch(void visit(VerType item))//有向圖和非連通圖廣度優先遍歷
{
	int *visited=new int[NumOfVer()];
	for(int i=0;i<NumOfVer();i++)
		visited[i]=0;
	for(i=0;i<NumOfVer();i++)
		if(!visited[i])
			BroadFirstSearch(i,visited,visit);
		delete []visited;
}
Edge* AdjList::GetAdj(int v)
{
	if (v<0||v>=numOfVertice)
		{
			cout<<"序號為v的結點不存在，無法找到指向他的第一條鄰接邊的指針！";
			exit(0);
		}
	Edge*p=Vertice[v].firstAdj;
	return p;
}