实验范围为第2章，任务是验证教材中的线性表类及其基本操作，设计实现指定操作的算法，并做算法分析。“实验目的和要求”已由教材实验2给出。要求使用Java语言，采用泛型类，算法效率为一次遍历。

实验题目及分配如下（按班级名单序号依次选取）。

以下各题对带头结点的单链表进行操作，方法声明见实验2。

（1） 判断单链表是否包含另一条单链表的所有结点，即判断无序的子集。

（2） 返回从单链表指定位置开始、长度为n的子表，深拷贝。

（3） 以深拷贝方式在单链表的指定位置插入另一条单链表，集合并运算。

（4） 以深拷贝方式在单链表最后添加另一条单链表的所有结点。

（5） 删除单链表从指定位置开始、长度为n的子表。

（6） 返回由两条单链表中元素值相同的所有结点组成的单链表对象，集合交运算。

（7） 删除当前单链表中那些也包含在list链表中的所有结点，集合差运算。

（8） 判断单链表是否包含与另一条单链表匹配的子表，BF模式匹配算法。

（9） 将单链表中所有与sourcelist匹配的子表替换为destlist子表，包含BF模式匹配算法。

以下各题对带头结点的循环单链表进行操作：

（10） 比较两条循环单链表是否相等。

（11） 判断循环单链表是否包含另一条循环单链表的所有结点。

（12） 返回从循环单链表指定位置开始、长度为n的子表，深拷贝。

（13） 实现循环单链表深拷贝功能。

（14） 由单链表构造循环单链表，深拷贝。

（15） 以深拷贝方式在循环单链表的指定位置插入另一条循环单链表，集合并运算。

（16） 以深拷贝方式在循环单链表最后添加另一条循环单链表的所有结点。

（17） 删除循环单链表从指定位置开始、长度为n的子表。

（18） 返回由两条循环单链表中元素值相同的所有结点组成的循环单链表对象，集合交运算。

（19） 删除循环单链表中那些也包含在指定另一条循环单链表中的所有结点，集合差运算。

（20） 判断循环单链表是否包含与另一条循环单链表匹配的子表。

（21） 将循环单链表中所有与sourcelist匹配的子表替换为destlist子表。

以下各题对带头结点的双链表进行操作：

（22） 比较两条双链表是否相等，并实现递归算法。

（23） 判断双链表是否包含另一条双链表的所有结点。

（24） 返回从双链表指定位置开始、长度为n的子表，深拷贝。

（25） 实现双链表深拷贝功能。

（26） 由单链表构造双链表，深拷贝。

（27） 以深拷贝方式在双链表的指定位置插入另一条双链表，集合并运算。

（28） 以深拷贝方式在双链表最后添加另一条双链表的所有结点。

（29） 删除双链表从指定位置开始、长度为n的子表。

（30） 返回由两条双链表中元素值相同的所有结点组成的双链表对象，集合交运算。

（31） 删除双链表中那些也包含在指定另一条双链表中的所有结点，集合差运算。

（32） 判断双链表是否包含与另一条双链表匹配的子表。

（33） 将双链表中所有与sourcelist匹配的子表替换为destlist子表。

以下各题对带头结点的循环双链表进行操作：

（34） 比较两条循环双链表是否相等。

（35） 判断循环双链表是否包含另一条循环双链表的所有结点。

（36） 返回从循环双链表指定位置开始、长度为n的子表，深拷贝。

（37） 实现循环双链表深拷贝功能。

（38） 由单链表构造循环双链表，深拷贝。

（39） 由循环单链表构造循环双链表，深拷贝。

（40） 由双链表构造循环双链表，深拷贝，构造函数声明如下：

（41） 以深拷贝方式在循环双链表的指定位置插入另一条循环双链表，集合并运算。

（42） 返回由两条循环双链表中元素值相同的所有结点组成的循环双链表对象，集合交运算。

（43） 以深拷贝方式在循环双链表最后添加另一条循环双链表的所有结点，集合差运算。

（44） 删除循环双链表从指定位置开始、长度为n的子表。

（45） 删除循环双链表中那些也包含在指定另一条循环双链表中的所有结点。

（46） 判断循环双链表是否包含与另一条循环双链表匹配的子表。

（47） 将循环双链表中所有与sourcelist匹配的子表替换为destlist子表。

选做的难题：

（48） 删除单链表中所有与另一条单链表匹配的子表，BF模式匹配算法查找到再删除。

（49） 删除循环单链表中所有与另一条循环单链表匹配的子表。

（50） 删除双链表中所有与另一条双链表匹配的子表。

（51） 删除循环双链表中所有与另一条循环双链表匹配的子表。

实验二  树和二叉树的基本操作

实验范围为第6章，验证教材中树结构的基本操作，设计实现指定操作的算法，并做算法分析。“实验目的和要求”已由教材实验6给出。要求使用Java语言，采用泛型类，算法效率为一次遍历。

实验题目及分配如下（按班级名单序号反向次序依次选取）。

以下各题二叉树的存储结构是二叉链表表示，方法声明见实验6。

（52） 求一棵BinaryTree二叉树中各结点数值的平均值。

（53） 将每个结点的左子树与右子树交换。

（54） 验证二叉树的性质3：。

（55） 由中根和后根次序遍历序列构造二叉树。

（56） 二叉树深拷贝，复制一棵二叉树。

（57） 判断两棵二叉树是否相等。

（58） 判断一棵二叉树是否为完全二叉树。

（59） 求一棵二叉树在后根次序遍历下第一个访问的结点。

（60） 实现二叉树后根次序遍历的非递归算法。

（61） 求结点所在的层次。

（62） 二叉树增加层次属性，求结点所在的层次。

（63） 二叉树增加平衡因子（见第8章）属性，求各结点的平衡因子。

（） 判断一棵二叉树bitree是否是当前二叉树的子树。

以下各题二叉树的存储结构是三叉链表表示。

（65） 求一棵BinaryTree二叉树中各结点数值的平均值。

（66） 将每个结点的左子树与右子树交换。

（67） 验证二叉树的性质3：。

（68） 由中根和后根次序遍历序列构造二叉树。

（69） 二叉树深拷贝，复制一棵二叉树。

（70） 判断两棵二叉树是否相等。

（71） 判断一棵二叉树是否为完全二叉树。

（72） 求一棵二叉树在后根次序遍历下第一个访问的结点。

（73） 实现二叉树后根次序遍历的非递归算法。

（74） 求结点所在的层次。

（75） 二叉树增加层次属性，求结点所在的层次。

（76） 二叉树增加平衡因子（见第8章）属性，求各结点的平衡因子。

（77） 判断一棵二叉树bitree是否是当前二叉树的子树。

在一棵中序线索二叉树中，实现以下操作。

（78） 调用求结点的前驱结点算法，按中根次序遍历一棵中序线索二叉树。

（79） 按后根次序遍历中序线索二叉树。

（80） 删除指定结点的右孩子结点，删除2度结点，用其右孩子顶替。

（81） 删除指定结点的左孩子结点，分别用删除结点的左或右孩子顶替。

在采用孩子兄弟链表存储的树类Tree中，增加以下操作。

（82） 返回p结点的第i（i≥0）个孩子结点。

（83） 返回node的父母结点。

（84） 返回p结点的孩子结点个数。

（85） 返回树的高度height()。

（86） 按层次遍历树levelOrder()。

（87） 插入x元素作为p结点的第i个孩子。

（88） 删除以p的第i个孩子为根的子树。

（） 深拷贝。

（90） 复制sub子树并插入作为p的第i个子树。

（91） 比较两棵树是否相等。

（92） 返回元素为x的结点所在的层次。

（93） 先根次序遍历树的非递归算法。

（94） 树增加层次属性，求结点所在的层次。

（95） 判断一棵树tree是否是当前树的子树。

声明父母孩子链表存储的树类，使用顺序表作为成员变量存储数目不定的孩子结点，实现树的操作。

（96） 返回树的高度height()。

（97） 按层次遍历树。

（98） 插入x元素作为p结点的第i个孩子。

（99） 删除以p的第i个孩子为根的子树。

（100） 深拷贝。

（101） 复制sub子树并插入作为p的第i个子树。

（102） 比较两棵树是否相等。

（103） 返回元素为x的结点所在的层次。

（104） 先根次序遍历树的非递归算法。

（105） 树增加层次属性，求结点所在的层次。

（106） 判断一棵树tree是否是当前树的子树。下载本文