第八课 数组、字符串与常见数据结构
——程序里的“储物柜”：一格一格存数据
这一课是从“单个变量”走向“一组数据”的关键一步。
本课要解决一个新问题：
如果我要同时保存100个、1000个数据怎么办？
这就进入了数组、字符串以及线性数据结构。
一、本课学习目标
第一层：数组
能够：
理解数组是什么
看懂数组定义
看懂数组下标
区分
a[0]、a[1]……能够进行数组程序模拟
能够判断数组元素最后的值
理解二维数组
第二层：字符串
能够：
理解
char和字符串看懂
string理解字符串下标
判断字符串长度
进行简单字符串模拟
利用周期解决简单字符串题
第三层：数据结构
初步理解：
数组 ↓ 栈 ↓ 队列并能够区分：
栈：后进先出
队列：先进先出
考试中，对栈，明确考查了“入栈顺序、出栈顺序、栈容量”等问题；队列则考查了入队、出队和循环队列等问题。
二、第一部分：为什么需要数组？
先问同学们一个问题：
如果要记录一个班40个同学的数学成绩。
不用数组：
int a1; int a2; int a3; int a4; ... int a40;太痛苦了。
我们希望：
a[0] a[1] a[2] ... a[39]于是：
数组就是“一排编号连续的储物柜”。
例如：
int a[5];可以想象成：
数组 a 下标： 0 1 2 3 4 ┌───┬───┬───┬───┬───┐ │ │ │ │ │ │ └───┴───┴───┴───┴───┘一共有5个格子。
三、重要的知识：数组下标从0开始
这是初学者最容易犯的错误。
int a[5];不是：
a[1] ~ a[5]而是：
a[0] ~ a[4]也就是说：
| 下标 | 元素 |
|---|---|
| 0 | 第1个 |
| 1 | 第2个 |
| 2 | 第3个 |
| 3 | 第4个 |
| 4 | 第5个 |
一定要让自己形成条件反射：
a[0]是第1个元素。
四、为什么C++从0开始？
可以先不讲复杂的内存地址。
只需要给同学们一个直观解释：
数组的第一个位置可以理解为：
“距离起点0格”第二个：
“距离起点1格”第三个：
“距离起点2格”所以：
第几个元素 = 下标 + 1反过来：
下标 = 第几个元素 - 1这个理解非常重要。
五、数组初始化
例如：
int a[5] = {10,20,30,40,50};对应：
下标 0 1 2 3 4 ┌────┬────┬────┬────┬────┐ a │ 10 │ 20 │ 30 │ 40 │ 50 │ └────┴────┴────┴────┴────┘所以：
cout << a[0];输出：
10cout << a[3];输出：
40六、数组程序阅读题的第一招
看到：
int a[5] = {10,20,30,40,50};不要只看代码。
建议同学们在草稿纸上画：
下标： 0 1 2 3 4 ───────────────── a： 10 20 30 40 50以后程序修改：
a[2] = 100;马上改成：
下标： 0 1 2 3 4 ────────────────── a： 10 20 100 40 50这就是：
CSP-J程序阅读中的“状态表”。
七、数组和循环是天生的一对
数组最大的价值就是：
可以和循环配合，一次处理大量数据。
例如：
int a[5]; for(int i=0;i<5;i++) { cin >> a[i]; }这里：
i=0 → a[0] i=1 → a[1] i=2 → a[2] i=3 → a[3] i=4 → a[4]正好访问5个元素。
所以：
for(int i=0;i<n;i++)配合：
a[i]是以后C++算法题最常见的组合之一。
八、经典程序阅读题
int a[5] = {1,2,3,4,5}; for(int i=0;i<5;i++) { a[i] = a[i] * 2; }问：
最后数组是什么？
不建议心算。
做去画表：
| i | 修改 |
|---|---|
| 0 | a[0]=2 |
| 1 | a[1]=4 |
| 2 | a[2]=6 |
| 3 | a[3]=8 |
| 4 | a[4]=10 |
最终：
2 4 6 8 10九、一个容易错的问题
看：
int a[5] = {1,2,3,4,5}; for(int i=1;i<5;i++) { a[i] = a[i-1]; }有的会说：
1 2 3 4 5实际上：
i=1
a[1] = a[0];变成：
1 1 3 4 5i=2
a[2] = a[1];注意！
现在a[1]已经是1了。
所以：
1 1 1 4 5i=3
1 1 1 1 5i=4
1 1 1 1 1最终：
1 1 1 1 1十、我们要建立一个重要思想
数组程序阅读题不是：
“看原来的数组。”
而是：
看程序运行过程中数组是怎么变化的。
所以一定要记录：
初始状态 ↓ 第一次修改 ↓ 第二次修改 ↓ …… ↓ 最终状态这和我们前面的“程序模拟”完全连接起来了。
十一、数组越界
例如：
int a[5];合法：
a[0] a[1] a[2] a[3] a[4]但是：
a[5]越界。
还有：
a[-1]也是越界。
所以：
长度为n的数组，下标通常是0 ~ n-1。
这是CSP-J初赛中重要的基础知识。
十二、二维数组
如果一维数组是一排储物柜：
那么二维数组就是：
一个教室里的座位表。
例如：
int a[3][4];表示：
3行4列可以画成：
列 0 1 2 3 ┌───┬───┬───┬───┐ 行 0 │ │ │ │ │ ├───┼───┼───┼───┤ 行 1 │ │ │ │ │ ├───┼───┼───┼───┤ 行 2 │ │ │ │ │ └───┴───┴───┴───┘十三、二维数组访问
a[1][2]表示：
第1行、第2列？
注意C++从0开始。
所以实际上是：
第2行、第3列。
这也是二维数组容易错的地方。
十四、二维数组和双重循环
例如：
for(int i=0;i<3;i++) { for(int j=0;j<4;j++) { cout << a[i][j] << " "; } cout << endl; }程序运行顺序：
a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3]可以把它理解为：
外层循环负责“走哪一行”，内层循环负责“这一行走哪一列”。
十五、第二部分：字符串
现在问孩子：
如果要保存：
HELLO怎么办？
可以：
char a[6] = {'H','E','L','L','O','\0'};非常麻烦。
C++还提供了：
string s = "HELLO";这就是字符串。
十六、字符串是什么？
对于我们小学生，可以先理解成：
字符串 = 一串字符排在一起。
例如：
HELLO实际上是：
H E L L O \0' \0 ' 是我们字符串的终止符，我们访问字符串，终止符是字符串结束的标志。
字符串也可以通过下标访问。
string s = "HELLO";那么：
下标： 0 1 2 3 4 5 ──────────── s： H E L L O \0于是：
s[0] == 'H' s[1] == 'E' s[4] == 'O'十七、字符和字符串一定要区分
这是初学者非常容易混淆的地方。
'A'是：
一个字符。
而：
"ABC"是：
一个字符串。
可以记：
'A' 一个小盒子 "ABC" 一串小盒子十八、字符串的长度
例如：
string s = "HELLO";长度：
5可以使用：
s.size()或者：
s.length()得到长度。
所以：
cout << s.size();输出：
5十九、字符串也可以修改
string s = "HELLO"; s[0] = 'Y';变成：
YELLO所以字符串程序阅读，也可以采用：
“下标 + 状态变化”
的方法。
二十、字符串程序模拟
例如：
string s = "ABCDE"; for(int i=0;i<5;i++) { s[i] = s[4-i]; }我们逐步模拟。
开始：
ABCDEi=0
s[0] = s[4];变成：
EBCDEi=1
s[1] = s[3];变成：
EDCDEi=2
s[2] = s[2];还是：
EDCDEi=3
s[3] = s[1];现在s[1]已经是D。
变成：
EDDDEi=4
s[4] = s[0];现在s[0]是E。
最终：
EDDEE这个题适合训练学生：
数组/字符串程序一定要关注“右边的数据是不是已经被修改过”。
二十一、字符串的周期
这是CSP-J初赛经常考察的一类题。
例题：
小老鼠按照：
CapsLock、A、S、D、F不断循环按键。
最终产生的字符序列具有周期性：
ASDFasdfASDFasdf...周期为8。
因此第81个字符可以用：
81 % 8快速确定。周期为8，81 % 8 = 1，所以答案是A。
二十二、为什么可以用取模？
假设：
A B C D不断循环：
A B C D A B C D A B C D...周期：
4那么：
第1个 → A 第2个 → B 第3个 → C 第4个 → D 第5个 → A 第6个 → B发现：
1 % 4 2 % 4 3 % 4 4 % 4 5 % 4但是由于第4个位置对应余数0，所以更准确地说：
位置 = (n-1) % 周期因此：
int pos = (n - 1) % 4;这就是：
“大规模循环”变成“小规模模拟”。
这是初赛中重要的数学+程序思想。
二十三、第三部分：数组、字符串、栈、队列有什么关系？
现在把前面的知识串起来。
它们都是：
“保存一组数据的方法”。
但组织方式不同。
数组
[1][2][3][4][5]特点：
按下标访问。
栈
像一摞盘子：
5 4 3 2 1最后进去的先出来。
后进先出 LIFO
队列
像排队：
1 → 2 → 3 → 4 → 5先来的人先走。
先进先出 FIFO
二十四、栈：后进先出
例如：
1入栈 2入栈 3入栈此时：
┌───┐ │ 3 │ ← 栈顶 ├───┤ │ 2 │ ├───┤ │ 1 │ └───┘出栈：
3再出：
2再出：
1所以：
入：1 2 3 出：3 2 1同学们要大量练习，判断这种“入栈—出栈”序列是否合法。
二十五、队列：先进先出
例如：
1 → 2 → 3 → 4第一个进入：
1第一个出去：
1然后：
2所以：
入：1 2 3 4 出：1 2 3 4这和排队买票完全一样。
二十六、栈和队列不要搞混
给同学们一个超级简单的口诀：
栈：后进先出——像一摞盘子。
队列：先进先出——像排队买票。
二十七、CSP-J最常见的栈题
例如：
1,2,3,4,5依次入栈。
问：
哪个出栈序列不可能？
孩子不能凭感觉。
应该模拟。
比如要求：
2,1,3,5,4可以：
1入 2入 2出 1出 3入 3出 4入 5入 5出 4出所以合法。
二十八、栈如何与第7课的递归联系起来？
这是重要的“知识串联”。
第7课：
函数调用 ↓ 调用栈第8课：
栈 ↓ 后进先出同学们应该明白：
递归不是凭空发生的，它的函数调用过程就是利用栈来管理的。
可以明确把“递归”和“栈”联系在一起，并想到递归调用层数过多可能导致栈空间溢出。
二十九、第四部分：数组模拟栈
如果不用stack，我们也可以自己用数组模拟。
例如：
int s[100]; int top = 0;入栈：
s[top] = x; top++;出栈：
top--; x = s[top];可以理解：
top ↓ ┌───┐ │ 3 │ ├───┤ │ 2 │ ├───┤ │ 1 │ └───┘top永远指向：
下一个可以放元素的位置。
三十、数组模拟队列
同样可以：
int q[100]; int front = 0; int rear = 0;入队：
q[rear] = x; rear++;出队：
x = q[front]; front++;所以：
front → 1 2 3 4 ← rear出队以后：
front → 2 3 4 ← rear三十一、为什么需要循环队列？
普通数组模拟队列会遇到一个问题。
例如：
[ ][ ][ ][ ][ ]连续入：
1 2 3 4 5然后出掉：
1 2变成：
[ ][ ][3][4][5] ↑ 空出来了前面虽然有空间：
[ ][ ]但是rear已经走到后面。
于是：
空间被浪费了。
循环队列通常通过取模让front、rear绕回来。
三十二、循环队列的核心思想
假设数组长度是5：
0 1 2 3 4走到4以后：
(4+1)%5 = 0于是：
0 → 1 → 2 → 3 → 4 ↑ ↓ └───────────────┘这就是：
环形数组。
三十三、循环队列两个重要公式
循环队列规则：
队空
rear == front队满
为了区分队空和队满，通常少使用一个空间：
(rear + 1) % MAXN == front元素个数
(rear - front + n) % n这些都是CSP-J中的直接考点。
对于小学生，参加初赛，不要求大量手写循环队列代码。
但是：
看到公式、会判断状态、会模拟指针移动。
这是初赛更重要的能力。
三十四、第五部分：CSP-J程序阅读中的“状态表”
今天我们把程序模拟进一步升级。
例如：
int a[5] = {1,2,3,4,5}; for(int i=0;i<4;i++) { a[i+1] += a[i]; }建议同学们画：
| i | 数组 |
|---|---|
| 初始 | 1 2 3 4 5 |
| 0 | 1 3 3 4 5 |
| 1 | 1 3 6 4 5 |
| 2 | 1 3 6 10 5 |
| 3 | 1 3 6 10 15 |
最终：
1 3 6 10 15这其实就是在做：
“程序运行的录像”。
三十五、数组题最容易错的三个地方
错误1：下标从1开始
错。
a[0]才是第一个元素。
错误2：忽略修改后的数组
例如：
a[i] = a[i-1];右边的a[i-1]可能已经被前面修改。
错误3：循环边界看错
例如：
for(int i=0;i<n;i++)执行：
n次不是n-1次。
三十六、字符串题最容易错的三个地方
错误1
把：
'A'和：
"A"当成一样。
错误2
忘记字符串下标从0开始。
错误3
看到重复出现的字符串，却一个一个模拟。
应该先问：
有没有周期？
如果有：
第n项 → (n-1)%周期可能一下就解决。
三十七、栈题最容易错的地方
不要背：
“看起来像可以。”
必须严格按照：
入栈 入栈 出栈 入栈 出栈 ……一步一步模拟。
三十八、队列题最容易错的地方
永远记住：
front：队头 rear：队尾入队：
rear移动出队：
front移动循环队列：
移动后要取模三十九、本课综合例题1：数组
int a[5] = {2,4,6,8,10}; for(int i=0;i<4;i++) { a[i] = a[i+1]; } cout << a[0] << " " << a[4];模拟：
初始： 2 4 6 8 10 i=0： 4 4 6 8 10 i=1： 4 6 6 8 10 i=2： 4 6 8 8 10 i=3： 4 6 8 10 10所以输出：
4 10四十、综合例题2：字符串
string s = "ABCDE"; for(int i=0;i<3;i++) { char t = s[i]; s[i] = s[4-i]; s[4-i] = t; }这是什么？
其实是在：
交换首尾字符。
第一次：
ABCDE ↓ EBCDA第二次：
EBCDA ↓ EDCBA第三次：
EDCBA所以最终：
EDCBA这个题是在考：
数组/字符串下标 + 临时变量 + 程序模拟。
四十一、综合例题3：栈
依次：
1入 2入 3入 2出 4入 4出 3出 1出问最终出栈顺序。
模拟：
1入 [1] 2入 [1,2] 3入 [1,2,3] 2出？不可能！
因为：
3在2上面。
所以：
栈题最重要的不是计算，而是判断“上面的东西挡没挡住”。
四十二、综合例题4：队列
依次：
1入 2入 3入 1出 4入 2出队列：
1 2 3出1：
2 3入4：
2 3 4出2：
3 4所以最后：
3 4这就是先进先出。
四十三、本课的知识地图
建议同学们自己画出来：
一组数据 │ ┌─────────┼─────────┐ ↓ ↓ ↓ 数组 字符串 栈/队列 │ │ │ 下标 字符 顺序 │ │ ┌──┴──┐ 循环 周期 栈 队列 │ │ │ │ 程序模拟 取模 后进先出 先进先出四十四、本课CSP-J必记口诀
数组
长度n，下标0到n-1。
二维数组
第一维看行，第二维看列。
字符串
字符用单引号，字符串用双引号。
字符串周期
重复出现先找周期，大数位置用取模。
栈
后进先出，像一摞盘子。
队列
先进先出，像排队。
循环队列
走到尽头绕回来，别忘了取模。
程序阅读
不要凭感觉，画状态表。
四十五、本课练习
第一组：数组基础
① 数组下标 ② 数组初始化 ③ 修改数组 ④ 循环访问数组第二组：数组程序模拟
① 前后元素 ② 累加 ③ 交换 ④ 最大/最小值 ⑤ 数组逆序第三组：字符串
① 字符与字符串 ② 字符串下标 ③ 字符串修改 ④ 长度 ⑤ 周期第四组：栈
重点：
入栈 出栈 栈顶 合法出栈序列第五组：队列
重点：
入队 出队 front rear 循环队列尤其练习：
(rear-front+n)%n以及：
(rear+1)%n==front等循环队列判断。
四十六、课后作业
★ 基础题
10题：
数组下标
数组赋值
字符串下标
字符串长度
栈/队列概念
目标：
100%正确。
★★ 程序阅读题
5题：
重点训练：
数组 + 循环 字符串 + 循环 数组 + 条件 栈模拟 队列模拟要求：
必须画状态表。
不能只写答案。
★★★ CSP-J真题
历年真题。
要求每道题回答：
① 这道题考什么？ ② 数据在哪里保存？ ③ 数据怎么变化？ ④ 最后问什么？ ⑤ 我是怎么模拟出来的？
