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

2
00:00:00,500 --> 00:00:11,137
[MUSIC CHƠI]

3
00:00:11,137 --> 00:00:12,220
DAVID J. Malan: Được rồi.

4
00:00:12,220 --> 00:00:13,950
Đây là CS50.

5
00:00:13,950 --> 00:00:18,560
Đây là tuần năm tiếp tục, và chúng tôi
có một số tin tốt và một tin xấu.

6
00:00:18,560 --> 00:00:21,140
Vì vậy, tin tốt là CS50
ra mắt vào thứ sáu này.

7
00:00:21,140 --> 00:00:24,430
Nếu bạn muốn tham gia với chúng tôi,
đầu vào URL thông thường ở đây.

8
00:00:24,430 --> 00:00:28,670
Tin tức Thậm chí tốt hơn, không có bài giảng
này đến thứ hai 13.

9
00:00:28,670 --> 00:00:31,970
Hơi ít tin tức tốt hơn,
bài kiểm tra không là thứ tư tới.

10
00:00:31,970 --> 00:00:33,840
Thông tin chi tiết có thể
tìm thấy tại URL này ở đây.

11
00:00:33,840 --> 00:00:36,340
Và trong vài ngày tới
chúng tôi sẽ điền vào chỗ trống

12
00:00:36,340 --> 00:00:39,234
liên quan đến các phòng
rằng chúng tôi sẽ đã đặt.

13
00:00:39,234 --> 00:00:41,400
Tin tức tốt hơn là có sẽ thấy
được đánh giá quá trình toàn

14
00:00:41,400 --> 00:00:43,570
phiên này tới
Thứ hai vào buổi tối.

15
00:00:43,570 --> 00:00:46,270
Hãy theo dõi quá trình của
trang web cho vị trí và chi tiết.

16
00:00:46,270 --> 00:00:49,290
Phần, mặc dù nó là một
kỳ nghỉ, cũng sẽ đáp ứng là tốt.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Tin tức tốt nhất, giảng vào thứ sáu tới.

19
00:00:52,940 --> 00:00:56,220
Vì vậy, đây là một truyền thống chúng tôi
có, theo các giáo trình.

20
00:00:56,220 --> 00:00:58,100
Just-- nó sẽ là tuyệt vời.

21
00:00:58,100 --> 00:01:02,510
Bạn sẽ thấy những thứ như
thời gian cố định cấu trúc dữ liệu

22
00:01:02,510 --> 00:01:04,730
và các bảng và cây và cố gắng băm.

23
00:01:04,730 --> 00:01:07,150
Và chúng ta sẽ nói về vấn đề sinh nhật.

24
00:01:07,150 --> 00:01:09,440
Một bó toàn bộ công cụ
đang chờ đợi vào thứ sáu tới.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
OK.

27
00:01:12,200 --> 00:01:13,190
Nhưng dù sao.

28
00:01:13,190 --> 00:01:17,080
>> Vì vậy, nhớ lại rằng chúng ta đã
tập trung vào hình ảnh của những gì

29
00:01:17,080 --> 00:01:18,980
bên trong bộ nhớ máy tính của chúng tôi.

30
00:01:18,980 --> 00:01:22,875
Vì vậy, bộ nhớ hoặc bộ nhớ RAM là nơi mà các chương trình
tồn tại trong khi bạn đang chạy chúng.

31
00:01:22,875 --> 00:01:25,215
Nếu bạn kích đúp vào một
biểu tượng để chạy một số chương trình

32
00:01:25,215 --> 00:01:27,520
hoặc nhấp đúp vào một
biểu tượng để mở một số tập tin,

33
00:01:27,520 --> 00:01:30,430
nó được nạp từ đĩa cứng của bạn
ổ đĩa hoặc ổ đĩa trạng thái rắn

34
00:01:30,430 --> 00:01:34,190
vào bộ nhớ RAM, bộ nhớ truy cập ngẫu nhiên, nơi
nó sống cho đến khi bị cúp điện tắt,

35
00:01:34,190 --> 00:01:36,700
nắp máy tính xách tay đóng cửa,
hoặc bạn thoát khỏi chương trình.

36
00:01:36,700 --> 00:01:38,960
>> Bây giờ nhớ rằng,
mà bạn có thể có

37
00:01:38,960 --> 00:01:41,950
1 gigabyte những ngày này, 2
gigabyte, hoặc thậm chí nhiều hơn nữa,

38
00:01:41,950 --> 00:01:44,420
thường được đặt ra
cho một chương trình nhất định

39
00:01:44,420 --> 00:01:47,170
trong loại hình chữ nhật
mô hình khái niệm

40
00:01:47,170 --> 00:01:50,860
nhờ đó chúng ta có ngăn xếp ở phía dưới
và một loạt các công cụ khác ở đầu trang.

41
00:01:50,860 --> 00:01:53,140
Điều ở đầu
chúng tôi đã nhìn thấy trên hình ảnh này

42
00:01:53,140 --> 00:01:55,670
trước nhưng không bao giờ nói về
là cái gọi là đoạn văn bản.

43
00:01:55,670 --> 00:01:58,419
Đoạn văn bản chỉ là một cách ưa thích
nói rằng các số không và những người

44
00:01:58,419 --> 00:02:01,150
soạn chương trình biên dịch thực tế của bạn.

45
00:02:01,150 --> 00:02:03,910
>> Vì vậy, khi bạn nhấp đúp
Microsoft Word trên máy Mac hoặc máy PC của bạn,

46
00:02:03,910 --> 00:02:08,030
hoặc khi bạn chạy chấm giảm Mario trên
Máy tính Linux ở cửa sổ thiết bị đầu cuối của bạn,

47
00:02:08,030 --> 00:02:12,460
các số không và những người soạn
Word hoặc Mario được lưu trữ tạm thời

48
00:02:12,460 --> 00:02:16,610
trong bộ nhớ RAM của máy tính trong cái gọi là
đoạn văn bản cho một chương trình cụ thể.

49
00:02:16,610 --> 00:02:19,080
Dưới đây mà đi khởi tạo
và dữ liệu chưa được khởi tạo.

50
00:02:19,080 --> 00:02:22,655
Đây là công cụ như biến toàn cầu,
mà chúng tôi đã không được sử dụng nhiều,

51
00:02:22,655 --> 00:02:24,910
nhưng vào dịp chúng tôi đã
đã biến toàn cầu

52
00:02:24,910 --> 00:02:28,819
hay tĩnh xác định chuỗi
được mã hóa cứng từ như "hello"

53
00:02:28,819 --> 00:02:31,860
không được thực hiện trong từ người sử dụng
được mã hóa cứng vào chương trình của bạn.

54
00:02:31,860 --> 00:02:34,230
>> Bây giờ, xuống phía dưới chúng tôi
có cái gọi là chồng.

55
00:02:34,230 --> 00:02:37,665
Và chồng, cho đến nay, chúng tôi đã
sử dụng cho những loại mục đích?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Có gì ngăn xếp được sử dụng cho?

58
00:02:40,997 --> 00:02:41,160
Vâng?

59
00:02:41,160 --> 00:02:42,070
>> TƯỢNG: Chức năng.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. Malan: Đối với chức năng?

61
00:02:43,320 --> 00:02:44,980
Trong ý nghĩa nào cho các chức năng?

62
00:02:44,980 --> 00:02:48,660
>> TƯỢNG: Khi bạn gọi một chức năng,
đối số được sao chép vào stack.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. Malan: Chính xác.

64
00:02:49,660 --> 00:02:52,650
Khi bạn gọi một chức năng, nó
đối số được sao chép vào stack.

65
00:02:52,650 --> 00:02:56,330
Vì vậy, bất kỳ của X hoặc Y hoặc A hoặc B
rằng bạn đang đi vào một chức năng

66
00:02:56,330 --> 00:02:58,680
được tạm thời đưa vào
cái gọi là chồng,

67
00:02:58,680 --> 00:03:02,000
giống như một trong những Annenberg
khay phòng ăn, và cũng có những thứ

68
00:03:02,000 --> 00:03:03,190
như các biến địa phương.

69
00:03:03,190 --> 00:03:06,290
Nếu chức năng foo hoặc trao đổi của bạn
chức năng có các biến địa phương,

70
00:03:06,290 --> 00:03:08,602
như nhiệt độ, hai
kết thúc trên stack.

71
00:03:08,602 --> 00:03:11,560
Bây giờ, chúng tôi sẽ không nói quá nhiều về
họ, nhưng các biến môi trường

72
00:03:11,560 --> 00:03:15,690
ở phía dưới chúng ta đã thấy trong một thời gian trước khi
Tôi đã futzing vào bàn phím một ngày

73
00:03:15,690 --> 00:03:20,050
và tôi bắt đầu truy cập thứ
như argv 100 hoặc argv 1000,

74
00:03:20,050 --> 00:03:22,320
chỉ elements-- tôi quên
các numbers-- nhưng điều đó

75
00:03:22,320 --> 00:03:24,330
đã không có quyền được truy cập bởi tôi.

76
00:03:24,330 --> 00:03:26,581
Chúng tôi bắt đầu nhìn thấy một số
biểu tượng sôi nổi trên màn hình.

77
00:03:26,581 --> 00:03:28,330
Đó là những cái gọi là
biến môi trường

78
00:03:28,330 --> 00:03:32,390
như thiết lập chung cho tôi
chương trình cho máy tính của tôi, không

79
00:03:32,390 --> 00:03:37,090
không liên quan đến gần đây
lỗi mà chúng ta đã thảo luận,

80
00:03:37,090 --> 00:03:39,670
Shellshock, đó là được
gây rắc rối cho một vài máy tính.

81
00:03:39,670 --> 00:03:42,960
>> Bây giờ cuối cùng, tập trung ngày hôm nay
cuối cùng chúng ta sẽ có trên heap.

82
00:03:42,960 --> 00:03:44,864
Đây là một đoạn bộ nhớ.

83
00:03:44,864 --> 00:03:47,030
Và về cơ bản tất cả điều này
bộ nhớ là những thứ tương tự.

84
00:03:47,030 --> 00:03:48,040
Đó là cùng một phần cứng.

85
00:03:48,040 --> 00:03:49,956
Chúng tôi loại
điều trị các cụm khác nhau

86
00:03:49,956 --> 00:03:51,460
của byte cho các mục đích khác nhau.

87
00:03:51,460 --> 00:03:56,540
Các đống cũng sẽ là nơi
biến và bộ nhớ mà bạn yêu cầu

88
00:03:56,540 --> 00:03:58,810
từ hệ điều hành
được lưu trữ tạm thời.

89
00:03:58,810 --> 00:04:01,890
>> Nhưng có loại của một vấn đề
ở đây, như hình ảnh ngụ ý.

90
00:04:01,890 --> 00:04:05,261
Chúng tôi có hai loại
tàu sắp va chạm.

91
00:04:05,261 --> 00:04:08,010
Bởi vì khi bạn sử dụng nhiều hơn và nhiều hơn nữa
của chồng, và như chúng ta thấy ngày nay

92
00:04:08,010 --> 00:04:11,800
trở đi, khi bạn sử dụng nhiều hơn và nhiều hơn nữa của
đống, chắc chắn những điều xấu có thể xảy ra.

93
00:04:11,800 --> 00:04:15,054
Và quả thực, chúng ta có thể tạo ra mà
cố ý hoặc vô ý.

94
00:04:15,054 --> 00:04:16,970
Vì vậy, cuối cùng cliffhanger
thời gian là chương trình này,

95
00:04:16,970 --> 00:04:20,570
mà không phục vụ cho bất kỳ chức năng
mục đích nào khác hơn là để chứng minh

96
00:04:20,570 --> 00:04:24,750
làm thế nào bạn như một kẻ xấu thực sự có thể
lợi dụng lỗi trong chương trình của một ai đó

97
00:04:24,750 --> 00:04:28,460
và đi qua một chương trình hoặc thậm chí một
toàn bộ hệ thống máy tính hoặc máy chủ.

98
00:04:28,460 --> 00:04:31,660
Như vậy chỉ cần lướt qua một thời gian ngắn, bạn
nhận thấy rằng chính ở phía dưới

99
00:04:31,660 --> 00:04:34,510
mất trong dòng lệnh
lập luận, theo argv.

100
00:04:34,510 --> 00:04:38,480
Và nó có một cuộc gọi đến một hàm f,
cơ bản là một chức năng không tên gọi

101
00:04:38,480 --> 00:04:40,250
f, và nó đi qua trong argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Vì vậy, bất cứ điều gì từ các loại sử dụng trong lúc
dấu nhắc sau khi tên của chương trình này,

103
00:04:43,960 --> 00:04:49,310
và sau đó chức năng này tùy ý lên
đầu, e, mất trong một chuỗi, AKA char *,

104
00:04:49,310 --> 00:04:51,720
như chúng tôi đã bắt đầu thảo luận,
và nó chỉ gọi nó là "quán bar."

105
00:04:51,720 --> 00:04:53,310
Nhưng chúng ta có thể gọi nó là bất cứ điều gì.

106
00:04:53,310 --> 00:04:57,470
Và sau đó nó tuyên bố, bên trong
f, một mảng ký tự

107
00:04:57,470 --> 00:04:59,930
gọi là c-- 12 ký tự như vậy.

108
00:04:59,930 --> 00:05:03,580
>> Bây giờ, bởi những câu chuyện tôi đã nói
một thời điểm trước đây, nơi mà trong bộ nhớ

109
00:05:03,580 --> 00:05:06,720
là c, hoặc là những người 12
ký tự sẽ kết thúc?

110
00:05:06,720 --> 00:05:07,570
Chỉ cần được rõ ràng.

111
00:05:07,570 --> 00:05:08,070
Vâng?

112
00:05:08,070 --> 00:05:08,590
>> TƯỢNG: Trên stack.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. Malan: Trên stack.

114
00:05:09,420 --> 00:05:10,720
Vì vậy, c là một biến địa phương.

115
00:05:10,720 --> 00:05:14,079
Chúng tôi đang yêu cầu 12 ký tự hoặc 12 byte.

116
00:05:14,079 --> 00:05:16,120
Những người sẽ kết thúc
về cái gọi là chồng.

117
00:05:16,120 --> 00:05:18,530
Bây giờ cuối cùng là chức năng khác này
đó là thực sự khá hữu ích,

118
00:05:18,530 --> 00:05:20,571
nhưng chúng tôi đã không thực sự sử dụng
nó chính mình, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Nó có nghĩa là sao chép chuỗi, nhưng
chỉ có n chữ cái, n ký tự.

121
00:05:25,200 --> 00:05:31,990
Vì vậy, n ký tự sẽ
sao chép từ thanh vào c.

122
00:05:31,990 --> 00:05:32,980
Và bao nhiêu?

123
00:05:32,980 --> 00:05:34,110
Chiều dài của thanh.

124
00:05:34,110 --> 00:05:36,330
Vì vậy, nói cách khác, đó
một dòng, strncopy,

125
00:05:36,330 --> 00:05:39,500
sẽ sao chép
hiệu quả thanh vào c.

126
00:05:39,500 --> 00:05:42,340
>> Bây giờ, chỉ để loại dự đoán
đạo đức của câu chuyện này,

127
00:05:42,340 --> 00:05:44,750
những gì là khả năng có vấn đề ở đây?

128
00:05:44,750 --> 00:05:49,710
Mặc dù chúng tôi đang kiểm tra chiều dài
thanh và đi qua nó vào strncopy,

129
00:05:49,710 --> 00:05:53,145
những gì được đường ruột của bạn nói với bạn là
vẫn bị hỏng về chương trình này?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Vâng?

132
00:05:55,220 --> 00:05:57,491
>> TƯỢNG: Không bao gồm
phòng cho các ký tự null.

133
00:05:57,491 --> 00:05:59,990
DAVID J. Malan: Không bao gồm
phòng cho các ký tự null.

134
00:05:59,990 --> 00:06:02,073
Có khả năng, không giống như trong
thực hành qua, chúng tôi thậm chí không

135
00:06:02,073 --> 00:06:04,810
có rất nhiều như là một cộng thêm 1 để
thích rằng nhân vật null.

136
00:06:04,810 --> 00:06:06,649
Nhưng nó thậm chí còn tệ hơn nữa.

137
00:06:06,649 --> 00:06:07,940
Chúng tôi những gì khác không làm gì?

138
00:06:07,940 --> 00:06:08,432
Vâng?

139
00:06:08,432 --> 00:06:09,307
>> TƯỢNG: [không nghe được]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
DAVID J. Malan: hoàn hảo.

142
00:06:16,440 --> 00:06:18,490
Chúng tôi đã cứng mã hoá 12 khá tùy tiện.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Đó không phải là quá nhiều
vấn đề, nhưng thực tế

145
00:06:21,330 --> 00:06:25,630
mà chúng ta thậm chí không kiểm tra nếu
chiều dài của thanh là dưới 12,

146
00:06:25,630 --> 00:06:28,530
trong trường hợp này sẽ là
an toàn để đặt nó vào trong bộ nhớ

147
00:06:28,530 --> 00:06:30,260
gọi là c mà chúng tôi đã được phân bổ.

148
00:06:30,260 --> 00:06:32,960
Thật vậy, nếu thanh giống như
20 ký tự,

149
00:06:32,960 --> 00:06:39,010
chức năng này dường như được sao chép
20 nhân vật từ thanh vào c, do đó

150
00:06:39,010 --> 00:06:41,310
tham gia ít nhất 8 byte
rằng nó không nên.

151
00:06:41,310 --> 00:06:42,690
Đó là ý nghĩa ở đây.

152
00:06:42,690 --> 00:06:44,347
>> Vì vậy, trong ngắn hạn chương trình, bị hỏng.

153
00:06:44,347 --> 00:06:45,180
Không phải là một vấn đề lớn.

154
00:06:45,180 --> 00:06:46,360
Có lẽ bạn nhận được một lỗi phân khúc.

155
00:06:46,360 --> 00:06:47,651
Tất cả chúng ta đã có lỗi trong chương trình.

156
00:06:47,651 --> 00:06:50,196
Chúng ta đều có thể có lỗi
trong các chương trình ngay bây giờ.

157
00:06:50,196 --> 00:06:51,320
Tuy nhiên, ý nghĩa là gì?

158
00:06:51,320 --> 00:06:54,390
Vâng, đây là một phiên bản thu nhỏ trong các
mà hình ảnh của bộ nhớ máy tính của tôi.

159
00:06:54,390 --> 00:06:56,230
Đây là dưới cùng của ngăn xếp của tôi.

160
00:06:56,230 --> 00:06:59,644
Và quả thực, ở dưới cùng là những gì
gọi là chồng thường xuyên phụ huynh, cách ưa thích

161
00:06:59,644 --> 00:07:00,560
nói đó là chính.

162
00:07:00,560 --> 00:07:03,772
Vì vậy, bất cứ ai gọi là chức năng
e rằng chúng ta đang nói về.

163
00:07:03,772 --> 00:07:05,230
Vì vậy, đây là đáy của ngăn xếp.

164
00:07:05,230 --> 00:07:06,640
Địa chỉ trở lại là một cái gì đó mới.

165
00:07:06,640 --> 00:07:08,810
Nó luôn ở đó,
luôn ở trong hình ảnh đó.

166
00:07:08,810 --> 00:07:10,440
Chúng tôi không bao giờ được gọi là chú ý đến nó.

167
00:07:10,440 --> 00:07:15,290
Bởi vì nó chỉ ra các cách c công trình là
rằng khi một cuộc gọi chức năng khác,

168
00:07:15,290 --> 00:07:18,780
không chỉ làm các đối số cho rằng
chức năng được đẩy vào stack,

169
00:07:18,780 --> 00:07:22,470
không chỉ làm địa phương của hàm
biến được đẩy vào stack,

170
00:07:22,470 --> 00:07:26,820
một cái gì đó gọi là địa chỉ trở lại
cũng được đưa vào ngăn xếp.

171
00:07:26,820 --> 00:07:33,330
Cụ thể, nếu cuộc gọi chính foo, của chính
địa chỉ riêng trong bộ nhớ, con bò một cái gì đó,

172
00:07:33,330 --> 00:07:38,240
hiệu quả được đưa vào ngăn xếp
để khi f được thực hiện thực hiện nó

173
00:07:38,240 --> 00:07:43,630
biết nơi để nhảy trở lại trong văn bản
phân khúc để tiếp tục thực hiện.

174
00:07:43,630 --> 00:07:47,760
>> Vì vậy, nếu chúng ta ở đây khái niệm,
trong chính, sau đó f được gọi là.

175
00:07:47,760 --> 00:07:50,200
Làm thế nào để biết ai f
để kiểm soát tay trở lại?

176
00:07:50,200 --> 00:07:52,020
Vâng, điều này ít
mẩu bánh mì màu đỏ ở đây,

177
00:07:52,020 --> 00:07:54,978
được gọi là địa chỉ trả lại, nó chỉ
kiểm tra, địa chỉ trở lại là gì?

178
00:07:54,978 --> 00:07:57,039
Oh, hãy để tôi nhảy trở lại chính ở đây.

179
00:07:57,039 --> 00:07:59,080
Và đó là một chút
của một sự đơn giản hóa,

180
00:07:59,080 --> 00:08:00,750
vì số không và những người
cho chính về mặt kỹ thuật

181
00:08:00,750 --> 00:08:01,967
ở đây trong phân khúc công nghệ cao.

182
00:08:01,967 --> 00:08:03,800
Nhưng đó là ý tưởng. f
chỉ cần có để biết những gì

183
00:08:03,800 --> 00:08:06,680
đến nơi kiểm soát cuối cùng quay trở lại.

184
00:08:06,680 --> 00:08:09,790
>> Nhưng các máy tính cách
từ lâu đã đặt ra những điều

185
00:08:09,790 --> 00:08:12,320
như các biến địa phương và
đối số là như thế này.

186
00:08:12,320 --> 00:08:17,180
Vì vậy, trong đầu hình ảnh này trong
màu xanh là khung stack cho f, vì vậy tất cả

187
00:08:17,180 --> 00:08:19,630
của bộ nhớ f
đặc biệt là sử dụng.

188
00:08:19,630 --> 00:08:22,990
Vì vậy, theo đó, nhận thấy rằng
thanh là trong ảnh này.

189
00:08:22,990 --> 00:08:23,980
Bar là lập luận của mình.

190
00:08:23,980 --> 00:08:27,240
Và chúng tôi cho rằng lập luận để
chức năng được đẩy vào stack.

191
00:08:27,240 --> 00:08:29,910
Và c, tất nhiên, là
cũng trong ảnh này.

192
00:08:29,910 --> 00:08:33,520
>> Và chỉ cho mục đích ký hiệu,
nhận thấy ở góc phía trên bên trái

193
00:08:33,520 --> 00:08:37,020
là những gì sẽ là c khung 0 và
sau đó giảm nhẹ về bên phải

194
00:08:37,020 --> 00:08:38,220
là c khung 11.

195
00:08:38,220 --> 00:08:41,240
Vì vậy, nói cách khác, bạn có thể tưởng tượng
rằng có một mạng lưới các byte

196
00:08:41,240 --> 00:08:44,380
ở đó, đầu tiên là
trên bên trái, phía dưới đó

197
00:08:44,380 --> 00:08:48,360
là cuối cùng của những 12 byte.

198
00:08:48,360 --> 00:08:49,930
>> Nhưng bây giờ cố gắng để nhanh chóng về phía trước.

199
00:08:49,930 --> 00:08:55,580
Là những gì sắp xảy ra nếu chúng tôi vượt qua
trong một quán bar chuỗi dài hơn c?

200
00:08:55,580 --> 00:08:59,130
Và chúng tôi không kiểm tra nếu
nó thực sự dài hơn 12.

201
00:08:59,130 --> 00:09:03,146
Mà một phần của bức tranh này là sẽ
được ghi đè bởi byte 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, và sau đó
xấu, 12, 13 đến 19?

203
00:09:07,890 --> 00:09:11,820
Điều gì sẽ xảy ra ở đây,
nếu bạn suy ra từ đặt hàng

204
00:09:11,820 --> 00:09:14,790
mà khung c 0 là trên đầu trang
và c khung 11 là loại xuống

205
00:09:14,790 --> 00:09:15,812
bên phải?

206
00:09:15,812 --> 00:09:16,796
Vâng?

207
00:09:16,796 --> 00:09:19,260
>> TƯỢNG: Vâng, nó sẽ
để ghi đè lên char * quán bar.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. Malan: Vâng, có vẻ như
bạn sẽ ghi đè lên char * quán bar.

209
00:09:22,260 --> 00:09:26,245
Và tồi tệ hơn, nếu bạn gửi trong một thực sự lâu dài
chuỗi, bạn thậm chí có thể ghi đè lên những gì?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
Địa chỉ hồi âm.

212
00:09:28,570 --> 00:09:31,380
Mà một lần nữa, giống như một
mẩu bánh mì để cho các chương trình mà

213
00:09:31,380 --> 00:09:34,060
quay trở lại khi f
được thực hiện được gọi.

214
00:09:34,060 --> 00:09:37,140
>> Vì vậy, những gì kẻ xấu thường làm
là nếu họ đi qua một chương trình

215
00:09:37,140 --> 00:09:41,290
rằng họ đang tò mò xem là
khai thác, lỗi theo cách như vậy

216
00:09:41,290 --> 00:09:43,550
rằng họ có thể mất
lợi dụng lỗi,

217
00:09:43,550 --> 00:09:45,720
nói chung là họ không nhận được
quyền này lần đầu tiên.

218
00:09:45,720 --> 00:09:48,590
Họ chỉ bắt đầu gửi, ví dụ,
chuỗi ngẫu nhiên vào chương trình của bạn,

219
00:09:48,590 --> 00:09:50,260
dù ở bàn phím,
hay nói thẳng là họ có thể

220
00:09:50,260 --> 00:09:52,740
viết một chương trình nhỏ để chỉ
tự động tạo ra các chuỗi,

221
00:09:52,740 --> 00:09:55,430
và bắt đầu đập vào chương trình của bạn bằng cách
gửi vào rất nhiều yếu tố đầu vào khác nhau

222
00:09:55,430 --> 00:09:56,340
ở độ dài khác nhau.

223
00:09:56,340 --> 00:09:58,990
>> Ngay sau khi tai nạn chương trình của bạn,
đó là một điều tuyệt vời.

224
00:09:58,990 --> 00:10:01,020
Bởi vì nó có nghĩa là ông
hay cô đã phát hiện ra

225
00:10:01,020 --> 00:10:02,660
những gì có lẽ thực sự là một lỗi.

226
00:10:02,660 --> 00:10:05,830
Và sau đó họ có thể nhận được thông minh hơn
và bắt đầu tập trung hẹp hơn

227
00:10:05,830 --> 00:10:07,420
làm thế nào để khai thác lỗi.

228
00:10:07,420 --> 00:10:11,480
Đặc biệt, những gì em có thể
làm là gửi, trong trường hợp tốt nhất, xin chào.

229
00:10:11,480 --> 00:10:12,210
Không có vấn đề lớn.

230
00:10:12,210 --> 00:10:14,750
Đó là một chuỗi đó là đủ ngắn.

231
00:10:14,750 --> 00:10:18,100
Nhưng nếu anh ta hoặc cô gửi,
và chúng tôi sẽ khái quát nó như là,

232
00:10:18,100 --> 00:10:20,890
tấn công code-- nên số không
và những người mà làm những việc

233
00:10:20,890 --> 00:10:25,150
như rm-rf, mà loại bỏ tất cả mọi thứ
từ ổ đĩa cứng hoặc gửi thư rác

234
00:10:25,150 --> 00:10:27,000
hoặc bằng cách nào đó tấn công máy tính này?

235
00:10:27,000 --> 00:10:29,570
>> Vì vậy, nếu mỗi người trong các
chữ cái từ A đến như biểu tượng,

236
00:10:29,570 --> 00:10:32,380
khái niệm, tấn công, tấn công,
tấn công, tấn công, một số mã xấu

237
00:10:32,380 --> 00:10:36,410
mà người khác đã viết, nhưng
nếu người đó là đủ thông minh

238
00:10:36,410 --> 00:10:40,790
không chỉ bao gồm tất cả
những rm-RFS, mà còn

239
00:10:40,790 --> 00:10:46,100
có vài byte cuối cùng của mình
là một con số tương ứng

240
00:10:46,100 --> 00:10:50,540
đến địa chỉ của mình
mình mã tấn công riêng

241
00:10:50,540 --> 00:10:53,820
rằng người đó đã thông qua chỉ
bằng cách cung cấp nó tại dấu nhắc,

242
00:10:53,820 --> 00:10:58,760
bạn có hiệu quả có thể lừa máy tính
vào nhận thấy khi f được thực hiện thực hiện,

243
00:10:58,760 --> 00:11:02,400
oh, đó là thời gian cho tôi để nhảy
trở lại địa chỉ trở lại màu đỏ.

244
00:11:02,400 --> 00:11:06,070
Nhưng vì người đó có bằng cách nào đó
chồng chéo địa chỉ trở lại

245
00:11:06,070 --> 00:11:09,602
với số lượng riêng của họ,
và họ đủ thông minh

246
00:11:09,602 --> 00:11:11,560
đã cấu hình mà
số để tham khảo, như bạn

247
00:11:11,560 --> 00:11:13,740
nhìn thấy trong siêu hàng đầu
bên trái góc đó,

248
00:11:13,740 --> 00:11:18,020
địa chỉ thực tế của máy tính
bộ nhớ của một số mã tấn công của họ,

249
00:11:18,020 --> 00:11:21,740
một kẻ xấu có thể lừa máy tính
vào thực thi mã riêng của mình.

250
00:11:21,740 --> 00:11:23,700
>> Và mã số đó, một lần nữa, có thể là bất cứ điều gì.

251
00:11:23,700 --> 00:11:26,120
Nó thường được gọi là
mã shell, mà chỉ là

252
00:11:26,120 --> 00:11:29,030
một cách khác để nói rằng nó không phải
nói chung là một cái gì đó đơn giản như rm-rf.

253
00:11:29,030 --> 00:11:32,340
Nó thực sự là một cái gì đó giống như Bash,
hoặc một chương trình thực tế mà đưa cho anh

254
00:11:32,340 --> 00:11:37,230
hoặc điều khiển chương trình của mình để thực hiện
bất cứ thứ gì họ muốn.

255
00:11:37,230 --> 00:11:40,210
Vì vậy, trong ngắn hạn, điều này tất cả
xuất phát từ thực tế đơn giản

256
00:11:40,210 --> 00:11:44,490
rằng lỗi này liên quan không kiểm tra
ranh giới của mảng của bạn.

257
00:11:44,490 --> 00:11:47,250
Và bởi vì đường
máy tính làm việc là họ

258
00:11:47,250 --> 00:11:49,430
sử dụng ngăn xếp từ
hiệu quả, khái niệm,

259
00:11:49,430 --> 00:11:54,830
dưới lên trên, nhưng sau đó các yếu tố
bạn đẩy vào ngăn xếp phát triển trên xuống dưới,

260
00:11:54,830 --> 00:11:56,624
này là cực kỳ có vấn đề.

261
00:11:56,624 --> 00:11:58,290
Bây giờ, có nhiều cách để làm việc này.

262
00:11:58,290 --> 00:12:00,800
Và thẳng thắn mà nói, có những ngôn ngữ
mà để làm việc này.

263
00:12:00,800 --> 00:12:03,100
Java là miễn dịch, ví dụ,
đến vấn đề này cụ thể.

264
00:12:03,100 --> 00:12:04,110
Bởi vì họ không cung cấp cho bạn con trỏ.

265
00:12:04,110 --> 00:12:05,943
Họ không cung cấp cho bạn
địa chỉ bộ nhớ trực tiếp.

266
00:12:05,943 --> 00:12:08,560
Vì vậy, với quyền lực này mà chúng ta có
chạm vào bất cứ điều gì trong bộ nhớ

267
00:12:08,560 --> 00:12:11,580
chúng tôi muốn đến, thừa nhận, nguy cơ rất lớn.

268
00:12:11,580 --> 00:12:12,430
>> Vì vậy, giữ một mắt ra.

269
00:12:12,430 --> 00:12:14,596
Nếu, thẳng thắn, trong những tháng
hoặc năm tới, bất cứ lúc nào

270
00:12:14,596 --> 00:12:17,740
bạn đọc về một số khai thác
của một chương trình hoặc một máy chủ,

271
00:12:17,740 --> 00:12:22,370
nếu bạn đã bao giờ nhìn thấy một dấu hiệu của một cái gì đó
như một cuộc tấn công tràn bộ đệm,

272
00:12:22,370 --> 00:12:25,390
hoặc tràn stack là một kiểu khác
tấn công, tinh thần tương tự,

273
00:12:25,390 --> 00:12:28,770
nhiều như truyền cảm hứng cho trang web của
tên, nếu bạn biết điều đó,

274
00:12:28,770 --> 00:12:33,170
đó là tất cả nói về chỉ
tràn kích thước của một số nhân vật

275
00:12:33,170 --> 00:12:36,200
mảng hoặc một mảng nói chung.

276
00:12:36,200 --> 00:12:38,822
Mọi câu hỏi, sau đó, về điều này?

277
00:12:38,822 --> 00:12:39,780
Đừng cố gắng này ở nhà.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Tất cả các quyền.

280
00:12:42,300 --> 00:12:47,270
Vì vậy, malloc vậy, đến nay đã được mới của chúng tôi
người bạn ở đó chúng ta có thể cấp phát bộ nhớ

281
00:12:47,270 --> 00:12:50,540
mà chúng ta không nhất thiết phải biết
tiến mà chúng ta muốn nên chúng tôi không có

282
00:12:50,540 --> 00:12:52,920
cứng mã thành của chúng tôi
số chương trình như 12.

283
00:12:52,920 --> 00:12:55,550
Một khi người sử dụng cho chúng ta biết bao nhiêu
dữ liệu mà họ muốn đầu vào,

284
00:12:55,550 --> 00:12:58,000
chúng ta có thể malloc nhiều bộ nhớ.

285
00:12:58,000 --> 00:13:01,484
>> Vì vậy, malloc nó quay ra, vào
mức độ nào đó, chúng tôi đã sử dụng nó,

286
00:13:01,484 --> 00:13:03,900
một cách rõ ràng thời gian qua, và sau đó
các bạn đã được sử dụng nó

287
00:13:03,900 --> 00:13:08,160
cho GetString vô cho
vài tuần, tất cả các bộ nhớ của malloc

288
00:13:08,160 --> 00:13:09,820
xuất phát từ cái gọi là heap.

289
00:13:09,820 --> 00:13:13,852
Và đây là lý do tại sao getString, ví dụ,
có thể cấp phát bộ nhớ động

290
00:13:13,852 --> 00:13:16,060
mà không biết những gì bạn đang
sẽ đánh trước,

291
00:13:16,060 --> 00:13:21,520
trao lại cho bạn một con trỏ tới bộ nhớ,
và bộ nhớ vẫn là của bạn để giữ,

292
00:13:21,520 --> 00:13:24,080
ngay cả sau khi GetString lợi nhuận.

293
00:13:24,080 --> 00:13:27,450
Bởi vì thu hồi sau khi tất cả những gì
ngăn xếp được liên tục đi lên và xuống,

294
00:13:27,450 --> 00:13:27,950
lên và xuống.

295
00:13:27,950 --> 00:13:30,230
Và ngay khi nó đi
xuống, có nghĩa là bất kỳ bộ nhớ

296
00:13:30,230 --> 00:13:33,030
Chức năng này được sử dụng nên
không được sử dụng bởi bất cứ ai khác.

297
00:13:33,030 --> 00:13:34,570
Đó là giá trị rác bây giờ.

298
00:13:34,570 --> 00:13:36,120
>> Nhưng đống lên ở đây.

299
00:13:36,120 --> 00:13:39,360
Và những gì tốt đẹp về malloc là
khi malloc cấp phát bộ nhớ lên đây,

300
00:13:39,360 --> 00:13:42,070
nó không bị ảnh hưởng, cho
nhất một phần, bởi chồng.

301
00:13:42,070 --> 00:13:46,000
Và vì vậy bất kỳ chức năng có thể truy cập
bộ nhớ đã được malloc'd,

302
00:13:46,000 --> 00:13:49,120
ngay cả bởi một chức năng như getString,
ngay cả sau khi nó được trả về.

303
00:13:49,120 --> 00:13:51,700
>> Bây giờ, chuyện của malloc là miễn phí.

304
00:13:51,700 --> 00:13:53,900
Và quả thực, các quy tắc bạn
cần phải bắt đầu áp dụng

305
00:13:53,900 --> 00:13:58,950
là bất kỳ, bất kỳ, bất cứ lúc nào bạn sử dụng malloc
bản thân bạn phải sử dụng miễn phí, cuối cùng,

306
00:13:58,950 --> 00:14:00,280
vào đó con trỏ tương tự.

307
00:14:00,280 --> 00:14:03,289
Tất cả thời gian này, chúng tôi đã được viết
lỗi, mã lỗi, vì nhiều lý do.

308
00:14:03,289 --> 00:14:05,580
Tuy nhiên, một trong số đó đã được
sử dụng thư viện CS50, mà

309
00:14:05,580 --> 00:14:09,010
chính nó là cố tình
lỗi, nó rò rỉ bộ nhớ.

310
00:14:09,010 --> 00:14:11,410
Bất cứ lúc nào bạn đã gọi là getString
trong vài tuần qua

311
00:14:11,410 --> 00:14:13,870
chúng tôi yêu cầu các hoạt động
hệ thống, Linux, cho bộ nhớ.

312
00:14:13,870 --> 00:14:15,780
Và bạn đã bao giờ một lần cho nó trở lại.

313
00:14:15,780 --> 00:14:17,730
Và đây không phải là, trong
thực hành, một điều tốt.

314
00:14:17,730 --> 00:14:20,330
>> Và Valgrind, một trong những
các công cụ được giới thiệu trong Pset 4,

315
00:14:20,330 --> 00:14:22,900
là tất cả về giúp bạn
bây giờ tìm thấy lỗi như thế.

316
00:14:22,900 --> 00:14:27,060
Nhưng may mắn cho Pset 4 bạn không cần
sử dụng thư viện CS50 hoặc getString.

317
00:14:27,060 --> 00:14:31,220
Vì vậy, bất kỳ lỗi nào liên quan đến bộ nhớ
cuối cùng sẽ là của riêng bạn.

318
00:14:31,220 --> 00:14:34,060
>> Vì vậy, malloc là nhiều hơn chỉ
thuận tiện cho mục đích này.

319
00:14:34,060 --> 00:14:37,420
Chúng ta có thể thực hiện giải quyết
vấn đề cơ bản khác nhau,

320
00:14:37,420 --> 00:14:41,640
và cơ bản giải quyết vấn đề hơn
hiệu quả như là một lời hứa tuần số không.

321
00:14:41,640 --> 00:14:44,720
Cho đến nay đây là gợi cảm nhất
cấu trúc dữ liệu chúng ta đã có.

322
00:14:44,720 --> 00:14:47,804
Và bởi cấu trúc dữ liệu tôi chỉ có nghĩa là
một cách khái niệm bộ nhớ

323
00:14:47,804 --> 00:14:50,720
trong một cách mà vượt xa chỉ cần nói,
đây là một int, đây là một char.

324
00:14:50,720 --> 00:14:52,930
Chúng tôi có thể bắt đầu điều cụm lại với nhau.

325
00:14:52,930 --> 00:14:54,460
>> Vì vậy, một mảng trông như thế này.

326
00:14:54,460 --> 00:14:57,270
Và những gì là quan trọng trong khoảng một
mảng là nó cung cấp cho bạn

327
00:14:57,270 --> 00:14:59,724
back-to-back khối
bộ nhớ, mỗi trong số đó

328
00:14:59,724 --> 00:15:02,765
là có được cùng loại, int,
int, int, int, hoặc char, char, char,

329
00:15:02,765 --> 00:15:03,330
char.

330
00:15:03,330 --> 00:15:04,496
Nhưng có một vài nhược điểm.

331
00:15:04,496 --> 00:15:06,570
Điều này ví dụ, là
một mảng có kích thước sáu.

332
00:15:06,570 --> 00:15:10,650
Giả sử bạn điền vào mảng này với sáu
số và sau đó, vì bất cứ lý do,

333
00:15:10,650 --> 00:15:13,187
người dùng của bạn muốn cung cấp cho
bạn một số thứ bảy.

334
00:15:13,187 --> 00:15:14,020
Nơi nào bạn đặt nó?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Giải pháp là gì nếu bạn có
tạo ra một mảng trên stack,

337
00:15:18,990 --> 00:15:22,030
Ví dụ, chỉ với tuần
hai ký hiệu mà chúng tôi giới thiệu,

338
00:15:22,030 --> 00:15:23,730
trong dấu ngoặc vuông với một số bên trong?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Vâng, bạn đã có sáu
con số trong các ô.

341
00:15:27,260 --> 00:15:28,530
Những gì bản năng của bạn sẽ là gì?

342
00:15:28,530 --> 00:15:29,973
Trong trường hợp bạn muốn đặt nó?

343
00:15:29,973 --> 00:15:30,860
>> TƯỢNG: [không nghe được]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. Malan: Xin lỗi?

345
00:15:31,315 --> 00:15:32,380
>> TƯỢNG: Đặt nó vào cuối.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. Malan: Đặt nó vào cuối.

347
00:15:33,796 --> 00:15:35,880
Vì vậy, chỉ hơn bên phải,
bên ngoài của hộp này.

348
00:15:35,880 --> 00:15:38,710
Đó sẽ là tốt đẹp, nhưng nó
Hóa ra bạn không thể làm điều đó.

349
00:15:38,710 --> 00:15:41,350
Bởi vì nếu bạn đã không hỏi
cho đoạn này của bộ nhớ,

350
00:15:41,350 --> 00:15:44,490
nó có thể là do trùng hợp ngẫu nhiên rằng điều này
đang được sử dụng bởi một số biến khác

351
00:15:44,490 --> 00:15:45,030
hoàn toàn.

352
00:15:45,030 --> 00:15:49,210
Hãy suy nghĩ lại một tuần hoặc lâu hơn khi chúng ta đặt
ra Zamyla và Davin và Gabe của tên

353
00:15:49,210 --> 00:15:49,930
trong bộ nhớ.

354
00:15:49,930 --> 00:15:51,638
Họ nghĩa đen
trở lại trở lại trở lại.

355
00:15:51,638 --> 00:15:53,550
Vì vậy, chúng ta có thể không nhất thiết phải
tin tưởng rằng bất cứ điều gì của

356
00:15:53,550 --> 00:15:55,800
ở đây có sẵn cho tôi để sử dụng.

357
00:15:55,800 --> 00:15:56,990
>> Vì vậy, những gì khác bạn có thể làm gì?

358
00:15:56,990 --> 00:16:00,282
Vâng, một khi nhận ra bạn
cần một mảng có kích thước bảy,

359
00:16:00,282 --> 00:16:02,490
bạn chỉ có thể tạo ra một
mảng có kích thước bảy sau đó sử dụng

360
00:16:02,490 --> 00:16:05,950
một vòng lặp hoặc một vòng lặp trong khi,
sao chép nó vào mảng mới,

361
00:16:05,950 --> 00:16:09,680
và sau đó bằng cách nào đó chỉ có được loại bỏ
mảng này hoặc chỉ cần ngừng sử dụng nó.

362
00:16:09,680 --> 00:16:12,130
Nhưng đó không phải là đặc biệt hiệu quả.

363
00:16:12,130 --> 00:16:15,340
Trong ngắn hạn, các mảng không cho phép
bạn tự động thay đổi kích thước.

364
00:16:15,340 --> 00:16:17,900
>> Vì vậy, một mặt bạn sẽ có được
truy cập ngẫu nhiên, mà là tuyệt vời.

365
00:16:17,900 --> 00:16:20,108
Bởi vì nó cho phép chúng tôi làm những việc
như phân chia và chinh phục,

366
00:16:20,108 --> 00:16:23,100
tìm kiếm nhị phân, tất cả chúng tôi đã
nói về trên màn hình ở đây.

367
00:16:23,100 --> 00:16:24,950
Nhưng bạn vẽ mình vào một góc.

368
00:16:24,950 --> 00:16:27,810
Ngay sau khi bạn nhấn
kết thúc của mảng của bạn,

369
00:16:27,810 --> 00:16:29,980
bạn phải làm rất
hoạt động đắt tiền

370
00:16:29,980 --> 00:16:33,910
hoặc viết một bó toàn bộ mã
đến nay giải quyết vấn đề đó.

371
00:16:33,910 --> 00:16:36,680
>> Vì vậy, nếu thay vào đó chúng tôi đã có
một cái gì đó gọi là một danh sách,

372
00:16:36,680 --> 00:16:38,820
hoặc một danh sách liên kết đặc biệt?

373
00:16:38,820 --> 00:16:41,930
Điều gì nếu thay vì phải
hình chữ nhật sao lưu để sao lưu để sao lưu,

374
00:16:41,930 --> 00:16:45,730
chúng tôi có hình chữ nhật để lại một chút
bit của căn phòng thoải mái ở giữa chúng?

375
00:16:45,730 --> 00:16:49,670
Và mặc dù tôi đã vẽ này
hình ảnh hoặc điều chỉnh hình ảnh này

376
00:16:49,670 --> 00:16:54,696
từ một trong những văn bản vào đây để được trở lại
trở lại trở lại rất có trật tự, trong thực tế,

377
00:16:54,696 --> 00:16:56,820
một trong những hình chữ nhật
có thể lên ở đây trong bộ nhớ.

378
00:16:56,820 --> 00:16:58,028
Một trong số đó có thể lên ở đây.

379
00:16:58,028 --> 00:17:00,420
Một trong số đó có thể lên đây,
ở đây, và vv.

380
00:17:00,420 --> 00:17:02,910
>> Nhưng nếu chúng ta thu hút,
trong trường hợp này, mũi tên

381
00:17:02,910 --> 00:17:05,650
mà bằng cách nào đó liên kết các
hình chữ nhật với nhau?

382
00:17:05,650 --> 00:17:08,170
Thật vậy, chúng tôi đã nhìn thấy một kỹ thuật
hóa thân của một mũi tên.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Chúng ta đã sử dụng trong gần đây
ngày đó, bên dưới mui xe,

385
00:17:13,710 --> 00:17:15,210
là đại diện của một mũi tên?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Một con trỏ, phải không?

388
00:17:17,349 --> 00:17:19,780
>> Vì vậy, nếu những gì, thay vì
chỉ lưu trữ các số,

389
00:17:19,780 --> 00:17:23,130
như 9, 17, 22, 26, 34,
nếu chúng ta không lưu trữ

390
00:17:23,130 --> 00:17:27,079
chỉ có một số nhưng một con trỏ
bên cạnh mỗi số như vậy?

391
00:17:27,079 --> 00:17:30,690
Vì vậy, giống như bạn sẽ một sợi
kim thông qua một bó toàn bộ vải,

392
00:17:30,690 --> 00:17:32,950
điều bằng cách nào đó buộc
với nhau, tương tự có thể

393
00:17:32,950 --> 00:17:35,550
chúng tôi với con trỏ, như
nhập thể bởi mũi tên ở đây,

394
00:17:35,550 --> 00:17:38,550
loại đan xen với nhau
các hình chữ nhật cá nhân

395
00:17:38,550 --> 00:17:41,780
bởi hiệu quả sử dụng một con trỏ
bên cạnh mỗi số đó

396
00:17:41,780 --> 00:17:46,065
chỉ ra một số số tiếp theo, đó
chỉ ra, lần lượt, một số số tiếp theo?

397
00:17:46,065 --> 00:17:47,940
Vì vậy, nói cách khác, những gì
nếu chúng ta thực sự muốn

398
00:17:47,940 --> 00:17:49,820
để thực hiện một cái gì đó như thế này?

399
00:17:49,820 --> 00:17:53,610
Cũng may, những hình chữ nhật,
ít nhất là một với 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
và vv, đây là những không còn
quảng trường đẹp với những con số duy nhất.

401
00:17:57,040 --> 00:17:59,960
Phía dưới, hình chữ nhật
9 dưới đây, ví dụ,

402
00:17:59,960 --> 00:18:04,330
đại diện cho những gì nên
là một con trỏ, 32 bit.

403
00:18:04,330 --> 00:18:09,460
Bây giờ, tôi chưa biết về bất kỳ kiểu dữ liệu
trong C cung cấp cho bạn không chỉ là một int

404
00:18:09,460 --> 00:18:11,630
nhưng một con trỏ hoàn toàn.

405
00:18:11,630 --> 00:18:15,020
>> Vì vậy, giải pháp là gì nếu chúng ta muốn
phát minh ra câu trả lời của chúng tôi với điều này?

406
00:18:15,020 --> 00:18:15,760
Vâng?

407
00:18:15,760 --> 00:18:16,640
>> TƯỢNG: [không nghe được]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. Malan: Cái gì thế?

409
00:18:17,360 --> 00:18:17,880
>> TƯỢNG: cấu trúc mới.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. Malan: Vâng, vậy tại sao
chúng ta không tạo ra một cấu trúc mới,

411
00:18:19,590 --> 00:18:20,920
hoặc C, một cấu trúc?

412
00:18:20,920 --> 00:18:25,990
Chúng tôi đã nhìn thấy cấu trúc trước đây, nếu một thời gian ngắn,
nơi mà chúng tôi xử lý một cấu trúc sinh viên

413
00:18:25,990 --> 00:18:27,780
như thế này, những người có một cái tên và một ngôi nhà.

414
00:18:27,780 --> 00:18:31,980
Trong Pset 3 đột phá mà bạn sử dụng toàn bộ
bó GRect structs-- và GOvals

415
00:18:31,980 --> 00:18:34,810
mà Stanford tạo ra để
thông tin cụm lại với nhau.

416
00:18:34,810 --> 00:18:38,580
Vì vậy, nếu chúng ta có ý tưởng này cùng
các từ khóa "typedef" và "cấu trúc"

417
00:18:38,580 --> 00:18:42,890
và sau đó một số công cụ sinh viên cụ thể,
và phát triển này như sau:

418
00:18:42,890 --> 00:18:46,210
struct node-- và nút là
chỉ là một khoa học máy tính rất chung chung

419
00:18:46,210 --> 00:18:49,980
hạn cho một cái gì đó trong một cấu trúc dữ liệu,
một thùng chứa trong một cấu trúc dữ liệu.

420
00:18:49,980 --> 00:18:53,900
Một nút tôi yêu cầu là sẽ có
một int n, hoàn toàn đơn giản,

421
00:18:53,900 --> 00:18:58,810
và sau đó một chút khó hiểu hơn,
Dòng thứ hai này, cấu trúc nút * tiếp theo.

422
00:18:58,810 --> 00:19:01,300
Nhưng về kỹ thuật ít hơn,
dòng thứ hai là gì

423
00:19:01,300 --> 00:19:02,980
mã bên trong dấu ngoặc nhọn?

424
00:19:02,980 --> 00:19:03,737
Vâng?

425
00:19:03,737 --> 00:19:04,851
>> TƯỢNG: [không nghe được]

426
00:19:04,851 --> 00:19:06,600
DAVID J. Malan: Một
con trỏ đến một nút khác.

427
00:19:06,600 --> 00:19:09,910
Vì vậy, phải thừa nhận rằng, cú pháp một chút khó hiểu.

428
00:19:09,910 --> 00:19:13,250
Nhưng nếu bạn đọc nó theo nghĩa đen,
tiếp theo là tên của một biến.

429
00:19:13,250 --> 00:19:14,410
Kiểu dữ liệu của nó là gì?

430
00:19:14,410 --> 00:19:18,206
Đó là một chút dài dòng thời gian này,
nhưng nó có cấu trúc kiểu nút *.

431
00:19:18,206 --> 00:19:22,960
Bất cứ lúc nào chúng tôi đã nhìn thấy một cái gì đó sao, mà
có nghĩa là nó là một con trỏ đến kiểu dữ liệu.

432
00:19:22,960 --> 00:19:26,810
Vì vậy, tiếp theo rõ ràng là một
con trỏ đến một nút cấu trúc.

433
00:19:26,810 --> 00:19:28,310
>> Bây giờ, một nút cấu trúc là gì?

434
00:19:28,310 --> 00:19:31,044
Vâng, chú ý bạn sẽ thấy những
cùng một từ ở bên phải.

435
00:19:31,044 --> 00:19:33,960
Và quả thực, bạn cũng thấy từ
"Nút" xuống đây ở dưới cùng bên trái.

436
00:19:33,960 --> 00:19:35,640
Và điều này thực sự chỉ là một tiện nghi.

437
00:19:35,640 --> 00:19:39,930
Chú ý rằng trong định nghĩa sinh viên của chúng tôi
có từ "sinh viên" chỉ một lần.

438
00:19:39,930 --> 00:19:42,510
Và đó là bởi vì một sinh viên
đối tượng không được tự tham chiếu.

439
00:19:42,510 --> 00:19:45,340
Không có gì bên trong của một học sinh là
cần để trỏ đến học sinh khác,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Đó sẽ là loại
kỳ lạ trong thế giới thực.

442
00:19:47,630 --> 00:19:50,880
>> Nhưng với một nút trong một liên kết
danh sách, chúng tôi muốn có một nút

443
00:19:50,880 --> 00:19:53,970
được tham chiếu đến một đối tượng tương tự.

444
00:19:53,970 --> 00:19:57,900
Và vì thế nhận thấy sự thay đổi ở đây không phải là
chỉ là những gì bên trong các dấu ngoặc nhọn.

445
00:19:57,900 --> 00:20:00,800
Nhưng chúng ta thêm từ "nút"
ở đầu cũng như

446
00:20:00,800 --> 00:20:02,930
thêm nó vào phía dưới
thay cho "học sinh."

447
00:20:02,930 --> 00:20:06,000
Và đây chỉ là một chi tiết kỹ thuật
do đó, một lần nữa, cấu trúc dữ liệu của bạn

448
00:20:06,000 --> 00:20:11,380
có thể tự tham chiếu, do đó một
nút có thể trỏ đến một nút khác như vậy.

449
00:20:11,380 --> 00:20:13,840
>> Vì vậy, đây là những gì cuối cùng
sẽ có ý nghĩa đối với chúng ta?

450
00:20:13,840 --> 00:20:17,560
Vâng, một, công cụ này bên trong
là nội dung của nút của chúng tôi.

451
00:20:17,560 --> 00:20:19,360
Điều này lên đây,
trên bên phải, chỉ là như vậy

452
00:20:19,360 --> 00:20:20,860
rằng, một lần nữa, chúng ta có thể tham khảo cho mình.

453
00:20:20,860 --> 00:20:23,401
Và sau đó những thứ ngoài cùng,
mặc dù nút là một thuật ngữ mới,

454
00:20:23,401 --> 00:20:25,500
có lẽ, nó vẫn còn
giống như học sinh và những gì

455
00:20:25,500 --> 00:20:27,520
là dưới mui xe trong SPL.

456
00:20:27,520 --> 00:20:31,095
>> Vì vậy, nếu bây giờ chúng ta muốn bắt đầu
thực hiện danh sách liên kết này,

457
00:20:31,095 --> 00:20:33,220
làm thế nào chúng ta có thể dịch
một cái gì đó như thế này để mã?

458
00:20:33,220 --> 00:20:35,350
Vâng, chúng ta chỉ thấy một
ví dụ về một chương trình

459
00:20:35,350 --> 00:20:36,840
thực sự sử dụng một danh sách liên kết.

460
00:20:36,840 --> 00:20:40,870
Trong số đang phân phối hiện nay
là một chương trình được gọi là Danh sách Zero.

461
00:20:40,870 --> 00:20:44,980
Và nếu tôi chạy này tôi tạo ra một siêu
giao diện đơn giản, giao diện đồ họa người dùng,

462
00:20:44,980 --> 00:20:46,460
nhưng nó thực sự chỉ là printf.

463
00:20:46,460 --> 00:20:50,930
Và bây giờ tôi đã cho bản thân mình một vài đơn
options-- Xóa, Chèn, tìm kiếm,

464
00:20:50,930 --> 00:20:51,750
và Traverse.

465
00:20:51,750 --> 00:20:52,630
Và Thoát.

466
00:20:52,630 --> 00:20:55,970
Đây là những hoạt động phổ biến chỉ trên
cấu trúc dữ liệu được biết đến như một danh sách liên kết.

467
00:20:55,970 --> 00:20:58,409
>> Bây giờ, xóa sẽ
xóa một số từ danh sách.

468
00:20:58,409 --> 00:21:00,200
Chèn sẽ thêm
một số vào danh sách.

469
00:21:00,200 --> 00:21:02,181
Tìm kiếm được sẽ xem xét
cho số lượng trong danh sách.

470
00:21:02,181 --> 00:21:04,930
Và đi qua chỉ là một cách ưa thích
nói, đi bộ qua danh sách,

471
00:21:04,930 --> 00:21:06,245
in nó ra, nhưng đó là nó.

472
00:21:06,245 --> 00:21:07,720
Không thay đổi nó bằng mọi cách.

473
00:21:07,720 --> 00:21:08,570
>> Vì vậy, hãy cố gắng này.

474
00:21:08,570 --> 00:21:10,160
Chúng ta hãy đi trước và loại 2.

475
00:21:10,160 --> 00:21:12,710
Và sau đó tôi sẽ
chèn số, nói 9.

476
00:21:12,710 --> 00:21:13,620
Enter.

477
00:21:13,620 --> 00:21:17,480
Và giờ đây, chương trình của tôi chỉ là
lập trình để nói, bây giờ là danh sách 9.

478
00:21:17,480 --> 00:21:20,190
Bây giờ, nếu tôi đi trước và
làm Chèn một lần nữa, chúng ta hãy

479
00:21:20,190 --> 00:21:23,680
tôi đi trước và thu nhỏ và gõ 17.

480
00:21:23,680 --> 00:21:25,770
Bây giờ danh sách của tôi là 9, sau đó 17.

481
00:21:25,770 --> 00:21:27,750
Nếu tôi làm chèn một lần nữa, chúng ta hãy bỏ qua một.

482
00:21:27,750 --> 00:21:32,400
Thay vì 22, theo hình ảnh chúng tôi đã
được xem xét ở đây, hãy để tôi nhảy trước

483
00:21:32,400 --> 00:21:34,630
và chèn 26 tới.

484
00:21:34,630 --> 00:21:36,230
Vì vậy, tôi sẽ gõ 26.

485
00:21:36,230 --> 00:21:37,755
Danh sách này là như tôi mong đợi.

486
00:21:37,755 --> 00:21:40,630
Nhưng bây giờ, chỉ để xem nếu mã này
là có được linh hoạt, cho tôi bây giờ

487
00:21:40,630 --> 00:21:43,520
22 loại, trong đó ít nhất
khái niệm, nếu chúng ta

488
00:21:43,520 --> 00:21:46,520
việc giữ này được sắp xếp, mà thực sự là
sẽ là một mục tiêu ngay bây giờ,

489
00:21:46,520 --> 00:21:48,690
nên đi ở giữa 17 và 26.

490
00:21:48,690 --> 00:21:50,270
Vì vậy, tôi nhấn Enter.

491
00:21:50,270 --> 00:21:51,380
Thật vậy, mà các công trình.

492
00:21:51,380 --> 00:21:54,950
Và vì vậy bây giờ hãy để tôi chèn
cuối cùng, mỗi hình ảnh, 34.

493
00:21:54,950 --> 00:21:55,450
>> Tất cả các quyền.

494
00:21:55,450 --> 00:21:58,980
Vì vậy, bây giờ hãy để tôi quy định rằng
Xóa và Traverse và tìm kiếm làm,

495
00:21:58,980 --> 00:21:59,760
trên thực tế, làm việc.

496
00:21:59,760 --> 00:22:04,180
Trong thực tế, nếu tôi chạy tìm kiếm, chúng ta hãy
tìm kiếm số 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Kết quả cho thấy 22.

498
00:22:05,010 --> 00:22:07,580
Vì vậy, đó là những gì này
Danh sách chương trình Zero, không.

499
00:22:07,580 --> 00:22:10,230
>> Nhưng những gì đang thực sự xảy ra
trên mà thực hiện điều này?

500
00:22:10,230 --> 00:22:14,530
Vâng, đầu tiên tôi có thể có, và thực sự
Tôi có một tập tin gọi là list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Và ở đâu đó trong có này
dòng, typedef, cấu trúc nút,

503
00:22:20,690 --> 00:22:24,850
Sau đó tôi có dấu ngoặc nhọn của tôi, int n, và
sau đó struct-- là những gì định nghĩa?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Nút cấu trúc tiếp theo.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Vì vậy, chúng ta cần ngôi sao.

508
00:22:31,045 --> 00:22:33,420
Bây giờ về mặt kỹ thuật, chúng tôi nhận được vào
thói quen vẽ nó ở đây.

509
00:22:33,420 --> 00:22:35,670
Bạn có thể thấy sách giáo khoa và
tài liệu tham khảo trực tuyến làm nó ở đó.

510
00:22:35,670 --> 00:22:36,660
Đó là chức năng tương đương.

511
00:22:36,660 --> 00:22:37,980
Trong thực tế, đây là điển hình hơn một chút.

512
00:22:37,980 --> 00:22:40,563
Nhưng tôi sẽ phù hợp với những gì
chúng tôi đã làm thời gian qua và làm được điều này.

513
00:22:40,563 --> 00:22:42,350
Và rồi cuối cùng, tôi sẽ làm điều này.

514
00:22:42,350 --> 00:22:45,550
>> Vì vậy, trong một tập tin tiêu đề
ở đâu đó, trong list0.h

515
00:22:45,550 --> 00:22:49,200
hôm nay là định nghĩa cấu trúc này,
và có thể một số nội dung khác.

516
00:22:49,200 --> 00:22:52,580
Trong khi đó tại list0c có
sẽ có một vài điều.

517
00:22:52,580 --> 00:22:54,740
Nhưng chúng ta sẽ chỉ
bắt đầu và không kết thúc này.

518
00:22:54,740 --> 00:22:59,690
List0.h là một tập tin tôi muốn
bao gồm trong tập tin C của tôi.

519
00:22:59,690 --> 00:23:03,910
Và sau đó tại một số điểm tôi
sẽ có int, chính, làm mất hiệu lực.

520
00:23:03,910 --> 00:23:06,530
Và sau đó tôi sẽ
có một số việc phải làm ở đây.

521
00:23:06,530 --> 00:23:10,620
Tôi cũng sẽ có một
nguyên mẫu, như bãi bỏ, tìm kiếm, int,

522
00:23:10,620 --> 00:23:13,610
n, có mục đích trong cuộc sống là
để tìm kiếm một phần tử.

523
00:23:13,610 --> 00:23:18,310
Và sau đó xuống đây tôi yêu cầu bồi thường trong
Mã ngày nay, bãi bỏ, tìm kiếm, int, n,

524
00:23:18,310 --> 00:23:21,020
không có dấu chấm phẩy nhưng dấu ngoặc nhọn mở.

525
00:23:21,020 --> 00:23:25,049
Và bây giờ tôi muốn bằng cách nào đó tìm kiếm
cho một phần tử trong danh sách này.

526
00:23:25,049 --> 00:23:27,340
Nhưng chúng ta không có đủ
thông tin trên màn hình được nêu ra.

527
00:23:27,340 --> 00:23:29,800
Tôi đã không thực sự
đại diện trong danh sách riêng của mình.

528
00:23:29,800 --> 00:23:33,070
Vì vậy, một trong những cách chúng ta có thể thực hiện
một danh sách liên kết trong một chương trình

529
00:23:33,070 --> 00:23:37,520
là tôi loại muốn làm điều gì đó
như tuyên bố danh sách liên kết ở đây.

530
00:23:37,520 --> 00:23:40,520
Để đơn giản, tôi sẽ làm cho
toàn cầu này, mặc dù trong chúng ta nói chung

531
00:23:40,520 --> 00:23:41,645
không nên làm điều này quá nhiều.

532
00:23:41,645 --> 00:23:43,260
Nhưng nó sẽ đơn giản hóa ví dụ này.

533
00:23:43,260 --> 00:23:45,890
Vì vậy, tôi muốn khai báo
một danh sách liên kết ở đây.

534
00:23:45,890 --> 00:23:47,010
Bây giờ, làm thế nào tôi có thể làm điều đó?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Dưới đây là hình ảnh của một danh sách liên kết.

537
00:23:50,750 --> 00:23:53,030
Và tôi không thực sự
biết tại thời điểm này như thế nào

538
00:23:53,030 --> 00:23:56,710
Tôi sẽ đi về đại diện
quá nhiều thứ chỉ với một

539
00:23:56,710 --> 00:23:58,040
biến trong bộ nhớ.

540
00:23:58,040 --> 00:23:59,160
Nhưng nghĩ lại một chút.

541
00:23:59,160 --> 00:24:00,830
Tất cả thời gian này, chúng tôi đã có
chuỗi, mà chúng tôi sau đó

542
00:24:00,830 --> 00:24:02,913
tiết lộ là mảng
nhân vật, mà chúng tôi sau đó

543
00:24:02,913 --> 00:24:05,740
tiết lộ chỉ là một con trỏ
để ký tự đầu tiên

544
00:24:05,740 --> 00:24:08,890
trong một loạt các ký tự
đó là null chấm dứt.

545
00:24:08,890 --> 00:24:13,530
Vì vậy, theo logic, và với điều này
hình ảnh loại hạt giống suy nghĩ của bạn,

546
00:24:13,530 --> 00:24:17,964
những gì chúng tôi thực sự cần viết của chúng tôi
mã để đại diện cho một danh sách liên kết?

547
00:24:17,964 --> 00:24:21,130
Làm thế nào nhiều thông tin này chúng ta cần
để nắm bắt trong mã C, bạn sẽ nói gì?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Vâng?

550
00:24:23,154 --> 00:24:24,738
>> TƯỢNG: Chúng tôi cần một con trỏ đến một nút.

551
00:24:24,738 --> 00:24:26,237
DAVID J. Malan: Một con trỏ tới một nút.

552
00:24:26,237 --> 00:24:29,320
Đặc biệt, trong đó nút sẽ của bạn
bản năng là giữ một con trỏ đến?

553
00:24:29,320 --> 00:24:30,026
>> TƯỢNG: Nút đầu tiên.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. Malan: Yeah,
có lẽ chỉ là người đầu tiên.

555
00:24:31,942 --> 00:24:34,030
Và hãy chú ý, lần đầu tiên
nút là một hình dạng khác nhau.

556
00:24:34,030 --> 00:24:37,690
Đó chỉ là một nửa kích thước của cấu trúc,
bởi vì nó thực sự chỉ là một con trỏ.

557
00:24:37,690 --> 00:24:44,650
Vì vậy, những gì bạn thực sự có thể làm là khai báo
một danh sách liên kết là các loại nút *.

558
00:24:44,650 --> 00:24:47,780
Và chúng ta hãy gọi nó là đầu tiên
và khởi tạo nó thành vô giá trị.

559
00:24:47,780 --> 00:24:49,910
Vì vậy, vô giá trị, một lần nữa, là tới
vào hình ảnh ở đây.

560
00:24:49,910 --> 00:24:53,620
Không chỉ được sử dụng như rỗng như một đặc biệt
giá trị trả về cho những thứ như getString

561
00:24:53,620 --> 00:24:57,770
và malloc, null cũng là số không
con trỏ, thiếu một con trỏ,

562
00:24:57,770 --> 00:24:58,430
nếu bạn sẽ.

563
00:24:58,430 --> 00:25:00,309
Nó chỉ có nghĩa là không có gì là có ở đây.

564
00:25:00,309 --> 00:25:02,100
Bây giờ đầu tiên, tôi có thể đã
gọi là bất cứ điều gì này.

565
00:25:02,100 --> 00:25:04,200
Tôi có thể gọi đó là "danh sách"
hoặc bất kỳ số lượng những thứ khác.

566
00:25:04,200 --> 00:25:06,960
Nhưng tôi gọi đó là "đầu tiên" để
nó lên đường với hình ảnh này.

567
00:25:06,960 --> 00:25:10,280
Vì vậy, giống như một chuỗi có thể được biểu
với địa chỉ của byte đầu tiên của nó,

568
00:25:10,280 --> 00:25:11,280
vì vậy có thể một danh sách liên kết.

569
00:25:11,280 --> 00:25:13,480
Và chúng ta sẽ thấy các dữ liệu khác
cấu trúc được đại diện

570
00:25:13,480 --> 00:25:16,700
chỉ với một con trỏ,
một mũi tên 32-bit, chỉ

571
00:25:16,700 --> 00:25:18,740
tại nút đầu tiên trong cấu trúc.

572
00:25:18,740 --> 00:25:20,340
>> Nhưng bây giờ chúng ta hãy dự đoán một vấn đề.

573
00:25:20,340 --> 00:25:23,230
Nếu tôi chỉ nhớ
trong chương trình của tôi địa chỉ

574
00:25:23,230 --> 00:25:27,220
của nút đầu tiên, là người đầu tiên
hình chữ nhật trong cấu trúc dữ liệu này,

575
00:25:27,220 --> 00:25:31,760
những gì đã tốt hơn là trường hợp về
thực hiện phần còn lại của danh sách của tôi?

576
00:25:31,760 --> 00:25:35,820
Một chi tiết quan trọng đó là sẽ là những gì
để đảm bảo điều này thực sự hoạt động?

577
00:25:35,820 --> 00:25:39,250
Và bởi "thực sự hoạt động" Tôi
có nghĩa là, giống như một chuỗi,

578
00:25:39,250 --> 00:25:42,180
cho phép chúng tôi đi từ ký tự đầu tiên
tên Davin để lần thứ hai,

579
00:25:42,180 --> 00:25:44,755
đến thứ ba, cho
thứ tư, cho đến cuối cùng,

580
00:25:44,755 --> 00:25:47,880
làm thế nào để chúng ta biết khi nào chúng tôi ở cuối
của một danh sách liên kết trông như thế này?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Khi đó là null.

583
00:25:50,660 --> 00:25:53,640
Và tôi đã đại diện cho loại này là
như một kỹ sư điện mạnh,

584
00:25:53,640 --> 00:25:56,420
với nền tảng ít
biểu tượng, các loại.

585
00:25:56,420 --> 00:25:58,246
Nhưng điều đó chỉ có nghĩa là vô giá trị trong trường hợp này.

586
00:25:58,246 --> 00:26:00,370
Bạn có thể vẽ nó bất kỳ số
cách khác nhau, nhưng tác giả này

587
00:26:00,370 --> 00:26:02,800
đã xảy ra để sử dụng biểu tượng này ở đây.

588
00:26:02,800 --> 00:26:06,260
>> Vì vậy, miễn là chúng ta đang xâu chuỗi
tất cả các nút với nhau,

589
00:26:06,260 --> 00:26:08,600
chỉ nhớ nơi
đầu tiên là, miễn

590
00:26:08,600 --> 00:26:11,760
khi chúng ta đặt một biểu tượng đặc biệt tại
nút cuối cùng trong danh sách,

591
00:26:11,760 --> 00:26:15,130
và chúng tôi sẽ sử dụng vô giá trị, bởi vì đó là
những gì chúng tôi có sẵn cho chúng tôi,

592
00:26:15,130 --> 00:26:16,480
danh sách này hoàn tất.

593
00:26:16,480 --> 00:26:20,190
Và ngay cả khi tôi chỉ cung cấp cho bạn một con trỏ đến
các yếu tố đầu tiên, bạn, các lập trình viên,

594
00:26:20,190 --> 00:26:22,486
chắc chắn có thể truy cập vào phần còn lại của nó.

595
00:26:22,486 --> 00:26:24,360
Nhưng chúng ta hãy để cho tâm trí của bạn
đi lang thang một chút,

596
00:26:24,360 --> 00:26:26,140
nếu họ không đã
khá wandered-- gì

597
00:26:26,140 --> 00:26:28,723
sẽ là thời gian chạy của
tìm kiếm bất cứ điều gì trong danh sách này?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Chết tiệt, đó là O lớn của n,
đó không phải là xấu, công bằng.

600
00:26:33,470 --> 00:26:34,800
Nhưng nó là tuyến tính.

601
00:26:34,800 --> 00:26:37,980
Chúng tôi đã từ bỏ những gì tính năng
các mảng bằng cách di chuyển hơn

602
00:26:37,980 --> 00:26:43,130
đối với hình ảnh của động
đan xen với nhau hoặc liên kết các nút?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Chúng tôi đã từ bỏ truy cập ngẫu nhiên.

605
00:26:46,687 --> 00:26:48,770
Một mảng là tốt đẹp vì
toán học tất cả mọi thứ

606
00:26:48,770 --> 00:26:50,340
là trở lại trở lại để trở lại trở lại.

607
00:26:50,340 --> 00:26:52,370
Mặc dù hình ảnh này
vẻ đẹp, và thậm chí

608
00:26:52,370 --> 00:26:55,830
mặc dù nó trông giống như các nút
độc đáo được cách nhau, trong thực tế

609
00:26:55,830 --> 00:26:56,830
họ có thể là bất cứ nơi nào.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, các
các nút có thể là bất cứ nơi nào.

611
00:27:01,590 --> 00:27:05,960
Bởi vì malloc không cấp phát bộ nhớ
từ đống, nhưng bất cứ nơi nào trong đống.

612
00:27:05,960 --> 00:27:09,080
Bạn không nhất thiết phải biết rằng nó
sẽ trở lại trở lại trở lại.

613
00:27:09,080 --> 00:27:12,460
Và như vậy hình này trong thực tế của
không có được khá xinh đẹp này.

614
00:27:12,460 --> 00:27:16,140
>> Vì vậy, nó sẽ mất một chút
làm việc để thực hiện chức năng này.

615
00:27:16,140 --> 00:27:17,880
Vì vậy, hãy thực hiện tìm kiếm ngay bây giờ.

616
00:27:17,880 --> 00:27:20,250
Và chúng ta sẽ thấy loại một
cách thông minh để làm điều này.

617
00:27:20,250 --> 00:27:24,660
Vì vậy, nếu tôi là một chức năng tìm kiếm và
Tôi cho một biến, số nguyên n

618
00:27:24,660 --> 00:27:28,490
tìm kiếm, tôi cần phải biết
cú pháp mới để tìm kiếm bên trong

619
00:27:28,490 --> 00:27:32,400
của một cấu trúc đó là
chỉ ra, để tìm n.

620
00:27:32,400 --> 00:27:33,210
Vì vậy, hãy làm điều này.

621
00:27:33,210 --> 00:27:36,030
>> Vì vậy, đầu tiên tôi sẽ đi
trước và tuyên bố một nút *.

622
00:27:36,030 --> 00:27:39,400
Và tôi sẽ gọi nó
con trỏ, chỉ cần theo quy ước.

623
00:27:39,400 --> 00:27:41,710
Và tôi sẽ khởi tạo nó đầu tiên.

624
00:27:41,710 --> 00:27:43,770
Và bây giờ tôi có thể làm điều này
trong một số cách.

625
00:27:43,770 --> 00:27:45,436
Nhưng tôi sẽ có cách tiếp cận phổ biến.

626
00:27:45,436 --> 00:27:50,180
Trong khi con trỏ không bằng
null, và đó là cú pháp hợp lệ.

627
00:27:50,180 --> 00:27:54,550
Và nó chỉ có nghĩa là làm như sau, vì vậy
miễn là bạn không chỉ ở không có gì.

628
00:27:54,550 --> 00:27:55,800
Tôi muốn làm gì?

629
00:27:55,800 --> 00:28:01,939
>> Nếu con trỏ điểm n, hãy để tôi trở lại
đó, equals-- bằng gì?

630
00:28:01,939 --> 00:28:03,105
Giá trị những gì tôi đang tìm kiếm?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
N thực tế đã được thông qua.

633
00:28:06,590 --> 00:28:09,020
Vì vậy, đây là tính năng khác
C và nhiều ngôn ngữ.

634
00:28:09,020 --> 00:28:13,705
Mặc dù cấu trúc gọi là nút
có n giá trị, hoàn toàn hợp pháp

635
00:28:13,705 --> 00:28:17,530
cũng có một tham số địa phương
hoặc biến được gọi là n.

636
00:28:17,530 --> 00:28:20,085
Bởi vì ngay cả chúng tôi, với
đôi mắt của con người, có thể phân biệt

637
00:28:20,085 --> 00:28:22,087
rằng n này có lẽ là
khác nhau từ n này.

638
00:28:22,087 --> 00:28:23,420
Bởi vì cú pháp là khác nhau.

639
00:28:23,420 --> 00:28:26,211
Bạn đã có một dấu chấm và một con trỏ,
trong khi một này không có điều như vậy.

640
00:28:26,211 --> 00:28:27,290
Vì vậy, đây là OK.

641
00:28:27,290 --> 00:28:29,120
Đó là OK để gọi họ là những điều tương tự.

642
00:28:29,120 --> 00:28:32,380
>> Nếu tôi để bạn tìm thấy điều này, tôi
sẽ muốn làm điều gì đó

643
00:28:32,380 --> 00:28:35,000
như thông báo rằng chúng tôi thấy n.

644
00:28:35,000 --> 00:28:37,930
Và chúng tôi sẽ rời khỏi đó như là một
bình luận hoặc mã giả.

645
00:28:37,930 --> 00:28:40,190
Khác, và đây là
Phần thú vị, những gì

646
00:28:40,190 --> 00:28:47,320
Tôi muốn làm gì nếu nút hiện tại
không chứa n mà tôi quan tâm?

647
00:28:47,320 --> 00:28:50,700
Làm thế nào để đạt được những điều sau đây?

648
00:28:50,700 --> 00:28:53,710
Nếu ngón tay của tôi tại
thời điểm là PTR, và nó

649
00:28:53,710 --> 00:28:55,920
chỉ tay vào bất cứ điều gì
đầu tiên là chỉ vào,

650
00:28:55,920 --> 00:28:59,290
làm thế nào để di chuyển ngón tay của tôi
đến nút tiếp theo trong mã?

651
00:28:59,290 --> 00:29:01,915
Vâng, mẩu bánh mì chúng tôi là những gì
đi theo trong trường hợp này?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
TƯỢNG: [không nghe được].

654
00:29:04,380 --> 00:29:05,630
DAVID J. Malan: Vâng, vì vậy tiếp theo.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Vì vậy, nếu tôi quay trở lại của tôi
mã ở đây, thực sự, tôi

657
00:29:09,824 --> 00:29:12,990
sẽ đi trước và nói con trỏ, mà
chỉ là một variable-- tạm thời nó

658
00:29:12,990 --> 00:29:15,320
một tên lạ, ptr, nhưng
nó chỉ giống như temp--

659
00:29:15,320 --> 00:29:19,234
Tôi sẽ đặt con trỏ
bằng bất cứ con trỏ is--

660
00:29:19,234 --> 00:29:22,150
và một lần nữa, điều này là có được một
lỗi nhỏ cho một dấu chấm moment-- tiếp theo.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Nói cách khác, tôi sẽ lấy của tôi
ngón tay trỏ vào nút này

663
00:29:26,550 --> 00:29:31,247
ở đây và tôi sẽ nói, bạn biết
những gì, hãy nhìn vào lĩnh vực tiếp theo

664
00:29:31,247 --> 00:29:33,330
và di chuyển ngón tay của bạn để
bất cứ điều gì nó chỉ tay vào.

665
00:29:33,330 --> 00:29:35,163
Và điều này sẽ
lặp lại, lặp lại, lặp lại.

666
00:29:35,163 --> 00:29:37,630
Nhưng khi nào ngón tay của tôi
ngừng làm bất cứ điều gì ở tất cả?

667
00:29:37,630 --> 00:29:40,095
Ngay sau khi những dòng mã trong đá?

668
00:29:40,095 --> 00:29:40,970
TƯỢNG: [không nghe được]

669
00:29:40,970 --> 00:29:43,060
DAVID J. Malan: Nếu điểm trong khi
con trỏ không bằng null.

670
00:29:43,060 --> 00:29:44,900
Tại một số điểm ngón tay của tôi
sẽ được chỉ vào vô

671
00:29:44,900 --> 00:29:47,070
và tôi sẽ thực hiện
đó là kết thúc của danh sách này.

672
00:29:47,070 --> 00:29:48,910
Bây giờ, đây là một chút
lời nói dối trắng cho đơn giản.

673
00:29:48,910 --> 00:29:51,580
Nó chỉ ra rằng mặc dù chúng ta
chỉ biết ký hiệu dấu chấm này

674
00:29:51,580 --> 00:29:55,220
cho các cấu trúc, con trỏ không phải là một cấu trúc.

675
00:29:55,220 --> 00:29:56,580
ptr là gì?

676
00:29:56,580 --> 00:29:58,350
Chỉ cần được nitpicky hơn.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Đó là một con trỏ đến một nút.

679
00:30:01,360 --> 00:30:03,120
Nó không phải là một nút riêng của mình.

680
00:30:03,120 --> 00:30:06,650
Nếu tôi không có ngôi sao ở đây, con trỏ
absolutely-- đó là một nút.

681
00:30:06,650 --> 00:30:08,650
Điều này giống như một tuần
khai báo của một biến,

682
00:30:08,650 --> 00:30:10,120
mặc dù từ "nút" là mới.

683
00:30:10,120 --> 00:30:13,860
>> Nhưng ngay khi chúng tôi giới thiệu một
sao, bây giờ là một con trỏ đến một nút.

684
00:30:13,860 --> 00:30:17,960
Và thật không may, bạn không thể sử dụng
các ký hiệu dấu chấm cho một con trỏ.

685
00:30:17,960 --> 00:30:21,070
Bạn phải sử dụng mũi tên
ký hiệu, trong đó, nổi bật,

686
00:30:21,070 --> 00:30:23,470
là lần đầu tiên bất cứ mảnh
cú pháp trông trực quan.

687
00:30:23,470 --> 00:30:25,245
Điều này nghĩa đen trông giống như một mũi tên.

688
00:30:25,245 --> 00:30:26,370
Và đó là một điều tốt.

689
00:30:26,370 --> 00:30:28,995
Và ở đây theo nghĩa đen
trông giống như một mũi tên.

690
00:30:28,995 --> 00:30:31,870
Vì vậy, tôi nghĩ rằng đó là la-- tôi không
nghĩ rằng tôi quá phạm here-- tôi

691
00:30:31,870 --> 00:30:34,120
nghĩ đó là tác phẩm mới nhất
cú pháp của chúng ta sẽ nhìn thấy.

692
00:30:34,120 --> 00:30:36,500
Và may mắn thay, nó thực sự
nhiều hơn một chút trực quan.

693
00:30:36,500 --> 00:30:40,090
>> Bây giờ, đối với những người bạn của những người
có thể thích theo cách cũ,

694
00:30:40,090 --> 00:30:42,550
bạn vẫn có thể sử dụng các ký hiệu dấu chấm.

695
00:30:42,550 --> 00:30:45,380
Tuy nhiên, theo thứ hai của
cuộc trò chuyện, chúng tôi đầu tiên

696
00:30:45,380 --> 00:30:50,530
cần phải đến đó, đi đến đó
giải quyết, và sau đó truy cập vào lĩnh vực này.

697
00:30:50,530 --> 00:30:51,897
Vì vậy, đây cũng là chính xác.

698
00:30:51,897 --> 00:30:53,730
Và thẳng thắn mà nói, đây là một
ít mô phạm hơn.

699
00:30:53,730 --> 00:30:56,530
Bạn đang nói theo nghĩa đen, tới đích
con trỏ và đi đến đó.

700
00:30:56,530 --> 00:30:59,320
Sau đó lấy .n, lĩnh vực được gọi là n.

701
00:30:59,320 --> 00:31:01,370
Nhưng thẳng thắn mà nói, không ai muốn
gõ hoặc đọc này.

702
00:31:01,370 --> 00:31:03,620
Và như vậy trên thế giới phát minh ra
các ký hiệu mũi tên, mà

703
00:31:03,620 --> 00:31:06,980
là tương đương, giống hệt nhau,
nó chỉ là cú pháp đường.

704
00:31:06,980 --> 00:31:10,570
Vì vậy, một cách nói này
có vẻ tốt hơn, hoặc trông đơn giản hơn.

705
00:31:10,570 --> 00:31:12,296
>> Vì vậy, bây giờ tôi sẽ làm một việc khác.

706
00:31:12,296 --> 00:31:15,420
Tôi sẽ nói "phá vỡ" một khi tôi đã
tìm thấy nó vì vậy tôi không tiếp tục tìm kiếm cho nó.

707
00:31:15,420 --> 00:31:17,620
Nhưng đây là ý chính
các chức năng tìm kiếm.

708
00:31:17,620 --> 00:31:21,710
Nhưng nó dễ dàng hơn rất nhiều, trong
kết thúc, không đi qua các mã.

709
00:31:21,710 --> 00:31:25,570
Điều này thực sự là việc thực hiện chính thức
tìm trong mã phân phối hiện nay.

710
00:31:25,570 --> 00:31:30,530
Tôi dám nói chèn đó không phải là
đặc biệt thú vị để đi bộ qua

711
00:31:30,530 --> 00:31:33,180
trực quan, cũng không phải là xóa, thậm chí
mặc dù vào cuối ngày

712
00:31:33,180 --> 00:31:35,460
họ đun sôi xuống khá
chẩn đoán đơn giản.

713
00:31:35,460 --> 00:31:36,330
>> Vì vậy, hãy làm điều này.

714
00:31:36,330 --> 00:31:39,250
Nếu bạn sẽ hài hước tôi ở đây, tôi đã làm
mang lại một loạt các quả bóng căng thẳng.

715
00:31:39,250 --> 00:31:40,620
Tôi mang một loạt các con số.

716
00:31:40,620 --> 00:31:46,562
Và chúng tôi có thể nhận được chỉ là một vài tình nguyện viên
để đại diện cho 9, 17, 20, 22, 29 và 34?

717
00:31:46,562 --> 00:31:48,270
Vì vậy, về cơ bản tất cả mọi người
người ở đây ngày hôm nay.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Đó là một, hai, ba,
bốn, năm, sáu người.

720
00:31:52,760 --> 00:31:55,740
Và tôi đã được yêu cầu go-- thấy, không có
một ở phía sau nâng bàn tay của họ.

721
00:31:55,740 --> 00:32:01,910
OK, một, hai, ba, bốn,
five-- cho tôi tải balance-- sáu.

722
00:32:01,910 --> 00:32:03,051
OK, bạn sáu đến ngày lên.

723
00:32:03,051 --> 00:32:04,050
Chúng ta sẽ cần những người khác.

724
00:32:04,050 --> 00:32:05,460
Chúng tôi đưa quả bóng căng thẳng thêm.

725
00:32:05,460 --> 00:32:08,200
Và nếu bạn có thể,
chỉ là một khoảnh khắc, dòng

726
00:32:08,200 --> 00:32:10,490
hãy tự lập chỉ
như hình ảnh này ở đây.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Tất cả các quyền.

729
00:32:15,959 --> 00:32:17,125
Hãy xem, tên của bạn là gì?

730
00:32:17,125 --> 00:32:17,550
>> TƯỢNG: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. Malan: Andrew,
bạn là số 9.

732
00:32:18,800 --> 00:32:19,540
Rất vui được gặp bạn.

733
00:32:19,540 --> 00:32:20,400
Ở đây bạn đi.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
TƯỢNG: Jen.

736
00:32:22,176 --> 00:32:22,662
DAVID J. Malan: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Số 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Có?

741
00:32:25,450 --> 00:32:26,400
>> TƯỢNG: Tôi là Julia.

742
00:32:26,400 --> 00:32:26,980
>> DAVID J. Malan: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Số 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
TƯỢNG: Kitô giáo.

746
00:32:29,340 --> 00:32:30,715
DAVID J. Malan: Kitô giáo, David.

747
00:32:30,715 --> 00:32:31,541
Số 22.

748
00:32:31,541 --> 00:32:32,040
Và?

749
00:32:32,040 --> 00:32:32,649
>> TƯỢNG: JP.

750
00:32:32,649 --> 00:32:33,440
DAVID J. Malan: JP.

751
00:32:33,440 --> 00:32:34,880
Số 29.

752
00:32:34,880 --> 00:32:37,080
Vì vậy, đi trước và nhận được in-- Uh oh.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uh oh.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Chế độ chờ.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Có ai có một dấu hiệu?

760
00:32:43,682 --> 00:32:44,890
TƯỢNG: Tôi đã có một Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. Malan: Bạn có một Sharpie?

762
00:32:45,660 --> 00:32:46,159
OK.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Và không ai có một mảnh giấy?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Lưu bài giảng.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Thôi nào.

769
00:32:55,362 --> 00:32:56,320
TƯỢNG: Chúng tôi đã có nó.

770
00:32:56,320 --> 00:32:57,600
DAVID J. Malan: Chúng tôi đã nhận nó?

771
00:32:57,600 --> 00:32:58,577
Được rồi, cảm ơn bạn.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Ở đây chúng ta đi.

774
00:33:02,520 --> 00:33:03,582
Được điều này từ bạn?

775
00:33:03,582 --> 00:33:04,540
Bạn chỉ cần lưu lại trong ngày.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Vì vậy, 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Tất cả các quyền.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Tôi sai chính tả 29, nhưng OK.

782
00:33:14,890 --> 00:33:15,720
Về phía trước.

783
00:33:15,720 --> 00:33:18,114
Được rồi, tôi sẽ cung cấp cho bạn
bút của bạn trở lại trong giây lát.

784
00:33:18,114 --> 00:33:19,280
Vì vậy, chúng tôi có những người ở đây.

785
00:33:19,280 --> 00:33:20,330
Hãy có một khác.

786
00:33:20,330 --> 00:33:23,750
Gabe, bạn muốn chơi
các yếu tố đầu tiên ở đây?

787
00:33:23,750 --> 00:33:25,705
Chúng tôi cần bạn chỉ
ở những người này tốt.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Vì vậy, 9, 17, 20, 22, sắp xếp
29, 34 và sau đó.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Chúng ta đã mất đi một người nào đó?

792
00:33:33,325 --> 00:33:33,950
Tôi có một 34.

793
00:33:33,950 --> 00:33:36,730
Trường hợp did-- OK, ai muốn trở thành 34?

794
00:33:36,730 --> 00:33:37,605
OK, đến ngày lên, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Được rồi, đây sẽ là
cũng có giá trị cao trào.

797
00:33:41,220 --> 00:33:41,550
Tên của bạn là gì?

798
00:33:41,550 --> 00:33:42,040
>> TƯỢNG: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. Malan: Peter, đi lên trên.

800
00:33:43,456 --> 00:33:46,810
Được rồi, vì vậy đây là một
bó toàn bộ các nút.

801
00:33:46,810 --> 00:33:49,060
Mỗi của các bạn đại diện cho
một trong những hình chữ nhật.

802
00:33:49,060 --> 00:33:51,930
Và Gabe, hơi kỳ quặc
con người ra, đại diện đầu tiên.

803
00:33:51,930 --> 00:33:54,850
Vì vậy, con trỏ của mình là nhỏ hơn một chút
trên màn hình hơn so với những người khác.

804
00:33:54,850 --> 00:33:58,120
Và trong trường hợp này, mỗi bên trái của bạn
tay sẽ hoặc chỉ xuống,

805
00:33:58,120 --> 00:34:01,085
do đó đại diện cho null, vì vậy
chỉ sự vắng mặt của một con trỏ,

806
00:34:01,085 --> 00:34:03,210
hoặc nó sẽ được trỏ
tại một nút bên cạnh bạn.

807
00:34:03,210 --> 00:34:05,440
>> Vì vậy, ngay bây giờ nếu bạn tô điểm
mình giống như hình ảnh

808
00:34:05,440 --> 00:34:07,585
ở đây, đi trước và điểm
nhau, với Gabe

809
00:34:07,585 --> 00:34:11,030
trong trỏ đặc biệt là ở
số 9 đại diện trong danh sách.

810
00:34:11,030 --> 00:34:14,050
OK, và số 34, tay trái của bạn
chỉ nên được trỏ xuống sàn nhà.

811
00:34:14,050 --> 00:34:15,750
>> OK, vì vậy đây là danh sách liên kết.

812
00:34:15,750 --> 00:34:17,580
Vì vậy, đây là kịch bản trong câu hỏi.

813
00:34:17,580 --> 00:34:20,210
Và quả thực, đây là đại diện
của một lớp học của các vấn đề

814
00:34:20,210 --> 00:34:21,929
mà bạn có thể cố gắng giải quyết với mã.

815
00:34:21,929 --> 00:34:25,020
Bạn muốn cuối cùng chèn
một nguyên tố mới vào danh sách.

816
00:34:25,020 --> 00:34:27,494
Trong trường hợp này, chúng ta sẽ
thử chèn số 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Tuy nhiên, sẽ là
trường hợp khác nhau để xem xét.

819
00:34:30,860 --> 00:34:34,409
Và quả thực, điều này là có được một
của hình ảnh lớn takeaways ở đây, là,

820
00:34:34,409 --> 00:34:35,659
các trường hợp khác nhau là gì.

821
00:34:35,659 --> 00:34:39,120
Điều gì là khác nhau nếu có điều kiện hoặc
chi nhánh rằng chương trình của bạn có thể có?

822
00:34:39,120 --> 00:34:42,024
>> Vâng, số lượng bạn đang cố gắng để
chèn, mà chúng ta biết bây giờ là 55,

823
00:34:42,024 --> 00:34:44,650
nhưng nếu bạn không biết
trước, tôi dám chắc

824
00:34:44,650 --> 00:34:47,840
rơi vào ít nhất ba
tình huống có thể.

825
00:34:47,840 --> 00:34:49,717
Trường hợp có một nguyên tố mới được?

826
00:34:49,717 --> 00:34:51,050
TƯỢNG: Và cuối hoặc trung bình.

827
00:34:51,050 --> 00:34:54,150
DAVID J. Malan: Cuối cùng, trong
giữa, hoặc ngay từ đầu.

828
00:34:54,150 --> 00:34:56,650
Vì vậy, tôi khẳng định có ít nhất
ba vấn đề chúng ta cần phải giải quyết.

829
00:34:56,650 --> 00:34:58,691
Hãy chọn những gì có thể
cho là đơn giản nhất

830
00:34:58,691 --> 00:35:01,090
một, nơi mà các nguyên tố mới
thuộc ngay từ đầu.

831
00:35:01,090 --> 00:35:04,040
Vì vậy, tôi sẽ có mã khá
như tìm kiếm, mà tôi chỉ viết.

832
00:35:04,040 --> 00:35:07,670
Và tôi sẽ phải ptr, mà
Tôi sẽ đại diện ở đây với ngón tay của tôi,

833
00:35:07,670 --> 00:35:08,370
như thường lệ.

834
00:35:08,370 --> 00:35:12,430
>> Và hãy nhớ, những gì giá trị
chúng tôi đã khởi tạo ptr?

835
00:35:12,430 --> 00:35:15,300
Vì vậy, chúng tôi khởi tạo nó thành vô giá trị ban đầu.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Nhưng sau đó, những gì chúng ta đã làm một lần chúng tôi
ở bên trong chức năng tìm kiếm của chúng tôi?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Chúng tôi thiết lập nó bằng đầu tiên,
đó không có nghĩa là làm điều này.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Nếu tôi đặt ptr bằng đầu tiên, những gì
nên bàn tay của tôi thực sự là chỉ tay vào?

842
00:35:30,570 --> 00:35:31,070
Đúng.

843
00:35:31,070 --> 00:35:33,290
Vì vậy, nếu Gabe và tôi sẽ
có giá trị tương đương ở đây,

844
00:35:33,290 --> 00:35:34,760
chúng ta cần cả hai điểm ở vị trí thứ 9.

845
00:35:34,760 --> 00:35:36,420
>> Vì vậy, đây là sự khởi đầu của câu chuyện của chúng tôi.

846
00:35:36,420 --> 00:35:38,700
Và bây giờ điều này chỉ đơn giản,
mặc dù cú pháp là mới.

847
00:35:38,700 --> 00:35:40,580
Khái niệm này chỉ là tìm kiếm tuyến tính.

848
00:35:40,580 --> 00:35:42,750
55 bằng 9?

849
00:35:42,750 --> 00:35:45,559
Hay đúng hơn, chúng ta hãy nói ít hơn 9.

850
00:35:45,559 --> 00:35:47,600
Bởi vì tôi đang cố gắng để
tìm ra nơi để đặt 55.

851
00:35:47,600 --> 00:35:51,270
Chưa đầy 9, ít hơn 17 ít hơn,
hơn 20, ít hơn 22, ít hơn 29,

852
00:35:51,270 --> 00:35:52,510
ít hơn 34, không có.

853
00:35:52,510 --> 00:35:55,080
Vì vậy, bây giờ chúng tôi đang ở trong trường hợp
một trong ít nhất ba.

854
00:35:55,080 --> 00:35:59,910
>> Nếu tôi muốn chèn 55 ​​trên đây, những gì
dòng mã cần phải được thực thi?

855
00:35:59,910 --> 00:36:01,890
Làm thế nào để hình ảnh này
con người cần phải thay đổi?

856
00:36:01,890 --> 00:36:03,181
Tôi phải làm gì với bàn tay trái của tôi không?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Điều này sẽ không có giá trị ban đầu,
bởi vì tôi đang ở cuối danh sách.

859
00:36:07,360 --> 00:36:09,318
Và những gì sẽ xảy ra
ở đây với Peter, đúng không?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Anh ấy rõ ràng là sẽ chỉ cho tôi.

862
00:36:12,430 --> 00:36:15,580
Vì vậy, tôi khẳng định có ít nhất hai dòng
mã trong các mẫu mã từ hôm nay

863
00:36:15,580 --> 00:36:18,570
đó là sẽ thực hiện điều này
kịch bản thêm 55 ở đuôi.

864
00:36:18,570 --> 00:36:20,950
Và tôi có thể có một người nào đó hop
và chỉ đại diện cho 55?

865
00:36:20,950 --> 00:36:22,200
Được rồi, bạn là người mới 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Vì vậy, bây giờ những gì nếu tiếp theo
kịch bản đến cùng,

868
00:36:27,054 --> 00:36:29,720
và chúng tôi muốn chèn vào
bắt đầu hoặc người đứng đầu danh sách này?

869
00:36:29,720 --> 00:36:31,100
Và tên, số 55 là gì?

870
00:36:31,100 --> 00:36:31,420
>> TƯỢNG: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. Malan: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, rất vui được gặp bạn.

873
00:36:33,585 --> 00:36:34,210
Chào mừng bạn.

874
00:36:34,210 --> 00:36:36,640
Vì vậy, bây giờ chúng ta sẽ
chèn, nói rằng, số lượng 5.

875
00:36:36,640 --> 00:36:39,840
Đây là trường hợp thứ hai của
ba chúng tôi đã đưa ra trước đây.

876
00:36:39,840 --> 00:36:43,050
Vì vậy, nếu 5 thuộc ngay từ đầu,
chúng ta hãy xem làm thế nào chúng tôi thấy rằng ra ngoài.

877
00:36:43,050 --> 00:36:46,310
Tôi khởi ptr của tôi
con trỏ đến số 9 một lần nữa.

878
00:36:46,310 --> 00:36:49,140
Và tôi nhận ra, oh, 5 là ít hơn 9.

879
00:36:49,140 --> 00:36:50,880
Vì vậy, sửa chữa hình ảnh này cho chúng tôi.

880
00:36:50,880 --> 00:36:54,820
Có bàn tay, Gabe hay David
or-- tên số 9 của là gì?

881
00:36:54,820 --> 00:36:55,740
>> TƯỢNG: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. Malan: hands-- Jen
mà bàn tay của chúng tôi cần phải thay đổi?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, vì vậy Gabe chỉ vào những gì bây giờ?

885
00:37:00,970 --> 00:37:01,640
Tại tôi.

886
00:37:01,640 --> 00:37:02,750
Tôi là nút mới.

887
00:37:02,750 --> 00:37:04,870
Vì vậy, tôi sẽ chỉ loại di chuyển
vào đây để xem nó trực quan.

888
00:37:04,870 --> 00:37:06,435
Và khi đó tôi chỉ làm những gì mà?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Tuy nhiên, nơi tôi đang chỉ.

891
00:37:09,020 --> 00:37:10,000
Vì vậy, đó là nó.

892
00:37:10,000 --> 00:37:13,717
Vì vậy, chỉ thực sự một dòng mã sửa lỗi
vấn đề này đặc biệt, nó sẽ có vẻ.

893
00:37:13,717 --> 00:37:14,800
Được rồi, vậy thì tốt.

894
00:37:14,800 --> 00:37:17,580
Và một người nào đó có thể là một giữ chỗ cho 5?

895
00:37:17,580 --> 00:37:18,080
Nào lên.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Chúng tôi sẽ giúp bạn có được thời gian tới.

898
00:37:21,320 --> 00:37:24,280
>> Được rồi, vậy now-- và
như một sang một bên, tên

899
00:37:24,280 --> 00:37:28,510
Tôi không làm cho rõ ràng đề cập đến quyền
bây giờ, con trỏ pred, con trỏ trước

900
00:37:28,510 --> 00:37:31,260
và con trỏ mới, đó là
chỉ những cái tên được

901
00:37:31,260 --> 00:37:35,280
trong mẫu mã để các con trỏ hoặc
tay của tôi đó là loại chỉ xung quanh.

902
00:37:35,280 --> 00:37:36,060
Tên của bạn là gì?

903
00:37:36,060 --> 00:37:36,700
>> TƯỢNG: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. Malan: Christine.

905
00:37:37,100 --> 00:37:38,090
Chào mừng bạn.

906
00:37:38,090 --> 00:37:42,180
Được rồi, vậy chúng ta hãy xem xét tại
một kịch bản hơi khó chịu,

907
00:37:42,180 --> 00:37:46,350
nhờ đó mà tôi muốn chèn
cái gì đó như 26 thành này.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Gì?

910
00:37:47,590 --> 00:37:50,510
Những are-- điều tốt chúng tôi có cây bút này.

911
00:37:50,510 --> 00:37:51,955
Được rồi, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Nếu ai đó có thể nhận được một mảnh
giấy đã sẵn sàng, chỉ trong case-- rồi.

914
00:37:57,570 --> 00:37:58,370
Ồ, thú vị.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Vâng đây là một ví dụ
một lỗi bài giảng.

917
00:38:02,390 --> 00:38:03,894
OK vì vậy tên của bạn là gì nữa?

918
00:38:03,894 --> 00:38:04,560
TƯỢNG: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. Malan: Julia, bạn có thể bật
ra và giả vờ như bạn không bao giờ có?

920
00:38:07,559 --> 00:38:09,040
OK, điều này không bao giờ xảy ra.

921
00:38:09,040 --> 00:38:09,680
Cảm ơn bạn.

922
00:38:09,680 --> 00:38:12,180
Vì vậy, giả sử chúng ta muốn chèn
Julia vào danh sách liên kết này.

923
00:38:12,180 --> 00:38:13,780
Cô là số 20.

924
00:38:13,780 --> 00:38:15,530
Và tất nhiên cô ấy
sẽ thuộc về các

925
00:38:15,530 --> 00:38:17,521
begin-- không chỉ vào bất cứ điều gì được nêu ra.

926
00:38:17,521 --> 00:38:20,020
Vì vậy, bàn tay của bạn có thể loại
xuống null hoặc một số giá trị rác.

927
00:38:20,020 --> 00:38:21,210
Hãy kể câu chuyện nhanh chóng.

928
00:38:21,210 --> 00:38:22,980
Tôi chỉ vào số 5 lần này.

929
00:38:22,980 --> 00:38:23,880
Sau đó, tôi kiểm tra 9.

930
00:38:23,880 --> 00:38:25,130
Sau đó, tôi kiểm tra 17.

931
00:38:25,130 --> 00:38:26,247
Sau đó, tôi kiểm tra 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Và tôi nhận ra, ooh, Julia
cần phải đi trước ngày 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Vì vậy, những gì cần phải xảy ra?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Có bàn tay cần phải thay đổi?

938
00:38:36,910 --> 00:38:38,360
Julia, tôi, or--
Tên của bạn là gì nữa?

939
00:38:38,360 --> 00:38:39,230
>> TƯỢNG: Kitô giáo.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. Malan: Kitô giáo hay?

941
00:38:40,060 --> 00:38:40,560
>> TƯỢNG: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. Malan: Andy.

943
00:38:40,905 --> 00:38:41,654
Kitô giáo hay Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy cần để trỏ tại?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
Tất cả các quyền.

949
00:38:47,840 --> 00:38:48,960
Vì vậy, Andy, bạn muốn chỉ ở mức Julia?

950
00:38:48,960 --> 00:38:50,120
Nhưng chờ một phút.

951
00:38:50,120 --> 00:38:53,260
Trong câu chuyện cho đến nay,
Tôi là loại một

952
00:38:53,260 --> 00:38:56,800
phụ trách, theo nghĩa là
con trỏ là điều đó là

953
00:38:56,800 --> 00:38:57,850
di chuyển qua danh sách.

954
00:38:57,850 --> 00:39:00,800
Chúng ta có thể có một tên cho Andy, nhưng
không có biến gọi là Andy.

955
00:39:00,800 --> 00:39:04,320
Các chỉ biến khác mà chúng tôi có là
đầu tiên, người đại diện của Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Vì vậy, đây thực sự là lý do tại sao như vậy,
đến nay chúng tôi đã không cần thiết này.

957
00:39:07,690 --> 00:39:10,846
Nhưng bây giờ trên màn hình có
đề cập đến một lần nữa con trỏ pred.

958
00:39:10,846 --> 00:39:11,970
Vì vậy, hãy để tôi được rõ ràng hơn.

959
00:39:11,970 --> 00:39:14,820
Nếu đây là con trỏ, tôi đã tốt hơn
nhận được nhiều hơn một chút thông minh

960
00:39:14,820 --> 00:39:15,950
về sự lặp lại của tôi.

961
00:39:15,950 --> 00:39:19,580
Nếu bạn không phiền nếu tôi qua đây
một lần nữa, chỉ ở đây, chỉ ở đây.

962
00:39:19,580 --> 00:39:22,500
Nhưng hãy để tôi có một con trỏ pred,
con trỏ người tiền nhiệm, đó là

963
00:39:22,500 --> 00:39:24,740
loại chỉ vào
yếu tố tôi đã chỉ ở.

964
00:39:24,740 --> 00:39:27,330
Vì vậy, khi tôi đi đây, bây giờ
cập nhật tay trái của tôi.

965
00:39:27,330 --> 00:39:29,370
Khi tôi đi đây cập nhật tay trái của tôi.

966
00:39:29,370 --> 00:39:33,090
Và bây giờ tôi không chỉ có một con trỏ đến
các yếu tố mà đi sau khi Julia,

967
00:39:33,090 --> 00:39:36,300
Tôi vẫn còn có một con trỏ đến
Andy, các yếu tố trước đây.

968
00:39:36,300 --> 00:39:39,430
Vì vậy, bạn có thể truy cập, về cơ bản,
vụn bánh mì, nếu bạn muốn,

969
00:39:39,430 --> 00:39:41,500
cho tất cả các con trỏ cần thiết.

970
00:39:41,500 --> 00:39:43,710
>> Vì vậy, nếu tôi chỉ vào
Andy và tôi cũng chỉ

971
00:39:43,710 --> 00:39:47,105
Christian, có bàn tay
bây giờ sẽ được chỉ ở nơi khác?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Vì vậy, Andy bây giờ có thể chỉ vào Julia.

974
00:39:51,960 --> 00:39:54,460
Julia bây giờ có thể chỉ vào Kitô giáo.

975
00:39:54,460 --> 00:39:56,950
Bởi vì cô ấy có thể sao chép của tôi
con trỏ tay phải của.

976
00:39:56,950 --> 00:40:00,044
Và đó là một cách hiệu quả đặt bạn
trở lại vào vị trí này ở đây.

977
00:40:00,044 --> 00:40:02,460
Vì vậy, trong ngắn hạn, mặc dù đây
chúng ta đang loại mãi mãi

978
00:40:02,460 --> 00:40:04,510
để thực sự cập nhật
danh sách liên kết, nhận ra

979
00:40:04,510 --> 00:40:06,580
rằng các hoạt động
là tương đối đơn giản.

980
00:40:06,580 --> 00:40:10,030
Đó là một, hai, ba
dòng mã cuối cùng.

981
00:40:10,030 --> 00:40:12,780
Nhưng quấn quanh những
dòng mã có lẽ

982
00:40:12,780 --> 00:40:16,350
là một chút logic mà hiệu quả
đặt câu hỏi, ở đâu chúng tôi?

983
00:40:16,350 --> 00:40:18,970
Có phải chúng ta ngay từ đầu,
giữa, hoặc cuối cùng?

984
00:40:18,970 --> 00:40:21,890
>> Bây giờ, chắc chắn có một số khác
hoạt động chúng ta có thể thực hiện.

985
00:40:21,890 --> 00:40:24,880
Và những hình ảnh ở đây chỉ mô tả
những gì chúng ta đã làm với con người.

986
00:40:24,880 --> 00:40:26,080
Gì về việc loại bỏ?

987
00:40:26,080 --> 00:40:30,650
Nếu tôi muốn, ví dụ,
loại bỏ các số 34 hoặc 55,

988
00:40:30,650 --> 00:40:34,680
Tôi có thể có cùng một loại mã,
nhưng tôi sẽ cần một hoặc hai bước.

989
00:40:34,680 --> 00:40:36,110
Bởi vì những gì mới?

990
00:40:36,110 --> 00:40:40,460
Nếu tôi loại bỏ một người nào đó ở cuối,
như số 55 và sau đó 34,

991
00:40:40,460 --> 00:40:42,995
cái gì cũng có thay đổi khi tôi làm điều đó?

992
00:40:42,995 --> 00:40:44,870
Tôi có phải không evict--
Tên của bạn là gì nữa?

993
00:40:44,870 --> 00:40:45,380
>> TƯỢNG: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. Malan: Jack.

995
00:40:46,255 --> 00:40:49,770
Tôi có phải không chỉ evict-- Jack miễn phí,
vậy nghĩa là Jack gọi miễn phí, hoặc ít nhất là

996
00:40:49,770 --> 00:40:53,530
con trỏ có quá, nhưng bây giờ
những gì cần phải thay đổi với Peter?

997
00:40:53,530 --> 00:40:55,510
Bàn tay anh nên bắt đầu hướng xuống dưới.

998
00:40:55,510 --> 00:40:59,300
Bởi vì ngay sau khi tôi gọi miễn phí trên
Jack, nếu Peter vẫn chỉ tay vào Jack

999
00:40:59,300 --> 00:41:02,530
và do đó tôi tiếp tục đi qua
danh sách và con trỏ truy cập này,

1000
00:41:02,530 --> 00:41:05,650
đó là khi phân khúc người bạn cũ của chúng tôi
lỗi thực sự có thể tiến hóa.

1001
00:41:05,650 --> 00:41:07,860
Bởi vì chúng tôi đã tạo
bộ nhớ trở lại với Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Bạn có thể ở lại đó
lúng túng trong chỉ là một thời điểm.

1003
00:41:10,760 --> 00:41:13,410
Bởi vì chúng tôi chỉ có một cặp vợ chồng
hoạt động cuối cùng để xem xét.

1004
00:41:13,410 --> 00:41:15,600
Loại bỏ người đứng đầu danh sách,
hoặc beginning-- và một này

1005
00:41:15,600 --> 00:41:16,349
một chút khó chịu.

1006
00:41:16,349 --> 00:41:19,640
Bởi vì chúng ta phải biết rằng Gabe
là loại đặc biệt trong chương trình này.

1007
00:41:19,640 --> 00:41:21,440
Vì quả thực, ông có con trỏ của mình.

1008
00:41:21,440 --> 00:41:24,860
Anh ấy không chỉ bị chỉ,
như là gần như tất cả mọi người khác ở đây.

1009
00:41:24,860 --> 00:41:28,112
>> Vì vậy, khi người đứng đầu danh sách là
loại bỏ, có bàn tay cần phải thay đổi bây giờ?

1010
00:41:28,112 --> 00:41:29,070
Tên của bạn là gì nữa?

1011
00:41:29,070 --> 00:41:29,450
>> TƯỢNG: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. Malan: Tôi là khủng khiếp
vào những cái tên, rõ ràng.

1013
00:41:31,408 --> 00:41:34,011
Vì vậy, Christine và Gabe,
có bàn tay cần phải thay đổi

1014
00:41:34,011 --> 00:41:36,510
khi chúng tôi cố gắng để loại bỏ Christine,
số 5, từ hình ảnh?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, vì vậy chúng ta hãy làm Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe sẽ điểm,
có lẽ, ở vị trí thứ 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Nhưng những gì tiếp theo sẽ xảy ra?

1020
00:41:44,642 --> 00:41:46,600
TƯỢNG: Christine nên
là vô giá trị [không nghe được].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. Malan: OK, chúng ta nên có thể
make-- Tôi nghe nói "vô giá trị" ở đâu đó.

1022
00:41:50,244 --> 00:41:51,410
TƯỢNG: Null và miễn phí của mình.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. Malan: null gì?

1024
00:41:51,855 --> 00:41:53,074
TƯỢNG: Null và miễn phí của mình.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. Malan: Null và miễn phí của mình.

1026
00:41:54,490 --> 00:41:55,422
Vì vậy, đây là rất dễ dàng.

1027
00:41:55,422 --> 00:41:58,380
Và nó hoàn hảo mà bạn bây giờ loại
đứng ở đó, không thuộc.

1028
00:41:58,380 --> 00:42:00,430
Bởi vì bạn đã
tách rời khỏi danh sách.

1029
00:42:00,430 --> 00:42:02,820
Bạn đã có hiệu quả
mồ côi từ danh sách.

1030
00:42:02,820 --> 00:42:07,770
Và vì vậy chúng tôi đã tốt hơn bây giờ gọi miễn phí
Christine để cung cấp cho bộ nhớ trở lại.

1031
00:42:07,770 --> 00:42:10,240
Nếu không mỗi lần chúng tôi
xóa một nút từ danh sách

1032
00:42:10,240 --> 00:42:14,230
chúng ta có thể làm cho danh sách
ngắn hơn, nhưng không thực sự giảm

1033
00:42:14,230 --> 00:42:15,096
kích thước trong bộ nhớ.

1034
00:42:15,096 --> 00:42:17,720
Và như vậy, nếu chúng ta tiếp tục bổ sung và
bổ sung thêm điều vào danh sách,

1035
00:42:17,720 --> 00:42:19,280
máy tính của tôi có thể nhận được chậm hơn
và chậm hơn và chậm hơn,

1036
00:42:19,280 --> 00:42:21,740
bởi vì tôi đang chạy ra khỏi
bộ nhớ, ngay cả khi tôi không thực sự

1037
00:42:21,740 --> 00:42:25,580
Christine sử dụng của byte
bộ nhớ nữa.

1038
00:42:25,580 --> 00:42:28,500
>> Vì vậy, cuối cùng có khác
kịch bản, loại bỏ course--

1039
00:42:28,500 --> 00:42:30,640
ở giữa, loại bỏ
cuối cùng, như chúng ta đã thấy.

1040
00:42:30,640 --> 00:42:32,348
Nhưng thú vị hơn
Thách thức hiện nay là

1041
00:42:32,348 --> 00:42:34,770
sẽ được xem xét một cách chính xác
những gì thời gian chạy là.

1042
00:42:34,770 --> 00:42:36,640
Vì vậy, không chỉ bạn có thể giữ cho bạn
mảnh giấy, nếu, Gabe,

1043
00:42:36,640 --> 00:42:38,640
bạn sẽ không nhớ cho
tất cả mọi người một quả bóng căng thẳng.

1044
00:42:38,640 --> 00:42:42,100
Cảm ơn bạn rất nhiều danh sách liên kết của chúng tôi
tình nguyện viên ở đây, nếu bạn có thể.

1045
00:42:42,100 --> 00:42:45,320
>> [Vỗ tay]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. Malan: Được rồi.

1047
00:42:46,700 --> 00:42:51,110
Vì vậy, một vài phân tích
câu hỏi sau đó, nếu tôi có thể.

1048
00:42:51,110 --> 00:42:59,670
Chúng tôi đã nhìn thấy ký hiệu này trước đây,
O lớn và omega, cận trên

1049
00:42:59,670 --> 00:43:02,520
và giới hạn thấp hơn trên
thời gian chạy của một số thuật toán.

1050
00:43:02,520 --> 00:43:04,950
Vì vậy, chúng ta hãy xem xét chỉ
một vài câu hỏi.

1051
00:43:04,950 --> 00:43:07,090
>> Một, và chúng tôi đã nói nó
trước đó, các hoạt động là những gì

1052
00:43:07,090 --> 00:43:10,647
thời gian tìm kiếm một
danh sách về O lớn?

1053
00:43:10,647 --> 00:43:13,480
Có gì một trên ràng buộc về các hoạt động
thời gian tìm kiếm một danh sách liên kết

1054
00:43:13,480 --> 00:43:16,340
thực hiện bởi các tình nguyện viên của chúng tôi ở đây?

1055
00:43:16,340 --> 00:43:17,820
Đó là O lớn của n, tuyến tính.

1056
00:43:17,820 --> 00:43:20,630
Bởi vì trong trường hợp xấu nhất,
các yếu tố, như 55,

1057
00:43:20,630 --> 00:43:23,830
chúng ta có thể tìm kiếm có thể là nơi
Jack là, tất cả các cách ở cuối.

1058
00:43:23,830 --> 00:43:28,250
Và thật không may, không giống như một mảng
chúng ta không thể có được ưa thích thời gian này.

1059
00:43:28,250 --> 00:43:31,820
Mặc dù tất cả con người của chúng tôi đã
sắp xếp từ yếu tố nhỏ, 5,

1060
00:43:31,820 --> 00:43:35,900
tất cả các cách để các phần tử lớn hơn,
55, đó thường là một điều tốt.

1061
00:43:35,900 --> 00:43:38,815
Nhưng những gì giả định rằng
không còn cho phép chúng ta làm gì?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
TƯỢNG: [không nghe được]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. Malan: Nói một lần nữa?

1065
00:43:40,920 --> 00:43:41,800
TƯỢNG: Truy cập ngẫu nhiên.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. Malan: Truy cập ngẫu nhiên.

1067
00:43:43,049 --> 00:43:46,330
Và lần lượt có nghĩa là chúng ta có thể không có
còn sử dụng số không yếu, trực giác,

1068
00:43:46,330 --> 00:43:49,365
và hiển nhiên của việc sử dụng hệ nhị phân
Tìm kiếm và phân chia và chinh phục.

1069
00:43:49,365 --> 00:43:51,240
Bởi vì mặc dù chúng ta
con người có thể rõ ràng

1070
00:43:51,240 --> 00:43:54,610
thấy rằng Andy hoặc Kitô giáo
khoảng ở giữa danh sách,

1071
00:43:54,610 --> 00:43:57,670
chúng tôi chỉ biết đó là một
máy tính bằng cách lướt danh sách

1072
00:43:57,670 --> 00:43:59,029
ngay từ đầu.

1073
00:43:59,029 --> 00:44:00,570
Vì vậy, chúng tôi đã từ bỏ việc truy cập ngẫu nhiên.

1074
00:44:00,570 --> 00:44:04,380
>> O quá lớn của n bây giờ là trên
ràng buộc về thời gian tìm kiếm của chúng tôi.

1075
00:44:04,380 --> 00:44:07,920
Những gì về omega tìm của chúng tôi?

1076
00:44:07,920 --> 00:44:11,535
Có gì thấp hơn bị ràng buộc vào tìm kiếm
đối với một số số trong danh sách này?

1077
00:44:11,535 --> 00:44:12,410
TƯỢNG: [không nghe được]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. Malan: Nói một lần nữa?

1079
00:44:13,040 --> 00:44:13,420
TƯỢNG: Một.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. Malan: Một.

1081
00:44:13,800 --> 00:44:14,760
Vì vậy, thời gian liên tục.

1082
00:44:14,760 --> 00:44:17,020
Trong trường hợp tốt nhất, Christine là
thực sự vào đầu danh sách.

1083
00:44:17,020 --> 00:44:19,020
Và chúng tôi đang tìm kiếm
số 5, vì vậy chúng tôi tìm thấy cô.

1084
00:44:19,020 --> 00:44:19,787
Vì vậy, không có việc lớn.

1085
00:44:19,787 --> 00:44:22,370
Nhưng cô đã nhận được ở
bắt đầu của danh sách trong trường hợp này.

1086
00:44:22,370 --> 00:44:23,745
Những gì về một cái gì đó giống như Xóa?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Điều gì nếu bạn muốn xóa một phần tử?

1089
00:44:26,300 --> 00:44:29,200
Có gì các ràng buộc trên và dưới
về xóa một cái gì đó từ một liên kết

1090
00:44:29,200 --> 00:44:29,699
liệt kê?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
TƯỢNG: [không nghe được]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. Malan: Nói một lần nữa?

1094
00:44:36,420 --> 00:44:37,067
TƯỢNG: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. Malan: n là
thực sự là trên ràng buộc.

1096
00:44:38,900 --> 00:44:41,700
Bởi vì trong trường hợp xấu nhất chúng tôi cố gắng
xóa Jack, như chúng ta chỉ cần làm.

1097
00:44:41,700 --> 00:44:43,050
Anh ấy là tất cả các cách ở cuối.

1098
00:44:43,050 --> 00:44:45,419
Đưa chúng ta mãi mãi, hoặc
n bước để tìm thấy anh ta.

1099
00:44:45,419 --> 00:44:46,460
Vì vậy, đó là một ràng buộc trên.

1100
00:44:46,460 --> 00:44:47,430
Đó là tuyến tính, chắc chắn.

1101
00:44:47,430 --> 00:44:50,970
Và trường hợp tốt nhất thời gian chạy, hoặc
giới hạn thấp hơn trong trường hợp tốt nhất

1102
00:44:50,970 --> 00:44:51,975
sẽ là thời gian liên tục.

1103
00:44:51,975 --> 00:44:54,600
Bởi vì có lẽ chúng ta cố gắng để xóa
Christine, và chúng tôi chỉ nhận được may mắn

1104
00:44:54,600 --> 00:44:55,558
cô ấy lúc đầu.

1105
00:44:55,558 --> 00:44:56,350
Bây giờ chờ đợi một phút.

1106
00:44:56,350 --> 00:44:59,370
Gabe cũng là lúc đầu,
và chúng tôi cũng đã phải cập nhật Gabe.

1107
00:44:59,370 --> 00:45:01,150
Vì vậy, đó không chỉ là một bước.

1108
00:45:01,150 --> 00:45:04,210
Vì vậy, nó thực sự không đổi
thời gian, trong trường hợp tốt nhất,

1109
00:45:04,210 --> 00:45:06,345
để loại bỏ các phần tử nhỏ nhất?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Đó là, mặc dù nó có thể là hai,
ba, hoặc thậm chí 100 dòng mã,

1112
00:45:10,960 --> 00:45:14,000
nếu đó là cùng một số
dòng, không phải trong một số vòng lặp,

1113
00:45:14,000 --> 00:45:16,577
và độc lập với kích thước
danh sách, hoàn toàn.

1114
00:45:16,577 --> 00:45:18,660
Xóa các phần tử ở
đầu danh sách,

1115
00:45:18,660 --> 00:45:21,940
ngay cả khi chúng ta phải đối phó với
Gabe, vẫn còn thời gian liên tục.

1116
00:45:21,940 --> 00:45:24,220
>> Vì vậy, đây có vẻ như một
bước lớn về phía sau.

1117
00:45:24,220 --> 00:45:27,000
Và những gì một sự lãng phí thời gian
nếu, trong tuần đầu tiên và tuần

1118
00:45:27,000 --> 00:45:30,250
bằng không chúng tôi đã không chỉ
đang giả nhưng mã thực tế

1119
00:45:30,250 --> 00:45:35,780
để thực hiện một cái gì đó đăng nhập
cơ sở n, hoặc đăng nhập, thay vào đó, n, cơ sở 2,

1120
00:45:35,780 --> 00:45:37,150
về thời gian của nó đang chạy.

1121
00:45:37,150 --> 00:45:40,710
Vì vậy, tại sao các heck chúng tôi muốn bắt đầu
sử dụng một cái gì đó giống như một danh sách liên kết?

1122
00:45:40,710 --> 00:45:41,517
Yeah.

1123
00:45:41,517 --> 00:45:44,022
>> TƯỢNG: Vì vậy, bạn có thể thêm
các yếu tố để các mảng.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. Malan: Vì vậy, bạn có thể
thêm các yếu tố để các mảng.

1125
00:45:46,230 --> 00:45:47,550
Và đây cũng là chủ đề.

1126
00:45:47,550 --> 00:45:49,740
Và chúng ta sẽ tiếp tục thấy
này, này thương mại-off, nhiều

1127
00:45:49,740 --> 00:45:51,573
như chúng ta đã nhìn thấy một
thương mại-off với sắp xếp hợp nhất.

1128
00:45:51,573 --> 00:45:54,606
Chúng tôi thực sự có thể tăng tốc độ
tìm kiếm hoặc phân loại, thay vào đó,

1129
00:45:54,606 --> 00:45:57,480
nếu chúng ta dành nhiều không gian hơn chút và
có một đoạn bổ sung của một bộ nhớ

1130
00:45:57,480 --> 00:45:58,760
hoặc một mảng để sắp xếp hợp nhất.

1131
00:45:58,760 --> 00:46:01,270
Nhưng chúng ta chi tiêu nhiều hơn
không gian, nhưng chúng tôi tiết kiệm thời gian.

1132
00:46:01,270 --> 00:46:04,820
Trong trường hợp này, chúng tôi
bỏ thời gian nhưng chúng tôi

1133
00:46:04,820 --> 00:46:08,170
tăng tính linh hoạt,
năng động nếu bạn muốn,

1134
00:46:08,170 --> 00:46:10,280
mà được cho là một tính năng tích cực.

1135
00:46:10,280 --> 00:46:11,520
>> Chúng tôi cũng dành không gian.

1136
00:46:11,520 --> 00:46:13,710
Theo nghĩa là một liên kết
danh sách đắt tiền hơn

1137
00:46:13,710 --> 00:46:15,700
về không gian là một mảng?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Đâu là không gian mở rộng đến từ đâu?

1140
00:46:19,920 --> 00:46:20,460
Vâng?

1141
00:46:20,460 --> 00:46:21,800
>> TƯỢNG: [không nghe được] con trỏ.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. Malan: Vâng, chúng tôi
cũng có con trỏ.

1143
00:46:23,310 --> 00:46:25,560
Vì vậy, đây là minorly gây phiền nhiễu
trong đó không còn là

1144
00:46:25,560 --> 00:46:27,780
Tôi lưu trữ chỉ là một int
để đại diện cho một int.

1145
00:46:27,780 --> 00:46:30,990
Tôi đang lưu trữ một int và một
con trỏ, đó cũng là 32 bit.

1146
00:46:30,990 --> 00:46:33,470
Vì vậy, tôi nghĩa là tăng gấp đôi
số lượng không gian liên quan.

1147
00:46:33,470 --> 00:46:36,040
Vì vậy, đó là một sự đánh đổi, nhưng
đó là trong trường hợp của int.

1148
00:46:36,040 --> 00:46:39,580
Giả sử rằng bạn không lưu trữ int,
nhưng giả sử mỗi một trong các hình chữ nhật

1149
00:46:39,580 --> 00:46:43,290
hoặc mỗi con người được đại diện
một từ, một từ tiếng Anh mà

1150
00:46:43,290 --> 00:46:46,430
có thể là năm ký tự, 10
nhân vật, thậm chí có thể nhiều hơn nữa.

1151
00:46:46,430 --> 00:46:49,940
Sau đó thêm chỉ 32 bit hơn
có thể là ít hơn của một vấn đề lớn.

1152
00:46:49,940 --> 00:46:52,160
>> Nếu những gì mỗi người trong số các sinh viên
trong các cuộc biểu tình

1153
00:46:52,160 --> 00:46:55,107
có nghĩa là cấu trúc của sinh viên
có tên và nhà ở và có thể

1154
00:46:55,107 --> 00:46:57,065
số điện thoại và Twitter
xử lý và như thế nào.

1155
00:46:57,065 --> 00:46:59,564
Vì vậy, tất cả các trường chúng tôi bắt đầu
nói về những ngày khác,

1156
00:46:59,564 --> 00:47:02,410
ít hơn nhiều của một việc lớn như
các nút của chúng tôi trở nên thú vị hơn

1157
00:47:02,410 --> 00:47:05,972
và lớn để chi tiêu, eh, thêm
con trỏ chỉ để liên kết chúng lại với nhau.

1158
00:47:05,972 --> 00:47:07,180
Nhưng thực sự, đó là một sự đánh đổi.

1159
00:47:07,180 --> 00:47:09,560
Và quả thực, các mã được
phức tạp hơn, như bạn sẽ thấy

1160
00:47:09,560 --> 00:47:11,770
nhìn thấy bằng cách lướt qua
mà ví dụ cụ thể.

1161
00:47:11,770 --> 00:47:14,302
Nhưng nếu có
một số Chén thánh ở đây.

1162
00:47:14,302 --> 00:47:17,010
Nếu chúng ta không có một bước
ngược nhưng là một bước lớn về phía trước

1163
00:47:17,010 --> 00:47:19,180
và thực hiện một dữ liệu
cấu trúc thông qua đó chúng tôi

1164
00:47:19,180 --> 00:47:22,870
có thể tìm thấy các yếu tố như Jack hoặc
Christine hay bất kỳ yếu tố khác

1165
00:47:22,870 --> 00:47:25,870
trong mảng này trong đúng thời gian cố định?

1166
00:47:25,870 --> 00:47:26,920
Tìm kiếm là hằng số.

1167
00:47:26,920 --> 00:47:28,320
Xóa là hằng số.

1168
00:47:28,320 --> 00:47:29,570
Chèn là hằng số.

1169
00:47:29,570 --> 00:47:32,260
Tất cả các hoạt động này là không đổi.

1170
00:47:32,260 --> 00:47:33,750
Đó sẽ là Chén thánh của chúng tôi.

1171
00:47:33,750 --> 00:47:36,690
Và đó là nơi chúng tôi
sẽ nhận thời gian tới.

1172
00:47:36,690 --> 00:47:38,600
Hẹn gặp lại sau đó.

1173
00:47:38,600 --> 00:47:39,371