0045算法笔记——【随机化算法】舍伍德随机化思想搜索有序表

1、 问题描述     用两个数组来表示所给的含有n个元素的有序集S。用value0:n存储有序集中的元素，link0:n存储有序集中元素在数组value中位置的指针(实际上使用数组模拟链表)。link0指向有序集中的第一个元素，集valuelink0是集合中的最小元素。一般地，如果valuei是所给有序集S中的第k个元素，则valuelinki是S中第k+1个元素。S中元素的有序性表现为，对于任意1<=i<=n有valuei<=valuelinki。对于集合S中的最大元素valuek有，linkk=0且value0是一个大数。 

2、   例：有序集S=1,2,3,5,8,13,21的一种表现方式如图所示：    搜索思想     对于有序链表，可采用顺序搜索的方式在所给的有序集S中搜索值为x的元素。如果有序集S中含有n个元素，则在最坏的情况下，顺序搜索算法所需的计算时间为O(n)。利用数组下标的索引性质，可以设计一个随机化搜索算法，一改进算法的搜索时间复杂性。算法的基本思想是，随机抽取数组元素若干次，从较接近搜索元素x的位置开始做顺序搜索。如果随机搜索数组元素k次，则其后顺序搜索所需的平均比较次数为O(n/k+1)。因此，如果去k=|sqrt(n)|，

3、则算法所需的平均计算时间为(Osqrt(n)。    随机化思想下的有序表实现具体代码如下：   1、RandomNumber.hcpp view plain copy1. #include"time.h"  2. /随机数类  3. const unsigned long maxshort = 65536L;  4. const unsigned long multiplie

4、r = 1194211693L;  5. const unsigned long adder = 12345L;  6.   7. class RandomNumber  8.   9.     private:  10.         /当前种子  11.

5、         unsigned long randSeed;  12.     public:  13.         RandomNumber(unsigned long s = 0);/构造函数，默认值0表示由系统自动产生种子  14.   

6、0;     unsigned short Random(unsigned long n);/产生0：n-1之间的随机整数  15.         double fRandom(void);/产生0,1)之间的随机实数  16. ;  17.   18. RandomNumber:RandomNumber(unsigned l

7、ong s)/产生种子  19.   20.     if(s = 0)  21.       22.         randSeed = time(0);/用系统时间产生种子  23.       24.  

8、0;  else  25.       26.         randSeed = s;/由用户提供种子  27.       28.   29.   30. unsigned short RandomNumber:Random(unsigned 

9、long n)/产生0：n-1之间的随机整数  31.   32.     randSeed = multiplier * randSeed + adder;/线性同余式  33.     return (unsigned short)(randSeed>>16)%n);  34.   35.   

10、;36. double RandomNumber:fRandom(void)/产生0,1)之间的随机实数  37.   38.     return Random(maxshort)/double(maxshort);  39.       2、7d3d2.cppcpp view plain copy1. /随机化算法搜素有序表  2. #include "stdafx.h&q

11、uot;  3. #include "RandomNumber.h"  4. #include "math.h"  5. #include <iostream>  6. using namespace std;  7.   8. template<class Type>  9. class OrderedList 

12、 10.   11.     friend int main();  12.     public:  13.         OrderedList(Type Small,Type Large,int MaxL);  14.       

13、  OrderedList();  15.         bool Search(Type x,int& index);     /搜索指定元素  16.         int SearchLast(void);     

14、60;         /搜索最大元素  17.         void Insert(Type k);                /插入指定元素  18.     

15、;    void Delete(Type k);                /删除指定元素  19.         void Output();          

16、;            /输出集合中元素  20.     private:  21.         int n;                

17、              /当前集合中元素的个数  22.         int MaxLength;                    &#

18、160; /集合中最大元素的个数  23.         Type *value;                        /存储集合中元素的数组  24.     

19、60;   int *link;                          /指针数组  25.         RandomNumber rnd;   

20、;                /随机数产生器  26.         Type Small;                   &#

21、160;     /集合中元素的下界  27.         Type TailKey;                       /集合中元素的上界    28.

22、;  29.   30. /构造函数  31. template<class Type>  32. OrderedList<Type>:OrderedList(Type small,Type Large,int MaxL)  33.   34.     MaxLength = MaxL;  35.    

23、 value = new TypeMaxLength+1;  36.     link = new intMaxLength+1;  37.     TailKey = Large;  38.     n = 0;  39.     link0

24、60;= 0;  40.     value0 = TailKey;  41.     Small = small;  42.   43.   44. /析构函数  45. template<class Type>  46. OrderedList<Type>:OrderedList()

25、0; 47.   48.     delete value;  49.     delete link;  50.   51.   52. /搜索集合中指定元素k  53. template<class Type>  54. bool OrderedList<Type>:Search(Type 

26、x,int& index)  55.   56.     index = 0;  57.     Type max = Small;  58.     int m = floor(sqrt(double(n);/随机抽取数组元素次数  59.   60.

27、60;   for(int i=1; i<=m; i+)  61.       62.         int j = rnd.Random(n)+1;/随机产生数组元素位置  63.         Type y =

28、60;valuej;  64.           65.         if(max<y)&& (y<x)  66.           67.        

29、0;    max = y;  68.             index = j;  69.           70.       71.   72.   

30、  /顺序搜索  73.     while(valuelinkindex<x)  74.       75.         index = linkindex;  76.       77.   78.   &

31、#160; return (valuelinkindex = x);  79.   80.   81. /插入指定元素  82. template<class Type>  83. void OrderedList<Type>:Insert(Type k)  84.   85.     if(n = Ma

32、xLength)|(k>=TailKey)  86.       87.         return;  88.       89.     int index;  90.   91.     if(!Search(k,i

33、ndex)  92.       93.         value+n = k;  94.         linkn = linkindex;  95.         linkindex

34、0;= n;  96.       97.   98.   99. /搜索集合中最大元素  100. template<class Type>  101. int OrderedList<Type>:SearchLast(void)  102.   103.     int index 

35、;= 0;  104.     Type x = valuen;  105.     Type max = Small;  106.     int m = floor(sqrt(double(n);/随机抽取数组元素次数  107.   108.   

36、60; for(int i=1; i<=m; i+)  109.       110.         int j = rnd.Random(n)+1;/随机产生数组元素位置  111.         Type y = valuej

37、;  112.   113.         if(max<y)&&(y<x)  114.           115.             max = y;  116

38、.             index = j;  117.           118.       119.   120.     /顺序搜索  121.    &#

39、160;while(linkindex!=n)  122.       123.         index = linkindex;  124.       125.     return index;  126.   127.  

40、60;128. /删除集合中指定元素  129. template<class Type>  130. void OrderedList<Type>:Delete(Type k)  131.   132.     if(n=0)&&(k>=TailKey)  133.       134.   

41、0;     return;  135.       136.   137.     int index;  138.     if(Search(k,index)  139.       140.      

42、   int p = linkindex;  141.         if(p = n)  142.           143.             linkindex&#

43、160;= linkp;  144.              145.         else  146.           147.         &

44、#160;   if(linkp!=n)  148.               149.                 int q = SearchLast();  150.  

45、0;              linkq = p;  151.                 linkindex = linkp;  152.       

46、        153.             valuep = valuen;/删除元素由最大元素来填补  154.             linkp = linkn;  155.  

47、         156.         n-;  157.       158.   159.   160. /输出集合中所有元素  161. template<class Type>  162. void OrderedList&l

48、t;Type>:Output()  163.   164.     int index = 0,i = 0;  165.     while(i<n)  166.       167.         index = 

49、linkindex;  168.         cout<<valueindex<<" "  169.         i+;  170.       171.     cout<<endl; 

50、0;172.     cout<<"value:"  173.     for(i=0; i<=n; i+)  174.       175.         cout.width(4);  176.      

51、   cout<<valuei;  177.       178.     cout<<endl;  179.     cout<<"link:"      180.     for(i=0; i<=n; i

52、+)  181.       182.         cout.width(4);  183.         cout<<linki;  184.       185.     cout<<e

53、ndl;     186.   187.   188. int main()  189.   190.     static RandomNumber rnd;  191.     OrderedList<int> *ol = new OrderedList<int>(0,100,100);  192.   193.     /创建  194.     cout<<&q