[计算机科学]基本数据结构课件

计算机科学基本数据结构导学欢迎大家参加基本数据结构课程！数据结构是计算机科学的基石，它们为程序设计和算法实现提供了基础组织框架作为一名程序员，掌握数据结构至关重要，它将帮助你编写更高效、更优雅的代码本课程将系统介绍各种基本数据结构，包括线性结构（如数组、链表、栈、队列）和非线性结构（如树、图、哈希表），帮助你深入理解这些结构的特点、实现方式和应用场景数据结构定义与分类数据结构的概念数据结构的分类数据结构是计算机存储、组织和管理数据的方式它是相互之间从逻辑上看，数据结构主要分为线性结构和非线性结构两大类存在一种或多种特定关系的数据元素的集合，不仅包含数据元素线性结构中的数据元素之间存在一对一的关系，比如数组、链本身，还包含数据元素之间的关系表、栈和队列等在实际编程中，选择适当的数据结构可以大大提高程序的效率和可维护性因此，理解各种数据结构的特点和适用场景对于程序员来说至关重要数据结构与算法的关系高效算法最优数据结构+最佳算法实现算法设计针对具体问题的解决方案数据结构数据组织和存储的基础框架算法是解决特定问题的一系列操作步骤，而数据结构是这些操作的载体和对象选择合适的数据结构对算法效率具有决定性影响例如，在大数据集上进行频繁查找操作时，使用哈希表比使用链表能显著提高效率数据抽象与抽象数据类型ADT抽象数据类型的定义接口与实现分离ADT的实际运用抽象数据类型ADT是一种数学模型，它ADT强调接口与实现的分离，用户只需通例如，栈可以被定义为一个ADT，它支持定义了一组对数据的操作，而不关心这些过定义好的接口操作数据，而无需了解内push（入栈）、pop（出栈）和peek操作的具体实现通过ADT，程序员可以部结构这种分离使得程序更加模块化，（查看栈顶元素）等操作，而不关心这些专注于数据的逻辑结构和行为，而不必考提高了代码的可维护性和可重用性操作的底层实现是使用数组还是链表虑底层的实现细节线性结构概述线性关系顺序性访问方式元素之间一对一连接有明确的前驱后继可以连续或跳跃访问线性结构是最基本的数据结构类型，其特点是数据元素之间存在一对一的线性关系在这种结构中，除了第一个和最后一个数据元素，其他数据元素都有唯一的前驱和后继线性结构的这种简单性使它成为许多复杂数据结构的基础数组定义与存储——连续内存分配下标访问机制多维数组数组在内存中占据连续的存储空间，每个数组使用下标（索引）来访问元素，通常元素占用相同大小的内存这种连续性使从0开始在计算机内部，访问数组元素得数组能够通过基地址和偏移量快速计算arr[i]实际上是通过计算基地址+i*元素大出任意元素的内存地址，从而实现O1时小来定位内存位置的这种机制使得数组间复杂度的随机访问成为最基本也是最高效的数据结构之一数组主要操作操作时间复杂度说明访问O1通过索引直接访问元素查找On查找特定元素需要线性扫描插入On可能需要移动多个元素删除On可能需要移动多个元素数组是一种基本的数据结构，其特点是支持快速的随机访问，但在插入和删除操作上效率较低这是因为在数组中间进行插入或删除操作时，需要移动大量元素以保持数组的连续性数组应用案例数组在计算机科学中有着广泛的应用在元素统计方面，可以利用数组索引直接对应元素类型，实现高效的频率计数例如，统计字符出现频率时，可以使用一个大小为256的数组，将ASCII码作为索引，对应位置的值表示出现次数矩阵运算是数组的另一个重要应用领域二维数组可以直观地表示矩阵，实现矩阵加法、乘法等操作在图像处理中，像素矩阵通常用二维数组表示，每个元素代表一个像素点的颜色值，通过对数组元素的操作实现图像旋转、缩放、滤波等处理动态数组与静态数组静态数组动态数组静态数组在声明时必须指定大小，且创建后大小不可更改其内动态数组可在运行时根据需要调整大小，通常通过重新分配更大存在编译时或运行初期就已分配，使用简单但缺乏灵活性的内存块并复制原有数据实现这提供了更高的灵活性，但有一定的性能开销在C/C++中，静态数组直接在栈上分配，如int arr

[10]这种方式分配和释放都很快，但数组大小必须是常量，且超出范围访问不会被自动检测链表基本概念——结点（Node）包含数据域和指针域指针（Pointer）连接各个结点链表（Linked List）通过指针连接的结点序列链表是一种线性数据结构，它由一系列结点组成，每个结点包含数据域和指针域数据域存储实际数据，指针域存储下一个结点的地址，通过这种方式将各个结点连接成一个链式结构链表的最后一个结点通常指向空（NULL），表示链表的结束单链表基本操作初始化链表创建一个空链表，通常只需要一个指向头结点的指针头结点可以不存储数据，仅作为链表的入口，也可以直接使用第一个数据结点作为头结点插入操作在链表中插入新结点主要涉及修改指针头部插入只需修改新结点的next指针和头指针；中间插入需要先找到插入位置的前一个结点，然后调整指针关系；尾部插入需要遍历到链表末尾，然后添加新结点删除操作删除结点时，需要找到要删除结点的前一个结点，修改其next指针跳过要删除的结点，然后释放被删除结点的内存删除头结点是一种特殊情况，只需修改头指针遍历链表单链表与数组比较O1链表插入/删除位置已知情况下的时间复杂度On链表查找最坏情况下的时间复杂度O1数组随机访问通过索引直接定位元素On数组插入/删除需要移动元素的时间复杂度链表和数组是两种基本的线性数据结构，它们在不同场景下各有优势在空间利用率方面，链表不需要预先分配固定大小的内存，能够根据需要动态分配空间，避免了空间浪费但链表每个结点除了存储数据外，还需要额外的空间存储指针，这增加了一定的内存开销双向链表与循环链表循环链表双向链表双向循环链表在循环链表中，最后一双向链表的每个结点有双向循环链表结合了循个结点的指针不是两个指针域，分别指向环链表和双向链表的特NULL，而是指向链表前一个结点和后一个结点，头结点的前驱指向的头结点，形成一个点这种结构支持双向尾结点，尾结点的后继环这种结构特别适合遍历，并且可以在O1指向头结点这种结构需要循环处理的场景，时间内删除给定结点而提供了最大的灵活性，如操作系统中的进程轮无需知道其前驱但也增加了结构复杂转调度性链表实际应用LRU缓存淘汰机制多任务调度最近最少使用（Least Recently操作系统中的多任务轮转调度常使用Used，LRU）缓存淘汰算法通常使用循环链表实现每个结点代表一个任双向链表实现每当访问一个缓存务，CPU按顺序处理链表中的任务，项，就将其移到链表头部，当缓存空处理完一个任务后移动到下一个，形间不足时，移除链表尾部（最久未使成循环用）的项多项式表示链表可以有效表示稀疏多项式，每个结点存储一个非零项的系数和指数这种表示方法特别适合多项式加、减、乘等运算，避免了数组表示中的空间浪费栈定义与特点——压栈Push查看栈顶Peek将新元素添加到栈顶查看栈顶元素但不移除判空isEmpty出栈Pop检查栈是否为空移除并返回栈顶元素栈是一种遵循后进先出LIFO,Last InFirst Out原则的线性数据结构在栈中，所有操作都在一端进行，这一端称为栈顶栈限制了数据的访问方式，只允许在一端进行插入和删除操作，这种限制使得栈特别适合某些特定的应用场景栈的顺序与链式实现数组实现栈链表实现栈使用数组实现栈时，通常将数组的一端定义为栈底，另一端作为链表实现栈时，通常将链表的头部作为栈顶push操作创建新栈顶需要一个指针top跟踪栈顶位置，push操作增加top并结点并插入到链表头部，pop操作移除头结点并返回其数据在新位置存储元素，pop操作返回top位置的元素并减少top数组实现的优点是简单高效，支持随机访问；缺点是容量固定，可能需要考虑扩容策略，这会导致某些操作的时间复杂度偶尔达到On栈的应用案例括号匹配函数调用栈浏览器历史在编译器和代码编辑器中，使用栈检查括操作系统和编程语言运行时使用栈管理函号是否匹配是一个经典应用遇到开括号数调用每次函数调用，系统将返回地时入栈，遇到闭括号时与栈顶元素比较，址、参数和局部变量等信息压入栈中，函如果匹配则出栈，最终栈为空表示所有括数返回时弹出这些信息这种机制支持了号匹配递归调用和函数的正常执行顺序队列定义与应用——入队Enqueue在队尾添加新元素队列处理元素按FIFO原则依次处理出队Dequeue移除队首元素队列是一种遵循先进先出FIFO,First InFirst Out原则的线性数据结构与栈不同，队列在两端进行操作一端队尾用于添加元素，另一端队首用于移除元素这种特性使队列特别适合需要按到达顺序处理数据的场景顺序队列与循环队列入队操作空间复用1循环队列中，rear指针增加后对数组长度取模元素出队后，相应位置可重新使用2判空与判满4出队操作3特殊标志或计数器区分空和满front指针增加后对数组长度取模顺序队列是使用数组实现的队列，其中队首和队尾由两个指针front和rear标记简单实现中，随着元素入队和出队，指针不断向前移动，最终可能导致假溢出问题——尽管数组中有空闲空间，但因为指针达到数组末尾而无法添加新元素队列的实际应用操作系统任务队列打印任务管理操作系统中，就绪队列存储等待CPU执打印机服务器使用队列管理多用户的打行的进程，I/O队列存储等待I/O操作完印请求打印任务按照到达顺序排队等成的进程调度器根据优先级和到达时待处理，确保先提交的任务先打印，避间从队列中选择进程执行，保证系统资免资源竞争和冲突，提高系统的稳定性源的合理分配和进程的公平执行和用户体验消息中间件分布式系统中的消息队列中间件（如RabbitMQ、Kafka）用于解耦生产者和消费者，提高系统的可靠性和可扩展性消息按发送顺序暂存于队列，等待消费者按自己的节奏处理双端队列与优先队列简介双端队列Deque优先队列Priority Queue双端队列支持在队列的两端进行元素的插入和删除操作，兼具栈优先队列中，元素的出队顺序取决于其优先级而非入队顺序每和队列的特性它可以用于需要同时具备FIFO和LIFO特性的场次出队操作都会移除当前优先级最高的元素，适用于任务调度、景，如滑动窗口算法、工作窃取调度等事件处理等需要按优先级处理的场景双端队列可以使用双向链表或循环数组实现双向链表实现更灵活但空间开销较大，循环数组实现空间效率高但需要预先分配固定大小空间字符串基本结构——字符序列编码方式字符串本质上是字符的有序序列，通字符串的存储与编码方式密切相关常使用字符数组存储，可以是定长或常见的编码包括ASCII、变长的在许多编程语言中，字符串UnicodeUTF-8/UTF-16等，不同是作为基本数据类型或内置的类提供编码方式对应不同的字符集和存储需的求基本操作字符串的常用操作包括连接、比较、子串提取、查找、替换等有些操作如连接可能涉及内存重新分配，在大量操作时需要注意效率问题在不同的编程语言中，字符串的实现方式有所不同C语言中的字符串是以空字符\0结尾的字符数组，而Java和Python等高级语言则提供了功能丰富的字符串类，支持更复杂的操作和更灵活的内存管理字符串算法应用模式匹配KMP算法利用部分匹配表跳过不必要的比较，大幅提高匹配效率字符串替换使用双指针或额外空间实现高效替换操作字符串倒置通过首尾交换实现原地倒置，常用于编辑操作字符串压缩通过替换重复字符为计数值，减少存储空间字符串算法在计算机科学中占有重要地位模式匹配是其中最常见的应用之一，例如KMP（Knuth-Morris-Pratt）算法通过构建部分匹配表，在Om+n时间内完成匹配，相比于朴素算法的Om*n效率有显著提升线性结构小结数据结构随机访问插入/删除主要应用场景数组O1On需要快速随机访问的场景链表On O1频繁插入删除的场景栈仅顶部O1仅顶部O1需要后进先出处理的场景队列仅首尾O1仅首尾O1需要先进先出处理的场景线性数据结构是计算机科学中最基础的数据组织形式，它们以不同的方式组织和管理数据，各有优缺点和适用场景数组支持快速随机访问但插入删除效率低；链表支持高效的插入删除但随机访问效率低；栈适用于需要后进先出处理的场景；队列适用于需要先进先出处理的场景非线性结构概述图结构表示多对多复杂关系树结构表示层次化一对多关系线性结构表示简单一对一关系非线性数据结构突破了线性结构元素之间一对一关系的限制，允许一个元素与多个元素相关联，能够表示更复杂的数据关系树是一种典型的非线性结构，它具有层次关系，每个节点可以有多个子节点，但只有一个父节点（根节点除外）树结构广泛应用于表示层次数据，如文件系统、组织结构等树基本概念——树的基本组成节点类型树的类型树是由节点和边组成的非线性数据结构，根节点是树的顶部节点，没有父节点；内其中一个特殊的节点被称为根节点每个部节点有父节点也有子节点；叶节点是没节点可以有零个或多个子节点，通过边连有子节点的节点，位于树的最底层节点接树没有环路，任意两个节点之间只有的度是指它拥有的子节点数量一条路径二叉树定义与性质二叉树的定义二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点这种结构简单而高效，是许多高级树结构的基础完全二叉树完全二叉树是除最底层外所有层都被完全填充，且最底层的所有节点都尽可能地集中在左侧的二叉树它常用于实现堆数据结构满二叉树满二叉树是一种所有非叶节点都有两个子节点，且所有叶节点都在同一层的二叉树满二叉树的节点总数为2^h-1，其中h为树的高度平衡二叉树平衡二叉树是任意节点的左右子树高度差不超过1的二叉树这种平衡性质保证了树的操作（如查找、插入、删除）具有较好的时间复杂度二叉树遍历方法前序遍历Pre-order中序遍历In-order后序遍历Post-order层序遍历Level-order前序遍历的顺序是根节点→中序遍历的顺序是左子树→后序遍历的顺序是左子树→层序遍历按照从上到下、从左左子树→右子树它首先访问根节点→右子树它首先递归右子树→根节点它首先递归到右的顺序访问树的所有节当前节点，然后递归地遍历左地遍历左子树，然后访问当前地遍历左子树，然后递归地遍点它通常使用队列来实现，子树，最后递归地遍历右子节点，最后递归地遍历右子历右子树，最后访问当前节首先将根节点入队，然后不断树前序遍历常用于创建树的树对于二叉搜索树，中序遍点后序遍历常用于删除树从队列取出节点访问，并将其拷贝或评估表达式树历会产生一个排序的序列（需要先删除子节点再删除父子节点入队，直到队列为空节点）二叉树存储结构顺序存储链式存储顺序存储使用数组表示二叉树，特别适合完全二叉树在这种表链式存储是二叉树最常用的存储方式，每个节点包含数据域和指示方式中，如果根节点存储在索引0，则对于任意节点i，其左子向左右子节点的指针域在C/C++中，可以定义如下结构节点在索引2i+1，右子节点在索引2i+2，父节点在索引i-1/2（整数除法）struct TreeNode{int data;//数据域顺序存储的优点是实现简单，访问父节点和子节点都很高效但TreeNode*left;//左子节点指针对于非完全二叉树，可能会浪费大量空间，因为需要为可能不存TreeNode*right;//右子节点指针在的节点预留位置};链式存储的优点是空间利用率高，适用于任何形态的二叉树，且插入删除操作方便缺点是需要额外的指针空间，且无法直接访问父节点（除非额外存储父指针）查找二叉树Binary SearchTreeBST的定义与性质二叉搜索树BST是一种特殊的二叉树，它满足以下性质对于任意节点，其左子树中所有节点的值都小于该节点的值，其右子树中所有节点的值都大于该节点的值这种特性使得BST能够高效地支持查找、插入和删除操作查找操作在BST中查找一个值，从根节点开始，如果目标值等于当前节点值，则找到；如果小于当前节点值，则在左子树中继续查找；如果大于当前节点值，则在右子树中继续查找查找的平均时间复杂度为Olog n，最坏情况下为On插入操作插入操作先按照查找操作的规则找到应插入的位置，然后创建新节点插入如果BST中不存在重复值，插入过程相对简单插入操作的时间复杂度与树的高度成正比，平均为Olog n，最坏为On删除操作删除操作较为复杂，分三种情况删除叶节点直接移除；删除只有一个子节点的节点，用其子节点替代；删除有两个子节点的节点，用其右子树中的最小值（或左子树中的最大值）替代，然后删除那个最小值节点平衡二叉树树AVL平衡二叉树（AVL树）是一种特殊的二叉搜索树，它满足任何节点的左右子树高度差（平衡因子）不超过1这种平衡性质确保了树的高度始终保持在Olog n，从而保证了查找、插入和删除操作的时间复杂度为Olog n当插入或删除操作导致AVL树失去平衡时，需要通过旋转操作来恢复平衡旋转操作主要有四种左旋转（LL）、右旋转（RR）、左右旋转（LR）和右左旋转（RL）例如，当一个节点的左子树过高且失衡发生在左子树的左侧，需要进行右旋转；当失衡发生在左子树的右侧，需要先对左子节点进行左旋转，再对当前节点进行右旋转AVL树通过这些旋转操作维持了良好的平衡性，避免了二叉搜索树在极端情况下（如顺序插入）退化为链表的问题，保证了稳定的性能然而，频繁的旋转操作也带来了一定的开销，这是AVL树的主要缺点堆（）结构与应用Heap大顶堆Max Heap小顶堆Min Heap堆操作大顶堆是一种完全二叉树，其中每个节点小顶堆也是一种完全二叉树，但每个节点堆的基本操作包括插入insert、删除最的值都大于或等于其子节点的值在大顶的值都小于或等于其子节点的值在小顶大/最小元素extract-max/min和建堆堆中，根节点总是存储堆中的最大值这堆中，根节点总是存储堆中的最小值小heapify插入时，先将新元素添加到种特性使大顶堆非常适合需要快速访问最顶堆常用于需要快速访问最小元素的场堆的末尾，然后向上调整（上浮）；删除大元素的场景景，如Dijkstra算法最大/最小元素时，将堆顶元素与末尾元素交换，移除末尾元素，然后将新的堆顶向下调整（下沉）哈夫曼树与编码应用统计频率计算每个字符出现的次数构建哈夫曼树根据频率逐步合并最小节点生成编码通过遍历树获取可变长编码哈夫曼树（也称霍夫曼树或最优二叉树）是一种特殊的二叉树，它根据节点的权重（通常是出现频率）构建，使得带权路径长度最小在哈夫曼树中，高频节点距离根节点较近，低频节点距离较远，这种特性使它成为数据压缩的理想工具哈夫曼编码是一种基于哈夫曼树的可变长前缀编码它为每个字符分配一个唯一的二进制编码，使得没有任何编码是其他编码的前缀，从而保证解码的无歧义性哈夫曼编码的核心思想是让高频字符使用较短的编码，低频字符使用较长的编码，以最小化整体编码长度这种策略在文本、图像和视频压缩中广泛应用，如JPEG、MP

3、ZIP等压缩格式都使用了哈夫曼编码的变种树的实际应用场景文件系统组织计算机文件系统采用树结构组织文件和目录根目录位于树的顶部，各级子目录和文件形成树的分支和叶节点这种结构使得文件的组织、访问和管理变得直观高效语法分析树编译器中的语法分析阶段使用树结构表示程序的语法结构语法分析树的叶节点是程序的标记（token），内部节点表示语法规则和表达式的结构关系，根节点代表整个程序数据库索引B树和B+树广泛应用于数据库系统的索引结构，支持高效的范围查询和点查询这些树结构能够在大规模数据集上保持良好的性能，是数据库性能优化的关键决策树在机器学习中，决策树是一种常见的预测模型树的每个内部节点表示一个特征测试，每个分支表示测试的一个可能结果，每个叶节点表示一个预测类别或值树结构在网络路由（如最小生成树协议）、游戏AI（如极小化极大搜索树）、组织结构图、家谱图等领域也有广泛应用不同类型的树针对不同需求进行了优化，如红黑树用于自平衡的动态集合管理，字典树（Trie）用于字符串前缀匹配和搜索自动完成功能图基本定义——顶点Vertex边Edge图中的基本单元，代表实体连接顶点，表示关系无向图有向图边无方向，如城市间道路边有方向，如社交网络关注图是由顶点（或节点）和边组成的非线性数据结构，用于表示多对多的复杂关系在图中，任意两个顶点之间可能存在连接关系（称为边），这种灵活性使图能够表示现实世界中的网络关系，如社交网络、道路网络、计算机网络等根据边的方向性，图可以分为有向图和无向图在有向图中，边有特定方向，例如Twitter的关注关系；在无向图中，边没有方向，例如Facebook的好友关系此外，图还可以根据其他特性进行分类，如带权图（边有权重）、连通图（任意两点间都有路径）、完全图（任意两点间都有边）等理解这些基本概念是学习图算法的基础图的存储结构邻接矩阵邻接表邻接矩阵使用一个二维数组表示图中顶点间的连接关系对于有邻接表为图中的每个顶点创建一个链表，链表中的每个节点表示n个顶点的图，使用一个n×n的矩阵A，其中A[i][j]=1表示从顶与该顶点相邻的顶点这种表示方法只存储实际存在的边，因此点i到顶点j存在一条边，A[i][j]=0表示不存在边对于带权图，对于稀疏图更为高效可以将矩阵元素设为边的权重邻接表的优点是空间复杂度与边数成正比（O|V|+|E|），适合邻接矩阵的优点是实现简单，可以快速判断两个顶点之间是否存存储稀疏图缺点是判断两个顶点之间是否存在边需要遍历链在边（O1时间复杂度）缺点是空间复杂度为On²，对于稀表，最坏情况下时间复杂度为O度此外，对于带权图，需要疏图（边数远小于n²）效率较低在链表节点中额外存储权重信息图的遍历算法深度优先搜索DFS广度优先搜索BFS应用场景深度优先搜索从一个起始顶点开始，尽可广度优先搜索也从一个起始顶点开始，但DFS适用于搜索所有可能路径、拓扑排能深地沿着一条路径探索，直到无法继续它先访问所有相邻顶点，然后再扩展到下序、连通分量分析等场景；BFS适用于寻前进，然后回溯到前一个顶点，探索其他一层顶点这种逐层扩展的方式通常使找最短路径、网络爬虫、社交网络中的六路径这种方法通常使用递归或栈实现用队列实现，可以找到最短路径（以边数度分隔分析等两种算法各有所长，选择计）取决于具体问题最短路径算法应用场景实现要点Dijkstra算法广泛应用于网络路由协议（如Dijkstra算法原理Dijkstra算法的核心数据结构是优先队列，用于高OSPF）、地图导航系统、网络流量分析等领域Dijkstra算法用于求解从单一源点到所有其他顶点效地选择距离最小的顶点算法时间复杂度与图的在实际应用中，可能需要根据具体场景进行优化，的最短路径问题，适用于边权重为非负的图算法表示方式和优先队列实现有关，使用二叉堆实现的例如使用双向搜索、启发式搜索等技术提高效率使用贪心策略，维护一个已知最短路径的顶点集合优先队列，时间复杂度为OV+ElogV，其中V是S，每次从尚未处理的顶点中选择距离源点最近的顶点数，E是边数顶点加入S，并更新其相邻顶点的距离除了Dijkstra算法，还有其他重要的最短路径算法，如处理负权边的Bellman-Ford算法、解决所有顶点对之间最短路径的Floyd-Warshall算法等选择合适的算法需要考虑图的特性（如是否有负权边）和问题的具体需求（如单源最短路径还是所有顶点对最短路径）最小生成树算法Kruskal算法Prim算法Kruskal算法是基于贪心策略的最小生成树算法，它从最小权重Prim算法也是一种贪心策略的最小生成树算法，但它从单个顶的边开始，逐步添加权重递增的边，同时避免形成环路该算法点开始，逐步扩展生成树该算法维护一个顶点集合（已加入最使用并查集（Union-Find）数据结构检测环路，具有优秀的时小生成树的顶点）和一个优先队列（与已加入顶点相邻的边），间复杂度每次选择权重最小的边来扩展生成树具体步骤如下

1.将所有边按权重升序排序；

2.初始时，每个具体步骤如下

1.选择任意顶点作为起点，加入最小生成树集顶点构成一个独立的连通分量；

3.按顺序考察每条边，如果边合；

2.将与当前最小生成树集合中顶点相邻的所有边加入优先的两个端点在不同的连通分量中，则将该边加入最小生成树，并队列；

3.选择优先队列中权重最小的边，如果该边连接的顶点合并这两个连通分量；

4.重复步骤3，直到最小生成树包含n-1尚未加入最小生成树集合，则将该边加入最小生成树，并将该顶条边（n为顶点数）点加入集合；

4.重复步骤2和3，直到所有顶点都加入最小生成树集合拓扑排序有向无环图拓扑排序必须应用于DAG计算入度统计每个顶点的入边数量排序处理移除入度为0的顶点并更新图结果验证检查是否所有顶点都已排序拓扑排序是将有向无环图DAG的所有顶点排成一个线性序列，使得图中任何一对顶点u和v，如果存在一条从u到v的路径，那么在序列中u出现在v之前拓扑排序可以用来表示顶点之间的依赖关系或先后顺序，如课程先修关系、任务调度顺序等拓扑排序的两种常见算法是Kahn算法和DFS算法Kahn算法基于入度，不断删除入度为0的顶点；DFS算法则基于深度优先搜索，记录顶点的完成时间在实际应用中，拓扑排序广泛用于编译器的依赖分析、任务调度系统、数据处理管道等场景，帮助确定执行顺序，避免循环依赖图的实际应用图数据结构在现实世界有着广泛的应用在社交网络分析中，图用于建模用户之间的关系，通过图算法可以发现社区结构、影响力节点、信息传播路径等社交媒体公司利用这些分析优化推荐系统、广告投放和内容分发策略，提高用户参与度和平台价值在路径规划与导航系统中，图用于表示道路网络，顶点代表路口或兴趣点，边代表道路，边权可以表示距离、时间或交通状况等导航应用使用最短路径算法（如Dijkstra、A*）计算最优路线，考虑实时交通状况、用户偏好和历史数据此外，图还广泛应用于计算机网络设计、生物信息学（如蛋白质相互作用网络）、知识图谱、推荐系统等领域，展现了强大的建模和问题解决能力哈希表原理与结构——哈希函数桶与槽位哈希函数是哈希表的核心，它将输哈希表内部通常是一个固定大小的入数据（键）映射到一个固定范围数组，数组的每个元素称为桶或内的整数值（哈希值），这个整数槽每个桶可以存储单个键值对，值作为数据在哈希表中的存储位置或者在处理冲突时存储多个键值对（桶或槽）好的哈希函数应该分（如链地址法）桶的数量影响哈布均匀，计算高效，并最小化冲希表的性能和空间利用率突冲突处理哈希冲突指的是两个不同的键被哈希函数映射到同一个桶有效处理冲突对哈希表性能至关重要常见的冲突解决策略包括链地址法（将冲突项链接在一起）和开放寻址法（在表中找其他位置）哈希表的主要优势在于其平均O1时间复杂度的查找、插入和删除操作，这使它成为实现字典、集合等数据结构的理想选择然而，哈希表的性能高度依赖于哈希函数的质量和冲突处理策略在最坏情况下（所有键都映射到同一个桶），操作复杂度可能退化到On哈希冲突解决方法开放寻址法链地址法再哈希与动态扩容开放寻址法在发生冲突时，通过某种探测链地址法（又称拉链法）在每个哈希桶中当哈希表中的元素数量增加到一定阈值序列在哈希表中查找其他空槽来存储冲突维护一个链表，所有映射到该桶的键值对（通常是表大小的一定比例，如75%）项常见的探测策略包括线性探测（依次都存储在这个链表中这种方法简单有时，可以通过创建一个更大的表并重新哈查看下一个位置）、二次探测（按二次函效，适合处理未知数量的冲突，但需要额希所有现有元素来减少冲突这种再哈希数间隔查看）和双重哈希（使用第二个哈外的内存来存储指针，且在链表很长时性操作虽然代价较高，但可以显著改善长期希函数计算步长）能可能下降性能哈希表应用案例字典与符号表哈希表是实现字典（键值映射）和符号表（变量名到值的映射）的常用数据结构编程语言的变量查找、编译器的符号表、JSON对象等都依赖哈希表实现高效的键值存取URL去重与缓存网络爬虫使用哈希表存储已访问的URL，快速检查新URL是否已被处理，避免重复访问类似地，Web缓存系统使用哈希表存储URL到缓存内容的映射，提供快速的缓存查找数据库索引某些数据库使用哈希索引加速等值查询（如WHERE column=value）哈希索引特别适合唯一性约束和主键索引，能够提供常数时间的查找性能密码存储系统通常不直接存储用户密码，而是存储密码的哈希值（通常加盐）验证时，系统对输入的密码应用相同的哈希函数，比较哈希值而非原始密码，增强安全性哈希表还广泛应用于文件块索引、内存管理（如内存池）、加密算法、负载均衡、分布式系统（一致性哈希）等场景几乎所有现代编程语言都提供哈希表的内置实现，如Java的HashMap、Python的dict、C++的unordered_map等，证明了其作为基础数据结构的重要性常用复合结构设计最大最小栈通过组合使用多个栈，可以实现在O1时间内获取栈中最大/最小值的数据结构一种实现方式是使用主栈存储所有元素，辅助栈记录当前最大/最小值，每次push操作时同步更新辅助栈LRU缓存LRU（最近最少使用）缓存结合双向链表和哈希表实现高效的缓存淘汰机制链表按访问顺序组织元素，最近访问的在前；哈希表存储键到链表节点的映射，实现O1查找访问或插入元素时，将其移至链表头部图的邻接表邻接表使用数组（或哈希表）和链表的组合表示图结构，每个顶点对应一个链表，存储其相邻顶点这种复合结构既节省空间（对于稀疏图），又支持高效的图操作字典树（Trie）字典树是一种特殊的树形数据结构，用于高效存储和查找字符串集合每个节点通常使用数组或哈希表存储子节点，实现字符到子节点的映射，支持前缀匹配和自动完成等功能这些复合数据结构展示了如何通过组合基本数据结构解决复杂问题，发挥各种结构的优势在实际开发中，选择合适的数据结构组合可以显著提高算法的性能和可维护性数据结构与算法配合实例On²基础排序如冒泡排序，依赖数组Onlogn高级排序如堆排序，依赖堆结构On线性查找遍历数组或链表Ologn二分查找需要有序数组或平衡树不同的算法对数据结构有不同的要求，选择合适的数据结构可以显著提高算法效率例如，排序算法与数据结构密切相关快速排序和归并排序通常在数组上实现，但归并排序在链表上也能高效工作；堆排序依赖于堆数据结构；基数排序可以利用队列处理不同位的元素查找算法也依赖特定的数据结构二分查找要求有序数组；哈希查找依赖哈希表；树形查找需要使用二叉搜索树或其变种图算法如最短路径、最小生成树、网络流等则需要合适的图表示方式（邻接矩阵或邻接表）理解数据结构与算法的关系，有助于在实际问题中选择最佳的解决方案，平衡时间复杂度和空间复杂度现代技术场景下的数据结构分布式数据结构大数据和云计算环境下，传统数据结构扩展到分布式系统，如分布式哈希表DHT支持P2P网络，一致性哈希算法优化分布式缓存，分片B树支持跨节点存储海量数据并发数据结构多线程环境需要线程安全的数据结构，如无锁数据结构（使用原子操作避免锁）、读写分离集合（允许并发读取）、并发哈希映射等，在保证数据一致性的同时提高并行性能内存优化结构随着内存层次结构复杂化，数据结构设计越来越注重缓存友好性紧凑数据布局、缓存感知算法和内存池技术能显著提高性能，尤其是在处理大规模数据时现代技术场景对传统数据结构提出了新的挑战和要求大数据环境下，数据结构需要考虑可扩展性、容错性和数据分布；云原生应用需要支持弹性扩展和微服务架构；物联网和边缘计算场景则对数据结构的实时性和资源效率提出了更高要求数据结构学习建议实际项目应用在线练习与竞赛在实际项目中有意识地应用所学数多语言实现对比通过LeetCode、HackerRank等据结构，并分析其对性能的影响夯实基础概念尝试用不同编程语言（如C/C++、平台上的数据结构题目强化实践能可以从实现一个简单的数据库索首先深入理解基本数据结构（数Java、Python）实现相同的数据力从简单题目开始，逐步挑战更引、缓存系统或游戏引擎开始，体组、链表、栈、队列、树、图、哈结构，体会不同语言的特性和实现复杂的问题参加编程竞赛如验数据结构在真实场景中的作用希表）的原理、优缺点和适用场差异C/C++可以深入了解内存管Codeforces、TopCoder也是锻景这些基础结构是更复杂结构和理，Java有丰富的集合框架可供参炼应用数据结构解决问题能力的好算法的基石，掌握它们的内部机制考，Python则展示了高级抽象的实方法和性能特性至关重要现方式课程回顾与重点总结结构选择决策根据应用需求选择最佳数据结构高级与复合结构组合基础结构实现复杂功能非线性结构树、图、哈希表等多维关系线性结构数组、链表、栈、队列等基础基本概念抽象数据类型与数据组织原理本课程系统介绍了计算机科学中的基本数据结构，从线性结构（数组、链表、栈、队列）到非线性结构（树、图、哈希表），探讨了它们的实现原理、操作特性和适用场景我们特别强调了数据结构与算法的紧密关系，以及如何根据具体问题选择合适的数据结构数据结构的选择对程序性能有决定性影响例如，需要频繁随机访问时应选择数组；需要频繁插入删除时应考虑链表；需要按特定顺序处理数据时可以使用栈或队列；需要表示层次关系时树结构更合适；需要表示复杂网络关系时图是首选；需要高效查找时哈希表通常是最佳选择掌握这些选择的原则和权衡因素，是成为优秀程序员的关键能力结束与提问感谢大家参加本次基本数据结构课程！我们已经全面介绍了计算机科学中最重要的数据结构及其应用希望这些知识能够帮助你在实际编程中做出更明智的选择，编写更高效的代码推荐的学习资源包括《算法导论》（经典教材，深入且全面）、《数据结构与算法分析》（更加实用的视角）、《编程珠玑》（展示算法思想之美）在线资源方面，建议关注LeetCode、Coursera上的数据结构与算法课程、GitHub上的开源项目如visualgo.net（数据结构可视化）等现在开放问答环节，欢迎大家就课程内容或数据结构的任何方面提问如果有特定的编程难题想讨论，也可以在此时提出，我们可以一起分析如何应用适当的数据结构来解决。