Pievienot darbus Atzīmētie0
Darbs ir veiksmīgi atzīmēts!

Atzīmētie darbi

Skatītie0

Skatītie darbi

Grozs0
Darbs ir sekmīgi pievienots grozam!

Grozs

Reģistrēties

interneta bibliotēka
Atlants.lv bibliotēka
6,99 € Ielikt grozā
Gribi lētāk?
Identifikators:461044
 
Autors:
Vērtējums:
Publicēts: 07.12.2005.
Valoda: Latviešu
Līmenis: Augstskolas
Literatūras saraksts: Nav
Atsauces: Nav
SatursAizvērt
Nr. Sadaļas nosaukums  Lpp.
1.  Saraksts (List)    4
1.1.  Saraksta jēdziens un operācijas ar to    4
1.1.1.  Saraksta jēdziens    4
1.1.2.  Sarakstu pamatoperācijas    4
1.1.3.  Steks un rinda    4
1.1.4.  Steka pamatoperācijas    5
1.1.5.  Rindas pamatoperācijas    5
1.2.  Sarakstu reprezentācija    5
1.2.1.  Galvenie reprezentācijas veidi    5
1.2.2.  Steka reprezentācija nepārtrauktā atmiņā    6
1.2.3.  Rindas reprezentācija nepārtrauktā atmiņā    7
1.2.4.  Steka reprezentācija saistītā atmiņā    8
1.2.5.  Rindas reprezentācija saistītā atmiņā    9
1.3.  Saraksta apstaigāšana    10
1.4.  Vienvirziena apstaigāšanas algoritms    10
1.5.  Divvirzienu apstaigāšanas algoritms    11
1.6.  Dubultsaišu saraksts    12
2.  Koks (tree)    15
2.1.  Koka jēdziens un saistītās pamatdefinīcijas    15
2.2.  Koku pamatveidi    16
2.3.  Pamatoperācijas ar kokiem    16
2.4.  Koka lietošanas piemērs    17
2.5.  Koka apstaigāšana    17
2.5.1.  Postorder apstaigāšana    17
2.5.2.  Preorder apstaigāšana    18
2.5.3.  Inorder apstaigāšana    18
2.6.  Koku implementācija    19
2.6.1.  Bināra koka implementācija    19
2.6.2.  Sakārtota koka implementācija    19
2.6.3.  Pilnīga bināra koka inplementācija    19
2.7.  Koku apstaigāšanas implemetācija    20
2.7.1.  Uz steku bāzēta apstaigāšana    20
2.7.2.  Apstaigāšana ar saišu inversiju    20
2.7.3.  Koka skanēšana konstantā telpā    24
2.7.4.  Pavedienkoks    25
3.  Grafs (Graph)    28
3.1  . Pamatjēdzieni    28
3.2.  Pamatoperācijas    28
3.3.  Grafu reprezentācija    29
3.3.1.  Piemērs    29
3.3.2.  Grafu incidences matricas    29
3.3.3.  Atbilstību matricas    30
3.3.4.  Savienoto virsotņu pāru saraksts    31
3.3.5.  Incidences saraksti    31
3.4.  Meklēšana grafā    32
3.4.1.  Meklēšana plašumā (Breadth-First search)    32
3.4.2.  Meklēšana dziļumā (Depth-First search)    33
3.4.3.  Topoloģiskā kārtošana    34
4.  Kārtošana    35
4.1.  Kātošanas metožu klasificēšanas kritēriji    35
4.2.  Tabulā esošu datu kārtošana    36
4.2.1.  Kārtošanas algoritms ar iespraušanu    36
4.2.2.  Šella algoritms    36
4.2.3.  Kārtošana ar izvēli    37
4.3.  Rinda ar prioritāti    37
4.4.  Kaudze (Heap)    38
4.5.  Kārtošana ar kaudzi (Heap Sort)    39
4.6.  Kārtošana ar sapludināšanu (Merge Sort)    40
4.7.  Ātrā kārtošana (Quick Sort)    40
4.8.  Digitālā kārtošana    42
4.9.  Bucket Sort    42
4.10.  Radix Sort    43
5.  Kopu realizācija ar sarakstiem un kokiem    44
5.1.  Kopas un vārdnīcas kā abstrakts datu tips    44
5.2.  Operācijas ar kopām    44
5.3.  Vārdnīca    44
5.4.  Vārdnīcas realizācijas iespējas    45
5.4.1.  Nesakārtoti saraksti    45
5.4.2.  Sakārtoti saraksti    46
5.4.3.  Binārā meklēšana    46
5.4.4.  Interpolējošā meklēšana    47
5.4.5.  Binārie meklēšanas koki    48
Darba fragmentsAizvērt

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.…

Autora komentārsAtvērt
Parādīt vairāk līdzīgos ...

Atlants

Izvēlies autorizēšanās veidu

E-pasts + parole

E-pasts + parole

Norādīta nepareiza e-pasta adrese vai parole!
Ienākt

Aizmirsi paroli?

Draugiem.pase
Facebook

Neesi reģistrējies?

Reģistrējies un saņem bez maksas!

Lai saņemtu bezmaksas darbus no Atlants.lv, ir nepieciešams reģistrēties. Tas ir vienkārši un aizņems vien dažas sekundes.

Ja Tu jau esi reģistrējies, vari vienkārši un varēsi saņemt bezmaksas darbus.

Atcelt Reģistrēties