一般练习

1. 复习下面概念：线性表（表），基本元素集合，元素集合和序列，下标，空表，（表的）长度，顺序关系（线性关系），首元素，尾元素，前驱和后继，数据抽象的实现者和使用者，顺序表（连续表）和链接表（链表），顺序表的元素布局，索引和索引结构，容量，（元素）遍历，查找（检索），定位，加入和删除元素，尾端加入（插入）和删除，保序插入和删除，表的一体式实现和分离式实现，动态顺序表，元素存储区的增长策略（线性增长，加倍增长），元素反转和排序，链接结构，单链表（单向链接表），链接，表头变量（表头指针），空链接，链表处理的扫描模式，汇集对象，尾结点引用，循环单链表，双向链接表（双链表），循环双链表，链表反转，链表排序，Josephus问题，随机存取，顺序存取，访问的局部性，类定义的内在一致性。

2. 下面哪些事物的相关信息适合用线性表存储和管理，为什么：

a) 在银行排队等候服务的顾客

b) 书架上的一排书籍

c) 计算机桌面上的各种图标及其相关信息

d) 计算机的文件和目录（文件夹）系统

e) 个人的电话簿

f) 工厂流水线上的一系列工位

g) 个人银行账户中的多笔定期存款

h) 一辆汽车的所有部件和零件

3. 假设需要频繁地在线性表的一端插入/删除元素。如果用顺序表实现，应该用哪一端作为操作端？如果用链接表实现呢？为什么？

4. 假设线性表的一个应用场景是基于位置访问表中元素和在表的最后插入删除元素，采用哪种结构实现线性表最为合理，为什么？

5. 在某种链接表使用场景中，最常用操作是在表首元素之前插入或删除元素，在表尾元素之后插入元素。此时采用哪种实现技术最为合适？为什么？

6. 请列举出顺序表的主要缺点，如果改用链接表能否避免这些缺点？请交换两者的角色并重新考虑类似的问题。

7. 请仔细总结顺序表和链接表的特点，并设法提出一些操作场景，在其中采用一种结构比较合适而采用另一种则非常不合适。

8. 设法总结出一些设计和选择的原则，说明在什么情况下应该优先使用顺序表，在什么情况下应该优先使用链接表。

9. 请考虑两个排序序列（例如元素按 < 关系从小到大排序）的合并操作，称为归并，并设计一种算法实现这种序列的归并。分析你设计的算法，如果其复杂性不是，请修改算法使之达到（其中和是两个序列的长度）。

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是什么关系？如果不是线性关系，请设法修改实现，使之能达到线性关系。这里要求遍历方法的空间代价是。（提示：你可以考虑为了遍历而修改表的结构，只要能在遍历的最后将表结构复原。）

7. 请为单链表类定义下面几个元素删除方法，并保持其他元素的相对顺序：

a) del_minimal() 删除当时链表中的最小元素；

b) del_if(pred) 删除当前链表里所有满足谓词函数pred的元素；

c) del_duplicate() 删除表中所有重复出现的元素，也就是说，表中任何元素的第一次出现保留不动，后续与之相等的元素都删除掉。

要求这些操作的复杂度均为，其中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. 链接表里的结点都是独立存在的对象，有可能脱离原来所在的表，或者从一个表转移到另一个表。从表对象出发通过遍历，可以访问表中的每个结点（及其数据），而从一个表结点出发则无法确定它属于哪个表（或者不属于任何一个表）。请分析这个问题，考虑在什么场景下确定结点的归属问题有重要意义。考虑下面的技术：为每个结点增加一个“表指针”指向其所属的表。定义一个类实现这种表。