导图社区 数据结构
- 3.0k
- 537
- 116
- 举报
数据结构
计算机考研必收藏!一张思维导图带你学懂计算机专业重要的专业基础课-数据结构树与二叉树知识点汇总。该导图详细著明了树的基本概念、二叉树、树与二叉树的相互转化、树与二叉树的应用、应用知识点。如果有帮到你，不妨点个赞吧!
编辑于2020-01-08 15:00:38- 相似推荐
- 大纲
数据结构
第一章：绪论
估计
时间复杂度：耗时的度量
空间复杂度：所需存储空间的度量
取最高次项：O(……)
第二章：线性表
线性关系：一对一
基本操作
初始化、销毁
查询：个体、整体
动态变化：插入、删除
存储结构
顺序存储：顺序表SqList
空间利用率不高 表的容量不可扩充，或扩充代价大（耗时） 插入和删除需要移动大量元素，耗时
类型定义
定长数组、当前长度
基址、当前长度、当前分配的容量
基本操作的实现
求表长、取第i个元素
随机存取，能直接找到第i个
按值查找
逐个比较
指定位置插入
先使待插入位置及后面的元素后移，腾出位置； 再插入。 注意： 溢出的判断，重新分配动态空间； 程序的健壮性
指定位置删除并返回
待删除位置之后的元素，从前到后逐个前移，覆盖。
移动操作很耗时间
链式存储：线性链表LinkList
类型定义
单链表
线性、单向、不连续存储 结点：数据域、后向指针域(*next) 动态空间
是否引入头节点？
有头节点：使空表成为实体，不必单独处理第一个元素
无头节点：空表时L=NULL
循环链表
从一个结点出发，单向遍历就能访问到所有节点：把末尾指针回指，循环链表 在O(1)时间内访问到头尾节点：修改数据结构，头尾指针表示
静态链表
不支持指针类型时
借用数组来表示链表，借用int来指示位置替代指针
vs 动态链表
双向链表
固定时间内找到某一结点的前驱和后继
双向链，插入删除注意每步的顺序
基本操作的实现
以带头结点的单链表为例 体会利用流程图和例子来分析设计算法
流程图： 画出初始状态、结果状态； 明确中间需要哪些步骤； 明确中间步骤的次序：根据步骤之间的依赖关系，是否会发生信息丢失；
指定位置插入
寻址：先找待插入位置之前的元素位置p p=L; j=0; while(p!=NULL && j<i-1){ p=p->next; j++; } 如果地址正确，则按步骤插入，注意步骤的先后 否则返回error
指定位置删除并返回
需要free掉该结点，故需要两个指针p、q，其一来指向待删除结点。 同样需要注意各步骤之间的次序。
寻址挺耗时
创建操作
头插法
新节点插入到线性表中第一个节点之前
尾插法
新节点插入到线性表最后一个节点之后
第三章：栈和队列
栈
仅在表尾（栈顶）进行插入或删除操作 后进先出
基本操作
初始化空栈、判断栈空、判断栈满
取栈顶元素
入栈
出栈
存储结构
顺序栈SqStack
顺序存储 通过重新分配空间realloc来实现空间扩充
类型定义
注意top的含义 顺序表第二种定义
栈底指针、栈顶指针(指向下一个空位置)、当前分配的存储容量
基本操作的实现
初始化：S.base=S.top
栈空：S.base==S.top
栈满：S.top-S.base==S.stacksize
入栈：*S.top++=e
出栈：e=*--S.top
链栈
链式存储 无法通过top随机存取，一般用的少 通过动态分配空间malloc来扩充 可以不必引入头节点
应用
数制转换
括号匹配的检验
行编辑程序
需要有字符来标识
迷宫求解
表达式求值、转换
表达式分类
中缀
需要比较算符优先级，并判断结合性！
前缀：波兰式
算符入栈后，判断其后是否连续入栈两个操作数，若是则求值并将整个过程看作一个操作数入栈； 需要递归 不需要比较优先级，也不需要判断结合性
后缀：逆波兰式
遇到算符时，立即计算，后将结果存入 不需要比较优先级，也不需要判断结合性
算符间优先级关系
大致思路
用两个栈，一个存操作符，一个存操作数 一定条件下操作符、操作数出栈运算后重新入栈 条件与表达式的形式有关
递归栈
递归：递推式+回归 减小问题规模，将原问题的求解分解为若干有重复操作的子问题的求解。 当满足递归结束条件后，逐级返回，依次获得较复杂问题的解
会画递归栈的工作状态
队列
只允许在一端（队尾）插入，在另一端（队头）删除 先进先出
基本操作
初始化空队列
入队列、出队列
判断队空、判断队满
取队头元素
存储结构
链式存储：链队列LinkQueue
线性链表
队头指针指向队头元素
队尾指针指向队尾元素
顺序存储：顺序队列SqQueue
类型定义
基址
头指针，指示队头元素
尾指针，指向队尾元素的下一个位置
均为int型，标识关于基址的偏移量
基本操作的实现
初始化空队列
Q.front=Q.rear=0;
入队列
判断是否队满；若未满则放入到Q.rear++的位置上
出队列
判断是否队空；若非空则Q.front++
队空
Q.front==Q.rear
队满
Q.rear==MAXQSIZE
链式和顺序都可以做成循环的
链式存储的，通过每次都使末尾指针回指 顺序存储的，通过取模
如不设置头节点，队满和队空条件冲突
设标志位，保存上次的动作
修改数据结构，增加当前队列长度
有维护代价
头结点
少用一个元素空间
应用
离散事件模拟
见代码
第四章：串
串：由零个或多个字符组成的有限序列 子串：串中任意个连续的字符组成的子序列 串用一对单引号括起来，但是这对单引号不属于串
基本操作
与线性表的相同
存储结构
定长顺序存储表示SString
会发生溢出，超过定长的部分舍去
类型定义
一般字符型数组
基本操作的实现
串联接
求从某位置开始的某长度的子串
堆分配存储表示HString
优化了上述两个基本操作
类型定义：基址+长度
基本操作的实现
串联接
求从某位置开始的某长度的子串
块链存储表示LString
类型定义
头指针、尾指针
当前长度
每个结点都是一个小数组+后向指针域
基本操作：方便对串中一小部分进行插入、删除处理
*模式匹配
子串的定位操作
有点类似状态机里的序列识别
匹配+回退
改进：不一定需要回退到首字母的后继，可以根据子串的特点，来求每个字母失配时需要返回的位置，
第五章：广义表
定义
LS=(a1,a2,...,an)
其中ai可以是单个元素（原子），也可以是广义表（子表）
意味着可以无限套娃
存储结构
头尾链表存储表示
每向下一层，就加一层括号，深度和层次有关，见p109
扩展线性链表存储表示
像是线性表扩展到高维，比头尾链表多了一个头结点，不占层数，见p110
第六章：树
一对多
定义和基本术语（见课本）
分层，根作为第一层，最大层数为树的深度
叶子=终端结点
孩子、双亲、兄弟、祖先、子孙
有序树：左右兄弟有顺序，不能互换
森林
二叉树
一对二
定义
二叉树不是有序树、二叉树不是树
二叉树的子树有左右之分，决定形状
性质
在二叉树的第i层上至多有2的i-1次方个结点
深度为k的二叉树至多有2的k次方-1个结点
最多时成为满二叉树
完全二叉树：最下层不一定满，但一定有
对完全二叉树从上到下，从左到右，从1到n编号，则有
i=1为根
非根结点，双亲的编号为|_ i/2 _|
结点i的左孩子是2i，右孩子是2i+1（不一定存在）
顺序存储，能在O(1)内找到任意结点
存储结构
*顺序存储
链式存储
二叉链表
data：当前结点数据
lchild：左孩子
rchild：右孩子
三叉链表：比二叉链表多一个指向双亲的
二叉树的遍历
顺序
以当前结点的访问次序命名，左子树总比右子树先访问
先序：中左右
中序：左中右
后序：左右中
递归
设计时常回溯+剪枝
层次遍历：从上到下，从左到右
用队列： 根访问并入队列； 若队列非空执行循环：出队头，左右孩子依次访问并入队列
两序列唯一确定一棵二叉树：必须有中序序列
应用：表达式树
*线索二叉树
把原先是null的指针利用起来，指向遍历序列中的前驱(l)/后继(r)
增设l/rTag域，标识该指针是指向孩子还是别的
树的存储结构
双亲表示法：线性表
结构体数组，结点中
一个域存储结点信息
另一个域存储当前结点双亲在数组中的存储位置
不方便：求结点孩子时需要遍历整个数组
孩子表示法：多重链表
类似于一组单链表
头结点存储一个结点的信息
表结点依次存储该结点从左到右的孩子在数组中的存储位置
孩子兄弟表示法：二叉链表
lchild指向当前结点的第一个孩子
rchild指向当前结点右侧的兄弟
将树转化为了二叉树
Huffman树及应用
定义
树的带权路径长度：树中所有叶子到根的带权路径长度和
Huffman树：带权路径长度和最小的二叉树
前缀编码：任何一个字符的编码都不能 是另一个字符的编码前缀
操作
构造Huffman树
选择两棵根节点权值最小的树（结点）作为新树的左右子树 新树的根节点没有数据，其权值为左右子树根节点权值和
Huffman编码：以出现频率为权，构造Huffman树，从根开始寻址，左0右1
第七章：图
多对多，注意时间复杂度
图的定义和术语（见图论课本）
图的存储结构
基本操作不难，难在对存储结构本身的理解
邻接矩阵：二维数组
n个顶，n*n的矩阵，存储权值/∞或1/0
容易求得每个顶点的度
邻接表
类似于树的孩子表示法，把孩子替换为邻顶
*十字链表
对有向图
类似于邻接表，结点中存的是弧的信息，结点指针域指向的是弧头/弧尾相同的
*邻接多重表
对无向图中十字链表的改进
每条边只对应一个结点
不要求算法，大概理解见课本示意图
图的遍历
深搜DFS
类似于树的先序遍历
一条线走到底，不行再逐层回退试探下一个
递归函数DFS：访问顶v；对v尚未访问的邻顶递归调用DFS
考虑到非连通图，一次递归只能访问完一个连通片 所以给递归函数加一个上层函数，增设visited数组，确保每条路都访问到
非递归函数DFS：使用栈，起点先入栈；每次出一个，入它的邻顶
入栈时访问
广搜BFS
类似于图的层次遍历
离出发点近的先访问，“层次”
非递归函数BFS：使用队列，起点先入队；每次出一个，入它的邻顶
入队列时访问
图的连通性问题
无向图的连通分量和生成树
前面DFS、BFS访问顶点时，顺便把弧/边收集了
*有向图的强连通分量
从一顶u向外做单向DFS，筛选出u能单向到达的顶 在筛选过程中，通过finished数组记录下第一个所有邻顶都被访问过的顶v
再以v为中心，向外逆向遍历刚才筛选出的所有顶点构成的顶点导出子图 将这些顶点划分成几组，得到的即为强连通分量
最小生成树
prim
通过边权选顶，逐个扩大顶集S
O(n²)
kruscal
选边，逐个填充无边的图
O(eloge)
*关节点和重连通分量
关节点：一顶的顶割集
重连通分量：没有关节点的连通分量
有向无环图（DAG图）及其应用
拓扑排序：由偏序（有先后顺序的关系）得到全序
例如已知A>C, B>C, 现在人为指定A>B>C
关键路径：从源点到汇点的最长路径
最短路径
Dijkstra
同样是逐步扩大顶集S
第九章：查找
查找表
同一类型的数据元素（或记录）构成的集合
常见操作
查询是否在表中
检索某元素存储的信息
关键字
唯一地标识一个记录
主关键字
标识若干记录
次关键字
插入
删除
分类
只做前两种“查找”操作
静态查找表
查找过程中涉及插入删除
动态查找表
查找的性能分析
平均查找长度
为了找到，需要和给定值进行比较的关键字个数的期望值 查找成功时的+查找不成功时的
静态查找表
顺序表或线性链表表示
不知是否有序
顺序查找
平均查找长度
等概率时的，为(n+1)*3/4
提高效率
访问频度表，把查找概率大的排的靠前些
有序表
等概率查找
折半查找
指针low、high、mid mid=|_(low+high)/2_| 每次与中间比较，决定替换上界还是下界
平均查找长度
|_log2(n)_|+1
不同的分割方式
斐波那契查找
插值查找
类似于线性的把待查找key映射到存储位置上，适用于线性均匀分布情况
不等概率查找
*静态树表
寻找查找过程判定树的最优情况
静态最优查找树
有别于Huffman树 Huffman树是为了两两之间编码不重叠，从而浪费了许多结点空间 而静态最优查找树的结点均为表中元素
构造时花费的时间代价太大
次优查找树
希望每个作为根的结点的左右子树的带权路径长度和近似均衡
索引顺序表
由索引表和存储表组成 存储表分块存储，块内无序块间有序
通过索引表实现块间的二分查找，定位到块； 再通过块内的顺序查找，定位到元素
动态查找表
表结构本身就是在查找过程中动态生成的，即查找失败时则插入。
二叉链表存储
二叉排序树
定义
从定义可以看出，二叉排序树具体啥样，与它的构造过程中各结点的插入顺序有关，如p227
若左子树非空，则其上所有节点的值均小于根节点的值
若右子树非空，则其上所有结点的值均大于根节点的值
左右子树均为二叉排序树
很有意思，先序遍历得到非递减有序序列，后序遍历得到非递增有序序列
操作
查找
类似于二叉排序树，逐层与根比较，决定向左走还是向右走
插入（创建）
如比较后应该向左走，但左边是空，说明没找到，就在那个位置插入
删除，不改变特性
分情况讨论（为了减少操作） 设待删除结点为*p，它的双亲为*f，不妨设*p为*f的左孩子
如果是右孩子，则后面的操作也要相应变化
*p为叶子节点
直接删去
*p只有一棵子树
令*p的子树直接成为双亲*f的子树
*p有两棵子树，详见p230
利用*p在关键字序列中的直接前驱*s1或直接后继*s2
因为容易知道，它们必然不可能同时有两棵子树
令*p的左子树代替*p的位置，成为*f的左子树; 令*p的右子树成为*s1的右子树;
令*s1替代*p（元素覆盖），然后在二叉排序树中删去原先的*s1
效率分析
性能
树高
与创建时的插入顺序有关
平衡二叉（排序）树
对二叉排序树的优化，减少查找失败的平均比较次数
定义
若非空则有后面性质
左子树和右子树都为平衡二叉树
左右子树的深度之差的绝对值不超过1
平衡因子：左子树深度-右子树深度
操作
查找：与二叉排序树相同
效率分析
O( log2(n) )
二叉排序树的平衡化
每次插入都及时平衡化，则因插入而失衡的情况必然只有后面四种； 假设a是离插入结点最近，且平衡因子绝对值超过1的祖先节点；
单向
单向右旋
单向左旋
双向
先左后右
先右后左
多叉链表存储
B-树
查找失败时比较次数相同
m阶B-树定义
有点类似多叉的排序树，指针指示的子树，数值夹在左右两边存储的数值之间。
每个节点至多有m棵子树
若不为叶子节点，则至少有两棵子树
除了根节点外的非终端节点至少有m/2取上整棵子树
叶子节点都出现在树的同一层上
操作
查找分析：分析B-树的深度
从定义
插入
若多则向上分裂
删除
无影响
临近兄弟可借，换下双亲中的一个
临近兄弟借不了，则合并，向上分裂的逆过程
一般仅考2-3树，即三阶B-树
每个结点至少有两棵子树，至多有三棵子树，也就意味着至少存储一个数，至多存储两个数
从例子中学习，如何分裂、合并
详见课本p242~p245，以及作业题9.14、9.15
哈希表
希望尽可能减少与关键字进行比较的次数
定义
哈希函数：存储位置和关键字之间的一一对应关系f
冲突：k1!=k2,f(k1)=f(k2)
处理冲突的方法g
Hash表：经过冲突处理后，把一组数据的关键字key转化为g( f( key ) )， 作为表中相应key的元素的存储位置
散列：上述映射的过程
哈希地址：上述方法最终得到的g
操作
构造哈希函数
直接定址：线性函数
平方取中
折叠：将关键字分割成位数相同的几部分，取这几部分的叠加和（舍去进位）
除留余数：取模
随机数
处理冲突
开放定址法：在原地址基础上加一个逐次变化的偏移量
线性探测再散列：1，2，3……
二次探测再散列：1²，-1²，2²，……
伪随机数
其它
查找
给定key值，求得哈希地址，定位到哈希表中该地址的元素
该位置上没有记录
查找不成功
有记录，比较key和该记录的关键字
相等，查找成功
不相等，根据造表时设定的处理冲突方法，寻找下一地址
有意思的是，此时左右也是平衡的
记不住啊啊啊！
看课本p234~p238，其实只需要学两种，也没必要记住
利用二叉树来表示查找过程