导图社区 2025数据结构
- 27
- 1
- 1
- 举报
2025数据结构
2025数据结构不仅涵盖了传统数据结构如线性表、栈、队列、树、图等的基本概念、存储结构及基本操作，还深入探讨了现代数据结构如散列表、堆、跳表等的高级应用。
编辑于2024-11-03 18:26:14- 数据结构
- 时间管理-读书笔记
时间管理-读书笔记，通过学习和应用这些方法，读者可以更加高效地利用时间，重新掌控时间和工作量，实现更高效的工作和生活。
- 设计史理解理论与方法⭐️（谢尔提·法兰2016）
本书是法兰教授的最新作品之一，主要阐明了设计史的来源、设计史现在的状况以及设计史的未来发展可能等三个基本问题。通过对设计史学科理论与方法的讨论，本书旨在促进读者对什么是设计史以及如何写作一部好的设计史等问题的深入认识与反思。
- 计算机组成原理
《计算机组成原理》涵盖了计算机系统的基本组成、数据的表示与运算、存储系统、指令系统、中央处理器（CPU）、输入输出（I/O）系统以及外部设备等关键内容。通过这门课程的学习，学生可以深入了解计算机硬件系统的各个组成部分及其相互之间的连接方式，掌握计算机的基本工作原理。
2025数据结构
社区模板帮助中心，点此进入>>
- 时间管理-读书笔记
时间管理-读书笔记，通过学习和应用这些方法，读者可以更加高效地利用时间，重新掌控时间和工作量，实现更高效的工作和生活。
- 设计史理解理论与方法⭐️（谢尔提·法兰2016）
本书是法兰教授的最新作品之一，主要阐明了设计史的来源、设计史现在的状况以及设计史的未来发展可能等三个基本问题。通过对设计史学科理论与方法的讨论，本书旨在促进读者对什么是设计史以及如何写作一部好的设计史等问题的深入认识与反思。
- 计算机组成原理
《计算机组成原理》涵盖了计算机系统的基本组成、数据的表示与运算、存储系统、指令系统、中央处理器（CPU）、输入输出（I/O）系统以及外部设备等关键内容。通过这门课程的学习，学生可以深入了解计算机硬件系统的各个组成部分及其相互之间的连接方式，掌握计算机的基本工作原理。
- 相似推荐
- 大纲
2025数据结构
排序
基本概念
内部排序
插入排序
直接插入排序
复杂度
稳定性
折半插入排序
复杂度
稳定性
希尔排序
复杂度
稳定性
交换排序
冒泡排序
复杂度
稳定性
快速排序
复杂度
稳定性
选择排序
简单选择排序
复杂度
稳定性
堆排序
复杂度
稳定性
归并排序
二路归并排序
复杂度
稳定性
基数排序
复杂度
稳定性
外部排序
多路归并排序
实现原理
复杂度
比较次数
败者树
置换选择排序（生成初始归并段）
最佳归并树
查找
相关概念
查找表：用于查找的数据集合
静态查找表：只涉及查找操作
动态查找表：需要动态插入删除的查找表
关键字：数据元素中唯一标识该元素的某个数据项的值
查找长度：指需要比较的关键字次数
平均查找长度：所有查找过程中进行关键字比较次数的平均值
逻辑结构
线性结构
顺序查找
一般顺序查找
效率
ASL成功=n+1/2
ASL失败=n+1
比较次数
成功：需进行n-i+1次
失败：需进行n+1次
优缺点
优点：对数据的存储没有要求，顺序存储或链式存储皆可，有序无序都可以使用；快速查找
缺点：当元素个数较大时，平均查找长度较大，概率低
有序顺序查找
效率
ASL成功=n+1/2
ASL不成功=n/2+n/n+1
比较次数
注意点
查找不成功的效率比一般的顺序查找好一些
有序顺序表的顺序查找线性表可以是链式存储，而折半查找只能是顺序存储
折半查找（二分查找Binary）
效率
ASL成功=log2（n+1）-1
时间复杂度：O（log2n）
比较次数
最多不超过树的高度「log2（n+1）］
若有n个关键字，则失败结点有n+1个，成功结点有n个
优缺点
优点：平均效率比顺序查找好
缺点：仅适合顺序存储结构，不适合链式存储，且要求元素按关键字有序排列
分块查找（索引顺序查找）：吸收顺序查找和折半查找的优点
效率
ASL=L1+L2=（b+1）/2+（s+1）/2=（s的平方+2s+n）/2s
优缺点
优点：缩小了块内查找的范围，故总体效率比顺序查找好
缺点：占用额外空间，增加了系统开销
树形结构
二叉排序树（二叉查找树）：左子树结点<根结点值<右子树结点值
非线性结构也有利于插入和删除
基本操作
删除：删除结点的同时保证二叉排序树的性质不丢失
1️⃣若删除结点是叶结点，则直接删除
2️⃣若删除结点z只有一棵子树，则让z的子树成为z父结点的子树，代替z的位置
3️⃣若结点z中有左、右两颗子树，则令z的直接后继（或直接前驱）代替z，然后删去这个直接后继（或直接前驱），转化成1️⃣、2️⃣的情况
效率
ASL成功=2.9
插入删除时间复杂度：仅需要修改指针来完成插入删除平均：O（logn）
查找时间复杂度：平均：若为平衡二叉树为O（logn）；最坏：若只有左子树/右子树为O（n）
平衡二叉树（AVL树）
定义左、右子树的高度差为平衡因子：左h-右h
可以为空树
基本操作
插入
LL平衡旋转
A的左孩子的左子树插入新结点，导致A的子树失去平衡
RR平衡旋转
A的右孩子的右子树插入新结点，导致A的子树失去平衡
LR平衡旋转
A的左孩子的右子树插入新结点，导致A的子树失去平衡
RL平衡旋转
A的右孩子的左子树插入新结点，导致A的子树失去平衡
构造
删除
若不平衡，则从结点w开始向上回溯，找到第一个不平衡的结点z；y为结点z的高度最高的孩子结点；x是结点y高度最高的孩子结点
查找
平均查找效率为O(logn)
红黑树
性质条件
性质：满足红黑性质的二叉排序树
每个结点只能是红、黑
根结点、叶结点、失败结点、虚构的外部结点、NULL结点都是黑色
不存在相邻的红色结点
对于每个结点，该结点到任意一个叶结点的简单路径上，黑色结点数量相同
结论1️⃣：从根到叶结点的最长路径不大于最短路径的两倍
结论2️⃣：有n个内部结点的红黑树高度h<=2log2（n+1）；黑高为h，内部结点最少有2的h次方-1个
结论3️⃣：新插入的结点颜色为红色
插入过程
多路平衡查找树（B-树）
m阶B树特性
树中结点至多有m棵子树，即至多有m-1个关键字
若根结点不是叶结点，则至少有2颗子树，即至少有1个关键字
除根结点外的所有非叶结点至少有「m/2】棵子树，即至少有「m/2】-1个关键字
基本操作
创建
插入
删除
B+树
散列结构
哈希表
图
图的基本概念：由顶点集V和边集E组成
图的名词解释
有向图/无向图
有向图：E是有向边的有限集合
无向图：E是无向图的有限集合
连通图/非连通图/极大连通图
连通图：若图中任意两点都是连通的 ｜E｜>=｜V｜-1 点少边多
非连通图：若图中任意两点都不是连通的；最多有C（2，n-1）条边
极大连通图：其是不被另外任何一个连通子图包含的子图，无向图中则称其为连通分量；有向图中则称其为强连通分量
连通分量/强连通分量
无向图中的极大连通图称为连通分量
有向图中的极大连通图称为强连通分量
子图/连通子图/生成子图
子图：图A的顶点集和边集都是另一个图B的顶点集和边集的子集，则称图A是图B的子图
连通子图：满足连通图和子图的定义
生成子图：若有图A的顶点集=图B的顶点集的子图A，则A就是B的生成子图
度/入度/出度
度：无向图中与该顶点相连边的条数
入度：有向图中以该顶点为终点的 边数目
出度：有向图中以该顶点为起点的边数目
边的权/网
边的权：边上代表某种含义的值
网：边上带有权值的图
路径/路径长度/简单路径
路径长度：路径上边的数目
路径：从一个顶点开始经过一系列边到达另一个顶点形成的顶点序列
简单路径：顶点不重复存在的路径
回路/简单回路
第一个顶点和最后一个顶点相同的路径成为回路或环
简单回路：除了第一个顶点和最后一个顶点重复出现，其余顶点不重复出现的回路
距离
路径的长度
生成树/生成森林/有向树
生成树：包含图中全部顶点的极小连通子图
生成森林：连通分量的生成树构成图的生成森林
图的形容词解释
连通/强连通
连通：在无向图中，顶点之间有路径存在称连通
强连通：在有向图中，有一对顶点⏺️相互之间都有路径🚧，则称此对顶点是强连通的
稀疏/稠密
稀疏：边数很少叫稀疏图
稠密：边数很多叫稠密图
简单/多重
简单：满足1️⃣、不存在重复边 条件 2️⃣、不存在顶点到自身的边，则称图为简单的
多重：图中某一对顶点之间的边数大于一条，又允许顶点通过一条边与自身关联
完全
完全：任意两顶点之间都存在边
n个顶点的无向完全图有n（n-1）/2条边
n个顶点的有向完全图有n（n-1）条边
存储结构
邻接矩阵法
用一个二维数组存储图中的信息（即各顶点之间的邻接关系），用一维数组来存储顶点的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵；以下是邻接矩阵的存储结构定义
具体实例
无向图
有向图
邻接矩阵相关结论
1、无向图的邻接矩阵一定是个对称矩阵（并且唯一）
2、关于度的结论
无向图中：顶点i的度=第i行或第i列非零且非∞的元素个数
有向图：顶点i的出度=第i行非零且非∞的元素个数。顶点i的入度=第i列非零且非∞的元素个数。
3、当边数e较小时（稀疏图），采用邻接矩阵比较浪费空间，稠密图采用邻接矩阵存储
4、很容易查找是否存在边，时间O（1），增删顶点和计算边的条数代价大
5、
邻接表法：顺序存储和链式存储
邻接表：指对图G中每个顶点建立一个单链表；以下是邻接表的存储结构定义
顶点表（头结点）：顶点域（存储顶点相关信息）+边表头指针（存储指向第一个邻接点的指针）
边表结点（边结点）：邻接结点域（存储与对应头结点邻接的顶点编号，即数组下标）+指针域（指向下一个边结点的指针）
实例
邻接表的相关结论
1、适用于稀疏图，极大节省空间
2、邻接表容易找出所有邻边，不容易确定在给定的顶点中是否存在边
3、关于度的结论
无向图的邻接表中：顶点的度等于该点对应的单链表中的边结点个数
有向图的邻接表中：顶点的出度等于该点对应单链表中的边结点的个数；入度则需要遍历整个单链表
4、图的邻接表表示不唯一
邻接多重表
无向图的的链式存储
实例
组成部分
顶点结点（头结点）
data域
firstEdge域
边结点
（mark）域
iVer域
iLink域
jVer域
jLink域
（info）域
十字链表
有向图的链式存储
实例
组成部分
顶点结点（表头结点）
data域
firstin域
firstout域
弧结点（边结点）
tailvex域
headvex域
hlink域
tlink域
（info）域
图的遍历
深度优先遍历
广度优先遍历
图的应用
最小生成树
性质
1、若图G中存在权值相同的边，则G的最小生成树不唯一
2、虽然可能最小生成树不唯一，但对应的权值之和是唯一的，而且是最小的
3、最小生成树的边数=顶点数-1=总度数
实现算法
prim算法
kruskal算法
最短路径
定义
带权路径长度：把从一个顶点到图中其余任意一个顶点的一条路径所经过边上的权值之和，定义为带权路径长度
问题
单源最短路径
BFS算法求单源最短路径
Dijkstra算法思想：设置顶点集合S并不断贪心选择地扩充这个集合
各顶点之间最短路径
Floyd算法求各顶点之间最短路径
拓扑排序
相关概念
有向无环图（DAG图）
构造案例
AOV网：通常用于需要先后顺序的场景
当且仅当满足以下条件称为拓扑排序
1、每个顶点出现且出现一次
2、若顶点A在序列中排顶点B的前面，则在图中不存在从B到A的路径
拓扑排序的实例
每轮选择一个入度为0的顶点并输出，然后删除该顶点和所有以它为起点的边
性质
算法
关键路径：完成一项工程的最小开销
相关概念
AOE网：常用于测算一个工程的完成时间
开始顶点（源点）
结束顶点（汇点）
关键路径的性质
关键路径的长度：从源点到汇点之间最长的路经
关键活动：关键路径上的活动
若网中有多条关键路径，减小所有的关键活动才能减小关键路径长度，从而缩短工期
只有所有进入某顶点的各有向边活动结束才能代表事件开始
关键路径的参量定义
事件
最早发生时间
最迟发生时间
活动
最早开始时间
最迟开始时间
时间余量
算法步骤
原始方法
简便方法
缩短工期分析
集合
并查集
存储结构
通常用树的双亲来表示，每个子集合以一棵树来表示
树的每个结点
树根结点的下标
根结点的双亲域为负数
基本操作
并查集的结构体
并查集的初始化
并查集的Find操作
并查集的合并操作
优化
压缩路径：查找路径上所有结点都直接挂根结点
代码
原理：每个集合用一棵树表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。 血的教训!!! 注意很多题目需要在合并时去最小值，若f数组存父亲值 f[y]=min(f[x],f[y]),f[x]=min(f[x],f[y]); 每次执行find操作，确实会让每个节点直接存根节点的值，之后查找的时间复杂度接近O(1)，但仅仅是接近，不一定全是1次找到，即之后查找要用find函数而不是直接f[]找。
树和二叉树
树是n个结点，n-1条边的有限集
1、树的根结点没有前驱，除根结点外所有结点有且仅有一个前驱
2、树中的所有结点都可以有零或多个后继
基本术语
K的亲戚关系
祖先
B
子孙
K是B的子孙
双亲
E
孩子
K是E的孩子结点
兄弟和堂兄弟
兄弟：L G的堂兄弟：E,F,H,I,J
度
结点的度：树中的一个结点的孩子个数
树的度：树中结点的最大度数
特殊结点
叶结点/终端结点
度为0的结点
分支结点/非终端结点
度大于0的结点
深度、高度、层次
深度
结点深度：结点所在的层次
树的深度：树中结点最大层数
层次
从树根开始定义，根结点为第一层，孩子为第二层，以此类推
高度
树的高度：树的结点的最大层数
结点高度：以该结点为根的子树高度
有序树和无序树
有序树
树中结点各子树从左到右都是有次序的不能互换
无序树
树中结点的各孩子无序，可以任意交换
路径
路径
两个结点之间所经过的结点序列
路径长度
路径上所经过的边的个数
森林
m棵互不相交的树的集合
树的性质
1、树的结点数n等于所有结点度数之和加一
2、度为m的树中第i层上至多有m的i-1次方个结点（i>1）
3、高度为h的m叉树至多有（m的h次方-1）/（m-1）
4、度为m、具有n个结点的树最小高度为「logm(n(m-1)+1)
5、度为m、具有n个结点的树最大高度h为n-m+1
6、度为m的树和m叉树的区别
度为m的树：至少有一个结点的度为m，一定有非空树，至少有m+1个结点
m叉树：允许所有结点度数都小于m，可以为空树
例题
二叉树
特殊二叉树
满二叉树
一颗高度为h，且有2的h次方-1个结点的二叉树
完全二叉树
高度为h、有个结点的二叉树，当且仅当每个结点的都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树
特点
若有度为1的结点，则最多只可能有一个
其叶结点只可能在最下面两层出现。出现在最下一层的叶结点，都依次排列在该层最左边的位置
若n为奇数，则每个分支结点都有左右孩子；若n为偶数，则编号最大的分支结点只有左孩子没有右孩子
高度为h的完全二叉树最少的结点个数（2的h-1次方-1）+1=2的h-1次方
二叉排序树
左子树小于根结点；右子树大于根结点；左右子树又各是一棵二叉排序树
平衡二叉树
树中任意一个结点的左子树和右子树的高度差的绝对值不超过1。
正则二叉树
树中的每个分支结点都有2个孩子，即树中只有度为0或2的结点
二叉树的性质
1、非空二叉树上的叶结点数等于度为2的结点的结点数加一，即n0=n2+1
2、非空二叉树的第k层最多有（2的k-1）次方个结点
3、高度为h的二叉树最多有（2的h次方-1个）结点
4、对完全二叉树按从上到下、从左到右的顺序依次编号1、2、…n
1、若i<=［n/2」，则结点i为分支结点，否则为叶结点，即最后一个分支结点编号为［n/2」
2、叶结点只可能在层次最大的两层出现
3、若有度为1的结点，则可能只有一个，且该结点只有左孩子没有右孩子；度为1的分支结点只可能是最后一个分支结点
4、一旦出现叶结点或只有左孩子的情况，编号大于n/2
5、n为奇数，则每个分支结点都有左、右孩子：n为偶数，则编号最大的分支结点（编号n/2）只有左孩子，没有右孩子，其余分支结点都有左右孩子
6、当i>1时，结点i的双亲结点的编号为［i/2」
7、如果结点i有左、右孩子，则左孩子编号为2i，右孩子编号为2i+1
8、结点i所在层次（深度）为［log2i」+1
5、具有n个结点的完全二叉树的高度为「log2（n+1）］或［log2n」+1
存储结构
基础定义
顺序存储
将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中
优缺点
优点
最大限度节省存储空间
利用数组元素下标值确定结点位置
缺点
空间利用率低
链式存储
二叉链表至少包含三个域：数据域，左指针域，右指针域
在含有n个结点的二叉链表中，含有n+1个空链域
双亲表示法
采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置
优缺点
优点：可以很快的得到每个结点的双亲结点
缺点：求结点的孩子时则需要遍历所有结点，效率较低
删除结点的方法
法1:直接将伪指针域设置为2，表示此结点不存在，弊端是结点只是看起来被删除，但还是占用空间，时间复杂度为o1
法2:将被删除结点从数组中移除，后续结点向前平移，时间复杂度为on
孩子表示
用一个数组来存储所有结点，但其每个结点内存储一个链表结点指针，指向其第一个孩子，n个结点就有n个孩子链表
孩子兄弟表示法
不借助数组，而借助于二叉链表作存储结构，与二叉树不同的是，左指针指向他的第一个孩子，右指针指向其下一个兄弟
优缺点
优点：可以方便实现树转化为二叉树的操作、易于查找结点的孩子
缺点：从当前结点查找双亲结点比较麻烦
基础算法
查找结点算法
删除结点算法
输出树高算法
统计结点数目算法
二叉树的遍历
先序
中序
后序
层次
线索二叉树：加上线索的二叉树
线索：具有n个结点二叉链表中，共有n+1个空指针，将n+1个空指针存放进指向其前驱和后继后 就叫做线索
先序线索二叉树
创建算法
遍历查找算法
先序遍历的第一个结点
先序遍历中特定节点的后继
先序遍历先序线索二叉树
中序线索二叉树
创建算法
中序线索二叉树递归算法构造（不带头节点）
中序线索二叉树递归算法构造（带头节点）
遍历和查找算法
中序遍历找结点后继的规律：若其右标志为1，则右链为线索，指示其后继，否则遍历右子树的第一个访问结点（右子树最左下的结点） 为其后继
中序遍历第一个结点和最后一个结点
找到特定结点的后继
找到结点的前驱算法
中序遍历中序线索二叉树算法
后序线索二叉树
创建算法
查找和遍历算法
后序遍历的第一个结点
后序遍历的后继结点
后序遍历后序线索二叉树
哈夫曼树/最优二叉树
定义：带权路径长度WPL最小的树
构造
性质
1、初始结点最终成叶结点，权值越小的结点到根结点的路径长度越大
2、构造过程中新建了n-1个结点，因此哈夫曼树结点数=2n-1
3、哈夫曼树不存在度为1的结点
哈夫曼编码
前提：没有一个编码是另一个编码的前缀，则称此为前缀编码，哈夫曼编码是基于哈夫曼树的最优前缀编码
绪论
基本概念
数据
数据是信息的载体，是描述客观事物的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
数据元素
数据元素是数据的基本单位
若干数据项组成一个数据元素
数据项是构成数据元素的不可分割的最小单位
数据对象
数据对象就是具有相同性质的数据元素的集合，是数据的一个子集
数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合
逻辑结构
指数据元素之间的逻辑关系
与数据的存储无关，独立于计算机
存储结构（物理结构）
数据的运算
数据类型
原子类型
其值不可再分
结构类型
其值可以再分成若干成分的数据类型
抽象数据类型
一个数学模型及定义在该数学模型上的一组操作
数据结构
逻辑结构
线形结构
一般线性表
受限线性表
栈
队列
串
线性表推广
数组
非线性结构
树形结构
一般树
二叉树
图状结构
有向图
无向图
集合
存储结构（物理结构）
顺序存储
链式存储
索引存储
散列存储
算法效率
时间复杂度
T(n)=O(f(n))
规则
加法规则
减法规则
常见时间复杂度
例题
线性表
逻辑结构
除第一个元素外，每个元素有且仅有一个直接前驱
除最后一个元素外，每个元素有且仅有一个直接后驱
特点
表中元素有限
表中元素具有逻辑上的顺序性，有其先后顺序
表中元素都是数据元素，每个元素都是单个元素
表中元素的数据类型都是相同的，每个元素都占有相同大小的存储空间
表中元素具有抽象性，即仅讨论元素之间的逻辑关系
存储结构
顺序表示
顺序表
线性表的顺序存储又称顺序表
特点
逻辑顺序和其存储的物理顺序相同
主要优缺点
优点
可以随机访问
存储密度高
缺点
插入和删除需要移动大量元素
顺序存储分配一段连续的存储空间，不够灵活
存储结构代码
静态分配
动态分配
基本操作
初始化
静态分配
动态分配
插入
时间复杂度
删除
时间复杂度
按值查找
时间复杂度
例题
链式表示
单链表
线性表的链式存储
优缺点
优点
插入和删除不需要移动元素
缺点
失去顺序表可随机存取的特点
浪费存储空间
存储结构定义
单链表的第一个数据结点之前附加的结点称为头结点
头指针和头结点的关系
头指针都始终指向链表的第一个结点（不带头结点的首元结点、带头结点的头结点）
头结点是带头结点的链表的第一个结点，此时首元结点则是下一个结点
不带头结点的链表，此时第一个结点称为首元结点
基本操作
初始化
不带头结点
带头结点
查找
按值查找
时间复杂度为0(n)
按序号查找
时间复杂度为0(n)
插入
前插
s→next= p→next
p→ next = s;
temp =p→data
p→ data = s→ data
S-data=temp
后插
s→ next =p→next
p→next=s
删除
删除结点＊p
q= p→next
p → data= p→ next → data
p→ next=q →next
free (q)
双链表
插入
前插法：
p->prior->next=q；q->next=p；q->prior=p->prior；p->prior=q；黄色部分不可颠倒顺序（不能断链）
后插法
删除
循环链表
循环单链表
判空条件是头结点的next域是否等于头指针L
有时循环单链表不设头指针而设尾指针
原因：设尾指针，r-→next即为头指针，插入元素仅用0(1)
带头结点、尾指针的单循环链表
寻找尾结点及尾结点的前驱结点所需时间最少
应用
操作/时间复杂度
删除首元素
删除末元素
首元素后插入
末元素后插入
带头结点
1头指针、1尾指针
O（1）
O（n）
O（1）
O（1）
1头指针、0尾指针
O（1）
O（n）
O（1）
O（n）
0头指针、1尾指针
O（1）
O（n）
O（1）
O（1）
不带头结点
1头指针、1尾指针
O（1）
O（n）
O（1）
O（1）
1头指针、0尾指针
O（n）
O（n）
O（1）
O（n）
0头指针、1尾指针
O（1）
O（n）
O（1）
O（1）
循环双链表
头结点的prior指针还要指向表尾结点
判空条件是其头结点的prior域和next域都等于头指针L
应用
操作/时间复杂度
删除首元素
删除末元素
首元素后插入
末元素后插入
带尾指针的双循环链表
寻找尾结点及尾结点的前驱结点所需时间为o（n）
带头结点的双循环链表
寻找尾结点及尾结点的前驱结点所需时间最少
1头指针、1尾指针
O（1）
O（1）
O（1）
O（1）
1头指针、0尾指针
O（1）
O（1）
O（1）
O（1）
0头指针、1尾指针
O（n）
O（n）
O（1）
O（1）
静态链表
静态链表就是用数组来描述线性表的链式存储结构
结束的标志：next==-1
顺序表和链表的对比
存取方式
顺序表
顺序存取/随机存取
链表
从表头开始顺序存取
在第i个位置存取
顺序表用一次访问
链表需从表头开始依次访问i次
查找、删除、和插入
按值查找
顺序表无序
均为o（1）
顺序表有序
顺序表可以采用折半查找 o（logn）
按序号查找
顺序表o（1）
链表o（n）
空间分配
栈
逻辑结构
栈顶
栈底
空栈
操作特性
后进后出
存储结构
顺序栈
采用顺序存储的栈
利用一组地址连续的存储单元存放自栈底到栈顶的数据元素
判断条件 (栈顶指针初始化为-1)
判空条件S.top ==-1
判满条件S.top ==MaxSize-1
栈长：S.top+1
基本操作
初始化
进栈
出栈
读栈顶元素
链栈
用链式存储的栈叫链栈
优点
便于多个栈共享空间
提高效率
不存在栈满上溢
便于结点的插入和删除
共享栈
利用栈底相对不变的特性，可让两个顺序栈共享一个一维数组空间栈底设在空间两端
TOP初始为1时
top0=-1时0号栈空，top1=maxsize时1号栈为空
top1-top0=1时，判断栈满
应用
表达式
算术表达式
后缀表达式求值
中缀表达式转后缀表达式
左优先原则
递归
斐波那契数列
递归转非递归
例题
队列
逻辑结构
先进先出
队头front
允许删除的一端
队尾rear
空队列
存储结构
顺序存储
队列
进队
rear值加1
出队
front值加1
假溢出：在data数组依然存在空位置时，却已经满足队列满的条件（出栈的元素位置空闲）
循环队列
从逻辑上把存储队列元素视为一个环
操作
当Q.front = Max Size-1再前进一个位置就自动到0
队首指针＋1: Q. front= (Q.front+1)% Max Size
队尾指针＋1: Q. rear = (Q. rear +1)% Max Size
初始化
队空
入队
出队
队空／队满判断条件
链式存储
同时有队头指针和队尾指针的单链表
基本操作
初始化
判队空
入队
出队
应用
层次遍历
缓冲区
CPU的资源竞争
双端队列
允许两端都可以进行插入和删除的线性表
数组
定义
n个相同类型的元素组成的有限序列
操作
初始化
销毁
存取元素
修改元素
存储结构
二维数组
一维数组
压缩存储：指为多个值相同的元素只分配一个存储空间、对零元素不分配空间
特殊矩阵的压缩存储
对称矩阵
一维数组对应的下标k=
i（i-1）/2+j-1
j（j-1）/2+i-1
三角矩阵
上三角矩阵
一维数组对应下标k=
（2n-i+2）（i-1）/2+（j-i）
n（n-1）/2
下三角矩阵
一维数组对应下标k=
i（i-1）/2+j-1
n（n-1）/2
三对角矩阵
下标对应关系
i=［（k+1）/3+1」
j=k-2i+3
一维数组下标k=2i+j-3
稀疏矩阵
三元组表
行数
列数
非零元素个数
串
串是一种特殊的线性表，数据呈线性关系
存储结构
定长顺序存储
每个串变量分配一个固定长度的存储区，即定长数组
堆分配
动态分配存储空间
块链
每个结点可以存一个或多个字符，称结点为块，整个链表称为块链结构
模式匹配
简单模式匹配
子串的定位操作称为串的模式匹配
暴力解
KMP算法
原理
实现
优化