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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

(мы  позволяем  себе писать n-1 в качестве границы в определении
типа, хотя в паскале это не разрешается). В этих массивах  будут
храниться  элементы  множества: оно равно множеству всех val [i]
для тех i, для которых used [i], причем все эти val [i]  различ-
ны.  По  возможности  мы  будем хранить элемент t на месте h(t),
считая это место "исконным" для элемента t.  Однако  может  слу-
читься  так,  что новый элемент, который мы хотим добавить, пре-
тендует на уже занятое место (для которого used истинно). В этом
случае мы отыщем ближайшее справа свободное место и запишем эле-
мент туда. ("Справа" значит  "в  сторону  увеличения  индексов";
дойдя  до  края,  мы  перескакиваем в начало.) По предположению,
число элементов всегда меньше n, так что пустые места гарантиро-
ванно будут.
     Формально говоря, в любой момент должно  соблюдаться  такое
требование:  для любого элемента множества участок справа от его
исконного места до его фактического места полностью заполнен.
     Благодаря этому проверка принадлежности заданного  элемента
t  осуществляется  легко: встав на h(t), двигаемся направо, пока
не дойдем до пустого места или до элемента t.  В  первом  случае
элемент  t отсутствует в множестве, во втором присутствует. Если
элемент отсутствует, то его можно добавить на  найденное  пустое
место.  Если  присутствует, то можно его удалить (положив used =
false).

     11.1.1. В предыдущем  абзаце  есть  ошибка.  Найдите  ее  и
исправьте.

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

     11.1.2.  Написать программы проверки принадлежности, добав-
ления и удаления.

     Решение.
  function принадлежит (t: T): boolean;
  | var i: integer;
  begin
  | i := h (t);
  | while used [i] and (val [i] <> t) do begin
  | | i := (i + 1) mod n;
  | end; {not used [i] or (val [i] = t)}
  | belong := used [i] and (val [i] = t);
  end;

  procedure добавить (t: T);
  | var i: integer;
  begin
  | i := h (t);
  | while used [i] and (val [i] <> t) do begin
  | | i := (i + 1) mod n;
  | end; {not used [i] or (val [i] = t)}
  | if not used [i] then begin
  | | used [i] := true;
  | | val [i] := 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 Большая Одесская Библиотека.