1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG 로이드 : 그래서 CS50, 우리는 다루었
다른 데이터 구조의 많은

3
00:00:08,300 --> 00:00:09,180
권리?

4
00:00:09,180 --> 00:00:11,420
우리는 배열을 볼 수, 및 연결 한
목록 및 해시 테이블,

5
00:00:11,420 --> 00:00:15,210
및 시도, 스택과 큐.

6
00:00:15,210 --> 00:00:17,579
우리는 또한 조금 배울 수 있습니다
나무와 힙에 대한,

7
00:00:17,579 --> 00:00:20,120
하지만 정말이 모든 단지 종료
최대 테마에 변화를 주도했습니다.

8
00:00:20,120 --> 00:00:22,840
정말이있다 이러한
네 가지 기본 아이디어 가지

9
00:00:22,840 --> 00:00:25,190
다른 그 모든 졸이다 수 있습니다.

10
00:00:25,190 --> 00:00:28,150
배열, 연결리스트,
해시 테이블 및 시도합니다.

11
00:00:28,150 --> 00:00:30,720
그리고 같은 내가 거기 말했다
그들에 변화가있다,

12
00:00:30,720 --> 00:00:32,720
하지만이 꽤있다
많은 요약 것

13
00:00:32,720 --> 00:00:38,140
모든 것을 우리가 이야기거야
C의 관점에서이 클래스에 대한

14
00:00:38,140 --> 00:00:40,140
>> 그러나 방법이 바로, 모든 측정 최대합니까?

15
00:00:40,140 --> 00:00:44,265
우리는 장점과 단점에 대해 얘기했습니다
그들에 별도의 동영상의 각의,

16
00:00:44,265 --> 00:00:46,390
하지만 숫자가 많이있다
주위에 던져지고.

17
00:00:46,390 --> 00:00:48,723
일반적으로 많이있다
생각은 주위에 던져지고.

18
00:00:48,723 --> 00:00:51,950
의 시도하고 통합하자
그것은 단지 하나의 장소에.

19
00:00:51,950 --> 00:00:55,507
의가에 대해 전문가의 무게를 보자
단점 및 고려

20
00:00:55,507 --> 00:00:57,340
이는 데이터 구조
올바른 데이터 수 있습니다

21
00:00:57,340 --> 00:01:01,440
특정 상황에 대한 구조,
데이터의 어떤 종류의 당신은 저장하고있다.

22
00:01:01,440 --> 00:01:06,625
당신은 반드시 항상 할 필요가 없습니다
, 슈퍼 빠른 삽입, 삭제를 사용하여

23
00:01:06,625 --> 00:01:10,761
트라이의 및 조회 당신이 만약 정말로
삽입과 삭제에 대한 상관 없어

24
00:01:10,761 --> 00:01:11,260
너무 많은.

25
00:01:11,260 --> 00:01:13,968
당신은 신속하게 임의해야하는 경우
액세스는, 어쩌면 배열이 더 좋다.

26
00:01:13,968 --> 00:01:15,340
그래서 그 증류 할 수 있습니다.

27
00:01:15,340 --> 00:01:18,530
의 네 개의 각각에 대해 얘기하자
데이터 구조의 주요 종류

28
00:01:18,530 --> 00:01:21,720
우리는 이야기, 그리고했는지
그들이 잘 될 수있는 경우에 단지 참조

29
00:01:21,720 --> 00:01:23,340
때 그들은 그렇게 좋은하지 않을 수 있습니다.

30
00:01:23,340 --> 00:01:24,610
그럼 배열을 시작하자.

31
00:01:24,610 --> 00:01:27,300
삽입 그래서, 그 종류의 나쁜.

32
00:01:27,300 --> 00:01:31,350
>> 배열의 마지막에 삽입은 OK입니다
우리가 가서 우리는 배열을 구축하는 경우.

33
00:01:31,350 --> 00:01:33,570
그러나 우리는 삽입해야하는 경우
중간에 요소,

34
00:01:33,570 --> 00:01:35,550
삽입을 다시 생각한다
정렬 많이있다

35
00:01:35,550 --> 00:01:37,510
의 거기에 요소에 맞게 이동.

36
00:01:37,510 --> 00:01:41,170
그리고 우리는 삽입하는거야 그렇다면
어딘가에 그러나 어레이의 단부,

37
00:01:41,170 --> 00:01:43,590
그것은 아마 그렇게 큰 아니에요.

38
00:01:43,590 --> 00:01:46,710
>> 마찬가지로, 삭제하지 않는 한 우리는있어
어레이의 단부로부터 삭제

39
00:01:46,710 --> 00:01:49,810
아마도 만약 그렇게 크지 않다
우리는 빈 틈을 떠나고 싶지 않아,

40
00:01:49,810 --> 00:01:50,790
이는 일반적으로 우리가하지 않습니다.

41
00:01:50,790 --> 00:01:54,700
우리는 요소를 제거 할, 그리고
다음 종류의 다시 아늑한합니다.

42
00:01:54,700 --> 00:01:57,670
그래서에서 요소를 삭제
배열도 그렇게 크지 않다.

43
00:01:57,670 --> 00:01:58,820
>> 조회는하지만, 아주 좋습니다.

44
00:01:58,820 --> 00:02:00,920
우리는 랜덤 액세스 할 수 있습니다,
일정 시간 조회.

45
00:02:00,920 --> 00:02:03,800
우리는 단지 일곱 말을하고, 우리가 간다
배열 재배치 일곱.

46
00:02:03,800 --> 00:02:05,907
우리는로 이동하여, 20 말
배열 재배치 (20).

47
00:02:05,907 --> 00:02:07,240
우리는에서 반복 할 필요가 없습니다.

48
00:02:07,240 --> 00:02:08,630
그건 꽤 좋은입니다.

49
00:02:08,630 --> 00:02:11,020
>> 배열은 정렬하기가 비교적 쉽다.

50
00:02:11,020 --> 00:02:14,040
우리가 정렬에 대해 얘기 할 때마다
이러한 선택 정렬과 같은 알고리즘,

51
00:02:14,040 --> 00:02:18,820
삽입 정렬, 버블 정렬, 병합
종류, 우리는 항상 그것을 할 배열을 사용,

52
00:02:18,820 --> 00:02:21,860
배열은 꽤 쉽기 때문에
데이터 구조들에 대하여, 정렬

53
00:02:21,860 --> 00:02:22,970
우리는 지금까지 본 것.

54
00:02:22,970 --> 00:02:24,320
>> 또한 상대적으로 작은입니다.

55
00:02:24,320 --> 00:02:25,695
여분의 공간이 많이 아니에요.

56
00:02:25,695 --> 00:02:29,210
당신은 정확히만큼 따로
당신이 당신의 데이터를 보유해야하므로,

57
00:02:29,210 --> 00:02:30,320
그게 꽤 많이 있습니다.

58
00:02:30,320 --> 00:02:33,180
그래서 그들은 아주 작은 것
그 방법으로 효율적입니다.

59
00:02:33,180 --> 00:02:36,000
그러나 또 다른 단점하지만,
그들은 크기가 고정되어 있다는 것입니다.

60
00:02:36,000 --> 00:02:38,630
우리는 정확히 어떻게 선언해야
큰 우리는, 우리의 배열이 원하는

61
00:02:38,630 --> 00:02:39,940
우리는 만에 하나의 기회를 얻을.

62
00:02:39,940 --> 00:02:41,280
우리는 성장하고 축소 할 수 없습니다.

63
00:02:41,280 --> 00:02:44,582
>> 우리가 성장 또는 축소해야하는 경우, 우리
완전히 새로운 배열을 선언해야합니다,

64
00:02:44,582 --> 00:02:47,750
의 모든 요소를​​ 복사
두 번째 배열에 첫 번째 배열.

65
00:02:47,750 --> 00:02:51,410
그리고 우리는 잘못 계산하는 경우
시간, 우리는 다시 할 필요가있다.

66
00:02:51,410 --> 00:02:52,760
정말 대단하지.

67
00:02:52,760 --> 00:02:58,750
그래서 배열은 우리에게 유연성을 제공하지 않습니다
요소의 변수 번호를 가지고 있습니다.

68
00:02:58,750 --> 00:03:01,320
>> 연결리스트로,
삽입은 매우 간단합니다.

69
00:03:01,320 --> 00:03:03,290
우리는 단지 전면에 압정.

70
00:03:03,290 --> 00:03:04,892
삭제도 매우 간단합니다.

71
00:03:04,892 --> 00:03:06,100
우리는 요소를 찾을 수있다.

72
00:03:06,100 --> 00:03:07,270
즉, 약간의 검색을 포함한다.

73
00:03:07,270 --> 00:03:10,270
>> 하지만 당신은 요소를 찾으면
당신은 당신이해야 할 모든 찾고

74
00:03:10,270 --> 00:03:12,830
포인터를 변경하고,
가능성이 당신이있는 경우

75
00:03:12,830 --> 00:03:15,151
이 이중 list-- 연결
연결리스트, rather--

76
00:03:15,151 --> 00:03:16,650
다음은 노드를 확보 할 수 있습니다.

77
00:03:16,650 --> 00:03:18,399
당신은 이동하지 않아도
주변의 모든 것을.

78
00:03:18,399 --> 00:03:22,090
당신은, 두 개의 포인터를 변경
그래서 꽤 빠르다.

79
00:03:22,090 --> 00:03:23,470
>> 조회 바로, 그래도 나쁜?

80
00:03:23,470 --> 00:03:26,280
우리를 찾는 위해서는
연결리스트의 요소,

81
00:03:26,280 --> 00:03:29,154
여부를 단독으로 또는 이중으로 연결된
우리는 그것을 검색 선형해야합니다.

82
00:03:29,154 --> 00:03:32,320
우리는 처음부터 시작해야하고
끝을 이동하거나 최종 이동 시작

83
00:03:32,320 --> 00:03:33,860
처음으로.

84
00:03:33,860 --> 00:03:35,474
우리는 더 이상 랜덤 액세스 할 수 없습니다.

85
00:03:35,474 --> 00:03:37,265
우리가 일을하는 경우에 따라서
검색의 많은, 어쩌면

86
00:03:37,265 --> 00:03:39,830
연결리스트는 아니다
우리에게 꽤 좋은.

87
00:03:39,830 --> 00:03:43,750
>> 그들은 정말도있어
정렬하기 어려운, 오른쪽?

88
00:03:43,750 --> 00:03:45,666
유일한 방법은 당신이 할 수있는
정말 링크 목록을 정렬

89
00:03:45,666 --> 00:03:47,870
당신이 그것을 구성으로 분류하는 것입니다.

90
00:03:47,870 --> 00:03:50,497
하지만 당신은 당신으로 분류하는 경우
를 구축, 당신은 더 이상 것 없다

91
00:03:50,497 --> 00:03:51,830
더 이상 빠른 삽입을.

92
00:03:51,830 --> 00:03:53,746
당신은 시침하지 않을
전면 위에 것들.

93
00:03:53,746 --> 00:03:55,710
당신은 찾을 수있다
정확한 지점은 그것을 넣어,

94
00:03:55,710 --> 00:03:57,820
다음 삽입
단지에 대한 나쁜됩니다

95
00:03:57,820 --> 00:03:59,390
배열에 삽입있다.

96
00:03:59,390 --> 00:04:03,130
그래서 연결리스트가 없습니다
데이터를 정렬 너무 좋아요.

97
00:04:03,130 --> 00:04:05,830
>> 그들은 또한 아주 작은 크기 현명한입니다.

98
00:04:05,830 --> 00:04:08,496
이중 약간 목록을 연결
단일 연결리스트보다 큰,

99
00:04:08,496 --> 00:04:10,620
이는 약간 큰
어레이보다하지만 아니다

100
00:04:10,620 --> 00:04:13,330
낭비 된 공간의 엄청난 금액.

101
00:04:13,330 --> 00:04:18,730
그래서 만약 공간이 프리미엄이지만,
아니 정말 강렬한 프리미엄,

102
00:04:18,730 --> 00:04:22,180
이 갈 올바른 방법 일 수 있습니다.

103
00:04:22,180 --> 00:04:23,330
>> 해시 테이블.

104
00:04:23,330 --> 00:04:25,850
해시 테이블로의 삽입
매우 간단합니다.

105
00:04:25,850 --> 00:04:26,980
이것은 두 단계 프로세스이다.

106
00:04:26,980 --> 00:04:30,700
처음에 우리는을 통해 우리의 데이터를 실행해야
해시 함수는 해시 코드를 얻으려면,

107
00:04:30,700 --> 00:04:37,550
그리고, 우리는에 요소를 삽입
그 해시 코드의 위치에서 해시 테이블.

108
00:04:37,550 --> 00:04:40,879
>> 연결리스트와 유사한 삭제,
당신이 요소를 발견하면 쉽다.

109
00:04:40,879 --> 00:04:43,170
당신은 먼저 찾아야
하지만 당신은 그것을 삭제하면,

110
00:04:43,170 --> 00:04:45,128
당신은 단지 교환 할 필요가
포인터의 부부,

111
00:04:45,128 --> 00:04:47,250
경우 별도의 체인을 사용하고 있습니다.

112
00:04:47,250 --> 00:04:49,942
당신이 프로빙 사용하는 경우,
또는 당신이하지 않은 경우

113
00:04:49,942 --> 00:04:51,650
사용하는 모든 체인
하여 해쉬 테이블에서,

114
00:04:51,650 --> 00:04:53,040
삭제는 실제로 정말 간단합니다.

115
00:04:53,040 --> 00:04:57,134
당신이해야 할 모든 해시입니다
데이터는 다음 해당 위치로 이동합니다.

116
00:04:57,134 --> 00:04:58,925
그리고 가정 당신은하지 않습니다
어떤 충돌이

117
00:04:58,925 --> 00:05:01,650
당신은 매우 신속하게 제거 할 수 있습니다.

118
00:05:01,650 --> 00:05:04,930
>> 자, 조회는 어디 것들
좀 더 복잡해진다.

119
00:05:04,930 --> 00:05:06,910
그것은 더 평균있어
연결리스트보다.

120
00:05:06,910 --> 00:05:09,560
당신이 체인을 사용하는 경우,
당신은 여전히​​ 링크 된 목록을 가지고,

121
00:05:09,560 --> 00:05:13,170
이는 여전히 있음을 의미
검색은 링크 된 목록을 손해.

122
00:05:13,170 --> 00:05:18,390
당신이 복용하고 있기 때문에 그러나 당신은 연결
목록 100 또는 1000에 그것을 분할

123
00:05:18,390 --> 00:05:25,380
또는 n 당신의 해시 테이블의 요소, 당신이있어
연결리스트의 크기 n 번째 모두 하나입니다.

124
00:05:25,380 --> 00:05:27,650
그들은 모두 실질적으로 작은입니다.

125
00:05:27,650 --> 00:05:32,080
당신은 N 대신 목록을 연결 한
크기 n의 하나 연결리스트의.

126
00:05:32,080 --> 00:05:34,960
>> 그래서이 실제 상수
일반적으로 우리 요인,

127
00:05:34,960 --> 00:05:39,730
시간 복잡도에 대해 얘기하지 않는, 그것을
실제로 여기에 변화를 않습니다.

128
00:05:39,730 --> 00:05:43,020
그래서 조회는 여전히 선형
당신이 체인을 사용하는 경우 검색,

129
00:05:43,020 --> 00:05:46,780
하지만,리스트의 길이
당신은을 통해 검색하는

130
00:05:46,780 --> 00:05:50,080
비교하면 매우 짧습니다.

131
00:05:50,080 --> 00:05:52,995
다시 정렬하여 인 경우
여기에 목표, 해시 테이블의

132
00:05:52,995 --> 00:05:54,370
아마 올바른 방법은 이동하지.

133
00:05:54,370 --> 00:05:56,830
정렬하면 그냥 배열을 사용
당신에게 정말 중요합니다.

134
00:05:56,830 --> 00:05:58,590
>> 그리고 그들은 크기의 영역을 실행 할 수 있습니다.

135
00:05:58,590 --> 00:06:01,640
그것은 여부를 말하기 어렵다
해시 테이블은 작거나 큰

136
00:06:01,640 --> 00:06:04,110
정말에 의존하기 때문에
얼마나 큰하여 해시 테이블이다.

137
00:06:04,110 --> 00:06:07,340
당신은 단지 저장 될 거라면
당신의 해시 테이블의 다섯 가지 요소,

138
00:06:07,340 --> 00:06:10,620
당신은 해시 테이블이
그것은 10,000 요소,

139
00:06:10,620 --> 00:06:12,614
당신은 아마 많은 공간을 낭비하고 있습니다.

140
00:06:12,614 --> 00:06:15,030
대조 또한 당신에게 할 수있는
매우 컴팩트 한 해시 테이블을 가지고

141
00:06:15,030 --> 00:06:18,720
그러나 작은 당신의 해시 테이블 가져옵니다
그 연결리스트의 각각을 길게

142
00:06:18,720 --> 00:06:19,220
가져옵니다.

143
00:06:19,220 --> 00:06:22,607
그래서 정말 정의 할 수있는 방법이 없습니다
정확하게 해시 테이블의 크기,

144
00:06:22,607 --> 00:06:24,440
그러나 그것은 아마 안전
그것은 일반적으로 말할 수 있습니다

145
00:06:24,440 --> 00:06:27,990
링크보다 더 될 것
동일한 데이터 저장 목록

146
00:06:27,990 --> 00:06:30,400
트라이보다하지만 작은.

147
00:06:30,400 --> 00:06:32,720
>> 그리고 시도는 네 번째입니다
이러한 구조의

148
00:06:32,720 --> 00:06:34,070
것을 우리는 얘기를했습니다.

149
00:06:34,070 --> 00:06:36,450
트라이에 삽입하면 복잡하다.

150
00:06:36,450 --> 00:06:38,400
동적 많이있다
메모리 할당,

151
00:06:38,400 --> 00:06:40,780
특히 초기에,
빌드하기 시작하고있다.

152
00:06:40,780 --> 00:06:43,700
그러나 일정 시간이다.

153
00:06:43,700 --> 00:06:47,690
그것은 단지 요소의 인간
여기가 힘들 수있다.

154
00:06:47,690 --> 00:06:53,250
널 포인터가 발생하는 데, malloc에
공간, 아마도 malloc에​​ 공간이 이동

155
00:06:53,250 --> 00:06:54,490
거기에서 다시.

156
00:06:54,490 --> 00:06:58,880
의 위협 요인의 종류
동적 메모리 할당에 대한 포인터

157
00:06:58,880 --> 00:07:00,130
취소 할 수있는 장애물이다.

158
00:07:00,130 --> 00:07:04,550
그러나 당신이 그것을 삭제 한 후에 삽입
실제로, 매우 간단 온다

159
00:07:04,550 --> 00:07:06,810
그리고 그것은 확실히 일정 시간이다.

160
00:07:06,810 --> 00:07:07,680
>> 삭제가 용이하다.

161
00:07:07,680 --> 00:07:11,330
당신이 할 필요가 아래로 이동하는
포인터와 무료 노드의 커플,

162
00:07:11,330 --> 00:07:12,420
그래서 꽤 좋다.

163
00:07:12,420 --> 00:07:13,930
조회도 꽤 빠릅니다.

164
00:07:13,930 --> 00:07:16,780
그것은 단지 기반으로
데이터의 길이.

165
00:07:16,780 --> 00:07:19,924
모든 데이터가 있다면
다섯 문자열,

166
00:07:19,924 --> 00:07:22,590
예를 들어, 다섯 기억하는
당신의 트라이에 문자열,

167
00:07:22,590 --> 00:07:25,439
그것은 단지 다섯 단계를 수행
당신이 찾고있는 것을 찾을 수 있습니다.

168
00:07:25,439 --> 00:07:28,480
다섯 때문에, 단지 일정한 요인이다
다시, 삽입, 삭제, 조회

169
00:07:28,480 --> 00:07:31,670
여기에 효율적으로, 모든 일정 시간이다.

170
00:07:31,670 --> 00:07:34,880
>> 또 다른 것은 당신의 트라이는 점이다
실제로 종류의 이미 오른쪽으로 정렬?

171
00:07:34,880 --> 00:07:36,800
우리가있어 방법의 장점으로
삽입 요소,

172
00:07:36,800 --> 00:07:40,060
의 문자로 편지를 이동하여
키의 숫자에 의해 키 또는 숫자,

173
00:07:40,060 --> 00:07:45,084
일반적으로, 당신의 트라이가 될 수있을 테니까요
당신이 그것을 구축으로 가지 분류.

174
00:07:45,084 --> 00:07:47,250
정말 수 없습니다
의미는 정렬에 대해 생각하는

175
00:07:47,250 --> 00:07:49,874
같은 방식으로 우리는 생각
그것은 배열, 또는 연결리스트와,

176
00:07:49,874 --> 00:07:51,070
또는 해시 테이블.

177
00:07:51,070 --> 00:07:54,780
그러나 어떤 의미에서, 당신의
당신이 가서 트라이가 정렬됩니다.

178
00:07:54,780 --> 00:07:58,630
>> 단점은 물론 있다는
트라이 빠르게 거대한된다.

179
00:07:58,630 --> 00:08:02,970
모든 연결 지점에서 다음을 수행 할 수도
키는 숫자로 구성된 경우 잔 마셔요,

180
00:08:02,970 --> 00:08:04,880
다른 (10)가
장소는 당신이 갈 수있는

181
00:08:04,880 --> 00:08:07,490
모든 노드 것을 의미한다
정보가 포함되어 있습니다

182
00:08:07,490 --> 00:08:11,440
데이터에 대해 당신이 저장할
해당 노드, 플러스 10 포인터에서.

183
00:08:11,440 --> 00:08:14,430
어느, CS50의 IDE에, 80 바이트입니다.

184
00:08:14,430 --> 00:08:17,220
그래서 적어도 80 바이트의
사용자가 만든 모든 노드,

185
00:08:17,220 --> 00:08:19,240
그리고 심지어 데이터를 계산 아니에요.

186
00:08:19,240 --> 00:08:24,950
및 노드 인 경우는
대신 숫자의 편지,

187
00:08:24,950 --> 00:08:27,825
지금은 26 포인터가
모든 위치에서.

188
00:08:27,825 --> 00:08:32,007
그리고 26 시간 (8)는 아마 200
바이트, 또는 그런 일.

189
00:08:32,007 --> 00:08:33,840
그리고 당신은 자본이
당신에게 할 수 lowercase--

190
00:08:33,840 --> 00:08:35,381
나는이 함께 갈거야 여기서 오른쪽 볼?

191
00:08:35,381 --> 00:08:37,500
귀하의 노드는 정말 얻을 수 있습니다
큰, 그래서 트라이

192
00:08:37,500 --> 00:08:40,470
자체, 전체, 수
너무, 정말 큰 얻을.

193
00:08:40,470 --> 00:08:42,630
공간은 높은에있는 경우 그래서
시스템에 프리미엄,

194
00:08:42,630 --> 00:08:45,830
트라이의 정보는 다음의 제품에 올바른 방법으로하지 않을 수 있습니다
심지어는 다른 장점이 있지만, 이동

195
00:08:45,830 --> 00:08:47,780
놀이로 제공됩니다.

196
00:08:47,780 --> 00:08:48,710
나는 더그 로이드입니다.

197
00:08:48,710 --> 00:08:50,740
이 CS50입니다.

198
00:08:50,740 --> 00:08:52,316