数据结构与算法分析课程设计指导书

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

1、《数据结构与算法分析》课程设计指导书（共4题）实验学时：60实验类型：综合型前修课程(含实践环节)名称：高级语言程序设计及其课程设计，离散数学。适用专业：计算机软件及应用专业。一.课程设计的目的课程设计的目的是训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发全过程的综合实践能力。巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。二.课程设计的要求在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类

2、的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。三.课程设计的内容题目10树练习[问题描述]用四叉树表示某图像卷积的映射分量，设各分量值已经求出；需要在一定带宽条件下传输树上接点中表示的图像信息到目标地，最后在目标地重新恢复具有压缩了的信息的四叉树。[基本要求]设可以手工或通过文件输入数据，生成四叉树，并且调用方法可以显示树。然后按选择1的要求实现后面的功

3、能：(有精力的同学可以选择实现[问题讨论]中的功能)选择1.按层次遍历树可以得到结点信息，但是只需要传输树上n(比如n=3)层结点的信息；最后在目标地根据传输过来的信息恢复被截短了的四叉树。[测试数据]提供不同的数据文件，文件中数据值按先根顺序排列。[实现提示]第一次生成树用先根次序生成；根据实现的功能要求设计树结点的结构，包括是否考虑结点在树中与其它结点的联系关系；按层次遍历时可以用队列作辅助结构；可以用分层分组的字符形式来显示树，要能表示结点的数据值和各结点之间的拓扑关系。[问题讨论]在生成四叉树后，实

4、现的功能还可以更强，以下两种选择可以供大家考虑实现：选择2.设最多只能传w个结点的数据，按层次遍历，依次传输结点数据，直到传够w个结点信息，但是注意数据值小于x的结点及其子树的信息不传，这样的结点不在w中计数。在目标地根据传输过来的信息恢复被修剪过了的四叉树。在恢复的树中，保留的结点仍在原来的层次和位置。选择3.设最多只能传w个结点的数据，按层次遍历，选择数据值较大的w个结点信息传输，遇到数据值小于x的结点的子树中有数据值较大且能挤入前w个的结点也要传输相应的信息。在目标地根据传输过来的信息恢复被修剪过了的

5、四叉树。在恢复的树中，保留的结点仍在原来的层次和位置。例子：初始生成的四叉树题目2：以队列实现的仿真技术预测理发馆的经营状况[问题描述]：理发馆一天的工作过程如下：1)理发馆有N把理发椅，可同时为N位顾客进行理发。2)理发师分三个等级（一级、二级、三级），对应不同的服务收费。3)当顾客进门时，需选择某级别理发师，只要该级别的理发师有空椅，则可立即坐下理发，否则需排队等候。4)一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。5)若理发馆每天连续营业T分钟，求（1）一天内顾客在理发馆内的平均逗留

6、时间；（2）顾客排队等候理发的队列长度平均值；（3）营业时间到点后仍需完成服务的收尾工作时间；（4）统计每天的营业额；（5）统计每天不同级别理发师的创收。[基本要求]：1)模拟理发馆一天的工作过程：必须采用事件驱动的离散模型（参考教科书3.5节离散事件模拟p65）；2)每个顾客到达和下一顾客到达时间的间隔应是随机的；3)理发师编号、理发师级别和每天的营业时间由用户输入；4)某顾客挑选某一个级别的理发师而不得时，选第一个队列排队等待；5)每个顾客进门时将生成三个随机数:(1)durtime:进门顾客理发所需服

7、务时间（简称：理发时间）；(2)intertime:下一顾客将到达的时间间隔（简称：间隔时间）；(3)select:服务选项。6)服务收费：应包含服务时间和理发师级别两个因素。7)除了输出统计的数据外，还需要显示理发馆的状态，可以采用文本方式（横向显示每张椅编号、理发师级别。纵向表示等待该理发师理发的排队长度）。[测试数据]：用户输入每位理发师编号、级别号和营业的时间，结合随机数进行测试。[实现提示]1)顾客进门和出门这两个时刻发生的事情称“事件”，按事件的先后次序逐个处理事件的工作方式称“事件驱动模拟”。

8、离散事件驱动模型的特点是只关注和刻画事物的状态变化(即事件)，不关心变化的过渡过程。模型靠每一个事件引发其它事件的方式来维持运转。每个事件都有发生时间，模型的运转实际就是按事件发生时间顺序逐个处理事件，'处理'将产生新的事件。因此，建模的关键就是全面分析事物的主要特点，抽象出几种能反映本质的事件和它们之间的驱动关系。系统时间就是当前事件的事件发生时间，它不是等间隔变化而是跳跃变化的。2)数据结构：本题设计两个抽象