数组概述

Array Allocation

对于数据类型 T 和 整型常数 N，声明如下 T A[N]，这个声明有如下效果：

1. 首先，计算机在内存中分配一个 L * N 字节的连续区域，这里 L 指的是数据类型 T 的大小。
2. 数组引入标识 A, 可以用 A 来作为指向数组开头的指针，这个指针的值表示为 Xa，可以用 0 ~ N-1 的整数索引来访问该数组元素,第 i 个数组元素会被存放在地址为 Xa + L*i 的地方。

访问数组

Array Access

C 语言允许对指针进行运算，而计算出来的值会根据该指针引用的数据类型的大小进行伸缩。也就是说，如果 p 是一个指向类型为 T 的数据的指针，p 的值为 xp, 那么表达式 p+i 的值为 xp + L*i，这里 L 是数据类型 T 的大小。操作符 & 可以产生指针，操作符 * 可以产生间接引用指针。也就是说，对于一个表示某个对象的表达式 Expr， &Expr 是给出该对象地址的一个指针。对于一个表示地址的表达式 AExpr, *AExp 是给出该地址处的值。因此，表达式 Expr 和 *&Expr 是等价的。可以对数组和指针应用数组下标操作，数组引用 A[ i ] 等价于表达式 *（A+i）,它计算第 i 个数组元素的地址，然后访问这个内存地址。

嵌套数组

Nested Array

当我们创建数组类型的数组时，数组分配和引用的一般原则也是成立的。创建了一个 T 数据类型的嵌套数组 A [R][C]，表示数组有 R 行，C 列，一个 T 数据类型需要 k 个字节存储。 整个数组 A 的大小就是 R * C * k 字节。要访问嵌套数组的元素，编译器会以数组起始为基地址，偏移量为索引，计算出期望的元素的偏移量。对于 A[R][C] 来说， &A[i][j] 的内存地址为 &A[R][C] = x + k * ( C * i + j )，其中 x 为数组 A 的起始地址， k是数据类型 T 以字节为单位的大小。

数据内存排列顺序

二维数组在内存中的排列顺序是以行为主，如上图所示，int A[R][C] 中 R 的值先从 0 开始，接着 C 的值从 0 ~ (c-1), 之后 R 的值到 1， C 的值再从 0 ~ (c-1), 直到 R 的值为 R-1。

多维数组

回忆一下，上面提到的嵌套数组。

Nested Array Example

那么接下来讲讲多维数组，这两个概念可是不一样的哦！

Multi-Level Array Example

上图中，首先定义了三个 zip_dig 类型的数组 cmu,uw,ucb。然后定义了一个 univ 的指针数组，该指针数组保存了 cmu,uw,ucb 的值。注意一下，univ 保存的是指针。

那么怎么访问嵌套数组呢？又怎么访问多维数组呢？

Array Element Accesses

对于嵌套数组来说，数组在内存的排列是连续的。所以数组元素的内存地址的计算方式是 Mem [ sea + 20 * index + 4 *dig ] ，其中 sea 是数组的起始地址，4 是数组中每个元素的字节大小， 20 是嵌套数组每行的内存容量由 4 * 5 得来，Mem表示内存数组。

嵌套数组

对于多维数组来说，数组在内存的排列则是非连续性的，依赖于指针的值。数组元素的内存地址的计算方式需要经过 2 个步骤，第一个步骤是计算出一维数组的指针地址 Mem[univ + 4 * index],第二个步骤才是计算出数组元素的地址 Mem[ Mem[univ + 4 * index] + 4* dig]。其中 univ 是多维数组的起始位置， 4 是数组中每个元素的字节大小，Mem表示内存数组。

多维数组

结构体

Structures

C 语言的 struct 声明创建一个数据类型，将可以能不同类型的对象聚合到一个对象中，用名字来引用结构中的各个组成部分。类似于数组的实现，结构中的所有组成部分都存放在内存中一段连续的区域内，而指向结构的指针就是结构第一个字节的地址，结构体中的变量的偏移地址是由编译器在编译时期确定的。

Structures

对于 struct 的实例来说，我们可以使用点（.）操作符来引用 struct 的变量

struct rec r1; 
r1.i = val; 

也可以使用指针来表示 struct，如 struct rec *r = &r1;
使用指针和点（.）操作符来访问 struct 变量

struct rec r1; 
(*r1).i = val; 

使用箭头（->）操作符来访问 struct 变量

r->i = val;

结构体对齐

Structures & Alignment

数据对齐的实现是依赖于机器的，IA32 Linux,x86-64 Linux 和 window 都是有差异的。

Unaligned Data

如上图所示，结构体 S1 的内存排列顺序在未进行对齐的情况下是这样的。按结构体的变量声明顺序排列，每个变量的容量大小按变量类型的字节大小分配。

Aligned Data

在数据对齐中，有 2 个重要的点，第

1. 假设变量的数据类型的字节大小 k 。
2. 对于数据类型的字节大小为 k 的变量，这个变量的地址必须是 k 的倍数。

对于结构体 S1, char c 分配 1 个字节， int i [2] 分配 8 个字节， double v 分配 8 个字节。

1. 从结构体对齐的角度来说，结构体 S1 的第一个变量 c 的地址必须是结构体 S1 的最大数据类型 double 的字节大小的倍数。
2. 结构体 S1 的第二个变量是 int 类型的 i[0],根据 “对于数据类型的字节大小为 k 的变量，这个变量的地址必须是 k 的倍数” 的原则， i[0] 的地址必须是 4 的倍数，所以需要在 c 之后增加 3 个 字节的位置之后再放置 i[0]。
3. 结构体 S1 的第二个变量是 int 类型的 i[1],由于 i[0] 的地址是 4 的倍数，而且 i[0] 占用 4 个位置，所以 i[0] 之后不需要增加额外的位置，可以直接放置 i[1]。
4. 结构体 S1 的第三个变量 v 是 double 类型，所以 v 的地址需要是 8 的倍数，i[1] 的地址是 8 的倍数，而 i[1] 的容量是 4，所以需要再增加额外的 4 个字节之后再放置 v。
5. 所以结构体 S1 的内存对齐格式如上图所示。

总结

数组和结构体是 C 语言编程过程中经常使用到的数据类型，对它们的理解越多越深，更能避免使用过程中的各种错误。

参考

本文是华盛顿大学的公开课 《 The Hardware / Software Interface 》的课程笔记，该课程的参考书籍是大名鼎鼎的 CSAPP 也就是《 深入理解计算机系统 》这书。文章截图来源于课程，文章的内容也参考了 CSAPP 的书本内容。

1. https://courses.cs.washington.edu/courses/cse351/17wi/videos.html
2. https://book.douban.com/subject/26912767/