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

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: Được rồi, vì vậy chúng tôi đang trở lại.

3
00:00:13,120 --> 00:00:14,480
Chào mừng bạn đến CS50.

4
00:00:14,480 --> 00:00:16,510
Đây là phần cuối của tuần bảy.

5
00:00:16,510 --> 00:00:20,200
Vì vậy, nhớ lại rằng thời gian qua, chúng tôi bắt đầu
nhìn hơi phức tạp hơn

6
00:00:20,200 --> 00:00:21,100
cấu trúc dữ liệu.

7
00:00:21,100 --> 00:00:25,110
Vì cho đến bây giờ, tất cả chúng tôi đã thực sự
lúc xử lý của chúng tôi là điều này, một mảng.

8
00:00:25,110 --> 00:00:29,340
>> Nhưng trước khi chúng tôi loại bỏ các mảng như không
tất cả những gì thú vị, mà thực sự nó

9
00:00:29,340 --> 00:00:33,570
thực sự là, những gì một số các
Điểm cộng của dữ liệu đơn giản này

10
00:00:33,570 --> 00:00:34,560
cấu trúc cho đến nay?

11
00:00:34,560 --> 00:00:36,110
Nó tốt là những gì?

12
00:00:36,110 --> 00:00:39,450
Cho đến nay như chúng ta đã thấy?

13
00:00:39,450 --> 00:00:42,540
Làm những gì bạn có?

14
00:00:42,540 --> 00:00:44,028
Không có gì.

15
00:00:44,028 --> 00:00:45,020
>> HỌC SINH: [nghe được].

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: Cái gì thế?

17
00:00:45,395 --> 00:00:46,410
>> HỌC SINH: [nghe được].

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1: cố định kích thước.

19
00:00:47,000 --> 00:00:51,260
OK, vậy tại sao kích thước cố định tốt mặc dù?

20
00:00:51,260 --> 00:00:53,180
>> HỌC SINH: [nghe được].

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: OK, vì vậy hiệu quả trong
nghĩa là bạn có thể phân bổ một

22
00:00:56,240 --> 00:01:00,070
số tiền cố định của không gian, mà hy vọng
là chính xác như nhiều

23
00:01:00,070 --> 00:01:01,180
không gian như bạn muốn.

24
00:01:01,180 --> 00:01:02,720
Do đó có thể được hoàn toàn một cộng.

25
00:01:02,720 --> 00:01:06,530
>> Một mặt khác lên của một mảng là những gì?

26
00:01:06,530 --> 00:01:07,610
Yeah?

27
00:01:07,610 --> 00:01:08,750
>> HỌC SINH: [nghe được].

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1: Tất cả các - xin lỗi?

29
00:01:09,550 --> 00:01:11,270
>> HỌC SINH: [nghe được].

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: Tất cả các ô trong bộ nhớ
hoặc bên cạnh nhau.

31
00:01:13,620 --> 00:01:15,220
Và đó là hữu ích - lý do tại sao?

32
00:01:15,220 --> 00:01:15,970
Đó là hoàn toàn đúng.

33
00:01:15,970 --> 00:01:18,611
Nhưng làm thế nào chúng ta có thể khai thác sự thật đó?

34
00:01:18,611 --> 00:01:21,500
>> HỌC SINH: [nghe được].

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: Chính xác, chúng tôi có thể theo dõi
nơi mà mọi thứ chỉ bằng cách biết

36
00:01:24,490 --> 00:01:28,560
một địa chỉ, cụ thể là địa chỉ của
byte đầu tiên là đoạn bộ nhớ.

37
00:01:28,560 --> 00:01:30,420
Hoặc trong trường hợp của chuỗi,
địa chỉ đầu tiên

38
00:01:30,420 --> 00:01:31,460
char trong chuỗi.

39
00:01:31,460 --> 00:01:33,330
Và từ đó, chúng ta có thể tìm thấy
kết thúc của chuỗi.

40
00:01:33,330 --> 00:01:35,710
Chúng ta có thể tìm các phần tử thứ hai,
Yếu tố thứ ba, và vv.

41
00:01:35,710 --> 00:01:38,740
>> Và do đó, cách ưa thích của mô tả đó
tính năng là mảng cung cấp cho chúng tôi

42
00:01:38,740 --> 00:01:40,020
truy cập ngẫu nhiên.

43
00:01:40,020 --> 00:01:44,330
Chỉ bằng cách sử dụng khung vuông
ký hiệu và một số, bạn có thể nhảy

44
00:01:44,330 --> 00:01:48,070
một yếu tố cụ thể trong mảng
trong thời gian liên tục, lớn O

45
00:01:48,070 --> 00:01:49,810
một, vậy để nói chuyện.

46
00:01:49,810 --> 00:01:51,080
>> Nhưng có được một số nhược điểm.

47
00:01:51,080 --> 00:01:53,110
Thật là một mảng không làm một cách dễ dàng?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Đó là những gì không tốt?

50
00:01:57,170 --> 00:01:58,810
>> HỌC SINH: [nghe được].

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: Cái gì thế?

52
00:01:59,860 --> 00:02:00,530
>> HỌC SINH: [nghe được].

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: Mở rộng quy mô.

54
00:02:01,460 --> 00:02:04,800
Vì vậy, những nhược điểm của mảng là
chính xác với những gì mà các

55
00:02:04,800 --> 00:02:05,540
mặt tích cực là.

56
00:02:05,540 --> 00:02:07,610
Vì vậy, một trong những nhược điểm là
rằng đó là một kích thước cố định.

57
00:02:07,610 --> 00:02:09,400
Vì vậy, bạn có thể không thực sự phát triển nó.

58
00:02:09,400 --> 00:02:13,510
Bạn có thể tái phân bổ một phần lớn của
bộ nhớ, và sau đó di chuyển các yếu tố cũ

59
00:02:13,510 --> 00:02:14,460
vào mảng mới.

60
00:02:14,460 --> 00:02:18,060
Và sau đó tự do mảng cũ, cho
Ví dụ, bằng cách sử dụng malloc hoặc tương tự

61
00:02:18,060 --> 00:02:21,180
chức năng gọi là realloc, mà
reallocates bộ nhớ.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, như một sang một bên, cố gắng để cung cấp cho bạn
bộ nhớ đó là bên cạnh mảng

63
00:02:25,490 --> 00:02:26,610
mà bạn đã có.

64
00:02:26,610 --> 00:02:28,740
Nhưng nó có thể di chuyển mọi thứ
xung quanh hoàn toàn.

65
00:02:28,740 --> 00:02:30,710
Nhưng trong ngắn hạn, đó là đắt tiền, phải không?

66
00:02:30,710 --> 00:02:33,440
Bởi vì nếu bạn có một đoạn bộ nhớ của
kích thước này, nhưng bạn thực sự muốn một

67
00:02:33,440 --> 00:02:36,710
kích thước này, và bạn muốn giữ lại
các yếu tố nguyên gốc, bạn có

68
00:02:36,710 --> 00:02:40,510
khoảng một tuyến tính quá trình sao chép thời gian
mà cần phải xảy ra từ

69
00:02:40,510 --> 00:02:41,900
mảng cũ sang mới.

70
00:02:41,900 --> 00:02:44,630
Và thực tế là yêu cầu điều hành
hệ thống một lần nữa và một lần nữa và

71
00:02:44,630 --> 00:02:48,340
một lần nữa cho khối lớn của bộ nhớ có thể bắt đầu
chi phí cho bạn một số thời gian là tốt.

72
00:02:48,340 --> 00:02:52,250
Vì vậy, nó là cả một phước lành và một lời nguyền trong
che giấu, thực tế là các mảng

73
00:02:52,250 --> 00:02:53,860
có kích thước cố định.

74
00:02:53,860 --> 00:02:56,790
Nhưng nếu chúng tôi giới thiệu thay vì một cái gì đó
như thế này, mà chúng tôi gọi là một liên kết

75
00:02:56,790 --> 00:03:00,580
danh sách, chúng tôi có được một vài mặt tích cực và
một vài nhược điểm ở đây là tốt.

76
00:03:00,580 --> 00:03:05,780
>> Vì vậy, một danh sách liên kết đơn giản chỉ là một dữ liệu
cấu trúc tạo thành cấu trúc của C trong này

77
00:03:05,780 --> 00:03:09,850
trường hợp, trong đó một cấu trúc, thu hồi, chỉ là
một container cho một hoặc nhiều cụ thể

78
00:03:09,850 --> 00:03:11,100
loại biến.

79
00:03:11,100 --> 00:03:16,110
Trong trường hợp này, điều gì làm các kiểu dữ liệu
xuất hiện để được bên trong các cấu trúc mà

80
00:03:16,110 --> 00:03:17,600
Lần cuối cùng chúng tôi được gọi là một nút?

81
00:03:17,600 --> 00:03:19,380
Mỗi một trong các hình chữ nhật là một nút.

82
00:03:19,380 --> 00:03:22,660
Và mỗi hình chữ nhật nhỏ hơn
bên trong của nó là một loại dữ liệu.

83
00:03:22,660 --> 00:03:25,300
Những loại nào chúng ta nói
họ vào thứ hai?

84
00:03:25,300 --> 00:03:26,478
Yeah?

85
00:03:26,478 --> 00:03:27,870
>> HỌC SINH: [nghe được].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: Một biến và một con trỏ, hoặc
cụ thể hơn, một int, cho n,

87
00:03:30,721 --> 00:03:32,180
và một con trỏ ở phía dưới.

88
00:03:32,180 --> 00:03:35,360
Cả hai của những xảy ra được 32 bit, tại
ít nhất là trên một máy tính như CS50 này

89
00:03:35,360 --> 00:03:37,980
Thiết bị, và vì thế chúng
rút ra như nhau trong kích thước.

90
00:03:37,980 --> 00:03:42,260
>> Vì vậy, những gì đang sử dụng con trỏ
mặc dù cho rõ ràng?

91
00:03:42,260 --> 00:03:47,690
Tại sao lại thêm mũi tên này bây giờ khi mảng là
như vậy tốt đẹp và sạch sẽ và đơn giản?

92
00:03:47,690 --> 00:03:50,460
Là con trỏ làm những gì cho
chúng tôi trong mỗi một nút?

93
00:03:50,460 --> 00:03:52,160
>> HỌC SINH: [nghe được].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: Chính xác.

95
00:03:52,465 --> 00:03:54,120
Nó nói cho bạn nơi
một kế tiếp.

96
00:03:54,120 --> 00:03:57,350
Vì vậy, tôi loại sử dụng sự tương tự của
sử dụng một sợi để sắp xếp của

97
00:03:57,350 --> 00:03:59,180
sợi các nút với nhau.

98
00:03:59,180 --> 00:04:01,760
Và đó chính xác là những gì chúng tôi đang làm với
con trỏ vì mỗi

99
00:04:01,760 --> 00:04:06,360
khối của bộ nhớ có thể có hoặc có thể không
tiếp giáp lãnh hải, trở lại trở lại để trở lại

100
00:04:06,360 --> 00:04:09,500
trong bộ nhớ RAM, bởi vì mỗi khi bạn
gọi malloc nói, cho tôi đủ

101
00:04:09,500 --> 00:04:12,510
byte cho một nút mới, nó có thể
ở đây hoặc nó có thể là đây.

102
00:04:12,510 --> 00:04:13,120
Nó có thể là đây.

103
00:04:13,120 --> 00:04:13,730
Nó có thể là đây.

104
00:04:13,730 --> 00:04:14,640
Bạn chỉ không biết.

105
00:04:14,640 --> 00:04:17,880
>> Nhưng sử dụng con trỏ trong các địa chỉ của
các nút, bạn có thể ghép chúng

106
00:04:17,880 --> 00:04:22,370
với nhau một cách trông trực quan
như một danh sách ngay cả khi những điều này là

107
00:04:22,370 --> 00:04:26,770
tất cả các trải ra khắp một hoặc
hai hoặc bốn GB bộ nhớ RAM của bạn

108
00:04:26,770 --> 00:04:28,760
bên trong máy tính của riêng bạn.

109
00:04:28,760 --> 00:04:33,230
>> Vì vậy, các nhược điểm, sau đó,
một danh sách liên kết là gì?

110
00:04:33,230 --> 00:04:34,670
Một mức giá chúng tôi là những gì
dường như trả tiền?

111
00:04:34,670 --> 00:04:36,010
>> HỌC SINH: [nghe được].

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: thêm không gian, phải không?

113
00:04:36,920 --> 00:04:39,340
Chúng tôi, trong trường hợp này, tăng gấp đôi số tiền
của không gian bởi vì chúng tôi đã đi

114
00:04:39,340 --> 00:04:43,500
từ 32 bit cho mỗi nút, cho mỗi
int, vì vậy bây giờ 64 bit bởi vì chúng ta phải

115
00:04:43,500 --> 00:04:45,050
giữ xung quanh một con trỏ là tốt.

116
00:04:45,050 --> 00:04:48,860
Bạn sẽ có được hiệu quả hơn nếu cấu trúc của bạn
lớn hơn điều này đơn giản.

117
00:04:48,860 --> 00:04:52,020
Nếu bạn thực sự có một sinh viên trong
trong số đó là một vài dây cho

118
00:04:52,020 --> 00:04:55,430
tên và ngôi nhà, có thể một số ID,
có thể một số lĩnh vực khác hoàn toàn.

119
00:04:55,430 --> 00:04:59,000
>> Vì vậy, nếu bạn có một cấu trúc đủ lớn,
thì có lẽ chi phí của con trỏ

120
00:04:59,000 --> 00:05:00,010
không phải là một việc lớn như vậy.

121
00:05:00,010 --> 00:05:03,570
Đây là một chút của một trường hợp góc trong đó
chúng tôi đang lưu trữ như một nguyên thủy đơn giản

122
00:05:03,570 --> 00:05:04,760
bên trong các danh sách liên kết.

123
00:05:04,760 --> 00:05:05,790
Nhưng điểm là như nhau.

124
00:05:05,790 --> 00:05:08,230
Bạn chắc chắn chi tiêu nhiều hơn
bộ nhớ, nhưng bạn đang nhận được

125
00:05:08,230 --> 00:05:08,990
linh hoạt.

126
00:05:08,990 --> 00:05:12,280
Bởi vì bây giờ nếu tôi muốn thêm một yếu tố
ở đầu danh sách này,

127
00:05:12,280 --> 00:05:14,340
Tôi cần phải phân bổ một nút mới.

128
00:05:14,340 --> 00:05:17,180
Và tôi có phải chỉ cần cập nhật những
mũi tên bằng cách nào đó bằng cách di chuyển

129
00:05:17,180 --> 00:05:17,980
một số điểm xung quanh.

130
00:05:17,980 --> 00:05:20,580
>> Nếu tôi muốn chèn một cái gì đó vào
giữa danh sách, tôi không cần phải

131
00:05:20,580 --> 00:05:24,410
đẩy sang một bên tất cả mọi người như chúng tôi đã làm trong
qua tuần với các tình nguyện viên người

132
00:05:24,410 --> 00:05:25,700
đại diện một mảng.

133
00:05:25,700 --> 00:05:29,470
Tôi chỉ có thể phân bổ một nút mới và
sau đó chỉ cần chỉ mũi tên trong

134
00:05:29,470 --> 00:05:32,290
hướng khác nhau bởi vì nó không
phải duy trì trong thực tế

135
00:05:32,290 --> 00:05:35,670
bộ nhớ một dòng đúng như tôi đã rút ra
nó ở đây trên màn hình.

136
00:05:35,670 --> 00:05:38,400
>> Và sau đó cuối cùng, nếu bạn muốn chèn
một cái gì đó vào cuối danh sách, đó là

137
00:05:38,400 --> 00:05:39,210
thậm chí còn dễ dàng hơn.

138
00:05:39,210 --> 00:05:43,320
Đây là loại ký hiệu tùy ý,
nhưng con trỏ 34 của, hãy đoán.

139
00:05:43,320 --> 00:05:46,710
Giá trị của con trỏ của nó nhất là những gì
thể loại vẽ giống như một tuổi

140
00:05:46,710 --> 00:05:47,700
ăng ten trường đó?

141
00:05:47,700 --> 00:05:48,920
>> HỌC SINH: [nghe được].

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: Đây có thể là vô giá trị.

143
00:05:49,900 --> 00:05:52,710
Và quả thật đó là một trong những tác giả của
đại diện của null.

144
00:05:52,710 --> 00:05:56,310
Và nó là vô giá trị bởi vì bạn hoàn toàn
cần phải biết nơi kết thúc của một liên kết

145
00:05:56,310 --> 00:06:00,050
danh sách là, vì sợ rằng bạn giữ sau và
sau và làm theo các mũi tên

146
00:06:00,050 --> 00:06:01,170
một số giá trị rác.

147
00:06:01,170 --> 00:06:06,230
Vì vậy, vô giá trị sẽ có nghĩa rằng không có
các nút hơn ở bên phải của số 34,

148
00:06:06,230 --> 00:06:07,200
trong trường hợp này.

149
00:06:07,200 --> 00:06:10,270
>> Vì vậy, chúng tôi đề xuất rằng chúng ta có thể thực hiện
nút này trong mã.

150
00:06:10,270 --> 00:06:12,130
Và chúng tôi đã nhìn thấy loại
cú pháp trước.

151
00:06:12,130 --> 00:06:15,090
Typedef chỉ định nghĩa một kiểu mới
chúng ta, cho chúng ta một từ đồng nghĩa như

152
00:06:15,090 --> 00:06:17,100
chuỗi là cho char *.

153
00:06:17,100 --> 00:06:21,030
Trong trường hợp này, nó sẽ cung cấp cho chúng tôi
viết tắt ký hiệu để nút cấu trúc

154
00:06:21,030 --> 00:06:24,010
có thể thay vì chỉ được viết như
nút, đó là rất nhiều bụi.

155
00:06:24,010 --> 00:06:25,360
Đó là rất nhiều ít tiết.

156
00:06:25,360 --> 00:06:30,080
>> Bên trong của một nút là rõ ràng một int
gọi là n, và sau đó một cấu trúc nút *

157
00:06:30,080 --> 00:06:34,670
có nghĩa là chính xác những gì chúng ta muốn
mũi tên có nghĩa là, một con trỏ đến một

158
00:06:34,670 --> 00:06:36,940
nút của các kiểu dữ liệu chính xác.

159
00:06:36,940 --> 00:06:40,300
Và nghĩ rằng mình có thể thực hiện một
chức năng tìm kiếm như thế này, tại

160
00:06:40,300 --> 00:06:41,890
Thoạt nhìn có vẻ
một chút phức tạp.

161
00:06:41,890 --> 00:06:43,330
Nhưng chúng ta hãy xem nó trong ngữ cảnh.

162
00:06:43,330 --> 00:06:45,480
>> Hãy để tôi đi qua để thiết bị ở đây.

163
00:06:45,480 --> 00:06:48,460
Hãy để tôi mở ra một tập tin gọi là
danh sách không chấm h.

164
00:06:48,460 --> 00:06:53,950
Và rằng chỉ có các định nghĩa chúng tôi
chỉ thấy một thời điểm trước đây cho dữ liệu này

165
00:06:53,950 --> 00:06:55,390
loại được gọi là một nút.

166
00:06:55,390 --> 00:06:57,350
Vì vậy, chúng tôi đã đặt đó vào một tập tin chấm h.

167
00:06:57,350 --> 00:07:01,430
>> Và như một sang một bên, mặc dù điều này
chương trình mà bạn đang về để xem là

168
00:07:01,430 --> 00:07:05,410
không tất cả những gì phức tạp, nó thực sự
ước khi viết một chương trình để

169
00:07:05,410 --> 00:07:10,270
đặt những thứ như các loại dữ liệu, để kéo
hằng số đôi khi, bên trong của bạn

170
00:07:10,270 --> 00:07:13,210
tập tin tiêu đề và không nhất thiết phải trong
tập tin C của bạn, chắc chắn khi bạn

171
00:07:13,210 --> 00:07:17,370
các chương trình lớn hơn và lớn hơn, do đó
bạn biết nơi để tìm cho cả hai

172
00:07:17,370 --> 00:07:20,840
tài liệu hướng dẫn trong một số trường hợp, hoặc
cho vấn đề cơ bản như thế này,

173
00:07:20,840 --> 00:07:22,360
định nghĩa của một số loại.

174
00:07:22,360 --> 00:07:25,680
>> Nếu bây giờ tôi mở ra danh sách không chấm
c, nhận thấy một vài điều.

175
00:07:25,680 --> 00:07:29,090
Nó bao gồm một vài tập tin tiêu đề, nhất
trong đó chúng tôi đã nhìn thấy trước.

176
00:07:29,090 --> 00:07:31,980
Nó bao gồm các tập tin tiêu đề riêng của mình.

177
00:07:31,980 --> 00:07:35,200
>> Và như một sang một bên, đó là lý do tại sao đôi
báo giá ở đây, trái với góc

178
00:07:35,200 --> 00:07:38,340
dấu ngoặc trên dòng
Tôi đã nhấn mạnh đó?

179
00:07:38,340 --> 00:07:39,180
>> HỌC SINH: [nghe được].

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: Đúng như vậy đó là một tập tin địa phương.

181
00:07:40,460 --> 00:07:44,300
Vì vậy, nếu đó là một tập tin địa phương của riêng của bạn ở đây
trên dòng 15, ví dụ, bạn sử dụng

182
00:07:44,300 --> 00:07:46,570
các dấu ngoặc kép thay
các dấu ngoặc góc cạnh.

183
00:07:46,570 --> 00:07:48,270
>> Bây giờ điều này là khá thú vị.

184
00:07:48,270 --> 00:07:51,830
Nhận thấy rằng tôi đã khai báo toàn cầu
biến trong chương trình này trên dòng 18

185
00:07:51,830 --> 00:07:55,910
gọi là đầu tiên, ý tưởng là đây là
sẽ là một con trỏ đến đầu tiên

186
00:07:55,910 --> 00:07:59,190
nút trong danh sách liên kết của tôi, và tôi đã
khởi tạo nó thành vô giá trị, bởi vì tôi đã

187
00:07:59,190 --> 00:08:02,310
không được giao thực tế
các nút chỉ được nêu ra.

188
00:08:02,310 --> 00:08:07,570
>> Vì vậy, điều này thể hiện, những bức tranh, những gì chúng tôi
nhìn thấy một thời điểm trước đây trong hình ảnh như

189
00:08:07,570 --> 00:08:10,090
rằng con trỏ trên xa
bên trái tay.

190
00:08:10,090 --> 00:08:12,260
Vì vậy, ngay bây giờ, con trỏ
không có một mũi tên.

191
00:08:12,260 --> 00:08:14,590
Nó thay vì chỉ là vô giá trị.

192
00:08:14,590 --> 00:08:17,880
Nhưng nó đại diện cho những gì sẽ được
địa chỉ của thực tế đầu tiên

193
00:08:17,880 --> 00:08:19,480
nút trong danh sách này.

194
00:08:19,480 --> 00:08:22,120
Vì vậy, tôi đã thực hiện nó là một toàn cầu
bởi vì, như bạn sẽ thấy, tất cả điều này

195
00:08:22,120 --> 00:08:25,310
chương trình nào trong cuộc sống là thực hiện
một danh sách liên kết cho tôi.

196
00:08:25,310 --> 00:08:27,050
>> Bây giờ tôi đã có một vài nguyên mẫu đây.

197
00:08:27,050 --> 00:08:31,190
Tôi quyết định thực hiện các tính năng như
xóa, chèn, tìm kiếm, và

198
00:08:31,190 --> 00:08:31,740
traversal -

199
00:08:31,740 --> 00:08:35,210
chỉ là đi bộ cuối cùng trên
danh sách, in ra thành phần của nó.

200
00:08:35,210 --> 00:08:36,750
Và giờ đây là chính thường xuyên của tôi.

201
00:08:36,750 --> 00:08:39,890
Và chúng tôi sẽ không dành quá nhiều thời gian trên
những vì đây là loại, hy vọng

202
00:08:39,890 --> 00:08:41,780
quá cũ rồi.

203
00:08:41,780 --> 00:08:45,370
>> Tôi sẽ làm như sau,
trong khi người sử dụng hợp tác.

204
00:08:45,370 --> 00:08:47,300
Vì vậy, một, tôi sẽ in
ra khỏi trình đơn này.

205
00:08:47,300 --> 00:08:49,420
Và tôi đã định dạng nó như
sạch như tôi có thể.

206
00:08:49,420 --> 00:08:52,240
Nếu loại người sử dụng trong một, có nghĩa là
họ muốn xóa một cái gì đó.

207
00:08:52,240 --> 00:08:54,560
Nếu loại người sử dụng trong hai, có nghĩa là
họ muốn chèn một cái gì đó.

208
00:08:54,560 --> 00:08:55,930
Và vv.

209
00:08:55,930 --> 00:08:58,270
Tôi sẽ sau đó nhắc nhở
sau đó cho một lệnh.

210
00:08:58,270 --> 00:08:59,300
Và sau đó tôi sẽ sử dụng getInt.

211
00:08:59,300 --> 00:09:02,790
>> Vì vậy, đây là một menuing thực sự đơn giản
giao diện mà bạn chỉ cần gõ

212
00:09:02,790 --> 00:09:05,270
một bản đồ số một
những lệnh trên.

213
00:09:05,270 --> 00:09:08,730
Và bây giờ tôi có một chuyển đổi sạch đẹp
tuyên bố rằng sẽ bật

214
00:09:08,730 --> 00:09:10,090
bất cứ điều gì người dùng gõ vào

215
00:09:10,090 --> 00:09:12,180
Và nếu họ đánh máy một, tôi sẽ
gọi xóa và phá vỡ.

216
00:09:12,180 --> 00:09:14,380
Nếu họ đánh máy hai, tôi sẽ
gọi chèn và phá vỡ.

217
00:09:14,380 --> 00:09:16,490
>> Và bây giờ thông báo tôi đã đưa từng
trong số này trên cùng một dòng.

218
00:09:16,490 --> 00:09:18,360
Đây chỉ là một quyết định phong cách.

219
00:09:18,360 --> 00:09:20,210
Thông thường, chúng tôi đã nhìn thấy một cái gì đó
như thế này.

220
00:09:20,210 --> 00:09:23,260
Nhưng tôi chỉ quyết định, thẳng thắn, chương trình của tôi
nhìn dễ đọc hơn vì

221
00:09:23,260 --> 00:09:25,980
đó là chỉ có bốn trường hợp để
chỉ liệt kê nó như thế này.

222
00:09:25,980 --> 00:09:28,360
Sử dụng hoàn toàn hợp pháp của phong cách.

223
00:09:28,360 --> 00:09:31,480
Và tôi sẽ làm điều này miễn là
người sử dụng đã không đánh số không, mà tôi

224
00:09:31,480 --> 00:09:33,910
quyết định sẽ có nghĩa là họ muốn bỏ thuốc lá.

225
00:09:33,910 --> 00:09:36,630
>> Vì vậy, bây giờ nhận thấy những gì tôi
sẽ làm gì đây.

226
00:09:36,630 --> 00:09:38,650
Tôi sẽ giải phóng danh sách rõ ràng.

227
00:09:38,650 --> 00:09:40,230
Nhưng thêm vào đó trong một lúc.

228
00:09:40,230 --> 00:09:41,640
Trước tiên hãy chạy chương trình này.

229
00:09:41,640 --> 00:09:45,250
Vì vậy, hãy để tôi làm một thiết bị đầu cuối lớn hơn
cửa sổ, dấu chấm dấu gạch chéo danh sách 0.

230
00:09:45,250 --> 00:09:49,510
Tôi sẽ đi trước và chèn bằng
gõ hai, một số như 50, và bây giờ

231
00:09:49,510 --> 00:09:51,590
bạn sẽ thấy danh sách hiện nay là 50.

232
00:09:51,590 --> 00:09:53,380
Và văn bản của tôi chỉ cuộn lên một chút.

233
00:09:53,380 --> 00:09:55,940
Vì vậy, bây giờ nhận thấy danh sách có chứa
số 50.

234
00:09:55,940 --> 00:09:58,220
>> Chúng ta hãy làm chèn khác bằng cách lấy hai.

235
00:09:58,220 --> 00:10:01,630
Chúng ta hãy nhập vào các số như một.

236
00:10:01,630 --> 00:10:03,940
Danh sách hiện nay là một, tiếp theo là 50.

237
00:10:03,940 --> 00:10:06,020
Vì vậy, đây chỉ là một đại diện văn bản
danh sách.

238
00:10:06,020 --> 00:10:10,550
Và chúng ta hãy chèn thêm một số như
số 42, đó là hy vọng

239
00:10:10,550 --> 00:10:14,620
sẽ kết thúc ở giữa, bởi vì
chương trình này trong các loại đặc biệt nó

240
00:10:14,620 --> 00:10:16,320
các yếu tố như nó chèn chúng.

241
00:10:16,320 --> 00:10:17,220
Vì vậy, chúng tôi đã có nó.

242
00:10:17,220 --> 00:10:20,730
Chương trình siêu đơn giản mà có thể
hoàn toàn đã sử dụng một mảng, nhưng tôi

243
00:10:20,730 --> 00:10:23,280
xảy ra để được sử dụng một danh sách liên kết
chỉ để tôi có thể tự động

244
00:10:23,280 --> 00:10:24,610
phát triển và thu nhỏ nó.

245
00:10:24,610 --> 00:10:28,470
>> Vì vậy, chúng ta hãy có một cái nhìn cho tìm kiếm, nếu tôi
chạy lệnh ba, tôi muốn tìm kiếm

246
00:10:28,470 --> 00:10:31,040
cho, nói, số 43.

247
00:10:31,040 --> 00:10:34,190
Và không có gì rõ ràng được tìm thấy,
bởi vì tôi đã trở lại không có phản ứng.

248
00:10:34,190 --> 00:10:35,010
Vì vậy, chúng ta hãy làm điều này một lần nữa.

249
00:10:35,010 --> 00:10:35,690
Tìm kiếm.

250
00:10:35,690 --> 00:10:39,520
Chúng ta hãy tìm kiếm cho 50, hay đúng hơn là tìm kiếm
42, trong đó có một tốt đẹp

251
00:10:39,520 --> 00:10:40,850
ít có ý nghĩa tinh tế.

252
00:10:40,850 --> 00:10:42,610
Và tôi tìm thấy ý nghĩa của cuộc sống nơi đây.

253
00:10:42,610 --> 00:10:44,990
Số 42, nếu bạn không biết
tài liệu tham khảo, Google nó.

254
00:10:44,990 --> 00:10:45,350
Được rồi.

255
00:10:45,350 --> 00:10:47,130
Vì vậy, những gì đã thực hiện chương trình này cho tôi?

256
00:10:47,130 --> 00:10:50,660
Nó chỉ cho phép tôi để chèn như vậy
xa và tìm kiếm các yếu tố.

257
00:10:50,660 --> 00:10:53,650
>> Hãy nhanh về phía trước, sau đó, để
có chức năng chúng tôi liếc nhìn

258
00:10:53,650 --> 00:10:55,360
vào thứ hai như một lời trêu ghẹo.

259
00:10:55,360 --> 00:10:59,620
Vì vậy, chức năng này, tôi khẳng định, tìm kiếm
một phần tử trong danh sách bằng cách đầu tiên

260
00:10:59,620 --> 00:11:03,830
một, khiến người sử dụng và sau đó gọi
GetInt để có được một int thực tế

261
00:11:03,830 --> 00:11:05,060
mà bạn muốn tìm kiếm.

262
00:11:05,060 --> 00:11:06,460
>> Sau đó, thông báo này.

263
00:11:06,460 --> 00:11:10,690
Tôi sẽ tạo một biến tạm thời
trong dòng 188 được gọi là con trỏ -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
có thể gọi nó là bất cứ điều gì.

266
00:11:12,440 --> 00:11:16,140
Và đó là một con trỏ đến một nút
bởi vì tôi đã nói nút * có.

267
00:11:16,140 --> 00:11:19,900
Và tôi khởi tạo nó để bằng
đầu tiên để tôi có hiệu quả của tôi

268
00:11:19,900 --> 00:11:22,860
ngón tay, có thể nói, trên rất
Yếu tố đầu tiên của danh sách.

269
00:11:22,860 --> 00:11:27,460
Vì vậy, nếu bàn tay phải của tôi ở đây là PTR tôi
chỉ vào cùng một điều rằng đầu tiên

270
00:11:27,460 --> 00:11:28,670
được chỉ vào.

271
00:11:28,670 --> 00:11:31,430
>> Vì vậy, bây giờ trở lại trong mã,
những gì xảy ra tiếp theo -

272
00:11:31,430 --> 00:11:35,070
đây là một mô hình phổ biến khi lặp lại
trên một cấu trúc như một

273
00:11:35,070 --> 00:11:35,970
danh sách liên kết.

274
00:11:35,970 --> 00:11:40,410
Tôi sẽ làm như sau trong khi
con trỏ không phải là bằng vô giá trị Vì vậy, trong khi

275
00:11:40,410 --> 00:11:47,530
ngón tay của tôi là không chỉ tại một số rỗng
giá trị, nếu con trỏ mũi tên n bằng n.

276
00:11:47,530 --> 00:11:52,290
Chúng ta sẽ nhận thấy đầu tiên đó n là những gì
người sử dụng gõ vào mỗi GetInts gọi đây.

277
00:11:52,290 --> 00:11:54,280
>> Và con trỏ mũi tên n có nghĩa là gì?

278
00:11:54,280 --> 00:11:59,020
Vâng, nếu chúng ta quay trở lại với hình ảnh ở đây,
nếu tôi có một ngón tay chỉ vào

279
00:11:59,020 --> 00:12:02,960
là nút đầu tiên có chứa chín, các
mũi tên về cơ bản có nghĩa là đi đến đó

280
00:12:02,960 --> 00:12:08,860
nút và lấy giá trị ở vị trí n,
trong trường hợp này, các lĩnh vực dữ liệu được gọi là n.

281
00:12:08,860 --> 00:12:14,120
>> Như một sang một bên - và chúng ta đã thấy điều này một vài
tuần trước khi có ai đó hỏi -

282
00:12:14,120 --> 00:12:18,840
cú pháp này là mới, nhưng nó không
cung cấp cho chúng tôi sức mạnh mà chúng ta

283
00:12:18,840 --> 00:12:20,040
không đã có.

284
00:12:20,040 --> 00:12:25,325
Cụm từ này tương đương với việc sử dụng là những gì
ký hiệu dấu chấm và một vài ngôi sao

285
00:12:25,325 --> 00:12:29,490
tuần trước khi chúng tôi bóc vỏ trở lại
lớp này một chút quá sớm?

286
00:12:29,490 --> 00:12:31,780
>> HỌC SINH: [nghe được].

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: Chính xác, đó là ngôi sao, và
sau đó nó là ngôi sao chấm n, với

288
00:12:38,880 --> 00:12:41,930
ngoặc đơn ở đây, mà trông,
thẳng thắn, tôi nghĩ rằng rất nhiều

289
00:12:41,930 --> 00:12:43,320
khó hiểu hơn để đọc.

290
00:12:43,320 --> 00:12:46,270
Nhưng sao con trỏ, như mọi khi,
phương tiện đi đó.

291
00:12:46,270 --> 00:12:49,090
Và một khi bạn đang ở đó, những dữ liệu
lĩnh vực bạn muốn truy cập?

292
00:12:49,090 --> 00:12:52,730
Vâng, bạn sử dụng các ký hiệu dấu chấm để truy cập
một trường dữ liệu cấu trúc, và tôi

293
00:12:52,730 --> 00:12:54,140
đặc biệt muốn n.

294
00:12:54,140 --> 00:12:56,240
>> Thành thật mà nói, tôi sẽ tranh luận này
chỉ là khó khăn hơn để đọc.

295
00:12:56,240 --> 00:12:58,080
Nó khó hơn để nhớ nơi
làm các dấu ngoặc đơn đi,

296
00:12:58,080 --> 00:12:59,030
ngôi sao và tất cả điều đó.

297
00:12:59,030 --> 00:13:02,150
Vì vậy, thế giới đã thông qua một số cú pháp
đường, vậy để nói chuyện.

298
00:13:02,150 --> 00:13:04,740
Chỉ là một cách gợi cảm của nói,
này là tương đương, và

299
00:13:04,740 --> 00:13:05,970
có lẽ trực quan hơn.

300
00:13:05,970 --> 00:13:09,600
Nếu con trỏ thực sự là một con trỏ,
mũi tên ký hiệu phương tiện đến đó và tìm thấy

301
00:13:09,600 --> 00:13:11,890
lĩnh vực trong trường hợp này được gọi là n.

302
00:13:11,890 --> 00:13:13,660
>> Vì vậy, nếu tôi tìm thấy nó, nhận thấy những gì tôi làm.

303
00:13:13,660 --> 00:13:17,430
Tôi chỉ đơn giản là in ra, tôi thấy phần trăm tôi,
cắm vào giá trị cho int đó.

304
00:13:17,430 --> 00:13:20,730
Tôi gọi ngủ trong một giây chỉ để loại
tạm dừng mọi thứ trên màn hình để

305
00:13:20,730 --> 00:13:22,900
cung cấp cho người dùng một giây để hấp thụ
những gì vừa xảy ra.

306
00:13:22,900 --> 00:13:24,290
Và sau đó tôi phá vỡ.

307
00:13:24,290 --> 00:13:26,330
Nếu không, tôi phải làm gì?

308
00:13:26,330 --> 00:13:30,960
Tôi cập nhật con trỏ đến bằng
con trỏ mũi tên bên cạnh.

309
00:13:30,960 --> 00:13:35,840
>> Vì vậy, chỉ cần được rõ ràng, điều này có nghĩa là đi
ở đó, sử dụng ký hiệu trường học cũ của tôi.

310
00:13:35,840 --> 00:13:39,580
Vì vậy, điều này chỉ có nghĩa là để đi đến bất cứ điều gì
bạn đang chỉ tay vào, mà trong rất

311
00:13:39,580 --> 00:13:43,660
Trường hợp đầu tiên là tôi chỉ vào
các cấu trúc với chín trong nó.

312
00:13:43,660 --> 00:13:44,510
Vì vậy, tôi đã đi ở đó.

313
00:13:44,510 --> 00:13:47,880
Và sau đó là ký hiệu dấu chấm có nghĩa là,
nhận được giá trị ở bên cạnh.

314
00:13:47,880 --> 00:13:50,470
>> Nhưng giá trị, mặc dù nó rút ra
như một thu hẹp, chỉ là một số.

315
00:13:50,470 --> 00:13:51,720
Đó là một địa chỉ số.

316
00:13:51,720 --> 00:13:55,670
Vì vậy, đây là một dòng mã, cho dù
viết như thế này, khó hiểu hơn

317
00:13:55,670 --> 00:14:00,190
cách, hoặc như thế này, nhiều hơn một chút
cách trực quan, chỉ có nghĩa là di chuyển bàn tay của tôi

318
00:14:00,190 --> 00:14:03,460
từ nút đầu tiên kế tiếp,
và sau đó tiếp theo, và sau đó

319
00:14:03,460 --> 00:14:05,320
kế tiếp, và vv.

320
00:14:05,320 --> 00:14:09,920
>> Vì vậy, chúng tôi không quan tâm tới người khác
triển khai các chèn và xóa

321
00:14:09,920 --> 00:14:14,030
và theo cây, hai đầu tiên của
mà là khá liên quan.

322
00:14:14,030 --> 00:14:17,010
Và tôi nghĩ rằng nó khá dễ dàng để có được
bị mất khi thực hiện nó bằng lời nói.

323
00:14:17,010 --> 00:14:19,890
Nhưng những gì chúng ta có thể làm ở đây là
cố gắng xác định như thế nào

324
00:14:19,890 --> 00:14:21,640
tốt nhất để làm điều này trực quan.

325
00:14:21,640 --> 00:14:24,800
Bởi vì tôi sẽ đề xuất rằng nếu chúng ta
muốn chèn vào các yếu tố này

326
00:14:24,800 --> 00:14:26,680
danh sách hiện có, mà
có năm yếu tố -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, và 33 -

328
00:14:29,530 --> 00:14:33,300
nếu tôi được là sẽ thực hiện điều này trong
mã, tôi cần phải xem xét làm thế nào để đi

329
00:14:33,300 --> 00:14:34,160
về việc này.

330
00:14:34,160 --> 00:14:37,720
>> Và tôi sẽ đề xuất thực hiện các bước bé
theo đó, trong trường hợp này tôi có nghĩa là, những gì đang có

331
00:14:37,720 --> 00:14:41,090
các kịch bản có thể là chúng tôi
có thể gặp ở chung?

332
00:14:41,090 --> 00:14:44,120
Khi thực hiện chèn một liên kết
danh sách, điều này chỉ xảy ra là một

333
00:14:44,120 --> 00:14:46,090
ví dụ cụ thể về kích thước năm.

334
00:14:46,090 --> 00:14:50,420
Vâng, nếu bạn muốn chèn một số,
thích nói số một, và

335
00:14:50,420 --> 00:14:53,380
giữ gìn trật tự sắp xếp, nơi
rõ ràng là không số một cần phải

336
00:14:53,380 --> 00:14:55,686
đi trong ví dụ cụ thể này?

337
00:14:55,686 --> 00:14:56,840
Giống như lúc đầu.

338
00:14:56,840 --> 00:15:00,030
>> Nhưng điều thú vị đó là
nếu bạn muốn chèn một thành này

339
00:15:00,030 --> 00:15:04,100
danh sách, những gì đặc biệt con trỏ cần
được cập nhật rõ ràng?

340
00:15:04,100 --> 00:15:04,610
Đầu tiên.

341
00:15:04,610 --> 00:15:07,830
Vì vậy, tôi sẽ tranh luận, đây là trường hợp đầu tiên
chúng ta có thể muốn xem xét, một

342
00:15:07,830 --> 00:15:11,140
kịch bản liên quan đến chèn vào
đầu danh sách.

343
00:15:11,140 --> 00:15:15,400
>> Hãy nhổ ra có thể là một dễ dàng hoặc thậm chí
trường hợp dễ dàng hơn, tương đối nói.

344
00:15:15,400 --> 00:15:18,110
Giả sử tôi muốn chèn
số 35 trong thứ tự sắp xếp.

345
00:15:18,110 --> 00:15:20,600
Nó rõ ràng là thuộc ở đó.

346
00:15:20,600 --> 00:15:25,320
Vì vậy, những gì con trỏ rõ ràng là sẽ
phải được cập nhật trong kịch bản đó?

347
00:15:25,320 --> 00:15:30,060
Con trỏ 34 của không trở thành vô giá trị
nhưng địa chỉ của cấu trúc

348
00:15:30,060 --> 00:15:31,800
chứa số 35.

349
00:15:31,800 --> 00:15:32,750
Vì vậy, đó là trường hợp hai.

350
00:15:32,750 --> 00:15:36,190
Như vậy, tôi đang sắp xếp của lượng tử hóa
bao nhiêu công việc tôi phải làm ở đây.

351
00:15:36,190 --> 00:15:39,880
>> Và cuối cùng, trường hợp giữa rõ ràng là
thực sự, ở giữa, nếu tôi muốn

352
00:15:39,880 --> 00:15:45,870
chèn một cái gì đó như nói 23, mà đi
giữa 23 và 26, nhưng

353
00:15:45,870 --> 00:15:48,680
bây giờ mọi thứ có được nhiều hơn một chút
tham gia bởi vì những gì

354
00:15:48,680 --> 00:15:52,800
con trỏ cần phải được thay đổi?

355
00:15:52,800 --> 00:15:56,680
Vì vậy, 22 rõ ràng là cần phải thay đổi
bởi vì anh ta không thể chỉ ra 26 nữa.

356
00:15:56,680 --> 00:16:00,320
Anh ta cần để trỏ đến các nút mới
Tôi sẽ phải phân bổ bằng cách gọi

357
00:16:00,320 --> 00:16:01,770
malloc hoặc một số tương đương.

358
00:16:01,770 --> 00:16:05,990
>> Nhưng sau đó tôi cũng cần có nút mới, 23
trong trường hợp này, để có con trỏ của nó

359
00:16:05,990 --> 00:16:07,870
chỉ vào ai?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
Và có sẽ là một
thứ tự của các hoạt động ở đây.

362
00:16:10,380 --> 00:16:13,410
Bởi vì nếu tôi làm điều này một cách ngu ngốc, và tôi
Ví dụ bắt đầu vào đầu

363
00:16:13,410 --> 00:16:16,040
danh sách, và mục tiêu của tôi là để chèn 23.

364
00:16:16,040 --> 00:16:18,610
Và tôi kiểm tra, hiện nó thuộc về
ở đây, gần chín?

365
00:16:18,610 --> 00:16:18,950
Không.

366
00:16:18,950 --> 00:16:20,670
Nó thuộc về nơi này, bên cạnh 17?

367
00:16:20,670 --> 00:16:20,940
Không.

368
00:16:20,940 --> 00:16:22,530
Liệu nó thuộc về đây bên cạnh 22?

369
00:16:22,530 --> 00:16:23,300
Vâng.

370
00:16:23,300 --> 00:16:26,400
>> Bây giờ nếu tôi là ngu ngốc ở đây, và không
suy nghĩ này thông qua, tôi có thể

371
00:16:26,400 --> 00:16:28,320
bố trí nút mới trong 23.

372
00:16:28,320 --> 00:16:32,080
Tôi có thể cập nhật con trỏ từ
nút được gọi là 22, chỉ

373
00:16:32,080 --> 00:16:33,080
nó tại nút mới.

374
00:16:33,080 --> 00:16:36,140
Và sau đó làm những gì tôi phải cập nhật
con trỏ nút mới được?

375
00:16:36,140 --> 00:16:38,120
>> HỌC SINH: [nghe được].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: Chính xác.

377
00:16:38,385 --> 00:16:39,710
Chỉ ở mức 26.

378
00:16:39,710 --> 00:16:45,590
Nhưng Chết tiệt nếu tôi chưa cập nhật
22 con trỏ để chỉ vào anh chàng này, và

379
00:16:45,590 --> 00:16:48,260
bây giờ tôi có trẻ em mồ côi, phần còn lại
danh sách, vậy để nói chuyện.

380
00:16:48,260 --> 00:16:52,140
Vì vậy, để hoạt động ở đây
sẽ là quan trọng.

381
00:16:52,140 --> 00:16:55,100
>> Để làm điều này tôi có thể ăn cắp,
nói, sáu người tình nguyện.

382
00:16:55,100 --> 00:16:57,650
Và chúng ta hãy xem nếu chúng ta không thể làm điều này
trực quan thay vì mã khôn ngoan.

383
00:16:57,650 --> 00:16:59,330
Và chúng tôi có một số căng thẳng đáng yêu
quả bóng cho bạn ngày hôm nay.

384
00:16:59,330 --> 00:17:02,510
OK, làm thế nào về một, hai, trong
trở lại - ngày kết thúc ở đó.

385
00:17:02,510 --> 00:17:04,530
ba, bốn, cả hai bạn
kẻ trên cùng.

386
00:17:04,530 --> 00:17:05,579
Và năm, sáu.

387
00:17:05,579 --> 00:17:05,839
Chắc chắn.

388
00:17:05,839 --> 00:17:06,450
Năm và sáu.

389
00:17:06,450 --> 00:17:08,390
Tất cả các bên phải và chúng tôi sẽ đến
đến với bạn lần sau.

390
00:17:08,390 --> 00:17:09,640
Tất cả các bên phải, đi lên trên.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Được rồi, kể từ khi bạn đang lên đây lần đầu tiên,
bạn muốn trở thành một trong những lúng túng

393
00:17:14,819 --> 00:17:16,119
trong Google Glass đây?

394
00:17:16,119 --> 00:17:19,075
Được rồi, vì vậy, OK, Thủy tinh,
quay video.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK, bạn tốt để đi.

397
00:17:24,589 --> 00:17:27,950
>> Được rồi, vì vậy nếu các bạn có thể đi qua
ở đây, tôi đã chuẩn bị trước

398
00:17:27,950 --> 00:17:30,110
một số con số.

399
00:17:30,110 --> 00:17:31,240
Được rồi, đi trên trên đây.

400
00:17:31,240 --> 00:17:33,440
Và tại sao bạn không đi một chút
tiếp tục như vậy.

401
00:17:33,440 --> 00:17:35,520
Và chúng ta hãy xem, tên của bạn là gì,
với kính Google?

402
00:17:35,520 --> 00:17:35,910
>> HỌC SINH: Ben.

403
00:17:35,910 --> 00:17:36,230
>> SPEAKER 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, bạn sẽ là người đầu tiên, theo nghĩa đen.

405
00:17:38,380 --> 00:17:40,580
Vì vậy, chúng tôi sẽ gửi cho bạn
đến cuối giai đoạn.

406
00:17:40,580 --> 00:17:41,670
Tất cả các bên phải, và tên của bạn?

407
00:17:41,670 --> 00:17:41,990
>> HỌC SINH: Jason.

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1: Jason, OK bạn sẽ
là số chín.

409
00:17:44,530 --> 00:17:46,700
Vì vậy, nếu bạn muốn theo Ben như vậy.

410
00:17:46,700 --> 00:17:47,010
>> HỌC SINH: Jill.

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: Jill, bạn sẽ được
17, mà nếu tôi đã làm điều này nhiều hơn

412
00:17:49,630 --> 00:17:51,260
thông minh, tôi sẽ có
bắt đầu ở đầu kia.

413
00:17:51,260 --> 00:17:52,370
Bạn đi theo cách đó.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
Và bạn?

416
00:17:53,670 --> 00:17:53,980
>> HỌC SINH: Mary.

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1: Mary, bạn sẽ có 22.

418
00:17:56,130 --> 00:17:58,420
Và tên của bạn là?

419
00:17:58,420 --> 00:17:58,810
>> HỌC SINH: Chris.

420
00:17:58,810 --> 00:18:00,100
>> SPEAKER 1: Chris, bạn sẽ có 26.

421
00:18:00,100 --> 00:18:00,740
Và sau đó cuối cùng.

422
00:18:00,740 --> 00:18:01,400
>> HỌC SINH: Diana.

423
00:18:01,400 --> 00:18:02,670
>> SPEAKER 1: Diana, bạn sẽ có 34.

424
00:18:02,670 --> 00:18:03,920
Vì vậy, bạn đi trên trên đây.

425
00:18:03,920 --> 00:18:06,360
>> Được rồi, vì vậy hoàn thiện sắp xếp
đặt hàng rồi.

426
00:18:06,360 --> 00:18:09,600
Và chúng ta hãy đi trước và làm điều này
để chúng ta có thể thực sự -

427
00:18:09,600 --> 00:18:11,720
Ben bạn chỉ cần loại tìm kiếm
ra vào không nơi nào có.

428
00:18:11,720 --> 00:18:15,670
OK, vì vậy chúng ta hãy đi trước và mô tả này
sử dụng vũ khí, giống như tôi, chính xác,

429
00:18:15,670 --> 00:18:16,250
những gì đang xảy ra.

430
00:18:16,250 --> 00:18:19,540
Vì vậy, đi trước và cho mình một
hoặc giữa hai chân mình.

431
00:18:19,540 --> 00:18:22,900
Và đi trước và chỉ bằng một tay để
bất cứ ai bạn nên chỉ vào

432
00:18:22,900 --> 00:18:23,470
trên cơ sở này.

433
00:18:23,470 --> 00:18:25,890
Và nếu bạn là vô giá trị chỉ điểm
thẳng xuống sàn nhà.

434
00:18:25,890 --> 00:18:27,690
OK, vì vậy tốt.

435
00:18:27,690 --> 00:18:32,290
>> Vì vậy, bây giờ chúng tôi có một danh sách liên kết, và cho tôi
đề xuất rằng tôi sẽ đóng vai trò của

436
00:18:32,290 --> 00:18:35,110
PTR, vì vậy tôi sẽ không bận tâm
thực hiện điều này xung quanh.

437
00:18:35,110 --> 00:18:37,830
Và sau đó - một người nào đó ước ngu ngốc -
bạn có thể gọi bất cứ điều gì bạn muốn này -

438
00:18:37,830 --> 00:18:39,800
con trỏ trước, con trỏ pred -

439
00:18:39,800 --> 00:18:43,930
nó chỉ là biệt danh chúng tôi đã cung cấp trong
mẫu mã của chúng tôi để tay trái của tôi.

440
00:18:43,930 --> 00:18:47,240
Mặt khác đó sẽ được giữ
theo dõi của những người trong người

441
00:18:47,240 --> 00:18:48,400
theo kịch bản.

442
00:18:48,400 --> 00:18:52,390
>> Vì vậy, giả sử, lần đầu tiên, tôi muốn nhổ ra
là ví dụ đầu tiên của chèn, nói

443
00:18:52,390 --> 00:18:54,330
20, vào danh sách.

444
00:18:54,330 --> 00:18:57,160
Vì vậy, tôi sẽ cần một người nào đó
là hiện thân của số 20 cho chúng ta.

445
00:18:57,160 --> 00:18:58,950
Vì vậy, tôi cần một người nào đó malloc
từ khán giả.

446
00:18:58,950 --> 00:18:59,380
Lên đây.

447
00:18:59,380 --> 00:19:00,340
Tên của bạn là gì?

448
00:19:00,340 --> 00:19:01,300
>> HỌC SINH: Brian.

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: Brian, tất cả các bên phải, vì vậy bạn
sẽ là nút chứa 20.

450
00:19:05,270 --> 00:19:06,810
Được rồi, đi trên trên đây.

451
00:19:06,810 --> 00:19:10,025
Và rõ ràng, nơi
Brian không thuộc về ai?

452
00:19:10,025 --> 00:19:12,190
Vì vậy, ở giữa - trên thực tế,
chờ một phút.

453
00:19:12,190 --> 00:19:13,420
Chúng tôi đang làm điều này trong trật tự.

454
00:19:13,420 --> 00:19:17,170
Chúng tôi đang làm điều này khó khăn hơn rất nhiều
hơn nó cần phải được lần đầu tiên.

455
00:19:17,170 --> 00:19:21,210
OK, chúng ta sẽ tự do Brian
và realloc Brian như năm.

456
00:19:21,210 --> 00:19:23,680
>> OK, vì vậy bây giờ chúng tôi muốn chèn
Brian là năm.

457
00:19:23,680 --> 00:19:25,960
Vì vậy, đến trên hơn ở đây bên cạnh
Ben chỉ là một thời điểm.

458
00:19:25,960 --> 00:19:28,250
Và bạn có lẽ có thể nói
nơi mà câu chuyện này đang xảy ra.

459
00:19:28,250 --> 00:19:30,500
Nhưng chúng ta hãy suy nghĩ cẩn thận về
thứ tự của các hoạt động.

460
00:19:30,500 --> 00:19:32,880
Và đó là chính xác hình ảnh này
đó là sẽ xếp hàng

461
00:19:32,880 --> 00:19:34,080
với mẫu mã.

462
00:19:34,080 --> 00:19:40,120
Vì vậy, ở đây tôi đã PTR chỉ ban đầu
không ở Bến, cho mỗi gia nhập, nhưng tại bất cứ điều gì

463
00:19:40,120 --> 00:19:43,245
đánh giá cao ông có, mà trong trường hợp này
là - tên của bạn là gì nữa?

464
00:19:43,245 --> 00:19:43,670
>> HỌC SINH: Jason.

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1: Jason, vì vậy cả hai Ben và tôi
Jason chỉ vào tại thời điểm này.

466
00:19:47,350 --> 00:19:49,700
Vì vậy, bây giờ tôi phải xác định,
nơi không thuộc về Brian?

467
00:19:49,700 --> 00:19:53,500
Vì vậy, điều duy nhất tôi có thể truy cập
ngay bây giờ là mục dữ liệu n của mình.

468
00:19:53,500 --> 00:19:58,280
Vì vậy, tôi sẽ kiểm tra, được
Brian ít hơn Jason?

469
00:19:58,280 --> 00:19:59,770
Câu trả lời là đúng.

470
00:19:59,770 --> 00:20:03,680
>> Vì vậy, những gì bây giờ cần phải xảy ra,
theo thứ tự đúng?

471
00:20:03,680 --> 00:20:07,120
Tôi cần phải cập nhật bao nhiêu con trỏ
trong tổng số trong câu chuyện này?

472
00:20:07,120 --> 00:20:10,720
Nơi tay của tôi vẫn còn chỉ vào
Jason, và bàn tay của bạn - nếu bạn muốn

473
00:20:10,720 --> 00:20:12,930
đặt bàn tay của bạn như thế nào, loại, tôi
không biết, một dấu hỏi.

474
00:20:12,930 --> 00:20:14,070
OK, tốt.

475
00:20:14,070 --> 00:20:15,670
>> Được rồi, vì vậy bạn có
một vài ứng cử viên.

476
00:20:15,670 --> 00:20:20,500
Hoặc Bến hoặc tôi hoặc Brian hoặc Jason
hoặc những người khác, mà

477
00:20:20,500 --> 00:20:21,370
con trỏ cần phải thay đổi?

478
00:20:21,370 --> 00:20:23,260
Bao nhiêu trong tổng số?

479
00:20:23,260 --> 00:20:24,080
>> OK, vì vậy hai.

480
00:20:24,080 --> 00:20:27,090
Con trỏ của tôi không thực sự quan trọng nữa
bởi vì tôi chỉ là tạm thời.

481
00:20:27,090 --> 00:20:31,370
Vì vậy, nó là hai chàng trai, có lẽ,
cả Ben và Brian.

482
00:20:31,370 --> 00:20:34,410
Vì vậy, hãy để tôi đề xuất rằng chúng tôi cập nhật
Ben, kể từ khi ông đầu tiên.

483
00:20:34,410 --> 00:20:36,350
Yếu tố đầu tiên của danh sách này
bây giờ sẽ là Brian.

484
00:20:36,350 --> 00:20:38,070
Vì vậy, Bến điểm tại Brian.

485
00:20:38,070 --> 00:20:39,320
OK, bây giờ những gì?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Người được chỉ vào ai?

488
00:20:43,460 --> 00:20:44,710
>> HỌC SINH: [nghe được].

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: OK để Brian có
điểm tại Jason.

490
00:20:46,180 --> 00:20:48,360
Nhưng tôi đã mất liên lạc với con trỏ?

491
00:20:48,360 --> 00:20:49,980
Tôi biết Jason là?

492
00:20:49,980 --> 00:20:50,790
>> HỌC SINH: [nghe được].

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1: tôi làm, vì tôi
con trỏ tạm thời.

494
00:20:52,620 --> 00:20:55,110
Và có lẽ, tôi đã không thay đổi
chỉ tại nút mới.

495
00:20:55,110 --> 00:20:58,300
Vì vậy, chúng tôi chỉ đơn giản là có thể có điểm Brian
ở bất cứ ai tôi chỉ vào.

496
00:20:58,300 --> 00:20:59,000
Và chúng tôi đang thực hiện.

497
00:20:59,000 --> 00:21:01,890
Vì vậy, trường hợp một, chèn vào
đầu danh sách.

498
00:21:01,890 --> 00:21:02,950
Có hai bước chính.

499
00:21:02,950 --> 00:21:06,750
Một, chúng ta phải cập nhật Ben, và sau đó
chúng tôi cũng có để cập nhật Brian.

500
00:21:06,750 --> 00:21:09,230
Và sau đó tôi không phải bận tâm
traipsing thông qua phần còn lại của

501
00:21:09,230 --> 00:21:12,680
danh sách, bởi vì chúng tôi đã tìm thấy mình
vị trí, bởi vì anh ta thuộc về

502
00:21:12,680 --> 00:21:14,080
bên trái của phần tử đầu tiên.

503
00:21:14,080 --> 00:21:15,400
>> Được rồi, vì vậy khá dễ dàng.

504
00:21:15,400 --> 00:21:18,110
Trong thực tế, cảm thấy như chúng tôi hầu như
làm này quá phức tạp.

505
00:21:18,110 --> 00:21:20,240
Vì vậy, bây giờ chúng ta nhổ ra cuối cùng
danh sách, và nhìn thấy nơi

506
00:21:20,240 --> 00:21:21,380
sự phức tạp bắt đầu.

507
00:21:21,380 --> 00:21:24,560
Vì vậy, nếu bây giờ, tôi alloc từ khán giả.

508
00:21:24,560 --> 00:21:25,540
Bất cứ ai muốn chơi 55?

509
00:21:25,540 --> 00:21:26,700
Được rồi, tôi thấy bàn tay của bạn đầu tiên.

510
00:21:26,700 --> 00:21:29,620
Lên đây.

511
00:21:29,620 --> 00:21:30,030
Vâng.

512
00:21:30,030 --> 00:21:31,177
Tên của bạn là gì?

513
00:21:31,177 --> 00:21:32,310
>> HỌC SINH: [nghe được].

514
00:21:32,310 --> 00:21:33,240
>> SPEAKER 1: Habata.

515
00:21:33,240 --> 00:21:33,890
OK, đi lên trên.

516
00:21:33,890 --> 00:21:35,730
Bạn sẽ có số 55.

517
00:21:35,730 --> 00:21:37,820
Vì vậy, bạn, tất nhiên, thuộc về
ở cuối danh sách.

518
00:21:37,820 --> 00:21:41,850
Vì vậy, chúng ta hãy xem lại các mô phỏng với tôi
là PTR cho chỉ là một thời điểm.

519
00:21:41,850 --> 00:21:44,050
Vì vậy, tôi đầu tiên sẽ chỉ vào
bất cứ điều gì Ben đã chỉ tay vào.

520
00:21:44,050 --> 00:21:45,900
Chúng tôi cả hai chỉ tại Brian.

521
00:21:45,900 --> 00:21:48,420
Vì vậy, 55 không phải là ít hơn năm.

522
00:21:48,420 --> 00:21:52,510
Vì vậy, tôi sẽ cập nhật bản thân mình bằng
trỏ đến con trỏ tiếp theo của Brian, người

523
00:21:52,510 --> 00:21:54,450
bây giờ tất nhiên là Jason.

524
00:21:54,450 --> 00:21:57,310
55 không phải là ít hơn chín, vì vậy
Tôi sẽ cập nhật PTR.

525
00:21:57,310 --> 00:21:58,890
Tôi sẽ cập nhật PTR.

526
00:21:58,890 --> 00:22:02,290
Tôi sẽ cập nhật PTR
Tôi sẽ cập nhật PTR.

527
00:22:02,290 --> 00:22:05,060
Và tôi sẽ - hmm, những gì
Tên của bạn một lần nữa?

528
00:22:05,060 --> 00:22:05,560
>> HỌC SINH: Diana.

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana là chỉ, tất nhiên,
tại vô giá trị với bàn tay trái của cô.

530
00:22:09,190 --> 00:22:13,030
Vì vậy, nơi nào thực sự Habata
thuộc rõ ràng không?

531
00:22:13,030 --> 00:22:15,050
Bên trái, ở đây.

532
00:22:15,050 --> 00:22:19,460
Vì vậy, làm thế nào để tôi biết đặt mình đây
Tôi nghĩ rằng tôi đã hơi say lên.

533
00:22:19,460 --> 00:22:22,420
Bởi vì là những gì PTR nghệ thuật
thời điểm này trong thời gian?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
Vì vậy, mặc dù, trực quan, chúng ta có thể
rõ ràng là nhìn thấy tất cả các

536
00:22:25,580 --> 00:22:26,610
kẻ ở đây trên sân khấu.

537
00:22:26,610 --> 00:22:29,680
Tôi đã không lưu giữ theo dõi trước đó
người trong danh sách.

538
00:22:29,680 --> 00:22:33,210
Tôi không có một ngón tay chỉ ra,
trong trường hợp này, nút số 34.

539
00:22:33,210 --> 00:22:34,760
>> Vì vậy, chúng ta hãy thực sự bắt đầu trên này.

540
00:22:34,760 --> 00:22:37,560
Vì vậy, bây giờ tôi thực sự cần
một biến địa phương thứ hai.

541
00:22:37,560 --> 00:22:40,980
Và đây là những gì bạn sẽ thấy trong các
thực tế mẫu mã C, nơi mà như tôi đi,

542
00:22:40,980 --> 00:22:45,860
khi tôi cập nhật tay phải của tôi chỉ
Jason, do đó để lại Brian sau, tôi

543
00:22:45,860 --> 00:22:51,440
tốt hơn bắt đầu sử dụng tay trái
cập nhật nơi tôi ở, vì vậy mà tôi đi

544
00:22:51,440 --> 00:22:52,700
thông qua danh sách này -

545
00:22:52,700 --> 00:22:55,040
lúng túng hơn tôi dự định
giờ đây trực quan -

546
00:22:55,040 --> 00:22:56,740
Tôi sẽ đến được với các
cuối danh sách.

547
00:22:56,740 --> 00:23:00,020
>> Tay này vẫn còn vô giá trị, mà là khá
vô dụng, khác hơn là để chỉ ra

548
00:23:00,020 --> 00:23:02,980
Tôi rõ ràng vào cuối danh sách,
nhưng bây giờ ít nhất tôi có điều này

549
00:23:02,980 --> 00:23:08,270
con trỏ chỉ người tiền nhiệm ở đây, vì vậy
bây giờ những gì đưa cho và những gì con trỏ cần

550
00:23:08,270 --> 00:23:10,150
được cập nhật?

551
00:23:10,150 --> 00:23:13,214
Có tay nào bạn muốn
để cấu hình lại đầu tiên?

552
00:23:13,214 --> 00:23:15,190
>> HỌC SINH: [nghe được].

553
00:23:15,190 --> 00:23:16,220
>> SPEAKER 1: OK, vậy Diana.

554
00:23:16,220 --> 00:23:21,110
Nơi nào bạn muốn chỉ
Con trỏ trái của Diana tại?

555
00:23:21,110 --> 00:23:23,620
55, có lẽ, vì vậy mà
chúng tôi đã đưa vào đó.

556
00:23:23,620 --> 00:23:25,560
Và nơi nên 55 con trỏ đi đâu?

557
00:23:25,560 --> 00:23:27,000
Xuống, đại diện cho null.

558
00:23:27,000 --> 00:23:28,890
Và bàn tay của tôi, vào thời điểm này, không
quan trọng bởi vì họ chỉ

559
00:23:28,890 --> 00:23:30,070
các biến tạm thời.

560
00:23:30,070 --> 00:23:31,030
Vì vậy, bây giờ chúng tôi đang thực hiện.

561
00:23:31,030 --> 00:23:34,650
>> Vì vậy, sự phức tạp thêm có - và
nó không phải là khó thực hiện,

562
00:23:34,650 --> 00:23:38,660
nhưng chúng ta cần một biến thứ cấp để làm
chắc chắn rằng trước khi tôi di chuyển phải của tôi

563
00:23:38,660 --> 00:23:42,140
tay, tôi cập nhật các giá trị của trái
tay, con trỏ pred trong trường hợp này, vì vậy

564
00:23:42,140 --> 00:23:45,860
rằng tôi có một con trỏ theo sau
để theo dõi các nơi tôi.

565
00:23:45,860 --> 00:23:49,360
Bây giờ như một sang một bên, nếu bạn đang suy nghĩ này
thông qua, điều này cảm thấy như đó là một

566
00:23:49,360 --> 00:23:51,490
ít khó chịu khi phải giữ
theo dõi của bàn tay trái này.

567
00:23:51,490 --> 00:23:54,015
>> Điều gì sẽ một giải pháp khác
cho vấn đề này đã được?

568
00:23:54,015 --> 00:23:56,500
Nếu bạn đã thiết kế lại các dữ liệu
cấu trúc chúng ta đang nói

569
00:23:56,500 --> 00:23:59,630
thông qua ngay bây giờ?

570
00:23:59,630 --> 00:24:02,690
Nếu loại chỉ này cảm thấy một chút
gây phiền nhiễu có, như thế, hai con trỏ

571
00:24:02,690 --> 00:24:08,430
đi qua danh sách, những người khác có thể
đã, trong một thế giới lý tưởng, duy trì

572
00:24:08,430 --> 00:24:10,160
thông tin cần thiết?

573
00:24:10,160 --> 00:24:11,360
Yeah?

574
00:24:11,360 --> 00:24:12,610
>> HỌC SINH: [nghe được].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: Chính xác.

577
00:24:16,150 --> 00:24:19,130
Đúng như vậy không thực sự là một thú vị
mầm của một ý tưởng.

578
00:24:19,130 --> 00:24:22,470
Và ý tưởng này của một con trỏ trước,
chỉ vào phần tử trước đó.

579
00:24:22,470 --> 00:24:25,580
Nếu tôi chỉ thể hiện rằng
trong danh sách chính nó?

580
00:24:25,580 --> 00:24:27,810
Và nó sẽ được khó khăn để hình dung
này mà không có tất cả các giấy

581
00:24:27,810 --> 00:24:28,830
rơi xuống sàn nhà.

582
00:24:28,830 --> 00:24:31,860
Nhưng giả sử rằng những kẻ sử dụng cả hai
bàn tay của mình để có một trước

583
00:24:31,860 --> 00:24:35,950
con trỏ, và một con trỏ tới, do đó
thực hiện những gì chúng tôi sẽ gọi một gấp đôi

584
00:24:35,950 --> 00:24:36,830
danh sách liên kết.

585
00:24:36,830 --> 00:24:41,090
Điều đó sẽ cho phép tôi để sắp xếp các tua lại,
dễ dàng hơn nhiều mà không có tôi, các

586
00:24:41,090 --> 00:24:43,800
lập trình, phải giữ
theo dõi bằng tay -

587
00:24:43,800 --> 00:24:44,980
thực sự bằng tay -

588
00:24:44,980 --> 00:24:47,280
nơi tôi đã được trước đó
trong danh sách.

589
00:24:47,280 --> 00:24:48,110
Vì vậy, chúng tôi sẽ không làm điều đó.

590
00:24:48,110 --> 00:24:50,950
Chúng tôi sẽ giữ nó đơn giản bởi vì đó là
sẽ đến ở một mức giá, gấp đôi

591
00:24:50,950 --> 00:24:53,450
nhiều không gian cho các con trỏ,
nếu bạn muốn có một thứ hai.

592
00:24:53,450 --> 00:24:55,760
Nhưng đó thực sự là một chung
cấu trúc dữ liệu được biết đến như một

593
00:24:55,760 --> 00:24:57,410
gấp đôi danh sách liên kết.

594
00:24:57,410 --> 00:25:01,310
>> Chúng ta hãy làm ví dụ cuối cùng ở đây và đặt
những kẻ ra khỏi đau khổ của họ.

595
00:25:01,310 --> 00:25:03,270
Vì vậy, malloc 20.

596
00:25:03,270 --> 00:25:05,320
Lên đây từ các lối đi đó.

597
00:25:05,320 --> 00:25:06,280
Được rồi, tên của bạn là gì?

598
00:25:06,280 --> 00:25:07,440
>> HỌC SINH: [nghe được].

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1: Xin lỗi?

600
00:25:07,855 --> 00:25:08,480
>> HỌC SINH: [nghe được].

601
00:25:08,480 --> 00:25:09,410
>> SPEAKER 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK đi lên trên.

603
00:25:10,230 --> 00:25:11,910
Bạn sẽ là 20.

604
00:25:11,910 --> 00:25:14,720
Bạn rõ ràng là sẽ
thuộc giữa 17 và 22.

605
00:25:14,720 --> 00:25:16,150
Vì vậy, hãy để tôi học được bài học của tôi.

606
00:25:16,150 --> 00:25:18,150
Tôi sẽ bắt đầu con trỏ
chỉ vào Brian.

607
00:25:18,150 --> 00:25:21,190
Và tôi sẽ có bàn tay trái của tôi
chỉ cập nhật đến Brian như tôi di chuyển đến

608
00:25:21,190 --> 00:25:23,600
Jason, kiểm tra thực hiện 20 ít hơn chín?

609
00:25:23,600 --> 00:25:24,060
Không.

610
00:25:24,060 --> 00:25:25,430
Là 20 ít hơn 17?

611
00:25:25,430 --> 00:25:25,880
Không.

612
00:25:25,880 --> 00:25:27,450
Là 20 ít hơn 22?

613
00:25:27,450 --> 00:25:28,440
Vâng.

614
00:25:28,440 --> 00:25:34,070
Vì vậy, những gì con trỏ hoặc tay cần phải thay đổi
nơi họ đang chỉ bây giờ?

615
00:25:34,070 --> 00:25:37,070
>> Vì vậy, chúng ta có thể làm 17 chỉ ở mức 20.

616
00:25:37,070 --> 00:25:37,860
Vì vậy, đó là tốt.

617
00:25:37,860 --> 00:25:40,080
Nơi nào chúng ta muốn chỉ
con trỏ của bạn bây giờ?

618
00:25:40,080 --> 00:25:41,330
Ở tuổi 22.

619
00:25:41,330 --> 00:25:45,410
Và chúng tôi biết là 22, một lần nữa cám ơn
để con trỏ tạm thời của tôi.

620
00:25:45,410 --> 00:25:46,760
Vì vậy chúng tôi có OK.

621
00:25:46,760 --> 00:25:49,440
Vì vậy, bởi vì dung lượng lưu trữ tạm thời
Tôi đã lưu giữ theo dõi nơi tất cả mọi người là.

622
00:25:49,440 --> 00:25:55,055
Và bây giờ bạn trực quan có thể đi vào nơi
bạn thuộc về, và bây giờ chúng ta cần 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 quả bóng căng thẳng,
và một tràng pháo tay cho

624
00:25:58,410 --> 00:25:59,770
những người này, nếu chúng ta có thể.

625
00:25:59,770 --> 00:26:00,410
Độc đáo được thực hiện.

626
00:26:00,410 --> 00:26:05,320
>> [Vỗ tay]

627
00:26:05,320 --> 00:26:06,330
>> SPEAKER 1: Được rồi.

628
00:26:06,330 --> 00:26:09,860
Và bạn có thể giữ cho các mảnh
giấy như vật lưu niệm.

629
00:26:09,860 --> 00:26:15,930
>> Được rồi, vì vậy, tôi tin tưởng nó rất nhiều
dễ dàng hơn để bước qua với

630
00:26:15,930 --> 00:26:17,680
con người hơn là với mã thực tế.

631
00:26:17,680 --> 00:26:22,690
Nhưng những gì bạn sẽ tìm thấy chỉ trong một khoảnh khắc
bây giờ, là như nhau - oh, cảm ơn bạn.

632
00:26:22,690 --> 00:26:23,630
Cảm ơn bạn -

633
00:26:23,630 --> 00:26:29,360
là bạn sẽ thấy rằng cùng một dữ liệu
cấu trúc, một danh sách liên kết, có thể thực sự

634
00:26:29,360 --> 00:26:33,200
được sử dụng như là một khối xây dựng cho nhiều hơn
tinh vi cấu trúc dữ liệu.

635
00:26:33,200 --> 00:26:37,620
>> Và nhận ra quá chủ đề ở đây là
chúng tôi đã hoàn toàn giới thiệu hơn

636
00:26:37,620 --> 00:26:40,060
phức tạp trong thực hiện
của thuật toán này.

637
00:26:40,060 --> 00:26:43,940
Chèn, và nếu chúng ta đã đi qua nó,
xóa và tìm kiếm, là một chút

638
00:26:43,940 --> 00:26:46,660
phức tạp hơn
là với một mảng.

639
00:26:46,660 --> 00:26:48,040
Nhưng chúng ta đạt được một số tính năng động.

640
00:26:48,040 --> 00:26:50,180
Chúng tôi nhận được một cấu trúc dữ liệu thích nghi.

641
00:26:50,180 --> 00:26:54,010
>> Nhưng một lần nữa, chúng tôi phải trả giá của việc có một số
phức tạp thêm, cả trong

642
00:26:54,010 --> 00:26:54,910
thực hiện nó.

643
00:26:54,910 --> 00:26:56,750
Và chúng tôi đang từ bỏ truy cập ngẫu nhiên.

644
00:26:56,750 --> 00:27:00,450
Và phải trung thực, không có một số đẹp
làm sạch trượt tôi có thể cung cấp cho bạn mà

645
00:27:00,450 --> 00:27:03,120
nói đây là lý do tại sao một danh sách liên kết
là tốt hơn so với một mảng.

646
00:27:03,120 --> 00:27:04,100
Và để nó ở đó.

647
00:27:04,100 --> 00:27:07,520
Vì chủ đề tái phát nữa, thậm chí
nhiều hơn như vậy trong vài tuần tới, là

648
00:27:07,520 --> 00:27:10,200
rằng có không nhất thiết
một câu trả lời chính xác.

649
00:27:10,200 --> 00:27:13,830
>> Đây là lý do tại sao chúng tôi có trục riêng biệt
thiết kế cho bộ vấn đề.

650
00:27:13,830 --> 00:27:17,700
Nó sẽ rất bối cảnh nhạy cảm
cho dù bạn muốn sử dụng dữ liệu này

651
00:27:17,700 --> 00:27:21,750
cấu trúc hoặc một, và nó sẽ
phụ thuộc vào những gì quan trọng với bạn về

652
00:27:21,750 --> 00:27:24,620
các nguồn lực và phức tạp.

653
00:27:24,620 --> 00:27:28,830
>> Nhưng hãy để tôi đề xuất rằng các dữ liệu lý tưởng
cấu trúc, Chén thánh, sẽ

654
00:27:28,830 --> 00:27:32,200
cái gì đó là thời gian liên tục,
không phân biệt bao nhiêu là công cụ

655
00:27:32,200 --> 00:27:36,940
bên trong nó, nó sẽ không thể tuyệt vời nếu một
cấu trúc dữ liệu trả về câu trả lời trong

656
00:27:36,940 --> 00:27:37,920
thời gian liên tục.

657
00:27:37,920 --> 00:27:38,330
Vâng.

658
00:27:38,330 --> 00:27:40,110
Từ này trong từ điển lớn của bạn.

659
00:27:40,110 --> 00:27:41,550
Hoặc không, từ đây không phải là.

660
00:27:41,550 --> 00:27:43,270
Hoặc bất kỳ vấn đề như vậy đó.

661
00:27:43,270 --> 00:27:46,360
Vâng chúng ta hãy xem nếu chúng ta không có thể ít nhất
đi một bước về phía đó.

662
00:27:46,360 --> 00:27:50,190
>> Hãy để tôi đưa ra một cấu trúc dữ liệu mới
có thể được sử dụng cho những thứ khác nhau,

663
00:27:50,190 --> 00:27:52,260
trong trường hợp này được gọi là một bảng băm.

664
00:27:52,260 --> 00:27:55,590
Và vì vậy chúng tôi đang thực sự trở lại liếc
tại một mảng, trong trường hợp này, và

665
00:27:55,590 --> 00:28:00,550
có phần tùy tiện, tôi đã rút ra này
bảng băm như một mảng với sắp xếp của một

666
00:28:00,550 --> 00:28:02,810
mảng hai chiều -

667
00:28:02,810 --> 00:28:05,410
hay đúng hơn là nó miêu tả đây như một hai
mảng chiều - nhưng điều này chỉ là

668
00:28:05,410 --> 00:28:10,770
một loạt các kích thước 26, như vậy nếu chúng ta
gọi bảng mảng, khung bảng

669
00:28:10,770 --> 00:28:12,440
không là hình chữ nhật ở phía trên.

670
00:28:12,440 --> 00:28:15,090
Bảng khung 25 là hình chữ nhật
ở phía dưới.

671
00:28:15,090 --> 00:28:18,620
Và điều này là làm thế nào tôi có thể rút ra một dữ liệu
cấu trúc trong đó tôi muốn để lưu trữ

672
00:28:18,620 --> 00:28:19,790
người dân tên.

673
00:28:19,790 --> 00:28:24,370
>> Vì vậy, ví dụ, và tôi sẽ không vẽ
toàn bộ điều trên đây trên cao, nếu tôi

674
00:28:24,370 --> 00:28:29,160
có mảng này, mà bây giờ tôi sẽ đến
gọi một bảng băm, và điều này một lần nữa

675
00:28:29,160 --> 00:28:31,360
vị trí không.

676
00:28:31,360 --> 00:28:34,840
Này đây là vị trí
một, và vv.

677
00:28:34,840 --> 00:28:37,880
Tôi cho rằng tôi muốn sử dụng dữ liệu này
cấu trúc, vì lợi ích của cuộc thảo luận,

678
00:28:37,880 --> 00:28:42,600
để lưu trữ tên người, Alice và Bob
và Charlie và các tên khác như vậy.

679
00:28:42,600 --> 00:28:46,110
Vì vậy, nghĩ về điều này bây giờ là sự khởi đầu
, nói rằng, một từ điển

680
00:28:46,110 --> 00:28:47,520
với nhiều từ ngữ.

681
00:28:47,520 --> 00:28:49,435
Chúng được tên
trong ví dụ của chúng tôi ở đây.

682
00:28:49,435 --> 00:28:52,560
Và điều này là tất cả các quá Gecman, có lẽ, để
thực hiện kiểm tra chính tả, như chúng tôi

683
00:28:52,560 --> 00:28:54,400
có thể cho vấn đề thiết lập sáu.

684
00:28:54,400 --> 00:28:59,300
>> Vì vậy, nếu chúng ta có một loạt các kích thước tổng số 26
do đó đây là vị trí thứ 25

685
00:28:59,300 --> 00:29:03,390
ở phía dưới, và tôi cho rằng Alice là
từ đầu tiên trong từ điển của

686
00:29:03,390 --> 00:29:07,260
tên mà tôi muốn để chèn vào bộ nhớ RAM,
vào cấu trúc dữ liệu này, ở đâu

687
00:29:07,260 --> 00:29:12,480
bản năng nói với bạn rằng Alice
tên nên đi trong mảng này?

688
00:29:12,480 --> 00:29:13,510
>> Chúng tôi có 26 tùy chọn.

689
00:29:13,510 --> 00:29:14,990
Nơi mà chúng tôi muốn đưa cô ấy?

690
00:29:14,990 --> 00:29:16,200
Chúng tôi muốn cô ấy trong khung không, phải không?

691
00:29:16,200 --> 00:29:18,280
Một cho Alice, chúng ta hãy gọi đó là bằng không.

692
00:29:18,280 --> 00:29:20,110
Và B sẽ là một, và C sẽ có hai.

693
00:29:20,110 --> 00:29:22,600
Vì vậy, chúng ta sẽ viết
Tên của Alice ở đây.

694
00:29:22,600 --> 00:29:24,890
Nếu chúng ta sau đó chèn Bob, mình
tên sẽ đi đây.

695
00:29:24,890 --> 00:29:27,280
Charlie sẽ đi đây.

696
00:29:27,280 --> 00:29:30,500
Và vv xuống qua
cấu trúc dữ liệu này.

697
00:29:30,500 --> 00:29:32,090
>> Đây là một cấu trúc dữ liệu tuyệt vời.

698
00:29:32,090 --> 00:29:32,730
Tại sao?

699
00:29:32,730 --> 00:29:37,460
Thời gian hoạt động cũng như là những gì
chèn tên của một con người vào trong này

700
00:29:37,460 --> 00:29:39,850
cấu trúc dữ liệu ngay bây giờ?

701
00:29:39,850 --> 00:29:43,702
Cho rằng bảng này được thực hiện,
thực sự, như một mảng.

702
00:29:43,702 --> 00:29:44,940
Vâng đó là thời gian liên tục.

703
00:29:44,940 --> 00:29:45,800
Đó là thứ tự của một.

704
00:29:45,800 --> 00:29:46,360
Tại sao?

705
00:29:46,360 --> 00:29:48,630
>> Cũng làm thế nào để bạn xác định
nơi thuộc về Alice?

706
00:29:48,630 --> 00:29:51,000
Bạn nhìn vào mà thư của tên cô ấy?

707
00:29:51,000 --> 00:29:51,490
Là người đầu tiên.

708
00:29:51,490 --> 00:29:54,350
Và bạn có thể đạt được điều đó, nếu đó là một chuỗi,
bởi chỉ cần nhìn vào chuỗi

709
00:29:54,350 --> 00:29:55,200
khung không.

710
00:29:55,200 --> 00:29:57,110
Vì vậy, nhân vật thứ không của chuỗi.

711
00:29:57,110 --> 00:29:57,610
Đó là dễ dàng.

712
00:29:57,610 --> 00:30:00,350
Chúng tôi đã làm điều đó trong mật
phân công tuần trước.

713
00:30:00,350 --> 00:30:05,310
Và sau đó khi bạn biết rằng Alice
thư được vốn A, chúng tôi có thể trừ

714
00:30:05,310 --> 00:30:08,160
ra 65 hoặc vốn A chính nó,
mà cho chúng ta không.

715
00:30:08,160 --> 00:30:10,940
Vì vậy, bây giờ chúng ta biết rằng Alice thuộc
ở vị trí số không.

716
00:30:10,940 --> 00:30:14,240
>> Và đưa ra một con trỏ đến dữ liệu này
cấu trúc, của một số loại, làm thế nào lâu

717
00:30:14,240 --> 00:30:18,840
nó đưa tôi đến một nơi
không ở một mảng?

718
00:30:18,840 --> 00:30:22,080
Chỉ cần một bước, phải Đó là thời gian liên tục
vì truy cập ngẫu nhiên chúng tôi

719
00:30:22,080 --> 00:30:23,780
đề xuất là một tính năng của một mảng.

720
00:30:23,780 --> 00:30:28,570
Vì vậy, trong ngắn hạn, tìm ra những gì các chỉ số
của tên Alice là, đó là, trong

721
00:30:28,570 --> 00:30:32,610
trường hợp này, là A, hoặc chúng ta hãy giải quyết
mà không, trong đó B là một trong và C là

722
00:30:32,610 --> 00:30:34,900
hai, tìm mà ra
là thời gian liên tục.

723
00:30:34,900 --> 00:30:38,510
Tôi chỉ cần nhìn vào chữ cái đầu tiên của mình,
tìm ra nơi không là một

724
00:30:38,510 --> 00:30:40,460
mảng cũng là thời gian liên tục.

725
00:30:40,460 --> 00:30:42,140
Vì vậy, về mặt kỹ thuật đó là
như hai bước bây giờ.

726
00:30:42,140 --> 00:30:43,330
Nhưng đó vẫn không đổi.

727
00:30:43,330 --> 00:30:46,880
Vì vậy, chúng tôi gọi đó là O lớn, nên chúng tôi đã
Alice đưa vào bảng này trong

728
00:30:46,880 --> 00:30:48,440
thời gian liên tục.

729
00:30:48,440 --> 00:30:50,960
>> Nhưng tất nhiên, tôi là
ngây thơ ở đây, phải không?

730
00:30:50,960 --> 00:30:53,240
Những gì nếu có một Aaron trong lớp học?

731
00:30:53,240 --> 00:30:53,990
Hoặc Alicia?

732
00:30:53,990 --> 00:30:57,230
Hoặc bất kỳ tên khác bắt đầu với
A. Chúng ta đi đâu để đặt

733
00:30:57,230 --> 00:31:00,800
người đó, phải không?

734
00:31:00,800 --> 00:31:03,420
Ý tôi là, ngay bây giờ chỉ có ba
người trên bàn, có lẽ chúng ta

735
00:31:03,420 --> 00:31:07,490
nên đặt tại vị trí Aaron
không một hai ba.

736
00:31:07,490 --> 00:31:09,480
>> Phải, tôi có thể đặt một đây.

737
00:31:09,480 --> 00:31:13,350
Nhưng sau đó, nếu chúng ta cố gắng để chèn David vào
danh sách này, nơi mà David đi đâu?

738
00:31:13,350 --> 00:31:15,170
Bây giờ hệ thống của chúng tôi bắt đầu phá vỡ
xuống, phải không?

739
00:31:15,170 --> 00:31:19,210
Bởi vì bây giờ David kết thúc ở đây
nếu Aaron thực sự là đây.

740
00:31:19,210 --> 00:31:23,060
Và vì vậy bây giờ ý tưởng này hoàn toàn có một
cấu trúc dữ liệu sạch cung cấp cho chúng tôi

741
00:31:23,060 --> 00:31:28,010
chèn thời gian liên tục không còn
thời gian liên tục, bởi vì tôi phải

742
00:31:28,010 --> 00:31:31,240
kiểm tra, oh, damnit, một ai đó đã
tại vị trí của Alice.

743
00:31:31,240 --> 00:31:35,320
>> Hãy để tôi thăm dò phần còn lại của dữ liệu này
cấu trúc, tìm kiếm một chỗ để đặt

744
00:31:35,320 --> 00:31:37,130
một người nào đó như tên của Aaron.

745
00:31:37,130 --> 00:31:39,390
Và do đó cũng đang bắt đầu
dành thời gian tuyến tính.

746
00:31:39,390 --> 00:31:42,710
Hơn nữa, nếu bây giờ bạn muốn tìm
Aaron trong cấu trúc dữ liệu này, và bạn

747
00:31:42,710 --> 00:31:45,430
kiểm tra, và tên của Aaron không phải là ở đây.

748
00:31:45,430 --> 00:31:47,960
Tốt nhất, bạn sẽ chỉ cần nói của Aaron
không trong cấu trúc dữ liệu.

749
00:31:47,960 --> 00:31:51,530
Nhưng nếu bạn bắt đầu để có chỗ cho
Aaron nơi có cần phải có được một D

750
00:31:51,530 --> 00:31:55,600
hoặc E, bạn, trường hợp xấu nhất, phải kiểm tra
cấu trúc dữ liệu toàn bộ, trong

751
00:31:55,600 --> 00:31:59,480
trường hợp này mạn vào một cái gì đó
tuyến tính trong các kích thước của bảng.

752
00:31:59,480 --> 00:32:00,920
>> Vì vậy, tất cả rồi, tôi sẽ sửa lỗi này.

753
00:32:00,920 --> 00:32:04,200
Vấn đề ở đây là tôi đã
26 yếu tố trong mảng này.

754
00:32:04,200 --> 00:32:05,000
Hãy để tôi thay đổi nó.

755
00:32:05,000 --> 00:32:06,010
Rất tiếc.

756
00:32:06,010 --> 00:32:10,600
Hãy để tôi thay đổi nó để thay là của
kích thước 26 trong tổng số, thông báo phía dưới

757
00:32:10,600 --> 00:32:12,720
chỉ số sẽ thay đổi đến n trừ đi 1.

758
00:32:12,720 --> 00:32:16,610
Nếu 26 rõ ràng là quá nhỏ đối với con người '
tên, bởi vì có hàng ngàn

759
00:32:16,610 --> 00:32:20,830
tên của thế giới, chúng ta chỉ cần thực hiện
trong 100 hoặc 1000, 10000.

760
00:32:20,830 --> 00:32:22,960
Chúng ta hãy phân bổ không gian nhiều hơn nữa.

761
00:32:22,960 --> 00:32:27,230
>> Cũng không nhất thiết phải giảm
xác suất mà chúng tôi sẽ không có hai

762
00:32:27,230 --> 00:32:31,510
những người có tên bắt đầu bằng A, và
như vậy, bạn đã đi để cố gắng đưa một

763
00:32:31,510 --> 00:32:33,120
tên ở vị trí không còn.

764
00:32:33,120 --> 00:32:36,850
Họ vẫn sẽ va chạm, mà
có nghĩa là chúng tôi vẫn cần một giải pháp để đưa

765
00:32:36,850 --> 00:32:41,020
Alice và Aaron và Alicia và khác
tên bắt đầu bằng một nơi khác.

766
00:32:41,020 --> 00:32:43,460
Nhưng bao nhiêu của một vấn đề là điều này?

767
00:32:43,460 --> 00:32:46,870
Xác suất là những gì mà bạn
có va chạm trong một dữ liệu

768
00:32:46,870 --> 00:32:48,240
cấu trúc như thế này?

769
00:32:48,240 --> 00:32:52,570
>> Vâng, hãy để tôi - chúng tôi sẽ trở lại
cho câu hỏi ở đây.

770
00:32:52,570 --> 00:32:55,530
Và xem làm thế nào chúng ta có thể
giải quyết nó đầu tiên.

771
00:32:55,530 --> 00:32:58,480
Hãy để tôi kéo lên đề nghị này đây.

772
00:32:58,480 --> 00:33:02,020
Một thuật toán những gì chúng tôi vừa mô tả là,
để phân tích được gọi là tuyến tính

773
00:33:02,020 --> 00:33:05,030
thăm dò, theo đó, nếu bạn đã cố gắng để chèn
một cái gì đó ở đây trong dữ liệu này

774
00:33:05,030 --> 00:33:08,920
cấu trúc, được gọi là một bảng băm,
và không có phòng đó, bạn

775
00:33:08,920 --> 00:33:12,000
thực sự thăm dò cấu trúc dữ liệu
kiểm tra, điều này không?

776
00:33:12,000 --> 00:33:13,430
Là có sẵn này có sẵn này?

777
00:33:13,430 --> 00:33:13,980
Đây có phải là có sẵn?

778
00:33:13,980 --> 00:33:17,550
Và khi nó cuối cùng là, bạn chèn
tên mà bạn dự định ban đầu

779
00:33:17,550 --> 00:33:19,370
ở những nơi khác tại địa điểm đó.

780
00:33:19,370 --> 00:33:23,360
Nhưng trong trường hợp xấu nhất, các vị trí chỉ
có thể là dưới cùng của dữ liệu

781
00:33:23,360 --> 00:33:25,090
cấu trúc, cuối của mảng.

782
00:33:25,090 --> 00:33:30,130
>> Vì vậy, tuyến tính thăm dò, trong trường hợp xấu nhất,
mạn vào một thuật toán tuyến tính nơi

783
00:33:30,130 --> 00:33:34,500
Aaron, nếu xảy ra sẽ được chèn vào cuối
trong cấu trúc dữ liệu này, ông có thể

784
00:33:34,500 --> 00:33:39,540
va chạm với vị trí đầu tiên này, nhưng
sau đó kết thúc bằng cách may mắn ở cuối.

785
00:33:39,540 --> 00:33:43,940
Vì vậy, đây không phải là một hằng số
Hiện Chén Thánh cho chúng ta.

786
00:33:43,940 --> 00:33:47,650
Cách tiếp cận này của các yếu tố chèn vào
một cấu trúc dữ liệu được gọi là băm

787
00:33:47,650 --> 00:33:52,050
bảng dường như không có thời gian liên tục
ít nhất là trong trường hợp tổng quát.

788
00:33:52,050 --> 00:33:54,000
Nó có thể phân cấp thành một cái gì đó tuyến tính.

789
00:33:54,000 --> 00:33:56,970
>> Vì vậy, nếu chúng ta giải quyết va chạm
hơi khác nhau?

790
00:33:56,970 --> 00:34:00,740
Vì vậy, đây là một tinh vi hơn
tiếp cận với những gì vẫn còn

791
00:34:00,740 --> 00:34:02,800
được gọi là một bảng băm.

792
00:34:02,800 --> 00:34:05,890
Và bằng cách băm, như một sang một bên, những gì
Tôi có nghĩa là chỉ số

793
00:34:05,890 --> 00:34:07,070
Tôi đề cập trước đó.

794
00:34:07,070 --> 00:34:09,810
Để băm một cái gì đó có thể
dùng như một động từ.

795
00:34:09,810 --> 00:34:13,690
>> Vì vậy, nếu bạn băm Alice là một tên,
một hàm băm, có thể nói,

796
00:34:13,690 --> 00:34:14,710
phải trả lại một số.

797
00:34:14,710 --> 00:34:18,199
Trong trường hợp này là số không nếu cô ấy thuộc về tại
vị trí không, một khi cô thuộc vào

798
00:34:18,199 --> 00:34:20,000
vị trí một, và vv.

799
00:34:20,000 --> 00:34:24,360
Vì vậy, hàm băm của tôi vậy, đến nay đã được
siêu đơn giản, chỉ nhìn vào

800
00:34:24,360 --> 00:34:26,159
chữ cái đầu tiên trong tên của một ai đó.

801
00:34:26,159 --> 00:34:29,090
Nhưng một hàm băm có như
đầu vào một số phần dữ liệu, một

802
00:34:29,090 --> 00:34:30,210
chuỗi, một int, bất cứ điều gì.

803
00:34:30,210 --> 00:34:32,239
Và nó phun ra thường là một số.

804
00:34:32,239 --> 00:34:35,739
Và con số đó là nơi mà dữ liệu
yếu tố thuộc về một cấu trúc dữ liệu

805
00:34:35,739 --> 00:34:37,800
được biết đến ở đây như một bảng băm.

806
00:34:37,800 --> 00:34:41,400
>> Vì vậy, chỉ bằng trực giác, đây là một
bối cảnh hơi khác nhau.

807
00:34:41,400 --> 00:34:44,170
Điều này thực sự là đề cập đến một ví dụ
liên quan đến ngày sinh nhật, nơi

808
00:34:44,170 --> 00:34:46,850
có thể có nhiều như
31 ngày trong tháng.

809
00:34:46,850 --> 00:34:52,239
Nhưng những gì đã làm người này quyết định
làm trong trường hợp có va chạm?

810
00:34:52,239 --> 00:34:55,304
Bối cảnh hiện nay là, không phải là một vụ va chạm của
tên, nhưng một vụ va chạm của ngày sinh nhật,

811
00:34:55,304 --> 00:35:00,760
nếu hai người có cùng ngày sinh trên
các ngày 02 tháng 10, ví dụ.

812
00:35:00,760 --> 00:35:02,120
>> HỌC SINH: [nghe được].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: Vâng, vì vậy ở đây chúng tôi có
sự thúc đẩy của danh sách liên kết.

814
00:35:05,010 --> 00:35:07,830
Vì vậy, có vẻ một chút khác nhau
hơn, chúng tôi đã thu hút nó trước đó.

815
00:35:07,830 --> 00:35:10,790
Nhưng chúng tôi dường như có một mảng
ở phía bên tay trái.

816
00:35:10,790 --> 00:35:13,230
Đó là một chỉ số, cho không
đặc biệt lý do.

817
00:35:13,230 --> 00:35:14,630
Nhưng nó vẫn còn một mảng.

818
00:35:14,630 --> 00:35:16,160
Nó là một mảng của con trỏ.

819
00:35:16,160 --> 00:35:20,670
Và mỗi người trong số những yếu tố này, mỗi
những vòng tròn hoặc dấu gạch chéo - các dấu gạch chéo

820
00:35:20,670 --> 00:35:23,970
đại diện null - mỗi
gợi ý rõ ràng là chỉ để

821
00:35:23,970 --> 00:35:25,730
những gì cấu trúc dữ liệu?

822
00:35:25,730 --> 00:35:26,890
Một danh sách liên kết.

823
00:35:26,890 --> 00:35:30,530
>> Vì vậy, bây giờ chúng tôi có khả năng
cứng mã vào chương trình của chúng tôi

824
00:35:30,530 --> 00:35:32,010
kích thước của bảng.

825
00:35:32,010 --> 00:35:35,360
Trong trường hợp này, chúng ta biết có bao giờ
hơn 31 ngày trong một tháng.

826
00:35:35,360 --> 00:35:38,480
Vì vậy, khó mã hóa một giá trị như 31 được
hợp lý trong bối cảnh đó.

827
00:35:38,480 --> 00:35:42,700
Trong bối cảnh tên, cứng mã hóa
26 là không hợp lý đó của người dân

828
00:35:42,700 --> 00:35:46,340
tên chỉ bắt đầu, ví dụ,
bảng chữ cái từ A đến Z. liên quan

829
00:35:46,340 --> 00:35:50,180
>> Chúng ta có thể nhồi nhét tất cả vào dữ liệu
cấu trúc, miễn là, khi chúng ta có được một

830
00:35:50,180 --> 00:35:55,330
va chạm, chúng tôi không đặt tên ở đây,
chúng tôi thay vì nghĩ về những tế bào

831
00:35:55,330 --> 00:36:00,270
không như các chuỗi mình, nhưng như
con trỏ đến, ví dụ, Alice.

832
00:36:00,270 --> 00:36:03,660
Và sau đó Alice có thể có một con trỏ
khác tên bắt đầu với

833
00:36:03,660 --> 00:36:06,150
A. Và Bob thực sự đi qua đây.

834
00:36:06,150 --> 00:36:10,850
>> Và nếu có một tên khác bắt đầu
với B, anh ta kết thúc ở đây.

835
00:36:10,850 --> 00:36:15,070
Và do đó mỗi nguyên tố này
bảng hai, nếu chúng tôi thiết kế này một

836
00:36:15,070 --> 00:36:17,350
ít khéo léo hơn -

837
00:36:17,350 --> 00:36:18,125
đi trên -

838
00:36:18,125 --> 00:36:22,950
nếu chúng tôi thiết kế này nhiều hơn một chút
khéo léo, bây giờ trở thành một dữ liệu thích ứng

839
00:36:22,950 --> 00:36:27,720
cấu trúc, mà không có giới hạn cứng
trên bao nhiêu yếu tố bạn có thể chèn

840
00:36:27,720 --> 00:36:30,700
vào nó bởi vì nếu bạn có
một vụ va chạm, đó là tốt.

841
00:36:30,700 --> 00:36:34,690
Chỉ cần đi trước và thêm nó vào
những gì chúng ta đã thấy một chút trước đã

842
00:36:34,690 --> 00:36:38,290
được biết đến như một danh sách liên kết.

843
00:36:38,290 --> 00:36:39,690
>> Vâng chúng ta hãy dừng lại một lúc.

844
00:36:39,690 --> 00:36:42,570
Xác suất của một vụ va chạm là những gì
ở nơi đầu tiên?

845
00:36:42,570 --> 00:36:45,480
Đúng, có lẽ tôi là hơn suy nghĩ, có thể
Tôi làm công nghệ hơn vấn đề này,

846
00:36:45,480 --> 00:36:46,370
bởi vì bạn biết gì không?

847
00:36:46,370 --> 00:36:49,070
Vâng, tôi có thể đến với bất
ví dụ ra khỏi đỉnh đầu của tôi như

848
00:36:49,070 --> 00:36:52,870
Allison và Aaron, nhưng trong thực tế,
cung cấp một phân phối thống nhất của

849
00:36:52,870 --> 00:36:56,990
đầu vào, đó là một số chèn ngẫu nhiên
thành một cấu trúc dữ liệu, những gì thực sự là

850
00:36:56,990 --> 00:36:58,580
xác suất của một vụ va chạm?

851
00:36:58,580 --> 00:37:01,670
Cũng quay ra, nó thực sự
siêu cao.

852
00:37:01,670 --> 00:37:03,850
Hãy để tôi khái quát này
vấn đề là như thế này.

853
00:37:03,850 --> 00:37:08,890
>> Vì vậy, trong một căn phòng của n CS50 sinh viên, những gì
xác suất có ít nhất

854
00:37:08,890 --> 00:37:11,010
hai sinh viên trong phòng
có cùng ngày sinh?

855
00:37:11,010 --> 00:37:13,346
Do đó, có những gì. một vài hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 người dân ở đây và một số
trăm người ở nhà hôm nay.

857
00:37:16,790 --> 00:37:20,670
Vì vậy, nếu bạn muốn tự hỏi mình những gì
xác suất của hai người

858
00:37:20,670 --> 00:37:23,930
trong căn phòng này có cùng ngày sinh,
chúng ta có thể con số này ra.

859
00:37:23,930 --> 00:37:26,250
Và tôi khẳng định trên thực tế có hai
những người có cùng ngày sinh.

860
00:37:26,250 --> 00:37:29,560
>> Ví dụ, không ai
có ngày sinh nhật hôm nay?

861
00:37:29,560 --> 00:37:31,340
Hôm qua?

862
00:37:31,340 --> 00:37:32,590
Ngày mai?

863
00:37:32,590 --> 00:37:35,980
Được rồi, nó cảm thấy như tôi sẽ
phải làm 363 này hay như vậy hơn

864
00:37:35,980 --> 00:37:39,500
Thời gian để thực sự tìm ra
nếu chúng ta có một vụ va chạm.

865
00:37:39,500 --> 00:37:42,350
Hoặc chúng tôi chỉ có thể làm điều này bằng toán học
chứ không phải là tediously

866
00:37:42,350 --> 00:37:43,200
làm điều này.

867
00:37:43,200 --> 00:37:44,500
Và đề nghị sau đây.

868
00:37:44,500 --> 00:37:48,740
>> Vì vậy, tôi đề nghị chúng ta có thể mô hình
xác suất của hai người có

869
00:37:48,740 --> 00:37:55,320
cùng sinh nhật như xác suất của 1
trừ khả năng không ai có

870
00:37:55,320 --> 00:37:56,290
cùng ngày sinh nhật.

871
00:37:56,290 --> 00:37:59,960
Vì vậy, để có được điều này, và điều này chỉ là
cách ưa thích của văn bản này, cho

872
00:37:59,960 --> 00:38:03,090
người đầu tiên trong phòng, anh ta hoặc cô
có thể có bất kỳ một trong những có thể

873
00:38:03,090 --> 00:38:07,370
ngày sinh nhật giả định 365 ngày trong năm,
với lời xin lỗi đối với người

874
00:38:07,370 --> 00:38:08,760
29 sinh nhật tháng hai.

875
00:38:08,760 --> 00:38:13,470
>> Vì vậy, người đầu tiên trong căn phòng này là miễn phí
có bất kỳ số lượng của ngày sinh nhật

876
00:38:13,470 --> 00:38:18,280
ra khỏi khả năng 365 để
chúng tôi sẽ làm điều đó 365 chia cho 365,

877
00:38:18,280 --> 00:38:18,990
đó là một trong.

878
00:38:18,990 --> 00:38:22,700
Người tiếp theo trong phòng, nếu mục tiêu
là để tránh va chạm, có thể chỉ

879
00:38:22,700 --> 00:38:26,460
có của mình hoặc sinh nhật của cô về cách
nhiều ngày khác nhau có thể?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Vì vậy, nhiệm kỳ thứ hai trong biểu thức này là
về cơ bản làm toán đó cho chúng ta

882
00:38:31,430 --> 00:38:33,460
bằng cách trừ đi một ngày có thể.

883
00:38:33,460 --> 00:38:36,390
Và sau đó vào ngày hôm sau, ngày hôm sau, các
Ngày hôm sau xuống với tổng số

884
00:38:36,390 --> 00:38:38,100
của người trong phòng.

885
00:38:38,100 --> 00:38:41,290
>> Và nếu chúng ta sau đó xem xét, sau đó là gì
xác suất không của tất cả mọi người có

886
00:38:41,290 --> 00:38:45,265
ngày sinh nhật độc đáo, nhưng lại trừ đi 1
rằng, một biểu hiện những gì chúng tôi nhận được là

887
00:38:45,265 --> 00:38:47,810
mà có thể rất fancifully
trông như thế này.

888
00:38:47,810 --> 00:38:50,330
Nhưng nó thú vị hơn
nhìn trực quan.

889
00:38:50,330 --> 00:38:55,120
Đây là một biểu đồ mà trên trục x
số lượng người trong phòng,

890
00:38:55,120 --> 00:38:56,180
số ngày sinh nhật.

891
00:38:56,180 --> 00:38:59,840
Trên trục y là xác suất
của một vụ va chạm, hai người

892
00:38:59,840 --> 00:39:01,230
có cùng ngày sinh.

893
00:39:01,230 --> 00:39:05,020
>> Và takeaway từ đường cong này là
rằng ngay khi bạn nhận được để thích 40

894
00:39:05,020 --> 00:39:11,110
sinh viên, bạn đang lên tại một xác suất 90%
combinatorically của hai

895
00:39:11,110 --> 00:39:13,550
người trở lên có
cùng ngày sinh nhật.

896
00:39:13,550 --> 00:39:18,600
Và một khi bạn nhận được để thích 58 người đó là
gần 100% cơ hội hai

897
00:39:18,600 --> 00:39:21,310
người trong phòng sẽ có
cùng sinh nhật, mặc dù có

898
00:39:21,310 --> 00:39:26,650
365 hoặc 366 thùng có thể, và
chỉ có 58 người trong phòng.

899
00:39:26,650 --> 00:39:29,900
Chỉ thống kê bạn có khả năng
nhận được va chạm, mà trong ngắn hạn

900
00:39:29,900 --> 00:39:31,810
thúc đẩy cuộc thảo luận này.

901
00:39:31,810 --> 00:39:35,890
Rằng ngay cả khi chúng tôi có được ưa thích ở đây, và
bắt đầu có những dây chuyền, chúng ta vẫn còn

902
00:39:35,890 --> 00:39:36,950
sẽ có va chạm.

903
00:39:36,950 --> 00:39:42,710
>> Để đặt ra câu hỏi, là những gì
chi phí kinh chèn và xóa bỏ

904
00:39:42,710 --> 00:39:44,850
thành một cấu trúc dữ liệu như thế này?

905
00:39:44,850 --> 00:39:46,630
Cũng cho tôi đề xuất -

906
00:39:46,630 --> 00:39:51,570
và cho tôi quay trở lại màn hình trên
ở đây - nếu chúng ta có n yếu tố trong

907
00:39:51,570 --> 00:39:56,330
danh sách, vì vậy nếu chúng ta đang cố gắng để chèn
n phần tử, và chúng tôi có

908
00:39:56,330 --> 00:39:58,050
bao nhiêu tổng số xô?

909
00:39:58,050 --> 00:40:03,450
Hãy nói rằng tổng số 31 thùng
trong trường hợp của ngày sinh nhật.

910
00:40:03,450 --> 00:40:09,240
Chiều dài tối đa của một là những gì
của các chuỗi có khả năng?

911
00:40:09,240 --> 00:40:12,670
>> Nếu một lần nữa có thể 31
ngày sinh nhật trong một tháng.

912
00:40:12,670 --> 00:40:14,580
Và chúng tôi chỉ kết tụ tất cả mọi người -

913
00:40:14,580 --> 00:40:15,580
thực sự đó là một ví dụ ngu ngốc.

914
00:40:15,580 --> 00:40:16,960
Hãy thay vì làm 26.

915
00:40:16,960 --> 00:40:20,890
Vì vậy, nếu thực sự có người có tên
bắt đầu với từ A đến Z, do đó cho

916
00:40:20,890 --> 00:40:22,780
chúng tôi 26 khả năng.

917
00:40:22,780 --> 00:40:25,920
Và chúng tôi đang sử dụng một cấu trúc dữ liệu như
mà chúng ta vừa thấy, nhờ đó chúng ta có

918
00:40:25,920 --> 00:40:30,210
một mảng của các con trỏ, mỗi trong số đó
trỏ đến một danh sách liên kết, nơi

919
00:40:30,210 --> 00:40:32,360
danh sách đầu tiên là tất cả mọi người
với tên Alice.

920
00:40:32,360 --> 00:40:35,770
Danh sách thứ hai là tất cả với
tên bắt đầu với A, bắt đầu

921
00:40:35,770 --> 00:40:36,980
với B, và vv.

922
00:40:36,980 --> 00:40:41,020
>> Chiều dài khả năng của từng là những gì
những danh sách nếu chúng ta giả định một sạch đẹp

923
00:40:41,020 --> 00:40:45,410
phân phối các tên từ A đến Z
trên cấu trúc dữ liệu toàn bộ?

924
00:40:45,410 --> 00:40:50,210
Có người n trong cấu trúc dữ liệu
chia cho 26, nếu họ độc đáo

925
00:40:50,210 --> 00:40:52,110
trải rộng trên toàn bộ
cấu trúc dữ liệu.

926
00:40:52,110 --> 00:40:54,970
Vì vậy, độ dài của mỗi
chuỗi là n chia cho 26.

927
00:40:54,970 --> 00:40:57,380
Nhưng trong ký hiệu O lớn, đó là những gì?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Đó thực sự là những gì?

930
00:41:02,440 --> 00:41:04,150
Vì vậy, nó thực sự chỉ là n, phải không?

931
00:41:04,150 --> 00:41:06,620
Bởi vì chúng tôi đã nói trong quá khứ,
rằng ugh bạn chia cho 26.

932
00:41:06,620 --> 00:41:08,710
Có, trong thực tế nó là nhanh hơn.

933
00:41:08,710 --> 00:41:12,720
Nhưng về mặt lý thuyết, nó không phải là cơ bản
tất cả những gì nhanh hơn.

934
00:41:12,720 --> 00:41:16,040
>> Vì vậy, chúng tôi dường như không có gì nhiều
gần Chén thánh này.

935
00:41:16,040 --> 00:41:17,750
Trong thực tế, đây chỉ là thời gian tuyến tính.

936
00:41:17,750 --> 00:41:20,790
Heck, vào thời điểm này, tại sao chúng ta không
chỉ cần sử dụng một danh sách liên kết rất lớn?

937
00:41:20,790 --> 00:41:23,510
Tại sao chúng ta không chỉ cần sử dụng một trong rất lớn
mảng để lưu trữ tên của

938
00:41:23,510 --> 00:41:25,010
tất cả mọi người trong phòng không?

939
00:41:25,010 --> 00:41:28,280
Vâng, ở đó vẫn còn một cái gì đó
hấp dẫn về một bảng băm?

940
00:41:28,280 --> 00:41:30,810
Ở đó vẫn còn một cái gì đó hấp dẫn
về một cấu trúc dữ liệu

941
00:41:30,810 --> 00:41:33,940
trông như thế này?

942
00:41:33,940 --> 00:41:35,182
Này.

943
00:41:35,182 --> 00:41:37,050
>> HỌC SINH: [nghe được].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: Đúng, và một lần nữa khi nó chỉ
một thời gian thuật toán tuyến tính, và một

945
00:41:39,840 --> 00:41:42,780
thời gian tuyến tính cấu trúc dữ liệu, tại sao không tôi
chỉ lưu trữ tên của tất cả mọi người trong một lớn

946
00:41:42,780 --> 00:41:44,210
mảng, hoặc trong một danh sách liên kết lớn?

947
00:41:44,210 --> 00:41:47,010
Và ngăn chặn làm cho CS rất nhiều khó khăn hơn
hơn nó cần phải được?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Là những gì hấp dẫn về điều này, thậm chí
mặc dù tôi trầy xước nó ra?

950
00:41:53,190 --> 00:41:54,930
>> HỌC SINH: [nghe được].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: Insertions không?

952
00:41:57,040 --> 00:41:58,140
Đắt tiền nữa.

953
00:41:58,140 --> 00:42:03,390
Vì vậy, có khả năng chèn có thể vẫn
có thời gian liên tục, ngay cả khi dữ liệu của bạn

954
00:42:03,390 --> 00:42:07,910
cấu trúc như thế này, một loạt các
con trỏ, mỗi trong số đó là chỉ tại

955
00:42:07,910 --> 00:42:09,550
có khả năng một danh sách liên kết.

956
00:42:09,550 --> 00:42:15,220
Làm thế nào bạn có thể đạt được liên tục
chèn thời gian của tên?

957
00:42:15,220 --> 00:42:16,280
Dính nó ở phía trước, phải không?

958
00:42:16,280 --> 00:42:19,290
>> Nếu chúng ta hy sinh một mục tiêu thiết kế từ
trước đó, nơi mà chúng tôi muốn giữ

959
00:42:19,290 --> 00:42:22,650
tên của tất cả mọi người, ví dụ, sắp xếp,
hoặc tất cả các số trên sân khấu được sắp xếp,

960
00:42:22,650 --> 00:42:25,020
Giả sử chúng ta có một
danh sách liên kết được phân loại.

961
00:42:25,020 --> 00:42:29,960
Nó chỉ chi phí cho chúng tôi một hoặc hai bước,
như trong trường hợp của Ben và Brian

962
00:42:29,960 --> 00:42:32,750
trước đó, để chèn một phần tử ở
đầu danh sách.

963
00:42:32,750 --> 00:42:36,090
Vì vậy, nếu chúng ta không quan tâm đến phân loại tất cả
của tên bắt đầu bằng A hoặc tất cả

964
00:42:36,090 --> 00:42:39,660
những cái tên bắt đầu với B, chúng tôi vẫn có thể
đạt được chèn thời gian liên tục.

965
00:42:39,660 --> 00:42:43,900
Bây giờ nhìn lên Alice hay Bob hoặc tên bất kỳ
nói chung là vẫn còn những gì?

966
00:42:43,900 --> 00:42:48,100
Đó là O lớn của n khi chia 26, trong
trường hợp lý tưởng, nơi tất cả mọi người là thống nhất

967
00:42:48,100 --> 00:42:51,190
phân phối, nơi có nhiều của một
như có Z, mà có lẽ là

968
00:42:51,190 --> 00:42:52,220
không thực tế.

969
00:42:52,220 --> 00:42:53,880
Nhưng đó vẫn là tuyến tính.

970
00:42:53,880 --> 00:42:57,120
>> Nhưng ở đây, chúng ta trở lại điểm
ký hiệu tiệm cận là

971
00:42:57,120 --> 00:42:58,600
về mặt lý thuyết đúng.

972
00:42:58,600 --> 00:43:02,960
Nhưng trong thế giới thực, nếu tôi cho rằng
chương trình của tôi có thể làm điều gì đó 26 lần

973
00:43:02,960 --> 00:43:06,210
nhanh hơn bạn, có chương trình
bạn sẽ thích sử dụng?

974
00:43:06,210 --> 00:43:09,660
Bạn hay của tôi, mà
là 26 lần nhanh hơn?

975
00:43:09,660 --> 00:43:14,320
Thực tế, người có là 26
lần nhanh hơn, ngay cả khi về mặt lý thuyết

976
00:43:14,320 --> 00:43:18,790
các thuật toán của chúng tôi chạy trong cùng một
tiệm cận thời gian chạy.

977
00:43:18,790 --> 00:43:20,940
>> Hãy để tôi đưa ra một khác nhau
giải pháp hoàn toàn.

978
00:43:20,940 --> 00:43:24,380
Và nếu điều này không thổi tâm trí của bạn,
chúng tôi đang trên cấu trúc dữ liệu.

979
00:43:24,380 --> 00:43:27,420
Vì vậy, đây là nó một Trie -

980
00:43:27,420 --> 00:43:28,520
loại một tên ngu ngốc.

981
00:43:28,520 --> 00:43:32,880
Nó xuất phát từ khả năng tìm lại, và từ
được viết Trie, t-r-i-e, vì

982
00:43:32,880 --> 00:43:34,450
Tất nhiên hồi âm thanh như Trie.

983
00:43:34,450 --> 00:43:36,580
Nhưng đó là lịch sử
của Trie từ.

984
00:43:36,580 --> 00:43:40,980
>> Vì vậy, một Trie thực sự là một số loại cây,
và nó cũng là một cách chơi từ đó.

985
00:43:40,980 --> 00:43:46,330
Và mặc dù bạn có thể không hoàn toàn nhìn thấy nó
với hình dung này, một Trie là một

986
00:43:46,330 --> 00:43:50,790
cây cấu trúc, giống như một cây gia đình với
một tổ tiên ở đầu và rất nhiều

987
00:43:50,790 --> 00:43:54,530
các cháu và chắt
như lá ở phía dưới.

988
00:43:54,530 --> 00:43:58,100
Nhưng mỗi nút trong một Trie là một mảng.

989
00:43:58,100 --> 00:44:00,680
Và nó trong một mảng - và chúng ta hãy
đơn giản hóa cho một thời điểm - đó là một

990
00:44:00,680 --> 00:44:04,600
mảng, trong trường hợp này, các kích thước 26, nơi
mỗi nút lại là một mảng có kích thước

991
00:44:04,600 --> 00:44:09,000
26, trong đó yếu tố thứ không trong đó
mảng đại diện cho A, và cuối cùng

992
00:44:09,000 --> 00:44:11,810
yếu tố trong mỗi ví dụ
mảng đại diện cho Z.

993
00:44:11,810 --> 00:44:15,520
>> Vì vậy, tôi đề nghị, sau đó, dữ liệu này
cấu trúc, được biết đến như một Trie, có thể

994
00:44:15,520 --> 00:44:17,600
cũng được sử dụng để lưu trữ từ.

995
00:44:17,600 --> 00:44:21,740
Chúng ta đã thấy một thời điểm trước đây như thế nào chúng ta có thể lưu trữ
từ, hoặc trong trường hợp này tên, và chúng tôi

996
00:44:21,740 --> 00:44:25,440
đã thấy trước đó như thế nào chúng ta có thể lưu trữ số,
nhưng nếu chúng ta tập trung vào tên hoặc dây

997
00:44:25,440 --> 00:44:27,460
ở đây, nhận thấy có gì thú vị.

998
00:44:27,460 --> 00:44:32,210
Tôi cho rằng các tên Maxwell là
bên trong của cấu trúc dữ liệu này.

999
00:44:32,210 --> 00:44:33,730
Nơi nào bạn nhìn thấy Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> HỌC SINH: [nghe được].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: Trên trái.

1002
00:44:36,240 --> 00:44:39,910
Vì vậy, điều thú vị với dữ liệu này
cấu trúc là thay vì lưu trữ các

1003
00:44:39,910 --> 00:44:46,200
chuỗi M-A-X-W-E-L-L dấu chéo ngược bằng không, tất cả
liên tục kế nhau, thay vì những gì bạn làm

1004
00:44:46,200 --> 00:44:46,890
là sau đây.

1005
00:44:46,890 --> 00:44:50,510
Nếu đây là một Trie như cấu trúc dữ liệu,
mỗi nút mà lại là một mảng,

1006
00:44:50,510 --> 00:44:54,650
và bạn muốn lưu trữ Maxwell, bạn đầu tiên
chỉ số và do đó nút của gốc, vì vậy

1007
00:44:54,650 --> 00:44:57,810
để nói chuyện, nút trên cùng,
tại địa điểm M, đúng, vì vậy

1008
00:44:57,810 --> 00:44:59,160
khoảng vào trung lộ.

1009
00:44:59,160 --> 00:45:03,740
Và sau đó từ đó, bạn thực hiện theo một
con trỏ tới một nút con, vậy để nói chuyện.

1010
00:45:03,740 --> 00:45:06,150
Vì vậy, trong ý nghĩa cây gia đình,
bạn làm theo nó xuống.

1011
00:45:06,150 --> 00:45:09,030
Và dẫn bạn đến một nút khác
trên bên trái có, đó là

1012
00:45:09,030 --> 00:45:10,540
chỉ là một mảng.

1013
00:45:10,540 --> 00:45:14,710
>> Và sau đó nếu bạn muốn lưu trữ Maxwell,
bạn tìm thấy những con trỏ đại diện cho

1014
00:45:14,710 --> 00:45:16,430
A, đó là một trong những điều này ở đây.

1015
00:45:16,430 --> 00:45:17,840
Sau đó, bạn đi đến nút tiếp theo.

1016
00:45:17,840 --> 00:45:20,100
Và thông báo - đây là lý do tại sao của hình ảnh
một chút lừa dối -

1017
00:45:20,100 --> 00:45:21,990
nút này nhìn siêu nhỏ.

1018
00:45:21,990 --> 00:45:26,050
Nhưng ở bên phải của việc này là Y và Z.
Nó chỉ là tác giả đã cắt ngắn

1019
00:45:26,050 --> 00:45:27,630
hình ảnh để bạn thực sự
nhìn thấy mọi thứ.

1020
00:45:27,630 --> 00:45:30,400
Nếu không hình ảnh này
sẽ là vô cùng rộng.

1021
00:45:30,400 --> 00:45:36,180
Vì vậy, bây giờ bạn chỉ vào vị trí X, sau đó
W, Sau đó, E, sau đó L, sau đó L. Sau đó, những gì

1022
00:45:36,180 --> 00:45:37,380
sự tò mò này?

1023
00:45:37,380 --> 00:45:41,250
>> Vâng, nếu chúng ta đang sử dụng loại này mới
mất làm thế nào để lưu trữ một chuỗi trong một

1024
00:45:41,250 --> 00:45:44,500
cấu trúc dữ liệu, bạn vẫn cần phải
về cơ bản đánh dấu vào trong các dữ liệu

1025
00:45:44,500 --> 00:45:47,250
cấu trúc một từ kết thúc ở đây.

1026
00:45:47,250 --> 00:45:50,830
Nói cách khác, mỗi một nút
bằng cách nào đó phải nhớ rằng chúng ta

1027
00:45:50,830 --> 00:45:53,500
thực sự sau tất cả những con trỏ
và để lại một chút

1028
00:45:53,500 --> 00:45:58,370
bánh cốm ở dưới đây này
cấu trúc để chỉ M-A-X-W-E-L-L là

1029
00:45:58,370 --> 00:46:00,230
thực sự trong cấu trúc dữ liệu này.

1030
00:46:00,230 --> 00:46:02,040
>> Vì vậy, chúng ta có thể làm điều này như sau.

1031
00:46:02,040 --> 00:46:06,810
Mỗi nút trong hình chúng ta chỉ
cưa có một người, một mảng có kích thước 27.

1032
00:46:06,810 --> 00:46:10,550
Và nó bây giờ 27, vì trong p thiết lập sáu,
chúng tôi sẽ thực sự cung cấp cho bạn một dấu nháy đơn,

1033
00:46:10,550 --> 00:46:13,590
vì vậy chúng tôi có thể có những cái tên như O'Reilly
và những người khác với dấu nháy.

1034
00:46:13,590 --> 00:46:14,820
Nhưng cùng một ý tưởng.

1035
00:46:14,820 --> 00:46:17,710
Mỗi của những yếu tố trong
điểm mảng tới một cấu trúc

1036
00:46:17,710 --> 00:46:19,320
nút, vì vậy chỉ cần một nút.

1037
00:46:19,320 --> 00:46:21,430
Vì vậy, đây là rất gợi nhớ
của danh sách liên kết của chúng tôi.

1038
00:46:21,430 --> 00:46:24,550
>> Và sau đó tôi có một Boolean, mà tôi sẽ
gọi từ, mà chỉ có được

1039
00:46:24,550 --> 00:46:29,120
đúng nếu một từ kết thúc tại đây
nút trong cây.

1040
00:46:29,120 --> 00:46:32,870
Nó có hiệu quả đại diện cho ít
tam giác chúng ta đã thấy một thời điểm trước đây.

1041
00:46:32,870 --> 00:46:37,190
Vì vậy, nếu một từ kết thúc tại đó nút trong
cây, mà lĩnh vực từ đó sẽ là sự thật,

1042
00:46:37,190 --> 00:46:41,990
được khái niệm kiểm tra tắt, hoặc
chúng tôi đang vẽ hình tam giác này, có có

1043
00:46:41,990 --> 00:46:44,080
là một từ đây.

1044
00:46:44,080 --> 00:46:45,120
>> Vì vậy, đây là một Trie.

1045
00:46:45,120 --> 00:46:48,540
Và bây giờ câu hỏi là, những gì
được của nó thời gian chạy?

1046
00:46:48,540 --> 00:46:49,930
Là nó lớn O n?

1047
00:46:49,930 --> 00:46:51,410
Nó là cái gì khác?

1048
00:46:51,410 --> 00:46:57,330
Vâng, nếu bạn có n tên trong dữ liệu này
cấu trúc, Maxwell là một trong

1049
00:46:57,330 --> 00:47:02,330
họ, thời gian hoạt động là những gì
chèn hoặc tìm Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Thời gian hoạt động là những gì
chèn Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Nếu có n tên khác
đã có trong bảng?

1053
00:47:11,740 --> 00:47:12,507
Yeah?

1054
00:47:12,507 --> 00:47:15,429
>> HỌC SINH: [nghe được].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: Vâng, đó là chiều dài
của tên, phải không?

1056
00:47:17,550 --> 00:47:24,420
Vì vậy, M-một-x-w-e-l-l để nó cảm thấy như thế này
thuật toán là O lớn trong bảy.

1057
00:47:24,420 --> 00:47:26,580
Bây giờ, tất nhiên, tên
sẽ thay đổi chiều dài.

1058
00:47:26,580 --> 00:47:27,380
Có lẽ đó là một tên ngắn.

1059
00:47:27,380 --> 00:47:28,600
Có lẽ đó là một tên dài hơn.

1060
00:47:28,600 --> 00:47:33,390
Nhưng điều quan trọng ở đây là
đó là một số không đổi.

1061
00:47:33,390 --> 00:47:36,810
Và có lẽ nó không thực sự liên tục,
nhưng thần, nếu thực tế, trong một

1062
00:47:36,810 --> 00:47:41,570
từ điển, có lẽ một số giới hạn
về số lượng ký tự trong một

1063
00:47:41,570 --> 00:47:43,820
tên của người đó trong một quốc gia cụ thể.

1064
00:47:43,820 --> 00:47:46,940
>> Và vì vậy chúng tôi có thể giả định rằng
giá trị là một hằng số.

1065
00:47:46,940 --> 00:47:47,750
Tôi không biết nó là gì.

1066
00:47:47,750 --> 00:47:50,440
Đây có thể là lớn hơn
chúng tôi nghĩ rằng đó là.

1067
00:47:50,440 --> 00:47:52,720
Bởi vì luôn có một số góc
trường hợp với một tên dài điên.

1068
00:47:52,720 --> 00:47:56,360
Vì vậy, chúng ta hãy gọi nó k, nhưng nó vẫn là một
liên tục có lẽ, bởi vì mỗi

1069
00:47:56,360 --> 00:48:00,190
tên trên thế giới, ít nhất là trong một
quốc gia cụ thể, đó là chiều dài hoặc

1070
00:48:00,190 --> 00:48:01,780
ngắn hơn, vì vậy nó không đổi.

1071
00:48:01,780 --> 00:48:04,490
Nhưng khi chúng tôi đã nói điều gì đó lớn
O của một giá trị cố định, những gì mà

1072
00:48:04,490 --> 00:48:07,760
thực sự tương đương với?

1073
00:48:07,760 --> 00:48:10,420
Đó thực sự là điều tương tự
cho biết thời gian liên tục.

1074
00:48:10,420 --> 00:48:11,530
>> Bây giờ chúng ta đang loại gian lận, phải không?

1075
00:48:11,530 --> 00:48:15,340
Chúng tôi đang loại tận dụng một số lý thuyết
đây để nói rằng tốt, thứ tự của k là

1076
00:48:15,340 --> 00:48:17,450
thực sự chỉ cần đặt hàng của một,
và đó là thời gian liên tục.

1077
00:48:17,450 --> 00:48:18,200
Nhưng nó thực sự là.

1078
00:48:18,200 --> 00:48:22,550
Bởi vì cái nhìn sâu sắc quan trọng ở đây là
nếu chúng ta có n tên đã có trong này

1079
00:48:22,550 --> 00:48:26,010
cấu trúc dữ liệu, và chúng tôi chèn Maxwell,
là lượng thời gian cần chúng tôi

1080
00:48:26,010 --> 00:48:29,530
chèn Maxwell ở tất cả bị ảnh hưởng
bao nhiêu người khác

1081
00:48:29,530 --> 00:48:31,100
là trong cấu trúc dữ liệu?

1082
00:48:31,100 --> 00:48:31,670
Dường như không có.

1083
00:48:31,670 --> 00:48:36,280
Nếu tôi có một tỷ phần nhiều đến thế này
Trie, và sau đó chèn Maxwell, được

1084
00:48:36,280 --> 00:48:38,650
ông ở tất cả các ảnh hưởng?

1085
00:48:38,650 --> 00:48:39,050
Không.

1086
00:48:39,050 --> 00:48:42,950
Và đó là không giống như bất kỳ dữ liệu ngày
cấu trúc, chúng tôi đã nhìn thấy vậy, đến nay, nơi

1087
00:48:42,950 --> 00:48:46,820
thời gian chạy của thuật toán của bạn là
hoàn toàn độc lập với bao nhiêu

1088
00:48:46,820 --> 00:48:51,430
là công cụ hoặc chưa được
trong cấu trúc dữ liệu.

1089
00:48:51,430 --> 00:48:54,650
>> Và như vậy với điều này dành cho bạn bây giờ là một
cơ hội cho p bộ sáu, sẽ

1090
00:48:54,650 --> 00:48:58,310
một lần nữa liên quan đến việc thực hiện của riêng bạn
kiểm tra chính tả, đọc trong 150.000

1091
00:48:58,310 --> 00:49:01,050
từ ngữ, cách tốt nhất để lưu trữ mà
không nhất thiết phải rõ ràng.

1092
00:49:01,050 --> 00:49:04,030
Và mặc dù tôi đã khao khát tìm
Chén thánh, tôi không

1093
00:49:04,030 --> 00:49:05,330
cho rằng một Trie là.

1094
00:49:05,330 --> 00:49:09,810
Trong thực tế, một bảng băm có thể rất tốt
chứng minh được hiệu quả hơn.

1095
00:49:09,810 --> 00:49:10,830
Nhưng đó chỉ là -

1096
00:49:10,830 --> 00:49:14,620
đó chỉ là một trong những quyết định thiết kế
bạn sẽ phải thực hiện.

1097
00:49:14,620 --> 00:49:18,920
>> Nhưng trong đóng cửa, chúng ta hãy 50 hoặc hơn
giây để có một cái nhìn vào những gì nằm

1098
00:49:18,920 --> 00:49:22,190
tuần trước tiếp theo và xa hơn nữa, chúng tôi chuyển tiếp
từ dòng lệnh này

1099
00:49:22,190 --> 00:49:26,220
thế giới nếu các chương trình C để điều web
dựa và các ngôn ngữ như PHP và

1100
00:49:26,220 --> 00:49:30,350
JavaScript và internet chính nó,
các giao thức như HTTP, mà bạn đã

1101
00:49:30,350 --> 00:49:32,870
dùng cho các cấp nhiều năm
bây giờ, và gõ hầu hết tất cả

1102
00:49:32,870 --> 00:49:34,440
ngày, có lẽ, hoặc nhìn thấy.

1103
00:49:34,440 --> 00:49:37,420
Và chúng tôi sẽ bắt đầu để vỏ lại
lớp của những gì là internet.

1104
00:49:37,420 --> 00:49:40,650
Và mã là những gì mà
nền tảng công cụ hiện nay.

1105
00:49:40,650 --> 00:49:43,230
Vì vậy, 50 giây trêu ghẹo này đây.

1106
00:49:43,230 --> 00:49:46,570
Tôi cung cấp cho bạn chiến binh của mạng Internet.

1107
00:49:46,570 --> 00:49:51,370
>> [VIDEO xem lại]

1108
00:49:51,370 --> 00:49:56,764
>> -Ông đến với một tin nhắn.

1109
00:49:56,764 --> 00:50:00,687
Với một giao thức tất cả của riêng mình.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Ông đến một thế giới của bức tường lửa độc ác,
không quan tâm thiết bị định tuyến, và nguy hiểm hơn

1112
00:50:19,780 --> 00:50:22,600
tồi tệ hơn cả cái chết.

1113
00:50:22,600 --> 00:50:23,590
Anh ấy nhanh.

1114
00:50:23,590 --> 00:50:25,300
Anh ấy mạnh mẽ.

1115
00:50:25,300 --> 00:50:27,700
Anh ấy là TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Và ông đã nhận địa chỉ của bạn.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Chiến binh của mạng Internet.

1119
00:50:34,590 --> 00:50:35,290
>> [END xem video]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: Đó là cách mạng Internet
làm việc theo tuần tới.

1121
00:50:38,070 --> 00:50:40,406