[Powered by Google Translate] [Tydzień 6, ciąg dalszy]
[David J. Malan] [Harvard University]
[To jest CS50.] [CS50.TV]
To, co jest CS50 koniec 6 tygodnia.
Więc CS50x, jeden z kursów 1-ci Harvardu zaangażowanych w inicjatywy EDX
rzeczywiście zadebiutował ten miniony poniedziałek.
Jeśli chcieliby Państwo uzyskać wgląd w to, co inni w Internecie
teraz stosując się, możesz udać się do x.cs50.net.
Który przekieruje Cię do odpowiedniego miejsca na edx.org,
co było, gdzie to i inne kursy z MIT i Berkeley teraz żyć.
Musisz zarejestrować się na konto, przekonasz się, że materiał jest w dużym stopniu same
jak miałem w tym semestrze, choć kilka tygodni opóźnione, ponieważ mamy wszystko gotowe.
Ale to, co uczniowie w CS50x będzie teraz zobaczyć, to interfejs bardzo podobny do tego.
To, na przykład, jest Zamyla prowadząc solucję do zbioru problemowego 0.
Po zalogowaniu się do edx.org, CS50x uczeń widzi różne rzeczy
można oczekiwać, aby zobaczyć w przedmiotu: wykład dla poniedziałku,
Wykład na środę, różne spodenkami, zestawy problem, solucje, pliki PDF.
Ponadto, jak można zobaczyć tutaj, tłumaczenia maszynowe
angielskich transkrypcji na język chiński, japoński, hiszpański, włoski,
i cała masa innych języków, które z pewnością będą niedoskonałe
jak rzucić je programowo przy użyciu coś, co nazywa API,
lub interfejs programowania aplikacji, od Google
która pozwala nam konwertować polski do tych innych językach.
Ale dzięki wspaniałym duchu niektórych ochotników sto-Plus,
przypadkowych ludzi w Internecie, którzy uprzejmie oferowane do angażowania
w ramach tego projektu, będziemy stopniowo ulegać poprawie jakości tych tłumaczeń
poprzez ludzi naprawić błędy, że nasze komputery wykonane.
>> Tak więc okazuje się, że mieliśmy kilka więcej studentów pokazać się w poniedziałek, niż początkowo oczekiwano.
W rzeczywistości, teraz ma 100.000 ludzi CS50x następujące razem w domu.
Więc sobie sprawę, że są częścią tego inauguracyjny klasa co ten kurs w informatyce
edukacja bardziej ogólnie, szerzej dostępne.
A rzeczywistość jest teraz, a niektóre z tych masowych kursów online,
wszyscy zaczynają się tych liczb bardzo dużych, jak wydaje się, że skończyliśmy.
Ale cel ostatecznie, CS50x jest naprawdę, aby uzyskać jak wielu ludzi do mety jak to możliwe.
Zgodnie z projektem, CS50x ma być oferowane z tym ostatnim poniedziałek
przez całą drogę 15 kwietnia 2013, tak, że ludzie, którzy mają zobowiązania szkoły w innym miejscu,
praca, rodzina, inne konflikty i podobne, mają nieco większą elastyczność
z którym do nurkowania w tym kursie, co wystarczy powiedzieć,
jest dość ambitnie zrobić, jeśli tylko w ciągu zaledwie trzech miesięcy w trakcie zwykłego semestru.
Ale te studenci będą walki te same zestawy problemowe, sprawdzające tę samą treść,
dostępu do tych samych, jak spodenki i.
Więc sobie sprawę, że tak naprawdę wszyscy jesteśmy w tym razem.
A jednym z celów końcowych CS50x jest nie tylko, aby jak najwięcej ludzi
do mety i dać im w szał zrozumienie informatyki
i programowania, ale także, aby je mieć to wspólne doświadczenie.
Jedną z cech charakterystycznych 50 na terenie kampusu, mamy nadzieję,
było to coś w rodzaju wspólnym doświadczeniem, na lepsze lub gorsze, czasami,
ale o tych ludzi, aby włączyć się w lewo i prawo,
i godziny biurowe i hackathon i uczciwe.
Jest to trochę trudniejsze, że osoby z ludzi online,
ale CS50x zakończy się w kwietniu z pierwszego w historii CS50 Expo
który będzie online na dostosowanie naszej idei fair
gdzie te tysiące studentów będzie być zaproszeni do złożenia 1 - do 2-minutowego filmu,
albo screencast ich ostatecznego projektu lub wideo z nich macha komentarzy
i mówić o ich projektu i demoing go,
podobnie jak waszych poprzedników zrobić tutaj na kampusie w targach,
tak, że przez koniec semestru, jest nadzieja na uzyskanie globalnego wystawę
końcowych przez CS50x studenckich projektów, podobnie jak to, co czeka Cię w grudniu tego roku tu, na terenie kampusu.
Więc więcej o tym w najbliższych miesiącach.
>> Z 100.000 studentów, choć przychodzi konieczność kilku urzędów więcej.
Biorąc pod uwagę, że chłopaki są płonący ślad tutaj i biorąc CS50
kilka tygodni przed premierą tego materiału dla ludzi na EDX,
zrealizować chcielibyśmy zaangażować jak wielu naszych studentów, jak to możliwe w tej inicjatywie,
zarówno w trakcie semestru, jak i tej zimy i wiosną tego roku nadchodzi.
Więc jeśli chcesz się zaangażować w CS50x,
szczególnie łączącą w sprawie CS50x dyskutować, Wersja EDX z CS50 dyskutować,
które wielu z was używał na kampusie, online tablicy ogłoszeń,
proszę głowa do tego adresu URL, daj nam znać, kim jesteś,
bo chcielibyśmy budować zespół studentów i pracowników i wykładowców zarówno
na uczelni, którzy są po prostu grać dalej i pomagać.
A gdy zobaczysz pytanie, jest im bliskie,
usłyszysz studenta raportowania jakiś błąd gdzieś tam w jakimś kraju w Internecie,
i że pierścienie dzwon, bo też miałem ten sam problem
w d-sali jakiś czas temu, mam nadzieję, że wtedy można dostroić się i podziel się swoim doświadczeniem.
Więc proszę wziąć udział, jeśli chcesz.
>> Kursy informatyki na Harvardzie mieć trochę tradycji,
CS50 wśród nich, z konieczności trochę odzieży, niektóre ubrania, które można nosić z dumą
na koniec semestru, mówiąc dość dumnie, że skończyłeś CS50
i wziął CS50 i tym podobne, i zawsze staramy się zaangażować uczniów
w tym procesie, jak najwięcej, w którym możemy zaprosić,
W tym czasie w semestrze, studenci do składania projektów
użyciu Photoshopa, czy cokolwiek narzędziem wyboru chcesz używać
jeśli jesteś projektantem, przedłożyć projekty na T-shirty i bluzy
i parasole i małe bandany dla psów mamy i tym podobne.
I wszystko jest wtedy - zwycięzcy każdego roku są następnie wystawiane
na kursie na stronie internetowej store.cs50.net.
Wszystko jest sprzedawane w cenie tam, ale na stronie internetowej po prostu uruchamia się
i pozwala ludziom wybór kolorów i wzorów, które im się podobają.
Więc pomyślałem, że po prostu podzielić się z zeszłorocznych projektów
które były na stronie internetowej poza tym tutaj, który jest coroczną tradycją.
"Każdego dnia jestem Seg Faultn" był jednym z udzielonych w ubiegłym roku,
która jest nadal dostępna jest dla absolwentów.
Mieliśmy ten jeden, "CS50, założona 1989."
Jeden z naszych Bowdens, Rob, był bardzo popularny w zeszłym roku.
"Team Bowden" urodził się, aby ten projekt został przedłożony wśród najlepszych sprzedawców.
Jak to było tu nikogo. Wielu ludzi ma "Fever Bowdena" Według sprzedaży dzienników.
Sobie sprawę, że może być teraz Twój projekt tam się w Internecie.
Więcej szczegółów na ten temat w następnym problemu ustawia przyjść.
>> Jeszcze jedno narzędzie: miałeś kilka ekspozycji i mam nadzieję teraz
pewne praktyczne doświadczenie z GDB,
co, oczywiście, debugger i pozwala manipulować
Twój program na poziomie dość niskim poziomie, co robi różne rzeczy?
Co GDB pozwala zrobić?
Tak? Daj mi coś. [Odpowiedź Student, niezrozumiały]
Good. Krok do funkcji, więc nie wystarczy wpisać słowo
i mieć cios programu dzięki całości, drukowanie rzeczy do standardowego wyjścia.
Przeciwnie, można wejść przez to linia po linii, albo wpisując obok
iść linia po linii po linii lub stopniu do nurkowania w funkcji, zazwyczaj jeden, który napisał.
Co jeszcze robi GDB pozwala zrobić? Tak? [Odpowiedź Student, niezrozumiały]
Wydrukuj zmienne. Więc jeśli chcesz zrobić trochę introspekcji wewnątrz programu
bez konieczności uciekania się do pisania printf na miejsce,
można po prostu wydrukować zmiennej lub wyświetlić zmienną.
Co jeszcze można zrobić z debugera jak GDB?
[Odpowiedź Student, niezrozumiały]
Dokładnie. Możesz ustawić punkty przerwania, można powiedzieć, wykonanie przerwy
w głównej funkcji lub funkcji foo.
Można powiedzieć, że wykonanie przerwy w linii 123.
I pułapki są naprawdę potężna technika
bo jeśli masz ogólne poczucie, gdzie Twój problem
zapewne, nie trzeba tracić czasu na przejście przez programu całości.
Można zasadniczo wskoczyć tam i wtedy zacznij pisać -
przejście przez niego lub następnego kroku lub podobne.
Ale jest haczyk z czymś GDB jest to, że pomaga, człowiek,
odnaleźć swoje problemy i znaleźć błędy.
To nie koniecznie znaleźć ich tak wiele dla Ciebie.
>> Więc wprowadzono inne style50 dzień, który jest krótki narzędziem wiersza poleceń
który stara się stylizować kod trochę bardziej czysty niż ty, człowiek, może mieć zrobione.
Ale to też jest naprawdę estetyczne rzeczą.
Ale okazuje się, że to jest inne narzędzie nazywa Valgrind, że jest trochę bardziej złożoną w użyciu.
Jego produkcja jest potwornie cryptic na pierwszy rzut oka.
Ale to cudownie przydatne, zwłaszcza teraz, kiedy jesteśmy w części kadencji
gdy zaczynasz używać malloc i dynamicznej alokacji pamięci.
Rzeczy może pójść nie tak naprawdę, naprawdę źle szybko.
Bo jeśli zapomnimy zwolnić pamięć, lub nieprawidłowego trochę wskaźniku NULL,
lub nieprawidłowego jakiś wskaźnik śmieci, co jest zazwyczaj objawem, że wyniki?
Seg winy. I masz ten plik rdzenia pewnej liczby kilobajtach lub megabajtach
który reprezentuje stan pamięci Twojego programu, kiedy rozbił się,
ale twój program ostatecznie seg wady, winy segmentacji,
co oznacza, że ​​coś złego się stało niemal zawsze związane
do pamięci związanych pomyłkę, że dokonane gdzieś.
Więc Valgrind pomaga znaleźć takie rzeczy.
Jest to narzędzie, które można uruchomić, jak GDB, kiedy już skompilowany program,
ale zamiast uruchomić program bezpośrednio, uruchomić Valgrind
i do niej przekazywać swój program, tak jak robisz z GDB.
Teraz, użytkowania, aby uzyskać najlepszy rodzaj produkcji,
jest trochę długi, więc tam na szczycie ekranu zobaczysz Valgrind-v.
"-V" niemal powszechnie oznacza verbose gdy używasz programów na komputerze z systemem Linux.
Więc oznacza to wypluć więcej danych niż możesz być domyślnie.
"- Wyciek-check = full." To jest po prostu mówiąc czek na wszystkich możliwych wycieków pamięci,
błędy, które mógłbym wykonane. To też jest wspólny paradygmat z programami Linux.
Generalnie, jeśli masz argument wiersza polecenia to "switch",
, który powinien zmienić program zachowania, a to jedna litera,
to-v, ale jeśli jest to włączone, po prostu projekt programatora,
jest pełne słowo lub szereg słów, argument linii poleceń zaczyna się od -.
Są to tylko ludzkie konwencje, ale zobaczysz je coraz bardziej.
, A następnie, na koniec, "a.out" jest dowolną nazwę programu w tym konkretnym przykładzie.
A tu jakiś przedstawiciel wyjście.
>> Zanim przyjrzymy się, co to może oznaczać, pozwól mi przejść do fragmentu kodu tutaj.
I pozwól mi przenieść ten z drogi, wkrótce,
i rzućmy okiem na memory.c, co jest to krótki przykład tutaj.
Więc w tym programie, pozwól mi przybliżyć funkcje i pytania.
Mamy funkcję głównego, który wywołuje funkcję, F,
i co ma zrobić, przejdź do f, w języku angielskim nieco techniczną?
Co f postępować zrobić?
Jak o Zacznę linii 20, a gwiazda jest lokalizacja nie ma znaczenia,
ale ja po prostu być zgodne tu z ostatniego wykładu.
Co znajduje się linia 20 nie dla nas? Na lewej stronie. Będziemy rozbicie go dalej.
Int * x: co to robić?
Okay. To stwierdzenie jest wskaźnik, a teraz niech się jeszcze bardziej techniczny.
Co to znaczy, bardzo konkretnie, aby zadeklarować wskaźnik? Ktoś jeszcze?
Tak? [Odpowiedź Student, niezrozumiały] za daleko.
Więc czytasz na prawej stronie znaku równości.
Skupmy się tylko na lewo, tylko na int * x.
To nie "deklarują" wskaźnik, ale teraz niech nurkować głębiej do tej definicji.
Co to konkretnie, technicznie oznacza? Tak?
[Odpowiedź Student, niezrozumiały]
Okay. Jest to przygotowanie do zapisania adresu w pamięci.
Good. I zróbmy krok dalej, to deklarowanie zmiennej, x, to jest 32 bitów.
I wiem, że to jest 32 bitów, ponieważ -
To nie dlatego, że to int, ponieważ jest to wskaźnik w tym przypadku.
Zbieg okoliczności, że to jedno i to samo z int,
ale fakt, że jest gwiazdą nie oznacza, że ​​jest to wskaźnik
i urządzenia, jak w wielu komputerach, ale nie wszystkie, wskaźniki są 32 bity.
Na więcej nowoczesnego sprzętu, jak najnowsze komputery Mac, komputery najnowsze, może być 64-bitowych,
ale w urządzeniu, te rzeczy są 32 bity.
Będziemy więc ujednolicić tego. Bardziej konkretnie, historia wygląda następująco:
We "deklarują" wskaźnik, co to oznacza?
Przygotowujemy do przechowywania adresu pamięci.
Co to znaczy?
Tworzymy zmienną o nazwie x, która zajmuje 32 bity
które wkrótce zapisać adres całkowitej.
I to jest prawdopodobnie tak precyzyjny, jak możemy.
Jest dobrze naprzód uprościć świat i po prostu powiedzieć zadeklarować wskaźnik o nazwie x.
Deklaracja wskaźnika, ale uświadomić sobie i zrozumieć, co się dzieje
nawet w ciągu zaledwie kilku tych znaków.
>> Teraz, ten jest prawie trochę łatwiej, choć to już wyraz.
Więc co to robi, że jest podświetlona teraz: "malloc (10 * sizeof (int));" Tak?
[Odpowiedź Student, niezrozumiały]
Good. A ja wezmę go tam. To przydzielenie kawałek pamięci dziesięciu liczb całkowitych.
A teraz zanurkować nieco głębiej, to przydzielenie kawałek pamięci dziesięciu liczb całkowitych.
Co to jest malloc następnie powrót?
Adres tego kawałka, lub, bardziej konkretnie, adres pierwszego bajtu tym kawałku.
Jak więc jestem, programista, aby wiedzieć, gdzie kończy się, że fragment pamięci?
Wiem, że to jest ciągłe. Malloc, z definicji, daje ciągły fragment pamięci.
Żadnych przerw w nim. Masz dostęp do każdego bajtu w tym kawałku,
z powrotem do tyłu do tyłu, ale skąd mam wiedzieć, gdzie koniec tego kawałka pamięci jest?
Podczas korzystania z funkcji malloc? [Odpowiedź Student, niezrozumiały] Dobra.
Nie masz. Musisz pamiętać.
I trzeba pamiętać, że użyłem wartości 10, a ja nawet nie wydają się tego robić tutaj.
Ale spoczywa wyłącznie na mnie. Strlen, którego staliśmy się nieco zależne od ciągów,
działa tylko z powodu tej konwencji o \ 0
czy ta specjalna nul charakter, NUL, na końcu łańcucha.
Że nie posiada za zaledwie dowolnych fragmentów pamięci.
To zależy od Ciebie. Tak linii 20, a następnie, przydziela ilość pamięci
, który może przechowywać dziesięć liczby całkowite, i zapisuje się adres pierwszego bajtu
tego fragmentu pamięci w zmiennej x wywołana.
Ergo, które jest wskaźnik. Więc linii 21, niestety, było błędem.
Ale najpierw, co on robi? To mówiąc, sklep na miejscu 10, 0 indeksowane,
z kawałka pamięci o nazwie x 0 wartość.
>> Więc zauważyć kilka rzeczy są dzieje.
Nawet jeśli x jest wskaźnik, wycofanie się z kilka tygodni temu
że można jeszcze użyć tablicy stylu notacji nawias prostokątny.
Bo to rzeczywiście krótki ręka notacja dla bardziej tajemnicze wyglądającej arytmetycznej wskaźnika.
gdzie chcemy zrobić coś takiego: Weź x adresowej, przenieść 10 punktów nad,
następnie przejść do tego, co tam jest adres zapisany w tej lokalizacji.
Ale szczerze mówiąc, to jest po prostu okropne czytać i dostać się komfortowo.
Więc świat zazwyczaj wykorzystuje nawiasy kwadratowe tylko dlatego, że jest o wiele bardziej przyjazny dla ludzi do czytania.
Ale to, co naprawdę dzieje się pod maską;
x to adres nie, tablica, per se.
Więc to jest przechowywanie 0 w miejscu 10 w x.
Dlaczego to jest złe? Tak?
[Odpowiedź Student, niezrozumiały] Dokładnie.
Mamy tylko przydzielone dziesięć wskazówki, ale liczymy od 0 przy programowaniu w C,
aby mieć dostęp do 0 1 2 3 4 5 6 7 8 9, 10, lecz nie.
Więc albo program będzie seg winy lub nie.
Ale naprawdę nie wiem, to jest coś w rodzaju niedeterministycznych zachowania.
To naprawdę zależy od tego, czy nam się poszczęści.
Jeśli okaże się, że system operacyjny nie ma nic przeciwko, jeśli mogę użyć tego dodatkowy bajt,
mimo, że nie dał mi to, mój program nie może upaść.
To surowe, wadliwa, ale nie może zobaczyć, że objaw,
lub można go zobaczyć tylko raz na jakiś czas.
Rzeczywistość jest jednak, że błąd jest w rzeczywistości, tam.
I to jest naprawdę kłopotliwe, jeśli napisałeś program, który ma być poprawne,
, które zostały sprzedane program, ludzie korzystają, że każdy raz na jakiś czas wywala
, ponieważ, oczywiście, nie jest dobry. W rzeczywistości, jeśli masz telefon z systemem Android lub iPhone
i pobrać aplikacje te dni, jeśli kiedykolwiek miał aplikacja po prostu zamknąć,
nagle znika, to jest prawie zawsze wynikiem jakiegoś problemu związanego z pamięci,
której programista spieprzył i dereferencjonowane wskaźnik
, że on lub ona nie powinna mieć, a wynik iOS lub Android jest po prostu zabić program całkowicie
zamiast ryzyka zachowanie niezdefiniowane lub jakiegoś kompromisu bezpieczeństwa.
>> Jest jeszcze jeden błąd w programie, oprócz tej jednej.
Co jeszcze schrzaniłem w tym programie?
I już nie praktykuje tego, co już głosił. Tak?
[Odpowiedź Student, niezrozumiały] Dobra.
Nie uwalnia pamięć. Więc zasada teraz
musi być w każdej chwili zadzwonić malloc, należy zadzwonić za darmo, kiedy są wykonywane przy użyciu tej pamięci.
Teraz, kiedy chciałbym zwolnić tę pamięć?
Prawdopodobnie, zakładając, że pierwsza linia była poprawna, chciałbym to zrobić tutaj.
Bo nie może, na przykład, to zrobić tutaj. Dlaczego?
Tylko z zakresu. Więc nawet jeśli mówimy o wskaźniki,
jest to 2 lub 3 tygodni problem, gdzie x jest tylko w zakresie wewnątrz nawiasy, gdzie została zadeklarowana.
Więc na pewno nie może uwolnić go tam. Moja jedyna szansa, aby uwolnić ją mniej więcej po linii 21.
Jest to dość prosty program, to było dość proste, gdy rodzaj owinięty swój umysł
wokół tego, co program robi, gdzie błędy były.
I nawet jeśli nie widzimy na pierwszy, miejmy nadzieję, że to trochę oczywiste teraz
że te błędy są dość łatwo rozwiązać i łatwo wykonane.
Ale gdy program jest więcej niż 12 linijek, to 50 linijek, 100 linijek,
chodzenie po linii kodu po linii, myśląc przez to logicznie,
jest możliwe, ale nie jest szczególnie do zabawy, ciągle szuka błędów,
i to także trudne, i dlatego narzędzia takie jak Valgrind istnieje.
Pozwólcie mi iść do przodu i zrobić to: pozwól mi otworzyć okno terminala,
i niech mi nie wystarczy uruchomić pamięć, bo pamięć wydaje się być w porządku.
Dostaję szczęście. Tego dodatkowego będzie bajtu na koniec tablicy
, nie wydaje się być zbyt skomplikowane.
Ale niech mnie, mimo wszystko, zrobić test poczytalności co oznacza po prostu, aby sprawdzić
, czy też nie jest to rzeczywiście prawidłowe.
>> Więc zróbmy Valgrind-V - wyciek-check = full,
a następnie nazwę programu w tym przypadku pamięć nie a.out.
Więc pozwól mi iść do przodu i robić. Naciśnij klawisz Enter.
Drogi Boże. To jest jego wyjście, i to, co wspomniałem wcześniej.
Ale, jeśli uczą się czytać przez wszystkie bzdury tutaj
większości jest to tylko wyjście diagnostyczne, które nie jest tak interesujące.
Co twoje oko naprawdę chce się szukać jakakolwiek wzmianka błędu lub nieprawidłowych.
Słowa, które sugerują problemy.
I rzeczywiście, zobaczymy, co się dzieje źle tutaj.
Mam podsumowanie pewnego rodzaju ", stosowany w wyjścia:. 40 bajtów 1 bloków"
Nie jestem pewien, co blok to jeszcze, ale 40 bajtów
faktycznie czuje się jak mogę dowiedzieć się, gdzie który jest pochodzi.
40 bajtów. Dlaczego 40 bajtów wykorzystania na wyjeździe?
A dokładniej, jeśli przewiń tutaj
dlaczego na pewno stracił 40 bajtów? Tak?
[Odpowiedź Student, niezrozumiały] Perfect. Tak, dokładnie.
Było dziesięć liczbami całkowitymi, a każdy z nich jest wielkości 4 lub 32 bitów,
tak straciłam dokładnie 40 bajtów, ponieważ, jak to zaproponował, nie nazywa się free.
To jeden błąd, a teraz spójrzmy w dół nieco dalej i zobaczyć obok tego,
"Nieprawidłowy zapis wielkości 4". Teraz to, co to jest?
Adres ten jest wyrażony co notacji podstawowej, najwyraźniej?
To jest szesnastkowy, a za każdym razem można zobaczyć numer zaczynający się od 0x,
oznacza to, szesnastkowy, co zrobiliśmy w drodze powrotnej w, myślę, w sekcji Pset 0 pytań,
co było po prostu zrobić ćwiczenia rozgrzewki, konwersja hex na dziesiętny na binarny i tak dalej.
Szesnastkowy, tylko przez ludzi z konwencją, jest zwykle używany do reprezentowania wskaźników
lub, bardziej ogólnie, adresów. To jest po prostu konwencja,
bo to trochę łatwiejsze do odczytania, jest to trochę bardziej kompaktowy niż coś po przecinku,
i binarne jest bezużyteczne dla większości ludzi, aby użyć.
Więc teraz, co to znaczy? Cóż, wygląda na to, że znajduje się nieprawidłowy zapis
wielkości 4 na linii 21 z memory.c.
Więc wróćmy do linii 21, i rzeczywiście, jest to, że nieprawidłowy zapis.
Więc Valgrind nie będzie całkowicie weź mnie za rękę i powiedz, co na to jest,
ale wykrywa, że ​​robię nieprawidłowy zapis.
Dotykam 4 bajty, że nie powinno być, a podobno to dlatego,
jak pan zauważył, robię [10] zamiast [9] maksymalnie
lub [0] lub coś pomiędzy.
Z Valgrind, realizować czasu jesteś teraz pisze program
wykorzystujący wskaźniki i wykorzystuje pamięć i malloc Dokładniej,
na pewno dostać się do nawyku jazdy tak długo
ale bardzo łatwo kopiować i wklejać dowództwo Valgrind
aby sprawdzić, czy znajduje się kilka błędów w tam.
I to będzie ogromna każdym zobaczyć wyjście,
ale po prostu analizować przez wizualnie wszystkie wyjścia i zobacz czy widzisz wspomina błędów
lub ostrzeżenia lub nieprawidłowe lub utracone.
Wszelkie słowa, które brzmią jak ty skręcane gdzieś.
Więc sobie sprawę, że jest to nowe narzędzie w zestawie narzędzi.
>> Teraz w poniedziałek, mieliśmy całą masę ludzi przychodzą tu
i reprezentują pojęcia połączonej listy.
I wprowadził połączonej listy jako rozwiązanie do tego, co problem?
Tak? [Odpowiedź Student, niezrozumiały] Dobra.
Tablice nie są dodane do nich pamięci.
Jeśli przydzielić tablicy rozmiaru 10, to wszystko masz.
Możesz zadzwonić do funkcji takich jak realloc jeśli początkowo nazywany malloc,
i można spróbować rosnąć tablicy jeśli jest miejsce pod koniec tego
że nikt inny nie używa, a jeśli nie, to po prostu znaleźć ci większy kawałek gdzieś indziej.
Ale to będzie skopiować wszystkie te bajty do nowej tablicy.
To brzmi jak rozwiązanie bardzo poprawny.
Dlaczego to jest nieatrakcyjna?
Myślę, że to działa, ludzie rozwiązać ten problem.
Dlaczego musimy się go rozwiązać w poniedziałek powiązanych list? Tak?
[Odpowiedź Student, niezrozumiały] To może zająć dużo czasu.
W rzeczywistości, za każdym razem dzwonisz malloc lub realloc lub calloc, co jest jeszcze jeden,
każdym razem, gdy program, mówisz do systemu operacyjnego,
masz tendencję do spowolnić program dół.
A jeśli robisz tego typu rzeczy w pętli, jesteś naprawdę spowalnia rzeczy.
Nie zamierzamy to zauważyć na najprostszych "Hello World" programów typu,
ale w znacznie większych programów, zwracając się do systemu operacyjnego ponownie i ponownie do pamięci
lub podając go znowu i znowu raczej nie będzie dobrze.
Plus, to jest po prostu swego rodzaju intelektualnym - to kompletna strata czasu.
Dlaczego przeznaczyć coraz więcej pamięci, ryzyko kopiując wszystko do nowej tablicy,
jeśli masz alternatywę, która pozwala przydzielić tylko tyle pamięci, jak rzeczywiście potrzebne?
Więc nie ma plusy i minusy w tutaj.
Jednym z plusów jest to, że teraz mamy dynamikę.
Nie ma znaczenia, gdzie kawałki pamięci jest to, że są wolne,
Mogę jakoś stworzyć te okruszki chleba poprzez wskaźniki
do string całe połączonej listy razem.
Ale zapłacić co najmniej jedną cenę.
>> Co muszę oddać w uzyskaniu związane życzeń?
Tak? [Odpowiedź Student, niezrozumiały] Dobra.
Potrzebujesz więcej pamięci. Teraz potrzebuję miejsca dla tych wskaźników,
w tym przypadku połączony super proste liście
że jest tylko próbuje przechowywać liczby całkowite, które są 4 bajty, wciąż mówią
dobrze, wskaźnik jest 4 bajty, więc teraz mam dosłownie podwoiła
Ilość pamięci, muszę tylko zapisać tę listę.
Ale znowu, jest to stały kompromis w informatyce
między czasie i przestrzeni i rozwoju, wysiłku i innych zasobów.
Co innego Minusem korzystania z połączonej listy? Tak?
[Odpowiedź Student, niezrozumiały]
Good. Nie tak łatwo dostępne. Nie możemy już wykorzystać
tydzień 0 zasady jak dziel i rządź.
A dokładniej, binarne wyszukiwanie. Bo choć my ludzie
można zobaczyć w przybliżeniu, gdzie środek tej listy jest
komputer wie, że ten powiązany Lista zaczyna się od adresu o nazwie pierwszy.
I to jest 0x123 lub coś w tym stylu.
A jedynym sposobem Program można znaleźć środkowego elementu
jest faktycznie przeszukać całą listę.
I nawet wtedy, dosłownie musi przeszukać całą listę, bo
nawet po osiągnięciu środkowego elementu wykonując wskaźniki,
ty program, nie mają pojęcia, jak długo ta lista jest, potencjalnie,
aż dojdziesz do końca to, i jak wiesz, programowo
że jesteś na koniec listy połączony?
Jest specjalny wskaźnik NULL, więc ponownie, konwencja.
Zamiast korzystać z tego wskaźnika, na pewno nie ma to być jakaś wartość śmieci
wskazując na scenie gdzieś, chcemy go za rękę w dół, null,
tak, że mamy tę terminus w tej strukturze danych, tak wiemy, gdzie się kończy.
>> Co jeśli chcemy manipulować tym?
Zrobiliśmy większość tego wizualnie, a także z ludźmi,
ale co jeśli chcemy zrobić wstawiania?
Więc oryginalna lista była 9, 17, 20, 22, 29, 34.
Co jeśli potem chciał przestrzeni malloc na numer 55, za to, węzła
a następnie chcemy wstawić 55 na liście, tak jak to zrobiliśmy w poniedziałek?
W jaki sposób możemy to zrobić? Cóż, Anita podszedł i ona zasadniczo chodził listę.
Rozpoczęła się pierwszego elementu, a następnie dalej, następne, następne, następne, następne.
Wreszcie uderzył lewą w dół
i zrealizowane oh, to jest NULL. Więc co manipulacja wskaźnik należy zrobić?
Osoba, która była na końcu, numer 34, potrzebował jego lewa ręka podniesiona
do punktu na 55, 55 potrzebował ich lewą rękę skierowaną w dół, aby mieć nowy NULL terminator. Gotowe.
Dość łatwo wstawić 55 do posortowanej listy.
I jak może to wyglądać?
>> Pozwólcie mi iść do przodu i otworzyć jakiś przykład kodu tutaj.
Ja otwarcie gedit i pozwól mi otworzyć dwa pliki pierwszy.
Jednym z nich jest list1.h, i daj mi tylko przypomnieć, że jest to fragment kodu,
że stosowany do reprezentowania węzeł.
Węzeł ma zarówno int o nazwie n i wskaźnik zwany dalej, że tylko punkty do następnej rzeczy z listy.
To jest teraz w pliku. Godz. Dlaczego?
Jest to konwencja, a nie skorzystało z tego ogromną ilość sami,
ale człowiek, który napisał i innych funkcji printf
dał jako dar dla świata te wszystkie funkcje, pisząc plik o nazwie stdio.h.
A wtedy nie string.h, a następnie tam map.h, a tam wszystkie te pliki h
że może widzieliście lub używane w okresie napisane przez innych ludzi.
Zazwyczaj w tych. Pliki h są tylko takie rzeczy jak typedef
lub deklaracje niestandardowych lub deklaracje stałych.
Nie umieścić implementacje funkcji "w plikach nagłówkowych.
Umieścić, zamiast tylko ich prototypy.
Można umieścić rzeczy, które chcesz podzielić się ze światem, co trzeba
aby skompilować kod. Więc po prostu dostać się do tego zwyczaju,
zdecydowaliśmy się zrobić to samo. Nie ma wiele w list1.h,
ale mamy już coś, co może być interesujące dla ludzi na świecie
, którzy chcą skorzystać z naszej połączonej realizację listy.
Teraz, w list1.c, nie będzie przejść przez te wszystkie rzeczy
bo to trochę długo, ten program, ale niech to naprawdę szybko biegać na polecenia.
Pozwól mi skompilować Lista1, niech następnie uruchomić Lista1 i co zobaczysz jest
mamy symulowane prosty mały program tutaj
że się dzieje, żebym mógł dodawać i usuwać numery do listy.
Więc pozwól mi iść dalej i wpisz 3 na 3 opcji menu.
Chcę wstawić numer - zróbmy pierwszy numer, który był 9,
a teraz mi powiedziano lista jest teraz 9.
Pozwól mi iść dalej i zrobić kolejny wkładanie, więc uderzyłem opcji menu 3.
Jaki numer chcę wstawić? 17.
Enter. I zrobię tylko jeden.
Pozwól mi wstawić numer 22.
Więc mamy początki połączonej listy, że mieliśmy w formie slajdów chwilą.
Jak to jest wprowadzenie właściwie się dzieje?
Rzeczywiście, 22 znajduje się teraz w koniec listy.
Więc opowieści powiedzieliśmy na scenie w poniedziałek i recapped właśnie
muszą być rzeczywiście dzieje się w kodzie.
Rzućmy okiem. Pozwól, przewiń w tym pliku.
Będziemy tuszować niektóre z funkcji,
ale będziemy iść w dół do, powiedzmy, funkcja insert.
>> Zobaczmy, w jaki sposób go o wstawienie nowego węzła w tej połączonej listy.
Gdzie jest lista zadeklarowanych? Cóż, przejść całą drogę w górę na górze,
i zauważ, że moja lista jest zasadniczo związany zgłoszone jako jeden wskaźnik, który jest początkowo NULL.
Więc używam zmienną globalną tutaj, co w ogóle mamy głosił przeciw
ponieważ czyni Twój kod trochę bałagan w utrzymaniu,
To trochę leniwy, zazwyczaj, ale to nie jest leniwy i nie jest źle i nie jest źle
Jeśli twój program jest jedynym celem w życiu jest symulacja jeden połączonej listy.
Która jest dokładnie to, co robimy.
Więc zamiast zgłoszenia tego w głównym, następnie trzeba przekazać go do każdej funkcji
pisaliśmy w tym programie, zamiast realizować oh, po prostu sprawiają, że globalne
ponieważ cały Celem tego programu jest pokazanie jednej i tylko jednej połączonej listy.
Tak, że czuje się dobrze. Oto moje prototypy, i nie przejdzie przez wszystkie te,
ale napisałem funkcję usuwania, w funkcji wyszukiwania, funkcję insert oraz funkcji trawersu.
Ale bądźmy teraz wrócić w dół do funkcji płytek
i zobaczyć, jak ten jeden działa tutaj.
Insert jest na linii - jedziemy.
Wstaw. Tak więc nie trzeba żadnych argumentów, bo będziemy prosić
wewnątrz użytkownik tej funkcji dla liczby chcą wstawić.
Ale najpierw przygotować, aby dać im trochę miejsca.
Jest to rodzaj kopiowania i wklejania z innego przykładu.
W tym przypadku, byliśmy przydzielania int, tym razem mamy do podziału węzła.
Naprawdę nie pamiętam, jak wiele bajtów węzeł jest, ale to jest w porządku.
Sizeof mogę zrozumieć, że dla mnie.
I dlaczego ja sprawdzanie NULL w wierszu 120?
Co może pójść źle w linii 119? Tak?
[Odpowiedź Student, niezrozumiały]
Good. Po prostu może być tak, że poprosiłem o pamięć zbyt dużo
czy coś jest nie tak, a system operacyjny nie ma wystarczającej ilości bajtów do daj mi,
tak to sygnalizuje tyle powracając NULL, a jeśli nie sprawdzić, że
a ja po prostu ślepo przystąpić do korzystania adres zwrócony, to może być NULL.
To może być jakaś nieznana wartość; nie jest dobrą rzeczą, chyba że -
rzeczywiście nie będzie wartość nieznana. To może być NULL, więc nie chcę
do nadużywania go i ryzykować dereferencji go.
Jeśli tak się stanie, po prostu wrócić i będziemy udawać, że nie wrócę wszelkich pamięci w ogóle.
>> W przeciwnym razie, mówię użytkownik daj mi numer do wstawienia, wzywam naszego starego getInt przyjacielu,
a potem to nowa składnia wprowadziliśmy w poniedziałek.
"Newptr-> n" oznacza mieć adres, który podano przez malloc
co stanowi pierwszy bajt nowego obiektu węzła
a następnie przejść do pola o nazwie n.
Trochę trivia pytanie: Jest to odpowiednik tego, co bardziej tajemniczych linii kodu?
Jak inaczej mógłbym napisać to? Chcesz wziąć ukłucie?
[Odpowiedź Student, niezrozumiały]
Good. Pomocą. N, ale to nie jest tak proste, jak to.
Co mam najpierw zrobić? [Odpowiedź Student, niezrozumiały]
Good. Muszę zrobić newptr.n *.
Więc to mówi nowy wskaźnik jest oczywiście adres. Dlaczego?
Ponieważ został zwrócony przez malloc. Newptr * mówiąc "tam"
, a następnie, gdy jesteś tam, a następnie można użyć bardziej znajomy. n,
ale to po prostu wygląda trochę brzydki, zwłaszcza jeśli my, ludzie będą
narysować wskaźniki ze strzałkami cały czas, świat ma znormalizowane na tym zapisie strzałki
który robi dokładnie to samo.
Więc używać tylko -> notacji gdy coś po lewej stronie jest wskaźnik.
W przeciwnym razie, jeśli jest rzeczywista struktura, użyj. N.
A potem to: Dlaczego zainicjować newptr-> next NULL?
Nie chcemy wiszącym lewą rękę off koniec etapu.
Chcemy, skierowane w dół, co oznacza koniec tej listy
potencjalnie może być w tym węźle, więc lepiej upewnić się, że jest NULL.
A w ogóle, inicjowanie zmienne i danych członków i strukturach
coś jest po prostu dobra praktyka.
Wystarczy pozwolić śmieci istnieją i będą istnieć ogół dostaje w tarapatach
jeśli zapomnisz zrobić coś później.
>> Oto kilka przypadków. To również jest funkcja wkładka,
i pierwsze co mam sprawdzić, czy zmienna jest nazywana pierwszym,
że globalna zmienna jest NULL, co oznacza, że ​​nie jest związana lista.
Nie dodaje się żadnych liczb, więc to jest trywialne, aby wstawić ten numer bieżącego
na liście, po prostu dlatego, że należy na początku listy.
Tak to było, kiedy Anita została po prostu stoję tu sam, udając
nikt inny nie był tu na scenie, dopóki nie przydzielono węzła
to może ona zwiększyć rękę po raz pierwszy,
gdyby wszyscy przyszli na scenę po niej w poniedziałek.
Teraz tutaj jest to trochę sprawdzić, gdzie mam do powiedzenia jeśli nowy węzła wartość n
jest <wartość n w bieżącym węźle pierwszy
to oznacza, że ​​jest połączona lista, która się rozpoczęła.
Jest co najmniej jeden węzeł na liście, ale ten nowy facet
należy przed nim, więc musimy przenieść rzeczy wokół.
Innymi słowy, jeśli lista rozpoczął się tylko, powiedzmy,
tylko numer 17, to - faktycznie, możemy to zrobić bardziej wyraźnie.
Jeśli zaczniemy naszą historię ze wskaźnikiem tutaj nazywa pierwsze,
i początkowo to NULL, i wstawić numer 9,
nr 9 wyraźnie należy na początku na liście.
Warto więc udawać, że tylko malloced adres lub numer 9 i umieścić go tutaj.
Jeśli pierwsze 9 domyślnie pierwszy scenariusz dyskutowaliśmy tylko oznacza punkt Miejmy ten facet tutaj
zostawić to jako NULL; teraz mamy numer 9.
Następny numer chcemy wstawić jest 17.
17 należy tu, więc będziemy musieli zrobić jakiś logiczny Zaostrzenie przez to.
Więc zamiast tego, zanim to zrobimy, udawajmy, że chcemy wstawić numer 8.
>> Więc po prostu dla wygody, idę wyciągnąć tutaj.
Ale pamiętaj, malloc można go umieścić niemal wszędzie.
Ale na rysunku dobra, włożę go tutaj.
Więc udawać Właśnie przydzielono węzeł numer 8, jest to NULL domyślnie.
Co teraz się stanie? Kilka rzeczy.
Zrobiliśmy ten błąd w poniedziałek na scenie, gdzie aktualizacja wskaźnik jak ten,
potem zrobił to, a potem twierdził - mamy osierocony wszyscy inni na scenie.
Bo nie mogę się - kolejność operacji jest tu ważne,
bo teraz straciliśmy tego węzła 9, który jest po prostu rodzaj pływających w przestrzeni.
Więc to nie było właściwe podejście w poniedziałek.
Najpierw musisz zrobić coś innego.
Stan świata wygląda tak. Początkowo, 8 jest przeznaczone.
Jaki byłby lepszy sposób wkładania 8?
Zamiast aktualizować ten wskaźnik pierwszy, po prostu zaktualizować Ten tutaj zamiast.
Więc potrzebujemy linii kodu, który zamierza przekształcić ten znak null
do rzeczywistego wskaźnika, która jest skierowana na węźle 9,
i wtedy możemy bezpiecznie zmienić pierwszy punkt na tego faceta tutaj.
Teraz mamy listę, listę, z dwóch elementów.
I co to faktycznie wygląda jak tutaj?
Jeśli spojrzeć na kod, zauważysz, że zrobiłem dokładnie to.
Powiedziałem newptr, w tej historii, newptr wskazywał na tego faceta.
>> Więc pozwól mi wyciągnąć jeszcze jedną rzecz i należy mi zostało trochę więcej miejsca na to.
Więc wybacz maleńki rysunek.
Ten facet nazywa newptr.
To jest zmienna zadeklarowaliśmy kilka linijek wcześniej, w linii - tuż powyżej 25.
I to wskazuje na 8. Więc kiedy mówię newptr-> next, czyli udać się do struktury
który jest ich wskazał przez newptr, więc jesteśmy, tam.
Potem strzałka mówiąc dostać następne pole, a następnie = mówi umieścić jaką wartość tam?
Wartości, który był w pierwszej kolejności; jakie wartości było w pierwszej kolejności?
Pierwszy wskazywał na tym węźle, więc oznacza to powinien teraz wskazywać na tym węźle.
Innymi słowy, to, co wygląda choć śmieszne bałagan z mojego pisma,
co jest prosty pomysł właśnie przenoszenie tych strzałek wokół
przekłada się na kodzie z tylko tego jednego liniowca.
Przechowywania, co jest w pierwszy w następnym polu, a następnie zaktualizować co najpierw faktycznie jest.
Idziemy do przodu i do przodu przez niektóre z tych,
i patrzeć tylko na tym założeniu ogonowej teraz.
Załóżmy, że dostać się do punktu, gdzie uważam, że następne pole jakiegoś węzła jest NULL.
I w tym momencie w historii, szczegółowo, że jestem zapominając o
jest to, że wprowadziliśmy kolejny wskaźnik tutaj w linii 142, wskaźnik poprzednika.
Zasadniczo, w tym momencie w historii, gdy lista jest długa,
I rodzaju muszą chodzić z dwoma palcami, bo jeśli za daleko,
Pamiętam, że w liście single-length, nie można cofnąć.
Więc ten pomysł predptr jest mój lewy palec i newptr - nie newptr.
Kolejna wskazówka, że ​​to tu jest mój drugi palec, a ja jestem po prostu rodzaj spaceru listę.
To dlatego, że istnieje. Ale niech tylko za jeden z prostszych przypadkach tutaj.
Jeśli tego wskaźnika na następne pole jest NULL, co jest logiczną implikacją?
Jeśli przemierzając tę ​​listę i trafisz wskaźniku NULL?
Jesteś na końcu listy, a więc kod następnie dołącz ten jeden dodatkowy element
jest swego rodzaju intuicyjna weźmie tego węzła, którego następny wskaźnik jest NULL,
więc jest to obecnie NULL, i zmienić go, choć, być adres nowego węzła.
Więc jesteśmy po prostu rysunek w kodzie strzałkę, że zwrócił na scenie przez podniesienie czyjąś lewą dłoń.
>> I tak, że będę machać rękami na teraz,
tylko dlatego, że myślę, że łatwo się pogubić, gdy robimy to w tego typu środowiska,
sprawdza do wstawienia na listę w środku.
Ale tylko intuicyjnie, co musi się zdarzyć, jeśli chcesz dowiedzieć się,
gdzie niektóre numer należy w środku jest to trzeba chodzić
więcej niż jednym palcem, więcej niż jeden wskaźnik,
dowiedzieć się, gdzie należy, poprzez sprawdzenie jest element <obecnym,
> Prąd jeden, a jak już znajdziesz to miejsce,
następnie musisz zrobić ten rodzaj gry powłoki gdzie przenieść wskaźniki wokół bardzo ostrożnie.
A to odpowiedź, jeśli chcesz do rozumu przez to w domu na własną rękę,
sprowadza się tylko do tych dwóch linii kodu, ale aby z tych wierszy jest super ważne.
Bo jeśli spadnie czyjąś rękę i podnieść kogoś innego w niewłaściwej kolejności,
ponownie, może skończyć się osierocenia listę.
Podsumowując bardziej konceptualnie, wstawiania na ogonie jest stosunkowo proste.
Wprowadzenie na głowę jest stosunkowo proste,
ale trzeba zaktualizować dodatkowy wskaźnik ten czas
wycisnąć numer 5 na liście tutaj
a następnie umieszczenie w środku wymaga jeszcze więcej wysiłku,
bardzo ostrożnie wstawić numer 20 w odpowiednim miejscu,
która znajduje się pomiędzy 17 i 22.
Więc trzeba zrobić coś jak mają nowego węzła 20 pkt do 22,
, a następnie, który węzeł jest wskaźnik musi być aktualizowany ostatni?
Jest 17, faktycznie go wstawić.
Więc jeszcze raz, ja wstrzymuje rzeczywisty kod dla tej konkretnej realizacji.
>> Na pierwszy rzut oka, że ​​to trochę przytłaczające, ale tak naprawde to pętla nieskończona
który jest zapętlenie, pętli, pętli, pętli, a łamiąc jak najszybciej trafić wskaźniku NULL,
w którym momencie można zrobić wymaganą wstawiania.
To zatem jest reprezentatywna związany kod wstawiania lista.
To był rodzaj partii, i jest to jak mamy rozwiązać jeden problem,
ale my wprowadziliśmy całą drugą. Szczerze mówiąc, spędziliśmy cały ten czas
na duże O i Ω i czasu pracy, starając się rozwiązać problemy szybciej,
i tutaj robimy duży krok do tyłu, to jest.
I jeszcze, jeśli celem jest do przechowywania danych,
czuje się jak Święty Graal, jak powiedział w poniedziałek, że naprawdę
do przechowywania rzeczy natychmiast.
>> Istotnie, przypuśćmy, że zrobiliśmy odłożyć połączonej listy na chwilę
a my zamiast wprowadził pojęcie tabeli.
I niech tylko myśleć o stole na chwilę jako tablicę.
Ta tablica i ta sprawa ma tu jakieś 26 elementów, 0 do 25,
i załóżmy, że trzeba jakiś kawałek składowania nazwami:
Alicja i Bob i Charlie i jak.
I trzeba trochę strukturę danych do przechowywania tych nazw.
Cóż, można użyć coś jak połączonej listy
i można było iść listę wkładanie Alice przed Bob i Charlie po Boba i tak dalej.
A w rzeczywistości, jeśli chcesz zobaczyć kod takiego jak bok,
Wiadomo, że w list2.h, robimy dokładnie to.
Nie przechodzi przez ten kod, ale jest to wariant pierwszego przykładu
która wprowadza jeden inny struct widzieliśmy przed zwanego studenta,
a co to właściwie przechowywane w połączonej listy jest wskaźnikiem do struktury studentów
niż proste trochę całkowitą, n.
Więc sobie sprawę, że znajduje się tam kod, który obejmuje rzeczywiste ciągi,
ale jeśli celem w ręku naprawdę teraz jest rozwiązanie problemu wydajności,
Czy nie byłoby miło, jeśli mamy dany obiekt o nazwie Alice,
chcemy umieścić ją w odpowiednim miejscu w strukturze danych,
czuje się, że to będzie naprawdę miło po prostu umieścić Alice,
, którego nazwa zaczyna się w pierwszym miejscu.
I Bob, którego nazwa zaczyna się na literę B, w drugiej lokalizacji.
Z tablicy lub zacznijmy nazywając to tabeli, tabeli mieszania na to,
możemy zrobić dokładnie to. Jeśli podano nazwę jak Alice,
łańcuch jak Alicja, gdzie można umieścić A-L-i-C-E?
Potrzebujemy hueristic. Potrzebujemy funkcji, aby robić jakieś wejście jak Alicja
i odesłać odpowiedź, "Put Alice w tym miejscu."
I ta funkcja, ta czarna skrzynka, będzie się nazywać funkcją skrótu.
>> Funkcja skrótu jest coś, co ma wejście, jak "Alice",
i wraca do ciebie, zazwyczaj w jakiś numeryczny lokalizacja struktury danych, w którym Alice należy.
W tym przypadku, funkcja mieszania nasz powinny być stosunkowo proste.
Nasza funkcja skrótu powinna powiedzieć, jeśli są podane "Alice", który znak powinien mnie obchodzi?
Pierwszy. Więc patrzę na [0], a potem powiedzieć, że jeśli [0] postać jest, zwraca liczbę 0.
Jeśli jest to B, powrót 1. Jeśli jest to C, zwróci 2, i tak dalej.
Wszystkie 0 index, i że pozwoli mi wstawić Alice, a potem Bob i potem Charlie i tak dalej
do tej struktury danych. Ale jest problem.
Co jeśli Anita przychodzi ponownie?
Gdzie stawiamy Anita? Jej imię, też zaczyna się na literę A,
i wydaje się, zrobiliśmy jeszcze większy bałagan tym problemem.
Mamy teraz natychmiastowe umieszczenie, stały czas wstawiania, w strukturze danych
zamiast gorszego przypadku liniowym,
ale co możemy zrobić z Anitą w tym przypadku?
Jakie są dwie opcje, naprawdę? Tak?
[Odpowiedź Student, niezrozumiały] Okay, więc możemy mieć inny wymiar.
To dobrze. Tak więc możemy budować rzeczy w 3D jak rozmawialiśmy werbalnie w poniedziałek.
Możemy dodać kolejną dostęp tutaj, ale przypuszczam, że nie, staram się zachować to proste.
Cały celem jest, aby mieć natychmiastowy dostęp w czasie stałym,
więc to dodanie zbyt dużej złożoności.
Jakie są inne opcje, gdy próbujesz wstawić Anitę do tej struktury danych? Tak?
[Odpowiedź Student, niezrozumiały] Dobra. Więc możemy przenieść wszystkich innych w dół,
jak Charlie trąca dół Bob i Alice, a następnie kładziemy Anita gdzie ona naprawdę chce być.
>> Oczywiście, teraz, jest efektem ubocznym tego.
Ta struktura danych prawdopodobnie jest przydatne nie dlatego, że chcemy wstawić ludziom raz
ale dlatego, że chcemy, aby sprawdzić, czy są tam później
jeśli chcemy wydrukować wszystkie nazwy w strukturze danych.
Mamy zamiar zrobić coś z tymi danymi w końcu.
Więc teraz mamy rodzaj skręcane na Alice, która już nie jest, gdzie ona ma być.
Ani Bob ani Charlie.
Więc może to nie jest taki dobry pomysł.
Ale rzeczywiście, to jest jedna z opcji. Możemy przenieść każdego w dół,
lub cholery, Anita przyszedł późno do gry, dlaczego nie możemy po prostu umieścić Anita
nie tutaj, nie tutaj, nie tutaj, po prostu umieścić ją trochę niżej na liście.
Ale wtedy ten problem zaczyna przechodzą ponownie.
Możesz być w stanie znaleźć Alice natychmiast, na podstawie jej imienia.
I Bob natychmiast, a Charlie. Ale potem szukać Anita,
i widzisz, hmm, Alice jest w drodze.
Cóż, pozwól mi sprawdzić poniżej Alice. Bob nie jest Anita.
Charlie nie jest Anita. Och, jest Anita.
A jeśli nadal tego pociągu logiki całą drogę,
, co jest najgorszym przypadku czas jazdy na znalezienie lub włożeniu Anitę do tej nowej struktury danych?
To jest O (n), prawda?
Bo w najgorszym przypadku, nie Alice, Bob, Charlie. . .
w dół do niejakiego "Y", więc jest tylko jedno miejsce w lewo.
Na szczęście, nie mamy jeden o nazwie "Z", więc umieścić Anitę na samym dole.
>> Tak naprawdę nie rozwiązuje tego problemu.
Więc może trzeba wprowadzić ten trzeci wymiar.
I okazuje się, jeśli nie wprowadzi tego trzeciego wymiaru,
nie możemy zrobić to doskonale, ale Święty Graal ma być coraz
stała w czasie wkładania i dynamiczne wstawki, tak aby
nie mamy do hard-code tablica wielkości 26.
Możemy wstawić tyle nazw, jak chcemy, ale weźmy naszą 5-minutową przerwę tutaj
a następnie zrobić prawidłowo.
Dobrze. Ustawić się dość sztucznie historię tam
wybierając Alice, a potem Bob, a potem Charlie i następnie Anita,
którego nazwa została oczywiście będzie kolidować z Alice.
Ale pytanie skończyło w poniedziałek jest tylko jak to jest prawdopodobne
że można dostać tego rodzaju kolizji? Innymi słowy,
jeśli zaczniemy używać tego tabelarycznego strukturę, która jest tak naprawdę tablicą,
w tym przypadku, 26 miejsc,
co jeśli nasze środki są zamiast równomiernie rozłożone?
To nie jest sztucznie Alicja i Bob i Charlie i David, i tak dalej alfabetycznie
to jest równomiernie rozłożony do Z.
>> Może po prostu miał szczęście, a my nie będziemy mieć dwa męskie lub dwa przez B
z prawdopodobieństwem bardzo wysokim poziomie, ale jak ktoś zauważył,
Jeśli się tego problemu i uogólnione nie 0 do 25
, ale, na przykład, 0 do 364 lub 65, często wiele dni w typowych roku
i zapytał, na pytanie: "Jakie jest prawdopodobieństwo, że dwóch z nas w tym pokoju mają urodziny tego samego?"
Innymi słowy, co jest prawdopodobieństwo, że dwóch z nas ma imię zaczynając?
Rodzaj pytanie jest taka sama, ale przestrzeni adresowej,
miejsce to search, jest większe w przypadku urodzin,
ponieważ mamy tak wiele więcej dni w roku niż liter w alfabecie.
Jakie jest prawdopodobieństwo kolizji?
Cóż, możemy myśleć o tym by dowiedzieć się matematyki w przeciwną stronę.
Jakie jest prawdopodobieństwo bez kolizji?
Cóż, to wyrażenie tutaj mówi, że to, co jest prawdopodobieństwo
jeśli jest tylko jedna osoba w tym pokoju, że mają wyjątkową urodziny?
Jest w 100%. Bo jeśli jest tylko jedna osoba w pokoju,
jego lub jej urodzin może być dowolny z 365 dni z roku.
Więc 365/365 opcji daje mi wartość 1.
Więc prawdopodobieństwo mowa w tej chwili jest tylko 1.
Ale jeśli jest druga osoba w pokoju,
Jakie jest prawdopodobieństwo, że ich urodziny jest inny?
Jest tylko 364 możliwych dni, pomijając lata przestępne,
ich urodzin nie zderzają się z innych osób.
Więc 364/365. Jeśli osoba trzecia jest w, to 363/365, i tak dalej.
Więc trzymamy pomnożenie razem te frakcje, które są coraz mniejsze,
dowiedzieć się, jakie jest prawdopodobieństwo, że każdy z nas posiada unikalne urodziny?
Ale wtedy możemy, oczywiście, po prostu weź tę odpowiedź i przerzucić go wokół
i zrobić 1 minus to wszystko, ekspresyjny my ostatecznie dostać
jeśli pamiętasz z tyłu książek matematycznych, to wygląda trochę coś takiego,
które jest znacznie łatwiej interpretować graficznie.
A ta grafika ma tu na osi x liczbę urodzin,
lub liczba osób z urodzin, a na osi Y jest prawdopodobieństwo meczu.
A co to jest o to, że jeśli masz, powiedzmy, nawet,
Wybierzmy coś jak 22, 23 lat.
Jeśli jest 22 lub 23 osób w pokoju,
prawdopodobieństwo, że dwa z tych bardzo niewielu ludzi będzie mieć urodziny tego samego
jest rzeczywiście bardzo wysokie, kombinatorycznie.
50% prawdopodobieństwo, że w klasie liczącej zaledwie 22 osób, w seminarium, praktycznie
2 z tych osób będzie mieć taki sam urodziny.
Ponieważ istnieje tak wiele sposobów, w którym można mieć urodziny tego samego.
Jeszcze gorzej, jeśli spojrzeć na prawej stronie wykresu,
do czasu masz klasę z 58 uczniów w tym,
prawdopodobieństwo 2 osób mających urodziny jest super, super wysoka, prawie 100%.
Teraz, to jest coś w rodzaju zabawy rzeczywistości o prawdziwym życiu.
>> Ale implikacje, teraz, struktur danych i przechowywania informacji
Oznacza to, że tylko przy założeniu, że masz ładne, czyste, równomierny rozkład danych
i masz na tyle duże, aby dopasować tablicy kilka rzeczy
nie znaczy, że będziemy się ludzi w unikalnych lokalizacjach.
Będziesz mieć kolizji. Więc to pojęcie mieszania, jak to się nazywa,
biorąc wejście jak "Alice" i masuje go w jakiś sposób
a następnie powrót odpowiedź jak 0 lub 1 lub 2.
Wracając jakieś wyjście z tej funkcji jest nękane przez to prawdopodobieństwo kolizji.
Więc jak możemy obsłużyć te kolizje?
Cóż, w jednym przypadku możemy mieć pojęcia, że ​​został zaproponowany.
Możemy po prostu przenieść każdego w dół, czy może, trochę więcej po prostu,
niż każdy inny ruch, po prostu przenieść Anitę do końca dostępnego miejsca.
Więc jeśli Alice jest w 0, Bob jest w 1, Charlie jest w 2,
my po prostu umieścić Anitę w miejscu 3.
I to jest technika, w strukturach danych nazywa adresowania liniowego.
Liniowy, ponieważ jesteś tylko w odległości tej linii, i jesteś rodzaju sondowania
dostępnych miejsc w strukturze danych.
Oczywiście, nakładanych w O (n).
Jeśli struktura danych jest naprawdę pełna, jest 25 osób, w nim już
a następnie Anita przychodzi, ona kończy się na to, co będzie lokalizacja Z, i to jest w porządku.
Ona nadal pasuje, i możemy ją znaleźć później.
>> Ale to było sprzeczne z celem przyspieszenia rzeczy.
Więc co, jeśli zamiast tego wprowadził trzeci wymiar?
Ta technika jest powszechnie nazywany oddzielny łańcuchowym lub posiadanie łańcuchów.
A co teraz jest hash table to tabelaryczne struktura,
Twoja tabela jest tylko tablica wskaźników.
Ale co te wskaźniki wskazują na to wiecie co?
Połączonej listy. Więc co, jeśli weźmiemy najlepsze z obu tych światów?
Używamy tablice dla początkowych indeksów
do struktury danych, dzięki czemu możemy od razu przejść do [0] [1], [30], lub tak dalej,
ale tak, że mamy pewną elastyczność i możemy dopasować Anita i Alice i Adam
oraz wszelkie inne imię,
my zamiast pozwolić drugiej osi rosnąć dowolnie.
I wreszcie, jak w poniedziałek, że ma zdolność wyrazu z połączonej listy.
Możemy rozwijać strukturę danych arbitralnie.
Alternatywnie, można po prostu zrobić ogromny 2-wymiarowej tablicy,
ale że będzie okropna sytuacja, gdy jeden z wierszy w tablicy 2-wymiarowej
nie jest wystarczająco duży dla dodatkowej osoby, której nazwisko dzieje zacząć A.
Boże broń mamy do realokacji ogromny 2-wymiarową strukturę
tylko dlatego, że jest tak wielu ludzi, nazwanych
zwłaszcza gdy jest tak mało ludzi nazwanych coś Z.
To jest po prostu będzie bardzo rzadki struktura danych.
Więc to nie jest idealne w jakikolwiek sposób, ale teraz przynajmniej mają możliwość
aby natychmiast znaleźć gdzie Alice lub Anita należy,
co najmniej w odniesieniu do osi pionowej,
i wtedy tylko zdecydować, gdzie umieścić Anita lub Alice w tej połączonej listy.
Jeśli nie dbamy o sortowaniu rzeczy, jak szybko możemy wstawić Alicję w strukturze jak ta?
To jest stała czasowa. Mamy indeks do [0], a jeśli nikt nie jest tam,
Alicja idzie na początku związaną listy.
Ale to nie jest wielka sprawa. Bo jeśli Anita potem przychodzi
pewna liczba kroków później, skąd Anita należą?
Cóż, [0]. OOP. Alicja jest już w tym związane listy.
>> Ale jeśli nie dbamy o sortowaniu te nazwy,
możemy po prostu przejść nad, Alice insert Anita, ale nawet to jest stała czasowa.
Nawet jeśli jest Alice i Adam i wszystkie te inne A imiona,
To naprawdę nie jest przesunięcie ich fizycznie. Dlaczego?
Bo po prostu nie tutaj z połączonej listy, kto wie były węzły te są tak?
Wszystko co musisz zrobić, to przenieść bułkę tartą.
Przesuń strzałki wokół, nie trzeba fizycznie przenieść żadnych danych wokół.
Więc możemy wstawić Anita, w tym przypadku, natychmiast. Stała czas.
Więc mamy stałej czasowej i stałej odnośnika czasie wkładanie kogoś takiego jak Anita.
Ale rodzaj upraszczasz świat.
Co jeśli później chcesz znaleźć Alice?
Ile kroków jest to, że zajmie?
[Odpowiedź Student, niezrozumiały]
Dokładnie. Liczba osób, przed Alicją w połączonej listy.
Więc to nie jest całkiem doskonały, bo nasza struktura danych, ponownie, ma ten pionowy dostęp
i wtedy ma te połączone życzeń wiszące - faktycznie, niech nie rysować tablicy.
Ma te związane Listy zawieszony z tego, że wygląda trochę coś takiego.
Ale problemem jest to, czy Alice i Adam i wszystkie te inne nazwy A
skończyć się coraz więcej tam,
znalezienie kogoś może skończyć biorąc kilka kroków,
bcause trzeba przemierzać listę,
które jest liniowa praca.
Tak bardzo, to czas jest ostatecznie wstawiania O (n), gdzie n jest liczbą elementów listy.
Podzielone przez, powiedzmy dowolnie nazwać m, gdzie m jest liczbą połączonych list
, że ma w osi pionowej.
Innymi słowy, jeśli rzeczywiście przyjąć równomierne nazw,
całkowicie nierealne. Jest oczywiście bardziej niektórych literami od innych.
>> Ale jeśli założymy na moment dystrybucji jednolity,
i mamy n osób, a ogółem m Łączna łańcuchy
nas dostępne, to długość każdego z tych łańcuchów
raczej tylko będzie łączna, podzielone przez n liczbę łańcuchów.
Więc n / m. Ale tu, gdzie możemy być wszystko matematycznie sprytny.
m jest stała, bo jest ustalona liczba tych.
Masz zamiar zadeklarować tablicę na początku,
i nie jesteśmy rozmiaru pionową. Zgodnie z definicją, która pozostaje stała.
To tylko oś pozioma, że ​​tak powiem, to się zmienia.
Więc technicznie, to jest stała. Więc teraz, czas wstawiania
jest dość dużo, O (n).
Tak, że nie czuje się aż tak dużo lepiej.
Ale co prawda, tutaj? Cóż, przez cały ten czas, na tydzień,
byliśmy mówiąc O (n ²). O (n), 2 x N ², - N, podzielona przez 2. . . ech.
To jest po prostu n ². Ale teraz, w tej części semestru,
możemy zacząć mówić o prawdziwym świecie ponownie.
I N / m jest absolutnie szybciej niż sama tylko n.
Jeśli masz tysiąc nazwisk i złamać je na kilka wiader
tak, że masz tylko dziesięć nazwisk w każdej z tych łańcuchów,
absolutnie szukają dziesięć rzeczy będzie szybszy niż tysiąc rzeczy.
I tak jeden z najbliższych zbiorów problemowych będzie wyzwanie
myśleć o tym dokładnie, że nawet jeśli tak,
asymptotycznie i matematycznie, to nadal jest tylko liniowe,
który ssie w ogóle, gdy próbuje znaleźć rzeczy.
W rzeczywistości, to będzie szybciej niż
z powodu tego dzielnik.
A więc znowu będzie to kompromis
i ten konflikt między teorią a rzeczywistością,
i jeden z haczyków rozpocznie obracanie w tym momencie w połowie
jest bardziej rzeczywistości jeden jak rodzaj przygotowania do końca semster się,
jak wprowadzenie w świat programowania WWW,
gdzie naprawdę wydajność będzie się liczyć, ponieważ użytkownicy będą
zaczynam czuć i docenić błędne decyzje projektowe.
>> Więc w jaki sposób przejść o implementowaniu linked - hash tabeli z 31 elementów?
I poprzedni przykład był arbitralnie o urodzinach.
Jeśli ktoś ma urodziny 01 stycznia i 01 lutego, będziemy je w tym wiadrze.
Jeśli to 2 stycznia, 2 lutego, 2 marca, będziemy je w tym wiadrze.
Dlatego to było 31. Jak można zadeklarować tabeli mieszania?
To może być całkiem proste, node * Tabela jest mój arbitralny dla niego nazwy, [31].
To daje mi 31 wskaźniki do węzłów
i to pozwala mi mieć 31 odnośniki do powiązanych list
nawet jeśli te łańcuchy są początkowo NULL.
Czego chcę postawić, jeśli chcę zapisać "Alice", "Bob", "Charlie"?
Cóż, musimy otoczyć te rzeczy w strukturze
ponieważ trzeba Alice wskazać Boba wskazać Charlie, i tak dalej.
Nie możemy po prostu nazwy sam, więc mogłem stworzyć nową strukturę o nazwie węzła tutaj.
>> Jaki jest rzeczywisty węzeł? Co to jest węzeł w nowej listy powiązane?
Pierwszą rzeczą, o nazwie słowo jest nazwisko osoby.
DŁUGOŚĆ przypuszczalnie odnosi się do maksymalnej długości ludzkiego imienia,
co, który jest, 20, 30, 40 w postaci szalonych przypadkach narożnych
i +1 to za co? To jest po prostu dodatkowy znak NULL, \ 0.
Więc to jest węzeł pakowania "coś" wewnątrz siebie,
ale również deklaruje wskaźnik o nazwie obok
tak, że możemy łańcuch Alice do Boba do Charliego i tak dalej.
Może mieć wartość NULL, ale nie musi być.
Wszelkie pytania dotyczące tych tabel hash? Tak?
[Student pyta pytanie, niezrozumiały] array - dobre pytanie.
Dlaczego jest to char słowo w tablicy, a nie tylko char *?
W tym przykładzie nieco arbitralny, nie chce mieć do uciekania
malloc dla każdego z oryginalnymi nazwami.
Chciałem zadeklarować maksymalną ilość pamięci dla ciągu
abym mógł skopiować do struktury Alice \ 0 i nie mieć do czynienia z malloc, wolnych i jak.
Ale mogę to zrobić, jeśli chcę być bardziej świadomi wykorzystania przestrzeni. Dobre pytanie.
Więc spróbujmy generalizować z dala od tego
i skupić resztę dzisiaj na strukturach danych ogólnie
i inne problemy, które można rozwiązać za pomocą tych samych podstaw
chociaż struktury danych może się różnić w swoich szczegółowych.
>> Okazuje się w informatyce, drzewa są bardzo powszechne.
A może myślisz o jakimś drzewie jak drzewa genealogicznego,
gdzie jest jakieś korzenie, niektóre matriarch lub patriarcha,
babcia lub dziadek lub wcześniej z powrotem,
pod które mama i tata lub różne rodzeństwo lub podobne.
Tak więc struktura drzewa ma węzły i ma dzieci,
zazwyczaj 0 lub więcej dzieci, dla każdego węzła.
A niektóre z żargonu, który widzisz na obrazku tutaj
jest każdy z tych małych dzieci lub wnuków na krawędziach
którzy nie mają strzałki emanujące od nich,
są to tzw liście i każdy w środku
jest wewnętrzny węzeł, można nazwać to coś wzdłuż tych linii.
Jednak struktura ta jest dość powszechne. Ten jest trochę przypadkowe.
Mamy jedno dziecko, po lewej stronie, mamy troje dzieci, po prawej stronie,
dwoje dzieci, na dole po lewej stronie.
Tak więc możemy mieć różne wielkości drzewa, ale jeśli zaczniemy do ujednolicenia rzeczy,
i może pamiętacie to z filmu Patryka binarnego wyszukiwania z ostatnich krótki
online, binary search nie musi być realizowane z tablicy
lub kawałki papieru na tablicy.
Załóżmy, że chcesz przechowywać liczb w bardziej wyrafinowane struktury danych.
Można utworzyć drzewo takiego.
Można mieć węzeł zadeklarowanych w C, i że węzeł może mieć co najmniej dwa elementy w jej wnętrzu.
Jednym z nich jest numer, który chcesz zapisać, a drugi jest - dobrze, potrzebujemy jeszcze jednego.
Drugi to jego dzieci.
Tak tu jest inna struktura danych. Tym razem, jest zdefiniowany jako węzła przechowywania liczbę n
a następnie dwa wskaźniki, lewy i prawy, dziecko, dziecko.
I nie są arbitralne. Co ciekawe o tym drzewie?
>> Co znajduje się wzór, w jaki sposób mamy określić ten limit lub jak Patrick położył go w swoim filmie?
Jest raczej oczywiste, że istnieje pewne sortowania dzieje,
ale co to jest prosta zasada? Tak?
[Odpowiedź Student, niezrozumiały]
Perfect. Jeśli spojrzeć na to, można zobaczyć małe numery na lewej stronie,
duże cyfry na lewo, ale to jest prawdziwe dla każdego węzła.
Dla każdego węzła, jego lewa dziecko poniżej niego, a jego prawo dziecko powyżej niego.
Co to oznacza to, jeśli chcę szukać tej strukturze danych, powiedzmy, numer 44,
Muszę zacząć od podstaw, bo jak z tych wszystkich bardziej złożonych struktur danych teraz,
mamy tylko wskaźnik do jednej rzeczy, początek.
I w tym przypadku, jest to początek główny. Nie lewy koniec jest,
to jest korzeń tej struktury. Widzę tu jest 55, a ja szukam 44.
W jakim kierunku chcę iść?
Cóż, chcę iść na lewo, bo oczywiście, na prawo będzie zbyt duży.
Więc tutaj odnotować, że jesteś rodzaju koncepcyjnie rąbanie drzewa w pół
bo nigdy nie będziemy w dół do prawej strony.
Więc teraz przejść od 55 do 33. Jest zbyt mały liczby.
Szukam 44, ale teraz wiem, czy 44 jest w tym drzewie, mogę oczywiście prawo.
Więc jeszcze raz, jestem cięcia drzewa w pół.
To jest prawie identyczne koncepcyjnie do książki telefonicznej.
To jest identyczna, co zrobiliśmy z papierami na tablicy,
ale jest to bardziej skomplikowane struktury, która pozwala nam na faktycznie
to dziel i rządź o konstrukcji algorytmu,
i faktycznie, przemierzając strukturę tak - ups.
Przejazd strukturę jak ten, gdzie jest to tylko "iść tą drogą lub przejść w ten sposób"
Oznacza to, cały ten kod pochyliła swój umysł najpierw podczas jej wdrażania w sekcji
lub przechodzenia przez nią w domu, dla binarnego wyszukiwania, używając rekursji lub iteracji,
to jest ból w szyi. Znajdź środkowy element, a następnie wykonać zaokrąglenie w górę lub w dół.
>> Jest piękno na to, ponieważ możemy teraz używać rekursji ponownie
ale o wiele bardziej czysto. Rzeczywiście, jeśli jesteś pod numerem 55, a chcesz znaleźć 44,
idziesz w lewo w tym przypadku, to co robisz? Uruchomić dokładnie ten sam algorytm.
Sprawdzić wartość węzła, a następnie przejść w lewo lub w prawo.
Następnie sprawdzić wartość węzła, przejdź w lewo lub w prawo.
Jest to doskonale nadaje się do rekurencji.
Więc nawet jeśli w przeszłości zrobiliśmy kilka dość dowolne przykłady obejmujące rekursji
że nie trzeba być rekurencyjne, z Konstrukcje danych,
szczególnie drzewa, jest to idealne zastosowanie tego pomysłu biorąc wątpliwości
kurczy, a następnie rozwiązywanie tego samego rodzaju, ale mniejsze, program.
>> Więc nie ma innej struktury danych, które możemy wprowadzić.
Ten przeznaczony jest na pierwszy rzut oka wyglądają tajemnicze, ale to jest niesamowite.
Więc jest to struktura danych o nazwie trie, trie, która jest dziedziczona z wyszukiwania tekstu,
który nie jest wymawiane ponowić-Val, ale to, co świat nazywa te rzeczy. Próbuje. T-i-R-E.
Jest to struktura, drzewo, pewnego rodzaju, ale każdego z węzłów w Trie
Wydaje się, że co? I to jest nieco mylące, ponieważ jest to rodzaj skróconej.
Ale wygląda na to, każdy węzeł w Trie jest rzeczywiście tablicą.
I mimo, że autor tego schematu nie wykazał go,
w tym przypadku, to trie to struktura danych, którego celem w życiu jest do przechowywania słowa
jak l-i-C-E-lub o-B-B.
A sposób, w jaki te dane przechowuje Alicja i Bob i Charlie i Anita i tak dalej
jest wykorzystuje tablicę której przechowywać Alicję w Trie,
zaczniemy od korzenia, który wygląda jak tablica,
i to zostało napisane w notacji skróconej.
Autor pomija abcdefg, ponieważ nie było nazwiska z tym.
Oni tylko pokazał M i P i T, ale w tym przypadku,
Przejdźmy od Alice i Bob i Charlie do niektórych nazwisk, które są tutaj.
Maxwell jest rzeczywiście w tym schemacie.
Jak więc magazyn autor M--x-w-e-l-l?
On lub ona rozpocząć od korzenia, i udał się do [M], więc mniej więcej 13, 13 miejsce w tablicy.
Następnie stamtąd, jest wskaźnik.
Pointer prowadzi do innej tablicy.
Stamtąd autor indeksowane do tej tablicy w miejscu A, jak pokazano tam na górze po lewej stronie,
a następnie on lub ona następnie, że wskaźnik do innej tablicy,
i udał się do wskaźnika w miejscu X.
Potem w następnym położeniu W tablicy, E, L, L, i tak dalej,
i wreszcie, niech faktycznie spróbować umieścić zdjęcie tego.
Co robi węzeł wygląda w kodzie?
Węzeł w Trie zawiera tablicę wskaźników do innych węzłów.
Ale jest też, że musi być jakaś wartość logiczna, przynajmniej w tej implementacji.
Tak się nazywają to is_word. Dlaczego?
Bo kiedy wstawiasz Maxwell, nie jesteś włożeniem
nic do tej struktury danych.
Nie piszesz M. nie piszesz X.
Wszystko co robisz jest po wskazówki.
Wskaźnik, który reprezentuje m, to wskaźnik, który reprezentuje,
Następnie wskaźnik, który reprezentuje X, a następnie W, E, L, L,
ale to, co trzeba zrobić, w końcu to rodzaj przejść, sprawdzić, dotarłem tej lokalizacji.
Nie było słowa, które kończy się tutaj w strukturze danych.
>> Więc co trie naprawdę wypełnione i autor wybrał do reprezentowania
te terminuses z niewielką trójkątów.
To po prostu oznacza, że ​​fakt ten trójkąt jest tutaj, to wartość logiczna true
Oznacza to, jeśli pójdziesz tyłem w drzewo,
co oznacza, że ​​słowo o nazwie Maxwell jest w tym.
Lecz słowo foo, np.
nie jest w drzewie, bo jeśli zaczynają się korzenia tu na górze,
Nie ma wskaźnik f, nie wskaźnik o, nie wskaźnik o. Foo nie nazwa tego słownika jest.
Ale w przeciwieństwie, Turing, U-T-I-R-N-G. Znowu, nie przechowuj T lub U lub R lub I lub N lub G.
Ale zrobiłem sklep w tej struktury danych wartość prawdziwej drogi w tym miejscu węzła - w drzewie
poprzez ustawienie tej wartości is_word logiczną true.
Więc trie jest rodzaj tej bardzo ciekawej strukturze meta
jeżeli nie jesteś naprawdę przechowywania samych słów dla tego rodzaju słownika.
Aby być jasne, jesteś po prostu przechowywanie tak lub nie, nie jest to słowo, które kończy się tutaj.
>> Teraz, co jest implikacja?
Jeśli masz 150.000 słowa w słowniku, który próbujesz zapisać w pamięci
używając coś jak połączonej listy,
będziesz mieć 150.000 węzły w połączonej listy.
I znalezienie jednego z tych słów alfabetycznie może potrwać O (n) czasu.
Czas liniowy. Ale w tym przypadku o Trie,
co czas pracy na znalezienie słowa?
Okazuje się, że piękno jest to, że nawet jeśli masz 149.999 słowa już w tym słowniku,
wykonanego z tej struktury danych,
ile czasu potrzeba, aby znaleźć lub wstawić jeszcze jedną osobę do, że tak jak Alice, Alice?
Cóż, to tylko 5, może 6 kroków do charakteru spływu.
Ponieważ presense innych nazw w strukturze
nie dostać w sposób wkładania Alice.
Ponadto uzyskanie Alice raz jest 150.000 słów w tym słowniku
nie wchodzić w drogę znalezienia Alice w ogóle,
bo Alice jest. . . . . tutaj, ponieważ uważam, że wartość logiczną.
A jeśli nie jest logiczna prawda, Alice nie jest w tej strukturze danych słów.
Innymi słowy, czas pracy znalezienia rzeczy i wkładając rzeczy do tego nowego
Struktura danych Trie jest O z - to nie jest n.
Ponieważ presense 150.000 ludzi nie ma wpływu na Alice wydaje.
Więc nazwijmy to k, gdzie k jest maksymalna długość słowa w języku angielskim
które jest zazwyczaj nie więcej niż 20-coś znaków.
Tak k jest stałą. Więc Święty Graal wydaje się, znalazłem teraz
jest to, że z trie stałą czasową, wkładki, do wyszukiwania, na delecji.
Ponieważ liczba rzeczy już struktury,
, które nie są jeszcze tam fizycznie. Ponownie, oni jakoś zaznaczone, tak lub nie,
nie ma wpływu na jej przyszłego czasu pracy.
>> Ale tam musi być jakiś haczyk, w przeciwnym razie nie mielibyśmy tyle czasu zmarnowane
na wszystkich tych struktur innych danych po prostu się w końcu dostać do tajnego jeden, który jest niesamowity.
Więc co mamy płacić cenę, aby osiągnąć tę wielkość tutaj? Space.
Ta rzecz jest ogromny. I dlatego, że autor
nie przedstawił go tutaj zauważyć, że wszystkie te rzeczy, które wyglądają jak tablice,
on nie wyciągnął resztę drzewa, reszta Trie,
ponieważ są one nie tylko istotne dla historii.
Ale wszystkie te węzły są bardzo szerokie, a każdy węzeł w drzewie zajmuje
26 lub faktycznie, może być 27 znaków, ponieważ w tym przypadku byłem w tym miejsca dla apostrofu
tak, że możemy mieć apostrophized słowa.
W tym przypadku, są szerokie tablice. Więc nawet jeśli nie są one picutured,
ta zajmuje ogromną ilość pamięci RAM.
Które mogą być w porządku, especilly w nowoczesnym sprzęcie,
ale jest to kompromis. Mamy mniej czasu, by spędzać więcej miejsca.
Więc gdzie jest to wszystko idzie?
Cóż, zrobić - zobaczymy tutaj.
Zróbmy skok do tego faceta tutaj.
>> Wierzcie lub nie, tak zabawne, jak C był już od jakiegoś czasu,
docieramy do punktu w semestrze, gdzie jest czas na przejście do rzeczy bardziej nowoczesne.
Rzeczy na wyższym poziomie. I mimo, że przez kilka następnych tygodni
będziemy nadal, aby zanurzyć się w świecie wskaźników i zarządzanie pamięcią
aby uzyskać komfort, który możemy następnie budować na,
rozgrywka jest ostatecznie do wprowadzenia, jak na ironię, nie ten język.
Spędzimy, jak 10 minut rozmowy na temat języka HTML.
Wszystkie HTML jest to język znaczników, a co język znaczników jest
Jest to cykl otwartych uchwytów i wsporników zamkniętych, które mówią, "aby ten bold"
"Make to kursywa" make to na środku. "
To nie wszystko, co intelektualnie ciekawa, ale jest to bardzo przydatne.
I to jest na pewno wszechobecne w tych dniach.
Ale co jest potężne o świecie HTML i programowania WWW bardziej ogólnie,
jest budowanie dynamicznych rzeczy, pisania kodu w językach takich jak PHP lub Python lub Ruby lub Java lub C #.
Naprawdę, bez względu na język z wyboru jest i generowania HTML dynamicznie.
Generowanie coś o nazwie CSS dynamicznie.
Kaskadowe arkusze stylów, która jest także o estetyce.
A więc nawet jeśli dzisiaj, jeśli pójdę do jakiejś witryny, jak znanego Google.com,
i idę zobaczyć, Developer, pokaż źródło, które może zrobiłeś wcześniej,
ale się do widoku Source, to rzeczy prawdopodobnie wygląda dość zagadkowych.
Ale to jest podstawowy kod, który implementuje Google.com.
Na przednim końcu. I właściwie to wszystko jest puszysty stuff estetyka.
To jest CSS tutaj. Jeśli będę się przesuwać w dół będziemy trochę kolorami rzeczy.
To jest HTML. Kod Google wygląda jak bałagan, ale jeśli faktycznie otwarcie innego okna,
widzimy pewną strukturę tego.
Jeśli otworzyć tę górę, tutaj odnotować, że to trochę bardziej czytelne.
Idziemy zobaczyć niedługo ten tag, [słowo] jest tag,
HTML, głowy, ciała, div, skrypt, obszar tekstu, span, wyśrodkowany div.
I to jest też coś w rodzaju tajemnicze wyglądający na pierwszy rzut oka
ale z tego bałaganu następuje pewne wzorce i powtarzalne wzory,
tak, że gdy mamy podstawy w dół, będziesz mógł napisać kod jak to
a następnie manipulować kod jak to za pomocą kolejnego języka, zwany JavaScript.
I JavaScript to język, który działa wewnątrz przeglądarki
dziś, że używamy na Harvard kursów, dla narzędzia handlowego oczywiście, że używa Google maps
dać ci całą masę dynamizmu, Facebook daje pokazać natychmiastowe aktualizacje statusu,
Twitter używa go pokazać tweets natychmiast.
Wszystko to zaczniemy zanurzyć się w.
Ale żeby się tam dostać, trzeba zrozumieć co nieco o Internecie.
Ten klip jest tu po prostu minut długości, a załóżmy, teraz to jest w rzeczywistości,
jak działa Internet jako teaser tego, co znajduje się przed nami. Daję wam "Warriors of the Net".
>> [♫ Wolna muzyka chór ♫]
[Mężczyzna narrator] On przyszedł z wiadomością.
Z protokołem wszystkie jego własne.
[♫ Szybciej electronic music ♫]
On przyszedł na świat chłodnych zapór, niedbały routerów
i zagrożenia o wiele gorsze niż śmierć.
Jest szybki. On jest silny. On jest TCP / IP, a on ma swój adres.
Wojownicy netto.
[Malan] Następne tygodnie, a następnie. Internet. Programowanie Web. To CS50.
[CS50.TV]