(完整word版)教学编制问题c语言数据结构实现.doc

(完整word版)教学编制问题c语言数据结构实现
(完整word版)教学编制问题c语言数据结构实现
(完整word版)教学编制问题c语言数据结构实现

数据结构
课程设计报告

主题：教学计划编制问题
学号：20091003768
班级：计科四班
姓名：熊金莲
指导老师：郭艳

内容概要
题目要求
教学计划编制问题的要点
函数模块及各函数可实现的功能简介
具体的源代码
使用说明
实验心得

一：题目要求如下：
大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
要求
（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）学分和直接先修课的课程号。
（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
二：教学计划编制问题的要点：
根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题——输出每学期的课程。
采用第二种策略：使课程尽可能地集中在前几个学期中；
根据教学计划中的课程及其关系和学分定义图的顶点和
边的结构体
创建图CreateGraph（）：结合先修关系的AOV网，显示代号所对应课程及课程的先修课程

4）拓扑排序TopologicalOrder(G)：将课程排序后并决定出每学期所学课程，输出图G的信息Display(G)：将图的顶点和弧边输出
三：程序模块及可实现的功能简介：
1）、图的邻接表的存储表示，即结构体的定义
typedefstructArcNode
{
intAdjOfV;//该弧所指向的顶点的位置
structArcNode*next;//指向下一条弧的指针
}ArcNode;

typedefcharVertexType[MAXOfNAME];
typedefstruct//链接表
{
VertexTypedata;//顶点信息
intgrades;//存储学分信息
ArcNode*first;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VER];//头结点

typedefstruct
{
AdjListver;//vertices存储课程名
intvexnum,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）、通过栈实现拓扑排序
intTopologicalOrder(ALGraphG,AdjListR,structNamename[])
{

inti,k,j=0,count,indegree[MAX_VER];
SqStackS;
ArcNode*p;
FindInDegree(G,indegree);//对各顶点求入度
InitStack(S);/