数据结构知识框架
先概览一下思维导图
数据
描述客观事物的符号，是计算机中可以操作的对象，能被计算机识别，并输入给计算机处理的符号集合
数据元素
是组成数据的、有一定意义的基本单位，在计算机通常作为整体处理，也被称为记录
数据项
一个数据元素可以由若干个数据项组成。数据项是数据不可分隔的最小单位
数据结构形式
数据结构
是相互之间存在一种或多种特定关系的数据元素的集合
分类
逻辑结构
集合结构
线性结构
树形结构
图形结构
物理结构
顺序存储结构
链式存储结构
具体概念
逻辑结构
数据对象中数据元素之间的相互关系
集合结构
集合中的数据元素除了同属一个集合外，它们之间没有其他关系
线性结构
数据元素之间是一对一的关系
树形结构
数据元素之间存在的一种一对多的层次关系
图形结构
数据元素是多对多的关系
物理结构
数据的逻辑结构在计算机中的存储形式
顺序存储结构
数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
链式存储结构
数据元素存放在任意的存储单元里，存储单元可以是连续的，也可以是不连续的
逻辑结构是面向问题的，物理结构是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中
程序算法
数据结构
算法
解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
算法特性
输入
算法有零个或多个输入
输出
至少有一个或多个输出
有穷性
算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且一个步骤在可接受的时间内完成
确定性
算法的每一个步骤都有确定含义，不会出现二义性
可行性
算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成
设计算法要求
正确性
可读性
健壮性
时间效率高
且空间使用率低
简单性
算法的复杂度 时间复杂度 空间复杂度 算法分析的分类
平均情况
任意输入规模的期望运行次数
最坏情况
任意输入规模的最大运行次数
最好情况
任意输入规模的最小运行次数，通常最好情况不会出现
时间复杂度--O渐进表示法
一般算法O(n)计算法
用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项系数存在且不是1，则去除与这个项相乘的常数
分治算法的时间复杂度计算
二分搜索算法的时间复杂度是lgN
M分搜索算法的时间复杂度为logM^N
递归算法的时间复杂度计算
递归总次数*每次递归次数
递归算法空间复杂度算法
N*每次递归空间大小
递归 递归定义若一个对象部分的包含它自己或者用它自己给自己定义，则称这个对象是递归的
递归的过程一个过程直接或间接的调用自己
递归的思想把问题分解成规模更小的具有与原来问题具有相同解法的小问题
递归条件缩小问题规模，使新问题与原问题具有相同的解决方式
设置递归的出口
递归分类
数据结构递归
问题解法递归
递归调用栈
尾递归
递归调用返回的结果总被直接返回
尾递归的本质
将单次计算的结果缓存起来，传递给下一次调用，相当于自动累积
时间复杂度
递归总次数*每次递归次数
回溯法
基本思想
迷宫算法
递归的优缺点
优点
递归在解决某些问题的时候使得我们思考的方式的以简化，代码也更加简练，容易阅读
缺点
递归的实质就是自己调用自己，而函数的调用开销是很大的，系统要为每次函数调用分配空间存储空间，并将调用点信息压栈，而在函数的调用结束后，还要释放空间，弹栈恢复断点，如果递归方案的复杂度
栈 栈的概念一种特殊的线性表，只允许从一端插入和删除数据
特点：后进先出 顺序栈顺序堆栈和书序表数据成员相同 ，不同之处，顺序堆栈的入栈和出栈操作只允许对当前栈顶进行
共享栈
一个数组实现两个栈
原理
既然是两个栈共享一段空间，向中间靠拢，数组两端表示两个栈的栈底，栈顶一直向中间靠近
应用场景
两个栈空间需求有相反的关系，也就是一个增长一个缩短的场景
链式栈头插头删
栈的应用括号匹配
逆波兰表达式
迷宫算法
队列 只允许在一端插入数据，在另一端删除数据的特殊线性表 顺序队列
实现方式一
队头不动出队列时所有元素向前移动
实现方式二
出队列时，队头向后移动一个位置
假溢出现象
多次入队列、出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出
真溢出现象
最大存储空间已经存储满，继续进行入队列操作
循环队列
头尾相接的顺序存储队列就是循环队列
队列满队列空的判断
少用一个存储空间
队尾指针加一等于队头指针就是队列满的判断条件
判空条件是尾和头相等
设计一个标记flag
初始flag置为0，入队列成功flag=1，出队列成功flag置为0
队空条件rearfront&&flag0,
堆满条件rear==front&&flag=1
设置一个计数器
初始时count=0,入队列成功，count+1,出队列成功count-1
队列空的条件count==0
队列满的条件count>0&&rear==front或者count == MaxSize
链式队列队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进，头出而已
优先级队列
带有优先级的队列
优先级高的先出队列，优先级相同的遵守先进先出规则
队列的应用生产者消费者模型
消息队列
排队现象
网络数据传输
矩阵 特殊矩阵有很多值相同的元素或有许多零元素，且值相同的元素或零元素的分布有一定规律的矩阵
对称矩阵
一个N*N矩阵，任意Aij = Aji
对称矩阵压缩存储
由于对称矩阵上三角和下三角是相同的所以只需存一半即可
对称矩阵和对称压缩存储的关系
下三角
i>jSymmetricMatrix[i][j] == Array[i*(i+1)/2+j]
稀疏矩阵
M*N矩阵，矩阵有效值的个数远小于无效值的个数，分布没有规律
稀疏矩阵压缩存储
只存储少量的有效值
使用{row,col,value}三元组按照数组中的位置，以行优先级先后顺序一次存放
矩阵逆置行列互换
快速逆置
初识树 树的基本概念
由N个节点（N>=0）构成的集合
有一个特殊的节点，称为根节点，根节点没有前驱节点
除过根节点外，其余节点别分成M个（M>0）个互不相交的集合T1、T2...Tn,其中每一个集合又是一棵与树结构类似的子树
树是递归定义的
名词解释
结点
结点包括一个数据元素及若干指向其他子树的分支（指针（索引））
结点的度
结点所拥有的的子树的个数
度为0的结点
又称终端节点
分支结点
度不为零的结点
非终端结点
祖先结点
从根结点到该结点所经分支上的所有结点
子孙结点
以某结点为根结点的子树中的所有结点
双亲结点
树中某结点有孩子节点，该结点称为它孩子节点的双亲结点
孩子结点
树中一个结点的子树的根结点称为该结点的孩子结点
兄弟结点
具有相同双亲结点的结点
树的度
树中所有结点的度的最大值
结点的层次
从根结点到树中某结点所经路径上的分支数
树的深度
树中所有结点的层次的最大值
有序树
树中结点的各棵子树T0,T1...是有序的
无序树
树中结点的各棵子树之间的次序不重要，可以相互交换位置
森林
树m棵树的集合
树的表示方法目录结构
集合文氏图
树的存储结构
双亲表示法
用指针表示出每个结点的双亲结点
优点
寻找一个结点的双亲结点操作实现很方便
缺点
寻找一个结点的孩子结点很不方便
孩子表示法
用指针指出每个结点的孩子结点
优点
寻找一个结点的孩子结点比较方便
缺点
寻找一个结点的双亲结点很不方便
双亲孩子表示法
用指针既表示出每个结点的双亲结点，也表示出每个结点的孩子结点
孩子兄弟表示法
表示出第一个结点的第一个孩子结点，也表示出每个结点的下一个兄弟结点
树的应用电脑的目录
树之二叉树 概念一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成
特点每个结点最多有两棵子树
二叉树的子树有左右之分，其次序不能颠倒
满二叉树所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上
完全二叉树如果一棵具有N个结点的二叉树的结构与满二叉树的前N个节点 的结构相同，称为完全二叉树
二叉树的性质、
若规定根节点的层次为1，则一棵非空二叉树第i层上最多有2^（i-1）（i>=1）个结点
若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^k-1 (k>=0)
对任何一棵二叉树，如果其叶结点个数为n0，度为2的非叶结点个数为n2,则有n0 = n2+1
具有n个结点的完全二叉树，如果按照从上至下从左到右的顺序对所有结点从0开始编号，则对于序号为i的结点有：
如果i>0,则序号为i的结点的双亲结点的序号为（i-1）/2,如果i==0，则序号为i的结点为根节点，无双亲结点
如果2i+1<n,则序号为i的双亲结点的左孩子序号是（i-1）/2，如果(2i+1)>=n,则序号为i结点无右孩子结点
如果2i+2<n,则序号为i结点的右孩子结点的序号为2i+2,如果2i+2>=n,则序号为i结点无右孩子结点
二叉树的存储结构
顺序存储
优点、
存储完全二叉树，简单省空间
缺点
对一般二叉树尤其单支树，存储空间利用不理想
链式存储
子主题 1
仿真指针（静态链表）
二叉树的基本操作
二叉树的创建
二叉树的遍历
前序
中序
后序
层序
初始化一个队列
把根节点的指针入队列
当队列非空时循环执行
出队列取一个节点
若该结点的左子树非空，将该节点的左子树指针入队列
若该节点的右子树非空将该节点的右子树入队列
结束
线索化二叉树 线索化概念按照二叉树的遍历将二叉树导成一个线性序列
普通二叉树可能存在的问题递归遍历有可能导致栈溢出
非递归版本可能会降低程序的效率
想要找到某种遍历形式下某个节点的前驱还是后继比较难
树中有大量的空指针域造成浪费，
线索化过程当某结点的左指为空时，令该指针指向按照某种方式遍历二叉树时得到该结点的前驱节点
当某结点的右指针为空时，令该指针指向按照某种遍历方式遍历二叉树时得到该结点的后继结点
线索标志位
作用区分是孩子结点还是前驱或者后继
leftThread
0
leftChild
1
leftThread
rightThread
0
rightChild
1
rightThread
线索结点中指向前驱或者后继结点的指针
线索二叉树二叉树的结点加上线索的二叉树
对二叉树按照某种方式（前序、中序、后序）遍历使其称为线索二叉树的过程称为按照什么方法对二叉树进行线索化
堆 堆的概念