Sémantická specifikace ATD Seznam
Implementace jednotlivých operací

Seznam je jednou z nejobecnějších datových struktur, používaných zejména v oblasti nenumerického zpracování. Je to lineární, homogenní, obecně dynamická datová struktura představovaná posloupností jednotlivých prvků vytvářejících seznam. Lineárnost seznamu je dána tím, že ke každému prvku seznamu lze určit jediný bezprostředně následující prvek.

Značení:
Pro účelné stanovení množiny operací nad lineárním seznamem se definuje zvláštní vlastnost seznamu; seznam buď obsahuje jeden z prvků, který je aktivní, a pak je i seznam aktivní, nebo neobsahuje žádný aktivní prvek a pak je seznam neaktivní. Pro účely sémantické specifikace popisem účinků jednotlivých operací zavedeme tuto notaci:

< >	prázdný seznam (je neaktivní, neobsahuje žádný aktivní prvek).
< A B C >	neaktivní seznam sestávající z posloupnosti prvků A, B a C. (Žádný prvek není aktivní)
< A B C >	aktivní seznam prvků A, B a C; prvek A je aktivní (je podtržen)
L	libovolný neprázdný neaktivní seznam.

Nad typem SEZNAM jsou definovány následující operace:

LISTINIT	Vytvoř prázdný seznam
FIRST	Aktivní bude první prvek seznamu
SUCC	Aktivní bude prvek následující za aktivním prvkem
POSTDELETE	Zruš prvek za aktivním prvkem
FIRSTDELETE	Zruš první prvek seznamu
COPY	Získej hodnotu aktivního prvku
COPYFIRST	Získej hodnotu prvního prvku
POSTINSERT	Vlož nový prvek za aktivní prvek
INSERTFIRST	Vlož nový prvek na začátek seznamu
ACTUALIZE	Dosaď novou hodnotu do aktivního prvku
ACTIVE	Dotaz, zda seznam obsahuje aktivní prvek

Začátek
Implementace jednotlivých operací

LISTINIT

FIRST

FIRST (< >) = < >                       FIRST (< A >) = < A >           FIRST (< A >) = < A >
FIRST (< ABL >) = < ABL >               FIRST (< AL >) = < AL >	        FIRST (< AL >) = < AL >
FIRST (< AL1BL2 >) = < AL1BL2 >         FIRST (< ALB >) = < ALB >

SUCC

SUCC (< >) = < >                        SUCC (< A >) = < A >		SUCC (< L >) = < L >
SUCC (< ABL >) = < ABL >  		SUCC (< LAB >) = < LAB >	SUCC (< LA >) = < LA >
SUCC (< L1ABL2 >) = < L1ABL2 >

POSTDELETE

POSTDELETE (< >) = < >		        POSTDELETE (< L >) = < L >
POSTDELETE (< A >) = < A >              POSTDELETE (< AB >) = < A >
POSTDELETE (< L1ABL2 >) = < L1AL2 >     POSTDELETE (< LAB >) = < LA >
POSTDELETE (< LA >) = < LA >

ACTUALIZE

ACTUALIZE (A,< >) = < > 	        ACTUALIZE (A,< L >) = < L >
ACTUALIZE (A,< B >) = < A >             ACTUALIZE (A,< BL >) = < AL >
ACTUALIZE (A,< L1BL2 >) = < L1AL2 > 	ACTUALIZE (A,< LB >) = < LA >

DELETEFIRST

DELETEFIRST (< >) = < > 		DELETEFIRST (< A >) = < >
DELETEFIRST (< A >) = < >               DELETEFIRST (< AL >) = < L >
DELETEFIRST (< AL >) = < L >

COPY

COPY (< >) = error		COPY (< L >) = error
COPY (< A >) = A		COPY (< AL >) = A
COPY (< L1AL2 >) = A 		COPY (< LA >) = A

POSTINSERT

POSTINSERT (A,< >) = < >		POSTINSERT (A,< L >) = < L >
POSTINSERT (A,< BL >) = < BAL >		POSTINSERT (A,< L1BL2 >) = < L1BAL2 >
POSTINSERT (A,< LB >) = < LBA >		POSTINSERT (A,< B >) = < BA >

INSERTFIRST

INSERTFIRST (A,< >) = < A >		INSERTFIRST (A,< L >) = < AL >
INSERTFIRST (A,< BL >) = < ABL >	INSERTFIRST (A,< L1BL2 >) = < AL1BL2 >
INSERTFIRST (A,< LB >) = < ALB > 	INSERTFIRST (A,< B >) = < AB >

COPYFIRST

 COPYFIRST (< >) = error	COPYFIRST (< A >) = A 	 	COPYFIRST (< A >) = A
 COPYFIRST (< AL >) = A	 	COPYFIRST (< AL >) = A

ACTIVE

ACTIVE (< >) = false		ACTIVE (< L >) = false
ACTIVE (< A >) = true		ACTIVE (< AL >) = true
ACTIVE (< L1AL2 >) = true	ACTIVE (< LA >) = true

Začátek
Sémantická specifikace ATD Seznam

Užité konstanty a typy:



type tData=string;                              {Muze byt libovolny}
     tUkPrvek=^tPrvek;
     tPrvek=record
              Data:tData;
              UkDalsi:tUkPrvek;
            end;
     tLIST=record                               {Vlastni ATD Seznam}
             UkAktivni,UkZacatek:tUkPrvek;
           end;
  

Algoritmy:

---

Procedure ListInit(var Seznam:tList);
{Vytvor prazdny seznam}
begin {ListInit}
  with Seznam do
  begin
    UkZacatek:=nil;
    UkAktivni:=nil;
  end;
end; {ListInit}

Procedure First(var Seznam:tList);
{Aktivni bude prvni prvek seznamu}
begin {First}
  with Seznam do UkAktivni:=UkZacatek;
end; {First}

Procedure LSucc(var Seznam:tList);
{Aktivni bude prvek za aktivnim prvkem.}
begin {LSucc}
  with Seznam do if UkAktivni<>nil then UkAktivni:=UkAktivni^.UkDalsi;
end; {LSucc}

Procedure PostDelete(var Seznam:tList);
{Smaz prvek za aktivnim prvkem}
var PomUk:tUkPrvek;
begin {PostDelete}
  with Seznam do
  if UkAktivni<>nil then
  begin
    if UkAktivni^.UkDalsi<>nil then
    begin
      PomUk:=UkAktivni^.UkDalsi^.UkDalsi;
      Dispose(UkAktivni^.UkDalsi);
      UkAktivni^.UkDalsi:=PomUk;
    end;
  end;
end; {PostDelete}

Procedure Actualize(var Seznam:tList;Data:tData);
{Dosad novou hodnotu do aktivniho prvku}
begin {Actualize}
  with Seznam do if UkAktivni<>nil then UkAktivni^.Data:=Data;
end; {Actualize}

Procedure DeleteFirst(var Seznam:tList);
{Smaz prvni prvek seznamu}
var PomUk:tUkPrvek;
begin {DeleteFirst}
  with Seznam do if UkZacatek<>nil then
  begin
    if UkAktivni=UkZacatek then UkAktivni:=nil;
    PomUk:=UkZacatek^.UkDalsi;
    Dispose(UkZacatek);
    UkZacatek:=PomUk;
  end;
end; {DeleteFirst}

Function LCopy(var Seznam:tList;var Error:boolean):tData;
{Vraci hodnotu aktivniho prvku. Neni-li prvek aktivni, vraci chybu}
begin {LCopy}
  with Seznam do
  begin
    Error:=UkAktivni=nil;
    if not Error then LCopy:=UkAktivni^.Data;
  end;
end; {LCopy}

Procedure PostInsert(var Seznam:tList;Data:tData);
{Vlozi prvek za aktivni prvek}
var PomUk:tUkPrvek;
begin {PostInsert}
  with Seznam do if UkAktivni<>nil then
  begin
    New(PomUk);
    PomUk^.Data:=Data;
    PomUk^.UkDalsi:=UkAktivni^.UkDalsi;
    UkAktivni^.UkDalsi:=PomUk;
  end;
end; {PostInsert}

Procedure InsertFirst(var Seznam:tList;Data:tData);
{Vlozi prvni prvek do seznamu}
var PomUk:tUkPrvek;
begin {InsertFirst}
  with Seznam do
  begin
    New(PomUk);
    PomUk^.Data:=Data;
    PomUk^.UkDalsi:=UkZacatek;
    UkZacatek:=PomUk;
  end;
end; {InsertFirst}

Function CopyFirst(var Seznam:tList;var Error:boolean):tData;
{Vraci hodnotu prvniho prvku. Je-li seznam prazdny, vraci chybu}
begin {CopyFirst}
  with Seznam do
  begin
    Error:=UkZacatek=nil;
    if not Error then CopyFirst:=UkZacatek^.Data;
  end;
end; {CopyFirst}

Function Active(var Seznam:tList):boolean;
{Dotaz, zda seznam obsahuje aktivni prvek}
begin {Active}
  Active:= Seznam.UkAktivni<>nil;
end; {Active}

Na začátek stránky

---

	Kontakt	Stanislav Chromčák 11. 2. 2000
	Originální umístění této stránky je:
	http://freeweb.coco.cz/ANCHOR/pascal/data/seznam.htm