拓扑排序（1）

（1） 1 #include"stdio.h"
 2 #include"stdlib.h"
 3 #define MAX_VEXTEX_NUM 20   //定义顶点的最大值
 4 #define  M 20
 5 #define STACK_INIT_SIZE 100 //定义栈的大小  100
 6 #define  STACKINCREMENT 10 //定义栈的增量  10
 7 #define OK 1
 8 #define ERROR  0
 9 
10 typedef  int ElemType;  //定义栈顶元素类型
11 typedef struct ArcNode
12 {
13     int adjvex; //该弧所指向的顶点的位置
14     struct  ArcNode *nextarc; //指向下一条弧的指针
15 }ArcNode; //表结点
16 
17 typedef  struct VNode
18 {
19     int data;//顶点信息
20     ArcNode *firstarc;//表结点的地址。指向该顶点的弧的指针
21 }VNode,AdjList[MAX_VEXTEX_NUM];  //头结点
22 
23 typedef struct  
24 {
25     AdjList vertices;
26     int vexnum,arcnum;// 图的顶点数和弧数
27 }ALGraph;
28 
29 typedef struct  //建栈
30 {
31     ElemType *base;  //在栈构造之前的指针
32     ElemType *top;//栈顶指针
33     int stacksize; //定义所分配的存储空间
34 }SqStack; //顺序栈
35 
36 void  InitStack(SqStack *S) //初始化栈
37 {
38     S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
39     if(!S->base)
40     {
41         printf("初始化出错，退出");
42         exit(1);
43     }
44     S->top=S->base; //空栈之前的指针赋给头指针
45     S->stacksize=STACK_INIT_SIZE;//栈的空间设为STACK_INIT_SIZE
46 
47 }
48 int Pop(SqStack *S,ElemType *e) //出栈操作
49 {
50     if(S->top==S->base)  //栈空返回OK  
51            return ERROR;
52     *e=*--S->top; //删除栈顶元素
53     return 0;
54 }
55 
56 void Push(SqStack *S,ElemType e) //进栈操作，插入元素e为新的栈顶元素
57 {
58     if(S->top-S->base >= S->stacksize) //栈满，追加存储空间
59     {
60         S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
61         if(!S->base)  //存储分配失败
62         {
63             printf("进栈出错，退出");
64             exit(1);
65         }
66 
67         S->top=S->base+S->stacksize;
68         S->stacksize+=STACKINCREMENT;
69     }
70     *S->top++=e;
71 }