数据结构

线性表是n个具有相同特性的数据元素的优先序列如，顺序表（数组）、链表、栈、队列、字符串……

线性表是逻辑上的线性结构，物理结构上不一定为连续的。

1.顺序表

顺序表是用一段物理地址连续的储存单元依次储存数据的线性结构，一般情况下用数组储存，在数组上完成数据的增删改查。

顺序表分为：

• 静态顺序表：使用定常数组存储

• 动态顺序表：使用动态开辟的数组存储

1. 中间/头部插入删除，时间复杂度为O(N)
2. 增容许愿申请新的空间，拷贝数据，释放旧的空间
3. 增容一般呈2倍的增长，势必会造成空间的浪费。

2.链表

链表是一种物理储存结构非连续，非顺序的储存结构，元素的逻辑顺序是通过链表中的指针连接次序实现的。

链表有很多种：

• 单向、双向

• 带头、不带头

• 循环、不循环

无头单向非循环链表：结构简单，一般不会单独用来存储数据，实际种更多的是作为其他数据结构的子结构，如哈希桶，图的邻接表等。

带头双向循环链表：结构复杂，一般用在单独存储数据，实际种使用链表结构都是带头双向循环链表。另外这个结构虽然复杂，但是使用代码实现以后发现结构中会带来很多优势。

顺序表和链表比较

顺序表：

优势：空间连续，支持随机访问

劣势：中间插入和头插以及删除的时间复杂度为O(N),增容代价比较大。

链表：

优势：对任意一个位置进行插入和删除时间复杂度都是O(1),增容代价小，插入一个元素开辟一个元素的空间

劣势：一节点为单位储存，不支持随机访问

4. 栈

栈：一种特殊的线性表，其只允许在一端进行插入和删除操作，进行数据插入和删除操作的一段称为栈顶，另一端称为栈底。栈中的元素遵循元素后进先出的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶。

出栈：栈的删除操作叫做出栈。数据出栈也在栈顶。

栈的实现一般可以使用数组或者链表实现，相对而言其他结构更优一些因为在尾部插入数据的代价比较小。

5.队列

队列：只允许在一端进行插入数据的操作，在另一端进行删除数据的操作的线性表，队列具有先进先出原则。

对头：进行删除操作的一端称为对头。

对尾：进行插入操作的一段称为队尾。

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组上出数据。效率比较低。

6.二叉树

树是一种非线性的数据结构，它是由n（n>=0）个有限系欸但组成的有层次的关系的集合。

有关名词定义：

节点的度：一个节点含有的子树的个数称为该节点的度

叶节点或者终端节点：度为0的节点称为叶节点

非终端节点或分支节点：度度不为0的节点

双亲节点或者父节点：若一个节点含有的子节点，则这个节点称为其子节点的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点

树的度：一棵树中，最大的节点的度称为树的度

节点的层次：从跟驾驶定义，根为第一层，根的子节点为第二层，以此类推

树的高度或者深度：树种节点的最大层次

堂兄弟节点：双亲在同一层的节点合称为堂兄弟节点

节点的祖先：从根节点多经分支上的所有节点

子孙：以某节点为根的子树中任一节点都称为该节点的子孙节点

森林：由m(m>=0)棵不相交的树的集合称为森林

树的表示

树结构相对线性表比较复杂，要存储表示比较麻烦，实际中树有很多表示方法。如双亲表示法，孩子表示法，孩子兴地表示法；

二叉树

一颗二叉树是节点的一个有限集合，该集合或者为空，或者是由一个根节点加上两颗别称为左右子树的二叉树组成；

特点：

每个节点最多有两个子树，二叉树的度不大于2

二叉树的子树有左右之分，其子树的次序不能颠倒

数据结构中的二叉树：

• 空树：根节点为空没有任何子树
• 单个节点：只有一个节点构成的二叉树
• 两个节点构成二叉树：一个节点为根节点，另一个节点为根节点的左孩子或右孩子
• 多节点二叉树：节点数目在2个以上，且具有二叉树的特点的树

特殊的二叉树：

1. 满二叉树：一个二叉树如果每一个节点的节点数都达到最大值，则成这个二叉树为满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个节点的二叉树，当且仅当每一个节点都是深度为K的满二叉树中编号从1至n的节点——对应时称为完全二叉树。

   

二叉树的存储结构

二叉树一般可以使用两种结构存储，一种时顺序结构，一种时链式结构

顺序存储

顺序结构就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间浪费。而现实中只有在堆排序才会使用数组来存储，关于堆我在另一篇博客中有总结，二叉树顺序在物理上是一个数组，在逻辑上是一可二叉树。

链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

struct BinaryTreeNode {
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子 
    struct BinTreeNode* _pRight; // 指向当前节点右孩子 
    BTDataType _data; // 当前节点值域 
}

二叉树链式结构的遍历

• 前序遍历：访问根节点的操作发送在遍历左右子树之前

• 中序遍历：访问根节点的操作发生在遍历左右子树之中

• 后续遍历：访问根节点的操作发生在遍历其左右子树之后

• 层序遍历：从根节点出发，从第一层的根节点开始，访问每一层的节点，自上而下，自左至右的过程