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