Warum verwenden verknüpfte Listen Zeiger, anstatt Knoten innerhalb von Knoten zu speichern?

Lesezeit: 14 Minuten

Benutzer-Avatar
m0meni

Ich habe vorher ausführlich mit verketteten Listen in Java gearbeitet, aber ich bin sehr neu in C++. Ich habe diese Knotenklasse, die mir in einem Projekt gegeben wurde, ganz gut verwendet

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

aber ich hatte eine Frage, die nicht sehr gut beantwortet wurde. Warum ist es notwendig zu verwenden

Node *m_next;

statt auf den nächsten Knoten in der Liste zu zeigen

Node m_next;

Ich verstehe, dass es besser ist, die Zeigerversion zu verwenden; Ich werde nicht mit Fakten argumentieren, aber ich weiß nicht, warum es besser ist. Ich habe eine nicht so klare Antwort darauf erhalten, wie der Zeiger für die Speicherzuweisung besser ist, und ich habe mich gefragt, ob mir hier jemand helfen könnte, das besser zu verstehen.

  • @self Entschuldigung? Warum sollte eine Sprache, in der alles ein Zeiger ist, keine verknüpften Listen haben?

    – Angew ist nicht mehr stolz auf SO

    9. April 2015 um 16:21 Uhr

  • Es ist wichtig zu beachten, wie sich C und C++ in Bezug auf Objektzeiger und Referenzen von Java unterscheiden. Node m_next ist kein Verweis auf einen Knoten, sondern ein Speicher für das Ganze Node selbst.

    – Brian Kain

    9. April 2015 um 16:21 Uhr

  • @self Java hat Zeiger, die Sie nur nicht explizit verwenden.

    – m0meni

    9. April 2015 um 16:22 Uhr

  • Schildkröten den ganzen Weg nach unten ist nicht eine Option. Irgendwo muss der Wahnsinn enden.

    – WhozCraig

    9. April 2015 um 16:22 Uhr


  • Bitte vergiss alles Sie kennen sich mit Java aus. C++ und Java handhaben Speicher auf grundlegend unterschiedliche Weise. Sehen Sie sich diese Frage für Buchempfehlungen an, wählen Sie eine aus und lesen Sie sie. Du tust uns allen einen großen Gefallen.

    – Rob K

    9. April 2015 um 18:37 Uhr

Benutzer-Avatar
Emlai

Es ist nicht nur besser, es ist der einzig mögliche Weg.

Wenn Sie a gespeichert haben Node Objekt in sich selbst, was würde sizeof(Node) sein? Es wäre sizeof(int) + sizeof(Node)was gleich wäre sizeof(int) + (sizeof(int) + sizeof(Node))was gleich wäre sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node)))usw. bis unendlich.

So ein Objekt kann nicht existieren. Es ist unmöglich.

  • *Es sei denn, es wird faul ausgewertet. Unendliche Listen sind möglich, nur nicht bei strenger Bewertung.

    – Krebserregend

    9. April 2015 um 20:07 Uhr

  • @Carcigenicate Es geht nicht darum, eine Funktion für das Node-Objekt auszuwerten/auszuführen – es geht um das Speicherlayout jeder Instanz von Node, das zur Kompilierzeit bestimmt werden muss, bevor eine Auswertung erfolgen kann.

    – Peter ist

    9. April 2015 um 22:17 Uhr

  • @DavidK Es ist logischerweise unmöglich, dies zu tun. Du brauchen ein Hinweis (naja, eigentlich eine Indirektion) hier – sicher kann die Sprache es vor Ihnen verbergen, aber am Ende führt kein Weg daran vorbei.

    – Voo

    10. April 2015 um 7:32 Uhr

  • @ David Ich bin verwirrt. Zuerst stimmen Sie zu, dass es logisch unmöglich ist, aber dann wollen Sie darüber nachdenken? Entfernen Sie alles von C oder C++ – es ist unmöglich in irgendein Sprache, die man sich, soweit ich sehen kann, jemals ausdenken könnte. Diese Struktur ist per Definition eine unendliche Rekursion, und ohne ein gewisses Maß an Indirektion können wir das nicht brechen.

    – Voo

    10. April 2015 um 13:08 Uhr


  • @benjamin Ich habe tatsächlich darauf hingewiesen (weil ich wusste, dass sonst jemand dies ansprechen würde – das hat nicht geholfen), dass Haskell die Thunks zum Zeitpunkt der Erstellung zugewiesen hat und daher funktioniert dies, weil diese Thunks uns die Indirektion geben, die wir brauchen. Dies ist nichts als ein Zeiger mit zusätzlichen Daten in Verkleidung …

    – Voo

    10. April 2015 um 16:00 Uhr


Benutzer-Avatar
pm100

Auf Java

Node m_node

speichert einen Zeiger auf einen anderen Knoten. Du hast keine Wahl. In C++

Node *m_node

bedeutet dasselbe. Der Unterschied besteht darin, dass Sie in C++ das Objekt tatsächlich speichern können, im Gegensatz zu einem Zeiger darauf. Deshalb musst du sagen, dass du einen Zeiger willst. In C++:

Node m_node

bedeutet, den Knoten genau hier zu speichern (und das kann eindeutig nicht für eine Liste funktionieren – Sie erhalten am Ende eine rekursiv definierte Struktur).

  • @SalmanA Das wusste ich bereits. Ich wollte nur wissen, warum es ohne einen Zeiger nicht funktionieren würde, was die akzeptierte Antwort viel besser erklärte.

    – m0meni

    10. April 2015 um 11:25 Uhr

  • @ AR7 Sie geben beide die gleiche Erklärung, knapp unter zwei verschiedenen Ansätzen. Wenn Sie es als “normale” Variable deklariert haben, würde es beim ersten Aufruf eines Konstruktors in einer neuen Instanz instanziiert. Aber bevor es mit der Instanziierung fertig ist – bevor der Konstruktor des ersten beendet ist – das Mitglied NodeDer eigene Konstruktor von würde aufgerufen, was eine weitere neue Instanz instanziieren würde … und Sie würden eine endlose Pseudo-Rekursion erhalten. Es ist nicht Ja wirklich streng und buchstäblich so sehr ein Größenproblem, wie es ein Leistungsproblem ist.

    – Panzerkrise

    10. April 2015 um 15:14 Uhr


  • Aber alles, was Sie wirklich wollen, ist nur ein Weg, um auf den nächsten in der Liste zu zeigen, nicht auf einen Node das ist eigentlich im ersten Node. Sie erstellen also einen Zeiger, was im Wesentlichen der Art und Weise entspricht, wie Java Objekte behandelt, im Gegensatz zu Primitives. Wenn Sie eine Methode aufrufen oder eine Variable erstellen, speichert Java keine Kopie des Objekts oder sogar das Objekt selbst; Es speichert einen Verweis auf ein Objekt, das im Wesentlichen ein Zeiger ist, um den ein bisschen wie ein Kinderhandschuh gewickelt ist. Dies sagen beide Antworten im Wesentlichen aus.

    – Panzerkrise

    10. April 2015 um 15:18 Uhr


  • Es ist kein Größen- oder Geschwindigkeitsproblem – es ist ein Unmöglichkeitsproblem. Das enthaltene Node-Objekt würde ein Node-Objekt enthalten, das ein Node-Objekt enthalten würde … Tatsächlich ist es unmöglich, es zu kompilieren

    – pm100

    10. April 2015 um 15:21 Uhr

  • @Panzercrisis Mir ist bewusst, dass beide die gleiche Erklärung geben. Dieser Ansatz war für mich jedoch nicht so hilfreich, da er sich auf das konzentrierte, was ich bereits verstanden hatte: wie Zeiger in C++ funktionieren und wie Zeiger in Java gehandhabt werden. Die akzeptierte Antwort gerichtet speziell Warum wäre es nicht möglich, einen Zeiger zu verwenden, da die Größe nicht berechnet werden kann? Andererseits beließ es dieser vage als „eine rekursiv definierte Struktur“. PS deine Erklärung, die du gerade geschrieben hast, erklärt es besser als beides: D.

    – m0meni

    10. April 2015 um 15:42 Uhr


C++ ist nicht Java. Wenn du schreibst

Node m_next;

in Java ist das dasselbe wie Schreiben

Node* m_next;

in C++. In Java ist der Zeiger implizit, in C++ explizit. Wenn du schreibst

Node m_next;

In C++ setzen Sie eine Instanz von Node direkt innerhalb des Objekts, das Sie definieren. Sie ist immer da und kann nicht weggelassen, ihr nicht zugeordnet werden new und es kann nicht entfernt werden. Dieser Effekt ist in Java unmöglich zu erreichen und unterscheidet sich völlig von dem, was Java mit derselben Syntax macht.

  • Etwas Ähnliches in Java zu erhalten, wäre wahrscheinlich “erweitert”, wenn SuperNode Node erweitert, SuperNodes alle Attribute von Node enthält und den gesamten zusätzlichen Speicherplatz reservieren muss. In Java können Sie also nicht “Knoten erweitert Knoten” ausführen.

    – Falko

    13. April 2015 um 9:58 Uhr

  • @Falco True, Vererbung ist eine Form der direkten Einbeziehung der Basisklassen. Da Java jedoch keine Mehrfachvererbung zulässt (im Gegensatz zu C++), können Sie nur eine Instanz einer einzelnen anderen bereits vorhandenen Klasse per Vererbung einbinden. Aus diesem Grund würde ich die Vererbung nicht als Ersatz für die direkte Einbeziehung von Mitgliedern betrachten.

    – Cmaster – Wiedereinsetzung von Monica

    13. April 2015 um 16:01 Uhr

Benutzer-Avatar
Nawaz

Sie verwenden einen Zeiger, sonst Ihren Code:

class Node
{
   //etc
   Node m_next; //non-pointer
};

…würde nicht compilieren, da der Compiler die Größe von nicht berechnen kann Node. Dies liegt daran, dass es von sich selbst abhängt – was bedeutet, dass der Compiler nicht entscheiden kann, wie viel Speicher er verbrauchen würde.

Letzteres (Node m_next) müssten enthalten der Knoten. Es würde nicht darauf hinweisen. Und es gäbe dann keine Verknüpfung von Elementen.

  • Schlimmer noch, es wäre logisch unmöglich, dass ein Objekt etwas vom gleichen Typ enthält.

    – Mike Seymour

    9. April 2015 um 16:20 Uhr

  • Würde es technisch gesehen nicht immer noch eine Verknüpfung geben, weil es ein Knoten wäre, der einen Knoten enthält, der einen Knoten enthält, und so weiter?

    – m0meni

    9. April 2015 um 16:20 Uhr

  • @AR7: Nein, Containment bedeutet, dass es sich buchstäblich innerhalb des Objekts befindet und nicht damit verknüpft ist.

    – Mike Seymour

    9. April 2015 um 16:22 Uhr

Benutzer-Avatar
Gemeinschaft

Der von Ihnen beschriebene Ansatz ist nicht nur mit C++ kompatibel, sondern auch mit seiner (größtenteils) Teilmengensprache C. Das Erlernen der Entwicklung einer verketteten Liste im C-Stil ist eine gute Möglichkeit, sich mit Low-Level-Programmiertechniken (z Speicherverwaltung), ist es aber im Allgemeinen nicht eine bewährte Methode für die moderne C++-Entwicklung.

Unten habe ich vier Varianten implementiert, wie man eine Liste von Elementen in C++ verwaltet.

  1. raw_pointer_demo verwendet den gleichen Ansatz wie Sie — manuelle Speicherverwaltung erforderlich mit der Verwendung von rohen Zeigern. Die Verwendung von C++ ist hier nur für syntethischer Zuckerund der verwendete Ansatz ist ansonsten mit der C-Sprache kompatibel.
  2. In shared_pointer_demo die Listenverwaltung wird immer noch manuell durchgeführt, die Speicherverwaltung jedoch schon automatisch (verwendet keine rohen Zeiger). Dies ist sehr ähnlich zu dem, was Sie wahrscheinlich mit Java erlebt haben.
  3. std_list_demo verwendet die Standard-Bibliothek list Container. Dies zeigt, wie viel einfacher die Dinge werden, wenn Sie sich auf vorhandene Bibliotheken verlassen, anstatt Ihre eigenen zu erstellen.
  4. std_vector_demo verwendet die Standard-Bibliothek vector Container. Dies verwaltet den Listenspeicher in einer einzigen zusammenhängenden Speicherzuweisung. Mit anderen Worten, es gibt keine Zeiger auf einzelne Elemente. Für bestimmte eher extreme Fälle kann dies erheblich ineffizient werden. Für typische Fälle ist dies jedoch die empfohlene Best Practice für die Listenverwaltung in C++.

Hinweis: Von all diesen nur die raw_pointer_demo erfordert tatsächlich, dass die Liste explizit zerstört wird, um ein “Leck” des Speichers zu vermeiden. Die anderen drei Methoden würden automatisch zerstört die Liste und ihren Inhalt, wenn der Container den Geltungsbereich verlässt (am Ende der Funktion). Der Punkt ist: C++ kann in dieser Hinsicht sehr “Java-ähnlich” sein — aber nur, wenn Sie sich dafür entscheiden, Ihr Programm mit den Ihnen zur Verfügung stehenden High-Level-Tools zu entwickeln.


/*BINFMTCXX: -Wall -Werror -std=c++11
*/

#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <memory>
using std::cerr;

/** Brief   Create a list, show it, then destroy it */
void raw_pointer_demo()
{
    cerr << "\n" << "raw_pointer_demo()..." << "\n";

    struct Node
    {
        Node(int data, Node *next) : data(data), next(next) {}
        int data;
        Node *next;
    };

    Node * items = 0;
    items = new Node(1,items);
    items = new Node(7,items);
    items = new Node(3,items);
    items = new Node(9,items);

    for (Node *i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr << "\n";

    // Erase the entire list
    while (items) {
        Node *temp = items;
        items = items->next;
        delete temp;
    }
}

raw_pointer_demo()...
9, 3, 7, 1

/** Brief   Create a list, show it, then destroy it */
void shared_pointer_demo()
{
    cerr << "\n" << "shared_pointer_demo()..." << "\n";

    struct Node; // Forward declaration of 'Node' required for typedef
    typedef std::shared_ptr<Node> Node_reference;

    struct Node
    {
        Node(int data, std::shared_ptr<Node> next ) : data(data), next(next) {}
        int data;
        Node_reference next;
    };

    Node_reference items = 0;
    items.reset( new Node(1,items) );
    items.reset( new Node(7,items) );
    items.reset( new Node(3,items) );
    items.reset( new Node(9,items) );

    for (Node_reference i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr<<"\n";

    // Erase the entire list
    while (items)
        items = items->next;
}

shared_pointer_demo()...
9, 3, 7, 1

/** Brief   Show the contents of a standard container */
template< typename C >
void show(std::string const & msg, C const & container)
{
    cerr << msg;
    bool first = true;
    for ( int i : container )
        cerr << (first?" ":", ") << i, first = false;
    cerr<<"\n";
}

/** Brief  Create a list, manipulate it, then destroy it */
void std_list_demo()
{
    cerr << "\n" << "std_list_demo()..." << "\n";

    // Initial list of integers
    std::list<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find( items.begin(), items.end(), 3), 8);
    show("B: ", items);

    // Sort the list
    items.sort();
    show( "C: ", items);

    // Erase '7'
    items.erase(std::find(items.begin(), items.end(), 7));
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}

std_list_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:

/** brief  Create a list, manipulate it, then destroy it */
void std_vector_demo()
{
    cerr << "\n" << "std_vector_demo()..." << "\n";

    // Initial list of integers
    std::vector<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find(items.begin(), items.end(), 3), 8);
    show( "B: ", items );

    // Sort the list
    sort(items.begin(), items.end());
    show("C: ", items);

    // Erase '7'
    items.erase( std::find( items.begin(), items.end(), 7 ) );
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}

std_vector_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:

int main()
{
    raw_pointer_demo();
    shared_pointer_demo();
    std_list_demo();
    std_vector_demo();
}

  • Schlimmer noch, es wäre logisch unmöglich, dass ein Objekt etwas vom gleichen Typ enthält.

    – Mike Seymour

    9. April 2015 um 16:20 Uhr

  • Würde es technisch gesehen nicht immer noch eine Verknüpfung geben, weil es ein Knoten wäre, der einen Knoten enthält, der einen Knoten enthält, und so weiter?

    – m0meni

    9. April 2015 um 16:20 Uhr

  • @AR7: Nein, Containment bedeutet, dass es sich buchstäblich innerhalb des Objekts befindet und nicht damit verknüpft ist.

    – Mike Seymour

    9. April 2015 um 16:22 Uhr

Überblick

Es gibt zwei Möglichkeiten, Objekte in C++ zu referenzieren und zuzuweisen, während es in Java nur eine Möglichkeit gibt.

Um dies zu erläutern, zeigen die folgenden Diagramme, wie Objekte im Speicher gespeichert werden.

1.1 C++-Elemente ohne Zeiger

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int          Code;
    char[50]     FirstName;
    char[50]     LastName;
    // "Address" IS NOT A pointer !!!
    AddressClass Address;
};

int main(...)
{
   CustomerClass MyCustomer();
     MyCustomer.Code = 1;
     strcpy(MyCustomer.FirstName, "John");
     strcpy(MyCustomer.LastName, "Doe");
     MyCustomer.Address.Code = 2;
     strcpy(MyCustomer.Address.Street, "Blue River");
     strcpy(MyCustomer.Address.Number, "2231 A");

   return 0;
} // int main (...)

.......................................
..+---------------------------------+..
..|          AddressClass           |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: Street            |..
..| [+] char[10]: Number            |..
..| [+] char[50]: POBox             |..
..| [+] char[50]: City              |..
..| [+] char[50]: State             |..
..| [+] char[50]: Country           |..
..+---------------------------------+..
.......................................
..+---------------------------------+..
..|          CustomerClass          |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: FirstName         |..
..| [+] char[50]: LastName          |..
..+---------------------------------+..
..| [+] AddressClass: Address       |..
..| +-----------------------------+ |..
..| | [+] int:      Code          | |..
..| | [+] char[50]: Street        | |..
..| | [+] char[10]: Number        | |..
..| | [+] char[50]: POBox         | |..
..| | [+] char[50]: City          | |..
..| | [+] char[50]: State         | |..
..| | [+] char[50]: Country       | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................

WarnungHinweis: Die in diesem Beispiel verwendete C++-Syntax ähnelt der Syntax in Java. Aber die Speicherzuordnung ist anders.

1.2 C++-Elemente, die Zeiger verwenden

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int           Code;
    char[50]      FirstName;
    char[50]      LastName;
    // "Address" IS A pointer !!!
    AddressClass* Address;
};

.......................................
..+-----------------------------+......
..|        AddressClass         +<--+..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: Street        |...|..
..| [+] char[10]: Number        |...|..
..| [+] char[50]: POBox         |...|..
..| [+] char[50]: City          |...|..
..| [+] char[50]: State         |...|..
..| [+] char[50]: Country       |...|..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|         CustomerClass       |...|..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: FirstName     |...|..
..| [+] char[50]: LastName      |...|..
..| [+] AddressClass*: Address  +---+..
..+-----------------------------+......
.......................................

int main(...)
{
   CustomerClass* MyCustomer = new CustomerClass();
     MyCustomer->Code = 1;
     strcpy(MyCustomer->FirstName, "John");
     strcpy(MyCustomer->LastName, "Doe");

     AddressClass* MyCustomer->Address = new AddressClass();
     MyCustomer->Address->Code = 2;
     strcpy(MyCustomer->Address->Street, "Blue River");
     strcpy(MyCustomer->Address->Number, "2231 A");

     free MyCustomer->Address();
     free MyCustomer();

   return 0;
} // int main (...)

Wenn Sie den Unterschied zwischen beiden Wegen überprüfen, werden Sie feststellen, dass bei der ersten Methode die Adressposition innerhalb des Kunden zugeordnet wird, während Sie bei der zweiten Methode jede Adresse explizit erstellen müssen.

Warnung: Java weist Objekte im Speicher wie bei dieser zweiten Technik zu, aber die Syntax ist wie bei der ersten Methode, was für “C++”-Neulinge verwirrend sein kann.

Implementierung

Ihr Listenbeispiel könnte also dem folgenden Beispiel ähnlich sein.

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

.......................................
..+-----------------------------+......
..|            Node             |......
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................v..
...................................[X].
.......................................

Zusammenfassung

Da eine verknüpfte Liste eine variable Anzahl von Elementen hat, wird der Speicher nach Bedarf und nach Verfügbarkeit zugewiesen.

AKTUALISIEREN:

Auch erwähnenswert, wie @hackks in seinem Beitrag kommentierte.

Dass Verweise oder Objektzeiger manchmal auf verschachtelte Elemente hinweisen (auch bekannt als „UML-Komposition“).

Und manchmal weisen Verweise oder Objektzeiger auf externe Elemente hin (auch bekannt als „UML-Aggregation“).

Aber verschachtelte Elemente derselben Klasse können nicht mit der “No-Pointer”-Technik angewendet werden.

1012850cookie-checkWarum verwenden verknüpfte Listen Zeiger, anstatt Knoten innerhalb von Knoten zu speichern?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy