1 00:00:07,260 --> 00:00:10,050 [Powered by Google Translate] Bei der Programmierung müssen wir oft Listen von Werten darstellen, 2 00:00:10,050 --> 00:00:12,840 wie die Namen der Schüler in einem Abschnitt 3 00:00:12,840 --> 00:00:15,100 oder deren Noten auf dem neuesten Quiz. 4 00:00:15,100 --> 00:00:17,430 >> In der Sprache C, erklärte Arrays verwendet werden können 5 00:00:17,430 --> 00:00:19,160 um Listen speichern. 6 00:00:19,160 --> 00:00:21,200 Es ist einfach, die Elemente einer Liste aufzuzählen 7 00:00:21,200 --> 00:00:23,390 gespeichert in einem Array, und wenn Sie den Zugriff auf 8 00:00:23,390 --> 00:00:25,050 oder ändern das i-te Listenelement 9 00:00:25,050 --> 00:00:27,570 für einige beliebiger Index I, 10 00:00:27,570 --> 00:00:29,910 Das kann in konstanter Zeit durchgeführt werden, 11 00:00:29,910 --> 00:00:31,660 aber Arrays haben auch Nachteile. 12 00:00:31,660 --> 00:00:33,850 >> Wenn wir ihnen erklären, wir müssen sagen, 13 00:00:33,850 --> 00:00:35,900 vorne wie groß sie sind, 14 00:00:35,900 --> 00:00:38,160 das heißt, wie viele Elemente sie speichern können 15 00:00:38,160 --> 00:00:40,780 und wie groß diese Elemente sind, die durch deren Art bestimmt. 16 00:00:40,780 --> 00:00:45,450 Zum Beispiel, int arr (10) 17 00:00:45,450 --> 00:00:48,220 können 10 Einträge speichern 18 00:00:48,220 --> 00:00:50,200 das sind die Größe eines int. 19 00:00:50,200 --> 00:00:52,590 >> Wir können nicht ändern eines Arrays der Größe nach Erklärung. 20 00:00:52,590 --> 00:00:55,290 Wir haben ein neues Array machen, wenn wir mehr Elemente speichern möchten. 21 00:00:55,290 --> 00:00:57,410 Der Grund dafür Einschränkung besteht darin, dass unsere 22 00:00:57,410 --> 00:00:59,040 Programm speichert das gesamte Array 23 00:00:59,040 --> 00:01:02,310 als zusammenhängender Block arbeiten. 24 00:01:02,310 --> 00:01:04,500 Sagen, das ist der Puffer, wo wir in unserem Array gespeichert. 25 00:01:04,500 --> 00:01:06,910 Es können auch andere Variablen 26 00:01:06,910 --> 00:01:08,310 befindet sich direkt neben dem Array 27 00:01:08,310 --> 00:01:10,060 im Speicher, so können wir nicht 28 00:01:10,060 --> 00:01:12,060 nur das Array größer. 29 00:01:12,060 --> 00:01:15,700 >> Manchmal möchten wir die Array-schnellen Datenzugriff Geschwindigkeit Handel 30 00:01:15,700 --> 00:01:17,650 für etwas mehr Flexibilität. 31 00:01:17,650 --> 00:01:20,380 Geben Sie die verknüpfte Liste, weitere grundlegende Datenstruktur 32 00:01:20,380 --> 00:01:22,360 Sie ist vielleicht nicht so vertraut sind. 33 00:01:22,360 --> 00:01:24,200 Auf einer hohen Ebene, 34 00:01:24,200 --> 00:01:26,840 eine verkettete Liste speichert Daten in einer Folge von Knoten 35 00:01:26,840 --> 00:01:29,280 daß miteinander mit Links verbunden sind, 36 00:01:29,280 --> 00:01:31,760 daher der Name "verketteten Liste." 37 00:01:31,760 --> 00:01:33,840 Wie wir sehen werden, ist dieser Unterschied im Design 38 00:01:33,840 --> 00:01:35,500 führt zu unterschiedlichen Vor-und Nachteile 39 00:01:35,500 --> 00:01:37,000 als ein Array. 40 00:01:37,000 --> 00:01:39,840 >> Hier einige C-Code für eine sehr einfache verknüpfte Liste von Zahlen. 41 00:01:39,840 --> 00:01:42,190 Sie können sehen, dass wir jeden Knoten vertreten 42 00:01:42,190 --> 00:01:45,520 in der Liste als eine Struktur, welche 2 Dinge enthält, 43 00:01:45,520 --> 00:01:47,280 eine ganze Zahl zu speichern als 'val' 44 00:01:47,280 --> 00:01:50,460 und einen Link zu dem nächsten Knoten in der Liste 45 00:01:50,460 --> 00:01:52,990 die wir vertreten als Zeiger namens "Weiter". 46 00:01:54,120 --> 00:01:56,780 Auf diese Weise können wir den gesamten Liste 47 00:01:56,780 --> 00:01:58,790 mit nur einem Zeiger auf den ersten Knoten 48 00:01:58,790 --> 00:02:01,270 und dann können wir folgen die nächsten Zeiger 49 00:02:01,270 --> 00:02:03,130 dem zweiten Knoten, 50 00:02:03,130 --> 00:02:05,280 dem dritten Knoten, 51 00:02:05,280 --> 00:02:07,000 dem vierten Knoten, 52 00:02:07,000 --> 00:02:09,889 und so weiter, bis wir an das Ende der Liste zu gelangen. 53 00:02:10,520 --> 00:02:12,210 >> Sie könnten in der Lage sein ein Vorteil, dies zu sehen 54 00:02:12,210 --> 00:02:14,490 über die statische Array-Struktur - mit einer verketteten Liste, 55 00:02:14,490 --> 00:02:16,450 wir brauchen nicht einen großen Teil des Speichers insgesamt. 56 00:02:17,400 --> 00:02:20,530 Der erste Knoten der Liste könnte an dieser Stelle in Erinnerung zu leben, 57 00:02:20,530 --> 00:02:23,160 und der zweite Knoten könnte den ganzen Weg hierher sein. 58 00:02:23,160 --> 00:02:25,780 Wir können alle Knoten zu erhalten, egal wo im Speicher sind, 59 00:02:25,780 --> 00:02:28,890 , weil ab dem 1. Knoten, wobei jeder Knoten nächste Zeiger 60 00:02:28,890 --> 00:02:31,700 sagt uns genau, wo zum nächsten gehen. 61 00:02:31,700 --> 00:02:33,670 >> Darüber hinaus haben wir nicht zu sagen, bis vor 62 00:02:33,670 --> 00:02:36,740 wie groß eine verlinkte Liste wird die Art, wie wir mit statischen Arrays, 63 00:02:36,740 --> 00:02:39,060 da können wir halten das Hinzufügen von Knoten zu einer Liste 64 00:02:39,060 --> 00:02:42,600 Solange es Raum irgendwo im Speicher zum neuen Knoten. 65 00:02:42,600 --> 00:02:45,370 Daher sind verkettete Listen einfach zu dynamisch ändern. 66 00:02:45,370 --> 00:02:47,950 Sprich, später im Programm haben wir weitere Knoten hinzufügen müssen 67 00:02:47,950 --> 00:02:49,350 in unsere Liste. 68 00:02:49,350 --> 00:02:51,480 Um einen neuen Knoten in unsere Liste einzufügen on the fly, 69 00:02:51,480 --> 00:02:53,740 alles, was wir tun müssen, ist Speicher für diesen Knoten 70 00:02:53,740 --> 00:02:55,630 plop in dem Datenwert, 71 00:02:55,630 --> 00:02:59,070 und dann legen Sie sie, wo wir durch Einstellung der entsprechenden Zeigern wollen. 72 00:02:59,070 --> 00:03:02,310 >> Zum Beispiel, wenn wir wollten, um einen Knoten zwischen platzieren 73 00:03:02,310 --> 00:03:04,020 die zweite und dritte Knoten der Liste 74 00:03:04,020 --> 00:03:06,800  hätten wir nicht die zweite oder dritte Knoten überhaupt zu bewegen. 75 00:03:06,800 --> 00:03:09,190 Sagen, dass wir das Einfügen dieses rote Knoten. 76 00:03:09,190 --> 00:03:12,890 Alles, was wir zu tun haben möchte, ist die neue Knoten nächste Zeiger gesetzt 77 00:03:12,890 --> 00:03:14,870 um zu der dritten Knotenpunkt 78 00:03:14,870 --> 00:03:18,580 und dann verkabeln des zweiten Knotens nächste Zeiger 79 00:03:18,580 --> 00:03:20,980 bis zum neuen Knotenpunkt. 80 00:03:22,340 --> 00:03:24,370 So können wir unsere Listen on the fly ändern 81 00:03:24,370 --> 00:03:26,090 da unsere Computer nicht Indexierung verlassen, 82 00:03:26,090 --> 00:03:28,990 sondern auf die Verknüpfung mit Zeigern, um sie zu speichern. 83 00:03:29,120 --> 00:03:31,600 >> Allerdings verknüpft ein Nachteil von Listen 84 00:03:31,600 --> 00:03:33,370 ist, dass, im Gegensatz zu einem statischen Array, 85 00:03:33,370 --> 00:03:36,690 Der Computer kann nicht nur auf die Mitte der Liste zu springen. 86 00:03:38,040 --> 00:03:40,780 Da der Computer muss jeder Knoten in der verketteten Liste zu besuchen 87 00:03:40,780 --> 00:03:42,330 um zum nächsten zu gelangen, 88 00:03:42,330 --> 00:03:44,770 es wird länger dauern, einen bestimmten Knoten zu finden 89 00:03:44,770 --> 00:03:46,400 als es in einem Array. 90 00:03:46,400 --> 00:03:48,660 Zu durchqueren die gesamte Liste braucht Zeit proportional 91 00:03:48,660 --> 00:03:50,580 der Länge der Liste, 92 00:03:50,580 --> 00:03:54,630 oder O (n) in asymptotischen Notation. 93 00:03:54,630 --> 00:03:56,510 Im Durchschnitt erreichen alle Knoten 94 00:03:56,510 --> 00:03:58,800 Auch braucht Zeit proportional zu n. 95 00:03:58,800 --> 00:04:00,700 >> Lassen Sie uns nun tatsächlich Code schreiben 96 00:04:00,700 --> 00:04:02,000 das funktioniert mit verknüpften Listen. 97 00:04:02,000 --> 00:04:04,220 Lassen Sie uns sagen, wir wollen eine verknüpfte Liste von Zahlen. 98 00:04:04,220 --> 00:04:06,140 Wir können einen Knoten in unserer Liste wieder vertreten 99 00:04:06,140 --> 00:04:08,340 als struct mit 2 Feldern, 100 00:04:08,340 --> 00:04:10,750 ein Integer-Wert namens "val" 101 00:04:10,750 --> 00:04:13,490 und ein nächster Zeiger auf den nächsten Knoten in der Liste. 102 00:04:13,490 --> 00:04:15,660 Nun, es scheint einfach genug. 103 00:04:15,660 --> 00:04:17,220 >> Lassen Sie uns sagen, wir wollen eine Funktion schreiben 104 00:04:17,220 --> 00:04:19,329 die Traversen die Liste ein und druckt die 105 00:04:19,329 --> 00:04:22,150 Wert in den letzten Knoten der Liste gespeichert. 106 00:04:22,150 --> 00:04:24,850 Nun, das heißt, wir müssen alle Knoten in der Liste durchlaufen 107 00:04:24,850 --> 00:04:27,310 um den letzten zu finden, aber da wir nicht das Hinzufügen 108 00:04:27,310 --> 00:04:29,250 oder etwas zu löschen, wollen wir nicht zu ändern 109 00:04:29,250 --> 00:04:32,210 Die innere Struktur der nächste Zeiger in der Liste. 110 00:04:32,210 --> 00:04:34,790 >> Also, wir einen Zeiger speziell brauchen für Traversierung 111 00:04:34,790 --> 00:04:36,940 die nennen wir "Crawler". 112 00:04:36,940 --> 00:04:38,870 Es wird durch alle Elemente der Liste kriechen 113 00:04:38,870 --> 00:04:41,190 indem Sie die Kette der nächsten Zeiger. 114 00:04:41,190 --> 00:04:43,750 Alle uns gespeichert ist ein Zeiger auf den ersten Knoten, 115 00:04:43,750 --> 00:04:45,730 oder "Kopf" der Liste. 116 00:04:45,730 --> 00:04:47,370 Kopf zeigt auf den ersten Knoten. 117 00:04:47,370 --> 00:04:49,120 Es ist vom Typ Zeiger-zu-Knoten. 118 00:04:49,120 --> 00:04:51,280 >> Um die tatsächliche ersten Knoten in der Liste zu bekommen, 119 00:04:51,280 --> 00:04:53,250 Wir haben zu dereferenzieren diesen Zeiger, 120 00:04:53,250 --> 00:04:55,100 aber bevor wir es dereferenzieren, müssen wir überprüfen, 121 00:04:55,100 --> 00:04:57,180 wenn sich der Zeiger null erste. 122 00:04:57,180 --> 00:04:59,190 Wenn es null ist, ist die Liste leer, 123 00:04:59,190 --> 00:05:01,320 und wir sollten Sie auch eine Nachricht, die, weil die Liste leer ist, 124 00:05:01,320 --> 00:05:03,250 es gibt keine letzte Knoten. 125 00:05:03,250 --> 00:05:05,190 Aber, sagen wir mal die Liste nicht leer ist. 126 00:05:05,190 --> 00:05:08,340 Wenn es nicht ist, dann sollten wir uns durch die gesamte Liste zu kriechen 127 00:05:08,340 --> 00:05:10,440 bis wir zu dem letzten Knoten der Liste 128 00:05:10,440 --> 00:05:13,030 und wie können wir sagen, ob wir bei der letzten Knoten in der Liste suchen? 129 00:05:13,670 --> 00:05:16,660 >> Nun, wenn eines Knotens nächste Zeiger null, 130 00:05:16,660 --> 00:05:18,320 Wir wissen, dass wir am Ende 131 00:05:18,320 --> 00:05:22,390 seit der letzten nächste Zeiger hätte keine nächsten Knoten in der Liste, um zu zeigen. 132 00:05:22,390 --> 00:05:26,590 Es ist gute Praxis, immer der letzte Knoten der nächste Zeiger mit null initialisiert 133 00:05:26,590 --> 00:05:30,800 eine standardisierte Eigenschaft, die uns warnt, wenn wir das Ende der Liste erreicht haben müssen. 134 00:05:30,800 --> 00:05:33,510 >> Also, wenn Crawler → weiter null ist, 135 00:05:34,120 --> 00:05:38,270 daran erinnern, dass der Pfeil-Syntax eine Abkürzung für Dereferenzierung ist 136 00:05:38,270 --> 00:05:40,010 ein Zeiger auf eine struct, dann Zugriff auf 137 00:05:40,010 --> 00:05:42,510 ihre nächste Feld entspricht der misslichen: 138 00:05:42,510 --> 00:05:48,750 (* Crawler). Nächsten. 139 00:05:49,820 --> 00:05:51,260 Nachdem wir den letzten Knoten gefunden, 140 00:05:51,260 --> 00:05:53,830 Wir wollen Crawler → val drucken, 141 00:05:53,830 --> 00:05:55,000 der Wert in dem aktuellen Knoten 142 00:05:55,000 --> 00:05:57,130 die wir kennen, ist das letzte. 143 00:05:57,130 --> 00:05:59,740 Andernfalls, wenn wir noch nicht auf dem letzten Knoten in der Liste, 144 00:05:59,740 --> 00:06:02,340 Wir müssen weiter an den nächsten Knoten in der Liste 145 00:06:02,340 --> 00:06:04,750 und prüfen, ob das ist das letzte. 146 00:06:04,750 --> 00:06:07,010 Um dies zu tun, setzen wir einfach unser Crawler Zeiger 147 00:06:07,010 --> 00:06:09,840 Um zu den aktuellen Knotens nächsten Wert darauf, 148 00:06:09,840 --> 00:06:11,680 das heißt, der nächste Knoten in der Liste. 149 00:06:11,680 --> 00:06:13,030 Dies wird getan, indem 150 00:06:13,030 --> 00:06:15,280 Crawler = Crawler → weiter. 151 00:06:16,050 --> 00:06:18,960 Dann wiederholen wir diesen Prozess mit einer Schleife zum Beispiel 152 00:06:18,960 --> 00:06:20,960 bis wir den letzten Knoten. 153 00:06:20,960 --> 00:06:23,150 So, zum Beispiel, wenn Crawler wurde Kopf nach, 154 00:06:24,050 --> 00:06:27,710 setzen wir Crawler zu Crawler → weiter zeigen, 155 00:06:27,710 --> 00:06:30,960 das ist der gleiche wie der nächste Feld des ersten Knotens. 156 00:06:30,960 --> 00:06:33,620 So, jetzt unser Crawler auf den zweiten Knoten zeigt, 157 00:06:33,620 --> 00:06:35,480 und wiederum wiederholen wir dies mit einer Schleife, 158 00:06:37,220 --> 00:06:40,610 bis wir den letzten Knoten gefunden, das heißt, 159 00:06:40,610 --> 00:06:43,640 wo der Knoten nächsten Zeiger zeigt auf null. 160 00:06:43,640 --> 00:06:45,070 Und da haben wir es, 161 00:06:45,070 --> 00:06:47,620 haben wir den letzten Knoten in der Liste gefunden, und um seinen Wert zu drucken, 162 00:06:47,620 --> 00:06:50,800 verwenden wir nur Crawler → val. 163 00:06:50,800 --> 00:06:53,130 >> Verfahrgeschwindigkeit ist nicht so schlimm, aber was ist das Einfügen? 164 00:06:53,130 --> 00:06:56,290 Lets sagen, wir wollen eine ganze Zahl in die vierte Position einzufügen 165 00:06:56,290 --> 00:06:58,040 in einer Integer-Liste. 166 00:06:58,040 --> 00:07:01,280 Das heißt zwischen den 3. und 4. aktuellen Knoten. 167 00:07:01,280 --> 00:07:03,760 Auch hier haben wir die Liste nur zu durchqueren 168 00:07:03,760 --> 00:07:06,520 bekommen die dritte Element, die wir nach dem Einsetzen sind. 169 00:07:06,520 --> 00:07:09,300 So schaffen wir einen Crawler Zeiger wieder auf die Liste zu durchlaufen, 170 00:07:09,300 --> 00:07:11,400 überprüfen, ob unser Kopf Zeiger ist null, 171 00:07:11,400 --> 00:07:14,810 und wenn es nicht ist, zeigen unsere Crawler Zeiger auf dem Head-Knoten. 172 00:07:16,880 --> 00:07:18,060 Also, wir sind auf dem ersten Element. 173 00:07:18,060 --> 00:07:21,020 Wir müssen vorwärts gehen 2 weitere Elemente, bevor wir einfügen können, 174 00:07:21,020 --> 00:07:23,390 so können wir eine for-Schleife verwenden 175 00:07:23,390 --> 00:07:26,430 int i = 1; i <3; i + + 176 00:07:26,430 --> 00:07:28,590 und in jeder Iteration der Schleife, 177 00:07:28,590 --> 00:07:31,540 voranzutreiben unser Crawler Zeiger vorwärts mit 1 Knoten 178 00:07:31,540 --> 00:07:34,570 durch Prüfen, ob der aktuelle Knoten der nächsten Feld null ist, 179 00:07:34,570 --> 00:07:37,550 und wenn es nicht ist, bewegen unsere Crawler Zeiger auf den nächsten Knoten 180 00:07:37,550 --> 00:07:41,810 indem sie gleich des aktuellen Knotens nächste Zeiger. 181 00:07:41,810 --> 00:07:45,210 So, da unsere for-Schleife, sagt das zu tun 182 00:07:45,210 --> 00:07:47,550 zweimal, 183 00:07:49,610 --> 00:07:51,190 wir haben den dritten Knoten erreicht, 184 00:07:51,190 --> 00:07:53,110 und einmal unser Crawler Zeiger hat den Knoten erreicht nach 185 00:07:53,110 --> 00:07:55,270 die wollen wir unsere neuen Integer einzufügen, 186 00:07:55,270 --> 00:07:57,050 Wie können wir eigentlich nicht das Einfügen? 187 00:07:57,050 --> 00:07:59,440 >> Nun, unsere neue Zahl in die Liste eingefügt werden 188 00:07:59,440 --> 00:08:01,250 als Teil seiner eigenen Knoten struct, 189 00:08:01,250 --> 00:08:03,140 da dies eigentlich eine Sequenz von Knoten. 190 00:08:03,140 --> 00:08:05,690 Also, lasst uns einen neuen Zeiger auf Knoten 191 00:08:05,690 --> 00:08:08,910 namens 'new_node " 192 00:08:08,910 --> 00:08:11,800 und setzen Sie ihn in den Speicher verweisen, dass wir nun die Möglichkeit 193 00:08:11,800 --> 00:08:14,270 auf dem Heap für den Knoten selbst, 194 00:08:14,270 --> 00:08:16,000 und wie viel Speicher brauchen wir zu vergeben? 195 00:08:16,000 --> 00:08:18,250 Nun, in der Größe eines Knotens, 196 00:08:20,450 --> 00:08:23,410 und wir wollen ihre val Feld auf die Zahl, die wir einfügen wollen eingestellt. 197 00:08:23,410 --> 00:08:25,590 Lassen Sie uns sagen, 6. 198 00:08:25,590 --> 00:08:27,710 Nun enthält der Knoten unserer Integer-Wert. 199 00:08:27,710 --> 00:08:30,650 Es ist auch ratsam, des neuen Knotens nächste Feld zu initialisieren 200 00:08:30,650 --> 00:08:33,690 darauf auf null 201 00:08:33,690 --> 00:08:35,080 aber was nun? 202 00:08:35,080 --> 00:08:37,179 >> Wir müssen die innere Struktur der Liste zu ändern 203 00:08:37,179 --> 00:08:40,409 und die nächsten Zeiger in der Liste der vorhandenen enthalten 204 00:08:40,409 --> 00:08:42,950 Dritte und vierte Knoten. 205 00:08:42,950 --> 00:08:46,560 Da die nächsten Zeiger bestimmt die Reihenfolge der Liste, 206 00:08:46,560 --> 00:08:48,650 und da wir das Einfügen unserer neuen Knoten 207 00:08:48,650 --> 00:08:50,510 direkt in die Mitte der Liste, 208 00:08:50,510 --> 00:08:52,010 kann es ein bisschen schwierig. 209 00:08:52,010 --> 00:08:54,250 Dies liegt daran, denkt daran, unsere Computer 210 00:08:54,250 --> 00:08:56,250 kennt nur die Position der Knoten in der Liste 211 00:08:56,250 --> 00:09:00,400 wegen der nächsten Zeiger in den vorherigen Knoten gespeichert. 212 00:09:00,400 --> 00:09:03,940 Also, wenn wir jemals aus den Augen verloren einem dieser Orte, 213 00:09:03,940 --> 00:09:06,860 sagen, indem einer der nächsten Zeiger in unserer Liste 214 00:09:06,860 --> 00:09:09,880 zum Beispiel, sagen wir, verändert 215 00:09:09,880 --> 00:09:12,920 der dritte Knoten nächsten Feld 216 00:09:12,920 --> 00:09:15,610 bis zu einem gewissen Knoten über hier zu zeigen. 217 00:09:15,610 --> 00:09:17,920 Wir hatten kein Glück, denn würden wir nicht 218 00:09:17,920 --> 00:09:20,940 eine Idee haben, wo der Rest der Liste zu finden, 219 00:09:20,940 --> 00:09:23,070 und das ist natürlich wirklich schlecht. 220 00:09:23,070 --> 00:09:25,080 Also, wir haben wirklich vorsichtig sein über die Reihenfolge 221 00:09:25,080 --> 00:09:28,360 in denen wir manipulieren unsere nächsten Zeiger beim Einführen. 222 00:09:28,360 --> 00:09:30,540 >> Also, um dies zu vereinfachen, sagen wir, dass 223 00:09:30,540 --> 00:09:32,220 unser erstes 4-Knoten 224 00:09:32,220 --> 00:09:36,200 heißen A, B, C und D, mit den Pfeilen, die die Kette von Zeigern 225 00:09:36,200 --> 00:09:38,070 , die die Knoten verbinden. 226 00:09:38,070 --> 00:09:40,050 Also müssen wir unsere neuen Knoten einfügen 227 00:09:40,050 --> 00:09:42,070 im zwischen den Knoten C und D. 228 00:09:42,070 --> 00:09:45,060 Es ist wichtig, um sie in der richtigen Reihenfolge zu tun, und ich werde Ihnen zeigen, warum. 229 00:09:45,060 --> 00:09:47,500 >> Lasst uns an der falschen Weg, um es zuerst tun suchen. 230 00:09:47,500 --> 00:09:49,490 Hey, kennen wir die neuen Knoten zu kommen, nachdem C rechts, 231 00:09:49,490 --> 00:09:51,910 also lasst uns gesetzt C der nächste Zeiger 232 00:09:51,910 --> 00:09:54,700 zeigen soll new_node. 233 00:09:56,530 --> 00:09:59,180 Alles klar, scheint okay, wir haben nur zu Ende zu bringen nun durch 234 00:09:59,180 --> 00:10:01,580 Damit ist das neue Knoten nächste Zeiger Punkt D, 235 00:10:01,580 --> 00:10:03,250 aber warten, wie können wir das tun? 236 00:10:03,250 --> 00:10:05,170 Das einzige, was uns sagen konnte, wo D war, 237 00:10:05,170 --> 00:10:07,630 wurde der nächste Zeiger zuvor in C gespeichert, 238 00:10:07,630 --> 00:10:09,870 aber wir schrieben den Zeiger 239 00:10:09,870 --> 00:10:11,170 auf den neuen Knotenpunkt, 240 00:10:11,170 --> 00:10:14,230 so haben wir nicht mehr eine Ahnung, wo D ist in Erinnerung, 241 00:10:14,230 --> 00:10:17,020 und wir haben den Rest der Liste verloren. 242 00:10:17,020 --> 00:10:19,000 Überhaupt nicht gut. 243 00:10:19,000 --> 00:10:21,090 >> Also, wie machen wir das richtig verstanden? 244 00:10:22,360 --> 00:10:25,090 Zum einen weisen die neuen Knoten der nächsten Zeiger auf D. 245 00:10:26,170 --> 00:10:28,990 Nun werden sowohl die neuen Knotens und C der nächste Zeiger 246 00:10:28,990 --> 00:10:30,660 sind mit dem gleichen Knoten, D weisende, 247 00:10:30,660 --> 00:10:32,290 aber das ist in Ordnung. 248 00:10:32,290 --> 00:10:35,680 Jetzt können wir zeigen C der nächste Zeiger auf den neuen Knoten. 249 00:10:37,450 --> 00:10:39,670 Also haben wir diese ohne Datenverlust durchgeführt. 250 00:10:39,670 --> 00:10:42,280 In Code ist C der aktuelle Knoten 251 00:10:42,280 --> 00:10:45,540 dass die Traversierung Zeiger Crawler verweist, 252 00:10:45,540 --> 00:10:50,400 und D wird durch den Knoten, auf die durch den aktuellen Knotens nächste Feld repräsentiert, 253 00:10:50,400 --> 00:10:52,600 oder Crawler → weiter. 254 00:10:52,600 --> 00:10:55,460 Also, wir zunächst des neuen Knotens nächste Zeiger 255 00:10:55,460 --> 00:10:57,370 zu Crawler → weiter zeigen, 256 00:10:57,370 --> 00:11:00,880 auf die gleiche Weise haben wir gesagt new_node der nächste Zeiger sollte 257 00:11:00,880 --> 00:11:02,780 weisen auf D in der Abbildung. 258 00:11:02,780 --> 00:11:04,540 Dann, können wir des aktuellen Knotens nächste Zeiger 259 00:11:04,540 --> 00:11:06,330 auf unserer neuen Knoten 260 00:11:06,330 --> 00:11:10,980 so wie wir warten, bis Punkt C in der Zeichnung new_node hatte. 261 00:11:10,980 --> 00:11:12,250 Jetzt ist alles in Ordnung, und wir nicht verlieren 262 00:11:12,250 --> 00:11:14,490 den Überblick über alle Daten, und wir konnten nur 263 00:11:14,490 --> 00:11:16,200 aufkleben unserem neuen Knotens in der Mitte der Liste 264 00:11:16,200 --> 00:11:19,330 ohne Umbau der ganzen Sache oder sogar verschieben alle Elemente 265 00:11:19,330 --> 00:11:22,490 die Art und Weise würden wir mit einem festen Array der Länge gehabt haben. 266 00:11:22,490 --> 00:11:26,020 >> So sind verkettete Listen eine grundlegende, aber wichtige dynamische Datenstruktur 267 00:11:26,020 --> 00:11:29,080 die haben beide Vor-und Nachteile 268 00:11:29,080 --> 00:11:31,260 gegenüber Arrays und anderen Datenstrukturen, 269 00:11:31,260 --> 00:11:33,350 und wie es oft der Fall, in der Informatik, 270 00:11:33,350 --> 00:11:35,640 ist es wichtig zu wissen, wann man jedes Werkzeug verwendet, 271 00:11:35,640 --> 00:11:37,960 so können Sie abholen das richtige Werkzeug für den richtigen Job. 272 00:11:37,960 --> 00:11:40,060 >> Für weitere Übungen versuchen, schriftlich Funktionen 273 00:11:40,060 --> 00:11:42,080 Löschen von Knoten aus einer verketteten Liste - 274 00:11:42,080 --> 00:11:44,050 erinnern, vorsichtig zu sein über die Reihenfolge, in der Sie neu anordnen 275 00:11:44,050 --> 00:11:47,430 Ihren nächsten Zeiger um sicherzustellen, dass Sie nicht verlieren ein Stück Ihrer Liste - 276 00:11:47,430 --> 00:11:50,200 oder eine Funktion, um die Knoten in einer verknüpften Liste zählen, 277 00:11:50,200 --> 00:11:53,280 oder eine lustige ein, um die Reihenfolge der alle Knoten in einer verknüpften Liste rückgängig zu machen. 278 00:11:53,280 --> 00:11:56,090 >> Mein Name ist Jackson Steinkamp, ​​ist dies CS50.