[Powered by Google Translate] [Tydzień 4] [David J. Malan] [Harvard University] [To jest CS50.] [CS50.TV] Dobrze, to CS50, i jest to początek 4 tygodniu i jest to jeden z najwolniejszych możliwych algorytmów sortowania. Które z nich było to, że po prostu obserwował tam? To było coś w rodzaju bańki, tak duże O (n ^ 2) + sum, i rzeczywiście nie jesteśmy jedynymi, którzy w tym świecie wydaje się wiedzieć co to jest lub bubble jego czas uruchomiona. Rzeczywiście, był to wywiad z Eric Schmidt z Google i były senator Barack Obama, zaledwie kilka lat temu. Teraz, Senator, jesteś tu w Google, a ja lubię myśleć o prezydencji rozmowy kwalifikacyjnej. Teraz trudno jest dostać pracę jako prezydenta, a ty przechodzisz rygorów teraz. Trudno też dostać pracę w Google. Mamy pytania i prosimy naszych kandydatów pytania, a ten jest z Larry Schwimmer. Myślicie, że żartuję? To właśnie tu. Co to jest najbardziej skuteczny sposób, aby posortować milion 32-bitowe liczby całkowite? [Śmiech] Dobrze Przykro mi. >> No, no, no, no. Myślę, że sortowanie bąbelkowe byłoby źle droga. Chodź, który powiedział mu to? Ostatni tydzień przypomnieć zrobiliśmy sobie przerwę od kodu, co najmniej na jeden dzień, i rozpoczął koncentrując się na niektórych wyższych idei i rozwiązywania problemów na poziomie bardziej ogólnym w kontekście wyszukiwania i sortowania, i wprowadził coś, co nie Slap tę nazwę w zeszłym tygodniu, ale asymptotycznej notacji, Big O, Big Omega, a czasem Big notacja Theta, a te były po prostu sposoby opisywania czas pracy algorytmów, ile czasu zajmuje dla algorytmu do uruchomienia. A może pamiętacie, że mówił o czasie trwania w zakresie wielkości wejścia, które ogólnie nazywamy n, co problem może być, gdzie n jest liczba osób w pokoju, liczba stron w książce telefonicznej i zaczęliśmy pisać rzeczy jak O (n ^ 2) lub O (n) lub O (n log n), i nawet jeśli matematyka nie bardzo wyszło tak idealnie i to było n ² - n / 2 czy coś takiego my zamiast po prostu wyrzucić niektóre z niższych warunkach zamówienia, i motywacja nie jest to, że naprawdę chcemy jakby obiektywny sposób oceny wydajność programów lub wykonanie algorytmów , które na koniec dnia nie ma nic, na przykład z szybkością komputera dziś. Na przykład, jeśli wdrożenie sortowania bąbelkowego, lub wdrożenie seryjnej sortowania sortowania lub zaznaczenie na dzisiejszym komputerze 2 GHz komputer, i uruchomić go, i zajmuje pewną liczbę sekund, w przyszłym roku nie ma 3 GHz lub 4 GHz komputer, a może potem twierdzić, że "Wow, mój algorytm jest teraz dwa razy szybciej ", podczas gdy w rzeczywistości to nie jest oczywiście prawdą. To tylko sprzęt jest coraz szybszy, ale komputer nie, i tak naprawdę chcemy wyrzucić rzeczy jak wielokrotność 2 lub wielokrotność 3, jeśli chodzi o opis jak szybko lub jak wolno algorytm jest i naprawdę skupić na n lub jakiś czynnik zawiadomienia, niektóre jego mocy, jak w przypadku z sortuje tygodnia. I przypominają, że z pomocą sortowanie korespondencji seryjnej byliśmy w stanie zrobić o wiele lepiej niż sortowanie bąbelkowe i rodzaju selekcji a nawet rodzaj wstawiania. Dostaliśmy się do n log n, i znowu, Przypomnijmy, że log n ogólnie odnosi się do czegoś, co rośnie wolniej, a następnie n, więc n log n dotąd było dobre ponieważ mniej niż ² n. Ale do osiągnięcia N log N z sortowania korespondencji seryjnej , co było podstawowym zalążkiem idei, które mieliśmy wykorzystać że my również wykorzystała już w tydzień 0? Jak udało się rozwiązać problem sortowania sprytnie z sortowania korespondencji seryjnej? Co było kluczem insight, być może? Każdy, kto w ogóle. Dobra, zróbmy krok w tył. Opisać seryjnej sortowanie swoimi słowami. Jak to działa? Dobrze, wiosłować z powrotem do 0 tygodni. Dobrze, tak. [Niesłyszalne-uczeń] Dobra, dobra, więc podzieliliśmy tablicy liczb na 2 części. Posortowaliśmy każdego z tych elementów, a następnie połączone ich i widzieliśmy ten pomysł przed podjęcia problemu, że to jest wielki i siekanie go na problem, że to jest duży czy to duży. Przypomnijmy przykład książki telefonicznej. Przypomnijmy sobie własny algorytm liczenia od tygodni temu więc scalić sort podsumował to Pseudokod tutaj. Kiedy podano n elementów, najpierw było sanity sprawdzić. Jeśli n <2, to nic nie robię w ogóle ponieważ jeśli n <2 to n jest 0 lub 1, oczywiście, a jeśli tak to albo 0 lub 1 nie ma nic do sortowania. Skończysz. Twoja lista jest już trywialnie posortowane. Ale w przeciwnym razie, jeśli masz 2 lub więcej elementów, należy iść dalej i podzielić je na 2 części, z lewej i prawej strony. Sortować każdej z tych połówek, a następnie scalić posortowane połówki. Ale problemem jest to, że na pierwszy rzut oka to jest jak mamy punting. Jest to okrągły, że jeśli definicja w Poprosiłem cię posortowanie tych n elementów i mówisz, "W porządku, w porządku, będziemy sortować te n / 2 i tych, n / 2 elementów" następnie moje następne pytanie będzie "Dobrze, jak można posortować n / 2 elementów?" Jednak ze względu na strukturę tego programu, bo nie ma w tym przypadku zasada, że ​​tak powiem, to szczególny przypadek, który mówi, że jeśli n jest > Sara, wszystko w porządku. Kelly. >> Kelly? Willy. >> Willy, Sara, Kelly i Willy. Teraz I zostały zadawane pytanie przez kogoś jak wiele osób się na tym etapie, a ja nie mam pojęcia. Jest to bardzo długa lista, a więc zamiast zamierzam zrobić trick. Zamierzam zwrócić się do osoby obok mnie zrobić większość prac, oraz że odbywa się po robi większość pracy Mam zamiar zrobić najmniejszą możliwą ilość pracy i po prostu dodać 1 do tego, co jest jej odpowiedź, więc jedziemy. Poproszono mnie, ile osób jest na scenie. Ilu ludzi na scenie na lewo od ciebie? Lewo ode mnie? >> Dobra, ale nie oszukuj. To dobrze, to prawda, ale jeśli chcemy kontynuować tę logikę Załóżmy, że podobnie chcą punt ten problem z lewej Ciebie więc zamiast odpowiedzi bezpośrednio iść do przodu i po prostu przekazać złotówki. Och, jak wiele osób jest na lewo od mnie? Ile osób jest na lewo? 1. [Śmiech] Ok, więc 0, więc co teraz Willy zrobił jest pan wrócił swoją odpowiedź w tym kierunku, mówiąc 0. Teraz, co należy zrobić? >> 1. Ok, więc jesteś 1, więc mówisz: "Dobra, mam zamiar dodać 1 do tego, co było Ilość Willy ", więc 1 + 0. Jesteś już 1, więc odpowiedź na prawo jest teraz- 1. >> A mój będzie 2. Dobra, więc bierzesz poprzednią odpowiedź 1, dodając minimalną ilość pracy, którą chcesz zrobić, co jest +1. Teraz masz 2, a następnie podaj mi jaka wartość? 3, to znaczy, przepraszam, 2. Good. Cóż, mieliśmy 0 w lewo. Potem mieliśmy 1, a następnie dodajemy 2, a teraz jesteś wręczając mi numer 2, i tak mówię, dobra, +1, 3. Jest rzeczywiście 3 ludzi stojących obok mnie na tym etapie, więc mogliśmy oczywiście zrobił to bardzo liniowo, bardzo w oczywisty sposób, ale co tak naprawdę zrobić? Wzięliśmy problem wielkości 3 na początku. Następnie złamał go na problem o rozmiarze 2, to problem wielkości 1, a na końcu bazowym było naprawdę, oh, nie ma nikogo, w którym momencie Willy wrócił efektywnie zakodowane odpowiedź kilka razy, i drugi następnie przepuszcza się, przepuszcza się, przepuszcza się, , a następnie przez dodanie tej dodatkowej 1 jeden zaimplementowaliśmy tę podstawową ideę rekursji. Teraz, w tym przypadku nie miało to rozwiązania problemu dłużej skutecznie następnie widzieliśmy do tej pory. Ale pomyśl o algorytmach zrobiliśmy na scenie do tej pory. Mieliśmy 8 kartek na tablicy, na wideo, kiedy Sean szukał numerem 7, a co on naprawdę robi? Cóż, nie zrobił żadnego rodzaju dziel i rządź. Nie zrobił żadnego rodzaju rekursji. Raczej po prostu nie ten liniowy algorytm. Ale kiedy wprowadził ideę posortowanych numerów na etapie żyć w zeszłym tygodniu Następnie mieliśmy ten instynkt będzie na środku, W tym momencie mieliśmy mniejszą listę wielkości 4 lub inny wykaz wielkości 4, a następnie mieliśmy dokładnie ten sam problem, więc powtarzać, powtarzać, powtarzać. Innymi słowy, mamy recursed. Dziękuję bardzo do naszych 3 wolontariuszy tutaj wykazanie rekursji z nami. Zobaczymy, czy nie możemy tego teraz trochę więcej betonu, rozwiązania problemu, że ponownie możemy zrobić dość łatwo, ale będziemy używać go jako odskocznię do realizacji tego podstawowego pojęcia. Jeśli chcę, aby obliczyć sumowanie kilka numerów, na przykład, jeśli podajesz w liczbie 3, Chcę dać wam wartość sigma 3, to, że suma 3 + 2 + 0 1 +. Chcę wrócić odpowiedzi 6, więc będziemy realizować tę funkcję sigma, funkcja sumowania że znowu bierze na wejściu, a następnie zwraca sumowanie z tej liczby w dół do 0. Możemy to zrobić dość łatwo, prawda? Możemy to zrobić z pewnego rodzaju pętli struktury, więc pozwól mi iść do przodu i uzyskać to się zaczęło. Dołącz stdio.h. Pozwól sobie na główny do pracy tutaj. Ratujmy to jako sigma.c. Potem mam zamiar iść tutaj, i mam zamiar zadeklarować int n, i mam zamiar wykonać następujące czynności, podczas gdy użytkownik nie współpracuje. Gdy użytkownik nie dał mi liczbę dodatnią pozwól mi iść dalej i skłonić ich do n = getInt, i dam im kilka wskazówek co do tego, co robić, więc printf ("liczba całkowita dodatnia proszę"). Tylko coś stosunkowo proste jak to tak, że w momencie trafiliśmy linii 14 teraz mamy dodatnią przypuszczalnie w n. Teraz coś z tym zrobić. Pozwólcie mi iść do przodu i obliczyć sumowanie, więc int suma = sigma (n). Sigma jest tylko podsumowanie, więc ja tylko piszę w hodowcy sposób. My po prostu nazwać to sigma tam. To suma, a teraz mam zamiar wydrukować wynik, printf ("suma jest% d \ n", suma). A potem wrócę 0 na dokładkę. Zrobiliśmy wszystko, że ten program wymaga oprócz interesującej części, które jest rzeczywiście sigma realizacji funkcji. Puść mnie tu na dole, i pozwól mi zadeklarować funkcji sigma. To musi się zmienną, która jest typu integer, i jaki typ danych chcę wrócić prawdopodobnie z sigma? Int, ponieważ chcę, aby dopasować moje oczekiwania na linii 15. Tu pozwól mi iść dalej i wdrożyć to w sposób bardzo prosty. Idziemy dalej i powiedzieć, int suma = 0, i teraz mam zamiar go mieć tutaj trochę dla pętli że zamierza powiedzieć coś takiego, for (int i = 0; i <= liczba; i + +) suma + = i. A potem mam zamiar wrócić sumę. Mogę to być realizowane na wiele sposobów. Mogłem użyć pętli while. Mogłem pominąć użyciu zmiennej sumy jeśli naprawdę chciał, ale w skrócie, po prostu mieć funkcję, że jeśli ja nie głupi deklaruje suma wynosi 0. Następnie przechodzi z 0 na górę przez liczbę, i na każdej iteracji dodaje, że obecne wartości do sumy, a następnie zwraca sumę. Teraz jest niewielka optymalizacja tutaj. Prawdopodobnie jest to zmarnowany krok, ale tak będzie. To jest w porządku teraz. Jesteśmy przynajmniej jest dokładny i będzie 0 całą drogę na górę. Nie bardzo ciężko i bardzo proste, , ale okazuje się, że przy pomocy funkcji sigma mamy same możliwości jak my tutaj, na scenie. Na scenie po prostu liczy ile osób było obok mnie, lecz jeśli chcemy policzyć 3 + 2 + 1 na dół do 0 mogliśmy podobnie punt do funkcji że ja zamiast opisać jako rekurencyjne. Tu zróbmy szybkie sanity sprawdzić i upewnić się, że nie głupi. Wiem, że istnieje co najmniej jedna rzecz w tym programie, że zrobił źle. Gdy wciskamy enter mam zamiar uzyskać jakiekolwiek na mnie krzyczeć? Co ja mam być krzyknęła na o? Tak, zapomniałem o prototyp, więc używam funkcji o nazwie sigma na linii 15, ale to nie jest zadeklarowane do linii 22, więc najlepiej udać się tutaj aktywnie i oświadczam prototypu, i powiem int Sigma (int liczba), i to jest to. Jest realizowany na dole. Albo inny sposób mogę rozwiązać ten problem, Mogę przenieść funkcję tam, co nie jest złe, ale przynajmniej gdy twoje programy zaczynają się długo, szczerze mówiąc, Myślę, że jest jakaś wartość w mając zawsze na górze głównej tak, że w czytniku może otworzyć plik, a następnie od razu zobaczyć co program robi, bez konieczności wyszukiwania przez niego szukam tej głównej funkcji. Chodźmy do mojego okna terminala tutaj, spróbuj zrobić sigma sigma, i wkręca się tutaj. Niejawna deklaracja getInt funkcji oznacza Zapomniałem zrobić to, co jeszcze? [Niesłyszalne-uczeń] Dobra, więc najwyraźniej to częsty błąd, więc zróbmy to tu, cs50.h, a teraz wróćmy do mojego okna terminala. Ja wyczyścić ekran, a ja ponownie uruchomić aby sigma. Wydaje się, że skompilowany. Chciałbym teraz uruchomić sigma. Będę pisać w liczbie 3, a ja dostałem 6, więc nie rygorystyczna kontrola, ale przynajmniej wydaje się działać na pierwszy rzut oka, ale teraz niech zgrać go na kawałki, i niech faktycznie wykorzystują ideę rekursji, znowu, w kontekście bardzo prosty, tak aby w ciągu kilku tygodni " kiedy zaczynamy odkrywać hodowcy struktur danych niż macierze mamy kolejne narzędzie w zestaw narzędzi, z którym do manipulować tych struktur danych, jak zobaczymy. To jest podejście iteracyjne, pętla podejście. Pozwól mi zamiast teraz zrobić. Pozwól mi powiedzieć, że zamiast sumowanie liczby w dół do 0 to naprawdę to samo, co liczba + sigma (liczba - 1). Innymi słowy, tak jak na etapie I punted do każdego z ludzi obok mnie, a one z kolei przechowywane punting aż wreszcie najniższy na Willy'ego, który musiał zwrócić zakodowane odpowiedź jak 0. Tu teraz jesteśmy podobnie punting do sigma Funkcjonalność pierwotnie wywołana, ale klucz wiedza o jest to, że nie dzwonisz sigma identycznie. Nie jesteśmy przekazując n. Mamy jasno przekazując numer - 1, więc nieco mniejszy problem, nieco mniejszy problem. Niestety, nie dość rozwiązanie jest jeszcze, i przed naprawić co można by wyskoczyć tak oczywiste w niektórych z was pozwól mi iść do przodu i ponownie wykonać. Wydaje skompilować okay. Pozwól, że powtórka z 6 sigma. Oj, daj mi powtórka z 6 sigma. Widzieliśmy to już wcześniej, choć czasem przypadkowo ostatniego, jak również. Dlaczego pojawia się ten tajemniczy segmentation fault? Tak. [Niesłyszalne-uczeń] Nie ma wariant podstawowy, a bardziej szczegółowo, co prawdopodobnie się stało? To zachowanie objawem co? Powiedz to głośniej. [Niesłyszalne-uczeń] Jest to nieskończona pętla skutecznie, i problem z nieskończonej pętli gdy wiąże rekursję w tym przypadku, funkcja wywołująca się, , co dzieje się za każdym razem wywołać funkcję? No cóż, wracam do tego jak rozplanowany pamięci w komputerze. Powiedzieliśmy, że jest to fragment pamięci nazywa stack to na dole, i za każdym razem wywołać funkcja trochę więcej pamięci zostanie wprowadzone w tym tzw stosu zawierający określoną funkcję w lokalnych zmiennych lub parametrów, jeśli tak nazywa rozmowy sigma Sigma nazywa sigma  wzywa sigma gdzie to mówi historia? Cóż, to w końcu przekroczenia całkowitej kwoty pamięci, że masz dostęp do komputera. Jesteś przekroczył segment Miałeś pozostać w, i masz ten błąd segmentacji, core po cenach dumpingowych, i co core dumped oznacza to, że mam teraz plik o nazwie rdzeń który jest plikiem zawierającym zer i jedynek faktycznie w przyszłości będzie diagnostycznie użyteczne. Jeśli nie jest to oczywiste dla Ciebie, gdzie jest błąd rzeczywiście można zrobić trochę analizy sądowej, by tak rzec, na ten plik zrzutu pamięci, które ponownie, jest po prostu cała masa zer i jedynek że w istocie reprezentuje stan programu w pamięci W chwili, gdy w ten sposób awarii. Fix jest to, że nie możemy po prostu ślepo wrócić sigma, liczba + sigma z nieco mniejszym problemem. Musimy mieć jakąś przypadku bazowego tutaj i co należy bazowym prawdopodobnie? [Niesłyszalne-uczeń] Ok, tak długo, jak liczba jest dodatnia powinna rzeczywiście powrót tego lub innymi słowy, jeśli liczba jest, powiedzmy, <= 0 do wiesz co, ja pójdę dalej i powrotu 0, podobnie jak Willy zrobił, a inny, mam zamiar iść do przodu i powrót tego, więc nie jest to znacznie krótszy niż iteracyjnej wersji, że podciął najpierw przy użyciu pętli for ale zauważ, że jest to rodzaj elegancji do niego. Zamiast zwracać pewną liczbę i wykonując wszystkie te matematyki i dodanie rzeczy z lokalnych zmiennych ty zamiast powiedzieć "Dobrze, jeśli jest to super łatwy problem, jak liczba jest <0, niech natychmiast powrócić 0 ". Nie będziemy się przejmować wspierających liczb ujemnych, więc mam zamiar ciężko kodem wartość 0. Ale poza tym, do realizacji tej idei zsumowanie Wszystkie te liczby razem można skutecznie wziąć mały kęs z tego problemu, podobnie jak my tutaj na scenie, Następnie reszta Punt problemu do następnej osoby, ale w tym przypadku osoba to samemu. To identycznie nazwany funkcji. Po prostu przekaż to mniejsze i mniejsze i mniejsze problemu za każdym razem, i mimo, że nie mamy dość sformalizowane rzeczy w kodzie tutaj to jest dokładnie to, co dzieje się w tydzień 0 z książki telefonicznej. To jest dokładnie to, co się dzieje w ostatnich tygodniach z Seanem i naszymi pokazami poszukiwania liczb. To biorąc problem i dzieląc go ponownie i ponownie. Innymi słowy, jest to sposób teraz przełożenia Konstrukt ten prawdziwy świat, to wyższy poziom konstrukt z dziel i rządź i robić coś znowu i znowu w kodzie, więc jest to coś ujrzymy znów w czasie. Teraz, jak na bok, jeśli jesteś nowy w rekursji należy przynajmniej rozumiem teraz dlaczego to jest śmieszne. Mam zamiar iść do google.com, i będę szukać pewnych sztuczek rekursji, enter. Poinformować osobę obok Ciebie, jeśli nie śmiali tylko teraz. Czy chodziło Ci o rekursji? Czy masz na myśli-ah, nie idziemy. Dobrze, że teraz jest reszta każdego. Trochę Pisanka osadzone gdzieś w Google. Tak na marginesie, jednym z ogniw możemy umieścić na stronie internetowej oczywiście na dziś jest tylko siatka ta z różnych algorytmów sortowania, niektóre z nich spojrzał na ostatni tydzień, ale to, co jest miłe o tej wizualizacji jak spróbować owinąć wokół różnych umysł rzeczy związanych z algorytmami wiedzą, że bardzo łatwo można teraz uruchomić z różnymi rodzajami wejść. Wejścia wszystkie odwrócone wejścia większości posortowane, wejścia losowo i tak dalej. Jak spróbować ponownie, odróżnić te rzeczy w twoim umyśle sobie sprawę, że na kursie URL strony internetowej na stronie Wykład może pomóc powód przez niektóre z nich. Dziś w końcu dostać się do rozwiązania tego problemu na chwilę z powrotem, co było, że ta funkcja wymiany po prostu nie działa, a co było podstawowym problemem z tym zamiana funkcji, Celem, który był znowu do wymiany wartości tu i tu takie, że tak się stanie? To faktycznie nie działa. Dlaczego? Tak. [Niesłyszalne-uczeń] Dokładnie wyjaśnienie tego bugginess po prostu dlatego, że podczas wywoływania funkcji w C i te funkcje przyjmują argumenty, jak i b tutaj jesteś przejazdem w kopii niezależnie od wartości czy prowadzimy dla tej funkcji. Nie dostarczamy oryginalne wartości siebie, więc widzieliśmy to w kontekście buggyc, buggy3.c, który wyglądał trochę coś takiego. Przypomnijmy, że X i Y było inicjowane 1 i 2, odpowiednio. Następnie wydrukować co oni. Potem twierdził, że byłem zamianę je poprzez wywołanie swap x, y. Ale problemem było to, że zamiana pracował, , ale tylko w zakresie wymiany samej funkcji. Jak tylko hit linii 40 Wartości te zamienione zostały wyrzucone i tak nic nie w pierwotnej funkcji głównego faktycznie zmienił się wcale, więc jeśli uważasz, że wtedy, co to wygląda z punktu widzenia naszej pamięci Jeśli to lewa strona płyty reprezentuje- i zrobię mój najlepszy dla wszystkich, aby zobaczyć, czy to lewa strona zarządu stanowi, powiedzmy, RAM, a stos będzie rosnąć w ten sposób, i wywołania funkcji, jak główny i główny ma 2 zmienne lokalne, X i Y, Opiszmy te jako x tutaj i niech opisują je jako y tu i postawmy w wartościach 1 i 2, więc tu jest głównym, i gdy główny wywołuje funkcja wymiany systemu operacyjnego daje Funkcja zamiany własnego pokos pamięci na stosie, własnej ramki na stosie, że tak powiem. Również przeznacza 32 bitów dla tych wskazówki. Zdarza się, zadzwonić do nich i b, ale to jest całkowicie arbitralne. To mogła być ich powołał, co chce, ale to, co dzieje się, gdy główny Swap połączenia jest potrzebny ten 1, umieszcza kopię tam, stawia kopię tam. Jest 1 inna zmienna lokalna w swap, choć nazywa co? Tmp. >> Tmp, więc pozwól mi dać sobie kolejne 32 bity Tutaj i co zrobić w tej funkcji? Powiedziałem int tmp ma, więc ma 1, więc zrobiłem to, kiedy ostatnio grał z tego przykładu. Potem dostaje b, więc b jest 2, tak teraz staje się to 2, i b otrzymuje się temperatury, to temperatura jest 1, tak teraz b staje to. To świetnie. Udało się. Ale następnie, gdy tylko funkcja zwróci swap pamięć skutecznie znika, tak, że może być użyte ponownie przez inną funkcję w przyszłości i głównym jest oczywiście całkowicie niezmieniona. Potrzebujemy sposób zasadniczy rozwiązania tego problemu, i dziś będziemy w końcu mieć to sposobem którym możemy wprowadzić coś, co nazywa wskaźnik. Okazuje się, że możemy rozwiązać ten problem nie przekazując kopie xiy ale zamiast tego, przekazując co, myślisz, z funkcją wymiany? Tak, a co z adresem? Tak naprawdę nie mówił o adresy w bardzo szczegółowo, ale jeśli ta tablica reprezentuje mojego komputera pamięć moglibyśmy z pewnością rozpocząć numerację bajtów w mojej pamięci i że to jest 1 bajtu, to bajt # 2, # 3 bajty, byte # 4, # byte ... 2 miliardy, jeśli mam 2 GB pamięci RAM, więc możemy z pewnością wymyślić jakiegoś niepożądanego numeracją dla wszystkich bajtów indywidualnych w mojej pamięci komputera. Co zrobić, jeśli zamiast kiedy dzwonię Swap zamiast przejść w kopii xiy dlaczego nie mogę zamiast przekazać w adresie X W tym adres y tutaj zasadniczo adres pocztowy xiy bo wtedy swap, jeśli on informowany z adresu w pamięci x i y, następnie swap, jeśli ćwiczyliśmy go trochę, mógłby potencjalnie prowadzić do tego adresu, by tak rzec, x, i zmień numer tam, a następnie jechać na adres y, zmienić numer tam, nawet jeśli nie jest właściwie coraz kopie tych wartości siebie, więc nawet rozmawialiśmy o tym, jako pamięć Main i to jako swap pamięć potężny i niebezpieczna część C jest to, że funkcja może dotykać dowolnego w pamięci komputera, i to jest potężny w których można zrobić bardzo fajne rzeczy z programów komputerowych w C. Jest to niebezpieczne, ponieważ można też zepsuć bardzo łatwo. W istocie, jednym z najbardziej popularnych sposobów programów te dni wykorzystać nadal jest na nie programista zrealizować że on lub ona jest zezwolenie na danych być zapisane w pamięci w miejscu, które nie jest przeznaczone. Na przykład stwierdza on szereg wielkości 10 ale potem przypadkowo próbuje umieścić 11 bajtów do tej tablicy pamięci, i zaczynasz dotykać części pamięci, które nie są już ważne. Wystarczy kontekstowe, niektórzy z was wiedzą, że oprogramowanie często monituje o numerach seryjnych lub kluczy rejestracyjnych, Photoshop i Word oraz programy takie jak ten. Istnieją pęknięć, jak niektórzy z was wiedzą, w Internecie, gdzie możesz uruchomić mały program, i voila, nie więcej wniosek o numer seryjny. Jak to działa? W wielu przypadkach te rzeczy są po prostu znalezienie w komputerach segmenty tekstu w komputerze rzeczywistych zer i jedynek gdzie jest ta funkcja, gdy numer seryjny jest wymagany, i zastąpić tę przestrzeń, lub gdy program jest uruchomiony można dowiedzieć się, gdzie klucz jest przechowywany używając coś nazywa debugger, można złamać oprogramowania w ten sposób. To nie znaczy, że to jest nasz cel na najbliższe kilka dni, ale ma bardzo rzeczywiste konsekwencje. Zdarza się, że jeden do włączenia kradzież oprogramowania, ale jest również kompromis z całych maszyn. W rzeczywistości, gdy strony te dni wykorzystać i zagrożona i dane wyciekły i hasła zostały skradzione to bardzo często odnosi się do złego zarządzania czyjejś pamięci, lub, w przypadku baz danych, brak przewidywania kontradyktoryjności input, więc więcej o tym w najbliższych tygodniach, ale teraz po prostu zapowiedzią tego rodzaju uszkodzenia, które możesz zrobić przez nie do końca zrozumieć, jak to wszystko działa pod maską. Chodźmy o zrozumienie, dlaczego to jest zepsuty z narzędzia, które stają się coraz bardziej przydatne jak nasze programy zdobyć bardziej złożone. Do tej pory, kiedy miałem błąd w programie jak odeszłaś o debugowania? Co twoi techniki było do tej pory, czy nauczane przez TF lub po prostu samoukiem? [Student] printf. Printf, więc printf był prawdopodobnie Twój przyjaciel, że jeśli chcesz, aby zobaczyć co się dzieje wewnątrz programu wystarczy umieścić printf tutaj, printf tutaj, printf tutaj. Następnie uruchom go, i masz całą masę rzeczy na ekranie że można użyć, aby następnie wywnioskować, co właściwie dzieje źle w swoim programie. Printf bywa bardzo potężne rzeczy, ale to bardzo proces ręczny. Musisz umieścić printf tu printf tutaj a jeśli go umieścić wewnątrz pętli może dostać 100 linii produkcji, które następnie trzeba przesiać przez. To nie jest bardzo łatwy w obsłudze i interaktywny mechanizm debugowania programów jest, ale na szczęście istnieje alternatywne. Jest to program, na przykład, o nazwie GDB, GNU Debugger, który jest trochę arcane w jaki sposób z niego korzystać. Jest to trochę skomplikowane, ale szczerze mówiąc, jest to jedna z tych rzeczy, gdzie jeśli umieścisz w tym tygodniu i następnym dodatkowe godziny, aby zrozumieć coś jak GDB to zaoszczędzić prawdopodobnie kilkadziesiąt godzin, w dłuższej perspektywie, tak z tym, dam ci liścik, w jaki sposób ta rzecz działa. Jestem w moim oknie terminala. Pozwólcie mi iść do przodu i skompilować ten program, buggy3. Jest już aktualne. Pozwól mi go uruchomić tak jak zrobiliśmy z powrotem podczas, i rzeczywiście, gdy jest uszkodzony. Ale dlaczego tak jest? Może spieprzyłem funkcję wymiany. Może to i b. Nie jestem dość porusza nimi w pełnym zakresie. Pozwólcie mi iść do przodu i robić. Zamiast po prostu uruchomić buggy3 pozwól zamiast uruchomić ten GDB programu, i mam zamiar powiedzieć to uruchomić buggy3, i mam zamiar dołączyć argument wiersza polecenia,-tui, a my umieścić to w przyszłości do problemów w ciemno przypominają. A teraz to czarno-biały interfejs pojawił się, że znów jest trochę przytłaczające w pierwszym, bo to wszystko jest Informacja o gwarancji na dół, ale przynajmniej coś jest znajome. W górnej części okna jest mojego aktualnego kodu, i jeśli mogę przewinąć tutaj pozwolę sobie przejść do samej górze moim pliku i rzeczywiście, nie buggy3.c i zauważ, w dolnej części okna Mam ten GDB monitu. To nie jest taki sam jak mój normalny John Harvard zachęty. Jest to szybka, że ​​się dzieje, żebym mógł kontrolować GDB. GDB to debugger. Debugger to program, który pozwala przejść przez wykonanie linii programowej przez linia po linii, po drodze robi wszystko co chcesz do programu, nawet wywołanie funkcji, lub patrząc, co ważniejsze, W różnych zmiennej wartości. Idziemy naprzód i to zrobić. Mam zamiar iść do przodu, a następnie wpisz w biegu na polecenia gdb, więc zauważyć, na dole po lewej stronie ekranu mam wpisane uruchomienia, i mam wcisnąć klawisz enter, i co z tego? To dosłownie pobiegł mój program, ale w rzeczywistości nie widać wiele dalej tutaj bo nie rzeczywiście powiedział debugera wstrzymać w określonym momencie. Wpisując run uruchamia program. I właściwie nie widzę. I nie można manipulować. Zamiast tego pozwól mi to zrobić. W tym wierszu GDB pozwól zamiast wpisać przerwę, enter. To nie jest to, co chciałem napisać. Załóżmy, zamiast wpisać przerwa main. Innymi słowy, chcę ustawić coś zwane przerwania, która jest trafnie nazwany, ponieważ będzie przerwa lub pauza Realizacja programu w tym konkretnym miejscu. Main to nazwa mojej funkcji. Zauważ, że GDB jest bardzo pomysłowe. To zorientowali się, że dzieje się z głównym rozpocząć mniej więcej na linii 18 z buggy3.c, a następnie zauważyć tutaj, w lewym górnym rogu b + jest tuż obok linii 18. To się przypominając mi, że mam ustawić punkt przerwania na linii 18. Tym razem po wpisaniu bieg, zamierzam uruchomić mój program aż trafi tego przerwania, więc program zatrzyma się na mnie na linii 18. Zaczynamy, biegać. Wydaje się, że nic nie stało, ale zauważ, w lewym dolnym uruchamiania programu, buggy3, breakpoint 1 w głównym na linii buggy3.c 18. Co mogę teraz zrobić? Zauważ, mogę zacząć pisać takie rzeczy jak drukowanej, nie printf, x druku, a teraz, że to dziwne. $ 1 to tylko ciekawość, jak zobaczymy za każdym razem drukować coś dostać nowy $ value. To jest tak, że można odwołać się do poprzednich wartości tylko w przypadku, ale teraz to, co mi mówi print jest wartość x w tym momencie w historii jest najwyraźniej 134514032. Co? Gdzie to jeszcze pochodzi? [Niesłyszalne-uczeń] Rzeczywiście, jest to, co my nazywamy wartość śmieci, a my nie rozmawialiśmy o tym jeszcze, ale dlatego, że należy zainicjować zmienne jest oczywiście tak, że mają jakąś wartość, że chcesz je mieć. Ale połów jest przypomnieć, że można zadeklarować zmienne jak ja przed chwilą w moim przykładzie sigma bez faktycznie dając im wartość. Przypomnijmy, co zrobiłem tutaj w sigma. I oświadczył n, ale jaka wartość dałem go? Brak, ponieważ wiedziałem, że w ciągu najbliższych kilku liniach GetInt zajmie problemu wprowadzenie wartości wewnątrz n. Ale w tym momencie w historii linii 11 i 12 linii i linia 13 i linia 14 Przez te kilka linii, co jest wartością n? W C po prostu nie wiem. Jest to generalnie niektóre wartości śmieci, niektóre całkowicie losowy numer Pozostaje się zasadniczo z jakiejś poprzedniej funkcji został uruchomiony, tak jak twój program działa Przypomnijmy, że funkcja pobiera funkcja, funkcja, funkcja. Wszystkie te klatki się umieścić na pamięci, a następnie powrót tych funkcji, i tak jak sugerowałem gumką ich pamięć jest ostatecznie ponownie używać. Cóż, tak się składa, że ​​zmienna x w tym programie Wydaje się, że zawierała jakąś wartość śmieci jak 134514032 z jakiejś poprzedniej funkcji, a nie taki, który napisałem. To może być coś, co przychodzi skutecznie z systemem operacyjnym, niektórych funkcji pod maską. Dobrze, że jest w porządku, ale niech teraz przejść do następnego wiersza. Jeśli napiszę "next" w moim wierszu GDB i wciskamy Enter, zauważyć, że podkreślając ruchy w dół do linii 19, ale logiczną implikacją jest, że linia 18 Obecnie zakończeniu wykonywania, więc jeśli znowu wpisać "print x" Należy teraz widzę 1, i rzeczywiście, mam. Znowu $ rzeczy jest sposób GDB przypomnienia co historia wydruków to, że zrobiłeś. Teraz pozwól mi iść do przodu i wydrukować y, i rzeczywiście, y pewne szalone napięcie, jak również, ale to nic wielkiego, bo w linii 19 mamy zamiar przypisać wartość 2, więc pozwól mi wpisać "Dalej". A teraz jesteśmy na printf linii. Pozwól mi zrobić X drukowania. Pozwól mi zrobić r drukowania. Szczerze mówiąc, jestem już trochę zmęczony drukowania to. Pozwól, że zamiast wpisywać "display X" i "Y Wskaźnik", i teraz za każdym razem wpisać polecenie w przyszłości I będzie przypominał tego, co jest x, a y, co to X i Y, co jest x i y. Nie mogę również, jak z boku, typu "mieszkańców informacji." Info jest specjalne polecenie. Mieszkańców oznacza to pokazuje mi zmiennych lokalnych. Tylko w przypadku, zapomnieć lub jest to szalone, skomplikowana funkcja że ja lub ktoś inny napisał miejscowi informacji powie jakie są wszystkie zmienne lokalne wewnątrz tego lokalnego funkcji które mogą Ci zależy, jeśli chcesz grzebać. Teraz printf ma się wykonać, więc pozwól mi iść do przodu i po prostu wpisz "next". Bo jesteśmy w tym środowisku nie jesteśmy rzeczywiście widząc go wykonać tu, ale zauważ, robi trochę zniekształcone tutaj. Zauważmy jednak, to nadrzędne ekran tam, więc to nie doskonały program tutaj jest, ale to jest w porządku, bo zawsze mogę Kapsa przy wydruku, jeśli chcę. Pozwól mi napisać następny raz, a teraz znajduje się interesująca część. W tym momencie w historii y oznacza 2, a x oznacza liczbę 1, sugerowane tu i ponownie, Powodem tego jest automatycznie wyświetla teraz jest, ponieważ użyto polecenia x ekran i wyświetlacz y, więc chwila wpisuję obok teoretycznie xiy powinny stać zamienione. Teraz już wiemy, że nie będzie to przypadek, ale zobaczymy za chwilę, jak możemy nurkować głębiej, aby dowiedzieć się, dlaczego tak jest prawda. Dalej, niestety, r 2 i jest w dalszym ciągu jeszcze x 1, i może nawet i potwierdzić. Print x, y print. Rzeczywiście, nie wymieniając faktycznie się stało, więc zacznijmy od tego. Oczywiście Swap jest zepsuty. Załóżmy, zamiast wpisać "run" ponownie. Pozwólcie mi powiedzieć, tak, chcę, aby uruchomić go ponownie od początku, enter. Teraz jestem z powrotem na linii 18. Zauważcie, x i y są wartościami śmieci ponownie. Dalej, dalej, dalej, dalej. Jeśli znudzi mogę też po prostu wpisać n dla następnego. Możesz skrócić go do najkrótszym sekwencję znaków. Swap jest teraz zepsuty. Miejmy nurkowania w, więc zamiast wpisywać następny, teraz mam zamiar napisać krok tak, że jestem krok wewnątrz tej funkcji tak, że można przez nie przejść, więc uderzyłem krok i wpisz. Zauważ, że skoki podkreślające się niżej w moim programie do linii 36. Teraz jakie są zmienne lokalne? Miejscowi info. Nic jeszcze tylko dlatego, że nie dotarłeś do tej linii, więc niech śmiało powiedzieć "następny". Teraz wydaje się mieć TMP, TMP druku. Wartość śmieci, prawda? Myślę, że tak. Jak o drukowanie, drukowanie B, 1 i 2? W momencie, jak tylko ponownie wpisać następny tmp ma zamiar wziąć na wartości 1, miejmy nadzieję, bo tmp zostanie przypisana wartość. Teraz zróbmy wydrukować, B PRINT, ale teraz wydrukować tmp, a to rzeczywiście 1. Pozwól mi zrobić. Pozwól mi zrobić. Skończyłem funkcję wymiany. Jestem jeszcze w jej wnętrzu w linii 40, więc pozwól mi wydrukować, print b, i nie obchodzi mnie, co tmp jest. Wygląda na to, swap jest poprawne, jeśli chodzi o zamianę a i b. Ale gdybym teraz wpisać obok, I wrócić do linii 25, i oczywiście, jeśli wpisz x i y druku oni nadal bez zmian, więc nie rozwiązaniu problemu. Ale teraz może diagnostycznie z tym programem GDB mamy przynajmniej zdobyć jeden krok bliżej do zrozumienia co się dzieje źle bez ściółki nasz kod umieszczając printf tutaj printf tutaj, printf tutaj, a następnie uruchomić go ponownie i ponownie próbuje dowiedzieć się, co się dzieje źle. Mam zamiar iść do przodu i wyjść z tego w ogóle z wyjść. To będzie wtedy powiedzieć: "Przestań tak?" Tak. Teraz jestem z powrotem w moim normalnym polecenia, a ja zrobić za pomocą GDB. Tak na marginesie, nie musisz korzystać z tego-tui banderą. W rzeczywistości, jeśli pominąć go dostać w zasadzie dolną połowę ekranu. Jeśli następnie wpisz przerwa głównym, a następnie uruchom Wciąż mogę uruchomić mój program, ale co to będzie zrobić, to bardziej tekstowo Tylko pokaż mi jednego z posiadanych linii na raz. -Tui, tekst interfejsu użytkownika, po prostu pokazuje, że bardziej programu na raz, co jest prawdopodobnie nieco koncepcyjnie prostsze. Ale rzeczywiście, można po prostu robić dalej, dalej, dalej, i mam zamiar zobaczyć jeden wiersz na raz, a jeśli naprawdę chcesz zobaczyć, co się dzieje Mogę pisać listy i zobacz całą masę sąsiednich linii. Jest film, że prosiłem, aby obserwować problemu ustawia 3 w którym Nate opisuje niektóre zawiłości GDB, i to jest jedna z tych rzeczy, szczerze mówiąc, gdzie niektóre nietrywialne procent z was nigdy nie dotykaj GDB, oraz że będzie źle bo dosłownie skończy się spędzać więcej czasu później w tym semestrze ścigających błędy to byś jeśli umieścić w tym pół godziny / godzina w tym tygodniu, a następnie uczenie się komfortowo z GDB. Printf był twoim przyjacielem. GDB powinien być twoim przyjacielem. Wszelkie pytania dotyczące GDB? A oto krótka lista niektórych poleceń najpotężniejszych i najbardziej użyteczne. Tak. >> Czy można wydrukować ciąg? Można wydrukować ciąg? Absolutnie. To nie musi być tylko liczbami całkowitymi. Jeżeli zmienna s jest ciągiem znaków, po prostu wpisz w s druku. To pokaże, co to zmienna string jest. [Niesłyszalne-uczeń] To daje adres i sam ciąg. Pokaże wam. I ostatnia rzecz, to, że są to dobrze wiedzieć, też. Backtrace i ramki, pozwól mi zanurkować w to ostatni raz, dokładnie taki sam program, z GDB. Pozwólcie mi iść do przodu i uruchamiania tekstową wersję interfejsu użytkownika, złamać main. Pozwól mi iść dalej i uruchomić ponownie. Oto jestem. Teraz pozwól mi iść dalej, następny, następny, następny, następny krok, wprowadź. A teraz załóżmy, że jestem teraz w swapu celowo, ale jestem jak "Cholera, co wartość x?" Nie mogę x więcej. Nie mogę y bo nie są w zakresie. Oni nie są w kontekście, ale nie ma problemu. Mogę pisać backtrace. To pokazuje mi wszystkie funkcje, które zostały wykonane do tej chwili. Zauważ, że jeden na dole, main, linii z głównym jest na spodzie obrazu o naszego. Fakt, że swap jest nad nią linii z Swap jest nad nim w pamięć, i jeśli chcę wrócić do głównego tymczasowo mogę powiedzieć "rama". Jaki numer? Main jest frame # 1. Mam zamiar iść do przodu i powiedzieć "Frame 1". Teraz jestem z powrotem w głównym i wydrukować x, a mogę drukować y, ale nie można wydrukować lub b. Ale mogę, jeśli powiem: "Dobra, czekaj. Gdzie Swap?" Pozwól mi iść dalej i powiedzieć "0 klatek." Teraz jestem z powrotem tam, gdzie chcę być, i jak na bok, tam też inne polecenia, jak jeśli jesteś naprawdę nudzi pisać następny, następny, następny, następny, można generalnie mówi "obok 10" i że będzie przejście przez kolejne 10 linii. Można również napisać "kontynuować", kiedy naprawdę się dość intensyfikacji przez nią. Nadal będzie uruchomić program bez przerwy, aż nie natrafi na kolejny punkt przerwania, czy w pętli lub niżej w programie. W tym przypadku mamy nadal do końca, a program zakończył się normalnie. To fantazyjny sposób, gorszy proces. Tylko program zakończył się normalnie. Więcej na ten temat w filmie i debugowania sesji przyjść. To było dużo. Weźmy naszą 5-minutową przerwę, tutaj, i wrócimy z kodowanym i plików. Jeśli zanurkował w tym tygodniu już Pset będziesz wiedzieć, że używamy w kodzie dystrybucji, kod źródłowy, że oferujemy Państwu jako punkt wyjścia, kilka nowych technik. W szczególności, wprowadził nowe słowo kluczowe struct nazwie, na konstrukcji, tak, że możemy tworzyć własne zmienne rodzaju. Wprowadziliśmy także pojęcie pliku I / O, wejścia i wyjścia plików, i to jest tak, że możemy zapisać stan danej tablicy Scramble do pliku na dysku tak, że chłopaki nauczania i mogę zrozumieć , co dzieje się wewnątrz programu, bez konieczności ręcznego grać kilkadziesiąt gier Scramble. Możemy to zrobić bardziej automatedly. Ten pomysł struct rozwiązuje dość przekonujące problem. Załóżmy, że chcemy zaimplementować jakiś program że jakoś śledzi informacje na temat studentów, a studenci mogą mieć, na przykład, identyfikator, nazwę i dom w miejscu jak Harvard, więc są 3 kawałki informacji chcemy, aby wokół, więc pozwól mi iść dalej i zacząć pisać mały program tutaj obejmują stdio.h. Pozwól mi zrobić to cs50.h. I wtedy zaczynam główną funkcję. Nie przejmuj się z argumentami wiersza poleceń, i tu chcę mieć ucznia, więc powiem Student ma imię, więc mam zamiar powiedzieć "nazwę ciągu." Potem powiem uczeń ma również identyfikator, więc int id, i student ma dom, więc jestem również zamiar powiedzieć "dom ciąg". Wtedy będę zamawiać te trochę bardziej czysty jak ten. Ok, teraz mam 3 zmiennych, z którymi do reprezentowania studenta, więc "student". A teraz chcę, aby wypełnić te wartości, więc pozwól mi iść dalej i powiedzieć coś w stylu "Id = 123". Nazwa ma zamiar wrócić do Dawida. Powiedzmy, że dom ma zamiar wrócić do Mather, a potem mam zamiar zrobić coś arbitralnie jak printf ("% s, którego ID wynosi% d, mieszka w% s. A teraz, co ja chcę, aby podłączyć się tutaj, jeden po drugim? Nazwa, id, house; return 0. Dobra, chyba spieprzyłem gdzieś tutaj Myślę, że mamy całkiem dobry program, który przechowuje jeden student. Oczywiście nie jest to ciekawe, że wszystkie. Co zrobić, jeśli chcę mieć 2 studentów? To nie jest wielka sprawa. Mogę wspierać 2 osób. Pozwól mi iść dalej i podkreślić to i iść na dół, i mogę powiedzieć, "id = 456", dla kogoś takiego jak Rob, który mieszka w Kirkland. Dobra, czekaj, ale nie mogę połączyć te samo, i wygląda na to będę musiał skopiować to, więc pozwól mi powiedzieć, że to będzie Dawida zmienne, i daj mi trochę kopie te dla Rob. Zadzwonimy do nich Roba, ale to nie będzie działać teraz bo-wait, zmieńmy mnie ID1, nazwa1 i House1. Rob będzie 2, 2. Muszę to zmienić, tutaj, tutaj, tutaj, tutaj, tutaj, tutaj. Czekaj, co Tommy? Zróbmy to jeszcze raz. Oczywiście, jeśli nadal uważasz, że jest to dobry sposób w ten sposób, to nie jest, więc kopiować / zły. Ale rozwiązać to tydzień temu. Jakie było nasze rozwiązanie, gdy chcemy mieć wiele instancji tego samego typu danych? [Studenci] tablica. Tablica, więc pozwól mi spróbować wyczyścić to. Pozwól mi zrobić trochę miejsca dla siebie na górze, i pozwól mi zrobić, a nie to tutaj. Nazwijmy tych ludzi, i zamiast ja powiem "INT identyfikatory" i zamierzam wspierać nas 3 na razie. Mam zamiar powiedzieć "Nazwy ciągów", a ja obsługuje 3 z nas, a ja powiem "domy ciąg" i mam zamiar wspierać 3 z nas. Teraz w tutaj zamiast David coraz własne zmienne lokalne możemy pozbyć się tych. Że czuje się dobrze, że mamy to do czyszczenia. Możesz wtedy powiedzieć David będzie [0] i nazwiska [0] i domy [0]. A potem Rob możemy podobnie zapisać na to. Ujmę to w dół tutaj, więc on będzie arbitralnie być ids [1]. On chce być nazwy [1], i wreszcie, domy [1]. Jeszcze trochę nudny, a teraz muszę to rozgryźć, więc powiedzmy, że "nazwiska [0], id [0], domy [0] i niech pluralize to. Identyfikatory, identyfikatory, identyfikatory. I znowu to robię, więc ponownie, jestem już uciekania się do kopiuj / wklej ponownie więc kursy są tam inne rozwiązanie tutaj. Prawdopodobnie mogę oczyścić to się dalej z pętli, czy coś takiego, Tak w skrócie, to jest trochę lepiej, ale nadal czuje się jak Jestem uciekania się do kopiuj / wklej, ale nawet to, jak twierdzą, naprawdę nie jest zasadniczo właściwym rozwiązaniem, ponieważ co jeśli kiedyś zdecydujemy wiesz co? Naprawdę należało przechowywania adresów e-mail dla Dawida i Rob i wszyscy w tym programie. Należy również zapisać numery telefonów. Należy również zapisać numery alarmowy. Mamy te wszystkie fragmenty danych, które chcemy przechowywać, więc jak się do tego zabrać? Zadeklarować kolejną tablicę na szczycie, a następnie ręcznie dodać Adres e-mail [0], e-mail [1] dla Dawida i Rob i tak dalej. Ale jest naprawdę założeniem tego projektu że używam systemu zaszczyt wiedzieć, że [I], w każdym z kilku tablic tak się dzieje w odniesieniu do tej samej osoby, tak [0] w IDS jest numer 123, i mam zamiar założyć, że nazwy [0] to samo nazwisko osoby i domy [0] jest tą samą osobą w domu i tak dalej dla wszystkich różnych tablic, które tworzę. Zauważmy jednak, że nie ma fundamentalne powiązania wśród tych 3 elementów informacji, id, nazwisko i dom, chociaż jednostka staramy się modelu w tym programie nie jest tablicami. Tablice są tylko ten programowy sposób to zrobić. Co naprawdę chcemy modelować w naszym programie jest to osoba jak Dawid, osoba jak Rob wewnątrz której lub dokonującym jest nazwa i ID i house. Czy możemy w jakiś sposób wyrazić tę ideę enkapsulacji którą osoba ma identyfikator, nazwę i dom , a nie uciekać się do naprawdę ten hack której właśnie ufać, że coś wspornika odnosi się do samej istoty ludzkiej w każdym z tych odrębnych tablic? Rzeczywiście możemy to zrobić. Pozwól mi iść wyżej główny na teraz, i pozwól mi stworzyć mój własny typ danych w bardzo po raz pierwszy. Wykorzystaliśmy tę technikę w Scramble, ale tutaj mam zamiar iść dalej i utworzyć typ danych, i wiesz co, będę nazywać to student lub osoba, i mam zamiar używać typedef dla określenia typu. I powiem, że jest to struktura, a ta struktura będzie studenta typu, to mówimy, nawet jeśli jest to trochę stary teraz na mnie. Powiemy "int id". Powiemy "nazwę ciągu." Wtedy możemy powiedzieć, "dom", ciąg więc teraz do końca tych kilku linii kodu Właśnie uczy dzyń, że istnieje typ danych oprócz wskazówki, oprócz łańcuchów, oprócz podwójna, oprócz pływaków. W tej chwili w linii czasu 11, jest teraz nowy typ danych o nazwie studenci, i teraz mogę zadeklarować zmienną studentów gdziekolwiek chcę, więc pozwól mi przejść tu ludzi. Teraz mogę się pozbyć tego, i mogę iść z powrotem do Dawida tutaj i dla Dawida faktycznie mogę powiedzieć, że David, możemy dosłownie nazwać zmienną po sobie, będzie studenta typu. To może wyglądać trochę dziwnie, ale to nie wszystko, co różni od deklarowania coś jako int lub łańcucha lub pacą. Tak się na miano ucznia teraz i jeśli chcę umieścić coś wewnątrz tej struktury Mam teraz korzystać z nowego fragmentu składni, ale to jest bardzo proste, david.id = 123, david.name = "David" w stolicy D i david.house = "Mather" i teraz mogę się pozbyć tych rzeczy tutaj. Zauważ teraz mamy przeprojektowany nasz program w sposób naprawdę dużo lepiej że teraz nasz program odzwierciedla rzeczywisty świat. Jest rzeczywistym świecie pojęcie osoby lub studenta. Tutaj mamy teraz wersję C osoby lub dokładniej jako student. Wewnątrz tej osoby są te istotne cechy, ID, name i dom, więc Rob istocie staje się samo i tutaj, rob tak uczeń, a teraz rob.id = 456, rob.name = "Rob". Fakt, że zmienna nazywa się Rob jest trochę bezsensowne. Mogliśmy nazwał x lub y lub z. My po prostu nazwał go Rob być semantycznie spójne, ale naprawdę nazywa się wewnątrz tego samego pola, więc teraz mam to. To też nie ma ochoty na najlepszy projekt w, że mam twarde zakodowanej Dawida. Mam stałe zakodowany Rob. I wciąż muszą uciekać się do jakiś skopiuj i wklej za każdym razem chcę nowe zmienne. Ponadto muszę najwyraźniej dać każdej z tych zmiennych nazwę, chociaż wolałbym opisać te zmienne  bardziej ogólnie jako studentów. Teraz możemy połączyć idee, które działa dobrze dla nas i zamiast powiedzieć: "Wiesz co, daj mi zmienną studentów, i niech się to być wielkości 3 ", więc teraz mogę ulepszyć ten dalej, pozbyć się ręcznie deklarowanej Dawida a ja zamiast powiedzieć coś studentów [0] tutaj. Możesz wtedy powiedzieć studentom [0] tutaj studentów [0] tutaj, i tak dalej, i mogę obejść i czyste, że się na Roba. Mogłem też iść o teraz może dodanie pętli i korzystania getString i getInt rzeczywiście dostać te wartości od użytkownika. Mogę iść o dodanie stałej, ponieważ na ogół jest to zła praktyka na twardym kod jakiś dowolny numer jak 3 tutaj a potem po prostu pamiętać, że należy umieścić nie więcej niż 3 uczniów w nim. Prawdopodobnie byłoby lepiej użyć # define na górze mojego pliku i czynnikiem, który obecnie, więc rzeczywiście, pozwól mi iść do przodu i generalizować to. Pozwól mi otworzyć się przykładem, który znajduje się między dzisiejszym przykłady z góry, structs1. To jest bardziej kompletny program, który wykorzystuje się tutaj # define i mówi, że będziemy mieć 3 studentów domyślnie. Tutaj jestem uznająca wartość klasy uczniów, tak w klasie uczniów, a teraz jestem za pomocą pętli tak aby kod trochę bardziej elegancki, zapełnić klasy z wyjścia użytkownika, więc iteracyjne od i = 0 dalej do studentów, co stanowi 3. A potem pyta użytkownika w tej wersji  co studenta ID, i mogę go z getInt. Co znajduje się nazwisko studenta, a potem dostać się getString. Co studenta dom? Rozumiem ze getString. A następnie na dole tutaj właśnie zdecydowaliśmy się na zmianę jak mam je z drukowania i faktycznie używać pętli, i kto ja drukowania? Zgodnie z komentarzem Jestem drukowania nikogo w Mather, i to jest tak Rob i Tommy, i tak dalej, a właściwie Tommy w Mather. Tommy i David będą drukowane w tym przypadku, ale jak jest to działa? Nie widzieliśmy tej funkcji przed, ale zgadywać, co to robi. Porównuje łańcuchy. To trochę nieoczywisty jak to porównać ciągi bo okazuje się, jeżeli zwraca 0 co oznacza, że ​​łańcuchy są równe. Jeśli zwróci -1 oznacza przychodzi alfabetycznie przed drugim, i jeżeli zwraca 1 oznacza to, że inne słowo pochodzi alfabetycznie przed innymi, i można sprawdzić online lub na stronie man dokładnie sprawdzić, w jaki sposób jest który, ale to wszystko jest teraz robi to jest mówi jeśli [i]. dom jest równa "Mather" śmiało i wydrukować tak i tak jest w Mather. Ale tu jest coś, czego nie widziałem wcześniej, i wrócimy do tego. Nie przypominam sobie, nigdy o to zrobić w jednym z moich programów. Bezpłatne najwyraźniej myśli pamięci, zwalniając pamięć, ale co ja mam pamięć najwyraźniej uwolnieniu w tej pętli na końcu tego programu? Wygląda to tak, jakbym uwalniając nazwisko osoby a człowiek w domu, ale dlaczego tak jest? Okazuje się, że te wszystkie tygodnie używałeś getString mamy trochę wprowadzało błąd w każdym z programów. GetString według projektu przydziela pamięć tak, że może wrócić do Ciebie strun jak David, czy Rob, i można wtedy robić, co chcesz z tym ciąg w programie, ponieważ mamy zarezerwowanej pamięci dla Ciebie. Problem jest cały czas za każdym razem wywołać getString my, autorzy getString, pytali system operacyjny dać nam trochę pamięci RAM dla tego łańcucha. Daj nam trochę pamięci RAM dla tego kolejnego łańcucha. Daj nam trochę więcej pamięci RAM dla tego kolejnego łańcucha. Co ty, programista, nigdy nie robi daje nam to z powrotem pamięci więc dla tych kilku tygodni wszystkie programy napisałeś mieli co nazywa skok pamięci za pomocą których należy korzystać więcej i więcej pamięci za każdym razem wywołać GetString, i to jest w porządku. Celowo nie jest to w pierwszych tygodniach, ponieważ nie jest tak interesujące mają się martwić, gdzie łańcuch pochodzi. Wszystko czego chcę to słowo Rob wrócić, gdy użytkownik wpisze go w. Ale naprzód teraz musimy zacząć bardziej wyrafinowane o tym. Za każdym razem możemy przydzielić pamięci lepiej ostatecznie oddać go z powrotem. W przeciwnym razie w świecie rzeczywistym na komputerze Mac lub PC możesz mieć czasami doświadczonym objawy, gdzie komputer jest szlifowanie do zatrzymania ostatecznie lub głupi przędzenia piłka plaża jest po prostu zajmując komputera cała uwaga i nie można robić różne rzeczy. , Które mogą być wyjaśnione przez dowolną liczbę błędów, ale wśród tych możliwych błędów Są rzeczy, których nazywa się wycieki pamięci kogoś, kto napisał ten kawałek oprogramowania używasz nie pamiętam w celu zwolnienia pamięci że on lub ona zwróciła się do systemu operacyjnego dla, nie używając getString, bo to CS50 rzecz, ale stosując podobne funkcje że zawiera system operacyjny dla pamięci. Jeśli ty lub oni zepsuć i nigdy nie wrócić, że pamięć objawem, który może być, że program spowalnia i spowalnia i spowalnia chyba pamiętasz zadzwonić darmo. Wrócimy do tego, kiedy i dlaczego nazywacie wolne, ale niech śmiało tylko środek na dobre i spróbuj uruchomić ten konkretny program. Nazywało structs1 wprowadzić. Pozwólcie mi iść do przodu i uruchamiania structs1, 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather i widzimy Dawida w Mather, Tommy w Mather. To jest po prostu trochę Sprawdzanie poprawności, że program działa. Teraz, niestety, ten program jest trochę frustrujące, że w Zrobiłem wszystko, co praca, wpisałem w 9 różnych ciągów, wciskamy Enter, powiedziano mi, kto był w Mather, ale oczywiście wiem, kto był już w Mather bo wpisałeś. To jest, jeśli co najmniej przyjemne Program jest bardziej bazie i faktycznie pamięta, co mam wpisać w więc nigdy nie musiały ponownie input te zapisy studentów. Może to jest jak registrarial systemu. Możemy to zrobić za pomocą tej techniki znanej jako pliku I / O, wejścia i wyjścia plików, bardzo ogólny sposób powiedzieć, kiedy tylko chcesz do odczytu plików lub zapisu plików można to zrobić z pewnym zestawem funkcji. Pozwólcie mi iść do przodu i otworzyć structs2.c przykład, który jest niemal identyczne, ale zobaczymy, co teraz robi. Na początku pliku Oświadczam studentów klasę. Następnie wypełnić klasę wyjścia użytkownika, więc te linie kodu są takie same jak wcześniej. Następnie jeśli przewiń tutaj wydrukować każdy, kto jest w Mather arbitralnie, jak poprzednio, ale jest to interesująca nowa funkcja. Te wiersze kodu są nowe i wprowadzają coś tu Pliku, wszystkie czapki, i to * w tutaj również. Pozwól przenieść to tutaj, a * tu również. Ta funkcja nie widzieliśmy wcześniej, fopen, ale to oznacza plik otwarty, więc niech przejrzeć te, i to jest coś, wrócimy w przyszłym psets, ale ta linia tutaj zasadniczo otwiera plik o nazwie bazy danych, i to specjalnie otwiera go w taki sposób, że może robić to, co do niego? [Niesłyszalne-uczeń] Dobra, więc "w" oznacza po prostu to mówi systemu operacyjnego otworzyć plik w taki sposób, że można w nim zapisu. Nie chcę, aby ją przeczytać. Nie chcę po prostu patrzeć. Chcę to zmienić i dodać rzeczy potencjalnie do niego, a plik ma być nazywany bazy danych. To można nazwać nic. To może być database.txt. To może być. DB. Może to być słowo jak foo, ale samowolnie wybrał nazwę pliku bazy danych. To jest trochę Sprawdzanie poprawności, że wrócimy do bardzo szczegółowo w czasie, jeżeli fp, dla wskaźnika pliku, nie jest równa NULL oznacza to wszystko jest dobrze. Długa historia krótkiego, funkcje takie jak fopen czasami nie. Może plik nie istnieje. Może jesteś z miejsca na płycie. Może nie ma uprawnień do tego folderu, więc jeśli fopen zwraca null coś się stało. Natomiast jeśli fopen nie zwróci null wszystko jest dobrze i mogę zacząć pisać do tego pliku. Oto nowy trick. To jest dla pętli, które jest Iterowanie nad każdym z moich studentów, i wygląda to tak podobne do tego, co zrobiliśmy wcześniej, ale ta funkcja jest kuzynem printf nazywa fprintf dla pliku printf, i zauważ, że jest inaczej w zaledwie 2 sposoby. Jednym, zaczyna f zamiast P ale to jego pierwszy argument jest najwyraźniej co? [Studenci] Plik. >> To jest plik. To coś nazywa fp, które będziemy w końcu odciąć co wskaźnik pliku jest ale teraz fp prostu reprezentuje plik, że mam otwarte, tak fprintf tutaj mówi Wydrukuj to ID użytkownika do pliku, a nie na ekranie. Drukuj nazwę użytkownika do pliku, a nie na ekranie, dom do pliku, a nie na ekranie, a następnie tu, oczywiście, zamknij plik, a następnie w dół tutaj wolne pamięci. Jedyna różnica między tą wersją i wersją 1 2 jest wprowadzenie fopen i ten plik z * i to pojęcie fprintf, więc zobaczymy, co efekt końcowy jest. Pozwól mi iść do mojego okna terminala. Pozwólcie mi biegać structs2 wprowadzić. Wygląda na to, że wszystko jest dobrze. Miejmy powtórka structs2. 123, David Mather, 456, Rob Kirkland, 789, Tommy Mather, enter. Wygląda tak, jak zachowywał się tak samo, ale jeśli teraz zrobić ls zauważyć, co plik jest tutaj wśród całego kodu, bazy danych, więc otwórzmy, że gedit z bazy danych, a popatrz na to. Nie najseksowniejszą formatów plików jest. Jest to naprawdę jeden kawałek linii danych w jednej linii na linię, ale ci z was, którzy korzystają z programu Excel lub CSV plików oddzielone przecinkami wartości, Mogę z pewnością stosowane fprintf, aby zamiast być może coś jak to zrobić tak, że mogę rzeczywiście stworzyć odpowiednik pliku Excel oddzielając przecinkami rzeczy, nie tylko nowych linii. W tym przypadku, gdybym zamiast stosować przecinków zamiast nowe linie Mogłem dosłownie otworzyć plik bazy danych w programie Excel, jeśli zamiast wygladalo to tak. Krótko mówiąc, teraz, że mamy prawo do zapisu plików możemy zacząć utrzymujących dane, uniemożliwiając jej okolice na płycie tak, że możemy przechowywać informacje wokół ponownie i ponownie. Zauważyć kilka innych rzeczy, które są teraz nieco bardziej znajome. W górnej części tego pliku C mamy typedef ponieważ chcieliśmy stworzyć typ danych, który reprezentuje słowo, więc ten typ nazywany jest słowem, a wewnątrz tej struktury to trochę hodowcy teraz. Dlaczego słowo składa się z pozornie tablicy? Co to słowo po prostu intuicyjnie? Jest to tablica znaków. Jest to ciąg znaków z powrotem do tyłu do tyłu. Listów, wszystkie czapki dzieje się nam arbitralnie powiedzieć maksymalna długość każdego słowa w słowniku, które używamy do Scramble. Dlaczego mam 1? Znak null. Przypomnijmy, gdy zrobiliśmy przykład Bananagrams potrzebowaliśmy szczególną wartość na końcu, w celu słowa śledzić , gdzie słowa rzeczywiście skończyło, a jak mówi specyfikacja zestaw problemem tutaj mamy skojarzenie z danym słowem wartość logiczną, flag, by tak rzec, prawda lub fałsz. Znalazłeś już tego słowa, ponieważ zdajemy sobie sprawę, naprawdę potrzebujemy sposobu pamiętania nie tylko to, co słowo to w Scramble ale czy ty, człowiek, znalazłem go tak, że jeśli nie znajdziesz słowa "" nie można po prostu wpisać, wejść,, enter, wprowadź i uzyskać 3 punkty, 3 punkty, 3 punkty, 3 punkty. Chcemy być w stanie do czarnej listy to słowo poprzez bool true jeśli już znalazłem, więc dlatego obudowane to w tej strukturze. Teraz, tutaj w Scramble istnieje ten inny struct nazwie słownika. Nieobecny jest tu słowo typedef ponieważ w tym przypadku musieliśmy ująć ideę słownika i Słownik zawiera całą masę słów, jak wynika z tej tablicy, i jak wiele z tych słów są tam? Cóż, cokolwiek ta zmienna nazywa rozmiar mówi. Ale wystarczy jeden słownik. Nie musimy typ danych o nazwie słownika. Potrzebujemy tylko jednego z nich, więc okazuje się, w C że jeśli nie mówisz typedef, po prostu powiedzieć, struct, a następnie wewnątrz nawiasów klamrowych umieścić swoje zmienne, a następnie umieścić nazwę. Ten deklaruje jeden zmienną słownik który wygląda tak. Natomiast linie te są wielokrotnego użytku, tworząc strukturę danych o nazwie słowo że można tworzyć wiele kopii, jak stworzyliśmy wiele kopii studentów. Co to w końcu pozwoli nam to zrobić? Pozwól mi wrócić do, powiedzmy, prostszy przykład z prostszych czasów, i pozwól mi otworzyć się, powiedzmy, compare1.c. Problem w kasie jest faktycznie odwinąć warstwa ciąg i rozpocząć wyłączyć te kółka bo okazuje się, że ciąg ten cały czas jest jak obiecaliśmy w tydzień 1 tak naprawdę pseudonim, synonim od CS50 bibliotece dla czegoś, co wygląda trochę bardziej tajemniczy, char *, a my widzieliśmy ten gwiazda przed. Widzieliśmy to w kontekście plików. Spróbujmy teraz zrozumieć, dlaczego mamy ukrywał tę informację od jakiegoś czasu. Tutaj jest plik o nazwie compare1.c, i najwyraźniej prosi użytkownika o 2 ciągi, S i T, , a następnie stara się porównać tych ciągów dla równości w linii 26, i czy są one równe, że mówi: "wpisane samo" i jeśli nie są one równe mówi "Wpisano różne rzeczy." Pozwól mi iść dalej i uruchomić ten program. Pozwól mi iść do mojego katalogu źródłowego, zrobić compare1. Jest opracowany w porządku. Pozwólcie mi biegać compare1. Ja powiększyć, enter. Powiedz coś. Hello. Powiem coś jeszcze raz. Hello. Zdecydowanie nie wpisać różne rzeczy. Pozwól mi spróbować jeszcze raz. BYE BYE. Zdecydowanie nie inna, więc to, co tu się dzieje? Cóż, to, co naprawdę jest w porównaniu z linią 26? [Niesłyszalne-uczeń] Tak, więc okazuje się, że łańcuch, typ danych, to rodzaj białego kłamstwa. Ciąg jest char *, ale co jest char *? Char *, jak mówią, jest wskaźnik, i wskaźnik jest skutecznie adres, lokalizacja suma w pamięci, a jeśli zdarzy się, że wpisane w słowa jak HELLO, pamiętam z poprzednich dyskusji ciągów to jest jak słowo hello. Pamiętaj, że słowo takie jak Halo może być reprezentowany jako tablica znaków, podobnie jak to , a następnie w postaci specjalnego koniec zwany znak pusty, jako \ oznacza. Co to jest rzeczywiście ciąg? Zauważ, że jest to kolejne fragmenty pamięci, i faktycznie, jego koniec jest znany jedynie raz przejrzeć cały ciąg szukasz specjalnego znaku pustego. Ale jeśli jest to fragment pamięci z mojej pamięci komputera, niech arbitralnie powiedzieć, że ten ciąg po prostu mieliśmy szczęście, i dostałem umieszczony na samym początku mojej pamięci RAM komputera. Ten bajt jest 0, 1, 2, 3, 4, 5, 6 ... Kiedy mówię, że coś takiego getString i zrobić string s = getString co tak naprawdę są zwracane? Dla tych ostatnich kilku tygodni, co naprawdę są przechowywane w s nie jest to łańcuch per se, ale w tym przypadku, co jest przechowywane 0 liczba, ponieważ to, co faktycznie robi GetString jest to fizycznie nie zwracać ciąg. To nawet nie naprawdę koncepcyjny sens. Co robi zwrot jest liczba. Ta liczba jest adres WITAJ w pamięci, i ciąg s wtedy, jeśli ta warstwa odwinąć, string nie istnieje naprawdę. To tylko uproszczenie w CS50 biblioteki. To naprawdę jest coś, co nazywa char *. Char ma sens, bo co to słowo, podobnie jak Halo? Cóż, to jest seria znaków, ciąg znaków. Char * oznacza adres znaku, więc co to znaczy zwracać ciąg? Ładny, prosty sposób powrotu ciąg to zamiast spróbować dowiedzieć się, jak wrócę do 5 lub 6 różnych bajtach Pozwól mi wrócić do adresu, który bajt? Pierwszy. Innymi słowy, dam ci adres znaku w pamięci. To, co char * reprezentuje, adres jednego znaku w pamięci. Zadzwoń do tej zmiennej s. Sklep w s, że dany adres, którą arbitralnie powiedział jest 0, żeby zachować rzeczy proste, ale w rzeczywistości jest to zazwyczaj większa liczba. Chwileczkę. Jeśli tylko daje mi adres pierwszego znaku, czy ja wiem, co adres drugi znak, trzeci, czwarty i piąty? [Niesłyszalne-uczeń] Musisz tylko wiedzieć, gdzie koniec łańcucha jest w drodze tej poręcznej trick, więc kiedy używać coś jak printf, co printf dosłownie wymaga jako argumentu, Przypomnijmy, że używamy tego zastępczy% s, a następnie przechodzą w Zmienna jest przechowywanie ciąg. Co naprawdę przechodzącej jest adres pierwszego znaku tego łańcucha. Printf wykorzystuje następnie do pętli lub pętli while po otrzymaniu tego adresu, na przykład 0, więc pozwól mi to zrobić teraz, printf ("% s \ n", s); Kiedy dzwonię do printf ("% s \ n", s); co jestem naprawdę dostarczanie printf z to adres pierwszego znaku w s, który w tym przypadku jest arbitralny H. Jak printf wiedzieć, co dokładnie, aby wyświetlić na ekranie? Osoba, która realizowana printf realizowane pętli while lub do pętli mówi, że to ma charakter szczególny charakter równy NULL? Jeśli nie, to wydrukować. Jak o tym? Jeśli nie drukować, drukować, drukować, drukować. Oh, ten jest wyjątkowy. Zatrzymaj drukowanie i powrócić do użytkownika. I to dosłownie wszystko, co dzieje się pod maską, i to dużo do strawienia w pierwszym dniu klasy, ale teraz to naprawdę budulcem wszystkiego zrozumienia który jest już od wewnątrz naszej pamięci komputera, i ostatecznie będziemy drażnić to apart z niewielką pomocą od jednego z naszych przyjaciół w Stanford. Profesor Nick Parlante w Stanford zrobił ten wspaniały sekwencji wideo od wszelkiego rodzaju różnych językach, które wprowadziły ten mały znak Claymation Binky. Głos masz zamiar usłyszeć w kilku podglądu sekund zaskoczenia jest to, że z Stanford profesora i dostajesz tylko 5 lub 6 sekund to teraz, ale to jest uwaga na której możemy stwierdzić dziś i rozpocznie się w środę. Daję ci Fun wskaźnik z Binky, podglądu. [♪ Muzyka ♪] [Profesor Parlante] Hey, Binky. Obudź się. To jest czas na zabawę wskaźnika. [Binky] Co to jest? Dowiedz się o wskaźniki? Oh, cukierek! Do zobaczenia w środę. [CS50.TV]