Послідовні таблиці.

Будемо розглядати невідсортоване таблиці.

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) Для послідовних таблиць зниження складності можна досягти за рахунок використання інформації про зустрічальності ключів. Операцію пошуку можна скоротити за рахунок скорочення довжини шляхів пошуку.

Список літератури

Для підготовки даної роботи були використані матеріали з сайту http://www.ergeal.ru/