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