数据结构总览（1）
数据结构
概念
数据
数据元素，数据项
数据对象
数据类型
+ 原子类型
+ 结构类型
+ 抽象类型
数据结构定义
数据元素之间存在一个或者多个特定关系的元素集合
逻辑结构
线性，线性表，栈，队列，数组
非线性，树，图，集合
物理结构
顺序，链表，索引，散列
算法
五要素，有穷性，正确性，可行性，输入和输出
时间复杂度:
O(1) O(logN) O(N) O(NlogN) O(N^2) O(N^3) O(2^N) O(3^N) O(N!) O(N^N)
空间复杂度
O(1) : 算法原地工作
线性表
顺序表
顺序表的基本操作
顺序表的操作，新增，删除，查找
链表
单链表
双链表
循环链表
链表的操作，新增，删除，查找，头插法，尾插法，头结点
静态链表
线性表的顺序表和链表对比
栈，队列，矩阵
栈
栈的顺序存储
栈的链式存储
共享栈
栈的基本操作push.,pop,empty
栈卡特兰公式
队列
队列的顺序存储
队列的链表存储
队列的的基本操作，新增，删除,pop,push
双端队列
输出和输入双端队列
栈和队列的应用
栈
括号匹配
计算表达式（前缀表达式，后缀表达式）
树的非递归遍历
函数调用栈
队列
树的层序遍历
打印机
操作系统中的任务调用
多维数组，矩阵，稀疏矩阵
多维数组的下标表示
对称矩阵和矩阵的存储
三角矩阵，上三角矩阵，下三家矩阵
对三角矩阵
字符串
字符串，子串
子串的匹配
暴力匹配
KMP算法
next数组
nextval数组
树
树的基本概念
根，父亲，双亲，孩子，祖父，子孙，兄弟，堂兄弟，叶子结点，非叶子结点
高度，层，深度
树的分支，树的度，有序树，非有序树
N个节点的最小高度 h = log m(n*(m+1) -1),m 为树点的度
二叉树
度为二的树
二叉树
完全二叉树，满二叉树
完全二叉树，满二叉树一些特性
排序树
平衡二叉树
树的遍历和线索化
树的遍历（递归和非递归算法）
树的前序遍历
树的后续遍历
树的中序遍历
树的线索化（利用度为0的节点和度为1的节点的左右子树为空，建立前驱和后驱线索）
树的前序线索
树的后续线索
树的中序线索
树和森林
树和森林的存储
双亲表示法
孩子表示法（链表法）
孩子兄弟表示法
树和森林的遍历
树的后序遍历 = 森林的中序遍历 = 二叉树的中序遍历
树的先序遍历 = 森林的先序遍历 = 二叉树的先序遍历
树的应用
哈夫曼树
带权路径长度
哈夫曼编码
并查集
