1 00:00:00,000 --> 00:00:02,520 [Powered by Google Translate] [Woche 6, Fortsetzung] 2 00:00:02,520 --> 00:00:04,160 [David J. Malan] [Harvard University] 3 00:00:04,160 --> 00:00:08,720 [Dies ist CS50.] [CS50.TV] 4 00:00:08,720 --> 00:00:12,970 Dies ist CS50 und das ist das Ende der Woche 6. 5 00:00:12,970 --> 00:00:17,970 So CS50x, einer der ersten Kurse in Harvard in den EDX-Initiative beteiligt 6 00:00:17,970 --> 00:00:20,590 Tat debütierte am vergangenen Montag. 7 00:00:20,590 --> 00:00:23,460 Wenn Sie möchten, um einen Blick auf, was andere über das Internet erhalten 8 00:00:23,460 --> 00:00:27,180 folgen nun zusammen mit, können Sie x.cs50.net Kopf. 9 00:00:27,180 --> 00:00:30,350 Das wird Sie an die entsprechende Stelle auf edx.org umzuleiten, 10 00:00:30,350 --> 00:00:34,160 das war, wo diese und andere Kurse vom MIT und Berkeley jetzt leben. 11 00:00:34,160 --> 00:00:38,140 Sie müssen sich für ein Konto, Sie werden feststellen, dass das Material weitgehend die gleichen 12 00:00:38,140 --> 00:00:42,170 Sie habe in diesem Semester, wenn auch ein paar Wochen verzögert, da wir alles fertig zu bekommen. 13 00:00:42,170 --> 00:00:46,930 Aber was die Schüler in CS50x werden jetzt sehen, ist eine Schnittstelle ganz wie diese ein. 14 00:00:46,930 --> 00:00:50,040 Dies ist zum Beispiel Zamyla führt die Komplettlösung für den problemlosen Satz 0. 15 00:00:50,040 --> 00:00:54,230 Nach der Anmeldung in edx.org sieht ein CS50x Schüler die Art von Dingen 16 00:00:54,230 --> 00:00:57,170 Sie erwarten würden, in einem Kurs zu sehen: die Vorlesung für Montag, 17 00:00:57,170 --> 00:01:01,650 Vortrag für Mittwoch, diverse Kurzfilme, die Problemstellungen, die Komplettlösungen, PDFs. 18 00:01:01,650 --> 00:01:04,459 Darüber hinaus, wie Sie hier sehen, maschinelle Übersetzungen 19 00:01:04,459 --> 00:01:08,390 Englisch Transkripte in Chinesisch, Japanisch, Spanisch, Italienisch, 20 00:01:08,390 --> 00:01:12,810 und eine ganze Reihe von anderen Sprachen, die sicherlich wird unvollkommenen 21 00:01:12,810 --> 00:01:15,840 wie wir ausrollen programmatisch mit etwas namens ein API, 22 00:01:15,840 --> 00:01:18,360 oder Application Programming Interface, von Google 23 00:01:18,360 --> 00:01:21,360 das ermöglicht es uns, zu konvertieren Deutsch zu diesen anderen Sprachen. 24 00:01:21,360 --> 00:01:24,100 Aber dank der wunderbaren Geist von einigen hundert-plus Freiwilligen, 25 00:01:24,100 --> 00:01:26,940 zufälligen Menschen über das Internet, die uns freundlicherweise angeboten haben, sich zu engagieren 26 00:01:26,940 --> 00:01:30,180 In diesem Projekt werden wir schrittweise Verbesserung der Qualität dieser Übersetzungen 27 00:01:30,180 --> 00:01:35,790 indem er den Menschen die Fehler korrigieren, dass unsere Computer gemacht haben. 28 00:01:35,790 --> 00:01:42,330 >> So stellt sich heraus, dass wir ein paar mehr Studenten auftauchen hatte am Montag, als wir ursprünglich erwartet. 29 00:01:42,330 --> 00:01:48,980 In der Tat, jetzt CS50x hat 100.000 Menschen nach zusammen zu Hause. 30 00:01:48,980 --> 00:01:54,430 So realisieren Sie alle sind Teil dieser konstituierenden Klasse machen diesen Kurs in der Informatik 31 00:01:54,430 --> 00:01:57,370 Bildung allgemein, weiter gefasst, zugänglich. 32 00:01:57,370 --> 00:02:00,130 Und die Realität ist nun mit einigen dieser massiven Online-Kurse, 33 00:02:00,130 --> 00:02:04,070 sie alle mit diesen sehr hohen Zahlen beginnen, wie wir hier zu tun zu haben scheinen. 34 00:02:04,070 --> 00:02:08,759 Aber das Ziel letztlich für CS50x ist wirklich so viele Menschen über die Ziellinie wie möglich zu erhalten. 35 00:02:08,759 --> 00:02:12,000 Vom Design her ist CS50x werde aus dieser vergangenen Montag angeboten werden 36 00:02:12,000 --> 00:02:17,430 den ganzen Weg bis zum 15. April 2013, so dass Leute, die haben Schule Verpflichtungen anderswo, 37 00:02:17,430 --> 00:02:20,990 Arbeit, Familie, andere Konflikte und dergleichen, haben ein bisschen mehr Flexibilität 38 00:02:20,990 --> 00:02:23,640 mit denen in diesem Kurs tauchen, das, es genügt zu sagen, 39 00:02:23,640 --> 00:02:30,540 ist ziemlich ambitioniert tun, wenn erst im Laufe von nur drei Monaten während eines üblichen Semester. 40 00:02:30,540 --> 00:02:34,190 Aber diese Schüler werden die Bewältigung der gleiche Problem Sets, sich den gleichen Inhalt, 41 00:02:34,190 --> 00:02:36,350 mit Zugriff auf dieselben Shorts und dergleichen. 42 00:02:36,350 --> 00:02:38,990 So erkennen, dass wir alle wirklich sind in diesem zusammen. 43 00:02:38,990 --> 00:02:42,360 Und einer der Endziele der CS50x ist nicht nur so viele Leute sich 44 00:02:42,360 --> 00:02:45,720 bis zur Ziellinie und ihnen diese neu gewonnene Verständnis der Informatik 45 00:02:45,720 --> 00:02:49,000 und Programmierung, sondern auch, haben sie über diese gemeinsame Erfahrung. 46 00:02:49,000 --> 00:02:52,010 Eines der bestimmenden Merkmale der 50 auf dem Campus, so hoffen wir, 47 00:02:52,010 --> 00:02:56,260 hat diese Art von Gemeinschaftserlebnis, zum Besseren oder zum Schlechteren, manchmal, 48 00:02:56,260 --> 00:02:59,480 aber mit diesen Menschen um nach links und nach rechts zu drehen, 49 00:02:59,480 --> 00:03:01,830 und Sprechzeiten und die Hackathon und fair. 50 00:03:01,830 --> 00:03:04,560 Es ist ein wenig schwerer zu, dass in der Person mit Leuten online tun, 51 00:03:04,560 --> 00:03:10,580 aber CS50x wird im April mit dem ersten CS50 Expo abzuschließen, 52 00:03:10,580 --> 00:03:13,630 was wird ein Online-Adaption unserer Idee der Messe sein 53 00:03:13,630 --> 00:03:18,250 wo diese Tausende von Studenten alle eingeladen, eine 1 einzureichen - bis 2-Minuten-Video, 54 00:03:18,250 --> 00:03:22,480 entweder ein Screencast über ihre endgültige Projekt oder Video von ihnen winken hallo 55 00:03:22,480 --> 00:03:24,490 und reden über ihr Projekt und Demonstrieren es, 56 00:03:24,490 --> 00:03:27,610 ähnlich wie Ihre Vorgänger haben hier auf dem Campus in der Messe getan, 57 00:03:27,610 --> 00:03:31,400 so dass durch Semester Ende ist die Hoffnung auf eine globale Ausstellung haben 58 00:03:31,400 --> 00:03:37,080 der CS50x Studenten Abschlussarbeiten, ähnlich wie das, was erwartet Sie im Dezember dieses Jahres hier auf dem Campus. 59 00:03:37,080 --> 00:03:39,680 Also mehr auf, dass in den kommenden Monaten. 60 00:03:39,680 --> 00:03:43,640 >> Mit 100.000 Studenten, obwohl, kommt eine Notwendigkeit für ein paar CAs. 61 00:03:43,640 --> 00:03:47,590 Vorausgesetzt, dass Sie Jungs sind sich der Weg hier und unter CS50 62 00:03:47,590 --> 00:03:51,630 mehrere Wochen im Voraus aus diesem Material die Freilassung der Leute auf EDX, 63 00:03:51,630 --> 00:03:55,330 erkennen wir würden uns freuen, möglichst viele unserer eigenen Studenten wie möglich an dieser Initiative beteiligt, 64 00:03:55,330 --> 00:03:58,720 sowohl während des Semesters als auch in diesem Winter und im kommenden Frühjahr. 65 00:03:58,720 --> 00:04:01,620 Also, wenn Sie möchten, sich in CS50x, 66 00:04:01,620 --> 00:04:07,450 Besonders Beitritt in auf CS50x diskutieren, die EDX Version CS50 diskutieren, 67 00:04:07,450 --> 00:04:10,140 was viele von Ihnen haben auf dem Campus wurden mit der Online-Bulletin Board, 68 00:04:10,140 --> 00:04:13,040 bitte den Kopf auf diese URL, lassen Sie uns wissen, wer Sie sind, 69 00:04:13,040 --> 00:04:16,450 weil wir würden gerne bauen ein Team von Studenten und Mitarbeitern und Dozenten gleichermaßen 70 00:04:16,450 --> 00:04:19,630 auf dem Campus, die sind einfach Mitspielen und aushelfen. 71 00:04:19,630 --> 00:04:21,720 Und wenn sie sehen, eine Frage, die ihnen vertraut ist, 72 00:04:21,720 --> 00:04:25,320 Sie hören einen Studenten berichten einige Fehler irgendwo da draußen in einem Land auf dem Internet, 73 00:04:25,320 --> 00:04:27,450 und dass klingelt, weil Sie hatte auch das gleiche Problem 74 00:04:27,450 --> 00:04:32,620 in Ihrer d-Halle vor einiger Zeit, hoffentlich dann können Sie in Glockenspiel und teilen Sie Ihre eigenen Erfahrungen. 75 00:04:32,620 --> 00:04:37,300 Also bitte teilzunehmen, wenn Sie möchten. 76 00:04:37,300 --> 00:04:39,360 >> Informatik Kurse an der Harvard haben ein bisschen von einer Tradition, 77 00:04:39,360 --> 00:04:44,730 CS50 unter ihnen, der mit etwas Kleidung, ein paar Kleider, die Sie mit Stolz tragen kann 78 00:04:44,730 --> 00:04:49,090 am Semester Ende sagen ganz stolz, dass Sie CS50 fertig 79 00:04:49,090 --> 00:04:51,830 und nahm CS50 und dergleichen, und wir versuchen immer die Studenten einbeziehen 80 00:04:51,830 --> 00:04:54,540 bei diesem Verfahren so weit wie möglich, wodurch wir laden, 81 00:04:54,540 --> 00:04:56,900 um diese Zeit des Semesters den Studenten einreichen Designs 82 00:04:56,900 --> 00:04:59,330 mit Photoshop, oder was auch immer Werkzeug der Wahl Sie möchten, verwenden 83 00:04:59,330 --> 00:05:02,330 wenn Sie ein Designer, Entwürfe für T-Shirts und Sweatshirts einreichen 84 00:05:02,330 --> 00:05:06,100 und Sonnenschirme und kleine Bandanas für Hunde, die wir jetzt haben, und dergleichen. 85 00:05:06,100 --> 00:05:09,370 Und alles ist dann - die Gewinner jedes Jahr werden dann ausgestellt 86 00:05:09,370 --> 00:05:12,700 auf den Verlauf der Internetseite store.cs50.net. 87 00:05:12,700 --> 00:05:15,790 Alles wird zum Selbstkostenpreis dort verkauft, aber die Website läuft einfach selbst. 88 00:05:15,790 --> 00:05:18,330 und ermöglicht es den Menschen, um die Farben und Designs, die sie gerne wählen. 89 00:05:18,330 --> 00:05:20,420 Also dachte ich, wir würden nur Aktien einige der letztjährigen Designs 90 00:05:20,420 --> 00:05:25,130 Das waren auf der Website neben diesem einen hier, was ist eine jährliche Tradition. 91 00:05:25,130 --> 00:05:29,410 "Every Day I Seg Faultn bin" war einer der Einreichungen im vergangenen Jahr, 92 00:05:29,410 --> 00:05:32,290 die immer noch dort für Alumni. 93 00:05:32,290 --> 00:05:35,820 Wir hatten diese ein, "CS50, Established 1989." 94 00:05:35,820 --> 00:05:39,010 Einer unserer Bowdens, Rob, war sehr beliebt im letzten Jahr. 95 00:05:39,010 --> 00:05:43,480 "Team Bowden" geboren wurde, wurde dieser Entwurf vorgelegt, unter den Top-Anbietern. 96 00:05:43,480 --> 00:05:49,040 Wie diese hier. Viele Menschen hatten "Bowden Fever" nach den Umsatz-Protokolle. 97 00:05:49,040 --> 00:05:52,650 Erkenne, dass das könnte jetzt Ihr Design dabei sein, auf dem Internet. 98 00:05:52,650 --> 00:05:57,510 Weitere Details hierzu finden Sie im nächsten Problem setzt zu kommen. 99 00:05:57,510 --> 00:06:00,330 >> Ein weiteres Werkzeug: Sie habe einige Belichtung und jetzt hoffentlich 100 00:06:00,330 --> 00:06:02,350 einige Hands-on Erfahrung mit GDB, 101 00:06:02,350 --> 00:06:04,570 das ist natürlich ein Debugger und ermöglicht es Ihnen zu manipulieren 102 00:06:04,570 --> 00:06:09,500 Ihr Programm auf einem relativ niedrigen Niveau, zu tun, was Arten von Dingen? 103 00:06:09,500 --> 00:06:13,030 Was bedeutet GDB können Sie tun? 104 00:06:13,030 --> 00:06:15,030 Yeah? Gib mir etwas. [Schüler Antwort unverständlich] 105 00:06:15,030 --> 00:06:18,120 Gut. Treten Sie ein in Funktion, so dass Sie nicht einfach zu laufen geben 106 00:06:18,120 --> 00:06:22,310 und haben das Programm durchblasen seiner Gesamtheit, Druck, Dinge auf die Standardausgabe. 107 00:06:22,310 --> 00:06:25,190 Vielmehr kann man durch sie Zeile für Zeile fort, entweder eingeben nächsten 108 00:06:25,190 --> 00:06:30,300 Zeile für Zeile für Zeile oder Schritt in eine Funktion zu tauchen, in der Regel ein, dass du geschrieben hast zu gehen. 109 00:06:30,300 --> 00:06:35,240 Was bedeutet GDB können Sie tun? Yeah? [Schüler Antwort unverständlich] 110 00:06:35,240 --> 00:06:38,100 Drucken Variablen. Also, wenn Sie wollen ein wenig Introspektion innerhalb des Programms zu tun 111 00:06:38,100 --> 00:06:41,500 ohne zu schreiben printf Aussagen ganz über dem Platz greifen, 112 00:06:41,500 --> 00:06:44,600 Sie können nur drucken variable oder zeigen eine Variable. 113 00:06:44,600 --> 00:06:46,710 Was kann man mit einem Debugger wie GDB tun? 114 00:06:46,710 --> 00:06:49,170 [Schüler Antwort unverständlich] 115 00:06:49,170 --> 00:06:52,080 Genau. Sie können Haltepunkte setzen, können Sie Pause Ausführung sagen, 116 00:06:52,080 --> 00:06:54,020 an der Hauptfunktion oder foo Funktion. 117 00:06:54,020 --> 00:06:56,800 Sie können Pause Ausführung in Zeile 123 sagen. 118 00:06:56,800 --> 00:06:58,950 Und Haltepunkte sind eine wirklich leistungsfähige Technik 119 00:06:58,950 --> 00:07:01,110 denn wenn Sie ein allgemeines Gefühl von wo Ihr Problem 120 00:07:01,110 --> 00:07:05,360 Wahrscheinlich ist, müssen Sie nicht Zeit damit verschwenden Durchlaufen des Programms insgesamt. 121 00:07:05,360 --> 00:07:08,250 Sie lassen sich im Wesentlichen genau dort springen und dann beginnt zu schreiben - 122 00:07:08,250 --> 00:07:10,970 Schreiten durch sie mit der nächsten Stufe oder od.dgl. 123 00:07:10,970 --> 00:07:14,340 Aber der Haken mit so etwas wie GDB ist, dass es Ihnen hilft, die menschliche, 124 00:07:14,340 --> 00:07:16,940 finden Sie Ihre Probleme und finden Sie Ihre Fehler. 125 00:07:16,940 --> 00:07:19,470 Es muss nicht unbedingt finden sie so viel für dich. 126 00:07:19,470 --> 00:07:23,070 >> So haben wir die anderen Tage style50, was eine kurze Kommandozeilen-Tool 127 00:07:23,070 --> 00:07:27,500 das versucht, Ihren Code ein wenig sauberer als Sie stilisieren, der Mensch könnte getan haben. 128 00:07:27,500 --> 00:07:29,530 Aber auch das ist wirklich nur eine ästhetische Sache. 129 00:07:29,530 --> 00:07:34,110 Aber es stellt sich heraus, es ist das andere Tool namens Valgrind, die ein wenig mehr geheimnisvoll zu bedienen ist. 130 00:07:34,110 --> 00:07:36,860 Sein Ausgang ist grausam kryptisch auf den ersten Blick. 131 00:07:36,860 --> 00:07:39,420 Aber es ist wunderbar nützlich, vor allem jetzt, da wir in dem Teil des Begriffs sind 132 00:07:39,420 --> 00:07:43,080 wo Sie fangen an, malloc und dynamische Speicherzuweisung verwenden. 133 00:07:43,080 --> 00:07:45,420 Dinge gehen wirklich, wirklich falsch schnell. 134 00:07:45,420 --> 00:07:49,320 Denn wenn Sie vergessen, Ihr Gedächtnis zu befreien, oder Sie dereferenzieren einige NULL-Zeiger, 135 00:07:49,320 --> 00:07:55,770 oder Sie einige Müll Zeigerdereferenzierung, was ist in der Regel das Symptom, dass die Ergebnisse? 136 00:07:55,770 --> 00:07:59,470 Seg Schuld. Und Sie erhalten diese Core-Datei einer gewissen Anzahl von Kilobyte oder Megabyte 137 00:07:59,470 --> 00:08:02,990 das stellt den Zustand Ihres Programms im Speicher, wenn es abgestürzt ist, 138 00:08:02,990 --> 00:08:05,730 aber Ihr Programm letztendlich seg Fehler, Segmentation Fault, 139 00:08:05,730 --> 00:08:08,450 was bedeutet, etwas Schlimmes passiert fast immer im Zusammenhang 140 00:08:08,450 --> 00:08:11,750 zu einem Speicher-bezogene Fehler, dass Sie irgendwo gemacht. 141 00:08:11,750 --> 00:08:14,100 So Valgrind hilft Ihnen, Dinge wie diese. 142 00:08:14,100 --> 00:08:17,720 Es ist ein Werkzeug, das Sie laufen, wie GDB, nachdem Sie das Programm zusammengestellt haben, 143 00:08:17,720 --> 00:08:20,330 aber anstatt Führen Sie das Programm direkt, laufen Sie Valgrind 144 00:08:20,330 --> 00:08:23,960 und Sie übergeben es Ihrem Programm, so wie du mit GDB tun. 145 00:08:23,960 --> 00:08:26,220 Nun, die Nutzung, um die beste Art der Ausgabe, 146 00:08:26,220 --> 00:08:30,410 ist ein wenig lang, so richtig es atop des Bildschirms sehen Sie Valgrind-v. 147 00:08:30,410 --> 00:08:35,350 "-V" fast universell bedeutet, verbose, wenn Sie Programme sind auf einem Linux-Computer. 148 00:08:35,350 --> 00:08:38,770 So bedeutet es ausspucken mehr Daten, als Sie vielleicht standardmäßig. 149 00:08:38,770 --> 00:08:45,510 "- Leck-check = voll." Dies ist nur zu sagen Check für alle möglichen Speicherlecks, 150 00:08:45,510 --> 00:08:49,430 Fehler, die ich gemacht haben könnte. Auch dies ist ein gemeinsames Paradigma mit Linux-Programmen. 151 00:08:49,430 --> 00:08:52,710 Im Allgemeinen, wenn Sie eine Befehlszeile Argument haben, das ist ein "Schalter", 152 00:08:52,710 --> 00:08:55,830 Das soll das Verhalten des Programms zu ändern, und es ist ein einzelner Buchstabe, 153 00:08:55,830 --> 00:09:00,310 es-v, aber wenn es das ist eingeschaltet, nur durch Design des Programmierers, 154 00:09:00,310 --> 00:09:05,150 ist ein ganzes Wort oder eine Reihe von Wörtern, beginnt das Befehlszeilenargument mit -. 155 00:09:05,150 --> 00:09:08,190 Dies sind nur menschliche Konventionen, aber du wirst sie immer sehen. 156 00:09:08,190 --> 00:09:12,410 Und dann, endlich, "a.out" ist die willkürliche Namen für das Programm in diesem speziellen Beispiel. 157 00:09:12,410 --> 00:09:14,640 Und hier einige repräsentative Ausgabe. 158 00:09:14,640 --> 00:09:22,890 >> Bevor wir uns, was das bedeuten könnte schauen, lass mich gehen über zu einer Code-Snippet hier. 159 00:09:22,890 --> 00:09:26,390 Und lassen Sie mich verschieben Sie diese aus dem Weg, in Kürze, 160 00:09:26,390 --> 00:09:32,120 und lassen Sie uns einen Blick auf memory.c, die in diesem kurzen Beispiel ist hier. 161 00:09:32,120 --> 00:09:36,290 So in diesem Programm, lassen Sie mich heran zu den Funktionen und Fragen. 162 00:09:36,290 --> 00:09:39,430 Wir haben eine Funktion main, die eine Funktion aufruft, f, 163 00:09:39,430 --> 00:09:45,590 und was dann bedeutet f gehen zu tun, in etwas technisches Englisch? 164 00:09:45,590 --> 00:09:49,760 Was bedeutet f gehen zu tun? 165 00:09:49,760 --> 00:09:53,680 Wie wäre ich mit der Linie 20 zu starten, und der Stern Standort spielt keine Rolle, 166 00:09:53,680 --> 00:09:56,720 aber ich werde einfach konsequent sein hier mit dem letzten Vortrag. 167 00:09:56,720 --> 00:09:59,910 Was ist in Zeile 20 für uns? Auf der linken Seite. Wir brechen sie weiter. 168 00:09:59,910 --> 00:10:02,410 Int * x: Was bedeutet das? 169 00:10:02,410 --> 00:10:04,940 Okay. Es Deklaration eines Zeigers, und jetzt lasst uns noch technisch. 170 00:10:04,940 --> 00:10:10,230 Was bedeutet es ganz konkret, um einen Zeiger zu deklarieren? Jemand anderes? 171 00:10:10,230 --> 00:10:15,050 Yeah? [Schüler Antwort unverständlich] Too far. 172 00:10:15,050 --> 00:10:17,060 Sie sind also auf der rechten Seite des Gleichheitszeichens lesen. 173 00:10:17,060 --> 00:10:20,290 Konzentrieren wir uns nur auf der linken Seite, nur auf int * x. 174 00:10:20,290 --> 00:10:24,700 Dies bedeutet "deklarieren", einen Zeiger, aber jetzt lass uns in tieferen dieser Definition tauchen. 175 00:10:24,700 --> 00:10:28,330 Was heißt das konkret, technisch bedeuten? Yeah? 176 00:10:28,330 --> 00:10:31,940 [Schüler Antwort unverständlich] 177 00:10:31,940 --> 00:10:35,090 Okay. Es bereitet sich auf eine Adresse im Speicher zu speichern. 178 00:10:35,090 --> 00:10:40,680 Gut. Und lassen Sie uns noch einen Schritt weiter, es ist eine Variable deklarieren, x, die 32 Bit ist. 179 00:10:40,680 --> 00:10:44,440 Und ich weiß, es ist 32 Bit, weil -? 180 00:10:44,440 --> 00:10:47,390 Es ist nicht, weil es ein int ist, weil es ein Zeiger in diesem Fall ist. 181 00:10:47,390 --> 00:10:49,650 Zufall, dass es ein und dieselbe mit einem int ist, 182 00:10:49,650 --> 00:10:51,970 aber die Tatsache, dass es der Stern dort bedeutet dies ist ein Zeiger 183 00:10:51,970 --> 00:10:57,300 und in dem Gerät, wie bei vielen Computern, aber nicht alle, sind Zeiger 32 Bits. 184 00:10:57,300 --> 00:11:01,850 Auf mehr moderne Hardware wie die neuesten Macs, die neuesten PCs, Sie haben 64-Bit-Zeiger, 185 00:11:01,850 --> 00:11:04,160 aber in dem Gerät, diese Dinge sind 32 Bit. 186 00:11:04,160 --> 00:11:08,380 So werden wir auf, dass zu standardisieren. Genauer gesagt, geht die Geschichte wie folgt: 187 00:11:08,380 --> 00:11:10,820 Wir "erklären" einen Zeiger, was bedeutet das? 188 00:11:10,820 --> 00:11:12,810 Wir bereiten eine Speicheradresse zu speichern. 189 00:11:12,810 --> 00:11:15,530 Was bedeutet das? 190 00:11:15,530 --> 00:11:19,810 Wir schaffen eine Variable namens x, das in Anspruch nimmt 32 Bit 191 00:11:19,810 --> 00:11:23,810 das wird sich bald speichern Sie die Adresse einer Ganzzahl. 192 00:11:23,810 --> 00:11:26,470 Und das ist wahrscheinlich ungefähr so ​​präzise wie wir bekommen können. 193 00:11:26,470 --> 00:11:31,810 Es ist gut voran, um die Welt zu vereinfachen und nur sagen, erklären, einen Zeiger namens x. 194 00:11:31,810 --> 00:11:35,380 Deklariert einen Zeiger, sondern erkennen und verstehen, was eigentlich vor sich geht 195 00:11:35,380 --> 00:11:38,490 sogar in nur jenen wenigen Zeichen. 196 00:11:38,490 --> 00:11:42,040 >> Nun, ist das ein fast ein wenig zu erleichtern, obwohl es eine längere Ausdruck ist. 197 00:11:42,040 --> 00:11:48,160 Also, was ist dieses Tun, das ist nun hervorgehoben: "malloc (10 * sizeof (int));" Yeah? 198 00:11:48,160 --> 00:11:52,350 [Schüler Antwort unverständlich] 199 00:11:52,350 --> 00:11:58,250 Gut. Und ich werde es dort. Es Zuteilung ein Stück Speicher für zehn Zahlen. 200 00:11:58,250 --> 00:12:02,190 Und nun in etwas tiefer tauchen, es ist Zuweisung ein Stück Speicher für zehn Zahlen. 201 00:12:02,190 --> 00:12:05,390 Was ist malloc dann wieder? 202 00:12:05,390 --> 00:12:10,390 Die Adresse dieser Brocken, oder, genauer gesagt, die Adresse des ersten Bytes des Chunk. 203 00:12:10,390 --> 00:12:14,080 Wie dann bin ich, der Programmierer, um zu wissen, wo das Stück Speicher Enden? 204 00:12:14,080 --> 00:12:18,340 Ich weiß, dass es zusammenhängende ist. Malloc, per Definition, wird Ihnen einen zusammenhängenden Block arbeiten. 205 00:12:18,340 --> 00:12:21,240 Keine Lücken. Sie haben Zugriff auf jedes Byte in diesem Stück, 206 00:12:21,240 --> 00:12:26,760 Rücken an Rücken an Rücken, aber wie kann ich wissen, wo das Ende dieses Stück Erinnerung ist? 207 00:12:26,760 --> 00:12:28,850 Wenn Sie malloc? [Schüler Antwort unverständlich] Gut. 208 00:12:28,850 --> 00:12:30,670 Sie tun es nicht. Sie haben sich daran zu erinnern. 209 00:12:30,670 --> 00:12:35,960 Ich muss daran erinnern, dass ich den Wert 10 verwendet wird, und ich weiß nicht einmal zu, dass hier getan haben. 210 00:12:35,960 --> 00:12:41,000 Aber die Verantwortung liegt ausschließlich bei mir. Strlen, was wir geworden sind leicht abhängig für Streicher, 211 00:12:41,000 --> 00:12:45,860 funktioniert nur, weil dieser Konvention mit \ 0 212 00:12:45,860 --> 00:12:48,840 oder diese spezielle nul Charakter, NUL am Ende eines Strings. 213 00:12:48,840 --> 00:12:51,740 Das bedeutet nicht nur für beliebige Stücke der Erinnerung zu halten. 214 00:12:51,740 --> 00:12:58,590 Es ist bis zu Ihnen. So Zeile 20, dann ordnet ein Stück der Erinnerung 215 00:12:58,590 --> 00:13:02,590 das kann zehn Ganzzahlen speichern und speichert die Adresse des ersten Bytes 216 00:13:02,590 --> 00:13:05,610 dieses Stück Speicher in der Variablen x. 217 00:13:05,610 --> 00:13:11,140 Ergo, die ein Zeiger ist. So Linie 21 war leider ein Fehler. 218 00:13:11,140 --> 00:13:16,110 Aber zuerst, was ist das denn? Es sagt store bei Position 10, 0 indiziert, 219 00:13:16,110 --> 00:13:19,480 der Brocken Speicher abgerufen x den Wert 0. 220 00:13:19,480 --> 00:13:21,510 >> So bemerkt ein paar Dinge sind passiert. 221 00:13:21,510 --> 00:13:25,420 Auch wenn x ist ein Zeiger, von ein paar Wochen wieder zu 222 00:13:25,420 --> 00:13:29,440 Sie können immer noch die Array-style eckigen Klammern. 223 00:13:29,440 --> 00:13:36,180 Denn das ist eigentlich kurz-Hand-Notation für die mehr kryptischen aussehende Zeigerarithmetik. 224 00:13:36,180 --> 00:13:40,320 wo wir etwas tun: Nehmen Sie die Adresse x, verschieben 10 Punkte über, 225 00:13:40,320 --> 00:13:44,550 dann gehen Sie zu, was Adresse wird an dieser Stelle gespeichert. 226 00:13:44,550 --> 00:13:48,090 Aber ehrlich gesagt, das ist nur grauenhaft zu lesen und sich bequem mit. 227 00:13:48,090 --> 00:13:52,900 So die Welt verwendet in der Regel die eckigen Klammern, nur weil es so viel mehr Menschen freundlich zu lesen ist. 228 00:13:52,900 --> 00:13:55,140 Aber das ist, was wirklich vor sich geht unter der Haube; 229 00:13:55,140 --> 00:13:58,190 x ist eine Adresse, nicht ein Array an sich. 230 00:13:58,190 --> 00:14:02,410 Das ist also die Speicherung 0 bei Position 10 in x. 231 00:14:02,410 --> 00:14:06,120 Warum ist das schlecht? Yeah? 232 00:14:06,120 --> 00:14:17,370 [Schüler Antwort unverständlich] Genau. 233 00:14:17,370 --> 00:14:21,100 Wir haben nur zugeteilt zehn ints, aber wir von 0 zu zählen, wenn die Programmierung in C, 234 00:14:21,100 --> 00:14:25,690 so haben Sie Zugang zu 0 1 2 3 4 5 6 7 8 9, aber nicht 10. 235 00:14:25,690 --> 00:14:30,270 Also entweder das Programm auf seg Fehler gehen oder es ist nicht. 236 00:14:30,270 --> 00:14:32,900 Aber wir wissen nicht wirklich, das ist eine Art von nichtdeterministischen Verhalten. 237 00:14:32,900 --> 00:14:35,600 Es hängt wirklich davon ab, ob wir Glück haben. 238 00:14:35,600 --> 00:14:40,650 Wenn es sich herausstellt, dass das Betriebssystem nicht dagegen, wenn ich diesen zusätzlichen Byte verwenden, 239 00:14:40,650 --> 00:14:43,360 obwohl es nicht hat sie mir gegeben, könnte mein Programm nicht abstürzen. 240 00:14:43,360 --> 00:14:46,780 Es ist roh, sie ist fehlerhaft, aber Sie könnten nicht sehen, dass Symptom, 241 00:14:46,780 --> 00:14:48,960 oder Sie können es nur einmal in eine Weile zu sehen. 242 00:14:48,960 --> 00:14:51,230 Aber die Realität ist, dass der Fehler ist in der Tat gibt. 243 00:14:51,230 --> 00:14:54,320 Und es ist wirklich problematisch, wenn Sie ein Programm, das Sie richtig geschrieben haben, 244 00:14:54,320 --> 00:14:58,840 dass Sie das Programm verkauft, dass die Menschen mit, dass jeder einmal in eine Weile stürzt 245 00:14:58,840 --> 00:15:02,450 weil natürlich das ist nicht gut. In der Tat, wenn Sie ein Android-Handy oder ein iPhone 246 00:15:02,450 --> 00:15:05,550 und laden Sie Apps in diesen Tagen, wenn Sie jemals eine App zu beenden, 247 00:15:05,550 --> 00:15:10,040 plötzlich verschwindet, das ist fast immer das Ergebnis einer Speicher-bezogene Frage, 248 00:15:10,040 --> 00:15:12,830 wobei der Programmierer und schraubte einen Zeiger dereferenziert 249 00:15:12,830 --> 00:15:18,670 dass er oder sie sollte nicht haben, und das Ergebnis der iOS oder Android ist einfach töten das Programm insgesamt 250 00:15:18,670 --> 00:15:23,080 anstatt das Risiko einzugehen undefinierten Verhalten oder irgendeine Art von Sicherheit zu gefährden. 251 00:15:23,080 --> 00:15:25,950 >> Es gibt einen weiteren Fehler in diesem Programm neben diesem ein. 252 00:15:25,950 --> 00:15:30,180 Was habe ich in diesem Programm geschraubt? 253 00:15:30,180 --> 00:15:32,740 Ich habe nicht geübt, was ich gepredigt. Yeah? 254 00:15:32,740 --> 00:15:34,760 [Schüler Antwort unverständlich] Gut. 255 00:15:34,760 --> 00:15:36,880 Ich habe nicht den Speicher freigegeben. So die Faustregel jetzt 256 00:15:36,880 --> 00:15:43,150 muss, wenn Sie malloc aufrufen, müssen Sie rufen Sie kostenlos, wenn Sie fertig sind mit diesem Speicher. 257 00:15:43,150 --> 00:15:45,610 Jetzt würde, wenn ich will, diesen Speicher zu befreien? 258 00:15:45,610 --> 00:15:49,780 Wahrscheinlich, vorausgesetzt, diese erste Zeile korrekt war, möchte ich es hier tun. 259 00:15:49,780 --> 00:15:55,710 Da konnte ich zum Beispiel nicht, tun Sie es hier unten. Warum? 260 00:15:55,710 --> 00:15:57,860 Just out of scope. Also auch wenn wir über Zeiger reden, 261 00:15:57,860 --> 00:16:04,830 dies ist in der Woche 2 oder 3 Ausgabe, wobei x ist nur im Umfang Innenseite der geschweiften Klammern dort erklärt wurde. 262 00:16:04,830 --> 00:16:11,000 So dass Sie definitiv nicht befreien können es dort. Meine einzige Chance, es zu befreien ist etwa nach Zeile 21. 263 00:16:11,000 --> 00:16:15,170 Dies ist ein ziemlich einfaches Programm, es war ziemlich einfach, sobald Sie wickelte Art von Geist 264 00:16:15,170 --> 00:16:17,870 um das, was das Programm tut, wo die Fehler waren. 265 00:16:17,870 --> 00:16:20,500 Und selbst wenn Sie nicht sehen, es auf den ersten, hoffentlich ist es ein wenig offensichtlich jetzt 266 00:16:20,500 --> 00:16:23,870 dass diese Fehler sind ziemlich leicht zu lösen und leicht gemacht. 267 00:16:23,870 --> 00:16:28,720 Aber wenn ein Programm mehr als 12 Zeilen lang ist, ist es 50 Zeilen lang, 100 Zeilen lang, 268 00:16:28,720 --> 00:16:31,150 Spaziergang durch den Code Zeile für Zeile, durchdenken es logisch, 269 00:16:31,150 --> 00:16:35,110 ist möglich, aber nicht besonders viel Spaß, ständig auf der Suche nach Bugs, 270 00:16:35,110 --> 00:16:38,340 und es ist auch schwer zu tun, und deshalb ein Tool wie Valgrind existiert. 271 00:16:38,340 --> 00:16:40,900 Lassen Sie mich gehen Sie vor und tun dies: Lassen Sie mich öffne meine Terminal-Fenster, 272 00:16:40,900 --> 00:16:45,400 und lass mich nicht nur laufen Speicher, weil der Speicher scheint in Ordnung zu sein. 273 00:16:45,400 --> 00:16:49,180 Ich bin immer glücklich. Flugziel daß zusätzliches Byte am Ende des Arrays 274 00:16:49,180 --> 00:16:51,060 scheint nicht allzu problematisch. 275 00:16:51,060 --> 00:16:56,370 Aber lassen Sie mich dennoch tun, eine Plausibilitätsprüfung, die bedeutet nur, um zu überprüfen, 276 00:16:56,370 --> 00:16:58,320 ob dies tatsächlich stimmt. 277 00:16:58,320 --> 00:17:04,690 >> So lasst uns valgrind-v - Leck-Check = full, 278 00:17:04,690 --> 00:17:07,520 und dann den Namen des Programms in diesem Fall ist der Speicher nicht a.out. 279 00:17:07,520 --> 00:17:10,760 Also lass mich gehen Sie vor und tun dies. Drücken Sie die Eingabetaste. 280 00:17:10,760 --> 00:17:14,109 Lieber Gott. Dies ist seine Leistung, und dies ist, was ich zuvor angespielt. 281 00:17:14,109 --> 00:17:17,550 Aber, wenn Sie lernen, durch all der Unsinn hier gelesen, 282 00:17:17,550 --> 00:17:20,760 die meisten ist dies nur eine diagnostische Ausgabe, ist nicht so interessant. 283 00:17:20,760 --> 00:17:24,829 Was das Auge wirklich will gesucht werden ist jede Erwähnung von Fehlern oder ungültig. 284 00:17:24,829 --> 00:17:26,800 Worte, die Probleme vorzuschlagen. 285 00:17:26,800 --> 00:17:29,340 Und in der Tat, mal sehen, was falsch läuft hier unten. 286 00:17:29,340 --> 00:17:35,230 Ich habe eine Zusammenfassung von einer Art "im Einsatz bei Ausfahrt. 40 Byte in 1 blocks" 287 00:17:35,230 --> 00:17:38,750 Ich bin nicht wirklich sicher, was ein Block ist noch nicht, aber 40 Bytes 288 00:17:38,750 --> 00:17:41,260 fühlt sich tatsächlich wie ich herausfinden konnte, wo das herkommt ist. 289 00:17:41,260 --> 00:17:45,030 40 Byte. Warum sind 40 Byte im Einsatz an der Ausfahrt? 290 00:17:45,030 --> 00:17:48,780 Und genauer gesagt, wenn wir nach unten scrollen hier 291 00:17:48,780 --> 00:17:54,520 warum habe ich endgültig verloren 40 Byte? Yeah? 292 00:17:54,520 --> 00:17:59,520 [Schüler Antwort unverständlich] Perfect. Ja, genau. 293 00:17:59,520 --> 00:18:03,540 Es waren zehn ganze Zahlen, und jede von ihnen ist eine Größe von 4 oder 32 Bits, 294 00:18:03,540 --> 00:18:08,300 so habe ich genau 40 Byte verloren, weil, wie Sie vorgeschlagen, ich nicht angerufen haben frei. 295 00:18:08,300 --> 00:18:13,460 Das ist ein Fehler, und jetzt schauen wir uns ein wenig nach unten weiter und sehen daneben, 296 00:18:13,460 --> 00:18:16,900 "Invalid der Größe 4 zu schreiben." Nun, was ist das? 297 00:18:16,900 --> 00:18:21,150 Diese Adresse wird, was Ausgangspunkt Schreibweise ausgedrückt, offenbar? 298 00:18:21,150 --> 00:18:23,640 Dies ist hexadezimal, und zu jeder Zeit sehen Sie eine Nummer, beginnend mit 0x, 299 00:18:23,640 --> 00:18:29,410 es bedeutet hexadezimal, was wir Weg zurück in, glaube ich, pset 0-Sektion von Fragen haben, 300 00:18:29,410 --> 00:18:34,090 das war nur ein Aufwärmprogramm Übung, die Umwandlung Dezimal in Hex zu binär und so weiter. 301 00:18:34,090 --> 00:18:39,220 Hexadezimal, nur durch menschliche Konvention ist in der Regel verwendet, um Zeiger stellen 302 00:18:39,220 --> 00:18:41,570 oder, allgemeiner, adressiert. Es ist nur eine Konvention, 303 00:18:41,570 --> 00:18:45,340 weil es ein wenig leichter zu lesen ist, ist es ein wenig kompakter als so etwas wie dezimal, 304 00:18:45,340 --> 00:18:47,720 und Binär ist nutzlos für die meisten Menschen zu verwenden. 305 00:18:47,720 --> 00:18:50,840 So, jetzt, was bedeutet das? Nun, es sieht aus wie es ist ein ungültiger Schreibvorgang 306 00:18:50,840 --> 00:18:54,480 der Größe 4 on line 21 von memory.c. 307 00:18:54,480 --> 00:18:59,180 So gehen wir zurück in die Linie 21, und in der Tat, hier ist, dass ungültige schreiben. 308 00:18:59,180 --> 00:19:02,640 So Valgrind wird nicht komplett meine Hand halten und sagen Sie mir, was die Lösung ist, 309 00:19:02,640 --> 00:19:05,520 aber es ist Erkennen, dass ich tue, einen ungültigen Schreibvorgang. 310 00:19:05,520 --> 00:19:08,800 Ich berühre 4 Byte, dass ich nicht sein sollte, und anscheinend das ist, weil, 311 00:19:08,800 --> 00:19:13,960 Sie haben darauf hingewiesen, ich tue [10] anstelle von [9] maximal 312 00:19:13,960 --> 00:19:16,660 oder [0] oder etwas dazwischen. 313 00:19:16,660 --> 00:19:19,690 Mit Valgrind realisieren jederzeit du jetzt schreibst ein Programm 314 00:19:19,690 --> 00:19:24,190 die Zeiger verwendet und Speicher verwendet, und malloc genauer gesagt, 315 00:19:24,190 --> 00:19:27,080 definitiv in der Gewohnheit läuft so lange erhalten 316 00:19:27,080 --> 00:19:30,890 aber sehr leicht kopiert und das Kommando über Valgrind eingefügt 317 00:19:30,890 --> 00:19:32,650 zu sehen, ob es gibt einige Fehler drin. 318 00:19:32,650 --> 00:19:34,820 Und es wird überwältigend sein jedes Mal, wenn Sie sehen die Ausgabe, 319 00:19:34,820 --> 00:19:39,430 sondern nur durch ein visuell alle der Ausgabe analysieren und sehen, wenn Sie sehen, erwähnt von Fehlern 320 00:19:39,430 --> 00:19:43,190 oder Warnungen oder ungültig werden oder verloren gehen. 321 00:19:43,190 --> 00:19:46,200 Jedes Wort, die klingen wie Sie vermasselt irgendwo. 322 00:19:46,200 --> 00:19:48,580 So erkennen, dass es ein neues Tool in Ihrem Toolkit. 323 00:19:48,580 --> 00:19:51,270 >> Jetzt am Montag hatten wir eine ganze Reihe von Leute kommen hier 324 00:19:51,270 --> 00:19:53,150 und stellen die Vorstellung einer verketteten Liste. 325 00:19:53,150 --> 00:20:00,970 Und wir stellten die verknüpfte Liste als eine Lösung für welches Problem? 326 00:20:00,970 --> 00:20:04,590 Yeah? [Schüler Antwort unverständlich] Gut. 327 00:20:04,590 --> 00:20:06,530 Arrays können nicht haben Memory hinzugefügt werden. 328 00:20:06,530 --> 00:20:09,440 Wenn Sie reservieren ein Array der Größe 10, das ist alles, was Sie bekommen. 329 00:20:09,440 --> 00:20:13,690 Sie können eine Funktion wie realloc, wenn Sie angerufen zunächst malloc, 330 00:20:13,690 --> 00:20:17,580 und dass können versuchen, das Array wachsen, wenn es Raum in Richtung des Ende davon 331 00:20:17,580 --> 00:20:21,610 dass niemand sonst benutzt, und wenn es nicht ist, wird es nur finden Sie einen größeren Teil woanders. 332 00:20:21,610 --> 00:20:25,040 Aber dann wird es all diese Bytes in das neue Array kopiert. 333 00:20:25,040 --> 00:20:28,310 Das klingt wie eine sehr richtige Lösung. 334 00:20:28,310 --> 00:20:34,790 Warum ist das unattraktiv? 335 00:20:34,790 --> 00:20:36,940 Ich meine, es funktioniert, haben die Menschen dieses Problem gelöst. 336 00:20:36,940 --> 00:20:40,710 Warum haben wir müssen es am Montag zu lösen mit verknüpften Listen? Yeah? 337 00:20:40,710 --> 00:20:44,060 [Schüler Antwort unverständlich] Es könnte lange dauern. 338 00:20:44,060 --> 00:20:49,260 In der Tat, jedes Mal, wenn malloc oder realloc oder calloc, die noch nicht ein anderes sind, 339 00:20:49,260 --> 00:20:52,470 jedes Mal, wenn das Programm, an das Betriebssystem sprechen, 340 00:20:52,470 --> 00:20:54,310 Sie neigen dazu, das Programm zu verlangsamen. 341 00:20:54,310 --> 00:20:57,470 Und wenn du diese Art von Dingen in Schleifen, du bist wirklich zu verlangsamen. 342 00:20:57,470 --> 00:21:00,740 Du wirst doch nicht um diese für die einfachsten "Hallo Welt"-Typ Programmen bemerken, 343 00:21:00,740 --> 00:21:04,300 aber in viel größeren Programmen fragen Sie das Betriebssystem wieder und wieder für das Gedächtnis 344 00:21:04,300 --> 00:21:07,520 oder geben sie wieder und wieder neigt nicht eine gute Sache sein. 345 00:21:07,520 --> 00:21:11,210 Plus, es ist nur eine Art intellektuell - es ist eine komplette Zeitverschwendung. 346 00:21:11,210 --> 00:21:16,490 Warum dafür mehr und mehr Speicher, Risiko kopiert alles, was in das neue Array, 347 00:21:16,490 --> 00:21:21,980 Wenn Sie eine Alternative, die Sie zuordnen nur so viel Speicher, wie Sie tatsächlich benötigen lets have? 348 00:21:21,980 --> 00:21:24,130 Also gibt es Vor-und Nachteile hier. 349 00:21:24,130 --> 00:21:26,730 Einer der Pluspunkte ist jetzt, dass wir die Dynamik haben. 350 00:21:26,730 --> 00:21:29,100 Egal, wo die Stücke der Erinnerung sind, dass sind kostenlos, 351 00:21:29,100 --> 00:21:32,070 Ich kann nur von erstellen sortieren diese Semmelbrösel über Zeiger 352 00:21:32,070 --> 00:21:34,470 mein ganzes verketteten Liste aneinanderreihen. 353 00:21:34,470 --> 00:21:36,470 Aber ich zahlen mindestens ein Preis. 354 00:21:36,470 --> 00:21:40,060 >> Was muss ich aufgeben müssen, zu gewinnen verkettete Listen? 355 00:21:40,060 --> 00:21:42,470 Yeah? [Schüler Antwort unverständlich] Gut. 356 00:21:42,470 --> 00:21:45,650 Sie benötigen mehr Speicher. Jetzt brauche ich Platz für diese Zeiger, 357 00:21:45,650 --> 00:21:47,900 und im Falle dieser super einfach verkettete Liste 358 00:21:47,900 --> 00:21:51,410 das ist nur versuchen, Zahlen, die 4 Bytes zu speichern, halten wir sagen 359 00:21:51,410 --> 00:21:54,240 gut, ist ein Zeiger 4 Bytes, so jetzt habe ich buchstäblich verdoppelt 360 00:21:54,240 --> 00:21:57,290 die Menge an Speicher brauche ich nur, um diese Liste zu speichern. 361 00:21:57,290 --> 00:21:59,680 Aber auch dies ist eine Konstante Kompromiss in der Informatik 362 00:21:59,680 --> 00:22:03,440 zwischen Zeit und Raum und Entwicklung, Aufwand und andere Ressourcen. 363 00:22:03,440 --> 00:22:06,630 Was ist ein weiterer Nachteil der Verwendung einer verketteten Liste? Yeah? 364 00:22:06,630 --> 00:22:10,150 [Schüler Antwort unverständlich] 365 00:22:10,150 --> 00:22:12,600 Gut. Nicht so einfach zu erreichen. Wir können nicht mehr nutzen 366 00:22:12,600 --> 00:22:15,530 Woche 0 Prinzipien wie teile und herrsche. 367 00:22:15,530 --> 00:22:18,220 Und genauer gesagt, binäre Suche. Denn obwohl wir Menschen 368 00:22:18,220 --> 00:22:20,400 kann grob sehen, wo in der Mitte dieser Liste ist, 369 00:22:20,400 --> 00:22:25,840 der Computer nur weiß, dass diese verketteten Liste unter der Adresse genannt das erste Mal startet. 370 00:22:25,840 --> 00:22:28,250 Und das ist 0x123 oder so ähnlich. 371 00:22:28,250 --> 00:22:30,990 Und der einzige Weg das Programm finden Sie das mittlere Element 372 00:22:30,990 --> 00:22:33,350 ist, um tatsächlich die gesamte Liste. 373 00:22:33,350 --> 00:22:35,500 Und selbst dann ist es buchstäblich um die ganze Liste zu suchen, weil 374 00:22:35,500 --> 00:22:38,950 sogar einmal erreichen Sie das mittlere Element, indem Sie die Zeiger, 375 00:22:38,950 --> 00:22:42,380 Sie, das Programm, haben keine Ahnung, wie lange diese Liste ist möglicherweise auch 376 00:22:42,380 --> 00:22:45,250 bis Sie traf das Ende, und wie Sie wissen, programmatisch 377 00:22:45,250 --> 00:22:48,600 dass Sie am Ende einer verketteten Liste sind? 378 00:22:48,600 --> 00:22:51,120 Es gibt eine spezielle NULL-Zeiger, so wieder, eine Konvention. 379 00:22:51,120 --> 00:22:53,870 Anstatt diesen Zeiger verwenden wir definitiv nicht wollen, dass es einige Müll Wert 380 00:22:53,870 --> 00:22:57,750 Hinweis Bühne irgendwo, wir wollen, dass es Hand nach unten, NULL, 381 00:22:57,750 --> 00:23:01,530 so dass wir diesen Terminus in dieser Datenstruktur, so dass wir, wo es endet kennen. 382 00:23:01,530 --> 00:23:03,410 >> Was ist, wenn wir dies manipulieren wollen? 383 00:23:03,410 --> 00:23:05,980 Wir haben die meisten dieser visuell und mit Menschen, 384 00:23:05,980 --> 00:23:07,630 aber was, wenn wir eine Insertion tun? 385 00:23:07,630 --> 00:23:12,360 So die ursprüngliche Liste war 9, 17, 20, 22, 29, 34. 386 00:23:12,360 --> 00:23:16,730 Was, wenn wir wollten dann malloc Platz für Nummer 55, ein Knoten für sie, 387 00:23:16,730 --> 00:23:20,730 und dann wollen wir 55 in die Liste einzufügen, so wie wir am Montag getan hat? 388 00:23:20,730 --> 00:23:23,690 Wie machen wir das? Nun kam Anita und sie im Wesentlichen ging die Liste. 389 00:23:23,690 --> 00:23:27,500 Sie begann am ersten Element, dann die nächste, die nächste, der nächsten, am nächsten, am nächsten. 390 00:23:27,500 --> 00:23:29,500 Schließlich traf die linke den ganzen Weg hinunter 391 00:23:29,500 --> 00:23:34,480 und erkannte, oh, das ist NULL. Also, was Zeigermanipulation getan werden musste? 392 00:23:34,480 --> 00:23:37,980 Die Person, die am Ende war, Nummer 34, musste seine linke Hand erhoben 393 00:23:37,980 --> 00:23:46,220 zu Punkt 55, brauchte 55 ihren linken Arm nach unten, um die neue Nullabschlusszeichen sein. Fertig. 394 00:23:46,220 --> 00:23:49,540 Ganz einfach bis 55 in eine sortierte Liste einzufügen. 395 00:23:49,540 --> 00:23:51,800 Und wie könnte dies aussehen? 396 00:23:51,800 --> 00:23:55,690 >> Lassen Sie mich gehen Sie vor und eröffnen einen Code Beispiel hier. 397 00:23:55,690 --> 00:23:58,120 Ich werde eröffnen gedit, und lassen Sie mich eröffnen zwei Dateien zuerst. 398 00:23:58,120 --> 00:24:02,050 Eines ist list1.h, und lassen Sie mich nur daran erinnern, dass dies der Teil des Codes war 399 00:24:02,050 --> 00:24:04,920 die wir verwendet, um einen Knoten zu repräsentieren. 400 00:24:04,920 --> 00:24:13,040 Ein Knoten verfügt sowohl über einen int namens n und einen Zeiger namens Next dass nur auf die nächste Sache in der Liste. 401 00:24:13,040 --> 00:24:15,450 Das ist jetzt in einer. H-Datei. Warum? 402 00:24:15,450 --> 00:24:19,090 Es gibt diese Konvention, und wir haben nicht zunutze gemacht eine riesige Menge selbst, 403 00:24:19,090 --> 00:24:22,220 aber die Person, printf und andere Funktionen schrieb 404 00:24:22,220 --> 00:24:27,150 gab als Geschenk an die Welt all diese Funktionen, indem er eine Datei namens stdio.h. 405 00:24:27,150 --> 00:24:30,950 Und dann gibt es string.h, und dann gibt es map.h, und es gibt all diese h-Dateien 406 00:24:30,950 --> 00:24:34,410 dass Sie vielleicht gesehen oder benutzt haben während der Laufzeit von anderen Leuten geschrieben. 407 00:24:34,410 --> 00:24:38,470 Typischerweise in diesen. H Dateien sind nur Dinge wie typedefs 408 00:24:38,470 --> 00:24:42,310 oder Erklärungen von benutzerdefinierten Typen oder Deklarationen von Konstanten. 409 00:24:42,310 --> 00:24:47,890 Sie müssen nicht gestellt Funktionen 'Implementierungen in Header-Dateien. 410 00:24:47,890 --> 00:24:50,570 Sie setzen stattdessen nur ihre Prototypen. 411 00:24:50,570 --> 00:24:53,050 Sie stellen Dinge, die Sie freigeben möchten, mit der Welt, was sie brauchen 412 00:24:53,050 --> 00:24:55,640 Um zu kompilieren ihren Code. So, nur um in dieser Gewohnheit zu bekommen, 413 00:24:55,640 --> 00:24:59,110 haben wir beschlossen, das Gleiche zu tun. Es gibt nicht viel in list1.h, 414 00:24:59,110 --> 00:25:02,070 aber wir haben etwas, das von Interesse sein könnten, um Menschen setzen in der Welt 415 00:25:02,070 --> 00:25:05,030 die wollen uns verlinkten Liste Implementierung verwenden. 416 00:25:05,030 --> 00:25:08,040 Jetzt, in list1.c, werde ich nicht durch diese ganze Sache 417 00:25:08,040 --> 00:25:11,390 weil es ein bisschen lang ist, dieses Programm, aber wir führen Sie es real schnell an der Eingabeaufforderung. 418 00:25:11,390 --> 00:25:15,720 Lassen Sie mich zu kompilieren list1, lassen Sie mich dann führen list1, und was Sie sehen, ist 419 00:25:15,720 --> 00:25:18,070 wir haben simuliert ein einfaches kleines Programm hier 420 00:25:18,070 --> 00:25:20,990 das wird mir zu erlauben, hinzuzufügen und zu entfernen Nummern in einer Liste. 421 00:25:20,990 --> 00:25:24,310 Also lass mich gehen Sie vor und geben Sie 3 für das Menü Option 3. 422 00:25:24,310 --> 00:25:27,880 Ich möchte die Nummer einfügen - lasst uns die erste Zahl, die 9 war, 423 00:25:27,880 --> 00:25:30,550 und jetzt bin ich erzählte der Liste ist nun 9. 424 00:25:30,550 --> 00:25:33,760 Lassen Sie mich gehen Sie vor und das andere tun Insertion, so schlug ich Menüpunkt 3. 425 00:25:33,760 --> 00:25:36,760 Welche Nummer muss ich einfügen wollen? 17. 426 00:25:36,760 --> 00:25:39,220 Enter. Und ich werde tun, nur eine mehr. 427 00:25:39,220 --> 00:25:41,720 Lassen Sie mich die Nummer 22. 428 00:25:41,720 --> 00:25:45,850 So haben wir die Anfänge der verketteten Liste, die wir in slide hatte vor einem Augenblick. 429 00:25:45,850 --> 00:25:48,740 Wie ist das Einsetzen tatsächlich passiert? 430 00:25:48,740 --> 00:25:52,000 Tatsächlich ist 22 nun am Ende der Liste. 431 00:25:52,000 --> 00:25:55,050 So die Geschichte uns erzählt auf der Bühne am Montag und wieder verschlossen gerade jetzt 432 00:25:55,050 --> 00:25:57,460 muss tatsächlich im Code geschehen. 433 00:25:57,460 --> 00:25:59,700 Lassen Sie uns einen Blick. Lassen Sie mich nach unten scrollen in dieser Datei. 434 00:25:59,700 --> 00:26:01,720 Wir beschönigen einige der Funktionen, 435 00:26:01,720 --> 00:26:05,630 aber wir gehen, um, sagen wir, die Funktion EINFÜGEN. 436 00:26:05,630 --> 00:26:11,720 >> Lasst uns sehen, wie wir über das Einfügen eines neuen Knotens in dieser verketteten Liste zu gehen. 437 00:26:11,720 --> 00:26:14,550 Wo ist die Liste erklärt? Nun, lassen Sie blättern ganzen Weg bis an der Spitze, 438 00:26:14,550 --> 00:26:19,970 und merke, dass meine verkettete Liste im Wesentlichen als einzigen Zeiger, die zunächst NULL ist erklärt. 439 00:26:19,970 --> 00:26:23,180 Also ich bin mit einer globalen Variablen hier, was in der Regel haben wir gegen gepredigt 440 00:26:23,180 --> 00:26:25,280 denn es macht Ihren Code ein wenig chaotisch zu pflegen, 441 00:26:25,280 --> 00:26:29,080 Es ist eine Art faul, in der Regel, aber es ist nicht faul und es ist nicht falsch, und es ist nicht schlecht 442 00:26:29,080 --> 00:26:33,660 wenn Ihr Programm die einzige Aufgabe im Leben ist es, eine verknüpfte Liste zu simulieren. 443 00:26:33,660 --> 00:26:35,460 Das ist genau das, was wir tun. 444 00:26:35,460 --> 00:26:39,100 Also anstatt zu erklären dies in Haupt-und dann müssen sie auf jeden Funktion übergeben 445 00:26:39,100 --> 00:26:42,640 Wir haben in diesem Programm geschrieben, wir stattdessen erkennen, oh, lass uns einfach machen es global 446 00:26:42,640 --> 00:26:47,060 weil der ganze Zweck dieses Programms ist es eine und nur eine verkettete Liste zu demonstrieren. 447 00:26:47,060 --> 00:26:50,700 So, das fühlt sich okay. Hier sind meine Prototypen, und wir werden nicht durch alle diese gehen, 448 00:26:50,700 --> 00:26:55,800 aber ich schrieb eine Löschfunktion, eine Suchfunktion, ein Insert-Funktion und eine Traverse-Funktion. 449 00:26:55,800 --> 00:26:59,080 Aber lasst uns jetzt wieder nach unten gehen, um die Insert-Funktion 450 00:26:59,080 --> 00:27:01,490 und sehen, wie diese hier funktioniert. 451 00:27:01,490 --> 00:27:09,940 Insert ist online - here we go. 452 00:27:09,940 --> 00:27:12,850 Einfügen. Es spielt also keine Argumente, weil wir zu fragen, sind 453 00:27:12,850 --> 00:27:15,930 der Benutzer innerhalb dieser Funktion für die Nummer, die sie einfügen möchten. 454 00:27:15,930 --> 00:27:19,410 Aber zuerst, bereiten wir ihnen etwas Platz. 455 00:27:19,410 --> 00:27:22,050 Dies ist eine Art copy and paste aus dem anderen Beispiel. 456 00:27:22,050 --> 00:27:25,110 In diesem Fall waren wir Zuordnung eines int, diesmal sind wir Zuweisung eines Knotens. 457 00:27:25,110 --> 00:27:27,910 Ich weiß nicht wirklich erinnern, wie viele Bytes ein Knoten ist, aber das ist in Ordnung. 458 00:27:27,910 --> 00:27:30,460 Sizeof herausfinden können, dass für mich. 459 00:27:30,460 --> 00:27:33,340 Und warum bin ich Überprüfung auf NULL in Zeile 120? 460 00:27:33,340 --> 00:27:37,530 Was könnte schief gehen in Linie 119? Yeah? 461 00:27:37,530 --> 00:27:40,530 [Schüler Antwort unverständlich] 462 00:27:40,530 --> 00:27:43,440 Gut. Nur könnte der Fall, dass ich zu viel Speicher gestellt werden 463 00:27:43,440 --> 00:27:47,020 oder etwas nicht stimmt und das Betriebssystem nicht genügend bytes mir zu geben, 464 00:27:47,020 --> 00:27:50,640 so signalisiert er so viel durch Rücksendung NULL, und wenn ich nicht für, dass der Check 465 00:27:50,640 --> 00:27:54,710 und ich einfach blind fahren verwenden Sie die Adresse zurückgegeben, könnte es sein, NULL. 466 00:27:54,710 --> 00:27:58,400 Es könnte einige unbekannte Wert sein, nicht eine gute Sache, wenn ich - 467 00:27:58,400 --> 00:28:00,590 tatsächlich kein unbekannter Wert. Es könnte NULL sein, so will ich nicht 468 00:28:00,590 --> 00:28:02,550 zu missbrauchen und riskieren Dereferenzierung es. 469 00:28:02,550 --> 00:28:07,410 Wenn das passiert, ich habe gerade zurück und wir werden tun, wie ich es nicht wieder eine Erinnerung überhaupt. 470 00:28:07,410 --> 00:28:12,270 >> Ansonsten sage ich der Benutzer geben Sie mir eine Nummer einzufügen, rufe ich unseren alten Freund GetInt, 471 00:28:12,270 --> 00:28:15,530 und dann war die neue Syntax wir am Montag vorgestellt. 472 00:28:15,530 --> 00:28:20,320 'Newptr-> n' bedeutet, nehmen Sie die Adresse, die Sie von malloc gegeben wurden 473 00:28:20,320 --> 00:28:23,490 Erforderlich ist eine das erste Byte eines neuen Knotens Objekt, 474 00:28:23,490 --> 00:28:26,860 und dann dem Feld namens n gehen. 475 00:28:26,860 --> 00:28:35,270 Ein wenig Trivia-Frage: Dies ist äquivalent zu dem, was kryptischer Code-Zeile? 476 00:28:35,270 --> 00:28:38,110 Wie sonst hätte ich das geschrieben? Möchten Sie einen Stich nehmen? 477 00:28:38,110 --> 00:28:41,480 [Schüler Antwort unverständlich] 478 00:28:41,480 --> 00:28:44,870 Gut. Mit der. N, aber es ist nicht ganz so einfach, wie dieses. 479 00:28:44,870 --> 00:28:47,090 Was brauche ich zuerst tun? [Schüler Antwort unverständlich] 480 00:28:47,090 --> 00:28:52,730 Gut. Ich muss * newptr.n tun. 481 00:28:52,730 --> 00:28:55,610 Das ist also sagen neuen Zeiger ist offensichtlich eine Adresse. Warum? 482 00:28:55,610 --> 00:28:59,520 Da wurde es von malloc zurückgegeben. Der * newptr sagen "go there" 483 00:28:59,520 --> 00:29:02,970 und dann, wenn Sie dort sind, dann können Sie das besser vertraut. n, 484 00:29:02,970 --> 00:29:05,730 aber das sieht einfach nur ein wenig hässlich, vor allem, wenn wir Menschen zu gehen 485 00:29:05,730 --> 00:29:10,360 Zeichnen Zeiger mit Pfeilen die ganze Zeit, die Welt standardisiert auf diesen Pfeil-Notation, 486 00:29:10,360 --> 00:29:12,320 was macht genau das Gleiche. 487 00:29:12,320 --> 00:29:16,070 So verwenden Sie nur die ->-Notation, wenn das Ding auf der linken Seite ist ein Zeiger. 488 00:29:16,070 --> 00:29:18,790 Andernfalls, wenn es eine tatsächliche Struktur ist, verwenden Sie die. N. 489 00:29:18,790 --> 00:29:25,800 Und dann das: Warum muss ich newptr-> next initialisiert auf NULL? 490 00:29:25,800 --> 00:29:28,610 Wir wollen keine baumelnden linke Hand nach dem Ende der Bühne. 491 00:29:28,610 --> 00:29:31,630 Wir wollen, dass es senkrecht nach unten, was bedeutet, das Ende dieser Liste 492 00:29:31,630 --> 00:29:34,980 könnte an diesem Knoten zu sein, so dass wir besser darauf achten, es ist NULL. 493 00:29:34,980 --> 00:29:38,460 Und überhaupt, die Initialisierung Ihrer Variablen oder Ihre Daten Mitglieder und Strukturen 494 00:29:38,460 --> 00:29:40,470 etwas ist nur gute Praxis. 495 00:29:40,470 --> 00:29:45,170 Nur lassen Müll bestehen und weiterhin in der Regel gibt es bekommt man in Schwierigkeiten 496 00:29:45,170 --> 00:29:48,650 Wenn Sie vergessen, etwas später tun. 497 00:29:48,650 --> 00:29:51,590 >> Hier sind ein paar Fälle. Dies wiederum ist die Insert-Funktion, 498 00:29:51,590 --> 00:29:54,930 und das erste, was ich prüfen ist, wenn die Variable namens ersten, 499 00:29:54,930 --> 00:29:58,240 dass die globale Variable ist NULL, dh es gibt keine verketteten Liste. 500 00:29:58,240 --> 00:30:02,460 Wir haben keine Zahlen eingefügt, so ist es trivial, um diesen Strom Nummer einfügen 501 00:30:02,460 --> 00:30:05,240 in die Liste, weil es nur gehört am Anfang der Liste. 502 00:30:05,240 --> 00:30:08,100 Das war also, wenn Anita gerade stand hier allein vorgibt 503 00:30:08,100 --> 00:30:11,390 niemand war hier auf der Bühne, bis wir einen Knoten zugeordnet, 504 00:30:11,390 --> 00:30:13,940 dann konnte sie ihre Hand zum ersten Mal zu erhöhen, 505 00:30:13,940 --> 00:30:17,420 wenn alle anderen hatten auf der Bühne nach ihr kommen am Montag. 506 00:30:17,420 --> 00:30:22,900 Jetzt ist hier, das ist ein wenig Kontrolle, wo ich muss sagen, wenn der neue Knoten den Wert von n 507 00:30:22,900 --> 00:30:27,370 beträgt 00:30:29,930 Das heißt, es ist eine verknüpfte Liste, die angefangen hat. 509 00:30:29,930 --> 00:30:32,330 Es gibt mindestens ein Knoten in der Liste, aber diese neue Mann 510 00:30:32,330 --> 00:30:37,230 gehört, bevor es so, wir müssen die Dinge bewegen. 511 00:30:37,230 --> 00:30:43,450 In anderen Worten, wenn die Liste mit gerade erst begonnen hat, sagen wir, 512 00:30:43,450 --> 00:30:48,100 nur die Zahl 17, das ist das ist - eigentlich können wir dies noch deutlicher machen. 513 00:30:48,100 --> 00:30:56,010 Wenn wir beginnen unsere Geschichte mit einem Zeiger hier als erste, 514 00:30:56,010 --> 00:30:59,870 und anfangs ist es NULL, und wir die Nummer 9, 515 00:30:59,870 --> 00:31:02,510 die Zahl 9 gehört eindeutig zu Beginn der Liste. 516 00:31:02,510 --> 00:31:07,400 Also lasst uns so tun wir gerade malloced die Adresse oder die Nummer 9 und steckte es hier. 517 00:31:07,400 --> 00:31:13,170 Wenn die ersten 9 ist standardmäßig das erste Szenario diskutierten wir nur bedeutet, let Standpunkt dieser Kerl hier, 518 00:31:13,170 --> 00:31:15,790 lassen dies als NULL; jetzt haben wir die Zahl 9. 519 00:31:15,790 --> 00:31:18,280 Die nächste Zahl, die wir einfügen wollen ist 17. 520 00:31:18,280 --> 00:31:22,420 17 gehört hierher, so dass wir gehen zu müssen, einige logische Abstufung durch dies zu tun. 521 00:31:22,420 --> 00:31:26,060 Also lasst uns statt, bevor das machen wir, wir behaupten, dass wir die Zahl 8 legen wollte. 522 00:31:26,060 --> 00:31:28,650 >> Also nur der Einfachheit halber, werde ich hier ziehen. 523 00:31:28,650 --> 00:31:30,760 Aber denken Sie daran, kann malloc es fast überall setzen. 524 00:31:30,760 --> 00:31:33,460 Aber für Zeichnung willen, werde ich es hier setzen. 525 00:31:33,460 --> 00:31:38,440 So behaupten, ich habe gerade einen Knoten für die Zahl 8 zugeordnet, dies ist standardmäßig NULL. 526 00:31:38,440 --> 00:31:42,800 Was muss nun geschehen? Ein paar Dinge. 527 00:31:42,800 --> 00:31:47,090 Wir haben diesen Fehler auf der Bühne am Montag, wo wir einen Zeiger wie folgt aktualisiert, 528 00:31:47,090 --> 00:31:51,890 Dann tat dies, und dann haben wir behauptet - wir verwaiste alle anderen auf der Bühne. 529 00:31:51,890 --> 00:31:54,350 Weil Sie kann nicht - die Reihenfolge der Operationen ist hier wichtig, 530 00:31:54,350 --> 00:31:58,760 denn jetzt haben wir diese Knoten 9, die gerade ist eine Art im Raum schwebend verloren. 531 00:31:58,760 --> 00:32:01,150 Das war also nicht der richtige Ansatz am Montag. 532 00:32:01,150 --> 00:32:03,330 Wir müssen zuerst noch etwas anderes zu tun. 533 00:32:03,330 --> 00:32:06,280 Der Zustand der Welt sieht wie folgt aus. Anfänglich hat 8 zugeordnet. 534 00:32:06,280 --> 00:32:10,550 Was wäre ein besserer Weg, Einfügen 8 sein? 535 00:32:10,550 --> 00:32:14,720 Statt der Aktualisierung dieses Zeigers erste, aktualisieren Sie einfach diese hier statt. 536 00:32:14,720 --> 00:32:17,720 Also brauchen wir eine Codezeile, werde diese NULL-Zeichen wiederum ist 537 00:32:17,720 --> 00:32:22,020 in eine tatsächliche Zeiger, der am Knoten 9 zeigt ist, 538 00:32:22,020 --> 00:32:27,970 und dann können wir sicher zuerst ändern an dieser Kerl hier zeigen. 539 00:32:27,970 --> 00:32:31,330 Jetzt haben wir eine Liste, eine verkettete Liste, aus zwei Elementen. 540 00:32:31,330 --> 00:32:33,580 Und was bedeutet das eigentlich, wie hier zu sehen? 541 00:32:33,580 --> 00:32:36,900 Wenn wir auf den Code schauen, bemerken, dass ich genau das getan. 542 00:32:36,900 --> 00:32:41,970 Ich habe gesagt, newptr, und in dieser Geschichte, newptr wurde bei dieser Kerl zeigt. 543 00:32:41,970 --> 00:32:45,520 >> Also lass mich ziehen eine weitere Sache, und ich sollte ein wenig mehr Raum für diese verlassen haben. 544 00:32:45,520 --> 00:32:48,540 So vergeben die winzig kleine Zeichnung. 545 00:32:48,540 --> 00:32:52,140 Dieser Kerl wird als newptr. 546 00:32:52,140 --> 00:32:57,940 Das ist die Variable, die wir erklärt, ein paar Zeilen zuvor in line - knapp über 25. 547 00:32:57,940 --> 00:33:03,430 Und es ist bis 8 zeigt. Also, wenn ich newptr-> next sagen, dass bedeutet, gehen Sie zu der Struktur 548 00:33:03,430 --> 00:33:07,910 das ist, die bei von newptr hingewiesen, so sind wir hier, dorthin zu gehen. 549 00:33:07,910 --> 00:33:13,990 Dann wird der Pfeil sagen Sie das nächste Feld, und dann die = sagt gestellt, welchen Wert es? 550 00:33:13,990 --> 00:33:17,280 Der Wert, der in der ersten war, welchen Wert war zuerst da? 551 00:33:17,280 --> 00:33:21,930 Zunächst wurde an diesem Knoten zeigt, so dass bedeutet dies sollte nun an diesem Knoten zeigen. 552 00:33:21,930 --> 00:33:25,660 In anderen Worten, sieht, was allerdings eine lächerliche Verwirrung mit meiner Handschrift, 553 00:33:25,660 --> 00:33:28,620 was ist eine einfache Idee, nur bewegen diese Pfeile um 554 00:33:28,620 --> 00:33:31,560 übersetzt den Code genau mit diesem Einzeiler. 555 00:33:31,560 --> 00:33:38,110 Bewahren, was in erster in das nächste Feld und aktualisieren Sie dann, was zuerst tatsächlich ist. 556 00:33:38,110 --> 00:33:40,900 Lassen Sie uns weiter und schneller vorwärts gehen einige davon, 557 00:33:40,900 --> 00:33:44,220 und nur schauen Sie sich diese tail Einsetzen für jetzt. 558 00:33:44,220 --> 00:33:51,210 Angenommen, ich bis zu dem Punkt, wo ich finde, dass das nächste Feld eines Knotens NULL bekommen. 559 00:33:51,210 --> 00:33:53,410 Und an diesem Punkt in der Geschichte, ein Detail, dass ich beschönigen 560 00:33:53,410 --> 00:33:58,170 ist, dass ich einen weiteren Zeiger eingeführt hier in Zeile 142, Vorgänger Zeiger. 561 00:33:58,170 --> 00:34:01,320 Im wesentlichen an diesem Punkt in der Geschichte, wenn die Liste erhält lang, 562 00:34:01,320 --> 00:34:04,800 Ich Art brauchen, um es mit zwei Fingern zu gehen, denn wenn ich zu weit gehen, 563 00:34:04,800 --> 00:34:08,219 Speichern in einer Single-length-Liste können Sie nicht rückwärts gehen. 564 00:34:08,219 --> 00:34:13,659 So diese Idee predptr ist meine linken Finger und newptr - nicht newptr. 565 00:34:13,659 --> 00:34:17,199 Ein weiterer Zeiger, hier ist meine andere Finger, und ich bin einfach Art des Gehens auf der Liste. 566 00:34:17,199 --> 00:34:22,179 Deshalb ist, was existiert. Aber lassen Sie berücksichtigen nur eine der einfacheren Fälle hier. 567 00:34:22,179 --> 00:34:26,620 Wenn dieses Zeigers nächste Feld ist NULL, was ist der logische Implikation? 568 00:34:26,620 --> 00:34:30,840 Wenn Sie durchqueren diese Liste sind und Sie treffen einen NULL-Zeiger? 569 00:34:30,840 --> 00:34:35,780 Du bist am Ende der Liste, und so wird der Code dann hängen diese ein zusätzliches Element 570 00:34:35,780 --> 00:34:41,230 ist eine Art der intuitiven nehmen, dass Knoten, dessen nächste Zeiger NULL ist, 571 00:34:41,230 --> 00:34:46,120 so ist dies derzeit NULL, und zu verändern, obwohl, um die Adresse des neuen Knotens ist. 572 00:34:46,120 --> 00:34:52,260 So sind wir nur Zeichnen im Code auf den Pfeil, dass wir auf der Bühne machte, indem jemand mit der linken Hand. 573 00:34:52,260 --> 00:34:54,070 >> Und der Fall, dass ich meine Hände jetzt winken, 574 00:34:54,070 --> 00:34:58,020 nur weil ich denke, es ist leicht verirren, wenn wir es in dieser Art von Umgebung zu tun, 575 00:34:58,020 --> 00:35:00,600 zum Einsetzen in der Liste der mittleren überprüfen. 576 00:35:00,600 --> 00:35:03,220 Aber gerade intuitiv, muss was passieren, wenn Sie herausfinden möchten, 577 00:35:03,220 --> 00:35:06,600 wo einige Zahl in der Mitte gehört, Sie zu tun haben, ihn zu gehen 578 00:35:06,600 --> 00:35:09,510 mit mehr als einem Finger, mehrere Zeiger, 579 00:35:09,510 --> 00:35:12,920 herauszufinden, wo es durch Überprüfung gehört, ist das Element 00:35:15,450 > Die aktuelle ein, und sobald Sie diesen Ort, 581 00:35:15,450 --> 00:35:20,400 dann müssen Sie diese Art von Hütchenspiel tun, wo man die Zeiger bewegen sehr sorgfältig. 582 00:35:20,400 --> 00:35:23,850 Und die Antwort, wenn Sie möchten die Vernunft durch diese wie zu Hause auf eigene Faust, 583 00:35:23,850 --> 00:35:28,340 läuft darauf hinaus, nur um diese beiden Zeilen Code, aber die Reihenfolge dieser Zeilen ist super wichtig. 584 00:35:28,340 --> 00:35:31,390 Denn wenn man jemandem die Hand sinken und heben jemand anderes in der falschen Reihenfolge, 585 00:35:31,390 --> 00:35:34,580 wieder, könnten Sie am Ende Verwaisung der Liste. 586 00:35:34,580 --> 00:35:39,500 Um mehr konzeptionell fassen, ist das Einfügen am Heck relativ einfach. 587 00:35:39,500 --> 00:35:42,940 Das Einsetzen an der Spitze ist auch relativ einfach, 588 00:35:42,940 --> 00:35:45,580 aber Sie müssen zu aktualisieren Ein zusätzliches Indiz diesmal 589 00:35:45,580 --> 00:35:47,930 die Nummer 5 in der Liste hier zu quetschen, 590 00:35:47,930 --> 00:35:51,560 und dann Einfügen in der Mitte geht noch mehr Aufwand, 591 00:35:51,560 --> 00:35:56,130 sehr sorgfältig die Nummer 20 in der richtigen Position, 592 00:35:56,130 --> 00:35:58,350 welches zwischen 17 und 22. 593 00:35:58,350 --> 00:36:02,700 Sie müssen also so etwas wie die neuen Knoten 20 auf 22 zu tun, 594 00:36:02,700 --> 00:36:08,470 und dann muss die Knoten Zeiger auf aktualisierte letzten werden? 595 00:36:08,470 --> 00:36:10,630 Es ist 17, um tatsächlich einfügen. 596 00:36:10,630 --> 00:36:14,080 Also noch einmal, ich werde aufschieben den eigentlichen Code für die jeweilige Umsetzung. 597 00:36:14,080 --> 00:36:17,280 >> Auf den ersten Blick ist es ein wenig überwältigend, aber es ist wirklich nur eine Endlosschleife 598 00:36:17,280 --> 00:36:21,770 Das ist Looping, Looping, Looping, Looping und brechen, sobald Sie die NULL-Zeiger getroffen, 599 00:36:21,770 --> 00:36:24,590 an welcher Stelle Sie tun können, die erforderliche Insertion. 600 00:36:24,590 --> 00:36:30,960 Dies also ist repräsentativ verketteten Liste Platzhalter-Code. 601 00:36:30,960 --> 00:36:34,590 Das war eine Art viel, und es fühlt sich an, wie wir ein Problem gelöst haben, 602 00:36:34,590 --> 00:36:36,940 aber wir haben eine ganze andere eingeführt. Ehrlich gesagt, haben wir die ganze Zeit verbracht 603 00:36:36,940 --> 00:36:40,540 auf großen O und Ω und Laufzeit, versuchen, Probleme schneller zu lösen, 604 00:36:40,540 --> 00:36:43,270 und hier sind wir einen großen Schritt nach hinten, spürt es. 605 00:36:43,270 --> 00:36:45,380 Und noch, wenn das Ziel ist, Daten zu speichern, 606 00:36:45,380 --> 00:36:48,010 es fühlt sich an wie der Heilige Gral, wie wir am Montag sagte, wäre wirklich 607 00:36:48,010 --> 00:36:50,470 die Dinge sofort zu speichern. 608 00:36:50,470 --> 00:36:53,930 >> In der Tat annehmen, dass wir beiseite verketteten Liste für einen Moment tat 609 00:36:53,930 --> 00:36:56,000 und wir stattdessen führte den Begriff einer Tabelle. 610 00:36:56,000 --> 00:36:59,110 Und lasst uns einfach eine Tabelle denken Sie einen Moment als ein Array. 611 00:36:59,110 --> 00:37:03,790 Dieses Array und dieser Fall hier hat rund 26 Elementen, 0 bis 25, 612 00:37:03,790 --> 00:37:07,940 und annehmen, dass Sie einige Brocken Speicher benötigt für Namen: 613 00:37:07,940 --> 00:37:10,350 Alice und Bob und Charlie und dergleichen. 614 00:37:10,350 --> 00:37:12,880 Und Sie brauchen etwas Datenstruktur um diese Namen zu speichern. 615 00:37:12,880 --> 00:37:15,000 Nun, man könnte so etwas wie eine verkettete Liste 616 00:37:15,000 --> 00:37:20,260 und man konnte die Liste einfügen Alice, bevor Bob und Charlie nach Bob gehen und so weiter. 617 00:37:20,260 --> 00:37:23,850 Und in der Tat, wenn Sie wollen, um Code so wie Nebenbei sehen 618 00:37:23,850 --> 00:37:27,230 wissen, dass in list2.h wir genau das tun. 619 00:37:27,230 --> 00:37:30,610 Wir werden nicht durch diesen Code zu gehen, aber dies ist eine Variante des ersten Beispiels 620 00:37:30,610 --> 00:37:34,640 das stellt einen weiteren struct wir vor genannten Studenten gesehen habe, 621 00:37:34,640 --> 00:37:40,330 und dann, was es eigentlich speichert in der verketteten Liste ist ein Zeiger auf einen Studenten-Struktur 622 00:37:40,330 --> 00:37:44,520 anstelle eines einfachen kleinen Integer, n ist. 623 00:37:44,520 --> 00:37:46,900 So klar es gibt Codes gibt, beinhaltet eigentlichen Strings, 624 00:37:46,900 --> 00:37:49,940 aber wenn das Ziel bei der Hand nun wirklich ist, die Effizienz Problem anzugehen, 625 00:37:49,940 --> 00:37:53,380 Wäre es nicht schön, wenn wir ein Objekt namens Alice sind gegeben, 626 00:37:53,380 --> 00:37:56,020 Wir wollen sie in der richtigen Stelle in einer Datenstruktur setzen, 627 00:37:56,020 --> 00:37:58,860 es fühlt sich an, wie es sein würde wirklich schön, nur legte Alice, 628 00:37:58,860 --> 00:38:01,180 deren Name mit A, in der ersten Lage. 629 00:38:01,180 --> 00:38:05,270 Und Bob, deren Name mit B, in der zweiten Lage. 630 00:38:05,270 --> 00:38:09,580 Mit einem Array oder fangen wir nennen es eine Tabelle, eine Hash-Tabelle an, dass 631 00:38:09,580 --> 00:38:13,650 können wir genau das tun. Wenn wir einen Namen wie Alice gegeben, 632 00:38:13,650 --> 00:38:16,700 eine Zeichenkette, wie Alice, weiß, wo du A-l-i-c-e? 633 00:38:16,700 --> 00:38:20,540 Wir brauchen eine hueristic. Wir brauchen eine Funktion, um eine Eingabe wie Alice nehmen 634 00:38:20,540 --> 00:38:24,610 und gibt eine Antwort, "Put Alice an dieser Stelle." 635 00:38:24,610 --> 00:38:28,720 Und diese Funktion, diese black box, wird als eine Hash-Funktion sein. 636 00:38:28,720 --> 00:38:32,330 >> Eine Hash-Funktion ist etwas, das einen Eingang hat, wie "Alice", 637 00:38:32,330 --> 00:38:38,080 und kehrt, dann typischerweise die numerische Position in irgendeiner Datenstruktur wo Alice gehört. 638 00:38:38,080 --> 00:38:40,830 In diesem Fall sollten Sie unsere Hash-Funktion relativ einfach sein. 639 00:38:40,830 --> 00:38:47,510 Unsere Hash-Funktion sollte sagen, wenn Sie "Alice", die Figur, die ich zu kümmern sollte gegeben werden? 640 00:38:47,510 --> 00:38:55,660 Die erste. So sehe ich [0], und dann sage ich, wenn [0] Zeichen A, wieder die Nummer 0. 641 00:38:55,660 --> 00:39:01,130 Wenn es B ist, kehren ein. Wenn es C, zurückzukehren 2, und so weiter. 642 00:39:01,130 --> 00:39:05,940 Alle 0 Index, und das würde mir erlauben, Alice und dann Bob und dann Charlie einfügen und so weiter 643 00:39:05,940 --> 00:39:10,960 in diese Datenstruktur. Aber es gibt ein Problem. 644 00:39:10,960 --> 00:39:13,060 Was passiert, wenn Anita kommt wieder? 645 00:39:13,060 --> 00:39:17,510 Wohin mit Anita? Ihr Name auch mit dem Buchstaben A, 646 00:39:17,510 --> 00:39:20,330 und es fühlt sich wie wir ein noch größeres Durcheinander von diesem Problem gemacht haben. 647 00:39:20,330 --> 00:39:24,380 Wir haben jetzt unmittelbaren Insertion, konstante Zeit Insertion, in eine Datenstruktur 648 00:39:24,380 --> 00:39:27,100 anstatt Worst-Case-linear, 649 00:39:27,100 --> 00:39:29,510 aber was können wir mit Anita zu tun in diesem Fall? 650 00:39:29,510 --> 00:39:34,110 Was sind die zwei Optionen, wirklich? Yeah? 651 00:39:34,110 --> 00:39:37,410 [Schüler Antwort unverständlich] Okay, so konnten wir eine weitere Dimension haben. 652 00:39:37,410 --> 00:39:42,320 Das ist gut. So können wir bauen Dinge in 3D, wie wir darüber gesprochen, mündlich am Montag. 653 00:39:42,320 --> 00:39:46,700 Wir könnten einen anderen Zugangspunkt hier hinzufügen, aber angenommen, dass keine, ich versuche zu halten so einfach. 654 00:39:46,700 --> 00:39:50,160 Das ganze Ziel ist hier die sofortige konstanter Zeit Zugriff haben, 655 00:39:50,160 --> 00:39:52,170 Also das ist zu viel Komplexität hinzuzufügen. 656 00:39:52,170 --> 00:39:55,970 Was sind andere Optionen beim Versuch, Anita in diese Datenstruktur einfügen? Yeah? 657 00:39:55,970 --> 00:39:58,610 [Schüler Antwort unverständlich] Gut. So konnten wir alle anderen nach unten zu bewegen, 658 00:39:58,610 --> 00:40:03,040 wie Charlie stößt sich Bob und Alice, und dann haben wir Anita, wo sie wirklich will zu sein. 659 00:40:03,040 --> 00:40:05,660 >> Natürlich, jetzt gibt es ein Nebeneffekt. 660 00:40:05,660 --> 00:40:09,000 Diese Datenstruktur ist wahrscheinlich sinnvoll, nicht weil wir die Menschen legen einmal wollen 661 00:40:09,000 --> 00:40:11,250 sondern weil wir wollen prüfen, ob sie später dort sind 662 00:40:11,250 --> 00:40:13,600 wenn wir drucken alle Namen in der Datenstruktur wollen. 663 00:40:13,600 --> 00:40:15,850 Wir werden etwas mit diesen Daten schließlich tun. 664 00:40:15,850 --> 00:40:20,810 So jetzt haben wir Art über Alice, die nicht mehr ist, wo sie sein soll geschraubt. 665 00:40:20,810 --> 00:40:23,880 Auch ist Bob, noch ist Charlie. 666 00:40:23,880 --> 00:40:26,060 Also vielleicht ist dies nicht so eine gute Idee. 667 00:40:26,060 --> 00:40:28,830 Aber in der Tat ist dies eine Option. Wir konnten zu verlagern jeden nieder, 668 00:40:28,830 --> 00:40:32,240 oder Heck, Anita spät gekommen, um das Spiel, warum nicht wir haben gerade Anita 669 00:40:32,240 --> 00:40:35,870 nicht hier, nicht hier, nicht hier, lass uns einfach legte ein wenig tiefer in der Liste. 670 00:40:35,870 --> 00:40:38,680 Aber dann dieses Problem beginnt wieder zu übergehen. 671 00:40:38,680 --> 00:40:41,630 Sie könnten in der Lage sein Alice finden sofort, basierend auf ihren Vornamen. 672 00:40:41,630 --> 00:40:44,320 Und Bob sofort, und Charlie. Aber dann schauen Sie für Anita, 673 00:40:44,320 --> 00:40:46,360 und du, hmm sehen, ist Alice im Weg. 674 00:40:46,360 --> 00:40:48,770 Nun, lassen Sie mich unter Alice überprüfen. Bob ist nicht Anita. 675 00:40:48,770 --> 00:40:51,850 Charlie ist nicht Anita. Oh, da ist Anita. 676 00:40:51,850 --> 00:40:54,720 Und wenn Sie weiterhin den Zug der Logik den ganzen Weg, 677 00:40:54,720 --> 00:41:00,690 was ist das Worst-Case-Laufzeit finden oder Einfügen von Anita in diese neue Datenstruktur? 678 00:41:00,690 --> 00:41:03,280 Es ist O (n), nicht wahr? 679 00:41:03,280 --> 00:41:06,280 Denn im schlimmsten Fall gibt es Alice, Bob, Charlie. . . 680 00:41:06,280 --> 00:41:10,150 den ganzen Weg hinunter jemandem namens "Y", so gibt es nur einen Ort verlassen. 681 00:41:10,150 --> 00:41:13,950 Zum Glück haben wir keine sogenannte "Z", so stellen wir Anita ganz unten. 682 00:41:13,950 --> 00:41:16,040 >> Wir haben nicht wirklich das Problem gelöst. 683 00:41:16,040 --> 00:41:19,890 Also vielleicht brauchen wir diese dritte Dimension vorzustellen. 684 00:41:19,890 --> 00:41:22,230 Und es stellt sich heraus, wenn wir diese dritte Dimension eingeführt haben, 685 00:41:22,230 --> 00:41:25,240 Wir können dies nicht perfekt, aber der Heilige Gral wird bekommen 686 00:41:25,240 --> 00:41:28,370 konstanter Zeit Einsetzen und dynamische Einfügungen, so dass 687 00:41:28,370 --> 00:41:30,960 haben wir nicht zu hart-Code ein Array der Größe 26. 688 00:41:30,960 --> 00:41:34,400 Wir können so viele Namen einzufügen, wie wir wollen, aber wir nehmen unsere 5-minütige Pause hier 689 00:41:34,400 --> 00:41:38,790 und dann tun, richtig. 690 00:41:38,790 --> 00:41:46,020 Gut. Ich habe die Geschichte bis ziemlich künstlich gibt 691 00:41:46,020 --> 00:41:48,670 indem Alice und dann Bob und dann Charlie und dann Anita, 692 00:41:48,670 --> 00:41:51,000 dessen Name offenbar werde, um mit Alice kollidieren. 693 00:41:51,000 --> 00:41:54,120 Aber die Frage, die wir am Montag endete mit ist nur, wie wahrscheinlich ist es, 694 00:41:54,120 --> 00:41:56,370 Sie würde diese Art von Kollisionen? Mit anderen Worten, 695 00:41:56,370 --> 00:42:00,490 wenn wir diese tabellarische Struktur zu verwenden beginnen, ist das wirklich nur ein Array, 696 00:42:00,490 --> 00:42:02,460 in diesem Fall von 26 Zielen, 697 00:42:02,460 --> 00:42:05,740 was ist, wenn unsere Eingänge statt gleichmäßig verteilt sind? 698 00:42:05,740 --> 00:42:09,620 Es ist nicht künstlich Alice und Bob und Charlie und David usw. alphabetisch 699 00:42:09,620 --> 00:42:12,380 es ist gleichmäßig über A bis Z. verteilt 700 00:42:12,380 --> 00:42:15,220 >> Vielleicht werden wir einfach Glück, und wir gehen nicht zwei A-oder zwei B haben 701 00:42:15,220 --> 00:42:17,640 mit sehr hoher Wahrscheinlichkeit, sondern als jemand darauf hingewiesen, 702 00:42:17,640 --> 00:42:20,730 wenn wir verallgemeinerte dieses Problem und nicht von 0 bis 25 703 00:42:20,730 --> 00:42:26,060 sondern etwa 0 bis 364 bzw. 65, oft die Anzahl der Tage in einem typischen Jahr 704 00:42:26,060 --> 00:42:31,170 und stellte die Frage: "Was ist die Wahrscheinlichkeit, dass zwei von uns in diesem Raum am gleichen Tag Geburtstag haben?" 705 00:42:31,170 --> 00:42:34,600 Anders ausgedrückt, was ist die Wahrscheinlichkeit, dass zwei von uns einen Namen beginnend mit A haben? 706 00:42:34,600 --> 00:42:37,190 Die Art der Anfrage ist dieselbe, aber das Adressraum, 707 00:42:37,190 --> 00:42:39,940 Dieses Suchraums, größer ist im Falle von Geburtstagen 708 00:42:39,940 --> 00:42:42,820 weil wir so viele Tage im Jahr als Buchstaben im Alphabet. 709 00:42:42,820 --> 00:42:44,910 Was ist die Wahrscheinlichkeit einer Kollision? 710 00:42:44,910 --> 00:42:48,410 Nun, wir können dies durch die herauszufinden, die Mathematik in die entgegengesetzte Richtung zu denken. 711 00:42:48,410 --> 00:42:50,580 Was ist die Wahrscheinlichkeit, dass keine Kollisionen? 712 00:42:50,580 --> 00:42:53,970 Nun, sagt dieser Ausdruck hier, dass, was die Wahrscheinlichkeit ist 713 00:42:53,970 --> 00:42:58,770 wenn es nur eine Person in diesem Raum, dass sie eine einzigartige Geburtstag haben? 714 00:42:58,770 --> 00:43:01,190 Es ist 100%. Denn wenn es nur eine Person im Raum, 715 00:43:01,190 --> 00:43:03,940 seinen Geburtstag kann jeder der 365 Tage aus dem Jahr. 716 00:43:03,940 --> 00:43:08,650 So 365/365 Optionen gibt mir einen Wert von 1. 717 00:43:08,650 --> 00:43:11,250 So ist die Wahrscheinlichkeit, in Frage im Moment ist nur 1. 718 00:43:11,250 --> 00:43:13,270 Aber wenn es eine zweite Person im Zimmer, 719 00:43:13,270 --> 00:43:16,490 was ist die Wahrscheinlichkeit, dass ihr Geburtstag anders ist? 720 00:43:16,490 --> 00:43:20,680 Es gibt nur 364 möglichen Tag, ignorieren Schaltjahre, 721 00:43:20,680 --> 00:43:23,580 für ihren Geburtstag nicht mit den anderen Personen kollidieren. 722 00:43:23,580 --> 00:43:31,920 So 364/365. Wenn eine dritte Person kommt, ist es 363/365, und so weiter. 723 00:43:31,920 --> 00:43:35,790 So halten wir miteinander multipliziert diese Fraktionen, die werden immer kleiner und kleiner, 724 00:43:35,790 --> 00:43:40,720 um herauszufinden, was ist die Wahrscheinlichkeit, dass alle von uns einzigartig Geburtstage haben? 725 00:43:40,720 --> 00:43:43,570 Aber dann können wir natürlich, nehmen Sie nur diese Antwort und drehen es um 726 00:43:43,570 --> 00:43:47,210 und tun 1 minus alle, dass ein Ausdruck wir schließlich bekommen werde 727 00:43:47,210 --> 00:43:51,250 Wenn Sie die Rückseite Ihrer math Pfund erinnern, es sieht ein wenig so etwas wie dieses, 728 00:43:51,250 --> 00:43:54,590 das ist viel leichter interpretiert grafisch dargestellt. 729 00:43:54,590 --> 00:43:57,820 Und diese Grafik hat hier auf der x-Achse die Anzahl der Geburtstage, 730 00:43:57,820 --> 00:44:02,030 oder die Anzahl der Personen mit Geburtstage und auf der y-Achse ist die Wahrscheinlichkeit einer Übereinstimmung. 731 00:44:02,030 --> 00:44:06,060 Und was das sagt, ist, dass wenn man, sagen wir, auch, 732 00:44:06,060 --> 00:44:10,860 wählen wir so etwas wie 22, 23. 733 00:44:10,860 --> 00:44:13,160 Wenn es 22 oder 23 Leute im Raum, 734 00:44:13,160 --> 00:44:17,100 die Wahrscheinlichkeit, dass zwei von diesen nur sehr wenige Menschen gehen, um am gleichen Tag Geburtstag haben 735 00:44:17,100 --> 00:44:19,560 ist eigentlich super high, kombinatorisch. 736 00:44:19,560 --> 00:44:23,450 50% Wahrscheinlichkeit, dass in einer Klasse mit nur 22 Personen, ein Seminar, praktisch, 737 00:44:23,450 --> 00:44:25,790 2 von diesen Leuten gehen, um am gleichen Tag Geburtstag haben. 738 00:44:25,790 --> 00:44:28,520 Denn es gibt so viele Möglichkeiten, wie Sie am gleichen Tag Geburtstag haben. 739 00:44:28,520 --> 00:44:31,110 Noch schlimmer ist, wenn man sich an der rechten Seite des Diagramms, 740 00:44:31,110 --> 00:44:34,040 durch die Zeit, Sie haben eine Klasse mit 58 Schülern in ihr, 741 00:44:34,040 --> 00:44:39,270 die Wahrscheinlichkeit von 2 Personen einen Geburtstag ist super, super hoch, fast 100%. 742 00:44:39,270 --> 00:44:41,880 Nun, das ist eine Art von Spaß Tatsache über das wahre Leben. 743 00:44:41,880 --> 00:44:45,850 >> Aber die Auswirkungen, jetzt, für Datenstrukturen und Speicherung von Informationen 744 00:44:45,850 --> 00:44:51,100 bedeutet, dass nur vorausgesetzt, Sie haben eine schöne, saubere, gleichmäßige Verteilung von Daten 745 00:44:51,100 --> 00:44:53,650 und Sie haben einen groß genug Array ein paar Dinge passen 746 00:44:53,650 --> 00:44:59,360 bedeutet nicht, dass du gehst, um Menschen in einzigartigen Orten zu bekommen. 747 00:44:59,360 --> 00:45:03,810 Du wirst Kollisionen haben. So diese Vorstellung von Hashing, wie es heißt, 748 00:45:03,810 --> 00:45:07,450 unter einen Eingang wie "Alice" und massiert es in irgendeiner Weise 749 00:45:07,450 --> 00:45:10,190 und dann immer wieder eine Antwort wie 0 oder 1 oder 2. 750 00:45:10,190 --> 00:45:17,500 Kommen wir zurück eine Ausgabe Aus dieser Funktion wird durch diese Kollisionswahrscheinlichkeit geplagt. 751 00:45:17,500 --> 00:45:19,530 Also, wie können wir damit umgehen, diese Kollisionen? 752 00:45:19,530 --> 00:45:21,940 Nun, auf dem einen Fall, können wir die Idee, dass vorgeschlagen wurde. 753 00:45:21,940 --> 00:45:25,100 Wir können nur zu verlagern jeden nieder, oder vielleicht ein wenig einfacher, 754 00:45:25,100 --> 00:45:29,870 anstatt sich alle anderen, lasst uns einfach bewegen Anita auf den Grund des zur Verfügung stehenden Platz. 755 00:45:29,870 --> 00:45:32,810 Also, wenn Alice ist in 0, Bob in 1 ist, ist Charlie in 2, 756 00:45:32,810 --> 00:45:35,260 wir gerade auf Anita an Position 3. 757 00:45:35,260 --> 00:45:38,860 Und dies ist eine Technik, bei Datenstrukturen als lineares Sondieren. 758 00:45:38,860 --> 00:45:41,310 Linear weil man nur zu Fuß diese Zeile, und du bist Art von Probing 759 00:45:41,310 --> 00:45:43,640 verfügbaren Stellen in der Datenstruktur. 760 00:45:43,640 --> 00:45:46,210 Natürlich zufällt dies in O (n). 761 00:45:46,210 --> 00:45:49,590 Wenn die Datenstruktur ist wirklich voll ist, gibt es 25 Leute in es schon, 762 00:45:49,590 --> 00:45:54,120 und dann Anita entlang kommt, endet sie an, was würde location Z sein, und das ist in Ordnung. 763 00:45:54,120 --> 00:45:56,540 Sie passt immer noch, und wir können sie später zu finden. 764 00:45:56,540 --> 00:46:00,100 >> Aber das war im Gegensatz zu dem Ziel der Beschleunigung Dinge. 765 00:46:00,100 --> 00:46:02,530 So was, wenn wir stattdessen führte diese dritte Dimension? 766 00:46:02,530 --> 00:46:06,400 Diese Technik wird allgemein als getrennte Verkettung oder mit Ketten. 767 00:46:06,400 --> 00:46:10,030 Und was für eine Hash-Tabelle ist jetzt, diese tabellarische Struktur, 768 00:46:10,030 --> 00:46:13,450 Ihr Tisch ist nur ein Array von Zeigern. 769 00:46:13,450 --> 00:46:18,230 Aber was diese Zeiger auf ist guess what? 770 00:46:18,230 --> 00:46:21,970 Eine verkettete Liste. So was passiert, wenn wir das Beste aus beiden Welten? 771 00:46:21,970 --> 00:46:26,500 Wir verwenden Arrays für die ersten Indizes 772 00:46:26,500 --> 00:46:32,070 in die Datenstruktur so können wir sofort auf [0] [1], [30] oder so weiter gehen, 773 00:46:32,070 --> 00:46:36,480 aber so, dass wir eine gewisse Flexibilität, und wir können Anita und Alice und Adam passen 774 00:46:36,480 --> 00:46:38,630 und andere Ein Name, 775 00:46:38,630 --> 00:46:43,470 wir stattdessen ließ die andere Achse beliebig wachsen. 776 00:46:43,470 --> 00:46:47,340 Und wir schließlich ab Montag, haben diese Möglichkeiten des Ausdrucks mit verknüpften Liste. 777 00:46:47,340 --> 00:46:49,530 Wir können eine Datenstruktur beliebig wachsen. 778 00:46:49,530 --> 00:46:52,450 Alternativ könnten wir nur einen großen 2-dimensionalen Array, 779 00:46:52,450 --> 00:46:57,190 aber das geht zu einer schrecklichen Situation, wenn eine der Zeilen in einem 2-dimensionalen Array 780 00:46:57,190 --> 00:47:01,280 ist nicht groß genug für die zusätzliche Person, deren Name zufällig mit A beginnen 781 00:47:01,280 --> 00:47:04,200 Gott bewahre, müssen wir eine riesige 2-dimensional umverteilen 782 00:47:04,200 --> 00:47:06,600 nur weil es so viele Menschen mit dem Namen A, 783 00:47:06,600 --> 00:47:09,480 vor allem, wenn es so wenige Menschen namens Z etwas. 784 00:47:09,480 --> 00:47:12,170 Es ist gerade dabei, eine sehr spärliche Daten-Struktur sein. 785 00:47:12,170 --> 00:47:15,400 So ist es nicht perfekt mit allen Mitteln, aber jetzt haben wir wenigstens die Möglichkeit haben 786 00:47:15,400 --> 00:47:19,090 um sofort herauszufinden, wo Alice oder Anita gehört, 787 00:47:19,090 --> 00:47:21,090 zumindest hinsichtlich der vertikalen Achse, 788 00:47:21,090 --> 00:47:25,850 und dann müssen wir nur noch zu entscheiden, wo Anita oder Alice in dieser verketteten Liste setzen. 789 00:47:25,850 --> 00:47:32,480 Wenn wir nicht über das Sortieren von Dingen kümmern, konnte, wie schnell wir legen Alice in eine Struktur wie diese? 790 00:47:32,480 --> 00:47:35,370 Es ist konstante Zeit. Wir Index in [0], und wenn niemand da ist, 791 00:47:35,370 --> 00:47:37,550 Alice geht am Anfang dieser verketteten Liste. 792 00:47:37,550 --> 00:47:40,000 Aber das ist keine große Sache. Denn wenn Anita dann kommt 793 00:47:40,000 --> 00:47:42,160 eine Zahl von Schritten später, woher Anita gehören? 794 00:47:42,160 --> 00:47:45,140 Nun, [0]. OOP. Alice ist bereits in dieser verketteten Liste. 795 00:47:45,140 --> 00:47:47,760 >> Aber wenn wir nicht über das Sortieren diese Namen egal, 796 00:47:47,760 --> 00:47:53,580 können wir nur bewegen Alice vorbei, Einsatz Anita, aber selbst das ist konstante Zeit. 797 00:47:53,580 --> 00:47:57,010 Auch wenn es Alice und Adam und all diese anderen A-Namen, 798 00:47:57,010 --> 00:47:59,410 es ist nicht wirklich verschieben sie physisch. Warum? 799 00:47:59,410 --> 00:48:04,090 Weil wir gerade hier mit verketteten Liste, wer weiß wurden diese Knoten sind sowieso? 800 00:48:04,090 --> 00:48:06,550 Alles, was Sie tun müssen, ist bewegen Sie die Semmelbrösel. 801 00:48:06,550 --> 00:48:10,930 Verschieben Sie die Pfeile um, Sie müssen nicht körperlich bewegen alle Daten um. 802 00:48:10,930 --> 00:48:14,610 So können wir legen Anita, in diesem Fall sofort. Konstante Zeit. 803 00:48:14,610 --> 00:48:20,250 So haben wir in konstanter Zeit Lookup und konstanter Zeit Einsetzen von jemandem wie Anita. 804 00:48:20,250 --> 00:48:22,740 Aber irgendwie vereinfache die Welt. 805 00:48:22,740 --> 00:48:28,510 Was ist, wenn wir später wollen Alice zu finden? 806 00:48:28,510 --> 00:48:31,050 Was ist, wenn wir später wollen Alice zu finden? 807 00:48:31,050 --> 00:48:35,690 Wie viele Schritte ist, dass gehen zu nehmen? 808 00:48:35,690 --> 00:48:37,850 [Schüler Antwort unverständlich] 809 00:48:37,850 --> 00:48:40,950 Genau. Die Zahl der Menschen, bevor Alice in der verknüpften Liste. 810 00:48:40,950 --> 00:48:45,420 So ist es nicht ganz perfekt, weil unsere Datenstruktur hat wieder diese vertikale Zugang 811 00:48:45,420 --> 00:48:50,240 und dann hat es diese verkettete Listen hängen - eigentlich, lasst uns nicht ziehen es ein Array. 812 00:48:50,240 --> 00:48:56,020 Es hat diese verkettete Listen hängen von ihm weg, das sieht ein wenig so etwas wie dieses. 813 00:48:56,020 --> 00:48:59,110 Aber das Problem ist, wenn Alice und Adam und all diese anderen A-Namen 814 00:48:59,110 --> 00:49:01,720 Ende mehr und mehr dort drüben, 815 00:49:01,720 --> 00:49:04,810 jemanden zu finden, könnte am Ende unter eine Reihe von Schritten, 816 00:49:04,810 --> 00:49:06,670 bcause müssen Sie die verknüpfte Liste durchlaufen, 817 00:49:06,670 --> 00:49:08,090 die eine lineare Operation. 818 00:49:08,090 --> 00:49:14,270 So wirklich also die Einfügezeitpunkt letztlich O (n), wobei n die Anzahl der Elemente in der Liste. 819 00:49:14,270 --> 00:49:21,780 Geteilt durch, lasst uns willkürlich nennen es m, wobei m die Anzahl der verbundenen Listen 820 00:49:21,780 --> 00:49:24,500 dass wir in dieser vertikalen Achse. 821 00:49:24,500 --> 00:49:27,180 Mit anderen Worten, wenn wir wirklich setzen eine gleichmäßige Verteilung von Namen, 822 00:49:27,180 --> 00:49:30,150 völlig unrealistisch. Es gibt offensichtlich einige Briefe als andere. 823 00:49:30,150 --> 00:49:32,580 >> Aber wenn man annimmt, für den Augenblick eine gleichmäßige Verteilung, 824 00:49:32,580 --> 00:49:37,350 und wir haben n insgesamt Volk und m Gesamtlänge Ketten 825 00:49:37,350 --> 00:49:40,630 Verfügung zu stellen, dann wird die Länge eines jeden dieser Ketten 826 00:49:40,630 --> 00:49:44,380 ziemlich einfach wird der gesamte, n geteilt durch die Anzahl von Ketten ist. 827 00:49:44,380 --> 00:49:48,900 So n / m. Aber hier, wo wir sicher sein können alle mathematisch clever. 828 00:49:48,900 --> 00:49:53,030 m eine Konstante ist, weil es eine feste Anzahl von diesen. 829 00:49:53,030 --> 00:49:54,620 Du wirst das Array zu Beginn erklären, 830 00:49:54,620 --> 00:49:58,450 und wir sind nicht die Größe des vertikalen Achse. Per Definition bleibt die behoben. 831 00:49:58,450 --> 00:50:01,220 Es ist nur die horizontale Achse, so zu sprechen, dass sich verändert. 832 00:50:01,220 --> 00:50:04,760 So technisch ist dies eine Konstante. So, jetzt das Einsetzen der Zeit 833 00:50:04,760 --> 00:50:09,700 ist so ziemlich O (n). 834 00:50:09,700 --> 00:50:12,410 Also das hat nicht das Gefühl, dass alle viel besser. 835 00:50:12,410 --> 00:50:14,940 Aber was ist die Wahrheit hier? Nun, die ganze Zeit, seit Wochen, 836 00:50:14,940 --> 00:50:20,640 Wir haben gesagt, O (n ²). O (n), 2 x n ², - n, dividiert durch zwei. . . ech. 837 00:50:20,640 --> 00:50:23,580 Es ist nur n ². Aber jetzt, in diesem Teil des Semesters 838 00:50:23,580 --> 00:50:25,560 können wir anfangen, über die reale Welt wieder. 839 00:50:25,560 --> 00:50:31,520 Und n / m ist absolut schneller als nur n allein. 840 00:50:31,520 --> 00:50:35,170 Wenn Sie mehr als tausend Namen, und Sie brechen in mehrere Eimer 841 00:50:35,170 --> 00:50:37,820 so dass Sie nur zehn Namen in jeder dieser Ketten, 842 00:50:37,820 --> 00:50:41,670 absolut Suchen zehn Dinge geht, schneller zu sein als tausend Dinge. 843 00:50:41,670 --> 00:50:43,740 Und so einer der kommenden Problemstellungen wird Sie herausfordern 844 00:50:43,740 --> 00:50:46,100 über genau das denken, obwohl, yeah, 845 00:50:46,100 --> 00:50:49,520 asymptotisch und mathematisch, ist dies immer noch nur linear, 846 00:50:49,520 --> 00:50:51,700 die saugt in der Regel, wenn Sie versuchen, die Dinge zu finden. 847 00:50:51,700 --> 00:50:54,530 In Wirklichkeit, es wird schneller sein als die 848 00:50:54,530 --> 00:50:56,520 wegen dieser Divisor. 849 00:50:56,520 --> 00:50:58,310 Und so gibt es wieder los, dies zu trade-off zu sein 850 00:50:58,310 --> 00:51:01,390 und dieser Konflikt zwischen Theorie und Wirklichkeit, 851 00:51:01,390 --> 00:51:03,550 und einen der Knöpfe beginnt sich zu diesem Zeitpunkt in den Semesterferien 852 00:51:03,550 --> 00:51:07,510 ist mehr von der Realität ein, wie wir für Semesters das Ende Art vorzubereiten, 853 00:51:07,510 --> 00:51:09,280 wie wir die Einführung in die Welt der Web-Programmierung, 854 00:51:09,280 --> 00:51:11,530 wo wirklich, wird die Leistung gehen zu zählen, weil die Benutzer gehen, um 855 00:51:11,530 --> 00:51:14,880 beginnen zu fühlen und schätzen schlechte Design-Entscheidungen. 856 00:51:14,880 --> 00:51:19,950 >> So wie Sie über die Durchführung einer verlinkten gehen - eine Hash-Tabelle mit 31 Elementen? 857 00:51:19,950 --> 00:51:22,600 Und das vorherige Beispiel wurde willkürlich über Geburtstage. 858 00:51:22,600 --> 00:51:26,190 Wenn jemand Geburtstag 1. Januar oder 1. Februar werden wir sie in diesem Eimer gestellt. 859 00:51:26,190 --> 00:51:28,960 Wenn es 2. Januar, 2. Februar, 2. März ist, werden wir sie in diesem Eimer gestellt. 860 00:51:28,960 --> 00:51:32,220 Deshalb ist es 31 war. Wie kann man erklären, eine Hash-Tabelle? 861 00:51:32,220 --> 00:51:37,480 Es kann ziemlich einfach, ist der Knoten * tabelle meiner beliebigen Namen für sie, [31]. 862 00:51:37,480 --> 00:51:42,400 Das gibt mir 31 Zeigern auf Knoten, 863 00:51:42,400 --> 00:51:45,370 und das ermöglicht es mir, 31 Zeiger auf verkettete Listen haben 864 00:51:45,370 --> 00:51:48,800 auch wenn diese Ketten sind zunächst NULL. 865 00:51:48,800 --> 00:51:54,860 Was will ich zu setzen, wenn ich speichern möchten "Alice", "Bob", "Charlie"? 866 00:51:54,860 --> 00:51:57,010 Nun müssen wir diese Dinge in einer Struktur wickeln 867 00:51:57,010 --> 00:52:00,530 denn wir brauchen Alice zu Bob zeigen, um Charlie zeigen, und so weiter. 868 00:52:00,530 --> 00:52:04,940 Wir können nicht einfach die Namen allein, so konnte ich eine neue Struktur namens Knoten hier. 869 00:52:04,940 --> 00:52:08,310 >> Was ist eine tatsächliche Knoten? Was ist ein Knoten in diesem neuen verketteten Liste? 870 00:52:08,310 --> 00:52:11,840 Die erste Sache, als Wort, ist für den Namen der Person. 871 00:52:11,840 --> 00:52:14,340 LÄNGE vermutlich betrifft die maximale Länge eines menschlichen Namen, 872 00:52:14,340 --> 00:52:18,210 was auch immer das ist, 20, 30, 40 Zeichen in verrückten Ecke Fällen, 873 00:52:18,210 --> 00:52:22,680 und +1 ist für was? Es ist nur die zusätzlichen NULL-Zeichen, \ 0. 874 00:52:22,680 --> 00:52:27,410 So wird dieser Knoten Einwickeln "etwas" in sich selbst, 875 00:52:27,410 --> 00:52:29,640 aber es erklärt auch einen Zeiger namens nächsten 876 00:52:29,640 --> 00:52:32,580 so dass wir Chain Alice an Bob, Charlie und so weiter. 877 00:52:32,580 --> 00:52:36,700 Kann NULL sein, aber nicht unbedingt so sein. 878 00:52:36,700 --> 00:52:40,110 Haben Sie Fragen zu dieser Hash-Tabellen? Yeah? 879 00:52:40,110 --> 00:52:46,190 [Schüler fragen Frage, unverständlich] Ein Array - gute Frage. 880 00:52:46,190 --> 00:52:50,120 Warum ist das char Wort in einem Array nicht nur char *? 881 00:52:50,120 --> 00:52:53,830 In diesem etwas willkürliches Beispiel, wollte ich nicht zu haben, um Zuflucht 882 00:52:53,830 --> 00:52:56,190 malloc für jeden der ursprünglichen Namen. 883 00:52:56,190 --> 00:52:59,530 Ich wollte eine maximale Menge an Speicher für den String zu erklären 884 00:52:59,530 --> 00:53:06,020 so dass ich in die Struktur kopieren Alice \ 0 und nicht mit malloc und free und dergleichen zu tun haben. 885 00:53:06,020 --> 00:53:11,710 Aber ich könnte das tun, wenn ich ein größeres Bewusstsein für Raumnutzung wollte. Gute Frage. 886 00:53:11,710 --> 00:53:14,780 So wollen wir versuchen, zu verallgemeinern weg von diesem 887 00:53:14,780 --> 00:53:18,350 und konzentrieren den Rest von heute auf Datenstrukturen allgemein 888 00:53:18,350 --> 00:53:21,170 und andere Probleme, die wir lösen mit den gleichen Grundlagen können 889 00:53:21,170 --> 00:53:24,590 obwohl die Datenstrukturen selbst könnten in ihren Angaben abweichen. 890 00:53:24,590 --> 00:53:27,910 >> So es sich herausstellt, in der Informatik, sind Bäume sehr häufig. 891 00:53:27,910 --> 00:53:29,760 Und Sie können von einem Baum wie eine Art Stammbaum denken, 892 00:53:29,760 --> 00:53:31,830 wo es einige Wurzeln, einige Matriarchin oder Patriarch, 893 00:53:31,830 --> 00:53:34,540 Oma oder Opa oder früher zurück, 894 00:53:34,540 --> 00:53:38,880 unter denen Mama und Papa oder verschiedene Geschwister oder dergleichen. 895 00:53:38,880 --> 00:53:42,500 So eine Baumstruktur hat Knoten und hat Kinder, 896 00:53:42,500 --> 00:53:45,260 meistens 0 oder mehr Kinder für jeden Knoten. 897 00:53:45,260 --> 00:53:47,320 Und einige der Jargon, dass Sie in diesem Bild sehen Sie hier 898 00:53:47,320 --> 00:53:50,630 irgendeine der kleine Kinder oder Enkel an den Rändern 899 00:53:50,630 --> 00:53:52,330 , die haben keine Pfeile von ihnen ausgehenden, 900 00:53:52,330 --> 00:53:55,070 das sind die sogenannten Blätter, und einem auf der Innenseite 901 00:53:55,070 --> 00:53:58,790 ist ein innerer Knoten, man kann es nennen etwas in diese Richtung. 902 00:53:58,790 --> 00:54:01,430 Aber diese Struktur ist sehr verbreitet. Dieser ist ein wenig willkürlich. 903 00:54:01,430 --> 00:54:04,930 Wir haben ein Kind auf der linken Seite, wir haben drei Kinder auf der rechten Seite, 904 00:54:04,930 --> 00:54:06,830 zwei Kinder auf dem Boden hinterlassen. 905 00:54:06,830 --> 00:54:10,740 So können wir haben unterschiedlich große Bäume, aber wenn wir Dinge zu standardisieren starten, 906 00:54:10,740 --> 00:54:15,330 und Sie könnten diese von Patrick Video erinnern, auf binäre Suche von einer früheren kurzen 907 00:54:15,330 --> 00:54:19,490 online, Binärsuche muss nicht mit einer Anordnung durchgeführt werden 908 00:54:19,490 --> 00:54:21,410 oder Stücke von Papier auf einer Tafel. 909 00:54:21,410 --> 00:54:25,490 Angenommen, Sie möchten Ihre Zahlen in einem komplexeren Datenstruktur speichern wollte. 910 00:54:25,490 --> 00:54:27,680 Sie könnten einen Baum wie diese. 911 00:54:27,680 --> 00:54:35,290 Sie hätte eine Knoten in C deklariert, und dieser Knoten kann wenigstens zwei Elemente im Inneren davon haben. 912 00:54:35,290 --> 00:54:39,470 Eine davon ist die Nummer, die Sie speichern wollen, und das andere ist - na ja, wir brauchen noch einen. 913 00:54:39,470 --> 00:54:41,540 Die andere ist seine Kinder. 914 00:54:41,540 --> 00:54:45,150 Also hier ist eine andere Datenstruktur. Dieser Zeitpunkt wird als ein Knoten Speichern einer Zahl n definiert 915 00:54:45,150 --> 00:54:49,060 und dann zwei Zeigern, links Kindes und das Recht Kind. 916 00:54:49,060 --> 00:54:52,100 Und sie sind nicht willkürlich. Was ist interessant an dieser Baum? 917 00:54:52,100 --> 00:55:00,550 >> Was ist das Muster, wie wir diese angelegt oder wie Patrick es legte in seinem Video? 918 00:55:00,550 --> 00:55:02,790 Es ist ziemlich offensichtlich, dass es einige Sortierung geht hier vor, 919 00:55:02,790 --> 00:55:04,460 aber was ist die einfache Regel? Yeah? 920 00:55:04,460 --> 00:55:08,350 [Schüler Antwort unverständlich] 921 00:55:08,350 --> 00:55:12,040 Perfect. Wenn Sie einen Blick auf diese, sehen Sie die kleinen Zahlen auf der linken Seite, 922 00:55:12,040 --> 00:55:14,690 großen Zahlen auf der linken Seite, aber das ist für jeden Knoten wahr. 923 00:55:14,690 --> 00:55:20,370 Für jeden Knoten, seine linke Kind weniger als sie und ihre rechte Kind größer als dieser. 924 00:55:20,370 --> 00:55:25,210 Was bedeutet dies jetzt, wenn ich diese Datenstruktur für, sagen wir, der Nummer 44 suchen möchten, 925 00:55:25,210 --> 00:55:29,320 Ich habe an der Wurzel beginnen, denn wie bei allen diesen komplexere Datenstrukturen jetzt 926 00:55:29,320 --> 00:55:31,910 wir haben nur einen Zeiger auf eine Sache, der Anfang. 927 00:55:31,910 --> 00:55:35,010 Und in diesem Fall, ist der Beginn der Wurzel. Es ist nicht das linke Ende, 928 00:55:35,010 --> 00:55:39,530 es ist die Wurzel dieser Struktur. Also ich sehe hier ist 55, und ich bin für 44 suchen. 929 00:55:39,530 --> 00:55:41,430 Welche Richtung will ich gehen? 930 00:55:41,430 --> 00:55:45,680 Nun, ich will nach links gehen, weil offensichtlich auf der rechten Seite wird zu groß sein. 931 00:55:45,680 --> 00:55:49,050 Also hier merkt, du bist Art konzeptionell hacken den Baum in der Mitte 932 00:55:49,050 --> 00:55:51,700 weil du nie auf der rechten Seite. 933 00:55:51,700 --> 00:55:55,410 So jetzt habe ich von der 55 auf die 33 gehen. Es ist zu klein für eine Nummer. 934 00:55:55,410 --> 00:56:01,590 Ich bin für 44 suchen, aber jetzt weiß ich, wenn 44 ist in diesem Baum, kann ich natürlich nach rechts gehen. 935 00:56:01,590 --> 00:56:04,460 Also noch einmal, ich bin Beschneiden der Baum in der Mitte. 936 00:56:04,460 --> 00:56:06,780 Es ist ziemlich identisch konzeptionell mit dem Telefonbuch. 937 00:56:06,780 --> 00:56:09,510 Es ist identisch zu dem, was wir mit den Arbeiten an der Tafel hat, 938 00:56:09,510 --> 00:56:13,940 aber es ist eine kompliziertere Struktur, die wir wirklich tun können 939 00:56:13,940 --> 00:56:16,880 Diese teilen und zu erobern, indem Entwurf des Algorithmus, 940 00:56:16,880 --> 00:56:19,420 und in der Tat, durchqueren eine Struktur wie diese - hoppla. 941 00:56:19,420 --> 00:56:22,870 Durchlaufen einer Struktur wie diese, wo es nur "diesen Weg gehen oder gehen Sie auf diese Weise" 942 00:56:22,870 --> 00:56:26,870 bedeutet, dass alle, dass Code, die Ihren Verstand auf den ersten gebogen bei ihrer Umsetzung in Abschnitt 943 00:56:26,870 --> 00:56:31,270 oder zu Fuß durch sie zu Hause, für binäre Suche mit Rekursion oder Iteration 944 00:56:31,270 --> 00:56:35,060 es ist ein Schmerz im Nacken. Finden Sie das mittlere Element, dann tun Sie Ihre Auf-oder Abrundung. 945 00:56:35,060 --> 00:56:39,230 >> Es gibt eine Schönheit, weil wir nun Rekursion wieder 946 00:56:39,230 --> 00:56:43,760 sondern viel mehr sauber. In der Tat, wenn Sie unter der Nummer 55, und Sie möchten 44 zu finden, 947 00:56:43,760 --> 00:56:48,450 Sie gehen links in diesem Fall, so was tun Sie? Sie führen den exakt gleichen Algorithmus. 948 00:56:48,450 --> 00:56:51,560 Sie überprüfen den Wert des Knotens, dann gehen Sie nach links oder rechts. 949 00:56:51,560 --> 00:56:53,670 Dann überprüfen Sie den Wert des Knotens, gehen Sie nach links oder rechts. 950 00:56:53,670 --> 00:56:56,710 Dieses ist perfekt auf Rekursion geeignet. 951 00:56:56,710 --> 00:57:00,920 Also auch wenn in der Vergangenheit haben wir einige ziemlich willkürlich Beispiele mit Rekursion 952 00:57:00,920 --> 00:57:03,430 das brauchte nicht rekursiv sein, mit Daten stuctures, 953 00:57:03,430 --> 00:57:07,820 vor allem Bäume, es ist eine perfekte Anwendung dieser Idee, ein Problem 954 00:57:07,820 --> 00:57:12,920 Schrumpfen, und dann die Lösung der gleichen Art von, jedoch kleiner Programm. 955 00:57:12,920 --> 00:57:14,590 >> So gibt es eine andere Datenstruktur, die wir einführen können. 956 00:57:14,590 --> 00:57:18,760 Dieser ist auf den ersten Blick aussehen kryptischen entwickelt, aber dieses ist erstaunlich. 957 00:57:18,760 --> 00:57:25,090 Dies ist also eine Datenstruktur genannt Trie Trie, die aus der Wort-Wiederauffindungseinrichtung geerbt wird, 958 00:57:25,090 --> 00:57:30,210 was nicht re-try-val ausgeprägt, aber das ist, was die Welt diese Dinge nennt. Versucht. T-R-I-e. 959 00:57:30,210 --> 00:57:35,190 Es ist eine Baumstruktur von einer Art, aber jeder der Knoten in einem Trie 960 00:57:35,190 --> 00:57:41,280 scheint was? Und das ist ein wenig irreführend, weil es irgendwie abgekürzt ist. 961 00:57:41,280 --> 00:57:45,960 Aber es sieht aus wie jeder Knoten in diesem Trie ist eigentlich ein Array. 962 00:57:45,960 --> 00:57:48,840 Und obwohl der Autor dieser Darstellung nicht gezeigt, 963 00:57:48,840 --> 00:57:54,130 in diesem Fall ist dies ein Trie-Datenstruktur, deren Zweck im Leben ist, um Wörter zu speichern 964 00:57:54,130 --> 00:57:57,330 wie A-l-i-c-e-oder B-O-B. 965 00:57:57,330 --> 00:58:02,480 Und die Art und Weise, in der diese Daten speichert Alice und Bob und Charlie und Anita usw. 966 00:58:02,480 --> 00:58:06,970 wird es verwendet ein Array, wodurch Alice in einer Trie speichern, 967 00:58:06,970 --> 00:58:09,820 Wir beginnen bei den Root-Knoten, die wie ein Array aussieht, 968 00:58:09,820 --> 00:58:12,080 und es ist in Kurzschrift geschrieben worden. 969 00:58:12,080 --> 00:58:15,070 Der Autor verzichtet abcdefg, denn es gab keine Namen damit. 970 00:58:15,070 --> 00:58:19,150 Sie zeigten nur M und P und T, aber in diesem Fall, 971 00:58:19,150 --> 00:58:22,780 Lassen Sie uns weg von Alice und Bob und Charlie zu bewegen, um ein paar Namen, die hier sind. 972 00:58:22,780 --> 00:58:25,670 Maxwell ist eigentlich in diesem Diagramm. 973 00:58:25,670 --> 00:58:29,570 Wie hat der Autor store M-A-x-w-e-l-l? 974 00:58:29,570 --> 00:58:36,990 Er oder sie begann an der Root-Knoten, und ging zu [M], so etwa 13, die 13. Position im Array. 975 00:58:36,990 --> 00:58:40,750 Dann von dort aus gibt es einen Zeiger. 976 00:58:40,750 --> 00:58:42,760 Ein Zeiger, die zu einem anderen Array. 977 00:58:42,760 --> 00:58:47,880 Von dort führt der Autor in diesem Array am Standort A indiziert, da links oben dargestellt, 978 00:58:47,880 --> 00:58:52,250 und dann hat er oder sie folgten den Zeiger zu einem anderen Array, 979 00:58:52,250 --> 00:58:55,460 und ging auf den Zeiger an der Stelle X. 980 00:58:55,460 --> 00:58:59,840 Dann im nächsten Matrixort W, E, L, L, und so weiter, 981 00:58:59,840 --> 00:59:03,090 und schließlich, lasst uns tatsächlich versuchen, ein Bild zu bereiten. 982 00:59:03,090 --> 00:59:05,380 Was bedeutet ein Knoten aussehen im Code? 983 00:59:05,380 --> 00:59:11,820 Ein Knoten in einem Trie enthält ein Array von Zeigern auf weitere Knoten. 984 00:59:11,820 --> 00:59:16,090 Aber es ist auch bekam eine Art von booleschen Wert zu sein, zumindest in dieser Implementierung. 985 00:59:16,090 --> 00:59:18,770 Ich bin zufällig nennen es is_word. Warum? 986 00:59:18,770 --> 00:59:22,670 Denn wenn Sie das Einfügen Maxwell, du bist nicht Einsetzen 987 00:59:22,670 --> 00:59:25,300 alles in dieser Datenstruktur. 988 00:59:25,300 --> 00:59:27,480 Sie sind nicht schriftlich M. Sie sind nicht schriftlich X. 989 00:59:27,480 --> 00:59:30,240 Alles, was Sie tun, ist nach Zeigern. 990 00:59:30,240 --> 00:59:33,360 Der Zeiger, M, dann wird der Zeiger, der A darstellt, 991 00:59:33,360 --> 00:59:36,310 dann die Zeiger, X, W, E, L, L, 992 00:59:36,310 --> 00:59:41,950 aber was Sie brauchen, um am Ende zu tun ist eine Art zu gehen, zu überprüfen, erreichte ich diesen Ort. 993 00:59:41,950 --> 00:59:45,560 Es gab ein Wort, das hier endet in der Datenstruktur. 994 00:59:45,560 --> 00:59:48,190 >> Also, was ein Trie ist wirklich mit gefüllt und der Autor wählte zu vertreten 995 00:59:48,190 --> 00:59:51,880 diese Endhaltestellen mit kleinen Dreiecke. 996 00:59:51,880 --> 00:59:56,470 Dies bedeutet nur, dass die Tatsache, dieses Dreieck ist hier, diese boolesche Wert true 997 00:59:56,470 --> 00:59:59,200 bedeutet, wenn Sie rückwärts in den Baum gehen, 998 00:59:59,200 --> 01:00:02,420 das heißt, ein Wort benannt Maxwell ist in diesem. 999 01:00:02,420 --> 01:00:04,870 Aber das Wort foo beispielsweise 1000 01:00:04,870 --> 01:00:07,970 nicht in den Baum, denn wenn ich starten am Wurzelknoten hier oben, 1001 01:00:07,970 --> 01:00:14,030 Es gibt keine f Zeiger, kein o Zeiger, kein o Zeiger. Foo ist nicht ein Name in diesem Wörterbuch. 1002 01:00:14,030 --> 01:00:22,460 Aber im Gegensatz dazu entwickelt, durch t-u-r-i-n-g. Auch habe ich nicht speichern t oder u oder r oder i oder n oder g. 1003 01:00:22,460 --> 01:00:29,820 Aber ich habe store in dieser Datenstruktur ein Wert von wahren Weg hier unten in diesem Knoten - im Baum 1004 01:00:29,820 --> 01:00:33,030 indem Sie diesen booleschen Wert is_word auf true. 1005 01:00:33,030 --> 01:00:35,740 So ein Trie ist eine Art dieser sehr interessanten Meta-Struktur, 1006 01:00:35,740 --> 01:00:39,810 wo du nicht wirklich die Speicherung der Worte selbst für diese Art von Wörterbuch. 1007 01:00:39,810 --> 01:00:45,100 Um es klar, du bist nur die Speicherung ja oder nein, es ist ein Wort, das hier endet. 1008 01:00:45,100 --> 01:00:46,430 >> Nun, was ist die Implikation? 1009 01:00:46,430 --> 01:00:51,120 Wenn Sie 150.000 Wörter in einem Wörterbuch, dass Sie versuchen, zu speichern 1010 01:00:51,120 --> 01:00:53,400 mit so etwas wie einer verketteten Liste, 1011 01:00:53,400 --> 01:00:56,870 Sie gehen zu 150.000 Knoten in Ihrer verketteten Liste haben. 1012 01:00:56,870 --> 01:01:00,250 Und die Suche nach einem dieser Wörter alphabetisch könnte O (n) Zeit. 1013 01:01:00,250 --> 01:01:04,370 Lineare Zeit. Aber in dem Fall des hier einem Trie 1014 01:01:04,370 --> 01:01:09,210 Was ist die Laufzeit der Suche nach einem Wort? 1015 01:01:09,210 --> 01:01:17,390 Es stellt sich heraus, die Schönheit hier ist, dass selbst wenn Sie 149.999 Wörter in diesem Wörterbuch, 1016 01:01:17,390 --> 01:01:20,170 wie mit dieser Datenstruktur implementiert, 1017 01:01:20,170 --> 01:01:25,560 Wie viel Zeit braucht es, um zu finden oder legen Sie eine weitere Person in das, wie Alice, Alice? 1018 01:01:25,560 --> 01:01:30,640 Nun, es ist nur 5, vielleicht 6 Schritte für den nachlaufenden Charakter. 1019 01:01:30,640 --> 01:01:32,880 Da die presense von anderen Namen in der Struktur 1020 01:01:32,880 --> 01:01:35,340 nicht in der Weise des Einsetzens Alice erhalten. 1021 01:01:35,340 --> 01:01:39,640 Darüber hinaus finden Alice einmal gibt es 150.000 Wörter in diesem Wörterbuch 1022 01:01:39,640 --> 01:01:41,960 nicht in den Weg zu finden, Alice überhaupt zu bekommen, 1023 01:01:41,960 --> 01:01:46,880 weil Alice ist. . . . . hier, weil ich fand einen boolean Wert. 1024 01:01:46,880 --> 01:01:50,920 Und wenn es keine boolesche wahr ist, dann Alice nicht in dieser Datenstruktur von Wörtern. 1025 01:01:50,920 --> 01:01:56,220 Mit anderen Worten, die Laufzeit des Findens Dinge und Einsetzen in diese neue Dinge 1026 01:01:56,220 --> 01:02:01,920 Datenstruktur Trie ist O - es ist nicht n. 1027 01:02:01,920 --> 01:02:05,730 Da die presense 150.000 Menschen hat keinen Einfluss auf Alice, wie es scheint. 1028 01:02:05,730 --> 01:02:11,560 So nennen wir es k, wo k ist die maximale Länge eines Wortes in Englisch 1029 01:02:11,560 --> 01:02:14,050 der typischerweise nicht mehr als 20-etwas Zeichen. 1030 01:02:14,050 --> 01:02:17,940 So k eine Konstante ist. So der Heilige Gral scheinen wir jetzt gefunden haben, 1031 01:02:17,940 --> 01:02:26,000 ist, dass von einem Trie konstante Zeit für Einsätze, für Lookups, für Deletionen. 1032 01:02:26,000 --> 01:02:29,170 Da die Anzahl der Dinge bereits in der Struktur, 1033 01:02:29,170 --> 01:02:32,600 das sind nicht einmal physisch anwesend. Auch sie einfach irgendwie abgehakt, ja oder nein, 1034 01:02:32,600 --> 01:02:35,050 hat keine Auswirkungen auf die künftige Laufzeit. 1035 01:02:35,050 --> 01:02:37,940 >> Aber es muss doch einen Haken, sonst wären wir nicht so viel Zeit verschwendet haben 1036 01:02:37,940 --> 01:02:41,460 auf all diesen anderen Datenstrukturen, nur um endlich das Geheimnis ein, die erstaunlich bekommen. 1037 01:02:41,460 --> 01:02:46,410 Also, was Preis zahlen wir diese Größe hier erreichen? Space. 1038 01:02:46,410 --> 01:02:49,010 Das Ding ist riesig. Und der Grund, dass der Autor 1039 01:02:49,010 --> 01:02:52,400 nicht präsentieren hier bemerken, dass all diese Dinge, die wie Arrays aussehen, 1040 01:02:52,400 --> 01:02:55,400 Er zog nicht den Rest des Baumes, der Rest der Trie 1041 01:02:55,400 --> 01:02:58,060 weil sie einfach nicht relevant für die Geschichte. 1042 01:02:58,060 --> 01:03:01,870 Aber alle diese Knoten sind super breit, und jeder Knoten im Baum nimmt 1043 01:03:01,870 --> 01:03:07,780 26 oder tatsächlich, könnte 27 Zeichen lang sein, da in diesem Fall war ich auch Platz für den Apostroph 1044 01:03:07,780 --> 01:03:09,980 so konnten wir haben apostrophierten Worte. 1045 01:03:09,980 --> 01:03:14,450 In diesem Fall sind dies breite Arrays. Also auch wenn sie nicht picutured, 1046 01:03:14,450 --> 01:03:18,190 Diese nimmt eine enorme Menge an RAM. 1047 01:03:18,190 --> 01:03:20,670 Welche könnte in Ordnung sein, especilly in moderner Hardware 1048 01:03:20,670 --> 01:03:25,650 aber das ist der Kompromiss. Wir bekommen weniger Zeit verbringen mehr Platz. 1049 01:03:25,650 --> 01:03:28,580 Also, wo ist das alles hin? 1050 01:03:28,580 --> 01:03:32,640 Nun, lass es uns tun - lasst uns hier zu sehen. 1051 01:03:32,640 --> 01:03:39,510 Lassen Sie uns einen Sprung zu diesem Kerl hier. 1052 01:03:39,510 --> 01:03:43,450 >> Ob Sie es glauben oder nicht, so viel Spaß wie C seit einiger Zeit jetzt gewesen, 1053 01:03:43,450 --> 01:03:48,130 wir den Punkt erreicht, in dem Semester, in denen es an der Zeit für den Übergang zu Dinge mehr modern. 1054 01:03:48,130 --> 01:03:50,950 Dinge, auf einer höheren Ebene. Und obwohl für die nächsten paar Wochen 1055 01:03:50,950 --> 01:03:54,580 wir noch weiter, um uns in der Welt der Zeiger und Speicher-Management eintauchen 1056 01:03:54,580 --> 01:03:57,210 , dass Trost, mit dem wir dann auf zu bauen bekommen, 1057 01:03:57,210 --> 01:04:01,270 das Endspiel ist letztlich einzuführen, ironischerweise nicht diese Sprache. 1058 01:04:01,270 --> 01:04:03,330 Wir verbringen, wie 10 Minuten reden HTML. 1059 01:04:03,330 --> 01:04:05,950 Alle HTML ist eine Markup-Sprache, und was für eine Markup-Sprache ist 1060 01:04:05,950 --> 01:04:10,220 ist diese Reihe von offenen Klammern und geschlossenen Klammern, 'machen diese bold' sagen 1061 01:04:10,220 --> 01:04:12,000 "Nehmen Sie diese kursiv 'machen diese zentriert." 1062 01:04:12,000 --> 01:04:14,250 Es ist gar nicht so intellektuell interessant, aber es ist super nützlich. 1063 01:04:14,250 --> 01:04:16,650 Und es ist sicherlich allgegenwärtig in diesen Tagen. 1064 01:04:16,650 --> 01:04:19,450 Aber was ist mächtig über die Welt der HTML und Web-Programmierung allgemein 1065 01:04:19,450 --> 01:04:25,910 baut dynamische Dinge; Schreiben von Code in Sprachen wie PHP oder Python oder Ruby oder Java oder C #. 1066 01:04:25,910 --> 01:04:30,360 Wirklich, was der Sprache Ihrer Wahl, und die Erzeugung von HTML dynamisch. 1067 01:04:30,360 --> 01:04:32,960 Generieren etwas namens CSS dynamisch. 1068 01:04:32,960 --> 01:04:35,810 Cascading Style Sheets, die auch um Ästhetik. 1069 01:04:35,810 --> 01:04:41,360 Und obwohl heute, wenn ich gehe zu einem gewissen Website wie die vertraute Google.com, 1070 01:04:41,360 --> 01:04:46,100 und ich gehe zu sehen, Entwickler, Quelltext, die Sie vielleicht zuvor getan, 1071 01:04:46,100 --> 01:04:49,800 sondern gehen für Quellenangaben, dieses Zeug wohl sieht ziemlich kryptisch. 1072 01:04:49,800 --> 01:04:55,320 Aber dies ist die zugrunde liegende Code, Google.com implementiert. 1073 01:04:55,320 --> 01:04:57,940 Auf dem vorderen Ende. Und tatsächlich all dies ist flauschig Ästhetik Zeug. 1074 01:04:57,940 --> 01:05:01,740 Dies ist CSS hier oben. Wenn ich nach unten scrollen zu halten bekommen wir einige farbige Sachen. 1075 01:05:01,740 --> 01:05:06,890 Dies ist HTML. Google-Code sieht aus wie ein Chaos, aber wenn ich tatsächlich eröffnen ein anderes Fenster, 1076 01:05:06,890 --> 01:05:09,380 können wir eine gewisse Struktur, das zu sehen. 1077 01:05:09,380 --> 01:05:12,640 Wenn ich diesen eröffnen, hier zu bemerken, ist es ein wenig besser lesbar. 1078 01:05:12,640 --> 01:05:16,850 Wir werden bald sehen diesen Tag, [word] ist ein Tag, 1079 01:05:16,850 --> 01:05:23,520 HTML, Kopf, Körper, div, Drehbuch, Textbereich, span, zentriert, div. 1080 01:05:23,520 --> 01:05:26,770 Und dies wird auch von kryptischen aussehende sortieren auf den ersten Blick 1081 01:05:26,770 --> 01:05:30,890 aber alle aus diesem Schlamassel folgt bestimmten Mustern und wiederholbare Muster, 1082 01:05:30,890 --> 01:05:33,850 so dass, wenn wir die Grundlagen runter, wirst du in der Lage sein, Code wie diesen schreiben 1083 01:05:33,850 --> 01:05:37,550 und dann manipulieren Code wie dies mit noch einer anderen Sprache, genannt JavaScript. 1084 01:05:37,550 --> 01:05:40,440 Und JavaScript ist eine Sprache, die in Auflagen von einem Browser 1085 01:05:40,440 --> 01:05:44,380 heute bekannt, dass wir auf Harvard Kursen, verwenden Sie für den Kurs Shopping-Tool, dass Google Maps verwendet 1086 01:05:44,380 --> 01:05:48,660 um Ihnen eine ganze Reihe von Dynamik, gibt Facebook Sie Instant Status-Updates zeigen, 1087 01:05:48,660 --> 01:05:51,430 Twitter nutzt es Ihnen zu zeigen, Tweets sofort. 1088 01:05:51,430 --> 01:05:53,820 All dies werden wir beginnen, uns eintauchen in. 1089 01:05:53,820 --> 01:05:57,190 Aber um dorthin zu gelangen, müssen wir ein bisschen etwas über das Internet zu verstehen. 1090 01:05:57,190 --> 01:06:01,130 Dieser Clip ist hier nur eine Minute lang, und nehmen wir an, jetzt dies ist in der Tat, 1091 01:06:01,130 --> 01:06:08,380 wie das Internet als Teaser für das, was zu kommen funktioniert. Gebe ich euch "Warriors of the Net". 1092 01:06:08,380 --> 01:06:14,720 >> [♫ Langsam Chormusik ♫] 1093 01:06:14,720 --> 01:06:20,450 [Männlich Erzähler] Er kam mit einer Botschaft. 1094 01:06:20,450 --> 01:06:23,770 Mit einem Protokoll alle seine eigenen. 1095 01:06:23,770 --> 01:06:37,270 [♫ Schnellere elektronische Musik ♫] 1096 01:06:37,270 --> 01:06:41,330 Er kam, um eine Welt der kühlen Firewalls, gefühllos Router, 1097 01:06:41,330 --> 01:06:45,690 und Gefahren weit schlimmer als der Tod. 1098 01:06:45,690 --> 01:06:55,400 Er ist schnell. Er ist stark. Er ist TCP / IP, und er hat Ihre Adresse. 1099 01:06:55,400 --> 01:06:59,250 Warriors of the Net. 1100 01:06:59,250 --> 01:07:05,290 [Malan] Nächste Woche dann. Das Internet ist. Web-Programmierung. Dies ist CS50. 1101 01:07:05,290 --> 01:07:08,290 [CS50.TV]