#include <iostream.h>
#include "SortHead.h"
#include<stdlib.h>
/*********************************************************************
*Created on 2007.7.12
*Creared by pdw
*CopyRight pdw
*version 1.1
*********************************************************************/
//初始化棧
void InitStack(SqStack *S){
  S->base = (int *)malloc(STACK_INIT_SIZE*sizeof(int)) ;          //分配內(nèi)存
  if(!S->base) exit(1) ;             //分配失敗      
  S->top = S->base ;
  S->stacksize = STACK_INIT_SIZE ;
}

//元素進(jìn)棧
void Push(SqStack *S , int e)  {      
	if(S->top - S->base >= S->stacksize){     //判斷棧是否溢
		S->base = (int *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(int));  //并為棧重新分配內(nèi)存
		if(!S->base) exit(1) ;
	      S->top = S->base+S->stacksize ;
	 S->stacksize +=STACKINCREMENT ;
	}
	* S->top++ = e ;
}

//元素出棧
void Pop(SqStack *S , int *e) {
	if(S->base == S->top)  
		cout<<"棧內(nèi)沒(méi)有元素"<<endl;
	*e = * --S->top;  
}

//計(jì)算節(jié)點(diǎn)入度,用數(shù)組存儲(chǔ)節(jié)點(diǎn)讀書(shū)
void AccountInDegree(ALGraph g ,int indegree[]) {
	 int i;
	for(i = 1 ; i <= g.verNum ; i ++){
		indegree[i]=0;
	}
	for(i = 1 ;i<=g.verNum;i++){
		while(g.vertices[i].firstArc){
		  indegree[g.vertices[i].firstArc->adjvex]++;
		g.vertices[i].firstArc = g.vertices[i].firstArc->nextArc;
		}
	}
}

//判斷棧是否為空
bool StackEmpty(SqStack *S)  {
   if(S->base == S->top) return true;
   else 
	   return false ;
}

void CreateGraph_AdjList(ALGraph *g){
   int verNum1 ,verNum2 ,i ;
   ArcNode *p ;
       cout<<"請(qǐng)輸入有向圖的邊數(shù)和節(jié)點(diǎn)數(shù)"<<endl;
       cin>>g->arcNum>>g->verNum ;
   
	   for( i = 1; i <= g->verNum ;i ++){              //創(chuàng)建節(jié)點(diǎn)的頭節(jié)點(diǎn)，采用順序存儲(chǔ)結(jié)構(gòu)
     g->vertices[i].data = i ;
	 g->vertices[i].firstArc = NULL ;
   }
   
	   for( i = 1;i<=g->arcNum ;i++){
      cout<<"請(qǐng)依次輸入邊的兩個(gè)節(jié)點(diǎn)的序號(hào)（先弧頭節(jié)點(diǎn)，再弧尾節(jié)點(diǎn)）："<<endl;      //鄰接表的基礎(chǔ)
	  cin>>verNum1>>verNum2;
	  
	  while(verNum1<0||verNum1>g->verNum||verNum2<0||verNum2>g->verNum) {       //判斷節(jié)點(diǎn)序號(hào)合法性
			cout<<"對(duì)不起，你輸入的節(jié)點(diǎn)序號(hào)不正確，請(qǐng)核對(duì)后重新輸入："<<endl;
		    cin>>verNum1>>verNum2;
	  }
	  //p = (ArcNode*)malloc(sizeof(ArcNode));
	  p = new ArcNode;
	  if(!p) exit(1);
	  p->adjvex = verNum2;
		  p->nextArc = g->vertices[verNum1].firstArc ;
          g->vertices[verNum1].firstArc = p ;
   }
   cout<<"由有向圖建立的鄰接表如下："<<endl;
   
   for(i = 1;i<=g->verNum ;i++){                            //建立并輸出有向圖的鄰接表
     cout<<g->vertices[i].data<<" ";
	 for(p = g->vertices[i].firstArc ;p;p = p->nextArc)
		 cout<<p->adjvex<<" ";
	 cout<<endl;
   }
}

//進(jìn)行拓?fù)渑判?void ToPuSort(ALGraph g) {
  int indegree[15];               //初始化儲(chǔ)存節(jié)點(diǎn)的整型數(shù)組
  int i,m,n;
  int count = 0;             //用count計(jì)數(shù)來(lái)判斷有向圖是否存在環(huán)
  ArcNode *p;
  SqStack S;

  AccountInDegree(g,indegree);
  InitStack(&S);

  for(i =1; i<=g.verNum ;i++){
    cout<<"第"<<i<<"個(gè)節(jié)點(diǎn)的入度為"<<indegree[i]<<endl;
  }
  cout<<endl;
  for(i =1; i<=g.verNum ;i++){
    if(!(indegree[i]))
		Push(&S,i);
  }
  cout<<"此有向圖的拓?fù)湫蛄袨椋?quot;<<endl;
  while(!StackEmpty(&S)){
    Pop(&S,&n);
	cout<<g.vertices[n].data<<" ";
	count++;
	for(p = g.vertices[n].firstArc;p;p=p->nextArc){
		m=p->adjvex;
	if(!(--indegree[m])){
	   Push(&S,m);
	}
	}
  }
  cout<<endl;
  if(count<g.verNum)
	  cout<<"該有向圖存在環(huán)"<<endl;

  else
	  cout<<"祝賀你，拓?fù)渑判虺晒?quot;<<endl;
}