sortcsource.cpp

拓扑排序,数据结构课程设计实现拓扑排序的源码!!!以及正确的调试结果

#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)) ;          //分配内存
  if(!S->base) exit(1) ;             //分配失败      
  S->top = S->base ;
  S->stacksize = STACK_INIT_SIZE ;
}

//元素进栈
void Push(SqStack *S , int e)  {      
	if(S->top - S->base >= S->stacksize){     //判断栈是否溢
		S->base = (int *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(int));  //并为栈重新分配内存
		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<<"栈内没有元素"<<endl;
	*e = * --S->top;  
}

//计算节点入度,用数组存储节点读书
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<<"请输入有向图的边数和节点数"<<endl;
       cin>>g->arcNum>>g->verNum ;
   
	   for( i = 1; i <= g->verNum ;i ++){              //创建节点的头节点，采用顺序存储结构
     g->vertices[i].data = i ;
	 g->vertices[i].firstArc = NULL ;
   }
   
	   for( i = 1;i<=g->arcNum ;i++){
      cout<<"请依次输入边的两个节点的序号（先弧头节点，再弧尾节点）："<<endl;      //邻接表的基础
	  cin>>verNum1>>verNum2;
	  
	  while(verNum1<0||verNum1>g->verNum||verNum2<0||verNum2>g->verNum) {       //判断节点序号合法性
			cout<<"对不起，你输入的节点序号不正确，请核对后重新输入："<<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;
   }
}

//进行拓扑排序
void ToPuSort(ALGraph g) {
  int indegree[15];               //初始化储存节点的整型数组
  int i,m,n;
  int count = 0;             //用count计数来判断有向图是否存在环
  ArcNode *p;
  SqStack S;

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

  for(i =1; i<=g.verNum ;i++){
    cout<<"第"<<i<<"个节点的入度为"<<indegree[i]<<endl;
  }
  cout<<endl;
  for(i =1; i<=g.verNum ;i++){
    if(!(indegree[i]))
		Push(&S,i);
  }
  cout<<"此有向图的拓扑序列为："<<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<<"该有向图存在环"<<endl;

  else
	  cout<<"祝贺你，拓扑排序成功"<<endl;
}