[计算机科学]数据结构复习课件

数据结构复习课件数据结构课程简介课程发展历程课程重要作用考核重点难点数据结构作为计算机科学的核心基础课数据结构是程序设计的核心，直接影响程，自20世纪60年代以来不断发展完程序的执行效率和内存使用掌握合适善从最初的简单数组操作，到现代复的数据结构可以显著提升算法性能，是杂的平衡树和图算法，数据结构理论与成为优秀程序员的必备技能同时也是实践并重，为软件开发和算法设计奠定后续操作系统、数据库、编译原理等课了坚实基础程的重要前置基础数据结构基本概念数据与数据元素逻辑结构与物理结构数据是信息的载体，数据元逻辑结构反映数据元素间的素是数据的基本单位，数据逻辑关系，物理结构描述数项是数据元素的组成部分据在计算机中的存储方式理解这些概念间的层次关系两者相互独立又密切相关，是学习数据结构的基础，为同一逻辑结构可以有多种物后续复杂结构设计提供理论理实现方式，选择合适的物支撑理结构直接影响算法效率抽象数据类型ADT基本结构分类树形结构图结构数据元素间存在一对多的关系数据元素间存在多对多的关系••二叉树、多叉树有向图、无向图••线性结构集合结构堆、哈夫曼树网络、拓扑结构••数据元素间存在一对一的关系特点层次分明，有根节点特点任意两点可能相关数据元素间没有特定关系••线性表、栈、队列数学集合概念••字符串、数组元素地位平等••特点有唯一前驱和后继特点仅属于同一集合线性表逻辑结构基本概念结构特点线性表是具有相同数据类型的n线性表具有有穷性、同质性和序个数据元素的有限序列每个元偶性三大特点元素个数有限，素最多有一个前驱和一个后继，类型相同，且存在唯一的序列关体现了数据的线性排列特征线系第一个元素无前驱，最后一性表是最基本也是最重要的数据个元素无后继，其余元素都有唯结构，为其他复杂结构提供了基一的前驱和后继础实现方法线性表主要有顺序存储和链式存储两种实现方式顺序存储使用连续内存空间，支持随机访问但插入删除开销大链式存储使用指针连接，插入删除高效但不支持随机访问线性表——顺序存储存储原理使用一组连续的内存单元存储线性表的数据元素每个元素占用相同大小的存储空间，通过数组下标直接计算元素地址，实现O1时间复杂度的随机访问随机访问特性由于元素在内存中连续存放，可以通过基地址加偏移量直接定位任意元素这种特性使得顺序表在查找操作上具有明显优势，特别适合需要频繁访问元素的应用场景空间分配策略需要预先分配固定大小的连续内存空间当表长超过预分配空间时，需要重新分配更大空间并复制所有元素动态扩容通常采用倍增策略以摊销时间复杂度线性表——链式存储节点结构设计每个节点包含数据域和指针域两部分数据域存储实际数据，指针域存储下一个节点的地址这种结构使得节点可以分散存储在内存的任意位置，通过指针维持逻辑顺序链表遍历过程从头节点开始，通过指针依次访问每个节点，直到遇到空指针表示链表结束遍历是链表的基本操作，时间复杂度为On，是查找、插入、删除操作的基础插入操作原理在指定位置插入新节点需要修改相关指针先将新节点的指针指向后继节点，再将前驱节点的指针指向新节点插入操作的时间复杂度为O1，但定位插入位置需要On时间单链表基本操作链表创建与初始化创建空链表通常使用头节点技术，头节点不存储实际数据，仅作为链表的入口点初始化时头节点的指针域为空，表示链表为空头节点的使用简化了插入和删除操作的边界处理节点查找与定位按值查找需要从头节点开始逐个比较，按位置查找需要计数遍历查找操作的时间复杂度为On实现时要注意边界条件处理，如空链表和超出范围的位置高效插入删除实现插入和删除操作的关键是正确修改指针指向删除节点时要先保存被删除节点的地址以便释放内存插入时要注意指针修改的顺序，避免链表断裂这些操作充分体现了链表的动态特性链表反转算法链表反转是经典算法题，可以用迭代或递归实现迭代方法使用三个指针（前驱、当前、后继）逐个反转指针方向递归方法利用函数调用栈，代码简洁但空间复杂度较高循环链表与双向链表循环链表特点双向链表优势实际应用场景最后一个节点的指针每个节点包含前驱和循环链表常用于资源指向头节点，形成环后继两个指针域，可调度和游戏中的循环形结构遍历时需要以双向遍历虽然增处理双向链表广泛特别处理终止条件，加了存储开销，但提应用于浏览器的前进避免无限循环循环供了更灵活的访问方后退功能、编辑器的链表适用于需要循环式双向链表在删除撤销重做操作、LRU缓访问数据的场景，如操作时更高效，因为存算法等需要双向访操作系统中的循环队可以直接访问前驱节问的场景这些特殊列调度算法点而无需遍历链表结构极大地扩展了应用范围静态链表与顺序表对比静态链表特征物理存储差异使用数组模拟链表结构，每个数组元素包含数据和下一个元素顺序表元素在内存中连续存放，静态链表物理上连续但逻辑上的数组下标虽然物理上连续存储，但逻辑上仍保持链式结构通过下标链接动态链表节点可分散存储在内存任意位置这的特点适用于不支持指针的编程语言或内存受限的嵌入式系种差异直接影响了访问效率和内存利用率统顺序表支持随机访问，静态链表和动态链表只能顺序访问，但静态链表的优点是避免了动态内存分配的开销，缺点是空间利插入删除操作的复杂度不同用率可能较低，且表长受数组大小限制线性表综合问题有序表合并算法经典归并思想的应用时间复杂度分析线性时间Om+n最优解空间复杂度优化原地合并与额外空间权衡有序表合并是线性表应用的经典问题给定两个有序线性表，要求合并成一个有序表算法使用双指针技术，分别指向两个表的当前元素，比较大小后将较小元素放入结果表时间复杂度为Om+n，其中m和n分别是两个表的长度这个算法体现了线性表顺序访问的特点，是归并排序的基础操作在实际应用中，可以根据具体需求选择顺序存储或链式存储实现栈的基本定义LIFO特性本质抽象数据类型描述栈是限制在一端进行插入和删栈的ADT包括初始化、判空、除操作的线性表，遵循后进先入栈、出栈、取栈顶元素等基出Last InFirst Out原则这本操作每个操作都有明确的种特性使得栈天然适合处理需前置条件和后置条件，如出栈要逆序或递归的问题，如函数操作要求栈非空这种抽象定调用、表达式计算等场景义为不同实现方式提供了统一接口栈在程序设计中的重要性栈是程序运行时的基础数据结构，函数调用栈记录函数调用关系和局部变量编译器利用栈进行语法分析，操作系统使用栈管理进程状态理解栈的工作原理对深入掌握程序执行机制至关重要栈的顺序实现栈指针管理使用数组实现栈时，需要维护一个栈顶指针top指示当前栈顶位置指针可以指向栈顶元素或栈顶元素的下一个位置，两种方式在操作实现上略有差异溢出检测机制上溢overflow发生在栈满时继续入栈，下溢underflow发生在空栈时执行出栈程序必须在每次操作前检查这些边界条件，防止数组越界访问导致程序崩溃栈顶栈底标识栈底通常固定在数组下标0位置，栈顶位置随着入栈出栈操作动态变化通过top指针值可以快速判断栈的状态top=-1表示空栈，top=MAXSIZE-1表示满栈栈的链式实现O1O1入栈时间复杂度出栈时间复杂度链栈在表头插入新节点，无需移动其他元删除表头节点，操作简单高效素无限理论容量上限只受系统内存限制，避免栈溢出问题链栈使用链表实现栈结构，每个节点包含数据域和指针域栈顶对应链表头部，入栈操作即在链表头部插入新节点，出栈操作即删除头节点链栈的最大优势是动态分配内存，理论上不存在栈满的情况，只要系统有足够内存就可以继续入栈但是需要额外的指针空间开销，且动态内存分配比数组访问稍慢链栈特别适合栈深度无法预估的应用场景栈的应用场景举例栈在计算机科学中有广泛应用括号匹配利用栈的LIFO特性检查括号是否正确配对，遇到左括号入栈，遇到右括号与栈顶配对表达式求值使用操作数栈和操作符栈，根据优先级决定计算顺序函数调用栈记录函数调用关系，每次函数调用将返回地址和局部变量压栈，函数返回时出栈恢复现场递归算法的实现本质上依赖系统调用栈，理解栈机制有助于优化递归程序和避免栈溢出队列定义与基本操作入队操作出队操作新元素从队尾进入，队尾指针后移元素从队头离开，队头指针后移状态查询队头元素访问判断队列是否为空或已满读取队头元素但不删除队列是另一种重要的线性数据结构，遵循先进先出First InFirst Out原则队列有两个端点队头用于删除元素，队尾用于插入元素这种特性使得队列非常适合模拟现实中的排队场景，如打印队列、任务调度等队列的抽象数据类型定义了一组标准操作，保证了不同实现方式的一致性和可替换性循环队列实现循环利用数组空间将数组首尾相连形成环形结构模运算计算指针使用取模运算实现指针的循环移动判满判空条件设计通过指针关系或计数器区分满队和空队循环队列是队列的一种高效实现方式，解决了顺序队列的假溢出问题通过将数组首尾连接成环，使得队列空间可以循环使用关键技术是使用模运算来计算指针位置rear+1%MAXSIZE判断队列状态是循环队列的难点，常用方法包括牺牲一个存储单元区分满队和空队，或者使用额外的计数器记录元素个数循环队列在操作系统的进程调度、网络数据缓冲等领域有重要应用链式队列队列节点结构每个节点包含数据域和指针域，与单链表节点结构相同队列需要同时维护队头和队尾两个指针，以支持在两端进行不同操作出队操作实现删除队头节点，将队头指针指向下一个节点如果删除后队列为空，需要同时将队尾指针置空出队操作需要释放被删除节点的内存空间入队操作实现在队尾添加新节点，更新队尾指针指向新节点如果队列原本为空，需要同时更新队头指针入队操作需要动态分配新节点内存队列的实际应用操作系统调度进程调度队列按照先来先服务原则分配CPU时间片就绪队列、等待队列等都采用队列结构多级反馈队列调度算法使用多个优先级不同的队列，提高系统响应速度和吞吐量双端队列应用双端队列deque允许在两端插入和删除元素，兼具栈和队列的特性广泛应用于滑动窗口算法、LRU缓存实现等场景双端队列提供了更灵活的数据访问方式优先队列机制优先队列根据元素优先级而非进入顺序决定出队次序通常使用堆数据结构实现，在任务调度、图算法、事件模拟等领域发挥重要作用优先队列是队列概念的重要扩展串（字符串）的定义串的基本概念串的存储表示串是由零个或多个字符组成的有串的存储方式包括定长顺序存限序列，也称为字符串串中字储、堆分配存储和块链存储定符的数目称为串的长度，零个字长存储简单但可能浪费空间，堆符的串称为空串串是一种特殊分配动态分配内存但管理复杂，的线性表，但其操作特点与一般块链存储适合长串但访问效率较线性表有显著差异低不同存储方式适用于不同应用场景串处理基本操作串的基本操作包括求串长、串赋值、串比较、串连接、求子串、串插入、串删除等这些操作构成了串处理的基础，是文本编辑、信息检索、生物信息学等领域算法的重要组成部分串的模式匹配算法朴素模式匹配算法改进思路朴素算法（暴力匹配）是最直观的字符串匹配方法从主串的朴素算法的主要问题是信息利用不充分，匹配失败时丢弃了已第一个字符开始，依次与模式串进行比较如果匹配失败，主经比较过的信息改进的关键是避免不必要的回退，利用已匹串指针回退到下一个起始位置，模式串指针回到开头重新匹配的前缀信息直接跳转到合适位置继续匹配配这种思想催生了KMP算法、Boyer-Moore算法等高效字符串匹虽然算法思路简单易懂，但在最坏情况下时间复杂度达到配算法，它们通过预处理模式串获得跳转信息，显著提高匹配Omn，其中m和n分别是主串和模式串的长度当模式串中有效率大量重复字符时效率较低KMP算法详细分析Next数组构建Next数组记录模式串中每个位置的最长相等前后缀长度通过动态规划思想构建，利用已计算的信息递推求解Next数组的正确计算是KMP算法成功的关键，直接影响匹配过程的跳转效率匹配过程优化当匹配失败时，利用Next数组确定模式串指针的新位置，避免重复比较已经匹配的字符主串指针不回退，只有模式串指针根据Next数组跳转，这是KMP算法高效的核心原因复杂度分析优势KMP算法的时间复杂度为Om+n，相比朴素算法的Omn有显著提升空间复杂度为Om用于存储Next数组在实际应用中，特别是处理大规模文本时，KMP算法的性能优势更加明显字符串典型习题子串查找实现技巧除了KMP算法，还有Robin-Karp算法使用哈希函数快速比较，Boyer-Moore算法从右向左匹配提高效率不同算法适用于不同场景，需要根据文本特征和性能要求选择合适的方法理解多种算法有助于灵活应对各种字符串处理问题最长公共子串问题最长公共子串是比较两个字符串相似度的重要指标可以使用动态规划方法求解，构建二维数组记录不同位置的匹配长度后缀数组和后缀树等高级数据结构也可以高效解决此类问题字符串编辑距离编辑距离衡量两个字符串的相似程度，定义为将一个字符串转换为另一个字符串所需的最少编辑操作数动态规划是求解编辑距离的经典方法，在拼写检查、DNA序列分析等领域有重要应用数组应用及多维数组一维数组基础二维数组结构线性结构的连续存储按行优先或列优先存储••元素类型相同矩阵运算基础••随机访问O1图像处理应用•地址计算简单•地址映射公式稀疏矩阵优化高维数组扩展大量零元素的特殊处理三维及以上数组的表示••空间效率提升科学计算需求••计算复杂度降低复杂度快速增长••专门存储格式实际应用受限稀疏矩阵的压缩存储三元组表示法每个非零元素用行号,列号,值三元组表示，按行优先顺序存储在一维数组中这种方法简单直观，适合静态矩阵的存储和基本运算十字链表法每个非零元素结点包含行指针、列指针和值域，形成行链表和列链表的十字交叉结构支持高效的插入、删除操作，适合动态稀疏矩阵压缩存储优势显著减少存储空间，提高缓存命中率矩阵运算时只处理非零元素，大幅提升计算效率在大规模科学计算和机器学习中应用广泛树的基本概念节点与关系度与层次概念树由节点和边组成，节点间节点的度是其子节点个数，存在父子关系每个节点最树的度是所有节点度的最大多有一个父节点，可以有多值节点的层次从根开始计个子节点根节点没有父节算，根为第1层树的高度点，叶节点没有子节点这等于最大层次数，深度概念种层次化结构是树的基本特与高度相似但计算方式略有征不同树的结构属性树具有唯一路径性，任意两个节点间存在唯一路径n个节点的树恰好有n-1条边树的子树也是树，体现了递归结构特性这些性质为树的算法设计提供了理论基础二叉树定义与性质₂⌊⌋2^i2^h-1log n+1第i层最大节点数高度h树最大节点数n个节点的最小高度每层节点数呈指数增长规律满二叉树达到最大节点数完全二叉树达到最小高度二叉树是每个节点最多有两个子节点的树结构，分为左子树和右子树满二叉树每个分支节点都有两个子节点，所有叶节点在同一层完全二叉树除最后一层外其他层都满，最后一层从左到右连续这些特殊二叉树具有良好的性质，在堆、二叉搜索树等数据结构中广泛应用二叉树的性质为算法分析和存储设计提供了数学基础二叉树的存储表示顺序存储方式链式存储方式使用数组存储二叉树，根节点存储在下标1的位置对于下标每个节点包含数据域、左指针域和右指针域链式存储灵活动为i的节点，其左子节点在2i位置，右子节点在2i+1位置，父节态，不浪费空间，是二叉树最常用的存储方式可以方便地表⌊⌋点在i/2位置这种存储方式适合完全二叉树，空间利用率示任意形状的二叉树高三叉链表还包含指向父节点的指针，便于向上遍历线索二叉对于一般二叉树，顺序存储可能产生大量空闲位置，造成空间树利用空指针域存储遍历信息，提高遍历效率不同的链式存浪费但顺序存储支持通过下标直接计算节点关系，操作简单储方式适应不同的应用需求高效二叉树遍历算法先序遍历实现访问顺序为根节点-左子树-右子树递归实现简洁明了先访问当前节点，再递归遍历左子树和右子树先序遍历常用于复制树结构或输出带括号的表达式，体现了自顶向下的处理思路中序遍历特点访问顺序为左子树-根节点-右子树对于二叉搜索树，中序遍历得到有序序列，这是二叉搜索树的重要性质中序遍历在表达式求值、语法分析等场景中发挥重要作用后序遍历应用访问顺序为左子树-右子树-根节点后序遍历适合自底向上的计算，如计算目录大小、释放内存等操作在编译器中，后序遍历用于生成后缀表达式和计算表达式值非递归实现方法使用栈模拟递归过程，显式管理遍历状态非递归实现避免了函数调用开销和栈溢出风险，在大规模数据处理中更加稳定不同遍历方式的非递归实现复杂度不同，后序遍历最为复杂层次遍历与队列结合根节点入队访问队头节点初始化队列并将根节点加入从队列中取出节点并访问其数据子节点入队重复处理将当前节点的非空子节点依次加入队列继续处理队列中的下一个节点层次遍历按照从上到下、从左到右的顺序访问树中所有节点，也称为广度优先遍历算法使用队列作为辅助数据结构，充分体现了队列先进先出的特性层次遍历在求树的宽度、判断完全二叉树、打印二叉树等问题中非常有用相比深度优先的递归遍历，层次遍历提供了不同的视角和解题思路，在图论算法中也有重要应用二叉树的建立与还原唯一确定条件需要中序遍历加上另一种遍历根节点定位技术先序/后序确定根，中序划分子树递归分治思想将问题分解为左右子树的重构时间复杂度分析On²朴素算法，优化可达On由遍历序列重构二叉树是经典算法问题仅凭一种遍历序列无法唯一确定二叉树，必须结合中序遍历和另一种遍历序列算法核心是利用先序或后序遍历确定根节点，用中序遍历划分左右子树，然后递归处理优化方法包括使用哈希表快速定位节点在中序序列中的位置，将时间复杂度从On²降低到On这类问题训练了分治思想和递归算法设计能力二叉搜索树BST高效查找操作利用BST的有序性质，查找操作平均时间复杂度为Olog n从根节点开始，根据比较结果决定向左或向右子树搜索，直到找到目标节点或遇到空指针查找路径长度取决于树的高度插入节点算法新节点总是插入为叶节点，保持BST性质插入过程类似查找，找到合适位置后创建新节点插入操作可能改变树的形状，频繁插入可能导致树变得不平衡，影响查找效率删除操作复杂性删除操作最为复杂，需要考虑三种情况删除叶节点直接删除，删除只有一个子节点的节点用子节点替代，删除有两个子节点的节点需要找到前驱或后继节点替代，保持BST性质平衡二叉树（AVL树）性能评价分析四种旋转操作AVL树保证了最坏情况下Olog n的查找、插平衡因子定义当插入或删除操作破坏平衡时，需要通过旋入和删除时间复杂度相比普通BST可能退化平衡因子是节点左子树高度减去右子树高度转恢复平衡包括左旋、右旋、左右旋和右为链表的On复杂度，AVL树提供了稳定的性的值，AVL树要求所有节点的平衡因子只能是左旋四种基本旋转旋转操作在局部调整树能保证但平衡维护需要额外的旋转开销，-

1、0或1这个严格的平衡条件保证了树的结构的同时保持BST的有序性质，是AVL树自在插入密集的场景中可能不如红黑树高效高度始终为Olog n，确保各种操作的效率平衡的核心机制哈夫曼树与编码构建最优树数据压缩应用哈夫曼树是带权路径长度最小的二叉树构建过程使用贪心算法每次选择哈夫曼编码广泛用于数据压缩，如JPEG图像压缩、ZIP文件压缩等通过将权值最小的两个节点合并为新节点，新节点权值为两个子节点权值之和，重高频字符用短码表示，低频字符用长码表示，显著减少数据存储空间是信复直到只剩一个节点息论在计算机科学中的重要应用编码规则设计从根到叶的路径确定编码，左分支为0，右分支为1频率高的字符对应较短路径，获得较短编码哈夫曼编码是前缀码，任何字符的编码都不是另一个字符编码的前缀，保证解码唯一性树的实际应用题树结构在实际应用中无处不在家谱管理系统使用树表示血缘关系，支持祖先查询、后代统计等操作组织架构图用树表示公司层级关系，便于权限管理和信息传递文件系统的目录结构是典型的树应用，支持路径导航和空间统计表达式树将数学表达式转换为树结构，便于编译器进行语法分析和代码生成这些应用展示了树结构在解决层次化问题中的强大能力m叉树与森林m叉树结构特点森林概念与操作与二叉树的转换m叉树允许每个节点最多有m个子节点，是森林是若干棵互不相交的树的集合森林任何树和森林都可以转换为二叉树表示二叉树的推广在决策树、语法分析树等可以通过添加虚拟根节点转换为树，也可转换规则左指针指向第一个子节点，右应用中，m叉树提供了更灵活的表示方式以通过删除树根得到森林森林的遍历可指针指向下一个兄弟节点这种转换保持存储时可以使用子节点数组或链表表示以转换为对应二叉树的遍历问题了原有的结构关系，使得可以用二叉树算法处理一般树问题图的基本概念顶点与边的关系路径与连通性图由顶点集V和边集E组成，记作路径是顶点序列，相邻顶点间存G=V,E边表示顶点间的关系，在边简单路径不重复经过顶可以是有向边或无向边顶点的点，环是起点和终点相同的路度是与其相关联的边数，有向图径连通图中任意两个顶点间都区分入度和出度图是比树更一存在路径，强连通有向图中任意般的数据结构，允许任意两个顶两个顶点间都存在双向路径连点间存在边通性是图的重要性质图的分类与特点按边的方向分为有向图和无向图，按权值分为带权图和无权图完全图中任意两个顶点间都有边，稀疏图边数较少，稠密图边数较多不同类型的图需要不同的存储方式和算法处理。