《按索引访问集合的3种算法》由会员分享，可在线阅读，更多相关《按索引访问集合的3种算法（4页珍藏版）》请在金锄头文库上搜索。
1、1 按索引访问集合下面是按索引访问集合的3种算法，看懂3种算法，按要求编程。1.1 基于数组的算法分析使用一个数组来描述集合，需要把集合中的每个元素映射到数组的具体位置上。下面我们用一个数学公式来确定每个元素的位置。一个简单的映射公式如下：location(i)=i-1 (2-1)公式(2-1)指明集合中第i个元素（如果存在的话）位于数组中i-1位置处。为了完整的描述集合，使用变量length作为集合的长度。在这种数据结构中，搜索一个元素只需根据公式(2-1)进行映射就能实现，其平均时间复杂度是O (1)，性能非常理想。为了在集合中删除第k个元素，需要首先确认集合中包含了第k个元素（如果不存在
2、第k个元素，则引发一个异常），将元素k+1，k+2，length依次向前移动一个位置，并将length的值减1，从而删除第k个元素。删除操作的平均时间复杂度为O(length)。为了在集合中第k个元素后面插入一个新元素，首先要把k+1至length元素往后移动一个位置，然后把新元素插入到k+1位置处。插入操作的平均时间复杂度为O(length)。此外，插入操作是，如果数组已经满了，则会引发一个异常。采用数组来描述一个集合实现起来非常简单。执行搜索的平均时间复杂度为常数，非常理想。执行删除和插入的时候，有一个和集合的大小呈线性关系的平均时间复杂度，在大部分情况下也是可以接受的。利用数组来描述集合
3、，使用在删除和插入操作少，搜索操作多的场合有非常优异的表现。但是，这种描述方法有一个非常大的缺点是空间的低効利用。必须要预测集合的最大可能尺寸，根据最大可能尺寸分配数组。考察如下情况，我们需要一个集合，它的最大可能尺寸是5000，但平均尺寸只有100，那么空间的利用率就只有2。在实际应用中，可能发生的情况会比这更极端。1.2 基于链表的算法分析在链表描述中，集合中的元素都放在链表的节点中进行描述。链表中的节点不是一个数组元素，因此不能通过公式来映射定位某个元素。取而代之的是，每个节点中都包含了下一个节点的位置信息，链表的表头包含了第一个节点的位置信息。为了在集合中找到第k个元素，就必须从表头开
4、始，遍历第1个到第k个节点。它的时间复杂度是O(k)，平均时间复杂度为O(length)。为了在集合中删除第k个元素，就要先找到第k-1和第k个节点，使第k-1个节点的下一个节点位置信息指向第k+1个节点，然后释放第k个节点所占的空间。它的时间复杂度是O(k)，平均时间复杂度为O(length)。插入和删除的过程很相似，首先要创建一个新的节点，然后找到第k-1个节点，在该节点的后面插入新的节点，并把第k-1个节点、新的节点的下一个节点位置信息进行适当设置。它的时间复杂度是O(k)，平均时间复杂度为O(length)。采用数组描述方法的集合仅需要能够保存所有元素的空间以及保存集合最大尺寸所需要的
5、空间。链表描述需要除集合元素本身的空间意外，还需要额外的空间，用例保存链接节点指向下一个节点位置的指针。但一般情况下，链表描述要比数值描述的空间利用率高得多。虽然数组描述、链表描述插入和删除操作的平均时间复杂度均为O(length)，但由于移动元素的操作比遍历元素的操作的开销要大得多，所以采用链表描述所实现的插入和删除操作要比数组描述执行得更快。而采用数组描述可以在常数时间内访问第k个元素，而在链表中，这种操作所需要的时间是O(k)。1.3 多级索引算法在链表描述的具有length个元素的集合中进行搜索，至多需要length次访问节点。如果在链的中部节点加一个指针，并记录头部到中部的距离，则访
6、问的节点数可以减少到n/2+1次。搜索时，首先将欲搜索的索引与头部到中部的距离进行比较，如果欲搜索的索引较小，则仅需搜索链表的左半部，否则，只要从中部开始搜索右半部。图3-1a的链表中有七个元素。该链表有一个头节点和一个尾节点。节点中的数表示该节点的索引值。如果要访问索引值为7的节点，对该链表的搜索要进行七次。在图3-1b中，增加了一个头部到中部的指针，指针上的数字表示头部到中部的距离。采用图3-1b中的办法，可以把最坏情况下的比较次数减为四次。搜索一个索引时，首先将它与头部到中间的距离进行比较，然后根据得到的结果，或者在链的左半部搜索或者在链的右半部搜索。如果在链表的左半部分和右半部分的中间
7、节点再增加一个指针，可以进一步减少最坏情况下的搜索比较次数。如图3-1c，在该图中有三条链。0级链就是图3-1a中的初始链，包括了所有的七个元素。1级链包括了第2、4、6个元素，而2级链只包括了第4个元素。寻找某一个索引指定的元素时，只需要在2级链上比较一次，根据比较结果，在1级链上比较一次，最后在0级链上找出所需的元素。采用图3-1c中的3级链表结构，允许在链表中进行折半查找，对所有的索引至多需要3次比较。对一个有n个元素的多级链接结构来说，0级链包括全部的n个节点，1级链包括n/2个节点，2级链包括n/4个节点，而每2i个元素有一个i级链指针。当且仅当一个节点在0i级链上，但不在i+1级链
8、上时，我们就称该节点是i级链节点。在图3-1c中，索引为4的节点是2级链上的唯一节点，而索引为6的节点是1级链节点。图3-1c所示的结构称为多级链表结构。在该结构中，有一组有层次的链，通过这中有层次的链，实现折半查找。在进行插入和删除操作时，要完整保持图3-1c的结构，必须耗时O(n)。如果可以采取适当放宽结构，只要使得在删除和插入后尽量逼近图3-1c的结构就可以降低保持结构的开销。在这种结构只能管，有n/2i个节点为i级链节点，所以我们可以认为在进行插入时，新节点属于i级链的概率为1/2i。在确定新节点的级时，应考虑各种可能的情况。因此，把新节点作为i级链的可能性定为pi。图3-1c中，p=
9、0.5。假设要在索引6的位置插入一个新的节点，首先要在链中找到索引为5和6的节点，然后在0级链上插入这个新的节点。接下来，要为新节点分配一个级，分配过程由随机数来确定。若新节点为i级链元素，那么，把这个节点分别插入到1i级链中。最后，调整每一级链上新的节点左边节点到下一节点的距离。如图3-1d所示，虚线的为新插入的节点。1234657图3-1a441234657图3-1b4412346572222图3-1c222254175643218图3-1d删除操作和插入操作类似，当删除一个节点时，必须要把这个节点从它的所有级别链上删除，同时调整该节点左边的节点到下一个节点的距离。关于级的分配，前面已经说
10、到，新节点作为i级链的可能性为pi。换种思路，可以认为i1级链中的节点属于i级链的概率为p。假设有一随机数产生器所产生的数在0到RAND_MAX之间。则下一次所产生的随机数小于等于CutOff=p*RAND_MAX的概率为p。因此，若下一随机术小于等于CutOff，则新节点应在1级链上。接下来确定新节点是否在2级链上。重复这个过程，直到一随机数大于CutOff为止。以下是确定节点的级的分配的代码int level=0;while (rand()=CutOff) level+;这种方法潜在的缺点是可能为某些节点分配特别大的级。为避免这种情况，可以设定新节点的级不大于链上已有节点的最大级加1。问题：任选一种语言，分别写出这3种算法的检索、插入和删除操作的函数。2 快速排序快速排序法的基本原理是：在数组中选一个支点（通常会选第一个元素），然后把数组的n个元素分成三段：左段是小于等于支点的元素，中段就是支点一个元素，右段是大于等于支点的元素。然后再对左段和右段分别排序。问题：任选一种语言，写出快速排序算法。快速排序在最坏的情况下，会退化成冒泡排序，请说明有什么办法能减少这种情况的出现。3 待遇问题：写下你对待遇的要求。
