Последовательные таблицы.
Будем рассматривать неотсортированные таблицы.
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) Для последовательных
таблиц понижение сложности можно достичь за счет использования информации о
встречаемости ключей. Операцию поиска можно сократить за счёт сокращения длины
путей поиска.
Список литературы
Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/