[Musik zu spielen]
Sprecher 1: In Ordnung.
Jeder willkommen zurück in Abschnitt.
Ich hoffe, Sie alle erfolgreich sind von Ihrem Quiz gewonnen
von letzter Woche.
Ich weiß, es ist ein bisschen verrückt zu Zeiten.
Wie ich zuvor gesagt habe, wenn Sie innerhalb der Standardabweichung,
nicht wirklich darum kümmern, vor allem für eine weniger komfortable Abschnitt.
Das ist ungefähr, wo man sein sollte.
>> Wenn ja toll, dann genial.
Ein großes Lob an euch.
Und wenn Sie das Gefühl, Sie brauchen ein bisschen mehr Hilfe, bitte
fühlen sich frei, zu erreichen aus einem der TFs.
Wir sind alle hier, um zu helfen.
>> Deshalb haben wir uns zu lehren.
Das ist, warum ich hier bin jeden Montag für Sie Jungs und bei der Bürozeiten am Donnerstag.
Also zögern Sie nicht, mich zu informieren wenn Sie sich Sorgen über alles bist
oder wenn es etwas gibt, auf das Quiz Sie würde wirklich gerne ansprechen.
>> So ist die Tagesordnung für heute alles über Datenstrukturen.
Einige von diesen sind gerade dabei, nur sein, um Sie mit diesen vertraut gemacht.
Sie können nicht immer umsetzen sie in dieser Klasse.
Einige von ihnen du willst, wie für Ihre Speller pset.
>> Sie werden Ihre Wahl zwischen Hash-Tabellen und versucht.
Also werden wir auf jeden Fall über diejenigen gehen.
Es wird auf jeden Fall mehr von Art sein einer Hochpegelabschnitt Heute jedoch
denn es gibt eine Menge von ihnen, und wenn Wir gingen in den Implementierungsdetails
auf all diese, würden wir nicht sogar durch verkettete Listen bekommen
und vielleicht ein bisschen von Hash-Tabellen.
>> So mit mir tragen.
Wir gehen nicht zu tun so viel Codierungs diesmal.
Wenn Sie irgendwelche Fragen über sie haben oder Sie zu sehen, es umgesetzt werden soll
oder probieren Sie es aus, Ich empfehle auf jeden Fall
werde study.cs50.net, die hat Beispiele für alle diese.
Es werde mein Powerpoints haben mit den Noten, die wir
neigen dazu, sowie einige Programmier verwenden Übungen, vor allem für Dinge
wie verkettete Listen und binäre Bäume Stacks und Queues.
So wenig mehr Hochebene, die wäre schön für euch sein.
>> Also mit diesem werden wir loslegen.
Und auch, yes-- Quiz.
Ich die meisten von euch, die in sind denken meine Abschnitten ihr Quiz,
aber jeder kommt in oder aus irgendeinem Grund tun sie nicht, sie sind hier in der Front.
>> So verknüpften Listen.
Ich kenne diese Art von geht vor Ihrem Quiz zurück.
Das war die Woche vor dass wir darüber gelernt.
Aber in diesem Fall, werden wir nur gehen ein bisschen mehr in die Tiefe.
>> Warum also könnten wir wählen ein verketteten Liste über ein Array?
Was unterscheidet sie?
Ja?
>> PUBLIKUM: Sie können zu erweitern eine verknüpfte List gegen feste Größe eines Arrays.
Sprecher 1: Richtig.
Ein Array hat eine Größe, während eine feste verketteten Liste hat eine variable Größe.
Also, wenn wir nicht wissen, wie viel speichern möchten wir,
eine verbundene Liste gibt uns eine große Weise zu tun, weil wir einfach
hinzufügen auf einem anderen Knoten und fügen Sie auf ein anderer Knoten und auf einem anderen Knoten hinzuzufügen.
Aber was könnte ein Kompromiss sein?
Erinnert sich noch jemand den Trade-off zwischen Arrays und verkettete Listen?
Mmhmm?
>> PUBLIKUM: Du musst gehen durch den ganzen Weg
durch die verkettete Liste finden Sie ein Element in einer Liste.
In einem Array können Sie nur ein Element zu finden.
>> Sprecher 1: Richtig.
Also mit arrays--
>> PUBLIKUM: [unverständlich].
>> Sprecher 1: Bei Arrays, haben wir was Random Access bezeichnet.
Bedeutet, dass, wenn wir wollen, was ist immer der fünfte Punkt einer Liste
oder der fünfte Punkt unserer Array, können wir einfach packen es.
Wenn es eine verknüpfte Liste, haben wir durchlaufen, oder?
Also Zugriff auf ein Element in ein Array ist konstante Zeit,
während bei einer verketteten Liste, es würde wahrscheinlichste lineare Zeit sein, weil vielleicht
unser Element ist den ganzen Weg am Ende.
Wir haben alles durch suchen.
Also mit all diesen Daten Strukturen werden wir
ein wenig mehr Zeit auf die Ausgaben, was sind die Vor-und Nachteile.
Wenn wir vielleicht wollen verwenden einen über den anderen?
Und das ist irgendwie das größere Sache zum Mitnehmen.
>> Hier das so haben wir Definition eines Knotens.
Es ist wie ein Element in unsere verketteten Liste, oder?
Also sind wir alle kennen mit unseren typedef Strukturen,
die wir gingen im Rückblick letzten Mal.
Es war im Grunde nur die Schaffung ein anderer Datentyp, den wir benutzen konnten.
>> Und in diesem Fall ist es einige Knoten dass eine gewisse ganze Zahl im zu halten.
Und was ist dann der zweite Teil hier?
Anyone?
>> PUBLIKUM: [unverständlich].
>> Sprecher 1: Ja.
Es ist ein Zeiger zu dem nächsten Knoten.
Also das sollte eigentlich hier sein.
Dies ist ein Zeiger vom Typ Knoten zum nächsten Sache.
Und das ist, was sie umfasst unser Knoten.
Cool.
>> In Ordnung, so mit der Suche, wie wir waren nur sagen, bevor die Hand, wenn Sie
gehen, um durch zu suchen, muss man eigentlich durchlaufen
durch Ihre verketteten Liste.
Also, wenn wir für die Nummer suchen 9, würden wir auf unserem Vorsprung
und weist uns am Anfang unserer verketteten Liste, oder?
Und wir sagen, OK, tut dies Knoten enthalten die Nummer 9?
Nein?
>> Also gut, gehen Sie zum nächsten.
Folgen Sie ihm.
Ist es die Zahl 9 enthalten?
Nein.
Folgen Sie der nächste.
>> Also müssen wir eigentlich durchlaufen durch unsere verketteten Liste.
Wir können nicht nur direkt zu denen 9 ist.
Und wenn euch wirklich wollen, sehen Sie einige Pseudo-Code oben.
Wir haben einige Suchfunktion hier das dauert in-- was bedeutet es in nehmen?
Was denken Sie?
So einfach.
Was ist das?
PUBLIKUM: [unverständlich].
Sprecher 1: Die Zahl, die wir suchen.
Richtig?
Und was würden es entsprechen?
Es ist ein Zeiger auf?
>> PUBLIKUM: Ein Knoten.
>> Sprecher 1: Ein Knoten in die Liste dass wir bei der rechten suchen?
So haben wir einige Knoten Zeiger sind hier.
Dies ist ein Punkt, der los ist tatsächlich durchlaufen unsere Liste.
Wir setzen sie gleich zur Liste denn das ist genau
Gleichsetzen mit der Start unserer verketteten Liste.
>> Und während es nicht NULL, während wir haben immer noch die Dinge in unserer Liste,
überprüfen Sie, ob dieser Knoten hat die Zahl, die wir suchen.
Return true.
Andernfalls aktualisieren Sie es, nicht wahr?
>> Wenn er NULL ist, verlassen wir unseren while-Schleife und return false
weil das bedeutet, wir haben es nicht gefunden.
Hat jeder bekommen, wie das funktioniert?
Ok.
>> Also mit Insertion, Sie drei verschiedene Arten.
Sie können voranstellen, können Sie anhängen können und Sie einfügen können in sortiert.
In diesem Fall sind wir Sich zu einem prepend tun.
Wer weiß, wie diejenigen, drei Fällen können sich unterscheiden?
>> So prepend bedeutet, dass Sie setzen es an der Vorderseite Ihrer Liste.
Also das würde bedeuten, dass, egal was Ihr Knoten ist, egal
was der Wert ist, du gehst die an dieser Stelle vor setzen, OK?
Es wird der erste sein Element in der Liste.
>> Wenn Sie es anhängen, es geht auf der Rückseite Ihrer Liste.
Und legen Sie in assorted bedeutet, dass Sie gehen, um tatsächlich an die Stelle setzen
wo es hält verknüpften Liste sortiert.
Wieder, wie Sie verwenden diejenigen, und wenn Sie verwenden
sie wird je nach Fall sehr unterschiedlich.
Wenn es nicht benötigen sortiert werden, neigt prepend
zu dem, was die meisten Menschen zu verwenden, da Sie dies nicht tun
haben, um durch die gesamte Liste zu gehen um das Ende, um es auf hinzufügen zu finden, richtig?
Sie können nur kleben sie direkt in.
>> So werden wir durch ein gehen Insertion 1 jetzt.
Also eine Sache, die ich zu gehen empfehlen auf dieser pset
ist es, die Dinge wie immer zu zeichnen.
Es ist sehr wichtig, dass Sie aktualisieren Ihre Zeiger in der richtigen Reihenfolge
denn wenn man sie zu aktualisieren etwas nicht in Ordnung,
Sie gehen, um am Ende bist verlieren Teile Ihrer Liste.
>> So zum Beispiel, in diesem Fall sind wir erzählt den Kopf, nur Punkt 1.
Wenn wir nur das tun, ohne Speichern dieses 1,
wir haben keine Ahnung, was 1 sollte jetzt zeigen
weil wir verloren haben, was der Kopf wies auf.
So eine Sache zu erinnern wenn du da einen prepend bist
ist es, was das Speichern Kopfpunkte auf ersten,
dann neu zuweisen, und dann aktualisieren was Ihre neue Knoten weisen auf.
In diesem Fall ist dies eine Möglichkeit, es zu tun.
>> Also, wenn wir es auf diese Weise getan hatte wo wir gerade neu zugewiesen Kopf,
verlieren wir im Grunde unseres gesamte Liste, oder?
Eine Möglichkeit, es zu tun ist, um 1 Punkt zu haben, nächsten, und dann haben Kopfpunkt bis 1.
Oder Sie eine Art, wie die tun können vorübergehende Speicherung, die ich darüber gesprochen.
>> Aber Bereich zuweist Zeiger in der richtigen Reihenfolge,
wird sehr, sehr sein wichtig für diese pset.
Ansonsten wirst du einen Hash haben sind Tisch oder einen Versuch, die gerade dabei ist zu sein
nur ein Teil der Wörter, die Sie wollen und dann you're-- mmhmm?
PUBLIKUM: Was war die vorübergehende Lagerung, was Sie redeten?
Sprecher 1: Der temporäre Speicher.
Also im Grunde ein weiterer so, wie Sie dies tun könnte
wird speichern Sie den Kopf von etwas, wie speichern sie die temporäre Variable.
Weisen Sie ihn auf 1 und dann aktualisieren Sie 1 zu Punkt
zu welchem ​​Kopf verwendet, um darauf hinzuweisen.
Auf diese Weise ist offensichtlich eleganter, weil Sie
nicht einen temporären Wert brauchen, aber nur bietet eine weitere Möglichkeit, es zu tun.
Und wir tatsächlich tun müssen ein Code für diese.
Also für verkettete Liste, die wir tatsächlich haben einige Code.
So übertragen Sie hier, dies ist das Voranstellen.
Also das geht es an die Spitze.
>> Also als erstes, brauchen Sie erstellen Sie Ihre neue Knoten, natürlich,
und überprüfen Sie NULL.
Immer gut.
Und dann müssen Sie die Werte zuordnen.
Wann immer Sie einen neuen Knoten zu erstellen, weiß nicht, was es als nächstes zu zeigen,
so dass Sie es zu initialisieren auf NULL möchten.
Wenn es am Ende auf etwas anderes, es wird neu zugewiesen, und es ist in Ordnung.
Wenn es das erste, was in der Liste, muss es
darauf zu, weil NULL das ist das Ende der Liste.
>> Also, um es einzufügen, sehen wir hier sind wir zuweisen den nächsten Wert der Knoten
zu sein, was auch immer Kopf ist, das ist, was wir hier hatten.
Das ist, was wir gerade getan.
Und dann sind wir die Zuordnung Kopf bis Punkt zu unserem neuen Knoten, denn denken Sie daran,
Neu ist einige Zeiger zu einem Knoten, und das ist genau das, was Kopf ist.
Das ist genau das, warum wir haben diese Pfeil-Zub.
Cool?
Mmhmm?
>> PUBLIKUM: Müssen wir initialisieren neue neben ersten Null,
oder können wir nur initialisieren, den Kopf?
>> Sprecher 1: New nächsten muss NULL zu starten, um sein
weil Sie nicht wissen, wo es sein wird.
Außerdem ist diese Art von Genau wie ein Paradigma.
Sie setzen es gleich NULL, nur um sicher sicher, dass alle Ihre Grundlagen abgedeckt
bevor Sie eine Neuzuweisung damit zu tun Sie immer, dass es garantiert
werden auf einen bestimmten Wert zeigt gegenüber wie ein Müllwert.
Weil, ja, wir ordnen neue nächste automatisch,
aber es ist mehr wie ein gute Übung, um es zu initialisieren
auf diese Weise, und dann neu zuweisen.
>> OK, also doppelt jetzt verkettete Listen.
Was denken wir?
Was ist anders bei doppelt verkettete Listen?
>> Also in unserem verkettete Listen, können wir nur in eine Richtung bewegen, oder?
Wir haben erst im nächsten.
Wir können nur vorwärts gehen.
>> Mit einer doppelt verketteten Liste wir können auch rückwärts bewegen.
So haben wir nicht nur die Zahl, die wir speichern wollen,
Wir haben, wo es zum nächsten Punkte und wo wir gerade von.
So ermöglicht dies einige besser Traversal.
>> Also doppelt verknüpften Knoten, sehr ähnlich, oder?
Der einzige Unterschied ist jetzt sind wir eine nächste und eine frühere.
Es ist der einzige Unterschied.
>> Also wenn wir voranstellen oder append-- wir keine Code dafür haben bis hier--
aber wenn Sie versuchen, waren und legen Sie sie, das Wichtigste
ist, dass Sie brauchen, um sicher, dass Sie die Zuordnung sind
sowohl Ihre bisherigen und Ihrer nächste Zeiger korrekt.
Also in diesem Fall, würden Sie nicht nur neben initialisieren,
Sie initialisieren vorherigen.
Wenn wir an der Spitze der Liste sind, wir würde nicht nur den Kopf gleich neue,
aber unsere neue vorherigen sollte weisen auf den Kopf, oder?
>> Das ist der einzige Unterschied.
Und wenn Sie mehr Übung mit wollen diese mit verknüpften Listen, mit Einfügen,
mit dem Löschen, mit Einsatz in eine sortierte Liste
überprüfen Sie bitte heraus study.cs50.net.
Es gibt ein paar tolle Übungen.
Ich empfehle ihnen.
Ich wünschte, wir Zeit, um durch sie gehen mussten aber es gibt eine Menge von Datenstrukturen
um durchzukommen.
>> OK, so Hash-Tabellen.
Dies ist wahrscheinlich die am meisten Nutzbit für Ihre pset
hier, weil du sein wirst Umsetzung einer von diesen, oder einen Versuch.
Ich mag Hash-Tabellen.
Sie sind ziemlich cool.
>> Also im Grunde, was geschieht, ist eine Hash-Tabelle,
ist, wenn wir wirklich brauchen schnelle Einfügen, Löschen und Lookup.
Das sind die Dinge, die wir sind Priorisierung in einer Hash-Tabelle.
Sie kann ziemlich groß, aber wie wir mit Versuchen zu sehen,
es gibt Dinge, die viel größer sind.
>> Aber im Grunde alles ein Hash Tabelle ist eine Hash-Funktion,
dass Ihnen sagt, welche Eimer zu jedem setzen Ihrer Daten, jede Ihrer Elemente.
Ein einfacher Weg, um eine Hash-Tabelle zu denken ist, dass es nur Eimer Dinge,
richtig?
Also, wenn Sie Sortier Dinge wie die ersten Buchstaben ihres Namens,
das ist wie eine Art von Hash-Tabelle.
>> Also, wenn ich zu einer Gruppe euch ist in Gruppen von wer Name beginnt
mit A hier, oder wer auch immer ist Geburtstag ist im Januar, Februar, März,
was auch immer, ist, dass effektiv Erstellen einer Hash-Tabelle.
Es ist nur die Schaffung Buckets, Sie Ihre Elemente in sortieren
so dass Sie sie leichter finden können.
Also auf diese Weise, wenn ich einer von euch zu finden,
Ich habe nicht zu suchen durch jede der Ihre Namen.
Ich kann wie, oh, ich weiß, dass Danielle Geburtstag ist in--
PUBLIKUM: --April.
Sprecher 1: April.
So sehe ich in meiner April Eimer, und mit etwas Glück,
sie wird die einzige in dort zu sein und meine Zeit war in diesem Sinne konstant,
während, wenn ich muss schauen durch eine ganze Reihe von Menschen,
es wird viel länger dauern.
So Hash-Tabellen sind wirklich nur Eimer.
Einfache Möglichkeit, von ihnen denken.
>> Also eine sehr wichtige Sache zu eine Hash-Tabelle ist eine Hash-Funktion.
So sind die Dinge, die ich gerade gesprochen, wie Ihre Anfangsbuchstaben Ihres Vornamens
oder Ihren Geburtstag Monat das sind Ideen, die
wirklich korrelieren Hashfunktion.
Es ist nur eine Möglichkeit, zu entscheiden, welche Eimer du bist Element in geht, OK?
Also für diese pset, können Sie nachschlagen ziemlich jede Hashfunktion Sie wollen.
>> Muss nicht Ihr eigenes sein.
Es gibt einige wirklich coole da draußen gibt, die alle möglichen verrückten Mathematik zu tun.
Und wenn Sie zu Ihrem machen wollen Rechtschreibprüfung super schnell,
Ich würde auf jeden Fall schauen Sie in einer von denen.
>> Aber es gibt auch das einfache, wie Compute
die Summe der Wörter, wie jeder Buchstabe hat eine Nummer.
Berechnen Sie die Summe.
Das bestimmt den Eimer.
Sie haben auch die einfachen diejenigen, sind genauso wie die gesamte A ist hier,
alle B ist hier.
Jeder von denen.
>> Grundsätzlich, es gerade erfahren Sie, welche Array-Index Ihr Element sollte in zu gehen.
Gerade der Entscheidung über die bucket-- es ist alles eine Hash-Funktion ist.
Hier haben wir also ein Beispiel, das ist nur der erste Buchstabe des Strings
dass ich nur darüber zu reden.
>> So dass Sie einige Hash, nur der ist haben Anfangsbuchstaben Ihres String minus A,
Sie haben dann einige Zahl zwischen 0 und 25.
Und was Sie tun möchten, ist stellen Sie sicher, dass dies
von der Größe Ihres Hash table-- wie viele Eimer gibt es.
Bei vielen dieser Hash-Funktionen, sie sind
gehen zu Werten zurück Das könnte weit über der Anzahl von Buckets
dass Sie tatsächlich in Ihrer Hash-Tabelle,
so müssen Sie sicherstellen, sicher und von denen, mod.
Ansonsten, es wird sagen: oh, sollte es in Eimer 5.000
aber Sie haben nur 30 Eimer in Ihrem Hash-Tabelle.
Und natürlich wissen wir alle, das ist werde in einigen verrückten Fehlern führen.
So stellen Sie sicher, dass Sie durch die MOD Größe Ihrer Hash-Tabelle.
Cool.
So Kollisionen.
Ist jeder gut so weit?
Mmhmm?
>> PUBLIKUM: Warum wäre es wie eine massive Wert zurückgeben?
>> Sprecher 1: Je nach Algorithmus dass Ihre Hash-Funktion verwendet.
Einige von ihnen werden zu tun verrückt Multiplikation.
Und es geht darum, eine gleichmäßige Verteilung,
so dass sie einige tun wirklich verrückte Dinge manchmal.
Das ist alles.
Noch etwas?
Ok.
>> So Kollisionen.
Grundsätzlich, wie ich bereits sagte, im besten Fall
einem Eimer I zu schauen ist gehen, um eine Sache zu haben,
so dass ich nicht haben, um überhaupt zu suchen, oder?
Ich weiß, es ist entweder da oder es ist nicht, und das ist, was wir wirklich wollen.
Aber wenn wir Zehntausende von Datenpunkten und weniger als diese Anzahl
von Eimern, wir gehen zu müssen, Kollisionen, wo schließlich etwas
wird sich in ein Ende zu haben, Schaufel, die bereits über ein Element.
>> Die Frage ist also, was wir in diesem Fall tun?
Was sollen wir tun?
Wir haben schon etwas gibt?
Haben wir nur werfen es aus?
>> Nein.
Wir müssen beide zu halten.
So ist die Art, wie wir typischerweise tun, ist was?
Was ist die Datenstruktur wir gerade darüber gesprochen?
PUBLIKUM: verketteten Liste.
Sprecher 1: Eine verkettete Liste.
So, jetzt, anstatt jede dieser Eimer nur mit einem Element,
es geht um eine verknüpfte Liste von enthalten die Elemente, die in sie gehasht wurden.
OK, nicht jeder Art von auf diese Idee?
Da könnten wir ein Array nicht weil wir nicht wissen, wie viele Dinge
gehen, um dort zu sein.
Eine verkettete Liste ermöglicht es uns, müssen nur die genaue Zahl,
werden in diesem Eimer gehasht, nicht wahr?
>> So linearen Austesten ist Im Grunde ist dies idea--
es ist ein Weg, um mit einer Kollision umzugehen.
Was Sie tun können, ist, wenn in diesem Fall wurde Beere in 1 gehasht
und wir haben bereits etwas da, man muss nur
weiterzumachen, bis finden Sie einen leeren Steckplatz.
Das ist ein Weg, damit umzugehen.
Die andere Weise zu hand ist es mit dem, was wir gerade
called-- die verknüpfte Liste nennt Verkettung.
>> Also diese Idee funktioniert, wenn Ihre Hash-Tabelle Sie denken
ist viel größer als Ihre Daten gesetzt oder wenn Sie
wollen versuchen, zu minimieren Verkettung bis es absolut notwendig ist.
So eine Sache ist linear Sondieren offensichtlich bedeutet
dass Ihre Hash-Funktion ist nicht so nützlich,
da wirst du am Ende mit gerade Ihre Hash-Funktion, immer bis zu einem Punkt,
Sie lineare zur Sonde nach unten einen Ort, der verfügbar ist.
Aber jetzt, natürlich, nichts sonst, landet dort,
Sie gehen zu müssen sind Suche noch weiter nach unten.
>> Und es gibt noch viel mehr Suchaufwand,
geht in die Eingabe ein Element in Ihrer Hash-Tabelle jetzt, nicht wahr?
Und jetzt, wenn Sie gehen und versuchen, und finden Beere wieder, du wirst es hash,
und es wird sagen: oh, in Eimer 1 suchen,
und es wird nicht zu sein im Eimer 1, so dass Sie
werde durchlaufen zu haben, durch den Rest davon.
So ist es manchmal sinnvoll, aber in den meisten Fällen,
wir gehen zu sagen, dass Verkettung ist, was Sie tun möchten.
>> Also sprachen wir über diese früher.
Ich habe ein wenig vor mich.
Aber Verkettung ist im Grunde, dass jeder Eimer in Ihrem Hash-Tabelle
ist nur eine verkettete Liste.
>> Also ein weiterer Weg, oder mehrere technische Weise zu einer Hash-Tabelle denken
ist, dass es nur ein Array von verknüpften Listen, die
wenn Sie schreiben Ihr Wörterbuch und Sie versuchen, es zu laden,
denken an sie als eine Array von verknüpften Listen
wird es viel einfacher für Sie zu initialisieren.
>> PUBLIKUM: Also Hash-Tabelle hat eine vorbestimmte Größe,
wie ein [unverständlich] von Eimern?
>> Sprecher 1: Richtig.
So hat es eine festgelegte Anzahl von Eimer, die Sie determine--
die Sie Jungs sollten fühlen Sie sich frei, um mit zu spielen.
Es kann ziemlich cool sein um zu sehen, was passiert,
wie Sie Ihre Anzahl von Eimern ändern.
Aber ja, es hat ein festgelegte Anzahl von Eimern.
Was können Sie als fit viele Elemente, wie Sie benötigen
ist dieser separate Verkettung wo Sie haben Listen in jedem Eimer verbunden.
Das heißt, Ihr Hash-Tabelle genau die Größe haben
dass Sie es brauchen, oder?
Das ist der ganze Sinn der verknüpften Listen.
Cool.
>> So kann jeder OK gibt?
In Ordnung.
Ah.
Was ist passiert?
Wirklich jetzt.
Ratet mal, jemand bringt mich um.
>> OK, wir werden in zu gehen Versuche, die ein wenig verrückt.
Ich mag Hash-Tabellen.
Ich denke, sie sind wirklich cool.
Tries sind cool, auch.
>> Also hat jemand daran erinnern, was einen Versuch ist?
Sie sollten über gegangen kurz in der Vorlesung?
Erinnern Sie sich an eine Art, wie es funktioniert?
PUBLIKUM: Ich bin nur nickend dass wir nicht über sie gehen.
Sprecher 1: Wir wissen über sie gehen.
OK, wir sind wirklich zu gehen über es jetzt ist, was wir sagen.
>> PUBLIKUM: Das ist für einen Abruf Baum.
>> Sprecher 1: Ja.
Es ist ein Abruf Baum.
Ehrfürchtig.
So eine Sache, hier zu bemerken ist, dass wir sind an den einzelnen Zeichen suchen
hier, nicht wahr?
>> Also, bevor mit unseren Hash-Funktion, die wir wurden bei den Wörtern als Ganzes suchen,
und jetzt sind wir mehr suchen an den Zeichen, oder?
So haben wir Maxwell hier und Mendel.
Also im Grunde ein try-- eine Möglichkeit zu denken, dabei ist, dass jede Ebene hier
eine Anordnung von Buchstaben.
Das ist also Ihr Root-Knoten hier, nicht wahr?
Das hat alle Zeichen der Alphabet für den Beginn jedes Wort.
>> Und was Sie tun möchten, ist sagen, OK, haben wir einige M-Wort.
Wir werden für Maxwell aussehen, so gehen wir in M. Und M zeigt auf eine ganze
andere ein Array, in dem jedes Wort, solange
ist ein Wort, A als zweiten Buchstaben,
Solange es ein Wort, hat B als zweiten Buchstaben,
es wird einen Zeiger haben werde einige nächsten Array.
>> Wahrscheinlich gibt es kein Wort, das MP etwas,
so an der P-Position in dieser Array, wäre es nur NULL sein.
Es würde sagen, OK, es gibt kein Wort das hat M gefolgt von einer P, OK?
Also, wenn wir darüber, jeder denken eines dieser kleinen Dinge
ist eigentlich einer von ihnen große Arrays von A bis Z.
Also, was könnte eines der Dinge sein dass ist eine Art Nachteil versuchen?
>> PUBLIKUM: Viel Speicher.
>> Sprecher 1: Es ist eine Tonne des Gedächtnisses, nicht wahr?
Jeder dieser Blöcke hier stellt 26 Plätze, 26 Elementanordnung.
So erhalten versucht unglaublich Raum schwer.
>> Aber sie sind sehr schnell.
So unglaublich schnell, aber wirklich Raum ineffizient.
Art haben, um heraus, welches wünschen Sie.
Dies sind wirklich cool für Ihre pset, aber sie nehmen viel Speicher,
so dass Sie einen Kompromiss.
Ja?
>> PUBLIKUM: Wäre es möglich, einzurichten versuchen und dann
sobald Sie alle Daten darin, dass Sie need--
Ich weiß nicht, ob das Sinn machen würde.
Ich war loszuwerden alle NULL-Zeichen, aber dann
Sie würden nicht in der Lage, Index them-- sein
>> Sprecher 1: Sie brauchen sie noch.
>> PUBLIKUM: - auf die gleiche Weise jedes Mal.
Sprecher 1: Ja.
Sie benötigen die NULL-Zeichen zu lassen Sie wissen, ob es nicht ein Wort gibt.
Ben hatten Sie etwas, was Sie wollen?
Ok.
Alles klar, also werden wir um ein bisschen mehr gehen
in die technischen Details hinter ausprobieren und die Arbeit durch ein Beispiel.
>> OK, das ist so die gleiche Sache.
Während in einer verketteten Liste, unser Haupt Art von-- was ist das Wort ich will? -
wie Gebäudeblock war ein Knoten.
In einem Versuch, haben wir auch einen Knoten, aber es ist anders definiert.
>> Also haben wir etwas bool dass stellt dar, ob ein Wort tatsächlich
existiert an diesem Ort, und dann wir haben einige Array hier-- oder besser gesagt,
Dies ist ein Zeiger auf eine Array von 27 Zeichen.
Und dies ist für die, in diesem Fall diese 27-- Ich bin sicher, alle von euch, wie sind, warten,
es gibt 26 Buchstaben im Alphabet.
Warum haben wir 27?
>> Also je nach dem so, wie Sie diese umsetzen,
dies ist aus einem pset dass für Apostrophe erlaubt.
Also das ist, warum die extra ein.
Sie werden auch in einige haben Fällen das Nullabschluss
wird als eine der mitgelieferten Zeichen, die es erlaubt zu sein,
und das ist, wie sie zu überprüfen, um sehen, ob es das Ende des Wortes.
Wenn Sie daran interessiert sind, lesen Sie Kevins Video auf study.cs50,
sowie Wikipedia hat einige gute Ressourcen gibt.
>> Aber wir werden durch nur irgendwie gehen dafür, wie Sie durch einen Versuch zu arbeiten
wenn Sie einen bestimmten bist.
So haben wir eine super einfach hier, dass hat die Wörter "Fledermaus" und "Zoom" in ihnen.
Und wie wir hier oben sehen diese wenig Platz hier
stellt unsere bool dass sagt, ja, das ist ein Wort.
Und dann hat diese unsere Arrays von Zeichen, oder?
>> So werden wir zu durchlaufen Suche nach "Fledermaus" in diesem Versuch.
So beginnen an der Spitze, nicht wahr?
Und wir wissen, dass b entspricht der zweite Index, das zweite Element
in dieser Anordnung, weil a und b.
So etwa die zweite.
>> Und er sagt, OK, cool, folgen, dass in der nächste Array, denn wenn wir uns daran erinnern,
es ist nicht so, dass jeder von diesen tatsächlich enthält das Element.
Jedes dieser Arrays enthält einen Zeiger, nicht wahr?
Es ist eine wichtige Unterscheidung zu machen.
>> Ich weiß, das wird be-- Versuche sind wirklich schwer, auf der ersten Zeit zu bekommen,
Selbst wenn dies der zweiten oder dritten Zeit
und es ist immer noch Art scheinbarer schwierig,
Ich verspreche, wenn Sie Uhr gehen die kurze morgen wieder,
es wird wahrscheinlich machen viel mehr Sinn.
Es braucht eine Menge zu verdauen.
Ich immer noch manchmal bin wie, warte, was ist einen Versuch?
Wie benutze ich das?
>> Also haben wir in diesem Fall B haben, Das ist unsere zweite Index.
Wenn wir, sagen wir, c oder d oder jede andere Brief,
wir müssen diese zurück zum Index Karte der unser Angebot, dass entspricht.
So möchten wir rchar nehmen und wir haben gerade subtrahieren ab, um sie in 0 Karte bis 25.
Jeder gute, wie wir Karte unsere Charaktere?
Ok.
>> So gehen wir in die zweite und wir sehen, dass, ja, es ist nicht auf NULL.
Wir können fahren Sie mit diesem nächsten Array.
Also wir gehen auf diese nächste Array hier.
>> Und wir sagen, OK, jetzt sind wir müssen sehen, ob eine ist hier.
Ist ein Null oder tut es tatsächlich vorwärts zu bewegen?
Also ein wirklich bewegt mitteln in diesem Array.
Und wir sagen, OK, t ist unser letzter Brief.
Also gehen wir zum t bei dem Index.
Und dann nach vorne bewegen wir uns denn es ist noch einer.
Und dieser im Grunde sagt, dass, ja, es sagt, dass es ein Wort hier--
dass, wenn Sie diese folgen Pfad, Sie sind angekommen
auf ein Wort, das wir wissen, ist, "bat."
Ja?
>> PUBLIKUM: Ist es üblich, dass haben als Index 0 und dann eine Art bei 1 haben
oder am Ende haben?
>> Sprecher 1: No.
Also, wenn wir zurückblicken auf unsere Erklärung hier, es ist ein bool,
so ist es seine eigene Element in Ihrem Knoten.
Es ist also nicht Teil des Arrays.
Cool.
Also, wenn wir fertig unser Wort und wir sind in diesem Array, was wir tun wollen
ist zu tun einen Scheck für das ist ein Wort.
Und in diesem Fall wäre es ja zurück.
>> Also in diesem Sinne, wir wissen, dass "Zoo" - wir wissen, wie die Menschen, dass "Zoo" ist ein Wort,
richtig?
Aber hier versuchen würden sagen, nein, ist es nicht.
Und es wäre das zu sagen, weil wir habe es nicht als Wort hier bezeichnet.
Auch wenn wir durchqueren können durch diese Anordnung,
Dieser Versuch würde sagen, dass, nein, Zoo ist nicht in Ihrem Wörterbuch
weil wir nicht sie als solche bezeichnet.
>> So ein Weg, um zu tun dass-- oh, Entschuldigung, das hier ein.
Also in diesem Fall ist "Zoo" nicht ein Wort, aber es ist in unserem Versuch.
Aber in diesem einen, sagen wir es wollen Einführung das Wort "Bad", was passiert,
ist folgen wir through-- B, A, t.
Wir sind in diesem Array und wir gehen, um h zu suchen.
>> In diesem Fall, wenn wir Blick auf die Zeiger an h,
es ist auf NULL zeigt, OK?
Also, es sei denn, es ist explizit deutete auf ein anderes Array,
Sie gehen davon aus, dass alle Zeiger in diesem Array sind, die auf null gesetzt.
Also in diesem Fall, ist h zeigen auf null, so dass wir nichts tun,
so wäre es auch zurück false, "Bad" ist nicht hier.
So, jetzt sind wir wirklich gehen zu durchlaufen
wie würden wir tatsächlich sagen, dass "Zoo" ist in unserem Versuch.
Wie können wir "Zoo" insert into unserem Versuch?
Also in der gleichen Weise, wie wir mit gestartet unsere verketteten Liste, beginnen wir an der Wurzel.
Wenn Sie Zweifel haben, beginnen bei die Wurzel von diesen Dingen.
>> Und wir werden sagen, OK, z.
z besteht darin, und es tut.
So können Sie in Bewegung sind an Ihre nächste Array, OK?
Und dann auf die nächste, wir sagen, OK, hat o existieren?
Es tut.
Diese erneut.
>> Und so weiter unsere nächste, haben wir gesagt, OK, "Zoo" ist bereits hier.
Alles, was wir tun müssen, ist dies gleichgesetzt wahr, daß es ein Wort gibt.
Wenn Sie hatte alles, gefolgt bis vor diesem Punkt,
Es ist ein Wort, so dass nur stellen Sie es gleich wie.
Ja?
>> PUBLIKUM: Also tut bedeuten, dass "ba" ist ein Wort, auch?
>> Sprecher 1: No.
Also in diesem Fall, "ba" würden wir bekommen Hier würden wir sagen, es ist ein Wort,
und es wäre immer noch nicht.
OK?
Mmhmm?
>> PUBLIKUM: Also, wenn Sie es ist ein Wort und Sie sagen, ja, dann ist es
enthalten wird, um m zu gehen?
>> Sprecher 1: Also das zu tun hat with-- Sie beim Laden des gerade in.
Sie sagen, "Zoo" ist ein Wort.
Wenn Sie gehen, um check-- wie, sagen Sie sagen wollen,
bedeutet "Zoo" in diesem Wörterbuch existieren?
Sie sind nur gehen, um nach "Zoo" und dann überprüfen, ob es ein Wort.
Du wirst nie zu bewegen bis hin zu m, weil das ist nicht
was Sie suchen.
>> Also, wenn wir eigentlich wollten hinzufügen "Bad" in diesem Versuch,
wir würden das gleiche tun wie wir mit did "Zoo"
außer wir würden sehen, dass, wenn wir versuchen, bis h, existiert es nicht.
Also du davon kann als Versuch einen neuen Knoten in einer verknüpften Liste hinzuzufügen,
so müssten wir eine weitere hinzufügen eine dieser Anordnungen, wie so.
Und dann, was wir tun, ist uns gerade die h eingestellt Element dieser Anordnung, die auf diese.
>> Und was wäre dann wollen wir hier tun?
Fügen Sie es gleich wahr denn es ist ein Wort.
Cool.
Ich weiß.
Tries sind nicht die aufregendste.
Vertrauen Sie mir, ich weiß.
>> So eine Sache, mit Versuchen zu realisieren, Ich sagte, sie sind sehr effizient.
Also haben wir sie gesehen haben nehmen eine Tonne Raum.
Sie sind irgendwie verwirrend.
Also warum sollten wir jemals nutzen diese?
Wir verwenden diese, weil sie unglaublich effizient.
>> Also, wenn Sie jemals suchen ein Wort, nur bist du
durch die Länge des Wortes begrenzt.
Also, wenn Sie für eine suchen Wort, das der Länge fünf ist,
Sie nur jemals zu haben machen höchstens fünf Vergleiche, OK?
So macht es im Grunde eine Konstante.
Wie Einfügen und Suchen sind grundsätzlich konstante Zeit.
>> Also, wenn Sie jemals bekommen kann etwas in konstanter Zeit,
das ist so gut wie es geht.
Sie können nicht besser als zu bekommen konstante Zeit für diese Dinge.
Damit ist eine der riesige Pluspunkte der Versuche.
>> Aber es ist viel Platz.
So können Sie Art zu entscheiden haben, Was ist Ihnen wichtiger.
Und am heutigen Computern, die Raum, einen Versuch kann aufnehmen
vielleicht nicht beeinträchtigt Sie so viel, aber vielleicht
Sie mit etwas zu tun das hat weit, weit mehr Dinge,
und einen Versuch ist einfach nicht angemessen.
Ja?
>> PUBLIKUM: Warten Sie, so dass Sie 26 haben Buchstaben in jedem einzelnen?
>> Sprecher 1: Mmhmm.
Ja, Sie haben 26.
Sie haben einige ist Wortmarkierung und dann Sie haben 26 Zeiger in jedem.
Und sie point--
>> PUBLIKUM: Und jeder 26, sie haben jeweils 26?
>> Sprecher 1: Ja.
Und deshalb, wie Sie können sehen, es ziemlich schnell expandiert.
In Ordnung.
Also wir werden in Bäume zu erhalten, welches Ich fühle mich wie erleichtert und wird wahrscheinlich
sein eine nette kleine Atempause aus versucht es.
So hoffentlich die meisten von euch haben einen Baum gesehen.
Nicht wie der hübsche Wieder draußen, die ich
weiß nicht, ob jemand ging draußen vor kurzem.
Ich ging Apfelernte dieses Wochenende und oh mein Gott, es war wunderschön.
Ich wusste nicht, Blätter könnte das hübsch aussehen.
>> Also das ist nur ein Baum, oder?
Es ist nur einige Knoten, und es verweist auf eine Reihe von anderen Knoten.
Wie Sie hier sehen, ist dies eine Art wiederkehrendes Thema.
Knoten, der auf Knoten ist eine Art das Wesen der vielen Datenstrukturen.
Es kommt nur darauf an, wie wir haben sie weisen zueinander
und wie wir durchqueren durch sie und wie wir
einfügen Dinge, die bestimmt, ihrer unterschiedlichen Eigenschaften.
>> Also nur einige Begriffe, die ich vorher benutzt.
Also Wurzel ist, was auch immer an der Spitze.
es ist, wo wir immer starten.
Man kann sich das wie der Kopf auch denken.
Aber für Bäume, neigen wir dazu, bezeichnen es als die Wurzel.
>> Alles an der Unterseite hier-- bei sehr, sehr bottom--
sind als Blätter.
So geht es zusammen mit dem ganzen Baum Sache, nicht wahr?
Die Blätter sind an den Rändern der Ihren Baum.
>> Und dann haben wir auch ein paar Begriffe, über Knoten in Beziehung sprechen
zueinander.
So haben wir Eltern, Kinder und Geschwister.
So dass in diesem Fall 3 ist das Mutter von 5, 6 und 7.
So ist die Muttergesellschaft ist, was auch immer eine Stufe über, was auch immer du bist
Bezugnahme auf, so dass nur wie ein Stammbaum.
Hoffentlich ist das alles ein wenig Bit intuitiver als die Versuche.
>> Geschwister sind alle, die haben die gleichen übergeordneten, nicht wahr?
Sie sind auf dem gleichen Niveau hier.
Und dann, als ich sagen, sind gerade Kinder
was immer eine Stufe unter der Knoten in Frage, OK?
Cool.
So ein binärer Baum.
Kann mir jemand eine Vermutung auf eine der die Eigenschaften des binären Baum?
>> PUBLIKUM: Max zwei Blätter.
>> Sprecher 1: Richtig.
Also max von zwei Blättern.
Also in dieser vor, diesen einen hatten wir dass hatte drei, aber in einem binären Baum,
Sie ein Maximum von zwei haben Kinder pro Elternteil, oder?
Es gibt eine andere interessante Eigenschaft.
Kennt jemand das?
Binary Tree.
>> So ein binärer Baum wird alles haben auf the-- dieses ist nicht sorted--
aber in einer sortierten binären Baum, alles auf der rechten
größer ist als die Ausgangs, und alles, was auf der linken
ist kleiner als die Eltern.
Und das ist ein Quiz Frage vor, so gut zu wissen.
So ist die Art, wie wir diese zu definieren, wieder haben wir einen weiteren Knoten.
Das sieht sehr ähnlich, was?
Doppelt
>> PUBLIKUM: Verknüpfte Listen
>> Sprecher 1: Ein Doppel verketteten Liste, oder?
Also, wenn wir diese ersetzen mit vorherigen und nächsten,
dies wäre eine doppelt verkettete Liste sein.
Aber in diesem Fall haben wir tatsächlich nach links und rechts und das ist es.
Ansonsten ist es genau das gleiche.
Wir haben immer noch das Element Sie suchen,
und Sie müssen nur zwei Zeiger werde, was auch immer als nächstes kommt.
Ja, also binäre Suchbaum.
Wenn wir bemerken, alles auf die hier ist größer than--
oder alles sofort nach rechts hier
größer als alles hier ist weniger als.
>> Also, wenn wir waren zu durchsuchen sie, sollte sehr nah an binäre Such aussehen
hier, nicht wahr?
Außer statt der Suche bei der Hälfte der Anordnung,
wir gerade auf der Suche entweder an der linken Seite oder der rechten Seite des Baumes.
So ist es ein wenig einfacher wird, denke ich.
>> Also, wenn Ihr Root NULL ist, offensichtlich ist es nur falsch.
Und wenn es da ist, es ist offensichtlich wahr.
Wenn es weniger als suchen wir nach links.
Wenn es größer als ist, wir suchen das richtige.
Es ist genau wie binäre Suche, nur eine andere Datenstruktur
dass wir mit.
Anstelle einer Anordnung, es ist nur ein binärer Baum.
>> OK, stapelt.
Und auch, es sieht aus wie wir vielleicht haben ein wenig Zeit.
Wenn wir das tun, bin ich glücklich zu gehen über irgendwelche von diesem wieder.
OK, so stapelt.
Erinnert sich noch jemand, was stacks-- von Eigenschaften eines Stapels?
>> OK, so dass die meisten von uns, denke ich, essen im Speisesaal halls--
so viel wie wir können nicht gern.
Aber offensichtlich können Sie aus einem Stapel denken können buchstäblich nur als ein Stapel von Tabletts
oder ein Stapel der Dinge.
Und was wichtig ist zu erkennen ist, dass es
something-- die charakteristische dass wir nennen es nach-- ist LIFO.
Weiß jemand, was das steht?
Mmhmm?
>> PUBLIKUM: last in, first out.
>> Sprecher 1: Richtig, last in, first out.
Also, wenn wir wissen, ob wir das Stapeln Dinge up, die einfachste Sache zu packen off--
und vielleicht das einzige, was wir greifen können aus, wenn unsere Stapel ist groß enough--
ist, dass Top-Element.
Also was auch immer wurde angelegt last-- wie wir hier sehen,
was auch immer geschoben wurde auf den meisten recently-- ist
werde der Erste sein Sache, die wir Pop weg, OK?
>> Also, was wir hier haben, ist weiteres typedef struct.
Das ist wirklich nur wie ein Crash-Kurs in der Datenstruktur,
so gibt es eine Menge an euch geworfen.
Ich weiß.
Also noch eine weitere Struktur.
Yay für Strukturen.
>> Und in diesem Fall ist es einige Zeiger auf ein Array, die eine gewisse Kapazität hat.
Also das steht für unsere Stack hier, wie unsere tatsächlichen Array
dass hält unseren Elementen.
Und dann haben wir hier einige Größe.
>> Und in der Regel, behalten möchten Sie Verfolgen Sie, wie groß Ihr Stack ist
denn was es geht, damit Sie zu tun ist, wenn Sie die Größe kennen,
es erlaubt Ihnen zu sagen, OK, ich bin an der Kapazitätsgrenze?
Kann ich etwas mehr hinzufügen?
Und es sagt Ihnen auch, wo die Spitze Ihres Stacks
ist, so dass Sie wissen, was Sie kann tatsächlich ausziehen.
Und das ist eigentlich los, um sein hier ein wenig klarer.
>> Also für Push, eine Sache, wenn Sie waren jemals Push implementieren,
wie ich sagte gerade, Ihre Stapel eine begrenzte Größe, oder?
Unser Angebot hatten einige Kapazitäten.
Es ist ein Array.
Es ist eine feste Größe, so müssen wir stellen Sie sicher, dass wir nicht setzen mehr
in unser Angebot, als wir tatsächlich haben Platz für.
>> Also, wenn Sie ein Push bist Funktion, erste, was Sie tun, ist sagen, OK,
muss ich Platz in meinem Stack?
Denn wenn ich nicht, sorry, Ich kann Ihre Element nicht speichern.
Wenn ich das tue, dann Sie speichern möchten es an der Spitze des Stapels, nicht wahr?
>> Und das ist, warum wir den Überblick über unsere Größe zu halten.
Wenn wir nicht den Überblick über unsere Größe zu halten, wir wissen nicht, wohin damit.
Wir wissen nicht, wie viele Dinge sind bereits unser Angebot.
Wie offensichtlich gibt es Möglichkeiten dass vielleicht Sie es tun könnte.
Man konnte alles zu initialisieren auf NULL und überprüfen Sie dann für die neueste NULL,
aber eine viel einfachere Sache ist nur zu sagen, OK, verfolgen Größe.
Wie ich weiß, ich habe vier Elemente in meinem Array, so dass die nächste Sache
dass wir anziehen, wir sind werde bei Index 4 zu speichern.
Und dann natürlich bedeutet dies, dass Sie haben erfolgreich etwas geschoben
auf Ihren Stack, Sie wollen, um die Größe zu erhöhen
so dass Sie wissen, wo Sie so sind dass man mehr Dinge auf zu drücken.
>> Also, wenn wir versuchen, Pop etwas vom Stapel,
was vielleicht das erste, was sein dass wir wollen für überprüfen?
Sie versuchen, zu nehmen etwas aus Ihrem Stack.
Sind Sie sicher, es gibt etwas in Ihrem Stack?
Nein.
Also, was können wir prüfen wollen?
>> PUBLIKUM: [unverständlich].
Sprecher 1: Überprüfen Sie für die Größe?
Größe.
Also, um zu überprüfen, um zu sehen, ob wir wollen unsere Größe ist größer als 0, OK?
Und wenn ja, dann zu verringern wollen wir unserer Größe von 0 und zurück, dass.
Warum?
>> In der ersten wurden wir Schieben, geschoben wir
auf Größe und dann aktualisiert Größe.
In diesem Fall sind wir Dekrementieren Größe und dann nehmen sie ab, Zupfen
von unserem Array.
Warum könnten wir das tun?
Also wenn ich eine Sache auf meinem Stapel, was würden meine Größe an diesem Punkt sein?
1.
>> Und wo ist das Element 1 gespeichert?
Bei welcher Index?
PUBLIKUM: 0.
Sprecher 1: 0.
So dass in diesem Fall haben wir immer brauchen, um sure--
Statt der Rücksendung Größe minus 1, da wir
wissen, dass unser Element in Zukunft an ein weniger gespeichert werden
was auch immer unsere Größe ist, diese dauert nur kümmern.
Es ist eine etwas elegantere Möglichkeit.
Und wir verringern unseren Größe und dann wieder groß.
Mmhmm?
>> PUBLIKUM: Ich denke, gerade im Allgemeinen, warum sollte diese Datenstruktur
von Vorteil?
>> Sprecher 1: Es hängt von Ihrem Kontext.
So dass für einige der Theorie, wenn Sie with-- OK arbeiten,
lassen Sie mich sehen, ob es einen Vorteil ein das ist vorteilhaft, mehr als außerhalb
von CS.
Mit Stapeln, jedes Mal, wenn Sie zu verfolgen, etwas zu behalten, dass
wird der zuletzt hinzugefügt wird, wenn wirst du zu einem Stapel verwenden möchten.
>> Und ich kann nicht von einem guten denken Beispiel, dass gerade jetzt.
Aber wann immer die aktuellste Sache ist für Sie am wichtigsten,
das ist, wenn ein Stapel wird, nützlich zu sein.
Ich versuche, wenn denken gibt es ein gutes Jahr für diese.
Wenn ich daran denke, ein gutes Beispiel in der nächsten 20 Minuten, werde ich auf jeden Fall sagen.
>> Aber insgesamt, ob es etwas gibt, wie ich sagte, die meisten, wo die meisten den letzten
am wichtigsten ist, das ist wobei ein Stapel ins Spiel kommt.
Während Warteschlangen sind so eine Art das Gegenteil.
Und all die kleinen Hunde.
Ist das nicht großartig, nicht wahr?
Ich fühle mich wie ich sollte einfach nur einen bunny Video
mitten in der Abschnitt für euch
denn dies ist eine intensive Schnitt.
>> So eine Warteschlange.
Grundsätzlich eine Warteschlange wie eine Linie.
You guys Ich bin sicher, nutzen diese täglich, Wie auch in unseren Mensen.
Also müssen wir in gehen und erhalten Sie unsere Tabletts, ich bin
sicher, dass Sie in der Schlange warten müssen zu streichen oder du bekommst dein Essen.
>> So ist der Unterschied hier ist, dass dieses FIFO.
Also, wenn LIFO wurde zuletzt in, first out, FIFO ist first in, first out.
Also das ist, wo auch immer Sie setzen am ersten ist Ihre wichtigste.
Also, wenn Sie warteten in einem line-- können Sie
vorstellen, wenn Sie ging zu hol Dir das neue iPhone
und es war ein Stapel, wo die Letzte in der Schlange stand es zunächst,
Menschen würden sich gegenseitig umbringen.
>> So FIFO, wir sind alle sehr vertraut mit hier die reale Welt,
und das alles mit eigentlich zu tun hat Art von Neuer diese ganze Linie
und Queuing-Struktur.
Während also mit dem Stapel, Wir haben Push und Pop.
Mit einer Warteschlange, haben wir Enqueue und dequeue.
So Enqueue im Grunde bedeutet, legte sie auf den Rücken,
und dequeue Mittel nehmen von der Vorderseite.
Also unsere Datenstruktur ist ein wenig komplizierter.
Wir haben eine zweite Sache, um zu verfolgen.
>> Also ohne Kopf, diese Genau ein Stapel, nicht wahr?
Dies ist die gleiche Struktur, wie einem Stapel.
Der einzige Unterschied ist, dass wir jetzt haben diese Kopf, der, was glauben Sie,
wird, um zu verfolgen?
>> PUBLIKUM: Der erste.
>> Sprecher 1: Richtig, das Erste, was wir in.
Der Leiter unserer Warteschlange.
Wer ist in der ersten Reihe.
Na gut, also, wenn wir tun, Enqueue.
Wieder mit einem Diese Datenstrukturen,
da wir mit einer Reihe zu tun haben, Wir müssen prüfen, ob wir haben Platz.
>> Dies ist eine Art, wie mir erzählt Sie Jungs, wenn Sie eine Datei öffnen,
müssen Sie für null überprüfen.
Bei jeder dieser Stacks und Warteschlangen, müssen Sie
zu sehen, ob es Raum, weil wir die sich mit einer festen Größe Array,
wie wir sehen hier-- 0, 1 alle bis zu 5.
Also, was wir in diesem Fall zu tun ist Check zu sehen, ob wir noch Platz.
Ist unsere Größe von weniger als Kapazität?
>> Wenn dem so ist, müssen wir es speichern der Schwanz, und wir aktualisieren unsere Größe.
So was kann der Schwanz in diesem Fall?
Es ist nicht explizit ausgeschrieben.
Wie würden wir es lagern?
Was würde der Schwanz sein?
>> Also lassen Sie uns dieses Beispiel gehen.
Das ist also ein Array der Größe 6, nicht wahr?
Und wir haben gerade jetzt ist unsere Größe 5.
Und wenn wir es in, es geht bis in die fünfte Index, gehen Sie nach rechts?
So speichern bei Schwanz.
>> Eine weitere Möglichkeit, Schwanz schreiben möchte nur sein unser Angebot an Index der Größe, nicht wahr?
Das ist Größe 5.
Das nächste, was los ist in 5 zu gehen.
Cool?
Ok.
Es wird etwas komplizierter wenn wir anfangen Unordnung mit dem Kopf.
Ja?
>> PUBLIKUM: Heißt das, dass wir würde ein Array erklärt haben, dass
war fünf Elemente lang und dann wir hinzufügen auf sie?
>> Sprecher 1: No.
So dass in diesem Fall ist dies ein Stapel.
Dies würde erklären als ein Array von der Größe 6.
Und in diesem Fall haben wir nur noch eine Stelle nach links.
>> OK, so eine Sache ist in diesem Fall, wenn unser Kopf ist bei 0,
dann nur, wir können ihn unter Größe hinzuzufügen.
Aber es ist ein wenig komplizierter wird denn eigentlich, sie
keine Rutsche für dieses, so werde ich
zu einem Unentschieden, weil es nicht Ganz so einfach, sobald man
anfangen, von Dingen zu befreien.
Während also mit einem Stapel Sie immer nur
über das, was die Größe ist Sorge wenn Sie etwas Zugabe auf,
mit einer Warteschlange, die Sie müssen auch sicherstellen, Sie sicher, dass Sie Ihren Kopf wird berücksichtigt,
weil eine coole Sache, über Warteschlangen ist, dass, wenn Sie an der Kapazitätsgrenze sind nicht,
Sie können tatsächlich machen es umschlingen.
>> OK, so ein thing-- oh, Das ist schrecklich Kreide.
Eine Sache zu prüfen, ist der Fall.
Wir müssen nur fünf tun.
OK, so werden wir sagen, der Kopf ist hier.
Dies ist 0, 1, 2, 3, 4.
>> Der Kopf ist da, und Sie haben sich die Dinge in ihnen.
Und wir wollen etwas in hinzuzufügen, oder?
Also das, was wir brauchen, um wissen ist, dass der Kopf ist immer
werde auf diese Weise bewegen und dann die Schleife wieder um, OK?
>> Also diese Warteschlange hat Platz, oder?
Es bietet Platz ganz am Anfang, Art der gegenüberliegenden hierfür.
Also, was wir tun müssen, ist, dass wir brauchen, um den Schwanz zu berechnen.
Wenn Sie wissen, dass Ihr Kopf hat sich nicht bewegt, Schwanz
ist nur Ihr Array bei der Index der Größe.
>> Aber in Wirklichkeit, wenn Sie mit einer Warteschlange, Ihr Kopf ist wahrscheinlich aktualisiert.
Also, was Sie tun müssen, ist tatsächlich berechnen den Schwanz.
Also, was wir tun, ist diese Formel hier, die ich werde dich lassen
Jungs denken Sie, und dann werden wir darüber reden.
Das ist also Kapazität.
>> So wird dies tatsächlich geben Ihnen einen Weg, es zu tun.
Weil in diesem Fall, was?
Unser Hauptsitz ist in 1 ist unsere Größe 4.
Wenn wir Mod, um 5, 0 erhalten wir, das ist, wo wir sollten Eingangs es.
>> Also in den nächsten Fall, Wenn wir dies tun sollten,
wir sagen, OK, lass uns etwas aus der Warteschlange entfernt.
Wir aus der Warteschlange entfernt diese.
Wir nehmen Sie dieses Element, nicht wahr?
>> Und nun unser Kopf ist hier zeigt, und wir wollen in einer anderen Sache hinzuzufügen.
Dies ist im Grunde das Rücken unserer Linie, nicht wahr?
Warteschlangen können um die Anordnung zu wickeln.
Das ist einer der Hauptunterschiede.
Stacks, können Sie nicht tun.
>> Mit Warteschlangen können Sie denn alles, was zählt
ist, dass Sie wissen, was wurde zuletzt hinzugefügt.
Da alles wird sich in hinzugefügt werden Diese Linksrichtung, in diesem Fall
und dann herum wickeln, können Sie weiterhin, das in neue Elemente
an der Vorderseite der Anordnung denn es ist nicht wirklich
die vor dem Array mehr.
Sie können der Beginn der Meinung Array als wo Ihr Kopf tatsächlich ist.
>> Also diese Formel ist, wie Sie berechnen Ihren Schwanz.
Macht das Sinn macht?
Ok.
OK, dequeue und dann Sie Kerle haben 10 Minuten
zu fragen mich keine klärende Fragen Sie wollen, weil ich weiß, es ist verrückt.
>> Na gut, so in der gleichen way-- Ich weiß nicht, ob euch aufgefallen,
aber CS ist alles über Muster.
Die Dinge sind so ziemlich das gleiche, nur mit winzigen zwickt.
Also dasselbe hier.
Wir müssen prüfen, ob wir tatsächlich sehen haben etwas in unserer Warteschlange, oder?
Sagen, OK, ist unsere Größe größer als 0?
Cool.
>> Wenn wir das tun, dann haben wir unseren Kopf, bewegen was ist das, was ich gerade hier demonstriert.
Wir aktualisieren unsere Kopf zu sein noch einen.
Und dann verringern wir unsere Größe und senden Sie das Element.
>> Es ist viel konkreter Code auf study.cs50.net,
und ich kann nur empfehlen dahin durch sie, wenn Sie Zeit haben,
auch wenn es nur ein Pseudo-Code.
Und wenn du Jungs wollen durch reden dass mit mir eins zu eins, informieren Sie mich
kennen.
Ich würde glücklich sein.
Datenstrukturen, falls Sie CS 124 werfen, werden Sie
wissen, dass Datenstrukturen werden sehr Spaß und das ist erst der Anfang.
>> Also ich weiß, es ist schwer.
Es ist in Ordnung.
Wir kämpfen.
Ich immer noch.
Also nicht zu viel Sorgen.
>> Aber das ist im Grunde Ihre Crash-Kurs in Datenstrukturen.
Ich weiß, es ist eine Menge.
Gibt es etwas, dass wir möchte wieder von vorne gehen?
Alles, was wir durchhalten wollen?
Ja?
>> Gruppe: für dieses Beispiel so der neue Schwanz ist bei 0 über dem?
Sprecher 1: Ja.
PUBLIKUM: OK.
Also durchmachen, Sie möchten 1 plus 4 oder-- haben
>> Sprecher 1: Also Sie sagten, wenn wir gehen wollen wieder tun?
PUBLIKUM: Yeah.
Also, wenn Sie herauszufinden out-- wurden, wo sind Sie berechnen den Schwanz ab, dass?
>> Sprecher 1: Also der Schwanz war in-- Ich änderte dies.
So dass in diesem Beispiel hier war das Array wir an, OK suchen?
So haben wir die Dinge in 1, 2, 3 und 4.
So haben wir unseren Kopf ist gleich 1 bei dieser Punkt, und gleich 4 ist unsere Größe
an dieser Stelle, nicht wahr?
>> Sie alle einig, dass das der Fall ist?
Also wir machen den Kopf und die Größe, die gibt uns 5, und dann um 5 mod wir.
Wir erhalten 0, die uns sagt, dass 0 wo ist unser Schwanz, wo wir Platz haben.
>> PUBLIKUM: Was ist eine Kappe?
>> Sprecher 1: Die Kapazität.
Entschuldigung.
Das ist also die Größe Ihrer Array.
Ja?
>> PUBLIKUM: [unverständlich], bevor wir das Element zurückgeben?
>> Sprecher 1: So bewegen wir die Kopf oder zurück in dem Moment?
Wenn wir also ein bewegen, verringern die Größe?
Warten Sie mal.
Ich auf jeden Fall habe eine andere.
Keine Ursache.
Es gibt keine andere Formel.
Ja, würden Sie wollen, um zurückzukehren der Kopf und bewegen Sie ihn dann zurück.
>> PUBLIKUM: OK, da zu diesem Punkt war der Kopf bei 0,
und dann müssen Sie zurückgeben möchten Index 0 und dann den Kopf ein?
>> Sprecher 1: Richtig.
Ich denke, es ist eine andere Formel eine Art, wie diese.
Ich habe es nicht auf der Spitze meinen Kopf als Ich will dich nicht das falsche zu geben.
Aber ich denke, es ist absolut in Ordnung, sagen, OK, speichern diese element-- unabhängig
Kopf Element ist-- verringern Ihren Größe, bewegen Sie den Kopf über und Rückkehr
was auch immer das Element ist.
Das ist völlig in Ordnung.
Ok.
Ich fühle mich wie das ist nicht wie die most-- Sie nicht
werde von hier zu Fuß wie, ja, ich weiß versucht.
Ich habe sie alle.
Das ist ok.
Ich verspreche.
Aber Datenstrukturen sind etwas, es nimmt viel Zeit sich daran zu gewöhnen.
Wahrscheinlich einer der härtesten Dinge, glaube ich, in den Kurs.
>> So dauert es auf jeden Fall Wiederholung und suchen at-- I
wusste nicht wirklich, verkettete Listen bis ich weit mit ihnen zu viel,
in der gleichen Weise, dass ich nicht Zeiger wirklich verstehen
bis ich musste es für zwei lehren Jahre und meine eigenen psets mit ihm.
Es braucht viel Wiederholung und Zeit.
Und schließlich wird es eine Art klicken.
>> Aber in der Zwischenzeit, wenn Sie Art von einem hohen Pegel zu verstehen, was
diese tun, ihre Vor- und cons-- was was ist
wir wirklich dazu neigen, zu unterstreichen, besonders im Intro natürlich.
Wie, warum sollten wir nutzen einen Versuch über ein Array?
Wie, was sind die positiven und Negative jedes von denen?
>> Und das Verständnis der Kompromisse zwischen jeder dieser Strukturen
ist, was viel wichtiger Augenblick.
Es kann einen verrückt sein Frage oder zwei, die ist
gehen Sie bitten, Push implementieren oder implementieren Pop oder Enqueue und dequeue.
Aber in den meisten Fällen, dass mit höhere Ebene Verständnis und mehr
der ein intuitives Verständnis ist wichtiger als tatsächlich
in der Lage, sie umzusetzen.
>> Es wäre wirklich genial sein, wenn alle von Ihnen konnte gehen und umzusetzen versuchen,
aber wir verstehen, es ist nicht unbedingt die vernünftigste Sache jetzt.
Aber Sie können in Ihrem pset, wenn Sie wollen zu, und dann wirst du die Praxis zu bekommen,
und dann vielleicht wirst du wirklich zu verstehen.
Ja?
>> PUBLIKUM: OK, also welche sind wir sollen in der pset benutzen?
Muss ich einer von ihnen benutzen?
Sprecher 1: Ja.
So haben Sie Ihre Wahl.
Ich denke, in diesem Fall können wir sprechen über die pset ein wenig
weil ich lief durch diesen.
Also in Ihrem pset, haben Sie Ihre Wahl von Versuchen oder Hash-Tabellen.
Einige Leute werden versuchen und benutzen Blüte Filter,
aber diejenigen, technisch nicht korrekt sind.
Wegen ihrer probabilistischen Natur sie geben falsche Positive manchmal.
Sie sind cool Blick in, wenn.
Sehr zu empfehlen suchen auf sie zumindest.
Aber Sie haben Ihre Wahl zwischen einer Hash-Tabelle und ein Versuch.
Und das wird sein, wo Sie laden in Ihrem Wörterbuch.
>> Und Sie müssen wählen Sie Ihre Hash-Funktion,
Sie müssen entscheiden, wie viele werden Schaufeln Sie haben, und es wird variieren.
Wie, wenn Sie mehr Schaufeln haben, vielleicht wird es schneller laufen.
Aber vielleicht Sie verschwenden eine viel Platz, dass Art und Weise, wenn.
Sie haben, um es herauszufinden.
Mmhmm?
>> PUBLIKUM: Sie sagten vorhin, dass können wir andere Hash-Funktionen zu verwenden,
dass wir nicht haben, Erstellen einer Hash-Funktion?
>> Sprecher 1: Ja, richtig.
So wörtlich für Ihre Hash-Funktion, wie google "Hash-Funktion"
und suchen Sie nach einigen Coolen.
Sie sind nicht zu erwarten, zu bauen Ihre eigene Hash-Funktionen.
Die Menschen verbringen ihre Thesen über diese Dinge.
>> Also nicht über den Aufbau Ihrer eigenen Sorgen.
Finden Sie ein Online mit zu beginnen.
Einige von ihnen müssen Sie ein wenig zu manipulieren
um sicherzustellen, dass Rückgabetypen zusammenpassen und so weiter, so dass am Anfang,
Ich würde empfehlen, mit etwas einfach, dass vielleicht gerade
Hashes auf den ersten Buchstaben.
Und dann, wenn Sie diese nun eingerichtet haben, mit eingebautem Kühler Hashfunktion.
Mmhmm?
>> PUBLIKUM: Oder wäre einen Versuch effizient, aber nur schwerer, like--
>> Sprecher 1: So einen Versuch, denke ich, ist intuitiv schwer zu implementieren
jedoch ist sehr schnell.
Jedoch mehr Raum einnimmt.
Auch hier können Sie sowohl von denen, in optimieren verschiedene Arten und es gibt Möglichkeiten zu--
PUBLIKUM: Wie sind wir auf diese benotet?
Hat es matter--
>> Sprecher 1: Sie sind also ganz normal benotet.
Du wirst auf das Design bewertet.
Unabhängig davon, welche Art und Weise Sie tun, Sie wollen stellen Sie sicher, es ist so elegant wie es sein kann
und effizient wie es sein kann.
Aber wenn man einen Versuch oder Hash wählen Tisch, solange er funktioniert,
wir sind damit zufrieden.
Und wenn Sie etwas verwenden, die Hashes auf den ersten Buchstaben, das ist in Ordnung,
wie vielleicht wie in puncto Design.
Wir sind auch das Erreichen der Punkt in diesem semester--
Ich weiß nicht, ob Sie Jungs noticed-- wenn Sie
pset Noten sinken ein wenig wegen der Gestaltung und was nicht alles,
das ist völlig in Ordnung.
Es wird bis zu einem Punkt, wo Ihre Programme werden immer komplizierter.
Es gibt mehr Plätze Sie verbessern können.
>> Es ist also völlig normal.
Es ist nicht, dass Sie tut schlimmer auf Ihrem pset.
Es ist einfach nur wir härter auf dich.
Also jeder hat das Gefühl es.
Ich habe gerade benotet alle Ihre psets.
Ich weiß, jeder fühlt es.
>> Also nicht besorgt darüber.
Und wenn Sie Fragen zu haben vor psets oder Möglichkeiten, die Sie verbessern können,
Ich versuche und kommentieren die spezifische Plätze, aber manchmal ist es zu spät
und ich müde.
Gibt es noch andere Dinge über Datenstrukturen?
Ich bin sicher, ihr Jungs nicht wirklich möchte über sie nicht mehr reden,
aber wenn es, ich bin glücklich, gehen über sie, sowie alles
vom Vortrag am vergangenen Woche oder letzte Woche.
>> Ich weiß, letzte Woche war alles schreiben, so können wir über etwas schreiben übersprungen haben
vom Vortrag.
Alle anderen Fragen, die ich beantworten kann?
OK, alles in Ordnung.
Naja, Sie Jungs da 15 Minuten zu früh.
>> Ich hoffe, das war halb hilfreich zumindest, und ich werde euch nächste Woche zu sehen
oder Donnerstag Bürozeiten.
Gibt es Anfragen für Snacks für die nächste Woche, es ist die Sache?
Weil ich vergessen candy heute.
Und ich Süßigkeiten letzten gebracht Woche, aber es war Columbus Day,
so gab es wie sechs Menschen, die hatte vier Tüten mit Süßigkeiten um sich.
Ich kann Starbursts bringen wieder, wenn Sie mögen.
Starbursts?
OK, klingt gut.
Hat einen großen Tag, Jungs.