(完整word版)教学编制问题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 ArcNodeint AdjOfV; / 该弧所指向的顶点的位置struct ArcNode *next; /指向下一条弧的指针ArcNode;typedef char VertexTypeMAXOfNAME; 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;hAdjOfV = j; p-next = G.veri.first; / 插在表头 G.veri.first = p; scanf(%s,va); 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 %sn,G.veri.data,G.verp-AdjOfV.data); 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 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(n第%d个学期应学课程:,q);while (C = MaxScores)C = C + RZ+1.grades;if (Z G.vexnum) CmpOfStr(RZ.data,name,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+），堆栈是否为空？，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 = 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.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 VertexTypeMAXOfNAME; 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 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.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(请输入教学计划的课程数: );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.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=0;hAdjOfV = j;113） p-next = G.veri.first; / 插在表头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, G.veri.data);128） printf( n%d条弧边:n,G.arcnum);129） for (i = 0;i %sn,G.veri.data,G.verp-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+) indegreei = 0; 144） for (i = 0;i AdjOfV+;149） p = p-next;150） 151） 152） 153） struct Name154） 155） char c20;156） name;157） 158） void CmpOfStr(VertexType 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( 汇编语言 );165） 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(str,name9.c)=0)printf( 线性代数);171） if(strcmp(str,name10.c)=0)printf( 普通物理);172） if(strcmp(str,name11.c)=0)printf( 数值分析); C:教学计划编制问题.Cpp #include#include#include#include#include SeqStack.h#include 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 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(n第%d个学期应学课程:,q);while (C = MaxScores)C = C + RZ+1.grades;if (Z G.vexnum)CmpOfStr(RZ.data,name,N);/*让C1C12分别与12门课程对应起来*/+Z;printf(n);if (q = TotalOfTerms)printf( nOK Over!);q+;return 1;/*/void main() ALGraph G; AdjList R; struct Name nameN=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语言的语句用法，学到了很多有用的知识。