教学计划编制问题课程设计数据结构(共32页).doc

精选优质文档-倾情为你奉上 攀枝花学院本科毕业设计（论文）教学计划编制问题学生姓名： 学生学号： 院 （系） 年级专业： 指导教师： 助理指导教师： 无 二一一年六月专心-专注-专业攀枝花学院本科学生课程设计任务书题目教学计划编制问题1、课程设计的目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）设计要求：针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。3、主要参考文献1数据结构（C语言版），严蔚敏，清华大学出版社，20032数据结构题集，严蔚敏，清华大学出版社，20053数据结构（C语言版），刘大有，高等教育出版社，20044Data Structure with C+，William FordWilliam Topp，清华大学出版社，20034、课程设计工作进度计划第1天 完成方案设计与程序框图 第2、3天 编写程序代码第4天 程序调试分析和结果第5天 课程设计报告和总结指导教师（签字）日期年 月 日教研室意见：年 月 日学生（签字）： 接受任务时间： 年 月 日注：任务书由指导教师填写。课程设计（论文）指导教师成绩评定表题目名称教学计划编制问题评分项目分值得分评价内涵工作表现20%01学习态度6遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。02科学实践、调研7通过实验、试验、查阅文献、深入生产实践等渠道获取与课程设计有关的材料。03课题工作量7按期圆满完成规定的任务，工作量饱满。能力水平35%04综合运用知识的能力10能运用所学知识和技能去发现与解决实际问题，能正确处理实验数据，能对课题进行理论分析，得出有价值的结论。05应用文献的能力5能独立查阅相关文献和从事其他调研；能提出并较好地论述课题的实施方案；有收集、加工各种信息及获取新知识的能力。06设计（实验）能力，方案的设计能力5能正确设计实验方案，独立进行装置安装、调试、操作等实验工作，数据正确、可靠；研究思路清晰、完整。07计算及计算机应用能力5具有较强的数据运算与处理能力；能运用计算机进行资料搜集、加工、处理和辅助设计等。08对计算或实验结果的分析能力（综合分析能力、技术经济分析能力）10具有较强的数据收集、分析、处理、综合的能力。成果质量45%09插图（或图纸）质量、篇幅、设计（论文）规范化程度5符合本专业相关规范或规定要求；规范化符合本文件第五条要求。10设计说明书（论文）质量30综述简练完整，有见解；立论正确，论述充分，结论严谨合理；实验正确，分析处理科学。11创新10对前人工作有改进或突破，或有独特见解。成绩指导教师评语指导教师签名： 年月日目 录摘 要4一 需求分析 51.1 实验内容和实验目的 51.2设计要求51.3理论与实践教学体系的关系5二 流程图设计 6三 概要设计 83.1 抽象数据类型图的定义 83.2主程序93.3程序模块调用关系10四 详细设计104.1头结点，表结点，邻接表的定义 104.2 栈的定义114.3 主程序和其他算法 11五 调试分析205.1 用户使用和说明 205.2 测试数据225.3 测试结果235.4 实验过程中出现的问题及解决方法 24六 实验分工24七 实验体会25八 参考文献26摘 要教学计划是学校保证教学质量和人才培养的关键，也是组织教学过程、安排教学过程、安排教学任务、确定教学编制的基本依据和课程安排的具体形式。是稳定教学秩序、提高教学质量的重要保证。从教学计划的设计、实施等方面，阐明了如何搞好教学管理，从而为提高教学质量提供保证。随着教育改革的不断深入和社会发展的需要，原旧的教学计划在定位上的方向性偏差，已经不再适应社会的需求。因此，应重视教学计划的改革和修订工作，以确保教育教学质量，提高教育教学水平。教学计划编制中的思路:一是明确培养目标;二是注重学科设置的整体性、统一性和灵活性、全面性;三是与学分制改革有机结合. 教学计划是高校实施常规教学活动的基本管理文档,由于传统的手工编制方式存在诸多弊端,开发基于Web应用程序形式的教学计划编制系统具有很好的应用价值。使用C程序设计语言,研究开发教学计划编制系统Web应用系统。关键词 教学计划 编制 培养目标 管理一 需求分析1.1实验内容和实验目的大学的每个专业都要编制教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限都相等。每个专业开设的课程都是确定的，而且课程的开设时间的安排必须满足先修关系。每个课程的先修关系都是确定的，可以有任意多门，也可以没有。每一门课程恰好一个学期。试在这样的情况下设置一个教学计划编制程序。在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息.本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程. 1.2设计要求针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。1.3理论与实践教学体系的关系 理论教学体系和实践教学体系是培养职业能力的两个主导因素是相互联系的，要处理好两者关系。基础理论教学要以应用为目的，以必需、够用为度，专业课教学要加强针对性和应用性。实践教学要改变过分依附理论教学的状况，探索建立相对独立的实践教学体系，形成基本实践能力与操作技能，专业技术应用能力与专业技能，综合实践能力与综合技能有机结合的实践教学体系。二 概要设计2.1抽象数据类型图的定义 ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:           R=VR           VR=(v,w)|v,wV,(v,w)表示v和w之间存在直接先修关系基本操作P:void CreatGraph(ALGraph *);void FindInDegree(ALGraph , int * );void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);ADT Graph栈的定义:ADT Stack   数据对象:D=ai|aiElemSet,i=1,2,n,n>=0     数据关系:R1=ai-1 ai|ai-1,aiD,i=2,n基本操作:void InitStack (SqStack *S);int StackEmpty(SqStack S);void Push(SqStack *S, int );int Pop(SqStack *S, int *e);ADT Stack2.2主程序 int main()            /主函数    int numterm;   /学期总数    int uplcredit; /一个学期的学分上限    int selectway;    ALGraph G;    printf("请输入学期总数:n");    scanf("%d",&numterm);    printf("请输入一个学期的学分上限:n");    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;三 代码设计3.1头结点，表结点，邻接表的定义#define MAX_VERTEX_NUM 100 /最大课程总数typedef struct ArcNode       int adjvex;        struct ArcNode *nextarc;        ArcNode;typedef struct VNode       char name24;       /课程名         int classid;      /课程号        int credit;         /课程的学分        int indegree;       /该结点的入度        int state;          /该节点的状态        ArcNode *firstarc; /指向第一条依附该顶点的弧的指针        VNode,AdjListMAX_VEXTEX_NUM;typedef struct        AdjList vertices;        int vexnum, arcnum;        ALGraph;邻接表的基本操作：void CreatGraph(ALGraph *);创建邻接表void FindInDegree(ALGraph , int * );求一个结点的入度void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);拓扑排序来编排课程void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);拓扑排序来编排课程3.2栈的定义#define STACk_INIT_SIZE 100 /存储空间的初时分配量#define STACKINCREMENT 10    /存储空间的分配增量typedef int ElemType;typedef struct        AdjList vertices;        int vexnum, arcnum;        ALGraph;基本操作：void InitStack (SqStack *S);栈的初始化int StackEmpty(SqStack S);判断栈是否为空void Push(SqStack *S, int );入栈操作int Pop(SqStack *S, int *e);出栈操作3.3主程序和其他算法int main()           /主函数 int numterm;   /学期总数    int uplcredit; /一个学期的学分上限    int selectway;    ALGraph G;    printf("请输入学期总数:n");    scanf("%d",&numterm);    printf("请输入一个学期的学分上限:n");    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;void CreatGraph(ALGraph *G)/构件图   int i, m, n;    ArcNode *p;    printf("请输入需要编排课程总数:n");    scanf("%d",&G->vexnum);    for( i=1;i<=G->vexnum;i+)            printf("请输入课程名n");        scanf("%s",&G->verticesi.name);         printf("请输入课程号n");        scanf("%d",&G->verticesi.classid);         printf("请输入该课程的学分n");        scanf("%d",&G->verticesi.credit);         G->verticesi.indegree=0;        G->vertices i.state=NOTSTUDY;        G->verticesi.firstarc=NULL;        printf("请输入课程先修关系总数：");    scanf("%d",&G->arcnum);     printf("请顺序输入每个课程先修关系(先修课程在前并以逗号作为间隔):n");    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->verticesn.firstarc;        G->verticesn.firstarc = p;        printf("n建立的邻接表为:n");          /输出建立好的邻接表    for(i=1;i<=G->vexnum;i+)            printf("%d:->",G->verticesi.classid);        for(p=G->verticesi.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);        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+)        indegreei = 0;    for (i = 1; i <= G.vexnum; i+)            while (G.verticesi.firstarc)                    indegreeG.verticesi.firstarc->adjvex+;            G.verticesi.firstarc = G.verticesi.firstarc->nextarc;            void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)     FILE *fp;    fp=fopen("bianpai.txt","w");    ArcNode *p;        SqStack S;   int indegreeM;/存放各节点的入度    int i,j, k, m,n;    int count; /课程编排数目计数器    int sumcredit;/每个学期的课程学分累加器    FindInDegree(G, indegree);    for (i = 1; i <= G.vexnum; i+)      G.verticesi.indegree=indegreei;    InitStack(&S);    count=0;    k=0;     while(count!=G.vexnum && k<=numterm)            sumcredit=0;        for(i=1;i<=G.vexnum;i+) /入度为零的节点入栈，即无先修的课程入栈             if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)                               Push(&S,i);              G.verticesi.state = STUDY;/避免入度为零节点重复入栈                     if(!StackEmpty(&S)&&(sumcredit<=uplcredit)                     k= k+1;            printf("n");            printf("第%d个学期学得课程有:n",k);            sumcredit = 0;          for(i=1;i<=G.vexnum;i+)/入度为零的节点入栈，即无先修的课程入栈                 if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)                    Push(&S,i);            while(!StackEmpty(&S)&&(sumcredit<uplcredit)/栈非空&&学分总数小于学分上限                             Pop(&S,&j);                sumcredit = sumcredit + G.verticesj.credit;               if(sumcredit <= uplcredit)                                   printf(" %s ",G.verticesj.name);                    fprintf(fp," %s ",G.verticesj.name);                    count+;                   for(p=G.verticesj.firstarc;p;p=p->nextarc)/对j号顶点每个邻接点的入度减一                        G.verticesp->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","w");    ArcNode *p;        SqStack S;    int indegreeM;    int i,j, k, m,n;       int maxnum;       int sumnum;    int count; /课程编排数目计数器    int sumcredit;/每个学期的课程学分累加器    FindInDegree(G, indegree);    for (i = 1; i <= G.vexnum; i+)            G.verticesi.indegree = indegreei;    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.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)                                           Push(&S,i);                            G.verticesi.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.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)                             Push(&S,i);                     while(!StackEmpty(&S)&&(sumcredit<uplcredit)&&(sumnum<maxnum)                    /栈非空&&学分总数小于学分上限&&学期课程数目小于学期最大数目                                               Pop(&S,&j);/出栈                         sumcredit = sumcredit + G.verticesj.credit;                            sumnum = sumnum+1;                         if(sumcredit <= uplcredit)&&(sumnum <= maxnum)                                                         printf(" %s ",G.verticesj.name);                                                   fprintf(fp," %s ",G.verticesj.name);                                count+;                                   for(p=G.verticesj.firstarc;p;p=p->nextarc)/对j号顶点每个邻接点的入度减一                                       G.verticesp->adjvex.indegree-;                                                else Push(&S,j);                                     fprintf(fp,"n");        printf("n");    if(count<G.vexnum)        printf("课程编排出错n");    else                printf("课程编排成功n");        fclose(fp);3.4程序模块调用关系 主程序模块  拓扑排序模块四 流程图设计流程图如下所示：void FindInDegree(ALGraph G, int indegree)/求图中各节点的入度（如图4.1）void CreatGraph(ALGraph *G)/构件图（如图4.2） 图4.1 图4.2void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) /有向图G采用邻接表存储结构(如图4.3)void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) /有向图G采用邻接表存储结构（如图4.4）图4.3 图4.4主函数：void main()图4.4五 调试分析5.1用户使用和说明使用VC+，打开教学计划编制问题.cpp文件，接着编译，无错误，然后重建也没有错误，最后执行该文件。要求输入学期总数、一个学期的学分上限、需要编排课程总数、课程名、课程号、该课程的学分，按照出现的每一步来输入该课程设计所提供的相关数据。然后还要输入课程先修课程总数，可以算出有16种关系，分别输出。接着程序会根据这些数据，自动生成建立好的邻接表，用户可以根据系统显示的选择编排策略进行选择，有两种编排策略，最后结果体现在实验的正确测试结果里。显示如下图：5.2测试数据学期总数：6；学分上限：10；该专业共开设12门课，课程号从01到12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。输入的内容如下:课程编号 课程名称    学分    先决条件01     程序设计基础      2      无02    离散数学   3         0103   数据结构      4      01，02 04   汇编语言       3        0105   语言的设计和分析   2        03，04 06  计算机原理      3        1107  编译原理      4      05，03 08  操作系统       4      03，06 09  高等数学       7         无 10  线性代数       5      0911  普通物理        2         0912  数值分析        3      09，10，01两种编排方法都输出结果为:第一学期学的课程有:高等数学 程序设计基础 第二学期学的课程有:普通物理 线性代数 汇编语言第三学期学的课程有:数值分析 计算机原理 离散数学第四学期学的课程有:数据结构第五学期学的课程有:操作系统 语言的设计和分析第六学期学的课程有:编译原理5.3测试结果正确测试结果：错误测试结果：5.4实验过程中出现的问题及解决方法我们在实验过程中遇到的最大难题是两个课程排序算法的编写。刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，