《数据结构》课件(C语言)第09章

《数据结构》课件(c语言)第09章目录contents数据结构基本概念回顾线性表及其顺序存储结构链表及其存储结构栈和队列数组和广义表目录contents树和二叉树图论基础查找技术排序技术01数据结构基本概念回顾数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它为算法提供服务，使算法在其上更有效地操作。数据结构可以分为线性结构和非线性结构。线性结构包括数组、链表、栈、队列等；非线性结构包括树、图等。数据结构定义及分类数据结构分类数据结构定义算法的设计取决于数据结构的特性，而数据结构的选择也会影响算法的效率。算法与数据结构紧密相关算法要求数据结构能够提供必要的信息，以便进行有效的操作。例如，查找算法要求数据结构能够提供快速定位元素的方法。算法对数据结构的要求算法与数据结构关系抽象数据类型（ADT）抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。ADT独立于具体的实现，它只描述数据类型和操作的行为特性，而不涉及具体的实现细节。抽象数据类型的实现抽象数据类型的实现是指根据ADT的定义，用具体的编程语言和数据结构来实现ADT所描述的操作。例如，可以用数组或链表来实现线性表的ADT。抽象数据类型介绍函数在C语言中，函数是实现算法和数据结构操作的基本单位。通过函数，可以将复杂的问题分解为多个简单的子问题，提高代码的可读性和可维护性。数组在C语言中，数组是一种基本的数据结构，它可以存储相同类型的元素，并且可以通过下标来访问元素。结构体结构体是C语言中一种自定义的数据类型，它可以包含多个不同类型的成员变量。通过结构体，可以实现更复杂的数据结构，如链表、树等。指针指针是C语言中一种重要的数据类型，它可以用来存储地址信息。通过指针，可以实现动态内存分配、链表等操作。C语言中数据结构实现方式02线性表及其顺序存储结构线性表定义及特点线性表定义线性表是一种具有n个元素的有限序列，其中元素按照顺序排列，每个元素都有前驱和后继（除首尾元素外）。线性表特点线性表中的数据元素之间是一对一的关系；除首尾元素外，每个元素有且只有一个前驱和一个后继；线性表的长度是动态变化的。顺序存储定义线性表的顺序存储结构是用一段连续的存储空间来依次存放线性表的元素，这种存储结构称为顺序存储结构或顺序表。顺序存储特点顺序表中元素按逻辑顺序依次存放在一组连续的存储单元中；顺序表的存储密度高，每个节点只存储数据元素；顺序表可以通过下标直接访问元素。顺序存储结构原理遍历顺序表依次访问顺序表中的每个元素。查找元素在顺序表中查找指定元素，可以顺序查找或二分查找。删除元素删除顺序表中的指定元素，需要移动删除位置后的所有元素。初始化顺序表为顺序表分配存储空间，并设置初始长度为0。插入元素在顺序表的指定位置插入一个元素，需要移动插入位置后的所有元素。顺序表基本操作实现使用顺序表解决约瑟夫环问题，通过循环遍历和删除操作实现。约瑟夫环问题使用顺序表实现一维数组的排序，如冒泡排序、插入排序等。一维数组排序使用顺序表实现栈和队列的数据结构，通过限制插入和删除操作的位置实现。栈和队列的实现使用顺序表实现字符串的存储和操作，如字符串拼接、查找子串等。字符串操作顺序表应用举例03链表及其存储结构VS链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表分类根据指针的不同，链表可分为单向链表、双向链表和循环链表等多种类型。链表定义链表定义及分类单链表存储结构原理单链表中的每个结点包含两部分，一部分是存储数据元素的数据域，另一部分是存储下一个结点地址的指针域。存储结构单链表通过每个结点的指针域将各个结点按顺序链接起来，形成一个线性结构。在单链表中，每个结点只有一个后继结点，除首结点外，每个结点有且只有一个前驱结点。原理初始化单链表插入元素删除元素遍历单链表单链表基本操作实现创建一个空的单链表，即头指针指向空。删除单链表中的指定元素，需要修改相应位置的前驱结点的指针域，使其指向被删除结点的后继结点。在单链表的指定位置插入一个新元素，需要修改相应位置的前驱结点的指针域。从头结点开始，依次访问单链表中的每个结点，直到尾结点为止。循环链表是一种首尾相接的链表，即尾结点的指针域指向头结点。在循环链表中，可以从任一结点出发访问到链表中的其他结点。双向链表中的每个结点包含两个指针域，一个指向前驱结点，另一个指向后继结点。双向链表可以更方便地实现某些操作，如反向遍历等。循环链表双向链表循环链表和双向链表简介04栈和队列

栈定义及特点栈(Stack)是一种特殊的线性表，其只允许在表的一端进行插入和删除操作。栈具有后进先出(LIFO,LastInFirstOut)的特点。栈的主要操作有：入栈(push)、出栈(pop)、取栈顶元素(top)等。栈的顺序存储结构通常使用一个一维数组来实现。定义一个栈顶指针，用于指示栈顶元素在数组中的位置。入栈操作：将元素添加到栈顶，栈顶指针加1。出栈操作：删除栈顶元素，栈顶指针减1。01020304栈顺序存储结构实现02030401栈链式存储结构实现栈的链式存储结构使用链表来实现。链表的头指针或尾指针可以作为栈顶指针。入栈操作：在链表头部或尾部插入新节点。出栈操作：删除链表头部或尾部的节点。队列(Queue)是一种特殊的线性表，其只允许在表的一端进行插入操作，在另一端进行删除操作。队列具有先进先出(FIFO,FirstInFirstOut)的特点。队列的主要操作有：入队(enqueue)、出队(dequeue)等。队列定义及特点03注意当队尾指针到达数组末尾时，需要进行循环移动，即将队尾指针移动到数组开头。01入队操作将元素添加到队尾，队尾指针加1。02出队操作删除队头元素，队头指针加1。队列顺序存储结构实现入队操作在链表尾部插入新节点，队尾指针指向新节点。出队操作删除链表头部的节点，队头指针指向下一个节点。如果链表为空，则队头指针和队尾指针都指向空。队列链式存储结构实现05数组和广义表数组是由相同类型的元素按一定顺序组成的集合，每个元素称为数组元素，每个元素受n个线性关系的约束，每个元素在n个线性关系中的序号称为该元素的下标，并称该数组为n维数组。数组的特点：结构固定，大小固定，元素具有相同的类型；元素的下标是其线性关系的序号，下标从0开始；数组在内存中连续存放，按行优先或列优先的方式存储。数组定义及特点将多维数组的第一维按照顺序存储，第二维及以后的维度在每个一维数组内部也按照顺序存储。这种方式下，多维数组元素的地址计算较为简单。按行优先存储将多维数组的第一维按照逆序存储，第二维及以后的维度在每个一维数组内部按照顺序存储。这种方式下，多维数组元素的地址计算相对复杂。按列优先存储多维数组存储方式VS特殊矩阵是指具有许多相同元素或零元素，并且这些相同元素或零元素的分布有一定规律的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。压缩存储方法：对于特殊矩阵，可以只存储其非零元素或不同元素，并利用这些元素在矩阵中的分布规律来确定它们在存储结构中的位置。这样可以大大节省存储空间，并提高矩阵运算的效率。特殊矩阵压缩存储方法稀疏矩阵是指矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律的矩阵。压缩存储方法：对于稀疏矩阵，可以采用三元组表或十字链表等数据结构来存储其非零元素。其中，三元组表由非零元素的值、行下标和列下标组成，十字链表则由行链表和列链表组成，每个链表节点包含非零元素的值、行（列）下标以及指向同一行（列）下一个非零元素的指针。稀疏矩阵压缩存储方法广义表是线性表的扩展，是由零个或多个单元素或子表所组成的有限序列。其中，单元素是原子类型的数据，子表也是广义表，广义表的元素可以是子表，而子表的元素还可以是子表，由此广义表是一个递归的数据结构。广义表的性质：广义表中的数据元素有相对次序；广义表的长度定义为最外层包含元素个数；广义表的深度定义为该广义表展开后所含括号的重数；广义表可以共享，即一个广义表可以被其他广义表所引用；广义表可以是一个递归的表，即广义表本身可以包含自己作为自己的子表。广义表定义及性质06树和二叉树当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。树（Tree）是n（n≥0）个结点的有限集。在任意一棵非空树中，有且仅有一个特定的称为根（Root）的结点。树定义及基本术语一个结点拥有的子树数称为该结点的度。结点的度（Degree）一棵树中，最大的结点的度称为树的度。树的度度为零的结点。叶子（Leaf）或终端结点度不为零的结点。非终端结点或分支结点树定义及基本术语二叉树（BinaryTree）是每个结点最多只有两个子树的树结构，通常子树被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）。二叉树的性质在二叉树的第i层上至多有2^(i-1)个结点（i≥1）。深度为k的二叉树至多有2^k-1个结点（k≥1）。对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。二叉树定义及性质二叉树遍历算法先序遍历（PreorderTraver…根结点->左子树->右子树。中序遍历（InorderTravers…左子树->根结点->右子树。后序遍历（PostorderTrave…左子树->右子树->根结点。层次遍历（LevelOrderTra…从根结点开始，自上而下逐层遍历，同一层中按从左到右的顺序遍历。线索二叉树（ThreadedBinaryTree）是对二叉树遍历的一种优化，利用空指针来指向二叉树的前驱结点和后继结点。线索化的实质是将二叉链表中的空指针改为指向前驱结点或后继结点的线索，同时为了区分普通指针和线索，需要给结点增加两个标志位来表明其左右指针是否为线索。线索二叉树根据线索性质的不同可分为前序线索二叉树、中序线索二叉树和后序线索二叉树。线索二叉树原理0102树转化为二叉树加线、去线、层次调整。加线在兄弟结点之间加一连线。去线对每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。层次调整以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。森林转化为二叉树森林由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。030405树和森林转化为二叉树方法07图论基础输入标题有向图与无向图图的定义图定义及基本术语图是由顶点集和边集组成的数据结构，表示为G=(V,E)，其中V是顶点集，E是边集。若图G'的顶点集和边集都是图G的顶点集和边集的子集，则称G'是G的子图；若G'是G的子图且包含G的所有顶点，则称G'是G的生成子图。在无向图中，与顶点v相关联的边的数目称为v的度；在有向图中，顶点v的度分为入度和出度。若图中的边有方向，则称为有向图；否则称为无向图。子图与生成子图顶点的度用一个二维数组表示图，数组元素表示顶点之间的邻接关系。适用于稠密图的存储。邻接矩阵邻接表十字链表邻接多重表用链表表示图，每个链表节点表示一条边。适用于稀疏图的存储。有向图的邻接表与逆邻接表的结合，适用于有向图的存储。无向图的邻接表的改进，适用于无向图的存储。图的存储结构深度优先遍历从某个顶点出发，尽可能深地访问图中的所有顶点，直到没有未访问的顶点为止。广度优先遍历从某个顶点出发，逐层访问图中的所有顶点，直到没有未访问的顶点为止。非递归遍历使用栈或队列等数据结构实现图的非递归遍历。图的遍历算法Prim算法从某个顶点出发，逐步增加边来构造最小生成树，每次选择当前生成树与外界顶点之间权值最小的边。要点一要点二Kruskal算法按照边的权值从小到大的顺序选择边来构造最小生成树，每次选择一条连接两个不同集合的边。最小生成树算法123求解单源最短路径问题，每次从未访问的顶点中选择一个距离源点最近的顶点进行访问，并更新其相邻顶点的距离。Dijkstra算法求解任意两点之间的最短路径问题，通过逐步构造中间点集合来更新任意两点之间的最短路径。Floyd算法可以处理带有负权边的最短路径问题，通过不断松弛所有边来更新源点到其他顶点的最短路径。Bellman-Ford算法最短路径算法08查找技术静态查找技术针对静态数据集（如数组）进行查找操作，数据在查找过程中不发生变化。动态查找技术针对动态数据集（如二叉搜索树）进行查找操作，数据在查找过程中可能会发生变化，如插入、删除等操作。散列查找技术利用散列函数将关键字映射到存储位置进行查找，具有较快的查找速度。查找技术分类算法思想时间复杂度优点缺点顺序查找算法在平均和最坏情况下，时间复杂度为O(n)，其中n为数据集中元素的个数。算法简单易懂，适用于小规模数据集。对于大规模数据集，查找效率较低。从数据集的第一个元素开始，逐个比较元素的关键字，直到找到与给定关键字相等的元素或遍历完整个数据集。算法思想又称二分查找，要求数据集有序。每次查找时，将数据集分成两半，确定待查找元素可能存在的区间，然后在该区间内继续折半查找，直到找到元素或区间为空。在平均和最坏情况下，时间复杂度为O(logn)，其中n为数据集中元素的个数。查找效率较高，适用于大规模有序数据集。要求数据集有序，对于无序数据集需要先进行排序操作。时间复杂度优点缺点折半查找算法散列表查找技术算法思想利用散列函数将关键字映射到存储位置进行查找。散列函数的设计应尽可能避免冲突，以提高查找效率。优点查找速度快，适用于大规模数据集。时间复杂度在理想情况下，时间复杂度为O(1)，即常数时间复杂度。但在冲突较多的情况下，查找效率会降低。缺点散列函数的设计和冲突处理方法的选择对查找效率有很大影响。同时，散列表需要额外的存储空间来存储关键字和存储位置的映射关系。09排序技术内部排序在内存