>> DAVID MALAN: Dobrze, witamy z powrotem.
To CS50.
To jest początek tygodnia siedem.
Więc to był czas, więc myślałem, że bym podjąć wicher wycieczkę gdzie
skończył i gdzie jesteśmy teraz dzieje.
>> Więc to, co tutaj może mieć wywołało niepokój w pierwszym.
Ale miejmy nadzieję, że zaczynasz zaaklimatyzować się, co to oznacza tutaj -
Standard stanowi wskaźnik, który jest tylko to, co w więcej laika?
Więc to jest adres.
>> Więc jest to adres coś w pamięci.
I zaczęliśmy się odwinąć warstwy Kilka tygodni temu, rzeczy takie jak
GetString i inne takie funkcje przez cały ten czas były powrocie
Adresy rzeczy w pamięci, podobnie jak adres pierwszego znaku
niektórych sekwencji.
>> Więc my też wprowadzone Valgrind, które zaczniesz korzystać z tego problemu
ustaw, w szczególności dla następnego Problem ustawić również.
I valgrind co robi dla nas?
Sprawdza, czy nie ma wycieków pamięci, a to także sprawdza nadużycia pamięci.
>> To może, z pewnym prawdopodobieństwem, wykryć, czy Twój kod będzie dotykać pamięci
że po prostu nie powinno.
Więc niekoniecznie przeciek, ale jeśli wykracza poza granice niektórych
array, a faktycznie uruchomić valgrind i wywoływać takie zachowanie podczas
valgrind działa w programie jest działa w jej wnętrzu, dostaniesz
wiadomości takie jak ta - "nieprawidłowy zapis rozmiar 4 ", który, przypominam kilka
tydzień temu oznaczało, że musiałem przypadkowo jak na jednym zbyt int
poza granice tablicy.
A więc rozmiar 4 oznacza tutaj rozmiar tego konkretnego int.
>> Więc wziąć pewność w tym, że valgrind wyjście, format nim,
jest po prostu okropna.
To naprawdę trudne, aby zobaczyć przez bałagan do ciekawych informacji.
Więc co zrobiliśmy tutaj jest tylko fragment niektóre z kilku więcej
ciekawe linie.
Ale świadomość, że 80% z tych valgrind Wyjście będzie nieco
roztargnienie.
>> Wystarczy spojrzeć na kierunkach takich jak te - nieważne prawo, nieważne czytać, 40 bajtów
a niektóre liczba bloków są zdecydowanie utracone, słowa kluczowe, takie jak to.
A co można mam nadzieję zobaczyć pewne rodzaj śladu co funkcjonować
błąd jest rzeczywiście w.
W tej sprawie, w jakim linia Kod był mój błąd widocznie?
>> 26 w pliku o nazwie memory.c, co było przykład graliśmy z
w tym czasie.
Więc to chyba nie w malloc.
To było prawdopodobnie w kodzie, zamiast.
Więc zobaczymy, to jeszcze raz i znowu niedługo.
>> Więc scanf, ten wpadł w Kilka form dotychczas.
Widzieliśmy sscanf krótko.
To coś liczba Ci zanurkował w telefonie
przygotowania do quizu.
I scanf jest rzeczywiście to, co CS50 Biblioteka został przy użyciu pod
kaptur od dłuższego czasu w celu , aby uzyskać informacje od użytkownika.
>> Na przykład, jeśli przejście na CS50 Urządzenie tutaj, pozwól mi otworzyć
Przykład dziś to się nazywa scanf-0.c I to jest bardzo proste.
To tylko kilka linii kodu.
Ale to pokazuje, naprawdę jak getInt pracuje cały ten czas.
>> W tym programie tu, w linii 16 Zauważ, że oświadczam, int.
Tak więc nie ma wskazówek, nic magicznego tam, po prostu int.
Następnie w linii 17, I zapyta Użytkownik dla wielu, proszę.
Następnie pod koniec 18, używam scanf tutaj.
I określić, trochę jak printf, że czekam na wycenę
cytatu procent i..
>> Tak więc procent i, oczywiście, oznacza int.
Zauważmy jednak, co drugi argument scanf jest.
Jak opisałbyś sekund Argument po przecinku?
Co to jest?
>> To adres x.
Więc to jest przydatne, ponieważ poprzez dostarczanie scanfa z adresem X, co czyni
które upoważniają tę funkcję do zrobienia?
Nie tylko tam, ale także zrobić co?
>> Wprowadzić zmiany do niego.
Bo można tam pojechać, to rodzaj jak mapa do lokalizacji w pamięci.
I tak długo, jak zapewnić scanf lub Każda funkcja z taką mapę, to
Funkcja może tam pojechać, i nie tylko spojrzeć na wartości, ale może również
zmienić tę wartość, co jest przydatne w przypadku celem w życiu jest do scanf
skanowania danych od użytkownika, w szczególności z klawiatury.
I f oznacza sformatowany, tak jak printf, f oznacza sformatowany
Ciąg, który chcesz wydrukować.
>> Tak w skrócie, to 18 linii po prostu mówi, próby odczytu int z instrukcji
klawiatury i przechowywać go w środku x, w bez względu na adres x zdarza się żyć w.
I wtedy wreszcie, wiersz 19 mówi tylko, dzięki za int, w tym przypadku.
>> Więc pozwól mi iść dalej i zrobić to.
Tak zrobić scanf 0.
Pozwólcie mi iść do przodu i powiększyć obraz
Pójdę i uruchomić to z dots slash scanf 0.
Numer, proszę?
50.
Dzięki za 50.
Więc jest to bardzo proste.
>> Teraz nie jest to, co robi?
To nie robi całą masę od sprawdzania błędów.
Na przykład, jeśli nie współpracują, i nie mam wpisać numer, ale
zamiast napisać coś w stylu "hello" to tylko jakieś dziwne.
I tak, jedną z rzeczy, CS50 biblioteka została robi dla nas dla niektórych
czasu jest to, że reprompting i reprompting.
>> Spróbuj przypomnieć zdanie było w cs50.c, i to jest powodem, że getInt w
Biblioteka CS50 jest właściwie cały Kilka linii długich, ponieważ jesteśmy
sprawdzanie głupich rzeczy, jak ta.
Nie dają użytkownikowi nas, w rzeczywistości, Int.?
Czy on lub ona dać nam coś jak alfabetycznej liście?
Jeśli tak, chcemy wykrywać że i krzyczeć na nich.
>> Ale robi się ciekawiej w tym przykładzie.
Jeśli pójdę do scanf-1c, co jest jednym rzecz, która jest zasadniczo zmieniło w
to następny przykład?
Używam char *, oczywiście, zamiast int.
>> Więc to jest ciekawe, bo char *, przypominam, jest tak naprawdę
samo jak łańcuch.
Więc jest to jak może to jest super prosta realizacja GetString.
Ale już obrane z powrotem warstwę z CS50 bibliotece, więc jestem
wywołanie tej char * teraz.
Zobaczmy więc, gdzie, jeśli w dowolnym miejscu, my się nie udać.
>> Linia 17 -
I jeszcze powiedzieć, proszę mi dać coś, w tym przypadku, łańcuch.
A potem, w następnej linii, wzywam scanf, ponownie, nadając mu kod formatu,
ale to s procent czasu.
I wtedy ten czas, jestem dając to bufor.
>> Zauważcie, nie używam Ampersand.
Ale dlaczego jest to, że prawdopodobnie OK tutaj?
Bo to, co jest bufor już?
To już wskaźnik.
To już adres.
>> I niech to słowo "mylić", pozwól mi po prostu nazwać to s, na przykład, na
prostota.
Ale ja nazywa to bufor, bo w ogólnego, w programowaniu, jeśli masz
fragment pamięci, który ciąg naprawdę po prostu jest, można nazwać to bufor.
Jest to miejsce do przechowywania informacji.
>> Podobne do rzeczy, takich jak YouTube, kiedy oni buforowanie, by tak rzec, że
Oznacza to po prostu pobierając bity z internetu i przechowywanie ich w
local tablica, lokalne fragment pamięci tak że można oglądać je później bez
to pomijanie lub wiszące ci podczas odtwarzania.
>> Więc nie ma problemu tutaj chociaż, bo mówię scanf, spodziewać
ciąg od użytkownika.
Oto adres fragment pamięci.
Umieść ten ciąg tam.
Dlaczego jest to, że związany dać nam kłopoty, choć?
>> Co to jest?
Czy mogę uzyskać dostęp do że część pamięci?
Wiesz, nie wiem.
Ponieważ jest bufor został zainicjowany do niczego?
Nie bardzo.
I tak to jest to, co my już dzwoni wartość śmieci, które
nie jest formalny wyraz.
To po prostu oznacza, że ​​nie mamy pojęcia, co bity są w środku z czterech bajtów
I przyznajemy jako bufor.
>> I nie nazywa malloc.
Ja na pewno nie nazywa GetString.
Więc kto wie, co jest w rzeczywistości wewnątrz bufora?
A jednak mówi scanf ślepo, tam i umieścić co użytkownik wpisał.
>> Więc co może powodować w naszym kodzie, jeśli go uruchomić?
Prawdopodobnie wysypać.
Może nie, ale prawdopodobnie wysypać.
A ja mówię nie, bo czasami może ty, czasami
nie dostaniesz wysypać.
Czasami po prostu miał szczęście, ale to jednak będzie
błąd w naszym programie.
>> Więc pozwól mi iść dalej i skompilować.
Mam zamiar zrobić to stary sposób szkoła.
Więc kreska dzyń 0, scanf-1, scanf-1.c, Enter.
Ups, too old school.
Zobaczymy.
Gdzie pójdę?
Oh, bufor * char.
Och, dziękuję -
Zapisz, OK -
bardzo stara szkoła.
W porządku, to był czas.
>> Tak już po prostu zapisany plik po co, że tymczasowe
zmienić chwilą.
I teraz mam skompilowane go ręcznie z Clang.
A teraz mam zamiar iść do przodu i uruchomić scanf-1, Enter.
String proszę.
Będę pisać w "hello".
>> A teraz, tutaj, gdzie, szczerze mówiąc, printf może to trochę irytujące.
To nie jest rzeczywiście będzie segfault w tym przypadku.
Printf jest trochę wyjątkowy, bo to jest tak bardzo powszechnie stosowane, że
zasadniczo printf robi nam przysługę i realizacji,
Nie ważne, że wskaźnik jest.
Pozwól mi wziąć to na siebie, po prostu wydrukować w nawiasach wartości null, nawet
choć nie jest to koniecznie, co sami z oczekiwaniami.
>> Tak naprawdę nie możemy łatwo wywołać wysypać się z tego, ale wyraźnie to
nie jest zachowanie chciałem.
Więc co jest proste rozwiązanie?
Cóż, w scanf-2, pozwól mi zaproponować zamiast właściwie tylko przydzielenie
char *, pozwól mi być trochę mądrzejszy o to i daj mi przydzielić bufor
jako ciąg 16 znaków.
>> Więc można zrobić to w kilka sposobów.
Mogę absolutnie używać malloc.
Ale mogę wrócić do tygodnia dwóch, gdy Potrzebne mi całą masę
znaków.
To tylko tablica.
Więc pozwól mi zamiast przedefiniować bufor się tablica z 16 znaków.
>> A teraz, kiedy mijam bufor w -
i to jest coś, czego nie zrobił mówić w drugim tygodniu -
ale można traktować tablicę jako choć to adres.
Technicznie, jak widzieliśmy, są one trochę inaczej.
Ale scanf nie przeszkadza jeśli przekazana Nazwa tablicy, bo to, co
Szczęk zrobi dla nas, jest w istocie traktować nazwę tej tablicy jako
adres fragmencie 16 bajtów.
>> Więc to jest lepiej.
Oznacza to, że teraz mam nadzieję, że mogę wykonaj następujące czynności.
Pozwól mi oddalić się na chwilę i robią scanf-2, skompilowany OK.
Teraz pozwól mi nie dostaje slash scanf-2.
String proszę. "Hello". I to wydawało się do pracy i tym razem.
>> Ale może ktoś zaproponować scenariusz , w którym nie może nadal działać?
Tak?
Coś więcej niż 16 znaków.
I rzeczywiście, możemy być trochę bardziej precyzyjne.
Coś dłuższy niż 15 znaków, bo naprawdę musimy pamiętać,
że musimy, że backslash zera pośrednio na końcu łańcucha,
co jest poza scanf zazwyczaj dbać o nas.
>> Więc pozwól mi zrobić coś takiego -
czasami po prostu może zostawić go tak.
OK, więc mamy teraz wywołane nasza wina segmentacja.
Dlaczego?
Bo wpisane do ponad 15 znaków, a więc mamy naprawdę
dotknął pamięci, że rzeczywiście nie powinien mieć.
>> Więc co tak naprawdę rozwiązanie tutaj?
A co, jeśli potrzebujemy dłuższy ciąg?
Cóż, być może zrobi to 32 bajtów.
A co, jeśli to nie jest wystarczająco długi?
Jak około 64 bajtów?
A co, jeśli to nie jest wystarczająco długi?
Jak około 128 lub 200 bajtów?
Co tak naprawdę jest rozwiązaniem tutaj ogólnym przypadku, jeśli nie wiemy, w
naprzód, co użytkownik będzie wpisać?
>> To tylko rodzaj wielkim bólem w dupie, Szczerze mówiąc, dlatego
CS50 biblioteka ma kilka linii tuzin Kod, który wspólnie realizować
GetString ciąg w sposób, że nie trzeba z góry wiedzieć, co
Użytkownik ma wpisać.
W szczególności, jeśli spojrzeć na cs50.c z dwa tygodnie temu, zobaczysz
że GetString faktycznie robi nie używać scanf w ten sposób.
Raczej, odczytuje jeden znak na raz.
>> Ponieważ jeden Zaletą czytając jeden znak jest to możliwe
gwarantuje się, aby zawsze mieć co najmniej jeden char.
Mogę tylko zadeklarować char, a następnie naprawdę te kroki tylko dziecko
Przeczytaj o jeden znak w co razem z klawiatury.
A potem, co zobaczysz GetString robi to za każdym razem skończy się,
powiedzmy, 16 bajtów pamięci, wykorzystuje malloc lub jej kuzyn, do
przydzielić więcej pamięci, kopiowanie starych pamięci do indeksowania nowych, a następnie
razem, coraz jeden znak na raz, a kiedy skończy się, że
fragment pamięci, rzuca ją, chwyta większy fragment pamięci, kopiuje stary
do nowych i powtórzeń.
I to jest naprawdę ból rzeczywiście zaimplementować coś tak proste, jak
się wkład ze strony użytkownika.
>> Więc można użyć scanf.
Można stosować inne podobne funkcje.
I wiele podręczników i online przykłady zrobić, ale oni wszyscy
narażone na problemy takie jak ten.
I w końcu, coraz segfault jest trochę denerwujące.
To nie jest dobre dla użytkownika.
>> A w najgorszym przypadku, co czyni to zasadniczo połóż
Kod na ryzyko?
Jakiś rodzaj ataku, potencjalnie.
Rozmawialiśmy o jednym takim ataku - przepełnienia stosu.
Ale w ogóle, jeśli wolno przepełnienie bufora, tak jak my
Kilka tygodni temu, ze tylko pisanie więcej niż "hello" na stosie, to
rzeczywiście może przejąć, potencjalnie, Komputer, lub przynajmniej na dane, które
nie należy do Ciebie.
>> Tak w skrócie, to dlaczego mamy te kółka.
Ale teraz, zaczynamy je zdjąć, jak nasze programy nie są już potrzebne,
Niekoniecznie, wejście od użytkownika.
Ale w przypadku problemu ustawić sześć, Twój wkład będzie pochodzić z ogromnym
plik słownika z 150 niektórych dziwne tysiąc słów.
>> Więc nie musisz się martwić o Użytkownik ma arbitralne wejście.
Będziemy Ci pewne założenia o tym pliku.
Wszelkie pytania na temat wskaźników lub scanf lub wprowadzane przez użytkownika w ogóle?
>> W porządku, więc szybkie spojrzenie, a następnie w jednej ciągnąc wątek z dwa tygodnie temu.
I to było to pojęcie struktury.
Nie dlatego, że - to pojęcie struct, co było, co?
Co struct dla nas zrobić?
>> Zdefiniuj -
Przepraszam?
Zdefiniuj typ zmiennej.
Tak jakby.
Jesteśmy naprawdę połączenie dwóch tematów.
Więc z typedef, przypominam, że możemy zadeklarować typ własne, jak
synonimem, jak napis na char *.
Ale za pomocą typedef i struct, możemy stworzyć prawdziwie własnych struktur danych.
>> Na przykład, jeśli wrócę do gedit tu tylko na chwilę, a ja śmiało
i zrobić coś, chciałbym zapisać to jak, powiedzmy, structs.c
czasowo, mam zamiar iść do przodu i to
standardio.h, int main void.
A potem tutaj, załóżmy, że chcę napisać program, który przechowuje
wielu studentów z różnych domy, na przykład.
Tak to jest jak registrarial Baza danych pewnego rodzaju.
>> Więc jeśli trzeba nazwisko jednego studenta, I może zrobić coś jak char * name,
i zrobię coś takiego -
faktycznie, użyjmy CS50 biblioteki na chwilę, aby to
trochę prostsze, więc możemy pożyczyć te dziesiątki linii kodu.
I niech po prostu keep it simple.
Będziemy to ciąg, i teraz GetString.
>> Więc twierdzą teraz, że mam zapisane nazwisko jakiegoś studenta, a domem
niektórych studentów, po prostu za pomocą zmiennych tak jak my w tygodniu jeden.
Ale przypuśćmy, że teraz chcą wspierać wielu studentów.
W porządku, więc moje instynkty są do zrobienia Ciąg name2, dostaje GetString, ciąg
house2 dostaje GetString.
A potem nasz trzeci uczeń, zróbmy NAME3 GetString.
>> W porządku, więc mam nadzieję, że jest to uderzające Ty jako głupie,
, ponieważ proces ten jest bardzo nigdy się skończy, a to po prostu będzie
aby mój kod wygląda gorzej i coraz gorzej.
Ale rozwiązaliśmy to też w drugim tygodniu.
Jaki był nasz stosunkowo czyste rozwiązanie kiedy mieliśmy wielu zmiennych
samego typu, które są związane, ale nie chcemy tego okropne bałagan
z podobnie nazwanych zmiennych?
Co możemy zrobić w zamian?
>> Więc myślę, że słyszałem kilka miejsc.
Mieliśmy tablicę.
Jeśli chcesz wiele wystąpień coś, czemu nie możemy oczyścić to wszystko
się i po prostu powiedzieć, daj mi array nazwie nazwy?
>> A teraz, niech ciężko 3 kodu.
A potem dał mi kolejną tablicę zwane domy, i niech mnie
teraz trudno kod 3.
A ja masowo posprzątać bałagan, że po prostu stworzony.
Teraz, mam wciąż trudno kodowane 3, ale nawet 3 może dynamicznie pochodzą z
Użytkownik lub argv lub tym podobne.
Tak to już jest czystsze.
>> Ale to, co jest irytujące jest to, że teraz, choć nazwa jest w jakiś sposób
zasadniczo związane dom studenta -
to student, że naprawdę chcą reprezentować -
Mam teraz dwie tablice, które są równoległe w tym sensie, że są one
Uchwyt sam rozmiar i nazwy 0 przypuszczalnie mapy do wspornika domy 0,
i nazwy Uchwyt 1 mapy do domów wspornik 1.
Innymi słowy, że studenckie życie w że dom, i że inne uczeń
mieszka w tym drugim domu.
Ale na pewno może to być zrobić jeszcze bardziej czysto.
>> Cóż, może w rzeczywistości.
I pozwól mi iść do przodu i otworzyć up structs.h, i będziesz
zobacz ten pomysł tutaj.
Zauważmy, że użyłem typedef, jak ty wspomniał chwilę temu uznaniu naszej
własny typ danych.
Ale jestem również za pomocą tego inne słowa kluczowe nazywa struct które daje mi nowe
Struktura danych.
>> I to struktura danych Twierdzę będzie mieć dwie rzeczy wewnątrz
it - ciąg nazwie name, i ciąg zwany dom.
A imię mam zamiar dać to struktura danych będzie
na miano ucznia.
Mogę nazwać to na co mam ochotę, ale semantycznie zrobić
sens dla mnie w mojej głowie.
>> Więc teraz, jeśli otworzy lepszą wersję programu zacząłem pisać
tam, pozwól mi przejść do góry.
I jest jeszcze kilka linii kodu tutaj, ale pozwól mi skupić się na
Moment na jednego.
I już ogłoszony stale zwane studentów i trudno kodowane 3 teraz.
Ale teraz, zauważyć, jak czyste mój kod zaczyna się dostać.
>> W linii 22, oświadczam array studentów.
I zauważyć, że uczeń jest najwyraźniej teraz typ danych.
Ponieważ na początku tego pliku, zawiadomienia Podaję ten plik nagłówka
że zatrzymał się przed chwilą.
I że plik po prostu miał nagłówek ta definicja studenta.
>> Więc teraz, stworzyłem swoje własne dane typ, że autorzy roku C
temu nie sądziłem, że z wyprzedzeniem.
Ale nie ma problemu.
Mogę zrobić to sam.
Więc to jest tablica o nazwie studentów, każdy z jej członków
jest struktura studentów.
A ja chcę te trzy w tablicy.
>> A teraz, co robi reszta tego programu zrobić?
Potrzebowałem czegoś niepożądanego.
Tak więc od teraz 24 począwszy, I iteracji od 0 do 3.
I następnie prosi użytkownika o nazwisko studenta.
A potem używam GetString jak wcześniej.
Następnie proszę o domu studenta, i używam GetString jak wcześniej.
>> Ale uwaga - nieco nowy Kawałek składni -
I może jeszcze wskaźnik do i-tego ucznia, ale w jaki sposób dostać się do konkretnych danych
wewnątrz pola tej struktury?
No, co jest najwyraźniej nowy kawałek składni?
To jest po prostu operator kropki.
>> Nie Naprawdę widziałem tego wcześniej.
Widziałeś go w Pset pięć Jeśli zanurkował w już z plików bitmapowych.
Ale kropka oznacza tylko wewnątrz tego struct lub wiele pól, dać kropkę
Nazwa, lub dać mi dot dom.
Oznacza to, że do środka tej struktury i dostać te poszczególne pola.
>> Co reszta tego programu zrobić?
To nie wszystko, że sexy.
Należy zauważyć, że iteracyjne od 0 do 3 Również a ja po prostu stworzyć English
Zwrot jak tak i tak jest w taki a taki dom, przekazując dot nazwy od
i-studentów i ich dom również.
>> I wtedy wreszcie, teraz zaczniemy dostać anal o tym, że teraz jesteśmy
zna co malloc i inne funkcje zostały
robi cały ten czas.
Dlaczego muszę uwolnić zarówno nazwę i dom, mimo że
nie wywołać malloc?
>> GetString zrobił.
I to był brudny mały sekret dla kilka tygodni, ale GetString ma
był wyciek pamięci na całym umieścić wszystkie semestr do tej pory.
I Valgrand ostatecznie ujawnić to do nas.
>> Ale nie jest to wielka sprawa, bo wiem, , że można po prostu zwolnić nazwę
i dom, choć technicznie, do jest super, super bezpieczne, powinien być
robi jakiś błąd sprawdzenia tutaj.
Co twój instynkt mówi ci?
Co mam być sprawdzanie przed I uwolnić to, co jest
ciąg, aka, które char *?
>> Mam naprawdę być sprawdzenie, czy uczniowie Uchwyt i nazwa dot nie
równa null.
Wtedy to będzie OK, aby przejść dalej i za darmo , że wskaźnik, i takie same lub inne
równie dobrze.
Jeśli uczniowie wspornik i kropka dom nie jest równa wartości null, to teraz będą chronić
w stosunku do przypadku, w którym rogu GetString zwraca coś null.
I widzieliśmy przed chwilą, printf będzie chronią nas tu tylko, że
null, która będzie wyglądać dziwnie.
Ale przynajmniej nie będzie wysypać, jak już widzieliśmy.
>> Cóż, pozwól mi zrobić jedną rzecz tutaj. structury-0 to rodzaj głupiego programu
bo wprowadzić wszystkie te dane, a następnie to porażka po zakończeniu programu.
Ale pozwól mi iść dalej i zrobić to.
Pozwól, że terminal Okno nieco większe.
Pozwól mi elemencie-1, które jest nowa wersja tego.
>> Będę powiększyć trochę.
A teraz pozwól mi uruchomić kropkę slash elemencie-1.
Nazwa Studenta -
David Mather, zróbmy Rob Kirkland, zróbmy Lauren Leverett.
Co ciekawe, to uwaga -
i wiem tylko to, ponieważ Napisałem program -
Plik jest teraz na mój obecny katalog o nazwie students.csv.
Niektórzy z was mogą nie widziałem te w realnym świecie.
>> Co to jest plik CSV?
Oddzielone przecinkami wartości.
To trochę tak jak biednych wersja pliku Excel.
To stół z wierszy i kolumn, które można otworzyć w programie, takich jak Excel,
lub numerów na komputerze Mac.
>> A jeśli mogę otworzyć ten plik tutaj na gedit, Ogłoszenie - i numery nie są.
To tylko gedit mówi mnie numery linii.
Zwróć uwagę na pierwszej linii tego plik jest David i Mather.
Następna linia jest Rob przecinek Kirkland.
I trzecia linia jest Lauren przecinek Leverett.
>> Więc co ja stworzony?
I już teraz napisany program w C, który skutecznie może generować arkusze kalkulacyjne
które można otworzyć w program jak Excel.
Nie wszystko, co atrakcyjne zestaw danych, ale jeśli masz dużo większe kawałki
dane, które rzeczywiście chcą manipulowania i zrobić wykresy i
podoba, jest to chyba jeden sposób tworzenia tych danych.
Co więcej, pliki CSV są rzeczywiście bardzo powszechne tylko do przechowywania prostych danych -
Yahoo Finance, na przykład, jeśli masz notowania akcji poprzez ich tzw
API, bezpłatna usługa, która pozwala uzyskać aktualny up-to-aktualne akcji
cytaty dla firm, ich przekazania tych danych w
super prosty w formacie CSV.
>> Więc jak to zrobić?
Cóż zauważyć, większość z tego programu-tych prawie takie same.
Jednak zauważyć tu, a nie do druku uczniom uwagę, na linii 35
naprzód, I twierdzą, że mam oszczędności studentów na dysku, więc zapisanie pliku.
>> Więc zauważyć jestem uznającej plikach * -
teraz, jest to rodzaj anomalii w C. Z jakiegoś powodu, FILE to wszystkie czapki,
co nie jest jak większość innych typów danych w C. Ale to jest wbudowany
Typ danych, * FILE.
A ja deklarując wskaźnik do pliku, jest to, jak można myśleć, że.
>> fopen oznacza otwarty plik.
Co plik chcesz otworzyć?
Chcę otworzyć plik, który będę arbitralnie nazywają students.csv.
Mogę nazwać to co zechcę.
>> A potem zgadywać.
Co robi drugi argument do fopen prawdopodobnie na myśli?
Prawo, w do zapisu, może być r do odczytu.
Jest dla dołączania jeśli Aby dodać wiersze, a nie
nadpisać całość.
>> Ale ja po prostu chcę, aby utworzyć ten plik raz, więc użyję cytatu cytatu w.
I wiem, że tylko od odczytu po dokumentacja, lub strona man.
Jeśli plik nie jest zerowy - innymi słowy, jeśli nic się nie udało tam -
pozwól mi iteracji studenci od 0 do 3.
>> A teraz zauważył, że coś bardzo nieznacznie różni
o linii 41 tutaj.
To nie jest printf.
To fprintf do pliku printf.
Tak to się zapisać do pliku.
Który plik?
Jeden, którego wskaźnik określić jako pierwszy argument.
>> Następnie określić ciąg formatu.
Następnie określamy, co chcemy, aby ciąg wtyczka w pierwszy s procent, a
następnie innej zmiennej lub sekunda s proc.
Następnie zamykamy plik z fclose.
Niż I uwolnić pamięć jak wcześniej, choć Powinienem wrócić i dodać
niektóre sprawdza null.
>> I to jest to.
fopen, fprintf, fclose daje mi Zdolność do tworzenia plików tekstowych.
Teraz zobaczysz w zestawie problemu pięciu, która obejmuje obrazy, będziesz używać
pliki binarne zamiast.
Ale zasadniczo chodzi o to samo, mimo poprawnego będziesz
zobaczyć to trochę inaczej.
>> Więc wycieczka wicher, ale dostaniesz zbyt zaznajomieni z pliku I/O--
wejście i wyjście - z Pset pięć.
A wszelkie pytania dotyczące Początkowe podstawy tutaj?
Tak?
>> Co jeśli spróbujesz uwolnić wartość null?
Wierzę, chyba wolne ma zdobyć trochę bardziej przyjazny dla użytkownika, można
potencjalnie wysypać.
Podanie to wartość null jest złe, bo nie mam uwierzyć darmo przeszkadza, by sprawdzić dla was,
bo to potencjalnie odpady czasu na to, aby zrobić się na
każdy na świecie.
Dobre pytanie, choć.
>> W porządku, więc tego rodzaju ma nam ciekawy temat.
Tematem zbioru problemowego pięć jest kryminalistyki.
Przynajmniej to jest część zestawu problemów.
Forensics ogólnie odnosi się do odzyskiwanie informacji, które mogą,
może nie zostały usunięte celowo.
I tak myślałem, że daje szybkie Smak tego, co naprawdę dzieje się wszystko
tym razem pod kaptur z komputera.
>> Na przykład, jeśli masz w środku waszego laptop lub komputer stacjonarny
dysk twardy, to albo mechaniczne Urządzenie, które w rzeczywistości kręci -
jest okrągłe rzeczy zwane talerze , które wyglądają zupełnie jak co
właśnie miałem na ekranie tutaj, choć to jest coraz bardziej stara szkoła.
To jest trzy i pół cala dysk twardy.
I trzy i pół cala nawiązuje z się z rzeczy, gdy go zainstalować
w komputerze.
>> Wielu z Was w swoich laptopach teraz mają dyski półprzewodnikowe lub SSD,
które nie mają ruchomych części.
Są bardziej jak pamięci RAM i mniej jak Te urządzenia mechaniczne.
Ale idee są wciąż takie same, z pewnością odnoszą się one
do problemu ustawić pięć.
>> A jeśli myślisz o teraz dysk twardy reprezentuje jako koło, które
Będę rysować jak to tutaj.
Podczas tworzenia pliku na komputerze, czy to SSD, lub w
W tym przypadku starszy szkoła dysk twardy, że plik zawiera wiele bitów.
Powiedzmy, że jest to 0 i 1, cała masa 0s i 1s.
Więc to jest mój cały dysk twardy.
To jest podobno dość duży plik.
I korzysta się 0s i 1s na które część fizycznej płyty.
>> Cóż, to, co jest, że fizyczna część?
Cóż, okazuje się, że na dysku twardym, przynajmniej tego typu, jest
te maleńkie cząstki magnetyczne.
I oni mają zasadniczo na północ i południe, słupy do nich tak, że jeśli
skręcić w jedną z tych cząstek magnetycznych w ten sposób, można powiedzieć, że jest to
stanowi 1.
A jeśli to jest do góry nogami, na południe do na północ, można powiedzieć, że jest to
co stanowi 0.
>> Tak więc w rzeczywistym świecie fizycznym, to jak można przedstawiać coś w
Stan binarny z 0 i 1.
Więc to wszystko pliku.
Jest cała masa magnetyczna cząstki, które są w ten sposób lub ich
W ten sposób stanie tworzenia od 0s i 1s.
>> Ale okazuje się, po zapisaniu pliku, niektóre informacje są zapisywane osobno.
Więc to jest mały stolik, katalog, że tak powiem.
A ja nazwać nazwę kolumny, a Zadzwonię do tej lokalizacji kolumny.
>> A ja powiem, przypuszczam to jest mój życiorys.
Mój resume.doc jest przechowywany w lokalizacja, powiedzmy 123.
I zawsze iść do tej liczby.
Ale wystarczy powiedzieć, że tak jak w pamięci RAM, można wziąć dysk twardy
to gigabyte lub 200 GB lub terabajt, i można
liczba wszystkich bajtów.
Można policzyć wszystkie kawałki 8 bitów.
>> Będziemy więc powiedzieć, że ten jest 123 miejsce.
Więc to wewnątrz katalogu mojej pracy System pamięta, że ​​my
CV jest na miejscu 123.
Ale robi się ciekawie, gdy można usunąć plik.
>> Tak na przykład -
i na szczęście, większość świata ma złapany na to - to, co się dzieje, gdy
przeciągnij plik do Kosza systemu Mac OS czy Twój system Windows Kosz?
Co jest celem robi?
To oczywiście pozbyć się pliku, ale co to akt przeciąganie i
spada do kosza lub twój Recycle Bin zrobić na komputerze?
>> Absolutnie nic, naprawdę.
To tak, jak w folderze.
Jest specjalnym folderze, aby się upewnić.
Ale czy to faktycznie usunąć plik?
>> No, no, bo niektórzy z was zapewne były podobne, oh cholera, ty nie
tego zrobić.
Więc kliknij dwukrotnie Trash lub Kosz.
Masz grzebali i masz odzyskane plik po prostu przeciągając je
stamtąd.
Tak wyraźnie, że to nie koniecznie usunięcie go.
>> OK, jesteś mądrzejsza.
Wiesz, że po prostu przeciągając go do Recycle Bin Trash lub nie oznacza
jesteś opróżniania kosza.
Więc idź do menu, a ty mówisz, Empty Trash lub Opróżnij Kosz.
Więc co się dzieje?
>> Tak, tak, to jest usuwany bardziej.
Ale wszystko, co się dzieje, jest to.
Komputer zapomina, gdzie resume.doc było.
>> Ale to, co pozornie nie zmieniło na zdjęciu?
Bity, 0s i 1s, że zastrzeżenia są na miejscu jakiegoś fizycznego aspektu
hardware.
Są tam jeszcze.
To jest po prostu komputer ma zapomniał, czym one są.
>> Więc to w zasadzie zwolniona file-tych bitów tak, że mogą być ponownie wykorzystane.
Ale nie aż do tworzenia nowych plików, i więcej plików, a pliki będą
probabilistycznie, te 0s i 1s, te cząstki magnetyczne, ponownie wykorzystane,
upside lub prawej strony w górę, na innych plików, 0s i 1s.
>> Więc trzeba to okno czasu.
I to nie z przewidywalnym Długość, naprawdę.
To zależy od wielkości dysku twardego, jazdy i ile masz i plików
jak szybko zrobić nowe.
Ale jest to okno, w czasie którym plik jest nadal doskonale
zwrotowi.
>> Więc jeśli kiedykolwiek korzystać z programów takich jak McAfee lub Norton, aby spróbować odzyskać
dane, wszystko robią próbuje odzyskać to tzw katalog na
dowiedzieć się, gdzie plik był.
A czasami Norton i powie, plik jest 93% do odzysku.
No, co to oznacza?
To po prostu oznacza, że ​​jakiś inny plik przypadkowo skończyło się, powiedzmy,
te kawałki ze swojego oryginalnego pliku.
>> Więc co jest faktycznie zaangażowany odzyskiwanie danych?
Cóż, jeśli nie ma czegoś takiego Norton wstępnie zainstalowany na komputerze,
Najlepsze co możesz zrobić, to patrzeć czasem na cały dysk twardy szukać
wzory bitów.
I jeden z tematów zestaw problemów pięć jest to, że można sprawdzić
odpowiednik dysku twardego, forensic Obraz Compact Flash Card od
aparat cyfrowy, szukając 0s i 1s, że zazwyczaj, z wysokiej
Prawdopodobieństwo, reprezentują początek obraz JPEG.
>> A wy może odzyskać te obrazy, zakładając, gdy widzę ten wzór
bitów na obraz, z sądowej wysokie prawdopodobieństwo, że znaki
początek JPEG.
A jeśli widzę ten sam wzór ponownie, że prawdopodobnie oznacza początek
kolejny JPEG, a drugi JPEG, a inny JPEG.
I to jest, jak zwykle odzyskiwanie danych będzie działać.
Co jest ładne o JPEG jest nawet Format pliku sam w sobie jest nieco
złożone, początek każdy taki plik jest rzeczywiście dość rozpoznawalne
i proste, jak widać, jeśli nie już.
>> Warto więc przyjrzeć się bliżej pod spodem kaptur, aby dokładnie to, co było
dzieje i co to 0s i 1s to, aby dać trochę więcej
kontekst dla tego konkretnego zadania.
>> [PLAYBACK VIDEO]
>> -Jeżeli komputer przechowuje najbardziej swoich stałych danych.
Aby to zrobić, dane podróżuje z RAM wraz z sygnałami oprogramowania, które mówią
dysk twardy, jak przechowywać te dane.
Układy napędowe twarde tłumaczyć te sygnały do ​​napięcia
wahania.
To, z kolei, sterowanie dysku twardego ruchomych części, niektóre z niewielu
ruchomych części pozostawione w nowoczesny komputer.
>> Niektóre z tych sygnałów steruje silnikiem który obraca talerze pokryte metalem.
Twoje dane są właściwie przechowywane na tych talerzach.
Inne sygnały przejść do odczytu / zapisu głowice do odczytu lub
zapisu danych na talerzach.
To maszyny tak precyzyjne, że człowiek włosy nie może nawet przejść między
głowice i talerze wirujące.
A jednak, to wszystko działa na wspaniałe prędkościach.
>> [END PLAYBACK VIDEO]
>> DAVID MALAN: Zoom in little głębiej teraz na to, co
faktycznie na tych talerzach.
>> [PLAYBACK VIDEO]
>> -Spójrzmy na to, co tylko widział w zwolnionym tempie.
Po krótki impuls elektryczny jest wysyłane do głowicy odczytu / zapisu, gdy odwraca
na małej elektromagnetycznych dla ułamek sekundy.
Magnes wytwarza pole, które zmiany polaryzacji z tiny, tiny
Część cząstek metalu, które płaszcz każdej powierzchni talerza.
>> Wzór seria z nich małe, opłata-up obszary na dysku
oznacza jeden bit Dane na liczbę binarną
System używany przez komputery.
Teraz, gdy prąd jest przesyłany w jedną stronę przez głowicę odczytu / zapisu, obszar
jest spolaryzowane w jednym kierunku.
Jeśli prąd jest przesyłany w przeciwnym kierunku,
polaryzacja jest odwrotna.
>> Jak uzyskać dane z dysku twardego?
Wystarczy odwrócić proces.
Więc to cząstki na dysku że dostać prąd
głowicy odczytu / zapisu ruchu.
Ułożyła miliony nich Segmenty i namagnesowane
masz plik.
>> Teraz kawałki jednego pliku może być rozrzucone po całym dysku-tych
talerze, trochę jak bałagan z papierami na biurku.
Więc specjalny dodatkowy plik śledzi , gdzie wszystko jest.
Czy nie chciałbyś mieć coś takiego?
>> [END PLAYBACK VIDEO]
>> DAVID MALAN: OK, chyba nie.
Tak jak wielu z was Wychowałem się z nich?
OK, więc to jest coraz mniej ręce każdego roku.
Ale cieszę się, że jesteś co najmniej zaznajomiony z nimi, bo to i nasza
demo książki, niestety, umierają bardzo powolną śmierć tu znajomości.
>> Ale to jest to, co ja, co najmniej, z powrotem w liceum, używane wykorzystanie do tworzenia kopii zapasowych.
I to było niesamowite, bo może przechowywać 1,4 megabajtów na
ten konkretny dysk.
A było to wersja wysoka gęstość, jak pokazano na HD, który ma
czyli przed dzisiejszych filmów HD.
>> Średnia gęstość 800 kilobajtów.
A wcześniej, nie było 400 kilobajtów dyski.
A wcześniej, było 5 i 1/4 calowe dyski, które były naprawdę floppy,
i nieco szerszy i wyższy niż tych rzeczy tutaj.
Ale rzeczywiście można zobaczyć tzw floppy aspektem tych dyskach.
>> I funkcjonalnie, są rzeczywiście bardzo podobne do dysków twardych o co
najmniej tego typu.
Ponownie, dyski SSD w nowszych komputerach działa trochę inaczej.
Jeśli jednak przenieść ten mały metalowy zaczep, rzeczywiście można zobaczyć trochę cookie,
lub tacy.
>> To nie jest metalem jak ten.
Ten jest rzeczywiście trochę tańsze tworzywo sztuczne.
I można trochę poruszać nim.
A ty trully tylko zetrzeć niektóre Ilość bitów lub cząstek magnetycznych
z tego dysku.
>> Więc na szczęście, nie ma nic na jej temat.
Jeśli to, co znajduje się na drodze - a pokrycie oczy i te z sąsiadem -
można po prostu rodzaj ciągnąć tego Cały off osłona tak.
Ale jest trochę wiosny, więc być świadomi, że na własne oczy.
Więc teraz trzeba rzetelnie dyskietkę.
>> I co o tym niezwykłym jest to, że w tak samo, jak to jest
małą skalę reprezentacja większe dysk twardy, te rzeczy są super,
super proste.
Jeśli szczypta dno to, że teraz że rzeczą metalu jest off, i skórki
je otwarte, wszystko jest to dwa kawałki filcu i tzw Dyskietka
z kawałkiem metalu w środku.
>> I tam jest połowa Treść mojego dysku.
Tam idzie kolejny połowa z nich.
Ale to wszystko, co było w środku przędzenia komputera w przeszłości.
>> I znowu, aby umieścić to w perspektywie, jak duży jest większość swojego
Dyski twarde w tych dniach?
500 GB, terabajt, może w Komputer stacjonarny, 2 TB, 3
TB, 4 terabajty, prawda?
Jest to jeden megabajt, lub dać, których nie można nawet zmieścić typowy MP3
anymore te dni, lub kilka Podobny plik muzyczny.
>> Więc trochę pamiątka dla Ciebie dzisiaj i także pomóc contextualize co
będziemy brać za pewnik teraz problemu ustawić pięć.
To są twoje utrzymanie.
Więc pozwól mi przejście do miejsca, gdzie będzie wydając kolejną PSET również.
Więc my teraz ustawić aktualizacja - oh, Kilka ogłoszeń szybko.
>> W ten piątek, jeśli chciałbyś dołączyć CS50 na obiad, pójść do zwykłego miejsca,
cs50.net/rsvp.
I ostateczny projekt -
tak na programie nauczania, jakie zamieścił ostateczna specyfikacja projektu już.
Sobie sprawę, że to nie oznacza, to z powodu szczególnie szybko.
To pisał, naprawdę, tak aby uzyskać wy o tym myśleć.
I rzeczywiście, bardzo istotne procent z was będą walki
Ostateczne projekty dotyczące materiału, który możemy nawet nie dostał się w klasie,
ale będzie już w przyszłym tygodniu.
>> Zauważmy jednak, że specyfikacja wymaga kilka różnych składników
projekt końcowy.
Najpierw, w ciągu kilku tygodni, jest pre-propozycja, dość przypadkowy adres:
Twój TF mu powiedzieć lub co masz myśląc o dla twojego projektu, z
bez zobowiązań.
Wniosek będzie Twój szczególności zaangażowanie, mówiąc o, to co
Chciałbym zrobić dla mojego projektu.
Co o tym sądzisz?
Zbyt duże?
Zbyt małe?
Czy to jest do opanowania?
I widzisz spec więcej szczegółów.
>> Kilka tygodni po tym, że jest stan Raport, który jest podobnie
dorywczo email do TF powiedzieć, jak daleko w tyle jesteś w final
Realizacja projektu, a następnie CS50 hackathon do którego każdy
jest zaproszenie, które będzie wydarzeniem z 20:00 na jeden wieczór aż do 07:00
Rano następnego dnia rano.
Pizza, a może już wspomniałem w tygodniu zero, wil być serwowane w 21:00,
Chińskie jedzenie na 01:00.
A jeśli nadal nie śpisz na 05:00, weźmiemy cię do IHOP na śniadanie.
>> Tak hackathon jest jednym z bardziej pamiętnych doświadczeń w klasie.
Wtedy realizacja wynika, i następnie szczytowy CS50 Fair.
Więcej szczegółów na temat wszystkich tych w najbliższych tygodniach.
>> Ale wróćmy do czegoś old school -
ponownie, array.
Więc tablica była miła, bo to rozwiązuje problemy jak widzieliśmy tylko
chwilą ze struktur studenckich się nieco spod kontroli, jeśli
chcą mieć jeden, student studentowi dwa, Student trzy, student dot dot dot,
niektóre arbitralne liczba studentów.
>> Więc tablic, kilka tygodni temu, spadały w i rozwiązać wszystkie nasze problemy z nie
wiedząc z góry, jak wiele rzeczy jakiegoś rodzaju może chcemy.
I widzieliśmy, że elemencie może nam pomóc ponadto zorganizować naszego kodu i zachować
koncepcyjnie podobnych zmiennych, takich jak imię i dom, razem, tak że
Można traktować je jako jedną całość, wewnątrz których istnieje mniejsze kawałki.
>> Ale tablice mają pewne wady.
Jakie są wady ale wystąpił
z tablicami do tej pory?
Co to jest?
Stały rozmiar - tak, nawet jeśli może być w stanie przydzielić pamięci dla
array, gdy wiesz, ilu uczniów masz, ile znaków trzeba
od użytkownika, kiedy już przyznane array, ty niby malowane
się w rogu.
>> Ponieważ nie można wstawić nowe elementy w środku tablicy.
Nie można wstawić więcej elementów na koniec tablicy.
Naprawdę, trzeba uciekać się do stworzenia Cała nowa tablica, jak już wspomniano,
kopiowanie starych do nowych.
I znowu, że jest ból głowy GetString oferty ze dla Ciebie.
>> Ale znowu, nie można nawet włożyć coś w środku tablicy
jeśli stawka nie jest całkowicie wypełniona.
Na przykład, jeśli ta tablica o wielkości sześć ma tylko pięć rzeczy w nim,
Cóż, może po prostu tack coś na koniec.
Ale co jeśli chcesz wstawić coś w środku
array, chociaż może to mieć pięć z sześciu rzeczy w nim?
>> No i co zrobić, gdy mieliśmy wszystko naszych ochotników na scenie w
tydzień przeszłości?
Jeśli chcemy, aby umieścić tu kogoś, albo ci ludzie, jak przenieść ten
sposób, lub te osoby, jak przenieść ten sposób, i które się kosztowne.
Przemieszczanie się ludzi wewnątrz array skończył sumowaniu i kosztów
nam czas, a więc dużo nasz n do kwadratu czasy działania jak sortowanie wstawiania do
Przykładowo, w najgorszym przypadku.
Więc tablice są świetne, ale trzeba z góry wiedzieć, jak duży chcesz.
>> Więc OK, tu jest rozwiązanie.
Jeśli nie wiesz z góry, ile studentów może mam i wiem, że raz
I zdecydować, choć utknąłem z tym wielu studentów, dlaczego nie mogę po prostu zawsze
przeznaczyć dwa razy więcej przestrzeni jak można myślę, że potrzebuję?
Czy nie jest to rozsądne rozwiązanie?
>> Realistycznie, nie sądzę, że jesteśmy będzie potrzebował więcej niż 50 gniazd
w tablicy dla średniej wielkości klas, więc po prostu zaokrąglić w górę.
Zrobię 100 gniazd w mojej tablicy, po prostu tak, że możemy na pewno się
Liczba studentów I spodziewać się być w jakimś średniej wielkości klasy.
Więc dlaczego nie po prostu zaokrąglić w górę i przeznaczyć więcej pamięci, zazwyczaj, na tablicy
niż myślisz, może nawet trzeba?
Co to jest proste pushback do tego pomysłu?
>> Jesteś po prostu tracić pamięć.
Dosłownie każdy program można napisać, a następnie jest być może za pomocą dwa razy więcej pamięci jako
rzeczywiście trzeba.
A to po prostu nie ma ochoty szczególnie eleganckie rozwiązanie.
Co więcej, tylko zmniejsza Prawdopodobieństwo wystąpienia problemu.
Jeśli zdarzy się, że popularny kurs jeden semestr i masz 101
studentów, program jest nadal zasadniczo stoi ten sam problem.
>> Więc na szczęście, jest rozwiązaniem Ogłoszenie wszystkie nasze problemy w postaci
struktury danych, które są bardziej skomplikowane niż te, które
jakie widziałem do tej pory.
To, jak twierdzą, jest linked list.
To jest lista numerów -
9, 17, 22, 26, i 34 -
, które zostały połączone ze sobą w drodze z tego, co już rysowane jako strzałki.
>> Innymi słowy, jeśli chcę do reprezentowania array, co mogłem zrobić
coś takiego.
I włożę to na napowietrznych za chwilę.
Mogłem zrobić -
witam, wszystko w porządku.
Stand by.
Nowy komputer tutaj jasne -
Dobrze.
>> Więc jeśli mam te liczby w tablicy -
9, 17, 22, 26, 24 -
niekoniecznie w skali.
W porządku, więc tutaj jest mój array -
oh my god.
W porządku, więc tutaj jest mój tablicy.
O mój Boże.
>> [Śmiech]
>> DAVID MALAN: Pretend.
To zbyt wiele wysiłku, aby wrócić i naprawić, więc nie -
26.
Mamy więc tę tablicę 9, 17, 22, 26 i 34.
Dla tych z Was może zobaczyć żenujący błąd Zrobiłem,
tam jest.
>> So I twierdzą, że jest to bardzo wydajne rozwiązanie.
Mam przydzielone tyle liczb całkowitych jak Muszę - Raz, dwa, trzy,
cztery, pięć lub sześć -
a ja następnie przechowywane numery wewnątrz tej tablicy.
Ale załóżmy, to chcę, aby wstawić wartość jak numer 8?
No, gdzie się udać?
Załóżmy, że chcę, aby wstawić liczba jak 20.
No, gdzie się udać?
Gdzieś tam w środku, lub numer 35 musi iść
gdzieś na końcu.
Ale ja jestem z kosmosu.
>> I tak to jest fundamentalnym wyzwaniem tablic, które nie są rozwiązaniem.
I twierdził chwilą GetString rozwiązuje ten problem.
Jeśli chcesz wstawić numer szósty do tego układu, co jest co najmniej jeden
Rozwiązanie można polegać na na pewno, tak jak my z GetString?
Co to jest?
>> Cóż, sprawiają, że większe jest łatwiej powiedzieć niż zrobić.
Nie możemy zawsze zrobić tablicę większe, ale co możemy zrobić?
Sprawdź nową tablicę, która jest większa, wielkości 6, a może rozmiar 10, jeśli chcemy
się wyprzedzić rzeczy, a następnie skopiować stara tablica na nowy, a następnie
uwolnić starą tablicę.
>> Ale co to jest czas pracy teraz z tego procesu?
Jest duży O n, ponieważ kopiowanie będzie kosztować kilka jednostek
czas, więc nie jest tak idealne, jeśli mamy do przydzielić nową tablicę, która ma zamiar
spożywać dwa razy tyle pamięci tymczasowo.
Skopiuj stary na nowe -
Mam na myśli, że to tylko ból głowy, który jest, ponownie, dlaczego napisał
GetString dla Ciebie.
>> Więc co możemy zrobić w zamian?
A co, jeśli nasza struktura danych rzeczywiście ma w nim luki?
Załóżmy, że mam odpocząć mój cel posiadania sąsiadujące fragmenty pamięci, gdzie 9
jest tuż obok 17, która jest obok 22, i tak dalej.
>> I przypuszczam, że 9 może być tutaj w RAM i 17 może być tutaj w pamięci RAM,
i 22 może być tutaj w pamięci RAM.
Innymi słowy, nie trzeba ich nawet z powrotem do tyłu już.
Muszę jakoś nawlec igłę przez każdy z tych numerów, lub każde
tych węzłów, jak będziemy nazywać prostokąty, jak ja ich, ciągnione
pamiętam, jak dostać się do ostatniego taki węzeł od początku.
>> Więc co jest konstrukcja programistyczna widzieliśmy całkiem niedawno, z którymi się
może realizować ten wątek, lub Sporządzono tutaj, z którym mogę
wprowadzić te strzałki?
Tak więc wskaźniki, prawda?
Gdybym nie przeznaczyć tylko Int., ale węzeł - i
węzeł, po prostu oznacza pojemnik.
I wizualnie, to znaczy prostokąt.
Więc najwyraźniej potrzebuje węzła zawiera dwie wartości -
Int. się, a następnie, jak sugeruje Dolna połowa prostokąta
wystarczająco dużo miejsca na int.
>> Tak właśnie myśli przed tutaj, jak duży jest ten węzeł, to
Pojemnik na pytanie?
Ile bajtów na int?
Przypuszczalnie 4, jeśli jest to tak samo jak zwykle.
A potem, jak wiele bajtów dla wskaźnika?
4.
Więc ten pojemnik, lub węzeł, jest będzie 8-bajtowy struktura.
Oh, i to szczęśliwy zbieg okoliczności, że właśnie wprowadził to pojęcie
struct lub struktura C.
>> Więc twierdzenie, że chcę zrobić krok wobec tego bardziej wyrafinowane
Wdrożenie listy numerów, o powiązana lista numerów, trzeba zrobić
trochę więcej myślenia i do przodu deklarują nie tylko int, ale struct
że zadzwonię, umownie tutaj, węzeł.
Moglibyśmy nazwać to co chcemy, ale Węzeł będzie w wielu tematycznych
z rzeczy zacząć patrzeć na teraz.
>> Wewnątrz tego węzła jest int n.
A potem ta składnia, trochę dziwne na pierwszy rzut oka -
struct node * next.
Cóż obrazowo, co to jest?
To jest dolna połowa Prostokąt widzieliśmy
przed chwilą.
>> Ale dlaczego ja mówię węzeł struct * a nie tylko węzeł *?
Bo jeśli wskaźnik wskazuje w innym węźle, to tylko
adres węzła.
To jest zgodne z tym, co mamy dyskutowali o wskazówki do tej pory.
Ale dlaczego, jeśli twierdzą, struktura ta jest zwany węzeł, muszę powiedzieć, struct
węzeł w środku tutaj?
>> Dokładnie.
To trochę głupie rzeczywistości C. Typedef, że tak powiem, nie ma
zdarzyło się jeszcze.
C jest super dosłowne.
Czyta górna kod do dołu, od lewej do prawej.
I dopóki nie natrafi na ten średnik Najważniejsze, zgadnij co nie
istnieć jako typ?
Węzeł, cytuję węzeł cytatu.
>> Ale ze względu na więcej komunikatów deklaracja ja na pierwszej linii -
typedef struct node -
dlatego, że był pierwszy, przed nawiasy klamrowe, że jest coś w rodzaju
pre-kształcenie Szczęk, że jesteś wiesz co, daj mi struct
nazywa węzła struct.
Szczerze mówiąc, nie lubię rzeczy, nazywając struct node, struct node wszystko
w całym kodzie.
Ale będę używać go tylko raz, tylko w środku, tak, że mogę skutecznie
stworzyć coś w rodzaju odwołania cyklicznego, nie wskaźnik do siebie per se, ale
wskaźnik do innego identyczny typ.
>> Okazuje się, że w strukturze danych tak, jest kilka
operacje, które mogą być interesujące dla nas.
Możemy być wstawiony w liście, jak ta.
Możemy usunąć z listy, jak ten.
Może Chcemy sprawdzić listę dla wartość, lub bardziej ogólnie, trawers.
I trawers jest tylko fantazyjny sposób mówiąc, początek po lewej i przesunąć wszystkie
sposób prawo.
>> I zauważ, nawet z tym nieco więcej wyrafinowane struktury danych, niech
ja proponuje, że możemy pożyczyć idee ostatnich dwóch tygodni i
realizacji funkcji o nazwie sprawdzić jak ten.
To będzie prawdziwe lub powrót false, wskazując, tak czy
Nie dotyczy to w tym wykazie.
Drugim argumentem jest wskaźnik z listy, w tak
wskaźnik do węzła.
>> Wszystko mam zamiar to zrobić, to zadeklarować zmienna tymczasowa.
Nazwijmy to ptr umownie dla wskaźnika.
I przypisać to równe początek listy.
>> A teraz uwaga pętli while.
Tak długo, jak wskaźnik nie jest równy null, mam zamiar sprawdzić.
Jest strzałka wskaźnik n równa n, która została uchwalona w?
I czekać minut - nowe Kawałek składni.
Co to jest strzałka nagle?
Tak?
>> Dokładnie.
Tak więc, podczas gdy kilka minut temu, używaliśmy notacji dot dostęp do czegoś
wewnątrz tej struktury, jeśli zmienna Nie masz struct jest
sam w sobie, ale wskaźnik do struktury, szczęście, że element składni
wreszcie sens intuicyjny.
Strzałka oznacza śledzenie wskaźnika, jak zwykle na myśli nasze strzały
obrazowo, i przejść na wewnątrz pola danych.
Więc strzałka jest to samo jak kropka, ale go używać, gdy masz wskaźnik.
>> Przypomnę więc tylko wtedy, gdy pole n wewnątrz struktury o nazwie wskaźnik
równa jest równa n, zwraca true.
W przeciwnym razie, ta linia tutaj - wskaźnik wynosi wskaźnik next.
Więc co to robi, zawiadomienia, to jeśli Obecnie wskazuje na struktury
zawierający 9 i 9 nie liczba jest Szuka - przypuszczać, szukam
dla n wynosi 50 -
Mam zamiar zaktualizować tymczasowy wskaźnik aby nie wskazywać na tym węźle
więcej, ale wskaźnik strzałkę obok, który ma zamiar umieścić mnie tutaj.
>> Teraz zdałem sobie sprawę, to trąba powietrzna Wprowadzenie.
W środę, my rzeczywiście to zrobić z niektórych ludzi, a niektóre więcej
Kod w wolniejszym tempie.
Ale sobie sprawę, jesteśmy teraz, aby nasze dane struktury bardziej złożone, tak aby nasi
Algorytmy mogą uzyskać bardziej efektywne, co będzie warunkiem
pset sześć, gdy wczytać się ponownie, tym 150.000 słowa, ale trzeba zrobić
skutecznie, a najlepiej, stworzyć program, który działa na nie nasi użytkownicy
liniowego, nie n kwadratu, ale stały czas, w ideale.
>> Do zobaczenia w środę.
>> Głośnik: Na następnym CS50, David zapomina o jego sprawy podstawowej.
>> DAVID MALAN: I w ten sposób wyślesz wiadomości tekstowych z C. Co -
>> [RÓŻNE wiadomość tekstową ZAWIADOMIENIE SOUNDS]