C++ 数组算法
数组是C++中最基础的数据结构之一，而数组算法则是处理数组数据的基本方法。掌握这些算法不仅对编程新手至关重要，还为学习更复杂的数据结构和算法打下坚实基础。
什么是数组算法？
数组算法是对数组元素进行操作的一系列方法，包括但不限于：
- 数组元素的访问与遍历
- 数组元素的查找
- 数组的排序
- 数组的统计操作（如求和、求平均值）
- 数组元素的插入与删除
数组遍历算法
遍历是最基础的数组操作，它是许多其他算法的基础。
基本遍历
cpp
#include <iostream>
using namespace std;
int main() {
int arr[5] = {10, 20, 30, 40, 50};
// 使用for循环遍历
cout << "数组元素：";
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
输出：
数组元素：10 20 30 40 50
使用范围for循环（C++11特性）
cpp
#include <iostream>
using namespace std;
int main() {
int arr[5] = {10, 20, 30, 40, 50};
// 使用范围for循环遍历
cout << "数组元素：";
for (int x : arr) {
cout << x << " ";
}
cout << endl;
return 0;
}
输出：
数组元素：10 20 30 40 50
提示
范围for循环是C++11引入的特性，它使得数组和容器的遍历更加简洁和易读。
数组查找算法
线性查找
线性查找（Linear Search）是最简单的查找算法，适用于任何数组。
cpp
#include <iostream>
using namespace std;
int linearSearch(int arr[], int size, int key) {
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
return i; // 返回找到元素的索引
}
}
return -1; // 没有找到目标元素
}
int main() {
int arr[5] = {10, 20, 30, 40, 50};
int key = 30;
int result = linearSearch(arr, 5, key);
if (result != -1) {
cout << "元素 " << key << " 在数组中的索引位置为: " << result << endl;
} else {
cout << "元素 " << key << " 不存在于数组中" << endl;
}
return 0;
}
输出：
元素 30 在数组中的索引位置为: 2
二分查找
二分查找（Binary Search）是一种高效的查找算法，但要求数组必须已经排序。
cpp
#include <iostream>
using namespace std;
int binarySearch(int arr[], int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2;
// 如果找到了元素
if (arr[mid] == key) {
return mid;
}
// 如果元素比中间值大，搜索右半部分
if (arr[mid] < key) {
low = mid + 1;
}
// 否则，搜索左半部分
else {
high = mid - 1;
}
}
// 如果没找到元素
return -1;
}
int main() {
int arr[5] = {10, 20, 30, 40, 50}; // 已排序数组
int key = 40;
int result = binarySearch(arr, 0, 4, key);
if (result != -1) {
cout << "元素 " << key << " 在数组中的索引位置为: " << result << endl;
} else {
cout << "元素 " << key << " 不存在于数组中" << endl;
}
return 0;
}
输出：
元素 40 在数组中的索引位置为: 3
警告
二分查找要求数组已经排序，否则结果将不准确！
数组排序算法
冒泡排序
冒泡排序是最简单的排序算法之一，它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们。
cpp
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
// 每轮冒泡后，最大的元素会"浮"到最右边
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// 交换相邻元素
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main() {
int arr[5] = {64, 34, 25, 12, 22};
cout << "排序前的数组: ";
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
bubbleSort(arr, 5);
cout << "\n排序后的数组: ";
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
return 0;
}
输出：
排序前的数组: 64 34 25 12 22
排序后的数组: 12 22 25 34 64
选择排序
选择排序是一种简单直观的排序算法，它每次从待排序的数据中选出最小（或最大）的元素，放在已排序序列的末尾。
cpp
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
// 找出从i到n-1位置中值最小的元素
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 将找到的最小元素与当前位置交换
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[5] = {64, 34, 25, 12, 22};
cout << "排序前的数组: ";
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
selectionSort(arr, 5);
cout << "\n排序后的数组: ";
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
return 0;
}
输出：
排序前的数组: 64 34 25 12 22
排序后的数组: 12 22 25 34 64
使用C++标准库算法
C++标准库提供了许多常用的算法，包括排序，它们通常比我们自己编写的算法更加高效。
cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[5] = {64, 34, 25, 12, 22};
cout << "排序前的数组: ";
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
// 使用标准库的sort函数
sort(arr, arr + 5);
cout << "\n排序后的数组: ";
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
return 0;
}
输出：
排序前的数组: 64 34 25 12 22
排序后的数组: 12 22 25 34 64
数组统计算法
计算数组元素之和
cpp
#include <iostream>
using namespace std;
int sumArray(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
return sum;
}
int main() {
int arr[5] = {10, 20, 30, 40, 50};
int sum = sumArray(arr, 5);
cout << "数组元素之和: " << sum << endl;
return 0;
}
输出：
数组元素之和: 150
找出数组中的最大值和最小值
cpp
#include <iostream>
using namespace std;
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
int findMin(int arr[], int n) {
int min = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
int main() {
int arr[5] = {64, 34, 25, 12, 22};
cout << "数组中的最大值: " << findMax(arr, 5) << endl;
cout << "数组中的最小值: " << findMin(arr, 5) << endl;
return 0;
}
输出：
数组中的最大值: 64
数组中的最小值: 12
使用C++标准库进行统计
cpp
#include <iostream>
#include <algorithm>
#include <numeric> // 用于accumulate
using namespace std;
int main() {
int arr[5] = {64, 34, 25, 12, 22};
// 使用标准库计算总和
int sum = accumulate(arr, arr + 5, 0);
// 使用标准库找最大值和最小值
int max_val = *max_element(arr, arr + 5);
int min_val = *min_element(arr, arr + 5);
cout << "数组元素之和: " << sum << endl;
cout << "数组中的最大值: " << max_val << endl;
cout << "数组中的最小值: " << min_val << endl;
return 0;
}
输出：
数组元素之和: 157
数组中的最大值: 64
数组中的最小值: 12
实际应用场景
学生成绩管理系统
以下是一个简单的学生成绩管理系统示例，它使用数组存储学生成绩，并实现了基本的统计分析功能：
cpp
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
const int STUDENT_COUNT = 5;
double scores[STUDENT_COUNT];
// 输入学生成绩
cout << "请输入" << STUDENT_COUNT << "个学生的成绩：" << endl;
for (int i = 0; i < STUDENT_COUNT; i++) {
cout << "学生 " << (i + 1) << " 的成绩: ";
cin >> scores[i];
}
// 计算平均分
double sum = accumulate(scores, scores + STUDENT_COUNT, 0.0);
double average = sum / STUDENT_COUNT;
// 找出最高分和最低分
double highest = *max_element(scores, scores + STUDENT_COUNT);
double lowest = *min_element(scores, scores + STUDENT_COUNT);
// 对成绩排序
sort(scores, scores + STUDENT_COUNT);
// 输出统计结果
cout << "\n成绩统计：" << endl;
cout << "平均分: " << average << endl;
cout << "最高分: " << highest << endl;
cout << "最低分: " << lowest << endl;
cout << "\n排序后的成绩（从低到高）: ";
for (int i = 0; i < STUDENT_COUNT; i++) {
cout << scores[i] << " ";
}
cout << endl;
return 0;
}
输入示例：
请输入5个学生的成绩：
学生 1 的成绩: 85
学生 2 的成绩: 92
学生 3 的成绩: 78
学生 4 的成绩: 95
学生 5 的成绩: 88
输出示例：
成绩统计：
平均分: 87.6
最高分: 95
最低分: 78
排序后的成绩（从低到高）: 78 85 88 92 95
简单的库存管理系统
cpp
#include <iostream>
#include <string>
using namespace std;
struct Product {
string name;
int quantity;
double price;
};
int main() {
const int MAX_PRODUCTS = 5;
Product inventory[MAX_PRODUCTS] = {
{"笔记本电脑", 10, 5999.99},
{"手机", 20, 2999.99},
{"耳机", 30, 299.99},
{"平板电脑", 15, 3999.99},
{"鼠标", 50, 99.99}
};
double totalValue = 0;
int lowStockCount = 0;
// 计算库存总价值和低库存产品数量
for (int i = 0; i < MAX_PRODUCTS; i++) {
totalValue += inventory[i].quantity * inventory[i].price;
if (inventory[i].quantity < 20) {
lowStockCount++;
}
}
// 显示库存信息
cout << "库存清单：" << endl;
cout << "--------------------------------------------------" << endl;
cout << "产品名称\t\t数量\t单价\t\t总价" << endl;
cout << "--------------------------------------------------" << endl;
for (int i = 0; i < MAX_PRODUCTS; i++) {
cout << inventory[i].name << "\t\t"
<< inventory[i].quantity << "\t"
<< inventory[i].price << "\t"
<< inventory[i].quantity * inventory[i].price << endl;
}
cout << "--------------------------------------------------" << endl;
cout << "库存总价值: " << totalValue << endl;
cout << "低库存产品数量 (少于20): " << lowStockCount << endl;
return 0;
}
输出：
库存清单：
--------------------------------------------------
产品名称 数量 单价 总价
--------------------------------------------------
笔记本电脑 10 5999.99 59999.9
手机 20 2999.99 59999.8
耳机 30 299.99 8999.7
平板电脑 15 3999.99 59999.9
鼠标 50 99.99 4999.5
--------------------------------------------------
库存总价值: 193999
低库存产品数量 (少于20): 2
总结
本文详细介绍了C++中常用的数组算法，包括：
- 遍历算法：使用for循环和范围for循环
- 查找算法：线性查找和二分查找
- 排序算法：冒泡排序和选择排序以及使用标准库函数
- 统计算法：求和、求最值
- 实际应用：展示了学生成绩管理和库存管理两个实际应用场景
通过学习这些基础的数组算法，你将能够更有效地处理各种数据问题。这些算法不仅在程序设计中非常实用，而且也是更高级算法和数据结构的基础。
练习题
为了巩固所学知识，请尝试完成以下练习：
- 编写一个函数，找出数组中出现频率最高的元素。
- 实现插入排序算法，并与冒泡排序和选择排序比较效率。
- 编写一个程序，判断一个数组是否为另一个数组的子集。
- 实现一个简单的图书管理系统，使用数组存储图书信息，并提供搜索、排序功能。
- 编写一个函数，将两个已排序的数组合并成一个新的已排序数组。
参考资源
- 《C++ Primer》第五版，由Stanley B. Lippman著
- 《数据结构与算法分析：C++描述》，由Mark Allen Weiss著
- cppreference.com - C++官方参考文档
- GeeksforGeeks - Array Algorithms
掌握这些数组算法将为你的编程之旅提供坚实的基础，祝学习顺利！