Programming

C 语言学习笔记 07 - 数组基础

数组

数组即为连续相同类型的多个元素，每个数组元素都有对应的下标，对应各个元素的位置，初始位置为 0。

例如，定义一个大小为 10 的数组：

//
// Created by NatsuYuki on 2022/9/7.
//

#include <stdio.h>

#define ARRAY_SIZE 10

int main() {
    int array[ARRAY_SIZE];

    for (int i = 0; i < ARRAY_SIZE; ++i) {
        array[i] = i;
        printf("%d\n", array[i]);
    }

    return 0;
}

得到：

0
1
2
3
4
5
6
7
8
9

Process finished with exit code 0

除了遍历赋值以外，我们也可以直接提供初始化列表赋值。

//
// Created by NatsuYuki on 2022/9/7.
//

#include <stdio.h>

#define ARRAY_SIZE 10

int main() {
    int array[] = {0,1,2,3,4,5,6,7,8,9};

    for (int i = 0; i < ARRAY_SIZE; ++i) {
        printf("%d\n", array[i]);
    }

    return 0;
}

特别的，在非 MSVC 编译器中，我们还可以使用变量声明数组的长度，称为变长数组 (VLA)。

int size = 6;

int array[size]; // it works

元素的默认值

上述代码中，并没有给数组提供其大小，大小为提供的列表大小。

若初始化了一个大小大于所提供初始化值列表的数组，可能会导致混淆。

//
// Created by NatsuYuki on 2022/9/7.
//

#include <stdio.h>

int main() {
    double array[5] = {1.5, 2.4, 3.4};

    for (int i = 0; i < 5; ++i) {
        array[i] = i;
        printf("%lf\n", array[i]);
    }

    return 0;
}
1.500000
2.400000
3.400000
0.000000
0.000000

可以看见，未提供初始值的元素变成了 0.000000。但初始值在不同编译器下有不同表现，应当注意。

指定元素下标初始化数组

在初始化列表中，我们也可以直接提供对应元素的下标插入：

//
// Created by NatsuYuki on 2022/9/7.
//

#include <stdio.h>

int main() {
    char array[5] = {[2] = 'a'};

    for (int i = 0; i < 5; ++i) {
        printf("%c\n", array[i]);
    }

    return 0;
} 

得到以下结果 >>


a



Process finished with exit code 0

同时，如果在 ‘a’ 后面再添加元素，下标则会从 3 开始算起。不过，这种特性在 C99 之后才有。

不可测的默认值

上面提到如果不提供初始化值，也会有默认值替换，但默认值到底是什么？

以 MinGW 为例，我们初始化一个大小为 10 的整型数组并打印：

7bff7f0
bd
5b4818e8
7ff7
f18113d0
25c
0
1
5b481000
7ff7

Process finished with exit code 0

MinGW 只负责划分一片内存区域出来给数组，并不会清理，其中的值可能会被污染。

再使用默认的 msvc：

cccccccc

可见，不同的编译器下默认值行为也不一致。但如果在函数外声明一个数组，则不会出现这种行为。

数组的边界

定义一个大小为 5 的数组。

int main() {
    int array[5];
    return 0;
}

使用调试 + Show In Memory View 查看数组分配的内存位置：

数组内存

msvc 会将其初始化为 cc cc cc cc。

每一个数组都有大小，因此也会有边界，我们可以通过 Memory View 模拟数组越界的行为，查看越界后元素的内存位置。

数组越界

可以看到，C 语言并不会检查边界，而是直接获取下一段内存地址中的内容。你必须自行检查数组边界，否则会造成不可测的后果。

字符串

字符串本质上也是一个数组，我们可以近似将字符串理解为 char[]。

比如表示 Hello World => char string[11] = "Hello World"。

但 char[] 并不等价于字符串，给出以下例子：

//
// Created by NatsuYuki on 2022/9/9.
//

#include <stdio.h>

int main() {
    char string[11] = "Hello World";

    printf("%s\n", string);

    return 0;
}

运行一下，得到了 Hello World烫烫蘔苃!忑/╔? (msvc 环境)，这样的输出结果显然与我们的预期不符。

在 C 语言中，字符串必须以 NULL (\0) 结尾。所以，上述代码中字符串的大小应为 12，即 11 个字符 + 1 个 NULL。

中文字符

我们也可以使用 char[] 以及 wchar_t (宽字符) 来表示中文字符，二者分别使用 GBK 与 UTF-8 编码后的中文字符。

不同编码的中文字符

数组参数

数组可以作为参数传入函数中，以一个求和数组中值的代码为例：

#define SIZE 10

int SumIntArray(int array[SIZE]) {
    int result = 0;

    for (int i = 0; i < SIZE; ++i) {
        result += array[i];
    }

    return result;
}

一切都很完美，但是当尝试传入一个大小与 10 不一致的数组，结果就会发生误差。显然，在将数组作为参数时不能直接定义其大小。

由于数组在传入仅是一个内存地址，并不是数组本身，因此想通过 sizeOf 获取其大小也是不现实的。我们可以尝试传入一个大小为 6 的数组，并使用 sizeOf 获取其大小。

int array[6] = {1, 3, 2, 3, 1, 31};
printf("%d", sizeof(array) / sizeof(array[0]));
-----------------------------------------------
Output 2

显然，2 并不是这个数组的大小。

所以，在将数组作为参数时的函数中，通常需要多添加一个参数作为数组的大小。

int RefactorSum(int array[], int size) {
    int result = 0;

    for (int i = 0; i < size; ++i) {
        result += array[i];
    }

    return result;
}

在 Java 等现代语言中，数组传参时会附带其大小信息，因此不需要额外添加参数。

高维数组

高维数组即为数组的数组，例如 int multiArray[5][2];定义了一个第一维长度为 5，二维长度为 2 的数组。

    int multiArray[5][2] = {
            {1, 1},
            {4, 5},
            {1, 4},
            {1, 9},
            {1, 9}
    };

高维数组与普通数组相同，只不过其中的元素并不是你所熟悉的数字、字符串，而是一个数组，且元素数组的大小与对应维度所定义的大小一致，例如此处二维数组的大小为 2。

高维数组作为参数传入时，一维以后的数组大小需要直接指定，就像这样：

void Function(int x, int y, int z, int 3d[][y][z]) {}

如果想用数组作为返回值，应当让调用方提供数组，而不是像上面一样在函数中声明一个类似 int result[] 的变量用于返回。

因为这个变量默认为 auto 类型，一旦函数返回，这个数组也会被销毁，即使返回了这个数组也不再可用了，正确的做法应该是这样：

void Function(int x, int y, int z, int 3d[][y][z], int result[])

数组排序

终于到了喜闻乐见的快排时刻，虽然排序方式有很多种，但最常用的还属快速排列。

快速排列的机制是 使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。 (摘自维基百科)。下面以排列整数数列为例：

int Swap(int array[], int from, int to) {
    int temp = array[from];
    array[from] = array[to];
    array[to] = temp;
}

int Partition(int array[], int start, int end) {
    int pivot = array[end];
    int partition = low;
    for (int i = low; i < end; ++i) {
        if (array[i] < pivot) {
            Swap(array, i, partition++);
        }
    }
    Swap(array, partition, end);
}

void QuickSort(int array[], int start, int end) {
    if (start >= end) return;
    int partition = Partition(array, start, end);
    QuickSort(array, start, partition - 1);
    QuickSort(array, partition + 1, end);
}

快排的核心是挑选一个基准值 (pivot)，将这一基准值与其他元素比较，并分割为两个不同数列，然后两个数列再进行相同操作，直到不可再分为止。这里基准值选择了数组末尾元素。

基准值的选择对排序的性能有着显著影响，此处仅介绍一种快速排列的实现，并非代表最优方法，可以参阅维基百科条目 快速排序。

comments powered by Disqus