数据结构实验报告学期授课计划.docVIP

实验四 学期授课计划 一、问题描述 1. 大学每个学期的课程授课有学分及授课门数上限的规定。课程之间有先行课的限制。设计编制学期授课计划，使得总的教学时长为最短的拓扑集合划分程序。 2. 实验要求 设计大学四年制授课计划编制的模拟程序。 1）采用邻接表或邻接矩阵存储结构。 2）使用栈或队列等作为拓扑排序的辅助数据结构。 3）可以尝试采用深度优先遍历求解问题。 二、需求分析 1. 创建一个邻接表来存储图的各项数据，创建顺序栈以辅助排序操作； 2. 程序运行前需输入相关数据，如学期数、授课门数、学分等； 3. 测试数据。 三、概要设计 1. 抽象数据类型图的邻接表存储如下： typedef struct ArcNode { int adjvex; /* 该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; }ArcNode; /* 表结点 */ typedef struct { VertexType data; ArcNode *firstarc; } VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */ typedef struct { AdjList vertices,verticestwo; int vexnum,arcnum; /* 图的当前顶点数和弧数 */ int kind; }ALGraph; 2. 抽象数据类型栈的存储表示： typedef struct SqStack { SElemType *base; /*栈底指针*/ SElemType*top; /* 栈顶指针 */ int stacksize; }SqStack; 3. 各函数模块： Status CreateGraph(ALGraph *G) /*创建一个图*/ void Display(ALGraph G) /*输出图的邻接矩阵*/ void FindInDegree(ALGraph G,int indegree[ ]) /*求顶点的入度*/ Status InitStack(SqStack *S) /*创建一个空栈*/ Status StackEmpty(SqStack S) /* 判断栈S是否为空栈*/ Status Pop(SqStack *S,SElemType *e) /*删除栈顶元素*/ Status Push(SqStack *S,SElemType e) /*插入新的栈顶元素*/ Status TopologicalSort(ALGraph G) /*进行拓扑排序*/ 四、详细设计 #includestring.h #includemalloc.h #includestdio.h #includemath.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; typedef int Boolean; #define MAX_NAME 10 #define MAXCLASS 100 #define STACK_INIT_SIZE 10 #define STACKINCREMENT 2 int Z=0; int X=0; int xqzs,q=1,xfsx; typedef int InfoType; typedef char VertexType[MAX_NAME]; /* 字符串类型 */ #define MAX_VERTEX_NUM 100 typedef enum{DG}GraphKind; /* {有向图,有向网,无向图} */