6*******************实践教学*******************兰州理工大学计算机与通信学院2011年春季学期数据结构课程设计题目:教学计划编制问题专业班级:软件一班姓名:学号:指导教师:成绩:_____________________前言本学期开设了算法与数据结构,通过学习算法与数据结构,大家对编程有了更多的了解,为了让大家将自己所学的知识应用到实际当中,学校开设了算法与数据结构课设,通过这次课设大家可以更好地将c语言应用到实际当中,而且可以更好的掌握算法与数据结构,将数据结构和c语言有效的结合起来,使大家的编程能力得到更大的提高。
目录摘要------------------------------------------------------------------------------------1 关键字----------------------------------------------------------------------------1 正文------------------------------------------------------------------------------------21. 采用类c语言定义相关的数据类型-----------------------------------------22.各模块的伪码算法-------------------------------------------------------------33 函数调用关系图-----------------------------------------------------------------64 试调分析--------------------------------------------------------------------------75 测试结果--------------------------------------------------------------------------8总结--------------------------------------------------------------------------------9参考文献------------------------------------------------------------------------------9 致谢---------------------------------------------------------------------------------10 附件Ⅰ 1.源程序[带注释](结构体文件)---------------------------------------------------------102.运行结果----------------------------------------------------------------------------28摘要大学的每个专业都要制定教学计划。
假设任何专业都有固定的学习年限,每学年含两学期,每学期的时间长度和学分上限值均相等。
每个专业开设的课程都是确定的,而且课程在开设时间的安排必须满足先修关系。
每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有。
每门课恰好占一个学期。
此程序就可以满足这些要求,输出正确的结果,帮助我们实现教学计划编制关键字:数据结构,计划,编制正文1采用类c语言定义相关的数据类型typedef char VertexType[MAX_NAME];int TotalTerms ; //学期总数int MaxScores; //学分上限typedef struct ArcNode{int adjvex; // 该弧所指向的顶点的位置弧的节点结构struct ArcNode *nextarc; //指向下一条弧的指针}ArcNode;/* 查找图中某个顶点位置*/int LocateVex(ALGraph G, VertexType u)/* 输出图G的信息*/void Display(ALGraph G)*求顶点的入度*/void FindInDegree(ALGraph G, int indegree[])struct Name{ char c[20];}name;void puanduan(VertexType str,struct Name name[],int n)/*栈定义*/typedef int SElemType; // 栈类型#define Stack_NUM 20 //存储空间初始分配量#define Stack_MoreNUM 5 // 存储空间分配增量typedef struct SqStack*拓扑排序*/int TopoSort(ALGraph G,AdjList Temp,struct Name name[]) 2.各模块的伪码算法(1)-图的邻接表存储表示-int adjvex; 该弧所指向的顶点的位置弧的节点结构struct ArcNode *nextarc; 指向下一条弧的指针}ArcNode; 链表结点typedef struct 链接表{ VertexType data; 顶点信息int grades; 存储学分信息ArcNode *firstarc; 指向第一条依附该顶点的弧的指针}VNode, AdjList[MAX_VERTEX_NUM]; 头结点typedef struct{ AdjList vertices; vertices 存储课程名int vexnum, arcnum; 图的当前顶点数和弧数}ALGraph;void OUTPUT()输出菜单(2)采用邻接表存储结构输出提示,按提示操作程序printf("请输入教学计划的课程数: " );printf( "请输入各个课程的先修课程的总和(弧总数): ");printf( "请输入%d个课程的课程号(最多%d个字符,数字+字母):", G.vexnum,MAX_NAME);printf("请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\n");(3)输出图G的信息void Display(ALGraph G)printf("有向图\n");printf("%d个顶点", G.vexnum);拓扑排序ArcNode *p; // 对输出顶点计数while (!StackEmpty(S)){ Pop(S, i);printf("%s(%d分),",G.vertices[i].data,G.vertices[i].grades);Temp[j++] = G.vertices[i]; //将当前的拓扑序列保存起来++count; // 输出i号顶点并计数for (p =G.vertices[i].firstarc; p; p=p->nextarc)// 对i号顶点的每个邻接点的入度减1{ k = p->adjvex;if (!(--indegree[k])) // 若入度减为0,则入栈Push(S, k);(4)void main()初始化strucNamename[N]={{"C1"},{"C2"},{"C3"},{"C4"},{"C5"},{"C6"},{"C7"},{" C8"},{"C9"},{"C10"},{"C11"},{"C12"}};3 函数调用关系图-4 试调分析-根据问题描述及要求,可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体,在运行结果中将图的信息显示出来,利用先修关系将课程排序,最后解决问题——输出每学期的课程。
end采用第二种策略:使课程尽可能地集中在前几个学期中根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体创建图CreateGraph():结合先修关系的AOV网,采用邻接链表存储菜单OUTPUT():显示代号所对应课程及课程的先修课程前插法main拓扑排序TopoSort(G):将课程排序后并决定出每学期所学课程输出图G的信息Display(G):将图的顶点和弧边输出5 测试结果测试数据:输入的内容如下:课程编号课程名称学分先决条件01 程序设计基础 2 无02 离散数学 3 0103 数据结构 4 01,0204 汇编语言 3 0105 语言的设计和分析 2 03,0406 计算机原理 3 1107 编译原理 4 05,0308 操作系统 4 03,0609 高等数学7 无10 线性代数 5 0911 普通物理 2 0912 数值分析 3 09,10,01学期总数:6;学分上限:10;该专业共开设12门课,课程号从C1到C12,学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。
两种编译都输出结果:第一学期学的课程有:高等数学第二学期学的课程有:普通物理线性代数计算机原理第三学期学的课程有:课程设计基础数据结构离散数学第四学期学的课程有:操作系统汇编语言语言的设计与分析第五学期学的课程有:编译原理数值分析第六学期学的课程有:总结我们在实验过程中遇到的最大难题是两个课程排序算法的编写。
刚开始的时候没有任何的思路,网上也只有拓扑排序的算法,对于课程设计要求的排序算法没有任何头绪。
经过请教老师和同学以及翻阅了一些相关书籍,并在网上的搜索有了排序算法的大体思路。
经过三天的修改,终于写出了符合要求的排序算法经过此次课程设计,自己解决编程中从在的问题,我们认识到了理论与实践结合的重要性,仅仅只是从课本上学到算法原理是远远不够的。
在实践中,我们总会出现许多错误。
这就要求我们以一个脚踏实地的态度来处理问题。
我们深刻地认识到自己写程序的不足,使我们学到了好多有用的知识,让我们明白了算法与编程的密切关系,使我们受益匪浅。
参考文献1《数据结构》(c语言描述)冶金工业出版社2《C程序设计》谭浩强3王连相,冯锋编著.C/C++程序设计.北京:中国科学技术出版社,20054严蔚敏,吴伟民编著.数据结构(C语言版).北京:清华大学出版社,19975 严蔚敏,吴伟民编著.数据结构题集(C语言版).北京:清华大学出版社,致谢首先感谢我的指导老师张永老师,他在我的课程设计过程中提出了指导性的方案和架构,并指引我阅读相关的资料和书籍,使我在不熟悉的领域中仍能迅速掌握新的技术。