数据结构总览

算法的复杂度

时间复杂度

• 概念

  • 执行算法所需要计算的工作量，可以理解为基本操作的计算随着数据量的提升，计算的工作量以指数增长，也就是增长率

• 针对递归求解

  • https://blog.csdn.net/u013048263/article/details/38676847

空间复杂度

线性表

顺序表

• 概念

• 类型

  • 数组
  • 动态链表

链表

• 类型

  • 单项链表
  • 双向链表
  • 单项循环链表
  • 双向循环链表

• 链表的操作

  • 插入
  • 删除

顺序表与链表的比较

栈与队列

栈

• 概念

  • 是一种只能在队首插入元素的线性表，主要特点是先进后出

• 结构划分

  • 顺序栈
  • 链式栈

• 操作

  • 进栈

    • 先移动栈首，再插入元素

  • 出栈

    • 先取出元素，再移动栈首

• 适用场景

  • 解决问题的过程中出现了一个子问题。凭借现在的条件无法解决，则先记下，等待能够解决他的条件出现再取出

• 实际使用场景

  • 括号匹配
  • 后缀表达式求值

队列

• 概念

  • 操作受限制的线性表，只能在一端插入，另一端删除

• 结构

  • 顺序队列

    • 循环队列（为了解决假溢出）

  • 链式队列

• 操作

  • 进队
  • 出队

串

匹配

• 暴力匹配
• KMP算法

树与二叉树

树

• 概念

  • 非线性的数据结构

• 基本术语

  • 结点的度:结点拥有的子树个数

  • 树的度

    • 树中各个节点度的最大值

  • 深度

  • 高度

  • 双亲

  • 兄弟

• 树的存储结构

  • 顺序存储结构

    • 1.双亲存储结构
      

      克鲁斯卡尔算法中有重要应用

      • 概念：用顺序表（数组）表示数，每个元素记录父节点（双亲）

  • 链式存储结构

    • 孩子存储结构
      

      实际就是图的邻接表结构

      • 先用顺序表存储每个节点，节点包含两个属性，一个存储data，一个存储左孩子节点，所有的孩子节点又作为一个链表

    • 孩子兄弟存储结构
      

      • 它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。 因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟

二叉树

• 概念

  • 1.在树的基础上，每个节点的度最多只能为2
  • 2.子树有左右顺序之分，不能颠倒

• 存储结构

  • 顺序存储结构
  • 链式存储结构

• 遍历算法

  • 递归遍历

    • 先序
    • 中序
    • 后序

  • 非递归遍历

    • 层次遍历

• 遍历算法的改进

  • 线索二叉树

应用

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

图

概念

基本术语

存储结构

• 邻接矩阵

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

• 邻接表

  • 一维数据存储节点信息，节点中存储边的信息

• 十字链表

• 邻接多重表

遍历算法

• 深度优先遍历
• 广度优先遍历

最小代价生成树

• Prim算法
• 克鲁斯卡尔算法

最短路径

• 迪杰斯特拉算法
• 弗洛伊德算法

排序

分类

• 插入类排序

  • 直接插入排序

  • 折半插入排序

  • 希尔排序

    执行到最后也会执行一趟直接插入排序

• 交换类排序

  • 冒泡排序
  • 快速排序

• 选择类排序

  • 简单选择排序

  • 堆排序

    完全二叉树

• 归并类排序

  • 二路归并排序

• 基数类排序

查找

顺序查找

折半查找

分块查找

二分查找+顺序查找

二叉排序树

• 定义

  • 左子树上的关键字均小于根关键字，右子树上的关键字均大于根关键字

• 操作

  • 查找关键字
  • 插入关键字
  • 删除关键字

二叉平衡树（AVL树）

树的高度约矮，查找效率越高

• 定义

  • 左右子树高度之差绝对不大于1

• 操作

  • 平衡调整
  • 删除节点

B-树（B树）

可以理解为m叉平衡查找树，但是约束更强，要求叶节点在同一层

• 定义

  • B-树中所有节点孩子节点个数的最大值成为阶

• 特性

  • 1.结点的分支数等于关键字数加一
  • 2.m阶B-数，每个节点必会有m/2向上取整-1个关键字
  • 3.节点内关键字有序

• 操作

  • 关键字查找
  • 关键字插入
  • 关键字删除

B+树

• 特性(与B-树的区别)

  • 1.B+树中含有n个关键字就含有n个分支
  • 2.m阶B+树，每个节点必会有m/2向上取整个关键字
  • 3.B+树中叶子节点包含信息，并且包含了全部关键字，叶子节点引出的指正引向记录
  • 4.B+树中，每个非叶节点只起到索引的作用
  • 5.在B+树上有一个指正指向关键字最小的叶子节点，所有叶子节点链接成一个线性链表

散列表（Hash表）

• 构造方法

  • 直接定址法
  • 数字分析法
  • 平方取中法
  • 除留余数法

• 解决冲突

  • 开放定址法

    • 线性探测法
    • 平方探测法

  • 链地址法

• 性能分析