12-2.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"
#include <malloc.h>
#define Vecter 100
#define StackSize 100 //假定预分配的栈空间最多为100个元素 
typedef int DataType;//假定栈元素的数据类型为整数 	
typedef struct{
      DataType data[StackSize];
      int top;
}SeqStack;   
// 置栈空
void Initial(SeqStack *S)
{//将顺序栈置空
      S->top=-1;
} 
//判栈空
int IsEmpty(SeqStack *S)
{
    return S->top==-1;
}
//判栈满
int IsFull(SeqStack *S)
{
	return S->top==StackSize-1;
}
//进栈
void Push(SeqStack *S,DataType x)
{
    if (IsFull(S))
		{
			printf("栈上溢"); //上溢,退出运行
			exit(1);
		}
    S->data[++S->top]=x;//栈顶指针加1后将x入栈
}
//出栈
DataType Pop(SeqStack *S)
{
		if(IsEmpty(S))
		{
			printf("栈为空"); //下溢,退出运行
			return -1;
		}
		return S->data[S->top--];//栈顶元素返回后将栈顶指针减1
}
// 取栈顶元素
DataType Top(SeqStack *S)
{
		if(IsEmpty(S))
		{
			printf("栈为空"); //下溢,退出运行
			exit(1);
		}
		return S->data[S->top];
}
int Topological(int v[])
{// 计算有向图中顶点的拓扑次序,
//如果找到了一个拓扑次序，则返回1，
//此时，在v[ 0 : n - 1 ]中记录拓扑次序
// 如果不存在拓扑次序，则返回1
	int n = Vertices();
	// 计算入度
	int i,u;
	int w;
	SeqStack S;
	int *InDegree =(int*)malloc(sizeof(int)*(n+1));
	InitializePos(); // 图遍历器数组
	for (i = 1; i <= n; i++) // 初始化
		InDegree[i] = 0;
	for (i = 1; i <= n; i++) {// 从i 出发的边
		u = Begin(i);
		while (u) {
			InDegree[u]++;
			u=NextVertex(i);
		}
	}
	// 把入度为０的顶点压入堆栈
	for (i = 1; i <= n; i++)
	if (!InDegree[i]) 
		Push(&S,i);
	// 产生拓扑次序
	i = 0; // 数组v 的游标
	while (IsEmpty(&S)) {// 从堆栈中选择
		 // 下一个顶点
		w=Pop(&S) ;
		v[i++] = w;
		u= Begin(w);
		while (u) {// 修改入度
			InDegree[u]--;
			if (!InDegree[u]) 
				Pop(&S,u);
				u=NextVertex(w); 
		}
	}
	DeactivatePos();
	free(InDegree);
	return (i == n);
}
void main(void)
{
	int V[Vecter];
	int succ=Topological(V);
}