数据结构

一张图带你了解数据结构。数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。如果有帮到你，不妨动动手指帮我点赞呀！

数据结构

• 字符串
  • 匹配算法
    • KMP
• 查找
  • 线性表
  • 散列表
    • 哈希表
      • 冲突
        • 1 拉链法
        • 2 开放寻址法
  • 树表
• 排序
  • 插入排序
  • 交换排序
  • 选择排序
  • 归并排序
• 图论
  • 图*基础
    • 度
      • 出度
      • 入度
    • 稀疏图
      • 边比较少
    • 稠密图
      • 边比较多
  • 最短路径
    • 1 Dijkstra
      • 单源最短路径
      • 子主题
    • 2 Floyd
      • dp
      • 子主题
    • 3 BellmanFord
      • 支持负边权
      • O(mn)
  • 最小生成树
    • 1 prime
      • 暴力
    • 2 kuruskal
      • 贪心+并查集
  • 有向无环图
  • 连通性
  • 邻接矩阵&&邻接表
    • 转化
• 基本概念
  • 数据
    • 能输入到计算机中并被程序识别的符合
  • 数据元素
    • 数据的基本单位
    • 最小单位：数据项
  • 数据结构
    • 相互之间存在一定关系的数据元素的集合
  • 逻辑结构
    • 数据元素间的逻辑关系
  • 时间复杂度
• 栈和队列
  • 栈
    • 思想
      • 先进后出
    • 建立
      • 只需维护一个top指针，s->next = top->next; top = s;
  • 队列
    • 思想
      • 先进先出
    • 顺序队列
      • 建立
        • 设front，rear指针
        • 初始化 rear=front=s；
        • s->next=null; rear->next=s; rear = s; //把s插入尾部
    • 循环队列
      • 队满判断//数组模拟
        • front==rear
        • front>rear
        • front<rear
• 线性表
  • 顺序表
    • 时间复杂度
      • O(1)
        • 按位查找
      • O(n)
        • 按值查找
        • 插入
        • 删除
        • 遍历
    • 思想
      • 用一段连续的储存单元储存元素
        • 缺点
          • 大小固定
          • 容易造成空间浪费
        • 有点
          • 对于小规模数据友好
  • 链表
    • 储存结构
      • 数据域(data)
      • 指针域(next)
    • 时间复杂度
      • O(1)
        • 删除
      • O(n)
        • 按值查找
        • 遍历
        • 插入
    • 建立方法
      • 头插法
        • 每次将新节点放在头节点后
        • s->next=first->next; first->next = s;
      • 尾插法
        • 每次将新节点放在终端节点后
        • * r = first; r->next=s;r=s;
      • s:新节点 first：头节点 r：保存尾节点
    • 删除节点注意事项
      • 按位删除
        • q=p->next;x=p->data; p->next=q->next; delete q;
        • 先new一个空节点 q
      • 按值删除
        • 找到p->next->data=x
        • q=p->next; p->next=q->next; delete q;
    • 双链表
      • 删除和插入都要双向更新
    • 循环链表
      • 同上
• 树
  • 树的逻辑结构
    • 树基础知识
      • 数据元素
        • 节点
      • 子树
        • 度：节点的子树个数
      • 深度
      • 路径
  • 树的储存结构
    • 双亲表示法
      • 一维数组存：data+parent
      • 分层储存
    • 孩子表示法
      • 顺序储存：child+*next
      • 顺序储存n个孩子的头指针
    • 兄弟孩子表示法
      • 二叉链表表示法：*firstChild+data+*rightSib
  • 二叉树的逻辑结构
    • 定义
      • n个节点的有限集合或空集
      • 由一个根节点和两颗互不相交的左右子树组成
    • 斜树
      • 所有节点都在左子树或者右子树
    • 满二叉树
      • 定义
        • 所有分支节点都存在左子树和右子树&&所有叶子都在同一层
      • 性质
        • 一定是一棵完全二叉树
    • 完全二叉树
      • 定义
        • 编号为i的结点与同样深度的满二叉树中编号为i的结点位置相同
      • 性质
        • 1. 深度为k的完全二叉树在k-1层是满二叉树
        • 2.叶子节点只能出现在最下两层&&最下层的叶子节点都集中在左侧连续位置
        • 3. 若有度为1的结点，有且只有一个且该节点只有左孩子
    • 性质
      • 叶子结点个数为n1，度为2的结点有n2个，则n1 = n2+1
      • 二叉树的第i层最多有2^(i-1) 个结点(i>=1)
      • 深度为k的二叉树中，最多有2^(k)-1个结点
      • 具有n个结点的完全二叉树的深度为logn+1
      • 对具有n个结点的完全二叉树从1开始按层编号
        • 如果i>1，则该结点双亲的编号为i/2，否则为根节点，无双亲
        • 如果2*i<=n,则结点i的左孩子的编号为2*i，否则无左孩子
        • 如果2*i+1<=n，则结点i的右孩子编号为2*i+1，否则无右孩子
    • 遍历
      • 前序
        • 根节点》左》右
      • 中序
        • 左》根节点》右
      • 后序
        • 左》右》根节点
  • 二叉树的储存结构
    • 顺序储存
      • 参考线段树的存法
    • 二叉链表
      • leftchild《《data》》rightchild
    • 三叉链表
      • data，*lchild，*rchild，*parent
  • 森林
    • 定义
      • m棵不相交的树的集合
    • 树森林的转换
      • 将树转换为二叉树
        • 1 加线
        • 2 去线
        • 3 层次调整
        • 遍历所得结果与转换后相同(转换前后所得遍历顺序一样)
      • 森林转换为二叉树
        • 1 将森林中的每棵树转换为二叉树
        • 2 将每棵树的结点作为兄弟，在所有根节点之间加上连线
        • 3 按照二叉树结点之间的关系进行层次调整
        • 遍历所得结果与转换后相同(转换前后所得遍历顺序一样)
      • 二叉树转换为森林
        • 1 加线
        • 2 去线
        • 3 层次调整
  • 最优二叉树
    • 哈夫曼算法
      • 定义
        • 带权路径长度最小的二叉树
      • 实现
        • 利用小根堆，每次取最小的两个元素，相加，再放入堆中，直至堆中只剩一个元素即为根
    • 哈夫曼编码
      • 前缀编码(一组编码中任一一组都不是其他任何组的一个编码前缀) 保证解码的唯一性