1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID MALAN: W porządku. 3 00:00:12,250 --> 00:00:13,860 Witamy z powrotem do CS50. 4 00:00:13,860 --> 00:00:16,190 To jest początek tygodnia 8. 5 00:00:16,190 --> 00:00:21,320 I przypominają, że zestaw problemem 5 zakończony z odrobiną wyzwanie. 6 00:00:21,320 --> 00:00:25,210 Więc zakładając, że odzyskane wszystkie swoje Fellows nauczania w fotografie i CA 7 00:00:25,210 --> 00:00:30,480 w pliku card.raw, masz prawo do teraz znaleźć wszystkie z tych osób, a 8 00:00:30,480 --> 00:00:34,510 jeden szczęśliwy zwycięzca będzie chodzić do domu z jednym z tych rzeczy, ruch skok 9 00:00:34,510 --> 00:00:37,450 Urządzenie, które można używać do finału projekty, na przykład. 10 00:00:37,450 --> 00:00:39,860 >> To, co roku, prowadzi do Trochę creepiness. 11 00:00:39,860 --> 00:00:43,480 A więc to, co myślałem, że robię to akcja z tobą kilka notatek, które mają 12 00:00:43,480 --> 00:00:47,370 poszedł w tę iz powrotem nad lista pracowników późno. 13 00:00:47,370 --> 00:00:51,110 Na przykład, tylko ostatniej nocy, cytatem Unquote, ze jeden z pracowników 14 00:00:51,110 --> 00:00:55,000 członków, "miałem tylko pukanie studentów do moich drzwi, aby zrobić zdjęcie ze mną. 15 00:00:55,000 --> 00:00:59,020 Stalker, mówię wam. "Zaczęło się dość opisowe, a następnie przenieśliśmy 16 00:00:59,020 --> 00:01:02,830 na, godzinę później: "Miałem Student czeka na mnie po sekcji 17 00:01:02,830 --> 00:01:06,080 i miał wszystkie nasze nazwiska i zdjęcia na niektórych arkuszach papieru. "Wszystko w porządku. 18 00:01:06,080 --> 00:01:09,230 Tak zorganizowany, ale nie wszystko, co przerażający jeszcze. 19 00:01:09,230 --> 00:01:12,520 >> Następnie, "I nie było w mieście w ten weekend, i kiedy wróciłem, nie było jednym z 20 00:01:12,520 --> 00:01:12,630 mój 21 00:01:12,630 --> 00:01:16,740 sypialnia. "[śmiech] 22 00:01:16,740 --> 00:01:20,410 DAVID MALAN: Następny cytat z personelem członkiem, "uczeń przyszedł do mojego domu w 23 00:01:20,410 --> 00:01:25,330 Somerville o 4 rano to rano. "Next Pracownicy, "Mam do mojego hotelu w San 24 00:01:25,330 --> 00:01:30,016 Francisco i czeka na studentów mnie w holu z trzech lustrzanek. " 25 00:01:30,016 --> 00:01:31,510 Typ aparatu. 26 00:01:31,510 --> 00:01:34,980 "Nie jestem nawet na pracowników w tym semestrze, ale uczeń włamał się do mojego domu, to 27 00:01:34,980 --> 00:01:40,480 rano i nagrał całość ze szkłem Google. "I wtedy wreszcie, 28 00:01:40,480 --> 00:01:43,650 "Co najmniej 12 osób, były chętnie czekając na mnie, kiedy wyszedłem z 29 00:01:43,650 --> 00:01:44,800 limo, a następnie I 30 00:01:44,800 --> 00:01:46,970 obudziłem się. "Wszystko w porządku. 31 00:01:46,970 --> 00:01:57,690 Więc między zdjęciami, jak możesz przypominam, to ten facet tutaj, z kim 32 00:01:57,690 --> 00:02:01,850 może wiedzieć, jak Milo banan, który żyje z Lauren Carvalho, nasza głowa 33 00:02:01,850 --> 00:02:02,905 nauczania Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, chodź tutaj chłopcze. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Pamiętaj, on sobie Google szyby, więc pokażemy wszystko po. 38 00:02:12,230 --> 00:02:16,190 Więc to jest Milo jeśli chcesz zrobić zdjęcie z nim później. 39 00:02:16,190 --> 00:02:18,240 Jeśli chcesz, aby zwrócić uwagę na publiczność tam. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 To dobry materiał. 42 00:02:20,200 --> 00:02:22,556 Cóż, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, nie rób tego. 44 00:02:23,941 --> 00:02:29,020 >> [Śmiech] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Więc słowa następnie na co przede mną, bo jak zaczniemy przejścia, 47 00:02:34,550 --> 00:02:38,410 w tym tygodniu specjalnie, z C w środowiska wiersza polecenia do PHP i 48 00:02:38,410 --> 00:02:42,720 JavaScript i SQL i HTML i CSS w web-based środowiska, będziemy 49 00:02:42,720 --> 00:02:44,490 wyposażanie Ci wszystko więcej wiedzy na 50 00:02:44,490 --> 00:02:46,010 potencjalnych ostatecznych projektów. 51 00:02:46,010 --> 00:02:49,240 Pod tym celu, kurs ma Tradycja organizowania seminariów, które 52 00:02:49,240 --> 00:02:50,950 są na stycznych tematów w toku. 53 00:02:50,950 --> 00:02:54,330 Bardzo podobne do programowania i rozwój aplikacji i tak dalej, ale 54 00:02:54,330 --> 00:02:57,010 niekoniecznie zbadane przez Kurs własny program nauczania. 55 00:02:57,010 --> 00:03:00,250 >> Więc jeśli może być zainteresowany w jednym lub więcej z tegorocznych seminariów, 56 00:03:00,250 --> 00:03:02,530 Zarejestruj się w cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Są starsze seminaria w cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 A na zaplanowany tak daleko w tym roku są niesamowite Web Apps z Ruby on 59 00:03:10,620 --> 00:03:13,580 Szyny, która jest alternatywnym język PHP. 60 00:03:13,580 --> 00:03:14,900 Computational Linguistics. 61 00:03:14,900 --> 00:03:18,710 Wprowadzenie do IO, który jest Platforma, która jest używana dla iPhone i 62 00:03:18,710 --> 00:03:19,850 iPad rozwój. 63 00:03:19,850 --> 00:03:22,890 JavaScript dla Web Apps, omówimy , ale w tym seminarium, to pójdziesz 64 00:03:22,890 --> 00:03:24,070 bardziej szczegółowo. 65 00:03:24,070 --> 00:03:27,390 >> Leap Motion, więc będziemy rzeczywiście niektóre naszych przyjaciół z Ruchu Leap, 66 00:03:27,390 --> 00:03:29,160 Sama firma, dołącz do nas. 67 00:03:29,160 --> 00:03:31,800 Jutro, w rzeczywistości, w celu zapewnienia praktyczne seminarium, jeśli 68 00:03:31,800 --> 00:03:33,320 interesujące dla ciebie. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, alternatywna technika Nie używając JavaScript w przeglądarce, 70 00:03:38,770 --> 00:03:39,970 ale na serwerze. 71 00:03:39,970 --> 00:03:42,110 Node.js, który jest bardzo w tym duchu, jak również. 72 00:03:42,110 --> 00:03:43,650 Elegancki design Android. 73 00:03:43,650 --> 00:03:46,990 Android jest bardzo popularną alternatywą dla iOS i Windows Phone 74 00:03:46,990 --> 00:03:48,790 i inne platformy mobilne. 75 00:03:48,790 --> 00:03:51,180 I Bezpieczeństwa Web aktywnej obrony. 76 00:03:51,180 --> 00:03:54,590 >> Faktycznie więc, jeśli chcesz do zaangażowania się w to, pozwól mi 77 00:03:54,590 --> 00:03:55,840 zanotuj to. 78 00:03:55,840 --> 00:03:57,790 Jesteśmy bardzo szczęśliwi, że nasi przyjaciele w Skoku 79 00:03:57,790 --> 00:03:59,140 Projekt, który jest startup - 80 00:03:59,140 --> 00:04:01,300 urządzenie to tak naprawdę przyszedł się kilka miesięcy temu - 81 00:04:01,300 --> 00:04:05,960 łaskawie wpłat 30 takich urządzeń w klasie, jak wielu studentów, jeśli 82 00:04:05,960 --> 00:04:08,670 chcesz pożyczyć sprzęt do końca semestru i używać go do 83 00:04:08,670 --> 00:04:10,390 rzeczywisty projekt końcowy. 84 00:04:10,390 --> 00:04:11,890 Wspierają one wiele języków. 85 00:04:11,890 --> 00:04:16,040 Żaden z nich C, żaden z nich PHP, tak realizacji jednego lub więcej z tych seminariów 86 00:04:16,040 --> 00:04:16,899 mogą okazać się interesujące. 87 00:04:16,899 --> 00:04:19,730 I wszystkie z nich będą filmowane w Wydarzenie, które nie są w stanie 88 00:04:19,730 --> 00:04:21,380 uczestniczyć osobiście. 89 00:04:21,380 --> 00:04:25,000 Harmonogram zostanie ogłoszony przez napisz jak ugruntować pokoje. 90 00:04:25,000 --> 00:04:28,460 >> I wreszcie, jeśli pójdziesz do projects.cs.50.net, to jest strona internetowa 91 00:04:28,460 --> 00:04:31,450 podtrzymujemy każdego roku, że zapraszamy ludzie z tej wspólnoty, wydział, 92 00:04:31,450 --> 00:04:36,420 wydziały, personel i oba na zewnątrz do CS50 93 00:04:36,420 --> 00:04:37,730 zaproponować pomysły na projekty. 94 00:04:37,730 --> 00:04:39,050 Co to dla grup studenckich. 95 00:04:39,050 --> 00:04:40,600 Co to do działów. 96 00:04:40,600 --> 00:04:43,990 Więc należy skręcić tam, jeśli masz problemy z niepewności co do tego, co 97 00:04:43,990 --> 00:04:46,700 będzie się chciał zająć. 98 00:04:46,700 --> 00:04:51,760 >> Więc ostatni raz, kiedy wprowadzono zapewne bardziej złożone struktury danych, niż bym 99 00:04:51,760 --> 00:04:53,300 widać na tydzień ostatnich. 100 00:04:53,300 --> 00:04:56,550 My byliśmy za pomocą tablic dość szczęśliwie jako przydatne 101 00:04:56,550 --> 00:04:58,160 uproszczona struktura danych. 102 00:04:58,160 --> 00:05:00,570 Następnie wprowadziliśmy te, które oczywiście są związane list. 103 00:05:00,570 --> 00:05:05,470 I to, co było jedną z motywacji do wprowadzenie tej struktury danych? 104 00:05:05,470 --> 00:05:06,930 Tak? 105 00:05:06,930 --> 00:05:07,250 Co to jest? 106 00:05:07,250 --> 00:05:08,080 >> PUBLICZNOŚCI: Dynamiczny rozmiar. 107 00:05:08,080 --> 00:05:09,040 >> DAVID MALAN: Dynamiczny rozmiar. 108 00:05:09,040 --> 00:05:11,890 Tak więc podczas gdy w tablicy, trzeba znać jej rozmiar z wyprzedzeniem 109 00:05:11,890 --> 00:05:12,740 można przeznaczyć go. 110 00:05:12,740 --> 00:05:14,380 W połączonej listy, nie wiesz wiedzieć, że. 111 00:05:14,380 --> 00:05:17,610 Można po prostu malloc, lub bardziej ogólnie, przeznaczyć dodatkowe 112 00:05:17,610 --> 00:05:20,720 węzeł, by tak rzec, kiedy tylko Aby wstawić więcej danych. 113 00:05:20,720 --> 00:05:22,670 A węzeł ma góry określone znaczenie. 114 00:05:22,670 --> 00:05:25,580 To tylko ogólny termin opisujący jakiś pojemnik, że jesteśmy 115 00:05:25,580 --> 00:05:29,610 używając w naszej struktury danych do przechowywania jakiś element zainteresowania, które w tym 116 00:05:29,610 --> 00:05:31,750 przypadku stało się całkowite. 117 00:05:31,750 --> 00:05:33,160 >> Ale zawsze kompromis. 118 00:05:33,160 --> 00:05:38,070 Więc mamy dynamiczne rozmiary danych struktury, ale jaką cenę płacimy? 119 00:05:38,070 --> 00:05:40,040 Co jest minusem linked list? 120 00:05:40,040 --> 00:05:41,006 Tak? 121 00:05:41,006 --> 00:05:41,980 >> PUBLICZNOŚCI: wymaga więcej pamięci. 122 00:05:41,980 --> 00:05:44,240 >> DAVID MALAN: To wymaga więcej pamięci, jak dokładnie? 123 00:05:44,240 --> 00:05:46,440 >> PUBLICZNOŚCI: [niesłyszalne]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID MALAN: Dokładnie. 125 00:05:47,050 --> 00:05:50,460 Więc teraz mamy wskaźniki podejmowania dodatkowa pamięć, że wcześniej 126 00:05:50,460 --> 00:05:53,040 nie potrzebne, ponieważ zaletą z tablicy, oczywiście, jest to, że 127 00:05:53,040 --> 00:05:54,860 wszystko jest ciągły, z powrotem z powrotem do tyłu, które 128 00:05:54,860 --> 00:05:56,380 daje swobodny dostęp. 129 00:05:56,380 --> 00:06:00,710 Bo tylko za pomocą uchwytu kwadratowego wskaźnik oznaczenie lub bardziej technicznie 130 00:06:00,710 --> 00:06:03,580 arytmetyka, bardzo prosty dodatek, można uzyskać dostęp do wszelkich 131 00:06:03,580 --> 00:06:05,700 elementów w czasie stałym. 132 00:06:05,700 --> 00:06:08,975 A w rzeczywistości, to jest rodzaj sugerując inna cena, którą płacimy z 133 00:06:08,975 --> 00:06:09,760 połączonej listy. 134 00:06:09,760 --> 00:06:13,890 >> Co się dzieje z systemem czasu coś jak wyszukiwanie, jeśli chcę 135 00:06:13,890 --> 00:06:17,270 znaleźć jakąś wartość i wewnątrz z połączonej listy? 136 00:06:17,270 --> 00:06:20,290 Co oznacza mój czas pracy się? 137 00:06:20,290 --> 00:06:21,560 Big O n. 138 00:06:21,560 --> 00:06:24,060 Jeśli jest klasyfikowane do? 139 00:06:24,060 --> 00:06:25,440 Co zrobić, jeśli struktura danych jest sortowane? 140 00:06:25,440 --> 00:06:28,640 Czy mogę to zrobić lepiej niż duże O n do wyszukiwania? 141 00:06:28,640 --> 00:06:31,700 Nie, gdyż w najgorszym przypadku może bardzo dobrze posortowane, ale liczba 142 00:06:31,700 --> 00:06:32,950 szukasz może być duży. 143 00:06:32,950 --> 00:06:35,370 Może to być liczba 100, która może zdarzyć się wszystko 144 00:06:35,370 --> 00:06:36,410 sposób na końcu. 145 00:06:36,410 --> 00:06:39,950 A ponieważ można tylko przejść linked list w tej realizacji przez 146 00:06:39,950 --> 00:06:42,690 sposób jego pierwszym węźle, jesteś jeszcze trochę pecha. 147 00:06:42,690 --> 00:06:47,450 Musisz przechodzić całość od początku do końca, aby wybrać 148 00:06:47,450 --> 00:06:49,150 że duża wartość jak 100. 149 00:06:49,150 --> 00:06:51,350 Lub w celu określenia, czy jest to nawet nie istnieje. 150 00:06:51,350 --> 00:06:55,960 >> Nie możemy więc zrobić to, co w ciągu danych, algorytm struktura, która wygląda tak? 151 00:06:55,960 --> 00:06:59,460 Nie możemy zrobić wyszukiwanie binarne, ponieważ Wyszukiwanie binarne wymaga, że ​​mamy 152 00:06:59,460 --> 00:07:00,740 random access. 153 00:07:00,740 --> 00:07:04,500 Moglibyśmy po prostu skakać z miejsca na miejsce Położenie bez konieczności wykonywania 154 00:07:04,500 --> 00:07:07,080 te bułki tartej w formie wszystkich tych wskaźników. 155 00:07:07,080 --> 00:07:08,300 >> Teraz, jak się nam wdrożyć to? 156 00:07:08,300 --> 00:07:12,830 Cóż, jeśli pójdziemy do ekranu tutaj, jeśli możemy szybko reimplement te dane 157 00:07:12,830 --> 00:07:13,440 struktura - 158 00:07:13,440 --> 00:07:15,670 mój charakter pisma nie wszystko, że tu świetnie, ale spróbujemy. 159 00:07:15,670 --> 00:07:22,030 Więc typedef struct, a co ja chcesz się połączyć, to coś tutaj? 160 00:07:22,030 --> 00:07:22,960 Node. 161 00:07:22,960 --> 00:07:24,580 Więc ja się nas zaczęło. 162 00:07:24,580 --> 00:07:27,860 A teraz, co musi być wewnątrz Struktura danych na które pojedynczo 163 00:07:27,860 --> 00:07:28,430 powiązana listę? 164 00:07:28,430 --> 00:07:29,950 Ile pól? 165 00:07:29,950 --> 00:07:30,450 >> Więc dwa. 166 00:07:30,450 --> 00:07:31,570 Jednym z nich jest całkiem proste. 167 00:07:31,570 --> 00:07:33,050 Więc int n. 168 00:07:33,050 --> 00:07:35,930 I moglibyśmy nazwać n co chcemy, ale powinno być int, czy jesteśmy 169 00:07:35,930 --> 00:07:37,660 wdrożenie połączonej listy do liczb całkowitych. 170 00:07:37,660 --> 00:07:41,920 A teraz to, co robi drugi Pole musi być? 171 00:07:41,920 --> 00:07:43,460 Struct node *. 172 00:07:43,460 --> 00:07:50,570 Więc jeśli zrobić węzeł struct *, a potem można nazwać również, co chcę, 173 00:07:50,570 --> 00:07:53,510 ale żeby była jasność Zadzwonię to następny, jak robiliśmy. 174 00:07:53,510 --> 00:07:55,270 I wtedy zamknę nawiasy klamrowe. 175 00:07:55,270 --> 00:08:00,700 >> A teraz, jak ostatnim razem, I umieścić węzeł tutaj. 176 00:08:00,700 --> 00:08:03,830 Ale jeśli mam deklarując to jako węzeł, dlaczego jest tak, że przeszkadza 177 00:08:03,830 --> 00:08:07,320 verbose tutaj deklarowania struct node * next, w przeciwieństwie 178 00:08:07,320 --> 00:08:09,210 do zaledwie węzła * następnego? 179 00:08:09,210 --> 00:08:09,904 Tak? 180 00:08:09,904 --> 00:08:12,810 >> PUBLICZNOŚCI: [niesłyszalne]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID MALAN: Dokładnie. 182 00:08:14,050 --> 00:08:14,530 Dokładnie. 183 00:08:14,530 --> 00:08:18,320 Ponieważ C naprawdę zabierze cię dosłownie i widzi tylko definicji węzła 184 00:08:18,320 --> 00:08:21,230 droga w dół tutaj, nie można odnoszą się do niego tutaj. 185 00:08:21,230 --> 00:08:24,760 Mamy więc tego rodzaju prewencyjne deklaracja tutaj, co jest wprawdzie 186 00:08:24,760 --> 00:08:25,390 bardziej gadatliwy. 187 00:08:25,390 --> 00:08:27,810 Struct węzła, to znaczy możemy uzyskać do niego dostęp 188 00:08:27,810 --> 00:08:29,760 Wnętrze struktury danych. 189 00:08:29,760 --> 00:08:33,370 >> I jak na bok, bo to jest staje się trochę bardziej subiektywne teraz, 190 00:08:33,370 --> 00:08:36,230 gwiazda może technicznie iść tutaj, Można go tutaj, może 191 00:08:36,230 --> 00:08:37,179 nawet go w środku. 192 00:08:37,179 --> 00:08:39,890 Musimy przyjąć, w stylu przewodnika Oczywiście, konwencja oddanie 193 00:08:39,890 --> 00:08:42,299 gwiazdki obok danych typu, które w tym przypadku, 194 00:08:42,299 --> 00:08:43,460 będzie węzeł struct. 195 00:08:43,460 --> 00:08:46,620 Ale sprawę w wielu podręcznikach i Internetowe odniesienia, to może rzeczywiście 196 00:08:46,620 --> 00:08:48,450 zobaczyć po drugiej stronie. 197 00:08:48,450 --> 00:08:52,200 Ale tylko uświadomić sobie, że jak będzie w rzeczywistości pracy i należy po prostu być 198 00:08:52,200 --> 00:08:52,970 spójne. 199 00:08:52,970 --> 00:08:53,580 >> Dobrze. 200 00:08:53,580 --> 00:08:55,630 Więc to była nasza deklaracja węzła struct. 201 00:08:55,630 --> 00:08:59,430 Ale potem zaczęliśmy robić więcej wyrafinowane rzeczy. 202 00:08:59,430 --> 00:09:03,410 Na przykład, zdecydowaliśmy się na wprowadzenie coś jak tabeli mieszania. 203 00:09:03,410 --> 00:09:08,160 Więc tutaj jest hash table n wielkości, indeksowane od 0 w lewym górnym rogu do n 204 00:09:08,160 --> 00:09:09,690 minus 1 na dole po lewej stronie. 205 00:09:09,690 --> 00:09:11,640 To może być hash Stół do niczego. 206 00:09:11,640 --> 00:09:15,340 Ale to, co wiele rzeczy nie mówimy o użyciu tabeli mieszania dla? 207 00:09:15,340 --> 00:09:18,370 Przechowywanie co? 208 00:09:18,370 --> 00:09:18,800 >> Nazwy. 209 00:09:18,800 --> 00:09:20,870 Moglibyśmy zrobić nazwiska jak my ostatnio. 210 00:09:20,870 --> 00:09:22,200 I rzeczywiście, można przechowywać wszystko. 211 00:09:22,200 --> 00:09:24,640 I zobaczymy, to jeszcze raz w PHP i JavaScript. 212 00:09:24,640 --> 00:09:28,550 Hash table jest ładny sort of Swiss Scyzoryk, który pozwala na przechowywanie 213 00:09:28,550 --> 00:09:33,690 dość dużo, co chcesz w środku to przez skojarzenie klucze z wartościami. 214 00:09:33,690 --> 00:09:34,770 Klawisze z wartościami. 215 00:09:34,770 --> 00:09:37,800 >> Teraz w tym prostym przypadku, nasz Klawisze są tylko liczby. 216 00:09:37,800 --> 00:09:40,380 Jesteśmy realizacji hash Stół w postaci tablicy. 217 00:09:40,380 --> 00:09:43,500 I tak klawisze są 0, 1, 2, i tak dalej. 218 00:09:43,500 --> 00:09:47,200 A więc my, jako ludzie, postanowił ostatnio tygodniu, że wiesz co, jeśli jesteśmy 219 00:09:47,200 --> 00:09:50,410 zamiar nazw sklepów, po prostu arbitralnie, ale dość rozsądnie, 220 00:09:50,410 --> 00:09:54,680 Zakładam, że Alice, name, będzie po prostu być indeksowane do 0. 221 00:09:54,680 --> 00:09:58,030 A Bob, nazwa B, będą indeksowane do 1, i tak dalej. 222 00:09:58,030 --> 00:10:02,490 Więc mieliśmy mapowanie pomiędzy wejściami, które są ciągami, a hash 223 00:10:02,490 --> 00:10:04,560 miejscach, które są liczbami. 224 00:10:04,560 --> 00:10:07,740 >> Tak, że proces ten jest powszechnie znany jako funkcja skrótu, i można naprawdę 225 00:10:07,740 --> 00:10:09,130 wdrożyć go w kodzie. 226 00:10:09,130 --> 00:10:12,080 Gdybym chciał realizować funkcji skrótu , że robi dokładnie to, co my 227 00:10:12,080 --> 00:10:17,070 tylko opisane od ostatniego czasu, może deklaruje funkcję, która przyjmuje jako 228 00:10:17,070 --> 00:10:18,330 Wejście na przykład - 229 00:10:18,330 --> 00:10:22,190 i zróbmy to w ten Ekran tutaj. 230 00:10:22,190 --> 00:10:26,180 Gdybym chciał wdrożyć hash Funkcja, mogę powiedzieć, 231 00:10:26,180 --> 00:10:27,410 coś takiego. 232 00:10:27,410 --> 00:10:29,030 >> To będzie powrót int. 233 00:10:29,030 --> 00:10:33,600 To będzie się nazywać hash, i to zamierza przyjąć jako argument na 234 00:10:33,600 --> 00:10:38,920 ciąg, lub może być bardziej właściwe teraz, i powiedzieć, char *, nazwijmy to s. 235 00:10:38,920 --> 00:10:43,840 A potem to wszystko funkcja ma robić, ostatecznie jest powrócić int. 236 00:10:43,840 --> 00:10:45,990 Teraz, jak to robi, że może nie być tak oczywiste. 237 00:10:45,990 --> 00:10:49,510 Idę do realizacji tego bez forma kontroli błędów teraz. 238 00:10:49,510 --> 00:10:55,740 Mam zamiar po prostu ślepo powiedzieć, powrót s, co jest w przedziale 0, minus, 239 00:10:55,740 --> 00:10:58,850 powiedzmy, kapitał średnikiem. 240 00:10:58,850 --> 00:10:59,960 >> Całkowicie zepsuty. 241 00:10:59,960 --> 00:11:02,620 To nie jest idealne, ponieważ jedno, co będzie, jeśli s jest null? 242 00:11:02,620 --> 00:11:04,000 Złe rzeczy się wydarzy. 243 00:11:04,000 --> 00:11:07,940 Dwa, co oznacza, że ​​pierwsze pismo w tej nazwa nie litera jest? 244 00:11:07,940 --> 00:11:09,860 To nie będzie się obracać się dobrze albo. 245 00:11:09,860 --> 00:11:11,970 To może być mała litera lub nie litery ogóle. 246 00:11:11,970 --> 00:11:15,520 Więc nic do zrobienia tutaj, ale to jest podstawowa idea. 247 00:11:15,520 --> 00:11:19,010 >> Co opisaliśmy w zeszłym tygodniu ustnie jako tylko proces mapowania Alice do 248 00:11:19,010 --> 00:11:23,360 0 do 1 i Bob może być wyrażona z pewnością bardziej formulaically jako C 249 00:11:23,360 --> 00:11:24,320 funkcjonować tutaj. 250 00:11:24,320 --> 00:11:28,630 Nazywane ponownie hash, pobiera ciąg jako wejściowego, a następnie w jakiś sposób robi coś 251 00:11:28,630 --> 00:11:31,020 z tego wejścia do produkcji wyjście. 252 00:11:31,020 --> 00:11:34,130 Nie inaczej naszej czarnej skrzynki opis że mamy długi zrobione. 253 00:11:34,130 --> 00:11:36,550 Nie wiem, jak to może być pracuje pod maską. 254 00:11:36,550 --> 00:11:40,120 >> Do zestawu problemów, 6 Jednym z wyzwań jest, aby zdecydować, co 255 00:11:40,120 --> 00:11:41,920 będzie twoja funkcja skrótu jest? 256 00:11:41,920 --> 00:11:45,760 Co będzie w środku, że czarny box, i prawdopodobnie, to będzie 257 00:11:45,760 --> 00:11:50,380 trochę bardziej interesujące niż to, i zdecydowanie bardziej podatne na błędy 258 00:11:50,380 --> 00:11:53,180 kontroli niż ta konkretna realizacja. 259 00:11:53,180 --> 00:11:54,580 >> Ale mogą pojawić się problemy, prawda? 260 00:11:54,580 --> 00:11:57,760 Jeśli mamy strukturę danych, takich jak ta jeden, co jest jednym z problemów 261 00:11:57,760 --> 00:12:01,600 można uruchomić w czasie gdy włożysz coraz więcej do nazwy 262 00:12:01,600 --> 00:12:02,880 hash table? 263 00:12:02,880 --> 00:12:04,630 Otrzymasz kolizji, prawda? 264 00:12:04,630 --> 00:12:07,560 Co zrobić, jeśli masz Alice i Aarona, dwie osoby, których nazwiska się 265 00:12:07,560 --> 00:12:08,190 na początek? 266 00:12:08,190 --> 00:12:11,660 To nasuwa pytanie, gdzie umieścić drugą taką nazwę? 267 00:12:11,660 --> 00:12:15,050 >> Cóż, może naiwnie, wystarczy umieścić go gdzie Bob należy, ale Bob jest 268 00:12:15,050 --> 00:12:17,300 rodzaj wkręca jeśli próbujesz wstaw swoje nazwisko obok i 269 00:12:17,300 --> 00:12:18,240 nie ma miejsca dla niego. 270 00:12:18,240 --> 00:12:21,400 Więc można umieścić Bob, gdzie jest Charlie, i można sobie wyobrazić, to bardzo szybko 271 00:12:21,400 --> 00:12:23,020 przekazanymi do trochę bałaganu. 272 00:12:23,020 --> 00:12:25,600 Coś liniowy w końcu, gdzie Wystarczy sprawdzić całość 273 00:12:25,600 --> 00:12:28,190 poszukuje Alice i Bob lub Aaron lub Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Zamiast więc zaproponowaliśmy, a nie tylko liniowo sondowania na otwartej przestrzeni 275 00:12:33,230 --> 00:12:36,450 i plopping nazwiska tam, proponowany hodowcy podejście. 276 00:12:36,450 --> 00:12:41,740 Hash table wdrożone jeszcze z tablica wskaźników, ale typ danych 277 00:12:41,740 --> 00:12:44,500 Teraz były wskaźniki te wskaźniki. 278 00:12:44,500 --> 00:12:47,360 Wskaźniki do czego? 279 00:12:47,360 --> 00:12:48,730 Wskaźniki do połączonych listach. 280 00:12:48,730 --> 00:12:53,330 >> Ponieważ przypomnieć, że lista jest połączony naprawdę tylko wskaźnik do węzła, a 281 00:12:53,330 --> 00:12:57,110 węzeł ma następne pole i tego węzła ma kolejne pola, i tak dalej. 282 00:12:57,110 --> 00:13:00,690 Więc możesz teraz myśleć o tej tablicy na lewa strona tabeli mieszania jako 283 00:13:00,690 --> 00:13:01,820 co prowadzi do połączonej listy. 284 00:13:01,820 --> 00:13:07,000 Zaletą, która jest, jeśli się Kolizja między Alice i Aarona, 285 00:13:07,000 --> 00:13:09,300 co zrobić z Druga taka osoba? 286 00:13:09,300 --> 00:13:14,150 Po prostu podłącz go lub ją end, a nawet początek 287 00:13:14,150 --> 00:13:15,490 tego połączonej listy. 288 00:13:15,490 --> 00:13:17,340 >> I rzeczywiście, po prostu makaron przez że na chwilę. 289 00:13:17,340 --> 00:13:18,640 Gdzie jak najwięcej sensu? 290 00:13:18,640 --> 00:13:22,060 Jeśli wstawić Alice, a ona kończy się na pierwsze miejsce, to staram się 291 00:13:22,060 --> 00:13:25,310 wstawić nazwę Aarona, a tam oczywiście kolizji, należy umieścić 292 00:13:25,310 --> 00:13:27,400 go na początku z połączonej listy? 293 00:13:27,400 --> 00:13:30,944 To w tym pierwszym miejscu, lub na końcu? 294 00:13:30,944 --> 00:13:31,440 >> PUBLICZNOŚCI: [niesłyszalne]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID MALAN: OK. 296 00:13:31,990 --> 00:13:32,490 Słyszałem początku. 297 00:13:32,490 --> 00:13:33,903 Dlaczego na początku? 298 00:13:33,903 --> 00:13:34,750 >> PUBLICZNOŚCI: [niesłyszalne]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID MALAN: OK. 300 00:13:34,940 --> 00:13:36,520 To alfabetycznie, więc to miłe. 301 00:13:36,520 --> 00:13:37,330 To dobry obiekt. 302 00:13:37,330 --> 00:13:39,335 Pozwoli to zaoszczędzić mi trochę czasu, potencjalnie. 303 00:13:39,335 --> 00:13:43,290 To nie pozwala mi zrobić wyszukiwania binarnego, ale może przynajmniej być w stanie wyrwać się 304 00:13:43,290 --> 00:13:47,340 z pętli, czy zdaję sobie sprawę, dobrze, jestem droga przeszłości były Aaron będzie w tym 305 00:13:47,340 --> 00:13:48,310 klasyfikowane połączonej listy. 306 00:13:48,310 --> 00:13:50,360 I nie trzeba tracić czasu na szukanie , aż do końca. 307 00:13:50,360 --> 00:13:51,530 Więc to jest rozsądne. 308 00:13:51,530 --> 00:13:54,710 Dlaczego jeszcze warto włożyć Nazwa w kolizji 309 00:13:54,710 --> 00:13:56,660 początku listy? 310 00:13:56,660 --> 00:13:57,397 Co to jest? 311 00:13:57,397 --> 00:13:58,680 >> PUBLICZNOŚCI: [niesłyszalne]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID MALAN: To może zająć dużo czasu, aby dostać się do końca listy. 313 00:14:00,820 --> 00:14:02,490 I rzeczywiście, coraz dłuższe. 314 00:14:02,490 --> 00:14:04,920 Im więcej wstawione, że nazwy początek, już, że 315 00:14:04,920 --> 00:14:06,280 Łańcuch dostanie. 316 00:14:06,280 --> 00:14:07,890 Już, że związane lista będzie się. 317 00:14:07,890 --> 00:14:09,420 Więc jesteś naprawdę tracić czas. 318 00:14:09,420 --> 00:14:14,070 Może lepiej jest utrzymanie stały czas wstawiania, big O 1, 319 00:14:14,070 --> 00:14:18,470 by zawsze kładąc na zderzanie nazwę na początek listę, na 320 00:14:18,470 --> 00:14:21,230 i nie martwić się, jak wiele o sortowaniu. 321 00:14:21,230 --> 00:14:22,600 >> Jaka jest najlepsza odpowiedź? 322 00:14:22,600 --> 00:14:23,320 Nie wiadomo. 323 00:14:23,320 --> 00:14:26,140 To rodzaj zależy od tego, co dystrybucji, co jest wzór 324 00:14:26,140 --> 00:14:27,850 nazw wstawiasz. 325 00:14:27,850 --> 00:14:29,430 To nie jest koniecznie Oczywista odpowiedź. 326 00:14:29,430 --> 00:14:33,100 Jednak tutaj, ponownie, jest możliwość projektowania. 327 00:14:33,100 --> 00:14:37,220 >> Więc czym spojrzał na tej rzeczy, które jest naprawdę inna wielka szansa 328 00:14:37,220 --> 00:14:38,180 dla p-set 6. 329 00:14:38,180 --> 00:14:41,770 I uświadomić sobie, jeśli jeszcze go nie masz, Nurkowań Zamyla do obu z nich, ziemniaki 330 00:14:41,770 --> 00:14:43,260 tabele i stara, bardziej szczegółowo. 331 00:14:43,260 --> 00:14:45,630 I instruktażu wideo osadzone w p-set specyfikacji. 332 00:14:45,630 --> 00:14:46,590 To był trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. I co ciekawe o było to, że czas pracy 334 00:14:51,670 --> 00:14:59,510 z wyszukiwania nazwy, jak Maxwell ostatni raz, był duży O czym? 335 00:14:59,510 --> 00:15:01,040 Co to jest? 336 00:15:01,040 --> 00:15:01,920 >> PUBLICZNOŚCI: liczba liter. 337 00:15:01,920 --> 00:15:02,550 >> DAVID MALAN: Ilość liter. 338 00:15:02,550 --> 00:15:03,210 Słyszałem dwie rzeczy. 339 00:15:03,210 --> 00:15:04,630 Liczba liter i stałą czasową. 340 00:15:04,630 --> 00:15:05,540 Więc idziemy z tym pierwszym. 341 00:15:05,540 --> 00:15:06,410 Liczba liter. 342 00:15:06,410 --> 00:15:10,195 Cóż, to struktura danych, przypomnijmy, jest jak drzewo, drzewo genealogiczne, każdy z 343 00:15:10,195 --> 00:15:12,860 , których węzły są wykonane z tablic. 344 00:15:12,860 --> 00:15:16,300 A te tablice są wskaźniki do inne takie węzły lub inne takie 345 00:15:16,300 --> 00:15:17,670 tablice w drzewie. 346 00:15:17,670 --> 00:15:22,890 >> Więc jeśli chcemy to ustalić czy Maxwell jest tutaj, mogę iść 347 00:15:22,890 --> 00:15:26,890 do pierwszej tablicy, na górze drzewo, tzw root góry 348 00:15:26,890 --> 00:15:30,521 trie, a następnie wskaźnik m, to wskaźnik, to x, 349 00:15:30,521 --> 00:15:31,710 W, E, L, L. 350 00:15:31,710 --> 00:15:34,910 A potem, kiedy widzę jakiś specjalny symbol, oznaczone tutaj jako trójkąt. 351 00:15:34,910 --> 00:15:38,480 W kodzie zobaczysz, proponujemy, aby realizowane jako bool, tylko, że tak 352 00:15:38,480 --> 00:15:40,540 lub nie, słowo zatrzymuje się tutaj. 353 00:15:40,540 --> 00:15:45,270 >> Cóż, kiedy już odszedł do M-A-W-X E-L-L, czuje się jak siedem, może 354 00:15:45,270 --> 00:15:48,910 osiem jeśli idziemy jeden przeszłości, osiem działania w celu znalezienia Maxwell. 355 00:15:48,910 --> 00:15:53,050 Albo nazwijmy go K. Ale pamiętam ostatni czas, I argumentował, że jeśli istnieje 356 00:15:53,050 --> 00:15:57,540 realnie o maksymalnej długości słowo, np. znaków 40-kilka-nieparzyste, 357 00:15:57,540 --> 00:16:00,810 Maksymalna długość oznacza wartość stała. 358 00:16:00,810 --> 00:16:05,770 Tak naprawdę, tak, to jest technicznie duże O z 8 lub 7, lub naprawdę duże O K. Ale 359 00:16:05,770 --> 00:16:09,420 czy jest na to, co skończone cap K może być, to jest stała. 360 00:16:09,420 --> 00:16:12,080 A więc jest to duże O z 1 na koniec dnia. 361 00:16:12,080 --> 00:16:13,040 >> Nie w świecie rzeczywistym. 362 00:16:13,040 --> 00:16:15,960 Nie wtedy, kiedy można zacząć oglądać zegar, jak Twój program biegu. 363 00:16:15,960 --> 00:16:20,690 To absolutnie będzie nieco wolniej niż naprawdę stała 364 00:16:20,690 --> 00:16:21,840 razem z jednym etapie. 365 00:16:21,840 --> 00:16:25,540 To będzie siedem lub osiem kroków, ale to jest dużo, dużo lepiej 366 00:16:25,540 --> 00:16:30,080 niż algorytm, takich jak Big O n tym zależy od wielkości, co jest w 367 00:16:30,080 --> 00:16:31,220 Struktura danych. 368 00:16:31,220 --> 00:16:34,970 >> Wskazówka upside o to możemy wstawić milion w to więcej nazwisk 369 00:16:34,970 --> 00:16:38,170 struktury danych, ale ile jeszcze kroków to będzie nas znaleźć 370 00:16:38,170 --> 00:16:40,480 Maxwell w tym przypadku? 371 00:16:40,480 --> 00:16:40,780 Brak. 372 00:16:40,780 --> 00:16:41,820 On jest nienaruszone. 373 00:16:41,820 --> 00:16:45,480 I do tej pory, nie sądzę, widzieliśmy Przykład struktury danych lub 374 00:16:45,480 --> 00:16:48,560 algorytm, który był całkowicie niezależne od zewnętrznych 375 00:16:48,560 --> 00:16:50,040 Zachowania takie jak to. 376 00:16:50,040 --> 00:16:51,160 Ale to nie może być niesamowity. 377 00:16:51,160 --> 00:16:52,900 To nie może być jedyną na p-set 378 00:16:52,900 --> 00:16:53,570 >> I to nie jest. 379 00:16:53,570 --> 00:16:55,980 Niekoniecznie jest dane Struktura należy skłaniają się, 380 00:16:55,980 --> 00:16:58,220 bo jak hash tabel, kompromis. 381 00:16:58,220 --> 00:17:00,500 Jaka jest cena, jaką płaci się tutaj? 382 00:17:00,500 --> 00:17:00,940 Pamięć. 383 00:17:00,940 --> 00:17:02,890 To znaczy, to jest okropne ilość pamięci. 384 00:17:02,890 --> 00:17:05,569 I nie można dość zobaczyć go tutaj, bo Autor tego obrazu 385 00:17:05,569 --> 00:17:09,420 oczywiście obcięte wszystkie tablice, i nie widzimy wiele tych i 386 00:17:09,420 --> 00:17:12,700 B i C jest i grupy Q i Y-tych i Z w tych tablicach. 387 00:17:12,700 --> 00:17:13,630 Ale oni tam. 388 00:17:13,630 --> 00:17:17,660 >> Każdy z tych węzłów jest cały szereg od około 26 lub więcej, każdy z bajtów 389 00:17:17,660 --> 00:17:19,170 która reprezentuje nas. 390 00:17:19,170 --> 00:17:22,920 27 w naszym przypadku, tak, że możemy wspierać apostrofy w zestawie problem. 391 00:17:22,920 --> 00:17:27,030 Więc to struktura danych jest naprawdę, bardzo gęsta i szeroka. 392 00:17:27,030 --> 00:17:30,880 I że sam może skończyć się spowolnienie rzeczy w dół, lub przynajmniej kosztującej 393 00:17:30,880 --> 00:17:32,240 dużo więcej miejsca. 394 00:17:32,240 --> 00:17:34,020 Ale znowu, możemy wyciągnąć porównania tutaj. 395 00:17:34,020 --> 00:17:39,190 >> Przypomnijmy, jakiś czas temu, osiągnęliśmy dużo bardziej ekscytujący czas pracy przy sortowaniu 396 00:17:39,190 --> 00:17:42,880 kiedy używamy sortowanie korespondencji seryjnej, ale cena zapłaciliśmy osiągnąć n log n do seryjnej 397 00:17:42,880 --> 00:17:46,930 sort wymaga, że ​​spędzimy więcej jakiego źródła? 398 00:17:46,930 --> 00:17:47,690 Więcej miejsca. 399 00:17:47,690 --> 00:17:50,530 Potrzebowaliśmy dodatkowego tablicę skopiować ludzi do, tak jak 400 00:17:50,530 --> 00:17:51,620 my tutaj, na scenie. 401 00:17:51,620 --> 00:17:55,880 Więc jeszcze raz, nie ma wyraźnych zwycięzców, ale tylko prywatną projekt 402 00:17:55,880 --> 00:17:57,710 podejmowanie decyzji. 403 00:17:57,710 --> 00:17:58,060 >> Dobrze. 404 00:17:58,060 --> 00:17:59,130 Tak jak o tym? 405 00:17:59,130 --> 00:18:02,050 Każdy, kto rozpoznać, które D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Tak więc trzy z nas. 408 00:18:03,170 --> 00:18:03,750 Mather Dom. 409 00:18:03,750 --> 00:18:05,070 Jest to więc posiłki Mathera. 410 00:18:05,070 --> 00:18:09,650 Założę się, że wszystkie jadłodajnie mają stosy tac tak. 411 00:18:09,650 --> 00:18:11,950 I to jest rzeczywiście reprezentatywna coś mamy 412 00:18:11,950 --> 00:18:13,050 oczywiście widziałem już. 413 00:18:13,050 --> 00:18:14,850 Nazwaliśmy go dosłownie stos. 414 00:18:14,850 --> 00:18:18,970 A stos, w związku z Państwa pamięci komputera, gdzie dane idzie 415 00:18:18,970 --> 00:18:20,460 natomiast funkcje są nazywane. 416 00:18:20,460 --> 00:18:23,410 >> Na przykład, jakie rzeczy iść na stosie w odniesieniu do 417 00:18:23,410 --> 00:18:27,420 układ pamięci Omówiliśmy w tygodniach minionych? 418 00:18:27,420 --> 00:18:28,736 Co to jest? 419 00:18:28,736 --> 00:18:29,670 >> PUBLICZNOŚCI: wywołań funkcji. 420 00:18:29,670 --> 00:18:30,260 >> DAVID MALAN: Przepraszam. 421 00:18:30,260 --> 00:18:31,210 >> PUBLICZNOŚCI: wywołań funkcji. 422 00:18:31,210 --> 00:18:33,590 >> DAVID MALAN: Połączenia do funkcji, ale konkretnie, co jest w środku każdego z 423 00:18:33,590 --> 00:18:35,340 te ramki? 424 00:18:35,340 --> 00:18:37,220 Jakie rzeczy? 425 00:18:37,220 --> 00:18:37,460 Tak. 426 00:18:37,460 --> 00:18:38,500 Tak więc zmienne lokalne. 427 00:18:38,500 --> 00:18:43,080 Anytime potrzebowaliśmy pamięci lokalnej, jak argument, lub int I, lub int 428 00:18:43,080 --> 00:18:45,940 temp, czy cokolwiek lokalne zmienna jest, już 429 00:18:45,940 --> 00:18:47,210 oddanie, że na stos. 430 00:18:47,210 --> 00:18:49,610 I nazywamy to stos, bo tej idei malowania. 431 00:18:49,610 --> 00:18:52,940 Tylko rodzaj dopasowania się z rzeczywistością, Koncepcja tej decyzji. 432 00:18:52,940 --> 00:18:56,650 >> Ale okazuje się, że można również stack traktować jako struktury danych, 433 00:18:56,650 --> 00:19:00,110 Alternatywą do tablicy, alternatywna do połączonej listy. 434 00:19:00,110 --> 00:19:02,770 Coś koncepcyjnie bardziej interesujące , które mogą być jeszcze 435 00:19:02,770 --> 00:19:06,030 realizowane przy użyciu jednej z tych rzeczy, ale to jest inny rodzaj 436 00:19:06,030 --> 00:19:09,140 Struktura danych wsparcie, naprawdę, tylko dwie operacje. 437 00:19:09,140 --> 00:19:11,000 Ale można dodać na hodowcy funkcje niż te. 438 00:19:11,000 --> 00:19:12,180 Ale to są podstawy - 439 00:19:12,180 --> 00:19:13,510 wcisnąć i pop. 440 00:19:13,510 --> 00:19:19,240 >> A pomysł z komina jest to, że jeśli tu mamy, z lub bez Annenberg 441 00:19:19,240 --> 00:19:22,880 wiedząc, tacę z pokoju obok z numerem 9 na nim. 442 00:19:22,880 --> 00:19:23,870 Więc po prostu int. 443 00:19:23,870 --> 00:19:26,990 I chcę pchać to na danych Struktura, która obecnie jest pusty. 444 00:19:26,990 --> 00:19:28,790 Należy to uwzględnić w dolnej części stosu. 445 00:19:28,790 --> 00:19:33,150 Chciałbym wcisnąć ten numer 9 na stos, a teraz jest tam. 446 00:19:33,150 --> 00:19:36,040 >> Ale ciekawa rzecz o stosie jest to, że jeśli teraz chcę naciskać 447 00:19:36,040 --> 00:19:40,210 inne wartości, takie jak 17, i nacisnąć to na stos, mam zamiar zrobić 448 00:19:40,210 --> 00:19:43,290 tylko intuicyjna sprawa, mam zamiar umieścić go tam, gdzie my, ludzie, 449 00:19:43,290 --> 00:19:45,180 byłby skłonny umieścić go na górze. 450 00:19:45,180 --> 00:19:48,850 Ale co ciekawe teraz jest, jak mogę dostać się na 9? 451 00:19:48,850 --> 00:19:50,670 Wiesz, ja nie bez pewnego wysiłku. 452 00:19:50,670 --> 00:19:54,070 >> Tak więc to, co jest ciekawe Stos jest to, że ze względów konstrukcyjnych, 453 00:19:54,070 --> 00:19:56,330 to struktura danych LIFO. 454 00:19:56,330 --> 00:19:59,680 Silly sposób opisywania ostatnie przyszło pierwsze wyszło. 455 00:19:59,680 --> 00:20:03,280 Więc ostatnia liczba w w tym czasie było 17. 456 00:20:03,280 --> 00:20:07,540 Więc jeśli chcę coś off pop stosu, to może być tylko 17. 457 00:20:07,540 --> 00:20:11,890 Więc jest obowiązkowa kolejność operacje tutaj, gdzie ostatni element 458 00:20:11,890 --> 00:20:14,260 w musi być pierwszy na zewnątrz. 459 00:20:14,260 --> 00:20:16,440 Stąd skrót, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Więc dlaczego może to być przydatne? 461 00:20:19,160 --> 00:20:22,690 Czy ich konteksty, w których bym chcą strukturę danych jak to? 462 00:20:22,690 --> 00:20:24,810 Cóż, to z pewnością przydatne wewnątrz komputera. 463 00:20:24,810 --> 00:20:29,050 Więc systemy operacyjne wyraźnie to wykorzystać rodzaj struktury danych na stosach. 464 00:20:29,050 --> 00:20:32,800 Będziemy także pojawia się ten sam pomysł jeśli chodzi o stronach internetowych. 465 00:20:32,800 --> 00:20:35,890 Więc ten tydzień i tydzień następny i poza nią, i jak rozpocząć wdrażanie sieci 466 00:20:35,890 --> 00:20:39,490 strony w języku nazywa HTML, można właściwie wykorzystywać strukturę danych jak 467 00:20:39,490 --> 00:20:42,690 To określenie, czy strona jest prawidłowo sformatowana. 468 00:20:42,690 --> 00:20:47,170 Ponieważ zobaczymy wszystkie strony internetowe postępuj rodzaj hierarchii, wcięcia 469 00:20:47,170 --> 00:20:52,030 która, na koniec dnia, są Struktura drzewa pod maską. 470 00:20:52,030 --> 00:20:53,620 Więc więcej o tym za chwilę. 471 00:20:53,620 --> 00:20:56,560 >> Ale na razie niech zaproponować Moment, w jaki sposób możemy go o 472 00:20:56,560 --> 00:20:58,830 reprezentujący co stack jest? 473 00:20:58,830 --> 00:21:03,370 Pozwól mi zaproponować, że wdrożenie stos z kodem tak. 474 00:21:03,370 --> 00:21:07,990 Więc stos będzie miał w jej wnętrzu dwie rzeczy, tablica nazwana tace 475 00:21:07,990 --> 00:21:09,510 tylko być zgodne z demo. 476 00:21:09,510 --> 00:21:12,660 I każdy z elementów tej tablicy będzie typu int. 477 00:21:12,660 --> 00:21:14,740 I pojemność jest prawdopodobnie to, co? 478 00:21:14,740 --> 00:21:18,796 Bo ja nie pisałem Pełna definicja tutaj. 479 00:21:18,796 --> 00:21:21,535 >> To chyba maksymalna rozmiar tablicy. 480 00:21:21,535 --> 00:21:25,150 I to prawdopodobnie uznane za ostry zdefiniować na początku pliku, niektóre 481 00:21:25,150 --> 00:21:28,450 rodzaj stała jak sugeruje Sama kapitalizacja. 482 00:21:28,450 --> 00:21:32,250 Więc gdzieś ilość jest zdefiniowana od maksymalnej możliwej wielkości. 483 00:21:32,250 --> 00:21:35,590 W międzyczasie, wewnątrz struktury danych znany jako stos nie będzie 484 00:21:35,590 --> 00:21:38,630 być liczbą całkowitą tylko znane po prostu jako wielkości. 485 00:21:38,630 --> 00:21:43,400 >> Więc gdybym miał reprezentować to teraz obrazowo, załóżmy, że to 486 00:21:43,400 --> 00:21:48,070 Cała czarna skrzynka reprezentuje mój stos. 487 00:21:48,070 --> 00:21:50,070 Wewnątrz niej ma dwie zmienne. 488 00:21:50,070 --> 00:21:54,780 Więc mam zamiar wyciągnąć Pierwszy z nich, jak wielkości. 489 00:21:54,780 --> 00:21:57,420 I drugi idę narysować w postaci tablicy. 490 00:21:57,420 --> 00:22:01,060 >> Ale tylko do przechowywania rzeczy uporządkowany, normalnie chciałbym zwrócić tablicę jak 491 00:22:01,060 --> 00:22:04,910 ta, ale to miłe jeśli mecz rzeczywistość, lub 492 00:22:04,910 --> 00:22:06,230 dopasować model mentalny. 493 00:22:06,230 --> 00:22:12,880 Więc pozwól mi zamiast zwrócić tablicę pionowo, która jest po prostu, znowu, 494 00:22:12,880 --> 00:22:13,840 odtworzeniem. 495 00:22:13,840 --> 00:22:16,610 Tak naprawdę nie ma znaczenia, co to jest pod maską. 496 00:22:16,610 --> 00:22:20,350 I powiemy, że domyślnie, pojemność ma być trzy. 497 00:22:20,350 --> 00:22:23,480 Tak więc będzie to Położenie 0, ta będzie miejsce 1, to 498 00:22:23,480 --> 00:22:25,740 będzie położenie 2. 499 00:22:25,740 --> 00:22:29,330 >> Gdybym przekupić z piłką na stres, by ktoś chciał wymyślić i uruchomić 500 00:22:29,330 --> 00:22:30,870 wsiąść tu tylko na chwilę? 501 00:22:30,870 --> 00:22:31,960 OK, zobaczyłem rękę pierwszy. 502 00:22:31,960 --> 00:22:33,950 Chodź na górę. 503 00:22:33,950 --> 00:22:36,500 Dobrze. 504 00:22:36,500 --> 00:22:38,760 Tak więc uważam, że jest Steven. 505 00:22:38,760 --> 00:22:40,035 Chodź na górę. 506 00:22:40,035 --> 00:22:40,770 Dobrze. 507 00:22:40,770 --> 00:22:46,760 >> Ale przypuśćmy, że teraz możemy cofnąć się do początkowego stan świata, gdzie 508 00:22:46,760 --> 00:22:52,180 właśnie oświadczył, stos, i to będzie o pojemności trzech. 509 00:22:52,180 --> 00:22:54,470 Ale wielkość nie została jeszcze ustalona. 510 00:22:54,470 --> 00:22:56,100 Brodziki nie została jeszcze ustalona. 511 00:22:56,100 --> 00:22:57,300 Więc kilka pytań pierwsze. 512 00:22:57,300 --> 00:23:01,310 I pozwól mi dać mikrofon, dzięki czemu można bardziej aktywnie uczestniczyć w tym. 513 00:23:01,310 --> 00:23:05,190 >> Więc co jest w środku wielkości w tej chwili w czasie, gdy wszystkie Zrobiłem to 514 00:23:05,190 --> 00:23:09,340 oświadczył stos z jedna linia kodu? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Nie bardzo. 516 00:23:10,100 --> 00:23:12,080 >> DAVID MALAN: OK, nie wiele. 517 00:23:12,080 --> 00:23:14,410 Czy wiemy, co jest w środku od wielkości, wiemy, co jest w środku 518 00:23:14,410 --> 00:23:16,330 tej tablicy tutaj? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Just losowy kod, prawda? 520 00:23:18,630 --> 00:23:20,220 Po prostu - 521 00:23:20,220 --> 00:23:23,230 >> DAVID MALAN: Tak, mam zamiar Nazywamy to kod, ale random - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Co. 523 00:23:23,820 --> 00:23:28,290 >> DAVID MALAN: Rzeczy takie jak random 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID MALAN: Bity, prawda? 526 00:23:29,530 --> 00:23:31,190 Tak więc wartości śmieci, prawda? 527 00:23:31,190 --> 00:23:33,470 Więc permutacje 0 i 1-tych. 528 00:23:33,470 --> 00:23:35,920 Pozostałości wcześniejszych zwyczajów tej pamięci. 529 00:23:35,920 --> 00:23:38,150 I tak naprawdę nie wiem jakie wartości są, więc zazwyczaj wyciągnąć je 530 00:23:38,150 --> 00:23:38,930 jako znaki zapytania. 531 00:23:38,930 --> 00:23:41,990 >> Tak więc pierwszą rzeczą, że jesteśmy prawdopodobnie będzie chciał zrobić tutaj - 532 00:23:41,990 --> 00:23:46,630 i pozwól mi dać to pole wewnątrz stamtąd nazwa - tacki. 533 00:23:46,630 --> 00:23:49,540 Co powinniśmy przypuszczalnie zainicjować rozmiar do jeżeli chcemy 534 00:23:49,540 --> 00:23:51,040 rozpocząć korzystanie z tego stosu? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Tray jest sub 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID MALAN: Tak, OK. 537 00:23:53,910 --> 00:23:56,710 Żeby było jasne, pojemność jest zadeklarowana gdzie indziej, jak trzy. 538 00:23:56,710 --> 00:23:58,570 I to jest to, co ja użyłam przydzielić tablicę. 539 00:23:58,570 --> 00:24:03,535 Rozmiar ma zamiar odwołać się do tego, jak wiele Tacki są obecnie na stosie. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID MALAN: Tak powinno być zero. 542 00:24:04,460 --> 00:24:07,760 Więc śmiało, a z każdym palcem, narysować zero w wielkości. 543 00:24:07,760 --> 00:24:08,440 Dobrze. 544 00:24:08,440 --> 00:24:10,920 Więc teraz, co jest w środku tego tutaj, nie wiemy. 545 00:24:10,920 --> 00:24:12,160 Są to tak naprawdę wartości śmieci. 546 00:24:12,160 --> 00:24:14,800 Więc możemy narysować znaki zapytania, ale trzymajmy teraz czysty deska 547 00:24:14,800 --> 00:24:16,300 bo to nie ma znaczenia co tam jest. 548 00:24:16,300 --> 00:24:19,130 Nie musimy zainicjować tablicę do niczego, bo jeśli wiemy, że 549 00:24:19,130 --> 00:24:23,100 Rozmiar stosu jest równa zero, oraz, że nie powinny być patrząc na coś w 550 00:24:23,100 --> 00:24:25,590 ta tablica i tak w ten punkt w czasie. 551 00:24:25,590 --> 00:24:29,970 >> Przyjmijmy teraz, że wciskam Numer 9 na stos. 552 00:24:29,970 --> 00:24:33,750 Jak powinniśmy zaktualizować strukturę danych wewnątrz tej czarnej skrzynki? 553 00:24:33,750 --> 00:24:35,540 Jakie wartości należy zmienić? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: W - 555 00:24:36,200 --> 00:24:37,400 rozmiar? 556 00:24:37,400 --> 00:24:37,650 >> DAVID MALAN: OK. 557 00:24:37,650 --> 00:24:38,770 Rozmiar powinien być, co? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Rozmiar będzie jeden. 559 00:24:39,580 --> 00:24:39,870 >> DAVID MALAN: OK. 560 00:24:39,870 --> 00:24:41,110 Tak więc wielkość powinna stać się jednym. 561 00:24:41,110 --> 00:24:42,540 Więc można to zrobić w kilka sposobów. 562 00:24:42,540 --> 00:24:46,920 Podam teraz swoje palec jest gumka. 563 00:24:46,920 --> 00:24:47,260 Dobrze. 564 00:24:47,260 --> 00:24:49,960 Właśnie teraz palec jest szczotka. 565 00:24:49,960 --> 00:24:50,330 Dobrze. 566 00:24:50,330 --> 00:24:52,820 A teraz, co jeszcze musi się zmienić, Oczywiście, w strukturze danych? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Jedziemy z bottom up to 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID MALAN: 9. 569 00:24:57,760 --> 00:24:58,420 OK, Good. 570 00:24:58,420 --> 00:25:01,550 Tak więc nadal nie ma znaczenia, co jest w miejsce jeden lub dwa, ponieważ są one 571 00:25:01,550 --> 00:25:04,520 wartości śmieci, ale nie przeszkadza patrząc tam, bo rozmiar jest 572 00:25:04,520 --> 00:25:07,540 mówi nam, że tylko pierwszy element jest rzeczywiście uzasadnione. 573 00:25:07,540 --> 00:25:10,400 Więc teraz wciskam 17 na liście. 574 00:25:10,400 --> 00:25:11,830 Co się dzieje z tym zdjęciem? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Tak rozmiar będzie iść do dwóch. 576 00:25:14,720 --> 00:25:15,300 >> DAVID MALAN: OK. 577 00:25:15,300 --> 00:25:16,070 Jesteś gumka - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Jesteś gumka. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID MALAN: Jesteś brush. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID MALAN: OK. 584 00:25:20,920 --> 00:25:21,600 I co jeszcze? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: A potem - 586 00:25:22,600 --> 00:25:22,915 >> DAVID MALAN: Mamy pchnął 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Trzymamy 17 na górze, więc - 588 00:25:24,760 --> 00:25:25,710 >> DAVID MALAN: OK, dobrze. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - spadek w dół. 590 00:25:27,040 --> 00:25:27,530 >> DAVID MALAN: W porządku. 591 00:25:27,530 --> 00:25:27,940 Robi się łatwo. 592 00:25:27,940 --> 00:25:29,300 I nie zamierzam pomóc tym razem. 593 00:25:29,300 --> 00:25:30,510 Naciśnij 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Gotowe. 595 00:25:31,720 --> 00:25:34,870 Staje gumka. 596 00:25:34,870 --> 00:25:37,340 Staję się szczotki. 597 00:25:37,340 --> 00:25:39,340 A potem kładę 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID MALAN: 22. 599 00:25:40,100 --> 00:25:40,620 Excellent. 600 00:25:40,620 --> 00:25:41,380 Więc jeszcze raz. 601 00:25:41,380 --> 00:25:44,280 Mam teraz zamiar naciskać na stos 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh Boże. 604 00:25:50,278 --> 00:25:52,520 Naprawdę złapał mnie z tropu. 605 00:25:52,520 --> 00:25:53,703 >> DAVID MALAN: Nie zobacz nadchodzi? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Nie widziałem tego spodziewać. 607 00:25:55,930 --> 00:25:58,756 Mogliśmy ponownie Początkowa zdolność? 608 00:25:58,756 --> 00:25:59,790 >> DAVID MALAN: To jest dobre pytanie. 609 00:25:59,790 --> 00:26:02,360 Więc my niby malowane siebie w kącie tutaj. 610 00:26:02,360 --> 00:26:06,740 Czy naprawdę nie jest dobry out dla Steven bo mamy przydzielone tej tablicy 611 00:26:06,740 --> 00:26:09,130 statycznie, że tak powiem, w środku struktury danych. 612 00:26:09,130 --> 00:26:12,170 A my w zasadzie trudno kodowane że jest z trzech wielkości. 613 00:26:12,170 --> 00:26:14,170 Tak naprawdę nie możemy przydzielić go. 614 00:26:14,170 --> 00:26:20,020 >> Możemy, jeśli poszliśmy z powrotem, my nowo tace być wskaźnikiem, że 615 00:26:20,020 --> 00:26:22,300 możemy użyć malloc do pamięci rękę do. 616 00:26:22,300 --> 00:26:25,050 Bo jeśli mamy w pamięci z heap przez malloc, my 617 00:26:25,050 --> 00:26:26,430 może następnie uwolnić go. 618 00:26:26,430 --> 00:26:29,630 Ale zanim zwalniając go, możemy przydzielić większą ilość pamięci, 619 00:26:29,630 --> 00:26:31,330 aktualizować wskaźnik, i tak dalej. 620 00:26:31,330 --> 00:26:33,500 Ale teraz, to jest naprawdę Najlepsze, co możemy zrobić. 621 00:26:33,500 --> 00:26:36,360 Naciśnij i pop są prawdopodobnie będzie aby sygnalizować jakiś błąd. 622 00:26:36,360 --> 00:26:40,270 >> Tak na przykład, nasza implementacja push może powrócić bool, który 623 00:26:40,270 --> 00:26:42,390 wcześniej zwróciło prawda, prawda, prawda. 624 00:26:42,390 --> 00:26:48,390 Ale czwarty raz, to będzie mieć do return false, na przykład. 625 00:26:48,390 --> 00:26:48,540 Dobrze. 626 00:26:48,540 --> 00:26:49,540 Bardzo dobrze zrobione. 627 00:26:49,540 --> 00:26:50,060 Gratulacje. 628 00:26:50,060 --> 00:26:52,160 Zasłużyłeś na swoją piłkę stres dzisiaj. 629 00:26:52,160 --> 00:26:53,110 >> [APPLAUSE] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Dziękuję. 631 00:26:54,382 --> 00:26:55,680 >> DAVID MALAN: Dziękuję. 632 00:26:55,680 --> 00:26:59,740 OK, tak więc wydaje się, że niewiele o krok do przodu, prawda? 633 00:26:59,740 --> 00:27:01,410 Opisaliśmy tę strukturę danych. 634 00:27:01,410 --> 00:27:02,320 To było przekonujące, prawda? 635 00:27:02,320 --> 00:27:03,200 Systemy operacyjne podoba. 636 00:27:03,200 --> 00:27:06,360 Podobno w internecie może skorzystać z tego, i inne aplikacje nadal. 637 00:27:06,360 --> 00:27:10,870 Ale to, co głupie ograniczenie, że jesteśmy Powrót Sortuj tygodnia dwie granice 638 00:27:10,870 --> 00:27:12,880 gdzie mamy ustalone tablice wielkości. 639 00:27:12,880 --> 00:27:15,010 >> Więc rzeczywiście istnieje kilka sposób możemy rozwiązać ten problem. 640 00:27:15,010 --> 00:27:18,750 Możemy dynamicznie przydziela tablicę, nie przez trudne kodowanie go jak już 641 00:27:18,750 --> 00:27:22,600 odbywa się tutaj, lecz ponownie deklarowania tego, żeby była jasność, jak 642 00:27:22,600 --> 00:27:23,830 coś takiego. 643 00:27:23,830 --> 00:27:29,040 Int tace * nie, decydując na mocy jeszcze. 644 00:27:29,040 --> 00:27:35,460 Ale kiedy Oświadczam stos gdzie indziej w moim kodu, mogłem wtedy zadzwonić malloc, 645 00:27:35,460 --> 00:27:38,250 uzyskać adres z kawałkiem pamięci, i mogłem przypisać 646 00:27:38,250 --> 00:27:39,980 że adres, na tackach. 647 00:27:39,980 --> 00:27:43,340 >> A potem, bo to po prostu kawał pamięci, mogę nadal korzystać z placu 648 00:27:43,340 --> 00:27:45,450 Zapis wspornik w zwykły sposób. 649 00:27:45,450 --> 00:27:49,020 Bo znowu, jest jakby to funkcjonalnym odpowiednikiem tablic i 650 00:27:49,020 --> 00:27:50,820 fragmenty pamięci, które pochodzą z powrotem z malloc. 651 00:27:50,820 --> 00:27:53,090 Możemy traktować jeden od drugiego używając arytmetyki wskaźników lub 652 00:27:53,090 --> 00:27:54,440 square notacja uchwytach. 653 00:27:54,440 --> 00:27:55,660 Więc to jest jeden sposób. 654 00:27:55,660 --> 00:28:00,120 >> Ale jak inaczej możemy realizować ten Ta sama struktura danych, potencjalnie? 655 00:28:00,120 --> 00:28:00,280 Prawda? 656 00:28:00,280 --> 00:28:04,530 Czuję się po prostu rozwiązać ten Problem jak tydzień temu. 657 00:28:04,530 --> 00:28:08,860 Co było rozwiązanie tego problemu że Steven wpadł? 658 00:28:08,860 --> 00:28:10,370 Tak połączone listy, tuż. 659 00:28:10,370 --> 00:28:13,410 >> Jeśli problemem jest to, że mamy do malowania się w rogu, przyznając 660 00:28:13,410 --> 00:28:17,580 z góry pamięci zbyt mało, że Następnie trzeba jakoś zająć, dobrze, 661 00:28:17,580 --> 00:28:19,880 dlaczego nie tylko uniknąć wydać w sumie? 662 00:28:19,880 --> 00:28:26,170 Dlaczego nie wystarczy zadeklarować tace być wskaźnik do węzła, ergo lista powiązana, 663 00:28:26,170 --> 00:28:30,740 a potem po prostu przeznaczyć nowe węzły za każdym razem, Steven potrzebne, aby dopasować 664 00:28:30,740 --> 00:28:32,400 Numer do struktury danych. 665 00:28:32,400 --> 00:28:34,200 >> Tak więc obraz będzie musiał zmienić. 666 00:28:34,200 --> 00:28:38,220 To nie będzie tak czyste, jak i proste, jak tylko tablicą trzech liczb całkowitych. 667 00:28:38,220 --> 00:28:42,970 Teraz to będzie wskaźnik do struct, a struktura jest zamiar 668 00:28:42,970 --> 00:28:44,830 mają int i następny wskaźnik. 669 00:28:44,830 --> 00:28:47,670 To będzie prowadzić za pośrednictwem tego wskaźnika do innej takiej struktury do 670 00:28:47,670 --> 00:28:48,600 kolejny przykład struct. 671 00:28:48,600 --> 00:28:50,560 Tak więc obraz faktycznie dostać Messier bitowej. 672 00:28:50,560 --> 00:28:52,950 A my nie strzałki wiążąc wszystko razem. 673 00:28:52,950 --> 00:28:55,280 >> Ale to jest w porządku, w porządku, bo widzieliśmy, jak to zrobić. 674 00:28:55,280 --> 00:28:58,180 A kiedy się komfortowo wdrażaniu coś linked 675 00:28:58,180 --> 00:29:01,450 Lista, która musisz zrobić, jeśli Decydując się na zastosowanie tabeli mieszania z 676 00:29:01,450 --> 00:29:05,120 oddzielne łańcucha dla p-set 6, można używać go jako element, lub 677 00:29:05,120 --> 00:29:08,870 składnik lub w Scratch mówić, procedura, coś, co mówiąc, ci 678 00:29:08,870 --> 00:29:12,560 stworzył swój własny kawałek układanki które następnie można ponownie wykorzystać. 679 00:29:12,560 --> 00:29:17,090 Więc kompromisów, ale potencjalnych rozwiązań że mamy rzeczywiście widział. 680 00:29:17,090 --> 00:29:20,560 >> Tak często, widzisz to co rok lub dwa, kiedy Apple wypuszcza 681 00:29:20,560 --> 00:29:23,060 coś nowego i wszyscy szaleńcy Line up poza Apple 682 00:29:23,060 --> 00:29:27,050 przechowywać do zakupu ich marginalna uaktualnienia na sprzęcie. 683 00:29:27,050 --> 00:29:30,420 Mówię o tym, że jest OK, bo Jestem jedną z tych osób. 684 00:29:30,420 --> 00:29:35,140 Więc jaki rodzaj struktury danych może reprezentować tę rzeczywistość? 685 00:29:35,140 --> 00:29:36,980 >> No cóż, nazwijmy to kolejka, linia. 686 00:29:36,980 --> 00:29:40,270 Więc Brytyjczycy nazywają to zwykle kolejki, tak więc jest to ładne imię. 687 00:29:40,270 --> 00:29:44,960 I dwie operacje kolejki wspiera my nazywamy Enqueue 688 00:29:44,960 --> 00:29:48,900 działanie i Dequeue operacja, które są podobne 689 00:29:48,900 --> 00:29:50,120 duch naciskać i pop. 690 00:29:50,120 --> 00:29:54,060 To tylko rodzaj różni się Konwencja, z czym mamy do wywoływania tych. 691 00:29:54,060 --> 00:29:57,680 Ale enqueue coś znaczy dodawać lub wprowadzić je do struktury danych. 692 00:29:57,680 --> 00:29:59,570 To usunie z niej oznacza usunięcie go. 693 00:29:59,570 --> 00:30:05,170 Ale podczas gdy stos było dane LIFO Struktura, kolejka jest pierwszym w, 694 00:30:05,170 --> 00:30:06,740 Najpierw się struktury danych. 695 00:30:06,740 --> 00:30:10,050 >> Jeśli jesteś pierwszą osobą w kolejce, będzie pierwszym, aby uzyskać 696 00:30:10,050 --> 00:30:12,420 z linii i zakupu nowego urządzenia. 697 00:30:12,420 --> 00:30:18,070 Wyobraź sobie, jak zdenerwowany osoby te byłyby jeśli Apple zamiast stosować stos, na 698 00:30:18,070 --> 00:30:21,250 instancją, do realizacji kompletacji up z nowej zabawki. 699 00:30:21,250 --> 00:30:24,310 Więc kolejki sensu, oczywiście, i możemy myśleć o wszelkiego rodzaju 700 00:30:24,310 --> 00:30:27,480 aplikacji, prawdopodobnie, w kolejkach, zwłaszcza, gdy chcemy uczciwości. 701 00:30:27,480 --> 00:30:30,040 Więc jak możemy realizować te jako struktury danych? 702 00:30:30,040 --> 00:30:33,680 >> Cóż, proponuję, że może musisz zrobić to w ten sposób. 703 00:30:33,680 --> 00:30:35,225 Więc mam zamiar teraz mają numery. 704 00:30:35,225 --> 00:30:38,190 Będziemy więc zachować proste i nie muszą mówić w kategoriach tac. 705 00:30:38,190 --> 00:30:40,220 Tylko liczby, które ludzie zdobyć. 706 00:30:40,220 --> 00:30:43,760 Pojemność będzie znów naprawić liczba osób, które mogą być w 707 00:30:43,760 --> 00:30:46,900 linia ta, jak trzy lub bez względu na inne wartości. 708 00:30:46,900 --> 00:30:50,760 >> Ale proponuję, że trzeba śledzić nie tylko od wielkości 709 00:30:50,760 --> 00:30:52,370 Kolejka, jak wiele rzeczy w nim. 710 00:30:52,370 --> 00:30:56,310 Tak więc rozmiar jest obecny rozmiar, pojemność Jest to maksymalny rozmiar. 711 00:30:56,310 --> 00:30:58,540 Tylko znowu, nomenklatura umownie. 712 00:30:58,540 --> 00:31:03,680 Dlaczego potrzebuję dodatkowego int wewnątrz z kolejki, aby śledzić, kto jest w 713 00:31:03,680 --> 00:31:05,365 przed linią? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Dlaczego muszę to zrobić w tym przypadku? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Cóż, jak to jest obraz zmieni? 718 00:31:16,190 --> 00:31:19,280 Prawdopodobnie mogę ponownie najbardziej z tego obrazu. 719 00:31:19,280 --> 00:31:21,480 Pozwólcie mi iść dalej i usunąć to, co jest tutaj. 720 00:31:21,480 --> 00:31:24,580 Damy to nieco inna nazwa tutaj. 721 00:31:24,580 --> 00:31:28,930 Chcę się pozbyć 17, pozbądźmy od 9, niech się pozbyć 3. 722 00:31:28,930 --> 00:31:30,410 I dodajmy jeszcze jedno. 723 00:31:30,410 --> 00:31:34,710 Proponuję, że trzeba śledzić z przodu listy, która jest po prostu 724 00:31:34,710 --> 00:31:35,570 będzie int również. 725 00:31:35,570 --> 00:31:36,550 A my jedziemy prosto. 726 00:31:36,550 --> 00:31:37,740 Nie powiązane lista teraz. 727 00:31:37,740 --> 00:31:40,900 >> Będziemy przyznać, że mamy zamiar trzaskać się tego limitu. 728 00:31:40,900 --> 00:31:43,720 Ale to, co chcę zobaczyć się tym razem? 729 00:31:43,720 --> 00:31:47,240 Więc załóżmy, że śmiało i pierwszy osoba pojawia się w linii, a 730 00:31:47,240 --> 00:31:48,560 to numer 9. 731 00:31:48,560 --> 00:31:49,680 Mamy piłeczki antystresowe. 732 00:31:49,680 --> 00:31:51,330 Czy można ukraść, powiedzmy, dwóch lub trzech osób? 733 00:31:51,330 --> 00:31:52,690 Jeden, dwa, trzy? 734 00:31:52,690 --> 00:31:53,120 Chodź na górę. 735 00:31:53,120 --> 00:31:56,022 Od przodu, ponieważ zrobimy to jedno szybkie. 736 00:31:56,022 --> 00:31:59,415 >> Każdy z was jest teraz będzie Chłopiec wentylator w kolejce w Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Nie będziesz otrzymywać sprzęt Apple na koniec tego jednak. 739 00:32:06,210 --> 00:32:06,500 Dobrze. 740 00:32:06,500 --> 00:32:09,430 Więc jesteś numer 9, jesteś numer 17, numer 22. 741 00:32:09,430 --> 00:32:12,130 Są to arbitralne liczby, jak Student ID lub cokolwiek. 742 00:32:12,130 --> 00:32:14,550 A za chwilę, zacznijmy do dodawania rzeczy. 743 00:32:14,550 --> 00:32:16,000 A ja uruchomić płytę tutaj w tym czasie. 744 00:32:16,000 --> 00:32:19,570 >> Więc w tym przypadku, mam zainicjowany przód być - 745 00:32:19,570 --> 00:32:22,380 I naprawdę nie obchodzi to, co przednia jest, ponieważ rozmiar jest zerowy. 746 00:32:22,380 --> 00:32:24,480 Więc to może równie dobrze być znak zapytania. 747 00:32:24,480 --> 00:32:26,170 To wszystko są znaki zapytania. 748 00:32:26,170 --> 00:32:29,880 Więc teraz zaczniemy rzeczywiście zobaczyć niektóre ludzie w kolejce w sklepie. 749 00:32:29,880 --> 00:32:33,320 >> Więc jeśli numer 9, jesteś pierwszy tam o 5 rano, iść do przodu i wyrównane, 750 00:32:33,320 --> 00:32:34,210 lub nocy. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Więc teraz 9 jest tutaj. 753 00:32:35,940 --> 00:32:37,940 Tak 9 jest w przedniej części listy. 754 00:32:37,940 --> 00:32:41,440 Więc mam zamiar iść dalej i aktualizować rozmiar danych bieżących 755 00:32:41,440 --> 00:32:44,740 Struktura nie jest już 0, ale jest 1. 756 00:32:44,740 --> 00:32:47,630 Mam zamiar umieścić 9 w początku listy. 757 00:32:47,630 --> 00:32:51,020 Pozwólcie mi iść dalej i włączyć ekran więc widzimy obok nas tutaj. 758 00:32:51,020 --> 00:32:53,220 >> A teraz, co chcę oddał do przodu? 759 00:32:53,220 --> 00:32:56,240 Będę śledzić, że przód kolejki teraz 760 00:32:56,240 --> 00:32:58,570 jest w położeniu 0. 761 00:32:58,570 --> 00:33:00,510 Bo to, co jest dalej będzie się działo? 762 00:33:00,510 --> 00:33:03,000 Dobrze, załóżmy, że teraz ja enqueue 17, jak również. 763 00:33:03,000 --> 00:33:04,510 Więc hop w wierszu. 764 00:33:04,510 --> 00:33:07,060 I jeszcze raz, jakby drzwi Sklep będzie tutaj. 765 00:33:07,060 --> 00:33:08,700 Więc teraz dodałem 17. 766 00:33:08,700 --> 00:33:10,810 I mimo, że ci faceci są blokowanie ekran, to jest OK, 767 00:33:10,810 --> 00:33:12,300 ponieważ widzimy go tutaj. 768 00:33:12,300 --> 00:33:12,910 Przepraszam. 769 00:33:12,910 --> 00:33:13,810 >> PUBLICZNOŚCI: Możemy przejść - 770 00:33:13,810 --> 00:33:14,660 >> DAVID MALAN: Nie, to jest OK. 771 00:33:14,660 --> 00:33:16,000 To ogromna tam. 772 00:33:16,000 --> 00:33:18,580 Tak więc 17 jest teraz wewnątrz kolejce. 773 00:33:18,580 --> 00:33:21,332 Muszę zaktualizować które pola teraz chociaż? 774 00:33:21,332 --> 00:33:23,210 OK, na pewno rozmiar. 775 00:33:23,210 --> 00:33:26,430 A co z przodu? 776 00:33:26,430 --> 00:33:27,040 OK, nr. 777 00:33:27,040 --> 00:33:30,200 Z przodu nie powinno się zmienić, bo w przeciwieństwie do stosu, my 778 00:33:30,200 --> 00:33:31,370 Aby zachować bezstronność. 779 00:33:31,370 --> 00:33:35,150 Więc jeśli 9 przyszedł pierwszy, chcemy 9 do pierwszej z linii 780 00:33:35,150 --> 00:33:36,420 i do sklepu. 781 00:33:36,420 --> 00:33:37,220 >> W rzeczywistości, zobaczmy to. 782 00:33:37,220 --> 00:33:42,235 Zanim wstawić 22, niech śmiało Dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Jak masz na imię? 784 00:33:42,970 --> 00:33:43,680 >> PUBLICZNOŚCI: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID MALAN: Jake będzie zostać wyjęty z kolejki teraz. 786 00:33:45,440 --> 00:33:48,050 Więc masz iść do sklepu. 787 00:33:48,050 --> 00:33:49,880 I udawać, że sklep jest tam. 788 00:33:49,880 --> 00:33:51,970 Więc co teraz potrzebuje - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Co musi się zdarzyć teraz? 790 00:33:53,400 --> 00:33:54,490 Projektu decyzji. 791 00:33:54,490 --> 00:33:56,825 Więc nie jest to zły instynkt, ale - jak masz na imię? 792 00:33:56,825 --> 00:33:57,090 >> PUBLICZNOŚCI: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID MALAN: David. 794 00:33:57,500 --> 00:33:58,810 Więc co David zrobić? 795 00:33:58,810 --> 00:34:02,590 Starał się coś w rodzaju naprawić dane Struktura i ruch od jego lokalizacji 796 00:34:02,590 --> 00:34:04,100 w dawnym miejscu Jake'a. 797 00:34:04,100 --> 00:34:06,740 I to jest w porządku, jeśli jesteśmy gotowi przyjąć, że jako 798 00:34:06,740 --> 00:34:08,199 Szczegóły realizacji. 799 00:34:08,199 --> 00:34:11,100 Ale najpierw niech aktualizacji danych struktury, zanim to zrobimy. 800 00:34:11,100 --> 00:34:14,139 Bo ja nie podoba się pomysł wszystko ludzie przesunięcie w tej linii. 801 00:34:14,139 --> 00:34:17,360 >> To nic wielkiego, jeśli David robi to z jeden krok, ale znowu, że z powrotem do 802 00:34:17,360 --> 00:34:20,360 kiedy miałem osiem wolontariuszy etap i zrobiliśmy jak wstawienia 803 00:34:20,360 --> 00:34:22,600 sort, gdzie mieliśmy zacząć przenoszenie wszystkich wokół. 804 00:34:22,600 --> 00:34:23,790 To ma drogie, prawda? 805 00:34:23,790 --> 00:34:28,330 To mnie lizać o Big O n, big O n kwadratu ponownie. 806 00:34:28,330 --> 00:34:30,650 To nie jest uczucie jak idealny wynik. 807 00:34:30,650 --> 00:34:32,080 >> Więc po prostu zaktualizować tego. 808 00:34:32,080 --> 00:34:35,120 Tak więc wielkość kolejki nie jest już 2. 809 00:34:35,120 --> 00:34:37,090 To teraz tylko 1. 810 00:34:37,090 --> 00:34:40,360 Ale mogę teraz zaktualizować coś I nie aktualizować przed, 811 00:34:40,360 --> 00:34:41,130 początku listy. 812 00:34:41,130 --> 00:34:45,420 Mogę tylko powiedzieć, jest to, że miejsce 1? 813 00:34:45,420 --> 00:34:49,770 Więc teraz mamy wartość śmieci tutaj, wartość śmieci tutaj, a David w 814 00:34:49,770 --> 00:34:51,469 Środek ten śmieci. 815 00:34:51,469 --> 00:34:54,980 Jednak struktura danych jest nadal w stanie nienaruszonym. 816 00:34:54,980 --> 00:34:58,540 >> I rzeczywiście, nie trzeba nawet zmiany były numer Jake'a 817 00:34:58,540 --> 00:35:00,460 9, bo kogo to obchodzi. 818 00:35:00,460 --> 00:35:04,470 Mam wystarczająco dużo informacji, obecnie w rozmiar, że wiem, że jest jedna osoba w 819 00:35:04,470 --> 00:35:05,030 ta kolejka. 820 00:35:05,030 --> 00:35:08,340 I wiem, że ta osoba jest na miejscu 1, nie 0. 821 00:35:08,340 --> 00:35:09,760 Nie liczę. 822 00:35:09,760 --> 00:35:11,300 Więc 1, jak również. 823 00:35:11,300 --> 00:35:13,410 Tak więc struktura danych jest nadal OK. 824 00:35:13,410 --> 00:35:14,330 >> Cóż, to, co dzieje się dalej? 825 00:35:14,330 --> 00:35:15,010 Miejmy enqueue - 826 00:35:15,010 --> 00:35:15,370 jak masz na imię? 827 00:35:15,370 --> 00:35:16,160 >> PUBLICZNOŚCI: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID MALAN: Callen. 829 00:35:16,580 --> 00:35:20,770 Miejmy enqueue się Callen i 22 jest teraz w kolejce. 830 00:35:20,770 --> 00:35:22,300 Więc teraz to, co musi się zmienić tutaj? 831 00:35:22,300 --> 00:35:24,380 Przód nie będzie zmienić, oczywiście. 832 00:35:24,380 --> 00:35:27,160 Rozmiar się nie zmieni się 2 ponownie. 833 00:35:27,160 --> 00:35:31,590 I 22 kończy się tutaj, 9 jest nadal obecny, ale skutecznie 834 00:35:31,590 --> 00:35:32,600 wartość śmieci teraz. 835 00:35:32,600 --> 00:35:35,910 To jest po prostu pozostałością przeszłości Jake. 836 00:35:35,910 --> 00:35:39,200 >> Więc teraz, co się stanie, jeśli I usunie z niej David? 837 00:35:39,200 --> 00:35:41,560 Jedna ostatnia operacja, Dequeue David. 838 00:35:41,560 --> 00:35:46,070 Możemy przesunąć, ale proponuję Chodźmy zrobić jak mało pracy, jak to możliwe. 839 00:35:46,070 --> 00:35:50,280 Teraz moja struktura danych idzie kopię wielkości od 2 do 1. 840 00:35:50,280 --> 00:35:53,730 Ale na początek kolejki teraz staje się 2. 841 00:35:53,730 --> 00:35:56,640 I nie ma potrzeby zmiany tych numerów jeszcze, bo są 842 00:35:56,640 --> 00:35:58,230 tylko wartości na śmieci. 843 00:35:58,230 --> 00:35:59,720 >> Ale teraz co się dzieje? 844 00:35:59,720 --> 00:36:03,280 Załóżmy, że enqueue siebie, 26? 845 00:36:03,280 --> 00:36:05,890 Czuję się jak ja należę tutaj. 846 00:36:05,890 --> 00:36:06,890 Jestem więc jest skolejkowany. 847 00:36:06,890 --> 00:36:08,760 Więc niby należą tutaj. 848 00:36:08,760 --> 00:36:11,300 I nawet jeśli nie bardzo Doceniam to wizualnie na scenie, 849 00:36:11,300 --> 00:36:15,075 bo mamy dużo miejsca, że ​​powinienem nie stać tutaj, dlaczego? 850 00:36:15,075 --> 00:36:16,290 >> PUBLICZNOŚCI: Jesteś poza granicami. 851 00:36:16,290 --> 00:36:16,370 >> DAVID MALAN: Racja. 852 00:36:16,370 --> 00:36:16,940 Jestem poza granicami. 853 00:36:16,940 --> 00:36:19,330 Mam indeksowane poza Granice tej tablicy. 854 00:36:19,330 --> 00:36:23,420 I naprawdę powinno być w jednym z trzy możliwe lokalizacje. 855 00:36:23,420 --> 00:36:25,150 Teraz, gdzie jest najbardziej naturalnym iść? 856 00:36:25,150 --> 00:36:27,760 I proponuję dźwignią tydzień jedna sztuczka. 857 00:36:27,760 --> 00:36:30,150 Operator mod, skuteczność. 858 00:36:30,150 --> 00:36:36,850 Bo jestem technicznie stoi na miejsce 3, ale ja 3 mod zdolności, 859 00:36:36,850 --> 00:36:40,250 tak 3, znak procent, 3 - 860 00:36:40,250 --> 00:36:40,970 pojemność to 3. 861 00:36:40,970 --> 00:36:41,720 Co to jest? 862 00:36:41,720 --> 00:36:43,700 Co jest w pozostałej, podzielić 3 przez 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Tak, że stawia mnie były Jake był, która jest w rzeczywistości dobra. 865 00:36:48,140 --> 00:36:50,370 Więc teraz realizacja z tego, co się dzieje w 866 00:36:50,370 --> 00:36:51,250 być trochę ból głowy. 867 00:36:51,250 --> 00:36:53,740 To naprawdę tylko jedna linia z bólem głowy, z kodem. 868 00:36:53,740 --> 00:36:56,580 Ale przynajmniej teraz nie śmieci wartość tutaj, ale jest dwa 869 00:36:56,580 --> 00:36:57,910 uzasadnione ints tutaj. 870 00:36:57,910 --> 00:37:04,160 I twierdzą, że teraz zrobiliśmy dokładnie to, co musimy zrobić, tak długo, jak długo 871 00:37:04,160 --> 00:37:08,600 możemy zmienić to, co Jake wartość miała być 26. 872 00:37:08,600 --> 00:37:12,110 >> Mamy już wystarczająco dużo informacji, nadal w celu zachowania integralności 873 00:37:12,110 --> 00:37:13,060 tej struktury danych. 874 00:37:13,060 --> 00:37:17,160 Wciąż jesteśmy rodzajem pecha, kiedy Aby wstawić sumie cztery lub więcej 875 00:37:17,160 --> 00:37:20,740 elementy, ale mogę przynajmniej zrobić całkiem efektywne wykorzystanie tej stałej 876 00:37:20,740 --> 00:37:21,740 Czas, w rzeczywistości. 877 00:37:21,740 --> 00:37:27,150 I nie trzeba się martwić o przesunięcie wszyscy, jak pochylenia Dawida było. 878 00:37:27,150 --> 00:37:30,816 >> Wszelkie pytania na stosy, czy ta kolejka? 879 00:37:30,816 --> 00:37:32,184 >> PUBLICZNOŚCI: Czy powodem trzeba rozmiar więc wiesz 880 00:37:32,184 --> 00:37:34,010 gdzie na osobę? 881 00:37:34,010 --> 00:37:34,770 >> DAVID MALAN: Dokładnie. 882 00:37:34,770 --> 00:37:38,230 I trzeba znać rozmiar tablicy bo muszę wiedzieć dokładnie, jak 883 00:37:38,230 --> 00:37:41,940 wiele z tych wartości są zgodne z prawem, i tak, że mogę dowiedzieć się, gdzie umieścić 884 00:37:41,940 --> 00:37:42,800 następna osoba. 885 00:37:42,800 --> 00:37:43,300 Dokładnie. 886 00:37:43,300 --> 00:37:44,580 Rozmiar jest - 887 00:37:44,580 --> 00:37:46,360 faktycznie, nie aktualizuje tego jeszcze. 888 00:37:46,360 --> 00:37:48,380 I dodaje się na 26. 889 00:37:48,380 --> 00:37:51,760 Rozmiar jest teraz, a nie 1, ale 2. 890 00:37:51,760 --> 00:37:57,780 Więc teraz to naprawdę pomaga mi znaleźć na początku listy, która nie jest 0, nie 891 00:37:57,780 --> 00:37:59,250 1, 2, lecz jest. 892 00:37:59,250 --> 00:38:01,665 Z przodu na liście to rzeczywiście numer 22. 893 00:38:01,665 --> 00:38:05,120 Bo przyszedł pierwszy, więc powinien on być dopuszczone do sklepu, zanim mnie 894 00:38:05,120 --> 00:38:08,780 choć wizualnie stoję bliżej do sklepu. 895 00:38:08,780 --> 00:38:09,220 >> Wszystko w porządku? 896 00:38:09,220 --> 00:38:12,410 Brawa dla tych facetów i damy je stamtąd. 897 00:38:12,410 --> 00:38:17,090 >> [APPLAUSE] 898 00:38:17,090 --> 00:38:18,150 >> DAVID MALAN: mogłem pozwolić trzymać tacę. 899 00:38:18,150 --> 00:38:20,760 Mogliśmy zobaczyć, co się stanie, jeśli chcesz, ale może nie. 900 00:38:20,760 --> 00:38:21,590 Dobrze. 901 00:38:21,590 --> 00:38:25,380 Więc co teraz nam pozostaje? 902 00:38:25,380 --> 00:38:28,900 Cóż, pozwól mi zaproponować, że nie Kilka innych struktur danych mogliśmy 903 00:38:28,900 --> 00:38:33,810 rozpocząć dodawanie do naszego zestawu narzędzi, które rzeczywiście być bardzo, bardzo istotne, ponieważ 904 00:38:33,810 --> 00:38:35,270 zagłębimy się rzeczy internetowej. 905 00:38:35,270 --> 00:38:38,150 Które znów ma jakieś połączenia z drzew w postaci 906 00:38:38,150 --> 00:38:40,550 coś, co nazywa DOM, dokument model obiektu. 907 00:38:40,550 --> 00:38:42,370 Ale zobaczymy więcej że przed długi. 908 00:38:42,370 --> 00:38:46,260 >> Pozwól mi zaproponować definicyjnie że zadzwoń drzewa teraz, co można wiedzieć, jak 909 00:38:46,260 --> 00:38:48,820 więcej drzewie rodzinnym, gdzie można posiada przodka w jakiś 910 00:38:48,820 --> 00:38:49,790 korzenie drzewa. 911 00:38:49,790 --> 00:38:54,480 Patriarchalny lub macierz w górze drzewa. 912 00:38:54,480 --> 00:38:56,700 Bez ich małżonków, w tym przypadku. 913 00:38:56,700 --> 00:39:00,940 Ale teraz mamy to, co my nazywamy dzieci, które są węzły, które wiszą 914 00:39:00,940 --> 00:39:05,480 od lewej dziecka lub dziecka prawej, strzałki, jak przedstawione tutaj. 915 00:39:05,480 --> 00:39:10,490 >> Innymi słowy, w strukturze danych drzewa w komputerze, drzewo ma wartość zero 916 00:39:10,490 --> 00:39:11,480 lub więcej węzłów. 917 00:39:11,480 --> 00:39:13,500 Jeżeli ma ona co najmniej jeden węzeł to się nazywa główny. 918 00:39:13,500 --> 00:39:15,700 To rzeczy, które wizualnie zwracamy na szczycie. 919 00:39:15,700 --> 00:39:20,280 I że węzeł, jak każdy inny węzeł, może mieć zero, jeden lub dwa, lub trzy, 920 00:39:20,280 --> 00:39:23,600 lub jednak wiele dzieci Struktura danych obsługuje. 921 00:39:23,600 --> 00:39:29,150 W tym przypadku, główny, przechowywania wartość jeden, ma dwoje dzieci, 2 i 3, 922 00:39:29,150 --> 00:39:33,020 więc ogólnie nazywamy 2 lewy dziecko i 3 prawa dziecka. 923 00:39:33,020 --> 00:39:36,940 >> A potem, kiedy zabieram się do 5, 6, i 7, 6 można nazwać średnim dzieckiem. 924 00:39:36,940 --> 00:39:38,940 Jeśli masz czworo dzieci, robi się mylące. 925 00:39:38,940 --> 00:39:42,260 Więc przestać używać tego rodzaju od skrótu ustnie. 926 00:39:42,260 --> 00:39:44,580 Ale to naprawdę tylko drzewo genealogiczne. 927 00:39:44,580 --> 00:39:48,880 A liście są tu węzłów, które sami nie mają dzieci. 928 00:39:48,880 --> 00:39:52,540 Wiszą off dno drzewo. 929 00:39:52,540 --> 00:39:56,940 >> Więc jak możemy zaimplementować drzewo, które ma tylko dwa dzieci maksymalnie? 930 00:39:56,940 --> 00:39:58,410 Nazwijmy to drzewo binarne. 931 00:39:58,410 --> 00:40:00,960 Bi ponownie, co oznacza, dwa, w tym przypadek, jak z binarnym. 932 00:40:00,960 --> 00:40:04,830 I tak może mieć zero, jeden, lub dwoje dzieci maksymalnie. 933 00:40:04,830 --> 00:40:08,650 >> Ja proponuję wdrażamy węzeł do tej struktury z int n, 934 00:40:08,650 --> 00:40:11,910 a następnie dwa wskaźniki, jeden o nazwie w lewo, jeden nazywa się prawo. 935 00:40:11,910 --> 00:40:14,830 Ale to są tylko ładne arbitralne konwencje. 936 00:40:14,830 --> 00:40:18,170 I co miło teraz, zwłaszcza jeśli niby walczyli koncepcyjnie z 937 00:40:18,170 --> 00:40:21,300 rekurencji, albo myśli, że to nie było naprawdę rozwiązanie do niczego, 938 00:40:21,300 --> 00:40:23,120 zwłaszcza jeśli można zabraknie pamięci. 939 00:40:23,120 --> 00:40:26,600 Teraz, gdy mówimy o danych Struktury i algorytmy, które pozwalają 940 00:40:26,600 --> 00:40:31,030 nam przemierzać i manipulować nimi, Okazuje się, że rekurencja wraca 941 00:40:31,030 --> 00:40:34,240 znacznie bardziej atrakcyjne jeśli nie piękny sposób. 942 00:40:34,240 --> 00:40:38,670 >> Więc proponuję, jest realizacja z funkcji wyszukiwania. 943 00:40:38,670 --> 00:40:39,870 Biorąc pod uwagę dwa wejścia - 944 00:40:39,870 --> 00:40:41,570 więc myślę o tym jako czarna skrzynka. 945 00:40:41,570 --> 00:40:46,560 Biorąc pod uwagę dwa wejścia, n, int i wskaźnik do drzewa, wskaźnik do 946 00:40:46,560 --> 00:40:50,020 węzeł, czy naprawdę korzeń drzewa, I Twierdzenie, że funkcja ta może powrócić 947 00:40:50,020 --> 00:40:53,530 prawda czy fałsz, że wartość n jest w środku tego drzewa. 948 00:40:53,530 --> 00:40:55,210 >> Co jest w środku tej czarnej skrzynki? 949 00:40:55,210 --> 00:40:57,440 Cóż, cztery oddziały. 950 00:40:57,440 --> 00:40:58,385 Najpierw po prostu sprawdza. 951 00:40:58,385 --> 00:41:00,490 Jeśli drzewo jest null, po prostu return false. 952 00:41:00,490 --> 00:41:04,580 Jeśli nie ma węzła, nie ma n, nie ma wiele, po prostu zwraca wartość false. 953 00:41:04,580 --> 00:41:12,330 Jeśli jednak, n, wartość szukasz na, jest mniej niż drzewa strzałki n, a 954 00:41:12,330 --> 00:41:15,180 żeby było jasne, co to znaczy, kiedy Piszę drzewo, a następnie strzałki 955 00:41:15,180 --> 00:41:18,150 zapis, n? 956 00:41:18,150 --> 00:41:18,690 Dokładnie. 957 00:41:18,690 --> 00:41:21,970 Oznacza to, że Dereferencjuj wskaźnik nazywa drzewo. 958 00:41:21,970 --> 00:41:26,750 Idź tam, a następnie dostać się do środka tego węzeł i uzyskać jego pole o nazwie n. 959 00:41:26,750 --> 00:41:30,810 , A następnie porównać rzeczywiste n, który był przeszedł do wyszukiwania przeciw nim. 960 00:41:30,810 --> 00:41:35,390 >> Więc jeśli n jest mniejsza od wartości n w węźle drzewa sam, dobrze, 961 00:41:35,390 --> 00:41:36,720 co to znaczy? 962 00:41:36,720 --> 00:41:40,690 Oznacza to, że nic na pierwszy rzut oka. 963 00:41:40,690 --> 00:41:40,900 Prawda? 964 00:41:40,900 --> 00:41:45,560 Podobnie jak wtedy, gdy masz tablicę wartości, które warto stosować binarne 965 00:41:45,560 --> 00:41:48,290 sprawdzić jako forma podziału i podbić. 966 00:41:48,290 --> 00:41:51,790 Ale co z założenia nie musimy mieć dla wyszukiwania binarnego do pracy na wszystkich 967 00:41:51,790 --> 00:41:54,510 w książce telefonicznej i Wcześniejsze przykłady? 968 00:41:54,510 --> 00:41:55,530 >> Jak być sortowane. 969 00:41:55,530 --> 00:41:59,490 Warto więc uściślić definicję drzewa tu nie być tylko drzewa, które mogą 970 00:41:59,490 --> 00:42:00,880 mieć dowolną liczbę dzieci. 971 00:42:00,880 --> 00:42:04,700 Nie tylko drzewo binarne, które mogą mieć 0, 1 lub 2 maksymalnie. 972 00:42:04,700 --> 00:42:09,700 Ale jako binarne drzewo wyszukiwania lub BST, który jest tylko fantazyjny sposób na powiedzenie 973 00:42:09,700 --> 00:42:15,430 drzewo binarne, takie, że każdy węzeł-tych lewej dziecko, jeśli jest obecny, jest 974 00:42:15,430 --> 00:42:16,830 poniżej węzła. 975 00:42:16,830 --> 00:42:20,170 I każdy węzeł ma rację dziecko, Jeśli występuje, jest większa 976 00:42:20,170 --> 00:42:21,740 od samego węzła. 977 00:42:21,740 --> 00:42:25,200 >> Więc innymi słowy, jeśli było wyciągnąć z drzewa, wszystkie numery są 978 00:42:25,200 --> 00:42:30,620 starannie wyważone, jak to tak, że jeśli masz 55 jako główny, 33 może pójść 979 00:42:30,620 --> 00:42:33,090 po jego lewej stronie, ponieważ jest to mniej niż 55. 980 00:42:33,090 --> 00:42:36,430 77 może iść do swojego prawa, ponieważ jest większa niż 55. 981 00:42:36,430 --> 00:42:40,750 Teraz jednak zauważyć, tę samą definicję, jest rekurencyjna definicja ustnie, 982 00:42:40,750 --> 00:42:42,600 ma zastosowanie do 33. 983 00:42:42,600 --> 00:42:47,610 33 w lewo dziecko musi być mniejsza niż to, i prawa dziecka 33-tych, 44, musi być 984 00:42:47,610 --> 00:42:48,580 większe niż to. 985 00:42:48,580 --> 00:42:51,670 >> Więc to jest drzewo binarne wyszukiwanie i Proponuję, używając trochę 986 00:42:51,670 --> 00:42:53,910 rekurencja, możemy teraz znaleźć n. 987 00:42:53,910 --> 00:42:59,160 Tak więc, jeśli n jest mniejsza od wartości n, który jest bieżący węzeł, zamierzam iść 988 00:42:59,160 --> 00:43:04,090 dalej i punt, że tak powiem, i po prostu zwrotu tego, co odpowiedź jest 989 00:43:04,090 --> 00:43:08,470 szukając n na lewa dziecko drzewa. 990 00:43:08,470 --> 00:43:11,370 Wskazówka ponownie, ta funkcja po prostu oczekuje węzła STAR 991 00:43:11,370 --> 00:43:12,780 wskaźnik do węzła. 992 00:43:12,780 --> 00:43:17,360 Więc pewnie po prostu może zrobić drzewo strzałka w lewo, co doprowadzi 993 00:43:17,360 --> 00:43:18,400 mnie do innego węzła. 994 00:43:18,400 --> 00:43:19,480 Ale to, co jest, że węzeł? 995 00:43:19,480 --> 00:43:22,820 >> Cóż, według tej deklaracji, w lewo jest tylko wskaźnik, tak, że tylko 996 00:43:22,820 --> 00:43:27,090 Oznacza to, ja przechodząc do funkcji wyszukiwania inny wskaźnik, a mianowicie 997 00:43:27,090 --> 00:43:30,750 który reprezentuje Moja lewa dziecka drzewo. 998 00:43:30,750 --> 00:43:36,040 Tak więc, w tym przypadku, wskaźnik 33, jeśli to jest nasz wkład próbka Tymczasem, jeśli 999 00:43:36,040 --> 00:43:40,740 n jest większe niż wartość n na bieżący węzeł w drzewie, to ja jestem 1000 00:43:40,740 --> 00:43:43,370 zamiar iść do przodu i punt w innych kierunek i po prostu powiedzieć, nie wiem 1001 00:43:43,370 --> 00:43:47,280 wiem, czy to n wartość jest w drzewie, ale wiem, że jeśli tak jest, to w dół my 1002 00:43:47,280 --> 00:43:49,090 Prawo oddziału, że tak powiem. 1003 00:43:49,090 --> 00:43:53,120 Więc pozwól mi zadzwonić rekursywnie sprawdzić, przechodząc n ponownie, ale przechodząc w 1004 00:43:53,120 --> 00:43:54,580 wskaźnik do mojej prawej dziecka. 1005 00:43:54,580 --> 00:44:00,020 >> Innymi słowy, jeśli jestem obecnie w 55 i szukam 99, wiem, że 99 1006 00:44:00,020 --> 00:44:04,270 jest większa niż 55, więc jak wyrwałem książki telefonicznej tygodnie temu, a my 1007 00:44:04,270 --> 00:44:07,140 poszedł w prawo, podobnie jesteśmy zamiar iść tutaj. 1008 00:44:07,140 --> 00:44:11,960 A ja nie wiem, czy to jest w mojej prawej stronie dziecko, i to nie jest, 77 ma, ale 1009 00:44:11,960 --> 00:44:13,210 Wiem, że to w tym kierunku. 1010 00:44:13,210 --> 00:44:18,770 Więc wzywam wyszukiwania na prawym dzieckiem 77, i niech się z postać wyszukiwania 1011 00:44:18,770 --> 00:44:24,950 tam, jeśli 99 w tym arbitralne Przykładem jest faktycznie istnieje. 1012 00:44:24,950 --> 00:44:26,900 >> Else, co jest ostateczna sprawa? 1013 00:44:26,900 --> 00:44:28,620 Jeśli drzewo jest null to jedna sprawa. 1014 00:44:28,620 --> 00:44:31,890 Jeśli n jest mniejsza niż obecna węzła wartość jest inna sprawa. 1015 00:44:31,890 --> 00:44:35,120 Jeśli n jest większe niż prąd wartość węzła jest trzeci przypadek. 1016 00:44:35,120 --> 00:44:38,250 Co czwarty i ostatni przypadek? 1017 00:44:38,250 --> 00:44:39,480 Myślę, że jesteśmy z przypadków, prawda? 1018 00:44:39,480 --> 00:44:44,690 To musi być to, że n jest bieżący węzeł, że jestem na. 1019 00:44:44,690 --> 00:44:49,640 >> Jeśli więc szukam 55 w tym momencie w historii, że oddział 1020 00:44:49,640 --> 00:44:51,780 drzewo wróci prawda. 1021 00:44:51,780 --> 00:44:55,380 Więc co ciekawe jest to, że my rzeczywiście, w przeciwieństwie tydzień przeszłości, my niby 1022 00:44:55,380 --> 00:44:56,740 o dwie podstawowe sprawy. 1023 00:44:56,740 --> 00:44:58,300 A oni nie mają do Wszystkie się na szczycie. 1024 00:44:58,300 --> 00:45:01,390 Top jest wariant podstawowy, ponieważ jeśli Drzewo jest null, nie ma nic do zrobienia. 1025 00:45:01,390 --> 00:45:03,410 Wystarczy wrócić zakodowanego wartość false. 1026 00:45:03,410 --> 00:45:07,400 >> Oddział dno jest rodzaj domyślnie, przy czym jeśli mamy sprawdzone 1027 00:45:07,400 --> 00:45:11,550 null, sprawdziliśmy, czy powinien on być lewo, ale nie powinny być, mamy 1028 00:45:11,550 --> 00:45:14,640 sprawdzić, czy powinno być w porządku, ale to Nie powinny być wyraźnie, że musi być 1029 00:45:14,640 --> 00:45:15,870 tu, gdzie jesteśmy. 1030 00:45:15,870 --> 00:45:16,780 To wariant podstawowy. 1031 00:45:16,780 --> 00:45:19,920 Więc nie dwa przypadki rekurencyjne umieszczona jest w środku. 1032 00:45:19,920 --> 00:45:21,630 Ale mogę napisać To, w dowolnej kolejności. 1033 00:45:21,630 --> 00:45:24,520 Pomyślałem, że to niby się czymś naturalnym najpierw sprawdzić ewentualnego błędu, 1034 00:45:24,520 --> 00:45:28,340 następnie sprawdzić w lewo, a następnie sprawdzić w prawo, a następnie Zakładam, że jesteś w węźle 1035 00:45:28,340 --> 00:45:30,630 jesteś rzeczywiście szukają. 1036 00:45:30,630 --> 00:45:36,240 >> Więc dlaczego może to być przydatne? 1037 00:45:36,240 --> 00:45:37,910 Okazuje się - 1038 00:45:37,910 --> 00:45:42,110 i pozwól mi przejść do teaser tutaj, że jest w internecie. 1039 00:45:42,110 --> 00:45:44,920 Zamierzamy rozpocząć korzystanie nie języka programowania na początku, ale 1040 00:45:44,920 --> 00:45:46,030 język znaczników. 1041 00:45:46,030 --> 00:45:48,740 Język znaczników jest jeden, który jest w duchu podobnym do programowania 1042 00:45:48,740 --> 00:45:51,715 język, ale to nie daje zdolność do wyrażania siebie logicznie. 1043 00:45:51,715 --> 00:45:55,070 To tylko daje możliwość wyrazić siebie strukturalnie. 1044 00:45:55,070 --> 00:45:57,960 >> Gdzie chcesz umieścić coś na stronie, strona internetowa? 1045 00:45:57,960 --> 00:45:59,200 Jaki kolor chcesz to zrobić? 1046 00:45:59,200 --> 00:46:00,950 Jaki rozmiar czcionki chcesz to zrobić? 1047 00:46:00,950 --> 00:46:02,970 Jakie słowa czy rzeczywiście chcesz na stronie internetowej? 1048 00:46:02,970 --> 00:46:04,060 Więc to jest język znaczników. 1049 00:46:04,060 --> 00:46:07,690 Ale my bardzo szybko wprowadzić JavaScript, który jest pełnoprawnym 1050 00:46:07,690 --> 00:46:08,560 język programowania. 1051 00:46:08,560 --> 00:46:12,530 Bardzo podobny z wyglądu składniowo do C, ale to jedne 1052 00:46:12,530 --> 00:46:15,200 ładny, mocniejszy, bardziej przyjaznych dla użytkownika funkcji. 1053 00:46:15,200 --> 00:46:18,050 >> I jeden z frustracji na to punkt w semestrze jest to, że my będziemy 1054 00:46:18,050 --> 00:46:22,065 szybko wdrożyć Speller w znacznie mniej linii kodu przy użyciu innych językach 1055 00:46:22,065 --> 00:46:25,580 niż C sobie pozwala, ale za przyczyną tych niedługo zrozumieć. 1056 00:46:25,580 --> 00:46:27,750 To będzie pierwsza taka strona. 1057 00:46:27,750 --> 00:46:30,120 To będzie całkowicie rozczarowująca, Pierwszy z nich robimy. 1058 00:46:30,120 --> 00:46:31,400 Będzie to po prostu powiedzieć, hello world. 1059 00:46:31,400 --> 00:46:34,010 Ale jeśli nigdy nie widziałem go Zanim to jest HTML 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Jeśli pójdziesz do pewnej opcji menu w Najbardziej dowolnej przeglądarki, na dowolnej stronie internetowej na 1062 00:46:39,310 --> 00:46:43,160 internet, można zobaczyć, HTML że niektórzy ludzie napisali do 1063 00:46:43,160 --> 00:46:44,400 tworzenia tej strony. 1064 00:46:44,400 --> 00:46:47,850 I to chyba nie wygląda tak krótkie lub jako czysty jak ten. 1065 00:46:47,850 --> 00:46:51,400 Ale będzie to zgodne z wzorcem z nich otwarte wsporniki i tnie i 1066 00:46:51,400 --> 00:46:53,660 Litery i ewentualnie numery. 1067 00:46:53,660 --> 00:46:56,770 >> Myślałam, że dam wam teaser z tego, co będzie można zrobić 1068 00:46:56,770 --> 00:46:57,950 po zrobieniu CS50. 1069 00:46:57,950 --> 00:47:02,620 Pozwólcie mi odejść do cs.harvard.edu / rob, strona główna nasze własne Roba Bowdena. 1070 00:47:02,620 --> 00:47:06,080 Zrobił to za nas. 1071 00:47:06,080 --> 00:47:07,490 Tak więc wkrótce będziesz w stanie tego zrobić. 1072 00:47:07,490 --> 00:47:10,660 A także, co usłyszałeś rano - 1073 00:47:10,660 --> 00:47:12,480 co słyszałeś to rano - 1074 00:47:12,480 --> 00:47:13,780 >> [CHOMIK MUSIC DANCE] 1075 00:47:13,780 --> 00:47:15,702 >> - Przychodzą w stanie dokonać tego. 1076 00:47:15,702 --> 00:47:16,790 To nas czeka w środę. 1077 00:47:16,790 --> 00:47:17,791 Będziemy zobaczenia. 1078 00:47:17,791 --> 00:47:22,950 >> [CHOMIK MUSIC DANCE] 1079 00:47:22,950 --> 00:47:24,300 DAVID MALAN: Na następnym CS50 - 1080 00:47:24,300 --> 00:47:31,670