-
Pamatalgoritmi
Реферат44 Математика, Компьютеры, программирование, электроника
Nr. | Название главы | Стр. |
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 |
Saraksts L ir sakārtota elementu virkne
Saraksta L garums tiek apzīmēts ar |L| ; līdz ar to |
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 =
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
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
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.…
Viss par pamatalgoritmiem
- Atvasinājums un tā fiziskā jēga
-
Pamatalgoritmi
Реферат44 Математика, Компьютеры, программирование, электроника
- Skolēnu matemātiskās spējas 8.-9. klasei
-
Ты можешь добавить любую работу в список пожеланий. Круто!Cikla operatori
Реферат для университета7
-
Pamatalgoritmi
Реферат для университета5
-
Ekstrēmu noteikšana funkcijām ar trim vai vairāk mainīgajiem
Реферат для университета8
-
Pamatalgoritmi
Реферат для университета12
-
Нахождение самого длинного пути в графе
Реферат для университета15