003.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> 
 #include<iostream.h> 
#define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 typedef int Status; 
typedef int Boolean;
#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)
{       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,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)
 { 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); /* 入度为者进栈*/
   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); 
      ++count;
     for(p=G.vertices[i].firstarc;p;p=p->nextarc)
     {        k=p->adjvex;
       if(!(--indegree[k])) 
         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);
}