常见的数据结构
- 数组—>方便通过下标随机访问数据
- 栈
- 先进后出
- 只能压入（push）/查看（peek）/删除（pop）栈顶
- 无法查找
- 队列
- 先进先出
- 从队首删除（remove），从队尾插入（insert），查看（peek）队首
- 循环队列
- 优先级队列
- 链表
- 单链表
- 在链首插入（因为没有序号，只有相对位置）
- 在特定数据后插入
- 删除特定数据
- 双端链表
- 可以在链首和链尾插入
- 因为删除最后一个数据后无法维护链尾，所以无法删除任何数据
- 双向链表
- 有序链表
- 树
| 数据结构 | 子结构 | 描述 | 特点 | 插入/删除 | 查找 | 遍历 |
|---|
| 线性表 | 链表 | 以相对位置放置数据 | 方便扩展 | O(1) | O(N) | O(N) |
| 数组 | 以绝对位置放置数据 | 大小一旦确定就无法修改 | O(1) | O(N) | O(N) |
| 有序数组 | 按关键字序列以绝对位置放置数据 | 二分查找 | O(1) | O(
log2N
log
2
N
) | O(N) |
| 栈 | 先进后出 | 模拟栈 | O(1) | ++ | ++ |
| 队列 | 先进先出 | 模拟队列 | O(1) | ++ | ++ |
| 树 | 二叉树 | 父节点至多有两个子节点 | 模拟现实树状对象 | O(1) | O(N) | 递归 |
| 搜索二叉树 | 实用，平衡插入和查找的效率 | 方便决定位置查找 | O(
log2N
log
2
N
) | O(
log2N
log
2
N
) | 递归 |
算法
| 算法 | 描述 | 复制 | 比较 | 交换 |
|---|
| 冒泡 | 通过n次循环：两两比较并交换，使得每次循环后选出第n值 | O() | O(
N2/2
N
2
/
2
) | O(
N2
N
2
) |
| 选择 | 通过n次循环：与选出的最值比较并交换，使得每次循环后选出第n值。与冒泡相比减少了交换次数 | O() | <=O(
N2/2
N
2
/
2
) | O() |
| 插入 | 从左边一个数的有序数组开始，右边的元素依次插入到左边的有序数组。当数量较多时二分查找的使用使得比较次数减少。 | O() | O() | O() |
| 希尔 | | O() | O() | O() |
| 快速 | | O() | O() | O() |
| 基数 | | O() | O() | O() |
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
