1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Bəzən, bina bir
proqram, siz istifadə etmək istədiyiniz bilər bir

3
00:00:10,890 --> 00:00:13,190
bir lüğət kimi tanınan data strukturu.

4
00:00:13,190 --> 00:00:17,960
Olan A lüğət xəritələr açarları,
adətən strings, dəyərlərə, ints,

5
00:00:17,960 --> 00:00:21,900
chars, bir obyekt bir göstərici,
biz istədiyiniz hər hansı.

6
00:00:21,900 --> 00:00:26,510
Bu yalnız adi lüğətlərin kimi
anlayışlar vasitəsilə xəritəsi sözləri.

7
00:00:26,510 --> 00:00:29,440
>> Lüğətlər ilə bizi təmin
məlumat saxlamaq üçün qabiliyyəti

8
00:00:29,440 --> 00:00:32,750
bir şey ilə bağlı
və sonra bu qədər baxmaq.

9
00:00:32,750 --> 00:00:36,620
Belə ki, necə biz, həqiqətən, həyata yoxdur bir
C kodu, demək, lüğət ki, biz

10
00:00:36,620 --> 00:00:38,460
bizim proqramları bir istifadə?

11
00:00:38,460 --> 00:00:41,790
Yaxşı, yolları bir çox var ki,
biz bir lüğət həyata bilər.

12
00:00:41,790 --> 00:00:45,930
>> Bir üçün, biz bir sıra istifadə edə bilər ki, biz
dinamik yenidən ölçüsü və ya bir istifadə edə bilər

13
00:00:45,930 --> 00:00:49,150
bağlı siyahı, hash table
və ya bir ikili ağac.

14
00:00:49,150 --> 00:00:52,250
Amma biz seçə nə olursa olsun, biz olmalıdır
səmərəliliyinin zehinli və

15
00:00:52,250 --> 00:00:54,300
həyata keçirilməsi performans.

16
00:00:54,300 --> 00:00:57,930
Biz istifadə alqoritmi haqqında düşünməlidir
daxil edin və daxil maddələr axtarmaq üçün

17
00:00:57,930 --> 00:00:59,120
Bizim data strukturu.

18
00:00:59,120 --> 00:01:03,060
>> Indi üçün, ki biz fərz edək
düymələri kimi strings istifadə etmək istəyirik.

19
00:01:03,060 --> 00:01:07,290
Biri mümkünlüyü haqqında danışmaq edək,
məlumat strukturu bir trie çağırıb.

20
00:01:07,290 --> 00:01:11,210
Belə ki, burada bir vizual nümayəndəliyi var
trie.

21
00:01:11,210 --> 00:01:14,590
>> Şəkil, bir Trie təklif kimi
bir ağac data strukturu

22
00:01:14,590 --> 00:01:16,050
qovşaqlarının birlikdə bağlı.

23
00:01:16,050 --> 00:01:19,420
Biz kök aydın var ki, bax
bəzi links uzanan ilə node

24
00:01:19,420 --> 00:01:20,500
digər qovşaqlarının.

25
00:01:20,500 --> 00:01:23,040
Amma hər node nə ibarətdir?

26
00:01:23,040 --> 00:01:26,700
Biz düymələri saxlanılması edirik ki, güman əgər
yalnız əlifba simvol, və

27
00:01:26,700 --> 00:01:30,150
biz kapitallaşma haqqında qayğı yoxdur,
Burada bir node bir tərif ki,

28
00:01:30,150 --> 00:01:31,100
kifayət edər.

29
00:01:31,100 --> 00:01:34,130
>> Kimin növü bir obyekt struct edir
node iki hissədən ibarətdir

30
00:01:34,130 --> 00:01:35,740
məlumat və uşaqlar çağırıb.

31
00:01:35,740 --> 00:01:39,200
Biz şərh olaraq data iştirak tərk etdik
bir komponenti ilə əvəz olunacaq

32
00:01:39,200 --> 00:01:43,190
struct node zaman bəyannamə
C proqram daxil.

33
00:01:43,190 --> 00:01:47,040
Bir node data hissəsi ola bilər
Göstərir Boolean dəyər və ya

34
00:01:47,040 --> 00:01:51,160
deyil node başa təmsil
Bir lüğət düyməsi və ya bir ola bilər

35
00:01:51,160 --> 00:01:54,240
müəyyən təmsil string
Lüğətə bir söz.

36
00:01:54,240 --> 00:01:58,870
>> Biz göstərmək üçün bir smiley face istifadə edəcəyik
məlumat node mövcud olduqda.

37
00:01:58,870 --> 00:02:02,310
26 elementləri var bizim
uşaqlar array, bir index

38
00:02:02,310 --> 00:02:03,690
əlifba xarakter başına.

39
00:02:03,690 --> 00:02:06,570
Biz əhəmiyyətini görəcəksiniz
tezliklə bu.

40
00:02:06,570 --> 00:02:10,759
>> Nin kök node yaxından nəzər almaq edək
bizim sxemdə, heç bir məlumat var

41
00:02:10,759 --> 00:02:14,740
tərəfindən göstərilən kimi, bu ilə bağlı
the smiley üz olmaması

42
00:02:14,740 --> 00:02:16,110
data hissəsi.

43
00:02:16,110 --> 00:02:19,910
Hissələri uzanan okları
uşaqlar array qeyri-node təmsil

44
00:02:19,910 --> 00:02:21,640
digər qovşaqlarının göstəricilərinə.

45
00:02:21,640 --> 00:02:25,500
Məsələn, arrow uzanan
uşaqların ikinci element

46
00:02:25,500 --> 00:02:28,400
məktub B təmsil
bir lüğət əsas.

47
00:02:28,400 --> 00:02:31,920
Və böyük diaqram
biz B. ilə etiket

48
00:02:31,920 --> 00:02:35,810
>> , Böyük diaqram Qeyd edək ki, zaman biz
başqa node bir göstərici çəkmək, bu

49
00:02:35,810 --> 00:02:39,100
Fərq etməz olduğu arrowhead
digər node görüşüb.

50
00:02:39,100 --> 00:02:43,850
Bizim nümunə lüğət trie şey
iki söz, və zoom.

51
00:02:43,850 --> 00:02:47,040
Nin bir misal vasitəsilə gəzmək edək
bir düyməsi üçün məlumatın axtarır.

52
00:02:47,040 --> 00:02:50,800
>> Biz baxmaq istəyirdi Güman edilən
əsas vanna üçün dəyər müvafiq.

53
00:02:50,800 --> 00:02:53,610
Biz göz başlamaq lazımdır
kök node.

54
00:02:53,610 --> 00:02:57,870
Sonra bizim ilk məktub almaq lazımdır
, əsas B, və müvafiq tapmaq

55
00:02:57,870 --> 00:03:00,020
bizim uşaqlar array spot.

56
00:03:00,020 --> 00:03:04,490
Tam 26 ləkələr var ki, görürsünüz
serialın, hər bir hərf üçün bir

57
00:03:04,490 --> 00:03:05,330
əlifba.

58
00:03:05,330 --> 00:03:08,800
Və biz ləkələr təmsil lazımdır
üçün əlifbasının hərfləri.

59
00:03:08,800 --> 00:03:13,960
>> Biz, sonra ikinci indeksi baxmaq lazımdır
Ümumiyyətlə B. index bir, əgər biz

60
00:03:13,960 --> 00:03:17,990
bəzi əlifba xarakter C, biz var
müvafiq spot müəyyən edə bilər

61
00:03:17,990 --> 00:03:21,520
istifadə uşaqlar array
Bu kimi bir hesablanması.

62
00:03:21,520 --> 00:03:25,140
Biz böyük uşaqlar istifadə edə bilər
biz göz up təklif etmək istəyirdi array əgər

63
00:03:25,140 --> 00:03:28,380
simvol daha geniş düymələri,
belə bütün, kimi

64
00:03:28,380 --> 00:03:29,880
ASCII character set.

65
00:03:29,880 --> 00:03:32,630
>> Bu halda, pointer
bizim uşaqlar array da

66
00:03:32,630 --> 00:03:34,320
index bir null deyil.

67
00:03:34,320 --> 00:03:36,600
Beləliklə, biz axtarır davam edəcəyik
əsas vanna up.

68
00:03:36,600 --> 00:03:40,130
Biz heç bir null göstərici rast varsa
uşaq müvafiq spot da

69
00:03:40,130 --> 00:03:43,230
array biz qovşaqlarının keçdiyi isə,
onda biz biz demək lazımdır

70
00:03:43,230 --> 00:03:45,630
ki düyməsi üçün bir şey tapa bilmədi.

71
00:03:45,630 --> 00:03:49,370
>> İndi biz ikinci məktub və almaq lazımdır
bizim əsas, A, və davam aşağıdakı

72
00:03:49,370 --> 00:03:52,400
bu şəkildə göstəricilərinə biz qədər
Bizim əsas sonuna çatmaq.

73
00:03:52,400 --> 00:03:56,530
Biz olmadan əsas sonuna çatmaq əgər
bir ölü bitir dəyən null göstəricilərinə,

74
00:03:56,530 --> 00:03:59,730
işin burada kimi, sonra biz yalnız
bir şey daha yoxlamaq lazımdır.

75
00:03:59,730 --> 00:04:02,110
Bu əsas deyil, həqiqətən,
Lüğətə?

76
00:04:02,110 --> 00:04:07,660
>> Əgər belədirsə, biz yaxşı, bir dəyər tapmaq lazımdır
Bizim diaqram smiley face icon yerləşir

77
00:04:07,660 --> 00:04:08,750
sözü bitir.

78
00:04:08,750 --> 00:04:12,270
Ilə saxlanılır başqa bir şey varsa
məlumat, sonra biz onu qaytara bilər.

79
00:04:12,270 --> 00:04:16,500
Məsələn, əsas zoo deyil
biz bilər, hətta lüğət,

80
00:04:16,500 --> 00:04:19,810
heç bu əsas sona çatdı
, bir null göstərici vuruş isə biz

81
00:04:19,810 --> 00:04:21,089
trie vasitəsilə təkrarlamaq.

82
00:04:21,089 --> 00:04:25,436
>> Biz əsas vanna axtarmaq üçün cəhd Əgər
Son node array indeksi ikinci,

83
00:04:25,436 --> 00:04:28,750
, məktubu H olardı müvafiq
bir null göstərici keçirilib.

84
00:04:28,750 --> 00:04:31,120
Belə ki, hamam lüğətdə yoxdur.

85
00:04:31,120 --> 00:04:34,800
Və belə bir trie ki, düymələri nadir
aydın saxlanılır heç vaxt

86
00:04:34,800 --> 00:04:36,650
məlumat strukturu.

87
00:04:36,650 --> 00:04:38,810
Belə ki, necə biz bir şey daxil edirsiniz
trie daxil?

88
00:04:38,810 --> 00:04:41,780
>> Nin əsas daxil edək
bizim trie daxil zoo.

89
00:04:41,780 --> 00:04:46,120
Xatırla ki, bir node bir smiley face
bir sadə kodu uyğun bilər

90
00:04:46,120 --> 00:04:50,170
Ki, zoo göstərir Boolean dəyəri
Lüğətə və ya bu ola bilər

91
00:04:50,170 --> 00:04:53,710
Daha ətraflı məlumat üçün uyğun ki, biz
əsas zoo ilə birləşmək arzulayıram,

92
00:04:53,710 --> 00:04:56,860
Bu müəyyən kimi
söz və ya başqa bir şey.

93
00:04:56,860 --> 00:05:00,350
Bəzi yollar, proses daxil
trie daxil bir şey benzer

94
00:05:00,350 --> 00:05:02,060
bir trie bir şey axtarır.

95
00:05:02,060 --> 00:05:05,720
>> Biz, bir daha kök node ilə başlamaq lazımdır
aşağıdakı göstəricilər müvafiq

96
00:05:05,720 --> 00:05:07,990
Bizim əsas məktublar.

97
00:05:07,990 --> 00:05:11,310
Neyse, biz göstəricilərinə əməl edə bildik
biz əldə qədər bütün yol

98
00:05:11,310 --> 00:05:12,770
əsas sonu.

99
00:05:12,770 --> 00:05:16,480
Zoo sözü bir prefiks olduğundan
nın üzvü olan zoom,

100
00:05:16,480 --> 00:05:19,440
lüğət, biz ehtiyac yoxdur
hər hansı bir yeni qovşaqlarının ayırırlar.

101
00:05:19,440 --> 00:05:23,140
>> Biz göstərir node dəyişə bilərsiniz ki,
aparıcı simvol yol

102
00:05:23,140 --> 00:05:25,360
Bu edir bizim lüğət bir əsas təmsil edir.

103
00:05:25,360 --> 00:05:28,630
İndi daxil edək
trie daxil əsas BATH.

104
00:05:28,630 --> 00:05:32,260
Biz kök node başlamaq lazımdır
və yenidən göstəricilərinə baxın.

105
00:05:32,260 --> 00:05:35,620
Amma bu vəziyyət, bir ölü edib
biz əldə edə önce son

106
00:05:35,620 --> 00:05:36,940
əsas sonu.

107
00:05:36,940 --> 00:05:40,980
İndi biz bir sıra yeni ayırmaq lazımdır
qovşaqlarının bir yeni ayırmaq lazımdır

108
00:05:40,980 --> 00:05:43,660
hər qalan üçün node
Bizim əsas məktubu.

109
00:05:43,660 --> 00:05:46,740
>> Bu halda, biz yalnız ehtiyac
yeni bir node ayrılması.

110
00:05:46,740 --> 00:05:50,590
Sonra H index etmək lazımdır
Bu yeni node istinad.

111
00:05:50,590 --> 00:05:54,070
Bir daha, biz node dəyişə bilərsiniz
göstərir ki, simvol yol

112
00:05:54,070 --> 00:05:57,120
ona aparan təmsil
bizim lüğət əsas.

113
00:05:57,120 --> 00:06:00,730
Nin asimptotik haqqında mülahizə edək
Bu üçün prosedurların mürəkkəbliyi

114
00:06:00,730 --> 00:06:02,110
iki əməliyyatları.

115
00:06:02,110 --> 00:06:06,420
>> Qeyd ki, hər iki halda sayı
bizim alqoritm aldı addımlar

116
00:06:06,420 --> 00:06:09,470
sayına mütənasib
söz məktublar.

117
00:06:09,470 --> 00:06:10,220
Bu doğru deyil.

118
00:06:10,220 --> 00:06:13,470
Sizə bir söz axtarmaq istədiyiniz zaman
trie yalnız vasitəsilə təkrarlamaq lazımdır

119
00:06:13,470 --> 00:06:17,100
məktublar bir-bir sizin qədər ya
Bu sözün sonunda və ya çatmaq

120
00:06:17,100 --> 00:06:19,060
trie bir ölü son edib.

121
00:06:19,060 --> 00:06:22,470
>> Və əsas daxil etmək üçün istədiyiniz zaman
istifadə edərək, bir trie daxil dəyər cüt

122
00:06:22,470 --> 00:06:26,250
proseduru biz, ən pis halda müzakirə
Siz yeni node ayrılması olacaq

123
00:06:26,250 --> 00:06:27,550
hər bir hərf üçün.

124
00:06:27,550 --> 00:06:31,290
Və biz ayrılması güman lazımdır
bir daimi zaman əməliyyatdır.

125
00:06:31,290 --> 00:06:35,850
Biz əsas uzunluğu olduğunu güman belə, əgər
sabit sabit, həm də həmsərhəddir

126
00:06:35,850 --> 00:06:39,400
durub və baxmaq daimi var
trie üçün vaxt əməliyyatları.

127
00:06:39,400 --> 00:06:42,930
>> Biz bu ehtimalı yoxdur ki, əgər
əsas uzunluğu sabit ilə həmsərhəddir

128
00:06:42,930 --> 00:06:46,650
daimi, sonra durub və baxmaq,
ən pis halda, xətti olunur

129
00:06:46,650 --> 00:06:48,240
əsas uzunluğu.

130
00:06:48,240 --> 00:06:51,800
Maddələr sayı saxlanılır ki, görürsünüz
trie görünüşünü qədər təsir etmir

131
00:06:51,800 --> 00:06:52,820
və ya durub zaman.

132
00:06:52,820 --> 00:06:55,360
Bu, yalnız təsir edir
əsas uzunluğu.

133
00:06:55,360 --> 00:06:59,300
>> Əksinə, demək, entries əlavə,
bir hash table etmək niyyətindədir

134
00:06:59,300 --> 00:07:01,250
gələcək yavaş baxmaq.

135
00:07:01,250 --> 00:07:04,520
Bu ilk cəlbedici görünə bilər baxmayaraq
yadda saxlamaq lazımdır ki, bir

136
00:07:04,520 --> 00:07:08,740
əlverişli asimptotik mürəkkəbliyi deyil
demək ki, təcrübədə data

137
00:07:08,740 --> 00:07:11,410
strukturu mütləq
tənbeh kənarda.

138
00:07:11,410 --> 00:07:15,860
Biz də saxlamaq üçün hesab lazımdır
pis biz lazımdır trie, söz

139
00:07:15,860 --> 00:07:19,700
halda, qovşaqlarının bir sıra proporsional
sözü özü uzunluğu.

140
00:07:19,700 --> 00:07:21,880
>> Çalışır yer çox istifadə edirlər.

141
00:07:21,880 --> 00:07:25,620
Ki, bir hash masa fərqli var,
biz yalnız bir yeni node lazımdır

142
00:07:25,620 --> 00:07:27,940
bəzi əsas dəyər cüt saxlamayın.

143
00:07:27,940 --> 00:07:31,370
İndi yenə nəzəriyyəsi, böyük kosmik
istehlak böyük kimi görünmür

144
00:07:31,370 --> 00:07:34,620
xüsusilə nəzərə alsaq, məşğul ki, müasir
kompüter gigabayt var və

145
00:07:34,620 --> 00:07:36,180
yaddaş gigabayt.

146
00:07:36,180 --> 00:07:39,200
Amma biz hələ ki, həyata çevirir
yaddaş istifadə və narahat

147
00:07:39,200 --> 00:07:42,540
naminə təşkilat
performance, çünki müasir kompüter

148
00:07:42,540 --> 00:07:46,960
altında yerdə mexanizmləri
yaddaş girişi sürətləndirmək üçün başlıq.

149
00:07:46,960 --> 00:07:51,180
>> Lakin bu mexanizmlər ən yaxşı zaman iş
yaddaş giriş-çıxış kompakt edilir

150
00:07:51,180 --> 00:07:52,810
bölgələrdə və ya sahələrdə.

151
00:07:52,810 --> 00:07:55,910
Və bir trie qovşaqlarının yaşamaq bilər
ki, yığın-yığın yerdə.

152
00:07:55,910 --> 00:07:58,390
Amma bu ticarət-off
biz hesab etməlidir ki,.

153
00:07:58,390 --> 00:08:01,440
>> Bir məlumat seçərkən, Unutmayın ki,
müəyyən bir vəzifə üçün strukturu, biz

154
00:08:01,440 --> 00:08:04,420
haqqında düşünmək lazımdır nə cür
əməliyyatları data strukturu lazımdır

155
00:08:04,420 --> 00:08:07,140
dəstək və nə qədər performance
o hər

156
00:08:07,140 --> 00:08:09,080
bizə əməliyyatları məsələləri.

157
00:08:09,080 --> 00:08:11,300
Bu əməliyyatlar hətta may
yalnız kənara

158
00:08:11,300 --> 00:08:13,430
əsas baxmaq və durub.

159
00:08:13,430 --> 00:08:17,010
Biz bir cür tətbiq etmək istəyirdi Güman
avtomatik tam funksionallıq çox

160
00:08:17,010 --> 00:08:18,890
kimi Google search engine yoxdur.

161
00:08:18,890 --> 00:08:22,210
Ki, bütün düymələri qayıtmaq və
potensial dəyərlər

162
00:08:22,210 --> 00:08:24,130
bir prefiks var.

163
00:08:24,130 --> 00:08:27,050
>> A trie benzersiz faydalıdır
Bu əməliyyat üçün.

164
00:08:27,050 --> 00:08:29,890
Bu vasitəsilə təkrarlamaq üçün sadə var
hər bir xarakter üçün trie

165
00:08:29,890 --> 00:08:30,950
prefiks.

166
00:08:30,950 --> 00:08:33,559
Sadəcə, bir qədər baxmaq əməliyyat kimi
biz göstəricilərinə əməl bilər

167
00:08:33,559 --> 00:08:35,400
xarakteri ilə xarakter.

168
00:08:35,400 --> 00:08:38,659
Sonra, biz sonunda gəldiyi zaman
prefiks, biz vasitəsilə təkrarlamaq bilər

169
00:08:38,659 --> 00:08:42,049
məlumat strukturunun qalan hissəsi
düymələri hər hansı bir kənarda bəri

170
00:08:42,049 --> 00:08:43,980
Bu point prefiks var.

171
00:08:43,980 --> 00:08:47,670
>> Bu siyahı əldə etmək də asan
ildən əlifba sırası ilə

172
00:08:47,670 --> 00:08:50,970
uşaqlar array elementləri
əlifba sırası ilə sifariş olunur.

173
00:08:50,970 --> 00:08:54,420
Belə ki, inşallah hesab edəcəyik
verilməsi cəhd çalışır.

174
00:08:54,420 --> 00:08:56,085
Mən Kevin Schmid oldum və bu CS50 edir.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, bu başlanğıcdır
azalması.

177
00:09:00,790 --> 00:09:01,350
Üzgünüm.

178
00:09:01,350 --> 00:09:01,870
Üzr istəyirik.

179
00:09:01,870 --> 00:09:02,480
Üzr istəyirik.

180
00:09:02,480 --> 00:09:03,130
Üzr istəyirik.

181
00:09:03,130 --> 00:09:03,950
>> Dörd vur.

182
00:09:03,950 --> 00:09:04,360
Mən deyiləm.

183
00:09:04,360 --> 00:09:05,280
Üzr istəyirik.

184
00:09:05,280 --> 00:09:06,500
Üzr istəyirik.

185
00:09:06,500 --> 00:09:07,490
Üzr istəyirik.

186
00:09:07,490 --> 00:09:12,352
Şəxs üçün üzr edən
Bu crazy getmək redaktə var.

187
00:09:12,352 --> 00:09:13,280
>> Üzr istəyirik.

188
00:09:13,280 --> 00:09:13,880
Üzr istəyirik.

189
00:09:13,880 --> 00:09:15,080
Üzr istəyirik.

190
00:09:15,080 --> 00:09:15,680
Üzr istəyirik.

191
00:09:15,680 --> 00:09:16,280
>> HOPARLÖR 1: Maşallah.

192
00:09:16,280 --> 00:09:17,530
Bu, həqiqətən yaxşı oldu.

193
00:09:17,530 --> 00:09:18,430