[Powered by Google Translate] Bei der Programmierung müssen wir oft Listen von Werten darstellen,
wie die Namen der Schüler in einem Abschnitt
oder deren Noten auf dem neuesten Quiz.
>> In der Sprache C, erklärte Arrays verwendet werden können
um Listen speichern.
Es ist einfach, die Elemente einer Liste aufzuzählen
gespeichert in einem Array, und wenn Sie den Zugriff auf
oder ändern das i-te Listenelement
für einige beliebiger Index I,
Das kann in konstanter Zeit durchgeführt werden,
aber Arrays haben auch Nachteile.
>> Wenn wir ihnen erklären, wir müssen sagen,
vorne wie groß sie sind,
das heißt, wie viele Elemente sie speichern können
und wie groß diese Elemente sind, die durch deren Art bestimmt.
Zum Beispiel, int arr (10)
können 10 Einträge speichern
das sind die Größe eines int.
>> Wir können nicht ändern eines Arrays der Größe nach Erklärung.
Wir haben ein neues Array machen, wenn wir mehr Elemente speichern möchten.
Der Grund dafür Einschränkung besteht darin, dass unsere
Programm speichert das gesamte Array
als zusammenhängender Block arbeiten.
Sagen, das ist der Puffer, wo wir in unserem Array gespeichert.
Es können auch andere Variablen
befindet sich direkt neben dem Array
im Speicher, so können wir nicht
nur das Array größer.
>> Manchmal möchten wir die Array-schnellen Datenzugriff Geschwindigkeit Handel
für etwas mehr Flexibilität.
Geben Sie die verknüpfte Liste, weitere grundlegende Datenstruktur
Sie ist vielleicht nicht so vertraut sind.
Auf einer hohen Ebene,
eine verkettete Liste speichert Daten in einer Folge von Knoten
daß miteinander mit Links verbunden sind,
daher der Name "verketteten Liste."
Wie wir sehen werden, ist dieser Unterschied im Design
führt zu unterschiedlichen Vor-und Nachteile
als ein Array.
>> Hier einige C-Code für eine sehr einfache verknüpfte Liste von Zahlen.
Sie können sehen, dass wir jeden Knoten vertreten
in der Liste als eine Struktur, welche 2 Dinge enthält,
eine ganze Zahl zu speichern als 'val'
und einen Link zu dem nächsten Knoten in der Liste
die wir vertreten als Zeiger namens "Weiter".
Auf diese Weise können wir den gesamten Liste
mit nur einem Zeiger auf den ersten Knoten
und dann können wir folgen die nächsten Zeiger
dem zweiten Knoten,
dem dritten Knoten,
dem vierten Knoten,
und so weiter, bis wir an das Ende der Liste zu gelangen.
>> Sie könnten in der Lage sein ein Vorteil, dies zu sehen
über die statische Array-Struktur - mit einer verketteten Liste,
wir brauchen nicht einen großen Teil des Speichers insgesamt.
Der erste Knoten der Liste könnte an dieser Stelle in Erinnerung zu leben,
und der zweite Knoten könnte den ganzen Weg hierher sein.
Wir können alle Knoten zu erhalten, egal wo im Speicher sind,
, weil ab dem 1. Knoten, wobei jeder Knoten nächste Zeiger
sagt uns genau, wo zum nächsten gehen.
>> Darüber hinaus haben wir nicht zu sagen, bis vor
wie groß eine verlinkte Liste wird die Art, wie wir mit statischen Arrays,
da können wir halten das Hinzufügen von Knoten zu einer Liste
Solange es Raum irgendwo im Speicher zum neuen Knoten.
Daher sind verkettete Listen einfach zu dynamisch ändern.
Sprich, später im Programm haben wir weitere Knoten hinzufügen müssen
in unsere Liste.
Um einen neuen Knoten in unsere Liste einzufügen on the fly,
alles, was wir tun müssen, ist Speicher für diesen Knoten
plop in dem Datenwert,
und dann legen Sie sie, wo wir durch Einstellung der entsprechenden Zeigern wollen.
>> Zum Beispiel, wenn wir wollten, um einen Knoten zwischen platzieren
die zweite und dritte Knoten der Liste
hätten wir nicht die zweite oder dritte Knoten überhaupt zu bewegen.
Sagen, dass wir das Einfügen dieses rote Knoten.
Alles, was wir zu tun haben möchte, ist die neue Knoten nächste Zeiger gesetzt
um zu der dritten Knotenpunkt
und dann verkabeln des zweiten Knotens nächste Zeiger
bis zum neuen Knotenpunkt.
So können wir unsere Listen on the fly ändern
da unsere Computer nicht Indexierung verlassen,
sondern auf die Verknüpfung mit Zeigern, um sie zu speichern.
>> Allerdings verknüpft ein Nachteil von Listen
ist, dass, im Gegensatz zu einem statischen Array,
Der Computer kann nicht nur auf die Mitte der Liste zu springen.
Da der Computer muss jeder Knoten in der verketteten Liste zu besuchen
um zum nächsten zu gelangen,
es wird länger dauern, einen bestimmten Knoten zu finden
als es in einem Array.
Zu durchqueren die gesamte Liste braucht Zeit proportional
der Länge der Liste,
oder O (n) in asymptotischen Notation.
Im Durchschnitt erreichen alle Knoten
Auch braucht Zeit proportional zu n.
>> Lassen Sie uns nun tatsächlich Code schreiben
das funktioniert mit verknüpften Listen.
Lassen Sie uns sagen, wir wollen eine verknüpfte Liste von Zahlen.
Wir können einen Knoten in unserer Liste wieder vertreten
als struct mit 2 Feldern,
ein Integer-Wert namens "val"
und ein nächster Zeiger auf den nächsten Knoten in der Liste.
Nun, es scheint einfach genug.
>> Lassen Sie uns sagen, wir wollen eine Funktion schreiben
die Traversen die Liste ein und druckt die
Wert in den letzten Knoten der Liste gespeichert.
Nun, das heißt, wir müssen alle Knoten in der Liste durchlaufen
um den letzten zu finden, aber da wir nicht das Hinzufügen
oder etwas zu löschen, wollen wir nicht zu ändern
Die innere Struktur der nächste Zeiger in der Liste.
>> Also, wir einen Zeiger speziell brauchen für Traversierung
die nennen wir "Crawler".
Es wird durch alle Elemente der Liste kriechen
indem Sie die Kette der nächsten Zeiger.
Alle uns gespeichert ist ein Zeiger auf den ersten Knoten,
oder "Kopf" der Liste.
Kopf zeigt auf den ersten Knoten.
Es ist vom Typ Zeiger-zu-Knoten.
>> Um die tatsächliche ersten Knoten in der Liste zu bekommen,
Wir haben zu dereferenzieren diesen Zeiger,
aber bevor wir es dereferenzieren, müssen wir überprüfen,
wenn sich der Zeiger null erste.
Wenn es null ist, ist die Liste leer,
und wir sollten Sie auch eine Nachricht, die, weil die Liste leer ist,
es gibt keine letzte Knoten.
Aber, sagen wir mal die Liste nicht leer ist.
Wenn es nicht ist, dann sollten wir uns durch die gesamte Liste zu kriechen
bis wir zu dem letzten Knoten der Liste
und wie können wir sagen, ob wir bei der letzten Knoten in der Liste suchen?
>> Nun, wenn eines Knotens nächste Zeiger null,
Wir wissen, dass wir am Ende
seit der letzten nächste Zeiger hätte keine nächsten Knoten in der Liste, um zu zeigen.
Es ist gute Praxis, immer der letzte Knoten der nächste Zeiger mit null initialisiert
eine standardisierte Eigenschaft, die uns warnt, wenn wir das Ende der Liste erreicht haben müssen.
>> Also, wenn Crawler → weiter null ist,
daran erinnern, dass der Pfeil-Syntax eine Abkürzung für Dereferenzierung ist
ein Zeiger auf eine struct, dann Zugriff auf
ihre nächste Feld entspricht der misslichen:
(* Crawler). Nächsten.
Nachdem wir den letzten Knoten gefunden,
Wir wollen Crawler → val drucken,
der Wert in dem aktuellen Knoten
die wir kennen, ist das letzte.
Andernfalls, wenn wir noch nicht auf dem letzten Knoten in der Liste,
Wir müssen weiter an den nächsten Knoten in der Liste
und prüfen, ob das ist das letzte.
Um dies zu tun, setzen wir einfach unser Crawler Zeiger
Um zu den aktuellen Knotens nächsten Wert darauf,
das heißt, der nächste Knoten in der Liste.
Dies wird getan, indem
Crawler = Crawler → weiter.
Dann wiederholen wir diesen Prozess mit einer Schleife zum Beispiel
bis wir den letzten Knoten.
So, zum Beispiel, wenn Crawler wurde Kopf nach,
setzen wir Crawler zu Crawler → weiter zeigen,
das ist der gleiche wie der nächste Feld des ersten Knotens.
So, jetzt unser Crawler auf den zweiten Knoten zeigt,
und wiederum wiederholen wir dies mit einer Schleife,
bis wir den letzten Knoten gefunden, das heißt,
wo der Knoten nächsten Zeiger zeigt auf null.
Und da haben wir es,
haben wir den letzten Knoten in der Liste gefunden, und um seinen Wert zu drucken,
verwenden wir nur Crawler → val.
>> Verfahrgeschwindigkeit ist nicht so schlimm, aber was ist das Einfügen?
Lets sagen, wir wollen eine ganze Zahl in die vierte Position einzufügen
in einer Integer-Liste.
Das heißt zwischen den 3. und 4. aktuellen Knoten.
Auch hier haben wir die Liste nur zu durchqueren
bekommen die dritte Element, die wir nach dem Einsetzen sind.
So schaffen wir einen Crawler Zeiger wieder auf die Liste zu durchlaufen,
überprüfen, ob unser Kopf Zeiger ist null,
und wenn es nicht ist, zeigen unsere Crawler Zeiger auf dem Head-Knoten.
Also, wir sind auf dem ersten Element.
Wir müssen vorwärts gehen 2 weitere Elemente, bevor wir einfügen können,
so können wir eine for-Schleife verwenden
int i = 1; i <3; i + +
und in jeder Iteration der Schleife,
voranzutreiben unser Crawler Zeiger vorwärts mit 1 Knoten
durch Prüfen, ob der aktuelle Knoten der nächsten Feld null ist,
und wenn es nicht ist, bewegen unsere Crawler Zeiger auf den nächsten Knoten
indem sie gleich des aktuellen Knotens nächste Zeiger.
So, da unsere for-Schleife, sagt das zu tun
zweimal,
wir haben den dritten Knoten erreicht,
und einmal unser Crawler Zeiger hat den Knoten erreicht nach
die wollen wir unsere neuen Integer einzufügen,
Wie können wir eigentlich nicht das Einfügen?
>> Nun, unsere neue Zahl in die Liste eingefügt werden
als Teil seiner eigenen Knoten struct,
da dies eigentlich eine Sequenz von Knoten.
Also, lasst uns einen neuen Zeiger auf Knoten
namens 'new_node "
und setzen Sie ihn in den Speicher verweisen, dass wir nun die Möglichkeit
auf dem Heap für den Knoten selbst,
und wie viel Speicher brauchen wir zu vergeben?
Nun, in der Größe eines Knotens,
und wir wollen ihre val Feld auf die Zahl, die wir einfügen wollen eingestellt.
Lassen Sie uns sagen, 6.
Nun enthält der Knoten unserer Integer-Wert.
Es ist auch ratsam, des neuen Knotens nächste Feld zu initialisieren
darauf auf null
aber was nun?
>> Wir müssen die innere Struktur der Liste zu ändern
und die nächsten Zeiger in der Liste der vorhandenen enthalten
Dritte und vierte Knoten.
Da die nächsten Zeiger bestimmt die Reihenfolge der Liste,
und da wir das Einfügen unserer neuen Knoten
direkt in die Mitte der Liste,
kann es ein bisschen schwierig.
Dies liegt daran, denkt daran, unsere Computer
kennt nur die Position der Knoten in der Liste
wegen der nächsten Zeiger in den vorherigen Knoten gespeichert.
Also, wenn wir jemals aus den Augen verloren einem dieser Orte,
sagen, indem einer der nächsten Zeiger in unserer Liste
zum Beispiel, sagen wir, verändert
der dritte Knoten nächsten Feld
bis zu einem gewissen Knoten über hier zu zeigen.
Wir hatten kein Glück, denn würden wir nicht
eine Idee haben, wo der Rest der Liste zu finden,
und das ist natürlich wirklich schlecht.
Also, wir haben wirklich vorsichtig sein über die Reihenfolge
in denen wir manipulieren unsere nächsten Zeiger beim Einführen.
>> Also, um dies zu vereinfachen, sagen wir, dass
unser erstes 4-Knoten
heißen A, B, C und D, mit den Pfeilen, die die Kette von Zeigern
, die die Knoten verbinden.
Also müssen wir unsere neuen Knoten einfügen
im zwischen den Knoten C und D.
Es ist wichtig, um sie in der richtigen Reihenfolge zu tun, und ich werde Ihnen zeigen, warum.
>> Lasst uns an der falschen Weg, um es zuerst tun suchen.
Hey, kennen wir die neuen Knoten zu kommen, nachdem C rechts,
also lasst uns gesetzt C der nächste Zeiger
zeigen soll new_node.
Alles klar, scheint okay, wir haben nur zu Ende zu bringen nun durch
Damit ist das neue Knoten nächste Zeiger Punkt D,
aber warten, wie können wir das tun?
Das einzige, was uns sagen konnte, wo D war,
wurde der nächste Zeiger zuvor in C gespeichert,
aber wir schrieben den Zeiger
auf den neuen Knotenpunkt,
so haben wir nicht mehr eine Ahnung, wo D ist in Erinnerung,
und wir haben den Rest der Liste verloren.
Überhaupt nicht gut.
>> Also, wie machen wir das richtig verstanden?
Zum einen weisen die neuen Knoten der nächsten Zeiger auf D.
Nun werden sowohl die neuen Knotens und C der nächste Zeiger
sind mit dem gleichen Knoten, D weisende,
aber das ist in Ordnung.
Jetzt können wir zeigen C der nächste Zeiger auf den neuen Knoten.
Also haben wir diese ohne Datenverlust durchgeführt.
In Code ist C der aktuelle Knoten
dass die Traversierung Zeiger Crawler verweist,
und D wird durch den Knoten, auf die durch den aktuellen Knotens nächste Feld repräsentiert,
oder Crawler → weiter.
Also, wir zunächst des neuen Knotens nächste Zeiger
zu Crawler → weiter zeigen,
auf die gleiche Weise haben wir gesagt new_node der nächste Zeiger sollte
weisen auf D in der Abbildung.
Dann, können wir des aktuellen Knotens nächste Zeiger
auf unserer neuen Knoten
so wie wir warten, bis Punkt C in der Zeichnung new_node hatte.
Jetzt ist alles in Ordnung, und wir nicht verlieren
den Überblick über alle Daten, und wir konnten nur
aufkleben unserem neuen Knotens in der Mitte der Liste
ohne Umbau der ganzen Sache oder sogar verschieben alle Elemente
die Art und Weise würden wir mit einem festen Array der Länge gehabt haben.
>> So sind verkettete Listen eine grundlegende, aber wichtige dynamische Datenstruktur
die haben beide Vor-und Nachteile
gegenüber Arrays und anderen Datenstrukturen,
und wie es oft der Fall, in der Informatik,
ist es wichtig zu wissen, wann man jedes Werkzeug verwendet,
so können Sie abholen das richtige Werkzeug für den richtigen Job.
>> Für weitere Übungen versuchen, schriftlich Funktionen
Löschen von Knoten aus einer verketteten Liste -
erinnern, vorsichtig zu sein über die Reihenfolge, in der Sie neu anordnen
Ihren nächsten Zeiger um sicherzustellen, dass Sie nicht verlieren ein Stück Ihrer Liste -
oder eine Funktion, um die Knoten in einer verknüpften Liste zählen,
oder eine lustige ein, um die Reihenfolge der alle Knoten in einer verknüpften Liste rückgängig zu machen.
>> Mein Name ist Jackson Steinkamp, ​​ist dies CS50.