教学计划编制问题

课 程 设 计 报 告

课程名称 数据结构课程设计 课题名称 教学计划编制问题

专 业 网络工程 班 级 0902 学 号 ************ 姓 名 豪哥 指导教师 刘哥 陈哥 李姐

2011年 7 月 15 日

1

课 程 设 计 任 务 书

课程名称 数据结构课程设计 课 题 教学计划编制问题

专业班级 网络工程0902 学生姓名 豪哥 学 号 ************ 指导老师 刘哥 陈哥 李姐 审 批

任务书下达日期： 2011 年 6 月 26 日 任务完成日期： 2011 年 7 月 15 日 2

一、设计内容与设计要求 1．设计内容：

1）问题描述

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

2）基本要求

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

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

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

3）测试数据 学期总数：6； 学分上限：10； 该专业共开设课数：12 课程号：从C01到C12；

学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。 先修关系如下图：

9 1 4 2 7 12 3 5 10 6 11 8

3

4)实现提示

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

2．设计要求：

 课程设计报告规范

1)需求分析

a.程序的功能。 b.输入输出的要求。

2)概要设计

a.

程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每

个模块的功能。

b.

课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什

么样的结构，它们之间有什么关系等。

3)详细设计

a.采用C语言定义相关的数据类型。 b.写出各模块的类C码算法。

c.画出各函数的调用关系图、主要函数的流程图。

4)调试分析以及设计体会

a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。

b.程序调试中遇到的问题以及解决问题的方法。 c.课程设计过程经验教训、心得体会。

5)使用说明

用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。

6)书写格式

见附带说明。

7)附录

4

a.参考书目

b.源程序清单（带注释）

 考核方式

指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：

① 平时出勤 （占10%）

② 系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） ③ 程序能否完整、准确地运行，个人能否、熟练地调试程序（占40%） ④ 设计报告（占30%）

注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 ⑤ 完成情况（占10%）。

 课程验收要求

① 运行所设计的系统。 ② 回答有关问题。 ③ 提交课程设计报告。

④ 提交电子文档（源程序、设计报告文档）。

⑤ 依内容的创新程度，完善程序情况及对程序讲解情况打分。 二、进

度安排

第19周

上午 星期一 √ 星期二 星期三 星期四 星期五 8：00~12：00 下午 13：30~17：30 晚上 18：00~20：00 √ √ √ √

5

第20周 上午 8：00~12：00 下午 13：30~17：30 晚上 18：00~20：00

附：

课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。

正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。

正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。 正文总字数要求在5000字以上（不含程序原代码）。

星期一 √ 星期二 星期三 星期四 星期五

6

目录

一、课题的主要功能 ............................................ 8

1.1程序的功能 .............................................. 8 1.2.输入输出的要求 ......................................... 8 二、课题的功能模块的划分 ....................................... 8

2.1程序的模块组成 .......................................... 8 2.2模块的层次结构及调用关系 ................................ 9 2.3模块的主要功能 .......................................... 9 2.4数据结构和数据库结构 .................................... 9 三．主要功能的实现 ........................................... 10

3.1采用C语言定义相关的数据类型 ........................... 10 3.2主要函数的流程图 ....................................... 10 3.3画出各函数的调用关系图 ................................. 14 四、程序调试 ................................................. 15

4.1测试数据： ............................................. 15 4.2使用说明 ............................................... 15 五．总结 ..................................................... 17

5.1 程序调试中遇到的问题以及解决问题的方法 ................ 17 5.2 课程设计过程经验教训、心得体会 ........................ 17 六、附录 ..................................................... 18

6.1参考书目 ............................................... 18 6.2源程序清单（带注释） ................................... 18

7

一、课题的主要功能

1.1程序的功能

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

本程序针对本科的学期内容，通过输入实际的课程及先后关系。结合每学期的学分及课程数，制定好学习计划。在输入相关数据后，程序会安排好每学期的课程。

1.2.输入输出的要求

输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。

输出要求输出各门课程所对应的学分，以及每学期各门课程的安排。

二、课题的功能模块的划分

2.1程序的模块组成

LocateVex（）：图的邻接表存储的基本操作 CreateGraph（）：构造生成树 Display（）：输出图的邻接矩阵 FindInDegree（）：求顶点的入度 InitStack（）：构造一个空栈 ClearStack（）：清空栈

8

StackEmpty（）：判断是否为空栈 Pop（）：出栈 Push（）：入栈

TopologicalSort（）：输出G顶点的拓扑排序结果

2.2模块的层次结构及调用关系

Main()函数 TopologicalSort（）输出G顶点的拓扑Display（）输出图的邻接矩阵 CreateGraph（） 生成图

2.3模块的主要功能

见“详细设计”－“主要函数流程图”

2.4数据结构和数据库结构

储存的数据为结构体类型数组，以及结构体单链表结点类型。 1）typedef struct ArcNode 弧所指定点位置 int

2）typedef struct 顶点信息

指向下一条弧的指针 struct 网的权值指针 InfoType 第一个表结点的地址 9

VertexType ArcNode

三．主要功能的实现

3.1采用C语言定义相关的数据类型。

其中包括字符常量，整型，字符型，字符串型，typedef 定义的类型，结构体型，单链表节点类型，结构体数组。

3.2主要函数的流程图

1.LocateVex（）：图的邻接表存储的基本操作。由初始条件: 图G存在,u和G中顶点有相同特征转而进行判断，若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。

10

图LocateVex（）

图CreateGraph（）

图Display（）

2.CreateGraph（）：构造生成图。采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)。

3.Display（）：输出图的邻接矩阵。采用循环设置输出图的邻接矩阵。 4.FindInDegree（）：求顶点的入度。

11

图FindInDegree（）

图InitStack（）

5.InitStack（）：构造一个空栈。 6.ClearStack（）：清空栈。

7.StackEmpty（）：判断栈是否为空。若栈S为空栈，则返回TRUE，否则返回FALSE。

8.Pop（）：出栈。若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。

12

9.Push（）：入栈。插入元素e为新的栈顶元素。

10.TopologicalSort（）：输出G顶点的拓扑排序结果。有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, 否则返回ERROR。

13

3.3画出各函数的调用关系图

FindInDgreeMain函数 ( ) CreatGraph( ) InitStack( ) Display( ) Push （ ） StackEmptyTolopogicalsort（ ） ( ) Pop( ) Push （ ） FindInDegree( ) ClearStack( ) StackEmpty( ) 14

四、程序调试

4.1测试数据：

准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。

准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。

数据如下：学期总数：6；

学分上限：10； 该专业共开设课数：12 课程号：从C01到C12；

学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。 先修顺序：

11 123 4 1 2 5 7 9 10 6 8 4.2使用说明

输入学期总数，学分上限，课程数，先修关系边数，课程代表符号，相对学分值

15

输入完成后执行可得到每个学期的课程结果

16

五．总结

5.1 程序调试中遇到的问题以及解决问题的方法。

由于程序十分的复杂，遇到了很多常见的语法错误，及逻辑错误。这需要我们不断的调试分析。符号的格式之类，指针的用法，判断输入输出的条件都是十分容易出错的地方。在逐条排除，向同学老师请教后，程序终于得以完成。这让我明白了，解决问题，要细心认真，集思广益，这样才能把问题解决。

5.2 课程设计过程经验教训、心得体会。

虽然在大一我们已经学习了C语言，但是，直到本期我们才开设了数据结构这一门课程。这门课程让我们对程序的原理有了系统的认识。对以往模糊的经验，起了总结提升的作用。在学习了这门课程后，我们进行了2个星期的课程设计，以实践我们的学习内容。

在这次课程设计中，我被分配到了教学计划课程编制问题，开始感觉很难，因为我从未编写过如此复杂的程序。在多方查找资料并参考类似程序后，我大体将程序的构架描绘好了。一边对照着网上的资料，一边对程序进行修改补充，然后根据拟好的大纲进行编制。期间，我与其它同学进行了讨论和探究，对程序的细节问题和应用方面进行了探索，并解决了主要的问题，于是便着手写具体的程序。

这次实验，我进行了大量的资料查阅，包括向老师请求帮助解释题目要求，对所学知识进行复习。通过这些努力，我对算法有了更深入的理解，对编程的步骤，有了具体的体会。通过和同学的广泛交流，我体会到了合作的必要性及合作的优势。更重要的是，这个课题完全脱胎于实际问题，让我对计算机行业，充满了信心和自豪。

以往我们学的计算机知识一般停留在理论上，这让我们不太理解计算机的应用和前景，而较少注重我们对算法的实践锻炼。而这一次的实习既需要我们去联系理论，又需要我们去实践方法，很多东西看上去都学过，但是和实际联系才知道变通的艰难。纸上得来终觉浅，这是我这次实习的最大收获。这次的实验让我们知道该如何跨过实际和理论之间的鸿沟。

这次实习，我认识到了以下几个方面。

第一就是要合作。不懂的问题一定要向同学，老师请教。这样才能集思广益，有利

17

于问题的解决。也能够让自己节省时间，有效率的完成工作。齐心协力完成这个程序，互相帮助，这是我们同做课题的同学的共同体会。

第二就是要细心。程序的编制难免会出现错误，不能一次成功，出现错误后，一定要认真细心耐心的排查，这样千锤百炼，程序才能完成。在浮躁的时候能够静下心来思考，是极其重要的。

第三就是要学习。学习网上已经有的类似程序，学习他们的方法与思想。这样，才能最快的了解问题，得到启迪。

这两个星期的课程设计，让我受益匪浅。它不只对我们专业知识进行了加强，还锻炼了我们的思维能力，合作的精神，是我们理论与实际想结合。这些都是在书本上难以学习到的。这些弥足珍贵的经验和记忆，使我对我的未来从事的工作充满了信心，而最终程序的运行成功使我得到了莫大的满足。在日后的学习中，我会更加重视知识的积累，学好算法，为成为一名优秀的计算机专业人才努力。

六、附录

6.1参考书目

1.《数据结构教程》 李春葆等 编著 清华大学出版社 2.《数据结构教程上机实验指导》 李春葆等 编著 清华大学出版社

6.2源程序清单（带注释）

#include #include

#include // malloc()等 #include // INT_MAX等

#include // EOF(=^Z或F6),NULL #include // atoi()52 #include // eof()

#include // floor(),ceil(),abs() #include // exit() #include // cout,cin

18

// 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE -1

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE #define MAX_NAME 10

/* 顶点字符串的最大长度*/ #define MAXCLASS 100 int Z=0; int X=0;

int xqzs,q=1,xfsx; 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,verticestwo;

int vexnum,arcnum; /* 图的当前顶点数和弧数*/ int kind; /* 图的种类标志*/ }ALGraph;

/* 图的邻接表存储的基本操作*/

int LocateVex(ALGraph G,VertexType u)

{ /* 初始条件: 图G存在,u和G中顶点有相同特征*/

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

for(i=0;iif(strcmp(u,G.vertices[i].data)==0) return i; return -1;

19

}

Status CreateGraph(ALGraph *G)

{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图) */ int i,j,k;

VertexType va,vb; ArcNode *p;

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

printf(\"请输入拓扑排序所形成的课程先修关系的边数: \"); scanf(\"%d\

printf(\"请输入%d个课程的代表值(<%d个字符):\\n\ for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量*/ { scanf(\"%s\ (*G).vertices[i].firstarc=NULL; }

printf(\"请输入%d个课程的学分值(<%d个字符):\\n\ for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量*/ {scanf(\"%s\ }

printf(\"请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\\n\"); for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表*/ { scanf(\"%s%s\

i=LocateVex(*G,va); /* 弧尾*/ j=LocateVex(*G,vb); /* 弧头*/

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) { /* 输出图的邻接矩阵G */ int i;

ArcNode *p; switch(G.kind)

{case DG: printf(\"有向图\\n\"); }

printf(\"%d个顶点：\\n\ for(i=0;iprintf(\"%s \ printf(\"\\n%d条弧(边):\\n\ for(i=0;i20

{

p=G.vertices[i].firstarc; while(p)

{printf(\"%s→%s \->adjvex].data); p=p->nextarc; }

printf(\"\\n\"); } }

void FindInDegree(ALGraph G,int indegree[]) { /* 求顶点的入度，算法调用*/ int i;

ArcNode *p;

for(i=0;iindegree[i]=0; /* 赋初值*/ for(i=0;ip=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; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针*/

int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ /* 顺序栈的基本操作*/

Status InitStack(SqStack *S) { /* 构造一个空栈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; }

21

void ClearStack(SqStack *S) //清空栈的操作 {

S->top=S->base; }

Status StackEmpty(SqStack S)

{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top==S.base) return TRUE; else

return FALSE; }

Status Pop(SqStack *S,SElemType *e)

{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; return OK; }

Status Push(SqStack *S,SElemType e) { /* 插入元素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; }

typedef int pathone[MAXCLASS]; typedef int pathtwo[MAXCLASS]; Status TopologicalSort(ALGraph G) { /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */

/* 否则返回ERROR。*/

int i,k,j=0,count,indegree[MAX_VERTEX_NUM];

22

bool has=false; SqStack S; pathone a; pathtwo b; ArcNode *p;

FindInDegree(G,indegree); /* 对各顶点求入度indegree[0..vernum-1] */ InitStack(&S); /* 初始化栈*/

for(i=0;i//cout<<*G.vertices[i].data</* 入度为者进栈*/

count=0; /* 对输出顶点计数*/ while(!StackEmpty(S)) { /* 栈不空*/ Pop(&S,&i);

a[i]=*G.vertices[i].data; b[i]=*G.verticestwo[i].data;

printf(\"课程%s→学分%s \ /* 输出i号顶点并计数*/ ++count;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) { /* 对i号顶点的每个邻接点的入度减*/ k=p->adjvex;

if(!(--indegree[k])) /* 若入度减为,则入栈*/ {Push(&S,k);

//cout<<*G.vertices[i].data<if(count{printf(\"此有向图有回路\\n\"); return ERROR; } else

{printf(\"为一个拓扑序列。\\n\"); has=true; }

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

cout<<\"======================课程计划如下===============================\"<23

int xxf;

while(qq<=xqzs) {

int result[20]; int rtop=0; int nn=0;

//int ccount=0; // 学期学分计算 xxf=0;

for(i=0;iPush(&S,i); } }

while(!StackEmpty(S)) {

int bb;

Pop(&S,&i);

bb=atoi(G.verticestwo[i].data); xxf=xxf+bb; if(xxf>xfsx) {

break; }

indegree[i]--;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) { /* 对i号顶点的每个邻接点的入度减*/ k=p->adjvex; indegree[k]--;

/* if(!(--indegree[k])) 若入度减为,则入栈 {

Push(&S,k); }*/ }

result[rtop]=i; rtop++; }

cout<<\"第\"<cout<<\"课程\"<24

return OK; }

void main() { ALGraph f;

printf(\"教学计划编制问题的数据模型为拓扑排序AOV-网结构。\\n\"); printf(\"以下为教学计划编制问题的求解过程:\\n\"); printf(\"请输入学期总数:\"); scanf(\"%d\

printf(\"请输入学期的学分上限:\"); scanf(\"%d\ CreateGraph(&f); Display(f);

TopologicalSort(f); }

25

计算机与通信学院课程设计评分表

课题名称： 教学计划编制问题

项 目 设计方案的合理性与创造性 设计与调试结果 设计说明书的质量 答辩陈述与回答问题情况 课程设计周表现情况 综合成绩 评 价

教师签名： 日 期：

26