教学计划编制问题.cpp

教学计划编制问题,内有详细报告,源代码,还有实验结果代码,总之是非常的详细.这是一份数据结构的课程设计,花了很长时间弄整理出来的

#include <stdio.h>
#include <malloc.h> // malloc()
#include <string.h>
#include <process.h> //exit()
#define M   20
#define MAX_VERTEX_NUM 100 //最大课程总数
#define STACK_INIT_SIZE 100 //存储空间的初时分配量
#define STACKINCREMENT 10    //存储空间的分配增量
// 函数结果状态代码
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct{             //定义一个栈
    int *base;
    int *top;
    int stacksize;//栈的长度
}SqStack;
typedef struct ArcNode{
       int adjvex;//该弧所指向的顶点的位置
        struct ArcNode *nextarc;//指向下一条弧的指针
        }ArcNode;
typedef struct VNode{
       char name[24];       //课程名 
        int classid;        //课程号
        int credit;         //课程的学分
        int indegree;       //该结点的入度
        char *state;        //该节点的状态
        ArcNode *firstarc;  //指向第一条依附该顶点的弧的指针
        }VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
        AdjList vertices;
        int vexnum, arcnum;       //课程总数，先修关系总数
        }ALGraph;
void CreatGraph(ALGraph *G)//构件图
{
    int i, m, n;
    ArcNode *p;
    printf("请输入需要编排课程总数: ");
    scanf("%d",&G->vexnum);
    for( i=1;i<=G->vexnum;i++)
    {
        printf("请输入课程名: ");
        scanf("%s",&G->vertices[i].name);
        
        printf("请输入课程号: ");
        scanf("%d",&G->vertices[i].classid);
        
        printf("请输入该课程的学分: ");
        scanf("%d",&G->vertices[i].credit);
        
        G->vertices[i].indegree=0;
        G->vertices [i].state="NOTSTUDY";
        G->vertices[i].firstarc=NULL;
    }
    printf("请输入课程先修关系总数：");
    scanf("%d",&G->arcnum); 
    printf("请顺序输入每个课程先修关系(先修课程在前并以逗号作为间隔): ");
    for (i = 1; i <= G->arcnum; i++)
    {
        printf("\n请输入存在先修关系的两个课程的序号:");
        scanf("%d,%d",&n,&m);
        while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
        {
            printf("输入的顶点序号不正确 请重新输入:");
            scanf("%d,%d",&n,&m);
        }
        p = (ArcNode*)malloc(sizeof(ArcNode));
        if (p == NULL)
        {
            printf("memory allocation failed,goodbey");
            exit(1);
        }
        p->adjvex = m;
        p->nextarc = G->vertices[n].firstarc;
        G->vertices[n].firstarc = p;
    }
    printf("\n建立的邻接表为:\n");          //输出建立好的邻接表
    for(i=1;i<=G->vexnum;i++)
    {
        printf("%d:->",G->vertices[i].classid);
        for(p=G->vertices[i].firstarc;p!=NULL;p=p->nextarc)
        printf("%d->",p->adjvex);
        printf("NULL");
        printf("\n");
    }
}
void InitStack(SqStack *S)           //初始化栈
{
   S->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));    
     if (!S->base) 
    {
   printf("ERROR");
        exit(1);
     }
    S->top=S->base;
     S->stacksize=STACK_INIT_SIZE;
}
int StackEmpty(SqStack *S)    //判定栈空
{
    if(S->top==S->base)
        return OK;
    else
        return ERROR;
}
void Push(SqStack *S,int e)       //入栈
{   
    if(S->top - S->base >= S->stacksize)
    {
        S->base = (int *) realloc (S->base , (S->stacksize + STACKINCREMENT) * sizeof(int));   //realloc重新申请空间
        if(!S->base) 
        {
            printf("ERROR");
            exit(1);
        }
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *S->top++ = e;
}
int Pop(SqStack *S, int *e)        //出栈
{
    if(S->top == S->base) exit(1);
    *e = * --S->top;
    return 0;
}
void FindInDegree(ALGraph G, int indegree[])//求图中各节点的入度 
{
    int i;                  
    for (i = 1; i <= G.vexnum; i++)     //初始化各结点的入度
        indegree[i] = 0;
    
    for (i = 1; i <= G.vexnum; i++)
    {
        while (G.vertices[i].firstarc)
        {
            indegree[G.vertices[i].firstarc->adjvex]++;
            G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
        }
    }
}
void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)      //有向图G采用邻接表存储结构
{
     FILE *fp;
    fp=fopen("bianpai.txt","wt");     //wt按文本文件写入
    ArcNode *p;    
    SqStack S;
   int indegree[M]; //存放各节点的入度 
   int i,j, k;
    int count; //课程编排数目计数器
    int sumcredit;//每个学期的课程学分累加器
    
    FindInDegree(G, indegree);    //查找入度
    for (i = 1; i <= G.vexnum; i++)
      G.vertices[i].indegree=indegree[i];
    InitStack(&S);    
    count=0;
    k=0;
     while(count!=G.vexnum && k<=numterm)
    {
        sumcredit=0;
        for(i=1;i<=G.vexnum;i++) //入度为零的节点入栈，即无先修的课程入栈 
            if((G.vertices[i].indegree==0)&&(G.vertices[i].state=="NOTSTUDY"))
           {
                    Push(&S,i);
              G.vertices[i].state = "STUDY";//避免入度为零节点重复入栈 
            }
        if(!StackEmpty(&S)&&(sumcredit<=uplcredit))
        {   
          k= k+1;
            printf("\n");
            printf("第%d个学期学得课程有: ",k);
            sumcredit = 0;
        
          for(i=1;i<=G.vexnum;i++)//入度为零的节点入栈，即无先修的课程入栈 
                if((G.vertices[i].indegree==0)&&(G.vertices[i].state=="NOTSTUDY"))
                    Push(&S,i);
        
            while((!StackEmpty(&S))&&(sumcredit<uplcredit))//栈非空&&学分总数小于学分上限 
            {
                Pop(&S,&j);
                sumcredit = sumcredit + G.vertices[j].credit;
               if(sumcredit <= uplcredit)
               {
                    printf(" %s ",G.vertices[j].name);
                    fprintf(fp," %s ",G.vertices[j].name);
                    
                    count++;
                   for(p=G.vertices[j].firstarc;p;p=p->nextarc)//对j号顶点每个邻接点的入度减一
                        G.vertices[p->adjvex].indegree--;
                }
                else Push(&S,j);//将未输出的节点重新压入栈 
            }
        }   
    fprintf(fp,"\n");
    }
    printf("\n");
    if(count<G.vexnum)
        printf("\n课程编排出错\n");
    else
    {   
        printf("\n课程编排成功\n");
    }
    fclose(fp);
}
void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)
{
    FILE *fp;
    fp=fopen("bianpai.txt","wt");
    ArcNode *p;    
    SqStack S;
	int indegree[M];
    int i,j, k;
    int maxnum;
    int sumnum;
    int count; //课程编排数目计数器
    int sumcredit;//每个学期的课程学分累加器
    
    FindInDegree(G, indegree);

    for (i = 1; i <= G.vexnum; i++)
            G.vertices[i].indegree = indegree[i];

    InitStack(&S);
    count=0;
    k=0;
       maxnum = G.vexnum/numterm+1;
     sumnum = 0;
        
     while(count!=G.vexnum && k<=numterm)
    {
            for(i=1;i<=G.vexnum;i++) //入度为零的节点入栈，即无先修的课程入栈 
                   if((G.vertices[i].indegree==0)&&(G.vertices[i].state=="NOTSTUDY"))
                   {
                        Push(&S,i);
                            G.vertices[i].state = "STUDY";
                   }
            if(!StackEmpty(&S)&&(sumcredit<=uplcredit)&&(sumnum<=maxnum))
             {
                    k= k+1;
                     printf("\n");
                     printf("第%d个学期学得课程有:",k);
                     sumcredit = 0;
                     sumnum = 0;
             
                     for(i=1;i<=G.vexnum;i++)//入度为零的节点入栈，即无先修的课程入栈 
                         if((G.vertices[i].indegree==0)&&(G.vertices[i].state=="NOTSTUDY"))
                             Push(&S,i);
             
                     while((!StackEmpty(&S))&&(sumcredit<uplcredit)&&(sumnum<maxnum))
                    //栈非空&&学分总数小于学分上限&&学期课程数目小于学期最大数目 
                     {
                         Pop(&S,&j);//出栈
                         sumcredit = sumcredit + G.vertices[j].credit;
                            sumnum = sumnum+1;
             
                         if((sumcredit <= uplcredit)&&(sumnum <= maxnum))
                         {
                                printf(" %s ",G.vertices[j].name);                   
                                fprintf(fp," %s ",G.vertices[j].name);
                                count++;
               
                                   for(p=G.vertices[j].firstarc;p;p=p->nextarc)//对j号顶点每个邻接点的入度减一
                                       G.vertices[p->adjvex].indegree--;
                        }
                        else Push(&S,j); 
                    }
            }
    fprintf(fp,"\n");
    }
    printf("\n");
    if(count<G.vexnum)
        printf("课程编排出错\n");
    else
    {    
        printf("课程编排成功\n");
    }
    fclose(fp);
}

int main()            //主函数
{
    int numterm;   //学期总数
    int uplcredit; //一个学期的学分上限
    int selectway;   //选择编排的方式
    ALGraph G;
    
    printf("请输入学期总数: ");
    scanf("%d",&numterm);
    printf("请输入一个学期的学分上限: ");
    scanf("%d",&uplcredit);
    CreatGraph(&G);
    printf("请选择编排策略:   1.课程尽可能集中到前几个学期；  2.课程尽量均匀分布\n");
    scanf("%d",&selectway);
    
    if(selectway==1)
        TopologicalSort_1(G,numterm,uplcredit);
    if(selectway==2)
      TopologicalSort_2(G,numterm,uplcredit);
    system("pause");
    return 0;
}