Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Таблицы расстановки со списками






Только что описанная схема страдает одним недостатком - возможностью переполнения таблицы. Рассмотрим ее модификацию, когда все элементы, имеющие одинаковое значения (первичной) функции расстановки, связываются в список (при этом отпадает необходимость использования функций hi для i > = 2). Таблица расстановки со списками - это массив указателей на списки элементов (рис. 7.3)

Вначале таблица расстановки пуста (все элементы имеют значение NULL). При поиске идентификатора Id вычисляется функция расстановки h(Id) и просматривается соответствующий линейный список. Поиск в таблице может быть описан следующей функцией:

struct Element {String IdentP; struct Element * Next; }; struct Element * T[N]; struct Element * Search(String Id){struct Element * P; P=T[h(Id)]; while (1) {if (P==NULL) return(NULL); else if (IdComp(P-> IdentP, Id)==0) return(P); else P=P-> Next; }}

Занесение элемента в таблицу можно осуществить следующей функцией:

struct Element * Insert(String Id){struct Element * P, H; P=Search(Id); if (P! =NULL) return(P); else {H=H(Id); P=alloc(sizeof(struct Element)); P-> Next=T[H]; T[H]=P; P-> IdentP=Include(Id); } return(P); }

Процедура Include заносит идентификатор в таблицу идентификаторов. Алгоритм иллюстрируется рис. 7.4.


Рис. 7.3.


Рис. 7.4.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.