Głośnik 1: Dobra, więc to jest CS50 To jest koniec tygodnia pięć. I pamiętam, że ostatnim razem zaczął patrząc na hodowcy danych Struktury, które rozpoczęły się rozwiązać Problemy, które zaczęły wprowadzać nowe problemy, ale kluczem do tego był typem gwintu, że zacząłem robić od węzła do węzła. Więc to jest oczywiście pojedynczo połączonej listy. I pojedynczo związany, Mam na myśli nie tylko jeden wątku pomiędzy każdym z tych węzłów. Okazuje się, że można zrobić hodowcy takie rzeczy jak podwójnie związane list w którym masz strzałę dzieje się w obu kierunkach, co może pomóc w pewnych korzyści. Ale to rozwiązało problem? Jaki problem miał rozwiązać ten problem? Dlaczego dbamy w poniedziałek? Dlaczego, w teorii, nie dbamy w poniedziałek? Co to robi? 

PUBLICZNOŚCI: Możemy dynamicznie zmienić jego rozmiar. 

Głośnik 1: OK, więc możemy dynamicznie zmienić jego rozmiar. Brawo was obu. Więc można dynamicznie zmieniać rozmiar tego Struktura danych, natomiast tablicy, Przypomnijmy, co musisz wiedzieć priori, jak chcesz dużo miejsca a jeśli potrzebujesz trochę więcej Przestrzeń, jesteś trochę pecha. Musisz stworzyć zupełnie nową tablicę. Musisz się przenieść wszystkie swoje dane z jednego do drugiego, w końcu uwolnić starą tablicę jeśli możesz, a następnie kontynuować. Które po prostu czuje się bardzo kosztowne i bardzo nieskuteczne, a nawet może być. Ale to nie jest dobre. Płacimy cenę, co było jednym z bardziej oczywistych cenach mamy zapłacić za pomocą połączonej listy? 

PUBLICZNOŚCI: Musimy wykorzystać podwójna przestrzeń dla każdego z nich. 1 głośnik: Tak, tak, musimy co najmniej dwukrotnie więcej przestrzeni. W rzeczywistości, zdałem sobie sprawę, ten obraz na nawet trochę mylące, ze względu na CS50 IDE w wielu nowoczesnych komputery, wskaźnik lub adres Nie ma w istocie cztery bajty. Jest to bardzo często są dni osiem bajtów, które Oznacza dno najbardziej prostokąty tam w rzeczywistości to rodzaj dwa razy duży jak co ja wyciągnąć, co oznacza, że ​​używasz trzy razy dużo miejsca, jak możemy mieć inaczej. Obecnie w tym samym czasie, jesteśmy jeszcze mówić bajtów, prawda? My nie musi mówić MB lub GB, chyba tych danych struktur uzyskać duże. 

I tak dzisiaj zaczynamy rozważać jak możemy zbadać dane bardziej efektywne, jeśli w Fakt dane robi się coraz większy. Ale spróbujmy canonicalize Pierwsze operacje że można to zrobić na nich rodzaje struktur danych. Więc coś jak powiązane Lista ogólnie popiera operacji jak usuwanie, włóż i wyszukiwania. I co mam na myśli? To tylko oznacza, że ​​zwykle, jeśli ludzie są przy użyciu połączonej listy, oni lub ktoś wdrożył funkcje, takie jak usuwanie, wstawianie, i wyszukiwania, dzięki czemu można rzeczywiście coś zrobić użyteczne struktury danych. Więc rzućmy okiem w jaki sposób możemy wdrożyć niektóre kodują listy połączonej w sposób następujący. 

Więc to tylko niektóre kod C, nawet kompletny program że bardzo szybko bita. To nie jest online w dystrybucji Kod, ponieważ nie będzie właściwie prowadzony. Zauważmy jednak, mam po prostu o komentarz powiedział: kropka kropka kropka, jest coś tam, kropka kropka kropka, coś tam. I niech to wystarczy spojrzeć na co soczyste części są. Więc na linii trzech, Przypomnijmy, że to jest teraz Zaproponowaliśmy deklarując węzeł ostatni razem z tych prostokątnych przedmiotów. Ma int, że zadzwonimy N, ale możemy nazwać to coś, a następnie gwiazdą węzeł struktura zwana dalej. I żeby była jasność, że druga linii, w wierszu szóstym, co to jest? Co on robi dla nas? Bo to na pewno wygląda bardziej tajemnicze, niż naszych zwykłych zmiennych. 

PUBLICZNOŚCI: To sprawia, że ​​przejście na jednego. 

Głośnik 1: To sprawia, że ​​przejście na jednego. A dokładniej, będzie przechowywać adres węzła, że ​​to znaczy być semantycznie obok niego, prawda? Więc to nie będzie musi przenieść wszystko. To po prostu będzie przechowywania wartości, która jest będzie adres pewnego innego węzła, i dlatego mamy powiedział struct gwiazda węzeł, gwiazda oznaczająca wskaźnik lub adres. OK, więc teraz, jeśli założymy, że mamy to N dla nas dostępne, i niech Zakładam, że ktoś inny ma włożona cała masa liczb całkowitych w połączonej listy. I że związane lista jest wskazywanego przez pewnym momencie zmienna o nazwie lista to przeszedł tu jako parametr, jak mam go o linię 14 wdrażania wyszukiwanie? Innymi słowy, jeśli jestem realizacji Funkcja, której celem w życiu jest podjęcie int a potem początek połączonej listy, które jest wskaźnikiem do połączonej listy. Podobnie jak pierwszy, który myślę, że David był wolontariuszem w poniedziałek, był wskazując na cała związana lista, to tak, jakby przekazujemy David jako naszego argumentu tutaj. Jak mamy go o przejeżdżające tą listę? Cóż, okazuje się, że nawet jeśli Wskaźniki są stosunkowo nowe teraz do nas, możemy to zrobić stosunkowo wprost. 

Mam zamiar iść do przodu i zadeklarować zmienną tymczasową, że umownie jest po prostu będzie być nazywany wskaźnikiem lub PTR, ale można je nazwać jak chcesz. I mam zamiar zainicjować że na początku listy. Tak więc można trochę pomyśleć o tym jak mnie nauczyciela na drugi dzień, rodzaj wskazując na kogoś wśród naszych ludzi jako wolontariuszy. Więc jestem tymczasową zmienną, która jest po prostu wskazując na to samo że nasz przypadkowo nazwany Wolontariusz Dawid również wskazanie. Teraz, gdy wskaźnik jest nie jest pusta, ponieważ odzyskanie że null jest jakaś specjalna wartość sentinel rozgranicza koniec listy tak, a ja nie jestem wskazując na ziemi jak nasz ostatni wolontariusz było, idziemy do przodu i wykonaj następujące czynności. Jeśli pointer-- i teraz niby chcą na to, co zrobiliśmy z uczniem structure-- jeśli wskaźnik kropka obok equals-- raczej, jeśli wskaźnik dot N równa wynosi zmienna N, przy czym Argument, że został przekazany, to chcę iść do przodu i powiedzieć return true. Znalazłem numer N wewnątrz od jeden z węzłów w moim połączonej listy. Ale kropka nie Prace w tym kontekście ponieważ wskaźnik, PTR, jest rzeczywiście wskaźnik, adres, faktycznie może cudownie używać wreszcie kawałek składni tego rodzaju marek intuicyjny sens i rzeczywiście użyj strzałek tutaj, co oznacza, przejść od że adres do liczby całkowitej tam w. Więc to jest bardzo podobne w Duch do operatora kropki, ale dlatego, że wskaźnik nie jest wskaźnikiem a nie rzeczywista sama struktura, po prostu użyj strzałki. 

Tak więc, jeśli bieżący węzeł I, zmienna tymczasowa, wskazuję na Nie dotyczy to, co chcę zrobić? Cóż, z moich ochotników że mieliśmy tutaj na drugi dzień, jeśli mój pierwszy ludzki nie jest tym, że chcą, a może drugi ludzki nie jest jeden chcę, a trzeci, ja trzeba zachować fizycznie ruchu. Podobnie jak w jaki sposób krok po kroku listy? Kiedy mieliśmy tablicę, ciebie po prostu tak jak ja plus plus. Jednak w tym przypadku, wystarczy to wskaźnik, dostaje, wskaźnik obok. Innymi słowy, obok pola jest jak wszyscy opuścili ręce że nasi ochotnicy w poniedziałek stosował wskazać na inny węzeł. To były ich najbliższych sąsiadów. 

Więc jeśli chcę przejść przez liście, Nie mogę po prostu zrobić ja plus oraz więcej, Zamiast tego mają do powiedzenia I, wskaźnik, będzie równa co następne pole jest następny obszar, tym następne pole jest po tych wszystkich lewej ręce że mieliśmy na scenie, wskazując niektórych kolejnych wartości. A jeśli się przez że cała iteracji, i wreszcie, uderzę null, nie mając Znaleziono N jeszcze, po prostu return false. Więc jeszcze raz, wszystko, co tu robimy, jak na zdjęciu przed chwilą, zaczyna od wskazując na początku listy zapewne. A następnie sprawdzić, czy wartość Szukam równa dziewiątej? Jeśli tak, to powrót prawdziwe i skończę. Jeśli nie, mogę zaktualizować moją rękę, AKA wskaźnik, punkt na miejscu następnego strzały, a to miejsce następnego strzały, i następne. Jestem po prostu spaceru po tej tablicy. 

Więc jeszcze raz, kogo to obchodzi? Podobnie jak to, co jest tym składnikiem dla? Cóż, pamiętam, że wprowadziliśmy pojęcie stosie, które Jest to abstrakcyjny typ danych, o ile jest to nie C rzecz, to nie jest rzecz, CS50, jest to abstrakcyjny pomysł, idea układanie rzeczy na jeden na drugim który może być realizowany bukiety różne sposoby. I jeden sposób zaproponowaliśmy był z tablica, lub z połączonej listy. I okazuje się, że kanonicznie, A Stos obsługuje co najmniej dwie operacje. I słowa Buzz są Push, aby wcisnąć coś na stos, jak nowy tacy w jadalnia, lub pop, co oznacza usunięcie najwyższy taca ze stosu w restauracji hol, a potem być może niektóre inne operacje, jak również. Więc jak możemy zdefiniować strukturę że jesteśmy teraz dzwoniąc stos? 

Cóż, wszyscy mamy do wymaganej Składnia do naszej dyspozycji w C. mówię, daj mi definicję typu struct wewnątrz stosu, Mam zamiar powiedzieć, jest tablicą, znaczny cała masa liczb i wielkości. Więc innymi słowy, jeśli chcę zaimplementować to w kodzie, pozwól mi iść i po prostu rodzaj narysuj, co to mówi. Tak to jest, mówiąc: daj mi struktura, która ma tablicę, a ja nie wiem, co pojemność jest, to widocznie niektórzy stała Mam zdefiniowane w innym miejscu, i to jest w porządku. Ale załóżmy, że to tylko jedna, dwa, trzy, cztery, pięć. Więc pojemność wynosi 5. Ten element wewnątrz mojego Struktura będzie nazwany numery. I wtedy potrzebny inne zmienne najwidoczniej Rozmiar że początkowo nazywany idę zastrzec, jest ustawiany na zero. Jeśli nie ma nic w stos, rozmiar wynosi zero, i to wartości śmieci w liczbach. Nie mam pojęcia, co tam jeszcze. 

Więc jeśli chcę naciskać coś na stos, Przypuśćmy, że funkcja push zadzwonić, a Mówię wcisnąć 50, jak liczba 50, gdzie proponujesz Rysuję go w tej tablicy? Istnieje pięć różnych możliwych odpowiedzi. Gdzie chcesz wcisnąć numer 50? Jeśli celem tutaj znowu, nazywamy Funkcja Push, przechodzi w kłótnię 50, gdzie mogę umieścić go? Pięć possible-- 20% szans zgadywać poprawnie. Tak? 

PUBLICZNOŚCI: Daleko w prawo. 

Głośnik 1: Daleko w prawo. Obecnie istnieje 25% szans zgadywać poprawnie. Tak, że faktycznie będzie. Zgodnie z konwencją, powiem z tablicą, będzie na ogół zaczynają się w lewo, ale z pewnością mogą rozpoczyna się na prawo. Więc spoiler tutaj byłoby jestem prawdopodobnie będzie zwrócić go po lewej stronie, tak jak w normalnej tablicy gdzie I zacząć chodzić lewej do prawej. Ale czy można odwrócić arytmetyka, w porządku. To nie tylko konwencjonalne. OK, muszę zrobić jeden więcej Zmiana chociaż. Teraz kiedy pchnął coś na stosie, co dalej? 

Dobra, muszę zwiększyć rozmiar. Więc pozwól mi iść dalej i po prostu aktualizuje, która była zero. I zamiast teraz, zamierzam umieścić w wartości jednego. A teraz załóżmy, wciskam innym Numer na stosie, jak 51. Cóż, muszę zrobić jeszcze jeden Zmiana, która jest do wielkości dwóch. I wtedy przypuszczać, wciskam jeden więcej Numer na stosie, jak 61, teraz muszę zaktualizować rozmiar jeden czas i uzyskać wartość 3 jako wielkości. A teraz załóżmy, nazywam pop. Teraz pop, zgodnie z konwencją, nie bierze argument. W stos, cała punkt metafory tacy jest to, że nie masz dyskrecję przejść się, że tacy, wszystko może zrobić jest pop najwyższą jednego z stos, tylko dlatego. To co robi to struktura danych. 

Więc w tej logiki, jeśli powiedzieć, pop, co wypada? Więc 61. Więc co tak naprawdę jest komputer zamiar zrobić w pamięci? Co mój kod trzeba zrobić? Co byś zaproponować zmieniamy się na ekranie? Co należy zmienić? Przepraszam? Więc pozbyć 61. Mogę więc na pewno to zrobić. I mogę się pozbyć 61. A to co innego Zmiana musi się zdarzyć? Rozmiar prawdopodobnie ma wrócić do dwóch. I tak to jest w porządku. Ale zaraz, wielkość przed chwilą było trzech. Zróbmy szybki test dla pewności. Skąd wiemy, że chciał się pozbyć z 61? Ponieważ jesteśmy popping. I tak mam ten drugi rozmiar własności. 

Chwileczkę, jestem myśli z powrotem do tygodnia dwóch kiedy zaczął mówić o tablice, gdzie było to miejsce zerowe, jest to położenie pierwsze, jest to położenie dwa, to jest położenie trzy, cztery, wygląda na to, związek między wielkością i element, który chcę usunąć z tablicy wydaje się być tylko co? Rozmiar minus jeden. I tak to jest, jak się ludzi wiemy, 61 jest na pierwszym miejscu. Jak komputer będzie wiedział? Gdy kod, gdzie prawdopodobnie chcesz zrobić jeden rozmiar minus, ogółem trzy minus jeden jest dwa, a Oznacza chcemy się pozbyć 61. I wtedy możemy rzeczywiście aktualizacji rozmiar tak, że wielkość teraz idzie od trzech do zaledwie dwóch. I po prostu być pedantyczny, zamierzam zaproponować, że skończę, prawda? Ty zaproponował intuicyjnie prawidłowo powinno się pozbyć 61. Ale nie mam rodzaj rodzaj pozbyć 61? Mam skutecznie zapomniał że faktycznie istnieje. I wracam do PSET4, jeśli czytałeś artykuł o kryminalistyce, PDF że mieliśmy wy czytać, lub odczyta ten tydzień dla PSET4. Przypomnijmy, że to jest rzeczywiście germane do cała idea śledczej. Jaki komputer na ogół nie jest to po prostu zapomina, gdzie coś jest, ale nie iść i jak spróbować zarysować go lub nadpisanie te bity z zer i jedynek lub jakiś inny losowy wzór chyba że samemu to zrobić świadomie. Więc twoja intuicja była Dobra, pozbyć 61. Ale w rzeczywistości, nie musimy się martwić. Musimy tylko pamiętać, że to nie poprzez zmianę rozmiaru. 

Teraz jest problem z tego stosu. Gdybym przeć rzeczy na stosie, co jest oczywiście będzie się działo W zaledwie kilka czasie chwile? Jedziemy do zabrakło miejsca. A co mamy zrobić? Jesteśmy trochę pijany. Ta implementacja nie pozwala nam zmienić rozmiar tablicy, ponieważ za pomocą składnia, jeśli Ciebie wracam na tydzień dwa, kiedy już zadeklarował wielkość tablicy, nie widzieliśmy jeszcze, gdzie mechanizm można zmienić rozmiar tablicy. I rzeczywiście C nie posiada takiej funkcji. Jeśli powiesz mi dać pięć Nths, nazywają ich numery, to wszystko masz zamiar zdobyć. Więc teraz zrobić od poniedziałku, mają zdolność do wyrażania rozwiązanie choć, po prostu trzeba podkręcić Definicja naszego stosu aby nie być pewne zakodowane tablica, ale po prostu zapisać adres. 

Teraz, dlaczego to jest? Teraz po prostu musimy być wygodne, fakt, że kiedy mój program działa, Jestem prawdopodobnie będzie trzeba zapytać człowieka, ile liczb chcesz przechowywać? Więc wejście musi skądś pochodzić. Ale gdy wiem, że Numer, to mogę po prostu wykorzystać to, co funkcjonuje dać mi fragment pamięci? Można używać malloc. I mogę powiedzieć dowolną liczbę bajty Chcę z powrotem do tych Nths. I wszystko, co mam do przechowywania w liczbach Zmienna tutaj wewnątrz tej struktury powinno być to, co? Co faktycznie idzie do Liczby w tym scenariuszu? Tak, wskaźnik do pierwszego bajt tym fragmencie pamięci, a bardziej konkretnie, adres pierwszego z tych bajtów. Nie ma znaczenia, czy jest to jeden bajtów lub miliard bajtów, Po prostu muszę się martwić o pierwszym. Bo to, co gwarantuje malloc i moje gwarancje systemu operacyjnego, jest to, że fragment pamięci I uzyskać, to będzie graniczyć. Nie będzie przerwy. Tak jakbym poprosił o 50 bajtów lub 1000 bajtów, oni wszystko będzie z powrotem do tyłu na plecach. I tak długo, jak pamiętam, jak duży, jak bardzo prosiłem, wszystko co musisz wiedzieć Jest to pierwszy taki adres. 

Więc teraz mamy możliwość w kodzie. Aczkolwiek, to będzie nas więcej czasu, aby napisać to w górę, możemy teraz realokacji, że pamięć po prostu przechowywania inny adres nie jeśli chcemy większy lub nawet mniejszy fragment pamięci. Więc tutaj na kompromis. Teraz mamy dynamizm. Mamy jeszcze contiguousness ja twierdzę. Ponieważ malloc da nam sąsiedni fragment pamięci. Ale to będzie ból w szyja dla nas, programista, faktycznie zakodowanie. To jest po prostu więcej pracy. Musimy kod podobny do tego, co było walić się chwilą. Bardzo wykonalne, ale dodaje złożoności. A więc czas developer, programista Czas jest kolejnym zasobem że może trzeba wydać jakiś czas, aby uzyskać nowe funkcje. I to oczywiście nie ma kolejki. Nie będziemy w to jeden na wiele szczegółów. Ale to jest bardzo podobne w duchu. Może zaimplementować kolejkę, a jego odpowiednie operacje, enqueue lub z kolejki, jak dodać lub usunąć, to tylko hodowcy sposób powiedzenia to, enqueue lub z kolejki, co następuje. Mogę tylko dać sobie struct że znów ma szereg szereg, w że znów ma rozmiar, ale dlaczego teraz trzeba śledzić przodu kolejki? Nie musisz wiedzieć przód mojego stosu. Cóż, gdybym jeszcze raz na queue-- niech po prostu trudne kodować go jako posiadające jak pięć liczby całkowite tutaj potencjalnie. Tak więc jest to zero, jeden, dwa, trzy, cztery. To będzie znowu numerów. A to nazwać rozmiar. 

Dlaczego nie jest wystarczająca mieć tylko rozmiar? Cóż, wcisnąć te same numery. Więc pushed-- I skolejkowany lub pchnął. Teraz będę enqueue 50, a następnie 51, a następnie 61 i kropka kropka kropka. Więc to enqueue. I skolejkowany 50, potem 51, potem 61. A że wygląda identycznie do stosu dotąd poza tym, że trzeba zrobić jedną zmianę. Muszę zaktualizować ten rozmiar, więc idę od zera do jednego do dwóch do trzech obecnie. Jak mogę z kolejki? Co się dzieje z rozkolejkowania? Kto powinien spaść do tej listy pierwszej czy jest to linia w sklepie Apple Store? Więc 50. Więc to trochę trudniejsze, tym razem. Podczas gdy ostatni raz to było super łatwo po prostu zrobić jeden rozmiar minus, I dostać się do końca mojej tablicy skutecznie w którym liczby są, usuwa 61. Ale nie chcę, aby usunąć 61. Chcę wziąć 50, który był tam o 5:00 AM do linii dla Nowy iPhone lub cokolwiek. I tak, aby pozbyć się 50, I Nie można po prostu to zrobić, prawda? Mogę wykreślić 50. Ale tylko, że my nie muszą być tak analny jak drapać się lub ukrywanie danych. Możemy po prostu zapomnieć, gdzie to jest. 

Ale jeśli mogę zmienić rozmiar teraz dwa, jest to wystarczające informacje wiedzieć, co dzieje się w mojej kolejce? Nie całkiem. Podobnie jak mój rozmiar jest dwa, ale skąd kolejka zacząć, zwłaszcza jeśli nadal mam te same liczby w pamięci. 50, 51, 61. Więc trzeba pamiętać teraz, gdy z przodu jest. I tak jak proponuje się nie, będziemy właśnie nazywa N-ty z przodu, których początkowa wartość powinna być co? Zero, tylko początek listy. Ale teraz oprócz odlicza rozmiar, po prostu zwiększyć przód. Teraz tutaj jest inny problem. Więc po I wracamy. Załóżmy, że jest to numer jak 121, 124, a następnie, do cholery, Jestem miejsca. Ale zaraz, ja nie. Więc w tym momencie w historii, przypuszczać, że rozmiar jest jeden, dwa, trzy, cztery, więc przypuszczam, że rozmiar jest cztery, z przodu jest jeden, tak 51 znajduje się z przodu. Chcę umieścić inny numer tutaj, ale, do cholery, mam miejsca. Ale nie jestem, prawda? Gdzie mogę umieścić niektóre Dodatkowym atutem, podobnie jak 171? Tak, mogłem po prostu rodzaj wrócić tam, prawda? A potem przekreślić 50, lub po prostu zastąpienie go 171. A jeśli zastanawiacie się, dlaczego nasze numery, ale tak przypadkowe, Te elementy są zwykle brane komputer Kursy nauki w Harvardzie po CS50. Ale to była dobra optymalizacja, bo teraz nie jestem marnowania miejsca. Mam jeszcze do zapamiętania jak duże to jest to całkowity. To pięć sumie. Bo nie chcę rozpocząć nadpisywanie 51. Więc teraz jestem jeszcze z miejsca, tak że ten sam problem jak poprzednio. Ale można zobaczyć, jak teraz w kodzie, prawdopodobnie napisać trochę więcej Złożoność, aby tak się stało. I rzeczywiście, jakie operator w C prawdopodobnie pozwala magicznie to kołowość zrobić? Tak operator modulo, znak procent. Więc co to za fajne o kolejce, chociaż utrzymać tablice rysunkowe jako tych, takich jak linie proste, jeśli Ciebie rodzaj myśleć o tym, jak zakrzywienie wokół jak koło, a potem po prostu intuicyjnie to niby działa psychicznie Myślę, że trochę bardziej czysto. Nadal będą musiały wdrożyć ten model psychicznego w kodzie. Tak więc nie jest trudno, doprowadzenie do wdrożenia, ale nadal stracić size-- raczej Możliwość zmiany rozmiaru, chyba, że ​​możemy to zrobić. 

Musimy pozbyć tablicy, możemy zastąpić go jednym wskaźnikiem, a następnie gdzieś w moim kodu mam transmisją, co działać, by tworzyć tablica zwane numery? Malloc lub innej podobnej Funkcja, dokładnie. Wszelkie pytania dotyczące stosów lub kolejek. Tak? Dobre pytanie. Co modulo należy użyć tutaj. Tak więc ogólnie, przy użyciu mod, by to zrobić z wielkością z Cała struktura danych. Więc coś w pięciu lub zdolności, jeżeli jest to stała, prawdopodobnie jest zaangażowana. Ale po prostu robi modulo pięć prawdopodobnie nie jest wystarczające bo musimy wiedzieć, jak my owinąć wokół tutaj lub tutaj lub tutaj. Więc jesteś prawdopodobnie również będzie chciał zaangażować rozmiar rzeczy, albo zmienna z przodu, jak również. Więc to jest właśnie to stosunkowo proste wyrażenie arytmetyczne, ale modulo będzie kluczowym składnikiem. 

Tak krótki film, jeśli będzie. Animacja, że ​​niektóre Ludzie na innej uczelni ułożyła, że ​​mamy przystosowane do tej dyskusji. Polega ona Jack nauki fakty na temat kolejek i statystyki. 

FILM: Dawno, dawno temu, był facet o imieniu Jack. Gdy przyszło do nawiązywania przyjaźni, Jack nie miał dryg. Więc Jack poszedł porozmawiać z Najbardziej popularne facet wiedział. Udał się do Lou i zapytał: Co mam zrobić? Lou zobaczył, że jego przyjaciel był bardzo zmartwiony. Cóż, zaczął po prostu wyglądają jak jesteś ubrany. Nie masz żadnych ubrań z innym spojrzeniem? Tak, powiedział Jack. Ja na pewno nie. Przyjdź do mojego domu i Pokażę je do Ciebie. Więc poszedł do Jacka. I Jack pokazał pole Lou gdzie trzymał wszystkie swoje koszule, i jego spodnie i skarpetki. Lou powiedział: Widzę, że masz wszystkie ubrania w stos. Dlaczego nie nosisz niektóre inni raz na jakiś czas? 

Jack powiedział, dobrze, kiedy zdjąć ubrania i skarpetki, I umyć je i umieścić je się w polu. Potem przychodzi następna rano, a nawet ja skaczę. Idę do okna i uzyskać moje ubrania off góry. Lou szybko zorientował się, problem z Jackiem. Trzymał ubrania, płyty CD, i książek w stosie. Kiedy dotarł do coś do czytania lub do noszenia, że on wybrać górną książkę lub bieliznę. Potem, kiedy skończył, on by umieścić go z powrotem. Powrót byłoby to, na szczycie stosu. Wiem, że rozwiązanie, powiedział triumfalny Loud. Musisz nauczyć się uruchomić za pomocą kolejki. Lou wziął ubrania Jacka i powiesił je w szafie. A kiedy opróżnił okno, on po prostu rzucił ją. 

Potem powiedział, teraz Jack, w końcu dzień, umieścić swoje ubrania po lewej stronie kiedy je dalej. Następnie jutro rano, kiedy zobaczyć słońca, dostać ubrania z prawej strony, od końca linii. Czy nie widzisz? powiedział Lou. To będzie tak miło. Będziesz nosić wszystko raz zanim dwa razy nosić coś. A wszystko w kolejkach w swojej szafy i półki, Jack zaczął odczuwać bardzo pewny siebie. Wszystko dzięki Lou i Jego wspaniała kolejka. Głośnik 1: Dobrze, że to urocze. Więc to, co zostało naprawdę dzieje na pod maską teraz? Że mamy wskazówki, że mamy malloc, że mamy możliwość tworzenia kawałki pamięci dla siebie dynamicznie. Więc jest to, że obraz dostrzegł dopiero drugi dzień. Tak naprawdę nie mieszkać na nim, ale ten obraz ma już od spodu kaptur od tygodni. A więc to oznacza, po prostu prostokąt, że mamy wyciągnąć, pamięci komputera. A może komputer lub CS50 ID, ma gigabajt pamięci lub pamięci RAM lub dwa gigabajty lub cztery. To naprawdę nie ma znaczenia. Twój system operacyjny System Windows lub Mac OS lub Linux, zasadniczo umożliwia program myśleć, że ma dostęp do całości pamięci komputera, chociaż może być uruchomiony wiele programów na raz. Tak więc w rzeczywistości, to naprawdę nie działa. Ale to rodzaj iluzji podane do wszystkich programów. Więc jeśli miał dwóch gigabajtów pamięci RAM, to to, w jaki sposób komputer może myśleć. 

Teraz jest przypadkiem, jednym z nich rzeczy, jeden z tych segmentów pamięci, nazywa stos. I rzeczywiście, za każdym razem do tej pory w pisania kodu , że nazywa się funkcji, na przykład głównego. Przypomnijmy, że za każdym razem mam Rysowane pamięci komputera, Zawsze zwrócić rodzaj połowa prostokąta tutaj i nie przeszkadza rozmawiać o tym, co powyżej. Bo gdy głównym nazywa, mam prawo że masz ten skrawek pamięci że idzie tutaj. A jeśli głównym nazywany funkcją jak swap, oraz wymiany idzie tutaj. I okazuje się, że to gdzie jest kończąc. Na coś, co nazywa stos wewnątrz pamięci komputera. Teraz na koniec dnia to jest po prostu adresy. To jak bajt zerowy, bajt jeden bajt 2 mld. Ale jeśli myślisz o tym jak tego prostokątnego obiektu, wszystko robimy na co Czas nazywamy funkcją jest warstw nowy kawałek pamięci. Dajemy tę funkcję kawałek własnej pamięci pracy. 

I przypominam sobie teraz, że to jest ważne. Bo jeśli mamy coś jak zamiana oraz dwie zmienne lokalne, takie jak A i B, możemy zmienić te wartości z jednego i dwóch do jednego, dwóch i przypominania że podczas wymiany zwraca, to tak, jakby ten kawałek pamięci jest po prostu zniknął. W rzeczywistości, to nadal nie forensically. I coś jeszcze faktycznie istnieje. Ale koncepcyjnie, to tak choć to całkowicie zniknęły. I tak głównym nie zna żadnej pracy które zostało zrobione w tej funkcji wymiany, chyba, że ​​jest to rzeczywiście przekazywane w tych argumenty przez wskaźnik lub przez odniesienie. Teraz, podstawowym rozwiązaniem do tego problemu z wymiany przechodzi rzeczy przez adres. Ale okazuje się, też, co jest trwa powyżej tej części prostokąta cały ten czas jest jeszcze nie ma więcej pamięci tam. A kiedy dynamicznie przydzielić pamięci, czy to wewnątrz getString, które robiliśmy dla Ciebie w CS50 biblioteka, lub jeśli faceci malloc zadzwonić i zapytać system operacyjny na fragmencie pamięci, nie pochodzi ze stosu. Pochodzi z innego miejsca w pamięci komputera które nazywa się sterty. I to nie jest inaczej. To jest to samo RAM. To jest ta sama pamięć. To tylko RAM to się tam zamiast tutaj. 

I tak, co to oznacza? Cóż, jeśli komputer ma skończoną ilość pamięci a stos rośnie, więc mówić, a kupa, zgodnie do tej strzałki, rośnie w dół. Innymi słowy, każda Czas zadzwonić malloc, jesteś z nich otrzymuje kawałek pamięć z powyższego to może trochę niżej, potem trochę niższe, za każdym razem dzwonić malloc, kupa, to wykorzystanie, jest rodzaj uprawy, coraz bliżej i bliżej do czego? Stos. Więc czy to wydawać się dobrym pomysłem? Chodzi mi o to, gdzie tak naprawdę nie jest jasne, Co jeszcze można zrobić, jeśli tylko mają ograniczoną wielkość pamięci. Ale to jest na pewno złe. Te dwa strzały są na zasadzie Crash Course dla siebie. 

I okazuje się, że facet, ludzie, którzy są szczególnie dobre z programowaniem, i próbuje włamać się do komputerów, może wykorzystać tę rzeczywistość. W rzeczywistości, rozważmy mały fragment. Więc to jest przykład można przeczytać o bardziej szczegółowo na Wikipedii. Będziemy wskazywać na Państwa Artykuł jeśli ciekawi. Ale jest na ogół atak znany jako przepełnienie bufora, które istnieje tak długo, jak ludzie miały możliwość manipulowania pamięci komputera, zwłaszcza w C Więc jest to bardzo arbitralne programu, ale niech ją przeczytać od dołu do góry. Główna pod gwiazdkowy argC char argv. Więc jest to program, który ma Argumenty wiersza poleceń. A wszystko podobno jest głównym ma połączenia funkcja, nazywamy to F dla uproszczenia. I przechodzi w co? Argv jednego. Tak przechodzi się do F, co Słowo to, że użytkownik wpisze w wierszu od wyprodukowania Nazwa programu w ogóle. Więc tak jak Cezara lub Vigenère które Może pamiętacie robi argv. 

Więc co to jest F? F odbywa się w ciąg jako jedyny argument, AKA gwiazdą char, sam rzeczą, jako ciąg znaków. I to się nazywa arbitralnie Pasek w tym przykładzie. A potem char c 12, tylko w laika, co jest char c uchwyt 12 robi dla nas? Jak to zrobić? Przydzielania pamięci, w szczególności 12 bajtów do 12 znaków. Dokładnie. A następnie w ostatniej linii, wymieszać i kopiowania, chyba pan nie widział. To jest kopia ciąg Funkcja, której celem w życiu jest skopiować drugi argument w pierwszym argumentem, lecz tylko do Pewna liczba bajtów. Więc trzeci argument mówi, ile bajtów należy skopiować? Długość paska, co użytkownik wpisał w. Oraz treść bar, ten ciąg, są kopiowane do pamięci wskazał na C 

Tak więc wydaje się głupie, i ona jest. Jest to wymyślony przykład, ale to przedstawiciel klasy wektorów ataku, sposób atakuje program. Wszystko jest w porządku i dobrze, jeśli użytkownik typy w słowie, które jest 11 znaków lub mniej, plus backslash zero. Co zrobić, jeśli użytkownik wpisze więcej niż 11 lub 12 lub 20 lub 50 znaków? Co znajduje się ten program zrobi? Potencjalnie seg winy. To się dzieje ślepo kopiować wszystko w barze się na jego długości, co jest dosłownie wszystko w barze, na adres wskazał na C, ale C dopiero zapobiegawczo podaje się 12 bajtów. Ale nie ma dodatkowego wyboru. Jeśli warunki nie ma. Nie ma tu kontroli błędów. 

A więc to, co ten program jest zamiar zrobić, to po prostu ślepo skopiować jedno do drugiego. I tak, jeśli zwracamy tym jako obraz, oto tylko skrawek przestrzeni pamięci. Tak więc zauważyć na dole, że mają zmienną lokalną bar. Więc tego wskaźnika, który będzie store-- a tym lokalnym argumentu, który jest będzie przechowywać pasek ciąg. I wtedy zauważył tylko nad nim w stosie bo za każdym razem prosić dla pamięci na stosie, to idzie trochę ponad to obrazowo, Ogłoszenie, że mamy 12 bajtów tam. W lewym górnym jeden jest uchwyt C zero i prawy dolny uchwyt jest C 11. To tylko jak komputery zamiar położyć go na zewnątrz. Więc po prostu intuicyjnie, jeśli pasek ma więcej niż 12 znaków w sumie, w tym odwrotny ukośnik zero, gdzie jest 12 lub wspornik C12 zamiar iść? Albo raczej, gdzie jest 12 znaków lub 13 znaków, setna charakter będzie do końca się na zdjęciu? Powyżej lub poniżej? 

Racja, bo choć sam stos rośnie w górę, kiedy już umieścić rzeczy w to, że ze względów konstrukcyjnych, umieszcza pamięci z góry do dołu. Więc jeśli masz więcej niż 12 bajtów, masz zamiar rozpocząć nadpisywanie bar. Teraz, że to błąd, ale to naprawdę nie jest wielka sprawa. Ale to jest wielka sprawa, bo nie ma więcej rzeczy dzieje się w pamięci. Więc oto jak może umieścić komentarzy, być jasne. Jeśli witam mam wpisane w wierszu. Backslash zerowa H-E-L-L-O, kończy się w ciągu te 12 bajtów, a my jesteśmy bardzo bezpieczne. Wszystko dobrze. Ale jeśli coś typu dłużej, potencjalnie to zamiar wkraść się Spacja. Ale co gorsza, okazuje z całym tym czasie, chociaż nigdy nie mówił o to, że stos jest używany do innych rzeczy. To nie tylko zmienne lokalne. 

C jest językiem bardzo niski poziom. I jakby potajemnie wykorzystuje stos również pamiętać, gdy Funkcja jest wywoływana, co adres jest poprzedniej funkcji więc może wrócić do tej funkcji. Kiedy więc zamienić główne połączenia między rzeczy odkładana na stos nie są po prostu zamienia zmienne lokalne, lub jego argumenty, także potajemnie pchnął na stosie, jak pokazano przez plasterek tutaj jest adres główny fizycznie w pamięci komputera, tak, że podczas wymiany odbywa komputer wie, że trzeba wrócić do głównego i zakończenia wykonywania funkcji main. Więc teraz jest to niebezpieczne, bo jeśli użytkownik wpisze w dobrze ponad komentarzy, takie, że wejście użytkownika clobbers lub nadpisuje ten czerwony punkt, logicznie, jeśli w komputerze po prostu będzie ślepo zakładać, że bajtów, że Red plaster są adres, na który należy zwrócić, co, jeśli przeciwnik jest na tyle sprytny, lub szczęście, aby umieścić sekwencję bajtów tam, że wygląda jak adres, ale jest to adres z kodem że on lub ona chce komputer wykonać zamiast Głównym? 

Innymi słowy, jeśli to, co użytkownik wpisując w wierszu, nie tylko coś nieszkodliwe jak cześć, ale w rzeczywistości jest to odpowiednik kodu usunąć wszystkie pliki tego użytkownika? Lub napisz do mnie swoje hasło? Lub rozpocząć rejestrowanie ich klawiszy, prawda? Jest na to sposób, niech przewidują dziś że mogą wpisywać nie tylko komentarzy świecie lub ich nazwa, mogli w zasadzie przechodzą w kodzie, zer i z nich, że komputer błędy zarówno dla kodu i adresem. Więc choć nieco abstrakcyjnie, jeśli użytkownik wpisze w tyle kodu kontradyktoryjności że będziemy tu generalizować A. jest atak lub przeciwnicy. Więc po prostu złe rzeczy. Nie dbamy o numerów lub zera lub te, dzisiaj, tak że w końcu nadpisanie, że czerwony punkt, zauważyć, że kolejność bajtów. O 835 C zera osiem zero. A teraz, jak artykule Wikipedii tutaj zaproponowała, jeśli teraz zacząć oznaczania bajtów komputera pamięci, co w artykule Wikipedia jest proponującą jest, że to, co jeśli adres tej górnym lewym bajt jest 80 C 0 3508. 

Innymi słowy, jeśli zły to tyle sprytny ze swoim kodem faktycznie umieścić numer tutaj odpowiada adresowi kodu on wstrzykiwany do komputera, Można oszukać komputer do robienia czegokolwiek. Usuwanie plików, wysyłanie e-maili rzeczy, wąchania ruchu, dosłownie wszystko może być wtryskiwane do komputera. I tak przepełnienie bufora Atak w swej istocie jest po prostu głupi, głupi Nadrzędnym tablicy, że nie mają sprawdzać jego granice. I to jest to, co jest bardzo niebezpieczne i jednocześnie potężny w C jest to, że naprawdę mamy dostęp do każdego miejsca w pamięci. To do nas, programistów, którzy piszą oryginalny kod aby sprawdzić długość cerować którejkolwiek macierze, że jesteśmy manipulacji. Więc być jasne, co to naprawić? Jeśli cofnąć się do tego Kod, że nie powinienem tak zmiana długości paska, co jeszcze powinien być sprawdzanie? Co mam robić, aby jeszcze uniknąć tego ataku w całości? Nie chcę, aby ślepo powiedzieć że należy skopiować tyle bajtów jak długość pręta. Chcę powiedzieć, skopiować, jak jak wiele bajtów są w barze do przydzielona pamięci lub 12 maksymalnie. Więc muszę jakąś jeśli warunek że nie sprawdzić długość paska, ale jeśli przekracza 12, mamy kod po prostu dysk 12 w maksymalnej możliwej odległości. W przeciwnym razie, tak zwany bufor atak przepełnienia może się zdarzyć. W dolnej części tych preparatów, Jeśli jesteś ciekaw, aby przeczytać więcej jest rzeczywisty oryginalny artykuł jeśli chcesz spojrzeć. 

Ale teraz, wśród ceny wypłacane tutaj był nieefektywność. Tak to było szybkie niski poziom spojrzenie na to, co Teraz mogą pojawić się problemy, które mają dostęp do pamięci komputera. Ale inny problem, jaki już natknął się w poniedziałek właśnie nieefektywność z połączonej listy. Jesteśmy z powrotem do czasu linearnego. Nie mamy już ciągłą tablicę. Nie mamy swobodny dostęp. Nie możemy używać notacji nawiasu kwadratowego. Dosłownie użyć pętli while jak ten napisałem przed chwilą. Ale w poniedziałek, że twierdził, że możemy skradać się z powrotem do królestwa efektywności osiągnięcia coś, co jest Może logarytmiczna, lub najlepiej jeszcze, może nawet coś, co jest tak zwana stała czasowa. Więc jak możemy to zrobić za pomocą tych nowych narzędzia, te adresy, te wskaźniki, i gwintowania rzeczy sami? Cóż, przypuszczam, że tutaj są to banda liczb, które chcemy przechowywać w Struktura danych i wyszukiwarka sprawnie. Możemy absolutnie przewinąć do tygodnia dwa, wrzuć je do tablicy, i szukać ich za pomocą wyszukiwania binarnego. Dziel i rządź. I faktycznie napisał binarne wyszukiwania w PSET3, gdzie realizowany program find. Ale wiesz co. Jest to trochę bardziej sprytny sposób to zrobić. To trochę więcej wyrafinowany i być może pozwala nam zrozumieć, dlaczego binarny wyszukiwania jest o wiele szybciej. Najpierw wprowadzenie pojęcie drzewa. Które chociaż w drzewa rzeczywistości rodzaj rosną jak to w świecie komputera nauka to rodzaj rosną w dół jak drzewo genealogiczne, gdzie trzeba Twoi dziadkowie lub pradziadkowie lub cokolwiek na górze, patriarchy i macierz rodziny, tylko jeden tak zwany korzeń, węzeł, poniżej które są jego dzieci, poniżej, które są jego dzieci, lub jego potomkowie bardziej ogólnie. I każdy zawieszony spód rodziny drzewo, oprócz bycia Najmłodszy w rodzinie, Można też po prostu być ogólnie nazywa liście drzewa. 

Więc to jest tylko kilka słów i definicji coś nazywa się drzewo w komputerze nauka, podobnie jak drzewa. Ale jest bardziej wyszukane wcieleń drzew, z których jeden Wyszukiwarka nazywamy drzewo binarne. I można rodzaju Tease od siebie, co robi ta rzecz. Cóż, to binarny, w jakim sensie? Skąd pochodzą z binarny tutaj? Przepraszam? To nie jest tak dużo lub. Jest to bardziej, że każdy z węzłów nie ma więcej niż dwoje dzieci, jak widzimy tutaj. W ogóle, tree-- i Twoi rodzice i dziadkowie może mieć tyle dzieci, lub wnuki, jak rzeczywiście chcą, i tak na przykład nie mamy trzy dzieci, poza tym węźle prawej stronie, ale w binarnym drzewie, węzeł ma zero, jeden lub dwoje dzieci maksymalnie. A to ładny obiekt, bo jeśli jest ograniczona przez dwa, będziemy w stanie trochę bazę dziennika dwóch Akcja dzieje się tutaj, w końcu. Mamy więc coś logarytmiczną. Ale o tym za chwilę. Szukaj drzewo oznacza, że ​​liczby te są ustawione tak, aby lewy dziecka jest większa od korzenia. Dziecko i jego prawo jest większy niż root. Innymi słowy, jeśli wziąć którykolwiek z węzły, kręgi na tym zdjęciu, i patrzy na jej lewej stronie dziecka i jego prawo dziecka, pierwszy powinien być mniejszy niż druga powinna być większa. Więc rozsądek sprawdzić 55. To co pozostało dziecka jest 33. To mniej niż. 55, jego prawo dziecka jest 77. Jest większa niż. I to jest rekurencyjna definicja. Możemy sprawdzić każdy z tych węzły i ten sam wzór będzie posiadał. 

Więc co jest miłe w sposób binarne drzewo poszukiwań, jest że jeden, możemy go wdrożyć ze struktury, po prostu lubię to. I mimo, że mamy do rzucania wiele struktur do Państwa, są nieco Intuicyjny teraz z nadzieją. Składnia jest wciąż arcane na pewno, ale zawartość węzła w tym context-- i trzymamy za pomocą węzła słowo, czy jest to prostokąt na ekranie lub okręgu to tylko niektóre rodzajowe kontenera, W tym przypadku drewna, takiego jak ten widzieliśmy, musimy liczbę całkowitą w każdym z węzłów i wtedy muszę dwa wskaźniki wskazujące do lewego i prawego dziecka dziecka odpowiednio. Tak to jest, jak może wdrożenie, że do struktury. I jak można wdrożyć go w kodzie? Cóż, weźmy szybkie spójrz na ten mały przykład. To nie jest funkcjonalny, ale mam kopiować i wklejać tej struktury. A jeśli moja funkcja binarny wyszukiwarka drzewo nazywane jest wyszukiwarka, i to ma dwa argumenty, liczba całkowita N i wskaźnik do węzła, więc wskaźnik na drzewie lub wskaźnik do korzenia drzewa, jak mogę iść o poszukiwaniu N? Cóż, po pierwsze, dlatego, że jestem czynienia ze wskaźnikami, Mam zamiar zrobić test dla pewności. Jeśli równi drzewo równa null, to N w tym drzewie, czy nie na tym drzewie? To nie może być, prawda? Jeśli jestem obok null, tam nic nie ma. Mógłbym równie dobrze ślepo powiedzieć return false. Jeśli dasz mi nic, ja na pewno nie może znaleźć żadnego numeru N. Więc co jeszcze mogę Sprawdź teraz? Mam zamiar powiedzieć, jak inni, jeśli N jest mniej niż to, co jest z węzła drzewa że byłem podał wartość N. Innymi słowy, liczba mi szuka, N jest mniejsza niż węzeł że patrzę. Oraz węzeł szukam co nazywa się drzewo, i pamiętam z poprzedniego przykładu aby dostać się w wartości wskaźnika, Używam notacji strzałki. Tak więc, gdy liczba N jest mniejsza niż drzewa strzałką N, chcę koncepcyjnie iść w lewo. W jaki sposób mogę wyrazić poszukiwań w lewo? Żeby było jasne, czy jest to obraz, o którym mowa, a ja już minęło, że najwyższy strzałka skierowana w dół, że jest. To moje drzewo wskaźnik. Jestem wskazując na korzenia drzewa. I szukam powiedzmy, na numer 44, arbitralnie. Jest 44 mniejsza niż lub większa niż 55 oczywiście? Więc to jest mniej niż. A więc to, czy dotyczy warunek. Tak koncepcyjnie, co chcę szukaj w przyszłym, jeśli szukam 44? Tak? 

Dokładnie, ja chcę szukaj lewy dziecko, lub w lewo poddrzewo tego obrazu. I rzeczywiście, niech mnie przez obraz tutaj na chwilę, ponieważ Nie mogę drapać to. Jeśli zacznę tutaj na 55, oraz Wiem, że wartość 44 Szukam jest lewica, jest to swego rodzaju jakby rozrywanie książki telefonicznej w pół lub łzawienie drzewo na pół. I nie muszą już dbać o Cały pół drzewa. A jednak, co ciekawe w kategoriach struktury, to coś tu, że zaczyna się od 33, która sama w sobie Wyszukiwarka jest drzewo binarne. I powiedział, że słowo rekurencyjne wcześniej, bo W rzeczywistości jest to struktura danych z definicji jest rekurencyjne. Możesz mieć drzewa, które jest w tym duży, ale każdy z jej dzieci reprezentuje drzewo tylko trochę mniejszy. Zamiast niego jest dziadek lub babcia, teraz to tylko mama or-- nie mogę nie say-- mama lub tata, to byłoby dziwne. Zamiast tego dwoje dzieci będzie jak brat i rodzeństwo. Nowa generacja drzewa genealogicznego. Ale strukturalnie, że to ten sam pomysł. I okazuje się, mam funkcji z których można przeszukiwać przeszukiwanie binarne drzewo. Nazywana jest wyszukiwarka. Szukam N w drzewo strzałka w lewo inaczej, jeśli n jest większe od wartości że jestem obecnie. 55 w historii przed chwilą. Mam funkcję o nazwie wyszukiwarka, że ​​mogę po prostu przekazać N to i rekurencyjnie wyszukiwania sub-tree i po prostu powrót cokolwiek to odpowiedź. Jeszcze mam jakiś ostateczny wariant podstawowy tutaj. 

Jaki jest ostateczny przypadek? Drzewo jest albo wartość null. Wartość ja albo szukasz jest mniejsze niż lub większa niż lub jej równa. I mogę powiedzieć, równa równe, ale logicznie to równowartość tylko, że jeszcze tutaj. Tak więc prawdą jest, jak coś znajdę. Więc mam nadzieję, że jest to jeszcze bardziej atrakcyjne przykładem niż funkcja głupiego sigma zrobiliśmy kilka wykładów z powrotem, gdzie to było tak łatwe w użyciu pętli liczyć się wszystkie numery z jednego N. tu ze struktury danych które samo w sobie jest rekurencyjnie zdefiniowane i rekurencyjnie rysowane, teraz my mają zdolność do wyrażania siebie w kodzie, który sam w sobie jest rekurencyjny. Więc to jest dokładnie ten sam kod tutaj. 

Więc jakie inne problemy możemy rozwiązać? Tak szybkie krok od drzew na chwilę. Oto, mówi, niemiecką flagę. I jest wyraźnie wzór do tej flagi. I jest mnóstwo flagi w świecie, są proste, ponieważ w warunkach ich kolorów i wzorów. Jednak przypuszczać, że jest to zapisane jako GIF lub JPEG lub bitmapy, lub ping, dowolny format pliku graficznego z których znasz, niektóre z których jesteśmy gry z w PSET4. Nie wydaje się opłaca przechowywać czarny piksel, czarny piksel, czarny piksel, kropka, kropka, kropka, cała masa czarne piksele na pierwszy scanline, lub wiersza, to cała masa takie same, wówczas cała masa to samo, a potem cała masa czerwonych pikseli, czerwonych pikseli, czerwony pikseli, a następnie całość kilka żółtych pikseli, żółty, prawda? 

Jest takie nieefektywność tutaj. Jak byś intuicyjnie skompresować niemiecką flagą jeśli wdrożenie go jako plik? Jak to, co my informacje nie mogą przeszkadza przechowywania na dysku, w celu aby zmniejszyć rozmiar pliku z naszego jak megabajt do kilobajtów, coś mniejsze? Na czym polega zwolnienie tutaj, aby być jasne? Co można zrobić? Tak? Dokładnie. Dlaczego nie, a nie pamiętam kolor każdego piksela absolutnie znakomite jak robisz w PSET4 z formatem plików graficznych, dlaczego nie można po prostu reprezentują skrajnej lewej kolumnie pikseli, na przykład kilka czarnych pikseli, banda czerwony, i kilka żółty, a potem po prostu w jakiś sposób zakodowania Pomysł powtórzyć ten 100 razy lub powtórzyć to 1000 razy? Gdzie 100 lub 1000 jest po prostu liczbą całkowitą, więc Ciebie może uciec z tylko jednym numerem zamiast setek lub tysięcy dodatkowych pikseli. I rzeczywiście, to w jaki sposób może skompresować niemiecką flagą. I Teraz co z francuską banderą? I trochę jakiś ćwiczenia umysłowe, które flagi mogą być kompresowane bardziej na dysku? Flaga niemiecki lub francuski flaga, jeśli weźmiemy to podejście? Niemiecka flaga, bo nie ma więcej pozioma redundancji. I projektowania, wiele graficznym pliku formaty rzeczywiście działają linie jako skanowania poziomo. Mogą one pracować pionowo, tak ludzkość lat temu zdecydowali, że będziesz ogólnie myślę o rzeczach rzędu po rzędzie zamiast kolumna po kolumnie. Więc rzeczywiście, jeśli były patrzeć na pliku wielkość niemiecką flagą i francusku flaga, tak długo, jak rozdzielczość to tym samym, o takiej samej szerokości i wysokość, ten tutaj będzie większy, bo Ciebie trzeba powtarzać sobie trzy razy. Musisz określić, niebieski, powtórki sam, biały, powtarzam się, czerwony, powtarzaj się. Nie można po prostu pójść na całość droga w prawo. I tak na marginesie, aby usunąć kompresję Jest wszędzie, o ile są one cztery ramki ze video-- ci może przypomnieć, że film lub wideo jest na ogół jak 29 lub 30 klatek na sekundę. To jak książeczki odwrotną, gdzie po prostu zobaczyć obraz, wizerunek, wizerunek, obraz, Obraz po prostu super szybko, więc wygląda na to, aktorzy na ekranie poruszają. Oto trzmieli na góry bukietem kwiatów. I choć może to być rodzaj trudno zobaczyć na pierwszy rzut oka, jedyne, co porusza się w ten film jest pszczoła. 

Co to jest głupi temat przechowywania sygnał wideo? Jest to swego rodzaju odpadów do sklepu wideo w czterech niemal identycznych obrazów różnią się jedynie w zakresie, gdzie pszczoły jest. Możesz wyrzucić najbardziej tej informacji i tylko pamiętać, na przykład pierwszy i ostatni rama rama, klatki kluczowe, jeśli już słyszał słowa, i po prostu przechowywać w Pszczoła w średnim gdzie jest. A ty nie musisz przechowywać wszystkie różowe, i niebieski, i Wartości zielone, jak również. Więc to jest tylko powiedzieć, że Kompresja jest wszędzie. Jest to technika często używamy lub wziąć za pewnik te dni. 

Ale w jaki sposób skompresować tekst? Jak idziesz na temat kompresji tekstu? Cóż, każda z postaci w ASCII jest jeden bajt lub osiem bitów. A to niby głupie, prawda? Bo prawdopodobnie typu A i E oraz I i O i U wielu częściej niż jak W lub Q lub Z, w zależności od języka, w którym piszesz na pewno. A więc dlaczego używamy osiem bitów na każdy list, w tym co najmniej popularne litery, prawda? Dlaczego nie skorzystać z mniejszej liczby bitów dla Super popularne litery, jak E, rzeczy się domyślić Pierwszy w Wheel of Fortune, i korzystać z większej liczby bitów dla mniej popularne litery? Czemu? Ponieważ jesteśmy po prostu będzie używać ich rzadziej. 

Cóż, okazuje się, że nie mają były podejmowane próby, aby to zrobić. A jeśli pamiętacie z klasy szkoły lub szkoły, alfabet Morse'a. Kod Morse'a ma kropki i kresek, które może być przekazywane wzdłuż drutu jako dźwięków lub sygnały pewnego rodzaju. Ale Morse'a jest super czyste. Jest to rodzaj systemu binarnego w że masz kropki lub kreski. Ale jeśli widzisz, na przykład, dwie kropki. Lub jeśli myślisz, że z powrotem do operatora kto idzie jak Beep, beep, beep, dźwięk, uderzając trochę spust że wysyła się sygnał, Jeśli odbiorca, otrzymuje dwa punktów, jakie otrzymał pan wiadomość? Całkowicie arbitralne. 

JA? JA? Albo co about-- czy ja? Może to była tylko dwa prawy E jest? Więc nie ma tego problemu z dekodowalność z Morse Kod, w którym chyba że osoba, wysyłając wiadomość faktycznie wstrzymuje więc można sortować z zobaczyć lub usłyszeć luki między literami, to nie wystarczy po prostu wysyłać strumień zer i jedynek, lub kropki i kreski, bo nie ma dwuznaczności. E jest jednym punktem, więc jeśli zobacz dwie kropki lub usłyszeć dwie kropki, może to dwie E czy też może jest to jeden I. Musimy więc system, który jest trochę mądrzejszy niż to. Więc człowiek, imieniem Huffman lat temu wpadł właśnie to. Więc my po prostu się podjąć szybkie spojrzenie w jaki sposób drzewa są germane do tego. Przypuszczać, że jest to nieco głupia wiadomość chcesz wysłać, składa się z tylko A, B, C w D's i E'S, ale jest wiele redundancji tutaj. To nie tak miało być angielski. To nie jest szyfrowane. To tylko głupia wiadomość z dużą ilością powtórzeń. Więc jeśli naprawdę liczą się wszystkie A'S, B, C'S, D's, i E, oto jest częstotliwość. 20% z liter są A w 45% z liter to E, a trzy inne częstotliwości. Liczyliśmy się tam ręcznie i po prostu nie matematyka. 

Tak więc okazuje się, że Huffman, jakiś czas temu, sobie sprawę, że, wiesz, co, jeśli zacznę budynku drzewo lub las drzew, jeśli chcesz, w następujący sposób, można wykonać następujące czynności. Mam zamiar dać węzeł do każdego z listów, że dbają o i mam zamiar zapisać wewnątrz tego węzła częstotliwości jak zmiennoprzecinkowych wartości, lub można go używać N, zbyt, ale użyjemy tutaj pływaka. Oraz algorytm zaproponował, że można wziąć ten las pojedynczego węzła drzewa, więc bardzo krótkie drzewa, i rozpocząć łączenie ich z nowe grupy, nowe rodzice, jeśli będzie. I można to zrobić, wybierając opcję dwa najmniejsze częstotliwości jednocześnie. Wziąłem więc 10% i 10%. Utworzyć nowy węzeł. I wzywam nowy węzeł 20%. 

Których dwa węzły Łączę dalej? To trochę niejednoznaczne. Więc jest kilka przypadków rożny dla rozważyć, ale do przechowywania rzeczy ładne, Mam zamiar wybrać 20% - I teraz ignorować dzieci. Mam zamiar wybrać 20% i 15% i narysować dwie nowe krawędzie. A teraz czego dwa węzły mam logicznie połączyć? Ignoruj ​​wszystkie dzieci, wszystkie wnuki, wystarczy spojrzeć na korzenie teraz. Które węzły dwa mogę powiązać? Punkt dwa i 0,35. Więc pozwól mi wyciągnąć dwa nowe krawędzie. A potem mam tylko jeden. Więc oto drzewo. I to było rysowane celowo szukać rodzaju dość, ale zauważ, że krawędzie mają również oznaczony zera do jeden. Więc wszystkie lewej krawędzi są zerowe arbitralnie, ale konsekwentnie. Wszystkie prawa krawędź są te. 

A więc to, co Hoffman proponuje się, jeśli chcesz do reprezentowania B, zamiast reprezentują liczbę 66 a ASCII, który jest osiem całych bitów, Wiesz co, tylko sklep wzór zero, zero, zero, zero, bo to droga z mojego drzewa, drzewo pana Huffman, w do liści z korzenia. Jeśli chcesz się zapisać E, natomiast nie wysłać osiem bitów, które reprezentują E. Zamiast wysyłać jaki wzór bitów? Jeden. A co jest miłe jest to, że E jest najbardziej popularne pismo, i że używasz najkrótszy kod dla niego. Kolejnym najbardziej popularne Pismo to wygląda A. I tak było, ile bitów on zaproponować używając do tego? Zero, jeden. 

A ponieważ jest realizowany w tym drzewie, na razie pozwól mi przewidują tam dwuznaczności jak w Morse Kod, ponieważ wszystkie Litery dbasz o znajdują się na końcu tych brzegów. Więc to jest tylko jeden Zastosowanie drzewa. To jest-- i będę machać moja ręka na to, w jaki sposób Może to realizować jako struktura C. Musimy po prostu połączyć symbolem, jak char, a częstotliwość w lewo i prawo. Ale spójrzmy na dwa przykłady końcowe, które będziesz się dość dobrze po Quiz zero problemu ustawić pięć. 

Tak więc jest struktura danych znany jako tabeli mieszania. I tabeli mieszania jest rodzajem ochłodzenia się tym, że ma wiadra. I przypuśćmy, że istnieje cztery wiadra tu, zaledwie cztery spacje. Oto talia kart, a tu jest Klub, łopata, klub, diamenty, klub, diamenty, club, diamenty, clubs-- więc jest to przypadkowe. Serca, hearts-- więc jestem bucketizing wszystkich wejściach tutaj. I potrzeby tabeli mieszania patrzeć na wejściu, a następnie umieścić go w pewien umieścić w oparciu o to, co widzisz. Jest to algorytm. A ja za pomocą super, prosty algorytm wideo. Najtrudniejszą częścią, która była pamiętając, co zdjęcia były. A jeszcze cztery łączne rzeczy. 

Teraz rosły stosy, które Jest to celowe projektowanie rzecz tutaj. Ale co jeszcze mogę zrobić? Czyli tutaj mamy kilka starych książek egzaminacyjnych szkoły. Załóżmy, że grono Nazwiska studentów są tutaj. Oto większy tabeli mieszania. Zamiast czterech wiader, I, powiedzmy, 26. I nie chcę iść pożyczyć 26 rzeczy z zewnątrz [? Annenberg?], Więc Oto pięć, które stanowią A do Z. A jeśli zobacz ucznia, którego nazwa zaczyna się od A, Mam zamiar umieścić swoje quizu istnieje. Jeśli ktoś zaczyna z C, tam, A-- faktycznie, nie chcę tego robić. B idzie tutaj. Więc mam A i B i C. A Teraz oto kolejny uczniowi. Ale jeśli ta tabela mieszania jest realizowane z tablicy, Jestem rodzaju wkręca w tym miejscu, prawda? I niby trzeba umieścić to gdzieś. 

Więc jeden sposób mogę rozwiązać to wszystko w prawo, A jest zajęty, B jest zajęty, C jest zajęty. Mam zamiar umieścić go w D. Tak więc w Pierwszy, mam losowy natychmiastowy dostęp każdej z kubłów dla studentów. Ale teraz to rodzaj przekazane w coś liniowych, bo jeśli chcę szukać kogoś którego nazwa zaczyna się na literę A, sprawdzić tutaj. Jeśli jednak tak nie jest A studentka szukam, I niby zacząć sprawdzanie wiadra, bo to, co zrobiłem był rodzaj liniowo badać strukturę danych. Głupi sposób powiedzenia tylko patrzeć do pierwszego dostępnego otworu i umieścić jako plan B, że tak powiem, lub planu D w tym przypadku wartość w tym miejscu zamiast. To jest tak, że jeśli masz ma 26 miejsc i nie studentów o nazwie Q lub Z, lub coś podobnego że przynajmniej używasz miejsca. 

Ale widzieliśmy już więcej Rozwiązanie, tutaj, prawda? Co byś zrobił, zamiast jeśli masz kolizję? Jeśli dwie osoby mają Nazwa A, co by były inteligentniejsze lub więcej intuicyjne rozwiązanie, niż tylko Umieszczenie gdzie D ma być? Dlaczego nie mogę po prostu iść poza [? Annenberg?] jak malloc, innego węzła, umieścić go tutaj, a następnie umieścić, że student tutaj. Tak, że zasadniczo mają jakiś rodzaj tablicy, a może bardziej elegancko, jak jesteśmy zaczynają widzieć połączonej listy. 

I tak tabeli mieszania jest strukturą że może wyglądać podobnie jak ten, ale bardziej inteligentnie, to coś, co nazywa oddzielna łańcuchowym, w której tabeli mieszania prostu jest tablicą, każdy z którego elementy nie jest liczbą, sama jest związana lista. Tak, że masz super szybki dostęp podejmowaniu decyzji, gdzie do mieszania swoją wartość. Podobnie jak w przykładzie kart, Zrobiłem bardzo szybkich decyzji. Miłość idzie tutaj, diamenty idzie tutaj. Sama Tutaj, idzie tutaj, D idzie tutaj, B idzie tutaj. Więc bardzo szybko look-up, a jeśli zdarzy ci się uruchomić w przypadku gdzie mam kolizji, dwie osób z tej samej nazwie, a następnie po prostu zacząć łącząc je razem. A może i ty zachować je klasyfikowane alfabetycznie, a może nie. Ale przynajmniej teraz mamy dynamizm. Tak więc z jednej strony mamy super szybki Stała czasowa i rodzaj czasie liniowym udział, jeśli tych powiązanych list zaczynają się trochę długo. 

Więc tego rodzaju głupie, geeky lat żart temu. Na CS50 hack-a-Thon, kiedy uczniowie sprawdzenia, niektóre TF lub CA co roku uważa, że ​​to zabawne, aby umieścić to znak, jak ten, w którym po prostu Oznacza jeśli nazwa zaczyna się na A, go w ten sposób. Jeśli nazwa zaczyna z B, przejdź this-- OK, to zabawne, a może jeszcze w tym semestrze. Ale nie ma innego sposób w ten sposób, też. Wrócić do tego. 

Więc jest ta struktura. I to jest nasz ostatni Struktura na dziś co jest coś nazywa się trie. T-R-I-E, które z jakiegoś powodu jest krótki do wyszukiwania, ale to się nazywa trie. Więc trie to kolejna ciekawa amalgamat wiele z tych pomysłów. Jest to drzewo, które widzieliśmy wcześniej. To nie jest przeszukiwanie binarne drzewo. Jest to drzewo z dowolnej liczby dzieci, a każdy z dzieci w trie jest tablicą. Tablica wielkości, powiedzmy, 26 czy może 27 jeśli chcesz obsługuje nazw łącznikiem lub apostrofy w nazwach ludzi. 

A więc jest to struktura danych. A jeśli spojrzeć od góry do dołu, tak jakby Ciebie spojrzeć na najwyższym węźle tam, M, jest wskazując na skrajnej lewej rzeczy tam, który następnie A, X, W, E, L, L. To tylko struktura danych arbitralnie jest zapisywanie nazwisk ludzi. Maxwell są przechowywane tylko przez następujące ścieżka tablicy do tablicy do tablicy. Ale to, co niesamowite, około trie jest że, podczas połączonej listy, a nawet tablica, najlepsza, jaką kiedykolwiek dostał się Czas czas liniowy lub logarytmiczny patrząc ktoś się. W tej strukturze danych z trie, jeżeli moja struktura danych ma jedną nazwę w nim i szukam Maxwell, jestem będzie dość szybko go znaleźć. I wystarczy spojrzeć na M-A-X-W-E-L-L. Gdyby Ta struktura danych, natomiast jeśli N jest milion, jeśli istnieje milion nazw w tej strukturze danych, Maxwell nadal będzie wykrywalne po prostu M-A-X-W-E-L-L kroki. I kroki David-- D-A-V-I-D. Innymi słowy, poprzez tworzenie struktura danych, która jest ale w których wszystkie z tych tablic, wszystkie sami wspierać swobodny dostęp, Mogę zacząć patrząc Ludowej wymienić stosując ilość czasu, który jest proporcjonalne do nie liczba rzeczy w strukturze danych, jak milion istniejące nazwy. Ilość czasu zajmuje mi znaleźć M-A-X-W-E-L-L w strukturze danych jest proporcjonalna nie do Wielkość struktur danych, lecz długość nazwy. A realnie Nazwy szukamy się nigdy nie będą szalone długo. Może ktoś ma 10 charakter wymienić, 20 nazwę postaci. Na pewno skończona, prawda? Jest człowiekiem na Ziemi, który ma najdłuższą nazwę, ale ta nazwa jest stałą Długość wartości, prawda? Nie różni się ona w jakimkolwiek sensie. Tak więc w ten sposób mamy osiągnąć strukturę danych to stała czasowa przeglądowa. To ma podjąć szereg kroków W zależności od długości wkładu, ale nie numer nazwy w strukturze danych. Jeśli więc podwoić liczbę nazw w przyszłym roku od miliarda do dwóch miliardów, Odkrycie Maxwell zajmie dokładnie taka sama liczba siedmiu krokach aby go odnaleźć. A więc wydaje się, że osiągnięty nasz Święty Graal czasu pracy. 

Więc kilka szybkich ogłoszeń. Quiz zera jest wymyślanie. Więcej na ten temat na stronie internetowej kursu jest w ciągu najbliższych kilku dni. Poniedziałkowa lecture-- To święto tutaj na Harvardzie w poniedziałek. To nie jest w New Haven, więc bierzemy klasę do New Haven na wykładzie w poniedziałek. Wszystko będzie sfilmowane i transmitowane na żywo, jak zwykle, ale niech kończy dziś z 30 drugiego zacisku zwane "głębokich myśli" przez Daven Farnham, który został zainspirowany w zeszłym roku przez sobotę "Głębokie Myśli" Night Live Jack Handy, który powinien teraz sensu. 

FILM: A teraz, "Głębokie Myśli "przez Daven Farnham. Tablica mieszająca. 

Głośnik 1: Dobra, to wszystko na teraz. Do zobaczenia w przyszłym tygodniu. 

DOUG: Aby zobaczyć go w akcji. Warto więc przyjrzeć się, że właśnie teraz. Więc, mamy nieposortowanej tablicy. 

IAN: Doug, można iść dalej i restart to tylko na jedną sekundę, proszę. Dobrze, kamery są toczenia, więc działania, jeżeli jesteś gotowy, Doug, OK? DOUG: No dobrze, więc co my tu jest bez sortowania tablicy. A ja kolorowe wszystkie elementy czerwonego, co wskazuje na to, w rzeczywistości nieposortowane. Tak więc przypomnieć, że pierwszą rzeczą, jaką możemy zrobić jest sortujemy lewą połowę tablicy. Następnie sortować prawo połowa macierzy. I ya-da, ya-da, ya-da, możemy je połączyć razem. I mamy zupełnie posortowaną tablicę. Tak to jest, jak sortowanie przez scalanie działa. 

IAN: Zaraz, zaraz, zaraz, cięcia, cięcia, cięcia, cięcia. Doug, nie możesz po prostu ya-da, ya-da, ya-da, na swój sposób przez sortowanie przez scalanie. 

DOUG: Właśnie tak. Jest dobrze. Jesteśmy dobrze iść. Miejmy tylko utrzymać toczenia. W każdym razie, 

IAN: trzeba wyjaśnić to dokładniej niż. To nie jest po prostu za mało. DOUG: Ian, nie robimy trzeba wrócić do jednego. Jest dobrze. W każdym razie, jeśli mamy kontynuować merge-- Ian, jesteśmy w środku kręcenia. 

IAN: Wiem. I nie możemy po prostu ya-da, ya-da, ya-da, w całym procesie. Trzeba wyjaśnić, w jaki sposób Obie strony scalone razem. 

DOUG: Ale już mam wyjaśnia, w jaki sposób dwie sides-- 

IAN: Po prostu pokazane im tablica seryjnej. DOUG: Wiedzą, że ten proces. Oni są w porządku. Przeszliśmy nad nim dziesięć razy. 

IAN: Po prostu pomijane tuż nad nim. Wracamy do jednego, Nie możesz ya-da, ya-da się nad nim. Dobra, z powrotem do jednego. 

DOUG: Muszę wrócić przez wszystkie prowadnice? Mój Boże. To tak, jakby po raz szósty, Ian. Jest dobrze. 

IAN: Wszystko w porządku. Jesteś gotowy? Wielki. Akcja.