6.cpp

用于编程序

/* 输出有向图的一个拓扑序列及其应用问题的算法实现程序 */
#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h> 
#include<stdio.h> 
#include<stdlib.h> 
#include<io.h> 
#include<math.h> 
#include<process.h> 

/* 函数结果状态代码 */
#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)//构件图
{
int  i,k,j;
VertexType va,vb;
ArcNode *p;

printf("请输入顶点数和边数:");
scanf("%d%d",&G->vexnum,&G->arcnum);

for (i = 1; i <= G->vexnum; i++)
{
scanf("%s",G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}

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(sizeof(SElemType)*STACK_INIT_SIZE);
   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,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)
    {printf("%s ", G.vertices[X].data);
  ++X;
  }
  printf("\n");
  q++;
}
  else
{printf("\n");
return OK;
}
}
return OK;
}

int main()
{  ALGraph G;
  
   CreateGraph(&G);
   Display(G);
   TopologicalSort(G);
   
   return 0;
}