【文章內(nèi)容簡介】 pedef int Status。 // Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 typedef int Boolean。 // Boolean是布爾類型,其值是TRUE或FALSEdefine MAX_NAME 10/* 頂點字符串的最大長度*/define MAXCLASS 100int Z=0。int X=0。int xqzs,q=1,xfsx。typedef int InfoType。typedef char VertexType[MAX_NAME]。 /* 字符串類型*//* 圖的鄰接表存儲表示*/define MAX_VERTEX_NUM 100typedef enum{DG}GraphKind。 /* {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} */typedef struct ArcNode{int adjvex。 /* 該弧所指向的頂點的位置*/struct ArcNode *nextarc。 /* 指向下一條弧的指針*/InfoType *info。 /* 網(wǎng)的權(quán)值指針）*/}ArcNode。 /* 表結(jié)點*/typedef struct{VertexType data。 /* 頂點信息*/ArcNode *firstarc。 /* 第一個表結(jié)點的地址,指向第一條依附該頂點的弧的指針*/ }VNode,AdjList[MAX_VERTEX_NUM]。 /* 頭結(jié)點*/typedef struct{AdjList vertices,verticestwo。int vexnum,arum。 /* 圖的當(dāng)前頂點數(shù)和弧數(shù)*/int kind。 /* 圖的種類標(biāo)志*/}ALGraph。/* 圖的鄰接表存儲的基本操作*/int LocateVex(ALGraph G,VertexType u){ /* 初始條件: 圖G存在,u和G中頂點有相同特征*//* 操作結(jié)果: 若G中存在頂點u,則返回該頂點在圖中位置。否則返回1 */int i。for(i=0。i。++i)if(strcmp(u,[i].data)==0)return i。return 1。}Status CreateGraph(ALGraph *G){ /* 采用鄰接表存儲結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的圖G(用一個函數(shù)構(gòu)造種圖) */ int i,j,k。VertexType va,vb。ArcNode *p。printf(請輸入教學(xué)計劃的課程數(shù): )。scanf(%d,amp。(*G).vexnum)。printf(請輸入拓撲排序所形成的課程先修關(guān)系的邊數(shù): )。scanf(%d,amp。(*G).arum)。printf(請輸入%d個課程的代表值(%d個字符):\n,(*G).vexnum,MAX_NAME)。for(i=0。i(*G).vexnum。++i) /* 構(gòu)造頂點向量*/{ scanf(%s,(*G).vertices[i].data)。 (*G).vertices[i].firstarc=NULL。}printf(請輸入%d個課程的學(xué)分值(%d個字符):\n,(*G).vexnum,MAX_NAME)。 for(i=0。i(*G).vexnum。++i) /* 構(gòu)造頂點向量*/{ scanf(%s,(*G).verticestwo[i].data)。}printf(請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n)。 for(k=0。k(*G).arum。++k) /* 構(gòu)造表結(jié)點鏈表*/{ scanf(%s%s,va,vb)。 i=LocateVex(*G,va)。 /* 弧尾*/ j=LocateVex(*G,vb)。 /* 弧頭*/ p=(ArcNode*)malloc(sizeof(ArcNode))。 padjvex=j。 pinfo=NULL。 /* 圖*/ pnextarc=(*G).vertices[i].firstarc。 /* 插在表頭*/ (*G).vertices[i].firstarc=p。}return OK。}void Display(ALGraph G){ /* 輸出圖的鄰接矩陣G */int i。ArcNode *p。switch(){case DG: printf(有向圖\n)。}printf(%d個頂點：\n,)。for(i=0。i。++i)printf(%s ,[i].data)。printf(\n%d條弧(邊):\n,)。for(i=0。i。i++){p=[i].firstarc。while(p){ printf(%s→%s ,[i].data,[padjvex].data)。 p=pnextarc。}printf(\n)。}}void FindInDegree(ALGraph G,int indegree[]){ /* 求頂點的入度，算法調(diào)用*/int i。ArcNode *p。for(i=0。i。i++)indegree[i]=0。 /* 賦初值*/for(i=0。i。i++){p=[i].firstarc。while(p){ indegree[padjvex]++。 p=pnextarc。}}}typedef int SElemType。 /* 棧類型*//*棧的順序存儲表示*/define STACK_INIT_SIZE 10 /* 存儲空間初始分配量*/define STACKINCREMENT 2 /* 存儲空間分配增量*/typedef struct SqStack{SElemType *base。 /* 在棧構(gòu)造之前和銷毀之后，base的值為NULL */ SElemType *top。 /* 棧頂指針*/int stacksize。 /* 當(dāng)前已分配的存儲空間，以元素為單位*/}SqStack。 /* 順序棧*//* 順序棧的基本操作*/Status InitStack(SqStack *S){ /* 構(gòu)造一個空棧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。}void ClearStack(SqStack *S) //清空棧的操作{Stop=Sbase。}Status StackEmpty(SqStack S){ /* 若棧S為空棧，則返回TRUE，否則返回FALSE */ if(==) 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采用鄰接表存儲結(jié)構(gòu)。若G無回路,則輸出G的頂點的一個拓撲序列并返回OK, *//* 否則返回ERROR。*/int i,k,j=0,count,indegree[MAX_VERTEX_NUM]。bool has=false。SqStack S。pathone a。pathtwo b。ArcNode *p。FindInDegree(G,indegree)。 /* 對各頂點求入度indegree[0..vernum1] */ InitStack(amp。S)。 /* 初始化棧*/for(i=0。i。++i) /* 建零入度頂點棧S */if(!indegree[i]){ Push(amp。S,i)。//cout*[i].dataendl。}/* 入度為者進棧*/count=0。 /* 對輸出頂點計數(shù)*/while(!StackEmpty(S)){ /* 棧不空*/ Pop(amp。S,amp。i)。 a[i]=*[i].data。 b[i]=*[i].data。 printf(課程%s→學(xué)分%s ,[i].data,[i].data)。 /* 輸出i號頂點并計數(shù)*/ ++count。 for(p=[i].firstarc。p。p=pnextarc){ /* 對i號頂點的每個鄰接點的入度減*/ k=padjvex。 if(!(indegree[k])) /* 若入度減為,則入棧*/{ Push(amp。S,k)。//cout*[i].dataendl。}}}if(count){ printf(此有向圖有回路\n)。 return ERROR。}else{ printf(為一個拓撲序列。\n)。 has=true。}FindInDegree(G,indegree)。 /* 對各頂點求入度indegree[0..vernum1] */ ClearStack(amp。S)。cout======================課程計劃如下===============================endl。int qq=1。 //學(xué)期數(shù)int xxf。while(qq=xqzs){ int result[20]。 int rtop=0。 int nn=0。//int ccount=0。// 學(xué)期學(xué)分計算 x