(算法与数据结构课程设计指导秋信息.docVIP

信息科学与技术学院 数 据 结 构（分册） 盐城师范学院信息科学与技术学院算法与数据结构课程组编 2011.9 《数据结构》课程设计 一、概 述 （一）课程设计的性质、目的与作用 数据结构是计算机及其相关专业一门重要的核心课程，是学习计算机软件设计的重要基础课程。从实际工作需要来看，仅靠教学计划安排的课内实践时间是难以满足要求的，为了帮助同学扎实的掌握数据结构内容，提高运用数据结构的方法解决实际问题的能力，有计划、有目的、有系统地进行必要的实践训练，编写了《数据结构》课程设计这部分内容。 课内的实验是侧重于对某一方面知识的学习，在解决实际问题时，可能涉及并运用多个方面的知识，具有较强的综合性，这就需要进行一些综合性的设计练习，来提高分析和解决实际应用问题的能力。 数据结构课程设计的目的是利用本课程内的以及到目前为止所学到的有关知识和技术解决一些不算太复杂却具有综合性的问题。通过课程设计，在建立问题模型、构造求解算法、设计数据结构、编写程序代码及上机调试等方面得到全面的锻炼，从而能更深刻地理解《数据结构》的精髓，为后续软件课程的学习及软件设计能力的提高奠定良好的基础。包括， 熟练掌握数据结构的一些常用算法和经典算法； 熟练的运用常用的算法和经典算法解决具有一定规模和复杂程度的实际问题； 熟练掌握分析问题和解决问题的方法，合理选择数据结构，学会分析算法的优劣，分析算法的复杂度。 （二）课程设计的要求 在课程设计时，对要解决的问题，要注意以下几个方面： 正确性：设计的算法要严谨、正确，能正确解决实际问题，符合指定的要求； 高效：有效的建立数学模型，合理的选择数据结构，编写高效的程序代码； 清晰：算法和程序的结构要清晰，算法要用流程图来表示，程序代码要加注解； 设计报告：每一个问题解决后，要按统一的纸张及格式，完整、整洁地写出设计报告，打印程序清单，拷贝所做设计的电子版文档和程序。 （三）设计报告格式 在将综合设计作为教学的一个环节时，设计报告一般包括以下几个方面的内容： 设计任务、要求和所用的软件环境和技术； 设计思想及其简要说明； 设计的算法，以及算法可能由几个模块组成，算法用流程图表示出来； 使用说明，包括使用前提，所用软件环境，文件清单； 验收时间，验收情况说明等； 通过课程设计的收获以及对所用方法的分析和综合； 打印的程序清单以及结果，结果以贴图的方式附在报告后。 二、预备知识 线性表的顺序和链式表示和实现 栈和队列的表示和实现以及应用 递归和非递归的转化 串的表示和实现 数组的应用 树及其二叉树的表示、实现、遍历和应用 图的表示方法及其遍历和应用 各种查找方法的实现和分析及应用 各种排序方法的实现和分析和应用 三、《数据结构》课程设计课题 说明： 1、不限定开发语言，Java、Jsp、Asp、C、C#、C++等都行。重在答辩。 2、相同情况下，选择提高题、综合题与运用题的学生，我们给予10分鼓励分，优先给这三类学生评优。 3、要突出数据结构与算法设计思路步骤，代码中的文档注释量不能低于代码量。重在业务分析、模块接口设计、数据结构设计与操作算法步骤设计。重在对分析问题、解决问题能力的培养与评定。 4、课程设计报告请严格规定安格式书写电子稿，并打印，没有依格式写的课程设计报告检查后要重新打印，并扣态度分，打印前请认真检查。 可供选择的数据结构课程设计题： 基础题：以下选题为每题限选2人。 【课题1】用贪婪法求解“货郎担问题”。所谓“货郎担问题”是指，给定一个无向图，并已知各边的权，在这样的图中，找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和为最小。 【课题 2】背包问题。从N件不同价值、不同重量的物品中选取一部分物品，在不超过规定重量的情况下，使这部分物品的总价值最大。 【课题 3】用十字链表表示稀疏矩阵，并实现稀疏矩阵加法。 【课题 4】马的遍历问题。设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个“马”．均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。程序输出8×8方阵，用1－64表示走过每个位置的次序，起始点标为1。 【课题 5】编写程序，初始从键盘输入二叉树的结点数据创建二叉树，并将该二叉树的数据以某种方式存储到文件btree.dat中，以便程序此后运行时从文件中读取数据构建该二叉树；要求能根据指定结点求出其在二叉树中所在的层数。 【课题 6】若某算术表达式采用后置法表示（即逆波兰表达式），请编程计算该表达式的值。如：表达式(a+b*c)/d-e用后置法表示为abc*