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:
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.
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 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 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 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.
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 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.
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.
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.
alena *
alfons *
cecilka *
dalimil *
danuse *
eric *
franta *
hugo *
jana *
jaromir *
jirina *
john *
judita *
karel *
ludek *
patrik *
rudolf *
zita *
zuzana *
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