教学计划安排检验程序正文

1、德州学院 计算机系 2011网络工程 数据结构课程设计目 录1 实验目的12 问题描述13 需求分析14 概要设计24.1设计思想24.2设计流程图24.3 数据库设计34.4函数及功能要求34.5模块调用关系45详细设计45.1制定课程计划伪码46 测试分析87 使用说明118 总结129 参考文献1310 附录14教学计划安排检验（德州学院计算机系，山东德州 253023）1 实验目的本次数据结构课程设计的主要目的是检验和巩固专业知识，提高综合素质和能力。并在实际操作中掌握：1邻接表的存储结构。2栈的基本操作。3拓扑排序的思想。通过实习，可以将我们课堂上掌握的理论知识与处理数据的业务相结合

2、，以检验我们掌握知识的宽度、深度及对知识的综合运用能力。2 问题描述针对学院的计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划，并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程。3 需求分析该程序的工作是制定课程安排计划，并满足各学期课程数大致相同。此程序规定：1、输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于20，学期数小于或是等于8，课程名的长度小于等于10个字符。2、程序所能达到的功能：按照用户的输入，给出每学期应学的课程。3、测试数据：输入：学期数：，课程数：12，

3、课程间的先后关系数：16，课程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,v1 v3, v1 v4,v1 v12,v2 v3,v3 v5,v3 v7,v3 v8,v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12,v11v6输出：第1学期应学的课程：v1 v9 第2学期应学的课程：v2 v4 v10 v11 第3学期应学的课程：v3 v6 v12 第4学期应学的课程：v5 v8 第5学期应学的课程：v74 概要设计4.1设计思想总体思想是利用拓扑排序的思想和堆栈思想

4、编写相应函数。首先根据课程的先后关系画出AOV网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作AOV网的存储结构，且在头结点中增加一个存放顶点入度的数组。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。4.2设计流程图开始输入学期数，课程数，课程代表值，课程相互关系数，课程两两先后关系学期数<=8课程数<=20拓扑排序输出相应课程结束不符图1 流程图4.3 数据库设计ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据系统用到的抽象数据类型定义：1关系R：R=VRVR=<

5、v,w>|v,wV且P(v,w),<v,w>表示从v到w的弧， 谓词P(v,w)定义了弧<v,w>的意义和信息 基本操作：（1）Status CreateDG(ALGraph&G)；（2）void FindInDegree(ALGraph G)；（3）Status TopologicalSort(ALGraph G)；ADT Graph2. ADT Stack数据对象：D=ai|aiElemSet，i=1,2,n, n0数据关系：R1=<ai-1，ai>|ai-1，aiD,i=2,，n 约定an端为栈顶，a1端为栈底。基本操作：（1）Statu

6、s InitStack(SqStack&S)；（2）Status Push(SqStack&S,SElemType e)；（3）Status Pop(SqStack&S,SElemType&e)；（4）Status StackEmpty(SqStack S)；ADT Stack4.4函数及功能要求（1）Status InitStack(SqStack&S)：构造一个空栈。（2）Status Push(SqStack&S,SElemType e)：插入元素e为新的栈顶元素。（3）Status Pop(SqStack&S,SElemType&

7、amp;e)：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。（4）Status StackEmpty(SqStack S)：判断栈是否为空,为空返回TRUE,否则返回FALSE。（5）Status CreateDG(ALGraph&G)：建立邻接表。（6）void FindInDegree(ALGraph G)：求图的入度。（7）void print(int n,ALGraph G)：排序输出顶点数据。（8）Status TopologicalSort(ALGraph G)：拓扑排序，有向图G采用邻接表存储结构。4.5模块调用关系各程序模块之间的调用关系（

8、子程序编号见上）：主函数可调用子程序5，8。子程序8可调用子程序1，2，3，4，6，7。5详细设计5.1制定课程计划伪码制定课程计划算法的伪码描述如下：Status CreateDG(ALGraph&G)/建立邻接表提示"请输入学期数目（学期数目必须小于等于8）："scanf("%d",&学期数目);if(学期数目>8)提示"请重新输入学期数目（学期数目必须小于等于8）："scanf("%d",&学期数目); 提示"请输入课程数目(课程数必须小于20)："scanf

9、("%d",&课程数目);if(课程数目>=20)提示"请重新输入课程数目(课程数必须小于20)："scanf("%d",&课程数目);图G的顶点数=课程数目;提示"请输入课程间的先后关系数："scanf("%d",&图G的顶点数);提示"请输入课程的代表值(课程名的长度小于等于10个字符):"for(i=0;i<图G的顶点数;i+) scanf("%s",&图G的第i个顶点的数据);图G的第i个顶点指向的第一条

10、弧 = NULL;/输入顶点信息提示"请输入课程间两两间的先后关系："for(i=0;i<图G的弧数;i+)/输入弧的信息scanf("%d,%d",&弧尾v, &弧头w);ArcNode *p= new ArcNode;/建立结点if(p为空) return ERROR;p所指向的顶点（p->adjvex）=w-1;p所指向的下一条弧（p->nextarc）=G.verticesv-1.firstarc;/顶点v的链表G.verticesv-1.firstarc=p;/添加到最左边return OK;voidFindI

11、nDegree(ALGraph G)/求图各顶点的入度ArcNode* p;for(int i=0;i<图G的顶点数;i+)p=G.verticesi.firstarc;while(p不为空) for(int j=0;j<图G的顶点数;j+)if(p所指向的顶点位置（p->adjvex）=j)第j个顶点的入度+1;p=p->nextarc;void print(int n,ALGraph G)/对刚出s1栈的数据进行排序然后输出 for(i=0;ni!=-1;i+)for(j=i+1;nj!=-1;j+)if(ni>nj)ni与nj交换;for(i=0;ni!=-

12、1;i+)输出“G.verticesni.data”;Status TopologicalSort(ALGraph G) /拓扑排序 /有向图G采用邻接表存储结构SqStack S1,S2;ArcNode* p;inti,count,k,m,n20;FindInDegree(G);InitStack(S1);InitStack(S2);for(i=0;i<20;i+)ni=-1;/将数组n全部赋值为-1for(i=图G的顶点数-1;i>=0;-i)if(第i个顶点的入度为0)把入度为0的压入栈S1count=0; /对输出顶点计数while(S1不为空栈)输出("第%d学

13、期应学的课程:",count+1);m=0;while(S1不为空栈)将S1的栈顶元素删除，并将其值返回给I;nm=i;把i号顶点压入栈S2m+;调用排序及输出函数将数组n全部赋值为-1count+; /计数while(S2不为空)将S1的栈顶元素删除，并将其值返回给I;for(p=G.verticesi.firstarc;p;p=p->nextarc)k=p->adjvex; /对i号顶点的每个邻接点的入度减1if(!(-indegreek) /若入度减为0,则入栈将度为0的顶点入栈S1;if(count<G.vexnum) /该有向图有回路return ERRO

14、R;else return OK;/TopologicalSort6 测试分析1运行程序打开界面如下图，并根据提示，输入学期数目：图2 测试1输入出错时显示如下：图3 测试22 输入正确继续根据提示输入课程数目：图4 测试33输入错误时的显示如下：图5 测试44输入正确则继续根据界面提示输入课程的代表值：图6 测试55根据界面提示输入课程间两两间的先后关系：图7 测试66 输入课程间两两间的先后关系后，则输出每学期应学的课程：图8 测试77 使用说明运行程序，出现主页面，输入学期数目（学期数目必须小于等于8），输入完成后，按回车进行下一步；输入课程数目（课程数必须小于20），输入完成后，按回车

15、进行下一步；输入课程间的先后关系，输入完成后，按回车进行下一步；输入课程的代表值（课程名的长度小于等于10个字符，课程名之间用空格隔开），输入完成后，按回车进行下一步；输入课程间两两间的先后关系（注意：只输入课程代表值的数字部分，两两关系间用逗号隔开，不同组的关系用空格隔开），输入完成后，按回车，主界面上将显示每学期的课程安排。至此，本程序运行结束。8 总结本程序充分应用了我们数据结构中所学的知识，完成了教学计划安排的检验。通过本次课程设计我们不仅仅掌握了邻接表的存储结构、栈的基本操作、拓扑排序的思想等知识。其实我们收获的不仅仅是技术，本次程序设计使我不仅深化理解了教学内容，进一步提高灵活运用

16、数据结构、算法和程序设计技术的能力，并且在总体分析、总体结构设计、算法设计、课程设计、上机操作及程序调试等基本技能方面受到了综合训练，使我在编读程序时更容易。通过本次课程设计我们小组成员团结合作但又不缺乏分工，查找资料，编写代码，完成报告。在此期间，我们充分认识了团结合作的重要性，查找、编写过程，我们有过思考，有过讨论，有过困难，但最终通过我们的团结，商讨，困难被化解，报告最终展现在我们面前。9 参考文献1. 严蔚敏，数据结构 C语言，清华大学出版社2. 谭浩强，c语言程序设计，清华大学出版社3. 晋良颍，数据结构，人民邮电出版社，2002年4. 李春保，数据结构习题，清华大学出版社5. 严蔚

17、敏，数据结构习题，清华大学出版社6. 王立柱，c语言与数据结构，清华大学出版社7. 李春葆，数据结构（C语言篇）习题与解析，清华大学出版社9.徐孝凯，魏荣数据结构,机械工业出版社，1996年10.徐孝凯，数据结构简明教程，清华大学出版社，1995年11.陈文博，朱青数据结构与算法，机械工业出版社，1996年 12.许卓群，张乃孝，杨冬青，唐世渭数据结构，高等教育出版社，1988年 13.李廉治，姜文清，郭福顺数据结构，大连理工大学出版社，1989年10 附录见源代码：#include"malloc.h"#include"stdio.h"#define O

18、K 1#define ERROR 0#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量#define MAX_VERTEX_NUM 20typedef int Status;typedef int SElemType;typedef struct SElemType *base; /在栈构造之前和销毁之后,base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间,以元素为单位SqSt

19、ack;typedef struct ArcNodeint adjvex;/该弧所指向的顶点的位置struct ArcNode *nextarc;/指向第一条依附该顶点的弧的指针ArcNode;typedef struct VNodechar data10;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;int indegree20=0; /存储图的入度的全局变量数组Status InitStack(SqStack

20、&S)/构造一个空栈SS.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)return ERROR;/内存分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStackStatus Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素 if(S.top-S.base>=S.stacksize) /栈满,追加存储空间S.base=(SElemType*)realloc(S.base,(S

21、.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) return ERROR;/存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push Status Pop(SqStack &S,SElemType &e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top=S.base)return ERROR;e=*-S.top;return OK;/PopStatu

22、s StackEmpty(SqStack S)/判断栈是否为空,为空返回TRUE,否则返回FALSEif(S.top=S.base)return TRUE;else return FALSE;Status CreateDG(ALGraph &G)/建立邻接表int i,l,v,w,vex; printf("请输入学期数目（学期数目必须小于等于8）："); scanf("%d",&l); if(l>8) printf("请重新输入学期数目（学期数目必须小于等于8）："); scanf("%d",

23、&l); printf("请输入课程数目(课程数必须小于20)：");scanf("%d",&vex);if(vex>=20)printf("请重新输入课程数目(课程数必须小于20)：");scanf("%d",&vex); G.vexnum=vex;printf("请输入课程间的先后关系数：");scanf("%d",&G.arcnum);printf("请输入课程的代表值(课程名的长度小于等于10个字符):");f

24、or(i=0;i<G.vexnum;i+) scanf("%s",&G.verticesi.data);G.verticesi.firstarc = NULL;/输入顶点信息printf("请输入课程间两两间的先后关系：");for(i=0;i<G.arcnum;i+)/输入边的信息scanf("%d,%d",&v, &w);/形式2ArcNode *p= new ArcNode;/建立结点if(!p) return ERROR;p->adjvex=w-1;p->nextarc=G.verticesv-1.firstarc;/顶点v的链表G.verticesv-1.firstarc=p;/添加到最左边return OK; void FindInDegree(ALGraph G)/求图的入度ArcNode* p;for(int i=0;i<G.vexnum;