Tabulky
Seřazená tabulka
 Tisk

Seřazená tabulka


Seřazená tabulka je dalším typem. Položky jsou uspořádány v tabulce vzestupně podle jejich klíče. Rušení se provádí opět označením neplatnosti. Problém vzniká při vkládání. Při každém vložení bychom potřebovali nalézt vhodné místo pro vložení a, pokud není náhodou volné (zrušená položka), udělat místo pro vložení přesunem zbývající části tabulky o jedno místo. To by podstatně snižovalo rychlost při vkládání. Proto se tabulka rozdělí na seřazenou část a neseřazenou část. Při reorganizaci se neseřazená část seřadí a její položky se zařadí na příslušné místo v seřazené části.


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



Řídící struktura tabulky obsahuje čtyři prvky:



Inicializace tabulky

Při inicializaci tabulky je nastaven maximální počet položek v tabulce a ostatní tři 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 neseřazené části tabulky 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 alespoň částečná reorganizace tabulky, kdy jsou vypuštěna volná místa. Pokud je potom index poslední položky v neseřazené části tabulky 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í položky

Vyhledání položky podle zadaného klíče se provádí v seřazené části tzv. půlením intervalu a v neseřazené části sekvenčním způsobem. Vyhledání půlením intervalu spočívá v tom, že se nastaví meze - první a poslední položka seřazené části. Pak se vyhledá prvek v polovině nastavených mezí a jeho klíč se porovnává s hledaným klíčem. Pokud dojde ke shodě, vyhledání končí, jinak se pokračuje buď v prohledání tak, že pokud je hledaný klíč menší než klíč prvku v polovině nastavených mezí, nastaví se horní mez na index prvku v polovině nastavených mezí snížený o jedničku, jinak se nastaví dolní mez na index prvku v polovině nastavených mezí zvýšený o jedničku. Opět se vybere prvek v polovině zadaných mezí. To se provádí tak dlouho dokud se prvek buď nenalezne, nebo je horní mez je menší než dolní mez. Neseřazená část se prohledá sekvenčně.

Pokud označíme index poslední položky v seřazené části tabulce N, pak doba prohledávání seřazené tabulky je průměrně úměrná log2 N. Z toho vyplývá, že jde o velmi rychlý algoritmus a že je třeba se snažit omezit délku neseřazené části tabulky, neboť zde je doba vyhledání lineárně závislá na počtu prvků.


Změna položky

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.


Zrušení položky

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 seřazené části tabulky roven skutečnému počtu položek v tabulce.

Neseřazená část buď může být zařazena hned za seřazenou, nebo může být na konci.


Seřazené tabulky se používají, pokud je třeba rychle vyhledávat danou položku a také zpracovávat metodou zpracuj nejbližší další položku vzestupně. Příklad seřazené tabulky je na následujícím obrázku.

Algoritmus prohledání seřazené tabulky


Algoritmus má dvě části:



Prohledání neseřazené části bylo ukázáno v minulém článku.

Prohledání seřazené části je opět demonstrování na prohledání souboru s typem seřazeného podle klíče.



unit definice;


// Autor: Kopeček       Datum: 30.10.2003

// Funkce: vyhledani půlením intervalu - 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 puleni_f;


// Autor: Kopeček       Datum: 30.10.2003

// Funkce: vyhledání půlením intervalu - vlastní algoritmus

//

// Podprogramy:

//      rovno ... porovná dva řetezce na rovnost

//      mensi ... porovná dva řetezce na relaci mensi

//      puleni... vlastní algoritmus

interface

uses

    definice;

function puleni(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 mensi(a,b:t_jmeno):boolean;

var

    i:integer;

    bool:boolean;

begin

    bool := false;

    i:= 1;

    while (i <= NAME_LEN) and   // maximalně celá délka řetezce

          not bool and          // jakmile je jeden znak menší

          not (a[i] > b[i])do begin // nebo vetší, pak se končí

        if a[i] < b[i] then bool := true;

        inc(i)

    end;

    mensi := bool;

end;


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

// Algoritmus:

//      dolmí mez hledání se nastaví na začátek souboru - 0. zaznam

//      horní mez hledaní se nastaví na poslední záznam / filesize(f) - 1

//      příznak nalezení se nastaví na nenalezeno

//      tak dlouho, pokud není dolní mez větší nez horní a nic nebylo nalezeno se

//      provadí:

//            - nastaví se střed intervalu na polovinu horní a dolní meze

//            - prečte se záznam ve středu intervalu

//            - pokud je prečtený záznam ten hledaný, pak se nastaví příznak

//              nalezení na nalezeno

//            - pokud je prečtený záznam menší než hledaný, pak se dolní mez

//              hledání nastaví na o 1 vyšší, než je číslo přečteného záznamu

//            - pokud je přečtený záznam větší než hledaný, pak se horní mez

//              hledání nastaví na o 1 nižší, než je číslo přečteného záznamu

//      výsledkem je buď nalezené číslo záznamu nebo -1

var

    dolni,horni,stred:integer;

    nalezeno :boolean;

    f_jmeno :t_jmena;

begin

    dolni := 0;

    stred := -1;

    horni := filesize(f)-1;

    nalezeno := false;

    while not (dolni > horni) and not nalezeno do begin

        stred := (dolni + horni) div 2;

        seek(f,stred);

        read(f,f_jmeno);

        if rovno(f_jmeno.jmeno,s) then begin

            nalezeno := true;

        end

        else if mensi(f_jmeno.jmeno,s) then begin

            dolni := stred +1;

        end

        else begin

            horni := stred -1;

        end;

    end;

    if not nalezeno then puleni := -1

                    else puleni := stred;

end;


end.



Hlavni program


program puleni_p;


// Autor: Kopeček       Datum: 30.10.2003

// Funkce: vyhledaní půlením intervalu - hlavní program

//

// Parametry: žádné, data se čtou ze seřazeneho souboru jmena.sor

//

// Poznámka: Program funguje spravně jen pro jména ze

//           - samých malých písmen

//           - samých velkých písmen

//           - samých číslic


uses

SysUtils,

definice in 'definice.pas',

puleni_f in 'puleni_f.pas';


var

    f:t_soubor;

    jmeno:t_jmeno;

    s:string[NAME_LEN];

    i,pul:integer;

begin

    assign(f,'jmena.sor');

    reset(f);

    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];

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

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

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

    until s = '.';

    close(f);

end.



Testovací data

alena                    *

alfons                   *

cecilka                  *

dalimil                  *

danuse                   *

eric                     *

franta                   *

hugo                     *

jana                     *

jaromir                  *

jirina                   *

john                     *

judita                   *

karel                    *

ludek                    *

patrik                   *

rudolf                   *

zita                     *

zuzana                   *


Výsledky programu


zadejte jmeno nebo ".":alena

zadane jmeno alena                     je ve 0. zaznamu

zadejte jmeno nebo ".":john

zadane jmeno john                      je ve 11. zaznamu

zadejte jmeno nebo ".":zuzana

zadane jmeno zuzana                    je ve 18. zaznamu

zadejte jmeno nebo ".":xxxxxx

zadane jmeno xxxxxx                    neni v souboru

zadejte jmeno nebo ".":.

zadane jmeno .                         neni v souboru