PHP|PHP 实现数据结构 PHP实现数据结构

【PHP|PHP 实现数据结构】参考诸多视频和文章，主要通过PHP 实现线性表的顺序存储结构，单链表，静态链表，双向链表以及二叉树等数据结构，代码中主要在各个实现脚本内部，通过注释以及images目录下的手绘图做详细的解释。另外，由于php没有指针，各个实现中，通过Node类来模拟结构题以及指针功能。
最后，如果有任何问题、感谢指正
代码地址： https://github.com/Sihuafu/php-data-structure

数据结构：

计算机存储，组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

数据类型：

是指一组性质相同的值的集合以及定义在此集合上的一些操作的总称，例如：整型，浮点型，字符型分为：原子类型，例如：整型，浮点型，字符型结构类型，由若干个类型组合而成。

抽象：

是指抽出事物具体的普遍性的本质。它要求抽出问题的特征而忽略非本质的细节。是对具体事物的一个概括。抽象是一种思考问题的方式

抽象数据类型，Abstract Data Type, ADT.

是指一个数据模型以及定义在该模型上的一组操作描述一个抽象数据类型： ADT 线性表（List） Data 数据对象 Operation 数据对象上的操作，比如初始化，创建，插入，删除等 EndData

线性表 (code List/)

由领个或多个数据元素组成的有限序列当有0个元素的线性表称为，空表

线性表 - 顺序存储结构

指的是一段地址连续的存储单元依次存储线性表的数据元素物理上的存储方式就是在内存中，通过占位符形式，把一定内存给占用，然后把相同的数据类型的元素依次放在这块内存当中

树 (code Tree/)

是n(n>=0)个结点的有限集，当n=0时为空树在任意一颗非空树中：有且仅有一个特定的根结点当n>1时，其余结点可分为互不相交的有限集，其中每个集合又是一颗树，并成为根的子树结点拥有的子树数量，称为结点的度 degree 树的度取树内各结点的度的最大值度为0的结点称为叶结点(Leaf)或终端结点度不为0的结点称为分支结点或非终端结点。除根结点外。分支结点也称为内部结点树中结点的最大层次称为树的深度(Depth)或高度如果将树中的各个子树看成从左到右是有次序的，不能互换的，则称为树为有序树，否则称为无序树森林是m颗子树互不相交的树的集合

二叉树 Binary Tree

是n (n>=0)个结点的有限集合，该集合为空称为空二叉树由一个根结点和两颗互不相交的，分别称为根结点的左子树和由子树的二叉树组成特点每个结点最多有两颗子树，左子树和右子树是又顺序的，次序不能颠倒即使树中某结点只有一颗子树，也要区分它是左子树还是右子树五种形态空二叉树只有一个根结点的二叉树根结点只有左子树的二叉树根结点只有由子树的二叉树根结点既有左子树又有右子树的二叉树斜树要么左右结点都是左子树，要么都是右子树，一条线的斜满二叉树所有分支结点都有左子树和右子树，并且所有叶子都在同一层，称为满二叉树完全二叉树对一颗具有n个结点的二叉树按层序编号，如果编号i(1<=i<=n)的结点与同样深度的满二叉树中的编号i的结点位置完全相同，则称为完全二叉树性质：在二叉树的第i层上，至多有2^(i-1)个结点，与byte的二进制有点类似深度为k的二叉树，至多有2^k - 1个结点(k>=1)，也有byte的二进制有点类似，比如一个字节有符号的最大值0111，即2^k - 1 对任何一颗二叉树T，如果其终端结点树为n0，度为2的结点树为n2，则n0 = n2 + 1 具有n个结点的完全二叉树的深度为 logn的结果向下取整之后 + 1， 2为底数。个人理解深度k = log(n+1)，2 为底树存储结构用一维数据存储二叉树中的各个结点，并且结点的存储位置能体现结点之间的逻辑关系，浪费空间二叉链表每个结点最多两个子结点，所以设计一个结构，包含一个数据域和两个指针域，组成的链表称为二叉链表二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问依次且仅被访问一次方式：前序遍历访问根结点的操作发生在遍历其左右子树之前若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，在前序遍历右子树，见/images/二叉树遍历-前序遍历.jpeg 中序遍历访问根结点的操作发生在遍历其左右子树之中（间）。若树为空，则空操作返回，否则，中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树见/images/二叉树遍历-中序遍历.jpeg 后序遍历访问根结点的操作发生在遍历其左右子树之后。若树为空，则空操作返回，否则遍历左子树，然后遍历右子树，最后访问根结点见/images/二叉树遍历-后序遍历.jpeg 层序遍历若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上至下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问见/images/二叉树遍历-层序遍历.jpeg