Jednokierunkowa lista szablonowa

Siemka, mam problem z programem. Kompiluje się, aczkolwiek coś nie gra, wydaje mi się, że przy dodawaniu elementów. Będę wdzięczny, jeśli ktoś wskaże mi pomyłkę.

//header
#include <iostream>
#include <cstdlib>

template <typename Type>
class Lista
{
private:
    struct Element
    {
        Element *next;
        Type dane;
    };
    Element *head;
public:
    Lista();
    ~Lista();
    void show();
    void add(Type d);
    void usun(Element * elem);
    bool isempty();
    int rozmiar();
    void czysc();
};

//metody

template <typename Type>
Lista<Type>::Lista()
{
    head = NULL;
    std::cout << "dziala konstruktor" << std::endl;
}

template <typename Type>
Lista<Type>::~Lista()
{
    czysc();
}

template <typename Type>
void Lista<Type>::czysc()
{
    if(head == NULL)
    {
        std::cerr << "Nie ma czego usunac" << std::endl;
        return;
    }
    else
    {
        Element *temp = new Element;
        for(temp = head; temp != NULL; temp = temp->next)
        {
            std::cout << "destruktor" << std::endl;
            delete temp;
        }
    }
}

template <typename Type>
void Lista<Type>::show()
{
    Element *temp = new Element;

    for(temp = head; temp->next!=NULL; temp = temp->next)
    {
        std::cout << temp->dane << std::endl;
    }
}

template <typename Type>
void Lista<Type>::add(Type d)
{
    Element * nowa = new Element;
    nowa->dane = d;

    if(head == NULL)
    {
        std::cout << "dodawanie" << std::endl;
        head = nowa;
    }
    else
    {
       Element *temp = new Element;
       temp = head;

       while(temp->next!=NULL)
       {
           temp = temp->next;
       }
       temp->next = nowa;
       nowa->next = NULL;
    }
}

//main
int main()
{
    Lista<int> L;
    L.add(2);
    L.show();
}

 

http://4programmers.net/Forum/1102448

1. Jak masz 1 element, to nic się nie pokaże, bo przecież:

for(temp = head; temp->next!=NULL; temp = temp->next)

Poprawny warunek to temp != NULL.

2. Zamień

void add(Type d);

na

void add(const Type& d);

3. Wycieki pamięci:

Element *temp = new Element;
temp = head;

Element *temp = new Element;
for(temp = head

po 1

masz tutaj mnóstwo memory leaków;

po 2

zamień wszystkie NULL -> nullptr

po 3 wywala Ci się na Lista::show()

a wywala Ci się bo head->next jest niezainicjalizowane, ustaw head->next = nullptr, jak ustawiasz head

1. Dlaczego przy dodawaniu muszę podawać argument przez referencję, a nie przez wartość?
2. Zmieniłem tak jak pisaliście, gdzie są te wycieki pamięci?

template <typename Type>
Lista<Type>::Lista()
{
    head = nullptr;
    head->next = nullptr;
    std::cout << "dziala konstruktor" << std::endl;
}

template <typename Type>
Lista<Type>::~Lista()
{
    czysc();
}

template <typename Type>
void Lista<Type>::czysc()
{
    if(head == nullptr)
    {
        std::cerr << "Nie ma czego usunac" << std::endl;
        return;
    }
    else
    {
        Element *temp = new Element;
        for(temp = head; temp != nullptr; temp = temp->next)
        {
            std::cout << "destruktor" << std::endl;
            delete temp;
        }
    }
}

template <typename Type>
void Lista<Type>::show()
{
    Element *temp = new Element;

    for(temp = head; temp!=nullptr; temp = temp->next)
    {
        std::cout << temp->dane << std::endl;
    }
}

template <typename Type>
void Lista<Type>::add(const Type &d)
{
    Element * nowa = new Element;
    nowa->dane = d;

    if(head == nullptr)
    {
        std::cout << "dodawanie" << std::endl;
        head = nowa;
    }
    else
    {
        Element *temp = new Element;
        for(temp = head; temp!=nullptr; temp = temp->next)
        {
            temp->next = nowa;
            nowa->next = nullptr;
        }
    }
}

 

mamama9090 napisał(a):

1. Dlaczego przy dodawaniu muszę podawać argument przez referencję, a nie przez wartość?
   Bo przez wartość oznacza kopiowanie parametru, co może być kosztowne przy dużych obiektach.

2. Zmieniłem tak jak pisaliście, gdzie są te wycieki pamięci?

Element* temp = new Element;

Rezerwujesz pamięć na nowy element, a potem wyrzucasz to, bo od razu przypisujesz

temp = head;

A wystarczy

Element* temp = head;

bo potrzebujesz wskaźnika, nie wskaźnika z zaalokowaną dynamicznie pamięcią.

template <typename Type>
void Lista<Type>::show()
{
    Element *temp = new Element;
 
    for(temp = head; temp!=nullptr; temp = temp->next)
    {
        std::cout << temp->dane << std::endl;
    }
}

pomyśl co się dzieje z pamięcią zaalakowaną dla temp, gdy zrobisz temp = head

Czyli

Element * nowa = new Element;
 

pamięć alokuję tylko w funkcji add, przy dodawaniu nowego elementu?

Teraz funkcja wyświetlająca jest ok?

template <typename Type>
void Lista<Type>::show()
{
    Element *temp = head;

    while(temp!=nullptr)
    {
        std::cout << temp->dane << std::endl;
        temp = temp->next;
    }
}
 

No i po dodaniu linijek

 
head->next = nullptr;
head->dane = 0;

program się od razu wywala i nie przechodzi dalej. Dlaczego? Może to mieć jakiś związek z tym, że strukturę Element deklaruję w prywatnych składowych Listy?

Stary kod:

while(temp->next!=NULL)
{
    temp = temp->next;
}
temp->next = nowa;
nowa->next = NULL;

Nowy kod:

for(temp = head; temp!=nullptr; temp = temp->next)
{
    temp->next = nowa;
    nowa->next = nullptr;
}

Widzisz co zepsułeś?

temp->next = nowa;
nowa->next = nullptr;
 

ma być poza pętlą, bo rozumiem, że

 
temp != nullptr;

jest poprawnym warunkiem stopu

Dodajesz nowy element, więc przy warunku

temp != nullptr

zatrzymujesz się na null i próbujesz dodać do nulla nowy element. Stary warunek był dobry:

 temp->next != nullptr

Zauważ różnicę w warunku stopu między przypadkiem dodawania a pokazania.

Ok, dzięki wielki, rozumiem! Ostatni problem to destruktor, a konkretnie funkcja czysc()

template <typename Type>
void Lista<Type>::czysc()
{
    if(head == nullptr)
    {
        std::cerr << "Nie ma czego usunac" << std::endl;
        return;
    }
    else
    {
        Element *temp;
        for(temp = head; temp != nullptr; temp = temp->next)
        {
            delete temp;
        }
    }
    std::cout << "destruktor" << std::endl;
}
 

Nie wykonuje się, bo nie wyświetla mi się "destruktor", a konkretniej psuje się na pętli

 
for(temp = head; temp != nullptr; temp = temp->next)
        {
            delete temp;
        }

nie wychodzi z niej. Warunek stopu wg mnie jest ok.

No bo jak zrobisz delete temp to jak potem chcesz zrobić jeszcze temp = temp->next?

Rozwiązałem to inaczej:

 
    else
    {
        Element *temp;

        while(head!=nullptr)
        {
            temp = head;
            head = head->next;
            if(temp!=nullptr)
                delete temp;
        }
         std::cout << "destruktor" << std::endl;
    }
}

i działa. Dzięki wielkie za pomoc :)