教学计划编制数据结构课程设计报告(共27页).doc

精选优质文档-倾情为你奉上数据结构课程设计教学计划编制问题（图的应用）班级学号21333班学生姓名孙丽提交日期2015年7月23日成 绩 计算机与通信工程学院目 录一 需求分析··································································11.设计任务···································································12.功能模块图·································································13.流程图·····································································24.目标测试···································································2二 详细设计··································································41.运行环境···································································42.开发工具···································································43.涉及知识点·································································44.数据结构定义及基本操作·····················································45.函数调用关系图·····························································56.伪码流程···································································6三 调试分析··································································91.调试过程中遇到的问题与解决方法·············································92算法的时空分析·····························································93.改进思想···································································94.经验体会···································································9四 用户手册··································································9五 测试结果·································································111.输入······································································112.输出······································································14六 附录·····································································16七 参考文献·································································23专心-专注-专业一、需求分析1、设计任务教学计划编制问题（图的应用）问题描述大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。实现提示输入参数应包括：学期总数，一学期的学分上限，每门课的课程号（可以是固定占3位的字母数字串）、学分和直接先修课的课程号。应允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式可以自己设计。可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。2、功能模块图主程序模块栈的定义及操作拓扑排序模块图的定义及操作1、栈的顺序存储表示2、构造空栈3、判断栈是否为空4、入栈 5、出栈1、图的邻接表存储表示2、构造图3、求图中各节点的入度1、在有向图中选个没有前驱顶点且输出。2、从图中删除该顶点和所有以它为尾的弧。CreateGraph（）：构造图 InitStack（）：构造一个空栈 StackEmpty（）：判断是否为空栈 Push（）：入栈Pop（）：出栈 FindInDegree（）：求顶点的入度TopologicalSort（）：输出G顶点的拓扑排序结果3、流程图（具体流程图见详细设计伪码流程）主程序构造图GreateGraph ( )拓扑排序TopologicalSort开始结束4、目标测试正确测试：错误测试：二、详细设计1、运行环境：（1）WINDOWS 7系统（2）C-Free 5.02、开发工具： C语言3、涉及知识点：(1) 栈。用到有关栈的操作有初始化栈、判断栈是否为空、入栈和出栈。其中栈主要用来存放入度为零的顶点，即当前无先修关系可以编排的课程。(2) 图。用到有关图的操作有创建图、统计图中各顶点的入度。利用邻接表作为有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（indegree）。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点入度减一来实现。(3) 拓扑排序。 （a）在有向图中选一个没有前驱的顶点且输出之。 （b）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止，后一种情况则说明有向图中存在环。4、数据结构定义及基本操作A.所用存储结构及宏定义：#define MAX_VERTEX_NUM 100 /最大课程总数#define STACK_INIT_SIZE 100 /存储空间的初始分配量#define STACKINCREMENT 10    /存储空间的分配增量/图的邻接表存储表示typedef struct ArcNode int adjvex;/该弧所指向顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针ArcNode;typedef struct VNodechar name24;/课程名int classid; /课程号int credit;/课程的学分 int indegree;/该结点的入度 int state;/该节点的状态，1代表已学，0代表未学 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;/顶点向量int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;typedef int ElemType;/栈的顺序存储表示typedef struct /栈ElemType *base;ElemType *top;int stacksize;SqStack;B.程序中各函数的简要说明：（1） void CreatGraph(ALGraph &G)构建图。先输入各顶点（课程）的信息，包括课程名、课程号、课程学分。再输入弧信息（先修关系），将弧中顶点赋为弧尾，相应入度加1.最后输出构建好的邻接表。（2） void InitStack(SqStack &S)构造空栈int StackEmpty(SqStack &S)判断是否为空栈void Push(SqStack &S,int e)入栈 int Pop(SqStack &S, int *e)出栈（3） void FindInDegree(ALGraph G, int indegree)求图中各节点的入度。从每个节点的第一条依附于该节点的弧出发，将该节点对应的入度加1，接着指向下一条弧执行同样的操作，直至指针为空。（3）void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)按课程尽可能集中到前几个学期进行编排。当每个学期的学分总数不超过学分上限时，在有向图中选一个没有前驱的顶点（课程）且输出之。从图中删除该顶点（课程）和所有以它为尾的弧。当某学期的学分已满时，进入下一学期的编排。重复上述几步，直至全部顶点（课程）均已输出，或者当前图中不存在无前驱的顶点（课程）为止，后一种情况则说明有向图中存在环。（4）void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)按课程尽量均匀分布编排。当每个学期的学分总数不超过学分上限且课程数不超过课程数上限时，在有向图中选一个没有前驱的顶点（课程）且输出之。从图中删除该顶点（课程）和所有以它为尾的弧。当某学期的学分已满或课程数已满时，进入下一学期的编排。重复上述几步，直至全部顶点（课程）均已输出，或者当前图中不存在无前驱的顶点（课程）为止，后一种情况则说明有向图中存在环。（5）int main()主函数。在主函数中输出交互界面，要求用户输入各项信息。调用CreateGraph函数创建图，之后根据用户选择调用TopologicalSort_1或者TopologicalSort_2函数进行拓扑排序并输出编排结果，写入文件中。5、函数调用关系图Main函数GreateGraph ( )TopologicalSort_1或TopologicalSort _2FILE *fpFindInDegree ( )InitStack ( )Push ( )Pop ( )StackEmpty ( )6、伪码流程（1）void CreatGraph(ALGraph &G) （2）void FindInDegree(ALGraph G, int 构造图 indegree)求图中各节点的入度 (4) void TopologicalSort_1 (5)void TopologicalSort_2 (ALGraph G,int numterm, (ALGraph G,int numterm, int uplcredit) int uplcredit)有向图G采用邻接表存储结构 有向图G采用邻接表存储结构(6)Main主函数三、调试分析1、调试过程中遇到的问题与解决方法我在实验过程中遇到的最大难题是两个课程排序算法的编写。刚开始的时候没有任何的思路，书上、网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。经过三天的修改，终于写出了符合要求的排序算法。在设计过程中，我的程序有不少漏洞，例如在选择一次编排后，按任意键就会退出，不可以继续选择编排策略，经过一系列的修改，成功地将程序添加选择是否继续的功能。2、算法的时空分析对有n个顶点和e条弧的有向图而言，将建立求各顶点的入度的时间复杂度为O(e)；建立入度定点栈的时间复杂度为O(n)，在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减1的操作在while语句中总共执行e次，所以，总的时间复杂度为O(n+e)。3、改进思想A.程序界面有很大的改进空间，可设计更简洁美观的界面。B.输入数据比较繁琐，分步太多，可编写程序进行改善，如一步输入课程名、课程号、学分。C.课程号为01,02等形式，也可改为C1、C2的形式。4、经验体会在这次课设中，我进行了大量的资料查阅，包括上网查询和求助老师同学，对所学知识进行复习。通过这些努力，我对数据结构这门课程有了新的认识，对编程的步骤，有了具体的体会。更重要的是，这个课题完全脱离于只限于书本上的问题，多用在实际生活当中，让我对计算机行业，充满了信心和自豪。 以往我们学的计算机知识一般停留在理论上，这让我们不太理解计算机的应用和前景，而较少注重我们对算法的实践锻炼。而这一次的实习既需要我们去联系理论，又需要我们去实践方法，很多东西看上去都学过，但是和实际联系才知道变通的艰难。书上得来的并不是一切，大多还是需要在其它方面去吸收的，这是我这次课设的最大收获。这次的实验让我们知道该如何跨过实际和理论之间的鸿沟。四、用户手册1、 按照提示输入各个数据（如下图）：包括：学期总数，一学期的学分上限，编排课程总数，每门课的课程名、课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。课程名课程号学分先修关系程序设计基础012无离散数学02301数据结构03401,02汇编语言04301语言的设计和分析05203,04计算机原理06311编译原理07405,03操作系统08403,06高等数学097无线性代数10509普通物理11209数值分析12309,10,01先修顺序有向图：01104050212090811100607032、屏幕上会显示您输入的数据，确认无误后选择方案（如下图）：3、选择方案后会进行计算并输出，之后可根据需要选择是否继续（如下图）：五、测试结果1、输入2、输出策略1：bianpai1.txt策略2：bianpai2.txt六、附录源程序清单及其说明如下：#include "stdio.h"#include "malloc.h"#define MAX_VERTEX_NUM 100 /最大课程总数#define STACK_INIT_SIZE 100 /存储空间的初始分配量#define STACKINCREMENT 10 /存储空间的分配增量typedef struct ArcNode int adjvex;/该弧所指向顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针ArcNode;typedef struct VNodechar name24;/课程名int classid; /课程号int credit;/课程的学分 int indegree;/该结点的入度 int state;/该节点的状态，1代表已学，0代表未学 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;ALGraph;typedef int ElemType;typedef structElemType *base;ElemType *top;int stacksize;SqStack;void CreateGraph(ALGraph &G)/构建图int i, m, n;ArcNode *p;printf("请输入需要编排课程总数:");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=0;/NOTSTUDYG.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");return;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");return;S.top=S.base;S.stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack &S)if(S.top=S.base)return 1;elsereturn 0;void Push(SqStack &S,int e)if(S.top-S.base>=S.stacksize)S.base=(int*)realloc(S.base,(S.stacksize+10)*sizeof(int);if(!S.base) printf("ERROR");return;S.top=S.base+S.stacksize;S.stacksize+=10;*S.top+=e;int Pop(SqStack &S, int *e)if(S.top=S.base)return 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("bianpai1.txt","w");struct ArcNode *p;SqStack S;int indegreeMAX_VERTEX_NUM;/存放各节点的入度 int i,j,k;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=0)/入度为零的节点入栈，即无先修的课程入栈Push(S,i);G.verticesi.state =1;/避免入度为零节点重复入栈if(!StackEmpty(S)&&(sumcredit<=uplcredit)k= k+1;printf("n");printf("第%d个学期学得课程有:",k);sumcredit = 0;for(i=1;i<=G.vexnum;i+)if(G.verticesi.indegree=0)&&(G.verticesi.state=0)/入度为零的节点入栈，即无先修的课程入栈 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");elseprintf("n课程编排成功n");fclose(fp);void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)FILE *fp;fp=fopen("bianpai2.txt","w");struct ArcNode *p;SqStack S;int indegreeMAX_VERTEX_NUM;/存放各节点的入度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)sumcredit=0;for(i=1;i<=G.vexnum;i+) if(G.verticesi.indegree=0)&&(G.verticesi.state=0)/入度为零的节点入栈，即无先修的课程入栈Push(S,i);G.verticesi.state =1;/避免入度为零节点重复入栈if(!StackEmpty(S)&&(sumcredit<=uplcredit)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=0)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课程编排出错n");elseprintf("n课程编排成功n");fclose(fp);int main()/主函数 printf(" 教学计划编制问题n"); printf(" （拓扑排序AOV-网）nn"); /AOV-网：顶点表示活动，弧表示活动间优先关系的有向图；int CONTINUE=1; /while(CONTINUE!=0) printf("-n");int numterm;/学期总数int uplcredit; /一个学期的学分上限int selectway;ALGraph G;printf("请输入学期总数:");scanf("%d",&numterm);printf("请输入一个学期的学分上限:");scanf("%d",&uplcredit);CreateGraph(G); while(CONTINUE != 0)printf("请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布n");scanf("%d",&selectway);if(selectway=1)TopologicalSort_1(G,numterm,uplcredit);if(selectway=2)TopologicalSort_2(G,numterm,uplcredit); printf("n按1继续，按0结束:"); scanf("%d",&CONTINUE); return 0;七、 参考文献1. 谭浩强.C+程序设计（第2版）.北京：清华大学出版社,20112. 谭浩强.C程序设计（第四版）.北京：清华大学出版社，20103. 严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，2007