Шпаргалка: Последовательные таблицы

dispose(текущий.связь)

end

else begin

предок.связь:=текущий.связь;

dispose(текущий);

dispose(последний.связь)

end

end

Сложность = сложности поиска по линейному списку К/2

Таблицу нужно формировать так, чтобы наиболее часто встречаемые ключи находились в начале списка. Зная частоту встреча7емости ключей и отсортировав таблицу можно улучшить эффективность.

Сортированные последовательные таблицы.

Типы ключа и тела далее просты.

procedure вставить(var таблица: table; var последний: integer; ключ: key; тело:body)

var i:integer;

begin

if последний = N then write(‘таблица заполнена’) else begin

i:=последний;

{считаем, что все ключи упорядоченны по возрастанию, то есть

I(Kj)=I(Kt)+1

(Kj, Kt)R и не s: (Kj, Ks)R (Ks, Kt)R}

while (i>=1) and (таблица[i].ключ>ключ) do begin

таблица[i+1].ключ:=таблица[i].ключ;

таблица[i+1].тело:=таблица[i].тело;

i:=i-1

end;

таблица[i].тело:=тело;

таблица[i].ключ:=ключ

end

end