3.5表的应用
本节通过一个简单的例子展示表结构的使用。这里给出了同一个问题的几种不同实现，其中使用了不同的表结构。
3.5.1Josephus问题和基于“数组”概念的解法
Josephus问题是数据结构教材中一个常见的实例：假设有n个人围坐一圈，现在要求从第k个人开始报数，报到第m个数的人退出。然后从下一个人开始继续报数并按同样规则退出，直至所有人退出。要求按顺序输出各出列人的编号。
本节考虑第一种解决方法：基于Python的list和固定大小的“数组”概念，也就是说，在这里把list看作元素个数固定的对象，只修改元素的值，不改变表的结构（不用加入或删除元素的操作）。这相当于摆了一圈n把椅子，人可以走但椅子在那里且位置不变。基于这种设计可以有多种实现方法。下面的方法是给每个人赋予一个编号，没有人的情况用0表示，各list的元素记录这些编号。算法梗概：
初始：
建立一个包含n个人（的编号）的表。
找到第k个人，从那里开始。
处理过程中采用把相应表元素修改为0的方式表示已出列，反复做：
数m个（尚在坐的）人，遇到表的末端就转回下标0继续。
把表示第m个人的表元素修改为0。
n个人出列即结束。
下面算法里用i表示数组下标，其初值取k-1，内层循环中每次加一并通过取模n保持i的取值范围正确。大循环一次迭代出列一人，共计执行n次迭代。循环体里的count计数直至m（通过内层循环），计数中跳过空椅子。其他部分都很容易理解。
def josephus_A(n, k, m):
people = list(range(1, n+1))
i = k-1
for num in range(n):
count = 0
while count < m:
if people[i] > 0:
count += 1
if count == m:
print(people[i], end="")
people[i] = 0
i = (i+1) % n
if num < n-1:
print(", ", end="")
else:
print("")
return
这里函数名中的A表示数组实现。函数的使用实例如下：
josephus_A(10, 2, 7)
定义这个函数的主要麻烦是表下标的（循环）计数i和表中有效元素的计数count相互脱节。计数变量count达到m时输出表元素下标i，并将该元素置0，表示这个人已经出列。输出了最后一个元素后让print输出一个换行符。
这个算法的复杂度不容易分析。内层循环的总迭代次数是i加1的次数，应该与n和m有关，因为m影响到找到下一元素的操作步数。考虑两个特殊情况：
当m＝1时，每次内循环只执行一次迭代，总的时间开销是O(n)。
当m＝n时，先考虑计算到最后表中只剩一个元素的情况。不难看到，内层循环需要遍历整个表n遍，每一遍只能把count的值加1，因此，为了删除这个元素，花费的时间就是O(n2)。整个计算中i加1的次数大约是
可见这个算法分析中的麻烦，这里不进一步讨论了。
3.5.2基于顺序表的解
现在考虑另一个算法：把保存人员编号的list按表的方式处理，一旦确定了应该退出的人，就将表示其编号的表元素从表中删除。
这样，随着计算的进行，所用的表将变得越来越短。下面用num表示表的长度，每退出一人，表的长度num减一，至表长度为0时计算工作结束。采用这种想法和设计，表中的元素全是有效元素（不再出现表示没人的0），元素计数与下标计数得到统一，所以下标更新可以用i=(i+m-1)%num统一描述。
基于这些想法写出的程序非常简单：
def josephus_L(n, k, m):
people = list(range(1, n+1))
num, i = n, k-1
for num in range(n, 0, -1):
i = (i + m-1) % num
print(people.pop(i),
end=(", " if num > 1 else "\n"))
return
函数体是一个简单的循环计数，很容易理解。其中用list的pop操作删除元素。最后的输出语句值得说一下，其中用了一个条件表达式确定一次输出的结束字符串：如果整个计算还没完成（num的值大于1时），就在输出了出列人的编号后加上一个逗号；如果所有人的编号都已输出，就输出一个换行符。
函数调用的形式与前一函数相同，如：josephus_L(10, 2, 7)。
这个算法的复杂度比较容易考虑。虽然函数循环只执行n次，但由于输出语句调用了list的pop操作，它需要线性时间，所以算法复杂度是O(n2)。由于这里直接加m计算位置，所以算法的复杂度与m无关。
3.5.3基于循环单链表的解
现在考虑基于循环单链表实现一个算法。
从形式上看，循环单链表可以很直观地表示围坐一圈的人，顺序数人头可以自然地反映为在循环表中沿着next链扫描，一个人退出可以用删除相应结点的操作模拟。在这样做之后，又可以沿着原方向继续数人头了。
根据上面分析，这个算法应该分为两个阶段：
1）建立包含指定个数（和内容）的结点的循环单链表，这件事可以通过从空表出发，在尾部逐个加入元素的方式完成。
2）循环计数，找到并删除应该退出的结点。
具体实现可以有多种方式，例如：为原循环单链表增加一个循环数数的函数，然后写一段程序建立所需的循环单链表，并完成操作。下面的实现采用了另一种方式，即基于循环单链表类派生出一个专门的类，用其初始化方法完成全部工作。
派生类Josephus的实现中没有增加“当前人指针”一类设置，采用了另一种考虑，把计数过程看作人圈的转动（结点环的转动）。这个类里定义了新方法turn，它将循环表对象的rear指针沿next方向移m步（相当于结点环旋转）。
这个类的初始化函数首先调用基类LCList的初始化函数建立一个空表，然后通过一个循环建立包含n个结点和相应数据的初始循环表。最后的循环反复调用turn方法，找到并逐个弹出结点，输出结点里保存的编号。
class Josephus(LCList):
def turn(self, m):
for i in range(m):
self._rear = self._rear.next
def __init__(self, n, k, m):
LCList.__init__(self)
for i in range(n):
self.append(i+1)
self.turn(k-1)
while not self.is_empty():
self.turn(m-1)
print(self.pop(),
end=("\n" if self.is_empty() else ", "))
虽然这里用了一个类作为基础，其使用的方式却与调用一个函数类似，建立这个类的对象就是完成一次计算，如Josephus(10, 2, 7)。所创建对象本身并不重要。
这个算法的时间复杂度比较容易考虑：建立初始表的复杂度是O(n)，后面循环的算法复杂度为O(m×n)，因为总共做了m×n次一步旋转，每次是O(1)。
本章总结
本章讨论了线性表的概念、其基本运算和抽象数据类型，以及两种实现技术（顺序表和链接表实现）。线性表是一种比较简单的数据结构，是n个数据元素的有限序列，各元素在表中有特定的排列位置和前后顺序关系。
顺序表
在线性表的顺序存储实现（顺序表）中，元素存储在一块大存储区里，它们之间的逻辑顺序关系通过实际存储位置直接反映。顺序表里只需要存放数据元素本身的信息，因此存储密度大，空间利用率高。另外，元素的存储位置可以基于下标通过简单的算式算出，因此可以在O(1) 时间内随机存取。这些是顺序存储结构的优点。
另一方面，由于采用连续方式存储元素，顺序表技术的灵活性不足。为了有效支持元素的插入和删除，顺序表中需要预留一些空闲的空间。如果顺序表的长度变化较大，通常需要按最大需要安排存储空间。这些情况带来的空置存储位置也形成额外的存储开销。此外，在顺序表里插入和删除都可能需要移动许多元素，操作的代价通常都比较高。这些是线性表顺序存储结构的缺点。特殊情况是表的尾端插入和删除为O(1)操作。
由于采用连续方式存储元素，需要首先安排确定大小的存储空间。这样，如果程序运行中不断加入元素，最终会填满整个元素空间，这时再插入元素的操作就无法完成了。动态顺序表技术可以解决这个问题，避免由于表满而导致程序被迫终止。采用这种技术出现了一个新问题：原本高效的后端插入操作，也可能由于扩存而比较耗时。这种偶发的情况可能影响程序的行为，在开发对时间效率要求高的程序时，需要特别注意。另一情况是扩存策略，需要在平均操作效率和闲置存储量之间权衡。
链接表
在链接实现（链接表）里，表元素保存在一批较小的存储块里，通过显式的链接将这些块连成一串，形成一种链式结构。结点的链接结构直接反映元素的顺序关系。
在链接表中，表元素之间的顺序由它们所在的结点之间的链接显式表示，因此表结点可以任意安排位置，灵活地调整结构，通过调整链接完成表元素的插入、删除和各种重整顺序的操作。这些情况说明，链接表实现的灵活性较强，操作的实现方式更加灵活多样。对于一些应用，这种灵活性是非常重要的。
也应该看到另一些情况。为了实现链接表，每个结点都需要增加一个链接域，付出额外的存储空间代价。但是表中并不需要预留空闲位置，有多少元素就建立多少结点。对于一个链表，能直接掌握的只是其中一两个结点（首结点，以及可能的尾结点），要访问其他结点，只能顺着链接一步步去查找。因此链表中的元素不能随机访问，按位置访问的代价很高。由于这种情况，使用链表的最合理方式是前端操作和按元素顺序访问。增加了尾结点引用后，可以支持受限的后端操作，包括表元素访问和新元素插入，但不包括删除。引入相反方向的链接（双链表的前向链接），可以增加一种数据访问顺序，也使表中间结点的操作更加方便，但并没有改变链接表的本质。
链表的另一个特点是存在很多变形。为突破简单单链表带来的操作限制，可以引入尾结点指针，建立循环链接，或者为每个结点增加一个反向链接（形成双链表）。每种变形都能使一些操作的实现更直接，提高操作的效率；但要付出存储的代价，也给一些操作的实现带来新问题，如尾指针的维护、前向链接的维护等。
讨论
实际上，顺序表与链接表并不是决然相对的两种技术。本章讨论的链接表采用一个结点里存放一个表元素的方式，是最常见的方式，也是一种极端的安排。实际上，完全可以在一个链接结点里存储多个表元素，形成连续存储和链接存储的一种混合形式。从这个角度看，顺序表也是链接表的一种特殊形式，这种链接表只有一个结点，所有表元素都保存在这个结点里。回忆一下图3.6的分离式实现，情况可以看得很清楚。
顺序表的另一个优点是访问的局部性。表元素顺序映射到内存中连续的单元里，下一个元素的实际存储位置与当前元素很近。由于目前各种新型计算机体系结构的特点，顺序访问内存中相近位置的效率比较高，而真正的随机内存访问效率较低。对于链接表，逻辑上的下一个结点可能被安排在内存中的任何位置，逻辑上的顺序访问实际上可能是对计算机内存中许多不同地方的随机访问，效率比较低。
另一方面，顺序表需要较大的连续空间，这一情况有时也会带来问题。如果需要建立保存很多元素的巨大的表，采用顺序表可能给Python解释器的存储管理带来麻烦。链接表的结点是小块存储，无论表有多么大，存储管理问题都容易处理。
如前所述，顺序结构和链接结构是程序里构造复杂数据结构的两种基本技术，顺序表和链接表是这两种技术的典型代表。对这两种表的操作技术也是最典型的复杂数据结构操作技术，以及最重要的设计和编程技术。通过对这两种表结构的操作练习，能够大大提升初学者的编程水平。本章学习的一个重点是链接表操作，这是高级编程技术的一个难点，也是（几乎）一切高级编程技术的基础。
此外，本章内容还展示了一些重要的面向对象编程技术，讨论了如何通过继承已有的类构造新的具有类似功能（或结构）的类，以满足实际需要。
练习
一般练习
1.复习下面概念：线性表（表），基本元素集合，元素集合和序列，下标，空表，（表的）长度，顺序关系（线性关系），首元素，尾元素，前驱和后继，数据抽象的实现者和使用者，顺序表（连续表）和链接表（链表），顺序表的元素布局，索引和索引结构，容量，（元素）遍历，查找（检索），定位，加入和删除元素，尾端加入（插入）和删除，保序插入和删除，表的一体式实现和分离式实现，动态顺序表，元素存储区的增长策略（线性增长，加倍增长），元素反转和排序，链接结构，单链表（单向链接表），链接，表头变量（表头指针），空链接，链表处理的扫描模式，汇集对象，尾结点引用，循环单链表，双向链接表（双链表），循环双链表，链表反转，链表排序，Josephus问题，随机存取，顺序存取，访问的局部性，类定义的内在一致性。
2.下面哪些事物的相关信息适合用线性表存储和管理，为什么？
a）在银行排队等候服务的顾客；
b）书架上的一排书籍；
c）计算机桌面上的各种图标及其相关信息；
d）计算机的文件和目录（文件夹）系统；
e）个人的电话簿；
f）工厂流水线上的一系列工位；
g）个人银行账户中的多笔定期存款；
h）一辆汽车的所有部件和零件。
3.假设需要频繁地在线性表的一端插入/删除元素。如果用顺序表实现，应该用哪一端作为操作端？如果用链接表实现呢？为什么？
4.假设线性表的一个应用场景是基于位置访问表中元素和在表的最后插入/删除元素，采用哪种结构实现线性表最为合理，为什么？
5.在某种链接表使用场景中，最常用操作是在表首元素之前插入或删除元素，以及在表尾元素之后插入元素。此时采用哪种实现技术最为合适？为什么？
6.请列举出顺序表的主要缺点，如果改用链接表能否避免这些缺点？请交换两者的角色并重新考虑类似的问题。
7.请仔细总结顺序表和链接表的特点，并设法提出一些操作场景，在其中采用一种结构比较合适而采用另一种则非常不合适。
8.设法总结出一些设计和选择的原则，说明在什么情况下应该优先使用顺序表，在什么情况下应该优先使用链接表。
9.请考虑两个排序序列（例如元素按“＜”关系从小到大排序）的合并操作，称为归并，并设计一种算法实现这种序列的归并。分析你设计的算法，如果其复杂性不是O(max(m, n))，请修改算法使之达到O(max(m, n))（其中m和n是两个序列的长度）。
10.请从操作实现的方便性和效率的角度比较带尾结点指针的单链表和循环单链表，以及它们相对于简单单链表的优点和缺点等，并总结在什么情况下应该使用这两种结构，或应优先使用其中某一种。
11.请全面比较循环单链表和双链表的各方面特点。
编程练习
1.检查本章开始定义的线性表抽象数据类型和3.3节定义的链表类LList，给LList加入在抽象数据类型中有定义，但LList类没定义的所有操作。
2.请为LList类增加定位（给定顺序位置的）插入和删除操作。
3.给LList增加一个元素计数值域num，并修改类中操作，维护这个计数值。另外定义一个求表中元素个数的len函数。Python的内置标准函数len可以自动调用用户定义类里的相关函数__len__，也可以用它作为方法名。请比较这种实现和原来没有元素计数值域的实现，说明两者各自的优缺点。
4.请基于元素相等操作“==”定义一个单链表的相等比较函数。另请基于字典序的概念，为链接表定义大于、小于、大于等于和小于等于判断。
5.请为链接表定义一个方法，它基于一个顺序表参数构造一个链接表；另请定义一个函数，它从一个链接表构造出一个顺序表。
6.请为单链表类增加一个反向遍历方法rev_visit(self, op)，它能按从后向前的顺序把操作op逐个作用于表中元素。你定义的方法在整个遍历中访问结点的总次数与表长度n是什么关系？如果不是线性关系，请设法修改实现，使之达到线性关系。这里要求遍历方法的空间代价是O(1)。（提示：你可以考虑为了遍历而修改表的结构，只要能在遍历的最后将表结构复原。）
7.请为单链表类定义下面几个元素删除方法，并保持其他元素的相对顺序：
a）del_minimal()删除当时链表中的最小元素；
b）del_if(pred)删除当前链表里所有满足谓词函数pred的元素；
c）del_duplicate()删除表中所有重复出现的元素。也就是说，表中任何元素的第一次出现保留不动，后续与之相等的元素都删除。
要求这些操作的复杂度均为O(n)，其中n为表长。
8.请为单链表类定义一个变动方法interleaving(self, another)，它把另一个单链表another的元素交错地加入本单链表。也就是说，结果单链表中的元素是其原有元素与单链表another中元素的一一交错的序列。如果某个表更长，其剩余元素应位于修改后的单链表的最后。
9.考虑实现单链表插入排序的另一个想法：插入排序也就是把要排序的元素一个个按序插入到一个元素已经排好序的链表里，从空链表开始。请根据这个想法实现另一个完成单链表排序的插入排序函数。
10.定义一个单链表剖分函数partition(lst, pred)，其参数为单链表lst和谓词函数pred，函数partition返回一对单链表（一个序对），其中第一个单链表包含着原链表lst里所有值满足pred的结点，第二个链表里是所有其他结点。注意，两个表里的结点还应保持原表里结点的相对顺序。也就是说，如果在某结果表里结点a的后继结点是b，在原表lst里a一定位于b之前。
11.扩充本章给出的循环单链表类CLList，实现LList1中有定义的所有方法。
12.请为循环单链表类扩充一个方法interleaving(self, another)，要求见上面针对简单单链表的有关习题。
13.请为循环单链表类定义前面各习题中针对简单单链表类提出的方法。
14.请基于Python的list实现一个元素排序的顺序表类，其中元素按“＜”关系从小到大排序存放。考虑需要定义的方法并给出定义，包括一个方法merge(self, another)，其参数another是另一个排序顺序表。该方法将another的元素加入本顺序表，并保证结果表中的数据仍是正确排序的。
15.请从简单单链表类派生一个排序单链表类，表中元素按“＜”关系从小到大排序存放。首先考虑需要覆盖的方法并给出定义。为该类增加方法merge(self, another)，参数another也是排序单链表。该方法将链表another的元素加入本链表，并保证结果链表中的数据仍是正确排序的。
16.请为双链表类定义reverse方法和sort方法，要求通过搬移结点中数据的方式实现这两个操作。
17.请为双链表类定义reverse1方法和sort1方法，要求操作中不移动结点中的数据，只修改结点之间的链接。
18.实现双链表排序的一种可能做法是直接利用单链表的排序函数，只将结点按next方向正确排序链接，最后重新建立prev链接关系。请基于这个想法为双链表类实现一个排序方法，其中直接调用单链表类的插入排序方法。
19.请实现一个循环双链表类。
20.请考虑一种在一个结点里存储16个元素的单向链接表，定义一个类实现这种链表，为这个类定义各种重要的线性表操作。请从各方面比较这种实现与每个结点存储一个元素的简单实现。
21.利用（顺序或链接）表和第2章的人事记录类，实现一个简单的学校人事管理系统。首先分析问题，描述一个人事管理ADT，而后实现这个系统。由于不需生成多个实例，可以用类的数据属性保存人事信息（的表），用一组类方法实现必要操作。这是一种在Python语言中建立单例（singleton）数据抽象的技术。
22.利用链接表实现一种大整数类BigInt。用一个链表表示一个大整数，表中每个结点保存一位十进制整数，这样，任意长的链表就可以保存任意长的整数了。请实现这种大整数的各种重要运算。
23.链接表里的结点都是独立存在的对象，有可能脱离原来所在的表，或者从一个表转移到另一个表。从表对象出发通过遍历可以访问表中的每个结点（及其数据），而从一个表结点出发则无法确定它属于哪个表（或者不属于任何一个表）。请分析这个问题，考虑在什么场景下确定结点的归属问题有重要意义。考虑下面的技术：为每个结点增加一个“表指针”指向其所属的表。定义一个类实现这种表。