第八课 数组、字符串与常见数据结构——程序里的“储物柜”一格一格存数据这一课是从“单个变量”走向“一组数据”的关键一步。本课要解决一个新问题如果我要同时保存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 i0;i5;i) { cin a[i]; }这里i0 → a[0] i1 → a[1] i2 → a[2] i3 → a[3] i4 → a[4]正好访问5个元素。所以for(int i0;in;i)配合a[i]是以后C算法题最常见的组合之一。八、经典程序阅读题int a[5] {1,2,3,4,5}; for(int i0;i5;i) { a[i] a[i] * 2; }问最后数组是什么不建议心算。做去画表i修改0a[0]21a[1]42a[2]63a[3]84a[4]10最终2 4 6 8 10九、一个容易错的问题看int a[5] {1,2,3,4,5}; for(int i1;i5;i) { a[i] a[i-1]; }有的会说1 2 3 4 5实际上i1a[1] a[0];变成1 1 3 4 5i2a[2] a[1];注意现在a[1]已经是1了。所以1 1 1 4 5i31 1 1 1 5i41 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 i0;i3;i) { for(int j0;j4;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 i0;i5;i) { s[i] s[4-i]; }我们逐步模拟。开始ABCDEi0s[0] s[4];变成EBCDEi1s[1] s[3];变成EDCDEi2s[2] s[2];还是EDCDEi3s[3] s[1];现在s[1]已经是D。变成EDDDEi4s[4] s[0];现在s[0]是E。最终EDDEE这个题适合训练学生数组/字符串程序一定要关注“右边的数据是不是已经被修改过”。二十一、字符串的周期这是CSP-J初赛经常考察的一类题。例题小老鼠按照CapsLock、A、S、D、F不断循环按键。最终产生的字符序列具有周期性ASDFasdfASDFasdf...周期为8。因此第81个字符可以用81 % 8快速确定。周期为881 % 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绕回来。三十二、循环队列的核心思想假设数组长度是50 1 2 3 4走到4以后(41)%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 i0;i4;i) { a[i1] a[i]; }建议同学们画i数组初始1 2 3 4 501 3 3 4 511 3 6 4 521 3 6 10 531 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 i0;in;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 i0;i4;i) { a[i] a[i1]; } cout a[0] a[4];模拟初始 2 4 6 8 10 i0 4 4 6 8 10 i1 4 6 6 8 10 i2 4 6 8 8 10 i3 4 6 8 10 10所以输出4 10四十、综合例题2字符串string s ABCDE; for(int i0;i3;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出12 3入42 3 4出23 4所以最后3 4这就是先进先出。四十三、本课的知识地图建议同学们自己画出来一组数据 │ ┌─────────┼─────────┐ ↓ ↓ ↓ 数组 字符串 栈/队列 │ │ │ 下标 字符 顺序 │ │ ┌──┴──┐ 循环 周期 栈 队列 │ │ │ │ 程序模拟 取模 后进先出 先进先出四十四、本课CSP-J必记口诀数组长度n下标0到n-1。二维数组第一维看行第二维看列。字符串字符用单引号字符串用双引号。字符串周期重复出现先找周期大数位置用取模。栈后进先出像一摞盘子。队列先进先出像排队。循环队列走到尽头绕回来别忘了取模。程序阅读不要凭感觉画状态表。四十五、本课练习第一组数组基础① 数组下标 ② 数组初始化 ③ 修改数组 ④ 循环访问数组第二组数组程序模拟① 前后元素 ② 累加 ③ 交换 ④ 最大/最小值 ⑤ 数组逆序第三组字符串① 字符与字符串 ② 字符串下标 ③ 字符串修改 ④ 长度 ⑤ 周期第四组栈重点入栈 出栈 栈顶 合法出栈序列第五组队列重点入队 出队 front rear 循环队列尤其练习(rear-frontn)%n以及(rear1)%nfront等循环队列判断。四十六、课后作业★ 基础题10题数组下标数组赋值字符串下标字符串长度栈/队列概念目标100%正确。★★ 程序阅读题5题重点训练数组 循环 字符串 循环 数组 条件 栈模拟 队列模拟要求必须画状态表。不能只写答案。★★★ CSP-J真题历年真题。要求每道题回答① 这道题考什么 ② 数据在哪里保存 ③ 数据怎么变化 ④ 最后问什么 ⑤ 我是怎么模拟出来的