>> KEVIN SCHMID: Uneori, atunci când construirea unei Programul, ați putea dori să utilizeze un
structura de date cunoscut ca un dicționar.
A hărți dicționar chei, care sunt de obicei siruri de caractere, la valori, int,
caractere, un pointer la un obiect, ceea ce ne dorim.
E la fel ca dicționare obișnuite că hartă cuvinte prin definiții.
>> Dicționare ne oferi capacitatea de a stoca informații
asociat cu ceva și căutați-l mai târziu.
Deci, cum putem implementa de fapt o dicționar în, să zicem, cod C care putem
utilizarea în unul din programele noastre?
Ei bine, există o mulțime de moduri în care am putea pune în aplicare un dicționar.
>> Pentru unul, am putea folosi o matrice pe care le dinamic re-size sau am putea folosi un
Lista legată, tabelul hash sau un arbore binar.
Dar orice am alege, ar trebui să ne să fie conștient de eficiența și
performanță de punere în aplicare.
Ar trebui să ne gândim la algoritmul folosit pentru a introduce și căuta obiecte în
structura noastra de date.
>> Pentru moment, să presupunem că ne-am doriți să utilizați siruri de caractere ca taste.
Hai sa vorbim despre o posibilitate, o structură de date numit un trie.
Deci, aici este o reprezentare vizuală unui trie.
>> După cum sugerează imagine, un trie este o structură de date arbore cu
noduri legate împreună.
Vedem că există în mod clar o rădăcină nod cu unele link-uri de extindere a
alte noduri.
Dar ceea ce nu fiecare nod format din?
Dacă presupunem că suntem stocarea cheilor cu doar caractere alfabetice, și
nu ne pasă de capitalizare, aici este o definiție a unui nod care
va fi suficient.
>> Un obiect al cărui tip este struct nod are doua parti
numit de date si copii.
Am plecat de la partea de date ca un comentariu să fie înlocuită cu o componentă
declarație atunci când nod struct este încorporate într-un program C.
Partea de date a unui nod poate fi un Valoare boolean pentru a indica dacă sau
Nu nodul reprezintă finalizarea de o cheie de dicționar sau ar putea fi o
string reprezentând definiția de un cuvânt în dicționar.
>> Vom folosi o fata zambitoare pentru a indica atunci când datele sunt prezente într-un nod.
Există 26 de elemente în nostru copii matrice, un index
per caracter alfabetic.
Vom vedea semnificația din această curând.
>> Să ne o privire mai atentă a nodului rădăcină în diagrama noastră, care nu are date
asociate cu acesta, după cum este indicat de către lipsa de fața zâmbitoare în
porțiune de date.
Săgețile se extind din părțile matrice copiii reprezintă non-nod
indicii la alte noduri.
De exemplu, săgeata extinsă de la al doilea element de copii
reprezintă litera B într-o cheie dicționar.
Și în diagrama de mai mare am o eticheta cu un B.
>> Rețineți că în diagrama mai mare, atunci când ne trage un pointer la un alt nod, ea
nu contează în cazul în care pe vârful săgeții întâlnește celălalt nod.
Nostru trie dicționar eșantion conține două cuvinte, care și zoom.
Să mergem printr-un exemplu de uita în sus de date pentru o cheie.
>> Să presupunem că am vrut să se uite în sus valoare corespunzătoare pentru baie cheie.
Vom începe uite noastre în sus la nodul rădăcină.
Apoi vom lua prima literă a noastră cheie, B, și pentru a găsi corespunzătoare
la fața locului în copii nostru matrice.
Observați că există exact 26 pete în matrice, una pentru fiecare literă a
alfabetul.
Și vom avea pete reprezintă litere ale alfabetului, în ordine.
>> Ne vom uita la cea de a doua index, apoi, indicele unul, pentru B. In general, dacă
au un caracter alfabetic C noi ar putea determina locul corespunzător
în copii matrice folosind un calcul de genul asta.
Am fi putut folosi pentru copii mai mari matrice dacă ne-am dorit să oferim aspect din
chei, cu o gamă mai largă de personaje, cum ar fi întreaga
De caractere ASCII.
>> În acest caz, indicatorul la copiii nostru matrice la
indicele unul nu este nulă.
Asa ca vom continua căutarea up baia cheie.
Dacă am întâlnit vreodată un pointer nul la fața locului adecvat în copiii
matrice în timp ce ne-am traversat nodurile, atunci va trebui să spunem că ne-am
nu a putut găsi nimic pentru acea cheie.
>> Acum, vom avea de-a doua scrisoare de cheia noastră, A, și să continue în urma
indicii în acest fel până când vom ajunge la sfârșitul cheia noastră.
Dacă vom ajunge la capătul cheii fără a lovit nici unghiuri moarte, indicii nule,
cum este cazul aici, atunci numai noi Trebuie să verific un singur lucru.
Este această cheie de fapt în dicționar?
>> Dacă este așa, ar trebui să găsim o valoare, precum și o icon fata zambitoare în diagrama noastră, unde
cuvântul se termină.
Dacă există ceva stocate cu datele, atunci putem întoarce.
De exemplu, grădina zoologică cheie nu este în dicționar, chiar dacă am putea avea
a ajuns la sfârșitul acestei taste, fără vreodată lovind un pointer nul, în timp ce noi
itera prin trie.
>> Dacă am încercat să te uiți în sus baia cheie, în al doilea rând să indice matrice ultimul nod,
corespunzătoare literei H, ar au organizat un pointer nul.
Deci, baie, nu se află în dicționar.
Și astfel un trie este unic în faptul că tastele nu sunt niciodată stocate în mod explicit în
structura de date.
Deci, cum putem introduce ceva într-un trie?
>> Să introduceți cheia grădină zoologică în trie nostru.
Amintiți-vă că o fata zambitoare la un nod ar putea corespunde cu cod la un simplu
Valoare Boolean pentru a indica faptul că zoo este în dicționar sau ar putea
corespund la mai multe informații pe care le doresc să se asocieze cu gradina zoologica cheie,
cum ar fi definiția cuvânt sau altceva.
În unele privințe, procesul de a insera ceva într-un trie este similar cu
căutând ceva într-un trie.
>> Vom începe cu nodul rădăcină nou, Următoarele indicii corespunzătoare
scrisorile de cheia noastră.
Din fericire, noi am fost capabil să urmeze indicii tot drumul până când am ajuns la
capătul cheii.
Deoarece grădină zoologică este un prefix al cuvântului zoom-ul, care este un membru al
dicționar, nu avem nevoie să aloca noi noduri.
>> Putem modifica nodul pentru a indica faptul că calea de caractere care duc la
reprezintă o cheie în dicționarul nostru.
Acum, haideți să încercați să introduceți BATH cheie în trie.
Vom începe de la nodul rădăcină și să urmeze din nou indicii.
Dar, în această situație, am lovit un mort se încheie înainte de suntem capabili de a ajunge la
capăt al cheii.
Acum, va trebui să aloce unor noi noduri va trebui să aloce un nou
nod pentru fiecare rămasă scrisoarea de cheia noastră.
>> În acest caz, avem nevoie doar de de a aloca un nod nou.
Atunci vom avea nevoie pentru a face indicele H referire la acest nou nod.
Încă o dată, putem modifica nodul la indică faptul că drumul de caractere
care duce la aceasta reprezintă o cheie în dicționarul nostru.
Să rationa despre asimptotice complexitatea procedurilor noastre pentru aceste
două operațiuni.
>> Se observă că în ambele cazuri numărul de pașii algoritmului nostru a fost luat
proporțională cu numărul de litere din cuvântul cheie.
Asta-i drept.
Când doriți să căutați un cuvânt într-o trie trebuie doar să itera prin
literele una câte una, până când, fie ajunge la sfârșitul cuvântului sau
a lovit-o fundătură în trie.
>> Și atunci când doriți să introduceți o cheie Valoarea pereche într-un trie, utilizând
Procedura am discutat, cel mai rău caz va avea tu alocarea un nou nod
pentru fiecare literă.
Și vom presupune că alocarea este o operațiune de timp constant.
Deci, dacă am presupune că lungimea cheii este delimitate de o constantă fixă, ambele
inserare și privi în sus sunt constante operațiunilor de timp pentru un trie.
>> Dacă nu facem această presupunere că lungimea cheii este delimitată de un fix
constant, apoi inserare și privi în sus, în cel mai rău caz, sunt liniare în
lungimea codului.
Observați că numărul de elemente stocate în trie nu afectează aspectul în sus
sau timp de inserare.
Este afectat doar de către lungimea codului.
>> Prin contrast, adaugand intrări la, să zicem, un tabel hash tinde să facă
viitor căuta mai lent.
În timp ce acest lucru poate suna atragatoare la început, noi ar trebui să țină cont de faptul că o
complexitate asimptotică favorabil nu înseamnă că, în practică, datele
Structura este în mod necesar dincolo de reproș.
Noi trebuie să ia în considerare, de asemenea, că pentru a stoca o cuvânt într-un trie avem nevoie, în cel mai rău
caz, un număr de noduri proporțional cu lungimea cuvântului în sine.
>> Încearcă tendința de a folosi o mulțime de spațiu.
Aceasta este în contrast cu un tabel hash, unde avem nevoie doar de un nou nod de
stoca unele pereche valoare-cheie.
Acum, din nou, în teorie, spațiu mare consum nu pare ca o mare
a face, mai ales având în vedere că moderne computerele au gigabytes și
GB de memorie.
Dar se pare că mai avem încă să vă faceți griji cu privire la utilizarea de memorie și
organizare de dragul de performanță, deoarece calculatoare moderne
au mecanisme în loc sub capota pentru a accelera de acces la memorie.
>> Dar aceste mecanisme funcționează cel mai bine atunci când accese de memorie sunt făcute în compact
regiuni sau zone.
Și nodurile de un trie ar putea locui oriunde în grămadă.
Dar acestea sunt compromisuri că trebuie să ne gândim.
>> Amintiți-vă că, atunci când aleg un date structura pentru o anumită sarcină, ne-am
ar trebui să se gândească la ce fel de operațiunile de structura de date trebuie să
suport și cât de mult a performanței fiecăruia dintre aceste
Operațiuni contează pentru noi.
Aceste operațiuni pot chiar se extind dincolo de doar
aspect de bază în sus și inserare.
Să presupunem că ne-am dorit să pună în aplicare un fel de funcționalitate auto-complete, mult
cum ar fi motorul de căutare Google nu.
Asta este, se întoarcă toate cheile și potențial valori care
au un anumit prefix.
>> Un trie este unic util pentru această operație.
Este simplu pentru a itera prin trie pentru fiecare caracter de
prefixul.
La fel ca o operațiune privi în sus, am putea urmări indicii
caracter cu caracter.
Apoi, când am ajuns la sfârșitul perioadei de prefix, am putea repeta prin
restul porțiune a structurii de date deoarece oricare dintre tastele dincolo
acest punct au prefixul.
>> Este, de asemenea, ușor pentru a obține această listare în ordine alfabetică de la
elemente de matrice copii sunt ordonate alfabetic.
Deci sperăm că veți lua în considerare da încearcă un try.
Sunt Kevin Schmid, iar acest lucru este CS50.
>> Ah, aceasta este începutul a declinului.
Îmi pare rău.
Scuze.
>> Strike patru.
Am plecat.
Scuze.
Ne pare rău pentru a face persoana care are pentru a edita acest razna.
>> Scuze.
Scuze.
>> SPEAKER 1: Foarte bine.
, Care a fost foarte bine facut.