Einfügen von Knoten in die Doppelt verkettete Liste

Ich bin zu wollen, legen Sie eine newnode, die einen Namen in der richtigen position für die Doppelt verkettete Liste. Im Grunde eine Insertion sort ist, was ich will, hier zu erreichen.

Dies ist der code für die insert-Funktion gibt es jedoch Probleme:

  • Es bricht die Doppelt verkettete Liste, wenn Sie einfügen eines Knoten mit dem gleichen Wert mehr als einmal!!!!
  • Es ist nicht richtig Sortieren der Liste.

Hier ist der code für die Klasse:

class Doubly
{
private:
        struct node
           {
              string name; //stores name
              node* next; //points to next node
              node* prev; //points to previous node
           };

           node* head; //points to the first node in the list
           node* last; //points to the last node in the list

        public:

            Doubly(); //cstrctr
            ~Doubly(); //dstrctr

       bool empty() const { return head==NULL; }
       void insert(const string& );
       void remove(const string& );
       void print(ostream& OutStream) const;
       void sort (bool);
};

Hier ist der code zum einfügen:

void Doubly::insert (const string& input)
{
    //Insertion into an Empty List.

if(empty()) //create a new list with one node = Head/Null
    {

       node* name = new node;
       head = name;
       last = name;
       name -> prev = NULL;
       name -> next = NULL;
       name -> name = input; //

    }

    //Insertion into a populated list
else
    {
        node* newnode;
        newnode = head;

        while (input > newnode -> name && newnode -> next != last -> next)
                        newnode = newnode -> next;

            if (newnode == head)
                {
                     node* name = new node;
                     name -> name = input;
                     name -> prev = newnode;
                     name -> next = NULL;
                     head -> next = name;
                     last = name;
                }

           else
           {
               if (newnode == last && input > last -> name) //Add the name to the end of the linked list
                   {
                         last -> next = new node;
                         (last -> next) -> prev = last;
                         last = last -> next;
                         last -> next = NULL;
                         last -> name = input;  
                   }
               else
                   {
                     node* name = new node;
                     name -> name = input;
                     name -> next = newnode;
                     (newnode -> prev) -> next = name;
                     name -> prev = newnode -> prev;
                     newnode -> prev = name;
                   }
          }
    }
}
  • Es ist schwieriger als ich erwartet habe, zu Lesen newnode -> name; alle diese zusätzlichen Räume sind schwer zu bekommen über. 🙂
  • Eine Empfehlung: nutzen Sie die Liste Kopf schauen genug, wie ein list item und machen Sie die Liste Runder. Mit leeren Liste eine Kopf zeigt, um sich mit beiden "next" und "prev" können Sie immer auf "next" und "prev" nichts, so haben Sie nur einen einzigen Fall, anstatt der vier, die Verringerung der Menge an code und somit mögliche Orte für Fehler vier mal.
  • Eine weitere Empfehlung: es sei denn, Ihr macht Hausaufgaben (Sie sollten die Tags für deine Frage als solche, wenn Sie tun), nicht implementieren Listen selbst. Sie hat die Frage C++, so haben Sie STL-und wenn Sie etwas spezielles brauchen, kann pull-in boost. Es ist gut zu verstehen, verknüpfte Listen, aber nie schreibt Sie sich in der Praxis.
  • Was ist die Frage?
  • Nun, ich dachte, ich würde das einfügen eines neuen Knoten in die richtige position, der Doppelt Verknüpften Liste eher als eine separate Art-Funktion später auf, um sicherzustellen, dass alle Namen in Alphabetischer Reihenfolge.
  • IMO, mehr Menschen sollten in die Implementierung aller grundlegenden algorithmen und Datenstrukturen, tun Sie es regelmäßig, und tun es auch -- die Punkte auf eine andere interessante überlegung: sollten Hausaufgaben sein, fest verbunden mit der Realität oder "nur Akademische" übungen? (das ist ein weiterer gemeinsamer Ausdruck der mangelhaften praktischen/theoretischen Dichotomie.)
  • Es ist verwirrend, um zu verwenden, "name" sowohl für die "Daten" - Feld auf Ihrer Liste stehen und für die Knoten-Zeiger. Unsicherheit führt zu Fehlern.

InformationsquelleAutor pmqtr | 2011-03-23
Schreibe einen Kommentar