数据结构思维导图

这是一篇关于数据结构的思维导图，包含了线性表、串和数组、树和二叉树等内容，最细节的复习体系知识点梳理图，非常实用。

数据结构

• 绪论
  • 数据结构的研究内容
  • 基本概念和术语
    • 数据，数据元素，数据项和数据对象
    • 数据结构
      • 逻辑结构
        • 数据元素之间存在的一种或多种关系
        • 集合结构
        • 线性结构
          • 1．集合中必存在唯一的一个"第一个元素"； 2．集合中必存在唯一的一个"最后的元素"； 3．除最后元素之外，其它数据元素均有唯一的"后继"； 4．除第一元素之外，其它数据元素均有唯一的"前驱"。 数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。 如（a0,a1,a2,.....,an）,a0为第一个元素，an为最后一个元素，此集合即为一个线性结构的集合。
          • 一般线性表
          • 特殊线性表
          • 线性表的推广
        • 树结构
          • 树
          • 二叉树
        • 图结构
          • 无向图
          • 有向图
      • 存储结构
        • 顺序存储
        • 链式存储
    • 数据类型和抽象数据类型
  • 抽象数据结构的表示和实现
  • 算法和算法分析
  • 小结
• 线性表
  • 线性表的应用
    • 线性表的合并
    • 有序表的合并
  • 线性表的链式表示和实现
    • 单链表的基本操作的实现
      • 1.初始化2.取值3.删除，4.查找5.插入6.创建单链表
    • 循环链表
      • 首尾相连
    • 双向链表
      • 有两个指针域
    • 单链表的定义和表示
      • 数据域，指针域
  • 线性表的顺序表示和实现
    • 线性表的存储表示
      • 数据结构：length放元素个数，*指针放数组
    • 顺序表中的基本操作的实现
      • 1.初始化2.取值3.删除，4.查找5.插入
    • 顺序表移动元素：次数x=n-i+1第i个元素也需要移动
  • 顺序表和链表的比较
    • 时间复杂度比较
      • 1.找出算法中的基本语句2.算出基本语句的执行次数的数量级3.用O标记表示算法的时间性能
    • 空间复杂度比较
      • 占用的空间
• 栈和队列
  • 栈和队列的定义和特点
    • 栈的定义和特点
    • 队列的定义和特点
  • 队列的表示和操作的实现
  • 栈的表示和操作的实现
    • 队列的类型定义
    • 循环队列------队列的顺序表示和实现
      • 循环队列为了解决假溢出的情况 方法把队列变成环状结构： Q.rear=(Q.rear+1）% maxsize 或 Q.front=(Q.front+1% maxsize
      • 存储结构
        • 顺序表示
        • 链式表示
      • 初始化
      • 求循环队列的长度
        • （Q.rear-Q.front+MAXSIZE）%MAXSIZE 注意是不是前一个位置
      • 入队
      • 出队
      • 取队头元素
    • 链队---队列的链式表示和实现
  • 栈和递归
• 串和数组
  • 数组
    • 数组的顺序存储
      • 地址=loc(0.0)+(n*i+j)L//注意i,,j的开始是0还是1注意是行存储还是列存储
    • 特殊矩阵的压缩存储
      • 地址=j*(j+1)/2+i
  • 串
    • 模式匹配算法
      • bf算法
        • 需要的数据：位置，i,j，步骤：初始化，判断是否比较到末尾，继续比较后续字符，指针后退重新开始匹配，匹配成功返回位置，失败返回0;i-(j-1)是刚开始的位置所以返回i=i-j+2
      • kmp算法
        • 求next数组
    • 存储结构
  • 广义表
    • 广义表
      • 广义表中放松对表元素的原子限制，容许它们具有其自身结构 定义： 广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。
      • H是一个元素，T是一个表
• 树和二叉树
  • 树和二叉树的定义
  • 二叉树的性质和存储结构
    • 二叉树的性质
      • 节点数
        • 第i层有2的i-1次方个节点 i层的二叉树最多有2的k次方-1个节点
      • 节点的关系
        • n0=n2+1 证明： n0=n1+n2+n3 n-1=2n2+n1 联立解得
    • 满二叉树
      • 所有层节点数都达到最大
    • 完全二叉树
      • 除最后一层不满外，其他层全满
  • 遍历二叉树和线索二叉树
    • 遍历
      • 先序遍历
      • 中序遍历
      • 先中还原方法
        • 1.先找根，画出一二层 2.画左边，先序的下一个是根，根据中序判断在左还是在右（），重复 3.右边与步骤二相同
      • 后序遍历
      • 中后还原方法
        • 1.先找后序的最后一个为根 2.找中序，把后序分隔成两部分，找部分的最后一个 3.查看这个字符的前一部分，在左子树，后一部分在右子树
    • 线索二叉树
  • 哈夫曼树及其应用
    • 哈夫曼数的基本概念
      • 哈夫曼树又称最优二叉树 假设有m个权值，可以构造一个n个叶子节点的二叉树，其带权路径长度最小的二叉树称为最优二叉树 例如有a,b，c,d 其权值分别为7,5,2,4 ○ 7 / \ a ○ 5/ \ b ○ 2 / \4 c d wpl=7+5*2+2*3+4*3=35
    • 哈夫曼树的构造算法
      • 1.根据n个权值，构造n个权值的二叉树，共同构成森林 a b c d ○ ○ ○ ○ 7 5 2 4 2.选取权值最小的树作为左右子树构造一颗新的二叉树 ○ / \ c d 3.在森林中删除这两棵树 4.重复（2（3直到F只含一颗树为止 注：如果最小两个节点的值之和大于森林中的两个节点，就需要新开个子树
    • 哈夫曼编码
      • 在构造的哈夫曼树的 基础上根左0，根右1
  • 树和二叉树的抽象数据类型定义
  • 树和森林
    • 树的存储结构
    • 森林和二叉树的转换
      • 树到二叉树：兄弟之间连线，保留与第一个孩子的连线
      • 二叉树到树：化掉左孩子的右孩子连线，右孩子与根节点相连
      • 森林到二叉树：先转换成二叉树，再根节点相连转换成一棵树，后转换成二叉树
    • 树和森林的遍历
      • 树的遍历：先根遍历，后根遍历
      • 森林的遍历：先序遍历，中序遍历
• 图
  • 图就是各个顶点和各个边的集合组成的数据结构
  • 图的应用
    • 最小生成树能保证路径之和最小 最短路径：到达目的地的路径最小
    • 最小生成树
      • 对于带权值的连通图（通过DFS,或BFS一次遍历，可以遍历所有节点），可能有很多生成树 每颗生成树的的权值可能不同 权值最小的才是最小生成树 最小生成树唯一不唯一
      • Kruskal算法
        • 1.初始化：置U的初始值为v（包含G中的所有顶点），TE的初始值为空集（即图T中每一个顶点都构成一个连通分量） 2.将图G的边按权值大小选取； 如果构成环则舍弃；直到含有n-1条边为止。 加边法， 1.选择依次最小的权值边， 2.判断是否构成环，构成舍去，重复 3.直到含有n-1条边为止
        • 实现步骤
          • 准备阶段：要解决的问题是：怎么知道是否构成了环。 给每个顶点一个连通分量编号，当加过边之后，顶点的连通分量编号置为0； 1.将数组Edge中的元素按权值从小到大排序 2.依次查看数组Edge中的边，循环执行以下操作： if(vs1和vs2不等)输出此边，合并VS1,和VS2两个连通分量； If(相等舍去此边选择下一条权值小的边)
      • Prim算法
        • 找出两个集合的最小边 1).输入：一个加权连通图，其中顶点集合为V，边集合为E； 2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空； 3).重复下列操作，直到Vnew = V： a.在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； b.将v加入集合Vnew中，将边加入集合Enew中； 4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。 加点法，从头结点出发，找到第一个权值最小的边的那个顶点， 2.判断是否成环，成环就舍去
        • 实现步骤
          • 1.边的值放入lowcost中，
    • 最短路径
      • Dijkstra算法
      • Floyd算法
    • 拓扑排序
      • 一种排序方法。 例如:如果工程项目的步骤，只有先做A,再做B。画出拓扑图之后，利用拓扑排序算法，可以得到排序过程
      • 步骤
        • 1.从有向 图中选择一个没有前驱（即入度为0）的顶点并且输出它 2.从图中删去该节点，并且删去从该节点发出的全部有向边 3.重复，直到没有前驱的节点为止
    • 关键路径
      • 目的：解决做一件事最短的时间的问题 拓扑排序的结果是不一样的。 都可以解决问题，但是消耗的时间和资源不一样。 关键路径的目的是找出最短的时间。 理解错误。。。。。 关键活动（最早开始时间-最迟开始时间=0）组成的路径叫关键路径
      • 事件最早开始时间
        • 从开始到，到执行这个事件的时间就是事件的开始时间（汇点的不同时间取最大）
      • 事件的最迟发生时间
        • 事件的开始不得晚于下一事件的，开始时间。 就是事件的最迟发生时间
      • 活动的最早开始时间
        • 活动的最早开始时间，等于事件的最早发生时间
      • 活动的最迟开始时间
        • 这个事件的最迟开始-持续时间
  • 图的类型
    • 有向图
    • 无向图
  • 图的定义和基本术语
    • 子图
    • 无向完全图和有向完全图
      • 无向图：没有方向的图 有向图：有方向的图 无向完全图：~ 有向完全图：从一个地方可以到任何地方
    • 稀疏图和稠密图
    • 权和网
      • 带权值的边称为网
    • 路径和路径长度
    • 回路或环
    • 连通连通图和连通分量
      • 强连通图：所有的顶点都存在路径
    • 连通图的生成树
    • 有向树和生成深林
  • 图的存储结构
    • 邻接矩阵表示法
      • 用矩阵储存图； 1.输入总顶点数和边数 2.依次输入点的信息存入顶点表中 3.初始化邻接矩阵，使每个权值初始值为极大值 4.构造邻接矩阵。输入每条边依附的顶点及权值。确定两个顶点在图中的位置后，使相应的边赋予相应的权值，同时使其对称边赋予相同的权值 适合存储稠密图
    • 邻接表表示法
      • 邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。数组加链表 存储： 第一个结构体：边指向顶点的信息（位置，下一条边的指针） 第二个结构体：顶点；第一个结构体 第三个结构体：第二个结构体数组；图的顶点，边数；
      • 邻接表
      • 逆邻接表
    • 十字链表法
    • 邻接多重表
  • 图的遍历
    • 从图的某个顶点出发，以某个方法访问整个图，每个节点仅被访问一次
    • 深度优先搜索
      • 1.从顶点出发 2.访问下一节点，再从下一节点，访问未被访问的相邻节点 DFS算法：采用邻接表的结构 1.把已访问的的节点置为1 2.输出访问的额编号 3.p指向v的第一条边的头结点 4.判断是否为NULL 5不为NULL，指向第一个边，判读是否被访问 6.访问过指向下一条边，未访问调用函数自己。
    • 广度优先搜索
      • 1.访问顶点v 2.访问v的所有相邻节点v1,v2等。 3.访问v1的所有未被访问的节点
• 排序
  • 排序的概念
    • 内部排序方法的分类
    • 待排序记录的储存方式
    • 排序算法效率的评价标准
  • 交换排序
    • 冒泡排序
      • 算法
        • 1.将第一个数据与第二个数据比较，若大于就交换，然后比较第二个与第三个，依次类推。将最大的结果放到最大的位置上 2.第二次趟冒泡排序，次最大结果放到n-1大的位置上
    • 快速排序
      • 算法
        • 1.选择第一个记录作为枢轴，存在r[0]上，加上两个指针（low=1,high=L.length） 2.从右到左搜索，找到第一个小于枢轴的key,将其与key交换。 具体步骤：当low 3.从左向右搜索，找到第一个大于枢轴的key 交换。 具体操作：当low 4.重复2,3直到low和high相等为止。
  • 选择排序
    • 简单选择排序
      • 1.在代排数组中找最小的数据，与r[1]交换 2.从未排序中找第二个数据，与r[2]交换 3.依次类推
    • 树形排序
    • 堆排序
      • 堆排序：把堆pop输出 1.按堆的定义将待排序列调整成大顶堆，交换r[1],r[n] 2.将r[1..n-1]重新调整为堆，交换r[1]和r[n-1]，则r[n-1]为关键字次大的记录 3.循环n-1次，直到交换了r[1]和r[2]为止，得到了一个非递减的有序序列r[1....n】
      • 初建堆
      • 调整堆
      • 筛选法
        • 1.若r[s]>=r[2s],说明已经是堆了，不需要调整。 2.若r[s]
  • 基数排序
    • 多关键字排序
    • 链式基数排序
  • 外部排序
    • 外部排序的基本方法
    • 多路平衡归并的实现
    • 置换-选择排序
    • 最佳归并树
  • 归并排序
  • 插入排序
    • 直接插入排序
      • 概念
        • 将有序区的元素插入到无序区中
      • 算法
        • 1.在待排数组r[1~n]中，r[1]是有序序列 2.查找r[i]在已排序的序列中的位置， 。然后插入到有序表中。
    • 折半插入排序
      • 算法
        • 1.设存放在数组r[1~n]中，r[1]是一个有序序列 2.循环n-1次，每次使用折半查找，查找r[i]的位置,然后插入
    • 希尔排序
      • 算法
        • 1.第一趟取增量d1,将间隔为d1的分为同一组，在组间交换数据 2.取增量d2(d2 3.依次类推，直至增量取到dt=1;
• 查找
  • 线性查找
    • 顺序查找
      • 1.引入key值 2.for循环判断数组的值是否与key相等 3.若相等返回位置
    • 二分查找
      • 条件：要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列 算法步骤：1.判断key与mid=(high+low)/2 2.如果大于mid，low=mid.如果小于high=mid,如果等于就返回 3.回到步骤1
      • 建立判定树
        • 1.先找到根root=(low+high)/2 2.找左子树的根 3.找右子树的根 4.递归
    • 分块查找
      • 索引存储结构
        • 索引存储结构=数据表+索引表 索引表的每一项，称为索引项（关键字，地址） 索引的作用相当于目录，可以加快查找速度
      • 算法
        • 如：20个数据，你可以分成4块 建立索引块，每块放块中最大的元素，和第一个位置 1.建立索引表 2.判读属于哪个索引表中 3.顺序查找比较
  • 树形结构
    • 二叉排序树
      • 什么是二叉排序树：左子树的值小于根节点的值，右子树大于根节点的值，左右子树又是二叉排序树
      • 查找算法
        • 1.判读为空||等于关键值//递归出口 return 2.判读节点值与key值的大小 大 递归调用（bt->rightchilden,,k] 小 递归调用（bt->leftchildent ,k）
      • 插入算法
        • 1.判读为空//递归出口 1.new tree 2.左右子树赋值为空 3.数据域=key return tree; 2.判读节点值与key值的大小 大 递归调用（bt->rightchilden,,k] 小 递归调用（bt->leftchildent ,k） 等 返回
      • 删除算法
        • 1.if查找不到返回 查找到了 delete（） if(key>T->Now.data) 递归（T->rchildren） keynow.data 递归 （T->lchildren） delete ()算法的实现 1.如果该节点的右子树为空 重新连接左子树 2.左子树为空 重新连接右子树 3.左右均不为空 1.在左子树里找最大值 delete1()//一直向右找 if(r->rchild!=null） delete(r->rchilden) else p->key=r->key; p->data=r->data;值替换 q=r; r=r->lchild//删除r free(q); 2.在右子树里找最小值
    • 二叉平衡树
      • 目的：降低查找的次数 特殊的二叉排序树： 有以下性质： 左右子树的深度之差不超过1 左右子树也是平衡二叉树
      • 插入
      • 平衡因子bf
        • 该节点的左右子树深度之差
      • 平衡化旋转
        • RR,LL型
        • LR型
          • LR（L）型
            • 既然是LR型中的（L）型，证明比夫亲小，所以在父亲旋转上去时，它应该呆在左子树的右子树上
          • LR(R)型
            • 因为是LR(R)型，比父亲大，所以父亲选择上去时不变位置，当成为根节点时，变成原来根的左孩子
        • RL型
          • LR（L）型
            • 类似
          • LR(R)型
            • 类似
      • 算法
    • B-树（多路平衡查找）
    • B+树
  • 哈希查找
    • 快速查找记录的一种算法，构造哈希表来查找记录，以空间换取时间 适合的情况：存储地址=h(key) 地址与key值有函数关系 先构造一个哈希表(就像是一个数组) 通过哈希函数计算哈希值,然后放到哈希表中 例如是余数法 h(item) =item % (槽的大小)
    • 哈希表的概念
      • 什么是哈希表：地址与值有函数关系，通过关键值和关系形成的关系称为哈希表 例如：20个学号，201719044201-201719044220 可以用一个数组存储num[20]; 每个人存储在2017190442x-201719044201的位置上 查找某个人不需要比较存储的内容，可以直接通过学号-201719044201找到地址m'k
    • 哈希查找
    • 哈希冲突
      • 装填因子
        • 装填因子a=存储记录个数/哈希表的大小 a越大冲突越大，通常控制在0.6-0.9
      • 采用的哈希函数
        • 设计哈希函数
          • 直接定址法
            • 关键字k加上某个数值常量c h(k)=k+c 应用条件：知道key的分布情况，查找表小且连续的情况
          • 除留余数法
            • h(k)=k mod p p是小于或等于m的素数（能减少哈希冲突） 应用广，更可以在折叠，平方取中之后取模，保证散列地址一定落在散列表的地址空间中
          • 数字分析法
            • 数字分析法：从关键字中取数字分布均匀的若干位，作为哈希地址 条件：知道关键字集合，且比哈希表的地址码位数多
      • 解决冲突的方法
        • 开放定址法
          • 思想，在被占用的周围找位置
          • 线性探测法
            • di=(di上一个+1)mod max 缺点：产生非同义词冲突（本来该是这个位置却被不是这个位置的人占用了）
          • 平方探测法
          • 伪随机数序列
        • 链地址法法
          • 拉链法：想邻接矩阵的方法 左边可以找到值，右边是连接的链表 不会堆积，适合不确定表长的情况下， 坏处：需要指针空间
  • 概念
    • 静态查找
      • 查找数据
    • 动态查找
      • 查找时插入或删除元素
    • 查找表