Последовательные таблицы

Будем рассматривать неотсортированные таблицы.
K - количество элементов в таблице
N - длина вектора представления элементов таблицы
Векторное представление:
type элемент = record key ... body ...;
таблица = array [1..N] of элемент
end
key=...
body=...
Время поиска K/2
Списковое представление:
type элемент = record key... body ...;
связь=элемент;
procedure вставить (var table:таблица; var ключ:key; тело:body)
begin
if последний>=N then write(‘нет места’) else begin
последний:=последний+1;
table[последний].key:=ключ;
table[последний].body:=тело;
end;
with table[последний] do
key:=ключ;
body:=тело;
end
end
Предполагаем, что длина ключа и тела одна и та же.
procedure изменить(var table:таблица; var последний:integer)
var i,j:integer;
begin
table[последний+1].key:=ключ;
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=1) and (таблица[i].ключ>ключ) do begin
таблица[i+1].ключ:=таблица[i].ключ;
таблица[i+1].тело:=таблица[i].тело;
i:=i-1
end;
таблица[i].тело:=тело;
таблица[i].ключ:=ключ
end
end
Сложность операции вставки для отсортированных таблиц возросла.
Выводы:
1) основная сложность операций в таблице - поиск. Для данной - линейна.
2)векторное представление хорошо, когда операции удаления и вставки относительно редки, а, если же нет, то предпочтение нужно отдавать списковому представлению.
3) Для последовательных таблиц понижение сложности можно достичь за счет использования информации о встречаемости ключей. Операцию поиска можно сократить за счёт сокращения длины путей поиска.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию