Glava 4 — Povezane liste
Kod koji prati glavu 4 knjige Uvod u strukture podataka.
| Fajl | Sadržaj |
|---|---|
lista.h |
Struktura Cvor<T> i šablon klase Lista<T> — jednostruko povezana lista iz glave, sa učešljavanjem. |
dvostruka_lista.h |
Šablon klase DvostrukaLista<T> — dvostruko povezana lista sa sentinel-čvorom, dopunjena operacijama i iteratorom. |
testovi_lista.cpp |
Testovi svih operacija klase Lista, uključujući granične slučajeve i listu od dva miliona elemenata. |
testovi_dvostruka_lista.cpp |
Testovi klase DvostrukaLista; svaki test proverava i invarijantu. |
plesaci.cpp |
Zadatak o plesačima u krugu, rešen kružnom listom. |
ciklus.cpp |
Flojdov algoritam za otkrivanje ciklusa, sa primerima lista sa ciklusom i bez njega. |
linijski_editor.cpp |
Linijski editor iz glave, napisan nad std::list i nad klasom DvostrukaLista, radi poređenja. |
obilazak_niza_i_liste.cpp |
Merenje: obilazak niza i liste iste dužine, kao ilustracija keš lokalnosti. |
Operacije koje nisu u knjizi
Klasa Lista ima sve operacije iz glave, a pored njih i funkciju
ucesljaj, čija je ideja u glavi opisana, a kod izostavljen:
| Funkcija | Značenje | Složenost | std::forward_list |
|---|---|---|---|
ucesljaj(druga) |
učešljavanje dve sortirane liste; druga ostaje prazna |
$O(n + m)$ | merge(druga) |
Klasa DvostrukaLista u glavi ima samo umetanje i brisanje. Ostale operacije
izvode se iz njih:
| Funkcija | Značenje | Složenost | std::list |
|---|---|---|---|
umetni_iza(c, x) |
umetanje iza čvora c |
$O(1)$ | — |
obrisi_sa_pocetka() |
brisanje prvog elementa | $O(1)$ | pop_front() |
obrisi_sa_kraja() |
brisanje poslednjeg elementa | $O(1)$ | pop_back() |
isprazni() |
brisanje svih elemenata | $O(n)$ | clear() |
pronadji(x) |
pokazivač na prvi čvor sa podatkom x, odnosno nullptr ako ga nema |
$O(n)$ | std::find |
begin(), end() |
iteratori za obilazak, kao u odeljku o iteratorima | $O(1)$ | begin(), end() |
Iterator je ugnežđena klasa DvostrukaLista<T>::Iterator. Čuva pokazivač na
čvor i nudi samo operatore *, ++, --, == i !=, pa korisnik preko
njega ne može da pokvari vezu među čvorovima. Pozicija end() je
sentinel-čvor, kao kod std::list. Zahvaljujući funkcijama begin() i
end(), lista se može obilaziti i petljom for (int x : lista).
Prevođenje
Potreban je prevodilac koji podržava C++17, na primer:
g++ -std=c++17 -Wall -Wextra -pedantic testovi_lista.cpp -o testovi_lista
g++ -std=c++17 -Wall -Wextra -pedantic testovi_dvostruka_lista.cpp -o testovi_dvostruka_lista
g++ -std=c++17 -Wall -Wextra -pedantic plesaci.cpp -o plesaci
g++ -std=c++17 -Wall -Wextra -pedantic ciklus.cpp -o ciklus
g++ -std=c++17 -Wall -Wextra -pedantic linijski_editor.cpp -o linijski_editor
g++ -std=c++17 -O2 obilazak_niza_i_liste.cpp -o obilazak_niza_i_liste
Merenje u obilazak_niza_i_liste.cpp ima smisla samo uz optimizaciju
(-O2). Vremena zavise od računara, ali je odnos svuda sličan: obilazak
niza je najbrži, obilazak liste čiji čvorovi leže redom u memoriji primetno
sporiji, a obilazak liste sa nasumično raspoređenim čvorovima sporiji za red
veličine ili više.
Testovi se oslanjaju na assert, pa se treba biti pažljiv ako se prevodi
sa -DNDEBUG — tada se sve provere uklanjaju i program „prolazi“ bez
ikakve provere.
Greške u radu sa memorijom mogu se otkriti prevođenjem sa sanitizerom (GCC i Clang):
g++ -std=c++17 -g -fsanitize=address,undefined testovi_lista.cpp -o testovi_lista
Vežbe
- U funkciji
obrisi_sa_pocetka(fajllista.h) zamenite redosled naredbi tako da sedelete stari;izvrši prepocetak_ = stari->sledeci;. Program se često i dalje ponaša ispravno, jer oslobođena memorija još nije prepisana. Prevedite testove sa-fsanitize=address: sanitizer prijavljuje čitanje oslobođene memorije, o kome je reč u glavi 2. - U funkciji
ucesljajizbrišite reddruga.pocetak_ = nullptr;. Tada obe liste smatraju da su vlasnici istih čvorova. Prevedite testove sa-DNDEBUG -fsanitize=addressi pogledajte šta sanitizer prijavljuje pri uništavanju lista. - U funkciji
umetni_ispred(fajldvostruka_lista.h) zamenite redosled poslednje dve dodele pokazivača. Testovi padaju na proveri invarijante: nacrtajte na papiru šta se desilo sa vezama. - Napišite funkciju
obrni()za klasuLista, koja obrće redosled elemenata u vremenu $O(n)$, bez alokacije novih čvorova.
Zašto nema .cpp fajlova za klase
Lista i DvostrukaLista su šabloni klasa, pa se, kao i DinamickiNiz iz
glave 3, čitava implementacija nalazi u zaglavlju. Objašnjenje je u
README.md za glavu 3.