数据结构与算法课程设计任务书使用时间：2011-2012学年第2学期一、课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、课程设计题目共10题，每个学生一题，单独完成。（选法为根据学生所在班级名册的自然顺序，第1-12名同学分别做第1到第12题，然后循环，第13-24名同学分别做第1到第12题，依次类推。）1、 银行业务活动的模拟任务：假设某银行有4个窗口对外接待客户，从早晨银行开门起不断有客户进入银行，由于每个窗口在某个时刻只能接待一个客户。因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户。如果某个窗口的业务员正空闲，则可上前输业务。反之，若个窗口均有客户所占，他便会排在为数最少的队伍后面。编制一个程序模拟银行的这种业务活动并计算一天中客户在银行的平均逗留时间。功能要求：1).实现数据的输入；2).各个窗口数据的访问和输出；3)当前窗口的人员分布情况动态显示。界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计。请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2、 航班订票系统任务：通过此系统可以实现如下功能：1）、录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2）、查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；3）、订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；4）、退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。5）、修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计。请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；3、 迷宫问题非递归求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；4、链表的维护与文件形式的保存用链表结构的有序表表示某商场家电的库存模型。当有提货或进货时需要对该链表进行维护。每个工作日结束之后，将该链表中的数据以文件形式保存，每日开始营业之前，需将以文件形式保存的数据恢复成链表结构的有序表。链表结点的数据域包括家电名称、品牌、单价和数量，以单价的升序体现链表的有序性。程序功能包括：创建表、营业开始（读入文件恢复链表数据）、进货（插入）、提货（更新或删除）、查询信息、更新信息、营业结束（链表数据存入文件）等。5、 各种内部排序性能比较任务：用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。功能要求：给出多组不同元素个数的输入数据(可考虑用随机函数生成整数，而不用人工输入)，并用列表打印出每种排序下的各趟排序结果。每个排序法结束时应打印出其元素比较的次数和交换的次数。此程序需将结果用列表打印，一定要将其打印结果排列好。6、基于医院分诊系统的排队策略1）问题的提出: 近年来，随着医疗事业的发展，医院的规模不断扩大，科室门类划分的也越来越细，随之而来的是病人排队挂号和看病变的繁琐，等待时间变长，为此，需要制定一种良好的排队策略，减少病人的等待时间，提高医院的服务质量。2)问题的假设: 1， 我们假设医院实行八小时工作制，一天工作八小时,即480分钟。2， 医院门诊分为普通号和专家号，普通号一个可是有数为医生，专家号一个可是仅有一个医生，并且将普通好和专家号相互独立，以方便模拟。3， 我们将病人分为A类和B类，对于A类病人，我们仅进行一次诊断，即用户挂号后进入队列，在进行一次诊断后即完成诊治。B类病人需要进行两次诊断和一次检查，在完成一次诊断后，医生开出检查意见，病人进行检查，完成后病人需返回科室进行第二次诊断，在第二次完成后即完成诊治。4， 虽然实际中在一定时间内病人的产生应该按照泊松分布，由于参数设定的困难，我们将病人的产生使用一般的随机数生成，同理，病人的诊治时间也使用确定的时间。5， 实际中，每位医生每天接诊的人数是有一定限制的，尤其是专家门诊。但考虑病人来源的数据无论自实际数据库，还是来自根据实际情况的随机模拟数据，各类病人的数量都对应了实际的各科室接诊病人的限制。6， 对于由于到达时间过晚，部分病人将无法完成诊断，我们将忽略这部分病人。3)两种策略的制定：一级分诊队列模式: 每个诊室队列只对应一个诊区候诊队列，我们将之记作Q，一般排队规则是：刚完成挂号的病人，添加在Q的末尾；按医嘱完成体检的病人，直接插入在Q的首部。这种排队规则广泛应用于中小医院。二级分诊队列模式: 每个诊室队列对应一个诊区候诊队列和一个候诊厅候诊队列，我们将前者记作Q1，后者记作Q2。一般情况下，因为诊区空间限制，Q1的人数限制在2、3人左右；而候诊厅空间较大，所以对Q2的人数不作限制。一般排队规则是：刚完成挂号的病人，添加在Q2的末尾；按医嘱完成体检的病人，直接插入在Q2的首部；医师始终对Q1中的首位病人诊治，每位病人诊治结束时，若Q2不空，则Q2的首位病人脱离Q2，进入Q1的尾部。这种排队规则广泛应用于大中型医院。7、题目：压缩软件的实现-采用哈夫曼编码技术准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。8、题目：散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。9、利用栈求表达式的值，可供小学生作业，并能给出分数要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价10、学校超市选址问题（带权有向图的中心点）设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。11、管道铺设施工的最佳方案选择N(N10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管道，但代价不同。事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少，并希望以图形方式在屏幕上输出结果。12、利用哈希技术统计C源程序关键字出现频度1)题目内容：利用Hash技术统计某个C源程序中的关键字出现的频度2)基本要求：扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为：Hash(key)(key的第一个字母序号)*100+(key的最后一个字母序号) MOD 41三、课程设计要求：1、1人一题，且需独立完成。2、每人的设计程序必须为可执行的exe文件，且需指导教师验收合格。学生程序必须在课程设计的最后一天交由指导教师验收合格。过期不再验收程序，如程序验收不合格或在规定时间内未经指导教师验收，则视为该生程序没有完成。3、每人必须在规定时间内到机房做程序，指导老师将严格考勤，上机期间严禁做与课程设计无关的事情。指导教师将随时抽查。4、每人必须撰写课程设计报告并上交纸质稿（格式附后）。并上交报告电子稿和程序代码电子稿（每位同学先建立一个文件夹，取名规则为“学号姓名”，文件夹里存放上交电子内容，分别是“学号姓名报告” 和“学号姓名程序”，每班取一文件夹名，取名规则为班级号，内放该班同学上交内容，每班学习委员统一收齐后拷贝给指导老师。特别注意，上交的程序必须是在相应的编程环境下存在的文件，不能是*.txt或*.doc文件等。四、课程设计评分标准：1程序设计质量（占40%）2课程设计报告质量（占40%）3平时表现（占20%）附：课程设计报告格式。1、 需求分析说明（说明为何做该题目，程序最终需要完成的功能，从其需求上说明。）2、 总体设计（从总体上说明该题目的框架，用文字和图表说明）3、 详细设计（对数据结构进行详细的描述，设计好相应数据结构以及其操作功能，要求用C+设计成类；用文字详细描述每个功能实现的算法及思路。）4、 实现部分（主要描述程序调试过程，报告中只要贴入核心代码）5、 程序测试（给出各测试数据及其对应的测试结果，和程序运行图贴于此处。并能对程序运行结果分析之，且需提出改进算法。）6、 总结7、 自需要提交电子文档：个人的学号_个人的名字_报告.doc 个人的学号_个人的名字_源代码.doc *课程设计报告 题目： 学生姓名： 学 号： 班 级： 指导教师： 2012年 月 日3东华理工大学 软件学院 软件工程系