教学计划编制问题课程设计报告.doc

中北大学
数据结构与算法课程设计
说明书
 
学院、系:
软件学院
专业:
软件工程
学生姓名:
学号:
设计题目:
教学计划编制问题
起迄日期:
2013年12月9日-2013年12月20日
指导教师:
 
 
 
年12月 20 日
1需求分析
1. 在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息.
2. 本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程.
:
学期总数:6;学分上限:9;本专业共开设12门课,课程号从C00到C11,学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。
2概要设计
:
ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.
数据关系R:
R={VR}
VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}
基本操作P:
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph , int * );
int TopologicalOrder(ALGraph G,AdjList R,struct Name name[])
int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置*/
}ADT Graph
:
ADT Stack{
数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0}
数据关系:R1={﹤ai-1 ai﹥|ai-1,ai∈D,i=2,…,n}
基本操作:
void InitStack (SqStack *S);
int StackEmpty(SqStack S);
void Push(SqStack *S, int );
int Pop(SqStack *S, int *e);
}ADT Stack
,调用关系简单:主程序模块 →拓扑排序模块
3系统完成功能及功能框图
end
采用第二种策略:使课程尽可能地集中在前几个学期中
根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体
创建图CreateGraph():结合先修关系的AOV网,采用邻接链表存储
菜单OUTPUT():显示代号所对应课程及课程的先修课程
前插法
main
拓扑排序TopoSort(G):将课程排序后并决定出每学期所学课程
输出图G的信息Display(G):将图的顶点和弧边输出

0
C1
1 ^
5 ^
11 ^
11
10
6
7 ^
6 ^
4 ^
7
2 ^
11
3
4 ^
9 ^
1
C2
2
C3
3
C4
4
C5
5
C6
6
C7
^
7
C8
^
8
C9
9
C10
10
C11
11
C12
^

邻接表
对每个顶点求入度,并存入数组InDegree[i]中(i=0…n)
初始化栈Stack,Counter=0
Return OK
Return ERROR
依次将入度为0的顶点存入栈中
对以i号顶点为尾弧的每个邻接点的入度减1,并将入度减1后为零的顶点号压入栈中,输出i,计数器加1(Counter++)
推出栈顶的一个元素(入度为零的顶点号)至i,输出i,计数器加1(Counter++)
堆栈是否为空?
n个顶点全输出

Y Y
N


Y N
Y
拓扑排序流程图
C1
C4
C5
C7
C2
C3
C8
C9
C12
C10
C11
C6
课程先修关系图
4 详细设计
图的邻接表的存储表示,即结构体的定义:
typedef struct ode
{
int AdjOfV; // 该弧所指向的顶点的位置
struct ode *next; //指向下一条弧的指针
}ode;
typedef char VertexType[MAXOfNAME];
typedef struct //链接表
{
VertexType data; //顶点信息
int grades; //存储学分信息
ode *first; //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VER]; // 头结点
typedef struct
{
AdjList ve