Теория и реализация языков программирования


           

Этот вариант плох тем, что


Этот вариант плох тем, что занятые элементы "группируются" , образуют последовательные занятые участки и в пределах этого участка поиск становится по-существу линейным.
  • h2(i) = (i + k) mod N, где k и N взаимно просты. По-существу это предыдущий вариант, но элементы накапливаются не в последовательных элементах, а "разносятся".
  • h2(i) = (a * i + c) mod N - "псевдослучайная последовательность". Здесь c и N должны быть взаимно просты, b = a-1 кратно p для любого простого p, являщегося делителем N, b кратно 4, если N кратно 4 [6].

  • Поиск в таблице расстановки можно описать следующей функцией:
    void Search(String Id,boolean * Yes,int * Point) {int H0=h1(Id), H=H0; while (1) {if (Empty(H)==NULL) {*Yes=false; *Point=H; return; } else if (IdComp(H,Id)==0) {*Yes=true; *Point=H; return; } else H=h2(H); if (H==H0) {*Yes=false; *Point=NULL; return; } } }
    Функция IdComp(H,Id) сравнивает элемент таблицы на входе H с идентификатором и вырабатывает 0, если они равны. Функция Empty(H) вырабатывает NULL, если вход H пуст. Функция Search присваивает параметрам Yes и Pointer соответственно следующие значения :
    true, P - если нашли требуемый идентификатор, где P - указатель на соответствующий этому идентификатору вход в таблице,
    false, NULL - если искомый идентификатор не найден, причем в таблице нет свободного места, и
    false, P - если искомый идентификатор не найден, но в таблице есть свободный вход P.
    Занесение элемента в таблицу можно осуществить следующей функцией:
    int Insert(String Id) {boolean Yes; int Point=-1; Search(Id,&Yes,&Point); if (!Yes && (Point!=NULL)) InsertId(Point,Id); return(Point); }
    Здесь функция InsertId(Point,Id) заносит идентификатор Id для входа Point таблицы.

    Содержание  Назад  Вперед





    Forekc.ru
    Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий