1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> 스피커 1 : 좋아, 그래서 이것은이다
CS50이 주 다섯의 끝입니다.

3
00:00:15,860 --> 00:00:19,220
그리고 그 마지막 시간을 기억 우리
시작 애호가 데이터보고

4
00:00:19,220 --> 00:00:22,310
해결하기 위해 시작 구조
소개하기 시작 문제,

5
00:00:22,310 --> 00:00:25,640
새로운 문제가 있지만,이 열쇠
나사의 종류였습니다 우리

6
00:00:25,640 --> 00:00:27,940
노드에서 노드로 수행하기 시작했다.

7
00:00:27,940 --> 00:00:30,085
그래서 물론이다
단일 연결리스트.

8
00:00:30,085 --> 00:00:31,960
그리고에 의해 단독으로 연결된
난 그냥 거기에 하나의 의미

9
00:00:31,960 --> 00:00:33,380
그 각 노드 사이에 스레드.

10
00:00:33,380 --> 00:00:35,890
당신은 애호가 수행 할 수 있습니다 밝혀
이중 연결리스트 같은 것들

11
00:00:35,890 --> 00:00:38,470
당신은 화살표가된다
양방향으로 가고있는

12
00:00:38,470 --> 00:00:40,320
특정 효율성에 도움이 될 수 있습니다.

13
00:00:40,320 --> 00:00:42,000
그러나 이것은 문제를 해결?

14
00:00:42,000 --> 00:00:43,500
이 무슨 문제를 해결하는 데 도움이 되었습니까?

15
00:00:43,500 --> 00:00:46,620
우리는 월요일에 왜 관심을 했습니까?

16
00:00:46,620 --> 00:00:49,820
왜, 이론적으로, 우리는 월요일에 관심을 했습니까?

17
00:00:49,820 --> 00:00:50,630
그것은 무엇을합니까?

18
00:00:50,630 --> 00:00:51,950
>> 청중 : 우리는 동적으로 크기를 조정할 수 있습니다.

19
00:00:51,950 --> 00:00:53,740
>> 스피커 1 : OK, 우리가 할 수있는 그렇게
동적으로 크기를 조정합니다.

20
00:00:53,740 --> 00:00:54,710
그럼 당신의 모두를 수행.

21
00:00:54,710 --> 00:00:57,560
그래서 당신은 동적으로 크기를 조정할 수 있습니다
데이터 구조, 배열, 반면

22
00:00:57,560 --> 00:01:00,760
리콜, 당신은 알고있다
선험적 공간이 얼마나 당신이 원하는

23
00:01:00,760 --> 00:01:03,870
당신은 조금 더 필요로하는 경우
공간, 당신은 운이 가지입니다.

24
00:01:03,870 --> 00:01:05,560
당신은 완전히 새로운 배열을 생성해야합니다.

25
00:01:05,560 --> 00:01:07,893
당신은 모든 이동해야 당신의
다른 하나의 데이터,

26
00:01:07,893 --> 00:01:10,600
결국 기존의 배열을 해제
당신이 할 수있는 한 후 진행하면.

27
00:01:10,600 --> 00:01:13,891
어떤 단지 매우 비용이 많이 드는 느낌이 매우
비효율적, 실제로 그것을 할 수 있습니다.

28
00:01:13,891 --> 00:01:14,890
그러나이 모두 좋지 않다.

29
00:01:14,890 --> 00:01:18,180
우리는 가격을 지불 한 것이었다
더 확실한 가격의 우리

30
00:01:18,180 --> 00:01:20,550
링크 된 목록을 사용하여 지불?

31
00:01:20,550 --> 00:01:22,825
>> 청중 : 우리는 사용할 필요가
각각에 대해 두 공간.

32
00:01:22,825 --> 00:01:25,200
스피커 1 : 그래, 그래서 우리가 필요로하는
두 배 이상 많은 공간이있다.

33
00:01:25,200 --> 00:01:27,700
사실, 난 실현이 그림의
조금이라도 오해의 소지를,

34
00:01:27,700 --> 00:01:32,200
때문에 현대의 많은에 CS50의 IDE에
컴퓨터, 포인터 또는 주소

35
00:01:32,200 --> 00:01:33,700
사실 4 바이트에 있지 않습니다.

36
00:01:33,700 --> 00:01:36,090
그것은 매우 자주이있어
일 8 바이트, 어떤

37
00:01:36,090 --> 00:01:38,530
바닥 수단 가장
실제로이 직사각형

38
00:01:38,530 --> 00:01:40,900
의 두 배 종류의
내가 그린 한 것과 큰,

39
00:01:40,900 --> 00:01:44,409
이는 당신이 3 배를 사용하는 것을 의미
우리가 달리있을 수 있습니다 많은 공간.

40
00:01:44,409 --> 00:01:46,700
지금 동시에, 우리는 야
여전히 바이트를 말하는 거죠?

41
00:01:46,700 --> 00:01:49,140
우리는 반드시 이야기하지 않을
메가 바이트 또는 기가 바이트,

42
00:01:49,140 --> 00:01:51,000
이러한 데이터하지 않는 구조는 큰 얻을.

43
00:01:51,000 --> 00:01:54,510
>> 그래서 오늘 우리는 생각하기 시작
우리는 데이터를 탐색하는 방법

44
00:01:54,510 --> 00:01:57,310
보다 효율적의 경우
사실은 데이터가 더 큰 가져옵니다.

45
00:01:57,310 --> 00:02:00,360
그러나 이제 정규화 해보자
먼저 작업

46
00:02:00,360 --> 00:02:02,460
당신은이에 할 수있는
데이터 구조 가지.

47
00:02:02,460 --> 00:02:04,790
링크 같은 뭔가
목록은 일반적으로 지원

48
00:02:04,790 --> 00:02:07,514
작업은 삭제 좋아,
삽입하고 검색 할 수 있습니다.

49
00:02:07,514 --> 00:02:08,639
그리고 그 무엇을 의미합니까?

50
00:02:08,639 --> 00:02:11,222
그건 그냥, 그 일반적 의미
사람들이 연결리스트를 사용하는 경우,

51
00:02:11,222 --> 00:02:14,287
그들은 또는 다른 사람이 구현했습니다
삭제, 삽입 등의 기능,

52
00:02:14,287 --> 00:02:16,120
및 검색, 당신은 할 수 있습니다
실제로 뭔가를

53
00:02:16,120 --> 00:02:18,030
데이터 구조에 유용하다.

54
00:02:18,030 --> 00:02:20,760
그럼 잠깐 살펴 보자
우리가 구현하는 방법에

55
00:02:20,760 --> 00:02:24,530
연결리스트에 대한 몇 가지 코드는 다음과 같이 다음과 같습니다.

56
00:02:24,530 --> 00:02:27,885
>> 그래서이 그냥 C 코드입니다,
심지어 완전한 프로그램

57
00:02:27,885 --> 00:02:29,260
정말 빠르게 휘저어있다.

58
00:02:29,260 --> 00:02:32,300
그것은 분포 온라인 아니다
코드, 실제로 실행되지 않습니다 때문이다.

59
00:02:32,300 --> 00:02:33,790
하지만 난 그냥했습니다 통지
코멘트는 말했다와 함께,

60
00:02:33,790 --> 00:02:36,130
점 점 점, 거기에 뭔가
가,가, 뭔가를 점 점 점.

61
00:02:36,130 --> 00:02:38,410
그리고 그냥 살펴 보자
수분이 많은 부분은 무엇인지.

62
00:02:38,410 --> 00:02:40,790
그래서 라인 세에,
이 지금 리콜

63
00:02:40,790 --> 00:02:45,960
우리는 마지막 노드를 선언 제안 된
시간, 그 직사각형 개체 중 하나.

64
00:02:45,960 --> 00:02:48,790
그것은, 우리가 N 전화 할게 int를 가지고
그러나 우리는 무엇을 호출 할 수 있습니다,

65
00:02:48,790 --> 00:02:51,920
다음 구조체 노드 별은 다음했다.

66
00:02:51,920 --> 00:02:55,520
그리고 바로, 그 두 번째 분명합니다
라인, 라인 여섯에, 그것은 무엇인가?

67
00:02:55,520 --> 00:02:57,930
그것은 우리를 위해 무엇을하고 있는가?

68
00:02:57,930 --> 00:03:01,044
그것은 확실히 더 보이기 때문에
우리 보통의 변수보다 더 애매.

69
00:03:01,044 --> 00:03:02,740
>> 청중 : 그것은 하나를 통해 이동합니다.

70
00:03:02,740 --> 00:03:04,650
>> 스피커 1 : 그것은 하나를 통해 이동합니다.

71
00:03:04,650 --> 00:03:08,580
그리고, 더 정확하게하기
이는 주소를 저장할

72
00:03:08,580 --> 00:03:11,582
될 운명이야 노드의
의미 옆에, 오른쪽?

73
00:03:11,582 --> 00:03:13,540
그래서에 없을거야
반드시 아무것도 이동합니다.

74
00:03:13,540 --> 00:03:15,290
그냥 것
인 값을 저장

75
00:03:15,290 --> 00:03:17,170
주소 될 것
다른 노드,

76
00:03:17,170 --> 00:03:20,810
우리가 구조체 말한 이유입니다
노드 스타, 스타 나타내는

77
00:03:20,810 --> 00:03:22,370
포인터 또는 주소입니다.

78
00:03:22,370 --> 00:03:26,390
좋아, 그럼 지금 당신은 우리가 있다고 가정하면
우리에게 사용할 수있는이 N 및하자

79
00:03:26,390 --> 00:03:29,490
다른 사람이 있다고 가정
정수의 전체 무리를 삽입

80
00:03:29,490 --> 00:03:30,400
연결리스트로.

81
00:03:30,400 --> 00:03:35,640
그리고 링크 된 목록입니다
어떤 점 가리키는

82
00:03:35,640 --> 00:03:39,040
의 변수라는 목록
매개 변수로 여기에 전달,

83
00:03:39,040 --> 00:03:43,120
어떻게 라인 가야합니까
(14) 검색을 구현​​?

84
00:03:43,120 --> 00:03:45,990
즉, 내가 구현하고있는 경우
그 목적은 인생의 기능

85
00:03:45,990 --> 00:03:48,889
다음 INT와을하는 것입니다
연결리스트의 시작,

86
00:03:48,889 --> 00:03:50,430
즉, 연결리스트에 대한 포인터입니다.

87
00:03:50,430 --> 00:03:52,992
처음처럼, 나는 다윗을 누가 생각
우리의 자원 봉사는, 월요일에 있었다

88
00:03:52,992 --> 00:03:54,700
그는 가리키는했다
전체 연결리스트,

89
00:03:54,700 --> 00:03:57,820
우리가 통과하는 것처럼입니다
데이비드 여기에 우리의 인수로.

90
00:03:57,820 --> 00:03:59,990
어떻게 우리는이 목록을 통과 가야합니까?

91
00:03:59,990 --> 00:04:04,640
글쎄, 그것은 밝혀 그 비록
포인터는, 우리에게 지금 비교적 새로운

92
00:04:04,640 --> 00:04:07,010
우리는 상대적으로이 작업을 수행 할 수 있습니다
노골적.

93
00:04:07,010 --> 00:04:09,500
>> 나는 앞서 갈거야 및
임시 변수를 선언하는

94
00:04:09,500 --> 00:04:12,364
규칙에 의해 단지 것입니다
에가, PTR 포인터라고, 또는

95
00:04:12,364 --> 00:04:14,030
하지만 당신은 당신이 원하는 무엇이든을 호출 할 수 있습니다.

96
00:04:14,030 --> 00:04:16,470
그리고 초기화거야
그 목록의 시작.

97
00:04:16,470 --> 00:04:20,050
그래서 당신은 종류의이 생각할 수
내가 교사로서 다른 날,

98
00:04:20,050 --> 00:04:23,580
종류의 사람을 가리키는
자원 봉사자로서의 인간 사이.

99
00:04:23,580 --> 00:04:26,470
그래서의 임시 변수를 해요
단지 같은 것을 가리키는

100
00:04:26,470 --> 00:04:31,390
우리는 우연히라는 것을
자원 봉사 다윗은 또한 지적했다.

101
00:04:31,390 --> 00:04:35,440
이제 포인터가있는 동안
null이 아닌, 때문에 리콜

102
00:04:35,440 --> 00:04:40,350
그 null가 특별한 감시 값
이리스트의 단부를 획정

103
00:04:40,350 --> 00:04:44,280
내가 가리키는 아니에요 동안 그렇게
우리의 마지막 자원 봉사 등의 접지

104
00:04:44,280 --> 00:04:47,190
이고,의 앞서 가자
그리고 다음을 수행하십시오.

105
00:04:47,190 --> 00:04:51,820
pointer-- 경우 지금은 종류의 원하는
우리는 학생했던 일을

106
00:04:51,820 --> 00:04:57,410
structure-- 포인터 점 옆 경우
equals-- 포인터 점 N은, 동일 오히려 경우

107
00:04:57,410 --> 00:05:02,290
이 변수 N은 같
에 통과의 주장,

108
00:05:02,290 --> 00:05:05,370
나는 앞서 가고 싶어
그리고 true를 돌려 말한다.

109
00:05:05,370 --> 00:05:11,020
나는 내부 수 없음을 발견했다
내 연결리스트의 노드 중 하나.

110
00:05:11,020 --> 00:05:13,500
그러나 점 더 이상
이러한 맥락에서 작동,

111
00:05:13,500 --> 00:05:17,260
포인터, PTR은, 때문에
실제로 포인터, 주소,

112
00:05:17,260 --> 00:05:20,632
우리는 실제로 놀라 울 수
구문의 마지막 조각을 사용

113
00:05:20,632 --> 00:05:22,590
차종의 종류
직관적 인 감각과 실제로

114
00:05:22,590 --> 00:05:27,870
에서 이동 즉, 여기에 화살표를 사용하여
거기에 정수에 해당 주소.

115
00:05:27,870 --> 00:05:30,160
그래서 매우 유사
도트 연산자에 정신

116
00:05:30,160 --> 00:05:33,860
하지만, 포인터는 포인터 없기 때문에
아닌 실제 구조체 자체,

117
00:05:33,860 --> 00:05:35,380
우리는 단지에있는 화살표를 사용합니다.

118
00:05:35,380 --> 00:05:40,620
>> 경우에 따라서 현재 노드가 나는,
임시 변수가 가리키는입니다

119
00:05:40,620 --> 00:05:43,060
N, 내가 무엇을 하시겠습니까되지 않는 이유는 무엇입니까?

120
00:05:43,060 --> 00:05:45,910
글쎄, 내 인간 자원 봉사자
우리가 다른 날 여기 있다고,

121
00:05:45,910 --> 00:05:49,710
내 첫 인간은 하나의 내가 아닌 경우
원하고, 어쩌면 두 번째 사람은 아니다

122
00:05:49,710 --> 00:05:52,660
내가 원하는 한, 세 번째, 내가
이동 물리적으로 유지해야합니다.

123
00:05:52,660 --> 00:05:54,690
마찬가지로 내가 어떻게 목록을 단계별로합니까?

124
00:05:54,690 --> 00:05:57,470
우리가 배열이있을 때, 당신을
그냥 플러스 플러스 좋아했다.

125
00:05:57,470 --> 00:06:03,660
그러나이 경우에 충분
다음, 포인터, 도착, 포인터를 않습니다.

126
00:06:03,660 --> 00:06:07,580
즉, 다음 필드
왼쪽 손의 모든처럼

127
00:06:07,580 --> 00:06:10,880
월요일에 우리의 인간 자원 봉사자
다른 노드를 가리 키도록 사용했다.

128
00:06:10,880 --> 00:06:12,890
사람들은 자신의 다음 이웃이었다.

129
00:06:12,890 --> 00:06:17,060
>> 나는이 목록을 통해 단계 싶다면,
난 그냥, 더 이상 내가 할 플러스 플러스 없습니다

130
00:06:17,060 --> 00:06:20,120
내가 대신 말을해야
나는, 포인터는 것입니다

131
00:06:20,120 --> 00:06:24,650
다음 필드는 어떤 같음,
다음 필드는 다음 필드가 있습니다

132
00:06:24,650 --> 00:06:28,350
그 왼쪽 손 모두 다음
우리는 무대 가리키는 것으로

133
00:06:28,350 --> 00:06:30,000
일부 이후의 값.

134
00:06:30,000 --> 00:06:32,590
그리고 통과하는 경우
그 전체 반복,

135
00:06:32,590 --> 00:06:39,330
그리고 마지막으로, 내가 가진 NOT NULL 히트
발견 N 아직, 난 그냥 false를 돌려줍니다.

136
00:06:39,330 --> 00:06:44,100
그래서 다시, 우리가 여기서하고있는 모든 것을,
잠시 전에 그림에 따라,

137
00:06:44,100 --> 00:06:47,840
가리키는 의해 시작
아마도 목록의 시작.

138
00:06:47,840 --> 00:06:50,970
그리고 내가 확인 값입니다
나는 아홉 동일한 찾고 있어요?

139
00:06:50,970 --> 00:06:52,650
그렇다면, 나는 true를 돌려 나는 끝났어요.

140
00:06:52,650 --> 00:06:56,450
그렇지 않은 경우, 나는 내 손을 업데이트,
일명 포인터를 가리 키도록

141
00:06:56,450 --> 00:06:59,540
다음 화살표의 위치에서, 그리고
그 다음 화살표의 위치,

142
00:06:59,540 --> 00:07:00,480
그리고 다음.

143
00:07:00,480 --> 00:07:03,770
간단히 말해서 나는 당신이 배열을 통해 걷고 있어요.

144
00:07:03,770 --> 00:07:06,010
>> 그래서 다시, 누가 무슨 상관이 야?

145
00:07:06,010 --> 00:07:07,861
마찬가지로이에 대한 성분 무엇인가?

146
00:07:07,861 --> 00:07:10,360
글쎄, 우리가 도입 리콜
스택의 개념, 어느

147
00:07:10,360 --> 00:07:15,400
그것의 같은 추상적 인 데이터가있는 한 유형입니다
하지 C 것은,이 CS50 일이 아니다,

148
00:07:15,400 --> 00:07:19,430
그것은 추상적 인 아이디어의 생각
위에 다른 물건을 적재

149
00:07:19,430 --> 00:07:21,820
즉 구현 될 수있다
다른 방법의 무리가.

150
00:07:21,820 --> 00:07:25,600
그리고 우리가 제시 한 방법으로했다
배열, 또는 링크 된 목록.

151
00:07:25,600 --> 00:07:29,570
그리고는 그 canonically 밝혀
스택은 두 개 이상의 작업을 지원합니다.

152
00:07:29,570 --> 00:07:32,320
그리고 버즈 단어에, 푸시 있습니다
스택에 뭔가를 밀어

153
00:07:32,320 --> 00:07:34,770
새로운 트레이 등
식당, 또는 팝업,

154
00:07:34,770 --> 00:07:39,000
이는 최상위을 제거하는 것을 의미한다
식당에서 스택에서 트레이

155
00:07:39,000 --> 00:07:41,500
홀, 그리고 어쩌면 일부
다른 작업뿐만 아니라.

156
00:07:41,500 --> 00:07:45,770
그래서 우리가 어떻게 구조를 정의 할 수 있습니다
우리는 지금 스택을 호출하고 있는지?

157
00:07:45,770 --> 00:07:50,020
>> 음, 우리는 필요한 모든이
내가 말할 C로 우리의 처분에 구문,

158
00:07:50,020 --> 00:07:53,830
나에게의 타입 정의를 제공
스택의 내부 구조체,

159
00:07:53,830 --> 00:07:58,030
나는의 배열은 말할거야
정수의 무리하고 크기.

160
00:07:58,030 --> 00:08:00,930
그래서 다른 말로하면, 내가 원하는 경우
이 코드를 구현하기 위해,

161
00:08:00,930 --> 00:08:03,830
내가 가서 그냥 가지하자
이 무슨 말을 그립니다.

162
00:08:03,830 --> 00:08:06,317
이 말을 그래서, 나에게 줄
배열을 가지고 구조,

163
00:08:06,317 --> 00:08:09,400
나는, 용량이 무엇인지 모른다
그것은 내가했는지 분명히 몇 가지 상수이다

164
00:08:09,400 --> 00:08:10,858
다른 곳에서 정의하고, 그 괜찮아요.

165
00:08:10,858 --> 00:08:15,260
그러나, 그것은 단지 하나의 가정
둘, 셋, 넷, 다섯.

166
00:08:15,260 --> 00:08:16,700
그래서 용량은 5입니다.

167
00:08:16,700 --> 00:08:21,730
내부에이 요소 내
구조 번호를 호출됩니다.

168
00:08:21,730 --> 00:08:24,020
그리고 나에게도 필요
다른 변수 분명히

169
00:08:24,020 --> 00:08:27,814
처음에 내가 갈거야라는 크기
0으로 초기화되는 규정합니다.

170
00:08:27,814 --> 00:08:29,730
아무것도에 존재하지 않는 경우
스택, 크기는 제로

171
00:08:29,730 --> 00:08:31,420
그것은 숫자에 쓰레기 값을합니다.

172
00:08:31,420 --> 00:08:33,450
나는 아직 거기에 무슨 생각이 없다.

173
00:08:33,450 --> 00:08:36,059
>> 내가 밀어 싶다면
스택에 뭔가,

174
00:08:36,059 --> 00:08:40,780
내가 함수 푸시를 호출한다고 가정하고,
나는, 숫자 50과 같은 50를 밀어 말

175
00:08:40,780 --> 00:08:44,090
어디 제안 것이다
나는이 배열에 그립니다?

176
00:08:44,090 --> 00:08:47,124
다섯 가지 가능한 대답이있다.

177
00:08:47,124 --> 00:08:48,790
당신은 어디에서 수 (50)를 밀어 하시겠습니까?

178
00:08:48,790 --> 00:08:51,899
여기에 목표 경우, 다시 전화
기능 푸시는, 인수 전달

179
00:08:51,899 --> 00:08:52,940
50, 나는 그것을 어디에 배치해야합니까?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
다섯 possible-- 20 %의 확률로
의 제대로 추측.

182
00:08:59,052 --> 00:08:59,896
네?

183
00:08:59,896 --> 00:09:00,740
>> 청중 : 오른쪽.

184
00:09:00,740 --> 00:09:01,990
>> 스피커 1 : 오른쪽.

185
00:09:01,990 --> 00:09:08,359
25 %의 확률로 지금있다
의 제대로 추측.

186
00:09:08,359 --> 00:09:09,650
그래서 사실은 잘 될 것입니다.

187
00:09:09,650 --> 00:09:12,770
규칙에 따라, 나는 배열을 말할 것이다,
우리는 일반적으로, 왼쪽에서 시작할 것

188
00:09:12,770 --> 00:09:14,519
그러나 우리는 확실히 할 수
오른쪽에서 시작합니다.

189
00:09:14,519 --> 00:09:17,478
그래서 여기에 스포일러가 난 것
아마 왼쪽에 그리는 것,

190
00:09:17,478 --> 00:09:20,060
다만 정상적인 배열 경우처럼
나는 왼쪽에서 오른쪽으로가는 시작합니다.

191
00:09:20,060 --> 00:09:21,780
하지만 당신은 전환 할 수있는 경우
산술, 괜찮아요.

192
00:09:21,780 --> 00:09:23,060
그냥 기존 아니다.

193
00:09:23,060 --> 00:09:24,880
좋아, 내가 하나를 만들 필요가
하지만 더 변화.

194
00:09:24,880 --> 00:09:27,710
지금은 뭔가를 밀어했는지
스택에, 다음은 뭐지?

195
00:09:27,710 --> 00:09:29,400
>> 좋아, 내가 크기를 증가해야합니다.

196
00:09:29,400 --> 00:09:32,600
그래서 내가 앞으로 그냥 가자
제로이었다이를 업데이트합니다.

197
00:09:32,600 --> 00:09:35,950
그리고 대신에 지금은 갈거야
값 하나에 넣어.

198
00:09:35,950 --> 00:09:39,460
그리고 지금은 서로를 밀어 가정
스택에 수 (51) 등을들 수있다.

199
00:09:39,460 --> 00:09:42,680
글쎄, 난 하나 더 확인해야
크기 두 가지에 달려 변화.

200
00:09:42,680 --> 00:09:46,100
그리고 내가 한 번 더 밀어 가정
(61)와 같은 스택에 수,

201
00:09:46,100 --> 00:09:52,530
지금은 크기를 업데이트해야 하나
시간, 크기와 값 3을 얻는다.

202
00:09:52,530 --> 00:09:54,690
그리고 지금은 팝업을 호출한다고 가정합니다.

203
00:09:54,690 --> 00:09:57,250
지금 관례, 팝,
인수를하지 않습니다.

204
00:09:57,250 --> 00:10:00,430
스택 전체
트레이 은유의 포인트

205
00:10:00,430 --> 00:10:03,450
당신이 재량권을하지 않아도됩니다
용지함을 가서, 모든 당신은 할 수있다

206
00:10:03,450 --> 00:10:06,330
에서 최상위를 팝업됩니다
스택, 단지 때문이다.

207
00:10:06,330 --> 00:10:08,010
즉,이 데이터 구조가하는 일입니다.

208
00:10:08,010 --> 00:10:12,250
>> 만약 그 논리에 의해 그래서
팝, 무엇을 벗기라고?

209
00:10:12,250 --> 00:10:13,080
그래서 61.

210
00:10:13,080 --> 00:10:15,402
그래서 정말 컴퓨터는 무엇인가
메모리에 할 건가요?

211
00:10:15,402 --> 00:10:16,610
어떻게 내 코드는 무엇을해야합니까?

212
00:10:16,610 --> 00:10:20,330
당신은 무엇을 제안 할 것이다
우리는 화면 변경?

213
00:10:20,330 --> 00:10:23,410
무엇을 변경해야합니까?

214
00:10:23,410 --> 00:10:24,960
죄송합니다?

215
00:10:24,960 --> 00:10:26,334
그래서 우리는 (61)을 제거.

216
00:10:26,334 --> 00:10:27,500
그래서 나는 확실히 그렇게 할 수 있습니다.

217
00:10:27,500 --> 00:10:28,640
그리고 (61)을 제거 할 수 있습니다.

218
00:10:28,640 --> 00:10:30,980
그리고 다른 무엇
변화가 일어날 필요가 있겠습니까?

219
00:10:30,980 --> 00:10:33,160
크기는 아마 두로 돌아 가야한다.

220
00:10:33,160 --> 00:10:34,210
그리고 그 괜찮아요.

221
00:10:34,210 --> 00:10:36,690
그러나 분, 크기를 기다립니다
잠시 전 세였다.

222
00:10:36,690 --> 00:10:38,240
그냥 빠른 전성 검사를 해 보자.

223
00:10:38,240 --> 00:10:41,810
우리는 어떻게 우리가 알고 않았다
(61)을 제거하고 싶어?

224
00:10:41,810 --> 00:10:42,760
우리가 보여주고 있기 때문에.

225
00:10:42,760 --> 00:10:46,450
그래서 나는이 두 번째 공간이 있습니다.

226
00:10:46,450 --> 00:10:48,470
>> 난, 잠깐
일주일에 두 다시 생각

227
00:10:48,470 --> 00:10:51,660
우리는 얘기를 시작했을 때
이 위치 제로였다 배열,

228
00:10:51,660 --> 00:10:55,920
이 위치 하나,이 위치했다
두,이 위치 셋, 넷입니다,

229
00:10:55,920 --> 00:10:58,460
이처럼 보인다
크기 사이의 관계

230
00:10:58,460 --> 00:11:02,780
내가 원하는 요소를 제거합니다
배열에서 바로 무엇을 것 같습니다?

231
00:11:02,780 --> 00:11:05,120
크기 - 하나.

232
00:11:05,120 --> 00:11:07,786
그리고 그 방법으로 인간의
우리는 (61)이 먼저 알고있다.

233
00:11:07,786 --> 00:11:09,160
어떻게 컴퓨터가 알고있는거야?

234
00:11:09,160 --> 00:11:11,701
때 코드, 어디를 아마
크기 마이너스 하나를 수행 할,

235
00:11:11,701 --> 00:11:14,950
그래서 세 뺀 두하고 있다는 것입니다
우리는 (61)를 제거하는 것을 의미합니다.

236
00:11:14,950 --> 00:11:18,000
그리고 우리는 참으로 업데이트 할 수 있습니다
그 크기가 너무 크기 지금

237
00:11:18,000 --> 00:11:20,300
두 세에서 이동합니다.

238
00:11:20,300 --> 00:11:24,520
그냥 학자로, 내가 갈거야
내가 바로, 끝났어요 것을 제안 하는가?

239
00:11:24,520 --> 00:11:27,660
당신은 직관적 제안
제대로 나는 (61)을 제거한다.

240
00:11:27,660 --> 00:11:30,700
그러나이없는 내가 가지
종류의 (61)을 제거이라도?

241
00:11:30,700 --> 00:11:33,790
나는 효과적으로 잊어 버린
그것이 사실이있다.

242
00:11:33,790 --> 00:11:37,680
당신이 읽은 경우에, 다시 PSET4에 대한 생각
법의학에 대한 문서, PDF

243
00:11:37,680 --> 00:11:40,780
우리가 가진 것을 너희들은 읽기, 또는
PSET4이 주 읽습니다.

244
00:11:40,780 --> 00:11:44,300
이 실제로 밀접한 관계가 있음을 기억하라
컴퓨터 법의학의 모든 생각.

245
00:11:44,300 --> 00:11:47,820
어떤 컴퓨터가 일반적으로 수행하는 것입니다
뭔가가 어디 그냥 잊어

246
00:11:47,820 --> 00:11:51,300
하지만 가서 좋아하지 않는다
그것을 또는 재정의 스크래치하려고

247
00:11:51,300 --> 00:11:54,560
0과 1에 그 비트
또는 어떤 다른 임의의 패턴

248
00:11:54,560 --> 00:11:56,690
당신이하지 않으면 자신은 그렇게 의도적으로 않습니다.

249
00:11:56,690 --> 00:11:58,930
그래서 당신의 직관이었다
오른쪽의이 (61)을 제거 할 수 있습니다.

250
00:11:58,930 --> 00:12:00,650
그러나 현실에서, 우리는 귀찮게 할 필요가 없습니다.

251
00:12:00,650 --> 00:12:04,040
우리는 잊지 필요
그것은 우리의 크기를 변경하여이있다.

252
00:12:04,040 --> 00:12:05,662
>> 지금이 스택에 문제가있다.

253
00:12:05,662 --> 00:12:07,620
나는 일을 계속 밀고 경우
스택에, 무슨 일이야

254
00:12:07,620 --> 00:12:11,167
분명히 일어날 것
단지 잠시 시간?

255
00:12:11,167 --> 00:12:12,500
우리는 공간이 부족 될 것입니다.

256
00:12:12,500 --> 00:12:13,580
그리고 우리는 무엇을해야합니까?

257
00:12:13,580 --> 00:12:14,680
우리는 종류의 나사하고 있습니다.

258
00:12:14,680 --> 00:12:19,000
이 구현은 할 수 없습니다
사용하기 때문에 우리는, 배열의 크기를 조정

259
00:12:19,000 --> 00:12:21,240
이 구문, 당신의 경우
일주일에 두 다시 생각한다

260
00:12:21,240 --> 00:12:23,520
당신은 선언 한 후
어레이의 크기,

261
00:12:23,520 --> 00:12:26,780
우리는 아직 어디에 메커니즘을 보지 못했다
배열의 크기를 변경할 수있다.

262
00:12:26,780 --> 00:12:29,020
그리고 실제로 C는 해당 기능이 없습니다.

263
00:12:29,020 --> 00:12:32,524
당신이 말한다면 나에게 다섯 줄
Nths, 그들에게 전화 번호,

264
00:12:32,524 --> 00:12:33,940
즉, 당신이 그것을받을거야 모두이다.

265
00:12:33,940 --> 00:12:38,790
그래서 우리는 월요일로 지금,이
용액을 표현하는 능력

266
00:12:38,790 --> 00:12:42,480
하지만, 우리는 단지 조정할 필요
우리 스택의 정의

267
00:12:42,480 --> 00:12:46,840
일부 하드 코딩 배열하지 않으려면,
하지만 그냥 주소를 저장합니다.

268
00:12:46,840 --> 00:12:47,890
>> 이제 그 이유가 무엇입니까?

269
00:12:47,890 --> 00:12:51,690
이제 우리는 편안해야
사실 내 프로그램이 실행될 때,

270
00:12:51,690 --> 00:12:53,730
나는 아마 갈거야
인간에게 물어,

271
00:12:53,730 --> 00:12:55,110
얼마나 많은 숫자 당신은 저장 하시겠습니까?

272
00:12:55,110 --> 00:12:56,776
그래서 입력 어딘가에서 온있다.

273
00:12:56,776 --> 00:12:59,140
하지만 알고 나면
번호, 다음, 난 그냥 수

274
00:12:59,140 --> 00:13:02,470
제공하는 기능을 어떻게 사용
나 메모리의 덩어리?

275
00:13:02,470 --> 00:13:03,580
나는 malloc에​​ 사용할 수 있습니다.

276
00:13:03,580 --> 00:13:06,710
그리고 임의의 수를 말할 수있다
바이트 내가 다시이 Nths에 대한합니다.

277
00:13:06,710 --> 00:13:10,910
그리고 모든 나는 숫자에 저장해야
이 구조체의 내부 여기에 변수

278
00:13:10,910 --> 00:13:13,480
무엇을해야 하는가?

279
00:13:13,480 --> 00:13:18,440
무엇 실제로로 전환
이 시나리오의 숫자?

280
00:13:18,440 --> 00:13:21,300
네, 첫 번째 포인터
메모리의 청크의 바이트,

281
00:13:21,300 --> 00:13:24,940
또는보다 구체적으로는, 어드레스
그 바이트의 제.

282
00:13:24,940 --> 00:13:27,300
이 하나 있다면 상관 없어
바이트 또는 억 바이트,

283
00:13:27,300 --> 00:13:28,890
난 그냥 먼저 걱정해야합니다.

284
00:13:28,890 --> 00:13:31,530
때문에 무엇 malloc을 보장하고
내 운영체제 보장

285
00:13:31,530 --> 00:13:34,170
입니다 메모리 I의 덩어리
얻을, 그것은 인접 할 것입니다.

286
00:13:34,170 --> 00:13:35,378
간격이있을 것 아니에요.

287
00:13:35,378 --> 00:13:38,576
나는 50를 요구 한 경우에 따라서
바이트 또는 1,000 바이트,

288
00:13:38,576 --> 00:13:40,450
그들은 모두가 될거야
다시 다시 다시합니다.

289
00:13:40,450 --> 00:13:44,500
그리고 너무 오래 내가 어떻게 얼마나 큰 기억으로
많은 내가 알아야 할 모든 요구

290
00:13:44,500 --> 00:13:46,230
최초의 주소입니다.

291
00:13:46,230 --> 00:13:48,660
>> 그래서 지금 우리는 코드의 기능이 있습니다.

292
00:13:48,660 --> 00:13:51,280
이기는하지만, 그것은 우리를 취할 것
더 많은 시간이를 쓰기

293
00:13:51,280 --> 00:13:55,900
우리는 지금 그 메모리를 재 할당 할 수
그냥 거기에 다른 주소를 저장

294
00:13:55,900 --> 00:13:59,060
우리는 심지어 더 큰 이상을 원하는 경우
메모리의 작은 덩어​​리.

295
00:13:59,060 --> 00:14:00,170
그래서 여기에 무역 오프에.

296
00:14:00,170 --> 00:14:01,360
이제 우리는 활력을 얻을.

297
00:14:01,360 --> 00:14:03,350
우리는 여전히이
인접에 나는 주장하고있다.

298
00:14:03,350 --> 00:14:05,881
malloc을 우리에게 줄 것 때문에
메모리의 연속 된 덩어리.

299
00:14:05,881 --> 00:14:08,630
하지만이에 통증이 될 것입니다
우리의 목, 프로그래머,

300
00:14:08,630 --> 00:14:09,770
실제로 최대 코드.

301
00:14:09,770 --> 00:14:10,730
그것은 단지 더 많은 작업입니다.

302
00:14:10,730 --> 00:14:13,930
우리는 내가 무엇 유사 코드가 필요합니다
잠시 전 닌가.

303
00:14:13,930 --> 00:14:16,120
아주 행할 수 있지만, 복잡성을 추가합니다.

304
00:14:16,120 --> 00:14:19,520
그래서 개발자 시간, 프로그래머
시간은 또 다른 자원이다

305
00:14:19,520 --> 00:14:22,520
우리가 지출해야 할 수도 있음
약간의 시간이 새로운 기능을 얻을 수 있습니다.

306
00:14:22,520 --> 00:14:24,020
그리고 물론 큐가있다.

307
00:14:24,020 --> 00:14:26,227
우리는이에 가지 않을 것이다
많은 세부 사항 하나.

308
00:14:26,227 --> 00:14:27,560
하지만 정신에 매우 유사하다.

309
00:14:27,560 --> 00:14:31,220
나는 큐를 구현하고 수
그 대응 작업,

310
00:14:31,220 --> 00:14:35,660
대기열 또는 대기열에서 제외, 추가 또는 제거 등,
그것은, 그것을 말하는 단지 애호가 방법

311
00:14:35,660 --> 00:14:38,100
인큐 또는 디큐로는 다음과 같다.

312
00:14:38,100 --> 00:14:41,170
난 그냥 내 자신에게 구조체를 제공 할 수 있습니다
그 다시 숫자의 배열을 가지고,

313
00:14:41,170 --> 00:14:44,000
또 그 크기를 갖는,
하지만 왜 지금해야합니까

314
00:14:44,000 --> 00:14:46,940
큐의 앞을 추적하기 위해?

315
00:14:46,940 --> 00:14:50,630
내가 알 필요하지 않았다
내 스택의 앞.

316
00:14:50,630 --> 00:14:53,570
글쎄, 만약 내가 다시에 대한
queue-- 그냥 열심히하자

317
00:14:53,570 --> 00:14:57,870
다섯 같이 갖는으로 코딩
여기에 잠재적으로의 정수.

318
00:14:57,870 --> 00:15:00,940
그래서 이것은 제로, 하나, 둘, 셋, 넷이다.

319
00:15:00,940 --> 00:15:03,430
이 될 것입니다
다시 호출 번호.

320
00:15:03,430 --> 00:15:06,940
그리고이 크기라고한다.

321
00:15:06,940 --> 00:15:10,056
>> 왜이 충분하지
단지 크기가 있습니까?

322
00:15:10,056 --> 00:15:11,680
음,에 그 같은 번호를 눌러 보자.

323
00:15:11,680 --> 00:15:14,220
그래서 나는 큐에, 또는 밀어 pushed--.

324
00:15:14,220 --> 00:15:20,150
지금은 50을 대기열에, 그리고 것
51, 후 61, 도트는 도트와 도트.

325
00:15:20,150 --> 00:15:21,070
그래서 대기열입니다.

326
00:15:21,070 --> 00:15:23,176
나는 그 (61), 다음 (50), (51)의 대기열.

327
00:15:23,176 --> 00:15:25,050
그리고 그와 동일하게 나타남
지금까지 스택,

328
00:15:25,050 --> 00:15:27,190
를 제외하고 내가 한 변경을 할 필요가있다.

329
00:15:27,190 --> 00:15:33,680
나는이 크기를 업데이트해야합니다, 그래서 이동
이제 2-3 to 하나 0에서.

330
00:15:33,680 --> 00:15:35,760
어떻게 대기열에서 제외합니까?

331
00:15:35,760 --> 00:15:36,890
무엇 디큐으로됩니까?

332
00:15:36,890 --> 00:15:41,950
누가 먼저이 목록을 제공한다
그것은 애플 스토어에서 줄이 있다면?

333
00:15:41,950 --> 00:15:42,780
그래서 50.

334
00:15:42,780 --> 00:15:44,700
그래서 종류의 난이도가이 시간이다.

335
00:15:44,700 --> 00:15:47,880
마지막 반면 수퍼했다
쉽게 그냥 크기 마이너스 하나를 수행합니다

336
00:15:47,880 --> 00:15:51,440
나는 효과적으로 나의 배열의 끝에 도착
숫자가있는 곳, 그것은 61을 제거합니다.

337
00:15:51,440 --> 00:15:52,920
그러나 나는 61를 제거하지 않습니다.

338
00:15:52,920 --> 00:15:55,030
나는, (50)을 원하는 사람
오전 5시 00 분이 있었다

339
00:15:55,030 --> 00:15:56,790
위해 줄을
새로운 아이폰 또는 이것 저것.

340
00:15:56,790 --> 00:16:01,200
그래서 나는, 50 없애
바로,이 작업을 수행 할 수없는 이유는 무엇입니까?

341
00:16:01,200 --> 00:16:02,547
나는 (50)을 통과 할 수 있습니다.

342
00:16:02,547 --> 00:16:04,380
그러나 우리는 단지 우리를 말했다
그래서 항문 될 필요가 없습니다

343
00:16:04,380 --> 00:16:06,330
로 밖으로 긁거나 데이터를 숨 깁니다.

344
00:16:06,330 --> 00:16:08,090
그게 어디 우리는 잊을 수있다.

345
00:16:08,090 --> 00:16:12,330
>> 그러나 나는 지금 나의 크기를 변경하는 경우
두 사람은이 충분한 정보입니다

346
00:16:12,330 --> 00:16:15,711
내 큐에 무슨 일이 일어나고 있는지 알고?

347
00:16:15,711 --> 00:16:16,680
정말.

348
00:16:16,680 --> 00:16:19,830
내 크기가 두처럼하지만,
큐는 어디서부터 시작 않습니다,

349
00:16:19,830 --> 00:16:22,980
특히 나는 아직도이있는 경우
메모리에 그 같은 숫자.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
그래서 기억해야
이제 앞입니다.

352
00:16:27,090 --> 00:16:29,630
그래서 나는까지 제안 된
거기에, 우리는 단지라는거야

353
00:16:29,630 --> 00:16:33,729
그의 초기 N 번째 앞,
값은 무엇을 했어야?

354
00:16:33,729 --> 00:16:35,270
제로,리스트의 시작에 불과합니다.

355
00:16:35,270 --> 00:16:40,876
하지만 지금은 추가로 감소시키는합니다
크기는, 우리는 단지 전면을 증가.

356
00:16:40,876 --> 00:16:42,000
이제 여기에 또 다른 문제입니다.

357
00:16:42,000 --> 00:16:43,030
그래서 계속 한 번.

358
00:16:43,030 --> 00:16:47,520
이의 수를 가정
같은 121, 124, 다음, 젠,

359
00:16:47,520 --> 00:16:48,610
나는 공간이 부족 해요.

360
00:16:48,610 --> 00:16:50,390
하지만 난 아니에요, 분을 기다립니다.

361
00:16:50,390 --> 00:16:55,630
이야기를이 시점에서 그래서,
크기가 하나, 둘 것을 가정,

362
00:16:55,630 --> 00:17:00,370
셋, 넷, 그렇게한다고 가정
크기는, 전면이 하나이고, 4 개이고

363
00:17:00,370 --> 00:17:01,621
그래서 51 앞에있다.

364
00:17:01,621 --> 00:17:04,329
나는 여기에 다른 번호를 데려 가고 싶다는,
하지만, 젠장, 나는 공간이 부족 해요.

365
00:17:04,329 --> 00:17:06,710
하지만 난 지금, 정말 아니에요?

366
00:17:06,710 --> 00:17:11,192
좀 어디 넣을 수
(171)과 같은 부가 가치?

367
00:17:11,192 --> 00:17:13,400
그래, 내가 할 수있는 단지 종류의
바로, 다시 거기 가서?

368
00:17:13,400 --> 00:17:18,161
그리고 50을 교차, 또는
그냥 171으로 덮어.

369
00:17:18,161 --> 00:17:20,410
그리고 당신은 왜 궁금해하는 경우
우리의 숫자는, 그래서 무작위있어

370
00:17:20,410 --> 00:17:24,150
이들은 일반적으로 컴퓨터를 가져옵니다
CS50 후 하버드 대학 과학 교육 과정.

371
00:17:24,150 --> 00:17:27,510
하지만 좋은 최적화이었다,
지금 때문에 공간을 낭비하고 있지 않다.

372
00:17:27,510 --> 00:17:30,750
나는 아직도 기억해야
얼마나 큰이 일 총입니다.

373
00:17:30,750 --> 00:17:31,500
그것은 다섯 총입니다.

374
00:17:31,500 --> 00:17:33,375
에 내가 원하는하지 않기 때문에
(51)을 덮어 쓰기 시작합니다.

375
00:17:33,375 --> 00:17:36,260
그래서 지금은 아직 공간이 부족입니다,
그래서 같은 문제 이전.

376
00:17:36,260 --> 00:17:39,140
하지만 당신은 어떻게 지금 볼 수 있습니다
코드에서, 당신 아마

377
00:17:39,140 --> 00:17:41,910
더 조금 작성해야
복잡성은 그렇게 할 수 있습니다.

378
00:17:41,910 --> 00:17:44,510
그리고 사실, 어떤 연산자
C 아마 수 있습니다

379
00:17:44,510 --> 00:17:48,110
당신은 마술이 원형합니까?

380
00:17:48,110 --> 00:17:50,160
네 모듈로 연산자
퍼센트 기호.

381
00:17:50,160 --> 00:17:53,160
그래서 큐에 대한 종류의 멋진 무엇을,
우리는 드로잉 배열을 유지하더라도

382
00:17:53,160 --> 00:17:56,520
이와 같은 직선으로, 당신의 경우
종류의 커브 등이 생각

383
00:17:56,520 --> 00:18:00,341
주위에 원으로, 그럼 그냥
직관적으로는 가지 정신적으로 작동

384
00:18:00,341 --> 00:18:01,590
좀 더 명확하게 조금 생각합니다.

385
00:18:01,590 --> 00:18:05,190
당신은 여전히​​ 구현해야 할 것이다
코드에서 그 정신 모델.

386
00:18:05,190 --> 00:18:07,550
그래서없는 어려운,
궁극적으로, 구현

387
00:18:07,550 --> 00:18:12,430
하지만 우리는 여전히 오히려 size--을 잃게
우리는이 작업을 수행하지 않는 기능, 크기를 조정합니다.

388
00:18:12,430 --> 00:18:15,310
>> 우리는 배열을 제거해야 우리
하나의 포인터로 교체,

389
00:18:15,310 --> 00:18:20,010
다음 어딘가에 내 코드에 내가있어
실제로 생성하는 기능을 무엇 전화

390
00:18:20,010 --> 00:18:23,720
배열이라는 숫자?

391
00:18:23,720 --> 00:18:26,190
malloc에​​, 또는 이와 유사한
기능, 정확하게.

392
00:18:26,190 --> 00:18:30,481
스택 또는 큐에 대한 질문.

393
00:18:30,481 --> 00:18:30,980
그래?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
좋은 질문.

396
00:18:34,240 --> 00:18:35,830
무엇을 모듈로 여기에 사용합니다.

397
00:18:35,830 --> 00:18:38,520
그래서 일반적으로, 사용시
모드는, 당신은 그것을 할 것

398
00:18:38,520 --> 00:18:40,620
의 크기
전체 데이터 구조.

399
00:18:40,620 --> 00:18:44,120
그래서 뭔가 5 용량, 경우 같은
이 상수의, 아마 참여하고있다.

400
00:18:44,120 --> 00:18:47,100
그러나 단지 모듈로 다섯을하고
아마도 불충분

401
00:18:47,100 --> 00:18:51,380
우리가 알 필요가 있기 때문에 우리가 할
여기 또는 여기 또는 여기에 랩 어라운드.

402
00:18:51,380 --> 00:18:54,160
그래서 당신은 아마도있어
포함 할 것

403
00:18:54,160 --> 00:18:57,220
물건의 크기,
뿐만 아니라 전면 변수입니다.

404
00:18:57,220 --> 00:19:00,140
그래서 그냥이 상대적으로있어
간단한 산술 식,

405
00:19:00,140 --> 00:19:02,000
그러나 모듈은 핵심 요소가 될 것입니다.

406
00:19:02,000 --> 00:19:03,330
>> 그래서 단편 영화가됩니다.

407
00:19:03,330 --> 00:19:05,780
애니메이션 그 일부
다른 대학에서 사람

408
00:19:05,780 --> 00:19:08,060
우리가했습니다 것을 함께 넣어
이 토론에 적합.

409
00:19:08,060 --> 00:19:12,630
그것은 잭 학습 포함
큐와 통계에 대한 사실.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> 영화 : 옛적에 한 번,
잭이라는 사람이 있었다.

412
00:19:21,890 --> 00:19:25,330
이 친구 만들기에 왔을 때,
잭은 숙련 된 기술을 가지고 있지 않았다.

413
00:19:25,330 --> 00:19:28,220
그래서 잭은 얘기했다
가장 인기있는 남자 그는 알고 있었다.

414
00:19:28,220 --> 00:19:30,920
그는 루에 가서 어떻게해야합니까 물어?

415
00:19:30,920 --> 00:19:33,400
루는 그의 친구 것을보고
정말 고민했다.

416
00:19:33,400 --> 00:19:36,050
글쎄, 그는 단지, 시작
당신이 옷을 입고있는 방법을 찾습니다.

417
00:19:36,050 --> 00:19:38,680
당신은 어떤 옷이 없으십니까
다른 모습?

418
00:19:38,680 --> 00:19:39,660
네, 잭 말했다.

419
00:19:39,660 --> 00:19:40,840
나는 확실하지.

420
00:19:40,840 --> 00:19:43,320
우리 집에 와서
나는 당신에게 보여줄 것이다.

421
00:19:43,320 --> 00:19:44,550
그래서 그들은 잭에 떨어져 갔다.

422
00:19:44,550 --> 00:19:47,520
그리고 잭 루​​에게 상자를 보여 주었다
여기서 그는, 그의 셔츠를 유지

423
00:19:47,520 --> 00:19:49,260
자신의 바지와 양말.

424
00:19:49,260 --> 00:19:52,290
루는 내가 당신이 참조 말했다
더미에서 모든 옷.

425
00:19:52,290 --> 00:19:54,870
왜 일부를 착용하지 않는다
잠시 한번 다른 사람?

426
00:19:54,870 --> 00:19:58,020
>> 잭이 말했다 잘 때
, 옷과 양말을 제거

427
00:19:58,020 --> 00:20:00,780
나는 그들을 씻어 넣어
그들을 멀리 상자에.

428
00:20:00,780 --> 00:20:03,210
그런 다음 온다
아침, 최대 나는 홉.

429
00:20:03,210 --> 00:20:06,380
나는 상자에 가서 얻을
상단 떨어져 내 옷.

430
00:20:06,380 --> 00:20:09,070
루 빨리 실현
잭의 문제.

431
00:20:09,070 --> 00:20:12,080
그는, 옷, CD를 보관
스택 책.

432
00:20:12,080 --> 00:20:14,420
그는 위해 도착했을 때
뭔가를 읽거나 착용,

433
00:20:14,420 --> 00:20:17,100
그는 최고 책이나 속옷을 선택 것입니다.

434
00:20:17,100 --> 00:20:19,500
그리고 그는이 완료되었을 때, 그는
바로 다시 넣어 것입니다.

435
00:20:19,500 --> 00:20:21,970
다시는 스택의 상단에, 갈 것입니다.

436
00:20:21,970 --> 00:20:24,460
나는 해결책을 알고있다,
승리의 큰 소리로 말했다.

437
00:20:24,460 --> 00:20:27,090
당신은 배울 필요
큐를 사용하기 시작.

438
00:20:27,090 --> 00:20:29,870
루 잭의 옷을 가져다가
옷장에서 그들을 걸려.

439
00:20:29,870 --> 00:20:32,710
그리고 그는 비워했을 때
상자, ​​그는 단지 그것을 던졌다.

440
00:20:32,710 --> 00:20:36,500
>> 그리고 그는 잭의 말에, 지금은 말했다
하루, 왼쪽에 옷을 넣어

441
00:20:36,500 --> 00:20:37,990
당신이 그들을 멀리 둘 때.

442
00:20:37,990 --> 00:20:41,300
그럼 내일 아침에 때를
당신의 옷을 입고, 햇빛을 볼 수

443
00:20:41,300 --> 00:20:43,440
라인의 끝에서 오른쪽에.

444
00:20:43,440 --> 00:20:44,880
당신은 표시되지 않는 이유는 무엇입니까? 루는 말했다.

445
00:20:44,880 --> 00:20:46,370
너무 좋은 것입니다.

446
00:20:46,370 --> 00:20:49,770
당신은 한 번에 모든 것을 착용합니다
전에 두 번 뭔가를 착용하십시오.

447
00:20:49,770 --> 00:20:52,670
그리고 큐의 모든과
그의 옷장 선반에,

448
00:20:52,670 --> 00:20:55,160
잭 느끼기 시작
자신의 확신.

449
00:20:55,160 --> 00:20:59,720
루에 대한 모든 감사와
그의 멋진 큐.

450
00:20:59,720 --> 00:21:01,220
스피커 1 : 좋아, 그것은 사랑스러운입니다.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
그래서 정말 가고 무슨
지금은 후드 아래에?

453
00:21:10,080 --> 00:21:12,370
우리가 포인터를 가지고,
우리의 malloc을 가지고,

454
00:21:12,370 --> 00:21:15,680
우리가 만들 수있는 능력을 가지고 있다는
자신의 메모리의 덩어리

455
00:21:15,680 --> 00:21:16,344
동적.

456
00:21:16,344 --> 00:21:18,510
그래서이 사진 우리는
그냥 다른 하루 엿볼.

457
00:21:18,510 --> 00:21:21,180
우리는 정말 연연하지 않았다
거기에,하지만이 사진

458
00:21:21,180 --> 00:21:24,180
아래에있다가 계속되고
지금 주 후드.

459
00:21:24,180 --> 00:21:27,050
그리고 이것은 단지, 대표
우리가 그린 한 사각형,

460
00:21:27,050 --> 00:21:28,180
컴퓨터의 메모리.

461
00:21:28,180 --> 00:21:31,850
그리고 어쩌면 당신의 컴퓨터 또는 CS50
ID는, 메모리 또는 RAM의 기가 바이트를 가지고

462
00:21:31,850 --> 00:21:33,050
두 기가 바이트 네.

463
00:21:33,050 --> 00:21:34,450
정말 중요하지 않습니다.

464
00:21:34,450 --> 00:21:37,240
운영 체제
Windows 또는 Mac OS 또는 Linux,

465
00:21:37,240 --> 00:21:41,120
기본적으로 프로그램을 할 수 있습니다
이 액세스 할 수 있는지 생각하는

466
00:21:41,120 --> 00:21:42,982
전체에
컴퓨터의 메모리,

467
00:21:42,982 --> 00:21:45,440
심지어 당신이 실행 될 수 있지만
한 번에 여러 프로그램.

468
00:21:45,440 --> 00:21:46,990
그래서 현실에서, 그건 정말 작동하지 않습니다.

469
00:21:46,990 --> 00:21:49,448
그러나 그것은 환상 종류의
모든 프로그램에 주어진.

470
00:21:49,448 --> 00:21:53,110
그래서 만약 당신이이 RAM의 두 기가 있었다
컴퓨터가 생각할 수있는 방법이다.

471
00:21:53,110 --> 00:21:57,110
>> 지금 우연히, 이들 중 하나
것들, 이들의 메모리 세그먼트들 중 하나,

472
00:21:57,110 --> 00:21:58,350
스택이라고합니다.

473
00:21:58,350 --> 00:22:01,680
그리고 실제로 모든 시간
지금까지 코드를 작성에서

474
00:22:01,680 --> 00:22:05,900
당신이라는 것을
인스턴스 주에 대한 기능,.

475
00:22:05,900 --> 00:22:08,410
언제든지 내가했는지 기억
그린 컴퓨터 메모리,

476
00:22:08,410 --> 00:22:10,640
난 항상 종류의 그릴
여기에 사각형의 절반

477
00:22:10,640 --> 00:22:12,520
얘기 귀찮게하지 않습니다
위의 무엇에 대해.

478
00:22:12,520 --> 00:22:15,980
주를 호출 할 때, 내가 주장 때문에
당신은 메모리의 은색를 얻을

479
00:22:15,980 --> 00:22:16,970
즉, 여기에 내려갑니다.

480
00:22:16,970 --> 00:22:20,650
주요 만약 함수 호출
스왑처럼 잘 스왑 간다.

481
00:22:20,650 --> 00:22:23,720
그리고 그건, 밝혀
어디가 끝입니다.

482
00:22:23,720 --> 00:22:26,277
스택라는 뭔가
컴퓨터의 메모리의 내부.

483
00:22:26,277 --> 00:22:28,360
지금의 일 단부에,
이것은 단지 주소입니다.

484
00:22:28,360 --> 00:22:30,680
그것은 바이트 제로처럼
바이트 한 바이트 20 억.

485
00:22:30,680 --> 00:22:33,130
하지만 당신은 그것에 대해 생각하는 경우
이 직사각형의 객체로서,

486
00:22:33,130 --> 00:22:35,130
모든 우리는 모든 일을하고
시간 우리는 함수가 호출

487
00:22:35,130 --> 00:22:37,180
메모리의 새 슬라이스를 레이어링.

488
00:22:37,180 --> 00:22:41,700
우리는 슬라이스 해당 기능을 제공하고 있습니다
자신의 메모리와 함께 작동합니다.

489
00:22:41,700 --> 00:22:44,490
>> 그리고이 중요하다는 것을 지금 기억합니다.

490
00:22:44,490 --> 00:22:46,400
우리가 가지고있는 경우 때문에
스왑과 같은

491
00:22:46,400 --> 00:22:51,610
A와 B와 같은 두 개의 지역 변수
우리는 하나, 둘에서 그 값을 변경

492
00:22:51,610 --> 00:22:55,130
둘, 하나, 리콜
스왑 반환 때,

493
00:22:55,130 --> 00:22:58,330
그것은이 슬라이스 것처럼있어
메모리 다만 사라 졌어요.

494
00:22:58,330 --> 00:23:00,080
사실상, 그것은 여전히
이 포렌식.

495
00:23:00,080 --> 00:23:01,940
그리고 무언가가 실제로 아직 거기입니다.

496
00:23:01,940 --> 00:23:05,410
그러나 개념적으로, 그것은으로의
하지만 완전히 사라 졌어요.

497
00:23:05,410 --> 00:23:10,910
그리고 주요 작품의 어떤을 알 수 없습니다
즉, 그 스왑 기능에 이루어졌다

498
00:23:10,910 --> 00:23:14,890
그것은 실제로 그 전달 경우 제외
포인터 또는 참조를 기준으로 인수.

499
00:23:14,890 --> 00:23:17,790
이제, 근본적인 해결책
스왑과 그 문제

500
00:23:17,790 --> 00:23:19,970
주소로 물건을 전달합니다.

501
00:23:19,970 --> 00:23:23,250
하지만 너무 무엇이다, 밝혀
그 부분 이상 계속되고

502
00:23:23,250 --> 00:23:26,330
구형의 모든 시간이다
아직 더 많은 메모리 업이있다.

503
00:23:26,330 --> 00:23:28,790
그리고 때 동적
메모리를 할당,

504
00:23:28,790 --> 00:23:32,020
그것은하여 GetString, 내부 여부하는
우리는 CS50에 당신을 위해 해왔습니다

505
00:23:32,020 --> 00:23:34,710
라이브러리 또는 너희들 경우
malloc에​​ 전화해서 물어

506
00:23:34,710 --> 00:23:37,950
덩어리의 운영 체제
메모리, 그것은 스택에서 오지 않는다.

507
00:23:37,950 --> 00:23:40,960
또 다른 곳에서 유래
컴퓨터의 메모리에

508
00:23:40,960 --> 00:23:42,220
그는 힙이라고.

509
00:23:42,220 --> 00:23:43,430
그리고 그 어떤 다른 아니다.

510
00:23:43,430 --> 00:23:44,285
이 같은 RAM입니다.

511
00:23:44,285 --> 00:23:45,160
동일한 메모리이다.

512
00:23:45,160 --> 00:23:49,080
그것은까지 그냥 RAM의
이 대신에 여기까지.

513
00:23:49,080 --> 00:23:50,750
>> 그래서 그게 무슨 뜻 이죠?

514
00:23:50,750 --> 00:23:53,650
글쎄, 당신의 컴퓨터가있는 경우
메모리 한정된 양

515
00:23:53,650 --> 00:23:57,450
스택은 그렇게 성장하고있다
말을하고, 힙, 따라하기

516
00:23:57,450 --> 00:23:59,349
이 화살표로, 아래로 성장하고있다.

517
00:23:59,349 --> 00:24:01,140
즉, 모든
시간 당신이 malloc을 호출,

518
00:24:01,140 --> 00:24:03,430
당신은 조각을 주어지고있어
메모리의 위,

519
00:24:03,430 --> 00:24:06,630
조금 후, 낮은 어쩌면 조금
낮은, 당신이 malloc을 호출 할 때마다,

520
00:24:06,630 --> 00:24:10,100
힙, 그것은 사용이다,
종류의 성장,

521
00:24:10,100 --> 00:24:11,950
무엇에 점점 더 가까이 성장?

522
00:24:11,950 --> 00:24:13,382
스택입니다.

523
00:24:13,382 --> 00:24:14,840
그래서 이것은 좋은 생각처럼 보인다?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
정말 확실하지 않다 어디 말은,
당신은 다른 무엇을 당신이하는 경우에만 할 수있다

526
00:24:22,140 --> 00:24:23,910
메모리의 유한 한 양이있다.

527
00:24:23,910 --> 00:24:25,200
그러나 이것은 확실히 나쁘다.

528
00:24:25,200 --> 00:24:27,920
그 두 개의 화살표가 있습니다
서로에 대한 과정을 충돌.

529
00:24:27,920 --> 00:24:31,930
>> 그리고 그 나쁜 사람, 사람들 밝혀
프로그래밍 특히 좋다

530
00:24:31,930 --> 00:24:36,140
와 컴퓨터에 해킹을 시도,
이 현실을 악용 할 수 있습니다.

531
00:24:36,140 --> 00:24:38,290
사실, 이제 생각 해보자
작은 조각.

532
00:24:38,290 --> 00:24:41,350
그래서 당신이 읽을 수있는 예입니다
대한 위키 백과에 대한 상세.

533
00:24:41,350 --> 00:24:43,100
우리는 당신을 가리키는 것
기사의 경우 호기심.

534
00:24:43,100 --> 00:24:45,650
그러나 공격은 일반적으로있다
버퍼 오버 플로우로 알려진 그

535
00:24:45,650 --> 00:24:49,570
인간만큼 오랫동안 존재했다
조작 할 수 있었다

536
00:24:49,570 --> 00:24:53,120
특히 C에서 컴퓨터의 메모리,
그래서이 매우 임의적 프로그램은,

537
00:24:53,120 --> 00:24:55,130
하지만 이제 바닥부터 읽어 보자.

538
00:24:55,130 --> 00:24:57,650
ARGC의 문자 스타 ARGV에 주.

539
00:24:57,650 --> 00:24:59,830
그래서 걸리는 프로그램입니다
명령 줄 인수.

540
00:24:59,830 --> 00:25:03,620
그리고 모든 주요 분명히 전화는 않습니다
기능은 단순화를 위해 F를 호출합니다.

541
00:25:03,620 --> 00:25:04,610
그리고 그것은 무엇에 통과?

542
00:25:04,610 --> 00:25:05,490
하나의 ARGV.

543
00:25:05,490 --> 00:25:09,320
그래서 F로 통과 어떤
단어는 사용자가 입력 한 것입니다

544
00:25:09,320 --> 00:25:11,500
후 프롬프트에서
프로그램의 이름에서 모든.

545
00:25:11,500 --> 00:25:15,730
그래서 많은 시저 또는 Vigenere, 같은있는
당신은 ARGV와 함께 일을 불러올 수 있습니다.

546
00:25:15,730 --> 00:25:16,680
>> 그래서 F는 무엇인가?

547
00:25:16,680 --> 00:25:19,760
F는 문자열에 소요
단독 인수로,

548
00:25:19,760 --> 00:25:22,100
일명 숯 스타, 같은
일, 문자열로.

549
00:25:22,100 --> 00:25:24,920
그리고 임의로라고
이 예에서 바.

550
00:25:24,920 --> 00:25:27,710
그리고 숯불 C (12),
그냥 쉽게 설명하자면,

551
00:25:27,710 --> 00:25:31,750
우리를 위해 일을 숯불 C 브라켓 (12)은 무엇인가?

552
00:25:31,750 --> 00:25:33,440
그것은 무엇을 할거야?

553
00:25:33,440 --> 00:25:36,490
구체적으로는, 메모리를 할당
12 문자 12 바이트.

554
00:25:36,490 --> 00:25:36,990
정확히.

555
00:25:36,990 --> 00:25:40,000
그리고 마지막 줄, 저어
사본, 당신은 아마 본 적이 없다.

556
00:25:40,000 --> 00:25:43,360
이 문자열의 복사본입니다
그 목적은 인생의 기능

557
00:25:43,360 --> 00:25:48,160
두 번째 인수를 복사하는 것입니다
첫 번째 인자로,

558
00:25:48,160 --> 00:25:51,190
하지만 최대
바이트의 특정 번호.

559
00:25:51,190 --> 00:25:53,860
그래서 세 번째 인수는 말한다
당신은 얼마나 많은 바이트를 복사해야합니까?

560
00:25:53,860 --> 00:25:56,720
막대의 길이,
무엇이든에 입력 한 사용자.

561
00:25:56,720 --> 00:25:59,320
및 내용
이며, 그 문자열을 바

562
00:25:59,320 --> 00:26:02,330
메모리에 복사 ℃에서 지적했다

563
00:26:02,330 --> 00:26:04,060
>> 그래서이 종류의 바보 같은 것, 그리고 그것입니다.

564
00:26:04,060 --> 00:26:06,300
그것은 인위적인 예입니다,
그러나 대표자

565
00:26:06,300 --> 00:26:10,100
공격 경로의 클래스,
프로그램을 공격 방법.

566
00:26:10,100 --> 00:26:15,050
모든 고급 사용자가있는 경우 좋은
11 문자의 단어 유형

567
00:26:15,050 --> 00:26:18,040
적은, 플러스 백 슬래시 제로 나.

568
00:26:18,040 --> 00:26:22,830
무엇보다도 사용자의 유형을 더 있다면
11, 12, 20 또는 50 자?

569
00:26:22,830 --> 00:26:25,090
할 일이 프로그램은 무엇입니까?

570
00:26:25,090 --> 00:26:29,360
잠재적 SEG 오류. 그것은거야
맹목적으로 최대 표시 줄에 모든 것을 복사

571
00:26:29,360 --> 00:26:31,750
자사의 길이에
문자 그대로 표시 줄에 모든 것을,

572
00:26:31,750 --> 00:26:36,307
주소로 C. 그러나 C에서 지적
단지 선제 12 바이트로 부여하고있다.

573
00:26:36,307 --> 00:26:37,640
그러나 추가 검사가 없습니다.

574
00:26:37,640 --> 00:26:38,700
조건없는 경우가있다.

575
00:26:38,700 --> 00:26:40,580
여기에 검사 오류가 없습니다.

576
00:26:40,580 --> 00:26:43,270
>> 그리고이 프로그램은 무엇인가
할 거 그냥 맹목적이다

577
00:26:43,270 --> 00:26:45,750
다른 한 가지를 복사합니다.

578
00:26:45,750 --> 00:26:47,880
그래서 우리는이를 그릴 경우
그림으로, 여기에

579
00:26:47,880 --> 00:26:49,860
메모리 공간의 단지 슬리버.

580
00:26:49,860 --> 00:26:53,470
그래서 우리는 바닥에 알
지역 변수 바있다.

581
00:26:53,470 --> 00:26:57,330
store-- 것 그 포인터 그래서
사용자들은 로컬 인수 오히려

582
00:26:57,330 --> 00:26:58,672
문자열 줄을 저장하는 것.

583
00:26:58,672 --> 00:27:00,380
그리고 바로 알
위에 스택,

584
00:27:00,380 --> 00:27:02,505
때문에 당신이 물어 때마다
스택에 메모리,

585
00:27:02,505 --> 00:27:04,310
그것은 조금 간다
그림으로 위,

586
00:27:04,310 --> 00:27:06,270
우리가 12 바이트를 가지고 통지.

587
00:27:06,270 --> 00:27:10,690
왼쪽 상단 하나는 C 브라켓 제로입니다
오른쪽 아래 하나는 C 브래킷 (11)이다.

588
00:27:10,690 --> 00:27:12,870
즉 얼마나 컴퓨터의
를 배치하는 것.

589
00:27:12,870 --> 00:27:18,300
그래서 그냥 직관적으로, 줄이 더있는 경우
를 포함하여 총 12 자보다

590
00:27:18,300 --> 00:27:25,790
인 백 슬래시 제로,
12 C 브라켓 (12)은 갈?

591
00:27:25,790 --> 00:27:28,440
또는 오히려 여기서 12입니다
문자 또는 13 문자,

592
00:27:28,440 --> 00:27:30,900
가는 백 문자
사진에서 생을 마감하는 방법?

593
00:27:30,900 --> 00:27:33,400
위 또는 아래에?

594
00:27:33,400 --> 00:27:36,300
>> 마우스 오른쪽 단추로, 비록 때문에
스택 자체가 상방으로 성장

595
00:27:36,300 --> 00:27:39,590
당신은에 물건을 넣어 일단
그것은, 그 설계 이유로

596
00:27:39,590 --> 00:27:41,294
위에서 아래로 메모리를 저장합니다.

597
00:27:41,294 --> 00:27:44,460
당신은 12 개 이상의 바이트를 가지고 있다면,
당신은 줄을 덮어 쓰기 시작하는 것입니다.

598
00:27:44,460 --> 00:27:47,280
이제 버그는,하지만 그건
정말 큰 문제.

599
00:27:47,280 --> 00:27:51,130
이 때문에 그러나 그것은 큰 문제이며,
메모리에 계속 더 많은 물건.

600
00:27:51,130 --> 00:27:53,074
그래서 여기에 우리가 어떻게 힘이다
명확하게하기 위해, 안녕하세요했습니다.

601
00:27:53,074 --> 00:27:54,490
나는 프롬프트에서 인사에 입력합니다.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O 백 슬래시 제로, 내 끝
그 12 바이트는, 우리는 매우 안전 해요.

603
00:27:59,330 --> 00:28:00,330
모두가 잘됩니다.

604
00:28:00,330 --> 00:28:03,020
하지만 뭔가를 입력하면
이상, 잠재적입니다

605
00:28:03,020 --> 00:28:05,860
바 공간으로 크리프 것.

606
00:28:05,860 --> 00:28:08,405
그러나 더 나쁜 아직, 그것은집니다
이 모든 시간 초과,

607
00:28:08,405 --> 00:28:11,530
우리는 얘기 적이없는 경우에도
그것은 스택은 다른 재료에 사용됩니다.

608
00:28:11,530 --> 00:28:13,560
그것은 단지 지역 변수 아니다.

609
00:28:13,560 --> 00:28:15,100
>> C는 매우 낮은 수준의 언어이다.

610
00:28:15,100 --> 00:28:17,810
그리고 그것은 일종의 비밀
또한 스택을 사용

611
00:28:17,810 --> 00:28:21,260
때 기억
기능은 무엇이라고

612
00:28:21,260 --> 00:28:26,040
어드레스는 이전의 함수이며
그래서 다시 그 기능에 이동할 수 있습니다.

613
00:28:26,040 --> 00:28:29,980
그래서 주요 통화 중 교체 할 때
일이 스택으로 푸시

614
00:28:29,980 --> 00:28:34,380
있습니다 단지, 지역 변수를 스왑하지
또는 인수, 또한 비밀리에 추진

615
00:28:34,380 --> 00:28:37,510
스택에 나타낸 바와 같이
여기에 빨간색 조각에 의해,

616
00:28:37,510 --> 00:28:40,520
메인의 주소는 물리적으로
컴퓨터의 메모리에,

617
00:28:40,520 --> 00:28:44,180
그래서 스왑이 완료, 컴퓨터
나는 주에 다시 갈 필요가 알고

618
00:28:44,180 --> 00:28:46,760
및 주요 기능을 실행 완료.

619
00:28:46,760 --> 00:28:51,960
그래서, 지금은 위험한 경우 때문에
안녕하세요보다 잘 이상에서 사용자 유형,

620
00:28:51,960 --> 00:28:57,030
사용자의 입력이되도록 쳤을
또는, 그 빨간 부분을 덮어

621
00:28:57,030 --> 00:28:59,820
만약 논리적 컴퓨터
그냥 맹목적으로 가정 할 것

622
00:28:59,820 --> 00:29:03,830
그 붉은 조각의 바이트는 것을
이 반환해야되는 주소,

623
00:29:03,830 --> 00:29:09,020
상대가 어떤 경우 충분히 스마트 또는
바이트의 순서를 넣어 충분히 운

624
00:29:09,020 --> 00:29:13,450
이 주소처럼 보이는,
하지만 코드의 주소이다

625
00:29:13,450 --> 00:29:18,730
그 또는 그녀가 컴퓨터를 원한다고
대신에 메인으로 실행하는 방법?

626
00:29:18,730 --> 00:29:21,670
>> 즉, 어떤 경우를
사용자는 프롬프트에 입력됩니다

627
00:29:21,670 --> 00:29:23,850
다만 일이 아니다
안녕하세요 무해한 같은

628
00:29:23,850 --> 00:29:28,210
하지만 상당의 코드는 실제로이다
이 모든 사용자의 파일을 삭제하려면?

629
00:29:28,210 --> 00:29:30,060
아니면 나에게 자신의 암호를 이메일을 보내?

630
00:29:30,060 --> 00:29:31,940
또는 로깅을 시작 그들의
키, 오른쪽?

631
00:29:31,940 --> 00:29:34,920
방법이있다,,의 오늘 규정하자
그들은 안녕하세요 단지를 입력 할 수 있음

632
00:29:34,920 --> 00:29:36,711
세계 또는 이름,
그들은 본질적으로 수

633
00:29:36,711 --> 00:29:39,570
코드, 제로에 전달하고
사람, 그 컴퓨터

634
00:29:39,570 --> 00:29:43,450
코드와 주소를 모두 실수.

635
00:29:43,450 --> 00:29:48,950
이기는하지만 그래서 다소 추상적으로, 경우
충분히 적대적 코드에서 사용자 유형

636
00:29:48,950 --> 00:29:52,330
우리가 여기로 일반화거야
A. 공격 또는 적이다.

637
00:29:52,330 --> 00:29:53,140
그러니 그냥 나쁜 물건.

638
00:29:53,140 --> 00:29:55,306
우리는 걱정하지 않는다
숫자 또는 제로 또는 사람

639
00:29:55,306 --> 00:29:59,470
오늘, 당신은 결국 있음
그 빨간 부분을 덮어 쓰기,

640
00:29:59,470 --> 00:30:01,580
바이트의 순서를 알 수 있습니다.

641
00:30:01,580 --> 00:30:05,020
O 835 C 제로 여덟 제로.

642
00:30:05,020 --> 00:30:08,960
그리고 지금 여기에 위키 백과의 문서로
당신이 지금 실제로 시작하는 경우, 제안했다

643
00:30:08,960 --> 00:30:12,460
컴퓨터의에서 바이트를 라벨
메모리는 Wikipedia 기사는 무엇인가

644
00:30:12,460 --> 00:30:19,060
제안하는이며, 그 어떤 주소의 경우
그 왼쪽 상단 바이트의 80 ℃ 0 3508입니다.

645
00:30:19,060 --> 00:30:22,200
>> 즉, 나쁜 사람이면
자신의 코드로 똑똑

646
00:30:22,200 --> 00:30:26,650
실제로 여기에 숫자를 넣어 그
코드 어드레스에 대응

647
00:30:26,650 --> 00:30:29,180
그 또는 그녀는 주입
컴퓨터에, 당신

648
00:30:29,180 --> 00:30:31,050
컴퓨터를 속일 수 있습니다
아무것도에.

649
00:30:31,050 --> 00:30:34,140
파일을 제거 이메일
일, 트래픽 스니핑,

650
00:30:34,140 --> 00:30:36,710
말 그대로 아무것도 될 수있다
컴퓨터에 주입.

651
00:30:36,710 --> 00:30:39,220
그리고 버퍼 오버 플로우
그것의 핵심 공격

652
00:30:39,220 --> 00:30:43,530
그냥 바보, 바보
배열의 최우선 그

653
00:30:43,530 --> 00:30:45,840
그 경계를 확인하지 않았다.

654
00:30:45,840 --> 00:30:48,850
그리고 이것은 매우 위험한 것입니다
동시에 슈퍼 강력한

655
00:30:48,850 --> 00:30:52,560
C에서 우리가 참으로이 없다는 것입니다
메모리 어디서나 액세스 할 수 있습니다.

656
00:30:52,560 --> 00:30:55,320
그것은 우리에게 달려, 프로그래머,
사람은 원래의 코드를 작성

657
00:30:55,320 --> 00:30:59,330
어떤의 이놈의 길이를 확인하는
우리가 조작하고 배열.

658
00:30:59,330 --> 00:31:00,750
그래서 명확하게하기 위해, 수정은 무엇인가?

659
00:31:00,750 --> 00:31:03,190
우리는이 롤백 경우
코드, 내가하지 말아야 단지

660
00:31:03,190 --> 00:31:08,000
막대의 길이를 변경, 무엇
다른 내가 확인해야합니까?

661
00:31:08,000 --> 00:31:10,620
다른 내가에 일을해야
전적 공격을 방지?

662
00:31:10,620 --> 00:31:14,110
난 그냥 맹목적으로 말하고 싶지 않습니다
당신은 많은 바이트를 복사해야

663
00:31:14,110 --> 00:31:16,140
로 바의 길이입니다.

664
00:31:16,140 --> 00:31:18,910
나는로 복사하고 싶은 말
많은 바이트 줄에

665
00:31:18,910 --> 00:31:24,090
할당 된 최대
메모리 또는 최대로 (12).

666
00:31:24,090 --> 00:31:27,450
그래서 조건의 경우 어떤 종류의 필요
그 줄의 길이를 확인하지 않습니다,

667
00:31:27,450 --> 00:31:32,800
그러나 12, 우리 단지 하드 코드를 넘으면
최대 가능한 거리로 12.

668
00:31:32,800 --> 00:31:35,910
그렇지 않으면 소위 버퍼
오버 플로우 공격이 발생할 수 있습니다.

669
00:31:35,910 --> 00:31:38,451
그 슬라이드의 맨 아래에서,
당신은 자세한 내용을 궁금하다면

670
00:31:38,451 --> 00:31:41,200
실제 원본 기사입니다
당신을 살펴보고하려는 경우.

671
00:31:41,200 --> 00:31:44,550
>> 하지만 지금은 가격 중
비 효율성이 여기에 있었다 지불했다.

672
00:31:44,550 --> 00:31:46,680
그래서 빠른이었다
에서 낮은 수준의 모양 무엇

673
00:31:46,680 --> 00:31:49,709
문제는 우리가 지금이 발생할 수 있습니다
컴퓨터의 메모리에 액세스 할 수 있습니다.

674
00:31:49,709 --> 00:31:51,750
그러나 또 다른 문제 우리
이미 월요일에 발견

675
00:31:51,750 --> 00:31:53,800
바로 비 효율성이었다
연결리스트의.

676
00:31:53,800 --> 00:31:56,019
우리는 다시 선형 시간입니다.

677
00:31:56,019 --> 00:31:57,560
우리는 더 이상 연속 배열이 없습니다.

678
00:31:57,560 --> 00:31:58,980
우리는 랜덤 액세스 할 수 없습니다.

679
00:31:58,980 --> 00:32:00,710
우리는 대괄호 표기법을 사용할 수 없습니다.

680
00:32:00,710 --> 00:32:04,590
우리는 문자 그대로 while 루프를 사용해야합니다
처럼 나는 잠시 전에 썼다.

681
00:32:04,590 --> 00:32:09,740
그러나 월요일에, 우리는 우리가 할 수있는 주장
효율성의 영역으로 다시 크리프

682
00:32:09,740 --> 00:32:13,040
뭔가를 달성
로그 어쩌면, 또는 가장 아직,

683
00:32:13,040 --> 00:32:16,120
어쩌면 심지어 뭔가
일정 시간 소위.

684
00:32:16,120 --> 00:32:19,840
그래서 우리는 이러한 새로운를 사용하는 것이 어떻게 할 수
도구,이 주소,이 포인터,

685
00:32:19,840 --> 00:32:22,210
우리 자신의 일을 스레딩?

686
00:32:22,210 --> 00:32:23,960
글쎄, 있다고 가정
여기에, 이러한 무리입니다

687
00:32:23,960 --> 00:32:27,170
우리는에 저장할 수의
효율적으로 데이터 구조 및 검색.

688
00:32:27,170 --> 00:32:30,960
우리는 절대적으로 일주일에 되감기 할 수 있습니다
두 사람은, 배열에이 던져

689
00:32:30,960 --> 00:32:33,150
이진 검색을 사용하여 검색.

690
00:32:33,150 --> 00:32:34,040
분할하고 정복.

691
00:32:34,040 --> 00:32:37,720
그리고 사실 당신이 쓴
PSET3에서 이진 검색,

692
00:32:37,720 --> 00:32:40,100
위치를 찾기 프로그램을 구현했습니다.

693
00:32:40,100 --> 00:32:40,890
하지만 당신은 무엇을하는 것은 알고있다.

694
00:32:40,890 --> 00:32:45,060
더 많은 종류가있다
이렇게 영리한 방법.

695
00:32:45,060 --> 00:32:47,390
그것은 조금 더있어
정교하고 그것을 아마

696
00:32:47,390 --> 00:32:50,830
우리는 왜 바이너리 볼 수 있습니다
검색은 훨씬 더 빨리 그렇게입니다.

697
00:32:50,830 --> 00:32:52,980
먼저, 소개하자
나무의 개념.

698
00:32:52,980 --> 00:32:54,730
어느도에 불구하고
현실 나무 가지

699
00:32:54,730 --> 00:32:57,730
컴퓨터의 세계에서,이 같은 성장
그들이 종류의 하향 성장 과학

700
00:32:57,730 --> 00:33:00,830
당신이 가족 나무처럼
당신의 조부모 또는 증조부모

701
00:33:00,830 --> 00:33:04,580
또는 이것 저것 상단 족장에서와
가족의 족장, 한

702
00:33:04,580 --> 00:33:07,930
루트 노드 아래 소위
그 아이들이있는이다,

703
00:33:07,930 --> 00:33:11,442
그 이하의 어린이, 또는
그 자손 더 일반적.

704
00:33:11,442 --> 00:33:13,400
그리고 사람이 걸려
가족의 바닥

705
00:33:13,400 --> 00:33:16,070
나무,되고 게다가
가족의 막내,

706
00:33:16,070 --> 00:33:19,520
또한 단지 일반적으로 할 수있다
나무의 잎했다.

707
00:33:19,520 --> 00:33:21,800
>> 그래서 그냥 무리입니다
단어와 정의

708
00:33:21,800 --> 00:33:25,790
뭔가 컴퓨터에있는 나무라고
과학, 가족 나무처럼 많이.

709
00:33:25,790 --> 00:33:28,770
그러나 애호가 화신을 거기에
나무, 하나의

710
00:33:28,770 --> 00:33:30,780
이진 검색 트리라고합니다.

711
00:33:30,780 --> 00:33:34,380
그리고 당신은 할 수 있습니다 애타게 가지
이 일을 수행 떨어져 무엇.

712
00:33:34,380 --> 00:33:37,180
글쎄, 그것은 어떤 의미에서 진입니까?

713
00:33:37,180 --> 00:33:41,455
어디 이진 여기에서 오는가?

714
00:33:41,455 --> 00:33:41,955
죄송합니다?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
너무 많은 중 하나 또는 아니에요.

717
00:33:47,210 --> 00:33:52,000
이것은 각 노드가 더 있는지를 더
이상의 두 아이, 우리는 여기에서 볼 수있다.

718
00:33:52,000 --> 00:33:54,990
일반적으로, tree--에서와
당신의 부모와 조부모

719
00:33:54,990 --> 00:33:57,640
많은 아이를 가질 수 있습니다 또는
손자가 실제로 원하는대로,

720
00:33:57,640 --> 00:34:00,820
그래서 예를 들어 거기에서 우리는 세 가지가
그 오른쪽 노드 오프 어린이,

721
00:34:00,820 --> 00:34:05,480
하지만 이진 트리에서 노드 갖는다
최대로 0, 1, 또는 두 아이.

722
00:34:05,480 --> 00:34:08,496
그리고는, 좋은 숙박 시설의
이 두 가지로 덮인 거라면 때문에,

723
00:34:08,496 --> 00:34:10,620
우리는 할 수있을거야
작은 로그 기반을 얻을 두

724
00:34:10,620 --> 00:34:11,975
작업은 여기에 궁극적으로 진행.

725
00:34:11,975 --> 00:34:13,350
그래서 우리는 로그 뭔가가있다.

726
00:34:13,350 --> 00:34:14,558
그러나 잠시 그​​에 대한 자세한.

727
00:34:14,558 --> 00:34:19,810
탐색 트리 수 있다는 의미
배치되도록 왼쪽 아이의

728
00:34:19,810 --> 00:34:22,429
루트 값보다 크다.

729
00:34:22,429 --> 00:34:26,010
그리고 오른쪽 아이는
루트보다 크다.

730
00:34:26,010 --> 00:34:29,290
즉, 당신이 중 하나를 사용할 수있는 경우
노드,이 그림의 원,

731
00:34:29,290 --> 00:34:31,840
그 왼쪽에 보이는
자녀와 오른쪽 아이,

732
00:34:31,840 --> 00:34:34,739
첫 번째는,보다 작아야합니다
두 번째는보다 커야합니다.

733
00:34:34,739 --> 00:34:36,159
그래서 정신은 (55)을 선택합니다.

734
00:34:36,159 --> 00:34:37,780
그것은 아이를 남아 (33)이다.

735
00:34:37,780 --> 00:34:38,620
그것은 이하이다.

736
00:34:38,620 --> 00:34:40,929
55, 오른쪽 아이는 77입니다.

737
00:34:40,929 --> 00:34:41,783
이는보다 큰이다.

738
00:34:41,783 --> 00:34:43,199
그리고 그 재귀 적 정의이다.

739
00:34:43,199 --> 00:34:46,480
우리는 그 하나 하나 확인할 수 있습니다
노드 및 보유하는 것과 동일한 패턴입니다.

740
00:34:46,480 --> 00:34:49,389
>> 그래서에서 좋은거야
이진 검색 트리이고,

741
00:34:49,389 --> 00:34:52,204
그 하나는, 우리는이를 구현할 수
구조체로, 그냥이를 좋아한다.

742
00:34:52,204 --> 00:34:54,620
그리고 우리는 던지고있어 비록
당신의 구조를 많이,

743
00:34:54,620 --> 00:34:56,560
그들은 다소있어
직관적 인 지금 희망.

744
00:34:56,560 --> 00:35:00,570
구문은, 아직 확실히 비밀입니다
그러나,이 노드에서의 내용

745
00:35:00,570 --> 00:35:02,786
context-- 우리는 계속
단어 노드를 사용하여,

746
00:35:02,786 --> 00:35:04,910
그것은 사각형의 여부
화면 또는 원에,

747
00:35:04,910 --> 00:35:08,970
그것은, 그냥 일반 컨테이너의
같은 나무의이 경우,

748
00:35:08,970 --> 00:35:11,780
우리는 우리가 정수를 필요로했다
각 노드에서

749
00:35:11,780 --> 00:35:15,460
그리고, 나는 두 개의 포인터를 가리키는 필요
왼쪽 자식, 오른쪽 아이에게,

750
00:35:15,460 --> 00:35:16,590
각각.

751
00:35:16,590 --> 00:35:20,730
그건 어떻게 우리가 수도
구조체에 그를 구현한다.

752
00:35:20,730 --> 00:35:22,315
그리고 내가 어떻게 코드를 구현할 수?

753
00:35:22,315 --> 00:35:26,730
음, 빠른 보자
이 작은 예를 살펴 보자.

754
00:35:26,730 --> 00:35:29,820
그것은 작동하지 않습니다,하지만 난했습니다
복사 및 그 구조를 붙여.

755
00:35:29,820 --> 00:35:33,510
그리고 만약 바이너리 내 기능
검색 트리, 검색이라고합니다

756
00:35:33,510 --> 00:35:36,980
이 두 인수를,
정수 N과 포인터

757
00:35:36,980 --> 00:35:41,400
트리 노드, 그래서 포인터
또는 트리의 루트에 대한 포인터,

758
00:35:41,400 --> 00:35:43,482
어떻게 N을 찾고 가야합니까?

759
00:35:43,482 --> 00:35:45,440
음, 첫 번째, 내가이기 때문에
포인터를 처리,

760
00:35:45,440 --> 00:35:46,750
나는 정신 검사를 할거야.

761
00:35:46,750 --> 00:35:54,279
트리 등호가 null 같다면, N은
이 나무의 여부를이 나무에?

762
00:35:54,279 --> 00:35:55,070
그것은 바로,이 될 수없는 이유는 무엇입니까?

763
00:35:55,070 --> 00:35:56,870
내가 널 과거입니다 경우,
거기에 아무것도 없다.

764
00:35:56,870 --> 00:35:59,230
나는 수도뿐만 아니라 단지
맹목적으로 false를 돌려 말한다.

765
00:35:59,230 --> 00:36:04,050
당신은 내게 아무것도주지 않으면, 내가 확실히 할 수 없습니다
숫자 N을 찾을 수 밖에 그래서 나는 수도

766
00:36:04,050 --> 00:36:04,750
지금 확인하세요?

767
00:36:04,750 --> 00:36:12,830
내가 아니라 다른 N 인 경우는 말할거야
트리 노드에서 무엇이든 이하

768
00:36:12,830 --> 00:36:16,300
나는 N 값을 넘겨 봤는데.

769
00:36:16,300 --> 00:36:20,270
즉, 숫자 I는 요한다면
N, 찾고, 노드보다 작

770
00:36:20,270 --> 00:36:21,340
내가 찾고 있어요 그.

771
00:36:21,340 --> 00:36:23,190
그리고 노드는 내가 찾고 있어요
트리라고에,

772
00:36:23,190 --> 00:36:26,370
그리고 앞의 예에서 리콜
포인터의 값에 얻을 수 있습니다,

773
00:36:26,370 --> 00:36:28,310
나는 화살표 표기법을 사용합니다.

774
00:36:28,310 --> 00:36:35,960
N은 나무 화살표보다 작다면
N, 나는 개념적으로 왼쪽으로 가고 싶어.

775
00:36:35,960 --> 00:36:38,590
나는 어떻게 왼쪽들을 검색 명시합니까?

776
00:36:38,590 --> 00:36:41,560
이 경우, 명확하게하려면
문제의 사진,

777
00:36:41,560 --> 00:36:44,612
나는 통과 한 최상위 그
그 아래로 가리키는 화살.

778
00:36:44,612 --> 00:36:45,570
그건 내 나무 포인터입니다.

779
00:36:45,570 --> 00:36:48,060
나는 트리의 루트를 가리키는거야.

780
00:36:48,060 --> 00:36:52,100
내가 들어 말을 찾고 있어요
임의 수 (44).

781
00:36:52,100 --> 00:36:55,300
보다 44 작거나
분명히 55보다 큰?

782
00:36:55,300 --> 00:36:56,360
그래서 미만이다.

783
00:36:56,360 --> 00:36:58,760
그리고이 경우 조건이 적용됩니다.

784
00:36:58,760 --> 00:37:03,981
그래서 개념적으로, 내가 무엇을 하시겠습니까?
나는 44을 찾고 있다면 다음 검색?

785
00:37:03,981 --> 00:37:04,480
그래?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> 정확히 내가 원하는
왼쪽 아이를 검색,

788
00:37:11,100 --> 00:37:12,789
또는이 사진의 왼쪽 서브 트리.

789
00:37:12,789 --> 00:37:14,830
그리고 사실, 저를 통해 할 수
아래로 여기 사진

790
00:37:14,830 --> 00:37:17,770
단지 잠시, 이후
나는이를 긁지 수 있습니다.

791
00:37:17,770 --> 00:37:21,150
나는 55에 여기에 시작하고, 경우
내가 알고있는 값 (44)

792
00:37:21,150 --> 00:37:23,180
이다 위해 내가 찾고 있어요
왼쪽, 그것은 종류의

793
00:37:23,180 --> 00:37:26,010
에서의 전화 번호부 등에 찢어
절반 또는 절반에 나무를 찢어.

794
00:37:26,010 --> 00:37:29,660
나는 더 이상 걱정 할 필요가 없습니다
나무의이 전체의 절반입니다.

795
00:37:29,660 --> 00:37:33,270
그럼에도 불구하고, 호기심의 관점에서
구조, 여기에 이​​상이 일

796
00:37:33,270 --> 00:37:36,682
33로 시작하는 자체, 그
이진 검색 트리입니다.

797
00:37:36,682 --> 00:37:39,890
때문에 나는 전에 단어가 재귀 말했다
실제로 이것은 데이터 구조는 그

798
00:37:39,890 --> 00:37:41,707
정의에 의해 재귀입니다.

799
00:37:41,707 --> 00:37:44,540
당신이있어 나무가있을 수 있습니다
큰,하지만 그 아이의 모든 하나

800
00:37:44,540 --> 00:37:46,870
작은 조금 트리를 나타냅니다.

801
00:37:46,870 --> 00:37:50,910
대신의 할아버지 인
또는 할머니, 지금은 엄마의

802
00:37:50,910 --> 00:37:54,300
or-- 나는 엄마하지 say-- 수 없습니다
또는 아빠, 그 이상이 될 것이다.

803
00:37:54,300 --> 00:37:59,000
이 대신에 두 아이
형제와 형제처럼 될 것입니다.

804
00:37:59,000 --> 00:38:01,120
가계도의 새로운 세대.

805
00:38:01,120 --> 00:38:02,900
그러나 구조적으로, 같은 생각입니다.

806
00:38:02,900 --> 00:38:06,790
그리고 내가 기능이 밝혀
있는 나는 이진 검색을 검색 할 수 있습니다

807
00:38:06,790 --> 00:38:07,290
트리.

808
00:38:07,290 --> 00:38:08,680
그것은 검색이라고합니다.

809
00:38:08,680 --> 00:38:17,870
나는 나무 화살표 왼쪽에 N 검색
N이 값보다 큰 경우에 다른

810
00:38:17,870 --> 00:38:18,870
것을 나는 현재에있어.

811
00:38:18,870 --> 00:38:20,800
조금 전에 이야기 (55).

812
00:38:20,800 --> 00:38:23,780
나는라는 기능을 가지고
검색이 난 그냥 수

813
00:38:23,780 --> 00:38:29,660
N이를 통과하고 반복적으로 검색
서브 트리 그냥 반환

814
00:38:29,660 --> 00:38:30,620
무엇이든 그 대답.

815
00:38:30,620 --> 00:38:33,530
그렇지 나는 여기에 몇 가지 최종 기본 케이스를 가지고있다.

816
00:38:33,530 --> 00:38:35,310
>> 마지막 경우는 무엇인가?

817
00:38:35,310 --> 00:38:36,570
나무 중 하나 nul​​l입니다.

818
00:38:36,570 --> 00:38:39,980
나도 찾고 있어요 값은
그것보다보다 작거나 큰

819
00:38:39,980 --> 00:38:42,610
또는 동일.

820
00:38:42,610 --> 00:38:44,750
그리고 나는 동일을 말할 수
동일하지만, 논리적이다

821
00:38:44,750 --> 00:38:46,500
여기 다른 말을하는 것과 같습니다.

822
00:38:46,500 --> 00:38:49,150
그래서 사실은 내가 뭔가를 찾을 방법이다.

823
00:38:49,150 --> 00:38:51,710
그래서 희망이있다
더욱 강력한 예

824
00:38:51,710 --> 00:38:54,900
바보 시그마 기능 이상
우리는 다시 몇 강의를했다

825
00:38:54,900 --> 00:38:58,360
어디 루프를 사용하는만큼 쉬웠다
하나에서 모든 숫자를 계산하는

826
00:38:58,360 --> 00:39:02,390
데이터 구조와 여기에 N.
그 자체가 재귀 적입니다

827
00:39:02,390 --> 00:39:07,050
우리는 지금, 정의 반복적으로 그려
자신을 표현하는 능력을 가지고

828
00:39:07,050 --> 00:39:09,780
코드 자체는 재귀입니다.

829
00:39:09,780 --> 00:39:12,580
그래서 여기에 동일한 코드입니다.

830
00:39:12,580 --> 00:39:14,400
>> 그래서 우리는 다른 어떤 문제를 해결할 수 있습니까?

831
00:39:14,400 --> 00:39:18,160
멀리 그래서 빠른 단계
단지 잠시 나무.

832
00:39:18,160 --> 00:39:20,130
여기에, 독일 국기를 말한다.

833
00:39:20,130 --> 00:39:22,020
그리고 분명히있다
이 플래그 패턴.

834
00:39:22,020 --> 00:39:23,811
그리고 많이있다
세계 플래그 그

835
00:39:23,811 --> 00:39:27,560
측면에서이만큼 간단합니다
자신의 색상과 패턴의.

836
00:39:27,560 --> 00:39:31,930
그러나 이것은 저장된다고 가정
.GIF 또는 JPEG 또는 비트 맵 또는 핑,

837
00:39:31,930 --> 00:39:34,240
어떤 그래픽 파일 포맷
있는 당신이 잘 알고

838
00:39:34,240 --> 00:39:36,460
우리가있어 그 중 일부
PSET4에서 함께 연주.

839
00:39:36,460 --> 00:39:41,550
이 저장하는 가치가하지 않는 것
검은 픽셀, 검은 픽셀, 검은 픽셀,

840
00:39:41,550 --> 00:39:44,790
점, 점, 점,의 모두
첫 번째 주사선 검은 픽셀,

841
00:39:44,790 --> 00:39:47,430
또는 행, 다음 왕창
같은, 다음 왕창

842
00:39:47,430 --> 00:39:49,530
다음 같은, 그리고
빨간색 픽셀의 전체 무리,

843
00:39:49,530 --> 00:39:53,020
적색 픽셀, 적색 픽셀, 다음 전체
노랑 픽셀의 무리, 오른쪽?

844
00:39:53,020 --> 00:39:55,050
>> 이러한 비 효율성은 여기에있다.

845
00:39:55,050 --> 00:39:59,040
어떻게 직관적으로 당신 것
독일 국기를 압축

846
00:39:59,040 --> 00:40:01,320
파일로 구현하는 경우?

847
00:40:01,320 --> 00:40:04,940
어떤 정보처럼 우리를 할 수 없습니다
위해 디스크에 저장 귀찮게

848
00:40:04,940 --> 00:40:08,040
등으로부터 우리의 파일 크기를 줄일 수 있습니다
킬로바이트, 뭔가 메가 바이트

849
00:40:08,040 --> 00:40:09,430
작은?

850
00:40:09,430 --> 00:40:13,130
상기 리던던시 놓여
여기에 명확하게하는 방법?

851
00:40:13,130 --> 00:40:13,880
당신은 무엇을 할 수 있습니까?

852
00:40:13,880 --> 00:40:14,380
그래?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
정확히.

855
00:40:21,970 --> 00:40:24,550
왜보다는 기억
모든 이놈 픽셀의 색상

856
00:40:24,550 --> 00:40:28,200
당신이 PSET4에서하고있는 등
비트 맵 파일 형식으로,

857
00:40:28,200 --> 00:40:32,060
왜 당신은 단지를 대변하지 않습니다
예를 들어 픽셀의 왼쪽 열,

858
00:40:32,060 --> 00:40:35,370
검은 픽셀의 무리, 무리
빨간색과 노란색의 무리,

859
00:40:35,370 --> 00:40:39,210
다음 그냥 어떻게 든를 인코딩
반복의 생각이 100 배

860
00:40:39,210 --> 00:40:41,020
또는이 1,000 번 반복?

861
00:40:41,020 --> 00:40:43,430
경우 100 또는 1000입니다
그냥 정수, 당신 때문에

862
00:40:43,430 --> 00:40:47,290
단지 하나의 번호로 멀리 얻을 수 있습니다
대신 수백 또는 수천의

863
00:40:47,290 --> 00:40:48,270
추가 픽셀.

864
00:40:48,270 --> 00:40:50,990
그리고 실제로, 그것은 어떻게 우리를이다
독일 국기를 압축 할 수있다.

865
00:40:50,990 --> 00:40:51,490
과

866
00:40:51,490 --> 00:40:53,470
프랑스 국기에 대한 지금 무엇?

867
00:40:53,470 --> 00:40:58,930
어떤 종류의 그리고 조금
정신 운동하는 플래그

868
00:40:58,930 --> 00:41:01,040
디스크에 더 압축 할 수 있습니까?

869
00:41:01,040 --> 00:41:05,720
독일 국기 또는 프랑스
플래그, 우리는 그 접근 방식을 경우?

870
00:41:05,720 --> 00:41:08,490
독일 국기, 거기 때문에
더 수평 중복.

871
00:41:08,490 --> 00:41:12,190
그리고 디자인으로, 많은 그래픽 파일
형식은 참으로 스캔 라인을 작동합니까

872
00:41:12,190 --> 00:41:12,830
수평.

873
00:41:12,830 --> 00:41:14,674
그들은 일할 수있는
수직, 단지 인류

874
00:41:14,674 --> 00:41:17,090
결정 년전 우리는거야
일반적으로 일 행의 생각

875
00:41:17,090 --> 00:41:18,880
열을 기준으로 행 대신 열을 기준으로.

876
00:41:18,880 --> 00:41:20,820
그래서 실제로 당신이 인 경우에
파일을 보시려면,

877
00:41:20,820 --> 00:41:24,670
독일 국기와 프랑스의 크기
플래그, 너무 오래 해상도 그대로

878
00:41:24,670 --> 00:41:27,530
같은, 동일한 폭
높이, 이것

879
00:41:27,530 --> 00:41:31,580
여기가 더 될 것입니다 당신 때문에
자신에게 세 번을 반복해야합니다.

880
00:41:31,580 --> 00:41:35,570
당신은 파란색, 반복을 지정해야
자신을, 흰색, 빨간색, 자신을 반복

881
00:41:35,570 --> 00:41:36,740
자신을 반복합니다.

882
00:41:36,740 --> 00:41:39,000
당신은 모든 갈 수 없어
오른쪽 방법.

883
00:41:39,000 --> 00:41:41,200
그리고 옆으로, 만들려면
압축을 취소

884
00:41:41,200 --> 00:41:43,910
이러한 경우, 어디에나
video--에서 4 개의 프레임 당신

885
00:41:43,910 --> 00:41:45,890
영화 리콜 있습니다
또는 비디오는 일반적으로

886
00:41:45,890 --> 00:41:47,286
초당 29 또는 30 프레임 등을들 수있다.

887
00:41:47,286 --> 00:41:50,410
그것은 작은 플립 북처럼 어디를
단지 이미지, 이미지, 이미지, 이미지 참조

888
00:41:50,410 --> 00:41:54,410
이미지는 슈퍼 빠른 그래서 그것은처럼 보인다
화면의 배우가 이동하고있다.

889
00:41:54,410 --> 00:41:57,130
다음은 꿀벌에이다
꽃의 무리의 상단.

890
00:41:57,130 --> 00:41:59,790
그리고 그것은 종류의 수 있습니다하지만
첫 눈에 보이지,

891
00:41:59,790 --> 00:42:04,020
이동 유일한
이 영화는 꿀벌입니다.

892
00:42:04,020 --> 00:42:06,880
>> 어떤 것은 저장에 대한 바보
비디오 압축 해제?

893
00:42:06,880 --> 00:42:11,420
이는 비디오를 저장하는 폐기물의 종류의
네 개의 거의 동일한 이미지로 그

894
00:42:11,420 --> 00:42:13,670
만하는 한 벌입니다으로 다르​​다.

895
00:42:13,670 --> 00:42:16,280
당신은 멀리 던질 수있는 가장
정보의

896
00:42:16,280 --> 00:42:20,190
만 기억, 예를 들면,
제 프레임과 최종 프레임,

897
00:42:20,190 --> 00:42:22,180
당신이했습니다 경우 키 프레임
지금, 말씀을 듣고

898
00:42:22,180 --> 00:42:24,337
단지에 저장
꿀벌은 중간.

899
00:42:24,337 --> 00:42:26,170
그리고 당신은 필요 없어
, 핑크 모두 저장할

900
00:42:26,170 --> 00:42:28,330
파랑 및 및
녹색 값뿐만 아니라.

901
00:42:28,330 --> 00:42:31,200
그래서 이것은 단지라고하는 것입니다
압축은 어디 에나있다.

902
00:42:31,200 --> 00:42:34,900
우리가 자주 사용하는 기술이다
요즘 부여이나 걸릴.

903
00:42:34,900 --> 00:42:38,750
>> 그러나 당신은 어떻게 텍스트를 압축합니까?

904
00:42:38,750 --> 00:42:40,450
당신은 어떻게 텍스트를 압축 가야합니까?

905
00:42:40,450 --> 00:42:45,410
음, 문자의 각
ASCII는 한 바이트, 또는 8 비트이다.

906
00:42:45,410 --> 00:42:47,360
그리고 그 종류의 바보, 맞아?

907
00:42:47,360 --> 00:42:51,160
당신은 아마를 입력하기 때문에
그리고 E와 I와 O 및 U 많은

908
00:42:51,160 --> 00:42:55,270
더 자주 W 또는 Q 또는 Z와 같은보다,
언어에 따라하는

909
00:42:55,270 --> 00:42:56,610
당신은 확실히 쓰고있어.

910
00:42:56,610 --> 00:42:59,600
그리고 왜 우리가 사용하는
모든 문자에 8 비트,

911
00:42:59,600 --> 00:43:02,040
적어도 포함
인기있는 문자, 오른쪽?

912
00:43:02,040 --> 00:43:05,300
왜에 대한 적은 비트를 사용하지
슈퍼 인기있는 편지,

913
00:43:05,300 --> 00:43:07,760
E와 같은 일들이 당신이 생각
첫 번째 행운의 휠에,

914
00:43:07,760 --> 00:43:10,450
그리고 더 많은 비트를 사용
덜 인기있는 편지?

915
00:43:10,450 --> 00:43:10,950
왜?

916
00:43:10,950 --> 00:43:13,130
우리가 갈거야 때문에
자주 사용할.

917
00:43:13,130 --> 00:43:15,838
>> 음, 거기가 밝혀
이 작업을 수행하려고 시도되었습니다.

918
00:43:15,838 --> 00:43:18,630
그리고 당신은 학년에서 기억 경우
학교 또는 고등학교, 모스 부호.

919
00:43:18,630 --> 00:43:20,400
모스 부호는 점이
대시는 할 수

920
00:43:20,400 --> 00:43:24,270
와이어로 함께 전송
소리 또는 어떤 종류의 신호.

921
00:43:24,270 --> 00:43:25,930
하지만 모스 부호는 슈퍼 깨끗합니다.

922
00:43:25,930 --> 00:43:29,010
이 글은 이진 시스템의 종류의
것을 당신은 점 또는 대시가 있습니다.

923
00:43:29,010 --> 00:43:30,977
하지만 당신은, 예를 들어, 두 개의 점을 볼 경우.

924
00:43:30,977 --> 00:43:33,810
아니면 운영자에 다시 생각하는 경우
누가, 삐, 삐, 삐 같이 간다

925
00:43:33,810 --> 00:43:36,760
음, 약간의 트리거 타격
즉, 신호를 송신하고,

926
00:43:36,760 --> 00:43:40,360
당신이 경우,받는 사람, 두를 수신
점은, 어떤 메시지가 수신 한?

927
00:43:40,360 --> 00:43:43,490
완전히 임의의.

928
00:43:43,490 --> 00:43:44,450
>> 내가?

929
00:43:44,450 --> 00:43:45,060
내가?

930
00:43:45,060 --> 00:43:47,500
또는 무엇 비슷해 또는 I?

931
00:43:47,500 --> 00:43:49,570
아마 두 전자의 권리인가?

932
00:43:49,570 --> 00:43:52,480
그래서이 문제가있다
모스와 decodability의

933
00:43:52,480 --> 00:43:54,890
코드, 이에 않는
당신에게 메시지를 보내는 사람

934
00:43:54,890 --> 00:43:59,510
실제로 그래서 당신의 정렬 할 수 있습니다 일시 정지
참조 또는 문자 사이의 간격을 듣고,

935
00:43:59,510 --> 00:44:02,990
그것은 단지에 충분한 아니다
0과 1의 스트림을 전송,

936
00:44:02,990 --> 00:44:05,610
또는 점과 대시,
모호함이 존재하기 때문이다.

937
00:44:05,610 --> 00:44:08,640
E는 하나의 점, 그래서 당신 경우
두 개의 점을 참조하거나 두 개의 점을 듣고,

938
00:44:08,640 --> 00:44:11,254
아마 두 개의 전자의 나 어쩌면 하나 I.의

939
00:44:11,254 --> 00:44:13,670
그래서 우리는 A의 시스템이 필요
보다 더 영리한.

940
00:44:13,670 --> 00:44:16,851
그래서 사람의 이름 허프만 년
전 바로이 함께했다.

941
00:44:16,851 --> 00:44:18,600
그래서 우리는 단지거야
빠른 눈을 촬영합니다

942
00:44:18,600 --> 00:44:20,114
방법에 나무이 밀접한 있습니다.

943
00:44:20,114 --> 00:44:22,530
이 몇 가지 있음을 가정
보내려는 바보 메시지,

944
00:44:22,530 --> 00:44:26,342
다만 A, B로 구성, C의 D의와 E의,
하지만 중복이 많이 여기에있다.

945
00:44:26,342 --> 00:44:27,550
그것은 영어로 의미가 아니에요.

946
00:44:27,550 --> 00:44:28,341
그것은 암호화 아니에요.

947
00:44:28,341 --> 00:44:30,540
그냥 바보 메시지이다
반복이 많은.

948
00:44:30,540 --> 00:44:34,010
당신은 실제로 아웃 카운트 그래서 만약 모든
의, B의, C의, D의 및 E 년대는 여기

949
00:44:34,010 --> 00:44:34,890
주파수.

950
00:44:34,890 --> 00:44:37,800
편지의 20 %는
의, 편지의 45 %

951
00:44:37,800 --> 00:44:39,660
전자의, 3 다른 주파수이다.

952
00:44:39,660 --> 00:44:41,960
우리는 수동으로이 카운트 업
그냥 수학을했다.

953
00:44:41,960 --> 00:44:44,579
>> 그래서 밝혀
허프만, 얼마 전에,

954
00:44:44,579 --> 00:44:46,620
당신이 알고있는, 실현
무엇을, 나는 건물을 시작하는 경우

955
00:44:46,620 --> 00:44:51,172
나무, 또는 나무의 숲, 만약에 당신,
다음과 같이, 나는 다음과 같은 작업을 수행 할 수 있습니다.

956
00:44:51,172 --> 00:44:53,880
나는 각 노드를 줄거야
내가 걱정하는 편지

957
00:44:53,880 --> 00:44:55,530
내가 저장거야
해당 노드의 내부

958
00:44:55,530 --> 00:44:58,610
부동 소수점과 같은 주파수
값은, 또는 당신은, 너무, N을 사용할 수 있습니다

959
00:44:58,610 --> 00:45:00,210
그러나 우리는 여기 float를 사용합니다.

960
00:45:00,210 --> 00:45:03,100
그리고 알고리즘이
그는 당신 즉 제안

961
00:45:03,100 --> 00:45:07,210
단일 노드의 숲을
나무, 그래서 슈퍼 짧은 나무,

962
00:45:07,210 --> 00:45:11,920
당신은 그들을 연결 시작
새 그룹, 새 부모가됩니다.

963
00:45:11,920 --> 00:45:16,150
그리고 당신은을 선택하여이 작업을 수행
한 번에 두 개의 작은 주파수.

964
00:45:16,150 --> 00:45:18,110
그래서 10 %와 10 %를했다.

965
00:45:18,110 --> 00:45:19,090
나는 새로운 노드를 만들 수 있습니다.

966
00:45:19,090 --> 00:45:20,910
그리고 새로운 노드에게 20 %를 호출합니다.

967
00:45:20,910 --> 00:45:22,750
>> 어떤 두 개의 노드 내가 다음 결합?

968
00:45:22,750 --> 00:45:23,810
그것은 조금 모호하다.

969
00:45:23,810 --> 00:45:26,643
그래서 일부 코너 케이스를있다
고려하지만, 꽤 물건을 유지하기 위해,

970
00:45:26,643 --> 00:45:29,300
나는 20 %를 선택하는거야 -
지금은 아이들을 무시합니다.

971
00:45:29,300 --> 00:45:33,640
내가 20 %를 선택하는거야와
15 %는 두 개의 새로운 가장자리를 그립니다.

972
00:45:33,640 --> 00:45:35,624
그리고 지금하는 두 개의 노드
나는 논리적으로 결합합니까?

973
00:45:35,624 --> 00:45:38,540
모든 아이들, 모든 무시
손자, 그냥 뿌리를 보면

974
00:45:38,540 --> 00:45:39,070
지금.

975
00:45:39,070 --> 00:45:42,220
어떤 두 개의 노드 나는 함께 묶어합니까?

976
00:45:42,220 --> 00:45:44,530
지점이 0.35.

977
00:45:44,530 --> 00:45:45,890
그래서 내가 두 개의 새로운 가장자리를 그릴 수 있습니다.

978
00:45:45,890 --> 00:45:47,570
그리고 나는 단 하나의 왼쪽을 가지고있다.

979
00:45:47,570 --> 00:45:48,650
그래서 여기에 나무입니다.

980
00:45:48,650 --> 00:45:51,160
그리고 의도적으로 그려져있어
종류의 예쁜보고,

981
00:45:51,160 --> 00:45:55,870
그러나 가장자리가 알
또한 0과 1로 표시되었습니다.

982
00:45:55,870 --> 00:45:59,510
그래서 좌변 모두 제로이다
임의로하지만, 지속적으로.

983
00:45:59,510 --> 00:46:01,170
모든 오른쪽 가장자리가 그들이다.

984
00:46:01,170 --> 00:46:05,070
>> 그리고 호프만,이 제안 무엇
당신이 B를 표현하려면,

985
00:46:05,070 --> 00:46:10,080
로 숫자 66을 나타냅니다보다는
팔 전체 비트 아스키,

986
00:46:10,080 --> 00:46:13,360
당신은 무슨, 그냥 가게를 알고
패턴 제로, 제로, 제로,

987
00:46:13,360 --> 00:46:17,030
제로는 경로의 때문에
내 나무에서 씨 허프만의 나무,

988
00:46:17,030 --> 00:46:18,600
루트에서 잎에.

989
00:46:18,600 --> 00:46:20,970
당신을 저장하려면
E 대조적으로,하지

990
00:46:20,970 --> 00:46:26,290
E.를 나타내는 8 비트를 전송
대신 비트 어떤 패턴을 보내?

991
00:46:26,290 --> 00:46:26,890
하나.

992
00:46:26,890 --> 00:46:30,410
그리고이 약 좋은거야
그 E는 가장 인기있는 문자입니다,

993
00:46:30,410 --> 00:46:32,340
당신은을 사용하는
그것에 대한 짧은 코드입니다.

994
00:46:32,340 --> 00:46:34,090
다음으로 가장 인기있는
편지는 같다

995
00:46:34,090 --> 00:46:37,380
A.이었다 그리고 얼마나 많은 비트
그는 그것을 위해 사용 제안 했는가?

996
00:46:37,380 --> 00:46:38,270
0 개, 1 개.

997
00:46:38,270 --> 00:46:41,060
>> 그리고 그것은 구현 있기 때문에
이 나무로, 지금은

998
00:46:41,060 --> 00:46:43,350
내가 거기에 규정하자
모스와 같이 모호성 없습니다

999
00:46:43,350 --> 00:46:46,090
코드의 모든 때문에
당신이 걱정 편지

1000
00:46:46,090 --> 00:46:48,780
이들 에지들의 단부에있다.

1001
00:46:48,780 --> 00:46:50,580
그래서 그냥 하나
나무의 응용 프로그램입니다.

1002
00:46:50,580 --> 00:46:52,538
이은 ... - 나는 파도합니다
이에 내 손 방법을

1003
00:46:52,538 --> 00:46:55,570
C 구조로이를 구현 할 수 있습니다.

1004
00:46:55,570 --> 00:46:58,260
우리는 결합해야
기호, 문자 등,

1005
00:46:58,260 --> 00:46:59,910
및 주파수에 좌우.

1006
00:46:59,910 --> 00:47:02,510
그러나의 두 가지를 살펴 보자
마지막 예는거야

1007
00:47:02,510 --> 00:47:06,070
후 꽤 익숙해
문제의 퀴즈 제로 다섯을 설정합니다.

1008
00:47:06,070 --> 00:47:09,210
>> 따라서 데이터 구조가
해시 테이블로 알려진.

1009
00:47:09,210 --> 00:47:12,247
그리고 해시 테이블의 종류입니다
이 버킷을 갖는 것을 냉각.

1010
00:47:12,247 --> 00:47:14,830
그리고 네 개의 버킷이 겠
여기에, 단지 4 개의 빈 공간.

1011
00:47:14,830 --> 00:47:20,830
여기에 여기에 한 벌의 카드는, 그리고
클럽, 스페이드, 클럽, 다이아몬드, 클럽,

1012
00:47:20,830 --> 00:47:25,960
다이아몬드, 클럽, 다이아몬드,
clubs-- 그래서 이것은 랜덤입니다.

1013
00:47:25,960 --> 00:47:30,330
하트, hearts-- 그래서 해요
여기에 모든 입력을 bucketizing.

1014
00:47:30,330 --> 00:47:32,430
그리고 해시 테이블 요구
귀하의 의견을보고,

1015
00:47:32,430 --> 00:47:34,850
다음 일정에 넣어
당신이 보는 무엇을 기준으로 배치합니다.

1016
00:47:34,850 --> 00:47:35,600
이 알고리즘입니다.

1017
00:47:35,600 --> 00:47:37,980
그리고 슈퍼를 사용했다
단순한 시각적 알고리즘.

1018
00:47:37,980 --> 00:47:40,030
의 가장 어려운 부분이었다
그림이 무엇인지 기억.

1019
00:47:40,030 --> 00:47:41,590
그리고 네 총 것들을있다.

1020
00:47:41,590 --> 00:47:45,440
>> 이제 스택, 성장 된
여기에 의도적 인 디자인 일이다.

1021
00:47:45,440 --> 00:47:46,540
그러나 나는 다른 무엇을 할 수 있는가?

1022
00:47:46,540 --> 00:47:49,080
그래서 실제로 여기에 우리가
오래된 학교 시험 책의 무리.

1023
00:47:49,080 --> 00:47:51,240
한 무리한다고 가정
학생 이름은 여기에 있습니다.

1024
00:47:51,240 --> 00:47:52,570
여기에 더 큰 해시 테이블입니다.

1025
00:47:52,570 --> 00:47:54,867
대신 네 개의 버킷,
나는의 26 가정 해 봅시다했다.

1026
00:47:54,867 --> 00:47:57,950
그리고 우리는 (26)을 빌려 가고 싶지 않았다
외부 [에서 물건? 애넌 버그?], 그래서

1027
00:47:57,950 --> 00:48:00,289
여기를 대표하는 다섯이다
Z까지 그리고 만약 내가

1028
00:48:00,289 --> 00:48:03,580
누구의 이름으로 시작하는 학생을 볼
나는 거기에 자신의 퀴즈를 넣어거야.

1029
00:48:03,580 --> 00:48:08,850
누군가가 C로 시작하면, 저기,
그럼하지 머 실제로 그렇게하고 싶지 않았다.

1030
00:48:08,850 --> 00:48:10,060
B는 여기에 간다.

1031
00:48:10,060 --> 00:48:13,390
그래서있어 A와 B와 C 그리고
지금 여기에 또 다른 학생입니다.

1032
00:48:13,390 --> 00:48:16,212
그러나 해시 테이블이면
배열로 구현,

1033
00:48:16,212 --> 00:48:17,920
나는 종류의 나사 해요
이 시점에서, 오른쪽?

1034
00:48:17,920 --> 00:48:19,510
나는 종류의이 곳을 넣을 필요가있다.

1035
00:48:19,510 --> 00:48:24,380
>> 그래서이 문제를 해결할 수있는 한 가지 방법은 모든입니다
오른쪽은 C가 통화, B가 통화 중, 통화 중입니다.

1036
00:48:24,380 --> 00:48:28,880
나는에 그래서 D에 집어 넣어거야
첫째, 임의 즉시 액세스 할 수 있습니다

1037
00:48:28,880 --> 00:48:31,064
학생들을위한 버킷의 각.

1038
00:48:31,064 --> 00:48:33,230
그러나 지금은 종류의 양도 것
뭔가 선형으로,

1039
00:48:33,230 --> 00:48:36,750
내가 사람을 검색 할 경우 때문에
누구의 이름으로 시작, 나는 여기에서 확인.

1040
00:48:36,750 --> 00:48:38,854
하지만이 아닌 경우
내가 찾고 학생,

1041
00:48:38,854 --> 00:48:41,520
나는 종류의 검사를 시작해야
양동이, 내가 무슨 짓을했는지 때문에

1042
00:48:41,520 --> 00:48:44,530
의 선형 종류이었다
데이터 구조 프로브.

1043
00:48:44,530 --> 00:48:47,710
보고있는 것만 말하는 바보 방법
첫 번째 사용 가능한 개방,

1044
00:48:47,710 --> 00:48:51,850
그리고, 말하자면, 플랜 B로두고
또는이 경우 계획 D, 값

1045
00:48:51,850 --> 00:48:53,340
해당 위치에.

1046
00:48:53,340 --> 00:48:56,470
이 것을이 당신이했습니다 경우 바로 그래서이다
26 곳과없는 학생들을 얻었다

1047
00:48:56,470 --> 00:49:00,600
이름 Q 또는 Z, 또는 무엇인가 등으로
것을, 적어도 당신은 공간을 사용하고 있습니다.

1048
00:49:00,600 --> 00:49:03,140
>> 그러나 우리는 이미 더 봤어요
여기에 영리 솔루션, 오른쪽?

1049
00:49:03,140 --> 00:49:04,870
대신 무엇을 할 것입니다
당신은 충돌이있는 경우?

1050
00:49:04,870 --> 00:49:06,670
두 사람이있는 경우
이름, 무슨 일이 것

1051
00:49:06,670 --> 00:49:09,160
스마트 이상이었다
단지보다 직관적 인 솔루션

1052
00:49:09,160 --> 00:49:12,840
D가 있어야하는데 퍼팅?

1053
00:49:12,840 --> 00:49:14,810
왜 그냥 가지 마세요
외부 [? 애넌 버그?],

1054
00:49:14,810 --> 00:49:19,960
malloc에​​, 다른 노드처럼 넣어
여기에 다음 여기에 학생 것을 넣어.

1055
00:49:19,960 --> 00:49:22,120
나는 본질적으로 가질 수 있도록
배열의 일종,

1056
00:49:22,120 --> 00:49:25,590
또는 우리가있는 한 아마도 더 우아하게
연결리스트를보기 시작.

1057
00:49:25,590 --> 00:49:29,520
>> 그래서 해시 테이블 구조
즉, 그냥 다음과 같을 수 있습니다

1058
00:49:29,520 --> 00:49:33,900
하지만 더 영리하게, 당신은 무엇인가라는
별도의 체인, 이에 해시 테이블

1059
00:49:33,900 --> 00:49:38,340
간단히 배열의 각이고,
요소가 숫자가 아닌,

1060
00:49:38,340 --> 00:49:40,470
연결리스트는 자체입니다.

1061
00:49:40,470 --> 00:49:45,080
당신은 슈퍼 빠른 액세스를 얻을 수 있도록
경우에 값을 해시를 결정할.

1062
00:49:45,080 --> 00:49:48,059
많은 카드의 예와 같이,
나는 슈퍼 빠른 결정을했다.

1063
00:49:48,059 --> 00:49:49,600
하트 다이아몬드는 간다, 간다.

1064
00:49:49,600 --> 00:49:52,180
여기에 같은, 여기 간다,
D는 B가 간다, 간다.

1065
00:49:52,180 --> 00:49:55,740
그래서 슈퍼 빠른 조회를 한 경우
당신은 경우에 실행하는 일이

1066
00:49:55,740 --> 00:49:59,429
당신이있어 충돌, 두
같은 이름을 가진 사람, 그럼

1067
00:49:59,429 --> 00:50:00,970
당신은 이들과 결합하고 시작합니다.

1068
00:50:00,970 --> 00:50:03,900
그리고 어쩌면 당신은 그들을 정렬 유지
알파벳, 어쩌면 당신은하지 않습니다.

1069
00:50:03,900 --> 00:50:05,900
그러나 적어도 지금 우리는 역 동성을 가지고있다.

1070
00:50:05,900 --> 00:50:10,250
그래서 한편으로 우리는 슈퍼 빠른 있습니다
일정 시간, 그리고 선형 시간 가지

1071
00:50:10,250 --> 00:50:14,110
이러한 연결리스트 경우 참여
조금 긴 얻을 시작합니다.

1072
00:50:14,110 --> 00:50:16,880
>> 그래서 바보 같은 이런 종류의,
전 괴짜 농담 년.

1073
00:50:16,880 --> 00:50:19,590
CS50 해킹 - 마라톤에서,
학생들이 체크인 할 때,

1074
00:50:19,590 --> 00:50:22,040
일부 TF 또는 CA 매년
생각이 올려 재미

1075
00:50:22,040 --> 00:50:27,772
이 같은 기호, 어디 그냥
이름이로 시작하면 의미,

1076
00:50:27,772 --> 00:50:28,870
이 길을 갈.

1077
00:50:28,870 --> 00:50:31,110
이름이 시작되는 경우
B로,이 항아리 확인을 이동

1078
00:50:31,110 --> 00:50:33,290
그것은 아마 나중에 학기 재미있다.

1079
00:50:33,290 --> 00:50:36,420
그러나 다른있다
또한,이 일의 방법입니다.

1080
00:50:36,420 --> 00:50:37,410
다시 그에게 가자.

1081
00:50:37,410 --> 00:50:38,600
>> 그래서이 구조가있다.

1082
00:50:38,600 --> 00:50:40,420
그리고 이것은 우리의 마지막
오늘 구조,

1083
00:50:40,420 --> 00:50:42,400
이는 트라이라고 무언가이다.

1084
00:50:42,400 --> 00:50:47,140
어떤 이유로 짧은 T-R-I-E,
검색을 위해,하지만 트라이라고.

1085
00:50:47,140 --> 00:50:51,389
그래서 트라이는 또 다른 재미
이 아이디어의 많은 아말감.

1086
00:50:51,389 --> 00:50:52,930
그것은 우리가 전에 본 적이 트리입니다.

1087
00:50:52,930 --> 00:50:54,180
그것은 이진 검색 트리 아니다.

1088
00:50:54,180 --> 00:50:58,410
그것은 아이들의 수와 나무의
하지만 트라이의 아이들의 각

1089
00:50:58,410 --> 00:51:00,090
배열입니다.

1090
00:51:00,090 --> 00:51:04,790
크기의 배열, 26 아니면 27 말
당신은 하이픈 이름을 지원하려는 경우

1091
00:51:04,790 --> 00:51:06,790
또는 사람의 이름에 아포스트로피.

1092
00:51:06,790 --> 00:51:08,280
>> 그리고이 데이터 구조이다.

1093
00:51:08,280 --> 00:51:10,290
그리고 당신은 정상에서 보면
아래로,이 마음

1094
00:51:10,290 --> 00:51:13,710
, 거기 최상위 노드, M 봐
이 왼쪽 일을 가리키는

1095
00:51:13,710 --> 00:51:17,665
이는 다음, X, W, E, L은, L. 이것은이다
다만 데이터 구조 임의로 그

1096
00:51:17,665 --> 00:51:19,120
사람의 이름을 저장합니다.

1097
00:51:19,120 --> 00:51:25,720
그리고 맥스웰은 다음에 의해 저장된다
배열 배열 배열의 경로입니다.

1098
00:51:25,720 --> 00:51:30,050
트라이는 약하지만 놀라운 무엇
그 연결리스트 반면, 심지어

1099
00:51:30,050 --> 00:51:34,520
배열은, 우리가 이제까지받은 것 중에 최고입니다
선형 시간 또는 로그 시간을 찾고

1100
00:51:34,520 --> 00:51:35,600
사람입니다.

1101
00:51:35,600 --> 00:51:40,530
트라이의 데이터 구조, 경우에
내 데이터 구조는 하나의 이름을 가지고

1102
00:51:40,530 --> 00:51:43,720
나는 맥스웰을 찾고 있어요, 내가 해요
꽤 빨리 그를 찾을 것.

1103
00:51:43,720 --> 00:51:47,910
난 그냥 M-A-X-W-E-L-L을 찾습니다. 만약
이 데이터 구조에 대조적으로,

1104
00:51:47,910 --> 00:51:51,830
가 있다면 N은, 만 인 경우
이 데이터 구조 만 이름

1105
00:51:51,830 --> 00:51:57,100
맥스웰은 계속 될 것입니다
검색 가능 단지 M-A-X-W-E-L-L 후

1106
00:51:57,100 --> 00:51:58,090
단계.

1107
00:51:58,090 --> 00:52:01,276
그리고 David-- D-A-V-I-D 단계.

1108
00:52:01,276 --> 00:52:03,400
즉, 구축하여
의 데이터 구조

1109
00:52:03,400 --> 00:52:07,240
있어 이러한 배열의 모든, 모두의
자체는, 랜덤 액세스를 지원

1110
00:52:07,240 --> 00:52:11,090
나는 사람들의를 찾고 시작할 수 있습니다
시간의 양을 사용하여 이름

1111
00:52:11,090 --> 00:52:14,340
하지 수에 비례
데이터 구조의 것들,

1112
00:52:14,340 --> 00:52:16,330
같은 만 존재하는 이름.

1113
00:52:16,330 --> 00:52:20,135
그것을 찾기 위해 나를 걸리는 시간
M-A-X-W-L-E-L 데이터 구조로되어

1114
00:52:20,135 --> 00:52:22,260
비례하지 않음
데이터 구조의 크기,

1115
00:52:22,260 --> 00:52:25,930
그러나 이름의 길이.

1116
00:52:25,930 --> 00:52:28,440
그리고 현실적으로
이름은 우리가 찾고있어

1117
00:52:28,440 --> 00:52:29,970
결코 긴 미친 될 것 없습니다.

1118
00:52:29,970 --> 00:52:32,600
아마 누군가가 10 문자가
20 문자의 이름입니다.

1119
00:52:32,600 --> 00:52:33,900
그것은 바로, 확실히 유한입니까?

1120
00:52:33,900 --> 00:52:37,110
지구에 인간이 누구
가장 긴 이름을 가진,

1121
00:52:37,110 --> 00:52:39,920
하지만 그 이름은 상수
값 길이, 오른쪽?

1122
00:52:39,920 --> 00:52:41,980
그것은 어떤 의미에서 변화하지 않습니다.

1123
00:52:41,980 --> 00:52:45,090
그래서이 방법으로, 우리는했습니다
데이터 구조를 달성

1124
00:52:45,090 --> 00:52:47,800
즉 일정 시간 룩업입니다.

1125
00:52:47,800 --> 00:52:50,670
이것은 다수의 단계를 거쳐야
입력의 길이에 따라,

1126
00:52:50,670 --> 00:52:54,250
이름이 아닌 번호
데이터 구조.

1127
00:52:54,250 --> 00:52:58,700
우리는 이름들의 수를 두 배로한다면
억 이십억로부터 다음 해,

1128
00:52:58,700 --> 00:53:03,720
발견 맥스웰은 걸릴 것입니다
일곱 단계의 동일한 번호

1129
00:53:03,720 --> 00:53:04,650
그를 찾을 수 있습니다.

1130
00:53:04,650 --> 00:53:08,810
그래서 우리는 달성 한 것 같다
실행 시간의 우리의 성배.

1131
00:53:08,810 --> 00:53:10,860
>> 너무 빨리 발표의 커플.

1132
00:53:10,860 --> 00:53:11,850
퀴즈 제로 올라오고있다.

1133
00:53:11,850 --> 00:53:14,600
코스의 웹 사이트에 그에 대한 자세한
앞으로 며칠 동안.

1134
00:53:14,600 --> 00:53:17,120
월요일은 휴일이다 lecture--
여기 하버드 월요일에.

1135
00:53:17,120 --> 00:53:18,850
또한, 뉴 헤이븐에없는
그래서 우리는 수업을하고

1136
00:53:18,850 --> 00:53:20,310
월요일에 강의를위한 뉴 헤이븐에.

1137
00:53:20,310 --> 00:53:22,550
모든 것이 촬영한다
그리고, 평소와 같이 라이브 스트리밍

1138
00:53:22,550 --> 00:53:24,900
하지만의 오늘 종료하자
30 초 클립

1139
00:53:24,900 --> 00:53:26,910
소위 "깊은 생각"
Daven 판햄에 의해하는

1140
00:53:26,910 --> 00:53:30,850
토요일 지난해 영감을했다
밤 라이브의 "깊은 생각"

1141
00:53:30,850 --> 00:53:35,700
잭 핸디으로하는
지금은 이해합니다.

1142
00:53:35,700 --> 00:53:38,810
>> 영화 : 그리고 지금, "깊은
Daven 판햄으로 생각 ".

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
해시 테이블.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> 스피커 1 : 좋아, 그건 지금은 그것 뿐이다.

1147
00:53:47,660 --> 00:53:48,805
우리는 다음 주에 볼 수 있습니다.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> 더그 : 행동을 참조하십시오.

1150
00:53:56,680 --> 00:53:58,304
그래서 지금 그 살펴 보자.

1151
00:53:58,304 --> 00:53:59,890
그래서 여기, 우리는 정렬되지 않은 배열을 가지고있다.

1152
00:53:59,890 --> 00:54:04,860
>> 이안 : 더그, 당신은 앞으로 다시 시작 갈 수
한 초이, 제발.

1153
00:54:04,860 --> 00:54:08,562
좋아, 카메라는 그래서, 압연된다
행동이 더그, 준비가 될 때마다 확인을?

1154
00:54:08,562 --> 00:54:11,020
DOUG : 좋아, 그래서 우리
여기에있는 것은 정렬되지 않은 배열입니다.

1155
00:54:11,020 --> 00:54:13,960
그리고 모든 요소를​​ 색깔했습니다
이 사실을 나타 내기 위해 빨간색,

1156
00:54:13,960 --> 00:54:14,460
정렬되지 않은.

1157
00:54:14,460 --> 00:54:17,960
그래서 먼저 우리가 리콜
우리는 어레이의 왼쪽 절반을 정렬한다.

1158
00:54:17,960 --> 00:54:20,630
그 다음 우리는 오른쪽으로 정렬
배열의 절반입니다.

1159
00:54:20,630 --> 00:54:22,830
그리고 나중에 - 다, 아 -​​ 다, 아 -​​ 다,
우리는 함께 병합.

1160
00:54:22,830 --> 00:54:24,520
그리고 우리는 완전히 정렬 된 배열을 가지고있다.

1161
00:54:24,520 --> 00:54:25,360
그래서 작동 일종의 병합 방법입니다.

1162
00:54:25,360 --> 00:54:27,109
>> IAN : 워, 워, 워,
컷, 컷, 컷, 컷.

1163
00:54:27,109 --> 00:54:30,130
더그, 그냥 나중에 - 다 할 수없는, 아 -​​ 다,
아 - 다, 병합 정렬을 통해 당신의 방법.

1164
00:54:30,130 --> 00:54:31,970
>> 더그 : 난 그냥했다.

1165
00:54:31,970 --> 00:54:32,832
괜찮아.

1166
00:54:32,832 --> 00:54:33,540
우리는 갈 수 있어요.

1167
00:54:33,540 --> 00:54:34,760
그냥 롤링을 유지하자.

1168
00:54:34,760 --> 00:54:35,380
어쨌든,

1169
00:54:35,380 --> 00:54:37,800
>> 이안 : 당신은 설명 할 필요
그것을 더 완벽하게보다.

1170
00:54:37,800 --> 00:54:39,999
그건 그냥 충분하지 않습니다.

1171
00:54:39,999 --> 00:54:41,790
DOUG : 이안, 우리는하지 않습니다
하나로 돌아갈 필요가있다.

1172
00:54:41,790 --> 00:54:42,350
괜찮아.

1173
00:54:42,350 --> 00:54:45,690
어쨌든, 우리는 merge--를 계속하는 경우
이안, 우리는 촬영 중간에있어.

1174
00:54:45,690 --> 00:54:46,612
>> 이안 : 알아.

1175
00:54:46,612 --> 00:54:49,320
그리고 우리가 나중에 - 다 할 수없는, 아 -​​ 다,
전체 과정을 통해 아 - 다.

1176
00:54:49,320 --> 00:54:52,200
당신은 어떻게 설명 할 필요
양측이 함께 병합 얻는다.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG :하지만 우리는 이미했습니다
설명 방법이 sides--

1178
00:54:53,570 --> 00:54:55,321
>> 이안 : 당신은 그냥 보여 주었다
그들을 병합 배열입니다.

1179
00:54:55,321 --> 00:54:56,486
더그 : 그들은이 과정을 알고있다.

1180
00:54:56,486 --> 00:54:57,172
그들은 괜찮아요.

1181
00:54:57,172 --> 00:54:58,380
우리는 그 위에 열 번 갔어요.

1182
00:54:58,380 --> 00:55:00,330
>> 이안 : 당신은 바로 그 위에 생략.

1183
00:55:00,330 --> 00:55:03,360
우리는 하나 다시거야, 당신
그 위에 당신이 나중에 - 다, 아 -​​ 다 할 수 없습니다.

1184
00:55:03,360 --> 00:55:05,480
다시 한에 대한 모든 권리,.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG : 나는 돌아 가야한다
모든 슬라이드를 통해?

1186
00:55:07,833 --> 00:55:08,332
나의 하나님.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
그것은 여섯 번째 시간, 이안 같다.

1189
00:55:13,004 --> 00:55:13,940
괜찮아.

1190
00:55:13,940 --> 00:55:15,200
>> 이안 : 좋아.

1191
00:55:15,200 --> 00:55:16,590
당신 준비?

1192
00:55:16,590 --> 00:55:17,400
좋아요.

1193
00:55:17,400 --> 00:55:18,950
액션.