算法和数据结构-上机试验大纲

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