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. Przepraszam. Przepraszam. 

Strike cztery. Jestem na zewnątrz. Przepraszam. Przepraszam. Przepraszam. Przepraszam za osobę musi zmodyfikować zwariować. 

Przepraszam. Przepraszam. Przepraszam. Przepraszam. 

GŁOŚNIK 1: Dobra robota. To było naprawdę dobrze zrobione.