数据结构
2021-05-07 09:59:15 44 举报AI智能生成
登录查看完整内容
数据结构与算法知识整理
作者其他创作
大纲/内容
数据结构与算法
线性表
线性表顺序存储结构
数组
线性表链式存储结构
相关概念
头指针：链表中第一个结点存储的位置称为头指针， 如果单链表有头结点，则头指针指向头结点 ，如果单链表没有头结点，则头指针指向第一个首元结点
头节点：在单链表的一个结点前附设一个结点称为头结点，数据域可以不存任何信息，指针域指向单链表第一个元素的结点
首元结点：单链表中第一个有数据元素的结点，如果单链表有头结点，则首元结点为头结点的下一个结点，如果单链表没有头结点，则首元结点就是单链表的第一个结点
单链表：包含一个数据域和一个指针域
静态链表：用数组描述(数据域，指针域)的链表叫静态链表
循环链表：将单链表中终端结点的指针域由空指针改为指向头结点，使单链表形成一个环
双向链表： 在单链表中的每个结点中，再设一个指向其前驱结点的指针域
栈与队列
定义
栈：先进后出
栈应用
两栈共享空间
栈的应用-递归
栈的应用-四则运算
中缀表达式转后缀表达式
栈顶指针：指向栈顶结点的指针
单调栈
单调递增栈：从栈顶到栈底递增
单调递减栈：从栈顶到栈底递减
队列：先进先出
循环队列：
front指针：指向对头元素
rear指针：指向队尾元素的下一个位置
单调队列
单调递增队列：从队头到队尾递增
单调递减队列：从队头到队尾递减
应用:滑动窗口问题
存储
顺序存储：数组
链式存储：链表
串
存储结构
顺序存储：以一段连续的存储空间
链式存储:可以一个结点对应一个字符，也可以一个结点对应多个字符，若结点未占满可用其他非串值字符填满
朴素模式匹配算法：
KMP模式匹配算法
概念：子串与主串不匹配时，子串下一个开始匹配的索引的值取决于与子串当前失配字符之前的字符的最大前后缀的相似度
注意：对于短的字符串匹配，KMP算法效率可能不如朴素模式匹配算法，因为KMP算法要首先生成next数组
树
树是n(n>=0)个结点的集合，n=0时是空树。对于任意非空树：1.有且仅有一个特定的称为根的结点；2.当n>1时，其余结点可分为m(m>=0)个互不相交的有限集，其中每一个集合本身又是一棵树，并称为根的子树
度：结点拥有的子树数称为节点的度
叶结点(终端结点)：度为0的节点称为叶结点(终端结点)
分支结点(非终端结点)：度不为0的节点称为分支结点(非终端结点)，除根结点外，分支节点也称内部结点
树的度：树的度是树内各结点度的最大值
孩子和双亲：结点的子树的根称为该结点的孩子。相应的该结点称为孩子的双亲
兄弟：同一个双亲的孩子之间互称为兄弟
祖先：结点的祖先是从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中的任意结点都称为该结点的子孙
结点层次: 从跟开始定义起，根为第一层，根的孩子为第二层
树的深度（高度）: 树中结点的最大层次称为树的深度或高度
森林：m(m>=0)棵互不相交的树的集合
树的存储结构
双亲表示法：以一组连续的空间存储树的结点，同时在每个结点中，附设一个指示器，指示其双亲结点到链表中的位置
孩子表示法：把每个结点的孩子结点排列起来，以单链表作为存储结构。则n个结点有n个孩子链表，叶结点的单链表为空，然后n个头指针又组成一个线性表存放进一个一维数组中
二叉树
二叉树是n(n>=0)个结点的有限集合，该集合或者为空集，或者由一个根结点和两个互不相交的，分别称为根结点的左子树和右子树的二叉树组成
特殊二叉树
斜树:所有结点都只有左子树或只有右子树的二叉树
满二叉树：在一棵二叉树中，所有的分支结点都有左子树和右子树，并且所有的叶子结点都在同一层上，这样的二叉树称为满二叉树
完全二叉树：对一棵具有n个结点的二叉树按层级编号，如果编号为i的结点与和它相同深度的满二叉树的编号为i的结点在树中位置一致，则这棵二叉树称为完全二叉树
二叉查找树(BST)：对于树中每个结点X，它的左子树中所有项的值都小于X项的值，它的右子树中所有项的值都大于X项的值
线索二叉树:指向前驱和后继的指针称为线索，在二叉树的结点上加上线索的二叉树称为线索二叉树 对二叉树以某种次序遍历，使其变为线索二叉树的过程称做线索化
平衡二叉树
平衡二叉树是一种二叉查找树，其中每一个结点的左子树和右子树高度差至多为1
性质
1: 在二叉树的第i层上，最多有2^i - 1个结点
2：深度为k的二叉树，最多有2^k - 1个结点
3： 对于任意一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
4: 具有n个结点完全二叉树的深度为[log2 n]+1([x]表示不大于x的最大整数)
5： 如果对一棵有n个结点的完全二叉树的结点按层级编号，对任意结点i有： 1. 如果i=1，则结点i是树的根。如果i>1，则其双亲结点是[i/2] 2. 如果2i > n，则结点i无左孩子(为叶子结点)，否则其左孩子为2i 3. 如果2i+1 > n，则结点i无右孩子，否则其右孩子为结点2i+1
二叉树的顺序存储结构
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置也就是数组的下标，要能体现结点之间的逻辑关系比较适合存储完全二叉树对于一般的二叉树，也可以按照完全二叉树存储，将不存在的结点用“^”占位
二叉链表
由一个数据域和两个指针域组成
二叉树的遍历
定义：二叉树的遍历是指从根结点出发，按照某种次序，依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次
前序遍历：先访问根结点，再前序遍历左子树，再前序遍历右子树
中序遍历：先中序遍历左子树，再访问根结点，再中序遍历右子树
应用：表达式树（四则混合运算）
后序遍历： 先后续遍历左子树，再后续遍历右子树，再访问根结点
树和森林
树和森林的前根遍历和后根遍历结果，与将树和森林转化为二叉树后的前序遍历和中序遍历结果相同
赫夫曼树(哈夫曼树)
路径：从树中一个结点到另一个结点的分支构成两个结点之间的路径
路径长度：路径上的分支数称为路径长度
结点路径长度：从该结点到根结点的分支数称为结点的路径长度
树的路径长度:从树根到每一个结点的路径之和称为树的路径长度
结点的WPL(带权路径长度)：从该结点到树根的路径长度与该结点上权的乘积
树的带权路径长度：树中所有叶子结点的WPL(带权路径长度)之和
赫夫曼编码
自平衡二叉查找树
左旋操作: 当传入一个二叉查找树P时，将它的右孩子定义为R，将R的左子树变为P的右子树，再将P改为R的左子树，最后将R替换P成为根结点，完成一次左旋操作
右旋操作：当传入一个二叉查找树P时，将它的左孩子定义为L，将L的右子树变为P的左子树，再将P改为L的右子树，最后将L替换P成为根结点，完成一次右旋操作
平衡二叉树(AVL)
平衡因子：二叉树上结点的左子树深度减去右子树深度值称为平衡因子
最小不平衡子树：距离插入结点最近的，且平衡因子绝对值大于1的结点为根的子树，称为最小不平衡子树
单旋转：只通过一次旋转使最小不平衡子树重新恢复平衡，当平衡因子为负时左旋，当平衡因子为正时右旋
双旋转：当最小不平衡子树的平衡因子与它的子树平衡因子符号相反时，就需要对结点先进行一次旋转使符号相同，再反向旋转一次
红黑树
性质：
1. 节点是红色或黑色。2. 根节点是黑色。3.所有叶子都是黑色。（叶子是NIL节点）4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
伸展树
多路查找树
概念：多路查找树，其每一个结点的孩子数可以多于两个，且每一个结点处可存储多个元素，由于它是查找树，所以元素之间存在某种特定的排序关系
B树
定义：B树是一种平衡的多路查找树，结点最大的孩子数目称为B树的阶
2-3树
2-3树是一颗多路查找树，每个结点都具有2个孩子（称为二结点）或3个孩子（三结点）
二结点：包含一个元素和两个孩子（或没有孩子）
三结点：包含一小一大两个元素和三个孩子（或没有孩子）
插入原理
情况一 空树：创建一个二节点作为根节点即可
情况三 三节点的叶子节点 ：虽然有的分了很多种情况，但他们都有一个本质，就是如果待插入位置如果是三节点那么就分解它，向上抛掷，如果上面也是三节点，那么仍然需要拆解，向上抛掷，…等到如果抛掷到根节点，如果根节点也是三节点那么说明，这个树高度不够存放这个结构，就需要分解头节点终止操作增加树的高度。因为在往上没有节点可以执行操作
删除原理，同删除一样分多种情况
2-3-4树
就是2-3树的概念扩展，包括了4结点的使用，一个4结点包含了小中大三个元素和四个孩子（或没有孩子）
B+树
一颗m阶B+树和B树的差异
有n棵子树的结点中包含n个关键字
所有叶子结点包含全部关键字信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序连接
所有分支结点可以看成索引，结点中仅包含有其子树中最大(或最小)关键字
优先队列(堆)
概念：堆是将一组数据按照完全二叉树的存储顺序，存储在一维数组中
分类
小顶堆：任意结点的值均小于等于其左右孩子值，并且最小值位于堆顶，即根节点处
大顶堆：任意结点的值均大于等于它的左右孩子，并且最大的值位于堆顶，即根节点处
图
无向
无向图：图中任意两顶点的边都是无向边，则称该图为无向图
无向完全图：在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图
顶点的度：顶点v的度是和顶点v相关的边的数目(记为TD(v))。边数等于各顶点度之和的一半
连通图：如果从顶点v到v'有路径，则称v和v'是连通的，如果图中任意两个顶点都是连通的，则称图是连通图
连通分量
无向图中的极大连图子图称为连通分量
连通分量要求：1.要是子图2.子图要是连通的3.连通子图含有极大顶点数4.具有极大顶点数的连通子图包含依附于这些顶点的所有边
生成树：无向图中连通且n个顶点和n-1条边的叫生成树
有向
有向图：图中任意两顶点的边都是有向边，则称该图为有向图
有向完全图：在有向图中，若任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图
入度：以顶点V为头的弧的数量称为，顶点V的入度(记为ID(v))
出度：以顶点V为尾的弧的数量称为，顶点V的出度(记为ID(v))
强连通图：是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
定理：一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次
强连通分量：有向图中的极大强连通子图称做有向图的强连通分量
有向树：有向图中一个顶点入度为0的，其余顶点入度为1的称为有向树
生成森林：一个有向图的生成森林由若干个有向树组成，含有图中所有顶点，但只有足以构成若干棵不相交的有向树的弧
简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图
稀疏图：有很少边或弧的图
稠密图：有很多边或弧的图
权：与图的边或相关的数称为权
网：带权的图通常称为网
路径长度：路径上边或弧的数目
回路(或环)：第一个顶点到最后一个顶点相同的路径称为回路
简单路径：序列中顶点不重复出现的路径
简单回路：出第一个顶点和最后一个顶点外，其他顶点不重复出现的回路
邻接矩阵
图的邻接矩阵就是用两个数组来表示图，一个一维数组存储图中顶点集合，一个二维数组(邻接矩阵)存储图中边或弧的关系
邻接表
邻接表是将数组和链表结合起来的存储方法
1.图中的顶点用一个一维数组存储，对于顶点数组中，每个元素还需要存储指向第一个邻接点的指针，以便查询边的信息
2.图中每个顶点Vi的邻接点构成一个线性表，由于邻接点个数不定，所以用单链表存储，无向图称为顶点Vi的边表，有向图称为以顶点Vi为弧尾的出边表
十字链表
1.顶点数组中每个元素包含，data，firstin，fristout
2.单链表中每个结点包含：tailvex，headvex，headlink，taillink
邻接多重表
边集数组
由两个一维数组组成，一个一维数组存储图中顶点集合，另一个数组存储边的信息，这个边数组的每个元素由一条边的起始下标，终点下标和权重组成
图的常用算法
图的遍历
最小生成树
最短路径
拓扑排序
关键路径
查找
顺序表查找
从表中第一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功
带哨兵的顺序查找
在查找表的尽头放置哨兵，免去每次比较值后还要判断下标是否越界
有序表查找
折半查找（二分查找）
前提线性表中记录是有序的，每次比较时取线性表的中间值比较，若相等则查找成功，若小于，则在线性表左半区查找，若大于则在线性表右半区查找，不断重复上述过程，直到成功，或所有查找区域无记录，查找失败
插值查找
插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找
斐波拉契查找
线性索引查找
定义:所谓线性索引就是将索引项集合组织为线性结构，也称索引表
稠密索引：稠密索引是指在线性索引中，将数据集的每个记录对应一个索引项，对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列
分块索引
倒排索引
散列表查找
定义：散列技术是在记录的存储位置和它的关键字之间建立一个确定的关系f，使得每个关键字key对应一个存储位置f(key)
散列函数构造方法
直接定址法
数字分析法
平方取中法
折叠法
除留余数法
随机数法
处理散列冲突的方法
开放定址法
再散列函数法
链地址法
公共溢出区法
并查集
并查集主要用于解决动态连通性问题
连通的三个性质
1、自反性：节点p和p是连通的
2、对称性：如果节点p和q连通，那么q和p也连通
3、传递性：如果节点p和q连通，q和r连通，那么p和r也连通
二维坐标映射到一维的常用技巧：x * n + y(m是棋盘的行数，n是棋盘的列数）
0 条评论
回复 删除
下一页
