Es ist einfach, verkettete Liste in C++ zu implementieren, wo Sie Zeiger haben. Aber wie werden sie in anderen Sprachen implementiert (wie Java, Python, etc). Ich möchte keine integrierte Klasse (die in JAVA unterstützt werden) für die Linked-List verwenden, aber was ich will, ist, wie man Zeiger ersetzt, um Linked-List zu erstellen?Wie werden verknüpfte Listen ohne Zeiger implementiert?
Sie werden mithilfe von Verweisen implementiert, die im Wesentlichen (ohne Syntax) Zeiger sind, mit denen Sie Zeigerarithmetik nicht ausführen können (in einigen Sprachen können sie auch nicht null sein). In vielen Sprachen sind Verweise die Standardmethode zur Verwendung von Variablen, anders als in C++, wo der Standardwert By-Value ist.
+1 Ich liebe diese Erklärung für Referenzen. Es ist so schnell, einfach und genau, abgesehen davon, dass es für C-Veteranen offensichtlich ist und anderen einen Grund gibt, diesen Aspekt der Programmierung zu lernen. – delnan
Mit anderen Sprachen befassen Sie sich mit Referenzen, die eng mit Zeigern verwandt sind.
Wenn Sie Ihre eigene Klasse schreiben, sagen class node und haben jeweils node ein Feld zum nächsten node halten, Sie halten tatsächlich einen Verweis auf das nächste Knoten (oder null, wenn es das letzte ist)
statt Zeiger, die auf einen Speicherblock zeigen, werden Referenzen verwendet, wie zuvor erwähnt. So wie Sie in C++
Struct Node {
Node *last;
Node *next;
}
haben würde, es würde so aussehen:
Struct Node {
Node last;
Node next;
}
Der letzte Satz ist bedauerlich. Wenn wir es als bare Münze nehmen, das heißt „' Node' ist ein Werttyp“, es bedeutet, Ihre zweite Definition von' Node' ungültig ist, weil es auf unendlich groß ist. Referenzen sind zwar keine Adressen, aber sie sind * Rückweisungen. – delnan
Ich habe gerade festgestellt, dass Ihr zweites Beispiel ungültig ist, obwohl die jetzt entfernte Erklärung ignoriert wird. (Wenn es angenommen hat, C++ sein, das ist.) – delnan
Es wurde einfach angenommen, eine Visualisierung in Pseudo-Code sein. Das Struct kam gerade von seinem Hintergrund in C++ –
Eine gute Datenstrukturen Klasse wird Ihnen zeigen, dass eine verknüpfte Liste kann in jeder Sprache mit Arrays implementiert werden, wie zum Beispiel Fortran.
Anstatt Zeiger zu verwenden, würden Sie andere Mittel verwenden, um den nächsten Link zu finden. Bei Arrays würden Sie anstelle eines Zeigers einen Index für das nächste Element verwenden.
So könnten Sie eine verkettete Liste in einer Direktzugriffsdatei implementieren, indem Sie die Dateiposition anstelle von Zeigern verwenden.
Ich bin nicht sicher, ob das als verkettete Liste zählt. Es hat definitiv andere Eigenschaften als die zeigerbasierte Implementierung, da es begrenzter ist. Abgesehen davon ist dies völlig nebensächlich, weil Sie * reguläre 'verknüpfte Listen (und alle anderen Datenstrukturen, die auf Indirection angewiesen sind) mit Referenzen erstellen können. – delnan
Es ist eine Liste, und es ist verknüpft. Es verwendet keine Zeiger zum Verknüpfen der Knoten. Es ist eine andere * Implementierung * einer verknüpften Liste. Das habe ich in meinem Data Structures-Kurs an der Universität gelernt. –
Vielleicht finden Sie eine gute Antwort in diesem Buch - http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 - Ich fasse zusammen, was ich für Sie erinnere.
Grundsätzlich haben Sie zwei Arrays von gleicher Größe (hoffentlich größer als n, wobei n = Anzahl der Elemente, die Sie speichern möchten). Wir nennen sie Array A und Array B.
Array A [i] enthält den Datenwert. Array B [i] hält den "nächsten" Wert "k", so dass A [i] -> next = A [k].
Hoffentlich hilft das.
Siehe meinen Kommentar zu Thomas Matthews Antwort. – delnan
Denken Sie daran, das Konzept einer verketteten Liste ist, dass Sie von einem Element zum anderen gelangen können. Wie Sie es tun, kann sehr unterschiedlich sein.
In C++ zum Beispiel haben Sie erwähnt, dass Sie Zeiger verwenden können. Eine andere Möglichkeit wäre, dass Sie die Speicheradresse des Objekts verwenden.
Aber das ist nur eine Möglichkeit. Wenn alle Ihre Objekte von einem Array referenziert würden, könnten Sie auf ein Objekt anhand seines Index auf diesem Array verweisen. So würde jedes Element in Ihrer verknüpften Liste eine Ganzzahl haben, die den Index des Objekts angibt, mit dem es verbunden ist.
Um Ihnen ein anderes Beispiel zu geben. Wenn Sie ein Wörterbuch hätten, in dem Sie Objekte mit Zeichenfolgen assoziierten. Dann könnten Sie Zeichenfolgen verwenden, um sich gegenseitig zu referenzieren.
Das Kernkonzept verknüpfte Listen sind keine Zeiger, es ist, dass die Elemente in der Liste sind verantwortlich Spur des Elements zu halten es verbunden ist.
Lesen Sie dies, und sehen Sie, ob es Ihre Frage ausreichend beantwortet: http://StackOverflow.com/Questions/7480783/Pointers-in-Java –
@Asawyer Nichts wird durch Verweis in Python und Java übergeben. Weder in vielen anderen Sprachen, die Referenzen im selben Sinne verwenden. – delnan
@asawyer: stimme mit delnan überein. Java ist pass-by-Wert. Immer. Dieser Wert kann eine Referenz sein, aber ein Wert ist das, was übergeben wird. –