0045算法筆記——【隨機(jī)化算法】舍伍德隨機(jī)化思想搜索有序表

1、 問題描述     用兩個數(shù)組來表示所給的含有n個元素的有序集S。用value0:n存儲有序集中的元素，link0:n存儲有序集中元素在數(shù)組value中位置的指針(實(shí)際上使用數(shù)組模擬鏈表)。link0指向有序集中的第一個元素，集valuelink0是集合中的最小元素。一般地，如果valuei是所給有序集S中的第k個元素，則valuelinki是S中第k+1個元素。S中元素的有序性表現(xiàn)為，對于任意1<=i<=n有valuei<=valuelinki。對于集合S中的最大元素valuek有，linkk=0且value0是一個大數(shù)。 

2、   例：有序集S=1,2,3,5,8,13,21的一種表現(xiàn)方式如圖所示：    搜索思想     對于有序鏈表，可采用順序搜索的方式在所給的有序集S中搜索值為x的元素。如果有序集S中含有n個元素，則在最壞的情況下，順序搜索算法所需的計(jì)算時間為O(n)。利用數(shù)組下標(biāo)的索引性質(zhì)，可以設(shè)計(jì)一個隨機(jī)化搜索算法，一改進(jìn)算法的搜索時間復(fù)雜性。算法的基本思想是，隨機(jī)抽取數(shù)組元素若干次，從較接近搜索元素x的位置開始做順序搜索。如果隨機(jī)搜索數(shù)組元素k次，則其后順序搜索所需的平均比較次數(shù)為O(n/k+1)。因此，如果去k=|sqrt(n)|，

3、則算法所需的平均計(jì)算時間為(Osqrt(n)。    隨機(jī)化思想下的有序表實(shí)現(xiàn)具體代碼如下：   1、RandomNumber.hcpp view plain copy1. #include"time.h"  2. /隨機(jī)數(shù)類  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.         /當(dāng)前種子  11.

5、         unsigned long randSeed;  12.     public:  13.         RandomNumber(unsigned long s = 0);/構(gòu)造函數(shù)，默認(rèn)值0表示由系統(tǒng)自動產(chǎn)生種子  14.   

6、0;     unsigned short Random(unsigned long n);/產(chǎn)生0：n-1之間的隨機(jī)整數(shù)  15.         double fRandom(void);/產(chǎn)生0,1)之間的隨機(jī)實(shí)數(shù)  16. ;  17.   18. RandomNumber:RandomNumber(unsigned l

7、ong s)/產(chǎn)生種子  19.   20.     if(s = 0)  21.       22.         randSeed = time(0);/用系統(tǒng)時間產(chǎn)生種子  23.       24.  

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

9、long n)/產(chǎn)生0：n-1之間的隨機(jī)整數(shù)  31.   32.     randSeed = multiplier * randSeed + adder;/線性同余式  33.     return (unsigned short)(randSeed>>16)%n);  34.   35.   

10、;36. double RandomNumber:fRandom(void)/產(chǎn)生0,1)之間的隨機(jī)實(shí)數(shù)  37.   38.     return Random(maxshort)/double(maxshort);  39.       2、7d3d2.cppcpp view plain copy1. /隨機(jī)化算法搜素有序表  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、              /當(dāng)前集合中元素的個數(shù)  22.         int MaxLength;                    &#

18、160; /集合中最大元素的個數(shù)  23.         Type *value;                        /存儲集合中元素的數(shù)組  24.     

19、60;   int *link;                          /指針數(shù)組  25.         RandomNumber rnd;   

20、;                /隨機(jī)數(shù)產(chǎn)生器  26.         Type Small;                   &#

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

22、;  29.   30. /構(gòu)造函數(shù)  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. /析構(gòu)函數(shù)  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);/隨機(jī)抽取數(shù)組元素次數(shù)  59.   60.

27、60;   for(int i=1; i<=m; i+)  61.       62.         int j = rnd.Random(n)+1;/隨機(jī)產(chǎn)生數(shù)組元素位置  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);/隨機(jī)抽取數(shù)組元素次數(shù)  107.   108.   

36、60; for(int i=1; i<=m; i+)  109.       110.         int j = rnd.Random(n)+1;/隨機(jī)產(chǎn)生數(shù)組元素位置  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;/刪除元素由最大元素來填補(bǔ)  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.     /創(chuàng)建  194.     cout<<&q