《数据结构》课程实验报告.doc

《《数据结构》课程实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.4实验一基于二叉链表的二叉树的实现4.1问题描述基于二叉链表和队列及其堆栈存储结构，实现二叉链表的二叉树的对数据进行各种必要的操作。4.2系统设计1.2.1提供20个功能，分别是：1.2.2二叉链表的结构试一堆栈和队列的形式进行储存的分别是：1.2.3在程序中所定义的数据结构有：..2.3系统实现1.3.1InitTree功能初始二叉链表，传入的是头结点地址。申请一个存储空间，并用头结点中的首结点指针指向该空间首地址，相应的时间复杂度为1。具体实现如下：..1.3.2DestroyTree功能销毁头结点中首结点址针指向

2、的线性存储空间，传入的是头结点地址。具体实现如下：..1.3.3CreateBiTree功能与DestroyBiTree类似但是又有不同，ClearBiTree并不销毁物理空间，而是修改逻辑关系值：..1.3.4ClearBiTree功能与DestroyBiTree类似但是又有不同，ClearBiTree并不销毁物理空间，而是修改逻辑关系值..1.3.5BiTreeEmpty功能判空功能，判断表是否为空表。时间复杂度为1，因为只需判断一次就可以知道是否为空。实现如下：1.3.6BiTreeDepth功能求二叉链表深度的功

3、能，由于创建过程中已经把表长信息包含在头结点中，所以直接调用并显示即可..1.3.7Root(BiTreeT)功能获取二叉链表的根节点的元素，通过遍历二叉链表中的元素，来逐个判断，时间复杂度为（n）。1.3.8Value(BiTreeT,TElemTypee)功能求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是递归算法。时间复杂度为O(n)。具体实现如下：..1.3.9Assign功能求指定元素的后一个元素的内容，传入头结点值、包含指定元素信息的一个临

4、时表结点值、存储前一个元素的表结点地址。找到后，把新的数据值赋给所找到的节点。时间复杂度为O(n)。具体实现如下：..1.3.10Parent功能找双亲节点，找到后输出1.3.11LeftChild功能..查找左孩子，利用递归的算法，与遍历的时间复杂度为相同O(n)1.3.12RightChild功能查找右孩子，利用递归的算法，与遍历的时间复杂度为相同O(n)..1.3.13LeftSibling功能查找节点的左边的堂兄弟的，找到后输出该节点的数据..1.3.14RightSibling功能查找节点的右边的堂兄弟的，找到

5、后输出该节点的数据..1.3.15InsertChild函数在二叉链表中插入新的节点1.3.15DeleteChild功能删除指定编号的数据元素，传入头结点地址、编号i、表结点类型结构体地址来返回被删除元素内容。执行前先判断传入的编号是否在可寻找范围内。执行删除操作之后，进行“移位”运算。时间复杂度仍为O(n)。如下：..1.3.16PreOrderTraverse功能前序遍历二叉链表中的数据，采用先遍历左孩子，再访问根节点，后访问右孩子的思想来实现前序遍历的算法的。..1.3.17InOrderTraverse功能中序

6、遍历的函数，对二叉链表的数据进行访问，并且利用PreOrderTraverse函数1.3.18PostOrderTraverse功能采用后续遍历的思想，利用先序遍历的函数进行..1.3.19LevelOrderTraverse功能完全遍历二叉链表中的数据，并进行输出的..1.3.20Point功能定位节点的函数，在需要查找二叉链表二叉树的节点的时候，可以直接调用该函数，进行处理，相应的代码如下1.3.21FILE*fileOpen功能读取功能，通过fscanf实现格式化读取，同时结合CreateList函数实现顺序..1

7、.3.22BiTNode*Create(FILE*fp)功能把二叉链表二叉树的数据写入到文件中去1.4效率分析在上面介绍各功能时已经提到时间复杂度的计算了，这里再简单分析一下。具有同数量级复杂度的功能在实现方法上一般近似。比如InOrderTraverse，PostOrderTraverse，BiTreeDepth，LevelOrderTraverse它们都是基于PreOrderTraverse来设计的，所以效率都是O(n)；而Root，Value，Assign，Parent，LeftChild，RightChild，L

8、eftSiblingRightSibling，InsertChild，DeleteChild是基于VisitPoint，平均效率为O(n)；InitTreeDestroyBiTree所需信息，所以效率为O(1)；CreateBiTreeClearBiTreeBiTreeEmpty都要对二叉链表，平均效率为O(n)。.