Glava 6 — Red i dek
Kod koji prati glavu 6 knjige Uvod u strukture podataka.
| Fajl | Sadržaj |
|---|---|
red.h |
Šablon klase Red<T> — red nad kružnim baferom fiksnog kapaciteta, kao u glavi. |
red_lista.h |
Šablon klase RedLista<T> — red nad jednostruko povezanom listom, sa pokazivačima na prvi i poslednji čvor. |
red_dva_steka.h |
Šablon klase RedDvaSteka<T> — red pomoću ulaznog i izlaznog steka. |
dek.h |
Šablon klase Dek<T, S> — dek kao niz pokazivača na segmente, sa svim operacijama na oba kraja. |
primer_red.cpp |
Niz operacija iz tabele u glavi, izvršen nad sve tri implementacije reda. |
pretraga_u_sirinu.cpp |
Pretraga u širinu na mapi iz glave 5, sa rekonstrukcijom najkraćeg puta preko prethodnika. |
primer_dek.cpp |
Primer upotrebe deka: operacije na oba kraja, pristup po indeksu, stabilnost adresa, provera palindroma. |
testovi_red.cpp |
Testovi sve tri implementacije reda, uključujući kružno omotavanje i poređenje sa std::deque. |
testovi_dek.cpp |
Testovi klase Dek; posle svake promene proverava se invarijanta. |
Fajlovi dinamicki_niz.h, stek.h i lista.h prepisani su iz glava 3, 5 i
4, da bi folder bio samostalan. RedDvaSteka koristi klasu Stek, a
RedLista samo strukturu Cvor<T>.
Imena klasa
U glavi se i red nad kružnim baferom i red nad listom zovu Red, jer se
nikada ne pojavljuju zajedno. Ovde su u istom folderu, pa red nad listom
nosi ime RedLista, po uzoru na StekLista iz glave 5.
Operacije koje nisu u knjizi
Klasa Red ima operacije iz glave i, pored njih:
| Funkcija | Značenje | Složenost |
|---|---|---|
pun() |
da li je dostignut kapacitet, pa dodavanje nije dozvoljeno | $O(1)$ |
prazan(), velicina() |
provera praznog reda i broj elemenata | $O(1)$ |
U glavi su za RedLista prikazane samo operacije dodaj i izbaci. Ostale
(prednji, prazan, velicina i destruktor) urađene su onako kako ih tekst
opisuje.
Klasa Dek u glavi ima kompletnu deklaraciju, pristup po indeksu,
konstruktor, destruktor, dodavanje na kraj i preuređivanje niza pokazivača.
Ovde su dopisane i operacije koje su u tekstu samo opisane:
| Funkcija | Značenje | Složenost | std::deque |
|---|---|---|---|
dodaj_na_pocetak(x) |
simetrično dodavanju na kraj; novi segment počinje intervalom $[S, S)$ | $O(1)$ amortizovano | push_front(x) |
izbaci_sa_pocetka() |
prazan prvi segment se oslobađa | $O(1)$ | pop_front() |
izbaci_sa_kraja() |
prazan poslednji segment se oslobađa | $O(1)$ | pop_back() |
const verzije operator[], prednji, zadnji |
čitanje iz konstantnog deka | $O(1)$ | iste |
Dve funkcije služe samo testovima i nisu deo interfejsa deka:
invarijanta_vazi() proverava invarijantu iz glave, a
mesta_u_nizu_pokazivaca() vraća kapacitet niza pokazivača, pa se može
proveriti da niz ne raste kada dek „putuje“.
Kapacitet segmenta S mora biti bar 2: prvi element praznog deka upisuje se
na mesto $S/2$, a sa jednim mestom u segmentu dodavanje na početak ne bi
imalo gde da počne.
Prevođenje
Potreban je prevodilac koji podržava C++17, na primer:
g++ -std=c++17 -Wall -Wextra -pedantic testovi_red.cpp -o testovi_red
g++ -std=c++17 -Wall -Wextra -pedantic testovi_dek.cpp -o testovi_dek
g++ -std=c++17 -Wall -Wextra -pedantic primer_red.cpp -o primer_red
g++ -std=c++17 -Wall -Wextra -pedantic primer_dek.cpp -o primer_dek
g++ -std=c++17 -Wall -Wextra -pedantic pretraga_u_sirinu.cpp -o pretraga_u_sirinu
Program pretraga_u_sirinu čita mapu u istom obliku kao lavirint iz
glave 5, pa se dva programa mogu pokrenuti nad istim ulazom. Na mapi
$3 \times 3$ bez prepreka pretraga u širinu nalazi put od 4 koraka, a
pretraga u dubinu prolazi kroz svih 9 polja.
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_dek.cpp -o testovi_dek
Vežbe
- U funkciji
izbaciklaseRedLista(fajlred_lista.h) izbrišite naredbu kojom seposlednjipostavlja nanullptr. Testovi i dalje prolaze, jerdodajprazan red prepoznaje po pokazivačuprvi. Zamenite zatim u funkcijidodajuslovprvi == nullptruslovomposlednji == nullptri prevedite testove sa-fsanitize=address: posle uklanjanja jedinog elementaposlednjije viseći pokazivač, a sledeće dodavanje upisuje u oslobođenu memoriju. Greška je, dakle, postojala i ranije, samo nije bila vidljiva. - U funkciji
pripremiklaseRedDvaStekauklonite proveruif (izlazni.prazan()), tako da se prebacivanje obavlja uvek. Testovi padaju već na osnovnim operacijama: novi elementi dospevaju iznad starijih i preteknu ih. - Proširite klasu
Redtako da pri dodavanju u pun red udvostruči kapacitet. Pazite na redosled: elementi se u novi niz prepisuju redosledom kojim su u redu, od pozicijepocetak, a ne redosledom fizičkih pozicija. - U destruktoru klase
Dekzamenite redosled: najpredelete[] segmenti_, pa petlja. Šta prijavljuje sanitizer? - U klasi
RedDvaStekabrojite operacije nad stekovima i proverite da posle $m$ operacija nad redom, koji je na početku prazan, njihov broj nije veći od $4m$.
Zašto nema .cpp fajlova za klase
Sve klase u ovom folderu su šabloni, pa se, kao i DinamickiNiz iz glave 3,
čitava implementacija nalazi u zaglavlju. Objašnjenje je u README.md za
glavu 3.