WOJSKOWA AKADEMIA TECHNICZNA
Programowanie obiektowe
SPRAWOZDANIE Z ZADANIA LABORATORYJNEGO
Piotr Pucyk, Jakub Sobczuk, Radosław Żeszczuk, Artur Piersa
Grupa: I2Y3S1
Prowadzący ćwiczenie: mgr inż. Paweł Moszczyński
Data wykonania ćwiczenia: 12 XII 2013r.
Treść zadania
Naszym zadaniem było napisanie klasy Lista reprezentującej listę dwukierunkową opartą na szablonach tak, aby móć przechowywać w niej dowolne typy danych.
2)Omówienie kodu:
template <class T> struct ts_lista
{
struct ts_lista <T> *prev, *next;
T key;
};
Struktura ts_lista jest polem klasy Lista i zawiera w sobie listę dwukierunkową znaną nam z Algorytmów i struktur danych. Dodatkowo template <class T> powoduje powstanie jedynie szablonu tej struktury pozwalając przechowywać key dowolnego typu.
template <class T> class Lista
{
ts_lista <T>*head, *tail;
public:
Lista();
Lista( T);
Lista( const Lista &lista );
~Lista();
void Dodaj(T);
void Usun();
void Usun(T);
void Wypisz();
Lista<T>& operator = (const Lista<T>&);
void* operator new (size_t n);
void operator delete (void*);
};
Utworzony tu został szablon klasy Lista. Posiada on prywatną instancję ts_lista (z przekazanym typem T) oraz konstruktor bezargumentowy, konstruktor z parametrem, konstruktor kopiujący, destruktor, funkcję dodającą element o zadanym kluczu, funkcję usuwającą wszystkie elementy, funkcję usuwająca pierwszy występujący element o zadanym kluczu, funkcję wypisującą wszystkie elementy listy, a także przeciążony operator przyrównania.
template <class T> Lista<T>::Lista()
{
head=NULL;
tail=NULL;
cout<<"Konstruktor 1"<<endl;
}
Konstruktor bezparametrowy: Ustawia wskaźniki head I tail na NULL oraz wywołuje komunikat (pozwalający obserwować wywołanie konstruktora w programie).
template <class T> Lista<T>::Lista(T x)
{
head=NULL;
tail=NULL;
Dodaj(x);
cout<<"Konstruktor 2"<<endl;
}
Konstruktor z jednym parametrem: tworzy pustą listę, a następnie za pomocą funkcji Dodaj dodaje pierwszy element o zadanym kluczu x. Dodatkowo wywołuje komunikat jak w konstruktorze bezparametrowym.
template <class T> Lista<T>::Lista( const Lista<T> &lista )
{
head=tail=NULL;
if(lista.head){
ts_lista<T> *tmp= lista.head;
while(tmp){
Dodaj(tmp->key);
tmp=tmp->next;
}
}
};
Konstruktor kopiujący tworzy pustą listę, a następnie wypełnia ją w pętli while elementami listy przekazanej jako argument.
template <class T> Lista<T>::~Lista()
{
ts_lista <T>*tmp=head, *tmp2=head;;
while(tmp){
tmp2=tmp->next;
delete tmp;
tmp=tmp2;
}
cout<<"Destruktor<<endl;
}
Destruktor przechodzi przez całą listę usuwając po kolei elementy. Na końcu wywołuje komunikat, która pozwalać obserwować w programie wywołanie destruktora.
template <class T>void Lista<T>::Dodaj(T x)
{
ts_lista <T>*tmp= head;
if(!head)
{
ts_lista <T>*nowy= new ts_lista<T>;
nowy->key=x;
nowy->next=NULL;
nowy->prev=NULL;
head=nowy;
tail= nowy;
}
else
{
ts_lista <T>*nowy= new ts_lista<T>;
nowy->key=x;
tail->next=nowy;
nowy->prev=tail;
nowy->next=NULL;
tail=nowy;
}
}
Funkcja Dodaj rozpatruje 2 przypadki. Jeśli lista jest pusta to tworzy nowy element i umieszcza go jako głowę (i zarazem ogon) listy. Jeśli lista posiada już jakieś elementy to na końcu listy dodawany jest nowy element.
template <class T>
void Lista<T>::Usun()
{
ts_lista <T>*tmp= tail;
if(tmp)
{
tmp=tmp->prev;
if(tmp)
tmp->next=NULL;
if(tail==head) head=NULL;
delete tail;
tail=tmp;
}
else
{
cout<<"lista pusta"<<endl;
}
}
Funkcja Usun bez argumentów ma działanie podobne do destruktora klasy z tym, że można ją wywołać z kodu programu. Przechodzi przez całą listę usuwając jej elementy oraz zwalniając pamięć.
template <class T>
void Lista<T>::Usun(T x)
{
ts_lista <T>*tmp= head;
while(tmp && tmp->key!=x)
tmp= tmp->next;
if(tmp)
{
if(tmp->prev==NULL)
{
head=tmp->next;
}
else
tmp->prev->next=tmp->next;
if(tmp->next==NULL)
{
tail=tmp->prev;
}
else
{
tmp->next->prev=tmp->prev;
}
delete tmp;
}
}
Funkcja Usun z argumentem x odnajduje zadany element, omija go w wiązaniach listy oraz zwalnia po nim pamięć. Funkcja nie robi nic jeśli element nie znajduje się w liście
template <class T> void Lista<T>::Wypisz()
{
cout<<endl;
ts_lista <T>*tmp=head;
while(tmp)
{
cout<<tmp->key<<" ";
tmp=tmp->next;
}
}
Funkcja Wypisz przechodzi przez kolejne elementy listy i wypisuje ich klucze na ekranie.