《计算机程序设计艺术》数据结构之线性表速学

1,111

神书一本,简称 TAOCP,以下是它的维基百科的介绍,你看了就知道它多神了。

不过并不推荐各位购买,因为很可能看不懂。

接下来进入第一章。我会跳过 99% 跟数学有关的知识

数学归纳法

  1. 先证明 P(1) 为真
  2. 再证明 P(n) 为真时,P(n+1) 也为真

此为数学归纳法。

它不同于不完全归纳法,不完全归纳法至多是最好的预测,而数学归纳法是结论性的证明。

此后,本书用了大量的篇幅讲了无数数学题目,直接跳过。

接着书中介绍了一个名叫 MIX 的类汇编语言。这个语言能让你以机器的角度理解很多东西,但是我在这里并不打算介绍它,因为它的「劝退功效」相当突出,不信的话看看下面截图(不要担心,后面的内容绝对不会出现这种东西):

子程序

当程序中有若干地方需要执行同一个任务时,为了避免重复的代码,可以把这部分代码放在一个单独的地方,称为子程序。

执行完子程序后,要通过额外的转移指令(JUMP),回到主程序。

解释性程序

解释性程序是执行另一个程序(某种「类机器语言」写成)的指令的计算机程序。所谓类机器语言,指的是该语言的指令一般含有操作码、地址等。

这些定义和当今大多数计算机术语一样,是不精确的。我们根本不可能精确地划分哪些程序是解释性程序,哪些不是。

第一个解释程序可以说是「通用图灵机」,即一个有能力模拟任何其他图灵机的图灵机。

应用最广泛的早期解释程序大概是 IBM 701 快速编码系统。

接下来进入第二章:信息结构

线性表

  • 栈:所有插入和删除都在表的一端进行的一种线性表。
  • 队列:插入在表的一端,删除在另一端的一种线性表。
  • 双端队列:插入和删除可以在两端进行的一种线性表。

有人把栈叫做下推表、反向存储器、窖(cellars)、堆叠(piles)、后进先出表。 有人把队列叫做循环存储器、先进先出表。

还有一些其他术语,如压入栈的顶部、从栈的顶部弹出。

对于栈,一般使用「上下」表示方向;对于队列使用「在队列中等候」这样的属于;对于双端队列,使用「左右」表示方向。

顺序分配

在一台计算机中保存线性表最简单和自然的方法是把表放进连续的单元中,一个挨着一个。

这段连续单元的第一个单元的地址被叫做「基地址」,即 X[0] 对应的地址。

顺序分配对于处理栈来说非常方便,只需要设定一个栈指针变量 T

  • 当栈为空时,令 T = 0。
  • 把 Y 压入栈顶部时,T <- T + 1; X[T] <- Y
  • 把顶部元素弹出时,Y <- X[T]; T <- T - 1

但顺序分配对于队列或者双端队列的处理,则需要技巧。可以维持两个指针 F 和 B,F 表示前,B 表示后。

  • 当队列为空时,F = B = 0
  • 将 Y 插入队列时,B <- B + 1; X[B] <- Y
  • 出队时, F <- F + 1; Y <- X[F]。如果 F = B,则置 F <- B <- 0

为了避免队列过多地占用存储器,可以把 M 个节点做成一个圆圈

  • 将 Y 插入队列时,如果 B = M,则 B <- 1;否则 B <- B + 1; X[B] <- Y
  • 出队时,如果 F = M,则 F <- 1;否则 F <- F + 1; Y <- X[B]

不用圆圈的方式会让 F 和 B 一直增大,容易溢出(上溢 overflow 和下溢 underflow);用了圆圈则可限制至多有 M 个节点。 即使限制到 M 个节点,其实也存在 overflow(插入队列时发现 F 和 B 相等) 和 underflow(出队时发现 F 和 B 相等)。

有的时候我们会重复地删除元素直到出现 underflow 为止;而 overflow 则通常意味着一个错误,表满了,装不下了,程序只能终止。

共用空间

上面的讨论只考虑一个线性表,但是我们经常会遇到好多线性表,每个表的大小都是动态变化的。

当恰好有两个大小可变的表时,我们可以令他俩此消彼长,友好相处:

图中表1和表2的存储方向相反。中间的可用空间即可以给表1用,也可以给表2用。这样做的好处是使得每一个表的最大有效容量都大于可用空间的一半。除非两个表正好都满了(这很少出现)。

上面是两个表共用空间,如果是三个表及以上,情况就不一样了。

  • 两个表的时候,底部都是固定的,所有的访问都是相对于基地址进行的。
  • 而三个表或更多表的时候,大部分表的底部是不固定的,变成了相对寻址,比固定基地址寻址花费的时间更长一点点。

书中对于三个以上表的初始化和空间分配做了详细的描述,有兴趣的可以看看。

总而言之,如果让三个以上表共用空间,那么当你把相当多的项放进表中时,需要做很多的移动操作。即,顺序分配方案在空间共享上的效率不高。

链接分配

上面说了线性表一般是放在连续的存储单元中的。

下面介绍另一个更灵活的方案:每个节点记住下个节点的地址(或者叫链接)。

这里的 A B C D E 是内存中的「任意单元」(不一定连续),其中最后一项包含的地址是为空。

如果你要操作这个线性表,你只需要获取地址 A 即可。

我们把地址链接用箭头来表示:

这里的变量 First 的值是第一个节点的地址。

对比两种方案

我们来对比一下两种存储方案:

  1. 链接分配需要额外的空间存储下一个节点的地址。但是,从实际效果来看,这又不一定是个缺点。
    1. 首先,有的时候节点中的数据项永远不会占满整个单元,所以可以留几个位来存储地址信息。
    2. 其次,可以在一个节点上存储多个项,这样多个数据项只对应一个地址。
    3. 最后,链接分配更利于空间共享,因为它不需要连续的空间;而上一节我们已经发现,顺序分配方案在空间共享上面效率并不高。
  2. 从一个链接分配的表中删除一个项很容易。而对于顺序分配,删除一个项意味着要把表上大部分项移动一下。
  3. 向一个链接分配的表中插入一个项很容易。
  4. 链接分配更容易把两个表联合起来,或者把一个表切开。
  5. 链接分配方案能实现更复杂的结构,比如个数变化和大小变化的表,表中表等。
  6. 顺序分配方案的随机访问更容易。要获取第 k 项,只需要花费常数固定时间。而链接分配方案则需要迭代 k 次。即使不是随机访问,而是顺序访问,顺序分配也比链接分配快一点点。因为这是 INC1 c 和 LD1 0, 1(LINK)的差别,有些机器并不具有从一个变址单元装入一个变址寄存器的能力。

AVAIL 表(可用空间表)

当我们向往链接分配表中插入信息时,需要知道哪些空间是可用的,这通常是通过可用空间表做到的。

这个 AVAIL 表通常是一个栈,保存了所有可用空间的地址。所有可分配节点的集合叫做「存储池」。

一个程序开始时,需要初始化 AVAIL 栈:

  1. 把所有可用作链接分配的节点链接在一起组成一个表
  2. 把 AVAIL 置为表头的地址
  3. 把最后节点的下一个节点链到空地址。

如果要把 X 置为新空间的地址以供程序使用,可以进行如下操作:

X <- AVAIL, AVAIL <- LINK(AVAIL) 简记为 X <= AVAIL

其中 LINK(AVAIL) 表示获取 AVAIL 的下一个节点的链接(地址)。

当删除一块空间时:

LINK(X) <- AVAIL, AVAIL <- X

这样空间就被回收到 AVAIL 了,简记为 AVAIL <= X

可用空间不足

当操作 X <= AVAIL 时,如果 AVAIL = 空地址,则说明 overflow 了。

这是程序只能终止了。

或者,再制作一个「垃圾回收程序」,以找到更多的可用空间。

循环表

将一个链接分配表(非空)的最后节点链接到头节点,就得到了循环表。

PTR 指向表最右边的节点,那 LINK(PTR) 就是最左边节点的地址。

双向链接表

没有节点不仅包含下一个节点的链接,还包含上一个节点的链接,就得到了双重链接表。

在单向链接表中,你想获取上一个节点的地址是不方便的。而双向链接表则解决了这个问题。

至此我们已经学完 2.2 章节,下一节是 2.3 树。

未完待续,这将是一篇很长很长的文章。

关注我的掘金专栏