1
00:00:00,000 --> 00:00:02,210
[Powered by Google Translate] [연습 - 문제 세트 6]

2
00:00:02,210 --> 00:00:04,810
[Zamyla 찬 - 하버드 대학교 (Harvard University)]

3
00:00:04,810 --> 00:00:07,240
[이 CS50입니다. - CS50.TV]

4
00:00:07,240 --> 00:00:12,180
>> 안녕하세요 여러분, 연습 6에 오신 것을 환영합니다 Huff'n 퍼프합니다.

5
00:00:12,180 --> 00:00:17,440
Huff'n 퍼프에서 우리는하는 일이 허프만 압축 파일로 처리 될 것입니다

6
00:00:17,440 --> 00:00:20,740
다음, 백업을 피게 때문에, 그것을 압축을 푸는

7
00:00:20,740 --> 00:00:25,810
우리는 0s와 1S 사용자가 우리에게 보내는에서 번역 할 수 있도록

8
00:00:25,810 --> 00:00:30,660
그리고 원래 텍스트로 다시 변환합니다.

9
00:00:30,660 --> 00:00:34,360
이 도구의 일부를 만나러가는 때문에 Pset 6 정말 멋진 될 것입니다

10
00:00:34,360 --> 00:00:41,730
이 1 멋지다 개념으로 통합을 pset 4 pset 5 종류에 사용되는

11
00:00:41,730 --> 00:00:43,830
당신이 생각 올 때.

12
00:00:43,830 --> 00:00:50,110
>> 또한, 확실하게, pset 4 및 5는 우리가 제공해야한다고 가장 어려운 psets했다.

13
00:00:50,110 --> 00:00:53,950
그럼 지금부터, 우리는 C에서 1 개 pset가

14
00:00:53,950 --> 00:00:56,480
그리고 그 후 우리는 웹 프로그래밍에있어.

15
00:00:56,480 --> 00:01:02,310
따라서 CS50에서 가장 힘든 고비 점점을 위해 자신을 축하합니다.

16
00:01:03,630 --> 00:01:09,760
>> Huff'n 퍼프에의 이동이 pset에 대한 도구 상자는 허프만 나무가 될 것이다

17
00:01:09,760 --> 00:01:14,700
그래서 이진 나무 작업뿐만 아니라 구체적으로 허프만 나무뿐만 아니라 어떻게 이해

18
00:01:14,700 --> 00:01:16,240
어떻게가 건설하고 있습니다.

19
00:01:16,240 --> 00:01:20,210
그리고 우리는이 pset에 대해 배포 코드를 많이 할거야

20
00:01:20,210 --> 00:01:22,480
우리는 코드의 일부 실제로 만나러 와줄 거에요

21
00:01:22,480 --> 00:01:24,670
우리는 아직 완전히 이해되지 않을 수 있습니다

22
00:01:24,670 --> 00:01:30,080
그리고 그 후에는 함께. h 파일. C 파일 수 있지만

23
00:01:30,080 --> 00:01:34,300
우리에게 우리가 이러한 기능이 어떻게 작동하는지 알 수 있도록 필요로하는 충분한 이해를 제공합니다

24
00:01:34,300 --> 00:01:38,100
적어도 무엇을 어떻게해야 - 자신의 입력 및 출력 -

25
00:01:38,100 --> 00:01:40,760
우리는 블랙 박스에 무슨 일이 일어나는 건지 모르겠어 경우에도

26
00:01:40,760 --> 00:01:44,090
또는 내 블랙 박스에 일어나는 일을 이해하지 않습니다.

27
00:01:44,090 --> 00:01:49,400
그리고 마지막으로, 평소처럼, 우리는 새로운 데이터 구조를 다루고있는

28
00:01:49,400 --> 00:01:51,840
그 노드의 특정 유형은 어떤 일을 가리

29
00:01:51,840 --> 00:01:56,080
그래서 여기에 디자인 과정뿐만 아니라 펜과 종이를 가지고

30
00:01:56,080 --> 00:01:58,470
언제 당신이 pset가 작동하는 방법을 알아 내려고 노력 중입니다

31
00:01:58,470 --> 00:02:00,520
뿐만 아니라 디버깅시.

32
00:02:00,520 --> 00:02:06,140
이 값이 무엇인지 내려 동안, 당신의 펜과 종이와 함께 GDB를 가질 수

33
00:02:06,140 --> 00:02:09,320
위치가 화살표가 가리키고, 그와 같은 것들입니다.

34
00:02:09,320 --> 00:02:13,720
>> 먼저 허프만 나무를 살펴 보자.

35
00:02:13,720 --> 00:02:19,600
허프만 나무 각 노드는 어린이 2 인이 즉, 이진 나무입니다.

36
00:02:19,600 --> 00:02:24,870
허프만 나무에서 특징입니다 가장 자주 값을

37
00:02:24,870 --> 00:02:27,140
가장 적은 비트에 의해 표현된다.

38
00:02:27,140 --> 00:02:32,690
우리는 모스 코드의 강의 예제, 통합 종류의 어떤 편지 보았다.

39
00:02:32,690 --> 00:02:38,030
당신은 예를 들어 A 또는 E를 번역하려는 경우

40
00:02:38,030 --> 00:02:43,940
당신이 자주 번역하고 있으므로 대신 비트의 전체 집합을 사용할 필요

41
00:02:43,940 --> 00:02:48,640
그 일반적인 데이터 형식에 할당, 당신은 이하로 내려 압축

42
00:02:48,640 --> 00:02:53,730
그리고 표현이 편지는 빈도 이상 비트로 표현

43
00:02:53,730 --> 00:02:59,840
당신이 그 문자가 표시되는 주파수를 무게 때 그런 여유가 할수 있기 때문이다.

44
00:02:59,840 --> 00:03:03,020
우리는 허프만 나무에 여기 같은 생각을

45
00:03:03,020 --> 00:03:12,360
우리가 어디에 체인, 특정 문자까지가는 ​​경로의 종류를하고 있습니다.

46
00:03:12,360 --> 00:03:14,470
그리고 가장 빈도가 문자

47
00:03:14,470 --> 00:03:17,940
가장 적은 비트로 표현할 될 예정입니다.

48
00:03:17,940 --> 00:03:22,020
>> 당신은 허프만 트리를 구성하는 방법

49
00:03:22,020 --> 00:03:27,430
텍스트에 표시되는 문자를 모두 배치하는 것입니다

50
00:03:27,430 --> 00:03:30,630
하고 주파수를 계산, 얼마나 자주 나타납니다.

51
00:03:30,630 --> 00:03:33,880
이 중 그 글자가 나타납니다 횟수의 수있을 수

52
00:03:33,880 --> 00:03:40,270
아니면 하나 하나가 나타납니다 얼마나 많은 모든 문자에서의 비율입니다.

53
00:03:40,270 --> 00:03:44,270
그리고 당신이 할 일은 일단 그 매핑에서의 모든이 있습니다

54
00:03:44,270 --> 00:03:49,060
다음은 2 낮은 주파수를 찾아 다음 형제로 가입

55
00:03:49,060 --> 00:03:55,660
곳에서 부모 노드는 2 명의 어린이의 합계입니다 주파수가 있습니다.

56
00:03:55,660 --> 00:04:00,870
그리고 나서 대회로 그런 말을 왼쪽 노드,

57
00:04:00,870 --> 00:04:03,770
당신은 0 지점을 따라 그렇게 따라

58
00:04:03,770 --> 00:04:08,140
그리고 가장 오른쪽 노드는 한 가지입니다.

59
00:04:08,140 --> 00:04:16,040
우리가 모스 부호에서 본 바와 같이, 한 잡았다 저 사람이 당신은 삐와 삐가 있다면

60
00:04:16,040 --> 00:04:18,120
그것은 모호한했다.

61
00:04:18,120 --> 00:04:22,430
이 중 한 글자 될 수 또는 2 문자의 순서가 될 수 있습니다.

62
00:04:22,430 --> 00:04:27,790
그리고 무엇 허프만 나무가 않는 것은 캐릭터의 성격 때문에

63
00:04:27,790 --> 00:04:34,140
또는 최종 실제 문자 분기의 마지막 노드 것 -

64
00:04:34,140 --> 00:04:39,300
우리가 단풍으로 사람들에게 참조 -의 미덕하여 모호가 될 수 없습니다

65
00:04:39,300 --> 00:04:45,160
당신이 비트 시리즈를 인코딩하려고하는 편지의 관점에서

66
00:04:45,160 --> 00:04:50,670
때문에 한 문자를 나타냅니다 비트를 따라 어디 선가 갑자기

67
00:04:50,670 --> 00:04:55,960
당신은 다른 모든 편지가 발생하고, 거기에 혼동이되지 않습니다.

68
00:04:55,960 --> 00:04:58,430
하지만 우리는 당신들이 실제로 볼 수 예제로 가서 그

69
00:04:58,430 --> 00:05:02,120
대신에 우리는 그 사실을 알리는.

70
00:05:02,120 --> 00:05:06,390
>> 가 허프만 트리의 간단한 예를 들어 보자.

71
00:05:06,390 --> 00:05:09,380
나는 12 자 길이 여기에 문자열을 수 있습니다.

72
00:05:09,380 --> 00:05:14,010
난 6 학사 2 C를,으로 4 있습니다.

73
00:05:14,010 --> 00:05:17,270
내 첫 번째 단계는 계산하는 것이다.

74
00:05:17,270 --> 00:05:20,760
몇 번이나 나타 납니까? 이 문자열에 4 번 나타납니다.

75
00:05:20,760 --> 00:05:25,060
B는 6 번 나타나며, C는 2 번 나타납니다.

76
00:05:25,060 --> 00:05:28,970
물론, 제가, 가장 자주 B를 사용하고 말할거야

77
00:05:28,970 --> 00:05:35,970
그래서 비트의 적은 수, 0s와 1S의 적은 번호로 B를 나타냅니다하고 싶습니다.

78
00:05:35,970 --> 00:05:42,600
그리고 나는 또한 C는 물론 0s와 1S의 가장 금액을 필요로 기대 겠어.

79
00:05:42,600 --> 00:05:48,550
우선 여기에 내가 뭘 주파수의 관점에서 오름차순으로 배치되어 있습니다.

80
00:05:48,550 --> 00:05:52,710
우리는 C와 A는 그 우리의이 가장 낮은 주파수 것을 참조하십시오.

81
00:05:52,710 --> 00:06:00,290
우리는 부모 노드를 만들고, 그 부모 노드는 관련 문자가 없습니다

82
00:06:00,290 --> 00:06:05,070
하지만 합이 주파수를 지니고 있습니다.

83
00:06:05,070 --> 00:06:08,780
합은 6입니다 2 + 4가됩니다.

84
00:06:08,780 --> 00:06:10,800
그럼 우리가 왼쪽 지점을 따르십시오.

85
00:06:10,800 --> 00:06:14,970
우리가 여섯 노드에 있다면, 우리는 C에 도착하려면 0를 따를 겁니다

86
00:06:14,970 --> 00:06:17,450
그리고 1 A.을 받기 위해

87
00:06:17,450 --> 00:06:20,300
이제 우리는 두 노드가 있습니다.

88
00:06:20,300 --> 00:06:23,920
우리는 값이 6이 후 우리는 또한 값이 6 다른 노드가 있습니다.

89
00:06:23,920 --> 00:06:28,550
그리고 그 둘은 최저 2뿐만 아니라 남아있는 단지 2뿐만 아니라 아르

90
00:06:28,550 --> 00:06:33,820
그래서 우리는 합계는 12이되면, 다른 부모의 사람들을 가입 할 수 있습니다.

91
00:06:33,820 --> 00:06:36,300
그래서 여기에 우리가 우리의 허프만 트리를

92
00:06:36,300 --> 00:06:40,020
B로 이동 곳, 그냥 비트 1 것

93
00:06:40,020 --> 00:06:45,430
다음에 가야 우리는 C가 00 문제 다음 01 가지고 것입니다.

94
00:06:45,430 --> 00:06:51,300
그래서 여기에 우리가 기본적으로 우리가 1 또는 2 비트 중 하나와 함께이 문자를 대표하고 있는지 확인

95
00:06:51,300 --> 00:06:55,160
어디에 예측 B은, 적어도이 있습니다.

96
00:06:55,160 --> 00:07:01,730
그리고, 우리는 C가 가장 많이가 예상하지만, 이렇게 작은 허프만 트리인데

97
00:07:01,730 --> 00:07:06,020
다음은로 중간에 어딘가에 반대하는 2 비트으로 표시됩니다.

98
00:07:07,820 --> 00:07:11,070
>> 그냥 허프만 트리의 또 다른 간단한 예를 통해 이동하려면,

99
00:07:11,070 --> 00:07:19,570
당신이 문자열을 가지고 말 "안녕하세요."

100
00:07:19,570 --> 00:07:25,360
당신이 할 일은 당신이 몇 번 H이에 나타나지 않는 말 것 처음이다?

101
00:07:25,360 --> 00:07:34,200
H 한 번하고 전자가 나타납니다 나타나면, 그리고 나서 우리는 두 번 나타나는 리터가

102
00:07:34,200 --> 00:07:36,580
및 O 한 번 게재.

103
00:07:36,580 --> 00:07:44,310
그리고 나서 우리는 비트의 최소 숫자로 표시 할 수있는 편지 기대?

104
00:07:44,310 --> 00:07:47,450
[학생] 리터. >>의 리터. 그래. 내가 맞아.

105
00:07:47,450 --> 00:07:50,730
우리는 리터는 비트의 최소 숫자로 표시 될 것으로 예상

106
00:07:50,730 --> 00:07:55,890
때문에 나는 "안녕하세요."문자열에 가장 많이 사용됩니다

107
00:07:55,890 --> 00:08:04,280
지금해야 할 일이 노드를 끌어 있습니다.

108
00:08:04,280 --> 00:08:15,580
나는 다음에 o이 전자 또 다른 1 다음 1을, H입니다, 1를 가지고 있고, -

109
00:08:15,580 --> 00:08:23,410
리터입니다 후 2 - 지금은 순서로하겠습니다.

110
00:08:23,410 --> 00:08:32,799
그래서 내가 허프만 트리를 빌드하는 방법은 최소 주파수와 2 노드를 찾을 것입니다라고

111
00:08:32,799 --> 00:08:38,010
그리고 부모 노드를 만들어 그들에게 형제를합니다.

112
00:08:38,010 --> 00:08:41,850
여기서 우리는 가장 낮은 주파수가있는 3 개의 노드가 있습니다. 모두 하나하고 있습니다.

113
00:08:41,850 --> 00:08:50,620
그래서 여기에 우리가 우리가 처음 연결하는 것 어느 선택합니다.

114
00:08:50,620 --> 00:08:54,850
자, 내가 H와 E를 선택 말한다.

115
00:08:54,850 --> 00:09:01,150
1의 합계 + 1은 2이지만,이 노드가와 관련된 편지를 가지고 있지 않습니다.

116
00:09:01,150 --> 00:09:04,440
단지의 가치를 보유하고 있습니다.

117
00:09:04,440 --> 00:09:10,950
이제 우리는 다음 2 낮은 주파수에서 봐.

118
00:09:10,950 --> 00:09:15,590
그래서 2 1. 그것도 그 2 수도 있지만이 하나를 선택하는거야.

119
00:09:15,590 --> 00:09:18,800
합은 3입니다.

120
00:09:18,800 --> 00:09:26,410
그리고 마지막으로, 난 단지 왜 그렇게 후 5되거나, 두 왼쪽을 갖추고 있습니다.

121
00:09:26,410 --> 00:09:32,010
그의 인코딩을 입력하면 다음 여기, 등, 예상,

122
00:09:32,010 --> 00:09:37,480
1 초 항상 오른쪽 지점과 0s은 왼쪽이 있습니다.

123
00:09:37,480 --> 00:09:45,880
그럼 우리가 2 일까지 단 1 비트와 다음 O로 표시 리터가

124
00:09:45,880 --> 00:09:52,360
그리고 2로 전자 후 H는 3 비트 아래로 떨어집니다.

125
00:09:52,360 --> 00:09:59,750
그럼 당신은 "안녕하세요"이 메시지를 전송할 수 대신 실제로 문자를 사용

126
00:09:59,750 --> 00:10:02,760
단지 0s와 1 초에 의해.

127
00:10:02,760 --> 00:10:07,910
그러나, 몇 가지 경우에 우리는 주파수와 관계가 있다는 기억 해요.

128
00:10:07,910 --> 00:10:11,900
우리는 하나 어쩌면 먼저 H와 O를 함께 할 수 있었 잖아.

129
00:10:11,900 --> 00:10:15,730
아니면 나중에 우리는 2로 표시 나도했을 때에

130
00:10:15,730 --> 00:10:19,410
뿐만 아니라 2에 의해 표현 하나를 가입, 우리는 어느 하나 연결했습니다 수 있습니다.

131
00:10:19,410 --> 00:10:23,630
>> 그리고 보낼 때 0s와 1S, 실제로 보장하지 않는

132
00:10:23,630 --> 00:10:27,090
받는 사람은 완전히 바로 박쥐에서 메시지를 읽을 수

133
00:10:27,090 --> 00:10:30,490
그들은 당신이 만든 어떤 결정이 잘되지 않을 수 있습니다 때문입니다.

134
00:10:30,490 --> 00:10:34,920
그래서 우리는 허프만 압축을 상대 할 때

135
00:10:34,920 --> 00:10:40,090
어떻게 든 우리가 결정하는 방법 우리 메시지의받는 사람에게 얘기를 해 -

136
00:10:40,090 --> 00:10:43,470
그들은 추가 정보의 일부 종류를 알 필요가

137
00:10:43,470 --> 00:10:46,580
압축 된 메시지를 기입해야합니다.

138
00:10:46,580 --> 00:10:51,490
그들은 나무가 실제로 어떻게 생겼는지 이해할 필요가

139
00:10:51,490 --> 00:10:55,450
우리는 실제로 이러한 결정을하는 방법.

140
00:10:55,450 --> 00:10:59,100
>> 여기 우리는, 실제 개수에 따라 예를하고 있었

141
00:10:59,100 --> 00:11:01,550
하지만 가끔은 또한 허프만 트리를 가질 수

142
00:11:01,550 --> 00:11:05,760
주파수에 따라 문자가 나타납니다, 그것은 동일한 과정을 할 것인지.

143
00:11:05,760 --> 00:11:09,090
난 여기, 비율 또는 분수의 측면에서 표현 하려는데

144
00:11:09,090 --> 00:11:11,290
그래서 여기에 똑같이.

145
00:11:11,290 --> 00:11:15,300
나는 2 최저 그들을 합계, 최저 다음 2 그들을 합계 찾을 수

146
00:11:15,300 --> 00:11:19,390
나는 전체 트리를 때까지.

147
00:11:19,390 --> 00:11:23,610
우리는 그것을 우리가 백분율 상대가 어느 쪽이든, 할 수 있지만

148
00:11:23,610 --> 00:11:27,760
우리가 일을 나누어하고 소수점을 상대하고있는 나보다는 떠 그

149
00:11:27,760 --> 00:11:30,900
우리는 머리의 데이터 구조에 대해 생각하는 경우.

150
00:11:30,900 --> 00:11:32,540
우리는 수레에 대해 뭘 알고 있지?

151
00:11:32,540 --> 00:11:35,180
우리가 수레 상대가 일반적인 문제는 무엇입니까?

152
00:11:35,180 --> 00:11:38,600
[학생] 부정확 한 연산. >> 그래. 부정확.

153
00:11:38,600 --> 00:11:43,760
때문에 부동 소수점 부정확으로 인해이 pset에 대해 우리는 확인하도록

154
00:11:43,760 --> 00:11:49,450
우리가 어떤 가치를 잃게하지 않는 것이, 우리는 실제로 수를 처리 할거야.

155
00:11:49,450 --> 00:11:54,880
당신이 여기의 구조로 보면, 퍼레이드 노드의 생각 있었다면

156
00:11:54,880 --> 00:12:01,740
당신이 녹색을 보면 그것이와 관련된 주파수가

157
00:12:01,740 --> 00:12:08,760
뿐만 아니라은 왼쪽 노드뿐만 아니라 오른쪽으로 노드 가리 킵니다.

158
00:12:08,760 --> 00:12:13,970
그리고 붉은 색이 아니라 그들과 관련된 문자가 있습니다.

159
00:12:13,970 --> 00:12:18,900
우리는 부모와 후 최종 노드에 대해 별도의 사람을 만들려고하지

160
00:12:18,900 --> 00:12:23,680
있는 우리는 단풍으로 참조, 오히려 그는 NULL 값을 갖게됩니다.

161
00:12:23,680 --> 00:12:31,050
모든 노드에 대해 우리는 문자 그 노드가 나타내는 기호를해야합니다

162
00:12:31,050 --> 00:12:40,490
다음 주파수뿐만 아니라 왼쪽 자녀뿐만 아니라 오른쪽 자녀에 대한 포인터.

163
00:12:40,490 --> 00:12:45,680
맨 아래에 있습니다 잎은 또한 노드 포인터를 가지고 것입니다

164
00:12:45,680 --> 00:12:49,550
자신의 왼쪽과 오른쪽에, 그러나 그 값이 실제 노드에 연결되지 않기 때문에,

165
00:12:49,550 --> 00:12:53,970
의 값은 어떤 것입니까? >> [학생] NULL. >>의 NULL. 그렇지.

166
00:12:53,970 --> 00:12:58,430
다음은 수레에 주파수를 나타낼 수있는 방법에 대한 예를 들어, 좋은 데요

167
00:12:58,430 --> 00:13:02,130
하지만 우리는 정수로 처리 할 것

168
00:13:02,130 --> 00:13:06,780
그래서 내가 한 모든이 데이터 유형을 변경합니다.

169
00:13:06,780 --> 00:13:09,700
>> 의는 복잡한 예제의 조금 더에 가자.

170
00:13:09,700 --> 00:13:13,360
그러나 지금 우리는 간단한 사항을 수행 한, 단지 동일한 프로세스입니다.

171
00:13:13,360 --> 00:13:20,290
당신은이 낮은 주파수를 찾아 주파수를 합계

172
00:13:20,290 --> 00:13:22,450
그는 부모 노드의 새로운 주파수입니다

173
00:13:22,450 --> 00:13:29,310
이는 다음 한 지점과 0 지회와 오른손으로는 왼쪽을 가리 킵니다.

174
00:13:29,310 --> 00:13:34,200
우리는 문자열 "이 cs50입니다,"이 있다면 우리는 T 언급 횟수를 계산

175
00:13:34,200 --> 00:13:38,420
H는 언급, 난, S, C, 5, 0.

176
00:13:38,420 --> 00:13:42,010
그리고 내가 여기서 한 것은 그냥 심어 빨간색 노드와 함께

177
00:13:42,010 --> 00:13:48,530
내 나무의 하단에 결국 이러한 문자를 가졌어요 말했다.

178
00:13:48,530 --> 00:13:51,740
사람들은 잎의 모든 될 것이다.

179
00:13:51,740 --> 00:13:58,200
그리고 제가 한 건, 제가 오름차순으로 주파수별로 정렬됩니다

180
00:13:58,200 --> 00:14:02,950
이 실제로 pset 코드가 않는 방법입니다

181
00:14:02,950 --> 00:14:07,550
이 빈도를 기준으로 정렬을하고 알파벳입니다.

182
00:14:07,550 --> 00:14:13,870
그래서 주파수의 알파벳 순으로 첫 번째와 다음 번호가 있습니다.

183
00:14:13,870 --> 00:14:18,520
그럼 뭐 내가 어떻게하면 제가 2 낮은을 찾을 것입니다. 그는 0과 5입니다.

184
00:14:18,520 --> 00:14:22,390
난 그것들을 표현한 다면요, 그 2입니다. 그럼 난 다음 2 최저를 찾아 계속합니다.

185
00:14:22,390 --> 00:14:26,100
사람들은 두 1 초이며, 다음이도이된다.

186
00:14:26,100 --> 00:14:31,570
지금은 내 다음 단계는, 가장 낮은 번호를 가입 할 간다는 걸 알고

187
00:14:31,570 --> 00:14:41,380
이는, 1 T이며, 다음 주파수로 2가있는 노드 중 하나를 선택.

188
00:14:41,380 --> 00:14:44,560
그래서 여기에 우리가 3 가지 옵션이 있습니다.

189
00:14:44,560 --> 00:14:47,980
나는 슬라이드를 위해 뭘 할 건지 단지 시각적으로 당신을 다시 정렬 할 수 있습니다

190
00:14:47,980 --> 00:14:51,790
수 있도록 당신은 내가 구축 중이 방법을 볼 수 있습니다.

191
00:14:51,790 --> 00:14:59,040
코드 및 배포 코드가 무슨 짓을할지 것은 T를 가입됩니다

192
00:14:59,040 --> 00:15:01,410
0과 5 노드와.

193
00:15:01,410 --> 00:15:05,060
그럼 다음 3 총액, 그리고 우리가이 프로세스를 계속하는 것이.

194
00:15:05,060 --> 00:15:08,660
2 2 이제 그럼, 4 해당 금액을 최저 수 있습니다.

195
00:15:08,660 --> 00:15:12,560
모두가 지금까지 따라? 좋아요.

196
00:15:12,560 --> 00:15:16,410
그 뒤 우리는 3까지 추가해야 3가

197
00:15:16,410 --> 00:15:21,650
당신이 너무 지저분 해지하지 않는 눈 때문에 볼 수 있도록 그래서, 난 그냥 전환거야.

198
00:15:21,650 --> 00:15:25,740
우리가 불과 2 노드를 가지고 나서 우리는 6이 후 우리의 마지막 단계는 지금

199
00:15:25,740 --> 00:15:30,440
우리는 10 개입니다 우리 트리의 루트를 만들기 위해 사람들을 합계.

200
00:15:30,440 --> 00:15:34,100
각 노드는 표현 때문에 수 (10)는, 의미가

201
00:15:34,100 --> 00:15:40,750
자신의 가치, 자신의 주파수 번호, 그들은 문자열에 나타난 몇 번했다

202
00:15:40,750 --> 00:15:46,350
그리고 우리는 문자열에 5 문자를 가지고 의미가 있도록 말이다.

203
00:15:48,060 --> 00:15:52,320
우리는 실제로 인코딩 방식을 올려다 보면

204
00:15:52,320 --> 00:15:56,580
예상대로, 내가하고 가장 자주 나타나는 초,

205
00:15:56,580 --> 00:16:01,350
비트 적은 숫자로 표시됩니다.

206
00:16:03,660 --> 00:16:05,660
>> 여기에주의하십시오.

207
00:16:05,660 --> 00:16:09,780
허프만 나무의 경우는 실제로 문제.

208
00:16:09,780 --> 00:16:13,670
대문자 S는 소문자 S 다릅니다.

209
00:16:13,670 --> 00:16:21,260
우리가 가진 경우, 소문자 s에 두 번 만 나타납니다 다음, 대문자로 "이 CS50이다"

210
00:16:21,260 --> 00:16:27,120
그 값으로 2 노드 될 후 대문자 S는 한 번만 것이다.

211
00:16:27,120 --> 00:16:33,440
당신이 실제로 여기에 추가 잎을 가지고 있기 때문에 그래서 당신의 나무 구조를 변경합니다.

212
00:16:33,440 --> 00:16:36,900
그러나 합 여전히 10 것입니다.

213
00:16:36,900 --> 00:16:39,570
즉, 우리가 실제로 체크섬를 호출 할 것이야

214
00:16:39,570 --> 00:16:44,060
카운트의 모든 추가.

215
00:16:46,010 --> 00:16:50,990
>> 이제 우리는 허프만 트리를 적용 한, 우리는 Huff'n 퍼프, pset에 뛰어 수 있습니다.

216
00:16:50,990 --> 00:16:52,900
우리는 질문의 한 부분으로 시작 할거야

217
00:16:52,900 --> 00:16:57,990
이은 진 나무와 그 주변에 작동하는 데 익숙해 얻을 수 있습니다 :

218
00:16:57,990 --> 00:17:03,230
그림 노드, 노드에 대한 자신의 typedef 구조체를 생성,

219
00:17:03,230 --> 00:17:07,230
그리고 이진 트리, 정렬있어 하나에 삽입하는 방법을보고,

220
00:17:07,230 --> 00:17:09,050
그, 그와 같은 일을 가로 지르는.

221
00:17:09,050 --> 00:17:14,560
그 지식은 확실히 Huff'n 퍼프 부분에 때 다이빙을 도움이 될 수 있습니다

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

223
00:17:19,150 --> 00:17:26,329
pset의 표준 버전에서 귀하의 작업은, 퐁퐁을 구현하는 것입니다

224
00:17:26,329 --> 00:17:30,240
그리고 해커 버전에서 작업 후우을 구현하는 것입니다.

225
00:17:30,240 --> 00:17:38,490
후우는 무엇을, 그것은 텍스트를 소요하고는 0s와 1 초에 변환

226
00:17:38,490 --> 00:17:41,990
저희가 주파수를 계산 어디에 위 한하는 절차

227
00:17:41,990 --> 00:17:50,970
다음 트리를 만든 후, 말 "내가 T하려면 어떻게해야합니까?"

228
00:17:50,970 --> 00:17:54,840
T는 100으로 표시됩니다, 그런 일,

229
00:17:54,840 --> 00:17:58,860
그리고 후우은 텍스트 다음 출력이 진을 것입니다.

230
00:17:58,860 --> 00:18:04,920
뿐만 아니라 우리는 우리가 메시지의 우리의 수신자를 허용 할 알고 있기 때문에

231
00:18:04,920 --> 00:18:11,790
동일한 나무를 다시, 또한 주파수 카운트에 대한 정보가 포함되어 있습니다.

232
00:18:11,790 --> 00:18:17,980
그런 다음 퐁퐁으로 우리는 0s와 1S의 바이너리 파일이 제공됩니다

233
00:18:17,980 --> 00:18:21,740
또한 주파수에 대한 정보를 제공.

234
00:18:21,740 --> 00:18:26,740
우리는있는 원본 메시지에 해당 0s와 1S 다시 모든 번역

235
00:18:26,740 --> 00:18:29,350
그래서 우리는 그런 압축을 푸는하고 있습니다.

236
00:18:29,350 --> 00:18:36,450
당신은 표준 버전을 수행하는 경우, 당신은 후우을 구현 할 필요가 없습니다

237
00:18:36,450 --> 00:18:39,290
그럼 당신은 후우의 직원 구현을 사용할 수 있습니다.

238
00:18:39,290 --> 00:18:42,080
하는 작업을 수행하는 방법에 대한 사양의 지시가 있습니다.

239
00:18:42,080 --> 00:18:48,780
당신은 특정 텍스트 파일에 후우의 직원 구현을 실행할 수 있습니다

240
00:18:48,780 --> 00:18:53,270
그리고 퍼프하기 위해 입력으로 해당 출력을 사용합니다.

241
00:18:53,270 --> 00:18:59,330
>> 내가 전에 언급했듯이, 우리는이 하나의 배포 코드를 많이 가지고 있어요.

242
00:18:59,330 --> 00:19:01,810
나는에서부터 시작 겠어.

243
00:19:01,810 --> 00:19:04,400
나는에 대부분의 시간을 보낼거야. H 파일

244
00:19:04,400 --> 00:19:07,660
우리는. H가 있기 때문에. C 파일에 있기 때문에

245
00:19:07,660 --> 00:19:11,650
그는 함수의 프로토 타입으로 우리를 제공합니다

246
00:19:11,650 --> 00:19:15,520
우리는 완전히 정확히 이해 할 필요가 없습니다 -

247
00:19:15,520 --> 00:19:20,280
당신이. C 파일에 어떤 일이 일어나고 있는지 이해하지 않으면, 너무 걱정하지 마세요

248
00:19:20,280 --> 00:19:23,600
그 어떤 힌트를 줄 수 있기 때문에하지만 확실히 살펴보세요

249
00:19:23,600 --> 00:19:29,220
그리고 다른 사람의 코드를 읽고에 익숙해 유용합니다.

250
00:19:38,940 --> 00:19:48,270
>> huffile.h을 보면, 댓글이 허프만 코딩 된 파일에 대한 추상화 계층을 선언합니다.

251
00:19:48,270 --> 00:20:01,660
우리가 내려 가면, 우리는 우리가 코드를해야 할 수도있는 256 기호의 최대 있다는 것을 참조하십시오.

252
00:20:01,660 --> 00:20:05,480
대문자와 소문자 - -이 알파벳의 모든 글자를 포함

253
00:20:05,480 --> 00:20:08,250
그리고 기호와 숫자 등

254
00:20:08,250 --> 00:20:11,930
그럼 여기서 우리는 허프만 코딩 된 파일을 식별하는 마법의 숫자가 있습니다.

255
00:20:11,930 --> 00:20:15,890
허프만 코드 내에서 그들은 특정 마법 번호가 할거야

256
00:20:15,890 --> 00:20:18,560
헤더와 연관된.

257
00:20:18,560 --> 00:20:21,110
이, 그냥 임의의 마법 번호 같이 보일 수 있습니다

258
00:20:21,110 --> 00:20:27,160
당신이 실제로 ASCII로 번역 으면, 실제로 발끈를 해보면.

259
00:20:27,160 --> 00:20:34,290
여기 허프만 인코딩 파일에 대한 구조체가 있습니다.

260
00:20:34,290 --> 00:20:39,670
후우 파일과 관련된 이러한 특성의 모든이 있어요.

261
00:20:39,670 --> 00:20:47,080
그런 다음 여기 우리가 후우 파일에 대한 헤더를 가지고, 그래서 우리는 Huffeader 전화

262
00:20:47,080 --> 00:20:50,810
대신 어쨌든 같은 소리 때문에 여분의 H를 추가.

263
00:20:50,810 --> 00:20:52,720
귀여운.

264
00:20:52,720 --> 00:20:57,790
우리는과 관련된 매직 넘버가 있습니다.

265
00:20:57,790 --> 00:21:09,040
는 실제 후우 파일의 경우, 최대 위의이 마법 하나 번호 것 같네요.

266
00:21:09,040 --> 00:21:14,720
그리고 그 배열을해야합니다.

267
00:21:14,720 --> 00:21:18,750
따라서 각 기호에 대해, 그 중 256, 있습니다

268
00:21:18,750 --> 00:21:24,760
그것은 그 기호의 주파수가 후우 파일 내에 어떤 목록을 표시 할거야.

269
00:21:24,760 --> 00:21:28,090
그리고 마지막으로, 우리는 주파수에 대한 체크섬이

270
00:21:28,090 --> 00:21:32,160
이는 그 주파수의 합해야합니다.

271
00:21:32,160 --> 00:21:36,520
그럼 증거가 Huffeader입니다.

272
00:21:36,520 --> 00:21:44,600
그런 다음 우리는 후우 파일에 다음 비트를 반환 일부 기능이

273
00:21:44,600 --> 00:21:52,580
뿐만 아니라 hfclose, 여기서이 함수를 다음 후우 파일에 비트를 작성하고,

274
00:21:52,580 --> 00:21:54,650
그 실제로 후우 파일을 닫습니다.

275
00:21:54,650 --> 00:21:57,290
전에, 우리는 바로 바로 fclose 처리되었습니다

276
00:21:57,290 --> 00:22:01,190
하지만 후우 파일이있을 때, 대신에 fclosing의

277
00:22:01,190 --> 00:22:06,080
당신이 실제로 할 수있는 일은 것은 hfclose하고 hfopen입니다.

278
00:22:06,080 --> 00:22:13,220
그것들은 우리가 상대해야 할 것 같군 후우 파일에 특정 기능입니다.

279
00:22:13,220 --> 00:22:19,230
그럼 여기서 우리는 헤더에 읽고 다음 헤더를 써주세요.

280
00:22:19,230 --> 00:22:25,700
>> 그냥. H 파일을 읽어 우리는 후우 파일이 될 일을 파악할 종류의 수

281
00:22:25,700 --> 00:22:32,480
그것은 실제로 huffile.c로하지 않고, 가지고있는 특성

282
00:22:32,480 --> 00:22:36,750
이는 우리가 다이빙을하면 좀 더 복잡한 될 것입니다.

283
00:22:36,750 --> 00:22:41,270
이 I / O는 여기에 포인터를 처리 파일을 모두 있습니다.

284
00:22:41,270 --> 00:22:48,010
여기 우리는 hfread를 호출 할 때, 예를 들어, 아직도 fread과 대항하는 것을 볼 수 있습니다.

285
00:22:48,010 --> 00:22:53,050
우리는 완전히 그 기능을 떼어 버릴 수는 없을 걸,하지만 우리는을 처리 할 사람들을 보내는

286
00:22:53,050 --> 00:22:59,760
대신 자신의 모든 일을하는 후우 파일에서.

287
00:22:59,760 --> 00:23:02,300
당신이 궁금해 할까이 스캔 무료로 느낄 수

288
00:23:02,300 --> 00:23:08,410
그리고 가서 다시 레이어 조금 껍질을 벗기면.

289
00:23:20,650 --> 00:23:24,060
>> 우리가 보는거야 그 다음 파일 tree.h.입니다

290
00:23:24,060 --> 00:23:30,210
연습은 슬라이드에 전에 우리는 호프만 노드를 기대했다

291
00:23:30,210 --> 00:23:32,960
우리는 typedef 구조체 노드를했습니다.

292
00:23:32,960 --> 00:23:38,360
우리는 상징, 주파수, 그리고 두 노드 별을 가지고 기대하고 있습니다.

293
00:23:38,360 --> 00:23:41,870
이 경우 우리가하고있는 것은이 본질적으로 동일합니다

294
00:23:41,870 --> 00:23:46,880
대신 노드의 경우를 제외하고 우리가 나무 전화 할거야.

295
00:23:48,790 --> 00:23:56,760
우리는 당신이 나무를 호출 할 때 당신에게 나무 포인터를 반환하는 기능을 갖추고 있습니다.

296
00:23:56,760 --> 00:24:03,450
당신이 새로운 노드를 만들 때, 도전자로 돌아 가기

297
00:24:03,450 --> 00:24:11,410
당신이 말한 노드 * 새 단어 = malloc (sizeof)와 같은거야.

298
00:24:11,410 --> 00:24:17,510
기본적으로 mktree 당신을 위해 그 처리 될 예정입니다.

299
00:24:17,510 --> 00:24:20,990
마찬가지로, 당신은 나무를 제거 할 때,

300
00:24:20,990 --> 00:24:24,810
그래서은 본질적으로, 당신이 그것으로 완료 나무를 자유롭게 있어요

301
00:24:24,810 --> 00:24:33,790
대신 명시 적으로 그 무료로 전화, 당신이 실제로 rmtree 기능을 사용 할거야

302
00:24:33,790 --> 00:24:40,360
그런 다음 그 나무에 포인터를 전달하고있는 tree.c가 그 처리를 취할 것입니다.

303
00:24:40,360 --> 00:24:42,490
>> 우리는 tree.c. 조사

304
00:24:42,490 --> 00:24:47,240
우리는뿐만 아니라 구현을 참조하는 경우를 제외하고 동일한 기능을 기대합니다.

305
00:24:47,240 --> 00:24:57,720
우리가 예상했던대로, 당신이 mktree 호출 할 때 그것은 포인터로 나무의 크기를 mallocs

306
00:24:57,720 --> 00:25:03,190
NULL 값 때문에 0s 또는 NULLs에 값을 모두 초기화

307
00:25:03,190 --> 00:25:08,280
다음 단지 너에게 malloc'd 한 저 나무로 포인터를 반환합니다.

308
00:25:08,280 --> 00:25:13,340
다음은 나무를 제거 전화 할 때 먼저 더블 자유롭게하지 않도록합니다.

309
00:25:13,340 --> 00:25:18,320
당신이 실제로 제거 할 나무가 있는지 확인합니다.

310
00:25:18,320 --> 00:25:23,330
나무는 또한 어린이를 포함, 여기를하기 때문에

311
00:25:23,330 --> 00:25:29,560
이건 무엇을 그것은 재귀 트리의 왼쪽 노드에서 트리를 삭제 호출

312
00:25:29,560 --> 00:25:31,650
뿐만 아니라 오른쪽 노드 있습니다.

313
00:25:31,650 --> 00:25:37,790
그것이 부모를 자유롭게하기 전에뿐만 아니라 아이들을 해방해야합니다.

314
00:25:37,790 --> 00:25:42,770
부모는 또한 루트와 호환됩니다.

315
00:25:42,770 --> 00:25:46,500
그래서 고조 고조 할아버지와 같은 최초의 부모,

316
00:25:46,500 --> 00:25:52,130
또는 할머니 나무는 먼저 우리가 처음 수준을 확보해야합니다.

317
00:25:52,130 --> 00:25:58,490
그럼 그 무료로 아래로 통과 한 후 그 등을 다시 무료로 올라 와서

318
00:26:00,400 --> 00:26:02,210
그래서 그 나무입니다.

319
00:26:02,210 --> 00:26:04,240
>> 이제 우리는 숲보세요.

320
00:26:04,240 --> 00:26:09,860
귀하의 허프만 나무의 모든 곳은 숲입니다.

321
00:26:09,860 --> 00:26:12,910
이 음모라고, 우리가 뭔가를 봐야한다는 이야기를하는 거지

322
00:26:12,910 --> 00:26:22,320
그 나무에 대한 포인터뿐만 아니라 옆라는 플롯에 대한 포인터가 포함되어 있습니다.

323
00:26:22,320 --> 00:26:28,480
어떤 구조가 같아 보이는 이런 종류의 무엇입니까?

324
00:26:29,870 --> 00:26:32,490
그것은 가지 저쪽 말합니다.

325
00:26:34,640 --> 00:26:36,700
바로 여기 야.

326
00:26:37,340 --> 00:26:39,170
연결 목록입니다.

327
00:26:39,170 --> 00:26:44,590
우리는 음모를 가지고 때 플롯의 연결리스트 같은 것을 볼 수 있습니다.

328
00:26:44,590 --> 00:26:53,020
숲은 플롯의 연결리스트로 정의됩니다

329
00:26:53,020 --> 00:26:58,100
그리고 숲의 구조는 우리가 우리가 처음 계획에 대한 포인터를 가야는거야

330
00:26:58,100 --> 00:27:02,740
그 음모는 내 나무가 나 대신 나무에 가리

331
00:27:02,740 --> 00:27:06,190
그리고 등등 등등 다음 플롯을 가리 킵니다.

332
00:27:06,190 --> 00:27:11,100
숲을 만들려면 우리는 mkforest를 호출합니다.

333
00:27:11,100 --> 00:27:14,930
그럼 우리가 여기서 꽤 유용한 기능을 가지고 있습니다.

334
00:27:14,930 --> 00:27:23,240
이 반환 값은 트리 *이 다음 숲에 합격하고있는 우리는 선택해야

335
00:27:23,240 --> 00:27:25,210
나무에 대한 포인터.

336
00:27:25,210 --> 00:27:29,370
어떤 피크가 어떻게하면을 가리키고 있는지 그 숲에 들어갈 것입니다

337
00:27:29,370 --> 00:27:35,240
해당 포리스트에서 가장 낮은 빈도로 나무를 제거

338
00:27:35,240 --> 00:27:38,330
그리고 저 나무로 여러분에게 포인터를 제공합니다.

339
00:27:38,330 --> 00:27:43,030
당신이 선택 호출되면, 나무는 더 이상 숲에 존재하지 않습니다

340
00:27:43,030 --> 00:27:48,550
하지만 반환 값은 그 나무에 포인터입니다.

341
00:27:48,550 --> 00:27:50,730
그럼 당신은 공장을 갖추고 있습니다.

342
00:27:50,730 --> 00:27:57,420
이 아닌-0 주파수가 나무에 대한 포인터를 전달하는 한,

343
00:27:57,420 --> 00:28:04,040
어떤 공장 할 것은, 숲을 나무를하고, 공장 것입니다 그 숲의 나무 내부.

344
00:28:04,040 --> 00:28:06,370
여기 rmforest 있습니다.

345
00:28:06,370 --> 00:28:11,480
기본적으로 우리의 나무를 모두 해제 나무, 삭제와 마찬가지로

346
00:28:11,480 --> 00:28:16,600
숲을 제거 숲 속에 포함 된 무료 모든 것이다.

347
00:28:16,600 --> 00:28:24,890
>> 우리가 forest.c으로 보면, 우리는 거기에 최소 1 rmtree 명령을 볼 것으로 예상됩니다

348
00:28:24,890 --> 00:28:30,090
때문에 숲 안에 나무가있는 경우 숲에서 무료로 메모리,

349
00:28:30,090 --> 00:28:32,930
결국, 당신도 그 나무를 제거해야 할거야.

350
00:28:32,930 --> 00:28:41,020
우리가 forest.c으로 보면, 우리는 우리가 예상 한대로이 우리 mkforest을 수 있습니다.

351
00:28:41,020 --> 00:28:42,890
우리는 malloc 일을.

352
00:28:42,890 --> 00:28:51,740
가로 시작하는 비 때문에, NULL로 숲의 첫 번째 음모를 초기화

353
00:28:51,740 --> 00:29:05,940
그러면 우리는 가장 낮은 무게로 나무를 반환 곡괭이, 가장 낮은 주파수를 참조

354
00:29:05,940 --> 00:29:13,560
그리고 특정 노드의 못된 그 저 나무로 포인트와 다음,

355
00:29:13,560 --> 00:29:16,760
그래서 숲의 연결리스트에서 그을 해결합니다.

356
00:29:16,760 --> 00:29:24,510
그리고 여기에 우리는 어떤 연결리스트에 삽입하는 나무를 심는를 갖추고 있습니다.

357
00:29:24,510 --> 00:29:29,960
어떤 숲이 멋지게은 우리를 위해 정렬 유지 않습니다.

358
00:29:29,960 --> 00:29:37,910
그리고 마지막으로, 우리는 예상대로, 우리가 호출 rmtree 가지고 rmforest을합니다.

359
00:29:46,650 --> 00:29:55,440
>> 지금까지 배포 코드를 보면, huffile.c는 이해하기까지 가장 힘든가 아마도

360
00:29:55,440 --> 00:29:59,990
다른 파일 반면 자체는 따라하기가 아주 간단했다.

361
00:29:59,990 --> 00:30:03,090
포인터와 링크 된 목록과 같은 우리의 지식,

362
00:30:03,090 --> 00:30:04,860
우리는 아주 잘 따라 할 수 있었다.

363
00:30:04,860 --> 00:30:10,500
하지만 우리가 정말 우리가 완전히 이해했는지 확인하기 위해 필요한 것은. h 파일입니다

364
00:30:10,500 --> 00:30:15,840
당신은 그 반환 값으로 처리, 해당 함수를 호출 할 필요가 있기 때문에

365
00:30:15,840 --> 00:30:20,590
따라서 완전히 수행 할 것입니다 어떤 작업을 이해했는지 확인

366
00:30:20,590 --> 00:30:24,290
당신이 그 기능 중 하나를 호출 할 때마다.

367
00:30:24,290 --> 00:30:33,020
하지만 사실 이건 내부 이해하는 것은 우리가 사람들을 가지고 있기 때문에 상당히 필요가 없습니다. h 파일.

368
00:30:35,170 --> 00:30:39,490
우리는 우리의 배포 코드에 남아 둘 이상의 파일이 있습니다.

369
00:30:39,490 --> 00:30:41,640
>> 가 덤프 살펴 보도록하겠습니다.

370
00:30:41,640 --> 00:30:47,230
여기의 댓글로 덤프 허프만 압축 파일을 걸립니다

371
00:30:47,230 --> 00:30:55,580
그리고 번역 및 덤프의 모든 콘텐츠 아웃.

372
00:31:01,010 --> 00:31:04,260
여기 우리는 hfopen를 호출한다는 참조하십시오.

373
00:31:04,260 --> 00:31:10,770
이 * 입력 할 = fopen을 제기 할 미러링 종류입니다

374
00:31:10,770 --> 00:31:13,500
그리고 당신은 정보를 전달합니다.

375
00:31:13,500 --> 00:31:18,240
그것은 대신에 당신이 Huffile에 전달하는 파일 *의 경우를 제외하고 거의 동일입니다;

376
00:31:18,240 --> 00:31:22,030
대신 fopen의 당신은 hfopen를 전달하고 있습니다.

377
00:31:22,030 --> 00:31:29,280
여기 가지 우리가 헤더에 읽는 방법과 유사입니다 먼저 헤더에 읽기

378
00:31:29,280 --> 00:31:33,580
비트 맵 파일.

379
00:31:33,580 --> 00:31:38,000
우리가 여기서하는 것은 확인하여인지 여부를 헤더 정보

380
00:31:38,000 --> 00:31:44,330
는 실제 후우 파일의 것을 나타냅니다 오른쪽 마법 번호를 포함

381
00:31:44,330 --> 00:31:53,610
그런 다음 확인하려면 다음 수표 모두가 열려있는 실제 huffed 파일이나하지하는 파일이.

382
00:31:53,610 --> 00:32:05,330
이게 않는 것은 우리가 볼 수있는 상징의 모든 주파수를 출력합니다

383
00:32:05,330 --> 00:32:09,790
그래픽 테이블에 터미널 내에 있습니다.

384
00:32:09,790 --> 00:32:15,240
이 부분은 유용 할 것입니다.

385
00:32:15,240 --> 00:32:24,680
이 비트를 가지고 있으며 가변 비트에 조금씩를 읽고 다음을 출력합니다.

386
00:32:28,220 --> 00:32:35,430
나는 파일을 피 우니의 결과 hth.bin에 덤프에 전화를 건다면

387
00:32:35,430 --> 00:32:39,490
직원 솔루션을 사용하여,이를 것입니다.

388
00:32:39,490 --> 00:32:46,000
그것은 이러한 문자를 모두 출력하고는 게재되는 빈도를 태우고있다.

389
00:32:46,000 --> 00:32:51,180
우리가 보면, 대부분이 경우를 제외하고 0s 위치 : 두 번 나타납니다 H,,

390
00:32:51,180 --> 00:32:54,820
그리고 한 번 나타납니다 T,.

391
00:32:54,820 --> 00:33:07,860
그리고 여기에 우리는 0s와 1 초에 실제 메시지가 있습니다.

392
00:33:07,860 --> 00:33:15,450
우리가 hth.txt 보면되는데,이, 아마 huffed 된 원본 메시지입니다

393
00:33:15,450 --> 00:33:22,490
우리는 거기에 몇 가지 안녕하세요!와 TS를 볼 것으로 기대합니다.

394
00:33:22,490 --> 00:33:28,720
특히, 우리는 단 1 T 2 안녕하세요!를 볼 것으로 기대합니다.

395
00:33:32,510 --> 00:33:37,440
여기 hth.txt에 있습니다. 그것은 실제로 HTH 있습니다.

396
00:33:37,440 --> 00:33:41,270
우리가 볼 수 있지만, 거기에 포함 된 줄 바꿈 문자입니다.

397
00:33:41,270 --> 00:33:53,190
후우 파일 hth.bin는 또한뿐만 아니라 줄 바꿈 문자를 인코딩합니다.

398
00:33:55,680 --> 00:34:01,330
여기 우리는 주문 바꿈 한 후 HTH와 것을 알고 있기 때문에

399
00:34:01,330 --> 00:34:07,340
우리는 하나 (1)에 의해 아마 H가 표시되는 것을 볼 수 있습니다

400
00:34:07,340 --> 00:34:17,120
그리고 T는 아마 01이며, 그 다음 H는 1도

401
00:34:17,120 --> 00:34:21,139
그리고 우리는 두 0s로 표시 바꿈을 갖추고 있습니다.

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

403
00:34:26,530 --> 00:34:31,600
>> 그리고 마지막으로, 우리는 여러. C를 처리합니다. 때문에 H 파일

404
00:34:31,600 --> 00:34:36,350
우리는 컴파일러에 매우 복잡 주장을 할거야

405
00:34:36,350 --> 00:34:40,460
그래서 여기 당신을 위해 덤프를 만드는 메이크 있습니다.

406
00:34:40,460 --> 00:34:47,070
그러나 실제로, 당신은 자신의 puff.c 파일을 높이는 방법에 대한 가야 해.

407
00:34:47,070 --> 00:34:54,330
메이크는 실제로 당신을 위해 puff.c을 처리하지 않습니다.

408
00:34:54,330 --> 00:34:59,310
우리는 메이크 파일을 편집 할에 해당을 떠난다.

409
00:34:59,310 --> 00:35:05,930
당신이하는 모든 같은 명령을 입력하면, 예를 들어, 당신을 위해 모든 할 것입니다.

410
00:35:05,930 --> 00:35:10,760
과거 pset에서 메이크 파일의 예를 볼 주시기 바랍니다

411
00:35:10,760 --> 00:35:17,400
뿐만 아니라 귀하의 퍼프 파일을 만들 수 방법에 대해 알아 보려면이 하나 벗어

412
00:35:17,400 --> 00:35:20,260
이 메이크 파일을 편집하여.

413
00:35:20,260 --> 00:35:22,730
그건 우리의 유통 코드에 대해입니다.

414
00:35:22,730 --> 00:35:28,380
>> 우리가 첨부터 끝까지 읽어 본 후, 여기에 그냥 다른 기억

415
00:35:28,380 --> 00:35:30,980
어떻게 우리는 호프만 노드를 처리 할거야.

416
00:35:30,980 --> 00:35:35,400
우리는 더 이상 노드 전화 할 수 할 수 없어, 우리는 그들에게 나무를 호출 할 것

417
00:35:35,400 --> 00:35:39,260
우리가 숯불 자신의 기호를 대표 할가는 곳,

418
00:35:39,260 --> 00:35:43,340
자신의 주파수, 정수와 사건의 수입니다.

419
00:35:43,340 --> 00:35:47,370
이 수레보다 더 정확한이기 때문에 우리가 그걸를 사용하고 있습니다.

420
00:35:47,370 --> 00:35:52,980
그리고 우리는 왼쪽 자녀뿐만 아니라 오른쪽 자녀에게 또 다른 포인터가 있습니다.

421
00:35:52,980 --> 00:35:59,630
숲은 우리가 본대로, 단지 나무의 연결된 목록입니다.

422
00:35:59,630 --> 00:36:04,670
결국, 우리는 후우 파일을 구축 할 때,

423
00:36:04,670 --> 00:36:07,580
우리는 우리의 숲이 단 1 나무를 포함 할 -

424
00:36:07,580 --> 00:36:12,420
한 나무, 여러 어린이들과 한 뿌리.

425
00:36:12,420 --> 00:36:20,840
이전 우리가 우리의 허프만 트리를 만들 때에,

426
00:36:20,840 --> 00:36:25,360
우리는 우리의 화면에 노드를 모두 배치에 의해 시작

427
00:36:25,360 --> 00:36:27,790
그리고, 우리가이 노드를 할거야 말을

428
00:36:27,790 --> 00:36:32,920
결국은 잎이 될거야,이 자신의 상징이 자신의 주파수입니다.

429
00:36:32,920 --> 00:36:42,070
우리는 불과 3 글자가있는 경우의 숲, 그 3 나무의 숲입니다.

430
00:36:42,070 --> 00:36:45,150
그리고 우리는, 우리가 처음 부모를 추가 할 때, 계속으로

431
00:36:45,150 --> 00:36:48,080
우리는이 나무의 숲을했습니다.

432
00:36:48,080 --> 00:36:54,930
우리는 숲에서 아이들의 2를 삭제 한 다음 부모 노드로 대체

433
00:36:54,930 --> 00:36:58,820
그 아이들과 같은 사람들이 노드를했다.

434
00:36:58,820 --> 00:37:05,600
그리고 마지막으로, 우리의 마지막으로, 학사 학위의 예를하고있는 단계, 그리고 C를

435
00:37:05,600 --> 00:37:08,030
최종 부모를 만들기 위해 것,

436
00:37:08,030 --> 00:37:13,190
그리고 다음 1로 숲의 나무의 총 개수를 가져 겠지요.

437
00:37:13,190 --> 00:37:18,140
모두가 당신이 숲에서 여러 나무와 함께 시작하는 방법을 참조하십시오 않습니​​다

438
00:37:18,140 --> 00:37:22,520
과 1을 끝? 좋아요. 좋아.

439
00:37:25,530 --> 00:37:28,110
>> 우리는 퐁퐁을 위해 어떻게해야합니까?

440
00:37:28,110 --> 00:37:37,110
우리가해야 할 것은 언제나, 그들은 우리에게 입력의 오른쪽 유형을 지정하도록 is

441
00:37:37,110 --> 00:37:39,090
우리는 실제로 프로그램을 실행할 수 있도록.

442
00:37:39,090 --> 00:37:43,130
이 경우 사람들은 첫 번째 명령 줄 인수 후 회사를 제공 할 것

443
00:37:43,130 --> 00:37:53,440
2 개 : 우리가 압축 및 압축 해제 파일의 출력 할 파일.

444
00:37:53,440 --> 00:38:00,410
그러나 일단 그들이 값의 오른쪽 금액에서 우리를 통과해야합니다

445
00:38:00,410 --> 00:38:05,820
우리는 입력 후우 파일인지 확인하고 싶습니다.

446
00:38:05,820 --> 00:38:10,420
그리고 일단 우리는, 우리는 우리의 트리를 작성하려면, 그것이 후우 파일의 보장

447
00:38:10,420 --> 00:38:20,940
이 메시지를 보낸 사람이 만든 나무를 일치 등의 나무를 구축 할 수 있습니다.

448
00:38:20,940 --> 00:38:25,840
우리가 나무를 구축 후, 다음에 우리가 함께 0s하고에 전달하는 1 초,를 처리 할 수

449
00:38:25,840 --> 00:38:29,590
가 동일이기 때문에, 우리의 나무를 따라 사람들을 따라

450
00:38:29,590 --> 00:38:33,510
다음, 해당 메시지를 작성 문자로 다시 비트를 해석한다.

451
00:38:33,510 --> 00:38:35,880
그리고 마지막에 우리는 여기에 포인터를 다루고 있기 때문에

452
00:38:35,880 --> 00:38:38,110
우리는 우리가 어떤 메모리 누수가되지 않도록하려면

453
00:38:38,110 --> 00:38:41,330
그리고 우리 자유 다.

454
00:38:42,820 --> 00:38:46,430
>> 적절한 사용을 보장하는 것은 지금의 우리를 위해 낡은 모자입니다.

455
00:38:46,430 --> 00:38:51,980
우리는 입력에 타고있는이 부풀려 파일의 이름 것​​입니다,

456
00:38:51,980 --> 00:38:56,010
그리고 우리는 출력을 지정

457
00:38:56,010 --> 00:39:01,580
그래서 텍스트 파일 될 팽화 출력에 대한 파일의 이름입니다.

458
00:39:03,680 --> 00:39:08,820
그 사용입니다. 그리고 지금 우리는 입력이 huffed하거나되지 않도록하고 싶습니다.

459
00:39:08,820 --> 00:39:16,420
다시 생각 우리에게 도움을 줄 수있는 배포 코드에 없나요했습니다

460
00:39:16,420 --> 00:39:21,570
파일이 huffed 여부를 이해하십니까?

461
00:39:21,570 --> 00:39:26,910
Huffeader에 대한 huffile.c의 정보가 발생했습니다.

462
00:39:26,910 --> 00:39:33,430
우리는 모든 후우 파일 매직 넘버와 함께와 관련된 Huffeader이 알고

463
00:39:33,430 --> 00:39:37,240
각 기호에 대한 주파수뿐만 아니라 배열

464
00:39:37,240 --> 00:39:39,570
뿐만 아니라 체크섬 있습니다.

465
00:39:39,570 --> 00:39:43,180
우리는 알고 있지만, 우리는 또한, dump.c에서 살짝했다

466
00:39:43,180 --> 00:39:49,120
있는이 후우 파일로 읽었어요.

467
00:39:49,120 --> 00:39:53,990
그리고 그렇게하려면 그것이 정말 huffed이나되지 않았습니다 여부를 확인했다.

468
00:39:53,990 --> 00:40:03,380
그래서 아마도 우리가 우리 puff.c.에 대한 구조 dump.c 사용할 수 있습니다

469
00:40:03,380 --> 00:40:12,680
다시 pset 4 우리가 RGB의 트리플에 복사 한 파일 copy.c을했을 때

470
00:40:12,680 --> 00:40:14,860
우리는, 추리 소설과 크기 조정에 대한 그런 해석

471
00:40:14,860 --> 00:40:20,390
마찬가지로, 당신이 할 수있는 것은 바로 CP dump.c puff.c과 같은 명령을 실행합니다

472
00:40:20,390 --> 00:40:23,600
그리고 코드의 일부를 사용합니다.

473
00:40:23,600 --> 00:40:28,210
그러나, 프로세스의로 간단 않을거야

474
00:40:28,210 --> 00:40:33,010
puff.c에 dump.c 번역을위한,

475
00:40:33,010 --> 00:40:36,160
하지만 적어도 시작 어딘가를 제공합니다

476
00:40:36,160 --> 00:40:40,540
입력이 실제로 huffed하거나되지 않도록하는 방법에

477
00:40:40,540 --> 00:40:43,240
뿐만 아니라 다른 몇 가지 있습니다.

478
00:40:45,930 --> 00:40:50,250
우리는 적절한 사용을 보장하고 입력이 huffed 것을 보장합니다.

479
00:40:50,250 --> 00:40:53,570
우리가 우리 적절한 오류 검사를 수행 한 한 때마다,

480
00:40:53,570 --> 00:41:01,520
그래서 문제가있을 경우, 재 및 일부 오류가 발생할 경우 기능을 종료.

481
00:41:01,520 --> 00:41:07,170
>> 지금 우리가 원하는 것은 실제 트리를 구축합니다.

482
00:41:08,840 --> 00:41:12,640
우리가 숲을 보면, 2의 주요 기능이 있습니다

483
00:41:12,640 --> 00:41:15,800
우리는 매우 익숙하게하려는 것 같군.

484
00:41:15,800 --> 00:41:23,870
이 부울 함수의 공장은 우리의 숲 안에 비-0 주파수 나무 식물.

485
00:41:23,870 --> 00:41:29,250
그리고 거기에는 숲과 나무에 대한 포인터에 대한 포인터를 전달합니다.

486
00:41:32,530 --> 00:41:40,340
빠른 질문 : 당신은 허프만 트리를 구축 할 때 얼마나 많은 숲이 가능한가?

487
00:41:44,210 --> 00:41:46,650
우리 숲은 이제 우리의 캔버스처럼입니까?

488
00:41:46,650 --> 00:41:50,800
그래서 우리는 단 1 숲을받을거야,하지만 우리는 여러 나무를 할 겁니다.

489
00:41:50,800 --> 00:41:57,590
이 공장 전화 따라서 전에 아마 당신의 숲을 만들고 싶어거야.

490
00:41:57,590 --> 00:42:04,430
당신이 숲을 만들 수있는 방법에 forest.h에 보면 명령은 거기에 있습니다.

491
00:42:04,430 --> 00:42:09,270
당신은 나무를 심는 할 수 있습니다. 우리가 그렇게 작업을 수행하는 방법을 알아요.

492
00:42:09,270 --> 00:42:11,590
그리고 당신은 또한, 숲에서 나무를 선택할 수 있습니다

493
00:42:11,590 --> 00:42:17,540
낮은 무게로 나무를 제거하고 여러분에게 포인터를 제공.

494
00:42:17,540 --> 00:42:23,090
우리는 사례를 자신을하고있을 때 다시 생각하면,

495
00:42:23,090 --> 00:42:27,980
우리는 그것을 그릴 때, 우리는 단순히 그냥 링크를 추가했습니다.

496
00:42:27,980 --> 00:42:31,680
하지만 여기 대신, 그냥 링크를 추가

497
00:42:31,680 --> 00:42:40,630
당신이 그 노드의 2를 제거하고 다른 하나를 대체으로 더 생각합니다.

498
00:42:40,630 --> 00:42:44,200
수확과 재배의 관점에서 그 표현하려면,

499
00:42:44,200 --> 00:42:48,840
당신은이 나무를 채취 한 다음 다른 나무를 심는하고

500
00:42:48,840 --> 00:42:54,060
그 말은 당신이 어린이로 나온 사람들이 나무가 있습니다.

501
00:42:57,950 --> 00:43:05,280
호프만의 나무를 구축하려면 순서로 기호 및 주파수에서 읽을 수있는

502
00:43:05,280 --> 00:43:10,790
Huffeader이 당신에게 그 데이터를 얻을 수 있으므로하면,

503
00:43:10,790 --> 00:43:14,250
당신에게 주파수의 배열을 제공합니다.

504
00:43:14,250 --> 00:43:19,660
그러니 가서 수 있으며, 단지에서 0으로 아무 것도 무시

505
00:43:19,660 --> 00:43:23,760
우리는 그것의 끝에서 256 잎을 원하지 않기 때문에.

506
00:43:23,760 --> 00:43:27,960
우리는 문자로되어 잎의 수를 원하는

507
00:43:27,960 --> 00:43:31,600
그는 실제로 파일에 사용됩니다.

508
00:43:31,600 --> 00:43:37,590
당신은 그 기호에 읽기 및 비-0 주파수를 가진 기호의 각 수

509
00:43:37,590 --> 00:43:40,440
그 나무가 될 것이다.

510
00:43:40,440 --> 00:43:45,990
당신이 할 수있는 것은이 아닌-0 주파수 기호를 읽을 때마다

511
00:43:45,990 --> 00:43:50,660
당신은 숲의 나무를 심을 수 있습니다.

512
00:43:50,660 --> 00:43:56,620
당신이 숲에서 나무를 심는 후에는 형제 자매로 그 나무를 가입 할 수 있습니다

513
00:43:56,620 --> 00:44:01,130
따라서 재배 및 픽업하는 곳 따기 2 후 공장 1로 돌아 간다

514
00:44:01,130 --> 00:44:05,820
어디 한 당신이 공장은 당신이 선택한이 2 어린이의 부모입니다.

515
00:44:05,820 --> 00:44:11,160
그래서 최종 결과는 포리스트에서 단일 나무가 될 것입니다.

516
00:44:16,180 --> 00:44:18,170
즉, 당신이 나무를 만드는 방법은 다음과 같습니다.

517
00:44:18,170 --> 00:44:21,850
>> 여기 잘못 될 수도 여러 가지가 있습니다

518
00:44:21,850 --> 00:44:26,580
때문에 우리는 새로운 나무를 만들고 그런 식으로 포인터와 일 처리를 다루고 있습니다.

519
00:44:26,580 --> 00:44:30,450
우리가 포인터를 처리했을 때 전에,

520
00:44:30,450 --> 00:44:36,580
우리가 malloc'd 때마다 우리는 우리에게 NULL 포인터 값을 반환하지 않았는지 확인합니다 싶었어요.

521
00:44:36,580 --> 00:44:42,770
따라서이 과정에서 여러 단계에서 여러 가지 경우가있을 거예요

522
00:44:42,770 --> 00:44:45,920
어디에 프로그램이 실패 할 수 있습니다.

523
00:44:45,920 --> 00:44:51,310
당신이하길 원하는 것은, 당신이 이러한 오류를 처리되었는지 확인하고 싶어요

524
00:44:51,310 --> 00:44:54,580
그리고 사양에이 정상적으로 그것들을 처리 할 말

525
00:44:54,580 --> 00:45:00,280
따라서 프로그램이 종료하는 이유를 말해 사용자에게 메시지를 인쇄 좋아

526
00:45:00,280 --> 00:45:03,050
그리고 즉시 그것을 종료합니다.

527
00:45:03,050 --> 00:45:09,490
이 오류 처리 작업을 수행하려면, 당신이 그것을 확인하는 것이 좋습니다

528
00:45:09,490 --> 00:45:12,160
오류가있을 수 있다는 매번.

529
00:45:12,160 --> 00:45:14,660
당신이 새로운 포인터를하신다고 매번

530
00:45:14,660 --> 00:45:17,040
그가 성공적 있는지 확인하고 싶습니다.

531
00:45:17,040 --> 00:45:20,320
우리가 새로운 포인터와 malloc을시키는 것입니다 어떻게했는지 전에,

532
00:45:20,320 --> 00:45:22,380
그리고 우리는 그 포인터가 NULL인지 여부를 확인합니다.

533
00:45:22,380 --> 00:45:25,670
그래서, 그렇게 단 수있는 경우가있을 거예요

534
00:45:25,670 --> 00:45:28,610
하지만 가끔은 실제로 함수를 호출하는

535
00:45:28,610 --> 00:45:33,100
그 함수 내에서, 그 mallocing 짓을 하나.

536
00:45:33,100 --> 00:45:39,110
이 경우, 우리는 코드 내에서 기능의 일부로 살펴보면,

537
00:45:39,110 --> 00:45:42,260
그들 중 일부는 부울 함수이다.

538
00:45:42,260 --> 00:45:48,480
추상적 경우 우리는 foo를 호출 부울 함수가있는 경우

539
00:45:48,480 --> 00:45:54,580
기본적으로, 우리는 foo를이 무슨 일을 했든지하는 외에을 얻을 수 있습니다

540
00:45:54,580 --> 00:45:57,210
이 부울 함수니까, 사실 또는 false를 반환합니다 -

541
00:45:57,210 --> 00:46:01,300
사실이라면 성공, false이면 않습니다.

542
00:46:01,300 --> 00:46:06,270
그래서 우리는 foo는의 반환 값이 true 또는 false인지 확인하고 싶습니다.

543
00:46:06,270 --> 00:46:10,400
이 거짓이라면, 우리가 어떤 종류의 메시지를 인쇄 할거야 것을 의미합니다

544
00:46:10,400 --> 00:46:14,390
다음 프로그램을 종료합니다.

545
00:46:14,390 --> 00:46:18,530
우리가 원하는 것은 foo는의 반환 값을 확인합니다.

546
00:46:18,530 --> 00:46:23,310
foo는이 false를 반환한다면, 우리는 오류의 일부 종류를 발생 알

547
00:46:23,310 --> 00:46:25,110
우리는 우리의 프로그램을 종료해야합니다.

548
00:46:25,110 --> 00:46:35,600
이 작업을 수행하는 방법은 실제 기능 자체가 상태 인 조건을 가지고 있습니다.

549
00:46:35,600 --> 00:46:39,320
foo는이 X에 소요 말해.

550
00:46:39,320 --> 00:46:43,390
우리는 경우 조건으로 할 수 있습니다 (foo는 (X)).

551
00:46:43,390 --> 00:46:50,900
푸 실행의 끝에가 true를 반환하면 기본적으로, 그 의미

552
00:46:50,900 --> 00:46:57,390
함수가 푸 평가 있기 때문에 다음에 우리가 할 수

553
00:46:57,390 --> 00:47:00,500
전체 상태를 평가하는 순서를 유지해야합니다.

554
00:47:00,500 --> 00:47:06,500
그래서 그 기능이 true를 반환하고 성공하면 당신이 뭔가를 할 수있는 방법입니다.

555
00:47:06,500 --> 00:47:11,800
그러나 오류 검사 때, 당신은 만 함수가 false를 반환하면 종료하고 싶습니다.

556
00:47:11,800 --> 00:47:16,090
당신이 할 수있는 것은 바로 추가 할 수 있습니다 == 허위 또는 단지 앞에 쿵 추가

557
00:47:16,090 --> 00:47:21,010
그리고 당신은 (! foo는) 경우가 있습니다.

558
00:47:21,010 --> 00:47:29,540
그 조건의 본문 내에서, 오류 처리의 모든 것이다

559
00:47:29,540 --> 00:47:36,940
이 "이 나무를 만들 수 없습니다"좋아하고 1 그런 일을 반환합니다.

560
00:47:36,940 --> 00:47:43,340
그렇게되면,하지만, foo는 거짓 반환지라도입니다 -

561
00:47:43,340 --> 00:47:46,980
foo는이 true를 반환 해.

562
00:47:46,980 --> 00:47:51,060
그런 다음 다시 푸 전화 할 필요가 없습니다. 그건 일반적인 오해에요.

563
00:47:51,060 --> 00:47:54,730
이 귀하의 상태에 있었기 때문에, 그것은 이미 평가 거에요

564
00:47:54,730 --> 00:47:59,430
당신은 나무 나 그런 일을 할 사용하는 경우 그래서 당신은 이미 그 결과를이

565
00:47:59,430 --> 00:48:01,840
또는 식물이나 곡괭이 나 뭐.

566
00:48:01,840 --> 00:48:07,460
이미 그 값이 있습니다. 이미 실행있어.

567
00:48:07,460 --> 00:48:10,730
그럼 조건으로 부울 함수를 사용하는 것이 좋습니다

568
00:48:10,730 --> 00:48:13,890
때문에 여부가 실제로 루프의 몸을 실행할 수 없습니다,

569
00:48:13,890 --> 00:48:18,030
어쨌든 함수를 실행합니다.

570
00:48:22,070 --> 00:48:27,330
>> 마지막 단계에 대한 우리의 두 번째는 파일에 메시지를 쓰고있다.

571
00:48:27,330 --> 00:48:33,070
일단 허프만 트리를 빌드 후 파일에 메시지를 작성하는 것은 매우 간단합니다.

572
00:48:33,070 --> 00:48:39,260
단지 0s와 1 초를 따르 지금은 너무 간단입니다.

573
00:48:39,260 --> 00:48:45,480
그리고 국제 대회에서 우리는 허프만 트리에서 0s이 왼쪽 명시 알

574
00:48:45,480 --> 00:48:48,360
그리고 1 초 바로 나타냅니다.

575
00:48:48,360 --> 00:48:53,540
당신은 0을 얻을 당신이 조금씩에서 읽을 그래서 경우, 때마다

576
00:48:53,540 --> 00:48:59,100
당신은 1에서 읽을 때마다 다음 왼쪽 지점에 따라 거고

577
00:48:59,100 --> 00:49:02,100
당신은 오른쪽 지점에 따릅.

578
00:49:02,100 --> 00:49:07,570
당신은 잎이 나오기 전까지 그리고 계속 할거야

579
00:49:07,570 --> 00:49:11,550
잎은 가지의 끝 부분에 될거야 때문입니다.

580
00:49:11,550 --> 00:49:16,870
우리가 잎 여부를 누르 여부를 우리가 어떻게 알 수 있습니까?

581
00:49:19,800 --> 00:49:21,690
우리는 전에 말했다.

582
00:49:21,690 --> 00:49:24,040
[학생] 포인터가 NULL 인 경우. >> 그래.

583
00:49:24,040 --> 00:49:32,220
왼쪽과 오른쪽 모두 나무 포인터가 NULL 인 경우 우리가 잎에 충돌 한 경우 우리는 알 수 있습니다.

584
00:49:32,220 --> 00:49:34,110
좋아요.

585
00:49:34,110 --> 00:49:40,320
우리는 우리 후우 파일로 조금씩에서 읽을 할 알아요.

586
00:49:43,870 --> 00:49:51,220
우리가 dump.c에서 전에 본 바와 같이, 그들이 무슨 짓을했는지들은 후우 파일에 조금씩에서 읽을 수 있습니다

587
00:49:51,220 --> 00:49:54,560
불과 그 비트가 뭔지 출력한다.

588
00:49:54,560 --> 00:49:58,430
우리가 그렇게 일을 할 수 없어요. 우리는 조금 더 복잡한 뭔가 일을 할거야.

589
00:49:58,430 --> 00:50:03,620
하지만 우리가 할 수있는 것은 우리가 비트에 읽는 코드의 비트를 취할 수 있습니다.

590
00:50:03,620 --> 00:50:10,250
여기 우리가하고 있다고 현재의 비트를 나타내는 정수 비트가 있습니다.

591
00:50:10,250 --> 00:50:15,520
이 파일의 끝이 나오기 전까지이 파일에있는 비트의 모든 반복을 담당한다.

592
00:50:15,520 --> 00:50:21,270
그에 따라 다음이 반복자의 일부 종류를 갖고 싶어 할거야

593
00:50:21,270 --> 00:50:26,760
당신의 나무를 통과합니다.

594
00:50:26,760 --> 00:50:31,460
그리고, 비트가 0 또는 1인지에 따라

595
00:50:31,460 --> 00:50:36,920
여러분은 왼쪽에 그 반복자를 이동하거나 오른쪽으로 이동하려는거야

596
00:50:36,920 --> 00:50:44,080
모든 방법은 잎이 나오기 전까지 때문에 모든 방법은 중이 해당 노드까지

597
00:50:44,080 --> 00:50:48,260
더 이상 노드를 가리 키지 않습니다.

598
00:50:48,260 --> 00:50:54,300
왜 우리는 호프만 파일하지만 모스 코드와 함께이 작업을 수행 할 수 있습니다?

599
00:50:54,300 --> 00:50:56,610
모스 코드에서 모호 조금 있긴한데 때문입니다.

600
00:50:56,610 --> 00:51:04,440
우리는 대기 오처럼 될 수, 우리는 길을 따라 편지를 부딪 혔어요, 그럼이 우리의 편지입니다

601
00:51:04,440 --> 00:51:08,150
우리가 좀 더 계속하면, 우리는 또 다른 편지를 맞았을 텐데 반면.

602
00:51:08,150 --> 00:51:13,110
하지만 그건, 허프만 인코딩 할 순 없어

603
00:51:13,110 --> 00:51:17,540
그래서 우리는 우리가 갈 수있는 유일한 방법은 캐릭터를 공격 할 안심 하셔도됩니다

604
00:51:17,540 --> 00:51:23,480
해당 노드의 왼쪽과 오른쪽 아이가 NULL 인 경우입니다.

605
00:51:28,280 --> 00:51:32,350
>> 마지막으로, 우리는 우리의 기억을 모두 확보하고 싶습니다.

606
00:51:32,350 --> 00:51:37,420
우리는 우리가 다루고 된 것으로 모두 가까이 후우 파일에 원하는

607
00:51:37,420 --> 00:51:41,940
뿐만 아니라 우리의 숲에있는 나무를 모두 제거합니다.

608
00:51:41,940 --> 00:51:46,470
구현에 따라, 당신은 아마 숲을 제거 전화 할 거예요

609
00:51:46,470 --> 00:51:49,780
대신 실제로 나무 자신의 모든 통과.

610
00:51:49,780 --> 00:51:53,430
당신은 임시 나무를 한 경우 그러나, 당신은 그렇게 확보하는 것이 좋습니다.

611
00:51:53,430 --> 00:51:59,060
당신은 최고의 코드를 알고 있으므로 메모리를 할당하는 곳을 알아.

612
00:51:59,060 --> 00:52:04,330
그리고 당신이 들어가 있다면,, malloc에​​ 대한 F'ing도 제어하여 시작

613
00:52:04,330 --> 00:52:08,330
보는 때마다 malloc하고 그 모두를 해방 확인하기

614
00:52:08,330 --> 00:52:10,190
하지만, 그냥 코드를 겪고

615
00:52:10,190 --> 00:52:14,260
당신이 메모리를 할당했을 수도있는 이해.

616
00:52:14,260 --> 00:52:21,340
보통 당신은 "파일의 끝에서 난 그냥 내 숲에 숲을 제거하는거야"라고 할 수

617
00:52:21,340 --> 00:52:23,850
그래서 기본적으로 무료로, 그 메모리를 지우 즉,

618
00:52:23,850 --> 00:52:28,310
"그리고 나는 또한 파일을 닫 후 내 프로그램이 종료 것입니다 거예요."

619
00:52:28,310 --> 00:52:33,810
그러나 프로그램이 종료되는 그 유일한 시간은?

620
00:52:33,810 --> 00:52:37,880
아니, 때문에 때때로 어떻게 오류가 발생했을 수 있습니다.

621
00:52:37,880 --> 00:52:42,080
우리가 파일을 열 수 없습니다 또는 우리는 다른 나무를 만들 수 없습니다

622
00:52:42,080 --> 00:52:49,340
또는 오류의 일부 종류의 메모리 할당 과정에서 사고 때문에 NULL 반환.

623
00:52:49,340 --> 00:52:56,710
오류가 발생하고 우리는 돌아 종료합니다.

624
00:52:56,710 --> 00:53:02,040
그래서 당신은 프로그램이 가능한 모든 시간 종료 할 수 있는지 확인하려면

625
00:53:02,040 --> 00:53:06,980
거기 당신의 기억을 모두 확보하고 싶습니다.

626
00:53:06,980 --> 00:53:13,370
그것은 당신이 코드를 종료하는 main () 함수의 맨 끝은 아닐 거예요.

627
00:53:13,370 --> 00:53:20,780
당신은 당신의 코드가 잠재적으로 조기에 제공 할 수있는 모든 인스턴스에 다시보고 싶어요

628
00:53:20,780 --> 00:53:25,070
그리고 무료로 어떤 메모리는 의미가있다.

629
00:53:25,070 --> 00:53:30,830
당신은 숲을 만들고 그 true를 반환이라고했다 말한다.

630
00:53:30,830 --> 00:53:34,230
그런 다음 당신은 아마 당신의 숲을 제거 할 필요가 없습니다

631
00:53:34,230 --> 00:53:37,080
당신은 아직 숲이 없기 때문입니다.

632
00:53:37,080 --> 00:53:42,130
그러나 코드의 모든 시점에서 당신은 성급하게 제공 할 수있는

633
00:53:42,130 --> 00:53:46,160
당신이 가능한 모든 메모리를 확보되었는지 확인하고 싶습니다.

634
00:53:46,160 --> 00:53:50,020
>> 그래서 우리는 메모리를 자유롭게 처리하고 잠재적 인 누수가 발생하는 경우,

635
00:53:50,020 --> 00:53:55,440
우리는 우리의 판단과 논리를 사용하지 만 원

636
00:53:55,440 --> 00:54:01,850
뿐만 아니라 우리가 제대로 여부를 우리의 기억을 모두 해제 여부를 결정하기 위해 Valgrind 사용합니다.

637
00:54:01,850 --> 00:54:09,460
당신도 퐁퐁에서 Valgrind를 실행할 수 있습니다 그리고 당신은 또한에 합격해야

638
00:54:09,460 --> 00:54:14,020
명령 줄 인수의 오른쪽 숫자는 Valgrind합니다.

639
00:54:14,020 --> 00:54:18,100
당신은 실행할 수 있지만, 출력이 좀 이상한 것입니다.

640
00:54:18,100 --> 00:54:21,630
우리는 도전자와 함께하기 위해 사용되는 비트 수가있어하지만, 우리는 여전히 좀 더 도움이 필요합니다

641
00:54:21,630 --> 00:54:26,450
그럼, 누출 확인 = 전체와 같은 몇 가지 플래그와 함께 실행

642
00:54:26,450 --> 00:54:32,040
아마 우리가 우리에게 Valgrind에 좀 더 도움이 출력을 제공 할 것입니다.

643
00:54:32,040 --> 00:54:39,040
>> 그런 다음 디버깅하는 또 다른 유용한 팁은 diff 명령입니다.

644
00:54:39,040 --> 00:54:48,520
당신은 후우의 직원의 구현에 액세스 실행하는 텍스트 파일에, 수

645
00:54:48,520 --> 00:54:55,400
그리고 구체적으로, 이진 파일, 이진 후우 파일로 출력.

646
00:54:55,400 --> 00:54:59,440
그런 다음 그 이진 파일에 자신의 퍼프를 실행하는 경우

647
00:54:59,440 --> 00:55:03,950
그리고 이상적으로, 당신 출력 된 텍스트 파일은 동일한 될 것입니다

648
00:55:03,950 --> 00:55:08,200
당신은 집에 전달 된 원래 하나에

649
00:55:08,200 --> 00:55:15,150
난 여기 예제로 hth.txt를 사용하고 그건 당신이 사양에 대한 이야기​​ 하​​나.

650
00:55:15,150 --> 00:55:21,040
그 말 그대로 그냥 HTH 한 다음 줄 바꿈입니다.

651
00:55:21,040 --> 00:55:30,970
그러나 확실히 부담하면 확실히 이상 예제를 사용하는 것이 좋습니다

652
00:55:30,970 --> 00:55:32,620
텍스트 파일에 대해.

653
00:55:32,620 --> 00:55:38,110
>> 당신은 압축을 푸는 아마도 압축에서 총을 쏘면 수

654
00:55:38,110 --> 00:55:41,600
전쟁과 평화 등이 도전자에 사용하는 파일의 일부

655
00:55:41,600 --> 00:55:46,710
나 제인 오스틴이나 그런 걸 - 멋진 일이 될 것이다 - 또는 오스틴,

656
00:55:46,710 --> 00:55:51,880
우리는 그것에 큰 파일을 다루는 종류의 오지 않기 때문에

657
00:55:51,880 --> 00:55:55,590
우리는 여기에서 다음 도구 LS-리터를 사용한 경우.

658
00:55:55,590 --> 00:56:01,150
우리는 기본적으로 현재 디렉토리에있는 모든 내용을 나열인가요으로 사용하고 있습니다.

659
00:56:01,150 --> 00:56:07,860
플래그 - 나에 합격하는 것은 실제로 그 파일의 크기를 표시합니다.

660
00:56:07,860 --> 00:56:12,690
당신이 pset의 사양을 연다면, 사실은, 바이너리 파일을 만드는 과정을 안내합니다

661
00:56:12,690 --> 00:56:16,590
의를 피 우니, 당신은 매우 작은 파일을 보면

662
00:56:16,590 --> 00:56:23,910
을 압축하고 모든 정보를 번역의 공간 비용

663
00:56:23,910 --> 00:56:26,980
그렇게 모든 주파수와 일의 실제 혜택은 넘어서

664
00:56:26,980 --> 00:56:30,000
처음에 파일을 압축을.

665
00:56:30,000 --> 00:56:37,450
당신이 더 이상 텍스트 파일에서 실행한다면, 그럼 당신은 당신이 이익을 얻을 시작하는 볼 수 있습니다

666
00:56:37,450 --> 00:56:40,930
그 파일을 압축 인치

667
00:56:40,930 --> 00:56:46,210
>> 그리고 마지막으로, 우리는 확실히 너무 유용 할 것이다 우리의 오랜 친구의 GDB를 갖추고 있습니다.

668
00:56:48,360 --> 00:56:55,320
>> 우리는 나무를 만들기의 아마 후우 나무 나 과정에 대한 질문이 있습니까

669
00:56:55,320 --> 00:56:58,590
또는 Huff'n 퍼프에 다른 질문?

670
00:57:00,680 --> 00:57:02,570
좋아요. 내가 좀 주위를있을거야.

671
00:57:02,570 --> 00:57:06,570
>> 감사합니다, 여러분. 이 연습 6이었다. 그리고 행운을 빌어 요.

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