教学编制问题c语言数据结构实现.doc

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

数据结构
课程设计报告

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

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

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

4）拓扑排序TopologicalOrder (G)：将课程排序后并决定出每学期所学课程，输出图G的信息Display(G)：将图的顶点和弧边输出
三：程序模块及可实现的功能简介：
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;/**/
}
拓扑排序要点：依次将入度为0的顶点存入InDegree中，对每个顶点求入度，并存入数组InDegree[i]中（i=0…n），初始化栈Stack,Counter=0，对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Counter++)，推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Counter++），堆栈是否为空？，n个顶点全输出，依次将入度为0的顶点存入InDegree中
5)根据学分上限决定出每学期应学课程，其中R[ ]中存储的是经过拓扑排序后的课程先后顺序。        

    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++;
}
四：具体的源代码
本程序分为三部分
A:::::::::SeqStack.h

1） #define StackofNUM 20 //存储空间初始分配量
2） #define StackforMore 5 // 存储空间分配增量
3）
4） typedef struct SqStack
5） {
6） int *a;
7） int *top;
8） int size; //分配的存储空间
9） }SqStack;
10）
11） int InitStack(SqStack &S) /*栈的初始化*/
12） {
13） S.a= (int *)malloc(StackofNUM * sizeof(int));
14） if (!S.a)exit(-1);
15） S.top =S.a;
16） S.size =StackofNUM;
17） return 1;
18） }
19）
20） int StackEmpty(SqStack S) /*判断栈是否为空*/
21） {
22） if (S.top == S.a)return 1;
23） else return 0;
24） }
25） int Push(SqStack &S, int x)/*入栈*/
26） {
27） if (S.top - S.a >= S.size)
28） {
29） S.a = (int *) realloc ( S.a, (S.size + StackforMore) * sizeof(int));
30） if ( !S.a ) exit(-1);
31） S.top =S.a +S.size;
32） S.size +=StackforMore;
33） }
34） *S.top++ = x;
35） return 1;
36） }
37）
38） int Pop(SqStack &S, int &x) /*出栈*/
39） {
40） if (S.top == S.a)return 0;
41） x = *--S.top;
42） return 1;
43） }

B:::::::::ALGraph.h
44） #define MAXOfNAME 3 //最多字符个数
45） #define MAX_VER 100 //最大顶点数
46）
47） typedef struct ArcNode
48） {
49） int AdjOfV; // 该弧所指向的顶点的位置
50） struct ArcNode *next; //指向下一条弧的指针
51） }ArcNode;
52）
53） typedef char VertexType[MAXOfNAME];
54） typedef struct //链接表
55） {
56） VertexType data; //顶点信息
57） int grades; //存储学分信息
58） ArcNode *first; //指向第一条依附该顶点的弧的指针
59） }VNode, AdjList[MAX_VER]; // 头结点
60）
61） typedef struct
62） {
63） AdjList ver; //vertices 存储课程名
64） int vexnum, arcnum; // 图的当前顶点数和弧数
65） }ALGraph;
66）
67） int TotalOfTerms ; //学期总数
68） int MaxScores; //学分上限
69）
70） int LocateVex(ALGraph G, VertexType u)/* 查找图中某个顶点位置 */
71） {
72） int i;
73） for (i = 0;i < G.vexnum;++i)
74） if (strcmp(u,G.ver[i].data)==0)return i;
75） return -1;
76） }
77）
78） int CreateGraph(ALGraph &G) /*采用邻接表存储结构*/
79） {
80） int i, j, h;
81） VertexType va;
82） ArcNode *p;
83） printf("请输入教学计划的课程数: " );
84） scanf("%d",&G.vexnum);
85） getchar();
86） printf( "请输入各个课程的先修课程的总和(弧总数): ");
87） scanf("%d",&G.arcnum);
88） getchar();
89） printf( "请输入%d个课程的课程号(最多%d个字符,字母+数字如C10):", G.vexnum,MAXOfNAME);
90） for (i = 0;i < G.vexnum;++i)
91） {
92） scanf("%s",&G.ver[i].data);
93） getchar();
94） G.ver[i].first = NULL;
95） }
96）
97） printf("请输入%d个课程的学分值:",G.vexnum);
98） for (i = 0;i < G.vexnum;++i)
99） {
100） scanf("%d",&G.ver[i].grades);getchar();
101） }
102） printf("请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\n");
103） for (h=0;h<G.vexnum;++h) // 构造表结点链表,利用前插法
104） {
105） printf("%s的先修课程:",G.ver[h].data);
106） scanf("%s",va);getchar();
107） while (va[0]!='0')
108） {
109） i = LocateVex(G, va); //弧头
110） j = h; //弧尾
111） p = (ArcNode*)malloc(sizeof(ArcNode));
112） p->AdjOfV = j;
113） p->next = G.ver[i].first; // 插在表头
114） G.ver[i].first = p;
115） scanf("%s",va); getchar();
116） }
117） }
118） return 1;
119） }
120）
121） void Display(ALGraph G) /* 输出图G的信息*/
122） {
123） int i;
124） ArcNode *p;
125） printf("有向图\n");
126） printf("%d个顶点", G.vexnum);
127） for (i = 0;i < G.vexnum;++i)printf("%4s", G.ver[i].data);
128） printf(" \n%d条弧边:\n",G.arcnum);
129） for (i = 0;i < G.vexnum;i++)
130） { p = G.ver[i].first;
131） while (p)
132） { printf("%s---->%s\n",G.ver[i].data,G.ver[p->AdjOfV].data);
133） p = p->next;
134） }
135） }
136） }
137）
138）
139） void FindInDegree(ALGraph G, int indegree[]) /*求顶点的入度*/
140） {
141） int i;
142） ArcNode *p;
143） for (i = 0;i < G.vexnum;i++) indegree[i] = 0;
144） for (i = 0;i < G.vexnum;i++)
145） {
146） p = G.ver[i].first;
147） while (p)
148） { indegree[p->AdjOfV]++;
149） p = p->next;
150） }
151） }
152） }
153） struct Name
154） {
155） char c[20];
156） }name;
157）
158） void CmpOfStr(VertexType str,struct Name name[],int n) /*让C1~C12分别与12门课程对应起来*/
159） {
160）
161） if(strcmp(str,name[0].c)==0)printf(" 程序设计基础");
162） if(strcmp(str,name[1].c)==0)printf(" 离散数学");
163） if(strcmp(str,name[2].c)==0)printf(" 数据结构");
164） if(strcmp(str,name[3].c)==0)printf(" 汇编语言 ");
165） if(strcmp(str,name[4].c)==0)printf(" 语言的设计和分析 ");
166） if(strcmp(str,name[5].c)==0)printf(" 计算机原理");
167） if(strcmp(str,name[6].c)==0)printf(" 编译原理");
168） if(strcmp(str,name[7].c)==0)printf(" 操作系统 ");
169） if(strcmp(str,name[8].c)==0)printf(" 高等数学");
170） if(strcmp(str,name[9].c)==0)printf(" 线性代数");
171） if(strcmp(str,name[10].c)==0)printf(" 普通物理");
172） if(strcmp(str,name[11].c)==0)printf(" 数值分析");

C::::::::::::::::::教学计划编制问题.Cpp
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include "SeqStack.h"
#include "ALGraph.h"
#define N 12
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;/**/
}
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);
}
五：说明：
本程序按照课件9-2所显示的那12门课程编排，示列6个学期，每学期不超过学分数示例输入9。程序示例运行如下：

六：实验心得：
经过此次课程设计，我深刻地认识到自己写程序的不足，认识到了仅仅只是从课本上学到算法原理是远远不够的，理论与实践结合才是最重要的。实验中，我总是不经意间出现各种错误，这就要求
今后的我要以脚踏实地的态度来思考处理问题。总之本次课程设计，让我进一步熟悉了C语言的语句用法，学到了很多有用的知识。