[Powered by Google Translate] [Walkthrough - Problem Set 6]
[Zamyla Chan - Harvard University]
[Dies ist CS50. - CS50.TV]
>> Hallo, alle, und Walkthrough 6 begrüßen zu dürfen: Huff'n Puff.
In Huff'n Puff, was wir tun wird, um mit einem Huffman komprimierten Datei zu tun
und dann schnaufend wieder hoch, so Dekomprimierung
so dass wir von der 0 und 1, die der Benutzer schickt uns übersetzen
und wandeln es wieder in den ursprünglichen Text.
Pset 6 sein wird ziemlich cool, weil Sie einige der Werkzeuge zu sehen sind
Sie verwendet in pset 4 und pset 5 und Art der Kombination in 1 recht ordentlich Konzept
wenn Sie darüber nachdenken kommen.
>> Auch wohl, waren pset 4 und 5 die schwierigsten pset, dass wir zu bieten hatte.
Also ab jetzt haben wir diese 1 mehr pset in C,
und dann nach, dass wir auf Web-Programmierung.
So gratuliere euch für immer über den härtesten Buckel CS50.
>> Moving on für Huff'n Puff, sind unsere Toolbox für dieses pset werde Huffman Bäume,
so zu verstehen, nicht nur, wie binäre Bäume Arbeit, aber auch speziell Huffman-Bäume,
wie sie konstruiert.
Und dann werden wir eine Menge Code der Verteilung der in diesem pset haben,
und wir kommen zu dem tatsächlich sehen einige der Code
wir vielleicht nicht in der Lage sein voll noch zu verstehen,
und so die werden die. c-Dateien, aber dann die dazugehörigen. h-Dateien
geben uns genügend Verständnis, dass wir brauchen, damit wir wissen, wie diese Funktionen arbeiten
oder zumindest das, was sie tun sollen - ihre Ein-und Ausgänge -
auch wenn wir nicht wissen, was in der Black Box passiert
oder nicht verstehen, was in der Black Box geschieht innerhalb.
Und dann endlich, wie üblich, werden wir mit neuen Datenstrukturen zu tun haben,
bestimmte Arten von Knoten, die auf bestimmte Dinge,
und so hier einen Stift und Papier nicht nur für den Design-Prozess
und wenn Sie versuchen, herauszufinden, wie Sie Ihre pset funktionieren sollte
sondern auch beim Debuggen.
Sie können GDB neben Ihren Stift und Papier, während Sie nehmen auf, was die Werte sind,
wo Ihre Pfeile zeigen, und solche Dinge.
>> Lassen Sie uns zunächst bei Huffman Bäume sehen.
Huffman-Bäume sind binäre Bäume, was bedeutet, dass jeder Knoten hat nur 2 Kinder.
In Huffman-Bäume das Merkmal, dass die häufigsten Werte
werden durch die wenigsten Bits repräsentiert.
Wir sahen in der Vorlesung Beispiele für Morse-Code, welche Art von konsolidierten einige Briefe.
Wenn Sie versuchen, ein A oder ein E, zum Beispiel zu übersetzen,
Sie so oft übersetzt, so anstatt den vollen Satz von Bits zu verwenden
zugeordnet zu diesem üblichen Datentyp, komprimieren Sie es auf weniger,
und dann diese Briefe, die vertreten werden weniger häufig mit längeren Bit dargestellt
weil Sie sich leisten können, dass, wenn Sie sich die Frequenzen, dass diese Buchstaben erscheinen wiegen.
Wir haben die gleiche Idee hier in Huffman-Bäume
wo wir einen Kette, eine Art von Pfad zu den bestimmte Zeichen zu erhalten.
Und dann die Zeichen, die am meisten Frequenz haben
gehen, um mit den wenigsten Bits dargestellt werden.
>> Die Art und Weise, dass Sie einen Huffman-Baum zu konstruieren
ist, indem alle Zeichen, die im Text erscheinen
und Berechnung ihrer Häufigkeit, wie oft sie erscheinen.
Dies könnte entweder eine Anzahl, wie oft diese Buchstaben erscheinen werden
oder vielleicht ein Prozentsatz von allen Charakteren, wie viele jeder erscheint.
Und so, was Sie tun müssen, ist, wenn Sie alle dieser vorgezeichnet haben,
dann schauen Sie für die 2 niedrigsten Frequenzen und dann kommen sie als Geschwister
wo dann der übergeordnete Knoten eine Frequenz aufweist, die Summe ihrer zwei Kinder ist.
Und dann per Konvention sagen, dass die linken Knoten,
Sie folgen, dass, indem Sie die 0 Zweig,
und dann der rechte Knoten ist der 1 Zweig.
Wie wir in Morse-Code sah, war das ein gotcha, dass, wenn Sie hatte nur einen Signalton und den Signalton
es war zweideutig.
Es könnte entweder ein Buchstabe oder es könnte eine Folge von 2 Buchstaben sein.
Und so was Huffman-Bäume tut, ist, weil von der Natur der Zeichen
oder unsere letzte tatsächlichen Zeichen wobei die letzten Teilnehmer auf dem Ast -
verweisen wir auf die wie Blätter - durch, dass kann es keine Zweideutigkeit
in Bezug auf die Buchstaben, den Sie versuchen, mit der Folge von Bits codieren sind
denn nirgendwo entlang der Bits, 1 Buchstabe stellen
begegnen Sie noch eine ganze Brief, und es wird keine Verwirrung da sein.
Aber wir werden in Beispielen gehen, dass Sie Jungs können tatsächlich sehen, dass
anstatt uns nur zu sagen, dass das stimmt.
>> Lassen Sie uns ein einfaches Beispiel eines Huffman Baum.
Ich habe eine Zeichenfolge hier, die 12 Zeichen lang ist.
Ich habe 4 As, 6 B, und 2 Cs.
Mein erster Schritt wäre zu zählen.
Wie oft muss ein erscheinen? Es erscheint 4 mal im String.
B erscheint 6-mal, und C erscheint 2 mal.
Natürlich, ich werde sagen, ich bin mit B am häufigsten
so möchte ich B mit der geringsten Anzahl von Bits, die geringste Anzahl von 0 und 1 darstellen.
Und dann habe ich werde auch zu erwarten, C, um die größte Menge von 0 und 1 als auch benötigen.
Erste, was ich hier getan wird Ich legte sie in aufsteigender Reihenfolge in Bezug auf die Frequenz.
Wir sehen, dass die C-und die A-, die unsere 2 tiefsten Frequenzen sind.
Wir schaffen einen übergeordneten Knoten, und dass übergeordnete Knoten nicht einen Brief zugeordnet,
aber es hat eine Frequenz, die die Summe ist.
Die Summe wird 2 + 4, nämlich 6.
Dann folgen wir den linken Ast.
Wenn wir in diesem 6 Knoten waren, dann würden wir folgen 0 auf C erhalten
und dann 1, um A. zu bekommen
Deshalb haben wir jetzt 2 Knoten.
Wir haben den Wert 6 und dann haben wir auch einen weiteren Knoten mit dem Wert 6.
Und so die 2 sind nicht nur die zwei niedrigsten aber auch nur die 2, die noch übrig,
Darum preisen wir dich, die von einem anderen Elternteil, mit wobei die Summe 12.
Also hier haben wir unsere Huffman-Baum
wo nach B zu kommen, das wäre nur das Bit 1 sein
und dann zur A bekommen müssten wir 01 und dann C mit 00.
Hier sehen wir also, dass wir im Grunde genommen sind vertreten diese Zeichen mit entweder 1 oder 2 Bits
wobei die B-, wie vorhergesagt, hat die geringste.
Und dann hatten wir erwartet, C, die meisten haben, aber da es so eine kleine Huffman Baum,
dann die A wird auch durch zwei Bits als irgendwo in der Mitte gegenüberliegenden dargestellt.
>> Nur um über ein anderes einfaches Beispiel für die Huffman-Baum gehen,
sagen, Sie haben den String "Hallo."
Was Sie tun, ist in erster würden Sie sagen, wie viele Male hat H in dieser erscheinen?
H erscheint einmal und dann e erscheint einmal und dann haben wir l erscheinen zweimal
und o erscheinen einmal.
Und so ist, dann wir erwarten welchen Buchstaben von der geringsten Anzahl von Bits dargestellt werden?
[Schüler] l. >> L. Yeah. l richtig ist.
Wir erwarten, l durch die geringste Anzahl von Bits dargestellt werden
weil ich am meisten in der Zeichenfolge verwendet "Hallo."
Was ich jetzt tun wird ziehen diese Knoten.
Ich habe 1, welche H ist, und dann eine weitere 1, die E ist, und dann eine 1, die o ist -
im Moment bin ich setzen sie um - und dann 2, das ist l.
Dann sage ich: die Art und Weise, dass ich einen Huffman-Baum zu bauen, ist die 2-Knoten mit den geringsten Frequenzen zu finden
und sie Geschwister durch die Schaffung eines übergeordneten Knoten.
Hier haben wir drei Knoten mit der niedrigsten Frequenz. Sie sind alle ein.
Also hier haben wir wählen, welche wir gehen zuerst zu verknüpfen.
Sagen wir, ich wählen Sie die H-und die E.
Die Summe von 1 + 1 gleich 2 ist, aber dieser Knoten nicht über einen Brief mit ihm verbunden.
Es hält nur den Wert.
Jetzt sind wir an der nächsten 2 tiefsten Frequenzen zu suchen.
Das ist 2 und 1. Das könnte entweder zu den 2 sein, aber ich werde diese zu wählen.
Die Summe ist 3.
Und dann endlich, ich habe nur noch 2 Stück, so dann wird das 5.
Dann ist hier, wie erwartet, wenn ich füllen die Codierung für das,
1s immer der rechte Ast und 0s sind die linke.
Dann haben wir l von nur 1 Bit und dann die o durch 2 dargestellt
und dann wird die E durch 2 und dann das H fällt auf 3 Bits.
So können Sie übertragen diese Botschaft "Hallo", anstatt wirklich mit den Zeichen
von nur 0 und 1.
Beachten Sie jedoch, dass in einigen Fällen haben wir Beziehungen zu unseren Frequenz hatte.
Wir konnten entweder beigetreten sind die H und O ersten vielleicht.
Oder dann später, wenn wir hatten die l um 2 vertreten
sowie die trat einem durch 2 dargestellt, könnte man entweder ein verknüpft haben.
>> Und so, wenn Sie senden die 0 und 1, die eigentlich nicht garantiert
dass der Empfänger vollständig lesen Ihre Nachricht auf Anhieb
weil sie vielleicht nicht wissen, welche Entscheidung Sie gemacht.
Also, wenn wir mit Huffman-Kompression zu tun haben,
irgendwie haben wir den Empfänger unserer Botschaft, wie wir uns entschieden zu erzählen -
Sie müssen irgendeine Art von persönlichen Informationen kennen
zusätzlich zu der komprimierten Nachricht.
Sie müssen verstehen, was der Baum tatsächlich aussieht,
wie wir tatsächlich diese Entscheidungen.
>> Hier wurden wir gerade dabei Beispiele für die tatsächliche Anzahl basiert,
aber manchmal kann man auch einen Huffman-Baum
basierend auf der Häufigkeit, mit der Buchstaben erscheinen, und es ist genau das gleiche Verfahren.
Hier bin ich Ausdruck in Prozentzahlen ausgedrückt oder einer Fraktion,
und so hier genau dasselbe.
Ich finde die 2 niedrigsten, sie summieren, die nächsten 2 niedrigsten, sie summieren,
bis ich einen vollen Baum.
Obwohl wir tun könnten, so oder so, wenn wir mit Prozentsätzen zu tun haben,
das bedeutet, dass wir teilen alles und den Umgang mit Dezimalzahlen oder eher schwimmt
wenn wir über Datenstrukturen eines Kopfes denken.
Was wissen wir über floats wissen?
Was ist ein häufiges Problem, wenn wir mit Schwimmern zu tun?
[Schüler] Ungenaue Arithmetik. >> Ja. Ungenauigkeit.
Aufgrund der Fließkomma-Ungenauigkeit, für diese pset, so dass wir sicher
dass wir nicht verlieren alle Werte, dann sind wir eigentlich los mit der Anzahl zu tun haben.
Also, wenn Sie wurden zu einer Huffman-Knoten zu denken, wenn Sie zurück auf die Struktur hier,
wenn man sich den grünen schauen Sie hat eine Frequenz mit ihr verbundenen
ebenso wie es verweist auf einen Knoten auf der linken Seite sowie einem Knoten zu seinem Recht.
Und dann die roten gibt es auch einen Charakter mit ihnen verbunden.
Wir gehen nicht zu trennen diejenigen für die Eltern und dann den Endknoten zu machen,
denen wir als Blätter, sondern die müssen nur NULL-Werte.
Für jeden Knoten müssen wir ein Zeichen, das Symbol, dass Knoten repräsentiert,
dann eine Frequenz sowie einen Zeiger auf seiner linken Kindes sowie dessen rechtes Kind.
Die Blätter, die ganz unten sind, müssten auch Knotenzeiger
zu ihrer Linken und ihr Recht, aber da diese Werte verweist nicht auf tatsächlichen Knoten,
was deren Wert sein? >> [Schüler] NULL. >> NULL. Genau.
Hier ist ein Beispiel dafür, wie Sie die Frequenz in Posen vertreten,
aber wir werden mit ihm sein Umgang mit Zahlen,
so alles, was ich tat, ist den Datentyp gibt.
>> Lassen Sie uns auf ein bisschen mehr von einem komplexen Beispiel gehen.
Aber jetzt, da wir die Einfältigen getan, es ist nur der gleiche Vorgang.
Sie finden die 2 niedrigsten Frequenzen, summieren die Frequenzen
und das ist die neue Frequenz Ihrer übergeordneten Knoten,
die dann weist auf seiner linken mit dem 0 Zweig und rechts mit dem ein Zweig.
Wenn wir den String "Dies ist CS50," haben wir dann zählen, wie viele Male T erwähnt,
h erwähnt, i, s, c, 5, 0.
Dann tat ich hier mit den roten Knoten ich gepflanzt,
Ich sagte, ich werde diese Zeichen schließlich haben an der Unterseite meines Baumes.
Diejenigen gehen, um alle Blätter sein.
Dann, was ich tat, ist Ich sortierte sie nach Häufigkeit in aufsteigender Reihenfolge,
und das ist eigentlich der Weg, den pset Code es tut
ist es sortiert sie nach Frequenz und dann alphabetisch.
So hat es die Zahlen zuerst und dann alphabetisch nach der Frequenz.
Dann, was ich tun würde, ist würde ich die 2 niedrigsten finden. Das ist 0 und 5.
Ich würde sie summieren, und das ist 2. Dann würde ich weiter, finden die nächsten 2 niedrigsten.
Das sind die beiden 1s, und dann diejenigen geworden 2 als gut.
Jetzt weiß ich, dass mein nächster Schritt wird sein Eintritt in die niedrigste Zahl,
das ist der T, der 1, und dann über eine der Knoten, die 2 hat wie die Frequenz.
Also hier haben wir 3 Möglichkeiten.
Was ich für den Schieber zu tun ist nur optisch neu zu ordnen sie für Sie
so dass Sie sehen können, wie baue ich es.
Was der Code und Ihrer Distribution Code tun würde sich dem T ein
mit 0 bis 5 Knoten.
Also dann, dass Beträge bis 3, und dann werden wir den Prozess fortzusetzen.
Die 2 und die 2 jetzt sind die niedrigsten, so dass dann die Summe auf 4.
Jeder nach so weit? Okay.
Dann, nach, dass wir die 3 und die 3, die addiert werden müssen,
so ich denke schon wieder nur Einschalten, so dass Sie visuell so kann sehen, dass es nicht zu chaotisch.
Dann haben wir eine 6, und dann unsere letzte Schritt ist nun, dass wir nur noch 2 Knoten
fassen wir diejenigen, die Wurzel unserer Baum, der 10 ist zu machen.
Und die Zahl 10 macht Sinn, weil jeder Knoten dargestellt,
ihren Wert, ihre Häufigkeit Zahl, war, wie oft sie in der Zeichenfolge erschien,
und dann haben wir 5 Zeichen in unserem String, so das macht Sinn.
Wenn wir schauen, wie wir tatsächlich kodieren,
wie erwartet, das i und der n, die die am häufigsten erscheint
werden durch die geringste Anzahl von Bits dargestellt.
>> Hier vorsichtig sein.
In Huffman Bäumen der Fall tatsächlich ankommt.
Durch ein großes S ist anders als einem Kleinbuchstaben s.
Hätten wir "Dies ist CS50" mit Großbuchstaben, dann die Kleinbuchstaben s nur zweimal erscheinen,
würde ein Knoten mit 2 als Wert sein, und dann Großbuchstaben S nur einmal.
Also dann Ihren Baum würde sich ändern, Strukturen, weil Sie haben tatsächlich einen zusätzlichen Blatt hier.
Aber die Summe immer noch 10 sein.
Das ist, was wir eigentlich gehen zu dem Aufruf der Prüfsumme,
die Zugabe aller Zählungen.
>> Nun, da wir Huffman Bäumen bedeckt, können wir in Huff'n Puff, der pset tauchen.
Wir werden mit einem Querschnitt von Fragen beginnen,
und dies wird, um Sie mit binären Bäumen und wie man rund um die Bedienung gewöhnt:
Zeichnen Knoten, die Erstellung Ihrer eigenen typedef struct für einen Knoten,
und zu sehen, wie Sie in einem binären Baum, eine, die ist sortiert einzufügen,
durchqueren, und solche Dinge.
Dieses Wissen ist definitiv zu Ihnen helfen, wenn Sie in die Huff'n Puff Teil Tauchgang
der pset.
In der Standard-Edition des pset, ist Ihre Aufgabe, Puff zu implementieren,
und in der Hacker-Version Ihre Aufgabe ist es Huff umzusetzen.
Was Huff tut, ist es dauert Text und dann übersetzt sie in die 0 und 1,
so dass der Prozess, den wir oben gemacht haben, wo wir die Frequenzen gezählt
und machte dann den Baum und sagte dann: "Wie bekomme ich T?"
T wird durch 100 repräsentiert, solche Dinge,
und dann Huff würde den Text und dann ausgegeben, dass binäre.
Aber auch, weil wir wissen, dass wir unsere Empfänger der Nachricht zulassen möchten
die exakt gleiche Baum neu, es enthält auch Informationen über die Häufigkeiten.
Dann mit Puff wir eine binäre Datei von 0 und 1 gegeben
und auch die Informationen über die Frequenzen gegeben.
Wir übersetzen alle diese 0s und 1s in die ursprüngliche Nachricht, war,
so dass wir Dekomprimieren, dass.
Wenn du tust die Standard Edition sind, brauchen Sie nicht, um Huff implementieren,
so dann können Sie einfach das Personal Umsetzung Huff.
Es gibt Hinweise in der Spezifikation auf, wie dies zu tun.
Sie können die Mitarbeiter Umsetzung Huff nach einem bestimmten Text-Datei ausführen
und verwenden Sie dann, dass der Ausgang als Eingang Puff.
>> Wie ich bereits erwähnt habe, haben wir eine Menge der Verteilung Code für diesen ein.
Ich werde beginnen werde durch sie.
Ich werde die meiste Zeit auf dem zu verbringen. H-Dateien
weil in den. c Dateien, da haben wir die. h
und dass bietet uns mit den Prototypen der Funktionen,
wir nicht vollständig brauchen, um genau zu verstehen -
Wenn Sie nicht verstehen, was los ist in der. C-Dateien, dann nicht zu viele Sorgen,
aber definitiv versuchen, einen Blick zu nehmen, weil es einige Hinweise geben könnte
und es ist nützlich, um das Lesen anderer Leute Code zu gewöhnen.
>> Mit Blick auf huffile.h, in den Kommentaren erklärt sie eine Abstraktionsschicht für die Huffman-kodierte Dateien.
Wenn wir nach unten gehen, sehen wir, dass es ein Maximum von 256 Zeichen, dass wir vielleicht Codes für benötigen.
Dies umfasst alle Buchstaben des Alphabets - Groß-und Kleinschreibung -
und dann Symbole und Zahlen, etc.
Dann haben wir hier eine magische Zahl, die eine Huffman-codierten Datei.
Innerhalb eines Huffman-Code sie gehen, um eine bestimmte magische Zahl haben
assoziiert mit dem Header.
Das mag nur eine zufällige magische Zahl zu sehen,
aber wenn Sie übersetzen es tatsächlich in ASCII, dann ist es tatsächlich buchstabiert HUFF.
Hier haben wir eine Struktur für eine Huffman-codierte Datei.
Es gibt all diese Eigenschaften mit einem Huff Datei zugeordnet ist.
Dann hinunter wir hier die Überschrift für eine Huff Datei haben, so nennen wir es Huffeader
Statt der Zugabe der zusätzlichen h, weil es die gleiche klingt sowieso.
Cute.
Wir haben eine magische Zahl zugeordnet.
Wenn es eine tatsächliche Huff-Datei ist, es geht um die Zahl da oben sein, diese Magie ein.
Und dann wird es ein Array.
Also für jedes Symbol, von denen es 256,
es geht um aufzulisten, was die Häufigkeit dieser Symbole innerhalb des Huff Datei.
Und schließlich haben wir eine Prüfsumme für die Frequenzen,
was sollte die Summe dieser Frequenzen sein.
Also das ist, was ein Huffeader ist.
Dann haben wir einige Funktionen, die das nächste Bit zurück in die Huff-Datei
sowie schreibt ein Bit nach Huff Datei, und dann diese Funktion hier, hfclose
das tatsächlich schließt die Huff-Datei.
Vorher waren wir mit geraden nur fclose zu tun haben,
aber wenn man eine Huff Datei haben, anstelle von fclosing es
was Sie tatsächlich tun werden, ist hfclose und hfopen es.
Das sind spezielle Funktionen für die Huff-Dateien, die wir gehen, um mit zu tun haben.
Dann hier sind wir in der Kopfzeile zu lesen und dann schreiben Sie die Kopfzeile.
>> Nur durch das Lesen der. H-Datei können wir Art ein Gefühl von dem, was ein Huff Datei könnte sein,
welche Eigenschaften es hat, ohne tatsächlich in die huffile.c,
die, wenn wir in tauchen, wird ein bisschen komplizierter.
Es hat all der Datei I / O hier mit Zeigern.
Hier sehen wir, dass, wenn wir hfread nennen, zum Beispiel, es ist immer noch mit fread.
Wir sind nicht loszuwerden diese Funktionen vollständig, aber wir schicken diejenigen, die gepflegt werden
im Huff Datei statt alles tun es uns.
Sie können sich gerne durch diese scannen, wenn Sie neugierig sind
und gehen und schälen die Ebene wieder ein wenig.
>> Die nächste Datei, dass wir gehen, zu betrachten ist tree.h.
Bevor in der Walkthrough gleitet wir sagten, wir erwarten eine Huffman-Knoten
und wir haben eine typedef struct Knoten.
Wir erwarten, dass es ein Symbol, eine Frequenz, und dann 2 Knoten Sterne haben.
In diesem Fall, was wir tun, ist dies im Wesentlichen die gleiche
aber anstatt des Knotens werden wir nennen sie Bäume.
Wir haben eine Funktion, dass wenn Sie Baum nennen Sie gibt einen Baum Zeiger.
Sichern, um Speller, wenn Sie machten einen neuen Knoten
Sie sagten node * neues Wort = malloc (sizeof) und solche Dinge.
Grundsätzlich ist mktree denn damit zu tun für Sie.
Ebenso, wenn Sie einen Baum entfernen möchten,
Also das ist im wesentlichen die Befreiung der Baum, wenn Sie mit ihm fertig sind,
anstelle von expliziten Aufruf kostenlos auf, dass Sie eigentlich nur gehen, um die Funktion rmtree verwenden
wo Sie in der Zeiger übergeben, um den Baum und dann tree.c kümmern, dass für Sie.
>> Wir schauen in tree.c.
Wir erwarten, dass die gleiche Funktion, jedoch die Umsetzung so gut sehen.
Wie erwartet, wenn man mktree nennen mallocs die Größe eines Baums in einen Zeiger,
initialisiert alle Werte der NULL-Wert, so 0s oder NULL,
und gibt dann den Zeiger auf dem Baum, dass du nur um dich malloc'd.
Hier beim Entfernen Baum nennen es erste sorgt dafür, dass Sie nicht doppelt zu befreien.
Es stellt sicher, dass Sie tatsächlich ein Baum, den Sie entfernen möchten.
Hier, weil ein Baum auch seine Kinder,
was dieser tut, ist es ruft rekursiv entfernen Baum auf der linken Knoten des Baumes
sowie rechten Knoten.
Bevor es die Eltern entlastet, braucht es, um die Kinder als auch befreien.
Eltern ist auch austauschbar mit root.
Die erste Mutter, so wie der Ur-Ur-Ur-Ur-Großvater
oder Großmutter Baum, zuerst müssen wir befreien sich die Ebenen ersten.
So auf den Boden zu überqueren, freie diejenigen, und dann wieder kommen, freie diejenigen, etc.
Also das ist Baum.
>> Jetzt schauen wir uns Wald.
Wald ist, wo Sie alle Ihre Huffman Bäumen platzieren.
Es sagt, dass wir gehen, um etwas zu haben als ein Grundstück
das enthält einen Zeiger auf einen Baum sowie einen Zeiger auf einem Grundstück namens Next.
Welche Struktur hat diese Art der aussehen?
Es Art von heißt es dort.
Hier drüben.
Eine verkettete Liste.
Wir sehen, dass, wenn wir ein Grundstück haben es wie eine verkettete Liste von Grundstücken ist.
Ein Wald wird als verkettete Liste der Grundstücke definiert,
und so die Struktur des Waldes ist, dass wir gerade dabei, einen Zeiger müssen unsere erste Handlung
und dass Grundstück hat einen Baum in ihr oder vielmehr auf einem Baum
und dann auf das nächste Grundstück, so weiter und so fort.
Um einen Wald machen wir nennen mkforest.
Dann haben wir ein paar ziemlich nützliche Funktionen hier.
Wir haben abholen, wo Sie in einem Wald und passieren dann ist der Rückgabewert ist ein Baum *
ein Zeiger auf einen Baum.
Was Pick tun werden, ist es in den Wald gehen, dass Sie auf den Hinweis
dann entfernen Sie einen Baum mit der niedrigsten Frequenz von diesem Wald
und dann geben Sie den Zeiger auf dem Baum.
Sobald Sie holen aufrufen, wird der Baum nicht in den Wald mehr gibt,
aber der Rückgabewert ist der Zeiger auf dem Baum.
Dann haben Sie Pflanze.
Vorausgesetzt, dass Sie übergeben einen Zeiger auf eine Struktur, die eine nicht-0 Frequenz hat,
Welche Pflanze tun werden, ist es in den Wald, nehmen Sie die Baum und Pflanze, Baum innerhalb des Waldes.
Hier haben wir rmforest.
Ähnlich wie Baum, die im Grunde befreit alle unsere Bäume für uns zu entfernen,
Entfernen Wald freier Wille alles in diesem Wald enthalten.
>> Wenn wir in forest.c anschauen, werden wir erwarten, dass mindestens 1 rmtree Befehl dort zu sehen,
weil, um Speicher frei im Wald, wenn ein Wald hat Bäume in ihm,
dann schließlich wirst du haben, um diese Bäume zu entfernen.
Wenn wir in forest.c aussehen, haben wir unsere mkforest, die, wie wir erwarten.
Wir malloc Dinge.
Wir initialisieren die erste Grundstück im Wald als NULL, weil es leer ist zu beginnen,
dann sehen wir, pick, die den Baum wieder mit dem geringsten Gewicht, die niedrigste Frequenz,
und dann entledigt diesem bestimmten Knoten, die auf dem Baum und das nächste,
so dauert es, dass aus der verketteten Liste des Waldes.
Und dann haben wir hier Anlage, die Einsätze auf einen Baum in der verketteten Liste.
Welche Wald tut, ist es schön hält es für uns sortiert.
Und schließlich haben wir rmforest und, wie erwartet, wir rmtree genannt dort haben.
>> Betrachtet man die Verteilung Code so weit war huffile.c wohl mit Abstand am schwierigsten zu verstehen,
während die anderen Dateien selbst waren ziemlich einfach zu folgen.
Mit unserem Wissen von Zeigern und verkettete Listen und solche,
konnten wir recht gut folgen.
Aber alles, was wir brauchen, um wirklich sicherzustellen, dass wir voll und ganz zu verstehen, ist die. H-Dateien
weil Sie zu rufen diese Funktionen, die sich mit diesen Rückgabewerten
so stellen Sie sicher, dass Sie verstehen, was Aktion wird durchgeführt werden
wenn Sie einer jener Funktionen aufrufen.
Aber tatsächlich das Verständnis innerhalb der IT ist nicht ganz notwendig, weil wir die haben. H-Dateien.
Wir haben 2 weitere Dateien in unseren Verteiler-Code überlassen.
>> Lassen Sie uns Dump aussehen.
Dump durch seine Kommentar hier nimmt eine Huffman-komprimierte Datei
und dann übersetzt und Dumps alle seine Inhalte aus.
Hier sehen wir, dass es ruft hfopen.
Dies ist eine Art Spiegelung in einer Datei * input = fopen,
und dann passieren Sie die Informationen ein.
Es ist fast identisch mit der Ausnahme anstelle einer Datei * Sie in einem Huffile Durchreise;
Statt fopen Sie in hfopen vorbei.
Hier lesen wir in der Kopfzeile erste, was ist eine Art ähnlich wie lesen wir in der Kopfzeile
für eine Bitmap-Datei.
Was wir hier tun, ist zu überprüfen, ob die Header-Informationen
enthält die richtige magische Zahl, dass es eine tatsächliche Huff-Datei ist zeigt,
dann alle diese Prüfungen, um sicherzustellen, dass die Datei, die wir offen ist eine tatsächliche schnaufte Datei oder nicht.
Was dies bedeutet ist es gibt die Frequenzen aller Symbole, die wir sehen können,
innerhalb einer Terminal in eine grafische Tisch.
Dieser Teil wird nützlich sein.
Es hat ein bisschen und liest Bit für Bit in der Variablen bisschen und dann druckt es aus.
So wenn ich zu dump on hth.bin, die das Ergebnis von schnaufend eine Datei aufrufen
mit dem Personal-Lösung, würde ich dies.
Es ist die Ausgabe alle diese Zeichen und dann setzen die Frequenz, mit der sie erscheinen.
Wenn wir betrachten, sind die meisten von ihnen mit Ausnahme für diese 0s: H, der zweimal erscheint,
und dann T, die einmal erscheint.
Und dann haben wir hier die eigentliche Nachricht in 0s und 1s.
Wenn wir hth.txt betrachten, ist die vermutlich die ursprüngliche Nachricht, die schnaubte,
wir erwarten, dass einige Hs und Ts in dort zu sehen.
Insbesondere erwarten wir, nur 1 T und 2 Hs sehen.
Hier sind wir in hth.txt. Es hat in der Tat HTH.
Im dort, obwohl wir es nicht sehen können, ist ein Zeilenumbruch.
Die Huff-Datei hth.bin auch Codierung der Zeilenumbruch als gut.
Hier, weil wir wissen, dass die Reihenfolge HTH und dann newline ist,
können wir sehen, dass wahrscheinlich die H dargestellt wird, durch nur einen einzigen 1
und dann das T ist vermutlich 01 und dann wird die nächste H 1 sowie
und dann haben wir einen Zeilenumbruch durch zwei 0s angegeben.
Cool.
>> Und schließlich, weil wir mit mehreren. C-Geschäfte und. H-Dateien,
werden wir eine ziemlich komplexe Argument der Compiler haben,
und so haben wir hier ein Makefile, die Deponie für Sie macht.
Aber eigentlich müssen Sie über Ihre eigenen puff.c Datei.
Das Makefile tatsächlich nicht mit der Herstellung puff.c für Sie tun.
Wir verlassen, dass bis zu Ihnen, um die Makefile bearbeiten.
Wenn Sie einen Befehl wie make all eingeben, zum Beispiel, wird es alle von ihnen für Sie.
Fühlen Sie sich frei, um auf die Beispiele des Makefile aus der Vergangenheit pset aussehen
sowie Abheben dieses ein, um zu sehen, wie Sie in der Lage sein, um Ihre Puff Datei vornehmen
und bearbeite diese Makefile.
Das war es für unsere Vertriebs-Code.
>> Nachdem wir durch das, bekommen haben, dann ist hier nur eine weitere Erinnerung
wie werden wir mit den Huffman-Knoten zu tun haben.
Wir gehen nicht zu rufen Sie Knoten mehr, wir gehen zu rufen ihnen Bäume
wohin wir gehen zu repräsentieren ihr Symbol mit einem char,
ihre Häufigkeit, die Anzahl des Auftretens, mit einer Ganzzahl.
Wir verwenden, weil es genauer als eine float ist.
Und dann haben wir einen weiteren Zeiger auf der linken Kindes sowie das Recht Kind.
Ein Wald, wie wir gesehen haben, ist nur eine verlinkte Liste von Bäumen.
Letztendlich, wenn wir den Aufbau unserer Huff-Datei,
Wir wollen unseren Wald auf nur 1 Baum enthalten -
1 Baum, 1 root mit mehreren Kindern.
Früher, als wir nur, dass unsere Huffman-Bäume,
starteten wir, indem alle Knoten auf unserem Bildschirm
und sagen, wir gehen, um diese Knoten haben,
sie schließlich werde die Blätter sein wollen, und das ist ihr Symbol, das ist ihre Frequenz.
In unserem Wald, wenn wir nur 3 Buchstaben, das ist ein Wald von 3 Bäumen.
Und dann, als wir weitergehen, wenn wir die ersten Eltern aufgenommen,
machten wir einen Wald von 2 Bäumen.
Wir haben 2 dieser Kinder aus unserem Wald und dann ersetzt es mit einem übergeordneten Knoten
das hatte die 2 Knoten als Kinder.
Und dann endlich, unsere letzte Schritt mit der Herstellung unserem Beispiel mit dem As, Bs und Cs
wäre es, die endgültige übergeordneten machen,
und so dann wäre unsere gesamte Anzahl der Bäume im Wald auf 1 zu bringen.
Hat jeder sehen, wie Sie beginnen mit mehreren Bäumen in der Gesamtstruktur
und am Ende mit 1? Okay. Cool.
>> Was brauchen wir für Puff zu tun?
Was wir tun müssen, ist sicherzustellen, dass, wie immer, sie geben uns die richtige Art von Input
so dass wir tatsächlich das Programm auszuführen.
In diesem Fall werden sie gehst zu geben uns nach dem ersten Befehlszeilenargument
2 weitere: die Datei, die wir wollen zu dekomprimieren und der Ausgang der dekomprimierten Datei.
Aber sobald wir sicherstellen, dass sie uns passieren in der richtigen Menge von Werten,
Wir wollen sicherstellen, dass die Eingabe eine Huff-Datei ist oder nicht.
Und dann, wenn wir garantieren, dass es sich um eine Huff-Datei ist, dann müssen wir unseren Baum bauen wollen,
Aufbau des Baumes, so dass es den Baum, dass die Person, die die Nachricht geschickt gebaut übereinstimmt.
Dann, nachdem wir den Baum zu bauen, dann können wir behandeln die 0 und 1, dass sie weitergegeben werden,
folgen denen entlang unserer Baum, weil er identisch ist,
und schreiben Sie dann die Nachricht aus, interpretieren die Bits wieder in Zeichen.
Und dann am Ende, weil wir mit Zeigern zu tun hier,
Wir wollen sicherstellen, dass wir keine Speicherlecks
und dass wir frei alles.
>> Sicherstellung der ordnungsgemäßen Nutzung ist ein alter Hut für uns jetzt.
Wir leben in einer Eingabe nehmen, was wird der Name der Datei zu paffen sein,
und dann legen wir eine Ausgabe,
so dass der Name der Datei für die gepufften Ausgang, der die Textdatei sein wird.
Das ist Einsatz. Und jetzt wollen wir sicherstellen, dass die Eingabe schnaubte ist oder nicht.
Wenn ich zurückdenke, gab es etwas in der Verteilung Code, der uns helfen könnte
mit dem Verständnis, ob eine Datei schnaufte ist oder nicht?
Es gab Informationen in huffile.c über die Huffeader.
Wir wissen, dass jeder Huff Datei einen Huffeader mit ihm mit einer magischen Nummer zugeordnet ist
sowie eine Anordnung von den Frequenzen für jedes Symbol
sowie eine Prüfsumme.
Wir wissen das, aber wir haben auch einen Blick auf dump.c,
, in dem es in einem Huff Datei lesen.
Und so zu tun, hatte es zu überprüfen, ob es wirklich war, schnaubte oder nicht.
So könnten wir vielleicht benutzen dump.c als eine Struktur für unsere puff.c.
Zurück zur pset 4, wenn wir die Datei copy.c, die in RGB Tripel kopiert hatten
und wir interpretieren, dass für Whodunit und Resize,
ähnlich ist, was Sie tun können, nur den Befehl wie cp dump.c puff.c laufen
und verwenden einen Teil des Codes gibt.
Allerdings ist es nicht zu sein, wie einfach eines Prozesses
für die Übersetzung Ihrer dump.c in puff.c,
aber zumindest gibt es Ihnen irgendwo zu beginnen
wie sichergestellt werden, dass der Eingang effektiv schnaufte oder nicht
sowie ein paar andere Dinge.
Wir haben ordnungsgemäße Nutzung gewährleistet und sichergestellt, dass der Eingang schnaubte wird.
Jedes Mal, dass wir getan, dass wir unsere richtige Fehlerprüfung getan haben,
so zurück und verlassen die Funktion, wenn irgendein Fehler tritt auf, wenn es ein Problem gibt.
>> Nun, was wir wollen, ist bauen die eigentliche Baum.
Wenn wir im Wald suchen, gibt es 2 Hauptfunktionen
dass wir gehen zu wollen, sehr vertraut mit.
Es gibt die Boolesche Funktion Pflanze, Pflanzen a non-0-Frequenz Baum in unserem Wald.
Und so gibt passieren Sie einen Zeiger auf einen Wald und einen Zeiger auf einen Baum.
Kurze Frage: Wie viele Wälder werden Sie haben, wenn Sie den Aufbau einer Huffman-Baum sind?
Unser Wald ist wie unsere Leinwand, nicht wahr?
Also sind wir nur gehen, um ein Wald haben, aber wir werden auf mehrere Bäume.
Also, bevor Sie Pflanze nennen, sind Sie vermutlich gehen zu wollen, Ihren Wald machen.
Es ist ein Befehl für dass, wenn Sie in forest.h auf, wie man einen Wald aussehen.
Sie können einen Baum pflanzen. Wir wissen, wie das zu tun.
Und dann kann man auch wählen einen Baum aus dem Wald,
Entfernen eines Baumes mit dem geringsten Gewicht und geben Sie den Mauszeiger darauf.
Denken wir zurück, wenn wir taten den Beispielen selbst,
wenn wir zogen es heraus, wir einfach haben soeben die Links.
Aber hier, statt nur das Hinzufügen der Links,
denke es mehr als du Entfernen 2 dieser Knoten und dann ersetzt sie durch eine andere.
Um dies in Bezug auf die Kommissionierung und Pflanzgut auszudrücken,
Sie Kommissionierung 2 Bäume und dann pflanzen einen Baum
das hat diese 2 Bäume, die Sie als Kinder abgeholt.
Um Huffman den Baum zu bauen, können Sie in den Symbolen und Frequenzen in Reihenfolge gelesen
weil die Huffeader gibt, dass Sie,
gibt Ihnen eine Reihe von Frequenzen.
So können Sie voran gehen und einfach ignorieren alles, was mit der 0 in ihm
weil wir nicht wollen, 256 Blätter am Ende davon.
Wir wollen nur die Anzahl der Blätter, die Zeichen sind
dass tatsächlich in der Datei verwendet.
Sie können in dieser Symbole zu lesen, und jedes dieser Symbole, die nicht-null Frequenzen haben,
die gehen, um Bäume.
Was Sie tun können, ist jedes Mal, wenn in einem nicht-0-Frequenz-Symbol lesen,
Sie pflanzen den Baum im Wald.
Sobald Sie die Bäume zu pflanzen im Wald, können Sie diese Bäume als Geschwister teilnehmen,
so geht zurück auf Pflanzen und Kommissionierung, wo Sie abholen 2 und dann Anlage 1,
wo das 1, die Sie Pflanze die Muttergesellschaft der 2 Kinder, dass Sie abgeholt ist.
Also Ihr Endergebnis wird ein einzelner Baum in der Gesamtstruktur sein.
Das ist, wie Sie Ihren Baum zu bauen.
>> Es gibt mehrere Dinge, die schief gehen könnte hier
weil wir mit der Herstellung neuer Bäume und den Umgang mit Zeigern und solche Dinge zu tun.
Vor, wenn wir mit Zeigern zu tun haben,
wenn wir malloc'd wollten wir sicherstellen, dass es nicht zurück uns eine NULL-Zeiger-Wert.
So in mehreren Schritten in diesem Prozess gibt es werde einige Fälle geben,
wo Ihr Programm scheitern könnte.
Was Sie tun möchten, ist Sie wollen sicherstellen, dass Sie diese Fehler zu behandeln,
und in der spec sie sagt, sie ordnungsgemäß zu behandeln,
so gerne drucken Sie eine Nachricht an den Benutzer sagen, warum das Programm zu beenden
und dann umgehend beenden Sie es.
Um diese Fehlerbehandlung zu tun, denken Sie daran, dass Sie es überprüfen wollen
jedes Mal, es könnte ein Fehler sein.
Jedes einzelne Mal, dass du machst einen neuen Zeiger
Sie wollen sicherstellen, dass das erfolgreich ist.
Bevor das, was wir zu tun pflegten wird eine neue Zeiger und malloc es machen,
und dann würden wir prüfen, ob dieser Zeiger NULL ist.
So gibt es werde einige Fälle, in denen Sie gerade tun, kann das sein,
aber manchmal Sie tatsächlich den Aufruf einer Funktion
und in dieser Funktion, das ist das eine, die macht das mallocing ist.
In diesem Fall, wenn wir blicken zurück auf einige der Funktionen innerhalb des Codes,
einige von ihnen sind Boolesche Funktionen.
In der abstrakten Fall, wenn wir eine Boolesche Funktion namens foo,
Grundsätzlich kann man, dass zusätzlich zu tun, was bedeutet foo annehmen,
da es eine Boolesche Funktion ist, gibt es wahr oder falsch -
true, wenn erfolgreich, andernfalls false.
So wollen wir prüfen, ob der Rückgabewert von foo wahr oder falsch ist.
Wenn es falsch ist, bedeutet das, dass wir gehen zu wollen, um irgendeine Art von Nachricht zu drucken
und dann das Programm beenden.
Was wir wollen, ist den Rückgabewert von foo.
Wenn foo false zurückgibt, dann wissen wir, dass wir irgendeine Art von Fehler aufgetreten
und wir müssen unser Programm zu beenden.
Ein Weg, dies zu tun, ist eine Bedingung, wo die eigentliche Funktion selbst Ihr Zustand.
Sagen foo nimmt in x.
Wir können als eine Bedingung, wenn haben (foo (x)).
Grundsätzlich bedeutet dies, dass, wenn am Ende der Ausführung foo es wahr zurückgibt,
dann können wir dies tun, weil die Funktion muss foo evaluieren
um zu beurteilen, die ganze Zustand.
Also das ist, wie können Sie so etwas tun, wenn die Funktion wahr und ist erfolgreich.
Aber wenn Sie die Fehlerprüfung sind, Sie wollen nur beenden, wenn Ihre Funktion false zurück.
Was Sie tun können, ist fügen Sie einfach einen == false oder fügen Sie einfach einen Knall vor ihm
und dann haben Sie if (! foo).
Innerhalb dieser Körper dieser Bedingung würden Sie haben alle die Fehlerbehandlung,
so mögen ", konnte nicht erstellt werden diesen Baum" und dann wieder 1 oder so ähnlich.
Was das bedeutet, ist jedoch, dass, obwohl foo false zurückgegeben -
Sagen foo true zurück.
Dann müssen Sie nicht auf foo erneut aufrufen. Das ist ein weit verbreitetes Missverständnis.
Weil es in deinem Zustand war, ist es bereits ausgewertet,
so haben Sie bereits das Ergebnis, wenn Sie machen Baum oder so etwas sind
pflanzliche oder Pick oder so etwas.
Es hat schon diesen Wert. Es ist bereits ausgeführt.
So ist es sinnvoll, Boolesche Funktionen als Bedingung verwenden
denn ob Sie tatsächlich auszuführen, den Körper der Schleife
es führt die Funktion sowieso.
>> Unsere vorletzte Schritt ist das Schreiben der Nachricht in die Datei.
Sobald wir die Huffman-Baum zu bauen, dann Schreiben der Nachricht in die Datei ist ziemlich einfach.
Es ist ziemlich einfach jetzt folgen Sie einfach dem 0s und 1s.
Und so durch Konvention wir wissen, dass in einem Huffman-Baum die 0s linken Seite zeigen
und die 1s zeigen nach rechts.
Also, wenn Sie in etwas zu lesen für Stück, jedes Mal, dass Sie eine 0 zu erhalten
Sie folgen dem linken Ast, und dann jedes Mal, wenn Sie lesen in einer 1
Sie gehen zu den rechten Zweig folgen.
Und dann wirst du weiter, bis Sie ein Blatt getroffen
weil die Blätter gehen, um am Ende der Schenkel liegen.
Wie können wir sagen, ob wir ein Blatt oder nicht getroffen habe?
Wir sagten es vor.
[Schüler] Wenn die Zeiger NULL sind. >> Ja.
Wir können sagen, wenn wir ein Blatt getroffen haben, wenn die Zeiger auf die linke und rechte Bäumen NULL sind.
Perfect.
Wir wissen, dass wir in Bit für Bit zu lesen in unseren Huff file wollen.
Wie wir bereits in dump.c gesehen haben, ist, was sie taten sie etwas gelesen von Bit in das Huff-Datei
und gerade heraus, was diese Bits gedruckt wurden.
Wir gehen nicht zu tun. Wir werden tun, etwas, das ein wenig komplexer ist.
Aber was wir tun können ist, können wir das bisschen Code, der in der Bit-Lesevorgänge zu nehmen.
Hier haben wir die Zahl Bit für das aktuelle Bit, dass wir uns befinden.
Dieser kümmert sich Iteration alle Bits in der Datei, bis Sie das Ende der Datei zu schlagen.
Auf dieser Grundlage, dann sind Sie gehen zu wollen, um irgendeine Art von Iterator haben
Ihren Baum zu durchlaufen.
Und dann, ob das Bit 0 oder 1 basiert,
Sie gehen zu wollen, um entweder zu bewegen, dass Iterator nach links oder bewegen Sie ihn nach rechts
den ganzen Weg, bis Sie ein Blatt getroffen, so den ganzen Weg bis zu diesem Knoten, den Sie sich gerade befinden
nicht zu einem mehr Knoten zeigen.
Warum können wir tun dies mit einer Huffman-Datei aber nicht Morse-Code?
Da im Morse-Code gibt es ein wenig Unklarheit.
Wir könnten wie, oh wait sein, haben wir einen Brief auf dem Weg getroffen, so vielleicht ist unser Brief,
während, wenn wir nur ein bisschen länger fort, dann würden wir einen weiteren Brief getroffen haben.
Aber das ist nicht geschehen in Huffman-Kodierung,
so können wir sicher sein, dass der einzige Weg, dass wir gehen, um ein Zeichen getroffen
ist, wenn dieser Knoten dem linken und rechten Kinder NULL sind.
>> Schließlich wollen wir alle unsere Speicher freizugeben.
Wir wollen sowohl in der Nähe des Huff-Datei, die wir mit beschäftigt
sowie die Entfernung aller Bäume in unseren Wäldern.
Basierend auf Ihrer Implementierung, sind Sie wahrscheinlich gehen zu wollen, rufen Sie entfernen Wald
anstatt wirklich gehen durch alle Bäume sich.
Aber wenn Sie alle temporären Bäumen, Sie wollen zu befreien, dass.
Sie wissen Ihren Code am besten, so dass Sie wissen, wo Sie Zuweisen von Speicher sind.
Und so, wenn Sie in zu gehen, sogar um Kontrolle F'ing für malloc starten,
sehen, wenn Sie malloc und dafür sorgen, dass Sie alle, dass der freie
aber dann gerade durch Ihren Code,
verstehen, wo Sie Speicher kann zugeteilt wurden.
Normalerweise könnte einfach sagen: "Am Ende einer Datei Ich werde einfach Wald auf meinen Wald zu entfernen",
so dass im Grunde klar, dass der Speicher frei, dass
"Und dann bin ich auch gehen, um die Datei zu schließen und dann mein Programm wird beendet."
Aber ist das das einzige Mal, dass Ihr Programm beendet?
Nein, denn manchmal gibt es vielleicht ein Fehler, die passieren können.
Vielleicht könnten wir eine Datei nicht öffnen oder wir könnten nicht einen anderen Baum
oder irgendeine Art von Fehler passiert im Speicher Allokation und so kehrte er NULL.
Ein Fehler passiert und dann haben wir wieder und beenden.
So dann wollen Sie sicherstellen, dass alle möglichen Zeit, dass Ihr Programm beenden können,
Sie wollen alle Ihre Speicher gibt befreien.
Es ist nicht einfach so zu ganz am Ende der Hauptfunktion, dass Sie Ihren Code aufzuhören.
Sie wollen zurück zu blicken auf jede Instanz, dass Ihr Code möglicherweise könnte vorzeitig zurück
und dann frei unabhängig Speicher sinnvoll.
Sagen Sie angerufen hatte um Wald und das false zurückgegeben.
Dann haben Sie wahrscheinlich nicht brauchen, um Ihrer Gesamtstruktur entfernen
weil du nicht einen Wald noch.
Aber an jedem Punkt im Code, wo Sie vielleicht vorzeitig zurück
Sie wollen sicherstellen, dass Sie alle möglichen Speicher freizugeben.
>> Also, wenn wir mit Speicherfreigabe Umgang und mit potenziellen Lecks,
Wir wollen nicht nur unsere Urteilskraft und unsere Logik
aber auch Valgrind, um festzustellen, ob wir alle unsere Speicher freigegeben worden sind oder nicht.
Sie können entweder Valgrind am Puff und dann haben Sie auch weitergeben
die richtige Anzahl von Kommandozeilen-Argumente Valgrind.
Sie können das, aber der Ausgang ist ein bisschen kryptisch.
Wir haben ein bisschen daran gewöhnt mit Speller bekommen, aber wir brauchen noch ein bisschen mehr Hilfe,
so dann läuft es mit ein paar mehr Flags wie das Leck-Check = full,
das wird wahrscheinlich geben Sie uns einige weitere hilfreiche Ausgang Valgrind.
>> Dann ein weiterer nützlicher Tipp, wenn Sie Debugging ist der Unterschied Befehl.
Sie können auf der Mitarbeiter Durchführung von Huff, laufen, dass auf einer Text-Datei,
und dann Ausgabe, die es in eine binäre Datei, eine binäre Huff-Datei, um genau zu sein.
Dann, wenn Sie Ihr eigenes puff auf dieser Binärdatei
dann idealerweise wird die Ausgabe der Text-Datei werde identisch sein
an das Original, das Sie übergeben in.
Hier verwende ich hth.txt wie das Beispiel, und das ist das ein darüber gesprochen in Ihrem spec.
Das ist buchstäblich nur HTH und dann ein Zeilenumbruch.
Aber auf jeden Fall fühlen Sie sich frei, und Sie werden auf jeden Fall dazu ermutigt, mehr Beispiele verwenden
für Ihren Text-Datei.
>> Sie können sogar einen Schuss auf möglicherweise komprimiert und dann dekomprimiert
einige der Dateien, die Sie in Speller verwendet, wie Krieg und Frieden
oder Jane Austen oder so etwas - das ist irgendwie cool wäre - oder Austin Powers,
Art des Umgangs mit größeren Dateien denn wir würden nicht kommen, es
wenn wir verwendet das nächste Werkzeug hier ls-l.
Wir fahren nach ls, die im Grunde sind alle Inhalte in unserem aktuellen Verzeichnis verwendet.
Passing in der Flagge-l tatsächlich zeigt die Größe dieser Dateien.
Wenn Sie durch die pset spec gehen, es tatsächlich führt Sie durch die Erstellung der Binärdatei,
der schnaufend, und Sie sehen, dass für sehr kleine Dateien
der Raum Kosten komprimieren und Übersetzung all dieser Informationen
aller Frequenzen und dergleichen überwiegt der tatsächliche Nutzen
des Komprimierens der Datei in dem ersten Platz.
Aber wenn man es auf einigen längeren Text-Dateien ausführen, dann könnten Sie sehen, dass Sie einen gewissen Nutzen Sie beginnen
beim Komprimieren Sie diese Dateien.
>> Und schließlich haben wir unsere alten Kumpel GDB, die definitiv ist in praktisch zu kommen.
>> Haben wir irgendwelche Fragen über Huff Bäumen oder den Prozess vielleicht machen die Bäume
oder irgendwelche anderen Fragen über Huff'n Puff?
Okay. Ich bleibe ein bisschen herum.
>> Thanks, everyone. Dies war Walkthrough 6. Und viel Glück.
>> [CS50.TV]