《数据结构思维导图》
一、线性结构
1. 线性表 (Linear List)
1.1 定义
- 由n(n>=0)个相同类型数据元素构成的有限序列。
1.2 存储结构
- 顺序存储 (Sequential Storage):
- 使用连续的内存空间存储元素。
- 优点：访问速度快，通过下标直接访问。
- 缺点：插入和删除操作需要移动大量元素，空间利用率较低，需要预先分配空间。
- 链式存储 (Linked Storage):
- 使用节点存储元素，节点之间通过指针连接。
- 优点：插入和删除操作效率高，不需要移动元素，空间利用率高，按需分配空间。
- 缺点：访问速度慢，需要沿着指针查找，占用额外的存储空间存储指针。
1.3 基本操作
- 查找 (Search)
- 插入 (Insert)
- 删除 (Delete)
- 修改 (Modify)
1.4 应用
- 数组 (Array)
- 字符串 (String)
2. 栈 (Stack)
2.1 定义
- 一种特殊的线性表，只允许在表的一端进行插入和删除操作，遵循后进先出 (LIFO) 原则。
2.2 存储结构
- 顺序栈 (Sequential Stack)
- 链式栈 (Linked Stack)
2.3 基本操作
- 入栈 (Push)
- 出栈 (Pop)
- 查看栈顶元素 (Peek/Top)
- 判断栈是否为空 (IsEmpty)
2.4 应用
- 函数调用
- 表达式求值
- 括号匹配
- 深度优先搜索 (DFS)
3. 队列 (Queue)
3.1 定义
- 一种特殊的线性表，只允许在表的一端进行插入操作，另一端进行删除操作，遵循先进先出 (FIFO) 原则。
3.2 存储结构
- 顺序队列 (Sequential Queue)
- 循环队列 (Circular Queue): 解决顺序队列的假溢出现象。
- 链式队列 (Linked Queue)
3.3 基本操作
- 入队 (Enqueue)
- 出队 (Dequeue)
- 查看队头元素 (Peek/Front)
- 判断队列是否为空 (IsEmpty)
3.4 应用
- 广度优先搜索 (BFS)
- 任务调度
- 消息队列
二、非线性结构
1. 树 (Tree)
1.1 定义
- 由n(n>=0)个节点组成的有限集合。当n=0时，称为空树。当n>0时，存在一个根节点，其余节点可分为m(m>0)个互不相交的有限集合，每个集合又构成一棵树，称为根节点的子树。
1.2 术语
- 节点 (Node)
- 根节点 (Root)
- 父节点 (Parent)
- 子节点 (Child)
- 兄弟节点 (Sibling)
- 叶子节点 (Leaf)
- 树的深度/高度 (Depth/Height)
- 树的度 (Degree)
1.3 常见类型
- 二叉树 (Binary Tree)
- 满二叉树 (Full Binary Tree)
- 完全二叉树 (Complete Binary Tree)
- 平衡二叉树 (Balanced Binary Tree)
- 二叉搜索树 (Binary Search Tree)
- B树 (B-Tree)
- B+树 (B+ Tree)
- 红黑树 (Red-Black Tree)
- 堆 (Heap)
- 最大堆 (Max Heap)
- 最小堆 (Min Heap)
1.4 存储结构
- 顺序存储 (数组)
- 只适用于完全二叉树
- 链式存储 (节点包含数据和指向子节点的指针)
1.5 遍历方式
- 前序遍历 (Preorder Traversal)
- 中序遍历 (Inorder Traversal)
- 后序遍历 (Postorder Traversal)
- 层序遍历 (Level Order Traversal)
1.6 应用
- 文件系统
- 数据库索引
- 编译器的语法树
2. 图 (Graph)
2.1 定义
- 由顶点 (Vertex) 和边 (Edge) 组成的集合。
2.2 术语
- 顶点 (Vertex)
- 边 (Edge)
- 有向图 (Directed Graph)
- 无向图 (Undirected Graph)
- 邻接点 (Adjacent Vertex)
- 度 (Degree)
- 路径 (Path)
- 环 (Cycle)
- 连通图 (Connected Graph)
- 强连通图 (Strongly Connected Graph)
2.3 存储结构
- 邻接矩阵 (Adjacency Matrix)
- 邻接表 (Adjacency List)
2.4 遍历方式
- 深度优先搜索 (DFS)
- 广度优先搜索 (BFS)
2.5 常见算法
- 最短路径算法 (Shortest Path Algorithms)
- Dijkstra算法
- Floyd-Warshall算法
- 最小生成树算法 (Minimum Spanning Tree Algorithms)
- Prim算法
- Kruskal算法
2.6 应用
- 社交网络
- 地图导航
- 路由算法
三、查找
1. 顺序查找 (Sequential Search)
- 遍历整个数据结构，逐个比较。
2. 二分查找 (Binary Search)
- 适用于有序数据结构，每次将查找范围缩小一半。
3. 哈希查找 (Hash Search)
- 通过哈希函数将数据映射到哈希表中的位置。
4. 树表查找
- 利用树结构进行查找，如二叉搜索树，B树等。
四、排序
1. 插入排序 (Insertion Sort)
- 将未排序的数据逐个插入到已排序的序列中。
2. 选择排序 (Selection Sort)
- 每次从未排序的数据中选择最小 (或最大) 的元素放到已排序序列的末尾。
3. 冒泡排序 (Bubble Sort)
- 相邻元素两两比较，将较大的元素交换到后面。
4. 快速排序 (Quick Sort)
- 选择一个基准元素，将数据分成两部分，一部分小于基准元素，一部分大于基准元素，递归排序两部分。
5. 归并排序 (Merge Sort)
- 将数据分成两部分，递归排序两部分，然后将两部分合并。
6. 堆排序 (Heap Sort)
- 利用堆这种数据结构进行排序。
7. 希尔排序 (Shell Sort)
- 插入排序的改进版，通过分组的方式减少元素的移动次数。
五、总结
数据结构是计算机科学中非常重要的基础知识，理解各种数据结构的特性和适用场景，能够帮助我们设计出更高效的算法和程序。 选择合适的数据结构对于解决特定问题至关重要。