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.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich denke, das problem ist beim einfügen am Kopf der Liste, und Sie haben nur ein element, das
while (input > newnode -> name && newnode -> next != last -> next)
beenden können, wegen 2 Gründen, und Sie sind asuming, dass, wenn der Zeiger noch auf dem Kopf, die Sie haben, um es einzufügen hinterher, aber vielleicht ist es gerade ging der Weile, denn es war nur ein element, und Sie haben zu setzen Sie die neue ein, bevor der Kopf.So dass Sie wahrscheinlich haben, um etwas zu tun wie: