《数据结构教程》课件

数据结构教程（课程总览）欢迎各位同学加入《数据结构教程》课程！数据结构是计算机科学中最基础、最重要的课程之一，它研究数据的组织方式与处理算法，为大型软件系统的设计与实现奠定坚实基础本课程将系统介绍各种经典数据结构的定义、特性、实现方法及应用场景，从基本概念到复杂算法，循序渐进地建立起完整的知识体系，培养同学们的抽象思维能力与问题解决能力通过本课程学习，你将掌握如何选择合适的数据结构来高效处理各类应用问题，为后续的算法设计、软件开发和计算机系统学习打下坚实基础数据结构的基本概念数据、数据元素与数据项数据是信息的载体，是对客观事物的符号表示数据元素是数据的基本单位，也称为记录每个数据元素由若干个数据项组成，数据项是数据的最小单位例如，学生记录中，每个学生是一个数据元素，而学号、姓名、年龄等属性是数据项理解这三者的关系是掌握数据结构的基础数据对象与数据结构数据对象是具有相同性质的数据元素的集合数据结构则是数据元素之间的关系集合，包括数据元素间的关系和操作数据结构是抽象数据类型的物理实现掌握数据结构不仅要了解数据如何组织，更要理解如何有效地对其进行操作与处理，以解决实际问题抽象数据类型（）基础ADT抽象定义独立于具体实现的数据模型操作集合对数据类型合法的操作集合实现方法具体的编程语言实现方式抽象数据类型（）是一种数学模型，它定义了数据对象、数据对象之间的关系及操作，但不涉及具体实现的核心思想是抽象ADT ADT与封装，即将数据及其操作封装在一起，对外只提供接口，隐藏内部实现细节这种分离使得我们可以聚焦于问题本身，而不被具体实现细节干扰例如，栈的定义了后进先出的特性和入栈、出栈等操作，ADT但不考虑用数组还是链表实现这种抽象思维对于软件设计至关重要数据结构的三要素逻辑结构逻辑结构描述数据元素之间的抽象关系，是从问题的逻辑角度出发，与具体实现无关包括线性结构（如线性表）、树形结构（如二叉树）、图形结构（如有向图）和集合结构存储结构存储结构是逻辑结构在计算机中的实现方式，主要包括顺序存储、链式存储、索引存储和散列存储存储结构关注如何在有限的物理空间内高效组织数据运算运算是施加在数据结构上的操作集合，如查找、插入、删除、修改等不同的存储结构会影响运算的效率，因此选择合适的存储结构对于算法效率至关重要这三个要素相互关联，构成了数据结构的完整概念在实际应用中，我们需要根据问题特点选择合适的逻辑结构，并根据运算需求确定最佳的存储结构，以达到时间和空间的最优平衡数据的逻辑结构全景集合结构线性结构元素间除属于同一集合外无其他关系元素之间存在一对一的前驱后继关系图状结构树形结构元素之间存在多对多的网络关系元素之间存在一对多的层次关系逻辑结构是从具体问题抽象出的数据模型，反映了数据元素之间的关系集合结构最为简单，如数据库中的记录集；线性结构有明确的线性次序，如队列、栈；树形结构具有层次特性，适合表示分类数据；图状结构最为复杂，可表示任意关系不同的问题领域适合不同的逻辑结构例如，家族关系适合用树形结构，而城市交通网络则适合用图状结构表示选择合适的逻辑结构是解决问题的第一步，也是最关键的一步线性表基础线性表定义线性表特性线性表是具有相同数据类型的个数线性表中的元素是有序的，具有线性n据元素的有限序列，其中当关系，且每个元素在线性表中的位置n≥0时称为空表除了首尾元素外，是唯一的线性表的长度可以动态变n=0每个元素都有唯一的前驱和后继化，但在任一时刻都是有限的线性表分类按存储方式分为顺序表和链表顺序表使用连续内存空间存储，链表使用分散的存储单元通过指针连接两种实现各有优劣，适用于不同场景线性表是最基本的数据结构之一，是其他复杂数据结构（如栈、队列）的基础其操作主要包括初始化、插入、删除、查找、修改等线性表广泛应用于数据处理的各个领域，如学生信息管理、图书管理系统等理解线性表的概念和操作对于学习其他高级数据结构至关重要，也是编程能力培养的基础后续我们将深入讨论线性表的不同实现及其效率分析线性表的顺序存储内存布局使用一组连续的存储单元依次存储线性表的各个元素，物理位置相邻访问方式通过首地址和元素序号，利用数学公式直接计算元素的存储位置动态扩容初始分配固定空间，当空间不足时，申请更大的连续空间并拷贝数据性能特点随机访问高效（），但插入删除需要移动元素（平均）O1On顺序存储是线性表最基本的实现方式，它利用数组的索引特性，使得元素的随机访问非常高效在C语言中，我们通常使用结构体表示顺序表，包含数据数组、当前长度和总容量三个主要字段顺序表的主要优点是支持随机访问和遍历效率高，但缺点是插入删除操作需要移动大量元素，且预先分配固定空间可能导致空间浪费或空间不足在实际应用中，当查询操作频繁而插入删除较少时，顺序表是较好的选择线性表的链式存储节点结构设计数据域存储元素值，指针域存储后继节点地址链表操作实现通过修改指针实现插入删除，无需移动元素头指针与头节点头指针指向链表第一个节点，头节点简化操作链式存储结构是线性表的另一种重要实现方式，它不要求逻辑上相邻的元素在物理位置上也相邻链表中的每个节点由两部分组成数据域和指针域数据域存储元素值，指针域存储下一个节点的内存地址与顺序表相比，链表的优势在于插入和删除操作非常高效，时间复杂度为（不考虑查找时间）但链表不支持随机访问，查找操作效O1率低，且每个节点需要额外的空间存储指针链表特别适合元素动态变化频繁、无法预估数据规模的场景双向链表与循环链表双向链表结构双向链表的每个节点包含三个字段数据域、前驱指针和后继指针前驱指针指向前一个节点，后继指针指向后一个节点双向链表的主要优点是可以方便地访问前驱节点，使得逆向遍历和某些操作更加高效例如，从链表中删除当前节点时，不需要再从头遍历寻找前驱节点循环链表特点线性表典型算法实现操作顺序表链表查找直接索引访问需顺序遍历O1On插入需移动元素修改指针即可On O1删除需移动元素修改指针即可On O1空间利用可能有空间浪费按需分配更灵活线性表的基本操作包括初始化、销毁、插入、删除、查找和遍历等对于顺序表，查找操作效率高，而插入删除需要移动元素；对于链表，插入删除只需修改指针，但查找则需要从头遍历在实际应用中，我们需要根据操作特点选择合适的实现例如，电话簿这类需要频繁查询但很少修改的场景适合顺序表；而编辑器中频繁的插入删除操作则更适合链表理解两种实现的优缺点，是选择合适数据结构的关键栈的基础概念后进先出原理栈的典型应用栈的定义LIFO ADT栈的最核心特性是后进先出栈广泛应用于表达式求值、括号匹配检查、作为抽象数据类型，栈定义了一组操作初Last InFirst，即最后放入的元素最先被取出这就函数调用与返回、递归实现、中缀表达式转始化、判空、入栈、出栈、获取栈顶元素等Out像一摞书，我们只能从顶部放入或取出书本后缀表达式等场景例如，在计算表达式这些操作共同维护了栈的特性，确保了LIFO这种特性使栈成为解决某些特定问题的理想时，需要先计算括号内的值，这对栈的正确使用和理解3*4+5结构正是栈的应用栈是一种受限的线性表，只允许在一端（通常称为栈顶）进行插入和删除操作这种受限的线性表特性使栈成为解决特定问题的理想工具，例如在浏览器的前进后退功能、文本编辑器的撤销操作中都有应用栈的顺序与链式存储顺序栈实现顺序栈使用一维数组存储元素，同时使用一个指针（）指示栈顶位置top入栈操作时增加，出栈操作时减少顺序栈易于实现，但存在栈top top满的问题当顺序栈空间不足时，可以采用动态扩容策略分配一个更大的数组，将原数组内容复制过去，然后释放原数组这种方法虽然解决了空间不足问链式栈实现题，但复制操作会影响效率链式栈使用单链表实现，通常将链表的头部作为栈顶，便于快速进行入栈和出栈操作链式栈的优点是不存在栈满的问题，能灵活地根据需要分配空间在链式栈中，入栈等同于在单链表头部插入节点，出栈等同于删除头部节点这种实现方式避免了顺序栈可能的空间浪费，也不需要预先估计栈的大小在实际应用中，如果能够预估栈中元素的最大数量，且访问频繁，可以选择顺序栈；如果元素数量变化较大或无法预估，则链式栈可能更合适两种实现各有优缺点，选择时应考虑具体应用场景的需求栈的主要操作获取栈顶元素GetTop出栈操作Pop顺序栈返回位置元素，不改变top入栈操作Push顺序栈判断栈是否为空，非空则取栈初始化操作顺序栈判断栈是否已满，未满则元出位置元素，减top top1链式栈返回头节点的数据，不改变顺序栈分配内存空间，设置栈顶指素放入位置，加top+1top1链式栈判断栈是否为空，非空则保栈针为（空栈）top-1链式栈创建新节点，新节点指向原存栈顶元素，头指针指向下一节点，链式栈创建头节点，头指针指向栈顶，头指针指向新节点释放原栈顶（空栈）NULL栈的操作都集中在栈顶进行，这种特性使得栈的基本操作非常高效，时间复杂度均为在实现栈操作时，需要特别注意边界条件的处理，例如栈空栈满的O1判断，以避免下溢和上溢错误队列基本原理先进先出原则循环队列FIFO队列是一种遵循先进先出循环队列是为了解决顺序队列的原则的线假溢出问题设计的通过将队列First InFirst Out性结构，新元素只能从队尾入队，首尾相连形成一个循环，当队尾而元素的删除只能从队首进行指针到达数组末端时，如果数组这种特性使其在操作系统中的作前端有空闲位置，可以将其重新业调度、消息缓冲等场景有广泛利用，提高空间利用率应用链式队列链式队列使用链表实现，拥有头指针和尾指针，分别指向队首和队尾其优点是不存在空间固定的问题，能根据实际需要动态分配内存，但需要额外的空间存储指针信息队列作为一种基本数据结构，其操作包括初始化、判空、入队、出队和获取队首元素等在实现循环队列时，需要特别注意队满和队空条件的判断，通常采用牺牲一个存储单元的方式区分这两种状态队列扩展与应用双端队列缓冲区应用可在两端进行插入和删除操作解决生产者消费者问题的关键结构调度系统优先队列操作系统中进程和资源的管理元素出队顺序由优先级决定双端队列是队列的扩展，允许在两端进行插入和删除操作，结合了栈和队列的特性它可以用数组或链表实现，在算法设计中有特殊应用，deque如滑动窗口问题队列在计算机系统中应用广泛在操作系统中，队列用于进程调度、中断处理；在网络传输中，队列用于数据包的缓存与转发；在消息系统中，队列用于异步处理消息优先队列则在任务调度、事件驱动编程中发挥关键作用字符串与存储ADT字符串的定义静态存储方式字符串是由零个或多个字符组成静态字符串使用预分配的固定大的有限序列，记为小数组存储在语言中，字符C字符串是一种串以结尾，这种方式简单直S=a0a

1...an-1\0特殊的线性表，其元素为字符，观，但空间利用效率较低，且对有长度属性，且具有串接、子串长字符串支持不佳提取等特定操作动态存储方式动态字符串根据实际需要分配空间，如堆分配或块链存储结构这种方式灵活高效，适合长度变化大的字符串，但实现复杂，需要管理内存分配与释放字符串是程序设计中使用最广泛的数据类型之一，其操作包括串赋值、串连接、求子串、字符串比较等根据应用场景的不同，选择合适的存储方式至关重要字符串匹配基础算法朴素匹配算法逐一比较主串与模式串，时间复杂度Om*n算法KMP利用已匹配信息避免回溯，时间复杂度Om+n数组构建next记录模式串前缀与后缀的最大匹配长度实际应用文本搜索、序列匹配、网络入侵检测DNA字符串匹配是文本处理的基本操作，目的是在主串中查找模式串出现的位置朴素匹配算法思路简单但效率低，特别是在主串和模式串较长时性能较差算法是一种高效的字符串匹配算法，其核心思想是利用已经匹配的信息，在匹配失败时，不KMP必回溯主串指针，而是利用数组调整模式串指针这种方法显著提高了匹配效率，特别是在next文本搜索引擎、基因序列分析等需要大量字符串匹配的应用中具有重要价值数组与广义表一维数组一维数组是最简单的数组形式，元素按线性顺序排列物理存储上通常使用连续的内存空间，访问元素时通过基地址和偏移量计算其定位公式为，其中是基地址，Locai=base+i*size base是每个元素占用的空间大小size多维数组多维数组是一种高维数据结构，如矩阵（二维数组）存储方式有行优先（语言采用）和列优先C（采用）两种对于行列的二维数组，行优先存储的定位公式为Fortran mn Locaij=base+，其中是行号，是列号i*n+j*size ij广义表是一种特殊的线性表，其元素可以是单个数据，也可以是广义表这种递归定义使得广义表可以表示非常复杂的数据结构广义表通常用括号表示，如表示一个由三个元素组成的表，A=a,b,c则是一个包含了另一个表的广义表B=A,d广义表在表示复杂结构时非常有用，如家谱关系、多层嵌套的文件系统等在实现上，广义表通常采用链式存储结构，每个节点有两个指针，分别指向表头和表尾稀疏矩阵压缩存储稀疏矩阵定义1非零元素数远少于总元素数的矩阵三元组表示法2每个非零元素用行列值表示,,行压缩存储增加行索引数组提高访问效率稀疏矩阵在科学计算、图像处理等领域应用广泛传统的二维数组存储方式会造成大量空间浪费，因此需要特殊的压缩存储技术三元组表示法是最基本的压缩方式，将每个非零元素的行号、列号和值存储为一个三元组，按行主次、列次序排列对于大型稀疏矩阵，可以采用行压缩存储方式，增加一个行索引数组，记录每行第一个非零元素在三元组表中的位置这种方法显著提高了按行访问的效率，对矩阵运算（如矩阵乘法）有很大帮助在实际应用中，根据矩阵的特性和操作要求，可能还需要设计更复杂的存储结构树的基本概念节点与关系定义层次与深度树是由个节点组成的有限集合若节点的层次从根开始定义，根为第层，nn≥01，称为空树；若，则有且仅有一根的子节点为第层，以此类推树的深n=0n02个特定节点称为根节点，其余节点可分为度是树中节点的最大层数，也称为树的高个互不相交的子树度mm≥0每个节点有且仅有一个父节点（根节点除节点的深度是指从根到该节点的唯一路径外），可以有零个或多个子节点节点的长度节点的高度是指从该节点到叶子节度是指其子树的个数，树的度是所有节点点的最长路径长度对于同层节点，称为度的最大值兄弟节点树的种类根据节点的最大度数，可分为二叉树、三叉树等特殊的树包括完全二叉树、满二叉树、平衡二叉树等森林是指棵互不相交的树的集合通过将根节点相连，森林可以转换为树；反之，mm≥0删除树根与其子节点的连接，树可以转换为森林树结构是一种非线性结构，它模拟了自然界中分支结构的特点，能够表示层次关系树在实际应用中极为广泛，如文件系统、组织结构、家谱关系、决策树等树的存储结构双亲表示法孩子兄弟表示法孩子表示法双亲表示法使用一组连续空间（数组）存储树孩子兄弟表示法又称二叉链表表示法，每个节孩子表示法为每个节点建立一个子节点链表，的节点，每个节点除了数据域外，还包含指向点包含三个域数据域、第一个子节点指针、主体是一个节点数组，每个数组元素中保存一其父节点的指针这种方法便于找父节点，但下一个兄弟节点指针这种表示法能够方便地个指向子节点链表的头指针这种方法便于查查找子节点时需要遍历整个数组特别适用于实现树转换为二叉树的操作，对树的遍历和各找子节点，但不易确定父节点，除非使用双向经常需要查找父节点的场景种操作提供了很大便利链表选择合适的树存储结构取决于应用需求如果需要频繁查找父节点，可选择双亲表示法；如果需要方便进行树与二叉树的转换，可选择孩子兄弟表示法；如果主要操作是查找子节点，则孩子表示法较为合适二叉树基础22^n-1每个节点最多的子节点数满二叉树的节点数公式二叉树中的每个节点最多有两个子节点，分别称为高度为的满二叉树恰好有个节点n2^n-1左子节点和右子节点n+1叶子节点与度为节点的关系2在任意二叉树中，叶子节点数等于度为的节点数2加1二叉树是每个节点最多有两个子树的树结构，是树形结构的一种特殊形式二叉树具有五种基本形态空二叉树；只有一个根节点的二叉树；根节点只有左子树；根节点只有右子树；根节点同时有左右子树特殊类型的二叉树包括满二叉树（除叶子节点外，每个节点都有两个子节点）；完全二叉树（除最后一层外，其他层节点数达到最大，且最后一层节点从左到右连续排列）；平衡二叉树（任意节点的左右子树高度差不超过）这些特殊类型的二叉树在不同的应用场景中有着重要作用1二叉树遍历方法先序遍历访问顺序根节点左子树右子树→→递归实现若二叉树为空，返回；否则访问根节点，先序遍历左子树，先序遍历右子树2中序遍历访问顺序左子树根节点右子树→→递归实现若二叉树为空，返回；否则中序遍历左子树，访问根节点，中序遍历右子后序遍历3树访问顺序左子树右子树根节点→→递归实现若二叉树为空，返回；否则后序遍历左子树，后序遍历右子树，访问根节4层序遍历点访问顺序按层从上到下，每层从左到右实现使用队列，先将根节点入队，然后出队一个节点并访问，将其左右子节点入队，重复直到队列为空二叉树的遍历是指按特定顺序系统地访问二叉树中的所有节点，是二叉树上最基本的操作每种遍历方法都有其特定的应用场景，比如中序遍历对于二叉搜索树会得到一个有序序列二叉树的存储与还原顺序存储结构顺序存储使用一维数组，按照完全二叉树的层序编号方式存储节点对于节点，其左子节点索引为，右i2i+1子节点索引为，父节点索引为2i+2i-1/2⌊⌋这种存储方式适用于完全二叉树，对于稀疏二叉树会造成空间浪费在实现上，通常使用特殊值（如）NULL表示不存在的节点链式存储结构链式存储每个节点包含数据域和两个指针域，分别指向左右子节点这是最常用的二叉树存储方式，适用于各种类型的二叉树，特别是结构不规则的二叉树在语言中，通常使用结构体表示节点，如C struct TreeNode{int data;structTreeNode*left,这种结构灵活但需要额外空间存储指针*right;}线索二叉树线索化概念利用空指针域存储遍历序列的前驱和后继关系节点结构增加两个标志位指示左右子树指针的类型遍历优化无需递归和栈，直接访问前驱或后继节点构建方法在遍历过程中修改空指针，建立线索关系线索二叉树是一种改进的二叉树，它利用二叉树中大量的空指针域来存储遍历时的前驱和后继关系在普通二叉树中，对于个节点的二叉树，共有个指针域，其中有个空指针域线索二叉树充n2n n+1分利用这些空指针域，提高了遍历效率按照线索化的方式，线索二叉树可分为先序线索二叉树、中序线索二叉树和后序线索二叉树其中中序线索二叉树最为常用，因为中序遍历能够按照节点值的大小顺序访问节点，特别适合于二叉搜索树线索化后的二叉树遍历不再需要使用递归或栈，大大提高了遍历效率哈夫曼树与编码最优二叉树带权路径长度最小的二叉树1带权路径长度所有叶子节点的权值乘以路径长度之和前缀码没有任何码字是其他码字的前缀哈夫曼树（）又称最优二叉树，是一种带权路径长度最小的二叉树构建哈夫曼树的基本思想是将权值最小的两个节点合并成一Huffman Tree个新节点，新节点的权值为两个节点权值之和，然后在包含这个新节点的个节点中重复此过程，直到只剩一个节点，即树的根节点n-1哈夫曼编码是一种基于哈夫曼树的变长编码方式，其核心原理是频率高的字符使用短编码，频率低的字符使用长编码哈夫曼编码是前缀码，即没有任何一个字符的编码是另一个字符编码的前缀，这保证了解码的唯一性哈夫曼编码广泛应用于数据压缩，如图像压缩、音频压缩等JPEG MP3树的应用典型案例文件系统结构组织结构图编译器语法分析计算机文件系统是树结构的典型应用，目录和企业和机构的组织架构通常表现为树形结构，在编译原理中，语法分析过程会生成语法树或子目录形成树形结构，文件是树的叶子节点或总裁作为根节点，各部门经理作为内部抽象语法树，用于表示程序的语法结构这些CEO这种结构便于文件的组织和管理，支持高效的节点，员工作为叶子节点这种结构直观地反树结构帮助编译器理解和翻译高级语言，为代文件检索和路径导航操作系统通过树的遍历映了管理关系和信息流通路径，帮助企业建立码优化和目标代码生成提供基础现代编译器算法实现文件的查找、复制和删除等操作清晰的责任体系和沟通渠道和解释器严重依赖树结构进行语言处理树结构在实际应用中无处不在，从简单的家谱表示到复杂的人工智能决策系统在数据库系统中，树和树用于索引优化；在网页渲染中，B B+DOM树表示文档结构；在游戏开发中，场景图和行为树用于环境建模和控制理解树的原理和操作，对于解决各种实际问题具有重要意义HTML AI图的基础定义顶点与边有向图与无向图图由顶点集和边集组成，记无向图的边没有方向性，表示对G VE为每条边连接两个顶称关系；有向图的边有方向，表G=V,E点，表示它们之间存在某种关系示单向关系无向图中的边用无顶点的度是指与该顶点相连的边序对表示，有向图中的边用u,v的数量有向图中区分入度和出有序对表示，表示从到的路径u v度带权图带权图（网络）的每条边都有一个权值，表示两个顶点之间关系的强度、距离、成本等量化指标权值可以是正数、负数或零，根据具体应用决定其含义图是一种非线性数据结构，它由顶点和连接顶点的边组成，用于表示事物之间的复杂关系与树不同，图允许环的存在，且没有根节点概念图的应用极其广泛，包括社交网络分析、地图导航、网络拓扑结构、任务调度、资源分配等众多领域图的存储方法（邻接矩阵）图的存储方法（邻接表）邻接表结构邻接表是图的另一种主要存储方式，它为每个顶点建立一个链表，链表中的节点表示与该顶点相邻的顶点每个链表节点通常包含顶点编号、边权值（如有）和指向下一个节点的指针对于个顶点、条边的图，邻接表的空间复杂度为，比邻接矩阵更节省空间，特别是对稀疏图（n eOn+e e实现与优化在实现上，邻接表通常使用数组链表的组合结构，数组索引对应顶点编号，元素指向该顶点的邻接链表为了提高查询效率，+可以使用有序链表、跳表或平衡树代替普通链表图的深度优先遍历DFS遍历准备创建访问标记数组，初始化为visited false选择任一顶点作为起始点，标记为已访问准备栈（递归隐式使用）或显式使用栈结构递归探索访问当前顶点，并在数组中标记visited查找当前顶点的第一个未访问的邻接顶点若找到，递归访问该邻接顶点；否则回溯回溯处理当顶点所有邻接点都已访问，返回上一级调用继续查找上一级顶点的下一个未访问邻接点如此反复，直到所有顶点都被访问连通分量处理对于非连通图，需要扫描数组visited找到未访问的顶点，以其为起点重新开始DFS直到所有顶点都被访问过为止深度优先搜索（）是图遍历的一种基本方法，其核心思想是尽可能深地搜索图的分支的实现可以使用递DFS DFS归或显式栈，递归实现更为简洁，但可能因调用栈深度过大导致栈溢出图的广度优先遍历BFS初始化创建队列和访问标记数组，选择起始顶点起点入队将起始顶点标记为已访问并入队队列处理出队一个顶点，访问并处理该顶点邻接点处理将所有未访问的邻接点标记并入队循环重复重复处理队列，直到队列为空广度优先搜索（）是与相对的另一种图遍历策略，它按距离起始顶点的远近顺序逐层遍历图中的顶点的核心数据结构是队列，它保证了顶点被访问的顺序与其到起始点的BFS DFS BFS距离成正比在寻找最短路径、连通性分析和层次关系处理等问题上有重要应用例如，在社交网络中查找两人之间的最短联系路径、在迷宫中寻找出口的最短路径等与相比，占用的BFS DFSBFS空间可能更大，但能保证找到的路径是最短的连通分量与生成树连通分量是无向图中的最大连通子图在连通图中，任意两个顶点之间都存在路径，整个图就是一个连通分量；在非连通图中，存在多个连通分量，每个连通分量内的顶点相互可达连通分量的识别可以通过一次或完成DFSBFS生成树是连通图的一个极小连通子图，它包含图中所有顶点，且边数最少（条，为顶点数）任何连通图都至少有一棵生成树若给定图的每条边都有权值，则总权n-1n值最小的生成树称为最小生成树（），用于解决网络设计中的最低成本连接问题MST在有向图中，若从某个顶点出发能到达图中任意顶点，则称该顶点为强连通图的根以根顶点为起点进行遍历得到的树称为有向图的生成树生成树反映了图的骨架结构，去除了环路，简化了图的分析最小生成树算法——Prim选择起始顶点从图中任选一个顶点作为起始点，加入最小生成树集合S寻找最小边在所有连接和的边中，找出权值最小的边，其中∈，∈S V-S u,v uS vV-S扩展生成树将顶点加入集合，将边加入最小生成树v Su,v重复执行重复前两步，直到所有顶点都加入集合，此时得到最小生成树S算法是求解最小生成树的一种贪心算法，它的核心思想是从一棵单顶点的树开始，逐步选择Prim最小权值的边来扩展这棵树，直到包含图中所有顶点与算法不同，算法始终保持Kruskal Prim一棵生长中的树算法特别适用于稠密图（边数接近顶点数的平方），因为它的时间复杂度主要取决于如何寻Prim找最小权值的边使用邻接矩阵实现时，时间复杂度为；使用优先队列优化时，可以降低On²到，其中是顶点数，是边数Oe logn ne最小生成树算法——Kruskal边排序初始化将所有边按权值升序排序每个顶点作为单独的连通分量合并分量选择边合并边连接的两个连通分量按权值顺序选择不形成环的边算法是另一种求解最小生成树的贪心算法，它的核心思想是按权值从小到大选择边，并保证不形成环路与算法从一个顶点开始不同，Kruskal Prim算法可能同时维护多个不相交的树（森林），最终这些树会合并成一棵最小生成树Kruskal算法特别适用于稀疏图（边数远小于顶点数的平方），其时间复杂度主要取决于边的排序，为，其中是边数为了高效检测环Kruskal Oe log ee路，通常使用并查集（）数据结构，它支持快速查询两个顶点是否在同一个集合中，以及合并两个集合Union-Find最短路径问题算法——Dijkstra初始化距离1源点到自身距离为，到其他顶点距离为无穷大0选择顶点选择距离最小的未访问顶点u更新距离通过松弛所有与相邻的未访问顶点u uv算法是解决单源最短路径问题的经典算法，适用于所有边权值非负的图其核心思想是贪心策略，每次选择当前距离源点最近的未访Dijkstra问顶点，通过该顶点更新其他顶点的距离松弛操作是关键步骤，即如果通过顶点可以得到更短的路径，则更新相应的距离值u算法的实现通常使用优先队列（如小顶堆）来高效地选择最小距离顶点对于稠密图，使用邻接矩阵实现的时间复杂度为；对于Dijkstra On²稀疏图，使用邻接表和优先队列实现的时间复杂度为，其中是顶点数，是边数Oelogn ne拓扑排序与网AOV网定义拓扑排序概念AOV活动在顶点（）网是一种有向拓扑排序是将有向无环图中的所有顶点排成一个线Activity OnVertex无环图（），用于表示活动之间的先后依赖关性序列，使得图中任何一对顶点和，若存在边，DAG uv系图中的顶点表示活动，有向边表示活动必须在则在排序中出现在之前一个可能有多个不i uv DAG活动之前完成同的拓扑排序结果j用于描述工程计划、课程安排等具有依赖关系拓扑排序的结果反映了活动的执行顺序••的活动可用于检测图中是否存在环路（环路无法得到•必须没有环路，否则表示存在循环依赖，无法拓扑排序）•安排顺序实现算法拓扑排序有两种主要实现方法算法（基于入度）和（基于深度优先搜索）算法的基本思想Kahn DFSKahn是不断移除入度为的顶点，然后更新其邻接点的入度0计算所有顶点的入度，将入度为的顶点加入队列

1.0出队一个顶点，将其加入结果序列，并将其所有邻接顶点的入度减

2.1如果减后入度变为，则将该顶点入队

3.10重复上述过程直到队列为空

4.拓扑排序在实际应用中十分广泛，例如在编译器中确定模块编译顺序、在项目管理中安排任务执行顺序、在课程设计中安排先修课程等检测循环依赖也是其重要应用，如果拓扑排序结束后仍有顶点未被排序，则说明图中存在环路查找结构与算法分类顺序查找二分查找哈希查找顺序查找是最基本的查找方法，从表的一端开二分查找要求查找表是有序的，每次比较中间哈希查找基于哈希表这一特殊的数据结构，通始，依次比较表中元素与目标值，直到找到或元素与目标值，然后在中间元素的左侧或右侧过哈希函数将关键字映射到表中的位置，理想查找完表中所有元素它适用于任何查找表，子表中继续查找它的时间复杂度为，情况下可以实现时间复杂度的查找但哈Olog n O1不要求表有序，但效率较低，平均时间复杂度效率明显高于顺序查找，但对查找表有序性的希冲突的存在使得哈希查找的效率受到影响，为要求限制了其应用范围需要合理设计哈希函数和冲突解决策略On查找是计算机科学中的基本操作，是从大量数据中快速定位特定元素的过程根据查找表的结构和算法思想，可以将查找分为多种类型除了基本的顺序查找、二分查找和哈希查找外，还有基于树结构的查找（如二叉搜索树查找、平衡树查找）和基于数字结构的查找（如基数树查找）等顺序查找与改进基本顺序查找顺序查找（线性查找）是最简单的查找算法，从表的第一个元素开始，按顺序依次比较表中的每个元素与目标值，直到找到匹配项或遍历完整个表基本顺序查找的伪代码如下function SequentialSearchA,n,key:哨兵优化for i=1to ndoif A[i]==key then顺序查找的一个常见优化是使用哨兵技术在查找前，将目标值临时存放在表的末尾（位置），这样n+1return i可以省略每次循环中的边界检查，提高效率return0//未找到哨兵优化的伪代码这种方法不要求表有序，适用于任何查找表，但平均时间复杂度为，效率较低Onfunction SentinelSearchA,n,key:A[n+1]=key//设置哨兵i=1while A[i]!=key doi=i+1if i=n thenreturnielsereturn0//未找到哨兵技术不改变算法的时间复杂度，但能减少循环中的比较次数，提高常数因子的效率对于大型数据集，顺序查找的效率过低，通常需要考虑其他查找算法或数据结构然而，在小型数据集或无法预先排序的情况下，顺序查找仍是一种简单可靠的方法现代处理器的缓存机制和分支预测也可能使顺序查找在某些情况下表现良好二分查找实现及边界讨论算法前提二分查找要求查找表已排序（通常是升序），且支持随机访问（如数组）对于频繁查找但较少更新的数据，预先排序是值得的优化递归实现递归方法将问题分解为更小的子问题，代码简洁但有栈开销伪代码BinarySearchA,low,high,key基本思想是计算中间位置，比较与，然后在左半部分或右半部分递归查找mid A[mid]key非递归实现迭代方法使用循环代替递归，避免栈开销，更为高效伪代码比较并调整或while low=high{low high}需要注意循环条件和边界调整，防止死循环或索引越界边界错误案例计算可能导致整数溢出错误写法mid mid=low+high/2正确写法或mid=low+high-low/2mid=low+high1循环条件、边界更新和返回值处理都是常见错误源二分查找虽然概念简单，但正确实现却容易出错常见错误包括循环条件使用而非；更新边界时使用而=mid非±；计算可能导致整数溢出；未考虑重复元素的情况等这些微小的错误可能导致算法失效或陷入无mid1mid限循环散列查找与哈希函数哈希表基本结构装填因子与性能哈希表（散列表）是一种数据结构，它装填因子是哈希表中已存储元素数量α通过哈希函数将关键字映射到表中的某与表大小的比值随着的增大，哈希α个位置，以实现高效的插入、删除和查冲突的概率增加，查找效率降低一般找操作理想情况下，查找的时间复杂建议将控制在之间，必要α

0.5-

0.75度为，但实际效率取决于哈希函时进行表扩容，以保持较高的查找效率O1数的设计和冲突解决策略哈希函数设计好的哈希函数应均匀分布，计算简单，减少冲突常见的哈希函数包括直接定址法（适用于关键字分布已知且较小）；除留余数法（取模运算，表大小通常选择质数）；数字分析法（分析关键字的分布特性）；折叠法（将关键字分割后叠加）；平方取中法等哈希查找的效率高度依赖于哈希函数的质量和冲突解决方法一个好的哈希函数应该将关键字均匀分布在哈希表中，减少冲突；同时计算过程应尽可能简单，不应成为性能瓶颈在实际应用中，可能需要根据具体的数据特性设计专门的哈希函数哈希冲突解决方法开放定址法线性探测二次探测双重散列冲突时在表中寻找其他可用位置依次检查下一个位置直到找到空位使用二次函数增量减少聚集问题使用第二个哈希函数计算探测步长开放定址法是解决哈希冲突的一种方法，当发生冲突时，它在哈希表中寻找其他位置存储元素线性探测是最简单的方式，但容易导致主聚集问题；二次探测使用二次函数作为偏移量，可以减轻聚集；双重散列使用第二个哈希函数计算步长，分布更均匀但计算量增加链地址法（拉链法）是另一种常用的冲突解决方法，它将哈希到同一位置的元素存储在一个链表中这种方法不限制表中元素数量，实现简单，但需要额外的链表空间对于链较长的情况，可以使用平衡树代替链表，进一步提高查找效率冲突解决方法的选择应考虑数据特性、空间限制和预期操作排序算法全景算法时间复杂度平均空间复杂度稳定性冒泡排序稳定On²O1选择排序不稳定On²O1插入排序稳定On²O1希尔排序不稳定On^

1.3O1快速排序不稳定On logn Olog n归并排序稳定On logn On堆排序不稳定On lognO1排序算法可分为内部排序和外部排序两大类内部排序在内存中完成，适用于数据量较小的情况；外部排序需要借助外部存储设备，适用于大规模数据按照原理，排序算法又可分为比较类（如冒泡、快速、归并等）和非比较类（如计数、基数、桶排序等）评价排序算法的指标包括时间复杂度（最好、最坏、平均情况）、空间复杂度、稳定性（相同键值的元素相对顺序是否保持不变）、适用数据范围等在实际应用中，应根据数据特性、排序要求和硬件环境选择合适的排序算法冒泡排序、选择排序冒泡排序原理冒泡排序是一种简单的比较排序算法，它重复地比较相邻元素，并在需要时交换它们的位置每一轮循环后，最大最小元素会移动到数组的末/端，就像气泡上升一样function BubbleSortA,n:for i=1to n-1dofor j=1to n-i doifA[j]A[j+1]thenswap A[j]and A[j+1]冒泡排序的时间复杂度为，空间复杂度为，是一种稳定排序算法可以通过添加标志位判断一轮比较是否有交换发生，如果没有则On²O1提前结束排序插入排序与希尔排序插入排序插入排序是一种简单直观的排序算法，它的工作原理类似于扑克牌整理将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置初始时，已排序部分只包含第一个元素插入排序的时间复杂度为，但在近乎有序的数据集上表现极佳，接近它是一种稳定的排序算法，适合小规模或接近有序的数据排序On²On希尔排序希尔排序是插入排序的改进版，它通过将数组分成若干个间隔为的子数组，对每个子数组进行插入排序，然后减小的值，重复此过程直到这种方法使得元素能够大步移动，减少h hh=1了交换次数希尔排序的时间复杂度与增量序列的选择有关，一般在到之间它是一种不稳定的排序算法，但在中等规模数据上表现良好，且实现简单，是实际应用中常用的算法On^

1.3On^2性能对比在小规模或近乎有序的数据上，插入排序通常优于希尔排序，因为它的常数因子较小，实现简单而在大规模或无序数据上，希尔排序的性能明显优于插入排序，因为它减少了元素的交换次数两种算法都只需要的额外空间，适合内存受限的环境插入排序的稳定性使其适合需要保持相等元素相对顺序的场景，而希尔排序则在不要求稳定性的场合提供更好的性能O1插入排序和希尔排序在实际应用中各有优势很多高级排序算法（如快速排序、归并排序）在处理小规模子数组时会切换到插入排序，以减少递归开销并利用插入排序在小数据集上的高效性快速排序、归并排序快速排序策略选择基准元素，将数组分为小于和大于基准的两部分分区操作通过一次遍历实现元素分区，返回基准最终位置递归排序对基准元素两侧的子数组递归应用快速排序归并排序原理将数组分成两半，递归排序后合并有序子数组快速排序是一种高效的分治算法，平均时间复杂度为，最坏情况下为它的核心是分区操作，通过选择基准元素将数组分为两部分，然后递归地对子数组进行排序快速排序的优势在于局部性好，On logn On²常数因子小，但它是不稳定的，且在最坏情况下性能下降常见的优化包括三数取中法选择基准、小数组切换到插入排序、处理重复元素等归并排序同样采用分治策略，时间复杂度稳定在它的核心是合并操作，即将两个有序子数组合并成一个有序数组归并排序的主要优势是稳定性和最坏情况下的保证性能，缺点是需要的额外空On logn On间归并排序特别适合外部排序和大数据排序，因为它可以很好地利用磁盘的顺序访问特性堆排序与优先队列堆的定义完全二叉树，满足堆序性质堆的性质大顶堆父节点值子节点值；小顶堆父节点值子节点值≥≤堆化操作3自下而上或自上而下调整，维护堆的性质堆排序是一种基于二叉堆数据结构的比较排序算法它的基本思想是首先将待排序序列构建成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点；将根节点与末尾元素交换，此时末尾元素为最大值；然后将剩余个元素重新构建成堆，重复上述步骤，直到整个序列有序n-1优先队列是一种特殊的队列，它的出队顺序不是先进先出，而是按照元素的优先级决定堆是实现优先队列的理想数据结构，因为它支持快速的插入（）和删除最大最小元素（）操作优先队列在操作系统的作业调度、图算法（如算法和算法）等领域有广泛Olog n/Olog nDijkstra Prim应用排序算法实验与性能对比数据结构前沿与热点树与字符串处理跳表与并发数据结构Trie树（前缀树）是一种用于高效存储跳表是一种随机化的数据结构，它允许Trie和检索字符串的树形数据结构，在自动期望时间的查找、插入和删除Ologn补全、拼写检查和路由查找等应用中表操作，可视为平衡树的一种替代方案现出色近年来，压缩和双数组跳表实现简单，且特别适合并发环境，Trie等变体进一步提高了空间效率和查因此在等现代数据库系统中得到Trie Redis询速度，使其在大规模文本处理和网络广泛应用其并发友好的特性使其成为应用中更具竞争力多线程编程中的重要工具大数据环境下的数据结构在大数据时代，传统的内存数据结构面临挑战，催生了一系列新型数据结构，如布隆过滤器用于高效判断元素是否存在；用于近似频率统计；Count-Min SketchHyperLogLog用于基数估计这些概率数据结构以极小的空间代价提供了近似但足够准确的结果随着计算环境的变化，数据结构也在不断演进和多核处理器的普及推动了并行数据结构的GPU发展；持久内存技术催生了针对新型存储介质优化的数据结构；分布式系统的广泛应用则需要特殊的一致性保证机制同时，机器学习和人工智能领域也提出了新的数据组织需求，如高效的稀疏矩阵表示和张量操作课程总结与复习要点核心知识回顾面试题目与技巧学习建议与拓展本课程系统介绍了数据结构的基本概念、主要类型在技术面试中，数据结构是重点考察内容常见题深入学习数据结构建议多动手实现各种数据结构；及其实现方法从线性结构（线性表、栈、队列）型包括链表操作（如反转、环检测）；树的遍历结合实际问题思考适用场景；关注算法竞赛和编程到非线性结构（树、图），从逻辑结构到物理实现，与构造；图的搜索与最短路径；栈与队列的应用；挑战；阅读开源项目中的数据结构实现未来可拓我们构建了完整的知识体系重点掌握各种数据结哈希表的设计等答题时应先分析问题，选择合适展学习高级数据结构（如红黑树、树）；并发B+构的定义、特性、基本操作及适用场景，理解时间的数据结构，然后考虑边界情况，最后给出清晰的数据结构；分布式数据结构；机器学习相关数据结空间复杂度分析方法解决方案构等/数据结构是计算机科学的基石，掌握它不仅有助于编写高效程序，也是理解计算机系统和算法设计的关键希望通过本课程，同学们不仅学到了具体的数据结构知识，更培养了抽象思维和问题分析能力，为未来的学习和工作奠定坚实基础。