数据结构中的两个核心概念

在计算机科学中，数据结构是组织和存储数据以供程序处理的重要方式。它们可以从两个核心概念来理解：逻辑结构和物理结构。

1. 逻辑结构：
   • 逻辑结构是指数据元素之间的逻辑关系，它定义了数据元素是如何相互关联的。
   • 例如，线性表 是一种数据结构，其中数据元素之间存在一对一的关系。这使得线性表在处理有序数据时非常有用。
   • 另一个例子是 树型结构，它是一种层次化的节点集合，其中每个节点（除了根节点）都有一个明确的父节点。这种结构在表示具有包含或分类关系的数据时非常有用。
2. 物理结构：
   • 物理结构是指数据元素在存储介质上的实际存放方式，它影响着数据的访问和操作效率。
   • 对于线性表，有两种常见的物理实现：
     • 数组：在数组中，数据元素必须在内存中连续存储。这种连续性使得数组能够提供快速的元素访问，但插入和删除操作可能需要移动大量元素。
     • 链表：与数组不同，链表中的元素不需要在内存中连续存储。每个元素都包含一个指向下一个元素的指针，从而形成链式结构。链表在插入和删除操作上更为灵活，但访问特定元素的速度可能较慢。

数组基础

定义数组时，可以选择性地为数组中的某些元素指定初始值。例如，如果只对数组的第二个元素赋值为 1，而忽略了其他元素的初始化，那么在全局或静态作用域中，未被显式初始化的元素将自动被设置为 0。这种特性确保了数组在使用前具有确定的初始状态，避免了未定义行为。

#define ARRAY_SIZE 5

int array[ARRAY_SIZE] = {[2]=1}; // 除去第二个元素值为1外，其余元素均为0

int array[ARRAY_SIZE] = {[2]=1, 2, 3};  // 若是这样，则是从数组的第二个元素开始赋值，0 0 1 2 3

局部数组和全局数组的默认初始化行为是不同的。全局数组，由于其生命周期贯穿整个程序，存储在静态存储区，如果未显式初始化，则其元素会被自动初始化为 0。这确保了全局数组在使用前具有一个已知的初始状态。

相对地，局部数组的元素在没有明确初始化的情况下，其值是未定义的。局部数组存储在堆栈上，编译器不会为它们提供自动初始化，因此在函数内部定义的数组在使用前需要显式初始化，以避免不确定的行为。

数组的边界

声明数组时，需要指定数组的数据类型和长度。数据类型定义了数组可以存储的元素类型，例如，int 类型的数组只能存储整数。数组名通常遵循变量命名规则，建议使用复数形式以表示多个元素的集合。

C 语言要求数组的长度至少为 1，且长度必须是编译时常量，不能是运行时才能确定的变量。这意味着数组的长度必须在编译时就已知，不能依赖于程序运行时的数据。

数组初始化是为数组的每个元素赋予初始值的过程。初始化可以与声明同时进行，有几种不同的初始化方式：

• 使用花括号 {} 直接指定元素值，如 int arr[] = {1, 2, 3};，这定义了一个包含三个整数的数组，其值为 1、2、3。
• 如果只提供一个元素的值，并且数组长度已知，如 int arr[10] = {0};，则创建了一个长度为 10 的数组，所有元素初始化为 0。
• 如果初始化列表中的元素少于数组长度，未指定的元素将自动初始化为 0，如 int arr[5] = {1, 2, 3};，这将创建一个长度为 5 的数组，其中前三个元素为 1、2、3，后两个元素为 0。

访问数组元素可以通过数组名后跟索引的方式实现。例如，array [5] 访问的是数组 array 从首地址开始的第六个元素，这等同于 array 地址加上 5 个该数组元素类型的字节大小。同样地，array [0] 访问的是数组的第一个元素，即数组的首地址，也就是 array 本身。

需要注意的是，不同的编译器可能对数组长度的处理存在差异。在某些情况下，如果数组长度是一个变量，MSVC（Microsoft Visual C）编译器可能无法通过编译，因为它可能期望数组的大小在编译时是已知的。而 MinGW（Minimalist GNU for Windows）编译器可能允许这种编译，因为它遵循了 GNU GCC 的某些行为，允许在运行时确定数组的大小。

#include <stdio.h>

#define ARRAY_SIZE 5

int main() {

  int value = 5;
  int array_size[value];

  for (int i = 0; i < value; ++i) {
    array_size[i] = i;
    printf("%d ", array_size[i]);    // 0 1 2 3 4
  }

  return 0;
}

数组下标越界是一个常见的错误，它指的是尝试访问数组之外的内存空间。

1. 数组下标越界访问：当程序试图读取或写入数组之外的元素时，就会发生越界访问。这种行为是未定义的，可能会导致程序崩溃、数据损坏或其他不可预测的后果。
2. 数组下标越界修改：越界修改指的是程序不仅访问了数组之外的内存，而且还尝试修改它。这种操作比越界访问更危险，因为它可能会破坏程序的其他部分或操作系统的数据，导致更严重的程序崩溃或安全漏洞。

数组的随机访问原理

数组之所以能够实现随机访问，关键在于其在内存中的存储方式和寻址公式。

寻址公式：

address_array[i] = 首元素地址/数组的基地址 + 目标元素的地址偏移量（offset）

1. 数组的基地址：数组的基地址是数组首元素的地址。在 C 语言中，数组名本身就是数组首元素的地址。
2. 目标元素的地址偏移量（offset）：这是从数组基地址到目标元素地址之间的字节差值。由于数组中的元素在内存中是连续存储的，这个偏移量可以通过元素的下标乘以每个元素的大小来计算。

公式简化：由于数组首元素的下标是 0，因此可以从公式中省略与首元素下标的差值，简化为： address_array[i] = base_address(arr) + i * sizeof(element)

实现前提：

1. 内存空间的连续性：数组的内存空间必须是连续的，这样才能通过寻址公式连续计算每个元素的地址。
2. 元素类型的一致性：数组要求每个存储单元的长度一致，即所有元素的类型和大小必须相同。

为什么数组可以实现快速随机访问？

• 直接计算：由于数组元素在内存中是连续存储的，我们可以通过简单的算术运算直接计算出任意元素的地址。
• 不需要遍历：与链表等数据结构不同，数组不需要从头开始遍历到特定位置，因此访问速度非常快。

数组的限制

• 固定大小：一旦数组被声明和分配，其大小就固定了，不能动态改变。
• 类型一致性：数组中的所有元素必须是同一类型，不能存储不同类型的元素。

可变数组

MSVC 编译器遵循 C90 标准，该标准并不支持变长数组（VLA，Variable-Length Array），这是由于 C90 对数组长度要求在编译时必须是常量表达式。而 C99 标准放宽了这一限制，允许数组的长度在运行时确定，从而支持变长数组。GCC 编译器作为遵循 C99 及之后标准的编译器，对变长数组进行了特别处理，因此能够支持这种特性。

因此，如果代码中使用了变长数组，可能会在 MSVC 编译器中遇到编译错误，因为它默认遵循 C90 标准。而 GCC 编译器则由于其对 C99 及更新标准的兼容，能够正确处理变长数组的定义和使用。

在 C 语言的某些版本和编译器中，使用 const 关键字声明的常量可能会遇到兼容性问题。例如，MSVC（Microsoft Visual C）编译器在处理某些 const 变量时可能会报错，这通常与其对 C 标准的支持程度有关。相比之下，GCC（GNU Compiler Collection）编译器对 const 常量的支持较为全面，能够顺利编译包含 const 声明的代码。

当涉及到 C++ 时，情况有所不同。C++ 语言规范对 const 常量提供了完整的支持，将其视为不可修改的值。在 C++ 中，const 修饰的变量在编译时和运行时都受到保护，确保其值不会被改变，这与 C++ 对数据安全性和稳定性的重视相一致。

const int Ksize = 5;
int array_const[Ksize]; // MSVC报错: 应输入常量表达式; MingW: 成功运行

局部变量数组

局部变量数组是定义在函数体内部的数组，它们具有几个关键特性：

1. 作用域限制：局部变量数组的作用域仅限于定义它们的函数体内部，即它们只能在函数的 {} 花括号内使用。
2. 初始化要求：如果局部变量数组仅声明而没有初始化，那么它们的元素将包含未定义的值，这可能导致未定义行为。因此，在使用前必须手动初始化局部变量数组。
3. 内存分配：局部变量数组的内存是在栈上分配的，这意味着它们存储在虚拟内存空间的栈中。栈内存的优点是性能高，自动管理，但缺点是大小有限，通常远小于堆内存。
4. 栈大小可调：不同编译器平台允许调整栈的大小。例如，在 MSVC 平台上，默认栈大小为 1MB，而在 GCC 平台上，默认栈大小为 8MB。
5. 避免栈溢出：由于栈空间有限，不应在栈上分配大型数据结构，如大型数组。如果分配的内存超出栈容量，可能会导致栈溢出错误，这是一种严重的运行时错误。

数组和链表的对比

数组的优缺点

优点：

1. 随机访问：数组最大的优点是支持随机访问，这意味着可以通过下标直接访问数组中的任何元素，时间复杂度为 O(1)，无论数组的长度如何。

缺点：

1. 连续内存空间：数组需要占用一大块连续的内存空间，这可能导致在内存紧张的情况下分配大数组失败。
2. 不灵活：一旦数组的空间被分配，其长度就固定了，不能动态改变。这使得数组对于需要动态调整大小的场景适应性较差。
3. 类型一致性：数组中的所有元素必须是同一类型，不能存储多种类型的数据。
4. 操作复杂：在数组中进行中间插入或删除元素的操作比较困难，通常需要移动大量元素，时间复杂度为 O(n)，其中 n 是数组的长度。

链表的优缺点

优点：

1. 内存使用灵活：链表不要求元素在内存中连续存储，因此可以更灵活地使用内存，特别是在内存碎片较多的情况下。
2. 动态扩容：链表可以方便地进行扩容或裁剪节点，不需要移动大量元素，使得动态调整大小变得容易。
3. 插入和删除效率高：在链表的中间进行插入或删除操作相对数组来说效率更高，因为通常只需要改变几个节点的指针。

缺点：

1. 不支持随机访问：链表不支持随机访问，访问链表中的元素需要从头开始遍历，时间复杂度为 O(n)，其中 n 是链表的长度。

字符串

英文字符串数组

在 C 语言中，字符数组用于存储字符串，必须在数组的末尾包含空字符 ‘\0’ 作为字符串结束的标识。如果仅将字符数组的大小设置为待存储字符的数量，就会忽略这个重要的空字符，从而导致在使用 printf 函数打印字符串时出现潜在的数组越界问题。

例如，要存储字符串 “hello world”，需要的字符数组大小应该是 13，而不是 11。这是因为除了字符串中的 12 个字符外，还需要一个额外的位置来存储空字符 ‘\0’。正确的声明方式如下：char string [13] = "hello world";

这样声明后，使用 printf ("\n% s", string) 打印字符串时，将正确地在字符串的末尾遇到空字符并停止打印，避免了数组越界。

#include <stdio.h>

void TestString() {
  char string[11] = {"hello world"};

  for (int i = 0; i < 11; ++i) {
    printf("%c", string[i]);    // hello world
  }

  // 由于字符数组设置为 11，不是 12，所以输出结果为：hello world 烫烫烫烫烫烫烫烫?
  printf("\n%s", string);

  // char string[12] = {"hello world"};  // 此处设置为 12
  // printf("\n%s", string);             // 输出结果正常，为：hello world   
}

中文字符串数组

// 中文转换为当前文件的编码，然后以那个编码的形式存入到字符数组中
char zh[] = "你好，中国";    

使用 MSVC 在调试过程中可以查看字符数组：

在 GBK 编码系统中，“你好，中国” 这个中文短语被转换成对应的 GBK 编码序列，例如 “\xc4\xe3\xbc\xd3\xc8\xd5″。这表明在 C 语言中，存储中文字符串的字符数组实际上是在存储 GBK 编码的字节序列。由于 GBK 编码的每个中文字符占用 2 个字节，因此存储这个短语的数组大小需要是 11 个字节，这包括了 7 个中文字符和 2 个字节的标点，以及额外的 1 个字节用于存储字符串结束的空字符 ‘\0’。

宽字符数组与常规字符数组在内部表示上存在显著差异，它们专门设计用来存储 Unicode 字符，每个元素通常对应一个 Unicode 码点的值。例如，如果宽字符数组 ws 的第一个元素 ws [0] 的值被赋为 20320，这实际上代表了 Unicode 编码中的汉字 “你”。这种表示方式允许宽字符数组准确地存储和处理国际化文本。

// wchar_t 是无符号短整型
wchar_t ws[] = L"你好，中国";    // 存储的是 Unicode 的码点

同样需要注意的是，尽管宽字符数组存储的是 Unicode 值，它们仍然遵循 C 语言字符串的惯例，以空字符 ‘\0’ 结尾，这确保了字符串的结束可以被正确识别。因此，如果数组用于存储包含 5 个汉字的字符串，加上结尾的 ‘\0’，数组将总共包含 6 个宽字符元素。

函数的数组类型参数

当在 C 语言中将数组用于函数参数时，应传递数组的首地址以及元素的数量。这是因为数组名在传递过程中会自动转换为指向其第一个元素的指针。因此，为了在函数内部正确地访问数组的每个元素，需要额外提供数组的长度信息。

#include <stdio.h>

int SumArray(int array[], int n) {
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += array[i];
  }
  return sum;
}

int main() {

  int arrays[] = {1, 2, 3, 4, 5};
  int array_size[] = {1, 2, 3, 4, 5, 6, 7};

  int a = SumArray(arrays, 5);    // 15
  int b = SumArray(array_size, 7);  // 28

  printf("%d\n", a);
  printf("%d", b);

  return 0;
}

二维数组

二维数组的初始化

在 C 语言中初始化二维数组时，如果只指定了数组中某些特定位置的初始值，那么剩余未指定的位置将默认初始化为 0。这与一维数组的初始化行为保持一致，确保了数组的每个元素都有一个确定的初始状态。

int vehicle[3][2] = {1, 2, 4, 5, [1][1] = -1    // 二维数组结果为 1 2 4 -1 0 0
};

二维数组的本质

1. 数学角度：在数学上，二维数组可以被视为矩阵，它具有行和列的结构。矩阵中的每个元素都可以通过行号和列号来唯一确定其位置。例如，一个 int 类型的二维数组 int arr[5][9]；其中 arr[3][4] 表示矩阵的第四行第五列的元素。掌握矩阵的概念有助于理解和使用二维数组。
2. 内存角度：在内存中，二维数组并不是一种独特的结构，它实际上是一维数组的集合，其中每个元素都是一个一维数组。这意味着二维数组的每个元素都是相同类型的一维数组，它们必须具有相同的长度，以确保二维数组的列数是唯一确定的。
   • 二维数组的声明中，列数是类型的一部分，不能省略。例如，double arr[][10]; 表示这个二维数组的元素是类型为 double[10] 的一维数组，即可以存储多个长度为 10 的 double 类型一维数组。
   • char arr[4][7]; 表示此二维数组的元素是类型为 char[7] 的一维数组，且共有 4 个这样的一维数组。

二维数组的遍历

在 C 语言中，二维数组在内存中是按行主序存储的，这意味着数据首先连续存储完数组的第一行，然后才是第二行，依此类推。这种存储方式使得二维数组在内存中是连续的，但行与行之间是分开的。

由于二维数组的这种存储特性，遍历二维数组时通常采用先遍历行再遍历列的顺序。这种遍历方式可以通过嵌套的 for 循环实现，其中外层 for 循环负责遍历数组的行，而内层 for 循环则负责遍历每一行中的列。

二维数组的传参

在 C 语言中，当需要将二维数组传递给函数时，由于 C 语言在函数参数中只识别一维数组的概念，因此必须对二维数组的传递方式进行特殊处理。具体来说，可以在函数参数中指定二维数组的第二维大小，例如使用 int array [rows][cols] 的形式，其中 rows 是数组的行数，而 cols 是列数，两者都需要在函数调用时明确。

然而，如果在函数原型中使用变量来指定数组的大小，如 int array[][cols] ，其中 cols 是函数的参数，这在某些编译器中可能会导致编译错误。MSVC（Microsoft Visual C）编译器可能不支持这种语法，因为它要求数组的大小在编译时是已知的常量表达式。而 MinGW（Minimalist GNU for Windows）编译器则可能允许这种语法，因为它遵循了 GNU GCC 的某些行为。

// 参数 row, col 的作用域是函数原型作用域
void SumIntArray(int rows, int cols, int array[][cols], int result[rows]) {
  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < cols; ++j) {
      result[i] += array[i][j];
    }
  }
}
// MSVC 编译器无法运行，报错: error C2057: 应输入常量表达式
//                         error C2466: 不能分配常量大小为 0 的数组
//                         error C2087: “array”: 缺少下标

数组作为函数返回值

在 C 语言编程中，数组本身不能作为函数的返回类型，因为数组在返回时会被退化为指向其首元素的指针，从而导致数据丢失。相反，我们通常通过将数组的指针或引用作为函数参数来实现数组数据的传递和修改。

这意味着，当我们希望在函数中处理数组并改变其内容时，我们会将数组的指针传递给函数。函数可以修改指针指向的数组元素，因为指针指向的是原始数组的内存地址。例如，一个函数可能会接收一个整型数组的指针，并在函数内部对数组中的元素进行变换或排序。

#include <stdio.h>

void SumIntArray(int rows, int cols, int array[][cols], int result[rows]) {
  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < cols; ++j) {
      result[i] += array[i][j];
    }
  }
}

int main() {

  int vehicle[3][2] = {1, 2, 4, 5, [1][1] = -1    // 二维数组结果为 1 2 4 -1 0 0
  };

  int result[3] = {0};    // 注意一定要清 0，否则计算求和要出大问题，因为初值不确定

  SumIntArray(3, 2, vehicle, result);

  for (int i = 0; i < 3; ++i) {
    printf("%d ", result[i]);    // 3 3 0
  }

  return 0;
}