算法设计与实践（基于MWORKS）课件 第三章基础数据结构

第三章基础数据结构3.1链表3.2队列3.3栈3.4二叉树和哈弗曼树CONTENTS目录3.1链表3.1.1定义链表是一种线性数据结构，由一系列节点组成。每个节点不仅存储数据元素，还包含指向下一个节点的引用（在单向链表中）。与数组不同，链表中的元素在内存中无需连续存储，这种特性为其带来了独特的优势。3.1链表3.1.2基本结构链表的基本结构围绕节点展开。以单向链表为例，每个节点包含两个部分：数据域（存储实际数据）和指针域（存储指向下一个节点的引用）。链表通过这些节点间的引用关系，将各个节点串联起来，形成一个线性序列。链表有一个头指针，用于指向链表的第一个节点，它是访问链表的入口。3.1链表3.1.3类型1.单向链表单向链表是链表中最为基础的类型。在单向链表中，每个节点只有一个指向其后继节点的指针。链表的尾节点的指针域为nothing，以此标识链表的结束。这种结构使得单向链表只能从前往后进行遍历。3.1链表3.1.3类型2.双向链表双向链表是对单向链表的扩展。每个节点除了拥有指向后继节点的next指针，还增加了一个指向前驱节点的prev指针。这一特性允许双向链表从任意一端开始进行遍历，极大地提高了链表操作的灵活性。双向链表的头节点的prev指针和尾节点的next指针均为nothing。3.1链表3.1.3类型3.循环链表循环链表又可细分为循环单向链表和循环双向链表。在循环单向链表中，尾节点的next指针不再指向nothing，而是指向链表的头节点，形成一个闭环结构。循环双向链表则是在此基础上，头节点的prev指针指向尾节点，进一步增强了其循环特性。这种结构在一些需要重复遍历或者无头尾之分的场景中非常有用。3.1链表3.1.4基本操作-----1.创建链表首先要定义节点的结构。mutablestructListNodedata::Anynext::Union{ListNode,Nothing}functionListNode(d)new(d,nothing)endend3.1链表3.1.4基本操作-----1.创建链表mutablestructSinglyLinkedListhead::Union{ListNode,Nothing}functionSinglyLinkedList()new(nothing)endend然后可以创建一个空链表，通常通过将头指针初始化为nothing来实现：3.1链表3.1.4基本操作2.插入节点在单向链表中插入节点有多种情况。若要在链表头部插入新节点，只需让新节点的next指针指向原头节点，然后将头指针更新为新节点。在链表中间或尾部插入节点时，则需要遍历链表找到合适的位置，修改相应节点的next指针。3.1链表3.1.4基本操作3.删除节点删除节点同样需要考虑多种情况。若要删除头节点，只需将头指针更新为头节点的下一个节点。删除中间或尾部节点时，需要遍历链表找到待删除节点的前驱节点，然后修改前驱节点的next指针，使其跳过待删除节点。3.1链表3.1.4基本操作4.遍历链表遍历链表是常见操作。对于单向链表，从头部开始，通过不断跟随节点的next指针，依次访问每个节点，直到遇到nothing。3.1链表3.1.5相关算法链表反转是链表相关的一个重要算法。在单向链表中，通过改变节点间的指针方向，将链表反转。其实现思路是：从链表头开始，逐个节点地将next指针反转，使原链表的头节点变为尾节点，原尾节点变为头节点。3.1链表3.1.5相关算法链表反转是链表相关的一个重要算法。在单向链表中，通过改变节点间的指针方向，将链表反转。其实现思路是：从链表头开始，逐个节点地将next指针反转，使原链表的头节点变为尾节点，原尾节点变为头节点。3.1链表3.1.6优缺点1.优点•动态内存分配：链表无需预先确定数据量的大小，可以根据实际需求动态分配内存，避免了数组可能出现的内存浪费（数据量较小时）或内存不足（数据量超出预期时）的问题。3.1链表3.1.6优缺点1.优点•插入和删除高效：在链表中进行插入和删除操作时，只需修改相关节点的指针，无需像数组那样移动大量元素。在已知插入或删除位置的情况下，时间复杂度为O(1)。•灵活性高：适用于数据元素频繁变动的场景，能够轻松应对节点的增加、删除和位置调整等操作。3.1链表3.1.6优缺点2.缺点•访问效率低：无法像数组那样通过索引直接访问某个节点。若要访问第n个节点，需要从头节点开始依次遍历，时间复杂度为O(n)。3.1链表3.1.6优缺点2.缺点•额外内存开销：每个节点除了存储数据本身，还需要额外存储一个或两个指针（单向链表一个，双向链表两个），这增加了内存占用。•实现复杂度较高：相比数组，链表的实现涉及到节点结构的定义、指针操作等，代码实现和理解的难度相对较大。3.1链表3.1.7应用领域操作系统中的进程管理实现邻接表来表示图浏览器的历史记录LRU（最近最少使用）缓存3.2队列3.2.1定义队列是一种遵循先进先出（FIFO）原则的数据结构。新元素在队列的末尾添加（入队操作），而元素从队列的开头移除（出队操作）。这种特性使得队列在许多需要按顺序处理数据的场景中发挥着重要作用。3.2队列3.2.2基本结构队列的基本结构可以用数组或链表来实现。以数组实现为例，通常需要维护两个指针：front指针指向队列的头部元素，rear指针指向队列的尾部元素的下一个位置。当队列为空时，front和rear指针相等。随着元素的入队和出队，这两个指针会相应地移动。3.2队列3.2.3类型1.基于数组的队列分为普通队列和循环队列。普通队列在rear指针到达数组末尾时，如果再进行入队操作，即使数组前面有空闲空间，也会认为队列已满，导致空间浪费。循环队列则通过将数组看作一个环状结构，当rear指针到达数组末尾时，下一个入队位置回到数组开头，从而充分利用数组空间，避免了普通队列可能出现的“假溢出”问题。3.2队列3.2.3类型2.基于链表的队列基于链表实现的队列，队列的头部对应链表的头节点，队列的尾部对应链表的尾节点。入队操作在链表尾部添加新节点，出队操作删除链表头部节点。从链表结构角度，可分为单向链表队列和双向链表队列。由于队列的FIFO特性，单向链表队列已能很好地满足需求，双向链表队列虽也可实现队列，但在实际应用中，其双向遍历优势在队列场景下使用较少。3.2队列3.2.4基本操作1.创建队列用数组实现队列时，在Julia中定义用链表实现队列时，节点和队列定义2.入队操作数组实现的队列入队操作链表实现的队列入队操作3.2队列3.2.4基本操作3.出队操作数组实现的队列出队操作：链表实现的队列出队操作：4.判断队列是否为空数组实现的队列判断是否为空链表实现的队列判断是否为空3.2队列3.2.5相关算法在广度优先搜索（BFS）算法中，队列发挥着核心作用。以图的BFS遍历为例，从起始节点开始，将其加入队列。然后不断从队列中取出节点，访问该节点，并将其未访问过的邻居节点加入队列。通过这种方式，按照层次顺序遍历图，从而找到从起始节点到目标节点的最短路径3.2队列3.2.6优缺点1.优点•顺序性强。•简单直观。•动态内存分配（链表实现）。•高效的入队和出队操作（链表实现）。3.2队列3.2.6优缺点2.缺点•固定大小限制（数组实现）•出队操作效率问题（普通数组队列）•额外内存开销（链表实现）•访问效率低（链表实现）3.2队列3.2.7应用领域•打印任务队列。•操作系统的进程调度。•消息队列系统。•广度优先搜索（BFS）算法。3.3栈3.3.1定义栈是一种后进先出（LIFO）的数据结构，元素在栈的顶部添加（入栈操作）和移除（出栈操作）。这种特性使得栈在许多需要处理具有相反顺序的数据场景中非常有用。3.3栈3.3.2基本结构栈可以用数组或链表来实现。以数组实现为例，使用一个数组来存储栈中的元素，并通过一个top指针来指示栈顶元素的位置。当栈为空时，top指针通常为0；随着元素的入栈和出栈，top指针相应地增加或减少。3.3栈3.3.3类型1.基于数组的栈基于数组实现的栈主要是普通栈。虽然在某些特定场景下可能会有变体，如可动态扩容的栈（当栈满时，自动创建一个更大的数组并复制元素），但其基本结构和操作方式围绕普通栈的概念展开。普通栈在操作过程中，当top指针等于数组的容量时，表示栈已满；当top指针为0时，表示栈为空。3.3栈3.3.3类型2.基于链表的栈基于链表实现的栈，栈顶对应链表的头节点。入栈操作是在链表头部插入新节点，出栈操作是删除链表头部节点。链表实现的栈可以动态分配内存，避免了数组可能出现的固定大小限制问题。3.3栈3.3.4基本操作1.创建栈2.入栈操作3.出栈操作4.判断栈是否为空3.3栈3.3.5相关算法表达式求值是栈的一个重要应用场景。以后缀表达式（逆波兰表达式）求值为例，从左到右扫描后缀表达式，遇到操作数时将其压入栈中，遇到运算符时从栈中弹出相应的操作数进行运算，然后将运算结果压入栈中。最终，栈顶元素即为表达式的计算结果。3.3栈3.3.6优缺点1.优点•操作简单高效•内存紧凑（数组实现）•动态内存分配（链表实现）3.3栈3.3.6优缺点2.缺点•固定大小限制（数组实现）•额外内存开销（链表实现）•缺乏灵活性（数组实现）3.3栈3.3.7应用领域•表达式求值•函数调用栈•深度优先搜索（DFS）算法•括号匹配检查3.4

二叉树和哈弗曼树3.4.1二叉树1.定义二叉树是一种树状数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的节点包含数据元素以及指向左右子节点的引用。二叉树有一个根节点，从根节点出发，可以通过子节点的引用遍历整个二叉树。3.4

二叉树和哈弗曼树3.4.1二叉树2.基本结构二叉树的基本结构围绕节点展开。每个节点包含三个部分：数据域（存储实际数据）、左子节点指针（指向左子树的根节点）和右子节点指针（指向右子树的根节点）。如果一个节点没有左子节点或右子节点，则相应的指针为nothing。二叉树可以为空，即没有任何节点。3.4

二叉树和哈弗曼树3.4.1二叉树3.类型1.满二叉树：一棵二叉树中，除了叶子节点（没有子节点的节点）外，每个节点都有两个子节点，并且所有叶子节点都在同一层。满二叉树的节点总数为2^h-1，其中h为树的高度（根节点所在层为第1层）。3.4

二叉树和哈弗曼树3.4.1二叉树3.类型2.完全二叉树：对于一棵具有n个节点的二叉树，按层序编号（从根节点开始，从上到下，从左到右），如果编号为i（1\leqi\leqn）的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，则称这棵二叉树为完全二叉树。完全二叉树的叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左侧。3.4

二叉树和哈弗曼树3.4.1二叉树3.类型3.二叉搜索树（BST）：是一种特殊的二叉树，对于树中的每个节点，其左子树中所有节点的值都小于该节点的值，其右子树中所有节点的值都大于该节点的值。二叉搜索树具有高效的查找、插入和删除操作特性。3.4

二叉树和哈弗曼树3.4.1二叉树4.基本操作定义节点结构插入节点查找节点删除节点3.4

二叉树和哈弗曼树3.4.1二叉树遍历二叉树有三种常见方式：前序遍历：先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树中序遍历：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树后序遍历：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。3.4

二叉树和哈弗曼树3.4.1二叉树5.相关算法计算二叉树的高度是一个常见算法，通过递归计算左右子树的高度并取较大值加1得到。6.优缺点优点：•高效的查找、插入和删除（二叉搜索树）•层次结构清晰•递归算法实现方便缺点：•最坏情况下性能退化（二叉搜索树）•内存开销较大。•实现复杂度较高3.4

二叉树和哈弗曼树3.4.1二叉树7.应用领域•搜索算法•表达式树•文件系统目录结构•决策树3.4

二叉树和哈弗曼树3.4.2哈弗曼树1.定义哈弗曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。在哈弗曼树中，每个叶子节点都带有一个权值，树的带权路径长度（WPL）定义为每个叶子节点的权值乘以其到根节点的路径长度之和。哈弗曼树常用于数据压缩等应用中，通过构建哈弗曼树来为不同字符分配不同长度的编码，从而实现数据的压缩。3.4

二叉树和哈弗曼树3.4.2哈弗曼树2.基本结构哈弗曼树是一种特殊的二叉树，其节点除了包含数据域（在哈弗曼树中通常是字符或者符号）和指向左右子节点的指针外，还包含一个权值域，用于存储该节点对应的权值。根节点是整个哈弗曼树的入口，通过根节点可以遍历到所有的叶子节点。非叶子节点的权值是其左右子节点权值之和。3.4

二叉树和哈弗曼树3.4.2哈弗曼树3.类型哈弗曼树本质上是一种特定性质的二叉树，并没有基于其自身结构特点进一步细分的类型。不过，根据应用场景的不同，哈弗曼树可以用于不同类型数据的压缩或编码，比如对文本字符进行压缩，或者对音频、图像等数据中的符号进行编码。4.基本操作3.4

二叉树和哈弗曼树3.4.2哈弗曼树5.相关算法哈弗曼编码算法是基于哈弗曼树实现数据压缩的关键。通过构建哈弗曼树并生成编码，将原始数据中的字符替换为对应的哈弗曼编码，从而减少数据存储所需的空间。解码算法则是编码算法的逆过程，根据哈弗曼树，将哈弗曼编码还原为原始数据。3.4

二叉树和哈弗曼树3.4.2哈弗曼树6.优缺点（1）优点：高效的数据压缩通用性理论最优性（2）缺点：

构建成本

存储开销

适应性问题3.4

二叉树和哈弗曼树3.4.2哈弗曼树7.应用领域•搜索算法•表达式树•文件系统目录结构•决策树3.4

二叉树和哈弗曼树3.4.2哈弗曼树1.定义哈弗曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。在哈弗曼树中，每个叶子节点都带有一个权值，树的带权路径长度（WPL）定义为每个叶子节点的权值乘以其到根节点的路径长度之和。哈弗曼树常用于数据压缩等应用中，通过构建哈弗曼树来为不同字符分配不同长度的编码，从而实现数据的压缩。3.4

二叉树和哈弗曼树3.4.2哈弗曼树2.基本结构哈弗曼树是一种特殊的二叉树，其节点除了包含数据域（在哈弗曼树中通常是字符或者符号）和指向左右子节点的指针外，还包含一个权值域，用于存储该节点对应的权值。根节点是整个哈弗曼树的入口，通过根节点可以遍历到所有的叶子节点。非叶子节点的权值是其左右子节点权值之和。3.4

二叉树和哈弗曼树3.4.2哈弗曼树3.类型哈弗曼树本质上是一种特定性质的二叉树，并没有基于其自身结构特点进一步细分的类型。不过，根据应用场景的不同，哈弗曼树可以用于不同类型数据的压缩或编码，比如对文本字符进行压缩，或者对音频、图像等数据中的符号进行编码。3.4

二叉树和哈弗曼树3.4.2哈弗曼树4.基本操作创建哈弗曼树是核心操作，需要根据