用舍伍德算法实现线性表的快速查找

1、学生学号104972101535论文成绩武汉理工大学研究生课程论文课程名称 算法设计与分析 论文题目 用舍伍德算法实现线性表的快速查找专业班级 软件工程101 学生姓名 王洪洋 任课老师 夏红霞 2010 2011 学年 第 二 学期摘要：舍伍德算法是概率算法的一种，该文在比较线悱表的顺序存储与链式存储的特点之后，提出了一种较优的数据结构用数组模拟链袁。理论上证明了采用舍伍德算法进行查找运算的时间复杂度为0(n)，),并在计算机上给出相应数据的模拟。关键词：舍伍德算法；概率算法；查找abstract:sherwood algorithm is a kind of probability alg

2、orithm. after comparing characteristic of linear list stored by sequential array and single inked fist. the paper puts forward a data structure一一linked list simulating by array. and it proves that time complexity of search operation is 0(n) by it in theory. at last，the paper gives some data testing

3、in computerkey words: sherwood algorithm；probability algorithm; search前言：所谓概率算法，就是在算法的过程中引入随机数，使得算法在执行的过程中随机选择下一个计算步骤。很多算法的每一个计算步骤都是固定的，而概率算法允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。概率算法的特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果(时间和结果)。正文：l舍伍德算法设a是一个确定性算法，当它的输入实例为

4、x时所需的计算时间记为ta(x)。设xn是算法a的输入规模为n的实例的全体，则当问题的输入规模为n时，算法a所需的平均时间为这显然不能排除存在xxn使得 的可能性。希望获得一个概率算法b，使得对问题的输入规模为n的每一个实例均有这就是舍伍德算法设计的基本思想。当s(n)与ta(n)相比可忽略时，舍伍德算法可获得很好的平均性能。概率算法的一个特征是对同一实例用同概率算法求解两次可能得到完全不同的结果。这两次求解可能会得到相当大的差别。概率算法大致有4类：数值概率算法，蒙特r罗算法，拉斯维加斯算法和舍伍德算法。本文采用舍伍德算法来求解。舍伍德算法总能求得闷题的一个解，且所求的解总是正确韵。当一个确

5、定性算法在最坏情况下的计算复杂性与在平均情况下的计算复杂性的较大差别时，可在这个确定性算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例悯的这种差别。该算法的精髓1：足避免算法的最坏情况行为，而足没法消除这种最坏情况行为与特定实例之间的关联性。2线性袁的组织在现实世界中，线性表的倒子枚不胜举，如一幅扑克牌的点数(2,3,4，,j，q，k，a)可构成一个线性表；数据库表中的记录也可以构成一个线性表，只不过是该线性表中的数据元索稍复杂一点罢了。正因为线性表如此重要，ansl和iso于1998年制定的stl(standard template library)中提供了对线性表的支持。

6、stl的容器是用来防止各种类型的对象，其中每一个容器类就是计算机的一个基本数据结构。stl有以下7个最基本的容器类：向照(vector)，列表(list)，双端队列(deque)，集合(set)，多重集合(multiset)，映像(map)，多重映像(multimap)等。线性表的存储有两种方式：顺序存储和链式存储。从空问的角度看，链式存储的存储密度低，因为它需要存储附加的指针域的数据。而顺序存储不需要存储附加信息，因而存储效率比较高；从时间角度来看，由于顺序存储的逻辑顺序与物理顺序一致，其存储可采用其索引号来加以存取，因此是一种随机存取结构，表中的任意一个结点都可在o(1)的时间内直接存取，

7、但是在表中插入和删除元索时耍移动大量的元素，该结构适合经常进行查找，很少做插入和删除运算操作的场台。而链式存储与它恰恰相反，插入和删除不需要移动元素，只需要修改指针即可，但其查找的时间复杂度却为o(n)在stl中容器类中的vector类采用顺序存储，list类采用链式存储。后面的程序测试就是采用这两个类来进行的。有没有这样的一个数据结构，即能像链式存错储结构那样，插入和删除不需移动大量元素，在查找时也能像顺序存储结构相似，不会比较报多的数据?况且在一些不包含指针的程序设计语音如java和vb中，如何实现链式存储结构呢?3数组实现链表在不包含指针的程序没汁语言如vb中，可以采用数组来实现链表，实

8、现了“虚假”的指针操作。但就是这种“虚假”指针，恰恰不仅弥补某些指针的某些缺结，还发挥了这种“虚假”指针的优点。采用这种数据结构，抛弃了顺序存储在插入运算中需要移动大量元素的缺点。采用这种数据结构，利用,舍伍德算法进行查找、插入和删除操作，其效率在传统的顺序存储和链式存储之间。在所有的程序设计语言中都有数组，可以利用两个数组m_pdata和m_plink来表示所给的含有多个元素的有序集。用m_pdata存储有序链表的数据，用m_plink存储有序链表的数据元索的直接后继的指针(在数组中的索引号)。m_plinko指向有序链表的第一个元素，换句话说，m_pdatam_plink0是有序链表中的最

9、小元素。一般来说，如果m_pdatai】是有序链表中的第k个元素，则m_pdatam_plinki是有序链表中的第k+1个元素。有序链表的有序性表现在：对于任意的iin，有m_pdataim_pdatam_plinki。有序链表中的最大元素m_pdatak有m_plinkk-o(无后继，指向第零个结点，第零个结点是监视哨)且m_pdaia0为一个大数。 倘若采用顺序搜索的方式在这种有序链表中查找指定的元素，每次查找与有序链表建立的顺序有关，此时采用舍伍德算法可以消除这种联系。利用数组下标的索引性质，可以设计一个随机化的搜索算法，以改进搜索的时间复杂性。该算法的基本思想是随机选取数组元素若干次，

10、从较接近搜索元素x的位置开始进行顺序查找，而没有必要从有序链表的开始位置进行搜索，从而较大幅度地提高查找效率。遗憾的是在stl容器类中的voctor类采用顺序存储，list类采用链式存储，并没有这样的一种数据结构一用数组模拟有序链表。模仿标准stl中的类模板的实现，我们编制了一个类模板corderlist，并实现了用舍伍德算法进行查找、插入等算法。4用类模板实现算法用类模板实现的算法如下：templatebool corderlist：search(type x, int&index)/搜索有序链袭中的指定元素x、并将其位置放在index变量中/m cnrrentnumber为当前有序链表中元

11、素的个数，它为类模/板corderlisl的数据成员,m为随机搜索的次数；int m=(int)sqrt(double(m_curmntnumber);int j;index=o;/m_lowbound为当前有序链表中最小元素的值它为类模板/corderlist的数据成员;type max=m_lowbound;for(int i=l；i=m，i+j=randl( );/产生一个随机数j，在数组m_pdata随机中找一个值type y-mpdatau：if(maxy)&(yx)/找最靠近查找元素x的索引位置indexmax=y；index=j；/从最靠近查找元素x的index所指向的位置升妯进

12、行顺序搜索while(m_pdatam_plinkindexx)index=m_plinkindex；指针后移return(n_pdatam_plinkindcx=x)；/是否找到5程序测试利用vc6.0编制程序，测试其查找几十万个元素用不同的算法所需要的运行时问(机器为赛扬633内存128mb)，结果如表1所示。表1 数组模拟有序链表的查找时间万个元素算法1020304050舍伍德算法（s）12345顺序查找顺序表(s)48 131821顺序查找链式表(s)48121620 6结束语采用数组模拟有序链表，它本质上是利用两个数组，一个存储数据，一个存储其后继在数组中的位置，对于查找指定元素，采用舍伍德算法可在0(n1/2)时间内完成，采用顺序存储结构时，若数组元素无序，则只能顺序查找，需o(n)时间，若数组元素有序，可进行二分法查找，其时问复杂度虽然降为0(logn)，但却在进行插入和删除元素时，需要移动大量元素。与链式存储相比，插入和删除时虽然都不需要移动元素，但在查找