Toto je starší verze dokumentu!


Domáca úloha č. 5: Obojstrane spojovaný zoznam

  • Úloha zadaná: 22. 11. 2014
  • Odovzdávanie naostro možné od: 26. 11. 2014
  • Absolútny koniec odovzdávania: 9. 12. 2014
  • Odovzdávate súbory: list.h, listitem.h

Doplnenie zadania (zobrazené podčiarknuto):

  • zatiaľ nič

Zadanie

Obojstanný spojový zoznam patrí medzi najzákladnejšie dátové štruktúry. Je vhodný predovšetkým na časté dynamické pridávanie a odoberanie prvkov. Nevýhodou je sekvenčný prístup k prvkom (jediný spôsob, ako sa prepracovať k n-tému prvku, je prejsť všetky pred ním).

So zoznamom ste sa pravdepodobne už stretli v PB071 - Úvode do jazyka C a detailnejšie teoreticky rozobrali v IB002 - Algoritmoch a dátových štruktúrach. Vašou úlohou bude implementovať jeho šablónovú verziu v jazyku C++, podľa nižšie uvedených požiadaviek.

Pre pripomenutie dopĺňam odkaz na wikipediu: http://en.wikipedia.org/wiki/Doubly-linked_list.

Požiadavky

Vytvorte dve šablónové triedy - List a ListItem. List predstavuje celý zoznam, ListItem je jedným prvkom v zozname.

Všeobecné požiadavky

  • metódy, ktoré preberajú sekvencie (begin .. end) môžu predpokladať, že tieto sekvencie budú korektné a nebudú sa prekrývať
  • sekvencie sú inkluzívne (vrátane begin a end)
  • sekvencia, kde begin == end, je korektná sekvencia
  • ak metóda vracia ukazovateľ, bude chybu oznamovať pomocou vrátenia NULL
  • ak dôjde k chybe, mala by metóda vrátiť zoznam do pôvodného stavu
  • všetky metódy preberajúce ako parameter ukazovateľ budou noop (žiadna akcia), ak bude ukazovateľ NULL. Výnimkou sú metódy, ktoré majú akciu pre NULL uvedenú v špecifikácii (insert_after, insert_before)
  • NULL ako parameter musí byť akceptovaný ( napr. list.remove(list.first()) na prázdnom zozname by nemalo zhodiť program)

Trieda ListItem

Pre sprehľadnenie kódu si môžte v triede zadefinovať typové aliasy:
  •  typedef T ValueType; 
    • zodpovedá typu, nad ktorým budeme budovať zoznam
  •  typedef ListItem<T> ItemType; 
    • je typ jedného prvku zoznamu

Použitie typových aliasov nie je povinné, váš kód ich nemusí obsahovať. Budú však využité v nižšie uvedenej špecifikácii.

Atribúty:

  • Ukazovateľ na nasledujúci prvok
  • Ukazovateľ na predchádzajúci prvok
  • Hodnota daného prvku

Metódy:

  • ListItem()
    • bezparametrický konštruktor, nastaví ukazovatele na hodnotu NULL
  • ListItem(const ValueType&);
    • nastaví okrem ukazovateľov tiež hodnotu daného prvku
  • ItemType* getNext() const
    • vráti ukazovateľ na nasledujúci prvok zoznamu
  • ItemType* getPrevious() const
    • vráti ukazovateľ na predchádzajúci prvok
  • ValueType& getValue();
    • vráti hodnotu uloženú v danom prvku zoznamu
  • ValueType  getValue() const;
    • vráti hodnotu uloženú v danom prvku zoznamu
Aby bolo možné korektne implementovať všetky operácie nad zoznamom, je tiež potrebné v tejto triede povoliť prístup pre triedu List - prístupové právo friend. Pozor tiež na to, že List je taktiež šablóna!

Trieda List

Opäť, pre sprehľadnenie vášho kódu môžu poslúžiť ďalšie typové aliasy:
  •  typedef typename ListItem<T>::ValueType ValueType; 
    • je typ jedného prvku zoznamu
  •  typedef typename ListItem<T>::ItemType ItemType; 
    • zodpovedá typu, nad ktorým budujeme zoznam

Použitie typových aliasov nie je povinné, váš kód ich nemusí obsahovať. Budú však využité v nižšie uvedenej špecifikácii.

Atribúty:

  • Ukazovateľ na začiatok zoznamu
  • Ukazovateľ na koniec zoznamu

Metódy:

  • List();
    • vytvorí prázdny zoznam
    • zoznam musí byť skutočne prázdny - nedôjde k vytvoreniu nijakej inštancie typu T
  • List(const List<T>&);
    • vytvorí kópiu zoznamu
  • List(ItemType* begin, ItemType* end);
    • vytvorí kópiu intervalu
    • zadaný interval bude vždy korektný - nemusíte testovať
    • first()-last() na prázdnom zozname je korektný interval
  • ~List();
    • deštruktor, korektne uvoľní pamäť
  • ItemType* first() const;
    • vráti prvý prvok zoznamu
  • ItemType* last() const;
    • vráti posledný prvok zoznamu
  • bool empty() const;
    • test na prázdnosť zoznamu
  • ItemType* insert_after(ItemType* existing, const ValueType& v);
    • vytvorí a vloží nový prvok zoznamu s hodnotou v za už existujúci prvok, vráti novo vložený prvok
    • ak je existujúci prvok NULL, vloží prvok na začiatok zoznamu
  • ItemType* insert_before(ItemType* existing, const ValueType& v);
    • vytvorí a vloží nový prvok zoznamu s hodnotou v pred už existujúci prvok, vráti novo vložený prvok
    • ak je existujúci prvok NULL, vloží prvok na koniec zoznamu
  • ItemType* push_back(const ValueType&);
    • vytvorí a vloží nový prvok zoznamu s hodnotou v na koniec zoznamu
    • ekvivalent insert_after(last())
  • ItemType* push_front(const ValueType&);
    • vytvorí a vloží nový prvok zoznamu s hodnotou v na začiatok zoznamu
    • ekvivalent insert_before(first())
  • ItemType* pop_front();
    • odoberie prvok zo začiatku, vráti odobraný prvok
  • ItemType* pop_back();
    • odoberie prvok z konca, vráti odobraný prvok
  • void remove(ItemType*);
    • deštruktívne odoberie prvok
    • príslušná pamäť sa dealokuje
  • void remove(ItemType* begin, ItemType* end);
    • deštruktívne odoberie interval
    • zadaný interval bude vždy korektný - nemusíte testovať
    • first()-last() pre prázdny zoznam je korektný interval
    • príslušná pamäť sa dealokuje
  • void clear();
    • odstráni všetky prvky zoznamu
    • ekvivalent remove(first(),last())
  • ItemType* unlink(ItemType*);
    • nedeštruktívne odoberie prvok
    • vráti ukazateľ na odobratý prvok
    • ukazatele na predchádzajúci a nasledujúci prvok odobraného prvku zostávajú zachované (nestavujú sa na NULL)
  • void reverse();
    • prevráti zoznam
  • template <typename R> friend std::ostream& operator<<(std::ostream&, const List<R>&);
    • operátor výstupu
    • môžte predpokladať, že ValueType má tento operátor preťažený
    • formát výstupu: { hodnota1, hodnota2, hodnota3 }
    • slovne: zátvorka medzera hodnota čiarka medzera hodnota čiarka medzera hodnota medzera zátvorka
    • pre viac ako 3 hodnoty samozrejme zodpovedajúco :)
    • pre prázdny zoznam: { } (zátvorka medzera zátvorka)
    • v triede deklarujte friend pre tento operátor, jeho telo definujte mimo triedy.

Bonus

Celkovo za 3 bonusové body máte možnosť implementovať v triede List dve ďalšie metódy:

  • void swap(ItemType* first, ItemType* second);
    • prehodí dva prvky
    • za túto metódu môžte získať 1 bonusový bod
  • void swap(ItemType* begin1, ItemType* end1, ItemType* begin2, ItemType* end2);
    • prehodí dva intervaly
    • intervaly budú vždy korektné - nemusíte testovať
    • intervaly sa nikdy nebudú prekrývať - nemusíte testovať
    • za túto metódu môžte získať 2 bonusové body

Main

Ako základ pre vaše testovanie môže poslúžiť nasledujúci main. Rozhodne však ale nemá nahradiť vaše testovanie!

main.cpp
#include "list.h"
 
#include <iostream>
using namespace std;
 
int main()
{
	List<int> x; List<int>::ItemType *it;
	x.insert_after(x.first(),10);
 
	x.push_front(15);
	it = x.pop_back();
	cout << it->getValue() << endl;
	delete it;
 
	x.push_back(20);
	it = x.pop_front();
	cout << it->getValue() << endl;
	delete it;
 
	x.reverse();
 
	x.remove(x.first());
 
	x.insert_before(x.first(),50);
	x.insert_before(x.first(),55);
	x.remove(x.first(),x.first());
 
	x.clear();
 
	if (x.empty())
	{
		cout << "Seznam je prazdny" << endl;
	}
 
	x.push_back(99);
	x.push_back(97);
	cout << x.first()->getValue() << endl;
	cout << x.last()->getValue() << endl;
 
	List<int> y(x);
	cout << y << endl;
 
	List<int> z(x.first(),x.last());
 
	it = z.unlink(z.first());
	cout << it->getValue() << endl;
	delete it;
 
	cout << z << endl;
 
	return 0;
}

Poznámky

Jednotlivé metódy sa silne funkčne prekrývajú, využite to a nepíšte zbytočne duplicitný kód
Pokiaľ narazíte na chybu kompilácie - „error: ‘NULL’ was not declared in this scope“, najjednoduchšie to vyriešite pomocou #include <cstddef>, kde je NULL definované
Ak budete oddeľovať definície metód od deklarácii, môžu vám pomôcť nasledujúce makrá:

V ListItem.h:

#define MItemType typename ListItem<T>::ItemType
#define MValueType typename ListItem<T>::ValueType

V List.h:

#ifdef MItemType
#undef MItemType
#endif
#define MItemType typename List<T>::ItemType
 
#ifdef MValueType
#undef MValueType
#endif
#define MValueType typename List<T>::ValueType

Ukážková binárka pre túto úlohu nie je k dispozícii vzhľadom na charakter zadania.

Autor: Úlohu od Mgr. Šimona Tótha upravil Ján Bella, v prípade nejasností píšte na diskusné fórum, prípadne na xbella1@fi.muni.cz.

QR Code
QR Code public:pb161_fall14_hw05 (generated for current page)