计算机考研数据结构知识点
2021-09-17 22:06:57 1 举报AI智能生成
数据结构知识点大纲
作者其他创作
大纲/内容
n个结点则为n阶矩阵
图：有边/弧为1，否则为0
网：有边/弧为权值，否则为∞
邻接矩阵(适用于稠密图)
数组(弧尾结点)+链表(邻接点)+个数
邻接表(适用于稀疏图)
图的存储结构
辅助用栈，结果不唯一
访问某节点，从该结点出发
沿某路径依次访问未被访问的结点
若有顶点未访问，则选取一个未访问结点出发
重复上述过程，直到无未被访问结点
过程
：深搜过程就是对搜索树先序遍历的过程
深度优先搜索
辅助用队列，结果不唯一
依次访问邻接点，再从邻接点出发
广搜过程就是对搜索树层次遍历的过程
广度优先搜索
图的遍历
实质上是带权无向图。最小生成树是权值之和最小的生成树，不唯一
特点：只与顶点个数n有关，与边的个数e无关，适用于稠密图
V为连通网顶点集，U为生成树顶点集，TE为生成树边集
U={v₀}，TE=∅
计算U到其他顶点的最小代价，将该顶点纳入U，边纳入TE
重复上一步骤，知道U=V
普利姆(Prim)算法
特点：只与边的个数n有关，与顶点个数e无关，适用于稀疏图
不构成环条件下，每次选最小的边(做题技巧，不要过程时使用)
克鲁斯卡尔(Kruskal)算法
时间复杂度： Prim O(n²)，Kruskal O(e log₂e)
最小生成树
两顶点之间带权路径长度最短的路径
初始化数组
vⱼ为当前所求最短路径终点，另求S∪{j}
修改此时从v₀出发到集合V-S上任意顶点vₖ最短路径的长度
若dist[j]+arcs[j][k]<dist[k]则令dist[k]=dist[j]+arcs[j][k]; path[k]=j
重复2、3、4步骤n-1次，知道S中包含全部顶点
Dijkstra算法
使用邻接矩阵A⁽⁰⁾、A⁽¹⁾、A⁽²⁾······、A ⁽ⁿ⁾
第n次计算从起点经过n-1个顶点到达某个顶点最小带权之和
若到某个顶点有更小的权值之和，则替换之前的值并修改路径
直到到达终点
Floyd算法
最短路径
有向无环图：一个有向图中不存在环，简称DAG图
AOV网：用DAG图表示一个工程，顶点为活动，有向边为优先级，这样的网络为AOV网
由一个有向无环图的顶点组成的序列，满足一下要求，则称该图的拓扑排序
若顶点A在B的前面，则图中不存在从B到A的路径
每个顶点只出现一次
要求：
拓扑排序
AOE网：用DAG图表示一个工程，顶点代表事件，边代表活动，这样的网络为AOE网
AOE网只有一个入度/出度为0的顶点，称为源点/汇点
整个工程完工需要多多长时间
哪些活动影响工程进度？
问题：
事件(顶点)：最早发生时间Ve(i)，最晚发生时间Vl(i)
整个工程完工的时间就是终点的最早发生的时间，关键路径就是路径长度最长的路径。
对顶点进行拓扑排序（*是任意前驱事件）
Ve(1)=0
计算Ve(j)
Vl(n)=Ve(n)
计算Vl(i)
算法：
关键路径
应用
图
顺序存储和链式存储，时间复杂度O(n)
按顺序逐个比较，直到找到或者找不到
成功ASL=(n-1)/2，失败ASL=n/2+n/(n+1)
顺序查找
仅适用于有序的顺序表，时间复杂度O(log₂n)
先从中间开始比较，比较一次抛弃一半元素逐渐缩小范围
ASL=log₂(n+1)+1
折半查找
索引顺序查找，顺序查找+折半查找
块内元素可以无序，但块之间必须有序
分块查找
阶：所有结点的孩子结点数的最大值
只能随机检索
n个关键字，m阶B树高度h：logₘ(n+1)≤h≤logₘ ₂[(n+1)/2]+1
每个结点最多有m棵子树
非叶根结点至少有2棵子树
除根结点以外的所有非终端结点至少有m/2(取上界)棵子树
非终端结点有n个关键字和n+1棵子树，关键字个数n：(m/2)-1≤n≤m-1
所有叶子在同一层，不含信息
B树
可以顺序查找和随机查找
每个分支结点至多m棵子树
非叶根节点至少有2棵子树
除根节点以外的所有非终端结点至少有m/2(取上界)棵子树
结点的子树个数与关键字个数均为m/2(取上界)
叶子结点包含全部关键字，且按顺序排列
B+树
B树和B+树
哈希(Hash)查找
散列表/哈希表：建立了关键字与存储地址之间的一种映射关系
散列函数/哈希函数：把关键字映射到其对应存储地址的函数
装填因子：α=n/m，n个记录，m个地址空间
散列表的平均查找长度与n和m不直接相关，而是取决于装填因子和处理冲突的方法
不可随意删除某个元素，否则会造成查找失败
线性探测法：易引起堆积现象，降低效率
二次(平方)探测法：避免堆积，但无法探测到所有单元
再散列法
伪随机序列
开放定址法
把所有同义词存放在一个线性链表中，散列表存放头指针
适用于经常插入和删除的情况
链地址法
冲突处理
散列查找
查找
时间复杂度O(n²)，空间复杂度O(1)
顺序存储和链式存储，稳定算法
直接插入排序
顺序存储，稳定算法
折半插入排序
插入排序
时间复杂度O(n¹˙⁵)，空间复杂度O(1)
顺序存储，不稳定算法
增量序列逐渐缩小到1
希尔排序
一次比较相邻元素，逆序则交换，重复n-1次
冒泡排序
时间复杂度O(nlog₂n)，空间复杂度O(log₂n)
顺序存储和链式存储，不稳定算法
选1个元素为轴从前向后、从后向前扫描，抓大放小，分成两部分后依次进行快排
快速排序
第i次排序在剩余待排记录选一个最小(大)的放在第i个位置。
比较次数为 n(n-1)/2
简单选择排序
时间复杂度O(nlog₂n)，空间复杂度O(1)
小顶堆堆顶为最小元素，大顶堆堆顶为最大元素
对具有双亲结点的结点从大到小编号做出以下调整
① 若孩子结点皆小于双亲结点，则该结点调整结束
② 若孩子结点大于双亲结点，则将最大的孩子结点与双亲结点交换
③ 对交换后的堆再次重复①②，直到出现①结束
堆的初始化
将堆顶元素与编号最后一个的元素交换后弹出
对堆进行初始化，并再次重复上述步骤，直到堆空结束
堆排序
时间复杂度O(nlog₂n)，空间复杂度O(n)
归并：两个或两个以上的有序表合成一个新的有序表
划分+排序（直接插入排序）
二路归并排序
时间复杂度O(d(n+r))，空间复杂度O(r)
不基于比较，稳定算法
最高位优先MSD
最低位优先LSD
基于关键字各位的大小进行排序，分为
采用“分配”与“收集”策略
对n个数据进行基数排序，每个数据基数为 r，有d位数字
一趟分配和收集用时n+r（分配用n，收集用 r），共需n趟
辅助空间用到 r 个队列
特点
基数排序
排序
线性结构、集合、树状结构、图状结构（后三种为非线性结构）
逻辑结构
顺序存储、链式存储、索引存储、散列存储/哈希存储
存储结构/物理结构
数据的运算
数据结构的内容
三元组：数据对象、数据关系、基本操作
抽象数据类型（例如：栈）的表示
O(1)＞O(log₂n)＞O(n)＞O(nlog₂n)＞O(n²)＞O(n³)＞O(n!)＞O(nⁿ)
时间复杂度和空间复杂度
绪论
用一组连续存储单元依次存储线性表的数据元素
插入 平均移动次数：n/2，时间复杂度：O(n)，需要移动元素
删除 平均移动次数：(n-1)/2，时间复杂度：O(n)，需要移动元素
按值查找 平均移动次数：(n+1)/2，时间复杂度：O(n)，顺序访问
按位查找 时间复杂度：O(1)，随机访问
基本操作
顺序表
线性表的链式存储
建立单链表：头插法(头结点之后)、尾插法(尾结点之后)
删除 时间复杂度：O(n)，不需要移动元素
查找 时间复杂度：O(n)，不需要移动元素，顺序访问
单链表
尾结点指向下一个节点的指针不是NULL，而是头结点
若常做操作在表头表尾，可对循环链表不设头指针而仅设尾指针，提高效率
循环链表
在单链表的机车上增加一个指向前驱结点的指针
双向链表
借用数组来描述链表(非顺序存储)
静态链表
链表
线性表
后进先出的线性表，抽象数据结构
栈的顺序存储(类似顺序表)，插入删除操作均在表尾
优点：便于多个栈共享存储空间和提高效率，且不存在栈满上溢
共享栈：栈底在共享空间两端，栈顶向空间中部延伸
用不带头节点的单链表实现，指针指向栈顶，所有操作均在栈顶完成
栈的链式存储
合法出栈个数：C(上标2n 下标n)/(n+1)
左括号则入栈
右括号，若匹配则弹出栈顶，不匹配则序列非法
遍历完毕，若栈非空则序列非法
括号匹配
中缀表达式转化为后缀/前缀表达式
1.按优先级对所有运算单位加括号
前缀：把运算符移到对应括号前
后缀：把运算符移到对应括号后
2.
3.去掉括号
简便做法
表达式求值
递归转化为非递归常使用栈来完成
栈
先进先出的线性表，队头删除队尾插入，抽象数据结构，
队列的顺序存储，两个指针分别指向队头队尾
队列的链式存储，两个指针分别指向头结点和尾结点
队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
空:Q.rront==Q.rear
满:Q.front==(Q.rear+1)%MaxSize
牺牲一个存储单元
空:Q.size==0
满:Q.size==MaxSize
增加记录个数的变量(Q.size)
空:Q.rront==Q.rear && tag==0
满:Q.rront==Q.rear && tag==1
增加tag标识
判空/满
循环队列
应用：树的层次遍历一般利用队列完成
队列
逻辑结构。线性表的推广，每个元素受到n个线性关系的约束
存储结构：多用顺序存储
目标：节约存储空间；方法：不存储0，多值相同存储一个
需n(n+1)/2个单元空间
元素aij与他的存储位置sa[k]的关系
i(i-1)/2+j-1 当i≥j
j(j-1)/2+i-1 当i＜j
k=
对称矩阵
需n(n+1)/2+1个单元空间
n(n+1)/2 当i＞j
(i-1)(2n-i+2)/2+j-i 当i≤j
上三角区，k=
i(i-1)/2+j-i 当i≥j
n(n+1)/2 当i＜j
下三角区，k=
三角矩阵
中心地带宽为d，非0元素(2d+1)*n-(1+d)*d个
元素aij与他的存储位置sa[k]的关系 k=2i+j-3
对角矩阵
利用三元组(行标，列标，值)存储
稀疏矩阵压缩后，失去了随机存取的特性
稀疏矩阵
应用：特殊矩阵的压缩存储
数组
栈、队列、数组
度：该结点的子结点个数，树中最大的度称为树的度
高/深度：叶子结点向上数为高度，根节点向下数为深度，最大高/深度为树的高/深度
有/无序树：树中结点的各子树从左向右是否有序
概念
n个结点的树，只有n-1条边
结点数=所有结点的度+1
度为m的树中第i层上至多有mⁱ⁻¹个结点(i≥1)
n个结点的m叉树最小高度为logₘ(n(m-1))+1（取上界）
结点为 i，双亲[i/2](取下界)，左孩子2i，右孩子2i+1
性质
树
满二叉树：深度为n，有2ⁿ-1个结点
完全二叉树：n个结点的完全二叉树中结点在对应满二叉树中编号1-n
二叉树第 i 层上至多有 2ⁱ⁻¹ 个结点
深度为n的二叉树至多有 2ⁿ-1 个结点
非空二叉树叶子结点数等于度为2的节点数+1
深度为 log₂(n+1)(取上界)
i 的双亲是i/2(取下界)
i 的左孩子是2i，若2i>n，则无左孩子
i 的右孩子是2i+1，若2i+1>n则无右孩子
n个结点的完全二叉树
顺序存储：用数组把编号 i 的结点存放在 i-1 处，适用于存储完全二叉树
用二叉链表存储n个结点的二叉树，共有n+1个空指针域
用三叉链表存储n个结点的二叉树，共有n+2个空指针域
链式存储(二叉链表)
存储结构
方法：从上至下、从左至右、利用队列
将根放入队列，若队列不空则取队头元素p
若p不空则访问，将其左右子树入列
循环直至队空
思路
层次遍历
先序遍历：根-左-右
中序遍历：左-根-右
后序遍历：左-右-根
先序/后序/层次+中序，可以确定唯一二叉树，先序+后序不唯一
二叉树的遍历
线索：利用空指针指向前驱或后继结点
lchild | LTag | data | RTag | rchild
0 lchild/rchild域指向左/右孩子
1 lchild/rchild域指向前驱/后继
LTag/RTag=
画线索二叉树：先写遍历序列，再画线索
线索二叉树
特点：左小右大
判别：中序遍历得到结果从小到大有序
与根比较大小，大则去右子树，小则去左子树
平均查找长度：(n+1)/2
插入：先查找，无插入节点再将其插入最后访问节点的孩子
如果是叶子结点，直接删除
如果左子树或者右子树为空：将左子树接到双亲上
如果左右子树都不空：借左子树最大节点替换被删除节点
删除
二叉排序树
平衡因子BF为该节点的左子树深度减去右子树深度
平衡二叉树的平衡因子只有1、0、-1
右单旋：左子树的左子树多1
左单旋：右子树的右子树多1
先左后右：左子树的右子树多1
先右后左：右子树的左子树多1
平衡化
构造平衡二叉树
平均查找长度：O(log₂n)
0，h=0
1，h=1
Nₕ₋₁+Nₕ₋₂+1，h≥2
n个结点的平衡二叉树的最少结点，Nₕ=
平衡二叉树
二叉树
数组指向双亲结点
找双亲快。但找孩子慢
双亲表示法
数组指向孩子结点
找孩子快。但找双亲慢
孩子表示法
便于转换为二叉树，找孩子快。但找双亲慢
孩子兄弟表示法
树的存储结构
树转化为二叉树，根节点没有右孩子
森林转化为二叉树，森林的第一棵树的根作为对应二叉树的根
先序遍历
中序遍历
后序遍历
森林的遍历
树、二叉树与森林的转化
一类带权路径长度最短的树
方法：每次取两个最小的树组成二叉树
结果不唯一，但带权路径长度都是最小的
哈弗曼树(编码)
树与二叉树
数据结构
收藏
0 条评论
回复 删除
下一页
