C++学习笔记（六：数组）

往篇内容：

 C++学习笔记（一）
        一、C++编译阶段※

        二、入门案例解析 

        三、命名空间详解

        四、C++程序结构

C++学习笔记（二）

        五、函数基础

        六、标识符

        七、数据类型

        补充：二进制相关的概念

                  sizeof 运算符简介

        补充：原码、反码和补码

C++学习笔记（三）

        补充：ASCII码表

        八、内存构成

         补充：变量

        九、指针基础 

        十、const关键字

        十一、枚举类型 

C++学习笔记（四）

        十二、 类型转换

        十三、define指令 

        十四、typedef关键字

        十五、运算符

        十六、 流程控制

目录

十七、数组 

1、数组的概述

2、数组初始化

3、数组名传参

4、数组使用案例

①数组反转

②二分查找 

③冒泡排序

④插入排序

⑤选择排序

⑥希尔排序

5、二维数组

①定义格式

②元素访问

③内存结构​编辑

 ④二位数组的初始化

 ⑤二维数组的遍历

⑥案例：使用二维数组创建杨辉三角并输出

 6、字符数组

①基本概念 

②定义初始化

③数组输入

 ④处理函数

⑤常见问题

⑥使用二维数组存储多个字符串

7、总结

8、字符串类 

十七、数组 

1、数组的概述

表示一块连续的内存空间，可以用来从存储多个数据元素，要求类型一致。

定义： 数据类型 数据名[常量表达式]

数组下标区间：  [0,数组长度-1]

数组越界：

        在 C++ 中，数组越界是一个常见但非常危险的错误，可能导致程序崩溃、数据损坏甚至安全漏洞。

典型场景：

int arr[5];
// 错误：i 最大到 5，越界访问 arr[5]
for (int i = 0; i <= 5; ++i)
{
arr[i] = i;
}

数组越界的后果

1. 未定义行为（Undefined Behavior）

        C++ 标准不定义数组越界行为，程序可能表现异常，但不会立刻崩溃

2. 内存损坏

        越界写入会覆盖相邻内存区域的数据，导致变量值被篡改或程序逻辑错误

3. 程序崩溃

        如果越界访问触发操作系统的内存保护机制（如访问受保护的地址），程 序会崩溃（如 segmentation fault）。

4. 安全漏洞

        缓冲区溢出攻击（Buffer Overflow）利用数组越界漏洞执行恶意代码。

例如：通过精心构造输入覆盖函数返回地址，劫持程序执行流程。

5. 难以定位的错误

        越界错误可能在程序运行后期才暴露，导致调试困难。

示例：某次越界写入覆盖了关键变量，后续逻辑错误才导致崩溃。

2、数组初始化

3、数组名传参

#include<iostream>
using namespace std;void outArray(int arr[], int len) {for(int i=0; i<len; i++) {cout << arr[i] << " ";}cout << endl;
}int main() {int array[8];for(int i=0; i<8; i++)array[i] = i;int len = sizeof(array)/sizeof(int);outArray(array, len);return 0;
}

①数组反转

#include <iostream>
#include "fanzhuan.h"using namespace std;// 反转数组
void reverseArray(int arr[], int len) {for (int i = 0; i < len / 2; i++) {// 交换arr[i]和arr[len-1-i]的值arr[i] = arr[i] ^ arr[len - i - 1];arr[len - i - 1] = arr[i] ^ arr[len - 1 - i];arr[i] = arr[i] ^ arr[len - 1 - i];}
}// 遍历数组
void outArray(int arr[], int len) {for (int i = 0; i < len; i++) {cout << arr[i] << " ";}cout << endl;
}int main() {// 准备数组int arr[10];int num = 0;for (int i = 0; i < 10; i++) {arr[i] = num;num += 2;}int len = sizeof(arr) / sizeof(int);outArray(arr, len);reverseArray(arr, len);outArray(arr, len);return 0;
}

②二分查找 

二分查找的核心思想

        在一个有序序列中查找某个元素，将n个元素分成个数大致相同的两半，取a[n/2]与欲查 找的x作比较，如果x=a[n/2]则找到x，算法终止；如果x<a[n/2]，则我们只要在 数组a的左半部继续搜索x；如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

分治策略

        将搜索区间分为两部分，通过比较目标值与中间元素的大小关系，确定目标值可能存在的区间。每次比较后，搜索区间减半。

时间复杂度

        二分查找的时间复杂度为 O(log n)，远优于线性查找的 O(n)。这是因为每次迭代都将问题规模减半。

关键条件

• 数据必须有序：二分查找依赖数据的顺序性，否则无法保证正确性。
• 随机访问：需要支持通过索引直接访问元素（如数组），链表等结构不适用。

实现步骤

1. 初始化左右边界（通常为 left = 0，right = n-1）。
2. 计算中间索引 mid = left + (right - left) / 2（避免整数溢出）。
3. 比较目标值与 arr[mid]：
   • 若相等，返回 mid。
   • 若目标值较小，调整右边界 right = mid - 1。
   • 若目标值较大，调整左边界 left = mid + 1。
4. 重复步骤 2-3 直至找到目标或区间无效（left > right）。

#include <iostream>using namespace std;int binarySearch(int arr[], int len, int value)
{int start = 0;int end = len - 1;int mid;while (true){mid = (start + end) / 2;if (value == arr[mid]){return mid;}else if (value > arr[mid]){start = mid + 1;}else{end = mid - 1;}//当start > end 循环结束if (start > end)break;}return -1;
}int main()
{int arr[] = {1, 3, 4, 5, 7, 9, 10};int len = sizeof(arr) / sizeof(int);int index = binarySearch(arr, len, 1);cout << "1: " << index << endl;index = binarySearch(arr, len, 2);cout << "2: " << index << endl;index = binarySearch(arr, len, 10);cout << "10: " << index << endl;return 0;
}

③冒泡排序

#include <iostream>
using namespace std;void outArray(int arr[], int len) {for(int i = 0; i < len; i++) {cout << arr[i] << " ";}cout << endl;
}//冒泡排序
void bubbleSort(int arr[], int len) {//每次排序，可以将 未排序序列中 最大值 放到最后位置//len个成员，一共排序len-1次即可for(int i = 0; i < len-1; i++) {//每次排序，借助交换 相邻两个数，实现 最大值移动到最后位置for(int j = 0; j < len-1-i; j++) {if(arr[j] > arr[j+1]) {arr[j] = arr[j] ^ arr[j+1];arr[j+1] = arr[j] ^ arr[j+1];arr[j] = arr[j] ^ arr[j+1];}}cout << "第" << (i+1) << "次排序后: ";outArray(arr,len);}
}int main() {int array[] = {4,5,3,2,1};int size = sizeof(array) / sizeof(int);//排序bubbleSort(array,size);cout << "排序完成后: " << endl;//遍历outArray(array,size);return 0;
}

#include <iostream>
using namespace std;// 遍历数组 函数声明
void printArray(int arr[], int len);
// 插入排序 函数声明
void insertSort(int arr[], int len);int main() {// 准备一个int数组int array[] = {5, 2, 6, 9, 0, 3};int len = sizeof(array) / sizeof(int);cout << "排序前: ";printArray(array, len);// 插入排序insertSort(array, len);// 输出排序结果cout << "排序后: ";printArray(array, len);return 0;
}void insertSort(int arr[], int len) {if (len <= 1) {return;}// 外层循环控制 总体循环次数for (int i = 1; i < len; i++) {// 内层循环做的事情：将无序列表中第一个元素插入到有序列表中合适位置int value = arr[i];// 获取有序列表中最后一个元素下标int j = i - 1;for (; j >= 0; j--) {if (value < arr[j]) {arr[j + 1] = arr[j];} else {break;}}// 将需要插入的元素 放置到合适位置arr[j + 1] = value;// 一次排序完成后，输出 方便 观察cout << "第 " << i << "次排序: ";printArray(arr, len);}
}void printArray(int arr[], int len) {for (int i = 0; i < len; i++) {cout << arr[i] << " ";}cout << endl;
}

⑤选择排序

#include <iostream>
using namespace std;// 遍历数组 函数声明
void printArray(int arr[], int len);// 选择排序 函数声明
void selectSort(int arr[], int len);int main()
{// 准备一个int数组int array[] = {5, 2, 6, 9, 0, 3};int len = sizeof(array) / sizeof(int);cout << "排序前: ";printArray(array, len);// 选择排序selectSort(array, len);// 输出排序结果cout << "排序后: ";printArray(array, len);return 0;
}void selectSort(int arr[], int len)
{if (len <= 1)return;// 外层循环控制总体排序次数for (int i = 0; i < len - 1; i++){int minIndex = i;// 内层循环找到当前无序列表中最小下标for (int j = i + 1; j < len; j++){if (arr[minIndex] > arr[j]){minIndex = j;}}// 将无序列表中最小值添加到有序列表最后位置if (minIndex != i){arr[minIndex] = arr[minIndex] ^ arr[i];arr[i] = arr[minIndex] ^ arr[i];arr[minIndex] = arr[minIndex] ^ arr[i];}cout << "第 " << i << " 次排序: ";printArray(arr, len);}
}void printArray(int arr[], int len)
{for (int i = 0; i < len; i++){cout << arr[i] << " ";}cout << endl;
}

⑥希尔排序

#include <iostream>
using namespace std;// 遍历数组 函数声明
void printArray(int arr[], int len);// 希尔排序 函数声明
void shellSort(int arr[], int len);int main()
{// 准备一个int数组int array[] = {5, 2, 6, 9, 0, 3};int len = sizeof(array) / sizeof(int);cout << "排序前: ";printArray(array, len);// shell排序shellSort(array, len);// 输出排序结果cout << "排序后: ";printArray(array, len);return 0;
}void shellSort(int arr[], int len)
{if (len <= 1)return;// 设置初始增量int gap = len / 2;// 定义排序次数int count = 0;// 由增量控制整体排序次数while (gap > 0){// 插入排序改造for (int i = gap; i < len; i++){// 记录要插入的值int value = arr[i];// 有序序列的最后一个元素下标int j = i - gap;for (; j >= 0; j -= gap){if (value < arr[j]) {arr[j + gap] = arr[j];} else {break;}}arr[j + gap] = value;}count++;cout << "第 " << count << " 次排序: ";printArray(arr, len);gap = gap / 2;}
}void printArray(int arr[], int len)
{for (int i = 0; i < len; i++){cout << arr[i] << " ";}cout << endl;
}

5、二维数组

①定义格式

1)数据类型 数组名[一维长度m][二维长度n];

2)数据类型 数组名 [] [二维长度n];

可以省略一维长度

②元素访问

③内存结构

这个 SVG 图像展示了二维数组在内存中的存储方式：

• 左侧为逻辑上的 3 行 4 列矩阵结构
• 右侧为实际在内存中的线性存储方式（行优先存储）
• 每个内存单元标注了对应的数组元素和假设的内存地址（假设每个元素占 4 字节）
• 红色虚线表示逻辑结构到内存布局的映射关系

二维数组在内存中是连续存储的，通过行优先的方式将多维结构映射到一维内存空间。

 ④二位数组的初始化

• 行数 = sizeof(arr) / sizeof(arr[0])

• 列数 = sizeof(arr[0]) / sizeof(arr[0][0])

 ⑤二维数组的遍历

#include <iostream>
using namespace std;// 函数声明
void printArray(int arr[][4], int rows);
// ok
//void printArray(int arr[3][4], int rows);
// error
//void printArray(int arr[][], int rows, int cols);int main()
{// 定义一个 3 行 4 列的二维数组int matrix[3][4] = {{1, 4},{8},{9, 10, 12}};// 调用函数打印数组printArray(matrix, 3);return 0;
}// 函数定义：打印二维数组
void printArray(int arr[][4], int rows)
{for (int i = 0; i < rows; ++i){for (int j = 0; j < 4; ++j){cout << arr[i][j] << " ";}cout << endl;}
}

注意：如果用二维数组名作为函数形参，则声明二维数组作为参数时，必须指定第二维的大小，且应与实参的第二维的大小相同。第一维的大小可以指定，也可以不指定。

⑥案例：使用二维数组创建杨辉三角并输出

#include <iostream>
using namespace std;int main()
{int arr[5][5] = {0};// 根据规律，构造出二维数组并且赋值for (int i = 0; i < 5; i++){// 循环给二维数组中的每个位置赋值for (int j = 0; j < 5; j++){if (j == 0 || j == i){arr[i][j] = 1;}else if (i > j){// 除了下标中的0和最后一个，其他的元素都具备相同的规律// 这个位置的值=上一层和它相同下标的值+前一个元素的值arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];}}}// 把赋值完成的二维数组按要求进行输出for (int i = 0; i < 5; i++){// 1.控制每行开始输出的空格for (int j = 0; j < (5 - i - 1); j++){cout << " ";}// 2.控制输出二维数组中的值，记得值和值之间有空格隔开for (int k = 0; k <= i; k++){cout << arr[i][k] << " ";}// 当前行输出完，再单独输出一个换行cout << endl;}return 0;
}

 6、字符数组

①基本概念 

 示例：

//数组 `str` 存储了字符串 `"Hello"`，最后一个元素 `\0` 是隐式添加的终止符。

char str[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

②定义初始化

• 常量表达式 ：数组的长度
• 示例： char name[20]; 定义一个可存储 19 个字符的数组（最后一个字符为 \0 ）

• 明确指定每个字符，包括终止符 \0 。

• 等价于 char name[5] = {'J', 'o', 'h', 'n', '\0'};
• 如果未指定大小，编译器会根据字符串长度自动分配空间

③数组输入

• 读取字符直到遇到空格、换行符或制表符
• 不会自动添加 \0 （实际会添加，但可能导致缓冲区残留问题）
• 不推荐用于需要处理空格或换行的场景

 ④处理函数

示例：

#include <iostream>
#include <cstring>
using namespace std;
int main() {char str1[20] = "Hello";char str2[] = "World";strcpy(str1, str2); // str1 = "World"cout << "str1: " << str1 << endl;cout << "Length: " << strlen(str1) << endl; // 输出 5cout << "Compare: " << strcmp(str1, str2) << endl; // 输出 0strcat(str1, "!"); // str1 = "World!"cout << str1 << endl;return 0;
}

⑤常见问题

• 若未手动添加 \0 ，字符串函数（如 strlen 、 strcpy ）会继续读取内存，导致未定义行为。
• 正确做法

• 若输入字符串长度超过数组容量，会导致数据溢出，破坏内存
• 解决方法

• 字符数组：固定大小的数组，存储字符序列
• 字符串：动态对象（如 std::string ），可自动调整大小
• 建议：现代 C++ 推荐使用 std::string 替代字符数组，避免手动管理内存

⑥使用二维数组存储多个字符串

 遍历二维字符数组

8、字符串类 

•         用字符数组来存放字符串并不是最理想和最安全的方法，C++提供了一种新的数据类型：字符串类型 string ，在使用方法上，它和 char、int 类型一样，可以用来定义变量，例如： string str;
•          实际上， string 并不是 C++语言本身具有的基本类型，它是在 C++标准库中声明的一个字符串类，用这种类可以定义对象，每一个字符串变量都是string 类的一个对象。

string str = "Then";

str[2] = 'a';

//结果为：Than

cout << "str: " << str << endl;