数据结构

https://visualgo.net/zh/sorting

逻辑结构

• 集合结构
• 线性结构
• 树状结构
• 网络结构
  https://baike.baidu.com/item/%E9%80%BB%E8%BE%91%E7%BB%93%E6%9E%84

存储结构

• 顺序存储
• 链式存储
• 索引存储
• 散列存储
  https://blog.csdn.net/bbc955625132551/article/details/72629470

线性结构

• 线性表（链表），栈，队列，双队列，串，数组

  
  image.png

列表

• 静态链表

静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。

• 动态链表

动态链表是用内存申请函数（malloc/new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。

image.png
https://www.jianshu.com/p/73d56c3d228c

栈

• 链栈

  
  image.png

队列

• 循环队列
  // 顺序队列
  https://blog.csdn.net/zhangxiangDavaid/article/details/29195859

• 循序队列
  // 链式队列

  
  image.png

散列表

• 直接定址法

  
  image.png

• 除留余数法

  
  image.png

• 数字分析法

  
  image.png

• 折叠法

  
  image.png

• 平方取值法

  
  image.png

树

• 最小生成树（最小权重生成树）

最小生成树是一副连通加权无向图中一棵权值最小的生成树。

image.png

• 二叉排序树（二叉查找树、二叉搜索树）

  
  image.png

• 哈夫曼树

  
  image.png

树的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
https://juejin.im/post/5d6f33fe6fb9a06acc00a3b7

• 满二叉树

  
  image.png

• 完全二叉树
  叶结点个数：n-[n/2]

  
  image.png
  image.png

• 线索二叉树

  
  image.png
  

  线索数：n+1

• 树

树有先根和后根遍历；森林有先序和中序遍历；二叉树则有先序、中序和后序遍历。
其中，
树的先根遍历，森林的先序遍历和二叉树的先序遍历相互对应。
树的后根遍历，森林的中序遍历和二叉树的中序遍历相互对应。

堆

-定义：堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

• 最大堆：父节点的值比每一个子节点的值都要大。

  
  image.png

• 最小堆：父节点的值比每一个子节点的值都要小。

  
  image.png
• 应用场景

优先级队列
利用堆求 Top K
利用堆求中位数

• 堆排序：构建无序堆，从最后一个结点开始，从右到左，从下到上
  https://www.bilibili.com/video/av62952101?from=search&seid=17925035136853990347
  https://bajdcc.github.io/html/heap.html