[Powered by Google Translate] [Woche 4]
[David J. Malan] [Harvard University]
[Dies ist CS50.] [CS50.TV]
>> Alle Rechte, ist dies CS50, und dies ist der Beginn der Woche 4
und dies ist einer der langsamsten möglichen Sortieralgorithmen.
Welches war es, dass wir nur zugesehen da?
Das war bubble sort, um big O (n ^ 2) + Summe,
und in der Tat sind wir nicht die einzigen, die in dieser Welt scheinen zu wissen,
Welche bubble sort ist oder dessen Laufzeit.
In der Tat war dies ein Interview mit Eric Schmidt von Google
und ehemaliger Senator Barack Obama nur ein paar Jahre her.
>> Nun, Senator, sind Sie hier bei Google,
und Ich mag die Präsidentschaft als ein Vorstellungsgespräch zu denken.
Nun, es ist schwer, einen Job als Präsident bekommen, und du bist durch die Strapazen gehe jetzt.
Es ist auch schwer, einen Job bei Google zu bekommen.
Wir haben Fragen, und wir bitten unsere Kandidaten Fragen,
und dieses ist von Larry Schwimmer.
You guys glaube, ich bin ein Scherz? Es ist hier genau richtig.
Was ist der effizienteste Weg, um eine Million 32-Bit-Integer sortieren?
[Gelächter]
Well-
Es tut mir leid. >> Nein, nein, nein, nein.
Ich denke, die bubble sort wäre der falsche Weg zu gehen.
>> Come on, der ihm sagte, diese?
Letzte Woche erinnern wir uns eine Pause von Code, zumindest für einen Tag,
und begann mit Schwerpunkt auf einigen höherrangigen Ideen und Problemlösungen allgemein
im Rahmen der Suche und Sortierung,
und wir stellten etwas, das wir nicht zu schlagen diesen Namen auf letzte Woche,
aber asymptotische Notation, die Big O, der Big Omega,
und manchmal auch die Big Theta-Notation, und diese waren einfach Möglichkeiten
beschreiben die Laufzeit von Algorithmen,
wie viel Zeit für einen Algorithmus zum Ausführen dauert.
>> Und Sie erinnern sich vielleicht, dass Sie über die Laufzeit sprach in Bezug auf die Größe
des Eingangs, die wir allgemein n, was das Problem sein kann,
wobei n die Anzahl der Personen im Raum,
die Anzahl der Seiten in einem Telefonbuch, und wir begannen, die Dinge schreiben,
wie O (n ^ 2) oder O (n) oder O (n log n),
und selbst wenn die Mathematik nicht so recht geklappt so perfekt
und es war n ² - n / 2 oder so ähnlich
würden wir statt einfach wegwerfen einige der Terme niedrigerer Ordnung,
und die Motivation es ist, dass wir wirklich einen
Art objektive Art und Weise der Auswertung
die Leistung der Programme oder die Leistung der Algorithmen
dass am Ende des Tages nichts zu tun hat, beispielsweise
mit der Geschwindigkeit Ihres Computers heute.
>> Zum Beispiel, wenn Sie bei der Umsetzung bubble sort,
oder Sie implementieren Mergesort oder Auswahl Art auf der heutigen Computer,
ein 2 GHz Computer, und Sie laufen lassen,
und es dauert eine gewisse Anzahl von Sekunden, im nächsten Jahr gibt es einen 3 GHz
oder eine 4 GHz Computer, und man könnte dann behaupten, dass "Wow, mein Algorithmus
ist jetzt doppelt so schnell ", wenn in Wirklichkeit die offensichtlich nicht der Fall ist.
Es ist nur die Hardware ist mittlerweile schneller, aber Ihr Computer
nicht, und so wollen wir wirklich wegwerfen Dinge wie
Vielfache von 2 oder ein Vielfaches von 3, wenn es um die Beschreibung kommt
wie schnell oder wie langsam ein Algorithmus ist und wirklich nur zu konzentrieren
auf n oder einem Faktor davon,
etwas Strom davon, wie in dem Fall der Art von den letzten Wochen.
Und daran erinnern, dass mit Hilfe von Mergesort
konnten wir so viel besser als bubble sort und Auswahl sort
und sogar insertion sort.
>> Wir haben bis zu n log n, und wieder
daran erinnern, dass log n in der Regel bezieht sich auf etwas, das wächst
langsamer, dann n, so n log n bisher war gut
denn es war weniger als n ².
Aber zu erreichen n log n mit Mergesort
was war der Grund Keim einer Idee, die wir nutzen mussten
dass wir auch wieder in Woche 0 genutzt?
Wie haben wir bekämpfen die Sortierung Problem geschickt mit Mergesort?
Was war die wichtigste Erkenntnis, vielleicht?
Wer überhaupt.
Okay, lassen Sie uns einen Schritt zurück.
Beschreiben Mergesort in Ihren eigenen Worten.
Wie hat es funktioniert?
Okay, wir rudern zurück zur Woche 0.
Okay, yeah.
[Unverständlich-Student]
Okay, gut, so teilten wir die Anordnung von Zahlen in 2 Stücke.
Wir sortierten jedes dieser Stücke, und dann werden wir fusionierte sie,
und wir haben diese Idee schon einmal gesehen zu nehmen ein Problem, das diese groß ist
und Hacken es zu einem Problem, das dieser große oder diese groß ist.
>> Rufen Sie das Telefonbuch Beispiel.
Rufen Sie den Selbst-Zählung Algorithmus Wochen
so Mergesort wurde von diesem Pseudocode hier zusammengefasst.
Wenn Sie n Elemente sind gegeben, zuerst war es Plausibilitätsprüfung.
Wenn n <2 dann nicht überhaupt etwas tun
denn wenn n <2 ist, dann n 0 oder 1 ist offensichtlich,
und so, wenn es entweder ist 0 oder 1 gibt es nichts zu sortieren.
Du bist fertig.
Ihre Liste ist bereits trivial sortiert.
Aber sonst, wenn du hast 2 oder mehr Elementen gehen Sie vor und teilen sie
in 2 Hälften, links und rechts.
Sortieren jede dieser Hälften, und dann verschmelzen die sortierten Hälften.
Aber das Problem dabei ist, dass auf den ersten Blick, wie wir punting sind anfühlt.
Dies ist eine zirkuläre Definition, dass, wenn ich dich gebeten habe, diese n Elemente zu sortieren
und du willst mir erzählen, "Alles klar, gut, wir diese n / 2 und die n / 2 Elemente sortieren"
dann meine nächste Frage sein wird "Fine, wie sehen Sie die n / 2 Elemente zu sortieren?"
>> Aber aufgrund der Struktur dieses Programms,
weil es zu diesem Basismodell, so zu sprechen,
diesem speziellen Fall, dass, wenn n <Einige festen Wert wie 2 Rückkehr sofort sagt.
Nicht mit dem gleichen kreisförmigen Antwort reagieren.
Dieser Prozess wird diese Zyklizität schließlich am Ende.
Wenn ich Sie "Sortieren diese n Elemente" zu stellen und Sie sagen: "Fine, sortieren diese n / 2,"
dann sagen Sie, "Fine, sortieren diese n / 4, n / 8, N/16"
schließlich werden Sie von einem großen genug Zahl dividieren
dass Sie haben nur 1 Element links, an welchem ​​Punkt kann man sagen,
"Hier, hier ist eine sortierte einzelnes Element."
Dann die Brillanz dieses Algorithmus hier oben ist aus der Tatsache abzuleiten
dass, sobald Sie haben alle diese einzeln sortierten Listen,
von denen alle von der Größe 1, welches sich als nutzlos scheint,
sobald Sie anfangen, ihre Zusammenlegung und ihre Zusammenlegung
Sie bauen schließlich als Rob hat in dem Video ein finally sortierte Liste.
>> Aber diese Idee weit über Sortierung.
Es ist diese Idee in diesem Programm als Rekursion bezeichnet eingebettet,
die Idee, wodurch Sie ein Programm,
und ein Problem nennen Sie sich zu lösen,
oder im Kontext von Programmiersprachen Sie sind eine Funktion setzen,
und um ein Problem zu lösen, können Sie die Funktion nennen sich
wieder und wieder und wieder, aber Sie die Funktion
können nicht nennen sich unendlich oft.
Irgendwann muss man die Talsohle, so zu sprechen,
und haben einige hartcodierte base Zustand, sagt
an dieser Stelle aufhören, sich so, dass der gesamte Prozess
Schließlich ist in der Tat zu stoppen.
Was bedeutet das eigentlich, um recurse?
>> Mal sehen, ob wir eine einfache, triviale Beispiel mit tun können, sagen wir,
3 Leute mit mir hier oben auf der Bühne, wenn jemand ist komfortabel.
1, auf bis, 2 und 3 kommen.
Wenn Sie 3 bis hier herauf kommen wollen.
Wenn Sie direkt stehen, um mich hier in einer Linie wollen, nehme an, dass das Problem an der Hand
ist sehr trivial zählen die Anzahl der Menschen, die hier sind.
Aber ehrlich gesagt, ich bin müde von all diesen zählen Beispiele.
Das wird einige Zeit dauern, 1, 2 und Punkt, Punkt, Punkt zu nehmen.
Es wird ewig dauern.
Ich würde lieber nur punt dieses Problem überhaupt mit Hilfe der-wie ist dein Name?
Sara. >> Sara, alles in Ordnung.
Kelly. >> Kelly und?
>> Willy. >> Willy, Sara, Kelly und Willy.
Im Moment habe ich die Frage von jemandem gefragt,
wie viele Menschen auf dieser Stufe, und ich habe keine Ahnung.
Dies ist eine wirklich lange Liste, und so statt Ich werde diesen Trick zu tun.
Ich werde die Person neben mir die meiste Arbeit tun, fragen,
und sobald sie getan wird dabei die meiste Arbeit
Ich werde die geringste Menge an Arbeit zu tun und fügen Sie einfach 1
um was ihre Antwort ist, so here we go.
Ich bin gebeten worden, wie viele Menschen auf der Bühne.
Wie viele Menschen sind auf der Bühne nach links von euch?
Die links von mir? >> Okay, aber nicht zu betrügen.
Das ist gut, das ist richtig, aber wenn wir wollen, diese Logik weiter
Lassen Sie uns annehmen, dass Sie ähnlich wollen punt dieses Problem auf der linken Seite von Ihnen,
so als Antwort direkt vor gehen und nur die Schuld zuschieben.
Oh, wie viele Menschen sind auf der linken Seite von mir?
Wie viele Menschen sind auf der linken Seite?
Ein.
[Gelächter]
Okay, so 0, so was nun Willy getan hat
ist du hast wieder deine Antwort in diese Richtung sagen 0.
Nun, was sollte man tun? >> 1.
Okay, so dass Sie die 1 sind, so dass Sie sagen: "Alles klar, werde ich hinzu: 1
um unabhängig von Willy Graf war, "so 1 + 0.
Du bist jetzt ein so Ihre Antwort auf der rechten Seite ist jetzt
1. >> Und mir würde 2 sein.
Gut, so nimmst du die vorherige Antwort von 1,
Hinzufügen die minimale Menge an Arbeit, die Sie tun möchten, ist die +1.
Sie haben nun 2, und Sie dann gib mir welchen Wert?
3, meine ich, sorry, 2.
Gut.
>> Nun, wir hatten 0 nach links.
Dann hatten wir ein, und dann fügen wir 2,
und jetzt bist du reichte mir die Nummer 2
und so sage ich, okay, +1, 3.
Es gibt ja 3 Personen neben mir auf der Bühne,
so konnten wir natürlich getan haben dies sehr linear,
sehr viel in der Hand Mode, aber was wir wirklich tun?
Wir haben ein Problem der Größe 3 zunächst.
Wir haben dann brach es sich in ein Problem der Größe 2,
dann ein Problem der Größe 1, und dann schließlich die Base-Case-
war wirklich, oh, es ist niemand da,
an welcher Stelle Willy kehrte effektiv eine hartcodierte Antwort ein paar Mal,
und die zweite wurde dann, sprudelte, sprudelte sprudelte,
und dann durch Zugabe von in diesem einen zusätzlichen 1
Wir haben diese Grundidee der Rekursion implementiert.
>> Nun, in diesem Fall ist es nicht wirklich ein Problem zu lösen
mehr effektiv dann haben wir bisher gesehen.
Aber über die Algorithmen, die wir auf der Bühne gemacht habe bisher denken.
Wir hatten 8 Stück Papier an die Tafel,
auf Video, als Sean wurde für die Zahl 7 suchen, und was hat er wirklich?
Nun, er nicht jede Art von Teile und Herrsche.
Er tat es nicht jede Art von Rekursion.
Vielmehr ist er gerade tat diese lineare Algorithmus.
Aber wenn wir die Idee von sortierten Zahlen auf Stufe eingeführt leben letzten Woche
dann hatten wir diesen Instinkt zu gehen bis in die Mitte,
An diesem Punkt hatten wir eine kleinere Liste der Größe 4 oder einer anderen Liste der Größe 4,
und dann haben wir genau das gleiche Problem hatten, so dass wir wiederholt, wiederholt, wiederholt.
Mit anderen Worten, wir rekursiv.
Vielen Dank an unsere 3 Freiwilligen hier zur Demonstration Rekursion mit uns.
>> Lasst uns sehen, ob wir nicht machen dies nun ein wenig konkreter,
ein Problem zu lösen, dass wir wieder konnte ziemlich leicht tun,
aber wir werden es als ein Sprungbrett für die Umsetzung dieser Grundidee verwenden.
Wenn ich will, um die Summierung einer Reihe von Zahlen zu berechnen,
zum Beispiel, wenn Sie passieren in der Nummer 3,
Ich möchte Ihnen den Wert von Sigma 3,
so dass die Summe von 3 + 2 + 1 + 0.
Ich will wieder die Antwort 6,
so dass wir implementieren diese sigma Funktion, diese Summenfunktion
dass wiederum nimmt im Eingang, und kehrt dann die Summation
dieser Zahl den ganzen Weg hinunter auf 0 gesetzt.
Wir könnten dies ziemlich einfach zu tun, nicht wahr?
Wir könnten dies mit irgendeiner Art von looping Struktur zu tun,
so lassen Sie mich gehen Sie vor und bekomme gestartet.
>> Include stdio.h.
Lassen Sie mich mich in Haupt mit hier zu arbeiten.
Retten wir dies als sigma.c.
Dann werde ich hier, und ich werde einen int n erklären,
und ich werde Folgendes tun, während der Benutzer nicht kooperiert.
Während der Benutzer hat mir nicht eine positive Zahl
Lassen Sie mich gehen Sie vor und fordert sie für n = GetInt,
und lassen Sie mich ihnen einige Anweisungen, was zu tun ist,
so printf ("Positive Ganzzahl bitte").
Nur etwas relativ einfach wie diese, so dass durch die Zeit, die wir Zeile 14 getroffen
wir haben jetzt eine positive ganze Zahl vermutlich in n.
>> Jetzt machen wir etwas mit ihm.
Lassen Sie mich gehen Sie vor und berechnet die Summe, so int sum = sigma (n).
Sigma ist nur Summation, so Ich schreibe es in der ausgefalleneren Art und Weise.
Wir nennen es einfach sigma gibt.
Das ist die Summe, und jetzt werde ich zum Ausdrucken des Ergebnisses,
printf ("Die Summe ist% d \ n", sum).
Und dann werde ich 0 für eine gute Maßnahme zurück.
Wir haben alles, was dieses Programm erfordert außer der interessanteste Teil getan,
was tatsächlich umzusetzen den sigma-Funktion.
>> Lassen Sie mich gehen hier unten auf den Boden, und lassen Sie mich erklären, Funktion sigma.
Es muss eine Variable vom Typ integer ist zu nehmen,
und was Datentyp will ich vermutlich wieder von Sigma?
Int, weil ich es zu meinen Erwartungen on line 15 entsprechen soll.
Hier lassen Sie mich gehen Sie vor und implementieren diese
in einem hübschen unkompliziert.
>> Fahren wir fort und sagen int sum = 0,
und jetzt werde ich gehen ein wenig for-Schleife hier
das wird so etwas sagen,
for (int i = 0; i <= Zahl; i + +) sum + = i.
Und dann werde ich Betrag zurückzuerstatten.
Ich konnte dies in irgendeiner Anzahl von Arten implementiert sein.
Ich konnte eine while-Schleife verwendet haben.
Ich konnte übersprungen Verwendung der Summe Variable, wenn ich wirklich wollte zu haben,
aber kurz, wir haben nur eine Funktion, wenn ich nicht goof erklärt Summe 0 ist.
Dann durchläuft von 0 auf bis über die Anzahl,
und bei jeder Iteration fügt es, dass die gegenwärtige Wert Summe und kehrt dann Summe.
>> Jetzt gibt es eine leichte Optimierung hier.
Dies ist wahrscheinlich eine Verschwendung Schritt, aber es so sein. Das ist jetzt in Ordnung.
Wir sind zumindest ist gründlich und gehen 0 den ganzen Weg rauf.
Nicht sehr hart und ziemlich einfach,
aber es stellt sich heraus, dass mit dem Sigma-Funktion, die wir die gleichen Chancen haben,
wie wir es hier getan habe auf der Bühne.
Auf der Bühne haben wir nur gezählt, wie viele Leute waren neben mir,
sondern wenn wir wollten, um die Zahl 3 + 2 + 1 zu zählen
auf bis zu 0 könnten wir ähnlich punt zu einer Funktion
dass ich statt als rekursive beschreiben.
Hier wollen wir tun, eine schnelle Vernunft und zu überprüfen, damit ich nicht goof.
>> Ich weiß, es ist zumindest eine Sache in diesem Programm, dass ich falsch gemacht habe.
Wenn ich in traf ich werde jede Art von schrie mich bekommen?
Was mache ich bei etwa werden angeschrien?
Ja, ich den Prototyp vergessen, so verwende ich eine Funktion namens Sigma on line 15,
aber es ist nicht bis Zeile 22 deklariert, so dass ich am besten proaktiv gehen hier
und erklären, ein Prototyp, und ich werde int sigma (int number) sagen, und das ist es.
Es ist an der Unterseite umgesetzt.
>> Oder eine andere Art, wie ich dieses Problem lösen könnte,
Ich konnte die Funktion dort oben zu bewegen, das ist nicht schlecht,
aber zumindest, wenn Ihre Programme zu starten, um lange, ehrlich gesagt,
Ich denke, es gibt einige Wert in immer mit Haupt an der Spitze
so dass Sie in der Leser kann die Datei öffnen und dann sofort sehen,
was das Programm, ohne sich durch sie zu suchen dabei
Suche nach dem main-Funktion.
Wir gehen hinunter zu meinem Terminal-Fenster hier, versuchen Sie, sigma machen sigma,
und ich vermasselt auch hier.
Implizite Deklaration der Funktion GetInt heißt, ich habe vergessen, was tun?
[Unverständlich-Student]
Gut, so scheint ein weit verbreiteter Irrtum, so lasst uns dieses hier,
cs50.h, und jetzt gehen wir zurück zu meinem Terminal-Fenster.
>> Ich werde den Bildschirm, und ich werde erneut machen sigma.
Es scheint zusammengestellt. Lassen Sie mich jetzt laufen sigma.
Ich werde in der Nummer 3 geben, und ich habe 6 erhalten, so dass nicht eine strenge Prüfung,
aber zumindest scheint es auf den ersten Blick zu arbeiten, aber jetzt wollen wir zerreißen sie auseinander,
und lasst uns tatsächlich nutzen die Idee der Rekursion wieder
in einer sehr einfachen Rahmen, so dass in ein paar Wochen Zeit,
wenn wir erkunden schicker Datenstrukturen als Arrays
Wir haben ein anderes Werkzeug im Toolkit, mit dem
Bearbeitung dieser Datenstrukturen wie wir sehen werden.
Dies ist die iterative Vorgehensweise, die Schleife Ansatz.
>> Lassen Sie mich statt jetzt tun.
Lassen Sie mich stattdessen sagen, dass die Summe der Anzahl
auf bis zu 0 ist wirklich das gleiche wie
Nummer + sigma (Anzahl - 1).
In anderen Worten, genau wie auf der Bühne I zu jedem der Leute neben mir punted,
und sie wiederum hielt punting bis wir die Talsohle endlich bei Willy,
Wer hatte einen hartcodierten Antwort wie 0 zurück.
Hier nun sind wir ähnlich punting zu Sigma
die gleiche Funktion wie hieß ursprünglich, aber die wichtigste Erkenntnis hier
ist, dass wir nicht anlaufen sigma identisch.
Wir sind nicht auf und übergibt n.
Wir deutlich vorbei an der Zahl - 1,
so ein etwas kleineres Problem, geringfügig kleiner Problem.
>> Leider ist dies nicht ganz eine Lösung noch nicht, und ehe wir
was sein könnte herausspringen so offensichtlich bei einigen von euch
Lassen Sie mich gehen Sie vor und führen Sie machen.
Es scheint zu kompilieren okay.
Lassen Sie mich erneut sigma mit 6.
Whoops, lass mich erneut sigma mit 6.
Wir haben dies vor, wenn auch versehentlich letzte Mal gesehen, wie gut.
Warum habe ich diese kryptischen Segmentation Fault? Yeah.
[Unverständlich-Student]
Es gibt keine base case, genauer gesagt, was wohl passiert?
Dies ist ein Symptom, welches Verhalten?
Sagen Sie es ein wenig lauter.
[Unverständlich-Student]
Es ist eine unendliche Schleife effektiv, und das Problem mit Endlosschleifen
wenn sie beinhalten Rekursion in diesem Fall ruft eine Funktion selbst,
was passiert jedes Mal, wenn Sie eine Funktion aufrufen?
Nun, denken Sie zurück an, wie wir legte den Speicher in einem Computer.
Wir haben gesagt, dass es dieses Stück Speicher genannt Stack, der an der Unterseite ist,
und jedes Mal, wenn Sie eine Funktion aufrufen ein wenig mehr Speicher wird gesetzt
auf dieser sogenannten Stack enthält dieses Funktionsdisplay lokalen Variablen oder Parameter,
also wenn sigma nennt Sigma Anrufe Sigma nennt sigma
nennt Sigma Woher kommt diese Geschichte?
>> Nun, es ist schließlich Überschreitungen der Gesamtbetrag
der Erinnerung, die Sie zur Verfügung zu Ihrem Computer haben.
Sie überrannt das Segment, das man eigentlich zum Verweilen ein,
und Sie diese Segmentation Fault zu bekommen, Core Dump,
und was core dumped bedeutet, ist, dass ich jetzt eine Datei namens core
das ist eine Datei mit Nullen und Einsen
, dass in der Zukunft tatsächlich wird diagnostisch nützlich.
Wenn es nicht klar, wo Ihre Fehler ist
Sie konkret tun können ein bisschen forensische Analyse, so zu sprechen,
auf dieser Core-Dump-Datei ist, die wiederum nur eine ganze Reihe von Nullen und Einsen
das stellt im Wesentlichen den Zustand Ihres Programms im Speicher
der Moment, es stürzte auf diese Weise.
>> Der Fix ist, dass wir nicht einfach blind zurück sigma,
die Zahl + Sigma von einem etwas kleineren Problem.
Wir müssen eine Art von base case hier zu haben,
und was sollte die Basis Fall wahrscheinlich sein?
[Unverständlich-Student]
Okay, so lange die Zahl positiv ist, dass wir eigentlich wieder dazu
oder anders gesagt, wenn die Zahl, sagen wir, <= auf 0
wissen Sie was, ich werde weitermachen und 0 zurückgeben,
ähnlich wie Willy tat, und sonst, ich werde weitermachen
und geben diese, so dass es nicht so viel kürzer
als die iterative Version, dass wir Schlagsahne zuerst mit einer for-Schleife
aber feststellen, dass es diese Art von Eleganz zu.
Statt der Rücksendung eine gewisse Anzahl und Durchführung all diese math
und das Hinzufügen Dinge mit lokalen Variablen
Sie stattdessen sagen: "Okay, wenn dies ist ein super einfaches Problem,
wie die Zahl <0 ist, lassen Sie mich sofort 0 zurück. "
>> Wir gehen nicht auf die Unterstützung negative Zahlen stören,
so bin ich zu hart Code wird den Wert von 0 auf.
Aber sonst, zur Umsetzung dieser Idee Summierung
alle diese Zahlen zusammen können Sie effektiv einen kleinen Happen
aus dem Problem, viel wie wir hier auf der Bühne,
dann punt der Rest des Problems an die nächste Person,
aber in diesem Fall die nächste Person ist sich.
Es ist eine gleichnamige Funktion.
Übergeben Sie einfach es ist ein kleiner und kleineres Problem jedes Mal,
und obwohl wir noch nicht ganz formalisiert Dinge im Code hier
das ist genau, was los war in Woche 0 mit dem Telefonbuch.
Das ist genau, was los war in den vergangenen Wochen mit Sean
und mit unseren Demonstrationen der Suche nach Zahlen.
Es dauert ein Problem und dividiert sie wieder und wieder.
>> In anderen Worten, es ist ein Weg, jetzt übersetzen
Diese realen Welt Konstrukt, diese höhere Ebene Konstrukt
des divide et impera und etwas wieder und wieder
im Code, so ist dies etwas, das wir wieder sehen wird im Laufe der Zeit.
Jetzt, als beiseite, wenn Sie neu in Rekursion sind, sollten Sie zumindest verstehe jetzt
warum das so ist lustig.
Ich werde auf google.com gehen,
und ich werde für ein paar Tipps und Tricks auf Rekursion zu suchen, geben.
Sagen Sie der Person neben dir, wenn sie nicht lachten gerade jetzt.
Meinten Sie Rekursion?
Meinten Sie-ah, es geht los.
Okay, das ist jetzt, dass der Rest der jedermann.
Ein wenig Osterei irgendwo in Google eingebettet.
Nebenbei, einer der Links, die wir auf dem Kurs der Website genommen
heute ist nur dieses Gitter verschiedener Sortieralgorithmen
von denen wir einige sah letzte Woche, aber was ist mit dieser Visualisierung schöne
wie Sie versuchen, Ihren Verstand um verschiedene Dinge im Zusammenhang mit Algorithmen wickeln
wissen, dass man sehr leicht jetzt mit verschiedenen Eingängen zu beginnen.
Die Eingänge alle umgekehrt, meist die Eingänge sortiert, die Eingänge zufällig und so weiter.
Wie Sie, erneut zu versuchen, zeichnen diese Dinge im Kopf
erkennen, dass diese URL auf den Verlauf der Website auf dem Lectures Seite
könnte Ihnen helfen, Vernunft durch einige von denen.
>> Heute haben wir endlich mal dieses Problem eine Weile zurück zu lösen,
was war, dass diese Swap-Funktion einfach nicht funktioniert,
und was war das grundlegende Problem mit dieser Funktion swap,
deren Ziel es war wieder um einen Wert hier und hier austauschen
so dass in diesem Fall?
Das ist nicht wirklich funktionieren. Warum?
Yeah.
[Unverständlich-Student]
Genau, die Erklärung für diese Verrücktheit
war einfach, weil, wenn Sie die Funktionen in C aufrufen
und jene Funktionen übernehmen Argumente, wie a und b hier
Sie werden in Kopien, was Wert du auf diese Funktion, die vorbei.
Sie sind nicht die Bereitstellung der ursprünglichen Werte selbst,
so sahen wir dies im Rahmen der buggyc,
buggy3.c, die ein wenig so etwas sah.
>> Erinnern, dass wir x und y auf 1 und 2 initialisiert sind.
Wir haben dann, was sie gedruckt wurden.
Ich habe dann behauptet, dass ich tauschen sie durch den Aufruf Tausch von x, y.
Aber das Problem war, dass der Austausch funktioniert,
aber nur im Rahmen der Swap-Funktion selbst.
Sobald wir getroffen Linie 40 Diejenigen getauschte Werte
wurden weggeworfen, und so nichts
in der ursprünglichen Funktion main wurde tatsächlich geändert überhaupt,
Wenn Sie also denken, damals, was so aussieht wie in Bezug auf unser Gedächtnis
wenn dies linken Seite des Brettes für-
und ich werde mein Bestes für alle, um zu sehen this-wenn dies linken Seite des Brettes
stellt, sagen wir, Ihre RAM, und der Stapel wird wachsen auf bis auf diese Weise,
und wir nennen eine Funktion wie Haupt-und wichtigsten verfügt über 2 lokale Variablen x und y,
Lassen Sie uns beschreiben, die als x hier, und wir beschreiben diese als y hier
und lassen Sie uns in den Werten 1 und 2 gesetzt, so ist das hier main,
und wenn Haupt ruft die Swap-Funktion des Betriebssystems
verleiht dem Swap-Funktion eine eigene Schneise der Speicher auf dem Stack,
eigenen Rahmen auf dem Stack, so zu sprechen.
Es teilt auch 32 Bit für diese ints.
Es passiert nennen a und b, aber das ist völlig willkürlich.
Es könnte sie berufen habe, was sie will, aber was passiert, wenn der Haupt-
Anrufe Swap ist es dauert diese 1, legt eine Kopie gibt, legt eine Kopie gibt.
>> Es gibt 1 weitere lokale Variable in swap, aber als was? >> Tmp.
Tmp, so lassen Sie mich mich noch 32 Bits hier
und was habe ich zu tun in dieser Funktion?
Ich sagte int tmp bekommt ein, so dass eine hat 1, also tat ich dies, wenn wir mit diesem Beispiel zuletzt gespielt.
Dann ein bekommt b, so b 2, so dass nun wird dies 2,
und nun b erhält temp, so temp ist 1,
so jetzt b wird diese.
Das ist toll. Es funktionierte.
Aber dann, sobald die Funktion zurückkehrt
Swap-Speicher effektiv ausgeblendet, so dass es wiederverwendet werden kann
durch eine andere Funktion in der Zukunft, und die wichtigsten ist offensichtlich völlig unverändert.
Wir brauchen einen Weg grundlegend Lösung dieses Problems
und heute werden wir endlich einen Weg, dies zu tun, wobei
können wir die Einführung einer so genannten Zeiger.
Es stellt sich heraus, dass wir dieses Problem lösen kann
nicht durch Einleiten von Kopien von x und y
sondern, indem in dem, was, denken Sie an den Swap-Funktion?
Ja, was ist die Adresse?
Wir haben nicht wirklich über Adressen sehr detailliert gesprochen,
aber wenn diese Tafel stellt meine Arbeitsspeicher des Computers
Wir könnten sicherlich Nummerierung beginnen die Bytes in meinem RAM
und sagen, das ist das Byte Nr. 1, ist dieses Byte # 2, Byte # 3,
Byte # 4, Byte # ... 2 Milliarden, wenn ich 2 Gigabyte RAM haben,
so konnten wir sicherlich kommen mit einer beliebigen Numerierung
für alle einzelnen Bytes in meinem Arbeitsspeicher des Computers.
>> Was wäre, wenn statt, wenn ich Makeln
anstatt Durchgang in Kopien von x und y
warum ich nicht stattdessen in der Adresse x dahin,
die Adresse y hier im wesentlichen die Postanschrift
von x und y, weil dann tauschen, wenn er informiert
der Adresse im Speicher von x und y,
dann tauschen, wenn wir ihn trainiert ein wenig,
Er könnte zu dieser Adresse fahren, so zu sprechen,
x, und ändern Sie dort die Rufnummer, dann an die Adresse von y zu fahren,
die Anzahl gibt, auch wenn nicht eigentlich immer Kopien von den Werten selbst,
so, obwohl wir sprachen über dies als wichtigsten Speicher
und dies als Swap-Speicher die Mächtigen und die gefährlichste Teil C
ist, dass jede Funktion Speicher überall in dem Computerspeicher zu berühren,
und dies ist mächtig, dass man sehr ausgefallene Dinge mit Computerprogrammen in C schreiben
Dies ist gefährlich, da man auch vermasseln sehr leicht.
Tatsächlich einem der gängigsten Methoden für Programme in diesen Tagen ausgenutzt werden
noch für einen Programmierer nicht zu erkennen,
dass er oder sie ermöglicht eine Daten
in einer Speicherstelle, die nicht beabsichtigt war geschrieben werden.
>> Zum Beispiel erklärt er oder sie ein Array der Größe 10
aber dann versehentlich versucht, 11 Bytes in dieser Reihe von Speicher abgelegt,
und starten Sie berühren Teile des Speichers, die nicht mehr gültig sind.
Nur um kontextuelle dies könnte einige von euch wissen, dass
Software oft fordert Sie auf, Seriennummern oder Registrierungsschlüssel,
Photoshop und Word und Programme wie dieses.
Es gibt Risse, wie einige von euch wissen, online, wo kann man ein kleines Programm ausführen,
und voila, keine Aufträge mehr für eine Seriennummer.
Wie ist das Problem?
In vielen Fällen sind diese Dinge sind einfach zu finden in den Computern
Textsegmente in den Computer tatsächlichen Nullen und Einsen
wo ist diese Funktion, wo die Seriennummer angefordert wird,
und überschreiben Sie diesen Raum, oder während das Programm läuft
Sie können herausfinden, wo der Schlüssel tatsächlich gespeichert wird
mit etwas namens ein Debugger, und Sie können Software, die Art und Weise zu knacken.
Dies ist nicht zu sagen, dass dies unser Ziel ist es, für die nächsten paar Tage,
aber es hat sehr reale Konsequenzen.
Dass man passiert den Diebstahl von Software beinhalten,
aber es gibt auch Kompromisse kompletter Maschinen.
>> In der Tat, wenn Webseiten in diesen Tagen ausgebeutet werden
und kompromittiert und die Daten zugespielt und Passwörter gestohlen werden
sehr oft bezieht sich auf schlechtes Management des eigenen Speicher,
oder, im Fall von Datenbanken, zum Scheitern antizipieren
kontradiktorischen Eingang, so mehr auf, dass in den kommenden Wochen,
aber für jetzt nur eine Vorschau auf die Art von Schäden, die Sie tun können
um nicht ganz zu verstehen, wie die Dinge unter der Haube arbeiten.
Lassen Sie uns über das Verständnis, warum dies ist kaputt gehen
mit einem Werkzeug, das wird mehr und mehr nützlich
wie unsere Programme immer komplexer.
So weit, wenn Sie habe einen Fehler in Ihrem Programm
wie haben Sie zum Debuggen es weg?
Was haben Ihre Techniken bisher gewesen, ob von Ihrem TF unterrichtet
oder einfach nur Autodidakt?
[Student] Printf.
Printf, so printf ist wahrscheinlich dein Freund, dass, wenn Sie sehen wollen
was los ist auf der Innenseite des Programms
setzt man printf hier printf hier printf hier.
Anschließend führen Sie es, und Sie bekommen eine ganze Menge Zeug auf dem Bildschirm
die Sie verwenden können, um dann ableiten, was ist eigentlich los in Ihrem Programm falsch.
>> Printf neigt dazu, eine sehr mächtige Sache sein,
aber es ist ein sehr manueller Prozess.
Sie müssen eine printf hier setzen, ein printf hier
und wenn man es innerhalb einer Schleife erhalten Sie möglicherweise 100 Zeilen
der Ausgabe, die Sie dann zu sichten.
Es ist nicht eine sehr benutzerfreundliche und interaktive Mechanismus für Debuggen von Programmen,
aber zum Glück gibt es Alternativen.
Es ist ein Programm, zum Beispiel, genannt GDB, der GNU Debugger,
das ist etwas obskure, wie Sie es verwenden.
Es ist ein wenig komplex, aber ehrlich gesagt,
Dies ist eines der Dinge, wo, wenn Sie in dieser Woche gestellt und im nächsten
die zusätzliche Stunde so etwas wie GDB verstehen
es spart Ihnen wahrscheinlich Dutzende von Stunden auf lange Sicht,
so mit, dass, lassen Sie mich Ihnen einen Vorgeschmack, wie dieses Ding funktioniert.
>> Ich bin in meinem Terminal-Fenster.
Lassen Sie mich gehen Sie vor und dieses Programm kompilieren, buggy3.
Es ist bereits up to date.
Lassen Sie mich laufen lassen, so wie wir eine Weile zurück tat, und in der Tat, es ist gebrochen.
Aber warum ist das? Vielleicht habe ich vermasselt die Swap-Funktion.
Vielleicht ist es a und b. Ich bin nicht ganz bewegt sie herum richtig.
Lassen Sie mich gehen Sie vor und tun dies.
Anstatt nur buggy3 laufen lassen mich stattdessen dieses Programm GDB,
und ich werde es sagen, buggy3 laufen,
und ich werde ein Befehlszeilenargument-tui gehören,
und wir werden dies auch in Zukunft Probleme bei spec zu erinnern setzen.
Und nun diese Schwarz-Weiß-Schnittstelle tauchte, dass wieder
ist ein wenig überwältigend auf den ersten, weil es all dies
Informationen zur Garantie hier unten, aber zumindest gibt es etwas Vertrautes.
Im oberen Bereich des Fensters ist meine eigentliche Code,
und wenn ich nach oben ließ mich hier navigieren Sie zu dem ganz oben auf meiner Datei
und in der Tat, es gibt buggy3.c, und beachten Sie am unteren Rand des Fensters
Ich habe dieses GDB prompt.
>> Dies ist nicht das Gleiche wie mein normales John Harvard prompt.
Dies ist eine Aufforderung, die gehen mir zu erlauben, GDB Control.
GDB ist ein Debugger.
Ein Debugger ist ein Programm, das Sie durch gehen können
Ausführung des Programms Zeile Zeile für Zeile,
entlang des Weges zu tun, was Sie wollen mit dem Programm,
auch den Aufruf von Funktionen, oder auf der Suche, was noch wichtiger ist,
an verschiedenen Variablen Werte.
Lasst uns weitermachen und tun.
Ich werde weitermachen und geben Sie in Lauf bei GDB Eingabeaufforderung
so an der Unterseite des Bildschirms Ich tippte laufen gelassen haben bemerkt,
und ich habe getroffen, und geben, was half das?
Es ist buchstäblich lief mein Programm, aber ich habe nicht wirklich viel zu sehen hier gehen
weil ich habe nicht wirklich gesagt, den Debugger
zu pausieren zu einem bestimmten Zeitpunkt.
Nur die Eingabe run läuft das Programm.
Ich weiß nicht wirklich etwas sehen. Ich kann mich nicht manipulieren.
>> Stattdessen lassen Sie mich dies tun.
An diesem GDB Prompt ließ mich stattdessen schreiben Pause geben.
Das ist nicht, was ich zu geben gemeint.
Lasst uns stattdessen schreiben Pause main.
In anderen Worten, ich möchte so etwas wie ein Breakpoint gesetzt,
was ist treffend benannt, weil sie brechen oder Pause
Ausführung des Programms an diesem besonderen Ort.
Main ist der Name meiner Funktion.
Beachten Sie, dass GDB ziemlich schlau ist.
Es herausgefunden, dass Haupt auf rund beginnen in Zeile 18 geschieht,
der buggy3.c, und dann hier bemerken, links oben
b + befindet sich direkt neben der Leitung 18.
Das ist erinnert mich, dass ich einen Haltepunkt in Zeile 18 gesetzt.
Dieses Mal, wenn ich run geben, werde ich mein Programm laufen
bis er trifft, dass Haltepunkt,
so dass das Programm pausiert für mich in Zeile 18.
Here we go, laufen.
Nichts scheint passiert zu sein, aber beachten Sie unten links
Starten des Programms, buggy3, Haltepunkt 1 in Haupt am buggy3.c Linie 18.
Was kann ich jetzt tun?
>> Beachten Sie, ich kann der Eingabe beginnen Dinge wie Druck,
nicht printf, print x, und das ist jetzt seltsam.
Das $ 1 ist nur ein Kuriosum, wie wir sehen werden
jedes Mal, wenn Sie etwas ausdrucken erhalten Sie eine neue $ value.
Das ist so, dass man entnehmen zurück zur vorherigen Werte nur für den Fall,
aber für jetzt, was Druck ist mir zu sagen ist, dass der Wert von x an diesem Punkt in der Geschichte
ist offenbar 134514032.
Was? Wo hast, dass auch herkommen?
[Unverständlich-Student]
In der Tat ist das, was wir eine Garbage-Wert nennen, und wir haben nicht darüber gesprochen noch
aber der Grund, dass Sie Variablen zu initialisieren
ist offensichtlich so, dass sie einen gewissen Wert, dass Sie wollen, dass sie bei sich haben müssen.
Aber der Haken ist daran erinnern, dass Sie Variablen deklarieren
wie ich vorhin in meinem Sigma beispielsweise
ohne tatsächlich ihnen einen Wert.
Erinnern, was ich über habe hier im Sigma.
Ich erklärte n, sondern welchen Wert habe ich ihm geben?
Keine, weil ich wusste, dass in den nächsten paar Zeilen
GetInt kümmern würde das Problem der Umsetzung einen Wert innerhalb der n nehmen.
>> Aber an diesem Punkt in der Geschichte der Linie 11
und Linie 12 und Linie 13 und Linie 14
in all den mehreren Zeilen ist, was der Wert von n?
In C Sie wissen einfach nicht.
Es ist in der Regel einige Müll Wert, einige völlig Zufallszahl
Das ist mehr als im Wesentlichen aus einem früheren Funktion verlassen
worden laufen, so wie Ihr Programm läuft
daran erinnern, dass function, Funktion, Funktion erhält.
All diese Bilder bekommen auf den Speicher zu stellen, und dann jene Funktionen geben,
und genau wie ich vorgeschlagen mit dem Radiergummi ihr Gedächtnis schließlich wiederverwendet wird.
Nun, es passiert einfach so, dass diese Variable x in diesem Programm
scheint enthalten einige Müll Wert wie 134514032 haben
aus einem früheren Funktion, nicht ein, dass ich geschrieben habe.
Es könnte etwas die effektiv kommt mit dem Betriebssystem sein,
eine Funktion unter der Haube.
>> Okay, das ist in Ordnung, aber wir nun voraus auf die nächste Zeile.
Wenn ich "next" an meinem GDB Eingabeaufforderung eingeben und ich drücken Sie Enter
feststellen, dass die Hervorhebung nach unten bewegt, um die Leitung 19,
sondern die logische Implikation ist, dass Zeile 18
ist nun fertig ausgeführt, so dass, wenn ich wieder geben "print x"
Ich sollte jetzt 1, und in der Tat, das tue ich.
Auch hier ist die $ zeug ein Weg GDB Sie daran erinnert,
was die Geschichte der Ausdrucke sind, dass du getan hast.
Nun lassen Sie mich gehen Sie vor und drucken Sie y, und in der Tat ist y ein paar verrückte Wert als gut,
aber keine große Sache, weil in Zeile 19 sind wir zu zuweisen
der Wert 2, so lassen Sie mich geben "next" wieder.
Und jetzt sind wir auf dem printf Linie.
Lass es mich tun print x.
Lass es mich tun Print y. Ehrlich gesagt, ich bin ein wenig müde von Druck-dies.
Lassen Sie mich statt geben "Anzeige x" und "Display y"
und jetzt jedes Mal, wenn ich einen Befehl in der Zukunft
Ich werde von dem, was erinnert werden x und y, was ist x und y, was ist x und y.
>> Ich kann auch, wie eine Seite, geben Sie "info Einheimischen."
Info ist ein spezieller Befehl.
Die Einheimischen bedeutet dies zeigt mir die lokalen Variablen.
Nur für den Fall vergesse ich oder ist dies eine verrückte, komplizierte Funktion
dass ich oder jemand anderes schrieb info Einheimischen werden Ihnen sagen,
was sind all die lokalen Variablen innerhalb dieses lokalen Funktion
dass Sie vielleicht zu, wenn Sie wollen, um stecken zu kümmern.
Jetzt, printf ist ca. auszuführen, so lassen Sie mich weiter und geben Sie einfach gehen "Weiter".
Weil wir in diesem Umfeld sind wir nicht wirklich sehen es
führen hier unten, aber feststellen, es ist immer ein wenig verstümmelt hier.
Aber merkt es das Überschreiben der Bildschirm gibt,
so ist es nicht ein perfektes Programm hier, aber das ist okay, weil ich immer in der Nähe stecken kann
mit Druck, wenn ich will.
>> Lassen Sie mich nächste wieder geben, und jetzt hier ist der interessante Teil.
An diesem Punkt in der Geschichte y gleich 2 ist und x 1 ist,
wie hier vorgeschlagen, und wieder
Der Grund dies automatisch angezeigt wird, ist, weil ich den Befehl verwendet
Anzeige x und Anzeige y, so dass der Moment, als ich als nächstes schreiben
in der Theorie x und y werden sollte getauscht.
Nun, wir wissen bereits, dass wird nicht der Fall sein,
aber wir werden gleich sehen, wie wir tiefer tauchen, um herauszufinden, warum das so ist wahr.
Weiter, und leider ist y noch 2 und x ist noch 1, und ich kann so viel zu bestätigen.
Drucken x-, Druck-y.
In der Tat, kein Swapping tatsächlich passiert, so beginnen wir diese über.
Klar Swap ist gebrochen.
Lasst uns stattdessen schreiben "run" wieder.
Lassen Sie mich sagen, ja, ich will es von Anfang starten wollen, geben.
>> Jetzt bin ich wieder in Zeile 18.
Jetzt bemerken, x und y sind Müll Werte wieder.
Weiter, weiter, weiter, weiter.
Wenn mir langweilig Ich kann auch einfach n für die nächste.
Sie können es auf die kürzest mögliche Folge von Zeichen abkürzen.
Swap ist nun gebrochen.
Lasst uns eintauchen, so dass anstelle der Eingabe nächsten,
Jetzt werde ich Schritt geben, so dass ich in Intensivierung bin von dieser Funktion
so dass ich durch sie hindurchgehen, so schlug ich Schritt und geben Sie dann.
Beachten Sie, dass die Hervorhebung springt hinunter tiefer in mein Programm zu Zeile 36.
Nun, was sind die lokalen Variablen?
Info Einheimischen.
Nichts nur noch, weil wir nicht auf dieser Linie bekommen,
so lassen Sie uns gehen und sagen "Weiter".
Jetzt scheinen wir tmp, Print tmp haben.
Garbage-Wert, nicht wahr? Ich denke schon.
Wie wäre es drucken, print b, 1 und 2?
In einem Moment, sobald ich als nächstes schreiben wieder
tmp wird auf einem Wert von 1 treffen, hoffentlich
weil tmp wird zugeordnet den Wert eines werden.
>> Nun wollen wir noch einen, Druck b drucken,
aber jetzt gedruckt tmp, und es ist in der Tat ein.
Lassen Sie mich als nächstes tun. Lassen Sie mich als nächstes tun.
Ich habe die Swap-Funktion beendet.
Ich bin immer noch in der es in Zeile 40, also lasst mich auszudrucken a,
print b, und ich weiß nicht, was tmp ist.
Es sieht aus wie Swap ist richtig, wenn es um Swapping a und b kommt.
Aber wenn ich nun neben geben, springe ich zurück zu Zeile 25,
und natürlich, wenn ich Typ in x-und Print-y
sie sind immer noch unverändert, so haben wir nicht das Problem behoben.
Aber diagnostisch jetzt vielleicht mit diesem GDB-Programm
wir haben zumindest bekommen einen Schritt näher an das Verständnis
was ist los, ohne Einstreu unseren Code, indem sie eine printf hier falsch,
printf hier printf hier und dann läuft es wieder und wieder
versuchen herauszufinden, was falsch läuft.
>> Ich werde weitermachen und beenden aus diesem insgesamt mit beenden.
Es wird dann sagen: "Beenden Sie eigentlich?" Ja.
Jetzt bin ich wieder in meinem normalen Eingabeaufforderung, und ich bin fertig mit GDB.
Nebenbei, die Sie nicht brauchen, um diese-tui-Flag verwenden.
In der Tat, wenn Sie es weglassen man im wesentlichen die untere Hälfte des Bildschirms.
Wenn ich dann break main und führen Sie dann
Ich kann mich noch mein Programm, aber was sie tun ist textlich
nur zeigen mir die aktuelle Zeile ein zu einer Zeit.
Die-tui, textuelle Benutzeroberfläche
nur zeigt Ihnen mehr von dem Programm auf einmal, das ist wahrscheinlich ein wenig konzeptionell einfacher.
Aber in der Tat, kann ich nur als nächstes tun, next, next,
und ich werde auf eine Zeile zu einem Zeitpunkt, zu sehen, und wenn ich wirklich will, um zu sehen, was los ist
Ich kann geben Liste und sehen eine ganze Reihe von benachbarten Linien.
>> Es gibt ein Video, dass wir darum gebeten, dass Sie Probleme setzt 3 zu sehen
in denen Nate deckt einige der Feinheiten der GDB,
und dies ist eines jener Dinge, ehrlich, wo einige nicht-triviale Prozentsatz Ihrer
wird niemals berühren GDB, und das wird eine schlechte Sache sein
weil buchstäblich Sie am Ende verbringen mehr Zeit im Laufe dieses Semesters
Jagd nach Bugs dann würden Sie, wenn Sie setzen in dieser halben Stunde / Stunde
diese und nächste Woche Lernen, sich bequem mit GDB.
Printf war Ihr Freund.
GDB sollte jetzt dein Freund sein.
>> Haben Sie Fragen zum GDB?
Und hier ist eine kurze Liste von einigen der mächtigsten und nützlichsten Befehlen.
Yeah. >> Können Sie einen String?
Können Sie eine Zeichenfolge? Absolut.
Es muss nicht nur ganzzahlig sein.
Wenn eine Variable s ist ein String geben Sie einfach in print s.
Es zeigt Ihnen, was das String-Variable ist.
[Unverständlich-Student]
Es wird Ihnen die Adresse und den String selbst.
Es zeigt Ihnen beides.
Und eine letzte Sache, nur weil diese gut zu kennen.
Backtrace und Rahmen, lassen Sie mich in diese ein letztes Mal tauchen,
genau dasselbe Programm mit GDB.
Lassen Sie mich gehen Sie vor und führen Sie die textuelle Benutzeroberfläche Version
break main.
Lassen Sie mich gehen Sie vor und führen Sie erneut. Hier bin ich.
Jetzt lass mich gehen nächste, nächste, nächste, nächste, nächste, Schritt geben.
>> Und jetzt nehme ich bin jetzt in swap bewusst, aber ich bin wie "Verdammt, was war der Wert von x?"
Ich kann das nicht x mehr.
Ich kann das nicht y, weil sie nicht im Lieferumfang sind.
Sie sind nicht in Zusammenhang, aber kein Problem.
Ich kann geben backtrace.
Das zeigt mir alle Funktionen, die bis zu diesem Zeitpunkt ausgeführt wurden.
Beachten Sie, dass ein auf dem Boden, Haupt-, Linien mit Haupt
ist auf der Unterseite der unser Bild hier.
Die Tatsache, dass Swap darüber Linien ist mit Swap oberhalb im Speicher hier
und wenn ich wieder an die wichtigsten vorübergehend wollen, kann ich sagen, "frame".
Welche Nummer? Main frame # 1.
Ich werde weitermachen und sagen: "Frame 1".
>> Jetzt bin ich wieder in main, und ich kann x zu drucken, und ich kann y drucken,
aber ich kann nicht drucken oder b.
Aber ich kann, wenn ich sage: "Okay, warten Sie eine Minute. Wo war das swap?"
Lassen Sie mich gehen Sie vor und sagen, "frame 0".
Jetzt bin ich wieder da, wo ich sein möchte, und so nebenbei,
gibt es weitere Befehle zu, wie wenn Sie wirklich immer langweilig Typisierung nächsten, Weiter, Weiter, weiter,
Sie können in der Regel sagen Dinge wie "nächsten 10," und das wird durch die nächsten 10 Zeilen fort.
Sie können auch auf "Weiter", wenn Sie wirklich mit Schrittmotoren durch sie gefüttert.
Weiter wird Ihr Programm ohne Unterbrechung laufen, bis es einen weiteren Haltepunkt trifft,
ob in einer Schleife oder weiter unten in Ihrem Programm.
>> In diesem Fall werden wir weiter bis zum Ende, und das Programm beendet normal.
Dies ist eine andere Art, inferior Prozess.
Nur Ihr Programm beendet normal.
Mehr dazu im Video und in Debugging-Sitzungen zu kommen.
Das war eine Menge.
Nehmen wir unsere 5-minütige Pause hier, und wir werden mit Strukturen und Dateien zurückzukehren.
>> Wenn Sie in dieser Woche pset tauchten bereits
Sie wissen, dass wir bei der Verteilung Code zu verwenden,
der Quellcode, die wir Ihnen bieten als Ausgangspunkt, einige neue Techniken.
Insbesondere haben wir dieses neue Schlüsselwort heißt struct, für Struktur,
so dass wir können benutzerdefinierte Variablen Sorten.
Wir haben auch den Begriff des Datei-I / O, Datei-und Ausgang,
und das ist so, dass wir den Staat zu retten
Ihrer Scramble Bord in einer Datei auf einer Disc
so dass die Lehre Stipendiaten und ich kann verstehen,
was innerhalb des Programms gehen, ohne manuell zu spielen
Dutzende von Spielen Scramble.
Wir können dies mehr automatisiert zu tun.
>> Diese Idee einer Struktur löst eine ziemlich überzeugende Problem.
Angenommen, wir wollen einige Programm umsetzen wollen
das irgendwie verfolgt von Informationen über Studenten,
und Studenten haben könnte, zum Beispiel, eine ID, einen Namen
und ein Haus an einem Ort wie Harvard, so sind diese 3 Stücke von Informationen
Wir wollen, um zu halten, so lassen Sie mich gehen Sie vor und mit dem Schreiben beginnen ein kleines Programm hier
gehören stdio.h.
Lass es mich tun zählen cs50.h.
Und dann beginne meine Hauptfunktion.
Ich werde nicht mit Befehlszeilenargumenten stören,
und hier möchte ich einen Schüler haben, so werde ich zu sagen
ein Student hat einen Namen, so werde ich sagen: "string name."
Dann werde ich sagen, ein Student hat auch eine ID, so int id,
und ein Student hat ein Haus, so bin ich auch sagen würde "string Haus."
Dann werde ich diese ein wenig mehr sauber bestellen wie diese.
Okay, jetzt habe ich 3 Variablen, mit denen ein Student vertreten, so "ein Student."
>> Und jetzt habe ich diese Werte auffüllen möchten, so lassen Sie es mich voran gehen und etwas sagen wie
"Id = 123".
Name wird David bekommen.
Lassen Sie uns sagen Haus wird Mather bekommen,
und dann werde ich etwas willkürlich wie printf zu tun ("% s,
dessen ID% d, lebt in% s.
Und jetzt, was ich will hier anschließen, einer nach dem anderen?
Name, ID, Haus; return 0.
Okay, wenn ich vermasselt irgendwo hier
Ich denke, wir haben eine ziemlich gute Programm, das ein Student speichert.
Natürlich ist dies nicht so interessant. Was, wenn ich 2 Studenten haben wollen?
Das ist keine große Sache. Ich kann unterstützt 2 Personen.
Lassen Sie mich gehen Sie vor und markieren Sie diese und gehen Sie hier
und ich kann sagen "id = 456" für jemanden wie Rob, der in Kirkland lebt.
>> Okay, warten, aber ich kann nicht nennen diese die gleiche Sache,
und es sieht aus wie ich zu haben, um diese zu kopieren bin,
so lassen Sie mich sagen, dass dies wird Davids Variablen,
und lassen Sie mich einige Kopien davon für Rob.
Wir rufen diese Robs aber dies ist nicht zur Arbeit gehen jetzt
weil ich-warten haben, ändern wir mir id1, name1 und house1.
Rob wird 2, 2.
Ich habe dies hier, hier, hier, hier, hier, hier ändern.
Warten Sie, was Tommy? Lasst uns wieder tun.
Natürlich, wenn Sie immer noch denke, dies ist ein guter Weg, dies zu tun, ist es nicht,
so kopieren / einfügen schlecht.
Aber wir lösen diese vor einer Woche.
>> Was war unsere Lösung, wenn wir mehrere Instanzen des gleichen Datentyp haben wollte?
[Studenten] Ein Array.
Ein Array, so lassen Sie mich versuchen, diese bereinigen.
Lassen Sie mich einige Zimmer für mich an der Spitze, und lass mich tun, anstatt dies hier.
Wir rufen diese Menschen, und stattdessen werde ich sagen, "int ids"
und ich werde bis 3 von uns jetzt zu unterstützen.
Ich werde sagen, "string Namen," und ich werde 3 von uns unterstützt,
und dann werde ich sagen: "string Häuser," und ich werde bis 3 von uns zu unterstützen.
Jetzt hier anstelle von David immer seine eigenen lokalen Variablen
können wir diejenigen loswerden.
Das fühlt sich gut, dass wir die Reinigung ausgedacht.
Ich kann dann sagen, David wird [0] und Namen [0] sein
und Häuser [0].
Und dann Rob können wir ebenfalls auf diese zu speichern.
Lassen Sie uns dies hier unten gesetzt, so er wird willkürlich ids [1] sein.
Er will Namen sein [1],
und dann schließlich, Häuser [1].
>> Noch ein wenig langweilig, und jetzt habe ich, um dies herauszufinden,
so sagen wir "names [0] id [0], Häuser [0]
und lasst pluralize dies.
Ids, IDs IDs.
Und wieder, ich mache es, so wieder, ich bin schon Rückgriff auf copy / paste wieder
so Chancen gibt es eine andere Lösung.
Ich kann wahrscheinlich reinigen diese bis weiter mit einer Schleife oder so etwas,
Also kurz gesagt, ist es ein wenig besser, aber immer noch das Gefühl
Ich Rückgriff auf copy / paste, aber selbst das, behaupte ich,
ist nicht wirklich grundlegend die richtige Lösung, weil
was ist, wenn irgendwann entscheiden wir wissen Sie was?
Wir sollten wirklich worden Speichern E-Mail-Adressen für David und Rob
und alle anderen in diesem Programm.
Wir sollten auch speichern Telefonnummern.
Wir sollten auch speichern Notrufnummern.
Wir haben alle diese Stücke von Daten, die wir speichern wollen,
so wie Sie zu tun, dass?
>> Sie erklären anderes Array an der Spitze, und dann manuell hinzufügen
eine E-Mail-Adresse [0], E-Mail-Adresse [1]
David und Rob und so weiter.
Aber es ist wirklich nur eine Vermutung zugrunde liegende Design
dass ich mit dem Ehren-System zu wissen, dass
[I] in jedem der mehreren Arrays
passiert einfach so auf die gleiche Person beziehen,
so [0] in ids ist die Nummer 123,
und ich werde, dass die Namen anzunehmen [0]
ist die gleiche Person den Namen und Häuser [0]
ist die gleiche Person das Haus und so weiter für all die verschiedenen Arrays, dass ich schaffen.
Aber beachten Sie, dass es keinen fundamentalen Verknüpfung
unter diesen 3 Stück von Informationen, id, name und Haus,
obwohl das Unternehmen wir zu modellieren versucht sind in diesem Programm ist nicht Arrays.
Arrays sind nur diese programmatischen Weg, dies zu tun.
Was wir wirklich wollen, in unserem Programm zu modellieren ist eine Person,
wie David, ein Mensch wie Rob innerhalb derer
oder Verkapselung ist ein Name und ID und ein Haus.
>> Können wir irgendwie ausdrücken diese Idee der Kapselung
bei dem eine Person eine ID, einen Namen und ein Haus
und nicht wirklich diesen Hack zurückgreifen, wobei wir nur
vertrauen, dass Halterung etwas
bezieht sich auf die gleiche Entität menschlichen in jedem dieser unterschiedlichen Arrays?
Wir können tatsächlich tun.
Lassen Sie mich oben gehen jetzt Haupt-, und lassen Sie mich meine eigenen Datentyp
für wirklich die erste Zeit.
Wir verwendeten diese Technik in Scramble,
aber hier werde ich weitermachen und erstellen einen Datentyp,
und wissen Sie was, ich werde nennen es Studenten oder Personen,
und ich werde zu verwenden typedef definieren für einen Typ.
Ich werde sagen, dass dies eine Struktur,
und dann diese Struktur wird vom Typ Student sein, sagen wir,
obwohl es jetzt ein wenig für mich datiert.
Wir sagen "int id."
Wir sagen "string name."
Dann werden wir sagen, "string Haus"
so jetzt bis Ende diesen wenigen Zeilen Code
Ich habe gerade clang gelehrt, dass es existiert,
ein Datentyp neben ints neben Saiten neben verdoppelt neben schwimmt.
>> Ab diesem Zeitpunkt Linie 11 gibt es nun eine neue Datentyp namens Studenten,
und jetzt kann ich ein Student variable überall Ich möchte erklären,
so lassen Sie mich nach unten scrollen Sie hier, um die Menschen.
Jetzt kann ich loswerden, und ich kann wieder auf David hier
und David Ich kann wirklich sagen, dass David,
Wir können buchstäblich einen Namen für die Variable nach mir,
wird vom Typ Student sein.
Dies aussehen könnte ein wenig seltsam, aber das ist gar nicht so verschieden
von der Deklaration etwas als int oder einer Schnur oder einem Schwimmer.
Es passiert einfach so genannt Studenten nun,
und wenn ich will etwas in dieser Struktur setzen
Ich habe jetzt ein neues Stück Syntax verwenden, aber es ist ziemlich einfach,
david.id = 123, david.name = "David" in der Hauptstadt D,
und david.house = "Mather,"
und jetzt kann ich loswerden von diesem Zeug hier.
Haben wir nun feststellen, unser Programm in wirklich einen viel besseren Weg umgestaltet
, dass nun unser Programm spiegelt die reale Welt.
>> Es gibt eine reale Vorstellung von einer Person oder eines Schülers.
Hier haben wir nun eine C-Version von einer Person oder genauer gesagt eines Schülers.
Innerhalb von dieser Person sind diese relevanten Eigenschaften,
ID, Name und Haus, so Rob Wesentlichen wird die gleiche Sache hier unten,
so Studentin rob, und jetzt rob.id = 456,
rob.name = "Rob."
Die Tatsache, dass die Variable heißt Rob ist eine Art bedeutungslos.
Wir konnten nannte x bzw. y bzw. z sind.
Wir nannten es Rob als semantisch konsistent,
aber wirklich der Name ist innerhalb dieses Feldes selbst,
so jetzt habe ich dies.
Auch nicht wie das beste Design, dass ich hart David habe kodiert fühlen.
Ich habe hart Rob codiert.
Und ich habe noch bis zu einem gewissen Kopie zurückgreifen und fügen Sie jedes Mal möchte ich neue Variablen.
Außerdem habe ich scheinbar zu geben jede dieser Variablen einen Namen,
obwohl ich würde viel lieber beschreiben diese Variablen
mehr allgemein als Studenten.
>> Jetzt können wir verschmelzen die Ideen, die gearbeitet haben, gut für uns
und stattdessen sagen: "Weißt du was, gib mir eine Variable namens Studenten,
und lasst uns haben es der Größe 3 sein, "so kann ich jetzt zu verfeinern dies weiter,
loszuwerden, die manuell erklärt David,
und ich kann stattdessen etwas sagen wie Studenten [0] hier.
Ich kann dann sagen Studenten [0] hier
Studenten [0] hier, und so weiter, und ich kann gehen um
und reinigen, dass für Rob.
Ich könnte auch über jetzt vielleicht indem eine Schleife gehen
und mit GetString und GetInt um tatsächlich diese Werte durch den Benutzer.
Ich konnte über das Hinzufügen eines konstanten gehen, weil dies in der Regel schlechte Praxis
hart zu codieren einige willkürliche Zahl wie 3 hier
und dann nur daran erinnern, dass Sie sollten nicht mehr als 3 Studenten in sie setzen.
Es wäre wahrscheinlich besser, # verwende am Anfang meiner Datei definieren
und Faktor, dass sich, so der Tat, lassen Sie mich gehen Sie vor und verallgemeinern diese.
>> Lassen Sie mich eröffnen ein Beispiel, das unter den heutigen ist
Beispiele: Vorkasse, structs1.
Dies ist ein komplettes Programm, das # define hier verwendet
und sagt, wir gehen zu 3 Studenten standardmäßig haben.
Hier bin ich die Deklaration einer Klasse im Wert von Studenten,
so ein Klassenzimmer der Schüler, und jetzt bin ich mit einer Schleife
nur um den Code ein wenig eleganter, bevölkern die Klasse
Mit der Eingabe des Benutzers, so von i = 0 auf iterieren bis zu Studenten, die 3 ist.
Und dann habe ich den Benutzer auffordern, in dieser Version
was ist der Schüler-ID, und ich bekomme es mit GetInt.
Was ist der Name des Studenten, und dann bekomme ich es mit GetString.
Was ist des Schülers Haus? Ich bekomme es mit GetString.
Und dann am Ende hier habe ich gerade beschlossen zu ändern
wie ich Drucken Sie diese aus und tatsächlich eine Schleife verwenden,
Und wer bin ich Bedrucken?
Nach dem Kommentar, den ich bin Drucken jemand in Mather,
und dass es so Rob und Tommy und so weiter, eigentlich Tommys in Mather.
Tommy und David würde in diesem Fall gedruckt werden, aber wie wird das funktioniert?
Wir haben diese Funktion nicht gesehen, aber zu erraten, was diese tut.
Vergleicht Strings.
>> Es ist ein wenig nicht klar, wie es Zeichenketten verglichen, weil sich herausstellt,
wenn es 0 zurückgibt dh die Saiten sind gleich.
Wenn es eine gibt -1 dh kommt Reihenfolge vor dem anderen,
und wenn es ein gibt das heißt das andere Wort kommt alphabetisch
vor dem anderen, und Sie können sich online oder auf der Manpage
um genau zu sehen, welchen Weg ist, die aber all dies ist nun zu tun ist es sagt
wenn die [i]. Haus ist gleich "Mather"
dann gehen Sie vor und drucken Sie so und so ist in Mather.
Aber hier ist etwas, was wir nicht gesehen haben, bevor, und wir kommen darauf zurück.
Ich erinnere mich nicht, jemals dazu in keinem meiner Programme.
Free ist offenbar auf Speicher freigegeben werden kann,
aber was Speicher bin ich anscheinend zu befreien in dieser Schleife am unteren Rand dieses Programms?
Es sieht aus wie ich befreit den Namen einer Person bin
und eine Person das Haus, aber warum ist das so?
>> Es stellt sich heraus all diesen Wochen, dass Sie schon mit GetString
Wir haben Art wurde die Einführung eines Fehlers in jedem Ihrer Programme.
GetString by design Speicher zuweist, so dass es für Sie eine Zeichenfolge zurückgeben kann,
wie David oder Rob, und Sie können dann tun, was Sie wollen
mit diesem String in Ihrem Programm, weil wir den Speicher für Sie reserviert.
Das Problem ist, die ganze Zeit jedes Mal, rufen Sie GetString
wir, die Autoren der GetString, gefragt haben das Betriebssystem
um uns ein wenig RAM für diesen String.
Geben Sie uns ein bisschen RAM für die nächste Saite.
Gib uns etwas mehr RAM für die nächste Saite.
Was Sie als Programmierer, noch nie getan
gibt uns das Gedächtnis zurück,
so für diese mehrere Wochen alle Programme, die Sie geschrieben haben,
gehabt haben, was eine Speicherkarte Sprung bezeichnet, wodurch sie mit zu halten
mehr und mehr Speicher jedes Mal rufen Sie GetString, und das ist in Ordnung.
Wir haben uns bewusst machen, dass in den ersten Wochen, weil es nicht so interessant
zu müssen, wo die Saite herkommt kümmern.
Alles, was Sie wollen, ist das Wort Rob wieder zu kommen, wenn der Benutzer es in.
>> Aber voran müssen wir jetzt beginnen immer ausgefeilter darüber.
Jedes Mal, wenn wir Speicherzuweisung wir besser schließlich geben es zurück.
Ansonsten in der realen Welt auf Ihrem Mac oder PC haben Sie vielleicht gelegentlich erfahrenen
Symptome, wo Ihr Computer zu einem Stillstand Schleifen wird schließlich
oder die dumme Spinnerei Beachball gerade Besetzung des Computers
ganze Aufmerksamkeit und Sie können nicht Dinge tun.
Dies kann durch eine beliebige Anzahl von Bugs erklärt werden, aber unter diesen möglichen Fehler
werden Dinge genannt Speicherlecks wodurch jemand dieses Stück Software geschrieben
Sie verwenden nicht um Speicher frei zu erinnern
dass er oder sie gebeten das Betriebssystem für,
nicht mit GetString, denn das ist ein CS50 Sache, aber mit ähnlichen Funktionen
, die das Betriebssystem für den Speicher zu stellen.
Wenn Sie oder sie vermasseln und eigentlich nie zurück, dass der Speicher
ein Symptom, das sein, dass ein Programm und verlangsamt verlangsamt und verlangsamt können
wenn Sie daran denken, rufen Sie kostenlos.
>> Wir kommen wieder, wann und warum Sie kostenlos anrufen,
aber lassen Sie uns gehen, nur für eine gute Maßnahme und versuchen Sie, dieses besondere Programm.
Dies hieß structs1 geben.
Lassen Sie mich gehen Sie vor und führen Sie structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, und wir sehen Davids in Mather, Tommys in Mather.
Dies ist nur eine kleine Plausibilitätsprüfung, dass das Programm funktioniert.
Nun, leider ist dieses Programm ein wenig frustrierend, dass
Ich habe all die Arbeit, die ich in 9 verschiedenen Zeichenketten eingegeben, drücken Sie Enter,
wurde gesagt, wer war in Mather, aber natürlich wusste ich, wer war in Mather schon, weil ich es eingetippt haben.
Es wäre zumindest schön, wenn dieses Programm ist mehr wie eine Datenbank
und es tatsächlich merkt, was ich eingetippt
so dass ich nie wieder die Eingabe diese Studenten Aufzeichnungen.
Vielleicht ist es wie ein registrarial System.
>> Wir können dies tun, indem diese Technik als Datei-I / O, Datei-und Ausgang bekannt ist,
eine sehr allgemeine Weise des Sagens wann immer Sie wollen, um Dateien zu lesen oder Schreiben von Dateien
Sie können dies mit einem bestimmten Satz von Funktionen zu tun.
Lassen Sie mich gehen Sie vor und öffnen Sie dieses Beispiel structs2.c,
das ist fast identisch, aber mal sehen, was es jetzt tut.
Am Anfang der Datei erkläre ich eine Klasse von Studenten.
Ich habe dann bevölkern die Klasse mit der Eingabe des Benutzers,
so dass diese Code-Zeilen sind genau wie früher.
Dann, wenn ich hier unten scrollen drucke ich alle, die in Mather ist beliebig wie vorher,
aber das ist eine interessante neue Funktion.
Diese Codezeilen sind neu, und führen sie hier etwas,
FILE, alle Kappen, und es hat * in auch hier.
Lassen Sie mich zu bewegen diese hier, eine * über hier.
>> Diese Funktion haben wir nicht gesehen, fopen,
aber es Datei bedeutet, offen, also lasst überfliegen diesen
und dies ist etwas, das wir wieder kommen werden, um in Zukunft pset
aber diese Linie hier im Wesentlichen öffnet eine Datei namens Datenbank
und es öffnet sie spezifisch in der Weise, dass er, was zu tun?
[Unverständlich-Student]
Richtig, so "w" bedeutet nur, es zu sagen das Betriebssystem
Öffnen Sie diese Datei in einer Weise, dass ich es zu schreiben.
Ich will nicht, es zu lesen. Ich will nicht nur auf ihn achten.
Ich möchte es ändern und Dinge möglicherweise dazu,
und die Datei wird als Datenbank.
Das kann alles abgerufen werden.
Dies könnte database.txt. Dies könnte. Db sein.
Dies könnte ein Wort wie foo sein, aber ich willkürlich gewählt, um die Datei-Datenbank zu nennen.
Dies ist ein wenig Plausibilitätsprüfung, dass wir kommen zurück, um im Detail über die Zeit,
wenn fp für Dateizeiger, nicht gleich NULL dh alles ist gut.
>> Lange Rede kurzer Sinn, Funktionen wie fopen manchmal fehl.
Möglicherweise ist die Datei nicht existiert. Vielleicht sind Sie von Speicherplatz.
Vielleicht haben Sie nicht die Berechtigung in diesem Ordner,
also wenn fopen gibt null etwas Schlimmes passiert.
Umgekehrt, wenn fopen nicht zurück null ist alles gut
und ich kann mit dem Schreiben beginnen diese Datei.
Hier ist ein neuer Trick.
Dies ist eine for-Schleife, Iteration über ist jeder meiner Studenten,
und das sieht so ähnlich, was wir bisher gemacht habe,
aber diese Funktion ist ein Cousin von printf fprintf für Datei printf aufgerufen,
und bemerken es anders in nur 2 Möglichkeiten.
Einer, es beginnt mit f statt p,
aber dann das erste Argument ist offenbar was?
[Studenten] File. >> Es ist eine Datei.
Dieses Ding namens fp, die wir schließlich zu necken werde auseinander, was einen Dateizeiger ist,
aber jetzt fp stellt einfach die Datei, die ich geöffnet haben,
so fprintf hier sagen Drucken Sie diese Benutzer-ID in der Datei, nicht auf dem Bildschirm.
Drucken den Namen des Benutzers in der Datei, nicht auf dem Bildschirm,
Das Haus an der Datei nicht auf dem Bildschirm, und dann hier unten, offensichtlich,
schließen Sie die Datei, und dann hinunter hier kostenlos das Gedächtnis.
>> Der einzige Unterschied zwischen dieser Version 2 und 1
ist die Einführung von fopen und diese Datei mit *
und diese Vorstellung von fprintf, also lasst uns sehen, was das Ergebnis ist.
Lassen Sie mich in mein Terminal-Fenster zu gehen.
Lassen Sie mich laufen structs2 geben.
Sieht aus wie alles ist gut. Lassen Sie uns erneut structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, geben.
Sieht aus wie es die gleiche verhalten, aber wenn ich jetzt tun ls
feststellen, welche Datei ist hier unter all meinen Code, Datenbank,
so öffnen wir, dass gedit der Datenbank, und schauen Sie sich, dass.
Es ist nicht die sexiest von Dateiformaten.
Es ist wirklich ein Stück von Daten Zeile für Zeile pro Zeile,
aber diejenigen von euch, die Excel-oder CSV-Dateien verwenden, Komma Werten getrennt,
Ich könnte sicherlich fprintf verwendet haben, statt vielleicht etwas tun
so dass ich tatsächlich schaffen das Äquivalent einer Excel-Datei
durch die Trennung Dinge mit Kommas, nicht nur neue Linien.
>> In diesem Fall hätte ich statt Kommas anstelle von neuen Linien verwendet
Ich konnte buchstäblich öffnen Sie diese Datenbank-Datei in Excel, wenn ich machte, anstatt es so aussehen.
Kurz gesagt, jetzt, dass wir die Macht haben, Dateien zu schreiben
Wir können jetzt damit beginnen anhaltenden Daten, hält es rund auf der Disc
so dass wir Informationen rund um wieder und wieder zu halten.
Beachten Sie ein paar andere Dinge, die jetzt ein bisschen mehr vertraut.
An der Spitze dieser C-Datei haben wir einen typedef
denn wir wollten einen Datentyp, der ein Wort darstellt, erstellt wird,
so dass diese Art genannt wird Wort, und innerhalb dieser Struktur
es ist ein wenig schicker jetzt.
Warum ist ein Wort aus scheinbar ein Array gemacht?
Was ist ein Wort nur intuitiv?
>> Es ist ein Array von Zeichen.
Es ist eine Folge von Zeichen Rücken an Rücken an Rücken.
BRIEFE in allen Caps passiert zu sein wir willkürlich sagen, dass die maximale Länge
von jedem Wort im Wörterbuch, dass wir für Scramble verwenden.
Warum muss ich eine +1?
Das Null-Zeichen.
Erinnern, wenn wir die Bananagrams Beispiel haben wir einen besonderen Wert nötig
am Ende des Wortes, um zu verfolgen
wo Worte tatsächlich zu Ende, und wie das Problem Satz Spezifikation sagt
hier haben wir es mit einem gegebenen Wort assoziieren einen booleschen Wert,
eine Fahne, so zu sprechen, wahr oder falsch.
Haben Sie dieses Wort schon gefunden, weil wir erkennen,
wir wirklich brauchen, einen Weg des Erinnerns nicht nur, was ein Wort ist in Scramble
aber ob Sie, der Mensch, habe es gefunden
so dass, wenn Sie tun, das Wort "das" man kann nicht einfach geben Sie das Geben, das Geben, das Geben
und erhalten Sie 3 Punkte, 3 Punkte, 3 Punkte, 3 Punkte.
Wir wollen in der Lage sein, dieses Wort, indem Sie einen bool Blacklist
true, wenn Sie es bereits gefunden habe, und damit ist, warum wir
eingekapselt in dieser Struktur.
>> Nun, hier unten in Scramble gibt es diese anderen struct genannt Wörterbuch.
Abwesend ist hier das Wort typedef weil in diesem Fall
wir brauchten, um die Idee eines Wörterbuchs zu kapseln,
und ein Wörterbuch enthält eine ganze Reihe von Wörtern,
wie von diesem Array implizit, und wie viele von diesen Worten gibt es?
Nun, was diese Variable namens Größe sagt.
Aber wir brauchen nur ein Wörterbuch.
Wir brauchen nicht einen Datentyp namens Wörterbuch.
Wir brauchen nur eine von ihnen, so stellt sich heraus, in C
dass, wenn Sie nicht sagen typedef, die Sie gerade sagen, struct, dann innerhalb der geschweiften Klammern
Sie setzen Ihre Variablen, dann setzen Sie den Namen.
Dies wird erklärt ein Variable namens Wörterbuch
das sieht wie folgt aus.
Im Gegensatz dazu, werden diese Linien, die eine wiederverwendbare Datenstruktur namens Wort
Sie können mehrere Kopien, wie wir geschaffen
mehrere Kopien von Studenten.
>> Was bedeutet das es uns ermöglichen, zu tun?
Lassen Sie mich zurück in, sagen wir, ein einfacheres Beispiel aus einfacheren Zeiten,
und lassen Sie mich öffnen, sagen wir mal, compare1.c.
Das Problem hier bei der Hand ist, um tatsächlich abziehen
die Schicht aus einem String und starten Ausziehen diese Stützräder
weil es stellt sich heraus, dass ein String ganze Zeit
ist, wie wir in der Woche 1 wirklich versprochen, nur einen Spitznamen,
ein Synonym von der CS50-Bibliothek für etwas, das ein wenig mehr kryptisch aussieht,
char *, und wir haben diesen Stern gesehen.
Wir sahen sie in den Kontext von Dateien.
>> Lassen Sie uns nun sehen, warum wir versteckt habe dieses Detail für einige Zeit.
Hier ist eine Datei namens compare1.c,
und es scheint fragt den Benutzer nach 2 Strings, s und t,
und dann versucht, diese Zeichenfolgen für die Gleichstellung in Zeile 26 zu vergleichen,
und wenn sie gleich heißt es bist "Du dasselbe getippt"
und wenn sie es nicht sind gleich heißt es: "Sie gaben verschiedene Dinge."
Lassen Sie mich gehen Sie vor und führen Sie dieses Programm.
Lassen Sie mich in mein Quellverzeichnis, machen Sie eine compare1. Es zusammengestellt okay.
Lassen Sie mich laufen compare1.
Ich werde zu vergrößern, geben.
Etwas sagen. HALLO.
Ich werde wieder etwas sagen. HALLO.
Ich habe definitiv nicht geben verschiedene Dinge.
>> Lassen Sie mich noch einmal versuchen. BYE BYE.
Definitiv nicht anders, so was ist denn hier los?
Nun, das ist, was wirklich in Zeile 26 verglichen?
[Unverständlich-Student]
Ja, so stellt sich heraus, dass ein String, der Datentyp, eine Art Notlüge ist.
Ein String ist eine char *, aber was ist ein char *?
Ein char *, wie sie sagen, ist ein Zeiger,
und ein Zeiger ist effektiv eine Adresse,
eine Summe Stelle im Speicher, und wenn Sie zufällig in einem Wort wie HALLO eingegeben haben,
erinnern, aus der Vergangenheit Diskussionen über Strings
Das ist wie das Wort HALLO.
Beachten Sie, dass ein Wort wie HALLO dargestellt werden können,
als ein Array von Zeichen wie dies
und dann mit einem speziellen Zeichen am Ende genannt Nullzeichen
als \ bezeichnet.
Was ist eigentlich ein String?
Beachten Sie, dass diese mehrere Stücke der Erinnerung,
und in der Tat, ist das Ende der nur bekannt, wenn Sie durch den ganzen String suchen
Suche nach dem besonderen null Charakter.
Aber wenn dies ein Stück Erinnerung aus meinem Arbeitsspeicher des Computers,
lasst uns willkürlich sagen, dass diese Zeichenfolge einfach nur Glück,
und es wurde ganz am Anfang meines Computers RAM platziert.
Dies ist das Byte 0, 1, 2, 3, 4, 5, 6 ...
>> Wenn ich etwas sagen wie GetString und ich string s = GetString
was wirklich zurückgegeben?
Für diese letzten paar Wochen, was ist wirklich in s gespeichert
nicht diese Zeichenfolge per se, aber in diesem Fall, was gespeichert ist
die Zahl 0, denn was GetString tatsächlich
ist es nicht physisch einen String zurück.
Das bedeutet aber nicht, auch wirklich konzeptionellen Sinn.
Was sie tut, Rückkehr eine Zahl ist.
Diese Zahl ist die Adresse des HALLO im Speicher
und String s dann, wenn wir abziehen diese Schicht, wird String nicht wirklich existieren.
Es ist nur eine Vereinfachung der CS50-Bibliothek.
>> Das ist wirklich etwas namens char *.
Char macht Sinn, denn was ist ein Wort, wie HALLO?
Nun, es ist eine Reihe von Zeichen, eine Reihe von Zeichen.
Char * bedeutet die Adresse eines Zeichens,
so was bedeutet es, einen String zurückgeben?
Eine schöne, einfache Möglichkeit der Rücksendung einen String
ist, anstatt zu versuchen, herauszufinden, wie ich 5 oder 6 verschiedenen Bytes zurück
Lassen Sie mich an die Adresse von welchem ​​Byte zurück?
Die erste.
In anderen Worten, lassen Sie mich Ihnen die Adresse eines Zeichens im Speicher.
Das hat char * darstellt, die Adresse der ein einzelnes Zeichen in den Speicher.
Rufen Sie die Variable s.
Store in s, dass bestimmte Adresse, die ich willkürlich die 0 ist,
nur um die Dinge einfach halten, aber in Wirklichkeit ist es in der Regel eine größere Anzahl.
>> Warten Sie eine Minute.
Wenn Sie nur geben sind mir die Adresse des ersten Zeichens, wie kann ich wissen, was die Adresse
des zweiten Zeichens, das dritte, das vierte und das fünfte?
[Unverständlich-Student]
Sie müssen nur wissen, wo das Ende des Strings ist durch dieses handlichen Trick,
so, wenn Sie etwas verwenden, wie printf, was printf wörtlich nimmt als Argument,
erinnern, dass wir dieses% s Platzhalter verwenden, und dann passieren,
die Variable, die die Speicherung eines Strings ist.
Was Sie wirklich vorbei ist die Adresse des ersten Zeichens des Strings.
Printf verwendet dann eine for-Schleife oder eine while-Schleife mit dem Erhalt der Adresse,
zum Beispiel 0, so lassen Sie mich dies jetzt zu tun,
printf ("% s \ n", s);
Wenn ich rufe printf ("% s \ n", s); was ich wirklich Bereitstellung printf mit
ist die Adresse des ersten Zeichens in s, der in diesem Fall beliebig ist H.
>> Wie funktioniert printf wissen, was genau auf dem Bildschirm angezeigt werden?
Die Person, die umgesetzt printf eine while-Schleife oder eine for-Schleife implementiert
das sagt dieser Charakter entsprechen nicht den besonderen null Charakter?
Wenn nicht, ausdrucken. Wie wäre es mit diesem?
Wenn nicht drucken, drucken, drucken, drucken.
Oh, das ist ein besonderes. Brechen Sie den Druckvorgang und kehren an den Benutzer.
Und das ist buchstäblich alles, was unter der Haube wurde passiert,
und das ist eine Menge in den ersten Tag einer Klasse zu verdauen,
aber jetzt ist es wirklich der Baustein alles verstehen
Das ist auf der Innenseite der Arbeitsspeicher des Computers gegangen,
und schließlich werden wir necken diese außer mit ein wenig Hilfe
von einem unserer Freunde in Stanford.
>> Professor Nick Parlante an der Stanford hat diese wunderbare Videosequenz getan
aus allen möglichen verschiedenen Sprachen, die eingeführt
diese kleine Claymation Charakter Binky.
Die Stimme, die Sie sind im Begriff, in nur wenigen Sekunden Sneak Preview zu hören
ist, dass der Stanford-Professor, und Sie bekommen
nur 5 oder 6 Sekunden dieser gerade jetzt,
aber dies ist die Notiz auf dem schließen wir heute werde
und am Mittwoch beginnen.
Ich gebe Ihnen Pointer Spaß mit Binky, die Vorschau.
[♪ Music ♪] [Professor Parlante] Hey, Binky.
Aufwachen. Es ist Zeit für Zeiger Spaß.
[Binky] Was ist das? Erfahren Sie mehr über Zeiger?
Oh, goody!
>> Wir werden Sie am Mittwoch sehen.
[CS50.TV]