教学计划编制数据结构专业课程设计报告样本.doc

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

数据结构课程设计

教学计划编制问题（图的应用）

班级学号
21333班2133326
学生姓名
孙丽
提交日期
2015年7月23日
成 绩

计算机与通信工程学院
目 录
一 需求分析··································································1
···································································1
·································································1
·····································································2
···································································2
二 详细设计··································································4
···································································4
···································································4
·································································4
·····················································4
·····························································5
···································································6
三 调试分析··································································9
·············································9
2．算法的时空分析·····························································9
···································································9
···································································9
四 用户手册··································································9
五 测试结果·································································11
······································································11
······································································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
2、开发工具：
C语言
3、涉及知识点：
(1) 栈。用到有关栈的操作有初始化栈、判断栈是否为空、入栈和出栈。其中栈主要用来存放入度为零的顶点，即当前无先修关系可以编排的课程。
(2) 图。用到有关图的操作有创建图、统计图中各顶点的入度。利用邻接表作为有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（indegree）。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点入度减一来实现。
(3) 拓扑排序。
（a）在有向图中选一个没有前驱的顶点且输出之。
（b）从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止，后一种情况则说明有向图中存在环。

4、数据结构定义及基本操作
：
#define MAX_VERTEX_NUM 100 //最大课程总数
#define STACK_INIT_SIZE 100 //存储空间的初始分配量
#define STACKINCREMENT 10    //存储空间的分配增量
//图的邻接表存储表示
typedef struct ArcNode
{
int adjvex;//该弧所指向顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
}ArcNode;
typedef struct VNode
{
char name[24];//课程名
int classid; //课程号
int credit;//课程的学分
int indegree;//该结点的入度
int state;//该节点的状态，1代表已学，0代表未学
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;//顶点向量
int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
typedef int ElemType;
//栈的顺序存储表示
typedef struct //栈
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;

：
（1） void CreatGraph(ALGraph &G)
构建图。先输入各顶点（课程）的信息，包括课程名、课程号、课程学分。再输入弧信息（先修关系），将弧中顶点赋为弧尾，。
（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 _2
FILE *fp
FindInDegree ( )
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、改进思想
，可设计更简洁美观的界面。
，分步太多，可编写程序进行改善，如一步输入课程名、课程号、学分。
,02等形式，也可改为C1、C2的形式。

4、经验体会
在这次课设中，我进行了大量的资料查阅，包括上网查询和求助老师同学，对所学知识进行复习。通过这些努力，我对数据结构这门课程有了新的认识，对编程的步骤，有了具体的体会。更重要的是，这个课题完全脱离于只限于书本上的问题，多用在实际生活当中，让我对计算机行业，充满了信心和自豪。 
以往我们学的计算机知识一般停留在理论上，这让我们不太理解计算机的应用和前景，而较少注重我们对算法的实践锻炼。而这一次的实习既需要我们去联系理论，又需要我们去实践方法，很多东西看上去都学过，但是和实际联系才知道变通的艰难。书上得来的并不是一切，大多还是需要在其它方面去吸收的，这是我这次课设的最大收获。这次的实验让我们知道该如何跨过实际和理论之间的鸿沟。

四、用户手册
1、 按照提示输入各个数据（如下图）：
包括：学期总数，一学期的学分上限，编排课程总数，每门课的课程名、课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。
课程名
课程号
学分
先修关系
程序设计基础
01
2
无
离散数学
02
3
01
数据结构
03
4
01,02
汇编语言
04
3
01
语言的设计和分析
05
2
03,04
计算机原理
06
3
11
编译原理
07
4
05,03
操作系统
08
4
03,06
高等数学
09
7
无
线性代数
10
5
09
普通物理
11
2
09
数值分析
12
3
09,10,01
先修顺序有向图：
011
04
05
02
12
09
08
11
10
06
07
03

2、屏幕上会显示您输入的数据，确认无误后选择方案（如下图）：

3、选择方案后会进行计算并输出，之后可根据需要选择是否继续（如下图）：

五、测试结果
1、输入

2、输出

策略1：

策略2：

六、附录
源程序清单及其说明如下：
#include ""
#include ""
#define MAX_VERTEX_NUM 100 //最大课程总数
#define STACK_INIT_SIZE 100 //存储空间的初始分配量
#define STACKINCREMENT 10 //存储空间的分配增量
typedef struct ArcNode
{
int adjvex;//该弧所指向顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
}ArcNode;
typedef struct VNode
{
char name[24];//课程名
int classid; //课程号
int credit;//课程的学分
int indegree;//该结点的入度
int state;//该节点的状态，1代表已学，0代表未学
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef int ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
void CreateGraph(ALGraph &G)//构建图
{
int i, m, n;
ArcNode *p;
printf("请输入需要编排课程总数:");
scanf("%d",&);
for( i=1;i<=;i++)
{
printf("\n请输入课程名:");
scanf("%s",&[i].name);
printf("\n请输入课程号:");
scanf("%d",&[i].classid);
printf("\n请输入该课程的学分:");
scanf("%d",&[i].credit);
[i].indegree=0;
[i].state=0;//NOTSTUDY
[i].firstarc=NULL;
}
printf("请输入课程先修关系总数：");
scanf("%d",&);
printf("请顺序输入每个课程先修关系(先修课程在前并以逗号作为间隔):\n");
for (i = 1; i <= ; i++)
{
printf("\n请输入存在先修关系的两个课程的序号:");
scanf("%d,%d",&n,&m);
while (n<0||n>||m<0||m>)
{
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=[n].firstarc;
[n].firstarc = p;
}
printf("\n建立的邻接表为:\n");//输出建立好的邻接表
for(i=1;i<=;i++)
{
printf("%d:->",[i].classid);
for(p=[i].firstarc;p!=NULL;p=p->nextarc)
printf("%d->",p->adjvex);
printf("NULL");
printf("\n");
}
}
void InitStack(SqStack &S)
{
=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
if (!)
{
printf("ERROR");
return;
}
=;
=STACK_INIT_SIZE;
}
int StackEmpty(SqStack &S)
{
if(==)
return 1;
else
return 0;
}
void Push(SqStack &S,int e)
{
if(>=)
{
=(int*)realloc(,(+10)*sizeof(int));
if(!)
{
printf("ERROR");
return;
}
=+;
+=10;
}
*++=e;
}
int Pop(SqStack &S, int *e)
{
if(==)
return 1;
*e=*;
return 0;
}
void FindInDegree(ALGraph G, int indegree[])//求图中各节点的入度
{
int i;
for (i = 1; i <= ; i++)
indegree[i] = 0;
for (i = 1; i <= ; i++)
{
while ([i].firstarc)
{
indegree[[i].firstarc->adjvex]++;
[i].firstarc = [i].firstarc->nextarc;
}
}
}
void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)
{
FILE *fp;
fp=fopen("","w");
struct ArcNode *p;
SqStack S;
int indegree[MAX_VERTEX_NUM];//存放各节点的入度
int i,j,k;
int count; //课程编括排数目计数器
int sumcredit;//每个学期的课程学分累加器
FindInDegree(G,indegree);
for (i = 1; i <= ; i++)
[i].indegree=indegree[i];
InitStack(S);
count=0;
k=0;
while(count!= && k<=numterm)
{
sumcredit=0;
for(i=1;i<=;i++)
if(([i].indegree==0)&&([i].state==0))//入度为零的节点入栈，即无先修的课程入栈
{
Push(S,i);
[i].state =1;//避免入度为零节点重复入栈
}
if((!StackEmpty(S))&&(sumcredit<=uplcredit))
{
k= k+1;
printf("\n");
printf("第%d个学期学得课程有:",k);
sumcredit = 0;
for(i=1;i<=;i++)
if(([i].indegree==0)&&([i].state==0))//入度为零的节点入栈，即无先修的课程入栈
Push(S,i);
while((!StackEmpty(S))&&(sumcredit<uplcredit))//栈非空&&学分总数小于总学分上限
{
Pop(S,&j);
sumcredit = sumcredit + [j].credit;
if(sumcredit <= uplcredit)
{
printf(" %s ",[j].name);
fprintf(fp," %s ",[j].name);
count++;
for(p=[j].firstarc;p;p=p->nextarc)//对j号顶点每个邻接点的入度减一
[p->adjvex].indegree--;
}
else Push(S,j);//将未输出的节点重新压入栈
}
}
fprintf(fp,"\n");
}
printf("\n");
if(count<)
printf("\n课程编排出错\n");
else
{
printf("\n课程编排成功\n");
}
fclose(fp);
}
void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)
{
FILE *fp;
fp=fopen("","w");
struct ArcNode *p;
SqStack S;
int indegree[MAX_VERTEX_NUM];//存放各节点的入度
int i,j,k,m,n;
int maxnum;
int sumnum;
int count; //课程编排数目计数器
int sumcredit;//每个学期的课程学分累加器
FindInDegree(G,indegree);
for (i = 1; i <= ; i++)
[i].indegree=indegree[i];
InitStack(S);
count=0;
k=0;
maxnum=+1;
sumnum=0;
while(count!= && k<=numterm)
{
sumcredit=0;
for(i=1;i<=;i++)
if(([i].indegree==0)&&([i].state==0))//入度为零的节点入栈，即无先修的课程入栈
{
Push(S,i);
[i].state =1;//避免入度为零节点重复入栈
}
if((!StackEmpty(S))&&(sumcredit<=uplcredit))
{
k= k+1;
printf("\n");
printf("第%d个学期学得课程有:",k);
sumcredit = 0;
sumnum=0;
for(i=1;i<=;i++)//入度为零的节点入栈，即无先修的课程入栈
if(([i].indegree==0)&&([i].state==0))
Push(S,i);
while((!StackEmpty(S))&&(sumcredit<uplcredit)&&(sumnum<maxnum))//栈非空&&学分总数小于学分上限&&不超过每学期课程上限
{
Pop(S,&j);
sumcredit = sumcredit + [j].credit;
sumnum=sumnum+1;
if((sumcredit<=uplcredit)&&(sumnum<=maxnum))
{
printf(" %s ",[j].name);
fprintf(fp," %s ",[j].name);
count++;
for(p=[j].firstarc;p;p=p->nextarc)//对j号顶点每个邻接点的入度减一
[p->adjvex].indegree--;
}
else Push(S,j);//将未输出的节点重新压入栈
}
}
fprintf(fp,"\n");
}
printf("\n");
if(count<)
printf("\n课程编排出错\n");
else
{
printf("\n课程编排成功\n");
}
fclose(fp);
}
int main()//主函数
{
printf(" 教学计划编制问题\n");
printf(" （拓扑排序AOV-网）\n\n");
//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("请选择编排策略:；\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. ++程序设计（第2版）.北京：清华大学出版社,2011
2. （第四版）.北京：清华大学出版社，2010
3. 严蔚敏，（C语言版）.北京：清华大学出版社，2007