第08讲：数组初步

《计算机程序设计》

苏醒

计算机学院计算机研究所编译系统研究室

课前准备

• 在WSL Ubuntu中建立一个专门的目录用于课上练习，如~/course

$ mkdir ~/course

• 打开VSCode并连接到WSL，打开此目录并新建文件，如~/course/main.cpp
• 编辑main.cpp，随堂编程练习的代码请直接在此文件中编辑

main.cpp

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
  // ============= begin =============

  // =============  end  =============
  return 0;
}

温故

考考你

阅读下列程序，判断程序输出是什么？

#include <iostream>

void maxmin(double a, double b, double c, double &max, double &min) {
  max = min = a;
  if (b > max) max = b;
  if (c > max) max = c;
  if (b < min) min = b;
  if (c < min) min = c;
  return;
}

double max, min;

int main() {
  double a = 1.0, b = 2.0, c = 3.0;
  maxmin(a, b, c, max, min);
  std::cout << "max = " << max << std::endl;
  std::cout << "min = " << min << std::endl;
  return 0;
}

学习目标

• 学习内容
  • 数组的定义与初始化
  • 数组的访问与遍历
  • 数组作为函数参数
  • 排序与查找

学习目标

• 掌握数组的定义、初始化与使用方法
• 理解数组的内存布局、数组名的本质
• 应用数组解决排序与查找问题

数组的定义与初始化

C++类型系统

---
config:
  look: handDrawn
  themeVariables:
    fontSize: 28px
---
flowchart TD
  类型系统 --> 基础类型
  类型系统 --> 复合类型
  基础类型 --> 整型
  基础类型 --> 浮点型
  基础类型 --> 字符型
  基础类型 --> 布尔型
  复合类型 --> 数组
  复合类型 --> pointer["指针/引用"]
  复合类型 --> struct["结构/类"]
  复合类型 --> 枚举
  复合类型 --> 联合

数组类型

• 在C++中，数组用于存储一组数据，具有以下特点
  • 数组长度固定
  • 元素数据类型相同
  • 元素有序排列并在内存中连续存储

考考你

C++数组与Python列表有什么区别？

数组的定义

• C++数组定义语法为

存储类别 元素类型 数组名[数组长度];

• 元素类型可以是任意基础类型或复合类型
• 数组长度是一个整型表达式，可以是常量或变量

数组定义示例

#include <iostream>
int main() {
  int a[4];            // 整型数组，长度为4，自动存储
  static double b[2];  // 双精度数组，长度为2，静态存储
  int n;
  std::cin >> n;       // 输入12
  char c[n];           // 字符数组，长度为n（C++11支持），自动存储
  return 0;
}

数组的内存布局

• 数组在内存中是连续存储的
• 数组中每个元素都满足所属类型的对齐要求

数组在内存中的连续存储（一个方格代表4字节）

数组定义示例

#include <iostream>
int main() {
  int a[4];            // 整型数组，长度为4，自动存储
  static double b[2];  // 双精度数组，长度为2，静态存储
  int n;
  std::cin >> n;       // 输入12
  char c[n];           // 字符数组，长度为n（C++11支持），自动存储
  return 0;
}

数组的长度

错误的数组长度示例

int n;
double numbers[n];
int main() {
  int empty[0];
  char negtive[-1];
  return 0;
}

$ g++ -o code/arraysize code/arraysize.cpp

code/arraysize.cpp:2:16: error: size of array ‘numbers’ is not an integral constant-expression
    2 | double numbers[n];
      |                ^
code/arraysize.cpp: In function ‘int main()’:
code/arraysize.cpp:5:18: error: narrowing conversion of ‘-1’ from ‘int’ to ‘long unsigned int’ [-Wnarrowing]
    5 |   char negtive[-1];
      |                  ^
code/arraysize.cpp:5:16: error: size ‘-1’ of array ‘negtive’ is negative
    5 |   char negtive[-1];
      |                ^~

考考你

• 静态长度的数组和动态长度数组在内存分配上有什么区别？

数组的初始化

• 数组在定义的同时可以进行初始化，使用{}括起来初始化表达式列表

数组初始化示例

#include <iostream>
void printArray(const char *name, int a[], int n) {
  std::cout << name << ": ";
  for (int i = 0; i < n; i++)
    std::cout << a[i] << ' ';
  std::cout << std::endl;
}
int main() {
  int a[5] = {1, 2, 3, 4, 5}; // 为每个元素赋初值
  int b[5] = {1, 2, 3};       // 为前三个元素赋初值，其余为0
  int c[] = {1, 2};           // 自动推导数组长度为2
  printArray("a", a, 5); printArray("b", b, 5); printArray("c", c, 2);
  return 0;
}

$ g++ -o code/arrayinit code/arrayinit.cpp
$ ./code/arrayinit

a: 1 2 3 4 5 
b: 1 2 3 0 0 
c: 1 2 

初始化与赋值

• 数组的初始化不能等同理解为赋值

数组赋值

int main() {
  int a[5] = {1, 2, 3, 4, 5};
  int b[5];
  b = a;
  b = {1, 2, 3, 4, 5};
  return 0;
}

$ g++ -o code/arrayassign code/arrayassign.cpp

code/arrayassign.cpp: In function ‘int main()’:
code/arrayassign.cpp:4:5: error: invalid array assignment
    4 |   b = a;
      |   ~~^~~
code/arrayassign.cpp:5:5: error: assigning to an array from an initializer list
    5 |   b = {1, 2, 3, 4, 5};
      |   ~~^~~~~~~~~~~~~~~~~

避坑

数组作为整体是不允许赋值的！

数组名的本质

考考你

当对一般变量进行读写操作时，本质上是通过变量名对变量所在的内存空间进行读写，那么数组名的本质是什么？

• 数组名是数组的首地址，是一个常量指针

数组名的本质

#include <iostream>
int main() {
  int arr[5] = {1, 2, 3, 4, 5};
  std::cout << arr << std::endl;
  return 0;
}

$ g++ -o code/arrayname code/arrayname.cpp
$ ./code/arrayname

0x7ffd8c628e90

数组的访问与遍历

数组元素的访问

• 数组元素的访问使用[]运算符，下标从0开始
  • 访问可以是读取或写入操作
  • 数组元素访问越界会导致未定义行为

数组访问示例

#include <iostream>
int main() {
  int arr[5] = {1, 2, 3, 4, 5};
  std::cout << arr[0] << std::endl;
  arr[0] = 10;
  std::cout << arr[0] << std::endl;
  std::cout << arr[6] << ' ' << arr[-1] << std::endl; // 可能有警告，但是不会导致程序崩溃
  arr[-1] = 100; // 极度危险！！！可能导致程序崩溃
  return 0;
}

$ g++ -o code/arrayaccess code/arrayaccess.cpp
$ ./code/arrayaccess

1
10
1610973184 21943

数组的遍历

• 由于数组长度通常是已知的，因此使用for循环遍历数组最为常见

数组遍历示例

#include <iostream>
int main() {
  int arr[5] = {1, 2, 3, 4, 5};
  int sum = 0;
  for (int i = 0; i < 5; i++) {
    std::cout << arr[i] << ' ';
    sum += arr[i];
  }
  std::cout << "\nsum: " << sum << std::endl;
  return 0;
}

$ g++ -o code/arraytraverse code/arraytraverse.cpp
$ ./code/arraytraverse

1 2 3 4 5 
sum: 15

数组访问练习

测一测

编写程序，计算两个n维向量\(x = (x_1, \ldots, x_n)\)和\(y = (y_1, \ldots, y_n)\)的笛卡尔距离 \(d = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}\)

n维向量的笛卡尔距离

#include <iostream>
#include <cmath>
int main() {
  int n = 0;
  std::cin >> n;
  double x[n], y[n];
  for (int i = 0; i < n; i++) {
    x[i] = i; y[i] = 2 * n - i;
  }
  double distance = 0;
  // ============= begin =============

  // ============= end =============
  std::cout << std::sqrt(distance) << std::endl;
  return 0;
}

数组元素作为函数参数

考考你

数组元素作为函数参数时，在函数内修改参数的值，外界是否能感知？

数组元素作为函数参数

#include <iostream>
void update(int x) { ++x; }
void updateByRef(int &x) { ++x; }
int main() {
  int a[5] = {1, 2, 3, 4, 5};
  update(a[0]); std::cout << a[0] << std::endl;
  updateByRef(a[0]); std::cout << a[0] << std::endl;
  return 0;
}

$ g++ -o code/arrayelemparam code/arrayelemparam.cpp
$ ./code/arrayelemparam

1
2

明察秋毫

数组元素可以作为普通参数和引用参数传递，其行为与普通变量相同

数组作为函数参数

• 数组形式参数的语法为元素类型 数组名[]

数组作为函数参数

#include <iostream>
void printArray(int a[], int n) {
  for (int i = 0; i < n; i++)
    std::cout << a[i] << ' ';
  std::cout << std::endl;
}
int main() {
  int a[5] = {1, 2, 3, 4, 5}; // 为每个元素赋初值
  printArray(a, 5);
  return 0;
}

$ g++ -o code/arrayparam code/arrayparam.cpp
$ ./code/arrayparam

1 2 3 4 5 

Try it!

试试给数组形式参数[]中加上长度信息，看看会发生什么？思考能否通过这种方式传递数组长度？为什么？

明察秋毫

数组作为函数参数时，传递的是数组的首地址！再想想，这个首地址是传值还是传引用？

数组参数小结

• 数组作为函数参数的注意事项
  • 形式参数为数组形式，不使用引用
  • 方括号中的数组长度不是必要的，也是无用的
  • 调用时，实参传入一个数组名
  • 为防止越界，通常数组元素个数也作为另一个参数传递过来

数组作为函数参数

#include <iostream>
void printArray(int a[], int n) {
  for (int i = 0; i < n; i++)
    std::cout << a[i] << ' ';
  std::cout << std::endl;
}
int main() {
  int a[5] = {1, 2, 3, 4, 5}; // 为每个元素赋初值
  printArray(a, 5);
  return 0;
}

sizeof运算符

• 对于数组，sizeof运算符返回整个数组的字节数

sizeof运算符

#include <iostream>
int foo(int x[3]) { return sizeof(x) / sizeof(int); }
int main() {
  int a[4]; static double b[2];
  int n; std::cin >> n; char c[n];
  std::cout << "length of a/b/c: " << sizeof(a) / sizeof(int) << " " << sizeof(b) / sizeof(double) << " " << sizeof(c) / sizeof(char) << std::endl;
  std::cout << "length of x:" << foo(a) << std::endl;
  return 0;
}

$ g++ -o code/arraysizeof code/arraysizeof.cpp
$ echo 12 | ./code/arraysizeof

code/arraysizeof.cpp: In function ‘int foo(int*)’:
code/arraysizeof.cpp:2:35: warning: ‘sizeof’ on array function parameter ‘x’ will return size of ‘int*’ [-Wsizeof-array-argument]
    2 | int foo(int x[3]) { return sizeof(x) / sizeof(int); }
      |                                  ~^~
code/arraysizeof.cpp:2:13: note: declared here
    2 | int foo(int x[3]) { return sizeof(x) / sizeof(int); }
      |         ~~~~^~~~
length of a/b/c: 4 2 12
length of x:2

数组声明

考考你

如何声明一个外部数组变量？从数组名的本质出发进行思考

arraydecl.cpp

#include <iostream>
using namespace std;
int main() {
  extern int a[10];
  extern int b[];
  cout << sizeof(a) / sizeof(int) << endl;
//  cout << sizeof(b) / sizeof(int) << endl;
  cout << sizeof(b[0]) / sizeof(int) << endl;
  return 0;
}

arrayextern.cpp

int a[20] = {0};
int b[10] = {0};

$ g++ -o code/arraydecl code/arrayextern.cpp code/arraydecl.cpp

排序与查找

数组的随机访问特性

• C++数组具有随机访问的特性，即索引任意元素的时间复杂度为常数

考考你

对于int a[10]数组，计算机如何在常数时间内访问第5个元素a[4]？为什么数组可以随机访问？

• 数组提供了高效地随机访问，但是也有短板
  • 插入和删除元素的效率很低
  • 难以动态调整数组的长度

线性查找

• 在数组中查找一个元素，复杂度为\(O(n)\)

线性查找

#include <iostream>
int main() {
  int arr[5] = {1, 2, 3, 4, 5};
  int target;
  std::cin >> target;
  for (int i = 0; i < 5; i++) {
    if (arr[i] == target) {
      std::cout << "Found " << target << " at index " << i << std::endl;
      return 0;
    }
  }
  std::cout << "Not found" << std::endl;
  return 0;
}

$ g++ -o code/linearsearch code/linearsearch.cpp
$ echo 4 | ./code/linearsearch

Found 4 at index 3

$ echo 6 | ./code/linearsearch

Not found

二分查找

• 对于一个有序数组，二分查找是一种高效的查找算法，复杂度为\(O(\log n)\)

二分查找

#include <iostream>
int main() {
  int arr[1024];
  for (int i = 0; i < 1024; i++) arr[i] = i;
  int target;
  std::cin >> target;
  // 二分查找
  int left = 0, right = 1023, count = 0;
  while (left <= right) {
    int mid = (left + right) / 2;
    ++count;
    if (arr[mid] == target) {
      std::cout << "Found " << target << " at the " << count << " try\n";
      return 0;
    } else if (arr[mid] < target)
      left = mid + 1;
    else
      right = mid - 1;
  }
  std::cout << "Not found" << std::endl;
  return 0;
}

$ g++ -o code/binarysearch code/binarysearch.cpp
$ echo 236 | ./code/binarysearch

Found 236 at the 10 try

$ echo 955 | ./code/binarysearch

Found 955 at the 8 try

$ echo 2000 | ./code/binarysearch

Not found

考考你

能否解释为什么二分查找算法的时间复杂度为\(O(\log n)\)？

排序

• 对数组进行排序是一种常见的操作，常用的排序算法有
  • 冒泡排序
  • 选择排序
  • 插入排序
  • 快速排序

选择排序

• 选择排序的思路是每次选择未排序部分的最小元素，放到未排序部分的最前面

选择排序

#include <cstdlib>
#include <iostream>
int main() {
  int numbers[1024];
  for (int i = 0; i < 1024; i++)
    numbers[i] = std::rand() % 1024;
  // 选择排序
  for (int i = 0; i < 1024; i++) {
    int min = i;
    for (int j = i + 1; j < 1024; j++)
      if (numbers[j] < numbers[min])
        min = j;
    // 交换numbers[i]和numbers[min]
    int temp = numbers[i];
    numbers[i] = numbers[min];
    numbers[min] = temp;
  }
  return 0;
}

冒泡排序

• 冒泡排序的思路是比较相邻的元素，如果逆序则交换，每次沉底一个最大元素

冒泡排序

#include <cstdlib>
#include <iostream>
int main() {
  int numbers[1024];
  for (int i = 0; i < 1024; i++)
    numbers[i] = std::rand() % 1024;
  // 冒泡排序
  for (int i = 0; i < 1024; i++) {
    for (int j = 0; j < 1024 - i - 1; j++) {
      if (numbers[j] > numbers[j + 1]) {
        // 交换numbers[j]和numbers[j + 1]
        int temp = numbers[j];
        numbers[j] = numbers[j + 1];
        numbers[j + 1] = temp;
      }
    }
  }
  return 0;
}

插入排序

• 插入排序的思路是将一个元素插入到已排序部分的合适位置

插入排序

#include <cstdlib>
#include <iostream>
int main() {
  int numbers[1024];
  for (int i = 0; i < 1024; i++)
    numbers[i] = std::rand() % 1024;
  // 插入排序
  for (int i = 1; i < 1024; i++) {
    // ============= begin ===============

    // ============= end ===============
  }
  return 0;
}

总结

本节内容

---
config:
  look: handDrawn
  themeVariables:
    fontSize: 20px
---
mindmap
  数组初步
    数组定义与初始化
      连续内存布局
      静态长度与动态长度
      数组初始化
      数组名为首地址
    数组访问
      索引运算符
      遍历数组
      数组参数
    查找与排序
      随机访问
      线性查找
      二分查找
      选择排序
      冒泡排序
      插入排序

学习目标

• 掌握数组的定义、初始化与使用方法
• 理解数组的内存布局、数组名的本质
• 应用数组解决排序与查找问题

课后作业

• 实训（截止时间2025.03.27）
  • C&C++数组实训（第1–3关）
  • 综合练习—C&C++数组（第1–3关）
• 预习
  • 教材7.1–7.3：指针

计算机程序设计