数据结构考查作品的设计指教.docVIP

数据结构考查作品设计指导 邹才凤 计算机软件技术教研室 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 在本课程考查作品设计过程中要求学生： （1）培养严谨、科学和踏实的工作态度； （2）按照规定范围内的题目要求，独立地完成各项任务，严禁抄袭；允许通过互联网有哪些信誉好的足球投注网站引擎查找资料； （3）认真编写课程作品实验报告。 三、设计步骤 问题分析和任务定义； 数据类型和系统设计； 编码实现和静态检查； 上机调试； 5、总结和整理实验报告。 四、考核方式和成绩评定 作品成绩采用五级分制。考核分为两个部分： 程序运行情况：按规定时间运行和演示程序，由老师检查运行情况。学生能对自己的程序面对教师提问并能熟练地解释清楚。 实验报告：是否按规定书写实验报告的各??内容。 五、上交相关内容要求 上交的成果的内容必须由以下几个部分组成，缺一不可 （一）上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中，以学号姓名作为文件夹名）； （二）上交程序的说明文件：（保存在.doc中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明； （三）作品实验报告：（保存在word 文档中，文件名要求按照姓名-学号-作品实验报告起名）按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成： 1、需求分析 程序的功能； 输入输出的要求； 测试数据。 2、概要设计 　包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。 3、详细设计 包括模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等），每个模块的算法设计说明（可以是描述算法的流程图）。 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 4、调试分析 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 5、核心源程序清单和执行结果 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 六、作品答辩注意事项 答辩以数据结构的设计和算法的实现过程为主，重点围绕以下问题： 1．选择了哪些数据结构来解决问题？为什么选择这些数据结构？其优点是什么？并针对具体实例，画出具体存储结构。 2．算法的主要思想是什么？要求演示具体流程。比如，实现了快速排序方法，则要求对某一组数据，将每趟排序过程详细地手工演示出来。实现了迪杰斯特拉(Dijkstra)算法，则要求举例，将求最短路径的步骤详细地手工演示出来。 附录1 数据结构作品设计的具体内容 作品范围可以参考下面的某一个题目，或者在文档《 HYPERLINK 数据结构实验指导书.doc 数据结构实验指导书》的实验里面选做一题，或者自己选题（必须与数据结构的知识点相关，选用合理的数据结构来实现）。 通讯录只是作为教学用例，最好不要用通讯录来交作品。如果以通讯录为作品，必须按照32、通信录管理系统的要求来做。功能要求如下： （1） 查看功能：选择此功能时，列出下列三类选择。 A 工作类 B 家庭类 C 朋友类 ，当选中某类时，显示出此类所有数据中的姓名和电话号码） （2） 增加功能：能录入新数据（一个结点包括：姓名、电话号码、分类（可选项有：A 工作类 B 家庭类 C 朋友类）、家庭住址）。例如 杨春 商务类 南开区 当录入了重复的姓名和电话号码时，则提示数据录入重复并取消录入；当通信录中超过10条信息时，存储空间已满，不能再录入新数据；录入的新数据能按递增的顺序自动进行条目编号。 （3）修改功能：选中某个人的姓名时，可对此人的相应数据进行修改 （4） 删除功能：选中某个人的姓名时，可对此人的相应数据进行删除，并自动调整后续条目的编号。 作品范围参考如下： 1、一元多项式乘法 1) 问题描述 已知A(x)=a0+a1x+a2x2+……+anxn和B(x)=b0+b1x+b2x2+……+bmxm，并且在A(x)和B(x)中指数相差很多，求A(x)=A(x)*B(x)。 2) 基本要求 (1)设计存储结构表示一元多项式； (2)设计算法实现一元多项式乘法； (3)分析算法的时间复杂度和空间复杂度。 2、 迷宫问题 1)问题描述 迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图2所示为一个迷宫示意图，其