1 00:00:00,000 --> 00:00:02,832 >> [Musikwiedergabe] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> DOUG LLOYD: OK, so zumin dieser Punkt im Verlauf, 4 00:00:08,560 --> 00:00:15,300 wir haben eine Menge von den Grundlagen der C abgedeckt Wir wissen eine Menge über Variablen, Arrays, 5 00:00:15,300 --> 00:00:17,610 Zeiger, alles, gute Sachen. 6 00:00:17,610 --> 00:00:21,610 Das sind alles Art gebaut in die als die Grundlagen sehen 7 00:00:21,610 --> 00:00:23,880 aber wir können noch mehr tun, nicht wahr? 8 00:00:23,880 --> 00:00:27,930 Wir können Dinge zu kombinieren zusammen auf interessante Weise. 9 00:00:27,930 --> 00:00:31,010 >> Und so wollen wir das tun, lassen Sie uns beginnen um aus dem, was C gibt uns zu verzweigen, 10 00:00:31,010 --> 00:00:35,270 und beginnen, unsere eigenen Daten zu erstellen Strukturen unter Verwendung dieser Gebäude 11 00:00:35,270 --> 00:00:40,590 Blöcke zusammen, um etwas zu tun, wirklich wertvoll, nützlich. 12 00:00:40,590 --> 00:00:43,420 Ein Weg, können wir dies zu tun ist über Sammlungen sprechen. 13 00:00:43,420 --> 00:00:48,360 Also so weit haben wir eine Art von Daten hatte Struktur zum Darstellen Sammlungen 14 00:00:48,360 --> 00:00:51,030 der gerne Werte, ähnliche Werte. 15 00:00:51,030 --> 00:00:52,350 Das wäre ein Array sein. 16 00:00:52,350 --> 00:00:57,020 Wir haben Sammlungen von ganzen Zahlen oder Sammlung von Zeichen und so weiter. 17 00:00:57,020 --> 00:01:00,890 >> Strukturen werden auch von einem Daten sortieren Struktur zum Sammeln von Informationen, 18 00:01:00,890 --> 00:01:03,220 aber es ist nicht für das Sammeln wie Werte. 19 00:01:03,220 --> 00:01:08,090 Es mischt sich in der Regel unterschiedliche Datentypen zusammen in einer einzigen Box. 20 00:01:08,090 --> 00:01:10,750 Aber es ist nicht selbst zusammen zur Ketten 21 00:01:10,750 --> 00:01:16,920 oder miteinander verbinden ähnliche Einzelteile, wie ein Array. 22 00:01:16,920 --> 00:01:20,960 Arrays sind für Element auf, sondern Rückruf 23 00:01:20,960 --> 00:01:24,262 , dass es sehr schwierig ist um in ein Array einfügen, 24 00:01:24,262 --> 00:01:26,470 es sei denn, wir sind bei Einsetzen das Ende des Arrays. 25 00:01:26,470 --> 00:01:29,730 >> Und das beste Beispiel habe ich denn das ist Insertion Sort. 26 00:01:29,730 --> 00:01:31,650 Wenn Sie sich unser Video erinnern on Insertion Sort, 27 00:01:31,650 --> 00:01:34,110 es gab eine Menge von Aufwand mit einbezogen 28 00:01:34,110 --> 00:01:37,970 abholen Elemente und verschieben sie aus dem Weg, um etwas zu passen 29 00:01:37,970 --> 00:01:41,290 in der Mitte des Arrays. 30 00:01:41,290 --> 00:01:44,690 Arrays leiden auch unter einem anderen Problem, das ist mangelnde Flexibilität. 31 00:01:44,690 --> 00:01:47,150 Wenn wir erklären, ein Array, wir bekommen einen Schuss auf ihn. 32 00:01:47,150 --> 00:01:49,790 Wir bekommen zu sagen, ich will so viele Elemente. 33 00:01:49,790 --> 00:01:51,940 Vielleicht 100, könnte es sein 1000, könnte es 34 00:01:51,940 --> 00:01:55,930 sein, worin x eine Zahl ist, dass der Benutzer hat uns mit einer Eingabeaufforderung oder in der Befehls 35 00:01:55,930 --> 00:01:56,630 Linie. 36 00:01:56,630 --> 00:01:59,905 >> Aber wir nur einen Schuss auf ihn zu bekommen, die wir nicht bekommen, um dann sagen, oh, eigentlich habe ich 37 00:01:59,905 --> 00:02:04,360 benötigt 101, oder ich brauchte x plus 20. 38 00:02:04,360 --> 00:02:07,910 Zu spät, die wir bereits erklärt haben, die Array und wenn wir wollen, um 101 oder erhalten x 39 00:02:07,910 --> 00:02:12,050 plus 20, müssen wir erklären, ein ganz anderes Array, 40 00:02:12,050 --> 00:02:15,540 kopieren Sie alle Elemente des Arrays über, und dann haben wir genug. 41 00:02:15,540 --> 00:02:19,880 Und was, wenn wir uns wieder falsch sind, was wenn wir wirklich brauchen 102 oder x plus 40, 42 00:02:19,880 --> 00:02:21,970 müssen wir dies wieder tun. 43 00:02:21,970 --> 00:02:26,250 So sind sie sehr unflexibel für die Größenänderung unsere Daten, 44 00:02:26,250 --> 00:02:29,360 aber wenn wir zusammen etwas zu kombinieren von den Grundlagen, die wir bereits haben 45 00:02:29,360 --> 00:02:33,230 über Zeiger und Strukturen gelernt, insbesondere unter Verwendung von dynamischen Speicher 46 00:02:33,230 --> 00:02:36,180 Belegung mit malloc, wir können diese Stücke zusammen 47 00:02:36,180 --> 00:02:40,960 um eine neue Daten structure-- a erstellen einfach verkettete Liste könnten wir sagen-- 48 00:02:40,960 --> 00:02:45,400 dass ermöglicht es uns, zu wachsen und Schrumpf eine Sammlung von Werten 49 00:02:45,400 --> 00:02:48,800 und wir werden keinen Platz verschwendet. 50 00:02:48,800 --> 00:02:53,320 >> Also noch einmal, nennen wir diese Idee, dieser Begriff, eine verknüpfte Liste. 51 00:02:53,320 --> 00:02:56,320 Insbesondere in diesem Video sind wir reden einfach verkettete Liste, 52 00:02:56,320 --> 00:02:59,185 und dann ein anderes Video wir reden etwa doppelt verkettete Listen, die 53 00:02:59,185 --> 00:03:01,560 ist nur eine Variation über ein Thema hier. 54 00:03:01,560 --> 00:03:05,200 Aber eine einfach verkettete Liste wird aus Knoten, 55 00:03:05,200 --> 00:03:08,559 Knoten gerade eine abstrakte term-- es ist nur etwas, was ich rufe 56 00:03:08,559 --> 00:03:10,350 das ist eine Art von Struktur, im Grunde bin ich? 57 00:03:10,350 --> 00:03:16,190 Nur gehen, nennen es einen node-- und dies Knoten zwei Mitglieder oder zwei Felder. 58 00:03:16,190 --> 00:03:20,300 Es verfügt über Daten, in der Regel ein ganze Zahl, ein Zeichen, float, 59 00:03:20,300 --> 00:03:23,790 oder könnte ein anderer Datentyp sein , dass Sie mit einer Art def definiert haben. 60 00:03:23,790 --> 00:03:29,290 Und einen Zeiger auf enthält einen anderen Knoten des gleichen Typs. 61 00:03:29,290 --> 00:03:34,710 >> So haben wir zwei Dinge im Inneren des Dieser Knoten, Daten und einen Zeiger 62 00:03:34,710 --> 00:03:36,380 zu einem anderen Knoten. 63 00:03:36,380 --> 00:03:39,370 Und wenn Sie beginnen zu visualisieren Damit kann man darüber nachdenkt, 64 00:03:39,370 --> 00:03:42,280 wie eine Kette von Knoten, sind miteinander verbunden. 65 00:03:42,280 --> 00:03:45,070 Wir haben den ersten Knoten, es Daten enthält, und einen Zeiger 66 00:03:45,070 --> 00:03:49,110 an den zweiten Knoten, der enthält Daten und einen Zeiger auf den dritten Knoten. 67 00:03:49,110 --> 00:03:52,940 Und damit ist, warum es eine nennen wir verknüpften Liste, sie miteinander verbunden sind. 68 00:03:52,940 --> 00:03:56,070 >> Was bedeutet diese Sonder Knotenstruktur aus? 69 00:03:56,070 --> 00:04:01,120 Nun, wenn Sie aus unserem Video on erinnern Definition von benutzerdefinierten Typen, mit Typ-def, 70 00:04:01,120 --> 00:04:05,400 können wir eine structure-- definieren und Geben Sie definieren eine Struktur wie diese. 71 00:04:05,400 --> 00:04:11,240 tyepdef struct sllist, und dann bin ich Verwendung hier das Wort ein Wert beliebig 72 00:04:11,240 --> 00:04:13,891 um beliebige Datentypen richtig anzuzeigen. 73 00:04:13,891 --> 00:04:16,890 Sie könnten auf Integer oder Float übergeben, könnten Sie haben, was Sie wollen. 74 00:04:16,890 --> 00:04:19,389 Es ist nicht nur beschränkt ganzen Zahlen, oder so etwas. 75 00:04:19,389 --> 00:04:22,790 So Wert ist nur ein beliebiger der Datentyp und dann ein Zeiger 76 00:04:22,790 --> 00:04:26,310 an einen anderen Knoten des gleichen Typs. 77 00:04:26,310 --> 00:04:29,690 >> Nun, es ist ein wenig fangen hier mit der Definition einer Struktur 78 00:04:29,690 --> 00:04:33,030 wenn es eine Selbstbezugsstruktur. 79 00:04:33,030 --> 00:04:35,340 Ich habe einen temporären zu haben, Namen für meine Struktur. 80 00:04:35,340 --> 00:04:37,640 Am Ende des Tages habe ich es nennen wollen, klar 81 00:04:37,640 --> 00:04:43,030 SLL-Knoten, das ist schließlich das neue nennen Teil meiner Typ-Definition, 82 00:04:43,030 --> 00:04:47,450 aber ich kann nicht verwenden sll Knoten in der Mitte davon. 83 00:04:47,450 --> 00:04:51,430 Der Grund dafür ist, habe ich nicht schuf eine sll Knotentyp genannt 84 00:04:51,430 --> 00:04:55,200 bis ich hier aus den letzten Punkt. 85 00:04:55,200 --> 00:04:59,720 Bis zu diesem Zeitpunkt muss ich haben Ein anderer Weg zu dieser Datentyp. 86 00:04:59,720 --> 00:05:02,440 >> Und dies ist ein selbst Referenzdatentyp. 87 00:05:02,440 --> 00:05:06,314 Es; s Datentyp ein Struktur, die einen Daten enthält, 88 00:05:06,314 --> 00:05:08,480 und einen Zeiger auf ein anderes Struktur des gleichen Typs. 89 00:05:08,480 --> 00:05:11,750 Also muss ich in der Lage, zu beziehen sein Dieser Datentyp wenigstens vorübergehend 90 00:05:11,750 --> 00:05:14,910 so gibt es eine vorübergehende Name des struct sllist 91 00:05:14,910 --> 00:05:18,540 erlaubt mir dann sagen, ich möchte ein Zeiger auf eine andere Struktur sllist, 92 00:05:18,540 --> 00:05:24,690 eine Struktur sllist Sterne, und dann nachdem ich die Definition abgeschlossen ist, 93 00:05:24,690 --> 00:05:27,220 Jetzt kann ich diese Art ein sll Knoten nennen. 94 00:05:27,220 --> 00:05:30,520 >> Also das ist, warum Sie sehen, es gibt hier einen temporären Namen, 95 00:05:30,520 --> 00:05:31,879 sondern eine dauerhafte Namen hier. 96 00:05:31,879 --> 00:05:33,920 Manchmal werden Sie vielleicht sehen, Definitionen der Struktur, 97 00:05:33,920 --> 00:05:36,570 zum Beispiel, die nicht selbst verweis, dass 98 00:05:36,570 --> 00:05:39,390 keine Spezifizierer Namen hier. 99 00:05:39,390 --> 00:05:43,040 Es würde einfach sagen, typedef struct, öffnen geschweifte Klammer und dann definieren. 100 00:05:43,040 --> 00:05:45,620 Aber wenn Sie struct ist selbst referentielle, als dieses ist, 101 00:05:45,620 --> 00:05:49,010 Sie brauchen, um ein angeben Namen temporärer Art. 102 00:05:49,010 --> 00:05:51,310 Aber letztlich jetzt dass wir das getan, 103 00:05:51,310 --> 00:05:53,620 wir können einfach zu beziehen diese Knoten, diese Einheiten, 104 00:05:53,620 --> 00:05:57,900 wie sll Knoten für Zwecke der Rest dieses Video. 105 00:05:57,900 --> 00:06:00,900 >> Na gut, so dass wir wissen, wie man erstellen Sie eine verknüpfte Liste Knoten. 106 00:06:00,900 --> 00:06:03,240 Wir wissen, wie zu definieren, eine verbundene Liste Knoten. 107 00:06:03,240 --> 00:06:06,670 Nun, wenn wir gehen, um zu starten mit ihnen, um Informationen zu sammeln, 108 00:06:06,670 --> 00:06:10,360 es gibt ein paar Operationen wir müssen verstehen, und die Arbeit mit. 109 00:06:10,360 --> 00:06:12,860 Wir müssen wissen, wie das Erstellen eine verknüpfte Liste aus der Luft gegriffen. 110 00:06:12,860 --> 00:06:14,901 Wenn es keine Liste bereits, wir wollen zu starten. 111 00:06:14,901 --> 00:06:16,960 Also müssen wir zu können , eine verknüpfte Liste zu erstellen, 112 00:06:16,960 --> 00:06:19,130 wir müssen wahrscheinlich zu suchen durch die Link-Liste 113 00:06:19,130 --> 00:06:21,830 um ein Element wir finden. 114 00:06:21,830 --> 00:06:24,430 Wir müssen in der Lage, einzufügen neue Dinge in die Liste, 115 00:06:24,430 --> 00:06:25,930 wir wollen, dass unsere Liste, um zu wachsen. 116 00:06:25,930 --> 00:06:28,638 Und in ähnlicher Weise zu können wollen wir die Dinge aus unserer Liste zu löschen, 117 00:06:28,638 --> 00:06:30,250 wir wollen, dass unsere Liste, um zu schrumpfen. 118 00:06:30,250 --> 00:06:32,160 Und am Ende der Programme, insbesondere 119 00:06:32,160 --> 00:06:34,550 Wenn Sie sich erinnern, dass wir die dynamische Zuweisung von Speicher 120 00:06:34,550 --> 00:06:38,337 diese Listen in der Regel zu bauen, wir alle, dass Speicher frei möchten 121 00:06:38,337 --> 00:06:39,670 wenn wir fertig sind mit ihm arbeiten. 122 00:06:39,670 --> 00:06:44,627 Und so müssen wir in der Lage, einen zu löschen gesamten verknüpften Liste in einem nicht Schlag. 123 00:06:44,627 --> 00:06:46,460 Lassen Sie uns also durchlaufen einige dieser Operationen 124 00:06:46,460 --> 00:06:51,192 und wie wir sie sichtbar zu machen, Gespräche in Pseudocode spezifisch. 125 00:06:51,192 --> 00:06:53,150 So, um eine erstellen möchten wir verknüpften Liste, so dass wir vielleicht 126 00:06:53,150 --> 00:06:56,480 möchte eine Funktion zu definieren Mit diesem Prototyp. 127 00:06:56,480 --> 00:07:01,690 sll Knoten Sterne, zu erstellen, und ich bin vorbei in einem Argument, einige beliebige Daten 128 00:07:01,690 --> 00:07:05,530 erneut eingeben, der einer beliebigen Datentyp. 129 00:07:05,530 --> 00:07:10,482 Aber ich bin returning-- diese Funktion sollten kehrt zu mir einen Zeiger auf eine einzeln 130 00:07:10,482 --> 00:07:11,190 verknüpften Liste Knoten. 131 00:07:11,190 --> 00:07:14,050 Auch hier versuchen wir, zu erstellen eine verknüpfte Liste aus der Luft gegriffen, 132 00:07:14,050 --> 00:07:17,900 so brauche ich einen Zeiger auf dass die Liste, wenn ich fertig bin. 133 00:07:17,900 --> 00:07:19,420 >> Also, was sind die Schritte hier beteiligt? 134 00:07:19,420 --> 00:07:20,960 Nun, ich bin erste, was zu tun ist, dynamisch 135 00:07:20,960 --> 00:07:22,550 Speicherplatz zuweisen für einen neuen Knoten. 136 00:07:22,550 --> 00:07:26,689 Auch hier schaffen wir es aus dem Nichts Luft, so müssen wir malloc Platz dafür. 137 00:07:26,689 --> 00:07:28,480 Und natürlich sofort nachdem wir malloc, 138 00:07:28,480 --> 00:07:31,692 wir prüfen immer, um sicherzustellen, dass unsere pointer-- wir nicht wieder null. 139 00:07:31,692 --> 00:07:33,650 Denn wenn wir versuchen, Ehrerbietung einen Null-Zeiger, 140 00:07:33,650 --> 00:07:36,190 wir werden leiden ein segfault und wir wollen das nicht. 141 00:07:36,190 --> 00:07:39,510 >> Dann, im Bereich füllen möchten wir, wir den Wert Feld initialisiert werden soll 142 00:07:39,510 --> 00:07:41,690 und initialisieren Sie das nächste Feld. 143 00:07:41,690 --> 00:07:45,450 Und dann zu-- schließlich als das wollen wir Funktionsprototyp indicates-- wir wollen, 144 00:07:45,450 --> 00:07:49,940 einen Zeiger auf ein sll Knoten zurückzukehren. 145 00:07:49,940 --> 00:07:51,710 Also, was machen diese sehen aus wie optisch? 146 00:07:51,710 --> 00:07:55,230 Nun, zunächst einmal, wir werden dynamisch Speicherplatz zuweisen für eine neue sll Knoten, 147 00:07:55,230 --> 00:07:58,320 so dass wir malloc-- das ist, eine visuelle Darstellung 148 00:07:58,320 --> 00:08:00,020 des Knotens wir gerade erstellt. 149 00:08:00,020 --> 00:08:02,757 Und wir überprüfen, ob es ist in diesem Fall nicht null--, 150 00:08:02,757 --> 00:08:04,840 das Bild nicht hätte up gezeigt, wenn es null, 151 00:08:04,840 --> 00:08:07,298 wir würden über genügend Arbeitsspeicher ausgeführt haben, so sind wir gut, dorthin zu gehen. 152 00:08:07,298 --> 00:08:10,200 So, jetzt sind wir zu dem Schritt C, initialisieren Sie den Knoten Wertefeld. 153 00:08:10,200 --> 00:08:12,280 Nun, auf der Grundlage dieser Funktion aufrufen Ich verwende hier, 154 00:08:12,280 --> 00:08:16,700 sieht aus wie ich in 6 übergeben, so werde ich 6 im Wertefeld. 155 00:08:16,700 --> 00:08:18,865 Nun, initialisieren Sie das nächste Feld. 156 00:08:18,865 --> 00:08:21,640 Nun, was soll ich nur tun gibt, gibt es nichts weiter, rechts, 157 00:08:21,640 --> 00:08:23,600 Das ist das einzige, was in der Liste. 158 00:08:23,600 --> 00:08:27,206 Also, was ist das nächste, was in der Liste? 159 00:08:27,206 --> 00:08:29,660 >> Es sollte auf nichts, richtig. 160 00:08:29,660 --> 00:08:33,600 Es gibt nichts anderes gibt, so was ist das Konzept kennen wir, das ist nothing-- 161 00:08:33,600 --> 00:08:35,638 Zeiger auf nichts? 162 00:08:35,638 --> 00:08:37,929 Es sollte vielleicht wir wollen, einen Null-Zeiger dort setzen, 163 00:08:37,929 --> 00:08:40,178 und ich werde die Null stellen Zeiger als nur ein rotes Feld, 164 00:08:40,178 --> 00:08:41,559 wir können nicht weiter gehen. 165 00:08:41,559 --> 00:08:44,430 Wie wir später ein wenig zu sehen, wir schließlich Ketten 166 00:08:44,430 --> 00:08:46,330 Pfeile Verbindungs diese Knoten zusammen, 167 00:08:46,330 --> 00:08:48,480 aber wenn Sie drücken Sie die rotes Feld, das ist null, 168 00:08:48,480 --> 00:08:51,150 wir können nicht weiter gehen, das ist das Ende der Liste. 169 00:08:51,150 --> 00:08:53,960 >> Und schließlich wollen wir nur liefern einen Zeiger auf diesen Knoten. 170 00:08:53,960 --> 00:08:56,160 Also werden wir es nennen neue, und neue Rück 171 00:08:56,160 --> 00:08:59,370 so kann es verwendet werden in was auch immer-Funktion geschaffen hat. 172 00:08:59,370 --> 00:09:03,100 Es gibt also wir gehen, haben wir ein einfach erstellt verknüpften Liste Knoten aus der Luft gegriffen, 173 00:09:03,100 --> 00:09:05,920 und jetzt haben wir eine Liste wir arbeiten können. 174 00:09:05,920 --> 00:09:08,260 >> Nun lassen Sie uns sagen, dass wir bereits haben eine große Kette, 175 00:09:08,260 --> 00:09:09,800 und wir wollen etwas in ihm zu finden. 176 00:09:09,800 --> 00:09:12,716 Und wir wollen, eine Funktion, die gehen true oder false zurück, je 177 00:09:12,716 --> 00:09:15,840 davon ab, ob ein Wert in der Liste vorhanden ist. 178 00:09:15,840 --> 00:09:18,160 Ein Funktionsprototyp oder Erklärung für die Funktion, 179 00:09:18,160 --> 00:09:23,320 aussehen könnte this-- bool zu finden, und dann wollen wir in zwei Argumente übergeben. 180 00:09:23,320 --> 00:09:26,996 >> Das erste ist ein Zeiger auf die erste Element der verketteten Liste. 181 00:09:26,996 --> 00:09:29,620 Das ist eigentlich etwas, das Sie wollen immer, um zu verfolgen, 182 00:09:29,620 --> 00:09:33,110 und tatsächlich könnte etwas sein, dass Sie sogar in einer globalen Variablen gesetzt. 183 00:09:33,110 --> 00:09:35,360 Sobald Sie eine Liste zu erstellen, Sie immer, immer 184 00:09:35,360 --> 00:09:38,990 wollen den Überblick über die sehr zu halten erste Element der Liste. 185 00:09:38,990 --> 00:09:43,690 So können Sie auf alle anderen beziehen Elemente nur durch Anschluss an die Kette, 186 00:09:43,690 --> 00:09:47,300 ohne Zeiger zu halten intakt zu jedem einzelnen Element. 187 00:09:47,300 --> 00:09:50,920 Sie müssen nur den Überblick über die ersten zu halten eine, wenn sie alle miteinander verkettet. 188 00:09:50,920 --> 00:09:52,460 >> Und dann die zweite Sache, wir sind wieder vorbei in 189 00:09:52,460 --> 00:09:54,376 beliebig some-- unabhängig von Datentyp sind wir 190 00:09:54,376 --> 00:09:59,640 Suche nach gibt es im Inneren des hoffentlich einen der Knoten in der Liste. 191 00:09:59,640 --> 00:10:00,980 Also, was sind die Schritte? 192 00:10:00,980 --> 00:10:04,250 Nun, das erste, was wir tun, ist schaffen wir eine Querzeiger 193 00:10:04,250 --> 00:10:06,015 zeigte auf den Listen Kopf. 194 00:10:06,015 --> 00:10:08,890 Nun, warum wir das tun, haben wir bereits einen Zeiger an der Listen Kopf, 195 00:10:08,890 --> 00:10:10,974 warum nicht wir bewegen nur, dass man in der Umgebung? 196 00:10:10,974 --> 00:10:13,140 Nun, wie ich gerade gesagt habe, es ist wirklich wichtig für uns, 197 00:10:13,140 --> 00:10:17,580 um immer den Überblick über die zu halten allererste Element in der Liste. 198 00:10:17,580 --> 00:10:21,270 Und so ist es tatsächlich besser ein Duplikat daß schaffen, 199 00:10:21,270 --> 00:10:25,350 und verwenden, die in der Umgebung von nie zu bewegen, so dass wir versehentlich weg, oder wir immer 200 00:10:25,350 --> 00:10:30,430 einen Zeiger zu einem bestimmten Zeitpunkt, das ist direkt auf das erste Element der Liste. 201 00:10:30,430 --> 00:10:33,290 So ist es besser, einen zu erstellen zweite, die wir verwenden, um zu bewegen. 202 00:10:33,290 --> 00:10:35,877 >> Dann vergleichen wir nur, ob das Wertefeld an diesem Knoten 203 00:10:35,877 --> 00:10:38,960 ist das, was wir suchen, und wenn es nicht, wir haben nur an den nächsten Knoten zu verschieben. 204 00:10:38,960 --> 00:10:41,040 Und wir weiterhin tun, dass über und über und über, 205 00:10:41,040 --> 00:10:44,811 bis wir entweder zu finden das Element, oder wir treffen 206 00:10:44,811 --> 00:10:47,310 null-- wir das Ende erreicht auf der Liste und es ist nicht da. 207 00:10:47,310 --> 00:10:50,540 Dies sollte hoffentlich eine Glocke läuten Ihnen als nur lineare Suche, 208 00:10:50,540 --> 00:10:54,430 wir sind nur zu replizieren es in eine einfach verkettete Liste Struktur 209 00:10:54,430 --> 00:10:56,280 anstelle der Verwendung einer Anordnung, um dies zu tun. 210 00:10:56,280 --> 00:10:58,210 >> Also hier ist ein Beispiel dafür, eine einfach verkettete Liste. 211 00:10:58,210 --> 00:11:00,043 Dieser besteht aus fünf Knoten, und wir haben 212 00:11:00,043 --> 00:11:04,330 ein Zeiger auf den Kopf des Liste, die Liste aufgerufen wird. 213 00:11:04,330 --> 00:11:07,385 Das erste, was wir tun wollen, ist wieder, noch zu einer Durchquerung Zeiger. 214 00:11:07,385 --> 00:11:09,760 So haben wir jetzt zwei Zeiger dass auf die gleiche Sache. 215 00:11:09,760 --> 00:11:15,025 >> Jetzt bemerken auch hier habe ich nicht müssen keine Platz für trav malloc. 216 00:11:15,025 --> 00:11:18,970 Ich habe nicht gesagt trav gleich malloc etwas, bereits vorhanden ist, dass der Knoten, 217 00:11:18,970 --> 00:11:21,160 dass Platz im Speicher vorhanden ist. 218 00:11:21,160 --> 00:11:24,290 Also alles, was ich eigentlich tun ist die Schaffung einer anderen Zeiger darauf. 219 00:11:24,290 --> 00:11:28,210 Ich bin nicht mallocing eine zusätzliche Raum, haben gerade zwei Zeiger 220 00:11:28,210 --> 00:11:31,370 , die auf die gleiche Sache. 221 00:11:31,370 --> 00:11:33,710 >> So ist 2, was ich suche? 222 00:11:33,710 --> 00:11:37,220 Nun, nein, so dass anstelle Ich bin gehen, um zum nächsten zu bewegen. 223 00:11:37,220 --> 00:11:41,740 Also im Grunde würde ich sagen, trav gleich trav nächsten. 224 00:11:41,740 --> 00:11:43,630 Ist 3, was ich suche, nein. 225 00:11:43,630 --> 00:11:45,780 Also habe ich weiter gehen durch, bis schließlich 226 00:11:45,780 --> 00:11:48,690 bekommen bis 6 das ist, was ich suche für die auf der Funktionsaufruf auf der Basis 227 00:11:48,690 --> 00:11:51,600 Ich habe an der Spitze dort, und so bin ich fertig. 228 00:11:51,600 --> 00:11:54,150 >> Nun, was ist, wenn das Element Ich bin suche, ist nicht in der Liste, 229 00:11:54,150 --> 00:11:55,510 ist es immer noch zur Arbeit zu gehen? 230 00:11:55,510 --> 00:11:57,120 Nun, feststellen, dass die Liste Hier ist auf subtile Weise anders, 231 00:11:57,120 --> 00:11:59,410 und das ist eine andere Sache, die ist wichtig verkettete Listen, 232 00:11:59,410 --> 00:12:01,780 Sie müssen nicht zu erhalten sie in einer bestimmten Reihenfolge. 233 00:12:01,780 --> 00:12:05,390 Sie können, wenn Sie wollen, aber Sie vielleicht schon bemerkt haben 234 00:12:05,390 --> 00:12:09,310 dass wir nicht die Verfolgung von welche Nummer Element stehen wir. 235 00:12:09,310 --> 00:12:13,150 >> Und das ist eine Art von Handel, die wir haben mit verknüpften Liste Verse Arrays, 236 00:12:13,150 --> 00:12:15,300 wird wir nicht Direktzugriff mehr. 237 00:12:15,300 --> 00:12:18,150 Wir können nicht einfach sagen, ich will an der 0-ten Element zu gehen, 238 00:12:18,150 --> 00:12:21,410 oder das 6. Element meiner Array, die ich in einem Array zu tun. 239 00:12:21,410 --> 00:12:25,080 Ich kann nicht sagen, ich will, um unterwegs 0. Element oder das 6. Element, 240 00:12:25,080 --> 00:12:30,360 oder das 25. Element meiner verknüpften Liste, es gibt keinen Index mit ihnen verbunden sind. 241 00:12:30,360 --> 00:12:33,660 Und so ist es nicht wirklich wichtig, wenn wir unsere Liste, um zu bewahren. 242 00:12:33,660 --> 00:12:36,080 Wenn Sie Sie wollen sicherlich kann, aber es gibt 243 00:12:36,080 --> 00:12:38,567 keinen Grund, warum sie brauchen in beliebiger Reihenfolge erhalten werden. 244 00:12:38,567 --> 00:12:40,400 Also noch einmal, lassen Sie uns versuchen und finden 6 in dieser Ansicht. 245 00:12:40,400 --> 00:12:43,200 Nun, fangen wir an die Anfang, wir nicht finden, 6, 246 00:12:43,200 --> 00:12:47,690 und dann weiter wir nicht finden, 6, bis wir schließlich zu uns kommen. 247 00:12:47,690 --> 00:12:52,790 So jetzt trav Punkte an den Knoten mit 8 und sechs ist nicht drin. 248 00:12:52,790 --> 00:12:55,250 >> Der nächste Schritt wäre, um zum nächsten Zeiger zu gehen, 249 00:12:55,250 --> 00:12:57,440 so sagen trav gleich trav nächsten. 250 00:12:57,440 --> 00:13:00,750 Nun, trav nächsten, angezeigt durch die rote Box gibt, ist null. 251 00:13:00,750 --> 00:13:03,020 So gibt es nirgendwo anders zu gehen, und so an dieser Stelle 252 00:13:03,020 --> 00:13:06,120 können wir feststellen, dass wir erreicht haben das Ende der verketteten Liste, 253 00:13:06,120 --> 00:13:07,190 und 6 ist nicht drin. 254 00:13:07,190 --> 00:13:10,980 Und es zurückgegeben werden würde falsch in diesem Fall. 255 00:13:10,980 --> 00:13:14,540 >> OK, wie können wir setzen Sie eine neue Knoten in der verknüpften Liste? 256 00:13:14,540 --> 00:13:17,310 So haben wir in der Lage, zu erstellen eine verknüpfte Liste aus dem Nichts, 257 00:13:17,310 --> 00:13:19,370 aber wir wollen wahrscheinlich Aufbau einer Kette und nicht 258 00:13:19,370 --> 00:13:22,620 erstellen eine Reihe von unterschiedlichen Listen. 259 00:13:22,620 --> 00:13:25,700 Wir wollen eine Liste haben, dass hat eine Reihe von Knoten drin, 260 00:13:25,700 --> 00:13:28,040 nicht ein Haufen von Listen mit einem einzigen Knoten. 261 00:13:28,040 --> 00:13:31,260 So können wir nicht nur halten mit der CREATE Funktion zuvor definierten wir, jetzt sind wir 262 00:13:31,260 --> 00:13:33,860 wollen in ein einfügen Liste, die bereits vorhanden ist. 263 00:13:33,860 --> 00:13:36,499 >> Also hier, wir gehen in zwei Argumente übergeben, 264 00:13:36,499 --> 00:13:39,290 der Zeiger auf den Kopf, dass verknüpften Liste, die wir hinzufügen möchten. 265 00:13:39,290 --> 00:13:40,910 Wieder, das ist, warum es so wichtig, dass wir immer 266 00:13:40,910 --> 00:13:43,400 im Auge behalten, denn es ist die einzige Art, wie wir wirklich 267 00:13:43,400 --> 00:13:46,690 haben, um sich auf die ganze Liste nur durch einen Zeiger auf das erste Element. 268 00:13:46,690 --> 00:13:49,360 So dass wir in eine weitergeben wollen Zeiger auf das erste Element, 269 00:13:49,360 --> 00:13:52,226 und was wir Wert möchte in die Liste aufzunehmen. 270 00:13:52,226 --> 00:13:54,600 Und schließlich diese Funktion wird einen Zeiger zurück 271 00:13:54,600 --> 00:13:57,980 auf den neuen Chef einer verketteten Liste. 272 00:13:57,980 --> 00:13:59,700 >> Was sind die Schritte hier beteiligt? 273 00:13:59,700 --> 00:14:02,249 Nun, genau wie bei zu erstellen, wir brauchen, um dynamisch zuzuweisen 274 00:14:02,249 --> 00:14:05,540 Platz für einen neuen Knoten, und überprüfen Sie, dass wir nicht über genügend Arbeitsspeicher ausgeführt, wieder, 275 00:14:05,540 --> 00:14:07,150 weil wir unter Verwendung von malloc. 276 00:14:07,150 --> 00:14:09,080 Dann, um zu bevölkern wollen wir und fügen Sie den Knoten, 277 00:14:09,080 --> 00:14:12,730 so setzen die Zahl, was auch immer val ist, in den Knoten. 278 00:14:12,730 --> 00:14:17,310 Wir wollen den Knoten einfügen der Anfang der verknüpften Liste. 279 00:14:17,310 --> 00:14:19,619 >> Es gibt einen Grund, dass ich dies tun wollen, und es 280 00:14:19,619 --> 00:14:21,910 vielleicht lohnt sich ein zweiter sein um das Video hier zu unterbrechen, 281 00:14:21,910 --> 00:14:25,860 und darüber, warum ich zu wollen, denken Einsatz am Anfang einer verknüpften 282 00:14:25,860 --> 00:14:26,589 Liste. 283 00:14:26,589 --> 00:14:28,630 Auch erwähnte ich vorher , dass es nicht wirklich 284 00:14:28,630 --> 00:14:33,020 egal, ob wir es zu bewahren in jeder um, so vielleicht ist das ein Anhaltspunkt. 285 00:14:33,020 --> 00:14:36,040 Und man sah, was geschehen würde, wenn wir wollte zu-- oder von nur einer Sekunde 286 00:14:36,040 --> 00:14:37,360 vor, wenn wir wollten durch Suche können Sie 287 00:14:37,360 --> 00:14:39,235 konnte, was sehen könnte passieren, wenn wir versuchten, 288 00:14:39,235 --> 00:14:41,330 am Ende der Liste eingefügt. 289 00:14:41,330 --> 00:14:44,750 Denn wir haben nicht ein Zeiger auf das Ende der Liste. 290 00:14:44,750 --> 00:14:47,490 >> Also der Grund, dass ich würde zu Beginn einzufügen, 291 00:14:47,490 --> 00:14:49,380 ist, weil ich es sofort tun. 292 00:14:49,380 --> 00:14:52,730 Ich habe einen Zeiger am Anfang, und Wir werden dies in einer visuellen in einem zweiten zu sehen. 293 00:14:52,730 --> 00:14:55,605 Aber wenn ich am Ende einfügen, Ich muss am Anfang beginnen, 294 00:14:55,605 --> 00:14:58,760 queren den ganzen Weg zu der Ende, und dann tack sie auf. 295 00:14:58,760 --> 00:15:01,420 So würde das bedeuten, dass Einsetzen am Ende der Liste 296 00:15:01,420 --> 00:15:04,140 wäre ein o n geworden Betrieb, geht zurück 297 00:15:04,140 --> 00:15:06,720 unsere Diskussion Rechenkomplexität. 298 00:15:06,720 --> 00:15:10,140 Es wäre ein o n Betrieb, in dem sich die Liste wurde größer und größer, 299 00:15:10,140 --> 00:15:13,310 und größer, es wird mehr werden und schwieriger, etwas zu heften 300 00:15:13,310 --> 00:15:14,661 am Ende. 301 00:15:14,661 --> 00:15:17,410 Aber es ist immer wirklich einfach, tack etwas am Anfang, 302 00:15:17,410 --> 00:15:19,060 du bist immer am Anfang. 303 00:15:19,060 --> 00:15:21,620 >> Und wir werden sehen, noch einmal eine visuelle dafür. 304 00:15:21,620 --> 00:15:24,100 Und dann, sobald wir fertig sind, einmal wir haben den neuen Knoten eingefügt, 305 00:15:24,100 --> 00:15:26,880 wir unsere Zeiger zurückgeben möchten der neue Leiter einer verknüpften Liste, die 306 00:15:26,880 --> 00:15:29,213 da wir in der Einführungs beginnen, tatsächlich sein wird 307 00:15:29,213 --> 00:15:31,060 ein Zeiger zu dem Knoten wir gerade erstellt. 308 00:15:31,060 --> 00:15:33,280 Lassen Sie uns dies zu visualisieren, weil ich denke, es wird Ihnen helfen. 309 00:15:33,280 --> 00:15:36,661 >> Also hier ist unsere Liste, es besteht aus vier Elemente, ein Knoten, der 15, 310 00:15:36,661 --> 00:15:38,410 was auf einem Knoten enthält 9, die 311 00:15:38,410 --> 00:15:41,370 verweist auf einen Knoten mit 13 der an einem Knotenpunkt der Punkte enthält 312 00:15:41,370 --> 00:15:44,840 10, die den null hat Zeiger als nächstes Zeiger 313 00:15:44,840 --> 00:15:47,010 damit ist das Ende der Liste. 314 00:15:47,010 --> 00:15:50,200 So ein einfügen wollen wir neuen Knoten mit dem Wert 12 315 00:15:50,200 --> 00:15:52,720 am Anfang dieses Liste, was sollen wir tun? 316 00:15:52,720 --> 00:15:58,770 Nun, zunächst malloc wir Raum für die Knoten, und dann haben wir 12 drin. 317 00:15:58,770 --> 00:16:02,211 >> So, jetzt haben wir erreicht haben, ein Entscheidungspunkt, nicht wahr? 318 00:16:02,211 --> 00:16:03,960 Wir haben ein paar Hinweise, dass wir 319 00:16:03,960 --> 00:16:06,770 zu bewegen, die einen sollten wir zuerst zu bewegen? 320 00:16:06,770 --> 00:16:09,250 Sollten wir 12 Punkt der neue Leiter des list-- 321 00:16:09,250 --> 00:16:13,020 oder entschuldigen Sie, sollten wir 12 auf den alten Kopf der Liste? 322 00:16:13,020 --> 00:16:15,319 Oder sollten wir sagen, dass die Liste beginnt nun bei 12. 323 00:16:15,319 --> 00:16:17,110 Es gibt einen Unterschied gibt, und wir werden sehen 324 00:16:17,110 --> 00:16:19,870 was sowohl in einem zweiten Fall. 325 00:16:19,870 --> 00:16:23,350 >> Dies führt jedoch zu einer großes Thema für die Seitenleiste, 326 00:16:23,350 --> 00:16:26,280 die, dass einer der ist heikelsten Dinge mit verknüpften Listen 327 00:16:26,280 --> 00:16:30,980 wird der Zeiger zu arrangieren in der richtigen Reihenfolge. 328 00:16:30,980 --> 00:16:34,520 Wenn Sie die Dinge in Ordnung zu bewegen, können Sie versehentlich am Ende 329 00:16:34,520 --> 00:16:36,050 verwaisen den Rest der Liste. 330 00:16:36,050 --> 00:16:37,300 Und hier ist ein Beispiel dafür. 331 00:16:37,300 --> 00:16:40,540 Lassen Sie uns also mit dem Gedanken gehen von-- Nun, wir haben gerade 12. 332 00:16:40,540 --> 00:16:43,180 Wir wissen, dass 12 sein wird, der neue Kopf der Liste, 333 00:16:43,180 --> 00:16:47,660 und so, warum wir nicht einfach bewegen Die folgende Liste enthält Zeiger auf es verweisen. 334 00:16:47,660 --> 00:16:49,070 >> OK, das ist gut. 335 00:16:49,070 --> 00:16:51,560 So, jetzt wo endet 12 nächste Punkt? 336 00:16:51,560 --> 00:16:54,580 Ich meine, wir sehen können visuell dass es bis 15 zeigen, 337 00:16:54,580 --> 00:16:57,250 als Menschen, es ist zu uns wirklich auf der Hand. 338 00:16:57,250 --> 00:17:00,300 Wie funktioniert der Computer wissen? 339 00:17:00,300 --> 00:17:02,720 Wir haben nichts zeigt auf 15 mehr, oder? 340 00:17:02,720 --> 00:17:05,869 >> Wir haben keine Möglichkeit, bis 15 beziehen sich verloren. 341 00:17:05,869 --> 00:17:11,460 Wir können nicht sagen neue Pfeil neben equals etwas, da ist nichts. 342 00:17:11,460 --> 00:17:13,510 Tatsächlich haben wir verwaiste habe der Rest der Liste 343 00:17:13,510 --> 00:17:16,465 Auf diese Weise haben wir Versehen Sie die Kette gebrochen. 344 00:17:16,465 --> 00:17:18,089 Und wir wollen sicher nicht, das zu tun. 345 00:17:18,089 --> 00:17:20,000 >> Also lassen Sie uns gehen Sie zurück und noch einmal versuchen. 346 00:17:20,000 --> 00:17:24,060 Vielleicht ist das Richtige zu tun, ist es, 12 der nächste Zeiger gesetzt 347 00:17:24,060 --> 00:17:28,290 zur alten Kopf der Liste zuerst dann können wir die Liste über zu bewegen. 348 00:17:28,290 --> 00:17:30,420 Und in der Tat ist, dass das richtigen Reihenfolge, dass wir 349 00:17:30,420 --> 00:17:32,836 folgen müssen, wenn wir Arbeiten mit einfach verkettete Liste. 350 00:17:32,836 --> 00:17:36,460 Wir wollen immer die verbinden neues Element in der Liste, 351 00:17:36,460 --> 00:17:41,010 bevor wir diese Art von wichtiger Schritt des Änderns 352 00:17:41,010 --> 00:17:43,360 wo der Kopf der verketteten Liste ist. 353 00:17:43,360 --> 00:17:46,740 Wieder ist, dass eine solche grundlegende Sache, wir wollen nicht zu verfolgen, es zu verlieren. 354 00:17:46,740 --> 00:17:49,310 >> Also, um sicherzustellen, dass wir wollen alles miteinander verkettet, 355 00:17:49,310 --> 00:17:52,040 bevor wir diesen Zeiger. 356 00:17:52,040 --> 00:17:55,300 Und so wäre dies die richtige Reihenfolge zu sein, die an der Liste Verbinden 12, 357 00:17:55,300 --> 00:17:57,630 dann sagen, dass die Liste beginnt eine 12. 358 00:17:57,630 --> 00:18:00,860 Wenn wir die Liste beginnt bei 12 und dann versucht, in die Liste zu verbinden 12, 359 00:18:00,860 --> 00:18:02,193 Wir haben bereits gesehen, was passiert. 360 00:18:02,193 --> 00:18:04,920 Wir verlieren die Liste aus Versehen. 361 00:18:04,920 --> 00:18:06,740 >> OK, so dass eine weitere Sache, darüber zu sprechen. 362 00:18:06,740 --> 00:18:09,750 Was ist, wenn wir wollen, um loszuwerden, eine ganze verbundene Liste auf einmal? 363 00:18:09,750 --> 00:18:11,750 Auch hier sind wir mallocing all das Platz, und so haben wir 364 00:18:11,750 --> 00:18:13,351 brauchen, um es zu befreien, wenn wir fertig sind. 365 00:18:13,351 --> 00:18:15,350 So, jetzt löschen möchten wir die gesamte verknüpfte Liste. 366 00:18:15,350 --> 00:18:16,850 Nun, was wollen wir tun? 367 00:18:16,850 --> 00:18:20,460 >> Wenn wir die Null-Zeiger zu erreichen, haben wir aufhören, sonst, einfach löschen 368 00:18:20,460 --> 00:18:23,420 der Rest der Liste und dann befreie mich. 369 00:18:23,420 --> 00:18:28,890 Löschen Sie den Rest der Liste, und dann befreien den aktuellen Knoten. 370 00:18:28,890 --> 00:18:32,850 Wie klingt das wie, Welche Technik haben wir sprachen 371 00:18:32,850 --> 00:18:35,440 über zuvor Klingt das wie? 372 00:18:35,440 --> 00:18:39,560 Alle löschen anderes, dann kommen zurück, und löschen Sie mich. 373 00:18:39,560 --> 00:18:42,380 >> Das ist die Rekursion, die wir gemacht haben die Problem ein wenig kleiner, 374 00:18:42,380 --> 00:18:46,910 wir sagen löschen jedermann anderes, dann können Sie mir zu löschen. 375 00:18:46,910 --> 00:18:50,940 Und weiter die Straße hinunter, dass der Knoten wird sagen, löschen Sie alle anderen. 376 00:18:50,940 --> 00:18:53,940 Aber irgendwann werden wir um das zu bekommen Punkt, an dem die Liste ist null, 377 00:18:53,940 --> 00:18:55,310 und das ist unser Basisszenario. 378 00:18:55,310 --> 00:18:57,010 >> Werfen wir also einen Blick auf diese, und wie dies funktionieren könnte. 379 00:18:57,010 --> 00:18:59,759 Also hier ist unsere Liste, ist es das gleiche Liste waren wir nur darüber zu reden, 380 00:18:59,759 --> 00:19:00,980 und es gibt die Schritte. 381 00:19:00,980 --> 00:19:04,200 Es gibt eine Menge von Text hier, aber hoffentlich die Visualisierung hilft. 382 00:19:04,200 --> 00:19:08,557 >> Also haben wir have-- und ich zog auch unsere Stapelrahmen illustration 383 00:19:08,557 --> 00:19:10,890 aus unserem Video auf Abruf-Stacks, und hoffentlich all dies 384 00:19:10,890 --> 00:19:13,260 zusammen wird Ihnen zeigen, was los ist. 385 00:19:13,260 --> 00:19:14,510 Also hier ist unsere Pseudocode. 386 00:19:14,510 --> 00:19:17,830 Wenn wir ein Null zu erreichen Zeiger zu stoppen, sonst, 387 00:19:17,830 --> 00:19:21,320 löschen Sie den Rest der Liste, dann kostenlos den aktuellen Knoten. 388 00:19:21,320 --> 00:19:25,700 So jetzt, list-- der Zeiger, die wir sind 389 00:19:25,700 --> 00:19:28,410 vorbei an den Punkten 12 zu zerstören. 390 00:19:28,410 --> 00:19:33,340 12 ist kein Null-Zeiger, so sind wir gehen, um den Rest der Liste zu löschen. 391 00:19:33,340 --> 00:19:35,450 >> Was ist das Löschen der Rest von uns beteiligt? 392 00:19:35,450 --> 00:19:37,950 Na ja, bedeutet dies, dass ein anrufen, um zu zerstören, zu sagen 393 00:19:37,950 --> 00:19:42,060 dass 15 ist der Beginn der Rest der Liste, die wir zerstören wollen. 394 00:19:42,060 --> 00:19:47,480 Und so wird der Anruf zu zerstören 12 ist eine Art zu halten. 395 00:19:47,480 --> 00:19:52,690 Es gibt eingefroren und warten auf die anrufen, um zu zerstören 15, um seine Arbeit zu beenden. 396 00:19:52,690 --> 00:19:56,280 >> Nun, 15 ist kein Null-Zeiger, und also wird es zu sagen, alles in Ordnung, 397 00:19:56,280 --> 00:19:58,450 gut, löschen Sie den Rest der Liste. 398 00:19:58,450 --> 00:20:00,760 Der Rest der Liste beginnt 9, und so werden wir nur 399 00:20:00,760 --> 00:20:04,514 warten Sie, bis Sie alle zu löschen, dass stuff, dann kommen Sie und löschen Sie mich. 400 00:20:04,514 --> 00:20:06,680 Gut 9 geht zu sagen, na ja, Ich bin nicht eine Null-Zeiger, 401 00:20:06,680 --> 00:20:09,020 Der Rest der Liste von hier so zu löschen. 402 00:20:09,020 --> 00:20:11,805 Und so versuchen und zu zerstören 13. 403 00:20:11,805 --> 00:20:15,550 13, sagt, ich bin mir nicht Null-Zeiger, elbe ist, leitet sie den Schwarzen Peter zuschieben. 404 00:20:15,550 --> 00:20:17,930 10 nicht Null-Zeiger, 10 enthält eine Null-Zeiger, 405 00:20:17,930 --> 00:20:20,200 aber 10 nicht selbst ein NULL-Zeiger gerade jetzt, 406 00:20:20,200 --> 00:20:22,470 und so ist es passiert den Schwarzen Peter zu. 407 00:20:22,470 --> 00:20:25,560 >> Und jetzt gibt es Punkte aufzulisten, es wirklich möchte darauf zu some-- 408 00:20:25,560 --> 00:20:28,710 wenn ich mehr Platz in dem Bild, es wäre, um einige zufällige Platz zeigen 409 00:20:28,710 --> 00:20:29,960 dass wir nicht wissen, was es ist. 410 00:20:29,960 --> 00:20:34,680 Es ist der Null-Zeiger, obwohl die Liste ist buchstäblich nun eingestellt, es ist Werte null. 411 00:20:34,680 --> 00:20:36,820 Es ist nach rechts innerhalb dieses roten Feld. 412 00:20:36,820 --> 00:20:39,960 Wir erreichten einen Null-Zeiger, so können wir aufhören, und wir sind fertig. 413 00:20:39,960 --> 00:20:46,230 >> Und so, dass lila Rahmen ist now-- bei der Anfang der stack--, die der aktive Frame ist, 414 00:20:46,230 --> 00:20:47,017 aber es geht. 415 00:20:47,017 --> 00:20:48,600 Wenn wir eine Null-Zeiger erreicht, Halt. 416 00:20:48,600 --> 00:20:51,290 Wir haben nichts zu tun, haben wir kann nicht frei einen Null-Zeiger, 417 00:20:51,290 --> 00:20:55,070 wir haben nicht jede malloc Raum, und so sind wir fertig. 418 00:20:55,070 --> 00:20:57,590 So dass Funktionsrahmen zerstört wird, und wir 419 00:20:57,590 --> 00:21:00,930 resume-- wir bauen, wo wir aufge mit der nächsthöheren ein, die 420 00:21:00,930 --> 00:21:02,807 ist dieser dunkelblauen Rahmen hier. 421 00:21:02,807 --> 00:21:04,390 So holen wir genau da, wo wir aufgehört haben. 422 00:21:04,390 --> 00:21:06,598 Wir löschen den Rest des Liste bereits, so jetzt sind wir 423 00:21:06,598 --> 00:21:08,000 gehen, um die aktuellen Knoten zu befreien. 424 00:21:08,000 --> 00:21:12,920 So, jetzt können wir diese Knoten zu befreien, und nun wir haben das Ende der Funktion erreicht. 425 00:21:12,920 --> 00:21:16,810 Und so, dass Funktionsrahmen zerstört wird, und wir holen Sie am hellblaue. 426 00:21:16,810 --> 00:21:20,650 >> So ist es says-- Ich habe bereits done-- Löschen der Rest der Liste, so 427 00:21:20,650 --> 00:21:23,140 befreien den aktuellen Knoten. 428 00:21:23,140 --> 00:21:26,520 Und nun die gelben Rahmen ist wieder an der Spitze des Stapels. 429 00:21:26,520 --> 00:21:29,655 Und so, wie Sie sehen, jetzt sind wir Zerstören der Liste von rechts nach links. 430 00:21:29,655 --> 00:21:33,710 431 00:21:33,710 --> 00:21:37,280 >> Was wäre geschehen, wenn auch, wenn wir die Dinge in die falsche Richtung getan? 432 00:21:37,280 --> 00:21:39,410 Genau wie als wir versuchten, um ein Element hinzuzufügen. 433 00:21:39,410 --> 00:21:41,909 Wenn wir vermasselt die Kette, wenn wir nicht schließen Sie die Zeiger 434 00:21:41,909 --> 00:21:44,690 in der richtigen Reihenfolge, wenn wir nur befreit das erste Element, 435 00:21:44,690 --> 00:21:47,420 wenn wir nur befreit die Kopf der Liste, jetzt sind wir 436 00:21:47,420 --> 00:21:49,642 haben keine Möglichkeit, zu beziehen der Rest der Liste. 437 00:21:49,642 --> 00:21:51,350 Und so hätten wir verwaiste alles, 438 00:21:51,350 --> 00:21:53,880 wir hätten was ist rief ein Speicherverlust. 439 00:21:53,880 --> 00:21:56,800 Wenn Sie aus unserem Video erinnern auf dynamische Speicherzuweisung, 440 00:21:56,800 --> 00:21:58,650 das ist nicht sehr gute Sache. 441 00:21:58,650 --> 00:22:00,810 >> So, wie ich sagte, es sind mehrere Operationen 442 00:22:00,810 --> 00:22:04,010 dass wir verwenden, um zu arbeiten mit Liste effektiv verknüpft. 443 00:22:04,010 --> 00:22:08,430 Und Sie haben vielleicht bemerkt, ich eines weggelassen, Löschen eines einzelnen Elements aus einer verknüpften 444 00:22:08,430 --> 00:22:09,064 Liste. 445 00:22:09,064 --> 00:22:10,980 Der Grund, warum ich das getan habe ist es eigentlich ganz 446 00:22:10,980 --> 00:22:14,360 schwierig, wie Sie denken, zu löschen ein einzelnes Element aus einem einzeln 447 00:22:14,360 --> 00:22:15,600 verknüpften Liste. 448 00:22:15,600 --> 00:22:19,950 Wir müssen in der Lage zu überspringen sein etwas in der Liste, die 449 00:22:19,950 --> 00:22:22,975 bedeutet, dass wir auf eine point-- wir bekommen wollen diese node-- löschen 450 00:22:22,975 --> 00:22:25,350 aber um es so zu machen wir nicht verlieren alle Informationen, 451 00:22:25,350 --> 00:22:30,530 wir brauchen, um diese zu verbinden Knoten über hier, hier. 452 00:22:30,530 --> 00:22:33,390 >> So wohl habe ich das falsch in optischer Hinsicht. 453 00:22:33,390 --> 00:22:36,830 So dass wir am Anfang sind unsere Liste, sind wir durch fortgefahren wird, 454 00:22:36,830 --> 00:22:40,510 Wir wollen diesen Knoten zu löschen. 455 00:22:40,510 --> 00:22:43,440 Wenn wir einfach löschen, wir haben die Kette gebrochen. 456 00:22:43,440 --> 00:22:45,950 Dieser Knoten hier bezieht sich auf alles andere, 457 00:22:45,950 --> 00:22:48,260 sie enthält die Kette von hier an heraus. 458 00:22:48,260 --> 00:22:51,190 >> Also, was wir tatsächlich tun müssen, nachdem wir zu diesem Punkt, 459 00:22:51,190 --> 00:22:56,670 ist, müssen wir einen Schritt zurück, und verbinden Sie diesen Knoten über diesem Knoten, 460 00:22:56,670 --> 00:22:58,590 so können wir löschen der eine in der Mitte. 461 00:22:58,590 --> 00:23:02,120 Aber einfach verkettete Listen nicht geben uns einen Weg, um rückwärts zu gehen. 462 00:23:02,120 --> 00:23:05,160 Also müssen wir entweder zu halten zwei Zeiger, und verschieben Sie sie 463 00:23:05,160 --> 00:23:09,527 Art von off Schritt hinter andere, wie wir gehen, oder sich zu einem Punkt 464 00:23:09,527 --> 00:23:11,110 und senden Sie dann einen anderen Zeiger durch. 465 00:23:11,110 --> 00:23:13,150 Und wie Sie es sehen können kann ein wenig chaotisch. 466 00:23:13,150 --> 00:23:15,360 Glücklicherweise haben wir Ein anderer Weg, zu beschließen, 467 00:23:15,360 --> 00:23:17,810 wenn wir über die doppelt verkettete Listen zu sprechen. 468 00:23:17,810 --> 00:23:20,720 >> Ich bin Doug Lloyd, ist dies CS50. 469 00:23:20,720 --> 00:23:22,298