《数据结构与算法-周NO》课件

数据结构与算法欢迎来到《数据结构与算法》课程！本课程将带您深入了解计算机科学中最基础、最核心的概念通过学习各种数据结构和算法，您将掌握解决复杂问题的思维方式和技巧，为您的编程能力奠定坚实基础在这个信息爆炸的时代，数据的高效组织和处理变得尤为重要无论是在日常应用程序开发中，还是在面对大数据、人工智能等前沿领域的挑战时，扎实的数据结构与算法知识都将是您最有力的武器课程介绍课程目标学习内容考核方式培养学生的逻辑思维能本课程将涵盖线性结构课程考核包括平时作业力和问题分析能力，使（数组、链表、栈、队（）、编程实践（30%学生掌握数据的组织方列）、非线性结构（树）和期末考试（30%式和处理算法，并能在、图）以及各种常见算）鼓励学生在课40%实际编程中灵活应用各法（排序、查找、递归堂上积极参与讨论，并种数据结构和算法解决、动态规划等）的原理通过实际编程加深对理复杂问题和实现论知识的理解什么是数据结构？定义重要性数据结构是指数据元素相互之间存在的一种或多种特定关系良好的数据结构可以提高算法的效率，降低程序的时间复杂的集合它研究的是数据的逻辑结构和物理结构以及它们之度和空间复杂度在处理大规模数据时，合适的数据结构往间的相互关系，并对这种结构定义相应的运算往能带来指数级的性能提升简单来说，数据结构就是组织和存储数据的方式，使得数据掌握数据结构不仅是编程的基础，也是理解计算机系统工作可以高效地被访问和修改不同的数据结构适用于不同的应原理的窗口无论是操作系统、数据库还是网络通信，都离用场景，选择合适的数据结构是程序设计的关键不开各种数据结构的支持什么是算法？定义算法是解决特定问题的一系列操作步骤它是一种被定义好的、可计算的解决问题的方法，通常表示为一系列有限的、清晰的指令算法可以看作是程序的灵魂，它决定了程序如何处理输入数据并产生期望的输出一个好的算法应该能够正确、高效地解决问题特性好的算法应具备以下特性输入算法必须有零个或多个输入•输出算法必须产生至少一个输出•确定性算法的每一步都必须明确无误•有限性算法必须在有限步骤后终止•可行性算法的每一步都必须是可执行的•数据结构与算法的关系相互依存相互影响1数据结构为算法提供了操作对象算法随数据结构变化而调整2相互转化相互补充4算法可视为对数据结构的操作3共同构成计算机科学的核心数据结构与算法就像是鱼和水的关系，密不可分数据结构是静态的，它描述了数据元素之间的关系；而算法是动态的，它描述了处理数据的方法数据结构的选择会直接影响算法的效率同样，算法的设计也需要考虑所操作的数据结构特性在实际问题解决中，往往需要结合二者的优势，找到最优解决方案时间复杂度定义时间复杂度是对算法执行时间的量度，它表示算法的运行时间与输入规模之间的关系时间复杂度通常记为，其中表示输入数据的规模Tn n时间复杂度关注的不是算法的实际执行时间，而是算法执行时间随输入规模增长的变化趋势它能帮助我们在不实际运行算法的情况下，就可以分析算法的效率大表示法O大表示法是表示时间复杂度的一种数学符号，用于描述算法的渐进行为O它表示的是算法执行时间的上界常见的时间复杂度有常数时间复杂度，与输入规模无关•O1对数时间复杂度，如二分查找•Olog n线性时间复杂度，如顺序查找•On线性对数时间复杂度，如归并排序•On log n平方时间复杂度，如冒泡排序•On²指数时间复杂度，如某些回溯算法•O2^n空间复杂度定义1空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度空间复杂度通常记为，其Sn中表示输入数据的规模n空间复杂度包括两部分算法的固定部分（如代码、常量、变量等占用的空间）和与问题规模相关的可变部分（如递归栈空间、动态分配的空间等）在分析空间复杂度时，我们通常只关注与问题规模相关的部分计算方法2计算空间复杂度的基本方法是找出算法在执行过程中同时占用的最大存储空间，并用大表示法表示O常见的空间复杂度有常数空间复杂度，与输入规模无关•O1线性空间复杂度，如存储输入数据的副本•On平方空间复杂度，如二维数组•On²时空权衡3在算法设计中，常常需要在时间复杂度和空间复杂度之间做出权衡有些算法可以通过牺牲空间换取时间，即使用更多的存储空间来提高算法的执行速度；有些算法则相反，通过增加计算量减少存储空间的使用权衡的最终目标是在满足问题需求的前提下，找到最优的解决方案线性结构概述定义与特点常见线性结构12线性结构是一种最简单且最基常见的线性结构包括数组、链本的数据结构，它的特点是数表、栈和队列这些结构在计据元素之间存在一对一的关系算机科学中被广泛应用，是构在线性结构中，除了第一个建更复杂数据结构的基础它和最后一个元素，每个元素都们各自有不同的特点和适用场有且仅有一个前驱和一个后继景，掌握这些基本结构是学习数据结构的第一步线性结构的操作3对线性结构的基本操作包括插入、删除、查找、修改等这些操作的实现方式和效率在不同的线性结构中有所差异理解这些差异有助于在实际应用中选择合适的数据结构数组O1On访问效率插入删除效率/数组元素在内存中连续存储，支持通过索在数组中间位置插入或删除元素需要移动引直接访问，是最基础的数据结构其他元素，效率较低固定空间分配大多数编程语言中，数组需要预先分配固定大小的连续内存空间数组是最基础的数据结构，它由相同类型的元素按顺序组成，在内存中占据连续的空间数组的每个元素都有一个索引，用于标识它在数组中的位置通过索引，我们可以在常数时间内访问数组中的任何元素，这是数组的最大优势数组的应用场景非常广泛，包括但不限于存储和处理固定数量的数据；实现矩阵运算；作为其他数据结构（如栈、队列、堆等）的底层实现；在编译器和解释器中用于符号表等链表单链表单链表中的每个节点包含数据域和指向下一个节点的指针域单链表的特点是只能从头到尾遍历，不能反向访问单链表适用于只需要单向遍历的场景双链表双链表中的每个节点除了数据域，还包含指向前一个节点和后一个节点的两个指针域双链表支持双向遍历，在需要频繁地向前和向后查找数据的场景中更为高效循环链表循环链表是一种首尾相连的链表在单循环链表中，尾节点的指针指向头节点；在双循环链表中，头节点的前指针指向尾节点，尾节点的后指针指向头节点循环链表适用于需要周期性处理数据的场景链表是一种通过指针将离散的内存空间连接起来的数据结构与数组不同，链表不需要连续的内存空间，它通过节点来存储数据，每个节点包含数据本身和指向其他节点的指针链表的优点是插入和删除操作高效（时间复杂度为），不需要预先分配内存；缺点是O1随机访问效率低（需要从头开始遍历），且每个节点都需要额外的空间来存储指针栈应用场景函数调用、表达式求值、括号匹配1操作2入栈和出栈push pop定义3后进先出的线性数据结构LIFO栈是一种特殊的线性表，它只允许在一端（通常是表的末端，称为栈顶）进行插入和删除操作栈遵循后进先出（，Last InFirst Out）的原则，即最后入栈的元素最先出栈LIFO栈的基本操作包括入栈（），将元素压入栈顶；出栈（），将栈顶元素弹出；获取栈顶元素（），查看栈顶元素但不删push poppeek/top除；判断栈是否为空等这些操作的时间复杂度均为O1栈在计算机科学中有着广泛的应用，包括但不限于函数调用的实现（调用栈）；表达式的计算和转换；编译器中的语法分析；浏览器的前进后退功能；软件中的撤销（）功能等undo队列定义1先进先出的线性结构FIFO操作2入队和出队enqueue dequeue应用3任务调度、消息传递、缓冲区队列是一种特殊的线性表，它只允许在一端（队尾）进行插入操作，在另一端（队头）进行删除操作队列遵循先进先出（First InFirst Out，）的原则，即最先入队的元素最先出队FIFO队列的基本操作包括入队（），将元素加入队尾；出队（），将队头元素移出；获取队头元素（），查看队头元enqueue dequeuepeek/front素但不删除；判断队列是否为空等在队列的实现中，常见的有顺序队列（基于数组）和链式队列（基于链表）除了基本的单向队列，还有双端队列（），允许在队列的两端进行插入和删除操作；优先队列，元素的出队顺序由元素的优先级决定，而不deque是入队顺序；循环队列，为了解决顺序队列中的假溢出问题非线性结构概述树结构图结构散列结构树是一种层次性的数据结构，由节点和连图是一种更为复杂的非线性数据结构，由散列（哈希）是一种通过特定函数将关键接节点的边组成树中的每个节点可以有顶点和连接顶点的边组成在图中，任意字映射到表中位置的数据结构哈希表具多个后继，但只有一个前驱（根节点除外两个顶点之间都可能存在连接关系，没有有快速查找、插入和删除的特点，在处理，根节点没有前驱）树结构在表示具有固定的层次概念图适合表示网络结构的大量数据时尤为有效哈希表是实现关联层次关系的数据时非常有效数据，如社交网络、交通网络等数组、集合等高级数据结构的基础非线性结构与线性结构不同，它没有明确的首尾关系，数据元素之间的关系比较复杂在非线性结构中，一个元素可能与多个元素相关联，而不像线性结构那样只与前驱和后继有关树定义基本概念12树是由（）个有限节点组成的树的基本概念包括节点（存储数n n≥0集合当时，称为空树在任据的基本单位）、根节点（树的顶n=0意一棵非空树中，有且仅有一个特部节点，没有父节点）、父节点与定的称为根的节点当时，其子节点（有连接关系的节点）、叶n1余节点可分为（）个互不相节点（没有子节点的节点）、节点m m0交的有限集，每个集合本身又是一的度（子节点的数量）、树的度（棵树，称为原树的子树所有节点中最大的度）、层次（根节点为第层，依次递增）、树的1高度（最大层次数）树的类型3常见的树类型包括二叉树（每个节点最多有两个子节点）、满二叉树（每个节点要么是叶节点，要么有两个子节点）、完全二叉树（除最后一层外，每层都被填满，最后一层从左到右填充）、二叉搜索树（左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值）等二叉树定义性质二叉树是一种特殊的树形结构，它的特点是每个节点最多只二叉树具有以下重要性质有两个子节点，分别称为左子节点和右子节点二叉树的子第层上的节点数目最多为•i2^i-1i≥1树也是二叉树，并且左右子树有序，不能随意交换深度为的二叉树至多有个节点•k2^k-1k≥1在实际应用中，二叉树是最常用的树型结构，它既简单又强任何一棵二叉树，如果叶节点数为，度为的节点数•n02大，是构建其他复杂树形结构的基础为，则n2n0=n2+1具有个节点的完全二叉树的深度为•n log2n+1⌊⌋对于完全二叉树，若从上至下、从左至右编号，则编号•为的节点的左子节点编号为，右子节点编号为i2i2i+1，父节点编号为i/2⌊⌋二叉树的遍历前序遍历前序遍历（）的访问顺序是根节点左子树右子树Preorder Traversal→→这意味着我们首先访问当前节点，然后递归地对其左子树进行前序遍历，最后递归地对其右子树进行前序遍历前序遍历的一个典型应用是创建二叉树的复制品，因为我们首先创建根节点，然后递归地复制左右子树中序遍历中序遍历（）的访问顺序是左子树根节点右子树Inorder Traversal→→这意味着我们首先递归地对当前节点的左子树进行中序遍历，然后访问当前节点，最后递归地对其右子树进行中序遍历对于二叉搜索树，中序遍历可以得到一个按照关键字升序排列的序列，这是中序遍历的一个重要特性和应用后序遍历后序遍历（）的访问顺序是左子树右子树Postorder Traversal→→根节点这意味着我们首先递归地对当前节点的左子树进行后序遍历，然后递归地对其右子树进行后序遍历，最后访问当前节点后序遍历常用于释放树占用的内存空间，因为我们必须先释放子节点的内存，然后才能安全地释放父节点的内存平衡二叉树树红黑树AVL树是最早被发明的自平衡二叉搜索树在树中，红黑树是另一种常用的自平衡二叉搜索树，它通过为每个节AVL AVL任意节点的左右子树高度差不超过每当插入或删除操作点着色（红色或黑色）来保持树的平衡红黑树的平衡条件1导致树失去平衡时，就会通过旋转操作来重新平衡相对宽松，因此插入和删除操作引起的旋转次数通常少于树AVL树的特点是查找、插入和删除操作的时间复杂度均为AVL，这使得它在需要频繁查找的场景中表现优异然红黑树需要满足以下性质根节点是黑色的；每个叶节点（Olog n而，频繁的旋转操作可能会影响插入和删除的效率节点）是黑色的；如果一个节点是红色的，则它的两个NIL子节点都是黑色的；从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点平衡二叉树是为了解决普通二叉搜索树在最坏情况下退化为链表的问题通过保持树的平衡，可以确保树的高度始终保持在级别，从而保证各种操作的效率Olog n堆定义操作堆是一种特殊的完全二叉树，分为最大堆的基本操作包括堆和最小堆在最大堆中，父节点的值插入元素将新元素加入堆的末尾•总是大于或等于其子节点的值；在最小，然后上浮（重新排列以满足堆的堆中，父节点的值总是小于或等于其子性质）节点的值删除最大最小元素将堆顶元素•/由于堆是完全二叉树，它通常使用数组（最大最小元素）移出，用堆的/来实现，这样可以通过索引快速找到节最后一个元素替代，然后下沉（重点的父节点和子节点，而不需要使用额新排列以满足堆的性质）外的指针建堆将一个无序数组转换为堆•应用堆的主要应用包括堆排序一种基于堆的高效排序算法•优先队列在操作系统的任务调度、图算法（如最短路径）等中广泛应•Dijkstra用获取集合中的最大最小元素如获取流数据中的中位数•/问题找出个数中最大最小的前个数•TopK N/K图定义1图是一种由顶点（或称节点）和边组成的非线性数据结构形式上，图可以表示为G，其中是一组顶点，是一组边，用于连接这些顶点G=V,E VE图可以用来表示许多现实世界中的关系，如社交网络中的人际关系、交通网络中的道路连接、互联网中的网页链接等图是一种非常灵活和强大的数据结构基本概念2图的基本概念包括顶点（）图中的数据元素•Vertex边（）连接两个顶点的线段或弧•Edge有向图边有方向性•无向图边没有方向性•权重图边带有权重或成本•路径顶点的序列，其中任意两个连续顶点之间都有一条边•连通图任意两个顶点之间都存在路径•环起点和终点相同的非平凡路径•图的表示邻接矩阵邻接表邻接矩阵是表示图的一种方式，它使用一个二维数组来表示邻接表是图的另一种表示方式，它为每个顶点维护一个列表顶点之间的连接关系在邻接矩阵中，矩阵的行和列分别对，列表中包含与该顶点相邻的所有顶点通常，这个列表可应图中的顶点，矩阵的元素表示两个顶点之间是否存在边以用链表、数组或其他合适的数据结构实现对于有向图，每个顶点的邻接表包含该顶点的所有出边；对对于无权图，矩阵元素通常是或，表示是否存在边；对于无向图，每条边在两个顶点的邻接表中都会出现01于带权图，矩阵元素表示边的权值，不存在的边通常用特殊邻接表的优点是对于稀疏图能够节省空间（空间复杂度为值（如无穷大）表示），并且可以快速遍历与特定顶点相连的所有顶点OV+E邻接矩阵的优点是实现简单，可以快速判断两个顶点之间是；缺点是无法快速判断两个特定顶点之间是否存在边，需要否有边（时间）；缺点是空间复杂度为，对于稀在邻接表中搜索（最坏情况下为时间）O1OV²OV疏图（边数远小于顶点数的平方）会造成空间浪费图的遍历深度优先搜索（）DFS深度优先搜索是一种沿着图的深度方向尽可能深入探索的方法的基本思想是从起始顶点出发，沿着一条路径一直走到底，直到不能再继续前进；然DFS后回溯到上一个顶点，选择另一条路径继续前进通常使用递归或栈来实现递归实现更为简洁，但在处理大规模图时可能会导致栈溢出；使用显式栈可以避免这个问题DFS的应用包括拓扑排序、寻找连通分量、路径查找（如迷宫问题）、判断图是否是二分图等DFS广度优先搜索（）BFS广度优先搜索是一种层层推进的搜索方法的基本思想是从起始顶点出发，先访问所有相邻的顶点，然后再从这些顶点出发，访问它们相邻的未访问BFS顶点，以此类推通常使用队列来实现在访问一个顶点时，将其标记为已访问，并将其未访问的邻居加入队列BFS的应用包括寻找无权图中的最短路径、网络爬虫、社交网络中的六度空间理论、寻找两点之间的最少跳数等BFS排序算法概述算法平均时间复杂最坏时间复杂空间复杂度稳定性度度冒泡排序稳定On²On²O1选择排序不稳定On²On²O1插入排序稳定On²On²O1希尔排序不稳定On log n On²O1归并排序稳定On logn On logn On快速排序不稳定On logn On²Olog n堆排序不稳定On logn On lognO1排序算法是计算机科学中最基本、最重要的算法之一它的目标是将一组数据按照特定的顺序（如升序或降序）重新排列根据实现方式和性能特点，排序算法可以分为比较排序（如冒泡排序、选择排序、插入排序等）和非比较排序（如计数排序、桶排序、基数排序等）评价排序算法的指标主要包括时间复杂度（平均情况、最好情况、最坏情况）、空间复杂度、稳定性（排序前后相等元素的相对位置是否改变）、是否为原地排序（是否需要额外的存储空间）等在实际应用中，需要根据数据的特点和需求选择合适的排序算法冒泡排序基本原理冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成算法步骤从第一个元素开始，比较每一对相邻元素如果第一个比第二个大，就交换它们对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对这步做完后，最后的元素应该会是最大的数针对所有的元素重复以上的步骤，除了最后一个持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较性能分析冒泡排序的平均和最坏时间复杂度都是，最好的时间复杂度是，即On²On当数列已经是排好序的情况空间复杂度为，是一种原地排序算法冒O1泡排序是稳定的排序算法，相等元素的相对位置不会改变虽然冒泡排序性能不佳，但由于实现简单，常用于教学在实际应用中，当数据量较小或数据已经接近排序状态时，冒泡排序可能是一个不错的选择选择排序找最小值在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置这一步需要遍历整个未排序区间，找出其中的最小值交换位置将找到的最小元素与未排序区间的第一个元素交换位置，使该最小元素成为已排序区间的一部分如果最小元素已经在正确的位置上，可以省略交换步骤重复过程从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾重复这个过程，直到所有元素均排序完毕选择排序是一种简单直观的排序算法它的工作原理是首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾以此类推，直到所有元素均排序完毕选择排序的时间复杂度为，这与输入数据的顺序无关，因为无论如何它都需要找到最小值并交On²换数据空间复杂度为，仅需要一个临时变量用于交换元素值选择排序是不稳定的排序算法O1，因为它可能会改变相等元素的相对位置插入排序初始状态1将第一个元素视为已排序序列，其余元素视为未排序序列已排序序列初始只包含一个元素，就是数组的第一个元素取出元素2从未排序序列中取出第一个元素，称为待插入元素这个元素是未排序区间的第一个元素，也是已排序区间后面的那个元素寻找位置3在已排序序列中从后向前扫描，找到合适的位置插入这一步需要将已排序序列中大于待插入元素的元素向后移动一位，为待插入元素腾出空间插入元素4将待插入元素放入找到的位置此时已排序序列增加一个元素，未排序序列减少一个元素重复步骤到步骤，直到未排序序列为空，排序完成24插入排序是一种简单直观的排序算法它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入插入排序在实现上，通常采用排序（即只需用到的额in-place O1外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间插入排序的平均时间复杂度为，最坏时间复杂度为，最好时间复杂度为空间复杂度为On²On²On插入排序是稳定的排序算法，因为它只在找到插入位置时才进行交换，不会改变相同元素的相对顺序O1希尔排序选择增量序列按增量分组1确定一个增量序列，如序列将序列按增量分成若干子序列Knuth2减小增量对子序列排序4缩小增量再次分组排序，直至增量为3对每个子序列进行插入排序1希尔排序是插入排序的一种更高效的改进版本它的基本思想是先将整个待排序的记录序列分割成为若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序希尔排序的关键在于增量序列的选择常用的增量序列有增量序列（）和增量序列（Shell n/2,n/4,n/8,...,1Knuth1,4,13,40,...,）等不同的增量序列会导致算法性能的差异3^k-1/2希尔排序的平均时间复杂度取决于增量序列，通常认为是到之间希尔排序是不稳定的排序算法，因为相同的元素可能在不同On logn On^2的子序列中被分开排序，导致它们的相对位置发生变化归并排序分解将待排序序列分成若干个子序列，每个子序列包含一个元素（认为一个元素是已经排好序的）分解的过程通常采用递归的方式，不断将序列一分为二，直到每个子序列只包含一个元素合并将已有序的子序列合并，得到完全有序的序列合并的过程是比较两个子序列的第一个元素，将较小的元素移入新序列，并不断重复此过程，直到某一子序列为空，再将另一子序列的剩余元素直接复制到新序列末尾递归回溯随着递归的展开和回溯，不断将已排序的子序列合并成更大的有序序列，最终得到一个完全有序的序列这个过程像是一棵二叉树，从叶子节点开始，逐步向上合并到根节点归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法（Divide and）的一个非常典型的应用归并排序的核心思想是如果要排序一个数组，我们先把Conquer数组分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起归并排序的时间复杂度为，这也是基于比较的排序算法所能达到的最优时间复杂度Onlogn空间复杂度为，因为合并操作需要额外的存储空间归并排序是稳定的排序算法，合并On操作中保持了元素的相对顺序快速排序选择基准划分区域12从数列中挑出一个元素，称为基准（重新排序数列，所有比基准值小的元素摆）基准的选择会影响算法的效率放在基准前面，所有比基准值大的元素摆pivot，常见的选择方法有选取第一个元素、放在基准后面（相同的数可以到任一边）选取最后一个元素、选取中间元素、随机在这个分区结束之后，该基准就处于数选取或三数取中法（取首、尾、中三个元列的中间位置这个称为分区（素的中位数））操作partition递归排序3递归地把小于基准值元素的子数列和大于基准值元素的子数列排序递归的最底部情形是数列的大小是或，这时已经被排序好了如果要排序的数列只有或个元素，那么返回原0101数列即可，否则，继续递归排序左右两个分区快速排序是一种分而治之的算法，它通过将一个数组分成较小的两个数组来实现排序，一个数组的所有值都小于基准值，另一个数组的所有值都大于基准值快速排序的关键在于划分区域的操作，通过一次扫描，将数列分成两部分快速排序的平均时间复杂度为，最坏时间复杂度为（当待排序列为正序或逆序时）OnlognOn²空间复杂度为，主要是递归调用栈空间的开销快速排序是不稳定的排序算法，在划分Olog n过程中，相等元素可能会被划分到不同的区域，导致它们的相对位置发生变化。