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

《用舍伍德算法实现线性表的快速查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、akindofprobabilityalgorithm.Aftercomparingcharacteristicoflinearliststoredbysequentialarrayandsingleinkedfist.Thepaperputsforwardadatastructure一一Linkedlistsimulatingbyarray.Anditprovesthattimecomplexityofsearchoperationis0(n)byitintheory.Atlast，thepapergivessom

3、edatatestingincomputerKeywords:Sherwoodalgorithm；Probabilityalgorithm;Search前言：所谓概率算法，就是在算法的过程中引入随机数，使得算法在执行的过程中随机选择下一个计算步骤。很多算法的每一个计算步骤都是固定的，而概率算法允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此概率算法可在很大程度上降低算法的复杂度。 　　概率算法的特征是对所求解问题的同一实例用同一概率算法求解两

4、次可能得到完全不同的效果(时间和结果)。正文：l舍伍德算法设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在x∈Xn使得的可能性。希望获得一个概率算法B，使得对问题的输入规模为n的每一个实例均有这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。概率算法的一个特征是对同一实例用同‘概率算法求解两次可能得到完全不同的结果。这两次求解可能会得到相

5、当大的差别。概率算法大致有4类：数值概率算法，蒙特R罗算法，拉斯维加斯算法和舍伍德算法。本文采用舍伍德算法来求解。舍伍德算法总能求得闷题的一个解，且所求的解总是正确韵。当一个确定性算法在最坏情况下的计算复杂性与在平均情况下的计算复杂性的较大差别时，可在这个确定性算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例悯的这种差别。该算法的精髓1：足避免算法的最坏情况行为，而足没法消除这种最坏情况行为与特定实例之间的关联性。2线性袁的组织在现实世界中，线性表的倒子枚不胜举，如一幅扑克牌的点数(2,3,4，…,

6、J，Q，K，A)可构成一个线性表；数据库表中的记录也可以构成一个线性表，只不过是该线性表中的数据元索稍复杂一点罢了。正因为线性表如此重要，ANSl和ISO于1998年制定的STL(StandardTemplateLibrary)中提供了对线性表的支持。STL的容器是用来防止各种类型的对象，其中每一个容器类就是计算机的一个基本数据结构。STL有以下7个最基本的容器类：向照(Vector)，列表(List)，双端队列(Deque)，集合(Set)，多重集合(Multiset)，映像(Map)，多重映像(Multimap)

7、等。线性表的存储有两种方式：顺序存储和链式存储。从空问的角度看，链式存储的存储密度低，因为它需要存储附加的指针域的数据。而顺序存储不需要存储附加信息，因而存储效率比较高；从时间角度来看，由于顺序存储的逻辑顺序与物理顺序一致，其存储可采用其索引号来加以存取，因此是一种随机存取结构，表中的任意一个结点都可在O(1)的时间内直接存取，但是在表中插入和删除元索时耍移动大量的元素，该结构适合经常进行查找，很少做插入和删除运算操作的场台。而链式存储与它恰恰相反，插入和删除不需要移动元素，只需要修改指针即可，但其查找的时间复杂度却

8、为O(n)．在STL中容器类中的Vector类采用顺序存储，List类采用链式存储。后面的程序测试就是采用这两个类来进行的。有没有这样的一个数据结构，即能像链式存错储结构那样，插入和删除不需移动大量元素，在查找时也能像顺序存储结构相似，不会比较报多的数据?况且在一些不包含指针的程序设计语音如Java和VB中，如何实现链式存储结构呢?3数组实现链