阅读 ‧ 电子书库

17.6　链表与数组

很多编程问题，比如创建一个列表或队列，可以用链表（一种动态分配的结构序列链）或数组来处理。每种形式都有其优势和缺点，所以要根据具体问题的需求来决定选择哪一种形式。表17.3总结了链表和数组的性质。

表17.3　比较数组和链表

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

我们仔细研究插入和删除元素的过程。向数组中插入一个元素，必须移动其他元素以便安插新元素，如图17.9所示。新元素离数组头越近，要移动的元素越多。而向链表插入一个节点，只需分配两个指针值，如图17.10所示。类似地，从数组中删除一个元素要重新安置大量元素，而从链表中删除一个节点只需重新设置一个指针并释放被删除节点使用的内存。

图17.9　向数组中插入一个元素

图17.10　向链表中插入一个元素

其次，考虑如何访问列表中的成员。对数组来说，可以用数组索引直接访问任意元素。这被称为随机访问（random access）。对链表来说，必须从列表头开始，逐个节点地移动到所需的节点处，这叫做顺序访问（sequential access）。数组也可以顺序访问。只要在数组中按顺序使数组索引递增即可。在某些情况下，顺序访问就足够了。比如，如果要显示列表中的每一个项目，顺序访问就很不错。另外一些情况下随机访问更受欢迎，下面您会看到。

假设要在列表中搜索一个特定的项目。一种算法是从列表头开始顺序搜索列表,这被称为顺序搜索（sequential search）。如果项目并非以某种顺序排列，您只能使用顺序搜索。如果要搜索的项目不在列表里，您得查找完所有的项目才能得出该项目不在列表中的结论。

图17.11　以折半搜索法查找Susan

可以通过先对列表排序来改进顺序搜索。这样的话,当碰到一个排在待找项目后的项目时还未找到您要搜索的项目，就可以终止搜索了。例如，假设您在一个按字母排序的列表中查找Susan。从列表头开始查找每一个项目，最后碰到了Sylvia，而此时还没找到Susan。这时可以退出搜索了，因为如果Susan在列表里的话，它将在Sylvia之前。平均来讲，这种方法将会使查找不在列表中的项目的时间减半。

对于一个排序的列表，使用折半搜索（binary search）会比顺序搜索好得多。下面是其工作方法。首先，称您要搜索的列表项目为目标项（goal），并假设列表是按字母排序的。然后，把列表的中间项和目标项进行比较。如果两者相等，搜索结束。如果该中间项的字母比目标项靠前，则目标项若在列表中，一定在后一半。如果中间项的字母比目标项靠后，则目标项一定在前一半。任一种情况下，比较结果决定了下次搜索将在半个列表进行。而后，再次应用这种方法。即，选择剩下一半列表的中间项，同样，该方法或者找到目标项或者规定剩下列表的一半作为下次搜索的范围。照这样进行下去，直到找到目标项或排除整个列表（请参见图17.11）。这种方法非常有效率。假如列表有127个项目那么长。顺序搜索平均要做64次比较才能找到目标项或得知其不存在。而折半搜索只需最多7次比较。第一次比较排除到剩下63种可能，第二次比较排除到还剩31种可能，如此下去，直到第6次比较后只剩下一种可能。第7次比较决定剩下的这个是否是目标项。一般地，n次比较能处理具有2n－1个成员的数组，所以列表越长越能体现出折半搜索的优势。

用数组实现折半搜索是很简单的，因为可以用数组索引决定任何数组或部分数组的中点。只要把数组的第一个和最后一个元素的索引相加再除以2即可。例如，在一个有100个元素的列表中，第一个索引为0，最后一个索引为99,则首次猜测应为（0+99）/2，即49（整数除法）。如果索引为49的元素与目标项相比在字母表中太靠后，则正确的选择应在0到48范围内，所以下一次猜测应为（0+48）/2，即24。如果索引为24的元素在字母表中又太靠前了，则下一次的猜测应为（25+48）/2,即36。这就是数组的随机访问特性的体现。它使您能从一个位置直接跳到另一个而不需访问两者之间的每一个位置。而链表只支持顺序访问，不能提供直接跳到列表中点的手段，所以在链表中不能使用折半搜索。

这样的话可以看到，选择何种数据类型是取决于具体问题的。如果列表需要频繁地插入和删除元素因而不断地调整大小，并且不需要经常搜索，链表是更好的选择。而如果列表基本稳定只是偶尔插入或删除一些元素，但却需要经常搜索，则数组是更好的选择。

可是如果您需要的是一种既支持频繁地插入和删除元素又支持频繁搜索的数据类型，链表和数组都不是针对这个目标的理想选择。另一种形式，二叉搜索树，可能正是您所需要的。