Saraksts L ir sakārtota elementu virkne . Par saraksta elementu xi var kalpot kaut kāds objekts (piem. skaitlis, vārds, cits saraksts).
Saraksta L garums tiek apzīmēts ar |L| ; līdz ar to || = n
Saraksts var būt tukšs - <>; |<>| = 0.
L[i] ir saraksta i-tais elements, ja ir spēkā nosacījums 0 <= i < |L|
Sarakstu pamatoperācijas
Access(L, i): Atdod L[i] (ja i<0 vai i>|L|-1, tad kļūda).
Length(L): Atdod |L|.
Concat(L1, L2): Kā rezultātu atdod sarakstu L1 un L2 konkatenāciju, t.i.
ja L1 = un L2 = , tad Concat(L1, L2) atdod sarakstu .
MakeEmptyList(): Atdod tukšu sarakstu <>.
IsEmptyList(L): Atdod true, ja |L|=0, citādi - false.
Steks un rinda
Visbiežāk izplatītie sarakstu veidi ir steks un rinda.
Steks ir saraksts, kas var tikt modificēts, pieliekot vai izņemot elementus tikai no viena saraksta gala. Steku parasti sauc par LIFO (last-in-first-out) tipa sarakstu. Katrā konkrētā brīdī no steka var izņemt tikai to elementu, kas tika ielikts pēdējais.
Rinda ir saraksts, kas var tikt modificēts, pieliekot elementus tikai no viena gala (back) un izņemot - no otra gala (front). Rindu parasti sauc par FIFO (first-in-first-out) tipa sarakstu. No rindas var izņemt tikai to elementu, kas uz doto brīdi tajā ir atradies visilgāk.
Top(L): Atdod saraksta L pēdējo elementu; t.i. Access(L, |L|-1) (ja L ir tukšs, tad kļūda).
Pop(L): Izņem un atdod saraksta L pēdējo elementu; t.i. Atdod Top(L) un aizvieto L ar (ja L ir tukšs, tad kļūda).
Push(x, L): Pieliek galā x, t.i. aizvieto L ar Concat(L, ).
MakeEmptyStack(): Atdod tukšu sarakstu <>.
IsEmptyStack(L): Atdod true, ja |L|=0, citādi - false.
Rindas pamatoperācijas
Enqueue(x, L): Pieliek galā x, t.i. aizvieto L ar Concat(L, ).
Dequeue(L): Izņem un atdod saraksta L pēdējo elementu; t.i. Atdod L[0] un aizvieto L ar (ja L ir tukšs, tad kļūda).
Front(L): Atdod saraksta L pirmo elementu; t.i. L[0] (ja L ir tukšs, tad kļūda).
MakeEmptyQueue(): Atdod tukšu sarakstu <>.
IsEmptyQueue(L): Atdod true, ja |L|=0, citādi - false.
Sarakstu reprezentācija.
Galvenie reprezentācijas veidi
Ir divi pamatveidi sarakstu reprezentācijai: nepārtrauktas atmiņas reprezentācija un saišu reprezentācija.
Nepārtrauktas atmiņas reprezentācijā visi saraksta elementi tiek glabāti fiksēta izmēra tabulā. Tabulai ir jābūt tik lielai, lai tajā varētu izvietot visus saraksta elementus. Ir jābūt atbilstībai starp pozīciju tabulā un pozīciju sarakstā.
Saišu reprezentācijā katram elementam atmiņā tiek piekārtotas norādes uz vienu vai abiem kaimiņu elementiem. Izmantojot norādes, mēs varam izstaigāt visu sarakstu.
Saišu reprezentācija ir elastīgāka par nepārtrauktas atmiņas reprezentāciju, jo vieglāk var pielikt un izmest elementu un nav ierobežots saraksta lielums. Savukārt nepārtrauktas atmiņas reprezentācija izmanto mazāku atmiņas daudzumu viena elementa reprezentācijai un nodrošina lielāku pieejas ātrumu konkrētam elementam.…
