Случайный афоризм
Поэт - властитель вдохновенья. Он должен им повелевать. Иоганн Вольфганг Гёте
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

водов.

     11.2. Хеширование со списками

     На  хеш-функцию с m значениями можно смотреть как на способ
свести вопрос о хранении одного большого множества к  вопросу  о
хранении нескольких меньшим. Именно, если у нас есть хеш-функция
с  m значениями, то любое множество разбивается на m подмножеств
(возможно,   пустых),   соответствующих   возможных    значениям
хэш-функции.  Вопрос  о  проверке принадлежности, добавлении или
удалении для большого множества сводится к такому же вопросу для
одного из меньших (чтобы узнать, для какого, надо посмотреть  на
значение хеш-функции).

     В  принципе,  эти  меньшие  множества могут храниться любым
способом (раз они малы, это не очень важно), но удобно  их  хра-
нить  с помощью ссылок, поскольку нам известен их суммарный раз-
мер (равный числу элементов  хешируемого  множества).  Следующая
задача предлагает реализовать этот план.

     11.2.1. Пусть хеш-функция принимает значения 1..k. Для каж-
дого  значения хеш-функции рассмотрим список всех элементов мно-
жества с данным значением хеш-функции. Будем хранить эти k спис-
ков с помощью переменных

     Содержание: array [1..n] of T;
     Следующий: array [1..n] of 1..n;
     ПервСвоб: 1..n;
     Вершина: array [1..k] of 1..n;

так же, как мы это делали для k  стеков  ограниченной  суммарной
длины.  Напишите  соответствующие программы. (Теперь с удалением
будет меньше проблем.)

     Решение. Перед началом работы  надо  положить  Вершина[i]=0
для  всех  i=1..k,  и  связать  все  места  в  список свободного
пространства,  положив   ПервСвоб=1   и   Следующий[i]=i+1   для
i=1..n-1, а также Следующий[n]=0.

  function принадлежит (t: T): boolean;
  | var i: integer;
  begin
  | | i := Вершина[h(t)];
  | i := Вершина[h(t)];
  | {осталось искать в списке, начиная с i}
  | while (i <> 0) and (Содержание[i] <> t) do begin
  | | i := Следующий[i];
  | end; {(i=0) or (Содержание [i] = t)}
  | belong := Содержание[i]=t;
  end;

  procedure добавить (t: T);
  | var i: integer;
  begin
  | if not принадлежит(t) then begin
  | | i := ПервСвоб;
  | | {ПервСвоб <> 0 - считаем, что не переполняется}
  | | ПервСвоб := Следующий[ПервСвоб]
  | | Содержание[i]:=t;
  | | Следующий[i]:=Вершина[h(t)];

1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 18 : 19 : 20 : 21 : 22 : 23 : 24 : 25 : 26 : 27 : 28 : 29 : 30 : 31 : 32 : 33 : 34 : 35 : 36 : 37 : 38 : 39 : 40 : 41 : 42 : 43 : 44 : 45 : 46 : 47 : 48 : 49 : 50 : 51 : 52 : 53 : 54 : 55 : 56 : 57 : 58 : 59 : 60 : 61 : 62 : 63 : 64 : 65 : 66 : 67 : 68 : 69 : 70 : 71 : 72 : 73 : 74 : 75 : 76 : 77 : 78 : 79 : 80 : 81 : 82 : 83 : 84 : 85 : 86 : 87 : 88 : 89 : 90 : 91 : 92 : 93 : 94 : 95 : 96 : 97 : 98 : 99 : 100 : 101 : 102 : 103 : 104 : 105 : 106 : 107 : 108 : 109 : 110 : 111 : 112 : 113 : 114 : 115 : 116 : 117 : 118 : 119 : 120 : 121 : 122 : 123 : 124 : 125 : 126 : 127 : 128 : 129 : 130 : 131 : 132 : 133 : 134 : 135 : 136 : 137 : 138 : 139 : 140 : 141 : 142 : 143 : 144 : 145 : 146 : 147 : 148 : 149 : 150 : 151 : 152 : 153 : 154 : 155 : 156 : 157 : 158 : 159 : 160 : 161 : 162 : 163 : 164 : 165 : 166 : 167 : 168 : 169 : 170 : 171 : 172 : 173 : 174 : 175 : 176 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 184 : 185 : 186 : 187 : 188 : 189 : 190 : 191 : 192 : 193 : 194 : 195 : 196 : 197 : 198 : 199 : 200 : 201 : 202 : 203 : 204 : 205 : 206 : 207 : 208 : 209 : 210 : 211 : 212 : 213 : 214 : 215 : 216 : 217 : 218 : 219 : 220 : 221 : 222 : 223 : 224 : 225 : 226 : 227 : 228 : 229 : 230 : 231 : 232 : 233 : 234 : 235 : 236 : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : 246 : 247 : 248 : 249 : 250 : 251 : 252 : 253 : 254 : 255 : 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : 291 : 292 : 293 : 294 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.