软考中级嵌入式——第九章 数据结构与算法

1.数据结构与算法概念1.1数据结构数据结构概述数据结构是计算机存储、组织数据的方式。简单来说就是如何把现实中的数据如数字、文字、图片合理地整理好放进计算机里并定义好对这些数据可以做什么操作。一个完整的数据结构定义包含三个层面逻辑结构 —— 数据之间抽象的数学关系。分为线性结构和非线性结构 比如一对一线性表、一对多树、多对多图。物理结构存储结构 —— 这些数据实际在内存中的存放形式。 比如顺序存储数组、链式存储链表、索引存储、散列存储。运算操作 —— 对数据可以进行的有效操作。 比如插入、删除、查找、排序、遍历等。一句话概括数据结构 数据元素 元素之间的逻辑关系 允许的操作。1.2线性结构定义线性结构是一个数据元素的有序集合其中存在唯一的第一个元素表头和唯一的最后一个元素表尾。除第一个元素外每个元素有且仅有一个直接前驱。除最后一个元素外每个元素有且仅有一个直接后继。简单理解数据元素像一条线一样串在一起呈现一对一的邻接关系。典型例子数组内存中连续的一块区域可以通过编号索引快速访问任意元素。链表元素在内存中随意存放每个元素都记录着下一个元素的位置。插入和删除非常快但查找较慢。栈后进先出LIFO就像一叠盘子只能从顶部取放。用于函数调用、撤销操作等。队列先进先出FIFO就像排队买票。用于任务调度、消息队列等。1.3非线性结构定义在非线性结构中数据元素之间不满足线性结构的约束即一个元素可能有多个直接前驱或多个直接后继。数据元素之间的关系呈现一对多或多对多。简单理解数据元素不再是单线连接而是呈现出分支或网状关系。典型例子哈希表通过一个“哈希函数”将键Key直接映射到内存位置实现快速查找、插入和删除。比如字典、缓存系统。树一对多有层级关系的数据结构像一个倒挂的树。最常用的是二叉树和它的平衡变种如红黑树用于文件系统、数据库索引等。二叉树的一个特殊应用是堆它是一棵完全二叉树常用于实现优先队列。图多对多由节点和连接节点的边组成可以表示复杂的网络关系如社交网络好友关系、地图导航路线。1.4算法的概念算法的特性有穷性执行有穷步之后结束且每一步都可在有穷时间内完成确定性算法中每一条指令都必须有确切的含义不能含糊不清输入0输出1有效性可行性算法的每个步骤都能有效执行并能在执行有限次后得到确定的结果。例如a0b/a就无效。伪代码是一种算法描述语言介于自然语言和编程语言之间不用拘泥于具体的实现2.线性表一对一2.1线性表概述线性表的概念n 个具有相同特性的数据元素组成的有限序列线性表常见的两种存储结构顺序存储结构顺序表、链式存储结构链表顺序表用数组实现存储方式在内存中开辟一块连续的空间把元素一个挨一个地放进去。就像电影院的一排连座座位号是连续的。特点快速随机访问只要知道元素的位置下标如第 5 个就能立刻访问时间复杂度 O(1)。插入/删除较慢在中间插入或删除一个元素时后面的所有元素都要向后或向前移动平均时间复杂度 O(n)。空间固定数组大小一般事先确定扩容需要整体搬移可能造成空间浪费或不足。适用场景频繁按位置访问、很少插入删除的场景例如存储一周气温、学生成绩表。链表用节点串联存储方式每个元素节点在内存中可以随意存放节点里除了数据还存着下一个或上一个节点的地址指针。就像寻宝游戏每张纸条写着下一个线索的位置。常见种类单链表每个节点只指向下一个节点。双向链表每个节点既有指向前一个的指针也有指向后一个的指针可以双向遍历。循环链表最后一个节点又指向第一个节点形成圆环。特点插入/删除很快只要知道要操作的位置比如已经拿到某个节点的指针修改几个指针就能完成时间复杂度 O(1)。随机访问慢要访问第 i 个元素必须从头一个个找过去时间复杂度 O(n)。空间动态需要多少节点就申请多少内存不会浪费但也需要额外空间存储指针。适用场景频繁插入、删除且不常按位置访问的场景比如 LRU 缓存、音乐播放列表、图论的邻接表。常见的线性表队列与栈2.2队列与栈队列Queue和栈Stack都是操作受限的线性表它们与普通线性表数组、链表的区别在于对插入和删除的位置做了严格限制。2.2.1栈Stack定义栈是一种后进先出Last In First Out, LIFO的线性表。可以想象成一叠盘子你只能从顶部取放最下面的盘子要等上面所有盘子都被拿走才能取出。基本操作push压栈在栈顶插入一个元素。pop弹栈删除并返回栈顶元素。peek / top只返回栈顶元素不删除。isEmpty判断栈是否为空。size返回栈中元素个数。实现方式基于数组简单高效但需要处理动态扩容。基于链表无容量限制插入删除都是 O(1)。时间复杂度所有核心操作push, pop, peek均为 O(1)。经典应用函数调用栈记录函数的返回地址和局部变量递归的基础。括号匹配编译器检查{ }、[ ]、( )是否成对。表达式求值中缀转后缀逆波兰表达式计算器实现。撤销操作Undo编辑器记录每次修改撤销时弹出最近操作。浏览器的后退按钮将访问过的 URL 压栈后退即弹栈。2.2.2队列Queue定义队列是一种先进先出First In First Out, FIFO的线性表。想象成排队买票先来的人先买到票后来的人排在队尾。基本操作enqueue入队在队尾插入一个元素。dequeue出队删除并返回队头元素。front / peek只返回队头元素不删除。isEmpty判断队列是否为空。size返回元素个数。实现方式普通数组实现需要两个指针front, rear但可能出现“假溢出”通常用循环队列解决。链表实现维护头指针和尾指针入队 O(1)出队 O(1)更常用。时间复杂度所有核心操作enqueue, dequeue, front均为 O(1)。经典应用任务调度操作系统的进程/线程就绪队列、打印机任务队列。消息队列生产者‑消费者模型如 RabbitMQ、Kafka。广度优先搜索BFS借助队列逐层访问图的节点。缓存淘汰策略FIFO 队列较少用更常用 LRU。键盘缓冲区敲击的按键按顺序被系统读取。2.2.3对比总结2.3广义表Generalized List广义表Generalized List 是线性表的一种推广形式。它与普通线性表的区别在于表中的元素既可以是单个元素原子也可以是另一个广义表子表。这种递归定义使得广义表可以灵活地表示各种复杂结构如树、图、稀疏矩阵等。一个广义表LS可以递归地定义为LS (a₁, a₂, …, aₙ)其中n ≥ 0。n是广义表的长度也就是最外层包含的元素个数当n 0时称为空表记作()。每个aᵢ可以是原子不可再分的基本数据元素通常用小写字母表示。子表另一个广义表用括号括起来。深度括号嵌套的最大层数原子的深度为0空表的深度为1例子A ()— 空表B (a, b)— 两个原子长度为 2深度1C (a, (b, c))— 第一个元素是原子 a第二个元素是子表 (b, c)深度2D (a, (b, (c, d)), e)— 嵌套深度为 3长度3E (a, E)— 递归表表内包含自身称为递归表基本操作取表头Head(LS)返回第一个元素不改变原表。取表尾Tail(LS)返回去掉第一个元素后的子表。求深度递归计算深度 1 max(各元素深度)。遍历递归遍历每个元素遇到子表则递归进入。2.4串String串String 是由零个或多个字符组成的有限序列通常称为字符串。它是线性表的一种特例——表中的每个数据元素都是一个字符。是取值范围受限的线性表仅由字符构成一般记为S a₁ a₂ … aₙn ≥ 0S是串名。aᵢ是单个字符属于某个字符集如 ASCII、Unicode。n是串的长度。当n 0时称为空串null string记作。2.5数组Array与矩阵数组是由相同类型的数据元素组成的有限序列这些元素在内存中连续存储通过下标索引 访问。数组是线性表的直接推广一维数组就是线性表二维及以上称为多维数组。特点随机访问给定下标可在 O(1) 时间内访问任意元素。存储连续性物理地址连续以行优先或列优先方式存储。元素类型统一所有元素占用的内存大小相同便于计算地址。静态或半静态传统数组大小固定C/C动态数组如 Python list、Java ArrayList可扩容。存储地址计算以二维数组为例:假设二维数组A[m][n]每个元素占L字节按行优先存储元素A[i][j]的地址 基地址 (i * n j) * L按列优先如 Fortran地址 基地址 (j * m i) * L3.树与二叉树一对多3.1树(Tree)树是 nn ≥ 0个节点的有限集合满足当 n 0 时称为空树。当 n 0 时有且仅有一个根节点Root。其余节点被划分为 mm ≥ 0个互不相交的子集 T₁, T₂, …, Tₘ每个子集本身又是一棵树称为根的子树。这个递归定义意味着树由根和若干子树构成子树也是树。基本术语节点包含数据元素及指向子树的指针度节点拥有的子树个数树的高度深度叶子节点子树为0的节点如4、5、7、8分支节点子树不为0的节点如1、2、3、6内部节点除了根节点之外的分支节点如2、3、6父节点子节点兄弟节点层次3.2二叉树Binary Tree定义二叉树是 nn ≥ 0个节点的有限集合它要么是空树n0要么由一个根节点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。与普通树的区别每个节点最多有两个孩子且左右子树严格区分即使只有一个孩子也要指明是左还是右。二叉树的重要特性第 i 层最多有 2^(i-1) 个节点i ≥ 1。深度为 k 的二叉树最多有 2^k - 1 个节点满二叉树时。对任何非空二叉树若叶子数为 n₀度为 2 的节点数为 n₂则 n₀ n₂ 1。具有 n 个节点的完全二叉树深度为 [log₂ n] 1。对完全二叉树按层编号,从1开始到 [log₂ n]1,每层从左到右则对任意节点i(1≤i≤n)有如果i1则节点i无父节点是二叉树的根如果i1,则父亲节点是 ⌊i/2⌋如果2in,则节点i为叶子节点无左子节点否则其左子节点是2i如果2i1n,则节点i为叶子节点无右子节点否则其右子节点是2i1节点 i 的左孩子为 2i若 ≤ n节点 i 的右孩子为 2i1若 ≤ n节点 i 的双亲为 ⌊i/2⌋特殊二叉树满二叉树所有分支节点都有左右孩子且所有叶子都在同一层完美二叉树完全二叉树对满二叉树从右向左、从下向上删除若干节点后得到的树。叶子只允许在最后两层且最后一层的叶子靠左排列堆完全二叉树且每个节点值 ≥ 子节点大顶堆或 ≤ 子节点小顶堆非完全二叉树二叉排序树左子树所有节点值 根节点值 右子树所有节点值递归满足二叉平衡树任意节点左右子树高度差 ≤ 1数的表示方法括号表示法广义表形式(A(B,C(D,E)))文氏图用包含关系表示子树凹入法用缩进表示层次树形结构图最常用二叉树的遍历核心操作前序遍历根 → 左 → 右 1,2,4,5,7,8,3,6中序遍历左 → 根 → 右 4,2,7,8,5,1,3,6后序遍历左 → 右 → 根 4,8,7,5,2,6,3,1层次遍历从上到下从左到右 1,2,3,4,5,6,7,83.3堆Heap在数据结构中堆是一种特殊的完全二叉树大根堆任意节点的值 ≥ 其子节点的值 → 根节点是最大值。小根堆任意节点的值 ≤ 其子节点的值 → 根节点是最小值。在内存管理中堆是程序运行时用于动态内存分配的一块内存区域区别于栈Stack。4.图Graph多对多图由顶点Vertex和边Edge组成G (V, E)V非空顶点集合E边的集合每条边连接 V 中的两个顶点图的存储方式邻接矩阵表示法用一个n阶方阵R来存图中各节点的关联信息其矩阵元素Rij1表示有边0无边。优点判断边是否存在 O(1)适合稠密图。缺点空间 O(V²)稀疏图浪费内存。邻接链表表示法首先把每个顶点的邻接顶点用链表表示出来然后用一个一维数组来顺序存储上面每个链表的头指针。优点空间 O(VE)适合稀疏图。缺点判断边是否存在需要遍历列表平均 O(V) 但可优化。图的遍历深度优先DFS沿着一条路走到黑然后回溯。使用栈递归或显式栈。时间复杂度 O(VE)邻接表或 O(V²)邻接矩阵。应用连通分量、拓扑排序、检测环、求解迷宫。广度优先BFS层层推进先访问距离近的顶点。使用队列。时间复杂度同上。应用无权最短路径、二分图检测、网络爬虫。5.查找算法五大查找查找Searching 是计算机科学中最基础、最频繁的操作之一。简单来说查找就是在一个数据集合中找出满足某种条件的记录。通常我们给定一个关键字Key然后在数据集中找到与该关键字相等的记录或其位置。5.1顺序表查找5.1.1顺序查找顺序查找不要求数据有任何顺序可以用于任意线性结构数组、链表等。步骤从第一个元素或最后一个开始。比较当前元素是否等于目标关键字。若相等查找成功返回位置或元素本身。若不等移动到下一个元素重复步骤2。若已到达末尾仍未找到则查找失败。5.1.2二分查找前提条件顺序存储结构如数组因为需要随机访问中间元素。元素按关键字有序排列通常升序降序也可需调整比较逻辑。核心思想初始化低位索引low 0高位索引high n-1。循环当low high时计算中间位置mid low (high - low) / 2向下取整。若arr[mid] key查找成功返回mid。若arr[mid] key说明目标在右半部分更新low mid 1。若arr[mid] key说明目标在左半部分更新high mid - 1。在查找过程中low逐步增加而high逐步减少如果highlow,则查找失败算法结束5.1.3索引顺序查找分块查找5.2数表查找5.2.1二叉排序树查找5.2.1.1二叉排序树二叉排序树的定义左子树所有节点值 根节点值 右子树所有节点值递归满足一棵二叉排序树也称二叉查找树要么是空树要么满足若左子树非空则左子树上所有结点的值均小于根结点的值。若右子树非空则右子树上所有结点的值均大于根结点的值。左、右子树本身也各是一棵二叉排序树。二叉排序树的性质对二叉查找树进行中序遍历即可得到有序的序列二叉排序树查找先将待查找的数据生成二叉排序树然后执行以下步骤若查找的关键字等于根节点的关键字查找成功。若查找的关键字小于根节点的关键字递归查找左子树。若查找的关键字大于根节点的关键字递归查找右子树。若子树为空则查找失败5.2.1.2二叉平衡树二叉平衡树AVL的定义任意节点左右子树高度差 ≤ 1二叉平衡树的意义数据在生成二叉排序树时最坏情况树退化成单链表相当于变成顺序查找最好情况树两边平衡查找效率最高因此做平衡化处理是很重要的二叉平衡树的意义所在5.2.1.3哈夫曼树Huffman Tree最优二叉树定义给定N个权值作为N个叶子节点构造一颗二叉树若该树的带权路径长度达到最小称这样的二叉树为最优二叉树也称哈夫曼树。哈夫曼树是带权路径长度最短的树权值较大的节点离根较近。路径长度从一个结点到另一个结点之间的分支数目。树的路径长度从根到每个结点的路径长度之和。权Weight赋予叶子结点的数值表示出现频率、概率等。带权路径长度WPL所有叶子结点的权值 × 该叶子到根的路径长度 之和。哈夫曼树给定 n 个权值作为 n 个叶子结点构造出的二叉树中 WPL 最小 的树。核心步骤将所有左、右子树都为空的作为根节点在森林中选取两棵根节点权值最小的树作为一棵新树的左、右子树且置新树的附加根节点的权值为其左右子树上根节点的权值之和从森林中删除这两棵树同时把新树加入到森林中重复2、3步骤直到森林中只有一棵树为止此树便是哈夫曼树应用场景对字符集中的字符进行编码和译码性质没有度为1的结点即所有非叶子结点都有两个孩子—— 严格的二叉树。如果有 n 个叶子结点则总结点数为 2n - 1。权值越大的叶子离根越近路径长度越短。WPL 最小 —— 最优前缀编码的基础。5.2.1.4 B树B-Tree定义一颗m阶的B树是一颗平衡的多路搜索树它或者是空树或者是满足下列性质的树树中每个节点至多有m棵树即最多含m-1个关键字若根节点不是叶子节点则至少有两颗子树即至少 1 个关键字除根之外的所有非终端节点至少有【m/2】棵子树向上取整即至少⌈m/2⌉-1个关键字所有叶子结点都在同一层即树是完全平衡的。结点内的关键字按升序排列且关键字K[i]将子树指针P[i]和P[i1]所指向的子树范围分开P[i]指向的所有关键字 K[i]P[i1]指向的所有关键字。k 个关键字K[0], K[1], ..., K[k-1]按升序排列K[0] K[1] ... K[k-1]。k1 个指针P[0], P[1], ..., P[k]分别指向孩子结点子树。排序后P[0],K[0], P[1],K[1], ... P[k-1],K[k-1], P[k]每个关键字K[i]就像一个“分隔符”它把左右两边的指针所指向的子树范围分开。对于指针P[i]除了最右边的P[k]它指向的子树中 所有结点的所有关键字 都 小于K[i]。对于指针P[i1]除了最左边的P[0] 它指向的子树中 所有结点的所有关键字 都 大于K[i]。因此K[i]严格介于P[i]子树的最大值和P[i1]子树的最小值之间。即P[0]指向的子树中所有关键字 K[0]K[0]P[1]指向的子树中所有关键字 K[1]K[1]P[2]指向的子树中所有关键字 K[2]...K[k-2]P[k-1]指向的子树中所有关键字 K[k-1]K[k-1]P[k]指向的子树中所有关键字B树B树的一种变型一个m阶的B树具有如下几个特征每个叶子节点中含有N个关键字和N个指向记录的指针并且所有叶子节点彼此相链接构成一个有序链表其头指针指向含最小关键字的节点每个非叶子节点中的关键字K[i]即为其对应指针P[i]所指子树中关键字的最大值所有叶子节点都处在同一层次上每个叶子节点中关键字的个数均介于【m/2】和m之间B 树内部结点和叶子都存数据适合频繁单点查找且希望减少树高。B 树数据全在叶子内部结点纯索引叶子链表支持高效范围扫描是数据库索引的主流选择。典型应用数据库索引尤其是 B 树但 B 树思想相同。文件系统如 NTFS、HFS、ext4 使用 B 树变种。内存索引如某些键值存储。5.3散列表查找5.3.1哈希查找5.3.1.1散列表概述定义是一种通过关键字直接访问内存位置的数据结构。它利用一个散列函数哈希函数 把关键字映射到表中的某个位置从而实现近乎 O(1) 的查找效率。基本思想已知关键字集合U最大关键字m设计一个函数Hash它以关键字为自变量关键字的存储地址为因变量将关键字映射到一个有限的、地址连续的区间T中这个区间就称为散列表散列查找中使用的转换函数称为散列函数。理想情况下每个关键字对应唯一地址查找时间复杂度为 O(1)。但实际中不同的关键字可能映射到同一个地址这就产生了冲突。散列表的组成散列表数组大小为m的连续存储空间通常下标从 0 到 m-1。散列函数h(key)将关键字映射到[0, m-1]范围内的整数。冲突处理方法当两个不同关键字映射到同一地址时如何解决。5.3.1.2冲突解决方法拉链法链地址法每个散列表位置对应一个链表或动态数组所有映射到该地址的记录都挂在链表中。优点不会溢出平均查找长度短删除方便。缺点需要额外指针空间缓存不友好。开放定址法当h(key)已被占用则按某种探测序列寻找下一个空闲位置。线性探测再散列h(key) ii1,2,… 模 m。优点简单缺点易产生“一次聚集”。二次探测再散列h(key) i²模 m。可缓解一次聚集但可能无法探测整个表。双散列再散列h(key) i * h2(key)。使用第二个散列函数效果较好