数据结构

发表于 更新于 阅读次数： 本文字数： 280 阅读时长 ≈ 1 分钟

hash

键值对

1
"key":value

计数排序使用的就是这个办法
复杂度O(n+max)
缺点：空间复杂度高，无法对浮点数或负数进行对比（数组下标不能为负数）

桶排序
每个里面装几个，再用其它进行排序，可以解决空间

基数排序
从个位到最高位，一级一级排列，每次都会把数字放在这个位数确定的地方
如

1
2
3
4
5
6
7
8
9
52 4554 555 6569 46444
第一次
52 4554 46444 555 6569
第二次
46444 52 4554 555 6569
第三次
52 46444 4554 555 6569
第四次
52 555 4554 6569 46444

queue(队列)

先进先出（访问）
查询快速，不好删除

stack(栈)

后进先出，撤回就是此种

linkList（链表）

删除更改方便，查询缓慢

树

层级结构都比较像一棵树
几个概念：

  • 层
  • 深度
  • 节点个数 叶子节点 非叶子节点

二叉树

每次最多只分两个叉

  • 节点个数等于2^层数-1

满二叉树

所有叶子节点都是全的

完全二叉树

除最后一层外，所有层数都是满的，且最后一层只有右边是缺的或不缺

完全二叉树和满二叉树都可以用数组实现（因为有规律）