注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

独立观察员·网易

分享万岁

 
 
 

日志

 
 

[实验报告]教学计划编制问题  

2013-01-23 15:58:00|  分类: 原新浪博客的 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

杭州电子科技大学

计算机学院

 

数据结构课程设计

 

 

设计题目:教学计划编制问题

 

 

 

 

 

 

 

                                    网络工程      

       11052411      

       11054126      

       魏刘宏        

指导教师   王立波        

 

 

                                        20121229

 

 

 

一、    需求分析

1)问题描述

大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限,每学年含两学期,每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的,而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

2)基本要求

a.输入参数包括:学期总数,一学期的学分上限,每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。

b.允许用户指定下列两种编排策略之一:一是使学生在各学期中的学习负担尽量均匀;二是使课程尽可能地集中在前几个学期中。

c.若根据给定的条件问题无解,则报告适当的信息;否则,将教学计划输出到用户指定的文件中。计划的表格格式自行设计。

3)测试数据

学期总数:6

学分上限:10

该专业共开设课数:12

课程号:c01  c02  c03  c04  c05  c06  c07  c08  c09  c10  c11  c12

学分顺序:2  3  4  3  2  3  4  4  7  5  2  3

先修关系如下图:

c01 c04

c01 c02

c01 c03

c02 c03

c04 c05

c03 c05

c03 c07

c01 c12

c03 c08     

c09 c12

c09 c10

c09 c11    

c10 c12

c11 c06

c06 c08

c05 c07

 [实验报告]教学计划编制问题 - 独立观察员 - 独立观察员的博客

4)实现提示

可设学期总数不超过12,课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中,则作为错误处理。应建立内部课程号与课程号之间的对应关系。

 

二、    概要设计

typedef struct ArcNode{      

}ArcNode;

表节点(弧结构);

 

typedef struct{

}VNode, AdjList[MAX_VERTEX_NUM];

头结点;

 

typedef struct{

}ALGraph;

图结构;

 

int LocateVex(ALGraph G,VertexType u)

操作结果: G中存在顶点u,则返回该顶点在图中位置;否则返回-1

 

Status CreateGraph(ALGraph &G)

采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)

 

void Display(ALGraph G)

输出图的邻接矩阵G

 

void FindInDegree(ALGraph G,int indegree[])

求顶点的入度;

 

typedef struct SqStack{

}SqStack;

顺序栈;

 

Status InitStack(SqStack *S)

构造一个空栈S

 

void ClearStack(SqStack *S)

清空栈的操作;

 

Status StackEmpty(SqStack S)

若栈S为空栈,则返回TRUE,否则返回FALSE

 

Status Pop(SqStack *S,SElemType *e)

若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR

 

Status Push(SqStack *S,SElemType e)

插入元素e为新的栈顶元素;

 

Status zxf(ALGraph G)

求大学所有课程总学分;

 

Status TopologicalSort(ALGraph G)

程序的核心函数:

有向图G采用邻接表存储结构,若G无回路,则按用户选择的方案输出G的顶点的一个拓扑序列并返回OK, 否则返回ERROR

 

int main()

主函数;

 

三、    详细设计

#include<string.h>

#include<stdio.h>

#include<stdlib.h>

#include<iomanip>

#include<math.h> // floor(),ceil(),abs()

#include <iostream>

using namespace std;

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

typedef int Status; // Status是函数的返回类型;

typedef int Boolean;

#define MAX_NAME 10    //顶点字符串的最大长度;

#define MAX_CLASS_NUM 100

int Z=0;

int X=0;

int term_num,credit_lim,q=1;

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,vertices2;    //分别存课程名和学分;

        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 v1,v2;  //顶点信息;

     ArcNode * p;        //指向第一条依附某顶点的弧的指针;

  

     printf("请输入教学计划的课程数: ");

     scanf("%d",& G.vexnum);

     printf("请输入课程先修关系数(弧的数目): ");

     scanf("%d",& G.arcnum);

     printf("请输入%d个课程的代表值(:c01):\n",G.vexnum);

     for(i=0;i<G.vexnum;++i) {

               scanf("%s",G.vertices[i].data);

            G.vertices[i].firstarc=NULL;

     }

     printf("请输入%d个课程的学分值:\n",(G).vexnum);

     for(i=0;i<G.vexnum;++i) {

              scanf("%s",G.vertices2[i].data);

     }

     printf("请顺序输入每条弧的弧尾和弧头(以空格作为间隔):\n");

     for(k=0;k<G.arcnum;++k) {         

         scanf("%s%s",v1,v2);

            i=LocateVex(G,v1);

            j=LocateVex(G,v2);

            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  ",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;

     SElemType *top;

     int stacksize;

}SqStack;

 

Status InitStack(SqStack *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) { //清空栈的操作

         S->top=S->base;

}

 

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;

}

 

Status zxf(ALGraph G){ //求大学所有课程总学分;

         int z=0;

         for(int i=0; i < G.vexnum; i++){

                   z += atoi(G.vertices2[i].data);

         }

         return z;

}

typedef int pathone[MAX_CLASS_NUM];

typedef int pathtwo[MAX_CLASS_NUM];

Status TopologicalSort(ALGraph G){

        

  

   int i,k,count,indegree[MAX_VERTEX_NUM];

   bool has = false;

   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.vertices2[i].data;  //学分;

                   printf("课程%s→学分%s  ",G.vertices[i].data,G.vertices2[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\n");

                   has=true;

         }

        

         printf("请问您想使学生在各学期中的学习负担尽量均匀(输入1\n");

         printf("还是想使课程尽可能地集中在前几个学期中(输入2)?\n");

         int pattern;

         printf("请选择(1 or 2):");

         scanf("%d",&pattern);

 

       FindInDegree(G,indegree); //对各顶点求入度indegree[0..vernum-1] ;

         ClearStack(&S);

         printf("=====================================================\n");

         printf("教学计划如下:\n");

        int xq = 1; //学期数;

        int xfh;  //学分和;

         int now=0;

         int top = G.vexnum / term_num ;  //平均每学期课程数;

         int pjxf = zxf(G) / term_num ;  //每学期平均学分;

        

          

        while(xq <= term_num + 1){             

                 int result[20]; //某个学期的课程;

                 int m = 0;

                 xfh = 0;

                   now=0;   //当前学期课程数

                 for(i=0;i<G.vexnum;++i){         

                          if(0 == indegree[i])

                                     Push(&S,i);

                   }

                   if(xq == term_num+1 && !StackEmpty(S)){

                            printf("还有课程未安排!\n");

                   }

                 while(!StackEmpty(S) && xq <= term_num){

                            int xf;

                            Pop(&S,&i);  //弹出栈顶元素;

                            xf = atoi(G.vertices2[i].data); //atoi:字符串转换成整型数, xf:学分;

                            xfh = xfh+xf;

                            now++;

                            if(xfh > credit_lim){

                                      ClearStack(&S);

                                     break;

                            }

                            if(pattern == 1){

                                     if(xq!=term_num/2&&now>top){

                                               ClearStack(&S); //该操作使程序跳出此内层的while循环;

                                               now = 0;

                                               break;      

                                     }

                            }

                            if(pattern == 2){

                                     if(xq!=1&&xq!=term_num/2&&xq!=term_num/2-1&&now>top){

                                               ClearStack(&S);

                                               now = 0;

                                               break;

                                     }

                            }

                            indegree[i]--; //减为-1,避免被再次计入;

                            for(p=G.vertices[i].firstarc; p; p=p->nextarc){

                                     k=p->adjvex;

                                     indegree[k]--;

                                     if(indegree[k]==0)

                                               Push(&S,k);     

                            }

                            result[m]=i;

                            m++;

                    }

                    if(xq <= term_num){

                           printf("%d个学期的课程为:",xq);

                           for(int j=0; j<m; j++){

                                     printf("课程%s ",G.vertices[result[j]].data);

                           }

                    }

                  printf("\n");

                  xq++;

                    ClearStack(&S);     

        }

        printf("=====================================================\n");

         return OK;

}

 

int main(){  

     printf("                             教学计划编制问题\n");

    printf("                             (拓扑排序AOV-)\n\n");

     //AOV-:顶点表示活动,弧表示活动间优先关系的有向图;

         int CONTINUE = 1;

         //while(CONTINUE != 0){

                   printf("------------------------------------------------\n");

                   ALGraph f;       //图的邻接表存储;

               printf("请输入学期总数:");

               scanf("%d",&term_num);

               printf("请输入每学期的学分上限:");

               scanf("%d",&credit_lim);

               CreateGraph(f);

               Display(f);

         while(CONTINUE != 0){

               TopologicalSort(f);

                   printf("\n1继续,按0结束:");

                   scanf("%d",&CONTINUE);      

         }

    return 0;

}

四、    调试分析

1、  过程中出现一门课程重复输出的现象,经过调试分析,发现是因为输出一轮后,零入度顶点栈未清空。

2、  按各学期均匀的方案进行时,有课程未安排的现象,最后让个别学期(中间偏前)不按方案进行。

 

 

五、    用户手册

按照提示输入各个数据(如下图):

[实验报告]教学计划编制问题 - 独立观察员 - 独立观察员的博客

 

屏幕上会显示您输入的数据,确认无误后选择方案(如下图):

[实验报告]教学计划编制问题 - 独立观察员 - 独立观察员的博客

 

 

选择方案后程序会进行计算并输出,之后可选择是否继续(如下图):

[实验报告]教学计划编制问题 - 独立观察员 - 独立观察员的博客

 

六、    测试结果

[实验报告]教学计划编制问题 - 独立观察员 - 独立观察员的博客

[实验报告]教学计划编制问题 - 独立观察员 - 独立观察员的博客

[实验报告]教学计划编制问题 - 独立观察员 - 独立观察员的博客

七、    验收过程心得体会

有些程序往往没有标准答案,这就更需要不断优化!

  评论这张
 
阅读(22)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018