SPEAKER 1: Dobrze, więc jesteśmy z powrotem. Witamy CS50. To jest koniec tygodnia siedem. Tak więc przypomnieć, że ostatnim razem, zaczęliśmy patrząc na nieco bardziej wyrafinowane struktury danych. Ponieważ do tej pory, wszyscy mieliśmy naprawdę do naszej dyspozycji był ten, array. Zanim jednak usunąć tablicę, jak nie wszystko, co interesujące, które rzeczywiście rzeczywiście jest, jakie są niektóre plusy tego prostego danych Struktura tej pory? O co w tym dobry? Do tej pory, jak widzieliśmy? Co masz? Nic. STUDENT: [niesłyszalne]. SPEAKER 1: Co to jest? STUDENT: [niesłyszalne]. SPEAKER 1: Stały rozmiar. OK, więc dlaczego jest stały rozmiar dobry, choć? STUDENT: [niesłyszalne]. SPEAKER 1: OK, więc to jest skuteczny w Poczucie, że można przydzielić stałą ilość miejsca, które miejmy nadzieję, jest dokładnie tak samo miejsca, jak chcesz. Więc to może być absolutnie na plus. Co innego się z boku na tablicy? Tak? STUDENT: [niesłyszalne]. SPEAKER 1: All - Przepraszam? STUDENT: [niesłyszalne]. SPEAKER 1: Wszystkie pola w pamięci lub obok siebie. I to jest pomocne - dlaczego? To całkiem prawda. Ale w jaki sposób możemy wykorzystać tę prawdę? STUDENT: [niesłyszalne]. SPEAKER 1: Dokładnie, możemy śledzić gdzie wszystko jest po prostu wiedzieć jeden adres, czyli adres Pierwszy bajt że ilość pamięci. Lub w przypadku łańcucha, adres pierwszy char w tym ciągu. I tam, możemy znaleźć koniec napisu. Możemy znaleźć drugi element, na Trzeci element, i tak dalej. I tak fantazyjny sposób opisu, który Funkcja jest to, że daje nam tablice random access. Wystarczy za pomocą uchwytu kwadratowego oznaczenie i numer, można przejść do konkretny element w tablicy w stałym czasie, Big O z jednym, że tak powiem. Ale nie było pewne wady. Co nie tablica zrobić bardzo łatwo? Co nie jest dobry? STUDENT: [niesłyszalne]. SPEAKER 1: Co to jest? STUDENT: [niesłyszalne]. SPEAKER 1: Rozszerzenie wielkości. Więc downsides z tablicy są dokładnie odwrotne do Plusy są. Więc jedną z wad jest że jest to stały rozmiar. Tak naprawdę nie można rozwijać go. Możesz przydzielić większy kawałek pamięci, a następnie przenieść stare elementy do nowej tablicy. A wtedy darmo stare tablicą, na instancji, za pomocą malloc lub podobny Funkcja o nazwie realloc, które alokację pamięci. Realloc, jak na bok, stara się dać pamięci, która znajduje się obok tablicy , które już masz. Ale to może przenieść rzeczy wokół zupełnie. Ale w skrócie, to jest drogie, prawda? Bo jeśli masz kawałek pamięci tej wielkości, ale naprawdę chcesz jednego tej wielkości, a chcesz zachować oryginalne elementy, trzeba przybliżeniu liniowy proces kopiowania czas że musi się zdarzyć z stara tablica na nowe. A rzeczywistość jest zwrócenie się do działającej System znowu i znowu i ponownie na duże kawałki pamięci może rozpocząć kosztować trochę czasu, jak również. Więc to jest zarówno błogosławieństwem, jak i przekleństwem w ukrycia, fakt, że te tablice mają stały rozmiar. Ale jeśli wprowadzimy zamiast coś jak to, co nazwaliśmy linked lista, mamy kilka upsides i kilka downsides również tutaj. Więc związane lista jest po prostu dane Struktura składa się z struktur C, w tym przypadek, w którym struct, przypomnijmy, jest tylko pojemnik na jedną lub więcej konkretnych typy zmiennych. W tym przypadku, co zrobić, typy danych wydają się wewnątrz tej struktury, że Ostatni raz zadzwoniliśmy węzeł? Każdy z tych prostokątów jest węzeł. I każdy z mniejszych prostokątów wewnątrz niego jest typ danych. Jakie było powiedzieć byli w poniedziałek? Tak? STUDENT: [niesłyszalne]. SPEAKER 1: zmienna i wskaźnik, lub Dokładniej, Int., dla n, i wskaźnik na dole. Oba te stało się 32 bitów, co najmniej na komputerze, takie jak ten CS50 Appliance, a więc są wyciągnąć równie wielkości. Więc co za pomocą wskaźnika chociaż dla pozoru? Dlaczego warto dodać tę strzałkę, teraz, gdy tablice były tak ładne i czyste i proste? Co to jest wskaźnik ten dla nas w każdym z tych węzłów? STUDENT: [niesłyszalne]. SPEAKER 1: Dokładnie. To mówi ci, gdzie następny jest. Więc jakby użyć analogii za pomocą nici do rodzaju nawlec te węzły razem. I to jest dokładnie to, co robimy z wskaźniki, ponieważ każdy z nich fragmenty pamięci może być lub nie być ciągły, z powrotem do tyłu do tyłu wewnątrz pamięci RAM, ponieważ za każdym razem zadzwoń malloc mówiąc mi wystarczy bajtów dla nowego węzła, to może tu być lub może być tutaj. To może być tutaj. To może być tutaj. Po prostu nie wiem. Ale za pomocą wskaźników w adresach te węzły, można zszyć je ze sobą w sposób, który wygląda optycznie jak listy, nawet jeśli te rzeczy są wszystko rozłożone w całym jednym lub Twoje dwa lub Twoje cztery gigabajty pamięci RAM wewnątrz własnego komputera. Więc minusem, to, powiązana lista jest co? Co to jest cena jesteśmy widocznie płacą? STUDENT: [niesłyszalne]. SPEAKER 1: Więcej miejsca, prawda? Mamy w tym przypadku, podwoić ilość miejsca, bo zaszliśmy od 32 bitów dla każdego węzła, dla każdego int, więc teraz 64 bity, ponieważ mamy do utrzymać wokół wskaźnika, jak również. Masz większą wydajność, jeśli struct jest większy niż to prosta rzecz. Jeśli rzeczywiście ucznia wewnątrz których jest kilka ciągów Nazwa i dom, może numer ID, może jakieś inne pola w ogóle. Więc jeśli masz na tyle duże struct, to może koszt wskaźnika jest nie taka wielka sprawa. To jest trochę przypadku w tym rogu jesteśmy przechowywania takie proste prymitywne wewnątrz połączonej listy. Ale chodzi o to samo. Jesteś zdecydowanie większe wydatki pamięci, ale dostajesz elastyczność. Bo teraz, jeśli chcę, aby dodać element Na początku tej liście, Muszę przyznać nowy węzeł. A ja mam po prostu zaktualizować te strzałki jakoś poprzez przesuwanie kilka wskazówek okolicy. Jeśli chcę wstawić coś do środku listy, nie mam do wcisnąć każdy bok tak jak my w przeszłości tygodni z naszych wolontariuszy, którzy reprezentowane tablicę. Mogę tylko przydzielić nowy węzeł i a potem po prostu wskazać na strzałki w różnych kierunkach, ponieważ nie muszą pozostać w rzeczywistej Pamięć prawda linia jakbym rysowane to tutaj, na ekranie. I wtedy wreszcie, jeśli chcesz wstawić coś na koniec listy, to jeszcze łatwiejsze. To jest rodzaj niepożądanego notacji, ale 34 jest wskazówka, zgadywać. Jaka jest wartość jego wskaźnika większości może wyciągnąć trochę jak stary Antena szkole? STUDENT: [niesłyszalne]. SPEAKER 1: To chyba null. I rzeczywiście, że jest jednym autora reprezentacja null. I to jest wartość null, ponieważ absolutnie muszą wiedzieć, gdzie koniec linked Lista jest, żeby zachować następujące i po i po tych strzałek do pewnej wartości śmieci. Więc zerowy będzie oznaczać, że nie ma więcej węzłów na prawo od liczby 34, w tym przypadku. Tak więc proponuję, że możemy realizować węzeł w kodzie. I widzieliśmy tego rodzaju składni wcześniej. Typedef właśnie definiuje nowy typ dla nas, daje nam synonim jak Łańcuch był na char *. W tym przypadku, to będzie nam skróconą tak, że zapis struct node może zamiast po prostu zapisać jako Węzeł, który jest o wiele czystsze. To dużo mniej widoczny. Wewnątrz węzła jest najwyraźniej int nazywany N, a następnie węzeł struct * co oznacza dokładnie to, co chcieliśmy strzałki oznacza, wskaźnik do innego Węzeł dokładnie tego samego typu danych. A ja proponuję, że możemy realizować Funkcja wyszukiwania jak to, co w pierwszy rzut oka może się wydawać trochę skomplikowane. Ale zobaczymy go w kontekście. Pozwól mi przejść do urządzenia tutaj. Pozwól mi otworzyć plik o nazwie zerowej dot h lista. I że tylko zawiera definicję my Właśnie widziałem przed chwilą do tych danych Rodzaj nazwie węzła. Więc umieściliśmy że do pliku h dot. I jak na bok, chociaż program, który masz zamiar zobaczyć jest nie wszystko, co skomplikowane, jest to rzeczywiście Konwencja pisząc program umieścić rzeczy jak typy danych, aby wyciągnąć Stałe czasem, wewnętrznej stronie nagłówek pliku i niekoniecznie w plik C, na pewno, kiedy twój Programy uzyskać większe i większe, tak że wiesz, gdzie szukać zarówno dla Dokumentacja w niektórych przypadkach, lub dla podstawowych rzeczy, jak to, po określenie pewnego typu. Jeśli teraz otwierają listę punkt zerowy c, zauważyć kilka rzeczy. Obejmują kilka plików nagłówkowych, większość które widzieliśmy wcześniej. Zawiera własny plik nagłówkowy. A na marginesie, dlaczego to jest double cytuje tutaj, w przeciwieństwie do kąta Uchwyty na linii Mam podkreślił tam? STUDENT: [niesłyszalne]. SPEAKER 1: Tak więc jest to plik lokalny. Więc jeśli jest to plik lokalny z własnej tutaj na linii 15, na przykład, można użyć podwójne cudzysłowy zamiast z ostrych nawiasach. Teraz jest to rodzaj ciekawe. Zauważ, że już zadeklarowane globalne zmienna w tym programie on line 18 zwany pierwszy, w myśl której to będzie wskaźnik do pierwszego węzeł w mojej połączonej listy, a ja inicjowany jest na null, bo mam nie przypisany każdy rzeczywisty węzły jeszcze. Więc to oznacza, obrazowo, co my Przed chwilą widziałem na zdjęciu jako że wskaźnik na daleko lewej stronie. Więc teraz, że wskaźnik nie ma strzałę. Zamiast tego jest tylko null. Ale oznacza to, co będzie adres pierwszy rzeczywisty Węzeł w tym wykazie. Tak już realizowany jest globalny ponieważ, jak zobaczysz, to wszystko Program ma w życiu jest wdrożenie linked list dla mnie. Teraz mam kilka prototypów tutaj. I zdecydowała się na wdrożenie funkcji, takich jak usuwanie, wstawianie, wyszukiwanie i translacji - ostatnio po prostu spacer po lista, drukując jego elementy. I teraz tu jest mój główny rutyna. A my nie spędzają zbyt wiele czasu na to ponieważ jest to rodzaj, miejmy nadzieję, stary kapelusz teraz. Zamierzam wykonać następujące czynności, gdy użytkownik współpracuje. Więc jeden, mam zamiar wydrukować z tego menu. A ja sformatować go jako czysto, jak tylko mogłem. Jeśli użytkownik wpisze w jednym, to znaczy, chcą coś usunąć. Jeśli użytkownik wpisze w dwóch, co oznacza, że chcą wprowadzić coś. I tak dalej. Zamierzam się komunikat następnie na polecenie. A potem mam zamiar używać getInt. Więc to jest naprawdę proste menuing interfejsu, w którym wystarczy wpisać mapping numer jeden z tych poleceń. A teraz mam ładne czyste przełącznik oświadczenie, że zamierza włączyć co użytkownik wpisze w. A jeśli wpisane jedno, ja zadzwoń usunąć i złamać. Jeśli wpisane dwa, będę zadzwoń włożyć i złamać. A teraz zawiadomienie umieściłem każdego z nich w tym samym wierszu. To tylko stylistyczne decyzji. Zazwyczaj widzieliśmy coś jak ten. Ale ja po prostu zdecydował, szczerze mówiąc, mój program wyglądał bardziej czytelny, ponieważ to tylko cztery przypadki do tylko listy to tak. Całkowicie legalne stosowanie stylu. I mam zamiar to zrobić, tak długo, jak długo Użytkownik nie wpisał zero, co ja decyzję będzie oznaczać, że chcą, aby zamknąć. Więc teraz zauważyć, co mam zamiar zrobić tutaj. Mam zamiar uwolnić listę widocznie. Ale o tym za chwilę. Niech najpierw uruchomić ten program. Więc pozwól mi zrobić większy terminalu okno, dot slash lista 0. Mam zamiar iść do przodu i wprowadzić przez wpisując dwa, liczba jak 50, a teraz zobaczysz list jest teraz 50. A mój tekst po prostu przewijać się trochę. Więc teraz zauważyć lista zawiera Numer 50. Zróbmy jeszcze wkładkę biorąc dwa. Załóżmy, wpisać numer jak jeden. List jest teraz jednym, a następnie przez 50. Więc to jest tylko reprezentacja tekstowa z tej listy. I niech wstawić jeszcze jeden numer, jak numer 42, który jest nadzieją skończy się w środku, ponieważ ten program to w szczególności rodzaju elementy, jak wstawia ich. Więc nie mamy go. Super prosty program, który mógłby absolutnie nie stosować tablicę, ale stało się za pomocą połączonej listy tylko tak mogę dynamicznie rosną i kurczą się go. Warto więc spojrzeć na poszukiwania, jeśli uruchomić komendę trzy, chcę sprawdzić dla, powiedzmy, liczby 43. I nic nie było najwyraźniej znaleźć, bo wróciłem bez odpowiedzi. Więc zróbmy to jeszcze raz. Szukaj. Załóżmy, szukaj 50, a raczej szukać do 42, która ma miły mało subtelne znaczenie. I znalazłem sens życia tam. Numer 42, jeśli nie wiesz, odniesienia, Google to. Dobrze. Więc co jest ten program dla mnie zrobił? To jest po prostu pozwolił mi włożyć więc daleko i szukaj elementów. Niech szybko do przodu, a następnie, aby że funkcja my spojrzał na w poniedziałek jako teaser. Więc tej funkcji I twierdzą, wyszukuje Element na liście przez pierwszą jeden, który pyta użytkownika, a następnie wywołanie GetInt uzyskać rzeczywiste int , które chcesz wyszukać. Wtedy to zauważyć. Idę do tworzenia zmiennej tymczasowej w linii 188 zwany wskaźnik - PTR - może nazwali to coś. I to jest wskaźnik do węzła bo wspomniany węzeł * tam. A ja inicjowanie, że jest równa Pierwszy tak, że skutecznie mieć moje palec, by tak rzec, na bardzo pierwszy element listy. Więc jeśli moja prawa ręka o to PTR jestem wskazując na to samo, że najpierw wskazuje na. Więc teraz z powrotem w kodzie, to, co dzieje się dalej - jest to wspólny paradygmat podczas iteracji na strukturze jak połączonej listy. Zamierzam wykonać następujące czynności podczas wskaźnik nie jest równa null Tak więc, mój palec nie wskazuje na jakiś nieważną wartość, jeśli wskaźnik strzałka n wynosi n. Będziemy zauważyć po pierwsze, że n jest co użytkownik wpisany na GetInts zadzwonić tutaj. A wskaźnik strzałka n oznacza co? Cóż, jeśli wrócimy do obrazu tutaj, jeśli mam palca wskazującego że pierwszy węzeł zawierający dziewięć r. strzałka w istocie oznacza, że ​​go do węzeł i pobieramy wartość w miejscu n, W tym przypadku, pole danych o nazwie N. Tak na marginesie - i widzieliśmy to kilka tygodni temu, gdy ktoś zapytał - składnia ta jest nowa, ale tak nie jest daje nam uprawnienia, które nie mają już. Co to za wyrażenie równoważne użyciu dot notacji i gwiazda para tygodni temu, kiedy odrywa się ta warstwa nieco przedwcześnie? STUDENT: [niesłyszalne]. SPEAKER 1: Dokładnie, to była gwiazda, i potem było gwiazda dot n, z nawiasy tutaj, co wygląda, Szczerze mówiąc, myślę, że wiele bardziej tajemnicze przeczytać. Ale wskaźnik gwiazda, jak zawsze, środki tam. I raz, że tam jesteś, jakie dane Pole chcesz przejść? Dobrze użyć notacji dostęp kropka structury pole danych, a ja konkretnie chce n. Szczerze mówiąc, jestem zdania, to jest po prostu trudniejsze do odczytania. Jest to trudniejsze do zapamiętania, gdzie Czy nawiasy iść, gwiazda i to wszystko. Tak więc świat przyjął niektóre składniowe cukru, że tak powiem. Tylko sexy sposób powiedzenia, To jest równoważne, i może bardziej intuicyjne. Jeśli wskaźnik jest rzeczywiście wskaźnik, środki zapisu strzałek tam i znaleźć W tym przypadku pole zwane n. Więc jeśli go znaleźć, zauważyć to, co robię. I po prostu wydrukować, znalazłem procent I, podłączając wartości dla tego int. Wzywam spać przez jedną sekundę po prostu rodzaju rzeczy pauzy na ekranie, aby daje użytkownikowi sekund wchłonąć co się stało. I wtedy złamać. W przeciwnym razie, co mam zrobić? Aktualizować wskaźnik równy strzałka wskaźnik next. Tak właśnie stało się jasne, to znaczy iść tam, używając mojego starego szkolnego notacji. Więc oznacza to po prostu, aby przejść do tego, co jesteś wskazując, które w bardzo Pierwszy przypadek to ja, wskazując na struct z dziewięciu w nim. Więc Poszedłem tam. A potem dot zapis oznacza, uzyskać wartość na następny. Ale wartość, mimo że jest sporządzony jako wąska, to tylko liczba. To adres numeryczny. Więc to jedna linia kodu, czy napisany w ten sposób, tym bardziej tajemnicze sposób, albo w ten sposób, nieco bardziej intuicyjny sposób, oznacza po prostu przesunąć rękę od pierwszego węzła do następnego, i następny, a następnie następny i tak dalej. Tak więc nie będzie zatrzymywać się na innych implementacje wstawiania i usuwania i translacji, dwa pierwsze które są dość zaangażowany. I myślę, że jest to dość łatwe do uzyskania utracone, gdy robi to ustnie. Ale co możemy zrobić, o to spróbuj określić, w jaki sposób najlepiej to zrobić wizualnie. Bo chciałbym zaproponować, że jeśli Aby wstawić elementy do tego istniejącej listy, które składa się z pięciu elementów - 9, 17, 22, 26, i 33 - gdybym zamiar wdrożyć to w kod, trzeba zastanowić się, jak go o to robi. I proponuję podjęcie kroków dziecka przy czym, w tym przypadku mam na myśli, jakie są możliwe scenariusze, które może spotkać się w ogóle? Wdrażając wkładkę dla linked Lista ta okazuje się być Specyficznym przykładem wielkości pięciu. Cóż, jeśli chcesz wstawić numer, jak powiedzieć, numer jeden, i utrzymanie posortowane zamówienie, gdzie oczywiście nie potrzebujesz numer jeden go w tym konkretnym przykładzie? Podobnie jak na początku. Ale, co ciekawe, nie jest to, że jeśli chcesz wstawić jeden w to lista, co wymaga specjalnego wskaźnika być aktualizowane podobno? Po pierwsze. Więc jestem zdania, jest to pierwszy przypadek że możemy rozważyć, scenariusz obejmujący wprowadzenie w początek listy. Chcę wyrwać się może tak proste, a nawet łatwiejsza sprawa, relatywnie rzecz biorąc. Załóżmy, że chcę, aby wstawić Numer 35 w uporządkowanej kolejności. To oczywiście należy tam. Więc co wskaźnik oczywiście będzie musiały być aktualizowane w tym scenariuszu? 34 w coraz not null pointer ale adres struktury zawierające numer 35. Więc to jest sprawa dwóch. Więc już jestem rodzaj kwantyzacji jak wiele pracy muszę zrobić tutaj. I wreszcie, oczywista sprawa środku jest rzeczywiście, w środku, jeśli chcę wstawić coś jak powiedzmy 23, która wykracza między 23 a 26, ale teraz robi się trochę bardziej udział, bo to, co wskaźniki muszą być zmienione? Więc 22 oczywiście musi być zmienione bo nie może wskazywać na 26 więcej. Musi wskazywać nowego węzła Muszę przyznać, dzwoniąc malloc lub jakiś odpowiednik. Ale wtedy też trzeba, że ​​nowy węzeł, 23 w tym przypadku, aby jej wskaźnik wskazując na kogo? 26. I nie będzie Kolejność operacji tutaj. Bo jeśli robię to głupio, a ja na początku przykład na początku lista, a moim celem jest, aby włożyć 23. I sprawdzić, czy to należy tutaj, w pobliżu dziewięciu? Nie. Czy to miejsce jest tutaj, obok 17? Nie. Czy to należy tu obok 22? Tak. Teraz, gdy jestem głupi tutaj, a nie myśląc, że to dzięki, ja mogę przeznaczyć mój nowy węzeł 23. Mogę zaktualizować wskaźnik z węzeł o nazwie 22, wskazując go w nowym węźle. A to co mam do aktualizacji nowy węzeł w pointer być? STUDENT: [niesłyszalne]. SPEAKER 1: Dokładnie. Wskazując na 26. Ale dammit jeśli nie już aktualizować Wskaźnik 22 do punktu na tego faceta, a teraz mam sieroty, reszta z listy, że tak powiem. Więc tu kolejność operacji będzie ważne. Aby to zrobić mogłem ukraść, powiedzmy, sześciu wolontariuszy. I zobaczymy, czy nie można tego zrobić wizualnie zamiast kodu mądry. I mamy jakiś piękny stres Piłki dla Ciebie dzisiaj. OK, jak o jeden, dwa, w back - na koniec. trzy, cztery, oboje faceci na koniec. I pięć, sześć. Jasne. Pięć i sześć. W porządku, a my się do was następnym razem. Dobra, chodź się. Dobrze, skoro jesteś tu pierwszy, chcesz być jednym niezgrabnie w szkle Google tutaj? W porządku, więc OK, szkło, nagrać film. OK, jesteś dobry, aby przejść. W porządku, więc jeśli faceci mogą przyjść tutaj, mam przygotowany wcześniej niektóre numery. Dobra, chodź tutaj. A dlaczego nie można pójść trochę dalej w ten sposób. I zobaczymy, jak się nazywasz, ze szkłem Google? STUDENT: Ben. SPEAKER 1: Ben? OK, Ben, będzie pierwszym, dosłownie. Więc mamy zamiar wysłać na koniec etapu. Dobra, i masz na imię? STUDENT: Jason. SPEAKER 1: Jason, OK będziesz być numer dziewięć. Więc jeśli chcesz śledzić Ben ten sposób. STUDENT: Jill. SPEAKER 1: Jill, masz zamiar być 17, które, gdybym zrobił to bardziej inteligentnie, musiałbym rozpoczyna się na drugim końcu. Idziesz w ten sposób. 22. A ty jesteś? STUDENT: Mary. SPEAKER 1: Mary, będziesz 22. A masz na imię? STUDENT: Chris. SPEAKER 1: Chris, będziesz 26. I wtedy wreszcie. STUDENT: Diana. SPEAKER 1: Diana, będziesz 34. Więc chodź tutaj. W porządku, więc doskonalić klasyfikowane zamówić już. I idziemy dalej i to zrobić tak, że możemy naprawdę - Ben jesteś po prostu rodzaj patrzenia się do nigdzie nie. OK, więc idziemy do przodu i przedstawiają to przy użyciu broni, podobnie jak I było dokładnie,, co się dzieje. Więc idź naprzód i dać sobie stopa lub dwie od siebie. I śmiało zwrócić się z jednej strony do kto powinien być skierowany na na tej podstawie. A jeśli jesteś zerowy tylko wskazać prosto w dół na podłogę. OK, tak dobrze. Więc teraz mamy połączonej listy, i niech mnie zaproponować, że będę grać rolę PTR, więc nie przeszkadza realizacji tego wokół. A potem - ktoś głupi konwencji - można nazwać to, co chcesz - wskaźnik poprzednika, pred pointer - to tylko pseudonim daliśmy w nasz przykładowy kod do mojej lewej ręki. Z drugiej strony, że będzie utrzymanie śledzić, kto jest kim w Poniższe scenariusze. Więc przypuszczam, po pierwsze, chcę wyrwać się że pierwszy przykład wstawiając, powiedzmy 20, w liście. Więc będę potrzebował kogoś do ucieleśnieniem numer 20 dla nas. Więc muszę kogoś malloc publiczności. Chodź na górę. Jak masz na imię? STUDENT: Brian. SPEAKER 1: Brian, wszystko w porządku, więc jest węzeł zawierający 20. Dobra, chodź tutaj. I oczywiście, w którym zgadza się Brian należą? Tak więc, w środku - w rzeczywistości, chwileczkę. Robimy to w porządku. Robimy to o wiele trudniejsze nie musi być na początku. OK, jedziemy do swobodnego Briana i realloc Brian jako pięciu. OK, więc teraz chcemy wstawić Brian jako pięciu. Więc chodź tu obok Ben przez chwilę. I można prawdopodobnie powiedzieć gdzie ta historia się dzieje. Ale zastanówmy się dokładnie o kolejność operacji. I to jest właśnie ta wizualna że idzie do linii z tego przykładowego kodu. Więc ja PTR wskazując początkowo nie na Bena, per se, ale bez względu na zawiera on wartość, która w tym przypadku jest - jak masz na imię? STUDENT: Jason. SPEAKER 1: Jason, więc zarówno Ben i ja wskazując na Jasona w tym momencie. Więc teraz muszę ustalić, skąd Brian należą? Więc jedyne, co mam dostęp do teraz jest jego n element danych. Więc mam zamiar sprawdzić, jest Brian mniej niż Jason? Odpowiedź jest prawdziwa. Więc co teraz musi się zdarzyć, w odpowiedniej kolejności? Muszę zaktualizować ile wskaźniki w sumie w tej historii? Gdzie moja ręka wciąż wskazując na Jason, i rękę - jeśli chcesz wkładać rąk jak, coś, I nie wiem, znak zapytania. OK, dobrze. W porządku, więc trzeba kilku kandydatów. Albo Ben albo ja albo Brian i Jason lub każdy inny, który Wskaźniki należy zmienić? Ile w sumie? OK, więc dwa. Mój wskaźnik nie ma znaczenia więcej bo jestem tylko tymczasowe. Więc to ci dwaj faceci, prawdopodobnie, zarówno Ben i Brian. Więc pozwól mi Proponuję uaktualnić Ben, ponieważ on jest pierwszy. Pierwszy element tej listy teraz będzie Brian. Więc punkt Ben na Briana. OK, co teraz? Kto zostanie skierowany na kogo? STUDENT: [niesłyszalne]. SPEAKER 1: OK, więc Brian ma wskazać na Jasona. Jednak nie straciłem tego wskaźnika? Nie wiem, gdzie Jason jest? STUDENT: [niesłyszalne]. SPEAKER 1: ja, ponieważ jestem tymczasowy wskaźnik. I zapewne, że nie uległy zmianie wskazać w nowym węźle. Można więc po prostu punkt Brian co kto jestem, wskazując na. I skończymy. Więc sprawa jedna, wprowadzenie w początek listy. Były dwa kluczowe etapy. One, musimy zaktualizować Ben, a następnie Musimy również zaktualizować Brian. I wtedy nie trzeba się martwić traipsing przez resztę list, bo już znalazł lokalizacja, ponieważ należał do z lewej strony pierwszego elementu. W porządku, więc całkiem proste. W rzeczywistości, czuje się jak jesteśmy prawie czyniąc to zbyt skomplikowane. Więc teraz wyrwać się koniec z listy i zobacz gdzie Złożoność zaczyna. Więc jeśli teraz, alokacja z widowni. Każdy, kto chce grać w 55? Dobrze, widziałem swoją rękę jako pierwszy. Chodź na górę. Tak. Jak masz na imię? STUDENT: [niesłyszalne]. SPEAKER 1: Habata. OK, chodź na górę. Będziesz numer 55. Więc, oczywiście, należą na koniec listy. Warto więc powtórzyć symulację ze mną jest PTR na chwilę. Jestem więc najpierw będzie wskazywać na cokolwiek Ben jest wskazując na. Jesteśmy zarówno wskazując obecnie na Briana. Tak więc 55 jest nie mniejsza niż pięć. Więc mam zamiar aktualizować się przez wskazując na kolejnego wskaźnika Briana, który to oczywiście Jason. 55 nie jest mniejszy niż dziewięć, tak Mam zamiar zaktualizować PTR. Mam zamiar zaktualizować PTR. Mam zamiar zaktualizować PTR I zamierza zaktualizować PTR. I mam zamiar - hmm, co jest masz na imię? STUDENT: Diana. SPEAKER 1: Diana wskazuje, oczywiście, za nieważną z jej lewej strony. Więc skąd Habata faktycznie należy jasno? Po lewej stronie, tutaj. Więc jak mam wiedzieć, aby umieścić ją tutaj Myślę, że wkręca się. Bo to, co jest PTR art ten moment w czasie? Null. Dlatego, mimo że wizualnie, możemy oczywiście zobaczyć wszystkie te Chłopaki tutaj na scenie. I już nie śledzili poprzednie osoby z listy. Nie mam palcem wskazując, w tym przypadku, węzeł numer 34. Warto więc zacząć tę drugą. Więc teraz rzeczywiście jest konieczne Druga zmienna lokalna. I to jest to, co można zobaczyć w rzeczywiste próbki kodu C, gdzie, jak przejść, podczas aktualizacji moją prawą rękę, aby wskazać Jason, pozostawiając tym samym Brian tyłu, I lepiej zacząć używać lewą rękę do aktualizować, gdzie jestem, tak, że jak idę dzięki tej liście - bardziej niezręcznie niż zamierzałem teraz tutaj wizualnie - Mam zamiar dostać się do koniec listy. Ta ręka jest wciąż null, co jest dość bezużyteczne, inne niż wskazuje Jestem oczywiście na końcu listy, ale teraz przynajmniej mam to wskaźnik poprzednika wskazując tutaj, więc teraz to, co się za ręce i co wskaźniki muszą do aktualizacji? Czyja ręka chcesz przekonfigurować pierwszego? STUDENT: [niesłyszalne]. SPEAKER 1: OK, więc Diany. Jeżeli chcesz zaznaczyć Lewy wskaźnik Diany w? Na 55, przypuszczalnie dlatego, że mamy wstawione tam. A gdzie powinien 55 wskaźnik iść? W dół, co stanowi wartość null. I moje ręce, w tym momencie, nie znaczenia, bo były po prostu zmienne tymczasowe. Więc teraz mamy zrobić. Więc dodatkowe komplikacje tam - i to nie jest takie trudne do wdrożenia, ale musimy drugorzędną zmienną, aby upewnić się, że przed I przenieść prawo Ręka, zaktualizować wartość moja lewa Ręka, pred wskaźnik w tym przypadku, tak że mam wskaźnik spływu śledzić, gdzie jestem. Teraz, jak na bok, jeśli myślisz to przez to czuje się jak to jest trochę irytujące, aby zachować śledzenie tego lewej ręki. Co byłoby inne rozwiązanie tego problemu było? Jeśli masz przeprojektować dane Struktura mówimy przez teraz? Jeśli to właśnie niby czuje się trochę irytujące mieć, jak, dwa wskaźniki przejście przez listy, kto jeszcze mógłby nie, w idealnym świecie, utrzymywane Informacje, które nam potrzebne? Tak? STUDENT: [niesłyszalne]. SPEAKER 1: Dokładnie. Prawo więc jest rzeczywiście ciekawa zalążek pomysłu. I ten pomysł poprzedniego wskaźnika, wskazując na poprzednim elemencie. Co zrobić, jeśli tylko zawarte, że Wewnątrz samej listy? I to będzie trudne do wizualizacji to bez wszystkich papieru spada na podłogę. Ale załóżmy, że ci faceci wykorzystywane zarówno ich ręce, aby poprzedni wskaźnik, oraz następne wskaźnik, tym samym realizacji, co będziemy nazywać podwójnie połączonej listy. To pozwoli mi rozwiązać z przewijania, znacznie łatwiej beze mnie, programista, o utrzymanie śledzić ręcznie - naprawdę ręcznie - z, gdzie uprzednio na liście. Więc nie będziemy tego robić. Będziemy to proste, ponieważ jest to przyjdzie w cenie, dwa razy dużo miejsca dla wskaźników, jeśli chcesz drugi. Ale to jest rzeczywiście powszechne Struktura danych znany jako podwójnie połączonej listy. Zróbmy końcowy przykład tutaj i umieścić ci faceci z ich nędzy. Więc malloc 20. Chodź z nawy. Dobra, jak masz na imię? STUDENT: [niesłyszalne]. SPEAKER 1: Przepraszam? STUDENT: [niesłyszalne]. SPEAKER 1: Demeron? OK chodź się. Będziecie 20. Na pewno będą należą między 17 i 22. Więc pozwól mi nauczyć się mojej lekcji. Mam zamiar rozpocząć wskaźnik wskazując na Briana. I zamierzam mieć lewą rękę aktualizować tylko do Briana jak przenieść do Jason, sprawdzenie czy 20 mniej niż dziewięciu? Nie. Czy 20 mniej niż 17? Nie. Czy 20 mniej niż 22? Tak. Więc co wskaźniki lub ręce trzeba zmienić gdzie oni wskazując teraz? Tak więc możemy zrobić 17, wskazując na 20. Więc to jest w porządku. Gdzie chcemy zwrócić Twój wskaźnik teraz? Na 22. I wiemy, gdzie 22 jest ponownie dzięki do mojego tymczasowego wskaźnika. Więc jesteśmy OK tam. Więc z tego powodu czasowego składowania Mam śledził z których każdy jest. A teraz możesz także przejść do których należysz, a teraz musimy 1, 2, 3, 4, 5, 6, 7, 8, 9 stres kulki, i brawa dla ci faceci, jeśli można. Niezła robota. [APPLAUSE] SPEAKER 1: W porządku. A może zachować kawałki papieru jako pamiątki. W porządku, więc uwierzcie mi, że to dużo łatwiej przejść przez to z ludzi, niż to z rzeczywistego kodu. Ale to, co znajdziesz w chwilę teraz, jest to, że same - oh, dziękuję. Dziękujemy - jest to, że przekonasz się, że te same dane Struktura, połączonej listy, może faktycznie być używana jako element do jeszcze bardziej wyrafinowanych struktur danych. I uświadomić sobie zbyt tematu jest to, że my absolutnie wprowadziła więcej Złożoność do realizacji tego algorytmu. Insertion, a jeśli byliśmy przez to, usuwanie i wyszukiwanie, jest mało bardziej skomplikowane, niż to było z tablicą. Ale zdobyć dynamizm. Dostajemy adaptacyjną strukturę danych. Ale znowu, płacimy cenę jedne Dodatkowa złożoność, zarówno realizacji. A my zrezygnowali swobodny dostęp. I szczerze mówiąc, to nie jest jakiś ładny czyste szkiełko mogę ci dać, że mówi o to, dlaczego połączonej listy jest lepsze niż tablicy. I pozostawić go na tym. Ponieważ tematem ponownie pojawiła się teraz, nawet bardziej w najbliższych tygodniach, to że niekoniecznie Prawidłowa odpowiedź. To dlatego mamy oddzielną oś projektu dla zestawów problemowych. To będzie bardzo kontekstowa czy chcesz korzystać z tych danych Struktura lub jeden, i będzie zależy od tego, co jest dla Ciebie w zakresie zasobów i złożoności. Ale pozwól mi zaproponować idealne dane Struktura, Święty Graal, byłoby coś, co jest stała czasowa, niezależnie od tego, jak wiele rzeczy jest wewnątrz niego, nie byłoby to zdumiewające, jeśli Struktura danych zwróciło odpowiedzi w stały czas. Tak. Słowo to jest w ogromnym słownika. Albo nie, to słowo nie jest. Albo takie problemu. No zobaczymy, czy nie możemy przynajmniej zrobić krok w kierunku tego. Pozwól mi zaproponować nową strukturę danych, która może być stosowany do różnych rzeczy, w tym przypadku o nazwie hash table. A więc jesteśmy w rzeczywistości powrót do spoglądając na tablicy, w tym przypadku, a nieco arbitralnie, mam wyciągnąć ten hash table jako tablicę z rodzaju tablica dwuwymiarowa - czy raczej jest to przedstawione tu jako dwa dimensional array - ale jest to tylko Tablica rozmiarze 26, tak, że jeśli zadzwoń tabeli tablicy, uchwyt do stołu zerowa jest prostokąt na górze. Uchwyt do stołu 25 jest prostokąt u dołu. I to jest, jak mogę wyciągnąć dane Struktura, w którym chcesz zapisać Ludowej nazwy. Tak na przykład, a nie będę rysować Całość tutaj na napowietrznych, jeśli miał tę tablicę, którą mam teraz zamiar zadzwoń tabeli mieszania, i jest to kolejny lokalizacja zero. To tutaj jest miejsce jeden, i tak dalej. I twierdzą, że chcą wykorzystywać te dane Struktura, w trosce o dyskusji do przechowywania nazw ludzi, Alice i Bob i Charlie i inne takie nazwy. Więc myślę o tym teraz, początków , powiedzmy, słownika z dużą ilością słów. Zdarzają się nazwy w naszym przykładzie tutaj. I to wszystko jest zbyt germane, być może, wdrożenie sprawdzania pisowni, jak my może do problemu ustawić sześć. Więc jeśli mamy tablicę łącznej wielkości 26 tak, że jest to 25. miejsce na dole, i twierdzą, że Alice jest Pierwsze słowo w słowniku Nazwy, które chcę wstawić do pamięci RAM, do tej struktury danych, w którym są instynkty informacją, że Alice Nazwa powinna iść w tej tablicy? Mamy 26 opcji. W przypadku, gdy chcemy umieścić ją? Chcemy ją w uchwycie zera, prawda? Dla Alicji, nazwijmy to zero. I B będzie jeden, i C będą dwa. Więc mamy zamiar napisać Alicji nazwa tutaj. Jeśli następnie włóż Boba, jego Nazwa będzie tutaj. Charlie będzie tutaj. I tak dalej w dół ta struktura danych. Jest to wspaniała struktura danych. Dlaczego? Więc jaki jest czas pracy wstawiając imię ludzkiej w to Struktura danych w tej chwili? Biorąc pod uwagę, że ta tabela jest realizowany, naprawdę, jako tablicę. Cóż to jest stała czasowa. To zamówienie jednego. Dlaczego? Cóż, jak można określić gdzie Alice należy? Patrzysz na których litery jej imienia? Pierwszy. I można się tam dostać, czy jest to ciąg, po prostu patrząc na ciąg Uchwyt zero. Więc zerowego znaku łańcucha. To proste. Zrobiliśmy to w kryptografii tydzień przypisania temu. I wtedy, gdy wiesz, że Alice List jest kapitału, możemy odejmować off 65 lub kapitałowych, jako takiego, daje nam do zera. Więc teraz wiemy, że Alice należy w położeniu zerowym. A biorąc pod uwagę wskaźnik do tych danych struktury, jakiejś, jak długo to weź mnie do znalezienia lokalizacji zera w tablicy? Wystarczy jeden krok, prawda To jest stały czas Z powodu losowego dostępu my Proponowane były cechą tablicy. Tak w skrócie, dowiedzieć się, co index Nazwa z Alicji jest, która jest, w W tym przypadku jest, albo niech po prostu rozwiązać że do zera, przy czym B jest jednym i C jest dwa, dowiedzieć, że obecnie jest stały czas. I wystarczy spojrzeć na jej pierwszej litery, zastanawianie się, gdzie zero jest tablica jest także stały czas. Tak więc technicznie to jest jak dwóch etapach teraz. Ale to jeszcze stała. Tak nazywamy że Big O jednego, więc mamy do tego dodaje Alicja w tabeli stały czas. Ale oczywiście jestem za naiwne, prawda? Co jeśli jest Aaron w klasie? Albo Alicia? Albo jakieś inne nazwy zaczynające się A. W przypadku, gdy mamy zamiar umieścić że człowiek, prawda? To znaczy, teraz jest tylko trzech osób, na stole, więc może należy umieścić Aarona na miejscu zero jeden, dwa, trzy. Racja, może umieścić tutaj. Jednak wtedy, gdy staramy się włożyć Dawida do Ta lista, gdzie ma David iść? Teraz nasz system rozpoczyna łamanie w dół, w prawo? Bo teraz David kończy się tutaj czy Aaron jest rzeczywiście tutaj. A więc teraz cała ta idea posiadania clean struktura danych, która daje nam Wkładki stałe nie ma już czasu stały czas, bo muszę sprawdzić, oh, cholera, ktoś już na miejscu Alicji. Pozwól mi badać resztę tych danych Struktura, szuka miejsca, aby umieścić ktoś taki jak imię Aarona. I tak, że zbyt zaczyna wziąć liniowa. Ponadto, jeśli chcesz, aby znaleźć Aaron w tej strukturze danych, a sprawdzić, a nazwa Aarona tu nie ma. Najlepiej byłoby po prostu powiedzieć, Aarona nie w strukturze danych. Ale jeśli nie zacząć robić miejsce Aaron, gdzie nie powinno być D lub E, to, w najgorszym przypadku, musi sprawdzić, Cała struktura danych, w którym to przypadku nakładanych na coś liniowa wielkości tabeli. Więc wszystko w porządku, ja to naprawić. Problem polega na tym, że miałem 26 elementów w tej tablicy. Pozwól mi to zmienić. Ups. Pozwól mi zmienić go tak, że raczej jest z rozmiar 26 w sumie zauważyć dno Wskaźnik zmieni się na n minus 1. Jeśli 26 jest zdecydowanie zbyt mały dla ludzi " nazwiska, bo jest tysiące Nazwiska na świecie, po prostu zrobić w 100 lub 1000 lub 10000. Miejmy przeznaczyć dużo więcej miejsca. Dobrze, że nie musi zmniejszyć prawdopodobieństwo, że nie będziemy mieć dwa ludzie z nazwiskami od A, a tak, to jechaliśmy spróbować postawić Nazwiska na zero lokalizacji martwych. Oni nadal będzie kolidować, które Oznacza to, że nadal potrzebne jest rozwiązanie, aby umieścić Alice i Aaron i Alicia i inne Nazwy od A gdzie indziej. Ale, jak wielkim problemem jest to? Jakie jest prawdopodobieństwo, że ma kolizji w danych Struktura jak to? Cóż, niech mnie - wrócimy na to pytanie tutaj. I zastanowić się, jak moglibyśmy go rozwiązać w pierwszej kolejności. Pozwól mi wyciągnąć ten wniosek tutaj. Co po prostu opisany jest algorytm, heurystyczny o nazwie liniowy sondowania przy czym, jeśli próbował włożyć coś tu, w tym danych Struktura, która nazywa hash table, i nie ma miejsca tam, dobrze sondy strukturę danych sprawdzenia, czy jest to dostępne? Czy ta Dostępny jest to dostępne? Czy to dostępne? I kiedy w końcu jest, wstawiania nazwę, którą pierwotnie przeznaczone gdzie indziej w tym miejscu. Ale w najgorszym przypadku, jedynym miejscem, może być bardzo bottom danych Struktura, bardzo końca tablicy. Więc adresowania liniowego, w najgorszym przypadku, nakładanych na liniowy algorytm, w którym Aaron, czy zdarza mu się być wstawiony ostatni W tej strukturze danych, Mógłby zderzają się z tym pierwszym miejscu, ale następnie zakończyć pecha na samym końcu. Więc to nie jest stała Czas święty graal dla nas. Podejście to wstawianie do elementów Struktura danych o nazwie hash Tabela nie wydaje się być stała czasowa a przynajmniej nie w ogólnym przypadku. Może przechodzą w coś liniowego. Co z tego, że rozwiązania kolizji nieco inaczej? Więc tutaj jest bardziej wyrafinowane podejście do tego, co jeszcze zwany hash table. I mieszania, jak na bok, co Mam na myśli to, że index I, o którym mowa wcześniej. To może być coś hash traktowane jako czasownika. Więc jeśli hash Alice jest nazwa, funkcja skrótu, by tak rzec, powinny zwracać liczbę. W tym przypadku jest równa zero, jeśli jej miejsce w lokalizacja zero, jeden, jeśli ona należy na Położenie jednego, i tak dalej. Więc moja funkcja skrótu do tej pory nie było super proste, tylko patrząc na Pierwsza litera w czyimś imieniu. Ale funkcja przyjmuje jako hash input jakiś fragment danych, ciąg, int, cokolwiek. I to wypluwa zazwyczaj liczbę. I jest to numer, w którym te dane Element należy w strukturze danych znany tutaj jako tabeli mieszania. Więc po prostu intuicyjnie, to jest nieco inny kontekst. To rzeczywiście odnosi się do przykładu udziałem urodzin, gdzie nie może być tyle, ile 31 dni w miesiącu. Ale co ta osoba decyduje się zrobić w przypadku kolizji? Kontekst teraz jest, a nie zderzenie nazwy, ale zderzenie urodziny, jeśli dwie osoby mają urodziny tego samego dnia 2 października, na przykład. STUDENT: [niesłyszalne]. SPEAKER 1: Tak, tak, mamy tutaj efektu dźwigni połączonych listach. Wygląda więc na to trochę inaczej niż my ciągnęliśmy go wcześniej. Ale wydaje się mieć do tablicy po lewej stronie. To jeden indeks na nie szczególny powód. Ale to jeszcze tablica. Jest to tablica wskaźników. A każdy z tych elementów, każdy z te koła albo tnie - slash reprezentujący zerowy - każda z nich Wskaźniki najwyraźniej wskazując co struktura danych? Połączonej listy. Więc teraz mamy zdolność do trudno kod do naszego programu Wielkość stołu. W tym przypadku wiemy, że nigdy nie jest więcej niż 31 dni w miesiącu. Tak ciężko kodowania wartości jak 31 jest uzasadnione w tym kontekście. W związku z nazwami, trudno kodowania 26 to nie jest bezzasadne Ludowej Nazwy tylko rozpocznie się, na przykład, alfabet z udziałem do Z. Możemy dopchać je wszystkie do tych danych Struktura tak długo, jak długo, kiedy dostajemy kolizji, nie szuka nazwy tutaj, my, a nie myśleć o tych komórek Nie jako łańcuchy same, ale, jak wskaźniki do, na przykład, Alice. A potem Alice może mieć inny wskaźnik do innej nazwy, wychodząc z A. I Bob rzeczywiście idzie tutaj. A jeśli nie ma innej nazwy zaczynające z B, że kończy się tutaj. I tak, każdy z elementów tej Stół dwa, jeśli to zaprojektował trochę bardziej inteligentnie - chodź - jeśli zaprojektowany to trochę więcej sprytnie, teraz staje się dane adaptacyjne struktury, w których nie ma sztywny limit na ile elementów można wstawić do niego, bo jeśli masz kolizji, to w porządku. Po prostu idź i dołączyć go do co widzieliśmy trochę temu było znana jako związana listy. Dobrze niech przerwę na chwilę. Jakie jest prawdopodobieństwo kolizji W pierwszej kolejności? Dobrze, może jestem na myśli, może Jestem na inżynierii ten problem, bo wiesz co? Tak, mogę wymyślić dowolny przykłady od szczytu mojej głowy jak Allison i Aaron, ale w rzeczywistości, biorąc pod uwagę równomierny rozkład wejścia, które jest kilka losowych wstawki do struktury danych, co tak naprawdę jest Prawdopodobieństwo kolizji? Cóż okazuje się, że to rzeczywiście bardzo wysokie. Pozwól mi generalizować tego Problemem jest, jak to. Więc w pokoju n CS50 studentów, co jest Prawdopodobieństwo, że co najmniej dwóch studentów w pokoju mają takie same urodziny? Więc nie ma co. Kilka Hund - 200, 300 ludzi tutaj i kilka sto osób w domu dzisiaj. Więc jeśli chcesz, aby zadać sobie pytanie, co jest Prawdopodobieństwo dwóch osób w tym pokoju o tym samym urodziny, możemy to rozgryźć. I twierdzą, faktycznie istnieją dwie osób z tej samej urodziny. Na przykład, czy ktoś ma dzisiaj urodziny? Wczoraj? Jutro? W porządku, więc czuje się jak idę aby to zrobić 363 lub tak więcej razy, aby rzeczywiście zrozumieć jeśli mamy kolizję. Albo może po prostu to zrobić matematycznie zamiast żmudnego to robi. I proponuję następujące. Tak więc proponuję, że możemy modelować prawdopodobieństwo dwóch osób posiadających same urodziny jak prawdopodobieństwo 1 minus prawdopodobieństwo nikt o same urodziny. Tak więc, aby to, co jest po prostu fantazyjny sposób na piśmie, to, na pierwsza osoba w pokoju, on lub ona może mieć jedną z możliwych urodzin zakładając 365 dni w roku, z przeprosinami do osób z lutego 29. urodziny. Tak więc pierwszą osobą w tym pokoju jest bezpłatna mieć dowolną liczbę urodzin z 365 do możliwości, tak, że zrobimy to 365 podzielić przez 365, który jest jeden. Następna osoba w pokoju, jeśli celem jest, aby uniknąć kolizji, może tylko tego, by jego urodziny, w jaki sposób wiele różnych możliwych dzień? 364. Więc druga kadencja w tej wypowiedzi jest zasadniczo robi to dla nas matematyki odejmując od jeden możliwy dzień. A następnego dnia, następnego dnia, Następnego dnia w dół do liczby całkowitej osób w pokoju. A jeśli się zważy, co następnie jest prawdopodobieństwo nie z każdego posiadającego wyjątkowe urodziny, ale znowu 1 minus że to, co mamy, jest wyrazem , które mogą bardzo fantazyjnie wyglądać tak. Ale to jest bardziej interesujące przyjrzeć się wizualnie. To jest wykres, w którym na osi x ilość osób w pokoju, liczba urodzin. Na osi y jest prawdopodobieństwo kolizji, dwie osoby o same urodziny. I na wynos z tej krzywej jest , że tak szybko, jak można dostać się do jak 40 studentów, jesteś na poziomie 90% prawdopodobieństwem combinatorically dwóch lub więcej osób posiadających same urodziny. A kiedy już się do jak 58 osób to jest prawie 100% szansę dwóch osób w pokoju będziemy mieć same urodziny, choć jest 365 lub 366 możliwych wiadra i tylko 58 osób w pokoju. Tylko statystycznie jesteś prawdopodobnie uzyskać kolizji, które w skrócie motywuje tę dyskusję. Że nawet jeśli mamy ochotę tu i start o te łańcuchy, nadal jesteśmy będzie mieć kolizji. Tak, że nasuwa się pytanie, co jest koszty prowadzenia wstawienia i usunięcia w strukturze danych, takich jak ta? Więc pozwól mi zaproponować - i pozwól mi wrócić do ekranu na tutaj - jeśli mamy n elementów w lista, więc jeśli chcemy wstawić n elementów, a my mamy Ile razem wiadra? Powiedzmy 31 Wszystkie wiadra w przypadku urodzin. Jaka jest maksymalna długość jednego z tych łańcuchów potencjalnie? Jeśli znowu nie ma 31 możliwe urodziny w danym miesiącu. A my po prostu zbicie wszystkich - faktycznie jest to głupi przykład. Zróbmy 26 zamiast. Więc jeśli rzeczywiście mają ludzi, których nazwy zacząć do Z, dając tym samym nas 26 możliwości. I używamy strukturę danych jak jeden po prostu zobaczył, gdzie mamy Tablica wskaźników, z których każda wskazuje na połączonej listy, gdzie na Pierwsza lista jest każdy o nazwie Alice. Druga lista jest każdy z nazwy zaczynające się, począwszy z B, i tak dalej. Co jest prawdopodobne, długość każdego z wykazy te, jeśli założymy, ładny, czysty podział nazwisk od A do Z w całej strukturze danych? Jest n osób w strukturze danych podzielone przez 26, jeśli są ładnie rozłożone na cały Struktura danych. Tak więc długość każdego z tych łańcuchy są n dzieli się przez 26. Ale w wielkim notacji O, co to jest? Co to jest naprawdę? Więc jest to naprawdę tylko n, prawda? Ponieważ mówiliśmy w przeszłości, że ugh podzielić przez 26. Tak, w rzeczywistości jest to szybsze. Ale w teorii, nie jest zasadniczo wszystko szybciej. Tak więc nie wydaje się być aż tak dużo bliżej tego świętego Graala. W rzeczywistości jest to tylko czas liniowy. Heck, w tym momencie, dlaczego nie wystarczy użyć jednego wielkiego połączonej listy? Dlaczego nie możemy po prostu użyć jeden wielki tablica do przechowywania nazwy wszyscy w pokoju? Cóż, czy jest jeszcze coś, przekonujące o tabeli mieszania? Czy istnieje jeszcze coś fascynującego o strukturze danych który wygląda tak? Ten. STUDENT: [niesłyszalne]. SPEAKER 1: Tak, i jeszcze raz, jeśli to tylko algorytmu liniowej czasu, i liniowa struktura danych, czas, dlaczego nie mogę tylko przechowywać wszystkich na nazwę w big array, lub w dużym listy związane? I przestań robić CS więc znacznie trudniej nie musi on być? Co jest najważniejsze na ten temat, nawet choć podrapał go? STUDENT: [niesłyszalne]. SPEAKER 1: zamontowania nie są? Drogie anymore. Wkładki potencjalnie mogłyby więc nadal być stały czas, nawet jeśli dane struktura wygląda tak, tablicę wskazówek, z których każdy jest skierowany na potencjalnie linked list. Jak można osiągnąć stałą wstawiania Czas nazw? Trzymać go z przodu, prawda? Jeśli poświęcić cel projektu z wcześniej, w którym chcieliśmy zachować Nazwa każdego z nas, na przykład, sortowanie, lub wszystkie liczby w fazie sortowane, Załóżmy, że mamy nieposortowane połączonej listy. To kosztuje tylko nas jeden lub dwa kroki, jak w przypadku Bena i Brian wcześniej, aby wstawić element w początek listy. Jeśli więc nie dbają o sortowaniu wszystko o nazwach zaczynających się lub wszystkich nazwy zaczynające się na literę B, możemy nadal uzyskania stałej wstawianie czasu. Teraz patrząc na Alicję lub Boba lub dowolną nazwę ogólnie jest jeszcze co? Jest duży O n dzieli się przez 26, w idealnym przypadku, w którym każdy jest jednakowo rozdzielone, gdzie jest tak wiele tych jak są z tych, co jest prawdopodobnie nierealne. Ale to wciąż liniowa. Ale tu wracamy do punktu asymptotycznej notacji razie teoretycznie prawdziwe. Ale w prawdziwym świecie, jeśli twierdzą, że mój program może zrobić coś 26 razy szybciej niż twój, których program, zamierzacie wolą używać? Pozdrawiam i moje, które jest 26 razy szybciej? Realistycznie, osoba, której jest 26 razy szybciej, nawet jeśli teoretycznie nasze algorytmy działają w ten sam asymptotycznej czasu pracy. Pozwól mi zaproponować inny rozwiązanie całkowicie. A jeśli to nie cios umysłu, jesteśmy obecnie struktur danych. Więc to jest to trie - rodzaj głupiej nazwie. Pochodzi z wyszukiwań, a słowo jest wpisany Trie, t-r-i-e, z powodu pobieranie kursu brzmi jak trie. Ale to już historia z trie słowo. Więc trie jest rzeczywiście jakimś drzewie, i jest to także gra na tym słowie. I choć nie można zupełnie go zobaczyć z tej wizualizacji, trie jest drzewo skonstruowane, jak drzewo z rodziny jeden przodek na górze i wiele wnuków i wnuków wielkich jak liście na dole. Ale każdy węzeł w trie jest tablicą. I to jest w tablicy - i niech to Upraszczając chwilę - to tablicy, w tym przypadku, wielkość 26, gdzie każdy węzeł znowu jest tablica rozmiarów 26, w którym element zerowym tym, że tablica reprezentuje, a ostatni elementem każdej takiej tablica reprezentuje Z. Więc proponuję, to, że dane Struktura, znane jako trie, może być wykorzystywane również do przechowywania słowa. Widzieliśmy przed chwilą, jak możemy przechowywać słowa, czy w tym przypadku nazwy, a my Widzieliśmy wcześniej, jak można zapisać numery, ale jeśli skupimy się na nazwach i smyczki tu zauważyć, co jest interesujące. I twierdzą, że nazwa Maxwell jest wewnątrz tej struktury danych. Gdzie widzisz Maxwell? STUDENT: [niesłyszalne]. SPEAKER 1: Na lewo. Więc co jest ciekawe, z tych danych struktura jest zamiast przechowywać ciąg M--X-W-E-L-L backslash zero, wszystkie ciągły, co zamiast tego zrobić jest następujący. Jeśli jest to Trie jak struktury danych, węzłów, z których każda jest ponownie tablicą, i chcesz przechowywać Maxwell, najpierw Indeks i tak korzeń w węzeł, tak mówić, najwyższą węzeł, na miejscu m, prawa, tak mniej więcej w środku. A potem od tego, należy wykonać wskaźnikiem do węzłów potomnych, że tak powiem. Więc w tym sensie, drzewo genealogiczne, wykonać go w dół. I które prowadzą do innego węzła Po lewej stronie, która jest tylko kolejna tablica. A potem, jeśli chcesz zapisać Maxwell, znajduje się wskaźnik, który reprezentuje , Co jest tym tutaj. Następnie należy przejść do kolejnego węzła. I uwaga - jest to, dlaczego obraz jest trochę mylące - ten węzeł wygląda bardzo malutki. Ale z prawej strony jest to Y i Z. To tylko autor obcięty obraz tak, że rzeczywiście zobaczyć rzeczy. W przeciwnym razie ten obraz będzie niezwykle szeroki. Więc teraz wskaźnik do lokalizacji X, to W, A E, a następnie L, następnie L. Wtedy co ta ciekawość? Cóż, jeśli używamy tego rodzaju nowa podjąć jak przechowywać ciąg w struktury danych, trzeba jeszcze zasadniczo sprawdzić się w danych Struktura, że ​​słowo kończy się tutaj. Innymi słowy, każdy z tych węzłów jakoś musi pamiętać, że faktycznie po tych wszystkich wskaźników i zostawiając niewiele miękiszu chleba w dolnej tu ta Struktura wskazać M-A-X-W-E-L-L jest Rzeczywiście, w tej strukturze danych. Więc możemy to zrobić w następujący sposób. Każdy z węzłów w obrazie po prostu Pilarka posiada jedną, tablicę wielkości 27. I to jest teraz 27, ponieważ w punkcie ustawić sześć, my faktycznie daje apostrof, więc możemy mieć nazwy takie jak O'Reilly i inni z apostrofy. Ale sam pomysł. Każdy z tych elementów punkty tablicy na strukturę węzeł, tak właśnie węzeł. Więc to jest bardzo przypomina z naszej listy. A potem mam Boolean, które będę nazywamy słowo, które jest po prostu będzie true, jeśli słowo kończy się na tym węzeł w drzewie. Skutecznie reprezentuje trochę trójkąt widzieliśmy przed chwilą. Więc jeśli słowo kończy się na tym węźle Drzewo, które pole słowo będzie prawdą, który jest koncepcyjnie sprawdzanie off, lub rysujemy ten trójkąt, tak nie Jest to słowo tutaj. Więc to jest trie. I teraz pytanie, co jest jego czas pracy? Czy jest to duże O n? Czy jest coś jeszcze? Cóż, jeśli n nazw w tych danych Struktura, Maxwell jest tylko jednym z im, co to jest czas pracy wkładania lub znalezienie Maxwell? Co jest czas pracy wstawiania Maxwell? Jeśli jest n inne nazwy Już w tabeli? Tak? STUDENT: [niesłyszalne]. SPEAKER 1: Tak, to jest długość imienia, prawda? Tak M--x-w-e-l-l, więc czuje się jak to Algorytm jest duży O siedmiu. Teraz, oczywiście, nazwę będą różnić się długością. Może to krótka nazwa. Może to już nazwa. Ale to, co jest kluczem do tego jest to, że jest to stała liczba. A może i to naprawdę nie jest stała, Ale Bóg, jeśli realnie, w słownik, prawdopodobnie niektóre limitu od liczby liter w nazwisko osoby w danym kraju. A więc możemy założyć, że napięcie jest stałe. Nie wiem co to jest. To chyba większe niż uważamy, że jest. Bo zawsze znajdzie się jakiś róg Sprawa z szaloną nazwą długi. Więc nazwijmy to k, ale nadal stała przypuszczalnie, ponieważ każdy wymienić na świecie, przynajmniej w danego kraju, jest to, że długość lub krótszy, więc stała. Ale kiedy powiedziałam, że coś jest duże O o stałej wartości, co to jest naprawdę odpowiada? To naprawdę samo jak mówi stały czas. Teraz jesteśmy rodzajem oszustwa, prawda? Jesteśmy rodzaj dźwigni trochę teorii tutaj, aby powiedzieć, że dobrze, aby k jest naprawdę tylko zamówić z jednym, i to jest stała czasowa. Ale to naprawdę jest. Ponieważ Kluczową kwestią jest to, że jeśli mamy n nazw już w tym struktury danych, a my insert Maxwell, jest ilość czasu potrzebna nam włóż Maxwell w ogóle dotknięte , jak wiele innych osób, znajdują się w strukturze danych? Nie wydają się być. Gdybym miał miliard więcej elementów do tego trie, a następnie włóż Maxwell, jest on w ogóle dotyczy? Nie. I to w przeciwieństwie do każdego z dni danych Struktury widzieliśmy do tej pory, gdzie czas pracy swojego algorytmu jest całkowicie niezależna od tego, ile stuff jest lub nie jest już w tej strukturze danych. I tak z tym daje Ci to szansa dla p zestaw sześciu, które będą ponownie wiązać z realizacją własnych pisowni, czytania w 150000 Innymi słowy, w jaki sposób najlepiej przechowywać że nie zawsze jest oczywiste. I chociaż ja pragnął znaleźć Święty Graal, nie wiem twierdzą, że trie jest. W rzeczywistości, hash table może bardzo dobrze okazać się bardziej skuteczne. Ale to są tylko - to tylko jedna z decyzji projektowych trzeba będzie zrobić. Ale w zamknięciu weźmy 50 lub tak sekundy, aby rzucić okiem na to, co leży przed następnym tygodniu i poza my przejścia z tej linii poleceń świecie, jeśli programy C do sieci rzeczy oparty na PHP i języków, jak i JavaScript i internet sam w sobie, protokoły takie jak HTTP, które już za pewnik na rok teraz, i wpisane najbardziej każdy dzień, być może, ani nie widział. I zaczniemy odwinąć warstwy jakim jest internet. I co to jest kod, który leży u podstaw współczesne narzędzia. Tak więc 50 sekund tego liścik tutaj. I daje Warriors siatki. [PLAYBACK VIDEO] -On przyszedł z wiadomością. Z protokołu wszystkie jego własnym. Przyszedł na świat okrutnych zapór, niedbały routery, i niebezpieczeństwa daleko gorsze niż śmierć. Jest szybki. On jest silny. Jest TCPIP. I ma swój adres. Warriors siatki. [END PLAYBACK VIDEO] SPEAKER 1: To jest jak internet będą pracować w przyszłym tygodniu.