数据结构与算法

计算机二级数据结构与算法思维导图分享！下图清晰地梳理了算法、数据结构的基本概念、线性表及其顺序存储结构、栈和队列、线性链表等内容的脉络！希望对小伙伴们有帮助哦！

数据结构与算法

• 算法
  • 算法的基本概念
    • 概念：算法是指一系列解决问题的清晰指令
    • 4个基本特征：可行性、确定性、有穷性、拥有足够的情报
    • 两种基本要素
      • 对数据对象的运算和操作
        • 算数运算
        • 逻辑运算
        • 关系运算
        • 数据传输
      • 算法的控制结构（各操作之间的执行顺序）
        • 描述算法的工具
          • 同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同
          • 传统流程图
          • N-S结构化流程图
          • 算法描述语言
    • 设计的基本方法：列举法、归纳法、递推法、减半递推技术、回溯法
  • 算法的复杂度
    • 算法的时间复杂度：执行算法所需要的计算工作量
      • 问题的规模
      • 待处理的数据的状态
    • 算法的空间复杂度：执行算法所需的内存空间
      • 算法程序所占的空间
      • 输入的初始数据所占的存储空间
      • 算法执行各过程中所需的额外空间
        • 算法执行过程中的工作单元
        • 某种数据结构所需要的附加存储
• 数据结构的基本概念
  • 数据结构是自相互有关联的数据元素的集合，即数据组织形式。
    • 逻辑结构
      • 反应数据元素之间的逻辑关系
    • 存储结构
      • 数据的逻辑结构在计算机存储空间中的存放形式
      • 顺序存储
      • 索引存储
      • 散列存储
      • 链式存储
    • 对各种数据结构进行的运算
      • 数据
      • 数据元素
      • 数据对象
      • 数据的逻辑结构
        • 数据元素的集合D
        • 集合上的关系B=(D,R)
  • 按各元素前后件关系的复杂度
    • 非线性结构
    • 空的数据结构是线性还是非线性视具体情况而定
• 线性表及其顺序存储结构
  • 线性表的基本概念
    • 线性表（线性结构）最简单常用的一种数据结构
  • 线性表的顺序存储结构
    • 元素所占的存储空间必须连续
    • 元素在存储空间的位置是按逻辑顺序存放的
  • 线性表的插入运算
    • 最坏情况，插入在第一个，其他均需要移动
  • 线性表的删除运算
• 栈和队列
  • 栈及其基本运算
    • 基本概念
      • 栈是一种特殊的线性表，插入和删除运算都在线性表的一段进行，先进后出，后进先出
        • 常考
      • 栈顶：允许插入和删除的一段
      • 栈底：栈的另一端
      • 空栈：栈中没有元素的栈
    • 特点
      • 栈顶元素是最先被插入和最后被删除的元素
      • 栈有记忆作用
      • 在顺序存储结构下，栈的插入和删除运算不需要移动表中其他数据元素
      • 栈顶指针top动态反应了栈中元素的变化情况
      • 顺序存储和运算
        • 入栈运算
          • 在栈顶位置插入一个新元素：栈顶指针+1，新元素插入到栈顶指针指向的位置，当栈顶指针指向最后即已满，上溢错误
        • 退栈运算
        • 读栈顶运算
  • 队列及其基本运算
    • 基本概念
      • 队尾：允许插入的一端
        • 线性结构
          • 有且只有一个根节点，且每个节点最多只有一个直接前驱和一个直接后驱的非空数据结构（前件和后件）
      • 排头：允许删除的一端
    • 循环队列及其运算
      • 入队运算
        • 在循环队列的队尾加入一个新元素
        • 上溢：队列非空s=1，队尾指针等于队头指针，队列已满，不能入队运算
      • 退队运算
        • 从队头位置退出一个元素并赋给指定的变量
        • 下溢：队列为空s=0,不能进行退队运算
• 线性链表
  • 单链表/线性链表
    • 只有一个指针来存放下一个元素
  • 链式存储方式
    • 数据域
      • 存放数据元素值
    • 指针域
      • 存放指针（指针用于指向迁建或后件）
• 树和二叉树
  • 树可以有无数个结点，但二叉树最多有两个
  • 树的基本概念
    • 树是简单的非线性结构
    • 根：有且仅有一个没有前驱的节点
    • 父节点：每个节点只有一个前件，无前件的节点只有一个
    • 子节点：每个节点可以有多个后件，无后件的节点称为叶子节点
    • 树的度：所有节点最大的度
    • 树的深度：树的最大层次
  • 二叉树的定义及其基本性质
    • 二叉树的定义
      • 非线性结构，有限的节点集合
        • 完全二叉树
          • 满二叉树
          • （ ）
      • 可为空，空的二叉树无节点，非空二叉树有且只有一个根节点
      • 每个节点最多可以有两棵子树，左子树和右子树
    • 二叉树的基本性质
      • 在二叉树的遍历中无论是前序遍历，中序遍历还是后序遍历，二叉树的叶子节点优先
      • 在二叉树的第k层上至多有2k-1个节点
      • 深度为m的二叉树至多有2m-1个节点
      • 对任何一棵二叉树，度为0的节点（叶子节点）总是比度为2的节点多一个
      • 具有n个节点的完全二叉树的深度至少为[log2n]（整数部分）+1
    • 满二叉树与完全二叉树
      • 满二叉树
        • 除最后一层外，每一层的所有节点都有两个子结点
        • 每一层的节点数都达到最大值，第k层有2k-1个结点
        • 深度为m的二叉树有2m-1个结点
      • 完全二叉树
        • 除最后一层外，每一层的节点数均达到最大值
        • 在最后一层上只缺少右边的若干结点
        • 叶子结点只可能在层次最大的两层上出现，对于任何一个结点，其右分支的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次为p或p+1
  • 二叉树的遍历
    • 原则：先左后右
    • 分类
      • 前序遍历
        • 根节点→左子树→右子树
      • 中序遍历
        • 左子树→根节点→右子树
      • 后序遍历
        • 左子树→右子树→根节点
• 查找技术
  • 顺序查找
    • 只能用顺序查找的两种情况
      • 线性表为无序表
      • 链式存储的有序表
  • 二分法查找
    • 只适用于顺序存储的，按非递减排列的有序表
    • 查找方法
    • 最坏情况查找log2n次
• 排序技术
  • 交换类排序法
    • 冒泡排序法
      • 最坏情况比较次数为n（n-1）/2次
      • 平均执行时间o（n2）
    • 快速排序法
      • o（nlog2n）
      • 任取待排序序列中的某个元素作为基准
      • 分为左右两个子序列
      • 左子序列的排序码均≤基准元素的排序码
      • 右子序列的排序码锯≥基准元素的排序码
      • 然后排序，直到整个序列有序