anfänger - verkettete liste

hallo ich wollte mal in c++ eine verkettete liste oder einen verketteten stapel halt sowas in der art programmieren, mein hauptaugenmerk sollte dabei nicht auf objektorientierung sondern speicherverwaltung liegen, ich hab jetz erst mal ein bisschen was gemacht und bevor ich mich in die katastrophe stürze hätte iczh gerne ein paar meinungen dazu:

#ifndef ITEM_H
#define ITEM_H

class Item
{
public:
    int wert;
    Item* next;

public:
    Item();
    Item(int i);
};

Item::Item()
{
    wert= 0;
    next = NULL;
}
Item::Item(int i)
{
    wert = i;
    next = NULL;
}

#endif

#include "Item.h"

class List
{
protected:
    Item* first;
    Item* last;

public:
    List();
    List(int i);
    ~List();

    void add(int i);
    void erase();
    void print();
};

List::List()
{
    first = NULL;
    last = first;
}
List::~List()
{
}
void List::add(int i)
{
    Item* x = new Item(i);
    x->next = first;
    first = x;
}

void List::erase()
{
    if(first != NULL)
    {
        Item* t = first;
        first = first->next;
        delete t;
        t = NULL;
    }
}

void List::print()
{
    Item* t = first;
    std::cout << first->wert << std::endl;
    while(t->next != NULL)
    {
        t = t->next;
        std::cout << " " << t->wert << std::endl;
    }
}

Firefighter

Also an sich habe ich nichts auszusetzen. Bis auf eine kleine Sachen eventuell. Wenn du dann soweit bist, kannst du die Liste auch als Template machen, dann ist es auch möglich anstatt nur ints, wie jetzt, auch andere Sachen reinzupacken.

jencas

Das

t = NULL;

in erase() ist völlig überflüssig, da t dort sowieso "out of scope" geht.

asc

shisha schrieb:

...und bevor ich mich in die katastrophe stürze hätte iczh gerne ein paar meinungen dazu:

Bitte benutz im Forum bei der Codedarstellung im Falle von C oder C++ Code die cpp-Tags (statt den code-Tags).

Jetzt aber erst einmal Anmerkungen:
1. Trenne Implementierung/Deklaration (Header/Source)
2. Verwende Initialisierungslisten bei Konstruktoren
3. Datenkapselung ist sinnvoll (public Attribute würde ich meiden).
4. Wenn Item fix zu List gehört, und nur dort verwendet werden kann, eignen sich innere, private Klassen eher.
5. Ich würde lieber private statt protected verwenden...
6. Sobald du mit Zeigern und dynamischer Speicherverwaltung hantierst, musst du in der Regel auch Kopierkonstruktor und Zuweisungsoperator implementieren, oder explizit verbieten. Zudem hat dein Destruktor auch aufzuräumen, wenn noch Elemente vorhanden sind.

Um dir mal einen Ansatz zu geben:

#ifndef LIST_H
#define LIST_H

// List.h
class List
{
  private:
    // Listenelement, da nur intern in Verwendung ist die öffentliche
    // Schnittstelle okay...
    class Item
    {
      public:
        int wert;
        Item* next;
        Item(int wert = 0); // Ich reduziere mal auf einen Konstruktor...
    }

    Item* first; // Einfach verkette Listen brauchen nur einen Zeiger

public:
    // Neben den Konstruktor/Destruktor sind in deinem Fall noch
    // Kopierkonstruktor und Zuweisungsoperator nötig!
    // Alternativ: private Deklarieren, ohne Implementierung!
    List();
    List(
       List const & liste);
    List& operator=(
       List const & liste);
    ~List();

    void add(int i);
    void erase();
    void print();
};

#endif

// List.cpp
#include "List.h"

// *** Listenelement ***
List::Item::Item(  // Nun eine Verschachtelung tiefer (Da Item in List)
     int wert)
:    wert(wert),   // Initialisierungsliste
     next(NULL)
{
}

// *** Liste ***

List()
:   first(NULL)
{
}

List::~List()
{
    // Du musst hier auch aufräumen!
    clear();
}

List& List::operator=(
    List const & liste)
{
    // Man kann Zuweisungsoperatoren besser bauen (z.B. mittels swap)
    // Ich habe hier nur eine typische Anfängerimplementierung gewählt...
    if(this == &liste)
        return *this;

    // Alle Elemente aus Original übertragen, ich nutze hierbei die add-Funktion
    clear();
    for(Item * element=liste.first; element!=null; element=element->next)
        add(element->wert);

    return *this;
}

List::List(
    List const & liste)
:   first(NULL)
{
    // Alle Elemente aus Original übertragen
    for(Item * element=liste.first; element!=null; element=element->next)
        add(element->wert);
}

void List::clear()
{
    while(first) {
        Item * next = first->next;
        delete first;
        first = next;
    }
}

//... usw.

Code ist ungetestet. Aber noch weitere Hinweise:

7. Ausgaben und Datenhaltung würde ich grundsätzlich trennen, um den Code eher wiederverwerten zu können.
8. Merk dir grundsätzlich: Zu jedem new gehört immer genau ein delete!