1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:11,137 [MUZYKA GRA] 3 00:00:11,137 --> 00:00:12,220 David J. MALAN: Wszystko w porządku. 4 00:00:12,220 --> 00:00:13,950 To CS50. 5 00:00:13,950 --> 00:00:18,560 To jest tydzień pięć kontynuowane, a my dobre wieści i złe wieści. 6 00:00:18,560 --> 00:00:21,140 Więc dobrą wiadomością jest to, że CS50 uruchamia w ten piątek. 7 00:00:21,140 --> 00:00:24,430 Jeśli chcesz do nas dołączyć, udać się do zwykłej zawartości tutaj. 8 00:00:24,430 --> 00:00:28,670 Nawet lepsze wiadomości, nie wykład w najbliższy poniedziałek 13. 9 00:00:28,670 --> 00:00:31,970 Nieco mniej lepsze wieści, Quiz zero środę. 10 00:00:31,970 --> 00:00:33,840 Więcej informacji można znaleźć pod tym adresem URL tutaj. 11 00:00:33,840 --> 00:00:36,340 A w ciągu najbliższych kilku dni będziemy wypełnienie luki 12 00:00:36,340 --> 00:00:39,234 w odniesieniu do pomieszczeń które mamy zastrzeżone. 13 00:00:39,234 --> 00:00:41,400 Lepsze jest to, że nie będzie jest ocena całego kursu 14 00:00:41,400 --> 00:00:43,570 Sesja ta nadchodzi Poniedziałek wieczorem. 15 00:00:43,570 --> 00:00:46,270 Stay tuned się oczywiście na strona lokalizacji i szczegółów. 16 00:00:46,270 --> 00:00:49,290 Działy, nawet jeśli jest wakacje, spotka się również, jak również. 17 00:00:49,290 --> 00:00:50,490 18 00:00:50,490 --> 00:00:52,940 Najlepszą wiadomością, wykład w następny piątek. 19 00:00:52,940 --> 00:00:56,220 Tak to jest, że tradycja mają, zgodnie z programem szkolenia. 20 00:00:56,220 --> 00:00:58,100 Tylko-- to będzie niesamowite. 21 00:00:58,100 --> 00:01:02,510 Będzie można zobaczyć takie rzeczy jak Stała czasu struktury danych 22 00:01:02,510 --> 00:01:04,730 i tabele mieszania i drzewa i próbuje. 23 00:01:04,730 --> 00:01:07,150 I porozmawiamy o problemach urodziny. 24 00:01:07,150 --> 00:01:09,440 Cała masa rzeczy czeka na następny piątek. 25 00:01:09,440 --> 00:01:11,212 26 00:01:11,212 --> 00:01:12,200 OK. 27 00:01:12,200 --> 00:01:13,190 Tak czy inaczej. 28 00:01:13,190 --> 00:01:17,080 >> Więc przypomnieć, że byliśmy koncentrując się na tym obrazie, co jest 29 00:01:17,080 --> 00:01:18,980 wewnątrz pamięci naszego komputera. 30 00:01:18,980 --> 00:01:22,875 Więc pamięci lub pamięci RAM jest gdzie programy istnieć gdy jesteś ich prowadzenie. 31 00:01:22,875 --> 00:01:25,215 Po dwukrotnym kliknięciu ikonę, aby uruchomić jakiś program 32 00:01:25,215 --> 00:01:27,520 lub kliknij dwukrotnie ikonę, aby otworzyć jakiś plik, 33 00:01:27,520 --> 00:01:30,430 to ładowane z dysku dysk lub dysk SSD 34 00:01:30,430 --> 00:01:34,190 do pamięci RAM, Random Access Memory, gdzie żyje, aż do wyłączenia zasilania, 35 00:01:34,190 --> 00:01:36,700 Pokrywa zamyka laptopa, lub zamknięciu programu. 36 00:01:36,700 --> 00:01:38,960 >> Teraz, pamięci, z które prawdopodobnie masz 37 00:01:38,960 --> 00:01:41,950 1 gigabajt te dni, 2 GB lub nawet znacznie bardziej, 38 00:01:41,950 --> 00:01:44,420 jest ogólnie określone dla danego programu 39 00:01:44,420 --> 00:01:47,170 w tego rodzaju prostokątnym model koncepcyjny 40 00:01:47,170 --> 00:01:50,860 przy czym to ma na dole stosu i kilka innych rzeczy na górze. 41 00:01:50,860 --> 00:01:53,140 Rzeczą na samym szczycie widzieliśmy na tym zdjęciu 42 00:01:53,140 --> 00:01:55,670 wcześniej, ale nigdy nie mówił o jest tak zwany segmentu tekstu. 43 00:01:55,670 --> 00:01:58,419 Segment tekst jest po prostu fantazyjny sposób mówić do zer i jedynek, które 44 00:01:58,419 --> 00:02:01,150 skomponuj swój rzeczywisty skompilowany program. 45 00:02:01,150 --> 00:02:03,910 >> Więc po dwukrotnym kliknięciem Microsoft Word na komputerze Mac lub PC, 46 00:02:03,910 --> 00:02:08,030 lub po uruchomieniu kropkę na slash Mario Komputer Linux w oknie terminala, 47 00:02:08,030 --> 00:02:12,460 zera i jedynki, które tworzą Słowo lub Mario są przechowywane tymczasowo 48 00:02:12,460 --> 00:02:16,610 w pamięci RAM komputera w tzw Segment tekstu dla danego programu. 49 00:02:16,610 --> 00:02:19,080 Poniżej w polu zainicjowany i dane niezainicjalizowane. 50 00:02:19,080 --> 00:02:22,655 To rzeczy, jak zmienne globalne, że nie używałem wielu, 51 00:02:22,655 --> 00:02:24,910 ale od czasu do czasu mamy miał zmienne globalne 52 00:02:24,910 --> 00:02:28,819 lub statycznie zdefiniowane ciągi jest mocno zakodowane słowa takie jak "cześć" 53 00:02:28,819 --> 00:02:31,860 nie są pobierane z użytkownikiem , które są zakodowane w programie. 54 00:02:31,860 --> 00:02:34,230 >> Teraz, na dole mamy mają tak zwany stos. 55 00:02:34,230 --> 00:02:37,665 I stos, do tej pory, już używając do jakiego rodzaju celów? 56 00:02:37,665 --> 00:02:39,706 57 00:02:39,706 --> 00:02:40,997 Co stos używane do? 58 00:02:40,997 --> 00:02:41,160 Tak? 59 00:02:41,160 --> 00:02:42,070 >> WIDOWNI: Funkcje. 60 00:02:42,070 --> 00:02:43,320 >> David J. MALAN: Dla funkcji? 61 00:02:43,320 --> 00:02:44,980 W jakim sensie do funkcji? 62 00:02:44,980 --> 00:02:48,660 >> PUBLICZNOŚCI: Po wywołaniu funkcji, Argumenty są kopiowane na stos. 63 00:02:48,660 --> 00:02:49,660 >> David J. MALAN: Dokładnie. 64 00:02:49,660 --> 00:02:52,650 Podczas wywołania funkcji, jej Argumenty są kopiowane na stos. 65 00:02:52,650 --> 00:02:56,330 Więc wszelkie X lub Y jest w lub na lub B które przekazujemy do funkcji 66 00:02:56,330 --> 00:02:58,680 są tymczasowo umieścić na tak zwany stos, 67 00:02:58,680 --> 00:03:02,000 tak jak jednym Annenberg tace jadalni, a także rzeczy 68 00:03:02,000 --> 00:03:03,190 jak zmienne lokalne. 69 00:03:03,190 --> 00:03:06,290 Jeśli funkcja foo lub Twój Swap Funkcja ma zmienne lokalne, 70 00:03:06,290 --> 00:03:08,602 jak temp, te dwa kończy się na stosie. 71 00:03:08,602 --> 00:03:11,560 Teraz, nie będziemy mówić zbyt wiele o je, ale te zmienne środowiskowe 72 00:03:11,560 --> 00:03:15,690 na dole widzieliśmy jakiś czas temu, kiedy Byłem futzing na klawiaturze jeden dzień 73 00:03:15,690 --> 00:03:20,050 i zacząłem dostępu rzeczy jak argv 100 lub argv 1000, 74 00:03:20,050 --> 00:03:22,320 tylko elements-- zapomnę numbers-- ale 75 00:03:22,320 --> 00:03:24,330 nie miały być dostępne dla mnie. 76 00:03:24,330 --> 00:03:26,581 Zaczęliśmy widząc niektóre Funky symbole na ekranie. 77 00:03:26,581 --> 00:03:28,330 Były to tak zwane Zmienne środowiskowe 78 00:03:28,330 --> 00:03:32,390 jak dla moich ustawień globalnych program lub na moim komputerze, a nie 79 00:03:32,390 --> 00:03:37,090 niezwiązane z ostatnich błędów, które omówiliśmy, 80 00:03:37,090 --> 00:03:39,670 ShellShock, że było dręczące sporo komputerów. 81 00:03:39,670 --> 00:03:42,960 >> Teraz wreszcie, w dzisiejszym centrum uwagi my ostatecznie na stercie. 82 00:03:42,960 --> 00:03:44,864 To kolejny fragment pamięci. 83 00:03:44,864 --> 00:03:47,030 I to zasadniczo wszystkie pamięci jest taki sam materiał. 84 00:03:47,030 --> 00:03:48,040 To ten sam sprzęt. 85 00:03:48,040 --> 00:03:49,956 Jesteśmy po prostu rodzaj leczenia różnych klastrów 86 00:03:49,956 --> 00:03:51,460 bajtów do różnych celów. 87 00:03:51,460 --> 00:03:56,540 Kupa jest również, gdzie będzie zmienne i pamięci, że poprosisz 88 00:03:56,540 --> 00:03:58,810 od systemu operacyjnego są tymczasowo przechowywane. 89 00:03:58,810 --> 00:04:01,890 >> Ale jest to za błąd Tutaj jako obraz oznacza. 90 00:04:01,890 --> 00:04:05,261 Jesteśmy jakby mieć dwa zwykle około zderzają. 91 00:04:05,261 --> 00:04:08,010 Bo jak użyć bardziej stosu, i jak widzimy dzisiaj 92 00:04:08,010 --> 00:04:11,800 dalej, jak używać coraz więcej kupa, na pewno złe rzeczy mogą się zdarzyć. 93 00:04:11,800 --> 00:04:15,054 I rzeczywiście, że możemy wywoływać umyślnie lub nieumyślnie. 94 00:04:15,054 --> 00:04:16,970 Więc na cliffhanger ostatniego Czas był ten program, 95 00:04:16,970 --> 00:04:20,570 które nie służą wszelkie funkcjonalne celów innych niż w celu wykazania 96 00:04:20,570 --> 00:04:24,750 jak cię jak zły może rzeczywiście wziąć Zaletą błędów w czyimś programu 97 00:04:24,750 --> 00:04:28,460 i przejąć program lub nawet Cały system komputerowy lub serwer. 98 00:04:28,460 --> 00:04:31,660 Więc po prostu spojrzeć na krótko, ci zauważyć, że główny na dole 99 00:04:31,660 --> 00:04:34,510 odbywa się w linii poleceń argumenty, jak na argv. 100 00:04:34,510 --> 00:04:38,480 I ma połączenie z funkcji f, zasadniczo bezimienny funkcja o nazwie 101 00:04:38,480 --> 00:04:40,250 f, a to przechodząc w argv [1]. 102 00:04:40,250 --> 00:04:43,960 >> Więc cokolwiek słowo użytkownik wpisze w szybka po nazwie tego programu, 103 00:04:43,960 --> 00:04:49,310 , a następnie do tego dowolną funkcją Najwięcej, f, odbywa się w ciągu, AKA char *, 104 00:04:49,310 --> 00:04:51,720 jak zaczęliśmy dyskutować, i to właśnie nazywa to "bar". 105 00:04:51,720 --> 00:04:53,310 Ale możemy nazwać to coś. 106 00:04:53,310 --> 00:04:57,470 A następnie oświadcza, wewnątrz f, szereg znaków 107 00:04:57,470 --> 00:04:59,930 nazywa C-- 12 takich znaków. 108 00:04:59,930 --> 00:05:03,580 >> Teraz, przez historię mówiłem chwilą, gdy w pamięci 109 00:05:03,580 --> 00:05:06,720 jest c, to te 12 lub znaki skończy? 110 00:05:06,720 --> 00:05:07,570 Wystarczy być jasne. 111 00:05:07,570 --> 00:05:08,070 Tak? 112 00:05:08,070 --> 00:05:08,590 >> PUBLICZNOŚCI: Na stosie. 113 00:05:08,590 --> 00:05:09,420 >> David J. MALAN: Na stosie. 114 00:05:09,420 --> 00:05:10,720 Więc c jest zmienną lokalną. 115 00:05:10,720 --> 00:05:14,079 Pytamy do 12 znaków lub 12 bajtów. 116 00:05:14,079 --> 00:05:16,120 Te będą się kończyć na tak zwanym stosu. 117 00:05:16,120 --> 00:05:18,530 Teraz w końcu jest to inna funkcja to rzeczywiście bardzo przydatne, 118 00:05:18,530 --> 00:05:20,571 ale nie zostały rzeczywiście wykorzystane to sami, strncopy. 119 00:05:20,571 --> 00:05:21,550 120 00:05:21,550 --> 00:05:25,200 Oznacza to, kopię ciąg, ale tylko litery n, n znaków. 121 00:05:25,200 --> 00:05:31,990 Tak będzie n znaków skopiowane z baru do c. 122 00:05:31,990 --> 00:05:32,980 I ile? 123 00:05:32,980 --> 00:05:34,110 Długość paska. 124 00:05:34,110 --> 00:05:36,330 Tak więc, innymi słowy, że jedna linia, strncopy, 125 00:05:36,330 --> 00:05:39,500 ma zamiar skopiować skutecznie bar w na c. 126 00:05:39,500 --> 00:05:42,340 >> Teraz, po prostu rodzaj przewidywania Morał z tej historii, 127 00:05:42,340 --> 00:05:44,750 co tu jest potencjalnie problematyczne? 128 00:05:44,750 --> 00:05:49,710 Mimo, że mamy do sprawdzania długości z barem i przekazania go do strncopy, 129 00:05:49,710 --> 00:05:53,145 Jaki jest Twój gut mówi Ci to wciąż podzielone na temat tego programu? 130 00:05:53,145 --> 00:05:54,410 131 00:05:54,410 --> 00:05:55,220 Tak? 132 00:05:55,220 --> 00:05:57,491 >> PUBLICZNOŚCI: Nie obejmuje Pokój na znak null. 133 00:05:57,491 --> 00:05:59,990 David J. MALAN: Nie obejmuje Pokój na znak null. 134 00:05:59,990 --> 00:06:02,073 Potencjalnie przeciwieństwie dotychczasowa praktyka nie mamy nawet 135 00:06:02,073 --> 00:06:04,810 mają tyle jako plus 1 do przyjąć, że znak null. 136 00:06:04,810 --> 00:06:06,649 Ale jest jeszcze gorzej. 137 00:06:06,649 --> 00:06:07,940 Co jeszcze mamy nie robiąc? 138 00:06:07,940 --> 00:06:08,432 Tak? 139 00:06:08,432 --> 00:06:09,307 >> PUBLICZNOŚCI: [niesłyszalne] 140 00:06:09,307 --> 00:06:15,440 141 00:06:15,440 --> 00:06:16,440 David J. MALAN: Perfect. 142 00:06:16,440 --> 00:06:18,490 Mamy 12 bardzo ciężko kodowane arbitralnie. 143 00:06:18,490 --> 00:06:19,497 144 00:06:19,497 --> 00:06:21,330 To nie jest tak dużo problemem, ale fakt, 145 00:06:21,330 --> 00:06:25,630 że nie jesteśmy nawet sprawdzenie, czy Długość paska jest mniejsza niż 12 146 00:06:25,630 --> 00:06:28,530 w tym przypadku będzie bezpiecznie umieścić w pamięci 147 00:06:28,530 --> 00:06:30,260 nazywa c, że mamy przydzielone. 148 00:06:30,260 --> 00:06:32,960 W rzeczywistości, jeżeli pasek jest podobny 20 znaków, 149 00:06:32,960 --> 00:06:39,010 Funkcja ta wydaje się kopiowanie 20 znaków z baru na C, a tym samym 150 00:06:39,010 --> 00:06:41,310 przy co najmniej 8 bajtów które nie powinny być. 151 00:06:41,310 --> 00:06:42,690 To jest implikacja tutaj. 152 00:06:42,690 --> 00:06:44,347 >> Tak w skrócie, wadliwy program. 153 00:06:44,347 --> 00:06:45,180 Nie taka wielka sprawa. 154 00:06:45,180 --> 00:06:46,360 Może masz winy segmentacji. 155 00:06:46,360 --> 00:06:47,651 Wszyscy mieliśmy błędów w programach. 156 00:06:47,651 --> 00:06:50,196 Może wszyscy mają błędy w programach teraz. 157 00:06:50,196 --> 00:06:51,320 Ale co to implikacja? 158 00:06:51,320 --> 00:06:54,390 Cóż, tutaj jest powiększony w wersji że obraz z pamięci mojego komputera. 159 00:06:54,390 --> 00:06:56,230 To jest dno mojego stosu. 160 00:06:56,230 --> 00:06:59,644 I rzeczywiście, na samym dole jest to, co jest nazywa rodzic rutynowych stos, fantazyjny sposób 161 00:06:59,644 --> 00:07:00,560 powiedzieć, że jest główną. 162 00:07:00,560 --> 00:07:03,772 Tak, aby każdy, kto nazywa się funkcja f, że mówimy. 163 00:07:03,772 --> 00:07:05,230 Tak więc jest na dole stosu. 164 00:07:05,230 --> 00:07:06,640 Adres zwrotny jest coś nowego. 165 00:07:06,640 --> 00:07:08,810 To zawsze było tam, zawsze w tym zdjęciu. 166 00:07:08,810 --> 00:07:10,440 Po prostu nigdy nie zwrócił uwagę na to. 167 00:07:10,440 --> 00:07:15,290 Ponieważ okazuje się, jest sposób c działa że gdy jedna funkcja wymaga innego, 168 00:07:15,290 --> 00:07:18,780 Nie tylko, że argumenty Funkcja get odkładany na stos, 169 00:07:18,780 --> 00:07:22,470 nie tylko lokalny funkcja jest zmienne się zepchnięci na stos, 170 00:07:22,470 --> 00:07:26,820 coś, co nazywa adres zwrotny także dostaje umieścić na stosie. 171 00:07:26,820 --> 00:07:33,330 W szczególności, jeśli główne połączenia Foo, Main własny adres w pamięci, wół coś, 172 00:07:33,330 --> 00:07:38,240 skutecznie dostaje umieścić na stosie tak, że gdy m odbywa się wykonywanie 173 00:07:38,240 --> 00:07:43,630 wie, gdzie wrócić w tekście Segment w celu dalszego wykonywania. 174 00:07:43,630 --> 00:07:47,760 >> Jeśli więc jesteśmy tutaj koncepcyjnie, w głównym, to f jest wywoływana. 175 00:07:47,760 --> 00:07:50,200 Jak nie wiesz, kto f do sterowania ręcznego z powrotem? 176 00:07:50,200 --> 00:07:52,020 Cóż, to trochę nawigacyjny na czerwono tutaj 177 00:07:52,020 --> 00:07:54,978 zwany adres zwrotny, to po prostu sprawdza, co to jest adres zwrotny? 178 00:07:54,978 --> 00:07:57,039 Och, pozwól mi wrócić do głównego tutaj. 179 00:07:57,039 --> 00:07:59,080 I to jest trochę z uproszczeniem, 180 00:07:59,080 --> 00:08:00,750 bo zer i jedynek do magistrali są technicznie 181 00:08:00,750 --> 00:08:01,967 tu w segmencie technologii. 182 00:08:01,967 --> 00:08:03,800 Ale to jest pomysł. f po prostu musi wiedzieć, co 183 00:08:03,800 --> 00:08:06,680 gdzie kontrola ostatecznie wraca. 184 00:08:06,680 --> 00:08:09,790 >> Ale sposób komputery już dawno określone rzeczy 185 00:08:09,790 --> 00:08:12,320 jak zmiennych lokalnych i argumentów jest tak. 186 00:08:12,320 --> 00:08:17,180 Więc w górę tego obrazu niebieskie ramki stosu jest dla f, więc wszystko 187 00:08:17,180 --> 00:08:19,630 z pamięci, że f konkretnie jest używany. 188 00:08:19,630 --> 00:08:22,990 Więc w związku z tym zauważyć, że Bar jest na tym zdjęciu. 189 00:08:22,990 --> 00:08:23,980 Bar był jej argument. 190 00:08:23,980 --> 00:08:27,240 I twierdził, że mamy do argumentów Funkcje się odkładany na stos. 191 00:08:27,240 --> 00:08:29,910 C, jest oczywiście również na tym zdjęciu. 192 00:08:29,910 --> 00:08:33,520 >> I tylko do celów notacji, zawiadomienia w górnym lewym rogu 193 00:08:33,520 --> 00:08:37,020 jest to, co będzie c 0 i wspornik następnie lekko w prawo w dół 194 00:08:37,020 --> 00:08:38,220 Uchwyt 11 jest c. 195 00:08:38,220 --> 00:08:41,240 Więc innymi słowy, można sobie wyobrazić, że istnieje siatka bajtów 196 00:08:41,240 --> 00:08:44,380 tam, z których pierwszy jest u góry po lewej, z których dolna 197 00:08:44,380 --> 00:08:48,360 jest ostatnim z tych 12 bajtów. 198 00:08:48,360 --> 00:08:49,930 >> Ale teraz staram się szybko do przodu. 199 00:08:49,930 --> 00:08:55,580 Co ma się wydarzyć, gdy mijamy w barze smyczkowy, który jest dłuższy niż c? 200 00:08:55,580 --> 00:08:59,130 A my nie sprawdzając, czy to rzeczywiście dłużej niż 12 lat. 201 00:08:59,130 --> 00:09:03,146 Która część tego obrazu będzie nadpisane przez bajtów, 0, 1, 2, 3, 202 00:09:03,146 --> 00:09:07,890 kropka kropka kropka, 11, a następnie źle, 12, 13 do 19? 203 00:09:07,890 --> 00:09:11,820 Co wydarzy się tutaj, jeśli wnioskować z zamówienia 204 00:09:11,820 --> 00:09:14,790 że wspornik c0 jest na szczycie c uchwyt 11 jest jakby w dół 205 00:09:14,790 --> 00:09:15,812 do porządku? 206 00:09:15,812 --> 00:09:16,796 Tak? 207 00:09:16,796 --> 00:09:19,260 >> PUBLICZNOŚCI: Cóż, to będzie zastąpić bar char *. 208 00:09:19,260 --> 00:09:22,260 >> David J. MALAN: Tak, wygląda na to, masz zamiar zastąpić char * poprzeczkę. 209 00:09:22,260 --> 00:09:26,245 A co gorsza, jeśli wyślesz w bardzo długo ciąg, może nawet zastąpić, co? 210 00:09:26,245 --> 00:09:27,460 211 00:09:27,460 --> 00:09:28,570 Adres zwrotny. 212 00:09:28,570 --> 00:09:31,380 Co znowu, jest jak nawigacyjny powiedzieć program, w którym 213 00:09:31,380 --> 00:09:34,060 , aby wrócić do gdy f Odbywa się to miano. 214 00:09:34,060 --> 00:09:37,140 >> Więc co zrobić, źli zazwyczaj jest wtedy, gdy natknąłem się na programie 215 00:09:37,140 --> 00:09:41,290 że są ciekawi, czy jest do eksploatacji, wózek w taki sposób, 216 00:09:41,290 --> 00:09:43,550 że może on podjąć Zaletą tego błędu, 217 00:09:43,550 --> 00:09:45,720 ogólnie nie dostać to dobrze za pierwszym razem. 218 00:09:45,720 --> 00:09:48,590 Po prostu rozpocząć wysyłanie, na przykład losowe ciągi znaków do programu, 219 00:09:48,590 --> 00:09:50,260 czy na klawiaturze, i szczerze mówiąc, że prawdopodobnie 220 00:09:50,260 --> 00:09:52,740 Napisać mały program do tylko automatycznie generować ciągi, 221 00:09:52,740 --> 00:09:55,430 i zacząć walić w programie przez wysyłanie w wielu różnych wejść 222 00:09:55,430 --> 00:09:56,340 o różnych długościach. 223 00:09:56,340 --> 00:09:58,990 >> Jak tylko awarii programu, to jest niesamowite. 224 00:09:58,990 --> 00:10:01,020 Bo to oznacza, że lub odkryła 225 00:10:01,020 --> 00:10:02,660 co jest chyba rzeczywiście błąd. 226 00:10:02,660 --> 00:10:05,830 A następnie mogą dostać więcej sprytna i rozpocząć koncentrując się bardziej wąsko 227 00:10:05,830 --> 00:10:07,420 w jaki sposób wykorzystać ten błąd. 228 00:10:07,420 --> 00:10:11,480 W szczególności, co mógłby on zrobić, to wysłać, w najlepszym razie, cześć. 229 00:10:11,480 --> 00:10:12,210 Nic wielkiego. 230 00:10:12,210 --> 00:10:14,750 Jest to ciąg znaków, który jest wystarczająco krótki. 231 00:10:14,750 --> 00:10:18,100 Ale co, jeśli on lub ona wysyła, a my uogólnić jako, 232 00:10:18,100 --> 00:10:20,890 Atak code-- tak zer i te, które robią rzeczy 233 00:10:20,890 --> 00:10:25,150 rm-rf jak, to usuń wszystko z dysku twardego lub wysyłania spamu 234 00:10:25,150 --> 00:10:27,000 lub w jakiś sposób atakować maszynę? 235 00:10:27,000 --> 00:10:29,570 >> Tak więc, jeśli każdy z tych litery po prostu oznacza, 236 00:10:29,570 --> 00:10:32,380 koncepcyjnie, atak, atak, atak, atak, niektóre złe kod 237 00:10:32,380 --> 00:10:36,410 że ktoś inny napisał, ale jeśli osoba jest na tyle sprytny, 238 00:10:36,410 --> 00:10:40,790 nie tylko to wszystko te rm-RF, lecz również 239 00:10:40,790 --> 00:10:46,100 mieć swoje ostatnie kilka bajtów być numer odpowiadający 240 00:10:46,100 --> 00:10:50,540 na adres jego lub jej własny kod ataku 241 00:10:50,540 --> 00:10:53,820 że on lub ona przekazywana w tak poprzez zapewnienie mu na szybkie, 242 00:10:53,820 --> 00:10:58,760 można skutecznie oszukać komputer się zauważyć, gdy f jest wykonywana wykonania, 243 00:10:58,760 --> 00:11:02,400 Och, to jest czas dla mnie, aby przejść z powrotem do czerwonego adresu zwrotnego. 244 00:11:02,400 --> 00:11:06,070 Ale dlatego, że on lub ona ma jakiś krycie, że adres zwrotny 245 00:11:06,070 --> 00:11:09,602 z własnym numerem, i są one na tyle sprytny, 246 00:11:09,602 --> 00:11:11,560 które zostały skonfigurowane do Numer odnieść, jak ty 247 00:11:11,560 --> 00:11:13,740 zobacz w super góry lewy róg tam, 248 00:11:13,740 --> 00:11:18,020 rzeczywisty adres komputera pamięć niektórych ich kodu ataku, 249 00:11:18,020 --> 00:11:21,740 zły może oszukać komputer do wykonania swój własny kod. 250 00:11:21,740 --> 00:11:23,700 >> I że kod, ponownie, może być cokolwiek. 251 00:11:23,700 --> 00:11:26,120 To na ogół nazywane Kod powłoki, która jest po prostu 252 00:11:26,120 --> 00:11:29,030 sposobem na powiedzenie, że to nie jest ogólnie coś tak prostego jak rm-rf. 253 00:11:29,030 --> 00:11:32,340 To rzeczywiście coś jak bash, lub programem, który rzeczywiście daje mu 254 00:11:32,340 --> 00:11:37,230 lub jej wykonanie sterowania programowego wszystko, co chcą. 255 00:11:37,230 --> 00:11:40,210 Tak więc, w skrócie, wszystkie wynika z prostego faktu, 256 00:11:40,210 --> 00:11:44,490 że ten błąd nie sprawdzając zaangażowane granice swojej tablicy. 257 00:11:44,490 --> 00:11:47,250 A ponieważ na drodze komputerów jest to, że praca 258 00:11:47,250 --> 00:11:49,430 korzystania ze stosu skutecznie, koncepcyjnie, 259 00:11:49,430 --> 00:11:54,830 dołu na górę, ale potem elementy naciśnięciu na stos rośnie z góry na dół, 260 00:11:54,830 --> 00:11:56,624 to jest bardzo problematyczne. 261 00:11:56,624 --> 00:11:58,290 Teraz istnieją sposoby obejścia tego. 262 00:11:58,290 --> 00:12:00,800 I szczerze mówiąc, nie są w językach z którego można to obejść. 263 00:12:00,800 --> 00:12:03,100 Java odpornościowego, na przykład, do tej konkretnej kwestii. 264 00:12:03,100 --> 00:12:04,110 Ponieważ nie daje wskazówek. 265 00:12:04,110 --> 00:12:05,943 Nie daje bezpośrednie adresy pamięci. 266 00:12:05,943 --> 00:12:08,560 Więc z tego, że mamy moc dotykać niczego w pamięci 267 00:12:08,560 --> 00:12:11,580 Chcemy pochodzi wprawdzie wielkie ryzyko. 268 00:12:11,580 --> 00:12:12,430 >> Więc miej oko. 269 00:12:12,430 --> 00:12:14,596 Jeśli, szczerze mówiąc, w miesiącach lub latach, w każdej chwili 270 00:12:14,596 --> 00:12:17,740 można przeczytać o jakimś eksploatacji programu lub serwera, 271 00:12:17,740 --> 00:12:22,370 jeśli kiedykolwiek zobaczyć podpowiedź coś jak atak przepełnienia bufora, 272 00:12:22,370 --> 00:12:25,390 lub stosu przelewowa jest innym typem ataku, w duchu podobnym, 273 00:12:25,390 --> 00:12:28,770 ile inspiruje witryny wymienić, jeśli go znasz, 274 00:12:28,770 --> 00:12:33,170 to wszystko mówisz tylko przepełnione rozmiar charakterem 275 00:12:33,170 --> 00:12:36,200 tablica lub tablica ogólnie niektóre. 276 00:12:36,200 --> 00:12:38,822 Wszelkie pytania, a następnie, w tej sprawie? 277 00:12:38,822 --> 00:12:39,780 Nie próbuj tego w domu. 278 00:12:39,780 --> 00:12:41,620 279 00:12:41,620 --> 00:12:42,300 >> Wszystko w porządku. 280 00:12:42,300 --> 00:12:47,270 Więc malloc dotychczas był nasz nowy przyjaciel w które możemy przydzielić pamięci 281 00:12:47,270 --> 00:12:50,540 że nie muszą wiedzieć, w wcześniej, że chcemy więc nie mamy 282 00:12:50,540 --> 00:12:52,920 do dysku do naszego kodu numery programów, takich jak 12. 283 00:12:52,920 --> 00:12:55,550 Gdy użytkownik mówi nam, jak bardzo Dane on chce do wejścia, 284 00:12:55,550 --> 00:12:58,000 malloc, że możemy dużo pamięci. 285 00:12:58,000 --> 00:13:01,484 >> Więc malloc się okazuje, do stopniu używaliśmy go, 286 00:13:01,484 --> 00:13:03,900 wyraźnie ostatni raz, a następnie wy zostały zastosowane 287 00:13:03,900 --> 00:13:08,160 dla nieświadomie dla getString kilka tygodni, wszystko w pamięci malloc 288 00:13:08,160 --> 00:13:09,820 pochodzi z tzw sterty. 289 00:13:09,820 --> 00:13:13,852 I dlatego getString, na przykład może przydzielić pamięci dynamicznie 290 00:13:13,852 --> 00:13:16,060 nie wiedząc, co masz zamiar wpisać z góry, 291 00:13:16,060 --> 00:13:21,520 oddać z powrotem wskaźnik do tej pamięci, i że pamięć jest nadal twoje utrzymanie, 292 00:13:21,520 --> 00:13:24,080 nawet po getString zyski. 293 00:13:24,080 --> 00:13:27,450 Bo przecież przypomnieć, że stos ciągle idzie w górę iw dół, 294 00:13:27,450 --> 00:13:27,950 w górę iw dół. 295 00:13:27,950 --> 00:13:30,230 I tak szybko jak to jest w dół, to znaczy jakiejkolwiek pamięci 296 00:13:30,230 --> 00:13:33,030 Ta funkcja powinna nie być używany przez nikogo innego. 297 00:13:33,030 --> 00:13:34,570 To wartości śmieci teraz. 298 00:13:34,570 --> 00:13:36,120 >> Ale kupa jest tutaj. 299 00:13:36,120 --> 00:13:39,360 I co miłe jest to, że o malloc gdy malloc przydziela pamięć się tutaj, 300 00:13:39,360 --> 00:13:42,070 to nie wpłynęło na przeważającej części przez stos. 301 00:13:42,070 --> 00:13:46,000 , A więc każdy może uzyskać dostęp do funkcji pamięć, która została malloc'd, 302 00:13:46,000 --> 00:13:49,120 nawet przez funkcję jak getString, nawet po jej zwrócone. 303 00:13:49,120 --> 00:13:51,700 >> Teraz, rozmawiać z malloc jest bezpłatny. 304 00:13:51,700 --> 00:13:53,900 I rzeczywiście, ci reguła potrzebne do rozpoczęcia przyjmowania 305 00:13:53,900 --> 00:13:58,950 jest każdy, każdy, za każdym razem używasz malloc musisz sobie używać za darmo, w końcu, 306 00:13:58,950 --> 00:14:00,280 tego samego wskaźnika. 307 00:14:00,280 --> 00:14:03,289 Wszystko to razem pisali buggy, kod buggy, z wielu powodów. 308 00:14:03,289 --> 00:14:05,580 Jednak, z których jedna została korzystania z biblioteki CS50, które 309 00:14:05,580 --> 00:14:09,010 Sam jest celowo buggy, że przecieki pamięci. 310 00:14:09,010 --> 00:14:11,410 Za każdym razem pan nazywa getString w ciągu ostatnich kilku tygodni 311 00:14:11,410 --> 00:14:13,870 pytamy o eksploatacji System Linux, dla pamięci. 312 00:14:13,870 --> 00:14:15,780 I nigdy nie raz podano je z powrotem. 313 00:14:15,780 --> 00:14:17,730 I tak nie jest w ćwiczyć, coś dobrego. 314 00:14:17,730 --> 00:14:20,330 >> I Valgrind jeden z narzędzia wprowadzone w Pset 4, 315 00:14:20,330 --> 00:14:22,900 jest o pomaga teraz znaleźć błędy w tym stylu. 316 00:14:22,900 --> 00:14:27,060 Ale na szczęście dla Pset 4 nie trzeba do korzystania z biblioteki CS50 lub getString. 317 00:14:27,060 --> 00:14:31,220 Więc wszelkie błędy związane z pamięcią są ostatecznie będzie własne. 318 00:14:31,220 --> 00:14:34,060 >> Więc malloc jest więcej niż tylko Wygodne dla tego celu. 319 00:14:34,060 --> 00:14:37,420 Możemy faktycznie teraz rozwiązać zasadniczo różne problemy, 320 00:14:37,420 --> 00:14:41,640 i zasadniczo rozwiązać więcej problemów skutecznie, jak za tydzień Zero obietnicy. 321 00:14:41,640 --> 00:14:44,720 Jak dotąd jest to najseksowniejsza Struktura danych mieliśmy. 322 00:14:44,720 --> 00:14:47,804 I struktury danych, po prostu oznacza, sposób pamięci konceptualizacji 323 00:14:47,804 --> 00:14:50,720 w sposób, który wykracza poza tylko powiedzieć, to int jest char. 324 00:14:50,720 --> 00:14:52,930 Możemy zacząć rzeczy klastra razem. 325 00:14:52,930 --> 00:14:54,460 >> Tak wyglądała ta tablica. 326 00:14:54,460 --> 00:14:57,270 I to, co było kluczem o Tablica jest to, że daje 327 00:14:57,270 --> 00:14:59,724 back-to-back kawałki Pamięć, z których każda 328 00:14:59,724 --> 00:15:02,765 ma być tego samego typu, int int, int, int lub char, char, char, 329 00:15:02,765 --> 00:15:03,330 char. 330 00:15:03,330 --> 00:15:04,496 Ale jest kilka wad. 331 00:15:04,496 --> 00:15:06,570 To jest na przykład Tablica wielkości szóstego. 332 00:15:06,570 --> 00:15:10,650 Załóżmy, że wypełnienie tej tablicy z sześciu numery, a następnie, z jakichkolwiek przyczyn, 333 00:15:10,650 --> 00:15:13,187 Twój użytkownik chce dać Ci numer siódmy. 334 00:15:13,187 --> 00:15:14,020 Gdzie go umieścić? 335 00:15:14,020 --> 00:15:15,490 336 00:15:15,490 --> 00:15:18,990 >> Co to jest rozwiązanie, jeśli masz utworzony tablicę na stosie 337 00:15:18,990 --> 00:15:22,030 Na przykład, tylko z tygodnia dwa wprowadzono zapis, że my, 338 00:15:22,030 --> 00:15:23,730 w nawiasach kwadratowych z numerem wewnątrz? 339 00:15:23,730 --> 00:15:25,160 340 00:15:25,160 --> 00:15:27,260 Cóż, masz sześć Liczby w tych polach. 341 00:15:27,260 --> 00:15:28,530 Co by instynktowi być? 342 00:15:28,530 --> 00:15:29,973 Gdzie chcesz go umieścić? 343 00:15:29,973 --> 00:15:30,860 >> PUBLICZNOŚCI: [niesłyszalne] 344 00:15:30,860 --> 00:15:31,315 >> David J. MALAN: Przepraszam? 345 00:15:31,315 --> 00:15:32,380 >> PUBLICZNOŚCI: Umieść go na koniec. 346 00:15:32,380 --> 00:15:33,796 >> David J. MALAN: Umieść go na koniec. 347 00:15:33,796 --> 00:15:35,880 Tak właśnie się w prawo poza ten obszar. 348 00:15:35,880 --> 00:15:38,710 Które byłoby miło, ale to Okazuje się, że nie może tego zrobić. 349 00:15:38,710 --> 00:15:41,350 Bo jeśli nie prosiłem w tym fragmencie pamięci, 350 00:15:41,350 --> 00:15:44,490 to może być przypadkiem, że to jest używany przez inną zmienną 351 00:15:44,490 --> 00:15:45,030 całkowicie. 352 00:15:45,030 --> 00:15:49,210 Pomyśl tygodniu lub tak, gdy określone z nazwami Zamyla and Davina and Gabe 353 00:15:49,210 --> 00:15:49,930 w pamięci. 354 00:15:49,930 --> 00:15:51,638 Byli dosłownie z powrotem do tyłu na plecach. 355 00:15:51,638 --> 00:15:53,550 Nie możemy więc koniecznie ufać, że cokolwiek 356 00:15:53,550 --> 00:15:55,800 tutaj jest dostępna dla mnie do używania. 357 00:15:55,800 --> 00:15:56,990 >> Co jeszcze można zrobić? 358 00:15:56,990 --> 00:16:00,282 Cóż, po realizacji cię trzeba tablicę wielkości siedmiu, 359 00:16:00,282 --> 00:16:02,490 można po prostu stworzyć tablica rozmiarów siedmiu następnie użyć 360 00:16:02,490 --> 00:16:05,950 do pętli lub pętli while, skopiować je do nowej tablicy, 361 00:16:05,950 --> 00:16:09,680 a następnie w jakiś sposób po prostu pozbyć to tablica lub po prostu przestać go używać. 362 00:16:09,680 --> 00:16:12,130 Ale to nie jest szczególnie efektywne. 363 00:16:12,130 --> 00:16:15,340 Krótko mówiąc, nie pozwól tablice dynamicznie zmieniać rozmiar. 364 00:16:15,340 --> 00:16:17,900 >> Tak więc z jednej strony można uzyskać o dostępie swobodnym, co jest niesamowite. 365 00:16:17,900 --> 00:16:20,108 Ponieważ pozwala nam robić rzeczy, jak dziel i rządź, 366 00:16:20,108 --> 00:16:23,100 wyszukiwanie binarne, z których mamy mówił o na ekranie tutaj. 367 00:16:23,100 --> 00:16:24,950 Ale malować się w kąt. 368 00:16:24,950 --> 00:16:27,810 Tak szybko, jak trafisz koniec swojej tablicy, 369 00:16:27,810 --> 00:16:29,980 co musisz zrobić, to bardzo kosztowna operacja 370 00:16:29,980 --> 00:16:33,910 lub napisać całą masę kodu teraz sobie z tym problemem. 371 00:16:33,910 --> 00:16:36,680 >> Więc co, jeśli zamiast tego mieliśmy coś, co nazywa się lista, 372 00:16:36,680 --> 00:16:38,820 lub powiązane listy w szczególności? 373 00:16:38,820 --> 00:16:41,930 Co zrobić, jeśli zamiast prostokąty kopie kopii kopii, 374 00:16:41,930 --> 00:16:45,730 mamy prostokąty, które pozostawiają niewiele trochę manewru między nimi? 375 00:16:45,730 --> 00:16:49,670 I mimo, że mam wyciągnąć ten obraz lub dostosowany tego obrazu 376 00:16:49,670 --> 00:16:54,696 z jednego z tekstów tutaj, aby być z powrotem powrót powrót do bardzo uporządkowany, w rzeczywistości, 377 00:16:54,696 --> 00:16:56,820 jeden z tych prostokątów może być tu w pamięci. 378 00:16:56,820 --> 00:16:58,028 Jednym z nich może być tutaj. 379 00:16:58,028 --> 00:17:00,420 Jednym z nich może być tutaj, Tutaj, i tak dalej. 380 00:17:00,420 --> 00:17:02,910 >> Ale co, jeśli zwrócił, w tym przypadku, strzałki 381 00:17:02,910 --> 00:17:05,650 że w jakiś sposób połączyć te prostokąty razem? 382 00:17:05,650 --> 00:17:08,170 Rzeczywiście, widzieliśmy techniczne wcielenie strzałką. 383 00:17:08,170 --> 00:17:09,839 384 00:17:09,839 --> 00:17:13,710 Co my stosowane w ostatnich dni, że pod maską, 385 00:17:13,710 --> 00:17:15,210 jest przedstawicielem strzałką? 386 00:17:15,210 --> 00:17:16,290 387 00:17:16,290 --> 00:17:17,349 Wskaźnik, prawda? 388 00:17:17,349 --> 00:17:19,780 >> Więc co, jeśli zamiast tylko przechowywania numerów, 389 00:17:19,780 --> 00:17:23,130 jak 9, 17, 22, 26, 34, co jeśli nie są przechowywane 390 00:17:23,130 --> 00:17:27,079 tylko liczba, ale wskaźnik obok każdej takiej liczby? 391 00:17:27,079 --> 00:17:30,690 Tak, tak jak byś wątku igłę przez całą masę materiału, 392 00:17:30,690 --> 00:17:32,950 Materiały rzeczy jakoś razem, podobnie może 393 00:17:32,950 --> 00:17:35,550 my ze wskaźnikami, jak wcielony strzałkami tutaj, 394 00:17:35,550 --> 00:17:38,550 rodzaj splot razem te poszczególne prostokąty 395 00:17:38,550 --> 00:17:41,780 skutecznie za pomocą wskaźnika obok każdego numeru, który 396 00:17:41,780 --> 00:17:46,065 zwraca się do jakiegoś następnego numeru, który Wskazuje to, z kolei, część następna liczba? 397 00:17:46,065 --> 00:17:47,940 Tak więc, innymi słowy, co jeśli rzeczywiście chciał 398 00:17:47,940 --> 00:17:49,820 zaimplementować coś takiego? 399 00:17:49,820 --> 00:17:53,610 No niestety, te prostokąty, co najmniej w jednym z 9, 17, 22, 400 00:17:53,610 --> 00:17:57,040 i tak dalej, to nie są już ładne kwadraty z pojedynczych numerów. 401 00:17:57,040 --> 00:17:59,960 Dołu, prostokąt poniżej 9, na przykład 402 00:17:59,960 --> 00:18:04,330 reprezentuje to, co powinno być wskaźnikiem, 32 bity. 403 00:18:04,330 --> 00:18:09,460 Teraz nie jestem jeszcze świadoma każdego typu danych w C, który daje nie tylko int 404 00:18:09,460 --> 00:18:11,630 , ale wskaźnik w ogóle. 405 00:18:11,630 --> 00:18:15,020 >> Więc co to jest rozwiązanie, jeśli chcemy wymyślać własną odpowiedź na to pytanie? 406 00:18:15,020 --> 00:18:15,760 Tak? 407 00:18:15,760 --> 00:18:16,640 >> PUBLICZNOŚCI: [niesłyszalne] 408 00:18:16,640 --> 00:18:17,360 >> David J. MALAN: Co to jest? 409 00:18:17,360 --> 00:18:17,880 >> PUBLICZNOŚCI: Nowa struktura. 410 00:18:17,880 --> 00:18:19,590 >> David J. MALAN: Tak, tak, dlaczego Nie tworzymy nową strukturę, 411 00:18:19,590 --> 00:18:20,920 lub C, struct? 412 00:18:20,920 --> 00:18:25,990 Widzieliśmy konstrukcjom przed, czy krótko, gdzie mamy do czynienia ze strukturą studentów 413 00:18:25,990 --> 00:18:27,780 jak ten, który miał imię i dom. 414 00:18:27,780 --> 00:18:31,980 W Pset 3 Breakout użyłeś cały Pęczek structs-- GRect i GOvals 415 00:18:31,980 --> 00:18:34,810 że Stanford stworzył do Informacje klastra razem. 416 00:18:34,810 --> 00:18:38,580 Więc co, jeśli weźmiemy ten sam pomysł słowa kluczowe "typedef" i "struct", 417 00:18:38,580 --> 00:18:42,890 i niektóre specyficzne rzeczy studenta, i rozwijać się to do następujących czynności: 418 00:18:42,890 --> 00:18:46,210 typedef struct node-- i węzeł jest tylko bardzo ogólne informatyka 419 00:18:46,210 --> 00:18:49,980 Określenie czegoś w strukturze danych, Pojemnik, w strukturze danych. 420 00:18:49,980 --> 00:18:53,900 Twierdzę węzeł będzie miał int n, całkowicie proste, 421 00:18:53,900 --> 00:18:58,810 a następnie trochę więcej tajemniczo, Druga linia węzłów struct * dalej. 422 00:18:58,810 --> 00:19:01,300 Ale w mniejszym zakresie technicznych, co to jest druga linia 423 00:19:01,300 --> 00:19:02,980 kodu wewnątrz nawiasy? 424 00:19:02,980 --> 00:19:03,737 Tak? 425 00:19:03,737 --> 00:19:04,851 >> PUBLICZNOŚCI: [niesłyszalne] 426 00:19:04,851 --> 00:19:06,600 David J. MALAN: wskaźnika do innego węzła. 427 00:19:06,600 --> 00:19:09,910 Więc co prawda, trochę składni tajemniczy. 428 00:19:09,910 --> 00:19:13,250 Ale jeśli ją przeczytać dosłownie, następna jest nazwa zmiennej. 429 00:19:13,250 --> 00:19:14,410 Jaki jest jego typ danych? 430 00:19:14,410 --> 00:19:18,206 To trochę rozwlekły tym razem, ale to z węzła struct typu *. 431 00:19:18,206 --> 00:19:22,960 Za każdym razem widzieliśmy coś gwiazdę, że Oznacza to wskaźnik do tego typu danych. 432 00:19:22,960 --> 00:19:26,810 Więc następnym jest najwyraźniej wskaźnik do węzła struct. 433 00:19:26,810 --> 00:19:28,310 >> Teraz, co jest struct node? 434 00:19:28,310 --> 00:19:31,044 Cóż, zauważyć można zobaczyć tych, same słowa w prawym górnym rogu. 435 00:19:31,044 --> 00:19:33,960 I rzeczywiście, można również zobaczyć słowo "Węzeł" tu na dole po lewej. 436 00:19:33,960 --> 00:19:35,640 I to jest właściwie tylko wygoda. 437 00:19:35,640 --> 00:19:39,930 Zauważ, że w naszej definicji studenta jest słowo "student" tylko raz. 438 00:19:39,930 --> 00:19:42,510 A to dlatego, że student obiekt nie był autoreferencyjna. 439 00:19:42,510 --> 00:19:45,340 Nie ma nic w środku studenta że musi zwrócić się do innego ucznia, 440 00:19:45,340 --> 00:19:45,610 persay. 441 00:19:45,610 --> 00:19:47,630 To byłoby coś w rodzaju dziwne w świecie rzeczywistym. 442 00:19:47,630 --> 00:19:50,880 >> Ale z węzła w powiązane lista, chcemy węzeł 443 00:19:50,880 --> 00:19:53,970 jako wzorcowy do podobnego obiektu. 444 00:19:53,970 --> 00:19:57,900 I tak zauważyć tu nie jest zmiana tylko to, co znajduje się wewnątrz nawiasów klamrowych. 445 00:19:57,900 --> 00:20:00,800 Ale dodać słowo "węzeł" w górę, jak również 446 00:20:00,800 --> 00:20:02,930 dodawania do dołu zamiast "student". 447 00:20:02,930 --> 00:20:06,000 A to tylko szczegóły techniczne tak, że znowu twój struktura danych 448 00:20:06,000 --> 00:20:11,380 może być self-więzy, tak że Węzeł może wskazać innego takiego węzła. 449 00:20:11,380 --> 00:20:13,840 >> Więc co to jest ostatecznie będzie oznaczać dla nas? 450 00:20:13,840 --> 00:20:17,560 Cóż, jeden, ten materiał wewnątrz jest zawartość przykładowego węzła. 451 00:20:17,560 --> 00:20:19,360 To coś się tutaj, górna prawa, jest tak 452 00:20:19,360 --> 00:20:20,860 że znów możemy odnosić się do siebie. 453 00:20:20,860 --> 00:20:23,401 A następnie rzeczy najbardziej zewnętrzna, Nawet jeśli węzeł jest nowy okres, 454 00:20:23,401 --> 00:20:25,500 być może, to jeszcze samo, jak i to, co uczeń 455 00:20:25,500 --> 00:20:27,520 był pod maską w SPL. 456 00:20:27,520 --> 00:20:31,095 >> Jeśli więc teraz chciał zacząć realizacji tej połączonej listy, 457 00:20:31,095 --> 00:20:33,220 jak możemy tłumaczyć coś jak to zakodować? 458 00:20:33,220 --> 00:20:35,350 Cóż, po prostu zobaczyć Przykładem programu, który 459 00:20:35,350 --> 00:20:36,840 faktycznie korzysta z połączonej listy. 460 00:20:36,840 --> 00:20:40,870 Wśród dzisiejszego kodu dystrybucji jest program o nazwie Lista Zero. 461 00:20:40,870 --> 00:20:44,980 I jeśli uruchomię to stworzyłem Super proste GUI, Graphical User Interface, 462 00:20:44,980 --> 00:20:46,460 ale to naprawdę tylko printf. 463 00:20:46,460 --> 00:20:50,930 A teraz dałem sobie kilka menu options-- usuwanie, wstawianie, wyszukiwanie, 464 00:20:50,930 --> 00:20:51,750 i Traverse. 465 00:20:51,750 --> 00:20:52,630 I Quit. 466 00:20:52,630 --> 00:20:55,970 Są to tylko wspólne działania na struktura danych zwana listą linków. 467 00:20:55,970 --> 00:20:58,409 >> Teraz Usuń zamierza usunąć numer z listy. 468 00:20:58,409 --> 00:21:00,200 Wkładka będzie dodać Numer na liście. 469 00:21:00,200 --> 00:21:02,181 Wyszukiwanie będzie wyglądać do numeru na liście. 470 00:21:02,181 --> 00:21:04,930 I trawers tylko fantazyjny sposób mówić, chodzić na liście, 471 00:21:04,930 --> 00:21:06,245 wydrukować go, ale to wszystko. 472 00:21:06,245 --> 00:21:07,720 Nie zmienia to w żaden sposób. 473 00:21:07,720 --> 00:21:08,570 >> Warto więc spróbować. 474 00:21:08,570 --> 00:21:10,160 Idziemy do przodu i typu 2. 475 00:21:10,160 --> 00:21:12,710 A potem mam zamiar wstawić numer, powiedzmy 9. 476 00:21:12,710 --> 00:21:13,620 Enter. 477 00:21:13,620 --> 00:21:17,480 A teraz mój program jest po prostu zaprogramowany znaczy lista jest 9. 478 00:21:17,480 --> 00:21:20,190 Teraz, jeśli pójdę do przodu i wkładaj ponownie, niech 479 00:21:20,190 --> 00:21:23,680 mi iść dalej i pomniejszyć i wpisz 17. 480 00:21:23,680 --> 00:21:25,770 Teraz moja lista jest 9, a potem 17. 481 00:21:25,770 --> 00:21:27,750 Jeśli ja włożyć ponownie, pomińmy jeden. 482 00:21:27,750 --> 00:21:32,400 Zamiast 22, jak na zdjęciu mamy przygląda tutaj, pozwól mi przejść do przodu 483 00:21:32,400 --> 00:21:34,630 i włóż 26 następna. 484 00:21:34,630 --> 00:21:36,230 Więc mam zamiar wpisać 26. 485 00:21:36,230 --> 00:21:37,755 Lista jest jak oczekuję. 486 00:21:37,755 --> 00:21:40,630 Ale teraz, po prostu, aby zobaczyć, czy ten kod będzie elastyczny, niech mnie teraz 487 00:21:40,630 --> 00:21:43,520 typ 22, których co najmniej koncepcyjnie, jeśli jesteśmy 488 00:21:43,520 --> 00:21:46,520 Mając to sortowane, co jest w istocie będzie teraz inny cel, 489 00:21:46,520 --> 00:21:48,690 powinny znaleźć się w od 17 do 26. 490 00:21:48,690 --> 00:21:50,270 Więc naciśnij Enter. 491 00:21:50,270 --> 00:21:51,380 Rzeczywiście, że działa. 492 00:21:51,380 --> 00:21:54,950 A tak teraz daj mi włożyć ostatnio, na zdjęciu, 34. 493 00:21:54,950 --> 00:21:55,450 >> Wszystko w porządku. 494 00:21:55,450 --> 00:21:58,980 Więc teraz niech stanowią, że Usuń i Traverse i Szukaj zrobić, 495 00:21:58,980 --> 00:21:59,760 w rzeczywistości, działać. 496 00:21:59,760 --> 00:22:04,180 W rzeczywistości, jeśli nie uruchomić wyszukiwanie, niech wyszukać numer 22, Enter. 497 00:22:04,180 --> 00:22:05,010 Stwierdzono 22. 498 00:22:05,010 --> 00:22:07,580 Tak to jest, co to Program Lista Zero robi. 499 00:22:07,580 --> 00:22:10,230 >> Ale co się naprawdę dzieje na który implementuje ten? 500 00:22:10,230 --> 00:22:14,530 Cóż, po pierwsze mogę mieć, a nawet Muszę, plik o nazwie list0.h. 501 00:22:14,530 --> 00:22:16,540 502 00:22:16,540 --> 00:22:20,690 I gdzieś tam jest ta Linia, typedef, struct node, 503 00:22:20,690 --> 00:22:24,850 wtedy mam nawiasy klamrowe, int n, i następnie struct-- co definicja? 504 00:22:24,850 --> 00:22:26,530 505 00:22:26,530 --> 00:22:28,545 Struct node obok. 506 00:22:28,545 --> 00:22:29,920 507 00:22:29,920 --> 00:22:31,045 Więc musimy gwiazdę. 508 00:22:31,045 --> 00:22:33,420 Teraz przejdziemy do technicznie zwyczaj rysowania go tutaj. 509 00:22:33,420 --> 00:22:35,670 Możesz zobaczyć, podręczniki i odnośników internetowych zrobić tam. 510 00:22:35,670 --> 00:22:36,660 Jest to funkcjonalny odpowiednik. 511 00:22:36,660 --> 00:22:37,980 W rzeczywistości jest nieco bardziej typowe. 512 00:22:37,980 --> 00:22:40,563 Ale będę spójne z tym, co my ostatni raz i to zrobić. 513 00:22:40,563 --> 00:22:42,350 I wtedy wreszcie, mam zamiar to zrobić. 514 00:22:42,350 --> 00:22:45,550 >> Tak więc w pliku nagłówka gdzieś, w list0.h 515 00:22:45,550 --> 00:22:49,200 dziś jest to definicja struct, i być może kilka innych rzeczy. 516 00:22:49,200 --> 00:22:52,580 Tymczasem w list0c nie będzie kilka rzeczy. 517 00:22:52,580 --> 00:22:54,740 Ale będziemy tylko zacząć i nie skończyć. 518 00:22:54,740 --> 00:22:59,690 List0.h jest plik chcę aby w moim pliku C. 519 00:22:59,690 --> 00:23:03,910 A następnie w pewnym momencie, że jestem będzie mieć int, główny, unieważnić. 520 00:23:03,910 --> 00:23:06,530 A potem mam zamiar mają pewne rzeczy do zrobienia tutaj. 521 00:23:06,530 --> 00:23:10,620 Jestem również będzie mieć Prototyp, jak nieważne, wyszukiwanie, int, 522 00:23:10,620 --> 00:23:13,610 n, którego celem w życiu jest szukać elementu. 523 00:23:13,610 --> 00:23:18,310 A potem tu twierdzę w dzisiejszy kod, nieważne, wyszukiwania, int n, 524 00:23:18,310 --> 00:23:21,020 nie średnik ale otwarte nawiasy klamrowe. 525 00:23:21,020 --> 00:23:25,049 A teraz chcę jakoś sprawdzić elementu na tej liście. 526 00:23:25,049 --> 00:23:27,340 Ale nie mamy na tyle informacja na ekranie dotychczas. 527 00:23:27,340 --> 00:23:29,800 Faktycznie nie mam reprezentowane samego listę. 528 00:23:29,800 --> 00:23:33,070 Więc jeden sposób możemy wdrożyć połączonej listy w programie 529 00:23:33,070 --> 00:23:37,520 jest I niby chcesz zrobić coś jak deklaruje listę związane tutaj. 530 00:23:37,520 --> 00:23:40,520 Dla uproszczenia, mam zamiar zrobić Ten ogólny, chociaż Generalnie 531 00:23:40,520 --> 00:23:41,645 nie należy robić tego zbyt wiele. 532 00:23:41,645 --> 00:23:43,260 Ale będzie to uproszczenie tego przykładu. 533 00:23:43,260 --> 00:23:45,890 Tak, chcę oświadczyć, powiązana lista tutaj. 534 00:23:45,890 --> 00:23:47,010 Teraz, w jaki sposób może to zrobić? 535 00:23:47,010 --> 00:23:48,810 536 00:23:48,810 --> 00:23:50,750 >> Oto zdjęcie z połączonej listy. 537 00:23:50,750 --> 00:23:53,030 A ja naprawdę nie wiem w tej chwili how 538 00:23:53,030 --> 00:23:56,710 Zamierzam go o reprezentowanie tak wiele rzeczy, za pomocą jednego 539 00:23:56,710 --> 00:23:58,040 zmienną w pamięci. 540 00:23:58,040 --> 00:23:59,160 Ale pomyśl przez chwilę. 541 00:23:59,160 --> 00:24:00,830 Cały czas mieliśmy łańcuchy, które następnie 542 00:24:00,830 --> 00:24:02,913 ujawniły się tablice znaków, które następnie 543 00:24:02,913 --> 00:24:05,740 objawione być tylko wskaźnik do pierwszego znaku 544 00:24:05,740 --> 00:24:08,890 w tablicy znaków który jest wartość null zakończone. 545 00:24:08,890 --> 00:24:13,530 Więc w tej logice, i z tego obraz rodzaj siewu swoje myśli, 546 00:24:13,530 --> 00:24:17,964 co trzeba tak naprawdę napisać w naszym Kod do reprezentowania połączonej listy? 547 00:24:17,964 --> 00:24:21,130 Jak wiele z tych informacji musimy uchwycić w kod C, można by powiedzieć? 548 00:24:21,130 --> 00:24:22,654 549 00:24:22,654 --> 00:24:23,154 Tak? 550 00:24:23,154 --> 00:24:24,738 >> PUBLICZNOŚCI: Musimy wskaźnik do węzła. 551 00:24:24,738 --> 00:24:26,237 David J. MALAN: wskaźnik do węzła. 552 00:24:26,237 --> 00:24:29,320 W szczególności, który węzeł Czy Państwa instynkty się utrzymać wskaźnik? 553 00:24:29,320 --> 00:24:30,026 >> PUBLICZNOŚCI: pierwszy węzeł. 554 00:24:30,026 --> 00:24:31,942 >> David J. MALAN: Tak, prawdopodobnie tylko pierwszy. 555 00:24:31,942 --> 00:24:34,030 I zauważyć, pierwszy węzeł jest inny kształt. 556 00:24:34,030 --> 00:24:37,690 To tylko połowa wielkość struktury, bo to rzeczywiście tylko wskaźnik. 557 00:24:37,690 --> 00:24:44,650 Więc co można zrobić, to oświadczam, rzeczywiście powiązana lista będzie węzła typu *. 558 00:24:44,650 --> 00:24:47,780 I niech po prostu nazwać to pierwszy i zainicjować go na null. 559 00:24:47,780 --> 00:24:49,910 Tak, null, ponownie, jest przyjście na zdjęciu tutaj. 560 00:24:49,910 --> 00:24:53,620 Nie tylko jest zerowy, jak stosowany jako specjalny Wartość zwrócona na takie rzeczy jak getString 561 00:24:53,620 --> 00:24:57,770 i malloc, null jest również zerowa wskaźnik, brak wskaźnika, 562 00:24:57,770 --> 00:24:58,430 jeśli będzie. 563 00:24:58,430 --> 00:25:00,309 To po prostu oznacza, nic nie jest jeszcze tutaj. 564 00:25:00,309 --> 00:25:02,100 Teraz pierwszy, może mam nazywa to coś. 565 00:25:02,100 --> 00:25:04,200 Mogłem nazwał to "lista" lub dowolną liczbą innych miejscach. 566 00:25:04,200 --> 00:25:06,960 Ale dzwonię to "pierwszy", tak aby Linie go z tego obrazu. 567 00:25:06,960 --> 00:25:10,280 Tak jak ciąg może być reprezentowany z adresem swojego pierwszego bajtu 568 00:25:10,280 --> 00:25:11,280 więc może powiązana lista. 569 00:25:11,280 --> 00:25:13,480 I zobaczymy, inne dane Struktury być reprezentowane 570 00:25:13,480 --> 00:25:16,700 za pomocą jednego wskaźnika, 32-bitowy strzałka, wskazując 571 00:25:16,700 --> 00:25:18,740 w pierwszym węźle konstrukcji. 572 00:25:18,740 --> 00:25:20,340 >> Ale teraz niech przewidywania problem. 573 00:25:20,340 --> 00:25:23,230 Jeśli mam tylko pamiętać, w moim programie adresowej 574 00:25:23,230 --> 00:25:27,220 w pierwszym węźle pierwszego prostokąt w tej strukturze danych, 575 00:25:27,220 --> 00:25:31,760 co lepiej być sprawy o Realizacja reszty mojej liście? 576 00:25:31,760 --> 00:25:35,820 Co znajduje się klucz, który będzie szczegółowo aby zapewnić ten faktycznie działa? 577 00:25:35,820 --> 00:25:39,250 I "naprawdę działa" I myśli, podobnie jak ciąg znaków, 578 00:25:39,250 --> 00:25:42,180 pozwala nam przejść od pierwszego znaku w imię Davina do drugiego, 579 00:25:42,180 --> 00:25:44,755 do trzeciej, do po czwarte, do samego końca, 580 00:25:44,755 --> 00:25:47,880 skąd wiemy, kiedy jesteśmy na końcu z połączonej listy, który wygląda tak? 581 00:25:47,880 --> 00:25:50,035 582 00:25:50,035 --> 00:25:50,660 Kiedy jest zerowa. 583 00:25:50,660 --> 00:25:53,640 A ja tego typu reprezentowane jako jak inżyniera elektrycznego potęgi, 584 00:25:53,640 --> 00:25:56,420 z małym uziemienia Symbol, rodzajów. 585 00:25:56,420 --> 00:25:58,246 Ale to tylko oznacza wartość null w tym przypadku. 586 00:25:58,246 --> 00:26:00,370 Możesz wyciągnąć go dowolną liczbę sposobów, ale ten sam autor 587 00:26:00,370 --> 00:26:02,800 się do korzystania z tego symbolu tutaj. 588 00:26:02,800 --> 00:26:06,260 >> Tak długo, jak długo jesteśmy sznurka Wszystkie z tych węzłów wspólnie 589 00:26:06,260 --> 00:26:08,600 tylko pamiętać, gdzie Pierwszy z nich jest tak długo 590 00:26:08,600 --> 00:26:11,760 jak położyć specjalny symbol na Ostatnim węzeł listy 591 00:26:11,760 --> 00:26:15,130 i użyjemy null, ponieważ jest to co mamy dla nas dostępne, 592 00:26:15,130 --> 00:26:16,480 ta lista jest pełna. 593 00:26:16,480 --> 00:26:20,190 I nawet jeśli tylko daje wskaźnik do Pierwszy element, to programista, 594 00:26:20,190 --> 00:26:22,486 z pewnością może uzyskać dostęp do reszty. 595 00:26:22,486 --> 00:26:24,360 Ale niech niech wasze umysły wędrować trochę, 596 00:26:24,360 --> 00:26:26,140 jeżeli nie są one już co jest dość wandered-- 597 00:26:26,140 --> 00:26:28,723 będzie czas pracy znalezienie czegokolwiek w tym liście? 598 00:26:28,723 --> 00:26:30,450 599 00:26:30,450 --> 00:26:33,470 Cholera, to jest duże O n, co nie jest złe, w uczciwości. 600 00:26:33,470 --> 00:26:34,800 Ale jest liniowa. 601 00:26:34,800 --> 00:26:37,980 Daliśmy się co funkcja tablic, przenosząc więcej 602 00:26:37,980 --> 00:26:43,130 w stronę tego obrazu dynamicznie lub powiązane ze sobą splecione węzły? 603 00:26:43,130 --> 00:26:44,970 604 00:26:44,970 --> 00:26:46,687 Daliśmy się swobodny dostęp. 605 00:26:46,687 --> 00:26:48,770 Tablica jest dobre, bo matematycznie wszystko 606 00:26:48,770 --> 00:26:50,340 jest z powrotem do tyłu, aby z powrotem do tyłu. 607 00:26:50,340 --> 00:26:52,370 Nawet jeśli tego obrazu wygląda całkiem, a nawet 608 00:26:52,370 --> 00:26:55,830 ale wygląda na to, tych węzłów są dobrze rozmieszczone, w rzeczywistości 609 00:26:55,830 --> 00:26:56,830 mogą być w dowolnym miejscu. 610 00:26:56,830 --> 00:27:01,590 OX1, Ox50, Ox123, Ox99 te węzłów może być wszędzie. 611 00:27:01,590 --> 00:27:05,960 Ponieważ malloc nie przydzielić pamięci z hałdy, ale w dowolnym miejscu w kupie. 612 00:27:05,960 --> 00:27:09,080 Nie muszą wiedzieć, że jest to będzie z powrotem do tyłu na plecach. 613 00:27:09,080 --> 00:27:12,460 I tak ten obraz w rzeczywistości jest nie będzie aż tak bardzo. 614 00:27:12,460 --> 00:27:16,140 >> Więc to zajmie trochę pracy do realizacji tej funkcji. 615 00:27:16,140 --> 00:27:17,880 Warto więc wdrożyć Wyszukaj teraz. 616 00:27:17,880 --> 00:27:20,250 I zobaczymy, rodzaj sprytny sposób to zrobić. 617 00:27:20,250 --> 00:27:24,660 Więc jeśli jestem funkcja wyszukiwania i Jestem biorąc pod uwagę zmienną całkowitą n, 618 00:27:24,660 --> 00:27:28,490 szukać, muszę wiedzieć Nowa składnia patrząc wewnątrz 619 00:27:28,490 --> 00:27:32,400 struktury, która jest Wskazał, aby znaleźć n. 620 00:27:32,400 --> 00:27:33,210 Więc zróbmy to. 621 00:27:33,210 --> 00:27:36,030 >> Więc najpierw mam zamiar iść dalej i zadeklarować węzeł *. 622 00:27:36,030 --> 00:27:39,400 I zamierzam to nazwać wskaźnik, tylko umownie. 623 00:27:39,400 --> 00:27:41,710 I mam zamiar zainicjować go do pierwszego. 624 00:27:41,710 --> 00:27:43,770 A teraz mogę to zrobić w wielu aspektach. 625 00:27:43,770 --> 00:27:45,436 Ale mam zamiar podjąć wspólne podejście. 626 00:27:45,436 --> 00:27:50,180 Podczas gdy wskaźnik nie jest równy null, i to jest prawidłowa składnia. 627 00:27:50,180 --> 00:27:54,550 I to tylko oznacza, wykonaj następujące czynności, aby długo, jak nie jesteś, wskazując na nic. 628 00:27:54,550 --> 00:27:55,800 Co chcę zrobić? 629 00:27:55,800 --> 00:28:01,939 >> Jeśli wskaźnik kropka n, pozwól mi wrócić do tego, equals-- równa co? 630 00:28:01,939 --> 00:28:03,105 Jakie wartości mam szukać? 631 00:28:03,105 --> 00:28:04,920 632 00:28:04,920 --> 00:28:06,590 Rzeczywistych N, który został przekazany. 633 00:28:06,590 --> 00:28:09,020 Więc oto kolejna funkcja z C i wielu języków. 634 00:28:09,020 --> 00:28:13,705 Nawet jeśli w węźle struktury nazywane ma wartość n, całkowicie uzasadniony 635 00:28:13,705 --> 00:28:17,530 się również lokalne argumentu lub zmienną o nazwie n. 636 00:28:17,530 --> 00:28:20,085 Bo nawet my, z ludzkie oczy, można wyróżnić 637 00:28:20,085 --> 00:28:22,087 , że n jest przypuszczalnie różnego od n. 638 00:28:22,087 --> 00:28:23,420 Bo składnia jest inna. 639 00:28:23,420 --> 00:28:26,211 Masz kropkę i wskaźnik, podczas gdy ten nie ma czegoś takiego. 640 00:28:26,211 --> 00:28:27,290 Tak to jest OK. 641 00:28:27,290 --> 00:28:29,120 To jest OK, aby połączyć je te same rzeczy. 642 00:28:29,120 --> 00:28:32,380 >> Jeśli mam znaleźć to, jestem będzie chciał coś zrobić 643 00:28:32,380 --> 00:28:35,000 jak ogłosić, że okazało się, n. 644 00:28:35,000 --> 00:28:37,930 I zostawimy, że jako komentarz lub kod pseudokod. 645 00:28:37,930 --> 00:28:40,190 Indziej, a tu interesujący, co 646 00:28:40,190 --> 00:28:47,320 chcę zrobić, jeżeli bieżący węzeł nie zawierający n, że mi zależy? 647 00:28:47,320 --> 00:28:50,700 Jak mogę osiągnąć następujące? 648 00:28:50,700 --> 00:28:53,710 Jeśli mój palec w moment jest PTR, i to 649 00:28:53,710 --> 00:28:55,920 wskazując na cokolwiek Pierwsza wskazuje na, 650 00:28:55,920 --> 00:28:59,290 Jak mogę przesunąć palcem do następnego węzła kod? 651 00:28:59,290 --> 00:29:01,915 Cóż, co jesteśmy nawigacyjny będzie podążać w tym przypadku? 652 00:29:01,915 --> 00:29:03,464 653 00:29:03,464 --> 00:29:04,380 PUBLICZNOŚCI: [niesłyszalne]. 654 00:29:04,380 --> 00:29:05,630 David J. MALAN: Tak, tak dalej. 655 00:29:05,630 --> 00:29:06,640 656 00:29:06,640 --> 00:29:09,824 Tak więc, jeśli wrócę do mojego kod tutaj rzeczywiście jestem 657 00:29:09,824 --> 00:29:12,990 zamiar iść dalej i powiedzieć, wskaźnik, który jest tylko chwilowy zmienna-- to 658 00:29:12,990 --> 00:29:15,320 dziwna nazwa, PTR, ale to tak jak temp-- 659 00:29:15,320 --> 00:29:19,234 Mam zamiar ustawić wskaźnik równa jakiegokolwiek wskaźnika jest-- 660 00:29:19,234 --> 00:29:22,150 i znowu, to będzie trochę buggy na moment-- kropką. 661 00:29:22,150 --> 00:29:23,551 662 00:29:23,551 --> 00:29:26,550 Innymi słowy, mam zamiar wziąć mój wskazujący palec, który jest w tym węźle 663 00:29:26,550 --> 00:29:31,247 tutaj i mam zamiar powiedzieć, wiesz, co, spójrz na następne pole 664 00:29:31,247 --> 00:29:33,330 i przesuń palcem do bez względu na to, wskazując na. 665 00:29:33,330 --> 00:29:35,163 I to będzie powtarzać, powtarzać, powtarzać. 666 00:29:35,163 --> 00:29:37,630 Ale kiedy to mój palec przestać robić cokolwiek? 667 00:29:37,630 --> 00:29:40,095 Tak szybko, jak to, co linia rzutów kodu w? 668 00:29:40,095 --> 00:29:40,970 PUBLICZNOŚCI: [niesłyszalne] 669 00:29:40,970 --> 00:29:43,060 David J. MALAN: Jeśli punkt podczas wskaźnik nie jest równy null. 670 00:29:43,060 --> 00:29:44,900 W pewnym momencie mój palca będzie wskazując na wartość null 671 00:29:44,900 --> 00:29:47,070 i mam zamiar zrealizować że to koniec tej listy. 672 00:29:47,070 --> 00:29:48,910 Teraz jest trochę białe kłamstwo dla uproszczenia. 673 00:29:48,910 --> 00:29:51,580 Okazuje się, że chociaż Właśnie dowiedziałem się, to notacji 674 00:29:51,580 --> 00:29:55,220 dla struktur, wskaźnik nie jest struct. 675 00:29:55,220 --> 00:29:56,580 PTR jest co? 676 00:29:56,580 --> 00:29:58,350 Po prostu być bardziej nitpicky. 677 00:29:58,350 --> 00:29:59,720 678 00:29:59,720 --> 00:30:01,360 Jest to wskaźnik do węzła. 679 00:30:01,360 --> 00:30:03,120 To nie jest sam węzeł. 680 00:30:03,120 --> 00:30:06,650 Gdybym miał tutaj żadnego gwiazdę, wskaźnik absolutely-- to węzeł. 681 00:30:06,650 --> 00:30:08,650 To jest jak jeden tydzień deklaracja zmiennej, 682 00:30:08,650 --> 00:30:10,120 chociaż słowo "węzeł" jest nowy. 683 00:30:10,120 --> 00:30:13,860 >> Ale jak tylko wprowadzić gwiazda, teraz wskaźnik do węzła. 684 00:30:13,860 --> 00:30:17,960 I niestety nie można używać notacja kropki na wskaźniku. 685 00:30:17,960 --> 00:30:21,070 Musisz użyć strzałek Zapis, który uderzająco, 686 00:30:21,070 --> 00:30:23,470 Jest pierwszym każdy kawałek składni wygląda intuicyjne. 687 00:30:23,470 --> 00:30:25,245 To dosłownie wygląda jak strzała. 688 00:30:25,245 --> 00:30:26,370 I tak, że to dobra rzecz. 689 00:30:26,370 --> 00:30:28,995 I tu dosłownie wygląda jak strzała. 690 00:30:28,995 --> 00:30:31,870 Więc myślę, że to la-- ja nie Chyba jestem zbyt popełnienia tutaj-- I 691 00:30:31,870 --> 00:30:34,120 myślę, że to ostatni nowy kawałek składni mamy zamiar zobaczyć. 692 00:30:34,120 --> 00:30:36,500 I na szczęście, to rzeczywiście trochę bardziej intuicyjne. 693 00:30:36,500 --> 00:30:40,090 >> Teraz, dla tych z Państwa, którzy wolą stary sposób, 694 00:30:40,090 --> 00:30:42,550 nadal można korzystać z notacji kropki. 695 00:30:42,550 --> 00:30:45,380 Ale jak na poniedziałkowym rozmowa, najpierw 696 00:30:45,380 --> 00:30:50,530 trzeba tam pojechać, pójść do tego rozwiązania, a następnie uzyskać dostęp do pola. 697 00:30:50,530 --> 00:30:51,897 Więc to jest również prawidłowe. 698 00:30:51,897 --> 00:30:53,730 I szczerze mówiąc, to jest trochę bardziej pedantyczny. 699 00:30:53,730 --> 00:30:56,530 Jesteś dosłownie mówiąc, nieprawidłowego wskaźnik i tam. 700 00:30:56,530 --> 00:30:59,320 Następnie chwycić .n, pole o nazwie n. 701 00:30:59,320 --> 00:31:01,370 Ale szczerze mówiąc, nikt nie chce wpisać lub przeczytać. 702 00:31:01,370 --> 00:31:03,620 I tak świat wymyślony Zapis strzałka, która 703 00:31:03,620 --> 00:31:06,980 jest równoważny, identyczny, to jest po prostu cukier syntaktyczny. 704 00:31:06,980 --> 00:31:10,570 Tak fantazyjny sposób na powiedzenie tego wygląda lepiej, lub wygląda prościej. 705 00:31:10,570 --> 00:31:12,296 >> Więc teraz mam zamiar zrobić jedną rzecz. 706 00:31:12,296 --> 00:31:15,420 Mam zamiar powiedzieć "przerwę", kiedy już okazało się, że tak nie trzymać go szukać. 707 00:31:15,420 --> 00:31:17,620 Ale to jest sedno z funkcji wyszukiwania. 708 00:31:17,620 --> 00:31:21,710 Ale to jest o wiele łatwiejsze, w końca, aby nie chodzić po kodzie. 709 00:31:21,710 --> 00:31:25,570 To jest rzeczywiście formalne wdrożenie wyszukiwania w dzisiejszym kodu dystrybucji. 710 00:31:25,570 --> 00:31:30,530 Śmiem twierdzić, że wkładka nie jest szczególnie zabawne, iść przez 711 00:31:30,530 --> 00:31:33,180 wizualnie ani usunąć, nawet jeśli na koniec dnia 712 00:31:33,180 --> 00:31:35,460 sprowadzają się one do dość proste heurystyki. 713 00:31:35,460 --> 00:31:36,330 >> Więc zróbmy to. 714 00:31:36,330 --> 00:31:39,250 Jeśli będziesz mnie tu humor, ja przynieść kilka piłeczki antystresowe. 715 00:31:39,250 --> 00:31:40,620 Przywiozłem kilka numerów. 716 00:31:40,620 --> 00:31:46,562 I możemy uzyskać tylko kilka wolontariuszy reprezentować 9, 17, 20, 22, 29, i 34? 717 00:31:46,562 --> 00:31:48,270 Więc w zasadzie wszyscy kto tu dzisiaj. 718 00:31:48,270 --> 00:31:50,170 719 00:31:50,170 --> 00:31:52,760 To był jeden, dwa, trzy, cztery, pięć, sześć osób. 720 00:31:52,760 --> 00:31:55,740 I byłem proszony o go-- zobaczyć, nie jeden z tyłu podnosi ręce. 721 00:31:55,740 --> 00:32:01,910 OK, jeden, dwa, trzy, cztery five-- pozwól mi załadować balance-- sześć. 722 00:32:01,910 --> 00:32:03,051 OK, sześć przyjść na górę. 723 00:32:03,051 --> 00:32:04,050 Będziemy potrzebować innych ludzi. 724 00:32:04,050 --> 00:32:05,460 Przywieźliśmy dodatkowe piłeczki antystresowe. 725 00:32:05,460 --> 00:32:08,200 I jeśli można, na tylko chwila, linia 726 00:32:08,200 --> 00:32:10,490 Sami się tylko jak ten obraz tutaj. 727 00:32:10,490 --> 00:32:15,200 728 00:32:15,200 --> 00:32:15,959 >> Wszystko w porządku. 729 00:32:15,959 --> 00:32:17,125 Zobaczmy, jak się nazywasz? 730 00:32:17,125 --> 00:32:17,550 >> PUBLICZNOŚCI: Andrew. 731 00:32:17,550 --> 00:32:18,800 >> David J. MALAN: Andrzej, jesteś numer 9. 732 00:32:18,800 --> 00:32:19,540 Miło cię poznać. 733 00:32:19,540 --> 00:32:20,400 Proszę bardzo. 734 00:32:20,400 --> 00:32:21,593 735 00:32:21,593 --> 00:32:22,176 PUBLICZNOŚCI: Jen. 736 00:32:22,176 --> 00:32:22,662 David J. MALAN: Jen. 737 00:32:22,662 --> 00:32:23,162 David. 738 00:32:23,162 --> 00:32:23,765 Numer 17. 739 00:32:23,765 --> 00:32:24,950 740 00:32:24,950 --> 00:32:25,450 Tak? 741 00:32:25,450 --> 00:32:26,400 >> PUBLICZNOŚCI: Jestem Julia. 742 00:32:26,400 --> 00:32:26,980 >> David J. MALAN: Julia, David. 743 00:32:26,980 --> 00:32:27,545 Numer 20. 744 00:32:27,545 --> 00:32:28,507 745 00:32:28,507 --> 00:32:29,340 PUBLICZNOŚCI: Christian. 746 00:32:29,340 --> 00:32:30,715 David J. MALAN: Christian Dawid. 747 00:32:30,715 --> 00:32:31,541 Numer 22. 748 00:32:31,541 --> 00:32:32,040 A? 749 00:32:32,040 --> 00:32:32,649 >> PUBLICZNOŚCI: JP. 750 00:32:32,649 --> 00:32:33,440 David J. MALAN: JP. 751 00:32:33,440 --> 00:32:34,880 Numer 29. 752 00:32:34,880 --> 00:32:37,080 Więc idź i dostać in-- Uh oh. 753 00:32:37,080 --> 00:32:38,486 754 00:32:38,486 --> 00:32:38,985 Uh oh. 755 00:32:38,985 --> 00:32:39,650 756 00:32:39,650 --> 00:32:40,150 Czuwania. 757 00:32:40,150 --> 00:32:41,360 758 00:32:41,360 --> 00:32:42,390 20. 759 00:32:42,390 --> 00:32:43,682 Czy ktoś ma obrońcę? 760 00:32:43,682 --> 00:32:44,890 PUBLICZNOŚCI: Mam Sharpie. 761 00:32:44,890 --> 00:32:45,660 David J. MALAN: Masz Sharpie? 762 00:32:45,660 --> 00:32:46,159 OK. 763 00:32:46,159 --> 00:32:47,577 764 00:32:47,577 --> 00:32:49,160 I czy ktoś ma kawałek papieru? 765 00:32:49,160 --> 00:32:51,562 766 00:32:51,562 --> 00:32:52,270 Zapisz wykład. 767 00:32:52,270 --> 00:32:53,810 768 00:32:53,810 --> 00:32:55,362 Chodź. 769 00:32:55,362 --> 00:32:56,320 PUBLICZNOŚCI: Mamy go. 770 00:32:56,320 --> 00:32:57,600 David J. MALAN: Mamy to? 771 00:32:57,600 --> 00:32:58,577 Wszystko w porządku, dziękuję. 772 00:32:58,577 --> 00:33:01,380 773 00:33:01,380 --> 00:33:02,520 Zaczynamy. 774 00:33:02,520 --> 00:33:03,582 Czy to od ciebie? 775 00:33:03,582 --> 00:33:04,540 Po prostu uratował dzień. 776 00:33:04,540 --> 00:33:05,670 777 00:33:05,670 --> 00:33:07,220 Tak więc 29. 778 00:33:07,220 --> 00:33:10,510 779 00:33:10,510 --> 00:33:11,110 Wszystko w porządku. 780 00:33:11,110 --> 00:33:13,360 781 00:33:13,360 --> 00:33:14,890 I błędnie 29, ale OK. 782 00:33:14,890 --> 00:33:15,720 Śmiało. 783 00:33:15,720 --> 00:33:18,114 Dobra, dam ci Twój długopis z powrotem na chwilę. 784 00:33:18,114 --> 00:33:19,280 Tak więc mamy tutaj tych ludzi. 785 00:33:19,280 --> 00:33:20,330 Zróbmy jeden inny. 786 00:33:20,330 --> 00:33:23,750 Gabe, chcesz grać Pierwszy element o? 787 00:33:23,750 --> 00:33:25,705 Musimy cię do punktu w tych znakomitych ludzi. 788 00:33:25,705 --> 00:33:26,930 789 00:33:26,930 --> 00:33:31,030 Tak, 9, 17, 20, 22, sort z 29, a następnie 34. 790 00:33:31,030 --> 00:33:32,160 791 00:33:32,160 --> 00:33:33,325 Czy stracimy kogoś? 792 00:33:33,325 --> 00:33:33,950 Mam 34. 793 00:33:33,950 --> 00:33:36,730 Gdzie did-- OK, kto chce być 34? 794 00:33:36,730 --> 00:33:37,605 OK, dalej w górę, 34. 795 00:33:37,605 --> 00:33:39,280 796 00:33:39,280 --> 00:33:41,220 Dobra, to będzie warto kulminacyjnym. 797 00:33:41,220 --> 00:33:41,550 Jak masz na imię? 798 00:33:41,550 --> 00:33:42,040 >> PUBLICZNOŚCI: Peter. 799 00:33:42,040 --> 00:33:43,456 >> David J. MALAN: Piotr, dalej w górę. 800 00:33:43,456 --> 00:33:46,810 W porządku, więc tutaj jest cała masa węzłów. 801 00:33:46,810 --> 00:33:49,060 Każdy z was reprezentuje jeden z tych prostokątów. 802 00:33:49,060 --> 00:33:51,930 I Gabe, nieco dziwne mężczyznę, oznacza pierwszy. 803 00:33:51,930 --> 00:33:54,850 Więc jego wskaźnik jest nieco mniejszy na ekranie, niż wszyscy inni. 804 00:33:54,850 --> 00:33:58,120 I w tym przypadku, każdy z lewej ręce będzie albo wskazać dół, 805 00:33:58,120 --> 00:34:01,085 a tym samym stanowiących null, więc tylko brak wskaźnika, 806 00:34:01,085 --> 00:34:03,210 czy to będzie wskazując w węźle obok ciebie. 807 00:34:03,210 --> 00:34:05,440 >> Więc teraz, jeśli zdobią sami, jak na zdjęciu 808 00:34:05,440 --> 00:34:07,585 tu, iść do przodu i punkt na siebie, z Gabe 809 00:34:07,585 --> 00:34:11,030 w szczególności wskazując na nr 9 do reprezentowania listę. 810 00:34:11,030 --> 00:34:14,050 OK, a numer 34, lewą ręką powinna być skierowana tylko na podłodze. 811 00:34:14,050 --> 00:34:15,750 >> OK, więc jest powiązana lista. 812 00:34:15,750 --> 00:34:17,580 Więc to jest scenariusz, o którym mowa. 813 00:34:17,580 --> 00:34:20,210 I rzeczywiście, jest to przedstawiciel klasy problemów 814 00:34:20,210 --> 00:34:21,929 że może spróbować rozwiązać z kodem. 815 00:34:21,929 --> 00:34:25,020 Chcesz ostatecznie wstawić element do listy. 816 00:34:25,020 --> 00:34:27,494 W tym przypadku, będziemy spróbuj włożyć numer 55. 817 00:34:27,494 --> 00:34:28,500 818 00:34:28,500 --> 00:34:30,860 Ale nie będzie różne przypadki do rozważenia. 819 00:34:30,860 --> 00:34:34,409 I rzeczywiście, to będzie jeden z big-picture takeaways tu jest, 820 00:34:34,409 --> 00:34:35,659 jakie są różne przypadki. 821 00:34:35,659 --> 00:34:39,120 Jakie są różne, jeżeli warunki lub gałęzie, że program może mieć? 822 00:34:39,120 --> 00:34:42,024 >> Cóż, liczba próbujesz Wkładka, które znamy teraz jako 55, 823 00:34:42,024 --> 00:34:44,650 ale jeśli nie wiesz z góry, Przypuszczam 824 00:34:44,650 --> 00:34:47,840 spadnie do co najmniej trzy możliwych sytuacjach. 825 00:34:47,840 --> 00:34:49,717 W przypadku, gdy nowy element może być? 826 00:34:49,717 --> 00:34:51,050 PUBLICZNOŚCI: I koniec lub średnim. 827 00:34:51,050 --> 00:34:54,150 David J. MALAN: Na koniec, w średnim, lub na początku. 828 00:34:54,150 --> 00:34:56,650 Więc twierdzić tam co najmniej trzy problemy musimy rozwiązać. 829 00:34:56,650 --> 00:34:58,691 Załóżmy, wybrać to, co jest być może prawdopodobnie najprostsza 830 00:34:58,691 --> 00:35:01,090 jeden, gdy nowy element Należy na początku. 831 00:35:01,090 --> 00:35:04,040 Więc mam zamiar mieć kod dość jak sprawdzić, który właśnie napisał. 832 00:35:04,040 --> 00:35:07,670 I mam zamiar mieć ptr, która Ja reprezentuje tu z moim palcem, 833 00:35:07,670 --> 00:35:08,370 w zwykły sposób. 834 00:35:08,370 --> 00:35:12,430 >> I pamiętaj, co wartość nie możemy zainicjować ptr do? 835 00:35:12,430 --> 00:35:15,300 Więc zainicjowany go początkowo null. 836 00:35:15,300 --> 00:35:16,410 837 00:35:16,410 --> 00:35:19,770 Ale to co zrobiliśmy, gdy będziemy były wewnątrz naszej funkcji wyszukiwania? 838 00:35:19,770 --> 00:35:20,940 839 00:35:20,940 --> 00:35:24,870 Stawiamy to równa pierwsze, co nie znaczy to zrobić. 840 00:35:24,870 --> 00:35:25,890 841 00:35:25,890 --> 00:35:30,570 Jeżeli ustawić ptr równą pierwsze, co Naprawdę powinna być moja ręka wskazując na? 842 00:35:30,570 --> 00:35:31,070 Prawo. 843 00:35:31,070 --> 00:35:33,290 Więc jeśli Gabe i ja być równe wartości tutaj, 844 00:35:33,290 --> 00:35:34,760 musimy zarówno miejsca, w liczbie 9. 845 00:35:34,760 --> 00:35:36,420 >> Więc to był początek naszej historii. 846 00:35:36,420 --> 00:35:38,700 A teraz jest to tylko proste, chociaż składni jest nowy. 847 00:35:38,700 --> 00:35:40,580 Koncepcyjnie to tylko liniowy wyszukiwania. 848 00:35:40,580 --> 00:35:42,750 Czy 55 równa 9? 849 00:35:42,750 --> 00:35:45,559 Albo raczej, powiedzmy mniej niż 9. 850 00:35:45,559 --> 00:35:47,600 Ponieważ staram się dowiedzieć się, gdzie umieścić 55. 851 00:35:47,600 --> 00:35:51,270 Mniej niż 9, mniej niż 17, mniej niż 20, mniej niż 22, mniej niż 29, 852 00:35:51,270 --> 00:35:52,510 mniej niż 34, no. 853 00:35:52,510 --> 00:35:55,080 Tak więc teraz jesteśmy w przypadku jeden z co najmniej trzech. 854 00:35:55,080 --> 00:35:59,910 >> Jeśli chcę wstawić 55 tu, co linii kodu konieczności zostanie wykonany? 855 00:35:59,910 --> 00:36:01,890 Jak to wygląda ludzie muszą się zmienić? 856 00:36:01,890 --> 00:36:03,181 Co mam zrobić z moją lewą ręką? 857 00:36:03,181 --> 00:36:04,530 858 00:36:04,530 --> 00:36:07,360 To powinno być null początkowo, ponieważ ja na koniec listy. 859 00:36:07,360 --> 00:36:09,318 A co powinno się zdarzyć tutaj z Piotrem, prawda? 860 00:36:09,318 --> 00:36:10,520 861 00:36:10,520 --> 00:36:12,430 On oczywiście będzie zwrócić się do mnie. 862 00:36:12,430 --> 00:36:15,580 Więc twierdzić tam co najmniej dwie linie kodu w kodzie próbki od dzisiaj 863 00:36:15,580 --> 00:36:18,570 , że zamierza wdrożyć to Scenariusz dodając 55 w ogonie. 864 00:36:18,570 --> 00:36:20,950 I mógłbym kogoś hop się i po prostu reprezentują 55? 865 00:36:20,950 --> 00:36:22,200 Dobra, jesteś nowy 55. 866 00:36:22,200 --> 00:36:23,580 867 00:36:23,580 --> 00:36:27,054 >> I co teraz, czy w przyszłym Scenariusz przychodzi, 868 00:36:27,054 --> 00:36:29,720 i chcemy włożyć w rozpoczynających lub szef tej liście? 869 00:36:29,720 --> 00:36:31,100 A jak masz na imię, numer 55? 870 00:36:31,100 --> 00:36:31,420 >> PUBLICZNOŚCI: Jack. 871 00:36:31,420 --> 00:36:32,295 >> David J. MALAN: Jack? 872 00:36:32,295 --> 00:36:33,585 OK, miło cię poznać. 873 00:36:33,585 --> 00:36:34,210 Witamy na pokładzie. 874 00:36:34,210 --> 00:36:36,640 Więc teraz jedziemy do wstawić, powiedzmy, liczbę 5. 875 00:36:36,640 --> 00:36:39,840 Oto druga sprawa trzy wpadliśmy wcześniej. 876 00:36:39,840 --> 00:36:43,050 Tak więc, jeśli 5 należy na początku Zobaczmy, w jaki sposób się tego dowiedzieć. 877 00:36:43,050 --> 00:36:46,310 Zainicjować moje ptr wskaźnik do liczby 9 ponownie. 878 00:36:46,310 --> 00:36:49,140 I zdałem sobie sprawę, o, 5 jest mniejsza niż 9. 879 00:36:49,140 --> 00:36:50,880 Więc rozwiązać ten obraz dla nas. 880 00:36:50,880 --> 00:36:54,820 Których ręce, Gabe i Dawida or-- co to za nazwa numer 9? 881 00:36:54,820 --> 00:36:55,740 >> PUBLICZNOŚCI: Jen. 882 00:36:55,740 --> 00:36:58,406 >> David J. MALAN: hands-- Jen które z naszych rękach trzeba zmienić? 883 00:36:58,406 --> 00:36:58,905 884 00:36:58,905 --> 00:37:00,970 OK, więc Gabe wskazuje na co teraz? 885 00:37:00,970 --> 00:37:01,640 Na mnie. 886 00:37:01,640 --> 00:37:02,750 Jestem nowy węzeł. 887 00:37:02,750 --> 00:37:04,870 Więc będę po prostu rodzaj ruchu tutaj, aby go zobaczyć wizualnie. 888 00:37:04,870 --> 00:37:06,435 A tymczasem to, co mogę podkreślić, że? 889 00:37:06,435 --> 00:37:07,910 890 00:37:07,910 --> 00:37:09,020 Jeszcze gdzie mam wskazując. 891 00:37:09,020 --> 00:37:10,000 Tak, to jest to. 892 00:37:10,000 --> 00:37:13,717 Tak naprawdę tylko jeden wiersz kodu poprawek ten konkretny problem, wydaje się. 893 00:37:13,717 --> 00:37:14,800 Wszystko w porządku, więc to jest dobre. 894 00:37:14,800 --> 00:37:17,580 A może ktoś być zastępczym dla 5? 895 00:37:17,580 --> 00:37:18,080 Chodź na górę. 896 00:37:18,080 --> 00:37:20,270 897 00:37:20,270 --> 00:37:21,320 My się następnym razem. 898 00:37:21,320 --> 00:37:24,280 >> Dobra, i tak teraz-- Tak na marginesie, nazwy 899 00:37:24,280 --> 00:37:28,510 Nie mam co wyraźnie o prawo teraz, pred wskaźnik, wskaźnik poprzednika 900 00:37:28,510 --> 00:37:31,260 i nowy wskaźnik, który znajduje się podano tylko nazwy 901 00:37:31,260 --> 00:37:35,280 w przykładowy kod do wskaźników lub moje ręce, że niby wskazujące wokół. 902 00:37:35,280 --> 00:37:36,060 Jak masz na imię? 903 00:37:36,060 --> 00:37:36,700 >> PUBLICZNOŚCI: Christine. 904 00:37:36,700 --> 00:37:37,100 >> David J. MALAN: Christine. 905 00:37:37,100 --> 00:37:38,090 Witamy na pokładzie. 906 00:37:38,090 --> 00:37:42,180 W porządku, więc rozważmy teraz nieco irytujące scenariusz, 907 00:37:42,180 --> 00:37:46,350 w którym chcę wstawić coś jak 26 do tego. 908 00:37:46,350 --> 00:37:47,090 20? 909 00:37:47,090 --> 00:37:47,590 Co? 910 00:37:47,590 --> 00:37:50,510 Są are-- dobrą rzeczą mamy ten długopis. 911 00:37:50,510 --> 00:37:51,955 Wszystko w porządku, 20. 912 00:37:51,955 --> 00:37:53,640 913 00:37:53,640 --> 00:37:57,570 Jeśli ktoś może dostać inny kawałek papier gotowy, tylko w case-- porządku. 914 00:37:57,570 --> 00:37:58,370 O, ciekawe. 915 00:37:58,370 --> 00:37:59,760 916 00:37:59,760 --> 00:38:02,390 Cóż to jest przykład buga wykładowej. 917 00:38:02,390 --> 00:38:03,894 OK, więc jak masz na imię? 918 00:38:03,894 --> 00:38:04,560 PUBLICZNOŚCI: Julia. 919 00:38:04,560 --> 00:38:07,559 David J. MALAN: Julia, można pop się i udawać, że nigdy tam nie byłeś? 920 00:38:07,559 --> 00:38:09,040 OK, to się nigdy nie wydarzyło. 921 00:38:09,040 --> 00:38:09,680 Dziękujemy. 922 00:38:09,680 --> 00:38:12,180 Więc załóżmy, że chcemy wstawić Julia do tego połączonej listy. 923 00:38:12,180 --> 00:38:13,780 Jest to ilość 20. 924 00:38:13,780 --> 00:38:15,530 I oczywiście, że jest będzie należeć w 925 00:38:15,530 --> 00:38:17,521 begin-- nie wskazują na coś jeszcze. 926 00:38:17,521 --> 00:38:20,020 Więc twoja ręka może być rodzaj w dół zerowy lub niektóre wartość śmieci. 927 00:38:20,020 --> 00:38:21,210 Powiedzmy szybką historię. 928 00:38:21,210 --> 00:38:22,980 Jestem wskazując na numer 5 to czasu. 929 00:38:22,980 --> 00:38:23,880 Potem sprawdź 9. 930 00:38:23,880 --> 00:38:25,130 Potem sprawdzić 17. 931 00:38:25,130 --> 00:38:26,247 Potem sprawdzić 22. 932 00:38:26,247 --> 00:38:27,650 933 00:38:27,650 --> 00:38:32,485 I zdaję sobie sprawę, ooh, Julia musi iść przed 22. 934 00:38:32,485 --> 00:38:33,580 935 00:38:33,580 --> 00:38:34,660 Więc to, co musi się zdarzyć? 936 00:38:34,660 --> 00:38:35,786 937 00:38:35,786 --> 00:38:36,910 Których ręce trzeba zmienić? 938 00:38:36,910 --> 00:38:38,360 Julia, moja, or-- jak masz na imię? 939 00:38:38,360 --> 00:38:39,230 >> PUBLICZNOŚCI: Christian. 940 00:38:39,230 --> 00:38:40,060 >> David J. MALAN: Christian lub? 941 00:38:40,060 --> 00:38:40,560 >> PUBLICZNOŚCI: Andy. 942 00:38:40,560 --> 00:38:40,905 >> David J. MALAN: Andy. 943 00:38:40,905 --> 00:38:41,654 Christian lub Andy? 944 00:38:41,654 --> 00:38:44,280 945 00:38:44,280 --> 00:38:45,690 Andy musi wskazać na? 946 00:38:45,690 --> 00:38:46,780 947 00:38:46,780 --> 00:38:47,341 Julia. 948 00:38:47,341 --> 00:38:47,840 Wszystko w porządku. 949 00:38:47,840 --> 00:38:48,960 Tak Andy, chcesz zwrócić na Julia? 950 00:38:48,960 --> 00:38:50,120 Ale chwileczkę. 951 00:38:50,120 --> 00:38:53,260 W historii do tej pory, Jestem jakby jednym 952 00:38:53,260 --> 00:38:56,800 w ładunku, w tym sensie, że wskaźnik jest rzeczą, która jest 953 00:38:56,800 --> 00:38:57,850 przemieszczania się po liście. 954 00:38:57,850 --> 00:39:00,800 Możemy mieć nazwę Andy, ale nie ma zmienną o nazwie Andy. 955 00:39:00,800 --> 00:39:04,320 Tylko inne mamy, jest zmienna Pierwszy, który reprezentuje Gabe. 956 00:39:04,320 --> 00:39:07,690 >> Więc to jest naprawdę, dlaczego w ten sposób pory nie potrzebowaliśmy tego. 957 00:39:07,690 --> 00:39:10,846 Ale teraz na ekranie jest wspomnieć jeszcze o pred wskaźnika. 958 00:39:10,846 --> 00:39:11,970 Więc pozwól mi być bardziej wyraźne. 959 00:39:11,970 --> 00:39:14,820 Jeśli jest to wskaźnik, miałem lepsze trochę bardziej inteligentny 960 00:39:14,820 --> 00:39:15,950 o mojej iteracji. 961 00:39:15,950 --> 00:39:19,580 Jeśli nie masz nic przeciwko moim przechodzi tutaj ponownie, wskazując tutaj, wskazując tutaj. 962 00:39:19,580 --> 00:39:22,500 Ale pozwól mi mieć pred wskaźnik, wskaźnik poprzednika, to 963 00:39:22,500 --> 00:39:24,740 rodzaj, wskazując na Element Byłem na. 964 00:39:24,740 --> 00:39:27,330 Więc kiedy wrócę tu, teraz Moja lewa ręka. aktualizacje 965 00:39:27,330 --> 00:39:29,370 Kiedy wrócę tu moja lewa aktualizacji ręcznych. 966 00:39:29,370 --> 00:39:33,090 A teraz mam nie tylko wskaźnik do Element, który idzie po Julia, 967 00:39:33,090 --> 00:39:36,300 Nadal mam wskaźnik do Andy elementem wcześniej. 968 00:39:36,300 --> 00:39:39,430 Więc masz dostęp, zasadniczo, bułka tarta, jeśli chcesz, 969 00:39:39,430 --> 00:39:41,500 do wszystkich wymaganych wskaźników. 970 00:39:41,500 --> 00:39:43,710 >> Więc jeśli ja, wskazując na Andy i ja również wskazując 971 00:39:43,710 --> 00:39:47,105 w ręce chrześcijan, którego Należy teraz wskazać gdzie indziej? 972 00:39:47,105 --> 00:39:48,770 973 00:39:48,770 --> 00:39:51,960 Więc Andy może teraz zwrócić się Julia. 974 00:39:51,960 --> 00:39:54,460 Julia może teraz wskazać na chrześcijanina. 975 00:39:54,460 --> 00:39:56,950 Bo można skopiować mój wskaźnik prawicy za. 976 00:39:56,950 --> 00:40:00,044 Oraz że skutecznie stawia się z powrotem na to miejsce tutaj. 977 00:40:00,044 --> 00:40:02,460 Tak więc, w skrócie, chociaż zabiera nas rodzaj wiecznie 978 00:40:02,460 --> 00:40:04,510 faktycznie zaktualizować lista powiązana, realizować 979 00:40:04,510 --> 00:40:06,580 że operacje są stosunkowo proste. 980 00:40:06,580 --> 00:40:10,030 To o jeden, dwa, trzy linii kodu ostatecznie. 981 00:40:10,030 --> 00:40:12,780 Ale owinięte wokół tych linii kodu przypuszczalnie 982 00:40:12,780 --> 00:40:16,350 jest nieco logiki, które skutecznie zadaje pytanie, gdzie jesteśmy? 983 00:40:16,350 --> 00:40:18,970 Jesteśmy na początku, środkowy lub końcowy? 984 00:40:18,970 --> 00:40:21,890 >> Obecnie istnieją oczywiście inna Operacje możemy realizować. 985 00:40:21,890 --> 00:40:24,880 I tu właśnie przedstawiają te zdjęcia co właśnie zrobił z ludzi. 986 00:40:24,880 --> 00:40:26,080 Co o usunięciu? 987 00:40:26,080 --> 00:40:30,650 Jeśli chcę, aby, na przykład, usunąć numer 34 lub 55, 988 00:40:30,650 --> 00:40:34,680 Może mam ten sam rodzaj kodu, ale będę potrzebować jednego lub dwóch etapów. 989 00:40:34,680 --> 00:40:36,110 Bo to, co nowego? 990 00:40:36,110 --> 00:40:40,460 Jeśli usunąć kogoś na koniec, jak numer 55 i 34, 991 00:40:40,460 --> 00:40:42,995 co ma również zmienić, jak to zrobić? 992 00:40:42,995 --> 00:40:44,870 Muszę nie evict-- jak masz na imię? 993 00:40:44,870 --> 00:40:45,380 >> PUBLICZNOŚCI: Jack. 994 00:40:45,380 --> 00:40:46,255 >> David J. MALAN: Jack. 995 00:40:46,255 --> 00:40:49,770 Mam nie tylko evict-- darmo Jack, tak dosłownie telefonować Jack, lub przynajmniej 996 00:40:49,770 --> 00:40:53,530 Wskaźnik jest też jednak teraz co trzeba zmienić z Peterem? 997 00:40:53,530 --> 00:40:55,510 Jego ręka lepiej zacząć wskazując w dół. 998 00:40:55,510 --> 00:40:59,300 Bo jak tylko zadzwonić bezpłatnie na Jack, czy Piotra wciąż wskazując na Jacka 999 00:40:59,300 --> 00:41:02,530 i dlatego trzymam przejeżdżające lista i dostęp ten wskaźnik, 1000 00:41:02,530 --> 00:41:05,650 wtedy nasz stary przyjaciel segmentacja winy może faktycznie kopać. 1001 00:41:05,650 --> 00:41:07,860 Bo dałeś pamięci z powrotem do Jacka. 1002 00:41:07,860 --> 00:41:10,760 >> Można tam niezgrabnie na chwilę. 1003 00:41:10,760 --> 00:41:13,410 Ponieważ mamy tylko kilka Czynności końcowe do rozważenia. 1004 00:41:13,410 --> 00:41:15,600 Usuwanie głowę listy, lub beginning-- i ten jest 1005 00:41:15,600 --> 00:41:16,349 trochę denerwujące. 1006 00:41:16,349 --> 00:41:19,640 Ponieważ musimy wiedzieć, że Gabe to rodzaj specjalnego w tym programie. 1007 00:41:19,640 --> 00:41:21,440 Bo rzeczywiście, on ma swój własny wskaźnik. 1008 00:41:21,440 --> 00:41:24,860 On nie tylko jest wskazał, jak prawie wszyscy tutaj. 1009 00:41:24,860 --> 00:41:28,112 >> Kiedy więc szef liście jest usunięte, których ręce trzeba zmienić teraz? 1010 00:41:28,112 --> 00:41:29,070 Jak masz na imię? 1011 00:41:29,070 --> 00:41:29,450 >> PUBLICZNOŚCI: Christine. 1012 00:41:29,450 --> 00:41:31,408 >> David J. MALAN: Jestem strasznie w nazwach, najwyraźniej. 1013 00:41:31,408 --> 00:41:34,011 Więc Christine i Gabe, których ręce trzeba zmienić 1014 00:41:34,011 --> 00:41:36,510 gdy próbujemy usunąć Christine, numer 5, z obrazka? 1015 00:41:36,510 --> 00:41:37,550 1016 00:41:37,550 --> 00:41:38,820 OK, więc zróbmy Gabe. 1017 00:41:38,820 --> 00:41:40,950 Gabe będzie wskazywać, przypuszczalnie w liczbie 9. 1018 00:41:40,950 --> 00:41:42,230 1019 00:41:42,230 --> 00:41:44,642 Ale co dalej się stanie? 1020 00:41:44,642 --> 00:41:46,600 PUBLICZNOŚCI: Christine powinna być null [niesłyszalne]. 1021 00:41:46,600 --> 00:41:50,244 David J. MALAN: OK, powinniśmy prawdopodobnie make-- usłyszałem "null" gdzieś. 1022 00:41:50,244 --> 00:41:51,410 PUBLICZNOŚCI: Null i jej wolne. 1023 00:41:51,410 --> 00:41:51,855 David J. MALAN: null co? 1024 00:41:51,855 --> 00:41:53,074 PUBLICZNOŚCI: Null i jej wolne. 1025 00:41:53,074 --> 00:41:54,490 David J. MALAN: Null i jej wolne. 1026 00:41:54,490 --> 00:41:55,422 Więc to jest bardzo proste. 1027 00:41:55,422 --> 00:41:58,380 I to jest doskonały, że jesteś teraz sortowania stojącego tam, nie należące. 1028 00:41:58,380 --> 00:42:00,430 Ponieważ byli oddzielone od listy. 1029 00:42:00,430 --> 00:42:02,820 Ty rzeczywiście zostały osieroconych z listy. 1030 00:42:02,820 --> 00:42:07,770 A więc lepiej zadzwonić za darmo teraz Christine dać, że pamięć z powrotem. 1031 00:42:07,770 --> 00:42:10,240 Za każdym razem w inny sposób usunąć węzeł z listy 1032 00:42:10,240 --> 00:42:14,230 możemy być sporządzaniu listy krótszy, ale w rzeczywistości nie maleje 1033 00:42:14,230 --> 00:42:15,096 rozmiar pamięci. 1034 00:42:15,096 --> 00:42:17,720 A więc jeśli będziemy dodawać i dodając, dodając rzeczy do listy, 1035 00:42:17,720 --> 00:42:19,280 komputer może się wolniej i wolniej i wolniej, 1036 00:42:19,280 --> 00:42:21,740 bo jestem na wyczerpaniu pamięci, nawet jeśli w rzeczywistości nie jestem 1037 00:42:21,740 --> 00:42:25,580 za pomocą bajtów Christine z pamięci więcej. 1038 00:42:25,580 --> 00:42:28,500 >> A więc w końcu istnieje inne scenariusze, z course-- usunięcia 1039 00:42:28,500 --> 00:42:30,640 w środku, usuwanie Na koniec, jak widzieliśmy. 1040 00:42:30,640 --> 00:42:32,348 Ale bardziej interesujące wyzwaniem jest 1041 00:42:32,348 --> 00:42:34,770 będzie dokładnie rozważyć Czas pracy, co jest. 1042 00:42:34,770 --> 00:42:36,640 Więc nie tylko można zachować kawałki papieru, jeśli, Gabe, 1043 00:42:36,640 --> 00:42:38,640 nie masz nic przeciwko dając każdy piłka stres. 1044 00:42:38,640 --> 00:42:42,100 Dziękuję bardzo do naszej listy wolontariuszy tutaj, jeśli można. 1045 00:42:42,100 --> 00:42:45,320 >> [Aplauz] 1046 00:42:45,320 --> 00:42:46,700 >> David J. MALAN: Wszystko w porządku. 1047 00:42:46,700 --> 00:42:51,110 Więc kilka analityczna pytania, następnie, jeśli będę mógł. 1048 00:42:51,110 --> 00:42:59,670 Widzieliśmy ten zapis przed, Big O i omega, górne granice 1049 00:42:59,670 --> 00:43:02,520 i dolne granice na czas jakiś algorytm działa. 1050 00:43:02,520 --> 00:43:04,950 Warto więc wziąć pod uwagę tylko kilka pytań. 1051 00:43:04,950 --> 00:43:07,090 >> Jeden, i powiedział, że wcześniej, co jest uruchomiony 1052 00:43:07,090 --> 00:43:10,647 czas poszukiwania lista w zakresie Big O? 1053 00:43:10,647 --> 00:43:13,480 Co znajduje się górne ograniczenie na prowadzeniu czas poszukiwania połączonej listy 1054 00:43:13,480 --> 00:43:16,340 wdrożone przez naszych wolontariuszy tutaj? 1055 00:43:16,340 --> 00:43:17,820 To wielki O n, liniowy. 1056 00:43:17,820 --> 00:43:20,630 Ponieważ w najgorszym wypadku elementem, podobnie jak 55, 1057 00:43:20,630 --> 00:43:23,830 możemy szukać, gdzie może być Gniazdo to wszystkie sposób na końcu. 1058 00:43:23,830 --> 00:43:28,250 I niestety, w przeciwieństwie do tablicy nie możemy się ochotę tym razem. 1059 00:43:28,250 --> 00:43:31,820 Mimo, że wszyscy nasi ludzie byli sortowane od małych elementów, 5, 1060 00:43:31,820 --> 00:43:35,900 wszystko aż do większego elementu 55, który jest zazwyczaj dobrze. 1061 00:43:35,900 --> 00:43:38,815 Ale co to założenie nie pozwalają nam robić? 1062 00:43:38,815 --> 00:43:39,775 1063 00:43:39,775 --> 00:43:40,650 PUBLICZNOŚCI: [niesłyszalne] 1064 00:43:40,650 --> 00:43:40,920 David J. MALAN: Powiedz jeszcze raz? 1065 00:43:40,920 --> 00:43:41,800 PUBLICZNOŚCI: Random dostęp. 1066 00:43:41,800 --> 00:43:43,049 David J. MALAN: Random dostęp. 1067 00:43:43,049 --> 00:43:46,330 A to z kolei oznacza, że ​​nie możemy już używać słabego zer, intuicji, 1068 00:43:46,330 --> 00:43:49,365 i oczywistość za pomocą binarnego wyszukiwać i dziel i rządź. 1069 00:43:49,365 --> 00:43:51,240 Bo chociaż ludzie mogli oczywiście 1070 00:43:51,240 --> 00:43:54,610 zobaczyć, że Andy i Christian byli mniej więcej w połowie listy 1071 00:43:54,610 --> 00:43:57,670 wiemy tylko, że jak Komputer zebranie z listy 1072 00:43:57,670 --> 00:43:59,029 od samego początku. 1073 00:43:59,029 --> 00:44:00,570 Więc daliśmy się, że swobodny dostęp. 1074 00:44:00,570 --> 00:44:04,380 >> Tak duże O n jest górna związany na naszego czasu wyszukiwania. 1075 00:44:04,380 --> 00:44:07,920 Co omega naszego wyszukiwania? 1076 00:44:07,920 --> 00:44:11,535 Co znajduje się dolne ograniczenie na poszukiwania dla pewnej liczby w tym liście? 1077 00:44:11,535 --> 00:44:12,410 PUBLICZNOŚCI: [niesłyszalne] 1078 00:44:12,410 --> 00:44:13,040 David J. MALAN: Powiedz jeszcze raz? 1079 00:44:13,040 --> 00:44:13,420 PUBLICZNOŚCI: Jeden. 1080 00:44:13,420 --> 00:44:13,800 David J. MALAN: Jeden. 1081 00:44:13,800 --> 00:44:14,760 Tak więc stała czasowa. 1082 00:44:14,760 --> 00:44:17,020 W najlepszym przypadku, Christine w rzeczywistości na początku listy. 1083 00:44:17,020 --> 00:44:19,020 I szukamy Numer 5, więc ją znaleźć. 1084 00:44:19,020 --> 00:44:19,787 Więc nic wielkiego. 1085 00:44:19,787 --> 00:44:22,370 Ale ona ma być na początku listy w tej sprawie. 1086 00:44:22,370 --> 00:44:23,745 Co o czymś jak Delete? 1087 00:44:23,745 --> 00:44:24,717 1088 00:44:24,717 --> 00:44:26,300 Co zrobić, jeśli chcesz usunąć element? 1089 00:44:26,300 --> 00:44:29,200 Co znajduje się górna granica i dolna granica na usuwanie coś związane z 1090 00:44:29,200 --> 00:44:29,699 listy? 1091 00:44:29,699 --> 00:44:35,195 1092 00:44:35,195 --> 00:44:36,070 PUBLICZNOŚCI: [niesłyszalne] 1093 00:44:36,070 --> 00:44:36,420 David J. MALAN: Powiedz jeszcze raz? 1094 00:44:36,420 --> 00:44:37,067 PUBLICZNOŚCI: brak. 1095 00:44:37,067 --> 00:44:38,900 David J. MALAN: n rzeczywiście górna granica. 1096 00:44:38,900 --> 00:44:41,700 Ponieważ w najgorszym przypadku staramy usunąć Jack, jak my właśnie zrobiliśmy. 1097 00:44:41,700 --> 00:44:43,050 On jest wszystkim sposobem na końcu. 1098 00:44:43,050 --> 00:44:45,419 Zabiera nas na zawsze, lub n kroków, aby go odnaleźć. 1099 00:44:45,419 --> 00:44:46,460 Więc to jest górna granica. 1100 00:44:46,460 --> 00:44:47,430 To jest liniowa, na pewno. 1101 00:44:47,430 --> 00:44:50,970 A najlepszym przypadku czas pracy, lub dolne granice w najlepszym wypadku 1102 00:44:50,970 --> 00:44:51,975 będzie stała czasowa. 1103 00:44:51,975 --> 00:44:54,600 Bo może spróbować usunąć Christine, i po prostu miał szczęście 1104 00:44:54,600 --> 00:44:55,558 ona jest na początku. 1105 00:44:55,558 --> 00:44:56,350 Chwileczkę. 1106 00:44:56,350 --> 00:44:59,370 Gabe również na początku i mieliśmy również zaktualizować Gabe. 1107 00:44:59,370 --> 00:45:01,150 Tak, że nie było tylko jeden krok. 1108 00:45:01,150 --> 00:45:04,210 Tak więc jest to rzeczywiście stała Czas, w najlepszym przypadku, 1109 00:45:04,210 --> 00:45:06,345 , aby usunąć najmniejsze elementu? 1110 00:45:06,345 --> 00:45:07,360 1111 00:45:07,360 --> 00:45:10,960 To znaczy, nawet jeżeli mogłyby być dwa trzy, albo nawet 100 linii kodu, 1112 00:45:10,960 --> 00:45:14,000 czy to ta sama liczba linie, nie w jakiejś pętli, 1113 00:45:14,000 --> 00:45:16,577 i niezależnie od rozmiarów z listy, absolutnie. 1114 00:45:16,577 --> 00:45:18,660 Usuwanie elementu w początku listy 1115 00:45:18,660 --> 00:45:21,940 nawet jeśli mamy do czynienia z Gabe jest nadal stała czasowa. 1116 00:45:21,940 --> 00:45:24,220 >> Tak więc wydaje się, że jak ogromny krok wstecz. 1117 00:45:24,220 --> 00:45:27,000 A co stratą czasu jeśli w jednym tygodniu tydzień 1118 00:45:27,000 --> 00:45:30,250 zera mieliśmy nie tylko Kod pseudokod, ale rzeczywisty kod 1119 00:45:30,250 --> 00:45:35,780 wdrożyć coś, co jest dziennik Podstawa n lub log, a, n, podstawa 2, 1120 00:45:35,780 --> 00:45:37,150 w zakresie jego czasu pracy. 1121 00:45:37,150 --> 00:45:40,710 Więc dlaczego do cholery nie chcemy, aby rozpocząć przy użyciu coś jak połączonej listy? 1122 00:45:40,710 --> 00:45:41,517 Tak. 1123 00:45:41,517 --> 00:45:44,022 >> PUBLICZNOŚCI: Więc możesz dodać elementy do tablicy. 1124 00:45:44,022 --> 00:45:46,230 David J. MALAN: Więc możesz dodawanie elementów do tablicy. 1125 00:45:46,230 --> 00:45:47,550 I to też jest tematyczna. 1126 00:45:47,550 --> 00:45:49,740 A my nadal zobaczyć to, to kompromis, znacznie 1127 00:45:49,740 --> 00:45:51,573 jak widzieliśmy kompromis z seryjnej rodzaju. 1128 00:45:51,573 --> 00:45:54,606 Możemy naprawdę przyspieszyć wyszukiwania i sortowania, a, 1129 00:45:54,606 --> 00:45:57,480 jeśli spędzić trochę więcej miejsca i mają dodatkowy fragment pamięci 1130 00:45:57,480 --> 00:45:58,760 lub tablica do seryjnej rodzaju. 1131 00:45:58,760 --> 00:46:01,270 Ale spędzamy więcej przestrzeń, ale zaoszczędzić czas. 1132 00:46:01,270 --> 00:46:04,820 W tym przypadku mamy dając się czas, ale jesteśmy 1133 00:46:04,820 --> 00:46:08,170 zyskuje elastyczność, dynamizm, jeśli chcesz, 1134 00:46:08,170 --> 00:46:10,280 która niewątpliwie jest pozytywną cechą. 1135 00:46:10,280 --> 00:46:11,520 >> Jesteśmy również spędzać miejsca. 1136 00:46:11,520 --> 00:46:13,710 W jakim sensie jest powiązana listy droższe 1137 00:46:13,710 --> 00:46:15,700 w zakresie miejsca niż tablicy? 1138 00:46:15,700 --> 00:46:18,379 1139 00:46:18,379 --> 00:46:19,920 Gdzie jest dodatkowa przestrzeń pochodzi? 1140 00:46:19,920 --> 00:46:20,460 Tak? 1141 00:46:20,460 --> 00:46:21,800 >> PUBLICZNOŚCI: [niesłyszalne] wskaźnik. 1142 00:46:21,800 --> 00:46:23,310 >> David J. MALAN: Tak, również wskaźnik. 1143 00:46:23,310 --> 00:46:25,560 Więc to jest minorly irytujące że nie am 1144 00:46:25,560 --> 00:46:27,780 Ja przechowywania tylko int do reprezentowania int. 1145 00:46:27,780 --> 00:46:30,990 Jestem przechowywania int i A wskaźnik, który jest 32 bitów. 1146 00:46:30,990 --> 00:46:33,470 Więc jestem dosłownie podwojenie Ilość miejsca zaangażowany. 1147 00:46:33,470 --> 00:46:36,040 Więc to jest kompromis, ale to w przypadku int. 1148 00:46:36,040 --> 00:46:39,580 Załóżmy, że nie jesteś przechowywania int, ale przypuszczam, każdy z tych prostokątów 1149 00:46:39,580 --> 00:46:43,290 lub każdy z tych ludzi reprezentował Słowo, angielskie słowo, które 1150 00:46:43,290 --> 00:46:46,430 może być pięć znaków, 10 znaków, a może nawet więcej. 1151 00:46:46,430 --> 00:46:49,940 Następnie dodanie zaledwie 32 więcej bitów może być mniejsza od wielkiego. 1152 00:46:49,940 --> 00:46:52,160 >> Co zrobić, jeśli każdy z uczniów w demonstracji 1153 00:46:52,160 --> 00:46:55,107 były uczeń, który dosłownie elemencie mają nazwy i domy a może 1154 00:46:55,107 --> 00:46:57,065 numery telefonów i Twitter uchwyty i podobne. 1155 00:46:57,065 --> 00:46:59,564 Więc wszystkie pola zaczęliśmy mówić o innym dniu, 1156 00:46:59,564 --> 00:47:02,410 znacznie mniej wielkiego jak Nasze węzły uzyskać bardziej interesujące 1157 00:47:02,410 --> 00:47:05,972 i duże, aby spędzić, co, dodatkowe wskaźnik po prostu połączyć je ze sobą. 1158 00:47:05,972 --> 00:47:07,180 Ale rzeczywiście, jest to kompromis. 1159 00:47:07,180 --> 00:47:09,560 I rzeczywiście, kod jest bardziej złożone, jak będziesz 1160 00:47:09,560 --> 00:47:11,770 zobacz zebranie przez że konkretny przykład. 1161 00:47:11,770 --> 00:47:14,302 Ale co, jeśli nie było jakiś święty graal tutaj. 1162 00:47:14,302 --> 00:47:17,010 Co, jeśli nie zrobić krok do tyłu, ale ogromny krok do przodu 1163 00:47:17,010 --> 00:47:19,180 i wdrożenie danych Struktura poprzez które 1164 00:47:19,180 --> 00:47:22,870 można znaleźć elementy, takie jak Jack lub Christine lub inne elementy 1165 00:47:22,870 --> 00:47:25,870 w tej tablicy w prawdziwej stałym czasie? 1166 00:47:25,870 --> 00:47:26,920 Szukaj jest stała. 1167 00:47:26,920 --> 00:47:28,320 Usuń jest stała. 1168 00:47:28,320 --> 00:47:29,570 Wkładka jest stała. 1169 00:47:29,570 --> 00:47:32,260 Wszystkie te operacje są stałe. 1170 00:47:32,260 --> 00:47:33,750 To byłby nasz Święty Graal. 1171 00:47:33,750 --> 00:47:36,690 I to jest miejsce, gdzie wzrośnie następnym razem. 1172 00:47:36,690 --> 00:47:38,600 Do zobaczenia. 1173 00:47:38,600 --> 00:47:39,371