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

2
00:00:10,900 --> 00:00:15,860
>> HOPARLÖR 1: Bütün sağ, belə ki, bu deyil
CS50 Bu həftə beş sonu.

3
00:00:15,860 --> 00:00:19,220
Və son dəfə xatırlayıram, biz
açılmış meraklısı data baxaraq

4
00:00:19,220 --> 00:00:22,310
həll başladı strukturları
təqdim başladı problemlər,

5
00:00:22,310 --> 00:00:25,640
yeni problemlər, lakin bu əsas
Threading cür idi ki, biz

6
00:00:25,640 --> 00:00:27,940
node node etməyə başladı.

7
00:00:27,940 --> 00:00:30,085
Belə ki, əlbəttə, bu
bir story bağlı siyahı.

8
00:00:30,085 --> 00:00:31,960
Və story, bağlı
Mən yalnız bir var deməkdir

9
00:00:31,960 --> 00:00:33,380
bu qovşaqlarının hər arasında mövzu.

10
00:00:33,380 --> 00:00:35,890
Siz meraklısı edə bilərsiniz çıxır
ikiqat bağlı siyahıları kimi şeylər

11
00:00:35,890 --> 00:00:38,470
bir arrow var qovuşdurmağımız
hər iki istiqamətdə gedir ki,

12
00:00:38,470 --> 00:00:40,320
müəyyən verim ilə kömək edə bilər.

13
00:00:40,320 --> 00:00:42,000
Amma bu problemi həll?

14
00:00:42,000 --> 00:00:43,500
Bu nədir problem həll etdi?

15
00:00:43,500 --> 00:00:46,620
Biz bazar ertəsi Niyə qayğı idi?

16
00:00:46,620 --> 00:00:49,820
Niyə, nəzəri, biz bazar ertəsi qayğı idi?

17
00:00:49,820 --> 00:00:50,630
O nə edir?

18
00:00:50,630 --> 00:00:51,950
>> Auditoriya: Biz dinamik boyutlandır bilər.

19
00:00:51,950 --> 00:00:53,740
>> HOPARLÖR 1: OK, biz belə
dinamik boyutlandır.

20
00:00:53,740 --> 00:00:54,710
Yaxşı Siz də aparılır.

21
00:00:54,710 --> 00:00:57,560
Belə ki, dinamik bu boyutlandır bilər
data structure, bir sıra halbuki,

22
00:00:57,560 --> 00:01:00,760
Xatırladaq ki, bir bilmək lazımdır
priori nə qədər yer istədiyiniz

23
00:01:00,760 --> 00:01:03,870
və bir az daha lazımdır, əgər
space, siz uğurlar cür istəyirik.

24
00:01:03,870 --> 00:01:05,560
Siz yeni bir sıra yaratmaq lazımdır.

25
00:01:05,560 --> 00:01:07,893
Siz bütün hərəkət var sizin
bir digər məlumatlar,

26
00:01:07,893 --> 00:01:10,600
nəticədə köhnə sıra pulsuz
Siz, sonra davam edin.

27
00:01:10,600 --> 00:01:13,891
Hansı yalnız çox bahalı hiss və çox
səmərəsiz və həqiqətən ola bilər.

28
00:01:13,891 --> 00:01:14,890
Amma bu, bütün yaxşı deyil.

29
00:01:14,890 --> 00:01:18,180
Biz qiymət ödəmək, bir nə idi
daha aydın qiymətləri biz

30
00:01:18,180 --> 00:01:20,550
bir bağlı siyahı istifadə edərək ödəmək?

31
00:01:20,550 --> 00:01:22,825
>> Auditoriya: Biz istifadə etmək lazımdır
hər biri üçün ikiqat yer.

32
00:01:22,825 --> 00:01:25,200
HOPARLÖR 1: Bəli, belə ki, biz lazımdır
ən azı iki dəfə çox yer kimi.

33
00:01:25,200 --> 00:01:27,700
Əslində, mən həyata bu şəkil nin
hətta bir az yanlış,

34
00:01:27,700 --> 00:01:32,200
çünki müasir bir çox CS50 IDE haqqında
kompüter, bir pointer və ya bir ünvan

35
00:01:32,200 --> 00:01:33,700
Əslində dörd bytes deyil.

36
00:01:33,700 --> 00:01:36,090
Bu, çox tez-tez bu var
gün səkkiz bytes olan

37
00:01:36,090 --> 00:01:38,530
alt deməkdir ən
əslində orada düzbucaqlı

38
00:01:38,530 --> 00:01:40,900
iki dəfə kimi növ
Mən tərtib etdik nə kimi böyük,

39
00:01:40,900 --> 00:01:44,409
siz üç dəfə kimi istifadə edirik deməkdir
biz başqa ola bilər kimi çox yer.

40
00:01:44,409 --> 00:01:46,700
İndi eyni zamanda, biz istəyirik
hələ bayt söhbət, sağ?

41
00:01:46,700 --> 00:01:49,140
Biz mütləq söhbət deyilik
megabayt və ya gigabayt,

42
00:01:49,140 --> 00:01:51,000
Bu məlumatlara halda strukturları böyük almaq.

43
00:01:51,000 --> 00:01:54,510
>> Və belə ki, bu gün biz hesab başlamaq
biz data araşdırmaq bilər necə

44
00:01:54,510 --> 00:01:57,310
daha səmərəli əgər
fakt data daha böyük olur.

45
00:01:57,310 --> 00:02:00,360
Amma canonicalize edək
ilk əməliyyatları

46
00:02:00,360 --> 00:02:02,460
bu edə bilərsiniz ki,
data strukturları növləri.

47
00:02:02,460 --> 00:02:04,790
Bir bağlı kimi belə bir şey
siyahısı, ümumiyyətlə dəstəkləyir

48
00:02:04,790 --> 00:02:07,514
əməliyyatlar silmək istəyirəm,
daxil edin və axtarış.

49
00:02:07,514 --> 00:02:08,639
Və mən ki, nə deməkdir?

50
00:02:08,639 --> 00:02:11,222
Bu yalnız, adətən deməkdir
insanlar bağlı siyahı istifadə əgər,

51
00:02:11,222 --> 00:02:14,287
onlar və ya başqası həyata keçirdi
sil, insert kimi funksiyaları,

52
00:02:14,287 --> 00:02:16,120
və axtarış, siz belə
həqiqətən bir şey

53
00:02:16,120 --> 00:02:18,030
data strukturu ilə faydalı.

54
00:02:18,030 --> 00:02:20,760
Belə ki, tez nəzər salaq
biz həyata bilər necə

55
00:02:20,760 --> 00:02:24,530
bir bağlı siyahı bəzi kodu kimi belə.

56
00:02:24,530 --> 00:02:27,885
>> Belə ki, bu yalnız bir C kodu,
belə tam bir proqramdır

57
00:02:27,885 --> 00:02:29,260
Mən, həqiqətən, tez çırpılmış ki.

58
00:02:29,260 --> 00:02:32,300
Bu paylanmasında online deyil
kodu, bu, həqiqətən run deyil, çünki.

59
00:02:32,300 --> 00:02:33,790
Amma yalnız var fark
Şərh dedi,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, bir şey var
var, orada bir şey dot dot dot.

61
00:02:36,130 --> 00:02:38,410
Və yalnız baxaq
şirəli hissələri nə.

62
00:02:38,410 --> 00:02:40,790
Belə ki, xətt üç,
bu artıq Xatırladaq ki,

63
00:02:40,790 --> 00:02:45,960
Biz son bir node elan təklif
vaxt, o düzbucaqlı obyektlərindən biri.

64
00:02:45,960 --> 00:02:48,790
Bu, biz n zəng edəcəyik int var
lakin biz bir şey zəng edə bilər,

65
00:02:48,790 --> 00:02:51,920
və sonra bir struct node ulduz növbəti çağırıb.

66
00:02:51,920 --> 00:02:55,520
Və yalnız, ikinci aydın olmaq
line line altı on ki, nədir?

67
00:02:55,520 --> 00:02:57,930
Bu, bizim üçün nə edir?

68
00:02:57,930 --> 00:03:01,044
Bu, əlbəttə, daha görünür, çünki
bizim adi dəyişənlər çox sirli.

69
00:03:01,044 --> 00:03:02,740
>> Auditoriya: Bu artıq hərəkət edir.

70
00:03:02,740 --> 00:03:04,650
>> HOPARLÖR 1: Bu artıq hərəkət edir.

71
00:03:04,650 --> 00:03:08,580
Və daha dəqiq olmalıdır
Bu ünvan saxlamaq olacaq

72
00:03:08,580 --> 00:03:11,582
üçün nəzərdə node
semantically yanında, sağ?

73
00:03:11,582 --> 00:03:13,540
Belə ki, etmək niyyətində deyil
mütləq bir şey hərəkət.

74
00:03:13,540 --> 00:03:15,290
Bu, sadəcə olacaq
olan bir dəyər saxlamaq

75
00:03:15,290 --> 00:03:17,170
Ünvan olacaq
bəzi digər node,

76
00:03:17,170 --> 00:03:20,810
biz struct bildirib etdik niyə və ki
node ulduz, star belirten

77
00:03:20,810 --> 00:03:22,370
bir göstərici və ya ünvanı.

78
00:03:22,370 --> 00:03:26,390
OK, belə ki, indi biz güman əgər
bizə mövcud bu N, və edək

79
00:03:26,390 --> 00:03:29,490
başqasının var ki, güman
integers bütün dəstə daxil

80
00:03:29,490 --> 00:03:30,400
bir bağlı siyahısına daxil.

81
00:03:30,400 --> 00:03:35,640
Və bağlı siyahısı
bir nöqtədə ilə işarə

82
00:03:35,640 --> 00:03:39,040
bir dəyişən adlı siyahısı
bir parametri kimi burada keçdi,

83
00:03:39,040 --> 00:03:43,120
necə xətti haqqında getmək yoxdur
14 axtarış həyata?

84
00:03:43,120 --> 00:03:45,990
Başqa sözlə, mən həyata edirəm
kimin məqsədi həyat funksiyası

85
00:03:45,990 --> 00:03:48,889
sonra bir int və almaq üçün
bir bağlı siyahı başlayan,

86
00:03:48,889 --> 00:03:50,430
ki bağlı siyahı bir göstəricisidir.

87
00:03:50,430 --> 00:03:52,992
Ilk kimi, mən David kim hesab edirəm ki,
könüllü, Bazar ertəsi günü idi

88
00:03:52,992 --> 00:03:54,700
O işarə edildi
bütün bağlı siyahı,

89
00:03:54,700 --> 00:03:57,820
biz keçən etdiyiniz kimi bu
David burada arqument kimi.

90
00:03:57,820 --> 00:03:59,990
Necə ki, biz bu siyahı traversing haqqında getmək yoxdur?

91
00:03:59,990 --> 00:04:04,640
Bəli, bu çıxır ki, baxmayaraq ki,
göstəricilərinə, bizə indi nisbətən yeni

92
00:04:04,640 --> 00:04:07,010
biz nisbətən bunu edə bilərsiniz
straightforwardly.

93
00:04:07,010 --> 00:04:09,500
>> Mən irəli getmək üçün gedirəm və
müvəqqəti dəyişən elan ki,

94
00:04:09,500 --> 00:04:12,364
Konvensiya ilə yalnız gedir
üçün, PTR pointer çağırıb, və ya

95
00:04:12,364 --> 00:04:14,030
lakin siz istədiyiniz bir şey zəng edə bilər.

96
00:04:14,030 --> 00:04:16,470
Mən başlamaq üçün gedirəm
Bu siyahıda başlaması.

97
00:04:16,470 --> 00:04:20,050
Belə ki, siz cür bu hesab edə bilər
Mənə müəllim kimi digər gün,

98
00:04:20,050 --> 00:04:23,580
cür kimsə işarə
könüllü olaraq insanlar arasında.

99
00:04:23,580 --> 00:04:26,470
Belə ki, bir müvəqqəti dəyişən deyiləm
yalnız eyni şey işarə

100
00:04:26,470 --> 00:04:31,390
bizim təsadüfən adlı
könüllü David də işarə etdi.

101
00:04:31,390 --> 00:04:35,440
İndi göstərici isə
null deyil, çünki geri

102
00:04:35,440 --> 00:04:40,350
ki null bəzi xüsusi sentinel dəyəri
siyahı sonunda ayırır

103
00:04:40,350 --> 00:04:44,280
Mən işarə deyiləm isə
son könüllü kimi torpaq

104
00:04:44,280 --> 00:04:47,190
idi nin irəli gedək
və aşağıdakı.

105
00:04:47,190 --> 00:04:51,820
Göstərici Əgər indi cür istəyirəm
biz tələbə ilə nə etmək

106
00:04:51,820 --> 00:04:57,410
quruluşu pointer dot növbəti əgər
bərabərdir pointer dot N bərabərdir olduqca əgər

107
00:04:57,410 --> 00:05:02,290
dəyişən N bərabərdir
qəbul edilmişdir dəlil,

108
00:05:02,290 --> 00:05:05,370
sonra irəli getmək istəyirəm
və doğru qayıtmaq deyirlər.

109
00:05:05,370 --> 00:05:11,020
Mən daxili sayı N gördük
Mənim bağlı siyahı qovşaqlarının biri.

110
00:05:11,020 --> 00:05:13,500
Amma dot artıq
bu çərçivədə işləyir,

111
00:05:13,500 --> 00:05:17,260
pointer, PTR, çünki
həqiqətən bir göstərici, bir ünvan,

112
00:05:17,260 --> 00:05:20,632
Biz, həqiqətən, gözəl edə bilərsiniz
sintaksis nəhayət bir parça istifadə

113
00:05:20,632 --> 00:05:22,590
markalı belə
intuitiv mənada və həqiqətən

114
00:05:22,590 --> 00:05:27,870
getmək deməkdir ki, burada bir arrow istifadə
orada tam ki, ünvanı.

115
00:05:27,870 --> 00:05:30,160
Belə ki, çox oxşar
dot operator ruhu,

116
00:05:30,160 --> 00:05:33,860
lakin pointer bir göstərici deyil, çünki
və faktiki struct özü,

117
00:05:33,860 --> 00:05:35,380
biz yalnız arrow istifadə edin.

118
00:05:35,380 --> 00:05:40,620
>> Belə ki, cari node ki, mən,
müvəqqəti dəyişən işarə edirəm

119
00:05:40,620 --> 00:05:43,060
N, mən nə istəyirəm deyil?

120
00:05:43,060 --> 00:05:45,910
Bəli, mənim insan könüllüləri ilə
biz gün burada idi ki,

121
00:05:45,910 --> 00:05:49,710
Mənim ilk insan bir mən deyil
istəyirik və bəlkə ikinci insan deyil

122
00:05:49,710 --> 00:05:52,660
Mən istəyirəm biri və üçüncü, mən
hərəkət fiziki saxlamaq lazımdır.

123
00:05:52,660 --> 00:05:54,690
Kimi necə bir siyahısını addım edirsiniz?

124
00:05:54,690 --> 00:05:57,470
Biz bir sıra idi, siz
yalnız i plus plus kimi etdi.

125
00:05:57,470 --> 00:06:03,660
Lakin bu halda, bu kifayətdir
növbəti göstərici olur, göstərici yoxdur.

126
00:06:03,660 --> 00:06:07,580
Başqa sözlə, növbəti sahəsində
sol əlində bütün kimi

127
00:06:07,580 --> 00:06:10,880
ki, bazar ertəsi insan könüllü
bəzi digər node qeyd etmək üçün istifadə idi.

128
00:06:10,880 --> 00:06:12,890
Həmin onların növbəti qonşuları idi.

129
00:06:12,890 --> 00:06:17,060
>> Mən bu siyahıda gezinmek üçün istəyirsinizsə Belə ki,
Mən artıq mən bunu plus plus bilməz

130
00:06:17,060 --> 00:06:20,120
Mən əvəzinə demək lazımdır
Mən pointer, gedir

131
00:06:20,120 --> 00:06:24,650
növbəti sahəsində nə bərabər,
növbəti sahəsində, növbəti sahəsində var

132
00:06:24,650 --> 00:06:28,350
o sol əlləri aşağıdakı
biz mərhələ işarə idi ki,

133
00:06:28,350 --> 00:06:30,000
bir sonrakı dəyərlərə.

134
00:06:30,000 --> 00:06:32,590
Mən vasitəsilə almaq əgər
ki, bütün iteration,

135
00:06:32,590 --> 00:06:39,330
və nəhayət, mən olmayan null edib
aşkar N hələ, mən yalnız yalan qayıtmaq.

136
00:06:39,330 --> 00:06:44,100
Belə ki, yenə, biz burada edirik ki, bütün,
bir an əvvəl şəkil kimi,

137
00:06:44,100 --> 00:06:47,840
işarə ilə başlayır
ehtimalla siyahısı başlayan.

138
00:06:47,840 --> 00:06:50,970
Və sonra mən yoxlamaq, dəyəri nə
Mən doqquz bərabər arıyorum?

139
00:06:50,970 --> 00:06:52,650
Əgər belədirsə, mən doğru qayıtmaq və mən bitirdim.

140
00:06:52,650 --> 00:06:56,450
Əgər, əlimi yeniləmə
AKA pointer, qeyd etmək

141
00:06:56,450 --> 00:06:59,540
növbəti Ok'un yeri, və
sonra yanındakı arrow yeri,

142
00:06:59,540 --> 00:07:00,480
və növbəti.

143
00:07:00,480 --> 00:07:03,770
Mən sadəcə bu array vasitəsilə gəzinti edirəm.

144
00:07:03,770 --> 00:07:06,010
>> Belə ki, yenə, kimin umurunda?

145
00:07:06,010 --> 00:07:07,861
Like bu bir tərkib hissəsi nədir?

146
00:07:07,861 --> 00:07:10,360
Yaxşı, biz təqdim ki, xatırlayıram
bir yığın anlayışı olan

147
00:07:10,360 --> 00:07:15,400
bu kimi mücərrəd data insofar yazın
bir C şey, bir CS50 şey deyil,

148
00:07:15,400 --> 00:07:19,430
Bu mücərrəd fikir, bu fikir
bir-birinə üst şeyi yığma

149
00:07:19,430 --> 00:07:21,820
ki, həyata keçirilə bilər
müxtəlif yollarla dəstələri.

150
00:07:21,820 --> 00:07:25,600
Və biz təklif bir yolu idi
bir sıra, və ya bir bağlı siyahısı ilə.

151
00:07:25,600 --> 00:07:29,570
Və bu ki, canonically çıxır
yığını ən azı iki əməliyyatları dəstəkləyir.

152
00:07:29,570 --> 00:07:32,320
Və buzz sözləri, push var
yığını üzərinə bir şey təkan,

153
00:07:32,320 --> 00:07:34,770
yeni tray kimi
yemekhane, və ya pop,

154
00:07:34,770 --> 00:07:39,000
olan topmost aradan qaldırılması deməkdir
yemək yığını tray

155
00:07:39,000 --> 00:07:41,500
zalı, sonra bəlkə bəzi
digər əməliyyatlar həmçinin.

156
00:07:41,500 --> 00:07:45,770
Belə ki, necə biz strukturu müəyyən edə bilər
biz indi bir yığın zəng edirik ki?

157
00:07:45,770 --> 00:07:50,020
>> Bəli, biz zəruri bütün var
deyirəm C. bizim sərəncamında syntax,

158
00:07:50,020 --> 00:07:53,830
Mənə bir növü tərif vermək
bir yığın daxilində struct,

159
00:07:53,830 --> 00:07:58,030
Mən, bir sıra edir demək gedirəm
bütün nömrələri dəstə və sonra ölçüsü.

160
00:07:58,030 --> 00:08:00,930
Belə ki, başqa sözlə, mən istəyirəm
kodu bu həyata keçirilməsi üçün,

161
00:08:00,930 --> 00:08:03,830
Mənə getmək və yalnız cür imkan
bu söyləyərək nə cəlb edir.

162
00:08:03,830 --> 00:08:06,317
Bu deyib ki, mənə vermək
bir sıra var quruluşu,

163
00:08:06,317 --> 00:08:09,400
və mən gücü nə bilmirəm
Mən etdik ki, yəqin bəzi daimi var

164
00:08:09,400 --> 00:08:10,858
başqa müəyyən ki, gözəl var.

165
00:08:10,858 --> 00:08:15,260
Lakin, yalnız bir Güman
iki, üç, dörd, beş.

166
00:08:15,260 --> 00:08:16,700
Belə ki, gücü 5-dir.

167
00:08:16,700 --> 00:08:21,730
Daxilində bu element mənim
strukturu nömrələri adlanacaq.

168
00:08:21,730 --> 00:08:24,020
Və sonra mən bir ehtiyac
digər dəyişən yəqin

169
00:08:24,020 --> 00:08:27,814
əvvəlcə mən gedirəm adlı ölçüsü
sıfır başlanır müəyyən etmək.

170
00:08:27,814 --> 00:08:29,730
Heç bir şey varsa
yığını ölçüsü, sıfır

171
00:08:29,730 --> 00:08:31,420
və nömrələr zibil dəyərlər var.

172
00:08:31,420 --> 00:08:33,450
Mən hələ orada nə heç bir fikrim yoxdur.

173
00:08:33,450 --> 00:08:36,059
>> Mən basmaq istəyirsinizsə Belə ki,
yığını üzərinə bir şey,

174
00:08:36,059 --> 00:08:40,780
Mən funksiyası təkan zəng Güman, və
Mən sayı 50 kimi 50 təkan demək

175
00:08:40,780 --> 00:08:44,090
burada təklif edirəm
Mən bu array onu cəlb?

176
00:08:44,090 --> 00:08:47,124
Beş müxtəlif mümkün cavab var.

177
00:08:47,124 --> 00:08:48,790
Harada sayı 50 basmaq istəyirsiniz?

178
00:08:48,790 --> 00:08:51,899
Burada məqsəd varsa, yenə zəng
funksiyası push, bir dəlil keçmək

179
00:08:51,899 --> 00:08:52,940
50, mən bunu harada qoymaq bilərəm?

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

181
00:08:55,680 --> 00:08:59,052
Beş mümkün var 20% şans
düzgün təxmin.

182
00:08:59,052 --> 00:08:59,896
Bəli?

183
00:08:59,896 --> 00:09:00,740
>> Auditoriya: Far hüququ.

184
00:09:00,740 --> 00:09:01,990
>> HOPARLÖR 1: Far hüququ.

185
00:09:01,990 --> 00:09:08,359
25% şans artıq var
düzgün təxmin.

186
00:09:08,359 --> 00:09:09,650
Belə ki, həqiqətən gözəl olardı.

187
00:09:09,650 --> 00:09:12,770
Konvensiya, mən bir sıra ilə demək lazımdır,
biz ümumiyyətlə, sol başlayacaq

188
00:09:12,770 --> 00:09:14,519
lakin biz, əlbəttə bilər
sağ başlamaq.

189
00:09:14,519 --> 00:09:17,478
Belə ki, burada spoyler Mən olardı
yəqin ki, sol onu cəlb,

190
00:09:17,478 --> 00:09:20,060
yalnız bir normal sıra olduğu kimi
Mən soldan sağa gedən başlamaq.

191
00:09:20,060 --> 00:09:21,780
Amma flip bilər, əgər
hesab, gözəl.

192
00:09:21,780 --> 00:09:23,060
Bu, yalnız şərti deyil.

193
00:09:23,060 --> 00:09:24,880
OK, Mən bir etmək lazımdır
baxmayaraq daha dəyişiklik.

194
00:09:24,880 --> 00:09:27,710
İndi mən bir şey sövq etdik ki,
yığını üzərinə, nə gələn var?

195
00:09:27,710 --> 00:09:29,400
>> Bütün sağ, mən ölçüsü arttırmayı var.

196
00:09:29,400 --> 00:09:32,600
Mənə irəli və yalnız gidelim
sıfır olan bu yeniləmə.

197
00:09:32,600 --> 00:09:35,950
Əvəzinə indi mən gedirəm
dəyəri bir qoymaq üçün.

198
00:09:35,950 --> 00:09:39,460
İndi başqa bir təkan güman
yığını üzərinə sayı 51 kimi.

199
00:09:39,460 --> 00:09:42,680
Bəli, mən bir daha etmək lazımdır
ölçüsü iki qədər dəyişiklik.

200
00:09:42,680 --> 00:09:46,100
Və sonra mən bir daha təkan güman
61 kimi yığını üzərinə sayı,

201
00:09:46,100 --> 00:09:52,530
indi ölçüsü güncellemeniz lazımdır daha bir
vaxtı və ölçüsü kimi dəyər 3 almaq.

202
00:09:52,530 --> 00:09:54,690
İndi pop zəng güman edirlər.

203
00:09:54,690 --> 00:09:57,250
İndi Konvensiya ilə, pop,
bir dəlil deyil.

204
00:09:57,250 --> 00:10:00,430
Bir yığını ilə bütün
tray məcaz point

205
00:10:00,430 --> 00:10:03,450
Siz mülahizə yoxdur ki,
ki, tray almaq getmək, bütün edə bilərsiniz

206
00:10:03,450 --> 00:10:06,330
olan topmost bir pop edir
yığını yalnız çünki.

207
00:10:06,330 --> 00:10:08,010
Yəni bu data structure nə var.

208
00:10:08,010 --> 00:10:12,250
>> Ki məntiqi Belə ki,
pop, nə off gəlir demək?

209
00:10:12,250 --> 00:10:13,080
Belə ki, 61.

210
00:10:13,080 --> 00:10:15,402
Belə ki, həqiqətən, kompüter nə
yaddaş nə edəcək?

211
00:10:15,402 --> 00:10:16,610
Mənim code nə var?

212
00:10:16,610 --> 00:10:20,330
Nə təklif edirəm
biz ekranda dəyişdirmək?

213
00:10:20,330 --> 00:10:23,410
Nə dəyişdirmək lazımdır?

214
00:10:23,410 --> 00:10:24,960
Bağışlayın?

215
00:10:24,960 --> 00:10:26,334
Beləliklə, biz 61 durun.

216
00:10:26,334 --> 00:10:27,500
Beləliklə, mən mütləq bunu edə bilərsiniz.

217
00:10:27,500 --> 00:10:28,640
Mən 61 xilas edə bilər.

218
00:10:28,640 --> 00:10:30,980
Və sonra nə digər
dəyişiklik baş etmək lazımdır?

219
00:10:30,980 --> 00:10:33,160
Size yəqin ki, iki geri getmək üçün var.

220
00:10:33,160 --> 00:10:34,210
Və belə ki, gözəl.

221
00:10:34,210 --> 00:10:36,690
Amma bir dəqiqə, ölçüsü gözləyin
bir an əvvəl üç idi.

222
00:10:36,690 --> 00:10:38,240
Yalnız tez ağlı başında olma çek edək.

223
00:10:38,240 --> 00:10:41,810
Biz necə ki, bilirdinizmi
61 qurtarmaq istəyirdi?

224
00:10:41,810 --> 00:10:42,760
Biz yaratma edirik, çünki.

225
00:10:42,760 --> 00:10:46,450
Və mən bu ikinci əmlak ölçüsü var.

226
00:10:46,450 --> 00:10:48,470
>> Mən, bir dəqiqə gözləyin
həftə iki geri düşüncə

227
00:10:48,470 --> 00:10:51,660
Biz söhbət açılmış zaman
Bu yer sıfır idi Diziler,

228
00:10:51,660 --> 00:10:55,920
Bu yer bir idi, bu yer idi
iki, bu yer üç, dörd,

229
00:10:55,920 --> 00:10:58,460
bu kimi görünür
ölçüsü arasında əlaqələr

230
00:10:58,460 --> 00:11:02,780
və mən istəyirəm element aradan qaldırılması üçün
array yalnız nə ola görünür?

231
00:11:02,780 --> 00:11:05,120
Size minus biridir.

232
00:11:05,120 --> 00:11:07,786
Və belə ki, necə insanlar kimi deyil
biz 61 birinci gəlir bilirik.

233
00:11:07,786 --> 00:11:09,160
Necə kompüter bilmək olacaq?

234
00:11:09,160 --> 00:11:11,701
Zaman kodu harada siz yəqin ki,
ölçüsü minus bir etmək istəyirəm,

235
00:11:11,701 --> 00:11:14,950
Belə ki, üç minus iki, və ki,
biz 61 qurtarmaq istəyirəm deməkdir.

236
00:11:14,950 --> 00:11:18,000
Və sonra biz həqiqətən təkmilləşdirə bilər
ki, ölçüsü belə ölçüsü indi

237
00:11:18,000 --> 00:11:20,300
yalnız iki üç gedir.

238
00:11:20,300 --> 00:11:24,520
Və yalnız xırdaçı olmaq üçün gedirəm
Mən, bitirdim ki, təklif üçün necə?

239
00:11:24,520 --> 00:11:27,660
Siz daxilən təklif
Düzgün Mən 61 qurtarmaq lazımdır.

240
00:11:27,660 --> 00:11:30,700
Amma yox I növ
sort 61 xilas kazanılmış?

241
00:11:30,700 --> 00:11:33,790
Mən səmərəli unuttuysanız
ki, həqiqətən var.

242
00:11:33,790 --> 00:11:37,680
Siz oxumaq sonra əgər, geri pset4 düşünmək
Suclari haqqında məqalə, PDF

243
00:11:37,680 --> 00:11:40,780
biz ki, uşaqlar oxumaq, və ya
pset4 üçün bu həftə oxumaq olacaq.

244
00:11:40,780 --> 00:11:44,300
Bu həqiqətən ilgili Xatırladaq ki
kompüter Suclari bütün fikir.

245
00:11:44,300 --> 00:11:47,820
Hansı bir kompüter ümumiyyətlə yoxdur edir
bir şey olduğu yalnız, unudur

246
00:11:47,820 --> 00:11:51,300
lakin bu getmək və kimi deyil
onu və ya yalnış danışıq üçün cəhd edin

247
00:11:51,300 --> 00:11:54,560
adet sıfır və olanları olanlar bit
və ya digər təsadüfi model

248
00:11:54,560 --> 00:11:56,690
Sizin halda özünüz belə qəsdən yoxdur.

249
00:11:56,690 --> 00:11:58,930
Belə ki, intuisiya idi
sağ, 61 xilas edək.

250
00:11:58,930 --> 00:12:00,650
Lakin əslində, biz narahat yoxdur.

251
00:12:00,650 --> 00:12:04,040
Biz yalnız ki, unutmaq lazımdır
bu, bizim ölçüsü dəyişən var.

252
00:12:04,040 --> 00:12:05,662
>> İndi bu yığını ilə bir problem var.

253
00:12:05,662 --> 00:12:07,620
Mən hər şeyi basmaqla saxlamaq
yığını üzərinə, nə

254
00:12:07,620 --> 00:12:11,167
açıq-aydın baş verəcək
yalnız bir neçə dəqiqə vaxt?

255
00:12:11,167 --> 00:12:12,500
Biz yer tökülmək olacaq.

256
00:12:12,500 --> 00:12:13,580
Və biz nə etməliyəm?

257
00:12:13,580 --> 00:12:14,680
Biz cür berbat edirik.

258
00:12:14,680 --> 00:12:19,000
Bu həyata imkan vermir
istifadə edərək, çünki bizə sıra ölçüsünü

259
00:12:19,000 --> 00:12:21,240
Bu syntax, əgər
həftə iki geri hesab edirəm ki,

260
00:12:21,240 --> 00:12:23,520
Siz bəyan sonra
bir sıra ölçüsü,

261
00:12:23,520 --> 00:12:26,780
biz harada bir mexanizm görmədim
Siz serialın ölçüsünü dəyişə bilərsiniz.

262
00:12:26,780 --> 00:12:29,020
Həqiqətən C xüsusiyyət yoxdur.

263
00:12:29,020 --> 00:12:32,524
Desəniz mənə beş vermək
Nths, onlara zəng nömrələri,

264
00:12:32,524 --> 00:12:33,940
ki, siz onu almaq olacaq bütün var.

265
00:12:33,940 --> 00:12:38,790
Beləliklə, biz Bazar ertəsi kimi indi var
həll ifadə etmək qabiliyyəti

266
00:12:38,790 --> 00:12:42,480
baxmayaraq ki, biz yalnız çimdik lazımdır
Bizim yığını müəyyən

267
00:12:42,480 --> 00:12:46,840
bəzi ağır kodlu array ola,
lakin yalnız bir ünvan saxlamaq üçün.

268
00:12:46,840 --> 00:12:47,890
>> İndi niyə bu?

269
00:12:47,890 --> 00:12:51,690
İndi biz yalnız rahat olmalıdır
fakt mənim proqram çalışır ki,

270
00:12:51,690 --> 00:12:53,730
Mən güman gedirəm
insan soruşmaq lazımdır,

271
00:12:53,730 --> 00:12:55,110
neçə ədəd saxlamaq istəyirsiniz?

272
00:12:55,110 --> 00:12:56,776
Belə ki, giriş bir yerdən gəlmək var.

273
00:12:56,776 --> 00:12:59,140
Amma bir dəfə
sayı, sonra mən yalnız bilərsiniz

274
00:12:59,140 --> 00:13:02,470
vermək fəaliyyət nə istifadə
Mənə yaddaş yığın?

275
00:13:02,470 --> 00:13:03,580
Mən malloc istifadə edə bilərsiniz.

276
00:13:03,580 --> 00:13:06,710
Mən hər hansı bir sayı demək olar
bytes geri bu Nths üçün istəyirəm.

277
00:13:06,710 --> 00:13:10,910
Və bütün nömrələri saxlamaq üçün
bu struct daxilində burada dəyişən

278
00:13:10,910 --> 00:13:13,480
nə olmalıdır?

279
00:13:13,480 --> 00:13:18,440
Nə həqiqətən gider
Bu ssenari nömrələri?

280
00:13:18,440 --> 00:13:21,300
Bəli, ilk bir göstərici
yaddaş ki, yığın byte,

281
00:13:21,300 --> 00:13:24,940
və ya daha çox xüsusi, ünvan
o bayt ilk.

282
00:13:24,940 --> 00:13:27,300
Bu bir, əgər Fərq etməz
byte və ya bir milyard bytes,

283
00:13:27,300 --> 00:13:28,890
Mən ilk haqqında qayğı lazımdır.

284
00:13:28,890 --> 00:13:31,530
Çünki nə malloc zəmanətləri və
Mənim əməliyyat sistemi zəmanət,

285
00:13:31,530 --> 00:13:34,170
ki, yaddaş I yığın
almaq, bu bitişik olacaq.

286
00:13:34,170 --> 00:13:35,378
Boşluqlar var olacaq deyil.

287
00:13:35,378 --> 00:13:38,576
Mən 50 xahiş etdik Belə ki
bytes və ya 1000 bytes,

288
00:13:38,576 --> 00:13:40,450
onlar bütün olacaq
geri geri geri.

289
00:13:40,450 --> 00:13:44,500
Və belə uzun mən necə böyük xatırlayıram
qədər mən bilmək lazımdır bütün istədi

290
00:13:44,500 --> 00:13:46,230
ilk ünvan.

291
00:13:46,230 --> 00:13:48,660
>> Belə ki, indi biz kodu imkanı var.

292
00:13:48,660 --> 00:13:51,280
Olsa da, bu, bizi almaq olacaq
çox vaxt bu qədər yazmaq

293
00:13:51,280 --> 00:13:55,900
indi ki, yaddaş təkrar bölüşdürə bilər
yalnız orada fərqli bir ünvan saxlanılması

294
00:13:55,900 --> 00:13:59,060
biz hətta daha böyük və ya istəyirsinizsə
yaddaş kiçik bir yığın.

295
00:13:59,060 --> 00:14:00,170
Belə ki, burada bir ticarət off.

296
00:14:00,170 --> 00:14:01,360
İndi biz dinamizm almaq.

297
00:14:01,360 --> 00:14:03,350
Biz hələ var
contiguousness Mən iddia edirəm.

298
00:14:03,350 --> 00:14:05,881
Malloc bizə verəcək, çünki
yaddaş bitişik yığın.

299
00:14:05,881 --> 00:14:08,630
Amma bu bir ağrı olacaq
bizim üçün boyun, proqramçı,

300
00:14:08,630 --> 00:14:09,770
həqiqətən kod.

301
00:14:09,770 --> 00:14:10,730
Bu, yalnız daha çox iş var.

302
00:14:10,730 --> 00:14:13,930
Biz nə yaxın kodu lazımdır
Yalnız bir an əvvəl həyata tarpıltı.

303
00:14:13,930 --> 00:14:16,120
Çox doable, lakin bu mürəkkəbliyi edər.

304
00:14:16,120 --> 00:14:19,520
Və belə geliştirici zaman, proqramçı
vaxt başqa bir resurs deyil

305
00:14:19,520 --> 00:14:22,520
biz sərf etmək lazımdır bilər ki,
bir müddət yeni funksiyalar almaq üçün.

306
00:14:22,520 --> 00:14:24,020
Və sonra əlbəttə bir sıra var.

307
00:14:24,020 --> 00:14:26,227
Biz bu girməyəcəyəm
çox ətraflı bir.

308
00:14:26,227 --> 00:14:27,560
Amma bu ruhunda çox oxşar.

309
00:14:27,560 --> 00:14:31,220
Mən bir sıra həyata və bilər
müvafiq əməliyyatlar,

310
00:14:31,220 --> 00:14:35,660
enqueue və ya dequeue, əlavə və ya aradan qaldırılması kimi,
Bu, deyərək bir meraklısı yoldur

311
00:14:35,660 --> 00:14:38,100
enqueue və ya dequeue kimi edir.

312
00:14:38,100 --> 00:14:41,170
Mən yalnız özümü bir struct verə bilər
ki, yenə bir sıra nin sıra var,

313
00:14:41,170 --> 00:14:44,000
ki, yenə bir ölçüsü var,
amma niyə indi lazımdır

314
00:14:44,000 --> 00:14:46,940
bir sıra qarşısında takip?

315
00:14:46,940 --> 00:14:50,630
Mən bilmək lazım deyil
Mənim yığını qarşısında.

316
00:14:50,630 --> 00:14:53,570
Yaxşı, əgər mən yenə bir
Sıraya yalnız ağır edək

317
00:14:53,570 --> 00:14:57,870
Beş kimi olan kimi kod
burada potensial da integers.

318
00:14:57,870 --> 00:15:00,940
Belə ki, bu sıfır, bir, iki, üç, dörd edir.

319
00:15:00,940 --> 00:15:03,430
Bu olacaq
yenidən çağırıb nömrələri.

320
00:15:03,430 --> 00:15:06,940
Bu size adlanacaq.

321
00:15:06,940 --> 00:15:10,056
>> Niyə kifayət deyil
yalnız ölçüsü var?

322
00:15:10,056 --> 00:15:11,680
Yaxşı, o eyni nömrələr təkan edək.

323
00:15:11,680 --> 00:15:14,220
Mən enqueued, və ya basdı pushed--.

324
00:15:14,220 --> 00:15:20,150
İndi sonra 50 enqueue və lazımdır
51, sonra 61, və dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Belə ki, enqueue var.

326
00:15:21,070 --> 00:15:23,176
Mən sonra 61, sonra 50, 51 enqueued.

327
00:15:23,176 --> 00:15:25,050
Və eyni görünür
indiyə qədər bir yığını,

328
00:15:25,050 --> 00:15:27,190
istisna olmaqla, mən bir dəyişiklik etmək lazımdır.

329
00:15:27,190 --> 00:15:33,680
Bu ölçüsü güncellemeniz lazımdır, belə ki, mən getmək
İndi üç iki bir sıfırdan.

330
00:15:33,680 --> 00:15:35,760
Necə dequeue edirsiniz?

331
00:15:35,760 --> 00:15:36,890
Nə dequeue olur?

332
00:15:36,890 --> 00:15:41,950
Kim ilk bu siyahı off gəlmək lazımdır
Apple Store xətt var, əgər?

333
00:15:41,950 --> 00:15:42,780
Belə ki, 50.

334
00:15:42,780 --> 00:15:44,700
Belə ki, bu cür trickier bu vaxt var.

335
00:15:44,700 --> 00:15:47,880
Son dəfə isə bu super idi
asan yalnız, ölçüsü minus bir etmək

336
00:15:47,880 --> 00:15:51,440
Mən səmərəli mənim serialın sonuna almaq
ədəd olduğu, bu 61 rədd et.

337
00:15:51,440 --> 00:15:52,920
Amma 61 çıxarmaq istəmirəm.

338
00:15:52,920 --> 00:15:55,030
Mən 50 etmək istəyən
5:00 AM var idi

339
00:15:55,030 --> 00:15:56,790
üçün sıraya girdi
Yeni iPhone və ya etajer.

340
00:15:56,790 --> 00:16:01,200
Və mən, 50 qurtarmaq üçün
sağ, bunu edə bilməz?

341
00:16:01,200 --> 00:16:02,547
Mən 50 silmək olar.

342
00:16:02,547 --> 00:16:04,380
Amma biz yalnız biz bildirib
belə anal olmaq yoxdur

343
00:16:04,380 --> 00:16:06,330
kimi danışıq və ya məlumat gizlətmək.

344
00:16:06,330 --> 00:16:08,090
Olduğu Biz yalnız unuda bilər.

345
00:16:08,090 --> 00:16:12,330
>> Amma indi mənim ölçüsünü dəyişdirmək əgər
iki, bu kifayət qədər məlumat var

346
00:16:12,330 --> 00:16:15,711
Mənim növbə gedir nə bilirik?

347
00:16:15,711 --> 00:16:16,680
Həqiqətən.

348
00:16:16,680 --> 00:16:19,830
Mənim ölçüsü, iki Like lakin
queue harada başlayır,

349
00:16:19,830 --> 00:16:22,980
xüsusilə Mən hələ varsa
yaddaş həmin nömrələri.

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

351
00:16:24,260 --> 00:16:27,090
Belə ki, xatırlamaq lazımdır
İndi ön olduğu.

352
00:16:27,090 --> 00:16:29,630
Və mən qədər təklif
orada biz yalnız çağırıb lazımdır

353
00:16:29,630 --> 00:16:33,729
Onun ilkin Nth ön,
dəyəri nə olmalıdır?

354
00:16:33,729 --> 00:16:35,270
Zero siyahı yalnız başlanğıcıdır.

355
00:16:35,270 --> 00:16:40,876
Amma indi əlavə decrementing üçün
ölçüsü, biz yalnız ön arttırmayı.

356
00:16:40,876 --> 00:16:42,000
İndi burada bir problem var.

357
00:16:42,000 --> 00:16:43,030
Belə ki, davam bir.

358
00:16:43,030 --> 00:16:47,520
Bu sayı düşünək
kimi 121, 124, sonra dammit,

359
00:16:47,520 --> 00:16:48,610
Mən kosmik həyata deyiləm.

360
00:16:48,610 --> 00:16:50,390
Amma deyiləm, bir dəqiqə gözləyin.

361
00:16:50,390 --> 00:16:55,630
Hekayə bu nöqtədə, belə ki,
size bir iki Güman,

362
00:16:55,630 --> 00:17:00,370
üç, dörd, belə ki, güman
ölçüsü, ön biridir, dörd

363
00:17:00,370 --> 00:17:01,621
belə 51 qarşısında deyil.

364
00:17:01,621 --> 00:17:04,329
Mən burada bir sıra qoymaq istəyirəm,
lakin, dammit, mən kosmik həyata deyiləm.

365
00:17:04,329 --> 00:17:06,710
Amma sağ, həqiqətən deyiləm?

366
00:17:06,710 --> 00:17:11,192
Mən harada qoymaq bilər
171 kimi əlavə dəyər?

367
00:17:11,192 --> 00:17:13,400
Bəli, mən biləcəyi yalnız cür
sağ, üzərində geri getmək?

368
00:17:13,400 --> 00:17:18,161
Və sonra 50 silmək, və ya
yalnız 171 ilə üzerine.

369
00:17:18,161 --> 00:17:20,410
Və niyə merak edirsinizsə
Bizim nömrələri, belə ki, təsadüfi var

370
00:17:20,410 --> 00:17:24,150
Bu adətən kompüter alınır
CS50 sonra Harvard elm kursları.

371
00:17:24,150 --> 00:17:27,510
Amma yaxşı bir optimallaşdırma idi,
İndi, çünki mən yer israf deyiləm.

372
00:17:27,510 --> 00:17:30,750
Mən hələ yadda var
necə böyük bu şey ümumi edir.

373
00:17:30,750 --> 00:17:31,500
Bu beş ümumi var.

374
00:17:31,500 --> 00:17:33,375
Mən istəmirəm, çünki
51 yadda başlayın.

375
00:17:33,375 --> 00:17:36,260
Belə ki, indi mən hələ kosmik həyata am,
belə ki, eyni problem əvvəlki kimi.

376
00:17:36,260 --> 00:17:39,140
Amma necə indi görə bilərsiniz
Sizin kodu, yəqin ki,

377
00:17:39,140 --> 00:17:41,910
bir az daha yazmaq lazımdır
mürəkkəbliyi baş etmək üçün.

378
00:17:41,910 --> 00:17:44,510
Və əslində, nə operator
C yəqin ki, imkan verir ki,

379
00:17:44,510 --> 00:17:48,110
Siz magically bu circularity edirsiniz?

380
00:17:48,110 --> 00:17:50,160
Bəli modulo operator,
faiz işarəsi.

381
00:17:50,160 --> 00:17:53,160
Belə ki, bir sıra haqqında sərin cür nə,
biz rəsm serialların saxlamaq, baxmayaraq ki,

382
00:17:53,160 --> 00:17:56,520
bu kimi düz xətləri kimi, əgər
cür Eğme kimi bu barədə düşünmək

383
00:17:56,520 --> 00:18:00,341
ətrafında bir dairə kimi, sonra yalnız
daxilən bu cür əqli işləri

384
00:18:00,341 --> 00:18:01,590
Mən daha çox pakizə bir az düşünmək.

385
00:18:01,590 --> 00:18:05,190
Siz hələ həyata keçirmək olardı
kodu ki, ruhi model.

386
00:18:05,190 --> 00:18:07,550
Belə ki, çətin,
nəticədə, həyata keçirmək üçün

387
00:18:07,550 --> 00:18:12,430
lakin biz hələ deyil, size-- itirmək
Bunu halda qabiliyyəti, boyutlandır.

388
00:18:12,430 --> 00:18:15,310
>> Biz serialın qurtarmaq üçün var, biz
bir göstərici ilə əvəz,

389
00:18:15,310 --> 00:18:20,010
və sonra bir yerdə mənim kodu I var
bir həqiqətən yaratmaq üçün fəaliyyət nə zəng

390
00:18:20,010 --> 00:18:23,720
array adlı nömrələri?

391
00:18:23,720 --> 00:18:26,190
Malloc, və ya bəzi oxşar
funksiyası, dəqiq.

392
00:18:26,190 --> 00:18:30,481
Bacalar və ya sıralarında hər hansı bir sual.

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

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

395
00:18:33,657 --> 00:18:34,240
Yaxşı sualdır.

396
00:18:34,240 --> 00:18:35,830
Nə modulo burada istifadə edir.

397
00:18:35,830 --> 00:18:38,520
Belə ki, ümumiyyətlə, istifadə edərkən
mod, siz bunu

398
00:18:38,520 --> 00:18:40,620
ölçüsü ilə
bütün data structure.

399
00:18:40,620 --> 00:18:44,120
Belə ki, bir şey beş və ya gücü, əgər kimi
daimi var, yəqin ki, iştirak edir.

400
00:18:44,120 --> 00:18:47,100
Amma yalnız modulo beş edir
yəqin ki, kifayət qədər deyil

401
00:18:47,100 --> 00:18:51,380
Biz bilmək lazımdır, çünki biz nə
burada və ya burada və ya burada ətrafında kesmek.

402
00:18:51,380 --> 00:18:54,160
Beləliklə, siz yəqin ki, həmçinin istəyirik
cəlb etmək istəyirəm olacaq

403
00:18:54,160 --> 00:18:57,220
şey ölçüsü, və ya
eləcə də ön dəyişən.

404
00:18:57,220 --> 00:19:00,140
Belə ki, yalnız bu nisbətən var
sadə hesab ifadə edərək,

405
00:19:00,140 --> 00:19:02,000
lakin modulo əsas tərkib hissəsi olacaq.

406
00:19:02,000 --> 00:19:03,330
>> Belə ki, qısa film olacaq əgər.

407
00:19:03,330 --> 00:19:05,780
Bir animasiya ki, bəzi
başqa universitetdə insanlar

408
00:19:05,780 --> 00:19:08,060
biz birlikdə qoymaq
Bu müzakirə üçün uyğunlaşdırılmışdır.

409
00:19:08,060 --> 00:19:12,630
Bu Jack öyrənmək daxildir
sıralarında və stats haqqında faktlar.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Bir zamanlar,
Jack adlı bir oğlan var idi.

412
00:19:21,890 --> 00:19:25,330
Bu dostlar edilməsi gələndə,
Jack bir bacarıq yox idi.

413
00:19:25,330 --> 00:19:28,220
Belə ki, Jack danışmaq üçün getdi
ən məşhur oğlan bilirdi.

414
00:19:28,220 --> 00:19:30,920
O, Lou getdi və mən nə etməliyəm, xahiş?

415
00:19:30,920 --> 00:19:33,400
Lou yoldaşı gördüm ki,
həqiqətən çətin idi.

416
00:19:33,400 --> 00:19:36,050
Bəli, o, yalnız başladı
Siz geyimli etdiyiniz necə baxmaq.

417
00:19:36,050 --> 00:19:38,680
Əgər hər hansı bir paltar yoxdur
fərqli bir göz ilə?

418
00:19:38,680 --> 00:19:39,660
Bəli, Jack bildirib.

419
00:19:39,660 --> 00:19:40,840
Mən əminəm ki, yoxdur.

420
00:19:40,840 --> 00:19:43,320
Evimə gəlin və
Mən sizə onlara göstərmək lazımdır.

421
00:19:43,320 --> 00:19:44,550
Belə ki, onlar Jack çıxdı.

422
00:19:44,550 --> 00:19:47,520
Və Jack Lou qutusu göstərdi
o, bütün köynək saxlanılır

423
00:19:47,520 --> 00:19:49,260
və onun şalvar və onun corab.

424
00:19:49,260 --> 00:19:52,290
Lou Mən görmək olduğunu ifadə edərək,
bir qalaq bütün paltar.

425
00:19:52,290 --> 00:19:54,870
Niyə bəzi geymək deyil
biraz dəfə başqaları?

426
00:19:54,870 --> 00:19:58,020
>> Jack, dedi yaxşı, mən
, paltar və corab aradan qaldırılması

427
00:19:58,020 --> 00:20:00,780
Mən onları yumaq və qoymaq
onlara üz qutusuna.

428
00:20:00,780 --> 00:20:03,210
Sonra gələn gəlir
səhər və mən hop.

429
00:20:03,210 --> 00:20:06,380
Mən qutusu getmək və almaq
üst off mənim paltar.

430
00:20:06,380 --> 00:20:09,070
Lou tez həyata
Jack ilə problem.

431
00:20:09,070 --> 00:20:12,080
O, paltar, CD saxlanılır
və yığını kitablar.

432
00:20:12,080 --> 00:20:14,420
O çatdıqda
bir şey oxumaq və ya geymək,

433
00:20:14,420 --> 00:20:17,100
O top kitab və ya alt seçmək istədiyiniz.

434
00:20:17,100 --> 00:20:19,500
Sonra o, görülən zaman, o,
sağ geri qoymaq olardı.

435
00:20:19,500 --> 00:20:21,970
Geri yığını üst, getmək olardı.

436
00:20:21,970 --> 00:20:24,460
Mən həll bilirik,
bir zəfər Loud bildirib.

437
00:20:24,460 --> 00:20:27,090
Siz öyrənmək lazımdır
bir sıra istifadə edərək başlayın.

438
00:20:27,090 --> 00:20:29,870
Lou Jack paltar götürüb
gizli onlara asdı.

439
00:20:29,870 --> 00:20:32,710
O, boşaldılmış zaman
box, o, yalnız onu tossed.

440
00:20:32,710 --> 00:20:36,500
>> Sonra o, Jack sonunda keçdiyini ifadə edərək,
gün, sol paltar qoymaq

441
00:20:36,500 --> 00:20:37,990
Əgər siz onları üz qoymaq zaman.

442
00:20:37,990 --> 00:20:41,300
Sonra sabah səhər zaman
Sizin paltar almaq, günəş görmək

443
00:20:41,300 --> 00:20:43,440
xəttinin sonunda sağ, on.

444
00:20:43,440 --> 00:20:44,880
Siz görmürlərmi? Lou bildirib.

445
00:20:44,880 --> 00:20:46,370
Bu, belə gözəl olacaq.

446
00:20:46,370 --> 00:20:49,770
Siz bir dəfə hər şeyi geymək lazımdır
əvvəl iki dəfə bir şey köhnəlir.

447
00:20:49,770 --> 00:20:52,670
Və sıralarında hər şeyi ilə
onun gizli və şelfində,

448
00:20:52,670 --> 00:20:55,160
Jack hiss etməyə başlayıb
özü kifayət qədər əmin.

449
00:20:55,160 --> 00:20:59,720
Lou Bütün thanks və
onun gözəl queue.

450
00:20:59,720 --> 00:21:01,220
HOPARLÖR 1: Yaxşı, bu sitayişə layiq deyil.

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

452
00:21:05,920 --> 00:21:10,080
Belə ki, həqiqətən gedir nə
İndi başlıq altında?

453
00:21:10,080 --> 00:21:12,370
Biz göstəricilərinə var ki,
biz malloc var ki,

454
00:21:12,370 --> 00:21:15,680
biz yaratmaq imkanı var ki,
özümüz üçün yaddaş chunks

455
00:21:15,680 --> 00:21:16,344
dinamik.

456
00:21:16,344 --> 00:21:18,510
Belə ki, bu şəkil biz
yalnız gün glimpsed.

457
00:21:18,510 --> 00:21:21,180
Biz, həqiqətən, əbədi etməyib
bu, ancaq bu şəkil

458
00:21:21,180 --> 00:21:24,180
altında var davam
İndi həftə başlıq.

459
00:21:24,180 --> 00:21:27,050
Və bu, yalnız təmsil
Biz tərtib etdik düzbucaqlı,

460
00:21:27,050 --> 00:21:28,180
kompüter yaddaş.

461
00:21:28,180 --> 00:21:31,850
Və bəlkə sizin kompüter və ya CS50
ID, yaddaş və ya RAM gigabayt var

462
00:21:31,850 --> 00:21:33,050
və ya iki qiqabayt və ya dörd.

463
00:21:33,050 --> 00:21:34,450
Bu, həqiqətən etməz.

464
00:21:34,450 --> 00:21:37,240
Sizin əməliyyat sistemi
Windows və ya Mac OS və ya Linux,

465
00:21:37,240 --> 00:21:41,120
mahiyyətcə proqram imkan verir
Bu çıxışı var hesab edirəm ki,

466
00:21:41,120 --> 00:21:42,982
tam üçün
kompüter yaddaş,

467
00:21:42,982 --> 00:21:45,440
hətta çalışan bilər, baxmayaraq
Eyni anda birdən çox proqramları.

468
00:21:45,440 --> 00:21:46,990
Belə ki, əslində, həqiqətən işləmir.

469
00:21:46,990 --> 00:21:49,448
Lakin bir illüziya növü var
proqramları bütün verilir.

470
00:21:49,448 --> 00:21:53,110
Belə ki, bu RAM iki gigs var idi
Kompüter hesab edə bilər necə.

471
00:21:53,110 --> 00:21:57,110
>> İndi təsadüfən, bu bir
şeyi, yaddaş bu seqmentləri biri

472
00:21:57,110 --> 00:21:58,350
bir yığın adlanır.

473
00:21:58,350 --> 00:22:01,680
Həqiqətən heç bir zaman
indiyə qədər yazılı kodu

474
00:22:01,680 --> 00:22:05,900
Siz çağırıb ki,
instansiya əsas funksiyası.

475
00:22:05,900 --> 00:22:08,410
Heç bir zaman mən var Xatırladaq ki,
tərtib kompüter yaddaş,

476
00:22:08,410 --> 00:22:10,640
Mən həmişə sort çəkmək
burada düzbucaqlı yarım

477
00:22:10,640 --> 00:22:12,520
və söhbət narahat etmir
Yuxarıda nə haqqında.

478
00:22:12,520 --> 00:22:15,980
Əsas adlanır zaman, mən iddia çünki
Siz yaddaş bu qəlpə almaq

479
00:22:15,980 --> 00:22:16,970
burada enir.

480
00:22:16,970 --> 00:22:20,650
Əsas əgər bir funksiyası adlanır
svop kimi, yaxşı svop burada gedir.

481
00:22:20,650 --> 00:22:23,720
Və bu ki, çıxır
harada sona oldu.

482
00:22:23,720 --> 00:22:26,277
Bir yığın adlı bir şey On
Sizin kompüter yaddaş daxilində.

483
00:22:26,277 --> 00:22:28,360
İndi günün sonunda,
Bu yalnız müraciət edir.

484
00:22:28,360 --> 00:22:30,680
Bu byte sıfır kimi
byte bir byte 2 milyard.

485
00:22:30,680 --> 00:22:33,130
Amma bu barədə düşünmək
Bu düzbucaqlı obyekt kimi,

486
00:22:33,130 --> 00:22:35,130
bütün biz hər edirik
dəfə biz bir funksiyası zəng

487
00:22:35,130 --> 00:22:37,180
yaddaş yeni bir dilim layering.

488
00:22:37,180 --> 00:22:41,700
Biz dilim funksiyası ötürür
öz yaddaş ilə işləmək üçün.

489
00:22:41,700 --> 00:22:44,490
>> Bu əhəmiyyətli olduğunu indi xatırlayıram.

490
00:22:44,490 --> 00:22:46,400
Biz var, çünki
svop kimi bir şey

491
00:22:46,400 --> 00:22:51,610
A və B və kimi və iki yerli dəyişənlərin
biz bir və iki həmin dəyərləri dəyişdirmək

492
00:22:51,610 --> 00:22:55,130
iki və bir geri üçün
svop qaytarır zaman,

493
00:22:55,130 --> 00:22:58,330
Bu dilim sanki var
yaddaş yalnız getdi.

494
00:22:58,330 --> 00:23:00,080
Əslində, bu, hələ də var
orada forensically.

495
00:23:00,080 --> 00:23:01,940
Və bir şey həqiqətən var hələ də var.

496
00:23:01,940 --> 00:23:05,410
Amma konseptual, bu kimi deyil
baxmayaraq ki, tamamilə getdi.

497
00:23:05,410 --> 00:23:10,910
Və belə ki, əsas iş hər hansı bir bilmir
ki, ki, mübadilə funksiyası edildi

498
00:23:10,910 --> 00:23:14,890
Bu, həqiqətən o keçdi halda
pointer ya istinadən dəlilləri.

499
00:23:14,890 --> 00:23:17,790
İndi fundamental həll
svop ilə problem

500
00:23:17,790 --> 00:23:19,970
ünvanı şeyi keçir.

501
00:23:19,970 --> 00:23:23,250
Amma bu da nə var, çıxır
bir hissəsi yuxarıda davam

502
00:23:23,250 --> 00:23:26,330
düzbucaqlı bütün bu vaxt
hələ daha çox yaddaş orada var.

503
00:23:26,330 --> 00:23:28,790
Və zaman dinamik
yaddaş ayrılması,

504
00:23:28,790 --> 00:23:32,020
Bu GetString, daxilində olub ki,
biz CS50 sizin üçün bunu etdik

505
00:23:32,020 --> 00:23:34,710
kitabxana, və ya uşaqlar əgər
malloc zəng və xahiş

506
00:23:34,710 --> 00:23:37,950
bir yığın üçün əməliyyat sistemi
yaddaş, bu yığını deyil.

507
00:23:37,950 --> 00:23:40,960
Bu başqa yerə gəlir
kompüter yaddaş

508
00:23:40,960 --> 00:23:42,220
ki, yığın deyirlər.

509
00:23:42,220 --> 00:23:43,430
Və hər hansı bir fərqli deyil.

510
00:23:43,430 --> 00:23:44,285
Bu eyni RAM var.

511
00:23:44,285 --> 00:23:45,160
Bu eyni yaddaş var.

512
00:23:45,160 --> 00:23:49,080
Bu qədər yalnız RAM var
orada əvəzinə aşağı burada.

513
00:23:49,080 --> 00:23:50,750
>> Və belə ki, nə deməkdir?

514
00:23:50,750 --> 00:23:53,650
Yaxşı, sizin kompüter varsa
yaddaş məhdud məbləği

515
00:23:53,650 --> 00:23:57,450
və yığını, belə ki, böyüyür
danışmaq, və yığın, görə

516
00:23:57,450 --> 00:23:59,349
bu arrow aşağı artır.

517
00:23:59,349 --> 00:24:01,140
Başqa sözlə, hər
zaman malloc zəng

518
00:24:01,140 --> 00:24:03,430
Bir dilim veriləcək edirik
yaddaş yuxarıda,

519
00:24:03,430 --> 00:24:06,630
Bir az sonra, aşağı sonra bəlkə bir az
aşağı, siz malloc zəng hər zaman,

520
00:24:06,630 --> 00:24:10,100
yığın, bu istifadə var,
cür artır,

521
00:24:10,100 --> 00:24:11,950
nə daha yaxın və daha artan?

522
00:24:11,950 --> 00:24:13,382
yığını.

523
00:24:13,382 --> 00:24:14,840
Belə ki, bu yaxşı bir fikir kimi görünür?

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

525
00:24:18,420 --> 00:24:22,140
Bu, həqiqətən, açıq-aydın deyil Mən demək,
başqa nə yalnız edə bilərsiniz

526
00:24:22,140 --> 00:24:23,910
yaddaş məhdud miqdarı var.

527
00:24:23,910 --> 00:24:25,200
Amma bu, şübhəsiz ki, pis.

528
00:24:25,200 --> 00:24:27,920
Bu iki oxlar bir var
bir-birinə kurs qəza.

529
00:24:27,920 --> 00:24:31,930
>> Və bu pis oğlan, insanlar çıxır
, proqramlaşdırma ilə xüsusilə yaxşı

530
00:24:31,930 --> 00:24:36,140
və kompüter hack çalışır,
Bu həqiqəti istifadə edə bilərsiniz.

531
00:24:36,140 --> 00:24:38,290
Əslində, hesab edək
bir az parçasını.

532
00:24:38,290 --> 00:24:41,350
Belə ki, bu oxuya bilərsiniz bir nümunəsidir
haqqında Wikipedia daha ətraflı.

533
00:24:41,350 --> 00:24:43,100
Biz sizə qeyd edəcəyik
Məqalədə əgər maraqlı.

534
00:24:43,100 --> 00:24:45,650
Amma bir hücum ümumiyyətlə var
bufer daşqın kimi tanınan

535
00:24:45,650 --> 00:24:49,570
insanlar kimi uzun üçün mövcud
manipulyasiya etmək imkanı var

536
00:24:49,570 --> 00:24:53,120
xüsusilə C. kompüter yaddaş,
Belə ki, bu, çox özbaşına proqram,

537
00:24:53,120 --> 00:24:55,130
lakin alt qədər oxumaq bildirin.

538
00:24:55,130 --> 00:24:57,650
Argc char star argv daxil Main.

539
00:24:57,650 --> 00:24:59,830
Belə ki, edir ki, bir proqram
command line dəlilləri.

540
00:24:59,830 --> 00:25:03,620
Və bütün əsas yəqin zəng etmir
bir funksiyası, sadəlik üçün F çağırırıq.

541
00:25:03,620 --> 00:25:04,610
Və nə keçir?

542
00:25:04,610 --> 00:25:05,490
Bir argv.

543
00:25:05,490 --> 00:25:09,320
Belə ki, F keçir nə
Word istifadəçi tipli ki,

544
00:25:09,320 --> 00:25:11,500
sonra sətirinə
Proqramın adı bütün.

545
00:25:11,500 --> 00:25:15,730
Belə ki, çox Sezar və ya Vigenere kimi olan
Siz argv ilə məşğul xatırlayıram bilər.

546
00:25:15,730 --> 00:25:16,680
>> Belə ki, F nədir?

547
00:25:16,680 --> 00:25:19,760
F simli edir
onun yeganə arqument kimi,

548
00:25:19,760 --> 00:25:22,100
AKA bir char ulduz, eyni
şey, bir string kimi.

549
00:25:22,100 --> 00:25:24,920
Və bu özbaşına deyirlər
Bu misalda bar.

550
00:25:24,920 --> 00:25:27,710
Və sonra char c 12
yalnız layman nin baxımından,

551
00:25:27,710 --> 00:25:31,750
bizim üçün bunu char c bracket 12 nədir?

552
00:25:31,750 --> 00:25:33,440
Nə olub?

553
00:25:33,440 --> 00:25:36,490
Xüsusi, yaddaş ayrılması
12 chars 12 bytes.

554
00:25:36,490 --> 00:25:36,990
Məhz.

555
00:25:36,990 --> 00:25:40,000
Və sonra son xətt, tərpənmək və
surəti, yəqin ki, görmədim etdik.

556
00:25:40,000 --> 00:25:43,360
Bu string surəti
kimin məqsədi həyat funksiyası

557
00:25:43,360 --> 00:25:48,160
ikinci arqument surəti deyil
ilk mübahisəyə,

558
00:25:48,160 --> 00:25:51,190
lakin yalnız bir qədər
bayt müəyyən sayda.

559
00:25:51,190 --> 00:25:53,860
Belə ki, üçüncü arqument deyir
Necə bir çox bytes surəti lazımdır?

560
00:25:53,860 --> 00:25:56,720
bar uzunluğu,
nə Yığdığınız istifadəçi.

561
00:25:56,720 --> 00:25:59,320
Və məzmunu
ki, ki, simli bar

562
00:25:59,320 --> 00:26:02,330
yaddaş daxil sitemizi C işarə

563
00:26:02,330 --> 00:26:04,060
>> Belə ki, bu cür axmaq görünür, o da olur.

564
00:26:04,060 --> 00:26:06,300
Bu göstərdi misal var,
lakin bu nümayəndəsi var

565
00:26:06,300 --> 00:26:10,100
hücum istiqamətini sinfinin,
bir proqram hücum bir yol.

566
00:26:10,100 --> 00:26:15,050
Bütün gözəl və istifadəçi əgər yaxşı
11 simvol bir sözlə növləri

567
00:26:15,050 --> 00:26:18,040
az, plus backslash sıfır və ya.

568
00:26:18,040 --> 00:26:22,830
Daha istifadəçi növləri daha əgər
11 və ya 12 və ya 20 və ya 50 simvol?

569
00:26:22,830 --> 00:26:25,090
Edəcəyimiz bu proqram nədir?

570
00:26:25,090 --> 00:26:29,360
Potensial seg günah. Gedir
kor-koranə up bar hər şeyi surəti

571
00:26:29,360 --> 00:26:31,750
onun uzunluğu
sanki bar hər şey

572
00:26:31,750 --> 00:26:36,307
Ünvan daxil C. Lakin C işarə
yalnız preemptively 12 bayt kimi verdi.

573
00:26:36,307 --> 00:26:37,640
Amma heç bir əlavə çek var.

574
00:26:37,640 --> 00:26:38,700
Şərtləri əgər heç bir var.

575
00:26:38,700 --> 00:26:40,580
Burada yoxlanılması heç bir səhv var.

576
00:26:40,580 --> 00:26:43,270
>> Və bu proqram nə
edəcəyimiz yalnız kor-koranə deyil

577
00:26:43,270 --> 00:26:45,750
digər bir şey surəti.

578
00:26:45,750 --> 00:26:47,880
Və belə ki, biz bu aparsaq
bir şəkil kimi, burada

579
00:26:47,880 --> 00:26:49,860
yaddaş alanı yalnız bir sliver.

580
00:26:49,860 --> 00:26:53,470
Belə ki, biz, altındakı qeyd
yerli dəyişən bar var.

581
00:26:53,470 --> 00:26:57,330
Store-- olacaq ki, pointer So
ki, yerli dəlil deyil,

582
00:26:57,330 --> 00:26:58,672
string bar saxlamaq üçün gedir.

583
00:26:58,672 --> 00:27:00,380
Və sonra yalnız qeyd
Yuxarıda bir yığını,

584
00:27:00,380 --> 00:27:02,505
çünki xahiş hər zaman
yığını yaddaş üçün,

585
00:27:02,505 --> 00:27:04,310
Bu bir az gedir
pictorially yuxarıda,

586
00:27:04,310 --> 00:27:06,270
biz orada 12 bytes var bildiriş.

587
00:27:06,270 --> 00:27:10,690
sol üst bir C bracket sıfır və
sağ alt bir C bracket 11.

588
00:27:10,690 --> 00:27:12,870
Bu necə kompüter var
onu qoymaq niyyətindədir.

589
00:27:12,870 --> 00:27:18,300
Belə ki, yalnız daxilən, bar daha var, əgər
olmaq üzrə cəmdə 12 simvol daha

590
00:27:18,300 --> 00:27:25,790
var backslash sıfır,
12 və ya C bracket 12 getmək üçün gedir?

591
00:27:25,790 --> 00:27:28,440
Və ya daha burada 12-ci
xarakter və ya 13 xarakteri,

592
00:27:28,440 --> 00:27:30,900
gedir yüzüncü xarakter
şəkil başa?

593
00:27:30,900 --> 00:27:33,400
Yuxarıda və ya aşağıda?

594
00:27:33,400 --> 00:27:36,300
>> Sağ, baxmayaraq ki, çünki
yığını özü yuxarı artır

595
00:27:36,300 --> 00:27:39,590
Siz məhsulları qoymaq sonra
Bu, dizayn səbəblərə görə,

596
00:27:39,590 --> 00:27:41,294
üstdən-aşağı yaddaş qoyur.

597
00:27:41,294 --> 00:27:44,460
Siz 12-dən çox bayt var Belə ki,
Siz bar üzerine başlamaq olacaq.

598
00:27:44,460 --> 00:27:47,280
İndi bir səhv var, lakin bu
həqiqətən böyük.

599
00:27:47,280 --> 00:27:51,130
Var, çünki Lakin bu, böyük edir
yaddaş gedən daha stuff.

600
00:27:51,130 --> 00:27:53,074
Belə ki, burada biz necə güc var
aydın olmaq, salam qoydu.

601
00:27:53,074 --> 00:27:54,490
Mən sətirinə salam çap edin.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash sıfır ərzində başa
o 12 bytes, biz super təhlükəsiz edirik.

603
00:27:59,330 --> 00:28:00,330
Hər şey yaxşıdır.

604
00:28:00,330 --> 00:28:03,020
Amma bir şey yazın əgər
artıq potensial bu

605
00:28:03,020 --> 00:28:05,860
bar kosmosa dırmaşmaq gedir.

606
00:28:05,860 --> 00:28:08,405
Amma pis hələ, bu çevrilir
Bütün bu müddət həyata,

607
00:28:08,405 --> 00:28:11,530
Biz söhbət heç etdik olsa da
bu yığını digər məhsulları üçün istifadə olunur.

608
00:28:11,530 --> 00:28:13,560
Bu, sadəcə yerli dəyişənlərin deyil.

609
00:28:13,560 --> 00:28:15,100
>> C çox aşağı səviyyədə dilidir.

610
00:28:15,100 --> 00:28:17,810
Və bu cür gizli
də yığını istifadə

611
00:28:17,810 --> 00:28:21,260
zaman xatırlamaq bir
funksiyası, nə adlanır

612
00:28:21,260 --> 00:28:26,040
ünvan, əvvəlki funksiyası var
belə ki, geri funksiyası atlayabilirsiniz.

613
00:28:26,040 --> 00:28:29,980
Belə ki, əsas zənglər arasında mübadilə zaman
şeyi yığını üzərinə basdı

614
00:28:29,980 --> 00:28:34,380
yalnız yerli dəyişənlərin svopları deyil
və ya onun dəlilləri də gizli basdı

615
00:28:34,380 --> 00:28:37,510
yığını üzərinə təmsil
Burada qırmızı dilim ilə,

616
00:28:37,510 --> 00:28:40,520
əsas ünvanı fiziki
Sizin kompüter yaddaşında,

617
00:28:40,520 --> 00:28:44,180
ki, svop edilir, kompüter
Mən əsas geri getmək lazımdır bilir

618
00:28:44,180 --> 00:28:46,760
və əsas funksiyası həyata tamamlayın.

619
00:28:46,760 --> 00:28:51,960
Belə ki, bu, indi təhlükəli, çünki
salam daha yaxşı daha çox istifadəçi,

620
00:28:51,960 --> 00:28:57,030
İstifadəçi girişi clobbers ki, belə
və ya, qırmızı bölmə üzerine yazır

621
00:28:57,030 --> 00:28:59,820
məntiqi əgər kompüter
yalnız kor-koranə güman gedir

622
00:28:59,820 --> 00:29:03,830
ki, qırmızı dilim bytes var ki,
Bu qaytarmalıdır olan ünvan,

623
00:29:03,830 --> 00:29:09,020
rəqib nə varsa kifayət qədər ağıllı və ya
bayt ardıcıllığı qoymaq üçün kifayət qədər şanslı

624
00:29:09,020 --> 00:29:13,450
orada bir ünvan kimi görünür ki,
lakin bu kodu ünvanı var

625
00:29:13,450 --> 00:29:18,730
o kompüter istəyir ki,
əvəzinə əsas icra?

626
00:29:18,730 --> 00:29:21,670
>> Başqa sözlə, nə əgər
istifadəçi tez at yazaraq

627
00:29:21,670 --> 00:29:23,850
yalnız bir şey deyil
, salam xətərsiz kimi

628
00:29:23,850 --> 00:29:28,210
lakin bu ekvivalent var code həqiqətən
Bu istifadəçinin bütün faylları silmək üçün?

629
00:29:28,210 --> 00:29:30,060
Və ya mənə öz parol e-poçt?

630
00:29:30,060 --> 00:29:31,940
Və ya giriş başlamaq onların
tuş vuruşlarını, sağ?

631
00:29:31,940 --> 00:29:34,920
Bir yol yoxdur, bu gün müəyyən edək
Onlar salam yalnız yazın bilər ki,

632
00:29:34,920 --> 00:29:36,711
dünya və ya onların adı,
onlar mahiyyətcə bilər

633
00:29:36,711 --> 00:29:39,570
indeksi, adet sıfır keçmək və
olanlar, kompüter

634
00:29:39,570 --> 00:29:43,450
kodu və ünvanı üçün səhvlər.

635
00:29:43,450 --> 00:29:48,950
Olsa belə qədər mücərrəd, əgər
kifayət qədər çəkişmə kodu istifadəçi

636
00:29:48,950 --> 00:29:52,330
Biz burada kimi ümumiləşdirmək lazımdır ki,
A. A hücum və ya düşmən edir.

637
00:29:52,330 --> 00:29:53,140
Belə ki, yalnız pis stuff.

638
00:29:53,140 --> 00:29:55,306
Biz haqqında qayğı yoxdur
nömrələri və ya adet sıfır və ya olanları

639
00:29:55,306 --> 00:29:59,470
bu gün belə başa ki,
qırmızı bölmə yadda,

640
00:29:59,470 --> 00:30:01,580
bayt ki, ardıcıllıqla qeyd.

641
00:30:01,580 --> 00:30:05,020
O 835 C sıfır səkkiz sıfır.

642
00:30:05,020 --> 00:30:08,960
İndi burada Wikipedia məqalə
İndi həqiqətən başlamaq əgər, təklif edib

643
00:30:08,960 --> 00:30:12,460
Sizin kompüter-ci ildə bayt etiketleme
yaddaş, Wikipedia article nə

644
00:30:12,460 --> 00:30:19,060
təklif edir ki, nə ünvan əgər
ki, sol üst byte 80 C 0 3508 edir.

645
00:30:19,060 --> 00:30:22,200
>> Başqa sözlə, pis adam əgər
onun kodu ilə kifayət qədər ağıllı

646
00:30:22,200 --> 00:30:26,650
həqiqətən, burada bir sıra qoymaq ki,
kodu ünvanı uyğundur

647
00:30:26,650 --> 00:30:29,180
o vurulub
kompüter, siz

648
00:30:29,180 --> 00:30:31,050
kompüter bezemek bilər
bir şey bunu nəzərə.

649
00:30:31,050 --> 00:30:34,140
, Faylları aradan qaldırılması e-poçt
şeyi, trafik koklama,

650
00:30:34,140 --> 00:30:36,710
sanki bir şey ola bilər
Kompüter enjekte.

651
00:30:36,710 --> 00:30:39,220
Və belə bir bufer daşqın
onun əsas hücum

652
00:30:39,220 --> 00:30:43,530
Yalnız bir axmaq, axmaq
bir sıra əsas ki,

653
00:30:43,530 --> 00:30:45,840
onun sərhədləri yoxlanılır yox idi.

654
00:30:45,840 --> 00:30:48,850
Bu super təhlükəli nə
və eyni zamanda super güclü

655
00:30:48,850 --> 00:30:52,560
C biz həqiqətən var ki,
yaddaş yerdə çıxış.

656
00:30:52,560 --> 00:30:55,320
Bu, bizim üçün var, proqramçılar,
olan orijinal kodu yazmaq

657
00:30:55,320 --> 00:30:59,330
hər hansı bir darn uzunluğu yoxlamaq üçün
biz manipulyasiya edirik Diziler.

658
00:30:59,330 --> 00:31:00,750
Belə ki, aydın olmaq, fix nə var?

659
00:31:00,750 --> 00:31:03,190
Bu geri gəzmək
kodu, mən olmalıdır yalnız

660
00:31:03,190 --> 00:31:08,000
bar uzunluğu dəyişdirmək, nə
başqa mən yoxlanılması lazımdır?

661
00:31:08,000 --> 00:31:10,620
Nə mən bunu etmək lazımdır
tamamilə bu hücumun qarşısını?

662
00:31:10,620 --> 00:31:14,110
Mən yalnız kor-koranə demək istəmirəm
Siz kimi bir çox bytes surəti lazımdır ki,

663
00:31:14,110 --> 00:31:16,140
kimi bar uzunluğu.

664
00:31:16,140 --> 00:31:18,910
Mən surəti, demək istəyirəm
kimi bir çox bytes bar var

665
00:31:18,910 --> 00:31:24,090
ayrılan qədər
yaddaş, və ya maksimum 12.

666
00:31:24,090 --> 00:31:27,450
Beləliklə, mən vəziyyətdə əgər bir növ lazımdır
ki, bar uzunluğu yoxlamaq yoxdur,

667
00:31:27,450 --> 00:31:32,800
lakin bu 12, biz yalnız ağır kodu artıq olduqda
Maksimum məsafə 12.

668
00:31:32,800 --> 00:31:35,910
Əks halda qondarma bufer
daşqın hücum ola bilər.

669
00:31:35,910 --> 00:31:38,451
Bu slaydlar altında,
daha çox oxumaq maraqlı olduğunuz halda

670
00:31:38,451 --> 00:31:41,200
faktiki orijinal məqalə
Bir nəzər istəyirsinizsə.

671
00:31:41,200 --> 00:31:44,550
>> Amma indi, qiymətlər arasında
qeyri-səmərəli burada idi etmişdir.

672
00:31:44,550 --> 00:31:46,680
Belə ki, tez idi
aşağı səviyyədə baxmaq nə

673
00:31:46,680 --> 00:31:49,709
problemlər ki, biz indi yarana bilər
kompüter yaddaş girmə imkanı vardır.

674
00:31:49,709 --> 00:31:51,750
Amma bir problem biz
Artıq bazar ertəsi stumbled

675
00:31:51,750 --> 00:31:53,800
yalnız təsirsizlik idi
bir bağlı siyahı.

676
00:31:53,800 --> 00:31:56,019
Biz geri xətti vaxt var.

677
00:31:56,019 --> 00:31:57,560
Biz artıq bir bitişik array var.

678
00:31:57,560 --> 00:31:58,980
Biz təsadüfi çıxışı yoxdur.

679
00:31:58,980 --> 00:32:00,710
Biz kvadrat mötərizə notation istifadə edə bilməz.

680
00:32:00,710 --> 00:32:04,590
Biz sözün bir müddət loop istifadə etmək lazımdır
kimi mən bir an əvvəl yazmışdır.

681
00:32:04,590 --> 00:32:09,740
Lakin bazar ertəsi, biz əlimizdən iddia etdi
səmərəliliyinin sahəsində geri dırmaşmaq

682
00:32:09,740 --> 00:32:13,040
ki, bir şey əldə
logarithmic bəlkə, və ya ən yaxşı hələ,

683
00:32:13,040 --> 00:32:16,120
bəlkə hətta bir şey
daimi vaxt qondarma.

684
00:32:16,120 --> 00:32:19,840
Beləliklə, biz bu yeni istifadə edərək necə edə bilərik
alətlər, bu ünvanları, bu göstəricilər,

685
00:32:19,840 --> 00:32:22,210
və öz şeyi Threading?

686
00:32:22,210 --> 00:32:23,960
Yaxşı ki, güman
Burada, bu bir dəstə var

687
00:32:23,960 --> 00:32:27,170
Biz saxlamaq istədiyiniz nömrələri
səmərəli data strukturu və axtarış.

688
00:32:27,170 --> 00:32:30,960
Biz tamamilə həftə geri bilər
iki, bir sıra bu atmaq

689
00:32:30,960 --> 00:32:33,150
və ikili axtarış istifadə edərək, onları axtarmaq.

690
00:32:33,150 --> 00:32:34,040
Bölün və fəth.

691
00:32:34,040 --> 00:32:37,720
Və əslində siz yazdı
pset3 ikili axtarış,

692
00:32:37,720 --> 00:32:40,100
harada tapmaq proqramını həyata keçirmişdir.

693
00:32:40,100 --> 00:32:40,890
Amma bilirik.

694
00:32:40,890 --> 00:32:45,060
Daha növü var
bunu ağıllı yol.

695
00:32:45,060 --> 00:32:47,390
Bu bir az daha çox
inkişaf etmiş və bəlkə

696
00:32:47,390 --> 00:32:50,830
Bizi niyə ikili görmək üçün imkan verir
Axtarış çox daha sürətli belə deyil.

697
00:32:50,830 --> 00:32:52,980
Birincisi, təqdim edək
bir ağac anlayışı.

698
00:32:52,980 --> 00:32:54,730
Hansı hətta baxmayaraq
reallıq ağaclar cür

699
00:32:54,730 --> 00:32:57,730
Kompüter dünyada, bu kimi inkişaf
Onlar cür aşağı bitir elm

700
00:32:57,730 --> 00:33:00,830
bir ailə ağac kimi
Sizin grandparents və ya böyük babası

701
00:33:00,830 --> 00:33:04,580
və ya etajer üst patriarxı və
ailə matriarch yalnız bir

702
00:33:04,580 --> 00:33:07,930
kök, node, aşağıdakı qondarma
onun uşaqlar olan var,

703
00:33:07,930 --> 00:33:11,442
Aşağıda onun uşaqlar, və ya
onun nəvələri ümumiyyətlə.

704
00:33:11,442 --> 00:33:13,400
Və hər kəs off asma
ailə alt

705
00:33:13,400 --> 00:33:16,070
ağac, olmaqla yanaşı
ailə gənc,

706
00:33:16,070 --> 00:33:19,520
də yalnız generically ola bilər
Onun yarpaqları çağırıb.

707
00:33:19,520 --> 00:33:21,800
>> Belə ki, bu, yalnız bir dəstə
sözlər və anlayışlar

708
00:33:21,800 --> 00:33:25,790
bir şey üçün kompüter bir ağac adlı
elm, bir ailə ağac kimi.

709
00:33:25,790 --> 00:33:28,770
Amma maraqlısı incarnations var
ağac, biri

710
00:33:28,770 --> 00:33:30,780
bir ikili axtarış ağac adlanır.

711
00:33:30,780 --> 00:33:34,380
Və siz tease cür
Bu şey yoxdur ayrı nə.

712
00:33:34,380 --> 00:33:37,180
Bəli, bu nə mənada ikili var?

713
00:33:37,180 --> 00:33:41,455
Harada ikili buradan gəlir?

714
00:33:41,455 --> 00:33:41,955
Bağışlayın?

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

716
00:33:45,961 --> 00:33:47,210
Bu, çox bir və ya deyil.

717
00:33:47,210 --> 00:33:52,000
Bu qovşaqlarının hər bir var ki, daha çox
daha iki uşaq, biz burada görürük.

718
00:33:52,000 --> 00:33:54,990
Ümumiyyətlə, bir ağac və
valideynlər və grandparents

719
00:33:54,990 --> 00:33:57,640
kimi bir çox uşaq ola bilər və ya
grandkids onlar həqiqətən istədiyiniz kimi,

720
00:33:57,640 --> 00:34:00,820
və belə məsələn, orada biz üç
ki, sağ node off uşaqlar,

721
00:34:00,820 --> 00:34:05,480
lakin bir ikili ağac, bir node var
maksimum sıfır, bir, ya iki uşaqlar.

722
00:34:05,480 --> 00:34:08,496
Və, bir gözəl əmlak var
Bu iki başıbağlı əgər çünki,

723
00:34:08,496 --> 00:34:10,620
biz mümkün olacaq
bir az log bazası almaq iki

724
00:34:10,620 --> 00:34:11,975
Fəaliyyət burada nəticədə gedir.

725
00:34:11,975 --> 00:34:13,350
Beləliklə, biz logarithmic bir şey var.

726
00:34:13,350 --> 00:34:14,558
Amma bir an ki, daha çox.

727
00:34:14,558 --> 00:34:19,810
Axtarış ağac nömrələri o deməkdir ki,
təşkil, belə ki, sol uşaq

728
00:34:19,810 --> 00:34:22,429
dəyəri kök daha böyükdür.

729
00:34:22,429 --> 00:34:26,010
Və onun sağ uşaq
kök daha böyük.

730
00:34:26,010 --> 00:34:29,290
Başqa sözlə, siz hər hansı bir əgər
qovşaqlarının, bu şəkil dairələr,

731
00:34:29,290 --> 00:34:31,840
və onun sol baxır
uşaq və sağ uşaq,

732
00:34:31,840 --> 00:34:34,739
ilk, az olmalıdır
ikinci daha çox olmalıdır.

733
00:34:34,739 --> 00:34:36,159
Belə ki, ağlı başında olma 55 oldu.

734
00:34:36,159 --> 00:34:37,780
Bu uşaq qalan 33.

735
00:34:37,780 --> 00:34:38,620
Bu az deyil.

736
00:34:38,620 --> 00:34:40,929
55, onun sağ uşaq 77.

737
00:34:40,929 --> 00:34:41,783
Bu daha çox var.

738
00:34:41,783 --> 00:34:43,199
Və bir recursive müəyyən edir.

739
00:34:43,199 --> 00:34:46,480
Biz o hər bir yoxlamaq bilər
qovşaqlarının və saxlayın ki, eyni model.

740
00:34:46,480 --> 00:34:49,389
>> Belə ki, bir gözəl nə var
ikili axtarış ağac

741
00:34:49,389 --> 00:34:52,204
ki, bir, biz bunu həyata keçirə bilər
bir struct ilə, yalnız bu kimi.

742
00:34:52,204 --> 00:34:54,620
Və biz atma edirik, baxmayaraq ki,
Sizin at strukturlarının çox,

743
00:34:54,620 --> 00:34:56,560
onlar bir qədər istəyirik
intuitiv indi inşallah.

744
00:34:56,560 --> 00:35:00,570
syntax hələ əmin üçün gizli deyil
lakin bu bir node məzmunu

745
00:35:00,570 --> 00:35:02,786
kontekstdə və biz saxlamaq
söz node istifadə edərək,

746
00:35:02,786 --> 00:35:04,910
bu bir düzbucaqlı olub
ekran və ya bir dairə üzrə,

747
00:35:04,910 --> 00:35:08,970
Bu, yalnız bir ümumi konteyner var
kimi bir ağac bu halda,

748
00:35:08,970 --> 00:35:11,780
Biz bir tam lazımdır, gördüm
qovşaqlarının hər

749
00:35:11,780 --> 00:35:15,460
və sonra mən iki göstəricilərinə işarə lazımdır
sol uşaq və sağ uşaq,

750
00:35:15,460 --> 00:35:16,590
olaraq təyin olundu.

751
00:35:16,590 --> 00:35:20,730
Ki Belə ki, necə biz bilər
bir struct ki, həyata keçirir.

752
00:35:20,730 --> 00:35:22,315
Və necə kodu bunu həyata bilər?

753
00:35:22,315 --> 00:35:26,730
Yaxşı, tez götürək
Bu kiçik nümunə oldu.

754
00:35:26,730 --> 00:35:29,820
Bu funksional deyil, lakin mən var
sitemizi və strukturu yapışdırılır.

755
00:35:29,820 --> 00:35:33,510
Əgər bir ikili üçün funksiyası
axtarış ağac, axtarış adlanır

756
00:35:33,510 --> 00:35:36,980
və bu iki dəlilləri edir,
bir tam N və bir pointer

757
00:35:36,980 --> 00:35:41,400
ağac bir node, belə bir göstərici
və ya bir ağac kök bir göstərici,

758
00:35:41,400 --> 00:35:43,482
necə N üçün axtarış haqqında getmək yoxdur?

759
00:35:43,482 --> 00:35:45,440
Bəli, ilk, mən deyiləm, çünki
göstəricilər ilə məşğul,

760
00:35:45,440 --> 00:35:46,750
Mən ağlı başında olma çek etmək gedirəm.

761
00:35:46,750 --> 00:35:54,279
Ağac bərabər null bərabərdir əgər, N
Bu ağac və ya bu ağac?

762
00:35:54,279 --> 00:35:55,070
Bu doğru ola bilər?

763
00:35:55,070 --> 00:35:56,870
Mən null keçmiş am varsa,
orada heç nə yoxdur.

764
00:35:56,870 --> 00:35:59,230
Mən güc həmçinin yalnız
kor-koranə saxta qayıtmaq deyirlər.

765
00:35:59,230 --> 00:36:04,050
Mənə heç bir şey versələr, mən mütləq bilməz
hər hansı bir sayı N. tapmaq başqa Belə ki, nə mən bilər

766
00:36:04,050 --> 00:36:04,750
İndi yoxlamaq?

767
00:36:04,750 --> 00:36:12,830
Mən də başqa N əgər demək gedirəm
ağac node nə az

768
00:36:12,830 --> 00:36:16,300
Mən N dəyər təqdim etdik ki.

769
00:36:16,300 --> 00:36:20,270
Başqa sözlə, sayı Ben əgər
N axtarır, node az

770
00:36:20,270 --> 00:36:21,340
Mən baxıram ki.

771
00:36:21,340 --> 00:36:23,190
Və node I arıyorum
ağac adlanır at,

772
00:36:23,190 --> 00:36:26,370
və əvvəlki Məsələn geri
bir pointer dəyəri almaq üçün,

773
00:36:26,370 --> 00:36:28,310
Mən arrow notation istifadə edin.

774
00:36:28,310 --> 00:36:35,960
N ağac arrow az olduqda belə
N, mən konseptual sol getmək istəyirəm.

775
00:36:35,960 --> 00:36:38,590
Necə sol axtarış ifadə edirsiniz?

776
00:36:38,590 --> 00:36:41,560
Bu halda, aydın olmaq
sual şəkil,

777
00:36:41,560 --> 00:36:44,612
Mən qəbul etdik topmost ki
ki, aşağı işarə arrow.

778
00:36:44,612 --> 00:36:45,570
Bu mənim ağac göstərici var.

779
00:36:45,570 --> 00:36:48,060
Mən ağac kökü işarə edirəm.

780
00:36:48,060 --> 00:36:52,100
Və mən, demək arıyorum
özbaşına sayı 44.

781
00:36:52,100 --> 00:36:55,300
Daha az və ya 44
açıq-aydın 55-dən çox?

782
00:36:55,300 --> 00:36:56,360
Belə ki, az deyil.

783
00:36:56,360 --> 00:36:58,760
Və bu halda vəziyyət tətbiq edilir.

784
00:36:58,760 --> 00:37:03,981
Belə ki, konseptual, mən nə istəyirəm
Mən 44 arıyorum əgər növbəti axtarış?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Məhz, Mən istəyirəm
sol uşaq axtarış

788
00:37:11,100 --> 00:37:12,789
və ya bu şəkil sol alt ağac.

789
00:37:12,789 --> 00:37:14,830
Və əslində, məni vasitəsilə bildirin
aşağı burada şəkil

790
00:37:14,830 --> 00:37:17,770
yalnız bir an üçün,-ci ildən
Mən bu danışıq bilməz.

791
00:37:17,770 --> 00:37:21,150
Mən 55 burada başlamaq və əgər
Mən bilirəm ki, dəyəri 44

792
00:37:21,150 --> 00:37:23,180
Etmək üçün mən arıyorum
Sol, bu cür

793
00:37:23,180 --> 00:37:26,010
bir telefon kitab qoparmaq kimi
yarım və ya yarısında ağac qoparmaq.

794
00:37:26,010 --> 00:37:29,660
Mən artıq qayğı var
ağac bütün bu yarısı.

795
00:37:29,660 --> 00:37:33,270
Və hələ, maraqla baxımından
strukturu, burada bu şey

796
00:37:33,270 --> 00:37:36,682
33 ilə başlayır özü ki,
bir ikili axtarış ağac.

797
00:37:36,682 --> 00:37:39,890
Çünki əvvəl söz recursive bildirib
Həqiqətən, bu data structure ki,

798
00:37:39,890 --> 00:37:41,707
müəyyən recursive edir.

799
00:37:41,707 --> 00:37:44,540
Bu bir ağac ola bilər
böyük, lakin onun uşaqların hər biri

800
00:37:44,540 --> 00:37:46,870
kiçik bir az bir ağac təmsil edir.

801
00:37:46,870 --> 00:37:50,910
Əvəzində bu baba olan
və ya nənə, indi yalnız ana var

802
00:37:50,910 --> 00:37:54,300
or-- Mən ana deyil demək olmaz
və ya dad, ki, qəribə olardı.

803
00:37:54,300 --> 00:37:59,000
Əvəzinə iki uşaq
qardaşı və qardaşı kimi olacaq.

804
00:37:59,000 --> 00:38:01,120
Ailə ağac yeni nəsil.

805
00:38:01,120 --> 00:38:02,900
Amma struktur, eyni fikirdir.

806
00:38:02,900 --> 00:38:06,790
Və mən bir funksiyası var çıxır
olan bir ikili axtarış axtarış edə bilərsiniz

807
00:38:06,790 --> 00:38:07,290
ağac.

808
00:38:07,290 --> 00:38:08,680
Bu axtarış adlanır.

809
00:38:08,680 --> 00:38:17,870
Mən ağac arrow sol N üçün axtarış
N dəyərindən artıq başqa əgər

810
00:38:17,870 --> 00:38:18,870
Mən hazırda edirəm.

811
00:38:18,870 --> 00:38:20,800
Bir an əvvəl hekayə 55.

812
00:38:20,800 --> 00:38:23,780
Mən adlı funksiyası var
Axtarış ki, mən yalnız bilərsiniz

813
00:38:23,780 --> 00:38:29,660
N bu keçir və recursively axtarış
sub-ağac və yalnız qaytarılması

814
00:38:29,660 --> 00:38:30,620
nə ki, cavab.

815
00:38:30,620 --> 00:38:33,530
Else Mən burada bir final baza halda var.

816
00:38:33,530 --> 00:38:35,310
>> Son işi nədir?

817
00:38:35,310 --> 00:38:36,570
Tree ya null edir.

818
00:38:36,570 --> 00:38:39,980
Mən ya arıyorum dəyəri
daha bu daha az və ya daha çox

819
00:38:39,980 --> 00:38:42,610
və ya ona bərabər.

820
00:38:42,610 --> 00:38:44,750
Mən bərabər deyə bilər
bərabər, lakin məntiqi bu

821
00:38:44,750 --> 00:38:46,500
yalnız burada başqa deyərək bərabərdir.

822
00:38:46,500 --> 00:38:49,150
Belə ki, doğru, mən bir şey tapmaq necə.

823
00:38:49,150 --> 00:38:51,710
Belə ki, inşallah bu bir deyil
daha çekici nümunə

824
00:38:51,710 --> 00:38:54,900
axmaq sigma funksiyası daha
Biz bir neçə mühazirə etdi

825
00:38:54,900 --> 00:38:58,360
harada bir loop istifadə etmək kimi asan idi
biri bütün nömrələri saymaq

826
00:38:58,360 --> 00:39:02,390
bir veri strukturu Burada N.
özü recursively ki,

827
00:39:02,390 --> 00:39:07,050
biz indi, müəyyən və recursively tərtib
özümüzü ifadə etmək imkanı var

828
00:39:07,050 --> 00:39:09,780
kodu özü recursive edir.

829
00:39:09,780 --> 00:39:12,580
Belə ki, burada eyni kodu.

830
00:39:12,580 --> 00:39:14,400
>> Beləliklə, biz nə digər problemləri həll edə bilər?

831
00:39:14,400 --> 00:39:18,160
Uzaq Belə ki, tez addım
yalnız bir an üçün ağaclar.

832
00:39:18,160 --> 00:39:20,130
Burada, Alman bayrağı deyirlər.

833
00:39:20,130 --> 00:39:22,020
Və aydın var bir
Bu bayraq model.

834
00:39:22,020 --> 00:39:23,811
Və çox var
Dünyada bayraqları ki,

835
00:39:23,811 --> 00:39:27,560
baxımından bu kimi sadə
Onların rənglər və nümunələri.

836
00:39:27,560 --> 00:39:31,930
Amma bu kimi saxlanılır ki, güman
GIF və ya JPEG, və ya bitmap və ya ping,

837
00:39:31,930 --> 00:39:34,240
hər hansı bir qrafik fayl format
olan siz, tanış olduğunuz

838
00:39:34,240 --> 00:39:36,460
Biz istəyirik ki, bəzi
pset4 ilə oynayır.

839
00:39:36,460 --> 00:39:41,550
Bu saxlamaq üçün dəyərli görünmür
qara pixel, qara pixel, qara pixel,

840
00:39:41,550 --> 00:39:44,790
nöqtə, nöqtə, nöqtə, bütün dəstə
ilk scanline qara piksel,

841
00:39:44,790 --> 00:39:47,430
və ya satır, sonra bütün dəstə
eyni, sonra bütün dəstə

842
00:39:47,430 --> 00:39:49,530
sonra eyni və
qırmızı piksel bütün dəstə,

843
00:39:49,530 --> 00:39:53,020
qırmızı piksel, qırmızı piksel, sonra bütün
sarı sarı piksel dəstə, sağ?

844
00:39:53,020 --> 00:39:55,050
>> Belə səmərəsizlik burada var.

845
00:39:55,050 --> 00:39:59,040
Necə daxilən siz ki
Alman bayraq kompres

846
00:39:59,040 --> 00:40:01,320
bir fayl olaraq həyata əgər?

847
00:40:01,320 --> 00:40:04,940
Nə məlumat kimi biz bilməz
məqsədilə disk saxlanılması narahat

848
00:40:04,940 --> 00:40:08,040
kimi bizim fayl ölçüsü azaltmaq üçün
bir kilobayt, bir şey üçün bir MB

849
00:40:08,040 --> 00:40:09,430
kiçik?

850
00:40:09,430 --> 00:40:13,130
Orada redundancy yatır
Burada aydın olmaq?

851
00:40:13,130 --> 00:40:13,880
Siz nə edə bilər?

852
00:40:13,880 --> 00:40:14,380
Evet?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Məhz.

855
00:40:21,970 --> 00:40:24,550
Niyə daha çox xatırlayıram
hər darn pixel rəng

856
00:40:24,550 --> 00:40:28,200
yalnız pset4 etdiyini etdiyiniz kimi
bitmap fayl formatı ilə,

857
00:40:28,200 --> 00:40:32,060
niyə yalnız təmsil etmir
məsələn piksel leftmost sütun,

858
00:40:32,060 --> 00:40:35,370
qara piksel bir dəstə, bir dəstə
qırmızı və sarı bir dəstə,

859
00:40:35,370 --> 00:40:39,210
və sonra yalnız birtəhər kodlar
təkrar ideyası bu 100 dəfə

860
00:40:39,210 --> 00:40:41,020
və ya bu 1000 dəfə təkrar?

861
00:40:41,020 --> 00:40:43,430
Harada 100 və ya 1000
yalnız bir tam, belə ki,

862
00:40:43,430 --> 00:40:47,290
yalnız bir sıra üz əldə edə bilərsiniz
əvəzinə yüzlərlə və ya minlərlə

863
00:40:47,290 --> 00:40:48,270
əlavə piksel.

864
00:40:48,270 --> 00:40:50,990
And olsun ki, necə biz var
Alman bayrağı kompres bilər.

865
00:40:50,990 --> 00:40:51,490
Və

866
00:40:51,490 --> 00:40:53,470
Fransız bayrağı haqqında indi nə?

867
00:40:53,470 --> 00:40:58,930
Bəzi sort və bir az
ruhi həyata olan bayraq

868
00:40:58,930 --> 00:41:01,040
disk haqqında daha çox sıxılmış bilər?

869
00:41:01,040 --> 00:41:05,720
German flag və ya Fransız
bayraq, biz ki, yanaşma, əgər?

870
00:41:05,720 --> 00:41:08,490
Alman bayraq, var, çünki
daha üfüqi ixtisar.

871
00:41:08,490 --> 00:41:12,190
Və dizayn bir çox qrafik fayl
formatları həqiqətən kimi scan xətləri çalışır

872
00:41:12,190 --> 00:41:12,830
yatay.

873
00:41:12,830 --> 00:41:14,674
Onlar işləmək bilər
şaquli, yalnız insanlıq

874
00:41:14,674 --> 00:41:17,090
qərar il əvvəl biz lazımdır
ümumiyyətlə şeyi sıra hesab

875
00:41:17,090 --> 00:41:18,880
sütun cərgə əvəzinə sütun.

876
00:41:18,880 --> 00:41:20,820
Belə ki, həqiqətən olsaydı
fayl baxmaq

877
00:41:20,820 --> 00:41:24,670
Alman bayrağı və bir Fransız ölçüsü
bayraq, belə uzun qətnamə kimi

878
00:41:24,670 --> 00:41:27,530
eyni, eyni eni
və hündürlüyü, bu

879
00:41:27,530 --> 00:41:31,580
Burada böyük olacaq çünki
Özünüz üç dəfə təkrar etmək lazımdır.

880
00:41:31,580 --> 00:41:35,570
Siz mavi, təkrar daxil etmək
özünüzü, ağ, qırmızı, özünüzü təkrar

881
00:41:35,570 --> 00:41:36,740
Özünüzü deyirəm.

882
00:41:36,740 --> 00:41:39,000
Siz yalnız bütün getmək bilməz
sağ yol.

883
00:41:39,000 --> 00:41:41,200
Və bir kənara kimi, etmək
sıxılma sil

884
00:41:41,200 --> 00:41:43,910
Bu halda, hər yerdə
bir video-- dörd çərçivəsində siz

885
00:41:43,910 --> 00:41:45,890
bir film olduğunu xatırlayıram bilər
və ya video ümumiyyətlə

886
00:41:45,890 --> 00:41:47,286
saniyədə 29 və ya 30 kadr kimi.

887
00:41:47,286 --> 00:41:50,410
Bu bir az flip kitab kimi harada
yalnız image, şəkil, şəkil, şəkil görmək,

888
00:41:50,410 --> 00:41:54,410
image yalnız super sürətli belə ki, kimi görünür
Ekranda aktyorlar hərəkət edir.

889
00:41:54,410 --> 00:41:57,130
Burada Bumble Bee var
gül bir dəstə üst.

890
00:41:57,130 --> 00:41:59,790
Və bu cür ola bilər, baxmayaraq
ilk baxışda görmək çətin,

891
00:41:59,790 --> 00:42:04,020
hərəkət tək şey
Bu film arı edir.

892
00:42:04,020 --> 00:42:06,880
>> Nə saxlanılması haqqında lal
video sıkıştırılmamış?

893
00:42:06,880 --> 00:42:11,420
Bu video saxlamaq üçün tullantıların növü var
Dörd təxminən eyni images kimi

894
00:42:11,420 --> 00:42:13,670
yalnız insofar arı olduğu kimi fərqlənir.

895
00:42:13,670 --> 00:42:16,280
Siz üz atmaq ən
ki, informasiya

896
00:42:16,280 --> 00:42:20,190
və yalnız xatırlayıram, məsələn,
ilk çərçivəsində və son çərçivəsində,

897
00:42:20,190 --> 00:42:22,180
Siz var əgər əsas çərçivəsində
heç söz eşitdim

898
00:42:22,180 --> 00:42:24,337
və yalnız saxlamaq
arı orta.

899
00:42:24,337 --> 00:42:26,170
Və yoxdur
, çəhrayı bütün saxlamaq

900
00:42:26,170 --> 00:42:28,330
mavi, və və
yaşıl dəyərlər həmçinin.

901
00:42:28,330 --> 00:42:31,200
Belə ki, bu yalnız ki, demək deyil
sıxılma hər yerdə var.

902
00:42:31,200 --> 00:42:34,900
Bu tez-tez istifadə bir texnika var
bu gün verilən və ya almaq.

903
00:42:34,900 --> 00:42:38,750
>> Amma necə mətn kompres edirsiniz?

904
00:42:38,750 --> 00:42:40,450
Necə mətn kompressor haqqında getmək yoxdur?

905
00:42:40,450 --> 00:42:45,410
Bəli, simvol hər
Ascii bir byte, səkkiz bit edir.

906
00:42:45,410 --> 00:42:47,360
Və bu cür lal, doğru?

907
00:42:47,360 --> 00:42:51,160
Yəqin ki, bir növü, çünki
və E və mən və O və U bir çox

908
00:42:51,160 --> 00:42:55,270
daha tez-tez W və ya Q ya Z kimi çox,
dil asılı olaraq hansı

909
00:42:55,270 --> 00:42:56,610
Siz əlbəttə ki, yazılı etdiyiniz.

910
00:42:56,610 --> 00:42:59,600
Və belə ki, niyə biz istifadə olunur
hər hərf üçün səkkiz bit,

911
00:42:59,600 --> 00:43:02,040
ən azı, o cümlədən
Məşhur məktublar, sağ?

912
00:43:02,040 --> 00:43:05,300
Nə üçün az bit istifadə
super məşhur məktublar,

913
00:43:05,300 --> 00:43:07,760
E kimi şeylər tapmaq
ilk Fortune Təkər ilə,

914
00:43:07,760 --> 00:43:10,450
və daha çox bit istifadə
az məşhur məktublar?

915
00:43:10,450 --> 00:43:10,950
Niyə?

916
00:43:10,950 --> 00:43:13,130
Biz yalnız olacaq, çünki
az tez-tez istifadə edin.

917
00:43:13,130 --> 00:43:15,838
>> Bəli, bu var ki, həyata çevirir
Bunu etmək üçün edilən cəhdlər olmuşdur.

918
00:43:15,838 --> 00:43:18,630
Və grade geri əgər
məktəb və ya orta məktəb, Morse kodu.

919
00:43:18,630 --> 00:43:20,400
Morse kodu nöqtələr var
və tire ola bilər ki,

920
00:43:20,400 --> 00:43:24,270
bir tel kimi boyunca ötürülən
səslər və ya bir növ siqnalları.

921
00:43:24,270 --> 00:43:25,930
Amma Morse kodu super təmiz.

922
00:43:25,930 --> 00:43:29,010
Bu bir ikili sistem növü var
ki, nöqtə və ya tire var.

923
00:43:29,010 --> 00:43:30,977
Amma, məsələn, iki nöqtələr görürsünüzsə.

924
00:43:30,977 --> 00:43:33,810
Yoxsa operator geri düşünüyorsanız
kim, beep, beep, beep kimi gedir

925
00:43:33,810 --> 00:43:36,760
beep, bir az trigger vuruş
ki, bir siqnal ötürür,

926
00:43:36,760 --> 00:43:40,360
əgər, alıcı, iki qəbul
nöqtələr, nə mesaj almış?

927
00:43:40,360 --> 00:43:43,490
Tamamilə əsassız.

928
00:43:43,490 --> 00:43:44,450
>> Mən?

929
00:43:44,450 --> 00:43:45,060
Mən?

930
00:43:45,060 --> 00:43:47,500
Və ya nə about-- ya mən?

931
00:43:47,500 --> 00:43:49,570
Bəlkə yalnız iki E sağ idi?

932
00:43:49,570 --> 00:43:52,480
Belə ki, bu problem var
Morse ilə decodability of

933
00:43:52,480 --> 00:43:54,890
indeksi, vasitəsi halda
sizə göndərməklə şəxs

934
00:43:54,890 --> 00:43:59,510
həqiqətən belə ki, sıralayabilirsiniz duraklamalar
və ya məktubları arasında boşluqlar eşitmək,

935
00:43:59,510 --> 00:44:02,990
yalnız kifayət qədər deyil
adet sıfır və olanları bir axın göndərmək,

936
00:44:02,990 --> 00:44:05,610
və ya nöqtə və tire,
qeyri var, çünki.

937
00:44:05,610 --> 00:44:08,640
E bir dot, belə ki, əgər
iki nöqtələr və ya iki nöqtələr eşitmək,

938
00:44:08,640 --> 00:44:11,254
bəlkə iki E-nin və ya bəlkə bir I. var

939
00:44:11,254 --> 00:44:13,670
Beləliklə, biz bir var bir sistem lazımdır
daha ağıllı az.

940
00:44:13,670 --> 00:44:16,851
Belə ki, bir adam adına Huffman il
bundan məhz bu ilə gəldi.

941
00:44:16,851 --> 00:44:18,600
Belə ki, biz yalnız olacaq
sürətli bir nəzər almaq

942
00:44:18,600 --> 00:44:20,114
necə ağaclar bu ilgili var.

943
00:44:20,114 --> 00:44:22,530
Bu bir olduğunu düşünək
göndərmək istədiyiniz axmaq mesaj,

944
00:44:22,530 --> 00:44:26,342
yalnız A, B ibarət C D's və E-nin,
lakin ixtisar bir çox burada var.

945
00:44:26,342 --> 00:44:27,550
İngilis olmaq üçün nəzərdə deyil.

946
00:44:27,550 --> 00:44:28,341
Bu şifrelenmiş deyil.

947
00:44:28,341 --> 00:44:30,540
Bu, sadəcə bir axmaq mesaj var
təkrar çox.

948
00:44:30,540 --> 00:44:34,010
Siz həqiqətən saymaq əgər Belə ki, bütün
A, B, C, D's, və E-nin, burada

949
00:44:34,010 --> 00:44:34,890
tezliyi.

950
00:44:34,890 --> 00:44:37,800
Məktubları 20%
A, məktublar 45%

951
00:44:37,800 --> 00:44:39,660
E-nin və digər üç tezliklərin.

952
00:44:39,660 --> 00:44:41,960
Biz əl orada sayılır
və yalnız riyaziyyat etdi.

953
00:44:41,960 --> 00:44:44,579
>> Belə ki, çıxır ki,
Huffman, bir müddət əvvəl,

954
00:44:44,579 --> 00:44:46,620
Bilirsiniz ki, həyata
nə, mən bina başlamaq əgər

955
00:44:46,620 --> 00:44:51,172
bir ağac və ya ağac meşə, Siz,
Aşağıdakı kimi, mən aşağıdakıları edə bilərsiniz.

956
00:44:51,172 --> 00:44:53,880
Mən hər bir node vermək gedirəm
Mən qayğı məktubları

957
00:44:53,880 --> 00:44:55,530
Mən saxlamaq üçün gedirəm
ki, node daxilində

958
00:44:55,530 --> 00:44:58,610
üzən nöqtəsi kimi tezliklərin
dəyəri, və ya siz də bir N istifadə edə bilər

959
00:44:58,610 --> 00:45:00,210
lakin biz burada bir float istifadə edəcəyik.

960
00:45:00,210 --> 00:45:03,100
Və alqoritm ki,
o ki, təklif

961
00:45:03,100 --> 00:45:07,210
bir node bu meşə almaq
ağac, belə ki, super qısa ağacları,

962
00:45:07,210 --> 00:45:11,920
və onları birləşdirən başlayın
yeni qruplar, yeni valideynlər, Siz.

963
00:45:11,920 --> 00:45:16,150
Və seçerek bunu
bir zamanda iki kiçik tezliklərin.

964
00:45:16,150 --> 00:45:18,110
Belə ki, 10% və 10% etdi.

965
00:45:18,110 --> 00:45:19,090
Mən yeni node yaratmaq.

966
00:45:19,090 --> 00:45:20,910
Mən yeni node 20% çağırırıq.

967
00:45:20,910 --> 00:45:22,750
>> Hansı iki qovşaqlarının mən növbəti birləşdirmək?

968
00:45:22,750 --> 00:45:23,810
Bu bir az qeyri-müəyyən var.

969
00:45:23,810 --> 00:45:26,643
Belə ki, bəzi künc hallarda var
hesab, lakin olduqca şeyi saxlamaq üçün,

970
00:45:26,643 --> 00:45:29,300
Mən 20% seçmək gedirəm -
İndi uşaqlar bilməz.

971
00:45:29,300 --> 00:45:33,640
Mən 20% seçmək gedirəm və
15% və iki yeni kənarları cəlb edir.

972
00:45:33,640 --> 00:45:35,624
Və indi iki qovşaqlarının
Mən məntiqi birləşdirmək edirsiniz?

973
00:45:35,624 --> 00:45:38,540
Bütün uşaqlar, bütün Yoksay
nəvələri, yalnız kökləri baxmaq

974
00:45:38,540 --> 00:45:39,070
indi.

975
00:45:39,070 --> 00:45:42,220
Hansı iki qovşaqlarının mən birlikdə bağlamaq edirsiniz?

976
00:45:42,220 --> 00:45:44,530
Point iki 0.35.

977
00:45:44,530 --> 00:45:45,890
Belə ki, mənə iki yeni kənarları cəlb edək.

978
00:45:45,890 --> 00:45:47,570
Və sonra mən yalnız bir sol var.

979
00:45:47,570 --> 00:45:48,650
Belə ki, burada bir ağac var.

980
00:45:48,650 --> 00:45:51,160
Və qəsdən tərtib edilmişdir
cür olduqca baxmaq üçün,

981
00:45:51,160 --> 00:45:55,870
lakin kənarları olduğunu fark
də sıfır və bir etiketlendi.

982
00:45:55,870 --> 00:45:59,510
Belə ki, sol kənarları bütün sıfır var
özbaşına, lakin ardıcıl.

983
00:45:59,510 --> 00:46:01,170
Bütün hüquqlar kənarları olanlardır.

984
00:46:01,170 --> 00:46:05,070
>> Və belə Hoffman, təklif olunan nə
Bir B təmsil etmək istəyirsinizsə,

985
00:46:05,070 --> 00:46:10,080
kimi sayı 66 təmsil daha çox
səkkiz bütün bit bir Ascii,

986
00:46:10,080 --> 00:46:13,360
nə, yalnız mağaza bilirik
model sıfır, sıfır, sıfır,

987
00:46:13,360 --> 00:46:17,030
sıfır ki, yol, çünki
Mənim ağacdan, cənab Huffman nin ağac,

988
00:46:17,030 --> 00:46:18,600
kökündən yarpaq.

989
00:46:18,600 --> 00:46:20,970
Bir saxlamaq istəyirsinizsə
E, əksinə, deyil

990
00:46:20,970 --> 00:46:26,290
bir E. təmsil səkkiz bit göndər
Əksinə, bit nə model göndərmək?

991
00:46:26,290 --> 00:46:26,890
Biri.

992
00:46:26,890 --> 00:46:30,410
Və bu barədə gözəl nə var
ki, E ən məşhur məktub,

993
00:46:30,410 --> 00:46:32,340
və istifadə etdiyiniz
bunun üçün ən qısa kodu.

994
00:46:32,340 --> 00:46:34,090
növbəti ən məşhur
məktub kimi görünür

995
00:46:34,090 --> 00:46:37,380
A. idi Və neçə bit
o istifadə təklif etdi?

996
00:46:37,380 --> 00:46:38,270
Zero, bir.

997
00:46:38,270 --> 00:46:41,060
>> Və həyata çünki
bu ağac kimi, indi

998
00:46:41,060 --> 00:46:43,350
Mənə var müəyyən edək
Morse kimi heç bir qeyri

999
00:46:43,350 --> 00:46:46,090
kodu bütün çünki
siz qayğısına məktubları

1000
00:46:46,090 --> 00:46:48,780
bu kənarları sonunda var.

1001
00:46:48,780 --> 00:46:50,580
Belə ki, yalnız biri
bir ağac tətbiqi.

1002
00:46:50,580 --> 00:46:52,538
Bu is-- və mən dalğa lazımdır
Bu mənim əl necə

1003
00:46:52,538 --> 00:46:55,570
C strukturu kimi bu həyata bilər.

1004
00:46:55,570 --> 00:46:58,260
Biz yalnız birləşdirmək lazımdır
simvolu, bir char kimi,

1005
00:46:58,260 --> 00:46:59,910
və tezlik sol və sağ.

1006
00:46:59,910 --> 00:47:02,510
Amma iki baxaq
son nümunələri will

1007
00:47:02,510 --> 00:47:06,070
sonra olduqca tanış
problem viktorina sıfır beş seçin.

1008
00:47:06,070 --> 00:47:09,210
>> Belə ki, data strukturu var
bir hash masa kimi tanınır.

1009
00:47:09,210 --> 00:47:12,247
Və bir hash table cür deyil
Bu buketler var ki, sərin.

1010
00:47:12,247 --> 00:47:14,830
Və dörd buketler var güman
Burada yalnız dörd boş fəzalarında.

1011
00:47:14,830 --> 00:47:20,830
Burada burada kartlar göyərtə, və
klub, bel, klub, brilyant, klub,

1012
00:47:20,830 --> 00:47:25,960
brilyant, klub, brilyant,
clubs-- bu təsadüfi deyil.

1013
00:47:25,960 --> 00:47:30,330
Hearts, hearts-- mən deyiləm
burada vəsaitlərin bütün bucketizing.

1014
00:47:30,330 --> 00:47:32,430
Və bir hash table ehtiyacları
Sizin giriş baxmaq,

1015
00:47:32,430 --> 00:47:34,850
və sonra müəyyən qoyun
Siz görmək nə əsasında yer.

1016
00:47:34,850 --> 00:47:35,600
Bu alqoritm var.

1017
00:47:35,600 --> 00:47:37,980
Mən bir super istifadə
sadə vizual alqoritmi.

1018
00:47:37,980 --> 00:47:40,030
ən ağır hissəsi idi
şəkillər idi nə xatırlayaraq.

1019
00:47:40,030 --> 00:47:41,590
Və sonra dörd ümumi şeylər var.

1020
00:47:41,590 --> 00:47:45,440
>> İndi çıxarıcı borular, artan olan
Burada qəsdən dizayn şeydir.

1021
00:47:45,440 --> 00:47:46,540
Amma başqa nə edə bilər?

1022
00:47:46,540 --> 00:47:49,080
Belə ki, həqiqətən, burada biz bir
köhnə məktəb imtahan kitab dəstə.

1023
00:47:49,080 --> 00:47:51,240
Bir dəstə Tutaq ki,
tələbələr adları burada var.

1024
00:47:51,240 --> 00:47:52,570
Burada böyük bir hash masa var.

1025
00:47:52,570 --> 00:47:54,867
Əvəzində dörd buketler,
Mən 26 deyək var.

1026
00:47:54,867 --> 00:47:57,950
Və biz 26 borc getmək istəmədi
kənarda [olan şeylər? Annenberg?], Belə ki,

1027
00:47:57,950 --> 00:48:00,289
burada təmsil ki, beş deyil
A Z. vasitəsilə və əgər mən

1028
00:48:00,289 --> 00:48:03,580
, adı A ilə başlayır bir tələbə görmək
Mən orada onun viktorina qoymaq üçün gedirəm.

1029
00:48:03,580 --> 00:48:08,850
Kimsə C başlayır, orada,
A-- həqiqətən, bunu istəmədi.

1030
00:48:08,850 --> 00:48:10,060
B burada gedir.

1031
00:48:10,060 --> 00:48:13,390
Beləliklə, mən var A və B və C. Və
İndi burada başqa bir şagird var.

1032
00:48:13,390 --> 00:48:16,212
Amma bu hash table əgər
bir sıra ilə həyata keçirilən,

1033
00:48:16,212 --> 00:48:17,920
I növ berbat alıram
bu nöqtədə, sağ?

1034
00:48:17,920 --> 00:48:19,510
I növ bu yerdə qoymaq lazımdır.

1035
00:48:19,510 --> 00:48:24,380
>> Mən bu həll edə bilər bir yolu bütün var
sağ, A C məşğul, B məşğul, məşğul olur.

1036
00:48:24,380 --> 00:48:28,880
Mən Belə ki, D. onu qoymaq gedirəm
ilk, mən təsadüfi anında erişim

1037
00:48:28,880 --> 00:48:31,064
tələbələr üçün buketler hər.

1038
00:48:31,064 --> 00:48:33,230
Amma indi bu cür keçir ki,
bir şey xətti daxil,

1039
00:48:33,230 --> 00:48:36,750
Mən kimsə üçün axtarmaq istəyirsinizsə, çünki
onun adı ilə başlayır, mən burada yoxlayın.

1040
00:48:36,750 --> 00:48:38,854
Amma bu deyil
I arıyorum tələbə,

1041
00:48:38,854 --> 00:48:41,520
I növ yoxlanılması başlamaq üçün
buketler, mən nə çünki

1042
00:48:41,520 --> 00:48:44,530
bir xətti sort idi
data strukturu sonda.

1043
00:48:44,530 --> 00:48:47,710
Yalnız baxmaq deyərək bir axmaq yol
ilk mövcud açılması üçün,

1044
00:48:47,710 --> 00:48:51,850
və, belə danışmaq, bir B planı kimi qoymaq
və ya bu halda plan D, dəyəri

1045
00:48:51,850 --> 00:48:53,340
əvəzinə yeri.

1046
00:48:53,340 --> 00:48:56,470
Bu ki, varsa, yalnız belə
26 yeri və heç bir tələbə var

1047
00:48:56,470 --> 00:49:00,600
Adı Q ya Z, ya bir şey kimi ilə
ki, ən azı kosmik istifadə edirik.

1048
00:49:00,600 --> 00:49:03,140
>> Amma biz artıq gördük
burada ağıllı həllər, sağ?

1049
00:49:03,140 --> 00:49:04,870
Əvəzinə nə edərdiniz
Bir toqquşma varsa?

1050
00:49:04,870 --> 00:49:06,670
Iki nəfər varsa
adı A, nə olardı

1051
00:49:06,670 --> 00:49:09,160
asan və ya daha çox olmuşdur
Yalnız intuitiv həll

1052
00:49:09,160 --> 00:49:12,840
D olması ehtimal edilir A qoyulması?

1053
00:49:12,840 --> 00:49:14,810
Niyə yalnız getmək deyil
kənarda [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
malloc, başqa node kimi, qoyun
Burada və sonra burada bir tələbə qoymaq.

1055
00:49:19,960 --> 00:49:22,120
Mən mahiyyətcə var ki,
bir sıra bir növ,

1056
00:49:22,120 --> 00:49:25,590
və ya biz etdiyiniz kimi bəlkə daha zərif
bir bağlı siyahısını görmək üçün başlayır.

1057
00:49:25,590 --> 00:49:29,520
>> Və belə bir hash table bir strukturu
ki, yalnız bu kimi baxmaq bilər

1058
00:49:29,520 --> 00:49:33,900
lakin daha ağıllı, bir şey deyilən
ayrı-ayrı chaining, qovuşdurmağımız bir hash table

1059
00:49:33,900 --> 00:49:38,340
sadəcə bir sıra hər edir
Onun elementləri bir sıra deyil,

1060
00:49:38,340 --> 00:49:40,470
bir bağlı siyahı özü edir.

1061
00:49:40,470 --> 00:49:45,080
Siz super sürətli çıxış almaq ki,
olduğu üçün dəyər hash qərar.

1062
00:49:45,080 --> 00:49:48,059
Çox kartları misal ilə kimi,
Mən super sürətli qərar qəbul edib.

1063
00:49:48,059 --> 00:49:49,600
Hearts brilyant burada gedir, burada gedir.

1064
00:49:49,600 --> 00:49:52,180
Burada eyni, A burada gedir,
D B burada gedir, burada gedir.

1065
00:49:52,180 --> 00:49:55,740
Belə ki, super sürətli göz-up, və əgər
Bir halda daxil ola

1066
00:49:55,740 --> 00:49:59,429
Siz var toqquşma, iki
eyni adlı insanlar, yaxşı, sonra

1067
00:49:59,429 --> 00:50:00,970
Yalnız birlikdə onları birləşdirən başlayın.

1068
00:50:00,970 --> 00:50:03,900
Və bəlkə onlara sıralanır saxlamaq
əlifba sırası ilə, bəlkə deyil.

1069
00:50:03,900 --> 00:50:05,900
Amma ən azı indi dinamizm var.

1070
00:50:05,900 --> 00:50:10,250
Belə ki, bir tərəfdən biz super sürətli var
daimi vaxt, və xətti vaxt növ

1071
00:50:10,250 --> 00:50:14,110
bu bağlı siyahıları əgər cəlb
bir az uzun almaq üçün başlamaq.

1072
00:50:14,110 --> 00:50:16,880
>> Belə ki, bir silly bu cür,
bundan geeky zarafat il.

1073
00:50:16,880 --> 00:50:19,590
CS50 hack-a-Thon da,
tələbələr yoxlamaq zaman,

1074
00:50:19,590 --> 00:50:22,040
bir TF və ya CA hər il
düşünür onu qoymaq komik

1075
00:50:22,040 --> 00:50:27,772
Bu kimi bir ibrət, burada yalnız
adı A ilə başlayır əgər o deməkdir ki,

1076
00:50:27,772 --> 00:50:28,870
Bu yol getmək.

1077
00:50:28,870 --> 00:50:31,110
Adınızı başlayır
B ilə şeylərdir OK getmək,

1078
00:50:31,110 --> 00:50:33,290
bəlkə daha sonra dövr komik.

1079
00:50:33,290 --> 00:50:36,420
Amma başqa bir var
də bunu yol.

1080
00:50:36,420 --> 00:50:37,410
Geri gəlir.

1081
00:50:37,410 --> 00:50:38,600
>> Belə ki, bu quruluş var.

1082
00:50:38,600 --> 00:50:40,420
Bu da son
Bu gün strukturu,

1083
00:50:40,420 --> 00:50:42,400
olan trie deyilən bir şey var.

1084
00:50:42,400 --> 00:50:47,140
Nədənsə qısa T-R-I-E,
alınması üçün, lakin trie deyirlər.

1085
00:50:47,140 --> 00:50:51,389
Belə ki, bir trie bir maraqlı
bu ideyaların bir çox amalgam.

1086
00:50:51,389 --> 00:50:52,930
Biz əvvəl gördüm bir ağac var.

1087
00:50:52,930 --> 00:50:54,180
Bu ikili axtarış ağac deyil.

1088
00:50:54,180 --> 00:50:58,410
Bu uşaqların hər hansı bir sayı ilə bir ağac var
lakin trie uşaqların hər

1089
00:50:58,410 --> 00:51:00,090
bir sıra edir.

1090
00:51:00,090 --> 00:51:04,790
Ölçüsü bir sıra, 26 və ya bəlkə 27 demək
Siz hyphenated adları dəstək istəyirsinizsə

1091
00:51:04,790 --> 00:51:06,790
və ya insanların adları apostrophes.

1092
00:51:06,790 --> 00:51:08,280
>> Və bu bir data strukturu.

1093
00:51:08,280 --> 00:51:10,290
Və üst baxsaq
alt, kimi, əgər

1094
00:51:10,290 --> 00:51:13,710
, var top node, M baxmaq
orada leftmost şey işarə edərək,

1095
00:51:13,710 --> 00:51:17,665
daha sonra A, X, W, E, L, L. Bu edir
yalnız bir data strukturu ki, özbaşına

1096
00:51:17,665 --> 00:51:19,120
insanların adları saxlanılması edir.

1097
00:51:19,120 --> 00:51:25,720
Və Maxwell yalnız aşağıdakı saxlanılır
array array serialın bir yol.

1098
00:51:25,720 --> 00:51:30,050
Bir trie haqqında Amma gözəl nə var
ki, bir bağlı siyahı isə hətta

1099
00:51:30,050 --> 00:51:34,520
bir sıra, biz heç kazanılmış etdik ən yaxşı
xətti vaxt və ya logarithmic vaxt axtarır

1100
00:51:34,520 --> 00:51:35,600
kimsə.

1101
00:51:35,600 --> 00:51:40,530
Bir trie Bu data strukturu, əgər
Mənim data structure bu bir adı var

1102
00:51:40,530 --> 00:51:43,720
və mən Maxwell arıyorum, Mən
olduqca tez onu tapmaq üçün gedir.

1103
00:51:43,720 --> 00:51:47,910
Mən yalnız M-A-X-W-E-L-L axtarmaq. Əgər
Bu data strukturu, əksinə,

1104
00:51:47,910 --> 00:51:51,830
bir var, əgər N, bir milyon əgər
Bu data strukturu milyon adları,

1105
00:51:51,830 --> 00:51:57,100
Maxwell hələ olacaq
discoverable yalnız M-A-X-W-E-L-L sonra

1106
00:51:57,100 --> 00:51:58,090
addımlar.

1107
00:51:58,090 --> 00:52:01,276
Və, David D-A-V-I-D addımlar.

1108
00:52:01,276 --> 00:52:03,400
Başqa sözlə, tikinti
bir data strukturu

1109
00:52:03,400 --> 00:52:07,240
var bu serialların bütün olan
özləri təsadüfi giriş dəstək

1110
00:52:07,240 --> 00:52:11,090
Mən insanların axtarır başlaya bilərsiniz
ki, bir zaman məbləği istifadə edərək ad

1111
00:52:11,090 --> 00:52:14,340
Biz sayına proporsional
məlumat strukturu şeyi,

1112
00:52:14,340 --> 00:52:16,330
kimi bir milyon mövcud adları.

1113
00:52:16,330 --> 00:52:20,135
Bu tapmaq üçün mənə lazım vaxt məbləği
M-A-X-W-E-L-L Bu data strukturu deyil

1114
00:52:20,135 --> 00:52:22,260
proporsional deyil
məlumat strukturu ölçüsü,

1115
00:52:22,260 --> 00:52:25,930
lakin adı uzunluğu.

1116
00:52:25,930 --> 00:52:28,440
Və real
adları biz aradığınız

1117
00:52:28,440 --> 00:52:29,970
heç uzun crazy olacaq.

1118
00:52:29,970 --> 00:52:32,600
Bəlkə kimsə 10 xarakter daşıyır
20 xarakter adı.

1119
00:52:32,600 --> 00:52:33,900
Bu hüququ, əlbəttə məhdud var?

1120
00:52:33,900 --> 00:52:37,110
Yer üzündə bir insan var olan
uzun mümkün adı var,

1121
00:52:37,110 --> 00:52:39,920
lakin adı sabit deyil
dəyəri uzunluğu, sağ?

1122
00:52:39,920 --> 00:52:41,980
Hər hansı bir mənada fərqli deyil.

1123
00:52:41,980 --> 00:52:45,090
Belə ki, bu şəkildə, biz
bir veri strukturu əldə

1124
00:52:45,090 --> 00:52:47,800
ki, daimi vaxt göz-up edir.

1125
00:52:47,800 --> 00:52:50,670
Bu addımlar bir sıra almaq yoxdur
giriş uzunluğu asılı olaraq,

1126
00:52:50,670 --> 00:52:54,250
adı, lakin sayı
data strukturu.

1127
00:52:54,250 --> 00:52:58,700
Biz adları sayı ikiqat Belə ki
bir milyard iki gələn il,

1128
00:52:58,700 --> 00:53:03,720
tapıntı Maxwell etmək niyyətindədir
yeddi addımlar eyni sayı

1129
00:53:03,720 --> 00:53:04,650
onu tapmaq üçün.

1130
00:53:04,650 --> 00:53:08,810
Və belə ki, biz əldə etdik görünür
zaman çalışan bizim müqəddəs grail.

1131
00:53:08,810 --> 00:53:10,860
>> Belə ki, tez elanlar bir neçə.

1132
00:53:10,860 --> 00:53:11,850
Quiz sıfır gəlir.

1133
00:53:11,850 --> 00:53:14,600
Kurs saytında ki, daha çox
gün növbəti neçə üzərində.

1134
00:53:14,600 --> 00:53:17,120
Bazar ertəsi nin bir bayram məruzə
burada Harvard bazar ertəsi.

1135
00:53:17,120 --> 00:53:18,850
Bu, New Haven deyil
belə ki, biz sinif alaraq edirik

1136
00:53:18,850 --> 00:53:20,310
bazar ertəsi mühazirə üçün New Haven üçün.

1137
00:53:20,310 --> 00:53:22,550
Hər şey film olur
və həmişə olduğu kimi canlı axın

1138
00:53:22,550 --> 00:53:24,900
lakin bu gün son qoy
30 ikinci clip ilə

1139
00:53:24,900 --> 00:53:26,910
qondarma "Deep düşüncələr"
Daven Farnham tərəfindən hansı

1140
00:53:26,910 --> 00:53:30,850
Şənbə tərəfindən keçən il ilham
Night Live "Deep düşüncələr"

1141
00:53:30,850 --> 00:53:35,700
Jack Handy tərəfindən hansı
İndi mənada etməlidir.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: İndi "Deep
Daven Farnham tərəfindən düşüncələr ".

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash masa.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> HOPARLÖR 1: Yaxşı ki, indi üçün var.

1147
00:53:47,660 --> 00:53:48,805
Biz gələn həftə görəcəksiniz.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: aksiyada görmək üçün.

1150
00:53:56,680 --> 00:53:58,304
Belə ki, indi ki, bir nəzər salaq.

1151
00:53:58,304 --> 00:53:59,890
Odur ki, biz çeşidlənməmiş sıra var.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, siz irəlidə və yenidən getmək bilər
yalnız bir ikinci bu edin.

1153
00:54:04,860 --> 00:54:08,562
Bütün sağ, kameralar, belə ki, yuvarlanan olunur
fəaliyyət Doug, hazır zaman, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Bütün sağ, belə nə biz
burada var çeşidlənməmiş sıra edir.

1155
00:54:11,020 --> 00:54:13,960
Mən elementləri bütün rəngli etdik
əslində olduğunu göstərir qırmızı,

1156
00:54:13,960 --> 00:54:14,460
çeşidlənməmiş.

1157
00:54:14,460 --> 00:54:17,960
Belə ki, ilk şey ki, geri
Biz serialın sol yarım sort edir.

1158
00:54:17,960 --> 00:54:20,630
Sonra biz hüququ sort
serialın yarısı.

1159
00:54:20,630 --> 00:54:22,830
Və ya-da, ya-da, ya-da,
biz onları birlikdə birləşməsi.

1160
00:54:22,830 --> 00:54:24,520
Və biz tamamilə sıralanır array var.

1161
00:54:24,520 --> 00:54:25,360
Belə ki, işləri sort daxil necə.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Vay, Vay, Whoa,
cut kəsilmiş, cut, kəsdi.

1163
00:54:27,109 --> 00:54:30,130
Doug, yalnız ya-da bilməz, ya-da,
ya-da, birləşməsi növ vasitəsilə yol.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Mən yalnız etdi.

1165
00:54:31,970 --> 00:54:32,832
Bu yaxşıdır.

1166
00:54:32,832 --> 00:54:33,540
Biz getmək iyi.

1167
00:54:33,540 --> 00:54:34,760
Yalnız yayma saxlamaq edək.

1168
00:54:34,760 --> 00:54:35,380
Belə ki, hər halda,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Siz izah etmək
Bu daha tam daha.

1170
00:54:37,800 --> 00:54:39,999
Bu yalnız kifayət deyil.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, biz deyil
biri geri getmək lazımdır.

1172
00:54:41,790 --> 00:54:42,350
Bu yaxşıdır.

1173
00:54:42,350 --> 00:54:45,690
Belə ki, hər halda, biz merge-- ilə davam
Ian, biz çəkiliş ortasında istəyirik.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Mən bilirəm.

1175
00:54:46,612 --> 00:54:49,320
Və biz yalnız ya-da bilməz, ya-da,
bütün prosesi vasitəsilə ya-da.

1176
00:54:49,320 --> 00:54:52,200
Siz necə izah etmək
iki tərəf birlikdə birləşdi almaq.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Amma biz artıq var
izah necə iki sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Siz yalnız göstərilən etdik
onlara birləşməsi array.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Onlar prosesi bilirik.

1180
00:54:56,486 --> 00:54:57,172
Onlar gözəl istəyirik.

1181
00:54:57,172 --> 00:54:58,380
Biz artıq on dəfə getdi etdik.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Siz yalnız sağ üzərində atlandı.

1183
00:55:00,330 --> 00:55:03,360
Biz bir geri olacaq, siz
artıq siz ya-da, ya-da bilməz.

1184
00:55:03,360 --> 00:55:05,480
Geri bir bütün hüququ.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Mən geri getmək üçün var
slaydlar bütün vasitəsilə?

1186
00:55:07,833 --> 00:55:08,332
My God.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Bu altıncı dəfə, Ian kimi.

1189
00:55:13,004 --> 00:55:13,940
Bu yaxşıdır.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Bütün hüququ.

1191
00:55:15,200 --> 00:55:16,590
Hazır edirsiniz?

1192
00:55:16,590 --> 00:55:17,400
Great.

1193
00:55:17,400 --> 00:55:18,950
Fəaliyyət.