《数据结构》实验讲义
课程简介
实验（选做, 设计性实验，2学时，来自第四章）
实验题目：字符串基本操作的实现
1、假设串以堆分配存储结构表示，设计一个算法，完成串的替换操作Replace(&S,T,V)。
2、实现串匹配的KMP算法及它的改进算法。
3、假设串以堆分配存储结构表示，设计一个算法，求串S和串T的一个最长公共字串，并分析你的算法时间复杂度。
实验目的：
1、 掌握串的三种存储结构。
2、 熟练掌握串的基本操作。
3、 熟悉串的应用。
实验要求：
1、 定义串的堆分配存储结构
2、 熟练从键盘或文件中读入源字符串。
3、 实现对字符串的替换、查找、匹配等运算。
4、 比较并分析你的算法的时间复杂度。
实验内容和实验步骤：（由学生填写）
实验用测试数据和相关结果分析：（由学生填写）
实验总结：（由学生填写）
实验四（必做, 设计性实验，2学时，来自第五章）
实验题目：三元组表表示的稀疏矩阵的加法运算的实现
1、设稀疏矩阵以三元组顺序表为压缩存储结构，写出矩阵转置的算法。转置后的矩阵以三元组顺序表表示。
2、设稀疏矩阵以三元组顺序表为压缩存储结构，写出矩阵相加的算法，用三元组表C存放和矩阵。
实验目的：
1、 了解压缩的基本原理。
2、 了解稀疏矩阵的三元组表的压缩存储方法。
3、 熟悉三元组表表示的稀疏矩阵运算的实现。
实验要求：
1、 定义稀疏矩阵压缩存储的存储结构-三元组顺序表
2、 将稀疏矩阵压缩到三元组顺序表中。
3、 实现矩阵转置的经典算法和三元组顺序表表示的稀疏矩阵的转置运算，其中三元组顺序表表示的稀疏矩阵的转置算法需用普通和快速转置算法来实现。
4、 实现矩阵相加的经典算法和三元组顺序表表示的稀疏矩阵的加法运算。
5、 比较并分析你的算法的时间复杂度。
实验内容和实验步骤：（由学生填写）
实验用测试数据和相关结果分析：（由学生填写）
实验总结：（由学生填写）
实验五(必做，设计性实验，2学时，来自第六章)
实验题目：二叉树的递归及非递归的遍历及其应用
1、二叉树的前、中、后序遍历算法和非递归算法的实现
2、求二叉树中叶子结点数目的递归算法。
3、编写求二叉树深度的递归算法。
实验目的：
1、 熟练掌握二叉树的二叉链表存储结构的C语言实现。
2、 掌握二叉树的基本操作-前序、中序、后序遍历二叉树的三种方法。
3、 了解非递归遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。
实验要求：
1、创建二叉树的二叉链表结构、遍历先、中、后序的递归函数显示不同遍历序列，结合习题了解二叉树遍历的应用实例。
2、遍写前、中、后、层序遍历的非遍历函数，注意用以前作过的栈和队列作辅助存储结构。
3、思考遍历二叉树还有哪些应用？
实验内容和实验步骤：（由学生填写）
实验用测试数据和相关结果分析：（由学生填写）
实验总结：（由学生填写）
实验六（必做，验证性实验，2学时，来自第六章）
实验题目：Huffman树及Huffman编码的算法实现
实验目的：
1、 了解该树的应用实例，熟悉掌握Huffman树的构造方法及Huffman编码的应用，
2、 了解Huffman树在通信、编码领域的应用过程。
实验要求：
1、输入一段100—200字的英文短文，存入一文件a中。
2、写函数统计短文出现的字母个数n及每个字母的出现次数
3、写函数以字母出现次数作权值，建Haffman树（n个叶子），给出每个字母的Haffman编码。
4、用每个字母编码对原短文进行编码，码文存入文件b中。
5、用Haffman树对b中码文进行译码，结果存入文件c中，比较a,c是否一致，以检验编码、译码的正确性。
实验内容和实验步骤：（由学生填写）
实验用测试数据和相关结果分析：（由学生填写）
实验总结：（由学生填写）
实验（必做，验证性实验，2学时，来自第七章）
实验题目：图的深度优先遍历
实验目的：
1、 熟悉图的数组表示法和邻接表存储结构，
2、 掌握构造有向图、无向图的算法 ，
3、 在掌握以上知识的基础上，熟悉图的深度优先遍历算法，并实现。
实验要求：
1、图的数组表示法定义及基本操作的实现。
2、图的邻接表表示法定义及基本操作的实现。
3、写函数实现图的深度优先遍历（分别在两种结构上）
4、在邻接表上实现关键路径的求法，在邻接矩阵上实现最短路经、最小生成树的求法。
实验内容和实验步骤：（由学生填写）
实验用测试数据和相关结果分析：（由学生填写）
实验总结：（由学生填写）
实验七（必做，验证性实验，2学时，来自第九章）
实验题目：查找
实验目的：
1、 熟练掌握顺序表和有序表的查找方法，
2、 以一、两个算法为例，掌握其时间复杂度的分析方法。
实验要求：
1、验证并设计顺序表的查找（顺序查找、折半查找）算法
2、验证二叉排序树上的查找（创建、查找、插入）算法
3、验证Hash表查找（Hash函数定义、建立，查找，插入）算法（选做）
实验内容和实验步骤：（由学生填写）
实验用测试数据和相关结果分析：（由学生填写）
实验总结：（由学生填写）
实验八（必做，验证+设计，4学时，来自第十章）
实验题目：排序
实验目的：
1、 了解排序的方法、过程及原则。
2、 掌握插入排序、快速排序、选择排序、归并排序的算法思想
3、 以一、两个算法为例，实现以上各类算法，掌握其时间复杂度的分析方法。
实验要求：
1、定义待排序序列的存储结构。
2、验证插入排序、快速排序、选择排序、归并排序中各排序方法中的一、二个排序算法。
实验内容和实验步骤：（由学生填写）
实验用测试数据和相关结果分析：（由学生填写）
实验总结：（由学生填写）
附录：实验报告的要求
实验报告是反映学生实验效果的最主要的依据，也是学生正确地表达问题、综合问题和发现问题的能力的基本培养手段，因而是非常重要的内容，本课程的实验报告中要包括以下几项内容：
（一） 实验题目；参见实验讲义
（二） 实验目的；参见实验讲义
（三） 实验要求；参见实验讲义
（四） 实验内容和实验步骤；
1．需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：
（1）输入的形式和输入值的范围；
（2）输出的形式；
（3）程序所能实现的功能；
2．概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。
3．详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。
4．调试分析：
（1）调试过程中所遇到的问题及解决方法；
（2）算法的时空复杂度分析；
（五） 实验结果：列出对于给定的输入所产生的输出结果，并阐述原因。若可能，测试随输入规模的增长所用算法的实际运行时间的变化。
（六） 实验总结：有关实验过程中的感悟和体会、经验和教训等。总结调试过程中遇到的主要问题及解决办法；对设计和编码进行回顾、讨论和分析以及对主要算法的改进设想。
第二篇：C语言_数据结构_实验2
实验二：线性表子系统
1．实验目的：
（1）掌握线性表的特点
（2）掌握线性表顺序存储结构和链式存储结构的基本运算。
（3）掌握线性表的创建、插入、删除和显示线性表中元素等基本操作。
2．实验内容：
（1）用结构体描述一个字符形的单链表。
（2）创建线性表；在线性表中插入元素、删除元素；显示线性表中所有元素等基本操作。
（3）用if 语句设计一个选择式菜单。
3．参考程序
