tuopu.cpp

用C++做的一个高校排课系统.主要用了托普算法来实现

#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)  
{ 
   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  \n",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 100  
#define STACKINCREMENT 20  
typedef struct SqStack  
{  
   SElemType *base; 
   SElemType *top; 
   int stacksize;  
}SqStack; 

Status InitStack(SqStack *S)  
{  
   (*S).base=(SElemType *)malloc(10*(sizeof(SElemType)));  
   if(!(*S).base)  
     exit(OVERFLOW);
   (*S).top=(*S).base;  
   (*S).stacksize=STACK_INIT_SIZE;  
   return OK;  
}  
Status StackEmpty(SqStack S)  
{  
   if(S.top==S.base)  
     return TRUE;  
   else  
     return FALSE;  
}  
Status Pop(SqStack *S,SElemType *e)  
{ 
   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)  
{  
   int i,k,j=0,count,indegree[MAX_VERTEX_NUM];  
   SqStack S;  
   pathone a;  
   pathtwo b;  
   ArcNode *p;  
   FindInDegree(G,indegree); 
   InitStack(&S);  
   for(i=0;i<G.vexnum;++i)  
     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  \n",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;
		 ++C;
  }    
  printf("第%d个学期应学课程:",q);  
  while(X<=Z)  
        {cout<<*G.vertices[X].data<<" ";  
  ++X;  
  }  
  cout<<endl;  
  q++;  
}  
  else  
{
	  cout<<"课程编制已经完成！"<<endl;  
      return OK;  
}  
}  
return OK;  
} 

void canKaoShuRu()
 {
	 printf("************************************************\n");
	 printf("**     假设要输入以下课程:    先修关系    ******\n");
	 printf("**     A:计算机导论                       ******\n");   
     printf("**     B:高等数学                         ******\n");   
	 printf("**     C:线性代数                         ******\n"); 
     printf("**     D:大学英语1                        ******\n"); 
     printf("**     E:大学英语2                  D     ******\n");              
     printf("**     F:大学英语3                  E     ******\n");               
     printf("**     G:大学英语4                  F     ******\n");              
     printf("**     H:专业英语                   G     ******\n");             
     printf("**     I:C语言程序设计              A     ******\n");        
     printf("**     G:计算机组成与原理           A     ******\n");
	 printf("**     则科目有10科,课程先修关系的边数为6条*****\n");
	 printf("**	    C-D,D-E,E-F,F-G,A-H,A-I       ******\n");
	 printf("**     注意提示的输入格式                 ******\n");
	 printf("**     本系统并不完善,输入先修关系要慎重  ******\n");
	 printf("************************************************\n\n\n");
 }
void owner()
{    
	 printf("************************************************\n");
     printf("***   By EDU-TECH CLASS TWO: Sun HuiQi       ***\n");
     printf("***   The finish date is :Nov 27,2007        ***\n");
	 printf("***   the softfare is protected by Chinese laws*\n");
	 printf("************************************************\n\n\n");
 }
void paiKeXiTong()
{  
   ALGraph f; 
   printf("  请输入学期总数:\n");  
   scanf("%d",&xqzs);  
   printf("  请输入每学期的最高学分:\n"); 
   scanf("%d",&xfsx);  
   CreateGraph(&f);  
   Display(f);  
   TopologicalSort(f);
}
 

 

void main()  
{  
	int n;
   while(1){
   printf("****************   请选择!   *******************\n");
   printf("************************************************\n");  
   printf("***1:使用本系统前请参考题目输入信息:     *******\n"); 
   printf("***2:进入排课系统:                       *******\n");
   printf("***3:开发人员介绍                        *******\n");
   printf("***0:退出本系统                          *******\n");
   printf("************************************************\n");
   printf("************************************************\n");
   scanf("%d",&n);
   switch(n)
   {
       case 1:canKaoShuRu();break;
       case 2:paiKeXiTong();break;
	   case 3:owner();break;
	   case 0:exit(0);break;
	   default: printf("输入错误,请重新输入\n");
   }
} 
}