数据结构ii课程设计任务书

《数据结构ii课程设计任务书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构II课程设计任务书软件学院教师:马德印一、课程设计目的数据结构课程是软件工程专业的必修课，在课程体系中占有重要地位。数据结构本身具有概念抽象、算法复杂和难于掌握的特点，要想掌握数据结构，不仅要做适量的习题，更重要的是动手能力。通过课程设计，可以加深对基本算法的理解，激发学习兴趣，增强自信心。二、课程设计题目本课程设计共包括10个题目，内容覆盖了数据机构的树和图的基本算法，详见附录1。三、适用班级本课程设计任务书适用于长春工业大学软件学院13级学生。四、指导教师马德印。五、设计要求在本课程设计

2、过程中要求学生：（1）3名同学一组，每组选1道题。（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。（3）认真编写课程设计报告。六、考核方式和成绩评定考核分为两个部分：l程序运行情况：按规定时间到机房运行程序，由老师检查运行情况。学生能对自己的程序面对教师提问并能熟练地解释清楚。l要有树和图的相关知识点。l课程设计报告：是否按规定书写实验报告的各项内容。课程设计成绩

3、采用：成绩=上机检查（40%）+答辩（40%）+课程设计报告（20%）五、上交相关内容要求上交的成果的内容必须由以下几个部分组成，缺一不可1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；2．课程设计报告书：（具体要求见内容六“课程设计说明书规范”）。六、课程设计说明书规范课程设计说明书是课程设计主要成果之一，对于设计类，应包括图纸、程序、实验成果等。1、说明书基本格式说明书要手写，书写工整。2、说明书结构及要求（1）封面12包括：题目、系别、班级、完成日期、成绩

4、及指导教师（签字）、学生姓名等项。（2）目录要求层次清晰，给出标题及页次。最后一项为"参考资料"。（3）正文正文应按照目录所确定的顺序依次撰写，要求计算准确，论述清楚、简练、通顺，插图清晰整洁。文中图、标及公式应规范地绘制和书写。a)总体设计（程序设计组成框图、流程图）b)详细设计（模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等）c)调试与测试：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施d)关键源程序清单和执行结果：清单中应有足够的注释问题描述和功能设

5、计（4）参考资料参考资料按下述顺序和格式书写：[1]毛昶熙，周名德等．闸坝工程水力学与设计管理.北京：水利电力出版社，1995：8—9如参考网上资料，请写明网址。12附录1数据结构II课程设计的具体内容本次课程设计完成如下模块（共10个模块，任选其中1个题目作为课设的题目）1、信号放大器1)问题描述天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相

6、同。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。2)基本要求(1)建立模型，设计数据结构；(2)设计算法完成放大器的放置；(3)分析算法的时间复杂度。3)设计思想为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。图5是一个网络示意图，边上标出的是从父结点到子结点的信号衰减量。ABCDEFGHIJK1312222122图5网络分布示意图对于网络中任一结点i，

7、设d(i)表示结点i与其父结点间的衰减量，D(i)为从结点i到结点i的子树中任一叶子结点的衰减量的最大值，并有如下递推公式：D(i)=0若i为叶结点D(i)=max{D(j)+d(j)}若i不是叶结点且j是i的孩子在此公式中，要计算某结点的D值，必须先计算其孩子结点的D值，因而必须后序遍历二叉树，当访问一个结点时，计算其D值。12例如，D(B)=max{D(D)+d(D)，D(E)}=4，若容忍值为3，则在B点或其祖先的任意一点放置放大器，并不能减少B与其后代的衰减量，必须在D点放置一个放大器或在其

8、孩子结点放置一个或多个放大器。若在结点D处放置一个放大器，则D(B)=2。根据上述分析，设计如下存储结构：STRUCTELEMENT{intD;//该结点的衰减量intd;//父结点的衰减量boolboost;//当且仅当本处设置放大器，则boost为true};structBiNode{elementdata;BiNode*lchild,*rchild;};计算并放置放大器的伪代码为：1.D(i)=0;2.for(i的每个孩子j)2.1如果D(j)+d(j)>容忍值