程序原本(三十七):程序设计的核心思想——数据结构:顺序存储(指针既是对顺序的结构化存储在运行期的补充,也是天堂与地狱通行证)

阅读数:35 2019 年 9 月 28 日 18:22

程序原本(三十七):程序设计的核心思想——数据结构:顺序存储(指针既是对顺序的结构化存储在运行期的补充,也是天堂与地狱通行证)

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

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

复制代码
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^就是一个游离的、无值的标识。

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

评论

发布