[Powered by Google Translate] [Abschnitt 6: weniger komfortabel] [Nate Hardison] [Harvard University] [Dies ist CS50.] [CS50.TV] Gut. Willkommen in Abschnitt 6. Diese Woche werden wir über Datenstrukturen sprechen im Schnitt, vor allem, weil dieser Woche Problem auf spellr gesetzt hat eine ganze Reihe von unterschiedlichen Datenstruktur Exploration. Es gibt eine Reihe von verschiedenen Möglichkeiten, wie Sie mit dem Problem Satz gehen kann, und desto mehr Daten Strukturen, die Sie kennen, die mehr coole Dinge, die Sie tun können. 

Also lasst uns loslegen. Zunächst werden wir zu Stapeln zu sprechen, Der Stack und Queue-Datenstrukturen, dass wir gehen, um darüber zu sprechen. Stacks und Warteschlangen sind sehr hilfreich, wenn wir reden über Graphen starten, was wir nicht so viel von jetzt tun. Aber sie sind wirklich gut zu einem der großen grundlegenden Datenstrukturen der CS verstehen. Die Beschreibung in der gestellten Aufgabe Spezifikation wenn Sie es nach oben ziehen, spricht über Stacks als ähnlich der Stapel Speisesaal Schalen, die Sie haben in der Cafeteria der Mensa wo, wenn der Speisesaal Personal kommt und setzt die Ess-Schalen aus, nachdem sie sie gereinigt haben, sie stapeln sie ein auf der anderen. Und dann, wenn Kinder kommen, um Nahrung zu bekommen, ziehen sie die Fächer aus, zuerst die obere, dann die darunter liegende, dann die darunter. Also, in der Tat ist das erste Fach, der Speisesaal Mitarbeiter eingeschläfert die letzte, die abgenommen wird. Das letzte, dass der Speisesaal Mitarbeiter anzuziehen ist die erste, die sich für das Abendessen wird übernommen. In der gestellten Aufgabe der spec, die Sie herunterladen können, wenn Sie nicht bereits haben, sprechen wir über Modellierung eines Stack-Daten stucture Verwendung dieser Art von Struktur. 

Also, was wir hier haben, ist dies ähnlich zu dem, was in der Vorlesung vorgestellt, außer im Vortrag präsentierten wir dies mit ints zu char * s entgegen. Das wird ein Stapel, dass speichert, was sein? Daniel? Was sollen wir speichern in diesem Stapel? [Daniel] Strings? >> Wir sind die Speicherung von Zeichenketten in diesem Stapel, genau. Alles was Sie brauchen zu müssen, um einen Stapel zu erstellen ist ein Array einer bestimmten Kapazität, die in diesem Fall, Kapazität wird in Großbuchstaben sein, weil es eine Konstante ist. Und dann neben dem Feld, ist alles, was wir brauchen, um zu verfolgen die aktuelle Größe des Arrays. Eine Sache zu beachten, dass ist irgendwie cool ist, dass wir schaffen das gestapelte Datenstruktur auf einer anderen Datenstruktur, das Array. Es gibt verschiedene Wege, um Stapel zu implementieren. Wir werden es nicht ganz noch, aber hoffentlich nachdem ich die verkettete Liste Probleme, Sie werden sehen, wie Sie ganz einfach zu implementieren einen Stapel auf einer verketteten Liste als gut. Aber jetzt werden wir zu den Arrays zu halten. Also noch einmal, ist alles was wir brauchen ein Array, und wir müssen nur die Größe des Arrays zu verfolgen. [Sam] Sorry, warum ist es, dass Sie sagten der Stapel ist auf der Oberseite der Saiten? Für mich scheint es, wie die Saiten innerhalb des Stapels sind. [Hardison] Yeah. Wir schaffen, wir nehmen unser Angebot Datenstruktur - Das ist eine große Frage. Die Frage ist also, warum die Menschen, die gerade dieses online sind, Deshalb sagen wir, dass der Stapel auf der Saiten, denn hier sieht es aus wie die Saiten innerhalb des Stapels sind? Welche ist völlig der Fall. Was ich bezog, war, dass wir haben eine Reihe Datenstruktur. Wir haben eine Reihe von char * s, dieses Array von Strings, und werden wir an, dass zuzusetzen, um die gestapelte Datenstruktur zu erstellen. 

So ein Stapel ist etwas komplexer als ein Array. Wir können eine Reihe, um einen Stapel zu bauen. Also das ist, wo wir sagen, dass der Stapel auf einer Matrix aufgebaut ist. Ebenso, wie ich bereits sagte, können wir einen Stapel auf einer verketteten Liste zu bauen. Anstelle der Verwendung eines Arrays zu unserer Elemente halten, wir könnten eine verlinkte Liste unserer Elemente enthalten und bauen Sie den Stapel um, dass. Lassen Sie uns durch ein paar Beispiele gehen, Blick auf einige Code, zu sehen, was tatsächlich passiert hier. Auf der linken Seite habe ich mich, was das Stapel struct würde wie im Speicher aussehen geworfen wenn die Kapazität wurden # definiert vier sein. Wir haben unsere vier Elementen char * array. Wir haben strings [0], strings [1], strings [2], strings [3] und dann das letzte Platz für unsere Größe integer. Ist das sinnvoll? Okay. Dies ist, was passiert, wenn das, was ich auf dem richtigen zu tun, was wird mein Code zu sein, ist nur zu erklären, eine Struktur, eine gestapelte Struktur namens s. Dies ist, was wir bekommen. Er legt diese Präsenz in Erinnerung. Die erste Frage ist hier, was sind die Inhalte dieser Stapel struct? Gerade jetzt sind sie nichts, aber sie sind nicht völlig nichts. Sie sind diese Art von Müll. Wir haben keine Ahnung, was in ihnen. Wenn wir Stapel s zu erklären, wir sind nur zu werfen, dass sich auf der Oberseite des Speichers. Es ist wie eine Art erklärt int i und nicht initialisieren. Sie wissen nicht, was da drin ist. Sie können lesen, was da drin ist, aber es kann nicht sein, super hilfsbereit. Eine Sache, die Sie immer daran denken, zu tun ist, zu initialisieren, was initialisiert werden muss. In diesem Fall werden wir die Größe zu initialisieren Null sein, weil das wird sich erweisen sich als sehr wichtig für uns. Wir könnten weitermachen und initialisiert alle Zeiger, die ganze char * s, einige verständlichen Wert, wahrscheinlich null sein. Aber es ist nicht absolut notwendig, dass wir das tun. 

Nun sind die beiden wichtigsten Operationen auf Stacks? Wer aus der Vorlesung erinnern, was Sie mit Stapeln tun? Ja? [Stella] Schieben und knallen? >> Genau. Schieben und knallen sind die beiden wichtigsten Operationen auf Stacks. Und was bedeutet Push zu tun? >> Es legt etwas auf die Spitze des Stapels und dann Knallgeräusch nimmt sie ab. [Hardison] Genau. So drückt drückt etwas auf oben auf dem Stapel. Es ist wie der Speisesaal Mitarbeiter setzen einen Speisesaal Tablett auf die Theke. Und knallen nimmt eine Esstablett vom Stapel. Lassen Sie uns durch ein paar Beispiele dafür, was passiert, gehen wenn wir die Dinge schieben und in den Stapel. Wenn wir den String 'Hallo' auf unserem Stapel schieben waren, das ist, was in unserem Diagramm würde jetzt aussehen. Sehen, was passiert? Wir schoben in das erste Element der Array-Strings und wir steigerte unserer Größe Anzahl 1 sein. Also, wenn wir den Unterschied zwischen den beiden Folien zu sehen, hier war 0, hier vor dem Stoß. Hier ist nach dem Stoß. Vor dem Druck, nach dem Stoß. Und jetzt haben wir ein Element in unserem Stapel. Es ist die Zeichenfolge "Hallo", und das ist es. Alles andere in der Anordnung, in unserem Saiten-Array, ist noch Müll. Wir haben es nicht initialisiert. Sagen wir, wir schieben eine andere Zeichenfolge auf unserem Stapel. Wir gehen "Welt" auf diese Zeit zu schieben. So können Sie sehen, "Welt" hier geht oben auf "Hallo", und die Größe Zählung geht bis zu 2. Jetzt können wir schieben "CS50", und das wird wieder an der Spitze zu gehen. Wenn wir gehen, können Sie sehen, wie wir schieben die Dinge auf der Oberseite des Stapels. Und nun kommen wir zu knallen. Wenn wir etwas aus der Stapel geholt, passiert was? Wer den Unterschied? Es ist ziemlich subtil. [Student] Die Größe. >> Ja, verändert die Größe. 

Was würden Sie erwarten zu ändern haben? [Student] Die Saiten auch. >> Richtig. Die Saiten zu. Es stellt sich heraus, dass, wenn du tust es auf diese Weise, weil wir nicht das Kopieren der Elemente in unserem Stapel, wir eigentlich nicht haben, etwas zu tun, können wir einfach die Größe den Überblick über die Anzahl der Dinge zu halten in unser Angebot so dass, wenn wir wieder auftauchen, wieder wir nur verringern unserer Größe bis zu 1. Es gibt keine Notwendigkeit, tatsächlich gehen und überschreiben nichts. Art von funky. Es stellt sich heraus, dass wir in der Regel nur verlassen Dinge allein, weil es weniger Arbeit ist für uns zu tun. Wenn wir nicht zurück zu gehen und zu überschreiben etwas, warum dann tun? Also, wenn wir zweimal von Pop des Stapels, ist alles, was tut verringern die Größe einer paar mal. Und wieder ist dies nur, weil wir nicht das Kopieren Dinge in unserem Stapel. Ja? Go ahead. [Student, unverständlich] >> Und was passiert dann, wenn Sie etwas erneut drücken? Wenn Sie etwas erneut drücken, wo kommt es hin? Wo geht es hin, Basil? >> In strings [1]? >> Richtig. Warum funktioniert es nicht in Strings [3] gehen? [Basil] Weil sie vergaß, daß es etwas in strings [1] und [2]? [Hardison] Genau. Unsere Stapel, im wesentlichen, "vergessen", dass es das Festhalten an nichts in strings [1] oder strings [2], so dass, wenn wir "woot" drücken, es einfach macht, die in das Element an Saiten [1]. Gibt es irgendwelche Fragen auf, wie dies funktioniert, auf einer grundlegenden Ebene? [Sam] Das ist also in keiner Weise dynamische, in der Höhe oder in Bezug auf die Größe des Stapels? [Hardison] Genau. Dies ist - der Punkt war, dass dies nicht ein dynamisch growning Stapel. Dies ist ein Stack, halten, mit höchstens vier char * s, höchstens vier Dinge. Wenn wir versuchen, und schieben ein Fünftel Sache waren, was denkst du sollte passieren? [Studenten, unverständlich] [Hardison] Genau. Es gibt eine Reihe von Dingen, geschehen könnte. Es könnte möglicherweise seg Fehler, je nachdem, was wir waren - wie genau wir die Umsetzung der Back-End. Es könnte zu überschreiben. Es könnte, dass Pufferüberlauf, dass wir darüber gesprochen, in der Klasse. Was wäre die naheliegendste Sache, die überschrieben werden könnte wenn wir versuchten, eine zusätzliche Sache auf unserem Stapel schieben? So, die Sie erwähnt einen Pufferüberlauf. Was könnte die Sache, über bekommen würde schriftlich oder auf stampfte sein wenn wir übergelaufen versehentlich, indem Sie versuchen, um eine zusätzliche Sache zu forcieren? [Daniel, unverständlich] >> Mögliche. Aber zunächst, was könnte passieren? Was ist, wenn wir eine vierte Sache schieben versucht? Es überschreiben könnte die Größe, zumindest mit dieser Erinnerung Diagramm, das wir haben. 

In das Problem set-Spezifikation ist die, was wir zu sein Umsetzung heute was wir wollen, ist nur false zurück. Unser Push-Verfahren wird ein boolean Wert zurück, und dass boolean Wert wird wahr, wenn die Push-Nachfolge und falsch, wenn wir nicht schieben nichts mehr, weil der Stapel voll ist. Lassen Sie uns durch eine wenig von dem Code jetzt gehen. Hier ist unsere Push-Funktion. Unser Push-Funktion für einen Stapel wird in der Zeichenfolge zu ergreifen, um auf den Stapel gelegt. Es wird true zurück, wenn die Zeichenfolge erfolgreich geschoben wurde auf den Stapel und andernfalls false. Irgendwelche Vorschläge, was könnte eine gute erste, was hier zu tun? [Sam] Wenn die Größe entspricht Kapazitäten dann wieder falsch? [Hardison] Bingo. Nice job. Wenn die Größe ist die Kapazität, werden wir false zurück. Wir können nicht etwas mehr in unserem Stapel. Ansonsten wollen wir etwas auf der Oberseite den Stapel gelegt. Was ist "die Spitze des Stapels," zunächst? [Daniel] Größe 0? >> Size 0. Was ist die Spitze des Stapels, nachdem es eine Sache im Stapel? Missy, weißt du das? [Missy] One. >> Die Größe ist ein, genau. Sie halten das Hinzufügen der Größe, und jedes Mal, wenn Sie in das neue Element an der Index-Größe im Array setzen sind. Wir können es mit dieser Art von one-liner tun, wenn das Sinn macht. Also haben wir unsere Saiten array bekommen habe, werden wir es auf die Größe Index zugreifen, und wir sind gerade dabei, unsere char * in dort zu speichern. Beachten Sie, wie es ist keine Zeichenfolge Kopieren los hier, keine dynamische Zuweisung von Speicher? Und dann Missy erzogen, was wir jetzt tun müssen, weil wir den String an der entsprechenden Stelle im Array gespeichert, und sie sagte, dass wir, um die Größe um eins erhöht, so dass wir bereit für den nächsten Tastendruck sind hatte. So können wir, dass mit s.size tun + +. An diesem Punkt haben wir in unser Angebot geschoben. Was ist das letzte, was wir zu tun haben? [Student] Gibt true. >> Gibt true. So ist es recht einfach, eine ziemlich einfache Code. Nicht zu viel. Sobald Sie Ihren Kopf herum, wie der Stack arbeitet gewickelt, das ist ziemlich einfach zu implementieren. 

Nun wird der nächste Teil dieses Aufspringen eine Zeichenfolge vom Stapel. Ich werde Ihnen Jungs etwas Zeit, um auf dieser ein wenig zu arbeiten. Es ist fast Wesentlichen das Gegenteil von dem, was wir hier im Push getan. Was ich getan habe ist eigentlich - oops. Ich habe bis ein Gerät hier, und das Gerät gestartet wird, Ich habe das Problem gesetzt 5-Spezifikation gezogen. Wenn wir vergrößern hier können wir sehen, ich bin am cdn.cs50.net/2012/fall/psets/pset5.pdf. Habt ihr heruntergeladen diesen Code, die hier gelegen, section6.zip? Gut. Wenn Sie noch nicht getan haben, tun, dass gerade jetzt, wirklich schnell. Ich werde es in meinem Terminal-Fenster tun. Ich eigentlich tat es hier oben. Yeah. Ja, Sam? >> Ich habe eine Frage, warum hast du gesagt s.string 's Klammern size = str? Was ist str? Ist das irgendwo vor definiert, oder - oh, in der char * str? [Hardison] Ja, genau. Das war das Argument. >> Oh, okay. Entschuldigung. [Hardison] Wir Angabe der Zeichenfolge zu schieben in. Die andere Frage, die kommen könnte, dass wir nicht wirklich hier sprechen war Wir hielten es für selbstverständlich, dass wir diese Variable namens s hatten das war in Umfang und uns zugänglich. Wir hielten es für selbstverständlich, dass s dieser Stapel struct war. So blickt bei dieser Push-Code, Sie können sehen, dass wir Dinge tun, mit dieser Zeichenfolge, die übergeben wurde aber dann plötzlich, wir Zugriff s.size, wie, woher s her? In dem Code, den wir gehen, um in der Rubrik Archiv suchen und dann die Sachen, die Sie in Ihr Problem tun setzt, wir haben unsere Stapel struct eine globale Variable so dass wir Zugang zu ihm in all unseren unterschiedlichen Funktionen haben ohne manuell Pass It Around und geben es durch Verweis alles tun, dass die Art von Zeug dazu. Wir stehen noch betrügen ein wenig, wenn man so will, die Dinge schöner machen. Und das ist etwas, was wir eigentlich hier sind, weil es zum Spaß, es ist einfacher. Oft werden Sie sehen, wie Menschen dies tun, wenn sie eine große Datenstruktur haben Das ist, an denen innerhalb ihres Programms betrieben. 

Gehen wir zurück auf das Gerät. Haben alle erfolgreich erhalten die section6.zip? Jeder entpacken Sie es mit unzip section6.zip? Wenn Sie in dem Abschnitt 6 Verzeichnis - aah, alle über dem Platz - und eine Liste, was ist hier, sehen Sie, dass Sie haben drei verschiedene. c Dateien. Du hast eine Warteschlange, sll, die einfach verknüpfte Liste ist, und einen Stapel. Wenn Sie eröffnen stack.c, Sie können sehen, dass wir haben dieses struct für uns definiert, die genaue Struktur, die wir gerade gesprochen in den Folien. Wir haben unsere globale Variable für den Stack bekam, wir haben unseren Push-Funktion, und dann haben wir unsere Pop-Funktion. Ich werde den Code für Back Push-up auf der Folie hier aber was ich möchte euch zu tun ist, um das Beste aus Ihrer Fähigkeit, gehen und Umsetzung der pop-Funktion. Sobald Sie es implementiert, können Sie dies mit Make-Stack zu kompilieren, und dann das resultierende Stack ausführbar, und das wird all diese Test-Code hier unten, das ist im Hauptlauf. Und Haupt kümmert sich eigentlich machen die Push-und Pop Anrufe und dafür zu sorgen, dass alles durch alles in Ordnung geht. Es initialisiert auch die Größe des Stacks hier so dass Sie sich keine Sorgen um die Initialisierung Sorgen. Man kann davon ausgehen, dass es gewesen ist richtig initialisiert von der Zeit, dass Sie es in der Pop-Funktion zugreifen. Macht das Sinn? So here we go. Es ist die Push-Code. Ich gebe euch 5 oder 10 Minuten. Und wenn Sie Fragen haben in der Zwischenzeit, während Sie mit der Codierung sind, bitten Sie sie laut. Also, wenn Sie zu einem Knackpunkt zu bekommen, fragen Sie einfach. Lassen Sie mich wissen, lassen Sie alle anderen wissen. Arbeiten Sie mit Ihrem Nachbarn auch. [Daniel] Wir stehen noch die Umsetzung pop gerade jetzt? >> Just Pop. Zwar können Sie kopieren die Umsetzung von Push, wenn Sie möchten so dass die Tests funktionieren wird. Denn es ist schwer, die Dinge immer in zu testen - oder ist es schwer zu knallen Dinge zu testen aus einem Stapel, wenn es nichts gibt, in dem Stapel zu beginnen. 

Was ist Pop soll zurückkehren? Das Element von der Oberseite des Stapels. Es soll das Element Haltestelle der Spitze des Stapels und anschließend Dekrementieren der Größe des Stapels, und jetzt hast du das Element auf der Oberseite verloren. Und dann kehren Sie das Element auf der Oberseite. [Student, unverständlich] [Hardison] So was passiert, wenn Sie das tun? [Student, unverständlich] Was am Ende passiert ist, sind Sie wahrscheinlich Zugriff entweder Ein Element, das wurde noch nicht initialisiert, so dass Ihre Berechnung von denen der letzte Element ausgeschaltet ist. Also hier, wenn Sie bemerken, in push, wir Zugriff Saiten am s.size Element denn es ist ein neuer Index. Es ist die neue Spitze des Stapels. Während im Pop, ist s.size werde der nächste Raum, der Raum, der an der Spitze aller Elemente in Ihrem Stack ist. So das oberste Element ist nicht s.size, sondern es ist unter ihm. 

Die andere Sache zu tun, wenn Sie - in Pop, wird Sie zu tun haben, um die Größe zu verringern. Wenn Sie erinnere mich an unser kleines Diagramm rechts hier wirklich, das einzige, was wir sahen passiert, wenn wir gerufen pop war, dass diese Größe, fallengelassen ersten bis 2, dann auf 1. Dann, wenn wir ein neues Element aufgeschoben, würde es gehen, an der richtigen Stelle. [Basil] Wenn die s.size 2 ist, dann wäre es nicht zu Element 2 gehen, und dann würden Sie wollen, dass die Element-Pop off? Also, wenn wir gingen - >> Also lasst uns an dieser noch einmal an. Wenn das unsere Stapel an dieser Stelle und wir nennen Pop, bei dem Index ist das oberste Element? [Basil] Bei 2, aber es geht um 3 Pop. >> Richtig. Also das ist, wo unsere Größe ist 3, aber wir wollen das Element am Index 2 Pop. Es ist die typische Art von durch ein, dass Sie mit der Null-Indizierung von Arrays. So Sie wollen, um das dritte Element Pop, aber das dritte Element ist nicht an Index 3. Und der Grund, warum wir nicht haben, dass minus 1 tun, wenn wir Druck sind ist denn im Moment bemerken Sie, dass das oberste Element, wenn wir etwas anderes auf den Stapel an dieser Stelle schieben waren, wir wollen es an Index 3 schieben. Und es passiert einfach so, dass die Größe und die Indizes up-Linie, wenn Sie schieben sind. 

Wer eine Arbeitsgruppe Stack-Implementierung haben? Sie haben eine Arbeitsgruppe Stapel ein. Haben Sie pop funktioniert noch? [Daniel] Ja. Ich denke schon. >> Programm läuft und nicht seg Verwerfungen, es auszudrucken? Ist es auszudrucken "Erfolg", wenn Sie es? Yeah. Machen Sie stapeln, führen Sie es, wenn es ausdruckt "Erfolg" und geht nicht boom, dann ist alles gut. Gut. Lassen Sie uns über die Appliance wirklich schnell, und wir werden durch diese gehen. Wenn wir schauen, was ist denn hier los mit Pop, Daniel, was war das erste, was du getan hast? [Daniel] Wenn s.size größer als 0 ist. [Hardison] Okay. Und warum hast du das getan? [Daniel] Um sicher zu gehen, dass es etwas innerhalb des Stapels. [Hardison] Right. Sie wollen testen, um sicherzustellen, dass s.size größer als 0 ist; ansonsten, was Sie haben wollen, geschehen? [Daniel] Return null? >> Return null, genau. Wenn also s.size größer als 0. Und was sollen wir tun? Was sollen wir tun, wenn der Stapel nicht leer ist? [Stella] Sie verringern die Größe? >> Sie verringern die Größe, okay. Also, wie hast du das gemacht? >> S.size--. [Hardison] Great. Und dann, was hast du getan? [Stella] Und dann sagte ich Rückkehr s.string [s.size]. [Hardison] Great. Ansonsten null zurück. Ja, Sam? [Sam] Warum braucht es nicht zu sein s.size + 1? [Hardison] Plus 1? >> Ja. >> Got it. [Sam] Ich dachte, weil du unter 1 out sind, dann wirst du zurückkehren nicht die ein, dass sie gefragt. [Hardison] Und das war genau das, was wir reden mit diesem ganzen Thema 0 Indizes. Wenn wir also zurück zu vergrößern hier. Wenn wir diesen Kerl hier anschaut, kann man sehen, dass, wenn wir Pop, wir tauchen das Element am Index 2. 

So verringern wir unsere Größe, dann unsere Größe unserem Index übereinstimmt. Wenn wir nicht verringern Sie die Größe, dann haben wir die Größe -1 und dann Dekrement tun. Great. All good? Haben Sie Fragen dazu? Es gibt eine Reihe von verschiedenen Möglichkeiten, dies auch zu schreiben. In der Tat können wir sogar etwas tun - wir können einen Einzeiler zu tun. Wir können eine einzeilige Rückkehr. So können wir tatsächlich verringern, bevor wir zurück, indem das zu tun. So setzen die - vor dem s.size. Das macht die Linie wirklich dicht. Wo die Differenz zwischen der -. Seine Größe und s.size-- ist, dass diese postfix - sie nennen es postfix weil die - kommt nach dem s.size-- bedeutet, dass s.size zum Zwecke der Feststellung der Index ausgewertet wie es derzeit, wenn diese Zeile ausgeführt wird, und dann diese - passiert, nachdem die Linie ausgeführt. Nachdem das Element am Index s.size zugegriffen wird. Und das ist nicht das, was wir wollen, weil wir die Abnahme der ersten geschehen soll. Othewise, wir gehen werden Zugriff auf das Array, effektiv außerhalb der Grenzen. Wir gehen zu den Zugriff auf das Element über dem ein, dass wir tatsächlich zugreifen möchten. Ja, Sam? >> Ist es schneller oder mit weniger RAM in einer Linie oder nicht? [Hardison] Ehrlich gesagt, es hängt wirklich davon. [Sam, unverständlich] >> Ja, es hängt. Sie können Compiler Tricks um den Compiler zu bekommen das zu erkennen, in der Regel, denke ich. 

So haben wir ein wenig über diese Compiler-Optimierung Zeug genannten dass man bei der Zusammenstellung zu tun, und das ist die Art der Sache, dass ein Compiler in der Lage sein, um herauszufinden, könnte, wie oh, hey, vielleicht kann ich das alles in einem Arbeitsgang zu tun, um das Laden der Größe variabel in vom RAM im Gegensatz Verringern sie und speichert sie wieder heraus, und dann laden Sie sie wieder den Rest dieser Operation zu verarbeiten. Aber in der Regel, nein, das ist nicht die Art von Dingen das wird sich Ihr Programm deutlich schneller zu machen. Haben Sie noch Fragen zu Stacks? 

So Schieben und knallen. Wenn euch ausprobieren wollen die Hacker Ausgabe, was wir in der Hacker-Ausgabe vorgenommen tatsächlich verschwunden und machte dieser Stapel dynamisch wachsen. Die Herausforderung besteht vor allem hier in der Push-Funktion, um herauszufinden, wie man das Array wachsen Sie pushen mehr und mehr Elemente auf dem Stapel. Es ist eigentlich nicht zu viel zusätzlichen Code. Nur ein Anruf - Sie haben sich daran zu erinnern, um die Anrufe auf malloc bekommen dort richtig, und dann herauszufinden, wenn Sie vorhaben, realloc nennen sind. Das ist eine lustige Herausforderung, wenn Sie interessiert sind. 

Aber für den Augenblick, lasst uns bewegen, und lassen Sie uns über Warteschlangen sprechen. Blättern Sie hier durch. Die Warteschlange ist eine enge Geschwister des Stapels. So in dem Stapel, waren Dinge, die in der letzten gelegt waren die ersten Dinge, die dann abgerufen werden. Wir haben diese last in, first out oder LIFO, Bestellung. Während in der Warteschlange, wie Sie es aus, wenn Sie in der Schlange zu erwarten, die erste Person in der Schlange zu bekommen, das erste, was in der Warteschlange zu bekommen, ist die erste Sache, die aus der Warteschlange abgerufen wird. Warteschlangen werden auch oft verwendet, wenn wir mit Graphen zu tun haben, wie wir sprachen über kurz mit Stacks, und Warteschlangen sind auch für eine Reihe anderer Dinge griffbereit. Eine Sache, die angezeigt wird oft versucht, zu halten, zum Beispiel, eine sortierte Liste von Elementen. Und Sie können dies mit einem Array zu tun. Sie pflegen eine sortierte Liste von Dingen, die in einem Array, aber wo das wird schwierig dann haben Sie immer zu finden der geeignete Ort, um die nächste Sache einzusetzen. Also, wenn Sie haben eine Reihe von Zahlen, 1 bis 10, und dann wollen Sie, dass für alle Zahlen von 1 zu erweitern durch 100, und Sie bekommen diese Zahlen in zufälliger Reihenfolge und zu versuchen, alles zu halten sortiert, wie Sie durch gehen, beenden Sie mit viel der Verlagerung zu tun. Bei bestimmten Arten von Warteschlangen und bestimmte Arten von zugrundeliegenden Datenstrukturen, Sie können tatsächlich halten es ziemlich einfach. Sie haben noch etwas hinzufügen und dann neu zu mischen dem Ganzen jeder Zeit. Auch müssen Sie nicht zu viel Verschiebung der internen Elemente um zu tun. Als wir an einer Warteschlange betrachten, sehen Sie, dass - auch in queue.c im Abschnitt Code - die struct, dass wir euch gegeben ist wirklich ähnlich dem struct, dass wir euch für einen Stapel. 

Es gibt eine Ausnahme, und dass eine Ausnahme ist, dass wir diese zusätzliche Zahl genannt Kopf haben, und der Kopf ist hier für die Verfolgung der Kopf der Schlange, oder das erste Element in der Warteschlange. Mit einem Stapel, konnten wir den Überblick über das Element halten, dass wir über abzurufen waren, oder die Oberseite des Stapels, mit nur die Größe, während mit einer Warteschlange, wir mit mit entgegengesetzten Enden umzugehen. Wir versuchen, tack Dinge am Ende, aber dann wieder alles von vorne. So effektiv, mit dem Kopf, haben wir den Index der Anfang der Warteschlange, und die Größe gibt uns den Index des am Ende der Warteschlange so dass wir die Dinge aus dem Kopf abrufen und fügen Sie die Dinge auf den Schwanz. Während bei dem Stapel, waren wir immer nur die sich mit der Oberseite des Stapels. Wir hatten nie die Unterseite des Stapels zugreifen. Wir haben nur aufgenommen, was nach oben und nahm die Dinge von der Spitze so dass wir nicht brauchen, dass zusätzliches Feld innerhalb unserer Struktur. Heißt das in der Regel sinnvoll? Gut. Ja, Charlotte? [Charlotte, unverständlich] [Hardison] Das ist eine gute Frage, und das war eine, die sich in der Vorlesung kam. Vielleicht zu Fuß durch ein paar Beispiele verdeutlichen, warum wir wollen nicht zu verwenden strings [0] als den Kopf der Warteschlange. 

So vorstellen, dass wir unsere Warteschlange haben, werden wir es nennen Warteschlange. Am Anfang, als wir gerade diese instanziiert wenn wir es gerade erklärt, wir haben nichts initialisiert. Es ist alles Müll. So natürlich wollen wir sicherstellen, dass wir zu initialisieren sowohl die Größe und die Kopf-Felder auf 0, etwas Vernünftiges sein. Wir könnten auch voran gehen und null die Elemente in unserer Warteschlange. Und für dieses Diagramm fit zu machen, feststellen, dass jetzt unsere Warteschlange kann nur halten drei Elemente; während unsere Stapel vier halten konnte, können unsere Warteschlange nur halten drei. Und das ist nur das Diagramm fit zu machen. Das erste, was hier passiert, ist, dass wir Enqueue den String "hallo". Und genauso wie wir es mit dem Stack, das nichts anders hier, werfen wir den String an strings [0] und erhöhen unsere Größe um 1 erhöht. Wir einreihen "bye", wird es angelegt. So sieht es wie ein Stapel zum größten Teil. Wir starteten hier neues Element, neues Element, hält Größe steigt. Was passiert an dieser Stelle, wenn wir etwas dequeue wollen? Wenn wir dequeue wollen, ist, die das Element, dass wir dequeue wollen? [Basil] Strings [0]. >> Zero. Genau richtig, Basil. Wir wollen, um loszuwerden, der ersten Zeichenfolge, dieser, "hallo". Also, was war die andere Sache, die sich geändert? Beachten Sie, wenn wir etwas aus der Stapel geholt, wir haben nur verändert die Größe, aber hier haben wir noch ein paar Dinge, die Veränderung. Nicht nur die Größe ändern, aber der Kopf Veränderungen. Dies geht zurück nach Charlotte Standpunkt früher: warum haben wir diesen Kopf, wie gut? Macht es Sinn, jetzt, Charlotte? >> Art. [Hardison] Art? Also, was passiert, wenn wir aus der Warteschlange entfernt? Was hat der Kopf zu tun, dass jetzt interessant ist? [Charlotte] Oh, da es verändert - okay. Ich verstehe. Da der Kopf - wo der Kopf in Bezug auf Veränderungen des Orts zeigt. Es ist nicht mehr immer die Null-Index ein. >> Ja, genau. Was geschah, war, wenn dequeueing die hohe Element getan wurde und wir nicht dieses Kopffeld weil wir immer fordern diese Zeichenfolge bei 0 Index der Leiter unserer Warteschlange dann müssten wir den Rest der Warteschlange Runterschalten. Wir hätten zu verschieben "bye" von von strings [1], um die Saiten [0]. Und strings [2] auf strings [1]. Und wir müssten dies für die gesamte Liste von Elementen zu tun, das gesamte Array von Elementen. Und wenn wir dies mit einem Array, bekommt das wirklich teuer. Also hier ist es keine große Sache. Wir müssen nur drei Elemente in unser Angebot. Aber wenn wir eine Schlange von tausend Elemente oder eine Million Elemente, und dann ganz plötzlich, starten wir einen Haufen dequeue ruft alle in einer Schleife, Dinge wirklich zu verlangsamen, da sie alles verschiebt sich ständig. Sie wissen, um 1 verschieben, Verschiebung um 1, Verschiebung um 1, Verschiebung um 1 erhöht. Stattdessen verwenden wir diese Kopf, wir nennen es ein "Zeiger", obwohl es nicht wirklich ein Zeiger im engeren Sinne, es ist nicht ein Zeiger-Typ. Es ist nicht ein int * oder char * oder so etwas. Aber es zeigt, oder angibt, an den Leiter unserer Warteschlange. Yeah? 

[Student] Wie funktioniert dequeue weiß nur Pop ausgeschaltet, was steht an der Spitze? [Hardison] Wie funktioniert dequeue wissen, wie Pop-off, was ist an der Spitze? >> Richtig, ja. >> Was es bei uns nur, was der Kopf Feld auf. So in diesem ersten Fall, wenn wir uns hier, unserem Kopf ist 0, Index 0. >> Richtig. [Hardison] So ist es nur sagt okay, gut, das Element mit dem Index 0, die Zeichenfolge "Hallo", das Element an der Spitze der Warteschlange. So werden wir den Kerl aus der Warteschlange entfernt. Und das wird das Element, das an den Aufrufer zurückgegeben wird sein. Ja, Saad? >> Also der Kopf Grunde setzt die - wohin du gehst zu indizieren sind? Das ist der Anfang von ihm? >> Ja. >> Okay. [Hardison] Das ist zum neuen Start für unser Angebot. Also, wenn Sie etwas aus der Warteschlange entfernt, ist alles was Sie zu tun haben, auf das Element am Index q.head, und das wird das Element, das Sie dequeue wollen. Sie haben auch die Größe zu verringern. Wir werden in ein bisschen zu sehen, wo die Dinge ein wenig tricky mit diesem zu bekommen. Wir dequeue, und jetzt, wenn wir wieder einreihen, Wo stehen wir einreihen? Woher kommt das nächste Element in unserer Warteschlange gehen? Sagen wir, wir wollen die Zeichenfolge "CS" einreihen. In welchem ​​Index wird es gehen? [Studenten] Strings [2]. >> Zwei. Warum 2 und nicht 0? [Basil] Denn jetzt ist der Kopf ein, so dass es wie der Beginn der Liste? [Hardison] Right. Und was bedeutet das Ende der Liste? Was haben wir mit, um das Ende unserer Warteschlange bezeichnen? Der Kopf ist der Kopf unserer Warteschlange, der Anfang unserer Warteschlange. Was ist das Ende unserer Warteschlange? [Studenten] Größe. >> Größe, genau. Also unsere neue Elemente gehen bei Größe, und die Elemente, die wir ausziehen kommen Sie an den Kopf. Wenn wir das nächste Element einreihen, wir setzen es in bei Größe. [Student] Bevor Sie setzen, dass in though, Größe 1 war, nicht wahr? [Hardison] Right. So nicht ganz auf Größe. Größe +, nicht ein, sondern + Kopf. Weil wir verschoben alles durch den Kopf Betrag. Also hier, jetzt haben wir eine Warteschlange der Größe 1, die bei Index 1 beginnt. Der Schwanz ist Index 2. Ja? 

[Student] Was passiert, wenn Sie dequeue strings [0], und die Saiten "Slots im Speicher nur geleert, im Grunde gehen, oder einfach nur vergessen? [Hardison] Yeah. In diesem Sinne, wir sind nur zu vergessen. Wenn wir Speichern von Kopien von ihnen - viele Datenstrukturen oft speichern ihre eigenen Kopien der Elemente so dass die Person die Verwaltung der Datenstruktur nicht Sorgen zu machen darüber, wo all die Zeiger gehen. Die Datenstruktur hält an alles, hält an allen Kopien um sicherzustellen, dass alles richtig anhält. Allerdings ist in diesem Fall diese Datenstrukturen nur der Einfachheit halber werden keine Kopien von etwas, dass wir in ihnen lagern. [Student] So ist dies eine kontinuierliche Reihe von -? >> Ja. Wenn wir wieder an, was die Definition war dieser Struktur aussehen, ist es. Es ist nur ein Standard-Array wie Sie gesehen haben, ein Array von char * s. Heißt das -? >> Ja, ich war nur fragen, Wenn Sie schließlich über genügend Arbeitsspeicher ausgeführt, zu einem gewissen Grad, wenn Sie alle diese leeren Stellen im Array? [Hardison] Ja, das ist ein guter Punkt. 

Wenn wir schauen, was passiert jetzt an diesem Punkt, Wir haben unsere Warteschlange gefüllt, es sieht aus wie. Aber wir haben nicht wirklich unsere Warteschlange gefüllt denn wir haben eine Warteschlange, Größe 2, aber es beginnt bei Index 1, weil das ist, wo unser Zeiger ist. Wie Sie sagten, dass das Element bei strings [0], bei Index 0, ist nicht wirklich da. Es ist nicht in unserer Warteschlange mehr. Wir haben einfach nicht die Mühe zu gehen und zu überschreiben, wenn wir es aus der Warteschlange entfernt. Also auch wenn es, wie wir aus der Erinnerung habe laufen sieht, haben wir wirklich nicht. Das Spot ist für uns nutzen zu können. Das richtige Verhalten, wenn wir versuchen, erste dequeue etwas wie "Auf Wiedersehen", das wäre knallen bye ausgeschaltet. Jetzt ist unsere Warteschlange beginnt bei Index 2 und der Größe 1. Und nun, wenn wir versuchen, Enqueue wieder etwas, sagen wir 50, 50 sollte an dieser Stelle bei Index 0 gehen weil es immer noch für uns. Ja, Saad? [Saad] Heißt das automatisch geschehen? [Hardison] Es ist nicht ganz automatisch. Sie haben die Mathematik zu tun , damit es funktioniert, aber im Wesentlichen, was wir getan haben, ist, dass wir gerade gewickelt. [Saad] Und ist es in Ordnung, wenn diese ein Loch in der Mitte davon? [Hardison] Es ist, wenn wir sicherstellen können, die Mathematik zu arbeiten ordnungsgemäß. 

Und es stellt sich heraus, dass dies eigentlich nicht so schwer, mit dem Mod-Operator zu tun. So wie wir es mit Caesar und dem Krypto-Zeug, mit mod, können wir Dinge zu umschlingen und fahren um und um und um mit unseren Warteschlange halten, dass Kopfzeiger bewegen. Beachten Sie, dass Größe ist immer mit Rücksicht auf die Anzahl der Elemente tatsächlich innerhalb der Warteschlange. Und es ist nur der Kopf Zeiger, Radfahren durch hält. Wenn wir schauen, was hier passiert, wenn wir wieder an den Anfang zu gehen, und Sie müssen nur sehen, was passiert in den Kopf wenn wir etwas einreihen, passiert nichts auf den Kopf. Wenn wir etwas anderes eingereiht, passiert nichts auf den Kopf. Sobald wir etwas aus der Warteschlange entfernt, geht der Kopf nach dem anderen. Wir Warteschlange etwas passiert nichts auf den Kopf. Wenn wir etwas aus der Warteschlange entfernt, ganz plötzlich der Kopf wird erhöht. Wenn wir etwas einreihen, geschieht nichts auf den Kopf. 

Was wäre an dieser Stelle geschehen, wenn wir wieder etwas aus der Warteschlange entfernt waren? Irgendwelche Gedanken? Was würde mit dem Kopf passiert? Was soll mit dem Kopf passiert wenn wir etwas anderes dequeue waren? Der Kopf ist im Moment bei Index 2, was bedeutet, dass der Kopf der Warteschlange strings [2]. [Student] Welche 0 zurückgibt? >> Es sollte auf 0 zurück. Es sollte wickeln wieder um, genau. So weit, jedes Mal, wenn wir aufgerufen dequeue, haben wir schon länger ein auf den Kopf, fügen Sie ein auf den Kopf, fügen Sie ein auf den Kopf, fügen Sie ein auf den Kopf. Sobald diese Kopfzeiger bringt es auf den letzten Index in unser Angebot, dann haben wir es wickeln zurück an den Anfang haben, gehen Sie zurück auf 0 gesetzt. [Charlotte] Was bestimmt die Kapazität der Warteschlange in einem Stapel? [Hardison] In diesem Fall haben wir gerade mit einem # definierte Konstante. >> Okay. [Hardison] In der aktuellen. C-Datei können Sie in und Dreck gehen mit ihm ein bisschen und machen es so groß oder so wenig, wie Sie möchten. [Charlotte] Also, wenn du machst es eine Warteschlange, wie machen Sie den Computer wissen wie groß der Stapel sein wollen? [Hardison] Das ist eine große Frage. Es gibt ein paar Möglichkeiten. Man ist nur definieren vorn und sagen, das wird eine Warteschlange, die 4 Elemente oder 50 Elementen oder 10.000 verfügt. Der andere Weg ist zu tun, was die Hacker edition Leute tun und Funktionen erstellen, um Ihre Schlange wächst dynamisch weitere Dinge hinzukommen in. 

[Charlotte] So mit der ersten Option zu gehen, was Syntax verwenden um das Programm zu sagen, was ist die Größe der Warteschlange? [Hardison] Ah. Also lasst uns hier raus. Ich bin immer noch in stack.c hier, also bin ich gerade dabei, nach oben an die Spitze hier. Können Sie diese hier richtig? Dies ist der # define-Kapazität 10. Und das ist fast genau die gleiche Syntax, die wir für Warteschlange. Außer in der Warteschlange haben wir, dass zusätzliche struct Feld hier haben. [Charlotte] Oh, ich dachte, die Kapazität soll die Kapazität für den String. [Hardison] Ah. >> Dass es die maximale Länge des Wortes ist. >> Got it. Yeah. Die Kapazität hier - das ist ein großer Punkt. Und das ist etwas, was schwierig ist weil das, was wir hier erklärt ist ein Array von char * s. Ein Feld von Zeigern. Dies ist ein Array von Zeichen. Dies ist wahrscheinlich das, was Sie gesehen haben, wenn Sie bereits erklärt habe Ihre Puffer für Datei-I / O, wenn Sie habe seit Saiten manuell auf den Stapel. Aber was wir hier haben ist ein Array von char * s. Es ist also ein Array von Zeigern. Eigentlich, wenn wir wieder zu verkleinern, und wir schauen, was hier vor sich geht in der Präsentation sehen Sie, dass die tatsächlichen Elemente, die Zeichendaten nicht innerhalb des Arrays selbst gespeichert. Was ist in unser Angebot hier gespeichert sind Zeiger auf die Zeichendaten. Okay. So haben wir gesehen, wie die Größe der Warteschlange ist nur mit dem Stapel möchten, die Größe immer respektiert die Anzahl der Elemente derzeit in der Warteschlange. Nachdem 2 reiht, ist die Größe 2. Nachdem Sie eine dequeue die Größe ist nun 1. Nach einen weiteren Enqueue die Größe ist wieder bis zu 2. So dass die Größe definitiv respektiert die Anzahl der Elemente in der Warteschlange, und dann der Kopf hält gerade Radfahren. Es geht von 0-1-2, 0-1-2, 0-1-2. Und jedes Mal, nennen wir dequeue, wird der Head-Zeiger zum nächsten Index erhöht. Und wenn der Kopf über zu gehen vorbei, Schleifen es wieder rund auf 0 gesetzt. Also mit diesem können wir schreiben das dequeue Funktion. Und wir werden den Enqueue-Funktion zu verlassen für euch statt zu implementieren. 

Wenn wir ein Element aus der Warteschlange entfernt aus unserer Warteschlange was war das erste, was Daniel tat, wenn wir schreiben das Popup-Funktion für Stapel begonnen? Lassen Sie mich von jemandem, der nicht geredet hat noch hören. Mal sehen, Saad, erinnerst du dich, was Daniel als erstes, wenn er pop schrieb tat? [Saad] Es wurde, war es - >> Er testete für etwas. [Saad] Wenn größer als 0 ist. >> Genau. Und was war das Tests für? [Saad] Das war testen, ob es etwas gibt, innerhalb des Arrays. [Hardison] Yeah. Genau. So können Sie nicht knallen nichts aus dem Stapel, wenn es leer ist. Ebenso können Sie nicht aus der Warteschlange entfernt etwas von einer Warteschlange, wenn es leer ist. Was ist das erste, was wir in unserem dequeue Funktion tun sollte hier, meinst du? [Saad] Wenn die Größe größer als 0 ist? >> Ja. In diesem Fall habe ich eigentlich nur getestet, um zu sehen, ob es 0 ist. Wenn es 0 ist, können wir null zurück. Aber genau die gleiche Logik. Und lassen Sie uns damit weitermachen. Wenn die Größe nicht 0 ist, wo ist das Element, das wir dequeue wollen? [Saad] An der Spitze? >> Genau. Wir können gerade herausziehen das erste Element in unserer Warteschlange durch Zugriff auf das Element am Kopf. Nichts verrückt. Danach, was sollen wir tun? Was muss passieren? Was war die andere Sache, über die wir sprachen dequeue? Zwei Dinge müssen geschehen, weil unsere Queue geändert hat. [Daniel] Reduzieren Sie die Größe. >> Wir haben die Größe zu reduzieren und erhöhen den Kopf? Genau. Um den Kopf zu erhöhen, können wir nicht einfach blind zu erhöhen den Kopf, erinnern. Wir können nicht einfach tun queue.head + +. Wir müssen auch diesen mod durch die Kapazität. Und warum tun wir durch die Kapazität Mod, Stella? [Stella] Weil es umschlingen hat. >> Genau. Wir mod durch die Kapazität, weil sie zu wickeln wieder um auf 0 hat. So, jetzt, an diesem Punkt können wir tun, was Daniel gesagt. Wir können verringern die Größe. Und dann können wir nur Rückkehr das Element, das am Anfang der Warteschlange war. Es sieht irgendwie aus knorrigen auf den ersten. Vielleicht haben Sie eine Frage. Sorry? 

[Sam] Warum ist an der Spitze der Warteschlange zuerst? Wo kommt das hin? [Hardison] Es kommt aus der vierten Zeile von unten. Nachdem wir testen, um sicherzustellen, dass unsere Warteschlange nicht leer ist, Wir ziehen char * first, ziehen wir das Element, das an der Spitze index sitzt, der unser Angebot, unsere Saiten Array >> und Anruf, dass zuerst? [Hardison] Und wir nennen es zuerst. Yeah. Gerade im Nachgang zu, dass, warum Sie denken, wir mussten das tun? [Sam] Jeder wird zunächst nur wieder q.strings [q.head]? >> Ja. >> Da wir tun diese Veränderung der q.head mit dem Mod-Funktion, und es gibt keine Möglichkeit, dass innerhalb Rückleitung auch tun. [Hardison] Genau. Du bist vor Ort auf. Sam ist völlig vor Ort auf. Der Grund mussten wir ziehen das erste Element in unserer Warteschlange und speichert sie in einer Variablen Denn diese Zeile, wo wir gerade waren q.head, gibt es die mod-Operator in gibt es nicht etwas, was wir tun können, und haben es wirksam auf den Kopf ohne - in einer Zeile. So haben wir eigentlich zu ziehen das erste Element, und stellen Sie dann den Kopf, Passen Sie die Größe, und dann wieder das Element, dass wir herausgezogen. Und das ist etwas, dass wir später mit Gekommen verkettete Listen, wie wir spielen, um mit ihnen. Oft, wenn Sie zu befreien oder die Veräußerung von verkettete Listen Sie brauchen, um das nächste Element, der nächste Zeiger einer verketteten Liste erinnern vor der Entsorgung des aktuellen. Weil man sonst wegwerfen die Informationen, was in der Liste links. Nun, wenn Sie Ihr Gerät, öffnen Sie queue.c--x raus. Also, wenn ich queue.c öffnen, lassen Sie mich zoom hier, Sie werden sehen, dass Sie eine ähnlich aussehende Datei haben. Ähnlich aussehende Datei, was wir hatten früher mit stack.c. Wir haben unsere Struktur für Queue so wie wir auf den Folien sahen definiert haben. 

Wir haben unsere Enqueue-Funktion, die für Sie zu tun ist. Und wir haben die dequeue Funktion. Die dequeue Funktion in der Datei wird nicht implementiert, aber ich werde es wieder aufgemacht auf der PowerPoint so dass Sie es in eingeben können, wenn Sie möchten. So für die nächsten 5 Minuten oder so, euch auf Enqueue arbeiten das ist fast genau das Gegenteil von dequeue. Sie müssen nicht den Kopf anpassen, wenn Sie Einreihen sind, aber was haben Sie einstellen? Größe. Also, wenn Sie Enqueue, der Kopf unberührte bleibt, wird die Größe geändert. Aber es dauert ein wenig - Sie müssen spielen, um mit diesem mod um herauszufinden, was genau index das neue Element am eingefügt werden soll. So gebe ich euch ein wenig, legte wieder dequeue auf der Folie, und als euch Fragen haben, rufen sie aus, so dass wir alle reden über sie als Gruppe. Auch mit der Größe, die Sie tun nicht - wenn man die Größe anzupassen, können Sie immer nur - Sie müssen die Größe immer mod? [Daniel] No >> Sie haben noch um die Größe mod, richtig. Da die Größe wird immer, wenn du bist - vorausgesetzt, Sie sind Geschäftsführer Dinge angemessen, die Größe immer zwischen 0 und 3 liegen. Wo haben Sie MOD, wenn Sie tun Enqueue sind? [Student] Nur für den Kopf. >> Nur für den Kopf, genau. Und warum hast du überhaupt Mod im Enqueue? Wann ist eine Situation, in der Sie mod hätten? [Student] Wenn Sie Sachen auf Bereiche haben, die in Räumen 1 und 2 mögen, und dann musste etwas bei 0 hinzuzufügen. [Hardison] Ja, genau. Also, wenn Sie Ihren Kopf Zeiger ist ganz am Ende, oder wenn Ihre Größe plus Kopf größer ist, oder besser gesagt, wird sich um die Warteschlange zu wickeln. 

So in dieser Situation, dass wir haben hier auf der Folie gerade jetzt, wenn ich will sofort etwas einreihen, wir wollen etwas mit dem Index 0 einreihen. Also, wenn Sie schauen, wo die 50 geht, und ich rufe Enqueue 50, geht es dort an der Unterseite. Es geht in Index 0. Es ersetzt das 'Hallo', die bereits aus der Warteschlange entfernt wurde. [Daniel] Weißt du nicht kümmern, dass in dequeue schon? Warum tut sie nichts mit dem Kopf in Enqueue? [Hardison] Oh, so dass Sie nicht ändern Sie den Kopf, sorry. Aber man muss die Mod-Operator verwenden, wenn Sie den Zugriff sind das Element, das Sie einreihen, wenn Sie Zugriff sind möchten das nächste Element in der Warteschlange. [Basil] Ich habe das nicht tun, und ich bekam "Erfolg" dort. [Daniel] Oh, ich verstehe, was du sagst. [Hardison] So didn't - du gerade getan hast am q.size? [Basil] Yeah. Ich habe gerade die Seiten gewechselt, ich habe nichts mit dem Kopf. [Hardison] Sie eigentlich nicht haben, um den Kopf setzen, etwas zu sein, aber wenn man Index in die Saiten Array Sie haben tatsächlich voran gehen und berechnen, wo das nächste Element ist, weil withe den Stapel, war das nächste Element in Ihrem Stapel immer am Index entsprechend der Größe. Wenn wir wieder in unserem Stapel Push-Funktion, konnten wir immer in unserem neuen Elements plunk rechts Indexgröße. Während bei der Warteschlange, können wir nicht tun, denn wenn wir in dieser Situation, wenn wir Warteschlange 50 neuen String würde gehen Sie nach rechts auf strings [1] die wir nicht tun wollen. Wir möchten, dass die neue Zeichenfolge mit dem Index 0 gehen. 

Hat jemand - ja? [Student] Ich habe eine Frage, aber es ist nicht wirklich zusammen. Was bedeutet es, wenn jemand ruft einfach etwas wie pred Zeiger? Was ist der Name eine Abkürzung für? Ich weiß, es ist nur ein Name. [Hardison] Pred Zeiger? Mal sehen. In welchem ​​Zusammenhang? [Student] Es war für den Einsatz. Ich kann Ihnen später fragen, ob Sie denn es ist nicht wirklich verwandt, aber ich - [Hardison] Von David Einsatz Code aus Vorlesung? Wir ziehen kann, dass und darüber reden. Wir werden über das nächste, sobald wir verkettete Listen zu sprechen. 

Also lasst uns wirklich schnell schauen, was die Enqueue-Funktion aussieht. Was war das erste, was die Menschen in Ihrem Enqueue Linie zu tun versucht? In dieser Warteschlange? Ähnlich wie ihr für Stapel schieben. Was haben Sie getan, Stella? [Stella, unverständlich] [Hardison] Genau. Wenn (q.size == CAPACITY) - Ich muss meine Zahnspange an der richtigen Stelle setzen - false zurück. Zoom in ein wenig. Okay. Nun, was ist das nächste, was wir zu tun hatten? Nur mit dem Stapel mögen, und eingesetzt an der richtigen Stelle. Und was war der richtige Ort, um das einfügen? Mit dem Stapel war es Indexgröße, damit es nicht ganz so. [Daniel] Ich habe q.head--oder - >> q.strings? >> Yeah. q.strings [q.head + q.size mod CAPACITY]? [Hardison] Wir wollen wahrscheinlich Klammern um diese gelegt so dass wir immer die entsprechende Vorrang und so, das ist cleart to everybody. Und gesetzt, dass gleich? >> Um str? >> Um str. Great. Und nun, was ist das letzte, was wir zu tun haben? So wie wir in den Stapel getan. >> Erhöhen Sie die Größe? >> Erhöhen Sie die Größe. Boom. Und dann, da der Startcode gerade standardmäßig false, Wir wollen dies an der wahren ändern, wenn alles glatt läuft durch und alles gut geht. Gut. Das ist eine Menge von Informationen für Abschnitt. Wir sind noch nicht ganz vorbei. Wir wollen sehr schnell reden einfach-verkettete Listen. Ich bringe diese bis so können wir wieder gehen, um es später. Aber gehen wir zurück zu unserer Präsentation nur für ein paar weitere Folien. So Enqueue TODO ist, jetzt haben wir es geschafft. 

Werfen wir nun einen Blick auf einfach verkettete Listen. Wir sprachen über diese ein wenig mehr in der Vorlesung. Wie viele von euch sahen die Demo, wo wir Menschen mussten unbeholfen aufeinander zeigen und Halten Zahlen? >> Ich war in diesem. >> Was denkt ihr? Hat das hoffentlich zu entmystifizieren diese ein wenig? Mit einer Liste, wie sich herausstellt, dass wir mit dieser Art umzugehen, dass wir gehen, um einen Knoten nennen. Während bei der Warteschlange und der Stapel hatten wir Strukturen, die wir Warteschlange in Stapel nennen würde, hatten wir diese neue Warteschlange im Stapel Typen, Hier eine Liste wirklich nur aus einer Reihe von Knoten. In der gleichen Weise, dass Strings nur ein paar Zeichen sind alle aufgereiht nebeneinander. Eine verkettete Liste ist nur ein Knoten und ein anderer Knoten und einem anderen Knoten und einem anderen Knoten. Und anstatt Zerschlagung alle Knoten zusammen und speichert sie zusammenhängend alles in Ordnung nebeneinander im Speicher, mit dieser nächste Zeiger ermöglicht es uns, die Knoten, wo zu speichern, nach dem Zufallsprinzip. Und dann Art von Draht sie alle zusammen, um von einem zum nächsten Punkt. 

Und was war der große Vorteil, dass diese über ein Array hatte? Über Speicherung alles zusammenhängend gerade stecken nebeneinander? Sie erinnern sich? Yeah? >> Dynamische Speicherreservierung? >> Dynamic Speicherzuweisung in welchem ​​Sinne? [Student] Indem Sie halten damit größer und Sie müssen nicht das gesamte Array zu verschieben? [Hardison] Genau. So mit einem Array, wenn Sie ein neues Element in der Mitte von setzen wollen, Sie haben alles zu verschieben, um Platz zu machen. Und wie wir sprachen über die der Warteschlange, das ist, warum wir diese Kopfzeiger halten, so dass wir nicht ständig verändernden Dinge. Denn das wird teuer, wenn du ein großes Array haben und Sie sind ständig dabei diese zufälligen Insertionen. Während bei einer Liste, ist alles was Sie zu tun haben, werfen Sie es auf einem neuen Knoten, stellen Sie die Zeiger, und du bist fertig. Was saugt über diese? Abgesehen von der Tatsache, dass es nicht so leicht mit als Array funktionieren? Yeah? [Daniel] Nun, ich denke, es ist viel schwieriger, ein bestimmtes Element in der verketteten Liste zugreifen? [Hardison] Sie können nicht nur auf ein beliebiges Element in der Mitte der verketteten Liste zu springen. Wie haben Sie es stattdessen tun? >> Sie müssen über die ganze Sache fort. [Hardison] Yeah. Sie müssen durch ein zu einer Zeit, eines zu einer Zeit, zu gehen. Es ist eine riesige - es ist ein Schmerz. Was ist die andere - es gibt eine andere Sturz dazu. [Basil] Sie können nicht vorwärts und rückwärts gehen? Sie haben in eine Richtung gehen? [Hardison] Yeah. So wie lösen wir, dass manchmal? [Basil] Doppelt verkettete Listen? >> Genau. Es gibt doppelt verkettete Listen. Es gibt auch - sorry? 

[Sam] Ist das das gleiche wie mit den pred, was - Ich erinnerte, ist nicht das, was die pred Sache ist geeignet? Ist das nicht zwischen doppelt und einfach? [Hardison] Lasst uns schauen, was genau er tat. So here we go. Hier ist die Liste Code. Hier haben wir predptr, hier. Ist das, was Sie reden? Das war also - er befreit eine Liste und er versucht, einen Zeiger zu speichern. Dies ist nicht die doppelt, einfach verkettete-Listen. Wir können dazu später mehr sprechen, da dies reden Befreiung der Liste und ich möchte einige andere Sachen zuerst angezeigt. aber es ist einfach - es ist die Erinnerung an die Wert ptr [Student] Oh, es ist vorhergehenden Zeiger? >> Ja. So dass wir dann erhöhen ptr selbst, bevor wir dann frei, was predptr ist. Denn wir können nicht frei ptr und rufen Sie dann ptr = ptr nächsten, nicht wahr? Das wäre schlecht. Also mal sehen, zurück zu diesem Kerl. 

Die andere schlechte Sache über Listen ist, dass während mit einem Array wir müssen alle Elemente selbst gestapelt nebeneinander, Hier haben wir auch diesen Zeiger eingeführt. So gibt es eine zusätzliche Stück Erinnerung, dass wir mit zu verwenden für jedes Element, dass wir in unserer Liste speichert. Wir bekommen Flexibilität, aber es kommt zu einem Preis. Es kommt mit dieser Zeit Kosten, und es kommt mit diesem Speicher Kosten zu. Zeit in dem Sinne, dass wir jetzt durch jedes Element im Array gehen die ein mit dem Index 10, oder jenes wäre Index 10 in einem Array haben zu finden. 

Nur ganz schnell, wenn wir Diagramm aus dieser Listen typischerweise wir halten an der Spitze der Liste oder dem ersten Zeiger der Liste und beachten Sie, dass dies eine echte Zeiger ist. Es ist nur 4 Byte. Es ist nicht eine tatsächliche Knoten selbst. Sie sehen also, dass es keinen int Wert darin, keine nächste Zeiger in sich hat. Es ist buchstäblich nur ein Zeiger. Es wird zu etwas, das eine tatsächliche Knoten struct zeigen. [Sam] Ein Zeiger namens Knoten? >> Das ist - nein. Dies ist ein Zeiger, um etwas vom Typ Knoten. Es ist ein Zeiger auf einen Knoten Struct. >> Oh, okay. Auf der Zeichnung links, Code rechts. Wir können es null, was ein guter Weg, um zu beginnen ist eingestellt. Wenn Sie Diagramm ist, können Sie entweder schreibe es als null oder Sie legen eine Linie durch das so. 

Eine der einfachsten Möglichkeiten, um mit Listen arbeiten, und wir bitten Sie sowohl voranstellen und anhängen, um die Unterschiede zwischen den beiden zu sehen, aber vorangestellt ist definitiv einfacher. Wenn Sie voranstellen, das ist, wo man - wenn man prepend (7), Sie gehen und erstellen Sie den Knoten struct und Sie zum ersten Mal auf ihn verweisen, denn jetzt, da wir vorangestellt ist, es wird am Anfang der Liste stehen. Wenn wir voranstellen (3), dass ein anderer Knoten erstellt, aber jetzt 3 kommt vor 7. Also werden wir im wesentlichen schieben Dinge auf unserer Liste. Jetzt können Sie sehen, dass prepend, manchmal Leute nennen es schieben, weil Sie schob ein neues Element auf Ihrer Liste. Es ist auch einfach, auf der Vorderseite einer Liste zu löschen. So können die Leute oft nennen das Pop. Und auf diese Weise können Sie emulieren einen Stapel mit einer verketteten Liste. Whoops. Sorry, jetzt sind wir in append bekommen. Also hier haben wir vorangestellt (7), jetzt haben wir voranstellen (3). Wenn wir vorangestellt etwas anderes auf dieser Liste, wenn wir vorangestellt (4), dann müssten wir 4 und dann 3 und dann 7. So könnten wir knallen und entfernen 4, remove 3, entfernen 7. Oft ist die intuitive Art und Weise, darüber nachzudenken ist mit append. Also habe ich aus, wie es wäre mit anhängen schau grafisch dargestellt. Hier angehängt (7) sieht nicht anders denn es gibt nur ein Element in der Liste. Und Anhängen (3) bringt es am Ende. Vielleicht können Sie jetzt sehen den Trick mit append ist, dass, da wir nur wissen, wo der Anfang der Liste ist, , um eine Liste haben Sie den ganzen Weg durch die Liste zu gehen anhängen bis zum Ende erhalten, stoppen, dann bauen Sie Ihre Knoten und plunk alles auf. Verdrahten all das Zeug. Also mit prepend, wie wir gerade riss durch das wirklich schnell, wenn Sie zu einer Liste voranstellen, ist es ziemlich einfach. 

Sie machen Ihren neuen Knoten beinhalten eine dynamische Speicherzuweisung. Also hier wir machen einen Knoten struct mit malloc. So malloc verwenden wir denn das werde beiseite Erinnerung für uns für eine spätere weil wir das nicht wollen - wir wollen diese Erinnerung für eine lange Zeit anhalten. Und wir bekommen einen Zeiger auf den Platz im Speicher, dass wir gerade zugeordnet. Wir verwenden Größe der Knoten, wissen wir nicht fassen die Felder. Wir wissen nicht manuell erzeugen die Anzahl von Bytes, Stattdessen verwenden wir sizeof so dass wir wissen, dass wir immer die entsprechende Anzahl von Bytes. Wir stellen sicher, um zu testen, dass unsere malloc Aufruf erfolgreich war. Dies ist etwas, was Sie wollen in der Regel tun. Auf modernen Maschinen, läuft der Speicher ist nicht etwas, das einfach es sei denn, du bist Zuteilung einer Tonne Material und machen eine riesige Liste, aber wenn Sie bauen Sachen für, sagen wir, wie ein iPhone oder ein Android-Gerät, Sie haben eine begrenzte Speicher-Ressourcen, vor allem, wenn Sie etwas intensiver sind. So ist es gut, in die Praxis zu bekommen. 

Beachten Sie, dass ich ein paar verschiedene Funktionen verwendet hier Sie haben gesehen, dass es neue Art von. So fprintf ist nur printf gerne außer dem ersten Argument ist der Strom, auf die Sie drucken möchten. In diesem Fall wollen wir die Standardfehler String ausdrucken die sich von der Norm outstream. Standardmäßig zeigt sich an der gleichen Stelle. Darüber hinaus druckt der Terminal, aber Sie können - Verwendung dieser Befehle, die Sie kennen gelernt, die Umleitung Techniken Sie erfuhr in Tommys Video für Problem Satz 4 können Sie leiten es zu verschiedenen Bereichen, dann verlassen, genau hier, verlässt das Programm. Es ist im Wesentlichen wie eine Rückkehr von der Hauptstraße, außer wir Ausfahrt weil hier Rückkehr wird nichts. Wir sind nicht in Haupt-, nicht so wieder nicht das Programm zu beenden, wie wir wollen. So nutzen wir die Exit-Funktion und geben ihm einen Fehlercode. Dann Hier setzen wir den neuen Knoten den Wert Feld, seinen i Feld gleich i, und dann werden wir verdrahten. Wir setzen den neuen Knoten der nächsten Zeiger auf ersten Punkt und dann die erste wird nun auf den neuen Knoten zeigen. Diese ersten Zeilen Code, wir tatsächlich den Bau des neuen Knotens. Nicht die letzten beiden Zeilen dieser Funktion, aber die ersten. Sie können tatsächlich ziehen Sie in eine Funktion, in eine Hilfsfunktion. Das ist oft das, was ich tue, ist, ziehe ich es in eine Funktion, Ich nenne es so etwas wie Build-Knoten, und dass die prepend Funktion ziemlich klein hält, ist es nur 3 Zeilen dann. Ich mache einen Anruf auf mein Build-Knoten-Funktion, und dann habe ich Draht alles durcheinander. 

Das letzte, was ich möchte Ihnen zeigen, und ich lasse Sie append und all das auf eigene Faust, ist, wie zum Iterieren über eine Liste. Es gibt eine Reihe von verschiedenen Möglichkeiten zur Iteration über eine Liste. In diesem Fall werden wir die Länge einer Liste zu finden. So beginnen wir mit Länge = 0. Dies ist sehr ähnlich zu schreiben strlen für eine Zeichenkette. Dies ist, was ich Ihnen zeigen, diese for-Schleife hier wollen. Es sieht irgendwie funky, es ist nicht die übliche int i = 0, i <whatever, i + +. Stattdessen ist es die Initialisierung unsere Variable n der Anfang der Liste stehen. Und dann, während unsere Iteratorvariable nicht null ist, halten wir. Dies liegt daran, durch Konvention, das Ende unserer Liste wird null sein. Und dann zu inkrementieren, anstatt sich + +, die verknüpfte Liste Äquivalent + + n = n-> nächsten. 

Ich lasse Sie in den Spalten hier ausfüllen, weil wir aus der Zeit sind. Aber denken Sie daran, wie Sie auf Ihrem spellr pset. Verkettete Listen, wenn Sie implementieren eine Hash-Tabelle, wird auf jeden Fall sehr nützlich sein. Und mit diesem Idiom für Schleife über Dinge, wird das Leben viel einfacher machen, hoffentlich. Haben Sie Fragen, schnell? [Sam] Werden Sie senden den ausgefüllten sll und sc? [Hardison] Yeah. Ich werde senden abgeschlossen Dias und fertig sll Stack und queue.cs. [CS50.TV]