Implementierung einer doppelt verknüpften Liste

Question

Ich versuche eine verkettete Liste zu implementieren, und ich bin völlig verloren. Ich bekomme überall Breakpoints, speziell mit der Löschmethode. Wenn ich die Löschmethode ändere, wird zwangsläufig ein Fehler auftreten. Ich habe Zeigerfehler, Probleme mit dem Destruktor, die nur auftreten, wenn die Löschmethode aufgerufen wird, und so weiter.

Hier ist, was ich bisher:

Header-Datei:

#pragma once 

class IntList { 
private: 

    class IntNode { 
    public: 
     IntNode(int v, IntNode *pr, IntNode *nx); 
     ~IntNode(); 
     IntNode* previous; 
     IntNode* next; 

     class iterator { 

     public: 
      iterator(IntNode* t); 
      int& operator*(); 
      iterator& operator++(); 
      iterator& operator--(); 
      bool operator!=(iterator other)const; 
     private: 
      IntNode* target; 
     }; 

    private: 
     int value; 
    }; 

    IntNode* head; 
    IntNode* tail; 
    int count; 

public: 

    IntList(); 
    ~IntList(); 
    void push_back(int v); 
    void pop_back(); 
    int size() const { return count; } 
    typedef IntNode::iterator iterator; 
    iterator begin(); 
    iterator end(); 
    //unsigned int size() const; 
    void push_front(int value); 
    bool empty() const; 
    int& front(); 
    int& back(); 
    void clear(); 
    iterator erase(iterator position); 
}; 

Umsetzung:

#include "IntList.h" 
#include <stdexcept> 

IntList::IntList() : head{ nullptr }, tail{ nullptr }, count{ 0 } 
{} 

IntList::~IntList() { 
    while (head) { 
     head = head->next; 
     delete head; 
    } 
} 

void IntList::push_back(int v) { 
    tail = new IntNode{ v, tail, nullptr }; 
    if (!head) { head = tail; } 
    count += 1; 
} 

void IntList::pop_back() { 
    tail = tail->previous; 
    delete tail->next; 
    count -= 1; 
} 

IntList::iterator IntList::begin() 
{ 
    return iterator{ head }; 
} 

IntList::iterator IntList::end() { 
    return iterator{ nullptr }; 
} 

void IntList::push_front(int value) { 
    head = new IntNode{ value, nullptr, head }; 
    if (!tail) { tail = head; } 
    count += 1; 
} 

bool IntList::empty() const{ 
    return (count==0); 
} 

int& IntList::front() { 
    return *begin(); 
} 

int& IntList::back() { 
    return *begin(); 
} 

void IntList::clear() { 
    head = nullptr; 
    tail = nullptr; 
    count = 0; 
} 

IntList::iterator IntList::erase(iterator position) { 

    int midpointL = 0; 

    for (iterator index = begin(); index != position; ++index) { 
     midpointL++; 
    } 

    if (midpointL == 0) { 
     head = head->next; 
    } 
    else if (midpointL == count) { 
     tail = tail->previous; 
    } 
    else { 

     // Move head to get a reference to the component that needs to be deleted 
     for (int i = 0; i < midpointL; i++) { 
      head = head->next; 
     } 

     // Change the previous and next pointers to point to each other 
     (head->previous)->next = (head->next); 
     (head->next)->previous = (head->previous); 

     for (int i = midpointL-1; i > 0; i++) { 
      head = head->previous; 
     } 

    } 

    count-=1; 

    return position; 
} 


IntList::IntNode::IntNode(int v, IntNode * pr, IntNode * nx) 
    : previous{ pr }, next{ nx }, value{ v } 
{ 
    if (previous) { previous->next = this; } 
    if (next) { next->previous = this; } 
} 

IntList::IntNode::~IntNode() { 
    if (previous) previous->next = next; 
    if (next) next->previous = previous; 
} 

IntList::IntNode::iterator::iterator(IntNode* t) 
    : target{ t } 
{} 

int& IntList::IntNode::iterator::operator*() { 
    if (!target) { throw std::runtime_error{ "Deferenced sentinel iterator." }; } 
    return target->value; 
} 

IntList::IntNode::iterator& IntList::IntNode::iterator::operator++() 
{ 
    if (target) { target = target->next; } 
    return *this; 
} 

IntList::IntNode::iterator& IntList::IntNode::iterator::operator--() 
{ 
    if (target) { target = target->previous; } 
    return *this; 
} 

bool IntList::IntNode::iterator::operator!=(iterator other)const 
{ 
    return (!(target == other.target)); 
} 

Könnte jemand in die richtige Richtung zeigen mir helfen?

Danke!

Answer 1

Lassen Sie uns eine Art schnelle Überprüfung hier machen:

IntList::~IntList() { 
    while (head) { 
     head = head->next; 
     delete head; 
    } 
} 

sollten Sie stattdessen tun:

IntList::~IntList() { 
    while (head) { 
     IntNode* newHead = head->next; 
     delete head; 
     head = newHead; 
    } 
} 

, wie Sie das „next“ Objekt löschen und dann Sie versuchen, Zugang zu erhalten, es in der nächsten Iteration.

void IntList::pop_back() { 
    tail = tail->previous; 
    delete tail->next; 
    count -= 1; 
} 

Hier Sie prüfen nicht, ob Schwanz null ist oder wenn es auf den Kopf zeigt .. (was ist der leere Zustand?), Vielleicht count!=0? im Fall können Sie einen nicht vorhandenen nächsten Knoten

IntList::iterator IntList::end() { 
    return iterator{ nullptr }; 
} 

.. end ist null löschen? ebd sollte Ihr Schwanz ...

int& IntList::back() { 
    return *begin(); 
} 

sein, die begin..not zurück ist.

void IntList::clear() { 
    head = nullptr; 
    tail = nullptr; 
    count = 0; 
} 

ein Löschen sollte alle Objekte in der Liste freigeben. Sie erzeugen Müll hier (Lecks).

Ich habe hier angehalten, Entschuldigung, es ist nur eine Kaffeepause. Aber Sie sollten sorgfältig prüfen: * Null-Zeiger Verwendung * löschen Sie Ihr Knotenlistenelement, wenn es nicht * achten Sie benötigen nicht benutzt ungültige Zeiger (wie head->previous->next Ich sah irgendwo)

Sie haben Ihren Code zu überprüfen, Prost. Ich hoffe, dass diese ersten Hinweise Ihnen durch Ihren Lernprozess helfen.

Haben Sie Spaß, Ste