| 研究数据结构的核心(目标:设计高效的算法) | 逻辑结构 · 存储结构 · 基本操作(插入 · 删除 · 查找) | |
| 逻辑结构 | ||
|---|---|---|
| 线性结构 | 非线性结构 | |
| 定义 | 元素之间有一对一的线性关系 | 元素之间关系复杂，可能有层次或网络关系 |
| 例子 | 线性表(数组 · 链表) · 栈(后进先出,LIFO) · 队列(先进先出,FIFO) · 串(字符序列 · 字符串) · 数组 · 广义表 | 树(一对多) · 图(任意多对多) |
| 数据存储结构 | ||
| 顺序存储结构 | 链式存储结构 | |
| 定义 | 用连续的内存单元存储数据 | 用指针将不连续的内存单元链接在一起 |
| 特点 | 易于通过索引访问 · 插入和删除操作相对复杂，需要移动大量元素 | 灵活，支持动态扩展 · 插入和删除效率高，但随机访问速度慢 |
| 算法定义 | 解决特定问题的一系列明确的指令(数据+结构=算法) | |
| 算法的特性 | 有穷性 · 确定性 · 可行性 · 输入 · 输出 | |
| 数据结构中的关系 | 线性结构(一对一 · 直线结构) · 树形结构(一对多 · 分支结构) · 图形结构(多对多 · 网络结构) | |
| 抽象数据类型(ADT) | 定义了数据和操作，但与具体实现无关。 | |
