Tabulky
Vstupněsekvenční tabulka
 Tisk

Vstupněsekvenční tabulka


Vstupněsekvenční tabulka je nejjednodušším typem. Položky v tabulce nejsou organizovány podle žádného klíče, ale jsou zaznamenávány v pořadí jejich příchodu.


Výhodou vstupněsekvenčních tabulek je jejich jednoduchost. Používají se zejména tam, kde se vkládá velké množství položek a zpracovává se většina položek sekvenčním způsobem.


Tabulku lze implementovat dostatečně dlouhých polem. Prvkem tohoto pole je datový typ záznam, který obsahuje:



Indikace platnosti položky se používá pro urychlení rušení. Při rušení položky se nemusí posouvat následující položky. Stačí pouze označit příslušnou položku za zrušenou. Fyzické vypuštění se provede operací, která se nazývá reorganizace tabulky. Ta se provádí v době nízkého zatížení počítače nebo při určitém stavu zaplnění tabulky.


Dále je vhodné definovat řídící strukturu tabulky, která obsahuje tři prvky:




Iniciace tabulky

Při inicializaci tabulky je nastaven maximální počet položek v tabulce a ostatní dva prvky řídící struktury jsou vynulovány.


Vložení do tabulky

Při vložení nové položky se kontroluje, zda index poslední položky v tabulce není roven maximálnímu počtu položek. Pokud ano a skutečný počet položek je menší, než maximální, pak se musí provést tzv. reorganizace tabulky, kdy jsou vypuštěna volná místa. Pokud je potom index poslední položky v tabulce menší, než maximální počet položek, vloží se nová položka za poslední, její indikace se nastaví na platnou a skutečný počet a index poslední položky se zvýší o jedna.


Vyhledání v tabulce

Vyhledání položky podle zadaného klíče se provádí sekvenčním způsobem. Postupně se zadaný klíč porovnává s klíči v tabulce počínaje prvním záznam, přičemž se tabulce vynechávají položky s indikací zrušení. Pokud se nalezne shoda, položka je nalezena, pokud se dosáhne indexu poslední položky a klíč se neshoduje, položka není v tabulce. Pokud označíme index poslední položky v tabulce N, pak doba prohledávání vstupněsekvenční tabulky je průměrně úměrná N/2, pokud položka existuje a je úměrná N, pokud položka neexistuje.


Změna položka v tabulce

Změna položky spočívá ve vyhledání podle klíče a změně uživatelské informace. Řídící struktura tabulky zůstává nezměněna.


Rušení položky z tabulky

Rušení položky spočívá ve vyhledání podle klíče, nastavení indikace na zrušení a snížení skutečného počtu položek v tabulce o jednu.


Reorganizace tabulky

Po reorganizaci je index poslední položky v tabulce roven skutečnému počtu položek v tabulce.


Příklad vstupněsekvenční tabulky je na obrázku .

Algoritmus prohledání vstupněsekvenční tabulky


Algoritmus pro nalezení záznamu v tabulce je demonstrován na nalezení záznamu v souboru s udaným typem. Doba hledání je úměrná počtu záznamů v souboru.


unit definice;


// Autor: Kopecek       Datum: 3.10.2006

// Funkce: sekvencni vyhledani - definice


interface

const

    NAME_LEN = 25;

type

    t_jmeno = array[1..NAME_LEN] of char;

    t_jmena = record

                jmeno: t_jmeno;

                filler:array[0..2] of char;

              end;

     t_soubor = file of t_jmena;

implementation


end.


Vlastní algoritmus hledání


unit sekvencni_f;


// Autor: Kopecek       Datum: 3.10.2006

// Funkce: sekvencni vyhledani - vlastni algoritmus


//

// Podprogramy:

//      rovno     ... porovna dva retezce na rovnost

//      sekvencni ... vlastni algoritmus

interface

uses

    definice;

function sekvencni(var f:t_soubor;s:t_jmeno): integer;


implementation

function rovno(a,b:t_jmeno):boolean;

var

    i:integer;

begin

    rovno := true;

    for i := 1 to NAME_LEN do

        if a[i] <> b[i] then rovno := false;

end;



function sekvencni(var f:t_soubor;s:t_jmeno): integer;

// Algoritmus:

//      ukazatel zaznamu se nastavi na -1

//      priznak nalezeni se nastavi na nenalezeno

//      tak dlouho pokud neni dosazeno konce souboru nebo neni nalezeno se

//      provadi:

//            - nastavi ukazatel zaznamu na dalsi

//            - precte se dalsi zaznam

//            - pokud je precteny zaznam ten hledany, pak se nastavi priznak

//              nalezeni na nalezeno

//

//      vysledkem je bud nalezene cislo zaznamu nebo -1

var

    nalezeno :boolean;

    f_jmeno :t_jmena;

    zaznam   :integer;

begin

    nalezeno := false;

    zaznam   := -1;

    reset(f);

    while not eof(f) and not nalezeno do begin

        inc(zaznam);

        read(f,f_jmeno);

        if rovno(f_jmeno.jmeno,s) then begin

            nalezeno := true;

        end

    end;

    if not nalezeno then sekvencni := -1

                    else sekvencni := zaznam;

end;


end.


Hlavni program


program sekvencni_p;


// Autor: Kopecek       Datum: 3.10.2006

// Funkce: sekvencni vyhledani - hlavni program

//

// Parametry: zadne, data se ctou ze serazeneho souboru jmena.txt

//

// Poznamka: Program funguje spravne jen pro jmena ze

//           - samych malych pismen

//           - samych velkych pismen

//           - samych cislic


uses

SysUtils,

definice in 'definice.pas',

sekvencni_f in 'sekvencni_f.pas';


var

    f:t_soubor;

    jmeno:t_jmeno;

    s:string[NAME_LEN];

    i,sek:integer;

begin

    assign(f,'jmena.txt');

    repeat

        writeln('zadejte jmeno nebo ".":');

        readln(s);

        for i := 1 to NAME_LEN do jmeno[i] := ' ';

        for i := 1 to length(s) do jmeno[i] := s[i];

        sek := sekvencni(f,jmeno); // vraci -1 pri neuspechu, jinak cislo zaznamu

        if sek >= 0 then writeln('zadane jmeno ',jmeno,' je ve ',sek,'. zaznamu')

        else writeln('zadane jmeno ',jmeno,' neni v souboru');

    until s = '.';

    close(f);

end.


Testovací data


alena                    *

jirina                   *

alfons                   *

danuse                   *

hugo                     *

john                     *

zuzana                   *

zita                     *

judita                   *

jana                     *

jaromir                  *

cecilka                  *

franta                   *

karel                    *

ludek                    *

eric                     *

dalimil                  *

rudolf                   *

patrik                   *


Výsledky programu


zadejte jmeno nebo ".":eric

zadane jmeno eric                      je ve 15. zaznamu

zadejte jmeno nebo ".":john

zadane jmeno john                      je ve 5. zaznamu

zadejte jmeno nebo ".":alena

zadane jmeno alena                     je ve 0. zaznamu

zadejte jmeno nebo ".":xxxxxxxx

zadane jmeno xxxxxxxx                  neni v souboru

zadejte jmeno nebo ".":

zadane jmeno .                         neni v souboru