#include
#include
#define?MAX_VEXTEX_NUM?20???//最大頂點(diǎn)個(gè)數(shù)#define?M?20
#define?STACK_INIT_SIZE?100
#define?STACKINCREMENT?10
#define?OK?1
#define?M?20
#define?ERROR?0
typedef?int?ElemType;
typedef?struct?ArcNode???????//定義表結(jié)點(diǎn)結(jié)構(gòu)
{
int?adjvex;???????????????//與vi相鄰接的頂點(diǎn)編號(hào)
struct?ArcNode?*nextarc;????//指向下一條弧（邊）的指針
}ArcNode;
typedef?struct?VNode???????//定義表頭結(jié)點(diǎn)結(jié)構(gòu)
{
int?data;
ArcNode?*firstarc;???????//指向第一條弧（邊）的指針
}VNodeAdjList[MAX_VEXTEX_NUM];
typedef?struct????????????//定義鄰接表結(jié)構(gòu)
{
AdjList?vertices;????????//表頭結(jié)點(diǎn)數(shù)組
int?vexnum?arcnum;?????//頂點(diǎn)和弧（邊）的個(gè)數(shù)
}ALGraph;
typedef?struct?//構(gòu)件棧
{
ElemType?*base;
ElemType?*top;
int?stacksize;
}SqStack;
void?InitStack（SqStack?*）;???????????????//函數(shù)聲明
int?Pop（SqStack?*?ElemType?*）;
void?Push（SqStack?*ElemType?）;
int?StackEmpty（SqStack?*）;
void?CreatGraph（ALGraph?*）;
void?FindInDegree（ALGraph??int?*?）;
void?TopologicalSort（ALGraph?）;
void?InitStack（SqStack?*S）//初始化棧
{
S->base=（ElemType?*）malloc（STACK_INIT_SIZE*sizeof（ElemType））;
if（!S->base）
{
printf（“memory?allocation?failed?goodbye“）;
exit（1）;
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
int?Pop（SqStack?*SElemType?*e）//出棧操作
{
if（S->top==S->base）
{
return?ERROR;
}
*e=*--S->top;
return?0;
}
void?Push（SqStack?*SElemType?e）//進(jìn)棧操作
{
if（S->top-S->base>=S->stacksize）
{
S->base?=?（ElemType?*）realloc（S->base（S->stacksize+STACKINCREMENT）*sizeof（ElemType））;
if（!S->base）
{
printf（“memory?allocation?failed?goodbye“）;
exit（1）;
}
S->top?=?S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
}
int?StackEmpty（SqStack?*S）//判斷棧是否為空
{
if（S->top==S->base）
return?OK;
else
return?ERROR;
}
void?CreatGraph（ALGraph?*G）//構(gòu)建圖
{
int?m?n?i;
ArcNode?*p;
printf（“請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):“）;
scanf（“%d?%d“&G->vexnum&G->arcnum）;
for?（i?=?1;?i?<=?G->vexnum;?i++）
{
G->ve