>> KEVIN SCHMID: Czasami, gdy budynek Program, możesz wykorzystać
Struktura danych znane jako słownik.
Słownik mapy klawiszy, które są zwykle struny, do wartości, ints,
znaków, wskaźnik do jakiegoś obiektu, co chcemy.
To tak jak zwykłych słownikach że mapa słowa przez definicje.
>> Słowniki nam Zdolność do przechowywania informacji
kojarzy się z czymś i szukać go później.
Jak więc właściwie wdrożyć Słownik w, powiedzmy, kod C, które możemy
używać w jednym z naszych programów?
Cóż, istnieje wiele sposobów, które moglibyśmy zaimplementować słownik.
>> Dla jednego, możemy używać tablicy, że dynamicznie zmienić rozmiar lub możemy użyć
powiązana lista, tabela hash lub binarne drzewo.
Ale cokolwiek zdecydujemy, powinniśmy pamiętać o efektywności i
realizacja wdrożenia.
Powinniśmy myśleć o algorytmu stosowanego włożyć i sprawdzić elementy do
Nasza struktura danych.
>> Teraz załóżmy, że mamy użyć ciągi jako klucze.
Pomówmy o jednej możliwości, struktura danych o nazwie TRIE.
Tak tu jest wizualna reprezentacja z trie.
>> Jak obraz sugeruje, TRIE jest drzewo struktury danych
węzły połączone ze sobą.
Widzimy, że jest wyraźnie korzeń węzeł z kilka linków rozszerzające
inne węzły.
Ale to, co ma każdy węzeł składa się z?
Jeśli założymy, że mamy do przechowywania kluczy się tylko znaki alfabetu, a
nie dbamy o kapitalizacji, oto definicja węzła
wystarczy.
>> Obiekt, którego typ jest struktura węzeł zawiera dwie części
zwane dane i dzieci.
Zostawiliśmy część danych jako komentarz być zastąpiony składnikiem
Deklaracja gdy węzeł jest struktura włączone w programie C.
Część danych z węzła może być Wartość logiczna, aby wskazać, czy
Węzeł nie oznacza zakończenie klucza słownika lub może być
Ciąg reprezentujący definicji wyrazu w słowniku.
>> Użyjemy buźkę, aby wskazać gdy dane są obecne w węźle.
Jest 26 elementów w naszym dzieci tablicy, jeden indeks
na znak alfabetu.
Zobaczymy znaczenie to wkrótce.
>> Chodźmy bliżej węzła głównego w naszym schemacie który ma dane
związany z nim, jak pokazano brak buźkę w
część danych.
Strzałki rozciągające się od części dzieci tablicy reprezentują nie-węzeł
wskaźniki do innych węzłów.
Na przykład, rozciągający się od strzałki Drugi element dzieci
oznacza literę B w kluczu słownika.
W szerszym kontekście schematu możemy opisać go z B.
>> Należy zauważyć, że w większej schemacie, kiedy zwrócić wskaźnik do innego węzła, to
nie ma znaczenia, gdzie grot spełnia ten drugi węzeł.
Nasz słownik zawiera próbkę trie dwa słowa, które i zoom.
Prześledźmy przykład patrząc w górę danych za pomocą klucza.
>> Załóżmy, że chcemy, aby wyszukać odpowiadające wartości dla klucza kąpieli.
Zaczniemy nasz wygląd się dla węzła głównego.
Następnie weźmiemy pierwszą literę naszego klucz, B i znaleźć odpowiadające
miejscu w naszej tablicy dzieci.
Zauważ, że istnieje dokładnie 26 miejsc w tablicy, po jednym dla każdej litery
alfabet.
I będziemy mieć plamy reprezentują litery alfabetu w kolejności.
>> Będziemy patrzeć na drugiego indeksu, a następnie, Indeks jeden, do B. W ogóle, jeśli
jakiś znak literowy C my może określić odpowiednie miejsce
w tablicy dzieci korzystających Obliczenie tak.
Mogliśmy użył większych dzieci Tablica jeśli chcieliśmy zaoferować Look Up
klucze z szerszego zakresu znaków, takie jak cały
Zestawu znaków ASCII.
>> W tym przypadku, wskaźnik w naszej tablicy dzieci w
Indeks nie jest null.
Będziemy więc nadal szuka się kluczowym kąpieli.
Jeśli kiedykolwiek napotkał wskaźnika null w odpowiednim miejscu u dzieci
tablica podczas gdy ruch węzłów, wtedy będziemy musieli powiedzieć, że
nie mógł znaleźć coś dla tego klucza.
>> Teraz weźmiemy drugą literę nasz klucz, i nadal następujące
wskaźniki w ten sposób, dopóki nie dotrzeć do końca nasz klucz.
Jeśli dotrzemy do końca klucza bez uderzając w żadne ślepych zaułków, null wskaźniki,
jak jest w tym przypadku, to tylko trzeba sprawdzić jeszcze jedną rzecz.
Klucz ten jest w rzeczywistości w słowniku?
>> Jeśli tak, to powinniśmy znaleźć wartość, oraz buźkę emotka w naszym schemacie, gdzie
słowo kończy.
Jeśli jest coś jeszcze przechowywane w dane, to możemy go zwrócić.
Przykładowo, klucz nie znajduje się w zoo słowniku, choć mogliśmy
osiągnął koniec tego klucza, nigdy uderzenie pustego wskaźnika, podczas gdy my
iteracji trie.
>> Jeśli będziemy starali się patrzeć na kluczową kąpieli, Drugi do indeksu tablicy ubiegłym węzła,
odpowiadający literze H, to prowadziły pustego wskaźnika.
Więc kąpiel nie ma w słowniku.
I tak trie jest unikalny w tym, że klawisze nigdy nie są wyraźnie zapisane w
Struktura danych.
Jak więc wstawić coś w trie?
>> Miejmy włożyć klucz zoo w naszej trie.
Pamiętaj, że buźkę w węźle może odpowiadać w kodzie, aby proste
Wartość logiczna, aby wskazać, że zoo jest w słowniku lub mogłoby
odpowiadają, że mamy więcej informacji chcesz skojarzyć z kluczem zoo,
jak w definicji Słowo lub coś innego.
W pewnym sensie, to proces, aby wstawić coś w trie jest podobny do
patrząc na coś w trie.
>> Zaczniemy od węzła głównego ponownie, Poniższe wskaźniki odpowiadające
litery z naszych kluczowych.
Na szczęście udało nam się przestrzegać wskazówek do końca, aż dotarliśmy
Koniec klucza.
Ponieważ zoo jest prefiksem słowa zoom, który jest członkiem
słowniku, nie musimy się przydzielić nowych węzłów.
>> Można zmodyfikować, aby wskazać, że węzeł ścieżka postaci, co prowadzi do
stanowi klucz w naszym słowniku.
Teraz spróbujmy wstawienie Kluczem do KĄPIELI trie.
Zaczniemy w węźle głównym i ponownie wykonaj następujące wskaźniki.
Ale w tej sytuacji, to hit martwy zakończyć przed jesteśmy w stanie dostać się do
Koniec klucza.
Teraz musimy przeznaczyć kilka nowych Węzły będą musiały przeznaczyć jeden nowy
za każdy pozostały węzeł List z naszych kluczowych.
>> W tym przypadku wystarczy przeznaczyć jeden nowy węzeł.
Następnie musimy dokonać indeks H odwoływać się do tego nowego węzła.
Po raz kolejny możemy zmodyfikować węzeł wskazują, że ścieżka znaków
prowadzi do niego oznacza klucz w naszym słowniku.
Miejmy rozumować o asymptotycznej Złożoność naszych procedur są
dwie operacje.
>> Zauważmy, że w obu przypadkach liczba kroków algorytmu wziął był nasz
proporcjonalna do liczby litery w słowa kluczowego.
Zgadza się.
Gdy chcesz sprawdzić słowo w trie wystarczy iteracji
litery jeden po drugim, aż was albo dotrzeć do końca tego słowa lub
trafić w ślepy zaułek w trie.
>> A gdy chcesz wstawić klucz para wartości do trie pomocą
Procedura dyskutowaliśmy, najgorszy przypadek będzie można przydzielenie nowego węzła
dla każdej litery.
I zakładamy, że przydział jest stałe działanie czasu.
Tak więc, jeśli założymy, że długość klucza jest ograniczona przez stałą stała, zarówno
wstawiania i patrzeć są stałe Operacje czas na trie.
>> Jeśli nie robimy tego założenia, że Długość klucza jest ograniczone przez stałą
stała, a następnie wkładanie i patrzeć, W najgorszym przypadku, stosuje się liniowe
Długość klucza.
Zauważ, że liczba elementów przechowywanych w trie nie wpływa na wygląd się
lub czas wstawiania.
To wpływ jedynie Długość klucza.
>> Natomiast dodanie pozycji do, powiedzmy Tabela mieszania dąży do
przyszłość patrzeć wolniej.
Chociaż może wydawać się atrakcyjne w pierwszym, należy pamiętać, że
korzystne nie asymptotycznej złożoności W praktyce oznacza to, że dane
Struktura jest koniecznie bez zarzutu.
Musimy również wziąć pod uwagę, że do przechowywania Słowo w trie musimy, w najgorszym
przypadek, liczba węzłów proporcjonalna do długości tego słowa.
>> Próbuje zazwyczaj stosować dużo miejsca.
To w przeciwieństwie do tabeli mieszania, gdzie musimy tylko jeden nowy węzeł do
przechowywać pewną parę wartości klucza.
Teraz, również teoretycznie dużą przestrzeń paliwa nie wydaje się duża
czynienia, szczególnie biorąc pod uwagę, że nowoczesna komputery mają gigabajtów i
gigabajty pamięci.
Ale okazuje się, że mamy jeszcze martwić się o zużycie pamięci i
organizacji dla dobra wydajność, ponieważ nowoczesne komputery
mają mechanizmy pod kaptur, aby przyspieszyć dostęp do pamięci.
>> Ale mechanizmy te działają najlepiej, gdy odwiedziny pamięci są w zwarty
regiony lub obszary.
I węzły trie może znajdować wszędzie w tej sterty.
Ale to są kompromisy , że musimy wziąć pod uwagę.
>> Pamiętaj, że przy wyborze danych Struktura pewne zadanie, to
powinniśmy myśleć o tym, co rodzaje Operacje struktura danych musi
Wsparcie i ile wydajność każdego z tych
operacji jest dla nas.
Operacje te mogą nawet wykraczać poza tak
Podstawową się wygląd i wstawiania.
Załóżmy, że chcemy realizować rodzaj z funkcji autouzupełniania, dużo
jak wyszukiwarka Google robi.
Oznacza to, że z powrotem wszystkie klucze i Wartości, które potencjalnie
mają podane prefiks.
>> Trie jest wyjątkowo przydatna Do tej operacji.
Jest to proste do iteracji trie dla każdego znaku
prefiks.
Podobnie jak pracy przeglądowej, możemy śledzić wskaźniki
znak po znaku.
Następnie, kiedy przyjechaliśmy na koniec prefiks, możemy iteracji
Pozostała część tej struktury danych od jednego z klawiszy poza
Ten punkt ma prefiks.
>> Jest również łatwo uzyskać ten wpis w kolejności alfabetycznej od
elementy tablicy dzieci są sortowane alfabetycznie.
Więc mam nadzieję, że będziesz pod uwagę dawanie próbuje spróbować.
Jestem Kevin Schmid, a to jest CS50.
>> Ach, to jest początek spadku.
Przykro mi.
Przepraszam.
>> Strike cztery.
Jestem na zewnątrz.
Przepraszam.
Przepraszam za osobę musi zmodyfikować zwariować.
>> Przepraszam.
Przepraszam.
>> GŁOŚNIK 1: Dobra robota.
To było naprawdę dobrze zrobione.