数据结构思维导图

数据结构思维导图，帮助了解数据结构大纲，其中包括绪论，线性表，栈和队列，串，数组和广义表的超详细介绍还有代码。除此之外还有树，图，查找的大概内容。走过路过不要错过。

数据结构

• 数组和广义表
  • 数组
    • 数组的基本概念
      • 从逻辑结构上看，一维数组A是n（n＞1）个相同类型数据元素a1、a2、…、an构成的有限序列，其逻辑表示为： A=（a1，a2，…，an） 其中，ai（1≤i≤n）表示数组A的第i个元素。　一个m行n列的二维数组A可以看作是每个数据元素都是相同类型的一维数组的一维数组。由此看出，多维数组是线性表的推广。
      • 以C/C++语言为例，其中数组数据类型具有以下性质：
    • 一维数组的存储结构
    • 二维数组的存储结构
    • 特殊矩阵的压缩存储
      • 特殊矩阵的主要形式有： （1）对称矩阵 （2）上三角矩阵／下三角矩阵 （3）对角矩阵 它们都是方阵，即行数和列数相同。
        • • 子主题
          • 子主题
  • 稀疏矩阵
    • • 子主题
    • 稀疏矩阵和特殊矩阵的不同点
    • 稀疏矩阵的三元组表示
      • 约定：data域中表示的非零元素通常以行序为主序顺序排列，它是一种下标按行有序的存储结构。 这种有序存储结构可简化大多数矩阵运算算法。
      • 子主题
    • 稀疏矩阵的十字链表表示
      • 子主题
  • 广义表
    • 广义表的定义
    • 广义表重要概念：
      • 广义表的长度定义为最外层包含元素个数。 广义表的深度定义为所含括弧的重数。其中，原子的深度为0，空表的深度为1 。 广义表GL的表头为第一个元素a1，其余部分(a2，…，an)为GL的表尾。一个广义表的表尾始终是一个广义表。空表无表头表尾。 广义表的长度定义为表中最上层元素个数。 广义表的深度定义为所含括号的最大层数。其中，原子的深度为0，空表的深度为1 。
    • 广义表的存储结构
      • 子主题
• 图
  • 图的基本概念
  • 图的存储结构和基本运算算法
  • 图的遍历
  • 生成树和最小生成树
  • 最短路径
  • 拓扑排序
  • AOE网与关键路径
• 查找
  • 查找的基本概念
  • 线性表的查找
  • 数表的查找
  • 哈希表的查找
• 树和二叉树
  • 树的基本概念
    • 树的定义
      • 子主题
    • 树的基本术语
      • 子主题
      • 子主题
      • 子主题
      • 子主题
      • 树的性质
    • 树的基本运算
      • 子主题
      • 子主题
    • 树的存储结构
      • 双亲存储结构
      • 孩子链存储结构
      • 孩子兄弟链存储结构
      • 广义表的存储结构
  • 二叉树的概念和性质
  • 二叉树的存储结构
  • 二叉树基本运算及其实现
  • 二叉树遍历
  • 二叉树的构造
  • 线索二叉树
  • 哈夫曼树
  • 用并查集求解等价问题
• 串
  • 串的基本概念
    • 串（或字符串）是由零个或多个字符组成的有限序列。串包含于线性表
    • 串中所含字符的个数称为该串的长度（或串长）。 含零个字符的串称为空串，用Ф表示。
    • • 串相等：两个串的长度相等并且各个对应位置上的字符都相同时。所有空串是相等的。
    • 子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。真子串是指不包含自身的所有子串。
  • 串的基本运算
    • StrAssign(&s，cstr)：将字符串常量cstr赋给串s，即生成其值等于cstr的串s。 StrCopy(&s，t)：串复制。将串t赋给串s。 StrEqual(s，t)：判串相等。若两个串s与t相等则返回真；否则返回假。 StrLength(s)：求串长。返回串s中字符个数。 Concat(s，t)：串连接:返回由两个串s和t连接在一起形成的新串。 SubStr(s，i，j)：求子串。返回串s中从第i（1≤i≤n）个字符开始的、由连续j个字符组成的子串。
  • 存储结构
    • 串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构。
    • 串的顺序存储结构
      • 每个单元(如4个字节)只存一个字符，称为非紧缩格式（其存储密度小）。
      • 每个单元存放多个字符，称为紧缩格式（其存储密度大）。
    • 串的链式存储结构
      • 链串结点大小1时，链串的结点类型声明如图：
  • 模式匹配
    • BF算法分析
      • Brute-Force简称为BF算法，亦称简单匹配算法。采用穷举的思路。BF是指暴力的意思！
      • 例如，s="aaaabcd"，t="abc"。 BF算法思路：从s的每一个字符开始依次与t的字符进行匹配。
      • i,j分别扫描字符串s和t i从0到s.length-t.length循环。 对于每个s[i]，k=i,j=0开始比较 如果t扫描完毕，则返回i 若s全部比较完毕都没有返回，则返回-1
    • KMP算法
      • KMP就是快速地从主串中找出你想要的子串。仅仅后移模式串，比较指针不回朔
      • 基于BF算法，采用空间换时间的方式，提取保存有利于匹配的信息。 提取s还是t中的信息？每次从s不同字符开始匹配，而t总是从t0开始匹配 ->提取t中的信息 t中的什么信息？ -> 部分匹配信息。
• 栈和队列
  • 栈
    • 栈的定义
    • 栈的几个概念
    • • 栈的顺序存储结构及其基本运算实现
  • 栈的链式存储结构及其基本运算的实现
  • 队列
    • 队列的定义
    • 基本运算
    • 队列的顺序存储结构及其基本运算实现
    • 队列的链式存储结构及其基本运算的实现
• 线性表
  • 线性表及其逻辑结构
    • 线性表的定义
      • 线性表是一个具有相同特性的数据元素的有限序列。
      • 有穷性：数据元素个数是有限的。 一致性：所有元素性质相同，即属于同一数据类型。 序列性：数据元素由逻辑序号唯一确定。一个线性表中可以有相同值的元素。 逻辑关系：元素之间为1对1的关系。
      • 线性表中所含元素的个数叫做线性表的长度，用n表示，n≥0。n=0时，表示线性表是一个空表，即表中不包含任何元素。
    • 线性表的抽象数据类型描述
      • 1 初始化线性表InitList(&L)：构造一个空的线性表L。 2 销毁线性表DestroyList(&L)：释放线性表L占用的内存空间。 3 判线性表是否为空表ListEmpty(L)：若L为空表，则返回真，否则返回假。 4 求线性表的长8度ListLength(L)：返回L中元素个数n。 5 输出线性表DispList(L)：线性表L不为空时，顺序显示L中各结点的值域。 6 求线性表L中指定位置8某个数据元素GetElem(L，i，&e)：用e返回L中第i（1≤i≤n）个元素的值。 7 定位查找LocateElem(L，e)：返回L中第一个值域与e相等的逻辑位序。若这样的元素不存在，则返回值为0。 8 插入一个数据元素ListInsert(&L，i，e)：在L的第i（1≤i≤n）个元素之前插入新的元素e，L的长度增1。 删除数据元素ListDelete(&L，i，&e)：删除L的第i（1≤i≤n）个元素，并用e返回其值，L的长度减1。
      • 基本型操作：InitList, DestroyList 引用型操作：操作的结果不改变结构 加工型操作：操作的结果改变结构
      • 线性表的抽象数据类型：
  • 线性表的顺序存储—顺序表
    • 线性表顺序存储结构：把线性表中的所有元素按照顺序存储方法进行存储。即按逻辑顺序依次存储到存储器中一片连续的存储空间中。
    • 顺序表基本运算的实现
      • 算法参数说明
      • 删除顺序表中所有值为x的元素
        • 子主题
  • 线性表的链式存储—链表
    • 链表的概述
      • 线性表中每个元素有唯一的前驱元素和后继元素。
    • 设计链式存储结构时，每个逻辑元素用一个结点单独存储，为了表示逻辑关系，增加指针域。
      • 每个物理结点增加一个指向后继结点的指针域  单链表。 每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域  双链表。
    • . 链表和顺序表的比较
      • 存储密度
    • 单链表
      • 单链表增加一个头结点的优点
      • 单链表的特点
      • • 子主题
      • 线性表基本运算在单链表上的实现
    • 双链表
      • 在线性表的链式存储结构中，每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域 双链表。
      • 双链表的优点：
    • 循环链表
  • 应用
    • 两个表自然连接问题
      • 设计基本运算算法
        • • • 为什么与一般尾插法建表不一样？
  • 有序表
    • 有序表的概念
    • 有序表的存储结构及其基本运算算法
    • 有序表的归并算法
• 绪论
  • 什么是数据结构
    • 数据结构的定义
      • 数据是描述客观事物的数和字符的集合
      • 数据项是具有独立含义的数据最小单位，也称为字段或域
      • 数据对象是指性质相同的数据元素的集合，它是数据的一个子集
      • 数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合
      • 数据结构通常包括
        • 数据的逻辑结构
          • 由数据元素之间的逻辑关系构成
        • 数据的存储结构
          • 数据元素及其关系在计算机存储器中的存储表示，也称为数据的物理结构
        • 数据结构的运算
          • 施加在该数据上的操作
    • 逻辑结构
      • 逻辑结构的表示
        • 图表表示
          • 采用表格或者图形直接描述数据的逻辑关系
          • 采用表格或者图形直接描述数据的逻辑关系
        • 二元组表示
          • 数据逻辑结构表示方式，如：B=(D，R)。<x.y>,x为y的前驱元素，y为x的后继元素。若某个元素没有前驱元素则称该元素为开始元素，若没有后继元素，就称该元素为终端元素。对于对称序偶可用圆括号代替尖括号。
          • 数据逻辑结构表示方式，如：B=(D，R)。<x.y>,x为y的前驱元素，y为x的后继元素。若某个元素没有前驱元素则称该元素为开始元素，若没有后继元素，就称该元素为终端元素。对于对称序偶可用圆括号代替尖括号。
      • 逻辑结构的类型
        • 集合
        • 线性结构
          • 数据元素间有一对一的关系。其特点是开始元素和终端元素都是唯一的。
          • 数据元素间有一对一的关系。其特点是开始元素和终端元素都是唯一的。
        • 树形结构
          • 一对多的关系。
          • 一对多的关系。
        • 图形结构
          • 多对多的关系
          • 多对多的关系
    • 存储结构
      • 顺序存储结构
        • 顺序存储结构，是采用一组连续的存储单元存放所有的数据元素， 优点：存储效率高，实现对元素的随机存取 缺点：不便于数据修改
        • 顺序存储结构，是采用一组连续的存储单元存放所有的数据元素， 优点：存储效率高，实现对元素的随机存取 缺点：不便于数据修改
      • 链式存储结构
        • 优点：便于数据修改 缺点：存储空间利用率低，不能对元素进行随机存取
        • 优点：便于数据修改 缺点：存储空间利用率低，不能对元素进行随机存取
      • 索引存储结构
        • 优点：查找效率高。 缺点：需要建立索引表，从而增加了空间开销
        • 优点：查找效率高。 缺点：需要建立索引表，从而增加了空间开销
      • 哈希（或散列）存储结构
        • 优点：查找速度快（只存储数据不存储逻辑关系，一般只适合要求对数据能够进行快速查找和插入的场合）
        • 优点：查找速度快 特点：只存储数据不存储逻辑关系，一般只适合要求对数据能够进行快速查找和插入的场合
    • 数据类型与抽象数据类型
      • 数据类型（c/c++）
        • int型
          • int型可以有三个修饰符，即short（短整句），long（长整句）和unsigned（无符号整数）。
        • Boolean 布尔值型
        • float型
        • double型
        • char型
      • 抽象数据类型ADT
        • 指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法
  • 算法及其描述
    • 特性
      • 有穷性
      • 确定性
      • 可行性
      • 有输入
        • 作为算法加工对象的量值、通常体现为算法中的一组变量。一个算法有零个或者多个输入
      • 有输出
        • 一组与“输入”有确定对应关系的量值。一个算法有一个或者多个输出
    • 设计目标
      • 正确性
        • 要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的标准
      • 可使用性
        • 要求算法能够很方便地使用，也叫用户友好性
      • 可读性
        • 要求算法易于理解，算法的逻辑必须清晰的、简单的和结构化的
      • 健壮性
        • 要求算法有很好的容错性，即提供异常处理，能够对不合理的数据进行检查，不经常出现异常中断或死机现象
      • 高效性与存储量需求
        • 通常算法的效率主要指算法的执行时间；算法存储量指的是算法执行过程中所需的最大存储空间
    • 算法分析
      • 算法的时间性能分析（CPU时间）
        • 算法的频度T（n）
          • 假设算法的规模为n，如果10个整数排序，问题规模n就是10。 算法时间分析就是求出算法所有原操作的执行次数（也称频度），它是问题规模的函数，用T(n)表示。 算法执行时间大致等于原操作所需的时间*T(n)
        • 时间复杂度，T(n)用“O”表示
          • 由于由于算法分析不是绝对时间的比较，再求出T(n)后，通常进一步采用时间复杂度来表示 时间复杂度：用T(n)的数量级来表示，记作T(n)=O(f(n)) 也称为渐进时间复杂度，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。 因此算法时间复杂度分析实际上是一种时间增长趋势分析。
          • 一个没有循环的算法的执行时间与问题规模n无关，记作O(1)，也称作常数阶。 一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。 其余常用的算法时间复杂度还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。
        • 递归算法的时间复杂度分析
        • 　算法时间性能比较：
          • 假如求同一问题有两个算法：A和B，如果算法A的平均时间复杂度为O(n)，而算法B的平均时间复杂度为O(n2)。 　　一般情况下，认为算法A的时间性能好比算法B。
        • 简化的算法时间复杂度分析
      • 算法的空间性能分析（内存时间）
        • 简要分析
        • 递归算法的空间复杂度分析
      • 算法分析的目的：
        • 分析算法的时空效率以便改进算法性能
  • 从数据结构角度求解问题