数据结构课程设计

数据结构课程设计 一、课程的性质、教学目的 《数据结构》是一门实践性较强的软件基础课程～计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》～必须在掌握理论知识的同时编写一些在特定数据结构上的算法～通过上机调试～才能更好地掌握各种数据结构及其特点～同时提高解决计算机应用实际问题的能力。 数据结构课程设计旨在要求学生将理论与实际应用相结合～能够根据数据对象的特性～学会数据组织的方法～能把现实世界中的实际问题在计算机内部表示出来～达到以下能力:巩固和加深所学知识、提高学生综合运用所学知识的能力,查阅 手册 华为质量管理手册 下载焊接手册下载团建手册下载团建手册下载ld手册下载 及文献资料的能力,培养独立思考～深入研究～分析问题、解决问题的能力,培养基本的、良好的程序设计技能,严肃认真的工作作风和团队合作精神。 二、数据结构课程设计要求 1.通过这次设计～要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时～在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 2.学生必须仔细研读《数据结构》课程设计要求～以学生自学为主、指导教师指导为辅～认真、独立地完成课程设计的任务～有问题及时主动与指导教师沟通。 3.本次课程设计按照教学要求需要在五周时间内独立完成～五周中每天至少要保证2小时的上机来调试C或C++语言设计的程序。学院安排上机时间学生不得缺席。学生要发挥自主学习的能力～充分利用时间～安排好课设的时间 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ～并在课设过程中不断检测自己的计划完成情况～及时地向指导教师汇报。 4.每位同学须在线性表、栈和队列、树和图、查找和排序九个部分中各选一题(共10题)按以下要求完成课程设计: (1)设计、调试、运行源程序; (2)通过老师的测试及验收; (3)完成实验报告; (4)输入/输出利用文件进行(图形界面要求的除外); (5)上交相关内容要求 上交的成果的内容必须由以下三个部分组成～缺一不可 ?源程序:学生按照课程设计的具体要求所开发的所有源程序,应该放到一个文件夹中,, ?上交程序的说明文件:,保存在.txt中,在说明文档中应该写明上交程序所在的目录～上交程序的主程序文件名～如果需要安装～要有程序的安装使用说明, ?课程设计报告:,保存在word 文档中～文件名要求 按照"姓名-学号-课程设计报告题目"起名～如文件名为"张三-Exxxxxxx-二叉树动态演示".doc ,按照课程设计的具体要求建立的功能模块～每个模块要求按照“五、实验报告模板 《数据结构》 课程设计报告”内容。 5.编程语言任选。 6.学生自选课题 学生原则上可以结合个人爱好自选课题～要求自选课题必须覆盖数据结构的主要内容～有一定的深度与难度～有一定的算法复杂性～能明确体现数据抽象与组织、算法设计与性能分析以及编码实现等过程。学生自选课题需提前报课程设计指导教师批准方可 生效。 三、成绩考核 根据完成任务的情况(必须进行系统验收 + 答辩)、课程设计报告书的质量和课程设计过程中的工作态度等按照50%、30%、20%加权综合打分。成绩评定实行优秀、良好、中等、及格和不及格五个等级或对应的百分制。上机程序检查未通过者、无设计报告者以及严重抄袭他人设计者～成绩为不及格。 缺席次数 最终成绩 中等及以下 1次 不及格 2次及以上 四、设计选题 请仔细阅读每部分的要求: 选题方法一:每部分的必做题按一定的要求选题～满分60,另再选做一题选做题40～选做题有一定的难度～根据实际选做题目的难度和数量以及实现程序的完善性可以适当加减分, 选题方法二:将52个必做题进行大循环选择,学号模52+1,～满分20分～根据实际选做题目的难度和数量以及实现程序的完善性可以适当加减分,另再选做四题选做题～满分80, 同学们在选题时～要结合个人实际情况～确保及格～力争多做。 采用哪个方法选择请尽快告知～或者你们有更好的办法。一经确定～3个班的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 相同。 1.线性表部分 本部分(1)-(14)必做～学号的尾数模14+1为该生的题目。 (1)集合运算器的设计 要求实现集合的并、交、差、补、对称差和环积。 (2)航空客运订票系统 问题描述:航空客运订票的业务活动包括:查询航线、客票预订和办理退票等。试设计一个航空客运订票系统～以使上述业务可以借助计算机来完成。 设计任务:通过此系统可以实现如下功能: 录入:可以录入航班情况,数据可以存储在一个数据文件中～数据结构、具体数据自定, 查询:可以查询某个航线的情况,如～输入航班号～查询起降时间～起飞抵达城市～航班票价～票价折扣～确定航班是否满仓,,可以输入起飞抵达城市～查询飞机航班情况,根据旅客提出的终点站名输出下列信息:航班号、飞机号、星期几飞行～最近一天航班的日期和余票额, 订票:,订票情况可以存在一个数据文件中～结构自己设定,根据客户提出的要求,日期、航班号、订票数额,查询该航班票额情况～若尚有余额～则为客户办理订票手续～输出座位号,若已满员或余票额少于订票额～则需要重新询问客户要求。若需要～可预约登记排队等候。如果该航班已经无票～可以提供相关可选择航班, 退票:根据客户提供的情况,日期、航班、退票数额,～为客户办理退票手续～然后查询该航班是否有人预约登记～首先询问排在第一的客户～若所退票额能满足他的要求～则为他办理订票手续～否则依次询问其他排队预约的客户……退票成功后修改相关数据文件。 客户资料有姓名～证件号～订票数量及航班情况～订单要有编号。 修改航班信息:当航班信息改变可以修改航班数据文件 要求:根据以上功能说明～设计航班信息～订票信息的存储结构～设计程序完成功能。 测试数据:由学生任意指定～但报告上要求写出多批数据测试结果。 实现提示:每条航线应包含的信息有:终点站名、航班号、飞机号、飞行日期,星期几,、乘员定额、余票额、已订票的客户名单,包括姓名、订票额、座位号,和预约登记的客户名单,包括日期、姓名、所需票额,。这最后两项显然是一个线性表和一个队列。为查找方便、已订票客户的线性表应按客户姓名有序～并且～为插入和删除方便～应以链表作存储结构。由于预约人数无法预料～队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上～由于航线基本不变～可采用顺序存储结构～并按航班有序或按终点站名有序。每条航线是这张表上的一个记录～包含上述八个域～其中乘员名单域为指向乘员名单链表的头指针～预约登记客户名单域为分别指向队头和队尾的指针。 选做内容:当客户订票要求不能满足时～系统可向客户提供到达同一目的地的其它航线情况。 注:大家还可以充分发挥自己的想象力～增加你的系统的功能和其它服务项目。 (3)学生成绩管理系统 现有学生成绩信息文件1,1.txt,～内容如下 姓名 学号 语文 数学 英语 张明明 01 67 78 82 李成友 02 78 91 88 张辉灿 03 68 82 56 王露 04 56 45 77 陈东明 05 67 38 47 …. .. .. .. … 学生成绩信息文件2,2.txt,,内容如下: 姓名 学号 语文 数学 英语 陈果 31 57 68 82 李华明 32 88 90 68 张明东 33 48 42 56 李明国 34 50 45 87 陈道亮 35 47 58 77 …. .. .. .. … 试编写一管理系统,要求如下: ?实现对两个文件数据进行合并,生成新文件3.txt; ?抽取出三科成绩中有补考的学生并保存在一个新文件4.tx; ?对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现); ?输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现); ?要求使用结构体,链或数组等实现上述要求; ?采用多种方法且算法正确者,可适当加分。 实现功能:输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。 (4)职工管理系统 ?问题描述:对单位的职工进行管理～包括插入、删除、查找、排序等功能。 ?结构要求:职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。 ?操作要求:新增一名职工:将新增职工对象按姓名以字典方式职工管理文件中, 删除一名职工:从职工管理文件中删除一名职工对象, 查询:从职工管理文件中查询符合某些条件的职工, 修改:检索某个职工对象～对其某些属性进行修改, 排序:按某种需要对职工对象文件进行排序。 ?实现提示 职工对象数不必很多～便于一次读入内存～所有操作不经过内外存交换。由键盘输入职工对象～以文件方式保存。程序执行时先将文件读入内存,对职工对象中的"姓名"按字典顺序进行排序,对排序后的职工对象进行增、删、查询、修改、排序等操作。 ?选做内容 将职工对象按散列法存储～并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操作。 (5)电话号码查找系统 问题描述:设计散列表实现电话号码查找系统 基本要求: ?设每个记录有下列数据项:电话号码、用户名、地址, ? 从键盘输入各记录～分别以电话号码和用户名为关键字建立散列表, ?采用一定的方法解决冲突, ? 查找并显示给定电话号码的记录, ? 查找并显示给定用户名的记录。 进一步完成内容: ?系统功能的完善, ?设计不同的散列函数～比较冲突率, ?在散列函数确定的前提下～尝试各种不同类型处理冲突的方法～考察平均查找长度的变化。 (6)图书管理系统 问题描述:设计一个计算机管理系统完成图书管理基本业务。主要分为两大功能: ?图书管理(增加图书、查询图书、删除图书、图书借阅、还书), ?会员管理(增加会员、查询会员、删除会员、借书信息), 基本要求: ?每种书的登记内容包括书号、书名、著作者、现存量和库存量, ?对书号建立索引表,线性表,以提高查找效率, ?系统主要功能如下: *采编入库:新购一种书～确定书号后～登记到图书帐目表中～如果表中已有～则只将库存量增加, *借阅:如果一种书的现存量大于0～则借出一本～登记借阅者的书证号和归还期限～改变现存量, *归还:注销对借阅者的登记～改变该书的现存量。 进一步完成内容: ?系统功能的进一步完善, ?索引表采用树表, ?设计内容, ?程序流程图, ?源程序, ?软件测试报告,包括所用到的数据及结果,。 (7) 通讯录管理系统 模块要求: 第一个模块——主函数main()的功能是:根据选单的选项调用各函数～并完成相应的功能。 第二个模块——Menu()的功能是:显示英文提示选单。 第三个模块——Quit()的功能是:退出选单。 第四个模块——Create()的功能是:创建新的通讯录。 第五个模块——Add()的功能是:在通讯录的末尾～写入新的信息～并返回选单。 第六个模块——Find()的功能是:查询某人的信息～如果找到了～则显示该人的信息～如果未找到～则提示通讯录中没有此人的信息～并返回选单。 第七个模块——Alter()的功能是:修改某人的信息～如果未找到要修改的人～则提示通讯录中没有此人的信息～并返回选单。 第八个模块——Delete()的功能是:删除某人的信息～如果未找到要删除的人～则提示通讯录中没有此人的信息～并返回选单。 第九个模块——List()的功能是:显示通讯录中的所有记录。; 设计要求: ?每条信息至少包含 :姓名,NAME ,、性别(GENDER)、电话,TEL, 、城市,CITY,邮编,EIP,几项。 ?作为一个完整的系统～应具有友好的界面和较强的容错能力 (8)宿舍管理查询软件 ?任务:为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求: A. 采用交互工作方式 B. 建立数据文件 ～数据文件按关键字,姓名、学号、房号,进行排序(冒泡、选择、插入排序等任选一种) ?查询菜单: (用二分查找实现以下操作) A. 按姓名查询 B. 按学号查询 C. 按房号查询 ?打印任一查询结果,可以连续操作, (9)活期储蓄帐目管理系统 活期储蓄处理中～储户开户、销户、存入、支出活动频繁～系统设计要求: ?能比较迅速地找到储户的帐户～以实现存款、取款记账, ?能比较简单～迅速地实现插入和删除～以实现开户和销户的需要。 , (10) 商店存货管理系统,** 功能:建立一商店存货管理系统～要求每次出货时取进货时间最早且最接近保质期中止时间的货物。 分步实施: ?初步完成总体设计～搭好框架～确定人机对话的界面～确定函数个数, ?完成最低要求:建立一个文件～包括5个种类的货物情况～能对商品信息进行扩充,追加,～修改和删除以及简单的排序, ?进一步要求:扩充商品数量～以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。 (11)一元稀疏多项式的计算 任务:能够按照指数降序排列建立并输出多项式,能够完成两个多项式的相加、相减～并将结果输出, 要求:以链式存储结构实现多项式。 (12) 长整数四则运算 问题描述:设计一个实现任意长的整数进行加法运算的演示程序。基本要求:利用双向循环链表实现长整数的存储～每个结点含一个整形变量。任何整形变量的范围是 -215 - 1 215 - 1。输入和输出形式:按中国对于长整数的表示习惯～每四位一组～组间用逗号隔开。测试数据:(1)0;0;应输出“0” 。(2)-23456789;-76543211;应输出“-100000000” 。(3)-99999999;1000000000000;应输出“999(4)100010001;-100010001; 应输出“0”。(5)100010001;-100010000;应输出“1” 。(6)-999999999999;-999999999999; 应输出“1999999999998” 。(7)1000099999999;1;应输出“1000100000000”。实现提示:(1)每个结点中可以存放的最大整数为 32767～才能保证两数相加不会溢出～但若这样存放～即相当于按 32768 进制存放～在十进制与 32768 进制数之间的转换十分不方便～故可以在每个结点中仅存十进制的 4 位～即不超过 9999 的非负整数～整个链表表示为万进制。(2)可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。不能给长整数位数 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 上限。选做内容实现长整数的四则运算。 (13) 任意大非负整数的任意大非负整数次方 (14)运动会分数统计 任务:参加运动会有n个学校～学校编号为1……n。比赛分成m个男子项目～和w个女子项目。项目编号为男子1……m～女子m+1……m+w。不同的项目取前五名或前三名积分,取前五名的积分分别为:7、5、3、2、1～前三名的积分分别为:5、3、2,哪些项目取前五名或前三名由学生自己设定。,m<=20,n<=20, 功能要求: (1)可以输入各个项目的前三名或前五名的成绩, (2)能统计各学校总分; (3)可以按学校编号、男女团体总分排序输出, (4)可以按学校编号查询学校某个项目的情况,可以按项目编号查询取得前三或前五名的学校。 规定:输入数据形式和范围:20以内的整数,如果做得更好可以输入学校的名称～运动项目的名称, 输出形式:有中文提示～各学校分数为整型 界面要求:有合理的提示～每个功能可以设立菜单～根据提示～可以完成相关的功能要求。 存储结构:学生自己根据系统功能要求自己设计～但是要求运动会的相关数据要存储在数据文件中。,数据文件的数据读写方法等相关内容在c语言程序设计的书上～请自学解决,请在最后的上交资料中指明你用到的存储结构, 相关数据结构,参考,:项目名次及分值 :用二位数组Score[m+w][5]; 单项获奖情况登记表,项目编号～获奖名次、获奖学校～得分,自动得分,, 学校获奖名次表,学校编号～团体总分～名次, 测试数据:要求使用1、全部合法数据,2、整体非法数据,3、局部非法数据。进行程序测试～以保证程序的稳定。测试数据及测试结果请在上交的资料中写明, (15) 随机漫步问题,选做题, 背景介绍: 有一类被称为“随机漫步”的问题长期以来吸引这数学界的兴趣。解决这类问题(除了最简单的以外)是极其困难的。而且他们在很大程度上还远没有得到解决。其中的一个问题可以这样描述: 在一个n*m大小房间内～一只(喝醉酒的)螳螂被放在地板中央一个给定的瓷砖方格内。蟑螂在房间里随机地从一块瓷砖漫步到另一块瓷砖。假定他从目前所在的瓷砖移动到周围8块瓷砖中任意一块的概率是相等的～那么需要多少时间他才能将地板上的每块瓷砖都至少接触一次, 这个问题用纯粹的概论理论是很难解决的～但是我们可以借助计算机容易的解决它。这种技术被称作模拟～它广泛应用与工业中～用来预测交通流量～进行库存控制等等。我们可以假设正在控制的一只正在“随机漫步”的螳螂～让其在一个给定的离散空间内移动～然后～用随机和统计的方法来分析这类问题。 实习任务:编写一个程序以完成上述模拟实验过程。 您的程序需要达到下面的要求: 能处理满足2<=n<=600和2<=m<=600的所有m、n。 分别对 n=15,m=15,起始点(9.9), n=39,m=39,起始点(0.0) 两种的情况进行实验。 (3)具有迭代限制～也就是说～规定是严重螳螂移动的最大次数。对于这个习题来说～最大次数为5000000000是合适的。 (4)对每次实验～打印 螳螂进行合法移动的总次数, 每个方格被接触的次数 (5)如果假定房间的最左和最右是循环相通的～最前和最后也是循环相同的～这样～整个房间就不在一个中心了～因此～初始化任何一点都是等效的。请考虑这种问题下这个问题的解。 技术提示: 引入一个n*m的数组作为计数器(Counter)来表示螳螂到达每块瓷砖的次数。每个数组单元(作为计数器使用)都初始化为零。用坐标(x～y)表示螳螂在地板上的位臵。 为了使得可以让程序更加简单和优雅～我们可以设计另一个八元素的数组～存放八种可能的移动方法～例如:数组MoveOffset[0]=(-1,1)表示在x坐标往左移动一格～y坐标往上移动一格。那么事实上～下个时间的螳螂位臵～很容易被表示为:(x+MoveOffset[i]x,y+MoveOffset[i],y),这样～每次只要随机选择i就可以了。 我们已经可以给出～这八种移动可以是: 1,-1) MoveOffset[0]=(- MoveOffset[1]=(-1,0) MoveOffset[2]=(-1,1) MoveOffset[3]=(0,-1) MoveOffset[4]=(-0,1) MoveOffset[5]=(1,-1) MoveOffset[6]=(1,0) MoveOffset[7]=(1,1) 通过产生一个均匀分布于[0.8)的随机数K～就可以模拟一项八个给定方格之一的随机漫步过程。当然～螳螂不能移到房间之外～所以当一个指向墙壁的坐标生成时～我们必须将其忽略～然后生成一个新的组合。每到达一个方格～此方格的计数器会加一～从而计数器的每个非零元素的值表示至目前为止螳螂到达对应方格的次数。当每个方格都至少被进入了至少一次时～实验就完成了。 扩展要求: ?可以考虑将结果图形化～分析初始位臵和尺寸对结果的影响。 ?下图显示了500*500空间内每一个瓷砖被访问的次数图像的一个样例。 ?对于一组输入进行多次实验～可以得到多组结果～研究输出他们的统计特性。 根据多组数据的值～研究该问题得到结果的复杂度曲线。用近似分析的方法～估算该问题的时间复杂度的量级。 2.栈 本部分(1)-(5)必做～学号的尾数模5+1为该生的题目。 (1)括号匹配——含小括号、中括号和大括号 (2)汉诺塔问题——动态效果 (3)算术表达式求值——前缀、后缀 编写程序实现表达式求值～即验证某算术表达式的正确性～若正确～则计算该算术表达式的值。 主要功能描述如下: ?从键盘上输入表达式; ?分析该表达式是否合法(是数字～则判断该数字的合法性。若合法～则压入数据到堆栈中;是规定的运算符～则根据 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf 进行处理,在处理过程中～将计算该表达式的值;若是其它字符～则返回错误信息。 ?若上述处理过程中没有发现错误～则认为该表达式合法～并打印处理结果。 程序中应主要包含下面几个功能函数: void initstack():初始化堆栈 int Make_str():语法检查并计算 int push_operate(int operate):将操作码压入堆栈 int push_num(double num):将操作数压入堆栈 int procede(int operate):处理操作码 int change_opnd(int operate):将字符型操作码转换成优先级 int push_opnd(int operate):将操作码压入堆栈 int pop_opnd():将操作码弹出堆栈 int caculate(int cur_opnd):简单计算+～-～*～/ double pop_num():弹出操作数 (4)数制的转换 任意给定一个M进制的数x ～请实现如下要求: ?求出此数x的10进制值,用MD表示, ?实现对x向任意的一个非M进制的数的转换。 ?至少用两种或两种以上的方法实现上述要求,用栈解决～用数组解决～其它方法解决,。 (5)迷宫求解 任务:以一个m*n的长方阵表示迷宫～0和1分别表示迷宫中的通路和障碍。设计一个程序～对任意设定的迷宫～求出一条从入口到出口的通路～或得出没有通路的结论。 要求:首先实现一个栈类型～然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出～其中(i,j)指示迷宫中的一个坐标～d表示走到下一坐标的方向。 (6)马踏棋盘又名骑士漫游,选做题, 问题描述:将马随机放在国际象棋的 8X8 棋盘中的某个方格中～马按走棋规则进行移动。要求每个方格上只进入一次～走遍棋盘上全部 64 个方格。编制递归程序～求出马的行走路线 ～并按求出的行走路线～将数字 1～2～…～64 依次填入 8X8 的方阵输出之。测试数据:由读者指定可自行指定一个马的初始位臵。实现提示:每次在多个可走位臵中选择一个进行试探～其余未曾试探过的可走位臵必须用适当结构妥善管理～以备试探失败时的“回溯”悔棋使用。并探讨每次选择位臵的“最佳策略”～以减少回溯的次数。 背景介绍: 国际象棋为许多令人着迷的娱乐提供了固定的框架～而这些框架常独立于游戏本身。其中的许多框架都基于骑士奇异的L型移动规则。一个经典的例子是骑士漫游问题。从十八世纪初开始～这个问题就引起了数学家和解密爱好者的注意。简单地说～这个问题要求从棋盘上任一个方格开始按规则移动骑士～使之成功的游历国际象棋棋盘的64个方格～且每个方格都接触且仅接触一次。 可以用一种简便的方法表示问题的一个解～即将数字1～……～64按骑士到达的顺序依次放入棋盘的方格中。 一种非常巧妙的解决骑士漫游地方法由J.C.Warnsdorff于1823年给出。他给出的规则是:骑士总是移向那些具有最少出口数且尚未到达的方格之一。其中出口数是指通向尚未到达方格的出口数量。在进一步的阅读之前～你可以尝试利用Warnsdorff规则手工构造出该问题的一个解。 实习任务: 编写一个程序来获得马踏棋盘即骑士漫游问题的一个解。 您的程序需要达到下面的要求: 棋盘的规模是8*8, 对于任意给定的初始化位臵进行试验～得到漫游问题的解, 对每次实验～按照棋盘矩阵的方式～打印每个格被行径的顺序编号。 技术提示: 解决这类问题的关键是考虑数据在计算机中的存储表示。可能最自然的表示方法就是把棋盘存储在一个8*8的二维数组board中。以(x,y)为起点时骑士可能进行的八种移动。一般来说～位于(x,y)的骑士可能移动到以下方格之一:(x-2,y+1)、(x-1,y+2)、(x+1,y+2)、(x+2,y+1)、(x+2,y-1)、(x+1,y-2)、(x-1,y-2)、(x-2,y-1)。但请注意～如果(x,y)的位臵离某一条边较近～有些可能的移动就会把骑士移到棋盘之外～而这当然是不允许的。骑士的八种可能的移动可以用一个数组MoveOffset方便地表示出来: MoveOffset[0]=(-2,1) 1,2) MoveOffset[1]=(- MoveOffset[2]=(1,2) MoveOffset[3]=(2,1) MoveOffset[4]=(2,-1) MoveOffset[5]=(1,-2) MoveOffset[6]=(-1,-2) MoveOffset[7]=(-2,-1) 于是～位于(x,y)的骑士可以移动到(x+MoveOffset[k].x, y+MoveOffset[k].y)～其中k是0到7之间的某个整数值～并且新方格必须仍位于棋盘上。 扩展需求:可以考虑将结果图形化。(b)考察所有初始化的情况～测试是否都能够得到解。 3.队列 本部分(1)-(8) 必做～学号的尾数模8+1为该生的题目。 (1)猴子选大王 任务:一堆猴子都有编号～编号是1～2～3 ...m ,这群猴子,m个,按照1--m的顺序围坐一圈～从第1开始数～每数到第N个～该猴子就要离开此圈～这样依次下来～直到圈中只剩下最后一只猴子～则该猴子为大王。 要求:输入数据:输入m,n。 m,n 为整数～nTIMEOUT_FREQUENCY) m_OnlineAccounts.Remove(acc.id); } m_LastCheckTimestamp = Datetime.Now; } 输出文本: Protected void Check() { Timespan tspan = DateTime.Now – m_LastCheckTimestamp; Timespan timespan = DateTime.Now – m_LastCheckTimestamp; if (tspan.TotalSeconds < CHECK_FREQUENCY) return; foreach (object val in m_OnlineAccounts.Values) { OnlineAccountInfo acc = (OnlineAccountInfo)val; if (acc == null) continue; tspan = DatTime.Now – acc.timestamp; if(tspan.TotalSeconds > TIMEOUT_FREQUENCY) m_OnlineAccounts.Remove(acc.id); } m_LastCheckTimestamp = DateTime.Now; } 上面的文本比对由于是逐行进行的～事实上～每一行就是上面例子中序列中的一个元素。下面～对基本的比对算法(编辑路径)给出一个并非最优的思路提示: 对于{ai}和{bj}两个序列～顺序考察每一个元素, 开辟两个扫描指针～p 和 q 分别表示对两个序列扫描的指针, 当考察到ap元素的时候～增加 l=q,q+1,q+2,…,q+N直到扫描完成或者ap=bl。 当考察到bq元素的时候～增加 t=p,p+1,p+2,…,p+M直到扫描完成或者at=bq。 取l 和t 的改变最小的值作为p和q 移动的步长～分析修改而得到的成本。 下面～将给出一个例子来说明上面的算法: 假设～扫描 窗口M=N=5～{ai}=[1,3,0,5,3]变为{bj}=[1,5,4,3]。 [1,3,0,5,] [1,5,4,3] a[p]==b[q] 不产生输出和成本 P ? q? 向后移动p,q [1,2,0,5,3] [1,5,4,3] 若让a[t]==b[q],t=p+2 对应删除a[1]和p? t? q? l? 若让b[l]==a[p], l=q+2 a[2]的两次删除操 因为2==2～任取依着～即作～产生成本4 让p移动到t. q仍然保持不变。 [1,3,0,5,3] [1,5,4,3] a[p]==b[q] 不产生输出和成本 p? q? 向后移动p,q [1,3,0,5,3] [1,5,4,3] 若让a[t]==b[q],无解 对应插入4的操作～ p? q?l? 若让 b[l]==a[p], l=q+1 产生成本1 取l=q+1,因此让q移动 到1 P 仍然保持不变 [1,3,0,5,3] [1,5,4,3] a[p]==b[q] 不产生输出和成本 p? q? 向后移动p,q 当文本太长的时候～猜测l和t不能无限制地往后查找～因此～我们常常设定一个扫描窗口M和N～当扫描口内无解的时候～我们就索性将源中的这行删除～直接原地插入目标中的对应行(当然～这样 要付出更多的成本)～这样至少可以得到一个可行解。事实证明～不是M和N越大～得到的结果就越好～我们可以测试一下～对于一个特定长度的文本～如何取M和N能够得到比较好的结果。 扩展需求: 可以考虑将结果图形化～或者渲染为HTML彩色输出。 考虑如果增加替换原子操作Replace(k,v)将如何改变算法获得最小的代价。 5. 多维数组和广义表的应用 本部分(1)-(3)必做～学号的尾数模3+1为该生的题目。 (1)稀疏矩阵运算器,压缩存储、快速转臵、求和、求积等, (2)特殊矩阵压缩与解压缩设计,对称、三角、带状, (3)魔方阵,幻方, 要求:至少用3种方法构造奇数阶幻方,3种方法构造偶数阶幻方 (4)数独,选做题, “数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”～是大数学家欧拉于1783年发明的。 6 树结构的应用 本部分(1)-(6)必做～学号的尾数模6+1为该生的题目。 (1) 存储结构与基本运算的算法 要求:实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法～层次序的非递归算法的实现～应包含建树的实现。 (2) 线索二叉树的创建与遍历 (3) 由前序和中序遍历确定二叉树,递归和非递归两种方法, (4) 由中序和后序遍历确定二叉树,递归和非递归两种方法, (5) 电文的编码和译码——简单Huffman编码/译码的设计与实现 [问题描述]利用哈夫曼编码进行信息通信可以大大提高信道利用率～缩短信息传输时间～降低传输成本。但是～这要求在发送端通过一个编码系统对待传数据预先编码～在接收端将传来的数据进行译码,复原,。对于双工信道,即可以双向传输信息的信道,～每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。 [基本要求]一个完整的系统应具有以下功能: ?I:初始化,Initialization,。从终端读入字符集大小n～以及n个字符和n个权值～建立哈夫曼树～并将它存于文件hfmTree中。 ?E:编码,Encoding,。利用已建好的哈夫曼树,如不在内存～则从文件htmTree中读入,～对文件ToBeTran中的正文进行编码～然后将结果存入文件CodeFile中。 ?D:译码,Decoding,。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码～结果存入文件TextFile中。 ?P:印代码文件,Print,。将文件CodeFile以紧凑格式显示在终端上～每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 ?T:印哈夫曼树,Tree Printing,。将已在内存中的哈夫曼树以直观的方式,树或凹入表形式,显示在终端上～同时将此字符形式的哈夫曼树写入文件TreePrint中。 测试数据: ?数据一:已知某系统在通信联络中只可能出现8种字符～其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序进行调试。 ?用下表给出的字符集和频度的实际统计数据建立哈夫曼树～并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。 字符 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 实现提示: ?文件CodeFile的基类型可以设为子界型bit = 0..1。 ?用户界面可以设计为“菜单”方式:显示上述功能符号～再加上“Q”～表示运行Quit。请用户键入一个先把功能符～些功能执行完毕后再经菜单～直至某次用户先把了“E”为止。 ?在程序的一次执行过程中～第一次执行I、D或C命令之后～哈夫曼树已经在内存了～不必再读入。每次执行中不一定执行I命令～因为文件hfmTree可能早已建好。 (6) 家族关系查询系统——名著家谱图 (7)重言式判别(选做题) 问题描述一个逻辑表达式如果对于其变元的任一种取值均为真～则成为重言式;反之～如果对于其变元的任一种取值都为假～则称为矛盾式～然而～更多的情况下～既非重言式～也非矛盾式。试写一个程序～通过真值表判别一个逻辑表达式属于上述哪一类。～ 基本要求(1) 逻辑表达式从终端输入～长度不超过一行。逻辑运算符包括“|”、“&”和“~”～分别表示或、与和非～运算优先程度递增～但可有括号改变～即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。(2)若是重言式或矛盾式～可以只显示“True Forever”或“False Forever”～否则显示“Satisfactible”以及变量名序列～与用户交互。若用户对表达式变元取定一组值～程序就求出并显示逻辑表达式的值。测试数据(1)(A|~A)&(BB)(2)(Aamp~A)&C(3)ABCDE|~A实现提示1 识别逻辑表达式的符号形式并建立二叉树可以有两种策略: 自底向上的算符优先法和自顶向下分割～先序遍历建立二叉树的方法。2 可设表达式中逻辑变量数不超过 20。真值的产生可以通过在一维数组上维护一个“软计数器”实现～用递归算法实现更简单。 7图 必做～学号的尾数模7+1为该生的题目。 本部分(1)必做～(2)-(8) (1)图的邻接矩阵存储结构建立 问题描述:建立图的邻接矩阵存储结构(图的类型可以是有向图或有向网、无向图或无向网～学生可以任选一种类型)～能够输入图的顶点和边的信息～并存储到相应存储结构中～而后给出图的 DFS,BFS次序。 要求: ?先任意创建一个图, ?图的DFS,BFS的递归和非递归算法的实现 (2)最小生成树,两个算法,的实现～求连通分量的实现 设计要求:在n个城市之间建设网络～只需保证连通即可～求最经济的架设方法。存储结构采用多种;求解算法多种。要求用邻接矩阵、邻接表、十字链表多种结构存储实现 (3)农夫过河问题——动态实现 (4)公园导游系统——旅游路线安排模拟系统 (5)安排教学计划——排课软件 [问题描述]大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限～每学年含两学期～每学期的时间长度和学分上限值均相等～每个专业开设的课程都是确定的～而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的～可以有任意多门～也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 [基本要求] (1)输入参数包括:学期总数～一学期的学分上限～每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。 (2)允许用户指定下列两种编排策略之一:一是使学生在各学期中的学习负担尽量均匀,二是使课程尽可能地集中在前几个学期中。 (3)若根据给定的条件问题无解～则报告适当的信息,否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。 [测试数据] 学期总数:6,学分上限:10,该专业共开设12门课～课程号从C01到C12～学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下: 课程编号 课程名称 先决条件 C1 程序设计基础 无 C2 离散数学 C1 C3 数据结构 C1～C2 C4 汇编语言 C1 C5 语言的设计和分析 C3～C4 C6 计算机原理 C11 C7 编译原理 C5～C3 C8 操作系统 C3～C6 C9 高等数学 无 C10 线性代数 C9 C11 普通物理 C9 C12 数值分析 C9～C10～C1 [实现提示] 可设学期总数不超过12～课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中～则作为错误处理。应建立内部课程序号与课程号之间的对应关系。 (6)校园导航 问题描述(1)设计你的学校的校园平面图～所含景点不少于 10 个。以图中顶点表示学校各景点～存放景点名称、代号、简介等信息;以边表示路径～存放路径长度等相关信息。(2)为来访客人提供图中任意景点的问路查询～即查询任意两个景点之间的一条最短的简单路径。(3)为来访客人提供图中任意景点相关信息的查询。测试数据由读者根据实际情况指定。 实现提示:一般情况下～校园的道路是双向通行的～可设计校园平面图是一个无向网。顶点和边均含有相关信息。 (7)拓扑排序和关键路径 (8)最短路径——Dijkstra、Floyd算法(学校超市选址问题、全国铁路运输网最佳经由问题) 问题描述:学校超市选址问题,带权有向图的中心点, 设计要求:对于某一学校超市～其他各单位到其的距离不同～同时各单位人员去超市的频度也不同。请为超市选址～要求实现总体最优。 (9)全国铁路运输网最佳经由问题,选做题, 问题描述:这是上海铁路局目前仍在使用的行包托运软件中的一部分内部算法。该题目采用1995年年底我国铁路运输网的真实数据进行编程和运行验证。 铁路运输网络中由铁路线和火车站的两个主要概念～譬如:1号铁路线表示京广线～2号铁路线表示京沪线等。 铁路线对象包括铁路线编号,铁路线名称～起始站编号,终点站编号,该铁路线长度～通行标志(00B客货运禁行,01B货运通行专线～10B客运通行专线～11B客货运通行)。 火车站对象包括所属铁路线编号～车站代码～车站名～车站简称～离该铁路线起点站路程及终点站路程。 设计要求: ?查询某站所属的铁路线 ?要求具备新增铁路线的管理功能 ?要求具备新增车站的管理功能 ?针对客运～货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序。 (10)中国道路交通网络信息查询系统,选做题, 问题描述:出于不同的目的的旅客对交通工具有不同的要求。例如～因公出差的旅客希望在旅途中的时间尽可能短～出门旅游的游客则期望旅费尽可能省～而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序～为旅客提供两种或三种最优决策的交通咨询。 基本要求: ?提供对城市信息进行编辑,如:添加或删除,的功能。 ?城市之间有两种交通工具:火车和飞机。提供对列车时刻表和飞机航班进行编辑,增设或删除,的功能。 ?提供两种最优决策:最快到达或最省钱到达。全程只考虑一种交通工具, ?旅途中耗费的总时间应该包括中转站的等候时间, ?咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具～输出信息:最快需要多长时间才能到达或者最少需要多少旅费才能到达～并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。 测试数据:参考《数据结构》清华版7.6节图7.33的全国交通图,自行设计列车时刻表和飞机航班。 实现提示: ?对时刻表和飞机航班进行编辑,应提供文件输入和键盘输入两种形式。飞机航班信息包括:起始站的出发时间,终点站的到达时间和票价;列车时刻表则需 根据交通图给出各个路段的详细信息,如:对从北京到上海的火车,给出北京至天 津,天津至徐州及徐州至上海各段的出发时间,到达时间及票价等信息。 ?以邻接表作交通图的存储结构,表示边的结构内除含有邻接点的信息外,还包括交通工具,路途中耗费的时间和花费以及出发和到达时间等多种属性。 选做内容:增加旅途中中转次数最少的最优决策。 8.查找 各种查找算法性能比较 ?静态查找——折半查找和斐波拉契查找,有序, ?动态查找 ?散列法查找 在Hash查找方法中～散列函数构造方法多种多样～同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法～做实验观察～不同的解决冲突方法对查询性能的影响。 9.排序 各种排序算法性能比较 利用随机函数产生N个随机整数,20000以上,～对这些数进行多种方法进行排序。 要求: ?至少采用三种方法实现上述问题求解,提示～可采用的方法有插入排序、2-路插入排序、希尔排序、起泡排序、改进的冒泡排序、快速排序、选择排序、堆排序、归并排序、三部排序、计数排序、鸽巢排序、鸡尾酒排序、地精排序、奇偶排序、梳排序、 耐心排序——标红的至少选择一种,。并把排序后的结果保存在不同的文件中。 ?统计每一种排序方法的性能,以上机运行程序所花费的时间为准进行对比,～找出其中两种较快的方法。 ?如果采用4种或4种以上的方法者～可适当加分。 ?如果采用动态演示方法者～可适当加分。 10.游戏类 纸牌游戏 任务:编号为1-52张牌～正面向上～从第2张开始～以2为基数～是2的倍数的牌翻一次～直到最后一张牌,然后～从第3张开始～以3为基数～是3的倍数的牌翻一次～直到最后一张牌,然后…从第4张开始～以4为基数～是4的倍数的牌翻一次～ 直到最后一张牌,...再依次5的倍数的牌翻一次～6的～7的 直到 以52为基数的 翻过～输出:这时正面向上的牌有哪些, 五、实验报告模板 《数据结构》 课程设计报告 课程名称: 《数据结构》课程设计 课程设计题目: XXXXXXX(下文以民航航班查询系统为例) 姓 名: 计算机学院 院系: 专 业: 年 级: 学 号: 指导教师: 年 10月 12 日 2013 目 录 1 课程设计的目的………………………………………………………………x 2 需求分析………………………………………………………………………x 3 课程设计报告内容……………………………………………………………x 3.1概要设计……………………………………………………………………x 3.2详细设计……………………………………………………………………x 3.3调试分析……………………………………………………………………x 3.4用户手册……………………………………………………………………x 3.5测试结果……………………………………………………………………x 3.6程序清单……………………………………………………………………x 4 小结 …………………………………………………………………………x 5 参考文献 ………………………………………………………………x 1.课程设计的目的 (1) 熟练使用 C 语言编写程序～解决实际问题; (2) 了解并掌握数据结构与算法的设计方法～具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2.需求分析 在该部分中叙述～每个模块的功能要求。 3 XXXXXXX的设计 3.1概要设计 在此说明每个部分的算法设计说明,可以是描述每一个算法的流程图,～每个程序中使用的存储结构设计说明,如果指定存储结构请写出该存储结构的定义。 3.2详细设计 各个算法实现的源程序～对每个题目要有相应的源程序,可以是一组源程序～每个功能模块采用不同的函数实现, 源程序要按照写程序的规则来编写。要结构清晰～重点函数的重点变量～重点功能部分要加上清晰的程序注释。 3.3调试分析 测试数据～测试输出的结果～时间复杂度分析～和每个模块设计和调试时存在问题的思考,问题是哪些,问题如何解决,,～算法的改进设想。 3.4用户手册(略) 3.5测试结果(略) 4总结 总结可以包括 : 课程设计 过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容。 5、程序清单:(见附录) 、参考文献1 严蔚敏～吴伟民 编著. 数据结构(C 语言版)--北京: 清华大学出版6 社～2007.2 严蔚敏～吴伟民 米 宁 编著. 数据结构题集(C 语言版)--北京: 清华大学出版社～ 2007.3网上搜索相关程序作为参考 、程序运行结果 7 运行截图