Question

顺序存储中用到了两种数据结构概念，即数组和结构体。在此前的讨论中，我们预设了两个前提，其一是顺序存储，其二是数组元素的长度总是能预知的。后面这个条件往往并不能满足，例如我们有一个程序的功能就是“让用户手工输入元素长度”，那么在编写该程序的时候，（程序员）就无法知道如何分配存储了。

这种情况下，程序员在编程的时候知道一个标识，并且要基于该标识来编写后续逻辑，他只是无法将标记与可能的值关联起来而已。例如下面的形式代码：

1 2 3 4

var pArea; // 无法预知该标识的值 function process(Int len) { pArea = allocMem(len); // 无法预知该标识的值的长度 }

顺序存储的限制条件需要“地址+长度”两个条件，而上面的例子意味着在程序正式运行起来之前只有“地址”是可以预设的。因此我们只能将该地址“预占”起来（记得排排座故事中的“冬冬不在留一个”吧），以便将来用于找到真实地址。下面对比这种情况与一个实际的顺序存储之间的差异。首先是以数组为典型的存储效果，由于长度是已知的，所以程序员可以安排自 X 位置之后存储其他数据（见图 7）：

图 7　已知数据内容的顺序存储

然而，在 待处理的数据 长度未知时，由于“用于存储一个地址值”所需的长度是可知的，所以我们采用“预占”存储效果如图 8 所示：

图 8　数据内容未知时，预占“存储地址值”所需的确定空间

此后程序员仍然可以安排自 X 位置之后的存储——当然，也可以通过编写程序来设计其后的安排。例如，在程序运行过程中，我们在预占位置填写一个 实际的地址值 ，以说明 实际的数据 的存储位置，如图 9 所示：

图 9　保证顺序存储的方案：通过填写预占位置，指示实际的存储位置

通过图 9，我们也可以发现， pArea 本身和 Area 自身都是连续的。如果 unknown 部分也按照上述规则来处理，则 unknown 也将是连续的。如此，我们仍然可以保证整个存储空间是连续的。

现在，我们知道这里所谓的 pArea 就是 指针（pointer） ，它是对 顺序的结构化存储 这一方案在运行期的一种补充，满足两个条件：

• 它是一个标识，有一个计算系统访问它的地址（记为 p ）；
• 它包含数据（值），该值是一个（与它关联的、实际的）数据的地址（记为 p^ ）。

在程序中，通过上述方式来设计数据结构时存在两种可能。其一，如果一个地址是可以先期知道的，那么 p^ 与值的绑定是静态的、在系统运行之前发生的，因此它也是一种安全的指针。其二，如果一个地址是不可预知的，那么 p^ 就需要在运行期再动态地绑定它的值；在正式绑定值之前， p^ 就是一个游离的、无值的标识。

如同我们此前所说过的，如果标识与其值未能绑定，则它的抽象含义——或称之为“计算中的数/数据的含义”——就是不确定的，这也意味着，在这样的模式上建立的计算系统是不安全的。换而言之，指针的动态绑定（以及解除绑定）是一种不安全的机制。

1. 即所谓“算”是程序之表，“数”是程序之本。 ↩
2. 这里我并不强调它是“必备条件”，因为有些计算机和计算机系统并不是由“人”来使用的，因此与它们交互的数据形式也不相同。关于这一点，应退回到本书“第 1 章 数，以及对数据的性质的思考”中，在与“数据的提出”有关的话题中去讨论。 ↩
3. 我们只假设了一种最简单的情况以便于后续讨论。现实是，需要考虑运算器与存储器之间的总线，以及指令与数据缓存、预取装置等，在整个数据的传输过程中的位宽，决定了这些数值的大小以及存取效率。 ↩
4. 这样的表示法显然有非常非常多种可能性，而且也确实存在着好几种在用的方案。 ↩
5. 地址标识与寻址问题是一个复杂而一体的问题，并非此处所说的“整型增量”这样简单。例如，在硬盘读写的寻址方面，就有多套完全独立的体系。这些体系与磁头、磁盘片以及高速马达的惯性等都有关系。地址标识与如何提高设备存取的效能，是计算机系统中“存储”相关的焦点问题。而在此处及后文中，我们仅从软件开发视角上讨论该问题的一个子集，并且事实上“顺序地址”也是软件开发中有关存储的一般抽象。 ↩
6. 这里涉及表示的地址索引与存取大小之间的约定。实际上 x86 约定的地址是字节序的，因此在最后的这个地址上只有一个 Byte 能被处理，而其他的位置将因为无法编码地址而溢出。 ↩
7. 例如一个图形计算环境，就可以考虑以 RGB 为基础数据类型并建立起基于此的运算体系。 ↩
8. 与此前讨论的地址索引问题类似，这个连续区域的实际大小也受限于可用的、能被编码的地址大小。 ↩
9. 我们这里先讨论程序设计中一个狭义的数组概念，之后的讨论中会再进一步完善它。 ↩
10. 理解为抽象概念中的“引申”。 ↩
11. Struct type 一般译作“结构（类型）”，这里用“结构体”以与本书中讨论的、普遍含义上的“（数据）结构”区别开来。一些语言中，结构体也被称为记录，这同样也是数据库中“记录”称谓的源起——本书后文中还将讨论到结构体与数据库之间的抽象关系。 ↩