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

       

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


Только что описанная схема страдает одним недостатком - возможностью переполнения таблицы. Рассмотрим ее модификацию, когда все элементы, имеющие одинаковое значения (первичной) функции расстановки, связываются в список (при этом отпадает необходимость использования функций 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. 



Содержание раздела