自学的数据结构 关于拓扑排序的知识还有些模糊，写了个小程序还有地方不知怎么实现，求指点！！
#include<iostream.h>#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAX_VERTEX_NUM 20
typedef char Vertex_Type[5];
typedef struct Arc_Node
{
int adjvex; //弧所指向的顶点的位置
struct Arc_Node *nextarc;
}Arc_Node;
typedef struct Vertex_Node
{
Vertex_Type data;
int indegree;
Arc_Node *firstarc;
}Vertex_Node;
typedef struct
{
Vertex_Node vexs[MAX_VERTEX_NUM];
//Vertex_Type *vexs;
int vexnum;
int arcnum;
}ALGraph;
/*struct Vertex
{
Vertex_Type data; //结点的数据域
Arc_Node *adj; //边链表的首指针
}*/
typedef struct //栈的定义
{
int *base;
int *top;
int stacksize;
}SqStack;
/////////////栈的操作函数定义
void InitStack(SqStack *S)
{
S->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
if(!S->base)
exit(0);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *S,int e)
//插入元素e为新的栈顶元素
{
if(S->top-S->base>=S->stacksize)
{
S->base=(int*)realloc(S->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(int));
if(!S->base)
exit(0);
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top)++=e;
}
void Pop(SqStack *S,int *e)
//若栈不空，则删除S的栈顶元素，用e返回其值
{
if(S->top==S->base)
exit(0);
*e=*--(S->top);
}
int StackEmpty(SqStack *S)
{
if(S->base==S->top)
return (1);
else
return (0);
}
void Init_ALGraph(ALGraph &G)
{
cout<<"输入图的顶点数:";
cin>>G.vexnum;
cout<<"输入图的边数:";
cin>>G.arcnum;
int i;
cout<<"输入定点值:";
for(i=0;i<G.vexnum;++i)
{
cin>>G.vexs[i].data;
G.vexs[i].firstarc=NULL;
}
}
//获取定点在向量中的位置 如果出错就终止运行
int Get_Vertex_Location(ALGraph G,Vertex_Type v)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(v,G.vexs[i].data)==0)
return i;
exit(0);
}
void Greate_ALGraph(ALGraph &G)
{
Init_ALGraph(G);
Vertex_Type v1,v2;
int m,n,i;
cout<<"输入图形的边数:";
for(i=0;i<G.arcnum;++i) //输入并构造邻接表
{
cin>>v1>>v2;
m=Get_Vertex_Location(G,v1);
n=Get_Vertex_Location(G,v2);
Arc_Node *p1;
p1=(Arc_Node*)malloc(sizeof(Arc_Node));
p1->adjvex=n; //对弧点赋邻接点位置信息
p1->nextarc=G.vexs[m].firstarc;
G.vexs[m].firstarc=p1;
}
}
int TopSort(ALGraph G)
{
SqStack S;
int k,i;
int vexnum;
int*indegree=new int[vexnum];
//int v;
Arc_Node *p;
//int FindInDegree(ALGraph &G,int *indegree); //对各顶点求入度indegree[0...vexnum-1]
for(i=0;i<vexnum;i++)
{
indegree[i]=0; //初始化入度统计数组
}
/*首先遍历结点数组找出每个结点的入度*/
for(i=0;i<vexnum;i++)
{
Arc_Node *ptr=vexs[i].data; //取得每个边链表的第一个元素结点
while(ptr!=NULL) //遍历每个边链表的结点
{
int p=ptr->adjvex; //统计图中每个顶点入度数
indegree[p]++;
ptr=ptr->nextarc;
}
}
InitStack(&S);
for(i=0;i<G.vexnum;++i) //建零入度顶点栈S
{
if(indegree[i]==0) //入度为零者进栈
Push(&S,i);
int count=0; //对输出的顶点计数
while(!StackEmpty(&S))
{
Pop(&S,&i);
cout<<i<<G.vexs[i].data; //输出i号顶点并计数
++count;
for(p=G.vexs[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!(--indegree[k])) //对i号顶点的每个邻接点的入度减1
Push(&S,k); //若入度减为零则入栈
}
}
if(count<G.vexnum) //该有向图有回路
return 0;
else
return 1;
}
}
void Print_ALGraph(ALGraph G)
{
int i;
Arc_Node *p=NULL;
for(i=0;i<G.vexnum;++i)
{
//p=G.vexs[i].indegree[i];
p=G.vexs[i].firstarc;
while(p)
{
cout<<G.vexs[i].data;
cout<<G.vexs[p->adjvex].data<<endl;
p=p->nextarc;
}
}
}
int main()
{
ALGraph G;
Greate_ALGraph(G);
cout<<"该有向图的拓扑排序为:";
TopSort(G);
Print_ALGraph(G);
return 0;
}
