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

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

3
00:00:04,810 --> 00:00:07,240
[Acest lucru este CS50. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> Bună ziua, tuturor, si bun venit la Walkthrough 6: Huff'n Puff.

5
00:00:12,180 --> 00:00:17,440
În Puff Huff'n ceea ce facem va fi de-a face cu un fișier comprimat Huffman

6
00:00:17,440 --> 00:00:20,740
și apoi puffing-l înapoi, așa că decompressing,

7
00:00:20,740 --> 00:00:25,810
astfel încât să putem traduce din 0s și 1s că utilizatorul trimite-ne

8
00:00:25,810 --> 00:00:30,660
și ao transforma înapoi în textul original.

9
00:00:30,660 --> 00:00:34,360
PSET 6 se va fi destul de cool pentru că ai de gând pentru a vedea unele dintre instrumentele

10
00:00:34,360 --> 00:00:41,730
pe care ați utilizat în PSET 4 și 5 și PSET un fel de a le combina într-un concept destul de elegant

11
00:00:41,730 --> 00:00:43,830
atunci când vin să te gândești la asta.

12
00:00:43,830 --> 00:00:50,110
>> De asemenea, fără îndoială, PSET 4 și 5 au fost cele mai dificile pe care psets am avut de oferit.

13
00:00:50,110 --> 00:00:53,950
Deci, de acum, avem această PSET 1 mai mult în C,

14
00:00:53,950 --> 00:00:56,480
și apoi după că suntem pe programare web.

15
00:00:56,480 --> 00:01:02,310
Deci, vă felicit pentru obtinerea peste cele mai dificile bizon în CS50.

16
00:01:03,630 --> 00:01:09,760
>> Mutarea de pe Puff pentru Huff'n, set de instrumente nostru pentru acest PSET vor fi copaci Huffman,

17
00:01:09,760 --> 00:01:14,700
astfel încât înțelegerea nu numai modul de lucru binar copaci, dar, de asemenea, în special arbori Huffman,

18
00:01:14,700 --> 00:01:16,240
modul în care sunt construite.

19
00:01:16,240 --> 00:01:20,210
Și apoi vom avea o mulțime de cod de distribuție în acest PSET,

20
00:01:20,210 --> 00:01:22,480
și vom veni să vedem că de fapt, o parte din codul

21
00:01:22,480 --> 00:01:24,670
noi nu ar putea fi capabil să înțeleagă pe deplin încă,

22
00:01:24,670 --> 00:01:30,080
și astfel cei care vor fi fișierele. c, dar apoi își însoțesc h fișiere.

23
00:01:30,080 --> 00:01:34,300
ne va da suficient de înțelegere de care avem nevoie, astfel încât să știm cum funcționează aceste funcții

24
00:01:34,300 --> 00:01:38,100
sau cel puțin ceea ce ar trebui să facă - intrări și ieșiri ale acestora -

25
00:01:38,100 --> 00:01:40,760
chiar dacă nu știm ce se întâmplă în cutia neagră

26
00:01:40,760 --> 00:01:44,090
sau nu înțeleg ce se întâmplă în cutia neagră în termen de.

27
00:01:44,090 --> 00:01:49,400
Și apoi în cele din urmă, ca de obicei, avem de-a face cu structuri de date noi,

28
00:01:49,400 --> 00:01:51,840
anumite tipuri de noduri care indica anumite lucruri,

29
00:01:51,840 --> 00:01:56,080
și astfel avem aici un creion și hârtie, nu numai pentru procesul de proiectare

30
00:01:56,080 --> 00:01:58,470
și atunci când sunteți încercarea de a seama cum PSET ta ar trebui să funcționeze

31
00:01:58,470 --> 00:02:00,520
dar, de asemenea, în timpul de depanare.

32
00:02:00,520 --> 00:02:06,140
Puteți avea GDB alături de creion și o hârtie în timp ce ia în jos ce valorile sunt,

33
00:02:06,140 --> 00:02:09,320
în cazul în care săgețile tale sunt orientate, și lucruri de genul asta.

34
00:02:09,320 --> 00:02:13,720
>> În primul rând să ne uităm la copaci Huffman.

35
00:02:13,720 --> 00:02:19,600
Arbori Huffman sunt arbori binari, ceea ce înseamnă că fiecare nod are doar 2 copii.

36
00:02:19,600 --> 00:02:24,870
În copaci Huffman caracteristică este că valorile cele mai frecvente

37
00:02:24,870 --> 00:02:27,140
sunt reprezentate de cele mai putine biți.

38
00:02:27,140 --> 00:02:32,690
Am văzut în exemplele de curs de codul Morse, ce fel de consolidat niște scrisori.

39
00:02:32,690 --> 00:02:38,030
Dacă sunteți încercarea de a traduce un A sau un E, de exemplu,

40
00:02:38,030 --> 00:02:43,940
te traducerea că de multe ori, astfel încât în ​​loc de a avea pentru a utiliza un set complet de biți

41
00:02:43,940 --> 00:02:48,640
alocate pentru acel tip de date de obicei, îl comprimați până la mai puține,

42
00:02:48,640 --> 00:02:53,730
și apoi aceste scrisori, care sunt reprezentate mai multe ori sunt reprezentate cu biți mai lungi

43
00:02:53,730 --> 00:02:59,840
pentru că vă puteți permite ca, atunci când se cântăresc frecvențele că aceste scrisori apar.

44
00:02:59,840 --> 00:03:03,020
Avem aceeași idee aici, în copaci Huffman

45
00:03:03,020 --> 00:03:12,360
în cazul în care facem un lanț, un fel de cale pentru a ajunge la anumite personaje.

46
00:03:12,360 --> 00:03:14,470
Și apoi personajele care au cea mai mare frecvență

47
00:03:14,470 --> 00:03:17,940
vor fi reprezentate cu cele mai putine biți.

48
00:03:17,940 --> 00:03:22,020
>> Modul în care vă construi un copac Huffman

49
00:03:22,020 --> 00:03:27,430
este prin plasarea dintre toate personajele care apar în text

50
00:03:27,430 --> 00:03:30,630
și calcularea frecvenței lor, cât de des acestea apar.

51
00:03:30,630 --> 00:03:33,880
Acest lucru ar putea fi un număr de câte ori apar aceste scrisori

52
00:03:33,880 --> 00:03:40,270
sau poate un procent de din toate personajele câte fiecare dintre apare.

53
00:03:40,270 --> 00:03:44,270
Și astfel ceea ce faci este o dată aveți toate că afară cartografiate,

54
00:03:44,270 --> 00:03:49,060
Apoi te uiți pentru frecvențele mai mici 2 și apoi li se alăture ca frații

55
00:03:49,060 --> 00:03:55,660
în cazul în care, atunci nodul părinte are o frecvență care este suma sale 2 copii.

56
00:03:55,660 --> 00:04:00,870
Și apoi, prin convenție, spune că din stânga nod,

57
00:04:00,870 --> 00:04:03,770
urmați de faptul că în urma ramura 0,

58
00:04:03,770 --> 00:04:08,140
și apoi nodul din dreapta este ramura 1.

59
00:04:08,140 --> 00:04:16,040
Așa cum am văzut în codul Morse, unul a fost prins că, dacă ați avut doar un bip bip și

60
00:04:16,040 --> 00:04:18,120
a fost ambiguă.

61
00:04:18,120 --> 00:04:22,430
S-ar putea să fie o literă sau ar putea fi o secvență de 2 litere.

62
00:04:22,430 --> 00:04:27,790
Și ce face este Huffman copaci, deoarece prin natura personajelor

63
00:04:27,790 --> 00:04:34,140
sau noastre finale de caractere reale fiind nodurile de pe ultimele ramura -

64
00:04:34,140 --> 00:04:39,300
ne referim la cele cum frunzele - în virtutea că nu poate exista nici o ambiguitate

65
00:04:39,300 --> 00:04:45,160
în funcție de care scrisorii pe care încercați să codifica cu seria de biți

66
00:04:45,160 --> 00:04:50,670
deoarece nicăieri de-a lungul biți care reprezintă 1 literă

67
00:04:50,670 --> 00:04:55,960
te va întâlni o altă scrisoare întreg, și nu va fi nici o confuzie acolo.

68
00:04:55,960 --> 00:04:58,430
Dar noi vom merge în exemple pe care voi poate vedea de fapt, că

69
00:04:58,430 --> 00:05:02,120
în loc de noi doar vă spun că e adevărat.

70
00:05:02,120 --> 00:05:06,390
>> Să ne uităm la un exemplu simplu de un copac Huffman.

71
00:05:06,390 --> 00:05:09,380
Am un șir de aici, care este de 12 caractere.

72
00:05:09,380 --> 00:05:14,010
Am 4 Ca, 6 B, C și 2.

73
00:05:14,010 --> 00:05:17,270
Primul meu pas ar fi să număr.

74
00:05:17,270 --> 00:05:20,760
Cum de multe ori nu o sa apara? Se pare de 4 ori în șir.

75
00:05:20,760 --> 00:05:25,060
B apare de 6 ori, și C apare de 2 ori.

76
00:05:25,060 --> 00:05:28,970
Firește, am de gând să spun eu sunt, folosind B cele mai multe ori,

77
00:05:28,970 --> 00:05:35,970
așa că am dori să reprezinte B cu cel mai mic număr de biți, cel mai mic număr de 0s și 1s.

78
00:05:35,970 --> 00:05:42,600
Și apoi, de asemenea, am de gând să aștepte C a solicita mai cantitatea de 0s și 1s, de asemenea.

79
00:05:42,600 --> 00:05:48,550
În primul rând ceea ce am făcut aici este le-am plasat în ordine crescătoare, în ceea ce privește frecvența.

80
00:05:48,550 --> 00:05:52,710
Vedem că C și A, acestea sunt cele 2 cele mai mici frecvențe.

81
00:05:52,710 --> 00:06:00,290
Vom crea un nod părinte, și că nodul părinte nu are o scrisoare de asociat cu acesta,

82
00:06:00,290 --> 00:06:05,070
dar ea are o frecvență, care este suma.

83
00:06:05,070 --> 00:06:08,780
Suma devine 2 + 4, care este de 6.

84
00:06:08,780 --> 00:06:10,800
Apoi urmăm ramura stanga.

85
00:06:10,800 --> 00:06:14,970
Dacă am fost la acel nod 6, atunci ne-ar urma pentru a ajunge la 0 C

86
00:06:14,970 --> 00:06:17,450
și apoi 1 pentru a obține la A.

87
00:06:17,450 --> 00:06:20,300
Deci acum avem 2 noduri.

88
00:06:20,300 --> 00:06:23,920
Avem valoare 6 și apoi ne-am, de asemenea, un alt nod cu valoarea 6.

89
00:06:23,920 --> 00:06:28,550
Și astfel cei doi nu sunt doar mai mic, dar, de asemenea, la doar 2 2 care au rămas,

90
00:06:28,550 --> 00:06:33,820
asa ne alăturăm celor de un alt părinte, cu suma fiind de 12.

91
00:06:33,820 --> 00:06:36,300
Deci, aici avem copacul nostru Huffman

92
00:06:36,300 --> 00:06:40,020
în cazul în care pentru a ajunge la B, care ar fi doar bit 1

93
00:06:40,020 --> 00:06:45,430
și apoi pentru a ajunge la o vom avea 01, iar apoi C cu 00.

94
00:06:45,430 --> 00:06:51,300
Deci, aici vom vedea că practic ne reprezintă aceste caractere, cu 1 sau 2 biți

95
00:06:51,300 --> 00:06:55,160
în cazul în care B, după cum a prezis, are cel.

96
00:06:55,160 --> 00:07:01,730
Și apoi ne-am asteptat sa aiba cea mai mare C, dar din moment ce este un astfel de mic copac Huffman,

97
00:07:01,730 --> 00:07:06,020
atunci A este, de asemenea, reprezentată de 2 biți, spre deosebire de undeva la mijloc.

98
00:07:07,820 --> 00:07:11,070
>> Doar pentru a trece peste un alt exemplu simplu de arbore Huffman,

99
00:07:11,070 --> 00:07:19,570
spunem că aveți șirul "Hello".

100
00:07:19,570 --> 00:07:25,360
Ceea ce faci este în primul rând v-ar spune de câte ori se H apare în asta?

101
00:07:25,360 --> 00:07:34,200
H apare o singură dată și apoi e apare o singură dată și apoi ne-am l apar de două ori

102
00:07:34,200 --> 00:07:36,580
și o dată apare.

103
00:07:36,580 --> 00:07:44,310
Și așa, atunci ne așteptăm scrisoarea, care să fie reprezentate de către cel mai mic număr de biți?

104
00:07:44,310 --> 00:07:47,450
[Elev] L. L >>. Da. L are dreptate.

105
00:07:47,450 --> 00:07:50,730
Ne așteptăm ca l pentru a fi reprezentat de cel mai mic număr de biți

106
00:07:50,730 --> 00:07:55,890
deoarece l este utilizat cel mai mult în șirul "Hello".

107
00:07:55,890 --> 00:08:04,280
Ceea ce am de gând să fac acum este egal în aceste noduri.

108
00:08:04,280 --> 00:08:15,580
Am 1, care este H, iar apoi un alt 1, care este e, iar apoi o 1, care este o -

109
00:08:15,580 --> 00:08:23,410
acum le-am pune în ordine - și apoi 2, care este l.

110
00:08:23,410 --> 00:08:32,799
Apoi am spus modul în care am construi un arbore Huffman este de a găsi cele 2 noduri cu cel mai frecvențele

111
00:08:32,799 --> 00:08:38,010
și să le facă frați prin crearea unui nod parinte.

112
00:08:38,010 --> 00:08:41,850
Aici avem 3 noduri cu frecvența cea mai mică. Sunt toate 1.

113
00:08:41,850 --> 00:08:50,620
Deci, aici vom alege care unul ne vom lega mai întâi.

114
00:08:50,620 --> 00:08:54,850
Să spunem că am alege H și e.

115
00:08:54,850 --> 00:09:01,150
Suma de 1 + 1 este 2, dar acest nod nu are o scrisoare de asociat cu aceasta.

116
00:09:01,150 --> 00:09:04,440
El detine doar valoarea.

117
00:09:04,440 --> 00:09:10,950
Acum ne uităm la următoarele 2 mai mici frecvențe.

118
00:09:10,950 --> 00:09:15,590
Asta e 2 și 1. Asta ar putea fi una dintre cele 2, dar am de gând să alegeți această unul.

119
00:09:15,590 --> 00:09:18,800
Suma este de 3.

120
00:09:18,800 --> 00:09:26,410
Și apoi în cele din urmă, am doar 2 stânga, astfel încât atunci care devine 5.

121
00:09:26,410 --> 00:09:32,010
Atunci aici, cum era de așteptat, în cazul în care am completați în codificarea pentru că,

122
00:09:32,010 --> 00:09:37,480
1s sunt întotdeauna ramura dreapta si 0s sunt cel stâng.

123
00:09:37,480 --> 00:09:45,880
Apoi, avem am reprezentată de doar 1 bit și apoi o cu 2

124
00:09:45,880 --> 00:09:52,360
si apoi e de 2 și apoi H cade la 3 biți.

125
00:09:52,360 --> 00:09:59,750
Astfel încât să puteți transmite acest mesaj "Bună ziua" în loc de a folosi efectiv caracterele

126
00:09:59,750 --> 00:10:02,760
doar prin 0s și 1s.

127
00:10:02,760 --> 00:10:07,910
Cu toate acestea, amintiți-vă că, în multe cazuri am avut legături cu frecvența noastră.

128
00:10:07,910 --> 00:10:11,900
Am fi putut s-au alăturat, fie H și o prima poate.

129
00:10:11,900 --> 00:10:15,730
Sau mai târziu, atunci când am avut am reprezentat cu 2

130
00:10:15,730 --> 00:10:19,410
precum și sa alăturat uneia reprezentat de 2, am fi putut legate fie unul.

131
00:10:19,410 --> 00:10:23,630
>> Și așa că atunci când vă trimite 0s și 1s, că de fapt nu garantează

132
00:10:23,630 --> 00:10:27,090
că destinatarul poate citi pe deplin mesajul dvs. right off BAT

133
00:10:27,090 --> 00:10:30,490
deoarece acestea ar putea să nu știe ce decizie ai luat.

134
00:10:30,490 --> 00:10:34,920
Așa că atunci când avem de a face cu compresie Huffman,

135
00:10:34,920 --> 00:10:40,090
cumva avem să spunem destinatarul mesajului nostru modul în care ne-am decis -

136
00:10:40,090 --> 00:10:43,470
Ei au nevoie să știe un fel de informații suplimentare

137
00:10:43,470 --> 00:10:46,580
în plus față de mesajul comprimat.

138
00:10:46,580 --> 00:10:51,490
Ei au nevoie să înțeleagă ceea ce de fapt copacul arata ca,

139
00:10:51,490 --> 00:10:55,450
cum ne-am facut de fapt aceste decizii.

140
00:10:55,450 --> 00:10:59,100
>> Aici facem doar exemple bazate pe numărul de efective,

141
00:10:59,100 --> 00:11:01,550
dar, uneori, puteți avea, de asemenea, un copac Huffman

142
00:11:01,550 --> 00:11:05,760
bazat pe frecvența la care literele apar, si este exact acelasi proces.

143
00:11:05,760 --> 00:11:09,090
Aici eu o exprimă în termeni de procente sau o fracțiune,

144
00:11:09,090 --> 00:11:11,290
și astfel aici, exact același lucru.

145
00:11:11,290 --> 00:11:15,300
Mi se pare cel mai mic 2, concluzie le, 2 Urmatorul cel mai mic, le însumați,

146
00:11:15,300 --> 00:11:19,390
până când am un copac plin.

147
00:11:19,390 --> 00:11:23,610
Chiar dacă am putea face nici un fel, atunci când avem de-a face cu procente,

148
00:11:23,610 --> 00:11:27,760
înseamnă că suntem împărțirea lucrurilor și care se ocupă cu zecimale sau, mai degrabă plutește

149
00:11:27,760 --> 00:11:30,900
dacă ne gândim despre structurile de date ale unui cap.

150
00:11:30,900 --> 00:11:32,540
Ce știm despre flotoare?

151
00:11:32,540 --> 00:11:35,180
Ce este o problemă comună atunci când avem de-a face cu flotoare?

152
00:11:35,180 --> 00:11:38,600
[Elev] impreciși aritmetică. Da >>. Imprecizie.

153
00:11:38,600 --> 00:11:43,760
Din cauza impreciziei în virgulă mobilă, pentru acest PSET, astfel încât să ne asigurăm

154
00:11:43,760 --> 00:11:49,450
că noi nu pierdem nici o valoare, apoi vom fapt de gând să se ocupe cu numărul.

155
00:11:49,450 --> 00:11:54,880
Deci, dacă ar fi să gândească la un nod Huffman, daca te uiti inapoi la structura aici,

156
00:11:54,880 --> 00:12:01,740
daca te uiti la cei verzi are o frecvență asociat cu acesta

157
00:12:01,740 --> 00:12:08,760
precum și punctele de la un nod la stânga acestuia, precum și un nod la dreptul său.

158
00:12:08,760 --> 00:12:13,970
Și apoi cele roșii au existat, de asemenea, un caracter asociate cu acestea.

159
00:12:13,970 --> 00:12:18,900
Noi nu suntem de gând să facă cele separate pentru părinți și apoi noduri finale,

160
00:12:18,900 --> 00:12:23,680
care ne vom referi în continuare frunze, ci mai degrabă cei care vor avea doar valori NULL.

161
00:12:23,680 --> 00:12:31,050
Pentru fiecare nod vom avea un caracter, simbol că acest nod reprezintă,

162
00:12:31,050 --> 00:12:40,490
apoi o frecvență, precum și un pointer la copilul său din stânga, precum și de dreptul său de copil.

163
00:12:40,490 --> 00:12:45,680
Frunzele, care se află la partea de jos foarte, ar trebui, de asemenea, indicii de nod

164
00:12:45,680 --> 00:12:49,550
la stânga și la dreapta lor, dar din moment ce aceste valori nu sunt orientate în ganglionii reale,

165
00:12:49,550 --> 00:12:53,970
ceea ce ar fi valoarea lor? >> [Elev] NULL. NULL >>. Exact.

166
00:12:53,970 --> 00:12:58,430
Iată un exemplu despre cum ați putea reprezenta frecvența în flotoare,

167
00:12:58,430 --> 00:13:02,130
dar am de gând să se ocupe cu ea cu numere întregi,

168
00:13:02,130 --> 00:13:06,780
deci tot ce am făcut este să schimbăm tipul de date acolo.

169
00:13:06,780 --> 00:13:09,700
>> Să mergem pe la un pic mai mult de un exemplu complex.

170
00:13:09,700 --> 00:13:13,360
Dar acum, că am făcut cele mai simple, e doar același proces.

171
00:13:13,360 --> 00:13:20,290
Puteți găsi frecvențele cele mai mici 2, însumați frecvențele

172
00:13:20,290 --> 00:13:22,450
si asta e noua frecventa a nodului părinte,

173
00:13:22,450 --> 00:13:29,310
care apoi arată la stânga cu ramura 0 și dreapta cu ramura 1.

174
00:13:29,310 --> 00:13:34,200
Dacă avem șirul "Aceasta este CS50," atunci vom conta de câte ori este menționat T,

175
00:13:34,200 --> 00:13:38,420
h menționat, I, S, C, 5, 0.

176
00:13:38,420 --> 00:13:42,010
Atunci ce am făcut aici este cu noduri roșii am plantate,

177
00:13:42,010 --> 00:13:48,530
Am spus că voi avea aceste personaje în cele din urmă, la partea de jos a copacul meu.

178
00:13:48,530 --> 00:13:51,740
Cei care vor să fie tot de frunze.

179
00:13:51,740 --> 00:13:58,200
Atunci ceea ce am făcut este că le-clasificate în funcție de frecvență, în ordine crescătoare,

180
00:13:58,200 --> 00:14:02,950
și acest lucru este de fapt modul în care codul de PSET o face

181
00:14:02,950 --> 00:14:07,550
Este îl sortează după frecvența și apoi după alfabet.

182
00:14:07,550 --> 00:14:13,870
Deci, are numere mai întâi și apoi în ordine alfabetică de frecvență.

183
00:14:13,870 --> 00:14:18,520
Atunci ce aș face este că va găsi cel mai mic 2. Asta e 0 și 5.

184
00:14:18,520 --> 00:14:22,390
Eu le-ar rezuma, și asta e 2. Atunci aș continua, găsiți următoarele 2 mai mic.

185
00:14:22,390 --> 00:14:26,100
Acestea sunt 1s două, și apoi devin cei 2, precum.

186
00:14:26,100 --> 00:14:31,570
Acum, eu știu că pasul următor este meu va fi aderarea cel mai mic număr,

187
00:14:31,570 --> 00:14:41,380
care este T, 1, și alegând apoi unul dintre nodurile care are 2 ca frecvență.

188
00:14:41,380 --> 00:14:44,560
Deci, aici avem 3 optiuni.

189
00:14:44,560 --> 00:14:47,980
Ceea ce am de gând să fac pentru diapozitiv este doar vizual rearanja-le pentru tine

190
00:14:47,980 --> 00:14:51,790
astfel încât să puteți vedea cum eu o construirea.

191
00:14:51,790 --> 00:14:59,040
Ce cod și codul de distribuție este de gând să facă ar fi alătura t un

192
00:14:59,040 --> 00:15:01,410
cu nodul 0 și 5.

193
00:15:01,410 --> 00:15:05,060
Deci faptul că sumele la 3, iar apoi vom continua procesul.

194
00:15:05,060 --> 00:15:08,660
2 și 2 acum sunt cele mai mici, astfel încât atunci cei suma intre la 4.

195
00:15:08,660 --> 00:15:12,560
Toată lumea urma până acum? Bine.

196
00:15:12,560 --> 00:15:16,410
Apoi, după ce că avem 3 și 3, care trebuie să fie adăugate,

197
00:15:16,410 --> 00:15:21,650
deci din nou, eu sunt doar de comutare, astfel încât să puteți vedea vizual, astfel încât să nu se prea murdar.

198
00:15:21,650 --> 00:15:25,740
Atunci avem un 6, iar apoi pas nostru final este acum că avem doar 2 noduri

199
00:15:25,740 --> 00:15:30,440
am rezuma cele de a face rădăcina arborelui nostru, care este de 10.

200
00:15:30,440 --> 00:15:34,100
Și numărul 10 are sens, deoarece fiecare nod reprezentat,

201
00:15:34,100 --> 00:15:40,750
valoarea lor, numărul lor de frecvență, a fost de câte ori au apărut în șir,

202
00:15:40,750 --> 00:15:46,350
și apoi avem 5 caractere în șirul nostru, astfel încât are sens.

203
00:15:48,060 --> 00:15:52,320
Dacă ne uităm în sus la modul în care ne-ar codifica de fapt,

204
00:15:52,320 --> 00:15:56,580
cum era de asteptat, i și s, care apar cel mai des

205
00:15:56,580 --> 00:16:01,350
sunt reprezentate de cel mai mic număr de biți.

206
00:16:03,660 --> 00:16:05,660
>> Fii atent aici.

207
00:16:05,660 --> 00:16:09,780
În copaci Huffman caz, de fapt contează.

208
00:16:09,780 --> 00:16:13,670
Un S majuscule este diferită de un s. litere mici.

209
00:16:13,670 --> 00:16:21,260
Dacă am fi avut "Aceasta este CS50" cu majuscule, atunci s-ar părea minuscule doar de două ori,

210
00:16:21,260 --> 00:16:27,120
ar fi un nod cu 2 valoarea sa, și apoi cu majuscule S-ar fi doar o singură dată.

211
00:16:27,120 --> 00:16:33,440
Deci, atunci arborele se va schimba structurile că aveți de fapt, o frunză în plus aici.

212
00:16:33,440 --> 00:16:36,900
Dar suma ar fi încă 10.

213
00:16:36,900 --> 00:16:39,570
Asta e ceea ce esti de fapt, o să fie de asteptare de control,

214
00:16:39,570 --> 00:16:44,060
adăugarea tuturor conteaza.

215
00:16:46,010 --> 00:16:50,990
>> Acum, că ne-am acoperit copaci Huffman, putem scufunda in Puff Huff'n, PSET.

216
00:16:50,990 --> 00:16:52,900
Vom începe cu o secțiune de întrebări,

217
00:16:52,900 --> 00:16:57,990
și acest lucru se întâmplă pentru a te obișnui cu pomi binare și modul în care să opereze în jurul valorii de faptul că:

218
00:16:57,990 --> 00:17:03,230
noduri de desen, crearea de dvs. struct propria typedef pentru un nod,

219
00:17:03,230 --> 00:17:07,230
și văzând cum s-ar putea insera într-un arbore binar, unul care e sortate,

220
00:17:07,230 --> 00:17:09,050
traversează aceasta, și lucruri de genul asta.

221
00:17:09,050 --> 00:17:14,560
Această cunoaștere este cu siguranta te va ajuta atunci cand se arunca cu capul în partea Puff Huff'n

222
00:17:14,560 --> 00:17:17,089
a PSET.

223
00:17:19,150 --> 00:17:26,329
În ediția standard a PSET, sarcina dumneavoastră este de a pune în aplicare Puff,

224
00:17:26,329 --> 00:17:30,240
și în versiunea hacker sarcina dumneavoastră este de a pune în aplicare Huff.

225
00:17:30,240 --> 00:17:38,490
Ce Huff nu este nevoie de text și apoi îl traduce în 0s și 1s,

226
00:17:38,490 --> 00:17:41,990
astfel procesul care am făcut mai sus în cazul în care am numarat frecvențelor

227
00:17:41,990 --> 00:17:50,970
și apoi a făcut copac și apoi a spus, "Cum pot obține T?"

228
00:17:50,970 --> 00:17:54,840
T este reprezentat de 100, lucruri de genul asta,

229
00:17:54,840 --> 00:17:58,860
și apoi Huff va lua textul și apoi de ieșire care binar.

230
00:17:58,860 --> 00:18:04,920
Dar, de asemenea, pentru că știm că ne-o dorim pentru a permite destinatarului mesajului nostru de

231
00:18:04,920 --> 00:18:11,790
pentru a recrea exact același copac, aceasta include, de asemenea, informații despre numărul de frecvențe.

232
00:18:11,790 --> 00:18:17,980
Apoi, cu Puff ni se dă un fișier binar de 0s și 1s

233
00:18:17,980 --> 00:18:21,740
și având în vedere, de asemenea, informații despre frecvențele.

234
00:18:21,740 --> 00:18:26,740
Noi traducem toți cei înapoi 0s și 1s în mesajul original, care a fost,

235
00:18:26,740 --> 00:18:29,350
așa că suntem decompressing.

236
00:18:29,350 --> 00:18:36,450
Dacă faci ediția standard, nu trebuie să pună în aplicare Huff,

237
00:18:36,450 --> 00:18:39,290
astfel încât, atunci puteți folosi doar punerea în aplicare a personalului Huff.

238
00:18:39,290 --> 00:18:42,080
Există instrucțiuni în spec. cu privire la modul de a face acest lucru.

239
00:18:42,080 --> 00:18:48,780
Puteți rula punerea în aplicare a personalului Huff asupra unui anumit fișier text

240
00:18:48,780 --> 00:18:53,270
și de a folosi apoi că producția ca intrare la Puff.

241
00:18:53,270 --> 00:18:59,330
>> Așa cum am menționat mai înainte, avem o mulțime de cod de distribuție pentru asta.

242
00:18:59,330 --> 00:19:01,810
Am de gând să înceapă merge prin ea.

243
00:19:01,810 --> 00:19:04,400
Am de gând să-și petreacă cea mai mare parte a timpului pe fișiere. H

244
00:19:04,400 --> 00:19:07,660
deoarece în fișierele. c, pentru că avem ore.

245
00:19:07,660 --> 00:19:11,650
și care ne oferă cu prototipuri ale funcțiilor,

246
00:19:11,650 --> 00:19:15,520
nu avem nevoie de a înțelege pe deplin exact -

247
00:19:15,520 --> 00:19:20,280
Dacă nu înțelegi ce se întâmplă în fișierele. C, atunci nu vă faceți griji prea mult,

248
00:19:20,280 --> 00:19:23,600
dar încercați cu siguranta pentru a lua o privire, pentru că s-ar putea da unele sugestii

249
00:19:23,600 --> 00:19:29,220
și este util să te obișnuiești cu citirea codului altor oameni.

250
00:19:38,940 --> 00:19:48,270
>> Privind la huffile.h, în comentariile pe care le declară un strat de abstractizare pentru Huffman-codificate fișiere.

251
00:19:48,270 --> 00:20:01,660
Dacă mergem în jos, vom vedea că există un număr maxim de 256 de simboluri pe care le-ar putea avea nevoie de coduri pentru.

252
00:20:01,660 --> 00:20:05,480
Aceasta include toate literele din alfabet - mari și mici -

253
00:20:05,480 --> 00:20:08,250
și apoi simboluri și numere, etc

254
00:20:08,250 --> 00:20:11,930
Atunci aici avem un numar magic de identificare un fișier Huffman-codat.

255
00:20:11,930 --> 00:20:15,890
În termen de un cod Huffman au de gând să aibă un anumit numar magic

256
00:20:15,890 --> 00:20:18,560
asociat cu antet.

257
00:20:18,560 --> 00:20:21,110
Acest lucru ar putea arata ca doar un numar magic aleator,

258
00:20:21,110 --> 00:20:27,160
dar dacă traduce de fapt în ASCII, atunci este de fapt vrăji Huff.

259
00:20:27,160 --> 00:20:34,290
Aici avem o struct pentru un fișier Huffman-codificat.

260
00:20:34,290 --> 00:20:39,670
Există toate aceste caracteristici asociate cu un fișier Huff.

261
00:20:39,670 --> 00:20:47,080
Atunci aici jos, avem un fișier antet pentru Huff, de aceea îl numim Huffeader

262
00:20:47,080 --> 00:20:50,810
în loc de a adăuga h în plus pentru că sună la fel, oricum.

263
00:20:50,810 --> 00:20:52,720
Drăguț.

264
00:20:52,720 --> 00:20:57,790
Avem un număr de magie asociate cu aceasta.

265
00:20:57,790 --> 00:21:09,040
Dacă e un real fișier Huff, că va fi numărul de deasupra, acest magic.

266
00:21:09,040 --> 00:21:14,720
Și apoi va avea o matrice.

267
00:21:14,720 --> 00:21:18,750
Deci, pentru fiecare simbol, din care există 256,

268
00:21:18,750 --> 00:21:24,760
se va lista ce frecvența acestor simboluri se află în fișierul Huff.

269
00:21:24,760 --> 00:21:28,090
Și apoi în cele din urmă, avem o sumă de control pentru frecvențele,

270
00:21:28,090 --> 00:21:32,160
care ar trebui să fie suma intre aceste frecvențe.

271
00:21:32,160 --> 00:21:36,520
Deci, asta e ceea ce o Huffeader este.

272
00:21:36,520 --> 00:21:44,600
Apoi, avem unele funcții care returnează următorul bit în dosarul Huff

273
00:21:44,600 --> 00:21:52,580
precum și scrie un pic la dosar Huff, iar apoi această funcție aici, hfclose,

274
00:21:52,580 --> 00:21:54,650
care se închide, de fapt fișierul Huff.

275
00:21:54,650 --> 00:21:57,290
Înainte, am fost de-a face cu drept fclose doar,

276
00:21:57,290 --> 00:22:01,190
dar atunci când aveți un fișier Huff, în loc să-l fclosing

277
00:22:01,190 --> 00:22:06,080
ceea ce de fapt de gând să faceți este să hfclose și hfopen-l.

278
00:22:06,080 --> 00:22:13,220
Acestea sunt funcții specifice fișierelor Huff că suntem de gând să se ocupe cu.

279
00:22:13,220 --> 00:22:19,230
Apoi aici am citit în antet și apoi scrie antetul.

280
00:22:19,230 --> 00:22:25,700
>> Doar prin citirea fișierului h.. Putem fel de a obține un sentiment de ceea ce un fișier Huff ar putea fi,

281
00:22:25,700 --> 00:22:32,480
ce caracteristici are, de fapt, fără a intra în huffile.c,

282
00:22:32,480 --> 00:22:36,750
pe care, dacă am arunca cu capul în, va fi un pic mai complex.

283
00:22:36,750 --> 00:22:41,270
Ea are toate fișierului I / O, aici de-a face cu pointeri.

284
00:22:41,270 --> 00:22:48,010
Aici vom vedea că atunci când ne numim hfread, de exemplu, este încă de-a face cu fread.

285
00:22:48,010 --> 00:22:53,050
Nu ne scăpa de aceste funcții în întregime, dar vă trimitem pe cei care urmează să fie luate în grijă de

286
00:22:53,050 --> 00:22:59,760
în interiorul fișierul Huff loc de a face totul singuri.

287
00:22:59,760 --> 00:23:02,300
Puteți simți liber pentru a scana prin acest lucru, dacă ești curios

288
00:23:02,300 --> 00:23:08,410
și du-te și coaja de stratul de spate un pic.

289
00:23:20,650 --> 00:23:24,060
>> Urmatorul fisier pe care am de gând să se uite la este tree.h.

290
00:23:24,060 --> 00:23:30,210
Înainte de a în Walkthrough alunecă am spus ne așteptăm la un nod Huffman

291
00:23:30,210 --> 00:23:32,960
și am făcut un nod typedef struct.

292
00:23:32,960 --> 00:23:38,360
Ne așteptăm ca acesta să aibă un simbol, o frecvență, apoi 2 stele nod.

293
00:23:38,360 --> 00:23:41,870
În acest caz, ceea ce facem noi este acest lucru este în esență același

294
00:23:41,870 --> 00:23:46,880
cu excepția loc de nod vom numi copaci.

295
00:23:48,790 --> 00:23:56,760
Avem o funcție care, atunci când apelați face copac se întoarce ai un pointer copac.

296
00:23:56,760 --> 00:24:03,450
Copii de la Speller, atunci când s-au a face un nod nou

297
00:24:03,450 --> 00:24:11,410
ai spus nod * nou cuvânt = malloc (sizeof) și lucruri de genul asta.

298
00:24:11,410 --> 00:24:17,510
Practic, mktree va fi a face cu asta pentru tine.

299
00:24:17,510 --> 00:24:20,990
În mod similar, atunci când doriți să eliminați un copac,

300
00:24:20,990 --> 00:24:24,810
Deci, asta e, în esență eliberarea copac atunci când ați terminat cu ea,

301
00:24:24,810 --> 00:24:33,790
în loc de în mod explicit apel gratuit de pe care, tu esti de fapt doar de gând să utilizeze funcția rmtree

302
00:24:33,790 --> 00:24:40,360
în cazul în care vă trece în pointer la acel pom și apoi tree.c va avea grija de asta pentru tine.

303
00:24:40,360 --> 00:24:42,490
>> Ne uităm în tree.c.

304
00:24:42,490 --> 00:24:47,240
Ne așteptăm ca aceleași funcții, cu excepția pentru a vedea punerea în aplicare, de asemenea.

305
00:24:47,240 --> 00:24:57,720
Așa cum ne-am așteptat, atunci când apelați mktree l mallocs marimea unui copac într-un pointer,

306
00:24:57,720 --> 00:25:03,190
initializeaza toate valorile la valoarea NULL, deci 0s sau valori nule,

307
00:25:03,190 --> 00:25:08,280
și apoi returnează pointer la acel copac pe care tocmai l-ați malloc'd pentru tine.

308
00:25:08,280 --> 00:25:13,340
Aici atunci când apelați scoateți copac mai întâi se asigură că nu ești dublu eliberarea.

309
00:25:13,340 --> 00:25:18,320
Se face-vă că aveți de fapt, un copac pe care doriți să o eliminați.

310
00:25:18,320 --> 00:25:23,330
Aici, deoarece un copac include, de asemenea copiii săi,

311
00:25:23,330 --> 00:25:29,560
ce face asta este recursiv solicită eliminarea copac de pe nodul din stânga a arborelui

312
00:25:29,560 --> 00:25:31,650
precum și dreptul de nod.

313
00:25:31,650 --> 00:25:37,790
Înainte de a elibereaza-mamă, de care are nevoie pentru a elibera copii, precum și.

314
00:25:37,790 --> 00:25:42,770
Mamă este, de asemenea, interschimbabile cu rădăcină.

315
00:25:42,770 --> 00:25:46,500
Mamă pentru prima dată, așa cum ar fi stră-stră-stră-stră-bunicul

316
00:25:46,500 --> 00:25:52,130
sau copac bunica, în primul rând trebuie să ne eliberăm de stabilire a nivelurilor primul.

317
00:25:52,130 --> 00:25:58,490
Deci, pentru a traversa partea de jos, cele libere, și apoi întoarce-te, gratis cele, etc

318
00:26:00,400 --> 00:26:02,210
Deci asta e copacul.

319
00:26:02,210 --> 00:26:04,240
>> Acum ne uităm la pădure.

320
00:26:04,240 --> 00:26:09,860
Pădurea este locul unde vă plasați toate copacii Huffman.

321
00:26:09,860 --> 00:26:12,910
Se spune că vom avea ceva numit un complot

322
00:26:12,910 --> 00:26:22,320
care conține un pointer la un copac, precum și un pointer la un complot numit următoare.

323
00:26:22,320 --> 00:26:28,480
Ce structura are acest tip de arata ca?

324
00:26:29,870 --> 00:26:32,490
Intr-un fel se spune de acolo.

325
00:26:34,640 --> 00:26:36,700
Chiar aici.

326
00:26:37,340 --> 00:26:39,170
O listă legate.

327
00:26:39,170 --> 00:26:44,590
Vedem că, atunci când avem un teren e ca o listă legată de parcele.

328
00:26:44,590 --> 00:26:53,020
O pădure este definită ca o listă legată de parcele,

329
00:26:53,020 --> 00:26:58,100
și astfel structura de pădure este de suntem doar de gând să aibă un pointer la primul nostru complot

330
00:26:58,100 --> 00:27:02,740
și că Parcela dispune de un copac în el sau, mai degrabă arată într-un copac

331
00:27:02,740 --> 00:27:06,190
și apoi indică următoarea parcelă, așa mai departe și așa mai departe.

332
00:27:06,190 --> 00:27:11,100
Pentru a face o pădure numim mkforest.

333
00:27:11,100 --> 00:27:14,930
Apoi, avem unele funcții destul de utile aici.

334
00:27:14,930 --> 00:27:23,240
Avem alege unde să treci într-o pădure, apoi valoarea returnata este un copac *,

335
00:27:23,240 --> 00:27:25,210
un pointer la un copac.

336
00:27:25,210 --> 00:27:29,370
Ce alegere va face este că va merge în pădure pe care îl indică spre

337
00:27:29,370 --> 00:27:35,240
apoi scoateți un copac cu cea mai mică frecvență de la acea pădure

338
00:27:35,240 --> 00:27:38,330
și să dea apoi pointer la acel copac.

339
00:27:38,330 --> 00:27:43,030
Odată ce ați alege suna, copacul nu va exista în pădure mai,

340
00:27:43,030 --> 00:27:48,550
dar valoarea returnată este pointer la acel copac.

341
00:27:48,550 --> 00:27:50,730
Apoi, aveți de plante.

342
00:27:50,730 --> 00:27:57,420
În cazul în care să treci într-un pointer la un copac care are o frecvență non-0,

343
00:27:57,420 --> 00:28:04,040
ce planta va face este că va lua pădure, ia copac, și a plantelor ca in interiorul copac din pădure.

344
00:28:04,040 --> 00:28:06,370
Aici avem rmforest.

345
00:28:06,370 --> 00:28:11,480
Similar pentru a elimina copac, care practic toate eliberat de arbori noastre pentru noi,

346
00:28:11,480 --> 00:28:16,600
eliminarea pădure vor totul gratis conținută în acea pădure.

347
00:28:16,600 --> 00:28:24,890
>> Dacă ne uităm în forest.c, vom aștepta să vedem cel puțin 1 comandă rmtree acolo,

348
00:28:24,890 --> 00:28:30,090
deoarece pentru a elibera memorie în pădure, dacă o pădure are copaci în ea,

349
00:28:30,090 --> 00:28:32,930
apoi în cele din urmă ai de gând să aibă de a elimina aceste copaci prea.

350
00:28:32,930 --> 00:28:41,020
Dacă ne uităm în forest.c, avem mkforest nostru, care este la fel ne asteptam.

351
00:28:41,020 --> 00:28:42,890
Am malloc lucruri.

352
00:28:42,890 --> 00:28:51,740
Am inițializa complot primul pădure ca NULL pentru ca este gol pentru a începe cu,

353
00:28:51,740 --> 00:29:05,940
apoi vom vedea alege, care returnează copac cu cea mai mică greutate, frecvența cea mai mică,

354
00:29:05,940 --> 00:29:13,560
si apoi scapa de acel nod special, care indică faptul că la pomul și alta,

355
00:29:13,560 --> 00:29:16,760
așa că ia că din lista legată de pădure.

356
00:29:16,760 --> 00:29:24,510
Și apoi aici, avem de plante, care introduce un copac în lista de legat.

357
00:29:24,510 --> 00:29:29,960
Ce pădure nu este frumos menține sortate pentru noi.

358
00:29:29,960 --> 00:29:37,910
Și apoi în cele din urmă, avem rmforest și, cum era de asteptat, avem rmtree chemat acolo.

359
00:29:46,650 --> 00:29:55,440
>> Privind la codul de distribuție până în prezent, a fost, probabil, huffile.c de departe cel mai greu de înțeles,

360
00:29:55,440 --> 00:29:59,990
întrucât celelalte fișiere înșiși au fost destul de simplu de urmat.

361
00:29:59,990 --> 00:30:03,090
Cu cunoștințele noastre de indicii și liste legate și astfel,

362
00:30:03,090 --> 00:30:04,860
noi am fost capabil să urmeze destul de bine.

363
00:30:04,860 --> 00:30:10,500
Dar tot ce avem nevoie pentru a face sigur că am înțeles pe deplin este h fișierele.

364
00:30:10,500 --> 00:30:15,840
pentru că aveți nevoie pentru a fi de asteptare acestor funcții, care se ocupă cu aceste valori de returnare,

365
00:30:15,840 --> 00:30:20,590
astfel încât asigurați-vă că ați înțeles pe deplin ce acțiuni urmează să fie efectuate

366
00:30:20,590 --> 00:30:24,290
ori de câte ori te sun una din aceste funcții.

367
00:30:24,290 --> 00:30:33,020
Dar, de fapt înțelegerea în interiorul acestuia nu este destul de necesar, deoarece avem cele. Fișiere oră.

368
00:30:35,170 --> 00:30:39,490
Avem 2 mai multe fișiere rămase în codul nostru de distributie.

369
00:30:39,490 --> 00:30:41,640
>> Să ne uităm la groapa de gunoi.

370
00:30:41,640 --> 00:30:47,230
Utilitară benă de comentariul său are aici un fișier Huffman-comprimat

371
00:30:47,230 --> 00:30:55,580
și apoi traduce si din haldele de toate de conținutul său out.

372
00:31:01,010 --> 00:31:04,260
Aici vom vedea că sună hfopen.

373
00:31:04,260 --> 00:31:10,770
Aceasta este un fel de oglindire a depune * intrare = fopen,

374
00:31:10,770 --> 00:31:13,500
si apoi treci la informații.

375
00:31:13,500 --> 00:31:18,240
E aproape identice, cu excepția în loc de un fișier * te trece într-o Huffile;

376
00:31:18,240 --> 00:31:22,030
în loc de fopen ce te trece în hfopen.

377
00:31:22,030 --> 00:31:29,280
Aici am citit în antet în primul rând, care este un fel de similar cu modul în care am citit în antetul

378
00:31:29,280 --> 00:31:33,580
pentru un fișier de tip bitmap.

379
00:31:33,580 --> 00:31:38,000
Ceea ce facem noi aici este de verificare pentru a vedea dacă antetul informații

380
00:31:38,000 --> 00:31:44,330
conține numărul magic dreapta care indică faptul că acesta este un real fișier Huff,

381
00:31:44,330 --> 00:31:53,610
atunci toate aceste controale pentru a se asigura că fișierul pe care am deschis un fișier este reală sau nu rățoiește.

382
00:31:53,610 --> 00:32:05,330
Ceea ce face este să emită frecvențele toate simbolurile pe care le putem vedea

383
00:32:05,330 --> 00:32:09,790
într-un terminal de într-un tabel grafic.

384
00:32:09,790 --> 00:32:15,240
Această parte va fi utilă.

385
00:32:15,240 --> 00:32:24,680
Ea are un pic și citește bit cu bit în biți variabilă și apoi se imprimă.

386
00:32:28,220 --> 00:32:35,430
Deci, dacă ar fi să sun la groapa de hth.bin, care este rezultatul unui fișier huffing

387
00:32:35,430 --> 00:32:39,490
folosind soluția de personal, mi-ar lua asta.

388
00:32:39,490 --> 00:32:46,000
Este scoate toate aceste personaje și apoi punerea frecvența la care ele apar.

389
00:32:46,000 --> 00:32:51,180
Dacă ne uităm, cele mai multe dintre ele sunt 0s, cu excepția pentru acest lucru: H, care apare de două ori,

390
00:32:51,180 --> 00:32:54,820
și atunci T, care apare o singură dată.

391
00:32:54,820 --> 00:33:07,860
Și apoi aici, avem mesajul real în 0s și 1s.

392
00:33:07,860 --> 00:33:15,450
Dacă ne uităm la hth.txt, care este probabil mesajul original care a fost rățoiește,

393
00:33:15,450 --> 00:33:22,490
ne așteptăm să vedem niște Hs și Ts acolo.

394
00:33:22,490 --> 00:33:28,720
Concret, ne așteptăm să vedem doar 1 T și 2 HS.

395
00:33:32,510 --> 00:33:37,440
Aici suntem în hth.txt. Ea într-adevăr are HTH.

396
00:33:37,440 --> 00:33:41,270
Incluse în acolo, desi nu-l putem vedea, este un personaj linie noua.

397
00:33:41,270 --> 00:33:53,190
Hth.bin fișier Huff este, de asemenea, codificarea caracter linie noua, de asemenea.

398
00:33:55,680 --> 00:34:01,330
Aici, pentru că știm că ordinea este HTH și apoi linie noua,

399
00:34:01,330 --> 00:34:07,340
putem vedea că, probabil, H este reprezentat de doar un singur 1

400
00:34:07,340 --> 00:34:17,120
și apoi T este, probabil, 01 și apoi H următoarea este de 1, precum și

401
00:34:17,120 --> 00:34:21,139
și apoi vom avea o linie nouă indicate prin două 0s.

402
00:34:22,420 --> 00:34:24,280
Mișto.

403
00:34:26,530 --> 00:34:31,600
>> Și apoi în final, pentru că avem de a face cu mai multe. C și fișiere. H,

404
00:34:31,600 --> 00:34:36,350
vom avea un argument destul de complex pentru compilator,

405
00:34:36,350 --> 00:34:40,460
și așa mai departe aici avem un Makefile care face benă de tine.

406
00:34:40,460 --> 00:34:47,070
Dar, de fapt, trebuie să te duci despre a face dvs. de propriul dosar puff.c.

407
00:34:47,070 --> 00:34:54,330
Makefile de fapt, nu se ocupă cu efectuarea puff.c pentru tine.

408
00:34:54,330 --> 00:34:59,310
Plecăm că până la tine pentru a edita Makefile.

409
00:34:59,310 --> 00:35:05,930
Atunci când introduceți o comandă ca fac toate, de exemplu, se va face tot de pe ei pentru tine.

410
00:35:05,930 --> 00:35:10,760
Simțiți-vă liber să se uite la exemple de Makefile din PSET trecut

411
00:35:10,760 --> 00:35:17,400
precum și merge off de aceasta pentru a vedea cum s-ar putea fi capabil de a face fișierul Puff

412
00:35:17,400 --> 00:35:20,260
prin editarea acestui fișier Makefile.

413
00:35:20,260 --> 00:35:22,730
Asta e despre asta pentru codul noastre de distribuție.

414
00:35:22,730 --> 00:35:28,380
>> După ce am trecut prin asta, atunci aici e doar un alt memento

415
00:35:28,380 --> 00:35:30,980
de modul în care vom fi de-a face cu noduri Huffman.

416
00:35:30,980 --> 00:35:35,400
Noi nu vom fi numindu-le nodurile mai, vom fi numindu-le copaci

417
00:35:35,400 --> 00:35:39,260
în cazul în care vom reprezenta simbolul lor cu un char,

418
00:35:39,260 --> 00:35:43,340
frecvența lor, numarul de aparitii, cu un număr întreg.

419
00:35:43,340 --> 00:35:47,370
Suntem folosind ca pentru ca este mult mai precisă decât un flotor.

420
00:35:47,370 --> 00:35:52,980
Și apoi avem un alt indicatorul la stânga copilului, precum și dreptul de copil.

421
00:35:52,980 --> 00:35:59,630
O pădure, așa cum am văzut, este doar o listă legat de copaci.

422
00:35:59,630 --> 00:36:04,670
În cele din urmă, atunci când suntem construirea dosarul nostru Huff,

423
00:36:04,670 --> 00:36:07,580
vrem pădure noastră să conțină doar 1 copac -

424
00:36:07,580 --> 00:36:12,420
1 copac, 1 radacina cu copii multiple.

425
00:36:12,420 --> 00:36:20,840
Mai devreme cand am fost a face doar copacii noastre Huffman,

426
00:36:20,840 --> 00:36:25,360
am inceput prin plasarea toate nodurile pe ecran noastră

427
00:36:25,360 --> 00:36:27,790
și spunând vom avea aceste noduri,

428
00:36:27,790 --> 00:36:32,920
în cele din urmă ei vor fi frunze, iar acest lucru este simbolul lor, acest lucru este frecvența lor.

429
00:36:32,920 --> 00:36:42,070
În pădure noastră, dacă avem doar 3 litere, asta e o pădure de copaci 3.

430
00:36:42,070 --> 00:36:45,150
Și apoi ca mergem mai departe, atunci când am adăugat-mamă în primul rând,

431
00:36:45,150 --> 00:36:48,080
ne-am facut-o pădure de 2 copaci.

432
00:36:48,080 --> 00:36:54,930
Am eliminat 2 din acei copii din pădure noastră și apoi a înlocuit-o cu un nod parinte

433
00:36:54,930 --> 00:36:58,820
care a avut cele 2 noduri ca și copii.

434
00:36:58,820 --> 00:37:05,600
Și apoi în cele din urmă, ultimul pas noastră cu a face exemplul nostru cu Ca, B, și C

435
00:37:05,600 --> 00:37:08,030
ar fi de a face-mamă finală,

436
00:37:08,030 --> 00:37:13,190
și așa mai apoi că ar aduce numărul nostru total de pomi în pădure la 1.

437
00:37:13,190 --> 00:37:18,140
Are toată lumea vedea cum începe cu mai mulți arbori în pădure dvs.

438
00:37:18,140 --> 00:37:22,520
și se încheie cu 1? Bine. Mișto.

439
00:37:25,530 --> 00:37:28,110
>> Ce trebuie să facem pentru Puff?

440
00:37:28,110 --> 00:37:37,110
Ceea ce trebuie să faceți este să se asigure că, ca întotdeauna, ei ne dau dreptul de tipul de intrare

441
00:37:37,110 --> 00:37:39,090
astfel încât să putem rula de fapt programul.

442
00:37:39,090 --> 00:37:43,130
În acest caz, ei vor să fie oferindu-ne după prima lor linie de comandă argumentul

443
00:37:43,130 --> 00:37:53,440
2 mai mult: fișierul pe care ne-o dorim pentru a decomprima și de ieșire a fișierului decomprimat.

444
00:37:53,440 --> 00:38:00,410
Dar odată ce ne asigurăm că ne-au trecut în dreptul de suma de valori,

445
00:38:00,410 --> 00:38:05,820
dorim să ne asigurăm că este un fișier de intrare Huff sau nu.

446
00:38:05,820 --> 00:38:10,420
Și apoi, odată ce vom garanta faptul că este un fișier Huff, apoi vrem să construim copacul nostru,

447
00:38:10,420 --> 00:38:20,940
construi copac, astfel încât se potrivește copac care persoana care a trimis mesajul construit.

448
00:38:20,940 --> 00:38:25,840
Apoi, după ce ne-am construit arborele, atunci putem face cu, 0s și 1s că au trecut în

449
00:38:25,840 --> 00:38:29,590
urmați de-a lungul celor copacul nostru, deoarece este identic,

450
00:38:29,590 --> 00:38:33,510
și să scrie apoi că mesajul, interpreta biții înapoi în caractere.

451
00:38:33,510 --> 00:38:35,880
Și apoi, la sfârșit, deoarece avem de-a face cu pointeri aici,

452
00:38:35,880 --> 00:38:38,110
vrem să ne asigurăm că nu avem nici o scurgere de memorie

453
00:38:38,110 --> 00:38:41,330
și că avem totul gratuit.

454
00:38:42,820 --> 00:38:46,430
>> Asigurarea de utilizare corectă este pălărie vechi pentru noi până acum.

455
00:38:46,430 --> 00:38:51,980
Ne ia într-o intrare, care va fi numele fișierului pentru a sufla,

456
00:38:51,980 --> 00:38:56,010
și apoi vom specifica o iesire,

457
00:38:56,010 --> 00:39:01,580
astfel încât numele fișierului de ieșire pentru umflat, care va fi fișierul text.

458
00:39:03,680 --> 00:39:08,820
Asta e de utilizare. Și acum vrem să ne asigurăm că intrarea este rățoiește sau nu.

459
00:39:08,820 --> 00:39:16,420
Gândindu-mă, a fost ceva în codul de distribuție, care ne-ar putea ajuta

460
00:39:16,420 --> 00:39:21,570
cu înțelegerea dacă un fișier este rățoiește sau nu?

461
00:39:21,570 --> 00:39:26,910
Nu a fost de informații în huffile.c despre Huffeader.

462
00:39:26,910 --> 00:39:33,430
Stim ca fiecare fișier are un Huff Huffeader asociat cu acesta, cu un număr de magie

463
00:39:33,430 --> 00:39:37,240
precum și o serie de frecvențe pentru fiecare simbol

464
00:39:37,240 --> 00:39:39,570
, precum și o sumă de control.

465
00:39:39,570 --> 00:39:43,180
Știm asta, dar am luat, de asemenea, o privire la dump.c,

466
00:39:43,180 --> 00:39:49,120
în care a fost citit într-un fișier Huff.

467
00:39:49,120 --> 00:39:53,990
Și așa să faci asta, a trebuit să verifice dacă într-adevăr a fost rățoiește sau nu.

468
00:39:53,990 --> 00:40:03,380
Deci, poate că am putea folosi dump.c ca o structură de puff.c. nostru

469
00:40:03,380 --> 00:40:12,680
Înapoi la PSET 4 când am avut copy.c fișierul pe care copiat în triplete RGB

470
00:40:12,680 --> 00:40:14,860
și am interpretat că, pentru roman sau film polițist și Redimensionare,

471
00:40:14,860 --> 00:40:20,390
În mod similar, ceea ce ai putea face este doar să rulați comanda ca cp dump.c puff.c

472
00:40:20,390 --> 00:40:23,600
și de a folosi o parte din codul de acolo.

473
00:40:23,600 --> 00:40:28,210
Cu toate acestea, ea nu va fi la fel de simplă a unui proces de

474
00:40:28,210 --> 00:40:33,010
pentru traducerea dump.c dvs. în puff.c,

475
00:40:33,010 --> 00:40:36,160
dar cel puțin te dă pe undeva pentru a începe

476
00:40:36,160 --> 00:40:40,540
cu privire la modul pentru a se asigura că intrarea este de fapt rățoiește sau nu

477
00:40:40,540 --> 00:40:43,240
precum și alte câteva lucruri.

478
00:40:45,930 --> 00:40:50,250
Ne-am asigurat de utilizare corectă și a asigurat că de intrare este rățoiește.

479
00:40:50,250 --> 00:40:53,570
De fiecare dată când ne-am făcut că ne-am făcut verificarea noastra de eroare corespunzătoare,

480
00:40:53,570 --> 00:41:01,520
astfel returnarea și renunti funcție dacă apare un eșec, în cazul în care există o problemă.

481
00:41:01,520 --> 00:41:07,170
>> Acum, ceea ce dorim să facem este construirea copac real.

482
00:41:08,840 --> 00:41:12,640
Dacă ne uităm în Pădurea, există 2 funcții principale

483
00:41:12,640 --> 00:41:15,800
că am de gând să doriți să devină foarte familiarizat cu.

484
00:41:15,800 --> 00:41:23,870
Nu e planta funcție booleană care plantele un copac non-0 frecvență în interiorul pădurii nostru.

485
00:41:23,870 --> 00:41:29,250
Și deci nu te treci intr-un pointer la o pădure și un pointer la un copac.

486
00:41:32,530 --> 00:41:40,340
Intrebare rapida: Câte pădurile vei avea atunci când veți construi un copac Huffman?

487
00:41:44,210 --> 00:41:46,650
Padurea noastra este ca panza nostru, nu?

488
00:41:46,650 --> 00:41:50,800
Deci, vom avea doar o pădure, dar vom avea mai mulți arbori.

489
00:41:50,800 --> 00:41:57,590
Deci, înainte de a apela plantelor, probabil ai de gând să doriți să vă padure.

490
00:41:57,590 --> 00:42:04,430
Există o comandă pentru că, dacă te uiți în forest.h privind modul în care puteți face o pădure.

491
00:42:04,430 --> 00:42:09,270
Puteți planta un copac. Știm cum să faci asta.

492
00:42:09,270 --> 00:42:11,590
Și apoi puteți alege, de asemenea, un copac din pădure,

493
00:42:11,590 --> 00:42:17,540
eliminarea unui copac cu cel mai mic greutate și oferindu-vă pointer la asta.

494
00:42:17,540 --> 00:42:23,090
Gândindu-mă la momentul făceam exemple noi înșine,

495
00:42:23,090 --> 00:42:27,980
cand am fost l întocmirea, pur și simplu adăugat doar link-urile.

496
00:42:27,980 --> 00:42:31,680
Dar aici în loc de a adăuga doar link-uri,

497
00:42:31,680 --> 00:42:40,630
cred că de ea mai mult ca esti eliminarea acestor 2 din noduri și apoi înlocuirea acesteia cu o alta.

498
00:42:40,630 --> 00:42:44,200
Pentru a exprima faptul că, în ceea ce privește alegerea și de răsaduri,

499
00:42:44,200 --> 00:42:48,840
te cules 2 copaci și apoi plantarea alt copac

500
00:42:48,840 --> 00:42:54,060
care are acele 2 copaci care ați ales ca si copii.

501
00:42:57,950 --> 00:43:05,280
Pentru a construi arborele Huffman, puteți citi în simbolurile și frecvențele în ordine

502
00:43:05,280 --> 00:43:10,790
deoarece oferă Huffeader că, pentru a vă,

503
00:43:10,790 --> 00:43:14,250
vă oferă o gamă de frecvențe.

504
00:43:14,250 --> 00:43:19,660
Astfel încât să puteți merge mai departe și să ignore pur și simplu nimic cu 0 în ea

505
00:43:19,660 --> 00:43:23,760
pentru ca nu vrem 256 frunze la sfârșitul anului acesta.

506
00:43:23,760 --> 00:43:27,960
Dorim doar numărul de frunze, care sunt de caractere

507
00:43:27,960 --> 00:43:31,600
care sunt utilizate efectiv în fișierul.

508
00:43:31,600 --> 00:43:37,590
Puteți citi în aceste simboluri, și fiecare dintre aceste simboluri care au non-0 frecvențe,

509
00:43:37,590 --> 00:43:40,440
cei care vor fi copaci.

510
00:43:40,440 --> 00:43:45,990
Ce puteți face este de fiecare dată când citesc în frecvență un simbol non-0,

511
00:43:45,990 --> 00:43:50,660
puteți planta acel copac în pădure.

512
00:43:50,660 --> 00:43:56,620
După ce planta copaci în pădure, vă puteți alătura acestor copaci ca frații,

513
00:43:56,620 --> 00:44:01,130
așa merge înapoi la plantarea și în cazul în care alegeți 2 și apoi a plantelor 1,

514
00:44:01,130 --> 00:44:05,820
în cazul în care o instalație care le este mamă a doi copii pe care i-ați ales.

515
00:44:05,820 --> 00:44:11,160
Deci, atunci rezultatul final va fi un singur copac în pădure ta.

516
00:44:16,180 --> 00:44:18,170
Asta e modul în care vă construiți arborele.

517
00:44:18,170 --> 00:44:21,850
>> Există mai multe lucruri care ar putea merge greșit aici

518
00:44:21,850 --> 00:44:26,580
pentru că avem de-a face cu a face copaci noi și care se ocupă cu pointeri si lucruri de genul asta.

519
00:44:26,580 --> 00:44:30,450
Înainte de a atunci când am de-a face cu pointeri,

520
00:44:30,450 --> 00:44:36,580
ori de câte ori am malloc'd am vrut să ne asigurăm că nu ne-a returnat o valoare pointer NULL.

521
00:44:36,580 --> 00:44:42,770
Deci, la mai multe etape în cadrul acestui proces se vor fi mai multe cazuri

522
00:44:42,770 --> 00:44:45,920
în cazul în care programul ar putea eșua.

523
00:44:45,920 --> 00:44:51,310
Ce vrei să faci este doriți să vă asigurați că ați ocupe de aceste erori,

524
00:44:51,310 --> 00:44:54,580
și în spec. se spune să se ocupe de ele grațios,

525
00:44:54,580 --> 00:45:00,280
asa ca imprima un mesaj de la utilizatorul spunându-le de ce trebuie sa renunte la programul

526
00:45:00,280 --> 00:45:03,050
si apoi iesi cu promptitudine.

527
00:45:03,050 --> 00:45:09,490
Pentru a face acest lucru eroare de manipulare, amintiți-vă că doriți să-l verificați

528
00:45:09,490 --> 00:45:12,160
de fiecare dată că ar putea exista un eșec.

529
00:45:12,160 --> 00:45:14,660
De fiecare data cand faci un pointer nou

530
00:45:14,660 --> 00:45:17,040
doriți să vă asigurați că este de succes.

531
00:45:17,040 --> 00:45:20,320
Înainte de a ceea ce am folosit pentru a face este de a face un pointer nou și malloc-l,

532
00:45:20,320 --> 00:45:22,380
si atunci ne-ar verifica dacă această indicatorul este NULL.

533
00:45:22,380 --> 00:45:25,670
Deci nu vor fi unele cazuri în care tocmai ați putea face asta,

534
00:45:25,670 --> 00:45:28,610
dar, uneori, esti de asteptare de fapt, o funcție

535
00:45:28,610 --> 00:45:33,100
și în această funcție, că e cel care face mallocing.

536
00:45:33,100 --> 00:45:39,110
În acest caz, dacă ne uităm înapoi la anumite funcții în cadrul codului,

537
00:45:39,110 --> 00:45:42,260
unele dintre ele sunt funcții booleene.

538
00:45:42,260 --> 00:45:48,480
În cazul în abstract, în cazul în care avem o functie booleana numit foo,

539
00:45:48,480 --> 00:45:54,580
practic, putem presupune că, în afară de a face tot ce face foo,

540
00:45:54,580 --> 00:45:57,210
din moment ce este o funcție booleană, se returneaza true sau false -

541
00:45:57,210 --> 00:46:01,300
true în caz de succes, dacă nu false.

542
00:46:01,300 --> 00:46:06,270
Așa că vrem să verifice dacă valoarea returnată de foo este adevărată sau falsă.

543
00:46:06,270 --> 00:46:10,400
Dacă e fals, ceea ce înseamnă că am de gând să doriți să imprimați un fel de mesaj

544
00:46:10,400 --> 00:46:14,390
apoi părăsiți programul.

545
00:46:14,390 --> 00:46:18,530
Ceea ce vrem să facem este să verificați valoarea returnată de foo.

546
00:46:18,530 --> 00:46:23,310
Dacă foo returneaza false, atunci știm că am întâlnit un fel de eroare

547
00:46:23,310 --> 00:46:25,110
și avem nevoie pentru a iesi programul nostru.

548
00:46:25,110 --> 00:46:35,600
O modalitate de a face acest lucru este să aibă o condiție în cazul în care funcția în sine este starea dumneavoastră.

549
00:46:35,600 --> 00:46:39,320
Spune foo ia în x.

550
00:46:39,320 --> 00:46:43,390
Putem avea, ca o condiție în cazul în care (foo (x)).

551
00:46:43,390 --> 00:46:50,900
Practic, asta înseamnă că dacă la sfârșitul anului de executare foo-l returneaza true,

552
00:46:50,900 --> 00:46:57,390
atunci putem face acest lucru, deoarece funcția trebuie să evalueze foo

553
00:46:57,390 --> 00:47:00,500
în scopul de a evalua starea întreg.

554
00:47:00,500 --> 00:47:06,500
Deci asta e modul în care puteți face ceva în cazul în care funcția returnează adevărat și este de succes.

555
00:47:06,500 --> 00:47:11,800
Dar când ești verificarea erorilor, doriți doar să renunțe dacă funcția dumneavoastră returnează false.

556
00:47:11,800 --> 00:47:16,090
Ce ai putea face este sa adaugi doar un == fals sau doar adaugă o bubuitură în fața sa

557
00:47:16,090 --> 00:47:21,010
si apoi ai if (! foo).

558
00:47:21,010 --> 00:47:29,540
În cadrul acestui organism de această condiție le-ar fi toate de tratare a erorilor,

559
00:47:29,540 --> 00:47:36,940
asa ca, "Nu am putut crea acest copac" și apoi să se întoarcă 1 sau ceva de genul asta.

560
00:47:36,940 --> 00:47:43,340
Ceea ce face, însă, este că, chiar dacă foo revenit false -

561
00:47:43,340 --> 00:47:46,980
Spune foo returneaza true.

562
00:47:46,980 --> 00:47:51,060
Apoi, nu trebuie să sun din nou foo. Asta e o concepție greșită comună.

563
00:47:51,060 --> 00:47:54,730
Pentru că a fost în stare ta, este deja evaluate,

564
00:47:54,730 --> 00:47:59,430
astfel încât aveți deja rezultatul dacă utilizați face copac sau ceva de genul asta

565
00:47:59,430 --> 00:48:01,840
sau ale plantelor sau de preluare sau ceva de genul.

566
00:48:01,840 --> 00:48:07,460
Ea are deja acea valoare. E deja executate.

567
00:48:07,460 --> 00:48:10,730
Deci, este util să folosiți funcții booleene ca condiție

568
00:48:10,730 --> 00:48:13,890
pentru că dacă aveți sau nu executa de fapt, corpul buclei,

569
00:48:13,890 --> 00:48:18,030
, execută funcția oricum.

570
00:48:22,070 --> 00:48:27,330
>> Două noastră de a Ultimul pas este scris mesajul la dosar.

571
00:48:27,330 --> 00:48:33,070
După ce vom construi arborele Huffman, apoi scris mesajul la dosar este destul de simplă.

572
00:48:33,070 --> 00:48:39,260
E destul de simplu acum să urmeze doar 0s și 1s.

573
00:48:39,260 --> 00:48:45,480
Și astfel, prin convenție, știm că într-un copac Huffman a 0s indica plecat

574
00:48:45,480 --> 00:48:48,360
și indică dreptul de 1s.

575
00:48:48,360 --> 00:48:53,540
Deci, dacă ați citit în bit cu bit, de fiecare dată când obțineți un 0

576
00:48:53,540 --> 00:48:59,100
veți urmări ramura stânga, și apoi de fiecare dată când citesc în un 1

577
00:48:59,100 --> 00:49:02,100
ai de gând să urmeze ramura dreapta.

578
00:49:02,100 --> 00:49:07,570
Și apoi ai de gând să continue până când te-a lovit o frunză

579
00:49:07,570 --> 00:49:11,550
deoarece frunzele vor fi la sfârșitul sucursale.

580
00:49:11,550 --> 00:49:16,870
Cum putem spune dacă ne-am lovit-o frunză sau nu?

581
00:49:19,800 --> 00:49:21,690
Am spus-o înainte.

582
00:49:21,690 --> 00:49:24,040
[Elev] În cazul în care indicii sunt nule. Da >>.

583
00:49:24,040 --> 00:49:32,220
Noi putem spune dacă ne-am lovit o frunză în cazul în care indicii de copaci, atât stânga și dreapta sunt nule.

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

585
00:49:34,110 --> 00:49:40,320
Știm că vrem să citesc în bit cu bit în fișierul nostru Huff.

586
00:49:43,870 --> 00:49:51,220
Așa cum am văzut înainte în dump.c, ceea ce au făcut ei este citit în bit cu bit în dosarul Huff

587
00:49:51,220 --> 00:49:54,560
si doar tipărite ce acei biți au fost.

588
00:49:54,560 --> 00:49:58,430
Noi nu suntem de gând să faci asta. Vom face ceva care este un pic mai complex.

589
00:49:58,430 --> 00:50:03,620
Dar ceea ce putem face este să putem avea că pic de cod care citeste in pentru a biți.

590
00:50:03,620 --> 00:50:10,250
Aici avem biti reprezentand putin curent pe care suntem pe.

591
00:50:10,250 --> 00:50:15,520
Aceasta are grija de iterarea tuturor biți din fișierul până când te-a lovit la sfârșitul fișierului.

592
00:50:15,520 --> 00:50:21,270
Bazat pe faptul că, atunci ai de gând să doriți să aveți un fel de iterator

593
00:50:21,270 --> 00:50:26,760
pentru a traversa copac.

594
00:50:26,760 --> 00:50:31,460
Și apoi, dacă pe bit este 0 sau 1,

595
00:50:31,460 --> 00:50:36,920
ai de gând să doriți să mutați, fie că iterator la stânga sau mutați-l la dreapta

596
00:50:36,920 --> 00:50:44,080
tot drumul până când a lovit o frunză, astfel încât tot drumul până la acel nod pe care esti pe

597
00:50:44,080 --> 00:50:48,260
nu indică nici mai noduri.

598
00:50:48,260 --> 00:50:54,300
De ce putem face acest lucru cu un fișier Huffman, dar nu codul Morse?

599
00:50:54,300 --> 00:50:56,610
Pentru că în codul Morse e un pic de ambiguitate.

600
00:50:56,610 --> 00:51:04,440
Am putea fi ca, Oh, așteptați, ne-am lovit-o scrisoare de-a lungul drum, așa că poate aceasta este scrisoarea noastră,

601
00:51:04,440 --> 00:51:08,150
întrucât în ​​cazul în care am continuat doar un pic mai mult, atunci ne-ar fi lovit o altă scrisoare.

602
00:51:08,150 --> 00:51:13,110
Dar asta nu se va întâmpla în codificarea Huffman,

603
00:51:13,110 --> 00:51:17,540
astfel încât să putem fi siguri că singurul mod în care vom lovi un caracter

604
00:51:17,540 --> 00:51:23,480
este în cazul în care copiii nod stânga și dreapta sunt nule.

605
00:51:28,280 --> 00:51:32,350
>> În cele din urmă, dorim să eliberăm toată memoria noastră.

606
00:51:32,350 --> 00:51:37,420
Ne dorim atât de aproape de fișier Huff pe care le-am fost de-a face cu

607
00:51:37,420 --> 00:51:41,940
precum și eliminarea ca toate copacii din pădure noastră.

608
00:51:41,940 --> 00:51:46,470
Bazat pe punerea în aplicare tau, esti, probabil, de gând să doriți să apelați eliminați pădure

609
00:51:46,470 --> 00:51:49,780
în loc de fapt, trece prin toate copaci singuri.

610
00:51:49,780 --> 00:51:53,430
Dar, dacă ați făcut orice copaci temporare, veți dori să eliberați asta.

611
00:51:53,430 --> 00:51:59,060
Tu știi cel mai bine codul, astfel încât să știi unde te alocare de memorie.

612
00:51:59,060 --> 00:52:04,330
Și așa, dacă te duci în, începeți prin chiar F'ing de control pentru malloc,

613
00:52:04,330 --> 00:52:08,330
ori de câte ori văd malloc și asigurându-vă că vă elibera toate că

614
00:52:08,330 --> 00:52:10,190
dar apoi trece printr-cod,

615
00:52:10,190 --> 00:52:14,260
înțelegerea în cazul în care s-ar putea s-au alocat de memorie.

616
00:52:14,260 --> 00:52:21,340
De obicei, s-ar putea spune doar, "La sfârșitul unui fișier Mă duc să elimine pădure în pădure mea,"

617
00:52:21,340 --> 00:52:23,850
atât de clar încât practic de memorie, fără ca,

618
00:52:23,850 --> 00:52:28,310
"Si apoi am, de asemenea, de gând să închidă fișierul și apoi programul meu este de gând să renunțe."

619
00:52:28,310 --> 00:52:33,810
Dar este faptul că singura dată când se închide programul tău?

620
00:52:33,810 --> 00:52:37,880
Nu, pentru că, uneori, nu ar fi putut fi o eroare care sa întâmplat.

621
00:52:37,880 --> 00:52:42,080
Poate nu am putut deschide un fișier sau nu am putut face un alt copac

622
00:52:42,080 --> 00:52:49,340
sau un fel de eroare sa întâmplat în procesul de alocare de memorie și așa sa întors NULL.

623
00:52:49,340 --> 00:52:56,710
O eroare a avut loc și apoi ne-am întors și ieși.

624
00:52:56,710 --> 00:53:02,040
Deci, apoi doriți să vă asigurați că în orice moment posibil ca programul dvs. poate renunta,

625
00:53:02,040 --> 00:53:06,980
doriți să eliberați toate memoria ta acolo.

626
00:53:06,980 --> 00:53:13,370
Nu este doar de gând să fie la sfârșitul foarte de funcția principală pe care ai renunțat codul.

627
00:53:13,370 --> 00:53:20,780
Vrei să te uiți înapoi la fiecare instanță a codului potențial s-ar putea întoarce prematur

628
00:53:20,780 --> 00:53:25,070
și apoi liber, indiferent de memorie are sens.

629
00:53:25,070 --> 00:53:30,830
Spuneți că ați avut chemat face de pădure și care a returnat false.

630
00:53:30,830 --> 00:53:34,230
Atunci probabil nu va fi nevoie pentru a elimina padure

631
00:53:34,230 --> 00:53:37,080
pentru că nu aveți încă o pădure.

632
00:53:37,080 --> 00:53:42,130
Dar la fiecare punct din cod unde s-ar putea întoarce prematur

633
00:53:42,130 --> 00:53:46,160
doriți să vă asigurați că ați elibera orice memorie este posibil.

634
00:53:46,160 --> 00:53:50,020
>> Așa că atunci când avem de a face cu eliberarea de memorie și având scurgeri potențiale,

635
00:53:50,020 --> 00:53:55,440
vrem să folosească nu numai judecata noastră și logica noastră

636
00:53:55,440 --> 00:54:01,850
dar folosesc, de asemenea, Valgrind pentru a determina dacă ne-am eliberat toate memorie în mod corect sau nu.

637
00:54:01,850 --> 00:54:09,460
Puteți rula fie pe Puff Valgrind și apoi va trebui să treci de asemenea, sa

638
00:54:09,460 --> 00:54:14,020
numărul corect de argumente de linie de comandă pentru a Valgrind.

639
00:54:14,020 --> 00:54:18,100
Puteți rula asta, dar rezultatul este un pic criptic.

640
00:54:18,100 --> 00:54:21,630
Am ajuns un pic folosit pentru a-l cu Speller, dar avem nevoie de încă un pic de ajutor mai mult,

641
00:54:21,630 --> 00:54:26,450
asa apoi rulează cu câteva steaguri mai mult, cum ar fi scurgeri de check = complet,

642
00:54:26,450 --> 00:54:32,040
care va da, probabil, ne unii de ieșire de mai mult ajutor pe Valgrind.

643
00:54:32,040 --> 00:54:39,040
>> Apoi, un alt sfat util atunci când sunteți depanare este comanda dif.

644
00:54:39,040 --> 00:54:48,520
Puteți accesa punerea în aplicare personalului de Huff, executați pe un fișier text,

645
00:54:48,520 --> 00:54:55,400
și transmite apoi într-un fișier binar, un binar Huff fișier, să fie specifice.

646
00:54:55,400 --> 00:54:59,440
Apoi, dacă aveți o puf ta cu privire la acest fisier binar,

647
00:54:59,440 --> 00:55:03,950
atunci în mod ideal, fișierul text scoase este de gând să fie identice

648
00:55:03,950 --> 00:55:08,200
la cel original pe care l-ai trecut inch

649
00:55:08,200 --> 00:55:15,150
Aici eu sunt, folosind hth.txt ca exemplu, si asta e cel vorbit despre în spec. ta.

650
00:55:15,150 --> 00:55:21,040
Asta e literalmente doar HTH și apoi o linie nouă.

651
00:55:21,040 --> 00:55:30,970
Dar cu siguranta se simt liber și vă sunt cu siguranta încurajați să folosească exemple mai lungi

652
00:55:30,970 --> 00:55:32,620
pentru fișierul text.

653
00:55:32,620 --> 00:55:38,110
>> Puteți lua chiar și o șansă la comprimarea poate și apoi decomprima

654
00:55:38,110 --> 00:55:41,600
unele dintre fișierele pe care le-ați utilizat în Speller ca Război și pace

655
00:55:41,600 --> 00:55:46,710
sau Jane Austen sau ceva de genul asta - care ar fi un fel de rece - sau Austin Powers,

656
00:55:46,710 --> 00:55:51,880
un fel de a face cu fișiere mai mari, deoarece nu ne-ar veni să-l

657
00:55:51,880 --> 00:55:55,590
daca am folosit instrumentul următoarea aici, ls-l.

658
00:55:55,590 --> 00:56:01,150
Suntem obișnuiți să ls, care enumeră, practic toate componentele în directorul nostru curent.

659
00:56:01,150 --> 00:56:07,860
Trece în pavilion-l afișează, de fapt dimensiunea acestor fișiere.

660
00:56:07,860 --> 00:56:12,690
Dacă te duci prin spec. PSET, de fapt tu plimba prin crearea de fișier binar,

661
00:56:12,690 --> 00:56:16,590
huffing de el, și veți vedea că pentru fisiere foarte mici

662
00:56:16,590 --> 00:56:23,910
costul spațiului de comprimare ea și traducerea tuturor informațiilor

663
00:56:23,910 --> 00:56:26,980
a tuturor frecvențelor și lucruri de genul asta depășește beneficiul real

664
00:56:26,980 --> 00:56:30,000
de a comprima fișierul în primul rând.

665
00:56:30,000 --> 00:56:37,450
Dar dacă îl executați pe unele fișiere de text mai lungi, atunci s-ar putea vedea că începe pentru a obține niște beneficii

666
00:56:37,450 --> 00:56:40,930
în comprimarea acestor fișiere.

667
00:56:40,930 --> 00:56:46,210
>> Și apoi în cele din urmă, avem vechiul nostru prieten GDB, care este cu siguranta va veni la îndemână prea.

668
00:56:48,360 --> 00:56:55,320
>> Nu avem întrebări pe copaci Huff sau procesul, probabil, de a face copaci

669
00:56:55,320 --> 00:56:58,590
sau orice alte întrebări cu privire Puff Huff'n?

670
00:57:00,680 --> 00:57:02,570
Bine. Voi rămâne în jurul valorii de un pic.

671
00:57:02,570 --> 00:57:06,570
>> Mulțumesc, tuturor. Acest lucru a fost Walkthrough 6. Și noroc.

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