搜索
《算法与数据结构》实验(上机)大纲课程名称：算法与数据结构上机学时：16学时适用专业：软件工程一、实验（上机）课程的性质、目的与任务：《算法与数据结构》是软件工程专业的一门专业必修课，是理论与实践并重的课程。实验是该课程实践教学环节的重要环节，它的内容覆盖了算法与数据结构的各个主要部分。通过实验可以加深对数据结构基本概念、基本理论的理解，使学生巩固和运用所学知识以解决实际的具体问题，同时提高程序设计和实际操作的能力，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。原则上要求学生针对实际问题进行数据结构设计、算法设计、编程调试、算法测试和优化，获得运行结果，并作为课程考核内容的一部分，也为后续课程的学习打下良好的基础。二、实验（上机）报告内容⒈问题描述：包括需求分析、实现目标、任务、条件和约束的描述。充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。⒉设计：包括概要设计和详细设计在概要设计中，第一步先进行数据结构设计：针对要求解决的问题，考虑各种可能的数据结构，还可以根据算法的时间复杂度和空间复杂度一起考虑，以确定最合适的数据结构，主要描述逻辑结构。第二步进行关键算法设计：对每个算法的功能及初始条件和操作结果认真分析确定，并针对模块化开发的特点，自顶向下分解成若干顺序模块，确定模块间的相互关系以及模块之间的信息交换问题。第三步设计主控模块及功能模块层次间的结构；在详细设计中，第一步对数据结构的存储结构进行描述，对数据结构的逻辑结构和物理结构进行定义，掌握其特点和映射关系。第二步对每个算法进行实现，包括输入、处理和输出的描述。程序代码尽可能的多加注释，用C语言实现。3．测试：准备典型测试数据和测试方案，对测试结果进行分析与讨论，对测试过程中遇到的主要问题及所采用的解决措施进行总结，以优化算法。⒋使用说明和作业小结（如果有）：⑴使用说明主要描述如何使用你的程序以及使用时的主要事项；⑵在小结中说明实验过程中碰到的问题，算法的改进思想、经验和体会。⒌提交一份程序清单及运行示例的结果（电子版）。三．实验（上机）内容、要求及学时分配：1、线性表的存储结构定义及基本操作（2学时）2、线性表的综合应用（2学时）3、栈和队列的综合应用（2学时）4、二叉树的定义及基本操作（2学时）5、图及其应用（2学时）6、最短路径和关键路径的研究与实现（2学时）7、查找和排序算法的实现（2学时）8、赫夫曼编码及其应用（2学时）四．实验（上机）的具体要求和指导：实验一：线性表的存储结构定义及基本操作（基本2学时，扩展4学时）实验目的：掌握线性表的逻辑特征掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算熟练掌握线性表的链式存储结构定义及基本操作理解循环链表和双链表的特点和基本运算加深对栈结构的理解，培养解决实际问题的编程能力。加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力实验内容：（1）基本实验内容：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁,置空表、求表长、查找元素、判线性表是否为空；建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。（2）扩展实验内容：查前驱元素、查后继元素、顺序表合并，两个有序单链表的合并操作等。实验二：线性表的综合应用（2学时）实验目的：掌握顺序表和链表的概念，学会对问题进行分析，选择恰当的逻辑结构和物理结构加深对顺序表和链表的理解，培养解决实际问题的编程能力实验内容:实现一元稀疏多项式的表示及基本操作（建立、销毁、输出、加法、减法、乘法等操作）；实验三：栈和队列的综合应用（2学时）实验目的：熟悉栈的定义和栈的基本操作熟悉队列的定义和栈的基本操作掌握递归和非递归算法的实现技术和实际应用加深对栈结构的理解，培养解决实际问题的编程能力。实验内容:实现Hanoi塔的问题；完成迷宫问题或马踏棋盘问题求解。实验四：二叉树的定义及基本操作（基本2学时，扩展4学时）实验目的：熟练掌握二叉树的二叉链表存储结构掌握二叉树的非线性和递归性特点熟练掌握二叉树的递归遍历操作的实现方法，掌握二叉树的非递归遍历操作的实现掌握线索二叉树的定义和基本操作加深对二叉树结构和性质的理解．逐步培养解决实际问题的编程能力实验内容:（1）基本实验内容：定义二叉树的链式存储结构；实现二叉树的基本操作：建空树、销毁二叉树、生成二叉树(先序,中序或后序)、判二叉树是否为空、求二叉树的深度、求二叉树的根等基本算法；实现二叉树的递归(先序、中序或后序)遍历算法；（2）扩展实验内容：求某一个结点的双亲结点,求某一个结点的左孩子（或右孩子）结点；求某一个孩子的左兄弟（或右兄弟）算法；利用栈，实现二叉树的非递归(先序、中序或后序)遍历算法；利用队列，实现层序递归遍历二叉树；定义线索二叉树的链式存储结构，建立线索二叉树，实现线索二叉树的插入和删除操作；实验五：图及其应用（2学时）实验目的：熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法掌握图的基本运算及应用加深对图的理解，逐步培养解决实际问题的编程能力实验内容:采用邻接表或邻接矩阵方式存储图，实现图的深度遍历和广度遍历；用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径。实验六：最短路径和关键路径的研究与实现（2学时）实验目的：掌握图的邻接矩阵、邻接表的表示方法掌握迪杰斯特拉和弗洛伊德的最短路径算法理解拓扑排序，掌握关键路径的算法加深对图的理解，逐步培养解决实际问题的编程能力实验内容：最短路径和关键路径的实现实验七：查找和排序算法的实现（基本2学时，扩展4学时）实验目的：掌握有序表、无序表查找的基本思想及存储、运算的实现熟练掌握常用排序算法的基本思想及实现深刻理解各种算法的特点，并加以灵活应用加深对查找和排序的理解，逐步培养解决实际问题的编程能力实验内容:（1）基本实验内容：建立一个无序表并实现其上的顺序查找；建立一个有序表并实现其上的折半查找；实现插入排序、起泡排序、快速排序和希尔排序的基本算法；（2）扩展实验内容：建立二叉排序树并在其上查找指定关键字。实验八：赫夫曼编码及其应用（基本2学时，扩展2学时）实验目的：掌握赫夫曼树的概念、存储结构掌握建立赫夫曼树和赫夫曼编码的方法及带权路径长度的计算熟练掌握二叉树的应用实验内容:（1）基本实验内容：实现赫夫曼树的生成，完成赫夫曼编码的输出；（2）扩展实验内容：完成一组码字的赫夫曼编码及解码(以一个文本文件的内容为例).四、大纲说明在实验中，一定要以C或C++代码的形式实现各算法，并通过实验得以调试、运行通过，得到预期的结果。实验（上机）大纲的有些实验包含基本实验和扩展实验，其基本实验是要求学生在课程的实验学时内必须保证完成并掌握的，而扩展实验内容可以满足部分同学进行系统化、综合性学习的要求。五、考核以学生的实验报告情况和做实验时的表现为考核依据。六、教学参考书1.数据结构与算法分析——C语言描述（原书第2版）,机械工业出版社,20072.严蔚敏吴伟民著,数据结构(C语言版),清华大学出版社,2007