[MUZYKA GRA] David J. MALAN: Wszystko w porządku. To CS50. To jest tydzień pięć kontynuowane, a my dobre wieści i złe wieści. Więc dobrą wiadomością jest to, że CS50 uruchamia w ten piątek. Jeśli chcesz do nas dołączyć, udać się do zwykłej zawartości tutaj. Nawet lepsze wiadomości, nie wykład w najbliższy poniedziałek 13. Nieco mniej lepsze wieści, Quiz zero środę. Więcej informacji można znaleźć pod tym adresem URL tutaj. A w ciągu najbliższych kilku dni będziemy wypełnienie luki w odniesieniu do pomieszczeń które mamy zastrzeżone. Lepsze jest to, że nie będzie jest ocena całego kursu Sesja ta nadchodzi Poniedziałek wieczorem. Stay tuned się oczywiście na strona lokalizacji i szczegółów. Działy, nawet jeśli jest wakacje, spotka się również, jak również. Najlepszą wiadomością, wykład w następny piątek. Tak to jest, że tradycja mają, zgodnie z programem szkolenia. Tylko-- to będzie niesamowite. Będzie można zobaczyć takie rzeczy jak Stała czasu struktury danych i tabele mieszania i drzewa i próbuje. I porozmawiamy o problemach urodziny. Cała masa rzeczy czeka na następny piątek. OK. Tak czy inaczej. Więc przypomnieć, że byliśmy koncentrując się na tym obrazie, co jest wewnątrz pamięci naszego komputera. Więc pamięci lub pamięci RAM jest gdzie programy istnieć gdy jesteś ich prowadzenie. Po dwukrotnym kliknięciu ikonę, aby uruchomić jakiś program lub kliknij dwukrotnie ikonę, aby otworzyć jakiś plik, to ładowane z dysku dysk lub dysk SSD do pamięci RAM, Random Access Memory, gdzie żyje, aż do wyłączenia zasilania, Pokrywa zamyka laptopa, lub zamknięciu programu. 

Teraz, pamięci, z które prawdopodobnie masz 1 gigabajt te dni, 2 GB lub nawet znacznie bardziej, jest ogólnie określone dla danego programu w tego rodzaju prostokątnym model koncepcyjny przy czym to ma na dole stosu i kilka innych rzeczy na górze. Rzeczą na samym szczycie widzieliśmy na tym zdjęciu wcześniej, ale nigdy nie mówił o jest tak zwany segmentu tekstu. Segment tekst jest po prostu fantazyjny sposób mówić do zer i jedynek, które skomponuj swój rzeczywisty skompilowany program. 

Więc po dwukrotnym kliknięciem Microsoft Word na komputerze Mac lub PC, lub po uruchomieniu kropkę na slash Mario Komputer Linux w oknie terminala, zera i jedynki, które tworzą Słowo lub Mario są przechowywane tymczasowo w pamięci RAM komputera w tzw Segment tekstu dla danego programu. Poniżej w polu zainicjowany i dane niezainicjalizowane. To rzeczy, jak zmienne globalne, że nie używałem wielu, ale od czasu do czasu mamy miał zmienne globalne lub statycznie zdefiniowane ciągi jest mocno zakodowane słowa takie jak "cześć" nie są pobierane z użytkownikiem , które są zakodowane w programie. 

Teraz, na dole mamy mają tak zwany stos. I stos, do tej pory, już używając do jakiego rodzaju celów? Co stos używane do? Tak? 

WIDOWNI: Funkcje. 

David J. MALAN: Dla funkcji? W jakim sensie do funkcji? 

PUBLICZNOŚCI: Po wywołaniu funkcji, Argumenty są kopiowane na stos. 

David J. MALAN: Dokładnie. Podczas wywołania funkcji, jej Argumenty są kopiowane na stos. Więc wszelkie X lub Y jest w lub na lub B które przekazujemy do funkcji są tymczasowo umieścić na tak zwany stos, tak jak jednym Annenberg tace jadalni, a także rzeczy jak zmienne lokalne. Jeśli funkcja foo lub Twój Swap Funkcja ma zmienne lokalne, jak temp, te dwa kończy się na stosie. Teraz, nie będziemy mówić zbyt wiele o je, ale te zmienne środowiskowe na dole widzieliśmy jakiś czas temu, kiedy Byłem futzing na klawiaturze jeden dzień i zacząłem dostępu rzeczy jak argv 100 lub argv 1000, tylko elements-- zapomnę numbers-- ale nie miały być dostępne dla mnie. Zaczęliśmy widząc niektóre Funky symbole na ekranie. Były to tak zwane Zmienne środowiskowe jak dla moich ustawień globalnych program lub na moim komputerze, a nie niezwiązane z ostatnich błędów, które omówiliśmy, ShellShock, że było dręczące sporo komputerów. 

Teraz wreszcie, w dzisiejszym centrum uwagi my ostatecznie na stercie. To kolejny fragment pamięci. I to zasadniczo wszystkie pamięci jest taki sam materiał. To ten sam sprzęt. Jesteśmy po prostu rodzaj leczenia różnych klastrów bajtów do różnych celów. Kupa jest również, gdzie będzie zmienne i pamięci, że poprosisz od systemu operacyjnego są tymczasowo przechowywane. 

Ale jest to za błąd Tutaj jako obraz oznacza. Jesteśmy jakby mieć dwa zwykle około zderzają. Bo jak użyć bardziej stosu, i jak widzimy dzisiaj dalej, jak używać coraz więcej kupa, na pewno złe rzeczy mogą się zdarzyć. I rzeczywiście, że możemy wywoływać umyślnie lub nieumyślnie. Więc na cliffhanger ostatniego Czas był ten program, które nie służą wszelkie funkcjonalne celów innych niż w celu wykazania jak cię jak zły może rzeczywiście wziąć Zaletą błędów w czyimś programu i przejąć program lub nawet Cały system komputerowy lub serwer. Więc po prostu spojrzeć na krótko, ci zauważyć, że główny na dole odbywa się w linii poleceń argumenty, jak na argv. I ma połączenie z funkcji f, zasadniczo bezimienny funkcja o nazwie f, a to przechodząc w argv [1]. 

Więc cokolwiek słowo użytkownik wpisze w szybka po nazwie tego programu, , a następnie do tego dowolną funkcją Najwięcej, f, odbywa się w ciągu, AKA char *, jak zaczęliśmy dyskutować, i to właśnie nazywa to "bar". Ale możemy nazwać to coś. A następnie oświadcza, wewnątrz f, szereg znaków nazywa C-- 12 takich znaków. 

Teraz, przez historię mówiłem chwilą, gdy w pamięci jest c, to te 12 lub znaki skończy? Wystarczy być jasne. Tak? 

PUBLICZNOŚCI: Na stosie. 

David J. MALAN: Na stosie. Więc c jest zmienną lokalną. Pytamy do 12 znaków lub 12 bajtów. Te będą się kończyć na tak zwanym stosu. Teraz w końcu jest to inna funkcja to rzeczywiście bardzo przydatne, ale nie zostały rzeczywiście wykorzystane to sami, strncopy. Oznacza to, kopię ciąg, ale tylko litery n, n znaków. Tak będzie n znaków skopiowane z baru do c. I ile? Długość paska. Tak więc, innymi słowy, że jedna linia, strncopy, ma zamiar skopiować skutecznie bar w na c. 

Teraz, po prostu rodzaj przewidywania Morał z tej historii, co tu jest potencjalnie problematyczne? Mimo, że mamy do sprawdzania długości z barem i przekazania go do strncopy, Jaki jest Twój gut mówi Ci to wciąż podzielone na temat tego programu? Tak? 

PUBLICZNOŚCI: Nie obejmuje Pokój na znak null. David J. MALAN: Nie obejmuje Pokój na znak null. Potencjalnie przeciwieństwie dotychczasowa praktyka nie mamy nawet mają tyle jako plus 1 do przyjąć, że znak null. Ale jest jeszcze gorzej. Co jeszcze mamy nie robiąc? Tak? 

PUBLICZNOŚCI: [niesłyszalne] David J. MALAN: Perfect. Mamy 12 bardzo ciężko kodowane arbitralnie. To nie jest tak dużo problemem, ale fakt, że nie jesteśmy nawet sprawdzenie, czy Długość paska jest mniejsza niż 12 w tym przypadku będzie bezpiecznie umieścić w pamięci nazywa c, że mamy przydzielone. W rzeczywistości, jeżeli pasek jest podobny 20 znaków, Funkcja ta wydaje się kopiowanie 20 znaków z baru na C, a tym samym przy co najmniej 8 bajtów które nie powinny być. To jest implikacja tutaj. 

Tak w skrócie, wadliwy program. Nie taka wielka sprawa. Może masz winy segmentacji. Wszyscy mieliśmy błędów w programach. Może wszyscy mają błędy w programach teraz. Ale co to implikacja? Cóż, tutaj jest powiększony w wersji że obraz z pamięci mojego komputera. To jest dno mojego stosu. I rzeczywiście, na samym dole jest to, co jest nazywa rodzic rutynowych stos, fantazyjny sposób powiedzieć, że jest główną. Tak, aby każdy, kto nazywa się funkcja f, że mówimy. Tak więc jest na dole stosu. Adres zwrotny jest coś nowego. To zawsze było tam, zawsze w tym zdjęciu. Po prostu nigdy nie zwrócił uwagę na to. Ponieważ okazuje się, jest sposób c działa że gdy jedna funkcja wymaga innego, Nie tylko, że argumenty Funkcja get odkładany na stos, nie tylko lokalny funkcja jest zmienne się zepchnięci na stos, coś, co nazywa adres zwrotny także dostaje umieścić na stosie. W szczególności, jeśli główne połączenia Foo, Main własny adres w pamięci, wół coś, skutecznie dostaje umieścić na stosie tak, że gdy m odbywa się wykonywanie wie, gdzie wrócić w tekście Segment w celu dalszego wykonywania. 

Jeśli więc jesteśmy tutaj koncepcyjnie, w głównym, to f jest wywoływana. Jak nie wiesz, kto f do sterowania ręcznego z powrotem? Cóż, to trochę nawigacyjny na czerwono tutaj zwany adres zwrotny, to po prostu sprawdza, co to jest adres zwrotny? Och, pozwól mi wrócić do głównego tutaj. I to jest trochę z uproszczeniem, bo zer i jedynek do magistrali są technicznie tu w segmencie technologii. Ale to jest pomysł. f po prostu musi wiedzieć, co gdzie kontrola ostatecznie wraca. 

Ale sposób komputery już dawno określone rzeczy jak zmiennych lokalnych i argumentów jest tak. Więc w górę tego obrazu niebieskie ramki stosu jest dla f, więc wszystko z pamięci, że f konkretnie jest używany. Więc w związku z tym zauważyć, że Bar jest na tym zdjęciu. Bar był jej argument. I twierdził, że mamy do argumentów Funkcje się odkładany na stos. C, jest oczywiście również na tym zdjęciu. 

I tylko do celów notacji, zawiadomienia w górnym lewym rogu jest to, co będzie c 0 i wspornik następnie lekko w prawo w dół Uchwyt 11 jest c. Więc innymi słowy, można sobie wyobrazić, że istnieje siatka bajtów tam, z których pierwszy jest u góry po lewej, z których dolna jest ostatnim z tych 12 bajtów. 

Ale teraz staram się szybko do przodu. Co ma się wydarzyć, gdy mijamy w barze smyczkowy, który jest dłuższy niż c? A my nie sprawdzając, czy to rzeczywiście dłużej niż 12 lat. Która część tego obrazu będzie nadpisane przez bajtów, 0, 1, 2, 3, kropka kropka kropka, 11, a następnie źle, 12, 13 do 19? Co wydarzy się tutaj, jeśli wnioskować z zamówienia że wspornik c0 jest na szczycie c uchwyt 11 jest jakby w dół do porządku? Tak? 

PUBLICZNOŚCI: Cóż, to będzie zastąpić bar char *. 

David J. MALAN: Tak, wygląda na to, masz zamiar zastąpić char * poprzeczkę. A co gorsza, jeśli wyślesz w bardzo długo ciąg, może nawet zastąpić, co? Adres zwrotny. Co znowu, jest jak nawigacyjny powiedzieć program, w którym , aby wrócić do gdy f Odbywa się to miano. 

Więc co zrobić, źli zazwyczaj jest wtedy, gdy natknąłem się na programie że są ciekawi, czy jest do eksploatacji, wózek w taki sposób, że może on podjąć Zaletą tego błędu, ogólnie nie dostać to dobrze za pierwszym razem. Po prostu rozpocząć wysyłanie, na przykład losowe ciągi znaków do programu, czy na klawiaturze, i szczerze mówiąc, że prawdopodobnie Napisać mały program do tylko automatycznie generować ciągi, i zacząć walić w programie przez wysyłanie w wielu różnych wejść o różnych długościach. 

Jak tylko awarii programu, to jest niesamowite. Bo to oznacza, że lub odkryła co jest chyba rzeczywiście błąd. A następnie mogą dostać więcej sprytna i rozpocząć koncentrując się bardziej wąsko w jaki sposób wykorzystać ten błąd. W szczególności, co mógłby on zrobić, to wysłać, w najlepszym razie, cześć. Nic wielkiego. Jest to ciąg znaków, który jest wystarczająco krótki. Ale co, jeśli on lub ona wysyła, a my uogólnić jako, Atak code-- tak zer i te, które robią rzeczy rm-rf jak, to usuń wszystko z dysku twardego lub wysyłania spamu lub w jakiś sposób atakować maszynę? 

Tak więc, jeśli każdy z tych litery po prostu oznacza, koncepcyjnie, atak, atak, atak, atak, niektóre złe kod że ktoś inny napisał, ale jeśli osoba jest na tyle sprytny, nie tylko to wszystko te rm-RF, lecz również mieć swoje ostatnie kilka bajtów być numer odpowiadający na adres jego lub jej własny kod ataku że on lub ona przekazywana w tak poprzez zapewnienie mu na szybkie, można skutecznie oszukać komputer się zauważyć, gdy f jest wykonywana wykonania, Och, to jest czas dla mnie, aby przejść z powrotem do czerwonego adresu zwrotnego. Ale dlatego, że on lub ona ma jakiś krycie, że adres zwrotny z własnym numerem, i są one na tyle sprytny, które zostały skonfigurowane do Numer odnieść, jak ty zobacz w super góry lewy róg tam, rzeczywisty adres komputera pamięć niektórych ich kodu ataku, zły może oszukać komputer do wykonania swój własny kod. 

I że kod, ponownie, może być cokolwiek. To na ogół nazywane Kod powłoki, która jest po prostu sposobem na powiedzenie, że to nie jest ogólnie coś tak prostego jak rm-rf. To rzeczywiście coś jak bash, lub programem, który rzeczywiście daje mu lub jej wykonanie sterowania programowego wszystko, co chcą. Tak więc, w skrócie, wszystkie wynika z prostego faktu, że ten błąd nie sprawdzając zaangażowane granice swojej tablicy. A ponieważ na drodze komputerów jest to, że praca korzystania ze stosu skutecznie, koncepcyjnie, dołu na górę, ale potem elementy naciśnięciu na stos rośnie z góry na dół, to jest bardzo problematyczne. Teraz istnieją sposoby obejścia tego. I szczerze mówiąc, nie są w językach z którego można to obejść. Java odpornościowego, na przykład, do tej konkretnej kwestii. Ponieważ nie daje wskazówek. Nie daje bezpośrednie adresy pamięci. Więc z tego, że mamy moc dotykać niczego w pamięci Chcemy pochodzi wprawdzie wielkie ryzyko. 

Więc miej oko. Jeśli, szczerze mówiąc, w miesiącach lub latach, w każdej chwili można przeczytać o jakimś eksploatacji programu lub serwera, jeśli kiedykolwiek zobaczyć podpowiedź coś jak atak przepełnienia bufora, lub stosu przelewowa jest innym typem ataku, w duchu podobnym, ile inspiruje witryny wymienić, jeśli go znasz, to wszystko mówisz tylko przepełnione rozmiar charakterem tablica lub tablica ogólnie niektóre. Wszelkie pytania, a następnie, w tej sprawie? Nie próbuj tego w domu. 

Wszystko w porządku. Więc malloc dotychczas był nasz nowy przyjaciel w które możemy przydzielić pamięci że nie muszą wiedzieć, w wcześniej, że chcemy więc nie mamy do dysku do naszego kodu numery programów, takich jak 12. Gdy użytkownik mówi nam, jak bardzo Dane on chce do wejścia, malloc, że możemy dużo pamięci. 

Więc malloc się okazuje, do stopniu używaliśmy go, wyraźnie ostatni raz, a następnie wy zostały zastosowane dla nieświadomie dla getString kilka tygodni, wszystko w pamięci malloc pochodzi z tzw sterty. I dlatego getString, na przykład może przydzielić pamięci dynamicznie nie wiedząc, co masz zamiar wpisać z góry, oddać z powrotem wskaźnik do tej pamięci, i że pamięć jest nadal twoje utrzymanie, nawet po getString zyski. Bo przecież przypomnieć, że stos ciągle idzie w górę iw dół, w górę iw dół. I tak szybko jak to jest w dół, to znaczy jakiejkolwiek pamięci Ta funkcja powinna nie być używany przez nikogo innego. To wartości śmieci teraz. 

Ale kupa jest tutaj. I co miłe jest to, że o malloc gdy malloc przydziela pamięć się tutaj, to nie wpłynęło na przeważającej części przez stos. , A więc każdy może uzyskać dostęp do funkcji pamięć, która została malloc'd, nawet przez funkcję jak getString, nawet po jej zwrócone. 

Teraz, rozmawiać z malloc jest bezpłatny. I rzeczywiście, ci reguła potrzebne do rozpoczęcia przyjmowania jest każdy, każdy, za każdym razem używasz malloc musisz sobie używać za darmo, w końcu, tego samego wskaźnika. Wszystko to razem pisali buggy, kod buggy, z wielu powodów. Jednak, z których jedna została korzystania z biblioteki CS50, które Sam jest celowo buggy, że przecieki pamięci. Za każdym razem pan nazywa getString w ciągu ostatnich kilku tygodni pytamy o eksploatacji System Linux, dla pamięci. I nigdy nie raz podano je z powrotem. I tak nie jest w ćwiczyć, coś dobrego. 

I Valgrind jeden z narzędzia wprowadzone w Pset 4, jest o pomaga teraz znaleźć błędy w tym stylu. Ale na szczęście dla Pset 4 nie trzeba do korzystania z biblioteki CS50 lub getString. Więc wszelkie błędy związane z pamięcią są ostatecznie będzie własne. 

Więc malloc jest więcej niż tylko Wygodne dla tego celu. Możemy faktycznie teraz rozwiązać zasadniczo różne problemy, i zasadniczo rozwiązać więcej problemów skutecznie, jak za tydzień Zero obietnicy. Jak dotąd jest to najseksowniejsza Struktura danych mieliśmy. I struktury danych, po prostu oznacza, sposób pamięci konceptualizacji w sposób, który wykracza poza tylko powiedzieć, to int jest char. Możemy zacząć rzeczy klastra razem. 

Tak wyglądała ta tablica. I to, co było kluczem o Tablica jest to, że daje back-to-back kawałki Pamięć, z których każda ma być tego samego typu, int int, int, int lub char, char, char, char. Ale jest kilka wad. To jest na przykład Tablica wielkości szóstego. Załóżmy, że wypełnienie tej tablicy z sześciu numery, a następnie, z jakichkolwiek przyczyn, Twój użytkownik chce dać Ci numer siódmy. Gdzie go umieścić? 

Co to jest rozwiązanie, jeśli masz utworzony tablicę na stosie Na przykład, tylko z tygodnia dwa wprowadzono zapis, że my, w nawiasach kwadratowych z numerem wewnątrz? Cóż, masz sześć Liczby w tych polach. Co by instynktowi być? Gdzie chcesz go umieścić? 

PUBLICZNOŚCI: [niesłyszalne] 

David J. MALAN: Przepraszam? 

PUBLICZNOŚCI: Umieść go na koniec. 

David J. MALAN: Umieść go na koniec. Tak właśnie się w prawo poza ten obszar. Które byłoby miło, ale to Okazuje się, że nie może tego zrobić. Bo jeśli nie prosiłem w tym fragmencie pamięci, to może być przypadkiem, że to jest używany przez inną zmienną całkowicie. Pomyśl tygodniu lub tak, gdy określone z nazwami Zamyla and Davina and Gabe w pamięci. Byli dosłownie z powrotem do tyłu na plecach. Nie możemy więc koniecznie ufać, że cokolwiek tutaj jest dostępna dla mnie do używania. 

Co jeszcze można zrobić? Cóż, po realizacji cię trzeba tablicę wielkości siedmiu, można po prostu stworzyć tablica rozmiarów siedmiu następnie użyć do pętli lub pętli while, skopiować je do nowej tablicy, a następnie w jakiś sposób po prostu pozbyć to tablica lub po prostu przestać go używać. Ale to nie jest szczególnie efektywne. Krótko mówiąc, nie pozwól tablice dynamicznie zmieniać rozmiar. 

Tak więc z jednej strony można uzyskać o dostępie swobodnym, co jest niesamowite. Ponieważ pozwala nam robić rzeczy, jak dziel i rządź, wyszukiwanie binarne, z których mamy mówił o na ekranie tutaj. Ale malować się w kąt. Tak szybko, jak trafisz koniec swojej tablicy, co musisz zrobić, to bardzo kosztowna operacja lub napisać całą masę kodu teraz sobie z tym problemem. 

Więc co, jeśli zamiast tego mieliśmy coś, co nazywa się lista, lub powiązane listy w szczególności? Co zrobić, jeśli zamiast prostokąty kopie kopii kopii, mamy prostokąty, które pozostawiają niewiele trochę manewru między nimi? I mimo, że mam wyciągnąć ten obraz lub dostosowany tego obrazu z jednego z tekstów tutaj, aby być z powrotem powrót powrót do bardzo uporządkowany, w rzeczywistości, jeden z tych prostokątów może być tu w pamięci. Jednym z nich może być tutaj. Jednym z nich może być tutaj, Tutaj, i tak dalej. 

Ale co, jeśli zwrócił, w tym przypadku, strzałki że w jakiś sposób połączyć te prostokąty razem? Rzeczywiście, widzieliśmy techniczne wcielenie strzałką. Co my stosowane w ostatnich dni, że pod maską, jest przedstawicielem strzałką? Wskaźnik, prawda? 

Więc co, jeśli zamiast tylko przechowywania numerów, jak 9, 17, 22, 26, 34, co jeśli nie są przechowywane tylko liczba, ale wskaźnik obok każdej takiej liczby? Tak, tak jak byś wątku igłę przez całą masę materiału, Materiały rzeczy jakoś razem, podobnie może my ze wskaźnikami, jak wcielony strzałkami tutaj, rodzaj splot razem te poszczególne prostokąty skutecznie za pomocą wskaźnika obok każdego numeru, który zwraca się do jakiegoś następnego numeru, który Wskazuje to, z kolei, część następna liczba? Tak więc, innymi słowy, co jeśli rzeczywiście chciał zaimplementować coś takiego? No niestety, te prostokąty, co najmniej w jednym z 9, 17, 22, i tak dalej, to nie są już ładne kwadraty z pojedynczych numerów. Dołu, prostokąt poniżej 9, na przykład reprezentuje to, co powinno być wskaźnikiem, 32 bity. Teraz nie jestem jeszcze świadoma każdego typu danych w C, który daje nie tylko int , ale wskaźnik w ogóle. 

Więc co to jest rozwiązanie, jeśli chcemy wymyślać własną odpowiedź na to pytanie? Tak? 

PUBLICZNOŚCI: [niesłyszalne] 

David J. MALAN: Co to jest? 

PUBLICZNOŚCI: Nowa struktura. 

David J. MALAN: Tak, tak, dlaczego Nie tworzymy nową strukturę, lub C, struct? Widzieliśmy konstrukcjom przed, czy krótko, gdzie mamy do czynienia ze strukturą studentów jak ten, który miał imię i dom. W Pset 3 Breakout użyłeś cały Pęczek structs-- GRect i GOvals że Stanford stworzył do Informacje klastra razem. Więc co, jeśli weźmiemy ten sam pomysł słowa kluczowe "typedef" i "struct", i niektóre specyficzne rzeczy studenta, i rozwijać się to do następujących czynności: typedef struct node-- i węzeł jest tylko bardzo ogólne informatyka Określenie czegoś w strukturze danych, Pojemnik, w strukturze danych. Twierdzę węzeł będzie miał int n, całkowicie proste, a następnie trochę więcej tajemniczo, Druga linia węzłów struct * dalej. Ale w mniejszym zakresie technicznych, co to jest druga linia kodu wewnątrz nawiasy? Tak? 

PUBLICZNOŚCI: [niesłyszalne] David J. MALAN: wskaźnika do innego węzła. Więc co prawda, trochę składni tajemniczy. Ale jeśli ją przeczytać dosłownie, następna jest nazwa zmiennej. Jaki jest jego typ danych? To trochę rozwlekły tym razem, ale to z węzła struct typu *. Za każdym razem widzieliśmy coś gwiazdę, że Oznacza to wskaźnik do tego typu danych. Więc następnym jest najwyraźniej wskaźnik do węzła struct. 

Teraz, co jest struct node? Cóż, zauważyć można zobaczyć tych, same słowa w prawym górnym rogu. I rzeczywiście, można również zobaczyć słowo "Węzeł" tu na dole po lewej. I to jest właściwie tylko wygoda. Zauważ, że w naszej definicji studenta jest słowo "student" tylko raz. A to dlatego, że student obiekt nie był autoreferencyjna. Nie ma nic w środku studenta że musi zwrócić się do innego ucznia, persay. To byłoby coś w rodzaju dziwne w świecie rzeczywistym. 

Ale z węzła w powiązane lista, chcemy węzeł jako wzorcowy do podobnego obiektu. I tak zauważyć tu nie jest zmiana tylko to, co znajduje się wewnątrz nawiasów klamrowych. Ale dodać słowo "węzeł" w górę, jak również dodawania do dołu zamiast "student". A to tylko szczegóły techniczne tak, że znowu twój struktura danych może być self-więzy, tak że Węzeł może wskazać innego takiego węzła. 

Więc co to jest ostatecznie będzie oznaczać dla nas? Cóż, jeden, ten materiał wewnątrz jest zawartość przykładowego węzła. To coś się tutaj, górna prawa, jest tak że znów możemy odnosić się do siebie. A następnie rzeczy najbardziej zewnętrzna, Nawet jeśli węzeł jest nowy okres, być może, to jeszcze samo, jak i to, co uczeń był pod maską w SPL. 

Jeśli więc teraz chciał zacząć realizacji tej połączonej listy, jak możemy tłumaczyć coś jak to zakodować? Cóż, po prostu zobaczyć Przykładem programu, który faktycznie korzysta z połączonej listy. Wśród dzisiejszego kodu dystrybucji jest program o nazwie Lista Zero. I jeśli uruchomię to stworzyłem Super proste GUI, Graphical User Interface, ale to naprawdę tylko printf. A teraz dałem sobie kilka menu options-- usuwanie, wstawianie, wyszukiwanie, i Traverse. I Quit. Są to tylko wspólne działania na struktura danych zwana listą linków. 

Teraz Usuń zamierza usunąć numer z listy. Wkładka będzie dodać Numer na liście. Wyszukiwanie będzie wyglądać do numeru na liście. I trawers tylko fantazyjny sposób mówić, chodzić na liście, wydrukować go, ale to wszystko. Nie zmienia to w żaden sposób. 

Warto więc spróbować. Idziemy do przodu i typu 2. A potem mam zamiar wstawić numer, powiedzmy 9. Enter. A teraz mój program jest po prostu zaprogramowany znaczy lista jest 9. Teraz, jeśli pójdę do przodu i wkładaj ponownie, niech mi iść dalej i pomniejszyć i wpisz 17. Teraz moja lista jest 9, a potem 17. Jeśli ja włożyć ponownie, pomińmy jeden. Zamiast 22, jak na zdjęciu mamy przygląda tutaj, pozwól mi przejść do przodu i włóż 26 następna. Więc mam zamiar wpisać 26. Lista jest jak oczekuję. Ale teraz, po prostu, aby zobaczyć, czy ten kod będzie elastyczny, niech mnie teraz typ 22, których co najmniej koncepcyjnie, jeśli jesteśmy Mając to sortowane, co jest w istocie będzie teraz inny cel, powinny znaleźć się w od 17 do 26. Więc naciśnij Enter. Rzeczywiście, że działa. A tak teraz daj mi włożyć ostatnio, na zdjęciu, 34. 

Wszystko w porządku. Więc teraz niech stanowią, że Usuń i Traverse i Szukaj zrobić, w rzeczywistości, działać. W rzeczywistości, jeśli nie uruchomić wyszukiwanie, niech wyszukać numer 22, Enter. Stwierdzono 22. Tak to jest, co to Program Lista Zero robi. 

Ale co się naprawdę dzieje na który implementuje ten? Cóż, po pierwsze mogę mieć, a nawet Muszę, plik o nazwie list0.h. I gdzieś tam jest ta Linia, typedef, struct node, wtedy mam nawiasy klamrowe, int n, i następnie struct-- co definicja? Struct node obok. Więc musimy gwiazdę. Teraz przejdziemy do technicznie zwyczaj rysowania go tutaj. Możesz zobaczyć, podręczniki i odnośników internetowych zrobić tam. Jest to funkcjonalny odpowiednik. W rzeczywistości jest nieco bardziej typowe. Ale będę spójne z tym, co my ostatni raz i to zrobić. I wtedy wreszcie, mam zamiar to zrobić. 

Tak więc w pliku nagłówka gdzieś, w list0.h dziś jest to definicja struct, i być może kilka innych rzeczy. Tymczasem w list0c nie będzie kilka rzeczy. Ale będziemy tylko zacząć i nie skończyć. List0.h jest plik chcę aby w moim pliku C. A następnie w pewnym momencie, że jestem będzie mieć int, główny, unieważnić. A potem mam zamiar mają pewne rzeczy do zrobienia tutaj. Jestem również będzie mieć Prototyp, jak nieważne, wyszukiwanie, int, n, którego celem w życiu jest szukać elementu. A potem tu twierdzę w dzisiejszy kod, nieważne, wyszukiwania, int n, nie średnik ale otwarte nawiasy klamrowe. A teraz chcę jakoś sprawdzić elementu na tej liście. Ale nie mamy na tyle informacja na ekranie dotychczas. Faktycznie nie mam reprezentowane samego listę. Więc jeden sposób możemy wdrożyć połączonej listy w programie jest I niby chcesz zrobić coś jak deklaruje listę związane tutaj. Dla uproszczenia, mam zamiar zrobić Ten ogólny, chociaż Generalnie nie należy robić tego zbyt wiele. Ale będzie to uproszczenie tego przykładu. Tak, chcę oświadczyć, powiązana lista tutaj. Teraz, w jaki sposób może to zrobić? 

Oto zdjęcie z połączonej listy. A ja naprawdę nie wiem w tej chwili how Zamierzam go o reprezentowanie tak wiele rzeczy, za pomocą jednego zmienną w pamięci. Ale pomyśl przez chwilę. Cały czas mieliśmy łańcuchy, które następnie ujawniły się tablice znaków, które następnie objawione być tylko wskaźnik do pierwszego znaku w tablicy znaków który jest wartość null zakończone. Więc w tej logice, i z tego obraz rodzaj siewu swoje myśli, co trzeba tak naprawdę napisać w naszym Kod do reprezentowania połączonej listy? Jak wiele z tych informacji musimy uchwycić w kod C, można by powiedzieć? Tak? 

PUBLICZNOŚCI: Musimy wskaźnik do węzła. David J. MALAN: wskaźnik do węzła. W szczególności, który węzeł Czy Państwa instynkty się utrzymać wskaźnik? 

PUBLICZNOŚCI: pierwszy węzeł. 

David J. MALAN: Tak, prawdopodobnie tylko pierwszy. I zauważyć, pierwszy węzeł jest inny kształt. To tylko połowa wielkość struktury, bo to rzeczywiście tylko wskaźnik. Więc co można zrobić, to oświadczam, rzeczywiście powiązana lista będzie węzła typu *. I niech po prostu nazwać to pierwszy i zainicjować go na null. Tak, null, ponownie, jest przyjście na zdjęciu tutaj. Nie tylko jest zerowy, jak stosowany jako specjalny Wartość zwrócona na takie rzeczy jak getString i malloc, null jest również zerowa wskaźnik, brak wskaźnika, jeśli będzie. To po prostu oznacza, nic nie jest jeszcze tutaj. Teraz pierwszy, może mam nazywa to coś. Mogłem nazwał to "lista" lub dowolną liczbą innych miejscach. Ale dzwonię to "pierwszy", tak aby Linie go z tego obrazu. Tak jak ciąg może być reprezentowany z adresem swojego pierwszego bajtu więc może powiązana lista. I zobaczymy, inne dane Struktury być reprezentowane za pomocą jednego wskaźnika, 32-bitowy strzałka, wskazując w pierwszym węźle konstrukcji. 

Ale teraz niech przewidywania problem. Jeśli mam tylko pamiętać, w moim programie adresowej w pierwszym węźle pierwszego prostokąt w tej strukturze danych, co lepiej być sprawy o Realizacja reszty mojej liście? Co znajduje się klucz, który będzie szczegółowo aby zapewnić ten faktycznie działa? I "naprawdę działa" I myśli, podobnie jak ciąg znaków, pozwala nam przejść od pierwszego znaku w imię Davina do drugiego, do trzeciej, do po czwarte, do samego końca, skąd wiemy, kiedy jesteśmy na końcu z połączonej listy, który wygląda tak? Kiedy jest zerowa. A ja tego typu reprezentowane jako jak inżyniera elektrycznego potęgi, z małym uziemienia Symbol, rodzajów. Ale to tylko oznacza wartość null w tym przypadku. Możesz wyciągnąć go dowolną liczbę sposobów, ale ten sam autor się do korzystania z tego symbolu tutaj. 

Tak długo, jak długo jesteśmy sznurka Wszystkie z tych węzłów wspólnie tylko pamiętać, gdzie Pierwszy z nich jest tak długo jak położyć specjalny symbol na Ostatnim węzeł listy i użyjemy null, ponieważ jest to co mamy dla nas dostępne, ta lista jest pełna. I nawet jeśli tylko daje wskaźnik do Pierwszy element, to programista, z pewnością może uzyskać dostęp do reszty. Ale niech niech wasze umysły wędrować trochę, jeżeli nie są one już co jest dość wandered-- będzie czas pracy znalezienie czegokolwiek w tym liście? Cholera, to jest duże O n, co nie jest złe, w uczciwości. Ale jest liniowa. Daliśmy się co funkcja tablic, przenosząc więcej w stronę tego obrazu dynamicznie lub powiązane ze sobą splecione węzły? Daliśmy się swobodny dostęp. Tablica jest dobre, bo matematycznie wszystko jest z powrotem do tyłu, aby z powrotem do tyłu. Nawet jeśli tego obrazu wygląda całkiem, a nawet ale wygląda na to, tych węzłów są dobrze rozmieszczone, w rzeczywistości mogą być w dowolnym miejscu. OX1, Ox50, Ox123, Ox99 te węzłów może być wszędzie. Ponieważ malloc nie przydzielić pamięci z hałdy, ale w dowolnym miejscu w kupie. Nie muszą wiedzieć, że jest to będzie z powrotem do tyłu na plecach. I tak ten obraz w rzeczywistości jest nie będzie aż tak bardzo. 

Więc to zajmie trochę pracy do realizacji tej funkcji. Warto więc wdrożyć Wyszukaj teraz. I zobaczymy, rodzaj sprytny sposób to zrobić. Więc jeśli jestem funkcja wyszukiwania i Jestem biorąc pod uwagę zmienną całkowitą n, szukać, muszę wiedzieć Nowa składnia patrząc wewnątrz struktury, która jest Wskazał, aby znaleźć n. Więc zróbmy to. 

Więc najpierw mam zamiar iść dalej i zadeklarować węzeł *. I zamierzam to nazwać wskaźnik, tylko umownie. I mam zamiar zainicjować go do pierwszego. A teraz mogę to zrobić w wielu aspektach. Ale mam zamiar podjąć wspólne podejście. Podczas gdy wskaźnik nie jest równy null, i to jest prawidłowa składnia. I to tylko oznacza, wykonaj następujące czynności, aby długo, jak nie jesteś, wskazując na nic. Co chcę zrobić? 

Jeśli wskaźnik kropka n, pozwól mi wrócić do tego, equals-- równa co? Jakie wartości mam szukać? Rzeczywistych N, który został przekazany. Więc oto kolejna funkcja z C i wielu języków. Nawet jeśli w węźle struktury nazywane ma wartość n, całkowicie uzasadniony się również lokalne argumentu lub zmienną o nazwie n. Bo nawet my, z ludzkie oczy, można wyróżnić , że n jest przypuszczalnie różnego od n. Bo składnia jest inna. Masz kropkę i wskaźnik, podczas gdy ten nie ma czegoś takiego. Tak to jest OK. To jest OK, aby połączyć je te same rzeczy. 

Jeśli mam znaleźć to, jestem będzie chciał coś zrobić jak ogłosić, że okazało się, n. I zostawimy, że jako komentarz lub kod pseudokod. Indziej, a tu interesujący, co chcę zrobić, jeżeli bieżący węzeł nie zawierający n, że mi zależy? Jak mogę osiągnąć następujące? Jeśli mój palec w moment jest PTR, i to wskazując na cokolwiek Pierwsza wskazuje na, Jak mogę przesunąć palcem do następnego węzła kod? Cóż, co jesteśmy nawigacyjny będzie podążać w tym przypadku? PUBLICZNOŚCI: [niesłyszalne]. David J. MALAN: Tak, tak dalej. Tak więc, jeśli wrócę do mojego kod tutaj rzeczywiście jestem zamiar iść dalej i powiedzieć, wskaźnik, który jest tylko chwilowy zmienna-- to dziwna nazwa, PTR, ale to tak jak temp-- Mam zamiar ustawić wskaźnik równa jakiegokolwiek wskaźnika jest-- i znowu, to będzie trochę buggy na moment-- kropką. Innymi słowy, mam zamiar wziąć mój wskazujący palec, który jest w tym węźle tutaj i mam zamiar powiedzieć, wiesz, co, spójrz na następne pole i przesuń palcem do bez względu na to, wskazując na. I to będzie powtarzać, powtarzać, powtarzać. Ale kiedy to mój palec przestać robić cokolwiek? Tak szybko, jak to, co linia rzutów kodu w? PUBLICZNOŚCI: [niesłyszalne] David J. MALAN: Jeśli punkt podczas wskaźnik nie jest równy null. W pewnym momencie mój palca będzie wskazując na wartość null i mam zamiar zrealizować że to koniec tej listy. Teraz jest trochę białe kłamstwo dla uproszczenia. Okazuje się, że chociaż Właśnie dowiedziałem się, to notacji dla struktur, wskaźnik nie jest struct. PTR jest co? Po prostu być bardziej nitpicky. Jest to wskaźnik do węzła. To nie jest sam węzeł. Gdybym miał tutaj żadnego gwiazdę, wskaźnik absolutely-- to węzeł. To jest jak jeden tydzień deklaracja zmiennej, chociaż słowo "węzeł" jest nowy. 

Ale jak tylko wprowadzić gwiazda, teraz wskaźnik do węzła. I niestety nie można używać notacja kropki na wskaźniku. Musisz użyć strzałek Zapis, który uderzająco, Jest pierwszym każdy kawałek składni wygląda intuicyjne. To dosłownie wygląda jak strzała. I tak, że to dobra rzecz. I tu dosłownie wygląda jak strzała. Więc myślę, że to la-- ja nie Chyba jestem zbyt popełnienia tutaj-- I myślę, że to ostatni nowy kawałek składni mamy zamiar zobaczyć. I na szczęście, to rzeczywiście trochę bardziej intuicyjne. 

Teraz, dla tych z Państwa, którzy wolą stary sposób, nadal można korzystać z notacji kropki. Ale jak na poniedziałkowym rozmowa, najpierw trzeba tam pojechać, pójść do tego rozwiązania, a następnie uzyskać dostęp do pola. Więc to jest również prawidłowe. I szczerze mówiąc, to jest trochę bardziej pedantyczny. Jesteś dosłownie mówiąc, nieprawidłowego wskaźnik i tam. Następnie chwycić .n, pole o nazwie n. Ale szczerze mówiąc, nikt nie chce wpisać lub przeczytać. I tak świat wymyślony Zapis strzałka, która jest równoważny, identyczny, to jest po prostu cukier syntaktyczny. Tak fantazyjny sposób na powiedzenie tego wygląda lepiej, lub wygląda prościej. 

Więc teraz mam zamiar zrobić jedną rzecz. Mam zamiar powiedzieć "przerwę", kiedy już okazało się, że tak nie trzymać go szukać. Ale to jest sedno z funkcji wyszukiwania. Ale to jest o wiele łatwiejsze, w końca, aby nie chodzić po kodzie. To jest rzeczywiście formalne wdrożenie wyszukiwania w dzisiejszym kodu dystrybucji. Śmiem twierdzić, że wkładka nie jest szczególnie zabawne, iść przez wizualnie ani usunąć, nawet jeśli na koniec dnia sprowadzają się one do dość proste heurystyki. 

Więc zróbmy to. Jeśli będziesz mnie tu humor, ja przynieść kilka piłeczki antystresowe. Przywiozłem kilka numerów. I możemy uzyskać tylko kilka wolontariuszy reprezentować 9, 17, 20, 22, 29, i 34? Więc w zasadzie wszyscy kto tu dzisiaj. To był jeden, dwa, trzy, cztery, pięć, sześć osób. I byłem proszony o go-- zobaczyć, nie jeden z tyłu podnosi ręce. OK, jeden, dwa, trzy, cztery five-- pozwól mi załadować balance-- sześć. OK, sześć przyjść na górę. Będziemy potrzebować innych ludzi. Przywieźliśmy dodatkowe piłeczki antystresowe. I jeśli można, na tylko chwila, linia Sami się tylko jak ten obraz tutaj. 

Wszystko w porządku. Zobaczmy, jak się nazywasz? 

PUBLICZNOŚCI: Andrew. 

David J. MALAN: Andrzej, jesteś numer 9. Miło cię poznać. Proszę bardzo. PUBLICZNOŚCI: Jen. David J. MALAN: Jen. David. Numer 17. Tak? 

PUBLICZNOŚCI: Jestem Julia. 

David J. MALAN: Julia, David. Numer 20. PUBLICZNOŚCI: Christian. David J. MALAN: Christian Dawid. Numer 22. A? 

PUBLICZNOŚCI: JP. David J. MALAN: JP. Numer 29. Więc idź i dostać in-- Uh oh. Uh oh. Czuwania. 20. Czy ktoś ma obrońcę? PUBLICZNOŚCI: Mam Sharpie. David J. MALAN: Masz Sharpie? OK. I czy ktoś ma kawałek papieru? Zapisz wykład. Chodź. PUBLICZNOŚCI: Mamy go. David J. MALAN: Mamy to? Wszystko w porządku, dziękuję. Zaczynamy. Czy to od ciebie? Po prostu uratował dzień. Tak więc 29. Wszystko w porządku. I błędnie 29, ale OK. Śmiało. Dobra, dam ci Twój długopis z powrotem na chwilę. Tak więc mamy tutaj tych ludzi. Zróbmy jeden inny. Gabe, chcesz grać Pierwszy element o? Musimy cię do punktu w tych znakomitych ludzi. Tak, 9, 17, 20, 22, sort z 29, a następnie 34. Czy stracimy kogoś? Mam 34. Gdzie did-- OK, kto chce być 34? OK, dalej w górę, 34. Dobra, to będzie warto kulminacyjnym. Jak masz na imię? 

PUBLICZNOŚCI: Peter. 

David J. MALAN: Piotr, dalej w górę. W porządku, więc tutaj jest cała masa węzłów. Każdy z was reprezentuje jeden z tych prostokątów. I Gabe, nieco dziwne mężczyznę, oznacza pierwszy. Więc jego wskaźnik jest nieco mniejszy na ekranie, niż wszyscy inni. I w tym przypadku, każdy z lewej ręce będzie albo wskazać dół, a tym samym stanowiących null, więc tylko brak wskaźnika, czy to będzie wskazując w węźle obok ciebie. 

Więc teraz, jeśli zdobią sami, jak na zdjęciu tu, iść do przodu i punkt na siebie, z Gabe w szczególności wskazując na nr 9 do reprezentowania listę. OK, a numer 34, lewą ręką powinna być skierowana tylko na podłodze. 

OK, więc jest powiązana lista. Więc to jest scenariusz, o którym mowa. I rzeczywiście, jest to przedstawiciel klasy problemów że może spróbować rozwiązać z kodem. Chcesz ostatecznie wstawić element do listy. W tym przypadku, będziemy spróbuj włożyć numer 55. Ale nie będzie różne przypadki do rozważenia. I rzeczywiście, to będzie jeden z big-picture takeaways tu jest, jakie są różne przypadki. Jakie są różne, jeżeli warunki lub gałęzie, że program może mieć? 

Cóż, liczba próbujesz Wkładka, które znamy teraz jako 55, ale jeśli nie wiesz z góry, Przypuszczam spadnie do co najmniej trzy możliwych sytuacjach. W przypadku, gdy nowy element może być? PUBLICZNOŚCI: I koniec lub średnim. David J. MALAN: Na koniec, w średnim, lub na początku. Więc twierdzić tam co najmniej trzy problemy musimy rozwiązać. Załóżmy, wybrać to, co jest być może prawdopodobnie najprostsza jeden, gdy nowy element Należy na początku. Więc mam zamiar mieć kod dość jak sprawdzić, który właśnie napisał. I mam zamiar mieć ptr, która Ja reprezentuje tu z moim palcem, w zwykły sposób. 

I pamiętaj, co wartość nie możemy zainicjować ptr do? Więc zainicjowany go początkowo null. Ale to co zrobiliśmy, gdy będziemy były wewnątrz naszej funkcji wyszukiwania? Stawiamy to równa pierwsze, co nie znaczy to zrobić. Jeżeli ustawić ptr równą pierwsze, co Naprawdę powinna być moja ręka wskazując na? Prawo. Więc jeśli Gabe i ja być równe wartości tutaj, musimy zarówno miejsca, w liczbie 9. 

Więc to był początek naszej historii. A teraz jest to tylko proste, chociaż składni jest nowy. Koncepcyjnie to tylko liniowy wyszukiwania. Czy 55 równa 9? Albo raczej, powiedzmy mniej niż 9. Ponieważ staram się dowiedzieć się, gdzie umieścić 55. Mniej niż 9, mniej niż 17, mniej niż 20, mniej niż 22, mniej niż 29, mniej niż 34, no. Tak więc teraz jesteśmy w przypadku jeden z co najmniej trzech. 

Jeśli chcę wstawić 55 tu, co linii kodu konieczności zostanie wykonany? Jak to wygląda ludzie muszą się zmienić? Co mam zrobić z moją lewą ręką? To powinno być null początkowo, ponieważ ja na koniec listy. A co powinno się zdarzyć tutaj z Piotrem, prawda? On oczywiście będzie zwrócić się do mnie. Więc twierdzić tam co najmniej dwie linie kodu w kodzie próbki od dzisiaj , że zamierza wdrożyć to Scenariusz dodając 55 w ogonie. I mógłbym kogoś hop się i po prostu reprezentują 55? Dobra, jesteś nowy 55. 

I co teraz, czy w przyszłym Scenariusz przychodzi, i chcemy włożyć w rozpoczynających lub szef tej liście? A jak masz na imię, numer 55? 

PUBLICZNOŚCI: Jack. 

David J. MALAN: Jack? OK, miło cię poznać. Witamy na pokładzie. Więc teraz jedziemy do wstawić, powiedzmy, liczbę 5. Oto druga sprawa trzy wpadliśmy wcześniej. Tak więc, jeśli 5 należy na początku Zobaczmy, w jaki sposób się tego dowiedzieć. Zainicjować moje ptr wskaźnik do liczby 9 ponownie. I zdałem sobie sprawę, o, 5 jest mniejsza niż 9. Więc rozwiązać ten obraz dla nas. Których ręce, Gabe i Dawida or-- co to za nazwa numer 9? 

PUBLICZNOŚCI: Jen. 

David J. MALAN: hands-- Jen które z naszych rękach trzeba zmienić? OK, więc Gabe wskazuje na co teraz? Na mnie. Jestem nowy węzeł. Więc będę po prostu rodzaj ruchu tutaj, aby go zobaczyć wizualnie. A tymczasem to, co mogę podkreślić, że? Jeszcze gdzie mam wskazując. Tak, to jest to. Tak naprawdę tylko jeden wiersz kodu poprawek ten konkretny problem, wydaje się. Wszystko w porządku, więc to jest dobre. A może ktoś być zastępczym dla 5? Chodź na górę. My się następnym razem. 

Dobra, i tak teraz-- Tak na marginesie, nazwy Nie mam co wyraźnie o prawo teraz, pred wskaźnik, wskaźnik poprzednika i nowy wskaźnik, który znajduje się podano tylko nazwy w przykładowy kod do wskaźników lub moje ręce, że niby wskazujące wokół. Jak masz na imię? 

PUBLICZNOŚCI: Christine. 

David J. MALAN: Christine. Witamy na pokładzie. W porządku, więc rozważmy teraz nieco irytujące scenariusz, w którym chcę wstawić coś jak 26 do tego. 20? Co? Są are-- dobrą rzeczą mamy ten długopis. Wszystko w porządku, 20. Jeśli ktoś może dostać inny kawałek papier gotowy, tylko w case-- porządku. O, ciekawe. Cóż to jest przykład buga wykładowej. OK, więc jak masz na imię? PUBLICZNOŚCI: Julia. David J. MALAN: Julia, można pop się i udawać, że nigdy tam nie byłeś? OK, to się nigdy nie wydarzyło. Dziękujemy. Więc załóżmy, że chcemy wstawić Julia do tego połączonej listy. Jest to ilość 20. I oczywiście, że jest będzie należeć w begin-- nie wskazują na coś jeszcze. Więc twoja ręka może być rodzaj w dół zerowy lub niektóre wartość śmieci. Powiedzmy szybką historię. Jestem wskazując na numer 5 to czasu. Potem sprawdź 9. Potem sprawdzić 17. Potem sprawdzić 22. I zdaję sobie sprawę, ooh, Julia musi iść przed 22. Więc to, co musi się zdarzyć? Których ręce trzeba zmienić? Julia, moja, or-- jak masz na imię? 

PUBLICZNOŚCI: Christian. 

David J. MALAN: Christian lub? 

PUBLICZNOŚCI: Andy. 

David J. MALAN: Andy. Christian lub Andy? Andy musi wskazać na? Julia. Wszystko w porządku. Tak Andy, chcesz zwrócić na Julia? Ale chwileczkę. W historii do tej pory, Jestem jakby jednym w ładunku, w tym sensie, że wskaźnik jest rzeczą, która jest przemieszczania się po liście. Możemy mieć nazwę Andy, ale nie ma zmienną o nazwie Andy. Tylko inne mamy, jest zmienna Pierwszy, który reprezentuje Gabe. 

Więc to jest naprawdę, dlaczego w ten sposób pory nie potrzebowaliśmy tego. Ale teraz na ekranie jest wspomnieć jeszcze o pred wskaźnika. Więc pozwól mi być bardziej wyraźne. Jeśli jest to wskaźnik, miałem lepsze trochę bardziej inteligentny o mojej iteracji. Jeśli nie masz nic przeciwko moim przechodzi tutaj ponownie, wskazując tutaj, wskazując tutaj. Ale pozwól mi mieć pred wskaźnik, wskaźnik poprzednika, to rodzaj, wskazując na Element Byłem na. Więc kiedy wrócę tu, teraz Moja lewa ręka. aktualizacje Kiedy wrócę tu moja lewa aktualizacji ręcznych. A teraz mam nie tylko wskaźnik do Element, który idzie po Julia, Nadal mam wskaźnik do Andy elementem wcześniej. Więc masz dostęp, zasadniczo, bułka tarta, jeśli chcesz, do wszystkich wymaganych wskaźników. 

Więc jeśli ja, wskazując na Andy i ja również wskazując w ręce chrześcijan, którego Należy teraz wskazać gdzie indziej? Więc Andy może teraz zwrócić się Julia. Julia może teraz wskazać na chrześcijanina. Bo można skopiować mój wskaźnik prawicy za. Oraz że skutecznie stawia się z powrotem na to miejsce tutaj. Tak więc, w skrócie, chociaż zabiera nas rodzaj wiecznie faktycznie zaktualizować lista powiązana, realizować że operacje są stosunkowo proste. To o jeden, dwa, trzy linii kodu ostatecznie. Ale owinięte wokół tych linii kodu przypuszczalnie jest nieco logiki, które skutecznie zadaje pytanie, gdzie jesteśmy? Jesteśmy na początku, środkowy lub końcowy? 

Obecnie istnieją oczywiście inna Operacje możemy realizować. I tu właśnie przedstawiają te zdjęcia co właśnie zrobił z ludzi. Co o usunięciu? Jeśli chcę, aby, na przykład, usunąć numer 34 lub 55, Może mam ten sam rodzaj kodu, ale będę potrzebować jednego lub dwóch etapów. Bo to, co nowego? Jeśli usunąć kogoś na koniec, jak numer 55 i 34, co ma również zmienić, jak to zrobić? Muszę nie evict-- jak masz na imię? 

PUBLICZNOŚCI: Jack. 

David J. MALAN: Jack. Mam nie tylko evict-- darmo Jack, tak dosłownie telefonować Jack, lub przynajmniej Wskaźnik jest też jednak teraz co trzeba zmienić z Peterem? Jego ręka lepiej zacząć wskazując w dół. Bo jak tylko zadzwonić bezpłatnie na Jack, czy Piotra wciąż wskazując na Jacka i dlatego trzymam przejeżdżające lista i dostęp ten wskaźnik, wtedy nasz stary przyjaciel segmentacja winy może faktycznie kopać. Bo dałeś pamięci z powrotem do Jacka. 

Można tam niezgrabnie na chwilę. Ponieważ mamy tylko kilka Czynności końcowe do rozważenia. Usuwanie głowę listy, lub beginning-- i ten jest trochę denerwujące. Ponieważ musimy wiedzieć, że Gabe to rodzaj specjalnego w tym programie. Bo rzeczywiście, on ma swój własny wskaźnik. On nie tylko jest wskazał, jak prawie wszyscy tutaj. 

Kiedy więc szef liście jest usunięte, których ręce trzeba zmienić teraz? Jak masz na imię? 

PUBLICZNOŚCI: Christine. 

David J. MALAN: Jestem strasznie w nazwach, najwyraźniej. Więc Christine i Gabe, których ręce trzeba zmienić gdy próbujemy usunąć Christine, numer 5, z obrazka? OK, więc zróbmy Gabe. Gabe będzie wskazywać, przypuszczalnie w liczbie 9. Ale co dalej się stanie? PUBLICZNOŚCI: Christine powinna być null [niesłyszalne]. David J. MALAN: OK, powinniśmy prawdopodobnie make-- usłyszałem "null" gdzieś. PUBLICZNOŚCI: Null i jej wolne. David J. MALAN: null co? PUBLICZNOŚCI: Null i jej wolne. David J. MALAN: Null i jej wolne. Więc to jest bardzo proste. I to jest doskonały, że jesteś teraz sortowania stojącego tam, nie należące. Ponieważ byli oddzielone od listy. Ty rzeczywiście zostały osieroconych z listy. A więc lepiej zadzwonić za darmo teraz Christine dać, że pamięć z powrotem. Za każdym razem w inny sposób usunąć węzeł z listy możemy być sporządzaniu listy krótszy, ale w rzeczywistości nie maleje rozmiar pamięci. A więc jeśli będziemy dodawać i dodając, dodając rzeczy do listy, komputer może się wolniej i wolniej i wolniej, bo jestem na wyczerpaniu pamięci, nawet jeśli w rzeczywistości nie jestem za pomocą bajtów Christine z pamięci więcej. 

A więc w końcu istnieje inne scenariusze, z course-- usunięcia w środku, usuwanie Na koniec, jak widzieliśmy. Ale bardziej interesujące wyzwaniem jest będzie dokładnie rozważyć Czas pracy, co jest. Więc nie tylko można zachować kawałki papieru, jeśli, Gabe, nie masz nic przeciwko dając każdy piłka stres. Dziękuję bardzo do naszej listy wolontariuszy tutaj, jeśli można. 

[Aplauz] 

David J. MALAN: Wszystko w porządku. Więc kilka analityczna pytania, następnie, jeśli będę mógł. Widzieliśmy ten zapis przed, Big O i omega, górne granice i dolne granice na czas jakiś algorytm działa. Warto więc wziąć pod uwagę tylko kilka pytań. 

Jeden, i powiedział, że wcześniej, co jest uruchomiony czas poszukiwania lista w zakresie Big O? Co znajduje się górne ograniczenie na prowadzeniu czas poszukiwania połączonej listy wdrożone przez naszych wolontariuszy tutaj? To wielki O n, liniowy. Ponieważ w najgorszym wypadku elementem, podobnie jak 55, możemy szukać, gdzie może być Gniazdo to wszystkie sposób na końcu. I niestety, w przeciwieństwie do tablicy nie możemy się ochotę tym razem. Mimo, że wszyscy nasi ludzie byli sortowane od małych elementów, 5, wszystko aż do większego elementu 55, który jest zazwyczaj dobrze. Ale co to założenie nie pozwalają nam robić? PUBLICZNOŚCI: [niesłyszalne] David J. MALAN: Powiedz jeszcze raz? PUBLICZNOŚCI: Random dostęp. David J. MALAN: Random dostęp. A to z kolei oznacza, że ​​nie możemy już używać słabego zer, intuicji, i oczywistość za pomocą binarnego wyszukiwać i dziel i rządź. Bo chociaż ludzie mogli oczywiście zobaczyć, że Andy i Christian byli mniej więcej w połowie listy wiemy tylko, że jak Komputer zebranie z listy od samego początku. Więc daliśmy się, że swobodny dostęp. 

Tak duże O n jest górna związany na naszego czasu wyszukiwania. Co omega naszego wyszukiwania? Co znajduje się dolne ograniczenie na poszukiwania dla pewnej liczby w tym liście? PUBLICZNOŚCI: [niesłyszalne] David J. MALAN: Powiedz jeszcze raz? PUBLICZNOŚCI: Jeden. David J. MALAN: Jeden. Tak więc stała czasowa. W najlepszym przypadku, Christine w rzeczywistości na początku listy. I szukamy Numer 5, więc ją znaleźć. Więc nic wielkiego. Ale ona ma być na początku listy w tej sprawie. Co o czymś jak Delete? Co zrobić, jeśli chcesz usunąć element? Co znajduje się górna granica i dolna granica na usuwanie coś związane z listy? PUBLICZNOŚCI: [niesłyszalne] David J. MALAN: Powiedz jeszcze raz? PUBLICZNOŚCI: brak. David J. MALAN: n rzeczywiście górna granica. Ponieważ w najgorszym przypadku staramy usunąć Jack, jak my właśnie zrobiliśmy. On jest wszystkim sposobem na końcu. Zabiera nas na zawsze, lub n kroków, aby go odnaleźć. Więc to jest górna granica. To jest liniowa, na pewno. A najlepszym przypadku czas pracy, lub dolne granice w najlepszym wypadku będzie stała czasowa. Bo może spróbować usunąć Christine, i po prostu miał szczęście ona jest na początku. Chwileczkę. Gabe również na początku i mieliśmy również zaktualizować Gabe. Tak, że nie było tylko jeden krok. Tak więc jest to rzeczywiście stała Czas, w najlepszym przypadku, , aby usunąć najmniejsze elementu? To znaczy, nawet jeżeli mogłyby być dwa trzy, albo nawet 100 linii kodu, czy to ta sama liczba linie, nie w jakiejś pętli, i niezależnie od rozmiarów z listy, absolutnie. Usuwanie elementu w początku listy nawet jeśli mamy do czynienia z Gabe jest nadal stała czasowa. 

Tak więc wydaje się, że jak ogromny krok wstecz. A co stratą czasu jeśli w jednym tygodniu tydzień zera mieliśmy nie tylko Kod pseudokod, ale rzeczywisty kod wdrożyć coś, co jest dziennik Podstawa n lub log, a, n, podstawa 2, w zakresie jego czasu pracy. Więc dlaczego do cholery nie chcemy, aby rozpocząć przy użyciu coś jak połączonej listy? Tak. 

PUBLICZNOŚCI: Więc możesz dodać elementy do tablicy. David J. MALAN: Więc możesz dodawanie elementów do tablicy. I to też jest tematyczna. A my nadal zobaczyć to, to kompromis, znacznie jak widzieliśmy kompromis z seryjnej rodzaju. Możemy naprawdę przyspieszyć wyszukiwania i sortowania, a, jeśli spędzić trochę więcej miejsca i mają dodatkowy fragment pamięci lub tablica do seryjnej rodzaju. Ale spędzamy więcej przestrzeń, ale zaoszczędzić czas. W tym przypadku mamy dając się czas, ale jesteśmy zyskuje elastyczność, dynamizm, jeśli chcesz, która niewątpliwie jest pozytywną cechą. 

Jesteśmy również spędzać miejsca. W jakim sensie jest powiązana listy droższe w zakresie miejsca niż tablicy? Gdzie jest dodatkowa przestrzeń pochodzi? Tak? 

PUBLICZNOŚCI: [niesłyszalne] wskaźnik. 

David J. MALAN: Tak, również wskaźnik. Więc to jest minorly irytujące że nie am Ja przechowywania tylko int do reprezentowania int. Jestem przechowywania int i A wskaźnik, który jest 32 bitów. Więc jestem dosłownie podwojenie Ilość miejsca zaangażowany. Więc to jest kompromis, ale to w przypadku int. Załóżmy, że nie jesteś przechowywania int, ale przypuszczam, każdy z tych prostokątów lub każdy z tych ludzi reprezentował Słowo, angielskie słowo, które może być pięć znaków, 10 znaków, a może nawet więcej. Następnie dodanie zaledwie 32 więcej bitów może być mniejsza od wielkiego. 

Co zrobić, jeśli każdy z uczniów w demonstracji były uczeń, który dosłownie elemencie mają nazwy i domy a może numery telefonów i Twitter uchwyty i podobne. Więc wszystkie pola zaczęliśmy mówić o innym dniu, znacznie mniej wielkiego jak Nasze węzły uzyskać bardziej interesujące i duże, aby spędzić, co, dodatkowe wskaźnik po prostu połączyć je ze sobą. Ale rzeczywiście, jest to kompromis. I rzeczywiście, kod jest bardziej złożone, jak będziesz zobacz zebranie przez że konkretny przykład. Ale co, jeśli nie było jakiś święty graal tutaj. Co, jeśli nie zrobić krok do tyłu, ale ogromny krok do przodu i wdrożenie danych Struktura poprzez które można znaleźć elementy, takie jak Jack lub Christine lub inne elementy w tej tablicy w prawdziwej stałym czasie? Szukaj jest stała. Usuń jest stała. Wkładka jest stała. Wszystkie te operacje są stałe. To byłby nasz Święty Graal. I to jest miejsce, gdzie wzrośnie następnym razem. Do zobaczenia.