还剩5页未读,继续阅读
文本内容:
数据结构与算法分析课程设计指导书摘要[测试数据]提供不同的数据文件文件中数据值按先根顺序排列....--总体设计包括问题分析和总体方案设计基本数据结构算法思路功能设计模块划...关键词算法数据结构类别专题技术来源牛档搜索(Niudown.COM)http://___.niudown.com/http://www.niudown.com/ 本文系牛档搜索(Niudown.COM)http://___.niudown.com/根据用户的指令自动搜索的结果,文中内涉及到的资料均来自互联网,用于学习交流经验,作品其著作权归原__所有不代表牛档搜索(Niudown.COM)http://___.niudown.com/赞成本文的内容或立场,牛档搜索(Niudown.COM)http://___.niudown.com/不对其付相应的法律责任!《数据结构与算法分析》课程设计指导书(共4题)实验学时60实验类型综合型前修课程含实践环节名称高级语言程序设计及其课程设计,离散数学适用专业计算机软件及应用专业
1.课程设计的目的课程设计的目的是训练学生灵活应用所学数据结构知识,__完成问题分析、总体设计、详细设计和编程实现等软件__全过程的综合实践能力巩固、深化学生的理论知识,提高编程水平,并在此过程中培养他们严谨的科学态度和良好的工作作风
2.课程设计的要求在处理每个题目时,要求从分析题目的需求入手,按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目,最终写出完整的分析报告前期准备工作完备与否直接影响到后序上机调试工作的效率在程序设计阶段应尽量利用已有的标准函数,加大代码的重用率
3.课程设计的内容题目10树练习[问题描述]用四叉树表示某图像卷积的映射分量,设各分量值已经求出;需要在一定带宽条件下传输树上接点中表示的图像信息到目标地,最后在目标地重新恢复具有压缩了的信息的四叉树[基本要求]设可以手工或通过文件输入数据,生成四叉树,并且调用方法可以显示树然后按选择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每个顾客进门时将生成三个随机数:1durtime:进门顾客理发所需服务时间(简称理发时间);2intertime:下一顾客将到达的时间间隔(简称间隔时间);3select:服务选项6服务收费应包含服务时间和理发师级别两个因素7除了输出统计的数据外,还需要显示理发馆的状态,可以采用文本方式(横向显示每张椅编号、理发师级别纵向表示等待该理发师理发的排队长度)[测试数据]用户输入每位理发师编号、级别号和营业的时间,结合随机数进行测试[实现提示]1顾客进门和出门这两个时刻发生的事情称“__”,按__的先后次序逐个处理__的工作方式称“__驱动模拟”离散__驱动模型的特点是只__和刻画事物的状态变化即__,不关心变化的过渡过程模型靠每一个__引发其它__的方式来维持运转每个__都有发生时间,模型的运转实际就是按__发生时间顺序逐个处理__,处理将产生新的__因此,建模的关键就是全面分析事物的主要特点,抽象出几种能反映本质的__和它们之间的驱动关系系统时间就是当前__的__发生时间,它不是等间隔变化而是跳跃变化的2数据结构本题设计两个抽象数据类型队列抽象数据类型登录排队等候理发的顾客情况每个元素应包括顾客进门时刻、理发师级别、理发所需时间N把椅子对应N个队列__链表抽象数据类型登录顾客进门__、出门__每个__应包括__类型(进门__类型为0,出门__类型按N把椅子所排队列分为为
1、
2、...N)和__发生的时刻occurtime为便于按__发生先后顺序逐一处理__,__表应按“时刻”有序3)对理发椅需要进行编号,使不同级别的理发师与编号的理发椅相对应[问题讨论]1顾客排队前,可以在等待该级别各个理发师的各个队列中,选择最短队列;2更进一步顾客可以选择最快队列(设计选最快的策略)3可以发挥创造性,采用更直观漂亮的图形方式显示理发馆的状态题目
3、使用哈希表技术判别两个源程序的相似性[问题描述]对于两个C语言的源程序清单,用哈希表的方法分别统计两个程序中使用C语言关键字的情况,并最终按定量的计算结果,得出两份源程序清单的相似性[基本要求]C语言关键字的哈希表可以自建,也可以利用《数据结构及应用算法教程》(严蔚敏陈文博编著清华大学出版社)书中810的哈希表此题的工作主要是扫描给定的源程序,累计在每个源程序中C语言关键字出现的频度在扫描源程序过程中,每遇到关键字就查找哈希表,并累加相应关键字出现的频度为保证查找效率,建议自建哈希表的平均查找长度ASL不大于2扫描两个源程序所统计的所有关键字不同频度,可以得到两个向量如下面简单的例子所示VoidIntForCharIfElsewhile43437024254521关键字程序1种关键字频度程序2种关键字频度哈希地址0123456789X1=
[4304307002]X2=
[4205405201]通过计算向量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和每段长度以及医院点的名称都由教师以文本文件形式给出,格式为meABCDEFGH……m个点名称,大小写代表不同点AEGHK……n个医院名称AB11AC15EG9……FK24e条路段及长度救护车总数及分派方案在运行前从键盘输入
1.基本要求是救护车只接本医院的病人,病人求救时该院无车就只能等待
702.进一步要求是最近的医院无车时,派最近的待命救护车最好还能权衡一下是否等待该院的车回来更快?
853.还可改进除了可派正在待命的车外,还可派遣送达外院病人后正在返点的车,有时它比待命地点离病人更近难度更高,实际要求这种情况下救护车逐路段地返回,每到一个点都生成一个__,较麻烦
4.显示界面还可改为更直观漂亮的图形模式,设计更好的显示方案提示
1.可以设3种__病人呼救,救护车到病人家,救护车到医院一个__队列,一个呼救等待队列,n个救护车待命队列
2.初始化时设置第一个病人呼救__插入__队列,以启动系统运行处理病人呼救__时,将这个呼救排入呼救等待队列,同时产生下一个病人呼救__
3.无向网可用邻接多重表求出每个医院到其他各点的最短路径,每个点设一个由近到远的医院列表
4.参考___中第3章第5节离散__模拟四.设备、环境采用PC计算机,TurboC或TurboC++__环境五.课程设计步骤
1.上机前要求认真分析题目要求完成书面的总体设计和详细设计.其中:--总体设计包括问题分析和总体方案设计基本数据结构、算法思路、功能设计、模块划分.形式可用图表文字说明.--详细设计包括:每个模块的功能入出信息处理逻辑以及关键技术问题的具体解决办法.
2.完成程序设计并调试正确后应请指导教师检查并得到认可全部完成后应写出完整的课程设计报告成绩的重要因素A4纸装订,连同源程序软盘交__教师六.课程设计报告内容包括:--题目--问题分析和总体设计--详细设计--测试数据和调试报告--小结--简明的软件使用说明七.验收标准验收包括程序测试结果、类设计的合理性和文档质量三部分程序测试分标准数据样本的测试、随机输入数据测试、查看源代码和变更问题需求条件的随机数据测试发现有过分相似的代码和文档将另行处理。