Nun, Sie werden mit so etwas enden
%Vor% und jetzt versucht der C-Compiler herauszufinden, wie groß Item ist. Aber da next direkt in Item eingebettet ist, wird es mit einer Gleichung wie dieser enden
was unendlich ist. Daher haben wir ein Problem. Aus diesem Grund benötigt C Zeiger, so dass Sie
haben %Vor%was geschlossen ist. Interessanterweise speichern Sie, selbst wenn Sie dies in Sprachen wie Java, Python oder Haskell tun, implizit einen Zeiger (sie sagen Referenz), um den Zyklus zu unterbrechen. Sie verstecken nur die Tatsache von dir.
Sie müssen eigentlich nicht Zeiger verwenden, um eine Datenstruktur zu implementieren, die die Schnittstelle einer verknüpften Liste verfügbar macht, aber Sie tun brauchen sie, um die Leistung bereitzustellen Eigenschaften einer verknüpften Liste.
Was wären die Alternativen zu Zeigern? Nun, item muss eine Möglichkeit haben, sich auf das nächste Element zu beziehen. Es kann das nächste Element aus verschiedenen Gründen nicht zusammenfassen, eines davon ist, dass dies die Struktur "rekursiv" machen würde und daher nicht realisierbar wäre:
Was Sie können tun, ist ein Array von Elementen und implementieren Sie die verknüpfte Liste darüber:
%Vor%Das sieht so aus, als würde es funktionieren; Sie können eine Funktion haben, die Elemente zur Liste hinzufügt und eine andere, die sie löscht:
%Vor% Diese Funktionen würden entweder existing aus dem Array entfernen (wobei der next "Zeiger" des vorherigen Elements aktualisiert werden muss), einen leeren Slot erstellen oder das existing -Element finden und new in ein einfügen leerer Slot in storage (update next , um dorthin zu zeigen).
Das Problem dabei ist, dass die Operationen add_after und remove in konstanter Zeit nicht realisierbar sind, weil Sie jetzt in das Array suchen und es neu zuweisen müssen, wenn Sie keinen Speicherplatz mehr haben.
Da konstante Zeit add / remove ist der Grund, warum Leute eine verkettete Liste verwenden, macht dies den Non-Pointer-Ansatz nur als intellektuelle Übung nützlich. Für eine echte Liste bedeutet die Verwendung von Zeigern, dass Sie diese Operationen in konstanter Zeit ausführen können.
Zeiger werden für die dynamische Zuweisung von Speicher verwendet.
Sie können eine Liste als einfaches Array implementieren, aber das bedeutet, dass Sie einen durchgehenden Speicherbereich zuweisen, der für eine große Liste nicht effizient ist. Auch Arrays sind schwieriger zu erweitern (Sie müssen es neu zuweisen, wenn Sie seine maximale Größe erreichen).
Daher wird die dynamische Zuordnung für große Listen bevorzugt, und für jedes Element kann sie an beliebiger Stelle dauerhaft oder nicht gespeichert werden, und Sie können sie problemlos erweitern.
Außerdem können Sie nicht in einer struct item anderen struct item speichern, da die Struktur noch nicht definiert ist und die Größe der Struktur nicht festgelegt werden kann:
Dies ist nicht möglich :
%Vor%Daher werden Zeiger verwendet, da die Größe eines Zeigers bestimmt werden kann (die Größe einer ganzen Zahl auf dieser Plattform), wenn die Struktur kompiliert wird.
Ohne einen Zeiger enthält jedes Listenelement ein anderes Listenelement ( next ), das ein anderes Listenelement enthält. Das wiederum enthält einen anderen Listeneintrag. Und so weiter.
Sie erhalten eine unendlich große Datenstruktur, die unendlich viel Speicher benötigt, und das kann natürlich nicht funktionieren.
Sie benötigen keinen Zeiger, um eine Liste in C zu erstellen. Wenn eine Zeigerliste vorzuziehen ist, hängt dies von Ihrer Anwendung ab. Leute benutzten verkettete Listen, bevor sie ein Konzept von in Sprachen implementierten Zeigern hatten. Es ist nur manchmal für einige Leute einfacher zu verstehen (mit Zeigern). Sie brauchen auch keine Struktur mit Daten.
Ein einfaches Array wird gut funktionieren. Sie brauchen:
-1 (bedeutet nil oder NULL in der Pointer-Terminologie), oder 0 .. N-1 , bedeutet: der Array-Index des nächsten verknüpften Elements. Der Indexindex von index-array repräsentiert den Index des Elements im Datenarray. Das ist alles was du brauchst.
Ein Array anstelle einer Zeigerliste kann
habenBitte lesen Sie hier .
Ihr Beispiel würde daher aussehen wie:
%Vor%Das sollte alles sein, was Sie brauchen, um mit einem einfachen Testfall zu beginnen.
Wichtiger Zeiger in c
Vorteile: -
Die Ausführungsgeschwindigkeit ist hoch.
Zeiger ermöglichen uns den Zugriff auf die Variable außerhalb einer Funktion.
Reduzieren Sie die Größe unseres Codes.
ohne Zeiger: -
Die Code-Größe wird erhöht.
Wir können die Daten nicht effizient verwalten.
In der Liste wird der Zeiger verwendet, um das nächste Element aus der Liste zu zeigen. Wenn Sie nicht deklariert sind, bedeutet dies, dass Sie nicht auf mehr als ein Element aus der Liste zugreifen können.
Wenn Sie zur Laufzeit dynamisch etwas Speicher reservieren, werden die Zeiger wirklich benötigt.
Es gibt mehr als eine Art von "Liste". Die Implementierung, die Sie zeigen, ist eine "Verknüpfte Liste". Ohne Zeiger gäbe es keine "Links", also müssten wir uns andere Arten von Listen ansehen.
Also, zuerst, was passiert, wenn Sie einfach * aus der Strukturdefinition entfernen: Es wird nicht kompiliert. Sie können eine Struktur innerhalb einer anderen Struktur enthalten, aber wenn es eine Rekursion gibt, dann wird die Struktur unendliche Größe haben, die nicht passieren wird!
Wie wäre es mit einem Array als Liste?
%Vor%Ja, das klappt, aber jetzt hat deine Liste eine feste Größe.
Ok, lassen Sie uns die Liste dynamisch zuweisen:
%Vor%Dann müssen Sie jedes Mal, wenn Sie der Liste hinzufügen, Folgendes tun:
%Vor%OK, das funktioniert, aber jetzt teilen wir den Speicher häufig neu zu, was zu vielen Speicherkopien und Ineffizienz führt.
Andererseits, wenn die Liste sehr selten aktualisiert wird, ist dies platzsparender, und das könnte eine gute Sache sein.
Ein weiterer Nachteil der Verwendung eines Arrays besteht darin, dass Vorgänge wie Push, Pop, Sort, Reverse usw. sehr viel teurer werden; Sie alle bedeuten mehrere Speicherkopien.
Es gibt andere Arten von "Listen", aber alle beinhalten Zeiger, also denke ich, dass wir sie hier ignorieren können.
Tags und Links c pointers linked-list