🤖 Assistant

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 📚 数据结构 | 第1章 绪论精讲

## 🎯 本章知识导航
```mermaid
graph TD
    A[绪论核心知识点] --> B[数据结构是什么？]
    A --> C[数据结构分类]
    A --> D[算法与复杂度]
    B --> B1[数据元素集合]
    B --> B2[数据的组织与操作]
    C --> C1[逻辑结构]
    C --> C2[存储结构]
    C1 --> C11[线性]
    C1 --> C12[树形]
    C1 --> C13[网状]
    C1 --> C14[集合]
    D --> D1[算法五要素]
    D --> D2[时间复杂度/空间复杂度]

📦 1.1 初识数据结构

数据结构是研究非数值的计算机程序设计操作对象（研究逻辑机构，存储结构，算法）

🧩 生活中的数据结构（先理解再记忆）

  • 图书馆管理：书籍按照索引号（逻辑结构）存储在不同书架（存储结构）
  • 快递分拣：包裹按地区（分类）、货架类型（存储方式）、扫码查询（操作算法）
  • 手机通讯录：姓名排序（线性结构） vs 微信好友分组（树形结构）

💡 专业术语解读

1
2
3
4
5
| 术语         | 相当于现实中的...          | 示例说明                   |
|--------------|---------------------------|---------------------------|
| 数据元素      | 独立物品                  | 一本具体的书/一条快递记录 |
| 数据项       | 物品属性                  | 书名/ISBN号/价格          |
| 数据对象     | 同类元素集合              | 所有计算机类书籍          |

A.数据（data）：

数据是客观事物符号的表示，（能输入计算机，计算机可处理的符号总称）

B.数据元素（data element）：

数据的基本单位，也成为结点或记录或顶点

数据元素（一个）可以有多个或者若干个数据项（data item）组成

C.数据项（data item）：

数据项是数据处理的最小单位

数据项（data item）是数据不可再分的最小单位，如学生信息记录中的学号、姓名等。

D.数据对象(data object):

数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。

（数据对象是讨论数据集合的抽象，是数据的一个子集。数据对象中的数据元素必须具有相同的特性，即属于同一个数据类型。）

e．数据结构（data structure）:

数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。

🧠 1.2 数据结构三要素

a.数据的逻辑结构

b.数据的物理结构

c.数据的运算及实现

🌳 逻辑结构（用户视角）

1
2
3
4
5
6
7
8
9
10
11
12
13
graph LR
    A[逻辑结构] 
    A --> B[线性结构]
    A --> C[非线性结构]
    C --> A1[树]
    C --> A2[图]
    C --> E[集合]
 B --> B1[线性表]
 B --> B2[栈]
 B --> B3[队列]
 B --> B4[串]
 B --> B5[数组]
 B --> B6[广义表]

🧱 存储结构（计算机视角）

1
2
3
4
5
6
7
8
9
10
11
12
13
1. **顺序存储**：数组式排列 ✨
   - 特点：元素连续存储，可通过索引直接访问
   - 优劣：访问快但插入删除开销大

2. **链式存储**：寻宝图模式 🔗
   - 特点：通过指针链接元素
   - 优劣：动态扩展方便但占用额外空间
3. **索引存储**：快递驿站扫码查包裹 🔗
   - 特点：索引项包含关键字 + 物理地址
   - 优劣：快速定位 + 支持范围查询
4. **散例存储**：凭取件码直取快递 🔗
   - 特点：
   - 优劣：
存储方式 典型应用 访问速度 空间成本 适用场景
顺序存储 数组/矩阵 ★★★★☆ 低 频繁随机访问
链式存储 链表/树结构 ★★☆☆☆ 中 动态数据增减
索引存储 数据库索引 ★★★☆☆ 高 快速检索+范围查询
散列存储 哈希表/缓存系统 ★★★★★ 可变 快速精确查找

注：★★★★★表示最优，★数量减少表示性能递减

⚙️ 1.3 算法分析核心

🎯 算法五大要素（BAT面试易考点）

  1. 确定性 → 同输入必然同输出
  2. 可行性 → 能通过计算机实现
  3. 有穷性 → 不能死循环（注意与程序的区别）
  4. 输入输出 → 至少一个输出

📈 复杂度分析诀窍

时间增长模型（关键口诀）

1
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)

常见复杂度场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 🧠 复杂度等级实战案例
def O_1_demo(arr):           # 常量级：哈希表查询
    return arr[0]

def O_logn_demo(n):          # 对数级：二分查找
    while n > 1:
        n = n//2

def O_n_demo(n):             # 线性级：单层循环
    for i in range(n):
        print(i)

def O_n2_demo(n):            # 平方级：冒泡排序
    for i in range(n):
        for j in range(n):
            a = i + j

✨ 复杂度计算技巧表

代码模式 时间复杂度 示例
简单语句 O(1) a = b + c
单层循环 O(n) for(i=0;i<n;i++)
嵌套循环 (两重) O(n²) 冒泡排序核心代码
递归调用（二分） O(logn) 二叉树查找
递归调用（非平衡） O(n) 链表遍历

🔑 1.4 学习方法建议

💡 三点学习哲学

  1. 多画图解 → 绘制数据结构形态演变图
  2. 手写代码 → 关键操作在纸上模拟执行
  3. 对比记忆 → 对比不同结构的CRUD复杂度

🛠️ 动手实验建议

1
2
3
- 实验1：用扑克牌模拟栈的入栈/出栈
- 实验2：用收纳盒做顺序存储 VS 行李箱做链式存储
- 实验3：给家庭成员画二叉树（父母结点/孩子结点）

📌 本章小结

✅ 数据结构 = 逻辑结构 + 存储结构 + 运算
✅ 算法优劣关键看时间/空间复杂度
✅ 分析复杂度要抓主要矛盾

复杂度增长趋势图

```

注：以上内容完整支持Markdown语法，可直接导入Obsidian/Notion等笔记软件，思维导图需支持Mermaid的编辑器查看。练习题目配套代码已整合核心知识要点。