1
00:00:00,000 --> 00:00:03,423
>> [MUSIC CHƠI]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> Andi PENG: Chào mừng bạn đến tuần 6 phần.

4
00:00:08,210 --> 00:00:11,620
Chúng tôi đã đi trệch khỏi tiêu chuẩn của chúng tôi
Phần thứ ba của thời gian

5
00:00:11,620 --> 00:00:14,130
buổi chiều đến sáng chủ nhật đáng yêu này.

6
00:00:14,130 --> 00:00:17,330
Cảm ơn bạn cho tất cả mọi người mà
tham gia cùng tôi ngày hôm nay, nhưng nghiêm túc,

7
00:00:17,330 --> 00:00:18,170
một tràng pháo tay.

8
00:00:18,170 --> 00:00:20,600
>> Đó là một nỗ lực khá lớn.

9
00:00:20,600 --> 00:00:23,600
Tôi gần như đã thậm chí không làm cho nó
lên trong thời gian, nhưng nó là OK.

10
00:00:23,600 --> 00:00:27,520
Vì vậy, tôi biết rằng tất cả các bạn
đã đã thực hiện nó vào bài kiểm tra.

11
00:00:27,520 --> 00:00:30,370
Trước hết, chào mừng
mặt trái của điều đó.

12
00:00:30,370 --> 00:00:32,917
>> Thứ hai, chúng ta sẽ nói về nó.

13
00:00:32,917 --> 00:00:34,000
Chúng ta sẽ nói về các bài kiểm tra.

14
00:00:34,000 --> 00:00:35,700
Chúng tôi sẽ nói về cách
bạn đang làm trong lớp.

15
00:00:35,700 --> 00:00:36,550
Bạn se ổn thôi.

16
00:00:36,550 --> 00:00:39,080
Tôi có câu đố của bạn
bạn vào cuối ở đây,

17
00:00:39,080 --> 00:00:42,120
vì vậy nếu các bạn muốn đi
một nhìn vào nó, hoàn toàn tốt.

18
00:00:42,120 --> 00:00:46,590
>> Vì vậy, một cách nhanh chóng trước khi chúng tôi bắt đầu,
chương trình nghị sự cho ngày hôm nay là như sau.

19
00:00:46,590 --> 00:00:48,430
Như bạn có thể thấy, chúng tôi
bắn nhanh cơ bản

20
00:00:48,430 --> 00:00:52,120
thông qua một bó toàn bộ các cấu trúc dữ liệu
thực sự, thực sự, thực sự nhanh chóng.

21
00:00:52,120 --> 00:00:54,380
Vì vậy, như vậy, nó sẽ không được
siêu tương tác ngày hôm nay.

22
00:00:54,380 --> 00:00:59,620
Nó sẽ chỉ là tôi loại la hét
điều mà bạn, và nếu tôi làm bạn bối rối,

23
00:00:59,620 --> 00:01:02,680
nếu tôi đi quá nhanh, cho tôi biết.

24
00:01:02,680 --> 00:01:05,200
Chúng chỉ khác nhau dữ liệu
cấu trúc, và như là một phần

25
00:01:05,200 --> 00:01:07,070
pset của bạn cho việc này
tuần sắp tới, bạn sẽ

26
00:01:07,070 --> 00:01:10,340
được yêu cầu để thực hiện một trong số họ,
có lẽ hai them-- hai người

27
00:01:10,340 --> 00:01:12,319
trong pset của bạn.

28
00:01:12,319 --> 00:01:14,610
OK, vì vậy tôi chỉ cần đi để
bắt đầu với một số thông báo.

29
00:01:14,610 --> 00:01:19,070
Chúng tôi sẽ đi qua ngăn xếp và hàng đợi nhiều hơn ở
sâu hơn so với những gì chúng ta đã làm trước các bài kiểm tra.

30
00:01:19,070 --> 00:01:20,990
Chúng tôi sẽ đi qua liên kết
liệt kê một lần nữa, một lần nữa,

31
00:01:20,990 --> 00:01:23,899
sâu hơn so với những gì
chúng tôi đã có trước khi các bài kiểm tra.

32
00:01:23,899 --> 00:01:26,440
Và sau đó chúng ta sẽ nói về băm
bảng, cây và cố gắng, mà

33
00:01:26,440 --> 00:01:28,890
là tất cả khá cần thiết cho pset của bạn.

34
00:01:28,890 --> 00:01:32,925
Và sau đó chúng ta sẽ đi qua một số
lời khuyên hữu ích cho pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, vậy đố 0.

36
00:01:37,360 --> 00:01:41,090
Trung bình là 58%.

37
00:01:41,090 --> 00:01:45,370
Nó là rất thấp, và do đó các bạn tất cả
đã làm rất, rất tốt phù hợp

38
00:01:45,370 --> 00:01:46,510
với.

39
00:01:46,510 --> 00:01:49,970
>> Khá nhiều, nguyên tắc nhỏ là nếu bạn
trong vòng một độ lệch chuẩn của giá trị trung bình

40
00:01:49,970 --> 00:01:52,990
đặc biệt là kể từ khi chúng tôi đang ở trong một ít
phần thoải mái, bạn hoàn toàn tốt.

41
00:01:52,990 --> 00:01:54,120
Bạn đang đi đúng hướng.

42
00:01:54,120 --> 00:01:55,190
Cuộc sống là tốt.

43
00:01:55,190 --> 00:01:58,952
>> Tôi biết nó đáng sợ khi nghĩ rằng
Tôi đã như một 40% trên bài kiểm tra này.

44
00:01:58,952 --> 00:02:00,160
Tôi sẽ không lớp này.

45
00:02:00,160 --> 00:02:02,243
Tôi hứa với bạn, bạn không
sẽ thất bại lớp.

46
00:02:02,243 --> 00:02:03,680
Bạn hoàn toàn tốt.

47
00:02:03,680 --> 00:02:06,850
>> Đối với những người bạn của những người đã vượt qua
giá trị trung bình, ấn tượng, ấn tượng,

48
00:02:06,850 --> 00:02:08,780
như, nghiêm túc thực hiện tốt.

49
00:02:08,780 --> 00:02:09,689
Tôi có họ với tôi.

50
00:02:09,689 --> 00:02:11,730
Hãy đến đón chúng
ở cuối phần.

51
00:02:11,730 --> 00:02:14,520
Hãy cho tôi biết nếu bạn có bất kỳ
vấn đề, câu hỏi với họ.

52
00:02:14,520 --> 00:02:17,204
Nếu chúng ta cộng số điểm của bạn
sai, hãy cho chúng tôi biết.

53
00:02:17,204 --> 00:02:21,240
>> OK, vì vậy pset5, đây là một thực sự
tuần lạ cho Yale trong ý nghĩa

54
00:02:21,240 --> 00:02:24,240
rằng pset chúng tôi là do
Thứ Tư lúc trưa bao gồm

55
00:02:24,240 --> 00:02:27,317
Vào cuối ngày, vì vậy nó thực sự
về mặt lý thuyết do thứ ba vào buổi trưa.

56
00:02:27,317 --> 00:02:29,150
Có lẽ không có một kết thúc
tại thứ ba vào buổi trưa.

57
00:02:29,150 --> 00:02:30,830
Điều đó hoàn toàn tốt.

58
00:02:30,830 --> 00:02:33,700
Chúng tôi sẽ có những giờ văn phòng
tối nay cũng như đêm thứ hai.

59
00:02:33,700 --> 00:02:36,810
Và tất cả các mục trong tuần này sẽ
thực sự được biến thành các cuộc hội thảo,

60
00:02:36,810 --> 00:02:38,800
vì vậy cảm thấy tự do để bật trong
bất kỳ phần bạn muốn,

61
00:02:38,800 --> 00:02:42,810
và họ sẽ có loại mini-pset
hội thảo để được giúp đỡ về điều đó.

62
00:02:42,810 --> 00:02:45,620
Vì vậy, như vậy, đây là phần duy nhất
nơi chúng tôi đang giảng dạy vật chất.

63
00:02:45,620 --> 00:02:49,220
Tất cả các phần khác sẽ được tập trung
hoàn toàn vào sự giúp đỡ cho các pset.

64
00:02:49,220 --> 00:02:50,146
Yeah?

65
00:02:50,146 --> 00:02:52,000
>> Đung đâu là giờ làm việc?

66
00:02:52,000 --> 00:02:56,120
>> Andi PENG: Thời gian làm việc
tonight-- oh, câu hỏi hay.

67
00:02:56,120 --> 00:03:00,580
Tôi nghĩ giờ hành chính tối nay
là trong Teal hoặc tại Commons.

68
00:03:00,580 --> 00:03:02,984
Nếu bạn kiểm tra trực tuyến CS50
và bạn đi đến giờ làm việc,

69
00:03:02,984 --> 00:03:05,650
không nên có một lịch trình
cho bạn nơi mà tất cả chúng đều.

70
00:03:05,650 --> 00:03:07,954
>> Tôi biết một trong hai đêm nay
hoặc ngày mai là teal,

71
00:03:07,954 --> 00:03:10,120
và tôi nghĩ rằng chúng tôi có thể có
commons cho đêm khác.

72
00:03:10,120 --> 00:03:11,020
Tôi không chắc.

73
00:03:11,020 --> 00:03:11,700
Câu hỏi hay.

74
00:03:11,700 --> 00:03:14,430
Kiểm tra trên CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, bất kỳ câu hỏi liên quan đến việc
Lịch trình tiếp theo như ba ngày?

76
00:03:18,780 --> 00:03:21,690
Tôi hứa với các bạn như David
cho biết, đây là đỉnh đồi.

77
00:03:21,690 --> 00:03:23,050
Các bạn đang ở gần đó.

78
00:03:23,050 --> 00:03:24,644
Hơn chỉ trong ba ngày.

79
00:03:24,644 --> 00:03:26,310
Đạt được điều đó, và sau đó chúng tôi sẽ tất cả đi xuống.

80
00:03:26,310 --> 00:03:28,114
Chúng tôi sẽ có một kì nghỉ CS-free tốt đẹp.

81
00:03:28,114 --> 00:03:28,780
Chào mừng trở lại.

82
00:03:28,780 --> 00:03:30,779
Chúng tôi sẽ nhảy vào web
lập trình và phát triển,

83
00:03:30,779 --> 00:03:35,150
điều đó rất thú vị so
với một số các psets khác.

84
00:03:35,150 --> 00:03:37,974
Và nó sẽ được lạnh, và
chúng ta sẽ có rất nhiều niềm vui.

85
00:03:37,974 --> 00:03:38,890
Chúng tôi sẽ có thêm kẹo.

86
00:03:38,890 --> 00:03:39,730
Xin lỗi cho kẹo.

87
00:03:39,730 --> 00:03:40,945
Tôi quên kẹo.

88
00:03:40,945 --> 00:03:43,310
Đó là một buổi sáng thô.

89
00:03:43,310 --> 00:03:46,340
Vì vậy, các bạn đang ở gần đó,
và tôi thực sự tự hào về các bạn.

90
00:03:46,340 --> 00:03:49,570
>> OK, vì vậy ngăn xếp.

91
00:03:49,570 --> 00:03:53,331
Ai yêu các câu hỏi về Jack
và quần áo của mình vào các bài kiểm tra?

92
00:03:53,331 --> 00:03:53,830
Không một ai?

93
00:03:53,830 --> 00:03:56,500
Được rồi, ổn mà.

94
00:03:56,500 --> 00:04:00,200
>> Vì vậy, về cơ bản như bạn có thể
hình ảnh Jack, anh chàng này ở đây,

95
00:04:00,200 --> 00:04:03,350
yêu thương để lấy quần áo
ra khỏi đỉnh của ngăn xếp,

96
00:04:03,350 --> 00:04:05,750
và ông đặt nó trở lại vào
stack sau khi anh ta thực hiện.

97
00:04:05,750 --> 00:04:07,600
Vì vậy, bằng cách này, ông không bao giờ
dường như nhận được

98
00:04:07,600 --> 00:04:10,090
để dưới cùng của
ngăn xếp trong quần áo của mình.

99
00:04:10,090 --> 00:04:12,600
Vì vậy, đây loại mô tả
cấu trúc dữ liệu cơ bản

100
00:04:12,600 --> 00:04:16,610
làm thế nào một chồng được thực hiện.

101
00:04:16,610 --> 00:04:20,060
>> Về cơ bản, suy nghĩ của một
ngăn xếp như bất kỳ ngăn xếp của các đối tượng

102
00:04:20,060 --> 00:04:24,900
nơi bạn đặt mọi thứ lên đầu trang, và
sau đó bạn bật chúng ra khỏi đầu.

103
00:04:24,900 --> 00:04:28,600
Vì vậy, LIFO là từ viết tắt của chúng tôi thích
để use-- cuối In, First Out.

104
00:04:28,600 --> 00:04:32,480
Và như vậy kéo dài vào đầu
ngăn xếp là một trong những đầu tiên mà đi ra.

105
00:04:32,480 --> 00:04:34,260
Và do đó, hai thuật ngữ
chúng tôi muốn liên kết

106
00:04:34,260 --> 00:04:36,190
với điều đó được gọi là push và pop.

107
00:04:36,190 --> 00:04:39,790
Khi bạn đẩy một cái gì đó lên
ngăn xếp, và bạn bật nó trở lại.

108
00:04:39,790 --> 00:04:43,422
>> Và vì vậy tôi đoán đây là loại một
khái niệm trừu tượng cho những người bạn

109
00:04:43,422 --> 00:04:45,630
ai muốn xem như một
thực hiện thực tế của điều này

110
00:04:45,630 --> 00:04:46,740
trong thế giới thực.

111
00:04:46,740 --> 00:04:50,170
Làm thế nào nhiều bạn đã viết một bài luận
có lẽ như một giờ trước khi nó là do,

112
00:04:50,170 --> 00:04:54,510
và bạn vô tình xóa một lớn
đoạn của nó, giống như vô tình?

113
00:04:54,510 --> 00:04:58,560
Và sau đó những gì kiểm soát làm
chúng tôi sử dụng để đưa nó trở lại?

114
00:04:58,560 --> 00:05:00,030
Control-Z, yeah?

115
00:05:00,030 --> 00:05:03,640
Control-Z, vì vậy số lượng lần
rằng Control-Z đã cứu cuộc đời tôi,

116
00:05:03,640 --> 00:05:08,820
đã lưu ass của tôi, mỗi lần
đó là thực hiện thông qua một chồng.

117
00:05:08,820 --> 00:05:13,020
>> Về cơ bản tất cả các thông tin
đó là trên tài liệu Word của bạn,

118
00:05:13,020 --> 00:05:15,080
nó được đẩy và bật theo ý muốn.

119
00:05:15,080 --> 00:05:19,460
Và do đó, về cơ bản bất cứ khi nào bạn
xóa bất cứ điều gì, bạn bật nó trở lại.

120
00:05:19,460 --> 00:05:22,820
Và sau đó nếu bạn cần nó trở lại, bạn
đẩy nó, đó là những gì Control-C không.

121
00:05:22,820 --> 00:05:26,770
Và chức năng trên thế giới rất thật
cấu trúc dữ liệu như thế nào đơn giản

122
00:05:26,770 --> 00:05:28,690
có thể giúp cuộc sống hàng ngày của bạn.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Vì vậy, một struct là cách mà
chúng tôi thực sự tạo ra một chồng.

125
00:05:40,150 --> 00:05:44,720
Chúng tôi gõ xác định cấu trúc, và sau đó
chúng ta gọi nó là ngăn xếp ở phía dưới.

126
00:05:44,720 --> 00:05:47,440
Và trong ngăn xếp,
chúng tôi có hai thông số

127
00:05:47,440 --> 00:05:51,580
rằng chúng ta có thể thao tác cơ bản,
vì vậy chúng tôi có char chuỗi sao năng lực.

128
00:05:51,580 --> 00:05:55,150
>> Tất cả những gì nó đang làm
đang tạo ra một mảng

129
00:05:55,150 --> 00:05:58,835
rằng chúng ta có thể lưu trữ bất cứ điều gì bạn muốn
mà chúng ta có thể xác định khả năng của mình.

130
00:05:58,835 --> 00:06:01,990
Công suất là chỉ số tiền tối đa của
mặt hàng chúng tôi có thể đưa vào mảng này.

131
00:06:01,990 --> 00:06:05,660
int size kích thước là quầy mà giữ
theo dõi bao nhiêu mặt hàng hiện đang là

132
00:06:05,660 --> 00:06:07,850
trong ngăn xếp.

133
00:06:07,850 --> 00:06:11,860
Vì vậy, sau đó chúng ta có thể theo dõi, A,
cả lớn như thế nào stack thực tế là,

134
00:06:11,860 --> 00:06:14,850
và, B, bao nhiêu đó ngăn xếp
chúng tôi đầy bởi vì chúng tôi không muốn

135
00:06:14,850 --> 00:06:18,800
tràn trên những năng lực của chúng tôi là.

136
00:06:18,800 --> 00:06:24,340
>> Vì vậy, ví dụ, điều này đáng yêu
Câu hỏi là trên bài kiểm tra của bạn.

137
00:06:24,340 --> 00:06:28,160
Về cơ bản cách làm chúng ta đẩy
vào đầu của một chồng.

138
00:06:28,160 --> 00:06:28,830
Khá đơn giản.

139
00:06:28,830 --> 00:06:30,621
Nếu bạn nhìn vào nó,
chúng ta sẽ đi qua này.

140
00:06:30,621 --> 00:06:32,640
Nếu [Không nghe thấy] size--
nhớ, bất cứ khi nào bạn

141
00:06:32,640 --> 00:06:35,300
muốn truy cập vào bất kỳ
Tham số trong một cấu trúc,

142
00:06:35,300 --> 00:06:40,320
bạn làm tên của struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Trong trường hợp này, s là
tên của ngăn xếp của chúng tôi.

144
00:06:42,720 --> 00:06:46,230
Chúng tôi muốn truy cập vào kích thước
của nó, vì vậy chúng tôi làm s.size.

145
00:06:46,230 --> 00:06:50,280
Vì vậy, miễn là kích thước không phải là
bằng công suất hoặc kéo dài

146
00:06:50,280 --> 00:06:52,940
vì nó là ít hơn so với năng lực,
hoặc là sẽ làm việc ở đây.

147
00:06:52,940 --> 00:06:57,180
>> Bạn muốn truy cập vào bên trong
của ngăn xếp của bạn, vì vậy s.strings,

148
00:06:57,180 --> 00:07:00,790
và bạn đang đi để đưa con số mới
mà bạn muốn chèn vào đó.

149
00:07:00,790 --> 00:07:05,030
Hãy chỉ nói rằng chúng ta sẽ muốn
chèn int n vào ngăn xếp,

150
00:07:05,030 --> 00:07:08,905
chúng ta có thể làm s.strings,
ngoặc, s.size bằng n.

151
00:07:08,905 --> 00:07:11,030
Bởi vì kích thước là nơi chúng tôi
Hiện tại trong ngăn xếp

152
00:07:11,030 --> 00:07:14,590
nếu chúng ta để đẩy
nó trên, chúng ta chỉ cần truy cập

153
00:07:14,590 --> 00:07:17,370
bất cứ nơi nào kích thước là,
viên mãn hiện tại của chồng,

154
00:07:17,370 --> 00:07:21,729
và chúng tôi đẩy int n vào nó.

155
00:07:21,729 --> 00:07:24,770
Và sau đó, chúng tôi muốn chắc chắn rằng
chúng tôi cũng cách tăng kích thước của n,

156
00:07:24,770 --> 00:07:27,436
vì vậy chúng tôi có thể theo dõi của chúng tôi đã
thêm một điều thêm vào stack.

157
00:07:27,436 --> 00:07:29,660
Bây giờ chúng ta có một kích thước lớn hơn.

158
00:07:29,660 --> 00:07:33,196
Liệu điều này ở đây có ý nghĩa để
tất cả mọi người, làm thế nào nó hoạt động một cách hợp lý?

159
00:07:33,196 --> 00:07:34,160
Đó là một loại nhanh chóng.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
Đung bạn có thể đi qua
các s.stringss.strings [s.size] một lần nữa?

162
00:07:42,160 --> 00:07:45,808
Andi PENG: Chắc chắn rồi, vì vậy những gì hiện
s.size hiện đang cung cấp cho chúng ta?

163
00:07:45,808 --> 00:07:47,440
Đung Đó là kích thước hiện tại.

164
00:07:47,440 --> 00:07:50,890
Andi PENG: Chính xác, do đó,
chỉ số hiện tại mà kích thước của chúng tôi là,

165
00:07:50,890 --> 00:07:57,780
và vì vậy chúng tôi muốn đưa các số nguyên mới
rằng chúng ta muốn chèn vào s.size.

166
00:07:57,780 --> 00:07:58,760
Điều đó có ý nghĩa?

167
00:07:58,760 --> 00:08:01,110
Bởi vì s.strings, tất cả những gì
là là tên của mảng.

168
00:08:01,110 --> 00:08:03,510
Tất cả đó là là truy cập
mảng trong cấu trúc của chúng tôi,

169
00:08:03,510 --> 00:08:06,030
và do đó, nếu chúng ta muốn
đặt n vào chỉ số đó,

170
00:08:06,030 --> 00:08:09,651
chúng ta chỉ có thể truy cập nó
sử dụng dấu ngoặc s.size.

171
00:08:09,651 --> 00:08:10,150
Mát.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Tất cả các quyền, pop, tôi giả nó ra
cho bạn, nhưng khái niệm tương tự.

174
00:08:18,916 --> 00:08:19,790
Điều đó có ý nghĩa?

175
00:08:19,790 --> 00:08:22,310
Nếu kích thước lớn
hơn số không, sau đó bạn

176
00:08:22,310 --> 00:08:25,350
biết rằng bạn muốn để có cái gì
ra vì nếu kích thước không phải là

177
00:08:25,350 --> 00:08:27,620
lớn hơn số không, sau đó bạn
không có gì trong ngăn xếp.

178
00:08:27,620 --> 00:08:29,840
>> Vì vậy, bạn chỉ muốn thực hiện
mã này, nó chỉ có thể

179
00:08:29,840 --> 00:08:32,320
bật nếu có cái gì đó để bật.

180
00:08:32,320 --> 00:08:35,830
Vì vậy, nếu kích thước lớn
hơn 0, chúng ta trừ đi kích thước.

181
00:08:35,830 --> 00:08:40,020
Chúng tôi giảm các kích thước và sau đó quay trở lại
bất cứ điều gì là bên trong của nó, vì

182
00:08:40,020 --> 00:08:42,710
bằng cách popping, chúng tôi muốn
truy cập bất cứ điều gì được lưu trữ

183
00:08:42,710 --> 00:08:45,694
trong chỉ mục của các đỉnh của ngăn xếp.

184
00:08:45,694 --> 00:08:46,610
Tất cả mọi thứ có ý nghĩa?

185
00:08:46,610 --> 00:08:49,693
Nếu tôi làm bạn kẻ viết này ra,
các bạn sẽ có thể viết nó ra?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, các bạn có thể chơi xung quanh với nó.

188
00:08:53,570 --> 00:08:55,252
Không phải lo lắng nếu bạn không nhận được nó.

189
00:08:55,252 --> 00:08:57,460
Chúng tôi không có thời gian để mã
nó ra ngày hôm nay bởi vì chúng tôi đã

190
00:08:57,460 --> 00:08:59,959
có rất nhiều các cấu trúc
đi qua, nhưng về cơ bản

191
00:08:59,959 --> 00:09:02,214
giả, rất, rất tương tự để đẩy.

192
00:09:02,214 --> 00:09:03,380
Chỉ cần làm theo dọc theo logic.

193
00:09:03,380 --> 00:09:06,092
Hãy chắc chắn rằng bạn đang truy cập tất cả các
tính năng của cấu trúc của bạn một cách chính xác.

194
00:09:06,092 --> 00:09:06,574
Yeah?

195
00:09:06,574 --> 00:09:09,282
>> ĐỐI TƯỢNG: liệu những slide và
toàn bộ điều này được ký hôm nay-ish?

196
00:09:09,282 --> 00:09:11,586
Andi PENG: Luôn luôn, vâng.

197
00:09:11,586 --> 00:09:13,710
Tôi sẽ cố gắng đưa
này lên như một giờ sau.

198
00:09:13,710 --> 00:09:16,626
Tôi sẽ gửi email cho David, David sẽ cố gắng
đặt nó lên như một giờ sau này.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, vậy thì chúng ta bước sang khác này
cấu trúc dữ liệu đáng yêu gọi là hàng đợi.

201
00:09:25,470 --> 00:09:30,140
Như các bạn có thể thấy ở đây, một
hàng đợi, đối với người Anh trong số chúng tôi,

202
00:09:30,140 --> 00:09:32,010
tất cả đó là là một dòng.

203
00:09:32,010 --> 00:09:34,680
Vì vậy, trái với những gì
bạn nghĩ rằng một chồng là,

204
00:09:34,680 --> 00:09:37,750
một hàng đợi là chính xác những gì
logic bạn nghĩ rằng đó là.

205
00:09:37,750 --> 00:09:41,914
Nó được tổ chức bởi các quy tắc của FIFO,
đó là First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Nếu bạn là người đầu tiên
một trong các dòng, bạn

207
00:09:43,705 --> 00:09:46,230
một trong những đầu tiên
đi ra khỏi dòng.

208
00:09:46,230 --> 00:09:49,680
>> Vì vậy, những gì chúng tôi muốn kêu gọi này
được dequeueing và enqueueing.

209
00:09:49,680 --> 00:09:52,380
Nếu chúng ta muốn thêm một cái gì đó
vào hàng đợi của chúng tôi, chúng tôi enqueue.

210
00:09:52,380 --> 00:09:55,690
Nếu chúng ta muốn dequeue, hoặc mất
đi cái gì đó, chúng ta dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Vì vậy, cùng một ý nghĩa mà chúng ta đang loại
tạo ra yếu tố kích thước cố định mà chúng ta

212
00:10:03,350 --> 00:10:06,500
có thể lưu trữ nhất định
thứ, nhưng chúng ta cũng có thể

213
00:10:06,500 --> 00:10:10,100
thay đổi nơi chúng tôi đang đặt
các thông số bên trong của họ

214
00:10:10,100 --> 00:10:13,140
dựa trên những gì loại
chức năng chúng tôi muốn.

215
00:10:13,140 --> 00:10:16,700
Vì vậy, ngăn xếp, chúng tôi muốn cuối cùng
một, N là người ra đầu tiên.

216
00:10:16,700 --> 00:10:19,800
Queue là chúng tôi muốn điều đầu tiên
để được điều đầu tiên ra.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Vì vậy, các cấu trúc kiểu
xác định, như bạn có thể thấy,

219
00:10:26,710 --> 00:10:29,470
đó là một chút khác nhau
từ những gì các ngăn xếp được

220
00:10:29,470 --> 00:10:33,120
không chỉ bởi vì chúng ta phải giữ
theo dõi các nơi kích thước là hiện nay,

221
00:10:33,120 --> 00:10:37,420
chúng tôi cũng muốn theo dõi của người đứng đầu
cũng như nơi chúng tôi đang có.

222
00:10:37,420 --> 00:10:39,580
Vì vậy, tôi nghĩ rằng đó là dễ dàng hơn
nếu tôi vẽ này lên.

223
00:10:39,580 --> 00:10:53,270
Vì vậy, chúng ta hãy tưởng tượng chúng ta đã có một hàng đợi,
vì vậy chúng ta hãy nói người đứng đầu là đúng ở đây.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Người đứng đầu của dòng, chúng ta hãy
chỉ nói rằng hiện đang có,

226
00:10:58,310 --> 00:11:01,809
và chúng tôi muốn chèn
một cái gì đó vào trong hàng đợi.

227
00:11:01,809 --> 00:11:04,350
Tôi sẽ gọi cho kích thước cơ bản
là những điều tương tự như đuôi,

228
00:11:04,350 --> 00:11:06,314
cuối hàng đợi của bạn bất cứ nơi nào có.

229
00:11:06,314 --> 00:11:07,730
Hãy chỉ nói rằng kích thước là quyền ở đây.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Vì vậy, làm thế nào một khả thi
chèn một cái gì đó vào một hàng đợi?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Chỉ số gì làm chúng tôi muốn đặt
nơi mà chúng ta muốn chèn vào.

234
00:11:24,130 --> 00:11:29,320
Nếu đây là sự khởi đầu của bạn
xếp hàng và đây là kết thúc của nó

235
00:11:29,320 --> 00:11:31,860
hoặc kích thước của nó, nơi nào chúng ta
muốn thêm đối tượng kế tiếp?

236
00:11:31,860 --> 00:11:32,920
>> Đung [Không nghe thấy]

237
00:11:32,920 --> 00:11:35,920
Andi PENG: Chính xác, bạn muốn thêm
nó tùy thuộc vào bạn đã viết nó.

238
00:11:35,920 --> 00:11:37,840
Hoặc này là trống hay là trống.

239
00:11:37,840 --> 00:11:42,630
Vì vậy, bạn muốn thêm vào thì có lẽ nó
ở đây vì nếu kích thước is--

240
00:11:42,630 --> 00:11:50,540
nếu đây là tất cả đầy đủ, bạn muốn
để thêm nó phải ở đây, phải không?

241
00:11:50,540 --> 00:11:57,150
>> Và đó là, trong khi rất, rất
đơn giản, không hoàn toàn luôn luôn đúng

242
00:11:57,150 --> 00:12:00,690
bởi vì sự khác biệt chính
giữa một hàng đợi và một chồng

243
00:12:00,690 --> 00:12:04,350
là hàng đợi có thể
thực sự được thao tác

244
00:12:04,350 --> 00:12:06,980
do đó những thay đổi đầu
tùy thuộc vào nơi bạn muốn

245
00:12:06,980 --> 00:12:08,650
đầu cue của bạn để bắt đầu.

246
00:12:08,650 --> 00:12:11,900
Và kết quả là, cái đuôi của bạn
cũng sẽ thay đổi.

247
00:12:11,900 --> 00:12:14,770
Và do đó, có một cái nhìn tại
mã này ngay bây giờ.

248
00:12:14,770 --> 00:12:18,620
Như các bạn cũng được yêu cầu
viết ra trên các bài kiểm tra, enqueue.

249
00:12:18,620 --> 00:12:22,580
Có lẽ chúng ta sẽ nói chuyện thông qua tại sao
câu trả lời là những gì nó được.

250
00:12:22,580 --> 00:12:26,790
>> Tôi có thể không khá phù hợp với dòng này trên một,
nhưng về cơ bản đoạn mã này

251
00:12:26,790 --> 00:12:29,030
nên được trên một dòng.

252
00:12:29,030 --> 00:12:30,140
Chi tiêu như 30 giây.

253
00:12:30,140 --> 00:12:33,000
Hãy xem, và xem tại sao
đây là cách mà nó được.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Rất, cấu trúc rất giống nhau, rất, rất
cấu trúc tương tự như trước đây

256
00:12:55,420 --> 00:12:58,090
chồng ngoại trừ có lẽ
một dòng mã.

257
00:12:58,090 --> 00:13:01,190
Và đó là một dòng mã
xác định các chức năng.

258
00:13:01,190 --> 00:13:03,900
Và nó thực sự khác biệt
một hàng đợi từ một chồng.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Bất cứ ai muốn để mất một đâm
tại giải thích tại sao bạn đã

261
00:13:22,010 --> 00:13:24,980
có điều phức tạp này tại đây?

262
00:13:24,980 --> 00:13:27,845
Chúng ta thấy sự trở lại của chúng tôi
tuyệt vời modulus bạn.

263
00:13:27,845 --> 00:13:31,020
Như các bạn sẽ sớm đi
để nhận ra trong lập trình,

264
00:13:31,020 --> 00:13:34,910
hầu như bất cứ lúc nào bạn cần một cái gì đó
để bọc xung quanh bất cứ điều gì,

265
00:13:34,910 --> 00:13:36,850
mô đun sẽ là cách để làm điều đó.

266
00:13:36,850 --> 00:13:40,510
Vì vậy, khi biết rằng, không ai muốn
để cố gắng giải thích rằng dòng mã?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Vâng, tất cả các câu trả lời
chấp nhận và hoan nghênh.

269
00:13:47,507 --> 00:13:48,840
Đung bạn đang nói chuyện với tôi?

270
00:13:48,840 --> 00:13:49,506
Andi PENG: Yeah.

271
00:13:49,506 --> 00:13:56,200
Đung Oh, không xin lỗi.

272
00:13:56,200 --> 00:14:00,250
Andi PENG: OK, vì vậy chúng ta
đi bộ qua đoạn mã này.

273
00:14:00,250 --> 00:14:03,642
Vì vậy, khi bạn đang cố gắng để
thêm một cái gì đó vào một hàng đợi,

274
00:14:03,642 --> 00:14:08,510
trong trường hợp đáng yêu mà người đứng đầu xảy ra
là ngay tại đây, nó rất dễ dàng cho chúng tôi

275
00:14:08,510 --> 00:14:10,960
chỉ cần đi đến cùng
chèn một cái gì đó, phải không?

276
00:14:10,960 --> 00:14:14,690
Nhưng điểm chung của một hàng đợi
rằng người đứng đầu thực sự có thể tự động

277
00:14:14,690 --> 00:14:17,280
thay đổi tùy thuộc vào nơi chúng tôi
muốn bắt đầu q của chúng tôi có được,

278
00:14:17,280 --> 00:14:19,880
và như vậy, đuôi
cũng sẽ thay đổi.

279
00:14:19,880 --> 00:14:31,100
>> Và như vậy tưởng tượng rằng đây không phải là
xếp hàng, nhưng thay vì đây là hàng đợi.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Hãy nói rằng người đứng đầu là đúng ở đây.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Hãy nói rằng hàng đợi của chúng tôi trông như thế này.

284
00:14:56,980 --> 00:15:00,190
Nếu chúng ta muốn thay đổi nơi
đầu dòng là,

285
00:15:00,190 --> 00:15:03,400
hãy nói chúng tôi chuyển đầu
cách này và kích cỡ tại đây.

286
00:15:03,400 --> 00:15:07,100
>> Bây giờ chúng ta muốn thêm một cái gì đó để
hàng đợi này, nhưng như các bạn có thể thấy,

287
00:15:07,100 --> 00:15:11,150
nó không phải đơn giản như vậy để chỉ
thêm bất cứ điều gì là sau khi kích thước

288
00:15:11,150 --> 00:15:13,630
bởi vì sau đó chúng tôi chạy ra khỏi
giới hạn của mảng thực tế của chúng tôi.

289
00:15:13,630 --> 00:15:16,190
Nơi mà chúng tôi muốn thực sự thêm là ở đây.

290
00:15:16,190 --> 00:15:18,610
Đó là vẻ đẹp của một hàng đợi
là để chúng ta, nó trực quan

291
00:15:18,610 --> 00:15:22,380
trông giống như các dòng đi như thế này,
nhưng khi được lưu trữ trong một cấu trúc dữ liệu,

292
00:15:22,380 --> 00:15:29,370
họ cung cấp cho nó như là giống như một chu kỳ.

293
00:15:29,370 --> 00:15:32,360
Nó loại kết thúc tốt đẹp xung quanh
vào phía trước cùng một cách

294
00:15:32,360 --> 00:15:34,780
rằng một dòng cũng có thể bọc
xung quanh phụ thuộc vào bất cứ nơi nào bạn

295
00:15:34,780 --> 00:15:36,279
muốn đầu dòng được.

296
00:15:36,279 --> 00:15:38,630
Và như vậy nếu chúng ta hãy
nhìn xuống ở đây, chúng ta hãy

297
00:15:38,630 --> 00:15:40,880
nói chúng tôi muốn tạo ra một
chức năng gọi là enqueue.

298
00:15:40,880 --> 00:15:43,980
Chúng tôi muốn thêm int n vào q đó.

299
00:15:43,980 --> 00:15:49,250
Nếu q.size q-- chúng ta sẽ gọi là dữ liệu của chúng tôi
structure-- nếu queue.size chúng tôi không

300
00:15:49,250 --> 00:15:52,520
bằng công suất hoặc nếu
nó ít hơn so với năng lực,

301
00:15:52,520 --> 00:15:55,120
q.strings là mảng trong q của chúng tôi.

302
00:15:55,120 --> 00:15:58,380
Chúng ta sẽ thiết
mà bằng q.heads,

303
00:15:58,380 --> 00:16:02,730
mà là ngay đây, cộng với q.size
modulus bởi năng lực, mà

304
00:16:02,730 --> 00:16:04,290
bọc chúng lại quanh đây.

305
00:16:04,290 --> 00:16:08,040
>> Vì vậy, trong ví dụ này, chỉ số
đầu là 1, phải không?

306
00:16:08,040 --> 00:16:11,480
Các chỉ số của kích thước là 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Vì vậy, chúng ta có thể làm 1 cộng với 4 mô đun
bởi khả năng của chúng tôi mà là 5.

308
00:16:19,500 --> 00:16:20,920
Những gì mà không cho chúng ta?

309
00:16:20,920 --> 00:16:23,270
Chỉ số là gì mà
đi ra khỏi đây?

310
00:16:23,270 --> 00:16:24,080
>> Đung 0.

311
00:16:24,080 --> 00:16:27,870
>> Andi PENG: 0,
sẽ xảy ra là ngay tại đây,

312
00:16:27,870 --> 00:16:30,640
và vì vậy chúng tôi muốn có thể
để chèn vào ngay đây.

313
00:16:30,640 --> 00:16:34,730
Và do đó, phương trình này ở đây loại
chỉ hoạt động với bất kỳ số điện

314
00:16:34,730 --> 00:16:36,750
tùy thuộc vào nơi bạn
đầu và kích thước của bạn.

315
00:16:36,750 --> 00:16:38,541
Nếu bạn biết những gì các
điều là, bạn biết

316
00:16:38,541 --> 00:16:43,170
chính xác nơi bạn muốn chèn
bất cứ điều gì là sau khi hàng đợi của bạn.

317
00:16:43,170 --> 00:16:44,640
Điều đó có ý nghĩa với tất cả mọi người?

318
00:16:44,640 --> 00:16:48,560
>> Tôi biết loại của một bộ não
trêu ghẹo đặc biệt là kể từ nay

319
00:16:48,560 --> 00:16:50,512
đến hậu quả của bài kiểm tra của bạn.

320
00:16:50,512 --> 00:16:52,220
Nhưng hy vọng rằng tất cả mọi người
bây giờ có thể hiểu được

321
00:16:52,220 --> 00:16:57,800
tại sao giải pháp này hay này
chức năng là cách mà nó được.

322
00:16:57,800 --> 00:16:59,840
Bất cứ ai một chút không rõ ràng về điều đó?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
ĐƯỢC.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> Và vì vậy bây giờ, nếu bạn
muốn dequeue, điều này

327
00:17:09,970 --> 00:17:15,240
là nơi đầu của chúng tôi sẽ được chuyển
bởi vì nếu chúng ta dequeue,

328
00:17:15,240 --> 00:17:17,030
chúng tôi không đưa ra khỏi cuối của q.

329
00:17:17,030 --> 00:17:19,130
Chúng tôi muốn đi ra khỏi đầu, phải không?

330
00:17:19,130 --> 00:17:24,260
Vì vậy, kết quả là, người đứng đầu là sẽ thay đổi,
và đó là lý do tại sao khi bạn enqueue,

331
00:17:24,260 --> 00:17:26,800
bạn đã có để theo dõi
nơi đầu của bạn và kích thước của bạn

332
00:17:26,800 --> 00:17:29,450
là để có thể chèn
vào đúng vị trí.

333
00:17:29,450 --> 00:17:32,740
>> Và như vậy khi bạn dequeue,
Tôi cũng giả nó ra.

334
00:17:32,740 --> 00:17:35,480
Cảm thấy tự do để nếu bạn muốn
để cố gắng mã hóa này ra.

335
00:17:35,480 --> 00:17:36,980
Bạn muốn di chuyển đầu, phải không?

336
00:17:36,980 --> 00:17:39,320
Nếu tôi muốn dequeue, tôi
sẽ di chuyển đầu hơn.

337
00:17:39,320 --> 00:17:40,800
Điều này sẽ là người đứng đầu.

338
00:17:40,800 --> 00:17:45,617
>> Và kích thước hiện tại của chúng tôi sẽ
trừ bởi vì chúng tôi không còn

339
00:17:45,617 --> 00:17:46,950
có bốn yếu tố trong mảng.

340
00:17:46,950 --> 00:17:51,370
Chúng tôi chỉ có ba, và sau đó chúng tôi muốn
để trả lại bất cứ đã được lưu trữ bên trong

341
00:17:51,370 --> 00:17:56,260
của người đứng đầu bởi vì chúng tôi muốn đi này
giá trị ra như vậy rất giống với stack.

342
00:17:56,260 --> 00:17:58,010
Chỉ cần bạn đang dùng
từ một nơi khác,

343
00:17:58,010 --> 00:18:01,770
và bạn phải phân công lại con trỏ của bạn
đến nơi khác như một kết quả.

344
00:18:01,770 --> 00:18:03,890
Một cách hợp lý, tất cả mọi người làm theo?

345
00:18:03,890 --> 00:18:05,690
Thật tuyệt.

346
00:18:05,690 --> 00:18:10,156
>> OK, vì vậy chúng ta sẽ nói một chút
sâu hơn về danh sách liên kết

347
00:18:10,156 --> 00:18:13,280
vì họ sẽ được rất, rất có giá trị
cho bạn trong quá trình tuần này của

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Danh sách liên kết, như các bạn
có thể nhớ, tất cả họ là

350
00:18:17,130 --> 00:18:22,570
là các nút đó là nút của một số
giá trị của cả một giá trị và một con trỏ

351
00:18:22,570 --> 00:18:26,290
được liên kết với nhau
bởi những con trỏ.

352
00:18:26,290 --> 00:18:29,880
Và do đó, các cấu trúc trên như thế nào
chúng ta tạo ra một nút ở đây là chúng ta

353
00:18:29,880 --> 00:18:33,569
có int n, mà là bất cứ điều gì
các giá trị trong một cửa hàng hoặc chuỗi n

354
00:18:33,569 --> 00:18:35,610
hoặc bất cứ điều gì bạn muốn
gọi nó, char sao n.

355
00:18:35,610 --> 00:18:41,482
Struct sao nút, mà là con trỏ
mà bạn muốn có trong mỗi nút,

356
00:18:41,482 --> 00:18:43,690
bạn đang đi để có mà
điểm con trỏ về phía sau.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Bạn sẽ có người đứng đầu
của một danh sách liên kết đó

359
00:18:50,040 --> 00:18:53,140
sẽ trỏ đến các phần còn lại của
các giá trị vv và vv

360
00:18:53,140 --> 00:18:55,290
cho đến khi bạn cuối cùng đã đạt được kết thúc.

361
00:18:55,290 --> 00:18:58,040
Và nút cuối cùng này chỉ là
sẽ không có một con trỏ.

362
00:18:58,040 --> 00:18:59,952
Nó sẽ trỏ đến
null, và đó là khi

363
00:18:59,952 --> 00:19:01,910
Bạn có biết bạn đã nhấn
cuối danh sách liên kết của bạn

364
00:19:01,910 --> 00:19:04,076
là khi con trỏ cuối cùng của bạn
không trỏ đến bất cứ điều gì.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Vì vậy, chúng ta sẽ đi một chút trong
chiều sâu về cách người ta sẽ có thể

367
00:19:10,990 --> 00:19:12,400
tìm kiếm một danh sách liên kết.

368
00:19:12,400 --> 00:19:15,460
Ghi một số là gì
nhược điểm của danh sách liên kết

369
00:19:15,460 --> 00:19:19,340
các câu một mảng liên quan đến tìm kiếm.

370
00:19:19,340 --> 00:19:22,565
Một mảng, bạn có thể tìm kiếm nhị phân, nhưng
tại sao bạn không thể làm điều đó trong một danh sách liên kết?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> Đung Bởi vì tất cả chúng đều được kết nối,
nhưng bạn không biết chắc đâu

373
00:19:30,320 --> 00:19:31,330
[Không nghe thấy].

374
00:19:31,330 --> 00:19:34,600
>> Andi PENG: Yeah, chính xác như vậy nhớ
rằng sự sáng chói của một mảng

375
00:19:34,600 --> 00:19:37,190
đã được thực tế rằng chúng tôi đã có
bộ nhớ truy cập ngẫu nhiên mà

376
00:19:37,190 --> 00:19:41,580
nếu tôi muốn các giá trị từ chỉ số
sáu, tôi chỉ có thể nói chỉ số sáu,

377
00:19:41,580 --> 00:19:42,407
cho tôi giá trị đó.

378
00:19:42,407 --> 00:19:45,240
Và đó là bởi vì các mảng đều được sắp xếp
trong một không gian tiếp giáp của bộ nhớ

379
00:19:45,240 --> 00:19:48,020
ở một nơi, trong khi
loại danh sách liên kết

380
00:19:48,020 --> 00:19:52,820
là xen kẽ ngẫu nhiên tất cả xung quanh,
và cách duy nhất bạn có thể tìm thấy một

381
00:19:52,820 --> 00:19:56,890
là thông qua một con trỏ mà nói với bạn
địa chỉ nơi mà nút tiếp theo là.

382
00:19:56,890 --> 00:20:00,290
>> Và do đó, kết quả là, cách duy nhất
để tìm kiếm thông qua một danh sách liên kết

383
00:20:00,290 --> 00:20:01,560
là tìm kiếm tuyến tính.

384
00:20:01,560 --> 00:20:05,890
Bởi vì tôi không biết chính xác nơi
giá trị thứ 12 trong danh sách liên kết là,

385
00:20:05,890 --> 00:20:08,780
Tôi phải đi qua toàn bộ
trong đó một danh sách liên kết

386
00:20:08,780 --> 00:20:12,450
bởi một từ đầu đến nút đầu tiên,
đến nút thứ hai, đến nút thứ ba,

387
00:20:12,450 --> 00:20:17,690
tất cả các con đường xuống cho đến khi cuối cùng tôi nhận được
đến nơi mà nút Tôi đang tìm được.

388
00:20:17,690 --> 00:20:22,110
Và như vậy trong ý nghĩa này, tìm kiếm
vào một danh sách liên kết luôn luôn là n.

389
00:20:22,110 --> 00:20:23,040
Nó luôn luôn n.

390
00:20:23,040 --> 00:20:25,690
Nó luôn luôn trong thời gian tuyến tính.

391
00:20:25,690 --> 00:20:28,470
>> Và do đó, các mã trong đó
chúng tôi thực hiện điều này, và điều này

392
00:20:28,470 --> 00:20:32,620
là một chút mới cho các bạn kể từ khi bạn
kẻ đã không thực sự nói về hoặc bao giờ

393
00:20:32,620 --> 00:20:35,000
con trỏ thấy trong cách
tìm kiếm thông qua con trỏ,

394
00:20:35,000 --> 00:20:37,670
vì vậy chúng tôi sẽ đi bộ qua
này rất, rất chậm.

395
00:20:37,670 --> 00:20:40,200
Vì vậy, tìm kiếm bool, phải,
hãy tưởng tượng chúng ta muốn

396
00:20:40,200 --> 00:20:42,820
để tạo ra một chức năng gọi là
tìm kiếm trả về true

397
00:20:42,820 --> 00:20:46,820
nếu bạn tìm thấy một giá trị bên trong liên kết
danh sách, và nó trả về false.

398
00:20:46,820 --> 00:20:50,030
Danh sách sao Node là
hiện nay chỉ con trỏ

399
00:20:50,030 --> 00:20:52,960
đến mục đầu tiên trong danh sách liên kết của bạn.

400
00:20:52,960 --> 00:20:56,700
int n là giá trị mà bạn
tìm kiếm trong danh sách đó.

401
00:20:56,700 --> 00:20:58,770
>> Vì vậy, con trỏ sao nút bằng danh sách.

402
00:20:58,770 --> 00:21:00,970
Điều đó có nghĩa là chúng tôi đang thiết
và tạo ra một con trỏ

403
00:21:00,970 --> 00:21:03,592
gửi đến nút đầu tiên bên trong danh sách.

404
00:21:03,592 --> 00:21:04,300
Tất cả mọi người với tôi?

405
00:21:04,300 --> 00:21:06,530
Vì vậy, nếu chúng ta đi
trở lại đây, tôi sẽ có

406
00:21:06,530 --> 00:21:13,850
khởi tạo một con trỏ trỏ tới
người đứng đầu danh sách đó là bất cứ điều gì.

407
00:21:13,850 --> 00:21:18,600
>> Và sau đó một khi bạn nhận được xuống đây,
trong khi con trỏ không làm rỗng bằng nhau,

408
00:21:18,600 --> 00:21:22,160
vì vậy đó là các vòng lặp trong đó chúng tôi
sẽ là sau đó đi qua

409
00:21:22,160 --> 00:21:25,940
phần còn lại của danh sách của chúng tôi vì những gì
xảy ra khi con trỏ bằng null?

410
00:21:25,940 --> 00:21:27,550
Chúng tôi biết rằng chúng tôi have--

411
00:21:27,550 --> 00:21:28,450
>> Đung [Không nghe thấy]

412
00:21:28,450 --> 00:21:31,491
>> Andi PENG: Chính xác, vì vậy chúng tôi biết rằng
chúng tôi đã đạt đến cuối danh sách, phải không?

413
00:21:31,491 --> 00:21:34,470
Nếu bạn quay trở lại đây, mỗi nút
nên được trỏ đến một nút khác

414
00:21:34,470 --> 00:21:36,550
vv và vv
cho đến khi bạn nhấn cuối cùng

415
00:21:36,550 --> 00:21:41,589
đuôi của danh sách liên kết của bạn,
trong đó có một con trỏ chỉ

416
00:21:41,589 --> 00:21:43,130
không trỏ bất cứ nơi nào khác hơn là không có.

417
00:21:43,130 --> 00:21:47,510
Và do đó, về cơ bản bạn biết rằng
danh sách của bạn vẫn còn đó lên

418
00:21:47,510 --> 00:21:50,900
cho đến khi con trỏ không bằng
null bởi vì một khi nó bằng null,

419
00:21:50,900 --> 00:21:53,310
Bạn có biết rằng không có nhiều thứ hơn.

420
00:21:53,310 --> 00:21:56,930
>> Vì vậy, đó là các vòng lặp, trong đó chúng tôi
sẽ phải tìm kiếm thực tế.

421
00:21:56,930 --> 00:22:01,690
Và nếu pointer-- làm bạn thấy
là loại mũi tên chức năng đó?

422
00:22:01,690 --> 00:22:06,930
Vì vậy, nếu con trỏ trỏ đến n, nếu
con trỏ chuột tại n bằng bằng n,

423
00:22:06,930 --> 00:22:09,180
do đó có nghĩa rằng nếu
các con trỏ mà bạn

424
00:22:09,180 --> 00:22:13,420
tìm kiếm trên phần cuối của mỗi
nút là thực sự bằng giá trị

425
00:22:13,420 --> 00:22:15,990
bạn đang tìm kiếm, sau đó
bạn muốn trở thành sự thật.

426
00:22:15,990 --> 00:22:19,280
Vì vậy, về cơ bản, nếu bạn đang ở một nút đó
có giá trị mà bạn đang tìm kiếm,

427
00:22:19,280 --> 00:22:23,550
bạn biết rằng bạn đã
có thể tìm kiếm thành công.

428
00:22:23,550 --> 00:22:27,150
>> Nếu không, bạn muốn thiết lập
con trỏ của bạn đến nút tiếp theo.

429
00:22:27,150 --> 00:22:28,850
Đó là những gì mà dòng ở đây là làm.

430
00:22:28,850 --> 00:22:31,750
Pointer bằng con trỏ tới.

431
00:22:31,750 --> 00:22:33,360
Mọi người thấy thế nào mà làm việc?

432
00:22:33,360 --> 00:22:36,580
>> Và về cơ bản bạn đang đi để chỉ
đi qua toàn bộ danh sách,

433
00:22:36,580 --> 00:22:41,920
đặt con trỏ của bạn mỗi lần cho đến khi
Cuối cùng bạn nhấn vào cuối danh sách.

434
00:22:41,920 --> 00:22:45,030
Và bạn biết rằng không có
các nút hơn để tìm kiếm thông qua,

435
00:22:45,030 --> 00:22:47,999
và sau đó bạn có thể quay trở lại sai
bởi vì bạn biết rằng, oh, tốt,

436
00:22:47,999 --> 00:22:50,540
nếu tôi đã có thể tìm kiếm
thông qua toàn bộ danh sách.

437
00:22:50,540 --> 00:22:54,530
Nếu trong ví dụ này, nếu tôi muốn
để tìm kiếm các giá trị là 10,

438
00:22:54,530 --> 00:22:57,250
và tôi bắt đầu từ đầu, và
Tôi tìm kiếm tất cả các con đường xuống,

439
00:22:57,250 --> 00:23:00,550
và cuối cùng tôi đã đến đây, mà
một con trỏ trỏ đến null,

440
00:23:00,550 --> 00:23:04,415
Tôi biết rằng, crap, tôi đoán 10 không có trong
danh sách này bởi vì tôi không thể tìm thấy nó.

441
00:23:04,415 --> 00:23:06,520
Và tôi đang ở cuối danh sách.

442
00:23:06,520 --> 00:23:11,040
Và trong trường hợp bạn biết
Tôi sẽ trả về false.

443
00:23:11,040 --> 00:23:12,900
>> Hãy để đó ngâm trong một chút.

444
00:23:12,900 --> 00:23:17,350
Đây sẽ là khá
quan trọng cho pset của bạn.

445
00:23:17,350 --> 00:23:21,140
Logic của nó rất đơn giản, có lẽ
cú pháp chỉ thực hiện nó.

446
00:23:21,140 --> 00:23:23,365
Các bạn muốn làm
chắc chắn rằng bạn hiểu.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Mát.

449
00:23:27,650 --> 00:23:32,560
>> OK, vậy làm thế nào chúng tôi sẽ là
chèn các nút, phải,

450
00:23:32,560 --> 00:23:35,380
vào một danh sách vì nhớ
những gì là những gì trong những lợi ích

451
00:23:35,380 --> 00:23:39,230
của việc có một danh sách liên kết so với
một mảng về lưu trữ?

452
00:23:39,230 --> 00:23:41,110
>> Đung Đó là năng động,
vì vậy nó dễ dàng hơn đối với:

453
00:23:41,110 --> 00:23:43,180
>> Andi PENG: Chính xác,
do đó, nó là năng động,

454
00:23:43,180 --> 00:23:46,880
có nghĩa là nó có thể mở rộng và thu nhỏ
tùy thuộc vào nhu cầu của người dùng.

455
00:23:46,880 --> 00:23:56,570
Và như vậy, trong ý nghĩa này, chúng ta không cần
để lãng phí bộ nhớ không cần thiết bởi vì tôi

456
00:23:56,570 --> 00:24:00,850
nếu tôi không biết có bao nhiêu giá trị tôi muốn
để lưu trữ, nó không có ý nghĩa đối với tôi

457
00:24:00,850 --> 00:24:04,310
để tạo ra một mảng vì
nếu tôi muốn để lưu trữ 10 giá trị

458
00:24:04,310 --> 00:24:08,380
và tôi tạo ra một mảng của 1000, đó là
rất nhiều bộ nhớ bị lãng phí, quy định.

459
00:24:08,380 --> 00:24:11,180
Đó là lý do tại sao chúng tôi muốn sử dụng một liên kết
danh sách để có thể tự động

460
00:24:11,180 --> 00:24:13,860
thay đổi hoặc thu nhỏ kích thước của chúng tôi.

461
00:24:13,860 --> 00:24:17,040
>> Và vì vậy mà làm chèn
một chút phức tạp hơn.

462
00:24:17,040 --> 00:24:20,810
Kể từ khi chúng tôi không thể truy cập ngẫu nhiên các yếu tố
cách mà chúng tôi sẽ của một mảng.

463
00:24:20,810 --> 00:24:24,270
Nếu tôi muốn chèn một phần tử
vào các chỉ số thứ bảy,

464
00:24:24,270 --> 00:24:26,930
Tôi chỉ có thể chèn nó
vào các chỉ số thứ bảy.

465
00:24:26,930 --> 00:24:30,020
Trên một danh sách liên kết, nó không
khá làm việc như là một cách dễ dàng,

466
00:24:30,020 --> 00:24:34,947
và do đó, nếu chúng ta muốn chèn
cái ở đây, trong danh sách liên kết,

467
00:24:34,947 --> 00:24:36,280
trực quan, nó rất dễ dàng để xem.

468
00:24:36,280 --> 00:24:39,363
Chúng tôi chỉ muốn chèn nó ở ngay đó,
ngay từ đầu của danh sách,

469
00:24:39,363 --> 00:24:40,840
ngay sau khi người đứng đầu.

470
00:24:40,840 --> 00:24:44,579
>> Nhưng cách thức mà chúng ta phải phân công lại
các con trỏ là một chút phức tạp

471
00:24:44,579 --> 00:24:47,620
hay, hợp lý, nó có ý nghĩa, nhưng
bạn muốn chắc chắn rằng bạn có nó

472
00:24:47,620 --> 00:24:50,250
hoàn toàn xuống vì
điều cuối cùng bạn muốn

473
00:24:50,250 --> 00:24:52,990
là để gán một con trỏ
cách mà chúng tôi đang làm ở đây.

474
00:24:52,990 --> 00:24:58,170
Nếu bạn tới đích của các
con trỏ từ đầu đến 1,

475
00:24:58,170 --> 00:25:01,086
sau đó tất cả của một đột ngột
phần còn lại của danh sách liên kết của bạn

476
00:25:01,086 --> 00:25:04,680
bị mất bởi vì bạn đã không thực sự
tạo ra một điều gì tạm thời.

477
00:25:04,680 --> 00:25:06,220
Đó là chỉ vào 2.

478
00:25:06,220 --> 00:25:10,080
Nếu bạn gán lại con trỏ, sau đó các
phần còn lại của danh sách của bạn là hoàn toàn bị mất.

479
00:25:10,080 --> 00:25:13,310
Vì vậy, bạn muốn được
rất, rất cẩn thận ở đây

480
00:25:13,310 --> 00:25:17,010
đầu tiên gán
con trỏ từ bất cứ điều gì bạn

481
00:25:17,010 --> 00:25:20,150
muốn chèn vào bất cứ nơi nào
bạn muốn, và sau đó bạn

482
00:25:20,150 --> 00:25:22,710
có thể tới đích của phần còn lại của danh sách của bạn.

483
00:25:22,710 --> 00:25:25,250
>> Vì vậy, điều này áp dụng cho bất cứ nơi nào
bạn đang cố gắng để chèn vào.

484
00:25:25,250 --> 00:25:27,520
Nếu bạn muốn chèn vào
đầu, nếu bạn muốn trả lời ở đây,

485
00:25:27,520 --> 00:25:29,455
nếu bạn muốn chèn vào
Cuối cùng, cũng, kết thúc tôi

486
00:25:29,455 --> 00:25:30,910
đoán bạn sẽ chỉ
không có con trỏ, nhưng bạn

487
00:25:30,910 --> 00:25:33,830
muốn chắc chắn rằng bạn làm không
mất phần còn lại của danh sách của bạn.

488
00:25:33,830 --> 00:25:36,640
Bạn luôn muốn chắc chắn
nút mới của bạn được trỏ

489
00:25:36,640 --> 00:25:39,330
hướng tới bất cứ điều gì bạn
muốn chèn vào,

490
00:25:39,330 --> 00:25:42,170
và sau đó bạn có thể thêm các chuỗi trên.

491
00:25:42,170 --> 00:25:43,330
Mọi người đều rõ ràng?

492
00:25:43,330 --> 00:25:45,427
>> Điều này là có được
một trong những vấn đề thực tế.

493
00:25:45,427 --> 00:25:48,010
Một trong những vấn đề lớn nhất
bạn sẽ có trên pset của bạn

494
00:25:48,010 --> 00:25:51,340
là bạn sẽ cố gắng để tạo ra
một danh sách liên kết và những thứ chèn

495
00:25:51,340 --> 00:25:53,340
nhưng sau đó chỉ mất
phần còn lại của danh sách liên kết của bạn.

496
00:25:53,340 --> 00:25:54,900
Và bạn sẽ được như thế, tôi
không biết tại sao điều này xảy ra?

497
00:25:54,900 --> 00:25:58,040
Và đó là một nỗi đau để đi qua
và tìm kiếm tất cả các con trỏ của bạn.

498
00:25:58,040 --> 00:26:02,100
>> Và tôi đảm bảo với bạn về pset này,
viết và vẽ các nút này ra

499
00:26:02,100 --> 00:26:03,344
sẽ rất, rất hữu ích.

500
00:26:03,344 --> 00:26:06,010
Vì vậy, bạn hoàn toàn có thể theo dõi
của nơi mà tất cả các con trỏ của bạn,

501
00:26:06,010 --> 00:26:08,540
những gì đang xảy ra sai,
nơi mà tất cả các nút của bạn đang có,

502
00:26:08,540 --> 00:26:12,660
những gì bạn cần làm để truy cập hay
chèn hoặc xóa hoặc bất kỳ của họ.

503
00:26:12,660 --> 00:26:14,550
Mọi người đều tốt với điều đó?

504
00:26:14,550 --> 00:26:15,050
Mát.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Vì vậy, nếu chúng ta muốn nhìn vào mã?

507
00:26:22,600 --> 00:26:24,470
Oh, tôi không biết nếu chúng tôi
có thể thấy the-- OK, vì vậy

508
00:26:24,470 --> 00:26:27,940
ở đầu tất cả đó là là một chức năng
tên chèn nơi chúng tôi muốn

509
00:26:27,940 --> 00:26:31,365
để chèn int n vào danh sách liên kết.

510
00:26:31,365 --> 00:26:32,740
Chúng ta sẽ đi qua này.

511
00:26:32,740 --> 00:26:34,770
Đó là một rất nhiều mã, rất nhiều cú pháp mới.

512
00:26:34,770 --> 00:26:36,220
Chúng tôi sẽ OK.

513
00:26:36,220 --> 00:26:39,120
>> Vì vậy, ở đầu, bất cứ khi nào
chúng tôi muốn tạo ra bất cứ điều gì

514
00:26:39,120 --> 00:26:42,380
những gì chúng ta cần phải làm, đặc biệt là nếu bạn
muốn nó không được lưu trữ trên stack

515
00:26:42,380 --> 00:26:43,920
nhưng trong đống?

516
00:26:43,920 --> 00:26:45,460
Chúng tôi đi đến một malloc, phải không?

517
00:26:45,460 --> 00:26:48,240
Vì vậy, chúng ta sẽ tạo ra một con trỏ.

518
00:26:48,240 --> 00:26:52,074
Node, con trỏ, bình đẳng mới
malloc kích thước của một nút

519
00:26:52,074 --> 00:26:53,740
bởi vì chúng tôi muốn nút đó được tạo ra.

520
00:26:53,740 --> 00:26:56,720
Chúng tôi muốn lượng
nhớ rằng một nút chiếm

521
00:26:56,720 --> 00:26:59,300
được phân bổ cho các
tạo ra các nút mới.

522
00:26:59,300 --> 00:27:02,270
>> Và sau đó chúng ta sẽ kiểm tra
xem equals mới bằng null.

523
00:27:02,270 --> 00:27:03,370
Hãy nhớ những gì chúng tôi đã nói?

524
00:27:03,370 --> 00:27:06,470
Dù bạn malloc,
những gì bạn luôn phải làm gì?

525
00:27:06,470 --> 00:27:09,490
Bạn luôn luôn phải kiểm tra xem
có hay không mà là null.

526
00:27:09,490 --> 00:27:13,620
>> Ví dụ, nếu điều hành của bạn
hệ thống là hoàn toàn đầy đủ,

527
00:27:13,620 --> 00:27:17,060
nếu bạn có trí nhớ không có nhiều ở
tất cả và bạn cố gắng để malloc,

528
00:27:17,060 --> 00:27:18,410
nó sẽ trả về null cho bạn.

529
00:27:18,410 --> 00:27:21,094
Và do đó, nếu bạn cố gắng sử dụng nó
khi nó đã được trỏ đến null,

530
00:27:21,094 --> 00:27:23,260
bạn sẽ không thể
truy cập thông tin.

531
00:27:23,260 --> 00:27:27,010
Và như vậy, như vậy, chúng tôi muốn làm
chắc chắn rằng bất cứ khi nào bạn đang mallocing,

532
00:27:27,010 --> 00:27:30,500
bạn luôn kiểm tra để xem nếu
rằng bộ nhớ dành cho bạn là null.

533
00:27:30,500 --> 00:27:33,670
Và nếu nó không phải, sau đó chúng ta có thể di chuyển
trên với phần còn lại của mã của chúng tôi.

534
00:27:33,670 --> 00:27:36,140
>> Vì vậy, chúng ta sẽ
khởi tạo các nút mới.

535
00:27:36,140 --> 00:27:39,050
Chúng tôi đang đi làm n mới bằng n.

536
00:27:39,050 --> 00:27:42,390
Và sau đó, chúng tôi đang đi làm
thiết lập mới các con trỏ trên mới

537
00:27:42,390 --> 00:27:46,900
để null vì ngay bây giờ chúng ta làm không
muốn bất cứ điều gì cho nó để trỏ đến.

538
00:27:46,900 --> 00:27:48,755
Chúng tôi không có ý tưởng
nó sẽ đưa bạn,

539
00:27:48,755 --> 00:27:50,630
và sau đó nếu chúng ta muốn
chèn nó ở phần đầu,

540
00:27:50,630 --> 00:27:53,820
sau đó chúng ta có thể gán
con trỏ vào đầu.

541
00:27:53,820 --> 00:27:58,530
Có phải mọi người làm theo logic
nơi đang diễn ra?

542
00:27:58,530 --> 00:28:02,502
>> Tất cả chúng ta đang làm là tạo ra một mới
nút, đặt con trỏ đến null,

543
00:28:02,502 --> 00:28:04,210
và sau đó giao lại
nó cho người đứng đầu nếu chúng ta

544
00:28:04,210 --> 00:28:06,320
biết chúng ta muốn chèn nó ở phần đầu.

545
00:28:06,320 --> 00:28:09,420
Và sau đó người đứng đầu là có
chỉ hướng tới rằng nút mới.

546
00:28:09,420 --> 00:28:11,060
Mọi người đều OK với điều đó?

547
00:28:11,060 --> 00:28:12,380
>> Vì vậy, nó là một quá trình hai bước.

548
00:28:12,380 --> 00:28:14,760
Bạn đã có để gán đầu tiên
bất cứ điều gì bạn đang tạo.

549
00:28:14,760 --> 00:28:18,260
Đặt rằng con trỏ đến
tham khảo, và sau đó bạn

550
00:28:18,260 --> 00:28:21,400
có thể loại dereference
con trỏ đầu tiên

551
00:28:21,400 --> 00:28:22,972
và trỏ về phía nút mới.

552
00:28:22,972 --> 00:28:25,680
Bất cứ nơi nào bạn muốn chèn nó,
logic rằng sẽ giữ đúng.

553
00:28:25,680 --> 00:28:27,530
>> Nó giống như là gán
các biến tạm thời.

554
00:28:27,530 --> 00:28:28,700
Hãy nhớ rằng, bạn đã có
để đảm bảo rằng bạn

555
00:28:28,700 --> 00:28:30,346
không mất theo dõi nếu bạn đang trao đổi.

556
00:28:30,346 --> 00:28:33,470
Bạn muốn chắc chắn rằng bạn có một
biến tạm thời là loại giữ

557
00:28:33,470 --> 00:28:35,620
theo dõi các nơi điều mà
được lưu trữ để bạn

558
00:28:35,620 --> 00:28:41,190
không bị mất bất kỳ giá trị trong khóa học
giống như rối tung xung quanh với nó.

559
00:28:41,190 --> 00:28:42,710
>> OK, do đó, mã sẽ được ở đây.

560
00:28:42,710 --> 00:28:45,020
Các bạn hãy xem phần sau.

561
00:28:45,020 --> 00:28:48,060
Nó sẽ ở đó.

562
00:28:48,060 --> 00:28:50,280
>> Vì vậy, tôi đoán như thế nào
này khác nếu chúng ta muốn

563
00:28:50,280 --> 00:28:52,300
để chèn vào giữa hoặc cuối cùng?

564
00:28:52,300 --> 00:28:57,892
Có ai có một ý tưởng về những gì là
giả như là tài liệu tham khảo logic

565
00:28:57,892 --> 00:29:00,350
rằng chúng ta sẽ có được nếu chúng ta muốn
để chèn nó vào giữa?

566
00:29:00,350 --> 00:29:03,391
Vì vậy, nếu chúng ta muốn chèn nó ở
đầu, tất cả chúng tôi làm là tạo ra một nút mới.

567
00:29:03,391 --> 00:29:06,311
Chúng tôi đặt con trỏ đó
nút mới vào bất cứ điều gì vào đầu,

568
00:29:06,311 --> 00:29:08,310
và sau đó chúng tôi đặt đầu
đến nút mới, phải không?

569
00:29:08,310 --> 00:29:11,560
Nếu chúng ta muốn chèn nó ở giữa
của danh sách, những gì chúng ta sẽ phải làm gì?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Đung Nó vẫn sẽ
là một quá trình tương tự

572
00:29:16,110 --> 00:29:19,114
giống như gán con trỏ và
sau đó gán con trỏ đó,

573
00:29:19,114 --> 00:29:20,530
nhưng chúng ta sẽ phải xác định vị trí đó.

574
00:29:20,530 --> 00:29:23,560
>> Andi PENG: Chính xác, vì vậy chính xác
quá trình tương tự, ngoại trừ bạn

575
00:29:23,560 --> 00:29:27,820
phải xác định vị trí chính xác nơi bạn
muốn rằng con trỏ mới đi vào,

576
00:29:27,820 --> 00:29:44,790
vì vậy nếu tôi muốn chèn vào
giữa liên kết list-- OK,

577
00:29:44,790 --> 00:29:46,370
hãy nói rằng đó là danh sách liên kết của chúng tôi.

578
00:29:46,370 --> 00:29:49,500
Nếu chúng ta muốn chèn nó phải ở đây,
chúng ta sẽ tạo ra một nút mới.

579
00:29:49,500 --> 00:29:50,520
Chúng tôi đang đi để malloc.

580
00:29:50,520 --> 00:29:52,220
Chúng ta sẽ tạo ra một nút mới.

581
00:29:52,220 --> 00:29:55,940
Chúng tôi sẽ giao
con trỏ của nút này ở đây.

582
00:29:55,940 --> 00:29:58,335
>> Nhưng vấn đề đó khác
từ nơi mà người đứng đầu là

583
00:29:58,335 --> 00:30:00,490
là chúng ta biết chính xác
nơi người đứng đầu là.

584
00:30:00,490 --> 00:30:01,930
Đó là ngay ở lần đầu tiên, phải không?

585
00:30:01,930 --> 00:30:04,870
Nhưng ở đây chúng ta phải theo dõi
của nơi mà chúng ta đang chèn nó vào.

586
00:30:04,870 --> 00:30:07,930
Nếu chúng ta đang chèn chúng tôi
nút ở đây, chúng tôi đã có

587
00:30:07,930 --> 00:30:12,270
để đảm bảo rằng các
trước đó đến nút này

588
00:30:12,270 --> 00:30:14,172
là một trong đó reassigns con trỏ.

589
00:30:14,172 --> 00:30:16,380
Vì vậy, sau đó bạn phải loại
theo dõi trong hai điều.

590
00:30:16,380 --> 00:30:19,420
Nếu bạn theo dõi các nơi này
nút hiện được chèn vào.

591
00:30:19,420 --> 00:30:23,280
Bạn cũng cần phải theo dõi các nơi
nút trước đó mà bạn đang tìm kiếm

592
00:30:23,280 --> 00:30:24,340
cũng đã có.

593
00:30:24,340 --> 00:30:25,830
Mọi người đều tốt với điều đó?

594
00:30:25,830 --> 00:30:26,500
ĐƯỢC.

595
00:30:26,500 --> 00:30:28,000
>> Làm thế nào về cách chèn vào cuối?

596
00:30:28,000 --> 00:30:34,220
Nếu tôi muốn thêm nó here-- nếu tôi muốn
để thêm một nút mới vào cuối danh sách,

597
00:30:34,220 --> 00:30:37,009
làm thế nào tôi có thể đi về làm việc đó?

598
00:30:37,009 --> 00:30:39,300
Đung Vì vậy, hiện nay,
người cuối cùng đã chỉ để null.

599
00:30:39,300 --> 00:30:40,960
Andi PENG: Yeah.

600
00:30:40,960 --> 00:30:43,560
Chính xác, vì vậy một trong này
hiện là chỉ để biết,

601
00:30:43,560 --> 00:30:46,720
và vì vậy tôi đoán, trong ý nghĩa này, nó
rất dễ dàng để thêm vào cuối danh sách.

602
00:30:46,720 --> 00:30:51,810
Tất cả bạn phải làm là cài đặt nó
bằng null và sau đó bùng nổ.

603
00:30:51,810 --> 00:30:53,070
Ngay ở đó, rất dễ dàng.

604
00:30:53,070 --> 00:30:53,960
Rất đơn giản.

605
00:30:53,960 --> 00:30:56,430
>> Rất giống với
đầu, nhưng logic bạn

606
00:30:56,430 --> 00:30:59,690
muốn chắc chắn rằng các bước
bạn đưa về phía làm bất cứ điều này,

607
00:30:59,690 --> 00:31:01,500
bạn đang theo cùng.

608
00:31:01,500 --> 00:31:04,420
Nó rất dễ dàng để, ở giữa
code của bạn, nhận được đánh bắt lên trên,

609
00:31:04,420 --> 00:31:05,671
oh, tôi đã có rất nhiều con trỏ.

610
00:31:05,671 --> 00:31:07,461
Tôi không biết nơi
bất cứ điều gì được trỏ đến.

611
00:31:07,461 --> 00:31:09,170
Tôi thậm chí còn không biết mà nút tôi đang trên.

612
00:31:09,170 --> 00:31:11,490
Điều gì đang xảy ra?

613
00:31:11,490 --> 00:31:13,620
>> Hãy thư giãn, bình tĩnh lại, hít một hơi thật sâu.

614
00:31:13,620 --> 00:31:15,530
Vẽ ra danh sách liên kết của bạn.

615
00:31:15,530 --> 00:31:18,800
Nếu bạn nói, tôi biết chính xác nơi
Tôi cần phải chèn này vào

616
00:31:18,800 --> 00:31:22,970
và tôi biết chính xác làm thế nào để phân công lại của tôi
con trỏ, nhiều, dễ dàng hơn nhiều để ảnh

617
00:31:22,970 --> 00:31:27,200
out-- nhiều, dễ dàng hơn nhiều để không
bị lạc trong các lỗi của mã của bạn.

618
00:31:27,200 --> 00:31:29,410
Mọi người đều OK với điều đó?

619
00:31:29,410 --> 00:31:31,380
ĐƯỢC.

620
00:31:31,380 --> 00:31:35,120
>> Vì vậy, tôi đoán là một khái niệm mà chúng ta có không
thực sự đã nói trước bây giờ,

621
00:31:35,120 --> 00:31:38,131
và tôi đoán bạn có thể
sẽ không gặp phải nhiều yet--

622
00:31:38,131 --> 00:31:40,880
đó là loại một concept-- tiên tiến
là chúng ta thực sự có một dữ liệu

623
00:31:40,880 --> 00:31:43,900
cấu trúc được gọi là một danh sách gấp đôi được liên kết.

624
00:31:43,900 --> 00:31:46,390
Vì vậy, các bạn có thể thấy,
tất cả chúng ta đang làm là tạo

625
00:31:46,390 --> 00:31:50,400
một giá trị thực tế, một phụ
con trỏ trên mỗi nút của chúng tôi

626
00:31:50,400 --> 00:31:52,660
mà cũng chỉ đến nút trước đó.

627
00:31:52,660 --> 00:31:58,170
Vì vậy, chúng ta không chỉ có chúng tôi
nút điểm đến kế tiếp.

628
00:31:58,170 --> 00:32:01,430
Họ cũng chỉ ra trước đó.

629
00:32:01,430 --> 00:32:04,310
Tôi sẽ bỏ qua hai ngay bây giờ.

630
00:32:04,310 --> 00:32:06,740
>> Vì vậy, sau đó bạn có một chuỗi
có thể di chuyển cả hai cách,

631
00:32:06,740 --> 00:32:09,630
và sau đó nó là một chút dễ dàng hơn
để hợp lý theo cùng.

632
00:32:09,630 --> 00:32:11,896
Giống như ở đây, thay vì
việc theo dõi, oh, tôi

633
00:32:11,896 --> 00:32:14,520
phải biết rằng nút này là
một trong đó tôi phải phân công lại,

634
00:32:14,520 --> 00:32:17,532
Tôi chỉ có thể đến đây và
chỉ cần kéo trước.

635
00:32:17,532 --> 00:32:19,490
Sau đó, tôi biết chính xác nơi
đó là, và sau đó bạn

636
00:32:19,490 --> 00:32:21,130
không phải đi qua
toàn bộ các danh sách liên kết.

637
00:32:21,130 --> 00:32:22,180
Đó là một chút dễ dàng hơn.

638
00:32:22,180 --> 00:32:24,960
>> Nhưng như vậy, bạn có gấp đôi
số lượng con trỏ,

639
00:32:24,960 --> 00:32:26,960
đó là gấp đôi số lượng của bộ nhớ.

640
00:32:26,960 --> 00:32:28,950
Đó là rất nhiều của các con trỏ để theo dõi.

641
00:32:28,950 --> 00:32:32,140
Nó phức tạp hơn một chút, nhưng nó
hơn một chút thân thiện với người sử dụng tùy

642
00:32:32,140 --> 00:32:34,080
vào những gì bạn đang cố gắng để thực hiện.

643
00:32:34,080 --> 00:32:36,910
>> Vì vậy, loại dữ liệu
cấu trúc hoàn toàn tồn tại,

644
00:32:36,910 --> 00:32:40,280
và cấu trúc cho là rất, rất
đơn giản, ngoại trừ tất cả các bạn đang gặp là,

645
00:32:40,280 --> 00:32:43,850
thay vì chỉ là một con trỏ đến tiếp theo,
bạn cũng có một con trỏ đến trước.

646
00:32:43,850 --> 00:32:45,940
Đó là tất cả sự khác biệt.

647
00:32:45,940 --> 00:32:47,740
Mọi người đều tốt với điều đó?

648
00:32:47,740 --> 00:32:48,240
Mát.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Được rồi, vậy bây giờ tôi
để thực sự dành lẽ

651
00:32:53,280 --> 00:32:56,870
như 15-20 phút hoặc số lượng lớn
của phần còn lại của thời gian trong phần

652
00:32:56,870 --> 00:32:58,360
nói về bảng băm.

653
00:32:58,360 --> 00:33:02,590
Bao nhiêu người trong các bạn
đã đọc pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Được rồi, tốt.

655
00:33:03,620 --> 00:33:06,160
Đó là cao hơn so với 50% của bình thường.

656
00:33:06,160 --> 00:33:07,560
Đó là OK.

657
00:33:07,560 --> 00:33:10,345
>> Vì vậy, các bạn sẽ thấy,
bạn đang thách thức trong pset5

658
00:33:10,345 --> 00:33:16,790
sẽ được thực hiện một từ điển
nơi bạn nạp trên 140.000 lời

659
00:33:16,790 --> 00:33:20,610
mà chúng tôi cung cấp cho bạn và kiểm tra chính tả
nó chống lại tất cả các văn bản.

660
00:33:20,610 --> 00:33:22,580
Chúng tôi sẽ cung cấp cho bạn ngẫu nhiên
mảnh của văn học.

661
00:33:22,580 --> 00:33:23,520
Chúng tôi sẽ cung cấp cho bạn The Odyssey.

662
00:33:23,520 --> 00:33:24,561
Chúng tôi sẽ cung cấp cho bạn The Iliad.

663
00:33:24,561 --> 00:33:26,350
Chúng tôi sẽ cung cấp cho bạn Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Và thách thức của bạn
sẽ được kiểm tra chính tả

665
00:33:28,220 --> 00:33:31,760
mỗi từ duy nhất trong tất cả các
của những từ điển

666
00:33:31,760 --> 00:33:34,960
về cơ bản với kiểm tra chính tả của chúng tôi.

667
00:33:34,960 --> 00:33:38,620
Và do đó, có một vài bộ phận
tạo pset này,

668
00:33:38,620 --> 00:33:41,970
đầu tiên bạn muốn được
có thể thực sự tải

669
00:33:41,970 --> 00:33:43,970
tất cả các từ vào của bạn
từ điển, và sau đó bạn

670
00:33:43,970 --> 00:33:45,530
muốn để có thể
kiểm tra chính tả tất cả chúng.

671
00:33:45,530 --> 00:33:48,780
Và như vậy, như vậy, bạn sẽ cần
một cấu trúc dữ liệu có thể làm điều này nhanh

672
00:33:48,780 --> 00:33:50,790
và có hiệu quả và năng động.

673
00:33:50,790 --> 00:33:52,900
>> Vì vậy, tôi cho rằng đơn giản nhất
cách để làm điều này, bạn

674
00:33:52,900 --> 00:33:55,010
có lẽ sẽ tạo ra một mảng, phải không?

675
00:33:55,010 --> 00:33:58,910
Cách đơn giản nhất là bạn lưu trữ
có thể tạo ra một mảng của 140.000 lời

676
00:33:58,910 --> 00:34:03,400
và chỉ cần đặt tất cả chúng ở đó và
sau đó đi qua chúng bằng cách tìm kiếm nhị phân

677
00:34:03,400 --> 00:34:06,780
hoặc bằng cách chọn hoặc not--
xin lỗi đó là phân loại.

678
00:34:06,780 --> 00:34:10,729
Bạn có thể sắp xếp chúng và sau đó đi qua chúng
bằng cách tìm kiếm nhị phân hoặc tìm kiếm chỉ tuyến tính

679
00:34:10,729 --> 00:34:13,730
và chỉ thức lời nói, nhưng điều đó
mất một số tiền rất lớn của bộ nhớ,

680
00:34:13,730 --> 00:34:15,190
và nó không phải là rất hiệu quả.

681
00:34:15,190 --> 00:34:18,350
>> Và vì vậy chúng tôi đang đi để bắt đầu
nói về cách làm

682
00:34:18,350 --> 00:34:20,110
Hiện chúng tôi đang chạy hiệu quả hơn.

683
00:34:20,110 --> 00:34:23,190
Và mục tiêu của chúng tôi là để có được
hằng số thời gian nơi

684
00:34:23,190 --> 00:34:25,810
nó gần như mảng, nơi
bạn có thể truy cập tức thời.

685
00:34:25,810 --> 00:34:28,560
Nếu tôi muốn tìm kiếm bất cứ điều gì,
Tôi muốn để có thể chỉ,

686
00:34:28,560 --> 00:34:30,810
bùng nổ, tìm thấy nó một cách chính xác, và kéo nó ra.

687
00:34:30,810 --> 00:34:34,100
Và do đó, một cấu trúc trong đó
chúng tôi sẽ trở nên rất gần

688
00:34:34,100 --> 00:34:37,569
để có thể truy cập liên tục
thời gian, Chén thánh này

689
00:34:37,569 --> 00:34:41,370
trong lập trình không đổi
thời gian được gọi là một bảng băm.

690
00:34:41,370 --> 00:34:45,370
Và do đó, David đã đề cập trước đây
[Không nghe thấy] một chút trong bài giảng,

691
00:34:45,370 --> 00:34:49,100
nhưng chúng ta sẽ thực sự
lặn sâu trong tuần này

692
00:34:49,100 --> 00:34:51,780
trên một mảnh đó là liên quan đến
làm thế nào một bảng băm làm việc.

693
00:34:51,780 --> 00:34:53,949
>> Vì vậy, cách mà một hash
công trình bảng, ví dụ,

694
00:34:53,949 --> 00:35:00,230
nếu tôi muốn để lưu trữ một loạt các từ ngữ, một
bó của các từ trong ngôn ngữ tiếng Anh,

695
00:35:00,230 --> 00:35:02,940
Tôi về mặt lý thuyết có thể đặt
chuối, táo, kiwi, xoài, cặp,

696
00:35:02,940 --> 00:35:04,980
và dưa đỏ trên tất cả chỉ là một mảng.

697
00:35:04,980 --> 00:35:07,044
Tất cả họ có thể phù hợp và được tìm thấy.

698
00:35:07,044 --> 00:35:09,210
Nó muốn được loại đau đớn đến
tìm kiếm thông qua và truy cập,

699
00:35:09,210 --> 00:35:12,920
nhưng cách dễ dàng hơn để làm điều này là
rằng chúng ta có thể tạo ra một cấu trúc thực sự

700
00:35:12,920 --> 00:35:15,680
gọi là một bảng băm, nơi chúng tôi băm.

701
00:35:15,680 --> 00:35:19,880
Chúng tôi chạy tất cả các phím của chúng tôi thông qua
một hàm băm, một phương trình,

702
00:35:19,880 --> 00:35:22,600
có thể biến tất cả chúng thành
một số loại của một giá trị

703
00:35:22,600 --> 00:35:28,740
mà sau đó chúng ta có thể lưu trữ lên
bản chất là một mảng các danh sách liên kết.

704
00:35:28,740 --> 00:35:32,570
>> Và như vậy ở đây, nếu chúng ta muốn
để lưu trữ các từ tiếng Anh,

705
00:35:32,570 --> 00:35:37,250
chúng tôi có khả năng có chỉ là, tôi không
biết, biến tất cả các chữ cái đầu tiên

706
00:35:37,250 --> 00:35:39,630
vào một số loại của một số.

707
00:35:39,630 --> 00:35:43,140
Và như vậy, ví dụ, nếu tôi muốn
Một đồng nghĩa với apple--

708
00:35:43,140 --> 00:35:47,460
hoặc với chỉ số 0, và
B để được đồng nghĩa với 1,

709
00:35:47,460 --> 00:35:51,030
chúng ta có thể có 26 mục
mà chỉ có thể lưu trữ

710
00:35:51,030 --> 00:35:53,610
tất cả các chữ cái của
bảng chữ cái mà chúng ta sẽ bắt đầu với.

711
00:35:53,610 --> 00:35:56,130
Và sau đó chúng ta có thể có
táo ở các chỉ số từ 0.

712
00:35:56,130 --> 00:35:59,160
Chúng tôi có thể có chuối tại chỉ số
1, dưa đỏ tại các chỉ số của 2,

713
00:35:59,160 --> 00:36:00,540
và vv và vv.

714
00:36:00,540 --> 00:36:04,460
Và như vậy, nếu tôi muốn tìm kiếm
bảng và truy cập băm của tôi táo,

715
00:36:04,460 --> 00:36:07,560
Tôi biết táo bắt đầu với
A, và tôi biết chính xác

716
00:36:07,560 --> 00:36:10,860
rằng nó phải được và băm
bảng tại chỉ số 0 bởi vì

717
00:36:10,860 --> 00:36:13,620
các chức năng trước đây đã giao.

718
00:36:13,620 --> 00:36:16,572
>> Vì vậy, tôi không biết, chúng tôi là
một chương trình sử dụng nơi

719
00:36:16,572 --> 00:36:18,780
bạn sẽ được tính phí với
arbitrarily-- không tùy tiện,

720
00:36:18,780 --> 00:36:22,530
với cố gắng để chu đáo
nghĩ về phương trình tốt

721
00:36:22,530 --> 00:36:25,460
để có thể lây lan
ra tất cả các giá trị của bạn

722
00:36:25,460 --> 00:36:29,370
theo đó, họ có thể dễ dàng truy cập
nó sau này có như một phương trình

723
00:36:29,370 --> 00:36:31,130
mà bạn, mình, biết.

724
00:36:31,130 --> 00:36:35,210
Vì vậy, trong ý nghĩa nếu tôi muốn đi đến
xoài, tôi biết, oh, nó bắt đầu với m.

725
00:36:35,210 --> 00:36:37,134
Nó phải có các chỉ số của 12.

726
00:36:37,134 --> 00:36:38,800
Tôi không cần phải tìm kiếm thông qua bất cứ điều gì.

727
00:36:38,800 --> 00:36:42,080
Tôi biết exactly-- tôi chỉ có thể đi đến
các chỉ số của 12 và kéo ra ngoài.

728
00:36:42,080 --> 00:36:45,520
>> Mọi người đều rõ ràng về cách thức một
hàm bảng băm của công trình?

729
00:36:45,520 --> 00:36:48,380
Đó là loại chỉ là một mảng phức tạp hơn.

730
00:36:48,380 --> 00:36:50,010
Đó là tất cả nó là.

731
00:36:50,010 --> 00:36:51,630
ĐƯỢC.

732
00:36:51,630 --> 00:36:57,690
>> Vì vậy, tôi đoán chúng tôi chạy vào
vấn đề này của những gì

733
00:36:57,690 --> 00:37:06,390
sẽ xảy ra nếu bạn có nhiều điều
mà cung cấp cho bạn những chỉ số tương tự?

734
00:37:06,390 --> 00:37:10,570
Vì vậy, nói chức năng của chúng tôi, tất cả nó
đã làm là lấy lá thư đầu tiên

735
00:37:10,570 --> 00:37:14,490
và biến chúng thành một
tương ứng từ 0 đến 25 chỉ số.

736
00:37:14,490 --> 00:37:17,137
Điều đó hoàn toàn tốt nếu
bạn chỉ có một của mỗi.

737
00:37:17,137 --> 00:37:18,970
Nhưng lần thứ hai bạn bắt đầu
có hơn, bạn

738
00:37:18,970 --> 00:37:20,910
sẽ có những gì được gọi là một vụ va chạm.

739
00:37:20,910 --> 00:37:25,580
>> Vì vậy, nếu tôi cố gắng để chèn chôn vào một hash
bảng mà đã có chuối trên đó,

740
00:37:25,580 --> 00:37:27,870
những gì sẽ xảy ra khi
bạn cố gắng để chèn đó?

741
00:37:27,870 --> 00:37:30,930
Những điều xấu vì chuối
đã tồn tại trong các chỉ số

742
00:37:30,930 --> 00:37:33,800
mà bạn muốn lưu trữ nó trong.

743
00:37:33,800 --> 00:37:35,560
Berry loại là như thế, ah, tôi phải làm gì?

744
00:37:35,560 --> 00:37:37,080
Tôi không biết đi đâu.

745
00:37:37,080 --> 00:37:38,410
Làm thế nào để giải quyết này?

746
00:37:38,410 --> 00:37:41,150
>> Và như vậy các bạn sẽ loại
thấy chúng tôi làm điều này khó khăn

747
00:37:41,150 --> 00:37:44,810
nơi chúng ta có thể loại thực sự
tạo danh sách liên kết trong mảng của chúng tôi.

748
00:37:44,810 --> 00:37:46,840
Và do đó, cách đơn giản nhất
để suy nghĩ về điều này,

749
00:37:46,840 --> 00:37:50,830
tất cả các bảng băm là một
mảng các danh sách liên kết.

750
00:37:50,830 --> 00:37:55,670
Và như vậy, trong ý nghĩa đó, bạn có
mảng này đẹp của con trỏ,

751
00:37:55,670 --> 00:37:58,740
và sau đó mỗi con trỏ ở
giá trị đó, trong số đó,

752
00:37:58,740 --> 00:38:00,740
thực sự có thể trỏ đến những thứ khác.

753
00:38:00,740 --> 00:38:05,720
Và do đó, bạn có tất cả những riêng
chuỗi sắp tắt của một mảng lớn.

754
00:38:05,720 --> 00:38:07,960
>> Và như vậy ở đây, nếu tôi
muốn chèn berry,

755
00:38:07,960 --> 00:38:11,220
Tôi biết, OK, tôi sẽ đầu vào
nó thông qua hàm băm của tôi.

756
00:38:11,220 --> 00:38:15,070
Tôi sẽ kết thúc với chỉ số của
1, và sau đó tôi sẽ có thể có

757
00:38:15,070 --> 00:38:20,410
chỉ là một tập hợp con nhỏ hơn này
khổng lồ từ điển 140.000 từ.

758
00:38:20,410 --> 00:38:24,220
Và sau đó tôi chỉ có thể nhìn
qua 1/26 đó.

759
00:38:24,220 --> 00:38:27,910
>> Và như vậy thì tôi chỉ có thể chèn
berry trước hoặc sau khi chuối

760
00:38:27,910 --> 00:38:28,820
trong trường hợp này?

761
00:38:28,820 --> 00:38:29,700
Sau khi, phải không?

762
00:38:29,700 --> 00:38:33,920
Và do đó, bạn sẽ muốn
chèn nút này sau chuối,

763
00:38:33,920 --> 00:38:36,667
và như vậy bạn sẽ chèn
ở đuôi của mà danh sách liên kết.

764
00:38:36,667 --> 00:38:38,500
Tôi sẽ quay trở lại
đến slide trước đây,

765
00:38:38,500 --> 00:38:40,680
vậy các bạn có thể xem như thế nào
hàm băm làm việc.

766
00:38:40,680 --> 00:38:43,980
>> Vì vậy, hàm băm là phương trình này
rằng bạn đang chạy loại đầu vào của bạn

767
00:38:43,980 --> 00:38:46,940
thông qua để có được bất cứ điều gì chỉ số
bạn muốn gán cho nó hướng tới.

768
00:38:46,940 --> 00:38:51,130
Và như vậy, trong ví dụ này, tất cả chúng ta muốn
phải làm là lấy chữ cái đầu tiên,

769
00:38:51,130 --> 00:38:55,890
biến chúng thành một chỉ số, sau đó chúng tôi
có thể lưu trữ trong đó hàm băm của chúng tôi.

770
00:38:55,890 --> 00:39:00,160
Tất cả chúng tôi đang làm ở đây là chúng tôi
chuyển đổi các chữ cái đầu tiên.

771
00:39:00,160 --> 00:39:04,770
Vì vậy keykey [0] chỉ là chữ cái đầu tiên
của bất cứ chuỗi chúng ta đang gặp phải,

772
00:39:04,770 --> 00:39:05,720
chúng ta đang đi trong.

773
00:39:05,720 --> 00:39:09,740
Chúng tôi đang chuyển đổi đó để phía trên, và
chúng tôi đã trừ bằng chữ hoa A,

774
00:39:09,740 --> 00:39:11,740
vì vậy tất cả những gì đang làm
là đem lại cho chúng ta một số

775
00:39:11,740 --> 00:39:13,670
trong đó chúng ta có thể băm giá trị của mình lên.

776
00:39:13,670 --> 00:39:16,550
>> Và sau đó chúng ta sẽ
trở băm modulus SIZE.

777
00:39:16,550 --> 00:39:19,340
Hãy rất, rất cẩn thận
bởi vì, về mặt lý thuyết, đây

778
00:39:19,340 --> 00:39:21,870
giá trị băm của bạn có thể là vô hạn.

779
00:39:21,870 --> 00:39:23,660
Nó chỉ có thể đi trên và trên và trên.

780
00:39:23,660 --> 00:39:26,080
Nó có thể là một số thực sự,
thực sự có giá trị lớn,

781
00:39:26,080 --> 00:39:29,849
nhưng vì bảng băm của bạn
bạn đã tạo ra chỉ có 26 chỉ số,

782
00:39:29,849 --> 00:39:31,890
bạn muốn chắc chắn của bạn
modulusing để bạn

783
00:39:31,890 --> 00:39:33,848
không run-- đó là cùng
điều như queue-- của bạn

784
00:39:33,848 --> 00:39:36,320
do đó bạn không chạy ra khỏi
dưới cùng của hàm băm của bạn.

785
00:39:36,320 --> 00:39:39,210
>> Bạn muốn quấn nó lại xung quanh
cách tương tự trong [không nghe được] khi

786
00:39:39,210 --> 00:39:41,750
bạn có giống như một rất,
thư rất lớn, bạn

787
00:39:41,750 --> 00:39:43,740
không muốn điều đó
chỉ cần chạy ra cuối cùng.

788
00:39:43,740 --> 00:39:46,948
Cùng một điều ở đây, bạn muốn chắc chắn
nó không chạy ra khỏi cuối bởi gói

789
00:39:46,948 --> 00:39:48,330
xung quanh để đầu bảng.

790
00:39:48,330 --> 00:39:50,530
Vì vậy, đây chỉ là một rất
hàm băm đơn giản.

791
00:39:50,530 --> 00:39:56,570
Tất cả những gì đã làm là lấy đầu tiên
thư của bất cứ đầu vào của chúng tôi là

792
00:39:56,570 --> 00:40:01,660
và biến chúng thành một chỉ số
chúng ta có thể đưa vào bảng băm của chúng tôi.

793
00:40:01,660 --> 00:40:05,450
>> Yeah, và như vậy như tôi đã nói trước đây,
cách chúng ta giải quyết va chạm

794
00:40:05,450 --> 00:40:09,330
trong bảng băm của chúng tôi đang có,
những gì chúng ta gọi, dí.

795
00:40:09,330 --> 00:40:13,860
Vì vậy, nếu bạn cố gắng để chèn nhiều
từ bắt đầu với cùng một điều,

796
00:40:13,860 --> 00:40:16,145
bạn sẽ có một giá trị băm.

797
00:40:16,145 --> 00:40:18,770
Quả bơ táo, nếu bạn đã
chạy nó thông qua hàm băm của chúng tôi,

798
00:40:18,770 --> 00:40:21,450
sẽ cung cấp cho bạn những
cùng một số, số 0.

799
00:40:21,450 --> 00:40:24,550
Và do đó, cách giải quyết chúng tôi đó là
rằng chúng ta có thể thực sự loại liên kết chúng

800
00:40:24,550 --> 00:40:27,010
với nhau thông qua danh sách liên kết.

801
00:40:27,010 --> 00:40:29,600
>> Và như vậy trong ý nghĩa này,
các bạn có thể nhìn thấy loại

802
00:40:29,600 --> 00:40:32,640
về cách cấu trúc dữ liệu
chúng tôi đã được thiết lập trước đó

803
00:40:32,640 --> 00:40:35,870
như một nho danh sách liên kết loại
các thể đến với nhau thành một.

804
00:40:35,870 --> 00:40:38,860
Và sau đó bạn có thể tạo đến nay
cấu trúc dữ liệu hiệu quả hơn

805
00:40:38,860 --> 00:40:43,350
mà có thể xử lý một lượng lớn
dữ liệu, thay đổi kích thước tùy rằng động

806
00:40:43,350 --> 00:40:44,870
vào nhu cầu của bạn.

807
00:40:44,870 --> 00:40:45,620
Mọi người đều rõ ràng?

808
00:40:45,620 --> 00:40:47,580
Tất cả mọi người loại rõ ràng
về những gì xảy ra ở đây?

809
00:40:47,580 --> 00:40:52,110
>> Nếu tôi muốn insert-- gì một
trái cây bắt đầu với, tôi không biết,

810
00:40:52,110 --> 00:40:54,726
B, khác hơn so với quả mọng, chuối.

811
00:40:54,726 --> 00:40:55,710
>> Đung Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> Andi PENG: Blackberry, blackberry.

813
00:40:57,910 --> 00:41:00,530
Trường hợp nào blackberry đi đây?

814
00:41:00,530 --> 00:41:04,251
Vâng, chúng tôi thực sự đã không được sắp xếp
này chưa, nhưng về mặt lý thuyết

815
00:41:04,251 --> 00:41:06,250
nếu chúng ta muốn có này
theo thứ tự bảng chữ cái,

816
00:41:06,250 --> 00:41:07,944
nơi nên Blackberry đi?

817
00:41:07,944 --> 00:41:09,210
>> Đung [Không nghe thấy]

818
00:41:09,210 --> 00:41:11,100
>> Andi PENG: Chính xác, sau khi ở đây, phải không?

819
00:41:11,100 --> 00:41:14,950
Nhưng kể từ đó là rất khó
reorder-- Tôi đoán nó thuộc vào các bạn.

820
00:41:14,950 --> 00:41:17,920
Các bạn có thể hoàn toàn
thực hiện bất cứ điều gì bạn muốn.

821
00:41:17,920 --> 00:41:20,730
Cách hiệu quả hơn
để làm điều này có lẽ

822
00:41:20,730 --> 00:41:24,570
sẽ được sắp xếp liên kết của bạn
liệt kê vào thứ tự chữ cái,

823
00:41:24,570 --> 00:41:26,520
và vì vậy khi bạn đang
chèn vật, bạn muốn

824
00:41:26,520 --> 00:41:28,632
phải chắc chắn để chèn chúng
vào thứ tự chữ cái

825
00:41:28,632 --> 00:41:30,590
vì vậy mà sau đó khi bạn đang
cố gắng để tìm kiếm chúng,

826
00:41:30,590 --> 00:41:32,410
bạn không phải đi qua tất cả mọi thứ.

827
00:41:32,410 --> 00:41:35,290
Bạn biết chính xác nơi
nó là, và nó dễ dàng hơn.

828
00:41:35,290 --> 00:41:39,100
>> Nhưng nếu bạn có loại
điều xen kẽ một cách ngẫu nhiên,

829
00:41:39,100 --> 00:41:41,420
bạn vẫn sẽ có
để đi qua nó anyways.

830
00:41:41,420 --> 00:41:44,990
Và vì vậy nếu tôi muốn chỉ
chèn blackberry đây

831
00:41:44,990 --> 00:41:47,470
và tôi muốn tìm kiếm
nó, tôi biết, oh, blackberry

832
00:41:47,470 --> 00:41:52,012
phải bắt đầu với chỉ số 1, vì vậy tôi
biết ngay lập tức tìm kiếm chỉ ở mức 1.

833
00:41:52,012 --> 00:41:53,970
Và sau đó tôi có thể loại
đi qua các danh sách liên kết

834
00:41:53,970 --> 00:41:56,120
cho đến khi tôi nhận được để blackberry,
và then-- yeah?

835
00:41:56,120 --> 00:41:59,550
>> Đung Nếu bạn đang cố gắng để create--
Tôi đoán như thế này là một hash rất đơn giản

836
00:41:59,550 --> 00:42:00,050
chức năng.

837
00:42:00,050 --> 00:42:02,835
Và nếu chúng ta muốn làm
nhiều lớp như thế,

838
00:42:02,835 --> 00:42:05,870
OK, chúng tôi muốn tách riêng thành
giống như tất cả các chữ cái ABC

839
00:42:05,870 --> 00:42:09,040
và sau đó một lần nữa để thích bộ khác
các chữ cái chữ cái trong đó,

840
00:42:09,040 --> 00:42:11,715
được chúng tôi đặt như một hash
bảng trong một bảng băm,

841
00:42:11,715 --> 00:42:13,256
hoặc như một chức năng trong một chức năng?

842
00:42:13,256 --> 00:42:14,880
Hoặc là that--

843
00:42:14,880 --> 00:42:17,510
>> Andi PENG: Vì vậy, băm của bạn
function-- bảng băm của bạn

844
00:42:17,510 --> 00:42:19,360
có thể lớn như bạn muốn nó.

845
00:42:19,360 --> 00:42:21,930
Vì vậy, trong ý nghĩa này, tôi nghĩ
nó là rất dễ dàng, rất

846
00:42:21,930 --> 00:42:25,320
đơn giản cho tôi để dựa chỉ là loại
trên các chữ cái của từ đầu tiên.

847
00:42:25,320 --> 00:42:28,690
Và do đó, chỉ có 26 tùy chọn.

848
00:42:28,690 --> 00:42:32,650
Tôi chỉ có thể nhận được 26 lựa chọn từ
0-25 vì họ chỉ có thể

849
00:42:32,650 --> 00:42:36,510
bắt đầu từ A đến Z. Nhưng nếu bạn muốn
thêm, có lẽ, phức tạp hơn

850
00:42:36,510 --> 00:42:39,260
hoặc nhanh hơn chạy thời gian để bạn
bảng băm, bạn hoàn toàn

851
00:42:39,260 --> 00:42:40,760
có thể làm tất cả các loại vật.

852
00:42:40,760 --> 00:42:43,330
Bạn có thể làm cho riêng bạn
phương trình cung cấp cho bạn

853
00:42:43,330 --> 00:42:48,000
phân phối ở của bạn
từ, sau đó khi bạn tìm kiếm,

854
00:42:48,000 --> 00:42:49,300
nó sẽ được nhanh hơn.

855
00:42:49,300 --> 00:42:52,100
>> Đó là hoàn toàn vào bạn kẻ
làm thế nào bạn muốn thực hiện điều đó.

856
00:42:52,100 --> 00:42:55,140
Hãy nghĩ về nó như là chỉ xô.

857
00:42:55,140 --> 00:42:57,376
Nếu tôi muốn có
26 xô, tôi sẽ

858
00:42:57,376 --> 00:42:59,420
để sắp xếp mọi thứ vào những xô.

859
00:42:59,420 --> 00:43:02,980
Nhưng tôi sẽ có một bó
công cụ trong mỗi nhóm,

860
00:43:02,980 --> 00:43:05,890
vì vậy nếu bạn muốn làm cho nó
nhanh hơn và hiệu quả hơn,

861
00:43:05,890 --> 00:43:07,190
cho tôi có một trăm thùng.

862
00:43:07,190 --> 00:43:09,290
>> Nhưng sau đó bạn phải tìm ra một
cách để sắp xếp mọi thứ để họ có

863
00:43:09,290 --> 00:43:11,040
trong xô thích họ phải ở trong.

864
00:43:11,040 --> 00:43:13,331
Nhưng sau đó khi bạn thực sự
muốn nhìn vào thùng đó,

865
00:43:13,331 --> 00:43:16,410
nó nhanh hơn rất nhiều bởi vì có
ít công cụ trong mỗi nhóm.

866
00:43:16,410 --> 00:43:20,250
Và như vậy, yeah, đó là thực sự
các trick cho các bạn trong pset5

867
00:43:20,250 --> 00:43:22,360
là bạn sẽ được
thách thức để chỉ cần tạo

868
00:43:22,360 --> 00:43:26,170
bất cứ điều gì là hiệu quả nhất
chức năng mà bạn có thể nghĩ đến được

869
00:43:26,170 --> 00:43:28,520
có thể lưu trữ và kiểm tra các giá trị này.

870
00:43:28,520 --> 00:43:30,840
>> Hoàn toàn vào bạn kẻ
tuy nhiên bạn muốn làm điều đó,

871
00:43:30,840 --> 00:43:32,229
nhưng đó là một điểm thực sự tốt.

872
00:43:32,229 --> 00:43:34,520
Đó là loại logic bạn
muốn bắt đầu suy nghĩ về

873
00:43:34,520 --> 00:43:37,236
là, tốt, tại sao tôi không làm cho nhiều xô.

874
00:43:37,236 --> 00:43:39,527
Và sau đó tôi phải tìm kiếm
điều ít hơn, và sau đó có lẽ tôi

875
00:43:39,527 --> 00:43:41,640
có một hàm băm khác nhau.

876
00:43:41,640 --> 00:43:45,500
>> Vâng, có rất nhiều cách để làm điều này
pset, một số là nhanh hơn so với những người khác.

877
00:43:45,500 --> 00:43:50,630
Tôi hoàn toàn sẽ chỉ nhìn thấy như thế nào
nhanh là các bạn sẽ nhanh nhất

878
00:43:50,630 --> 00:43:55,170
có thể có được chức năng của bạn để làm việc.

879
00:43:55,170 --> 00:43:58,176
OK, tất cả mọi người trên tốt
chaining và băm bảng?

880
00:43:58,176 --> 00:44:00,800
Nó thực sự giống như một rất đơn giản
khái niệm, nếu bạn nghĩ về nó.

881
00:44:00,800 --> 00:44:05,160
Tất cả đó là là tách bất cứ điều gì
đầu vào của bạn là vào xô,

882
00:44:05,160 --> 00:44:10,670
phân loại chúng, và sau đó tìm kiếm các
liệt kê rằng có liên kết với.

883
00:44:10,670 --> 00:44:11,852
>> Mát.

884
00:44:11,852 --> 00:44:18,160
Được rồi, bây giờ chúng ta có một loại khác nhau
cấu trúc dữ liệu đó được gọi là một cây.

885
00:44:18,160 --> 00:44:20,850
Chúng ta hãy đi vào và nói về cố gắng
đó là khác biệt rõ rệt,

886
00:44:20,850 --> 00:44:22,330
nhưng trong cùng thể loại.

887
00:44:22,330 --> 00:44:29,010
Về cơ bản, tất cả các cây là thay vì
tổ chức dữ liệu theo cách tuyến tính

888
00:44:29,010 --> 00:44:32,560
rằng một bảng băm does-- bạn
biết, nó có một đỉnh và đáy

889
00:44:32,560 --> 00:44:37,900
và sau đó bạn loại liên kết tắt của một it--
cây có đầu mà bạn gọi là gốc,

890
00:44:37,900 --> 00:44:40,220
và sau đó nó có những chiếc lá tất cả xung quanh nó.

891
00:44:40,220 --> 00:44:42,390
>> Và vì vậy tất cả các bạn có ở đây
chỉ là nút trên cùng

892
00:44:42,390 --> 00:44:45,980
trỏ đến các nút khác, mà điểm
để các nút hơn, và vv và vv.

893
00:44:45,980 --> 00:44:48,130
Và vì vậy bạn chỉ có các chi nhánh tách.

894
00:44:48,130 --> 00:44:53,255
Nó chỉ là một cách khác nhau của tổ chức
dữ liệu, và vì chúng ta gọi nó là một cây,

895
00:44:53,255 --> 00:44:56,270
các bạn just-- nó chỉ
mô hình ra để trông giống như một cái cây.

896
00:44:56,270 --> 00:44:57,670
Đó là lý do tại sao chúng tôi gọi nó là cây.

897
00:44:57,670 --> 00:44:59,370
>> Bảng băm trông giống như một bảng.

898
00:44:59,370 --> 00:45:01,310
Một cây chỉ trông giống như một cái cây.

899
00:45:01,310 --> 00:45:03,300
Tất cả đó là là một riêng biệt
cách thức tổ chức các nút

900
00:45:03,300 --> 00:45:06,020
tùy thuộc vào nhu cầu của bạn.

901
00:45:06,020 --> 00:45:11,810
>> Vì vậy, bạn có một bộ rễ và
sau đó bạn có lá.

902
00:45:11,810 --> 00:45:15,380
Cách mà chúng ta có thể đặc biệt
nghĩ về nó là một cây nhị phân,

903
00:45:15,380 --> 00:45:18,150
một cây nhị phân chỉ là một
loại hình cụ thể của một cây

904
00:45:18,150 --> 00:45:22,450
trong đó mỗi nút chỉ điểm
để, lúc tối đa, hai nút khác.

905
00:45:22,450 --> 00:45:25,434
Và do đó, ở đây bạn có khác biệt
đối xứng trong cây của bạn

906
00:45:25,434 --> 00:45:28,600
mà làm cho nó dễ dàng hơn để loại tìm
tại những giá trị bạn là bởi vì sau đó bạn

907
00:45:28,600 --> 00:45:30,150
luôn luôn có một trái hoặc bên phải.

908
00:45:30,150 --> 00:45:33,150
Có bao giờ giống như một phần ba trái từ
bên trái hoặc thứ tư từ bên trái.

909
00:45:33,150 --> 00:45:36,358
Nó chỉ là bạn có một trái và một bên phải
và bạn có thể tìm kiếm một trong hai.

910
00:45:36,358 --> 00:45:38,980
Và như vậy tại sao điều này là hữu ích?

911
00:45:38,980 --> 00:45:40,980
Cách rằng đây là
là hữu ích nếu bạn đang tìm kiếm

912
00:45:40,980 --> 00:45:42,890
để tìm kiếm thông qua các giá trị, phải không?

913
00:45:42,890 --> 00:45:45,640
Thay vì thực hiện nhị phân
tìm kiếm trong một mảng lỗi,

914
00:45:45,640 --> 00:45:49,260
nếu bạn muốn để có thể chèn các nút
và lấy đi các nút theo ý thích và cũng

915
00:45:49,260 --> 00:45:52,185
bảo tồn các tìm kiếm
năng lực tìm kiếm nhị phân.

916
00:45:52,185 --> 00:45:54,560
Vì vậy, theo cách này, chúng ta đang loại
tricking-- nhớ khi chúng ta

917
00:45:54,560 --> 00:45:56,530
cho biết danh sách liên kết không thể tìm kiếm nhị phân?

918
00:45:56,530 --> 00:46:01,700
Chúng tôi đang tạo ra một loại cấu trúc dữ liệu
rằng thủ đoạn đó vào làm việc.

919
00:46:01,700 --> 00:46:05,034
>> Và danh sách như vậy bởi vì liên kết là tuyến tính,
họ chỉ có liên kết một sau khi khác.

920
00:46:05,034 --> 00:46:06,950
Chúng ta có thể có loại
loại khác nhau của các con trỏ

921
00:46:06,950 --> 00:46:09,408
điểm đó đến các nút khác nhau
có thể giúp chúng ta tìm kiếm.

922
00:46:09,408 --> 00:46:12,590
Và như vậy ở đây, nếu tôi muốn
có một cây tìm kiếm nhị phân,

923
00:46:12,590 --> 00:46:14,090
Tôi biết rằng giữa tôi nếu 55.

924
00:46:14,090 --> 00:46:18,280
Tôi chỉ cần đi để tạo ra rằng
như giữa của tôi, như là người chủ của tôi,

925
00:46:18,280 --> 00:46:20,770
và sau đó tôi sẽ có
giá trị spin off của nó.

926
00:46:20,770 --> 00:46:25,610
>> Vì vậy, ở đây, nếu tôi sẽ tìm kiếm
giá trị của 66, tôi có thể bắt đầu ở mức 55.

927
00:46:25,610 --> 00:46:27,310
Đó là 66 lớn hơn 55?

928
00:46:27,310 --> 00:46:30,970
Có nó, vì vậy tôi biết tôi Mus tìm kiếm
i n con trỏ bên phải của cây này.

929
00:46:30,970 --> 00:46:32,440
Tôi đi đến 77.

930
00:46:32,440 --> 00:46:35,367
OK, là 66 nhỏ hơn hoặc lớn hơn 77?

931
00:46:35,367 --> 00:46:37,950
Nó ít hơn, vì vậy bạn có biết, oh,
mà đã được các nút còn lại.

932
00:46:37,950 --> 00:46:41,410
>> Và vì vậy ở đây chúng ta đang loại bảo quản
tất cả những điều tuyệt vời về mảng,

933
00:46:41,410 --> 00:46:44,420
do đó, như thay đổi kích thước động
của các đối tượng, được

934
00:46:44,420 --> 00:46:49,530
có thể chèn và xóa theo ý muốn,
mà không cần phải lo lắng về sự cố định

935
00:46:49,530 --> 00:46:50,370
số lượng không gian.

936
00:46:50,370 --> 00:46:52,820
Chúng tôi vẫn còn lưu giữ tất cả
những điều tuyệt vời

937
00:46:52,820 --> 00:46:57,140
đồng thời có thể để bảo tồn
đăng nhập và thời gian tìm kiếm nhị phân tìm kiếm

938
00:46:57,140 --> 00:47:00,450
rằng chúng tôi chỉ là trước đây
có thể có được một cụm từ.

939
00:47:00,450 --> 00:47:06,310
>> Cấu trúc dữ liệu thoáng mát, loại
phức tạp để thực hiện, các node.

940
00:47:06,310 --> 00:47:08,311
Như bạn có thể thấy, tất cả nó
là cấu trúc của nút

941
00:47:08,311 --> 00:47:10,143
là bạn có một trái
và một con trỏ bên phải.

942
00:47:10,143 --> 00:47:11,044
Đó là tất cả nó là.

943
00:47:11,044 --> 00:47:12,960
Vì vậy, thay vì chỉ
có một x hoặc trước đó.

944
00:47:12,960 --> 00:47:15,920
Bạn có một trái hoặc bên phải, và sau đó
bạn có thể loại liên kết chúng lại với nhau

945
00:47:15,920 --> 00:47:16,836
Tuy nhiên bạn nên chọn.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, chúng tôi đang thực sự đi
chỉ mất một vài phút.

948
00:47:24,270 --> 00:47:25,790
Vì vậy, chúng ta sẽ quay trở lại đây.

949
00:47:25,790 --> 00:47:28,270
Như tôi đã nói trước đây,
Tôi loại giải thích

950
00:47:28,270 --> 00:47:31,520
logic đằng sau như thế nào chúng tôi
sẽ tìm kiếm thông qua này.

951
00:47:31,520 --> 00:47:33,860
Chúng ta sẽ cố gắng
pseudocoding ra điều này để thấy

952
00:47:33,860 --> 00:47:38,000
nếu chúng ta loại có thể áp dụng
cùng một logic của tìm kiếm nhị phân

953
00:47:38,000 --> 00:47:40,055
để một kiểu khác nhau của cấu trúc dữ liệu.

954
00:47:40,055 --> 00:47:45,049
Nếu các bạn muốn đi như một cặp vợ chồng
phút để nghĩ đến điều này.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
ĐƯỢC.

957
00:48:46,925 --> 00:48:51,407
Được rồi, tôi sẽ
thực sự chỉ cần cung cấp cho bạn the-- không,

958
00:48:51,407 --> 00:48:52,990
chúng ta sẽ nói về các giả đầu tiên.

959
00:48:52,990 --> 00:48:56,580
Vì vậy, không ai muốn
để cung cấp cho một đâm vào những gì

960
00:48:56,580 --> 00:49:02,100
điều đầu tiên bạn muốn làm khi
bạn đang bắt đầu tìm kiếm là gì?

961
00:49:02,100 --> 00:49:04,460
Nếu chúng tôi đang tìm kiếm
giá trị của 66, có chuyện gì

962
00:49:04,460 --> 00:49:07,940
điều đầu tiên chúng tôi muốn làm nếu
chúng ta muốn thành dạng nhị phân tìm kiếm cây này?

963
00:49:07,940 --> 00:49:10,760
>> Đung Bạn muốn nhìn bên phải
và tìm kiếm bên trái và xem [không nghe]

964
00:49:10,760 --> 00:49:11,230
số lượng lớn hơn.

965
00:49:11,230 --> 00:49:12,271
>> Andi PENG: Yeah, chính xác.

966
00:49:12,271 --> 00:49:15,350
Vì vậy, bạn sẽ nhìn vào gốc của bạn.

967
00:49:15,350 --> 00:49:18,180
Có rất nhiều cách để bạn có thể gọi
nó, nút cha của người nói.

968
00:49:18,180 --> 00:49:21,317
Tôi muốn nói root bởi
đó là giống như gốc rễ của cây.

969
00:49:21,317 --> 00:49:23,400
Bạn sẽ nhìn vào
nút gốc của bạn, và bạn

970
00:49:23,400 --> 00:49:26,940
sẽ gặp là 66 lớn hơn
hơn hoặc ít hơn 55.

971
00:49:26,940 --> 00:49:30,360
Và nếu nó lớn hơn, tốt, nó là
lớn hơn, nơi nào chúng ta muốn nhìn?

972
00:49:30,360 --> 00:49:32,000
Nơi nào chúng ta muốn tìm kiếm bây giờ, phải không?

973
00:49:32,000 --> 00:49:34,340
Chúng tôi muốn tìm kiếm
nửa bên phải của cây này.

974
00:49:34,340 --> 00:49:38,390
>> Vì vậy, chúng ta có, thuận tiện, một
con trỏ trỏ bên phải.

975
00:49:38,390 --> 00:49:44,325
Và như vậy thì chúng ta có thể thiết lập
gốc mới của chúng tôi là 77.

976
00:49:44,325 --> 00:49:46,450
Chúng tôi chỉ có thể đi đến bất cứ nơi
con trỏ trỏ đến.

977
00:49:46,450 --> 00:49:49,100
Vâng, oh, ở đây chúng tôi đang bắt đầu
77, và chúng ta có thể chỉ

978
00:49:49,100 --> 00:49:51,172
làm điều này một cách đệ quy một lần nữa và một lần nữa.

979
00:49:51,172 --> 00:49:52,880
Bằng cách này, bạn loại
của có một chức năng.

980
00:49:52,880 --> 00:49:57,430
Bạn có một cách tìm kiếm mà bạn
chỉ có thể lặp lại hơn và hơn và hơn,

981
00:49:57,430 --> 00:50:02,720
tùy thuộc vào nơi bạn muốn tìm
cho đến khi bạn cuối cùng có được với giá trị

982
00:50:02,720 --> 00:50:04,730
mà bạn đang tìm kiếm.

983
00:50:04,730 --> 00:50:05,230
Có lý?

984
00:50:05,230 --> 00:50:07,800
>> Tôi về để cho bạn thấy thực tế
mã, và nó rất nhiều mã.

985
00:50:07,800 --> 00:50:08,674
Không cần phải lăn tăn.

986
00:50:08,674 --> 00:50:09,910
Chúng tôi sẽ nói chuyện qua nó.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Thực ra là không.

989
00:50:14,020 --> 00:50:15,061
Đó chỉ là giả.

990
00:50:15,061 --> 00:50:17,860
OK, đó mới chỉ là giả,
đó là một chút phức tạp,

991
00:50:17,860 --> 00:50:19,751
nhưng nó hoàn toàn tốt.

992
00:50:19,751 --> 00:50:21,000
Tất cả mọi người sau cùng ở đây?

993
00:50:21,000 --> 00:50:24,260
Nếu rễ là null, trở lại
sai bởi vì điều đó có nghĩa

994
00:50:24,260 --> 00:50:26,850
bạn thậm chí không có bất cứ điều gì ở đó.

995
00:50:26,850 --> 00:50:31,376
>> Nếu gốc n là giá trị, vì vậy nếu nó
sẽ xảy ra là một trong những bạn đang xem,

996
00:50:31,376 --> 00:50:34,000
sau đó bạn đang đi để trở về đúng
vì bạn biết bạn tìm thấy nó.

997
00:50:34,000 --> 00:50:36,250
Nhưng nếu giá trị nhỏ
hơn gốc của n, bạn

998
00:50:36,250 --> 00:50:38,332
sẽ tìm kiếm bên trái
trẻ em hoặc các lá trái,

999
00:50:38,332 --> 00:50:39,540
bất cứ điều gì bạn muốn gọi nó.

1000
00:50:39,540 --> 00:50:41,750
Và nếu giá trị lớn hơn gốc,
bạn đang đi để tìm kiếm cây bên phải,

1001
00:50:41,750 --> 00:50:44,610
sau đó chỉ cần chạy chức năng
thông qua tìm kiếm một lần nữa.

1002
00:50:44,610 --> 00:50:48,037
>> Và nếu rễ là null, mà đó
có nghĩa là bạn đã đạt đến kết thúc?

1003
00:50:48,037 --> 00:50:50,120
Điều đó có nghĩa là bạn không có
nhiều lá cây hơn để tìm kiếm,

1004
00:50:50,120 --> 00:50:52,230
sau đó bạn biết, oh, tôi
đoán nó không phải ở đây

1005
00:50:52,230 --> 00:50:55,063
bởi vì sau khi tôi đã nhìn qua
toàn bộ và không phải ở đây,

1006
00:50:55,063 --> 00:50:56,930
nó chỉ có thể không có mặt ở đây.

1007
00:50:56,930 --> 00:50:58,350
>> Điều đó có ý nghĩa với tất cả mọi người?

1008
00:50:58,350 --> 00:51:03,230
Vì vậy, nó giống như tìm kiếm nhị phân bảo quản
khả năng của danh sách liên kết.

1009
00:51:03,230 --> 00:51:09,200
Cool, và do đó loại thứ hai
cấu trúc dữ liệu các bạn

1010
00:51:09,200 --> 00:51:13,180
có thể cố gắng thực hiện trên pset của bạn,
bạn chỉ cần chọn một phương pháp.

1011
00:51:13,180 --> 00:51:19,430
Nhưng có lẽ một phương pháp khác để
bảng băm là những gì chúng ta gọi là một Trie.

1012
00:51:19,430 --> 00:51:24,080
>> Tất cả là một Trie là một
loại hình cụ thể của cây

1013
00:51:24,080 --> 00:51:28,600
có giá trị đó đi đến các giá trị khác.

1014
00:51:28,600 --> 00:51:31,450
Vì vậy, thay vì có một nhị phân
cây trong ý nghĩa rằng chỉ có một

1015
00:51:31,450 --> 00:51:35,940
điều có thể trỏ đến hai, bạn có thể có
điểm một điều để nhiều, nhiều điều.

1016
00:51:35,940 --> 00:51:39,450
Bạn có thực chất có mảng
bên trong mà bạn lưu trữ

1017
00:51:39,450 --> 00:51:41,790
con trỏ trỏ tới các mảng khác.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Vì vậy, các nút của chúng tôi như thế nào
sẽ xác định một Trie

1020
00:51:49,460 --> 00:51:52,590
là chúng ta muốn có một
Boolean, c từ, phải không?

1021
00:51:52,590 --> 00:51:54,920
Vì vậy, các nút là Boolean
như đúng hay sai,

1022
00:51:54,920 --> 00:51:58,490
trước hết ở đầu
mảng đó, đây là một từ?

1023
00:51:58,490 --> 00:52:03,620
Thứ hai, bạn muốn để có con trỏ
để bất cứ điều gì với phần còn lại của họ đang có.

1024
00:52:03,620 --> 00:52:07,470
Một chút phức tạp, một trừu tượng chút, nhưng
Tôi sẽ giải thích những gì mà tất cả các phương tiện.

1025
00:52:07,470 --> 00:52:13,800
>> Vì vậy, ở đây, ở phía trên, nếu bạn
có một mảng được khai báo đã có,

1026
00:52:13,800 --> 00:52:17,040
một nút mà bạn có một Boolean
giá trị được lưu trữ ở phía trước

1027
00:52:17,040 --> 00:52:19,490
mà nói với bạn là một từ này?

1028
00:52:19,490 --> 00:52:20,520
Này không phải là một từ?

1029
00:52:20,520 --> 00:52:23,240
Và sau đó bạn có
phần còn lại của mảng của bạn mà

1030
00:52:23,240 --> 00:52:26,040
thực sự lưu trữ tất cả các
khả năng của những gì nó có thể được.

1031
00:52:26,040 --> 00:52:28,660
Vì vậy, ví dụ, như
ở đầu trang bạn có

1032
00:52:28,660 --> 00:52:32,140
điều đầu tiên mà nói đúng hay
sai, có hay không, đây là một từ.

1033
00:52:32,140 --> 00:52:38,130
>> Và sau đó bạn có 0 đến 26 của
các chữ cái mà bạn có thể lưu trữ.

1034
00:52:38,130 --> 00:52:42,790
Nếu tôi muốn tìm kiếm ở đây
cho bat, tôi đi đến hàng đầu

1035
00:52:42,790 --> 00:52:49,200
và tôi tìm kiếm B. Tôi tìm B trong tôi
mảng, và vì vậy tôi biết, OK, là B một từ?

1036
00:52:49,200 --> 00:52:53,010
B không phải là một từ, do đó do đó
Tôi phải tiếp tục tìm kiếm.

1037
00:52:53,010 --> 00:52:56,410
Tôi đi từ B, và tôi nhìn vào
con trỏ mà B chỉ ra được sự

1038
00:52:56,410 --> 00:53:00,900
và tôi thấy một mảng của các thông tin,
cấu trúc tương tự mà chúng ta có trước.

1039
00:53:00,900 --> 00:53:05,240
>> Và here-- oh, tiếp theo
thư trong [không nghe được] là A.

1040
00:53:05,240 --> 00:53:07,210
Vì vậy, chúng ta nhìn vào mảng đó.

1041
00:53:07,210 --> 00:53:10,860
Chúng tôi tìm thấy những giá trị thứ tám,
và sau đó chúng ta nhìn thấy, oh,

1042
00:53:10,860 --> 00:53:12,840
hey, đó là một từ, là B-A là một từ?

1043
00:53:12,840 --> 00:53:13,807
Nó không phải là một từ.

1044
00:53:13,807 --> 00:53:14,890
Chúng ta phải tiếp tục tìm kiếm.

1045
00:53:14,890 --> 00:53:17,850
>> Và như vậy thì chúng ta nhìn đến nơi
con trỏ của A điểm,

1046
00:53:17,850 --> 00:53:21,130
và nó chỉ đến một cách khác trong
mà chúng tôi có giá trị lưu trữ nhiều.

1047
00:53:21,130 --> 00:53:24,150
Và cuối cùng, chúng tôi nhận được
B-A-T, đó là một từ.

1048
00:53:24,150 --> 00:53:25,970
Và vì vậy thời gian tiếp theo
bạn nhìn, bạn sẽ

1049
00:53:25,970 --> 00:53:30,850
để có mà kiểm tra, và vâng,
hàm Boolean điều này là đúng.

1050
00:53:30,850 --> 00:53:35,450
Và như vậy trong ý nghĩa chúng ta đang loại
của việc có một cây với mảng.

1051
00:53:35,450 --> 00:53:39,890
>> Vì vậy, sau đó bạn có thể loại tìm kiếm xuống.

1052
00:53:39,890 --> 00:53:43,650
Thay vì băm một chức năng và
gán giá trị của danh sách liên kết,

1053
00:53:43,650 --> 00:53:49,190
bạn chỉ có thể thực hiện một
Trie để tìm kiếm downwords.

1054
00:53:49,190 --> 00:53:50,850
Thực sự, thực sự phức tạp thứ.

1055
00:53:50,850 --> 00:53:54,060
Không dễ dàng để nghĩ về vì tôi giống
nhổ nước bọt rất nhiều cấu trúc dữ liệu ra

1056
00:53:54,060 --> 00:53:58,710
vào bạn, nhưng tất cả mọi người không loại
hiểu logic của các công trình này?

1057
00:53:58,710 --> 00:54:01,920
>> OK, mát mẻ.

1058
00:54:01,920 --> 00:54:05,600
Vì vậy, B-A-T, và sau đó
bạn đang đi để tìm kiếm.

1059
00:54:05,600 --> 00:54:07,940
Lần sau, bạn sẽ
để xem, oh, hey, đó là sự thật,

1060
00:54:07,940 --> 00:54:09,273
vì thế tôi biết điều này phải là một từ.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Cùng một điều cho sở thú.

1063
00:54:13,770 --> 00:54:17,960
Vì vậy, đây là điều ngay bây giờ, nếu chúng ta
muốn tìm kiếm các vườn thú, ngay bây giờ,

1064
00:54:17,960 --> 00:54:20,780
Hiện tại vườn thú không phải là một
từ trong từ điển của chúng tôi

1065
00:54:20,780 --> 00:54:25,300
bởi vì, như các bạn có thể thấy,
nơi đầu tiên mà chúng ta có một Boolean

1066
00:54:25,300 --> 00:54:28,590
trở về đúng là vào cuối zoom.

1067
00:54:28,590 --> 00:54:30,430
Chúng tôi có Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Và như vậy ở đây, chúng ta không thực sự có
từ, sở thú, trong từ điển của chúng tôi

1069
00:54:33,900 --> 00:54:36,070
vì hộp kiểm này không được chọn.

1070
00:54:36,070 --> 00:54:39,540
Vì vậy, các máy tính không
biết rằng sở thú là một từ

1071
00:54:39,540 --> 00:54:42,430
vì cách làm đó, chúng tôi đã
được lưu giữ nó, chỉ có một zoom đây

1072
00:54:42,430 --> 00:54:44,920
thực sự có một giá trị Boolean
đó là được trở thành sự thật.

1073
00:54:44,920 --> 00:54:49,380
Vì vậy, nếu chúng ta muốn chèn
từ, sở thú, vào trong từ điển của chúng tôi,

1074
00:54:49,380 --> 00:54:51,770
làm thế nào chúng ta sẽ đi về làm việc đó?

1075
00:54:51,770 --> 00:54:55,960
Những gì chúng ta phải làm gì để đảm bảo chúng tôi
Máy tính sẽ biết rằng Z-O-O là một từ

1076
00:54:55,960 --> 00:54:58,130
và không phải là từ đầu tiên là Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> Đung [Không nghe thấy]

1078
00:54:59,360 --> 00:55:01,450
>> Andi PENG: Chính xác, chúng tôi
muốn chắc chắn rằng điều này

1079
00:55:01,450 --> 00:55:07,890
ở đây, đó là giá trị Boolean
kiểm tra ra rằng đó là sự thật.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, sau đó chúng ta sẽ kiểm tra xem,
vì vậy chúng tôi biết chính xác, hey, vườn thú là một từ.

1081
00:55:13,297 --> 00:55:15,380
Tôi sẽ nói với các
máy tính mà nó là một từ quá

1082
00:55:15,380 --> 00:55:18,000
rằng khi kiểm tra máy tính,
nó biết rằng sở thú là một từ.

1083
00:55:18,000 --> 00:55:21,269
>> Bởi vì nhớ tất cả những dữ liệu này
cấu trúc, nó rất dễ dàng cho chúng tôi

1084
00:55:21,269 --> 00:55:22,310
để nói, oh, bat là một từ.

1085
00:55:22,310 --> 00:55:22,851
Zoo là một từ.

1086
00:55:22,851 --> 00:55:23,611
Zoom là một từ.

1087
00:55:23,611 --> 00:55:25,860
Nhưng khi bạn đang xây dựng nó,
máy tính không có ý tưởng.

1088
00:55:25,860 --> 00:55:28,619
>> Vì vậy, bạn phải nói cho nó chính xác
ở điểm nào đây là một từ?

1089
00:55:28,619 --> 00:55:29,910
Tại thời điểm nào là nó không phải là một từ?

1090
00:55:29,910 --> 00:55:31,784
Và vào thời điểm những gì làm tôi
cần phải tìm kiếm những điều,

1091
00:55:31,784 --> 00:55:34,000
và vào thời điểm những gì tôi cần để đi tiếp theo?

1092
00:55:34,000 --> 00:55:37,010
Mọi người đều rõ ràng về điều đó?

1093
00:55:37,010 --> 00:55:39,540
Mát.

1094
00:55:39,540 --> 00:55:42,530
>> Và do đó, sau đó đến các
Vấn đề làm sao chúng tôi sẽ

1095
00:55:42,530 --> 00:55:45,560
đi về chèn một cái gì đó
đó là thực sự không có?

1096
00:55:45,560 --> 00:55:49,090
Vì vậy, chúng ta hãy chỉ nói rằng chúng ta muốn chèn
từ, phòng tắm, vào Trie của chúng tôi.

1097
00:55:49,090 --> 00:55:53,589
Như các bạn có thể nhìn thấy như hiện nay
tất cả chúng ta có bây giờ là B-A-T,

1098
00:55:53,589 --> 00:55:55,630
và cấu trúc dữ liệu mới này
có có một pint đó

1099
00:55:55,630 --> 00:55:59,740
chỉ để null vì chúng ta giả định
rằng, oh, không có lời nói sau B-A-T,

1100
00:55:59,740 --> 00:56:02,530
tại sao chúng ta cần phải giữ
có những thứ sau đó T.

1101
00:56:02,530 --> 00:56:06,581
>> Nhưng vấn đề phát sinh nếu chúng ta làm bạn
muốn có một lời nói ra sau

1102
00:56:06,581 --> 00:56:07,080
các T.

1103
00:56:07,080 --> 00:56:09,500
Nếu bạn có bồn tắm, bạn đang
sẽ muốn một H phải.

1104
00:56:09,500 --> 00:56:13,290
Và do đó, cách chúng ta sẽ làm điều đó là
chúng ta sẽ tạo ra một nút riêng biệt.

1105
00:56:13,290 --> 00:56:16,840
Chúng tôi không phân bổ cho bất kỳ số tiền
bộ nhớ cho mảng mới này,

1106
00:56:16,840 --> 00:56:20,720
và chúng ta sẽ gán lại con trỏ.

1107
00:56:20,720 --> 00:56:22,947
>> Chúng tôi sẽ giao
H, Trước hết, null này,

1108
00:56:22,947 --> 00:56:24,030
chúng ta sẽ thoát khỏi.

1109
00:56:24,030 --> 00:56:26,590
Chúng ta sẽ có
xuống dưới điểm H.

1110
00:56:26,590 --> 00:56:30,600
Nếu chúng ta nhìn thấy một H, chúng tôi muốn nó
để đi đến một nơi khác.

1111
00:56:30,600 --> 00:56:33,910
>> Tại đây, chúng ta có thể kiểm tra tắt yes.

1112
00:56:33,910 --> 00:56:38,170
Nếu chúng ta đánh một H sau khi T, oh,
sau đó chúng ta biết rằng đây là một từ.

1113
00:56:38,170 --> 00:56:41,110
Các Boolean là sẽ trở thành sự thật.

1114
00:56:41,110 --> 00:56:42,950
Mọi người đều rõ ràng về cách mà đã xảy ra?

1115
00:56:42,950 --> 00:56:45,110
ĐƯỢC.

1116
00:56:45,110 --> 00:56:47,214
>> Vì vậy, về cơ bản, tất cả các
các cấu trúc dữ liệu

1117
00:56:47,214 --> 00:56:50,130
chúng ta đã đi qua ngày hôm nay, tôi đã
đi qua chúng thực sự, thực sự nhanh chóng

1118
00:56:50,130 --> 00:56:52,192
và không để nhiều
chi tiết, và đó là OK.

1119
00:56:52,192 --> 00:56:53,900
Một khi bạn bắt đầu rối tung
với nó, bạn sẽ có

1120
00:56:53,900 --> 00:56:55,733
theo dõi các nơi
tất cả các con trỏ là,

1121
00:56:55,733 --> 00:56:58,060
những gì đang xảy ra trong bạn
cấu trúc dữ liệu, vân vân.

1122
00:56:58,060 --> 00:56:59,810
Họ sẽ rất hữu ích,
và nó là vào bạn

1123
00:56:59,810 --> 00:57:03,890
kẻ hoàn toàn tìm ra cách
bạn muốn thực hiện điều này.

1124
00:57:03,890 --> 00:57:07,650
>> Và như vậy pset4, của 5-- oh, đó là sai.

1125
00:57:07,650 --> 00:57:10,140
Pset5 là lỗi chính tả.

1126
00:57:10,140 --> 00:57:13,710
Như tôi đã nói trước đây, bạn sẽ, một lần
một lần nữa, tải về mã nguồn từ chúng tôi.

1127
00:57:13,710 --> 00:57:16,210
Có sẽ là ba chính
điều bạn sẽ phải download.

1128
00:57:16,210 --> 00:57:18,470
Bạn sẽ tải về từ điển,
kers, và văn bản.

1129
00:57:18,470 --> 00:57:21,660
>> Tất cả những điều này là
hoặc là từ điển của từ

1130
00:57:21,660 --> 00:57:25,190
chúng tôi muốn bạn để kiểm tra
hoặc kiểm tra thông tin

1131
00:57:25,190 --> 00:57:26,930
chúng tôi muốn bạn để kiểm tra chính tả.

1132
00:57:26,930 --> 00:57:29,670
Và do đó, các bộ từ điển
chúng tôi cung cấp cho bạn đang đi

1133
00:57:29,670 --> 00:57:34,870
để cung cấp cho bạn những lời thực tế mà chúng tôi muốn
bạn lưu trữ bằng cách nào đó trong một cách đó là

1134
00:57:34,870 --> 00:57:36,530
hiệu quả hơn nhiều so với một mảng.

1135
00:57:36,530 --> 00:57:38,470
Và sau đó các văn bản có
sẽ là những gì chúng tôi

1136
00:57:38,470 --> 00:57:43,900
yêu cầu bạn kiểm tra chính tả để đảm bảo
tất cả các từ có từ thực tế.

1137
00:57:43,900 --> 00:57:47,970
>> Và như vậy ba khối
chương trình mà chúng tôi sẽ cung cấp cho bạn

1138
00:57:47,970 --> 00:57:51,130
được gọi là dictionary.c,
dictionary.h, và speller.c.

1139
00:57:51,130 --> 00:57:56,500
Và vì vậy tất cả dictionary.c không được
những gì bạn được yêu cầu để thực hiện.

1140
00:57:56,500 --> 00:57:57,880
Nó nạp từ.

1141
00:57:57,880 --> 00:58:02,000
Nó chính tả kiểm tra chúng, và nó làm cho chắc chắn
rằng tất cả mọi thứ được đưa vào đúng.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h chỉ là một tập tin thư viện
mà tuyên bố tất cả những chức năng.

1143
00:58:05,180 --> 00:58:07,650
Và speller.c, chúng tôi sẽ cung cấp cho bạn.

1144
00:58:07,650 --> 00:58:09,290
Bạn không cần phải sửa đổi bất kỳ của nó.

1145
00:58:09,290 --> 00:58:14,290
Tất cả speller.c không là mất rằng,
tải nó, kiểm tra tốc độ của nó,

1146
00:58:14,290 --> 00:58:19,190
các bài kiểm tra benchmark của như thế nào
nhanh chóng bạn có thể làm mọi việc.

1147
00:58:19,190 --> 00:58:20,410
>> Đó là một Speller.

1148
00:58:20,410 --> 00:58:23,920
Chỉ cần không gây rối với nó, nhưng chắc
chắc chắn rằng bạn hiểu những gì nó làm.

1149
00:58:23,920 --> 00:58:28,090
Chúng tôi sử dụng một chức năng gọi là getrusage mà
kiểm tra việc thực hiện chính tả của bạn

1150
00:58:28,090 --> 00:58:28,590
kiểm sát viên.

1151
00:58:28,590 --> 00:58:32,200
Tất cả nó là cơ bản được kiểm tra
thời gian của tất cả mọi thứ trong từ điển của bạn,

1152
00:58:32,200 --> 00:58:33,680
do đó hãy chắc chắn rằng bạn hiểu nó.

1153
00:58:33,680 --> 00:58:36,660
Hãy cẩn thận để không gây rối với nó hay
điều gì khác sẽ không chạy đúng.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Và phần lớn các thách thức này là dành cho
các bạn để thực sự thay đổi dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Chúng tôi sẽ cung cấp cho bạn
140.000 từ trong từ điển.

1157
00:58:48,526 --> 00:58:50,900
Chúng tôi sẽ cung cấp cho bạn một văn bản
tập tin mà có những lời nói,

1158
00:58:50,900 --> 00:58:54,840
và chúng tôi muốn bạn để có thể tổ chức
chúng vào một bảng băm hoặc một Trie

1159
00:58:54,840 --> 00:58:58,140
bởi vì khi chúng tôi yêu cầu bạn đánh vần
check-- tưởng tượng nếu bạn chính tả

1160
00:58:58,140 --> 00:59:00,690
kiểm tra như Odyssey của Homer.

1161
00:59:00,690 --> 00:59:03,010
Nó giống như, thử nghiệm rất lớn rất lớn này.

1162
00:59:03,010 --> 00:59:05,190
>> Hãy tưởng tượng, nếu mỗi đơn
từ mà bạn đã phải tìm

1163
00:59:05,190 --> 00:59:08,100
thông qua một loạt các giá trị 140.000.

1164
00:59:08,100 --> 00:59:10,350
Điều đó sẽ mất mãi mãi
cho máy tính của bạn để chạy.

1165
00:59:10,350 --> 00:59:14,490
Đó là lý do tại sao chúng tôi muốn tổ chức của chúng tôi
dữ liệu vào cấu trúc dữ liệu hiệu quả hơn

1166
00:59:14,490 --> 00:59:17,270
chẳng hạn như một bảng băm hoặc một Trie.

1167
00:59:17,270 --> 00:59:20,700
Và sau đó các bạn có thể loại
khi bạn tìm kiếm truy cập

1168
00:59:20,700 --> 00:59:22,570
thứ dễ dàng hơn và nhanh chóng hơn.

1169
00:59:22,570 --> 00:59:24,934
>> Và vì vậy hãy cẩn thận để giải quyết va chạm.

1170
00:59:24,934 --> 00:59:27,350
Bạn sẽ nhận được một bó
các từ đó bắt đầu với A.

1171
00:59:27,350 --> 00:59:29,957
Bạn sẽ nhận được một lời bó
bắt đầu bằng B. Up cho bạn

1172
00:59:29,957 --> 00:59:31,290
chàng trai như thế nào bạn muốn giải quyết nó.

1173
00:59:31,290 --> 00:59:34,144
Có lẽ có nhiều
hàm băm hiệu quả

1174
00:59:34,144 --> 00:59:36,810
hơn là chỉ các chữ cái đầu tiên của
một cái gì đó, và vì vậy đó là tùy thuộc vào bạn

1175
00:59:36,810 --> 00:59:38,190
chàng trai để loại làm bất cứ điều gì bạn muốn.

1176
00:59:38,190 --> 00:59:40,148
>> Có lẽ bạn muốn thêm
tất cả các chữ cái với nhau.

1177
00:59:40,148 --> 00:59:43,410
Có thể bạn muốn muốn làm những điều kỳ lạ
để hạch toán số của các chữ cái,

1178
00:59:43,410 --> 00:59:43,970
sao cũng được.

1179
00:59:43,970 --> 00:59:45,386
Up để các bạn làm thế nào bạn muốn làm.

1180
00:59:45,386 --> 00:59:49,262
Nếu bạn muốn làm một bảng băm, nếu bạn
muốn thử một Trie, hoàn toàn tùy thuộc vào bạn.

1181
00:59:49,262 --> 00:59:52,470
Tôi sẽ cảnh báo bạn trước thời gian mà các
Trie thường là một chút khó khăn hơn

1182
00:59:52,470 --> 00:59:54,520
chỉ vì có rất nhiều
nhiều con trỏ để theo dõi.

1183
00:59:54,520 --> 00:59:55,645
Nhưng hoàn toàn vào bạn guys.

1184
00:59:55,645 --> 00:59:58,742
Đó là hiệu quả hơn nhiều
trong hầu hết các trường hợp.

1185
00:59:58,742 --> 01:00:01,450
Bạn muốn thực sự có thể giữ
theo dõi tất cả các con trỏ của bạn.

1186
01:00:01,450 --> 01:00:03,850
Giống như làm điều tương tự
rằng tôi đã làm ở đây.

1187
01:00:03,850 --> 01:00:06,871
Khi bạn đang cố gắng để chèn
giá trị vào một bảng băm hoặc xóa,

1188
01:00:06,871 --> 01:00:08,620
hãy chắc chắn rằng bạn đang
thực sự theo dõi

1189
01:00:08,620 --> 01:00:11,860
của nơi mà mọi thứ là vì
nó thực sự dễ dàng cho nếu tôi

1190
01:00:11,860 --> 01:00:14,727
cố gắng để chèn như từ, andy.

1191
01:00:14,727 --> 01:00:16,810
Hãy chỉ nói rằng đó là một
từ thực tế, từ đó, andy,

1192
01:00:16,810 --> 01:00:19,640
vào một danh sách khổng lồ của A từ.

1193
01:00:19,640 --> 01:00:22,450
>> Nếu tôi chỉ xảy ra để gán lại
một sai con trỏ, oops,

1194
01:00:22,450 --> 01:00:24,940
có đi toàn bộ
phần còn lại của danh sách liên kết của tôi.

1195
01:00:24,940 --> 01:00:26,897
Bây giờ từ duy nhất tôi
có là andy, và bây giờ

1196
01:00:26,897 --> 01:00:29,230
tất cả các từ khác trong
từ điển đã bị mất.

1197
01:00:29,230 --> 01:00:31,370
Và do đó, bạn muốn chắc chắn rằng bạn
theo dõi tất cả các con trỏ của bạn

1198
01:00:31,370 --> 01:00:33,661
hoặc người nào khác bạn sẽ nhận được
vấn đề lớn trong mã của bạn.

1199
01:00:33,661 --> 01:00:35,840
Vẽ những điều trên một cách cẩn thận từng bước.

1200
01:00:35,840 --> 01:00:37,870
Nó làm cho nó dễ dàng hơn nhiều để nghĩ đến.

1201
01:00:37,870 --> 01:00:40,910
>> Và cuối cùng, bạn muốn để có thể
kiểm tra hiệu suất của bạn trong chương trình của bạn

1202
01:00:40,910 --> 01:00:41,618
trên bảng lớn.

1203
01:00:41,618 --> 01:00:43,710
Nếu các bạn có một
nhìn vào CS50 ngay bây giờ,

1204
01:00:43,710 --> 01:00:45,210
chúng tôi có những gì được gọi là các bảng lớn.

1205
01:00:45,210 --> 01:00:50,200
Đây là bảng điểm của các nhanh nhất
đánh vần lần kiểm tra trên tất cả các CS50

1206
01:00:50,200 --> 01:00:55,720
ngay bây giờ, tôi nghĩ rằng các hàng đầu như 10
lần tôi nghĩ rằng tám trong số đó là nhân viên.

1207
01:00:55,720 --> 01:00:57,960
Chúng tôi thực sự muốn các bạn để đánh bại chúng tôi.

1208
01:00:57,960 --> 01:01:00,870
>> Tất cả chúng ta đã cố gắng thực hiện
mã nhanh nhất có thể.

1209
01:01:00,870 --> 01:01:04,880
Chúng tôi muốn các bạn thử để thách thức
chúng tôi và thực hiện nhanh hơn so với tất cả chúng ta

1210
01:01:04,880 --> 01:01:05,550
có thể.

1211
01:01:05,550 --> 01:01:07,970
Và vì vậy đây thực sự là
lần đầu tiên chúng tôi

1212
01:01:07,970 --> 01:01:12,680
hỏi các bạn phải làm một pset đó
bạn thực sự có thể làm trong bất cứ phương pháp

1213
01:01:12,680 --> 01:01:13,760
bạn muốn.

1214
01:01:13,760 --> 01:01:17,730
>> Tôi luôn luôn nói rằng, đây là giống hơn
đến một giải pháp thực tế cuộc sống, phải không?

1215
01:01:17,730 --> 01:01:19,550
Tôi nói, hey, tôi cần bạn làm điều này.

1216
01:01:19,550 --> 01:01:21,380
Xây dựng một chương trình mà thực hiện điều này đối với tôi.

1217
01:01:21,380 --> 01:01:22,630
Làm nó tuy nhiên bạn muốn.

1218
01:01:22,630 --> 01:01:24,271
Tôi chỉ biết rằng tôi muốn nhanh chóng.

1219
01:01:24,271 --> 01:01:25,770
Đó là thách thức của bạn trong tuần này.

1220
01:01:25,770 --> 01:01:27,531
Các bạn, chúng ta đang đi
để cung cấp cho bạn một công việc.

1221
01:01:27,531 --> 01:01:29,030
Chúng tôi sẽ cung cấp cho bạn một thách thức.

1222
01:01:29,030 --> 01:01:31,559
Và sau đó nó lên đến với bạn
để hoàn toàn chỉ ra

1223
01:01:31,559 --> 01:01:34,100
những gì là nhanh nhất và nhất
cách hiệu quả để thực hiện điều này.

1224
01:01:34,100 --> 01:01:34,600
Yeah?

1225
01:01:34,600 --> 01:01:37,476
>> Đung Có phải chúng ta được phép nếu
muốn nghiên cứu những cách nhanh hơn

1226
01:01:37,476 --> 01:01:40,821
làm bảng băm trực tuyến, chúng tôi có thể làm
đó và trích dẫn mã của người khác?

1227
01:01:40,821 --> 01:01:42,070
Andi PENG: Vâng, hoàn toàn tốt.

1228
01:01:42,070 --> 01:01:44,320
Vì vậy, nếu các bạn đọc
spec, có một dòng

1229
01:01:44,320 --> 01:01:48,310
trong spec nói rằng các bạn
là hoàn toàn miễn phí để nghiên cứu băm

1230
01:01:48,310 --> 01:01:51,070
chức năng về những gì là một số
của các hàm băm nhanh hơn

1231
01:01:51,070 --> 01:01:54,720
chạy qua những điều như
miễn là bạn trích dẫn mã.

1232
01:01:54,720 --> 01:01:57,220
Vì vậy, một số người đã có
đã tìm ra cách nhanh chóng

1233
01:01:57,220 --> 01:02:00,250
làm cờ chính tả, về nhanh
cách lưu trữ thông tin.

1234
01:02:00,250 --> 01:02:02,750
Hoàn toàn vào bạn nếu bạn kẻ
muốn chỉ cần đi mà, phải không?

1235
01:02:02,750 --> 01:02:04,045
Hãy chắc chắn rằng bạn đang trích dẫn.

1236
01:02:04,045 --> 01:02:06,170
Thách thức ở đây thực sự
rằng chúng tôi đang cố gắng để kiểm tra

1237
01:02:06,170 --> 01:02:09,750
là đảm bảo rằng bạn biết
theo cách của bạn xung quanh con trỏ.

1238
01:02:09,750 --> 01:02:12,700
Theo như bạn thực hiện
hàm băm thực tế

1239
01:02:12,700 --> 01:02:15,070
và đến với như
toán học để làm điều đó,

1240
01:02:15,070 --> 01:02:17,570
các bạn có thể nghiên cứu bất cứ điều gì
phương pháp trực tuyến các bạn muốn.

1241
01:02:17,570 --> 01:02:17,996
Yeah?

1242
01:02:17,996 --> 01:02:19,700
>> Đung chúng tôi chỉ có thể trích dẫn
bằng cách sử dụng các [Không nghe thấy]?

1243
01:02:19,700 --> 01:02:20,120
>> Andi PENG: Yeah.

1244
01:02:20,120 --> 01:02:22,328
Bạn chỉ có thể, trong bình luận của bạn,
bạn có thể trích dẫn như thế, oh,

1245
01:02:22,328 --> 01:02:26,127
lấy từ yada, yada,
yada, hàm băm.

1246
01:02:26,127 --> 01:02:27,210
Bất cứ ai có bất kỳ câu hỏi?

1247
01:02:27,210 --> 01:02:29,694
Chúng tôi thực sự đi lướt
thông qua phần ngày hôm nay.

1248
01:02:29,694 --> 01:02:31,610
Tôi sẽ ở đây để
trả lời câu hỏi là tốt.

1249
01:02:31,610 --> 01:02:36,570
>> Ngoài ra, như tôi đã nói, văn phòng
giờ đêm nay và ngày mai.

1250
01:02:36,570 --> 01:02:40,307
Spec tuần này là thực sự
siêu dễ dàng và siêu ngắn để đọc.

1251
01:02:40,307 --> 01:02:43,140
Tôi sẽ đề nghị dùng một cái nhìn, chỉ
đọc qua toàn bộ của nó.

1252
01:02:43,140 --> 01:02:45,730
>> Và Zamyla thực sự đi bạn
qua mỗi chức năng

1253
01:02:45,730 --> 01:02:49,796
bạn cần phải thực hiện, và vì vậy nó
rất, rất rõ ràng làm thế nào để làm tất cả mọi thứ.

1254
01:02:49,796 --> 01:02:51,920
Chỉ cần chắc chắn rằng bạn đang
theo dõi các con trỏ.

1255
01:02:51,920 --> 01:02:53,650
Đây là một pset rất khó khăn.

1256
01:02:53,650 --> 01:02:56,744
>> Nó không phải thách thức bởi vì như thế,
oh, các khái niệm là còn nhiều hơn nữa

1257
01:02:56,744 --> 01:02:59,160
khó khăn, hoặc bạn phải học
rất nhiều cú pháp mới đường

1258
01:02:59,160 --> 01:03:00,650
mà bạn đã làm cho pset cuối cùng.

1259
01:03:00,650 --> 01:03:03,320
Pset này là khó khăn vì
có rất nhiều con trỏ,

1260
01:03:03,320 --> 01:03:06,980
và sau đó nó rất, rất dễ dàng để một lần
bạn có một lỗi trong mã của bạn không thể

1261
01:03:06,980 --> 01:03:08,315
để tìm nơi mà lỗi đó là.

1262
01:03:08,315 --> 01:03:13,200
>> Và để hoàn thành và niềm tin hoàn toàn vào bạn
chàng trai để có thể đánh bại chúng tôi [không nghe]

1263
01:03:13,200 --> 01:03:13,700
cách viết.

1264
01:03:13,700 --> 01:03:16,640
Tôi thực sự không có bất kỳ mỏ bằng văn bản
chưa, nhưng tôi sắp viết của tôi.

1265
01:03:16,640 --> 01:03:19,070
Vì vậy, trong khi bạn đang viết
của bạn, tôi sẽ viết tôi.

1266
01:03:19,070 --> 01:03:21,070
Tôi sẽ cố gắng làm cho
tôi nhanh hơn của bạn.

1267
01:03:21,070 --> 01:03:23,940
Chúng tôi sẽ xem ai có một cách nhanh nhất.

1268
01:03:23,940 --> 01:03:27,340
>> Và vâng, tôi sẽ thấy tất cả
các bạn ở đây vào thứ ba.

1269
01:03:27,340 --> 01:03:29,510
Tôi sẽ chạy một loại giống như một hội thảo pset.

1270
01:03:29,510 --> 01:03:32,640
Tất cả các bộ phận này
tuần là hội thảo pset,

1271
01:03:32,640 --> 01:03:36,690
vậy các bạn có nhiều cơ hội
giúp đỡ, giờ làm việc như mọi khi,

1272
01:03:36,690 --> 01:03:41,330
và tôi thực sự mong muốn
đọc tất cả các mã guys của bạn '.

1273
01:03:41,330 --> 01:03:44,160
Tôi có câu đố lên đây nếu bạn
kẻ muốn đến được những người.

1274
01:03:44,160 --> 01:03:45,880
Đó là tất cả.

1275
01:03:45,880 --> 01:03:48,180