skiplist.pas 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236
  1. Program skiplist;
  2. const
  3. infile='skiplist.in';
  4. outfile='skiplist.out';
  5. MaxLevel=100;
  6. inf=2000000000;
  7. type
  8. Valuetype = longint;
  9. Snode=^Skiptype;
  10. Skiptype=record
  11. key:longint;
  12. value:Valuetype;
  13. next:array[1..MaxLevel] of Snode;
  14. end;
  15. Listtype=record
  16. level:integer;
  17. header,tail:Snode;
  18. end;
  19. var
  20. Emptynode:Skiptype;
  21. result,newvalue:Valuetype;
  22. t,n,key:longint;
  23. f,fo:text;
  24. order:char;
  25. List:Listtype;
  26. update:array[1..MaxLevel] of Snode;
  27. Procedure Initialize;
  28. var
  29. i:integer;
  30. begin
  31. fillchar(Emptynode,sizeof(Emptynode),0);
  32. List.level:=1; new(List.header);
  33. List.header^:=Emptynode; List.header^.key:=-inf;
  34. new(List.tail); List.tail^:=Emptynode;
  35. for i:=1 to MaxLevel do List.header^.next[i]:=List.tail;
  36. List.tail^.key:=inf;
  37. for i:=1 to MaxLevel do update[i]:=List.header;
  38. end;
  39. Function Random_Level : integer; {p=0.5}
  40. var
  41. lev:integer;
  42. begin
  43. lev:=1;
  44. while random<0.5 do lev:=lev+1;
  45. Random_Level:=lev;
  46. end;
  47. Function Find_Element(var List:Listtype; SearchKey:longint; var res:Valuetype) : boolean;
  48. var
  49. x:Snode;
  50. i:integer;
  51. begin
  52. x:=List.header;
  53. for i:=List.level downto 1 do
  54. while x^.next[i]^.key<SearchKey do x:=x^.next[i];
  55. x:=x^.next[1];
  56. if x^.key=Searchkey then begin res:=x^.value; Find_Element:=true end
  57. else Find_Element:=false;
  58. end;
  59. Procedure Insert_Element(var List:Listtype; SearchKey:longint; Newvalue:Valuetype);
  60. var
  61. x:Snode;
  62. lvl,i:integer;
  63. update:array[1..MaxLevel] of Snode;
  64. begin
  65. x:=List.header;
  66. for i:=List.level downto 1 do begin
  67. while x^.next[i]^.key<SearchKey do x:=x^.next[i];
  68. update[i]:=x;
  69. end;
  70. if x^.next[1]^.key=SearchKey then begin
  71. x:=x^.next[1];
  72. x^.value:=Newvalue;
  73. end else begin
  74. lvl:=Random_level;
  75. if lvl>List.level then begin
  76. for i:=List.level+1 to lvl do update[i]:=List.header;
  77. List.level:=lvl+1;
  78. end;
  79. new(x);
  80. x^:=Emptynode;
  81. x^.key:=SearchKey;
  82. x^.value:=Newvalue;
  83. for i:=1 to lvl do begin
  84. x^.next[i]:=update[i]^.next[i];
  85. update[i]^.next[i]:=x;
  86. end;
  87. end;
  88. end;
  89. Procedure Delete_Element(var List:Listtype; SearchKey:longint);
  90. var
  91. x:Snode;
  92. i:integer;
  93. update:array[1..MaxLevel] of Snode;
  94. begin
  95. x:=List.header;
  96. for i:=List.level downto 1 do begin
  97. while x^.next[i]^.key<SearchKey do x:=x^.next[i];
  98. update[i]:=x;
  99. end;
  100. if x^.next[1]^.key=SearchKey then begin
  101. x:=x^.next[1];
  102. for i:=1 to List.level do begin
  103. if update[i]^.next[i]^.key<>SearchKey then break;
  104. update[i]^.next[i]:=x^.next[i];
  105. end;
  106. dispose(x);
  107. while (List.level>1)and(List.header^.next[List.level-1]^.key=key-inf) do
  108. dec(List.level);
  109. end;
  110. end;
  111. Function Find_Element_with_Finger(var List:Listtype; SearchKey:longint; var res:Valuetype) : boolean;
  112. var
  113. x:Snode;
  114. lvl,i:integer;
  115. begin
  116. lvl:=2;
  117. if update[1].key<SearchKey then begin
  118. while (lvl<=List.level)and(update[lvl].next[lvl].key<SearchKey) do inc(lvl);
  119. dec(lvl);
  120. x:=update[lvl];
  121. end else begin
  122. while (lvl<=List.level)and(update[lvl].key>=SearchKey) do inc(lvl);
  123. x:=update[lvl];
  124. end;
  125. for i:=lvl downto 1 do
  126. while x^.next[i]^.key<SearchKey do x:=x^.next[i];
  127. x:=x^.next[1];
  128. if x^.key=Searchkey then begin res:=x^.value; Find_Element_with_Finger:=true end
  129. else Find_Element_with_Finger:=false;
  130. end;
  131. procedure Insert_Element_with_Finger(var List:Listtype; SearchKey:longint; Newvalue:Valuetype);
  132. var
  133. x:Snode;
  134. lvl,i:integer;
  135. begin
  136. lvl:=2;
  137. if update[1].key<SearchKey then begin
  138. while (lvl<=List.level)and(update[lvl].next[lvl].key<SearchKey) do inc(lvl);
  139. dec(lvl);
  140. x:=update[lvl];
  141. end else begin
  142. while (lvl<=List.level)and(update[lvl].key>=SearchKey) do begin
  143. inc(lvl);
  144. end;
  145. x:=update[lvl];
  146. end;
  147. for i:=lvl downto 1 do begin
  148. while x^.next[i]^.key<SearchKey do x:=x^.next[i];
  149. update[i]:=x;
  150. end;
  151. if x^.next[1]^.key=SearchKey then begin
  152. x:=x^.next[1];
  153. x^.value:=Newvalue;
  154. end else begin
  155. lvl:=Random_level;
  156. if lvl>List.level then begin
  157. for i:=List.level+1 to lvl do update[i]:=List.header;
  158. List.level:=lvl+1;
  159. end;
  160. new(x);
  161. x^:=Emptynode;
  162. x^.key:=SearchKey;
  163. x^.value:=Newvalue;
  164. for i:=1 to lvl do begin
  165. x^.next[i]:=update[i]^.next[i];
  166. update[i]^.next[i]:=x;
  167. end;
  168. end;
  169. end;
  170. Procedure Delete_Element_with_Finger(var List:Listtype; SearchKey:longint);
  171. var
  172. x:Snode;
  173. i,lvl:integer;
  174. begin
  175. lvl:=2;
  176. if update[1].key<SearchKey then begin
  177. while (lvl<=List.level)and(update[lvl].next[lvl].key<SearchKey) do inc(lvl);
  178. dec(lvl);
  179. x:=update[lvl];
  180. end else begin
  181. while (lvl<=List.level)and(update[lvl].key>=SearchKey) do inc(lvl);
  182. x:=update[lvl];
  183. end;
  184. for i:=lvl downto 1 do begin
  185. while x^.next[i]^.key<SearchKey do x:=x^.next[i];
  186. update[i]:=x;
  187. end;
  188. if x^.next[1]^.key=SearchKey then begin
  189. x:=x^.next[1];
  190. for i:=1 to List.level do begin
  191. if update[i]^.next[i]^.key<>SearchKey then break;
  192. update[i]^.next[i]:=x^.next[i];
  193. end;
  194. dispose(x);
  195. while (List.level>1)and(List.header^.next[List.level-1]^.key=key-inf) do
  196. dec(List.level);
  197. end;
  198. end;
  199. begin
  200. Randomize;
  201. Initialize;
  202. assign(f,infile); reset(f);
  203. assign(fo,outfile); rewrite(fo);
  204. readln(f,n);
  205. for t:=1 to n do begin
  206. read(f,order);
  207. read(f,key);
  208. case order of
  209. '*':begin
  210. Find_Element_with_Finger(List,key,result);
  211. end;
  212. '+':begin
  213. read(f,newvalue);
  214. Insert_Element_with_Finger(List,key,newvalue);
  215. end;
  216. '-':begin
  217. Delete_Element_with_Finger(List,key);
  218. end;
  219. end;
  220. readln(f);
  221. end;
  222. close(fo);
  223. close(f);
  224. end.