程序原本(三十四):程序设计的核心思想——数据结构:顺序存储(“有一个起始地址的连续区域”思路下的两种数据类型)

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

程序原本(三十四):程序设计的核心思想——数据结构:顺序存储(“有一个起始地址的连续区域”思路下的两种数据类型)

数组(array type)指的是包括某种相同数据(数组元素的类型相同)的连续空间9,它是顺序地址存储这一概念的自然延伸10。首先我们认为 Byte、Word 等基础数据类型是受位宽限制的顺序地址存储,当我们把位宽限制这一条件去掉——或通过长度值来指定连续区域的大小——之后,就得到了数组的概念。由于它自然延伸了(但未改变)顺序地址存储的概念,因此它也可以作用于上述这些基础类型。例如:

9 我们这里先讨论程序设计中一个狭义的数组概念,之后的讨论中会再进一步完善它。

10 理解为抽象概念中的“引申”。

  • DWORD,等义于长度为 4 的字节数组;
  • BYTE,等义于长度为 8 的位数组;
  • INT64,等义于长度为 64 的位数组,或长度为 8 的字节数组,或……

基于此,我们也可以用数组这一概念来统一所有的基础类型,这最终可以将任何数据理解为位数组(bit array)。当然,需要强调,这里的数组是指一个连续空间中的数组,否则就与我们此前的抽象不一致了。

然而,我们留意上述的“某种相同数据”这一抽象限制条件,也就意味着,我们必然会面临“连续空间中包含某几种不同数据”的需求。我们做出这一“必然”判断的原因,是我们的需求总是问题的全集而非某个部分(所谓可能出现的,必将出现)。因此对问题的某一个分类中的所有可能性施以数据抽象,则它必然可以表达问题的全集,以及满足其背后的全部需求。推论上述逻辑:

  • 设定:在连续空间(S)中,要么包含同一种数据(m),要么包含不同种数据(n);
  • 如果存有混杂,则可以将它分解为多个连续的连续空间 (Si),使 (Si) 符合上述设定;
  • 如上,总是可以用 mn 来表示所有数据,并保持它们在空间上的连续性,亦即是 S

结构体(struct type)指的就是包括某几种不同数据的连续空间11。这一概念是对数组的补充,他们一起构成了“用基础数据类型”来复合其他类型的全部可能性。

11 Struct type 一般译作“结构(类型)”,这里用“结构体”以与本书中讨论的、普遍含义上的“(数据)结构”区别开来。一些语言中,结构体也被称为记录,这同样也是数据库中“记录”称谓的源起——本书后文中还将讨论到结构体与数据库之间的抽象关系。

评论

发布