#include<string.h>
 #include<ctype.h>
 #include<malloc.h> // malloc()等
 #include<limits.h> // INT_MAX等
 #include<stdio.h> // EOF(=^Z或F6),NULL
 #include<stdlib.h> // atoi()52
 #include<io.h> // eof()
 #include<math.h> // floor(),ceil(),abs()
 #include<process.h> // exit()
 #include<iostream.h> // cout,cin
 // 函數結果狀態代碼
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
 typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
 #define MAX_NAME 10 
 /* 頂點字符串的最大長度 */
 #define MAXCLASS 100
 int Z=0;
 int X=0;
 int xqzs,q=1,xfsx;
 typedef int InfoType;
 typedef char VertexType[MAX_NAME]; /* 字符串類型 */
 /* 圖的鄰接表存儲表示 */
 #define MAX_VERTEX_NUM 100
 typedef enum{DG}GraphKind; /* {有向圖,有向網,無向圖,無向網} */
 typedef struct ArcNode
 {
   int adjvex; /* 該弧所指向的頂點的位置 */
   struct ArcNode *nextarc; /* 指向下一條弧的指針 */
   InfoType *info; /* 網的權值指針） */
 }ArcNode; /* 表結點 */
 typedef struct
 {
   VertexType data; /* 頂點信息 */
   ArcNode *firstarc; /* 第一個表結點的地址,指向第一條依附該頂點的弧的指針 */
 }VNode,AdjList[MAX_VERTEX_NUM]; /* 頭結點 */
 typedef struct
 {
   AdjList vertices,verticestwo;
   int vexnum,arcnum; /* 圖的當前頂點數和弧數 */
   int kind; /* 圖的種類標志 */
 }ALGraph;
/*  圖的鄰接表存儲的基本操作 */
 int LocateVex(ALGraph G,VertexType u)
{ /* 初始條件: 圖G存在,u和G中頂點有相同特征 */
   /* 操作結果: 若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1 */
   int i;
   for(i=0;i<G.vexnum;++i)
     if(strcmp(u,G.vertices[i].data)==0)
       return i;
   return -1;
}
Status CreateGraph(ALGraph *G)
 { /* 采用鄰接表存儲結構,構造沒有相關信息的圖G(用一個函數構造4種圖) */
   int i,j,k;
   VertexType va,VB;
   ArcNode *p;
   
   printf("請輸入教學計劃的課程數: ");
   scanf("%d",&(*G).vexnum);
   printf("請輸入拓撲排序所形成的課程先修關系的邊數: ");
   scanf("%d",&(*G).arcnum);
   printf("請輸入%d個課程的代表值(<%d個字符):\n",(*G).vexnum,MAX_NAME);
   for(i=0;i<(*G).vexnum;++i) /* 構造頂點向量 */
   { scanf("%s",(*G).vertices[i].data);
     (*G).vertices[i].firstarc=NULL;
   }
   printf("請輸入%d個課程的學分值(<%d個字符):\n",(*G).vexnum,MAX_NAME);
   for(i=0;i<(*G).vexnum;++i) /* 構造頂點向量 */
   {scanf("%s",(*G).verticestwo[i].data);
   }
   printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");
   for(k=0;k<(*G).arcnum;++k) /* 構造表結點鏈表 */
   { scanf("%s%s",va,vb);
     i=LocateVex(*G,va); /* 弧尾 */
     j=LocateVex(*G,vb); /* 弧頭 */
     p=(ArcNode*)malloc(sizeof(ArcNode));
     p->adjvex=j;
     p->info=NULL; /* 圖 */
     p->nextarc=(*G).vertices[i].firstarc; /* 插在表頭 */
     (*G).vertices[i].firstarc=p;
    }
   return OK;
 }
void Display(ALGraph G)
 { /* 輸出圖的鄰接矩陣G */
   int i;
   ArcNode *p;
   switch(G.kind)
   {case DG: printf("有向圖\n");
   }
   printf("%d個頂點：\n",G.vexnum);
   for(i=0;i<G.vexnum;++i)
     printf("%s ",G.vertices[i].data);
   printf("\n%d條弧(邊):\n",G.arcnum);
   for(i=0;i<G.vexnum;i++)
   {
     p=G.vertices[i].firstarc;
     while(p)
     {printf("%s→%s  ",G.vertices[i].data,G.vertices[p->adjvex].data);
      p=p->nextarc;
     }
     printf("\n");
   }
 }
void FindInDegree(ALGraph G,int indegree[])
 { /* 求頂點的入度，算法調用 */
   int i;
   ArcNode *p;
   for(i=0;i<G.vexnum;i++)
     indegree[i]=0; /* 賦初值 */
   for(i=0;i<G.vexnum;i++)
   {
     p=G.vertices[i].firstarc;
     while(p)
     { indegree[p->adjvex]++;
       p=p->nextarc;
     }
   }
 }
 typedef int SElemType; /* 棧類型 */
 /*棧的順序存儲表示 */
 #define STACK_INIT_SIZE 10 /* 存儲空間初始分配量 */
 #define STACKINCREMENT 2 /* 存儲空間分配增量 */
 typedef struct SqStack
 {
   SElemType *base; /* 在棧構造之前和銷毀之后，base的值為NULL */
   SElemType *top; /* 棧頂指針 */
   int stacksize; /* 當前已分配的存儲空間，以元素為單位 */
 }SqStack; /* 順序棧 */
 /* 順序棧的基本操作 */
 Status InitStack(SqStack *S)
 { /* 構造一個空棧S */
   (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
   if(!(*S).base)
     exit(OVERFLOW); /* 存儲分配失敗 */
   (*S).top=(*S).base;
   (*S).stacksize=STACK_INIT_SIZE;
   return OK;
}
Status StackEmpty(SqStack S)
 { /* 若棧S為空棧，則返回TRUE，否則返回FALSE */
   if(S.top==S.base)
     return TRUE;
   else
     return FALSE;
}
 Status Pop(SqStack *S,SElemType *e)
 { /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */
   if((*S).top==(*S).base)
     return ERROR;
   *e=*--(*S).top;
   return OK;
 }
 Status Push(SqStack *S,SElemType e)
 { /* 插入元素e為新的棧頂元素 */
   if((*S).top-(*S).base>=(*S).stacksize) /* 棧滿，追加存儲空間 */
   {
     (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof

(SElemType));
     if(!(*S).base)
       exit(OVERFLOW); /* 存儲分配失敗 */
     (*S).top=(*S).base+(*S).stacksize;
     (*S).stacksize+=STACKINCREMENT;
   }
   *((*S).top)++=e;
   return OK;
 }
typedef int pathone[MAXCLASS];
typedef int pathtwo[MAXCLASS];
Status TopologicalSort(ALGraph G)
 { /* 有向圖G采用鄰接表存儲結構。若G無回路,則輸出G的頂點的一個拓撲序列并返回OK, */
   /* 否則返回ERROR。 */
   int i,k,j=0,count,indegree[MAX_VERTEX_NUM];
   SqStack S;
   pathone a;
   pathtwo b;
   ArcNode *p;
   FindInDegree(G,indegree); /* 對各頂點求入度indegree[0..vernum-1] */
   InitStack(&S); /* 初始化棧 */
   for(i=0;i<G.vexnum;++i) /* 建零入度頂點棧S */
     if(!indegree[i])
       Push(&S,i); /* 入度為0者進棧 */
   count=0; /* 對輸出頂點計數 */
   while(!StackEmpty(S))
   { /* 棧不空 */
     Pop(&S,&i);
     a[i]=*G.vertices[i].data;
     b[i]=*G.verticestwo[i].data;
     printf("課程%s→學分%s  ",G.vertices[i].data,G.verticestwo[i].data); 
  /* 輸出i號頂點并計數 */
     ++count;
     for(p=G.vertices[i].firstarc;p;p=p->nextarc)
     { /* 對i號頂點的每個鄰接點的入度減1 */
       k=p->adjvex;
       if(!(--indegree[k])) /* 若入度減為0,則入棧 */
         Push(&S,k);
     }
   }
   if(count<G.vexnum)
   {printf("此有向圖有回路\n");
    return ERROR;
   }
   else
   {printf("為一個拓撲序列。\n");
   }

while(q<=xqzs) 
{ int C=0;
  if(X<=G.arcnum)
 { while(C<=xfsx)
  {C+=*G.verticestwo[Z].data;
         ++Z;
  }  
  printf("第%d個學期應學課程:",q);
  while(X<=Z)
        {cout<<*G.vertices[X].data<<" ";
  ++X;
  }
  cout<<endl;
  q++;
 }
  else
 {cout<<"課程編制已經完成！"<<endl;
 return OK;
 }
}
return OK;
}
void main()
{  ALGraph f;
   printf("教學計劃編制問題的數據模型為拓撲排序AOV-網結構。\n");
   printf("以下為教學計劃編制問題的求解過程:\n");
   printf("請輸入學期總數:");
   scanf("%d",&xqzs);
   printf("請輸入學期的學分上限:");
   scanf("%d",&xfsx);
   CreateGraph(&f);
   Display(f);
   TopologicalSort(f);
}