c++ - verkettete - zentut linked list




Making Generic Linked-Liste platzieren nächsten Zeiger am Anfang der Struktur (2)

Das Buch, das Sie betrachten, Programming Interviews Exposed , ist (soweit ich das beurteilen kann) kein Buch über C ++, sondern ein Buch, das Sie darauf vorbereiten soll, die Art von Fragen zu beantworten, die bei einem typischen technischen Interview gestellt werden könnten . Ich würde nichts in dem Buch als eine beste C ++ Praxis nehmen, es sei denn, es ist als solches gekennzeichnet (und vielleicht nicht einmal dann).

Der Hinweis, den nächsten Zeiger zuerst in eine Struktur einer verknüpften Listenknotenposition zu bringen, kommt von Sprachen wie C, wo Sie sich nicht auf echte, vom Compiler unterstützte Vererbung verlassen können. Die Idee ist in der Tat, etwas wie Vererbung selbst zu implementieren, indem man Daten auf die Struktur der verknüpften Listenknoten packt. Erwägen:

typedef struct LinkedList {
  LinkedListNode* next;
  int type;
}

typedef struct Person {
  LinkedList listNode;
  char name[64];
  int age;
}

typedef struct Address {
  LinkedList listNode;
  char streetAddress[128];
  char city[32];
  char state[2];
  char zip[10];
}

typedef struct Employee {
  Person person;
  int department;
  int salary;
}

LinkedList ist hier ein Basistyp - für sich allein nicht gut, aber nützlich als Ausgangspunkt für Knoten mit mehr Daten. Sie müssen nichts über die anderen Typen wissen, um verknüpfte Listenoperationen auf einem Knoten auszuführen ... Sie können jeden Knotenzeiger auf LinkedList * umwandeln und auf die benötigten Informationen zugreifen. So können Sie eine Liste von Personen und Adresslisten erstellen, und beide können mit denselben Routinen bearbeitet werden. Ebenso können Sie einen Mitarbeiter * in eine Person * umwandeln und alle Operationen verwenden, die Sie auch für Person für Mitarbeiter geschrieben haben. Wenn Sie dem Typfeld von LinkedList entsprechende Konstanten zuweisen, können Sie sogar PersonNode mischen und das Typfeld verwenden, um später den Typ jedes Knotens zu bestimmen.

Dies war eine nützliche Art, vor 20 Jahren zu programmieren. Es funktioniert natürlich immer noch, aber die meisten Leute würden sich entscheiden, den Compiler die Vererbung für sie verwalten zu lassen, wenn sie die Option haben, und alle modernen objektorientierten Sprachen bieten diese Option an.

Lektion: Verstehen Sie die Technik für den Fall, dass Sie in altem Code darauf stoßen, aber wählen Sie gegebenenfalls eine andere Implementierung für Ihren neuen Code.

Ich lese eines der Bücher und stehe bei einer bestimmten Frage fest.

Definition einer Struktur für verkettete Liste :::

typedef struct LinkedList{
  LinkedList* next;
  int data;
}

Buch sagt "Platzieren des nächsten Zeigers am Anfang der Struktur oder Klasse macht es einfach, allgemeine Listenbehandlungsroutinen zu schreiben, egal was die Daten beinhalten."

Ich kann nicht verstehen, wie hier die Platzierung des nächsten Zeigers hilft.

Um eine generische Liste zu erstellen, benötigen wir nicht den Datentyp generic oder say void *?


Ich persönlich sehe keinen Grund, und ich stimme zu, das Argument sollte vorgetäuscht werden:

template <class T> class ListElement
{
   T data;
   ListElement* next;
   ...
}

Es kann einige Probleme hinsichtlich der Geschwindigkeit geben, bei der die Speicherausrichtung etwas besser ist, aber das bezweifle ich!

h

Mario