0046算法笔记——【随机化算法】舍伍德随机化思想解决跳跃表问题(2)

31. ~SkipList();

32. bool Search(const KType& k,EType& e) const; 33. SkipList& Insert(const EType& e);

34. SkipList& Delete(const KType& k,EType& e); 35. void Output(); 36. private:

37. int Level();

38. SkipNode *SaveSearch(const KType& k); 39. int MaxLevel; //跳跃表级别上界 40. int Levels; //当前最大级别 41. RandomNumber rnd; //随机数产生器 42. float Prob; //用于分配节点级别 43. KType TailKey; //元素键值上界 44. SkipNode *head; //头结点指针 45. SkipNode *NIL; //尾节点指针 46. SkipNode **last; //指针数组 47. }; 48.

49. //构造函数

50. template

51. SkipList::SkipList(KType Large,int MaxE,float p) 52. {

53. Prob = p;

54. MaxLevel = ceil(log(float(MaxE))/log(1/p))-1; //初始化跳跃表级别上

界

55. TailKey = Large; //元素键值上界 56. Levels = 0; //初始化当前最大级别 57.

58. //创建头、尾节点和数组 last

59. head = new SkipNode(MaxLevel+1); 60. NIL = new SkipNode(0);

61. last = new SkipNode *[MaxLevel+1]; 62. NIL->data = Large; 63.

64. //将跳跃表初始化为空表

65. for(int i=0; i<=MaxLevel; i++) 66. {

67. head->next[i] = NIL; 68. } 69. } 70.

71. //析构函数

72. template 73. SkipList::~SkipList()

74. {

75. SkipNode *next; 76.

77. //删除所有节点 78. while(head!=NIL) 79. {

80. next = head->next[0]; 81. delete head; 82. head = next; 83. } 84.

85. delete NIL; 86. delete []last; 87. } 88.

89. class element 90. {

91. friend int main(void); 92. public:

93. operator long() const 94. {

95. return key; 96. }

97. element& operator = (long y) 98. {

99. key = y; 100. return *this; 101. } 102. private: 103. int data; 104. long key; 105. }; 106.

107. //搜索指定元素k

108. template

109. bool SkipList::Search(const KType& k,EType& e) const 110. {

111. if(k>=TailKey) 112. {

113. return false; 114. }

115. //位置p恰好位于指定元素k之前 116. SkipNode *p = head;

117. for(int i=Levels; i>=0; i--)//逐渐向下搜索

118. {

119. while(p->next[i]->data

121. p = p->next[i];//每次搜索尽可能滴接近要搜索的元素 122. } 123. }

124. e = p->next[0]->data; 125. return (e==k); 126. } 127.

128. //搜索指定元素k,并将每一级中遇到的上一个节点存放在数组last中 129. template

130. SkipNode *SkipList::SaveSearch(const KType& k) 131. {

132. //位置p恰好位于指定元素k之前 133. SkipNode *p = head; 134. for(int i = Levels; i>=0; i--) 135. {

136. while(p->next[i]->data

138. p = p->next[i]; 139. }

140. last[i] = p; //上一个第i级结点 141. }

142. return (p->next[0]); 143. } 144.

145. //产生不超过MaxLevel 的随机级别 146. template 147. int SkipList::Level() 148. {

149. int lev = 0;

150. while(rnd.fRandom()

152. lev++; 153. }

154. return (lev<=MaxLevel)?lev:MaxLevel; 155. } 156.

157. //插入指定元素e

158. template

159. SkipList& SkipList::Insert(const EType& e) 160. {

161. KType k = e;//取得元素键值

162. if(k>=TailKey) 163. {

164. cout<<\元素键值超界!\<

167. //检查元素是否已存在

168. SkipNode *p = SaveSearch(k); 169. if(p->data == e) 170. {

171. cout<<\元素已存在!\<

175. //元素不存在，确定新节点级别 176. int lev = Level(); 177. //调整个级别指针 178. if(lev>Levels) 179. {

180. for(int i=Levels+1; i<=lev; i++) 181. {

182. last[i] = head; 183. }

184. Levels = lev; 185. } 186.

187. //产生新节点，并将新节点插入p之后

188. SkipNode *y = new SkipNode(lev+1); 189. y->data = e; 190.

191. for(int i=0; i<=lev; i++) 192. {

193. //插入第i级链

194. y->next[i] = last[i]->next[i]; 195. last[i]->next[i] = y; 196. }

197. return *this; 198. } 199.

200. //删除键值为k的元素，并将所删除的元素存入e 201. template

202. SkipList& SkipList::Delete(const KType& k,EType&

e) 203. {

204. if(k>=TailKey)

205. {

206. cout<<\元素键值超界!\<

208. //搜索待删除元素

209. SkipNode *p = SaveSearch(k); 210. if(p->data!=k) 211. {

212. cout<<\未找到待删除元素!\<

214. //从跳跃表中删除节点

215. for(int i=0; i<=Levels && last[i]->next[i] == p; i++) 216. {

217. last[i]->next[i] = p->next[i]; 218. }

219. //更新当前级别

220. while(Levels>0 && head->next[Levels] == NIL) 221. {

222. Levels--; 223. }

224. e = p->data; 225. delete p; 226. return *this; 227. } 228.

229. //输出集合中的元素

230. template 231. void SkipList::Output() 232. {

233. SkipNode *y = head->next[0]; 234. for(;y!=NIL; y=y->next[0]) 235. {

236. cout<data<<' '; 237. }

238. cout<

241. int main() 242. {

243. SkipList *s = new SkipList(100,10,0.5); 244.

245. //创建

246. cout<<\创建===========\<

248. int a[] = {5,3,2,11,7,13,19,17,23};

249.

250. for(int i=0; i<9; i++) 251. {

252. s->Insert(a[i]); 253. }

254. s->Output(); 255.

256. //搜索

257. cout<<\搜索===========\<

259. cout<<\搜索元素k=\<Search(17,e)) 261. {

262. cout<<\位置搜索结果为：k=\<

264. cout<

266. //删除

267. cout<<\删除===========\<

268. cout<<\删除跳跃表元素k=\<Delete(k,e); 270. s->Output(); 271.

272. delete s; 273. return 0; 274. }

程序运行结果如图：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库0046算法笔记——【随机化算法】舍伍德随机化思想解决跳跃表问题(2)在线全文阅读。