数据结构课程设计--教学计划安排系统.doc

教学单位计算机科学与技术 学生学号 数据结构 课程设计报告书题 目教学计划安排系统学生姓名 专业名称计算机科学与技术(软件工程)指导教师李志敏 吴先飞课程设计评分评分标准得分1、内容完整性（20分）2、报告撰写规范性（10分）3、问题描述正确性（10分）4、设计合理与有效性（10分）5、程序代码编写规范性（20分）6、程序运行正确性（10分）7、屏幕提示信息准确与充分性（10分）8、测试过程充分性与正确性（10分）合计平时成绩(30%)：课程设计报告成绩(70%)：总 成 绩：评阅人签名： 目录一、课程设计的目的4二、设计的内容与要求4三、总体设计4四、详细设计5五、调试与测试15六、课程设计的总结17一、 课程设计的目的1. 巩固和加深学生对C语言课程的基本知识的理解和掌握2. 掌握C语言编程和程序调试的基本技能3. 利用C语言进行基本的软件设计4. 掌握书写程序设计说明文档的能力5. 提高运用C语言解决实际问题的能力二设计的内容与要求 要建立一个图，因而要输入图的结点数和边数以及图的每一个结点的名称，要对所输入课程进行排课，因而要确定每一个结点的入度是否为零,并且将入度为零的结点分别进栈再出栈，再进另一个栈，最后出栈，最后实现对所输入的课程进行排课3 总体设计（1）该教学计划安排系统分为6个模块 1.建立图 2.栈的初始化 3.出栈4. 进栈5求结点的入度6拓扑排序（2） 算法描述（此程序中所包含的函数）1. 主函数main():调用CreateALGraph(G)函数和TopologicalSort(G)函数。2.CreateALGraph()函数:从键盘上输入所需要的值，并对每一个结点的*firstarc赋值为NULL。3.InitStack()函数:将栈分配存储空间，并对top和base赋值。4.Push()函数: 进满足条件的元素压入栈中，并改变top指针的值5. Pop()函数:开始判断栈中的top和base指针是否相等，若相等则返回，否则进行出栈操作。6.StackEmpty()函数:通过判断栈是否为空来返回相应的值。7.FindInDegree()函数:通过循环求出每一个结点的入度8.TopologicalSort()函数:通过拓扑排序将相应的课程给输出来四详细设计 数据的组织描述（比如主要的变量类型，结构体等等），模块之间的参数设计（接口设计，模块的功能说明），系统控制流程图，各个模块的流程图，采用的算法typedef structSElemType *base; /在栈构造之前和销毁之后,base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间,以元素为单位SqStack;typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置struct ArcNode *nextarc;/指向第一条依附该顶点的弧的指针ArcNode;typedef struct VNodechar data10;ArcNode *firstarc;AdjListmax_vertex_num;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;1. 主函数模块 定义一个图的变量，调用CreateALGraph(G)函数,和TopologicalSort(G)函数。 2.创建图的模块 从键盘上输入学期数，再输入课程数目（即结点数）和课程之间的关系数（即边数），并把指向第一条依附该顶点的弧的指针赋值为NULL，同时把每一个结点所指向的其他结点形成一个链表。为NULL。 3栈的初始化模块 使栈中base指针分配一定的存储空间，并使栈中top指针指向base指针。 4.栈的进栈模块 先开始判断这个栈是否为满，若满了，则重新分配一定的存储空间，栈中的top指针重新赋值之后，再使该元素进栈，并使top指针指向下一位。5. 栈的出栈模块 判断栈的top指针和base指针是否相等，若相等则为空，否则不为空。6. 栈空的模块 通过判断栈的top指针和base指针是否相等，来返回相应的值 7.求结点的入度模块对每一个结点已经形成了一个链表进行查找，若发现有一个结点指向另一个结点，就把另一个结点的入度加1，直到循环结束8. 拓扑排序模块 首先对栈进行初始化，然后找出结点的入度为零的结点，若入度为零，则进栈。当是S1不为空时，就将栈中的S1进行出栈操作，并把序号所对应的结点给输出来。与此同时，把结点所对应的序号压入栈S2，同时将count加1，并判断栈S2是否为空，若不为空，则把栈S2中的元素进行出栈操作，并把该结点所形成的链表中每一个结点的入度减一，若减之后，就把该结点的序号压入栈S1。如此循环，直到该循环结束 图(1)是CreateALGraph()函数inti,semester_num, v,w,vex CreateALGraph函数semester_num8输入学期数Nvex=20vex=20Y 课程数目输入课程之间的关系数输入课程的名字NiG.vexnum输入课程的之间的先后关系数v,wYi=S.stacksize return 1*S.top+=e return 0 是否S.top=S.base+S.stacksize,S.stacksize+=createstack; S.base=0S.base=(SElemType *)realloc(S.base,(S.stacksize+createstack)*sizeof(SElemType) 图(6) 图(6)是FindInDegree()函数 图(6)是FindInDegree()函数p=p-nextarci+否 结束是是是否否 indegreej+ int j=0 ,jadjvex=j P=NULL p=G.verticesi.firstarc i G.vexnum int i=0 ArcNode* p 图(5) return 0 return 1S.top=S.base图(5)是StackEmpty()函数SqStack S1,S2;ArcNode* p; int i=0,count=0,k;图(7)拓扑排序函数函数是indegreei=0 Push(S1,i)否是i+,inextarcPush(S1,k)-indegreek)=0 k=p-adjvex5. 调试与测试调试1.在编程当中，由于要输入大量的程序，所以经常出现很多不让人注意的小错误。例如大小写 int写成Int(因为是在word中写的，会自动将字母大写)2.关系运算符和赋值运算符总是用错，而这种错误也总是被忽略。3.有时候会忘记加分号或是在不该加的地方加上了分号。不过这种情况还是比较容易被发现的。4.有时候大括号也会忘加，尤其是在if语句和for语句中。5.最重要的是函数的应用，函数应该应用得当，否则程序会出现很大的错误，尤其是在如此庞大的程序中。6.调试拓扑排序的时候，最头疼，有时候调试半天没有结果，最后问了一下同学，才有了思绪，错误逐渐浮出水面，让我明白究竟错在哪里。7.总是忘了初始化，结果调试半天没有调试出来。8.我对拓扑排序基本弄清楚了，但是程序不一定写的出来，稍微错了一点很难找出来。9.在定义结构体时，纠结了半天，没有定义好结构体很多都是白搭，下面很多程序都不好写。10.全程变量的运用错误导致很多错误，调试了半天。测试 开始界面输入课程数目输入总边数输入所有课程的名称输入课程之间的先后关系学期课程安排六课程设计的总结通过这个课程设计，我们更加牢固的掌握了书本上的知识。并对于以前不熟悉的知识有了更加深刻的了解。在完成此次课程设计的过程中，虽然有些疲劳和困倦，但带给我很多的收获。数据结构已经学了半个学期了，有许多知识都存在似懂非懂的现象，这种现象通过实际的上机操作，已经减少了许多。很多程序理论上说得过去，但真正上机了却会发现行不通。所以说无论做什么事空有理论而不去实践都收获不到真正的果实。说实话，我这个程序在所有程序当中算是简单的，所包含的知识也就是调用函数和结构体，当中穿插了一些拓扑排序算法，总体来说结构还是很清晰的，由各个模块小模块组成了一个排课系统。但过程中也是遇到了不少的麻烦，很多地方都想不到或是想不全的。所以说对待任何事情我们都不容小觑，一件自己没做过的事谁都不能说你就一定能做好了。输入和调试程序的过程是相当枯燥的，但构思和完善程序的过程还是比较有趣的，无论怎样，当你完成了一个程序时，还是相当有成就感的。此次任务的完成，也体现出同学之间的团结精神。实践是检验真理的唯一标准。没有实践，就不会发现和深刻体会它的真实所在。只有通过检验的真理，在自己的心里，才会认可它的真实性。面向程序设计的完成，使我们懂得了真理的重要性，理论和实际的相结合，才能真正把握所学和所掌握的知识。同时培养了我做任何事都要善于坚持的精神，使我我们懂得了团队的重要性。在今后的学习工作中我们将会更好的发挥团队精神。 总的来说，数据结构还是十分重要的，可以通过人为的设计而让电脑来辅助性的做一些机械的东西。在今后的学习过程中，我也加更加认真地学习数据结构，希望能在今后设计出一个属于自己的程序。附录：#include#include#define stack_init_size 100 /存储空间初始分配量#define createstack 10 /存储空间分配增量#define max_vertex_num 20typedef int Status;typedef int SElemType;typedef structSElemType *base; /在栈构造之前和销毁之后,base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间,以元素为单位SqStack;typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置struct ArcNode *nextarc;/指向第一条依附该顶点的弧的指针ArcNode;typedef struct VNodechar data10;ArcNode *firstarc;AdjListmax_vertex_num;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;int indegree20=0; /存储图的入度的全局变量数组Status InitStack(SqStack &S)S.base=(SElemType *)malloc(stack_init_size*sizeof(SElemType);if(!S.base)return 0;S.top=S.base;S.stacksize=stack_init_size;return 1;Status Push(SqStack &S,SElemType e)/插入元素e为新的栈顶元素 if(S.top-S.base=S.stacksize) /栈满,追加存储空间 S.base=(SElemType *)realloc(S.base,(S.stacksize+createstack)*sizeof(SElemType); if(!S.base) return 0;/存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=createstack; *S.top+=e; return 1;Status Pop(SqStack &S,SElemType &e)if(S.top=S.base)return 0;e=*-S.top;return 1;Status StackEmpty(SqStack S)if(S.top=S.base)return 1;else return 0;Status CreateALGraph(ALGraph &G) int i,semester_num,v,w,vex; printf(请输入学期数目:); scanf(%d,&semester_num); if(semester_num8) printf(请重新输入学期数目:); scanf(%d,&semester_num); printf(请输入课程数目(课程数必须小于20):);scanf(%d,&vex);if(vex=20)printf(请重新输入课程数目(课程数必须小于20):);scanf(%d,&vex);G.vexnum=vex; printf(请输入课程间的先后关系数(总边数):);scanf(%d,&G.arcnum); for(i=0;iG.vexnum;i+) printf(请输入%d课程的名字(课程名的长度小于等于10个字符):,i+1);scanf(%s,&G.verticesi.data);G.verticesi.firstarc = NULL;for(i=0;iadjvex=w-1;p-nextarc=G.verticesv-1.firstarc;G.verticesv-1.firstarc=p;return 1; void FindInDegree(ALGraph G)ArcNode* p;for(int i=0;iG.vexnum;i+)p=G.verticesi.firstarc;while(p) for(int j=0;jadjvex=j)indegreej+;p=p-nextarc;Status TopologicalSort(ALG