数据结构待实现清单

:material-circle-edit-outline: 约 298 个字 :material-clock-time-two-outline: 预计阅读时间 1 分钟

数据结构讲课套路

性质：顺序性质，结构性质

操作：比如查询，插入，删除

复杂度等特殊性质

做算法忌讳的就是算法里有不确定的地方

delete的套路就是转化为merge

树有两个常见的表示法

1. 正常的
2. 左儿子右兄弟

前者随机访问儿子速度快，但是空间开销大，因为多个儿子需要多个指针

后者随机访问儿子慢一点，但空间开销小，因为每个结点都只需要两个指针

选择哪个需要考虑

Linear

1. Linear List
   1. Create
   2. Empty
   3. Push
2. Stack
   1. Push
   2. Pop
3. Queue
   1. Array/List

Sort

1. 冒泡排序
2. 插入排序
3. 交换排序
4. 选择排序
5. 归并排序
6. 快速排序
7. 基数排序
8. 计数排序
9. 希尔排序
10. 堆排序
11. 桶排序
12. 哈希算法

Tree

1. 普通二叉树
   1. 三种遍历
2. BST
   1. Find 1. 递归/迭代
   2. Insert
   3. Delete
3. AVL
   1. 旋转
4. splay
5. Heap
   1. 最大堆/最小堆
   2. Create
   3. Empty
   4. Full
   5. Insert
   6. Delete
   7. Build
6. Huffman
   1. Build
7. Set
   1. Find
   2. Union

Graph

1. DEFINE
2. Create
3. Insert
   1. InsertVertex
   2. InsertEdge
4. 遍历
   1. DFS
   2. BFS
5. ShortestPath
   1. BFS
   2. Dijkstra
   3. Floyd
6. MST

Search

build, insert, delete,

1. AVL
2. Splay
3. BST
4. B
5. B+
6. Leftist Heap
   1. define
   2. merge
   3. delete
7. Skew Heap
8. Binomial Queue
   1. FindMin
   2. Merge 1. MergeTree 2. MergeQueue
   3. Insert
   4. DeleteMin