1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Được rồi, vì vậy đây là
CS50 Đây là phần cuối của tuần năm.

3
00:00:15,860 --> 00:00:19,220
Và nhớ rằng thời gian qua chúng tôi
bắt đầu nhìn vào các dữ liệu fancier

4
00:00:19,220 --> 00:00:22,310
cấu trúc bắt đầu để giải quyết
vấn đề, mà bắt đầu giới thiệu

5
00:00:22,310 --> 00:00:25,640
những vấn đề mới, nhưng phím này
là loại luồng mà chúng ta

6
00:00:25,640 --> 00:00:27,940
bắt đầu làm từ nút tới nút.

7
00:00:27,940 --> 00:00:30,085
Vì vậy, điều này tất nhiên là
một danh sách đơn lẻ liên kết.

8
00:00:30,085 --> 00:00:31,960
Và bằng cách đơn lẻ liên kết,
Tôi có nghĩa là chỉ một

9
00:00:31,960 --> 00:00:33,380
sợi giữa mỗi người trong những nút.

10
00:00:33,380 --> 00:00:35,890
Thì ra bạn có thể làm fancier
những thứ như danh sách liên kết kép

11
00:00:35,890 --> 00:00:38,470
nhờ đó mà bạn có một mũi tên
đi theo cả hai hướng, mà

12
00:00:38,470 --> 00:00:40,320
có thể giúp đỡ hiệu quả nhất định.

13
00:00:40,320 --> 00:00:42,000
Nhưng điều này đã giải quyết được vấn đề?

14
00:00:42,000 --> 00:00:43,500
Những vấn đề đã giải quyết này?

15
00:00:43,500 --> 00:00:46,620
Tại sao chúng ta quan tâm vào thứ hai?

16
00:00:46,620 --> 00:00:49,820
Tại sao, trên lý thuyết, đã làm chúng tôi quan tâm vào thứ hai?

17
00:00:49,820 --> 00:00:50,630
Nó làm gì?

18
00:00:50,630 --> 00:00:51,950
>> Đung Chúng tôi có thể tự động thay đổi kích thước.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, vì vậy chúng tôi có thể
tự động thay đổi kích thước.

20
00:00:53,740 --> 00:00:54,710
Thực hiện tốt cả hai bạn.

21
00:00:54,710 --> 00:00:57,560
Vì vậy, bạn có thể tự động thay đổi kích thước này
cấu trúc dữ liệu, trong khi một mảng,

22
00:00:57,560 --> 00:01:00,760
thu hồi, bạn cần phải biết một
priori bao nhiêu không gian bạn muốn

23
00:01:00,760 --> 00:01:03,870
và nếu bạn cần nhiều hơn một chút
không gian, bạn đang loại ra khỏi may mắn.

24
00:01:03,870 --> 00:01:05,560
Bạn phải tạo một mảng hoàn toàn mới.

25
00:01:05,560 --> 00:01:07,893
Bạn phải di chuyển tất cả các bạn
dữ liệu từ một đến khác,

26
00:01:07,893 --> 00:01:10,600
cuối cùng giải phóng mảng cũ
nếu bạn có thể, và sau đó tiến hành.

27
00:01:10,600 --> 00:01:13,891
Mà chỉ cảm thấy rất tốn kém và rất
không hiệu quả, và thực sự nó có thể được.

28
00:01:13,891 --> 00:01:14,890
Nhưng điều này là không hoàn toàn tốt.

29
00:01:14,890 --> 00:01:18,180
Chúng tôi phải trả giá, là một trong những gì
của giá rõ ràng hơn chúng tôi

30
00:01:18,180 --> 00:01:20,550
thanh toán bằng cách sử dụng một danh sách liên kết?

31
00:01:20,550 --> 00:01:22,825
>> Đung Chúng ta phải sử dụng
không gian gấp đôi cho mỗi một.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Yeah, vì vậy chúng tôi cần
ít nhất là hai lần như nhiều không gian.

33
00:01:25,200 --> 00:01:27,700
Trong thực tế, tôi nhận ra của hình ảnh này
thậm chí là một chút sai lệch,

34
00:01:27,700 --> 00:01:32,200
bởi vì trên CS50 IDE trong rất nhiều hiện đại
máy vi tính, một con trỏ hoặc địa chỉ

35
00:01:32,200 --> 00:01:33,700
không có trong thực tế bốn byte.

36
00:01:33,700 --> 00:01:36,090
Nó rất thường những
ngày tám byte, mà

37
00:01:36,090 --> 00:01:38,530
có nghĩa là phía dưới nhất
hình chữ nhật có trong thực tế

38
00:01:38,530 --> 00:01:40,900
là loại gấp đôi
lớn như những gì tôi đã rút ra,

39
00:01:40,900 --> 00:01:44,409
có nghĩa là bạn đang sử dụng ba lần
không gian nhiều như chúng ta có thể có cách khác.

40
00:01:44,409 --> 00:01:46,700
Bây giờ cùng một lúc, chúng tôi
vẫn nói byte, phải không?

41
00:01:46,700 --> 00:01:49,140
Chúng tôi không nhất thiết phải nói
MB hoặc GB,

42
00:01:49,140 --> 00:01:51,000
trừ khi các cấu trúc dữ liệu nhận được lớn.

43
00:01:51,000 --> 00:01:54,510
>> Và vì vậy hôm nay chúng tôi bắt đầu xem xét
làm thế nào chúng ta có thể khám phá dữ liệu

44
00:01:54,510 --> 00:01:57,310
hiệu quả hơn nếu trong
thực tế dữ liệu được lớn hơn.

45
00:01:57,310 --> 00:02:00,360
Nhưng chúng ta hãy cố gắng canonicalize
các hoạt động đầu tiên

46
00:02:00,360 --> 00:02:02,460
mà bạn có thể làm trên những
các loại cấu trúc dữ liệu.

47
00:02:02,460 --> 00:02:04,790
Vì vậy, một cái gì đó giống như một liên kết
danh sách thường hỗ trợ

48
00:02:04,790 --> 00:02:07,514
hoạt động như xóa,
chèn, và tìm kiếm.

49
00:02:07,514 --> 00:02:08,639
Và những gì tôi có nghĩa là bằng cách đó?

50
00:02:08,639 --> 00:02:11,222
Điều đó chỉ có nghĩa là thường,
nếu người đang sử dụng danh sách liên kết,

51
00:02:11,222 --> 00:02:14,287
họ hoặc người khác đã thực hiện
các chức năng như xóa, chèn,

52
00:02:14,287 --> 00:02:16,120
và tìm kiếm, vì vậy bạn có thể
thực sự làm một cái gì đó

53
00:02:16,120 --> 00:02:18,030
hữu ích với các cấu trúc dữ liệu.

54
00:02:18,030 --> 00:02:20,760
Vì vậy, chúng ta hãy có một cái nhìn nhanh chóng
làm thế nào chúng ta có thể thực hiện

55
00:02:20,760 --> 00:02:24,530
một số mã cho một danh sách liên kết như sau.

56
00:02:24,530 --> 00:02:27,885
>> Vì vậy, đây chỉ là một số mã C,
thậm chí không phải là một chương trình hoàn chỉnh

57
00:02:27,885 --> 00:02:29,260
mà tôi thực sự nhanh chóng đánh lên.

58
00:02:29,260 --> 00:02:32,300
Nó không trực tuyến trong việc phân phối
mã, bởi vì nó sẽ không thực sự chạy.

59
00:02:32,300 --> 00:02:33,790
Nhưng nhận thấy tôi đã chỉ
với một bình luận nói,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, có điều gì đó
có, chấm chấm chấm, một cái gì đó.

61
00:02:36,130 --> 00:02:38,410
Và chúng ta chỉ cần nhìn vào
những gì các phần ngon ngọt đang có.

62
00:02:38,410 --> 00:02:40,790
Vì vậy, trên dòng ba,
nhớ lại rằng đây là bây giờ

63
00:02:40,790 --> 00:02:45,960
chúng tôi đề xuất tuyên bố một nút cuối cùng
thời gian, một trong những đối tượng hình chữ nhật.

64
00:02:45,960 --> 00:02:48,790
Nó có một int mà chúng ta sẽ gọi N,
nhưng chúng ta có thể gọi nó là bất cứ điều gì,

65
00:02:48,790 --> 00:02:51,920
và sau đó một ngôi sao struct nút gọi tiếp theo.

66
00:02:51,920 --> 00:02:55,520
Và chỉ để được rõ ràng, thứ hai
dòng, trên dòng sáu, đó là những gì?

67
00:02:55,520 --> 00:02:57,930
Nó đang làm gì cho chúng ta?

68
00:02:57,930 --> 00:03:01,044
Bởi vì chắc chắn nó trông
khó hiểu hơn các biến thông thường của chúng tôi.

69
00:03:01,044 --> 00:03:02,740
>> Đung Nó làm cho nó di chuyển trên một.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Nó làm cho nó di chuyển trên một.

71
00:03:04,650 --> 00:03:08,580
Và để được chính xác hơn,
nó sẽ lưu trữ địa chỉ

72
00:03:08,580 --> 00:03:11,582
của nút đó có nghĩa là phải
ngữ nghĩa bên cạnh nó, phải không?

73
00:03:11,582 --> 00:03:13,540
Vì vậy, nó không phải đi làm
nhất thiết phải di chuyển bất cứ điều gì.

74
00:03:13,540 --> 00:03:15,290
Nó chỉ đi
lưu trữ một giá trị, đó là

75
00:03:15,290 --> 00:03:17,170
sẽ là địa chỉ
của một số nút khác,

76
00:03:17,170 --> 00:03:20,810
và đó là lý do tại sao chúng tôi đã nói struct
sao nút, ngôi sao biểu thị

77
00:03:20,810 --> 00:03:22,370
một con trỏ hoặc một địa chỉ.

78
00:03:22,370 --> 00:03:26,390
OK, vì vậy bây giờ nếu bạn cho rằng chúng ta có
N này có sẵn cho chúng ta, và chúng ta hãy

79
00:03:26,390 --> 00:03:29,490
giả định rằng người nào khác có
chèn một bó toàn bộ các số nguyên

80
00:03:29,490 --> 00:03:30,400
vào một danh sách liên kết.

81
00:03:30,400 --> 00:03:35,640
Và đó là danh sách liên kết
trỏ đến bởi một số điểm

82
00:03:35,640 --> 00:03:39,040
một biến gọi là danh sách đó là
thông qua tại đây như là một tham số,

83
00:03:39,040 --> 00:03:43,120
làm thế nào để tôi đi về dòng
14 thực hiện tìm kiếm?

84
00:03:43,120 --> 00:03:45,990
Nói cách khác, nếu tôi đang thực hiện
chức năng, mục đích trong cuộc sống

85
00:03:45,990 --> 00:03:48,889
là để có một int và sau đó
bắt đầu của một danh sách liên kết,

86
00:03:48,889 --> 00:03:50,430
đó là một con trỏ trỏ tới các danh sách liên kết.

87
00:03:50,430 --> 00:03:52,992
Giống như lần đầu tiên, những người tôi nghĩ David
là tình nguyện viên của chúng tôi vào thứ hai,

88
00:03:52,992 --> 00:03:54,700
ông đã chỉ tay vào
toàn bộ danh sách liên kết,

89
00:03:54,700 --> 00:03:57,820
nó như chúng ta đang đi qua
David trong như là đối số của chúng tôi ở đây.

90
00:03:57,820 --> 00:03:59,990
Làm thế nào để chúng tôi đi về vượt qua danh sách này?

91
00:03:59,990 --> 00:04:04,640
Vâng, nó chỉ ra rằng mặc dù
con trỏ là tương đối mới bây giờ cho chúng tôi,

92
00:04:04,640 --> 00:04:07,010
chúng ta có thể làm điều này tương đối
thẳng thắn.

93
00:04:07,010 --> 00:04:09,500
>> Tôi sẽ đi trước và
khai báo một biến tạm thời mà

94
00:04:09,500 --> 00:04:12,364
theo quy ước là chỉ cần đi
để được gọi là con trỏ, hoặc PTR,

95
00:04:12,364 --> 00:04:14,030
nhưng bạn có thể gọi nó là bất cứ điều gì bạn muốn.

96
00:04:14,030 --> 00:04:16,470
Và tôi sẽ phải khởi tạo
nó cho sự bắt đầu của danh sách.

97
00:04:16,470 --> 00:04:20,050
Vì vậy, bạn có thể loại nghĩ về điều này
như tôi những giáo viên khác trong ngày,

98
00:04:20,050 --> 00:04:23,580
loại chỉ tay vào một người nào đó
trong số người của chúng tôi là tình nguyện viên.

99
00:04:23,580 --> 00:04:26,470
Vì vậy, tôi là một biến tạm thời đó là
chỉ chỉ tay vào điều tương tự

100
00:04:26,470 --> 00:04:31,390
mà chúng tôi tình cờ được đặt tên
tình nguyện viên David cũng đã được chỉ ra.

101
00:04:31,390 --> 00:04:35,440
Bây giờ trong khi con trỏ là
không null, vì thu hồi

102
00:04:35,440 --> 00:04:40,350
không cho rằng một số giá trị trọng điểm đặc biệt
các demarcates cuối danh sách,

103
00:04:40,350 --> 00:04:44,280
như vậy trong khi tôi không chỉ vào
mặt đất giống như tình nguyện viên của chúng tôi cuối cùng

104
00:04:44,280 --> 00:04:47,190
là, chúng ta hãy đi trước
và làm như sau.

105
00:04:47,190 --> 00:04:51,820
Nếu pointer-- và bây giờ tôi loại muốn
để làm những gì chúng ta đã làm với học sinh

106
00:04:51,820 --> 00:04:57,410
structure-- nếu con trỏ chấm tiếp theo
equals-- thay, nếu con trỏ dot N bằng

107
00:04:57,410 --> 00:05:02,290
bằng các biến N,
Lập luận đó là được thông qua tại,

108
00:05:02,290 --> 00:05:05,370
sau đó tôi muốn đi trước
và nói trở thành sự thật.

109
00:05:05,370 --> 00:05:11,020
Tôi đã tìm thấy các số N bên trong
một trong các nút của danh sách liên kết của tôi.

110
00:05:11,020 --> 00:05:13,500
Nhưng dấu chấm không còn
hoạt động trong bối cảnh này,

111
00:05:13,500 --> 00:05:17,260
vì con trỏ, PTR, là
thực sự là một con trỏ, một địa chỉ,

112
00:05:17,260 --> 00:05:20,632
chúng ta có thể thực sự tuyệt vời
sử dụng cuối cùng là một mảnh của cú pháp

113
00:05:20,632 --> 00:05:22,590
loại đó làm cho
cảm giác trực quan và thực tế

114
00:05:22,590 --> 00:05:27,870
sử dụng một mũi tên ở đây, có nghĩa là đi từ
địa chỉ đó cho các số nguyên có trong.

115
00:05:27,870 --> 00:05:30,160
Vì vậy, nó rất giống trong
tinh thần cho người điều khiển dot,

116
00:05:30,160 --> 00:05:33,860
nhưng vì con trỏ không phải là một con trỏ
và không phải là một cấu trúc thực tế bản thân,

117
00:05:33,860 --> 00:05:35,380
chúng ta chỉ cần sử dụng các mũi tên.

118
00:05:35,380 --> 00:05:40,620
>> Vì vậy, nếu nút hiện tại mà tôi, các
biến tạm thời, đang chỉ tay vào

119
00:05:40,620 --> 00:05:43,060
không tồn tại, những gì tôi muốn làm gì?

120
00:05:43,060 --> 00:05:45,910
Vâng, với những người tình nguyện của tôi
mà chúng tôi đã ở đây trong ngày khác,

121
00:05:45,910 --> 00:05:49,710
nếu con người đầu tiên của tôi không phải là một trong tôi
muốn, và có lẽ những con người thứ hai là không

122
00:05:49,710 --> 00:05:52,660
thứ mà mình muốn, và thứ ba, tôi
cần phải giữ thể chất di chuyển.

123
00:05:52,660 --> 00:05:54,690
Cũng giống như làm thế nào để tôi bước qua một danh sách?

124
00:05:54,690 --> 00:05:57,470
Khi chúng tôi đã có một mảng, bạn
chỉ cần làm như tôi cộng với cộng với.

125
00:05:57,470 --> 00:06:03,660
Nhưng trong trường hợp này, nó cũng đủ để
làm con trỏ, được, con trỏ, tiếp theo.

126
00:06:03,660 --> 00:06:07,580
Nói cách khác, các trường tiếp theo
cũng giống như tất cả các tay trái

127
00:06:07,580 --> 00:06:10,880
rằng những người tình nguyện của chúng tôi vào thứ hai
đã sử dụng đến điểm tại một số nút khác.

128
00:06:10,880 --> 00:06:12,890
Đó là những người hàng xóm tiếp theo của họ.

129
00:06:12,890 --> 00:06:17,060
>> Vì vậy, nếu tôi muốn bước qua danh sách này,
Tôi không thể chỉ làm tôi cộng với cộng nữa,

130
00:06:17,060 --> 00:06:20,120
Tôi thay vì phải nói
Tôi, con trỏ, được đi

131
00:06:20,120 --> 00:06:24,650
để bằng bất cứ lĩnh vực kế tiếp là,
các lĩnh vực tiếp theo là, lĩnh vực tiếp theo là,

132
00:06:24,650 --> 00:06:28,350
sau tất cả những bàn tay trái
rằng chúng tôi đã có trên sân khấu trỏ

133
00:06:28,350 --> 00:06:30,000
để một số giá trị tiếp theo.

134
00:06:30,000 --> 00:06:32,590
Và nếu tôi có được thông qua
rằng toàn bộ lặp,

135
00:06:32,590 --> 00:06:39,330
và cuối cùng, tôi nhấn vô không có
N thấy chưa, tôi chỉ trả về false.

136
00:06:39,330 --> 00:06:44,100
Vì vậy, một lần nữa, tất cả những gì chúng tôi đang làm ở đây,
theo hình ảnh một thời gian trước đây,

137
00:06:44,100 --> 00:06:47,840
được bắt đầu bằng cách chỉ vào
bắt đầu của danh sách có lẽ.

138
00:06:47,840 --> 00:06:50,970
Và sau đó tôi kiểm tra, là giá trị
Tôi đang tìm cho bằng chín?

139
00:06:50,970 --> 00:06:52,650
Nếu vậy, tôi trở thành sự thật và tôi đang làm.

140
00:06:52,650 --> 00:06:56,450
Nếu không, tôi cập nhật tay tôi,
AKA con trỏ, trỏ

141
00:06:56,450 --> 00:06:59,540
tại vị trí mũi tên bên cạnh, và
sau đó vị trí mũi tên tới,

142
00:06:59,540 --> 00:07:00,480
và tiếp theo.

143
00:07:00,480 --> 00:07:03,770
Tôi chỉ đơn giản là đi bộ qua mảng này.

144
00:07:03,770 --> 00:07:06,010
>> Vì vậy, một lần nữa, những người quan tâm?

145
00:07:06,010 --> 00:07:07,861
Như thế này là những gì một thành phần?

146
00:07:07,861 --> 00:07:10,360
Vâng, nhớ lại rằng chúng tôi giới thiệu
khái niệm về một chồng, mà

147
00:07:10,360 --> 00:07:15,400
là gõ một dữ liệu trừu tượng trong chừng mực nó
không phải là một điều C, nó không phải là một điều CS50,

148
00:07:15,400 --> 00:07:19,430
nó là một ý tưởng trừu tượng, ý tưởng này của
xếp thứ trên đầu trang của nhau

149
00:07:19,430 --> 00:07:21,820
có thể được thực hiện trong
chùm cách khác nhau.

150
00:07:21,820 --> 00:07:25,600
Và một trong những cách mà chúng tôi đề xuất là có
một mảng, hoặc với một danh sách liên kết.

151
00:07:25,600 --> 00:07:29,570
Và nó chỉ ra rằng theo giáo luật, một
stack hỗ trợ ít nhất hai hoạt động.

152
00:07:29,570 --> 00:07:32,320
Và những lời đồn là push, để
đẩy một cái gì đó vào ngăn xếp,

153
00:07:32,320 --> 00:07:34,770
như một khay mới trong
phòng ăn, hoặc pop,

154
00:07:34,770 --> 00:07:39,000
có nghĩa là để loại bỏ các topmost
Khay từ stack trong ăn uống

155
00:07:39,000 --> 00:07:41,500
hội trường, và sau đó có thể một số
các hoạt động khác.

156
00:07:41,500 --> 00:07:45,770
Vậy làm thế nào chúng ta có thể xác định cấu trúc
mà bây giờ chúng tôi đang kêu gọi một chồng?

157
00:07:45,770 --> 00:07:50,020
>> Vâng, chúng tôi có tất cả các điều kiện tiên quyết của
cú pháp mà chúng ta có trong C. Tôi nói,

158
00:07:50,020 --> 00:07:53,830
cho tôi một định nghĩa loại
một cấu trúc bên trong của một chồng,

159
00:07:53,830 --> 00:07:58,030
Tôi sẽ nói là một mảng, một
bó toàn bộ các con số và sau đó kích thước.

160
00:07:58,030 --> 00:08:00,930
Vì vậy, nói cách khác, nếu tôi muốn
để thực hiện điều này trong mã,

161
00:08:00,930 --> 00:08:03,830
hãy để tôi đi và chỉ cần loại
rút ra những gì này là nói.

162
00:08:03,830 --> 00:08:06,317
Vì vậy, đây là nói, cho tôi một
cấu trúc đó là có một mảng,

163
00:08:06,317 --> 00:08:09,400
và tôi không biết khả năng là những gì,
nó dường như một số hằng số mà tôi đã

164
00:08:09,400 --> 00:08:10,858
định nghĩa ở đâu, và đó là tốt.

165
00:08:10,858 --> 00:08:15,260
Nhưng giả sử nó chỉ là một,
hai, ba, bốn, năm.

166
00:08:15,260 --> 00:08:16,700
Vì vậy, công suất là 5.

167
00:08:16,700 --> 00:08:21,730
Yếu tố này bên trong của tôi
cấu trúc sẽ được gọi là con số.

168
00:08:21,730 --> 00:08:24,020
Và sau đó tôi cần một
biến khác rõ ràng

169
00:08:24,020 --> 00:08:27,814
gọi là kích thước mà ban đầu tôi sẽ
để quy định được khởi tạo bằng không.

170
00:08:27,814 --> 00:08:29,730
Nếu không có gì trong
ngăn xếp, kích thước là số không,

171
00:08:29,730 --> 00:08:31,420
và nó là giá trị rác với số lượng.

172
00:08:31,420 --> 00:08:33,450
Tôi không có ý tưởng những gì trong đó chỉ được nêu ra.

173
00:08:33,450 --> 00:08:36,059
>> Vì vậy, nếu tôi muốn đẩy
một cái gì đó vào ngăn xếp,

174
00:08:36,059 --> 00:08:40,780
giả sử tôi gọi hàm push, và
Tôi nói đẩy 50, như số 50,

175
00:08:40,780 --> 00:08:44,090
nơi mà bạn sẽ đề xuất
Tôi vẽ nó trong mảng này?

176
00:08:44,090 --> 00:08:47,124
Có năm câu trả lời khác nhau có thể.

177
00:08:47,124 --> 00:08:48,790
Nơi nào bạn muốn đẩy số 50?

178
00:08:48,790 --> 00:08:51,899
Nếu mục tiêu ở đây, một lần nữa, hãy gọi
chức năng push, vượt qua trong một cuộc tranh cãi

179
00:08:51,899 --> 00:08:52,940
50, nơi nào tôi đặt nó?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Năm possible-- 20% cơ hội
đoán một cách chính xác.

182
00:08:59,052 --> 00:08:59,896
Có?

183
00:08:59,896 --> 00:09:00,740
>> Đung Viễn đúng.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Far phải.

185
00:09:01,990 --> 00:09:08,359
Bây giờ có một cơ hội 25%
đoán một cách chính xác.

186
00:09:08,359 --> 00:09:09,650
Vì vậy, đó thực sự sẽ được tốt.

187
00:09:09,650 --> 00:09:12,770
Theo quy ước, tôi sẽ nói với một mảng,
chúng ta thường sẽ bắt đầu từ bên trái,

188
00:09:12,770 --> 00:09:14,519
nhưng chúng ta có thể chắc chắn
bắt đầu ở bên phải.

189
00:09:14,519 --> 00:09:17,478
Vì vậy, các spoiler ở đây sẽ là tôi
có lẽ sẽ vẽ nó trên bên trái,

190
00:09:17,478 --> 00:09:20,060
giống như trong một mảng bình thường mà
Tôi bắt đầu đi từ trái sang phải.

191
00:09:20,060 --> 00:09:21,780
Nhưng nếu bạn có thể lật
số học, tiền phạt.

192
00:09:21,780 --> 00:09:23,060
Nó chỉ là không thông thường.

193
00:09:23,060 --> 00:09:24,880
OK, tôi cần phải thực hiện một
nhiều thay đổi mặc dù.

194
00:09:24,880 --> 00:09:27,710
Bây giờ tôi đã đẩy một cái gì đó
vào ngăn xếp, những gì tiếp theo?

195
00:09:27,710 --> 00:09:29,400
>> Được rồi, tôi phải tăng kích thước.

196
00:09:29,400 --> 00:09:32,600
Vì vậy, hãy để tôi đi trước và chỉ
cập nhật này, đó là số không.

197
00:09:32,600 --> 00:09:35,950
Và thay vì bây giờ, tôi sẽ
để đưa vào một giá trị.

198
00:09:35,950 --> 00:09:39,460
Và bây giờ giả sử tôi đẩy khác
số vào stack, như 51.

199
00:09:39,460 --> 00:09:42,680
Vâng, tôi phải thực hiện thêm một
thay đổi, đó là lên đến kích thước hai.

200
00:09:42,680 --> 00:09:46,100
Và sau đó giả sử tôi đẩy thêm một
số vào stack như 61,

201
00:09:46,100 --> 00:09:52,530
bây giờ tôi cần phải cập nhật kích thước thêm một
thời gian, và có được giá trị 3 như kích thước.

202
00:09:52,530 --> 00:09:54,690
Và bây giờ giả sử tôi gọi pop.

203
00:09:54,690 --> 00:09:57,250
Bây giờ bật, theo quy ước,
không mất một đối số.

204
00:09:57,250 --> 00:10:00,430
Với một chồng, toàn bộ
điểm của các ẩn dụ khay

205
00:10:00,430 --> 00:10:03,450
là bạn không có quyền tự quyết
đi lấy khay đó, tất cả các bạn có thể làm

206
00:10:03,450 --> 00:10:06,330
được bật một topmost từ
ngăn xếp, chỉ vì.

207
00:10:06,330 --> 00:10:08,010
Đó là những gì cấu trúc dữ liệu này không.

208
00:10:08,010 --> 00:10:12,250
>> Vì vậy, bằng cách logic rằng nếu tôi
nói pop, những gì đi off?

209
00:10:12,250 --> 00:10:13,080
Vì vậy, 61.

210
00:10:13,080 --> 00:10:15,402
Vì vậy, những gì thực sự là máy tính
sẽ làm gì trong bộ nhớ?

211
00:10:15,402 --> 00:10:16,610
Những gì hiện mã của tôi phải làm gì?

212
00:10:16,610 --> 00:10:20,330
Những gì bạn sẽ đề xuất
chúng ta thay đổi trên màn hình?

213
00:10:20,330 --> 00:10:23,410
Điều gì cần thay đổi?

214
00:10:23,410 --> 00:10:24,960
Xin lỗi?

215
00:10:24,960 --> 00:10:26,334
Vì vậy, chúng ta thoát khỏi 61.

216
00:10:26,334 --> 00:10:27,500
Vì vậy, tôi chắc chắn có thể làm điều đó.

217
00:10:27,500 --> 00:10:28,640
Và tôi có thể thoát khỏi 61.

218
00:10:28,640 --> 00:10:30,980
Và sau đó những gì khác
thay đổi cần phải xảy ra?

219
00:10:30,980 --> 00:10:33,160
Kích thước có lẽ phải trở lại để hai.

220
00:10:33,160 --> 00:10:34,210
Và đó là tốt.

221
00:10:34,210 --> 00:10:36,690
Nhưng chờ một phút, kích thước
một thời điểm cách đây ba tuổi.

222
00:10:36,690 --> 00:10:38,240
Hãy làm một kiểm tra sự tỉnh táo nhanh chóng.

223
00:10:38,240 --> 00:10:41,810
Làm sao chúng ta biết rằng chúng ta
muốn thoát khỏi 61?

224
00:10:41,810 --> 00:10:42,760
Bởi vì chúng tôi đang popping.

225
00:10:42,760 --> 00:10:46,450
Và vì vậy tôi có kích thước tài sản thứ hai này.

226
00:10:46,450 --> 00:10:48,470
>> Chờ một phút, tôi
nghĩ lại hai tuần

227
00:10:48,470 --> 00:10:51,660
khi chúng tôi bắt đầu nói chuyện về
mảng, nơi này là địa điểm không,

228
00:10:51,660 --> 00:10:55,920
này là địa điểm duy nhất, đây là vị trí
hai, đây là vị trí ba, bốn,

229
00:10:55,920 --> 00:10:58,460
nó trông giống như
mối quan hệ giữa kích thước

230
00:10:58,460 --> 00:11:02,780
và các yếu tố mà tôi muốn loại bỏ
từ mảng này dường như chỉ là những gì?

231
00:11:02,780 --> 00:11:05,120
Kích trừ đi một.

232
00:11:05,120 --> 00:11:07,786
Và đó là cách như con người
chúng ta biết 61 đến trước.

233
00:11:07,786 --> 00:11:09,160
Làm thế nào của máy tính sẽ biết?

234
00:11:09,160 --> 00:11:11,701
Khi mã của bạn, nơi bạn có thể
muốn làm kích thước trừ một,

235
00:11:11,701 --> 00:11:14,950
như vậy ba trừ đi một là hai, và rằng
nghĩa là chúng ta muốn thoát khỏi 61.

236
00:11:14,950 --> 00:11:18,000
Và sau đó, chúng tôi thực sự có thể cập nhật
kích thước quá cỡ mà bây giờ

237
00:11:18,000 --> 00:11:20,300
đi từ ba đến chỉ hai.

238
00:11:20,300 --> 00:11:24,520
Và chỉ để được gàn dở, tôi sẽ
đề nghị mà tôi đang thực hiện, phải không?

239
00:11:24,520 --> 00:11:27,660
Bạn đề nghị trực giác
đúng tôi nên thoát khỏi 61.

240
00:11:27,660 --> 00:11:30,700
Nhưng có phải tôi loại
loại gạt bỏ 61?

241
00:11:30,700 --> 00:11:33,790
Tôi đã quên mất hiệu quả
rằng nó thực sự ở đó.

242
00:11:33,790 --> 00:11:37,680
Và nghĩ lại PSET4, nếu bạn đã đọc
các bài viết về pháp y, các PDF

243
00:11:37,680 --> 00:11:40,780
rằng chúng tôi đã có các bạn đọc, hoặc bạn
sẽ đọc trong tuần này cho PSET4.

244
00:11:40,780 --> 00:11:44,300
Nhớ lại rằng đây thực sự Gecman để
toàn bộ ý tưởng của pháp y máy tính.

245
00:11:44,300 --> 00:11:47,820
Những gì một máy tính thông thường, không có gì
nó chỉ là một cái gì đó mà quên là,

246
00:11:47,820 --> 00:11:51,300
nhưng nó không đi vào và như
cố gắng đầu nó ra hoặc ghi đè

247
00:11:51,300 --> 00:11:54,560
các bit với số không và những người thân
hoặc một số mẫu ngẫu nhiên khác

248
00:11:54,560 --> 00:11:56,690
trừ khi bạn tự mình cố tình làm như vậy.

249
00:11:56,690 --> 00:11:58,930
Vì vậy, trực giác của bạn là
phải, hãy thoát khỏi 61.

250
00:11:58,930 --> 00:12:00,650
Nhưng trong thực tế, chúng ta không cần phải bận tâm.

251
00:12:00,650 --> 00:12:04,040
Chúng ta chỉ cần quên rằng
nó ở đó bằng cách thay đổi kích thước của chúng tôi.

252
00:12:04,040 --> 00:12:05,662
>> Bây giờ có một vấn đề với chồng này.

253
00:12:05,662 --> 00:12:07,620
Nếu tôi tiếp tục đẩy mạnh việc
vào ngăn xếp, có gì

254
00:12:07,620 --> 00:12:11,167
rõ ràng là sẽ xảy ra
chỉ trong một thời gian vài phút?

255
00:12:11,167 --> 00:12:12,500
Chúng tôi đang đi để chạy ra khỏi không gian.

256
00:12:12,500 --> 00:12:13,580
Và chúng ta làm gì?

257
00:12:13,580 --> 00:12:14,680
Chúng tôi đang loại hơi say.

258
00:12:14,680 --> 00:12:19,000
Việc thực hiện này không cho phép
chúng tôi thay đổi kích thước mảng, bởi vì sử dụng

259
00:12:19,000 --> 00:12:21,240
cú pháp này, nếu bạn
nghĩ lại hai tuần,

260
00:12:21,240 --> 00:12:23,520
một khi bạn đã khai báo
kích thước của một mảng,

261
00:12:23,520 --> 00:12:26,780
chúng tôi đã không nhìn thấy một cơ chế nào đó
bạn có thể thay đổi kích thước của mảng.

262
00:12:26,780 --> 00:12:29,020
Và thực sự C không có tính năng đó.

263
00:12:29,020 --> 00:12:32,524
Nếu bạn nói cho tôi năm
Nths, gọi cho họ số,

264
00:12:32,524 --> 00:12:33,940
đó là tất cả các bạn đang đi để có được nó.

265
00:12:33,940 --> 00:12:38,790
Vì vậy, chúng tôi bây giờ là thứ Hai, có
khả năng thể hiện một giải pháp

266
00:12:38,790 --> 00:12:42,480
Mặc dù vậy, chúng ta chỉ cần tinh chỉnh
định nghĩa của ngăn xếp của chúng tôi

267
00:12:42,480 --> 00:12:46,840
để không có một số mảng cứng mã hóa,
nhưng chỉ để lưu trữ một địa chỉ.

268
00:12:46,840 --> 00:12:47,890
>> Bây giờ tại sao điều này là?

269
00:12:47,890 --> 00:12:51,690
Bây giờ chúng ta chỉ cần có để được thoải mái với
thực tế là khi chương trình của tôi chạy,

270
00:12:51,690 --> 00:12:53,730
Tôi có lẽ sẽ
phải yêu cầu nhân lực,

271
00:12:53,730 --> 00:12:55,110
bao nhiêu số nào bạn muốn để lưu trữ?

272
00:12:55,110 --> 00:12:56,776
Vì vậy, các đầu vào đã đến từ một nơi nào đó.

273
00:12:56,776 --> 00:12:59,140
Nhưng một khi tôi biết rằng
số lượng, sau đó tôi có thể chỉ

274
00:12:59,140 --> 00:13:02,470
sử dụng hàm nào để cung cấp cho
tôi một đoạn bộ nhớ?

275
00:13:02,470 --> 00:13:03,580
Tôi có thể sử dụng malloc.

276
00:13:03,580 --> 00:13:06,710
Và tôi có thể nói bất kỳ số lượng
byte tôi muốn trở lại cho những Nths.

277
00:13:06,710 --> 00:13:10,910
Và tất cả tôi có để lưu trữ trong các con số
biến ở đây bên trong cấu trúc này

278
00:13:10,910 --> 00:13:13,480
nên được những gì?

279
00:13:13,480 --> 00:13:18,440
Điều gì thực sự đi vào
số trong kịch bản này?

280
00:13:18,440 --> 00:13:21,300
Yeah, một con trỏ đến đầu tiên
byte mà đoạn bộ nhớ,

281
00:13:21,300 --> 00:13:24,940
hay cụ thể hơn, địa chỉ
của đầu tiên của những byte.

282
00:13:24,940 --> 00:13:27,300
Không quan trọng nếu nó là một
byte hoặc một tỷ byte,

283
00:13:27,300 --> 00:13:28,890
Tôi chỉ cần phải quan tâm đầu tiên.

284
00:13:28,890 --> 00:13:31,530
Bởi vì những gì đảm bảo malloc và
đảm bảo hệ thống điều hành của tôi,

285
00:13:31,530 --> 00:13:34,170
là các đoạn bộ nhớ tôi
nhận được, nó sẽ được tiếp giáp.

286
00:13:34,170 --> 00:13:35,378
Có sẽ không có những khoảng trống.

287
00:13:35,378 --> 00:13:38,576
Vì vậy, nếu tôi đã yêu cầu 50
byte hoặc 1000 byte,

288
00:13:38,576 --> 00:13:40,450
họ đang tất cả sẽ được
trở lại trở lại để trở lại.

289
00:13:40,450 --> 00:13:44,500
Và chừng nào tôi còn nhớ lớn như thế nào, làm thế nào
nhiều tôi yêu cầu, tất cả tôi cần biết

290
00:13:44,500 --> 00:13:46,230
là địa chỉ đầu tiên như vậy.

291
00:13:46,230 --> 00:13:48,660
>> Vì vậy, bây giờ chúng tôi có khả năng trong mã.

292
00:13:48,660 --> 00:13:51,280
Mặc dù, nó sẽ đưa chúng ta
nhiều thời gian hơn để viết này lên,

293
00:13:51,280 --> 00:13:55,900
bây giờ chúng ta có thể tái phân bổ bộ nhớ bởi
chỉ lưu trữ một địa chỉ khác nhau ở đó

294
00:13:55,900 --> 00:13:59,060
nếu chúng ta muốn có một lớn hơn hoặc thậm chí
một đoạn nhỏ hơn của bộ nhớ.

295
00:13:59,060 --> 00:14:00,170
Vì vậy, ở đây thành ra thương mại.

296
00:14:00,170 --> 00:14:01,360
Bây giờ chúng ta có được tính năng động.

297
00:14:01,360 --> 00:14:03,350
Chúng ta vẫn có
contiguousness Tôi tuyên bố.

298
00:14:03,350 --> 00:14:05,881
Bởi vì malloc sẽ cho chúng ta
một đoạn tiếp giáp của bộ nhớ.

299
00:14:05,881 --> 00:14:08,630
Nhưng điều này là có được một cơn đau ở
cổ cho chúng tôi, các lập trình viên,

300
00:14:08,630 --> 00:14:09,770
để thực sự mã lên.

301
00:14:09,770 --> 00:14:10,730
Đó là công việc chỉ hơn.

302
00:14:10,730 --> 00:14:13,930
Chúng tôi cần có mã giống như những gì tôi đã
đập ra chỉ một thời gian trước đây.

303
00:14:13,930 --> 00:14:16,120
Rất có thể làm được, nhưng nó thêm phức tạp.

304
00:14:16,120 --> 00:14:19,520
Và vì vậy thời gian phát triển, lập trình
Hiện vẫn chưa tài nguyên khác

305
00:14:19,520 --> 00:14:22,520
rằng chúng ta có thể cần phải chi tiêu
một thời gian để có được các tính năng mới.

306
00:14:22,520 --> 00:14:24,020
Và sau đó tất nhiên là có một hàng đợi.

307
00:14:24,020 --> 00:14:26,227
Chúng tôi sẽ không đi vào này
một trong nhiều chi tiết.

308
00:14:26,227 --> 00:14:27,560
Nhưng nó rất tinh thần tương tự.

309
00:14:27,560 --> 00:14:31,220
Tôi có thể thực hiện một hàng đợi, và
hoạt động tương ứng của nó,

310
00:14:31,220 --> 00:14:35,660
enqueue hoặc dequeue, như thêm hoặc loại bỏ,
nó chỉ là một cách nói fancier của nó,

311
00:14:35,660 --> 00:14:38,100
enqueue hoặc dequeue, như sau.

312
00:14:38,100 --> 00:14:41,170
Tôi chỉ có thể cung cấp cho bản thân mình một cấu trúc
mà lại có mảng của một số,

313
00:14:41,170 --> 00:14:44,000
mà lại có một kích thước,
nhưng tại sao bây giờ tôi cần

314
00:14:44,000 --> 00:14:46,940
để theo dõi phía trước của một hàng đợi?

315
00:14:46,940 --> 00:14:50,630
Tôi không cần biết
mặt trước của chồng tôi.

316
00:14:50,630 --> 00:14:53,570
Vâng, nếu tôi một lần nữa cho một
queue-- hãy chỉ cứng

317
00:14:53,570 --> 00:14:57,870
mã nó như có như năm
số nguyên ở đây có tiềm năng.

318
00:14:57,870 --> 00:15:00,940
Vì vậy, đây là số không, một, hai, ba, bốn.

319
00:15:00,940 --> 00:15:03,430
Điều này là có được
gọi là số một lần nữa.

320
00:15:03,430 --> 00:15:06,940
Và điều này sẽ được gọi là kích thước.

321
00:15:06,940 --> 00:15:10,056
>> Tại sao nó không đủ
để có chỉ là kích thước?

322
00:15:10,056 --> 00:15:11,680
Vâng, chúng ta hãy đẩy những con số tương tự trên.

323
00:15:11,680 --> 00:15:14,220
Vì vậy, tôi pushed-- tôi enqueued, hoặc bị đẩy.

324
00:15:14,220 --> 00:15:20,150
Bây giờ tôi sẽ enqueue 50, và sau đó
51, và sau đó là 61, và đánh dấu chấm chấm chấm.

325
00:15:20,150 --> 00:15:21,070
Vì vậy, đó là enqueue.

326
00:15:21,070 --> 00:15:23,176
Tôi enqueued 50, sau đó 51, sau đó 61.

327
00:15:23,176 --> 00:15:25,050
Và đó trông giống hệt nhau
để một chồng cho đến nay,

328
00:15:25,050 --> 00:15:27,190
ngoại trừ tôi cần phải thực hiện một sự thay đổi.

329
00:15:27,190 --> 00:15:33,680
Tôi cần phải cập nhật kích thước này, vì vậy tôi đi
từ số không đến một đến 2-3 giờ.

330
00:15:33,680 --> 00:15:35,760
Làm thế nào để dequeue?

331
00:15:35,760 --> 00:15:36,890
Điều gì xảy ra với dequeue?

332
00:15:36,890 --> 00:15:41,950
Ai nên đi ra khỏi danh sách này đầu tiên
nếu đó là dòng tại các cửa hàng của Apple?

333
00:15:41,950 --> 00:15:42,780
Vì vậy, 50.

334
00:15:42,780 --> 00:15:44,700
Vì vậy, nó là loại phức tạp hơn thời gian này.

335
00:15:44,700 --> 00:15:47,880
Trong khi đó, thời gian qua nó đã được siêu
dễ dàng chỉ cần làm kích thước trừ một,

336
00:15:47,880 --> 00:15:51,440
Tôi có được đến cuối của mảng của tôi có hiệu quả
nơi những con số, nó loại bỏ 61.

337
00:15:51,440 --> 00:15:52,920
Nhưng tôi không muốn loại bỏ 61.

338
00:15:52,920 --> 00:15:55,030
Tôi muốn lấy 50 người
đã có tại 05:00

339
00:15:55,030 --> 00:15:56,790
xếp hàng cho
iPhone mới hoặc có điều gì.

340
00:15:56,790 --> 00:16:01,200
Và do đó, để thoát khỏi 50, tôi
không thể chỉ làm điều này, phải không?

341
00:16:01,200 --> 00:16:02,547
Tôi có thể vượt ra ngoài 50.

342
00:16:02,547 --> 00:16:04,380
Nhưng chúng ta chỉ nói chúng tôi
không phải quá hậu môn

343
00:16:04,380 --> 00:16:06,330
như để xóa bỏ hoặc ẩn các dữ liệu.

344
00:16:06,330 --> 00:16:08,090
Chúng tôi chỉ có thể quên nó ở đâu.

345
00:16:08,090 --> 00:16:12,330
>> Nhưng nếu tôi thay đổi kích thước của tôi ngay bây giờ để
hai, là đầy đủ thông tin này

346
00:16:12,330 --> 00:16:15,711
để biết những gì đang xảy ra trong hàng đợi của tôi?

347
00:16:15,711 --> 00:16:16,680
Không hẳn.

348
00:16:16,680 --> 00:16:19,830
Giống như kích thước của tôi là hai, nhưng
nơi nào hàng đợi bắt đầu,

349
00:16:19,830 --> 00:16:22,980
đặc biệt là nếu tôi vẫn còn có
những con số tương tự trong bộ nhớ.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Vì vậy, tôi cần phải nhớ
bây giờ mà phía trước là.

352
00:16:27,090 --> 00:16:29,630
Và như vậy, tôi đã đề xuất lên
ở đó, chúng ta sẽ vừa gọi

353
00:16:29,630 --> 00:16:33,729
Nth phía trước, mà ban đầu
giá trị cần phải có được những gì?

354
00:16:33,729 --> 00:16:35,270
Zero, chỉ là khởi đầu của danh sách.

355
00:16:35,270 --> 00:16:40,876
Nhưng bây giờ ngoài việc giảm các chữ
kích thước, chúng tôi chỉ tăng phía trước.

356
00:16:40,876 --> 00:16:42,000
Bây giờ đây là một vấn đề khác.

357
00:16:42,000 --> 00:16:43,030
Vì vậy, một khi tôi tiếp tục đi.

358
00:16:43,030 --> 00:16:47,520
Giả sử đây là số lượng
như 121, 124, và sau đó, mẹ kiếp,

359
00:16:47,520 --> 00:16:48,610
Tôi ra khỏi không gian.

360
00:16:48,610 --> 00:16:50,390
Nhưng chờ một phút, tôi thì không.

361
00:16:50,390 --> 00:16:55,630
Vì vậy, tại thời điểm này trong những câu chuyện,
giả sử rằng kích thước là một, hai,

362
00:16:55,630 --> 00:17:00,370
ba, bốn, vì vậy giả sử rằng
kích thước là bốn, phía trước là một,

363
00:17:00,370 --> 00:17:01,621
vậy 51 là ở phía trước.

364
00:17:01,621 --> 00:17:04,329
Tôi muốn đặt một số khác ở đây,
nhưng, mẹ kiếp, tôi ra khỏi không gian.

365
00:17:04,329 --> 00:17:06,710
Nhưng tôi không thực sự, phải không?

366
00:17:06,710 --> 00:17:11,192
Nơi mà tôi có thể đặt một số
giá trị bổ sung, như 171?

367
00:17:11,192 --> 00:17:13,400
Chỉ Yeah, tôi có thể loại
đi lại ở đó, phải không?

368
00:17:13,400 --> 00:17:18,161
Và sau đó gạch bỏ 50, hoặc
chỉ ghi đè lên nó bằng 171.

369
00:17:18,161 --> 00:17:20,410
Và nếu bạn đang tự hỏi tại sao
số của chúng tôi đã rất ngẫu nhiên,

370
00:17:20,410 --> 00:17:24,150
này thường được lấy máy tính
các khóa học khoa học tại Harvard sau CS50.

371
00:17:24,150 --> 00:17:27,510
Nhưng đó là một tối ưu hóa tốt,
bởi vì bây giờ tôi sẽ không lãng phí thời gian.

372
00:17:27,510 --> 00:17:30,750
Tôi vẫn phải nhớ
lớn làm thế nào điều này là tổng số.

373
00:17:30,750 --> 00:17:31,500
Đó là tổng số năm.

374
00:17:31,500 --> 00:17:33,375
Bởi vì tôi không muốn
bắt đầu ghi đè lên 51.

375
00:17:33,375 --> 00:17:36,260
Vì vậy, bây giờ tôi vẫn ra ngoài không gian,
vì vậy vấn đề tương tự như trước.

376
00:17:36,260 --> 00:17:39,140
Nhưng bạn có thể nhìn thấy thế nào bây giờ
trong mã của bạn, có thể bạn

377
00:17:39,140 --> 00:17:41,910
phải viết nhiều hơn một chút
phức tạp để làm cho điều đó xảy ra.

378
00:17:41,910 --> 00:17:44,510
Và trên thực tế, những gì điều hành
trong C có thể cho phép

379
00:17:44,510 --> 00:17:48,110
bạn kỳ diệu làm điều này tuần hoàn?

380
00:17:48,110 --> 00:17:50,160
Vâng các nhà điều hành modulo,
các ký hiệu phần trăm.

381
00:17:50,160 --> 00:17:53,160
Vì vậy, những gì là loại mát mẻ về một hàng đợi,
mặc dù chúng tôi giữ mảng vẽ

382
00:17:53,160 --> 00:17:56,520
là những đường thẳng như thế, nếu bạn
loại suy nghĩ về điều này như cong

383
00:17:56,520 --> 00:18:00,341
xung quanh như một vòng tròn, sau đó chỉ cần
trực giác nó loại hoạt động tinh thần

384
00:18:00,341 --> 00:18:01,590
Tôi nghĩ rằng một chút sạch hơn.

385
00:18:01,590 --> 00:18:05,190
Bạn vẫn sẽ phải thực hiện
rằng mô hình về tinh thần trong mã.

386
00:18:05,190 --> 00:18:07,550
Vì vậy, không phải là khó,
cuối cùng, để thực hiện,

387
00:18:07,550 --> 00:18:12,430
nhưng chúng tôi vẫn mất size-- đúng hơn,
Khả năng thay đổi kích thước, trừ khi chúng ta làm điều này.

388
00:18:12,430 --> 00:18:15,310
>> Chúng tôi có để thoát khỏi của mảng, chúng tôi
thay thế nó bằng một con trỏ duy nhất,

389
00:18:15,310 --> 00:18:20,010
và sau đó một nơi nào đó trong mã của tôi, tôi đã có
một gọi hàm nào để thực sự tạo ra

390
00:18:20,010 --> 00:18:23,720
các mảng gọi là con số không?

391
00:18:23,720 --> 00:18:26,190
Malloc, hoặc một số tương tự
chức năng, chính xác.

392
00:18:26,190 --> 00:18:30,481
Bất kỳ câu hỏi trên ngăn xếp và hàng đợi.

393
00:18:30,481 --> 00:18:30,980
Yeah?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Câu hỏi hay.

396
00:18:34,240 --> 00:18:35,830
Modulo những gì bạn sẽ sử dụng ở đây.

397
00:18:35,830 --> 00:18:38,520
Vì vậy, nói chung, khi sử dụng
mod, bạn sẽ làm điều đó

398
00:18:38,520 --> 00:18:40,620
với kích thước của
toàn bộ cấu trúc dữ liệu.

399
00:18:40,620 --> 00:18:44,120
Vì vậy, giống như năm hoặc năng lực, nếu
đó là liên tục, có lẽ có liên quan.

400
00:18:44,120 --> 00:18:47,100
Nhưng chỉ cần làm theo modulo năm
có lẽ là không đủ,

401
00:18:47,100 --> 00:18:51,380
bởi vì chúng ta cần phải biết làm chúng tôi
quấn quanh ở đây hoặc ở đây hoặc ở đây.

402
00:18:51,380 --> 00:18:54,160
Vì vậy, có lẽ bạn đang còn
sẽ muốn liên quan

403
00:18:54,160 --> 00:18:57,220
kích thước của điều này, hoặc
biến phía trước là tốt.

404
00:18:57,220 --> 00:19:00,140
Vì vậy, nó chỉ này tương đối
biểu thức số học đơn giản,

405
00:19:00,140 --> 00:19:02,000
nhưng modulo sẽ là thành phần quan trọng.

406
00:19:02,000 --> 00:19:03,330
>> Vì vậy, bộ phim ngắn nếu bạn sẽ.

407
00:19:03,330 --> 00:19:05,780
Một hình ảnh động mà một số
folks tại trường đại học khác

408
00:19:05,780 --> 00:19:08,060
đặt lại với nhau rằng chúng tôi đã
thích nghi cho cuộc thảo luận này.

409
00:19:08,060 --> 00:19:12,630
Nó liên quan đến Jack học
sự thật về hàng đợi và số liệu thống kê.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: Đã có một thời gian,
có một chàng trai tên là Jack.

412
00:19:21,890 --> 00:19:25,330
Khi nó đến để làm cho bạn bè,
Jack đã không có một sở trường riêng.

413
00:19:25,330 --> 00:19:28,220
Vì vậy, Jack đã đến nói chuyện với
chàng trai nổi tiếng nhất mà ông biết.

414
00:19:28,220 --> 00:19:30,920
Ông đến Lou và hỏi, tôi phải làm gì?

415
00:19:30,920 --> 00:19:33,400
Lou đã thấy rằng người bạn của mình
đã thực sự đau khổ.

416
00:19:33,400 --> 00:19:36,050
Vâng, anh bắt đầu, chỉ
nhìn cách ăn mặc nữa.

417
00:19:36,050 --> 00:19:38,680
Bạn không có bất kỳ quần áo
với một cái nhìn khác nhau?

418
00:19:38,680 --> 00:19:39,660
Có, Jack nói.

419
00:19:39,660 --> 00:19:40,840
Tôi chắc chắn làm được.

420
00:19:40,840 --> 00:19:43,320
Đến nhà tôi và
Tôi sẽ cho họ với bạn.

421
00:19:43,320 --> 00:19:44,550
Vì vậy, họ đã đi off để Jack.

422
00:19:44,550 --> 00:19:47,520
Và Jack thấy Lou hộp
nơi ông giữ tất cả áo sơ mi của mình,

423
00:19:47,520 --> 00:19:49,260
và quần của mình, và vớ của mình.

424
00:19:49,260 --> 00:19:52,290
Lou nói, tôi thấy bạn có
tất cả quần áo của bạn trong một đống.

425
00:19:52,290 --> 00:19:54,870
Tại sao bạn không mặc một số
những người khác lần trong một lúc?

426
00:19:54,870 --> 00:19:58,020
>> Jack nói, tốt, khi tôi
loại bỏ quần áo và vớ,

427
00:19:58,020 --> 00:20:00,780
Tôi rửa cho họ và đưa
họ đi vào trong hộp.

428
00:20:00,780 --> 00:20:03,210
Sau đó đến tiếp theo
buổi sáng, và lên Tôi hop.

429
00:20:03,210 --> 00:20:06,380
Tôi đi tới hộp và nhận được
quần áo của tôi ra khỏi đầu.

430
00:20:06,380 --> 00:20:09,070
Lou nhanh chóng nhận ra
các vấn đề với Jack.

431
00:20:09,070 --> 00:20:12,080
Ông giữ quần áo, đĩa CD,
và sách trong ngăn xếp.

432
00:20:12,080 --> 00:20:14,420
Khi anh với
một cái gì đó để đọc hoặc để mặc,

433
00:20:14,420 --> 00:20:17,100
ông muốn chọn cuốn sách đầu hoặc đồ lót.

434
00:20:17,100 --> 00:20:19,500
Sau đó, khi ông đã được thực hiện, ông
sẽ đặt nó trở lại ngay.

435
00:20:19,500 --> 00:20:21,970
Trở lại nó sẽ đi, trên đỉnh của ngăn xếp.

436
00:20:21,970 --> 00:20:24,460
Tôi biết các giải pháp,
nói một Loud chiến thắng.

437
00:20:24,460 --> 00:20:27,090
Bạn cần phải tìm hiểu để
bắt đầu sử dụng một hàng đợi.

438
00:20:27,090 --> 00:20:29,870
Lou lấy quần áo của Jack và
treo chúng trong tủ quần áo.

439
00:20:29,870 --> 00:20:32,710
Và khi ông đã làm trống
hộp, anh chỉ ném nó.

440
00:20:32,710 --> 00:20:36,500
>> Sau đó, ông nói, bây giờ Jack, vào cuối
ngày, mặc quần áo của bạn bên trái

441
00:20:36,500 --> 00:20:37,990
khi bạn đưa chúng đi.

442
00:20:37,990 --> 00:20:41,300
Sau đó vào ngày mai buổi sáng khi bạn
nhìn thấy ánh nắng mặt trời, lấy quần áo của bạn

443
00:20:41,300 --> 00:20:43,440
bên phải, từ cuối dòng.

444
00:20:43,440 --> 00:20:44,880
Anh không thấy? Lou nói.

445
00:20:44,880 --> 00:20:46,370
Nó sẽ được tốt đẹp như vậy.

446
00:20:46,370 --> 00:20:49,770
Bạn sẽ mặc tất cả mọi thứ một lần
trước khi bạn mặc một cái gì đó hai lần.

447
00:20:49,770 --> 00:20:52,670
Và với tất cả mọi thứ trong hàng đợi
trong tủ quần áo và kệ của mình,

448
00:20:52,670 --> 00:20:55,160
Jack bắt đầu cảm thấy
khá chắc chắn của mình.

449
00:20:55,160 --> 00:20:59,720
Tất cả là nhờ Lou và
hàng đợi tuyệt vời của mình.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Đúng rồi, đó là đáng yêu.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Vì vậy, những gì đã được thực sự đi
trên dưới mui xe bây giờ?

453
00:21:10,080 --> 00:21:12,370
Rằng chúng ta có con trỏ,
rằng chúng ta có malloc,

454
00:21:12,370 --> 00:21:15,680
rằng chúng ta có khả năng để tạo ra
khối của bộ nhớ cho mình

455
00:21:15,680 --> 00:21:16,344
động.

456
00:21:16,344 --> 00:21:18,510
Vì vậy, đây là một hình ảnh chúng tôi
thoáng thấy chỉ một ngày khác.

457
00:21:18,510 --> 00:21:21,180
Chúng tôi đã không thực sự sống
trên đó, nhưng hình ảnh này

458
00:21:21,180 --> 00:21:24,180
có được đi vào bên dưới
mui xe cho tuần nay.

459
00:21:24,180 --> 00:21:27,050
Và do đó, điều này thể hiện, chỉ
một hình chữ nhật mà chúng tôi đã rút ra,

460
00:21:27,050 --> 00:21:28,180
bộ nhớ máy tính của bạn.

461
00:21:28,180 --> 00:21:31,850
Và có thể máy tính của bạn, hoặc CS50
ID, có một gigabyte bộ nhớ hoặc bộ nhớ RAM

462
00:21:31,850 --> 00:21:33,050
hoặc hai hoặc bốn gigabyte.

463
00:21:33,050 --> 00:21:34,450
Nó không thực sự quan trọng.

464
00:21:34,450 --> 00:21:37,240
Hệ thống điều hành của bạn
Windows hoặc Mac OS hay Linux,

465
00:21:37,240 --> 00:21:41,120
về cơ bản cho phép chương trình của bạn
để nghĩ rằng nó đã truy cập

466
00:21:41,120 --> 00:21:42,982
đến tính toàn vẹn của
bộ nhớ của máy tính,

467
00:21:42,982 --> 00:21:45,440
mặc dù bạn có thể chạy
nhiều chương trình cùng một lúc.

468
00:21:45,440 --> 00:21:46,990
Vì vậy, trong thực tế, điều đó không thực sự làm việc.

469
00:21:46,990 --> 00:21:49,448
Nhưng đó là loại một ảo tưởng
cho tất cả các chương trình của bạn.

470
00:21:49,448 --> 00:21:53,110
Vì vậy, nếu bạn đã có hai hợp đồng biểu diễn của RAM, điều này
là làm thế nào các máy tính có thể nghĩ về nó.

471
00:21:53,110 --> 00:21:57,110
>> Bây giờ tình cờ, một trong những
điều, một trong những phân đoạn của bộ nhớ,

472
00:21:57,110 --> 00:21:58,350
được gọi là một chồng.

473
00:21:58,350 --> 00:22:01,680
Và thực sự bất cứ lúc nào
vậy, đến nay trong văn bản mã

474
00:22:01,680 --> 00:22:05,900
mà bạn đã gọi là một
chức năng, ví dụ chính.

475
00:22:05,900 --> 00:22:08,410
Nhớ lại rằng bất cứ lúc nào tôi đã
bộ nhớ rút máy tính,

476
00:22:08,410 --> 00:22:10,640
Tôi luôn vẽ loại
một nửa của một hình chữ nhật ở đây

477
00:22:10,640 --> 00:22:12,520
và không bận tâm nói
về những gì ở trên.

478
00:22:12,520 --> 00:22:15,980
Bởi vì khi chính được gọi là, tôi yêu cầu bồi thường
mà bạn có được mảnh bộ nhớ này

479
00:22:15,980 --> 00:22:16,970
mà đi xuống đây.

480
00:22:16,970 --> 00:22:20,650
Và nếu chính được gọi là một chức năng
như hoán đổi, cũng trao đổi tại đây.

481
00:22:20,650 --> 00:22:23,720
Và hóa ra, đó là
nơi nó kết thúc.

482
00:22:23,720 --> 00:22:26,277
Trên một cái gì đó gọi là một chồng
bên trong bộ nhớ của máy tính.

483
00:22:26,277 --> 00:22:28,360
Bây giờ vào cuối ngày,
đây chỉ là địa chỉ.

484
00:22:28,360 --> 00:22:30,680
Nó giống như byte zero,
byte một, byte 2 tỷ USD.

485
00:22:30,680 --> 00:22:33,130
Nhưng nếu bạn nghĩ về nó
như đối tượng hình chữ nhật này,

486
00:22:33,130 --> 00:22:35,130
tất cả chúng ta đang làm hàng
Hiện chúng tôi gọi một chức năng là

487
00:22:35,130 --> 00:22:37,180
layering một lát mới của bộ nhớ.

488
00:22:37,180 --> 00:22:41,700
Chúng tôi đem lại cho chức năng đó một lát
bộ nhớ riêng của mình để làm việc với.

489
00:22:41,700 --> 00:22:44,490
>> Và bây giờ mà nhớ lại này là rất quan trọng.

490
00:22:44,490 --> 00:22:46,400
Bởi vì nếu chúng ta có
một cái gì đó như hoán đổi

491
00:22:46,400 --> 00:22:51,610
và hai biến số địa phương như A và B và
chúng ta thay đổi những giá trị từ một đến hai

492
00:22:51,610 --> 00:22:55,130
hai và một, thu hồi
rằng khi hoán đổi trả,

493
00:22:55,130 --> 00:22:58,330
nó giống như miếng này
bộ nhớ chỉ được đi.

494
00:22:58,330 --> 00:23:00,080
Trong thực tế, nó vẫn còn
có forensically.

495
00:23:00,080 --> 00:23:01,940
Và có điều gì đó vẫn thực sự ở đó.

496
00:23:01,940 --> 00:23:05,410
Nhưng khái niệm, nó như là
mặc dù nó hoàn toàn biến mất.

497
00:23:05,410 --> 00:23:10,910
Và như vậy chính không biết bất kỳ công việc
đã được thực hiện trong đó chức năng trao đổi,

498
00:23:10,910 --> 00:23:14,890
trừ khi nó thực sự được thông qua trong những
lập luận của con trỏ hoặc tham chiếu.

499
00:23:14,890 --> 00:23:17,790
Bây giờ, các giải pháp cơ bản
cho rằng vấn đề với swap

500
00:23:17,790 --> 00:23:19,970
là đi qua những điều trong theo địa chỉ.

501
00:23:19,970 --> 00:23:23,250
Nhưng hóa ra, quá, có chuyện gì
được diễn ra trên phần đó

502
00:23:23,250 --> 00:23:26,330
của hình chữ nhật tất cả các thời gian này là
chưa có nhiều bộ nhớ lên ở đó.

503
00:23:26,330 --> 00:23:28,790
Và khi bạn tự động
cấp phát bộ nhớ,

504
00:23:28,790 --> 00:23:32,020
cho dù đó là bên trong của GetString, mà
chúng tôi đã làm cho bạn trong CS50

505
00:23:32,020 --> 00:23:34,710
thư viện, hoặc nếu các bạn
gọi malloc và yêu cầu

506
00:23:34,710 --> 00:23:37,950
hệ điều hành cho một đoạn
bộ nhớ, nó không đến từ stack.

507
00:23:37,950 --> 00:23:40,960
Nó đến từ một nơi khác
trong bộ nhớ máy tính của bạn

508
00:23:40,960 --> 00:23:42,220
đó được gọi là heap.

509
00:23:42,220 --> 00:23:43,430
Và đó không phải là bất kỳ khác nhau.

510
00:23:43,430 --> 00:23:44,285
Đó là bộ nhớ RAM cùng.

511
00:23:44,285 --> 00:23:45,160
Đó là cùng một bộ nhớ.

512
00:23:45,160 --> 00:23:49,080
Nó chỉ là RAM đó là lên
có thay vì xuống đây.

513
00:23:49,080 --> 00:23:50,750
>> Và như vậy có nghĩa là gì?

514
00:23:50,750 --> 00:23:53,650
Vâng, nếu máy tính của bạn có
một số lượng hữu hạn của bộ nhớ

515
00:23:53,650 --> 00:23:57,450
và ngăn xếp được ngày càng tăng lên, vì vậy
để nói chuyện, và heap, theo

516
00:23:57,450 --> 00:23:59,349
vào mũi tên này, đang phát triển xuống.

517
00:23:59,349 --> 00:24:01,140
Nói cách khác, mỗi
thời gian bạn gọi malloc,

518
00:24:01,140 --> 00:24:03,430
bạn đang được đưa ra một lát
bộ nhớ từ trên cao,

519
00:24:03,430 --> 00:24:06,630
sau đó có thể là một ít thấp, sau đó một chút
thấp hơn, mỗi lần bạn gọi malloc,

520
00:24:06,630 --> 00:24:10,100
heap, nó sử dụng,
là loại ngày càng tăng,

521
00:24:10,100 --> 00:24:11,950
phát triển gần gũi hơn và gần gũi hơn với những gì?

522
00:24:11,950 --> 00:24:13,382
Stack.

523
00:24:13,382 --> 00:24:14,840
Vì vậy, điều này có vẻ như là một ý tưởng tốt?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Tôi có nghĩa là, nơi mà nó không thực sự rõ ràng
những gì khác bạn có thể làm gì nếu bạn chỉ

526
00:24:22,140 --> 00:24:23,910
có một số lượng hữu hạn của bộ nhớ.

527
00:24:23,910 --> 00:24:25,200
Nhưng điều này chắc chắn là xấu.

528
00:24:25,200 --> 00:24:27,920
Hai mũi tên ở một
sụp đổ nhiên cho nhau.

529
00:24:27,920 --> 00:24:31,930
>> Và nó chỉ ra rằng kẻ xấu, folks người
đặc biệt tốt với các chương trình,

530
00:24:31,930 --> 00:24:36,140
và cố gắng để hack vào máy tính,
có thể khai thác thực tế này.

531
00:24:36,140 --> 00:24:38,290
Trong thực tế, chúng ta hãy xem xét
một ít đoạn trích.

532
00:24:38,290 --> 00:24:41,350
Vì vậy, đây là một ví dụ bạn có thể đọc
về chi tiết hơn trên Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Chúng tôi sẽ chỉ cho bạn tại
bài viết nếu tò mò.

534
00:24:43,100 --> 00:24:45,650
Nhưng có một cuộc tấn công nói chung
được gọi là tràn bộ đệm

535
00:24:45,650 --> 00:24:49,570
đã tồn tại cho tới chừng con người
có khả năng thao tác

536
00:24:49,570 --> 00:24:53,120
bộ nhớ của máy tính, đặc biệt là trong C.
Vì vậy, đây là một chương trình rất tuỳ tiện,

537
00:24:53,120 --> 00:24:55,130
nhưng chúng ta hãy đọc nó từ dưới lên.

538
00:24:55,130 --> 00:24:57,650
Chính vào argc char sao argv.

539
00:24:57,650 --> 00:24:59,830
Vì vậy, nó là một chương trình mà mất
đối số dòng lệnh.

540
00:24:59,830 --> 00:25:03,620
Và tất cả các chính không rõ ràng là cuộc gọi
một chức năng, gọi nó là F cho đơn giản.

541
00:25:03,620 --> 00:25:04,610
Và nó đi trong những gì?

542
00:25:04,610 --> 00:25:05,490
Argv của một.

543
00:25:05,490 --> 00:25:09,320
Vì vậy, nó đi vào bất cứ điều gì F
từ đó mà người dùng gõ

544
00:25:09,320 --> 00:25:11,500
tại dấu nhắc sau khi
Tên của chương trình ở tất cả.

545
00:25:11,500 --> 00:25:15,730
Vì vậy, nhiều như Caesar hoặc Vigenere, mà
bạn có thể gọi lại làm với argv.

546
00:25:15,730 --> 00:25:16,680
>> Vì vậy, F là gì?

547
00:25:16,680 --> 00:25:19,760
F mất trong một chuỗi
là đại diện duy nhất của nó,

548
00:25:19,760 --> 00:25:22,100
AKA một ngôi sao char, cùng
điều, như một chuỗi.

549
00:25:22,100 --> 00:25:24,920
Và nó được gọi là tùy tiện
thanh trong ví dụ này.

550
00:25:24,920 --> 00:25:27,710
Và sau đó char c 12,
chỉ trong điều khoản của layman,

551
00:25:27,710 --> 00:25:31,750
char khung c 12 làm cho chúng ta là gì?

552
00:25:31,750 --> 00:25:33,440
Của nó làm những gì?

553
00:25:33,440 --> 00:25:36,490
Phân bổ bộ nhớ, đặc biệt
12 byte cho 12 ký tự.

554
00:25:36,490 --> 00:25:36,990
Chính xác.

555
00:25:36,990 --> 00:25:40,000
Và sau đó dòng cuối cùng, khuấy đều và
copy, bạn đã có thể không nhìn thấy.

556
00:25:40,000 --> 00:25:43,360
Đây là một bản sao chuỗi
chức năng, mục đích trong cuộc sống

557
00:25:43,360 --> 00:25:48,160
là sao chép đối số thứ hai của mình
thành số đầu tiên của mình,

558
00:25:48,160 --> 00:25:51,190
nhưng chỉ lên đến một
số lượng nhất định các byte.

559
00:25:51,190 --> 00:25:53,860
Vì vậy, đối số thứ ba nói,
có bao nhiêu byte bạn nên sao chép?

560
00:25:53,860 --> 00:25:56,720
Chiều dài của thanh,
bất cứ điều gì người dùng gõ vào.

561
00:25:56,720 --> 00:25:59,320
Và nội dung của
bar, chuỗi, là

562
00:25:59,320 --> 00:26:02,330
sao chép vào bộ nhớ chỉ ở tại C.

563
00:26:02,330 --> 00:26:04,060
>> Vì vậy, điều này có vẻ ngu ngốc, và nó được.

564
00:26:04,060 --> 00:26:06,300
Đó là một ví dụ tạo,
nhưng nó đại diện

565
00:26:06,300 --> 00:26:10,100
của một lớp học của vectơ tấn công,
một cách tấn công của một chương trình.

566
00:26:10,100 --> 00:26:15,050
Tất cả là tốt và tốt nếu người dùng
loại trong một từ đó là 11 ký tự

567
00:26:15,050 --> 00:26:18,040
hoặc ít hơn, cộng với dấu gạch chéo ngược zero.

568
00:26:18,040 --> 00:26:22,830
Điều gì nếu người dùng đánh vào hơn
11 hoặc 12, 20 hoặc 50 ký tự?

569
00:26:22,830 --> 00:26:25,090
Chương trình này sẽ làm những gì?

570
00:26:25,090 --> 00:26:29,360
Lỗi có khả năng seg. Nó sẽ
một cách mù quáng sao chép tất cả mọi thứ trong quán bar lên

571
00:26:29,360 --> 00:26:31,750
theo chiều dài của nó, đó là
nghĩa là tất cả mọi thứ trong quán bar,

572
00:26:31,750 --> 00:26:36,307
vào địa chỉ được trỏ C. Nhưng C
đã chỉ đánh phủ đưa ra là 12 byte.

573
00:26:36,307 --> 00:26:37,640
Nhưng không có kiểm tra bổ sung.

574
00:26:37,640 --> 00:26:38,700
Không có nếu điều kiện.

575
00:26:38,700 --> 00:26:40,580
Không có kiểm tra lỗi ở đây.

576
00:26:40,580 --> 00:26:43,270
>> Và vì vậy những gì chương trình này là
sẽ làm là chỉ mù quáng

577
00:26:43,270 --> 00:26:45,750
sao chép một điều khác.

578
00:26:45,750 --> 00:26:47,880
Và như vậy, nếu chúng ta vẽ này
như một bức tranh, đây là

579
00:26:47,880 --> 00:26:49,860
chỉ là một mảnh của không gian bộ nhớ.

580
00:26:49,860 --> 00:26:53,470
Vì vậy, nhận thấy ở phía dưới, chúng tôi
có thanh địa phương biến.

581
00:26:53,470 --> 00:26:57,330
Vì vậy mà con trỏ đó là sẽ store--
đúng hơn là lập luận địa phương đó là

582
00:26:57,330 --> 00:26:58,672
sẽ lưu thanh chuỗi.

583
00:26:58,672 --> 00:27:00,380
Và sau đó thông báo chỉ
ở trên nó trong một ngăn xếp,

584
00:27:00,380 --> 00:27:02,505
bởi vì mỗi khi bạn hỏi
cho bộ nhớ trên stack,

585
00:27:02,505 --> 00:27:04,310
nó đi một chút
ở trên nó trong những bức tranh,

586
00:27:04,310 --> 00:27:06,270
thông báo rằng chúng tôi đã có 12 byte có.

587
00:27:06,270 --> 00:27:10,690
Người đầu bên trái là khung C bằng không và
người dưới bên phải là khung C 11.

588
00:27:10,690 --> 00:27:12,870
Đó chỉ là cách các máy tính
sẽ lay nó ra.

589
00:27:12,870 --> 00:27:18,300
Vì vậy, chỉ bằng trực giác, nếu thanh có hơn
hơn 12 ký tự trong tổng số, bao gồm cả

590
00:27:18,300 --> 00:27:25,790
các dấu gạch chéo ngược bằng không, mà là
12 hoặc 12 khung C sẽ đi đâu?

591
00:27:25,790 --> 00:27:28,440
Hay đúng hơn, nơi là 12
nhân vật hoặc nhân vật thứ 13,

592
00:27:28,440 --> 00:27:30,900
các nhân vật trăm đi
để kết thúc trong hình ảnh?

593
00:27:30,900 --> 00:27:33,400
Trên hay dưới?

594
00:27:33,400 --> 00:27:36,300
>> Đúng, bởi vì mặc dù
stack tự mọc lên,

595
00:27:36,300 --> 00:27:39,590
một khi bạn đã đưa công cụ trong
nó, nó cho lý do thiết kế,

596
00:27:39,590 --> 00:27:41,294
đặt vào bộ nhớ từ trên xuống dưới.

597
00:27:41,294 --> 00:27:44,460
Vì vậy, nếu bạn đã có hơn 12 byte,
bạn sẽ bắt đầu ghi đè lên vạch.

598
00:27:44,460 --> 00:27:47,280
Bây giờ đó là một lỗi, nhưng nó
không thực sự là một vấn đề lớn.

599
00:27:47,280 --> 00:27:51,130
Nhưng nó là một vấn đề lớn, bởi vì có
nhiều thứ đang diễn ra trong bộ nhớ.

600
00:27:51,130 --> 00:27:53,074
Vì vậy, đây là cách chúng ta có thể
đặt hello, để được rõ ràng.

601
00:27:53,074 --> 00:27:54,490
Nếu tôi gõ trong hello tại dấu nhắc.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash không, kết thúc trong vòng
những 12 byte, và chúng tôi siêu an toàn.

603
00:27:59,330 --> 00:28:00,330
Tất cả đều tốt.

604
00:28:00,330 --> 00:28:03,020
Nhưng nếu tôi gõ một cái gì đó
dài hơn, có khả năng nó

605
00:28:03,020 --> 00:28:05,860
sẽ chui vào không gian bar.

606
00:28:05,860 --> 00:28:08,405
Nhưng tệ hơn, nó quay
ra tất cả các thời gian này,

607
00:28:08,405 --> 00:28:11,530
mặc dù chúng tôi đã không bao giờ nói chuyện về
nó, ngăn xếp được sử dụng cho các công cụ khác.

608
00:28:11,530 --> 00:28:13,560
Nó không chỉ là biến địa phương.

609
00:28:13,560 --> 00:28:15,100
>> C là một ngôn ngữ cấp rất thấp.

610
00:28:15,100 --> 00:28:17,810
Và nó loại bí mật
sử dụng stack cũng

611
00:28:17,810 --> 00:28:21,260
cần nhớ khi một
hàm được gọi, những gì

612
00:28:21,260 --> 00:28:26,040
địa chỉ là các chức năng trước đây,
do đó, nó có thể nhảy trở lại chức năng đó.

613
00:28:26,040 --> 00:28:29,980
Vì vậy, khi các cuộc gọi chính trao đổi, trong số
những điều đẩy vào stack

614
00:28:29,980 --> 00:28:34,380
không chỉ hoán đổi biến địa phương,
hoặc đối số của nó, cũng bí mật đẩy

615
00:28:34,380 --> 00:28:37,510
vào stack như là đại diện
bởi các miếng màu đỏ ở đây,

616
00:28:37,510 --> 00:28:40,520
là địa chỉ của chính thể chất
trong bộ nhớ của máy tính,

617
00:28:40,520 --> 00:28:44,180
để khi trao đổi được thực hiện, máy tính
biết tôi cần phải quay trở lại chính

618
00:28:44,180 --> 00:28:46,760
và kết thúc thực hiện các chức năng chính.

619
00:28:46,760 --> 00:28:51,960
Vì vậy, đây là nguy hiểm bây giờ, bởi vì nếu
sử dụng các loại trong tốt hơn hello,

620
00:28:51,960 --> 00:28:57,030
như vậy mà đầu vào của người dùng clobbers
hoặc ghi đè lên rằng phần màu đỏ,

621
00:28:57,030 --> 00:28:59,820
một cách hợp lý nếu máy tính
chỉ cần đi một cách mù quáng giả

622
00:28:59,820 --> 00:29:03,830
các byte trong đó lát đỏ
địa chỉ mà nó phải trả lại,

623
00:29:03,830 --> 00:29:09,020
nếu các đối thủ là những gì đủ thông minh hoặc
may mắn, đủ để đặt một chuỗi các byte

624
00:29:09,020 --> 00:29:13,450
có mà trông giống như một địa chỉ,
nhưng đó là địa chỉ của mã

625
00:29:13,450 --> 00:29:18,730
rằng anh ta muốn máy tính
để thực hiện thay vì chính?

626
00:29:18,730 --> 00:29:21,670
>> Nói cách khác, nếu những gì
dùng đang gõ tại dấu nhắc,

627
00:29:21,670 --> 00:29:23,850
không phải là một cái gì đó chỉ
như vô thưởng vô phạt hello,

628
00:29:23,850 --> 00:29:28,210
nhưng nó thực sự là mã đó là tương đương
để xóa tất cả các tập tin của người dùng này?

629
00:29:28,210 --> 00:29:30,060
Hoặc gửi email mật khẩu của họ với tôi?

630
00:29:30,060 --> 00:29:31,940
Hoặc bắt đầu đăng nhập của họ
tổ hợp phím, phải không?

631
00:29:31,940 --> 00:29:34,920
Có một con đường, chúng ta hãy định ngày hôm nay,
rằng họ có thể gõ vào không chỉ chào

632
00:29:34,920 --> 00:29:36,711
thế giới hoặc tên của họ,
họ có thể cơ bản

633
00:29:36,711 --> 00:29:39,570
vượt qua trong mã, số không và
những người thân, rằng máy tính

634
00:29:39,570 --> 00:29:43,450
sai lầm cho cả mã và địa chỉ.

635
00:29:43,450 --> 00:29:48,950
Vì vậy, mặc dù hơi trừu tượng, nếu
loại dùng trong đủ mã đối địch

636
00:29:48,950 --> 00:29:52,330
rằng chúng tôi sẽ khái quát ở đây là
A. A là tấn công hay kẻ thù.

637
00:29:52,330 --> 00:29:53,140
Vì vậy, những thứ chỉ có hại.

638
00:29:53,140 --> 00:29:55,306
Chúng tôi không quan tâm về
số hoặc các số không hoặc những người thân

639
00:29:55,306 --> 00:29:59,470
ngày hôm nay, như vậy mà bạn kết thúc
ghi đè lên rằng phần màu đỏ,

640
00:29:59,470 --> 00:30:01,580
nhận thấy rằng chuỗi các byte.

641
00:30:01,580 --> 00:30:05,020
O 835 C không tám không.

642
00:30:05,020 --> 00:30:08,960
Và bây giờ là bài viết của Wikipedia đây
đã đề xuất, nếu bây giờ bạn thực sự bắt đầu

643
00:30:08,960 --> 00:30:12,460
ghi nhãn các byte trong máy tính của bạn
bộ nhớ, những gì các bài viết Wikipedia là

644
00:30:12,460 --> 00:30:19,060
đề xuất là, những gì nếu địa chỉ
trong đó byte trên bên trái là 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Nói cách khác, nếu các chàng xấu là
đủ thông minh với mã của mình

646
00:30:22,200 --> 00:30:26,650
để thực sự đưa một số ở đây mà
tương ứng với địa chỉ của mã

647
00:30:26,650 --> 00:30:29,180
anh ta hoặc cô tiêm
vào máy tính, bạn

648
00:30:29,180 --> 00:30:31,050
có thể lừa máy tính
vào làm gì.

649
00:30:31,050 --> 00:30:34,140
Loại bỏ các tập tin, gửi email
điều, sniffing truy cập của bạn,

650
00:30:34,140 --> 00:30:36,710
nghĩa là bất cứ điều gì có thể là
tiêm vào máy tính.

651
00:30:36,710 --> 00:30:39,220
Và do đó, một lỗi tràn bộ đệm
tấn công vào cốt lõi của nó

652
00:30:39,220 --> 00:30:43,530
chỉ là một ngu ngốc, ngu ngốc
trọng của một mảng

653
00:30:43,530 --> 00:30:45,840
không có ranh giới của nó kiểm tra.

654
00:30:45,840 --> 00:30:48,850
Và đây là những gì là siêu nguy hiểm
và đồng thời siêu mạnh

655
00:30:48,850 --> 00:30:52,560
trong C là chúng ta thực sự có
truy cập vào bất cứ nơi nào trong bộ nhớ.

656
00:30:52,560 --> 00:30:55,320
Nó đến với chúng tôi, các lập trình viên,
người viết mã ban đầu

657
00:30:55,320 --> 00:30:59,330
để kiểm tra độ dài của bất kỳ darn
mảng mà chúng ta đang thao tác.

658
00:30:59,330 --> 00:31:00,750
Vì vậy, để được rõ ràng, việc sửa chữa là gì?

659
00:31:00,750 --> 00:31:03,190
Nếu chúng ta trở lại này
mã, tôi không nên chỉ

660
00:31:03,190 --> 00:31:08,000
thay đổi chiều dài của thanh, những gì
khác tôi cần được kiểm tra?

661
00:31:08,000 --> 00:31:10,620
Còn gì nên làm để
ngăn chặn cuộc tấn công này hoàn toàn?

662
00:31:10,620 --> 00:31:14,110
Tôi không muốn chỉ là một cách mù quáng nói
mà bạn nên sao chép như nhiều byte

663
00:31:14,110 --> 00:31:16,140
như là chiều dài của thanh.

664
00:31:16,140 --> 00:31:18,910
Tôi muốn nói, sao chép như
nhiều byte như là trong quán bar

665
00:31:18,910 --> 00:31:24,090
đến phân bổ
bộ nhớ, hoặc 12 tối đa.

666
00:31:24,090 --> 00:31:27,450
Vì vậy, tôi cần một số loại nếu điều kiện
mà không kiểm tra độ dài của thanh,

667
00:31:27,450 --> 00:31:32,800
nhưng nếu nó vượt quá 12, chúng tôi chỉ cứng mã
12 là khoảng cách tối đa có thể.

668
00:31:32,800 --> 00:31:35,910
Nếu không cái gọi là bộ đệm
tấn công tràn bộ có thể xảy ra.

669
00:31:35,910 --> 00:31:38,451
Ở dưới cùng của những slide,
nếu bạn đang tò mò muốn đọc thêm

670
00:31:38,451 --> 00:31:41,200
là bài viết thực tế ban đầu
nếu bạn muốn có một cái nhìn.

671
00:31:41,200 --> 00:31:44,550
>> Nhưng bây giờ, trong số các giá
trả ở đây là không hiệu quả.

672
00:31:44,550 --> 00:31:46,680
Vì vậy, đó là một cách nhanh chóng
cấp thấp này những gì

673
00:31:46,680 --> 00:31:49,709
vấn đề có thể phát sinh bây giờ chúng tôi rằng
có quyền truy cập vào bộ nhớ của máy tính.

674
00:31:49,709 --> 00:31:51,750
Nhưng một vấn đề khác chúng tôi
đã vấp vào thứ Hai

675
00:31:51,750 --> 00:31:53,800
chỉ là không hiệu quả
của một danh sách liên kết.

676
00:31:53,800 --> 00:31:56,019
Chúng tôi đang trở lại với thời gian tuyến tính.

677
00:31:56,019 --> 00:31:57,560
Chúng tôi không còn có một mảng kề nhau.

678
00:31:57,560 --> 00:31:58,980
Chúng tôi không có quyền truy cập ngẫu nhiên.

679
00:31:58,980 --> 00:32:00,710
Chúng tôi không thể sử dụng ký hiệu khung vuông.

680
00:32:00,710 --> 00:32:04,590
Chúng tôi theo nghĩa đen có sử dụng một vòng lặp trong khi
như một trong tôi đã viết một thời gian trước đây.

681
00:32:04,590 --> 00:32:09,740
Nhưng vào thứ hai, chúng tôi cho rằng chúng ta có thể
leo trở lại vào lĩnh vực hiệu quả

682
00:32:09,740 --> 00:32:13,040
đạt được một cái gì đó
logarit có thể, hoặc tốt nhất chưa,

683
00:32:13,040 --> 00:32:16,120
thậm chí có một cái gì đó
cái gọi là thời gian liên tục.

684
00:32:16,120 --> 00:32:19,840
Vậy làm thế nào chúng ta có thể làm điều đó bằng cách sử dụng các mới
công cụ, những địa chỉ này, các con trỏ,

685
00:32:19,840 --> 00:32:22,210
và luồng điều của riêng của chúng tôi?

686
00:32:22,210 --> 00:32:23,960
Vâng, giả sử rằng
ở đây, đây là một bó

687
00:32:23,960 --> 00:32:27,170
các con số mà chúng ta muốn lưu trữ trong một
cấu trúc dữ liệu và tìm kiếm hiệu quả.

688
00:32:27,170 --> 00:32:30,960
Chúng tôi hoàn toàn có thể tua tới tuần
hai, ném chúng vào một mảng,

689
00:32:30,960 --> 00:32:33,150
và tìm kiếm chúng bằng cách sử dụng tìm kiếm nhị phân.

690
00:32:33,150 --> 00:32:34,040
Chia và chinh phục.

691
00:32:34,040 --> 00:32:37,720
Và trên thực tế bạn đã viết
tìm kiếm nhị phân trong PSET3,

692
00:32:37,720 --> 00:32:40,100
nơi bạn thực hiện các chương trình find.

693
00:32:40,100 --> 00:32:40,890
Nhưng bạn có biết những gì.

694
00:32:40,890 --> 00:32:45,060
Có một loại hơn
cách thông minh để làm điều này.

695
00:32:45,060 --> 00:32:47,390
Đó là nhiều hơn một chút
tinh vi và nó có lẽ

696
00:32:47,390 --> 00:32:50,830
cho phép chúng ta thấy tại sao nhị phân
tìm kiếm là nhanh hơn rất nhiều.

697
00:32:50,830 --> 00:32:52,980
Đầu tiên, chúng ta hãy giới thiệu
khái niệm về một cái cây.

698
00:32:52,980 --> 00:32:54,730
Mà mặc dù trong
cây thực tế loại

699
00:32:54,730 --> 00:32:57,730
phát triển như thế này, trong thế giới của máy tính
khoa học họ loại được kéo dài

700
00:32:57,730 --> 00:33:00,830
giống như một cây gia đình, nơi bạn có
ông bà của bạn hoặc ông bà lớn

701
00:33:00,830 --> 00:33:04,580
hoặc không có điều gì ở phía trên cùng, tộc trưởng và
các matriarch của gia đình, chỉ cần một

702
00:33:04,580 --> 00:33:07,930
cái gọi là gốc, nút, bên dưới
mà là con của nó,

703
00:33:07,930 --> 00:33:11,442
dưới đây là con của nó, hoặc
con cháu của nó nói chung.

704
00:33:11,442 --> 00:33:13,400
Và bất cứ ai treo tắt
dưới cùng của gia đình

705
00:33:13,400 --> 00:33:16,070
cây, bên cạnh là các
út trong gia đình,

706
00:33:16,070 --> 00:33:19,520
cũng có thể chỉ là khái quát
gọi là lá của cây.

707
00:33:19,520 --> 00:33:21,800
>> Vì vậy, đây chỉ là một bó
của từ và định nghĩa

708
00:33:21,800 --> 00:33:25,790
cho một cái gì đó gọi là cây trong máy tính
khoa học, giống như một cây gia đình.

709
00:33:25,790 --> 00:33:28,770
Nhưng có thân fancier
của cây, một trong số đó

710
00:33:28,770 --> 00:33:30,780
được gọi là một cây tìm kiếm nhị phân.

711
00:33:30,780 --> 00:33:34,380
Và bạn có thể loại tease
ngoài những điều này không có gì.

712
00:33:34,380 --> 00:33:37,180
Vâng, đó là nhị phân trong ý nghĩa gì?

713
00:33:37,180 --> 00:33:41,455
Trường hợp không nhị phân đến từ đây?

714
00:33:41,455 --> 00:33:41,955
Xin lỗi?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Nó không quá nhiều một trong hai hoặc.

717
00:33:47,210 --> 00:33:52,000
Đó là chi tiết mà mỗi nút có không
hơn hai đứa con, như chúng ta thấy ở đây.

718
00:33:52,000 --> 00:33:54,990
Nói chung, một tree-- và
cha mẹ và ông bà của bạn

719
00:33:54,990 --> 00:33:57,640
có thể có nhiều trẻ em hoặc
cháu khi họ thực sự muốn,

720
00:33:57,640 --> 00:34:00,820
và do đó, ví dụ chúng tôi đã có ba
trẻ em ra rằng nút tay phải,

721
00:34:00,820 --> 00:34:05,480
nhưng trong một cây nhị phân, một nút có
bằng không, một, hoặc hai con tối đa.

722
00:34:05,480 --> 00:34:08,496
Và đó là một tài sản tốt đẹp,
bởi vì nếu nó bị chặn bởi hai,

723
00:34:08,496 --> 00:34:10,620
chúng ta sẽ có thể
có được một cơ sở đăng nhập ít hai

724
00:34:10,620 --> 00:34:11,975
hành động xảy ra ở đây cuối cùng.

725
00:34:11,975 --> 00:34:13,350
Vì vậy, chúng tôi có một cái gì đó logarit.

726
00:34:13,350 --> 00:34:14,558
Nhưng thêm vào đó trong một thời điểm.

727
00:34:14,558 --> 00:34:19,810
Cây tìm kiếm có nghĩa là những con số
sắp xếp như là con trái của

728
00:34:19,810 --> 00:34:22,429
giá trị lớn hơn căn.

729
00:34:22,429 --> 00:34:26,010
Và con phải của nó là
lớn hơn so với gốc.

730
00:34:26,010 --> 00:34:29,290
Nói cách khác, nếu bạn có bất kỳ của
các nút, các vòng tròn trong ảnh này,

731
00:34:29,290 --> 00:34:31,840
và nhìn vào bên trái của nó
con và con phải của nó,

732
00:34:31,840 --> 00:34:34,739
đầu tiên nên được ít hơn,
thứ hai phải lớn hơn.

733
00:34:34,739 --> 00:34:36,159
Vì vậy, sự tỉnh táo kiểm tra 55.

734
00:34:36,159 --> 00:34:37,780
Nó còn con là 33.

735
00:34:37,780 --> 00:34:38,620
Nó ít hơn.

736
00:34:38,620 --> 00:34:40,929
55 tuổi, con phải của nó là 77.

737
00:34:40,929 --> 00:34:41,783
Nó lớn hơn.

738
00:34:41,783 --> 00:34:43,199
Và đó là một định nghĩa đệ quy.

739
00:34:43,199 --> 00:34:46,480
Chúng tôi có thể kiểm tra mỗi một trong những
các nút và các mô hình tương tự sẽ giữ.

740
00:34:46,480 --> 00:34:49,389
>> Vì vậy, những gì tốt đẹp trong một
cây tìm kiếm nhị phân, là

741
00:34:49,389 --> 00:34:52,204
một trong đó, chúng ta có thể thực hiện nó
với một cấu trúc, chỉ như thế này.

742
00:34:52,204 --> 00:34:54,620
Và mặc dù chúng ta đang ném
rất nhiều cấu trúc tại của bạn,

743
00:34:54,620 --> 00:34:56,560
họ đang hơi
trực quan chỉ hy vọng.

744
00:34:56,560 --> 00:35:00,570
Cú pháp là vẫn còn phức tạp cho chắc chắn,
nhưng nội dung của một nút trong này

745
00:35:00,570 --> 00:35:02,786
context-- và chúng tôi giữ
sử dụng các nút chữ,

746
00:35:02,786 --> 00:35:04,910
cho dù đó là một hình chữ nhật
trên màn hình hoặc một vòng tròn,

747
00:35:04,910 --> 00:35:08,970
nó chỉ là một số thùng chứa chung chung,
trong trường hợp này của một cây, như một trong những

748
00:35:08,970 --> 00:35:11,780
chúng ta đã thấy, chúng ta cần một số nguyên
trong mỗi nút

749
00:35:11,780 --> 00:35:15,460
và sau đó tôi cần hai con trỏ trỏ
để con trái và con phải,

750
00:35:15,460 --> 00:35:16,590
tương ứng.

751
00:35:16,590 --> 00:35:20,730
Vì vậy, đó là làm thế nào chúng ta có thể
thực hiện điều đó trong một cấu trúc.

752
00:35:20,730 --> 00:35:22,315
Và làm thế nào tôi có thể thực hiện nó trong code?

753
00:35:22,315 --> 00:35:26,730
Vâng, chúng ta hãy nhanh chóng
nhìn vào ví dụ nhỏ này.

754
00:35:26,730 --> 00:35:29,820
Đó không phải là chức năng, nhưng tôi đã
sao chép và dán cấu trúc đó.

755
00:35:29,820 --> 00:35:33,510
Và nếu chức năng của tôi cho một số nhị phân
cây tìm kiếm được gọi là tìm kiếm,

756
00:35:33,510 --> 00:35:36,980
và điều này cần hai đối số,
một số nguyên N và một con trỏ

757
00:35:36,980 --> 00:35:41,400
đến một nút, do đó, một con trỏ đến cây
hoặc một con trỏ đến thư mục gốc của một cây,

758
00:35:41,400 --> 00:35:43,482
làm thế nào để đi về tìm kiếm cho N?

759
00:35:43,482 --> 00:35:45,440
Vâng, đầu tiên, bởi vì tôi là
đối phó với con trỏ,

760
00:35:45,440 --> 00:35:46,750
Tôi sẽ làm một kiểm tra sự tỉnh táo.

761
00:35:46,750 --> 00:35:54,279
Nếu equals cây bằng null, là N
trong cây này hay không trong cây này?

762
00:35:54,279 --> 00:35:55,070
Nó không thể được, phải không?

763
00:35:55,070 --> 00:35:56,870
Nếu tôi qua null,
có gì ở đó.

764
00:35:56,870 --> 00:35:59,230
Tôi có thể cũng chỉ
một cách mù quáng nói trở lại sai.

765
00:35:59,230 --> 00:36:04,050
Nếu bạn cung cấp cho tôi không có gì, tôi chắc chắn không thể
tìm thấy bất kỳ số N. Vì vậy, những gì khác tôi có thể

766
00:36:04,050 --> 00:36:04,750
kiểm tra ngay?

767
00:36:04,750 --> 00:36:12,830
Tôi sẽ phải nói cũng khác nếu N là
ít hơn so với bất cứ điều gì là tại các nút cây

768
00:36:12,830 --> 00:36:16,300
mà tôi đã được trao cho N giá trị.

769
00:36:16,300 --> 00:36:20,270
Nói cách khác, nếu số tôi
tìm kiếm, N, là ít hơn so với các nút

770
00:36:20,270 --> 00:36:21,340
mà tôi đang tìm kiếm tại.

771
00:36:21,340 --> 00:36:23,190
Và nút Tôi đang tìm
tại được gọi là cây,

772
00:36:23,190 --> 00:36:26,370
và nhớ lại từ ví dụ trước
để có được ở các giá trị trong một con trỏ,

773
00:36:26,370 --> 00:36:28,310
Tôi sử dụng các ký hiệu mũi tên.

774
00:36:28,310 --> 00:36:35,960
Vì vậy, nếu N là ít hơn so với cây mũi tên
N, tôi muốn khái niệm đi bên trái.

775
00:36:35,960 --> 00:36:38,590
Làm thế nào để tôi thể hiện: tìm kiếm này lại?

776
00:36:38,590 --> 00:36:41,560
Để được rõ ràng, nếu điều này là
hình ảnh trong câu hỏi,

777
00:36:41,560 --> 00:36:44,612
và tôi đã được thông qua mà trên cùng
mũi tên đó là trỏ xuống.

778
00:36:44,612 --> 00:36:45,570
Đó là con trỏ cây của tôi.

779
00:36:45,570 --> 00:36:48,060
Tôi chỉ vào thư mục gốc của cây.

780
00:36:48,060 --> 00:36:52,100
Và tôi đang tìm tiếng nói, cho
số 44, tùy tiện.

781
00:36:52,100 --> 00:36:55,300
Là 44 hoặc ít hơn
lớn hơn 55 rõ ràng?

782
00:36:55,300 --> 00:36:56,360
Vì vậy, nó ít hơn.

783
00:36:56,360 --> 00:36:58,760
Và vì vậy điều này nếu điều kiện được áp dụng.

784
00:36:58,760 --> 00:37:03,981
Vì vậy, khái niệm, tôi muốn những gì để
tìm kiếm tiếp theo nếu tôi đang tìm kiếm 44?

785
00:37:03,981 --> 00:37:04,480
Yeah?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Chính xác, tôi muốn
tìm kiếm con trái,

788
00:37:11,100 --> 00:37:12,789
hoặc trái cây tiểu của hình ảnh này.

789
00:37:12,789 --> 00:37:14,830
Và trên thực tế, cho tôi qua
hình ảnh xuống đây

790
00:37:14,830 --> 00:37:17,770
chỉ trong một khoảnh khắc, kể từ
Tôi không thể làm xước này ra.

791
00:37:17,770 --> 00:37:21,150
Nếu tôi bắt đầu ở đây là 55, và
Tôi biết rằng giá trị 44

792
00:37:21,150 --> 00:37:23,180
Tôi đang tìm kiếm là để
bên trái, đó là loại

793
00:37:23,180 --> 00:37:26,010
giống như xé cuốn sách điện thoại trong
nửa hoặc rách các cây trong một nửa.

794
00:37:26,010 --> 00:37:29,660
Tôi không còn phải quan tâm đến
toàn bộ nửa này của cây.

795
00:37:29,660 --> 00:37:33,270
Chưa hết, tò mò về các
cấu trúc, điều này trên đây mà

796
00:37:33,270 --> 00:37:36,682
bắt đầu với 33, mà bản thân
là một cây tìm kiếm nhị phân.

797
00:37:36,682 --> 00:37:39,890
Tôi nói từ trước bởi vì đệ quy
thực sự đây là một cấu trúc dữ liệu

798
00:37:39,890 --> 00:37:41,707
theo định nghĩa là đệ quy.

799
00:37:41,707 --> 00:37:44,540
Bạn có thể có một cái cây đó là này
lớn, nhưng mỗi một trong số các con của nó

800
00:37:44,540 --> 00:37:46,870
đại diện cho một cây chỉ nhỏ hơn một chút.

801
00:37:46,870 --> 00:37:50,910
Thay vì nó là ông nội
hoặc bà ngoại, bây giờ nó chỉ là mẹ

802
00:37:50,910 --> 00:37:54,300
or-- tôi không thể say-- không mẹ
hoặc cha, đó sẽ là kỳ lạ.

803
00:37:54,300 --> 00:37:59,000
Thay vào đó, hai đứa trẻ có
sẽ giống như anh trai và anh chị em.

804
00:37:59,000 --> 00:38:01,120
Một thế hệ mới của các cây gia đình.

805
00:38:01,120 --> 00:38:02,900
Nhưng về mặt cấu trúc, đó là ý tưởng tương tự.

806
00:38:02,900 --> 00:38:06,790
Và hóa ra tôi có một chức năng
mà tôi có thể tìm kiếm một tìm kiếm nhị phân

807
00:38:06,790 --> 00:38:07,290
cây.

808
00:38:07,290 --> 00:38:08,680
Nó được gọi là tìm kiếm.

809
00:38:08,680 --> 00:38:17,870
Tôi tìm kiếm cho N trong cây mũi tên trái
khác nếu N là lớn hơn giá trị

810
00:38:17,870 --> 00:38:18,870
mà tôi hiện tại là.

811
00:38:18,870 --> 00:38:20,800
55 trong câu chuyện lúc nãy.

812
00:38:20,800 --> 00:38:23,780
Tôi có một chức năng gọi là
tìm kiếm mà tôi có thể chỉ

813
00:38:23,780 --> 00:38:29,660
vượt qua N này và đệ quy tìm kiếm
các cây con và chỉ trở lại

814
00:38:29,660 --> 00:38:30,620
bất cứ câu trả lời đó.

815
00:38:30,620 --> 00:38:33,530
Khác tôi đã có một số trường hợp cơ sở thức ở đây.

816
00:38:33,530 --> 00:38:35,310
>> Các vụ án cuối cùng là gì?

817
00:38:35,310 --> 00:38:36,570
Cây hoặc là null.

818
00:38:36,570 --> 00:38:39,980
Các giá trị tôi hoặc tìm
ít hơn hoặc lớn hơn

819
00:38:39,980 --> 00:38:42,610
hoặc bằng nó.

820
00:38:42,610 --> 00:38:44,750
Và tôi có thể nói bằng
bình đẳng, nhưng một cách hợp lý nó

821
00:38:44,750 --> 00:38:46,500
tương đương với chỉ nói nào khác ở đây.

822
00:38:46,500 --> 00:38:49,150
Vì vậy, thật sự là cách tôi tìm thấy một cái gì đó.

823
00:38:49,150 --> 00:38:51,710
Vì vậy, hy vọng đây là một
thậm chí ví dụ hấp dẫn hơn

824
00:38:51,710 --> 00:38:54,900
hơn các chức năng sigma ngu ngốc
chúng tôi đã làm một vài bài giảng trở lại,

825
00:38:54,900 --> 00:38:58,360
nơi mà nó đã được chỉ là dễ dàng để sử dụng một vòng lặp
để đếm tất cả các số từ một

826
00:38:58,360 --> 00:39:02,390
để N. Ở đây với một cấu trúc dữ liệu
mà chính nó là đệ quy

827
00:39:02,390 --> 00:39:07,050
định nghĩa đệ quy và rút ra, bây giờ chúng tôi
có khả năng thể hiện bản thân

828
00:39:07,050 --> 00:39:09,780
trong mã đó chính là đệ quy.

829
00:39:09,780 --> 00:39:12,580
Vì vậy, đây là mã chính xác cùng ở đây.

830
00:39:12,580 --> 00:39:14,400
>> Vì vậy, những gì các vấn đề khác chúng ta có thể giải quyết?

831
00:39:14,400 --> 00:39:18,160
Vì vậy, một bước nhanh khỏi
cây chỉ trong một khoảnh khắc.

832
00:39:18,160 --> 00:39:20,130
Ở đây là, nói, lá cờ Đức.

833
00:39:20,130 --> 00:39:22,020
Và có một cách rõ ràng
mô hình để lá cờ này.

834
00:39:22,020 --> 00:39:23,811
Và có rất nhiều
cờ trong thế giới đó

835
00:39:23,811 --> 00:39:27,560
là đơn giản như này về
màu sắc và các mẫu của họ.

836
00:39:27,560 --> 00:39:31,930
Nhưng giả sử này được lưu giữ như một
.GIF, Hoặc JPEG, hoặc bitmap, hoặc một ping,

837
00:39:31,930 --> 00:39:34,240
bất kỳ định dạng tập tin đồ họa
mà bạn đã quen thuộc,

838
00:39:34,240 --> 00:39:36,460
một số trong đó chúng tôi
chơi với trong PSET4.

839
00:39:36,460 --> 00:39:41,550
Điều này dường như không đáng để lưu trữ
điểm ảnh màu đen, điểm ảnh màu đen, điểm ảnh màu đen,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, một bó toàn bộ
pixel màu đen cho scanline đầu tiên,

841
00:39:44,790 --> 00:39:47,430
hoặc hàng, sau đó một bó toàn bộ
giống nhau, sau đó một bó toàn bộ

842
00:39:47,430 --> 00:39:49,530
của nhau, và sau đó một
bó toàn bộ các điểm ảnh màu đỏ,

843
00:39:49,530 --> 00:39:53,020
điểm ảnh màu đỏ, các điểm ảnh màu đỏ, sau đó toàn bộ
bó pixel màu vàng, màu vàng, phải không?

844
00:39:53,020 --> 00:39:55,050
>> Có không hiệu quả như vậy ở đây.

845
00:39:55,050 --> 00:39:59,040
Làm thế nào bạn trực giác
nén cờ Đức

846
00:39:59,040 --> 00:40:01,320
nếu thực hiện nó như một tập tin?

847
00:40:01,320 --> 00:40:04,940
Giống như những thông tin nào có thể chúng ta không
bận tâm lưu trữ trên đĩa để

848
00:40:04,940 --> 00:40:08,040
để giảm kích thước tập tin của chúng tôi từ như
một megabyte để một kilobyte, một cái gì đó

849
00:40:08,040 --> 00:40:09,430
nhỏ hơn?

850
00:40:09,430 --> 00:40:13,130
Trong đó nằm trong dự phòng
ở đây cần được rõ ràng?

851
00:40:13,130 --> 00:40:13,880
Bạn có thể làm gì?

852
00:40:13,880 --> 00:40:14,380
Yeah?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Chính xác.

855
00:40:21,970 --> 00:40:24,550
Tại sao không chứ không phải là nhớ
màu sắc của mỗi điểm ảnh darn

856
00:40:24,550 --> 00:40:28,200
giống như bạn đang làm trong PSET4
với các định dạng tập tin bitmap,

857
00:40:28,200 --> 00:40:32,060
tại sao bạn không chỉ đại diện cho
cột ngoài cùng bên trái của điểm ảnh, ví dụ

858
00:40:32,060 --> 00:40:35,370
một loạt các điểm ảnh màu đen, một bó
màu đỏ, và một loạt các màu vàng,

859
00:40:35,370 --> 00:40:39,210
và sau đó chỉ cần bằng cách nào đó mã hóa
ý tưởng này lặp lại 100 lần

860
00:40:39,210 --> 00:40:41,020
hoặc lặp lại điều này 1.000 lần?

861
00:40:41,020 --> 00:40:43,430
Nơi 100 hoặc 1000 là
chỉ là một số nguyên, vì vậy bạn

862
00:40:43,430 --> 00:40:47,290
có thể nhận được ngay với chỉ một số duy nhất
thay vì hàng trăm hoặc hàng ngàn

863
00:40:47,290 --> 00:40:48,270
điểm ảnh bổ sung.

864
00:40:48,270 --> 00:40:50,990
Và quả thực, đó là cách chúng tôi
có thể nén các lá cờ Đức.

865
00:40:50,990 --> 00:40:51,490
Và

866
00:40:51,490 --> 00:40:53,470
Bây giờ những gì về cờ Pháp?

867
00:40:53,470 --> 00:40:58,930
Và một chút một số loại
rèn luyện tinh thần, mà cờ

868
00:40:58,930 --> 00:41:01,040
có thể được nén nhiều hơn trên đĩa?

869
00:41:01,040 --> 00:41:05,720
Cờ Đức hoặc Pháp
cờ, nếu chúng ta áp dụng phương pháp đó?

870
00:41:05,720 --> 00:41:08,490
Cờ Đức, bởi vì có
nhiều sự thừa ngang.

871
00:41:08,490 --> 00:41:12,190
Và do thiết kế, nhiều tập tin đồ họa
định dạng nào thực sự làm việc như quét đường

872
00:41:12,190 --> 00:41:12,830
theo chiều ngang.

873
00:41:12,830 --> 00:41:14,674
Họ có thể làm việc
theo chiều dọc, chỉ cần nhân loại

874
00:41:14,674 --> 00:41:17,090
năm trước đã quyết định rằng chúng ta sẽ
thường nghĩ về những điều liên tiếp

875
00:41:17,090 --> 00:41:18,880
bởi hàng thay vì cột theo cột.

876
00:41:18,880 --> 00:41:20,820
Vì vậy, thực sự nếu bạn là
để xem các tập tin

877
00:41:20,820 --> 00:41:24,670
kích thước của một lá cờ Đức và Pháp
cờ, miễn là độ phân giải là

878
00:41:24,670 --> 00:41:27,530
như nhau, có cùng chiều rộng
và chiều cao, điều này

879
00:41:27,530 --> 00:41:31,580
ở đây là có được lớn hơn, bởi vì bạn
phải lặp lại chính mình ba lần.

880
00:41:31,580 --> 00:41:35,570
Bạn phải xác định màu xanh, lặp lại
chính mình, trắng, lặp lại chính mình, đỏ,

881
00:41:35,570 --> 00:41:36,740
lặp lại chính mình.

882
00:41:36,740 --> 00:41:39,000
Bạn có thể không chỉ đi tất cả
các đường bên phải.

883
00:41:39,000 --> 00:41:41,200
Và như một sang một bên, để làm cho
xóa nén

884
00:41:41,200 --> 00:41:43,910
ở khắp mọi nơi, nếu đây là những
bốn khung hình từ một video-- bạn

885
00:41:43,910 --> 00:41:45,890
có thể nhớ lại rằng một bộ phim
hoặc video nói chung là

886
00:41:45,890 --> 00:41:47,286
như 29 hoặc 30 khung hình mỗi giây.

887
00:41:47,286 --> 00:41:50,410
Nó giống như một lật cuốn sổ nhỏ, nơi bạn
chỉ nhìn thấy hình ảnh, hình ảnh, hình ảnh, hình ảnh,

888
00:41:50,410 --> 00:41:54,410
hình ảnh chỉ là siêu nhanh như vậy có vẻ như
các diễn viên trên màn hình đang di chuyển.

889
00:41:54,410 --> 00:41:57,130
Dưới đây là một con ong bumble trên
đỉnh của một bó hoa.

890
00:41:57,130 --> 00:41:59,790
Và mặc dù nó có thể là loại
khó nhìn thấy ở cái nhìn đầu tiên,

891
00:41:59,790 --> 00:42:04,020
điều duy nhất di chuyển trong
phim này là những con ong.

892
00:42:04,020 --> 00:42:06,880
>> Là gì câm về lưu trữ
Video giải nén?

893
00:42:06,880 --> 00:42:11,420
Đó là loại chất thải để lưu trữ video
như bốn hình ảnh gần như giống hệt nhau

894
00:42:11,420 --> 00:42:13,670
chỉ khác nhau trong chừng mực mà các ong.

895
00:42:13,670 --> 00:42:16,280
Bạn có thể vứt bỏ nhất
thông tin mà

896
00:42:16,280 --> 00:42:20,190
và nhớ chỉ, ví dụ,
frame đầu tiên và frame cuối cùng,

897
00:42:20,190 --> 00:42:22,180
khung hình chính nếu bạn đã
bao giờ nghe lời,

898
00:42:22,180 --> 00:42:24,337
và chỉ lưu trữ trong
giữa, nơi thì ong.

899
00:42:24,337 --> 00:42:26,170
Và bạn không cần phải
lưu trữ tất cả các màu hồng,

900
00:42:26,170 --> 00:42:28,330
và màu xanh, và các
xanh lá cây là tốt.

901
00:42:28,330 --> 00:42:31,200
Vì vậy, đây là chỉ nói rằng
nén là ở khắp mọi nơi.

902
00:42:31,200 --> 00:42:34,900
Đó là một kỹ thuật chúng ta thường sử dụng
hoặc đưa cho các cấp trong những ngày này.

903
00:42:34,900 --> 00:42:38,750
>> Nhưng làm thế nào để bạn nén văn bản?

904
00:42:38,750 --> 00:42:40,450
Làm thế nào để bạn đi về nén văn bản?

905
00:42:40,450 --> 00:42:45,410
Vâng, mỗi nhân vật trong
Ascii là một byte, hoặc tám bit.

906
00:42:45,410 --> 00:42:47,360
Và đó là loại ngu ngốc, phải không?

907
00:42:47,360 --> 00:42:51,160
Bởi vì bạn có thể gõ A
và E và I và O và U rất nhiều

908
00:42:51,160 --> 00:42:55,270
thường xuyên hơn như W hoặc Q hoặc Z,
tùy thuộc vào ngôn ngữ mà

909
00:42:55,270 --> 00:42:56,610
bạn đang viết chắc chắn.

910
00:42:56,610 --> 00:42:59,600
Và như vậy tại sao chúng ta sử dụng
tám bit cho mỗi lá thư,

911
00:42:59,600 --> 00:43:02,040
trong đó có ít nhất
chữ nổi, phải không?

912
00:43:02,040 --> 00:43:05,300
Tại sao không sử dụng bit ít cho
các chữ siêu phổ biến,

913
00:43:05,300 --> 00:43:07,760
như E, những điều bạn đoán
đầu tiên trong Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
và sử dụng nhiều bit cho
các chữ cái ít phổ biến?

915
00:43:10,450 --> 00:43:10,950
Tại sao?

916
00:43:10,950 --> 00:43:13,130
Bởi vì chúng tôi chỉ cần đi để
sử dụng chúng thường xuyên.

917
00:43:13,130 --> 00:43:15,838
>> Vâng, nó chỉ ra rằng có có
những nỗ lực thực hiện để làm điều này.

918
00:43:15,838 --> 00:43:18,630
Và nếu bạn gọi lại từ lớp
trường học hoặc trung học, mã Morse.

919
00:43:18,630 --> 00:43:20,400
Mã Morse có dấu chấm
và dấu gạch ngang có thể được

920
00:43:20,400 --> 00:43:24,270
truyền dọc theo một dây như
âm thanh hay tín hiệu của một số loại.

921
00:43:24,270 --> 00:43:25,930
Tuy nhiên, mã Morse là một siêu sạch.

922
00:43:25,930 --> 00:43:29,010
Đó là một loại hệ thống nhị phân trong
rằng bạn có dấu chấm hoặc dấu gạch ngang.

923
00:43:29,010 --> 00:43:30,977
Nhưng nếu bạn nhìn thấy, ví dụ, hai chấm.

924
00:43:30,977 --> 00:43:33,810
Hoặc nếu bạn suy nghĩ lại về điều hành
người đi như tiếng bíp, bíp, bíp,

925
00:43:33,810 --> 00:43:36,760
beep, đánh một chút kích hoạt
mà truyền một tín hiệu,

926
00:43:36,760 --> 00:43:40,360
nếu bạn là người nhận, nhận được hai
chấm, những tin nhắn đã nhận bạn?

927
00:43:40,360 --> 00:43:43,490
Hoàn toàn tùy ý.

928
00:43:43,490 --> 00:43:44,450
>> Tôi?

929
00:43:44,450 --> 00:43:45,060
Tôi?

930
00:43:45,060 --> 00:43:47,500
Hoặc những gì about-- hay tôi?

931
00:43:47,500 --> 00:43:49,570
Có lẽ đó chỉ là hai E phải không?

932
00:43:49,570 --> 00:43:52,480
Vì vậy, có vấn đề này
của decodability với Morse

933
00:43:52,480 --> 00:43:54,890
mã, theo đó, trừ khi
người gửi cho bạn thông báo

934
00:43:54,890 --> 00:43:59,510
thực sự dừng lại vì vậy bạn có thể sắp xếp của
nhìn thấy hoặc nghe thấy những khoảng trống giữa các chữ cái,

935
00:43:59,510 --> 00:44:02,990
nó không đủ chỉ để
gửi một dòng số không và những người thân,

936
00:44:02,990 --> 00:44:05,610
hoặc dấu chấm và dấu gạch ngang,
bởi vì có sự không rõ ràng.

937
00:44:05,610 --> 00:44:08,640
E là một dấu chấm duy nhất, vì vậy nếu bạn
thấy hai chấm hoặc nghe thấy hai chấm,

938
00:44:08,640 --> 00:44:11,254
có thể nó là của hai E hoặc có thể nó là một I.

939
00:44:11,254 --> 00:44:13,670
Vì vậy, chúng ta cần một hệ thống đó là một
ít hơn thông minh hơn.

940
00:44:13,670 --> 00:44:16,851
Vì vậy, một người đàn ông tên Huffman năm
trước đây đã đưa ra chính xác này.

941
00:44:16,851 --> 00:44:18,600
Vì vậy, chúng tôi chỉ cần đi
để có một cái nhìn nhanh chóng

942
00:44:18,600 --> 00:44:20,114
làm thế nào cây Gecman này.

943
00:44:20,114 --> 00:44:22,530
Giả sử rằng đây là một số
nhắn ngu ngốc bạn muốn gửi,

944
00:44:22,530 --> 00:44:26,342
bao gồm các chỉ A, B, C của D's và E của,
nhưng có rất nhiều dự phòng ở đây.

945
00:44:26,342 --> 00:44:27,550
Nó không có nghĩa là tiếng Anh.

946
00:44:27,550 --> 00:44:28,341
Nó không được mã hóa.

947
00:44:28,341 --> 00:44:30,540
Nó chỉ là một thông điệp ngu ngốc
với rất nhiều sự lặp lại.

948
00:44:30,540 --> 00:44:34,010
Vì vậy, nếu bạn thực sự tính ra tất cả các
A, B, C, D, và E của, đây là

949
00:44:34,010 --> 00:44:34,890
tần số.

950
00:44:34,890 --> 00:44:37,800
20% của các chữ cái
A, 45% thư

951
00:44:37,800 --> 00:44:39,660
là của E, và ba tần số khác.

952
00:44:39,660 --> 00:44:41,960
Chúng tôi đếm được có tay
và chỉ cần làm toán.

953
00:44:41,960 --> 00:44:44,579
>> Vì vậy, nó chỉ ra rằng
Huffman, một số thời gian trước đây,

954
00:44:44,579 --> 00:44:46,620
nhận ra rằng, bạn biết
những gì, nếu tôi bắt đầu xây dựng

955
00:44:46,620 --> 00:44:51,172
một cây, hoặc rừng cây, nếu bạn muốn,
như sau, tôi có thể làm như sau.

956
00:44:51,172 --> 00:44:53,880
Tôi sẽ đưa ra một nút cho mỗi
của các chữ cái mà tôi quan tâm

957
00:44:53,880 --> 00:44:55,530
và tôi sẽ lưu trữ
bên trong của nút đó

958
00:44:55,530 --> 00:44:58,610
các tần số như là một điểm nổi
giá trị, hoặc bạn có thể sử dụng nó một N, quá,

959
00:44:58,610 --> 00:45:00,210
nhưng chúng tôi sẽ chỉ sử dụng một float ở đây.

960
00:45:00,210 --> 00:45:03,100
Và các thuật toán mà
ông đề nghị là bạn

961
00:45:03,100 --> 00:45:07,210
mất rừng này của nút duy nhất
cây, cây nên siêu ngắn,

962
00:45:07,210 --> 00:45:11,920
và bạn bắt đầu kết nối chúng với
nhóm mới, cha mẹ mới, nếu bạn sẽ.

963
00:45:11,920 --> 00:45:16,150
Và bạn làm điều này bằng cách chọn
hai tần số nhỏ nhất tại một thời điểm.

964
00:45:16,150 --> 00:45:18,110
Vì vậy, tôi mất 10% và 10%.

965
00:45:18,110 --> 00:45:19,090
Tôi tạo ra một nút mới.

966
00:45:19,090 --> 00:45:20,910
Và tôi gọi là nút mới 20%.

967
00:45:20,910 --> 00:45:22,750
>> Mà hai nút tôi kết hợp tiếp theo?

968
00:45:22,750 --> 00:45:23,810
Đó là một chút mơ hồ.

969
00:45:23,810 --> 00:45:26,643
Vì vậy, có một số trường hợp góc tới
xem xét, nhưng để giữ cho mọi thứ khá,

970
00:45:26,643 --> 00:45:29,300
Tôi sẽ chọn 20% -
Bây giờ tôi bỏ qua các con.

971
00:45:29,300 --> 00:45:33,640
Tôi sẽ chọn 20% và
15% và vẽ hai cạnh mới.

972
00:45:33,640 --> 00:45:35,624
Và bây giờ mà hai nút
Tôi kết hợp một cách hợp lý?

973
00:45:35,624 --> 00:45:38,540
Bỏ qua tất cả các con, tất cả các
cháu, chỉ cần nhìn vào các rễ

974
00:45:38,540 --> 00:45:39,070
bây giờ.

975
00:45:39,070 --> 00:45:42,220
Mà hai nút để tôi gắn kết với nhau?

976
00:45:42,220 --> 00:45:44,530
Điểm hai và 0,35.

977
00:45:44,530 --> 00:45:45,890
Vì vậy, hãy để tôi vẽ hai cạnh mới.

978
00:45:45,890 --> 00:45:47,570
Và sau đó tôi đã chỉ có một trái.

979
00:45:47,570 --> 00:45:48,650
Vì vậy, đây là một cây.

980
00:45:48,650 --> 00:45:51,160
Và nó được rút ra cố tình
để tìm loại khá,

981
00:45:51,160 --> 00:45:55,870
nhưng nhận thấy các cạnh có
cũng được dán nhãn không và một.

982
00:45:55,870 --> 00:45:59,510
Vì vậy, tất cả các cạnh còn lại là số không
tùy tiện, nhưng luôn.

983
00:45:59,510 --> 00:46:01,170
Tất cả các cạnh bên phải là những người thân.

984
00:46:01,170 --> 00:46:05,070
>> Và vì vậy những gì Hoffman đề xuất là,
nếu bạn muốn đại diện cho một B,

985
00:46:05,070 --> 00:46:10,080
chứ không phải là đại diện cho số 66 là
một Ascii mà là tám toàn bộ bit,

986
00:46:10,080 --> 00:46:13,360
bạn biết những gì, chỉ cửa hàng
mô hình không, không, không,

987
00:46:13,360 --> 00:46:17,030
bằng không, bởi vì đó là con đường
từ cây của tôi, cây của ông Huffman,

988
00:46:17,030 --> 00:46:18,600
để các lá từ gốc.

989
00:46:18,600 --> 00:46:20,970
Nếu bạn muốn lưu trữ một
E, ngược lại, không

990
00:46:20,970 --> 00:46:26,290
gửi tám bit đại diện cho một E.
Thay vào đó, hãy gửi những gì mô hình của các bit?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
Và những gì là tốt đẹp về việc này là
E rằng là thư phổ biến nhất,

993
00:46:30,410 --> 00:46:32,340
và bạn đang sử dụng
mã ngắn nhất cho nó.

994
00:46:32,340 --> 00:46:34,090
Tiếp theo phổ biến nhất
thư có vẻ như nó

995
00:46:34,090 --> 00:46:37,380
là A. Và như vậy bao nhiêu bit
ông đã đề xuất sử dụng cho điều đó?

996
00:46:37,380 --> 00:46:38,270
Zero, một.

997
00:46:38,270 --> 00:46:41,060
>> Và bởi vì nó được thực hiện
như cây này, cho bây giờ

998
00:46:41,060 --> 00:46:43,350
hãy để tôi định có
không mơ hồ như trong Morse

999
00:46:43,350 --> 00:46:46,090
mã, vì tất cả các
chữ mà bạn quan tâm

1000
00:46:46,090 --> 00:46:48,780
đang ở cuối của các cạnh.

1001
00:46:48,780 --> 00:46:50,580
Vì vậy, đó chỉ là một
ứng dụng của một cái cây.

1002
00:46:50,580 --> 00:46:52,538
Đây is-- và tôi sẽ sóng
Mặt tôi lúc này như thế nào bạn

1003
00:46:52,538 --> 00:46:55,570
có thể thực hiện điều này như là một cấu trúc C.

1004
00:46:55,570 --> 00:46:58,260
Chúng tôi chỉ cần kết hợp
một biểu tượng, như một char,

1005
00:46:58,260 --> 00:46:59,910
và tần số ở bên trái và bên phải.

1006
00:46:59,910 --> 00:47:02,510
Nhưng chúng ta hãy nhìn vào hai
ví dụ cuối cùng mà bạn sẽ

1007
00:47:02,510 --> 00:47:06,070
nhận được khá quen thuộc với sau
đố zero trong vấn đề thiết lập năm.

1008
00:47:06,070 --> 00:47:09,210
>> Vì vậy, có cấu trúc dữ liệu
được biết đến như là một bảng băm.

1009
00:47:09,210 --> 00:47:12,247
Và một bảng băm là loại
mát ở chỗ nó có xô.

1010
00:47:12,247 --> 00:47:14,830
Và giả sử có bốn xô
ở đây, chỉ cần bốn không gian trống.

1011
00:47:14,830 --> 00:47:20,830
Dưới đây là một bộ bài, và đây là
câu lạc bộ, thuổng, câu lạc bộ, kim cương, câu lạc bộ,

1012
00:47:20,830 --> 00:47:25,960
kim cương, câu lạc bộ, kim cương,
clubs-- vì vậy đây là sự ngẫu nhiên.

1013
00:47:25,960 --> 00:47:30,330
Hearts, hearts-- nên tôi
bucketizing tất cả các yếu tố đầu vào ở đây.

1014
00:47:30,330 --> 00:47:32,430
Và một nhu cầu bảng băm
nhìn vào đầu vào của bạn,

1015
00:47:32,430 --> 00:47:34,850
và sau đó đặt nó trong một số
đặt dựa trên những gì bạn nhìn thấy.

1016
00:47:34,850 --> 00:47:35,600
Đó là một thuật toán.

1017
00:47:35,600 --> 00:47:37,980
Và tôi đã sử dụng một siêu
Thuật toán trực quan đơn giản.

1018
00:47:37,980 --> 00:47:40,030
Phần khó nhất trong số đó là
ghi nhớ những gì các bức ảnh đều.

1019
00:47:40,030 --> 00:47:41,590
Và sau đó có tổng cộng bốn điều.

1020
00:47:41,590 --> 00:47:45,440
>> Bây giờ các ngăn xếp đã được phát triển, trong đó
là một thiết kế điều cố ý ở đây.

1021
00:47:45,440 --> 00:47:46,540
Nhưng những gì khác tôi có thể làm gì?

1022
00:47:46,540 --> 00:47:49,080
Vì vậy, thực sự ở đây chúng ta có một
bó sách thi học cũ.

1023
00:47:49,080 --> 00:47:51,240
Giả sử rằng một loạt các
tên học sinh ở đây.

1024
00:47:51,240 --> 00:47:52,570
Dưới đây là một bảng băm lớn hơn.

1025
00:47:52,570 --> 00:47:54,867
Thay vì bốn xô,
Tôi đã, chúng ta hãy nói 26.

1026
00:47:54,867 --> 00:47:57,950
Và chúng tôi không muốn đi vay 26
những thứ từ bên ngoài [? Annenberg?], Vì vậy

1027
00:47:57,950 --> 00:48:00,289
đây là năm mà đại diện
A đến Z. Và nếu tôi

1028
00:48:00,289 --> 00:48:03,580
nhìn thấy một học sinh có tên bắt đầu bằng A,
Tôi sẽ đưa ông hay đố cô ở đó.

1029
00:48:03,580 --> 00:48:08,850
Nếu ai đó bắt đầu với C, qua đó,
A-- thực sự, không muốn làm điều đó.

1030
00:48:08,850 --> 00:48:10,060
B đi qua đây.

1031
00:48:10,060 --> 00:48:13,390
Vì vậy, tôi đã có A và B và C. Và
bây giờ đây là một Một học sinh.

1032
00:48:13,390 --> 00:48:16,212
Nhưng nếu bảng băm này là
thực hiện với một mảng,

1033
00:48:16,212 --> 00:48:17,920
Tôi là loại hơi say
vào thời điểm này, phải không?

1034
00:48:17,920 --> 00:48:19,510
Tôi loại cần phải đặt một nơi nào đó.

1035
00:48:19,510 --> 00:48:24,380
>> Vì vậy, một cách nào tôi có thể giải quyết điều này là, tất cả
đúng, A là bận rộn, B là bận rộn, C là bận rộn.

1036
00:48:24,380 --> 00:48:28,880
Tôi sẽ đưa anh ta trong D. Vì vậy, tại
đầu tiên, tôi phải ngẫu nhiên ngay lập tức truy cập

1037
00:48:28,880 --> 00:48:31,064
cho mỗi nhóm cho các sinh viên.

1038
00:48:31,064 --> 00:48:33,230
Nhưng bây giờ nó loại phân cấp
vào một cái gì đó tuyến tính,

1039
00:48:33,230 --> 00:48:36,750
bởi vì nếu tôi muốn tìm kiếm ai đó
tên mà bắt đầu bằng A, tôi kiểm tra ở đây.

1040
00:48:36,750 --> 00:48:38,854
Nhưng nếu điều này không phải là A
sinh viên, tôi đang tìm,

1041
00:48:38,854 --> 00:48:41,520
Tôi có loại để bắt đầu kiểm tra
xô, bởi vì những gì tôi đã làm

1042
00:48:41,520 --> 00:48:44,530
là loại tuyến tính
thăm dò cấu trúc dữ liệu.

1043
00:48:44,530 --> 00:48:47,710
Một cách ngu ngốc nói chỉ cần nhìn
cho việc mở cửa đầu tiên có sẵn,

1044
00:48:47,710 --> 00:48:51,850
và đặt như là một kế hoạch B, có thể nói,
hoặc kế hoạch D trong trường hợp này, giá trị

1045
00:48:51,850 --> 00:48:53,340
tại địa điểm đó để thay thế.

1046
00:48:53,340 --> 00:48:56,470
Đây chỉ là để nếu bạn đã
có 26 địa điểm và không có học sinh

1047
00:48:56,470 --> 00:49:00,600
với Q tên hoặc Z, hoặc một cái gì đó như
rằng, ít nhất bạn đang sử dụng không gian.

1048
00:49:00,600 --> 00:49:03,140
>> Nhưng chúng tôi đã nhìn thấy nhiều hơn
giải pháp thông minh ở đây, phải không?

1049
00:49:03,140 --> 00:49:04,870
Bạn sẽ làm gì thay vì
nếu bạn có một vụ va chạm?

1050
00:49:04,870 --> 00:49:06,670
Nếu hai người có
tên A, những gì sẽ

1051
00:49:06,670 --> 00:49:09,160
đã là một thông minh hơn hay nhiều hơn
giải pháp trực quan hơn là chỉ

1052
00:49:09,160 --> 00:49:12,840
đưa A trong đó D là vụ phải được?

1053
00:49:12,840 --> 00:49:14,810
Tại sao tôi không chỉ đi
bên ngoài [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
như malloc, một nút khác, đặt nó
ở đây, và sau đó đưa rằng Một học sinh ở đây.

1055
00:49:19,960 --> 00:49:22,120
Vì vậy mà tôi về cơ bản có
một số loại của một mảng,

1056
00:49:22,120 --> 00:49:25,590
hoặc có thể thanh lịch hơn như chúng tôi
bắt đầu nhìn thấy một danh sách liên kết.

1057
00:49:25,590 --> 00:49:29,520
>> Và do đó, một bảng băm là một cấu trúc
mà có thể trông giống như thế này,

1058
00:49:29,520 --> 00:49:33,900
nhưng khéo léo hơn, bạn có một cái gì đó gọi là
chaining riêng biệt, theo đó một bảng băm

1059
00:49:33,900 --> 00:49:38,340
khá đơn giản chỉ là một mảng, mỗi
mà các thành phần không phải là một con số,

1060
00:49:38,340 --> 00:49:40,470
bản thân nó là một danh sách liên kết.

1061
00:49:40,470 --> 00:49:45,080
Vì vậy mà bạn có thể truy cập siêu nhanh
quyết định nơi để băm giá trị của bạn.

1062
00:49:45,080 --> 00:49:48,059
Giống như với ví dụ thẻ,
Tôi đã quyết định siêu nhanh.

1063
00:49:48,059 --> 00:49:49,600
Hearts tại đây, kim cương tại đây.

1064
00:49:49,600 --> 00:49:52,180
Tương tự ở đây, A đi đây,
D đi đây, đi B ở đây.

1065
00:49:52,180 --> 00:49:55,740
Vì vậy, siêu nhanh look-up, và nếu
bạn xảy ra để chạy vào một trường hợp

1066
00:49:55,740 --> 00:49:59,429
va chạm mà bạn đã có, hai
những người có cùng tên, cũng sau đó

1067
00:49:59,429 --> 00:50:00,970
bạn chỉ cần bắt đầu liên kết chúng lại với nhau.

1068
00:50:00,970 --> 00:50:03,900
Và có thể bạn giữ chúng được sắp xếp
theo thứ tự abc, có lẽ bạn không.

1069
00:50:03,900 --> 00:50:05,900
Nhưng ít nhất chúng ta có tính năng động.

1070
00:50:05,900 --> 00:50:10,250
Vì vậy, một mặt chúng ta có siêu nhanh
thời gian liên tục, và loại thời gian tuyến tính

1071
00:50:10,250 --> 00:50:14,110
tham gia nếu các danh sách liên kết
bắt đầu để có được một ít lâu.

1072
00:50:14,110 --> 00:50:16,880
>> Vì vậy, loại này của một ngớ ngẩn,
geeky đùa năm trước.

1073
00:50:16,880 --> 00:50:19,590
Tại CS50 hack-a-thon,
khi học sinh nhận phòng,

1074
00:50:19,590 --> 00:50:22,040
một số TF hoặc CA mỗi năm
nghĩ đó thật buồn cười phải đưa lên

1075
00:50:22,040 --> 00:50:27,772
một dấu hiệu như thế này, mà nó chỉ
có nghĩa là nếu tên của bạn bắt đầu với một A,

1076
00:50:27,772 --> 00:50:28,870
đi theo con đường này.

1077
00:50:28,870 --> 00:50:31,110
Nếu tên của bạn bắt đầu
với B, đi this-- OK,

1078
00:50:31,110 --> 00:50:33,290
đó thật buồn cười có lẽ sau này trong các học kỳ.

1079
00:50:33,290 --> 00:50:36,420
Nhưng có một
cách làm này, quá.

1080
00:50:36,420 --> 00:50:37,410
Hãy trở lại đó.

1081
00:50:37,410 --> 00:50:38,600
>> Vì vậy, có cấu trúc này.

1082
00:50:38,600 --> 00:50:40,420
Và điều này là cuối cùng của chúng tôi
cấu trúc cho ngày hôm nay,

1083
00:50:40,420 --> 00:50:42,400
mà là một cái gì đó gọi là một Trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, mà vì một lý do là ngắn
để thu hồi, nhưng nó được gọi là Trie.

1085
00:50:47,140 --> 00:50:51,389
Vì vậy, một Trie là một thú vị
hỗn hợp của rất nhiều những ý tưởng này.

1086
00:50:51,389 --> 00:50:52,930
Đó là một cái cây, mà chúng tôi đã nhìn thấy trước.

1087
00:50:52,930 --> 00:50:54,180
Nó không phải là một cây tìm kiếm nhị phân.

1088
00:50:54,180 --> 00:50:58,410
Đó là một cây với bất kỳ số lượng trẻ em,
nhưng mỗi trẻ em trong một Trie

1089
00:50:58,410 --> 00:51:00,090
là một mảng.

1090
00:51:00,090 --> 00:51:04,790
Một loạt các kích cỡ, nói, 26 hoặc có thể 27
nếu bạn muốn hỗ trợ tên có dấu nối

1091
00:51:04,790 --> 00:51:06,790
hoặc dấu nháy trong tên của người dân.

1092
00:51:06,790 --> 00:51:08,280
>> Và vì vậy đây là một cấu trúc dữ liệu.

1093
00:51:08,280 --> 00:51:10,290
Và nếu bạn nhìn từ đầu
xuống dưới, giống như nếu bạn

1094
00:51:10,290 --> 00:51:13,710
nhìn vào các nút trên cùng ở đó, M, là
trỏ đến tận cùng bên trái có điều,

1095
00:51:13,710 --> 00:51:17,665
mà sau đó A, X, W, E, L, L. Đây là
chỉ là một cấu trúc dữ liệu mà tùy tiện

1096
00:51:17,665 --> 00:51:19,120
là lưu trữ tên của người dân.

1097
00:51:19,120 --> 00:51:25,720
Và Maxwell được lưu trữ bởi chỉ sau
một con đường của mảng vào mảng vào mảng.

1098
00:51:25,720 --> 00:51:30,050
Nhưng điều tuyệt vời về một Trie là
rằng, trong khi một danh sách liên kết và thậm chí

1099
00:51:30,050 --> 00:51:34,520
một mảng, là tốt nhất mà chúng tôi từng nhận được là
thời gian tuyến tính logarit hoặc thời gian tìm kiếm

1100
00:51:34,520 --> 00:51:35,600
ai đó lên.

1101
00:51:35,600 --> 00:51:40,530
Trong cấu trúc dữ liệu này của một Trie, nếu
cấu trúc dữ liệu của tôi có một tên trong nó

1102
00:51:40,530 --> 00:51:43,720
và tôi đang tìm Maxwell, tôi
sẽ tìm thấy anh ta khá nhanh chóng.

1103
00:51:43,720 --> 00:51:47,910
Tôi chỉ cần nhìn cho M-A-X-W-E-L-L. Nếu
cấu trúc dữ liệu này, ngược lại,

1104
00:51:47,910 --> 00:51:51,830
nếu N là một triệu, nếu có một
triệu tên trong cấu trúc dữ liệu này,

1105
00:51:51,830 --> 00:51:57,100
Maxwell vẫn sẽ được
phát hiện chỉ sau M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
bước.

1107
00:51:58,090 --> 00:52:01,276
Và David-- D-A-V-I-D bước.

1108
00:52:01,276 --> 00:52:03,400
Nói cách khác, bằng cách xây dựng
một cấu trúc dữ liệu đó

1109
00:52:03,400 --> 00:52:07,240
đã nhận tất cả các mảng, tất cả đều
mình hỗ trợ truy cập ngẫu nhiên,

1110
00:52:07,240 --> 00:52:11,090
Tôi có thể bắt đầu nhìn lên của nhân dân
đặt tên bằng cách sử dụng một số lượng thời gian đó là

1111
00:52:11,090 --> 00:52:14,340
tỷ lệ thuận với số lượng không
của sự vật trong các cấu trúc dữ liệu,

1112
00:52:14,340 --> 00:52:16,330
giống như một triệu tên hiện có.

1113
00:52:16,330 --> 00:52:20,135
Lượng thời gian cần tôi để tìm
M-A-X-W-E-L-L trong cấu trúc dữ liệu này là

1114
00:52:20,135 --> 00:52:22,260
tỷ lệ chưa đến
kích thước của cấu trúc dữ liệu,

1115
00:52:22,260 --> 00:52:25,930
nhưng với chiều dài của tên.

1116
00:52:25,930 --> 00:52:28,440
Và thực tế các
tên mà chúng ta đang nhìn lên

1117
00:52:28,440 --> 00:52:29,970
sẽ không bao giờ được điên dài.

1118
00:52:29,970 --> 00:52:32,600
Có lẽ ai đó có một nhân vật 10
tên, 20 tên nhân vật.

1119
00:52:32,600 --> 00:52:33,900
Đó chắc chắn là hữu hạn, phải không?

1120
00:52:33,900 --> 00:52:37,110
Có một con người trên trái đất người
có tên dài nhất có thể,

1121
00:52:37,110 --> 00:52:39,920
nhưng tên đó là một hằng số
chiều dài giá trị, phải không?

1122
00:52:39,920 --> 00:52:41,980
Nó không thay đổi trong bất kỳ ý nghĩa.

1123
00:52:41,980 --> 00:52:45,090
Vì vậy, theo cách này, chúng tôi đã
đạt được một cấu trúc dữ liệu

1124
00:52:45,090 --> 00:52:47,800
đó là thời gian liên tục nhìn lên.

1125
00:52:47,800 --> 00:52:50,670
Nó có một số bước
tùy thuộc vào độ dài của đầu vào,

1126
00:52:50,670 --> 00:52:54,250
nhưng không phải là số lượng các tên
trong cấu trúc dữ liệu.

1127
00:52:54,250 --> 00:52:58,700
Vì vậy, nếu chúng ta tăng gấp đôi số lượng tên
năm tiếp theo từ một tỷ đến hai tỷ đồng,

1128
00:52:58,700 --> 00:53:03,720
Phát hiện Maxwell là sẽ mất
con số chính xác cùng của bảy bước

1129
00:53:03,720 --> 00:53:04,650
để tìm thấy anh ta.

1130
00:53:04,650 --> 00:53:08,810
Và như vậy chúng ta dường như đã đạt được
Chén thánh của chúng ta về thời gian chạy.

1131
00:53:08,810 --> 00:53:10,860
>> Vì vậy, một vài thông báo nhanh chóng.

1132
00:53:10,860 --> 00:53:11,850
Đố zero là đến.

1133
00:53:11,850 --> 00:53:14,600
Thêm vào đó trên trang web của khóa học
trong vài ngày tới.

1134
00:53:14,600 --> 00:53:17,120
Thứ hai của lecture-- đó là một kỳ nghỉ
ở đây tại Harvard vào thứ hai.

1135
00:53:17,120 --> 00:53:18,850
Nó không phải ở New Haven,
vì vậy chúng tôi đang dùng các lớp

1136
00:53:18,850 --> 00:53:20,310
New Haven cho bài giảng hôm thứ Hai.

1137
00:53:20,310 --> 00:53:22,550
Tất cả mọi thứ sẽ được quay
và truyền trực tiếp như bình thường,

1138
00:53:22,550 --> 00:53:24,900
nhưng chúng ta hãy kết thúc ngày hôm nay
với một clip 30 giây

1139
00:53:24,900 --> 00:53:26,910
gọi là "Suy nghĩ sâu"
bởi Daven Farnham, mà

1140
00:53:26,910 --> 00:53:30,850
lấy cảm hứng từ năm ngoái vào thứ Bảy
"Suy nghĩ sâu" Night Live của

1141
00:53:30,850 --> 00:53:35,700
Jack Handy, mà
bây giờ nên có ý nghĩa.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Và bây giờ, "Deep
Suy nghĩ "của Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Bảng băm.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Đúng rồi, đó là nó cho bây giờ.

1147
00:53:47,660 --> 00:53:48,805
Chúng tôi sẽ gặp bạn vào tuần tới.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Để nhìn thấy nó trong hành động.

1150
00:53:56,680 --> 00:53:58,304
Vì vậy, chúng ta hãy nhìn vào đó ngay bây giờ.

1151
00:53:58,304 --> 00:53:59,890
Vì vậy, ở đây, chúng tôi có một mảng được phân loại.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, bạn có thể đi trước và khởi động lại
này chỉ cho một thứ hai, xin vui lòng.

1153
00:54:04,860 --> 00:54:08,562
Tất cả các quyền, máy ảnh đang lăn, vì vậy
hành động bất cứ khi nào bạn đã sẵn sàng, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Được rồi, vì vậy những gì chúng tôi
có ở đây là một mảng được phân loại.

1155
00:54:11,020 --> 00:54:13,960
Và tôi đã có màu tất cả các yếu tố
màu đỏ để chỉ ra rằng đó là, trên thực tế,

1156
00:54:13,960 --> 00:54:14,460
không được phân loại.

1157
00:54:14,460 --> 00:54:17,960
Vì vậy, nhớ lại rằng điều đầu tiên chúng tôi làm
là chúng tôi sắp xếp một nửa còn lại của mảng.

1158
00:54:17,960 --> 00:54:20,630
Sau đó, chúng tôi sắp xếp quyền
một nửa của mảng.

1159
00:54:20,630 --> 00:54:22,830
Và ya-da, ya-da, ya-da,
chúng tôi kết hợp chúng lại với nhau.

1160
00:54:22,830 --> 00:54:24,520
Và chúng tôi có một mảng hoàn toàn được sắp xếp.

1161
00:54:24,520 --> 00:54:25,360
Vì vậy, đó là cách hợp nhất phân loại hoạt động.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, whoa, whoa,
cắt, cắt, cắt, cắt.

1163
00:54:27,109 --> 00:54:30,130
Doug, bạn không thể chỉ ya-da, ya-da,
ya-da, theo cách của bạn thông qua sắp xếp hợp nhất.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Tôi chỉ cần làm.

1165
00:54:31,970 --> 00:54:32,832
Tốt rồi.

1166
00:54:32,832 --> 00:54:33,540
Chúng tôi đang tốt để đi.

1167
00:54:33,540 --> 00:54:34,760
Hãy chỉ giữ cán.

1168
00:54:34,760 --> 00:54:35,380
Vậy thì,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Bạn phải giải thích
nó đầy đủ hơn đó.

1170
00:54:37,800 --> 00:54:39,999
Đó chỉ là không đủ.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, chúng tôi không
cần phải quay trở lại một.

1172
00:54:41,790 --> 00:54:42,350
Tốt rồi.

1173
00:54:42,350 --> 00:54:45,690
Vì vậy, dù sao, nếu chúng ta tiếp tục với merge--
Ian, chúng ta đang ở giữa tiến trình quay phim.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Tôi biết.

1175
00:54:46,612 --> 00:54:49,320
Và chúng ta không thể chỉ ya-da, ya-da,
ya-da, thông qua toàn bộ quá trình.

1176
00:54:49,320 --> 00:54:52,200
Bạn phải giải thích như thế nào
Hai bên nhận sáp nhập với nhau.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Nhưng chúng tôi đã đã
giải thích làm thế nào hai sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Bạn vừa thể hiện
họ một mảng kết hợp.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Họ biết quá trình này.

1180
00:54:56,486 --> 00:54:57,172
Họ ổn.

1181
00:54:57,172 --> 00:54:58,380
Chúng tôi đã đi qua nó mười lần.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Bạn chỉ cần bỏ qua ngay trên nó.

1183
00:55:00,330 --> 00:55:03,360
Chúng ta sẽ trở lại một, bạn
không có thể bạn ya-da, ya-da trên nó.

1184
00:55:03,360 --> 00:55:05,480
Được rồi, trở lại một.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Tôi phải quay trở lại
qua tất cả các slide?

1186
00:55:07,833 --> 00:55:08,332
Chúa tôi.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Nó giống như là lần thứ sáu, Ian.

1189
00:55:13,004 --> 00:55:13,940
Tốt rồi.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Tất cả các quyền.

1191
00:55:15,200 --> 00:55:16,590
Bạn sẵn sàng chưa?

1192
00:55:16,590 --> 00:55:17,400
Tuyệt vời.

1193
00:55:17,400 --> 00:55:18,950
Hành động.