Шпаргалка: Последовательные таблицы

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

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

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/