《数据结构与算法分析》课程设计指导书 (共4题)

读过一本好书，像交了一个益友。——藏克家
《数据结构与算法分析》课程设计指导书 （共4题）


实验学时： 60 实验类型： 综合型
前修课程(含实践环节)名称：高级语言程序设计及其课程设计，离散数学。
适用专业：计算机软件及应用专业。

一. 课程设计的目的
课程设计的目的是训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发全过程的综合实践能力。巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。

二. 课程设计的要求
在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。

三. 课程设计的内容
题目1 0树练习
[问题描述]
用四叉树表示某图像卷积的映射分量，设各分量值已经求出；需要在一定带宽条件下传输树上接点中表示的图像信息到目标地，最后在目标地重新恢复具有压缩了的信息的四叉树。
[基本要求]
设可以手工或通过文件输入数据，生成四叉树，并且调用方法可以显示树。然后按选择1的要求实现后面的功能：(有精力的同学可以选择实现[问题讨论]中的功能)
选择1. 按层次遍历树可以得到结点信息，但是只需要传输树上 n (比如n=3)层结点的信息；最后在目标地根据传输过来的信息恢复被截短了的四叉树。
[测试数据]
提供不同的数据文件，文件中数据值按先根顺序排列。
[实现提示]
第一次生成树用先根次序生成；根据实现的功能要求设计树结点的结构，包括是否考虑结点在树中与其它结点的联系关系；按层次遍历时可以用队列作辅助结构；可以用分层分组的字符形式来显示树，要能表示结点的数据值和各结点之间的拓扑关系。
[问题讨论]
在生成四叉树后，实现的功能还可以更强，以下两种选择可以供大家考虑实现：
选择2. 设最多只能传 w 个结点的数据，按层次遍历，依次传输结点数据，直到传够w 个结点信息，但是注意数据值小于 x 的结点及其子树的信息不传，这样的结点不在 w 中计数。在目标地根据传输过来的信息恢复被修剪过了的四叉树。在恢复的树中，保留的结点仍在原来的层次和位置。
选择3. 设最多只能传 w 个结点的数据，按层

次遍历，选择数据值较大的 w 个结点信息传输，遇到数据值小于 x的结点的子树中有数据值较大且能挤入前w个的结点也要传输相应的信息。在目标地根据传输过来的信息恢复被修剪过了的四叉树。在恢复的树中，保留的结点仍在原来的层次和位置。
例子： 初始生成的四叉树








题目2：以队列实现的仿真技术预测理发馆的经营状况
[ 问题描述 ] ：理发馆一天的工作过程如下：
1) 理发馆有N把理发椅，可同时为N位顾客进行理发。
2) 理发师分三个等级（一级、二级、三级），对应不同的服务收费。
3) 当顾客进门时，需选择某级别理发师，只要该级别的理发师有空椅，则可立即坐下理发，否则需排队等候。
4) 一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。
5) 若理发馆每天连续营业T分钟，求
（1） 一天内顾客在理发馆内的平均逗留时间；
（2） 顾客排队等候理发的队列长度平均值；
（3） 营业时间到点后仍需完成服务的收尾工作时间；
（4） 统计每天的营业额；
（5） 统计每天不同级别理发师的创收。
[ 基本要求 ] ：
1) 模拟理发馆一天的工作过程：必须采用事件驱动的离散模型（参考教科书3.5节离散事件模拟p65）；
2) 每个顾客到达和下一顾客到达时间的间隔应是随机的；
3) 理发师编号、理发师级别和每天的营业时间由用户输入；
4) 某顾客挑选某一个级别的理发师而不得时，选第一个队列排队等待 ；
5) 每个顾客进门时将生成三个随机数:
(1) durtime:进门顾客理发所需服务时间（简称：理发时间）；
(2) intertime:下一顾客将到达的时间间隔（简称：间隔时间）；
(3) select:服务选项 。
6) 服务收费：应包含服务时间和理发师级别两个因素。
7) 除了输出统计的数据外，还需要显示理发馆的状态，可以采用文本方式（横向显示每张椅编号、理发师级别。纵向表示等待该理发师理发的排队长度）。
[ 测试数据 ] ：用户输入每位理发师编号、级别号和营业的时间，结合随机数进行测试。
[ 实现提示 ]
1) 顾客进门和出门这两个时刻发生的事情称"事件"，按事件的先后次序逐个处理事件的工作方式称"事件驱动模拟"。离散事件驱动模型的特点是只关注和刻画事物的状态变化(即事件)，不关心变化的过渡过程。模型靠每一个事件引发其它事件的方式来维持运转。每个事件都有发生时间，模型的运转实际就是按事件发生时间顺序逐个处理事件，'处理'将产生新的事件。因此，建模的关键就是全面分析事物的主要特点，抽象出几种能反映本质的事件和它们之间的驱动关系。系统时间就是当前事件的事件发生

时间，它不是等间隔变化而是跳跃变化的。
2) 数据结构：本题设计两个抽象数据类型
* 队列抽象数据类型：登录排队等候理发的顾客情况。每个元素应包括顾客进门时刻、理发师级别、理发所需时间。N把椅子对应N个队列。
* 事件链表抽象数据类型：登录顾客进门事件、出门事件。每个事件应包括事件类型（进门事件类型为0，出门事件类型按N把椅子所排队列分为为1、2、...N）和事件发生的时刻occurtime。为便于按事件发生先后顺序逐一处理事件，事件表应按"时刻"有序。
3） 对理发椅需要进行编号，使不同级别的理发师与编号的理发椅相对应。
[ 问题讨论 ]：
1) 顾客排队前，可以在等待该级别各个理发师的各个队列中，选择最短队列；
2) 更进一步,顾客可以选择最快队列（设计选最快的策略）
3) 可以发挥创造性，采用更直观漂亮的图形方式显示理发馆的状态。

题目3、使用哈希表技术判别两个源程序的相似性
[问题描述]
对于两个C语言的源程序清单，用哈希表的方法分别统计两个程序中使用C语言关键字的情况，并最终按定量的计算结果，得出两份源程序清单的相似性。
[基本要求]
C语言关键字的哈希表可以自建，也可以利用《数据结构及应用算法教程》（严蔚敏 陈文博编著 清华大学出版社）书中8。10的哈希表。此题的工作主要是扫描给定的源程序，累计在每个源程序中C语言关键字出现的频度。在扫描源程序过程中，每遇到关键字就查找哈希表，并累加相应关键字出现的频度。为保证查找效率，建议自建哈希表的平均查找长度ASL不大于2。
扫描两个源程序所统计的所有关键字不同频度，可以得到两个向量。如下面简单的例子所示：
Void Int For Char If Else while 4 3 4 3 7 0 2 4 2 5 4 5 2 1 关键字
程序1种关键字频度
程序2种关键字频度
哈希地址
0 1 2 3 4 5 6 7 8 9

X1=[4,3,0,4,3,0,7,0,0,2] X2=[4,2,0,5,4,0,5,2,0,1]
通过计算向量X1和X2的相对距离来判断两个源程序的相似性，相对距离的计算方法是
，T表示向量的转置。
按例子所给的数据，s 0.13。显然当X1=X2时，s=0,反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。
[测试数据]
做几个编译和运行都无误的C程序，程序之间有相近的和差别大的，用上述方法求s,并对比差异程度。
[实现提示]
本题的很大工作量将是对源程序扫描，区分出C程序的每一关键字。可以为C语言关键字集建一棵键树，扫描源程序和在键树中查找

同步进行，以取得每一个关键字。
[问题讨论]
这种判断方法只是提供一种辅助手段，即便s=0也可能不是同一个程序，s的值很大，也可能算法是完全一样的。例如，一个程序使用while语句，另一个使用for语句，但功能完全相同。事实上，当发现s的值很小时，就应该以人工干预来区分。

题目4. 救护车调度模拟系统
问题描述
用Turbo-C语言设计实现一个用事件驱动的"救护车调度"离散模型，模拟120急救中心响应每个病人的呼救信号统一调度救护车运行的情况。
我们对问题作适当简化，假设：某城市共有m个可能的呼救点(居民小区、工厂、学校、公司、机关、单位等)，分布着n所医院(包含在m个点中)，有k辆救护车分派在各医院待命，出现呼救病人时，由急救中心统一指派救护车接送至最近的医院救治。救护车完成一次接送任务后即消毒，并回原处继续待命。假定呼救者与急救中心、急救中心与救护车之间的通讯畅通无阻，也不考虑道路交通堵塞的影响。可以用m个顶点的无向网来表示该城市的各地点和道路。时间可以分钟为单位，路段长可表示为救护车行驶化费的分钟数。
要求

读过一本好书，像交了一个益友。——藏克家
> 模拟每一起病人呼救-派车往救-接人回院的过程：显示每辆救护车的状态(待命、往救、送院{可能还有返点})和每个病人的状态(待派车、待接、送院途中)，显示各医院的待命救护车队列，实时显示当前的病人平均接送时间和平均派车延迟时间以及已送达病人数。救护车应按最快的路线接送病人。
> 呼救事件发生的间隔时间和地点都是随机的(其发生频度先给一个省缺值，可实时调整)。点数m、点名、路段数e和每段长度以及医院点的名称都由教师以文本文件形式给出，格式为：

ABCDEFGH... ... (m个点名称，大小写代表不同点)
AEGHK... ... (n个医院名称)
AB11,AC15,EG9, ... ... FK24, (e条路段及长度)
救护车总数及分派方案在运行前从键盘输入。
> 1.基本要求是救护车只接本医院的病人，病人求救时该院无车就只能等待。(70)
2.进一步要求是：最近的医院无车时，派最近的待命救护车。最好还能权衡一下：
是否等待该院的车回来更快？(85)
3.还可改进：除了可派正在待命的车外，还可派遣送达外院病人后正在返点的车，
有时它比待命地点离病人更近。难度更高，实际要求这种情况下救护车逐路段地
返回，每到一个点都生成一个事件，较麻烦。
4.显示界面还可改为更直观漂亮的图形模式，设计更好的显示方案。
提示：
1. 可以设3种事件：病人呼救

，救护车到病人家，救护车到医院。一个事件队列，一个呼救等待队列，n个救护车待命队列。
2. 初始化时设置第一个病人呼救事件插入事件队列，以启动系统运行。处理病人呼救事件时，将这个呼救排入呼救等待队列，同时产生下一个病人呼救事件。
3. 无向网可用邻接多重表。求出每个医院到其他各点的最短路径，每个点设一个由近到远的医院列表。
4. 参考教科书中第3章第5节：离散事件模拟。


四．设备、环境
采用PC计算机，Turbo C(或Turbo C++)开发环境

五. 课程设计步骤
1.上机前要求认真分析题目要求,完成书面的总体设计和详细设计. 其中:
--总体设计包括问题分析和总体方案设计(基本数据结构、算法思路、功能设计、模块划
分). 形式可用图表,文字说明.
--详细设计包括:每个模块的功能,入出信息,处理逻辑,以及关键技术问题的具体解决
办法.
2.完成程序设计并调试正确后,应请指导教师检查并得到认可。全部完成后应写出完
整的课程设计报告(成绩的重要因素),A4纸装订，连同源程序软盘交辅导教师。

六．课程设计报告内容包括:
--题目
--问题分析和总体设计
--详细设计
--测试数据和调试报告
--小结
--简明的软件使用说明

七. 验收标准
验收包括程序测试结果、类设计的合理性和文档质量三部分。程序测试分标准数据样本的测试、随机输入数据测试、查看源代码和变更问题需求条件的随机数据测试。发现有过分相似的代码和文档将另行处理。


读过一本好书，像交了一个益友。——藏克家