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

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

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

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

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/