1
00:00:00,000 --> 00:00:11,460

2
00:00:11,460 --> 00:00:12,250
>> DAVID Malan: Được rồi.

3
00:00:12,250 --> 00:00:13,860
Chào mừng trở lại CS50.

4
00:00:13,860 --> 00:00:16,190
Đây là khởi đầu của tuần 8.

5
00:00:16,190 --> 00:00:21,320
Và nhớ lại rằng vấn đề bộ 5 đã kết thúc
với một chút của một thách thức.

6
00:00:21,320 --> 00:00:25,210
Vì vậy, giả sử bạn phục hồi tất cả các bạn
nghiên cứu sinh giảng dạy và hình ảnh của CA

7
00:00:25,210 --> 00:00:30,480
trong tập tin card.raw, bạn có đủ điều kiện
Cho đến nay tất cả những người này, và

8
00:00:30,480 --> 00:00:34,510
một chiến thắng may mắn sẽ đi bộ về nhà với một
những điều này, chuyển động bước nhảy vọt

9
00:00:34,510 --> 00:00:37,450
thiết bị mà bạn có thể sử dụng cho thức
dự án, ví dụ.

10
00:00:37,450 --> 00:00:39,860
>> Này, mỗi năm, dẫn đến
một chút creepiness.

11
00:00:39,860 --> 00:00:43,480
Và vì vậy những gì tôi nghĩ rằng tôi muốn làm là chia sẻ
với bạn một số các ghi chú có

12
00:00:43,480 --> 00:00:47,370
đi lại trên
danh sách nhân viên cuối năm.

13
00:00:47,370 --> 00:00:51,110
Ví dụ, chỉ đêm qua, báo giá
unquote, từ một trong những nhân viên

14
00:00:51,110 --> 00:00:55,000
các thành viên, "Tôi chỉ có một tiếng gõ sinh viên
cửa nhà tôi để chụp ảnh với tôi.

15
00:00:55,000 --> 00:00:59,020
Stalker, tôi nói với bạn. "Bắt đầu ra
khá mô tả và sau đó chúng tôi chuyển

16
00:00:59,020 --> 00:01:02,830
vào, một giờ hoặc lâu sau, "Tôi đã có một
sinh viên chờ đợi cho tôi sau khi phần

17
00:01:02,830 --> 00:01:06,080
và ông ta đã có tên và hình ảnh của chúng tôi
trên một số tờ giấy. "Được rồi.

18
00:01:06,080 --> 00:01:09,230
Vì vậy, tổ chức, nhưng không
tất cả những gì đáng sợ chưa.

19
00:01:09,230 --> 00:01:12,520
>> Sau đó, "Tôi đã ra khỏi thành phố vào cuối tuần này,
và khi tôi trở lại, đã có một trong

20
00:01:12,520 --> 00:01:12,630
của tôi

21
00:01:12,630 --> 00:01:16,740
phòng ngủ. "[Cười]

22
00:01:16,740 --> 00:01:20,410
DAVID Malan: quote tiếp từ một nhân viên
thành viên ", một sinh viên đến nhà tôi tại

23
00:01:20,410 --> 00:01:25,330
Somerville lúc 4:00 sáng nay. "Tiếp
nhân viên, "Tôi đã đến khách sạn của tôi ở San

24
00:01:25,330 --> 00:01:30,016
Francisco và một sinh viên đã được chờ đợi
tôi ở hành lang với ba máy DSLR. "

25
00:01:30,016 --> 00:01:31,510
Loại máy ảnh.

26
00:01:31,510 --> 00:01:34,980
"Tôi thậm chí không vào nhân viên trong học kỳ này,
nhưng một sinh viên xông vào nhà tôi này

27
00:01:34,980 --> 00:01:40,480
buổi sáng và ghi lại toàn bộ điều
với Google Glass. "Và rồi cuối cùng,

28
00:01:40,480 --> 00:01:43,650
"Ít nhất 12 người đã háo hức
chờ tôi khi tôi bước ra khỏi của tôi

29
00:01:43,650 --> 00:01:44,800
đưa đón, và sau đó tôi

30
00:01:44,800 --> 00:01:46,970
tỉnh dậy. "Được rồi.

31
00:01:46,970 --> 00:01:57,690
Vì vậy, một trong những hình ảnh, như bạn có thể
nhớ lại, là đồng này đây, những người bạn

32
00:01:57,690 --> 00:02:01,850
có thể biết như Milo Chuối, sống
với Lauren Carvalho, người đứng đầu của chúng tôi

33
00:02:01,850 --> 00:02:02,905
giảng dạy viên.

34
00:02:02,905 --> 00:02:05,170
Milo, Milo, đến đây cậu bé.

35
00:02:05,170 --> 00:02:06,320
Milo.

36
00:02:06,320 --> 00:02:08,650
Milo.

37
00:02:08,650 --> 00:02:12,230
Tâm trí bạn, anh mặc Google Glass, vì vậy
chúng tôi sẽ cho bạn thấy tất cả điều này sau.

38
00:02:12,230 --> 00:02:16,190
Vì vậy, đây là Milo nếu bạn muốn
chụp một bức ảnh với anh ta sau đó.

39
00:02:16,190 --> 00:02:18,240
Nếu bạn muốn để tìm cho ra
vào khán giả ở đó.

40
00:02:18,240 --> 00:02:19,430
OK.

41
00:02:19,430 --> 00:02:20,200
Đó là cảnh quay tốt.

42
00:02:20,200 --> 00:02:22,556
Vâng, Milo chuối.

43
00:02:22,556 --> 00:02:23,941
Oh, không làm điều đó.

44
00:02:23,941 --> 00:02:29,020
>> [Cười]

45
00:02:29,020 --> 00:02:29,470
>> OK.

46
00:02:29,470 --> 00:02:34,550
Vì vậy, một từ sau đó trên những gì nằm phía trước,
bởi vì như chúng ta bắt đầu quá trình chuyển đổi,

47
00:02:34,550 --> 00:02:38,410
tuần này cụ thể, từ C trong một
môi trường dòng lệnh để PHP và

48
00:02:38,410 --> 00:02:42,720
JavaScript và SQL và HTML và CSS trong
một môi trường dựa trên web, chúng tôi sẽ

49
00:02:42,720 --> 00:02:44,490
trang bị cho bạn với tất cả các
kiến thức nhiều hơn cho

50
00:02:44,490 --> 00:02:46,010
dự án cuối cùng tiềm năng.

51
00:02:46,010 --> 00:02:49,240
Hướng tới mục tiêu đó, khóa học có
truyền thống của tổ chức hội thảo mà

52
00:02:49,240 --> 00:02:50,950
là về các chủ đề tiếp tuyến
cho khóa học.

53
00:02:50,950 --> 00:02:54,330
Rất nhiều liên quan đến lập trình và
phát triển ứng dụng và vv, nhưng

54
00:02:54,330 --> 00:02:57,010
không nhất thiết phải khám phá bởi
giáo trình riêng của khóa học.

55
00:02:57,010 --> 00:03:00,250
>> Vì vậy, nếu bạn có thể quan tâm trong một
hoặc nhiều hơn các cuộc hội thảo năm nay,

56
00:03:00,250 --> 00:03:02,530
đăng ký tại cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
Có các cuộc hội thảo lớn tuổi
tại cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
Và vào danh sách vậy, đến nay trong năm nay
là ứng dụng web tuyệt vời với Ruby on

59
00:03:10,620 --> 00:03:13,580
Đường ray, đó là một sự thay thế
ngôn ngữ PHP.

60
00:03:13,580 --> 00:03:14,900
Ngôn ngữ học tính toán.

61
00:03:14,900 --> 00:03:18,710
Giới thiệu về iOS, đó là
nền tảng được sử dụng cho iPhone và

62
00:03:18,710 --> 00:03:19,850
phát triển iPad.

63
00:03:19,850 --> 00:03:22,890
JavaScript cho Web Apps, chúng tôi sẽ giới thiệu
đó, nhưng trong buổi hội thảo này, bạn sẽ đi

64
00:03:22,890 --> 00:03:24,070
vào chi tiết hơn.

65
00:03:24,070 --> 00:03:27,390
>> Nhảy chuyển động, vì vậy chúng tôi sẽ thực sự có một số
bạn bè của chúng tôi từ Leap Motion,

66
00:03:27,390 --> 00:03:29,160
các công ty riêng của mình, chúng tôi tham gia.

67
00:03:29,160 --> 00:03:31,800
Ngày mai, trên thực tế, để cung cấp
một thực hành hội thảo, nếu

68
00:03:31,800 --> 00:03:33,320
quan tâm đến bạn.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, một kỹ thuật thay thế cho
không sử dụng JavaScript trong trình duyệt,

70
00:03:38,770 --> 00:03:39,970
nhưng trên một máy chủ.

71
00:03:39,970 --> 00:03:42,110
Node.js, mà là rất nhiều
trong tĩnh mạch đó là tốt.

72
00:03:42,110 --> 00:03:43,650
Thiết kế kiểu dáng đẹp Android.

73
00:03:43,650 --> 00:03:46,990
Android là một lựa chọn rất phổ biến
iOS và Windows Phone

74
00:03:46,990 --> 00:03:48,790
và các nền tảng di động khác.

75
00:03:48,790 --> 00:03:51,180
Và Web Security đăng nhập Quốc phòng.

76
00:03:51,180 --> 00:03:54,590
>> Vì vậy, trong thực tế, nếu bạn muốn
tham gia trong này, chúng tôi

77
00:03:54,590 --> 00:03:55,840
làm cho lưu ý về điều này.

78
00:03:55,840 --> 00:03:57,790
Chúng tôi rất vui khi nói rằng
bạn bè của chúng tôi tại Leap

79
00:03:57,790 --> 00:03:59,140
Chuyển động, đó là một khởi động -

80
00:03:59,140 --> 00:04:01,300
thiết bị này thực sự chỉ đến
ra cách đây vài tháng -

81
00:04:01,300 --> 00:04:05,960
đã ân cần tặng 30 thiết bị như vậy
đến lớp cho càng nhiều học sinh, nếu

82
00:04:05,960 --> 00:04:08,670
bạn muốn mượn phần cứng
hướng tới kết thúc học kỳ và sử dụng nó cho

83
00:04:08,670 --> 00:04:10,390
một dự án cuối cùng thực tế.

84
00:04:10,390 --> 00:04:11,890
Họ hỗ trợ một số ngôn ngữ.

85
00:04:11,890 --> 00:04:16,040
Ai trong số họ C, không ai trong số họ PHP, do đó
nhận ra một hoặc nhiều các cuộc hội thảo

86
00:04:16,040 --> 00:04:16,899
có thể chứng minh quan tâm.

87
00:04:16,899 --> 00:04:19,730
Và tất cả chúng sẽ được quay trong
trường hợp bạn không thể

88
00:04:19,730 --> 00:04:21,380
tham dự trong người.

89
00:04:21,380 --> 00:04:25,000
Lịch trình được công bố thông qua
email như chúng ta củng cố phòng.

90
00:04:25,000 --> 00:04:28,460
>> Và cuối cùng, nếu bạn đi đến
projects.cs.50.net, đây là một trang web

91
00:04:28,460 --> 00:04:31,450
chúng tôi duy trì mỗi năm mà chúng tôi mời
folks từ cộng đồng, giảng viên,

92
00:04:31,450 --> 00:04:36,420
các phòng ban, nhân viên, và cả hai
trong một bên ngoài của CS50 để

93
00:04:36,420 --> 00:04:37,730
đề xuất ý tưởng dự án.

94
00:04:37,730 --> 00:04:39,050
Những điều quan tâm đến các nhóm sinh viên.

95
00:04:39,050 --> 00:04:40,600
Những điều quan tâm cho các phòng ban.

96
00:04:40,600 --> 00:04:43,990
Do đó, biến đó nếu bạn đang gặp khó khăn
với sự không chắc chắn về những gì bạn

97
00:04:43,990 --> 00:04:46,700
mình muốn để giải quyết.

98
00:04:46,700 --> 00:04:51,760
>> Vì vậy, thời gian qua, chúng tôi đã giới thiệu cho là
cấu trúc dữ liệu phức tạp hơn chúng tôi

99
00:04:51,760 --> 00:04:53,300
nhìn thấy trong tuần qua.

100
00:04:53,300 --> 00:04:56,550
Chúng tôi đã sử dụng các mảng khá
hạnh phúc như một hữu ích nếu

101
00:04:56,550 --> 00:04:58,160
cấu trúc dữ liệu đơn giản.

102
00:04:58,160 --> 00:05:00,570
Sau đó, chúng tôi giới thiệu này, mà
tất nhiên là danh sách liên kết.

103
00:05:00,570 --> 00:05:05,470
Và những gì là một trong những động lực cho
giới thiệu cấu trúc dữ liệu này?

104
00:05:05,470 --> 00:05:06,930
Yeah?

105
00:05:06,930 --> 00:05:07,250
Đó là những gì?

106
00:05:07,250 --> 00:05:08,080
>> ĐỐI TƯỢNG: kích thước động.

107
00:05:08,080 --> 00:05:09,040
>> DAVID Malan: kích thước động.

108
00:05:09,040 --> 00:05:11,890
Vì vậy, trong khi ở mảng, bạn phải
biết kích thước của nó trước khi

109
00:05:11,890 --> 00:05:12,740
bạn phân bổ nó.

110
00:05:12,740 --> 00:05:14,380
Trong danh sách liên kết, bạn không
phải biết điều đó.

111
00:05:14,380 --> 00:05:17,610
Bạn có thể chỉ malloc, hay rộng hơn,
phân bổ thêm

112
00:05:17,610 --> 00:05:20,720
nút, có thể nói, bất cứ lúc nào bạn
muốn chèn dữ liệu hơn.

113
00:05:20,720 --> 00:05:22,670
Và nút đã không được xác định trước ý nghĩa.

114
00:05:22,670 --> 00:05:25,580
Nó chỉ là một thuật ngữ chung mô tả
một số loại container chúng tôi

115
00:05:25,580 --> 00:05:29,610
sử dụng trong cấu trúc dữ liệu của chúng tôi để lưu trữ
một số mặt hàng quan tâm, mà trong này

116
00:05:29,610 --> 00:05:31,750
trường hợp xảy ra là các số nguyên.

117
00:05:31,750 --> 00:05:33,160
>> Nhưng luôn có một sự cân bằng.

118
00:05:33,160 --> 00:05:38,070
Vì vậy chúng tôi có được kích thước năng động của các dữ liệu
cấu trúc, nhưng những gì chúng tôi phải trả giá?

119
00:05:38,070 --> 00:05:40,040
Các nhược điểm của danh sách liên kết là gì?

120
00:05:40,040 --> 00:05:41,006
Yeah?

121
00:05:41,006 --> 00:05:41,980
>> ĐỐI TƯỢNG: Yêu cầu bộ nhớ hơn.

122
00:05:41,980 --> 00:05:44,240
>> DAVID Malan: Nó đòi hỏi hơn
bộ nhớ, làm thế nào chính xác?

123
00:05:44,240 --> 00:05:46,440
>> ĐỐI TƯỢNG: [nghe được].

124
00:05:46,440 --> 00:05:47,050
>> DAVID Malan: Chính xác.

125
00:05:47,050 --> 00:05:50,460
Vì vậy, bây giờ chúng tôi đã gợi ý đi lên
bộ nhớ bổ sung mà chúng tôi trước đây

126
00:05:50,460 --> 00:05:53,040
không cần, bởi vì lợi thế
của một mảng, tất nhiên, là

127
00:05:53,040 --> 00:05:54,860
tất cả mọi thứ là liên tục, trở lại
để sao để trở lại, mà

128
00:05:54,860 --> 00:05:56,380
cung cấp cho bạn truy cập ngẫu nhiên.

129
00:05:56,380 --> 00:06:00,710
Bởi vì chỉ bằng cách sử dụng khung vuông
ký hiệu, hoặc kỹ thuật hơn con trỏ

130
00:06:00,710 --> 00:06:03,580
số học, bổ sung rất đơn giản,
bạn có thể truy cập bất kỳ

131
00:06:03,580 --> 00:06:05,700
các yếu tố trong thời gian liên tục.

132
00:06:05,700 --> 00:06:08,975
Và trong thực tế, đó là loại ám chỉ
khác giá mà chúng ta đang phải trả với một

133
00:06:08,975 --> 00:06:09,760
danh sách liên kết.

134
00:06:09,760 --> 00:06:13,890
>> Điều gì xảy ra thời gian chạy của
một cái gì đó như tìm kiếm, nếu tôi muốn

135
00:06:13,890 --> 00:06:17,270
tìm thấy một số giá trị và bên trong
của một danh sách liên kết?

136
00:06:17,270 --> 00:06:20,290
Không thời gian chạy của tôi trở thành những gì?

137
00:06:20,290 --> 00:06:21,560
O lớn của n.

138
00:06:21,560 --> 00:06:24,060
Nếu nó được sắp xếp để?

139
00:06:24,060 --> 00:06:25,440
Nếu cấu trúc dữ liệu được sắp xếp?

140
00:06:25,440 --> 00:06:28,640
Tôi có thể làm tốt hơn so với lớn
O của n để tìm kiếm?

141
00:06:28,640 --> 00:06:31,700
Không, bởi vì trong trường hợp xấu nhất nó có thể
rất tốt được sắp xếp, nhưng số lượng

142
00:06:31,700 --> 00:06:32,950
bạn đang tìm kiếm có thể là lớn.

143
00:06:32,950 --> 00:06:35,370
Nó có thể là số 100,
có thể xảy ra được tất cả

144
00:06:35,370 --> 00:06:36,410
cách ở cuối.

145
00:06:36,410 --> 00:06:39,950
Và bởi vì bạn chỉ có thể truy cập vào một liên kết
danh sách trong thực hiện điều này bằng cách

146
00:06:39,950 --> 00:06:42,690
cách của nút đầu tiên, bạn
vẫn còn loại ra khỏi may mắn.

147
00:06:42,690 --> 00:06:47,450
Bạn phải đi qua toàn bộ điều
từ đầu đến cuối để tìm ra

148
00:06:47,450 --> 00:06:49,150
có giá trị lớn như 100.

149
00:06:49,150 --> 00:06:51,350
Hoặc để xác định xem nó
thậm chí không có.

150
00:06:51,350 --> 00:06:55,960
>> Vì vậy, chúng tôi không thể làm những gì thuật toán trong một dữ liệu
cấu trúc trông như thế này?

151
00:06:55,960 --> 00:06:59,460
Chúng ta không thể thực hiện tìm kiếm nhị phân, vì
tìm kiếm nhị phân cần thiết mà chúng tôi đã

152
00:06:59,460 --> 00:07:00,740
truy cập ngẫu nhiên.

153
00:07:00,740 --> 00:07:04,500
Chúng tôi chỉ có thể nhảy từ vị trí đến
vị trí mà không cần phải theo

154
00:07:04,500 --> 00:07:07,080
những mẩu bánh mì trong các hình thức
của tất cả các con trỏ.

155
00:07:07,080 --> 00:07:08,300
>> Bây giờ, làm thế nào chúng ta thực hiện điều này?

156
00:07:08,300 --> 00:07:12,830
Vâng, nếu chúng ta đi vào màn hình ở đây, nếu
chúng ta có thể nhanh chóng reimplement dữ liệu này

157
00:07:12,830 --> 00:07:13,440
cấu trúc -

158
00:07:13,440 --> 00:07:15,670
chữ viết tay của tôi không phải là tất cả những gì
tuyệt vời ở đây, nhưng chúng tôi sẽ cố gắng.

159
00:07:15,670 --> 00:07:22,030
Vì vậy, cấu trúc typedef, và những gì đã làm tôi
muốn gọi điều này ở đây?

160
00:07:22,030 --> 00:07:22,960
Nút.

161
00:07:22,960 --> 00:07:24,580
Vì vậy, tôi sẽ nhận được chúng tôi bắt đầu.

162
00:07:24,580 --> 00:07:27,860
Và bây giờ, những gì cần phải được bên trong
cấu trúc dữ liệu cho rằng đơn lẻ

163
00:07:27,860 --> 00:07:28,430
danh sách liên kết?

164
00:07:28,430 --> 00:07:29,950
Làm thế nào nhiều lĩnh vực?

165
00:07:29,950 --> 00:07:30,450
>> Vì vậy, hai.

166
00:07:30,450 --> 00:07:31,570
Một là khá dễ dàng.

167
00:07:31,570 --> 00:07:33,050
Vì vậy, int n.

168
00:07:33,050 --> 00:07:35,930
Và chúng ta có thể gọi bất cứ điều gì n chúng ta muốn,
nhưng nó phải là một int nếu chúng ta

169
00:07:35,930 --> 00:07:37,660
thực hiện một danh sách liên kết cho số nguyên.

170
00:07:37,660 --> 00:07:41,920
Và bây giờ những gì hiện thứ hai
lĩnh vực có được?

171
00:07:41,920 --> 00:07:43,460
Struct node *.

172
00:07:43,460 --> 00:07:50,570
Vì vậy, nếu tôi làm cấu trúc nút *, và sau đó tôi
có thể gọi này cũng bất cứ điều gì tôi muốn,

173
00:07:50,570 --> 00:07:53,510
nhưng chỉ để được rõ ràng tôi sẽ gọi
nó bên cạnh, như chúng tôi đã làm.

174
00:07:53,510 --> 00:07:55,270
Và sau đó tôi sẽ đóng dấu ngoặc nhọn của tôi.

175
00:07:55,270 --> 00:08:00,700
>> Và bây giờ, như thời gian qua,
Tôi đặt nút xuống đây.

176
00:08:00,700 --> 00:08:03,830
Nhưng nếu tôi tuyên bố này như một
nút, tại sao tôi bận tâm được như vậy

177
00:08:03,830 --> 00:08:07,320
tiết ở đây trong tuyên bố cấu trúc
nút * tiếp theo, như trái ngược

178
00:08:07,320 --> 00:08:09,210
chỉ nút * tiếp theo?

179
00:08:09,210 --> 00:08:09,904
Yeah?

180
00:08:09,904 --> 00:08:12,810
>> ĐỐI TƯỢNG: [nghe được].

181
00:08:12,810 --> 00:08:14,050
>> DAVID Malan: Chính xác.

182
00:08:14,050 --> 00:08:14,530
Chính xác.

183
00:08:14,530 --> 00:08:18,320
Bởi vì C thực sự sẽ đưa bạn theo nghĩa đen và
chỉ nhìn thấy định nghĩa của nút

184
00:08:18,320 --> 00:08:21,230
đường xuống đây, bạn có thể không
đề cập đến nó ở đây.

185
00:08:21,230 --> 00:08:24,760
Vì vậy, chúng tôi có loại này ưu tiên
khai ở đây, đó là thừa nhận

186
00:08:24,760 --> 00:08:25,390
chi tiết hơn.

187
00:08:25,390 --> 00:08:27,810
Cấu trúc nút, điều đó có nghĩa
bây giờ chúng tôi có thể truy cập

188
00:08:27,810 --> 00:08:29,760
bên trong các cấu trúc dữ liệu.

189
00:08:29,760 --> 00:08:33,370
>> Và như một sang một bên, bởi vì đây là
trở thành một chút chủ quan hơn bây giờ,

190
00:08:33,370 --> 00:08:36,230
ngôi sao về mặt kỹ thuật có thể đi đây,
nó có thể đi đây, nó có thể

191
00:08:36,230 --> 00:08:37,179
thậm chí đi ở giữa.

192
00:08:37,179 --> 00:08:39,890
Chúng tôi đã được thông qua, trong hướng dẫn phong cách cho
quá trình, quy ước đặt

193
00:08:39,890 --> 00:08:42,299
ngôi sao ngay bên cạnh các dữ liệu
loại, mà trong trường hợp này,

194
00:08:42,299 --> 00:08:43,460
sẽ là nút cấu trúc.

195
00:08:43,460 --> 00:08:46,620
Nhưng nhận ra trong rất nhiều sách giáo khoa và
tài liệu tham khảo trực tuyến, bạn có thể thực sự

196
00:08:46,620 --> 00:08:48,450
nhìn thấy nó ở phía bên kia.

197
00:08:48,450 --> 00:08:52,200
Nhưng chỉ nhận ra rằng cả hai sẽ thực sự
làm việc và bạn chỉ cần có

198
00:08:52,200 --> 00:08:52,970
phù hợp.

199
00:08:52,970 --> 00:08:53,580
>> Được rồi.

200
00:08:53,580 --> 00:08:55,630
Vì vậy, đó là tuyên bố của chúng tôi
của nút cấu trúc.

201
00:08:55,630 --> 00:08:59,430
Nhưng sau đó chúng tôi bắt đầu làm nhiều hơn
những chuyện phức tạp.

202
00:08:59,430 --> 00:09:03,410
Ví dụ, chúng tôi quyết định giới thiệu
một cái gì đó giống như một bảng băm.

203
00:09:03,410 --> 00:09:08,160
Vì vậy, đây là một bảng băm kích thước n,
lập chỉ mục từ 0 phía trên bên trái để n

204
00:09:08,160 --> 00:09:09,690
trừ 1 trên dưới cùng bên trái.

205
00:09:09,690 --> 00:09:11,640
Điều này có thể là một băm
bảng cho bất cứ điều gì.

206
00:09:11,640 --> 00:09:15,340
Nhưng những gì các loại điều đã làm chúng tôi nói chuyện
về việc sử dụng một bảng băm cho?

207
00:09:15,340 --> 00:09:18,370
Lưu trữ những gì?

208
00:09:18,370 --> 00:09:18,800
>> Tên.

209
00:09:18,800 --> 00:09:20,870
Chúng ta có thể làm những cái tên như
chúng tôi đã làm thời gian qua.

210
00:09:20,870 --> 00:09:22,200
Và thực sự, bạn có thể lưu trữ bất cứ điều gì.

211
00:09:22,200 --> 00:09:24,640
Và chúng ta sẽ thấy điều này một lần nữa trong
PHP và JavaScript.

212
00:09:24,640 --> 00:09:28,550
Một bảng băm là một loại tốt đẹp của Thụy Sĩ
Quân đội dao cho phép bạn lưu trữ

213
00:09:28,550 --> 00:09:33,690
khá nhiều bất cứ điều gì bạn muốn bên trong
nó bằng cách kết hợp các phím với các giá trị.

214
00:09:33,690 --> 00:09:34,770
Phím với các giá trị.

215
00:09:34,770 --> 00:09:37,800
>> Bây giờ trong trường hợp này đơn giản, chúng tôi
phím chỉ là con số.

216
00:09:37,800 --> 00:09:40,380
Chúng tôi đang thực hiện một băm
bảng như là một mảng.

217
00:09:40,380 --> 00:09:43,500
Và như vậy các phím 0,
1, 2, và vv.

218
00:09:43,500 --> 00:09:47,200
Và vì vậy chúng tôi, như con người, quyết định cuối cùng
tuần bạn biết những gì, nếu chúng ta

219
00:09:47,200 --> 00:09:50,410
sẽ tên cửa hàng, chúng ta hãy chỉ
tùy tiện, nhưng khá hợp lý,

220
00:09:50,410 --> 00:09:54,680
giả định rằng Alice, một tên A,
sẽ chỉ được lập chỉ mục vào 0.

221
00:09:54,680 --> 00:09:58,030
Và Bob, một tên B, sẽ được lập chỉ mục
vào 1, và vv.

222
00:09:58,030 --> 00:10:02,490
Vì vậy, chúng tôi đã có một ánh xạ giữa đầu vào,
đó là chuỗi, và băm

223
00:10:02,490 --> 00:10:04,560
địa điểm, đó là những con số.

224
00:10:04,560 --> 00:10:07,740
>> Vì vậy, quá trình đó thường được gọi là
một hàm băm, và bạn có thể thực sự

225
00:10:07,740 --> 00:10:09,130
thực hiện nó trong mã.

226
00:10:09,130 --> 00:10:12,080
Nếu tôi muốn thực hiện một hàm băm
thực hiện chính xác những gì chúng tôi

227
00:10:12,080 --> 00:10:17,070
vừa mô tả từ thời gian qua, tôi có thể
khai báo một hàm mà có, như

228
00:10:17,070 --> 00:10:18,330
đầu vào ví dụ -

229
00:10:18,330 --> 00:10:22,190
và chúng ta hãy làm điều này trên này
màn hình trên đây.

230
00:10:22,190 --> 00:10:26,180
Nếu tôi muốn thực hiện một băm
chức năng, tôi có thể nói

231
00:10:26,180 --> 00:10:27,410
một cái gì đó như thế này.

232
00:10:27,410 --> 00:10:29,030
>> Nó sẽ trả lại một int.

233
00:10:29,030 --> 00:10:33,600
Nó sẽ được gọi là băm, và nó
sẽ chấp nhận như là một đối một

234
00:10:33,600 --> 00:10:38,920
chuỗi, hoặc chúng ta có thể thích hợp hơn bây giờ,
và nói char *, chúng tôi sẽ gọi nó là s.

235
00:10:38,920 --> 00:10:43,840
Và sau đó tất cả các chức năng này đã làm,
cuối cùng, được trả lại một int.

236
00:10:43,840 --> 00:10:45,990
Bây giờ, làm thế nào nó mà có thể
không thể rõ ràng.

237
00:10:45,990 --> 00:10:49,510
Tôi sẽ thực hiện điều này mà không cần bất kỳ
hình thành kiểm tra lỗi ngay bây giờ.

238
00:10:49,510 --> 00:10:55,740
Tôi chỉ cần đi một cách mù quáng nói, trở về
bất cứ điều gì là s khung 0, trừ,

239
00:10:55,740 --> 00:10:58,850
hãy nói, vốn Một dấu chấm phẩy.

240
00:10:58,850 --> 00:10:59,960
>> Hoàn toàn bị phá vỡ.

241
00:10:59,960 --> 00:11:02,620
Nó không phải là hoàn hảo bởi vì
một, những gì nếu s là vô giá trị?

242
00:11:02,620 --> 00:11:04,000
Những điều xấu sẽ xảy ra.

243
00:11:04,000 --> 00:11:07,940
Hai, nếu chữ cái đầu tiên trong này
tên không phải là một bức thư vốn?

244
00:11:07,940 --> 00:11:09,860
Điều đó sẽ không biến
hiện tốt một trong hai.

245
00:11:09,860 --> 00:11:11,970
Nó có thể là một chữ thường
hoặc không phải là một thư nào cả.

246
00:11:11,970 --> 00:11:15,520
Vì vậy, hoàn toàn phòng để cải thiện đây,
nhưng đây là ý tưởng cơ bản.

247
00:11:15,520 --> 00:11:19,010
>> Những gì chúng tôi mô tả tuần trước bằng lời nói như
chỉ là một quá trình lập bản đồ Alice

248
00:11:19,010 --> 00:11:23,360
0 và Bob tới 1 có thể được thể hiện
chắc chắn formulaically hơn như là một C

249
00:11:23,360 --> 00:11:24,320
hoạt động ở đây.

250
00:11:24,320 --> 00:11:28,630
Gọi lại băm, phải mất một chuỗi như
đầu vào, và sau đó bằng cách nào đó làm điều gì đó

251
00:11:28,630 --> 00:11:31,020
với đầu vào để sản xuất một đầu ra.

252
00:11:31,020 --> 00:11:34,130
Không giống như mô tả hộp đen của chúng tôi
mà chúng tôi đã thực hiện lâu.

253
00:11:34,130 --> 00:11:36,550
Tôi không biết làm thế nào điều này có thể
làm việc bên dưới mui xe.

254
00:11:36,550 --> 00:11:40,120
>> Cho bộ vấn đề 6, một trong những thách thức
là để bạn có thể quyết định những gì

255
00:11:40,120 --> 00:11:41,920
hàm băm của bạn sẽ được?

256
00:11:41,920 --> 00:11:45,760
Những gì sẽ là bên trong đó màu đen
hộp, và có lẽ, nó sẽ là một

257
00:11:45,760 --> 00:11:50,380
nhiều hơn một chút thú vị hơn này, và
chắc chắn dễ bị lỗi

258
00:11:50,380 --> 00:11:53,180
kiểm tra hơn đặc biệt này
thực hiện.

259
00:11:53,180 --> 00:11:54,580
>> Nhưng vấn đề có thể phát sinh, phải không?

260
00:11:54,580 --> 00:11:57,760
Nếu chúng ta có một cấu trúc dữ liệu như thế này
một, là những gì một trong những vấn đề

261
00:11:57,760 --> 00:12:01,600
bạn có thể chạy vào theo thời gian khi bạn chèn
ngày càng có nhiều tên vào

262
00:12:01,600 --> 00:12:02,880
bảng băm?

263
00:12:02,880 --> 00:12:04,630
Bạn nhận được va chạm, phải không?

264
00:12:04,630 --> 00:12:07,560
Nếu bạn có Alice và Aaron,
hai người có tên đã xảy ra

265
00:12:07,560 --> 00:12:08,190
để bắt đầu với A?

266
00:12:08,190 --> 00:12:11,660
Đó đặt ra câu hỏi, nơi bạn
đặt thứ hai như một tên?

267
00:12:11,660 --> 00:12:15,050
>> Vâng, bạn có thể ngây thơ chỉ cần đặt nó
nơi Bob thuộc, nhưng sau đó Bob là

268
00:12:15,050 --> 00:12:17,300
loại hơi say nếu bạn cố gắng
chèn tên của mình bên cạnh và

269
00:12:17,300 --> 00:12:18,240
không có chỗ cho anh ta.

270
00:12:18,240 --> 00:12:21,400
Vì vậy, bạn có thể đặt Bob nơi Charlie,
và bạn có thể tưởng tượng này rất nhanh chóng

271
00:12:21,400 --> 00:12:23,020
phân cấp vào một chút của một mớ hỗn độn.

272
00:12:23,020 --> 00:12:25,600
Một cái gì đó tuyến tính cuối cùng, nơi bạn
chỉ cần tìm kiếm trên toàn bộ điều

273
00:12:25,600 --> 00:12:28,190
tìm kiếm Alice hay Bob
hoặc Aaron hoặc Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Vì vậy, thay vào đó chúng tôi đề xuất, thay vì chỉ
tuyến tính thăm dò cho các không gian mở

275
00:12:33,230 --> 00:12:36,450
và nhúng cả những cái tên đó, chúng tôi
đề xuất một phương pháp tiếp cận fancier.

276
00:12:36,450 --> 00:12:41,740
Một bảng băm thực hiện vẫn có một
mảng của các chỉ số, nhưng các loại dữ liệu

277
00:12:41,740 --> 00:12:44,500
những chỉ số bây giờ là con trỏ.

278
00:12:44,500 --> 00:12:47,360
Con trỏ đến những gì?

279
00:12:47,360 --> 00:12:48,730
Con trỏ đến danh sách liên kết.

280
00:12:48,730 --> 00:12:53,330
>> Vì nói lại là một danh sách liên kết là
thực sự chỉ là một con trỏ tới một nút, và

281
00:12:53,330 --> 00:12:57,110
nút có một lĩnh vực tiếp theo, và nút đó
có một lĩnh vực tiếp theo, và vv.

282
00:12:57,110 --> 00:13:00,690
Vì vậy, bây giờ bạn có thể nghĩ đến mảng này trên
phía bên tay trái của một bảng băm như

283
00:13:00,690 --> 00:13:01,820
dẫn đến một danh sách liên kết.

284
00:13:01,820 --> 00:13:07,000
Ưu điểm của nó là nếu bạn nhận được một
va chạm giữa Alice và Aaron,

285
00:13:07,000 --> 00:13:09,300
bạn sẽ làm gì với
thứ hai người như thế?

286
00:13:09,300 --> 00:13:14,150
Bạn chỉ cần đính kèm anh ta hoặc cô đến
kết thúc, hoặc thậm chí đầu

287
00:13:14,150 --> 00:13:15,490
trong đó danh sách liên kết.

288
00:13:15,490 --> 00:13:17,340
>> Và thực sự, chúng ta hãy chỉ ăn liền thông qua
đó chỉ là một thứ hai.

289
00:13:17,340 --> 00:13:18,640
Mà sẽ làm cho ý nghĩa nhất?

290
00:13:18,640 --> 00:13:22,060
Nếu tôi đưa Alice và cô ấy kết thúc tại
vị trí đầu tiên, sau đó tôi cố gắng

291
00:13:22,060 --> 00:13:25,310
chèn tên A-rôn, và có
rõ ràng là một vụ va chạm, tôi nên đặt

292
00:13:25,310 --> 00:13:27,400
ông ngay từ đầu
của danh sách liên kết?

293
00:13:27,400 --> 00:13:30,944
Đó là ở vị trí đầu tiên,
hoặc ở cuối?

294
00:13:30,944 --> 00:13:31,440
>> ĐỐI TƯỢNG: [nghe được].

295
00:13:31,440 --> 00:13:31,990
>> DAVID Malan: OK.

296
00:13:31,990 --> 00:13:32,490
Tôi nghe nói bắt đầu.

297
00:13:32,490 --> 00:13:33,903
Tại sao ngay từ đầu?

298
00:13:33,903 --> 00:13:34,750
>> ĐỐI TƯỢNG: [nghe được].

299
00:13:34,750 --> 00:13:34,940
>> DAVID Malan: OK.

300
00:13:34,940 --> 00:13:36,520
Đó là chữ cái, vì vậy đó là tốt đẹp.

301
00:13:36,520 --> 00:13:37,330
Đó là một tài sản tốt.

302
00:13:37,330 --> 00:13:39,335
Nó sẽ tiết kiệm cho tôi một số thời gian có khả năng.

303
00:13:39,335 --> 00:13:43,290
Nó sẽ không cho phép tôi làm tìm kiếm nhị phân, nhưng tôi
có thể ít nhất có thể để thoát ra khỏi

304
00:13:43,290 --> 00:13:47,340
của một vòng lặp nếu tôi nhận ra, tốt, tôi là cách
qua là Aaron sẽ là trong này

305
00:13:47,340 --> 00:13:48,310
sắp xếp danh sách liên kết.

306
00:13:48,310 --> 00:13:50,360
Tôi không cần phải lãng phí thời gian của tôi đang tìm
tất cả các cách để kết thúc.

307
00:13:50,360 --> 00:13:51,530
Vì vậy, đó là hợp lý.

308
00:13:51,530 --> 00:13:54,710
Tại sao khác bạn có thể chèn
tên va chạm vào

309
00:13:54,710 --> 00:13:56,660
đầu danh sách?

310
00:13:56,660 --> 00:13:57,397
Đó là những gì?

311
00:13:57,397 --> 00:13:58,680
>> ĐỐI TƯỢNG: [nghe được].

312
00:13:58,680 --> 00:14:00,820
>> DAVID Malan: Nó có thể mất một thời gian dài
để đến cuối danh sách.

313
00:14:00,820 --> 00:14:02,490
Và trong thực tế, lâu hơn và lâu hơn.

314
00:14:02,490 --> 00:14:04,920
Tên hơn bạn chèn mà
bắt đầu với A, dài hơn

315
00:14:04,920 --> 00:14:06,280
dây chuyền là sẽ nhận được.

316
00:14:06,280 --> 00:14:07,890
Dài mà liên kết
danh sách sẽ nhận được.

317
00:14:07,890 --> 00:14:09,420
Vì vậy, bạn thực sự chỉ
lãng phí thời gian của bạn.

318
00:14:09,420 --> 00:14:14,070
Có lẽ bạn nên duy trì
thời điểm chèn liên tục, lớn O 1,

319
00:14:14,070 --> 00:14:18,470
bằng cách luôn đặt tên va chạm tại
đầu của danh sách liên kết,

320
00:14:18,470 --> 00:14:21,230
và không đáng lo ngại như nhiều
về phân loại.

321
00:14:21,230 --> 00:14:22,600
>> Câu trả lời tốt nhất là gì?

322
00:14:22,600 --> 00:14:23,320
Nó không rõ ràng.

323
00:14:23,320 --> 00:14:26,140
Nó loại phụ thuộc vào những gì
phân phối là, những gì mô hình là

324
00:14:26,140 --> 00:14:27,850
trong những cái tên bạn đang chèn.

325
00:14:27,850 --> 00:14:29,430
Nó không nhất thiết
một câu trả lời rõ ràng.

326
00:14:29,430 --> 00:14:33,100
Nhưng đây để, một lần nữa, là
một cơ hội thiết kế.

327
00:14:33,100 --> 00:14:37,220
>> Vì vậy, sau đó chúng tôi nhìn vào điều này,
thực sự là cơ hội lớn khác

328
00:14:37,220 --> 00:14:38,180
cho p-bộ 6.

329
00:14:38,180 --> 00:14:41,770
Và nhận ra, nếu bạn chưa có,
Zamyla lặn vào cả hai, băm

330
00:14:41,770 --> 00:14:43,260
bảng và cố gắng, chi tiết hơn.

331
00:14:43,260 --> 00:14:45,630
Và hương video
nhúng trong trang thiết lập thông số.

332
00:14:45,630 --> 00:14:46,590
Đây là một Trie -

333
00:14:46,590 --> 00:14:51,670
T-R-tôi-E. Và những gì là thú vị về
này là thời gian chạy

334
00:14:51,670 --> 00:14:59,510
tìm kiếm một tên, như Maxwell
thời gian qua, là O lớn của những gì?

335
00:14:59,510 --> 00:15:01,040
Đó là những gì?

336
00:15:01,040 --> 00:15:01,920
>> ĐỐI TƯỢNG: Số lượng các chữ cái.

337
00:15:01,920 --> 00:15:02,550
>> DAVID Malan: Số chữ cái.

338
00:15:02,550 --> 00:15:03,210
Tôi nghe nói hai điều.

339
00:15:03,210 --> 00:15:04,630
Số chữ cái và thời gian liên tục.

340
00:15:04,630 --> 00:15:05,540
Vì vậy, hãy đi với điều đó đầu tiên.

341
00:15:05,540 --> 00:15:06,410
Số lượng các chữ cái.

342
00:15:06,410 --> 00:15:10,195
Vâng, cấu trúc dữ liệu này, thu hồi, là
như một cái cây, một cây gia đình, mỗi

343
00:15:10,195 --> 00:15:12,860
các nút mà được tạo thành mảng.

344
00:15:12,860 --> 00:15:16,300
Và những mảng là con trỏ đến
các nút khác như vậy, hay như vậy khác

345
00:15:16,300 --> 00:15:17,670
mảng trong cây.

346
00:15:17,670 --> 00:15:22,890
>> Vì vậy, nếu chúng tôi muốn để sau đó xác định
dù Maxwell là ở đây, tôi có thể đi

347
00:15:22,890 --> 00:15:26,890
đến các mảng đầu tiên, ở phần trên của
cây, cái gọi là gốc, đầu

348
00:15:26,890 --> 00:15:30,521
các Trie, và sau đó theo con trỏ m,
sau đó là một con trỏ, sau đó x,

349
00:15:30,521 --> 00:15:31,710
w, e, l, l.

350
00:15:31,710 --> 00:15:34,910
Và sau đó khi tôi nhìn thấy một số biểu tượng đặc biệt,
ký hiệu ở đây như một hình tam giác.

351
00:15:34,910 --> 00:15:38,480
Trong mã bạn sẽ thấy chúng tôi đề nghị bạn
thực hiện như một bool, chỉ nói có

352
00:15:38,480 --> 00:15:40,540
hoặc không, một từ dừng lại ở đây.

353
00:15:40,540 --> 00:15:45,270
>> Vâng, một khi chúng tôi đã đi đến M-A-X-W-E-L-L,
cảm thấy như bảy, có thể

354
00:15:45,270 --> 00:15:48,910
tám nếu chúng ta đi một quá khứ nó, tám
bước sau để tìm Maxwell.

355
00:15:48,910 --> 00:15:53,050
Hoặc hãy gọi nó là K. Nhưng nhớ lại cuối cùng
thời gian, tôi cho rằng nếu có

356
00:15:53,050 --> 00:15:57,540
thực tế chiều dài tối đa trên một
từ, như nhân vật 40-một số lẻ, một

357
00:15:57,540 --> 00:16:00,810
tối đa chiều dài hàm ý
một giá trị không đổi.

358
00:16:00,810 --> 00:16:05,770
Vì vậy, thực sự, có, đó là O kỹ thuật lớn
8 hoặc 7, hoặc O thực sự lớn của K. Tuy nhiên,

359
00:16:05,770 --> 00:16:09,420
nếu có một giới hạn hữu hạn về những gì
K có thể được, đó là một hằng số.

360
00:16:09,420 --> 00:16:12,080
Và vì vậy nó lớn O của 1 tại
vào cuối ngày.

361
00:16:12,080 --> 00:16:13,040
>> Không trong thế giới thực.

362
00:16:13,040 --> 00:16:15,960
Không khi bạn thực sự bắt đầu xem
đồng hồ của bạn như chạy chương trình của bạn.

363
00:16:15,960 --> 00:16:20,690
Nó hoàn toàn sẽ là một chút
chậm hơn so với thực sự không đổi

364
00:16:20,690 --> 00:16:21,840
thời gian với một bước.

365
00:16:21,840 --> 00:16:25,540
Nó sẽ là bảy hay tám bước,
nhưng vẫn còn đó là nhiều, nhiều hơn

366
00:16:25,540 --> 00:16:30,080
hơn một thuật toán như O lớn của n mà
phụ thuộc vào kích thước của những gì trong

367
00:16:30,080 --> 00:16:31,220
cấu trúc dữ liệu.

368
00:16:31,220 --> 00:16:34,970
>> Nhận thấy xu hướng tăng giá ở đây là chúng ta có thể chèn
hơn một triệu tên thành này

369
00:16:34,970 --> 00:16:38,170
cấu trúc dữ liệu, nhưng có bao nhiêu bước nữa
là nó sẽ đưa chúng ta đến tìm

370
00:16:38,170 --> 00:16:40,480
Maxwell trong trường hợp đó?

371
00:16:40,480 --> 00:16:40,780
Không.

372
00:16:40,780 --> 00:16:41,820
Anh ấy không bị ảnh hưởng.

373
00:16:41,820 --> 00:16:45,480
Và cho đến nay, tôi không nghĩ rằng chúng tôi đã nhìn thấy
một ví dụ về một cấu trúc dữ liệu hoặc một

374
00:16:45,480 --> 00:16:48,560
thuật toán đó là hoàn toàn
không bị ảnh hưởng bởi bên ngoài

375
00:16:48,560 --> 00:16:50,040
hành vi như thế.

376
00:16:50,040 --> 00:16:51,160
Nhưng điều này không thể là tuyệt vời.

377
00:16:51,160 --> 00:16:52,900
Điều này không thể là giải pháp duy nhất
cho p-bộ

378
00:16:52,900 --> 00:16:53,570
>> Và nó không phải.

379
00:16:53,570 --> 00:16:55,980
Điều này không nhất thiết phải là dữ liệu
cấu trúc, bạn nên hút đến,

380
00:16:55,980 --> 00:16:58,220
vì như bảng băm, sự cân bằng.

381
00:16:58,220 --> 00:17:00,500
Giá mà bạn phải trả ở đây là gì?

382
00:17:00,500 --> 00:17:00,940
Bộ nhớ.

383
00:17:00,940 --> 00:17:02,890
Ý tôi là, đây là một tồi tệ
số lượng bộ nhớ.

384
00:17:02,890 --> 00:17:05,569
Và bạn không thể hoàn toàn thấy nó ở đây vì
tác giả của bức ảnh này

385
00:17:05,569 --> 00:17:09,420
rõ ràng là cắt ngắn tất cả các mảng,
và chúng tôi không nhìn thấy rất nhiều A và

386
00:17:09,420 --> 00:17:12,700
Của B và C và Q và Y
và Z trong các mảng.

387
00:17:12,700 --> 00:17:13,630
Nhưng họ đang có.

388
00:17:13,630 --> 00:17:17,660
>> Mỗi một nút đó là một mảng toàn bộ
của một số 26 hoặc nhiều byte, mỗi

389
00:17:17,660 --> 00:17:19,170
đại diện cho một thư.

390
00:17:19,170 --> 00:17:22,920
27 trong trường hợp của chúng tôi, để chúng tôi có thể hỗ trợ
dấu nháy trong bộ vấn đề.

391
00:17:22,920 --> 00:17:27,030
Vì vậy, cấu trúc dữ liệu này thực sự là,
thực sự dày đặc và rộng.

392
00:17:27,030 --> 00:17:30,880
Và rằng một mình có thể kết thúc chậm
điều xuống, hoặc ít nhất là chi phí cho bạn

393
00:17:30,880 --> 00:17:32,240
rất nhiều không gian.

394
00:17:32,240 --> 00:17:34,020
Nhưng một lần nữa, chúng ta có thể rút ra
so sánh ở đây.

395
00:17:34,020 --> 00:17:39,190
>> Nhớ lại một khi trở lại, chúng ta đạt được nhiều
thời gian hoạt động thú vị hơn trong sắp xếp

396
00:17:39,190 --> 00:17:42,880
khi chúng tôi sử dụng kết hợp phân loại, nhưng giá
chúng tôi trả tiền để đạt được n đăng nhập n cho hợp nhất

397
00:17:42,880 --> 00:17:46,930
loại yêu cầu mà chúng tôi dành
hơn những gì tài nguyên?

398
00:17:46,930 --> 00:17:47,690
Nhiều không gian hơn.

399
00:17:47,690 --> 00:17:50,530
Chúng tôi cần một mảng thứ
sao chép vào người, giống như

400
00:17:50,530 --> 00:17:51,620
chúng tôi đã làm ở đây trên sân khấu.

401
00:17:51,620 --> 00:17:55,880
Vì vậy, một lần nữa, không có người chiến thắng rõ ràng,
nhưng chỉ thiết kế chủ quan

402
00:17:55,880 --> 00:17:57,710
các quyết định được thực hiện.

403
00:17:57,710 --> 00:17:58,060
>> Được rồi.

404
00:17:58,060 --> 00:17:59,130
Vậy làm thế nào về điều này?

405
00:17:59,130 --> 00:18:02,050
Bất cứ ai cũng nhận ra D-Hall?

406
00:18:02,050 --> 00:18:02,440
OK.

407
00:18:02,440 --> 00:18:03,170
Vì vậy, ba chúng tôi làm.

408
00:18:03,170 --> 00:18:03,750
Mather nhà.

409
00:18:03,750 --> 00:18:05,070
Vì vậy, đây là cho ăn uống Mather của.

410
00:18:05,070 --> 00:18:09,650
Tôi sẽ đặt cược tất cả các nhà ăn có
ngăn xếp các khay như thế này.

411
00:18:09,650 --> 00:18:11,950
Và điều này thực sự là đại diện
của một cái gì đó chúng tôi đã

412
00:18:11,950 --> 00:18:13,050
rõ ràng là nhìn thấy rồi.

413
00:18:13,050 --> 00:18:14,850
Chúng tôi gọi nó theo nghĩa đen một chồng.

414
00:18:14,850 --> 00:18:18,970
Và ngăn xếp, trong điều khoản của bạn
bộ nhớ của máy tính, là nơi mà dữ liệu đi

415
00:18:18,970 --> 00:18:20,460
trong khi chức năng đang được gọi.

416
00:18:20,460 --> 00:18:23,410
>> Ví dụ, những loại điều đi
trên stack đối với với

417
00:18:23,410 --> 00:18:27,420
bố trí nhớ chúng tôi đã thảo luận
trong tuần qua?

418
00:18:27,420 --> 00:18:28,736
Đó là những gì?

419
00:18:28,736 --> 00:18:29,670
>> ĐỐI TƯỢNG: Các cuộc gọi đến các chức năng.

420
00:18:29,670 --> 00:18:30,260
>> DAVID Malan: Tôi xin lỗi.

421
00:18:30,260 --> 00:18:31,210
>> ĐỐI TƯỢNG: Các cuộc gọi đến các chức năng.

422
00:18:31,210 --> 00:18:33,590
>> DAVID Malan: Các cuộc gọi đến chức năng, nhưng
đặc biệt, bên trong của mỗi của những gì

423
00:18:33,590 --> 00:18:35,340
những khung?

424
00:18:35,340 --> 00:18:37,220
Những loại việc này?

425
00:18:37,220 --> 00:18:37,460
Vâng.

426
00:18:37,460 --> 00:18:38,500
Vì vậy, các biến địa phương.

427
00:18:38,500 --> 00:18:43,080
Bất cứ lúc nào chúng tôi cần một số lưu trữ địa phương,
như một tham số, hay int tôi, hay int

428
00:18:43,080 --> 00:18:45,940
tạm thời, hoặc bất cứ địa phương
biến được, chúng tôi đã

429
00:18:45,940 --> 00:18:47,210
đặt rằng trên stack.

430
00:18:47,210 --> 00:18:49,610
Và chúng tôi gọi nó là một chồng vì
của ý tưởng không giới hạn.

431
00:18:49,610 --> 00:18:52,940
Chỉ cần loại trận đấu với thực tế,
các khái niệm đó.

432
00:18:52,940 --> 00:18:56,650
>> Nhưng nó chỉ ra rằng một chồng cũng có thể
được xem như là một cấu trúc dữ liệu, một

433
00:18:56,650 --> 00:19:00,110
thay thế cho một mảng, một sự thay thế
một danh sách liên kết.

434
00:19:00,110 --> 00:19:02,770
Một cái gì đó khái niệm thú vị hơn
mà vẫn có thể được

435
00:19:02,770 --> 00:19:06,030
thực hiện bằng cách sử dụng một trong những người
điều, nhưng đó là một loại khác nhau của

436
00:19:06,030 --> 00:19:09,140
cấu trúc dữ liệu hỗ trợ, thực sự,
chỉ có hai hoạt động.

437
00:19:09,140 --> 00:19:11,000
Nhưng bạn có thể thêm vào fancier
tính năng hơn thế nữa.

438
00:19:11,000 --> 00:19:12,180
Nhưng đây là những điều cơ bản -

439
00:19:12,180 --> 00:19:13,510
đẩy và pop.

440
00:19:13,510 --> 00:19:19,240
>> Và ý tưởng với một chồng là nếu tôi
có đây, có hoặc không có Annenberg

441
00:19:19,240 --> 00:19:22,880
biết, một khay từ bên cạnh
với số 9 trên nó.

442
00:19:22,880 --> 00:19:23,870
Vì vậy chỉ cần một int.

443
00:19:23,870 --> 00:19:26,990
Và tôi muốn đẩy này vào dữ liệu
cấu trúc, mà chưa có hàng.

444
00:19:26,990 --> 00:19:28,790
Xem xét việc này dưới cùng của ngăn xếp.

445
00:19:28,790 --> 00:19:33,150
Tôi sẽ đẩy con số này lên 9
ngăn xếp, và bây giờ nó phải có.

446
00:19:33,150 --> 00:19:36,040
>> Nhưng điều thú vị về một chồng
là nếu bây giờ tôi muốn đẩy

447
00:19:36,040 --> 00:19:40,210
một số giá trị khác, như 17, và tôi đẩy
này vào ngăn xếp, tôi sẽ làm

448
00:19:40,210 --> 00:19:43,290
điều trực quan duy nhất, tôi chỉ cần đi
để đặt nó bên phải, nơi con người chúng ta

449
00:19:43,290 --> 00:19:45,180
sẽ được nghiêng để đặt nó, trên đầu trang.

450
00:19:45,180 --> 00:19:48,850
Nhưng điều thú vị tại
là, làm thế nào để tôi nhận được ở 9?

451
00:19:48,850 --> 00:19:50,670
Bạn biết đấy, tôi không phải không có một số nỗ lực.

452
00:19:50,670 --> 00:19:54,070
>> Vì vậy, những gì là thú vị về
một chồng là do thiết kế,

453
00:19:54,070 --> 00:19:56,330
đó là một cấu trúc dữ liệu LIFO.

454
00:19:56,330 --> 00:19:59,680
Cách ngớ ngẩn của mô tả
cuối cùng, đầu ra.

455
00:19:59,680 --> 00:20:03,280
Vì vậy, con số cuối cùng trong
tại thời điểm này là 17.

456
00:20:03,280 --> 00:20:07,540
Vì vậy, nếu tôi muốn một cái gì đó để bật tắt
của chồng, nó chỉ có thể là 17.

457
00:20:07,540 --> 00:20:11,890
Vì vậy, có một trật tự bắt buộc
hoạt động ở đây, nơi mà mục cuối cùng

458
00:20:11,890 --> 00:20:14,260
trong có phải là một trong những đầu tiên.

459
00:20:14,260 --> 00:20:16,440
Do đó các từ viết tắt, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Vì vậy, tại sao điều này có thể có ích?

461
00:20:19,160 --> 00:20:22,690
Là bối cảnh của họ, trong đó bạn sẽ
muốn có một cấu trúc dữ liệu như thế này?

462
00:20:22,690 --> 00:20:24,810
Vâng, nó chắc chắn là hữu ích
bên trong máy tính.

463
00:20:24,810 --> 00:20:29,050
Hệ thống hoạt động như vậy sử dụng rõ ràng này
loại cấu trúc dữ liệu cho ngăn xếp.

464
00:20:29,050 --> 00:20:32,800
Chúng tôi cũng sẽ thấy cùng một ý tưởng
khi nói đến các trang web.

465
00:20:32,800 --> 00:20:35,890
Vì vậy, trong tuần này và tuần tới và xa hơn nữa,
và khi bạn bắt đầu thực hiện web

466
00:20:35,890 --> 00:20:39,490
trang trong một ngôn ngữ được gọi là HTML, bạn có thể
thực sự sử dụng một cấu trúc dữ liệu như

467
00:20:39,490 --> 00:20:42,690
này để xác định xem trang
là định dạng đúng.

468
00:20:42,690 --> 00:20:47,170
Bởi vì chúng ta sẽ thấy tất cả các trang web theo
một loại hệ thống phân cấp, xẹp

469
00:20:47,170 --> 00:20:52,030
sẽ, vào cuối ngày, là một
cơ cấu cây bên dưới mui xe.

470
00:20:52,030 --> 00:20:53,620
Vì vậy, thêm vào đó trong chỉ là một chút.

471
00:20:53,620 --> 00:20:56,560
>> Nhưng bây giờ, chúng ta hãy đề nghị cho một
thời điểm, làm thế nào chúng ta có thể đi về

472
00:20:56,560 --> 00:20:58,830
đại diện cho những gì một chồng là?

473
00:20:58,830 --> 00:21:03,370
Hãy để tôi đề nghị chúng ta thực hiện
một chồng với mã như thế này.

474
00:21:03,370 --> 00:21:07,990
Vì vậy, một chồng là sẽ có bên trong của nó
hai điều, một mảng, được gọi là khay,

475
00:21:07,990 --> 00:21:09,510
chỉ để phù hợp với các bản demo.

476
00:21:09,510 --> 00:21:12,660
Và mỗi mục trong mảng
là có được một kiểu int.

477
00:21:12,660 --> 00:21:14,740
Và năng lực có lẽ là những gì?

478
00:21:14,740 --> 00:21:18,796
Bởi vì tôi đã không viết những
đầy đủ định nghĩa ở đây.

479
00:21:18,796 --> 00:21:21,535
>> Đó có lẽ là tối đa
kích thước của mảng.

480
00:21:21,535 --> 00:21:25,150
Và nó có thể khai báo là một sắc nét
xác định ở trên cùng của các tập tin, một số

481
00:21:25,150 --> 00:21:28,450
loại liên tục như ngụ ý của
chỉ giá trị vốn hóa.

482
00:21:28,450 --> 00:21:32,250
Vì vậy, ở đâu đó công suất được xác định
như kích thước tối đa có thể.

483
00:21:32,250 --> 00:21:35,590
Trong khi đó, bên trong các cấu trúc dữ liệu
được biết đến như một chồng có sẽ

484
00:21:35,590 --> 00:21:38,630
là một số nguyên chỉ được biết đến
đơn giản là kích thước.

485
00:21:38,630 --> 00:21:43,400
>> Vì vậy, nếu tôi được đại diện này ngay bây giờ
những bức tranh, chúng ta hãy giả sử rằng điều này

486
00:21:43,400 --> 00:21:48,070
hộp đen toàn bộ đại diện cho chồng tôi.

487
00:21:48,070 --> 00:21:50,070
Bên trong của nó là hai biến.

488
00:21:50,070 --> 00:21:54,780
Vì vậy, tôi sẽ vẽ
Người đầu tiên là kích thước.

489
00:21:54,780 --> 00:21:57,420
Và điều thứ hai tôi sẽ
để vẽ như là một mảng.

490
00:21:57,420 --> 00:22:01,060
>> Nhưng chỉ để giữ cho mọi thứ có trật tự,
bình thường tôi sẽ rút ra một mảng như thế

491
00:22:01,060 --> 00:22:04,910
này, nhưng đó là loại tốt đẹp
nếu chúng ta phù hợp với thực tế, hoặc

492
00:22:04,910 --> 00:22:06,230
phù hợp với mô hình tâm thần.

493
00:22:06,230 --> 00:22:12,880
Vì vậy, hãy để tôi thay vì vẽ mảng
theo chiều dọc, mà chỉ là, một lần nữa,

494
00:22:12,880 --> 00:22:13,840
màn biểu diễn của nghệ sĩ.

495
00:22:13,840 --> 00:22:16,610
Không thực sự có vấn đề gì đó
là bên dưới mui xe.

496
00:22:16,610 --> 00:22:20,350
Và chúng tôi sẽ nói rằng, theo mặc định,
khả năng là có được ba.

497
00:22:20,350 --> 00:22:23,480
Vì vậy, đây sẽ là vị trí 0, điều này
sẽ là vị trí 1, điều này

498
00:22:23,480 --> 00:22:25,740
sẽ là vị trí 2.

499
00:22:25,740 --> 00:22:29,330
>> Nếu tôi hối lộ với một quả bóng căng thẳng, sẽ
một người nào đó muốn đi lên và chạy

500
00:22:29,330 --> 00:22:30,870
hội đồng quản trị ở đây chỉ là một thời điểm?

501
00:22:30,870 --> 00:22:31,960
OK, thấy bàn tay của bạn đầu tiên.

502
00:22:31,960 --> 00:22:33,950
Lên đây.

503
00:22:33,950 --> 00:22:36,500
Được rồi.

504
00:22:36,500 --> 00:22:38,760
Vì vậy, tôi tin rằng đó là Steven.

505
00:22:38,760 --> 00:22:40,035
Lên đây.

506
00:22:40,035 --> 00:22:40,770
Được rồi.

507
00:22:40,770 --> 00:22:46,760
>> Nhưng giả sử bây giờ chúng ta quay lại với ban đầu
nhà nước trên thế giới mà tôi

508
00:22:46,760 --> 00:22:52,180
vừa tuyên bố một chồng, và nó
sẽ có công suất ba.

509
00:22:52,180 --> 00:22:54,470
Nhưng kích thước vẫn chưa được xác định.

510
00:22:54,470 --> 00:22:56,100
Khay chưa được xác định.

511
00:22:56,100 --> 00:22:57,300
Vì vậy, một vài câu hỏi đầu tiên.

512
00:22:57,300 --> 00:23:01,310
Và hãy để tôi cung cấp cho bạn mic để bạn có thể
cùng chia sẻ tích cực hơn trong việc này.

513
00:23:01,310 --> 00:23:05,190
>> Vì vậy, những gì bên trong kích thước tại thời điểm này
trong thời gian nếu tất cả tôi đã làm là

514
00:23:05,190 --> 00:23:09,340
tuyên bố một chồng với
một dòng mã?

515
00:23:09,340 --> 00:23:10,100
>> STEVEN: Không nhiều lắm.

516
00:23:10,100 --> 00:23:12,080
>> DAVID Malan: OK, không nhiều.

517
00:23:12,080 --> 00:23:14,410
Chúng ta biết những gì bên trong kích thước,
Chúng ta biết những gì bên trong

518
00:23:14,410 --> 00:23:16,330
của mảng này đây?

519
00:23:16,330 --> 00:23:18,630
>> STEVEN: Chỉ cần mã số ngẫu nhiên, phải không?

520
00:23:18,630 --> 00:23:20,220
Chỉ -

521
00:23:20,220 --> 00:23:23,230
>> DAVID Malan: Vâng, tôi sẽ
gọi nó là mã, nhưng ngẫu nhiên -

522
00:23:23,230 --> 00:23:23,820
>> STEVEN: điều.

523
00:23:23,820 --> 00:23:28,290
>> DAVID Malan: Những điều như ngẫu nhiên

524
00:23:28,290 --> 00:23:28,870
>> STEVEN: Bit.

525
00:23:28,870 --> 00:23:29,530
>> DAVID Malan: Bits, phải không?

526
00:23:29,530 --> 00:23:31,190
Vì vậy, các giá trị rác, phải không?

527
00:23:31,190 --> 00:23:33,470
Vì vậy, hoán vị của của 0 và 1.

528
00:23:33,470 --> 00:23:35,920
Chứng tích của tập quán trước
bộ nhớ này.

529
00:23:35,920 --> 00:23:38,150
Và chúng tôi không thực sự biết những gì các giá trị
được, vì vậy chúng tôi thường vẽ chúng

530
00:23:38,150 --> 00:23:38,930
là dấu hỏi.

531
00:23:38,930 --> 00:23:41,990
>> Vì vậy, điều đầu tiên chúng ta có lẽ
sẽ muốn làm ở đây -

532
00:23:41,990 --> 00:23:46,630
và hãy để tôi cung cấp cho lĩnh vực này trong
trong đó một tên - khay.

533
00:23:46,630 --> 00:23:49,540
Những gì nên chúng tôi có lẽ là khởi tạo
kích thước nếu chúng ta muốn

534
00:23:49,540 --> 00:23:51,040
bắt đầu sử dụng ngăn xếp này?

535
00:23:51,040 --> 00:23:53,070
>> STEVEN: Khay là phụ 3.

536
00:23:53,070 --> 00:23:53,910
>> DAVID Malan: Vì vậy, OK.

537
00:23:53,910 --> 00:23:56,710
Để được rõ ràng, công suất được khai báo
ở những nơi khác như ba.

538
00:23:56,710 --> 00:23:58,570
Và đó là những gì tôi đã sử dụng
phân bổ mảng.

539
00:23:58,570 --> 00:24:03,535
Kích thước sẽ đề cập đến bao nhiêu
khay hiện nay là trên stack.

540
00:24:03,535 --> 00:24:03,880
>> STEVEN: Zero.

541
00:24:03,880 --> 00:24:04,460
>> DAVID Malan: Vì vậy, nó phải là không.

542
00:24:04,460 --> 00:24:07,760
Nên đi trước, và với bất kỳ ngón tay,
rút ra một số không trong kích thước.

543
00:24:07,760 --> 00:24:08,440
Được rồi.

544
00:24:08,440 --> 00:24:10,920
Vì vậy, bây giờ, những gì bên trong này
ở đây, chúng ta không biết.

545
00:24:10,920 --> 00:24:12,160
Đây là những giá trị thực sự chỉ là rác.

546
00:24:12,160 --> 00:24:14,800
Vì vậy, chúng ta có thể rút ra những dấu hỏi, nhưng
chúng ta hãy giữ cho hội đồng quản trị sạch cho bây giờ

547
00:24:14,800 --> 00:24:16,300
bởi vì nó không quan trọng
những gì đang có.

548
00:24:16,300 --> 00:24:19,130
Chúng tôi không cần phải khởi tạo mảng
để bất cứ điều gì, bởi vì nếu chúng ta biết rằng

549
00:24:19,130 --> 00:24:23,100
kích thước của ngăn xếp là số không, tốt, chúng tôi
không nên nhìn vào bất cứ điều gì trong

550
00:24:23,100 --> 00:24:25,590
mảng này anyway tại
thời điểm này.

551
00:24:25,590 --> 00:24:29,970
>> Vì vậy, bây giờ giả sử rằng tôi đẩy
số 9 vào ngăn xếp.

552
00:24:29,970 --> 00:24:33,750
Làm thế nào chúng ta nên cập nhật các cấu trúc dữ liệu
bên trong của hộp đen này?

553
00:24:33,750 --> 00:24:35,540
Những giá trị cần phải thay đổi?

554
00:24:35,540 --> 00:24:36,200
>> STEVEN: Trong thời hạn -

555
00:24:36,200 --> 00:24:37,400
kích thước?

556
00:24:37,400 --> 00:24:37,650
>> DAVID Malan: OK.

557
00:24:37,650 --> 00:24:38,770
Kích thước nên trở thành những gì?

558
00:24:38,770 --> 00:24:39,580
>> STEVEN: Kích thước sẽ là một.

559
00:24:39,580 --> 00:24:39,870
>> DAVID Malan: OK.

560
00:24:39,870 --> 00:24:41,110
Vì vậy, kích thước nên trở thành một trong.

561
00:24:41,110 --> 00:24:42,540
Vì vậy, bạn có thể làm điều này trong một số cách.

562
00:24:42,540 --> 00:24:46,920
Hãy để tôi cho bạn, bây giờ của bạn
ngón tay là một cục tẩy.

563
00:24:46,920 --> 00:24:47,260
Được rồi.

564
00:24:47,260 --> 00:24:49,960
Sau đó bây giờ ngón tay của bạn là một bàn chải.

565
00:24:49,960 --> 00:24:50,330
Được rồi.

566
00:24:50,330 --> 00:24:52,820
Và bây giờ những gì người khác đã thay đổi,
rõ ràng, trong cấu trúc dữ liệu?

567
00:24:52,820 --> 00:24:57,060
>> Steven: Chúng tôi đang đi từ
từ dưới lên đến 9.

568
00:24:57,060 --> 00:24:57,760
>> DAVID Malan: 9.

569
00:24:57,760 --> 00:24:58,420
OK, tốt.

570
00:24:58,420 --> 00:25:01,550
Vì vậy, vẫn không có vấn đề gì là tại
vị trí một hoặc hai bởi vì họ

571
00:25:01,550 --> 00:25:04,520
giá trị rác, nhưng chúng ta không nên bận tâm
tìm kiếm ở đó bởi vì kích thước là

572
00:25:04,520 --> 00:25:07,540
nói với chúng tôi rằng chỉ có yếu tố đầu tiên
thực sự là hợp pháp.

573
00:25:07,540 --> 00:25:10,400
Vì vậy, bây giờ tôi đẩy 17 vào danh sách này.

574
00:25:10,400 --> 00:25:11,830
Những gì xảy ra cho hình ảnh này?

575
00:25:11,830 --> 00:25:14,720
>> STEVEN: Vì vậy, kích thước sẽ đi đến hai.

576
00:25:14,720 --> 00:25:15,300
>> DAVID Malan: OK.

577
00:25:15,300 --> 00:25:16,070
Bạn tẩy -

578
00:25:16,070 --> 00:25:16,810
oops.

579
00:25:16,810 --> 00:25:18,026
Bạn là một cục tẩy.

580
00:25:18,026 --> 00:25:18,840
>> STEVEN: Eraser.

581
00:25:18,840 --> 00:25:19,720
>> DAVID Malan: Bạn là một bàn chải.

582
00:25:19,720 --> 00:25:20,560
>> STEVEN: Brush.

583
00:25:20,560 --> 00:25:20,920
>> DAVID Malan: OK.

584
00:25:20,920 --> 00:25:21,600
Và những gì khác?

585
00:25:21,600 --> 00:25:22,600
>> STEVEN: Và sau đó chúng tôi -

586
00:25:22,600 --> 00:25:22,915
>> DAVID Malan: Chúng tôi đã đẩy 17.

587
00:25:22,915 --> 00:25:24,760
>> Steven: Chúng tôi dính vào 17 trên đầu, vì vậy -

588
00:25:24,760 --> 00:25:25,710
>> DAVID Malan: OK, tốt.

589
00:25:25,710 --> 00:25:27,040
>> Steven: - thả nó xuống.

590
00:25:27,040 --> 00:25:27,530
>> DAVID Malan: Được rồi.

591
00:25:27,530 --> 00:25:27,940
Nó nhận được dễ dàng.

592
00:25:27,940 --> 00:25:29,300
Tôi sẽ không để giúp bạn thời gian này.

593
00:25:29,300 --> 00:25:30,510
Đẩy 22.

594
00:25:30,510 --> 00:25:31,720
>> STEVEN: Xong.

595
00:25:31,720 --> 00:25:34,870
Trở thành một cục tẩy.

596
00:25:34,870 --> 00:25:37,340
Tôi trở thành một bàn chải.

597
00:25:37,340 --> 00:25:39,340
Và sau đó tôi đặt 22.

598
00:25:39,340 --> 00:25:40,100
>> DAVID Malan: 22.

599
00:25:40,100 --> 00:25:40,620
Tuyệt vời.

600
00:25:40,620 --> 00:25:41,380
Vì vậy, hơn một lần.

601
00:25:41,380 --> 00:25:44,280
Bây giờ tôi sẽ để đẩy
vào ngăn xếp 26.

602
00:25:44,280 --> 00:25:46,350
>> STEVEN: Ooh.

603
00:25:46,350 --> 00:25:50,278
Ôi trời.

604
00:25:50,278 --> 00:25:52,520
Bạn thực sự bắt tôi mất cảnh giác.

605
00:25:52,520 --> 00:25:53,703
>> DAVID Malan: Bạn đã không
thấy điều này sắp tới?

606
00:25:53,703 --> 00:25:55,930
>> Steven: Tôi không thấy điều này tới.

607
00:25:55,930 --> 00:25:58,756
Có thể chúng ta khả năng tái ban đầu?

608
00:25:58,756 --> 00:25:59,790
>> DAVID Malan: Đó là một câu hỏi hay.

609
00:25:59,790 --> 00:26:02,360
Vì vậy, chúng tôi đã loại sơn mình
trong một góc ở đây.

610
00:26:02,360 --> 00:26:06,740
Có thực sự là không ra tốt cho Steven
bởi vì chúng tôi đã phân bổ mảng này

611
00:26:06,740 --> 00:26:09,130
tĩnh, có thể nói, bên trong
của cấu trúc dữ liệu.

612
00:26:09,130 --> 00:26:12,170
Và chúng tôi đã được mã hóa cơ bản cứng
nó có kích thước ba.

613
00:26:12,170 --> 00:26:14,170
Vì vậy, chúng ta không thể thực sự phân phối lại nó.

614
00:26:14,170 --> 00:26:20,020
>> Chúng ta có thể nếu chúng ta quay trở lại trong, chúng tôi
xác định lại khay là một con trỏ

615
00:26:20,020 --> 00:26:22,300
sau đó chúng tôi sử dụng malloc để nhớ tay.

616
00:26:22,300 --> 00:26:25,050
Bởi vì nếu chúng ta có bộ nhớ từ
đống thông qua malloc, chúng tôi

617
00:26:25,050 --> 00:26:26,430
sau đó có thể giải phóng nó.

618
00:26:26,430 --> 00:26:29,630
Nhưng trước khi giải phóng nó, chúng ta có thể
tái phân bổ một phần lớn của bộ nhớ,

619
00:26:29,630 --> 00:26:31,330
cập nhật con trỏ, và vv.

620
00:26:31,330 --> 00:26:33,500
Nhưng hiện nay, điều này thực sự là
tốt nhất chúng tôi có thể làm.

621
00:26:33,500 --> 00:26:36,360
Đẩy và pop được có lẽ sẽ
có để báo hiệu một số lỗi.

622
00:26:36,360 --> 00:26:40,270
>> Vì vậy, ví dụ, thực hiện của chúng tôi
đẩy có thể trở lại một bool mà

623
00:26:40,270 --> 00:26:42,390
trước đó trở thành sự thật, sự thật, sự thật.

624
00:26:42,390 --> 00:26:48,390
Nhưng lần thứ tư, nó sẽ có
trở lại sai, ví dụ.

625
00:26:48,390 --> 00:26:48,540
Được rồi.

626
00:26:48,540 --> 00:26:49,540
Thực hiện rất tốt.

627
00:26:49,540 --> 00:26:50,060
Xin chúc mừng.

628
00:26:50,060 --> 00:26:52,160
Bạn đã kiếm được quả bóng căng thẳng của bạn ngày hôm nay.

629
00:26:52,160 --> 00:26:53,110
>> [Vỗ tay]

630
00:26:53,110 --> 00:26:54,382
>> Steven: Cảm ơn bạn.

631
00:26:54,382 --> 00:26:55,680
>> DAVID Malan: Cảm ơn bạn.

632
00:26:55,680 --> 00:26:59,740
OK, vì vậy điều này có vẻ không nhiều
một bước về phía trước, phải không?

633
00:26:59,740 --> 00:27:01,410
Chúng tôi mô tả cấu trúc dữ liệu này.

634
00:27:01,410 --> 00:27:02,320
Nó được hấp dẫn, phải không?

635
00:27:02,320 --> 00:27:03,200
Hệ điều hành thích nó.

636
00:27:03,200 --> 00:27:06,360
Rõ ràng các trang web có thể tận dụng điều này,
và các ứng dụng khác vẫn còn.

637
00:27:06,360 --> 00:27:10,870
Nhưng những gì một giới hạn ngu ngốc mà chúng ta
sao để sắp xếp tuần hai giới hạn

638
00:27:10,870 --> 00:27:12,880
nơi mà chúng tôi đã cố định kích thước mảng.

639
00:27:12,880 --> 00:27:15,010
>> Vì vậy, có thực sự là một vài
cách chúng ta có thể giải quyết điều này.

640
00:27:15,010 --> 00:27:18,750
Chúng tôi tự động có thể phân bổ mảng,
không bằng cứng mã hóa nó như tôi đã

641
00:27:18,750 --> 00:27:22,600
thực hiện ở đây, nhưng thay vào đó lại tuyên bố
này, chỉ cần được rõ ràng, như

642
00:27:22,600 --> 00:27:23,830
một cái gì đó như thế này.

643
00:27:23,830 --> 00:27:29,040
Int * khay, không quyết định
trên công suất được nêu ra.

644
00:27:29,040 --> 00:27:35,460
Nhưng khi tôi tuyên bố chồng ở nơi khác
trong mã của tôi, sau đó tôi có thể gọi malloc,

645
00:27:35,460 --> 00:27:38,250
có được địa chỉ của một đoạn
bộ nhớ, và tôi có thể chỉ định

646
00:27:38,250 --> 00:27:39,980
địa chỉ để khay.

647
00:27:39,980 --> 00:27:43,340
>> Và sau đó, bởi vì nó chỉ là một đoạn
bộ nhớ, tôi có thể tiếp tục sử dụng vuông

648
00:27:43,340 --> 00:27:45,450
khung ký hiệu theo cách thông thường.

649
00:27:45,450 --> 00:27:49,020
Bởi vì một lần nữa, có loại này
tương đương với chức năng của mảng và

650
00:27:49,020 --> 00:27:50,820
khối của bộ nhớ mà đến
trở lại từ malloc.

651
00:27:50,820 --> 00:27:53,090
Chúng ta có thể đối xử với người khác như
sử dụng con trỏ số học hoặc

652
00:27:53,090 --> 00:27:54,440
khung vuông ký hiệu.

653
00:27:54,440 --> 00:27:55,660
Vì vậy, đó là một cách tiếp cận.

654
00:27:55,660 --> 00:28:00,120
>> Nhưng làm thế nào khác chúng ta có thể thực hiện điều này
cấu trúc dữ liệu tương tự, có khả năng?

655
00:28:00,120 --> 00:28:00,280
Phải không?

656
00:28:00,280 --> 00:28:04,530
Tôi cảm thấy như chúng tôi chỉ giải quyết này
vấn đề như một tuần trước đây.

657
00:28:04,530 --> 00:28:08,860
Các giải pháp cho vấn đề này là gì
rằng Steven chạy vào?

658
00:28:08,860 --> 00:28:10,370
Vì vậy, danh sách liên kết, phải.

659
00:28:10,370 --> 00:28:13,410
>> Nếu vấn đề là chúng ta đang vẽ
mình vào một góc bằng cách phân bổ

660
00:28:13,410 --> 00:28:17,580
trước bộ nhớ quá nhỏ mà chúng ta
sau đó đã bằng cách nào đó giải quyết, tốt,

661
00:28:17,580 --> 00:28:19,880
tại sao không chỉ tránh được
phát hành hoàn toàn?

662
00:28:19,880 --> 00:28:26,170
Tại sao không chỉ cần khai báo khay là một
con trỏ tới một nút, ergo một danh sách liên kết,

663
00:28:26,170 --> 00:28:30,740
và sau đó chỉ cần phân bổ các nút mới
mỗi khi Steven cần thiết để phù hợp với một

664
00:28:30,740 --> 00:28:32,400
số vào cấu trúc dữ liệu.

665
00:28:32,400 --> 00:28:34,200
>> Vì vậy, các hình ảnh sẽ phải thay đổi.

666
00:28:34,200 --> 00:28:38,220
Nó sẽ không được làm sạch và như
đơn giản chỉ là một mảng của ba số nguyên.

667
00:28:38,220 --> 00:28:42,970
Bây giờ nó sẽ là một con trỏ đến một
cấu trúc, cấu trúc và có nghĩa là sẽ

668
00:28:42,970 --> 00:28:44,830
có một int và một con trỏ tới.

669
00:28:44,830 --> 00:28:47,670
Nó sẽ dẫn qua con trỏ
đến một cấu trúc như vậy

670
00:28:47,670 --> 00:28:48,600
một cấu trúc như vậy.

671
00:28:48,600 --> 00:28:50,560
Vì vậy, các hình ảnh sẽ thực sự
nhận được một chút hỗn độn.

672
00:28:50,560 --> 00:28:52,950
Và chúng tôi đã buộc mũi tên
tất cả mọi thứ với nhau.

673
00:28:52,950 --> 00:28:55,280
>> Nhưng đó là tốt, đúng, bởi vì
chúng ta đã thấy cách để làm điều này.

674
00:28:55,280 --> 00:28:58,180
Và một khi bạn có được thoải mái
thực hiện một cái gì đó giống như một liên kết

675
00:28:58,180 --> 00:29:01,450
danh sách, bạn sẽ phải làm gì nếu bạn
chọn để thực hiện một bảng băm với

676
00:29:01,450 --> 00:29:05,120
chuỗi riêng biệt cho p-bộ 6, bạn có thể
sử dụng nó như là một khối xây dựng, hoặc một

677
00:29:05,120 --> 00:29:08,870
thành phần, hoặc trong Scratch nói, một
thủ tục, một cái gì đó mà bạn đặt, bạn

678
00:29:08,870 --> 00:29:12,560
tạo ra mảnh ghép của riêng bạn
mà bạn có thể sử dụng lại.

679
00:29:12,560 --> 00:29:17,090
Cân bằng như vậy, nhưng các giải pháp tiềm năng
mà chúng tôi đã thực sự nhìn thấy trước.

680
00:29:17,090 --> 00:29:20,560
>> Vì vậy, khá thường xuyên, bạn sẽ thấy điều này mỗi
hoặc hai năm khi Apple phát hành

681
00:29:20,560 --> 00:29:23,060
một cái gì đó mới, và tất cả những người điên
xếp hàng bên ngoài của Apple

682
00:29:23,060 --> 00:29:27,050
cửa hàng để mua cận biên của họ
nâng cấp về phần cứng.

683
00:29:27,050 --> 00:29:30,420
Tôi nói điều này, đó là OK, vì
Tôi là một trong những người đó.

684
00:29:30,420 --> 00:29:35,140
Vì vậy, loại cấu trúc dữ liệu
có thể đại diện cho thực tế này?

685
00:29:35,140 --> 00:29:36,980
>> Vâng, chúng ta hãy gọi nó là một hàng đợi, một dòng.

686
00:29:36,980 --> 00:29:40,270
Vì vậy, Anh sẽ gọi nó thường là một
hàng đợi anyway, do đó nó là một cái tên đẹp.

687
00:29:40,270 --> 00:29:44,960
Và hai hoạt động mà một hàng đợi
sẽ hỗ trợ chúng ta sẽ gọi một enqueue

688
00:29:44,960 --> 00:29:48,900
hoạt động và hoạt động dequeue,
đó cũng tương tự như trong

689
00:29:48,900 --> 00:29:50,120
tinh thần để đẩy và pop.

690
00:29:50,120 --> 00:29:54,060
Nó chỉ là loại khác nhau trong
quy ước, những gì chúng tôi đang gọi điện thoại này.

691
00:29:54,060 --> 00:29:57,680
Nhưng để enqueue một cái gì đó có nghĩa là để thêm
hoặc chèn nó vào cấu trúc dữ liệu.

692
00:29:57,680 --> 00:29:59,570
Để dequeue có nghĩa là để loại bỏ nó.

693
00:29:59,570 --> 00:30:05,170
Nhưng trong khi một chồng là một dữ liệu LIFO
cấu trúc, một hàng đợi là một trong đầu,

694
00:30:05,170 --> 00:30:06,740
đầu tiên trong cấu trúc dữ liệu.

695
00:30:06,740 --> 00:30:10,050
>> Nếu bạn là người đầu tiên trong dòng,
bạn sẽ là người đầu tiên để có được

696
00:30:10,050 --> 00:30:12,420
ra khỏi dòng và mua thiết bị mới của bạn.

697
00:30:12,420 --> 00:30:18,070
Hãy tưởng tượng như thế nào khó chịu những người này sẽ được
nếu Apple thay vì sử dụng một chồng, cho

698
00:30:18,070 --> 00:30:21,250
Ví dụ, để thực hiện việc chọn
lên đồ chơi mới của bạn.

699
00:30:21,250 --> 00:30:24,310
Vì vậy, hàng đợi có ý nghĩa, chắc chắn, và
chúng ta có thể nghĩ về tất cả các loại

700
00:30:24,310 --> 00:30:27,480
các ứng dụng, có lẽ, cho hàng đợi,
đặc biệt là khi bạn muốn công bằng.

701
00:30:27,480 --> 00:30:30,040
Vậy làm thế nào chúng ta có thể thực hiện các
như một cấu trúc dữ liệu?

702
00:30:30,040 --> 00:30:33,680
>> Vâng, tôi đề nghị chúng ta có thể
cần phải làm theo cách này.

703
00:30:33,680 --> 00:30:35,225
Vì vậy, tôi sẽ bây giờ có con số.

704
00:30:35,225 --> 00:30:38,190
Vì vậy, chúng tôi sẽ giữ nó đơn giản và không
nhất thiết phải nói về khay.

705
00:30:38,190 --> 00:30:40,220
Chỉ số mà người dân nhận được.

706
00:30:40,220 --> 00:30:43,760
Khả năng sẽ đi, một lần nữa, sửa chữa
tổng số người có thể ở

707
00:30:43,760 --> 00:30:46,900
dòng này, như ba hoặc
bất cứ điều gì khác giá trị.

708
00:30:46,900 --> 00:30:50,760
>> Nhưng tôi đề nghị rằng tôi cần phải theo dõi
không chỉ về kích thước của các

709
00:30:50,760 --> 00:30:52,370
hàng đợi, bao nhiêu điều trong đó.

710
00:30:52,370 --> 00:30:56,310
Vì vậy kích thước là kích thước, công suất hiện tại
là kích thước tối đa.

711
00:30:56,310 --> 00:30:58,540
Chỉ cần một lần nữa, danh pháp
theo quy ước.

712
00:30:58,540 --> 00:31:03,680
Tại sao tôi cần một int thêm bên trong
của một danh sách để theo dõi những người trong

713
00:31:03,680 --> 00:31:05,365
phía trước của dòng?

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
Tại sao tôi cần phải làm điều đó trong trường hợp này?

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> Vâng, làm thế nào là hình ảnh này
sẽ thay đổi?

718
00:31:16,190 --> 00:31:19,280
Tôi có lẽ có thể tái sử dụng nhất
của hình ảnh này.

719
00:31:19,280 --> 00:31:21,480
Hãy để tôi đi trước và xóa những gì ở đây.

720
00:31:21,480 --> 00:31:24,580
Chúng tôi sẽ cung cấp cho một hơi
tên khác nhau ở đây.

721
00:31:24,580 --> 00:31:28,930
Hãy thoát khỏi 17, chúng ta hãy thoát khỏi
trong số 9, chúng ta hãy thoát khỏi 3.

722
00:31:28,930 --> 00:31:30,410
Và chúng ta hãy thêm một điều khác.

723
00:31:30,410 --> 00:31:34,710
Tôi đề nghị rằng tôi cần phải theo dõi
mặt trước của danh sách, mà chỉ là

724
00:31:34,710 --> 00:31:35,570
sẽ là một int là tốt.

725
00:31:35,570 --> 00:31:36,550
Và chúng ta sẽ giữ nó đơn giản.

726
00:31:36,550 --> 00:31:37,740
Không có danh sách liên kết cho bây giờ.

727
00:31:37,740 --> 00:31:40,900
>> Chúng tôi sẽ thừa nhận rằng chúng ta sẽ
băng lên chống lại giới hạn này.

728
00:31:40,900 --> 00:31:43,720
Nhưng những gì tôi muốn xem
xảy ra thời gian này?

729
00:31:43,720 --> 00:31:47,240
Vì vậy, giả sử tôi đi trước và là người đầu tiên
người đi lên trong dòng, và

730
00:31:47,240 --> 00:31:48,560
đó là số 9.

731
00:31:48,560 --> 00:31:49,680
Chúng tôi có bóng căng thẳng.

732
00:31:49,680 --> 00:31:51,330
Tôi có thể ăn cắp, nói, hai hoặc ba người?

733
00:31:51,330 --> 00:31:52,690
Một, hai, ba?

734
00:31:52,690 --> 00:31:53,120
Lên đây.

735
00:31:53,120 --> 00:31:56,022
Ngay từ trước, bởi vì
chúng tôi sẽ thực hiện điều này nhanh chóng.

736
00:31:56,022 --> 00:31:59,415
>> Mỗi bạn bây giờ là có được
một cậu bé người hâm mộ xếp hàng tại Apple.

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
Bạn sẽ không nhận được phần cứng của Apple
vào cuối năm mặc dù điều này.

739
00:32:06,210 --> 00:32:06,500
Được rồi.

740
00:32:06,500 --> 00:32:09,430
Vì vậy, bạn số 9, bạn
số 17, số 22.

741
00:32:09,430 --> 00:32:12,130
Đây là những con số tùy ý, như
sinh viên ID hay những thứ linh tinh.

742
00:32:12,130 --> 00:32:14,550
Và chỉ trong một thời điểm, chúng ta hãy bắt đầu
để bắt đầu thêm điều.

743
00:32:14,550 --> 00:32:16,000
Và tôi sẽ chạy hội đồng quản trị ở đây thời gian này.

744
00:32:16,000 --> 00:32:19,570
>> Vì vậy, trong trường hợp này, tôi đã khởi tạo
phía trước là -

745
00:32:19,570 --> 00:32:22,380
Tôi thực sự không quan tâm những gì
phía trước, bởi vì kích thước là số không.

746
00:32:22,380 --> 00:32:24,480
Như vậy có thể này cũng chỉ
là một dấu hỏi.

747
00:32:24,480 --> 00:32:26,170
Tất cả đều là dấu hỏi.

748
00:32:26,170 --> 00:32:29,880
Vì vậy, bây giờ chúng tôi sẽ bắt đầu thực sự thấy một số
người xếp hàng tại cửa hàng.

749
00:32:29,880 --> 00:32:33,320
>> Vì vậy, nếu số 9, bạn là người đầu tiên
có lúc 05:00, đi trước và xếp hàng,

750
00:32:33,320 --> 00:32:34,210
hoặc tối hôm trước.

751
00:32:34,210 --> 00:32:34,580
OK.

752
00:32:34,580 --> 00:32:35,940
Vì vậy, bây giờ là 9 đây.

753
00:32:35,940 --> 00:32:37,940
Vì vậy, 9 là ở mặt trước của danh sách.

754
00:32:37,940 --> 00:32:41,440
Vì vậy, tôi sẽ đi trước và cập nhật
kích thước của dữ liệu hiện tại này

755
00:32:41,440 --> 00:32:44,740
cấu trúc không là 0 nữa,
nhưng là 1.

756
00:32:44,740 --> 00:32:47,630
Tôi sẽ đưa 9 tại
phía trước của danh sách.

757
00:32:47,630 --> 00:32:51,020
Hãy để tôi đi trước và chuyển đổi màn hình
vì vậy chúng tôi có thể nhìn thấy qua chúng tôi ở đây.

758
00:32:51,020 --> 00:32:53,220
>> Và bây giờ những gì tôi muốn
đặt ở phía trước?

759
00:32:53,220 --> 00:32:56,240
Tôi sẽ theo dõi các
phía trước của hàng đợi ngay bây giờ

760
00:32:56,240 --> 00:32:58,570
là vị trí 0.

761
00:32:58,570 --> 00:33:00,510
Bởi vì những gì được tiếp theo sẽ xảy ra?

762
00:33:00,510 --> 00:33:03,000
Vâng, giả sử bây giờ tôi enqueue
17 là tốt.

763
00:33:03,000 --> 00:33:04,510
Vì vậy, hop trong dòng đó.

764
00:33:04,510 --> 00:33:07,060
Và một lần nữa, các loại cửa cho các
cửa hàng là có được ở đây.

765
00:33:07,060 --> 00:33:08,700
Vì vậy, bây giờ tôi đã bổ sung thêm 17.

766
00:33:08,700 --> 00:33:10,810
Và mặc dù những kẻ đang chặn
màn hình, đó là OK,

767
00:33:10,810 --> 00:33:12,300
bởi vì chúng ta có thể nhìn thấy nó ở đây.

768
00:33:12,300 --> 00:33:12,910
Xin lôi.

769
00:33:12,910 --> 00:33:13,810
>> ĐỐI TƯỢNG: Chúng tôi có thể di chuyển -

770
00:33:13,810 --> 00:33:14,660
>> DAVID Malan: Không, đó là OK.

771
00:33:14,660 --> 00:33:16,000
Nó lớn lên ở đó.

772
00:33:16,000 --> 00:33:18,580
Vì vậy, bây giờ 17 là bên trong của hàng đợi.

773
00:33:18,580 --> 00:33:21,332
Tôi cần phải cập nhật mà
lĩnh vực mặc dù bây giờ?

774
00:33:21,332 --> 00:33:23,210
OK, chắc chắn kích thước.

775
00:33:23,210 --> 00:33:26,430
Và làm thế nào về phía trước?

776
00:33:26,430 --> 00:33:27,040
OK, không.

777
00:33:27,040 --> 00:33:30,200
Phía trước không nên thay đổi, bởi vì
không giống như một chồng, chúng tôi

778
00:33:30,200 --> 00:33:31,370
muốn duy trì sự công bằng.

779
00:33:31,370 --> 00:33:35,150
Vì vậy, nếu trong 9 đến đầu tiên, chúng tôi muốn 9
là sản phẩm đầu tiên của dòng

780
00:33:35,150 --> 00:33:36,420
và vào cửa hàng.

781
00:33:36,420 --> 00:33:37,220
>> Trong thực tế, chúng ta thấy điều đó.

782
00:33:37,220 --> 00:33:42,235
Trước khi chúng ta chèn 22, chúng ta hãy
đi trước và dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Tên của bạn là gì nữa?

784
00:33:42,970 --> 00:33:43,680
>> ĐỐI TƯỢNG: Jake.

785
00:33:43,680 --> 00:33:45,440
>> DAVID Malan: Jake sẽ
được dequeued bây giờ.

786
00:33:45,440 --> 00:33:48,050
Vì vậy, bạn có thể đi bộ vào cửa hàng.

787
00:33:48,050 --> 00:33:49,880
Và giả vờ rằng các cửa hàng
là ở đó.

788
00:33:49,880 --> 00:33:51,970
Vì vậy, bây giờ những gì cần - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Những gì cần phải xảy ra bây giờ?

790
00:33:53,400 --> 00:33:54,490
Quyết định thiết kế.

791
00:33:54,490 --> 00:33:56,825
Vì vậy, không phải là một bản năng xấu, nhưng -
Tên của bạn là gì nữa?

792
00:33:56,825 --> 00:33:57,090
>> Khán giả: David.

793
00:33:57,090 --> 00:33:57,500
>> DAVID Malan: David.

794
00:33:57,500 --> 00:33:58,810
Vì vậy, những gì đã làm David làm gì?

795
00:33:58,810 --> 00:34:02,590
Ông đã cố gắng để sắp xếp các sửa chữa dữ liệu
cấu trúc và di chuyển từ vị trí của mình

796
00:34:02,590 --> 00:34:04,100
vào vị trí cũ của Jake.

797
00:34:04,100 --> 00:34:06,740
Và đó là tốt nếu chúng tôi sẵn sàng
để chấp nhận điều đó như một

798
00:34:06,740 --> 00:34:08,199
chi tiết thực hiện.

799
00:34:08,199 --> 00:34:11,100
Nhưng trước tiên, chúng ta hãy cập nhật dữ liệu
cấu trúc trước khi chúng tôi làm điều đó.

800
00:34:11,100 --> 00:34:14,139
Bởi vì tôi không thích ý tưởng của tất cả các
những người chuyển trong dòng này.

801
00:34:14,139 --> 00:34:17,360
>> Nó không có việc lớn, nếu David hiện điều đó với
một bước, nhưng một lần nữa, nghĩ lại

802
00:34:17,360 --> 00:34:20,360
khi tình nguyện viên đã có tám trên
sân khấu và chúng tôi đã làm như chèn

803
00:34:20,360 --> 00:34:22,600
sắp xếp, nơi mà chúng tôi đã phải bắt đầu
di chuyển tất cả mọi người xung quanh.

804
00:34:22,600 --> 00:34:23,790
Mà có đắt tiền, phải không?

805
00:34:23,790 --> 00:34:28,330
Điều đó làm tôi co rúm người lại về O lớn
n, O lớn của n bình phương một lần nữa.

806
00:34:28,330 --> 00:34:30,650
Nó không cảm thấy như
một kết quả lý tưởng.

807
00:34:30,650 --> 00:34:32,080
>> Vì vậy, chúng ta chỉ cần cập nhật này.

808
00:34:32,080 --> 00:34:35,120
Vì vậy kích thước của hàng đợi
không còn là 2.

809
00:34:35,120 --> 00:34:37,090
Nó bây giờ chỉ đơn giản là 1.

810
00:34:37,090 --> 00:34:40,360
Nhưng bây giờ tôi có thể cập nhật một cái gì đó
Tôi đã không cập nhật trước,

811
00:34:40,360 --> 00:34:41,130
phía trước của danh sách.

812
00:34:41,130 --> 00:34:45,420
Tôi chỉ có thể nói, là vị trí mà 1?

813
00:34:45,420 --> 00:34:49,770
Vì vậy, bây giờ chúng tôi có giá trị rác đây,
giá trị rác ở đây, và David trong

814
00:34:49,770 --> 00:34:51,469
giữa rác này.

815
00:34:51,469 --> 00:34:54,980
Nhưng cấu trúc dữ liệu
vẫn còn nguyên vẹn.

816
00:34:54,980 --> 00:34:58,540
>> Và trong thực tế, tôi thậm chí không cần phải
thay đổi số trước đây của Jake

817
00:34:58,540 --> 00:35:00,460
9, bởi vì những người quan tâm.

818
00:35:00,460 --> 00:35:04,470
Tôi có đủ thông tin bây giờ trong
kích thước mà tôi biết có một người trong

819
00:35:04,470 --> 00:35:05,030
hàng đợi này.

820
00:35:05,030 --> 00:35:08,340
Và tôi biết rằng người đó
là ở vị trí 1, không phải 0.

821
00:35:08,340 --> 00:35:09,760
Tôi không đếm.

822
00:35:09,760 --> 00:35:11,300
Vì vậy, 1 là tốt.

823
00:35:11,300 --> 00:35:13,410
Vì vậy, các cấu trúc dữ liệu vẫn OK.

824
00:35:13,410 --> 00:35:14,330
>> Vâng, những gì xảy ra tiếp theo?

825
00:35:14,330 --> 00:35:15,010
Hãy enqueue -

826
00:35:15,010 --> 00:35:15,370
Tên của bạn là gì?

827
00:35:15,370 --> 00:35:16,160
>> ĐỐI TƯỢNG: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID Malan: Callen.

829
00:35:16,580 --> 00:35:20,770
Hãy enqueue một Callen, và
22 giờ là trong hàng đợi.

830
00:35:20,770 --> 00:35:22,300
Vì vậy, bây giờ những gì có để thay đổi đây?

831
00:35:22,300 --> 00:35:24,380
Phía trước sẽ không
thay đổi, rõ ràng.

832
00:35:24,380 --> 00:35:27,160
Kích thước sẽ thay đổi được 2 lần nữa.

833
00:35:27,160 --> 00:35:31,590
Và 22 kết thúc ở đây, 9 vẫn còn hiện diện,
nhưng đó là một cách hiệu quả

834
00:35:31,590 --> 00:35:32,600
giá trị rác tại.

835
00:35:32,600 --> 00:35:35,910
Nó chỉ là một tàn dư của Jake qua.

836
00:35:35,910 --> 00:35:39,200
>> Vì vậy, bây giờ những gì sẽ xảy ra nếu
Tôi dequeue David?

837
00:35:39,200 --> 00:35:41,560
Một hoạt động cuối cùng, dequeue David.

838
00:35:41,560 --> 00:35:46,070
Chúng tôi có thể thay đổi, nhưng tôi đề nghị chúng ta hãy
làm càng ít việc càng tốt.

839
00:35:46,070 --> 00:35:50,280
Bây giờ cấu trúc dữ liệu của tôi đi
sao có kích thước 2-1.

840
00:35:50,280 --> 00:35:53,730
Nhưng phía trước của hàng đợi
bây giờ trở thành 2.

841
00:35:53,730 --> 00:35:56,640
Tôi không cần phải thay đổi những con số
chỉ được nêu ra, bởi vì chúng

842
00:35:56,640 --> 00:35:58,230
chỉ giá trị rác.

843
00:35:58,230 --> 00:35:59,720
>> Nhưng bây giờ những gì sẽ xảy ra?

844
00:35:59,720 --> 00:36:03,280
Giả sử tôi enqueue bản thân mình, 26?

845
00:36:03,280 --> 00:36:05,890
Tôi cảm thấy mình không thuộc về đây.

846
00:36:05,890 --> 00:36:06,890
Vì vậy, tôi được enqueued.

847
00:36:06,890 --> 00:36:08,760
Vì vậy, tôi loại thuộc về nơi này.

848
00:36:08,760 --> 00:36:11,300
Và ngay cả khi bạn không hoàn toàn
đánh giá cao này trực quan trên sân khấu,

849
00:36:11,300 --> 00:36:15,075
bởi vì chúng tôi có rất nhiều phòng, tôi nên
không được đứng ở đây, tại sao?

850
00:36:15,075 --> 00:36:16,290
>> ĐỐI TƯỢNG: Bạn nằm ngoài giới hạn.

851
00:36:16,290 --> 00:36:16,370
>> DAVID Malan: Đúng vậy.

852
00:36:16,370 --> 00:36:16,940
Tôi ra khỏi giới hạn.

853
00:36:16,940 --> 00:36:19,330
Tôi đã được lập chỉ mục ngoài
giới hạn của mảng này.

854
00:36:19,330 --> 00:36:23,420
Tôi thực sự phải ở trong một trong những
ba địa điểm có thể.

855
00:36:23,420 --> 00:36:25,150
Bây giờ, nơi là tự nhiên nhất để đi?

856
00:36:25,150 --> 00:36:27,760
Tôi đề nghị chúng ta sử dụng đòn bẩy
một tuần một trick.

857
00:36:27,760 --> 00:36:30,150
Các nhà điều hành mod, tỷ lệ phần trăm.

858
00:36:30,150 --> 00:36:36,850
Bởi vì tôi đang đứng ở mặt kỹ thuật
vị trí 3, nhưng tôi làm 3 công suất mod,

859
00:36:36,850 --> 00:36:40,250
do đó, 3, một dấu phần trăm, 3 -

860
00:36:40,250 --> 00:36:40,970
công suất là 3.

861
00:36:40,970 --> 00:36:41,720
Đó là những gì?

862
00:36:41,720 --> 00:36:43,700
Phần còn lại là những gì khi
bạn chia 3 của 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Vì vậy, mà đặt tôi đã Jake,
mà thực sự là tốt.

865
00:36:48,140 --> 00:36:50,370
Vì vậy bây giờ thực hiện
điều này sẽ

866
00:36:50,370 --> 00:36:51,250
là một chút đau đầu.

867
00:36:51,250 --> 00:36:53,740
Nó thực sự chỉ là một dòng
đau đầu, mã.

868
00:36:53,740 --> 00:36:56,580
Nhưng ít nhất bây giờ có rác
giá trị ở đây, nhưng có hai

869
00:36:56,580 --> 00:36:57,910
ints hợp pháp ở đây.

870
00:36:57,910 --> 00:37:04,160
Và tôi cho rằng bây giờ chúng tôi đã thực hiện
chính xác những gì chúng ta cần phải làm như vậy miễn là

871
00:37:04,160 --> 00:37:08,600
chúng ta thay đổi những gì của Jake
giá trị đã là 26.

872
00:37:08,600 --> 00:37:12,110
>> Bây giờ chúng tôi có đủ thông tin vẫn còn
để duy trì tính toàn vẹn

873
00:37:12,110 --> 00:37:13,060
cấu trúc dữ liệu này.

874
00:37:13,060 --> 00:37:17,160
Chúng ta vẫn còn loại ra khỏi may mắn khi chúng tôi
muốn chèn bốn hoặc nhiều hơn tổng số

875
00:37:17,160 --> 00:37:20,740
yếu tố, nhưng tôi có thể ít nhất là làm đẹp
hiệu quả sử dụng liên tục này

876
00:37:20,740 --> 00:37:21,740
thời gian, trên thực tế.

877
00:37:21,740 --> 00:37:27,150
Tôi không phải lo lắng về thay đổi
tất cả mọi người, như độ nghiêng của David là.

878
00:37:27,150 --> 00:37:30,816
>> Bất kỳ câu hỏi trên ngăn xếp,
hoặc hàng đợi này?

879
00:37:30,816 --> 00:37:32,184
>> ĐỐI TƯỢNG: là lý do tại sao
bạn cần kích thước để bạn biết

880
00:37:32,184 --> 00:37:34,010
nơi có một người?

881
00:37:34,010 --> 00:37:34,770
>> DAVID Malan: Chính xác.

882
00:37:34,770 --> 00:37:38,230
Tôi cần phải biết kích thước của mảng
bởi vì tôi cần phải biết chính xác có bao

883
00:37:38,230 --> 00:37:41,940
rất nhiều những giá trị này là hợp pháp,
và vì vậy mà tôi có thể tìm thấy nơi để đặt

884
00:37:41,940 --> 00:37:42,800
người tiếp theo.

885
00:37:42,800 --> 00:37:43,300
Chính xác.

886
00:37:43,300 --> 00:37:44,580
Kích thước là -

887
00:37:44,580 --> 00:37:46,360
trên thực tế, chúng tôi đã không cập nhật này.

888
00:37:46,360 --> 00:37:48,380
Tôi thêm bản thân mình tại 26.

889
00:37:48,380 --> 00:37:51,760
Kích thước là bây giờ, không phải 1, nhưng 2.

890
00:37:51,760 --> 00:37:57,780
Vì vậy, bây giờ điều này thực sự giúp tôi tìm thấy
đứng đầu danh sách, mà không phải là 0, không

891
00:37:57,780 --> 00:37:59,250
1, nhưng là 2.

892
00:37:59,250 --> 00:38:01,665
Mặt trước của danh sách
thực sự là số 22.

893
00:38:01,665 --> 00:38:05,120
Bởi vì ông đến đầu tiên, vì vậy ông nên
được cho phép vào cửa hàng trước khi tôi,

894
00:38:05,120 --> 00:38:08,780
mặc dù trực quan tôi đang đứng
gần cửa hàng.

895
00:38:08,780 --> 00:38:09,220
>> Tất cả phải không?

896
00:38:09,220 --> 00:38:12,410
Một tràng pháo tay cho những kẻ
và chúng tôi sẽ cho họ ra khỏi đó.

897
00:38:12,410 --> 00:38:17,090
>> [Vỗ tay]

898
00:38:17,090 --> 00:38:18,150
>> DAVID Malan: tôi có thể cho phép
bạn giữ khay.

899
00:38:18,150 --> 00:38:20,760
Chúng ta có thể xem những gì sẽ xảy ra nếu
bạn muốn, nhưng có lẽ không.

900
00:38:20,760 --> 00:38:21,590
Được rồi.

901
00:38:21,590 --> 00:38:25,380
Vì vậy, những gì bây giờ không để lại cho chúng tôi?

902
00:38:25,380 --> 00:38:28,900
Vâng, hãy để tôi đề xuất rằng có một
vài cấu trúc dữ liệu khác mà chúng tôi có thể

903
00:38:28,900 --> 00:38:33,810
bắt đầu thêm vào bộ công cụ của chúng tôi sẽ
thực sự là khá, khá liên quan như

904
00:38:33,810 --> 00:38:35,270
chúng tôi đi sâu vào công cụ web.

905
00:38:35,270 --> 00:38:38,150
Mà một lần nữa, có một số loại kết nối
để trồng trong các hình thức

906
00:38:38,150 --> 00:38:40,550
một cái gì đó gọi là DOM, tài liệu
mô hình đối tượng.

907
00:38:40,550 --> 00:38:42,370
Nhưng chúng ta sẽ thấy nhiều hơn
mà chẳng bao lâu.

908
00:38:42,370 --> 00:38:46,260
>> Hãy để tôi đề xuất rằng chúng ta definitionally
gọi cây bây giờ những gì bạn có thể biết như

909
00:38:46,260 --> 00:38:48,820
nhiều hơn một cây gia đình, nơi bạn
có một số tổ tiên tại

910
00:38:48,820 --> 00:38:49,790
rễ của cây.

911
00:38:49,790 --> 00:38:54,480
Một nữ chúa gia trưởng hoặc tại
phần trên của cây.

912
00:38:54,480 --> 00:38:56,700
Nếu không có vợ hoặc chồng, trong trường hợp này.

913
00:38:56,700 --> 00:39:00,940
Nhưng bây giờ chúng tôi có những gì chúng tôi sẽ gọi
trẻ em, trong đó có các nút treo

914
00:39:00,940 --> 00:39:05,480
ra khỏi con trái hoặc con phải,
mũi tên như mô tả ở đây.

915
00:39:05,480 --> 00:39:10,490
>> Nói cách khác, trong một cấu trúc dữ liệu cây
trong máy tính, một cây có không

916
00:39:10,490 --> 00:39:11,480
hoặc nhiều nút.

917
00:39:11,480 --> 00:39:13,500
Nếu nó có ít nhất một nút,
đó được gọi là gốc.

918
00:39:13,500 --> 00:39:15,700
Đó là những việc trực quan mà
chúng ta rút ra ở đầu trang.

919
00:39:15,700 --> 00:39:20,280
Và nút đó, giống như bất kỳ nút khác, có thể
có không, một, hoặc hai, hoặc ba,

920
00:39:20,280 --> 00:39:23,600
hoặc tuy nhiên nhiều trẻ em
cấu trúc dữ liệu hỗ trợ.

921
00:39:23,600 --> 00:39:29,150
Trong trường hợp này, các gốc, lưu trữ
giá trị một, có hai con, 2 và 3,

922
00:39:29,150 --> 00:39:33,020
vì vậy chúng tôi thường gọi 2 bên trái
trẻ em và 3 con phải.

923
00:39:33,020 --> 00:39:36,940
>> Và sau đó khi chúng tôi có được giảm xuống còn 5, 6, và
7, 6 có thể được gọi là con giữa.

924
00:39:36,940 --> 00:39:38,940
Nếu bạn có bốn người con,
nó được gây nhầm lẫn.

925
00:39:38,940 --> 00:39:42,260
Vì vậy, chúng tôi ngừng sử dụng loại đó
các phím tắt bằng lời nói.

926
00:39:42,260 --> 00:39:44,580
Nhưng nó thực sự chỉ là một cây gia đình.

927
00:39:44,580 --> 00:39:48,880
Và lá ở đây là các nút
mình không có con.

928
00:39:48,880 --> 00:39:52,540
Họ treo ra dưới cùng của cây.

929
00:39:52,540 --> 00:39:56,940
>> Vậy làm thế nào chúng ta có thể thực hiện một cây
chỉ có hai trẻ em tối đa?

930
00:39:56,940 --> 00:39:58,410
Chúng tôi sẽ gọi nó là một cây nhị phân.

931
00:39:58,410 --> 00:40:00,960
Bi lại có nghĩa là hai, trong này
trường hợp, như với nhị phân.

932
00:40:00,960 --> 00:40:04,830
Và do đó, nó có thể có không, một,
hoặc hai con tối đa.

933
00:40:04,830 --> 00:40:08,650
>> Tôi sẽ đề nghị chúng ta thực hiện các nút
cho rằng cấu trúc với một int n,

934
00:40:08,650 --> 00:40:11,910
và sau đó hai con trỏ, một được gọi là
còn lại, một được gọi là đúng.

935
00:40:11,910 --> 00:40:14,830
Nhưng những người chỉ đẹp
ước tùy ý.

936
00:40:14,830 --> 00:40:18,170
Và những gì tốt đẹp hiện nay, đặc biệt là nếu bạn
loại vật lộn với khái niệm

937
00:40:18,170 --> 00:40:21,300
đệ quy, hoặc nghĩ rằng đó là không
thực sự là một giải pháp cho bất cứ điều gì,

938
00:40:21,300 --> 00:40:23,120
đặc biệt là nếu bạn có thể
chạy ra khỏi bộ nhớ.

939
00:40:23,120 --> 00:40:26,600
Bây giờ chúng ta đang nói về dữ liệu
cấu trúc và thuật toán cho phép

940
00:40:26,600 --> 00:40:31,030
chúng tôi đi qua và vận dụng chúng,
chỉ ra rằng đệ quy trở lại trong

941
00:40:31,030 --> 00:40:34,240
một nhiều hơn nữa hấp dẫn
nếu không cách đẹp.

942
00:40:34,240 --> 00:40:38,670
>> Vì vậy, đây tôi đề xuất là việc thực hiện
của một chức năng tìm kiếm.

943
00:40:38,670 --> 00:40:39,870
Cho hai đầu vào -

944
00:40:39,870 --> 00:40:41,570
để nghĩ về điều này như một hộp đen.

945
00:40:41,570 --> 00:40:46,560
Với hai yếu tố đầu vào, n, một int, và một
con trỏ vào một cái cây, một con trỏ đến một

946
00:40:46,560 --> 00:40:50,020
nút, hoặc thực sự là gốc của một cây, tôi
cho rằng chức năng này có thể trở lại

947
00:40:50,020 --> 00:40:53,530
đúng hay sai, mà giá trị n
là bên trong của cây này.

948
00:40:53,530 --> 00:40:55,210
>> Bên trong của hộp đen này là gì?

949
00:40:55,210 --> 00:40:57,440
Vâng, bốn chi nhánh.

950
00:40:57,440 --> 00:40:58,385
Chỉ kiểm tra đầu tiên.

951
00:40:58,385 --> 00:41:00,490
Nếu cây là vô giá trị, chỉ cần trả về false.

952
00:41:00,490 --> 00:41:04,580
Nếu không có nút, không có n,
không có số, chỉ cần trả về false.

953
00:41:04,580 --> 00:41:12,330
Nếu mặc dù, n, giá trị mà bạn đang tìm kiếm
cho, nhỏ hơn cây mũi tên n, và

954
00:41:12,330 --> 00:41:15,180
chỉ để được rõ ràng, điều đó có nghĩa là khi
Tôi viết cây và sau đó mũi tên

955
00:41:15,180 --> 00:41:18,150
ký hiệu, n?

956
00:41:18,150 --> 00:41:18,690
Chính xác.

957
00:41:18,690 --> 00:41:21,970
Nó có nghĩa là tới đích mà
con trỏ được gọi là cây.

958
00:41:21,970 --> 00:41:26,750
Đi đến đó, và sau đó đi vào bên trong mà
nút và nhận được lĩnh vực của mình gọi là n.

959
00:41:26,750 --> 00:41:30,810
Và sau đó so sánh n thực tế đó là
thông qua vào tìm kiếm chống lại nó.

960
00:41:30,810 --> 00:41:35,390
>> Vì vậy, nếu n là ít hơn, giá trị n
trong nút cây chính nó, tốt,

961
00:41:35,390 --> 00:41:36,720
có nghĩa là gì?

962
00:41:36,720 --> 00:41:40,690
Điều đó có nghĩa không có gì ở cái nhìn đầu tiên.

963
00:41:40,690 --> 00:41:40,900
Phải không?

964
00:41:40,900 --> 00:41:45,560
Cũng giống như khi bạn có một mảng của
giá trị, bạn có thể muốn áp dụng nhị phân

965
00:41:45,560 --> 00:41:48,290
Tìm kiếm là một hình thức phân chia
và chinh phục.

966
00:41:48,290 --> 00:41:51,790
Nhưng những gì đã giả định chúng ta cần phải thực hiện
cho tìm kiếm nhị phân để làm việc ở tất cả các

967
00:41:51,790 --> 00:41:54,510
trong danh bạ điện thoại và
thí dụ trước đây?

968
00:41:54,510 --> 00:41:55,530
>> Làm thế nào để được sắp xếp.

969
00:41:55,530 --> 00:41:59,490
Vì vậy, hãy tinh chỉnh các định nghĩa của cây
đây không phải chỉ là một cây, có thể

970
00:41:59,490 --> 00:42:00,880
có bất kỳ số lượng trẻ em.

971
00:42:00,880 --> 00:42:04,700
Không chỉ là một cây nhị phân, có thể
có 0, 1, 2 hoặc tối đa.

972
00:42:04,700 --> 00:42:09,700
Nhưng như một cây tìm kiếm nhị phân, hoặc BST,
mà chỉ là một cách nói một

973
00:42:09,700 --> 00:42:15,430
cây nhị phân như vậy mà mỗi nút
con trái, nếu có, là

974
00:42:15,430 --> 00:42:16,830
dưới nút.

975
00:42:16,830 --> 00:42:20,170
Và con phải của mỗi nút,
nếu có, là lớn hơn

976
00:42:20,170 --> 00:42:21,740
hơn các nút đó.

977
00:42:21,740 --> 00:42:25,200
>> Vì vậy, nói cách khác, nếu bạn đã vẽ
ra khỏi cây, tất cả các con số

978
00:42:25,200 --> 00:42:30,620
sự cân cẩn thận như thế này để nếu
bạn có 55 như là gốc, 33 có thể đi

979
00:42:30,620 --> 00:42:33,090
bên trái của nó vì nó ít hơn 55.

980
00:42:33,090 --> 00:42:36,430
77 có thể đi bên phải của nó bởi vì
nó lớn hơn 55.

981
00:42:36,430 --> 00:42:40,750
Nhưng bây giờ nhận thấy, cùng một định nghĩa,
đó là một định nghĩa đệ quy bằng lời nói,

982
00:42:40,750 --> 00:42:42,600
phải áp dụng cho 33.

983
00:42:42,600 --> 00:42:47,610
Con trái 33 của phải nhỏ hơn nó,
và con phải của 33, 44, phải

984
00:42:47,610 --> 00:42:48,580
lớn hơn nó.

985
00:42:48,580 --> 00:42:51,670
>> Vì vậy, đây là một cây tìm kiếm nhị phân, và
Tôi đề nghị, sử dụng một chút

986
00:42:51,670 --> 00:42:53,910
đệ quy, chúng ta có thể tìm thấy n.

987
00:42:53,910 --> 00:42:59,160
Vì vậy, nếu n là ít hơn so với n giá trị đó là
nút hiện tại, tôi sẽ đi

988
00:42:59,160 --> 00:43:04,090
trước và punt, vậy để nói chuyện, và chỉ
trở lại bất cứ câu trả lời là của

989
00:43:04,090 --> 00:43:08,470
tìm kiếm n trên
con trái cây của.

990
00:43:08,470 --> 00:43:11,370
Nhận thấy một lần nữa, chức năng này chỉ
hy vọng sẽ là một ngôi sao nút, một

991
00:43:11,370 --> 00:43:12,780
con trỏ đến một nút.

992
00:43:12,780 --> 00:43:17,360
Vì vậy, chắc chắn tôi chỉ có thể làm cây
mũi tên trái, sẽ dẫn

993
00:43:17,360 --> 00:43:18,400
tôi sang một nút khác.

994
00:43:18,400 --> 00:43:19,480
Nhưng nút đó là những gì?

995
00:43:19,480 --> 00:43:22,820
>> Vâng, theo tuyên bố này,
trái chỉ là một con trỏ, để chỉ

996
00:43:22,820 --> 00:43:27,090
có nghĩa là tôi đang đi qua với chức năng tìm kiếm
một con trỏ khác nhau, cụ thể là

997
00:43:27,090 --> 00:43:30,750
là cái đại diện
cây con trái của tôi.

998
00:43:30,750 --> 00:43:36,040
Vì vậy, trong trường hợp này, con trỏ đến 33, nếu
đây là mẫu đầu vào của chúng tôi khi đó, nếu

999
00:43:36,040 --> 00:43:40,740
n lớn hơn n giá trị tại
nút hiện tại trong cây, sau đó tôi

1000
00:43:40,740 --> 00:43:43,370
sẽ đi trước và punt trong khác
hướng và chỉ nói rằng, tôi không

1001
00:43:43,370 --> 00:43:47,280
biết nếu giá trị n này nằm ở cây,
nhưng tôi biết nếu nó có, nó xuống của tôi

1002
00:43:47,280 --> 00:43:49,090
chi nhánh bên phải, vậy để nói chuyện.

1003
00:43:49,090 --> 00:43:53,120
Vì vậy, hãy để tôi gọi đệ quy tìm kiếm,
đi qua một n một lần nữa, nhưng đi qua trong một

1004
00:43:53,120 --> 00:43:54,580
con trỏ đến con phải của tôi.

1005
00:43:54,580 --> 00:44:00,020
>> Nói cách khác, nếu tôi là hiện tại 55
và tôi đang tìm kiếm 99, tôi biết rằng 99

1006
00:44:00,020 --> 00:44:04,270
lớn hơn 55, vì vậy chỉ cần như tôi xé
những tuần trước bạ điện thoại và chúng tôi

1007
00:44:04,270 --> 00:44:07,140
đi bên phải, tương tự như chúng ta
sẽ đi ngay đây.

1008
00:44:07,140 --> 00:44:11,960
Và tôi không biết nếu nó ở bên phải của tôi
trẻ em, và nó không phải, 77 là có, nhưng

1009
00:44:11,960 --> 00:44:13,210
Tôi biết đó là theo hướng đó.

1010
00:44:13,210 --> 00:44:18,770
Vì vậy, tôi gọi tìm kiếm trên con phải của tôi,
77, và để cho con số tìm kiếm ra khỏi

1011
00:44:18,770 --> 00:44:24,950
nếu có 99 trong tùy ý này
ví dụ là thực sự có.

1012
00:44:24,950 --> 00:44:26,900
>> Khác, trường hợp thức là những gì?

1013
00:44:26,900 --> 00:44:28,620
Nếu cây là null là một trường hợp.

1014
00:44:28,620 --> 00:44:31,890
Nếu n là ít hơn so với các nút của hiện tại
giá trị là một trường hợp khác.

1015
00:44:31,890 --> 00:44:35,120
Nếu n là lớn hơn so với hiện tại
giá trị nút là một trường hợp thứ ba.

1016
00:44:35,120 --> 00:44:38,250
Trường hợp thứ tư và cuối cùng là những gì?

1017
00:44:38,250 --> 00:44:39,480
Tôi nghĩ rằng chúng ta hết trường hợp, phải không?

1018
00:44:39,480 --> 00:44:44,690
Nó phải được rằng n là trong
nút hiện tại là tôi đang trên.

1019
00:44:44,690 --> 00:44:49,640
>> Vì vậy, nếu tôi đang tìm kiếm 55 vào thời điểm này
trong những câu chuyện, chi nhánh của

1020
00:44:49,640 --> 00:44:51,780
cây sẽ trở thành sự thật.

1021
00:44:51,780 --> 00:44:55,380
Vì vậy, điều thú vị ở đây là chúng tôi
trên thực tế, không giống như tuần qua, chúng tôi loại

1022
00:44:55,380 --> 00:44:56,740
của có hai trường hợp cơ sở.

1023
00:44:56,740 --> 00:44:58,300
Và họ không cần phải
được tất cả ở đầu trang.

1024
00:44:58,300 --> 00:45:01,390
Phía trên là một trường hợp cơ sở bởi vì nếu
cây là vô giá trị, không có gì để làm cả.

1025
00:45:01,390 --> 00:45:03,410
Chỉ trả lại một mã hóa cứng
giá trị sai.

1026
00:45:03,410 --> 00:45:07,400
>> Chi nhánh phía dưới là sắp xếp của
mặc định, theo đó nếu chúng tôi đã kiểm tra

1027
00:45:07,400 --> 00:45:11,550
vô giá trị, chúng tôi đã kiểm tra nếu nó phải được
để lại, nhưng nó không phải là, chúng tôi đã

1028
00:45:11,550 --> 00:45:14,640
kiểm tra nếu nó nên được quyền, nhưng nó
không nên, rõ ràng nó phải được

1029
00:45:14,640 --> 00:45:15,870
đúng cái mình đang có.

1030
00:45:15,870 --> 00:45:16,780
Đó là một trường hợp cơ sở.

1031
00:45:16,780 --> 00:45:19,920
Do đó, có hai trường hợp đệ quy
kẹp có ở giữa.

1032
00:45:19,920 --> 00:45:21,630
Nhưng tôi có thể viết
này theo thứ tự nào.

1033
00:45:21,630 --> 00:45:24,520
Tôi chỉ nghĩ đó loại cảm thấy tự nhiên
kiểm tra đầu tiên cho một lỗi có thể,

1034
00:45:24,520 --> 00:45:28,340
sau đó kiểm tra lại, sau đó kiểm tra ngay, sau đó
giả định rằng bạn đang ở nút

1035
00:45:28,340 --> 00:45:30,630
bạn đang thực sự tìm kiếm.

1036
00:45:30,630 --> 00:45:36,240
>> Vì vậy, tại sao điều này có thể có ích?

1037
00:45:36,240 --> 00:45:37,910
Vì vậy, nó quay ra -

1038
00:45:37,910 --> 00:45:42,110
và cho tôi chuyển đến một lời trêu ghẹo
đây đó trong các trang web.

1039
00:45:42,110 --> 00:45:44,920
Chúng ta sẽ bắt đầu sử dụng không phải là một
ngôn ngữ lập trình đầu tiên, nhưng một

1040
00:45:44,920 --> 00:45:46,030
ngôn ngữ đánh dấu.

1041
00:45:46,030 --> 00:45:48,740
Ngôn ngữ đánh dấu là một trong đó là
tinh thần tương tự lập trình

1042
00:45:48,740 --> 00:45:51,715
ngôn ngữ, nhưng nó không cung cấp cho bạn
khả năng thể hiện bản thân một cách hợp lý.

1043
00:45:51,715 --> 00:45:55,070
Nó chỉ cung cấp cho bạn khả năng
thể hiện bản thân cấu trúc.

1044
00:45:55,070 --> 00:45:57,960
>> Nơi nào bạn muốn đặt một cái gì đó
trên trang web, các trang web?

1045
00:45:57,960 --> 00:45:59,200
Màu sắc làm những gì bạn muốn làm cho nó?

1046
00:45:59,200 --> 00:46:00,950
Những gì kích thước phông chữ nào bạn muốn làm cho nó?

1047
00:46:00,950 --> 00:46:02,970
Từ những gì bạn thực sự
muốn trên các trang web?

1048
00:46:02,970 --> 00:46:04,060
Vì vậy, đó là một ngôn ngữ đánh dấu.

1049
00:46:04,060 --> 00:46:07,690
Nhưng sau đó chúng tôi sẽ rất nhanh chóng giới thiệu
JavaScript, đó là một chính thức

1050
00:46:07,690 --> 00:46:08,560
ngôn ngữ lập trình.

1051
00:46:08,560 --> 00:46:12,530
Tương tự như cú pháp xuất hiện
C, nhưng nó sẽ có một số

1052
00:46:12,530 --> 00:46:15,200
tốt đẹp, mạnh mẽ hơn,
tính năng thân thiện.

1053
00:46:15,200 --> 00:46:18,050
>> Và một trong những nỗi thất vọng tại này
điểm trong học kỳ là chúng ta sẽ

1054
00:46:18,050 --> 00:46:22,065
sớm thực hiện Speller trong rất ít
dòng mã sử dụng các ngôn ngữ khác

1055
00:46:22,065 --> 00:46:25,580
hơn so với C chính nó cho phép, nhưng vì lý do của
chúng tôi sẽ sớm hiểu.

1056
00:46:25,580 --> 00:46:27,750
Đây sẽ là lần đầu tiên trang web như vậy.

1057
00:46:27,750 --> 00:46:30,120
Nó sẽ hoàn toàn underwhelming,
người đầu tiên chúng tôi thực hiện.

1058
00:46:30,120 --> 00:46:31,400
Nó sẽ chỉ đơn giản, xin chào thế giới.

1059
00:46:31,400 --> 00:46:34,010
Nhưng nếu bạn đã bao giờ nhìn thấy nó
trước, đây là HTML,

1060
00:46:34,010 --> 00:46:35,670
HyperText Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Nếu bạn đi đến một tùy chọn menu nhất định trong
hầu hết bất kỳ trình duyệt trên bất kỳ trang web trên

1062
00:46:39,310 --> 00:46:43,160
internet, bạn sẽ nhìn thấy HTML
rằng một số người đã viết thư cho

1063
00:46:43,160 --> 00:46:44,400
tạo ra trang web đó.

1064
00:46:44,400 --> 00:46:47,850
Và nó có thể không giống như
ngắn gọn hoặc là gọn gàng như thế này.

1065
00:46:47,850 --> 00:46:51,400
Nhưng nó sẽ đi theo mô hình của các
mở ngoặc và dấu gạch chéo và

1066
00:46:51,400 --> 00:46:53,660
thư và có khả năng con số.

1067
00:46:53,660 --> 00:46:56,770
>> Tôi nghĩ rằng tôi muốn cung cấp cho bạn một lời trêu ghẹo
những gì bạn sẽ có thể làm

1068
00:46:56,770 --> 00:46:57,950
sau khi CS50.

1069
00:46:57,950 --> 00:47:02,620
Cho tôi đi đến cs.harvard.edu / cướp,
Rob trang chủ của chúng ta Bowden của.

1070
00:47:02,620 --> 00:47:06,080
Ông thực hiện điều này cho chúng ta.

1071
00:47:06,080 --> 00:47:07,490
Vì vậy, bạn sẽ sớm có thể làm điều đó.

1072
00:47:07,490 --> 00:47:10,660
Và cũng có thể, những gì bạn nghe
sáng nay -

1073
00:47:10,660 --> 00:47:12,480
những gì bạn nghe sáng nay -

1074
00:47:12,480 --> 00:47:13,780
>> [HAMSTER DANCE MUSIC]

1075
00:47:13,780 --> 00:47:15,702
>> - Vì bạn sẽ có thể thực hiện điều này.

1076
00:47:15,702 --> 00:47:16,790
Đang chờ đợi chúng tôi vào thứ tư.

1077
00:47:16,790 --> 00:47:17,791
Chúng ta sẽ thấy bạn sau đó.

1078
00:47:17,791 --> 00:47:22,950
>> [HAMSTER DANCE MUSIC]

1079
00:47:22,950 --> 00:47:24,300
DAVID Malan: Tại tới CS50 -

1080
00:47:24,300 --> 00:47:31,670