301 lines
9.6 KiB
Markdown
301 lines
9.6 KiB
Markdown
# 第6课：一维数组
|
||
|
||
## 教学目标
|
||
- 掌握一维数组的定义、初始化和访问
|
||
- 能使用数组进行遍历、查找、统计等基本操作
|
||
- 理解数组逆序和冒泡排序的原理
|
||
|
||
## 核心考点：数组下标、遍历与越界
|
||
|
||
### 考什么
|
||
考试常要求读入一组数据并完成求和、最值、查找、逆序或排序，也会直接考某个下标对应哪个元素。所有数组题的基础都是正确理解下标范围并完整遍历。
|
||
|
||
### 必须理解
|
||
长度为 n 的数组包含 n 个元素，但合法下标是 `0~n-1`。`arr[i]` 表示第 i+1 个元素，而不是第 i 个元素。遍历通常写成 `for (int i=0; i<n; i++)`，这样第一个和最后一个元素都恰好访问一次。数组不会自动检查越界；访问 `arr[n]` 已经超出范围，可能读到垃圾值或破坏其他数据。打擂台求最值时，最安全的初值通常是 `arr[0]`，再从下标1开始比较。
|
||
|
||
### 核心写法
|
||
```cpp
|
||
int arr[100];
|
||
for (int i = 0; i < n; i++) cin >> arr[i];
|
||
|
||
int maximum = arr[0];
|
||
for (int i = 1; i < n; i++) {
|
||
if (arr[i] > maximum) maximum = arr[i];
|
||
}
|
||
```
|
||
数组容量要不小于 n，循环条件必须是 `i < n`。
|
||
|
||
### 常见错误
|
||
- 写成 `i <= n`，最后访问到不存在的 `arr[n]`。
|
||
- 把"第几个元素"和"下标是多少"混为一谈。
|
||
- 最大值初始化为0，遇到全负数数组时得到错误答案。
|
||
- 使用未初始化的数组元素参与计算。
|
||
|
||
### 判断是否掌握
|
||
给定数组长度 n，能立即说出首尾下标，能写出无越界的输入和遍历循环，并能正确完成查找、统计或打擂台。
|
||
|
||
---
|
||
|
||
## 题目一：数组入门 — 求最大值与平均值
|
||
|
||
### 核心代码（一句话）
|
||
> 数组遍历的核心：**`for (i = 0; i < n; i++)`**，下标从 0 开始，到 n-1 结束；打擂台求最值，先请第一个当擂主。
|
||
|
||
### 自然语言思路
|
||
老师手上有 n 个分数，要找出最高分和平均分。
|
||
|
||
第一步，把 n 个分数先存进数组 `arr[0]` 到 `arr[n-1]`，用 `cin` 配合 `for` 循环读入。
|
||
第二步，求最大值用"打擂台"：先假设 `arr[0]` 是最大的（擂主），然后从 `arr[1]` 开始逐个挑战，谁更大谁就当新擂主。
|
||
第三步，求平均值：先把所有元素加到一起（累加器初始为 0），循环一遍累加，最后除以 n。
|
||
第四步，注意平均值可能是小数，要用 `double` 类型，整数除整数会丢掉小数部分。
|
||
|
||
### 伪代码
|
||
```
|
||
1. 输入 n
|
||
2. 定义数组 arr[n]
|
||
3. for i = 0 到 n-1：
|
||
4. 输入 arr[i] // 读入数组
|
||
5. maxVal = arr[0] // 擂主
|
||
6. sum = 0
|
||
7. for i = 0 到 n-1：
|
||
8. if arr[i] > maxVal： // 打擂
|
||
9. maxVal = arr[i]
|
||
10. sum += arr[i] // 累加
|
||
11. avg = (double)sum / n // 整数转浮点数
|
||
12. 输出 maxVal 和 avg
|
||
```
|
||
|
||
### 真实代码
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
int arr[n];
|
||
|
||
// 读入数组
|
||
for (int i = 0; i < n; i++) {
|
||
cin >> arr[i];
|
||
}
|
||
|
||
// 打擂台求最大值
|
||
int maxVal = arr[0];
|
||
for (int i = 1; i < n; i++) {
|
||
if (arr[i] > maxVal) {
|
||
maxVal = arr[i];
|
||
}
|
||
}
|
||
|
||
// 累加求和
|
||
int sum = 0;
|
||
for (int i = 0; i < n; i++) {
|
||
sum += arr[i];
|
||
}
|
||
double avg = (double)sum / n; // 强转，保留小数
|
||
|
||
cout << "最大值：" << maxVal << endl;
|
||
cout << "平均值：" << avg << endl;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
### 注意点
|
||
1. **下标从 0 开始**：`arr[0]` 是第一个元素，`arr[n-1]` 是最后一个。这是新手最容易犯的错。
|
||
2. **打擂台循环从 1 开始**：`for (i = 1; i < n; i++)`，因为 `arr[0]` 已经是擂主了，不用跟自己比。
|
||
3. **整数除法陷阱**：`sum / n` 两个 int 相除会丢掉小数，必须把其中一个转成 `double`。
|
||
4. **数组大小**：`int arr[n]` 在部分老编译器（如 VC6）上不支持变长数组，可以用 `int arr[1000]` 设一个大一点的固定值。
|
||
|
||
---
|
||
|
||
## 题目二：查找元素 — 找目标值
|
||
|
||
### 核心代码（一句话）
|
||
> 查找的核心：**遍历 + 比较 + break**，找到了就记录位置并退出，用一个 -1 表示"没找到"。
|
||
|
||
### 自然语言思路
|
||
在一个数组里找某个数，就像在一排抽屉里找东西。
|
||
|
||
第一步，设一个标记 `index = -1`，表示"还没找到"（-1 不可能是合法下标，所以用它当哨兵）。
|
||
第二步，从第一个到最后一个，逐个打开抽屉 `arr[i]`，跟目标值比。
|
||
第三步，一旦找到，记录下标 `index = i`，立刻 `break` 退出循环，不浪费时间。
|
||
第四步，循环结束后，如果 `index` 还是 -1 就是没找到，否则输出下标。
|
||
|
||
> 也叫"顺序查找"或"线性查找"，像沿着一条线逐个摸过去。
|
||
|
||
### 伪代码
|
||
```
|
||
1. 输入 n, 数组 arr, target
|
||
2. index = -1 // 哨兵：默认没找到
|
||
3. for i = 0 到 n-1：
|
||
4. if arr[i] == target：
|
||
5. index = i
|
||
6. break // 找到就停
|
||
7. if index != -1：
|
||
8. 输出 "找到，下标：" + index
|
||
9. else：
|
||
10. 输出 "未找到"
|
||
```
|
||
|
||
### 真实代码
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n, target;
|
||
cin >> n;
|
||
int arr[n];
|
||
for (int i = 0; i < n; i++) {
|
||
cin >> arr[i];
|
||
}
|
||
cin >> target;
|
||
|
||
int index = -1; // 哨兵
|
||
for (int i = 0; i < n; i++) {
|
||
if (arr[i] == target) {
|
||
index = i;
|
||
break; // 找到就停
|
||
}
|
||
}
|
||
|
||
if (index != -1) {
|
||
cout << "找到，下标为：" << index << endl;
|
||
} else {
|
||
cout << "未找到" << endl;
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
### 注意点
|
||
1. **哨兵值选 -1**：因为数组下标从 0 开始，-1 永远不可能是合法下标，所以用它表示"没找到"很安全。
|
||
2. **break 的作用**：找到后立刻停止，不需要继续往后找了。如果忘了加 `break`，会找到最后一次出现的位置。
|
||
3. **如果找第一个出现的位置**：加 `break`；**如果找最后一次出现的位置**：不加 `break`，让循环跑完。
|
||
|
||
---
|
||
|
||
## 题目三：数组逆序与冒泡排序
|
||
|
||
### 核心代码（一句话）
|
||
> 逆序的核心：**首尾交换，只换一半**；冒泡排序的核心：**相邻两两比较，大的往后冒**，每轮确定一个最大值的位置。
|
||
|
||
### 自然语言思路
|
||
|
||
**数组逆序**：
|
||
第一步，想象把数组对折：第 0 个和第 n-1 个交换，第 1 个和第 n-2 个交换……
|
||
第二步，循环只需要跑 `n / 2` 次，因为每次交换两个元素。
|
||
第三步，交换用三行代码（中间变量法）：`temp = a; a = b; b = temp;`。
|
||
|
||
**冒泡排序**：
|
||
第一步，外层循环决定"第几轮"，一共需要 n-1 轮。
|
||
第二步，每轮从数组开头开始，相邻两个比大小：如果前面的 > 后面的，就交换。
|
||
第三步，每轮结束，最大的那个数就"冒"到了最后面。所以下一轮可以少比一个（`j < n-1-i`）。
|
||
第四步，n-1 轮过后，数组从小到大排好了。
|
||
|
||
### 伪代码
|
||
|
||
**数组逆序**：
|
||
```
|
||
1. for i = 0 到 n/2 - 1：
|
||
2. temp = arr[i]
|
||
3. arr[i] = arr[n-1-i]
|
||
4. arr[n-1-i] = temp
|
||
```
|
||
|
||
**冒泡排序**：
|
||
```
|
||
1. for i = 0 到 n-2： // 外层：第 i 轮
|
||
2. for j = 0 到 n-2-i： // 内层：相邻比较
|
||
3. if arr[j] > arr[j+1]： // 前面大就交换
|
||
4. temp = arr[j]
|
||
5. arr[j] = arr[j+1]
|
||
6. arr[j+1] = temp
|
||
```
|
||
|
||
### 真实代码
|
||
|
||
**数组逆序**：
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
int arr[n];
|
||
for (int i = 0; i < n; i++) {
|
||
cin >> arr[i];
|
||
}
|
||
|
||
// 首尾交换，只换一半
|
||
for (int i = 0; i < n / 2; i++) {
|
||
int temp = arr[i];
|
||
arr[i] = arr[n - 1 - i];
|
||
arr[n - 1 - i] = temp;
|
||
}
|
||
|
||
for (int i = 0; i < n; i++) {
|
||
cout << arr[i] << " ";
|
||
}
|
||
cout << endl;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
**冒泡排序**：
|
||
```cpp
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int n;
|
||
cin >> n;
|
||
int arr[n];
|
||
for (int i = 0; i < n; i++) {
|
||
cin >> arr[i];
|
||
}
|
||
|
||
// 冒泡排序
|
||
for (int i = 0; i < n - 1; i++) { // 外层：n-1 轮
|
||
for (int j = 0; j < n - 1 - i; j++) { // 内层：每轮少比一个
|
||
if (arr[j] > arr[j + 1]) { // 前面大则交换
|
||
int temp = arr[j];
|
||
arr[j] = arr[j + 1];
|
||
arr[j + 1] = temp;
|
||
}
|
||
}
|
||
}
|
||
|
||
for (int i = 0; i < n; i++) {
|
||
cout << arr[i] << " ";
|
||
}
|
||
cout << endl;
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
### 注意点
|
||
1. **逆序循环次数**：`n / 2`，不是 `n`。如果是奇数个元素，中间那个不用换。例如 n=5，只需换 2 次（下标 0↔4，1↔3）。
|
||
2. **冒泡内层循环上界**：`n - 1 - i`，不是 `n - 1`。每轮少比一个是因为最后面已经排好了。
|
||
3. **冒泡时间复杂度**：n 个数大概要比 n² / 2 次，数据量大时较慢。学完 sort 后可以直接用 `sort` 替代冒泡。
|
||
4. **交换三行口诀**：`temp = 前; 前 = 后; 后 = temp;` —— 中间变量暂存，避免覆盖丢失。
|
||
|
||
---
|
||
|
||
## 本课打油诗
|
||
|
||
> 数组元素排排坐，下标从零开始摸。
|
||
> 遍历循环 for 一把，一个不落全看过。
|
||
> 擂台之上比高矮，先请一位站中央。
|
||
> 首尾交换逆序成，冒泡大的往后挪。
|
||
|
||
---
|
||
|
||
## 课后作业
|
||
1. 输入 n 个数，求第二大值（注意可能有重复最大值）
|
||
2. 输入 n 个数，将它们逆序存储后输出（不能用第二个数组）
|
||
3. 输入 n 个数，统计其中不同数字的个数
|
||
4. 输入 n 个数，使用冒泡排序从小到大排序后输出
|