吉林大学软件学院2011年数据结构实验题C++实现

第一个实验：问题1 单链表相关算法的实验验证。 【实验目的】验证单链表及其基本操作。 【实验内容及要求】 1、定义单链表类。 2、实验验证以下算法的正确性、各项功能及指标： 1）创建单链表； 2）插入操作：在当前节点之后、表头、表尾插入值为x的节点； 3）删除操作：分别删除当前节点的头节点、尾节点和后继节点； 4）访问操作：分别访问当前节点的值和单链表中第k个节点的值； 5）查找操作：查找值为x的元素在单链表中的位置（下标）。 问题2分别提供了栈和队列相关算法的实验验证。 【实验目的】验证栈、队列以及对它们的基本操作。 【实验内容及要求】（以队列为例） 1、定义队列类。 2、实验验证以下算法的正确性、各项功能及指标： 1）创建队列； 2）插入操作：将值为x的元素插入到队列末尾； 3）删除操作：删除队列的第一个元素； 4）访问操作：读取队列的第一个元素。 第二个实验问题1是二叉树相关算法的实验验证。 【实验目的】验证二叉树的链接存储结构及其基本操作。 【实验内容及要求】 1、定义链接存储的二叉树类。 2、实验验证以下算法的正确性、各项功能及指标： 1）创建二叉树并初始化； 2）以首根、中根、末根遍历二叉树（递归算法）； 3）在二叉树中查找给定节点的父节点； 4）在二叉树中搜索满足数据域条件的节点； 5) 从二叉树中删除给定的节点及其左右子树。

问题2：树和森林遍历算法的实验验证。 【实验目的】验证树和森林的遍历算法。 【实验内容及要求】 1、定义左子右兄弟链接中存储的树类和森林类。 2. 实验验证以下算法的正确性、各项功能及指标： 1）树木和森林的创建； 2）树和森林的根遍历的递归和迭代算法； 3）树和森林的根遍历的递归和迭代算法； 4）树和森林级别的遍历算法。 问题3：二叉搜索树的验证实验。 【实验目的】验证二叉搜索树及其相关操作。 【实验内容及要求】 1、定义二叉搜索树的类。 2、实验验证以下算法的正确性、各项功能及指标： 1）实现二叉搜索树结构； 2）实现二叉搜索树的查找、插入和删除算法； 第三实验题1 邻接表存储图相关算法的实验验证。 【实验目的】验证邻接表中存储的图及其基本操作。 【实验内容及要求】 1、定义邻接表中存储的图类。 2. 实验验证以下算法的正确性、各种功能和指标： 1）创建存储在邻接表中的图； 2）返回图中指定边的权重； 3）返回图中一个顶点的第一个相邻顶点；4）返回图中一个顶点的下一个相邻顶点到另一个顶点的序号； 5）插入操作：向图中插入一个顶点，插入一条边； 6）删除操作：删除图中的一个顶点，删除一条边。 问题2：图遍历算法的实验验证。 【实验目的】验证图遍历算法。 【实验内容及要求】 1、定义邻接表中存储的图。 2. 实验验证以下算法的正确性、各种功能和指标： 1）创建图； 2）图的深度优先遍历的递归算法； 3）图深度优先遍历的迭代算法； 4）图的广度优先遍历遍历算法。第四个实验请阅读插入排序、堆排序和快速排序的文档。