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

Будем рассматривать неотсортированные таблицы.

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<=последний 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;

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

end;

var таблица:ссылка;

procedure ВСТАВИТЬ(var таблица,последний:ссылка; ключ: key; тело:body)

var элемент:звено;

begin

new(элемент);

элемент.ключ:=ключ;

элемент.тело:=тело;

элемент.связь:=nil;

последний.связь:=элемент;

последний:=элемент;

if таблица=nil then таблица:=элемент else последний.связь:=элемент;

последний:=элемент

end

Сложность не зависит от длины таблицы

procedure изменить (var таблица, последний:ссылка; ключ:key; тело:body)

{найти таблица.ключ = ключ и заменить таблица.тело на тело}

var следующий:ссылка;

begin {поиск элемента с заданным ключом}

if таблица<> nil then begin

new(следующий);

следующий.ключ:=ключ:

следующий.связь:= nil;

последний.связь:=следующий;

следующий:=таблица;

end;

{поиск}

while следующий.ключ<> ключ do следующий:=следующий.связь;

if последний.связь<>следующий then следующий.тело:=тело

else write(‘элемент не найден’);

{нужно уничтожить сгенерированный элемент}

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

end

Сложность К/2

procedure удалить(var таблица, последний: ссылка; ключ: key);

var текущий: ссылка;

{если элемент последний или первый, то рассмотрим отдельно, иначе сдвинем ссылку и освободим память}

if {таблица пуста} then write (‘Таблица пуста’) else

if {в таблице один элемент} then

if {единственный элемент есть искомый} then {сделать таблицу пустой}

else write(‘нет искомого элемента в таблице’)

else write (‘нет искомого элемента в таблице’)

else {поиск в таблице}

new(текущий);

текущий.ключ=ключ;

текущий.связь:=nil;

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

текущий:=таблица;

while текущий.ключ<> ключ do begin

предок:=текущий;

текущий:=текущий.связь

end

if {первый элемент - искомый} then begin

текущий:=таблица;

таблица:= текущий.связь;

dispose(текущий)

end

if {последний- искомый (текущий=последний)} then begin

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

последний.связь:=nil;

dispose(текущий);

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

Сложность операции вставки для отсортированных таблиц возросла.

Выводы:

1) основная сложность операций в таблице - поиск. Для данной - линейна.

2)векторное представление хорошо, когда операции удаления и вставки относительно редки, а, если же нет, то предпочтение нужно отдавать списковому представлению.

3) Для последовательных таблиц понижение сложности можно достичь за счет использования информации о встречаемости ключей. Операцию поиска можно сократить за счёт сокращения длины путей пои