《数据结构实训》教学大纲
一、实训的性质和目的
《数据结构》实训是计算机专业集中实践性环节之一,其目的就是要达到理论与实际应用相结合,使学生能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来,并培养良好的程序设计技能。
二、实训教学的基本内容和要求
本实训面向应用,以解决实际问题为主。题目以选用学生相对比较熟悉的为宜,要求通过本实训,理解有关数据结构的基本概念、不同数据类型的存储和基本操作的算法实现,理解数据类型的逻辑结构及物理存储结构, 通过自己设计,编程、调试、测试、能够基本掌握在不同存储结构下的算法实现及算法优化,树立并培养系统规范开发的理念。实训中学生要将相关课程中学到的知识、思想和理念尽量应用在实训中。结束后要按规定提交代码和各种文档。
实训基本步骤:
1. 选题
设计的课题尽量结合教学、科研的实际课题,规模、大小适当,具有一定复杂度。应根据题目大小、难度确定是否分组,组内成员人数。
2. 数据结构及算法设计
根据需求分析,选择合理的数据结构及设计相应的算法。
3. 编码
根据已设计的数据结构和算法,编写代码。
4. 测试
按照系统测试的原则、方法和步骤,对系统进行测试。测试中应形成测试报告。
5. 编写实训报告
实训说明书,内容及要求如下:
(1) 封面
(2) 成绩评定
(3) 目录
(4) 说明书正文,主要内容包括:
一、 设计题目
二、 设计目的
三、数据结构及算法设计
四、 源代码
五、 运行结果分析
六、 实习总结(收获及体会)
七、参考资料;附录(核心代码)。
三、实训的进度安排
实训进度应由学生根据实训时间、本组学生人数、系统大小、难易,自行制定项目进度计划。进度大体安排可参考下表。
四、实训的考核
1. 成绩考核,以实训各阶段完成情况、系统运行情况为主,实训报告为辅。两者都必须达到基本要求,若有一项不达要求,成绩计为不及格。
2. 设计未完成或未达到老师要求的计为不及格。
3. 实训中有新思路、新方法,酌情加分。
4. 学生不允许请别人代作或相互抄袭,如发现上述情况,双方均取消实训资格。
5. 分组时,小组成员应有明确分工,检查时按分工完成情况计算成绩,组员之间实训报告不能雷同。
五、其他
1. 对学生的要求
(1) 每组两题,每组不许超过两人。
(2) 应认真阅读设计指导书,了解所做的设计内容及要求,完成课设。有问题及时主动通过各种方式与教师联系沟通。
(3) 学生要发挥自主学习的能力,查阅相关的参考文献;完成设计任务。
(4) 认真撰写实训报告,要求格式规范、文字通顺。
(5) 相关实训上交资料:
①源程序:学生开发的所有源程序。②实训报告。
2. 参考题目
课程设计题一:顺序表操作
一、 设计目的
1.掌握顺序表的建立。
2.掌握顺序表的基本操作。
二、设计内容和要求
建立顺序表,然后实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算(查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数),并能在屏幕上输出操作前后的结果。
课程设计题二:链表操作
一、 设计目的
1.掌握线性链表的建立。
2.掌握线性链表的基本操作。
二、设计内容和要求
建立线性链表,然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算(查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数),并能在屏幕上输出操作前后的结果。
课程设计题三:二叉树的基本操作
一、 设计目的
1.掌握二叉树的概念和性质
2. 掌握任意二叉树存储结构。
3.掌握任意二叉树的基本操作。
二、设计内容和要求
1.对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构,并实现二叉树的先序、中序、后序三种遍历,输出三种遍历的结果。
2. 求二叉树高度、结点数、度为1的结点数和叶子结点数。
山东科技大学泰山科技学院
课程实训说明书
课程:
题目:
院 系:
专业班级:
学 号:
学生姓名:
指导教师:
年 月 日
成绩
评语:
指导教师
第二篇:20xx级数据结构实训指导书(20xx年12月)
《数据结构课程设计》指导书
说明:本指导书适用于2012级1-4班
一、课程设计的目的、要求和任务
本课程设计是为了配合《数据结构》课程的开设,通过设计完整的程序,使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成程序并用上机调试的基本方法。
1.课程的目的
(1) 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结
构和操作实现算法,以及它们在程序中的使用方法。
(2) 使学生掌握软件设计的基本内容和设计方法,并培养学生进行规范化软件设计的
能力。
(3) 使学生掌握使用各种计算机资料和有关参考资料,提高学生进行程序设计的基本
能力;
2.课程的基本要求与任务
(1) 巩固和加深对数据结构基本知识的理解,提高综合运用课程知识的能力。
(2) 培养学生自学参考书籍,查阅手册、图表和文献资料的能力。
(3) 通过实际课程设计,初步掌握简单软件的分析方法和设计方法。
(4) 了解与课程有关的工程技术规范,能正确解释和分析实验结果。
(5) 题目具有足够的工作量。
二、课程设计的一般步骤:
1. 选题与搜集资料:每人选择一题(每题有几个同学选),进行课程设计课题的资料搜集。
2. 分析与概要设计:根据搜集的资料,进行程序功能与数据结构分析,并选择合适的数据结构、并在此基础上进行实现程序功能的算法设计。
3. 程序设计:运用掌握C/C++语言编写程序,分工实现各个模块功能。
4. 调试与测试:调试程序,并记录测试情况。
5. 完成课程设计报告。
6. 验收与评分:指导教师对每个同学的开发的系统进行综合验收,并由学院考核小组进行随机抽查评分。
三、课程设计成果的规范(详见文档模板)
课程设计成果应包括如下3个部分:
1.一个小组一份《设计文档》,其中包括:
a) 系统功能模块图(有流程图附上)
b) 系统定义的数据结构;
c) 系统设计的主要功能函数及功能简介
d) 项目组成员的分工情况
2. 每个同学一份《实训报告》,其中包括:
a) 问题描述
b) 基本要求
c) 系统分析与设计
d) 测试数据及结果
e) 总结
3. 附录:源程序清单
四、成绩评定标准
学生成绩由以下几个方面进行评定:
1. 学生编写的实际软件和运行结果,占总成绩50%;
2. 设计报告,占总成绩30%
3. 答辩,占总成绩10%
4. 出勤,占总成绩10%
五、实习过程
项目实训过程分为以下六个阶段,各阶段如下:
1、 功能分析(0.25天)
2、 模块划分及总体设计(0.75天)
3、 数据结构定义、详细设计(0.5天)
4、 编码(2.5天)
5、 测试修订(1天)
6、 答辩(1天)
合计6天。
六、备注:
1. 选题:
(1) 以下给出的课程设计题目分为四类,学生可以从任何一类中选择一个题目,并做
好相关准备(注意每一题限报人数);
(2) 时间安排:
从20xx年12月21日——12月26日,共6天,每天从上午8:30——11:30,下午从14:00——17:00
2. 功能完成及检测
(1) 要求独立完成规定的工作任务,不得弄虚作假,不准抄袭他人内容,否则成绩以
不及格计。
(2) 鼓励同学们充分发挥主观能动性,结合所选课题,独立思考,努力钻研,勤于实
践,勇于创新,在完成题目的基本要求外,尽量完善程序,提高程序的可读性、健壮性等,完成好的同学,给以适当加分。
课程设计题目
1 管理类
1.1
难度:
中
需求功能表:
电子中英文词典
1. 第一阶段要求用控制台应用程序实现该项目需求;
2. 项目基本要求:
(1) 实现启动画面及选择菜单。
(2) 实现简单的文本交互界面。
(3) 实现词典管理的功能。
(4) 能够按照英文单词检索词条。
3. 选做功能及模块:加入按照中文关键词检索词条的功能。
4. 在非常漂亮的完成了第一阶段的所有任务之后,如果团队想进一步提高软件的交互
性,选择使用VC++的MFC框架来改造控制台应用程序至Windows桌面应用程序; 主要技术点:
数组,结构体,链表。
技术难点:
中文关键词检索
团队配置:
其他:
无。 4人
1.2 停车场管理系统
难度:中
问题描述:
设计一个停车场管理系统,模拟停车场的运作。
(1)
理;
(2)
功能需求表:
要求处理的数据元素包括如下数据项:汽车“到达”或“离去”信息、汽车牌照及“到达”或“离去”的时刻; 要求以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管
项目要求:
1. 人机交互界面友好,对用户的非法输入要有一定的判断及提示;
2. 可根据基本要求,对系统的功能作进一步的完善;
3. 在很好完成必做模块的前提下,如又实现了选做模块,将给团队和相应个人加分; 主要技术点:
数组,链表,队列。
技术难点:
队列思想
团队配置:
其他:
无。 4人
1.3 运动会排名系统
难度:难
需求功能表:
1. 第一阶段要求用控制台应用程序实现该项目需求;
2. 实现友好的操作界面,使用户能根据界面提示进入相应的操作模块;
3. 基本的功能与模块需要实现:显示界面,按奖牌数排名、按项目排名、按国家查询、
按项目查询、更新项目信息、帮助。通过项目列表中记录的参与运动员及其国家等信息,生成国家信息列表。
4. 选做功能及模块:按积分排序、更新国家信息和运动员信息能同步更新相关列表;
5. 在非常漂亮的完成了第一阶段的所有任务之后,如果团队想进一步提高软件的交互
性,选择使用VC++的MFC框架来改造控制台应用程序至Windows桌面应用程序;
6. 可根据项目完成情况,在数据输入部分,添加利用文件导入的功能;在数据输出部
分,添加数据导出到文件的功能;
7. 关于项目加分:在很好完成必做模块的前提下,如又实现了选做模块,将给团队和相
应个人加分;
在很好地利用控制台应用程序完成项目后,如团队使用Windows桌面应用程序实现,将给团队和相应个人加分。
主要技术点:
数组,队列,链表。
技术难点:
链表的使用、查找。
团队配置:
4人
1.4 银行营业厅业务模拟系统
难度:难
问题描述:
设计一个银行业务模拟系统,模拟银行营业厅的运作。
(1) 业务流程为:客户到达营业听,选择业务类型并取号,然后等待被窗口叫号;
客户被叫号后,到对应窗口办理业务,完成后离开。客户包括普通客户、VIP客户、团体客户三种。设该营业厅一共有四个窗口。其中有三个窗口为普通窗口,一个窗口是VIP客户窗口,当有VIP客户时办理VIP客户业务,若当前无VIP客户,则视为普通窗口。普通窗口专为普通客户和团体客户开放。要求以队列模拟客户到达后的排队等待和办理完业务的离开过程。通过终端读入的输入数据序列进行模拟管理。
(2) 客户所办理的业务包括存款、取款、转账、开户等,每种业务的办理时间不
同。每个窗口业务员为客户办理不通业务时时间也不全相同。设客户是随机到达银行营业厅。
(3) 设银行工作时间从8:30AM- 17:30PM。
功能需求表:
项目要求:
1. 根据以上描述的流程和功能要求,灵活应用相关数据结构只是模拟实现系统;
2. 人机交互界面友好,对用户的非法输入要有一定的判断及提示;
3. 可根据基本要求,对系统的功能作进一步的完善;
4. 在很好完成必做模块的前提下,如又实现如下加分项:(1) 若能给出每位客户排号时
的预计等待时间,(2) 一天中客户在银行逗留的平均时间, (3) 若能形象模拟整个银行营业厅业务流程,将给团队及相应个人加分。
主要技术点:
队列
技术难点:
队列思想
团队配置:
其他:
无。 4人
2 通信类
2.1 邮件发送程序客户端- C或C++
技术难度:
难
需求描述:
SMTP协议是用于发送电子邮件的主要通信协议,是C语言进行网络编程时经常都会使用到的基础协议之一。邮件发送客户端程序要求使用C语言socket通信来完成SMTP协议,同时结合路由(图)等知识实现邮件发送程序的客户端应用,通过该程序能够向远程的SMTP服务器发送电子邮件的请求,并发送到指定的电子邮箱之中。
项目要求:
本程序需要完成的功能较多,因此在实现时建议通过以下两个阶段来完成。
? 第一阶段:只要求通过dos窗口实现简单文本邮件的发送,具体的要求如下:
? 程序启动后录入SMTP服务器地址;
? 录入SMTP服务器用户名和密码;
? 录入收件人地址和抄送人地址(允许录入多个,中间以分号分隔);
? 录入邮件主题;
? 录入邮件内容完成后发送邮件;
? 邮件发送成功后系统提供邮件发送成功;
? 第二阶段:要求能够实现发送MIME格式邮件或利用Win32编程将程序升级为桌面应
用程序,进入第二阶段必须满足以下条件:
? 必须是在充分理解SMTP协议的基础上;
? 必须是在充分理解MIME格式的基础上;
? 利用C语言将发送的内容格式化为MIME格式;
? 可以首先考虑只实现MIME格式的一部分格式化需求;
? 升级桌面应用程序必须对Win32 API有一定的理解和掌握;
整个邮件发送程序必须首先要对SMTP协议有比较全面的理解,并且对如何使用socket进行网络通信要有较为熟悉的使用,同时还需要对base64编码有所了解,并利用C语言实现对其编码。
SMTP 协议可以参考附件中的SMTP协议说明;
主要技术点:
C语言基础、字符串处理、指针、socket编程、图、SMTP协议、base64编码; 技术难点:
socket编程、SMTP协议的理解、base64编码
团队配置:
其它:
无 4人
2.2 电子邮件管理程序- C或C++
技术难度
难
需求描述:
POP3协议是实现邮件服务器邮件管理的基础协议之一,与SMTP协议一起构成了整个电子邮件的基础。电子邮件管理程序要求利用C语言的socket通信,运用指针、栈等知识,实现POP3协议管理远程电子邮件服务器系统中的电子邮件,并执行POP3协议中规定的服务项目。
项目要求:
POP3协议规定的服务项目较多,因此在实现时建议采用以下两个阶段来完成:
? 第一阶段:只要求通过dos窗口来实现POP3协议中规定的服务项目;
? 启动程序后录入POP3服务器地址、用户名、密码、建立与邮件服务器的连接。 ? 系统显示允许执行的POP3服务项目(获取邮件列表、删除邮件、获取邮件); ? 系统根据执行的服务,执行相应的服务;
? 如果选择获取邮件,将获取的邮件显示在dos窗口中;
? 第二阶段:要求能够通过Win32 API将程序升级为Windows桌面应用程序,进入第二
阶段必须满足以下条件:
? 必须熟悉Win32 API的基础知识;
? 能够创建Win32窗体并能够利用Win32进行子窗口的创建和管理;
POP3协议较SMTP协议更为复杂和实现更多的功能,因此对于POP3协议的理解是完成项目首先需要解决的问题,同时如何利用C语言的socket编程来实现相关协议也是开发过程中的一大考验;
主要技术点:
C语言基础、字符串处理、指针、socket编程、栈、SMTP协议、base64编码; 技术难点:
socket编程、POP3 协议理解、base64编码;
团队配置:
其它: 5人
无
2.3 安全文件传输- C语言
难度:难
需求描述:
运用C语言,结合数据结构的指针、链表、堆栈等知识,使用CS的模式,实现文件的传输
客户端的功能要求有传输文件、下载文件、设置属性等,三个功能的详细需求如下:
? 传输文件:向服务端传送本地文件;
? 下载文件:从服务端下载文件;
? 设置属性:设置服务端的相关信息,如地址、端口等;
项目要求:
1. 在第一阶段采用dos来完成以下功能;
2. 需要对录入数据进行有效性检查;
3. 在完成以上功能的基础上可以选择完成以下需求:
a) 将界面修改为Windows界面(可以考虑使用MFC或Win32)
b) 用C++写;
4. 在完成选择功能后,将提高小组的项目成绩;
主要技术:
C语言基础、指针、链表、排序、文件操作、队列、栈等;
技术难点:
socket编程、文件流操作、base64编码;
团队配置:
4人
其它说明:
无
2.4 网络聊天室- C++和MFC
难度:难
需求描述:
使用C/S模式,实现聊天室的功能
主要功能有:
? 服务器端:监听客户端的连接,发送并接收消息;
? 客户端:连接服务器端,发送并接收消息 ;
? 客户端设置属性:设置相关信息,如服务器IP地址、端口等; 项目要求:
1. 界面使用Windows界面(可以考虑使用MFC或Win32);
2. 连接有效性检查;
3. 能相互发送消息
主要技术:
C++语言基础;socket编程;指针;队列等
技术难点:
socket编程、MFC;
团队配置:
4人
其它说明:
3 游戏类
3.1 连连看
技术难度:
难
需求描述:
1) 12*12图形界面(12行,12列)
2) 使用QT作为开发框架
3) 软件上能够提供良好的用户界面,具有良好的运行效率,能快速的。
4) 发现自我的目的,有良好的扩充性,容易转入其他系统运行。
5) 系统能够提供友好的用户界面,使操作人员的工作量最大限度的减少;
6) 系统具有良好的运行效率,能够得到提高生产率的目的;
7) 系统应有良好的可扩充性,可以容易的加入其它系统的应用;
8) 平台的设计具有一定的超前性,灵活性,能够适应企业生产配置的变化;
9) 通过这个项目可以锻炼队伍,提高团队的开发能力和项目管理能力。
项目要求:
连连看游戏算法较为复杂,要实现的功能如下:
? 该题目涉及界面设计,根据实际情况可采用QT环境进行开发;
? 建议利用QT工具构造Windows环境下的桌面游戏界面;(老师在实训时会对该工具
进行介绍)
? 启动游戏后,初始程序界面,加载图库;
? 启动游戏后,根据算法随机初始放置图片位置;
? 游戏过程中,判断鼠标点击位置,传入后台代码;
? 游戏过程中,判断两次点击是否可以消除算法;
? 游戏过程中,判断是否消除图片已经结束;
? 游戏结束后,显示当前玩家的统计信息,可以选择重新开始;
主要技术点:
C++ 语言基础、QT开发库、二维数组、指针
技术难点:
游戏的算法问题、二维数组的灵活应用
团队配置:
其它: 4人
3.2 五子棋
技术难度:
难
需求描述:
国际比赛规则规定:对局中如黑方出现禁手,白方应立即指出禁手点,黑方即负。如白方在黑方出现禁手后,又落一步白子,黑棋禁手则不成立了。所以 在"有禁手"的房间里,如果黑方出现禁手,白方应立即按下"禁手"按钮。程序会判黑方负。如果这时白方又在棋盘上落一子,黑棋禁手则不成立了。为了简化用户对"禁手"按钮的使用,也有"走禁手就输"和"禁手不能落子"规则的房间,顾名思义不多介绍。虽然采取了禁手的限制,黑棋先行仍有优势,黑棋仍可以必胜。所以如果用户是高段位的棋手,或者想成为高手一定要选择国际上比赛选用的比赛标准,即“三手交换,五手两打”
项目要求:
俄罗斯方块游戏算法较为复杂,要实现的功能如下:
? 启动游戏后,初始界面,18*18的交叉网格线,用户使用白棋,计算机使用黑棋; ? 游戏过程中,根据白棋当前情况判断黑棋落子点;
? 游戏过程中,后台逻辑代码与界面分离;
? 游戏过程中,判断用户按键位置;
? 游戏过程中,按空格键暂停和恢复游戏;
? 游戏过程中,按Esc键退出游戏;
? 游戏结束后,显示当前玩家的统计信息,可以选择重新开始;
? 利用C语言的I/O实现游戏的保存和读取;
? 该题目涉及界面设计,根据实际情况可采用QT环境进行开发;
? 建议利用QT工具构造Windows环境下的桌面游戏界面;(老师在实训时会对该工具
进行介绍)
主要技术点:
C语言基础、二维数组、指针
技术难点:
游戏的算法问题、二维数组的灵活应用
团队配置:
其它:
无 4人
3.3 俄罗斯方块
技术难度:
难
需求描述:
俄罗斯方块是一个很多人都玩过的游戏,游戏开始后一个用于摆放小型正方形的平面虚拟场地,其标准大小:行宽为10,列高为20,以每个小正方形为单位;一组由4个小型正方形组成的规则图形,英文称为Tetromino,中文通称为方块,共有7种,分别以S、Z、L、J、I、O、T这7个字母的形状来命名;通过设计者预先设置的随机发生器不断地输出单个方块到场地顶部,以一定的规则进行移动、旋转、下落和摆放,锁定并填充到场地中。每次摆放如果将场地的一行或多行完全填满,则组成这些行的所有小正方形将被消除,并且以此来换取
一定的积分或者其他形式的奖励。而未被消除的方块会一直累积,并对后来的方块摆放造成各种影响;如果未被消除的方块堆放的高度超过场地所规定的最大高度(并不一定是20或者玩家所能见到的高度),则游戏结束。
项目要求:
俄罗斯方块游戏算法较为复杂,要实现的功能如下:
? 启动游戏后,左边显示游戏平面虚拟场地,右边显示下一方块和分数等统计信息; ? 游戏过程中,录入左、右控制下落方块的左右位置;
? 游戏过程中,录入向上键旋转下落方块;
? 游戏过程中,按下键则下落方块下落到底部;
? 游戏过程中,按空格键暂停和恢复游戏;
? 游戏过程中,按Esc键退出游戏;
? 在消除一定数量的方块后,游戏速度自动提高,增加游戏难度;
? 游戏结束后,显示当前玩家的统计信息,可以选择重新开始;
? 利用C语言的I/O实现游戏的保存和读取;
? 该题目涉及界面设计,根据实际情况可采用QT环境进行开发;
? 建议利用QT工具构造Windows环境下的桌面游戏界面;(老师在实训时会对该工具
进行介绍)
? 俄罗斯方块游戏的算法较为复杂,需要首先考虑好游戏中的算法问题,再利用C语言
实现其中的算法。
主要技术点:
C语言基础、二维数组、指针
技术难点:
游戏的算法问题、二维数组的灵活应用
团队配置:
其它:
无 4人
4 算法类
4.1 表达式计算器
难度:难
需求描述:
用户输入一个完整的四则运算表达式,程序能够求出表达式的值。要求能够处理括号、正负符号、加减乘除四则运算等。
基本要求:
1. 第一阶段要求用控制台应用程序实现该项目需求;
2. 项目基本要求:括号处理、正负符号处理、加减乘除四则运算以及浮点数在表达式中的处理。
主要技术点:
数组、栈、二叉树。
技术难点:
表达式合法性检查、栈的应用、优先级别的判定 4人 团队配置:
其他:无。
4.2 哈夫曼编码/译码器
难度:中
需求描述:哈夫曼编码在通讯、网络、数据压缩、图像处理中的得到广泛应用,在一个通讯系统中,采用图形界面设计哈夫曼树,对通讯信息进行编码和解码。
基本要求:
(1) 打开一篇英文文章,统计该文章中每个字符出现的次数,然后以它们作为权值,建立一棵哈
夫曼树,利用已经建好的哈夫曼树,对每个字符进行编码,结果存入文件CodeFile中,并将文件CodeFile显示在终端上。
(2) 利用编码规则,将文章进行变慢,写入文件CodePrint中。
(3) 利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中,并输
出结果。
项目要求:
1. 对控制台的输入需要一定的容错能力,给出一定的提示信息;
2. 对输出的结果进行一定的美化,做到内容清晰、易懂。
主要技术点:
哈夫曼编码、文件的输入、文件的输出。
团队配置:
3人。
4.3 关键路径问题
难度:难
问题描述:当一项工程划分为若干个子任务或活动后,人们不仅需要确定这些活动的先后次序,而且需要进一步计算完成整个工程的时间,确定哪些活动是影响工程进度的关键活动,以便合理地组织人力、物力、财力,加快这些活动的进度,为按时或提前完成整个工程提供保证,这就是关键路径问题。关键路径问题相应的网称为AOE网,其中:顶点表示事件,边表示活动,边上的权表示活动持续的时间。
基本要求:
(1)对一个描述工程的AOE网,建立其存储结构;(注:数据的输入可以是键盘输入或文件输入两种方式)
(2)判断该AOE网是否能够顺利进行。
(3)若该工程能顺利进行,输出完成整项工程至少需要多少时间,以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。(注:结果的输出可以是屏幕输出和文件输出两种方式)
项目要求:
1.对于控制台界面的输入需要增加容错能力,对于输入给出完整的提示信息,使得操作者能够轻松操作;
2.对输出的结果进行一定的美化,做到内容清晰、易懂;
主要技术点:
AOE网、关键活动的最早发生时间、最迟发生时间。 3人。 团队配置:
4.4 八数码难题
难度:难
需求描述:
在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动,其移动规则是:与空格相邻的数码方格可以移入空格。现在的问题是:对于指定的初始棋局和目标棋局,给出数码的移动序列。该问题称八数码难题或者重排九宫问题。
基本要求:
1. 从文件读取八数码的初始状态和终止状态。如:
2
1
8 6 (a) 3 4 1 7 2 6 (b) 3 5 8 ■ 4 7 ■ 5
2. 确定搜索策略,对八数码难题的所有状态空间图进行搜索,找出最短移动方案。
3. 界面要求:有合理的提示和人机交互。
主要技术点:
图的存储、状态空间搜索算法 状态空间构造与搜索(回溯法、分支限界法、A*算法) 3人。 技术难点及关键算法: 团队配置: