数据结构---教学计划编制

软件学院课程设计报告书课程名称数据结构设计题目教学计划编制2011年1月目录1设计时间...................................................12设计目的...................................................13设计任务...................................................14设计内容...................................................14.1需求分析...............................................14.2总体设计...............................................24.3详细设计...............................................64.4测试与分析............................................124.4.1测试.............................................124.4.2分析.............................................154.5附录.................................................165总结与展望................................................26参考文献....................................................27成绩评定....................................................2811设计时间2011年1月3日至2011年1月6日2设计目的1）通过课程设计，加深对《数据结构》这一课程所学内容的进一步理解与巩固。2）通过课程设计，提高程序开发能力，能运用合理的控制流程编写清晰高效的程序。3）通过课程设计，提高C程序调试能力，加强实践能力。4）通过课程设计，培养分析问题、解决实际问题的能力。5）通过课程设计，培养软件设计能力和开发能力。6）通过课程设计，培养交流、团结协作精神。7）通过课程设计，加强个人程序设计能力。3设计任务大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。4设计内容4.1需求分析1、程序所能达到的功能(1)数据结构使用有向图和栈。(2)课程先修关系（图7.26）2(3)如果输入的先修课程号不在该专业开设的课程序列内，则作为错误处理。2、输入的形式和输入值的范围输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。3、输出的形式每学期课程安排4、测试数据：学期总数6，一学期的学分上限10，该专业共开课程数目12，按照图7.26输入课程名，课程号，课程学分。输出正确的课程编排结果。4.2总体设计1、说明本程序中用到的所有抽象数据类型的定义ADTGraph{课程编号课程名称先决条件课程学分01程序设计基础无202离散数学01303数据结构01,02404汇编语言01305语言的设计和分析03,04206计算机原理11307编译原理05，03408操作系统03，06409高等数学无710线性代数09511普通物理09212数值分析09，10，0133数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}基本操作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[])初始条件：拓扑排序完成4操作结果：构造关键路径的先修关系网voidTopologicalSort_1(ALGraphG,intnumterm,intuplcredit)初始条件：图G已存在操作结构：进行拓扑排序，并完成关系网的构造，使课程尽可能集中在前几个学期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++)入度为零的节点入栈，即无先修的课程入栈if((G.vertices[i].indegree==0)&&(G.