7. Статические структуры данных.

Их представление, выделение памяти.

Отгосятся к разряду непримитивных структур, которые

содерж. структурир. множество примитивных. Память получают

автоматически, при компил. или при входе в блок.Могут представл. изменч. объекты(дин. массивы).Физ. представл. не

соотв. логическ. Физ. структ. ставится в соотв. дескриптор.

Он состоит из полей, которые зависят от описыв. структуры.

Дескриптор невидим для программиста. Создаётся компилятором.Стат. структуры в ЯП связаны со структурир. типами – массивами, записями, множествами.

8. Назначение хеширования данных.

Открытое хеширование.

Осн. идея метода закл. в том, что мн-во данных разбивается на конечн. число классов. для В классов от 0 до В-1 строится ф-ия Н,что

для любого эл-та Х из исх. мн-ва принимает значение 0..В-1, соотв. классу, котор. принадл. Х.

Х-ключ хэш ф-ии. Результат – значение. Классы- сегменты.

Хэш ф-ия плоха, если на один Х – несколько знач. – коллизия.

Если сегменты одинаковы, то списки должны быть max короткими. Средняя длина – N/B. N- кол-во эл-тов в исх. мн-ве.

Н следует выбирать, чтобы поровну распределяла эл-ты по сегментам

Пример:Представл. символов в виде чисел. В качестве Н используется Ord. Если Х-ключ, то можно использовать ф-ию, в котор. использ. коды символов, результ. делится на В и берётся остаток от деления, указыв. номер сегмента.

function h(x:nametype):0..B-1;

var

I,sum:integer;

begin

sum:=0;

for i:=1 to 10 do

sum:=sum+ord(x[i]); {Массив ключей -10}

h:=sum mod B;

end;

9.Назначение хеширования данных. Закрытое хеширование. Привести пример организации данных.

При закр. хешир. в табл. сегментов хранятся сами эл-ты, а не заголовки их списков. При закрытом применяется линейное опробование.

Если пытаться поместить эл-т Х в сегмент Н(Х), который занят, то выбир. послед. номеров других сегментов Н1(Х),Н2(Х), куда можно поместить Х. Каждая Н1,Н2… проверяется, пока не найдётся место. Если места нет – таблица заполнена.

Пример: a,b,c,d имеют значения 3,0,4,3.

a и d претендуют на 3-е место. Хотим вставить d в 3, но он занят, поэтому проверяем 4,5,6,7,0,1,2. Применяем H1 – 4 занят. Применяем Н2 – 5 свободен – вставляем. При поиске необходимо просмотреть все места для Х, пока не найдём Х или пустую ячейку(Х нет).

10.Разрешение коллизий в случае закрытого хеширования.

Коллизии разрешаются с помощью линейного опробования или открытого хеширования. Линейное опробование сводится к перебору эл-тов с некотор. шагом. a=h(key)+c*i. i-номер попытки разрешения коллизии. Квадр. опробование уменьшает кол-во проб благодаря нелинейности a=h(key2)+c*i+d*sqr(i). Вставка:

i:=0

a:=h(key)+i*c

Если t(a)=свободно, то t(a):=key. Стоп.

i:=i+1. Перейти к шагу 2.

Аналогично – поиск.Если key – стоп. Эл-т найден. Если свободно – стоп – эл-т не найден.

Удаление не аналогично вставке.Если просто удалить, то алгоритм будет останавливаться на первом найденном. Поэтому используется метка «удалено». Она интерпретируется как занято при поиске, и свободно при записи.Также существуют способы просмотра до конца и запоминания всех ключей за удаляемым в таблице, но они неэффективны.По мере заполнения таблицы может произойти превышение адресного пространства. Для избежания можно увеличить размер таблицы или использовать закольцовывание.

Вставка.

1)i:=0

2)a:=((h(key)+c*i)div n+(h(key)+c*i)mod n)mod n

3)Если t(a) =свободно или t(a)=удалено,то t(a):=key.Стоп. Добавлен.

3)Если t(a)=key, то t(a):=удалено. Стоп удалён.{Удаление}

3)Если t(a)=key, то стоп. найден. {Поиск}

4)Если i>m, то стоп. Рехеширование.

4)Если t(a)=свободно или i>m, то стоп. Не найден.{Удаление,поиск}

5)i:=i+1.К шагу 2.