专栏：算法
上一篇：
下一篇：
文章目录- 1. 数组
- 1.1 数组的创建
- 1.2 数组的初始化
- 1.3 多维数组
- 2. 基础算法
- 2.1 数的运算
- 2.1.1 交换两个数
- 2.1.2 求两数中的较大值或较小值
- 2.1.3 求两个数的最大公因数
- 2.1.4 求取两个数的最小公倍数
- 2.2 典型的数组处理
- 2.2.1 找出数组中最大值或最小值
- 2.2.2 计算数组元素的平均值
- 2.2.3 复制数组
- 2.2.4 数组元素逆序
- 2.2.5 判断数组是否有序
- 2.2.5.1 数组升序
- 2.2.5.2 数组降序
- 2.2.5.3 判断数组有序
- 2.2.6 在数组中查找值
- 2.3 数学函数
- 2.3.1 求一个数的绝对值 ∣ x ∣ left| x right| ∣x∣
- 2.3.2 计算两数的平方和 a 2 + b 2 a^2+b^2 a2+b2
- 2.3.3 计算直角三角形的斜边
- 2.4 简单计时
- 2.4.1 clock()函数
- 2.4.2 time()函数
- 2.4 其它算法
C/C++中的数组能够顺序存储相同类型的多个数据。除了存储数据，我们也希望能够访问数据。访问数组中的某个元素的方法就是将其编号然后索引。
C/C++中元素的编号是从0开始，而不是从1开始，遵循左闭右开原则。如果我们有
N
N
N个元素，它们的编号则为
0
0
0 到
N
−
1
N-1
N−1。这样，对于一个数组 a，我们就能把
0
0
0 到
N
−
1
N-1
N−1 之间任意的i作为元素的索引，在代码中用a[i]唯一地表示第i+1个元素的值，在 C/C++ 中这种数组被称为一维数组。
在C/C++中，创建数组有两种方式：
第一种方式是直接创建一个固定大小的数组，它所需要的内存在编译期就会被确定和分配。声明数组时，必须要用一个编译时常量指定数组的长度。
C99标准中的变长数组 允许使用变量来指定数组的长度，但是C++标准并不支持。
int a[16];
第二种方式是使用动态内存分配，可以在运行期分配内存，所需的内存空间大小不需要在编译期确定。
C函数库
#includeint* a = (int*)malloc( 16 * sizeof(int)); free(a);
而C++中有分别用于动态内存分配和释放的关键字：new 和delete。
int* a = new int[16]; delete[] a;
当动态分配的内存不再需要使用时，应该将其释放，将其归还给系统内存池，这样它以后可以被重新分配使用。分配内存但在使用完毕后不释放将引起内存泄漏(memory leak)。
1.2 数组的初始化 在上面的示例中，数组创建后并没有被初始化，那么数组元素的值是多少呢？
如果数组在代码块之外被声明或者使用了static关键字进行声明，那么数组将被存储于静态内存中，也就是不属于栈的内存，这时数组属于静态变量，数组元素的初始值将会自动设置为零。
如果数组在代码块内部声明，且没有用static关键字声明为静态变量，那么数组将被存储在栈中，属于自动变量，此时数组中元素的值是未初始化的，元素的值是多少取决于内存原本的值。
就像普通变量可以在声明中进行初始化一样，数组也可以这样做。唯一的区别就是数组的初始化需要一系列的值，这些值位于一对花括号内，每个值之间用逗号分隔。初始化列表给出的值将被逐个赋值给数组的各个元素。
int a[6] = {3, 1, 4, 1, 5, 9};
需要注意的是，声明的数组长度可以比列表长度大，但不能比列表长度小。
int a[3] = {1, 2, 3}; //正确
int a[4] = {1, 2, 3}; //正确，声明的数组长度可以大于列表长度，剩余的元素将被初始化为默认值0
int a[2] = {1, 2, 3}; //错误，声明的数组长度不允许小于列表长度
如果声明中并未给出数组的长度，编译器就把数组的长度设置为刚好能够容纳列表中所有初始值的长度。如果初始值列表经常修改，这个技巧尤其有用。
如果声明中并未给出数组的长度，该如何得知呢？可以使用 sizeof 关键字。
int a[] = {1, 2, 3}; //正确，数组长度不写明，将和列表长度一致，长度为3
int length = sizeof(a) / sizeof(a[0]); //获取数组a的长度
1.3 多维数组
如果某个数组的维数不止一个，那么它将被称为多维数组。例如，下面的声明：
int a[2][3]; //二维数组 int b[10][16][2]; //三维数组 int c[2][3][4][5]; //四维数组
多维数组的内存依然是连续的。多维数组中最常用的是二维数组，是“数组的数组”。
下面来看看一维数组a[3]和二维数组b[2][3]的数组元素的存储顺序(storage order)：
在上图中，二维数组b[2][3]优先存储b[0]，再存储b[1]，说明了数组元素的存储顺序。
在C中，多维数组的元素存储按照最右边的下标率先变化的原则，称为行主序(row major order)。
二维数组的动态内存分配则需要先分配一个指针数组，再为数组里的每个指针元素赋值一个一维数组的首地址。释放时顺序则相反，先释放指针数组里指针所指的内存，再释放指针数组的内存。
int row = 2, col = 3;
//分配内存
//先动态分配一个int*型的指针数组
int** a = new int*[row];
//再为数组里的指针素动态分配一个数组
for (int i = 0; i < row; i++) {
a[i] = new int[col];
}
//释放内存
//释放时释放顺序则相反，先释放指针数组里指针所指的内存
for (int i = 0; i < row; i++) {
delete[] a[i];
}
//再释放指针数组的内存
delete[] a;
2. 基础算法
2.1 数的运算
2.1.1 交换两个数
通常使用三变量法交换两个变量的值，对于 int 型变量 a 和 b ，可以使用如下代码进行交换：
int temp = a; a = b; b = temp;
写成函数形式：
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
swap() 函数调用：
swap(&a, &b);2.1.2 求两数中的较大值或较小值
可以使用三目运算符的简洁写法，比较两个数值，如果 a > b a > b a>b，则返回 a a a，否则返回 b 。 b。 b。
int max(int a, int b)
{
return a > b ? a : b;
}
int min(int a, int b)
{
return a < b ? a : b;
}
因为上述的函数十分简单，通常定义为宏或者内联来避免函数调用耗时（当然，编译器优化可能会自动帮我们进行这项操作）
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
2.1.3 求两个数的最大公因数
最大公因数(Greatest common divisor)也叫做最大公约数，两个整数的最大公因数(Gcd)是能同时整数二者的最大整数。例如 Gcd(50, 15) = 5，Gcd(16, 8) = 8。
求解通常使用欧几里得算法，也叫辗转相除法。
unsigned int gcd(unsigned int m, unsigned int n)
{
unsigned int rem;
while (n > 0) {
rem = m % n; //求m 除以 n 的余数
m = n;
n = rem;
}
return m;
}
这里无需保证
m
⩾
n
m geqslant n
m⩾n，因为如果
m
<
n
m < n
m 两个数的最小公倍数(Lowest common multiple)是指能同时被两个数整除的整数中的最小值，有如下计算公式。 要求 声明一个变量maxValue来记录数组中元素的最大值，遍历数组，与每一个元素进行比较，当元素的值比当前记录的最大值还要大时，更新maxValue的值。 最小值则遍历比较，找到更小的值时进行更新。 要求 遍历数组，对数组进行求和，最后判断数组长度是否大于0，数组长度大于0则返回平均值(数组所有元素值之和除以数组长度)，否则返回0。 要求 动态分配一个相同长度的数组，然后逐一复制每个数组元素。 如果仅要求将元素复制到另一个数组中，则只需要将数组逐一复制即可。 要求 将数组对应位置上的元素成对交换即可。假设数组长度为
N
N
N，交换的两个元素索引
i
,
j
i, j
i,j满足关系：
i
+
j
=
N
−
1
i+j=N-1
i+j=N−1。 要求 遍历数组，比较相邻的两个元素，如果找到不符合升序（索引值较大的元素反而值比较小）的情况，则可以直接判断出数组不是升序，结束循环。循环结束后，如果没有找到不符合的情况，说明数组为升序。 数组降序判断也是类似的处理。 要求 数组有序要求数组是升序或者降序均可，那么我们可以从头开始遍历，先找出两个相邻且不相等的值，然后继续遍历数组，根据这两个值的大小关系来对数组剩余部分做升序判断或者降序判断。如果找不到两个不相等的值，则说明数组中所有的元素都相等，数组有序。 要求 从头开始遍历数组，直到查找到和给定值相等的元素为止，返回其索引。如果遍历完成后仍未查找到，则返回-1。这种查找方法也叫线性查找。 判断值是否小于0，小于则返回其相反数，否则返回原来的值。 由勾股定理可得，直角三角形两条直角边
a
a
a和
b
b
b与斜边
c
c
c的长度关系为：
c
2
=
a
2
+
b
2
c^2 = a^2 + b^2
c2=a2+b2，可得：
c
=
a
2
+
b
2
c = sqrt{a^2 + b^2}
c=a2+b2
。 C 语言中的 time 函数总结 在程序中时有计时的需要，比如计算一段代码运行的耗时，这时可以通过调用C标准库 clock() 函数可以返回当前程序运行的时间，单位是(1 / CLOCKS_PER_SEC) 秒，这个宏CLOCKS_PER_SEC通常是1000，所以clock()的时间单位通常是毫秒(ms)。 函数声明: 返回值类型为 clock_t，是一个整数类型，表示程序运行时间（单位通常为毫秒）。 可以通过在一段代码前后分别调用 clock() 函数获取程序运行时间，两者相减即可得到代码的运行时间。 因为通常 CLOCKS_PER_SEC 为1000，所以一般计算运行时间时，也使用如下代码即可： time() 函数通常用来获取当前时间的对应的秒数(从1970-01-01 00:00:00开始)，作为随机数的种子，参数传入 NULL 即可。 函数声明： 返回值类型是 time_t，整数类型，被定义为 long 或 long long。实际上32位是不够的，只能记录100多年，所以现在用64位的long long。 使用示例如下： 专栏：算法 上一篇： 下一篇：
两
数
的
最
小
公
倍
数
=
两
数
的
乘
积
两
数
的
最
大
公
因
数
两数的最小公倍数 = cfrac{两数的乘积}{两数的最大公因数}
两数的最小公倍数=两数的最大公因数两数的乘积 鉴于分母不能为0，所以需要额外加个判断，防止两数都为0时出错。unsigned int gcd(unsigned int m, unsigned int n);
unsigned int lcm(unsigned int a, unsigned int b)
{
unsigned gcdValue = gcd(a, b);
return (gcdValue != 0) ? (a * b / gcdValue) : 0;
}
2.2 典型的数组处理
2.2.1 找出数组中最大值或最小值
找出数组中的最大值（最小值），返回其索引。int max(const int a[], int length)
{
int maxValue = a[0];
for (int i = 1; i < length; i++) {
if (a[i] > maxValue)
maxValue = a[i];
}
return maxValue;
}
int min(const int a[], int length)
{
int minValue = a[0];
for (int i = 1; i < length; i++) {
if (a[i] < minValue)
minValue = a[i];
}
return minValue;
}
2.2.2 计算数组元素的平均值
计算数组元素的平均值并返回，当数组长度为0时，返回0。double average(const int a[], int length)
{
double sum = 0.0;
for (int i = 0; i < length; i++)
sum += a[i];
return (length > 0) ? (sum / length) : 0;
}
2.2.3 复制数组
创建一个和给定数组大小一致且对应元素值都相等的数组，返回其首地址。int* copy(const int a[], int length)
{
int* b = new int[length];
for (int i = 0; i < length; i++)
b[i] = a[i];
return b;
}
void copy(int dest[], const int src[], int length)
{
for (int i = 0; i < length; i++)
dest[i] = src[i];
}
2.2.4 数组元素逆序
将数组中元素的顺序颠倒，原来位置为顺数第
n
n
n个的元素变成倒数第
n
n
n个。void inverse(int a[], int length)
{
for (int i = 0; i < length / 2; i++) {
int temp = a[i];
a[i] = a[length - 1 - i];
a[length - 1 - i] = temp;
}
}
2.2.5 判断数组是否有序
2.2.5.1 数组升序
判断数组中的元素是否是按照从小到大的顺序排序（单调递增）。
数组升序即数组中任意两个元素都满足索引值较大的元素大于等于索引值较小的元素（即如果i > j，有a[i] >= a[j]）。
注意：
这里并不要求数组元素值 严格单调递增，允许有相等的情况。bool isAscending(const int a[], int length)
{
for (int i = 1; i < length; i++) {
if (a[i] < a[i - 1])
return false;
}
return true;
}
2.2.5.2 数组降序
bool isDescending(const int a[], int length)
{
for (int i = 1; i < length; i++) {
if (a[i] > a[i - 1])
return false;
}
return true;
}
2.2.5.3 判断数组有序
判断一个数组是否有序（单调性），升序或降序均可，元素可以相等，不要求严格单调。//这里需要调用上面的两个函数
bool isAscending(const int a[], int length);
bool isDescending(const int a[], int length);
bool isSorted(const int a[], int length)
{
int i = 1;
while ((i < length) && (a[i-1] == a[i])) {
i++;
}
if (i < length) {
int len = length - i;
if (a[i] > a[i - 1])
return isAscending(&a[i], len);
else
return isDescending(&a[i], len);
}
else
return true;
}
2.2.6 在数组中查找值
在数组中查找出给定值相等的元素，返回其索引，如果数组中有多个元素的值和给定值相等，则返回最小的一个索引。如果数组中没有和给定值相等的元素，返回-1。int search(int value, const int a[], int length)
{
int pos = 0;
while ((pos < length) && (a[pos] != value)) {
pos++;
}
return (pos >= length) ? -1 : pos;
}
2.3 数学函数
2.3.1 求一个数的绝对值
∣
x
∣
left| x right|
∣x∣
int abs(int x)
{
return (x < 0) ? -x : x;
}
double abs(double x)
{
return (x < 0.0) ? -x : x;
}
2.3.2 计算两数的平方和
a
2
+
b
2
a^2+b^2
a2+b2
double square(double a, double b)
{
return a*a + b*b;
}
2.3.3 计算直角三角形的斜边
#include
2.4 简单计时
#include
typedef long clock_t;
示例如下：#include
clock_t runTime_ms = endClock - startClock;
2.4.2 time()函数
#include
#include
2.4 其它算法
