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

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

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/