>> KEVIN SCHMID: Bəzən, bina bir proqram, siz istifadə etmək istədiyiniz bilər bir
bir lüğət kimi tanınan data strukturu.
Olan A lüğət xəritələr açarları, adətən strings, dəyərlərə, ints,
chars, bir obyekt bir göstərici, biz istədiyiniz hər hansı.
Bu yalnız adi lüğətlərin kimi anlayışlar vasitəsilə xəritəsi sözləri.
>> Lüğətlər ilə bizi təmin məlumat saxlamaq üçün qabiliyyəti
bir şey ilə bağlı və sonra bu qədər baxmaq.
Belə ki, necə biz, həqiqətən, həyata yoxdur bir C kodu, demək, lüğət ki, biz
bizim proqramları bir istifadə?
Yaxşı, yolları bir çox var ki, biz bir lüğət həyata bilər.
>> Bir üçün, biz bir sıra istifadə edə bilər ki, biz dinamik yenidən ölçüsü və ya bir istifadə edə bilər
bağlı siyahı, hash table və ya bir ikili ağac.
Amma biz seçə nə olursa olsun, biz olmalıdır səmərəliliyinin zehinli və
həyata keçirilməsi performans.
Biz istifadə alqoritmi haqqında düşünməlidir daxil edin və daxil maddələr axtarmaq üçün
Bizim data strukturu.
>> Indi üçün, ki biz fərz edək düymələri kimi strings istifadə etmək istəyirik.
Biri mümkünlüyü haqqında danışmaq edək, məlumat strukturu bir trie çağırıb.
Belə ki, burada bir vizual nümayəndəliyi var trie.
>> Şəkil, bir Trie təklif kimi bir ağac data strukturu
qovşaqlarının birlikdə bağlı.
Biz kök aydın var ki, bax bəzi links uzanan ilə node
digər qovşaqlarının.
Amma hər node nə ibarətdir?
Biz düymələri saxlanılması edirik ki, güman əgər yalnız əlifba simvol, və
biz kapitallaşma haqqında qayğı yoxdur, Burada bir node bir tərif ki,
kifayət edər.
>> Kimin növü bir obyekt struct edir node iki hissədən ibarətdir
məlumat və uşaqlar çağırıb.
Biz şərh olaraq data iştirak tərk etdik bir komponenti ilə əvəz olunacaq
struct node zaman bəyannamə C proqram daxil.
Bir node data hissəsi ola bilər Göstərir Boolean dəyər və ya
deyil node başa təmsil Bir lüğət düyməsi və ya bir ola bilər
müəyyən təmsil string Lüğətə bir söz.
>> Biz göstərmək üçün bir smiley face istifadə edəcəyik məlumat node mövcud olduqda.
26 elementləri var bizim uşaqlar array, bir index
əlifba xarakter başına.
Biz əhəmiyyətini görəcəksiniz tezliklə bu.
>> Nin kök node yaxından nəzər almaq edək bizim sxemdə, heç bir məlumat var
tərəfindən göstərilən kimi, bu ilə bağlı the smiley üz olmaması
data hissəsi.
Hissələri uzanan okları uşaqlar array qeyri-node təmsil
digər qovşaqlarının göstəricilərinə.
Məsələn, arrow uzanan uşaqların ikinci element
məktub B təmsil bir lüğət əsas.
Və böyük diaqram biz B. ilə etiket
>> , Böyük diaqram Qeyd edək ki, zaman biz başqa node bir göstərici çəkmək, bu
Fərq etməz olduğu arrowhead digər node görüşüb.
Bizim nümunə lüğət trie şey iki söz, və zoom.
Nin bir misal vasitəsilə gəzmək edək bir düyməsi üçün məlumatın axtarır.
>> Biz baxmaq istəyirdi Güman edilən əsas vanna üçün dəyər müvafiq.
Biz göz başlamaq lazımdır kök node.
Sonra bizim ilk məktub almaq lazımdır , əsas B, və müvafiq tapmaq
bizim uşaqlar array spot.
Tam 26 ləkələr var ki, görürsünüz serialın, hər bir hərf üçün bir
əlifba.
Və biz ləkələr təmsil lazımdır üçün əlifbasının hərfləri.
>> Biz, sonra ikinci indeksi baxmaq lazımdır Ümumiyyətlə B. index bir, əgər biz
bəzi əlifba xarakter C, biz var müvafiq spot müəyyən edə bilər
istifadə uşaqlar array Bu kimi bir hesablanması.
Biz böyük uşaqlar istifadə edə bilər biz göz up təklif etmək istəyirdi array əgər
simvol daha geniş düymələri, belə bütün, kimi
ASCII character set.
>> Bu halda, pointer bizim uşaqlar array da
index bir null deyil.
Beləliklə, biz axtarır davam edəcəyik əsas vanna up.
Biz heç bir null göstərici rast varsa uşaq müvafiq spot da
array biz qovşaqlarının keçdiyi isə, onda biz biz demək lazımdır
ki düyməsi üçün bir şey tapa bilmədi.
>> İndi biz ikinci məktub və almaq lazımdır bizim əsas, A, və davam aşağıdakı
bu şəkildə göstəricilərinə biz qədər Bizim əsas sonuna çatmaq.
Biz olmadan əsas sonuna çatmaq əgər bir ölü bitir dəyən null göstəricilərinə,
işin burada kimi, sonra biz yalnız bir şey daha yoxlamaq lazımdır.
Bu əsas deyil, həqiqətən, Lüğətə?
>> Əgər belədirsə, biz yaxşı, bir dəyər tapmaq lazımdır Bizim diaqram smiley face icon yerləşir
sözü bitir.
Ilə saxlanılır başqa bir şey varsa məlumat, sonra biz onu qaytara bilər.
Məsələn, əsas zoo deyil biz bilər, hətta lüğət,
heç bu əsas sona çatdı , bir null göstərici vuruş isə biz
trie vasitəsilə təkrarlamaq.
>> Biz əsas vanna axtarmaq üçün cəhd Əgər Son node array indeksi ikinci,
, məktubu H olardı müvafiq bir null göstərici keçirilib.
Belə ki, hamam lüğətdə yoxdur.
Və belə bir trie ki, düymələri nadir aydın saxlanılır heç vaxt
məlumat strukturu.
Belə ki, necə biz bir şey daxil edirsiniz trie daxil?
>> Nin əsas daxil edək bizim trie daxil zoo.
Xatırla ki, bir node bir smiley face bir sadə kodu uyğun bilər
Ki, zoo göstərir Boolean dəyəri Lüğətə və ya bu ola bilər
Daha ətraflı məlumat üçün uyğun ki, biz əsas zoo ilə birləşmək arzulayıram,
Bu müəyyən kimi söz və ya başqa bir şey.
Bəzi yollar, proses daxil trie daxil bir şey benzer
bir trie bir şey axtarır.
>> Biz, bir daha kök node ilə başlamaq lazımdır aşağıdakı göstəricilər müvafiq
Bizim əsas məktublar.
Neyse, biz göstəricilərinə əməl edə bildik biz əldə qədər bütün yol
əsas sonu.
Zoo sözü bir prefiks olduğundan nın üzvü olan zoom,
lüğət, biz ehtiyac yoxdur hər hansı bir yeni qovşaqlarının ayırırlar.
>> Biz göstərir node dəyişə bilərsiniz ki, aparıcı simvol yol
Bu edir bizim lüğət bir əsas təmsil edir.
İndi daxil edək trie daxil əsas BATH.
Biz kök node başlamaq lazımdır və yenidən göstəricilərinə baxın.
Amma bu vəziyyət, bir ölü edib biz əldə edə önce son
əsas sonu.
İndi biz bir sıra yeni ayırmaq lazımdır qovşaqlarının bir yeni ayırmaq lazımdır
hər qalan üçün node Bizim əsas məktubu.
>> Bu halda, biz yalnız ehtiyac yeni bir node ayrılması.
Sonra H index etmək lazımdır Bu yeni node istinad.
Bir daha, biz node dəyişə bilərsiniz göstərir ki, simvol yol
ona aparan təmsil bizim lüğət əsas.
Nin asimptotik haqqında mülahizə edək Bu üçün prosedurların mürəkkəbliyi
iki əməliyyatları.
>> Qeyd ki, hər iki halda sayı bizim alqoritm aldı addımlar
sayına mütənasib söz məktublar.
Bu doğru deyil.
Sizə bir söz axtarmaq istədiyiniz zaman trie yalnız vasitəsilə təkrarlamaq lazımdır
məktublar bir-bir sizin qədər ya Bu sözün sonunda və ya çatmaq
trie bir ölü son edib.
>> Və əsas daxil etmək üçün istədiyiniz zaman istifadə edərək, bir trie daxil dəyər cüt
proseduru biz, ən pis halda müzakirə Siz yeni node ayrılması olacaq
hər bir hərf üçün.
Və biz ayrılması güman lazımdır bir daimi zaman əməliyyatdır.
Biz əsas uzunluğu olduğunu güman belə, əgər sabit sabit, həm də həmsərhəddir
durub və baxmaq daimi var trie üçün vaxt əməliyyatları.
>> Biz bu ehtimalı yoxdur ki, əgər əsas uzunluğu sabit ilə həmsərhəddir
daimi, sonra durub və baxmaq, ən pis halda, xətti olunur
əsas uzunluğu.
Maddələr sayı saxlanılır ki, görürsünüz trie görünüşünü qədər təsir etmir
və ya durub zaman.
Bu, yalnız təsir edir əsas uzunluğu.
>> Əksinə, demək, entries əlavə, bir hash table etmək niyyətindədir
gələcək yavaş baxmaq.
Bu ilk cəlbedici görünə bilər baxmayaraq yadda saxlamaq lazımdır ki, bir
əlverişli asimptotik mürəkkəbliyi deyil demək ki, təcrübədə data
strukturu mütləq tənbeh kənarda.
Biz də saxlamaq üçün hesab lazımdır pis biz lazımdır trie, söz
halda, qovşaqlarının bir sıra proporsional sözü özü uzunluğu.
>> Çalışır yer çox istifadə edirlər.
Ki, bir hash masa fərqli var, biz yalnız bir yeni node lazımdır
bəzi əsas dəyər cüt saxlamayın.
İndi yenə nəzəriyyəsi, böyük kosmik istehlak böyük kimi görünmür
xüsusilə nəzərə alsaq, məşğul ki, müasir kompüter gigabayt var və
yaddaş gigabayt.
Amma biz hələ ki, həyata çevirir yaddaş istifadə və narahat
naminə təşkilat performance, çünki müasir kompüter
altında yerdə mexanizmləri yaddaş girişi sürətləndirmək üçün başlıq.
>> Lakin bu mexanizmlər ən yaxşı zaman iş yaddaş giriş-çıxış kompakt edilir
bölgələrdə və ya sahələrdə.
Və bir trie qovşaqlarının yaşamaq bilər ki, yığın-yığın yerdə.
Amma bu ticarət-off biz hesab etməlidir ki,.
>> Bir məlumat seçərkən, Unutmayın ki, müəyyən bir vəzifə üçün strukturu, biz
haqqında düşünmək lazımdır nə cür əməliyyatları data strukturu lazımdır
dəstək və nə qədər performance o hər
bizə əməliyyatları məsələləri.
Bu əməliyyatlar hətta may yalnız kənara
əsas baxmaq və durub.
Biz bir cür tətbiq etmək istəyirdi Güman avtomatik tam funksionallıq çox
kimi Google search engine yoxdur.
Ki, bütün düymələri qayıtmaq və potensial dəyərlər
bir prefiks var.
>> A trie benzersiz faydalıdır Bu əməliyyat üçün.
Bu vasitəsilə təkrarlamaq üçün sadə var hər bir xarakter üçün trie
prefiks.
Sadəcə, bir qədər baxmaq əməliyyat kimi biz göstəricilərinə əməl bilər
xarakteri ilə xarakter.
Sonra, biz sonunda gəldiyi zaman prefiks, biz vasitəsilə təkrarlamaq bilər
məlumat strukturunun qalan hissəsi düymələri hər hansı bir kənarda bəri
Bu point prefiks var.
>> Bu siyahı əldə etmək də asan ildən əlifba sırası ilə
uşaqlar array elementləri əlifba sırası ilə sifariş olunur.
Belə ki, inşallah hesab edəcəyik verilməsi cəhd çalışır.
Mən Kevin Schmid oldum və bu CS50 edir.
>> Ah, bu başlanğıcdır azalması.
Üzgünüm.
Üzr istəyirik.
>> Dörd vur.
Mən deyiləm.
Üzr istəyirik.
Şəxs üçün üzr edən Bu crazy getmək redaktə var.
>> Üzr istəyirik.
Üzr istəyirik.
>> HOPARLÖR 1: Maşallah.
Bu, həqiqətən yaxşı oldu.