跳到主要内容

3.2 数据与结构

知识点​

1.什么是数据结构​

定义：数据结构是数据元素之间存在的一种或多种特定关系的集合，它包括数据的逻辑结构、存储结构和操作三个方面。

换个说法（更好懂）：数据结构解决"数据怎么组织、怎么存、能怎么操作"。

为什么需要数据结构：

  • 同样 1000 个数字，放在列表里能按下标快速访问；
  • 放在字典里能按名字快速查找；
  • 放在队列里能保证"先来先服务"。

结论：数据结构的选择决定了操作的效率——这是"程序 = 数据结构 + 算法"这句话的含义。

2.三个层面​

层面关注什么举例（学生名单）
逻辑结构数据元素之间的关系（线性／非线性）"名单是一串按学号排的序列"
存储结构在计算机中怎么存（顺序／链式）"放在一整块连续的内存里"
操作（运算）能做什么动作插入、删除、查找、排序、遍历

逻辑结构的分类（常考）：

逻辑结构
├── 线性结构（一对一）—— 线性表、栈、队列、串
└── 非线性结构
    ├── 树形结构（一对多）—— 树、二叉树
    └── 图形结构（多对多）—— 图

3.线性结构​

（1）数组／列表​

特点：元素排成一队，除首尾外每个元素只有一个前驱和一个后继；可以按下标（序号）随机访问。

优点：按下标访问极快（O(1)）；缺点：插入、删除要移动大量元素（O(n)）。

Python 的 list 就是"动态数组"——这就是本节后面重点讲的内容。

（2）栈（Stack）——后进先出​

特征说明
原则后进先出（LIFO，Last In First Out）
操作端只在一端（栈顶） 插入和删除
基本操作入栈（push）、出栈（pop）、取栈顶（top）、判空
生活类比叠盘子、子弹上膛、浏览器"后退"
典型应用函数调用（返回地址）、括号匹配、表达式求值、撤销操作（Ctrl+Z）

关键：栈只有一个口，进和出都在同一头。

（3）队列（Queue）——先进先出​

特征说明
原则先进先出（FIFO，First In First Out）
操作端一端进（队尾），另一端出（队头）
基本操作入队（enqueue）、出队（dequeue）、取队头、判空
生活类比排队买饭、打印任务队列、消息队列
典型应用打印缓冲、键盘缓冲区、任务调度、BFS 广度优先搜索

易混对比（必考）：

栈队列
原则后进先出先进先出
出入口同一端两端
类比叠盘子排队

（4）链表​

特点：元素（结点）不必连续存放，每个结点除了数据还保存指向下一个结点的指针。

优点：插入、删除只需改指针，不用移动元素；缺点：不能随机访问，找第 n 个必须从头一个个走。

4.非线性结构​

（1）树​

特点：一对多的层次关系，没有回路。

基本术语：

术语含义
根结点最上面的结点，没有父结点
叶子结点没有子结点的结点
父／子结点相邻两层的上下关系
子树某个结点及其所有后代构成的树
结点的度该结点子结点的个数
层次（深度）根为第 1 层，往下递增

二叉树：每个结点最多两个子结点（左、右）。

典型应用：文件目录结构、组织结构图、表达式树、决策树、数据库索引（B 树）。

（2）图​

特点：多对多的关系，由顶点（结点） 和边组成，可以有回路。

概念说明
无向图／有向图边有无方向（单向箭头）
权边上的数值（如两地距离、票价）
路径从一个顶点到另一个顶点经过的边序列

存储方式：邻接矩阵（二维表，1 表示相连）、邻接表。

典型应用：交通路线网、社交关系网络、通信网络、导航最短路径。

三种结构一句话对比：

结构关系例子
线性一对一排队、名单
树一对多目录、家族树
图多对多地铁线路、好友关系

5.Python 的列表（list）——最常用的线性结构​

（1）创建与索引​

scores = [78, 92, 65, 88, 95]
names = ["张三", "李四", "王五"]
empty = []
mixed = [1, "abc", 3.14, True]     # 可以混放不同类型（Python 特点）

索引规则（重点）：

写法含义
scores[0]第 1 个元素（下标从 0 开始）
scores[1]第 2 个元素
scores[-1]最后一个元素
scores[-2]倒数第 2 个

下标越界：scores[5]（长度 5 的列表）会报 IndexError: list index out of range。

（2）切片​

格式：列表[起始:终止:步长]

写法结果（以 [78,92,65,88,95] 为例）
scores[1:3][92, 65]（含 1 不含 3）
scores[:2][78, 92]（从头开始）
scores[2:][65, 88, 95]（到末尾）
scores[:]全部（复制一份）
scores[::-1][95, 88, 65, 92, 78]（倒序）
scores[::2][78, 65, 95]（隔一个取一个）

关键：切片同样是"含头不含尾"，与 range 一致。

（3）常用方法与函数（必背）​

操作写法说明
末尾追加lst.append(x)追加一个元素
合并列表lst.extend([a, b])把另一个列表的元素逐个加入
插入lst.insert(2, x)在下标 2 处插入
删除（按值）lst.remove(x)删除第一个值为 x 的元素
删除（按下标）lst.pop(2)删除并返回下标 2 的元素；pop() 删末尾
删除（关键字）del lst[2]按下标删除
查找下标lst.index(x)返回 x 首次出现的下标，不存在报错
计数lst.count(x)x 出现的次数
排序lst.sort()原地升序；sort(reverse=True) 降序
反转lst.reverse()原地反转
长度len(lst)元素个数
求和／最值sum(lst)／max(lst)／min(lst)数值列表常用
成员判断x in lst返回 True／False
清空lst.clear()删除全部元素

三个必须区分的点：

  1. append 与 extend：lst.append([1,2]) 得到"一个列表作为元素"，lst.extend([1,2]) 得到"两个元素"；
  2. sort() 与 sorted()：sort() 原地修改、返回 None；sorted(lst) 返回新列表、原列表不变；
  3. remove 按值、pop／del 按下标。
a = [3, 1, 2]
b = a.sort()          # a 变成 [1,2,3]，b 是 None！
print(b)              # None  ← 常见错误：以为 b 是排好序的列表

（4）列表推导式（简洁高效，考试常见）​

格式：[表达式 for 变量 in 序列 if 条件]

squares = [i * i for i in range(1, 6)]        # [1, 4, 9, 16, 25]
evens = [i for i in range(1, 21) if i % 2 == 0]  # 1~20 的偶数

等价于：

squares = []
for i in range(1, 6):
    squares.append(i * i)

读法："对序列中的每个 i，满足条件的，算出表达式的值放进列表"。

（5）遍历列表的两种方式​

# 方式一：直接取值（推荐，简洁）
for x in scores:
    print(x)

# 方式二：用下标（需要位置信息时）
for i in range(len(scores)):
    print(i, scores[i])

# 方式三：enumerate 同时取下标与值
for i, x in enumerate(scores):
    print(i, x)

（6）二维列表（矩阵）​

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(matrix[1][2])      # 6（第 2 行第 3 列）

遍历二维列表：

for row in matrix:              # 外层取一行
    for x in row:               # 内层取该行的每个元素
        print(x, end=" ")
    print()

求每行之和：

for row in matrix:
    print(sum(row))

易错：matrix[1][2] 是"先取行，再取列"，写成 matrix[2][1] 就变成 8。

6.元组（tuple）​

特点：有序、不可变（创建后不能修改元素），用圆括号。

point = (3, 5)
print(point[0])        # 3
# point[0] = 10        # 报错 TypeError: 'tuple' object does not support item assignment

用途：

  1. 表示不应被修改的数据（如坐标、日期）；
  2. 函数返回多个值时实际返回的就是元组；
  3. 可作为字典的键（列表不行，因为列表可变）。

单元素元组必须加逗号：t = (3,)，写成 (3) 只是数字 3。

7.字典（dict）​

特点：键值对（key-value） 的集合，键唯一且不可变，用花括号。

student = {"name": "张三", "age": 16, "score": 92}
print(student["name"])        # 张三
student["score"] = 95          # 修改
student["class"] = "高一(1)班" # 新增

为什么用字典：按"名字"查比按"位置"查更符合人的思维，且查找效率高（哈希表，接近 O(1)）。

操作写法说明
取值d[key]键不存在会报错 KeyError
安全取值d.get(key, 默认值)键不存在返回默认值，不报错
新增／修改d[key] = 值键存在则改，不存在则加
删除del d[key]／d.pop(key)—
取所有键d.keys()—
取所有值d.values()—
取所有键值对d.items()遍历时最常用
成员判断key in d判断的是键，不是值

遍历字典：

for k, v in student.items():
    print(k, ":", v)

易错：字典没有下标，d[0] 不等于"第一个元素"（除非真有键 0）；字典在 Python 3.7+ 保持插入顺序，但考试不必依赖这一点。

8.集合（set）​

特点：无序、元素不重复，用花括号但无冒号（或 set()）。

s = {1, 2, 3, 3, 2}
print(s)              # {1, 2, 3}  ← 自动去重
操作写法说明
交集a & b两个集合都有的元素
并集a.union(b)两个集合的全部元素（也可用竖线运算符 a ｜ b）
差集a - b在 a 中但不在 b 中的元素
添加a.add(x)加入一个元素
删除a.remove(x)／a.discard(x)remove 删不存在元素会报错，discard 不会
去重list(set(lst))列表去重的最简写法

最常用场景：给列表去重、判断两个名单的共同／独有成员。

注意：{} 是空字典，空集合要写 set()。

9.字符串（str）——特殊的"字符序列"​

字符串也是序列，支持索引、切片、遍历、in 判断，规则与列表一致。

方法作用示例
upper()／lower()转大写／小写"ab".upper() → "AB"
strip()去掉两端空白" a ".strip() → "a"
split(sep)按分隔符切分成列表"a,b,c".split(",") → ['a','b','c']
join(lst)用字符串连接列表"-".join(["a","b"]) → "a-b"
find(sub)查找子串首次出现的下标找不到返回 -1
count(sub)子串出现次数—
replace(old, new)替换（返回新串，原串不变）"abc".replace("b","x") → "axc"
startswith()／endswith()是否以某串开头／结尾—
isdigit()／isalpha()是否全为数字／字母—
len(s)字符串长度—

关键观念：字符串是不可变的——s[0] = "x" 会报错；replace、upper 等都返回新字符串，必须赋值接收。

s = "hello"
s.upper()          # 这样写没有任何效果
s = s.upper()      # 必须重新赋值 → "HELLO"

10.数据结构的选择建议（应用视角）​

需求推荐结构原因
按顺序存一批数据、要按下标访问列表随机访问快
要按"名字"快速查值字典哈希查找快
数据不能改元组不可变，安全
要去重／求交并差集合天然去重
后进先出（撤销、括号匹配）栈LIFO
先进先出（打印、任务调度）队列FIFO
层次结构（目录、组织）树一对多
网状关系（路线、社交）图多对多

11.速查表​

序号考点结论
1数据结构的三个方面逻辑结构、存储结构、操作
2线性结构关系一对一
3树的关系一对多
4图的关系多对多
5栈的原则后进先出（LIFO）
6队列的原则先进先出（FIFO）
7栈的出入口同一端
8队列的出入口两端（队头出、队尾进）
9栈的应用函数调用、括号匹配、撤销
10队列的应用打印缓冲、任务调度
11链表优点插删不需移动元素
12链表缺点不能随机访问
13列表下标起点0；[-1] 是最后一个
14切片边界含头不含尾
15倒序切片lst[::-1]
16追加一个append
17追加多个extend
18sort() 返回值None（原地排序）
19返回新列表的排序sorted(lst)
20列表推导式[表达式 for x in 序列 if 条件]
21二维列表取值matrix[行][列]
22元组特点不可变
23单元素元组(3,) 必须带逗号
24字典特点键值对，键唯一
25安全取值d.get(key, 默认值)
26in 判断字典判断的是键
27集合特点无序、不重复
28列表去重list(set(lst))
29空集合写法set()（{} 是空字典）
30字符串可变性不可变，方法返回新串
31split 与 join切分 ↔ 连接，互为逆操作
32find 找不到返回 -1

12.课堂提示（讲课参考）​

  • 栈和队列用实物演示：一叠作业本（只能从上面拿）、一队打饭的学生（先来先打），比讲定义直观十倍。
  • 列表方法让学生"错一遍"：b = a.sort() 得到 None，学生自己踩坑后再记 sorted() 就忘不掉。
  • 切片用"尺子量"的比喻：[1:3] 是"从第 1 格量到第 3 格之前"，含头不含尾与 range 统一讲，只学一个规则。
  • 字典用"学生档案"引入：说"我要查张三的成绩"，问学生用列表怎么查（得遍历找），用字典怎么查（d["张三"]）——数据结构的价值立刻体现。
  • 二维列表配九九乘法表、成绩表，为第 4 单元的矩阵类算法题铺路。