1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[MUSIC CHƠI]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID Malan: Đây là CS50.

5
00:00:14,010 --> 00:00:18,090
Và đây là cả hai bắt đầu và
end-- như literally-- gần như cuối cùng

6
00:00:18,090 --> 00:00:18,825
tuần sáu.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> Tôi nghĩ rằng tôi muốn chia sẻ một
chút của một thực tế thú vị.

9
00:00:22,640 --> 00:00:25,370
Tôi đã kéo này lên từ một
thiết lập dữ liệu của học kỳ vừa qua.

10
00:00:25,370 --> 00:00:29,710
Bạn có thể nhớ lại rằng chúng tôi yêu cầu bạn trên tất cả các
p thiết lập hình thức nếu bạn đã theo dõi trực tuyến

11
00:00:29,710 --> 00:00:31,580
hoặc nếu bạn đã học trong người.

12
00:00:31,580 --> 00:00:33,020
Và đây là dữ liệu.

13
00:00:33,020 --> 00:00:34,710
Vì vậy, ngày hôm nay là rất nhiều dự đoán được.

14
00:00:34,710 --> 00:00:37,126
Nhưng chúng tôi muốn dành một chút
thời gian với bạn dù sao.

15
00:00:37,126 --> 00:00:40,599
Bất cứ ai muốn phỏng đoán tại sao điều này
đồ thị là để răng cưa, lên xuống, lên xuống,

16
00:00:40,599 --> 00:00:41,265
nên nhất quán không?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
Làm gì mỗi của các đỉnh núi
và đáy đại diện?

19
00:00:45,130 --> 00:00:46,005
>> Đung [không nghe được]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID Malan: Thật vậy.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
Và amusingly hơn, thần cấm,
chúng tôi tổ chức một bài giảng vào ngày thứ sáu

24
00:00:55,480 --> 00:00:58,960
vào đầu học kỳ,
đó là những gì chúng ta thấy xảy ra.

25
00:00:58,960 --> 00:01:03,430
Vì vậy, ngày hôm nay, chúng ta cùng chia sẻ một chút
thêm về cấu trúc dữ liệu.

26
00:01:03,430 --> 00:01:06,660
Và để cung cấp cho bạn nhiều hơn của một chất rắn
mô hình tinh thần cho các vấn đề ở năm,

27
00:01:06,660 --> 00:01:07,450
mà bây giờ ra.

28
00:01:07,450 --> 00:01:10,817
Lỗi chính tả, trong đó, chúng ta sẽ
đưa cho bạn một tập tin văn bản một số 100.000

29
00:01:10,817 --> 00:01:12,650
cộng với từ tiếng Anh, và
bạn sẽ có

30
00:01:12,650 --> 00:01:17,770
để tìm ra cách để khéo léo tải chúng
vào bộ nhớ, vào RAM, sử dụng một số dữ liệu

31
00:01:17,770 --> 00:01:19,330
cấu trúc của sự lựa chọn của bạn.

32
00:01:19,330 --> 00:01:22,470
>> Bây giờ một cấu trúc dữ liệu như vậy có thể
được, nhưng có lẽ không nên,

33
00:01:22,470 --> 00:01:25,630
danh sách liên kết khá đơn giản,
mà chúng tôi giới thiệu thời gian qua.

34
00:01:25,630 --> 00:01:29,220
Và một danh sách liên kết có ít nhất
một lợi thế hơn một mảng.

35
00:01:29,220 --> 00:01:32,096
Một lợi thế của những gì
một danh sách liên kết cho là?

36
00:01:32,096 --> 00:01:32,950
>> Đung Chen.

37
00:01:32,950 --> 00:01:33,908
>> DAVID Malan: Đầu vào.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
Bạn có ý nghĩa gì vậy?

40
00:01:35,196 --> 00:01:37,872
>> Đung Anywhere cùng
danh sách [không nghe được].

41
00:01:37,872 --> 00:01:38,770
>> DAVID Malan: Tốt.

42
00:01:38,770 --> 00:01:42,090
Vì vậy, bạn có thể chèn một phần tử bất cứ nơi nào
bạn muốn ở giữa của danh sách

43
00:01:42,090 --> 00:01:45,490
mà không cần phải xáo trộn bất cứ điều gì,
mà chúng tôi kết luận, trong phân loại của chúng tôi

44
00:01:45,490 --> 00:01:47,630
thảo luận, không phải là
nhất thiết phải là một điều tốt,

45
00:01:47,630 --> 00:01:51,200
bởi vì nó cần có thời gian để thực sự di chuyển
tất cả những con người trái hoặc phải.

46
00:01:51,200 --> 00:01:55,540
Và như vậy với một danh sách liên kết, bạn có thể
chỉ phân bổ với malloc, một nút mới,

47
00:01:55,540 --> 00:01:58,385
và sau đó cập nhật một vài
pointers-- hai, ba hoạt động max--

48
00:01:58,385 --> 00:02:01,480
và chúng tôi có thể khe cắm một người nào đó
ở bất cứ nơi nào vào một danh sách.

49
00:02:01,480 --> 00:02:03,550
>> Những gì người khác là thuận lợi
về một danh sách liên kết?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
Yeah?

52
00:02:05,659 --> 00:02:06,534
>> Đung [không nghe được]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID Malan: Hoàn hảo.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
Perfect.

57
00:02:11,090 --> 00:02:12,070
Nó thực sự năng động.

58
00:02:12,070 --> 00:02:15,100
Và rằng bạn không cam kết,
trước, một số kích thước cố định

59
00:02:15,100 --> 00:02:18,750
đoạn bộ nhớ, như bạn sẽ phải
đến với một mảng, lộn ngược trong đó

60
00:02:18,750 --> 00:02:22,455
là bạn có thể bố trí các nút chỉ trên
do đó nhu cầu sử dụng chỉ như nhiều không gian

61
00:02:22,455 --> 00:02:23,330
khi bạn thực sự cần.

62
00:02:23,330 --> 00:02:26,830
Ngược lại với một mảng, bạn có thể
vô tình chia quá ít.

63
00:02:26,830 --> 00:02:28,871
Và sau đó nó chỉ cần đi
là một cơn đau ở cổ

64
00:02:28,871 --> 00:02:32,440
tái phân bổ một mảng lớn hơn mới, sao chép
tất cả mọi thứ trên, giải phóng mảng cũ,

65
00:02:32,440 --> 00:02:33,990
và sau đó di chuyển về doanh nghiệp của bạn.

66
00:02:33,990 --> 00:02:37,479
Hoặc tệ hơn, bạn có thể phân bổ cách
bộ nhớ nhiều hơn bạn thực sự cần,

67
00:02:37,479 --> 00:02:40,520
và vì vậy bạn sẽ có một rất
dân cư thưa thớt mảng, vậy để nói chuyện.

68
00:02:40,520 --> 00:02:44,350
>> Vì vậy, một danh sách liên kết cung cấp cho bạn những
lợi thế của tính năng động và linh hoạt

69
00:02:44,350 --> 00:02:46,080
với chèn và xóa bỏ.

70
00:02:46,080 --> 00:02:48,000
Nhưng chắc chắn phải có một giá phải trả.

71
00:02:48,000 --> 00:02:50,000
Trong thực tế, một trong những chủ đề
khám phá trên bài kiểm tra không

72
00:02:50,000 --> 00:02:52,430
là một vài thương mại-off
chúng ta đã thấy cho đến nay.

73
00:02:52,430 --> 00:02:56,161
Vì vậy, một giá phải trả hay là những gì
nhược điểm của một danh sách liên kết?

74
00:02:56,161 --> 00:02:56,660
Yeah.

75
00:02:56,660 --> 00:02:57,560
>> ĐỐI TƯỢNG: Không có truy cập ngẫu nhiên.

76
00:02:57,560 --> 00:02:58,809
>> DAVID Malan: Không có truy cập ngẫu nhiên.

77
00:02:58,809 --> 00:02:59,540
Nhưng những người quan tâm?

78
00:02:59,540 --> 00:03:01,546
Truy cập ngẫu nhiên không âm thanh hấp dẫn.

79
00:03:01,546 --> 00:03:02,421
>> Đung [không nghe được]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID Malan: Chính xác.

82
00:03:05,740 --> 00:03:07,580
Nếu bạn muốn có
một algorithm-- nhất định

83
00:03:07,580 --> 00:03:10,170
và cho tôi thực sự đề xuất
tìm kiếm nhị phân đặc biệt, mà

84
00:03:10,170 --> 00:03:12,600
là một trong chúng tôi đã sử dụng khá bit--
nếu bạn không có quyền truy cập ngẫu nhiên,

85
00:03:12,600 --> 00:03:15,516
bạn không thể làm điều đó số học đơn giản
tìm kiếm như các yếu tố trung

86
00:03:15,516 --> 00:03:16,530
và nhảy ngay đến nó.

87
00:03:16,530 --> 00:03:20,239
Thay vào đó bạn phải bắt đầu từ người đầu tiên
yếu tố và tuyến tính tìm kiếm từ bên trái

88
00:03:20,239 --> 00:03:22,780
bên phải nếu bạn muốn tìm
giữa hoặc bất kỳ yếu tố khác.

89
00:03:22,780 --> 00:03:24,410
>> Đung Nó có thể mất nhiều bộ nhớ hơn.

90
00:03:24,410 --> 00:03:25,040
>> DAVID Malan: Đưa bộ nhớ hơn.

91
00:03:25,040 --> 00:03:27,464
Ở đâu mà thêm
chi phí đến từ trong bộ nhớ?

92
00:03:27,464 --> 00:03:28,339
>> Đung [không nghe được]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID Malan: Chính xác.

95
00:03:33,440 --> 00:03:35,679
Trong trường hợp này ở đây, chúng tôi đã có
một danh sách liên kết cho các số nguyên,

96
00:03:35,679 --> 00:03:37,470
nhưng chúng tôi đang tăng gấp đôi
số lượng bộ nhớ

97
00:03:37,470 --> 00:03:39,680
chúng ta cần bởi cũng lưu trữ các con trỏ.

98
00:03:39,680 --> 00:03:42,090
Bây giờ ít hơn của một vấn đề lớn như
cấu trúc của bạn nhận được lớn hơn

99
00:03:42,090 --> 00:03:45,320
và bạn đang lưu trữ không phải là một số nhưng
có thể là một sinh viên hoặc một số đối tượng khác.

100
00:03:45,320 --> 00:03:46,880
Nhưng điểm chắc chắn vẫn còn.

101
00:03:46,880 --> 00:03:49,421
Và do đó, một số hoạt động
trên danh sách liên kết được gọi là

102
00:03:49,421 --> 00:03:50,570
là O lớn của n-- tuyến tính.

103
00:03:50,570 --> 00:03:54,730
Những điều như chèn hoặc tìm kiếm
hoặc xóa trong trường hợp một yếu tố

104
00:03:54,730 --> 00:03:57,720
xảy ra để được vào cuối của
danh sách cho dù nó được sắp xếp hay không.

105
00:03:57,720 --> 00:04:01,167
>> Đôi khi bạn có thể nhận được may mắn và trong
giới hạn rất thấp trên các hoạt động này

106
00:04:01,167 --> 00:04:04,250
cũng có thể là hằng số thời gian nếu bạn
luôn luôn nhìn vào các yếu tố đầu tiên,

107
00:04:04,250 --> 00:04:05,070
ví dụ.

108
00:04:05,070 --> 00:04:09,360
Nhưng cuối cùng, chúng tôi đã hứa
để đạt được Chén thánh

109
00:04:09,360 --> 00:04:12,630
cấu trúc dữ liệu, hoặc
một số trong đó xấp xỉ,

110
00:04:12,630 --> 00:04:14,290
bằng cách hằng số thời gian.

111
00:04:14,290 --> 00:04:17,579
Chúng ta có thể tìm thấy các yếu tố hoặc các yếu tố
hoặc loại bỏ các yếu tố từ một danh sách?

112
00:04:17,579 --> 00:04:19,059
Chúng ta sẽ thấy khá sớm.

113
00:04:19,059 --> 00:04:21,100
Và nó chỉ ra rằng một
các cơ chế chúng tôi

114
00:04:21,100 --> 00:04:23,464
sẽ bắt đầu sử dụng ngày hôm nay,
sử dụng hàng năm trong p thiết lập năm,

115
00:04:23,464 --> 00:04:24,630
thực sự là khá quen thuộc.

116
00:04:24,630 --> 00:04:27,430
Ví dụ, nếu điều này là một bó
sách thi, mỗi trong số đó

117
00:04:27,430 --> 00:04:29,660
có một học sinh đầu tiên
đặt tên và tên cuối cùng trên nó,

118
00:04:29,660 --> 00:04:31,820
và tôi chọn chúng từ
ở phần cuối của một kỳ thi,

119
00:04:31,820 --> 00:04:33,746
và tất cả đều khá
nhiều theo một thứ tự ngẫu nhiên,

120
00:04:33,746 --> 00:04:36,370
và chúng tôi muốn đi về phân loại
các kỳ thi để khi phân loại

121
00:04:36,370 --> 00:04:38,661
nó dễ dàng hơn chỉ là một rất nhiều và
nhanh hơn để giao lại ra

122
00:04:38,661 --> 00:04:40,030
cho học sinh theo thứ tự abc.

123
00:04:40,030 --> 00:04:42,770
Những gì bản năng của bạn sẽ được
cho một đống của các kỳ thi như thế này?

124
00:04:42,770 --> 00:04:45,019
>> Vâng, nếu bạn đang như tôi, bạn
có thể thấy rằng đây là m,

125
00:04:45,019 --> 00:04:48,505
vì vậy tôi sẽ để loại đặt điều này vào,
nếu điều này là bàn của tôi hoặc sàn nhà của tôi, nơi

126
00:04:48,505 --> 00:04:50,650
Tôi đang lan rộng điều
out-- hoặc mảng của tôi really--

127
00:04:50,650 --> 00:04:52,210
Tôi có thể đặt tất cả các bà trong đó.

128
00:04:52,210 --> 00:04:52,710
Oh.

129
00:04:52,710 --> 00:04:55,020
Dưới đây là một A. Vì vậy, tôi có thể
Khi đặt ở đây.

130
00:04:55,020 --> 00:04:55,520
Oh.

131
00:04:55,520 --> 00:04:57,980
Đây là một A. Tôi sẽ
để đưa qua đây.

132
00:04:57,980 --> 00:05:02,490
Dưới đây là một Z. Đây là một M. Và như vậy
Tôi có thể bắt đầu làm cọc như thế này.

133
00:05:02,490 --> 00:05:06,620
Và sau đó có lẽ tôi sẽ đi vào sau
và loại rất nitpicky-ly loại

134
00:05:06,620 --> 00:05:07,710
cọc cá nhân.

135
00:05:07,710 --> 00:05:11,300
Nhưng vấn đề là tôi sẽ xem xét
tại đầu vào rằng tôi là tay

136
00:05:11,300 --> 00:05:14,016
và tôi sẽ làm cho một số tính
quyết định dựa trên đầu vào đó.

137
00:05:14,016 --> 00:05:15,640
Nếu nó bắt đầu với A, đặt nó ở đó.

138
00:05:15,640 --> 00:05:18,980
Nếu nó bắt đầu với Z, đặt nó lên
ở đó, và tất cả mọi thứ ở giữa.

139
00:05:18,980 --> 00:05:22,730
>> Vì vậy, đây là một kỹ thuật đó là
thường được gọi là hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
mà thường có nghĩa là dùng như
đầu vào và sử dụng đầu vào để tính toán

141
00:05:26,550 --> 00:05:30,940
một giá trị, nói chung là một số, và
số là chỉ số vào một lưu trữ

142
00:05:30,940 --> 00:05:32,260
container, giống như một mảng.

143
00:05:32,260 --> 00:05:35,490
Vì vậy, nói cách khác, tôi có thể có một
hàm băm, như tôi đã làm trong đầu tôi,

144
00:05:35,490 --> 00:05:37,940
rằng nếu tôi nhìn thấy một ai đó
Tên người bắt đầu với A,

145
00:05:37,940 --> 00:05:40,190
Tôi sẽ để bản đồ đó
bằng không trong đầu tôi.

146
00:05:40,190 --> 00:05:44,160
Và nếu tôi nhìn thấy một người nào đó với Z, tôi
sẽ bản đồ đó đến 25 trong đầu của tôi

147
00:05:44,160 --> 00:05:46,220
và sau đó đặt điều đó vào
hầu hết đống cuối cùng.

148
00:05:46,220 --> 00:05:50,990
>> Bây giờ, nếu bạn suy nghĩ về không não của tôi
nhưng một chương trình C, những gì con số có thể

149
00:05:50,990 --> 00:05:53,170
bạn dựa vào để đạt được điều đó kết quả tương tự?

150
00:05:53,170 --> 00:05:55,594
Nói cách khác, nếu bạn
có các ký tự ASCII A,

151
00:05:55,594 --> 00:05:57,510
làm thế nào để bạn xác định
những gì xô để đặt nó trong?

152
00:05:57,510 --> 00:05:59,801
Bạn có lẽ không muốn
đặt nó vào thùng 65, mà

153
00:05:59,801 --> 00:06:01,840
sẽ như thế nào trên đó
không có lý do tốt.

154
00:06:01,840 --> 00:06:04,320
Nơi nào bạn muốn đặt A
về giá trị ASCII của nó?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
Nơi nào bạn muốn làm để ASCII của nó
giá trị để đến với một cái xô thông minh hơn

157
00:06:08,920 --> 00:06:09,480
để đặt nó trong?

158
00:06:09,480 --> 00:06:10,206
>> Đung Minus A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID Malan: Yeah.

160
00:06:10,956 --> 00:06:13,190
Vì vậy, trừ A hoặc trừ
đặc biệt 65 nếu nó

161
00:06:13,190 --> 00:06:18,240
A. một vốn Hoặc nếu 98
đó là một chữ thường a.

162
00:06:18,240 --> 00:06:21,300
Và do đó sẽ cho phép chúng ta, rất
đơn giản và rất số học,

163
00:06:21,300 --> 00:06:23,260
đặt một cái gì đó vào một cái xô như thế.

164
00:06:23,260 --> 00:06:26,010
Vì vậy, hóa ra chúng ta thực sự làm
này là tốt ngay cả với các câu đố.

165
00:06:26,010 --> 00:06:29,051
>> Vì vậy, bạn có thể nhớ lại bạn vòng của bạn
Tên giáo viên trên trang bìa.

166
00:06:29,051 --> 00:06:32,270
Và tên của TF đã được tổ chức
vào các cột theo thứ tự abc,

167
00:06:32,270 --> 00:06:34,400
tốt, có tin hay không,
khi tất cả 80 cộng của chúng tôi

168
00:06:34,400 --> 00:06:37,800
đã cùng nhau đêm khác đến lớp,
bước cuối cùng trong quá trình chấm điểm của chúng tôi

169
00:06:37,800 --> 00:06:41,830
là để băm câu đố vào một lớn
không gian của sàn tại [không nghe được]

170
00:06:41,830 --> 00:06:45,110
và đặt các câu đố của tất cả mọi người ra
trong chính xác thứ tự của TF của họ

171
00:06:45,110 --> 00:06:47,700
tên trên trang bìa, vì
sau đó nó dễ dàng hơn rất nhiều cho chúng tôi

172
00:06:47,700 --> 00:06:51,290
để tìm kiếm thông qua đó sử dụng tuyến tính
tìm kiếm hoặc một số loại thông minh

173
00:06:51,290 --> 00:06:54,050
cho một TF để tìm mình hoặc
câu đố học sinh của mình.

174
00:06:54,050 --> 00:06:56,060
>> Vì vậy, ý tưởng này của băm
bạn sẽ thấy là

175
00:06:56,060 --> 00:07:00,520
khá mạnh mẽ thực sự là khá
phổ biến và rất trực quan,

176
00:07:00,520 --> 00:07:03,000
giống như có thể phân chia và
chinh phục là trong tuần không.

177
00:07:03,000 --> 00:07:05,250
Tôi nhanh chóng đến hackathon về phía trước
một vài năm trước đây.

178
00:07:05,250 --> 00:07:08,040
Đây là Zamyla và một vài
sinh viên nhân viên lời chào khác

179
00:07:08,040 --> 00:07:09,030
khi họ bước vào.

180
00:07:09,030 --> 00:07:12,680
Và chúng tôi đã có một bó toàn bộ gấp
bảng đó với thẻ tên.

181
00:07:12,680 --> 00:07:15,380
Và chúng tôi đã có những thẻ tên tổ chức
với giống như Như trên đó

182
00:07:15,380 --> 00:07:16,690
và Zs ở đó.

183
00:07:16,690 --> 00:07:20,350
Và vì vậy một trong những TFs rất khéo léo
đã viết này như hướng dẫn

184
00:07:20,350 --> 00:07:21,030
trong ngày.

185
00:07:21,030 --> 00:07:24,480
Và trong tuần 12 của học kỳ này
tất cả các ý nghĩa hoàn hảo và tất cả mọi người

186
00:07:24,480 --> 00:07:25,310
biết phải làm gì.

187
00:07:25,310 --> 00:07:27,900
Nhưng bất cứ lúc nào bạn đã
xếp hàng trong cùng một cách,

188
00:07:27,900 --> 00:07:30,272
bạn đang thực hiện
cùng một khái niệm về một băm.

189
00:07:30,272 --> 00:07:31,730
Vì vậy, hãy chính thức hóa nó một chút.

190
00:07:31,730 --> 00:07:32,890
Dưới đây là một mảng.

191
00:07:32,890 --> 00:07:36,820
Nó rút ra được một chút
rộng chỉ để miêu tả, trực quan,

192
00:07:36,820 --> 00:07:38,920
chúng ta có thể đưa dây
trong một cái gì đó như thế này.

193
00:07:38,920 --> 00:07:41,970
Và mảng này là
rõ ràng của tổng kích thước 26.

194
00:07:41,970 --> 00:07:43,935
Và điều được gọi là
bảng tùy tiện.

195
00:07:43,935 --> 00:07:48,930
Nhưng điều này chỉ là màn biểu diễn của một nghệ sĩ
những gì một bảng băm có thể được.

196
00:07:48,930 --> 00:07:52,799
>> Vì vậy, một bảng băm bây giờ sẽ
là một cấu trúc dữ liệu cấp độ cao hơn.

197
00:07:52,799 --> 00:07:54,840
Vào cuối ngày
chúng tôi về để thấy rằng bạn

198
00:07:54,840 --> 00:07:58,700
có thể thực hiện một bảng băm, mà
là giống như các dòng check-in

199
00:07:58,700 --> 00:08:02,059
tại một hackathon nhiều như thế này
bảng được sử dụng để phân loại sách thi.

200
00:08:02,059 --> 00:08:03,850
Nhưng một bảng băm là
loại cao cấp này

201
00:08:03,850 --> 00:08:08,250
khái niệm mà có thể sử dụng một mảng
bên dưới mui xe để thực hiện nó,

202
00:08:08,250 --> 00:08:11,890
hoặc nó có thể sử dụng một danh sách dài, hoặc thậm chí
có lẽ một số cấu trúc dữ liệu khác.

203
00:08:11,890 --> 00:08:15,590
Và bây giờ đó là việc lấy theme--
một số trong những thành phần cơ bản

204
00:08:15,590 --> 00:08:18,310
giống như một mảng và tòa nhà này
ngăn chặn hiện nay của một danh sách dài

205
00:08:18,310 --> 00:08:21,740
và nhìn thấy những gì khác chúng ta có thể xây dựng
trên đầu trang của những người, như thành phần

206
00:08:21,740 --> 00:08:26,550
vào một công thức, làm cho ngày càng nhiều
kết quả cuối cùng thú vị và hữu ích.

207
00:08:26,550 --> 00:08:28,680
>> Vì vậy, với bảng băm
chúng ta có thể thực hiện nó

208
00:08:28,680 --> 00:08:32,540
trong bộ nhớ những bức tranh như thế này, nhưng
làm thế nào có thể nó thực sự được mã hóa lên?

209
00:08:32,540 --> 00:08:33,789
Vâng, có lẽ là chỉ đơn giản là thế này.

210
00:08:33,789 --> 00:08:38,270
Nếu NĂNG LỰC trong tất cả các mũ, chỉ là
một số constant-- ví dụ 26,

211
00:08:38,270 --> 00:08:42,030
26 chữ cái của alphabet--
Tôi có thể gọi là bảng biến của tôi,

212
00:08:42,030 --> 00:08:45,630
và tôi có thể khẳng định rằng tôi sẽ
đặt sao char trong đó, hoặc chuỗi.

213
00:08:45,630 --> 00:08:49,880
Vì vậy, nó đơn giản như này nếu bạn
muốn thực hiện một bảng băm.

214
00:08:49,880 --> 00:08:51,490
Tuy nhiên, điều này thực sự chỉ là một mảng.

215
00:08:51,490 --> 00:08:53,198
Nhưng một lần nữa, một băm
bảng tại là những gì chúng tôi sẽ

216
00:08:53,198 --> 00:08:57,470
gọi một kiểu dữ liệu trừu tượng mà chỉ
sắp xếp của một lớp khái niệm trên

217
00:08:57,470 --> 00:09:00,780
của một cái gì đó trần tục hơn
hiện nay giống như một mảng.

218
00:09:00,780 --> 00:09:02,960
>> Bây giờ, làm thế nào chúng ta đi
về việc giải quyết vấn đề?

219
00:09:02,960 --> 00:09:06,980
Vâng, trước đó tôi đã có sự sang trọng
của việc có đủ không gian bảng ở đây

220
00:09:06,980 --> 00:09:09,460
để tôi có thể đặt
câu đố bất cứ nơi nào tôi muốn.

221
00:09:09,460 --> 00:09:10,620
Vì vậy, Như có thể đi đây.

222
00:09:10,620 --> 00:09:12,100
Zs có thể đi đây.

223
00:09:12,100 --> 00:09:13,230
Bà có thể đi đây.

224
00:09:13,230 --> 00:09:14,740
Và sau đó tôi đã có một số không gian thêm.

225
00:09:14,740 --> 00:09:18,740
Nhưng đây là một chút của một cheat đúng
bây giờ bởi vì bảng này, nếu tôi thực sự

226
00:09:18,740 --> 00:09:22,720
nghĩ về nó như một mảng, chỉ cần là
sẽ có một số kích thước cố định.

227
00:09:22,720 --> 00:09:25,380
>> Vì vậy, về mặt kỹ thuật, nếu tôi kéo
lên bài kiểm tra của học sinh khác

228
00:09:25,380 --> 00:09:28,490
và xem, oh, người này
tên bắt đầu bằng A cũng vậy,

229
00:09:28,490 --> 00:09:30,980
Tôi loại muốn đặt nó ở đó.

230
00:09:30,980 --> 00:09:34,740
Nhưng ngay sau khi tôi đặt nó ở đó, nếu
bảng này thực sự đại diện cho một mảng,

231
00:09:34,740 --> 00:09:37,840
Tôi sẽ được trọng hoặc clobbering
ai đố của học sinh này là.

232
00:09:37,840 --> 00:09:38,340
Phải không?

233
00:09:38,340 --> 00:09:41,972
Nếu đây là một mảng, chỉ có một điều có thể
đi trong mỗi tế bào hoặc các yếu tố.

234
00:09:41,972 --> 00:09:43,680
Và vì vậy tôi loại có
chọn và chọn.

235
00:09:43,680 --> 00:09:45,735
>> Bây giờ trước đó tôi loại
lừa dối và đã làm điều này hay tôi

236
00:09:45,735 --> 00:09:47,526
chỉ cần loại xếp chồng lên nhau
họ trên mỗi khác.

237
00:09:47,526 --> 00:09:49,170
Nhưng đó không phải đi để bay trong mã.

238
00:09:49,170 --> 00:09:52,260
Vì vậy, nơi tôi có thể đặt
sinh viên thứ hai có tên

239
00:09:52,260 --> 00:09:54,964
Một là nếu tất cả tôi đã có được này
không gian bảng có sẵn?

240
00:09:54,964 --> 00:09:57,880
Và tôi đã sử dụng ba khe cắm và nó
có vẻ như đó chỉ là một vài người khác.

241
00:09:57,880 --> 00:09:58,959
Bạn có thể làm gì?

242
00:09:58,959 --> 00:09:59,834
Đung [không nghe được]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID Malan: Yeah.

245
00:10:01,315 --> 00:10:02,370
Có lẽ chúng ta hãy giữ nó đơn giản.

246
00:10:02,370 --> 00:10:02,660
Phải không?

247
00:10:02,660 --> 00:10:04,243
Nó không phù hợp với nơi tôi muốn đặt nó.

248
00:10:04,243 --> 00:10:07,450
Vì vậy, tôi sẽ đặt nó
về mặt kỹ thuật mà một B sẽ đi.

249
00:10:07,450 --> 00:10:09,932
Bây giờ, tất nhiên, tôi bắt đầu
vẽ bản thân mình vào một góc.

250
00:10:09,932 --> 00:10:11,890
Nếu tôi nhận được cho một học sinh
có tên thực sự là B,

251
00:10:11,890 --> 00:10:14,840
doanh nghiệp B sẽ được di chuyển một chút
về phía trước, như có thể xảy ra, vâng,

252
00:10:14,840 --> 00:10:17,530
nếu điều này là một B, bây giờ nó có để đi đây.

253
00:10:17,530 --> 00:10:20,180
>> Và vì vậy điều này rất nhanh chóng
có thể trở thành vấn đề,

254
00:10:20,180 --> 00:10:23,850
nhưng đó là một kỹ thuật mà thực sự
được gọi là tuyến tính thăm dò,

255
00:10:23,850 --> 00:10:26,650
nhờ đó mà bạn chỉ xem xét của bạn
mảng là dọc theo đường.

256
00:10:26,650 --> 00:10:29,680
Và bạn chỉ cần loại thăm dò hoặc
kiểm tra từng yếu tố có sẵn

257
00:10:29,680 --> 00:10:31,360
tìm kiếm một vị trí có sẵn.

258
00:10:31,360 --> 00:10:34,010
Và ngay khi bạn tìm thấy
một, bạn thả nó ở đó.

259
00:10:34,010 --> 00:10:38,390
>> Bây giờ, giá được trả tiền ngay
cho giải pháp này là gì?

260
00:10:38,390 --> 00:10:41,300
Chúng tôi có một mảng kích thước cố định,
và khi tôi chèn tên

261
00:10:41,300 --> 00:10:44,059
vào nó, ít nhất ban đầu, những gì
thời gian chạy của chèn

262
00:10:44,059 --> 00:10:46,350
để đưa các sinh viên '
câu đố trong xô phải không?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
Big O của những gì?

265
00:10:50,002 --> 00:10:51,147
>> Đung n.

266
00:10:51,147 --> 00:10:52,480
DAVID Malan: Tôi nghe nói O lớn của n.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
Không đúng sự thật.

269
00:10:54,300 --> 00:10:56,490
Nhưng chúng tôi sẽ trêu chọc nhau
tại sao chỉ trong một khoảnh khắc.

270
00:10:56,490 --> 00:10:57,702
Những gì khác nó có thể được?

271
00:10:57,702 --> 00:10:58,755
>> Đung [không nghe được]

272
00:10:58,755 --> 00:11:00,380
DAVID Malan: Và hãy để tôi làm điều đó trực quan.

273
00:11:00,380 --> 00:11:04,720
Vì vậy, giả sử đây là thư S.

274
00:11:04,720 --> 00:11:05,604
>> Đung Đó là một.

275
00:11:05,604 --> 00:11:06,520
DAVID Malan: Đó là một.

276
00:11:06,520 --> 00:11:06,710
Phải không?

277
00:11:06,710 --> 00:11:08,950
Đây là một mảng, mà
nghĩa là chúng ta có thể truy cập ngẫu nhiên.

278
00:11:08,950 --> 00:11:11,790
Và nếu chúng ta nghĩ về điều này
như bằng không và điều này là 25,

279
00:11:11,790 --> 00:11:13,800
và chúng tôi nhận ra rằng,
oh, đây là đầu vào S của tôi,

280
00:11:13,800 --> 00:11:16,350
Tôi chắc chắn có thể chuyển đổi
S, một ký tự ASCII,

281
00:11:16,350 --> 00:11:18,540
một số tương ứng
giữa số không và 25

282
00:11:18,540 --> 00:11:20,910
và sau đó ngay lập tức
đặt nó nơi mà nó thuộc về.

283
00:11:20,910 --> 00:11:26,120
>> Nhưng tất nhiên, ngay sau khi tôi nhận được đến
người thứ hai là người tên là A hoặc B hoặc C

284
00:11:26,120 --> 00:11:29,300
cuối cùng, nếu tôi đã sử dụng
tuyến tính thăm dò là giải pháp của tôi,

285
00:11:29,300 --> 00:11:31,360
thời gian chạy của
chèn trong trường hợp xấu nhất

286
00:11:31,360 --> 00:11:33,120
thực sự là sẽ giao phận sự vào những gì?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
Và tôi đã nghe nó ở đây
một cách chính xác ngay từ đầu.

289
00:11:36,045 --> 00:11:36,920
Đung [không nghe được]

290
00:11:36,920 --> 00:11:41,620
DAVID Malan: Vì vậy, nó là n thực sự một lần
bạn có một bộ dữ liệu đủ lớn.

291
00:11:41,620 --> 00:11:44,410
Vì vậy, một mặt, nếu
mảng của bạn là đủ lớn

292
00:11:44,410 --> 00:11:48,287
và dữ liệu của bạn là thưa thớt đủ, bạn
có được thời gian này liên tục đẹp.

293
00:11:48,287 --> 00:11:50,620
Nhưng ngay khi bạn bắt đầu
nhận được nhiều hơn và nhiều hơn nữa các yếu tố,

294
00:11:50,620 --> 00:11:53,200
và chỉ thống kê bạn nhận được
nhiều người bằng chữ

295
00:11:53,200 --> 00:11:56,030
Một khi tên của họ hoặc các thư
B, nó có thể có khả năng

296
00:11:56,030 --> 00:11:57,900
giao phận sự vào một cái gì đó nhiều hơn tuyến tính.

297
00:11:57,900 --> 00:11:59,640
Vì vậy, không hoàn toàn hoàn hảo.

298
00:11:59,640 --> 00:12:00,690
Vì vậy, chúng ta có thể làm tốt hơn?

299
00:12:00,690 --> 00:12:03,210
>> Vâng, là những gì chúng tôi
giải pháp trước khi chúng tôi

300
00:12:03,210 --> 00:12:06,820
muốn có sự năng động hơn
một cái gì đó giống như một mảng cho phép?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
Đung [không nghe được]

303
00:12:08,960 --> 00:12:10,030
DAVID Malan: chúng tôi đã giới thiệu gì?

304
00:12:10,030 --> 00:12:10,530
Yeah.

305
00:12:10,530 --> 00:12:11,430
Vì vậy, một danh sách liên kết.

306
00:12:11,430 --> 00:12:14,430
Vâng, chúng ta hãy xem những gì một liên kết
danh sách có thể làm cho chúng ta thay thế.

307
00:12:14,430 --> 00:12:17,630
Vâng, hãy để tôi đề xuất rằng chúng ta
rút ra những hình ảnh như sau.

308
00:12:17,630 --> 00:12:19,620
Bây giờ đây là một khác nhau
hình ảnh từ một ví dụ

309
00:12:19,620 --> 00:12:24,750
từ một văn bản khác nhau, trên thực tế, rằng
thực sự là sử dụng một mảng có kích thước 31.

310
00:12:24,750 --> 00:12:28,220
Và tác giả này chỉ đơn giản
quyết định băm dây

311
00:12:28,220 --> 00:12:32,430
không dựa trên tên của người đó,
nhưng dựa trên ngày sinh của họ.

312
00:12:32,430 --> 00:12:35,680
Không phân biệt của tháng, họ đã hình
nếu bạn sinh vào ngày đầu tiên của một tháng

313
00:12:35,680 --> 00:12:39,580
hoặc ngày 31 của một tháng, tác giả
sẽ băm dựa trên giá trị đó,

314
00:12:39,580 --> 00:12:44,154
để truyền bá tên ra một chút
nhiều hơn chỉ là 26 điểm có thể cho phép.

315
00:12:44,154 --> 00:12:47,320
Và có lẽ đó là một chút đồng đều hơn
vì đi với các chữ cái chữ cái,

316
00:12:47,320 --> 00:12:50,236
bởi vì tất nhiên có lẽ
nhiều người trên thế giới với tên

317
00:12:50,236 --> 00:12:54,020
mà bắt đầu với A hơn là chắc chắn
một số chữ cái khác của bảng chữ cái.

318
00:12:54,020 --> 00:12:56,380
Vì vậy, có lẽ đây là một chút
nhiều đồng phục, giả sử

319
00:12:56,380 --> 00:12:58,640
một phân bố đều
của trẻ sơ sinh qua một tháng.

320
00:12:58,640 --> 00:12:59,990
>> Nhưng, tất nhiên, điều này vẫn không hoàn hảo.

321
00:12:59,990 --> 00:13:00,370
Phải không?

322
00:13:00,370 --> 00:13:01,370
Chúng tôi đang có va chạm.

323
00:13:01,370 --> 00:13:04,680
Nhiều người trong này
cấu trúc dữ liệu vẫn còn

324
00:13:04,680 --> 00:13:08,432
có ngày sinh cùng ít nhất
bạn không phân biệt tháng.

325
00:13:08,432 --> 00:13:09,640
Nhưng những gì tác giả đã thực hiện?

326
00:13:09,640 --> 00:13:13,427
Vâng, có vẻ như chúng ta có một mảng
ở phía bên tay trái rút ra theo chiều dọc,

327
00:13:13,427 --> 00:13:15,010
nhưng đó chỉ là màn biểu diễn của một nghệ sĩ.

328
00:13:15,010 --> 00:13:18,009
Nó không quan trọng những gì hướng bạn
vẽ một mảng, nó vẫn là một mảng.

329
00:13:18,009 --> 00:13:20,225
Đây là những gì một mảng rõ ràng?

330
00:13:20,225 --> 00:13:21,500
>> Đung danh sách liên kết.

331
00:13:21,500 --> 00:13:21,650
>> DAVID Malan: Yeah.

332
00:13:21,650 --> 00:13:23,490
Có vẻ như nó là một
mảng các danh sách liên kết.

333
00:13:23,490 --> 00:13:26,490
Vì vậy, một lần nữa, đến thời điểm này của loại
của việc sử dụng các cấu trúc dữ liệu doanh nghiệp

334
00:13:26,490 --> 00:13:28,550
như thành phần để hơn
giải pháp thú vị,

335
00:13:28,550 --> 00:13:30,862
bạn hoàn toàn có thể mất một
cơ bản, giống như một mảng,

336
00:13:30,862 --> 00:13:33,320
và sau đó đi một cái gì đó nhiều hơn
thú vị giống như một danh sách liên kết

337
00:13:33,320 --> 00:13:36,660
và thậm chí kết hợp chúng thành một thậm chí
cấu trúc dữ liệu thú vị hơn.

338
00:13:36,660 --> 00:13:39,630
Và quả thực, điều này cũng sẽ
được gọi là một bảng băm,

339
00:13:39,630 --> 00:13:42,610
trong đó mảng là
thực sự là bảng băm,

340
00:13:42,610 --> 00:13:45,600
nhưng mà bảng băm có
dây chuyền, có thể nói,

341
00:13:45,600 --> 00:13:50,220
có thể phát triển hoặc thu nhỏ dựa trên
số yếu tố mà bạn muốn chèn.

342
00:13:50,220 --> 00:13:52,990
>> Bây giờ, theo đó, những gì
thời gian chạy ngay bây giờ?

343
00:13:52,990 --> 00:13:58,030
Nếu tôi muốn chèn một người nào đó
có sinh nhật là ngày 31 tháng 10,

344
00:13:58,030 --> 00:13:59,040
nơi nào họ đi đâu?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
Được rồi.

347
00:14:01,030 --> 00:14:02,819
Ở dưới cùng, nơi nó nói 31.

348
00:14:02,819 --> 00:14:03,610
Và đó là hoàn hảo.

349
00:14:03,610 --> 00:14:05,060
Đó là thời gian liên tục.

350
00:14:05,060 --> 00:14:08,760
Nhưng nếu chúng ta tìm thấy một người nào khác
có ngày sinh nhật được, chúng ta hãy xem,

351
00:14:08,760 --> 00:14:10,950
Tháng mười, tháng mười một, 31 tháng 12?

352
00:14:10,950 --> 00:14:12,790
Ở đâu anh ta hoặc cô sẽ đi đâu?

353
00:14:12,790 --> 00:14:13,290
Cùng một điều.

354
00:14:13,290 --> 00:14:13,970
Hai bước mặc dù.

355
00:14:13,970 --> 00:14:15,303
Đó là không đổi mặc dù không phải là nó?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
Được rồi.

358
00:14:16,860 --> 00:14:17,840
Tại thời điểm này nó là.

359
00:14:17,840 --> 00:14:20,570
Nhưng trong trường hợp chung,
càng có nhiều người chúng ta thêm,

360
00:14:20,570 --> 00:14:23,790
xác suất, chúng ta sẽ
để có được càng nhiều va chạm.

361
00:14:23,790 --> 00:14:26,820
>> Bây giờ đây là một chút
tốt hơn bởi vì về mặt kỹ thuật

362
00:14:26,820 --> 00:14:34,580
Hiện tại chuỗi của tôi có thể là trong
trường hợp xấu nhất bao lâu?

363
00:14:34,580 --> 00:14:38,890
Nếu tôi chèn n người vào hơn này
cấu trúc dữ liệu phức tạp, n người,

364
00:14:38,890 --> 00:14:41,080
trong trường hợp xấu nhất nó sẽ là n.

365
00:14:41,080 --> 00:14:41,815
Tại sao?

366
00:14:41,815 --> 00:14:43,332
>> Đung Bởi vì nếu tất cả mọi người
có cùng ngày sinh,

367
00:14:43,332 --> 00:14:44,545
họ sẽ có một dòng.

368
00:14:44,545 --> 00:14:45,420
DAVID Malan: Hoàn hảo.

369
00:14:45,420 --> 00:14:47,480
Nó có thể là một chút giả tạo,
nhưng thật sự trong trường hợp xấu nhất,

370
00:14:47,480 --> 00:14:50,117
nếu tất cả mọi người có cùng ngày sinh,
cho đầu vào bạn có,

371
00:14:50,117 --> 00:14:51,950
bạn sẽ có một
chuỗi dài ồ ạt.

372
00:14:51,950 --> 00:14:54,241
Và như vậy, bạn có thể gọi nó là một
băm bảng, nhưng thực sự nó

373
00:14:54,241 --> 00:14:56,810
chỉ là một danh sách liên kết lớn với
một toàn bộ rất nhiều không gian lãng phí.

374
00:14:56,810 --> 00:15:00,460
Nhưng nói chung, nếu chúng ta giả định rằng
ít nhất là sinh nhật uniform--

375
00:15:00,460 --> 00:15:01,750
và nó có lẽ không phải là.

376
00:15:01,750 --> 00:15:02,587
Tôi đang làm mà lên.

377
00:15:02,587 --> 00:15:04,420
Nhưng nếu chúng ta giả định, cho
vì lợi ích của thảo luận

378
00:15:04,420 --> 00:15:07,717
mà họ đang có, thì theo lý thuyết, nếu
đây là đại diện dọc

379
00:15:07,717 --> 00:15:11,050
của mảng, cũng sau đó hy vọng bạn
sẽ nhận được chuỗi đó là, bạn biết đấy,

380
00:15:11,050 --> 00:15:15,880
khoảng chiều dài tương tự mà mỗi
những đại diện cho một ngày trong tháng.

381
00:15:15,880 --> 00:15:19,930
>> Bây giờ nếu có 31 ngày trong tháng,
đó có nghĩa là thời gian chạy của tôi thực sự

382
00:15:19,930 --> 00:15:25,230
là O lớn của n hơn 31, mà
cảm thấy tốt hơn so với tuyến tính.

383
00:15:25,230 --> 00:15:27,950
Tuy nhiên, là một trong những gì của chúng tôi
cam kết một vài tuần

384
00:15:27,950 --> 00:15:31,145
trước bất cứ khi nào nó đến để bày tỏ
thời gian chạy của một thuật toán?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
Chỉ cần chỉ nhìn vào hạn trật tự cao.

387
00:15:35,190 --> 00:15:35,690
Phải không?

388
00:15:35,690 --> 00:15:37,400
31 chắc chắn là hữu ích.

389
00:15:37,400 --> 00:15:39,610
Nhưng điều này vẫn là O lớn của n.

390
00:15:39,610 --> 00:15:41,730
Nhưng một trong những chủ đề
các vấn đề thiết lập năm

391
00:15:41,730 --> 00:15:43,950
là có được để
thừa nhận rằng hoàn toàn,

392
00:15:43,950 --> 00:15:47,320
tiệm, về mặt lý thuyết
cấu trúc dữ liệu này

393
00:15:47,320 --> 00:15:50,470
là không tốt hơn so với chỉ
một danh sách liên kết lớn.

394
00:15:50,470 --> 00:15:53,550
Và quả thực, trong trường hợp xấu nhất, điều này
bảng băm có thể giao phận sự vào đó.

395
00:15:53,550 --> 00:15:57,620
>> Nhưng trong thế giới thực, với con người chúng ta
rằng máy Mac của riêng hoặc máy tính hoặc bất cứ điều gì

396
00:15:57,620 --> 00:16:01,240
và đang chạy thế giới thực
phần mềm trên dữ liệu thế giới thực,

397
00:16:01,240 --> 00:16:03,260
mà thuật toán thì bạn sẽ thích?

398
00:16:03,260 --> 00:16:09,180
Một trong đó thực hiện các bước cuối cùng hoặc các
một trong những mất n chia cho 31 bước

399
00:16:09,180 --> 00:16:12,900
để tìm thấy một số mảnh của dữ liệu hoặc
để tìm kiếm một số thông tin?

400
00:16:12,900 --> 00:16:16,580
Ý tôi là, hoàn toàn làm cho 31
một sự khác biệt trong thế giới thực.

401
00:16:16,580 --> 00:16:18,540
Nó là nhanh hơn 31 lần.

402
00:16:18,540 --> 00:16:20,880
Và con người chúng ta là chắc chắn
sẽ đánh giá cao điều đó.

403
00:16:20,880 --> 00:16:23,004
>> Vì vậy, nhận ra sự phân đôi
có giữa thực

404
00:16:23,004 --> 00:16:25,920
nói về những điều lý thuyết
và tiệm cận mà chắc chắn

405
00:16:25,920 --> 00:16:28,760
có giá trị như chúng ta đã thấy,
nhưng trong thế giới thực,

406
00:16:28,760 --> 00:16:32,930
nếu bạn quan tâm đến chỉ làm cho
hạnh phúc của con người cho đầu vào nói chung,

407
00:16:32,930 --> 00:16:36,010
bạn rất có thể muốn chấp nhận
thực tế là, có, đây là tuyến tính,

408
00:16:36,010 --> 00:16:38,360
nhưng nó nhanh hơn 31 lần
hơn tuyến tính có thể được.

409
00:16:38,360 --> 00:16:41,610
Và tốt hơn, chúng tôi không chỉ phải
làm điều gì đó tùy ý giống như một ngày sinh,

410
00:16:41,610 --> 00:16:44,030
chúng tôi có thể dành một chút
nhiều thời gian hơn và thông minh

411
00:16:44,030 --> 00:16:47,140
và suy nghĩ về những gì chúng ta có thể làm,
đưa ra tên của một người và có thể

412
00:16:47,140 --> 00:16:50,130
ngày sinh của họ để kết hợp những
thành phần để tìm ra một cái gì đó

413
00:16:50,130 --> 00:16:52,720
mà thực sự hơn là
thống nhất và ít răng cưa,

414
00:16:52,720 --> 00:16:56,250
vậy để nói chuyện hơn hình ảnh này
hiện cho thấy nó có thể được.

415
00:16:56,250 --> 00:16:57,750
Làm thế nào chúng ta có thể thực hiện điều này trong mã?

416
00:16:57,750 --> 00:17:00,280
Vâng, hãy để tôi đề xuất rằng chúng ta
chỉ mượn một số cú pháp chúng tôi đã

417
00:17:00,280 --> 00:17:01,799
sử dụng một vài lần cho đến nay.

418
00:17:01,799 --> 00:17:03,590
Và tôi sẽ xác định
một nút, mà lại

419
00:17:03,590 --> 00:17:06,812
là một thuật ngữ chung chỉ một số
container cho một số cấu trúc dữ liệu.

420
00:17:06,812 --> 00:17:09,020
Tôi sẽ đề nghị
một chuỗi sẽ ở đó.

421
00:17:09,020 --> 00:17:11,369
Nhưng chúng ta sẽ bắt đầu tham gia
đào tạo những bánh xe ra bây giờ.

422
00:17:11,369 --> 00:17:13,230
>> Không có thêm thư viện CS50
thực sự, trừ khi bạn muốn

423
00:17:13,230 --> 00:17:15,230
sử dụng nó cho cuối cùng của bạn
dự án, đó là tốt,

424
00:17:15,230 --> 00:17:18,569
nhưng bây giờ chúng ta sẽ kéo lại
rèm và nói rằng nó chỉ là một ngôi sao char.

425
00:17:18,569 --> 00:17:22,069
Vì vậy, từ đó là có được
tên của người trong câu hỏi.

426
00:17:22,069 --> 00:17:25,079
Và bây giờ tôi có một liên kết
ở đây đến nút tiếp theo

427
00:17:25,079 --> 00:17:28,170
do đó, các đại diện
mỗi nút

428
00:17:28,170 --> 00:17:30,950
trong chuỗi, có khả năng,
của một danh sách liên kết.

429
00:17:30,950 --> 00:17:34,090
>> Và bây giờ làm thế nào để khai báo
bảng băm chính nó?

430
00:17:34,090 --> 00:17:36,660
Làm thế nào để khai báo toàn bộ cấu trúc này?

431
00:17:36,660 --> 00:17:40,960
Vâng, thực sự, giống như tôi đã sử dụng một con trỏ
để chỉ phần tử đầu tiên của danh sách

432
00:17:40,960 --> 00:17:44,510
trước đó, tương tự như tôi có thể chỉ cần nói
Tôi chỉ cần một bó của con trỏ

433
00:17:44,510 --> 00:17:46,270
để thực hiện toàn bộ bảng băm này.

434
00:17:46,270 --> 00:17:49,484
Tôi sẽ có một mảng
gọi là bảng cho bảng băm.

435
00:17:49,484 --> 00:17:50,900
Nó sẽ là khả năng kích thước.

436
00:17:50,900 --> 00:17:52,525
Đó là cách nhiều yếu tố có thể phù hợp với nó.

437
00:17:52,525 --> 00:17:56,180
Và mỗi người trong số những yếu tố này trong
mảng là có được một ngôi sao nút.

438
00:17:56,180 --> 00:17:56,810
Tại sao?

439
00:17:56,810 --> 00:18:00,160
Vâng, mỗi bức tranh này, những gì tôi
thực hiện bảng băm như

440
00:18:00,160 --> 00:18:04,330
hiệu quả trong đầu chỉ là
mảng này mà chúng tôi đã rút ra theo chiều dọc,

441
00:18:04,330 --> 00:18:06,820
mỗi người có hình vuông
đại diện cho một con trỏ.

442
00:18:06,820 --> 00:18:09,170
Đó là những người có dấu gạch chéo
thông qua họ chỉ là null.

443
00:18:09,170 --> 00:18:11,410
Và những người có
mũi tên đi bên phải

444
00:18:11,410 --> 00:18:16,140
là con trỏ thực tế để hạch thực tế,
vậy thì sự bắt đầu của một danh sách liên kết.

445
00:18:16,140 --> 00:18:19,050
>> Vì vậy, ở đây, sau đó là làm thế nào chúng ta có thể
thực hiện một bảng băm

446
00:18:19,050 --> 00:18:21,580
thực hiện xâu chuỗi riêng biệt.

447
00:18:21,580 --> 00:18:22,840
Bây giờ chúng ta có thể làm tốt hơn?

448
00:18:22,840 --> 00:18:25,632
Tất cả các bên phải tôi hứa lần cuối cùng
chúng ta có thể đạt được thời gian liên tục.

449
00:18:25,632 --> 00:18:27,381
Và tôi loại cho bạn
hằng số thời gian ở đây,

450
00:18:27,381 --> 00:18:29,850
nhưng sau đó cho biết không thực sự
thời gian cố định vì nó vẫn còn

451
00:18:29,850 --> 00:18:31,890
phụ thuộc vào tổng số
số yếu tố

452
00:18:31,890 --> 00:18:34,500
bạn đang nhập vào
cấu trúc dữ liệu.

453
00:18:34,500 --> 00:18:35,980
Nhưng giả sử chúng ta đã làm điều này.

454
00:18:35,980 --> 00:18:39,550
Hãy để tôi quay trở lại màn hình ở đây.

455
00:18:39,550 --> 00:18:44,520
Hãy để tôi cũng dự án này lên đây, rõ ràng
màn hình, và cho rằng tôi đã làm điều này.

456
00:18:44,520 --> 00:18:49,300
Giả sử tôi muốn chèn tên
Daven trong vào cấu trúc dữ liệu của tôi.

457
00:18:49,300 --> 00:18:52,100
>> Vì vậy, tôi muốn chèn một chuỗi
Daven vào cấu trúc dữ liệu.

458
00:18:52,100 --> 00:18:54,370
Nếu tôi không sử dụng một
băm bảng, nhưng tôi sử dụng

459
00:18:54,370 --> 00:18:56,980
một cái gì đó nhiều hơn cây giống
giống như một cây gia đình, nơi

460
00:18:56,980 --> 00:18:59,670
bạn có một số gốc tại
đầu và sau đó các nút và lá

461
00:18:59,670 --> 00:19:01,440
mà đi xuống và ra ngoài.

462
00:19:01,440 --> 00:19:04,450
Giả sử sau đó, tôi thấy
muốn chèn Daven của

463
00:19:04,450 --> 00:19:06,430
vào những gì hiện một danh sách trống.

464
00:19:06,430 --> 00:19:09,780
Tôi sẽ làm như sau: Tôi
sẽ tạo ra một nút trong gia đình này

465
00:19:09,780 --> 00:19:15,170
cây giống như cấu trúc dữ liệu giống
một chút như thế này, mỗi trong số đó

466
00:19:15,170 --> 00:19:19,640
hình chữ nhật đã, chúng ta hãy nói,
bây giờ 26 yếu tố trong đó.

467
00:19:19,640 --> 00:19:21,650
Và mỗi người trong các tế bào
trong mảng này sẽ

468
00:19:21,650 --> 00:19:23,470
đại diện cho các thư của một bảng chữ cái.

469
00:19:23,470 --> 00:19:28,190
>> Cụ thể, tôi sẽ đối xử
đây là A, sau đó B, sau đó C, sau đó D,

470
00:19:28,190 --> 00:19:29,310
này ở đây.

471
00:19:29,310 --> 00:19:32,940
Vì vậy, điều này là có hiệu quả
biểu diễn chữ D.

472
00:19:32,940 --> 00:19:36,040
Nhưng để chèn tất cả các Daven của
tên tôi cần phải làm nhiều hơn một chút.

473
00:19:36,040 --> 00:19:37,840
Vì vậy, tôi đầu tiên sẽ băm, vậy để nói chuyện.

474
00:19:37,840 --> 00:19:41,049
Tôi sẽ nhìn vào các chữ cái đầu tiên
trong của Daven mà rõ ràng là một D,

475
00:19:41,049 --> 00:19:42,840
và tôi sẽ phải phân bổ
một nút trông

476
00:19:42,840 --> 00:19:45,570
this-- như một hình chữ nhật lớn lớn
đủ để phù hợp với toàn bộ bảng chữ cái.

477
00:19:45,570 --> 00:19:47,140
>> Bây giờ D được thực hiện.

478
00:19:47,140 --> 00:19:49,720
Bây giờ A. D-A-V-E-N là mục tiêu.

479
00:19:49,720 --> 00:19:51,220
Vì vậy, bây giờ những gì tôi sẽ làm được điều này.

480
00:19:51,220 --> 00:19:54,027
Ngay sau khi tôi bắt đầu thông báo D
không có con trỏ ở đó.

481
00:19:54,027 --> 00:19:56,860
Đó là giá trị rác tại thời điểm này,
hoặc tôi có thể khởi tạo nó thành vô giá trị.

482
00:19:56,860 --> 00:19:59,630
Nhưng hãy để tôi tiếp tục đi với
ý tưởng này xây dựng một cây.

483
00:19:59,630 --> 00:20:04,260
Hãy để tôi phân bổ một một trong những
các nút có 26 yếu tố trong đó.

484
00:20:04,260 --> 00:20:05,150
>> Và bạn biết gì không?

485
00:20:05,150 --> 00:20:09,130
Nếu đây chỉ là một nút trong bộ nhớ
Tôi tạo ra với malloc, sử dụng một cấu trúc

486
00:20:09,130 --> 00:20:11,240
như chúng ta sẽ sớm thấy,
Tôi sẽ làm this--

487
00:20:11,240 --> 00:20:14,450
Tôi sẽ vẽ một mũi tên từ
điều mà đại diện D xuống

488
00:20:14,450 --> 00:20:15,860
đến nút mới này.

489
00:20:15,860 --> 00:20:19,240
Và bây giờ, lần đầu tiên tiếp theo
thư trong tên của Daven,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- tôi sẽ đi trước
và vẽ một nút khác như thế này,

491
00:20:24,150 --> 00:20:30,150
theo đó, các yếu tố V ở đây, mà
chúng tôi sẽ vẽ cho tả instance--.

492
00:20:30,150 --> 00:20:31,020
Chúng tôi sẽ không rút ra ở đó.

493
00:20:31,020 --> 00:20:31,936
Nó sẽ đi đây.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> Sau đó chúng ta sẽ
coi đây là V.

496
00:20:35,712 --> 00:20:44,920
Và sau đó xuống đây chúng ta sẽ chỉ số
xuống từ V vào những gì chúng tôi sẽ xem xét E.

497
00:20:44,920 --> 00:20:50,100
Và rồi từ đây chúng ta sẽ
đi có một trong các nút ở đây.

498
00:20:50,100 --> 00:20:52,930
Và bây giờ chúng tôi có một câu hỏi để trả lời.

499
00:20:52,930 --> 00:20:57,840
Tôi cần phải bằng cách nào đó chỉ ra rằng
chúng ta đang ở cuối của chuỗi Daven.

500
00:20:57,840 --> 00:20:59,490
Vì vậy, tôi chỉ có thể để nó null.

501
00:20:59,490 --> 00:21:02,670
>> Nhưng nếu chúng ta có Daven của
tên đầy đủ cũng có, mà

502
00:21:02,670 --> 00:21:04,280
là, như chúng ta đã nói, Davenport?

503
00:21:04,280 --> 00:21:06,970
Vì vậy, nếu Daven là những gì
thực sự là một chuỗi con,

504
00:21:06,970 --> 00:21:08,960
một tiền tố của một chuỗi dài hơn nhiều?

505
00:21:08,960 --> 00:21:11,450
Chúng ta không thể chỉ vĩnh viễn
nói gì đang xảy ra

506
00:21:11,450 --> 00:21:14,410
đến đó, bởi vì chúng tôi có thể
không bao giờ chèn một từ như Davenport

507
00:21:14,410 --> 00:21:15,840
vào cấu trúc dữ liệu này

508
00:21:15,840 --> 00:21:19,560
>> Vì vậy, những gì chúng ta có thể làm thay vào đó là
đối xử với nhau của các yếu tố

509
00:21:19,560 --> 00:21:22,170
như có thể có hai
các yếu tố bên trong của họ.

510
00:21:22,170 --> 00:21:24,810
Một là một con trỏ, thực sự,
như tôi đã làm.

511
00:21:24,810 --> 00:21:27,100
Vì vậy, mỗi người trong các hộp
không chỉ là một tế bào.

512
00:21:27,100 --> 00:21:29,855
Nhưng nếu đầu
one-- một đáy của

513
00:21:29,855 --> 00:21:32,230
sẽ là vô giá trị, bởi vì
không có Davenport chỉ được nêu ra.

514
00:21:32,230 --> 00:21:34,197
Điều gì nếu một trong những đầu
là một số giá trị đặc biệt không?

515
00:21:34,197 --> 00:21:36,530
Và nó sẽ là một chút
khó có thể rút ra nó kích thước này.

516
00:21:36,530 --> 00:21:38,130
Nhưng giả sử nó chỉ là một dấu.

517
00:21:38,130 --> 00:21:38,920
Kiểm tra.

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N là một chuỗi
trong cấu trúc dữ liệu này.

519
00:21:44,230 --> 00:21:48,350
>> Trong khi đó, nếu tôi đã có nhiều không gian hơn
ở đây, tôi có thể làm P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
và tôi có thể đặt kiểm tra trong các nút
có chữ T ở cuối.

521
00:21:52,650 --> 00:21:55,460
Vì vậy, đây là một cách ồ ạt
phức tạp, tìm kiếm cấu trúc dữ liệu.

522
00:21:55,460 --> 00:21:57,210
Và chữ viết tay của tôi
chắc chắn không giúp đỡ.

523
00:21:57,210 --> 00:22:00,043
Nhưng nếu tôi muốn chèn một cái gì đó
khác, hãy xem xét những gì chúng ta sẽ làm gì.

524
00:22:00,043 --> 00:22:03,370
Nếu chúng ta muốn đưa David trong,
chúng tôi theo cùng một logic, D-A-V,

525
00:22:03,370 --> 00:22:08,802
nhưng bây giờ tôi sẽ chỉ ở bên cạnh
yếu tố không phải từ E, nhưng từ I đến D.

526
00:22:08,802 --> 00:22:10,760
Vì vậy, sẽ là
các nút hơn trong cây này.

527
00:22:10,760 --> 00:22:12,325
Chúng tôi sẽ có cuộc gọi malloc hơn.

528
00:22:12,325 --> 00:22:14,700
Nhưng tôi không muốn thực hiện một
mess hoàn thành các hình ảnh này.

529
00:22:14,700 --> 00:22:17,710
Vì vậy, hãy thay vì nhìn vào một
đó là được xây dựng trước

530
00:22:17,710 --> 00:22:21,810
như thế này với không chấm, dấu chấm,
dấu chấm, nhưng mảng chỉ viết tắt.

531
00:22:21,810 --> 00:22:23,950
Nhưng mỗi nút
trong cây này ở đây

532
00:22:23,950 --> 00:22:26,700
đại diện cho thing-- cùng
một mảng Ray kích thước 26.

533
00:22:26,700 --> 00:22:28,860
>> Hoặc nếu chúng ta muốn có
thực sự thích hợp bây giờ, những gì

534
00:22:28,860 --> 00:22:30,790
nếu tên của một ai đó như
một dấu nháy đơn, chúng ta hãy

535
00:22:30,790 --> 00:22:35,560
giả sử rằng mỗi nút thực sự có
như 27 chỉ số trong nó, không chỉ 26.

536
00:22:35,560 --> 00:22:42,020
Vì vậy, điều này bây giờ là có được một dữ liệu
cấu trúc được gọi là một trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Một Trie, mà được cho là
lịch sử là một tên thông minh cho một cây

538
00:22:46,120 --> 00:22:49,040
đó là tối ưu hóa cho
thu hồi, trong đó tất nhiên,

539
00:22:49,040 --> 00:22:50,870
được viết với chữ I-E vì vậy nó Trie.

540
00:22:50,870 --> 00:22:52,710
Nhưng đó là lịch sử của Trie.

541
00:22:52,710 --> 00:22:55,860
>> Vì vậy, một Trie là dữ liệu cây như thế này
cấu trúc giống như một cây gia đình

542
00:22:55,860 --> 00:22:57,510
mà cuối cùng cư xử như thế.

543
00:22:57,510 --> 00:23:00,890
Và đây chỉ là một ví dụ về một
bó toàn bộ các tên của người khác.

544
00:23:00,890 --> 00:23:03,540
Tuy nhiên, câu hỏi bây giờ
ở bàn tay là những gì có

545
00:23:03,540 --> 00:23:08,070
chúng tôi đã đạt được bằng cách giới thiệu cho là một nhiều hơn
cấu trúc dữ liệu phức tạp, và một,

546
00:23:08,070 --> 00:23:09,870
thẳng thắn, có sử dụng rất nhiều bộ nhớ.

547
00:23:09,870 --> 00:23:11,703
>> Bởi vì mặc dù,
tại thời điểm này, tôi chỉ là

548
00:23:11,703 --> 00:23:15,050
sử dụng con trỏ D's và
A và V và Es và Ns,

549
00:23:15,050 --> 00:23:16,700
Tôi đang lãng phí một heck của rất nhiều bộ nhớ.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
Nhưng mà tôi dành một nguồn tài nguyên,
Tôi có xu hướng để làm được lại khác.

552
00:23:22,660 --> 00:23:26,020
Vì vậy, nếu tôi là chi tiêu nhiều không gian hơn,
những gì có thể là hy vọng?

553
00:23:26,020 --> 00:23:27,407
Mà tôi đang chi tiêu ít hơn những gì?

554
00:23:27,407 --> 00:23:28,240
Đung Ít thời gian.

555
00:23:28,240 --> 00:23:28,990
DAVID Malan: Time.

556
00:23:28,990 --> 00:23:30,320
Bây giờ tại sao điều đó có thể được?

557
00:23:30,320 --> 00:23:33,880
Vâng, chèn là những gì
thời gian, trong điều khoản của O lớn bây giờ,

558
00:23:33,880 --> 00:23:37,660
của một tên như Daven
hoặc Davenport hay David?

559
00:23:37,660 --> 00:23:39,340
Vâng, Daven là năm bước.

560
00:23:39,340 --> 00:23:42,350
Davenport sẽ là chín bước,
do đó, nó sẽ là một vài bước nữa.

561
00:23:42,350 --> 00:23:44,250
David sẽ là năm bước là tốt.

562
00:23:44,250 --> 00:23:47,230
Vì vậy, những người đang có bê tông
con số, nhưng chắc chắn có

563
00:23:47,230 --> 00:23:49,550
một trên ràng buộc về
chiều dài của tên của một ai đó.

564
00:23:49,550 --> 00:23:52,240
Và quả thực, trong các vấn đề
bộ năm đặc điểm kỹ thuật,

565
00:23:52,240 --> 00:23:54,050
chúng tôi sẽ đề xuất
rằng đó là một cái gì đó

566
00:23:54,050 --> 00:23:55,470
đó là nhân vật 40-một số lẻ.

567
00:23:55,470 --> 00:23:58,180
>> Thực tế, không ai có
một cái tên dài vô hạn,

568
00:23:58,180 --> 00:24:01,542
mà là để nói rằng độ dài của một
tên hoặc chiều dài của một chuỗi chúng ta có thể

569
00:24:01,542 --> 00:24:03,750
có một số trạng thái của
cấu trúc được cho là những gì?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
Đó là không đổi.

572
00:24:06,250 --> 00:24:06,430
Phải không?

573
00:24:06,430 --> 00:24:09,310
Nó có thể là một hằng số lớn như
40-một cái gì đó, nhưng nó là hằng số.

574
00:24:09,310 --> 00:24:13,752
Và nó không có sự phụ thuộc vào bao nhiêu
tên khác là trong cấu trúc dữ liệu này.

575
00:24:13,752 --> 00:24:15,460
Nói cách khác, nếu tôi
muốn đến nay chèn

576
00:24:15,460 --> 00:24:20,540
Colton hoặc Gabriel hoặc Rob hoặc Zamyla hoặc
Alison hoặc Belinda hoặc bất kỳ tên khác

577
00:24:20,540 --> 00:24:23,940
từ các nhân viên vào dữ liệu này
cấu trúc, là thời gian chạy

578
00:24:23,940 --> 00:24:26,750
chèn tên khác
sẽ có mặt tại tất cả các ảnh hưởng

579
00:24:26,750 --> 00:24:30,220
bởi có bao nhiêu nguyên tố khác
trong cấu trúc dữ liệu chưa?

580
00:24:30,220 --> 00:24:31,040
Nó không phải.

581
00:24:31,040 --> 00:24:31,540
Phải không?

582
00:24:31,540 --> 00:24:36,150
Bởi vì chúng ta đang sử dụng có hiệu quả
nhiều lớp băm bảng này.

583
00:24:36,150 --> 00:24:38,280
Và thời gian chạy của
bất kỳ của các hoạt động này

584
00:24:38,280 --> 00:24:41,510
không phụ thuộc vào số lượng
các yếu tố có trong cấu trúc dữ liệu

585
00:24:41,510 --> 00:24:43,090
hoặc được cuối cùng sẽ
được trong cấu trúc dữ liệu,

586
00:24:43,090 --> 00:24:44,714
nhưng về độ dài của những gì cụ thể?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> Chuỗi là
đưa vào, mà không làm

589
00:24:49,200 --> 00:24:52,580
tiệm này liên tục
time-- O lớn của một.

590
00:24:52,580 --> 00:24:54,720
Và thẳng thắn mà nói, chỉ trong
thế giới thực, điều này

591
00:24:54,720 --> 00:24:58,380
có nghĩa là chèn tên của Daven mất
như năm bước, hoặc Davenport chín

592
00:24:58,380 --> 00:25:00,100
bước, hoặc David năm bước.

593
00:25:00,100 --> 00:25:03,071
Đó là khá darn lần chạy nhỏ.

594
00:25:03,071 --> 00:25:05,320
Và, thực sự, đó là một rất
điều tốt, đặc biệt là khi

595
00:25:05,320 --> 00:25:08,126
nó không phụ thuộc vào tổng số
số yếu tố trong đó.

596
00:25:08,126 --> 00:25:10,500
Vậy làm thế nào chúng ta có thể thực hiện điều này
loại cấu trúc trong mã?

597
00:25:10,500 --> 00:25:12,900
Đó là nhiều hơn một chút
phức tạp, nhưng vẫn còn đó

598
00:25:12,900 --> 00:25:15,050
chỉ là một ứng dụng của
khối xây dựng cơ bản.

599
00:25:15,050 --> 00:25:17,830
Tôi sẽ xác định lại
nút chúng tôi như sau:

600
00:25:17,830 --> 00:25:21,100
bool gọi word-- và điều này
có thể được gọi là bất cứ điều gì.

601
00:25:21,100 --> 00:25:23,970
Nhưng bool đại diện
những gì tôi đã thu hút như một dấu.

602
00:25:23,970 --> 00:25:24,490
Vâng.

603
00:25:24,490 --> 00:25:26,720
Đây là phần cuối của một chuỗi
trong cấu trúc dữ liệu này.

604
00:25:26,720 --> 00:25:30,702
>> Và, tất nhiên, ngôi sao nút
có được đề cập đến trẻ em.

605
00:25:30,702 --> 00:25:32,410
Và, thực sự, giống như
một cây gia đình, bạn

606
00:25:32,410 --> 00:25:34,370
sẽ xem xét các nút
được treo tắt

607
00:25:34,370 --> 00:25:36,920
dưới cùng của một số cha mẹ
yếu tố là trẻ em.

608
00:25:36,920 --> 00:25:40,510
Và do đó trẻ em sẽ
là một mảng của 27, một 27

609
00:25:40,510 --> 00:25:41,680
chỉ là cho dấu nháy đơn.

610
00:25:41,680 --> 00:25:43,390
Chúng tôi sẽ sắp xếp
các trường hợp đặc biệt.

611
00:25:43,390 --> 00:25:45,400
Vì vậy, bạn có thể có một số
tên với dấu nháy.

612
00:25:45,400 --> 00:25:47,399
Thậm chí có dấu gạch ngang nên
đi ở đó, nhưng bạn sẽ

613
00:25:47,399 --> 00:25:50,330
nhìn thấy trong p tập 5 chúng ta chỉ chăm sóc
về chữ cái và dấu nháy.

614
00:25:50,330 --> 00:25:52,990
>> Và sau đó làm thế nào để bạn đại diện
cấu trúc dữ liệu riêng của mình?

615
00:25:52,990 --> 00:25:56,454
Làm thế nào để bạn đại diện gốc
của Trie này, vì vậy để nói chuyện?

616
00:25:56,454 --> 00:25:59,620
Vâng, giống như với một danh sách liên kết, bạn
cần một con trỏ đến phần tử đầu tiên.

617
00:25:59,620 --> 00:26:04,270
Với một Trie bạn chỉ cần một
con trỏ vào thư mục gốc của Trie này.

618
00:26:04,270 --> 00:26:07,290
Và từ đó bạn có thể băm
cách của bạn xuống sâu hơn và sâu hơn

619
00:26:07,290 --> 00:26:10,460
để tất cả các nút khác trong cấu trúc.

620
00:26:10,460 --> 00:26:13,440
Vì vậy, chỉ đơn giản với can này
chúng tôi đại diện cho cấu trúc đó.

621
00:26:13,440 --> 00:26:15,877
>> Bây giờ Meanwhile-- Oh, câu hỏi.

622
00:26:15,877 --> 00:26:17,220
>> Đung từ bool là gì?

623
00:26:17,220 --> 00:26:20,490
>> DAVID Malan: Từ Bool là
chỉ hóa thân C này

624
00:26:20,490 --> 00:26:22,920
những gì tôi mô tả
trong hộp này đây, khi

625
00:26:22,920 --> 00:26:26,000
Tôi bắt đầu chia mỗi
các yếu tố của mảng thành hai mảnh.

626
00:26:26,000 --> 00:26:27,600
Một là một con trỏ đến nút tiếp theo.

627
00:26:27,600 --> 00:26:30,280
Các khác có được
một cái gì đó giống như một hộp kiểm tra

628
00:26:30,280 --> 00:26:33,770
nói có, có một
từ Daven kết thúc ở đây,

629
00:26:33,770 --> 00:26:35,610
bởi vì chúng tôi không muốn,
tại thời điểm này, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Mặc dù Dave là có được một
từ hợp pháp, ông không phải trong Trie

631
00:26:39,320 --> 00:26:39,830
được nêu ra.

632
00:26:39,830 --> 00:26:40,950
Và D không phải là một từ.

633
00:26:40,950 --> 00:26:42,770
Và D-A không phải là một từ hoặc một tên.

634
00:26:42,770 --> 00:26:45,020
Vì vậy, các dấu kiểm
chỉ một lần duy nhất bạn

635
00:26:45,020 --> 00:26:48,190
nhấn nút này là
con đường trước đây của nhân vật

636
00:26:48,190 --> 00:26:50,700
thực sự là một chuỗi mà bạn đã chèn.

637
00:26:50,700 --> 00:26:53,660
Vì vậy, đó là tất cả các bool
có được làm cho chúng ta.

638
00:26:53,660 --> 00:26:55,500
>> Bất kỳ câu hỏi khác trên cố gắng?

639
00:26:55,500 --> 00:26:56,215
Yeah.

640
00:26:56,215 --> 00:26:58,035
>> Đung sự chồng chéo là gì?

641
00:26:58,035 --> 00:26:59,945
Điều gì nếu bạn có một Dave và Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID Malan: Hoàn hảo.

643
00:27:00,820 --> 00:27:02,580
Điều gì nếu bạn có một Dave và Daven?

644
00:27:02,580 --> 00:27:06,240
Vì vậy, nếu chúng ta chèn, nói một biệt danh,
cho David-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
Đây thực sự là siêu đơn giản.

647
00:27:08,700 --> 00:27:10,325
Vì vậy, chúng tôi sẽ chỉ mất bốn bước.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. Và tôi có những gì để
làm một lần tôi nhấn nút đó thứ tư?

650
00:27:15,847 --> 00:27:16,680
Chỉ cần đi kiểm tra.

651
00:27:16,680 --> 00:27:18,000
Chúng tôi đã tốt để đi.

652
00:27:18,000 --> 00:27:18,840
Xong.

653
00:27:18,840 --> 00:27:19,750
Bốn bước.

654
00:27:19,750 --> 00:27:21,590
Thời gian cố định tiệm cận.

655
00:27:21,590 --> 00:27:26,300
Và bây giờ chúng tôi đã chỉ ra rằng cả hai Dave
và Daven là chuỗi trong cấu trúc.

656
00:27:26,300 --> 00:27:27,710
Vì vậy, không phải là một vấn đề.

657
00:27:27,710 --> 00:27:30,200
Và chú ý sự hiện diện
của Daven không làm cho nó

658
00:27:30,200 --> 00:27:34,750
có bất kỳ nhiều thời gian hơn hoặc ít hơn
thời gian cho Dave và ngược lại.

659
00:27:34,750 --> 00:27:36,000
>> Vì vậy, những gì khác chúng tôi bây giờ có thể làm gì?

660
00:27:36,000 --> 00:27:40,680
Chúng tôi đã sử dụng phép ẩn dụ này trước khi
khay đại diện cho một cái gì đó.

661
00:27:40,680 --> 00:27:43,380
Nhưng nó chỉ ra rằng một
chồng khay thực sự là

662
00:27:43,380 --> 00:27:47,187
chứng minh của một dữ liệu trừu tượng
type-- một cấu trúc dữ liệu cấp độ cao hơn

663
00:27:47,187 --> 00:27:49,770
là lúc kết thúc ngày chỉ là
giống như một mảng hoặc một danh sách liên kết

664
00:27:49,770 --> 00:27:50,970
hoặc một cái gì đó trần tục hơn.

665
00:27:50,970 --> 00:27:53,270
Nhưng đó là một thú vị hơn
khái niệm khái niệm.

666
00:27:53,270 --> 00:27:56,440
Một stack, như thế này
khay ở đây trong Mather,

667
00:27:56,440 --> 00:27:58,750
thường được gọi là
chỉ that-- một chồng.

668
00:27:58,750 --> 00:28:02,540
>> Và trong loại cấu trúc dữ liệu
bạn có hai operations--

669
00:28:02,540 --> 00:28:05,880
bạn có một gọi là thúc đẩy
thêm một cái gì đó để ngăn xếp,

670
00:28:05,880 --> 00:28:08,320
giống như đặt khay khác
sao trên đỉnh của stack.

671
00:28:08,320 --> 00:28:11,350
Và sau đó bật, có nghĩa là bạn
lấy khay ra trên cùng.

672
00:28:11,350 --> 00:28:16,210
Nhưng điều quan trọng về một chồng là
nó có đặc tính tò mò này.

673
00:28:16,210 --> 00:28:19,560
Khi các nhân viên phòng ăn là
sắp xếp lại các khay cho bữa ăn tiếp theo,

674
00:28:19,560 --> 00:28:21,380
những gì sẽ là
đúng về cách sinh viên

675
00:28:21,380 --> 00:28:22,856
tương tác với các cấu trúc dữ liệu này?

676
00:28:22,856 --> 00:28:24,480
Đung Họ sẽ bật một off.

677
00:28:24,480 --> 00:28:26,550
DAVID Malan: Họ sẽ
bật một tắt, hy vọng hàng đầu.

678
00:28:26,550 --> 00:28:28,910
Nếu không nó chỉ là ngu ngốc
đi tất cả các cách để phía dưới.

679
00:28:28,910 --> 00:28:29,070
Phải không?

680
00:28:29,070 --> 00:28:31,620
Cấu trúc dữ liệu không thực sự cho phép
bạn để lấy các khay dưới cùng ít nhất

681
00:28:31,620 --> 00:28:32,520
một cách dễ dàng.

682
00:28:32,520 --> 00:28:35,040
Vì vậy, có tò mò này
tài sản để một chồng

683
00:28:35,040 --> 00:28:39,730
rằng mục cuối cùng trong là
sẽ là một trong ra ngoài đầu tiên.

684
00:28:39,730 --> 00:28:43,400
Và các nhà khoa học máy tính gọi
LIFO-- này kéo dài, ra trước.

685
00:28:43,400 --> 00:28:45,540
Và nó thực sự không có
ứng dụng thú vị.

686
00:28:45,540 --> 00:28:50,090
Nó không nhất thiết phải rõ ràng như một số
những người khác, nhưng nó có thể, thực sự, có ích,

687
00:28:50,090 --> 00:28:54,040
và nó có thể, thực sự, được thực hiện
trong một vài cách khác nhau.

688
00:28:54,040 --> 00:28:58,550
>> Vì vậy, một, và thực sự, chúng ta hãy
tôi không đi sâu vào đó.

689
00:28:58,550 --> 00:28:59,860
Hãy làm điều này để thay thế.

690
00:28:59,860 --> 00:29:03,700
Hãy nhìn vào một trong đó là gần như
cùng một ý tưởng, nhưng đó là một chút công bằng hơn.

691
00:29:03,700 --> 00:29:04,200
Phải không?

692
00:29:04,200 --> 00:29:07,560
Nếu bạn là một trong những chàng trai fan hâm mộ hoặc
cô gái đó thực sự thích sản phẩm của Apple

693
00:29:07,560 --> 00:29:10,130
và bạn tỉnh dậy vào lúc 03:00
để xếp hàng tại một số cửa hàng

694
00:29:10,130 --> 00:29:14,150
để có được iPhone mới nhất, bạn
có thể xếp hàng như thế này.

695
00:29:14,150 --> 00:29:15,800
>> Bây giờ một hàng đợi rất cố tình đặt tên.

696
00:29:15,800 --> 00:29:18,190
Đó là một đường bởi vì có
một số sự công bằng cho nó.

697
00:29:18,190 --> 00:29:18,690
Phải không?

698
00:29:18,690 --> 00:29:21,690
Nó sẽ loại hút nếu bạn đã
đã có đầu tiên tại Apple Store

699
00:29:21,690 --> 00:29:25,700
nhưng bạn có hiệu quả dưới cùng
khay vì các nhân viên của Apple sau đó

700
00:29:25,700 --> 00:29:28,189
bật người cuối cùng
thực sự đã phù hợp.

701
00:29:28,189 --> 00:29:31,230
Vì vậy, ngăn xếp và hàng đợi, mặc dù
chức năng họ đang loại các same--

702
00:29:31,230 --> 00:29:33,105
nó chỉ là bộ sưu tập này
các nguồn lực đó là

703
00:29:33,105 --> 00:29:36,210
sẽ phát triển và shrink-- có của
khía cạnh công bằng này với nó,

704
00:29:36,210 --> 00:29:39,634
ít nhất là trong thế giới thực,
nơi mà các hoạt động tập thể dục

705
00:29:39,634 --> 00:29:40,800
về cơ bản là khác nhau.

706
00:29:40,800 --> 00:29:43,360
Một stack-- một hàng đợi
rather-- được cho là có

707
00:29:43,360 --> 00:29:45,320
hai hoạt động: n hàng đợi và d hàng đợi.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
Hoặc bạn có thể gọi cho họ
bất kỳ số lượng của sự vật.

710
00:29:48,090 --> 00:29:50,770
Nhưng bạn chỉ muốn chụp
quan điểm cho rằng một là thêm

711
00:29:50,770 --> 00:29:53,230
và là một trong những cuối cùng trừ.

712
00:29:53,230 --> 00:29:58,840
>> Bây giờ bên dưới mui xe, cả hai stack
và một hàng đợi có thể được thực hiện như thế nào?

713
00:29:58,840 --> 00:30:01,390
Chúng tôi sẽ không đi vào mã của
nó bởi vì mức độ cao hơn

714
00:30:01,390 --> 00:30:03,387
ý tưởng là loại rõ ràng hơn.

715
00:30:03,387 --> 00:30:04,470
Tôi có nghĩa là, những gì con người làm gì?

716
00:30:04,470 --> 00:30:07,030
Nếu tôi là người đầu tiên tại Apple
Lưu trữ và đây là cửa trước,

717
00:30:07,030 --> 00:30:08,130
bạn đã biết, tôi sẽ đứng ở đây.

718
00:30:08,130 --> 00:30:09,750
Và người kế tiếp của
sẽ đứng ở đây.

719
00:30:09,750 --> 00:30:11,500
Và người kế tiếp của
sẽ đứng ở đây.

720
00:30:11,500 --> 00:30:13,792
Vì vậy, những gì cấu trúc dữ liệu
vay chính nó để một hàng đợi?

721
00:30:13,792 --> 00:30:14,542
>> Đung Một hàng đợi.

722
00:30:14,542 --> 00:30:15,667
DAVID Malan: Vâng, một hàng đợi.

723
00:30:15,667 --> 00:30:16,390
Chắc chắn.

724
00:30:16,390 --> 00:30:16,920
Những gì khác?

725
00:30:16,920 --> 00:30:17,600
>> Đung Một danh sách liên kết.

726
00:30:17,600 --> 00:30:18,990
>> DAVID Malan: Một liên kết
danh sách bạn có thể thực hiện.

727
00:30:18,990 --> 00:30:22,500
Và một danh sách liên kết là tốt đẹp vì sau đó
nó có thể phát triển tùy tiện dài như trái ngược

728
00:30:22,500 --> 00:30:24,880
để có một số cố định
người trong cửa hàng.

729
00:30:24,880 --> 00:30:27,030
Nhưng có lẽ một số cố định
nơi là hợp pháp.

730
00:30:27,030 --> 00:30:30,350
Bởi vì nếu họ chỉ có như 20
iPhone vào ngày đầu tiên, có thể

731
00:30:30,350 --> 00:30:33,930
họ chỉ cần một mảng có kích thước
20 đại diện cho rằng hàng đợi, mà

732
00:30:33,930 --> 00:30:37,070
chỉ để nói bây giờ khi chúng tôi bắt đầu nói chuyện
về những vấn đề cấp cao hơn,

733
00:30:37,070 --> 00:30:38,890
bạn có thể thực hiện nó
trong bất kỳ số cách.

734
00:30:38,890 --> 00:30:42,030
Và có lẽ chỉ cần đi
là một thương mại giảm trong không gian và thời gian

735
00:30:42,030 --> 00:30:43,950
hoặc chỉ phức tạp mã riêng của bạn.

736
00:30:43,950 --> 00:30:45,380
>> Những gì về một chồng?

737
00:30:45,380 --> 00:30:48,190
Vâng, một chồng, chúng tôi đã nhìn thấy quá
chỉ có thể là những khay.

738
00:30:48,190 --> 00:30:50,007
Và bạn có thể thực hiện điều này một mảng.

739
00:30:50,007 --> 00:30:53,090
Tuy nhiên, tại một số điểm nếu bạn sử dụng một mảng,
những gì sẽ xảy ra với các khay

740
00:30:53,090 --> 00:30:54,173
bạn đang cố gắng để đặt xuống?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
Được rồi.

743
00:30:55,670 --> 00:30:57,490
Bạn sẽ chỉ
có thể đi quá cao.

744
00:30:57,490 --> 00:31:00,156
Và tôi nghĩ rằng trong Mather họ
thực sự lõm trong việc mở cửa đó.

745
00:31:00,156 --> 00:31:01,950
Vì vậy, thực sự, nó gần như
như Mather đang sử dụng

746
00:31:01,950 --> 00:31:03,783
một mảng có kích thước cố định,
bởi vì bạn chỉ có thể

747
00:31:03,783 --> 00:31:08,302
phù hợp với rất nhiều khay trong đó mở cửa trong
tường xuống dưới đầu gối của người dân.

748
00:31:08,302 --> 00:31:10,010
Và do đó có thể
cho là một mảng,

749
00:31:10,010 --> 00:31:14,300
nhưng chúng tôi chắc chắn có thể thực hiện điều đó
nói chung với một danh sách liên kết.

750
00:31:14,300 --> 00:31:16,390
>> Vâng, những gì về cấu trúc dữ liệu khác?

751
00:31:16,390 --> 00:31:18,760
Hãy để tôi kéo lên một hình ảnh khác ở đây.

752
00:31:18,760 --> 00:31:24,710
Một cái gì đó như thế nào về việc này ở đây?

753
00:31:24,710 --> 00:31:28,920
Tại sao nó có thể là hữu ích để có không
một cái gì đó là ưa thích như một Trie, mà

754
00:31:28,920 --> 00:31:32,370
chúng tôi đã thấy có các nút này rất rộng,
mỗi trong số đó là trong một mảng?

755
00:31:32,370 --> 00:31:35,740
Nhưng nếu chúng ta làm điều gì đó nhiều hơn
đơn giản, giống như một cây gia đình trường học cũ,

756
00:31:35,740 --> 00:31:38,110
từng có các nút ở đây
chỉ là lưu trữ một số.

757
00:31:38,110 --> 00:31:42,180
Thay vì một tên hoặc một hậu duệ
chỉ là lưu trữ một số lượng như thế này.

758
00:31:42,180 --> 00:31:45,250
>> Vâng, các thuật ngữ chúng tôi sử dụng trong
cấu trúc dữ liệu là cả hai cố gắng

759
00:31:45,250 --> 00:31:49,510
và cây, nơi một Trie, một lần nữa, là
chỉ một mà các nút là mảng,

760
00:31:49,510 --> 00:31:51,680
vẫn là những gì bạn có thể
sử dụng từ trường lớp

761
00:31:51,680 --> 00:31:53,860
khi bạn đã thực hiện một gia đình
tree-- lá và gốc

762
00:31:53,860 --> 00:31:57,250
của cây và trẻ em của
cha mẹ và anh chị em biết.

763
00:31:57,250 --> 00:32:03,670
Và chúng ta có thể thực hiện một cây,
Ví dụ như chỉ đơn giản như thế này.

764
00:32:03,670 --> 00:32:07,420
Một cây, nếu nó như là một nút, một trong những
những vòng tròn này có một số,

765
00:32:07,420 --> 00:32:09,947
nó sẽ không có
một con trỏ, nhưng hai.

766
00:32:09,947 --> 00:32:11,780
Và ngay khi bạn thêm
một con trỏ thứ hai, bạn

767
00:32:11,780 --> 00:32:13,905
thực sự bây giờ có thể làm cho loại
dữ liệu hai chiều

768
00:32:13,905 --> 00:32:14,780
cấu trúc trong bộ nhớ.

769
00:32:14,780 --> 00:32:16,660
Giống như một hai chiều
mảng, bạn có thể

770
00:32:16,660 --> 00:32:18,904
có loại hai chiều
danh sách liên kết, nhưng những người

771
00:32:18,904 --> 00:32:20,820
mà theo một mô hình
nơi không có chu kỳ.

772
00:32:20,820 --> 00:32:24,487
Đó thực sự là một cái cây với một
cách ông bà lên ở đây và sau đó

773
00:32:24,487 --> 00:32:27,320
một số phụ huynh và trẻ em và
cháu và chắt.

774
00:32:27,320 --> 00:32:28,370
và vv.

775
00:32:28,370 --> 00:32:32,390
>> Nhưng những gì thực sự gọn gàng về việc này quá,
chỉ để trêu chọc bạn với một chút mã,

776
00:32:32,390 --> 00:32:35,370
thu hồi đệ quy từ
một thời gian trở lại, nhờ đó mà

777
00:32:35,370 --> 00:32:38,220
bạn viết một chức năng mà tự gọi mình.

778
00:32:38,220 --> 00:32:41,140
Đây là một cơ hội đẹp
để thực hiện một cái gì đó

779
00:32:41,140 --> 00:32:42,920
như đệ quy, bởi vì xem xét việc này.

780
00:32:42,920 --> 00:32:43,860
>> Đây là một cây.

781
00:32:43,860 --> 00:32:48,040
Và tôi đã được một hậu môn nhỏ với cách
Tôi đặt các số nguyên vào các đường phố.

782
00:32:48,040 --> 00:32:51,020
Vì vậy, nhiều như vậy mà nó có một đặc biệt
name-- một cây tìm kiếm nhị phân.

783
00:32:51,020 --> 00:32:53,460
Bây giờ chúng ta đã nghe nói về nhị phân
tìm kiếm, nhưng có thể bạn

784
00:32:53,460 --> 00:32:55,180
làm việc ngược từ tên của điều này?

785
00:32:55,180 --> 00:32:59,280
Mô hình như thế nào tôi là gì
chèn các số nguyên vào cây này?

786
00:32:59,280 --> 00:33:00,696
Đó không phải là tùy ý.

787
00:33:00,696 --> 00:33:01,570
Có một số mô hình.

788
00:33:01,570 --> 00:33:02,090
Yeah.

789
00:33:02,090 --> 00:33:03,370
>> Đung những người nhỏ hơn ở bên trái.

790
00:33:03,370 --> 00:33:03,690
>> DAVID Malan: Yeah.

791
00:33:03,690 --> 00:33:05,062
Những cái nhỏ hơn là bên trái.

792
00:33:05,062 --> 00:33:06,270
Những người lớn hơn là ở bên phải.

793
00:33:06,270 --> 00:33:12,940
Như vậy mà một tuyên bố đúng là một
cha mẹ là lớn hơn con trái của nó,

794
00:33:12,940 --> 00:33:14,850
nhưng ít hơn con phải của nó.

795
00:33:14,850 --> 00:33:17,750
Và rằng một mình là ngay cả một
định nghĩa bằng lời nói đệ quy

796
00:33:17,750 --> 00:33:20,500
bởi vì bạn có thể áp dụng được
cùng một logic để tất cả các nút

797
00:33:20,500 --> 00:33:23,080
và nó chỉ có đáy
ra, một trường hợp cơ sở nếu bạn

798
00:33:23,080 --> 00:33:25,740
sẽ, khi bạn nhấn một trong
lá, có thể nói,

799
00:33:25,740 --> 00:33:28,580
nơi nghỉ không có con nữa.

800
00:33:28,580 --> 00:33:30,614
>> Bây giờ làm thế nào bạn có thể tìm thấy các số 44?

801
00:33:30,614 --> 00:33:32,280
Bạn sẽ bắt đầu ở gốc và nói, hm.

802
00:33:32,280 --> 00:33:35,690
55 không phải là 44 Vì vậy, tôi muốn đi
đúng hay tôi muốn đi sang trái?

803
00:33:35,690 --> 00:33:37,190
Vâng, rõ ràng là bạn muốn đi bên trái.

804
00:33:37,190 --> 00:33:40,060
Và do đó, nó chỉ giống như điện thoại
Ví dụ trong cuốn sách tìm kiếm nhị phân

805
00:33:40,060 --> 00:33:41,099
nói chung.

806
00:33:41,099 --> 00:33:43,390
Nhưng chúng tôi đang thực hiện nó
bây giờ là một ít năng động hơn

807
00:33:43,390 --> 00:33:45,339
là một mảng có thể cho phép.

808
00:33:45,339 --> 00:33:48,130
Và trong thực tế, nếu bạn muốn tìm
vào mã, ở cái nhìn đầu tiên chắc chắn.

809
00:33:48,130 --> 00:33:49,671
Nó trông giống như một bó toàn bộ các dòng.

810
00:33:49,671 --> 00:33:51,220
Nhưng nó đẹp đơn giản.

811
00:33:51,220 --> 00:33:54,490
Nếu bạn muốn thực hiện một chức năng
được gọi là tìm kiếm có mục đích trong cuộc sống

812
00:33:54,490 --> 00:33:57,290
là để tìm kiếm một giá trị
như n, một số nguyên,

813
00:33:57,290 --> 00:34:01,756
và bạn đang thông qua trong một pointer--
một con trỏ đến nút của rễ,

814
00:34:01,756 --> 00:34:04,380
đúng hơn, của cây mà từ đó
bạn có thể truy cập vào tất cả mọi thứ khác,

815
00:34:04,380 --> 00:34:08,850
thông báo một cách thẳng thắn
bạn có thể thực hiện logic.

816
00:34:08,850 --> 00:34:10,880
Nếu cây là null,
rõ ràng là nó không có ở đó.

817
00:34:10,880 --> 00:34:11,880
Hãy chỉ trả về false.

818
00:34:11,880 --> 00:34:12,000
Phải không?

819
00:34:12,000 --> 00:34:14,040
Nếu bạn đưa nó không có gì,
không có gì có.

820
00:34:14,040 --> 00:34:17,900
>> Khác, nếu n là ít hơn
cây mũi tên n-- tại mũi tên n,

821
00:34:17,900 --> 00:34:20,670
nhớ lại chúng tôi giới thiệu siêu
một thời gian ngắn ngày khác,

822
00:34:20,670 --> 00:34:25,100
và điều đó chỉ có nghĩa là de-tham khảo
con trỏ và nhìn vào các lĩnh vực được gọi là n.

823
00:34:25,100 --> 00:34:27,690
Vì vậy, nó có nghĩa là đi đến đó và
nhìn vào các lĩnh vực được gọi là n.

824
00:34:27,690 --> 00:34:33,810
Vì vậy, nếu n, giá trị mà bạn đang đưa ra, ít
hơn giá trị trong số nguyên cây,

825
00:34:33,810 --> 00:34:35,449
nơi nào bạn muốn đi đâu?

826
00:34:35,449 --> 00:34:36,389
Về bên trái.

827
00:34:36,389 --> 00:34:37,780
>> Vì vậy, chú ý đến đệ quy.

828
00:34:37,780 --> 00:34:39,860
Tôi returning-- không đúng sự thật.

829
00:34:39,860 --> 00:34:40,989
Không sai.

830
00:34:40,989 --> 00:34:45,670
Tôi trở lại bất cứ câu trả lời
là từ một cuộc gọi đến bản thân mình, đi qua

831
00:34:45,670 --> 00:34:50,100
một n một lần nữa, đó là không cần thiết,
nhưng những gì hơi khác nhau bây giờ?

832
00:34:50,100 --> 00:34:51,989
Làm thế nào tôi làm cho vấn đề nhỏ hơn?

833
00:34:51,989 --> 00:34:54,920
Tôi đang đi qua trong khi thứ hai
đối số, không phải là gốc của cây,

834
00:34:54,920 --> 00:34:59,616
nhưng con trái trong trường hợp này.

835
00:34:59,616 --> 00:35:00,990
Vì vậy, tôi đi qua trong con trái.

836
00:35:00,990 --> 00:35:04,720
>> Trong khi đó, nếu n lớn hơn
nút tôi hiện đang xem xét,

837
00:35:04,720 --> 00:35:06,690
Tôi tìm kiếm phía bên tay phải.

838
00:35:06,690 --> 00:35:10,880
Khác, nếu cây không phải là null, và
nếu các yếu tố không phải sang trái

839
00:35:10,880 --> 00:35:13,240
và nó không phải bên phải,
những gì là tuyệt vời như vậy?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Chúng tôi đã thực sự tìm thấy các nút trong
câu hỏi, và vì vậy chúng tôi trở thành sự thật.

842
00:35:18,440 --> 00:35:21,490
>> Vì vậy, chúng tôi đã chỉ trầy xước bề mặt
bây giờ một số các cấu trúc dữ liệu.

843
00:35:21,490 --> 00:35:24,370
Trong vấn đề thiết lập năm bạn sẽ thấy
khám phá những chưa thêm,

844
00:35:24,370 --> 00:35:27,250
và bạn sẽ được đưa ra thiết kế của bạn
lựa chọn thế nào để đi về việc này.

845
00:35:27,250 --> 00:35:30,250
Những gì tôi muốn kết luận về
chỉ là một lời trêu ghẹo thứ hai 30

846
00:35:30,250 --> 00:35:32,080
về những gì đang chờ đợi vào tuần tới và xa hơn nữa.

847
00:35:32,080 --> 00:35:35,390
>> Như chúng ta begin-- may mắn bạn có thể
think-- quá trình chuyển đổi của chúng tôi từ từ

848
00:35:35,390 --> 00:35:38,680
từ thế giới của C và thấp hơn
chi tiết quá trình thực hiện,

849
00:35:38,680 --> 00:35:42,090
đến một thế giới mà chúng ta có thể cho
cấp mà người khác có cuối cùng

850
00:35:42,090 --> 00:35:44,010
thực hiện các dữ liệu
cấu trúc cho chúng ta,

851
00:35:44,010 --> 00:35:47,570
và chúng ta sẽ bắt đầu hiểu được
thế giới thực có nghĩa là thực hiện

852
00:35:47,570 --> 00:35:50,560
các chương trình dựa trên web và
các trang web nói chung

853
00:35:50,560 --> 00:35:52,910
và cũng là an ninh rất
hàm ý rằng chúng tôi chỉ đã

854
00:35:52,910 --> 00:35:54,850
bắt đầu làm xước bề mặt.

855
00:35:54,850 --> 00:35:57,320
Đây là những gì chờ đợi chúng ta
trong những ngày tới.

856
00:35:57,320 --> 00:36:00,480
>> [VIDEO PLAYBACK]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Anh Đi kèm với một tin nhắn,
với một giao thức tất cả của riêng mình.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Ông đã đến một thế giới tàn nhẫn
tường lửa, router không quan tâm,

861
00:36:30,894 --> 00:36:33,368
và nguy hiểm tồi tệ hơn cả cái chết.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Ông nhanh chóng.

864
00:36:36,236 --> 00:36:37,980
Anh ấy mạnh mẽ.

865
00:36:37,980 --> 00:36:42,830
Anh ấy là TCP / IP, và ông đã nhận địa chỉ của bạn.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Warriors of the Net".

868
00:36:48,074 --> 00:36:49,660
[END Video PLAYBACK]

869
00:36:49,660 --> 00:36:50,910
DAVID Malan: Đến tuần tiếp theo.

870
00:36:50,910 --> 00:36:51,880
Chúng tôi sẽ nhìn thấy bạn sau đó.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[VIDEO PLAYBACK]

873
00:36:56,060 --> 00:36:59,240
-Và Bây giờ, "Suy nghĩ sâu"
bởi Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Luôn luôn bắt đầu
các bài giảng với, "Được rồi."

876
00:37:05,820 --> 00:37:08,750
Tại sao không, "Đây là giải pháp
cho vấn đề thiết lập trong tuần này "

877
00:37:08,750 --> 00:37:12,180
hoặc "Chúng tôi đang đem lại cho tất cả các bạn một A?"

878
00:37:12,180 --> 00:37:13,380
[Cười]

879
00:37:13,380 --> 00:37:15,530
[END Video PLAYBACK]