[Powered by Google Translate] [Tydzień 6] [David J. Malan] [Harvard University] [To jest CS50.] [CS50.TV] 

To CS50, i jest to początek tygodnia 6 więc kilka nowych narzędzi, są teraz dostępne dla Ciebie, aby skorzystać, z których pierwszy jest nazywany CS50 Styl. Kursy są, jeśli jesteś podobny do mnie, lub którykolwiek z kolegów nauczania, Prawdopodobnie widziałeś program, którego styl wygląda trochę coś takiego. Może rozpocząć cięcie niektórych zakątkach późno w nocy, lub będziesz radzić sobie z nim później, i TF lub CA przychodzi w godzinach pracy. Wtedy to trudno nam się czytać. Cóż, ten kod jest składniowo poprawne, i będzie go skompilować i będzie ono działać. Ale to na pewno nie 5 za styl. 

Ale teraz, jeśli pójdziemy do tego katalogu tu i zauważ, że mam conditions2.c- i uruchomić tę nową komendę, style50 na tej conditions2.c pliku, Enter zauważyć, że jest to poinformował mnie, że nie było stylizowane. Gedit zauważyłem, że plik został zmieniony na dysku, i jeśli kliknę przeładować, wszystkie twoje problemy są teraz zautomatyzowane. [Oklaski] To jedna z rzeczy, które zrobiliśmy w ten weekend. Sobie sprawę, że jest niedoskonały, ponieważ istnieje jakiś kod że po prostu nie są w stanie całkowicie stylizacji, ale uświadomić sobie, teraz jest to narzędzie, które można wykorzystać jeśli tylko uporządkowanie niektórych bardziej errantly umieszczone Nawiasy klamrowe i podobne. 

Ale teraz jest bardziej przekonujące CS50 Check. Przy CS50 sprawdzić, rzeczywiście można wykonać te same testy poprawności na własnym kodzie, że chłopaki nauczania są w stanie. Jest to narzędzie wiersza polecenia, które jest teraz w urządzeniu jak najszybciej zrobić update50 jak za Pset 4 specyfikacji i go używać w zasadzie tak. Uruchomić check50 polecenia. Następnie przechodzą w argumencie wiersza poleceń, lub bardziej powszechnie znany jako przełącznik lub flagi. Generalnie rzeczy, które nazywane są myślniki switch do programu z linii poleceń, tak c określa kontrole, które chcesz uruchomić. 

Testy, które mają być uruchamiane są identyfikowane jednoznacznie przez to ciąg znaków, 2012/pset4/resize. Innymi słowy, jest to po prostu dowolny, ale unikalny ciąg że używamy do identyfikacji Pset 4 na testy poprawności. A następnie określić spacjami listę plików, które chcesz przesłać CS50 do zameldowania w celu analizy. Na przykład, jeśli pójdę do mojego rozwiązania tutaj resize.c- pozwól mi otworzyć okno terminala większy- i iść do przodu i uruchamiania powiedzmy check50-c 2012/pset4/resize, a potem iść dalej i podać nazwy plików, resize.c, a następnie naciśnij Enter, to ściska, ono przesłane, sprawdza, a ja po prostu nie całą masę badań. Jeden w kolorze czerwonym w lewym górnym rogu i mówi, że resize.c bmp istnieje. To był test. To było pytanie poprosiliśmy. I to jest nieszczęśliwy, ponieważ odpowiedź była fałszywa. Biały tekst pod nim mówi spodziewać bmp.h istnieć, a to po prostu moja wina. Zapomniałem przesłać go, więc trzeba wgrać oba pliki, resize.c i bmp.h. Teraz jednak zauważyć wszystkie inne badania są w kolorze żółtym, ponieważ nie uruchomić, i tak buźkę jest pionowy, bo jest ani szczęśliwy, ani smutny, ale mamy do naprawienia tego problemu w czerwonym zanim te inne kontrole będą działać. 

Pozwól mi to naprawić. Pozwól oddalić i ponownie to, tym razem z bmp.h również w linii poleceń, Enter i teraz, jeśli wszystko pójdzie dobrze, to będzie sprawdzić, a następnie zwraca wynik z-wstrzymaj oddech- cały zielony, co oznacza, robię naprawdę dobrze na Pset 4 pory. Możesz zobaczyć i wywnioskować z tekstu opisowego tutaj dokładnie co to jest, że testowany. Testowaliśmy najpierw zrobić pliki istnieją? Następnie badany wykonuje resize.c skompilować? Następnie badany nie to zmienić rozmiar 1x1 pikseli BMP gdy n, współczynnik zmiany rozmiaru, jest 1. Teraz, jeśli nie masz pojęcia, co jest n, to po zanurkować Pset 4, ale to po prostu jest normalność upewnij się, że nie jesteś rozmiaru obraz w ogóle, jeśli czynnikiem resize jest 1. Jeśli natomiast, to zmienia rozmiar na 1x1 piksel w piksel BMP do 1x1 2x2 prawidłowo gdy n oznacza 2, a następnie w podobny, stanowi odpowiednio kopalni. 

W skrócie, jest to zadanie, jeden, podejmują skrzyżowań palców z równania tuż przed przesłać PSET. Będziesz wiedzieć, co dokładnie TF wkrótce wiedzieć kiedy go o złożenie niektórych z tych zestawów problemowych, a także pedagogiczne motywacja jest naprawdę umieścić szansa przed tobą tak, że kiedy wiesz a priori że nie ma błędów w kodzie i testy, które nie zostały przekazane, można umieścić w bardziej efektywnego czasu z przodu, aby rozwiązać te problemy zamiast tracić punktów, uzyskać informacje zwrotne od TF, a potem: "Ahh," jak należy się domyślić, że na zewnątrz. Teraz przynajmniej nie ma narzędzia, które pomogą Ci znaleźć to. To nie będzie wskazać, gdzie jest błąd, ale to powiedzieć to, co jest symptomatyczne dla niego. 

Sobie teraz sprawę, że testy nie zawsze są wyczerpujące. Tylko dlatego, że masz cały ekran zielony Smiley Faces nie oznacza, Twój kod jest doskonały, ale to nie oznacza, że przeszedł pewne badania określone przez spec. Czasami nie wyda kontrole. Na przykład, Whodunit, jednym z aspektów zbior 4 jest trochę rozczarowujące, jeśli ci odpowiedzi na pytanie, co to jest, i jest wiele sposobów, aby odsłonić która osoba jest w tej czerwonej hałasu. Specyfikacja zawsze określić w przyszłości Pset 5 począwszy co sprawdza istnieje dla Ciebie. Zauważysz tam ten biały URL na dole. Na razie jest to tylko wyjście diagnostyczne. Jeśli odwiedzić ten adres URL, dostaniesz całą masę zwariowanych, wiadomości tajemniczych które zapraszamy do obejrzenia, ale to głównie dla pracowników tak, że możemy diagnozować i debugowania błędów w check50 sama. 

Bez ceregieli, przejdźmy do miejsca, gdzie skończyliśmy. CS50 biblioteka braliśmy za pewnik przez kilka tygodni, ale w zeszłym tygodniu zaczęliśmy odrywając jedną z warstw to. Zaczęliśmy odkładając łańcuch za co w zamian? [Studenci] Char. Char *, które było char * przez cały ten czas, ale teraz nie mamy udawać, że to rzeczywisty typ danych string. Raczej to było synonimem rodzaju dla char *, i ciąg jest ciągiem znaków, więc dlaczego ma sens do reprezentowania ciągi jako char * s? Co char * reprezentowania w ramach tej koncepcji ciąg? Tak. >> [Student] pierwszy znak. Dobra, pierwszy znak, ale nie całkiem pierwszy znak. To te-[Uczniowie] Adres. Dobry, adres pierwszego znaku. Wszystko, co niezbędne do reprezentowania ciąg w pamięci komputera jest po prostu niepowtarzalny adres jego bajt pierwszy. Nie musisz nawet wiedzieć, jak długo jest bo jak można dowiedzieć się, że obecnie dynamicznie? [Student] długość String. Możesz zadzwonić długość ciągu, doskonałe, ale jak działa długość łańcucha? Co to robi? Tak. [Student] Tak trzymać, aż pojawi się znak null. Tak, dokładnie, to po prostu przechodzi z pętli for, while, niezależnie od * do końca, a na końcu jest reprezentowana przez \ 0, tak zwany znak nul, nul, nie mylić z wartością null, który jest wskaźnik, która wejdzie w rozmowie dzisiaj. 

Mamy obrane z powrotem warstwę getInt, a potem przyjrzał się getString, i przypomnieć, że zarówno z tych funkcji, lub naprawdę, GetString, był przy użyciu niektórych funkcji faktycznie analizować, czyli czytać i analizować, wprowadzane przez użytkownika. A co było, że nowa funkcja? Scanf lub sscanf. To rzeczywiście jest w kilku różnych smakach. Jest scanf, jest sscanf, jest fscanf. Na razie jednak skupmy się na jednej z najbardziej łatwo zilustrować, i pozwól mi iść do przodu i otworzyć się w urządzeniu plik tak, scanf1.c. To jest super prosty program, ale że robi coś, czego nigdy nie robiłem bez pomocy CS50 biblioteki. To dostaje int od użytkownika. Jak to działa? Cóż, w linii 16 tam, Zauważ, że deklarujemy int o nazwie x, a w tym momencie w historii, co wartość x? [Niesłyszalne odpowiedź uczeń] [David M.] Prawo, kto wie, jakaś wartość śmieci potencjalnie, tak w 17, po prostu poinformować użytkownika daj mi numer, proszę, i krok 18 jest, gdy robi się ciekawie. Scanf wydaje pożyczyć pomysł z printf, że używa tych kodów formatu w cudzysłowie. D% jest oczywiście liczba dziesiętna. Ale dlaczego ja przekazując & X, a nie tylko x? Pierwszy z nich jest poprawna. Tak. [Niesłyszalne odpowiedź uczeń] Dokładnie, jeżeli celem tego programu, jak getInt samej funkcji, jest dostać int od użytkownika można przekazać funkcji wszystkie zmienne chcę, ale jeśli nie przekazać je przez referencję lub według adresu lub przez wskaźnik, synonimami dla współczesnych celów, wtedy, że funkcja nie ma możliwości zmiany zawartości tej zmiennej. To minie w kopii jak buggy wersji swapu że rozmawialiśmy o kilka razy. 

Ale zamiast tego, wykonując & x, jestem dosłownie przechodzącą w czym? [Student] adres. >> Adres x. To jak rysowanie mapy dla funkcji o nazwie scanf i mówi tutaj Są to wskazówki do kawałka pamięci w komputerze że można go przechowywać niektóre całkowitą w. Aby sscanf do teraz zrobić co operator, co kawałek składni to będzie trzeba użyć mimo, że nie widać go, bo ktoś inny napisał z tej funkcji? Innymi słowy - co to jest? [Student] X czytać. Nie będzie trochę czytania, ale tylko w odniesieniu do x tutaj. Jeśli scanf przekazywana jest adres x, syntaktycznie, co operator ma obowiązek istnieć gdzieś wewnątrz realizacji scanf jest tak, że scanf może faktycznie napisać numer 2 na ten adres? Tak, tak, *. Przypomnijmy, że to nasz operator * dereference, które oznacza, idź tam. 

Kiedy już podał adres, jak w tym przypadku, scanf jest prawdopodobnie-jeśli faktycznie wyglądał wokół jego kod źródłowy- robi * x lub równoważnik faktycznie przejść na ten adres i umieścić tam jakąś wartość. Teraz, jak na jak scanf pobiera dane wejściowe z klawiatury, będziemy machać nasze ręce na dziś. Wystarczy założyć, że system operacyjny pozwala sscanf rozmawiać do użytkownika klawiatury, w tym momencie, ale teraz w linii 19, kiedy po prostu wydrukować x, wydaje się być w przypadku że scanf włożył int wx. To jest dokładnie tak, jak scanf działa i przypomnieć ostatni tydzień Tak właśnie GetString i getInt i jego inne rodzina funkcji ostatecznie działa, choć z lekkim wariancji jak sscanf, co oznacza, że ​​łańcuch skanowania Zamiast klawiatury. Ale rzućmy okiem na trochę wariancji to. W scanf2, faktycznie spieprzył. Co jest nie tak, a ja ukryć komentarz, który wyjaśnia, jak tak bardzo co jest nie tak z tym programem w wersji 2? Bądź tak techniczne, jak to możliwe tym czasie. Wygląda to całkiem nieźle. Jest ładnie wcięty, ale- dobrze, jak o niech przycinać go do krótszych pytań? Linia 16. Co robi linia 16 w języku angielskim, ale precyzyjnej technicznej? Się trochę niezręcznie. Tak, Michael. [Student] To wskazuje na pierwszą literę ciągu. 

Okay, w pobliżu. Pozwól mi podkręcić że trochę. Wskazując na pierwszą literę ciągu, jesteś deklarując zmienną bufor , które będą wskazywać na pierwszego adresu ciąg, lub raczej, że będzie wskazywać konkretnie do char. Zawiadomienie to nie jest faktycznie wskazując nigdzie, bo nie ma operator przypisania. Nie ma znaku równości, więc wszystko, co robimy jest przydzielenie zmienną bufor. Zdarza się 32 bitów, ponieważ jest to wskaźnik, i zawartość bufora końcu prawdopodobnie będzie zawierać adres char, ale teraz, to co bufor zawiera? Tylko niektóre fałszywe, kto wie, jakaś wartość śmieci, dlatego, że nie jawnie zainicjowana, więc nie należy niczego zakładać. Ok, więc teraz linia 17 jest-co linia 17 zrobić? Być może, że będzie ciepło to. Wypisuje łańcuch, prawda? Drukuje String proszę. 

Linia 18 jest trochę zna się na tym, że my po prostu zobaczyłem to wariancję ale o innym kodzie formatem, w linii 18, mówimy scanf tutaj jest adres kawałek pamięci. Chcę, byś dzwonił w ciągu, jak wynika z% s, ale problemem jest to, że nie zrobiliśmy kilka rzeczy tutaj. Co jest jednym z tych problemów? [Student] To próbuje nieprawidłowego wskaźnika pustego. Dobry, null lub po prostu inaczej znane wskaźniki. Jesteś wręczając scanf adresu, ale po prostu powiedział chwilę temu że adres jest jakaś wartość śmieci, bo nie faktycznie przypisać go do niczego, i tak mówisz scanf skutecznie przejść umieścić ciąg tutaj, ale nie wiem, gdzie tu jeszcze jest, więc nie zostały faktycznie przydzielone pamięci dla bufora. Ponadto, co jest również nie mówiąc nawet scanf? Załóżmy, że to był fragment pamięci, i to nie było napięcie śmieci, ale nadal nie jesteś mówiąc scanf coś ważnego. [Student] Gdzie jest w rzeczywistości, ampersand. Ampersand, więc w tym przypadku, to jest w porządku. Ponieważ bufor jest już zadeklarowany jako wskaźnik z kawałkiem * składni, nie trzeba używać znaku handlowego bo to już adres, ale myślę, że słyszałem go tutaj. [Animacja] Jak duży jest? Dobrze, że nie mówisz scanf jak duży bufor ten jest co oznacza, że ​​nawet jeśli bufor był wskaźnik, mówimy scanf, umieścić ciąg tutaj, , ale może być o 2 bajty, może być 10 bajtów, to może być megabajta. Scanf nie ma pojęcia, a ponieważ jest to fragment pamięci przypuszczalnie nie łańcuch jeszcze jest. To tylko raz napisać ciąg znaków i \ 0 do tego kawałka pamięci. Teraz to tylko niektóre fragment pamięci. Scanf nie będą wiedzieć, kiedy przestać pisać na ten adres. 

Jeśli pamiętacie jakieś przykłady z przeszłości, gdzie losowo wpisane na klawiaturze próby przepełnienia bufora, i rozmawialiśmy w piątek o dokładnie to. Jeśli przeciwnik jakoś wstrzykuje do programu znacznie większy słowo lub zdanie lub frazę, a następnie się spodziewałeś możesz opanowane fragment pamięci, który może mieć złe konsekwencje, jak przy całym programie. Musimy to naprawić jakoś. Pozwól oddalić i iść do wersji 3 tego programu. To jest trochę lepiej. W tej wersji, zauważysz różnicy. W linii 16, ja ponownie deklarując zmienną bufor, ale to, co jest teraz? Jest to tablica z 16 znaków. To jest dobre, bo to oznacza, że ​​mogę teraz powiedzieć scanf tutaj jest rzeczywisty fragment pamięci. Można niemal pomyśleć tablic jako wskaźniki teraz nawet jeśli nie są one rzeczywiście równoważne. Oni zachowują się inaczej w różnych kontekstach. Ale to na pewno tak, że bufor jest odwołanie 16 sąsiadujących znaki bo tak tablica jest i został na kilka tygodni teraz. 

Tutaj mówię scanf oto fragment pamięci. Ten czas, to rzeczywiście fragment pamięci, ale dlaczego jest to program nadal użytecznym? Co jest nie tak nadal? Powiedziałem, daj mi 16 bajtów, ale- [Student] Co jeśli wpisać w więcej niż 16? Dokładnie, co zrobić, jeśli użytkownik wpisze w 17 znaków lub znaków 1700? W rzeczywistości, zobaczymy, czy nie możemy potknąć tego błędu teraz. Jest lepiej, ale nie idealnie. Pozwól mi iść dalej i uruchomić make scanf3 skompilować ten program. Pozwólcie mi biegać scanf3, String proszę: witam, i wydaje się być w porządku. Spróbuję nieco dłuższa, hello tam. Dobra, zróbmy hello there jak się masz dziś, Enter. Uzyskiwanie rodzaju szczęście tutaj, powiedzmy hello there jak się masz. Cholera. Ok, więc mamy szczęście. Zobaczymy, czy nie możemy rozwiązać. Nie, to nie pozwolę, żeby mnie skopiować. Spróbujmy jeszcze raz. Dobra, czekaj. Zobaczymy, jak długo można udawać, że się skupić, a jednocześnie w ten sposób. Cholera. To raczej właściwe, faktycznie. Proszę bardzo. Punkt wykonane. 

To, że kłopotliwe jest również, że jest jednym ze źródeł wielkiej błąd podczas pisania programów, które mają błędy, ponieważ pojawiają się tylko raz na jakiś czas, czasami. W rzeczywistości jest to, że nawet jeśli Twój kod jest całkowicie złamana, może być całkowicie przerwane raz na jakiś czas bo czasem, zasadniczo co się dzieje jest system operacyjny przydziela trochę więcej pamięci niż rzeczywiście potrzebujesz jakiegoś powodu i tak nikt nie korzysta z pamięci tuż po fragmencie 16 znaków, więc jeśli się do 17, 18, 19, cokolwiek, to nie jest taki duży problem. Teraz komputer, nawet jeśli nie upaść w tym punkcie, może w końcu używać bajtowy numer 17 lub 18 lub 19 na coś innego, w tym momencie swoje dane, które można umieścić tam, choć zbyt długo, dostanie nadpisane potencjalnie przez inną funkcję. To nie koniecznie będzie pozostają nienaruszone, ale nie musi spowodować SEG błąd. Ale w tym przypadku, w końcu pod warunkiem wystarczającej liczby znaków że istotnie przekroczył moje segment pamięci i bam, system operacyjny, powiedział: "Przykro mi, że nie jest dobrze, segmentation fault". 

I zobaczymy teraz, jeśli to, co pozostaje w moim katalogu- zauważyć, że mam ten plik tutaj, rdzeń. Zauważ, że jest to po raz kolejny wezwała zrzut pamięci. Jest to w istocie plik zawierający treść twojego programu w pamięci w punkcie, w którym rozbił i po prostu spróbować trochę przykład tutaj zostaw mnie tutaj i uruchomić gdb na scanf3 a następnie określić trzeci argument zwany rdzeń, i tutaj odnotować, że jeśli listy kod, będziemy w stanie jak zwykle z gdb zacząć chodzić w ramach tego programu, i mogę go uruchomić i jak tylko hit-jak z polecenia krok w GDB- jak tylko uderzyć potencjalnie wadliwą linię po wpisaniu w ogromnym ciągu, Będę w stanie rzeczywiście określić to tutaj. Więcej na ten temat, choć w części w zakresie podstawowych wysypisk a jak tak, że rzeczywiście można poruszać się wewnątrz zrzutu pamięci i zobaczyć na jakiej linii program nie ciebie. Wszelkie pytania, a następnie na wskaźniki i adresów? Bo dzisiaj mamy zamiar zacząć brać za pewnik, że te rzeczy istnieją i wiemy dokładnie, jakie są. Tak. 

[Animacja] Jak to nie masz umieścić ampersand obok częściowo Dobre pytanie. Jak to nie miałem umieścić ampersand obok tablicy znaków jak ja wcześniej większość naszych przykładach? Odpowiedź jest krótka: tablice są trochę specjalnego. Można niemal pomyśleć bufor jak faktycznie jest adres, i to właśnie tak dzieje się tak, że zapis kwadratowy nawias jest wygoda tak, że możemy iść do przedziału 0, wspornik 1, Uchwyt 2, bez konieczności używania do zapisu *. To trochę białego kłamstwa, ponieważ tablice i wskaźniki są w rzeczywistości, trochę inaczej, ale często, ale nie zawsze są stosowane zamiennie. W skrócie, gdy funkcja oczekuje wskaźnika do kawałka pamięci, możesz przekazać go adresu, który został zwrócony przez malloc, i zobaczymy malloc ponownie niedługo, czy można przekazać jej nazwę tablicy. Nie musisz robić ampersand z tablicami, ponieważ są one już zasadniczo jak adresy. To jest jeden wyjątek. Nawiasy kwadratowe uczynić je wyjątkowym. 

Można umieścić ampersand obok bufora? Nie w tym przypadku. Które nie działa, ponieważ, ponownie w tym przypadku naroża gdzie tablice nie są dość rzeczywiście adresy. Ale będziemy chyba wrócić do tego wkrótce z innymi przykładami. Spróbujmy rozwiązać problem. Mamy strukturę danych, które używaliśmy pewnego czasu znany jako tablica. Sprawa w punkcie, to co mieliśmy tylko. Ale tablice mają jakieś upsides i wady. Tablice są ładne, dlaczego? Co jest jedna rzecz, która podoba Ci się-do tego stopnia chcesz tablice-o tablice? Jakie to wygodne o nich? Co jest atrakcyjne? Dlaczego możemy wprowadzić je w pierwszej kolejności? Tak. [Student] Mogą przechowywać dużo danych i nie trzeba używać całej rzeczy. Możesz użyć sekcji. Dobre, z tablicy można przechowywać dużo danych, i nie muszą korzystać z niego wszyscy, więc można alokuj, co może być wygodne, jeśli nie wiesz z góry, ile z czymś się spodziewać. 

GetString jest doskonałym przykładem. GetString, napisane przez nas, nie ma pojęcia, ilu znaków się spodziewać, więc fakt, że możemy przeznaczyć kawałkami ciągłej pamięci jest dobry. Tablice także rozwiązać problem widzieliśmy kilka tygodni temu, teraz gdzie kod zaczyna sprowadzać się do czegoś bardzo źle zaprojektowane. Przypomnijmy, że stworzył struktury studentów nazwie David, , a następnie, że faktycznie alternatywą jednak do posiadania zmienną nazwę i innej zmiennej nazwie, myślę, house, i innej zmiennej o nazwie ID, bo w tej historii Potem chciał wprowadzić coś innego lubię Roba do programu, tak, to postanowiłem poczekać minutę, Trzeba zmienić nazwy tych zmiennych. Nazwijmy kopalni nazwa1, ID1, House1. Nazwijmy Roba nazwa2 house2, ID2. Ale potem czekaj, a co z Tommym? Potem mieliśmy jeszcze trzy zmienne. Wprowadziliśmy kogoś innego, czterech zestawów zmiennych. Świat zaczął się bałagan bardzo szybko, więc wprowadziliśmy przypisać struktury, a co fascynującego struct? Co struct C pozwala zrobić? To bardzo niewygodne dziś. Co? >> [Niesłyszalne odpowiedź uczeń] Tak, konkretnie typedef pozwala utworzyć nowy typ danych, i struct, słowo kluczowe struct, pozwala upakować koncepcyjnie podobne fragmenty danych wraz a potem je nazwać coś takiego studenta. 

To było dobre, bo teraz możemy modelować bardziej rodzaj koncepcyjnie spójne pojęcie ucznia w zmiennej a nie o arbitralnie jeden dla łańcucha, po jednym dla identyfikatora, i tak dalej. Tablice są dobre, bo pozwalają nam rozpocząć sprzątanie naszego kodu. Ale co jest minusem teraz z tablicy? Czego nie może zrobić? Tak. [Student] Musisz wiedzieć, jak duże jest. Musisz wiedzieć, jak duże jest, więc jest to rodzaj bólu. Ci z was, z wcześniejszego doświadczenia programowania wiedzieć, że w wielu językach, jak Java, możesz poprosić kawałek pamięci, specjalnie z tablicy jak wielki jesteś, o długości, własności, że tak powiem, i to jest naprawdę wygodne. W C, nie można nawet nazwać strlen na ogólny tablicy ponieważ strlen, jak wskazuje nazwa, jest tylko na smyczki, i możesz dowiedzieć się długość łańcucha z powodu tej ludzkiej konwencji posiadania \ 0, ale tablicę, bardziej ogólnie, to tylko fragment pamięci. Jeśli to jest tablica liczb całkowitych, nie będzie to jakiś znak specjalny Na koniec czeka na ciebie. Trzeba pamiętać, długość tablicy. Kolejnym ograniczeniem tablicy hodowane głowę w getString się. Co jest kolejnym minusem tablicy? Panie, tylko Ty i ja dzisiaj. [Niesłyszalne reakcja studentów] >> To co? To uznany na stosie. Okay, oświadczył na stosie. Może ci się to podoba? [Student] Ponieważ pobiera ponownie. To staje się ponownie. Dobrze, jeśli używać tablicy do przydzielania pamięci, Nie można, na przykład, powrócić, bo to jest na stosie. Dobrze, że to wada. A jak o jedna z tablicy? Po jej podziału, jesteś rodzajem skręcane, jeśli potrzebujesz więcej miejsca niż tablica ma. 

Następnie wprowadzono przypominam, malloc, który dał nam możliwość dynamicznego przydzielania pamięci. Ale co, jeśli staraliśmy zupełnie inny świat? Co zrobić, jeśli chcemy rozwiązać kilka tych problemów więc zamiast tego-moje pióro zasnął tu co, jeśli zamiast tego chciał stworzyć świat w zasadzie to już nie tak? Jest tablica, oraz, oczywiście, w tym rodzaju pogarsza Po hit koniec tablicy i teraz już nie ma miejsca dla innej liczby całkowitej lub innego charakteru. Co jeśli rodzaj preemptively powiedzieć dobrze, dlaczego nie możemy się zrelaksować ten wymóg, że wszystkie te kawałki pamięci graniczyć z powrotem do tyłu, i dlaczego nie, gdy trzeba int lub char, Daj mi przestrzeń dla jednej z nich? A kiedy trzeba innego, daj mi jeszcze jedną przestrzeń, i kiedy potrzebuję innego, daj mi jeszcze jedną przestrzeń. Zaletą jest to, że, które teraz, jeżeli ktoś trwa pamięć tutaj, nic wielkiego. Wezmę tę dodatkową ilość pamięci tutaj, a potem ten jeden. 

Teraz, tylko haczyk tutaj jest to, że niemal czuje się jak mam cała masa różnych zmiennych. To czuje się jak pięć różnych zmiennych potencjalnie. Ale co, jeśli moglibyśmy ukraść pomysł z łańcuchów którym możemy jakoś połączyć te rzeczy razem koncepcyjnie, a co jeśli to zrobił? To jest moja bardzo słabo rysowane strzałki. Jednak sądzić, że każdy z tych kawałków pamięci wskazał na inny, a ten facet, który nie ma rodzeństwa w prawo, nie ma takiego strzałkę. Jest to w istocie to, co nazywa linked lista. Jest to nowa struktura danych, która pozwala nam przeznaczyć kawałek pamięci, potem drugi, potem jeszcze jeden, potem drugi, za każdym razem chcemy w trakcie programu, a musimy pamiętać, że wszystkie one są w jakiś sposób związane z przez dosłownie łańcuchowym je razem, a zrobiliśmy to obrazowo tutaj strzałką. Ale w kodzie, co będzie mechanizm, przez który można było jakoś połączyć, prawie jak Scratch, jeden kawałek na inny kawałek? Moglibyśmy użyć wskaźnika, prawda? Bo tak naprawdę strzałka idzie od góry kwadrat po lewej, ten facet, żeby ten jeden, może zawierać w środku tego placu nie tylko niektóre wskazówki, nie tylko niektóre char, ale co jeśli ja faktycznie przydzielone trochę więcej przestrzeni, tak, że teraz, każdy z moich kawałków pamięci, choć to będzie mnie kosztować, Teraz wygląda trochę bardziej prostokątny, gdzie jednym z fragmentów pamięci jest wykorzystywane do wielu, jak numer 1, a następnie, jeśli ten facet zapisuje numer 2, ten drugi fragment pamięci jest używana przez strzałki, lub bardziej konkretnie wskaźnik. I załóżmy, że zapisać numer 3, a ja tu użyć tego wskazać na tego faceta, a teraz ten facet, załóżmy, chcę tylko trzy takie kawałki pamięci. Będę narysować linię przez to, wskazując null. Nie ma żadnych dodatkowych znaków. 

Rzeczywiście, jest to w jaki sposób możemy przejść o implementowaniu coś, co się nazywa linked lista. Połączonej listy jest nowa struktura danych, i to krokiem w kierunku znacznie bardziej wyszukane struktury danych, które zaczynają rozwiązywać problemy wzdłuż linii problemach typu Facebook i Google typu problemów gdzie masz ogromne zbiory danych, a to już nie przecina go przechowywać wszystko ciągły i używać coś liniowego wyszukiwania lub nawet coś binarnego wyszukiwania. Chcesz jeszcze lepiej razy z rzędu. W rzeczywistości, jeden z Świętych Grails porozmawiamy o tym tygodniu lub przyszłym Jest to algorytm, którego czas trwania jest stały. Innymi słowy, nie ma zawsze ten sam czas niezależnie jak duże wejście jest, i że rzeczywiście być przekonujące, nawet bardziej niż coś logarytmicznego. Co to jest na ekranie, tutaj? Każdy z prostokątów jest dokładnie to, co właśnie zwrócił się ręcznie. Ale rzeczą aż po lewej stronie jest specjalna zmienna. To będzie jeden wskaźnik, ponieważ jeden gotcha z połączonej listy, jak te rzeczy są nazywane, jest to, że trzeba się trzymać jednego końca połączonej listy. 

Podobnie jak w ciągu, musisz znać adres pierwszego char. Samą ofertę w połączonych listach. Musisz znać adres pierwszego kawałka pamięci bo z tego miejsca można dotrzeć do każdej innej. Minusem. Jaką cenę jesteśmy płacić za to wszechstronność o dynamicznie Spora struktura danych, że jeśli kiedykolwiek potrzebują więcej pamięci, porządku, tylko przydzielić jeden kawałek i wyciągnąć wskaźnik z starego do nowego ogona listy? Tak. [Student] To trwa około dwa razy tyle miejsca. To zajmuje dwa razy więcej miejsca, więc to na pewno minusem, i widziałem to kompromis między przed czasem i przestrzenią i elastyczność gdzie już nie musimy 32 bitów dla każdej z tych liczb. Naprawdę potrzebujemy 64, 32 dla numeru i 32 dla wskaźnika. Ale hej, mam 2 GB pamięci RAM. Dodawanie kolejnych 32 bitów tutaj i tutaj nie wydaje się, że nic wielkiego. Ale dla dużych zbiorów danych, to na pewno dodaje się dosłownie dwa razy tyle. Co jest kolejnym minusem teraz lub co fabularnego możemy zrezygnować, jeśli stanowią listy rzeczy z połączonej listy, a nie tablicy? [Student] Nie można przechodzić do tyłu. Nie można przechodzić do tyłu, więc jesteś trochę przykręcony jeśli jesteś w odległości od lewej do prawej za pomocą pętli for lub pętli while a potem zdajesz sobie sprawę, "Och, chcę wrócić do początku listy." Nie można, ponieważ te wskaźniki tylko iść od lewej do prawej strzałki wskazują. 

Teraz może pamiętacie początek listy z innej zmiennej, ale to jest złożoność, aby pamiętać. Array, nie ważne jak daleko pójdziesz, zawsze można zrobić minus, minus, minus, minus i wracaj skąd przyszedłeś. Co jest kolejnym minusem tutaj? Tak. [Niesłyszalne pytanie uczeń] Można, więc już właściwie tylko zaproponowano strukturę danych zwaną listy dwukierunkowe, i rzeczywiście, możesz dodać kolejny wskaźnik, aby każdy z tych prostokątów że idzie w innym kierunku, do góry z których to teraz możesz przechodzić tam iz powrotem, Minusem, który obecnie używasz trzy razy tyle pamięci, jak kiedyś oraz zwiększania ich złożoności pod względem kodu musisz napisać aby zrobić to dobrze. Ale to wszystko może bardzo rozsądne kompromisy, jeśli odwrócenie jest ważniejsza. Tak. [Student] Nie można również mieć 2D połączonej listy. Dobry, naprawdę nie można mieć 2D połączonej listy. Można. To nie jest aż tak proste, jak w tablicy. Jak tablica, masz otwarty nawias, zamknięty nawias, nawias otwarty, zamknięty nawias, i masz jakieś 2-wymiarową strukturę. Można wdrożyć 2-wymiarowy połączonej listy jeśli nie dodatek jak proponowany-jedna trzecia wskaźnik do każdego z tych rzeczy, i jeśli myślisz o innej listy przyjście na Ciebie stylu 3D z ekranu, aby każdy z nas, który jest po prostu inny łańcuch jakiejś. Możemy to zrobić, ale to nie jest tak proste, jak wpisanie otwarty nawias, nawias kwadratowy. Tak. [Niesłyszalne pytanie uczeń] Dobrze, więc jest to prawdziwy kicker. 

Te algorytmy, że mamy pined nad, jak oh, wyszukiwanie binarne, możesz szukać tablicy liczb na planszy lub książka telefoniczna więc znacznie szybciej, jeśli używasz dziel i rządź i algorytm wyszukiwania binarnego, ale szukanie binarne wymagane dwa założenia. Jeden, że dane zostały posortowane. Teraz możemy przypuszczalnie mieć to posortowane, więc może to nie zmartwienie, ale także zakłada wyszukiwanie binarne że miał swobodny dostęp do listy numerów, i tablica pozwala mieć swobodny dostęp, oraz losowego dostępu, To znaczy, jeśli dostaniemy tablicę, ile czasu zajmuje Ci aby dostać się do przedziału 0? Jedna operacja, wystarczy użyć funkcji [0] a ty jesteś tam. Ile kroków trzeba zrobić, aby dostać się do miejsca 10? Jeden krok, po prostu idź do [10] i tam jesteś. Natomiast jak masz do 10 całkowitą w połączonej listy? Trzeba zacząć od początku, bo jesteś tylko pamiętając początek połączonej listy, podobnie jak ciąg jest pamiętać przez adres jego pierwszego znaku, a okaże się, że 10-gi int lub 10-ga znak w ciągu, trzeba szukać całe cholerstwo. 

Ponownie, nie jesteśmy rozwiązania wszystkich naszych problemów. Jesteśmy wprowadzenie nowych, ale to tak naprawdę zależy od tego, co próbujesz do projektowania. W zakresie realizacji tego możemy pożyczyć pomysł z tej struktury studentów. Składnia jest bardzo podobna, z wyjątkiem teraz, idea jest trochę bardziej abstrakcyjne niż dom i nazwa i ID. Ale proponuję, możemy mieć struktury danych w C że nazywa się węzeł, jako ostatnie słowo na slajdzie sugeruje wewnątrz węzła i węzeł jest tylko ogólny pojemnik w informatyce. To zwykle rysowany jako okrąg lub kwadrat lub prostokąt jak zrobiliśmy. I w tej strukturze danych, mamy int, n, więc to liczba chcę zapisać. Ale co to jest druga linia, struct node * next? Dlaczego jest to poprawne, jaką rolę gra ta sprawa, nawet jeśli jest to trochę tajemnicze na pierwszy rzut oka? Tak. [Niesłyszalne odpowiedź uczeń] Dokładnie, więc sort * łupów, że to pewnego rodzaju wskaźnik. Nazwa tego wskaźnika jest arbitralnie następny, ale mogliśmy nazwał to co chcemy, ale co ten punkt wskaźnik? [Student] Kolejny węzeł. >> Dokładnie, to wskazuje na innego takiego węzła. 

Teraz, to jest coś w rodzaju ciekawości C. Przypomnijmy, że C jest odczytywany przez kompilator góry do dołu, od lewej do prawej, co oznacza, że ​​jeśli-to jest trochę inny od tego, co zrobiliśmy ze studentem. Kiedy określona studenta, faktycznie nie włożył słowa tam. To właśnie powiedział typedef. Potem mieliśmy int id, nazwa String, String dom, , a następnie w dolnej uczeń struktury. Deklaracja ta jest nieco inna, ponieważ, ponownie, kompilator C jest trochę głupie. To tylko będzie czytać od góry do dołu, więc jeśli dojdzie do 2. linii tutaj gdzie obok jest deklarowana, a nie widzi, oh, tutaj jest zmienna nazywa się następny. Jest to wskaźnik do węzła struktury. Kompilator będzie zrozumieć, co jest węzeł struct? I nigdy nie słyszałem o tej rzeczy przed, ponieważ węzeł słowa nie mogłyby pojawić się do dołu, tak, że jest to zwolnienie. Masz do powiedzenia węzeł struct tutaj, które następnie można skrócić później dzięki typedef tu, ale to dlatego, mamy odwołanie się do samej struktury wewnątrz konstrukcji. To jest jeden haczyk tam. 

Niektóre interesujące problemy będą się pojawiać. Mamy listę numerów. Jak możemy wstawić do niego? Jak możemy go przeszukać? W jaki sposób usunąć z niego? Szczególnie teraz, że musimy zarządzać wszystkim z tych wskaźników. Myślałeś wskaźniki były rodzaju umysł gięcia kiedy miał jeden z nich po prostu próbuje odczytać int do niego. Teraz musimy manipulować całą listę warto. Dlaczego nie bierzemy 5-minutową przerwę, tu, a potem wnosimy niektórzy ludzie na scenie, aby zrobić dokładnie to. 

C jest dużo więcej zabawy, kiedy to działała na zewnątrz. Kto by dosłownie jak być pierwszy? Dobra, chodź na górę. Jesteś pierwszy. Kto chciałby być 9? Okay, 9. Jak o 9? 17? Trochę klika tutaj. 22 i 26, w tym rzędzie. A następnie, jak o kimś tam zostały wskazał. Jesteś 34. Dobra, 34, dalej w górę. Najpierw jest tam. Okay, wszystkie cztery z was. A kto nie mówimy o 9? Kim jest nasz 9? Kto naprawdę chce być 9? Dobra, chodź, będzie 9. Jedziemy. 34, spotkamy się tam. Pierwsza część jest zrobić sobie wyglądać. 26, 22, 17, dobrze. Jeśli można stać z boku, bo mamy zamiar przydzielić cię w jednej chwili. 

Dobrze, dobrze. Okay, doskonała, więc niech to zadać kilka pytań. I rzeczywiście, jak masz na imię? >> Anita. Anita, dobra, chodź tutaj. Anita pomoże nam rozwiązać jeden rodzaj dość proste pytanie w pierwszym, który jest jak znaleźć, czy wartość jest na liście? Teraz należy zauważyć, że po pierwsze, reprezentowane tu przez Lucas jest trochę inny, a więc jego kawałek papieru jest celowo bokiem bo to nie jest aż tak wysoki i nie zajmują tyle bitów, choć technicznie ma taki sam rozmiar papieru tylko obracać. Ale on jest trochę inny w tym, że ma tylko 32 bitów dla wskaźnika, i wszystkie z tych facetów to 64 bitów, z których połowa jest numer, z czego połowa jest wskaźnik. Ale wskaźnik nie jest przedstawiony, więc jeśli macie może trochę niezgrabnie używać lewej ręki wskazać na osoby obok. A ty jesteś numer 34. Jak masz na imię? Ari. Ari, tak naprawdę, trzymać papier w prawej ręce, a lewa ręka idzie prosto w dół. Użytkownik oświadcza zerowy na lewo. 

Teraz nasz ludzki obraz jest bardzo spójne. To jest rzeczywiście jak wskaźniki pracy. I czy można scrunch trochę w ten sposób, więc nie jestem w drodze. Anita tutaj, znaleźć mi numer 22, ale zakładają ograniczenie: nie człowiek trzyma się kawałki papieru, ale jest to lista, i masz tylko Lucas zacząć bo jest dosłownie pierwszy wskaźnik. Załóżmy, że sam jesteś wskaźnik, i tak też mają możliwość, aby wskazywał na coś. Dlaczego nie zacząć od wskazując dokładnie, co Lucas wskazujesz? Dobra, i pozwól mi na to uchwalić tutaj. Dla samej dyskusji, chciałbym wyciągnąć pustą stronę tutaj. Jak się pisze twoje imię? >> Anita. Okay, Anita. Powiedzmy węzła * anita = Lucas. Cóż, nie powinniśmy nazywam lucas. Powinniśmy zadzwonić pierwszy. Dlaczego to jest w rzeczywistości zgodny z rzeczywistością tutaj? Jeden, pierwszy już istnieje. Pierwsza została przydzielona prawdopodobnie gdzieś tutaj. Wezel * pierwszy, i to zostało przyznane listę jakoś. Nie wiem jak to się stało. Było to jeszcze przed klasa zaczęła. Ta związana lista ludzi został stworzony. A teraz w tym momencie historia-to wszystko dzieje Facebook najwyraźniej później- W tym momencie w historii Anita zainicjowaniu równa najpierw co nie znaczy, że punkty Anita na Lucasa. Przeciwnie, wskazuje ona na to, co wskazuje na ponieważ ten sam adres, który znajduje się wewnątrz bitów 32 Lucasa - 1, 2, 3 - jest teraz także wewnątrz bitów 32 Anity - 1, 2, 3. 

Teraz znajdź 22. Jak byś się za to zabrać? Co to jest? >> Point na cokolwiek. Wskazywać na cokolwiek, więc śmiało i działać go najlepiej jak można tutaj. Dobrze, dobrze, a teraz wskazuje na-jak masz na imię z 22? Ramon. >> Ramon, więc Ramon trzyma się 22. Masz teraz zrobić czek. Czy Ramon == 22, a jeśli tak, na przykład, możemy powrócić true. Pozwól mi, a te chłopaki tu stać nieco niezgrabnie- pozwól mi zrobić coś szybko jak bool znaleźć. Mam zamiar iść do przodu i powiedzieć (node ​​* lista, int n). Zaraz będę z powrotem z wami. Muszę napisać kod. I teraz mam zamiar iść do przodu i zrobić to, * węzła anita listę =. I mam zamiar iść do przodu i powiedzieć while (anita! = NULL). 

Metafora tutaj jest trochę rozciągnięty, ale jednocześnie (Anita! = NULL), co chcę zrobić? Potrzebuję jakiś sposób odwołującego całkowitą, która wskazuje na Anita. W przeszłości, gdy miały struktury, który to węzeł jest użyliśmy notacji dot, i powiedzieć coś w stylu anita.n, ale problemem jest to, że Anita nie jest struct per se. Czym ona jest? Jest to wskaźnik, tak naprawdę, jeśli chcemy korzystać z tej notacji dot- i to będzie wyglądać celowo trochę tajemnicze- mamy coś jak przejść do lewej dłoni Cokolwiek Anity jest skierowany na , a następnie dostać się pole o nazwie n. Anita jest wskaźnik, ale to, co jest * Anita? Co znajdziesz, gdy idziesz do co Anita wskazujesz? Struct, węzeł i węzeł, recall, posiada pole o nazwie n dlatego, że, przypomnijmy, te 2 pola, obok i N, które widzieliśmy przed chwilą tutaj. 

Aby rzeczywiście naśladować to w kodzie, możemy to zrobić i powiedzieć, że jeśli ((* anita). n == n), n, że ja szukam. Zauważ, że funkcja została przyjęta w numerze mi zależy. Wtedy mogę iść dalej i zrobić coś zwróci true. Indziej, jeśli nie jest to przypadek, co chcę zrobić? Jak mogę przetłumaczyć na kod co Anita zrobił intuicyjnie spaceru przez liście? Co należy zrobić, tu symulować Anita biorąc ten krok w lewo, to krok na lewo? [Niesłyszalne reakcja studentów] >> Co to jest? [Niesłyszalne odpowiedź uczeń] Dobra, nie jest to zły pomysł, ale w przeszłości, kiedy zrobiliśmy to, zrobiliśmy anita + + bo byłoby dodać numer 1 do Anity, , które zazwyczaj wskazują na następnej osoby, jak Ramon, lub osoba obok niego, lub obok niego człowiek w dół linii. Ale to nie jest dość dobry tu, bo co to sprawa wygląda w pamięci? Nie to. Musimy wyłączyć. Wygląda to w pamięci, i choć ja wyciągnąć 1 i 2 i 3 blisko siebie, jeśli naprawdę symulować to-can you guys, jednocześnie wskazując na tych samych ludzi, może niektórzy z was zdążają losową krok wstecz, niektórzy z was random krok do przodu? 

Ten bałagan jest jeszcze listę, ale ci faceci mogą być w dowolnym miejscu w pamięci, tak anita + + nie będzie działać, dlaczego? Co znajduje się w miejscu anita + +? Kto wie. Jest jakaś inna wartość, po prostu tak się dzieje, być wstawione wśród wszystkich tych węzłów przez przypadek, bo nie używamy tablicy. Mamy przeznaczone każdy z tych węzłów, indywidualnie. Dobrze, jeśli faceci może oczyścić siebie z powrotem. Pozwól mi zaproponować zamiast anita + +, ale zamiast zrobić anita pobiera- dobrze, dlaczego nie idziemy do Anita cokolwiek wskazuje na, a następnie zrobić. następny? Innymi słowy, możemy przejść do Ramon, który trzyma numer 22, i wtedy. obok jest jakby Anita będzie skopiowanie jego lewy wskaźnik dłoni. Ale ona nie chciała iść dalej niż Ramon ponieważ znaleźliśmy 22. Ale to byłoby idea. Teraz, to jest Bóg-okropne bałagan. Szczerze mówiąc, nikt nie będzie pamiętać tej składni, i tak na szczęście, to rzeczywiście mało celowe-oh, to faktycznie nie widzieć tego, co napisałem. To byłoby bardziej przekonujące, jeśli można. Voila! 

Za kulisami, ja rozwiązać problem w ten sposób. Anita, do podjęcia tego kroku w lewo, Najpierw idź do adresu, który wskazuje na Anita i gdzie będzie znaleźć nie tylko n, które właśnie sprawdzony dla porównania, ale można również znaleźć następne - w tym przypadku, Lewa Ramon wskazując kolejnego węzła na liście. Ale to bóg-okropne bałagan, o którym wspomniałem wcześniej, ale okazuje się, C pozwala nam to ułatwić. Zamiast pisać (* anita), możemy zamiast po prostu napisać Anita-> n, i to jest dokładnie to samo, funkcjonalnie, ale jest to dużo bardziej intuicyjny, i to o wiele bardziej zgodne z obrazu, który został nam rysunek cały ten czas za pomocą strzałek. 

Wreszcie, co musimy zrobić, w końcu w tym programie? Jest jedna linia kodu pozostałych. Powrót co? False, ponieważ jeśli mamy przez całość pętli while Anita i w rzeczywistości, pusty, co oznacza, że ​​weszła aż do końca listy gdzie wskazywał na-co masz na imię? Lewa Ariego. >> Ari, która jest null. Anita jest teraz pusty, i zdaję sobie sprawę, jesteś po prostu stoję tu niezręcznie w stanie zawieszenia ponieważ mam zamiar się na monologu tutaj ale musimy zaangażować ponownie za chwilę. Anita jest pusty w tym momencie w historii, więc pętla kończy się, i musimy zwrócić wartość false, bo jeśli ona ma aż do pustego wskaźnika Ari potem nie było, że liczba szukała w liście. Możemy oczyścić to zbyt, ale to jest bardzo dobre wykonanie, a następnie przechodzenia z funkcji, znaleźć funkcję dla połączonej listy. To wciąż liniowa search, ale to nie jest tak proste, jak + + wskaźnik lub + + zmienna i dlatego teraz nie możemy odgadnąć w którym każdy z tych węzłów jest w pamięci. Mamy dosłownie szlakiem panierce lub, bardziej szczegółowo, wskaźniki, aby dostać się z jednego węzła do drugiego. 

Teraz spróbujmy jeszcze jednego. Anita, czy chcesz tu wrócić? Dlaczego nie pójść dalej i przydzielić jedną osobę z publiczności? Malloc-jak masz na imię? >> Rebecca. Rebecca. Rebecca została malloced z publicznością, i ona jest teraz przechowywania liczby 55. A celem jest teraz w zasięgu ręki dla Anita wstawić Rebecca do połączonej listy tutaj, w jego właściwe miejsce. Chodź tutaj na chwilę. Zrobiłem coś takiego. Zrobiłem węzła *. A jakie jest twoje imię? Rebecca. >> Rebecca, okay. Rebecca ma malloc (sizeof (node)). Tak jak my przyznajemy rzeczy jak studentów i etażerka w przeszłości, musimy wielkość węzła, więc teraz Rebecca wskazuje na co? Rebecca ma dwa pola wewnątrz niej, z których jeden jest 55. Zróbmy co, rebecca-> = 55. Ale potem rebecca-> next-jak powinno być teraz, jej ręka jest jakby kto wie? To wskazuje na pewną wartość śmieci, więc dlaczego nie zrobić na dokładkę możemy przynajmniej zrobić tak, że lewa ręka jest teraz u jej boku. Teraz Anita, weź go stąd. Masz Rebecca zostały przydzielone. Idź przed siebie i dowiedzieć się, gdzie powinniśmy umieścić Rebecca. Dobrze, bardzo dobrze. Dobra, dobra, a teraz musisz zapewnić trochę kierunku, tak dodzwoniłeś Ari. Jego lewa ręka jest pusta, ale Rebecca wyraźnie należy do prawej, jak więc musimy zmienić ten połączonej listy w celu wprowadzenia Rebekę do odpowiedniego miejsca? Gdybyś mógł dosłownie przenieść lewy ludzi rękami w razie potrzeby, my rozwiązać problem w ten sposób. Dobra, dobra, a tymczasem, lewy Rebeki jest teraz u jej boku. 

To było zbyt łatwe. Spróbujmy alokacji, ale jesteśmy prawie gotowe, 20. Dobra, chodź na górę. 20 została przydzielona, ​​więc pozwól mi iść do przodu i powtarzam tutaj mamy tylko zrobić Saad * węzła. Mamy malloc (sizeof (node)). Następnie zrobić to samo dokładnej składni jak my przed na 20, i zrobię następny = NULL, a teraz to do Anita można wstawić do połączonej listy, jeśli można grać dokładnie to samo znaczenie. Execute. Dobra, dobra. Teraz zastanów, zanim zacznie się lewe ręce wokół. Jesteś zdecydowanie dostał najbardziej niezręcznej roli dziś. Którego ręka powinna być przeniesiona w pierwszej kolejności? Dobra, czekaj, słyszę niektóre nie tych. Jeśli niektórzy ludzie nie grzecznie ci pomóc rozwiązać niezręczną sytuację. Czyje lewa ręka powinna być aktualizowany jako pierwszy być może? Tak. [Student] Saad tych. Okay, Saad, to dlaczego, chociaż? [Niesłyszalne odpowiedź uczeń] Dobrze, bo jeśli będziemy poruszać się-jak masz na imię? >> Marshall. Marshall, jeśli przenieść rękę pierwszą w dół na null, teraz mamy dosłownie osierocony cztery osoby na tej liście bo był jedyną rzeczą, wskazując na Ramon i wszyscy w lewo, więc aktualizacji tego wskaźnika pierwszy był zły. Załóżmy, że cofnąć. Dobra, a teraz idź i przesuwaj odpowiednią lewą rękę wskazując na Ramon. To czuje się trochę zbędny. Teraz mamy dwie osoby wskazujące na Ramon, ale to jest w porządku bo teraz jak inaczej możemy zaktualizować listę? Co z drugiej strony ma się ruszać? Doskonały, teraz straciliśmy jakąkolwiek pamięć? No, tak dobrze, zobaczymy, czy nie możemy przełamać raz. 

Mallocing raz ostatni numer 5. Całą drogę z tyłu, chodź na dół. To bardzo ekscytujące. [Oklaski] Jak masz na imię? >> Ron. Ron, dobra, jesteś malloced jak numer 5. Właśnie wykonywany kod, który jest prawie identyczne do tych tylko z nazwy innego. Excellent. Teraz, Anita, powodzenia wstawiając numer 5 na liście teraz. Dobre, i? Doskonała, więc jest to naprawdę trzeci z trzech całości spraw. Najpierw był ktoś w końcu, Rebecca. Musieliśmy potem kogoś w środku. Teraz mamy kogoś na początku, w tym przykładzie, było teraz aktualizacji Lucas po raz pierwszy ponieważ pierwszy element listy ma teraz do punktu na nowy węzeł, który z kolei wskazuje na węźle numer 9. 

To było ogromnie niewygodne demonstracja, jestem pewien, tak duże brawa dla tych ludzi, jeśli możesz. Ładnie wykonane. To wszystko. Możesz zachować swoje kawałki papieru za mało pamięci. Okazuje się, że robi to w kodzie nie jest tak proste, jak po prostu się rękami i wskazując wskaźniki w różnych rzeczach. Ale świadomość, że jeśli chodzi o czas, aby wdrożyć coś takiego połączonej listy lub wariant to jeśli skupić się na naprawdę te podstawowe fundamenty, na bite-rozmiar problemów mam się dowiedzieć, to jest ta ręka lub ręka ta, że ​​to, co w inny sposób jest dość skomplikowany program może, w rzeczywistości, być zmniejszona do stosunkowo prostych bloków jak ta. 

Weźmy sprawy w kierunku bardziej zaawansowanych nadal. Teraz mamy pojęcie połączonej listy. Mamy też-dzięki sugestii powrotnej-listy podwójnie połączonej, które wygląda prawie tak samo, ale teraz mamy dwa wskaźniki wewnątrz struktury zamiast jednego, i moglibyśmy prawdopodobnie nazywają te wskaźniki poprzedni i następny lub w lewo lub w prawo, ale nie w rzeczywistości, trzeba dwa. Kod będzie trochę bardziej skomplikowane. Anita musiałby zrobić więcej pracy tutaj, na scenie. Ale możemy z pewnością wdrożenie tego rodzaju konstrukcji. W zakresie czasu pracy, chociaż, co będzie czas pracy dla Anita znalezienia n Liczba w połączonej listy teraz? Nadal duże O n, więc jest to nie lepiej niż liniowej wyszukiwania. Nie możemy zrobić wyszukiwanie binarne, chociaż raz. Dlaczego tak się dzieje? Nie można skakać. Chociaż oczywiście zobaczyć wszystkich ludzi na scenie, i Anita mogła eyeballed go i powiedział: "Oto jest w środku na liście" ona nie wie, że gdyby była program komputerowy ponieważ jedyną rzeczą musiała zatrzask na początku w scenariuszu był Lucas, który jako pierwszy wskaźnik. Chciała koniecznie wykonaj te linki, licząc jej drogę, aż znalazła się mniej więcej w środku, a nawet jeśli, to nie będzie wiedzieć, kiedy ona się na środku chyba idzie się aż do końca, aby dowiedzieć się, jak wiele ich jest, następnie cofa się, i że zbyt trudno byłoby chyba, że podwójnie połączonej listy pewnego rodzaju. 

Rozwiązywaniu problemów już dziś, ale wprowadzenie innych. Co o innej strukturze danych w ogóle? To jest zdjęcie z tac w Mather House, w tym przypadku, mamy strukturę danych mamy również rodzaj już mówi. Rozmawialiśmy o stosie w kontekście pamięci, a to jakby celowo nazwany ze stosu w zakresie pamięci jest skutecznie struktura danych, która ma coraz więcej rzeczy, nałożono na niego. Ale ciekawe o stos, jak to ma miejsce w rzeczywistości, jest to, że specjalny rodzaj struktury danych. Jest to struktura danych w której pierwszy element jest ostatnim elementem na zewnątrz. Jeśli jesteś pierwszy podajnik należy umieścić na stosie, masz zamiar być niestety ostatnio tacy należy wziąć ze stosu, i to nie koniecznie coś dobrego. Odwrotnie, może myślisz o tym drugą stronę, ostatni jest pierwszym na zewnątrz. 

Teraz, czy wszelkie scenariusze przychodzą do głowy, gdy o stos struktura danych, gdzie trzeba, że ​​majątek z ostatnich, pierwsze wyszło, w rzeczywistości jest przekonujące? Czy to jest dobre? Czy to źle? To na pewno źle, gdyby podajniki nie były identyczne i były wszystkie specjalne różne kolory lub czymkolwiek innym, i kolor chcesz to wszystko tak na dole. Oczywiście, nie można dostać się, że bez wielkiego wysiłku. Musisz zacząć od góry i przesuwaj się w dół. Podobnie, co, jeśli jesteś jednym z tych chłopców wentylatorowych który czeka całą noc, próbując dostać iPhone i linie do góry w miejscu takim jak to? Czy nie byłoby miło, gdyby Apple Store były struktura danych stos? Yay! Nay? To jest dobre tylko dla ludzi, którzy pokazują się w ostatniej chwili ewentualnego , a następnie dostać wyrywałem kolejki. A w rzeczywistości, fakt, że byłem tak skłonny powiedzieć kolejkę jest rzeczywiście zgodny z tym, co my nazywamy ten rodzaj struktury danych, jeden w rzeczywistości, w której celem ma znaczenia, i chcesz pierwszy w być pierwszy jedna jeśli tylko ze względu na ludzi uczciwości. Będziemy ogólnie nazwać to struktura danych, kolejki. 

Okazuje się, oprócz połączonych list, możemy zacząć korzystać z tych samych podstawowych idei i zacznij tworzyć nowe i różne rodzaje rozwiązań problemów. Na przykład, w przypadku stos, możemy stanowią stos używając struktury danych tak, chciałbym zaproponować. W tym przypadku, mam zadeklarowane struct, a mówiłem wewnątrz tej struktury jest tablicą liczb, a następnie zmienna nazywa wielkość, i mam zamiar zadzwonić to coś stosu. Teraz, dlaczego to rzeczywiście działa? W przypadku stosu, mogę narysować to skutecznie na ekranie w postaci tablicy. Tu jest mój stosu. To są moje numery. I będziemy rysować je jak to, to, to, to, to. I wtedy jakiś inny element danych tutaj Rozmiar, które nazywa się, to jest tak, wielkość, i to jest liczba, i zbiorowo, cały iPad tutaj reprezentuje jeden stos struktury. Teraz domyślnie rozmiar został przypuszczalnie ma być ustawiony na 0, i to, co jest w środku w tablicy liczb początkowo kiedy po raz pierwszy przydzielić tablicy? Śmieci. Kto wie? I to naprawdę nie ma znaczenia. Nie ma znaczenia, jeżeli jest to 1, 2, 3, 4, 5, całkowicie losowo przez pecha przechowywanych w mojej strukturze, ponieważ tak długo, jak wiem, że rozmiar stosu jest 0, wtedy wiem, że programowo, nie patrzeć na każdy z elementów w tablicy. Nie ma znaczenia, co tam jest. Nie patrz na nich, jak będzie implikacją o rozmiarze 0. 

Ale załóżmy, że teraz śmiało i włożyć coś do stosu. Chcę wstawić numer 5, więc mogę umieścić numer 5 tutaj i to co mogę umieścić na dole? Teraz chciałbym faktycznie odłożył 1 o rozmiar i teraz stos jest wielkości 1. Co zrobić, gdy śmiało wstawić numer, powiedzmy, 7 następny? To następnie jest aktualizowany do 2, a następnie zrobimy 9, i wtedy ten zostanie zaktualizowany do 3. Ale ciekawostką teraz z tego jest to, że stos Mam się usunąć, który element, jeśli chcę pop coś się z komina, że ​​tak powiem? 9 będzie pierwszą rzeczą do zrobienia. Jak należy obraz zmienić, jeśli chcę, aby pop element ze stosu, podobnie jak podajnik w Mather? Tak. >> [Student] Rozmiar Ustaw 2. Dokładnie, wszystko co robię jest rozmiar do 2, a co mam zrobić z tablicy? Nie muszę nic robić. Mogłem, po prostu być anal, umieścić 0 tam lub -1 lub coś sygnalizujący że nie legit wartości, ale nie ma to znaczenia, ponieważ Mogę nagrać poza tablicą, jak długo jest tak, wiem, że patrzy tylko na dwóch pierwszych elementów w tej tablicy. Teraz, jeśli pójdę i dodać numer 8 na tej tablicy, w jaki sposób obraz zmienić następny? To staje się 8, a staje się 3. Jestem cięcia kilkanaście zakrętów tutaj. Teraz mamy 5, 7, 8, i wracamy do wielkości 3. Jest to bardzo proste do wykonania, ale gdy będziemy żałować tej decyzji, projekt? Kiedy sprawy zaczynają iść bardzo, bardzo źle? Tak. [Niesłyszalne odpowiedź uczeń] Gdy chcesz wrócić i zdobyć pierwszy element, który wtrącił 

Okazuje się tutaj, chociaż stos jest tablica pod maską, tych strukturach zaczęliśmy mówić o są ogólnie znane jako abstrakcyjne struktury danych, zgodnie z którą, jak są one realizowane jest całkowicie poza punkt. Struktura danych jak stos ma dodać wsparcie operacje takie jak push, który popycha tacę na stosie, i pop, która usuwa element ze stosu, i to jest to. Jeśli było ściągnąć kogoś innego kodu, który już wdrożona to coś nazywa się stos, osoba napisałby tylko dwie funkcje dla Ciebie, push i pop, której jedynym celem w życiu byłoby zrobić dokładnie to. Ty czy on czy ona, że ​​program, który realizowany byłby całkowicie jeden zdecydować, jak zaimplementować semantyka popychanie i popping pod maską lub funkcjonalność popychanie i popping. I zrobiłem nieco krótkowzroczne decyzje o poprzez wdrożenie mój stos z tej prostej struktury danych dlaczego? Kiedy robi to struktury danych przerwę? W którym momencie mam zwróci błąd, gdy użytkownik wywołuje push, na przykład? [Student] Jeśli nie ma więcej miejsca. Dokładnie, jeśli nie ma więcej miejsca, jeśli już przekroczyła pojemność, czyli wszystkie czapki, ponieważ sugeruje, że jest to coś w rodzaju globalnej stała. No, to jestem po prostu będzie musiał powiedzieć: "Przepraszam, nie mogę wcisnąć inną wartość na stos ", podobnie jak w Mather. 

W pewnym momencie, że będą uderzać górną część tej małej szafce. Nie ma więcej miejsca lub pojemność w stosie, w tym momencie nie ma jakiś błędów. Mają umieścić element gdzieś indziej, tacy gdzieś indziej, lub gdzie w ogóle. Teraz, w kolejce, możemy wdrożyć go trochę inaczej. Kolejka jest trochę inaczej w tym pod maską, może być realizowane jako tablica, ale dlaczego w tym przypadku, mam propozycję posiada również element głowa, głowę liście przodu liście pierwszy w linii w sklepie Apple, oprócz wielkości? Dlaczego muszę dodatkowy kawałek danych tutaj? Wróćmy na chwilę do tego, co jest liczb jeśli narysowałeś to w następujący sposób. Załóżmy, że to jest teraz kolejka zamiast stosu, różnica jest-podobnie jak Apple Store-queue jest fair. Pierwszy w linii na początku na liście, nr 5, w tym przypadku, on lub ona będzie wpuszczony do sklepu pierwszy. Zróbmy to. Załóżmy, że jest to stan mojej kolejki w tej chwili w czasie, a teraz Apple Store otwiera i pierwszą osobą, numer 5, jest prowadzony do sklepu. Jak zmienić obraz teraz, że mam de-kolejce pierwszej osoby przodu linii? Co to jest? >> [Student] Zmień kolejkę. Zmień głowę, więc 5 znika. W rzeczywistości jest tak, choć-jak najlepiej to zrobić? W rzeczywistości, to jest tak, jakby ten facet znika. Co by numer 7 zrobić w rzeczywistym sklepie? Mieli zrobić duży krok do przodu. 

Ale czego się doceniać, gdy chodzi o tablice i przemieszczania się rzeczy? To trochę marnowanie czasu, prawda? Dlaczego musisz być tak anal, aby mieć pierwszą osobę na początku linii w fizycznie początku ilość pamięci? To jest zupełnie niepotrzebne. Dlaczego? Co może Pamiętam tylko zamiast tego? >> [Niesłyszalne odpowiedź uczeń] Dokładnie, może po prostu pamiętać w tym dodatkowym członkiem danych głowy że teraz szef liście nie jest już 0, co było przed chwilą. Teraz to rzeczywiście numer 1. W ten sposób uzyskać optymalizację lekki. Tylko dlatego, że mam de-kolejce kogoś z linii na początku linii w Apple Store nie znaczy, każdy ma do zmiany, która recall jest liniowym operacji. Mogę zamiast spędzać czas tylko stałą i osiągnięcia, a następnie znacznie szybszą reakcję. Ale cena płacę co zyskać, że dodatkowe działania i nie trzeba zmieniać wszystkich? Tak. >> [Niesłyszalne odpowiedź uczeń] Można dodać więcej ludzi, dobrze, że problem jest prostopadły z tym, że nie jesteśmy przesunięcia wokół ludzi. Jest jeszcze tablica, więc czy możemy przenieść wszystkich lub nie- O, widzę, co masz na myśli, okay. Faktycznie, zgadzam się z tym, co mówisz, w tym, że jest prawie tak, jak gdyby my nigdy teraz zamiar użyć początek tej tablicy już bo jeśli usunąć 5, a następnie usunąć 7. Ale tylko umieścić ludzi na prawo. 

Czuje się jakbym marnowała przestrzeń, i ostatecznie moja kolejka rozpada się zupełnie niczego, więc może po prostu musimy wraparound ludzi, i możemy myśleć o tej tablicy naprawdę jako pewnego rodzaju okrągłej struktury, ale używamy jakiego operatora w C zrobić tego rodzaju nawijania? [Niesłyszalne reakcja studentów] >> operator modulo. Byłoby to trochę irytujące, aby przemyśleć jak to zrobić wraparound, ale możemy to zrobić, i mogliśmy rozpocząć wprowadzanie ludzi w to co było z przodu linii, ale po prostu pamiętam z tej zmiennej głowy który rzeczywisty szef linii rzeczywistości. Co, jeśli zamiast, naszym celem ostatecznym, choć, było szukać numerów, jak my tutaj, na scenie z Anita, ale naprawdę chcemy najlepszym z tych światów? Chcemy więcej wyrafinowania niż tablica pozwala ponieważ chcemy możliwość dynamicznego wzrostu struktury danych. Ale my nie chcemy uciekać się do czegoś, co już zaznaczyliśmy w wykładzie nie optymalne algorytm że liniowej wyszukiwania. Okazuje się, że można, w rzeczywistości, osiągnąć lub przynajmniej blisko stałym czasie, w którym ktoś taki jak Anita, jeśli konfiguruje jej struktury danych nie jest linked list, nie jest stos nie być kolejki, może, w rzeczywistości, pochodzić ze strukturą danych, która pozwala jej patrzeć rzeczy, nawet słowa, nie tylko numery, w jakich będziemy nazywać stałym czasie. 

I rzeczywiście, patrząc z przodu, jedna z tej klasy psets prawie zawsze Wdrożenie sprawdzania pisowni, w którym dajemy ponownie kilka 150.000 angielskich słów i celem jest załadować do pamięci i te szybko być w stanie odpowiedzieć na pytania w formularzu jest to słowo napisane poprawnie? I to naprawdę ssać jeśli miałbyś iterację wszystkich 150.000 słów na to odpowiedzieć. Ale w rzeczywistości, przekonamy się, że możemy to zrobić w bardzo, bardzo szybkie. A to się wiąże wykonującą coś o nazwie hash table, i mimo, że na pierwszy rzut oka ta rzecz zwana hash table będzie niech nam osiągnąć te super szybkie czasy reakcji, Okazuje się, że nie jest w istocie problem. Kiedy przychodzi czas na wdrożenie to coś o nazwie-again, robię to ponownie. Jestem tylko jeden tutaj. Kiedy przychodzi czas na wdrożenie tej rzeczy nazywane hash table, będziemy musieli podjąć decyzję. Jak duży powinien być rzeczywiście ta rzecz? A kiedy zaczniemy numery wstawienie do tej tabeli mieszania, jak będziemy je przechowywać w taki sposób, że możemy je z powrotem tak szybko, jak mamy je w? Ale zobaczymy niebawem, że ta kwestia Kiedy każdy ma urodziny w klasie będzie bardzo związany z tematem. Okazuje się, że w tej sali, mamy kilkaset osób, więc szanse, że dwóch z nas ma takie same urodziny to chyba dość wysokie. Co zrobić, jeśli nie było tylko 40 z nas w tym pokoju? Jakie są szanse na dwie osoby o takim samym urodziny? [Studenci] Ponad 50%. Tak, ponad 50%. W rzeczywistości, nawet przyniósł wykres. Okazuje się, i to jest tak naprawdę zapowiedzią- jeśli jest tylko 58 z nas na tej sali, prawdopodobieństwo 2 z nas o takim samym urodziny jest niezwykle wysoka, prawie 100%, i to będzie powodować całą masę boli dla nas w środę. 

Z powiedział, że niech odroczyć tutaj. Zobaczymy się w środę. [Oklaski] [CS50.TV]