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

中北大学
数据结构与算法课程设计
说 明 书

学 院、系：
软件学院
专 业:
软件工程
学 生 姓 名：

学 号:

设 计 题 目：
教学计划编制问题
起 迄 日 期:
2013年12月9日-2013年12月20日
指 导 教 师：

2013 年12月 20 日
1需求分析
1。 在大学的某个专业中选取几个课程作为顶点，通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息.
2. 本程序的目的是为用户编排课程，根据用户输入的信息来编排出每学期要学的课程。
3.测试数据：
学期总数：6；学分上限：9；本专业共开设12门课，课程号从C00到C11，学分顺序为2,3，4，3,2，3,4，4，7，5,2，3。
2概要设计
1.抽象数据类型图的定义如下：
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
2.栈的定义如下：
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.本程序有两个模块，调用关系简单：主程序模块 → 拓扑排序模块
3系统完成功能及功能框图
end
采用第二种策略：使课程尽可能地集中在前几个学期中
根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体
创建图CreateGraph（）：结合先修关系的AOV网，采用邻接链表存储

菜单OUTPUT()：显示代号所对应课程及课程的先修课程
前插法

main
拓扑排序TopoSort(G)：将课程排序后并决定出每学期所学课程

输出图G的信息Display(G)：将图的顶点和弧边输出

图3。1系统功能框图
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
^
图3。2 邻接表
对每个顶点求入度，并存入数组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
图3.3 拓扑排序流程图
C1
C4
C5
C7
C2
C3
C8
C9
C12
C10
C11
C6

图3.4 课程先修关系图
4 详细设计
1. 图的邻接表的存储表示，即结构体的定义：
typedef struct ArcNode
{
int AdjOfV； // 该弧所指向的顶点的位置
struct ArcNode ＊next; //指向下一条弧的指针
｝ArcNode；
typedef char VertexType［MAXOfNAME];
typedef struct //链接表
｛
VertexType data； //顶点信息
int grades; //存储学分信息
ArcNode *first； //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VER］； // 头结点
typedef struct
｛
AdjList ver； //vertices 存储课程名
int vexnum， arcnum; // 图的当前顶点数和弧数
｝ALGraph；
2。 建立图的邻接链表：
printf("请输入下列课程的先修课程（无先修课程输入0 结束后也输入0)\n”）；
for （h=0;h〈G.vexnum;++h) // 构造表结点链表,利用前插法
{
printf("％s的先修课程：”，G。ver[h］。data）;
scanf（”%s”,va）;getchar（)；
while （va［0]！='0’)
｛
i = LocateVex(G， va）； //弧头
j = h； //弧尾
p = （ArcNode＊）malloc(sizeof（ArcNode))；
p—>AdjOfV = j；
p—〉next = G。ver［i］.first; // 插在表头
G。ver[i］。first = p；
scanf（”％s”，va);
getchar(）;
｝
3。 输出图的顶点和边：
printf（”％d个顶点”， G。vexnum）;
for （i = 0；i < G。vexnum；++i）printf（”%4s”， G.ver［i］.data）；
printf（” \n%d条弧边:\n”，G.arcnum）；
for （i = 0；i 〈 G.vexnum；i++）
｛ p = G。ver［i］.first；
while (p）
｛ printf（"％s—-—-〉％s\n"，G。ver［i］。data，G.ver［p-〉AdjOfV］.data）；
p = p—>next；
}
｝ 
4。 通过栈实现拓扑排序:
   int TopologicalOrder（ALGraph G，AdjList R,struct Name name［]）
｛
int i， k, j = 0， count， indegree[MAX_VER］；
SqStack S；
ArcNode *p；
FindInDegree（G, indegree）； // 对各顶点求入度
InitStack（S); // 初始化栈
for (i = 0;i 〈 G。vexnum；++i） //建零入度顶点栈S
if （！indegree［i］) Push（S， i); // 入度为0者进栈
count = 0; // 对输出顶点计数
while (！StackEmpty（S））
｛
Pop（S， i）；
printf("%s(％d学分），”,G.ver［i]。data，G。ver[i］。grades)；
R[j++］ = G.ver［i]； //将当前的拓扑序列保存起来
++count； // 输出i号顶点并计数
for （p =G。ver[i］。first； p; p=p—>next)// 对i号顶点的每个邻接点的入度减1
｛
k = p->AdjOfV；
if （!（——indegree［k]）） // 若入度减为0，则入栈
Push(S， k)；
｝
｝
if (count 〈 G。vexnum)
｛
printf（”此有向图有回路无法完成拓扑排序”);
return 0;
｝
else printf( " 为一个拓扑序列"）；
printf（”\n"）;
int q=1，Z=0；
while （q <= TotalOfTerms)
｛
int C = R［Z］。grades ；
printf（”\n第%d个学期应学课程：",q)；
while （C 〈= MaxScores)
｛
C = C + R［Z+1］.grades；
if (Z 〈 G。vexnum)
{
CmpOfStr(R［Z］。data，name,N)；/＊让C1～C12分别与12门课程对应起来＊/
++Z；
}
}
printf（”\n”）;
if （q == TotalOfTerms）printf（ "\nOK Over!”)；
q++;
｝
return 1;/**/
｝
5。主程序和其他伪码算法：
void main（)
{
ALGraph G；
AdjList R；
Struct name；
name［N]=｛{”C1”｝，｛”C2”｝,｛"C3”}，｛"C4”｝，｛”C5”｝，｛”C6”｝，｛”C7”｝，｛"C8”｝，{”C9”｝，｛”C10”｝,｛”C11"｝,｛”C12”}}；
printf(" ＊*＊＊**＊*＊**＊＊*＊教学计划编制问题＊*＊＊＊****＊*＊*＊\n” ）；
printf（ "请以课件9-2上课程先序图为例输入学期总数:"）;
scanf（"%d",＆TotalOfTerms）；
getchar(）;
printf("请输入学期的学分上限(8或9）:");
scanf（"％d”,＆MaxScores）；
getchar(）；
CreateGraph（G);
Display(G）；
TopologicalOrder（G，R，name）;
｝
int InitStack（SqStack ＆S） /*栈的初始化*/
｛
S。a= (int ＊）malloc（StackofNUM ＊ sizeof(int)）；
if （！S。a)exit（—1)；
S。top =S。a;
S.size =StackofNUM；
return 1；
}
int StackEmpty(SqStack S） /*判断栈是否为空*/
｛
if (S。top == S。a）return 1；
else return 0；
}
int Push（SqStack ＆S, int x）/＊入栈＊/
｛
if (S.top — S.a 〉= S.size）
｛
S。a = （int ＊） realloc （ S。a， (S。size + StackforMore) * sizeof(int)）；
if （ !S。a ） exit（—1）；
S。top =S.a +S。size;
S。size +=StackforMore；
｝
*S。top++ = x；
return 1;
}
int Pop(SqStack ＆S， int &x) /＊出栈＊/
｛
if (S。top == S。a)return 0；
x = ＊--S。top；
return 1;
｝
int LocateVex（ALGraph G， VertexType u）/* 查找图中某个顶点位置 ＊/
{
int i;
for （i = 0；i 〈 G。vexnum；++i)
if （strcmp（u，G。ver［i］。data)==0）return i；
return -1;
｝
int CreateGraph（ALGraph &G） /＊采用邻接表存储结构＊/
｛
int i， j, h;
VertexType va;
ArcNode ＊p；
printf（”请输入教学计划的课程数： ” ）;
scanf（”%d"，＆G.vexnum)；
getchar(）；
printf（ ”请输入各个课程的先修课程的总和(弧总数）： ”)；
scanf（"%d”，＆G.arcnum);
getchar（）;
printf（ ”请输入%d个课程的课程号(最多％d个字符，字母+数字如C10)：”, G。vexnum，MAXOfNAME）;
for (i = 0；i < G.vexnum;++i)
｛
scanf(”%s”，＆G。ver[i].data）；
getchar（）;
G。ver[i]。first = NULL；
｝
printf（"请输入％d个课程的学分值:”，G.vexnum）；
for （i = 0；i 〈 G。vexnum；++i)
{
scanf（"%d”,＆G。ver[i]。grades)；getchar（)；
}
printf(”请输入下列课程的先修课程（无先修课程输入0 结束后也输入0)\n”）；
for （h=0;h<G。vexnum；++h） // 构造表结点链表,利用前插法
｛
printf（"％s的先修课程：”，G.ver[h］。data）;
scanf（”%s”，va）；getchar（）;
while （va[0］！=’0')
｛
i = LocateVex（G， va)； //弧头
j = h； //弧尾
p = (ArcNode＊)malloc(sizeof(ArcNode））；
p->AdjOfV = j；
p—〉next = G.ver［i]。first; // 插在表头
G.ver［i］。first = p;
scanf（”％s”，va)； getchar()；
}
}
return 1;
｝
void Display(ALGraph G） /* 输出图G的信息*/
｛
int i;
ArcNode *p；
printf（"有向图\n”）;
printf（”％d个顶点”， G.vexnum);
for （i = 0；i < G。vexnum；++i）printf（”％4s"， G。ver[i］。data);
printf（” \n％d条弧边:\n”，G.arcnum）；
for (i = 0；i 〈 G.vexnum；i++）
{ p = G。ver［i]。first；
while （p）
{ printf（”%s-———>％s\n”，G.ver[i］。data,G.ver［p—>AdjOfV］.data）;
p = p-〉next；
｝
｝
}
void FindInDegree（ALGraph G, int indegree[］） /＊求顶点的入度＊/
｛
int i；
ArcNode ＊p；
for (i = 0;i 〈 G。vexnum;i++） indegree［i] = 0;
for (i = 0；i 〈 G。vexnum；i++）
｛
p = G.ver［i］.first；
while （p)
{ indegree[p->AdjOfV］++；
p = p-〉next;
｝
｝
｝
struct Name
{char c［20］；
｝name；
void CmpOfStr（VertexType str，struct Name name[］，int n） /＊让C1~C12分别与12门课程对应起来*/
｛ if（strcmp（str,name［0］.c)==0）printf(” C程序设计”);
if(strcmp(str，name［1].c)==0）printf(" 模拟数字电路");
if（strcmp（str，name［2］。c）==0）printf（" 数据结构”）;
if(strcmp(str,name［3］.c)==0)printf(” C++面向对象 ”）；
if（strcmp（str,name［4］.c）==0)printf（” 大学英语 "）;
if（strcmp（str，name［5］。c)==0）printf(" 计算机组成原理”);
if(strcmp（str，name［6].c）==0）printf（" 传感器原理”）;
if(strcmp（str,name［7］.c）==0）printf(” 软件工程导论")；
if（strcmp（str,name[8］.c）==0)printf（” 高等数学”）;
if（strcmp（str，name[9］。c）==0）printf(" 线性代数”）;
if（strcmp（str，name[10］。c）==0）printf（” 大学物理基础"）;
if（strcmp(str,name[11］.c）==0）printf（" 电工技术"）;
｝
4 界面设计
5 源代码
＃include〈stdio。h〉
#include〈stdlib。h>
＃include〈math。h〉
＃include〈string。h〉
＃define N 12
＃define MAXOfNAME 3 //最多字符个数
#define MAX_VER 100 //最大顶点数
＃define StackofNUM 20 //存储空间初始分配量
＃define StackforMore 5 // 存储空间分配增量
int TotalOfTerms ； //学期总数
int MaxScores;
typedef struct SqStack
{
int *a；
int *top；
int size; //分配的存储空间
｝SqStack;
typedef struct ArcNode
｛
int AdjOfV； // 该弧所指向的顶点的位置
struct ArcNode *next; //指向下一条弧的指针
｝ArcNode；
typedef char VertexType[MAXOfNAME］;
typedef struct //链接表
{
VertexType data; //顶点信息
int grades； //存储学分信息
ArcNode ＊first; //指向第一条依附该顶点的弧的指针
}VNode， AdjList[MAX_VER］; // 头结点
typedef struct
{
AdjList ver; //vertices 存储课程名
int vexnum， arcnum； // 图的当前顶点数和弧数
}ALGraph； //学分上限
int InitStack(SqStack S） /＊栈的初始化＊/
｛
S.a= （int *）malloc(StackofNUM ＊ sizeof（int))；
if （！S。a）exit（-1)；
S.top =S。a；
S。size =StackofNUM；
return 1；
｝
int StackEmpty(SqStack S） /*判断栈是否为空＊/
{
if (S.top == S。a)return 1；
else return 0；
｝
int Push（SqStack S， int x）/＊入栈＊/
{
if (S。top — S。a >= S。size）
｛
S。a = (int ＊） realloc （ S。a, (S。size + StackforMore) ＊ sizeof（int)）；
if （ !S.a ） exit（—1）;
S.top =S.a +S。size；
S。size +=StackforMore;
｝
＊S.top++ = x；
return 1;
｝
int Pop(SqStack S， int x） /*出栈＊/
｛
if （S。top == S.a)return 0；
x = ＊--S。top;
return 1；
｝
int LocateVex(ALGraph G， VertexType u)/* 查找图中某个顶点位置 ＊/
｛
int i；
for （i = 0；i 〈 G。vexnum;++i）
if (strcmp(u，G.ver［i]。data)==0）return i;
return —1;
｝
int CreateGraph（ALGraph G） /*采用邻接表存储结构＊/
{
int i， j, h；
VertexType va；
ArcNode *p；
printf("请输入教学计划的课程数： ” ）;
scanf（"％d”，＆G.vexnum);
getchar（）;
printf( ”请输入各个课程的先修课程的总和(弧总数）： "）；
scanf（”％d",＆G。arcnum)；
getchar(）;
printf( ”请输入％d个课程的课程号（最多％d个字符,字母+数字如C10）:”, G。vexnum，MAXOfNAME）；
for (i = 0;i < G。vexnum;++i)
{
scanf（”％s"，&G。ver［i］。data）；
getchar（）；
G。ver［i］。first = NULL;
}
printf（”请输入％d个课程的学分值:”，G。vexnum)；
for (i = 0；i < G.vexnum；++i）
｛
scanf（"％d”，＆G。ver[i］。grades）；getchar()；
｝
printf（"请输入下列课程的先修课程（无先修课程输入0 结束后也输入0）\n”）;
for (h=0;h<G。vexnum；++h） // 构造表结点链表，利用前插法
｛
printf（"%s的先修课程:”，G。ver[h］。data）；
scanf（"％s”,va）；getchar（）;
while (va［0]!=’0’）
{
i = LocateVex(G, va)； //弧头
j = h； //弧尾
p = (ArcNode＊）malloc（sizeof（ArcNode）)；
p—〉AdjOfV = j；
p—〉next = G。ver[i]。first； // 插在表头
G。ver［i］.first = p;
scanf(”％s",va）； getchar（）；
｝
｝
return 1;
｝
void Display(ALGraph G） /＊ 输出图G的信息*/
｛
int i;
ArcNode ＊p；
printf（”有向图\n")；
printf（”％d个顶点”, G。vexnum);
for （i = 0；i 〈 G。vexnum;++i）printf（"％4s"， G。ver[i］。data）；
printf（" \n％d条弧边：\n"，G。arcnum）；
for （i = 0；i 〈 G。vexnum；i++)
{ p = G.ver［i］.first;
while (p）
｛ printf（"％s-———〉%s\n”，G。ver［i]。data，G.ver［p-〉AdjOfV].data)；
p = p->next；
｝
｝
｝
void FindInDegree（ALGraph G, int indegree［］) /＊求顶点的入度＊/
｛
int i;
ArcNode ＊p；
for (i = 0；i 〈 G。vexnum;i++) indegree［i］ = 0；
for （i = 0；i < G.vexnum;i++)
{
p = G.ver[i］。first；
while （p）
｛ indegree［p—〉AdjOfV］++；
p = p—〉next;
｝
｝
}
struct Name
｛
char c［20］；
}name;
void CmpOfStr（VertexType str,struct Name name[］，int n） /*让C1～C12分别与12门课程对应起来＊/
｛
if(strcmp（str,name［0]。c）==0）printf（" c程序设计"）；
if（strcmp(str，name［1].c)==0)printf(" 模拟数字电路")；
if（strcmp(str，name［2］。c)==0）printf（" 数据结构”）；
if（strcmp（str，name[3］.c）==0）printf(" C++面向对象 ”）；
if（strcmp（str,name［4].c)==0）printf（” 大学英语 ”)；
if（strcmp(str，name［5］.c）==0）printf（" 计算机组成原理");
if(strcmp（str，name［6].c)==0）printf(” 传感器原理”）;
if（strcmp（str，name［7］。c）==0）printf（" 软件工程导论 ”)；
if（strcmp(str，name［8］。c）==0)printf（" 高等数学”）；
if（strcmp(str,name［9]。c）==0）printf（” 线性代数”）；
if（strcmp（str,name[10]。c）==0）printf(” 大学物理基础"）；
if(strcmp（str，name［11]。c)==0）printf（” 电工技术”）;
}
int TopologicalOrder（ALGraph G，AdjList R，struct Name name［］)
｛
int i， k, j = 0， count, indegree［MAX_VER］;
char q=1，Z=0;
SqStack S；
ArcNode *p；
FindInDegree(G， indegree）； // 对各顶点求入度
InitStack（S）； // 初始化栈
for （i = 0；i 〈 G。vexnum;++i) //建零入度顶点栈S
if （!indegree[i］) Push（S, i）； // 入度为0者进栈
count = 0； // 对输出顶点计数
while （!StackEmpty（S））
｛
Pop（S, i)；
printf（”％s(％d学分）,"，G.ver［i］。data，G.ver［i］。grades）；
R[j++］ = G.ver［i］； //将当前的拓扑序列保存起来
++count； // 输出i号顶点并计数
for （p =G.ver[i］。first; p； p=p—〉next）// 对i号顶点的每个邻接点的入度减1
｛
k = p->AdjOfV；
if （!(——indegree[k］）） // 若入度减为0，则入栈
Push（S， k）；
｝
｝
if （count 〈 G。vexnum）
｛
printf（”此有向图有回路无法完成拓扑排序”）；
return 0；
｝
else printf（ " 为一个拓扑序列")；
printf(”\n”)；
while (q 〈= TotalOfTerms)
{
int C = R[Z]。grades ；
printf(”\n第%d个学期应学课程:”,q）;
while （C <= MaxScores)
{
C = C + R［Z+1].grades;
if （Z < G。vexnum)
｛
CmpOfStr(R[Z］。data,name，N）；/＊让C1～C12分别与12门课程对应起来＊/
++Z；
}
}
printf（"\n”)；
if （q == TotalOfTerms)printf( ”\nOK Over！”）;
q++；
｝
return 1；/**/
｝
int main（）
｛
ALGraph G;
AdjList R；
struct Name name［N]=｛｛”C1"｝,{"C2”｝,｛”C3”},{”C4”｝,｛”C5"｝,｛"C6”}，｛"C7"｝，{”C8"｝，｛"C9”｝,｛”C10”｝，｛"C11”｝，{”C12"｝｝；
printf（" *＊＊**＊***＊＊****教学计划编制问题＊＊*＊＊＊*＊＊＊*＊**\n” ）;
printf（" *＊**＊＊＊*＊＊＊＊製作人 张启尧 董茁华 **＊＊＊*＊**＊＊＊＊＊\n")；
printf（ "请输入学期总数："）;
scanf