数据结构与算法思维导图_数据结构与算法分析思维导图

数据结构与算法思维导图

暑假期间总结的，内容都比较基础，可用作基础复习！文章最下方有思维导图PDF版本下载链接！
再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。

简介

数据结构的基本概念

• 基本概念和术语

  • 数据

    • 数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合

  • 数据元素

    • 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理

  • 数据对象

    • 数据对象是具有相同性质的数据元素的集合，是数据的一个子集

  • 数据类型

    • 数据类型是一个值的集合和定义再次集合上的一组操作的总称

      • 原子类型

        • 其值不可再分的数据类型

      • 结构类型

        • 其值可以再分解为若干成分（分量）的数据类型

      • 抽象数据类型

        • 抽象数据组织及与之相关的操作

  • 抽象数据类型

    • 抽象数据类型（ADT）是指一个数学模型及定义在该模型上的一组操作

  • 数据结构

    • 数据元素都不是孤立存在的，他们之间存在某种关系，这种数据元素相互之间的关系称为结构

• 数据结构三要素

  • 数据的逻辑结构

    • 线性结构

      • 一般线性表

      • 受限线性表

        • 栈和队列
        • 串

      • 线性表推广

        • 数组
        • 广义表

    • 非线性结构

      • 集合

      • 树形结构

        • 一般树
        • 二叉树

      • 图状结构

        • 有向图
        • 无向图

  • 数据的存储结构

    • 顺序存储

      • 在逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

    • 链式存储

      • 不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

    • 索引存储

      • 在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。

    • 散列存储

      • 根据元素的关键字直接计算出该元素的存储地址，又称Hash存储。

  • 数据的运算

算法和算法评价

• 算法的基本的概念

  • 5个重要特征

    • 有穷性
    • 确定性
    • 可行性
    • 输入
    • 输出

  • 好的算法达到的目标

    • 正确性
    • 可读性
    • 健壮性
    • 效率与低存储量需求

• 算法效率的度量

  • 时间复杂度

    • 在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T（n）=O（f(n)）。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数

  • 空间复杂度

    • 算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S（n）=O(f(n)),其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

线性表

定义

• 零个或多个数据元素的有限序列

顺序存储—顺序表

链式存储

• 单链表（指针实现）

  • 单链表结点中只有一个指向其后继的指针

• 双链表（指针实现）

  • 双链表结点中有两个指针分别指向其前驱结点和后继结点

• 循环链表（指针实现）

  • 循环单链表

    • 最后一个结点的指针不是NULL，而改为指向头节点，从而整个链表形成一个环

  • 循环双链表

    • 头结点的prior指针还要指向表尾结点

• 静态链表（数组实现）

  • 静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域

栈和队列

栈

• 定义

  • 只允许在一端进行插入或删除操作的线性表

• 栈顶

  • 线性表允许进行插入和删除的那一端

• 栈底

  • 固定的，不允许进行插入和删除的另一端

• 栈的分类

  • 顺序栈
  • 链栈
  • 共享栈

队列

• 定义

  • 队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除

• 特性

  • 先进先出

• 队头

  • 允许删除的一端，又称队首

• 队尾

  • 允许插入的一端

• 队列的分类

  • 循环队列

    • 将循序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

  • 链式队列

    • 队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表.

  • 双端队列

    • 指允许两端都可以进行入队和出队操作的队列

  • 空队列

    • 不含任何元素的空表

树与二叉树

树的基本概念

• 定义

  • 树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当N>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、…、Tn,其中每一个集合本身又是一棵树，并且称为根的字树。

• 两个特点

  • 树的根节点没有前驱结点，除根结点外的所有结点有且只有一个前驱结点
  • 树中所有结点可以有零个或多个后继结点

• 相关概念

  • 度

    • 树中一个结点的子结点个数称为该结点的度，书中结点的最大度数称为树的度。
    • 度为0的结点称为叶结点（leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。

  • 结点间的关系

    • 结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
    • 同一个双亲的孩子之间互称为兄弟。
    • 结点的祖先是从根到该结点所经分支上的所有结点。
    • 以某结点为根的子树中的任一结点都称为该结点的子孙

  • 树的深度或高度

    • 树中结点的最大层次称为树的深度或高度。

  • 有序树和无序树

    • 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树

  • 路径和路径长度

    • 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。

• 树的性质

  • 1）树中的结点数等于所有结点的度数加1
  • 2）度为m的树中第i层上至多有m^(i-1)个结点（i>=1）
  • 3)高度为h的m叉树至多有（m^h-1）/(m-1)个结点
  • 4）具有n个结点的m叉树的最小高度为[logm(n(m-1)+1)]

二叉树的概念

• 定义

  • 二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

• 特点

  • 每个结点最多有两棵子树，所以二叉树不存在度大于2的结点
  • 左子树和右子树是有顺序的，次序不能任意颠倒。
  • 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

• 五种基本形态

  • 空二叉树
  • 只有一个根节点
  • 根结点只有左子树
  • 根结点只有右子树
  • 根结点既有左子树又有右子树

• 特殊二叉树

  • 斜树

    • 所有的结点都只有左子树的二叉树叫左斜树。所有的结点都只有右子树的二叉树叫右斜树。

  • 满二叉树

    • 在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树

  • 完全二叉树

    • 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树

  • 二叉排序树

    • 左子树上所有结点的关键字均小于根节点的关键字；右子树上的所有结点的关键字均大于根结点的关键字。

  • 平衡二叉树

    • 树上任一结点的左子树和右子树的深度只差不超过1

• 性质

  • 在二叉树的第i层上至多有2^(i-1)个结点（i>=1）

  • 深度为k的二叉树至多有2^k-1个结点（k>=1）

  • 对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0=n2+1

  • 具有n个结点的完全二叉树的深度为[log2^n]+1(x表示不大于x的最大整数)

  • 如果对一棵有n个结点的完全二叉树（其深度为[log2^{n]+1）的结点按层序编号（从第1层到第[log2}n]+1层，每层从左到右），对任一结点i（1<=i<=n）有：

    • 如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点2i
    • 如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i
    • 如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1

• 二叉树的存储结构

  • 顺序存储结构

    • 用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系

  • 链式存储结构

    • 用一个链表来存储一棵二叉树，二叉树中的每个结点用链表的一个链节点来存储二叉链表至少包含3个域：数据域data、左指针域lchild、右指针域rchild

• 遍历二叉树

  • 定义

    • 二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次

  • 遍历方法

    • 前序遍历

      • 前序遍历左子树，再前序遍历右子树

    • 中序遍历

      • 中序遍历根节点的左子树，然后是访问根结点，最后中序遍历右子树

    • 后序遍历

      • 从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根节点

    • 层序遍历

      • 从根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问

• 线索二叉树

  • 这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树

树与森林

• 树转换为二叉树

  • 1、加线

    • 在所有兄弟结点之间加一条连线

  • 2、去线

    • 对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子节点之间的连线

  • 3、层次调整

    • 以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

• 森林转换为二叉树

  • 1、把每个树转换为二叉树
  • 2、第一棵二叉树不动，从第二棵二叉树开始，依次把一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

• 二叉树转换为树

  • 1、加线

    • 若某结点的左孩子结点存在，将左孩子的n个右孩子结点都作为此结点的孩子，将该结点与这些右孩子结点用线连接起来

  • 2、去线

    • 删除原二叉树中所有结点与其右孩子结点的连线

  • 3、层次调整

    • 使之结构层次分明

• 二叉树转换为森林

  • 1、从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……,直到所有右孩子连线都删除为止，得到分离的二叉树。
  • 2、再将每棵分离后的二叉树转换为树即可。

• 树与森林的遍历

  • 前序遍历

    • 先访问森林中第一棵树的根结点，然后再依次先根遍历根的每颗子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。

  • 后序遍历

    • 是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去每一棵树的剩余树构成的森林。

• 应用

  • 二叉排序树
  • 平衡二叉树
  • 哈夫曼树和哈夫曼编码

图

图的定义

• 图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合

术语总结

• 图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头
• 图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
• 图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。
• 图上的边或弧上带权则称为网
• 图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。
• 无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林

图的存储结构

• 邻接矩阵

  • 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

• 邻接表

  • 图中顶点用一个一维数组存储，图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点Vi的边表，有向图则称为顶点Vi作为弧尾的出边表

• 十字链表

  • 在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点

    • 弧结点

      • 尾域tailvex

        • 指示弧尾顶点

      • 头域headvex

        • 指示弧头顶点

      • 链域hlink

        • 指向弧头相同的下一条弧

      • 链域tlink

        • 指向弧尾相同的下一条弧

      • info域

        • 指向该弧的相关信息

    • 顶点结点

      • data域

        • 存放顶点相关的数据信息

      • 定点名称firstin

        • 指向以该顶点为弧头的第一个弧结点

      • 定点名称firstout

        • 指向以该顶点为弧尾的第一个弧结点

• 邻接多重表

  • 是无向图的另一种链接存储结构

图的遍历

• 广度优先遍历

  • 类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1,w2,…w3，然后依次访问w1,w2,…w3的所有未被访问对的邻接顶点；再从这些访问过的顶点出发，访问他们所有未被访问过的邻接顶点…以此类推，直到图中所有顶点都被访问过为止。

• 深度优先遍历

  • 类似于树的先序遍历。从图中某个顶点v触发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个为曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

图的应用

• 最小生成树

  • 构成连通网的最小代价生成树称为最小生成树

• 最短路径

  • 对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源头，最后一个顶点是终点。

• 拓扑排序

  • 设G=（V,E）是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn,满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之间。则我们称这样的顶点序列为一个拓扑序列。

• 关键路径

  • 路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有更大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

查找

基本概念

• 查找

  • 在数据集合中寻找满足某种条件的数据元素的过程称为查找

• 查找表

  • 用于查找的数据集合称为查找表

• 关键字

  • 数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

• 静态查找

  • 无须动态地修改查找表，此类查找表称为静态查找表。

• 动态查找

  • 需要动态地插入或删除地查找表

• 平均查找长度

  • 在查找过程中，一次查找地长度是指需要比较地关键字次数

静态查找表

• 顺序查找

  • 一般线性表地顺序查找

    • 从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。

  • 有序表的顺序查找

    • 若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

• 折半查找

  • 折半查找又称二分查找，它仅适用于有序的顺序表。基本思路是：首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。在缩小的范围内继续进行同样的查找。

• 分块查找

  • 又称为索引顺序查找，它吸引了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。分块查找的过程分为两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；第二步是在块内顺序查找。

B树

• 二叉排序树
• 二叉平衡树
• B树、B+树

散列结构

• 散列表

  • 性能分析
  • 冲突处理

排序

比较类排序

• 交换排序

  • 冒泡排序（Bubble Sort）

    • 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  • 快速排序（Quick Sort）

    • 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

• 插入排序

  • 插入排序（Insertion Sort）

    • 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

  • 希尔排序（Shell Sort）

    • 1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

• 选择排序

  • 选择排序（Selection Sort）

    • 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

  • 堆排序（Heap Sort）

    • 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

• 归并排序

  • 归并排序（Merge Sort）

    • 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

非比较类排序

• 计数排序（Counting Sort）

  • 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

• 桶排序（Bucket Sort）

  • 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

百度网盘链接：
链接：https://pan.baidu.com/s/1tYLvdsQ3ySVkiUBkdG6GwA
提取码：xii3
（需要请自取）