47数据结构课程设计报告--课程表设计

软件学院课程设计报告书课程名称数据结构设计题目教学计划编制专业班级软件10-04班学号1020010432姓名张小龙指导教师刘玲玲2011年1月目录说明：按住Ctrl并单击可访问当前链接，页数为文件中所标页码。1设计时间....................................错误!未定义书签。2设计目的....................................错误!未定义书签。3设计任务....................................错误!未定义书签。4设计内容....................................错误!未定义书签。4.1需求分析................................错误!未定义书签。4.2总体设计................................错误!未定义书签。4.3详细设计...............................................64.4测试与分析..............................错误!未定义书签。4.4.1测试...............................错误!未定义书签。4.4.2分析...............................错误!未定义书签。4.5附录...................................错误!未定义书签。5总结与展望................................................26参考文献....................................................28成绩评定....................................................2811设计时间2012年1月3日至2012年1月5日2设计目的（1）加强学生分析问题能力和应用所学知识解决问题的能力；（2）使学生对所学内容更深入的了解和应用；（3）提高C程序调试能力，加强程序设计和实践能力；（4）加深学生对《数据结构》和《C语言》等相关课程的认识；（5）培养学生自主软件设计能力和开发能力；（6）加强个人程序设计能力和学生与学生之间的交流和研讨。3设计任务大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。任选软件专业几门课程作为顶点，通过这几门课程的先修关系来构建一个有向图，用邻接表来储存，通过栈和有向图来完成课程教学计划安排。4设计内容4.1需求分析1、程序所能达到的功能(1)数据结构使用有向图和栈。(2)课程先修关系（表4.1--01）2课程名称课程号学分先修课的课程号软件设计基础014
无离散数学023无数据结构0351,2思想道德修养042无语言的设计与分析0523毛泽东思想0624马克思主义0726操作系统0843,5高等数学096无线性代数10309大学物理114无数值分析1231,8数字电子13411概率论1439（表4.1--01课程先修关系）(3)如果输入的先修课程号不在该专业开设的课程序列内，则作为错误处理。2、输入的形式和输入值的范围输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。3、输出的形式每学期课程安排4、测试数据：学期总数6，一学期的学分上限16，该专业共开课程数目14，按照表4.1--01输入课程名，课程号，课程学分。输出正确的课程编排结果。4.2总体设计1、说明本程序中用到的所有抽象数据类型的定义ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}3基本操作P:voidCreatGraph(ALGraph*G)操作结果：创造图GvoidInitStack(SqSttack*S)操作结果：构造一个空栈SvoidStackEmpty(SqStack*S)初始条件：栈S已存在操作结果：若栈S为空栈，则返回TRUE，否则FALSEvoidPush（SqStack*S，inte）初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素voidPop（SqStack*S，int*e）初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值voidFindInDegree(ALGraphG,intindegree[])初始条件：拓扑排序完成操作结果：构造关键路径的先修关系网voidTopologicalSort_1(ALGraphG,intnumterm,intuplcredit)初始条件：图G已存在4操作结构：进行拓扑排序，并完成关系网的构造，使课程尽可能集中在前几个学期voidTopologicalSort_2(ALGraphG,intnumterm,intuplcredit)初始条件：图G已存在操作结果：进行拓扑排序，并完成关系网的构造，使课程尽量均匀分布}ADTGraph2、说明主程序的流程53、说明各程序模块之间的层次（调用）关系（图4.2-3）主程序模块拓扑排序模块顺序栈SqStack模块图4.2-3各程序模块之间的层次（调用）关系开始输入学期总数，一学期学分上限输出编排结果结束构造图表G选择编排方式拓扑排序2课程尽量均匀分布拓扑排序1课程尽可能集中到前几个学期选择1选择2图4.2-2主程序流程图64.3详细设计1、实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法1）采用邻接表存储结构,构造没有相关信息的图G,并储存键入的相关信息voidCreatGraph(ALGraph*G){通过循环语句完成对键入的课程名称，课程号，学分的存储，并课程先修关系建立邻接表for(i=1;i=G-arcnum;i++)/*构造顶点向量*/{printf(\n请输入存在先修关系的两个课程的序号:);scanf(&n,&m);while(课程号不在编入范围){printf(输入的顶点序号不正确请重新输入:);scanf(&n,&m);}分配头结点的存储空间if(p为空){printf(分配失败);}建立邻接表}printf(建立的邻接表);for(i=1;i=G-vexnum;i++){printf(%d:-,G-vertices[i].classid);for(p=G-vertices[i].firstarc;p!=NULL;p=p-nextarc)printf(%d-,p-adjvex);printf(NULL);7printf(\n);}}2）构造一个空栈SvoidInitStack(SqStack*S){赋予顺序栈足够的存储空间if(!S-base){printf(存储分配失败)exit(1);}top=base初始栈为空，存储空间为所分配的足够的存储空间}3）判断是否为空栈intStackEmpty(SqStack*S){if(栈S为空栈)returnOK;elsereturnERROR;}4）入栈操作voidPush(SqStack*S,inte){插入元素e为新的栈顶元素if(栈满){为栈重新分配存储空间if(!S-base){printf(存储分配失败)exit(1);}8top=base初始栈为空，存储空间为所分配的足够的存储空间}栈顶指针上移}5.取栈顶操作intPop(SqStack*S,int*e)若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR{if(栈顶元素为空)exit(1);栈顶指针下移并将其值返回给*e}6）求图中各节点的入度voidFindInDegree(ALGraphG,intindegree[]){for(i=1;i=G.vexnum;i++)indegree[i]=0;for(i=1;i=G.vexnum;i++){while(G.vertices[i].firstarc){indegree[G.vertices[i].firstarc-adjvex]++;G.vertices[i].firstarc=G.vertices[i].firstarc-nextarc;}}}7）有向图G采用邻接表存储结构voidTopologicalSort_1(ALGraphG,intnumterm,intuplcredit){若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR。intindegree[M];存放各节点的入度intcount;课程编排数目计数器9intsumcredit;每个学期的课程学分累加器FindInDegree(G,indegree);对各顶点求入度indegree[0..vernum-1]for(i=1;i=G.vexnum;i++)G.vertices[i].indegree=indegree[i];初始化栈while(count!=G.vexnum&&k=numterm){sumcredit=0;for(无先修的课程入栈)if((G.vertices[i].indegree==0)&&(G.vertices[i].state==NOTSTUDY)){Push(&S,i);G.vertices[i].state=STUDY;避免入度为零节点重复入栈}if(栈非空且学分计数器小于学分上限){k=k+1;printf(第%d个学期学得课程有:\n,k);for(i=1;i=G.vexnum;i++)入度为零的节点入栈，即无先修的课程入栈if((G.vertices[i].indegree==0)&&(G.vertices[i].state==NOTSTUDY))Push(&S,i);while(栈非空&&学分总数小于学分上限){Pop(&S,&j);sumcredit=sumcredit+G.vertices[j].credit;if(学分计数器小于等于学分上限){printf(%s,G.vertices[j].name);课程数目累加10对j号顶点每个邻接点的入度减一}将未输出的节点重新压入栈}}}if(被编排课程编排课程总数)printf(课程编排出错);else{printf(课程编排成功);}}8)有向图G采用邻接表存储结构若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERRORvoidTopologicalSort_2(ALGraphG,intnumterm,intuplcredit){头结点指针P调用栈SFindInDegree(G,indegree);for(i=1;i=G.vexnum;i++)G.vertices[i].indegree=indegree[i];InitStack(&S);课程编排计数器赋值为0课程名计数器赋值maxnum=G.vexnum/numterm+1;sumnum=0;while(count!=G.vexnum&&k=numterm){for(i=1;i=G.vexnum;i++)入度为零的节点入栈，即无先修的if((G.vertices[i].indegree==0)&&(G.vertices[i].state==NOTSTUDY)){Push(&S,i);G.vertices[i].state=STUDY;}if(栈非空，学分计数器小于学分上限){11k=k+1;printf(第%d个学期学得课程有:,k);sumcredit=0;sumnum=0;for(i=1;i=G.vexnum;i++)入度为零的节点入栈，即