[Powered by Google Translate] [Opis] [Quiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Harvard University]
>> [To jest CS50.] [CS50.TV]
>> Hej, wszyscy.
Witamy w sesji przeglądu dla Quiz 0, co ma miejsce w środę.
Co będziemy robić dziś w nocy, jestem z 3 innych TFS
i razem będziemy przechodzić przegląd co zrobiliśmy w trakcie tej pory.
To nie będzie 100% niepełna, ale powinno dać lepszy pomysł
z tego, co już masz w dół, a co trzeba jeszcze studia przed środą.
I czuć się swobodnie podnieść rękę z pytaniami, jak będziemy razem,
ale należy pamiętać, że będziemy mieć trochę czasu na koniec
jeśli mamy dotrzeć z kilku minut do zapasowe uwagi na ogólne pytania,
więc miej to na uwadze, i tak mamy zamiar rozpocząć na początku z tygodnia 0.
>> [Quiz 0 recenzję!] [Część 0] [Lexi Ross] Ale zanim to zrobimy Porozmawiajmy o
logistyka w quizie.
>> [Logistics] [Quiz odbędzie się w środę 10/10 w miejsce wykładu]
>> [(Zobacz http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf szczegóły)] Jest to w środę, 10 października.
>> To w środę, a jeśli się do tego adresu URL tutaj
który jest również dostępny z CS50.net-tam jest link do niego-
możesz zobaczyć informacje o tym, gdzie się udać na podstawie
Twoje nazwisko lub powiązanie szkoły, jak również
opowiada o co dokładnie quiz będzie obejmował i rodzaje pytań, które masz zamiar uzyskać.
Pamiętaj, że będziesz mieć możliwość przejrzenia na quizie w przekroju,
więc twoje TF należy przekraczania pewnych problemów praktyki,
i to jest kolejna dobra okazja, aby zobaczyć, gdzie trzeba jeszcze uczyć się na quiz.
Zacznijmy od początku z Bytes 'N' bitów.
Zapamiętaj nieco tylko 0 lub 1,
a bajt to zbiór 8 tych bitów.
Przyjrzyjmy się tej kolekcji bitów tutaj.
Powinniśmy być w stanie dowiedzieć się, ile bitów są.
Gdzie możemy liczyć tam tylko 8 z nich, osiem 0 lub 1 jednostki.
A ponieważ nie ma 8 bitów, to 1 bajt,
i niech ją przekonwertować na system szesnastkowy.
Szesnastkowy jest baza 16, i jest to dość łatwe do konwersji
liczba w systemie binarnym, czyli co to jest do liczby w systemie szesnastkowym.
Wszystko co robimy jest spojrzeć na grupy 4,
i konwertować je do odpowiedniej cyfry szesnastkowe.
Zaczynamy od prawej przeważającej grupy 4, więc 0011.
To będzie jeden 1 i jeden 2, tak, że umożliwia 3 razem.
A potem spójrzmy na drugim bloku 4.
1101. To będzie jeden 1, jeden 4 i jeden 8.
Razem, że to będzie 13, co sprawia, D.
I będziemy pamiętać, że w systemie szesnastkowym nie pójść 0 do 9.
Idziemy 0 do F, więc po 9, 10 odpowiada,
11 do B, i tak dalej, gdzie F jest 15.
O D 13 jest,
tak, aby przekonwertować go na dziesiętne wszystko możemy zrobić, to tak naprawdę
traktować każdą pozycję potęgi 2.
To jedna 1, jedna 2, zero 4s, zero 8s, jeden 16, et cetera,
i jest to trochę trudne do obliczenia w głowie, ale jeśli idziemy do następnego slajdu
możemy zobaczyć odpowiedź.
>> Zasadniczo będziemy naprzeciwko powrotem do lewej,
i jesteśmy pomnożenie każdej cyfry przez odpowiednie potęgi 2.
I pamiętaj, na szesnastkową oznaczymy te numery z 0x na początku
więc nie mylić z liczbą dziesiętną.
Kontynuując, to Tabela ASCII,
i czego używamy ASCII jest mapowanie z znaków do wartości liczbowych.
Zapamiętaj w Pset kryptograficznej podjęliśmy szerokie wykorzystanie tablicy ASCII
Aby korzystać z różnych metod kryptografii
Cezar i szyfr Vigenère przekonwertować różne litery
w ciągu według klucza przez danego użytkownika.
Przyjrzyjmy się trochę ASCII matematyki.
Patrząc na "P" + 1, w postaci znaków, które byłyby Q
i pamiętaj, że '5 '≠ 5.
I jak dokładnie chcemy konwertować pomiędzy tymi 2 formach?
To nie jest naprawdę trudne.
W celu uzyskania 5 odejmiemy '0 '
ponieważ jest 5 miejsc pomiędzy '0 ', a '5.'
Aby przejść na inny sposób po prostu dodać 0,
, więc jest to coś w rodzaju regularnej arytmetyki.
Pamiętaj tylko, że jeśli coś ma cudzysłowy wokół niego to znak
i co odpowiada wartości w tabeli ASCII.
Przeprowadzka do bardziej ogólnych zagadnień informatyki.
Dowiedzieliśmy się, co algorytm jest i jak go używać programowania
do realizacji algorytmów.
Niektóre przykłady algorytmów są czymś naprawdę proste jak
sprawdzenie, czy liczba jest parzysta czy nieparzysta.
Za to pamiętam, że mod liczbę przez 2 i sprawdź, czy wynik jest 0.
Jeśli tak, to nawet. Jeśli nie, to dziwne.
I to jest przykład algorytm naprawdę podstawowe.
>> Trochę bardziej zaangażowany jeden jest binary search,
które będziemy później przejść w sesji przeglądarki.
I programowanie jest termin, którego używamy do wykonywania algorytmu
i konwertowanie jej do kodu, komputer może odczytać.
2 przykłady programowania jest Scratch,
czyli to, co zrobiliśmy w tygodniu 0.
Mimo tego, że w rzeczywistości nie wpisać się kod to sposób realizacji
ten algorytm, który drukuje numery 1-10,
i tu to samo w języku programowania C.
Są to funkcjonalny odpowiednik, tylko napisane w różnych językach lub składni.
Potem dowiedziałem się o wyrażeniach logicznych,
i logiczna jest wartość, która jest albo prawdziwe, albo fałszywe,
i tutaj często wyrażeń logicznych
wejdź na warunkach, więc jeśli (x ≤ 5),
dobrze, już ustawione x = 5, więc, że warunek ten będzie ocenić wartość true.
A jeśli to prawda, co kod jest pod warunkiem
zostanie ocenione przez komputer, tak że łańcuch ma być wydrukowany
do standardowego wyjścia, a warunek określony
odnosi się do tego, co jest wewnątrz nawiasów w if.
Pamiętam wszystkich operatorów.
Pamiętaj, że to && i | |, kiedy staramy się połączyć 2 lub więcej warunków,
== Nie = do sprawdzenia, czy 2 rzeczy są równe.
Pamiętaj, że = jest do przypisania natomiast == jest boolean operator.
≤, ≥, a następnie ostateczna 2 są oczywiste.
Ogólny przegląd boolean logiki tutaj.
I wyrażeń logicznych są również ważne w pętli,
którym pojedziemy już koniec.
Dowiedzieliśmy się o 3 rodzaje pętli dotąd w CS50, for, while i do while.
I ważne jest aby wiedzieć, że, podczas gdy w większości zastosowań
rzeczywiście możemy używać żadnych pętli ogólnie
pewne rodzaje celów lub wspólnych wzorów
w programowaniu, które specyficznie zadzwonić na jeden z tych pętli
które sprawiają, że najbardziej wydajne i eleganckie do kodu to w ten sposób.
Chodźmy czym każdy z tych obwodów bywa najczęściej stosuje.
>> W pętli for na ogół już wiedzą, ile razy chcemy iteracyjne.
To, co wkładamy w stanie.
W, i = 0, i <10, na przykład.
Wiemy już, że chcemy zrobić coś 10 razy.
Teraz, w pętli, na ogół nie koniecznie
wiem, ile razy chcemy pętli uruchomić.
Ale wiemy jakieś warunkiem, że chcemy, aby
zawsze prawdziwe lub zawsze false.
Na przykład, gdy jest ustawiony.
Powiedzmy, że jest logiczna zmienna.
Choć to prawda, że ​​chcemy kod do oceny,
więc trochę bardziej rozszerzalny, nieco bardziej ogólne niż do pętli,
ale każdy dla pętli można także przekształcić do pętli.
Wreszcie, czy pętle while, które mogą wydawać się trudne do zrozumienia od razu,
są często, gdy chcemy oceny kod najpierw
przed pierwszym momencie możemy sprawdzić stan.
Typowym przykładem użycia zrobić, gdy pętla
jest wtedy, gdy chcesz uzyskać dane wprowadzone przez użytkownika, i wiesz, że chcesz zwrócić się do użytkownika
do wprowadzania co najmniej raz, ale jeśli nie daje dobre wejście od zaraz
chcesz zachować prośbą do dają dobre wejście.
To najczęściej używane są podczas pętli,
i spójrzmy na rzeczywistej strukturze tych pętli.
Zazwyczaj zawsze mają tendencję do tych wzorów.
>> W pętli for wewnątrz masz 3 elementy:
inicjalizacji, zazwyczaj coś jak int i = 0 gdzie i jest licznik,
stan, w którym chcemy powiedzieć uruchomić to dla pętli tak długo jak ten warunek nadal posiada,
jak i <10, a następnie w końcu aktualizacji, który jest, jak zwiększamy
Licznik zmiennej w każdym punkcie w pętli.
Wspólna rzecz, aby zobaczyć jest tylko i + +,
co oznacza, że ​​inkrementacja i przez 1 za każdym razem.
Można też zrobić coś tak jak ja + = 2,
co oznacza, dodać 2 do i za każdym razem przejść przez pętlę.
, A następnie do tego tylko odnosi się do kodu, który faktycznie działa jako część pętli.
A dla pętli while, tym razem faktycznie mają inicjalizacji poza pętli
tak na przykład, powiedzmy, że chcemy zrobić ten sam typ pętli jak już opisany.
Chcemy powiedzieć int i = 0 zanim pętla zaczyna.
Wtedy możemy powiedzieć, gdy i <10 to zrobić,
tak samo, jak blok kodu wcześniej
i tym razem część aktualizacja kodu, na przykład, i + +
faktycznie idzie wewnątrz pętli.
I wreszcie, na zrobić, gdy, jest podobna do pętli while,
ale trzeba pamiętać, że kod będzie oceniać raz
przed warunek jest sprawdzany, więc jest o wiele więcej sensu
jeśli spojrzeć na to w porządku góry do dołu.
W pętli while zrobić kod ocenia zanim jeszcze spojrzeć na stanie, gdy,
natomiast pętli while, sprawdza najpierw.
Oświadczenia i zmiennych.
Gdy chcemy utworzyć nową zmienną najpierw chcą go zainicjować.
>> Na przykład, int bar inicjalizuje zmienną bar,
ale to nie daje mu wartość, więc co to jest wartość baru teraz?
Nie wiemy.
To może być jakaś wartość śmieci, które zostało wcześniej zapisane w pamięci tam,
a my nie chcemy używać tej zmiennej
aż rzeczywiście dać mu wartość,
więc uznać je tutaj.
Następnie zainicjować za 42 poniżej.
Teraz, oczywiście, wiemy, można to zrobić w jednej linii, int = 42 bar.
Ale tak się wyczyścić wielu kroków, które są dzieje,
deklaracja i inicjalizacja dzieje się tutaj oddzielnie.
To dzieje się na jednym etapie, a kolejny, int baz = bar + 1,
Stwierdzenie to poniżej, baz przyrosty, więc na końcu tego bloku kodu
gdybyśmy wydrukować wartość baz byłoby 44
bo zadeklarować i zainicjować go za 1> bar,
a potem zwiększamy ją jeszcze raz z + +.
Udaliśmy się nad tym dość krótko, ale dobrze jest mieć ogólne
zrozumienie co wątki i zdarzenia.
Zajmujemy się głównie to zrobił w Scratch,
więc można myśleć gwintów wielu sekwencji kodu
działa się w tym samym czasie.
W rzeczywistości, to prawdopodobnie nie działa w tym samym czasie,
ale rodzaju abstrakcyjnie możemy myśleć o tym w ten sposób.
>> W Scratch, na przykład, mieliśmy kilka ikonek.
Może być inny kod wykonujący się w tym samym czasie.
Można chodzić, a drugi mówi coś
w innej części ekranu.
Wydarzenia są kolejnym sposobem na oddzielenie logiki
poszczególnych elementów kodu,
i Scratch byliśmy w stanie symulować zdarzenia używając audycji,
i to faktycznie po otrzymaniu, nie, gdy słyszę,
ale zasadniczo jest to sposób przekazywania informacji
z jednego do drugiego ikonki.
Na przykład, może chcesz przekazać Game Over
i kiedy otrzyma kolejny sprite gra skończy,
reaguje w pewien sposób.
Jest to ważne do zrozumienia modelem dla programowania.
Wystarczy przejść przez podstawowego tygodniu 0, co udało nam się do tej pory już ponad,
Przyjrzyjmy się tym prostym programie C.
Tekst może być trochę mały stąd, ale pójdę nad nim naprawdę szybko.
Jesteśmy w tym 2 nagłówków plików na górze, cs50.h i stdio.h.
Mamy następnie zdefiniowania stałej o nazwie limit wynosi 100.
Mamy następnie realizując naszą główną funkcję.
Ponieważ nie używamy argumentów wiersza poleceń tutaj musimy położyć pustkę
jako argumenty dla main.
Widzimy powyżej int main. To typ zwracany, 0 w tym samym powrócić do dołu.
I używamy CS50 biblioteki funkcji dostać int
poprosić użytkownika o wprowadzenie, i zapisać go w tej zmiennej x,
więc oświadczam x powyżej, a my go zainicjować z x = getInt.
>> Następnie należy sprawdzić, czy użytkownik dał nam dobre wejście.
Jeśli jest to LIMIT ≥ chcemy zwrócić kod błędu 1 i wydrukować komunikat o błędzie.
I wreszcie, jeśli użytkownik dał nam dobre wejście
idziemy do kwadratu liczby i wydrukować tego rezultatu.
Wystarczy upewnić się, że te wszystkie hit home
widać etykiety różnych części kodu tutaj.
Wspomniałem stałe, nagłówków plików.
Oh, int x. Należy zapamiętać, że to zmienna lokalna.
To kontrastuje go od zmiennej globalnej, które będziemy rozmawiać o
Nieco później w sesji przeglądarki,
i mamy wywołanie funkcji biblioteki printf,
więc jeśli nie są wliczone w pliku nagłówkowego stdio.h
nie bylibyśmy w stanie wywołać printf.
I wierzę, że strzałka dostałem uciąć tu wskazując na% d,
która jest łańcuchem formatowanie printf.
Mówi wydrukować tej zmiennej jako liczby,% d.
I że jest to dla Tygodnia 0.
Teraz Lucas będzie nadal.
Hej, chłopaki. Nazywam się Lucas.
Jestem studentem drugiego roku w najlepszym domu na terenie kampusu, Mather,
i mam zamiar porozmawiać trochę o tydzień 1 i 2,1.
[Tydzień 1 i 2,1!] [Lucas Freitas]
Jako Lexi mówił, kiedy zaczęliśmy tłumaczyć kodu od podstaw w C
jedną z rzeczy, które zauważyłem jest to, że można nie tylko
napisać kod i uruchomić go za pomocą zieloną flagę już.
Faktycznie, trzeba użyć pewnych kroków, aby dokonać program C
się plik wykonywalny.
Zasadniczo to, co robisz, gdy jesteś pisania programu jest to, że
można przetłumaczyć swój pomysł na język kompilator może zrozumieć,
więc kiedy piszesz program w C
co robisz jest rzeczywiście coś pisze, że kompilator będzie zrozumieć,
a następnie kompilator będzie tłumaczyć, że kod
w coś, że komputer będzie zrozumieć.
>> I rzeczą jest, komputer jest rzeczywiście bardzo głupie.
Twój komputer może zrozumieć tylko 0s i 1s,
tak naprawdę w pierwszych komputerach ludzie zazwyczaj zaprogramowane
używając 0s i 1s, ale już nie, dzięki Bogu.
Nie mamy zapamiętać sekwencje 0s i 1s
w pętli do lub na pętli, i tak dalej.
Dlatego mamy kompilator.
Co kompilator robi to w zasadzie tłumaczy kod C,
w naszym przypadku, do języka, że ​​komputer będzie zrozumieć,
który jest przedmiotem kod i kompilator, że używamy
nazywa dzyń, więc jest to rzeczywiście symbol brzękiem.
Jeśli masz program, musisz zrobić 2 rzeczy.
Po pierwsze, musisz skompilować program, a następnie masz zamiar uruchomić program.
Aby skompilować program masz wiele możliwości, aby to zrobić.
Pierwszy z nich to zrobić program.c dzyń
, w którym program jest nazwa programu.
W tym przypadku widać, są one po prostu mówiąc "Hej, skompilować mój program."
Nie mówimy: "Chcę tę nazwę dla mojego programu" lub cokolwiek.
>> Druga opcja daje nazwę programu.
Można powiedzieć, dzyń-o, a następnie imię, które chcesz
Plik wykonywalny być nazwany i program.c.
I można to zrobić również zrobić program i zobaczyć, jak w ciągu pierwszych 2 przypadkach
Włożyłem. C, oraz w trzeciej mam tylko programy?
Tak, rzeczywiście nie należy umieszczać. C podczas korzystania zrobić.
W przeciwnym wypadku kompilator faktycznie się krzyczeć na Ciebie.
A także, że nie wiem, czy wy pamiętajcie,
ale wiele razy korzystaliśmy również-lcs50 lub-lm.
To się nazywa łączenie.
To po prostu mówi kompilatorowi, że będzie korzystać z tych bibliotek tam,
więc jeśli chcesz używać cs50.h rzeczywiście trzeba wpisać
dzyń program.c-lcs50.
Jeśli tego nie robią, to kompilator nie będzie wiedział
że używasz tych funkcji w cs50.h.
A kiedy chcesz uruchomić program masz 2 opcje.
Jeśli tak program.c Clang nie daliście nazwę programu.
Musisz uruchomić go za pomocą. / A.out.
A.out jest standardowy nazwa dzyń daje program, jeśli nie dajesz mu nazwę.
W przeciwnym razie będziemy robić. / Program, jeśli dał nazwę programu,
a także, jeśli nam się zaprogramować nazwę, że program dostanie
już będzie zaprogramować taką samą nazwę jak plik C.
Potem rozmawialiśmy o typach danych i danych.
>> Zasadniczo typy danych to samo jak małe pudełka, które wykorzystują
do przechowywania wartości, więc typy danych są rzeczywiście jak stworki.
Pochodzą one we wszystkich rozmiarach i rodzajach.
Nie wiem, czy to analogia sens.
Rozmiar dane rzeczywiście zależy od architektury maszyny.
Wszystkie dane rozmiary, że zamierzam tu pokazać
w rzeczywistości dla 32-bitowego, który jest w przypadku urządzenia, w naszym
ale jeśli faktycznie kodowanie komputera Mac lub w Windows również
Prawdopodobnie będziesz mieć 64-bitową maszynę,
więc pamiętać, że rozmiary danych, które mam zamiar tu pokazać
są na maszynie 32-bitowej.
Pierwszy, który widzieliśmy, był int,
co jest dość proste.
Użyć int przechowywać liczbę całkowitą.
Widzieliśmy również znak, char.
Jeśli chcesz korzystać z list lub trochę symbol jesteś prawdopodobnie będzie używać char.
Char ma 1 bajt, co oznacza 8 bitów, jak Lexi powiedział.
Zasadniczo mamy ASCII tabeli, która ma 256
możliwe kombinacje 0s i 1s,
a następnie po wpisaniu char to będzie tłumaczyć
znak, że wejścia wy numer, który masz w tabeli ASCII, jak Lexi powiedział.
Mamy też pływak, którego używamy do przechowywania liczb dziesiętnych.
Jeśli chcesz wybrać 3,14, na przykład, masz zamiar używać pacy
lub podwójny, który ma więcej precyzji.
Pływak ma 4 bajty.
Double ma 8 bajtów, więc jedyną różnicą jest precyzja.
Mamy również długi, że jest używany do liczb całkowitych,
i można zobaczyć na komputerze 32-bitowym int i długo mieć ten sam rozmiar,
tak naprawdę nie ma sensu używać długo w komputerze 32-bitowym.
>> Ale jeśli używasz komputera Mac i 64-bit, faktycznie długo ma rozmiar 8,
więc to naprawdę zależy od architektury.
Dla maszyny 32-bitowej nie ma sensu używać długo naprawdę.
A następnie długo długo, z drugiej strony, jest 8 bajtów,
tak to jest bardzo dobry, jeśli chcesz mieć dłuższą całkowitą.
I wreszcie, mamy ciąg, który jest faktycznie char *,
który jest wskaźnikiem do char.
To bardzo proste, aby myśleć, że wielkość znaków ma być jak
liczba znaków, które tam masz,
ale faktycznie sam char *
ma wielkość wskaźnika do char, które jest 4 bajty.
Rozmiar char * jest 4 bajty.
To nie ma znaczenia, jeśli masz małe słowo lub list czy coś.
To będzie 4 bajty.
Dowiedzieliśmy się także trochę o castingu
więc jak widać, jeśli, na przykład, program, który mówi
int x = 3, a następnie printf ("% d", x / 2)
Wiecie co to będzie drukować na ekranie?
>> Ktoś? >> [Uczniowie] 2.
1. >> 1, yeah.
Kiedy robisz 3/2 to dostanie 1,5,
ale skoro używamy integer to będzie ignorować dziesiętną część,
i będziesz mieć 1.
Jeśli nie chcesz, aby tak się stało, co można zrobić, na przykład,
jest stwierdzenie, float y = x.
Wtedy x, które dawniej były 3 teraz będzie 3,000 w y.
A następnie można wydrukować r / 2.
Właściwie powinienem mieć 2. tam.
To zrobi 3.00/2.00,
i masz zamiar się 1,5.
I mamy to 0,2 f prostu poprosić o 2 jednostkach dziesiętnych w części dziesiętnej.
Jeśli masz .3 f to się rzeczywiście 1,500.
Jeśli to 2 to będzie 1,50.
Mamy też w tej sprawie tutaj.
Jeśli nie pływaka x = 3,14 i wtedy printf x
masz zamiar dostać 3,14.
I jeśli x = int x,
co oznacza, że ​​traktuje x jako int i wypisać x teraz
będziesz mieć 3,00.
Czy to ma sens?
Bo jesteś najpierw działając x jako liczba całkowita, a więc jesteś ignorując dziesiętną część,
a następnie drukuje się x.
I wreszcie, można to zrobić,
int x = 65, a następnie zadeklarować char c = x,
, a następnie, jeśli wydrukować c. jesteś rzeczywiście dostanie
, Więc w zasadzie co tu robisz
przekłada liczbę całkowitą do charakteru,
jak ASCII Tabela robi.
Rozmawialiśmy także o operatorów matematycznych.
Większość z nich są bardzo proste, więc +, -, *, /,
a także rozmawialiśmy o modzie, która pozostała do podziału 2 liczb.
Jeśli masz 10% 3, na przykład,
to znaczy podzielić 10 przez 3, a co reszta?
To będzie 1, więc jest to naprawdę bardzo przydatne dla wielu programów.
Dla Vigenère i Cezara Jestem pewien, że wszyscy z was stosować mod.
O operatorów matematycznych, być bardzo ostrożnym podczas łączenia * i /.
>> Na przykład, jeśli nie (3/2) * 2, co masz zamiar dostać?
[Studenci] 2.
Tak, 2, ponieważ 3/2 będzie 1.5
ale skoro robisz operacji pomiędzy 2 liczb
jesteś rzeczywiście tak będzie badać, 1,
a następnie 1 * 2 będzie 2, więc być bardzo ostrożny
przy wykonywaniu arytmetyki liczb całkowitych, ponieważ z
można dostać, że 2 = 3, w tym przypadku.
A także być bardzo ostrożnym pierwszeństwa.
Należy zazwyczaj użyć nawiasów, aby upewnić się, że wiesz co robisz.
Niektóre użyteczne skróty, Oczywiście, jest i + + + i i = 1
lub przy użyciu + =.
To jest to samo, co robi i = i + 1.
Można również zrobić i - lub i - = 1,
co jest to samo, co i = i -1,
coś, czego faceci używają dużo w pętli, co najmniej.
Ponadto, dla *, jeśli używasz * = a jeśli nie, na przykład,
i * = 2 jest to samo, co mówią i = i * 2,
i to samo do podziału.
Jeśli nie i / = 2 to jest to samo co i = i / 2.
>> Teraz o funkcji.
Dowiedzieliśmy się, że chłopaki są funkcje bardzo dobra strategia, aby zapisać kod
gdy jesteś programowania, więc jeśli chcesz, aby wykonać to samo zadanie
w kodzie, po raz kolejny, prawdopodobnie chcesz użyć funkcji
tak więc nie musisz skopiować i wkleić kod w kółko.
Faktycznie, głównym jest funkcją, a kiedy pokazać format funkcji
masz zamiar zobaczyć, że to jest dość oczywiste.
Mamy również korzystać z funkcji z niektórych bibliotek,
na przykład, printf, Getin, który jest z biblioteki, CS50,
oraz inne funkcje, takie jak toupper.
Wszystkie te funkcje są w rzeczywistości realizowane w innych bibliotek,
i kiedy można umieścić te pliki Tether na początku programu
mówisz, czy możesz dać mi kod dla tych funkcji
więc nie mam do ich wdrożenia przez siebie?
Można także pisać własne funkcje, więc kiedy rozpocząć programowanie
zdajesz sobie sprawę, że biblioteki nie mają wszystkie funkcje, które potrzebujesz.
Dla ostatniego PSET, np. pisaliśmy rysować, Scramble, i wyszukiwania,
i to jest bardzo, bardzo ważne, aby móc napisać funkcje
dlatego, że są przydatne, a używamy ich cały czas w programowaniu,
i oszczędza dużo kodu.
Format funkcji jest ta.
Mamy zwracany typ na początku. Co to jest typ zwracany?
To jest tylko wtedy, gdy funkcja ma zamiar wrócić.
Jeśli masz funkcję, na przykład, silni,
, który ma obliczyć silnię liczby całkowitej,
Prawdopodobnie to będzie zwracać liczbę całkowitą również.
Następnie zwracany typ będzie int.
Printf faktycznie ma pustkę Zwraca typ
ponieważ nie jesteś powrocie nic.
Jesteś po prostu drukowanie rzeczy na ekranie
i wyjście z funkcji później.
Potem masz nazwę funkcji, które można wybrać.
Trzeba mieć trochę rozsądne, jak nie wybrać nazwę jak xyz
lub jak x2F.
Spróbuj uzupełnić nazwę, która ma sens.
>> Na przykład, jeśli jest to silni, powiedzmy silnię.
Jeśli jest to funkcja, która będzie narysować coś, nazwij go narysować.
A potem mają parametry, które są również nazywane argumenty,
które są jak zasobów, że funkcja musi
z kodu do wykonywania jego zadania.
Jeśli chcesz obliczyć silni liczby
prawdopodobnie trzeba mieć numer do obliczenia silni.
Jednym z argumentów, że będziemy mieć to numer sam.
I wtedy to będzie coś zrobić i zwraca wartość na koniec
chyba, że ​​jest to funkcja nieważne.
Zobaczmy przykład.
Jeśli chcę napisać funkcję, która sumuje wszystkie liczby w tablicy liczb całkowitych,
Po pierwsze, jest typu powrotu będzie int
ponieważ mam tablicę liczb całkowitych.
I wtedy będę miała nazwę funkcji jak sumArray,
a następnie zajmie się tablica, int nums,
a następnie długość tablicy, więc wiem, ile liczb mam do podsumowania.
Następnie trzeba zainicjować zmienną sumę, na przykład, do 0,
i za każdym razem widzę elementu w tablicy należy dodać go do sumy, więc zrobiłem dla pętli.
Podobnie jak Lexi mówi, robisz int i = 0, i długość <i i + +.
I dla każdego elementu w tablicy zrobiłem suma + = nums [i],
a następnie wróciłem sumę, więc jest to bardzo proste, a to oszczędza dużo kodu
jeśli korzystasz z tej funkcji, wiele razy.
Potem przyjrzał się warunków.
Mamy if, else i else if.
Zobaczmy, jaka jest różnica między tymi.
Spójrz na tych 2 kodów. Jaka jest różnica między nimi?
Pierwszy ma-w zasadzie kody żebyś powiedział
Jeśli liczba jest +, -, lub 0.
Pierwsza mówi, że jeśli to jest> 0 to jest to pozytywne.
Jeśli to = 0, a następnie to 0, a jeśli jest to <0 to jest to negatywne.
>> , A drugi robi if, else if, else.
Różnica między nimi jest, że ta faktycznie się
sprawdzić, czy> 0, <0 lub = 0 trzy razy,
więc jeśli masz numer 2, na przykład, że będzie tu przyjść i powiedzieć:
if (x> 0), a to się, że tak, więc wydrukować pozytywne.
Ale chociaż wiem, że to jest> 0 i nie będzie 0 lub <0
Wciąż będziemy robić to jest 0, to jest <0,
więc jestem naprawdę dzieje się wewnątrz ifs, że nie muszą
bo już wiem, że to nie będzie spełniać żadnego z tych warunków.
Można używać, jeśli else if, else.
To w zasadzie mówi, że jeśli x = 0 wydrukować pozytywne.
Jeśli tak nie jest, mam zamiar również przetestować.
Jeśli to 2 nie będę tego robić.
Zasadniczo jeśli miałem x = 2 powiedziałbyś
if (x> 0), tak, więc drukuj.
Teraz wiem, że to jest> 0 i że spełnione najpierw, jeśli
Nie jestem nawet zamiar uruchomić ten kod.
Kod działa szybciej, faktycznie, 3 razy szybciej, jeśli używasz tego.
Dowiedzieliśmy się także o AND i OR.
Nie zamierzam przejść przez to, ponieważ Lexi już mówił o nich.
To tylko && i | operator |.
>> Jedyne co powiem, to należy uważać, gdy masz 3 warunki.
Użyć nawiasów, bo to bardzo mylące, gdy występuje stan
i jeszcze jeden lub drugi.
Użyj nawiasów tylko mieć pewność, że twoje warunki sensu
, ponieważ w tym przypadku, na przykład, można sobie wyobrazić, że
może to być stan pierwszy i jeden lub inne
lub 2 połączone w warunkach i
lub trzeci, więc po prostu uważać.
I wreszcie, rozmawialiśmy o przełącznikach.
Przełącznik jest bardzo przydatna, gdy masz zmienną.
Powiedzmy, że masz zmienną jak n
, że mogą się 0, 1, lub 2, a w każdym z tych przypadków,
masz zamiar wykonać zadanie.
Można powiedzieć, włączyć zmienną, a oznacza to, że
napięcie wtedy jest jak value1 zamierzam to zrobić,
a potem przerwa, co oznacza, że ​​nie będę patrzeć na którykolwiek z pozostałych przypadkach
bo już przekonany, że przypadek
a następnie wartość2 i tak dalej, i ja również może mieć przełącznik domyślnego.
Oznacza to, że jeśli nie spełnia żadnego z przypadków, które miałem
że będę robić coś innego, ale to jest opcjonalne.
To wszystko dla mnie. Teraz mają Tommy.
W porządku, to będzie tydzień 3-owski.
Są to niektóre z tematów, będziemy zalewami crypto, zakresu tablic, et cetera.
Wystarczy szybkie słowo na kryptografii. Nie będziemy wbijać ten dom.
>> Zrobiliśmy to w Pset 2, ale w quizie należy znać różnicę
między szyfru Cezara i szyfrem Vigenère
jak zarówno tych, którzy pracy szyfrów i jak to jest do szyfrowania
i tekst odszyfrować użyciu tych 2 szyfry.
Pamiętaj, szyfr Cezara po prostu obraca każdy znak w tej samej wysokości,
upewniając się, że mod przez liczbę liter w alfabecie.
I szyfr Vigenère drugiej strony, każdy znak obraca
o innej wysokości, więc zamiast mówić
co obracać znaku przez 3 Vigenère obraca każdy znak
o różny w zależności od niektórych kluczowych
gdzie każda litera w kluczowych reprezentuje trochę inną kwotę
obrócić wyraźny tekst.
Niech najpierw rozmawiają o zasięg zmiennych.
Są 2 różne rodzaje zmiennych.
Mamy zmienne lokalne, a te zostaną określone
poza głównym lub poza dowolnej funkcji lub bloku,
i będą one dostępne w dowolnym miejscu w programie.
Jeśli masz funkcję i w tej funkcji jest pętla
duża zmienna globalna jest dostępna wszędzie.
Lokalne zmienne, z drugiej strony, jest ograniczony do miejsca, w którym jest to określone.
>> Jeśli masz funkcję o, na przykład, mamy tę funkcję g,
G i wewnątrz jest zmienną o nazwie Y
co oznacza, że ​​jest to zmienna lokalna.
Nawet jeśli ta zmienna nazywa y
i ta zmienna nazywa y te 2 funkcje
nie mam pojęcia co dla siebie lokalne zmienne.
Z drugiej strony, tu powiedzieć int x = 5,
i jest poza zakresem żadnej funkcji.
To jest poza zakresem główną, więc jest to zmienna globalna.
To oznacza, że ​​w środku tych 2 funkcji, gdy mówię, x - czy x + +
Mam dostęp do tego samego x przy czym ta y i to Y są różne zmienne.
To jest różnica między zmienną globalną i zmiennej lokalnej.
O ile chodzi o design, czasami to chyba lepszy pomysł
zachować zmienne lokalne, gdy to tylko możliwe
ponieważ mając kilka zmiennych globalnych można uzyskać naprawdę kłopotliwe.
Jeśli masz kilka funkcji wszystkie zmiany to samo
można zapomnieć, co jeśli ta funkcja przypadkowo modyfikuje ten globalny,
a to inna funkcja nie wie o tym,
i robi się dość skomplikowane, jak dostać więcej kodu.
Utrzymywanie zmienne lokalne, gdy to tylko możliwe
jest po prostu dobry design.
Macierze, Pamiętaj, są po prostu wykaz elementów tego samego typu.
Wewnątrz CI nie może mieć listę takich jak 1, 2,0, hello.
Po prostu nie mogę tego zrobić.
>> Kiedy stwierdzenie tablicy w C wszystkie elementy muszą być tego samego typu.
Tutaj mam tablicę 3 liczb całkowitych.
Tutaj mam długość tablicy, ale jeśli ja tylko deklarując go w tej składni
gdzie mogę określić wszystkie elementy nie są technicznie potrzebujemy 3.
Kompilator jest na tyle sprytny, aby dowiedzieć się, jak duża tablica powinna być.
Teraz, gdy chcę uzyskać lub ustawić wartość tablicy
to jest składnia to zrobić.
To będzie faktycznie zmienić drugi element tablicy, bo pamiętam,
Numeracja zaczyna się od 0, a nie na 1.
Jeśli chcę przeczytać tę wartość można powiedzieć coś takiego int x = array [1].
Albo, jeżeli chcesz ustawić tę wartość, tak jak ja tutaj robię,
Mogę powiedzieć, tablica [1] = 4.
Że czas dostępu do elementów poprzez ich indeks
lub ich pozycji lub gdy są w tablicy,
i że wpis zaczyna się 0.
Możemy również tablice tablic,
i to się nazywa wielowymiarową tablicę.
Kiedy mamy tablicę wielowymiarową
co oznacza, że ​​możemy mieć coś jak wierszy i kolumn,
i jest to tylko jeden ze sposobów wizualizacji to czy o tym myśleć.
Kiedy mam tablicę wielowymiarową, która oznacza, że ​​zamierzam rozpocząć konieczności
więcej niż 1 index bo jeśli mam siatkę
tylko, że to, co jesteś w wiersz nie daje nam liczbę.
To się naprawdę da nam listę numerów.
Powiedzmy, że mam tę tablicę tutaj.
Mam tablicę o nazwie sieci, a ja mówię, że to 2 wiersze i 3 kolumny,
i więc jest to sposób wizualizacji.
Kiedy mówię, że chcę, aby uzyskać element w [1] [2]
to znaczy, że ponieważ są rzędy kolumny, a potem
Mam zamiar przejść do wiersza 1 od powiedziałem 1.
>> Potem mam zamiar przyjść tutaj do kolumny 2, a ja zamierzam uzyskać wartość 6.
Ma sens?
Tablice wielowymiarowe, pamiętaj, są technicznie tylko tablica tablic.
Możemy mieć tablice tablice tablic.
Możemy iść dalej, ale naprawdę jeden sposób myślenia o
jak to jest określone i co się dzieje to jest wizualizacja
w siatce jak ta.
Kiedy mijamy tablicę do funkcji, że będziemy zachowywać się
trochę inaczej niż wtedy, gdy mijamy regularne zmienne do funkcji
jak przekazywanie int lub float.
Gdy przechodzimy w rodzaju int lub char lub dowolnym z tych danych
właśnie przyjrzał jeśli funkcja modyfikuje
wartość tej zmiennej, że zmiana nie będzie rozprzestrzeniać się
do wywoływania funkcji.
W tablicy, z drugiej strony, że tak się stanie.
Jeśli przechodzą w tablicy do niektórych funkcji, a funkcja zmienia niektóre z elementów,
kiedy wrócę do funkcji, która wywołała go
moja tablica jest teraz będzie inaczej, i za to słownictwo
jest tablice są przekazywane przez referencję, jak zobaczymy później.
Związane jest to w jaki sposób działają wskaźniki, gdzie te podstawowe typy danych,
z drugiej strony, są przekazywane przez wartość.
>> Możemy myśleć, że wykonanie kopii jakiejś zmiennej, a następnie przechodzi w kopii.
To nie ma znaczenia, co robimy z tej zmiennej.
Funkcji wywołującej nie będzie wiedział, że zmieniono.
Tablice są tylko trochę różni się w tym względzie.
Na przykład, tak, jak zamierzaliśmy, głównym jest po prostu funkcja
, które mogą podjąć w 2 argumenty.
Pierwszy argument funkcji głównej jest argc, lub liczbę argumentów
i drugi argument jest nazywany argv,
i to są rzeczywiste wartości tych argumentów.
Powiedzmy, że mam program o nazwie this.c,
i mówię, aby to, i mam zamiar uruchomić to w wierszu poleceń.
Teraz, aby przejść w niektórych argumentów do mojego programu nazwali to,
Mógłbym powiedzieć coś. / To jest cs 50.
To jest to, co możemy sobie wyobrazić David zrobić codziennie w terminalu.
Ale teraz główny wewnątrz funkcja tego programu
ma te wartości, więc argc jest 4.
To może być trochę mylące, bo tak naprawdę jesteśmy tylko przechodząc jest cs 50.
To tylko 3.
Ale pamiętaj, że pierwszy element argv lub pierwszy argument
jest nazwa samej funkcji.
Więc to oznacza, że ​​mamy 4 rzeczy tu,
oraz pierwszy element będzie. / to.
I to będzie reprezentowany jako ciąg.
Wtedy pozostałe elementy, co wpisane w po nazwie programu.
Tak, jak na bok, jak zapewne widzieliśmy w Pset 2,
pamiętać, że ciąg 50 jest ≠ całkowitą 50.
Więc nie możemy powiedzieć coś w stylu: "int x = argv 3".
>> Że po prostu nie będzie sensu, bo to jest ciąg, a to jest liczbą całkowitą.
Tak więc, jeśli chcesz przekonwertować między 2, pamiętaj, będziemy
mają magiczną funkcję o nazwie atoi.
Która pobiera ciąg i zwraca liczbę całkowitą reprezentowany wewnątrz tego łańcucha.
Więc to jest proste, aby błąd w quizie,
myśląc, że to będzie automatycznie odpowiedniego typu.
Ale wiedz, że to zawsze będzie smyczki
nawet, jeśli ciąg zawiera tylko liczbę całkowitą lub znak lub pacą.
Więc teraz porozmawiajmy o czas pracy.
Gdy mamy wszystkie te algorytmy, które te wszystkie szalone rzeczy,
staje się bardzo przydatne, by zadać pytanie: "Jak długo oni brać?"
Oświadczamy, że z czymś zwanym asymptotycznej notacji.
Więc to oznacza, że ​​- no cóż, powiedzmy, że dajemy naszym algorytmu
niektóre naprawdę, naprawdę, naprawdę duże wejście.
Chcemy zadać pytanie: "Jak długo to potrwa?
Ile kroków zajmie nasz algorytm, aby uruchomić
w funkcji wielkości wejściowych? "
Więc pierwszy sposób możemy opisać czas jest prowadzony z dużym O.
A to nasz najgorszy czas praca.
Więc jeśli chcemy sortować tablicę i dajemy nasz algorytm tablicy
że to w porządku malejącym, kiedy powinien być w porządku rosnącym,
że będzie to najgorszy przypadek.
To jest nasza górna granica w maksymalnej długości czasu nasz algorytm weźmie.
Z drugiej strony, ta Ω będzie opisać najlepszym razie czas pracy.
Więc jeśli dajemy już posortowaną tablicę do algorytmu sortowania,
jak długo to zajmie się rozwiązać to?
I to, a następnie, opisuje dolną granicę czasu pracy.
Więc tutaj to tylko niektóre słowa, które opisują pewne wspólne razy z rzędu.
Są to w kolejności rosnącej.
Najszybszy czas pracy mamy nazywa się stała.
>> To oznacza, że ​​bez względu na to jak wiele elementów dajemy algorytm,
nie ważne jak duże nasza tablica jest, jego sortowanie
lub robi cokolwiek robimy do tablicy zawsze będzie taką samą ilość czasu.
Tak więc można, że ​​stanowią tylko z 1, która jest stała.
Przyglądaliśmy się także logarytmicznym czasie wykonywania.
Więc coś jak wyszukiwanie binarne jest logarytmiczna,
gdzie tniemy problem w pół przy każdym
i rzeczy po prostu wyższy od tego.
A jeśli kiedykolwiek pisania O każdej czynnikowego algorytmu,
prawdopodobnie nie powinien uznać to za dzień pracy.
Kiedy porównać czas ważne jest, aby pamiętać o tych rzeczach.
Więc jeśli mam algorytm, który jest O (n), a ktoś inny
jest algorytm O (2n) są to właściwie asymptotycznie równoważne.
Jeśli więc wyobrazić n być duża liczba jak eleventy mld:
więc kiedy mamy porównanie eleventy mld do czegoś eleventy mld + 3,
nagle, że +3 naprawdę nie robi dużą różnicę już.
Dlatego mamy zamiar rozpocząć rozważa te rzeczy za równoważne.
Więc takie rzeczy jak tych stałych tutaj, jest 2 x ta lub dodając 3,
to tylko stałe, a te będą spadać w górę.
To dlatego wszystkie 3 z tych czasów przebiegu są takie same jak mówią oni O (n).
Podobnie, jeśli mamy 2 inne czas pracy, powiedzmy, O (n ³ + 2n ²), możemy dodać
+ N + 7, a następnie mamy kolejny czas pracy, który jest po prostu O (³ n).
ponownie, to samo, ponieważ są - nie są takie same.
Są to te same rzeczy, przepraszam. Więc to są takie same, ponieważ
ta ³ n ma zamiar zdominować ten 2n ².
>> Co to jest nie to samo jest, jeśli mamy uruchomić razy jak O (³ n) i O (n ²)
bo ³ n jest znacznie większy niż ten ² n.
Więc jeśli mamy wykładniki, nagle zaczyna to znaczenia,
ale gdy mamy po prostu do czynienia z czynnikami, jak jesteśmy tu,
wtedy to nie będzie się liczyć, ponieważ są one po prostu się wypaść.
Rzućmy okiem na niektóre z algorytmów widzieliśmy do tej pory
i porozmawiać o ich czasie pracy.
Pierwsze spojrzenie na liczby w liście, że widzieliśmy, był liniowy wyszukiwania.
I realizacja liniowej wyszukiwania jest bardzo prosta.
Musimy tylko listę, i będziemy patrzeć na każdego elementu na liście
dopóki nie znajdziemy liczby szukamy.
To oznacza, że ​​w najgorszym przypadku, to O (n).
A w najgorszym przypadku może tu być, jeśli element jest
Ostatnim elementem, a następnie za pomocą wyszukiwania liniowego musimy patrzeć na każdego elementu
aż dojdziemy do ostatniej, aby wiedzieć, że to rzeczywiście się na liście.
Nie możemy po prostu zrezygnować w połowie drogi i powiedzieć: "To chyba nie tam."
Z liniowym poszukiwaniu musimy spojrzeć na całą sprawę.
Najlepiej przypadku czasu pracy, z drugiej strony, jest stała
bo w najlepszym przypadku element szukamy jest tylko pierwszy z listy.
Więc to zajmie nam dokładnie 1 krok, nie ważne jak duża lista jest
jeśli patrzymy na każdym pierwszym elementem.
>> Więc kiedy szukać, pamiętaj, że nie oznacza to, że nasza lista jest sortowana.
Bo my po prostu będziemy patrzeć na każdego elementu, a to naprawdę nie ma znaczenia
jakiej kolejności te elementy są w.
Bardziej inteligentny algorytm wyszukiwania jest coś takiego jak wyszukiwanie binarne.
Pamiętaj, że realizacja wyszukiwania binarnego jest kiedy masz zamiar
Patrz na środku listy.
A ponieważ szukamy w środku, wymagamy, że lista jest sortowana
albo nie wiemy, gdzie jest środek, a my mamy patrzeć na
Cała lista go znaleźć, a następnie w tym punkcie jesteśmy po prostu marnowanie czasu.
Więc jeśli mamy posortowaną listę i znaleźć środek, będziemy porównywać środku
do elementu szukamy.
Jeśli jest zbyt wysoki, to możemy zapomnieć prawą połowę
ponieważ wiemy, że jeśli nasz element jest już zbyt wysoka
i wszystko, co na prawo od tego elementu jest jeszcze wyższa,
wtedy nie trzeba szukać już tam.
W przypadku, gdy z drugiej strony, jeżeli nasz elementem jest zbyt niska,
Wiemy wszystko w lewo tego elementu jest zbyt niska,
więc nie ma sensu szukać tam, albo.
W ten sposób, przy każdym kroku i za każdym razem patrzymy na w połowie listy,
będziemy ciąć nasz problem w pół bo nagle wiemy
cała masa liczb, które nie mogą być jeden szukamy.
>> W Pseudokod byłoby to wyglądać tak,
i dlatego mamy cięcia listę w pół przy każdym pojedynczym,
naszych najgorszych skoków czasie wykonywania z liniowej na logarytmiczną.
Więc nagle mamy logowania kroków w celu znalezienia elementu w liście.
Best-case Czas ucieka, choć wciąż jest stała
ponieważ teraz, po prostu powiedzieć, że element szukamy jest
zawsze dokładnie połowy pierwotnej liście.
Więc możemy rozwijać naszą listę tak duża, jak chcemy, ale jeśli element szukamy jest w środku,
potem to tylko zajmie nam 1 krok.
To dlatego, że jesteśmy O (log n) i Ω (1) lub stała.
Miejmy faktycznie uruchomić wyszukiwanie binarne na tej liście.
Więc powiedzmy, że szukamy elementu 164.
Pierwszą rzeczą, jaką chcemy zrobić, to znaleźć punkt środkowy tej listy.
Tak się składa, że ​​punkt środkowy będzie spadać między tymi 2 liczb
więc po prostu arbitralnie powiedzieć, za każdym razem punkt środkowy przypada między 2 liczb
niech po prostu zaokrąglić w górę.
Musimy tylko się upewnić, możemy to zrobić na każdym kroku sposób.
Więc idziemy do zaokrąglenia w górę, a my zamierzamy mówić, że 161 jest w środku naszej liście.
Tak 161 <164, a każdy z elementów 161 lewej
jest <164, więc wiemy, że to nie pomoże nam w ogóle
zacząć szukać tutaj, ponieważ element szukamy, nie może tam być.
Więc co możemy zrobić, to możemy zapomnieć o tym całym pół lewym listy
i teraz pod uwagę tylko z prawej strony 161 wzwyż.
>> Więc jeszcze raz, to jest punkt środkowy, niech po prostu zaokrąglić w górę.
Teraz 175 jest zbyt duża.
Więc wiemy, to nie pomoże nam szukają tutaj lub tutaj,
więc możemy po prostu wyrzucić, że daleko, a ostatecznie będziemy hit 164.
Wszelkie pytania dotyczące binarnego wyszukiwania?
Przejdźmy od poszukiwania przez już posortowanej listy
faktycznie biorąc listę numerów w dowolnej kolejności
i uczynienie tej listy w kolejności rosnącej.
Pierwszy algorytm przyjrzeliśmy nazwano sortowanie bąbelkowe.
I to byłoby prostsze z algorytmów, które widzieliśmy.
Sortowanie bąbelkowe mówi, że kiedy jakieś 2 elementy wewnątrz liście są nie na miejscu,
co oznacza, że ​​jest większa liczba z lewej mniejszej ilości,
Następnie idziemy, aby zamienić je, ponieważ to oznacza, że ​​lista będzie
Bardziej "posortowane", niż to było wcześniej.
A my po prostu będziemy kontynuować ten proces jeszcze raz i jeszcze raz i jeszcze raz
aż w końcu rodzaju elementy z bańki do ich właściwej lokalizacji i mamy posortowaną listę.
>> Czas pracy to będzie O (n ²). Dlaczego?
Ano dlatego, że w najgorszym przypadku, mamy zamiar wziąć każdy element, a
będziemy do końca się porównując ją do każdego innego elementu na liście.
Ale w najlepszym przypadku, mamy już posortowana lista, bańka sort'S
po prostu się przejść raz, mówią: "Nie. Nie robiłem żadnych swapów, więc mam zrobić".
Mamy więc najlepszym razie czas pracy Ω (n).
Uciekajmy sortowania bąbelkowego na liście.
Lub najpierw, po prostu spojrzeć na niektóre Pseudokod naprawdę szybko.
Chcemy powiedzieć, że chcą, aby śledzić, w każdej iteracji pętli,
śledzić czy nie zmienialiśmy żadnych elementów.
Tak więc powodem jest, jedziemy do zatrzymania, gdy nie zamieniły się żadnych elementów.
Tak więc na początku naszej pętli nie zamieniłem nic, więc możemy powiedzieć, że jest fałszywe.
Teraz mamy zamiar przejść przez listę i porównaj element i do elementu i + 1
i, jeśli jest to tak, że nie jest większa liczba z lewej mniejszej ilości,
to mamy po prostu się do zamiany.
>> I wtedy będziemy pamiętać, że zamieniłem element.
To oznacza, że ​​musimy przejść przez listę co najmniej 1 więcej czasu
bo stan, w którym zatrzymaliśmy się, kiedy cała lista jest już posortowane,
co oznacza, że ​​nie dokonano żadnych swapów.
To dlatego nasz stan tu jest "niektóre elementy zostały zamienione.
Więc teraz niech tylko spojrzeć na to uruchomiony na liście.
Mam listę 5,0,1,6,4.
Sortowanie bąbelkowe ruszy całą drogę w lewo, a to będzie porównać
elementy I, tak, i od 0 do 1 +, który jest elementem 1.
To się znaczy, oraz 5> 0, ale teraz 5 jest po lewej stronie,
więc trzeba zamienić 5 i 0.
Kiedy zamienić je, nagle pojawia się ten inną listę.
Teraz 5> 1, więc mamy zamiar zamienić je.
5 nie jest> 6, więc nie musimy nic robić tutaj.
Ale 6> 4, więc musimy zamienić.
Znowu trzeba uruchomić całą listę, aby w końcu odkryć,
że są one w porządku, my je zamieniać,
iw tym momencie musimy uruchomić listę 1 więcej czasu
się upewnić, że wszystko jest w porządku, i na tym etapie sortowania bąbelkowego zakończeniu.
Inny algorytm do podjęcia pewnych elementów i sortowanie ich jest swego wyboru.
Ideą rodzaju selekcji jest, że będziemy budować posortowaną część listy
1 element w tym samym czasie.
>> A sposób, w jaki zamierzamy zrobić to poprzez budowanie lewy segment listy.
I w zasadzie każdy - na każdym kroku, będziemy mieć najmniejszy element zostawiliśmy
, które nie zostały posortowane jeszcze, i mamy zamiar przenieść go do tego sortowanie segmencie.
To oznacza, że ​​musimy stale znaleźć minimalną niesortowanych elementu
a następnie podjąć ten najmniejszy element i zamienić go z tym, co
lewej najbardziej elementem, który nie jest posortowana.
Czas pracy to będzie O (n ²), ponieważ w najgorszym przypadku
musimy porównać każdy element do każdego innego elementu.
Bo mówisz, że jeśli zaczniemy w lewej części listy, musimy
przejść przez cały segment słusznie najmniejszy element.
A potem jeszcze raz, musimy przejść przez całą prawą segment i
wracamy się, że w kółko i od nowa.
To będzie ² n. Będziemy potrzebować do wewnątrz pętli innego dla pętli
co sugeruje ² n.
W najlepszym przypadku, myśli, powiedzmy, że daje mu już posortowaną listę;
tak naprawdę nie robi nic lepszego niż ² n.
Ponieważ rodzaj wyboru nie ma możliwości, wiedząc, że
Minimalny element jest tylko jeden I zdarzyć się patrzy.
Nadal musi się upewnić, że to rzeczywiście minimum.
>> I jedynym sposobem, aby upewnić się, że jest to minimum, za pomocą tego algorytmu,
jest spojrzenie na każdego elementu ponownie.
Tak naprawdę, jeśli dać to - jeśli dać selekcji Sortuj tak już posortowanej listy,
nie zrobi lepiej niż dając mu listę, która nie jest jeszcze posortowana.
Przy okazji, jeśli zdarza się tak, że coś jest O (coś)
i omega czegoś, możemy tylko powiedzieć, bardziej zwięźle, że to θ czegoś.
Więc jeśli widzisz, że pojawią się wszędzie, że to, co po prostu oznacza, że.
>> Jeśli coś jest theta n ², jest to zarówno duże O (n ²) i Ω (n ²).
Więc najlepszym przypadku i najgorszym wypadku, to nie ma znaczenia,
Algorytm ma zamiar zrobić to samo za każdym razem.
Więc to jest to, co do rodzaju karnetu Pseudokod mogłoby wyglądać.
Jesteśmy w zasadzie powiedzieć, że chcę iteracyjne nad listy
od lewej do prawej strony, a na każdej iteracji pętli, mam zamiar przenieść
Minimalny element w tym sortowanie części listy.
I raz przenieść coś tam, nigdy nie trzeba spojrzeć na ten element ponownie.
Ponieważ, jak tylko element wymiany w segmencie do lewej na liście, to posortowane
dlatego robimy wszystko co w kolejności rosnącej przy użyciu minimum.
Więc powiedział, dobrze, jesteśmy na pozycji I i musimy patrzeć na wszystkie elementy
z prawej I w celu znalezienia minimum.
To znaczy, że chcemy wygląda z i + 1 do końca listy.
A teraz, jeśli element, który mamy obecnie, patrząc na mniej niż nasze minimum tak daleko,
które, pamiętaj, zaczynamy off minimalną po prostu być
cokolwiek elementem jesteśmy obecnie na, będę zakładać, że to minimum.
Jeśli znaleźć element, który jest mniejszy niż, to ja powiem, dobrze,
dobrze, znalazłem nowe minimum.
Będę pamiętam gdzie, że minimum było.
>> Więc teraz, kiedy już przeszła przez to prawo segmencie niesegregowanych,
Mogę powiedzieć, że zamierzam zamienić najmniejszy element z elementem, który jest w pozycji I.
To zbuduje mój list, moja posortowane część listy od lewej do prawej,
i nie zawsze trzeba spojrzeć na element kolejny raz, że to w tej części.
Kiedy już zamieniłem go.
Więc uruchom rodzaju selekcja na tej liście.
Niebieski elementem tu będzie i, a czerwony element będzie minimalny element.
Więc rozpoczyna się aż na lewej liście, więc w 5.
Teraz musimy znaleźć minimalną niesortowanych element.
Tak więc możemy powiedzieć, 0 <5, więc 0 jest moim nowym minimum.
>> Ale nie mogę się tam zatrzymać, bo choć możemy uznać, że 0 jest najmniejszy,
musimy przechodzić przez każdego innego elementu na liście, aby się upewnić.
Tak więc 1 jest większa, 6 jest większy, 4 jest większy.
To oznacza, że ​​po obejrzeniu tych wszystkich elementów, jakie określono 0 jest najmniejszy.
Więc mam zamiar zamienić 5 i 0.
Kiedyś zamienić, że mam zamiar dostać nową listę, i wiem, że nigdy nie trzeba szukać w tym 0 raz
bo raz ja zamieniłem go, mam go i posortowane skończymy.
Teraz to po prostu tak się dzieje, że niebieski element jest ponownie 5,
i musimy spojrzeć na 1, 6 i 4 w celu określenia, że ​​1
jest najmniejszy element minimalny, więc będziemy zamieniać 1 i 5.
Ponownie, musimy patrzeć - porównanie 5 do 6 i 4,
i jedziemy do wymiany 4 i 5, a na końcu, porównaj
te 2 numery i zamienić je aż dostajemy naszą posortowaną listę.
Wszelkie pytania dotyczące rodzaju selekcji?
Okay. Przejdźmy do ostatniego tematu tutaj, i to jest rekurencja.
>> Rekurencja, pamiętaj, jest to naprawdę rzecz meta gdzie funkcja
wielokrotnie nazywa siebie.
W pewnym momencie, podczas gdy nasz fuction jest wielokrotnie nazywając siebie,
tam musi być jakiś punkt, w którym nie nazywać siebie.
Bo jeśli tego nie robią, to jesteśmy po prostu będzie nadal robić to zawsze,
a nasz program nie jest po prostu się kończy.
Nazywamy ten stan bazowym.
I bazowym mówi, niż wywołanie funkcji ponownie,
Mam zamiar wrócić jakąś wartość.
Więc raz wróciliśmy wartość, wstrzymaliśmy nazywając siebie,
i reszta połączeń zrobiliśmy do tej pory może powrócić.
Przeciwieństwem do przypadku bazowego jest recursive przypadek.
I to jest, gdy chcemy dokonać innego wywołanie funkcji, że jesteśmy obecnie w.
I prawdopodobnie, choć nie zawsze, chcesz używać różnych argumentów.
>> Więc jeśli mamy funkcję o nazwie f, f nazywany po prostu wziąć 1 argument,
i po prostu zachować wywołanie f (1), f (1), f (1), a tak się składa, że
Argument 1 wpada rekurencyjnego przypadku mamy jeszcze nigdy nie powstrzyma.
Nawet jeśli mamy przypadek bazowy, musimy upewnić się, że w końcu będziemy hit tej sprawy podstawowej.
My nie tylko zachować pobyt w tej cyklicznej przypadku.
Generalnie, gdy nazywamy samych siebie, prawdopodobnie będziesz mieć inny argumentem za każdym razem.
Tutaj jest naprawdę prosta funkcja rekurencyjna.
Więc to będzie obliczyć silnię liczby.
Do góry tutaj mamy przypadek bazowy.
W przypadku, gdy n ≤ 1, to nie zamierzasz zadzwonić silnia ponownie.
Mamy zamiar się zatrzymać, jesteśmy po prostu powróci jakąś wartość.
Jeśli nie jest to prawdą, to mamy zamiar uderzyć naszą rekurencyjną sprawę.
Zauważcie, że nie jesteśmy po prostu wywołanie silnia (n), ponieważ nie byłoby to bardzo pomocne.
Będziemy dzwonić silni coś innego.
>> A więc widać, w końcu jeśli mijamy czynnikowego (5) lub coś,
mamy zamiar zadzwonić silnia (4) i tak dalej, aż w końcu będziemy uderzać ten przypadek bazowy.
Tak to wygląda. Zobaczmy, co się dzieje, gdy faktycznie uruchomić to.
To jest komin, a powiedzmy, że główny będzie wywołać tę funkcję z argumentem (4).
Więc raz silni widzi i = 4, silni wywoła się.
Teraz, nagle, mamy silnia (3).
Więc te funkcje będą stale rosnąć, aż w końcu trafiliśmy naszą sprawę bazowej.
W tym momencie, wartość zwracana jest to zwrot (nx Wartość zwracana to),
Wartość zwracana jest nx Wartość zwracana to.
W końcu muszą trafić jakąś liczbę.
Na górze tutaj mówimy, powrót 1.
To oznacza, że ​​kiedy powróci ten numer, możemy wyskoczyć to ze stosu.
Więc to silnia (1) jest wykonywana.
Kiedy 1 wraca, to silni (1) zwroty, to powrót do 1.
Wartość zwracana to, pamiętaj, to nx Wartość zwracana to.
Tak nagle, ten facet wie, że chcę wrócić 2.
>> Więc pamiętaj, powrót wartość to tylko nx Wartość zwracana tutaj.
Więc teraz możemy powiedzieć, 3 x 2, a na końcu, tutaj możemy powiedzieć
jest to po prostu będzie to 4 x 3 x 2.
A kiedy to zwraca, ale dostać się do jednego środka całkowitą od main.
Wszelkie pytania dotyczące rekursji?
Dobrze. Więc jest więcej czasu na pytania na końcu,
ale teraz Joseph obejmie pozostałe tematy.
>> [Józef Ong] Dobrze. Więc teraz, że rozmawialiśmy o rekursji,
Porozmawiajmy trochę o tym, co scalania sortowania jest.
Merge sort jest zasadniczo inny sposób sortowania listy numerów.
I jak działa to z rodzaju łączenia masz listę i co możemy zrobić, to
możemy powiedzieć, niech podzielić to na 2 połówki.
Będziemy pierwszym uruchomieniu seryjnej sortowanie znowu na lewej połowie
wtedy możemy uruchomić seryjnej sortowanie na prawej połowie,
i to daje nam teraz 2 połówki, które są sortowane, a teraz mamy zamiar połączyć te połówki.
Jest to trochę trudne do zobaczenia, bez przykładu, więc pojedziemy przez ruchy i zobaczyć, co się dzieje.
Więc gdy z tej listy, możemy podzielić go na 2 części.
Prowadzimy seryjnej sortowania na lewej połowie pierwszego.
Więc to jest lewa połowa, a teraz je uruchomić po tej liście ponownie
, które zostanie przekazane do sortowania korespondencji seryjnej, a następnie szukać ponownie,
po lewej stronie tej listy i prowadzimy seryjnej sortowanie na nim.
Teraz możemy zabrać się do listy 2 liczb
i obecnie jest tylko lewa część 1 elementu, i nie może być
podzielić listę, która znajduje się tylko 1 element na pół, więc po prostu powiedzieć, kiedy będziemy mieli 50,
która jest tylko 1 element, to już załatwione.
>> Gdy skończymy z tym, widzimy, że możemy
przenieść się do prawej części tej listy,
i 3 jest również posortowane i tak się, że obie połówki są posortowane liście
możemy połączyć te numery z powrotem.
Tak to wygląda w 50 i 3, 3 jest mniejsza niż 50, to jest w tak, a potem 50 wkracza
Teraz to się robi, wracamy do tej listy i sortowania jest zaraz pół.
42 jest jego własny numer, więc to już posortowane.
Tak teraz porównanie tych 2 i 3 jest mniejsza niż 42, tak, że zostaje wprowadzone w pierwsze
teraz 42 zostanie wprowadzone, a 50 dostaje wtrącił
Teraz, to jest posortowana, jedziemy z powrotem do góry, 1337 i 15.
Cóż, teraz spójrz na lewej połowie tej listy; 1337 jest sama więc jest sortowane i samo z 15.
Więc teraz połączyć te 2 numery do sortowania, który oryginalną listę, 15 <1337,
tak to jest w pierwszym, a następnie 1337 idzie w.
A teraz mamy posortowane obie połówki oryginalnej listy na górze.
A wszystko, co musimy zrobić, to połączyć te.
Patrzymy na pierwsze 2 numery na liście, 3 <15, więc idzie do tablicy sortowania pierwszy.
15 <42 tak dalej w. Teraz, 42 <1337, które przechodzi w.
50 <1337, więc to idzie w. I zauważyć, że po prostu wziął 2 numerów off z tej listy.
Więc nie tylko przemian między 2 list.
Po prostu patrząc na początku, i bierzemy element
który jest mniejszy, a następnie wprowadzenie go do naszej tablicy.
Teraz mamy połączone wszystkie połówki i skończymy.
>> Wszelkie pytania dotyczące scalania sortowania? Tak?
[Student] Jeśli jest podział na różne grupy, dlaczego nie po prostu podzielić go raz
i masz 3 i 2 w grupie? [Reszta niezrozumiały Pytanie]
Powód - więc pytanie, dlaczego po prostu nie możemy połączyć je w tym pierwszym etapie, po je mamy?
Powodem możemy to zrobić, należy uruchomić w lewym większości elementów po obu stronach,
a następnie podjąć mniejszy i umieścić go w to, że wiemy, że te
Poszczególne listy są posortowane zamówień.
Więc jeśli ja patrząc na lewo większości elementów obu połówek,
Wiem, że masz zamiar być najmniejsze elementy tych list.
Więc mogę umieścić je w najmniejszych plam elementem tej dużej listy.
Z drugiej strony, jeżeli patrzeć na tych 2 wymienia się na drugim poziomie Tam
50, 3, 42, 1337 i 15, te, które nie są posortowane.
Więc jeśli spojrzeć na 50 i 1337, mam zamiar postawić 50 na mojej liście w pierwszej kolejności.
Ale to naprawdę nie ma sensu, bo 3 jest najmniejszy element z wszystkich tych.
Więc tylko dlatego możemy zrobić ten krok, łącząc to dlatego, że nasze listy są już posortowane.
Dlatego musimy schodzić aż do dna
bo gdy mamy tylko jeden numer, wiesz, że jeden numer
samo w sobie jest już posortowana lista.
>> Masz pytanie? No?
Złożoność? Cóż, widać, że na każdym kroku tam numery końcowe,
i możemy podzielić listę w dzienniku pół n razy,
czyli tam, gdzie mamy ten n log x n złożoność.
I zobaczysz najlepsze etui do sortowania korespondencji seryjnej jest n log n, i tak się
, że w najgorszym przypadku, lub Ω tam, jest również n log n.
Coś pamiętać.
Idąc dalej, chodźmy na kilka super podstawowego pliku I / O.
Jeżeli spojrzysz na Scramble, zauważysz, że mieliśmy jakieś systemu
gdzie można zapisać do pliku dziennika, jeśli przeczytać kodu.
Zobaczmy, jak można to zrobić.
Cóż, mamy fprintf, co można myśleć, jak tylko printf,
, ale tylko do pliku drukowania, zamiast, a zatem f na początku.
Ten rodzaj kodu w górę, to co robi jest, jak może widzieliście w Scramble,
przechodzi przez swojego 2-wymiarowej tablicy drukowania z kolejny wiersz, jakie numery są.
W tym przypadku, printf wypisuje do terminala lub to, co nazywamy standardowe wyjście sekcji.
>> A teraz, w tym przypadku, wszystko co musisz zrobić, to wymienić printf z fprintf,
powiedzieć to, co plik, który chcesz wydrukować, i w tym przypadku to po prostu wypisuje ją do tego pliku
zamiast wysyłać go do terminalu.
Cóż, to nasuwa się pytanie: Gdzie możemy dostać tego rodzaju pliku, z, prawda?
Mijaliśmy się zalogować do tego fprintf fuction ale nie mieliśmy pojęcia, skąd się wziął.
Cóż, na początku kodu, co mieliśmy było to kawałek kodu tutaj,
które zasadniczo mówi, że otwarty plik nazywa log.txt.
Co robimy po to musimy się upewnić, że plik jest otwarty pomyślnie.
Więc może to nie dla wielu powodów nie masz wystarczająco dużo miejsca na komputerze, na przykład.
Więc to jest zawsze ważne, przed wykonaniem jakichkolwiek operacji z plikiem
że możemy sprawdzić, czy plik został otwarty pomyślnie.
Więc, co to, to jest to argument dla fopen, dobrze, możemy otworzyć plik na wiele sposobów.
Co możemy zrobić, jest, możemy przekazać go w, co oznacza, zastąpić go, jeśli wychodzi już,
Można przekazać A, które dołącza się do końca, zamiast pliku nadrzędnego to,
lub możemy podać r, co oznacza, otwórzmy plik jako tylko do odczytu.
Jeśli więc program próbuje wprowadzić zmiany w pliku,
krzyczeć na nich i nie pozwól im tego zrobić.
Wreszcie, kiedy już skończysz z pliku, done robienia operacji na nim,
Musimy upewnić się, że zamykamy plik.
I tak na koniec programu, masz zamiar przekazać je ponownie
ten plik, który otwiera i po prostu zamknąć.
Więc to jest coś ważnego, że musisz upewnić się, że tak.
Więc pamiętaj możesz otworzyć plik, a następnie można zapisać do pliku,
robić operacji w pliku, ale potem trzeba zamknąć plik na końcu.
>> Wszelkie pytania dotyczące podstawowego pliku I / O? Tak?
[Pytanie Student, niezrozumiały]
Tutaj. Pytanie, skąd to log.txt plik pojawi?
Cóż, jeśli tylko dać Log.txt, tworzy go w tym samym katalogu co plik wykonywalny.
Więc jeśli Jeste - >> [Pytanie Student, niezrozumiały]
Tak. W tym samym folderze, w tym samym katalogu, jak to nazwać.
Teraz pamięć stosu i sterty.
Więc jak to jest określone w pamięci komputera?
Cóż, można sobie wyobrazić jako rodzaj pamięci tego bloku tutaj.
A w pamięci mamy to, co nazywa się sterty utknął tam i stosu, który jest na dole.
I rośnie w dół i kupa stos rośnie w górę.
Więc jak Tommy wspomniał - oh, no i mamy inne 4 segmenty, które dostanę w drugim -
Jako Tommy powiedział wcześniej, wiesz, jak nazywają się jego funkcje i dzwonić do siebie?
Budują ten rodzaj stosu ramki.
Cóż, jeśli główne połączenia foo foo pobiera umieścić na stosie.
Foo nazywa bar, dostać postawmy na stosie, i że zostanie położony na stosie po.
A jak wrócą, każdy się zdjąć ze stosu.
Czego każde z tych miejsc pamięci i trzymać?
Oraz, u góry, które jest segment tekstu zawiera samego programu.
Więc kodu maszynowego, to tam, raz skompilować program.
Następnie każdy zainicjowany zmienne globalne.
>> Więc masz zmienne globalne w programie, a ty mówisz jak, a = 5,
który pobiera umieścić w tym segmencie, a tuż pod tym,
masz niezainicjowane dane globalne, które jest po prostu int,
ale nie powiedzieć, że jest równa niczym.
Uświadom sobie, są to zmienne globalne, więc są one poza głównym.
Więc to oznacza wszelkie zmienne globalne, które są zadeklarowane, ale nie są zainicjowane.
Więc co jest w kupie? Pamięć przydzielona za pomocą malloc, co dostaniemy w trochę.
I w końcu, w stosie jakichkolwiek lokalne zmienne
i wszystkie funkcje można wywołać w każdym z parametrów.
Ostatnia sprawa, naprawdę nie wiedzieć, co zrobić, zmienne środowiskowe,
ale przy każdym uruchomieniu programu, jest coś związane, jak
jest to nazwa osoby, która prowadziła ten program.
I że będzie rodzaju na dole.
W zakresie, adresy pamięci, które są szesnastkowy,
wartościami w górę zaczynają się 0, a oni przejść całą drogę w dół.
W tym przypadku, jeśli jesteś na systemie 32-bitowym,
adres na dole będzie 0x, następnie af, bo to 32 bity,
który jest 8 bajtów, w tym przypadku 8 bajtów odpowiada 8 cyfr szesnastkowych.
Więc tu masz zamiar mieć jakieś 0xFFFFFF i tam będziesz mieć 0.
Więc jakie są wskaźniki? Niektórzy z was mogą nie objęły tego w sekcji przed.
ale poszedł nad nim w wykładzie, więc wskaźnik jest tylko typ danych
które przechowuje, zamiast jakiejś wartości, jak 50, przechowuje adres jakiegoś miejsca w pamięci.
Jak tej pamięci [niezrozumiałe].
Więc w tym przypadku to, co mamy, jest, mamy wskaźnik do liczby całkowitej lub * int,
i zawiera tę szesnastkowy adres 0xDEADBEEF.
>> Więc co mamy, jest, teraz, ten wskaźnik jest w pewnym miejscu w pamięci,
i to tylko, wartość 50 jest w tym miejscu pamięci.
W niektórych systemach 32-bitowych, na wszystkich 32-bitowych systemów, wskaźniki zajmują 32 bitów lub 4 bajtów.
Ale, na przykład, w systemie 64-bitowym, wskaźniki są 64 bity.
Więc to coś będziesz chciał pamiętać.
Więc na koniec-bitowym systemie, wskaźnik jest bity końcowe długo.
Wskaźniki są rodzajem ciężkostrawne bez dodatkowych rzeczy,
więc chodźmy na przykładzie dynamicznej alokacji pamięci.
Co dynamiczny przydział pamięci nie dla Ciebie, lub to, co nazywamy malloc,
to pozwala przeznaczyć jakąś danych poza zestawu.
Tak więc tego rodzaju danych jest bardziej trwały w czasie trwania programu.
Bo jak wiadomo, jeśli deklarują x wewnątrz danej funkcji i że funkcja powraca,
nie masz już dostępu do danych, które zostały zapisane w x.
Jakie wskaźniki zróbmy to pozwolili nam przechowywać pamięci lub przechowywania wartości
w innym segmencie, czyli pamięci sterty.
Teraz, gdy wracamy z funkcji, tak długo, jak mamy wskaźnik
do tego miejsca w pamięci, to co możemy zrobić, to możemy tylko patrzeć na wartości tam.
Spójrzmy na przykład: To jest nasz układ pamięci ponownie.
I mamy tę funkcję main.
Co robi jest - w porządku, tak proste, prawda? - Int x = 5, to po prostu zmienna na stosie w main.
>> Z drugiej strony, teraz zadeklarować wskaźnik, który wzywa do giveMeThreeInts funkcyjnych.
A więc teraz przejść do tej funkcji i tworzymy nowe ramki stosu dla niego.
Jednakże, w tym ramki stosu, deklarujemy int * temp,
które w mallocs 3 liczb dla nas.
Więc rozmiar int da nam jak wiele bajtów to int jest
i malloc daje nam, że wiele bajtów miejsca na stercie.
Więc w tym przypadku, stworzyliśmy wystarczająco dużo miejsca dla 3 liczb całkowitych,
i kupa jest tam droga, dlatego mam wyciągnąć go wyżej.
Gdy skończymy, wrócimy tu, trzeba tylko 3 ints wrócił,
i zwraca adres, w tym przypadku ponad jeżeli jest pamięć.
I wyznaczamy pointer = przełącznik i tam mamy tylko inny wskaźnik.
Ale co, że funkcja zwraca jest ułożone tu i znika.
Tak więc temperatura znika, ale w dalszym ciągu utrzymuje się adres, gdzie
te 3 liczby całkowite są wewnątrz sieci.
Tak więc w tym zestawie, to wskaźniki są Buforuj lokalnie na sterach ramce
lecz pamięć, do której odnoszą się w stos.
>> Czy to ma sens?
[Student] Czy mógłbyś powtórzyć? >> [Józef] Tak.
Więc jeśli wrócę tylko trochę, zobaczysz, że temp przydzielone
część pamięci na stercie tam.
Więc kiedy ta funkcja, giveMeThreeInts powróci, ten stos tutaj zniknie.
I to każdej ze zmiennych, w tym przypadku, to wskaźnik, że ułożone w przeznaczono ramy.
Że zniknie, ale odkąd wróciliśmy temp.
i ustawić wskaźnika = temp, wskaźnik jest teraz będzie wskazywać samą pamięć lokalizacji jako temp był.
Więc teraz, choć tracimy temp, że lokalny wskaźnik,
nadal zachowuje adres pamięci to, co wskazywał wewnątrz tej zmiennej wskaźnika.
Pytania? To może być trochę mylące temacie jeśli nie przeszedłby przez to w sekcji.
Możemy, twój TF pewno tam nad nim i oczywiście możemy odpowiedzieć na pytania
na końcu sesji przeglądarki do tego.
Ale to jest coś w rodzaju złożonego tematu, a mam więcej przykładów, które będą wykazywały się
, które pomogą wyjaśnić co wskaźniki rzeczywistości.
>> W tym przypadku, są równoważne wskaźniki tablic
, więc można po prostu użyć tego wskaźnika jako to samo co int tablicy.
Więc jestem indeksowanie do 0 i zmieniając pierwszą liczbę całkowitą 1,
zmieniając całkowitą do drugiego 2, i 3. do 3 całkowitą.
Więc tylko na wskaźniki. Cóż, pamiętam Binky.
W tym przypadku mamy przydzielone wskaźnik lub zadeklarowaliśmy wskaźnik,
ale na początku, gdy tylko ogłoszony wskaźnik, to nie wskazując nigdzie w pamięci.
To tylko wartości śmieci w jej wnętrzu.
Więc nie mam pojęcia, gdzie to jest wskaźnik wskazujący.
To ma adres, który jest po prostu wypełniony 0 i 1 jest gdzie początkowo zostało zgłoszone.
Nie mogę nic zrobić z tym, aż zadzwonię malloc na nim
a to daje mi trochę miejsca na stercie, gdzie można umieścić wartości środka.
Potem znowu, nie wiem co jest w środku tej pamięci.
Więc pierwszą rzeczą, którą musisz zrobić, to sprawdzić, czy system ma wystarczającą ilość pamięci
dać mi z powrotem 1 całkowitą na pierwszym miejscu, dlatego robię to sprawdzić.
Jeśli wskaźnik jest null, co oznacza, że ​​nie ma wystarczającej ilości miejsca lub innego błędu,
więc powinienem wyjść z mojego programu.
Ale jeśli to nie udało, teraz mogę użyć tego wskaźnika
i to, co robi, to wskaźnik * wynika, gdy adres jest
w przypadku, gdy wartość ta jest, i ustawia się wartość 1.
Więc tutaj, sprawdzamy, czy ta pamięć istniała.
>> Gdy wiesz, że istnieje, to można umieścić w nim
jaką wartość chcesz umieścić w nim, w tym przypadku 1.
Kiedy skończysz z nim, trzeba uwolnić tego wskaźnika
ponieważ musimy wrócić do systemu pamięci, że pytasz w pierwszej kolejności.
Ponieważ komputer nie wie, kiedy mamy z nim zrobić.
W tym przypadku mamy wyraźnie powiedzieć, ok, skończyliśmy z tym pamięci.
Jeśli inny proces potrzebuje, jakiś inny program potrzebuje, tutaj śmiało wziąć.
Co możemy zrobić, to możemy po prostu adres zmiennych lokalnych odbiornika.
Więc int x jest wewnątrz ułożone ramki głównej.
I kiedy użyć tego znaku handlowego, to i operator, co robi jest
trwa x, a x jest tylko niektóre dane w pamięci, ale nie ma adresu.
Znajduje się gdzieś. Poprzez wywołanie & x, co robi to jest to daje nam adres x.
W ten sposób robimy punkt wskaźnika, gdzie x jest w pamięci.
Teraz tylko coś jak * x, mamy zamiar dostać 5 plecy.
Gwiazda nazywa dereferencji go.
Możesz śledzić adres i uzyskać wartość z niego tam przechowywane.
>> Masz pytanie? Tak?
[Student] Jeśli nie zrobić 3-spiczasty rzeczy, to jeszcze skompilować?
Tak. Jeśli nie zrobić 3-wskaźnik rzeczy, to jeszcze zamierza skompilować,
ale pokażę ci, co się dzieje w drugim, a nie robiąc, że
że to, co nazywamy wyciek pamięci. Nie dajesz systemowi
kopię swojej pamięci, więc po jakimś czasie program będzie gromadzić
pamięci, która nie jest pomocą, a nic innego nie może go użyć.
Jeśli kiedykolwiek widziałeś Firefoksa z 1,5 milionów kilobajtów na komputerze,
w Menedżerze zadań, to co się dzieje.
Masz wyciek pamięci w programie, że nie jesteś obsługi.
Więc w jaki sposób wskaźnik pracy arytmetyka?
Cóż, arytmetyka wskaźnik jest coś w rodzaju indeksowania do tablicy.
W tym przypadku, mam wskaźnik, a co mogę zrobić, to zrobię punkt wskaźnik do pierwszego elementu
tej tablicy 3 liczby całkowite, że już przydzielone.
Więc co teraz mam zrobić, wskaźnik gwiazda zmienia tylko pierwszy element na liście.
Gwiazda wskaźnik +1 punktów tutaj.
Tak wskaźnik jest tutaj, wskaźnik +1 jest tutaj, wskaźnik +2 jest tutaj.
>> Więc po prostu dodając 1 to samo co poruszanie się tej tablicy.
Co możemy zrobić, to kiedy robimy wskaźnik +1 dostajesz adres tutaj,
i aby uzyskać wartość w tutaj, można umieścić gwiazdę od całego wyrażenia
do nieprawidłowego go.
Tak więc, w tym przypadku, jestem wyznaczenia pierwszego miejsca w tej tablicy 1,
Lokalizacja na 2 sekundy, a trzecie miejsce do 3.
Wtedy to, co robię tutaj jest mi drukowanie nasz wskaźnik 1,
który po prostu daje mi 2.
Teraz jestem zwiększający wskaźnik, więc wskaźnik wynosi wskaźnik 1,
który porusza się do przodu.
I tak teraz, czy mogę wydrukować wskaźnik 1, wskaźnik +1 jest teraz 3,
w tym przypadku, który drukuje się 3.
Oraz w celu swobodnego czegoś, wskazówka, że ​​dam ją
może być skierowana na początku tablicą powrocie z malloc.
Tak więc, w tym przypadku, gdybym miał zadzwonić 3 tutaj, to nie byłoby w porządku,
, ponieważ znajduje się on w środku tablicy.
Muszę odjąć aby dostać się do oryginalnej lokalizacji
Początkowy 1-cia spot przed mogę uwolnić go.
Tak, tu jest bardziej zaangażowani przykładem.
W tym przypadku mamy do rozdziału 7 znaków w tablicy znaków.
>> I w tym przypadku to, co robimy, to jesteśmy w pętli na pierwszym 6 z nich,
i jesteśmy ustawiając je do Z.
Tak więc, na int i = 0, i> 6, i + +
Zatem wskaźnik + będzie po prostu dać nam, w tym przypadku,
Wskaźnik, wskaźnik +1, wskaźnik +2, wskaźnik +3, i tak dalej, i tak dalej w pętli.
Co to będzie zrobić, to robi się z tego adresu, dereferences to, aby uzyskać wartość,
a zmiany tej wartości do Z.
Następnie na koniec pamiętaj, to ciąg znaków, tak?
Wszystkie łańcuchy muszą kończyć się znakiem NULL kończącego.
Więc, co mogę zrobić, to w wskaźnik 6 stawiam znak null terminator w.
A teraz o co mi właściwie robi tu realizuje printf dla łańcucha, prawda?
>> Tak więc, gdy nie printf teraz, kiedy to skończył się ciąg?
Gdy trafi na znak null falowy.
Tak więc, w tym przypadku, moje oryginalne wskaźnik wskazuje na początek tablicy.
Wydrukować pierwszy znak na zewnątrz. I przenieść ją na jeden.
Wydrukować ten znak na zewnątrz. I przenieść ją.
I robić to aż do końca.
A teraz * wskaźnik końcowy będzie dereference to i uzyskać znak null kończącą się.
A więc moja pętla działa tylko wtedy, gdy wartość nie jest znak null kończące.
Tak, teraz mogę wyjść z tej pętli.
I tak, jeśli odjąć 6 z tego wskaźnika,
Wrócę aż do początku.
Pamiętaj, że to robię, bo muszę iść na początku w celu uwolnienia go.
>> Tak, wiem, że było dużo. Czy są jakieś pytania?
Proszę, tak?
[Niezrozumiały pytanie uczniowski]
Można powiedzieć, że głośniej? Przepraszam.
[Student] Na ostatnim slajdzie tuż przed uwolnionym wskaźnik,
gdzie się faktycznie zmieniając wartość wskaźnika?
[Józef] Tak, jest tutaj. >> [Student] Oh, w porządku.
[Józef] Tak, mam wskaźnik minus minus, w prawo,
który porusza się o jeden rzeczy, a potem zwolnić go,
ponieważ wskaźnik ma być skierowana na początku tablicy.
[Student] Ale to nie byłaby potrzebna, gdybyś zatrzymał się po tej linii.
[Józef] Więc, gdybym zatrzymał się po to, to byłoby uznane za wyciek pamięci,
bo nie uruchomić darmo.
[Student] I [niezrozumiały] po pierwszych trzech liniach, gdzie mieli wskaźnik 1 [niezrozumiałe].
[Józef] Uh-huh. Więc, co to pytanie tutaj?
Przepraszam. Nie, nie. Idź, idź, proszę.
[Student] Tak, nie jesteś zmianę wartości wskaźników.
Nie musiałby zrobić wskaźnik minus minus.
[Józef] Tak, dokładnie.
Tak więc, gdy zrobić wskaźnik i wskaźnik 2 +1,
Nie robię wskaźnik równy wskaźnik +1.
Tak więc, pozostaje tylko wskaźnik wskazuje na początku tablicy.
Dopiero gdy ja plus plus, że ustawia wartość z powrotem do wskaźnika,
faktycznie porusza to razem.
Dobrze.
Więcej pytań?
>> Ponownie, jeśli jest to rodzaj przytłaczające, zostanie to opisane w sesji.
Zapytaj kolegów nauczania o tym, a my możemy odpowiedzieć na pytania na końcu.
I zazwyczaj nie chcemy zrobić ten minus rzecz.
To musi wymagać mnie śledzenie jak wiele się offset w tablicy.
Tak w ogóle, to po prostu wyjaśnić, jak działa wskaźnik arytmetycznych.
Ale to, co zwykle jak zrobić, to chcemy, aby utworzyć kopię wskaźnika,
i wtedy będziemy używać tej kopii, gdy idziemy po w ciągu.
Tak więc, w przypadku korzystania z tych kopii, aby wydrukować cały ciąg,
ale nie trzeba robić jak wskaźnik minus 6 lub śledzić ile przeszliśmy w tym,
tylko dlatego, że wiemy, że nasz pierwotny punkt nadal wskazywał na początku listy
i wszystko to, co to było zmieniane kopia.
Tak w ogóle, zmiany kopie oryginalnego wskaźnika.
Nie staraj się coś w rodzaju - don't zmieniać oryginalne kopie.
Próba zmiany tylko kopie oryginału.
Tak więc, można zauważyć, gdy mijamy ciąg do printf
nie musisz postawić gwiazdkę przed nim tak jak my z wszystkimi dereferences innych, prawda?
Tak więc, jeśli wydrukować cały ciąg% s oczekuje jest adres,
w tym przypadku, a wskaźnik lub jak w tym przypadku w postaci tablicy.
>> Postacie, char * s, i tablice są tak samo.
Pointer jest znaków i tablic znaków to samo.
I tak, wszystko co musisz zrobić, to przekazać w wskaźnika.
Nie mamy do przekazania w jak * wskaźnik lub coś podobnego.
Więc, tablice i wskaźniki to samo.
Kiedy robisz coś jak x [y] tutaj na tablicy,
co robi pod maską jest to mówiąc, dobrze, że jest to tablica znaków,
więc jest to wskaźnik.
A więc x to samo,
i tak to, co robi, jest to dodaje y do x,
co jest tym samym, co naprzód w pamięci, że dużo.
I teraz x + y daje nam jakiś adres,
i nieprawidłowego adresu lub śledzić strzałkę
w przypadku gdy lokalizacja w pamięci jest i uzyskać wartość z tej lokalizacji w pamięci.
Tak, więc te dwa są dokładnie tym samym.
To jest po prostu syntaktyczne cukru.
Robią to samo. Są po prostu różne syntactics dla siebie.
>> Więc, co może pójść źle z wskaźniki? Jak, partii. Okay. Tak, złe rzeczy.
Złe rzeczy, które możesz zrobić nie sprawdzasz, czy wywołanie malloc zwraca null, prawda?
W tym przypadku, pytam system dać mi - co to za numer?
Jak 2 miliardów razy 4, bo rozmiar jest liczbą całkowitą 4 bajty.
Pytam go, jak 8 miliardów bajtów.
Oczywiście komputer nie będzie w stanie dać mi tyle powrotem pamięci.
I nie, czy ta jest nieważna, więc kiedy staramy się dereference to tam -
śledzić strzałkę, gdzie to będzie - nie ma tej pamięci.
To jest to, co nazywamy dereferencji wskaźnika pustego.
I to w zasadzie jest ci powodem do segfault.
Jest to jeden ze sposobów, można wysypać.
Innych złych rzeczy można zrobić - no cóż.
To było dereferencji wskaźnika pustego. Okay.
Inne złe rzeczy - dobrze, by to naprawić wystarczy umieścić tam czek
która sprawdza, czy wskaźnik jest null
i wyjść z programu, jeżeli zdarza się, że malloc zwraca wskaźnika pustego.
To xkcd komiks. Ludzie rozumieją go teraz. Jakby.
>> Tak, pamięć. I poszedłem nad tym.
Nazywamy malloc w pętli, ale za każdym razem wywołujemy malloc
tracimy orientację, gdzie wskaźnik ten jest skierowany do,
ponieważ jesteśmy przebijania go.
Tak, pierwsze wywołanie malloc daje mi pamięć tutaj.
Moje wskazówki wskaźnik do tego.
Teraz, nie uwolnić go, więc teraz ja nazywam malloc ponownie.
Teraz podkreśla tutaj. Teraz moja pamięć jest skierowany tutaj.
Wskazując tutaj. Wskazując tutaj.
Ale ja straciłem z adresami wszystkich pamięci tutaj, że przydzielone.
A więc teraz nie mam żadnego odniesienia do nich więcej.
Tak więc, nie mogę uwolnić ich poza tym pętli.
I tak, aby naprawić coś takiego,
jeśli zapomnisz wolnej pamięci i masz ten wyciek pamięci,
Musisz zwolnić pamięć wewnątrz tej pętli raz jesteś z nim zrobić.
Cóż, to jest to, co się dzieje. Wiem dużo o tobie nienawidzę tego.
Ale teraz - yay! Otrzymasz jak 44.000 kilobajtach.
Tak więc, można zwolnić ją na końcu pętli
oraz że zamierza po prostu zwolnić pamięć za każdym razem.
Zasadniczo, twój program nie ma wyciek pamięci anymore.
>> A teraz jeszcze coś można zrobić, to zwolnić trochę pamięci, że już poprosił o dwa razy.
W tym przypadku, możesz coś malloc, zmienić jego wartość.
Możesz zwolnić go raz, bo mówił, że z nim zrobić.
Ale potem uwolnił go ponownie.
To jest coś, co jest bardzo złe.
To nie będzie początkowo segfault,
ale po jakimś czasie, co to nie jest podwójnie uwalniając ta psuje swoją strukturę sterty,
a dowiesz się nieco więcej o tym, jeśli zdecydujesz się wziąć udział w zajęciach jak CS61.
Ale zasadniczo po czasie, gdy komputer będzie się mylić
komórki pamięci o tym, co, gdzie i są tam, gdzie jest przechowywana -
w których dane są przechowywane w pamięci.
I tak uwolnienie wskaźnik dwukrotnie jest złe, że nie chcę tego robić.
>> Inne rzeczy, które mogą pójść źle nie używa sizeof.
Tak więc, w tym przypadku malloc 8 bajtów,
i to jest to samo, co dwóch liczb całkowitych, prawda?
Tak, że jest całkowicie bezpieczne, ale to?
Cóż, jak Lucas mówił o na różnych architekturach
całkowite mają różne długości.
Tak, na urządzeniu, którego używasz, liczby całkowite są około 4 bajty,
ale na innym systemie może być 8 bajtów lub mogą być one 16 bajtów.
Tak więc, jeśli po prostu użyć tego numeru tutaj,
ten program może działać na urządzenie,
ale to nie będzie przydzielić wystarczającej ilości pamięci na innym systemie.
W tym przypadku, jest to, co jest operator sizeof stosuje.
Gdy dzwonimy sizeof (int), co robi to jest
daje nam wielkość liczby całkowitej w systemie, że program jest uruchomiony.
Tak więc, w tym przypadku, sizeof (int) zwraca 4 na coś takiego urządzenia,
Teraz wola i 4 * 2, które są 8
która jest tylko ilość miejsca niezbędnego do dwóch liczb całkowitych.
Na innym komputerze, jeśli int jest jak 16 bajtów lub 8 bajtów,
to jest po prostu powróci tyle bajtów do przechowywania tej kwoty.
>> I wreszcie, kodowanym.
Tak więc, jeśli chcesz przechowywać planszę sudoku w pamięci, w jaki sposób możemy to zrobić?
Można o tym myśleć jak zmienna dla pierwszej rzeczy,
Zmienna do drugiej rzeczy, zmiennej w trzecim rzeczy,
zmienna w czwartym rzeczy - źle, prawda?
Zatem jeden poprawę można dokonać na górze to zrobić 9 x 9 tablicę.
To dobrze, ale co jeśli chce włączyć inne rzeczy z planszy sudoku
jak to, co trudność zarządu jest
lub, na przykład, co twój wynik jest, lub ile czasu zabrało Ci rozwiązać ten dział?
Cóż, co można zrobić, to można utworzyć strukturę.
Co mam w zasadzie powiedzieć, że definiuję tę strukturę tutaj,
i jestem definiowania planszę sudoku, który składa się z płyty, która jest 9 x 9.
>> I co to ma to ma wskaźniki do nazwy poziomu.
Posiada również xiy, które są współrzędne, gdzie jestem teraz.
Ma też czas spędzony [niezrozumiałe], i ma liczbę ruchów jakie wprowadzane do tej pory.
I tak w tym przypadku, można zgrupować całą masę danych do tylko jednej struktury
zamiast je jak latają w jak różnych zmiennych
że tak naprawdę nie można śledzić.
A to pozwala nam mieć tylko ładny składnię typu odwołującego różne rzeczy wewnątrz tej struktury.
Ja tylko mogę board.board i dostaję planszę sudoku powrotem.
Board.level, rozumiem, jak trudne to jest.
Board.x i board.y mi współrzędne, gdzie mogę być w zarządzie.
A więc mam dostęp do tego, co nazywamy pola struktury.
To definiuje sudokuBoard, który jest typ, który mam.
A teraz jesteśmy tutaj. Mam zmienną o nazwie "deska" z sudokuBoard typu.
A więc teraz mogę uzyskać dostęp do wszystkich pól, które tworzą tę strukturę tutaj.
>> Wszelkie pytania dotyczące elemencie? Tak?
[Student] Dla int x, y, to uznane zarówno w jednej linii? >> [Józef] Uh-huh.
[Student] Tak, można po prostu zrobić z nich wszystkich?
Jak w x, y czasy, że całkowite przecinek?
[Józef] Tak, na pewno można to zrobić, ale powodem umieścić xiy na tej samej linii -
i pytanie jest dlaczego możemy po prostu to zrobić na tej samej linii?
Dlaczego nie możemy po prostu umieścić wszystkie z nich w tej samej linii jest
X i Y są powiązane ze sobą,
i jest to tylko stylistycznie bardziej poprawne, w pewnym sensie,
bo to zgrupowanie dwóch rzeczy w tym samym wierszu
że podobnie jak rodzaj odnosi się do tego samego.
A ja po prostu podzielić te strzępy. To jest po prostu coś w stylu.
To sprawia, że ​​funkcjonalnie nie zmieniają.
Wszelkie inne pytania dotyczące elemencie?
Można zdefiniować Pokedex z struct.
Pokémon ma numer i ma list, właściciela, typu.
A potem, jeśli masz tablicę Pokémon można tworzą Pokedex, prawda?
Okay, cool. Tak, pytania na elemencie. Są podobne do struktur.
>> Wreszcie, GDB. Co GDB pozwala zrobić? Pozwala debugować program.
A jeśli nie był używany GDB, chciałbym zaleca oglądanie krótkich
i po prostu się nad tym, co GDB jest, jak z nim pracować, jak można z niego korzystać,
i testowania w programie.
I co z tego GDB pozwala zrobić to że pozwala wstrzymać [niezrozumiały] do swojego programu
i praktyczne line.
Na przykład chcę, aby wstrzymać wykonanie jak linii 3 w moim programie,
a ja jestem na linii 3 można wydrukować wszystkie wartości, które są tam.
A więc to, co nazywamy jak zatrzymując się w linii
jest nazywamy to oddanie punkt przerwania na tej linii
a następnie możemy wydrukować zmienne na stanie programu w tym czasie.
>> Możemy następnie stamtąd krok po kroku program linia po linii.
, A następnie można sprawdzić stan stosu w czasie.
I tak w celu korzystania z GDB, co możemy zrobić, to nazywamy brzękiem na plik C,
ale musimy przekazać go flagą-ggdb.
A kiedy skończymy, że po prostu uruchomić gdb na wynikowego pliku wyjściowego.
I tak trochę jak masę tekstu tak,
ale tak naprawdę wszystko, co musisz zrobić, to wpisać w poleceniach na początku.
Złamać główny stawia przerwania na main.
Lista 400 wymieniono linie kodu wokół linii 400.
A więc w tym przypadku można po prostu rozejrzeć się i powiedzieć, oh,
Chcę, aby ustawić punkt przerwania na linii 397, która jest ta linia,
a następnie program biegnie do niego i to się złamać.
To będzie wstrzymać tam, i można wydrukować, na przykład, wartości niskie lub wysokie.
I tak istnieje kilka poleceń, które musisz wiedzieć,
i ten pokaz będzie się na stronie internetowej,
więc jeśli chcesz po prostu odwołać je lub jak umieścić je na swoich oszukiwać arkuszy, tutaj.
>> Cool. To był Quiz weryfikacja 0 i będziemy trzymać się, jeśli masz jakiekolwiek pytania.
Dobrze.
>> [Oklaski]
>> [CS50.TV]