Verlinkte Liste Übung, was mache ich falsch?

Question

Hey alle. Ich mache eine verknüpfte Liste Übung, die dynamische Speicherzuweisung, Zeiger, Klassen und Ausnahmen beinhaltet. Wäre jemand bereit sein, es zu kritisieren und sagen Sie mir, was ich falsch gemacht habe und was ich beides getan besser in Bezug auf Stil haben sollte und auf jene Themen, die ich oben aufgelistet?

/*

Linked List exercise

*/

#include <iostream>
#include <exception>
#include <string>
using namespace std;

class node{
public:
    node * next;
    int * data;
    node(const int i){
        data = new int;
        *data = i;
    }
    node& operator=(node n){
        *data = *(n.data);
    }
    ~node(){
        delete data;
    }
};

class linkedList{

public:

    node * head;
    node * tail;
    int nodeCount;

    linkedList(){
        head = NULL;
        tail = NULL;
    }

    ~linkedList(){
        while (head){
            node* t = head->next;
            delete head;
            if (t) head = t;
        }
    }

    void add(node * n){
        if (!head) {
            head = n;
            head->next = NULL;
            tail = head;
            nodeCount = 0;
        }else {
            node * t = head;
            while (t->next) t = t->next;
            t->next = n;
            n->next = NULL;
            nodeCount++;
        }
    }

    node * operator[](const int &i){
        if ((i >= 0) && (i < nodeCount)) throw new exception("ERROR:  Invalid index on linked list.", -1);
        node *t = head;
        for (int x = i; x < nodeCount; x++) t = t->next;
        return t;
    }

    void print(){
        if (!head) return;
        node * t = head;
        string collection;
        cout << "[";
        int c = 0;
        if (!t->next) cout << *(t->data);
        else while (t->next){
            cout << *(t->data);
            c++;
            if (t->next) t = t->next;
            if (c < nodeCount) cout << ", ";
        }
        cout << "]" << endl;
    }

};

int main (const int & argc, const char * argv[]){

    try{
        linkedList * myList = new linkedList;
        for (int x = 0; x < 10; x++) myList->add(new node(x));
        myList->print();
    }catch(exception &ex){
        cout << ex.what() << endl;
        return -1;
    }   
    return 0;
}

Answer 1

Es gibt keine Notwendigkeit für Daten ein Zeiger zu sein.

Verwenden Sie die Ctor-Initialisiererliste, es ist besser für const-Korrektheit und Exception-Sicherheit. Keiner Ihrer Konstrukteure müssen im Inneren des Körpers einen Code haben.

Ihr VerketteteListe Konstruktor nicht nodeCount initialisieren.

Sie Ihre Liste der Endzeiger für nichts verwenden. Es würde speichern Sie die gesamte Liste Scannen durch in der nicht leeren Fall von Add -., Wenn Sie es auf dem Laufenden gehalten

Indexing (Operator []) ist eine ungewöhnliche Sache auf einer verknüpften Liste zu unterstützen. OTOH Sie haben keine Funktion remove.

gemacht

Operator [] sollte seine Parameter durch Verweis nicht nehmen. Nur große Strukturen müssen durch konstante Referenz übergeben werden, kleiner Typ wie int sollte nur von Wert übergeben werden.

Gerade jetzt, wenn Add ausfällt, leckt der Zeiger auf neue Knoten (). (Aber ich sehe nicht wirklich eine Möglichkeit für Zusatz scheitern, wenn die Liste Links beschädigt wurden.)

Sie sollten eine private Kopie-Konstruktor auf dem Knoten zu verhindern doppelt frei von den Daten definieren. Jedes Mal, wenn Sie definieren Operator = und destructor sollten Sie auch den Copykonstruktor (Regel drei) werden definiert, oder zu löschen. Sie sollten auch private Kopie Konstruktor und Zuweisungsoperator auf VerketteteListe definieren Doppelfrei zu verhindern.

Die Variable string Sammlung in Ihrer Druckfunktion wird nicht verwendet. Die Variable t in print () sollte ein Zeiger auf const sein. drucken selbst sollte eine konstante Elementfunktion sein.

Answer 2

/*
Linked List exercise
*/

class node {
public:
    node * next;
    int * data;

data muss nicht wirklich ein Zeiger sein (es sei denn, Ihre Klassenzuordnung sagt es sein muss). Sie können dies zu einem int ändern und dann Referenzen von *(t->data) nur t->data ändern. Ebenso werden Sie nicht brauchen, um den Einsatz new und delete im Ctor / dtor.

    node(const int i) {
        data = new int;
        *data = i;
    } 
    node& operator=(node n) {
        *data = *(n.data);
    } 
    ~node() {
        delete data;
    } 
};

class linkedList {

public:
    node * head;
    node * tail;
    int nodeCount;

    linkedList() {
        head = NULL;
        tail = NULL;

Sie sollten initialisieren alle Ihre Daten Mitglieder hier. nodeCount wird einigen Zufallswert hat, wenn Sie es auf Null eingestellt.

    } 

    ~linkedList() {
        while (head) {
            node* t = head->next;
            delete head;
            if (t)
                head = t;

sieht wie folgt aus einem Fehler. Sie müssen immer assign head = t, auch wenn t NULL ist, sonst wird Ihre Schleife nicht beendet (aber die gleichen Knoten mehrfach löschen wahrscheinlich Ursache einer Ausnahme).

        } 
    } 

    void add(node * n) {
        if (!head) {
            head = n;
            head->next = NULL;
            tail = head;
            nodeCount = 0;

Ich denke, die ganze if Aussage nicht notwendig ist. Beide Zweige das gleiche tun, wenn die verknüpfte Liste leer ist, so dass Sie nur immer die zweite verwenden ( sonst ) Zweig.

Auch scheint wie ein Fehler am Ende nodeCount zu 0 Einstellung; sollte es nicht 1 sein?

        } else {
            node * t = head;

            while (t->next)
                t = t->next;

            t->next = n;
            n->next = NULL;
            nodeCount++;
        } 
    } 

    node * operator[](const int &i) {

Ein kleiner nit, aber ein const int & Argument wirklich keinen Sinn machen. Sie sind nicht alles über nur vorbei einen int Typen zu gewinnen.

        if ((i >= 0) && (i < nodeCount))
            throw new exception("ERROR:  Invalid index on linked list.", -1);

Die Bedingung oben schaut nach hinten zu mir; Sie werden immer die Ausnahme mit gültigen Parametern werfen.

        node *t = head;

        for (int x = i; x < nodeCount; x++)
            t = t->next;

Die Schleife oben scheint ein wenig suspekt zu mir. Wenn i ist die nullbasierte Index des Knotens Sie wollen, sollten nicht Ihre Counter von 0 zu i-1?

        return t;
    } 

    void print() {
        if (!head)
            return;

Auch hier sollten Sie diese Methode Arbeit machen, ohne gegen eine leere Liste zu schützen zu haben. Ich würde eine leere Liste erwartet etwas wie [] zu drucken, aber mit dem Schutz Code oben, werden Sie nichts drucken.

        node * t = head;
        string collection;
        int c = 0;

        cout << "[";

        if (!t->next) {
            cout << *(t->data);

Wie der anderen Zustand über, ich denke, der Zweig oben nicht notwendig ist. Die zweite ( sonst ) Zweig sollte den NULL Fall behandelt nur in Ordnung.

        } else {
            while (t->next) {

Ich glaube, Sie wollen while (t) oben und nicht while (t->next)

                cout << *(t->data);
                c++;

                if (t->next)
                    t = t->next;

Ich denke, das ist ein Fehler wie die früher auf. Sie sollten immer werden die Zuweisung `t = t-> next‘, sonst wird Ihre Schleife nicht beenden.

                if (c < nodeCount)
                    cout << ", ";
            } 
        } 

        cout << "]" << endl;
    } 
};

int main (const int & argc, const char * argv[]) { // const int& ?

const int & wieder ...

    try {
        linkedList * myList = new linkedList;
        for (int x = 0; x < 10; x++)
            myList->add(new node(x));
        myList->print();
    } catch(exception &ex) {
        cout << ex.what() << endl;
        return -1;
    }  

Wahrscheinlich gut für eine Hausaufgabe, aber jede mögliche Ausnahme zu kontrollieren (wie Sie oben tun) wahrscheinlich nicht viel Wert hinzufügt hier, und wird im Allgemeinen als schlechte Praxis betrachtet.

Wenn Sie diese try / catch Sachen oben weglassen, ich vermute, dass, wenn Ihr Programm endet mit einer Ausnahme, die Standard-Top-Level-Exception-Handler vom Compiler zur Verfügung gestellt werden, die Ausnahme und Stack-Trace Info auskippen sowieso (abhängig von Ihrer Compiler).

    return 0;
}

Answer 3

1) Sie data = new int(i) zu initialisieren Feld verwenden können.

2) Sie einen falschen Zustand in Operator erstellt haben [] if ((i >= 0) && (i < nodeCount)), sollte es umgekehrt sein, wie if ((i < 0) || (i >= nodeCount))

Answer 4

if ((i >= 0) && (i < nodeCount)) throw new exception("ERROR:  Invalid index on linked list.", -1);

Diese Zeile sollte lauten:

if( i < 0 || i >= nodeCount ) throw...

Die Add-Methode hat auch Probleme:

void add(node * n){
    if (!head) {
        head = n;
        head->next = NULL;
        tail = head;
        nodeCount = 0;
    }else {
        node * t = head;
        while (t->next) t = t->next;
        t->next = n;
        n->next = NULL;
        nodeCount++;
    }
}

Für eine nach dem Hinzufügen der ersten Knotenzahl 0 sein wird, zum anderen sind Sie der Suche in einer verknüpften Liste einfügen ... eine Operation Menschen erwarten würde O sein (1).

Eine typische Implementierung wäre:

void add( node* n ) {
   node* old_head = head;
   head = n;
   head->next = old_head;
   ++nodeCount;
   if( old_head == NULL )
      tail = head
}