Search
Třetím úkolem začíná série úkolů, během níž budete implementovat oboustranně zřetězený spojový seznam (viz Wikipedia) ve stylu standardní knihovny. Jedná se o strukturu list, která pro každý obsažený prvek alokuje strukturu list::node. Samotná struktura list obsahuje ukazatel head, který ukazuje na první prvek v seznamu (front), naopak ukazatel tail ukazuje na poslední prvek v seznamu (back). Pokud má seznam pouze jeden prvek, pak head i tail ukazují na ten samý objekt. Pokud seznam nemá žádné prvky, head i tail jsou nastaveny na nullptr.
list
list::node
head
tail
nullptr
struct list { struct node { double val; node* prev; node* next; }; node* head = nullptr; node* tail = nullptr; size_t size = 0; };
Ve struktuře list::node se také nachází dva ukazatele, prev a next. Ukazatel next vždy ukazuje na další (následující) prvek v seznamu, prev na předchozí. Pokud je prvek prvním prvkem v seznamu, prev je nastaven na nullptr. Pokud je prvek posledním prvkem v seznamu, next je nastaven na nullptr.
prev
next
Potřebné hlavičkové soubory a testy ke stažení zde.
Jeden nebo více .cpp souborů, které implementují funkce deklarované v souboru list.hpp tak, aby testy procházely a neztrácela se paměť. Při práci na úkolu soubor list.hpp neměňte.
.cpp
list.hpp
Doporučujeme o listu přemýšlet a pohybovat se v něm podobně jako ve stromu, to jest jako v sérii uzlů. Prakticky to znamená, že by se člověk při průchodech neměl orientovat dle velikosti, ale dle struktury – začátek se pozná dle prev == nullptr, konec se pozná dle next == nullptr. Ostatní uzly jsou jednoduše někde uprostřed; není důležité, kde přesně.
prev == nullptr
next == nullptr
Stejně tak doporučujeme vždy aktualizovat ukazatele prvků v listu, i v případě, že to není striktně potřeba. Pokud tedy například smažete aktuálně poslední uzel v listu, tak krom přesunutí ukazatele tail byste měli aktualizovat i next ukazatel předposledního (nově posledního) uzlu listu.
Dávejte si pozor na přístup ke smazané paměti, protože jakmile jednou kus paměti uvolníte, všechna data v ní jsou pro vás ztracena. To znamená, že například při mazání listu je potřeba nejdříve přesunout hlavu a pak až smazat první prvek.
Malá ilustrace (node je celá struktura reprezentující uzel v listu a šipky jsou ukazatele):
Začneme se správně zkonstruovaným listem, který má 4 prvky.
head | | _____V__ ________ ________ ________ / node | / node | / node | / node | |------ | |------ | |------ | |------ | | value | | value | | value | | value | | next | -->| next | -->| next | -->| next | --| |-- | prev |<-- | prev |<-- | prev |<-- | prev | | | |-------- |-------- |-------- |-------- | ----------------------> nullptr <-------------------------
head | | _____V__ ________ ________ ________ / nod/ | / node | / node | / node | |\--/-- | |------ | |------ | |------ | | \/lue | | value | | value | | value | | /\xt | | next | -->| next | -->| next | --| |/pre\ |<-- | prev |<-- | prev |<-- | prev | | |-------- |-------- |-------- |-------- | nullptr <--------------------------
head.next
head | | ________ ____V___ ________ ________ / node | / node | / node | / node | |------ | |------ | |------ | |------ | | value | | value | | value | | value | | next | -->| next | -->| next | -->| next | --| |-- | prev |<-- | prev |<-- | prev |<-- | prev | | | |-------- |-------- |-------- |-------- | ----------------------> nullptr <-------------------------
head | | _______ ______V_ ________ ________ / nod/ | / node | / node | / node | |\--/--| |------ | |------ | |------ | | \/lue| | value | | value | | value | | /\xt | | next | -->| next | -->| next | --| |/pre\ | |- | prev |<-- | prev |<-- | prev | | |------- | |-------- |-------- |-------- | --------> nullptr <-------------------------
Pro tento úkol žádné hlavičky ze standardní knihovny nedoporučujeme.
V minulém semestru byl s tímto úkolem problém, že pokud vám neprocházel některý test, pak vám Valgrind hlásil únik paměti i tam, kde není. Pro tento semestr jsme to opravili, nicméně je možné, že jsme nějaký případ nepodchytili.