教学计划编制数据结构课程设计报告

1、数据结构课程设计教学计划编制问题（图的应用）班级学号21333 班 2133326学生丽提交日期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 七 参考文

2、献 23一、需求分析1、设计任务 教学计划编制问题（图的应用） 问题描述 大学的每个专业都要制定教学计划。 假设任何专业都有固定的学习年限， 每学年含两学 期，每学期的时间长度和学分上限值均相等。 每个专业开设的课程都是确定的， 而且课程在 开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门， 也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 实现提示 输入参数应包括：学期总数，一学期的学分上限，每门课的课程号（可以是固定占 3 位的字母数字串） 、学分和直接先修课的课程号。应允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负

3、担尽量均匀； 二是使课程尽可能地集中在前几个学期中。若根据给定的条件问题无解， 则报告适当的信息； 否则将教学计划输出到用户指定的文 件中。计划的表格格式可以自己设计。可设学期总数不超过 12，课程总数不超过 100。如果输入的先修课程号不在该专业开设 的课程序列中，则作为错误处理。2、功能模块图CreateGraph （）：构造图InitStack （）：构造一个空栈StackEmpty （）：判断是否为空栈Push（）：入栈Pop（）：出栈FindInDegree （）：求顶点的入度TopologicalSort （）：输出 G 顶点的拓扑排序结果3、流程图 （具体流程图见详细设计伪码流程

4、）4、目标测试 正确测试：错误测试：二、详细设计1、运行环境：(1) WINDOWS 系7 统( 2) C-Free 5.02、开发工具：C 语言3、涉及知识点：(1) 栈。用到有关栈的操作有初始化栈、判断栈是否为空、入栈和出栈。其中栈主要用来存 放入度为零的顶点，即当前无先修关系可以编排的课程。(2) 图。用到有关图的操作有创建图、统计图中各顶点的入度。利用邻接表作为有向图的存 储结构，且在头结点中增加一个存放顶点入度的数组( indegree )。入度为零的顶点即为没 有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点入度减一来实现。(3) 拓扑排序。( a)在有向图中选一个没有

5、前驱的顶点且输出之。( b)从图中删除该顶点和所有以它为尾的弧。重复上述两步， 直至全部顶点均已输出， 或者当前图中不存在无前驱的顶点为止， 后 种情况则说明有向图中存在环。4、数据结构定义及基本操作A. 所用存储结构及宏定义：#define MAX_VERTEX_NUM 100/ 最大课程总数#define STACK_INIT_SIZE 100 / 存储空间的初始分配量#define STACKINCREMENT 10 / 存储空间的分配增量/ 图的邻接表存储表示typedef struct ArcNodeint adjvex; / 该弧所指向顶点的位置struct ArcNode *ne

6、xtarc; / 指向下一条弧的指针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;typed

7、ef 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

8、,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）按课程尽可能集中到前几个学期进行编排。当每个学期的学分总数不超过学分上限时， 在有向图中选一个没有前驱的顶点（课程）且输出之。从图中删除该

9、顶点（课程）和所有以 它为尾的弧。当某学期的学分已满时，进入下一学期的编排。 重复上述几步，直至全部顶点 （课程）均已输出，或者当前图中不存在无前驱的顶点（课程）为止，后一种情况则说明有 向图中存在环。（4）void TopologicalSort_2（ALGraph G,int numterm, int uplcredit）按课程尽量均匀分布编排。 当每个学期的学分总数不超过学分上限且课程数不超过课程 数上限时， 在有向图中选一个没有前驱的顶点 （课程）且输出之。 从图中删除该顶点 （课程） 和所有以它为尾的弧。 当某学期的学分已满或课程数已满时， 进入下一学期的编排。 重复上 述几步， 直

10、至全部顶点 （课程） 均已输出， 或者当前图中不存在无前驱的顶点 （课程） 为止， 后一种情况则说明有向图中存在环。（5）int main（）主函数。 在主函数中输出交互界面， 要求用户输入各项信息。 调用 CreateGraph 函数创 建图，之后根据用户选择调用 TopologicalSort_1 或者 TopologicalSort_2 函数进行拓扑排 序并输出编排结果，写入文件中。5、函数调用关系图2) void FindInDegree(ALGraph G,求图中各节点的入度int6、伪码流程1) void CreatGraph(ALGraph &G)构造图 indegree)(4)

11、void TopologicalSort_1 (ALGraph G,int numterm, int uplcredit)(5)void TopologicalSort_2 (ALGraph G,int numterm, int uplcredit)有向图 G采用邻接表存储结构有向图 G采用邻接表存储结构(6)Main 主函数三、调试分析1、调试过程中遇到的问题与解决方法 我在实验过程中遇到的最大难题是两个课程排序算法的编写。 刚开始的时候没有任何的 思路， 书上、网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经 过请教老师和同学以及翻阅了一些相关书籍， 并在网上的搜索有了

12、排序算法的大体思路。 经 过三天的修改，终于写出了符合要求的排序算法。在设计过程中，我的程序有不少漏洞，例如在选择一次编排后，按任意键就会退出， 不可以继续选择编排策略，经过一系列的修改，成功地将程序添加选择是否继续的功能。2、算法的时空分析对有 n 个顶点和 e 条弧的有向图而言，将建立求各顶点的入度的时间复杂度为O(e) ；建立入度定点栈的时间复杂度为 O(n) ，在拓扑排序过程中，若有向图无环，则每个顶点进 一次栈，出一次栈， 入度减 1 的操作在 while 语句中总共执行 e 次，所以， 总的时间复杂度 为 O(n+e) 。3、改进思想A.程序界面有很大的改进空间，可设计更简洁美观的

13、界面。B.输入数据比较繁琐， 分步太多， 可编写程序进行改善， 如一步输入课程名、 课程号、 学分。C. 课程号为 01,02 等形式，也可改为 C1、C2 的形式。4、经验体会在这次课设中， 我进行了大量的资料查阅， 包括上网查询和求助老师同学， 对所学知识 进行复习。 通过这些努力，我对数据结构这门课程有了新的认识， 对编程的步骤， 有了具体 的体会。更重要的是，这个课题完全脱离于只限于书本上的问题， 多用在实际生活当中，让 我对计算机行业，充满了信心和自豪。以往我们学的计算机知识一般停留在理论上，这让我们不太理解计算机的应用和前景， 而较少注重我们对算法的实践锻炼。 而这一次的实习既需要

14、我们去联系理论， 又需要我们去 实践方法， 很多东西看上去都学过， 但是和实际联系才知道变通的艰难。 书上得来的并不是 一切， 大多还是需要在其它方面去吸收的， 这是我这次课设的最大收获。 这次的实验让我们 知道该如何跨过实际和理论之间的鸿沟。四、用户手册1、 按照提示输入各个数据(如下图) ：包括：学期总数，一学期的学分上限，编排课程总数，每门课的课程名、课程号( 固定占 3 位的字母数字串 ) 、学分和直接先修课的课程号课程名课程号学分先修关系程序设计基础012无离散数学02301数据结构03401,02汇编语言04301语言的设计和分析05203,04计算机原理06311编译原理0740

15、5,03操作系统08403,06高等数学097无线性代数10509普通物理11209数值分析12309,10,01先修顺序有向图：0405020307011208091006112、屏幕上会显示您输入的数据，确认无误后选择方案（如下图）3、选择方案后会进行计算并输出，之后可根据需要选择是否继续（如下图）五、测试结果1、输入请攒入学題总数汴 谢臥一翠誉期的学分=10 请猛入需要编排课程总数：12请输入课程名:程序设计基础请输入课程号：01 请输入该课程的学分：2 请输入课程名:离散数学 请输入课程号：02请输入该课程的学分：3 请输入课程名:数据结构请输入课程号：03 请输入该课程的学分泊 请输

16、入课程名:汇编语言请输入课程号:94请输入该课程的学分：3请输入课程名:语言的设计和分析谙输入课程号:05请输入该课程的学分汐请输入课程名:计算机原理 半：Ill请输入课程号；06I请输入该课程的学分：3 请输入课程名:编译原理 请输入课程号 请输入该课程的学分：4 |请输入课程名:操作系统I请输入课程号:08请输入该课程的学分：4 请输人课程名：高手敖学 |请输入课程号:09请输入该课程的学分汐 请输入课程缶线性代数 请输入课程号:価请输入该课程的学分：5请输人课程名:昔通物理请输入课程号:口请输入该课程的学分：2洁渝人.课程名嘲值升析请输入课程号：12请输入该虞程的学分：3IH2、输出策略

17、 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 ArcNodeint adjvex;/ 该弧所指向顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针ArcNode;typedef struct V

18、Nodechar 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

19、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.);printf(n 请输入课程号 :); scanf(%d,&G.verticesi.classid);printf(n 请输入该课程的学分 :); scanf(%d,&G.verticesi.credit);G.verti

20、cesi.indegree=0;G.vertices i.state=0;/NOTSTUDYG.verticesi.firstarc=NULL;printf( 请输入课程先修关系总数： );scanf(%d,&G.arcnum);):n);printf( 请顺序输入每个课程先修关系 ( 先修课程在前并以逗号作为间隔 for (i = 1; i = G.arcnum; i+)printf(n 请输入存在先修关系的两个课程的序号 :); scanf(%d,%d,&n,&m);while (nG.vexnum|mG.vexnum)printf( 输入的顶点序号不正确请重新输入 :); scanf(%

21、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.verticesi.classid); for(p=G.verticesi.firstarc;p!=NULL;p=p-nextarc)printf(

22、%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.stac

23、ksize)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.vexnu

24、m; i+)indegreei = 0;for (i = 1; i 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;

25、/ 每个学期的课程学分累加器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;/ 避免入度为

26、零节点重复入栈 if(!StackEmpty(S)&(sumcredit=uplcredit)k= k+1;printf(n);printf( 第 %d个学期学得课程有 :,k); sumcredit = 0;for(i=1;i=G.vexnum;i+)入度为零的节点入栈非空 &学对jif(G.verticesi.indegree=0)&(G.verticesi.state=0)/ 栈，即无先修的课程入栈Push(S,i);while(!StackEmpty(S)&(sumcredituplcredit)/ 分总数小于总学分上限Pop(S,&j);sumcredit = sumcredit +

27、 G.verticesj.credit; if(sumcredit nextarc)/ 号顶点每个邻接点的入度减一G.verticesp-adjvex.indegree-;else Push(S,j);/将未输出的节点重新压入栈 fprintf(fp,n);printf(n);if(countG.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

28、);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;w

29、hile(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)&(sumcredituplcre