DAVID MALAN: W porządku. Witamy z powrotem do CS50. To jest początek tygodnia 8. I przypominają, że zestaw problemem 5 zakończony z odrobiną wyzwanie. Więc zakładając, że odzyskane wszystkie swoje Fellows nauczania w fotografie i CA w pliku card.raw, masz prawo do teraz znaleźć wszystkie z tych osób, a jeden szczęśliwy zwycięzca będzie chodzić do domu z jednym z tych rzeczy, ruch skok Urządzenie, które można używać do finału projekty, na przykład. To, co roku, prowadzi do Trochę creepiness. A więc to, co myślałem, że robię to akcja z tobą kilka notatek, które mają poszedł w tę iz powrotem nad lista pracowników późno. Na przykład, tylko ostatniej nocy, cytatem Unquote, ze jeden z pracowników członków, "miałem tylko pukanie studentów do moich drzwi, aby zrobić zdjęcie ze mną. Stalker, mówię wam. "Zaczęło się dość opisowe, a następnie przenieśliśmy na, godzinę później: "Miałem Student czeka na mnie po sekcji i miał wszystkie nasze nazwiska i zdjęcia na niektórych arkuszach papieru. "Wszystko w porządku. Tak zorganizowany, ale nie wszystko, co przerażający jeszcze. Następnie, "I nie było w mieście w ten weekend, i kiedy wróciłem, nie było jednym z mój sypialnia. "[śmiech] DAVID MALAN: Następny cytat z personelem członkiem, "uczeń przyszedł do mojego domu w Somerville o 4 rano to rano. "Next Pracownicy, "Mam do mojego hotelu w San Francisco i czeka na studentów mnie w holu z trzech lustrzanek. " Typ aparatu. "Nie jestem nawet na pracowników w tym semestrze, ale uczeń włamał się do mojego domu, to rano i nagrał całość ze szkłem Google. "I wtedy wreszcie, "Co najmniej 12 osób, były chętnie czekając na mnie, kiedy wyszedłem z limo, a następnie I obudziłem się. "Wszystko w porządku. Więc między zdjęciami, jak możesz przypominam, to ten facet tutaj, z kim może wiedzieć, jak Milo banan, który żyje z Lauren Carvalho, nasza głowa nauczania Fellow. Milo, Milo, chodź tutaj chłopcze. Milo. Milo. Pamiętaj, on sobie Google szyby, więc pokażemy wszystko po. Więc to jest Milo jeśli chcesz zrobić zdjęcie z nim później. Jeśli chcesz, aby zwrócić uwagę na publiczność tam. OK. To dobry materiał. Cóż, Milo Banana. Oh, nie rób tego. [Śmiech] OK. Więc słowa następnie na co przede mną, bo jak zaczniemy przejścia, w tym tygodniu specjalnie, z C w środowiska wiersza polecenia do PHP i JavaScript i SQL i HTML i CSS w web-based środowiska, będziemy wyposażanie Ci wszystko więcej wiedzy na potencjalnych ostatecznych projektów. Pod tym celu, kurs ma Tradycja organizowania seminariów, które są na stycznych tematów w toku. Bardzo podobne do programowania i rozwój aplikacji i tak dalej, ale niekoniecznie zbadane przez Kurs własny program nauczania. Więc jeśli może być zainteresowany w jednym lub więcej z tegorocznych seminariów, Zarejestruj się w cs50.net/seminar. Są starsze seminaria w cs50.net/seminars. A na zaplanowany tak daleko w tym roku są niesamowite Web Apps z Ruby on Szyny, która jest alternatywnym język PHP. Computational Linguistics. Wprowadzenie do IO, który jest Platforma, która jest używana dla iPhone i iPad rozwój. JavaScript dla Web Apps, omówimy , ale w tym seminarium, to pójdziesz bardziej szczegółowo. Leap Motion, więc będziemy rzeczywiście niektóre naszych przyjaciół z Ruchu Leap, Sama firma, dołącz do nas. Jutro, w rzeczywistości, w celu zapewnienia praktyczne seminarium, jeśli interesujące dla ciebie. Meteor.js, alternatywna technika Nie używając JavaScript w przeglądarce, ale na serwerze. Node.js, który jest bardzo w tym duchu, jak również. Elegancki design Android. Android jest bardzo popularną alternatywą dla iOS i Windows Phone i inne platformy mobilne. I Bezpieczeństwa Web aktywnej obrony. Faktycznie więc, jeśli chcesz do zaangażowania się w to, pozwól mi zanotuj to. Jesteśmy bardzo szczęśliwi, że nasi przyjaciele w Skoku Projekt, który jest startup - urządzenie to tak naprawdę przyszedł się kilka miesięcy temu - łaskawie wpłat 30 takich urządzeń w klasie, jak wielu studentów, jeśli chcesz pożyczyć sprzęt do końca semestru i używać go do rzeczywisty projekt końcowy. Wspierają one wiele języków. Żaden z nich C, żaden z nich PHP, tak realizacji jednego lub więcej z tych seminariów mogą okazać się interesujące. I wszystkie z nich będą filmowane w Wydarzenie, które nie są w stanie uczestniczyć osobiście. Harmonogram zostanie ogłoszony przez napisz jak ugruntować pokoje. I wreszcie, jeśli pójdziesz do projects.cs.50.net, to jest strona internetowa podtrzymujemy każdego roku, że zapraszamy ludzie z tej wspólnoty, wydział, wydziały, personel i oba na zewnątrz do CS50 zaproponować pomysły na projekty. Co to dla grup studenckich. Co to do działów. Więc należy skręcić tam, jeśli masz problemy z niepewności co do tego, co będzie się chciał zająć. Więc ostatni raz, kiedy wprowadzono zapewne bardziej złożone struktury danych, niż bym widać na tydzień ostatnich. My byliśmy za pomocą tablic dość szczęśliwie jako przydatne uproszczona struktura danych. Następnie wprowadziliśmy te, które oczywiście są związane list. I to, co było jedną z motywacji do wprowadzenie tej struktury danych? Tak? Co to jest? PUBLICZNOŚCI: Dynamiczny rozmiar. DAVID MALAN: Dynamiczny rozmiar. Tak więc podczas gdy w tablicy, trzeba znać jej rozmiar z wyprzedzeniem można przeznaczyć go. W połączonej listy, nie wiesz wiedzieć, że. Można po prostu malloc, lub bardziej ogólnie, przeznaczyć dodatkowe węzeł, by tak rzec, kiedy tylko Aby wstawić więcej danych. A węzeł ma góry określone znaczenie. To tylko ogólny termin opisujący jakiś pojemnik, że jesteśmy używając w naszej struktury danych do przechowywania jakiś element zainteresowania, które w tym przypadku stało się całkowite. Ale zawsze kompromis. Więc mamy dynamiczne rozmiary danych struktury, ale jaką cenę płacimy? Co jest minusem linked list? Tak? PUBLICZNOŚCI: wymaga więcej pamięci. DAVID MALAN: To wymaga więcej pamięci, jak dokładnie? PUBLICZNOŚCI: [niesłyszalne]. DAVID MALAN: Dokładnie. Więc teraz mamy wskaźniki podejmowania dodatkowa pamięć, że wcześniej nie potrzebne, ponieważ zaletą z tablicy, oczywiście, jest to, że wszystko jest ciągły, z powrotem z powrotem do tyłu, które daje swobodny dostęp. Bo tylko za pomocą uchwytu kwadratowego wskaźnik oznaczenie lub bardziej technicznie arytmetyka, bardzo prosty dodatek, można uzyskać dostęp do wszelkich elementów w czasie stałym. A w rzeczywistości, to jest rodzaj sugerując inna cena, którą płacimy z połączonej listy. Co się dzieje z systemem czasu coś jak wyszukiwanie, jeśli chcę znaleźć jakąś wartość i wewnątrz z połączonej listy? Co oznacza mój czas pracy się? Big O n. Jeśli jest klasyfikowane do? Co zrobić, jeśli struktura danych jest sortowane? Czy mogę to zrobić lepiej niż duże O n do wyszukiwania? Nie, gdyż w najgorszym przypadku może bardzo dobrze posortowane, ale liczba szukasz może być duży. Może to być liczba 100, która może zdarzyć się wszystko sposób na końcu. A ponieważ można tylko przejść linked list w tej realizacji przez sposób jego pierwszym węźle, jesteś jeszcze trochę pecha. Musisz przechodzić całość od początku do końca, aby wybrać że duża wartość jak 100. Lub w celu określenia, czy jest to nawet nie istnieje. Nie możemy więc zrobić to, co w ciągu danych, algorytm struktura, która wygląda tak? Nie możemy zrobić wyszukiwanie binarne, ponieważ Wyszukiwanie binarne wymaga, że ​​mamy random access. Moglibyśmy po prostu skakać z miejsca na miejsce Położenie bez konieczności wykonywania te bułki tartej w formie wszystkich tych wskaźników. Teraz, jak się nam wdrożyć to? Cóż, jeśli pójdziemy do ekranu tutaj, jeśli możemy szybko reimplement te dane struktura - mój charakter pisma nie wszystko, że tu świetnie, ale spróbujemy. Więc typedef struct, a co ja chcesz się połączyć, to coś tutaj? Node. Więc ja się nas zaczęło. A teraz, co musi być wewnątrz Struktura danych na które pojedynczo powiązana listę? Ile pól? Więc dwa. Jednym z nich jest całkiem proste. Więc int n. I moglibyśmy nazwać n co chcemy, ale powinno być int, czy jesteśmy wdrożenie połączonej listy do liczb całkowitych. A teraz to, co robi drugi Pole musi być? Struct node *. Więc jeśli zrobić węzeł struct *, a potem można nazwać również, co chcę, ale żeby była jasność Zadzwonię to następny, jak robiliśmy. I wtedy zamknę nawiasy klamrowe. A teraz, jak ostatnim razem, I umieścić węzeł tutaj. Ale jeśli mam deklarując to jako węzeł, dlaczego jest tak, że przeszkadza verbose tutaj deklarowania struct node * next, w przeciwieństwie do zaledwie węzła * następnego? Tak? PUBLICZNOŚCI: [niesłyszalne]. DAVID MALAN: Dokładnie. Dokładnie. Ponieważ C naprawdę zabierze cię dosłownie i widzi tylko definicji węzła droga w dół tutaj, nie można odnoszą się do niego tutaj. Mamy więc tego rodzaju prewencyjne deklaracja tutaj, co jest wprawdzie bardziej gadatliwy. Struct węzła, to znaczy możemy uzyskać do niego dostęp Wnętrze struktury danych. I jak na bok, bo to jest staje się trochę bardziej subiektywne teraz, gwiazda może technicznie iść tutaj, Można go tutaj, może nawet go w środku. Musimy przyjąć, w stylu przewodnika Oczywiście, konwencja oddanie gwiazdki obok danych typu, które w tym przypadku, będzie węzeł struct. Ale sprawę w wielu podręcznikach i Internetowe odniesienia, to może rzeczywiście zobaczyć po drugiej stronie. Ale tylko uświadomić sobie, że jak będzie w rzeczywistości pracy i należy po prostu być spójne. Dobrze. Więc to była nasza deklaracja węzła struct. Ale potem zaczęliśmy robić więcej wyrafinowane rzeczy. Na przykład, zdecydowaliśmy się na wprowadzenie coś jak tabeli mieszania. Więc tutaj jest hash table n wielkości, indeksowane od 0 w lewym górnym rogu do n minus 1 na dole po lewej stronie. To może być hash Stół do niczego. Ale to, co wiele rzeczy nie mówimy o użyciu tabeli mieszania dla? Przechowywanie co? Nazwy. Moglibyśmy zrobić nazwiska jak my ostatnio. I rzeczywiście, można przechowywać wszystko. I zobaczymy, to jeszcze raz w PHP i JavaScript. Hash table jest ładny sort of Swiss Scyzoryk, który pozwala na przechowywanie dość dużo, co chcesz w środku to przez skojarzenie klucze z wartościami. Klawisze z wartościami. Teraz w tym prostym przypadku, nasz Klawisze są tylko liczby. Jesteśmy realizacji hash Stół w postaci tablicy. I tak klawisze są 0, 1, 2, i tak dalej. A więc my, jako ludzie, postanowił ostatnio tygodniu, że wiesz co, jeśli jesteśmy zamiar nazw sklepów, po prostu arbitralnie, ale dość rozsądnie, Zakładam, że Alice, name, będzie po prostu być indeksowane do 0. A Bob, nazwa B, będą indeksowane do 1, i tak dalej. Więc mieliśmy mapowanie pomiędzy wejściami, które są ciągami, a hash miejscach, które są liczbami. Tak, że proces ten jest powszechnie znany jako funkcja skrótu, i można naprawdę wdrożyć go w kodzie. Gdybym chciał realizować funkcji skrótu , że robi dokładnie to, co my tylko opisane od ostatniego czasu, może deklaruje funkcję, która przyjmuje jako Wejście na przykład - i zróbmy to w ten Ekran tutaj. Gdybym chciał wdrożyć hash Funkcja, mogę powiedzieć, coś takiego. To będzie powrót int. To będzie się nazywać hash, i to zamierza przyjąć jako argument na ciąg, lub może być bardziej właściwe teraz, i powiedzieć, char *, nazwijmy to s. A potem to wszystko funkcja ma robić, ostatecznie jest powrócić int. Teraz, jak to robi, że może nie być tak oczywiste. Idę do realizacji tego bez forma kontroli błędów teraz. Mam zamiar po prostu ślepo powiedzieć, powrót s, co jest w przedziale 0, minus, powiedzmy, kapitał średnikiem. Całkowicie zepsuty. To nie jest idealne, ponieważ jedno, co będzie, jeśli s jest null? Złe rzeczy się wydarzy. Dwa, co oznacza, że ​​pierwsze pismo w tej nazwa nie litera jest? To nie będzie się obracać się dobrze albo. To może być mała litera lub nie litery ogóle. Więc nic do zrobienia tutaj, ale to jest podstawowa idea. Co opisaliśmy w zeszłym tygodniu ustnie jako tylko proces mapowania Alice do 0 do 1 i Bob może być wyrażona z pewnością bardziej formulaically jako C funkcjonować tutaj. Nazywane ponownie hash, pobiera ciąg jako wejściowego, a następnie w jakiś sposób robi coś z tego wejścia do produkcji wyjście. Nie inaczej naszej czarnej skrzynki opis że mamy długi zrobione. Nie wiem, jak to może być pracuje pod maską. Do zestawu problemów, 6 Jednym z wyzwań jest, aby zdecydować, co będzie twoja funkcja skrótu jest? Co będzie w środku, że czarny box, i prawdopodobnie, to będzie trochę bardziej interesujące niż to, i zdecydowanie bardziej podatne na błędy kontroli niż ta konkretna realizacja. Ale mogą pojawić się problemy, prawda? Jeśli mamy strukturę danych, takich jak ta jeden, co jest jednym z problemów można uruchomić w czasie gdy włożysz coraz więcej do nazwy hash table? Otrzymasz kolizji, prawda? Co zrobić, jeśli masz Alice i Aarona, dwie osoby, których nazwiska się na początek? To nasuwa pytanie, gdzie umieścić drugą taką nazwę? Cóż, może naiwnie, wystarczy umieścić go gdzie Bob należy, ale Bob jest rodzaj wkręca jeśli próbujesz wstaw swoje nazwisko obok i nie ma miejsca dla niego. Więc można umieścić Bob, gdzie jest Charlie, i można sobie wyobrazić, to bardzo szybko przekazanymi do trochę bałaganu. Coś liniowy w końcu, gdzie Wystarczy sprawdzić całość poszukuje Alice i Bob lub Aaron lub Charlie. Zamiast więc zaproponowaliśmy, a nie tylko liniowo sondowania na otwartej przestrzeni i plopping nazwiska tam, proponowany hodowcy podejście. Hash table wdrożone jeszcze z tablica wskaźników, ale typ danych Teraz były wskaźniki te wskaźniki. Wskaźniki do czego? Wskaźniki do połączonych listach. Ponieważ przypomnieć, że lista jest połączony naprawdę tylko wskaźnik do węzła, a węzeł ma następne pole i tego węzła ma kolejne pola, i tak dalej. Więc możesz teraz myśleć o tej tablicy na lewa strona tabeli mieszania jako co prowadzi do połączonej listy. Zaletą, która jest, jeśli się Kolizja między Alice i Aarona, co zrobić z Druga taka osoba? Po prostu podłącz go lub ją end, a nawet początek tego połączonej listy. I rzeczywiście, po prostu makaron przez że na chwilę. Gdzie jak najwięcej sensu? Jeśli wstawić Alice, a ona kończy się na pierwsze miejsce, to staram się wstawić nazwę Aarona, a tam oczywiście kolizji, należy umieścić go na początku z połączonej listy? To w tym pierwszym miejscu, lub na końcu? PUBLICZNOŚCI: [niesłyszalne]. DAVID MALAN: OK. Słyszałem początku. Dlaczego na początku? PUBLICZNOŚCI: [niesłyszalne]. DAVID MALAN: OK. To alfabetycznie, więc to miłe. To dobry obiekt. Pozwoli to zaoszczędzić mi trochę czasu, potencjalnie. To nie pozwala mi zrobić wyszukiwania binarnego, ale może przynajmniej być w stanie wyrwać się z pętli, czy zdaję sobie sprawę, dobrze, jestem droga przeszłości były Aaron będzie w tym klasyfikowane połączonej listy. I nie trzeba tracić czasu na szukanie , aż do końca. Więc to jest rozsądne. Dlaczego jeszcze warto włożyć Nazwa w kolizji początku listy? Co to jest? PUBLICZNOŚCI: [niesłyszalne]. DAVID MALAN: To może zająć dużo czasu, aby dostać się do końca listy. I rzeczywiście, coraz dłuższe. Im więcej wstawione, że nazwy początek, już, że Łańcuch dostanie. Już, że związane lista będzie się. Więc jesteś naprawdę tracić czas. Może lepiej jest utrzymanie stały czas wstawiania, big O 1, by zawsze kładąc na zderzanie nazwę na początek listę, na i nie martwić się, jak wiele o sortowaniu. Jaka jest najlepsza odpowiedź? Nie wiadomo. To rodzaj zależy od tego, co dystrybucji, co jest wzór nazw wstawiasz. To nie jest koniecznie Oczywista odpowiedź. Jednak tutaj, ponownie, jest możliwość projektowania. Więc czym spojrzał na tej rzeczy, które jest naprawdę inna wielka szansa dla p-set 6. I uświadomić sobie, jeśli jeszcze go nie masz, Nurkowań Zamyla do obu z nich, ziemniaki tabele i stara, bardziej szczegółowo. I instruktażu wideo osadzone w p-set specyfikacji. To był trie - T-R-I-E. I co ciekawe o było to, że czas pracy z wyszukiwania nazwy, jak Maxwell ostatni raz, był duży O czym? Co to jest? PUBLICZNOŚCI: liczba liter. DAVID MALAN: Ilość liter. Słyszałem dwie rzeczy. Liczba liter i stałą czasową. Więc idziemy z tym pierwszym. Liczba liter. Cóż, to struktura danych, przypomnijmy, jest jak drzewo, drzewo genealogiczne, każdy z , których węzły są wykonane z tablic. A te tablice są wskaźniki do inne takie węzły lub inne takie tablice w drzewie. Więc jeśli chcemy to ustalić czy Maxwell jest tutaj, mogę iść do pierwszej tablicy, na górze drzewo, tzw root góry trie, a następnie wskaźnik m, to wskaźnik, to x, W, E, L, L. A potem, kiedy widzę jakiś specjalny symbol, oznaczone tutaj jako trójkąt. W kodzie zobaczysz, proponujemy, aby realizowane jako bool, tylko, że tak lub nie, słowo zatrzymuje się tutaj. Cóż, kiedy już odszedł do M-A-W-X E-L-L, czuje się jak siedem, może osiem jeśli idziemy jeden przeszłości, osiem działania w celu znalezienia Maxwell. Albo nazwijmy go K. Ale pamiętam ostatni czas, I argumentował, że jeśli istnieje realnie o maksymalnej długości słowo, np. znaków 40-kilka-nieparzyste, Maksymalna długość oznacza wartość stała. Tak naprawdę, tak, to jest technicznie duże O z 8 lub 7, lub naprawdę duże O K. Ale czy jest na to, co skończone cap K może być, to jest stała. A więc jest to duże O z 1 na koniec dnia. Nie w świecie rzeczywistym. Nie wtedy, kiedy można zacząć oglądać zegar, jak Twój program biegu. To absolutnie będzie nieco wolniej niż naprawdę stała razem z jednym etapie. To będzie siedem lub osiem kroków, ale to jest dużo, dużo lepiej niż algorytm, takich jak Big O n tym zależy od wielkości, co jest w Struktura danych. Wskazówka upside o to możemy wstawić milion w to więcej nazwisk struktury danych, ale ile jeszcze kroków to będzie nas znaleźć Maxwell w tym przypadku? Brak. On jest nienaruszone. I do tej pory, nie sądzę, widzieliśmy Przykład struktury danych lub algorytm, który był całkowicie niezależne od zewnętrznych Zachowania takie jak to. Ale to nie może być niesamowity. To nie może być jedyną na p-set I to nie jest. Niekoniecznie jest dane Struktura należy skłaniają się, bo jak hash tabel, kompromis. Jaka jest cena, jaką płaci się tutaj? Pamięć. To znaczy, to jest okropne ilość pamięci. I nie można dość zobaczyć go tutaj, bo Autor tego obrazu oczywiście obcięte wszystkie tablice, i nie widzimy wiele tych i B i C jest i grupy Q i Y-tych i Z w tych tablicach. Ale oni tam. Każdy z tych węzłów jest cały szereg od około 26 lub więcej, każdy z bajtów która reprezentuje nas. 27 w naszym przypadku, tak, że możemy wspierać apostrofy w zestawie problem. Więc to struktura danych jest naprawdę, bardzo gęsta i szeroka. I że sam może skończyć się spowolnienie rzeczy w dół, lub przynajmniej kosztującej dużo więcej miejsca. Ale znowu, możemy wyciągnąć porównania tutaj. Przypomnijmy, jakiś czas temu, osiągnęliśmy dużo bardziej ekscytujący czas pracy przy sortowaniu kiedy używamy sortowanie korespondencji seryjnej, ale cena zapłaciliśmy osiągnąć n log n do seryjnej sort wymaga, że ​​spędzimy więcej jakiego źródła? Więcej miejsca. Potrzebowaliśmy dodatkowego tablicę skopiować ludzi do, tak jak my tutaj, na scenie. Więc jeszcze raz, nie ma wyraźnych zwycięzców, ale tylko prywatną projekt podejmowanie decyzji. Dobrze. Tak jak o tym? Każdy, kto rozpoznać, które D-Hall? OK. Tak więc trzy z nas. Mather Dom. Jest to więc posiłki Mathera. Założę się, że wszystkie jadłodajnie mają stosy tac tak. I to jest rzeczywiście reprezentatywna coś mamy oczywiście widziałem już. Nazwaliśmy go dosłownie stos. A stos, w związku z Państwa pamięci komputera, gdzie dane idzie natomiast funkcje są nazywane. Na przykład, jakie rzeczy iść na stosie w odniesieniu do układ pamięci Omówiliśmy w tygodniach minionych? Co to jest? PUBLICZNOŚCI: wywołań funkcji. DAVID MALAN: Przepraszam. PUBLICZNOŚCI: wywołań funkcji. DAVID MALAN: Połączenia do funkcji, ale konkretnie, co jest w środku każdego z te ramki? Jakie rzeczy? Tak. Tak więc zmienne lokalne. Anytime potrzebowaliśmy pamięci lokalnej, jak argument, lub int I, lub int temp, czy cokolwiek lokalne zmienna jest, już oddanie, że na stos. I nazywamy to stos, bo tej idei malowania. Tylko rodzaj dopasowania się z rzeczywistością, Koncepcja tej decyzji. Ale okazuje się, że można również stack traktować jako struktury danych, Alternatywą do tablicy, alternatywna do połączonej listy. Coś koncepcyjnie bardziej interesujące , które mogą być jeszcze realizowane przy użyciu jednej z tych rzeczy, ale to jest inny rodzaj Struktura danych wsparcie, naprawdę, tylko dwie operacje. Ale można dodać na hodowcy funkcje niż te. Ale to są podstawy - wcisnąć i pop. A pomysł z komina jest to, że jeśli tu mamy, z lub bez Annenberg wiedząc, tacę z pokoju obok z numerem 9 na nim. Więc po prostu int. I chcę pchać to na danych Struktura, która obecnie jest pusty. Należy to uwzględnić w dolnej części stosu. Chciałbym wcisnąć ten numer 9 na stos, a teraz jest tam. Ale ciekawa rzecz o stosie jest to, że jeśli teraz chcę naciskać inne wartości, takie jak 17, i nacisnąć to na stos, mam zamiar zrobić tylko intuicyjna sprawa, mam zamiar umieścić go tam, gdzie my, ludzie, byłby skłonny umieścić go na górze. Ale co ciekawe teraz jest, jak mogę dostać się na 9? Wiesz, ja nie bez pewnego wysiłku. Tak więc to, co jest ciekawe Stos jest to, że ze względów konstrukcyjnych, to struktura danych LIFO. Silly sposób opisywania ostatnie przyszło pierwsze wyszło. Więc ostatnia liczba w w tym czasie było 17. Więc jeśli chcę coś off pop stosu, to może być tylko 17. Więc jest obowiązkowa kolejność operacje tutaj, gdzie ostatni element w musi być pierwszy na zewnątrz. Stąd skrót, LIFO. Więc dlaczego może to być przydatne? Czy ich konteksty, w których bym chcą strukturę danych jak to? Cóż, to z pewnością przydatne wewnątrz komputera. Więc systemy operacyjne wyraźnie to wykorzystać rodzaj struktury danych na stosach. Będziemy także pojawia się ten sam pomysł jeśli chodzi o stronach internetowych. Więc ten tydzień i tydzień następny i poza nią, i jak rozpocząć wdrażanie sieci strony w języku nazywa HTML, można właściwie wykorzystywać strukturę danych jak To określenie, czy strona jest prawidłowo sformatowana. Ponieważ zobaczymy wszystkie strony internetowe postępuj rodzaj hierarchii, wcięcia która, na koniec dnia, są Struktura drzewa pod maską. Więc więcej o tym za chwilę. Ale na razie niech zaproponować Moment, w jaki sposób możemy go o reprezentujący co stack jest? Pozwól mi zaproponować, że wdrożenie stos z kodem tak. Więc stos będzie miał w jej wnętrzu dwie rzeczy, tablica nazwana tace tylko być zgodne z demo. I każdy z elementów tej tablicy będzie typu int. I pojemność jest prawdopodobnie to, co? Bo ja nie pisałem Pełna definicja tutaj. To chyba maksymalna rozmiar tablicy. I to prawdopodobnie uznane za ostry zdefiniować na początku pliku, niektóre rodzaj stała jak sugeruje Sama kapitalizacja. Więc gdzieś ilość jest zdefiniowana od maksymalnej możliwej wielkości. W międzyczasie, wewnątrz struktury danych znany jako stos nie będzie być liczbą całkowitą tylko znane po prostu jako wielkości. Więc gdybym miał reprezentować to teraz obrazowo, załóżmy, że to Cała czarna skrzynka reprezentuje mój stos. Wewnątrz niej ma dwie zmienne. Więc mam zamiar wyciągnąć Pierwszy z nich, jak wielkości. I drugi idę narysować w postaci tablicy. Ale tylko do przechowywania rzeczy uporządkowany, normalnie chciałbym zwrócić tablicę jak ta, ale to miłe jeśli mecz rzeczywistość, lub dopasować model mentalny. Więc pozwól mi zamiast zwrócić tablicę pionowo, która jest po prostu, znowu, odtworzeniem. Tak naprawdę nie ma znaczenia, co to jest pod maską. I powiemy, że domyślnie, pojemność ma być trzy. Tak więc będzie to Położenie 0, ta będzie miejsce 1, to będzie położenie 2. Gdybym przekupić z piłką na stres, by ktoś chciał wymyślić i uruchomić wsiąść tu tylko na chwilę? OK, zobaczyłem rękę pierwszy. Chodź na górę. Dobrze. Tak więc uważam, że jest Steven. Chodź na górę. Dobrze. Ale przypuśćmy, że teraz możemy cofnąć się do początkowego stan świata, gdzie właśnie oświadczył, stos, i to będzie o pojemności trzech. Ale wielkość nie została jeszcze ustalona. Brodziki nie została jeszcze ustalona. Więc kilka pytań pierwsze. I pozwól mi dać mikrofon, dzięki czemu można bardziej aktywnie uczestniczyć w tym. Więc co jest w środku wielkości w tej chwili w czasie, gdy wszystkie Zrobiłem to oświadczył stos z jedna linia kodu? STEVEN: Nie bardzo. DAVID MALAN: OK, nie wiele. Czy wiemy, co jest w środku od wielkości, wiemy, co jest w środku tej tablicy tutaj? STEVEN: Just losowy kod, prawda? Po prostu - DAVID MALAN: Tak, mam zamiar Nazywamy to kod, ale random - STEVEN: Co. DAVID MALAN: Rzeczy takie jak random STEVEN: Bits. DAVID MALAN: Bity, prawda? Tak więc wartości śmieci, prawda? Więc permutacje 0 i 1-tych. Pozostałości wcześniejszych zwyczajów tej pamięci. I tak naprawdę nie wiem jakie wartości są, więc zazwyczaj wyciągnąć je jako znaki zapytania. Tak więc pierwszą rzeczą, że jesteśmy prawdopodobnie będzie chciał zrobić tutaj - i pozwól mi dać to pole wewnątrz stamtąd nazwa - tacki. Co powinniśmy przypuszczalnie zainicjować rozmiar do jeżeli chcemy rozpocząć korzystanie z tego stosu? STEVEN: Tray jest sub 3. DAVID MALAN: Tak, OK. Żeby było jasne, pojemność jest zadeklarowana gdzie indziej, jak trzy. I to jest to, co ja użyłam przydzielić tablicę. Rozmiar ma zamiar odwołać się do tego, jak wiele Tacki są obecnie na stosie. STEVEN: Zero. DAVID MALAN: Tak powinno być zero. Więc śmiało, a z każdym palcem, narysować zero w wielkości. Dobrze. Więc teraz, co jest w środku tego tutaj, nie wiemy. Są to tak naprawdę wartości śmieci. Więc możemy narysować znaki zapytania, ale trzymajmy teraz czysty deska bo to nie ma znaczenia co tam jest. Nie musimy zainicjować tablicę do niczego, bo jeśli wiemy, że Rozmiar stosu jest równa zero, oraz, że nie powinny być patrząc na coś w ta tablica i tak w ten punkt w czasie. Przyjmijmy teraz, że wciskam Numer 9 na stos. Jak powinniśmy zaktualizować strukturę danych wewnątrz tej czarnej skrzynki? Jakie wartości należy zmienić? STEVEN: W - rozmiar? DAVID MALAN: OK. Rozmiar powinien być, co? STEVEN: Rozmiar będzie jeden. DAVID MALAN: OK. Tak więc wielkość powinna stać się jednym. Więc można to zrobić w kilka sposobów. Podam teraz swoje palec jest gumka. Dobrze. Właśnie teraz palec jest szczotka. Dobrze. A teraz, co jeszcze musi się zmienić, Oczywiście, w strukturze danych? STEVEN: Jedziemy z bottom up to 9. DAVID MALAN: 9. OK, Good. Tak więc nadal nie ma znaczenia, co jest w miejsce jeden lub dwa, ponieważ są one wartości śmieci, ale nie przeszkadza patrząc tam, bo rozmiar jest mówi nam, że tylko pierwszy element jest rzeczywiście uzasadnione. Więc teraz wciskam 17 na liście. Co się dzieje z tym zdjęciem? STEVEN: Tak rozmiar będzie iść do dwóch. DAVID MALAN: OK. Jesteś gumka - oops. Jesteś gumka. STEVEN: Eraser. DAVID MALAN: Jesteś brush. STEVEN: Brush. DAVID MALAN: OK. I co jeszcze? STEVEN: A potem - DAVID MALAN: Mamy pchnął 17. STEVEN: Trzymamy 17 na górze, więc - DAVID MALAN: OK, dobrze. STEVEN: - spadek w dół. DAVID MALAN: W porządku. Robi się łatwo. I nie zamierzam pomóc tym razem. Naciśnij 22. STEVEN: Gotowe. Staje gumka. Staję się szczotki. A potem kładę 22. DAVID MALAN: 22. Excellent. Więc jeszcze raz. Mam teraz zamiar naciskać na stos 26. STEVEN: Ooh. Oh Boże. Naprawdę złapał mnie z tropu. DAVID MALAN: Nie zobacz nadchodzi? STEVEN: Nie widziałem tego spodziewać. Mogliśmy ponownie Początkowa zdolność? DAVID MALAN: To jest dobre pytanie. Więc my niby malowane siebie w kącie tutaj. Czy naprawdę nie jest dobry out dla Steven bo mamy przydzielone tej tablicy statycznie, że tak powiem, w środku struktury danych. A my w zasadzie trudno kodowane że jest z trzech wielkości. Tak naprawdę nie możemy przydzielić go. Możemy, jeśli poszliśmy z powrotem, my nowo tace być wskaźnikiem, że możemy użyć malloc do pamięci rękę do. Bo jeśli mamy w pamięci z heap przez malloc, my może następnie uwolnić go. Ale zanim zwalniając go, możemy przydzielić większą ilość pamięci, aktualizować wskaźnik, i tak dalej. Ale teraz, to jest naprawdę Najlepsze, co możemy zrobić. Naciśnij i pop są prawdopodobnie będzie aby sygnalizować jakiś błąd. Tak na przykład, nasza implementacja push może powrócić bool, który wcześniej zwróciło prawda, prawda, prawda. Ale czwarty raz, to będzie mieć do return false, na przykład. Dobrze. Bardzo dobrze zrobione. Gratulacje. Zasłużyłeś na swoją piłkę stres dzisiaj. [APPLAUSE] STEVEN: Dziękuję. DAVID MALAN: Dziękuję. OK, tak więc wydaje się, że niewiele o krok do przodu, prawda? Opisaliśmy tę strukturę danych. To było przekonujące, prawda? Systemy operacyjne podoba. Podobno w internecie może skorzystać z tego, i inne aplikacje nadal. Ale to, co głupie ograniczenie, że jesteśmy Powrót Sortuj tygodnia dwie granice gdzie mamy ustalone tablice wielkości. Więc rzeczywiście istnieje kilka sposób możemy rozwiązać ten problem. Możemy dynamicznie przydziela tablicę, nie przez trudne kodowanie go jak już odbywa się tutaj, lecz ponownie deklarowania tego, żeby była jasność, jak coś takiego. Int tace * nie, decydując na mocy jeszcze. Ale kiedy Oświadczam stos gdzie indziej w moim kodu, mogłem wtedy zadzwonić malloc, uzyskać adres z kawałkiem pamięci, i mogłem przypisać że adres, na tackach. A potem, bo to po prostu kawał pamięci, mogę nadal korzystać z placu Zapis wspornik w zwykły sposób. Bo znowu, jest jakby to funkcjonalnym odpowiednikiem tablic i fragmenty pamięci, które pochodzą z powrotem z malloc. Możemy traktować jeden od drugiego używając arytmetyki wskaźników lub square notacja uchwytach. Więc to jest jeden sposób. Ale jak inaczej możemy realizować ten Ta sama struktura danych, potencjalnie? Prawda? Czuję się po prostu rozwiązać ten Problem jak tydzień temu. Co było rozwiązanie tego problemu że Steven wpadł? Tak połączone listy, tuż. Jeśli problemem jest to, że mamy do malowania się w rogu, przyznając z góry pamięci zbyt mało, że Następnie trzeba jakoś zająć, dobrze, dlaczego nie tylko uniknąć wydać w sumie? Dlaczego nie wystarczy zadeklarować tace być wskaźnik do węzła, ergo lista powiązana, a potem po prostu przeznaczyć nowe węzły za każdym razem, Steven potrzebne, aby dopasować Numer do struktury danych. Tak więc obraz będzie musiał zmienić. To nie będzie tak czyste, jak i proste, jak tylko tablicą trzech liczb całkowitych. Teraz to będzie wskaźnik do struct, a struktura jest zamiar mają int i następny wskaźnik. To będzie prowadzić za pośrednictwem tego wskaźnika do innej takiej struktury do kolejny przykład struct. Tak więc obraz faktycznie dostać Messier bitowej. A my nie strzałki wiążąc wszystko razem. Ale to jest w porządku, w porządku, bo widzieliśmy, jak to zrobić. A kiedy się komfortowo wdrażaniu coś linked Lista, która musisz zrobić, jeśli Decydując się na zastosowanie tabeli mieszania z oddzielne łańcucha dla p-set 6, można używać go jako element, lub składnik lub w Scratch mówić, procedura, coś, co mówiąc, ci stworzył swój własny kawałek układanki które następnie można ponownie wykorzystać. Więc kompromisów, ale potencjalnych rozwiązań że mamy rzeczywiście widział. Tak często, widzisz to co rok lub dwa, kiedy Apple wypuszcza coś nowego i wszyscy szaleńcy Line up poza Apple przechowywać do zakupu ich marginalna uaktualnienia na sprzęcie. Mówię o tym, że jest OK, bo Jestem jedną z tych osób. Więc jaki rodzaj struktury danych może reprezentować tę rzeczywistość? No cóż, nazwijmy to kolejka, linia. Więc Brytyjczycy nazywają to zwykle kolejki, tak więc jest to ładne imię. I dwie operacje kolejki wspiera my nazywamy Enqueue działanie i Dequeue operacja, które są podobne duch naciskać i pop. To tylko rodzaj różni się Konwencja, z czym mamy do wywoływania tych. Ale enqueue coś znaczy dodawać lub wprowadzić je do struktury danych. To usunie z niej oznacza usunięcie go. Ale podczas gdy stos było dane LIFO Struktura, kolejka jest pierwszym w, Najpierw się struktury danych. Jeśli jesteś pierwszą osobą w kolejce, będzie pierwszym, aby uzyskać z linii i zakupu nowego urządzenia. Wyobraź sobie, jak zdenerwowany osoby te byłyby jeśli Apple zamiast stosować stos, na instancją, do realizacji kompletacji up z nowej zabawki. Więc kolejki sensu, oczywiście, i możemy myśleć o wszelkiego rodzaju aplikacji, prawdopodobnie, w kolejkach, zwłaszcza, gdy chcemy uczciwości. Więc jak możemy realizować te jako struktury danych? Cóż, proponuję, że może musisz zrobić to w ten sposób. Więc mam zamiar teraz mają numery. Będziemy więc zachować proste i nie muszą mówić w kategoriach tac. Tylko liczby, które ludzie zdobyć. Pojemność będzie znów naprawić liczba osób, które mogą być w linia ta, jak trzy lub bez względu na inne wartości. Ale proponuję, że trzeba śledzić nie tylko od wielkości Kolejka, jak wiele rzeczy w nim. Tak więc rozmiar jest obecny rozmiar, pojemność Jest to maksymalny rozmiar. Tylko znowu, nomenklatura umownie. Dlaczego potrzebuję dodatkowego int wewnątrz z kolejki, aby śledzić, kto jest w przed linią? Dlaczego muszę to zrobić w tym przypadku? Cóż, jak to jest obraz zmieni? Prawdopodobnie mogę ponownie najbardziej z tego obrazu. Pozwólcie mi iść dalej i usunąć to, co jest tutaj. Damy to nieco inna nazwa tutaj. Chcę się pozbyć 17, pozbądźmy od 9, niech się pozbyć 3. I dodajmy jeszcze jedno. Proponuję, że trzeba śledzić z przodu listy, która jest po prostu będzie int również. A my jedziemy prosto. Nie powiązane lista teraz. Będziemy przyznać, że mamy zamiar trzaskać się tego limitu. Ale to, co chcę zobaczyć się tym razem? Więc załóżmy, że śmiało i pierwszy osoba pojawia się w linii, a to numer 9. Mamy piłeczki antystresowe. Czy można ukraść, powiedzmy, dwóch lub trzech osób? Jeden, dwa, trzy? Chodź na górę. Od przodu, ponieważ zrobimy to jedno szybkie. Każdy z was jest teraz będzie Chłopiec wentylator w kolejce w Apple. Nie będziesz otrzymywać sprzęt Apple na koniec tego jednak. Dobrze. Więc jesteś numer 9, jesteś numer 17, numer 22. Są to arbitralne liczby, jak Student ID lub cokolwiek. A za chwilę, zacznijmy do dodawania rzeczy. A ja uruchomić płytę tutaj w tym czasie. Więc w tym przypadku, mam zainicjowany przód być - I naprawdę nie obchodzi to, co przednia jest, ponieważ rozmiar jest zerowy. Więc to może równie dobrze być znak zapytania. To wszystko są znaki zapytania. Więc teraz zaczniemy rzeczywiście zobaczyć niektóre ludzie w kolejce w sklepie. Więc jeśli numer 9, jesteś pierwszy tam o 5 rano, iść do przodu i wyrównane, lub nocy. OK. Więc teraz 9 jest tutaj. Tak 9 jest w przedniej części listy. Więc mam zamiar iść dalej i aktualizować rozmiar danych bieżących Struktura nie jest już 0, ale jest 1. Mam zamiar umieścić 9 w początku listy. Pozwólcie mi iść dalej i włączyć ekran więc widzimy obok nas tutaj. A teraz, co chcę oddał do przodu? Będę śledzić, że przód kolejki teraz jest w położeniu 0. Bo to, co jest dalej będzie się działo? Dobrze, załóżmy, że teraz ja enqueue 17, jak również. Więc hop w wierszu. I jeszcze raz, jakby drzwi Sklep będzie tutaj. Więc teraz dodałem 17. I mimo, że ci faceci są blokowanie ekran, to jest OK, ponieważ widzimy go tutaj. Przepraszam. PUBLICZNOŚCI: Możemy przejść - DAVID MALAN: Nie, to jest OK. To ogromna tam. Tak więc 17 jest teraz wewnątrz kolejce. Muszę zaktualizować które pola teraz chociaż? OK, na pewno rozmiar. A co z przodu? OK, nr. Z przodu nie powinno się zmienić, bo w przeciwieństwie do stosu, my Aby zachować bezstronność. Więc jeśli 9 przyszedł pierwszy, chcemy 9 do pierwszej z linii i do sklepu. W rzeczywistości, zobaczmy to. Zanim wstawić 22, niech śmiało Dequeue 9. Jak masz na imię? PUBLICZNOŚCI: Jake. DAVID MALAN: Jake będzie zostać wyjęty z kolejki teraz. Więc masz iść do sklepu. I udawać, że sklep jest tam. Więc co teraz potrzebuje - dit-dit-dit! Co musi się zdarzyć teraz? Projektu decyzji. Więc nie jest to zły instynkt, ale - jak masz na imię? PUBLICZNOŚCI: David. DAVID MALAN: David. Więc co David zrobić? Starał się coś w rodzaju naprawić dane Struktura i ruch od jego lokalizacji w dawnym miejscu Jake'a. I to jest w porządku, jeśli jesteśmy gotowi przyjąć, że jako Szczegóły realizacji. Ale najpierw niech aktualizacji danych struktury, zanim to zrobimy. Bo ja nie podoba się pomysł wszystko ludzie przesunięcie w tej linii. To nic wielkiego, jeśli David robi to z jeden krok, ale znowu, że z powrotem do kiedy miałem osiem wolontariuszy etap i zrobiliśmy jak wstawienia sort, gdzie mieliśmy zacząć przenoszenie wszystkich wokół. To ma drogie, prawda? To mnie lizać o Big O n, big O n kwadratu ponownie. To nie jest uczucie jak idealny wynik. Więc po prostu zaktualizować tego. Tak więc wielkość kolejki nie jest już 2. To teraz tylko 1. Ale mogę teraz zaktualizować coś I nie aktualizować przed, początku listy. Mogę tylko powiedzieć, jest to, że miejsce 1? Więc teraz mamy wartość śmieci tutaj, wartość śmieci tutaj, a David w Środek ten śmieci. Jednak struktura danych jest nadal w stanie nienaruszonym. I rzeczywiście, nie trzeba nawet zmiany były numer Jake'a 9, bo kogo to obchodzi. Mam wystarczająco dużo informacji, obecnie w rozmiar, że wiem, że jest jedna osoba w ta kolejka. I wiem, że ta osoba jest na miejscu 1, nie 0. Nie liczę. Więc 1, jak również. Tak więc struktura danych jest nadal OK. Cóż, to, co dzieje się dalej? Miejmy enqueue - jak masz na imię? PUBLICZNOŚCI: Callen. DAVID MALAN: Callen. Miejmy enqueue się Callen i 22 jest teraz w kolejce. Więc teraz to, co musi się zmienić tutaj? Przód nie będzie zmienić, oczywiście. Rozmiar się nie zmieni się 2 ponownie. I 22 kończy się tutaj, 9 jest nadal obecny, ale skutecznie wartość śmieci teraz. To jest po prostu pozostałością przeszłości Jake. Więc teraz, co się stanie, jeśli I usunie z niej David? Jedna ostatnia operacja, Dequeue David. Możemy przesunąć, ale proponuję Chodźmy zrobić jak mało pracy, jak to możliwe. Teraz moja struktura danych idzie kopię wielkości od 2 do 1. Ale na początek kolejki teraz staje się 2. I nie ma potrzeby zmiany tych numerów jeszcze, bo są tylko wartości na śmieci. Ale teraz co się dzieje? Załóżmy, że enqueue siebie, 26? Czuję się jak ja należę tutaj. Jestem więc jest skolejkowany. Więc niby należą tutaj. I nawet jeśli nie bardzo Doceniam to wizualnie na scenie, bo mamy dużo miejsca, że ​​powinienem nie stać tutaj, dlaczego? PUBLICZNOŚCI: Jesteś poza granicami. DAVID MALAN: Racja. Jestem poza granicami. Mam indeksowane poza Granice tej tablicy. I naprawdę powinno być w jednym z trzy możliwe lokalizacje. Teraz, gdzie jest najbardziej naturalnym iść? I proponuję dźwignią tydzień jedna sztuczka. Operator mod, skuteczność. Bo jestem technicznie stoi na miejsce 3, ale ja 3 mod zdolności, tak 3, znak procent, 3 - pojemność to 3. Co to jest? Co jest w pozostałej, podzielić 3 przez 3? 0. Tak, że stawia mnie były Jake był, która jest w rzeczywistości dobra. Więc teraz realizacja z tego, co się dzieje w być trochę ból głowy. To naprawdę tylko jedna linia z bólem głowy, z kodem. Ale przynajmniej teraz nie śmieci wartość tutaj, ale jest dwa uzasadnione ints tutaj. I twierdzą, że teraz zrobiliśmy dokładnie to, co musimy zrobić, tak długo, jak długo możemy zmienić to, co Jake wartość miała być 26. Mamy już wystarczająco dużo informacji, nadal w celu zachowania integralności tej struktury danych. Wciąż jesteśmy rodzajem pecha, kiedy Aby wstawić sumie cztery lub więcej elementy, ale mogę przynajmniej zrobić całkiem efektywne wykorzystanie tej stałej Czas, w rzeczywistości. I nie trzeba się martwić o przesunięcie wszyscy, jak pochylenia Dawida było. Wszelkie pytania na stosy, czy ta kolejka? PUBLICZNOŚCI: Czy powodem trzeba rozmiar więc wiesz gdzie na osobę? DAVID MALAN: Dokładnie. I trzeba znać rozmiar tablicy bo muszę wiedzieć dokładnie, jak wiele z tych wartości są zgodne z prawem, i tak, że mogę dowiedzieć się, gdzie umieścić następna osoba. Dokładnie. Rozmiar jest - faktycznie, nie aktualizuje tego jeszcze. I dodaje się na 26. Rozmiar jest teraz, a nie 1, ale 2. Więc teraz to naprawdę pomaga mi znaleźć na początku listy, która nie jest 0, nie 1, 2, lecz jest. Z przodu na liście to rzeczywiście numer 22. Bo przyszedł pierwszy, więc powinien on być dopuszczone do sklepu, zanim mnie choć wizualnie stoję bliżej do sklepu. Wszystko w porządku? Brawa dla tych facetów i damy je stamtąd. [APPLAUSE] DAVID MALAN: mogłem pozwolić trzymać tacę. Mogliśmy zobaczyć, co się stanie, jeśli chcesz, ale może nie. Dobrze. Więc co teraz nam pozostaje? Cóż, pozwól mi zaproponować, że nie Kilka innych struktur danych mogliśmy rozpocząć dodawanie do naszego zestawu narzędzi, które rzeczywiście być bardzo, bardzo istotne, ponieważ zagłębimy się rzeczy internetowej. Które znów ma jakieś połączenia z drzew w postaci coś, co nazywa DOM, dokument model obiektu. Ale zobaczymy więcej że przed długi. Pozwól mi zaproponować definicyjnie że zadzwoń drzewa teraz, co można wiedzieć, jak więcej drzewie rodzinnym, gdzie można posiada przodka w jakiś korzenie drzewa. Patriarchalny lub macierz w górze drzewa. Bez ich małżonków, w tym przypadku. Ale teraz mamy to, co my nazywamy dzieci, które są węzły, które wiszą od lewej dziecka lub dziecka prawej, strzałki, jak przedstawione tutaj. Innymi słowy, w strukturze danych drzewa w komputerze, drzewo ma wartość zero lub więcej węzłów. Jeżeli ma ona co najmniej jeden węzeł to się nazywa główny. To rzeczy, które wizualnie zwracamy na szczycie. I że węzeł, jak każdy inny węzeł, może mieć zero, jeden lub dwa, lub trzy, lub jednak wiele dzieci Struktura danych obsługuje. W tym przypadku, główny, przechowywania wartość jeden, ma dwoje dzieci, 2 i 3, więc ogólnie nazywamy 2 lewy dziecko i 3 prawa dziecka. A potem, kiedy zabieram się do 5, 6, i 7, 6 można nazwać średnim dzieckiem. Jeśli masz czworo dzieci, robi się mylące. Więc przestać używać tego rodzaju od skrótu ustnie. Ale to naprawdę tylko drzewo genealogiczne. A liście są tu węzłów, które sami nie mają dzieci. Wiszą off dno drzewo. Więc jak możemy zaimplementować drzewo, które ma tylko dwa dzieci maksymalnie? Nazwijmy to drzewo binarne. Bi ponownie, co oznacza, dwa, w tym przypadek, jak z binarnym. I tak może mieć zero, jeden, lub dwoje dzieci maksymalnie. Ja proponuję wdrażamy węzeł do tej struktury z int n, a następnie dwa wskaźniki, jeden o nazwie w lewo, jeden nazywa się prawo. Ale to są tylko ładne arbitralne konwencje. I co miło teraz, zwłaszcza jeśli niby walczyli koncepcyjnie z rekurencji, albo myśli, że to nie było naprawdę rozwiązanie do niczego, zwłaszcza jeśli można zabraknie pamięci. Teraz, gdy mówimy o danych Struktury i algorytmy, które pozwalają nam przemierzać i manipulować nimi, Okazuje się, że rekurencja wraca znacznie bardziej atrakcyjne jeśli nie piękny sposób. Więc proponuję, jest realizacja z funkcji wyszukiwania. Biorąc pod uwagę dwa wejścia - więc myślę o tym jako czarna skrzynka. Biorąc pod uwagę dwa wejścia, n, int i wskaźnik do drzewa, wskaźnik do węzeł, czy naprawdę korzeń drzewa, I Twierdzenie, że funkcja ta może powrócić prawda czy fałsz, że wartość n jest w środku tego drzewa. Co jest w środku tej czarnej skrzynki? Cóż, cztery oddziały. Najpierw po prostu sprawdza. Jeśli drzewo jest null, po prostu return false. Jeśli nie ma węzła, nie ma n, nie ma wiele, po prostu zwraca wartość false. Jeśli jednak, n, wartość szukasz na, jest mniej niż drzewa strzałki n, a żeby było jasne, co to znaczy, kiedy Piszę drzewo, a następnie strzałki zapis, n? Dokładnie. Oznacza to, że Dereferencjuj wskaźnik nazywa drzewo. Idź tam, a następnie dostać się do środka tego węzeł i uzyskać jego pole o nazwie n. , A następnie porównać rzeczywiste n, który był przeszedł do wyszukiwania przeciw nim. Więc jeśli n jest mniejsza od wartości n w węźle drzewa sam, dobrze, co to znaczy? Oznacza to, że nic na pierwszy rzut oka. Prawda? Podobnie jak wtedy, gdy masz tablicę wartości, które warto stosować binarne sprawdzić jako forma podziału i podbić. Ale co z założenia nie musimy mieć dla wyszukiwania binarnego do pracy na wszystkich w książce telefonicznej i Wcześniejsze przykłady? Jak być sortowane. Warto więc uściślić definicję drzewa tu nie być tylko drzewa, które mogą mieć dowolną liczbę dzieci. Nie tylko drzewo binarne, które mogą mieć 0, 1 lub 2 maksymalnie. Ale jako binarne drzewo wyszukiwania lub BST, który jest tylko fantazyjny sposób na powiedzenie drzewo binarne, takie, że każdy węzeł-tych lewej dziecko, jeśli jest obecny, jest poniżej węzła. I każdy węzeł ma rację dziecko, Jeśli występuje, jest większa od samego węzła. Więc innymi słowy, jeśli było wyciągnąć z drzewa, wszystkie numery są starannie wyważone, jak to tak, że jeśli masz 55 jako główny, 33 może pójść po jego lewej stronie, ponieważ jest to mniej niż 55. 77 może iść do swojego prawa, ponieważ jest większa niż 55. Teraz jednak zauważyć, tę samą definicję, jest rekurencyjna definicja ustnie, ma zastosowanie do 33. 33 w lewo dziecko musi być mniejsza niż to, i prawa dziecka 33-tych, 44, musi być większe niż to. Więc to jest drzewo binarne wyszukiwanie i Proponuję, używając trochę rekurencja, możemy teraz znaleźć n. Tak więc, jeśli n jest mniejsza od wartości n, który jest bieżący węzeł, zamierzam iść dalej i punt, że tak powiem, i po prostu zwrotu tego, co odpowiedź jest szukając n na lewa dziecko drzewa. Wskazówka ponownie, ta funkcja po prostu oczekuje węzła STAR wskaźnik do węzła. Więc pewnie po prostu może zrobić drzewo strzałka w lewo, co doprowadzi mnie do innego węzła. Ale to, co jest, że węzeł? Cóż, według tej deklaracji, w lewo jest tylko wskaźnik, tak, że tylko Oznacza to, ja przechodząc do funkcji wyszukiwania inny wskaźnik, a mianowicie który reprezentuje Moja lewa dziecka drzewo. Tak więc, w tym przypadku, wskaźnik 33, jeśli to jest nasz wkład próbka Tymczasem, jeśli n jest większe niż wartość n na bieżący węzeł w drzewie, to ja jestem zamiar iść do przodu i punt w innych kierunek i po prostu powiedzieć, nie wiem wiem, czy to n wartość jest w drzewie, ale wiem, że jeśli tak jest, to w dół my Prawo oddziału, że tak powiem. Więc pozwól mi zadzwonić rekursywnie sprawdzić, przechodząc n ponownie, ale przechodząc w wskaźnik do mojej prawej dziecka. Innymi słowy, jeśli jestem obecnie w 55 i szukam 99, wiem, że 99 jest większa niż 55, więc jak wyrwałem książki telefonicznej tygodnie temu, a my poszedł w prawo, podobnie jesteśmy zamiar iść tutaj. A ja nie wiem, czy to jest w mojej prawej stronie dziecko, i to nie jest, 77 ma, ale Wiem, że to w tym kierunku. Więc wzywam wyszukiwania na prawym dzieckiem 77, i niech się z postać wyszukiwania tam, jeśli 99 w tym arbitralne Przykładem jest faktycznie istnieje. Else, co jest ostateczna sprawa? Jeśli drzewo jest null to jedna sprawa. Jeśli n jest mniejsza niż obecna węzła wartość jest inna sprawa. Jeśli n jest większe niż prąd wartość węzła jest trzeci przypadek. Co czwarty i ostatni przypadek? Myślę, że jesteśmy z przypadków, prawda? To musi być to, że n jest bieżący węzeł, że jestem na. Jeśli więc szukam 55 w tym momencie w historii, że oddział drzewo wróci prawda. Więc co ciekawe jest to, że my rzeczywiście, w przeciwieństwie tydzień przeszłości, my niby o dwie podstawowe sprawy. A oni nie mają do Wszystkie się na szczycie. Top jest wariant podstawowy, ponieważ jeśli Drzewo jest null, nie ma nic do zrobienia. Wystarczy wrócić zakodowanego wartość false. Oddział dno jest rodzaj domyślnie, przy czym jeśli mamy sprawdzone null, sprawdziliśmy, czy powinien on być lewo, ale nie powinny być, mamy sprawdzić, czy powinno być w porządku, ale to Nie powinny być wyraźnie, że musi być tu, gdzie jesteśmy. To wariant podstawowy. Więc nie dwa przypadki rekurencyjne umieszczona jest w środku. Ale mogę napisać To, w dowolnej kolejności. Pomyślałem, że to niby się czymś naturalnym najpierw sprawdzić ewentualnego błędu, następnie sprawdzić w lewo, a następnie sprawdzić w prawo, a następnie Zakładam, że jesteś w węźle jesteś rzeczywiście szukają. Więc dlaczego może to być przydatne? Okazuje się - i pozwól mi przejść do teaser tutaj, że jest w internecie. Zamierzamy rozpocząć korzystanie nie języka programowania na początku, ale język znaczników. Język znaczników jest jeden, który jest w duchu podobnym do programowania język, ale to nie daje zdolność do wyrażania siebie logicznie. To tylko daje możliwość wyrazić siebie strukturalnie. Gdzie chcesz umieścić coś na stronie, strona internetowa? Jaki kolor chcesz to zrobić? Jaki rozmiar czcionki chcesz to zrobić? Jakie słowa czy rzeczywiście chcesz na stronie internetowej? Więc to jest język znaczników. Ale my bardzo szybko wprowadzić JavaScript, który jest pełnoprawnym język programowania. Bardzo podobny z wyglądu składniowo do C, ale to jedne ładny, mocniejszy, bardziej przyjaznych dla użytkownika funkcji. I jeden z frustracji na to punkt w semestrze jest to, że my będziemy szybko wdrożyć Speller w znacznie mniej linii kodu przy użyciu innych językach niż C sobie pozwala, ale za przyczyną tych niedługo zrozumieć. To będzie pierwsza taka strona. To będzie całkowicie rozczarowująca, Pierwszy z nich robimy. Będzie to po prostu powiedzieć, hello world. Ale jeśli nigdy nie widziałem go Zanim to jest HTML HyperText Markup Language. Jeśli pójdziesz do pewnej opcji menu w Najbardziej dowolnej przeglądarki, na dowolnej stronie internetowej na internet, można zobaczyć, HTML że niektórzy ludzie napisali do tworzenia tej strony. I to chyba nie wygląda tak krótkie lub jako czysty jak ten. Ale będzie to zgodne z wzorcem z nich otwarte wsporniki i tnie i Litery i ewentualnie numery. Myślałam, że dam wam teaser z tego, co będzie można zrobić po zrobieniu CS50. Pozwólcie mi odejść do cs.harvard.edu / rob, strona główna nasze własne Roba Bowdena. Zrobił to za nas. Tak więc wkrótce będziesz w stanie tego zrobić. A także, co usłyszałeś rano - co słyszałeś to rano - [CHOMIK MUSIC DANCE] - Przychodzą w stanie dokonać tego. To nas czeka w środę. Będziemy zobaczenia. [CHOMIK MUSIC DANCE] DAVID MALAN: Na następnym CS50 -