Theevilspirit
采用二叉链表作为树的物理结构,通过C语言程序实现课本§3.2的基本运算。要求具有易于操作易于理解的简易菜单,可选择实现树的文件形式存储。源代码须有适当的注释,便于检查和后期的修改与理解。
该线性表的实现包括一个.CPP文件。文件中定义了线性表的结构体、相关运算的函数定义及其实现、测试系统、多表管理、文件操作等函数。由于整个线性表比较简单,而且没有“#include”的需要,因此没有使用头文件。
通过实验达到:
加深对二叉树的概念、基本运算的理解;
熟练掌握二叉树的逻辑结构与物理结构的关系;
以二叉链表作为物理结构,熟练掌握二叉树基本运算的实现。
数据结构的实现根据实验要求的ADT定义,定义了基于C语言结构体的ADT定义。由于之前的实验(线性表)要求给出的代码的Codebase是经典的C语言面向过程的写法,没有使用C++的类,对于此次实验按照该模式模仿。结构体如下:
struct ElemType {
ValueType value;
size_t index;
bool null = true;
};
struct BiTreeNode {
ElemType data;
BiTreeNode* parent = NULL;
BiTreeNode* left = NULL;
BiTreeNode* right = NULL;
};
struct BiTree {
bool init = false;
BiTreeNode* root = NULL;
};
根据实验的要求以及二叉树ADT的定义,该二叉树ADT应包括如下的操作:
InitBiTree(初始化)
DestroyBiTree(销毁)
CreateBiTree(根据definition创建)
ClearBiTree(清空)
BiTreeEmpty(判断二叉树是否为空)
BiTreeDepth(求二叉树的深度)
Root(获取二叉树的根节点)
Value(根据index获取二叉树的节点值)
Assign(根据index获取某个节点并赋新值)
Parent(返回某节点的双亲节点)
LeftChild(返回某节点的左孩子)
RightChild(返回某节点的右孩子)
LeftSibling(返回某节点的左兄弟)
RightSibling(返回某节点的右兄弟)
InsertChild(将某非空无右子树的二叉树插入到某节点的左或右孩子处)
DeleteChild(删除某节点的左或右孩子)
PreOrderTraverse(先序遍历二叉树)
InOrderTraverse(中序遍历二叉树)
PostOrderTraverse(后序遍历二叉树)
LevelOrderTraverse(层级遍历二叉树)
为了便于错误处理,定义以下常量作为错误标识:
enum Error {
INIT,
NOT_INIT,
WRONG_DEF,
NO_SUCH_NODE,
};
其中,status是某个方法的返回类型,用于标志是否正确执行了相应的运算。Status的取值由上面的宏定义定义。当不为1时,认为发生了错误。然后可以根据status的值确定发生了何种错误。
ADT的运算有下面的函数定义,这些函数均返回status(如果不返回其他有用的值)、bool(判断是否为空)、size_t(求出长度或者位置)、BiTreeNode*(获取某个节点)。
status InitBiTree(BiTree& T);
status DestroyBiTree(BiTree& T);
status CreateBiTree(BiTree& T, vector<ElemType> def);
status ClearBiTree(BiTree& T);
bool BiTreeEmpty(const BiTree& T);
int BiTreeDepth(const BiTree& T);
BiTreeNode* Root(const BiTree& T);
status Value(const BiTree& T, size_t index, ElemType& value);
status Assign(BiTree& T, size_t index, ElemType& value);
BiTreeNode* Parent(const BiTree& T, size_t index);
BiTreeNode* LeftChild(const BiTree& T, size_t index);
BiTreeNode* RightChild(const BiTree& T, size_t index);
BiTreeNode* LeftSibling(const BiTree& T, size_t index);
BiTreeNode* RightSibling(const BiTree& T, size_t index);
status InsertChild(BiTree& T, size_t index, bool LR, BiTree& c);
status DeleteChild(BiTree& T, size_t index, bool LR);
status PreOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
status InOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
status PostOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
status LevelOrderTraverse(const BiTree& T);
使用C++ STL的Vector作为多二叉树的容器。使用容器可以简化相关的操作,同时具有很高的健壮性,也可以减少问题。
具体的思路为:在程序开始的时候创建一个空vector,同时设置一个索引变量,用于指示当前二叉树在vector中的位置。在运行的时候,每当用户选择新建一个线性表的时候,就将一个线性表添加到里面。
容器的定义如:
vector<BiTree> trees = {};
文件操作可以使二叉树的节点存放到硬盘上永久保存,更加贴近真实的使用场景。通过C语言标准库提供的文件读写API,可以很方便的操作文件。
通过fopen可以返回一个指针,该指针可以用来操作先前打开的文件。同时可以制定打开文件的方式,例如“r”可以用来打开一个只读文件。然后使用此文件进行读写操作,最后使用fclose销毁该指针。
具体的实现为,写出到文件时,先将二叉树容器trees的size写出到文件,然后遍历多二叉树的容器trees,对于每一个BiTree,先将其节点数目写出,然后先序遍历该二叉树(由于需要可以复原该二叉树,该先序遍历允许空节点),将所有的节点依次写出到文件中,每次写出sizeof(ElemType)个字节。
读文件时将上述操作逆着执行一遍即可。
开发环境选用Windows 10上的VSCode作为编辑器,g++作为编译器,g++的版本为8.1.0。
status InitBiTree(BiTree& T);
status DestroyBiTree(BiTree& T);
status CreateBiTree(BiTree& T, vector<ElemType> def);
status ClearBiTree(BiTree& T);
bool BiTreeEmpty(const BiTree& T);
int BiTreeDepth(const BiTree& T);
BiTreeNode* Root(const BiTree& T);
status Value(const BiTree& T, size_t index, ElemType& value);
status Assign(BiTree& T, size_t index, ElemType& value);
BiTreeNode* Parent(const BiTree& T, size_t index);
BiTreeNode* LeftChild(const BiTree& T, size_t index);
BiTreeNode* RightChild(const BiTree& T, size_t index);
BiTreeNode* LeftSibling(const BiTree& T, size_t index);
BiTreeNode* RightSibling(const BiTree& T, size_t index);
这五个操作接受一个已经开辟好内存的BiTree结构体的引用为第一个参数、要获取Parent、左孩子、右孩子、左兄弟、右兄弟的节点的index为第二个参数,返回与该节点有相应关系的节点。首先,该操作检查二叉树是否已经被初始化了,如果没有被初始化,则返回一个Error::NOT_INIT的错误。获取二叉树某个节点的相应关系的节点的方法是:
双亲结点:遍历该二叉树,依次判断各个节点的左右Child节点的index是否和参数提供的相等,如果相等则将该节点返回。
左孩子结点:遍历该二叉树,依次判断各个节点的index是否和参数提供的相等,如果相等则将该节点的BiTreeNode::left域返回。
右孩子结点:遍历该二叉树,依次判断各个节点的index是否和参数提供的相等,如果相等则将该节点的BiTreeNode::right域返回。
左兄弟结点:遍历该二叉树,依次判断各个节点的index是否和参数提供的相等,如果相等则将该节点的父节点的左孩子节点返回,如果等于该节点本身,则返回NULL。
右兄弟结点:遍历该二叉树,依次判断各个节点的index是否和参数提供的相等,如果相等则将该节点的父节点的右孩子节点返回,如果等于该节点本身,则返回NULL。
如果要寻找的节点不存在,这五个操作均会抛出(throw)一个Error::NO_SUCH_NODE错误。
这五个操作的时间复杂度为O(N),空间复杂度为O(logN)。
status InsertChild(BiTree& T, size_t index, bool LR, BiTree& c);
status DeleteChild(BiTree& T, size_t index, bool LR);
status PreOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
status InOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
status PostOrderTraverse(const BiTree& T, function<void(BiTreeNode*)>);
这三个操作接受一个已经开辟好内存的BiTree结构体的引用为第一个参数、一个回调函数指针作为第二个参数,返回该操作执行的状态。该操作用于遍历该二叉树。首先,该操作检查二叉树是否已经被初始化了,如果没有被初始化,则返回一个Error::NOT_INIT的错误。遍历的方法是递归调用遍历函数。遍历函数根据先序、中序或者是后序,按照对应的顺序递归执行遍历函数:
先序遍历:对当前节点执行Visit函数、对左孩子递归调用遍历函数、对右孩子递归调用遍历函数。
中序遍历:对左孩子递归调用遍历函数、对当前节点执行Visit函数、对右孩子递归调用遍历函数。
后序遍历:对左孩子递归调用遍历函数、对右孩子递归调用遍历函数、对当前节点执行Visit函数。
该操作的时间复杂度为O(N),空间复杂度为O(logN)。
多表系统实现了添加一张表、更改当前表两个操作(没有实现删除表)。
添加一张二叉树
添加一张二叉树就等价于在vector<BiTree>中添加了一个BiTree的实例,该BiTree的所有字段都是按照默认初始化进行初始化的。因此,该二叉树虽然有了内存空间但是却是一个空二叉树,其root等关键字段都是无效的值。
更改当前二叉树
更改当前表就等价于修改了指向vector<BiTree>的下标。该下标的取值为0至vector<BiTree>的长度。修改下标即可实现修改当前表所指向的值。从而达到修改当前表的目的。
容易可得,这两个操作的时间复杂度都为O(1)。
通过fopen可以返回一个指针,该指针可以用来操作先前打开的文件。同时可以制定打开文件的方式,例如“r”可以用来打开一个只读文件。然后使用此文件进行读写操作,最后使用fclose销毁该指针。在写文件的时候,可以将整个elems数组以2进制的方式存入文件。在读取的时候,连续读取每次读取sizeof(T)个字节,然后将这些字节拷贝到elems里面,直到读取到文件尾为止。同时,每次读取使线性表的长度增加1个长度。
文件操作可以使二叉树的节点存放到硬盘上永久保存,更加贴近真实的使用场景。通过C语言标准库提供的文件读写API,可以很方便的操作文件。
通过fopen可以返回一个指针,该指针可以用来操作先前打开的文件。同时可以制定打开文件的方式,例如“r”可以用来打开一个只读文件。然后使用此文件进行读写操作,最后使用fclose销毁该指针。
具体的实现为,写出到文件时,先将二叉树容器trees的size写出到文件,然后遍历多二叉树的容器trees,对于每一个BiTree,先将其节点数目写出,然后先序遍历该二叉树(由于需要可以复原该二叉树,该先序遍历允许空节点),将所有的节点依次写出到文件中,每次写出sizeof(ElemType)个字节。
读文件时将上述操作逆着执行一遍即可。
演示系统测试如下图所示:
该演示系统操作简单,输入对应的数字并按下回车即可。输入0-22表明运行对应的功能,且相应操作的结果会被输出到屏幕上,输入0退出系统。输入-1进入debug界面。
keyboard_arrow_left上一篇 : C语言实现的基于查找表的单词检索软件 基于QT实现的学生信息管理系统 : 下一篇keyboard_arrow_right