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

i:=1;

while not (table[i].key=ключ) do {это условие хотя бы раз выполняется}

i:=i+1;

if i=последний+1 then write(‘нет записи с ‘,ключ) else table[i].тело:=тело

end

Операции вставить и изменить имеют сложность K/2, где К - количество элементов в таблице.

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

var i:integer

begin {найти такое i: table[i].ключ=ключ и удалить этот элемент из table}

i:=1; | процедура

table[последний+1].ключ:=ключ; |

while table[i].ключ<>ключ do i:=i+1{условие инвариантности цикла}| поиска

if i<=последний then begin

while i<>последний do begin

table[i]:=table[i+1];

i:=i+1

end;

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

end else write(‘Такого элемента нет’)

end.

Сложность: К/2 - поиск

К/2 - сдвиг

К/2+К/2=К, то есть сложность линейна

body=...

key=...

type ссылка=звено;

звено=record ключ:key;

тело:body;

связь:ссылка