TAOCP|基本算法|顺序分配

传说中的计算机圣经TAOCP，虽然我自己啃完这套书不太现实，但是还是先记录自己读书的历程。本文主要记载了顺序分配的线性表的能力与局限。

在计算机中维护线性表，最简单最自然的方法是表项存放在连续位置。 (Array)

[公式]

其中

[公式]

是常量，称作基址， 是人为假定的节点X[0]的位置（实际索引从1开始）,

[公式]

是每个节点的字数（c>1时，另一种方法是把单个表划分成若干平行表，节点的每个字存在不同平行表的相同索引处）。

这种表示线性表的技术一目了然而又众所周知，但是我们不妨先考察这种简单情况。

栈

维护栈指针变量T，当栈空时，T=0，

push Y：

[公式]

pop Y：

[公式]

(在计算机内部最有效的方法是维护cT而不是T，我们这里按c=1讨论）

队列

维持两个指针F和R，当队列为空时，F=R=0，

enqueue Y：

[公式]

dequeue Y：

[公式]

，若

[公式]

,则置

[公式]

然而，如果R始终在F前（队列始终非空）,所用表项将会是无穷，因此这种方法只有在经常清空队列的情况下可行。

为了避免队列过度使用内存，可以预留M个节点，隐式安排为一个环。构成循环队列。

若

[公式]

若

[公式]

溢出

然而，这些讨论都不太现实，因为假定不会出错，例如删除时假定至少有一个节点，插入时假定存在可容纳的内存空间。因此在限定队列长度的情况下，我们假定超过队列长度为OVERFLOW,小于等于0为UNDERFLOW，此时F和R的初始值应该为1。此时伪代码变为：

[公式]

（入栈）

[公式]

[公式]

（出栈）

[公式]

[公式]

（入队）

[公式]

[公式]

[公式]

[公式]

（出队）

[公式]

[公式]

[公式]

溢出发生，应该怎么办？

我们经常遇见涉及大小动态变化的站的程序，在这种情况下，我们并不想对每个栈的容量设定最大值，因为该值通常难以预测。即使设置，也很难遇到所有栈同时填满的情况。

如果只有两个变长表，让这两个 表迎面增长，则它们可以很好地共存。然而，容易发现，没有办法在内存中存放更多的变长表，使得两个性质都得到满足：

(a)仅当所有表的总容量超过总空间时，才出现OVERFLOW

(b)每个表的底元素都有固定的位置。

如果希望满足(a），那么必须放弃条件(b），即上文中的基址不再是常数。

一个重要的特例是，变长表都是栈，由于我们只关注栈顶元素，因此完全可以像之前一样高效处理。即使发生overflow，我们也可以重新分配内存，从其他位置腾出空间。

最简单的方法

假设有n个栈，TOP[i]存储第i个栈的栈顶，BASE[i]存储第i个栈的栈底。所有的栈处于同一存储区，有

[公式]

个位置，

[公式]

for

[公式]

,

[公式]

[公式]

作为哨兵

当栈

[公式]

发生overflow时：

(a)存在k,满足

[公式]

（即上方存在空位）,找出最小的k，然后将

[公式]

到

[公式]

的内容全部上移一格

(b)存在k,满足

[公式]

（即下方存在空位）,找出最大的k，然后将

[公式]

到

[公式]

的内容全部下移一格

(c)所有的

[公式]

，

[公式]

,则放弃。

改进方法

每次重新分配内存时为多个新项腾出空间，根据上一次内存重新分配以来每个栈的改变情况，进行全面的重新分配。扬·加威克使用了

[公式]

来记录历史信息。

算法大意如下：

计算

[公式]

为剩余可用内存量，

[公式]

为内存增长量，

[公式]

为栈增长量的数组

[公式]

10%的内存被所有表平分，其余90%则根据上次分配后表的增长量按比例划分。

所有的栈计算新的基址，然后重新分配内存。顺序表的重定位过程太繁琐，暂时略过。

上述算法的平均性能还没有理论能够计算，但经验表明，存储只有半满载时，很少需要用算法来重新安排这些表，但几乎满载时，内存的上溢会非常频繁，因此当

[公式]

时，应该停止上述算法，其中阈值由程序员指定。

习题(等我自己先做几道再说）

1.[15] 在给定的队列操作（OVERFLOW版）中，一次可以插入多少项而不会上溢

2.[22] 推广队列操作，使之可以用于任意双端队列

3.[26]解释对于一个或多个循环队列表而非栈，如何修改插入/删除/重新分配算法

4.[M27]针对第一个算法，初始空间均给第n个栈，证明期望的平均移动次数为

[公式]

5.[M30] 证明扬·加威克算法对于任意m次插入/删除序列，时间复杂度为

[公式]

6.[16] 改写算法，使得下标以0为起始。