数据结构知识框架
2020-05-21 18:55:09 0 举报AI智能生成
数据结构知识框架
作者其他创作
大纲/内容
B树
平衡的多叉树
性质
根结点至少有两个孩子
每个非根结点至少有M/2（上取整）个孩子，至多有M个孩子
每个非根结点至少有M/2-1（上取整）个关键字，并且以升序排列
key[i]和key[i+1]之间的孩子结点的值介于key[i]、key[i+1]之间
所有的叶子结点都在同一层
B+树
性质
其定义基本与B树相同
非叶子节点的子树指针与关键字个数相同
非叶子结点的子树指针P[i]，指向关键字值属于[k[i],k[i+1])的子树
为所有叶子节点增加一个链指针
所有关键字都在叶子节点出现
搜索
和B树基本相同
特性
所有关键字都出现在叶子节点的链表中（稠密索引），且链表中的关键字恰好是有序的
不可能在叶子结点命中
非叶子节点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
更适合文件索引系统
B*树
在B+树的非根和非叶子结点之间再增加指向兄弟的指针
子主题 2
哈希
搜索（检索）
在数据元素集合中查找是否存在关键字等于某个给定关键字数据元素的过程
结果
成功
失败
搜索结构
用于搜索的数据集合
搜索的环境
静态环境
在执行插入和删除等操作的前后搜索结构不会发生改变
动态环境
为保持较高的搜索效率，搜索结构在执行插入和删除等操作的前后将自动调整，结构可能会发生改变
查找
静态查找
顺序表
从前往后依次遍历O（n）
有序顺序表
二分查找O（log(n)）
索引顺序表
动态查找
二叉树结构
二叉排序树
平衡二叉树
树结构
B树
B+树
哈希查找
每个元素的关键码和结构中一个唯一的结存储位置相对应
散列方法
插入和查找数据利用哈希函数求出存储位置再存放或者查找
哈希冲突
对于两个数据Ki和Kj（i!=j）,Ki!=Kj,但是有Hash(Ki)==Hash(Kj)
散列函数
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0-m-1之间
哈希函数计算出来的地址能均匀的分布在整个空间中
哈希函数应该比较简单
常见哈希函数
直接定址法
取关键字的某个线性函数为散列地址
优点：简单均匀
缺点：需要事先直到关键字的分布情况
使用场景：适合查找比较小且连续的情况
除留余数法
设散列中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key)=key%p,p<=m;将关键码转换成哈希地址
平方取中法
假设关键字是1234，平方就是1522756，再抽取中间的三位数227作为散列地址
折叠法
将关键字从左到右分成位数相等的几部分，然后将这几部分叠加求和，并按散列表长，取后几位作为散列地址
随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址
数学分析法
设有n个d位数，每一位肯能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，可将分布均匀的几位根据开散列的方式作为散列地址
散列冲突处理方法
闭散列法
一旦发生冲突，就去寻找下一个空的散列表地址，只要散列表足够大，空的散列地址总能知道
线性探查
插入时发现该位置的数据和要插入数据相等，不插入
产生冲突，依次查看其后的下一个桶，如果有空位置插入数据
二次探查
使用二次探查法，在表中寻找下一个空位置的公式是H(i)=(H0+i^2)%m,H(i)=(H0-i^2)%m
当表的长度为质数且转载因子不超过0.5时，新的表项一定能插入
双散列法
需要两个散列函数，当一个发生冲突时，利用下一个散列函数计算偏移量
载荷因子
a=填入表中的元素个数/散列表的长度
控制在0.7-0.8以下，超过0.8，查表时CPU缓存指数上升
开散列法
首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点组成一个向量，向量的元素个数与可能的桶数相同
布隆过滤器
当一个元素被加入集合时，通过k个散列函数将这个元素映射成一个位数组中的k个点，将它们置为1，检索时只要看是不是都是1，就可以，只要有一个零就不是，全是1，可能是
6.排序
概念
就是将一组杂乱无章的数据按照一定的规律（升序或降序）组织起来
数据表
待排序数据元素的有限集合
排序码
通常数据元素有多个属性域，其中有一个数据域可用来区分元素，作为排序依据，该域即为排序码
如果在数据表中各个元素的排序码互不相同，这种排序码称为主排序码
排序算法的稳定性
两个元素R[i]R[j],它们排序码K[i]==K[j]，且在排序之前，元素R[i]在R[j]之前，元素在R[i]和R[j]的顺序不变
常见排序算法
插入排序
直接插入排序
插入到已排序序列中，先找位置，然后将位置之后得元素后移
稳定
希尔排序
缩小增量排序
选择排序
选择排序
每次把最小的元素换在最前面
锦标赛排序
一直两两比较找出获胜者，将这个不再比较，其他继续两两比较，取得获胜者，一直循环
不稳定
堆排序
升序创建大堆，否则创建小堆
不稳定
交换排序
冒泡排序
稳定
依次比较相邻两个元素，不满足条件交换
快速排序
取一个基准值将比它小得放在左侧，大的放在右侧。左右两部分递归取基准值继续分
归并排序
归并排序
将待排序的序列分成两个等长的子序列，然后将它们合并成一个序列
非比较排序
计数排序
基数排序
图
由顶点集合及顶点间关系组成的一种数据结构
顶点和边
顶点
图中结点称为结点
边
顶点与顶点之间有一条边
图的分类
有向图
在有向图中，顶点对<x,y>是有序的<x,y><y,x>是不同的两条边
无向图
(x,y)(y,x)是一条边
完全图
在有n个顶点的无向图中，若有n*(n-1)/2条边，即任意两个两个顶点之间有且只有一条边
在n个顶点的有向图中，若有n*(n-1)条边，即任意两个顶点之间有且仅有方向相反的边
邻接结点
在无向图中G中，若（u,v）是E（G）中的一条边，则称u和v互为邻接顶点，并称（u，v）依附于顶点u和v
在有向图G中，若<u,v>是E（G）中的一条边，则称顶点u邻接到v，顶点v邻接自顶点u，并称边<u,v>与顶点u和v相关联
顶点的度
与它相关联的边的条数
在有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点v的入度是以v为终点的有向边的条数，记做indev(v)顶点v的出度是以v为起始点的有向边的条数记做outdev（v）
无向图的度等于入度和出度 dev(v) = indev(v) = outdev(v)
路径
在图G=(V,E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到vj的顶点序列为从顶点vi到顶点vj的路径
权
边附带的数据信息
路径长度
对于不带权的图，一条边的路径长度是指该路径上的边的条数
对于带权的图，一条路径的长度是指一条路径的路径长度是指该路径上各个边权值的总和
简单路径与回路
如路径上各个顶点 均不重复，则称这样的路径是简单路径，若路径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环
子图
设图G={V,E}和图G1={V1.E1},若V1属于V且E1属于E，则称G1是G的子图
连通图
无向图中，两个顶点之间有路径就是连通的，任一对顶点之间都是连通的则称这个图是连通图
强连通图
在有向图中，任意一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj到vi的一条路径
生成树
一个连通图的最小连通子图称作该图的生成树，有n个顶点的连通图的生成树有n个顶点和n-1条边
图的存储结构
邻接矩阵
邻接表
无向图
有向图
图的遍历
深度优先
广度优先
连通分量
当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索或广度优先搜索算法无法遍历图的所有顶点，而只能访问到该节点所在的最大连通子图的所有顶点，这些顶点构成一个连通分量
最小生成树
准则
只能使用图中的边来构造最小生成树
只能使用恰好n-1条边来连接图中的n个顶点
选用的n-1条边不能构成回路
贪心算法
在问题求解时，总是做出当前看起来最好的选择，也就是局部最优解
Kruskal算法
每次找一条具有最短权值且不再同一连通分量上的边加入生成树
prime算法
挨着找
单元最短路径
从在带权图的某一顶点出发，找出一条通往另一个顶点的最短路径，最短也即是沿路径各边的权值和最小
1.初识数据结构
概念
数据
描述客观事物的符号，是计算机中可以操作的对象，能被计算机识别，并输入给计算机处理的符号集合
数据元素
是组成数据的、有一定意义的基本单位，在计算机通常作为整体处理，也被称为记录
数据项
一个数据元素可以由若干个数据项组成。数据项是数据不可分隔的最小单位
数据结构形式
数据结构
是相互之间存在一种或多种特定关系的数据元素的集合
分类
逻辑结构
集合结构
线性结构
树形结构
图形结构
物理结构
顺序存储结构
链式存储结构
具体概念
逻辑结构
数据对象中数据元素之间的相互关系
集合结构
集合中的数据元素除了同属一个集合外，它们之间没有其他关系
线性结构
数据元素之间是一对一的关系
树形结构
数据元素之间存在的一种一对多的层次关系
图形结构
数据元素是多对多的关系
物理结构
数据的逻辑结构在计算机中的存储形式
顺序存储结构
数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
链式存储结构
数据元素存放在任意的存储单元里，存储单元可以是连续的，也可以是不连续的
逻辑结构是面向问题的，物理结构是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中
程序
算法
数据结构
算法
解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
算法特性
输入
算法有零个或多个输入
输出
至少有一个或多个输出
有穷性
算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且一个步骤在可接受的时间内完成
确定性
算法的每一个步骤都有确定含义，不会出现二义性
可行性
算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成
设计算法要求
正确性
可读性
健壮性
时间效率高
且空间使用率低
简单性
2.算法的复杂度
时间复杂度
空间复杂度
算法分析的分类
平均情况
任意输入规模的期望运行次数
最坏情况
任意输入规模的最大运行次数
最好情况
任意输入规模的最小运行次数，通常最好情况不会出现
时间复杂度--O渐进表示法
一般算法O(n)计算法
用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项系数存在且不是1，则去除与这个项相乘的常数
分治算法的时间复杂度计算
二分搜索算法的时间复杂度是lgN
M分搜索算法的时间复杂度为logM^N
递归算法的时间复杂度计算
递归总次数*每次递归次数
递归算法空间复杂度算法
N*每次递归空间大小
3.递归
递归定义
若一个对象部分的包含它自己或者用它自己给自己定义，则称这个对象是递归的
递归的过程
一个过程直接或间接的调用自己
递归的思想
把问题分解成规模更小的具有与原来问题具有相同解法的小问题
递归条件
缩小问题规模，使新问题与原问题具有相同的解决方式
设置递归的出口
递归分类
数据结构递归
问题解法递归
递归调用栈
尾递归
递归调用返回的结果总被直接返回
尾递归的本质
将单次计算的结果缓存起来，传递给下一次调用，相当于自动累积
时间复杂度
递归总次数*每次递归次数
回溯法
基本思想
迷宫算法
递归的优缺点
优点
递归在解决某些问题的时候使得我们思考的方式的以简化，代码也更加简练，容易阅读
缺点
递归的实质就是自己调用自己，而函数的调用开销是很大的，系统要为每次函数调用分配空间存储空间，并将调用点信息压栈，而在函数的调用结束后，还要释放空间，弹栈恢复断点，如果递归方案的复杂度
4.栈
栈的概念
一种特殊的线性表，只允许从一端插入和删除数据
特点：后进先出
顺序栈
顺序堆栈和书序表数据成员相同 ，不同之处，顺序堆栈的入栈和出栈操作只允许对当前栈顶进行
共享栈
一个数组实现两个栈
原理
既然是两个栈共享一段空间，向中间靠拢，数组两端表示两个栈的栈底，栈顶一直向中间靠近
应用场景
两个栈空间需求有相反的关系，也就是一个增长一个缩短的场景
链式栈
头插头删
栈的应用
括号匹配
逆波兰表达式
迷宫算法
5.队列
只允许在一端插入数据，在另一端删除数据的特殊线性表
顺序队列
实现方式一
队头不动出队列时所有元素向前移动
实现方式二
出队列时，队头向后移动一个位置
假溢出现象
多次入队列、出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出
真溢出现象
最大存储空间已经存储满，继续进行入队列操作
循环队列
头尾相接的顺序存储队列就是循环队列
队列满队列空的判断
少用一个存储空间
队尾指针加一等于队头指针就是队列满的判断条件
判空条件是尾和头相等
设计一个标记flag
初始flag置为0，入队列成功flag=1，出队列成功flag置为0
队空条件rear==front&&flag==0,
堆满条件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
线索
结点中指向前驱或者后继结点的指针
线索二叉树
二叉树的结点加上线索的二叉树
对二叉树按照某种方式（前序、中序、后序）遍历使其称为线索二叉树的过程称为按照什么方法对二叉树进行线索化
堆
堆的概念
把所有的元素按照完全二叉树的方式存储在一个一维数组中并满足Ki<=K2*i+1且Ki<=K2*i+2（Ki>=K2*i+1且Ki>=K2*i+2）,这个堆称为最小堆（最大堆）
堆的分类
小堆
任一节点的关键码均小于它左右孩子的关键码，位于堆顶结点的关键码最小
大堆
任一结点的关键码均大于它左右孩子的关键码，位于堆顶结点的关键码最大
堆的性质
如果i=0，结点i是根结点，没有双亲结点，否则结点i的双亲结点为（i-1）/2
如果2*i+1>n-1,则结点i无左孩子，否则结点i的左孩子为节点2*i+1
如果2*i+1>n-1,则结点i无左孩子，否则结点i的左孩子为节点2*i+2
堆的创建
从上向下调整
堆的插入
堆的删除
堆的应用
优先级队列
Huffman树
概念
路径
路径长度
把带权路径长度最小的树叫做Huffman树
构造huffman树
构造n棵只有根结点的二叉树森林，每棵二叉树都只有一个带有权值的根结点
重复以下步骤，直到F中只剩下一棵树
在二叉树森林中选最小的两个，作为左右子树构建一棵新的二叉树，新二叉树的根结点的权值为左右子树根结点的权值之和
在原来二叉树森林里删除这两棵二叉树
把新的二叉树加入二叉树森林
huffman编码
编码
在数据通信中经常把传输的文字转换成二进制字符0和1组成的二进制串，这叫做编码
等长编码
不等长编码
文件压缩
二叉搜索树
性质
如果左子树不为空，则左子树上所有节点的值都小于根结点的值
它的右子树不为空，则右子树上所有节点的值都大于根结点的值
它的左右子树也分别为二叉搜索树
操作
搜索
若根结点不为空
根结点key==要查找的key，返回true
根结点key>查找key，在其左子树查找
根结点key<查找key，在其右子树查找
否则返回false
插入
首先检测这个节点是不是已经存在，要是存在不插入
否则将元素插入到找到的位置
删除
首先判断是否在树中，没有直接返回
有的情况
要删除的节点没有孩子节点
直接删除该结点
要删除的节点只有左孩子
删除该结点并使被删除结点的双亲结点指向被删除结点的左孩子结点
要删除的节点只有右孩子
删除该结点并使被删除结点的双亲结点指向被删除结点的右孩子结点
要删除的节点有左、右孩子结点
在它的右子树中寻找中序下的第一个结点（关键码最小），用它的值填补到被删除节点中，再来处理该结点的删除问题
二叉搜索树性能分析
最坏情况下，平均查找长度为O(n)一般情况下平均长度为O(lgn)
AVL树
AVL树性质
它的左右子树都是AVL树
左子树和右子树高度之差（简称平衡因子）的绝对值不超过1（-1、0、1）
如果一棵树是高度平衡的，它就是AVL树。如果它有n个节点，其高度可保持在0(lgn)，平均搜索复杂度O(lgn)
平衡化旋转
左单旋
右单旋
左右双旋
右左双旋
AVL树的插入
如果是空树，插入后即为根结点，插入后直接返回true
如果树不空，寻找插入位置，若在查找过程中找到key，则插入失败直接返回false
插入节点
更新平衡因子，对树进行调整
AVL树的删除
被删除结点只有左孩子
parent的平衡因子为1或者-1，parent高度不变，则从parent到根所有结点高度均不变，不用调整
被删除结点只有右孩子
parent的平衡因子变成0，虽然以parent为根的子树平衡，其高度减1，但需要检查parent的双亲结点的平衡性
被删除结点左右孩子都有
变为删除中序遍历下的第一个结点q
结点parent的平衡因子为2或者-2，则较矮子数缩短，parent发生不平衡，需要进行平衡化旋转
parent较高子树的根为q
如果q的平衡因子为0，执行单循环恢复parent
如果q的平衡因子与parent平衡因子（正负）号相同，则执行一个单循环恢复parent
如果q的平衡因子与parent平衡因子（正负）号相反，则执行一个双旋转恢复parent
红黑树
概念
红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示结点的颜色，保证最长路径不超过最短路径的两倍，近似平衡
性质
每个结点不是红色就是黑色
树的根结点是黑色
如果一个结点是红色的，则它的两个孩子结点是黑色的（没有连续的两个红色结点）
对于每个节点，从该结点到其所有后代叶节点的简单路径上，均包含相同数目的黑色结点（每条路径上黑色结点的数量相等）
每个叶子节点都是黑色的（此处的叶子结点指的是空节点）
插入实现
若树为空，插入后需将新节点改成黑色
插入结点的父节点为黑色，不违反任何性质，直接插入
情况三
情况四
情况五
删除
运用
C++STL库--map/set multimap multiset
Java库
linux 内核
其他一些库
红黑树和AVL树的比较
0 条评论
下一页
