《数据结构基础》课件

数据结构基础本课件旨在全面介绍数据结构的基础知识，为学习者构建坚实的数据结构PPT理论基础通过本课程的学习，您将掌握各种常用数据结构的原理、特点及其应用，并能灵活运用这些数据结构解决实际问题本课程内容丰富，结构清晰，深入浅出，适合计算机科学专业的学生以及对数据结构感兴趣的开发者课程内容与学习目标课程内容学习目标数据结构基本概念理解数据结构的基本概念••线性表、栈、队列掌握常用数据结构的存储方式和特点••串、数组与广义表能够选择合适的数据结构解决实际问题••树与二叉树了解算法的时间复杂度和空间复杂度••图培养良好的程序设计习惯和算法思维••查找•排序•什么是数据结构？数据结构是计算机存储、组织数据的方式数据结构是指相互之间存在一种或多种特定关系的数据元素的集合通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率数据结构往往同高效的检索算法和索引技术有关数据结构是算法设计的基础理解并掌握数据结构对于编写高效的程序至关重要数据结构可以分为线性结构和非线性结构两大类线性结构包括线性表、栈、队列等，非线性结构包括树、图等不同的数据结构适用于不同的应用场景，选择合适的数据结构可以提高程序的性能数据结构的重要性提高程序效率优化存储空间合理的数据结构选择能够显著提有效的数据结构设计能够节约存高程序的执行效率，减少运行时储空间，降低内存占用间增强代码可读性清晰的数据结构能够提高代码的可读性和可维护性，方便团队协作基本概念数据、数据元素、数据项数据描述客观事物的符号，是所有能输入到计算机中并被计算机程序处理的符号的总称数据元素数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理也简称为元素，或称为记录、结点或顶点数据项组成数据元素的、具有独立含义的最小单位也称为字段或域逻辑结构与物理结构逻辑结构物理结构指数据元素之间的逻辑关系，是从逻辑意义上描述数据，与计算指数据在计算机中的存储形式，是数据元素及其关系在计算机存机无关常见的逻辑结构有集合结构、线性结构、树形结构、储器中的存储方式常见的物理结构有顺序存储结构、链式存图形结构储结构算法的概念算法是指解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作算法是计算机科学的核心，一个好的算法能够显著提高程序的效率和性能算法的设计需要考虑时间复杂度和空间复杂度，以保证算法的效率和资源的合理利用算法可以用自然语言、流程图、伪代码等多种方式进行描述选择合适的描述方式能够更清晰地表达算法的思路和步骤，方便理解和实现算法的设计和分析是计算机科学的重要研究方向，不断涌现出新的算法来解决各种复杂的问题算法的特性有穷性确定性可行性123算法必须在执行有限步骤后结束，算法的每个步骤必须有确定的含义算法的每个步骤都必须是可执行的不能无限循环，不能有二义性，可以通过有限次运算实现输入输出45算法可以有零个或多个输入算法必须有至少一个输出时间复杂度和空间复杂度时间复杂度空间复杂度衡量算法执行时间长短的一个标准，通常用大记号表示，例如衡量算法所需存储空间大小的一个标准，也用大记号表示空O O、、等时间复杂度越低，算法的执行效率间复杂度越低，算法对存储空间的利用率越高On On^2Olog n越高线性表的概念和特点线性表是最基本的数据结构之一，是由（）个数据元素组成的有限序列n n≥0线性表的特点是数据元素之间存在一对一的关系，即每个元素都有一个前驱“”元素和一个后继元素（第一个元素没有前驱，最后一个元素没有后继）线性表可以用顺序存储结构或链式存储结构实现线性表的常见操作包括插入、删除、查找等不同的存储结构对这些操作的效率有不同的影响例如，顺序存储结构在查找方面效率较高，而链式存储结构在插入和删除方面效率较高理解线性表的概念和特点对于后续学习其他数据结构至关重要线性表的顺序存储结构顺序存储结构是指用一段连续的存储单元依次存储线性表的数据元素顺序存储结构的特点是逻辑上相邻的元素在物理位置上也相邻顺序存储结构的优点是随机访问方便，可以通过下标直接访问元素；缺点是插入和删除操作需要移动大量元素，效率较低顺序存储结构通常使用数组来实现顺序存储结构的实现需要预先分配足够的存储空间，如果线性表的长度超过预分配的空间，则需要重新分配更大的空间，这会带来额外的开销因此，在选择顺序存储结构时，需要根据实际情况合理估计线性表的长度线性表的链式存储结构链式存储结构是指用一组任意的存储单元存储线性表的数据元素，这些存储单元可以是连续的，也可以是不连续的链式存储结构的特点是逻辑上相邻的元素在物理位置上不一定相邻链式存储结构的优点是插入和删除操作不需要移动元素，效率较高；缺点是随机访问不方便，需要从头开始遍历链表链式存储结构通常使用指针来实现，每个元素包含数据域和指针域，指针域指向下一个元素链式存储结构可以分为单链表、双向链表、循环链表等多种形式不同的链式存储结构适用于不同的应用场景，选择合适的链式存储结构可以提高程序的性能单链表的基本操作插入1在单链表的指定位置插入一个新节点需要修改指针，使新节点插入到正确的位置删除2从单链表中删除指定位置的节点需要修改指针，使链表保持连续查找3在单链表中查找指定值的节点需要从头开始遍历链表，直到找到目标节点或到达链表末尾双向链表双向链表是一种链式存储结构，每个节点包含数据域和两个指针域，分别指向前驱节点和后继节点双向链表的特点是可以从任意节点向前或向后遍历链表双向链表的优点是查找前驱节点方便，插入和删除操作更加灵活；缺点是需要额外的存储空间来存储前驱指针双向链表可以用于实现一些需要频繁访问前驱节点的应用，例如文本编辑器的撤销操作双向链表的实现需要注意维护两个方向的指针，以保证链表的正确性循环链表特点从循环链表的任何一个节点出发都可以2遍历整个链表定义循环链表是一种特殊的链表结构，其最1后一个节点的指针指向链表的第一个节点，形成一个环应用常用于处理具有周期性特点的数据，例3如操作系统中的时间片轮转调度栈的概念和特点定义特点应用栈是一种特殊的线性表，只允许在表的栈的特点是后进先出（），即最栈常用于表达式求值、递归调用、函数LIFO一端进行插入和删除操作后插入的元素最先被删除调用等场景栈的顺序存储结构栈的顺序存储结构是指用一段连续的存储单元依次存储栈的数据元素顺序存储结构的栈通常使用数组来实现栈的顺序存储结构需要一个指针来指向栈顶元素，方便进行插入和删除操作栈的顺序存储结构的优点是访问速度快，缺点是需要预先分配存储空间，容易造成空间浪费栈的顺序存储结构需要考虑栈的容量，当栈满时，无法进行插入操作；当栈空时，无法进行删除操作因此，在使用栈的顺序存储结构时，需要注意栈的容量和栈的状态，以保证程序的正确性栈的链式存储结构栈的链式存储结构是指用链表来存储栈的数据元素链式存储结构的栈不需要预先分配存储空间，可以动态地增加或减少节点链式存储结构的栈的优点是空间利用率高，缺点是访问速度慢栈的链式存储结构通常使用单链表来实现，栈顶元素指向链表的第一个节点栈的链式存储结构的插入和删除操作只需要修改指针，不需要移动元素，因此效率较高栈的链式存储结构可以用于实现一些需要频繁进行插入和删除操作的应用，例如浏览器的历史记录栈的应用表达式求值中缀表达式我们通常使用的表达式形式，例如1+2*3后缀表达式也称为逆波兰表达式，将运算符放在操作数之后，例如123*+求值过程使用栈来存储操作数和运算符，根据运算符的优先级进行计算，最终得到表达式的结果队列的概念和特点定义特点应用123队列是一种特殊的线性表，只允许队列的特点是先进先出（），队列常用于任务调度、消息队列、FIFO在表的一端进行插入操作，在另一即最先插入的元素最先被删除打印队列等场景端进行删除操作队列的顺序存储结构队列的顺序存储结构是指用一段连续的存储单元依次存储队列的数据元素顺序存储结构的队列通常使用数组来实现队列的顺序存储结构需要两个指针，分别指向队头元素和队尾元素，方便进行插入和删除操作队列的顺序存储结构的优点是访问速度快，缺点是需要预先分配存储空间，容易造成空间浪费队列的顺序存储结构需要考虑队列的容量，当队列满时，无法进行插入操作；当队列空时，无法进行删除操作为了解决队列满的问题，可以使用循环队列队列的链式存储结构队列的链式存储结构是指用链表来存储队列的数据元素链式存储结构的队列不需要预先分配存储空间，可以动态地增加或减少节点链式存储结构的队列的优点是空间利用率高，缺点是访问速度慢队列的链式存储结构通常使用单链表来实现，队头元素指向链表的第一个节点，队尾元素指向链表的最后一个节点队列的链式存储结构的插入和删除操作只需要修改指针，不需要移动元素，因此效率较高队列的链式存储结构可以用于实现一些需要频繁进行插入和删除操作的应用，例如消息队列循环队列解决假溢出“”循环队列可以有效地利用存储空间，避免假溢出现象1“”队头队尾相接2循环队列将队列的队头和队尾连接起来，形成一个环形结构判断队空队满需要特殊处理队空和队满的情况，例如设置标志位或保留一个空闲3单元当队列的顺序存储结构出现假溢出时，即队列还有空闲空间但无法插入新元素，可以使用循环队列来解决这个问题循环队列将队列的队“”头和队尾连接起来，形成一个环形结构，使得队列可以重复利用存储空间串的概念和特点定义1串是由零个或多个字符组成的有限序列，也称为字符串特点2串中的字符可以是字母、数字、符号等应用3串广泛应用于文本处理、模式匹配、数据压缩等领域串的存储结构顺序存储链式存储使用一组连续的存储单元来存储串中的字符可以使用固定长度使用链表来存储串中的字符可以按字符存储或按块存储链式的数组或动态分配的数组来实现存储结构的优点是插入和删除操作方便，缺点是存储密度较低算法KMP模式匹配1算法是一种高效的模式匹配算法，用于在一个文本串中查找一个模式串的出现位置KMP数组next2算法的核心是利用模式串的数组，来避免不必要的回溯KMP next时间复杂度算法的时间复杂度为，其中和分别是模式串和3KMP Om+n mn文本串的长度数组的概念和特点定义特点数组是由相同类型的数据元素组数组中的每个元素都有一个唯一成的有序集合的下标，可以通过下标访问元素应用数组广泛应用于各种程序设计中，例如存储图像、矩阵等多维数组的存储行优先列优先按行依次存储数组元素例如，对于二维数组，先存储第一行，按列依次存储数组元素例如，对于二维数组，先存储第一列，再存储第二行，以此类推再存储第二列，以此类推特殊矩阵的压缩存储对角矩阵只存储对角线上的元素，其余元素为零2对称矩阵1只存储上三角或下三角的元素，节省存储空间稀疏矩阵只存储非零元素及其位置信息，可以使3用三元组或十字链表来存储树的基本概念树1树是一种非线性数据结构，由（）个节点组成的有限集合当时，n n≥0n=0称为空树在任意一棵非空树中（）有且仅有一个特定的称为根的节点；1（）当时，其余节点可分为（）个互不相交的有限集合2n1m m0，其中每一个集合本身又是一棵树，并且称为根的子树T1,T2,…,Tm节点2树中的每个元素称为节点根节点3树的顶端节点称为根节点子节点4除根节点外，每个节点都可以有多个子节点树的存储结构双亲表示法孩子表示法孩子兄弟表示法用一组连续的存储单元存储树的节点，每用一组连续的存储单元存储树的节点，每每个节点包含数据域、指向其第一个孩子个节点包含数据域和指向其双亲节点的指个节点包含数据域和指向其孩子节点的指节点的指针和指向其兄弟节点的指针针针二叉树的概念和特点定义二叉树是每个节点最多有两个子树的树结构通常子树被称作“左子树（）和右子树（）”left subtree“”right subtree特点二叉树的每个节点最多有两个孩子节点，分别是左孩子和右孩子二叉树可以是空树，也可以是由一个根节点和两棵互不相交的左右子树组成应用二叉树广泛应用于搜索、排序、数据压缩等领域例如，二叉搜索树可以用于高效地查找数据，哈夫曼树可以用于数据压缩二叉树的遍历前序遍历1先访问根节点，然后前序遍历左子树，最后前序遍历右子树中序遍历2先中序遍历左子树，然后访问根节点，最后中序遍历右子树后序遍历3先后序遍历左子树，然后后序遍历右子树，最后访问根节点线索二叉树定义线索二叉树是一种特殊的二叉树，利用空指针来存储节点的前驱和后继信息1目的2线索二叉树的目的是加快二叉树的遍历速度线索化将二叉树中的空指针指向节点的前驱或后继的过程称为线索化3哈夫曼树与哈夫曼编码哈夫曼树哈夫曼编码哈夫曼树是一种带权路径长度最短的树，也称为最优二叉树哈哈夫曼编码是一种基于哈夫曼树的编码方式，用于数据压缩哈夫曼树的构建过程是将每个节点看作一棵树，然后每次选择两夫曼编码的原理是将出现频率较高的字符用较短的编码表示，个权值最小的树合并成一棵新的树，直到所有节点合并成一棵树将出现频率较低的字符用较长的编码表示图的基本概念图顶点图是一种非线性数据结构，由顶图中的每个数据元素称为顶点点和边组成顶点表示数据元素，边表示顶点之间的关系边顶点之间的连接称为边边可以是有方向的（有向图）或无方向的（无向图）图的存储结构邻接矩阵定义特点邻接矩阵是一种用矩阵来表示图中顶点之间关系的存储结构邻邻接矩阵的优点是简单直观，易于实现；缺点是需要占用大量的接矩阵的行和列分别表示图中的顶点，矩阵中的元素表示顶点之存储空间，特别是对于稀疏图间是否存在边图的存储结构邻接表定义邻接表是一种用链表来表示图中顶点之间关系的存储结构每个顶点对应一个链表，链表中存储与该顶点相邻的顶点特点邻接表的优点是节省存储空间，特别是对于稀疏图；缺点是实现较为复杂适用场景邻接表适用于存储稀疏图，可以有效地节省存储空间图的遍历深度优先搜索思想步骤12从图中某个顶点出发，依次访选择一个起始顶点；访

1.

2.问该顶点的邻接顶点，然后以问该顶点；依次访问该顶点

3.该邻接顶点为起点，继续进行的未被访问的邻接顶点；重

4.深度优先搜索，直到图中所有复步骤，直到图中所有顶点3顶点都被访问都被访问应用3深度优先搜索常用于查找路径、判断连通性等问题图的遍历广度优先搜索步骤选择一个起始顶点；访问该顶点；

1.

2.2依次访问该顶点的所有未被访问的邻

3.思想接顶点；重复步骤，直到图中所有

4.3从图中某个顶点出发，依次访问该顶点顶点都被访问1的所有邻接顶点，然后依次访问这些邻接顶点的未被访问的邻接顶点，直到图中所有顶点都被访问应用广度优先搜索常用于查找最短路径等问3题最小生成树算法Prim思想步骤应用从图中任意一个顶点开始，每次选择与当选择一个起始顶点；将该顶点加入算法常用于构建最小生成树，例如网

1.

2.Prim前生成树距离最短的顶点加入生成树，直生成树；每次选择与当前生成树距离最络布线等问题

3.到所有顶点都加入生成树短的顶点加入生成树；重复步骤，直

4.3到所有顶点都加入生成树最小生成树算法Kruskal思想将图中所有边按权值从小到大排序，然后依次选择权值最小的边加入生成树，如果加入该边会形成环，则舍1弃该边，直到所有顶点都加入生成树步骤将图中所有边按权值从小到大排序；依次选择权值最小的边加入生成树；如

1.

2.

3.2果加入该边会形成环，则舍弃该边；重复步骤和，直到所有顶点都加入生成树

4.23应用算法常用于构建最小生成树，例如电力网络规划等问题3Kruskal最短路径算法Dijkstra单源最短路径算法思想算法用于求解图中某个顶点到其他所有顶点的最短路径算法采用贪心策略，每次选择当前距离源点最近的顶点Dijkstra Dijkstra该算法要求图中所有边的权值都为非负数，并更新源点到其他顶点的距离最短路径算法Floyd多源最短路径算法用于求解图中任意两个顶点之间的最短路径1Floyd动态规划算法采用动态规划的思想，通过不断更新顶点之间的距离，最终得到2Floyd所有顶点之间的最短路径时间复杂度3算法的时间复杂度为，其中为图的顶点数Floyd On^3n拓扑排序有向无环图算法步骤应用拓扑排序是指将有向无环图中的顶点按照从图中选择一个入度为的顶点；将拓扑排序常用于任务调度、依赖关系分析

1.

02.一定的顺序排列，使得图中所有指向该顶该顶点从图中删除，并删除所有以该顶点等问题点的顶点都排在该顶点的前面为起点的边；重复步骤和，直到图

3.12中所有顶点都被删除查找的基本概念查找关键字12查找是指在数据集合中寻找满用于标识数据元素的某个域的足特定条件的元素值称为关键字查找算法3不同的查找算法适用于不同的数据结构和查找条件常见的查找算法有顺序查找、折半查找、分块查找、二叉排序树等顺序查找适用场景2顺序查找适用于数据集合无序的情况思想从数据集合的第一个元素开始，依次将1每个元素与目标元素进行比较，直到找到目标元素或遍历完整个数据集合时间复杂度顺序查找的时间复杂度为，其中为On n数据集合的元素个数3折半查找思想折半查找又称二分查找，要求数据集合必须有序每次将数据集合分成两半，然后将目标元素与中间元素进1行比较，如果目标元素小于中间元素，则在前半部分继续查找，否则在后半部分继续查找适用场景2折半查找适用于数据集合有序的情况时间复杂度折半查找的时间复杂度为，其中为数据集合的元素个3Olog n n数分块查找思想适用场景将数据集合分成若干块，每块中的元素可以无序，但块与块之间分块查找适用于数据集合部分有序的情况必须有序首先在索引表中查找目标元素所在的块，然后在该块中进行顺序查找二叉排序树定义二叉排序树又称二叉搜索树，是一种特殊的二叉树，满足以下条件（）若左子树不为空，则左子树上所有节点的值都小于1根节点的值；（）若右子树不为空，则右子树上所有节点的值2都大于根节点的值；（）左右子树也都是二叉排序树3特点二叉排序树可以用于高效地查找、插入、删除数据应用二叉排序树广泛应用于数据库、文件系统等领域平衡二叉树（树）AVL定义1平衡二叉树是一种特殊的二叉排序树，其左右子树的高度差不超过平衡二叉树可以保证查找、插入、删除操作的时间复杂度1为Olog n旋转操作2为了保持平衡，平衡二叉树在插入和删除节点时可能需要进行旋转操作，包括左旋、右旋、双旋等应用3平衡二叉树广泛应用于需要高效查找、插入、删除数据的场景树和树B B+树B树是一种平衡的多路查找树，常用于文件系统和数据库系统中树的特B B点是每个节点可以存储多个关键字，并且所有叶子节点都在同一层树B+树是树的一种变体，其所有关键字都存储在叶子节点中，并且叶子节B+B点之间通过指针连接树的优点是可以加快范围查找的速度B+哈希表定义哈希表是一种根据关键字直接访问内存存储位置的数据结构它通过哈希函数将关键1字映射到存储位置，从而实现快速查找哈希函数哈希函数是将关键字映射到存储位置的函数一个好的哈希函数应该能够2将关键字均匀地分布到存储位置，以减少冲突冲突处理当不同的关键字映射到同一个存储位置时，就会发生冲突常见3的冲突处理方法有开放定址法、链地址法等排序的基本概念排序排序算法12排序是指将数据集合按照一定不同的排序算法适用于不同的的顺序排列数据规模和排序条件常见的排序算法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序等稳定性3如果排序算法能够保证相同元素的相对位置不变，则该排序算法是稳定的插入排序适用场景插入排序适用于数据集合规模较小且基2本有序的情况思想将数据集合分成有序区和无序区，每次1从无序区中选择一个元素，插入到有序区的合适位置，直到无序区为空时间复杂度插入排序的时间复杂度为，其中On^23为数据集合的元素个数n希尔排序思想1希尔排序又称缩小增量排序，是对插入排序的一种改进它将数据集合分成若干个子序列，然后对每个子序列进行插入排序，随着增量的不断缩小，最终整个数据集合基本有序，最后进行一次插入排序适用场景2希尔排序适用于数据集合规模较大且无序的情况时间复杂度3希尔排序的时间复杂度与增量的选择有关，一般情况下为Onlog n冒泡排序与快速排序冒泡排序快速排序冒泡排序是一种简单的排序算法它重复地走访过要排序的数列快速排序使用分治法（）策略来把一个串行Divide andconquer，一次比较两个元素，如果他们的顺序错误就把他们交换过来（）分为两个子串行（）list sub-lists走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成选择排序与堆排序选择排序选择排序（）是一种简单直观的排序算法它的工Selection sort作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完堆排序堆排序（）是指利用堆这种数据结构所设计的一种排序Heapsort算法堆是一个近似完全二叉树的结构，并同时满足堆积的性质即子结点的键值或索引总是小于（或者大于）它的父节点复杂度堆排序的平均时间复杂度为Οn logn归并排序思想归并排序是一种分而治之的排序算法它将数据集合分成若干个子序列，然后将每个子序列进行排序，最后1将排序后的子序列合并成一个有序的数据集合适用场景2归并排序适用于数据集合规模较大的情况时间复杂度归并排序的时间复杂度为，其中为数据集合的元素3On lognn个数课程总结与展望本课程全面介绍了数据结构的基础知识，包括线性表、栈、队列、串、数组、树、图、查找、排序等通过本课程的学习，您已经掌握了各种常用数据结构的原理、特点及其应用，并能灵活运用这些数据结构解决实际问题希望本课程能够为您后续学习计算机科学奠定坚实的基础未来，数据结构将继续发展，涌现出更多新的数据结构和算法希望您能够不断学习，不断探索，为计算机科学的发展做出贡献。