章节回顾
又完成了一章！只剩下这个小测需要攻克……
函数实参可通过值传递、引用传递或地址传递三种方式传递。
- 对基本数据类型和枚举使用值传递。
- 对结构体、类，或需要函数修改实参时使用引用传递。
- 传递指针或内置数组时使用地址传递。
- 尽可能将引用或地址形参声明为
const。
函数返回值可通过值返回、引用返回或地址返回。
- 多数情况下使用值返回即可。
- 处理动态分配的数据、结构体或类时，可考虑引用返回或地址返回。
- 若采用引用或地址返回，务必确保返回对象不会在离开作用域后失效。
函数指针允许我们将一个函数作为实参传递给另一函数，常用于让调用者自定义函数行为，如排序方式。
动态内存在堆（heap）上分配。
调用栈（call stack）记录从程序开始到当前执行点所有尚未结束的活动函数。局部变量在栈上分配；栈容量有限。可用
std::vector实现类似栈的行为。递归函数指调用自身的函数，所有递归函数都必须具备终止条件。
命令行参数允许用户或其他程序在程序启动时向其传递数据。命令行参数始终是 C 风格字符串，如需数值需手动转换。
**可变参数（…）**允许向函数传递数量不定的实参，但会禁用类型检查，且无法自动得知实参个数，程序需自行维护这些信息。
Lambda 函数是可嵌套于其他函数内的匿名函数，无需命名，与算法库配合尤为便利。
小测
问题 1
为下列情况编写函数原型，必要时使用 const。
a) 函数名为 max，接收两个 double 参数，返回二者中较大值。
double max(double a, double b);
b) 函数名为 swap，交换两个 int 的值。
void swap(int& a, int& b);
c) 函数名为 getLargestElement，接收一个动态分配的 int 数组（含长度参数），返回该数组中最大元素的引用，以便调用者可修改返回的元素。
int& getLargestElement(int* array, int length);
问题 2
指出下列程序的问题所在。
a)
int& doSomething()
{
int array[]{ 1, 2, 3, 4, 5 };
return array[3];
}
答案： 返回局部数组元素的引用；函数结束时数组被销毁，引用将悬垂。
b)
int sumTo(int value)
{
return value + sumTo(value - 1);
}
答案： 缺少终止条件，导致无限递归和栈溢出。
c)
float divide(float x, float y)
{
return x / y;
}
double divide(float x, float y)
{
return x / y;
}
答案： 仅返回值类型不同无法构成重载，导致编译错误。
d)
#include <iostream>
int main()
{
int array[100000000]{};
for (auto x: array)
std::cout << x << ' ';
std::cout << '\n';
return 0;
}
答案：
在栈上分配巨大数组，易导致栈溢出；应使用 std::vector 或动态分配。
e)
#include <iostream>
int main(int argc, char* argv[])
{
int age{ argv[1] };
std::cout << "The user's age is " << age << '\n';
return 0;
}
答案：
argv[1] 是 C 风格字符串，需使用 std::stoi 等函数转换为 int 再赋值。
问题 3
背景：在有序数组中判断某值是否存在的最佳算法是二分查找。
算法流程：
- 取数组中间元素（偶数个时下取整）。
- 若中间元素大于目标值，则舍弃上半部分（或对下半部分递归）。
- 若中间元素小于目标值，则舍弃下半部分（或对上半部分递归）。
- 若中间元素等于目标值，返回其索引。
- 若数组被全部舍弃仍未找到，返回哨兵值 −1。
由于每次迭代可舍弃一半元素，算法极快；即使百万级数组，最多 20 次迭代即可完成。但前提是数组必须有序。
示例数组 { 3, 6, 8, 12, 14, 17, 20, 21, 26, 32, 36, 37, 42, 44, 48 }，目标值 7 的三步检索过程见原文。
在 C++20 中，可用
std::midpoint计算中点；C++20 之前请自行计算，推荐使用min + ((max - min) / 2)以避免溢出。
给定代码框架：
#include <iostream>
#include <iterator>
int binarySearch(const int* array, int target, int min, int max)
{
// 待实现
}
int main()
{
constexpr int array[]{ 3, 6, 8, 12, 14, 17, 20, 21, 26, 32, 36, 37, 42, 44, 48 };
constexpr int testValues[]{ 0, 3, 12, 13, 22, 26, 43, 44, 48, 49 };
int expectedResult[]{ -1, 0, 3, -1, -1, 8, -1, 13, 14, -1 };
static_assert(std::size(testValues) == std::size(expectedResult));
for (std::size_t count{ 0 }; count < std::size(testValues); ++count)
{
int index{ binarySearch(array, testValues[count], 0,
static_cast<int>(std::size(array)) - 1) };
if (index == expectedResult[count])
std::cout << "test value " << testValues[count] << " passed!\n";
else
std::cout << "test value " << testValues[count]
<< " failed. There's something wrong with your code!\n";
}
return 0;
}
a) 请编写迭代版本的 binarySearch 函数。
int binarySearch(const int* array, int target, int min, int max)
{
while (min <= max)
{
int mid{ min + (max - min) / 2 }; // 防溢出
if (array[mid] > target)
max = mid - 1;
else if (array[mid] < target)
min = mid + 1;
else
return mid;
}
return -1;
}
b) 请编写递归版本的 binarySearch 函数。
int binarySearch(const int* array, int target, int min, int max)
{
if (min > max)
return -1;
int mid{ min + (max - min) / 2 };
if (array[mid] > target)
return binarySearch(array, target, min, mid - 1);
else if (array[mid] < target)
return binarySearch(array, target, mid + 1, max);
else
return mid;
}
提示
std::binary_search返回有序列表中是否存在某值。std::equal_range返回与给定值相等的首尾迭代器。 请勿使用这两个函数完成本测验，但未来若需二分查找，可直接使用。
