数组概述
Array Allocation
对于数据类型 T 和 整型常数 N，声明如下 T A[N]，这个声明有如下效果：
- 首先，计算机在内存中分配一个 L * N 字节的连续区域，这里 L 指的是数据类型 T 的大小。
- 数组引入标识 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 个重要的点，第
- 假设变量的数据类型的字节大小 k 。
- 对于数据类型的字节大小为 k 的变量，这个变量的地址必须是 k 的倍数。
对于结构体 S1, char c 分配 1 个字节， int i [2] 分配 8 个字节， double v 分配 8 个字节。
- 从结构体对齐的角度来说，结构体 S1 的第一个变量 c 的地址必须是结构体 S1 的最大数据类型 double 的字节大小的倍数。
- 结构体 S1 的第二个变量是 int 类型的 i[0],根据 “对于数据类型的字节大小为 k 的变量，这个变量的地址必须是 k 的倍数” 的原则， i[0] 的地址必须是 4 的倍数，所以需要在 c 之后增加 3 个 字节的位置之后再放置 i[0]。
- 结构体 S1 的第二个变量是 int 类型的 i[1],由于 i[0] 的地址是 4 的倍数，而且 i[0] 占用 4 个位置，所以 i[0] 之后不需要增加额外的位置，可以直接放置 i[1]。
- 结构体 S1 的第三个变量 v 是 double 类型，所以 v 的地址需要是 8 的倍数，i[1] 的地址是 8 的倍数，而 i[1] 的容量是 4，所以需要再增加额外的 4 个字节之后再放置 v。
- 所以结构体 S1 的内存对齐格式如上图所示。
总结
数组和结构体是 C 语言编程过程中经常使用到的数据类型，对它们的理解越多越深，更能避免使用过程中的各种错误。
参考
本文是华盛顿大学的公开课 《 The Hardware / Software Interface 》的课程笔记，该课程的参考书籍是大名鼎鼎的 CSAPP 也就是《 深入理解计算机系统 》这书。文章截图来源于课程，文章的内容也参考了 CSAPP 的书本内容。
网友评论