惠州学院陈教员数据结构课件数据结构复习

数据结构复习概述欢迎参加数据结构复习课程！本课程将系统地回顾数据结构的核心概念、实现方法和应用场景，帮助大家巩固所学知识，为期末考试做好充分准备数据结构是计算机科学的基础，它研究如何在计算机中组织和存储数据，以便能够高效地访问和修改掌握好数据结构，是编写高效算法和程序的关键在这个复习系列中，我们将涵盖线性表、栈、队列、树、图、查找和排序等经典数据结构和算法，并结合实例讲解其应用场景同时，我们也会提供解题技巧和复习建议，帮助大家应对考试课程目标和学习要求掌握核心概念实现基本算法解决实际问题理解各种数据结构的能够独立实现各种数学会选择合适的数据定义、特性和基本操据结构及其相关算法，结构解决问题，能够作，能够准确描述其并分析时间和空间复分析问题并设计高效实现原理杂度的算法应对考试评估熟悉各类题型，掌握解题思路和技巧，能够在考试中正确应用所学知识数据结构的基本概念定义逻辑结构数据结构是计算机存储、组描述数据元素之间的逻辑关织数据的方式，它是相互之系，主要包括线性结构、树间存在一种或多种特定关系形结构、图形结构和集合结的数据元素的集合通过合构四种基本类型这些结构理的数据结构设计，可以提反映了现实世界中各种不同高算法的效率类型的关系物理结构指数据结构在计算机中的实际存储形式，主要包括顺序存储结构和链式存储结构物理结构的选择直接影响到对数据的操作效率算法的基本概念算法定义1算法是解决特定问题的一系列操作步骤，它必须具有有限性、确定性、可行性和输入/输出五个基本特性一个好的算法应该是正确的、可读的、健壮的并且高效的算法设计2算法设计是寻找解决问题的有效方法的过程，常用的设计策略包括分治法、动态规划、贪心算法等设计时需要考虑问题的特点和算法的效率算法实现3将设计好的算法转换为程序代码的过程良好的实现应当既能正确解决问题，又具有较高的执行效率和较低的资源消耗算法评价4对算法进行分析和评价，主要从算法的正确性、时间复杂度和空间复杂度三个方面进行这是比较不同算法优劣的重要依据时间复杂度和空间复杂度时间复杂度空间复杂度时间复杂度是算法执行所需时间的量度，用大表示法表空间复杂度是算法执行所需存储空间的量度，同样用大O O示常见的时间复杂度有表示法表示常数复杂度，如数组的随机访问在分析空间复杂度时，要考虑到算法运行过程中临时占用•O1的存储空间大小，包括为变量分配的空间和递归栈所需的对数复杂度，如二分查找•Olog n空间线性复杂度，如顺序查找•On•On logn如快速排序、归并排序算法的空间复杂度通常与问题的规模n有关，可以是常数级、线性级或更高级别在实际应用中，有时需O1On平方复杂度，如冒泡排序•On²要进行时间和空间的权衡指数复杂度，如汉诺塔问题•O2^n线性表的定义和特征线性表的应用广泛应用于排序、查找等1线性表的操作2插入、删除、查找、更新等线性表的实现3顺序存储和链式存储两种方式线性表的特征4元素有唯一前驱和后继（首尾除外）线性表的定义5n个数据元素的有限序列顺序表的实现和操作顺序表的定义将线性表中的元素按顺序存储在一片连续的内存空间中顺序表的特点支持随机访问，存储密度高，但插入删除需要移动元素顺序表的实现通常使用数组实现，需要定义最大容量和当前长度单链表的实现和操作结点定义链表创建插入操作删除操作包含数据域和指针域头插法或尾插法建立修改指针即可，时间修改前驱结点指针，释放O1空间双向链表和循环链表双向链表循环链表双向链表中的每个结点有两个指针域，分别指向前驱结点循环链表是一种特殊的链表，其特点是表中最后一个结点和后继结点这种结构使得可以方便地进行双向遍历，并的指针指向头结点，形成一个环循环链表可以是单循环且能够直接访问任一结点的前驱链表，也可以是双向循环链表特点特点可以双向遍历从表中任一结点出发都能遍历整个链表••删除结点时无需查找前驱适合处理环形结构的数据••结点结构稍复杂，占用空间较大没有明确的表尾标志••栈的定义和特征栈的特点基本操作后进先出LIFO,Last InFirst的访问特性，元素的入栈包括入栈、出栈、Out pushpop和出栈顺序与处理顺序相反获取栈顶元素、判断栈是top否为空等操作栈的定义应用场景栈是一种特殊的线性表，它只函数调用、表达式求值、括号允许在一端（称为栈顶）进行匹配、递归实现、浏览器历史插入和删除操作记录等众多场景栈的顺序存储实现基本结构设计使用一维数组实现栈，定义一个数组用于存储栈元素，使用stack[MaxSize]指针指示栈顶位置初始时表示空栈top top=-1入栈操作实现入栈时先判断栈是否已满，如果未满则将加，然后将新元素存入top1的位置入栈操作的时间复杂度为stack[top]O1出栈操作实现出栈时先判断栈是否为空，如果非空则取出栈顶元素，然stack[top]后将减出栈操作的时间复杂度也是top1O1其他操作实现获取栈顶元素返回的值而不修改判断栈空检stack[top]top查是否等于判断栈满检查是否等于top-1top MaxSize-1栈的链式存储实现基本结构设计使用链表实现栈，每个结点包含数据域和指针域通常将链表的头部作为栈顶，以便在O1时间内完成入栈和出栈操作入栈操作创建新结点，将数据存入数据域，将指针域指向当前的栈顶结点，然后更新栈顶指针指向新结点出栈操作保存当前栈顶结点的数据，将栈顶指针移动到下一个结点，释放原栈顶结点的空间，返回保存的数据其他操作获取栈顶元素直接返回栈顶结点的数据判断栈空检查栈顶指针是否为空链式栈不存在栈满的情况栈的应用表达式求值中缀表达式转后缀使用运算符栈，遇到操作数直接输出，遇到运算符则按优先级规则入栈或出栈如转换为a+b*c abc*+后缀表达式求值使用操作数栈，遇到操作数入栈，遇到运算符则弹出所需操作数进行计算，结果再入栈如计算为23*5+11括号匹配检查遇到左括号入栈，遇到右括号则与栈顶左括号匹配，匹配成功则出栈，最终栈为空则括号匹配正确函数调用实现程序运行时使用栈保存函数返回地址、参数和局部变量，实现函数的嵌套调用和正确返回栈的应用递归队列的定义和特征队列的定义队列Queue是一种特殊的线性表，它只允许在表的一端（称为队尾）进行插入操作，在另一端（称为队头）进行删除操作队列的特点先进先出FIFO,First InFirst Out的访问特性，元素的入队和出队顺序与处理顺序相同，类似于现实生活中的排队现象基本操作包括入队enqueue、出队dequeue、获取队头元素、判断队列是否为空等基本操作，这些操作通常要求在常数时间内完成应用场景广泛应用于操作系统的进程调度、网络数据包传输、广度优先搜索算法以及打印任务管理等需要按照先来先服务原则处理的场景队列的顺序存储实现基本结构设计入队操作出队操作使用一维数组存储队列元入队时先判断队列是否已满，如果未出队时先判断队列是否为空，如果非Q[MaxSize]素，使用指向队头元素，指向满则将新元素存入的位置，然空则取出队头元素，然后将front rearQ[rear]Q[front]队尾元素的下一个位置初始时后将加入队操作的时间复杂度加出队操作的时间复杂度也是rear1front1表示空队列为front=rear=0O1O1队列的链式存储实现基本结构设计使用链表实现队列，每个结点包含数据域和指针域设置指针指向队front头结点，指针指向队尾结点，以方便在队尾进行入队操作，在队头进行rear出队操作链队列的初始化创建一个头结点，和都指向该头结点也可以不设头结点，此front rear时初始化时和都为，表示空队列front rearNULL入队操作实现创建新结点，将数据存入数据域，将指针域置为，将当前队尾NULL结点的指针指向新结点，然后更新指针指向新结点rear出队操作实现判断队列是否为空，如果非空则取出队头结点的数据，将指front针移动到下一个结点，释放原队头结点的空间特别注意队列变空时需更新指针rear循环队列假溢出问题循环队列原理顺序队列中，随着入队和出队操作的进行，队头指针会不断向后移动，将数组视为环形，当队头或队尾指即使队列中实际元素不多，也可能针到达数组末端时，下一个位置绕因队尾指针已移至数组末端而无法回数组首部，有效利用数组空间入队状态判断实现方法队空条件；队满条件使用求余运算实现循环，front==rear，通常牺表示队头rear+1%MaxSize==front front=front+1%MaxSize牲一个空间位置来区分队空和队满指针后移，rear=rear+1%MaxSize表示队尾指针后移串的定义和基本操作串的定义串的基本操作串（String）是由零个或多个字符组成的有•串赋值将一个字符串常量赋给一个串限序列通常记作S=a1a

2...an，其中S是变量串名，单引号内是串的值，n是串的长度•串比较按字典序比较两个串的大小•串连接将两个串拼接成一个新串空串是长度为零的串，NULL串是不存在的•求子串返回串中指定位置和长度的子串，两者是不同的概念串•串插入在串的指定位置插入另一个串•串删除删除串中指定位置和长度的子串串的存储结构串的存储结构主要有顺序存储和链式存储两种方式顺序存储通常采用定长数组或动态分配的数组来实现，而链式存储则使用字符链表来表示串在实际应用中，顺序存储更为常用，因为串的操作主要是比较和查找，顺序存储便于随机访问算法KMP朴素模式匹配算法算法原理算法效率KMP KMP朴素的模式匹配算法采用暴力搜索方算法的核心思想是利用已匹配算法的时间复杂度为，KMP KMPOm+n式，主串从每个位置开始尝试匹配模的信息，在模式串中寻找最长的相同预处理数组的时间为，匹next Om式串，失配时回溯时间复杂度最坏前缀和后缀，从而在失配时避免主串配过程的时间为相比朴素算法，On为，其中和分别是主串和指针的回退，只需移动模式串的位置算法在模式串较长或需要多次Om*n mn KMP模式串的长度匹配时具有明显优势在匹配过程中，主串指针可能多次回算法中引入了数组（或算法的空间复杂度为，主KMP nextfail KMPOm退，这大大降低了匹配效率，尤其当函数），它记录了模式串中每个位置要用于存储数组尽管需要额外next模式串长度较大时之前的子串的最长相同前缀和后缀的空间，但在大多数实际应用中，这点长度利用数组，可以确定失配额外开销是值得的next时模式串应该向右移动的位置树的基本概念和术语树是一种非线性的数据结构，由nn≥0个结点构成的有限集合当n=0时，称为空树；当n0时，树由根结点和若干棵子树构成，每棵子树也是一棵树树的基本术语包括结点（树中的数据元素）、根结点（没有父结点的结点）、叶结点（没有子结点的结点）、内部结点（既有父结点又有子结点的结点）、子树（结点及其后代构成的集合）、结点的度（结点的子树数量）、树的度（所有结点中最大的度）、深度/高度（从根到结点的路径长度/从结点到最远叶结点的路径长度）、层次（根为第1层，依此类推）二叉树的定义和性质二叉树的定义二叉树是一种特殊的树形结构，它的每个结点最多有两个子结点，分别称为左子结点和右子结点二叉树可以为空，也可以只有一个结点，或者只有左（右）子树特殊二叉树满二叉树所有叶结点都在同一层，且每个非叶结点都有两个子结点完全二叉树除最后一层外其他层都是满的，最后一层的结点从左到右连续排列二叉树性质性质1二叉树第i层最多有2^i-1个结点性质2深度为k的二叉树最多有2^k-1个结点性质3任何二叉树，若叶结点数为n0，度为2的结点数为n2，则n0=n2+1二叉树表示二叉树可以用链式存储结构表示，每个结点包含数据域、左子结点指针和右子结点指针也可以使用顺序存储结构，尤其适合完全二叉树二叉树的遍历（前序、中序、后序）前序遍历中序遍历后序遍历前序遍历的顺序是根结点左子中序遍历的顺序是左子树根结后序遍历的顺序是左子树右子→→→树右子树算法实现通常采用递点右子树算法实现树根结点算法实现→→→归方式•中序遍历左子树•后序遍历左子树•访问当前结点•访问当前结点•后序遍历右子树•前序遍历左子树•中序遍历右子树•访问当前结点•前序遍历右子树对于二叉搜索树，中序遍历可以得到后序遍历的特点是根结点最后被访问，前序遍历的特点是根结点最先被访问，有序的结点序列，这是其重要应用之适用于树的删除操作等需要先处理子适用于创建一棵新的树以复制原树等一结点再处理父结点的场景场景二叉树的层次遍历层次遍历定义1层次遍历是按照树的层次从上到下、从左到右依次访问树中各个结点的过程它与前序、中序、后序遍历不同，不采用递归方式实现队列辅助实现层次遍历通常借助队列实现首先将根结点入队，然后循环执行出队、访问该结点、将其左右子结点入队的操作，直至队列为空算法步骤初始化一个队列，将根结点入队；当队列非空时，出队一个结点并访问，然后将其非空的左右子结点依次入队；重复上述过程直至队列为空应用场景4层次遍历在二叉树的宽度计算、最小深度求解、查找特定结点等问题中有重要应用，也是实现树形结构可视化的基础二叉树的存储结构顺序存储结构链式存储结构二叉树的顺序存储通常使用一维数组实现，按照完全二叉二叉树的链式存储通过设置数据域和指针域来表示结点之树的层次遍历顺序将结点存入数组空结点通常用特殊值间的关系每个结点包含一个数据域和两个指针域，分别表示指向左右子结点优点优点实现简单，节省指针空间适应性强，对各种形态的二叉树都适用••适合完全二叉树，存储效率高方便进行插入和删除操作••方便进行结点之间的关系计算不会造成空间浪费••缺点缺点对于非完全二叉树，会造成空间浪费需要额外的指针空间••插入和删除操作不方便不利于随机访问••二叉搜索树定义与特性搜索操作二叉搜索树是一种特殊的二叉BST从根结点开始，如果目标值等于当树，对于任何结点，其左子树上所前结点，返回成功；如果小于当前1有结点的值均小于该结点的值，右结点，在左子树中搜索；如果大于子树上所有结点的值均大于该结点当前结点，在右子树中搜索的值删除操作插入操作分三种情况删除叶结点直接删除；

1.删除只有一个子结点的结点，用子类似于搜索过程，找到插入位置一

2.结点替代；删除有两个子结点的结定是某个结点的子结点位置，创建

3.点，用中序后继或前驱替代新结点并连接到该位置平衡二叉树（树）AVL平衡因子概念平衡因子是结点左右子树高度差，树要求所有结点的平衡因子绝对值不超过AVL1旋转操作原理通过旋转操作调整树的结构，使其恢复平衡，包括左旋、右旋、先左后右双旋和先右后左双旋性能优势分析树保证了树的高度为，从而使搜索、插入和AVL Olog n删除操作的时间复杂度都为Olog n哈夫曼树和哈夫曼编码带权路径长度结点的权值与从根到该结点路径长度的乘积称为结点的带权路径长度，树的带权路径长度是所有叶结点带权路径长度之和哈夫曼树定义哈夫曼树是带权路径长度最小的二叉树，也称为最优二叉树构造方法是从权值最小的两个结点开始不断合并哈夫曼编码原理在哈夫曼树中，从根到叶结点的路径确定了该叶结点的编码，通常约定左分支为0，右分支为1编码应用优势哈夫曼编码是一种变长编码，根据字符出现频率分配编码长度，使得整体编码长度最短，广泛应用于数据压缩图的基本概念和术语图的定义基本术语图G=V,E由顶点集V和边集E组成，其中•顶点Vertex图中的数据元素V是非空集合，E是V中元素的二元关系•边Edge顶点之间的关系图可以表示元素之间的多对多关系，比•度Degree与顶点相关联的边数，线性表和树更为复杂有向图中分为入度和出度•有向图边有方向，用有序对u,v表•路径Path顶点序列，相邻顶点之示从u到v的边间有边•无向图边无方向，用无序对u,v表•连通图/强连通图任意两顶点之间示u和v之间的边存在路径•权Weight边或弧上的数值特殊图结构•完全图任意两个顶点之间都有边•连通分量无向图的最大连通子图•强连通分量有向图的最大强连通子图•生成树包含图中所有顶点的极小连通子图•DAG有向无环图，常用于表示依赖关系图的存储结构邻接矩阵图的存储结构邻接表On+e O1空间复杂度添加边操作n为顶点数，e为边数在链表头插入新边Od查找邻接点d为顶点的度邻接表是图的一种链式存储结构，它由顶点表和边表组成顶点表通常是一个数组，存储图中所有顶点的信息，每个顶点都有一个指向该顶点所有邻接点的链表对于无向图，每条边在两个顶点的邻接表中都会出现；对于有向图，边只在其起点的邻接表中出现邻接表适合表示稀疏图，因为它只存储图中实际存在的边，空间效率高查找特定顶点的所有邻接点也很方便，只需遍历其邻接表即可然而，要判断两个顶点之间是否有边，需要遍历邻接表，时间复杂度为Od，其中d是顶点的度图的遍历深度优先搜索（）DFS基本思想DFS深度优先搜索类似于树的前序遍历，从某个顶点出发，沿着一条路径一直走到底，然后回溯到上一个顶点，继续探索未访问的路径递归实现通常使用递归实现DFS访问当前顶点，标记为已访问，然后对每个未访问的邻接点递归调用DFS函数非递归实现也可以使用栈实现DFS将起始顶点入栈，循环出栈访问顶点，并将其未访问的邻接点入栈，直到栈为空应用场景4DFS广泛应用于拓扑排序、连通分量识别、路径查找、迷宫生成与求解等问题，是解决图论问题的基本算法之一图的遍历广度优先搜索（）BFS基本思想BFS广度优先搜索类似于树的层次遍历，从某个顶点出发，先访问其所有邻接点，然后再按照同样的方式访问这些邻接点的邻接点，逐层向外扩展BFS能找到从起点到其他顶点的最短路径（边数最少的路径）队列实现BFS通常使用队列来实现将起始顶点入队并标记为已访问，然后循环出队访问顶点，将其所有未访问的邻接点入队并标记，直到队列为空这种实现保证了顶点按照与起始顶点的距离（边数）递增的顺序被访问算法复杂度BFS的时间复杂度为OV+E，其中V是顶点数，E是边数使用邻接矩阵表示图时，复杂度为OV²；使用邻接表表示图时，复杂度为OV+E空间复杂度方面，需要一个队列存储顶点，最坏情况下为OV应用场景BFS广泛应用于寻找无权图的最短路径、网络爬虫、社交网络分析（查找社交距离）、连通性分析等场景在人工智能领域，BFS是求解最短路径问题的基础算法最小生成树算法Prim最小生成树定义连通图的生成树中，权值和最小的生成树算法思想Prim从单个顶点开始，逐步扩展生成树算法过程选择与当前树连接的最小权值边复杂度分析时间复杂度或OV²OE logV最小生成树算法Kruskal算法是求解最小生成树的一种贪心算法，其核心思想是按照边的权值从小到大的顺序选择边，只要不构成环路，就将这条Kruskal边加入生成树中算法从一个只有个顶点而没有边的森林开始，逐步添加边，直到形成一棵包含所有顶点的树n算法的实现通常采用并查集来判断添加一条边是否会形成环路首先将所有边按权值排序，然后依次考察每条边如果边Kruskal的两个顶点不在同一个连通分量中，则将该边加入最小生成树，并合并这两个连通分量算法的时间复杂度为，其中OE logE E是边的数量，主要开销来自于对边的排序算法特别适合于稀疏图（边较少的图）Kruskal最短路径算法Dijkstra算法思想算法过程算法用于求解单源最短路径初始时，源点到自身距离为，到其Dijkstra0问题，即从一个源点到其他所有顶他顶点距离为无穷大每次从未确1点的最短路径它基于贪心策略，定最短路径的顶点中选择距离最小每次选择当前已知最短路径的顶点的顶点，将其标记为已确定，并更进行扩展新与其相邻顶点的距离复杂度分析算法限制使用邻接矩阵实现时，时间复杂度算法要求图中不存在负权边，Dijkstra43为；使用优先队列优化时，时否则算法可能得到错误结果如果OV²间复杂度可降至，其中有负权边，需要使用OE logV VBellman-Ford是顶点数，是边数算法E最短路径算法Floyd实际应用路径规划、网络路由、图形分析1算法实现2使用三重循环和邻接矩阵D[i][j]表示路径长度时间复杂度3OV³，空间复杂度OV²核心思想逐步尝试所有可能的中间顶点，更新最短路径估计算法定义5解决所有顶点对之间最短路径的动态规划算法拓扑排序拓扑排序定义1拓扑排序是将有向无环图DAG的所有顶点排成一个线性序列，使得图中任何一对顶点u和v，如果存在边u→v，则u在序列中出现在v之前这种排序表示了顶点之间的优先关系基于入度的算法2首先找出所有入度为0的顶点，将它们放入队列中然后从队列中取出一个顶点，输出它，并将所有从它出发的边删除（相邻顶点入度减1）重复此过程直到队列为空基于的算法3DFS进行深度优先搜索，在搜索过程中维护一个栈当一个顶点的所有相邻顶点都已访问完成后，将该顶点入栈最后，栈中的顶点序列的逆序即为拓扑排序应用场景4拓扑排序广泛应用于任务调度、课程安排、软件编译依赖分析等场景，帮助确定满足依赖关系的执行顺序关键路径网络模型AOE活动-边表示Activity OnEdge网络是一种带权有向无环图，顶点表示事件，边表示活动，边上的权值表示活动的持续时间整个工程的完成时间取决于从源点到汇点的最长路径，即关键路径关键活动识别关键活动是指那些如果延迟就会导致整个工程延迟的活动这些活动位于关键路径上，它们的时间余量（松弛时间）为零识别关键活动是项目管理中的重要任务时间参数计算为计算关键路径，需要确定四个时间参数事件的最早发生时间ve、最迟发生时间vl、活动的最早开始时间e和最迟开始时间l当e=l时，该活动是关键活动算法实现步骤先通过拓扑排序按顺序计算每个事件的最早发生时间ve，再逆拓扑序计算每个事件的最迟发生时间vl，然后计算每个活动的e和l，最后确定关键活动和关键路径查找的基本概念查找的定义查找的方式查找是根据给定的关键字，在表中找静态查找仅查询表中是否存在满足出与关键字相匹配的记录的过程查条件的记录，不涉及插入和删除操作找表是记录的集合，每个记录通常由关键字和卫星数据组成动态查找在查找的同时，可能还需查找的目的是确定给定关键字在查找要对表进行修改，包括插入新记录和表中是否存在，如果存在，还要确定删除已有记录对应记录的位置，以便进行相应操作查找通常还分为精确查找和范围查找两种类型查找的评价指标平均查找长度ASL需要比较的关键字次数的期望值，是评价查找算法效率的主要指标时间复杂度和空间复杂度分析查找算法的资源消耗情况适用性算法是否适用于特定类型的数据或特定的应用场景顺序查找134算法思想实现方法复杂度分析适用场景顺序查找（通常使用带哨兵的实现方式，时间复杂度最好，最适用于线性表的各种存储结Sequential O1）是最简单的查找算将查找值临时存放在表的末坏，平均空间复构，特别是对于无序表或小Search On On法，从表的一端开始，逐个尾位置，这样可以简化循环杂度平均查找长度规模数据集，但对于大规模O1检查表中元素直到找到匹配终止条件的判断数据的搜索效率较低ASL=n+1/2项或查遍整个表二分查找Olog n O1时间复杂度空间复杂度比顺序查找更高效只需常数额外空间₂log n+1平均查找长度二分查找的ASL值二分查找（Binary Search）是一种高效的查找算法，它利用数据的有序性，将查找范围每次减半，从而快速定位目标元素该算法的前提是数据必须已经排序，且存储结构支持随机访问（如数组）二分查找的基本思想是每次取中间位置的元素与目标值比较，如果相等则查找成功；如果目标值小于中间元素，则在前半部分继续查找；如果目标值大于中间元素，则在后半部分继续查找通过这种方式，每次比较都能排除一半的元素，大大提高查找效率分块查找分块查找原理算法步骤复杂度与性能分块查找（又称索引顺序查找）是介•建立索引表，存储每块的最大值分块查找的时间复杂度取决于块数和于顺序查找和二分查找之间的一种查和起始位置每块的大小假设表长为，分为n m找算法它将查找表分成若干块，块块，则索引表查找的时间复杂度为•对索引表进行二分查找，确定关内元素可以无序，但块间必须有序，块内查找的时间复杂度为Olog m键字所在的块（前一块中的最大关键字小于后一块On/m•在确定的块内进行顺序查找中的最小关键字）当时，平均查找长度最小，约m=√n当表中的数据经常变动时，分块查找查找时先确定关键字所在的块（通常为分块查找的空间复杂度为O√n比较适用，因为只需要保持块间有序，使用索引表和二分查找），然后在块，主要用于存储索引表总体Om而块内可以无序，维护成本较低内进行顺序查找这种方法既利用了而言，分块查找在时间和空间效率上二分查找的高效性，又保持了一定的是顺序查找和二分查找的折中灵活性哈希表和哈希函数哈希概念哈希函数哈希（散列）是一种直接寻址技术，将关键字转换为哈希表地址的函数，1通过哈希函数将关键字映射到表中好的哈希函数应该计算简单、分布的位置，实现时间的查找均匀、冲突少O1哈希冲突常用哈希方法4不同关键字映射到相同地址的现象，直接定址法、除留余数法、数字分3是哈希技术不可避免的问题，需要析法、平方取中法、折叠法等，选通过冲突解决策略处理择取决于关键字特性哈希冲突的处理方法开放定址法链地址法再哈希法当发生冲突时，在哈希表中寻找其他空闲位将哈希表的每个桶实现为一个链表，所有映当哈希表接近饱和时，创建一个更大的新表，置存储元素常见的探测序列包括线性探测射到同一地址的元素都存储在对应的链表中并将原表中的所有元素重新哈希到新表中（每次向后移动固定步长）、二次探测（移这种方法简单灵活，适合处理无法预知的冲这种方法可以保持较低的装填因子，从而维动距离为二次函数）和双重哈希（使用第二突情况，且不会因为表满而导致查找性能骤持良好的查找性能再哈希的代价是需要一个哈希函数计算步长）开放定址法的优点降链地址法的主要缺点是需要额外的指针次性重新计算所有元素的哈希值，但这种操是实现简单，不需要额外空间，但当装填因空间，且可能导致某些链表过长，影响查找作通常可以分摊到多次插入操作中，平均代子增大时，查找效率会显著下降效率价较低排序的基本概念排序的定义排序是将一组无序的记录按照关键字的大小关系重新排列成一个有序序列的过程排序是数据处理中最常用的操作之一，也是算法设计与分析的经典问题排序的分类按存储介质分为内部排序和外部排序；按稳定性分为稳定排序和不稳定排序；按比较类型分为比较排序和非比较排序；按算法思想分为插入、交换、选择、归并等多种类型排序算法的评价指标时间复杂度分析最好、最坏和平均情况下的性能空间复杂度排序过程中需要的额外空间稳定性相同关键字的记录是否保持原有的相对顺序适应性对部分有序数据的处理能力排序的应用场景排序是数据库查询优化、数据分析、信息检索等许多领域的基础操作在实际应用中，通常需要根据数据特性和应用需求选择合适的排序算法，有时甚至需要结合多种算法以获得最佳性能插入排序基本思想插入排序的工作原理类似于玩扑克牌时的理牌过程将一组无序数据分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置算法步骤初始时，将第一个元素视为已排序部分；然后逐个处理后续元素，将其插入到已排序部分的合适位置插入时，从后向前比较并移动已排序元素，直到找到正确位置复杂度分析时间复杂度最好情况On（输入已排序），最坏情况On²（输入逆序），平均情况On²空间复杂度O1，只需要常数级的额外空间是一种原地排序算法特点与应用插入排序是一种稳定的排序算法，适合对基本有序的小规模数据集进行排序它具有实现简单、对部分有序数据效率高的特点，常用作其他复杂排序算法的基础或子步骤希尔排序算法思想希尔排序（Shell Sort）是插入排序的改进版，通过比较相隔一定间隔的元素来进行排序它的基本思想是先将整个待排序序列分割成若干子序列分别进行直接插入排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序间隔序列选择希尔排序的关键是确定步长序列（gap sequence），常用的步长序列包括Shell建议的n/

2、n/

4、...、1或Hibbard提出的2^k-

1、...、

3、1等不同的步长序列会导致算法性能的显著差异，目前尚无最优间隔序列的一般性结论算法实现对于给定的步长gap，将序列分成gap个组，对每组使用插入排序；然后减小gap，重复上述分组和排序过程，直到gap=1，此时进行一次普通插入排序由于前面的步骤已经让数据基本有序，最后一步的排序效率很高性能与应用希尔排序的时间复杂度取决于间隔序列的选择，通常在On log n到On²之间空间复杂度为O1，是一种原地排序算法希尔排序不是稳定排序，但对于中等规模的数据集，其性能往往优于简单的On²算法，被广泛应用于系统程序中冒泡排序冒泡排序原理1冒泡排序是一种简单直观的排序算法，它重复地遍历待排序的序列，比较相邻元素并交换它们的位置，使较大的元素逐渐浮向序列的末端，就像水中的气泡上升一样算法步骤2从序列的第一个元素开始，依次比较相邻的两个元素，如果前者大于后者，则交换它们的位置完成一次遍历后，最大的元素就会被放置在序列的末尾重复上述过程，但每次遍历的长度可以减少1，因为后面的元素已经有序算法优化3标准冒泡排序可以通过引入一个标志位进行优化如果在某一轮遍历中没有发生交换，说明序列已经有序，可以提前结束排序过程此外，还可以记录最后一次交换的位置，减少不必要的比较性能分析4时间复杂度最好情况On（输入已排序），最坏情况On²，平均情况On²空间复杂度O1，只需要一个临时变量用于交换冒泡排序是一种稳定的排序算法，但由于其较高的时间复杂度，通常只适用于小规模数据或教学目的快速排序快速排序是一种高效的排序算法，采用分治策略将待排序序列分为两部分，然后递归地对两部分进行排序其核心是划分操作选择一个基准元素（），将小于基准的元素放在基准的左边，大于基准的元素放在右边，基准元素则处于最终位置pivot快速排序的时间复杂度在平均情况下是，最坏情况（如序列已经有序时）为，但通过随机选择基准元素等优化手段On log n On²可以避免最坏情况空间复杂度为，主要是递归调用栈的开销快速排序是不稳定的排序算法，但由于其高效性，它是实Olog n际应用中最常用的排序算法之一，被广泛应用于标准库和系统排序功能中选择排序基本思想选择排序的核心思想是每次从未排序部分找出最小（或最大）的元素，放到已排序部分的末尾通过不断地选择和交换，最终完成排序算法步骤首先在未排序序列中找到最小元素，将其与序列的第一个元素交换位置；然后在剩余未排序序列中继续查找最小元素，与序列的第二个元素交换；以此类推，直到所有元素均排序完毕复杂度分析时间复杂度无论输入如何，都需要的比较操作，因此最好、最坏和平均情况下的时间复杂度均为空间复杂度，仅需要On²On²O1常数级额外空间特点与应用选择排序是不稳定的排序算法，由于其简单性和对数据移动的最小化（每轮只需一次交换），它在某些特定场景下仍有应用，特别是当数据移动成本高于比较成本时堆排序堆的概念堆排序原理性能分析堆是一种特殊的完全二叉树，分为最堆排序利用堆的特性进行排序，基本时间复杂度堆排序在最好、最坏和大堆和最小堆在最大堆中，每个节思想是首先将待排序序列构建成一平均情况下的时间复杂度均为On点的值都大于或等于其子节点的值；个最大堆，这样最大元素会位于堆顶；其中，建堆的时间复杂度为log n在最小堆中，每个节点的值都小于或然后将堆顶元素与堆的最后一个元素，调整堆的时间复杂度为On On等于其子节点的值堆通常使用数组交换，并将堆的大小减（相当于将1log n表示，对于索引为的节点，其左子节最大元素放到了序列的末尾）；最后i空间复杂度，是一种原地排序O1点索引为，右子节点索引为，重新调整堆，使其满足堆的性质，重2i+12i+2算法父节点索引为复上述过程直到堆的大小为i-1/21⌊⌋堆排序是不稳定的排序算法，但由于其稳定的时间复杂度和On log n O1通过这种方式，可以得到一个升序排的空间复杂度，在对排序稳定性没有列的序列如果使用最小堆，则可以要求的场景下，它是一种很有竞争力得到降序排列的序列的排序算法归并排序应用场景适用于对稳定性有要求的大数据排序1复杂度分析2时间On logn，空间On算法实现3分割和合并两个阶段的递归实现合并操作4将两个有序子序列合并为一个有序序列分治思想5将序列分成两半，递归排序，再合并基数排序基数排序原理1基数排序是一种非比较型排序算法，它根据元素的位值（个位、十位、百位...）进行多次分配和收集，从低位到高位（或从高位到低位）依次进行，最终实现排序算法步骤2首先确定数据的最高位数，然后从最低位（或最高位）开始，依次按照各位的值对数据进行分配和收集每一轮分配是根据当前位的值将元素放入对应的桶中，收集则是按照桶的顺序将元素重新组织成一个序列实现变种基数排序有两种实现方式LSD（Least SignificantDigit），从低位到高位排序；MSD（Most SignificantDigit），从高位到低位排序LSD适合位数接近的数据，而MSD则更适合位数差异较大的数据性能分析4时间复杂度Od*n+r，其中d是位数，n是元素个数，r是基数（如十进制数的基数为10）当d和r都相对较小时，基数排序可以实现接近线性的排序效率空间复杂度On+r，需要额外空间来存储桶和临时数据基数排序是稳定的排序算法各种排序算法的比较排序算法最好时间平均时间最坏时间空间复杂稳定性度插入排序On On²On²O1稳定希尔排序On logn On logn On²O1不稳定冒泡排序On On²On²O1稳定快速排序On logn On logn On²Olog n不稳定选择排序On²On²On²O1不稳定堆排序On lognOn lognOnlognO1不稳定归并排序OnlognOnlognOnlognOn稳定基数排序Odn+r Odn+r Odn+r On+r稳定外部排序的基本概念外部排序定义基本步骤性能考量外部排序是指待排序的数据量大，无法全部加•划分阶段将大文件分成若干个能够装入外部排序的性能主要受I/O操作的影响，因此载到内存中进行排序，需要借助外部存储（如内存的小文件（称为归并段或顺串）优化策略常常围绕如何减少I/O次数展开关磁盘）来辅助排序的过程外部排序通常采用键指标包括归并路数（一次能够归并的小文排序-归并的策略先将数据分成多个能装入件数量）、归并段长度、缓冲区大小以及读写•内部排序阶段对每个小文件在内存中进内存的块，对每个块进行内部排序，然后再进操作的并行程度通过选择合适的内部排序算行排序行多路归并法和归并策略，可以显著提高外部排序的效率•归并阶段将已排序的小文件归并成一个大的有序文件•如果归并后的文件仍然较大，可能需要多次归并多路归并排序归并过程多路归并基本概念为每个输入文件分配一个缓冲区，多路归并是外部排序的核心操作，1每次从所有缓冲区中选择最小或最它将多个已排序的序列合并成一个大元素输出，并从对应文件读入新更大的有序序列元素复杂度分析归并优化策略路归并排序的时间复杂度为增加归并路数可减少归并趟数，但k Onlog4，其中是元素总数，是归并路每趟归并的时间会增加；合理分配k nk3数；磁盘次数与归并趟数和数据内存缓冲区和使用优先队列可提高I/O量有关效率替换选择和败者树替换选择排序败者树应用优势替换选择是一种生成初始归并段的算法，它能败者树是一种用于多路归并的数据结构，它可替换选择和败者树的结合使用可以显著提高外够产生长度超过内存容量的有序段算法过程以在k路归并中以Olog k的时间找出k个元素部排序的效率替换选择减少了归并趟数，而是维护一个内存中的堆结构，不断从输入流中的最小值败者树是一棵完全二叉树，每个败者树则减少了每趟归并中选择最小元素的时读取记录，如果记录值大于等于堆顶，就将其内部节点存储的是在该节点比赛中失败的选手间复杂度这两种技术共同作用，使得外部排加入当前归并段；否则，将其加入下一个归并通过这种结构，每次找出最小元素后，只需要序能够处理超大规模的数据集，广泛应用于数段这种方法可以生成平均长度约为内存容量Olog k的时间更新树结构，大大提高了多路据库系统、大数据处理框架等需要处理海量数两倍的初始归并段，从而减少后续归并的趟数归并的效率据的场景考试重点和解题技巧重点内容重点掌握线性表、栈、队列、树和图的基本操作和实现方法，理解各种排序算法的原理和性能分析，熟悉查找算法的适用条件特别注意二叉树的遍历、图的搜索算法、动态规划和贪心策略等常见考点解题技巧分析问题时，先明确所需的数据结构，再考虑最适合的算法解答算法题时，注意时间和空间复杂度的分析，能否通过改进算法提高效率编写伪代码或实际代码时，注意边界条件和特殊情况的处理实战练习多做习题和上机实验，尤其是模拟题和往年考题，熟悉题型和考查方式将抽象的数据结构和算法与具体的应用场景结合起来，加深理解和记忆通过手动模拟算法执行过程，检验自己的理解是否正确考试策略考试时，先浏览全卷，合理分配时间，先做有把握的题目解答问题时条理清晰，步骤完整，必要时辅以图表说明对于大题，可以先列出解题思路和主要步骤，再补充详细内容，避免遗漏关键点总结和复习建议理论与实践结合建立知识联系小组讨论学习数据结构不仅要理数据结构和算法之组织小组讨论，相解概念，还要掌握间存在紧密联系，互解答疑问，交流实现和应用通过尝试梳理它们之间解题思路和技巧编写代码实现各种的关系，如不同排通过向他人讲解知数据结构和算法，序算法的比较、不识点，检验自己的加深对理论知识的同数据结构的选择理解，发现知识盲理解，培养解决实依据等，形成完整点，提高学习效率际问题的能力的知识体系制定复习计划根据个人情况制定有针对性的复习计划，合理安排时间，确保重点难点得到充分复习在考试前进行全面回顾，强化记忆，提高应试能力。