1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [Soluzione - Problema Set 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla Chan - Harvard University]

3
00:00:04,810 --> 00:00:07,240
[Questo è CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Ciao a tutti, e benvenuti a Scenario 6: Puff Huff'n.

5
00:00:12,180 --> 00:00:17,440
In Puff Huff'n quello che stiamo facendo sta andando a che fare con un file compresso Huffman

6
00:00:17,440 --> 00:00:20,740
e poi sbuffando di nuovo in su, in modo da decompressione,

7
00:00:20,740 --> 00:00:25,810
in modo che possiamo tradurre dal 0 e 1 che l'utente ci invia

8
00:00:25,810 --> 00:00:30,660
e convertirlo di nuovo nel testo originale.

9
00:00:30,660 --> 00:00:34,360
Pset 6 è sarà piuttosto fresco perché si sta andando a vedere alcuni degli strumenti

10
00:00:34,360 --> 00:00:41,730
utilizzato nel pset 4 e 5 e pset tipo di combinarle in 1 concetto abbastanza carino

11
00:00:41,730 --> 00:00:43,830
quando si arriva a pensarci.

12
00:00:43,830 --> 00:00:50,110
>> Inoltre, probabilmente, pset 4 e 5 sono stati i più difficili pset che aveva da offrire.

13
00:00:50,110 --> 00:00:53,950
Quindi da ora, abbiamo questa pset altri 1 in C,

14
00:00:53,950 --> 00:00:56,480
e poi, dopo che siamo alla programmazione web.

15
00:00:56,480 --> 00:01:02,310
Quindi voi congratulo per superare il più duro gobba in CS50.

16
00:01:03,630 --> 00:01:09,760
>> Passando per Puff Huff'n, la nostra cassetta degli attrezzi per questo pset saranno alberi di Huffman,

17
00:01:09,760 --> 00:01:14,700
in modo da comprendere non solo come il lavoro binario alberi, ma anche in particolare alberi di Huffman,

18
00:01:14,700 --> 00:01:16,240
come sono costruiti.

19
00:01:16,240 --> 00:01:20,210
E poi stiamo andando ad avere un sacco di codice di distribuzione in questo pset,

20
00:01:20,210 --> 00:01:22,480
e ci vengono a vedere che in realtà parte del codice

21
00:01:22,480 --> 00:01:24,670
potremmo non essere in grado di comprendere appieno ancora,

22
00:01:24,670 --> 00:01:30,080
e così quelli che saranno i file. c, ma poi i loro accompagnatori. h file

23
00:01:30,080 --> 00:01:34,300
ci darà abbastanza capire che abbiamo bisogno in modo da sapere come funzionano queste funzioni

24
00:01:34,300 --> 00:01:38,100
o per lo meno quello che dovrebbero fare - i loro ingressi e uscite -

25
00:01:38,100 --> 00:01:40,760
anche se non sappiamo cosa sta succedendo nella scatola nera

26
00:01:40,760 --> 00:01:44,090
o non capiscono cosa sta succedendo nella scatola nera all'interno.

27
00:01:44,090 --> 00:01:49,400
E infine, come al solito, si tratta di strutture di dati nuovi,

28
00:01:49,400 --> 00:01:51,840
specifici tipi di nodi che puntano a certe cose,

29
00:01:51,840 --> 00:01:56,080
ed ecco avente una carta e penna non solo per il processo di progettazione

30
00:01:56,080 --> 00:01:58,470
e quando si sta cercando di capire come dovrebbe funzionare il vostro pset

31
00:01:58,470 --> 00:02:00,520
ma anche durante il debug.

32
00:02:00,520 --> 00:02:06,140
Si può avere GDB insieme alla tua carta e penna, mentre si prende giù quali sono i valori,

33
00:02:06,140 --> 00:02:09,320
in cui le frecce siano rivolte, e cose del genere.

34
00:02:09,320 --> 00:02:13,720
>> Prima diamo un'occhiata agli alberi di Huffman.

35
00:02:13,720 --> 00:02:19,600
Alberi di Huffman sono alberi binari, il che significa che ogni nodo ha solo 2 figli.

36
00:02:19,600 --> 00:02:24,870
Negli alberi Huffman la caratteristica è che i valori più frequenti

37
00:02:24,870 --> 00:02:27,140
sono rappresentati dai minor quantità di bit.

38
00:02:27,140 --> 00:02:32,690
Abbiamo visto negli esempi delle lezioni di codice Morse, che tipo di consolidato alcune lettere.

39
00:02:32,690 --> 00:02:38,030
Se stai cercando di tradurre una A o una E, per esempio,

40
00:02:38,030 --> 00:02:43,940
si sta traducendo che spesso, così, invece di dover utilizzare il set completo di bit

41
00:02:43,940 --> 00:02:48,640
assegnare per il solito tipo di dati, lo si comprime fino a meno,

42
00:02:48,640 --> 00:02:53,730
e poi quelle lettere che sono rappresentati meno spesso sono rappresentati con più bit

43
00:02:53,730 --> 00:02:59,840
perché si può permettere che, quando si pesano le frequenze che le lettere compaiono.

44
00:02:59,840 --> 00:03:03,020
Abbiamo la stessa idea qui in alberi di Huffman

45
00:03:03,020 --> 00:03:12,360
dove stiamo facendo una catena, una sorta di percorso per arrivare ai personaggi alcuni.

46
00:03:12,360 --> 00:03:14,470
E poi i personaggi che hanno più frequenza

47
00:03:14,470 --> 00:03:17,940
stanno per essere rappresentata con il minor numero di bit.

48
00:03:17,940 --> 00:03:22,020
>> Il modo in cui si costruisce un albero di Huffman

49
00:03:22,020 --> 00:03:27,430
è mettere tutti i personaggi che compaiono nel testo

50
00:03:27,430 --> 00:03:30,630
e calcolando la loro frequenza, la frequenza con cui appaiono.

51
00:03:30,630 --> 00:03:33,880
Questo potrebbe essere un conteggio di quante volte quelle lettere appaiono

52
00:03:33,880 --> 00:03:40,270
o forse una percentuale su tutti i caratteri quante ognuno appare.

53
00:03:40,270 --> 00:03:44,270
E così quello che fai è una volta che avete tutto questo fuori mappato,

54
00:03:44,270 --> 00:03:49,060
poi si guarda per le 2 frequenze più basse e poi unirsi a loro come fratelli

55
00:03:49,060 --> 00:03:55,660
dove poi il nodo genitore ha una frequenza che è la somma delle sue due bambini.

56
00:03:55,660 --> 00:04:00,870
E poi, per convenzione, dire che il nodo di sinistra,

57
00:04:00,870 --> 00:04:03,770
si segue che seguendo lo 0 ramo,

58
00:04:03,770 --> 00:04:08,140
e quindi il nodo più a destra è il 1 filiale.

59
00:04:08,140 --> 00:04:16,040
Come abbiamo visto in codice Morse, il un dettaglio è che se si ha solo un segnale acustico e il segnale acustico

60
00:04:16,040 --> 00:04:18,120
era ambigua.

61
00:04:18,120 --> 00:04:22,430
Esso potrebbe essere 1 lettera o potrebbe essere una sequenza di due lettere.

62
00:04:22,430 --> 00:04:27,790
E allora cosa Huffman alberi fa è perché dalla natura dei personaggi

63
00:04:27,790 --> 00:04:34,140
o i nostri personaggi finali effettivi che sono i nodi ultime sul ramo -

64
00:04:34,140 --> 00:04:39,300
ci riferiamo a quelli come foglie - in virtù di che non vi può essere alcuna ambiguità

65
00:04:39,300 --> 00:04:45,160
in termini di quale lettera si sta cercando di codificare con la serie di bit

66
00:04:45,160 --> 00:04:50,670
perché nulla lungo i bit che rappresentano 1 lettera

67
00:04:50,670 --> 00:04:55,960
vi incontrano un'altra lettera tutto, e non ci sarà alcuna confusione lì.

68
00:04:55,960 --> 00:04:58,430
Ma andiamo in esempi che voi ragazzi può effettivamente vedere che

69
00:04:58,430 --> 00:05:02,120
invece di noi solo dicendo che questo è vero.

70
00:05:02,120 --> 00:05:06,390
>> Vediamo un semplice esempio di un albero di Huffman.

71
00:05:06,390 --> 00:05:09,380
Ho una stringa qui che è di 12 caratteri.

72
00:05:09,380 --> 00:05:14,010
Ho 4 Come, 6 B, e 2 Cs.

73
00:05:14,010 --> 00:05:17,270
Il mio primo passo sarebbe quello di contare.

74
00:05:17,270 --> 00:05:20,760
Quante volte A appare? Appare 4 volte nella stringa.

75
00:05:20,760 --> 00:05:25,060
B appare 6 volte, e C compare 2 volte.

76
00:05:25,060 --> 00:05:28,970
Naturalmente, ho intenzione di dire che sto usando B il più delle volte,

77
00:05:28,970 --> 00:05:35,970
quindi voglio rappresentare B con il minor numero di bit, il minor numero di 0 e 1.

78
00:05:35,970 --> 00:05:42,600
E poi ho anche intenzione di aspettare C di richiedere il maggior numero di 0 e 1, come pure.

79
00:05:42,600 --> 00:05:48,550
In primo luogo quello che ho fatto qui è Li ho messi in ordine crescente in termini di frequenza.

80
00:05:48,550 --> 00:05:52,710
Vediamo che la C e la A, queste sono le nostre 2 frequenze più basse.

81
00:05:52,710 --> 00:06:00,290
Creiamo un nodo genitore, e tale nodo padre non dispone di una lettera ad esso associata,

82
00:06:00,290 --> 00:06:05,070
ma ha una frequenza, che è la somma.

83
00:06:05,070 --> 00:06:08,780
La somma diventa 2 + 4, che è 6.

84
00:06:08,780 --> 00:06:10,800
Poi seguiamo il ramo di sinistra.

85
00:06:10,800 --> 00:06:14,970
Se fossimo in quel nodo 6, poi ci avrebbe seguito da 0 a raggiungere C

86
00:06:14,970 --> 00:06:17,450
e poi 1 per arrivare ad A.

87
00:06:17,450 --> 00:06:20,300
Così ora abbiamo 2 nodi.

88
00:06:20,300 --> 00:06:23,920
Abbiamo il valore 6 e quindi abbiamo anche un altro nodo con il valore 6.

89
00:06:23,920 --> 00:06:28,550
E così quei 2 non sono solo più 2, ma anche solo il 2 che sono di sinistra,

90
00:06:28,550 --> 00:06:33,820
così ci uniamo a quelle di un altro genitore, con la somma sia 12.

91
00:06:33,820 --> 00:06:36,300
Quindi qui abbiamo il nostro albero di Huffman

92
00:06:36,300 --> 00:06:40,020
dove per arrivare a B, che sarebbe solo il bit 1

93
00:06:40,020 --> 00:06:45,430
e poi per arrivare a A avremmo 01 e quindi C con 00.

94
00:06:45,430 --> 00:06:51,300
Così, qui vediamo che, in fondo stiamo rappresentare questi caratteri con 1 o 2 bit

95
00:06:51,300 --> 00:06:55,160
dove il B, come previsto, ha il minimo.

96
00:06:55,160 --> 00:07:01,730
E poi ci aspettavamo C per avere di più, ma dal momento che è un piccolo albero di Huffman,

97
00:07:01,730 --> 00:07:06,020
poi la A è rappresentato da 2 bit a differenza qualche parte nel mezzo.

98
00:07:07,820 --> 00:07:11,070
>> Solo per andare oltre un altro semplice esempio di albero di Huffman,

99
00:07:11,070 --> 00:07:19,570
dire che hai la stringa "Ciao".

100
00:07:19,570 --> 00:07:25,360
Quello che fai è prima dire quante volte H appare in questo?

101
00:07:25,360 --> 00:07:34,200
H appare una volta e poi e compare una sola volta e poi abbiamo l appare due volte

102
00:07:34,200 --> 00:07:36,580
e o apparire una volta.

103
00:07:36,580 --> 00:07:44,310
E così poi ci aspettiamo che la lettera di essere rappresentato dal minor numero di bit?

104
00:07:44,310 --> 00:07:47,450
[Studente] l. >> L. Gia '. l è giusto.

105
00:07:47,450 --> 00:07:50,730
Ci aspettiamo l per essere rappresentato dal minimo numero di bit

106
00:07:50,730 --> 00:07:55,890
perché l è usato più in la stringa "Ciao".

107
00:07:55,890 --> 00:08:04,280
Quello che sto per fare ora è tirare fuori questi nodi.

108
00:08:04,280 --> 00:08:15,580
Ho 1, che è H, e poi un altro 1, che è posta, e poi un 1, che è O -

109
00:08:15,580 --> 00:08:23,410
in questo momento io li sto mettendo in ordine - e poi 2, che è l.

110
00:08:23,410 --> 00:08:32,799
Allora io dico che il modo in cui ho costruito un albero di Huffman è quello di trovare i 2 nodi con meno frequenze

111
00:08:32,799 --> 00:08:38,010
e li rendono fratelli creando un nodo padre.

112
00:08:38,010 --> 00:08:41,850
Qui abbiamo 3 nodi con la frequenza più bassa. Sono tutti 1.

113
00:08:41,850 --> 00:08:50,620
Ecco quindi scegliere quale andremo a collegare prima.

114
00:08:50,620 --> 00:08:54,850
Diciamo che ho scelto l'H e l'indirizzo.

115
00:08:54,850 --> 00:09:01,150
La somma di 1 + 1 è 2, ma questo nodo non ha una lettera ad esso associati.

116
00:09:01,150 --> 00:09:04,440
Tiene solo il valore.

117
00:09:04,440 --> 00:09:10,950
Ora guardiamo i prossimi 2 frequenze più basse.

118
00:09:10,950 --> 00:09:15,590
Che è 2 e 1. Questo potrebbe essere uno di questi 2, ma ho intenzione di scegliere questo.

119
00:09:15,590 --> 00:09:18,800
La somma è 3.

120
00:09:18,800 --> 00:09:26,410
E poi finalmente, ho solo 2 a sinistra, in modo quindi che diventa 5.

121
00:09:26,410 --> 00:09:32,010
Poi qui, come previsto, se compilare la codifica per questo,

122
00:09:32,010 --> 00:09:37,480
1s sono sempre il ramo di destra e 0 sono la sinistra.

123
00:09:37,480 --> 00:09:45,880
Poi abbiamo l rappresentato dal solo 1 po 'e poi l'O di 2

124
00:09:45,880 --> 00:09:52,360
e quindi l'e da 2 e poi l'H scende a 3 bit.

125
00:09:52,360 --> 00:09:59,750
Così si può trasmettere questo messaggio "Ciao" invece di realtà utilizzando i caratteri

126
00:09:59,750 --> 00:10:02,760
da solo 0 e 1.

127
00:10:02,760 --> 00:10:07,910
Tuttavia, ricordare che in diversi casi abbiamo avuto legami con la nostra frequenza.

128
00:10:07,910 --> 00:10:11,900
Avremmo potuto né aderito H e l'O forse prima.

129
00:10:11,900 --> 00:10:15,730
Oppure poi più tardi, quando abbiamo avuto la l rappresentata da 2

130
00:10:15,730 --> 00:10:19,410
nonché l'unita quello rappresentato da 2, abbiamo potuto legati né uno.

131
00:10:19,410 --> 00:10:23,630
>> E così, quando si invia il 0 e 1, che in realtà non garantisce

132
00:10:23,630 --> 00:10:27,090
che il destinatario può leggere il messaggio completo destra fuori del blocco

133
00:10:27,090 --> 00:10:30,490
perché potrebbe non sapere quale decisione che hai fatto.

134
00:10:30,490 --> 00:10:34,920
Così, quando abbiamo a che fare con la compressione Huffman,

135
00:10:34,920 --> 00:10:40,090
in qualche modo dire al destinatario del nostro messaggio come abbiamo deciso -

136
00:10:40,090 --> 00:10:43,470
Hanno bisogno di sapere qualche tipo di informazioni aggiuntive

137
00:10:43,470 --> 00:10:46,580
in aggiunta al messaggio compresso.

138
00:10:46,580 --> 00:10:51,490
Hanno bisogno di capire che cosa l'albero si presenta come,

139
00:10:51,490 --> 00:10:55,450
come abbiamo effettivamente fatto quelle decisioni.

140
00:10:55,450 --> 00:10:59,100
>> Qui stavamo solo facendo esempi basati sul conteggio effettivo,

141
00:10:59,100 --> 00:11:01,550
ma a volte si può anche avere un albero di Huffman

142
00:11:01,550 --> 00:11:05,760
in base alla frequenza con cui le lettere appaiono, e il processo è esattamente lo stesso.

143
00:11:05,760 --> 00:11:09,090
Qui mi sto esprimendo in termini di percentuali o di una frazione,

144
00:11:09,090 --> 00:11:11,290
ed ecco la stessa cosa.

145
00:11:11,290 --> 00:11:15,300
Trovo il 2 più basso, riassumerle, il più basso 2 successivo, li somma,

146
00:11:15,300 --> 00:11:19,390
finché non avrò un albero pieno.

147
00:11:19,390 --> 00:11:23,610
Anche se potremmo farlo in entrambi i modi, quando abbiamo a che fare con percentuali,

148
00:11:23,610 --> 00:11:27,760
che significa che stiamo dividere le cose e si occupano di decimali o meglio galleggia

149
00:11:27,760 --> 00:11:30,900
se stiamo pensando di strutture di dati di una testa.

150
00:11:30,900 --> 00:11:32,540
Che cosa sappiamo di carri?

151
00:11:32,540 --> 00:11:35,180
Che cosa è un problema comune quando abbiamo a che fare con i galleggianti?

152
00:11:35,180 --> 00:11:38,600
[Studente] aritmetica impreciso. Sì >>. Imprecisione.

153
00:11:38,600 --> 00:11:43,760
A causa di imprecisione in virgola mobile, per questo pset in modo da assicurarsi che

154
00:11:43,760 --> 00:11:49,450
che non perde alcun valore, allora siamo veramente andando a che fare con il conteggio.

155
00:11:49,450 --> 00:11:54,880
Quindi, se si dovesse pensare ad un nodo Huffman, se si guarda indietro alla struttura qui,

156
00:11:54,880 --> 00:12:01,740
se si guardano quelle verdi ha una frequenza ad esso associati

157
00:12:01,740 --> 00:12:08,760
nonché punta a un nodo alla sua sinistra e un nodo alla sua destra.

158
00:12:08,760 --> 00:12:13,970
E poi i rossi ci hanno anche un carattere associato con loro.

159
00:12:13,970 --> 00:12:18,900
Non stiamo andando a fare quelle separate per i genitori e poi i nodi finali,

160
00:12:18,900 --> 00:12:23,680
cui ci riferiamo come foglie, ma questi saranno solo i valori NULL.

161
00:12:23,680 --> 00:12:31,050
Per ogni nodo avremo un carattere, il simbolo che rappresenta quel nodo,

162
00:12:31,050 --> 00:12:40,490
quindi una frequenza e un puntatore al suo figlio sinistro e il suo figlio destro.

163
00:12:40,490 --> 00:12:45,680
Le foglie, che sono in fondo, avrebbe anche puntatori nodo

164
00:12:45,680 --> 00:12:49,550
alla loro sinistra e alla loro destra, ma dal momento che tali valori non siano rivolte ai nodi reali,

165
00:12:49,550 --> 00:12:53,970
quale sarebbe il loro valore è? >> [Studente] NULL. >> NULL. Esattamente.

166
00:12:53,970 --> 00:12:58,430
Ecco un esempio di come si potrebbe rappresentare la frequenza di carri allegorici,

167
00:12:58,430 --> 00:13:02,130
ma stiamo andando a che fare con con numeri interi,

168
00:13:02,130 --> 00:13:06,780
quindi tutto quello che ho fatto è cambiare il tipo di dati lì.

169
00:13:06,780 --> 00:13:09,700
>> Passiamo a un po 'più di un esempio complesso.

170
00:13:09,700 --> 00:13:13,360
Ma ora che abbiamo fatto quelli semplici, è proprio lo stesso processo.

171
00:13:13,360 --> 00:13:20,290
Potete trovare le 2 frequenze più basse, sommare le frequenze

172
00:13:20,290 --> 00:13:22,450
e questa è la nuova frequenza del nodo padre,

173
00:13:22,450 --> 00:13:29,310
che punta poi alla sua sinistra con il ramo 0 e il diritto con il ramo 1.

174
00:13:29,310 --> 00:13:34,200
Se abbiamo la stringa "Questo è CS50", quindi contiamo quante volte viene citato T,

175
00:13:34,200 --> 00:13:38,420
h accennato, i, s, c, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Allora quello che ho fatto qui è con i nodi rossi ho appena piantato,

177
00:13:42,010 --> 00:13:48,530
Ho detto che ho intenzione di avere questi personaggi alla fine nella parte inferiore del mio albero.

178
00:13:48,530 --> 00:13:51,740
Coloro che saranno tutte le foglie.

179
00:13:51,740 --> 00:13:58,200
Allora quello che ho fatto è che li ordinato per frequenza in ordine crescente,

180
00:13:58,200 --> 00:14:02,950
e questo è in realtà il modo in cui il codice pset fa

181
00:14:02,950 --> 00:14:07,550
è esso viene ordinato in base alla frequenza e poi in ordine alfabetico.

182
00:14:07,550 --> 00:14:13,870
Così ha i numeri e poi in ordine alfabetico per la frequenza.

183
00:14:13,870 --> 00:14:18,520
Allora quello che vorrei fare è che avrei trovato il 2 più basso. Questo è 0 e 5.

184
00:14:18,520 --> 00:14:22,390
Io li somma, e questo è 2. Poi vorrei continuare, trovare il prossimo 2 più basso.

185
00:14:22,390 --> 00:14:26,100
Questi sono gli 1 due, e poi quelli diventano 2, come pure.

186
00:14:26,100 --> 00:14:31,570
Ora so che il mio prossimo passo sta per entrare a far parte il numero più basso,

187
00:14:31,570 --> 00:14:41,380
che è la T, l'1 e quindi scegliendo uno dei nodi che ha 2 come frequenza.

188
00:14:41,380 --> 00:14:44,560
Quindi qui abbiamo 3 opzioni.

189
00:14:44,560 --> 00:14:47,980
Che cosa ho intenzione di fare per la diapositiva è solo visivamente riorganizzare per voi

190
00:14:47,980 --> 00:14:51,790
in modo che si può vedere come lo sto costruendo.

191
00:14:51,790 --> 00:14:59,040
Quello che il codice e il codice di distribuzione è intenzione di fare sarebbe far parte T uno

192
00:14:59,040 --> 00:15:01,410
con il nodo 0 e 5.

193
00:15:01,410 --> 00:15:05,060
Allora che le somme a 3, e poi continuiamo il processo.

194
00:15:05,060 --> 00:15:08,660
Il 2 e il 2 ora sono i più bassi, in modo poi quelli somma a 4.

195
00:15:08,660 --> 00:15:12,560
Tutti in seguito fino ad ora? Va bene.

196
00:15:12,560 --> 00:15:16,410
Poi, dopo che abbiamo il 3 e il 3 che devono essere sommati,

197
00:15:16,410 --> 00:15:21,650
così ancora una volta sto solo di commutazione in modo che si può vedere visivamente in modo che non diventi troppo disordinato.

198
00:15:21,650 --> 00:15:25,740
Poi abbiamo un 6, e poi il nostro passo finale è che ora abbiamo solo 2 nodi

199
00:15:25,740 --> 00:15:30,440
sommiamo quelli per rendere la radice del nostro albero, che è 10.

200
00:15:30,440 --> 00:15:34,100
E il numero 10 ha un senso, perché ogni nodo rappresentato,

201
00:15:34,100 --> 00:15:40,750
il loro valore, il loro numero di frequenza, è quante volte sono apparsi nella stringa,

202
00:15:40,750 --> 00:15:46,350
e poi abbiamo 5 caratteri nella nostra stringa, in modo che abbia un senso.

203
00:15:48,060 --> 00:15:52,320
Se guardiamo a come si sarebbe in realtà lo codifica,

204
00:15:52,320 --> 00:15:56,580
come previsto, la i e la s, che appaiono più spesso

205
00:15:56,580 --> 00:16:01,350
sono rappresentati dal minor numero di bit.

206
00:16:03,660 --> 00:16:05,660
>> Fate attenzione qui.

207
00:16:05,660 --> 00:16:09,780
Negli alberi di Huffman caso conta realmente.

208
00:16:09,780 --> 00:16:13,670
Un S maiuscola è diverso da una s minuscola.

209
00:16:13,670 --> 00:16:21,260
Se avessimo "Questo è CS50" con lettere maiuscole, quindi la lettera minuscola s solo apparire due volte,

210
00:16:21,260 --> 00:16:27,120
sarebbe un nodo con 2 come il suo valore, e quindi S maiuscola sarebbe solo una volta.

211
00:16:27,120 --> 00:16:33,440
Allora l'albero sarebbe cambiare le strutture, perché in realtà hanno una foglia in più qui.

212
00:16:33,440 --> 00:16:36,900
Ma la somma sarebbe ancora 10.

213
00:16:36,900 --> 00:16:39,570
Questo è quello che stiamo effettivamente andando a essere chiamata la somma di controllo,

214
00:16:39,570 --> 00:16:44,060
l'aggiunta di tutti i conteggi.

215
00:16:46,010 --> 00:16:50,990
>> Ora che abbiamo coperto gli alberi di Huffman, siamo in grado di tuffarsi in Puff Huff'n, il pset.

216
00:16:50,990 --> 00:16:52,900
Stiamo per iniziare con una sezione di domande,

217
00:16:52,900 --> 00:16:57,990
e questo sta per farti abituato con gli alberi binari e come operare in giro che:

218
00:16:57,990 --> 00:17:03,230
nodi di disegno, creare il tuo proprio struct typedef per un nodo,

219
00:17:03,230 --> 00:17:07,230
e vedere come è possibile inserire in un albero binario, che è ordinato,

220
00:17:07,230 --> 00:17:09,050
movimento, e cose del genere.

221
00:17:09,050 --> 00:17:14,560
Questa conoscenza è sicuramente essere di aiuto quando ci si immerge nella porzione Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
del pset.

223
00:17:19,150 --> 00:17:26,329
Nell'edizione standard del pset, il vostro compito è quello di attuare Puff,

224
00:17:26,329 --> 00:17:30,240
e nella versione hacker, il vostro compito è quello di attuare Huff.

225
00:17:30,240 --> 00:17:38,490
Che cosa fa è Huff prende il testo e poi si traduce in 0 e 1,

226
00:17:38,490 --> 00:17:41,990
in modo che il processo che abbiamo fatto in precedenza in cui abbiamo contato le frequenze

227
00:17:41,990 --> 00:17:50,970
e poi ha fatto l'albero e poi disse: «Come faccio a T?"

228
00:17:50,970 --> 00:17:54,840
T è rappresentato da 100, cose del genere,

229
00:17:54,840 --> 00:17:58,860
e poi Huff avrebbe preso il testo e poi output binario.

230
00:17:58,860 --> 00:18:04,920
Ma anche perché sappiamo che vogliamo permettere che il nostro destinatario del messaggio

231
00:18:04,920 --> 00:18:11,790
per ricreare l'albero esattamente lo stesso, ma include anche le informazioni sui conteggi di frequenza.

232
00:18:11,790 --> 00:18:17,980
Poi con Puff ci viene dato un file binario di 0 e 1

233
00:18:17,980 --> 00:18:21,740
e dato anche informazioni relative alle frequenze.

234
00:18:21,740 --> 00:18:26,740
Traduciamo tutti i vostri cari 0 e 1 nel messaggio originale che era,

235
00:18:26,740 --> 00:18:29,350
quindi siamo decompressione che.

236
00:18:29,350 --> 00:18:36,450
Se stai facendo l'edizione standard, non è necessario implementare Huff,

237
00:18:36,450 --> 00:18:39,290
così allora si può semplicemente utilizzare l'implementazione staff di Huff.

238
00:18:39,290 --> 00:18:42,080
Ci sono istruzioni nelle specifiche su come farlo.

239
00:18:42,080 --> 00:18:48,780
È possibile eseguire l'applicazione personale di Huff su un file di testo certa

240
00:18:48,780 --> 00:18:53,270
e quindi utilizzare tale uscita come input per Puff.

241
00:18:53,270 --> 00:18:59,330
>> Come ho detto prima, abbiamo un sacco di codice di distribuzione per questo.

242
00:18:59,330 --> 00:19:01,810
Ho intenzione di cominciare ad andare attraverso di essa.

243
00:19:01,810 --> 00:19:04,400
Ho intenzione di passare la maggior parte del tempo sul file. H

244
00:19:04,400 --> 00:19:07,660
perché nei file. c, perché abbiamo il. h

245
00:19:07,660 --> 00:19:11,650
e che ci fornisce i prototipi delle funzioni,

246
00:19:11,650 --> 00:19:15,520
non siamo pienamente bisogno di capire esattamente -

247
00:19:15,520 --> 00:19:20,280
Se non si capisce cosa sta succedendo nei file. C, quindi non preoccupatevi troppo,

248
00:19:20,280 --> 00:19:23,600
ma provare a dare un'occhiata, perché potrebbe dare qualche suggerimento

249
00:19:23,600 --> 00:19:29,220
ed è utile abituarsi a leggere il codice di altre persone.

250
00:19:38,940 --> 00:19:48,270
>> Guardando huffile.h, nei commenti dichiara un livello di astrazione per Huffman codifica dei file.

251
00:19:48,270 --> 00:20:01,660
Se andiamo verso il basso, si vede che c'è un massimo di 256 simboli che potremmo bisogno di codici per.

252
00:20:01,660 --> 00:20:05,480
Ciò include tutte le lettere dell'alfabeto - maiuscole e minuscole -

253
00:20:05,480 --> 00:20:08,250
e poi simboli e numeri, ecc

254
00:20:08,250 --> 00:20:11,930
Allora qui abbiamo un numero magico che identifica un Huffman codifica del file.

255
00:20:11,930 --> 00:20:15,890
All'interno di un codice di Huffman che stanno per avere un certo numero magico

256
00:20:15,890 --> 00:20:18,560
associato con l'intestazione.

257
00:20:18,560 --> 00:20:21,110
Questo potrebbe sembrare un semplice numero magico casuale,

258
00:20:21,110 --> 00:20:27,160
ma se in realtà si traducono in ASCII, quindi incantesimi effettivamente fuori HUFF.

259
00:20:27,160 --> 00:20:34,290
Qui abbiamo una struttura di un file con codifica Huffman.

260
00:20:34,290 --> 00:20:39,670
Ci sono tutte queste caratteristiche associate a un file Huff.

261
00:20:39,670 --> 00:20:47,080
Quindi qui abbiamo l'intestazione di un file Huff, e così lo chiamiamo Huffeader

262
00:20:47,080 --> 00:20:50,810
invece di aggiungere il h extra perché sembra lo stesso in ogni caso.

263
00:20:50,810 --> 00:20:52,720
Carino.

264
00:20:52,720 --> 00:20:57,790
Abbiamo un numero magico associato.

265
00:20:57,790 --> 00:21:09,040
Se è un file vero e proprio Huff, che sta per essere il numero in alto, questa magia uno.

266
00:21:09,040 --> 00:21:14,720
E poi avrà una serie.

267
00:21:14,720 --> 00:21:18,750
Quindi per ogni simbolo, di cui ci sono 256,

268
00:21:18,750 --> 00:21:24,760
sta andando a elencare ciò che la frequenza di tali simboli sono all'interno del file Huff.

269
00:21:24,760 --> 00:21:28,090
E poi finalmente, abbiamo una somma di controllo per le frequenze,

270
00:21:28,090 --> 00:21:32,160
che dovrebbe essere la somma di tali frequenze.

271
00:21:32,160 --> 00:21:36,520
Quindi questo è quello che è un Huffeader.

272
00:21:36,520 --> 00:21:44,600
Poi ci sono alcune funzioni che restituiscono il bit successivo nel file Huff

273
00:21:44,600 --> 00:21:52,580
così come scrive un po 'per il file Huff, e poi questa funzione qui, hfclose,

274
00:21:52,580 --> 00:21:54,650
che chiude effettivamente il file Huff.

275
00:21:54,650 --> 00:21:57,290
Prima, avevamo a che fare con diritto solo fclose,

276
00:21:57,290 --> 00:22:01,190
ma quando si ha un file Huff, invece di esso fclosing

277
00:22:01,190 --> 00:22:06,080
ciò che si sta effettivamente andando a fare è hfclose e hfopen esso.

278
00:22:06,080 --> 00:22:13,220
Queste sono funzioni specifiche ai file Huff che stiamo andando a che fare con.

279
00:22:13,220 --> 00:22:19,230
Poi qui si legge nell'intestazione e quindi scrivere l'intestazione.

280
00:22:19,230 --> 00:22:25,700
>> Proprio leggendo il file. H possiamo sorta di ottenere un senso di ciò che un file di Huff potrebbe essere,

281
00:22:25,700 --> 00:22:32,480
quali sono le caratteristiche che ha, senza andare effettivamente sul huffile.c,

282
00:22:32,480 --> 00:22:36,750
che, se ci immergiamo in, sta per essere un po 'più complessa.

283
00:22:36,750 --> 00:22:41,270
Ha tutti i file di I / O qui che fare con i puntatori.

284
00:22:41,270 --> 00:22:48,010
Qui si vede che, quando chiamiamo hfread, per esempio, è ancora alle prese con fread.

285
00:22:48,010 --> 00:22:53,050
Non stiamo sbarazzarsi di queste funzioni del tutto, ma stiamo inviando quelli da prendere cura di

286
00:22:53,050 --> 00:22:59,760
all'interno del file di Huff, invece di fare tutto da soli.

287
00:22:59,760 --> 00:23:02,300
Si può sentire libero di eseguire la scansione attraverso questo se siete curiosi

288
00:23:02,300 --> 00:23:08,410
e andare a buccia lo strato posteriore un po '.

289
00:23:20,650 --> 00:23:24,060
>> Il file successivo che stiamo andando a guardare è tree.h.

290
00:23:24,060 --> 00:23:30,210
Prima nell'argomento Procedura dettagliata scorre abbiamo detto ci aspettiamo un nodo Huffman

291
00:23:30,210 --> 00:23:32,960
e abbiamo fatto un nodo typedef struct.

292
00:23:32,960 --> 00:23:38,360
Ci aspettiamo di avere un simbolo, una frequenza, e poi 2 stelle nodo.

293
00:23:38,360 --> 00:23:41,870
In questo caso quello che stiamo facendo è questo è essenzialmente la stessa

294
00:23:41,870 --> 00:23:46,880
tranne che invece di nodo che andremo a chiamarli alberi.

295
00:23:48,790 --> 00:23:56,760
Abbiamo una funzione che quando si chiama fanno albero ti restituisce un puntatore albero.

296
00:23:56,760 --> 00:24:03,450
Eseguire il backup di Speller, quando si stavano facendo un nuovo nodo

297
00:24:03,450 --> 00:24:11,410
hai detto nodo * nuova parola = malloc (sizeof) e cose del genere.

298
00:24:11,410 --> 00:24:17,510
In sostanza, mktree sta andando a che fare con quella per voi.

299
00:24:17,510 --> 00:24:20,990
Allo stesso modo, se si desidera rimuovere un albero,

300
00:24:20,990 --> 00:24:24,810
in modo che 'essenzialmente liberare l'albero quando hai finito con esso,

301
00:24:24,810 --> 00:24:33,790
invece di chiamare esplicitamente libero su questo, si sta effettivamente solo andando a utilizzare la funzione rmtree

302
00:24:33,790 --> 00:24:40,360
dove si passa il puntatore su quell'albero e poi tree.c si prenderà cura di questo per voi.

303
00:24:40,360 --> 00:24:42,490
>> Guardiamo in tree.c.

304
00:24:42,490 --> 00:24:47,240
Ci aspettiamo che le stesse funzioni se non per vedere l'attuazione e.

305
00:24:47,240 --> 00:24:57,720
Come ci aspettavamo, quando si chiama mktree mallocs che le dimensioni di un albero in un puntatore,

306
00:24:57,720 --> 00:25:03,190
inizializza tutti i valori per il valore NULL, quindi 0 o valori nulli,

307
00:25:03,190 --> 00:25:08,280
e restituisce il puntatore a tale albero che hai appena malloc'd a voi.

308
00:25:08,280 --> 00:25:13,340
Qui quando si chiama rimozione albero che prima fa in modo che non stai doppia liberazione.

309
00:25:13,340 --> 00:25:18,320
Si fa in modo che in realtà hanno un albero che si desidera rimuovere.

310
00:25:18,320 --> 00:25:23,330
Ecco perché un albero comprende anche i suoi figli,

311
00:25:23,330 --> 00:25:29,560
Quello che fa è che chiama ricorsivamente rimuovere albero sul nodo di sinistra dell'albero

312
00:25:29,560 --> 00:25:31,650
così come il nodo di destra.

313
00:25:31,650 --> 00:25:37,790
Prima libera la madre, deve liberare i figli.

314
00:25:37,790 --> 00:25:42,770
Capogruppo è anche intercambiabile con root.

315
00:25:42,770 --> 00:25:46,500
Il genitore prima volta, così come il gran-gran-gran-gran-nonno

316
00:25:46,500 --> 00:25:52,130
o albero nonna, prima dobbiamo liberare le livelli di prima.

317
00:25:52,130 --> 00:25:58,490
Quindi attraversare fino in fondo, senza quelli, e poi tornare su, senza quelli, ecc

318
00:26:00,400 --> 00:26:02,210
Ecco, questo è albero.

319
00:26:02,210 --> 00:26:04,240
>> Ora guardiamo alla foresta.

320
00:26:04,240 --> 00:26:09,860
Foresta vengono inseriti tutti i vostri alberi di Huffman.

321
00:26:09,860 --> 00:26:12,910
Sta dicendo che stiamo andando ad avere qualcosa che si chiama una trama

322
00:26:12,910 --> 00:26:22,320
che contiene un puntatore a un albero come un puntatore a una trama chiamata successiva.

323
00:26:22,320 --> 00:26:28,480
Quale struttura fa questo tipo di look simile?

324
00:26:29,870 --> 00:26:32,490
E 'sorta di si dice laggiù.

325
00:26:34,640 --> 00:26:36,700
Proprio qui.

326
00:26:37,340 --> 00:26:39,170
Una lista concatenata.

327
00:26:39,170 --> 00:26:44,590
Vediamo che quando abbiamo una trama è come una lista concatenata di trame.

328
00:26:44,590 --> 00:26:53,020
Una foresta è definito come una lista concatenata di trame,

329
00:26:53,020 --> 00:26:58,100
e così la struttura del bosco è che stiamo solo andando ad avere un puntatore per il nostro primo disegno

330
00:26:58,100 --> 00:27:02,740
e che la trama ha un albero dentro o punta piuttosto a un albero

331
00:27:02,740 --> 00:27:06,190
e punta quindi alla trama successiva, così via e così via.

332
00:27:06,190 --> 00:27:11,100
Per effettuare una foresta che chiamiamo mkforest.

333
00:27:11,100 --> 00:27:14,930
Poi ci sono alcune funzioni molto utili qui.

334
00:27:14,930 --> 00:27:23,240
Abbiamo scegliere dove si passa in un bosco e poi il valore di ritorno è un * albero,

335
00:27:23,240 --> 00:27:25,210
un puntatore a un albero.

336
00:27:25,210 --> 00:27:29,370
Che scelta farà sarà andrà nella foresta che si sta puntando a

337
00:27:29,370 --> 00:27:35,240
quindi rimuovere un albero con la frequenza più bassa di quella foresta

338
00:27:35,240 --> 00:27:38,330
e poi ti danno il puntatore a tale struttura.

339
00:27:38,330 --> 00:27:43,030
Una volta l'intercettazione, l'albero non esisterà più nella foresta,

340
00:27:43,030 --> 00:27:48,550
ma il valore di ritorno è un puntatore a quella struttura.

341
00:27:48,550 --> 00:27:50,730
Poi ci sono delle piante.

342
00:27:50,730 --> 00:27:57,420
A condizione che si passa un puntatore a un albero che ha un non-0 di frequenza,

343
00:27:57,420 --> 00:28:04,040
quale pianta farà è che ci vorrà la foresta, prendere l'albero, e la pianta che all'interno albero della foresta.

344
00:28:04,040 --> 00:28:06,370
Qui abbiamo rmforest.

345
00:28:06,370 --> 00:28:11,480
Simile a rimuovere albero, che fondamentalmente liberato tutti i nostri alberi per noi,

346
00:28:11,480 --> 00:28:16,600
rimuovere foresta sarà tutto libera contenuto in quella foresta.

347
00:28:16,600 --> 00:28:24,890
>> Se guardiamo in forest.c, ci aspettiamo di vedere almeno 1 comando rmtree in là,

348
00:28:24,890 --> 00:28:30,090
perché per liberare memoria nel bosco, se una foresta con alberi in esso,

349
00:28:30,090 --> 00:28:32,930
poi alla fine si sta andando ad avere per rimuovere quegli alberi troppo.

350
00:28:32,930 --> 00:28:41,020
Se guardiamo in forest.c, abbiamo il nostro mkforest, che è come ci aspettiamo.

351
00:28:41,020 --> 00:28:42,890
Noi malloc cose.

352
00:28:42,890 --> 00:28:51,740
Abbiamo inizializzare il primo lotto nella foresta come NULL perché è vuota per cominciare,

353
00:28:51,740 --> 00:29:05,940
poi vediamo scelta, che restituisce l'albero con il minor peso, la frequenza più bassa,

354
00:29:05,940 --> 00:29:13,560
e poi si fa eliminare quel determinato nodo che punta a quell'albero e quello successivo,

355
00:29:13,560 --> 00:29:16,760
quindi ci vuole che fuori dalla lista concatenata della foresta.

356
00:29:16,760 --> 00:29:24,510
E poi qui abbiamo delle piante, che si inserisce un albero nella lista collegata.

357
00:29:24,510 --> 00:29:29,960
Che cosa si è forestale mantiene ben risolto per noi.

358
00:29:29,960 --> 00:29:37,910
E poi finalmente, abbiamo rmforest e, come previsto, abbiamo rmtree chiamato lì.

359
00:29:46,650 --> 00:29:55,440
>> Guardando il codice di distribuzione fino ad ora, huffile.c era probabilmente di gran lunga la più difficile da capire,

360
00:29:55,440 --> 00:29:59,990
mentre gli altri file stessi erano abbastanza semplice da seguire.

361
00:29:59,990 --> 00:30:03,090
Con la nostra conoscenza di puntatori e liste concatenate e così via,

362
00:30:03,090 --> 00:30:04,860
siamo stati in grado di seguire abbastanza bene.

363
00:30:04,860 --> 00:30:10,500
Ma tutto quello che dobbiamo fare davvero sicuri di comprendere appieno è il file h.

364
00:30:10,500 --> 00:30:15,840
perché è necessario essere chiamata a queste funzioni, si occupano di quei valori di ritorno,

365
00:30:15,840 --> 00:30:20,590
in modo da assicurarsi di comprendere appieno quale azione sta per essere eseguita

366
00:30:20,590 --> 00:30:24,290
ogni volta che si chiama una di queste funzioni.

367
00:30:24,290 --> 00:30:33,020
Ma in realtà la comprensione all'interno di esso non è assolutamente necessario, perché ci sono quelli. File h.

368
00:30:35,170 --> 00:30:39,490
Abbiamo 2 più file lasciati nel nostro codice di distribuzione.

369
00:30:39,490 --> 00:30:41,640
>> Diamo un'occhiata a discarica.

370
00:30:41,640 --> 00:30:47,230
Dump dal suo commento qui prende un Huffman file compresso

371
00:30:47,230 --> 00:30:55,580
e poi traduce e discariche di tutto il suo contenuto fuori.

372
00:31:01,010 --> 00:31:04,260
Qui vediamo che sta chiamando hfopen.

373
00:31:04,260 --> 00:31:10,770
Questa è una specie di mirroring di file di input * = fopen,

374
00:31:10,770 --> 00:31:13,500
e poi si passa le informazioni.

375
00:31:13,500 --> 00:31:18,240
E 'quasi identico tranne che invece di un file * si sta passando in una Huffile;

376
00:31:18,240 --> 00:31:22,030
invece di fopen si sta passando a hfopen.

377
00:31:22,030 --> 00:31:29,280
Qui si legge nella prima intestazione, che è una specie di simile a come si legge nell'intestazione

378
00:31:29,280 --> 00:31:33,580
per un file bitmap.

379
00:31:33,580 --> 00:31:38,000
Quello che stiamo facendo qui è il controllo per vedere se l'intestazione informazioni

380
00:31:38,000 --> 00:31:44,330
contiene il giusto numero magico che indica che si tratta di un file vero e proprio Huff,

381
00:31:44,330 --> 00:31:53,610
allora tutti questi controlli per assicurarsi che il file che si è aperto un file vero e proprio sbuffò o meno.

382
00:31:53,610 --> 00:32:05,330
Quello che fa è che emette le frequenze di tutti i simboli che possiamo vedere

383
00:32:05,330 --> 00:32:09,790
all'interno di un terminale in una tabella grafica.

384
00:32:09,790 --> 00:32:15,240
Questa parte sarà utile.

385
00:32:15,240 --> 00:32:24,680
Ha un po 'e legge poco a poco nel bit variabile e quindi stampa fuori.

386
00:32:28,220 --> 00:32:35,430
Quindi, se dovessi chiamare dump hth.bin, che è il risultato di sbuffare un file

387
00:32:35,430 --> 00:32:39,490
utilizzando la soluzione personale, vorrei ottenere questo.

388
00:32:39,490 --> 00:32:46,000
E 'uscita di tutti questi personaggi e poi mettere la frequenza con cui compaiono.

389
00:32:46,000 --> 00:32:51,180
Se guardiamo, la maggior parte di loro sono 0s salva questa: H, che appare due volte,

390
00:32:51,180 --> 00:32:54,820
e quindi T, che appare una volta.

391
00:32:54,820 --> 00:33:07,860
E poi qui abbiamo il messaggio attuale in 0 e 1.

392
00:33:07,860 --> 00:33:15,450
Se guardiamo hth.txt, che è presumibilmente il messaggio originale che è stato sbuffò,

393
00:33:15,450 --> 00:33:22,490
ci aspettiamo di vedere un po 'di Hs e Ts in là.

394
00:33:22,490 --> 00:33:28,720
In particolare, ci aspettiamo di vedere solo 1 T e 2 Hs.

395
00:33:32,510 --> 00:33:37,440
Qui siamo in hth.txt. Ha infatti HTH.

396
00:33:37,440 --> 00:33:41,270
Incluso in là, anche se non si vede, è un carattere di nuova riga.

397
00:33:41,270 --> 00:33:53,190
Il hth.bin file di Huff è anche la codifica del carattere di nuova riga pure.

398
00:33:55,680 --> 00:34:01,330
Ecco perché sappiamo che l'ordine è HTH e poi ritorno a capo,

399
00:34:01,330 --> 00:34:07,340
possiamo vedere che probabilmente la H è rappresentato da un solo singolo 1

400
00:34:07,340 --> 00:34:17,120
e quindi la T è probabilmente 01 e quindi il successivo è H 1 nonché

401
00:34:17,120 --> 00:34:21,139
e poi abbiamo una nuova riga indicata da due 0.

402
00:34:22,420 --> 00:34:24,280
Cool.

403
00:34:26,530 --> 00:34:31,600
>> E poi, infine, perché abbiamo a che fare con più. Ce. File h,

404
00:34:31,600 --> 00:34:36,350
stiamo andando ad avere un argomento piuttosto complesso per il compilatore,

405
00:34:36,350 --> 00:34:40,460
e così qui abbiamo un Makefile che fa per voi discarica.

406
00:34:40,460 --> 00:34:47,070
Ma in realtà, si deve fare per rendere il proprio file puff.c.

407
00:34:47,070 --> 00:34:54,330
Il Makefile in realtà non si tratta di fare puff.c per voi.

408
00:34:54,330 --> 00:34:59,310
Stiamo lasciando che fino a di modificare il Makefile.

409
00:34:59,310 --> 00:35:05,930
Quando si immette un comando come fanno tutti, ad esempio, farà tutti per voi.

410
00:35:05,930 --> 00:35:10,760
Sentitevi liberi di guardare gli esempi di Makefile dalla pset passato

411
00:35:10,760 --> 00:35:17,400
così come andare fuori di questo per vedere come si potrebbe essere in grado di rendere il vostro file di Puff

412
00:35:17,400 --> 00:35:20,260
modificando il Makefile.

413
00:35:20,260 --> 00:35:22,730
Questo è tutto per il nostro codice di distribuzione.

414
00:35:22,730 --> 00:35:28,380
>> Una volta che abbiamo ottenuto attraverso quella, allora qui è solo un altro promemoria

415
00:35:28,380 --> 00:35:30,980
di come stiamo andando a che fare con i nodi Huffman.

416
00:35:30,980 --> 00:35:35,400
Non abbiamo intenzione di chiamare loro nodi più; abbiamo intenzione di essere li chiama alberi

417
00:35:35,400 --> 00:35:39,260
dove stiamo andando di rappresentare il loro simbolo con un char,

418
00:35:39,260 --> 00:35:43,340
loro frequenza, il numero di occorrenze, con un numero intero.

419
00:35:43,340 --> 00:35:47,370
Stiamo utilizzando tale perché è più preciso di un galleggiante.

420
00:35:47,370 --> 00:35:52,980
E poi abbiamo un altro puntatore al figlio sinistro e il figlio destro.

421
00:35:52,980 --> 00:35:59,630
Una foresta, come abbiamo visto, è solo una lista concatenata di alberi.

422
00:35:59,630 --> 00:36:04,670
In definitiva, quando stiamo costruendo il nostro file Huff,

423
00:36:04,670 --> 00:36:07,580
vogliamo che la nostra foresta per contenere solo 1 albero -

424
00:36:07,580 --> 00:36:12,420
1 albero, 1 radice con più di un figlio.

425
00:36:12,420 --> 00:36:20,840
In precedenza, quando stavamo facendo i nostri alberi di Huffman,

426
00:36:20,840 --> 00:36:25,360
abbiamo iniziato mettendo tutti i nodi sul nostro schermo

427
00:36:25,360 --> 00:36:27,790
e dire che stiamo andando ad avere questi nodi,

428
00:36:27,790 --> 00:36:32,920
alla fine si sta andando ad essere le foglie, e questo è il loro simbolo, questa è la loro frequenza.

429
00:36:32,920 --> 00:36:42,070
Nella nostra foresta, se dobbiamo solo 3 lettere, che è una foresta di 3 alberi.

430
00:36:42,070 --> 00:36:45,150
E poi come si va avanti, quando abbiamo aggiunto il primo genitore,

431
00:36:45,150 --> 00:36:48,080
abbiamo fatto una foresta di 2 alberi.

432
00:36:48,080 --> 00:36:54,930
Abbiamo rimosso 2 di quei bambini dal nostro bosco e poi lo ha sostituito con un nodo padre

433
00:36:54,930 --> 00:36:58,820
che ha avuto questi 2 nodi come i bambini.

434
00:36:58,820 --> 00:37:05,600
E poi finalmente, il nostro ultimo passo con rendendo il nostro esempio con il nome, B, e Cs

435
00:37:05,600 --> 00:37:08,030
sarebbe rendere il genitore finale,

436
00:37:08,030 --> 00:37:13,190
e così poi che avrebbe portato il nostro numero totale di alberi nella foresta a 1.

437
00:37:13,190 --> 00:37:18,140
Ritiene vedere a tutti come si inizia con più alberi nella foresta

438
00:37:18,140 --> 00:37:22,520
e finire con 1? Va bene. Cool.

439
00:37:25,530 --> 00:37:28,110
>> Che cosa dobbiamo fare per Puff?

440
00:37:28,110 --> 00:37:37,110
Quello che dobbiamo fare è garantire che, come sempre, ci danno il giusto tipo di ingresso

441
00:37:37,110 --> 00:37:39,090
in modo da poter effettivamente eseguire il programma.

442
00:37:39,090 --> 00:37:43,130
In questo caso si sta andando ad essere ci sta dando dopo il loro primo argomento della riga di comando

443
00:37:43,130 --> 00:37:53,440
2 più: il file che vogliamo decomprimere e l'output del file decompresso.

444
00:37:53,440 --> 00:38:00,410
Ma una volta che ci assicuriamo che ci passano la giusta quantità di valori,

445
00:38:00,410 --> 00:38:05,820
vogliamo garantire che l'input è un file Huff o meno.

446
00:38:05,820 --> 00:38:10,420
E poi una volta vi possiamo garantire che si tratta di un file di Huff, quindi vogliamo costruire il nostro albero,

447
00:38:10,420 --> 00:38:20,940
costruire l'albero in modo che corrisponda l'albero che la persona che ha inviato il messaggio costruito.

448
00:38:20,940 --> 00:38:25,840
Poi, dopo che costruire l'albero, allora possiamo affrontare il, 0 e 1, che hanno superato in

449
00:38:25,840 --> 00:38:29,590
seguono quelli lungo il nostro albero perché è identico,

450
00:38:29,590 --> 00:38:33,510
e poi scrivere quel messaggio, interpretare i bit di nuovo in caratteri.

451
00:38:33,510 --> 00:38:35,880
E poi alla fine, perché abbiamo a che fare con i puntatori qui,

452
00:38:35,880 --> 00:38:38,110
si vuole fare in modo che non ci sono perdite di memoria

453
00:38:38,110 --> 00:38:41,330
e che tutto gratis.

454
00:38:42,820 --> 00:38:46,430
>> Assicurare un corretto utilizzo è vecchio cappello per noi ormai.

455
00:38:46,430 --> 00:38:51,980
Prendiamo in un ingresso, che sarà il nome del file a sbuffare,

456
00:38:51,980 --> 00:38:56,010
e poi specificare un output,

457
00:38:56,010 --> 00:39:01,580
quindi il nome del file per l'output soffiato, che sarà il file di testo.

458
00:39:03,680 --> 00:39:08,820
Questo è il loro utilizzo. E ora vogliamo garantire che l'ingresso è sbuffò o meno.

459
00:39:08,820 --> 00:39:16,420
Ripensandoci, c'era qualcosa nel codice di distribuzione che potrebbe aiutarci

460
00:39:16,420 --> 00:39:21,570
con la comprensione se un file è sbuffò o no?

461
00:39:21,570 --> 00:39:26,910
C'era informazioni huffile.c sulla Huffeader.

462
00:39:26,910 --> 00:39:33,430
Sappiamo che ogni file Huff ha un Huffeader associato con un numero magico

463
00:39:33,430 --> 00:39:37,240
nonché una serie di frequenze per ogni simbolo

464
00:39:37,240 --> 00:39:39,570
nonché una checksum.

465
00:39:39,570 --> 00:39:43,180
Sappiamo che, ma abbiamo anche preso una sbirciatina al dump.c,

466
00:39:43,180 --> 00:39:49,120
in cui si leggeva in un file Huff.

467
00:39:49,120 --> 00:39:53,990
E così, per farlo, doveva verificare se davvero è stato sbuffò o meno.

468
00:39:53,990 --> 00:40:03,380
Quindi, forse, potremmo usare dump.c come una struttura per il nostro puff.c.

469
00:40:03,380 --> 00:40:12,680
Torna a pset 4 quando abbiamo avuto la copy.c file copiato in triple RGB

470
00:40:12,680 --> 00:40:14,860
e abbiamo interpretato che per Whodunit e ridimensionamento,

471
00:40:14,860 --> 00:40:20,390
allo stesso modo, quello che si potrebbe fare è semplicemente eseguire il comando come cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
e utilizzare parte del codice lì.

473
00:40:23,600 --> 00:40:28,210
Tuttavia, non sarà così semplice di un processo

474
00:40:28,210 --> 00:40:33,010
per tradurre il vostro dump.c in puff.c,

475
00:40:33,010 --> 00:40:36,160
ma almeno ti dà qualche parte per iniziare

476
00:40:36,160 --> 00:40:40,540
su come garantire che l'ingresso è effettivamente sbuffò o meno

477
00:40:40,540 --> 00:40:43,240
così come alcune altre cose.

478
00:40:45,930 --> 00:40:50,250
Abbiamo assicurato un corretto utilizzo e ha assicurato che l'ingresso è sbuffò.

479
00:40:50,250 --> 00:40:53,570
Ogni volta che abbiamo fatto, che abbiamo fatto il nostro controllo proprio errore,

480
00:40:53,570 --> 00:41:01,520
così tornare e uscire dalla funzione se qualche errore, se c'è un problema.

481
00:41:01,520 --> 00:41:07,170
>> Ora, quello che vogliamo fare è costruire l'albero vero e proprio.

482
00:41:08,840 --> 00:41:12,640
Se guardiamo nella foresta, ci sono 2 funzioni principali

483
00:41:12,640 --> 00:41:15,800
che stiamo andando a voler diventare molto familiare.

484
00:41:15,800 --> 00:41:23,870
C'è l'impianto funzione booleana che le piante di un non-0 albero di frequenza all'interno della nostra foresta.

485
00:41:23,870 --> 00:41:29,250
E così ci si passa un puntatore a un bosco e un puntatore a un albero.

486
00:41:32,530 --> 00:41:40,340
Domanda veloce: Quante foreste che si ha quando si sta costruendo un albero di Huffman?

487
00:41:44,210 --> 00:41:46,650
La nostra foresta è come la nostra tela, giusto?

488
00:41:46,650 --> 00:41:50,800
Quindi stiamo solo andando avere 1 foresta, ma abbiamo intenzione di avere più alberi.

489
00:41:50,800 --> 00:41:57,590
Quindi, prima di chiamare pianta, si sta probabilmente andando a voler rendere la vostra foresta.

490
00:41:57,590 --> 00:42:04,430
C'è un comando per che, se si guarda in forest.h su come si può fare una foresta.

491
00:42:04,430 --> 00:42:09,270
Si può piantare un albero. Noi sappiamo come farlo.

492
00:42:09,270 --> 00:42:11,590
E allora si può anche scegliere un albero dal bosco,

493
00:42:11,590 --> 00:42:17,540
la rimozione di un albero con il minor peso e dando il puntatore a questo.

494
00:42:17,540 --> 00:42:23,090
Pensi a quando stavamo facendo gli esempi noi stessi,

495
00:42:23,090 --> 00:42:27,980
quando stavamo tirando fuori, abbiamo semplicemente aggiunto i link.

496
00:42:27,980 --> 00:42:31,680
Ma qui invece di aggiungere i link,

497
00:42:31,680 --> 00:42:40,630
pensare più come si sta rimuovendo 2 di quei nodi e poi sostituirlo con un altro.

498
00:42:40,630 --> 00:42:44,200
Per esprimere che in termini di raccolta e impianto,

499
00:42:44,200 --> 00:42:48,840
si sta raccogliendo 2 alberi e poi piantare un altro albero

500
00:42:48,840 --> 00:42:54,060
che ha quei 2 alberi che avete raccolto da bambini.

501
00:42:57,950 --> 00:43:05,280
Per costruire albero di Huffman, è possibile leggere i simboli e le frequenze in ordine

502
00:43:05,280 --> 00:43:10,790
perché il Huffeader che dà a voi,

503
00:43:10,790 --> 00:43:14,250
ti dà una vasta gamma di frequenze.

504
00:43:14,250 --> 00:43:19,660
Così si può andare avanti e ignorare qualsiasi cosa con lo 0 in esso

505
00:43:19,660 --> 00:43:23,760
perché non vogliamo 256 foglie alla fine di esso.

506
00:43:23,760 --> 00:43:27,960
Noi vogliamo solo il numero di fogli che sono i caratteri

507
00:43:27,960 --> 00:43:31,600
che vengono effettivamente utilizzati nel file.

508
00:43:31,600 --> 00:43:37,590
È possibile leggere in tali simboli, e ciascuno di questi simboli che hanno frequenze non-0,

509
00:43:37,590 --> 00:43:40,440
coloro che stanno per essere alberi.

510
00:43:40,440 --> 00:43:45,990
Che cosa si può fare ogni volta che si è letto in un non-0 frequenza di simbolo,

511
00:43:45,990 --> 00:43:50,660
è possibile piantare quell'albero nel bosco.

512
00:43:50,660 --> 00:43:56,620
Una volta che piantare gli alberi della foresta, si può aderire quegli alberi come fratelli,

513
00:43:56,620 --> 00:44:01,130
così tornare a piantare e raccogliere in cui si sceglie 2 e poi impianto 1,

514
00:44:01,130 --> 00:44:05,820
dove che 1 che si pianta è il padre dei 2 bambini che hai scelto.

515
00:44:05,820 --> 00:44:11,160
Quindi il risultato finale sarà un unico albero nella foresta.

516
00:44:16,180 --> 00:44:18,170
Ecco come si costruisce l'albero.

517
00:44:18,170 --> 00:44:21,850
>> Ci sono diverse cose che potrebbero andare male qui

518
00:44:21,850 --> 00:44:26,580
perché abbiamo a che fare con fare nuovi alberi e trattare con puntatori e cose del genere.

519
00:44:26,580 --> 00:44:30,450
Prima, quando avevamo a che fare con i puntatori,

520
00:44:30,450 --> 00:44:36,580
ogni volta che malloc'd abbiamo voluto fare in modo che non ci ha restituito un valore NULL pointer.

521
00:44:36,580 --> 00:44:42,770
Quindi, a diversi passi all'interno di questo processo ci saranno diversi casi

522
00:44:42,770 --> 00:44:45,920
in cui il programma potrebbe fallire.

523
00:44:45,920 --> 00:44:51,310
Che cosa si vuole fare è che si vuole fare in modo che gestire tali errori,

524
00:44:51,310 --> 00:44:54,580
e nelle specifiche dice di gestirli con grazia,

525
00:44:54,580 --> 00:45:00,280
così come stampare un messaggio all'utente dicendo loro motivo per cui il programma deve uscire

526
00:45:00,280 --> 00:45:03,050
e poi prontamente uscire.

527
00:45:03,050 --> 00:45:09,490
Per fare questo la gestione degli errori, si ricordi che si desidera controllare

528
00:45:09,490 --> 00:45:12,160
ogni volta che ci potrebbe essere un guasto.

529
00:45:12,160 --> 00:45:14,660
Ogni volta che si sta facendo un nuovo puntatore

530
00:45:14,660 --> 00:45:17,040
si vuole fare in modo che questo è successo.

531
00:45:17,040 --> 00:45:20,320
La prima cosa che abbiamo usato per fare è effettuare un nuovo puntatore e lo malloc,

532
00:45:20,320 --> 00:45:22,380
e poi ci sarebbe verificare se tale puntatore è NULL.

533
00:45:22,380 --> 00:45:25,670
Quindi ci saranno alcuni casi in cui si può solo farlo,

534
00:45:25,670 --> 00:45:28,610
ma a volte si sta effettivamente chiamando una funzione

535
00:45:28,610 --> 00:45:33,100
e all'interno di tale funzione, che è quello che sta facendo il mallocing.

536
00:45:33,100 --> 00:45:39,110
In tal caso, se guardiamo indietro ad alcune delle funzioni all'interno del codice,

537
00:45:39,110 --> 00:45:42,260
alcuni di loro sono funzioni booleane.

538
00:45:42,260 --> 00:45:48,480
Nel caso in astratto se abbiamo una funzione booleana chiamata foo,

539
00:45:48,480 --> 00:45:54,580
in fondo, si può supporre che, oltre a fare tutto ciò che fa pippo,

540
00:45:54,580 --> 00:45:57,210
dal momento che è una funzione booleana, restituisce vero o falso -

541
00:45:57,210 --> 00:46:01,300
vero se ha successo, false in caso contrario.

542
00:46:01,300 --> 00:46:06,270
Quindi, vogliamo verificare se il valore di ritorno di foo è vera o falsa.

543
00:46:06,270 --> 00:46:10,400
Se è falso, il che significa che stiamo andando a voler stampare un qualche tipo di messaggio

544
00:46:10,400 --> 00:46:14,390
e quindi chiudere il programma.

545
00:46:14,390 --> 00:46:18,530
Quello che vogliamo fare è controllare il valore di ritorno di foo.

546
00:46:18,530 --> 00:46:23,310
Se foo restituisce false, allora sappiamo che abbiamo incontrato qualche tipo di errore

547
00:46:23,310 --> 00:46:25,110
e abbiamo bisogno di chiudere il nostro programma.

548
00:46:25,110 --> 00:46:35,600
Un modo per farlo è avere una condizione in cui la funzione di vero e proprio è la sua condizione.

549
00:46:35,600 --> 00:46:39,320
Dire foo prende in x.

550
00:46:39,320 --> 00:46:43,390
Possiamo avere come condizione if (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Fondamentalmente, significa che se alla fine di eseguire foo restituisce vero,

552
00:46:50,900 --> 00:46:57,390
allora si può fare questo perché la funzione deve valutare foo

553
00:46:57,390 --> 00:47:00,500
al fine di valutare la condizione intero.

554
00:47:00,500 --> 00:47:06,500
Allora è così che si può fare qualcosa se la funzione restituisce true e ha successo.

555
00:47:06,500 --> 00:47:11,800
Ma quando si è il controllo degli errori, si desidera solo uscire se la funzione restituisce false.

556
00:47:11,800 --> 00:47:16,090
Che cosa si potrebbe fare è aggiungere un == false o semplicemente aggiungere un botto di fronte ad essa

557
00:47:16,090 --> 00:47:21,010
e poi ci sono if (! foo).

558
00:47:21,010 --> 00:47:29,540
All'interno di quel corpo di tale condizione si avrebbe tutta la gestione degli errori,

559
00:47:29,540 --> 00:47:36,940
così come, "Impossibile creare questo albero" e poi tornare 1 o qualcosa del genere.

560
00:47:36,940 --> 00:47:43,340
Cosa che fa, però, è che anche se pippo ha restituito false -

561
00:47:43,340 --> 00:47:46,980
Dire foo restituisce true.

562
00:47:46,980 --> 00:47:51,060
Allora non c'è bisogno di chiamare foo nuovo. Questo è un errore comune.

563
00:47:51,060 --> 00:47:54,730
Perché era nelle tue condizioni, è già valutata,

564
00:47:54,730 --> 00:47:59,430
così hai già il risultato se si sta usando make albero o qualcosa del genere

565
00:47:59,430 --> 00:48:01,840
o di un impianto o di ritiro o qualcosa del genere.

566
00:48:01,840 --> 00:48:07,460
Ha già quel valore. E 'già eseguito.

567
00:48:07,460 --> 00:48:10,730
Quindi è utile utilizzare le funzioni booleane come condizione

568
00:48:10,730 --> 00:48:13,890
perché se realmente eseguito il corpo del ciclo,

569
00:48:13,890 --> 00:48:18,030
esegue la funzione comunque.

570
00:48:22,070 --> 00:48:27,330
>> Il nostro secondo per ultimo passo è scrivere il messaggio nel file.

571
00:48:27,330 --> 00:48:33,070
Una volta che si costruisce l'albero di Huffman, quindi scrivere il messaggio nel file è abbastanza semplice.

572
00:48:33,070 --> 00:48:39,260
E 'abbastanza semplice per seguire solo la 0 e 1.

573
00:48:39,260 --> 00:48:45,480
E così, per convenzione, si sa che in un albero di Huffman le 0s indicano a sinistra

574
00:48:45,480 --> 00:48:48,360
e gli 1 indicano a destra.

575
00:48:48,360 --> 00:48:53,540
E allora se si leggono in poco a poco, ogni volta che si ottiene uno 0

576
00:48:53,540 --> 00:48:59,100
si segue il ramo di sinistra, e quindi ogni volta che si legge in un 1

577
00:48:59,100 --> 00:49:02,100
avete intenzione di seguire il ramo di destra.

578
00:49:02,100 --> 00:49:07,570
E poi avete intenzione di continuare fino a colpire una foglia

579
00:49:07,570 --> 00:49:11,550
perché le foglie stanno per essere alla fine dei rami.

580
00:49:11,550 --> 00:49:16,870
Come possiamo sapere se abbiamo colpito una foglia o no?

581
00:49:19,800 --> 00:49:21,690
L'abbiamo detto prima.

582
00:49:21,690 --> 00:49:24,040
[Studente] Se i puntatori sono NULL. Sì >>.

583
00:49:24,040 --> 00:49:32,220
Siamo in grado di dire se abbiamo colpito una foglia se i puntatori agli alberi sia di sinistra e destra sono NULL.

584
00:49:32,220 --> 00:49:34,110
Perfetto.

585
00:49:34,110 --> 00:49:40,320
Sappiamo che si desidera leggere a poco a poco nel nostro file di Huff.

586
00:49:43,870 --> 00:49:51,220
Come abbiamo visto prima in dump.c, quello che hanno fatto è che leggono poco a poco nel file Huff

587
00:49:51,220 --> 00:49:54,560
e appena stampata che cosa fossero quei bit.

588
00:49:54,560 --> 00:49:58,430
Non abbiamo intenzione di fare questo. Stiamo andando a fare qualcosa che è un po 'più complessa.

589
00:49:58,430 --> 00:50:03,620
Ma quello che possiamo fare è che possiamo prendere quel po 'di codice che legge al bit.

590
00:50:03,620 --> 00:50:10,250
Qui abbiamo il bit numero intero che rappresenta il bit corrente che siamo sulla.

591
00:50:10,250 --> 00:50:15,520
Questo si occupa di scorrere tutti i bit nel file fino a colpire la fine del file.

592
00:50:15,520 --> 00:50:21,270
Sulla base di questo, allora si sta andando a voler avere un qualche tipo di iteratore

593
00:50:21,270 --> 00:50:26,760
per attraversare il vostro albero.

594
00:50:26,760 --> 00:50:31,460
E quindi a seconda che il bit è 0 o 1,

595
00:50:31,460 --> 00:50:36,920
si sta andando a voler spostare o che iteratore a sinistra o spostare verso destra

596
00:50:36,920 --> 00:50:44,080
tutta la strada fino a quando si colpisce una foglia, per cui tutta la strada fino a quel nodo che si è in

597
00:50:44,080 --> 00:50:48,260
non puntare ai nodi più.

598
00:50:48,260 --> 00:50:54,300
Perché possiamo fare questo con un file di Huffman, ma non il codice Morse?

599
00:50:54,300 --> 00:50:56,610
Perché in codice Morse c'è un po 'di ambiguità.

600
00:50:56,610 --> 00:51:04,440
Potremmo essere come, oh attesa, abbiamo colpito una lettera lungo la strada, quindi forse questa è la nostra lettera,

601
00:51:04,440 --> 00:51:08,150
mentre se abbiamo continuato solo un po 'di più, poi ci avrebbe colpito un'altra lettera.

602
00:51:08,150 --> 00:51:13,110
Ma questo non succederà nella codifica Huffman,

603
00:51:13,110 --> 00:51:17,540
in modo che possiamo stare tranquilli che l'unico modo che stiamo andando a colpire un personaggio

604
00:51:17,540 --> 00:51:23,480
è se i bambini a destra ea sinistra di quel nodo sono NULL.

605
00:51:28,280 --> 00:51:32,350
>> Infine, vogliamo liberare tutta la nostra memoria.

606
00:51:32,350 --> 00:51:37,420
Vogliamo sia vicino il file Huff che abbiamo avuto a che fare con

607
00:51:37,420 --> 00:51:41,940
così come rimuovere tutti gli alberi della nostra foresta.

608
00:51:41,940 --> 00:51:46,470
Sulla base della sua implementazione, probabilmente stai andando a voler chiamare rimuovere foresta

609
00:51:46,470 --> 00:51:49,780
invece di realtà passa attraverso tutti i voi stessi alberi.

610
00:51:49,780 --> 00:51:53,430
Ma se hai fatto di alberi temporanei, ti consigliamo di liberare questo.

611
00:51:53,430 --> 00:51:59,060
Tu conosci il tuo codice migliore, in modo da sapere dove si sta allocazione di memoria.

612
00:51:59,060 --> 00:52:04,330
E quindi se si va, si fa partire anche da controllo f'ing per malloc,

613
00:52:04,330 --> 00:52:08,330
vedendo ogni volta che si malloc e fare in modo che liberano tutto questo

614
00:52:08,330 --> 00:52:10,190
ma poi basta passare attraverso il codice,

615
00:52:10,190 --> 00:52:14,260
capire dove si potrebbe avere memoria allocata.

616
00:52:14,260 --> 00:52:21,340
Di solito si può solo dire: "Alla fine di un file Sto solo andando a rimuovere foresta sulla mia foresta,"

617
00:52:21,340 --> 00:52:23,850
quindi fondamentalmente chiaro che la memoria, gratuito che,

618
00:52:23,850 --> 00:52:28,310
"E poi ho anche intenzione di chiudere il file e quindi il mio programma sta per uscire."

619
00:52:28,310 --> 00:52:33,810
Ma è l'unica volta che il programma si chiude?

620
00:52:33,810 --> 00:52:37,880
No, perché a volte ci potrebbe essere stato un errore quello che è successo.

621
00:52:37,880 --> 00:52:42,080
Forse non abbiamo potuto aprire un file o non siamo riusciti a fare un altro albero

622
00:52:42,080 --> 00:52:49,340
o un qualche tipo di errore è accaduto nel processo di allocazione di memoria e così ha restituito NULL.

623
00:52:49,340 --> 00:52:56,710
Un errore è accaduto e poi siamo tornati e uscire.

624
00:52:56,710 --> 00:53:02,040
Allora si vuole fare in modo che ogni volta che possibile che il programma può uscire,

625
00:53:02,040 --> 00:53:06,980
si vuole liberare tutta la memoria lì.

626
00:53:06,980 --> 00:53:13,370
Non è solo sarà alla fine della funzione principale che si chiude il codice.

627
00:53:13,370 --> 00:53:20,780
Si vuole guardare indietro a ogni istanza che il codice potenzialmente potrebbe restituire prematuramente

628
00:53:20,780 --> 00:53:25,070
e quindi tutto ciò che libera la memoria ha un senso.

629
00:53:25,070 --> 00:53:30,830
Diciamo che aveva chiamato fare foresta e che ha restituito false.

630
00:53:30,830 --> 00:53:34,230
Allora probabilmente non sarà necessario rimuovere l'insieme di strutture

631
00:53:34,230 --> 00:53:37,080
perché non si dispone di una foresta ancora.

632
00:53:37,080 --> 00:53:42,130
Ma, in ogni punto del codice in cui si potrebbe tornare prematuramente

633
00:53:42,130 --> 00:53:46,160
si vuole fare in modo che liberano la memoria possibile.

634
00:53:46,160 --> 00:53:50,020
>> Così, quando abbiamo a che fare con la liberazione della memoria e con perdite potenziali,

635
00:53:50,020 --> 00:53:55,440
si desidera utilizzare non solo il nostro giudizio e la nostra logica

636
00:53:55,440 --> 00:54:01,850
ma anche utilizzare Valgrind per determinare se abbiamo liberato tutti della nostra memoria correttamente o meno.

637
00:54:01,850 --> 00:54:09,460
È possibile eseguire Valgrind sulla sfoglia e poi si deve anche passare

638
00:54:09,460 --> 00:54:14,020
il giusto numero di riga di comando argomenti Valgrind.

639
00:54:14,020 --> 00:54:18,100
È possibile eseguire, ma l'uscita è un po 'criptico.

640
00:54:18,100 --> 00:54:21,630
Abbiamo ottenuto un po 'l'abitudine con correttore ortografico, ma abbiamo ancora bisogno di aiuto un po' di più,

641
00:54:21,630 --> 00:54:26,450
così allora in esecuzione con alcune bandiere più come la perdita-check = pieno,

642
00:54:26,450 --> 00:54:32,040
che probabilmente ci darà un output più disponibile su Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Poi un altro suggerimento utile per il debug è il comando diff.

644
00:54:39,040 --> 00:54:48,520
È possibile accedere implementazione del personale di Huff, eseguire che in un file di testo,

645
00:54:48,520 --> 00:54:55,400
e poi l'output in un file binario, un file binario Huff, per essere precisi.

646
00:54:55,400 --> 00:54:59,440
Poi, se si esegue il tuo soffio proprio su quel file binario,

647
00:54:59,440 --> 00:55:03,950
poi idealmente, il file di testo in output sarà identico

648
00:55:03,950 --> 00:55:08,200
a quello originale che avete passato trovi

649
00:55:08,200 --> 00:55:15,150
Qui sto usando hth.txt come esempio, e questo è quello parlato nelle specifiche.

650
00:55:15,150 --> 00:55:21,040
Questo è letteralmente HTH e poi un ritorno a capo.

651
00:55:21,040 --> 00:55:30,970
Ma sicuramente sentire liberi e vi sono sicuramente incoraggiati ad usare gli esempi più

652
00:55:30,970 --> 00:55:32,620
per il file di testo.

653
00:55:32,620 --> 00:55:38,110
>> Si può anche prendere un colpo a forse la compressione e la decompressione poi

654
00:55:38,110 --> 00:55:41,600
alcuni dei file che avete usato per Speller come Guerra e pace

655
00:55:41,600 --> 00:55:46,710
o Jane Austen o qualcosa del genere - che sarebbe un po 'freddo - o di Austin Powers,

656
00:55:46,710 --> 00:55:51,880
tipo di trattare con file di grandi dimensioni, perché non sarebbe venuto al dunque

657
00:55:51,880 --> 00:55:55,590
se abbiamo utilizzato lo strumento successivo qui, ls-l.

658
00:55:55,590 --> 00:56:01,150
Siamo abituati a ls, che elenca in pratica tutti i contenuti nella nostra directory corrente.

659
00:56:01,150 --> 00:56:07,860
Passando il flag-l visualizza effettivamente le dimensioni di tali file.

660
00:56:07,860 --> 00:56:12,690
Se si passa attraverso la specifica pset, cammina in realtà l'utente attraverso la creazione del file binario,

661
00:56:12,690 --> 00:56:16,590
di sbuffare, e si vede che per i file molto piccoli

662
00:56:16,590 --> 00:56:23,910
il costo dello spazio di compressione e tradurre tutte le informazioni

663
00:56:23,910 --> 00:56:26,980
di tutte le frequenze e cose del genere è superiore ai benefici effettivi

664
00:56:26,980 --> 00:56:30,000
di comprimere il file in primo luogo.

665
00:56:30,000 --> 00:56:37,450
Ma se lo si esegue su alcuni file di testo più lunghi, allora si potrebbe vedere che si inizia ad avere qualche beneficio

666
00:56:37,450 --> 00:56:40,930
nel comprimere tali file.

667
00:56:40,930 --> 00:56:46,210
>> E poi finalmente, abbiamo la nostra GDB vecchio amico, che è sicuramente di tornare utile anche.

668
00:56:48,360 --> 00:56:55,320
>> Abbiamo qualche domanda sugli alberi Huff o il processo forse di fare gli alberi

669
00:56:55,320 --> 00:56:58,590
o qualsiasi altra domanda su Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Va bene. Starò in giro per un po '.

671
00:57:02,570 --> 00:57:06,570
>> Grazie a tutti. Questo era Walkthrough 6. E buona fortuna.

672
00:57:08,660 --> 00:57:10,000
>> [CS50.TV]