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

1、数据结构课程设计报告主题：教学计划编制问题学号：20091003768班级：计科四班姓名：熊金莲指导老师：郭艳内容概要（1） 题目要求（2） 教学计划编制问题的要点（3） 函数模块及各函数可实现的功能简介（4） 具体的源代码（5） 使用说明（6） 实验心得一：题目要求如下：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。要求（1）输入

2、参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）学分和直接先修课的课程号。 （2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。二：教学计划编制问题的要点：根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题输出每学期的课程。1） 采用第二种策略：使课程尽可能地集中在前几个学期中；2） 根据教

3、学计划中的课程及其关系和学分定义图的顶点和边的结构体3） 创建图CreateGraph（）：结合先修关系的AOV网，显示代号所对应课程及课程的先修课程4）拓扑排序TopologicalOrder (G)：将课程排序后并决定出每学期所学课程，输出图G的信息Display(G)：将图的顶点和弧边输出三：程序模块及可实现的功能简介： 1）、图的邻接表的存储表示，即结构体的定义typedef struct ArcNodeint AdjOfV; / 该弧所指向的顶点的位置struct ArcNode *next; /指向下一条弧的指针ArcNode;typedef char VertexTypeMAXO

4、fNAME; typedef struct /链接表VertexType data; /顶点信息int grades; /存储学分信息ArcNode *first; /指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VER; / 头结点typedef structAdjList ver; /vertices 存储课程名int vexnum, arcnum; / 图的当前顶点数和弧数ALGraph; 2）、利用前插法，建立图的邻接链表printf("请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)n"); for (h=0;h<G

5、.vexnum;+h) / 构造表结点链表,利用前插法 printf("%s的先修课程:",G.verh.data); scanf("%s",va);getchar(); while (va0!='0') i = LocateVex(G, va); /弧头 j = h; /弧尾 p = (ArcNode*)malloc(sizeof(ArcNode); p->AdjOfV = j; p->next = G.veri.first; / 插在表头 G.veri.first = p; scanf("%s",va)

6、; getchar();  3）、输出图的顶点和边printf("%d个顶点", G.vexnum); for (i = 0;i < G.vexnum;+i)printf("%4s", G.veri.data); printf(" n%d条弧边:n",G.arcnum); for (i = 0;i < G.vexnum;i+) p = G.veri.first; while (p) printf("%s->%sn",G.veri.data,G.verp->AdjOfV.data);

7、 p = p->next;  4）、通过栈实现拓扑排序      int TopologicalOrder(ALGraph G,AdjList R,struct Name name) int i, k, j = 0, count, indegreeMAX_VER; SqStack S;ArcNode *p;FindInDegree(G, indegree); / 对各顶点求入度InitStack(S); / 初始化栈for (i = 0;i < G.vexnum;+i) /建零入度顶点栈Sif (!indegre

8、ei) Push(S, i); / 入度为0者进栈count = 0; / 对输出顶点计数while (!StackEmpty(S) Pop(S, i);printf("%s(%d学分),",G.veri.data,G.veri.grades);Rj+ = G.veri; /将当前的拓扑序列保存起来+count; / 输出i号顶点并计数for (p =G.veri.first; p; p=p->next)/ 对i号顶点的每个邻接点的入度减1 k = p->AdjOfV;if (!(-indegreek) / 若入度减为0,则入栈Push(S, k);if (co

9、unt < G.vexnum)printf("此有向图有回路无法完成拓扑排序");return 0;else printf( " 为一个拓扑序列");printf("n");int q=1,Z=0;while (q <= TotalOfTerms)int C = RZ.grades ;printf("n第%d个学期应学课程:",q);while (C <= MaxScores)C = C + RZ+1.grades;if (Z < G.vexnum) CmpOfStr(RZ.data,nam

10、e,N);/*让C1C12分别与12门课程对应起来*/+Z;printf("n");if (q = TotalOfTerms)printf( "nOK Over!");q+;return 1;/*/ 拓扑排序要点：依次将入度为0的顶点存入InDegree中，对每个顶点求入度，并存入数组InDegreei中（i=0n），初始化栈Stack,Counter=0，对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Counter+)，推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Counter+）

11、，堆栈是否为空？，n个顶点全输出，依次将入度为0的顶点存入InDegree中5)根据学分上限决定出每学期应学课程，其中R 中存储的是经过拓扑排序后的课程先后顺序。             int q=1,Z=0;while (q <= TotalOfTerms)int C = RZ.grades ;printf("n第%d个学期应学课程:",q);while (C <= MaxScores) C = C + RZ+1.grades;if (Z

12、< G.vexnum)CmpOfStr(RZ.data,name,N);/*让C1C12分别与12门课程对应起来*/+Z; printf("n");if (q = TotalOfTerms)printf( "nOK Over!");q+;四：具体的源代码本程序分为三部分A:SeqStack.h1） #define StackofNUM 20 /存储空间初始分配量2） #define StackforMore 5 / 存储空间分配增量3）4） typedef struct SqStack5） 6） int *a; 7） int *top; 8） in

13、t 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）

14、 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

15、 &x) /*出栈*/39） 40） if (S.top = S.a)return 0;41） x = *-S.top;42） return 1;43） B:ALGraph.h44） #define MAXOfNAME 3 /最多字符个数45） #define MAX_VER 100 /最大顶点数46） 47） typedef struct ArcNode48） 49） int AdjOfV; / 该弧所指向的顶点的位置50） struct ArcNode *next; /指向下一条弧的指针51） ArcNode;52）53） typedef char VertexTypeMAXOfN

16、AME; 54） typedef struct /链接表55） 56） VertexType data; /顶点信息57） int grades; /存储学分信息58） ArcNode *first; /指向第一条依附该顶点的弧的指针59） VNode, AdjListMAX_VER; / 头结点60）61） typedef struct62） 63） AdjList ver; /vertices 存储课程名64） int vexnum, arcnum; / 图的当前顶点数和弧数65） ALGraph;66）67） int TotalOfTerms ; /学期总数68） int MaxScor

17、es; /学分上限 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.veri.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("

18、;请输入教学计划的课程数: " );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）

19、scanf("%s",&G.veri.data);93） getchar();94） G.veri.first = NULL;95） 96） 97） printf("请输入%d个课程的学分值:",G.vexnum);98） for (i = 0;i < G.vexnum;+i) 99） 100） scanf("%d",&G.veri.grades);getchar();101） 102） printf("请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)n");103） for (h

20、=0;h<G.vexnum;+h) / 构造表结点链表,利用前插法104） 105） printf("%s的先修课程:",G.verh.data);106） scanf("%s",va);getchar();107） while (va0!='0')108） 109） i = LocateVex(G, va); /弧头110） j = h; /弧尾111） p = (ArcNode*)malloc(sizeof(ArcNode);112） p->AdjOfV = j;113） p->next = G.veri.first

21、; / 插在表头114） G.veri.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

22、", G.veri.data);128） printf(" n%d条弧边:n",G.arcnum);129） for (i = 0;i < G.vexnum;i+)130） p = G.veri.first;131） while (p)132） printf("%s->%sn",G.veri.data,G.verp->AdjOfV.data);133） p = p->next;134） 135） 136） 137） 138）139） void FindInDegree(ALGraph G, int indegree) /

23、*求顶点的入度*/140） 141） int i;142） ArcNode *p;143） for (i = 0;i < G.vexnum;i+) indegreei = 0; 144） for (i = 0;i < G.vexnum;i+)145） 146） p = G.veri.first;147） while (p)148） indegreep->AdjOfV+;149） p = p->next;150） 151） 152） 153） struct Name154） 155） char c20;156） name;157） 158） void CmpOfStr(V

24、ertexType str,struct Name name,int n) /*让C1C12分别与12门课程对应起来*/159） 160） 161） if(strcmp(str,name0.c)=0)printf(" 程序设计基础");162） if(strcmp(str,name1.c)=0)printf(" 离散数学"); 163） if(strcmp(str,name2.c)=0)printf(" 数据结构");164） if(strcmp(str,name3.c)=0)printf(" 汇编语言 ");16

25、5） if(strcmp(str,name4.c)=0)printf(" 语言的设计和分析 ");166） if(strcmp(str,name5.c)=0)printf(" 计算机原理");167） if(strcmp(str,name6.c)=0)printf(" 编译原理");168） if(strcmp(str,name7.c)=0)printf(" 操作系统 ");169） if(strcmp(str,name8.c)=0)printf(" 高等数学");170） if(strcmp(

26、str,name9.c)=0)printf(" 线性代数");171） if(strcmp(str,name10.c)=0)printf(" 普通物理");172） if(strcmp(str,name11.c)=0)printf(" 数值分析"); C:教学计划编制问题.Cpp #include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include "SeqStack.h"#incl

27、ude "ALGraph.h"#define N 12int TopologicalOrder(ALGraph G,AdjList R,struct Name name) int i, k, j = 0, count, indegreeMAX_VER; SqStack S;ArcNode *p;FindInDegree(G, indegree); / 对各顶点求入度InitStack(S); / 初始化栈for (i = 0;i < G.vexnum;+i) /建零入度顶点栈Sif (!indegreei) Push(S, i); / 入度为0者进栈count = 0

28、; / 对输出顶点计数while (!StackEmpty(S) Pop(S, i);printf("%s(%d学分),",G.veri.data,G.veri.grades);Rj+ = G.veri; /将当前的拓扑序列保存起来+count; / 输出i号顶点并计数for (p =G.veri.first; p; p=p->next)/ 对i号顶点的每个邻接点的入度减1 k = p->AdjOfV;if (!(-indegreek) / 若入度减为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 = RZ.grades ;printf(&