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:
Při inicializaci tabulky je nastaven maximální počet položek v tabulce a ostatní dva prvky řídící struktury jsou vynulovány.
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í 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ž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 tabulce roven skutečnému počtu položek v tabulce.
Příklad vstupněsekvenční tabulky je na obrázku .
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.
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.
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.
alena *
jirina *
alfons *
danuse *
hugo *
john *
zuzana *
zita *
judita *
jana *
jaromir *
cecilka *
franta *
karel *
ludek *
eric *
dalimil *
rudolf *
patrik *
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