>> [Prehrávanie hudby]
>> [Videoprehrávanie]
>> -Je Klame.
>> -O čom?
>> -Neviem.
>> -Tak Čo vieme?
>> -to V 9:15, Ray Santoyo bol pri bankomate.
Jo.
Takže otázka je, čo robil v 9:16?
>> -Shooting Č.9 milimeter na niečo.
Možno videl ostreľovača.
>> -alebo Pracoval s ním.
>> Počkať.
Naspäť o jednu.
>> -Čo vidíš?
>> -Bring Jeho tvár plnom rozsahu.
>> His okuliare.
>> -Je To odraz.
>> -Je To baseballového tímu Nuevitas.
To je ich logo.
>> -A Hovorí sa kto má na sebe tú bundu.
>> [END Prehrávanie]
>> DAVID Malan: Dobre.
To je CS50 a to je trochu viac z [nepočuteľný], s ktorou ste
pustili s problémom set štyri.
Dnes začneme trochu vyzerať viac hlboko sa na tieto veci zvanej ukazovatele,
ktorý aj keď je to docela tajomný tému,
Ukazuje sa, že to bude byť prostriedky, ktoré sme
môže začať stavať a montáže omnoho sofistikovanejšie programy.
Ale my sme to urobili na poslednú stredu prostredníctvom nejakého claymation prvého.
Takže to, odvolanie, je Binky a my ho použiť
aby sa pozrieť na program, ktorý sa naozaj robiť nič zaujímavého,
ale to predsa odhalil niekoľko problémov.
Takže začať dnes, prečo chodíme rýchlo prechádzať niektoré z týchto krokov,
sa snaží páliť do ľudského hľadiska je presne to, čo sa tu deje
a prečo je to zlé, a potom prejsť na a skutočne začať budovať niečo,
s touto technikou?
Tak to bol prvý dva riadky v tomto programe
a Laicky povedané, to, čo sú tieto dva riadky robia?
Niekto, kto je primerane komfortné s tým, čo je deklarované na obrazovke?
Aké sú tieto dva riadky robia?
To nie je všetko, sa líši od jedného týždňa,
ale tam je nejaká nová špeciálna symbol.
Jo?
Tam vzadu.
>> Divákov: Deklarovanie ukazovatele?
DAVID Malan: znova, povedz?
Divákov: Deklarovanie ukazovatele?
DAVID Malan: Deklarácia ukazovatele a poďme upresniť to trochu viac.
Divákov: [Nepočuteľné] adresa x a potom y.
DAVID Malan: A potom sa zaoberať.
Takže, čo konkrétne robíme je deklarujeme dve premenné.
Tieto premenné, hoci, idú byť typu int hviezdy, ktoré
konkrétnejšie znamená, idú na ukladanie
adresu int, respektíve, x a y.
Teraz existujú nejaké hodnoty?
Existujú nejaké skutočné adresy v nich dve premenné v tomto okamihu?
Nie.
Je to len tzv hodnoty odpadky.
Ak nemáte skutočne priradiť variabilné, čo bolo v RAM
predtým sa chystá vyplniť nulami a tie, obe z týchto premenných.
Ale my ešte nevieme čo sú a to je
Bude kľúčom k prečo Binkym stratil hlavu minulý týždeň.
>> Tak toto bol claymation stelesnenie tohto
kedy máte len dve premenné, malé kruhové kusy hliny,
ktoré možno ukladať premenné, ale ako zabalený up šípky naznačujú,
oni nie sú v skutočnosti ukazujúci kamkoľvek o sebe známe.
A tak sme mali tento riadok, a to bol nový minulý týždeň, malloc pre pamäť
alokácie, čo je len ozdobný spôsob, ako rozprávanie operačný systém, Linux
alebo Mac OS alebo Windows, hej, daj mi nejakú pamäť,
a všetko, čo musíte povedať, operačný systém
je to, čo keď žiadajú to pre pamäť.
Nie je to bude jedno, čo budeš robiť s tým,
ale musíte povedať prevádzkové Systém, čo cestou malloc.
Jo?
>> Divákov: Koľko?
DAVID Malan: Koľko?
Koľko v bytoch, a tak, tak sa opäť neobvyklý spôsob príklad, je len povedať,
daj mi veľkosť int.
Teraz, veľkosť int štyri bajtov alebo 32 bitov.
Tak to je len spôsob, ako povediac, hej, operačný systém,
daj mi štyri bajtov pamäte že môžem použiť mám k dispozícii,
a najmä, čo robí malloc Daňové priznanie s ohľadom
k tomuto kusu štyri bajty?
Publikum: Adresa?
DAVID Malan: Adresa.
Adresa tohto kusu štyroch bajtov.
Presne tak.
A tak to je to, čo je uložené v konečnom v x, a to je dôvod, prečo sme naozaj nemám
jedno, čo je počet, ktorý adresa, či už je to OX1 alebo OX2
alebo nejaký tajomný hexadecimálne adresa.
Len Staráme obrazovo že táto premenná x je teraz
smerovať k tomuto kusu pamäti.
Takže šípka predstavuje ukazovateľ, alebo Viac špecificky, adresa pamäte.
Ale opäť, my nie typicky jedno čo tieto skutočné adresy.
Teraz hovorí, že tento riadok čo v Laicky povedané?
Hviezda x dostane 42 bodkočiarku.
Čo to znamená?
Chceš ísť?
Nepoškrabte krk.
>> Divákov: Adresa x je na 42.
>> DAVID Malan: Adresa x je na 42.
Nie tak celkom.
Tak blízko, ale nie tak celkom, pretože tam je hviezda, ktorá je prefixu túto x.
Preto musíme vyladiť trochu.
Jo?
>> Divákov: Hodnota, že pointer x ukazuje, je 42.
DAVID Malan: OK.
Hodnota, že ukazovateľ je x ukázal na, povedzme, bude 42,
alebo inak povedané, hviezdu x hovorí, choďte na adresu akéhokoľvek
je v x, či už je to 1 Oxford Ulice alebo 33 Oxford Street
alebo OX1 alebo ox33, čokoľvek že číselná adresa,
hviezda x je dereferencing x.
Tak choďte na túto adresu a potom dal číslo 42 tam.
Tak, že by bolo ekvivalent spôsob, ako povedať, že.
Tak to je všetko v poriadku a potom by sme predstavovať obraz
takto, kde sme pridali element 42 na tento kus štyroch
bajtov na pravej strane, ale Táto linka bola, kde veci pokazilo
a Binky hlava vyskočila off v tomto bode,
preto, že zlé veci sa stávajú, keď ste dereferencia hodnôt odpadky
alebo dereferencia neplatné ukazovatele, a ja hovorím neplatné
pretože v tomto bode príbeh, čo je vo vnútri y?
Aká je hodnota y na báze Na posledných niekoľkých krokoch?
Jo?
Čo je to?
>> Divákov: Adresu.
DAVID Malan: adresy.
Malo by sa jednať o adresu ale som inicializácii to?
Takže mám ešte nie.
Takže to, čo je známe, že je tam?
Je to len nejaký odpad hodnotu.
Mohlo by to byť akákoľvek adresa od nuly do 2000000000 ak máte dva koncerty RAM,
alebo nula až 4000000000, ak ste dostal štyri GB pamäte RAM.
Je to nejaký odpad hodnota, ale problém je
že operačný systém, ak nie je vám dal
že kus pamäte špecificky že sa snažíte ísť do,
to všeobecne bude spôsobovať to, čo sme videli ako poruchu segmentáciu.
Takže v skutočnosti, niektoré z vás, ktorí majú bojoval na problémy v úradných hodinách
alebo problémov, ktoré je viac všeobecne sa snaží prísť na to,
chyba segmentácia, že vo všeobecnosti znamená,
ste dotýka segment pamäti, že by ste nemali byť.
Tie dotýka pamäť, ktorá operačný systém nemá
nechá vás dotknúť, či už je to tým, že ide príliš ďaleko vo svojom poli
alebo od tejto chvíle, či už je to preto, že ste sa dotknete
pamäť, ktorá proste nejaký odpad hodnota.
>> Tak robí hviezda x tu druh nedefinované chovanie.
Nikdy by ste nemali robiť, pretože kurzy sú, program to len bude k havárii,
pretože ste hovoril, choďte na túto adresu
a nemáte tušenie, kde že adresa v skutočnosti je.
Teda systém je pravdepodobné spadne svoj program
ako výsledok a naozaj, to je čo sa tam stalo, aby Binkym.
Takže nakoniec, Binky fixné tento problém s tým.
Takže tento program sám bol chybný.
Ale ak ste nejako dopredu a namiesto toho spustiť tento riadok,
y sa rovná x jednoducho znamená čokoľvek adresa je x, tiež dať ju do y.
>> A tak obrazovo, máme reprezentovaný to s dvoma šípkami
z x a y z ukazujúci na rovnaké miesto.
Takže sémanticky, x je rovné k y, pretože oba tieto
ukladáte rovnaký adresa, ergo ukázal na 42,
a teraz, keď hovoríte, hviezda y, choďte na adresu v y,
to má zaujímavý vedľajší efekt.
Takže adresu v y je to isté ako adresu v x.
Takže ak ste, že ísť na adresu v y a zmeňte hodnotu na 13,
kto iný je ovplyvnený?
X, bod D, aby som tak povedal, by mali byť ovplyvnené tiež.
>> A skutočne, ako sa Nick nakreslil tento obrázok v claymation bolo presne to.
Aj keď sme sledovať ukazovateľ y, sme skončili na rovnakom mieste,
a tak ak by sme mali na vytlačenie out X alebo Y je pointee,
potom by sme vidieť hodnotu 13.
A teraz, hovorím pointee byť v súlade s videom.
Programátori, k môjmu vedomosti, vlastne nikdy
povedz slovo pointee, to, čo je špicatá
na, ale pre konzistencie s videom, realizovať
to je všetko, čo bolo znamenalo v takejto situácii.
Takže akékoľvek otázky týkajúce claymation alebo ukazovátka alebo malloc ešte nie?
Nie?
Dobre.
>> Takže bez ďalšieho ado, poďme sa pozrieť
na to, kde to má vlastne bol používaný na nejakú dobu.
Takže sme mali túto knižnicu CS50 že má všetky tieto funkcie.
Použili sme GetInt veľa, getString, Pravdepodobne GetLongLong skôr
v mojom pset jedného alebo tak, ale čo sa skutočne deje?
Dobre, poďme sa rýchlo pozrieť pod kapotou v programe, ktorý
inšpiruje, prečo dávame vám to CS50 knižnica, a dokonca od minulého týždňa,
sme začali brať tie, tréningové kolesá off.
Takže toto je teraz zoradená z toho, čo posmrtné
má sa deje vnútri knižnice CS50,
aj keď sme teraz začne pohybovať preč od toho u väčšiny programov.
>> Takže toto je program s názvom scanf 0.
Je to super krátke.
To sa jednoducho musí tieto riadky, ale to zavádza funkciu nazvanú scanf
že sme skutočne uvidí v moment vnútri knižnice CS50,
aj keď v trochu inej podobe.
Takže tento program na riadku 16 je deklarovanie premennej x.
Tak mi daj štyri byty pre int.
Je to už hovoril užívateľa, číslo, prosím, a potom
To je zaujímavé, že linka v skutočnosti spája dohromady minulý týždeň
a to.
Scanf, a potom všimnete, že trvá formát reťazca, rovnako ako printf,
% I znamená int, a potom to trvá Druhý argument, ktorý vyzerá trochu
funky.
Je to ampersand x, a pripomenúť, sme videli len raz minulý týždeň.
Čo ampersand x predstavuje?
Čo ampersand robiť v C?
Jo?
>> Divákov: Adresa.
DAVID Malan: Adresa.
Takže je to naopak prevádzkovateľa hviezdy,
že sa prevádzkovateľ hviezda hovorí, choďte na táto adresa, ampersand operátor
hovorí, zistiť adresa tejto premennej,
a preto je tento kľúč, pretože Účelom scanf v živote
je pre skenovanie užívateľa vstup z klávesnice,
v závislosti na čo on alebo ona typy, a potom si prečítajte vstup daného užívateľa
do premennej, ale videli v posledných dvoch týždňoch
že táto funkcia odkladacia, že sme Snažil ľahko implementovať
Len rozbité.
Pripomeňme si, že s funkciou odkladací, ak by sme proste vyhlásil, A a B, ako ints,
sme sa úspešne swap dve premenné vnútro swapu
Rovnako ako u mlieka a úradnom vestníku, ale akonáhle odkladacie vrátil,
čo bol výsledok s ohľadom k x a y, pôvodné hodnoty?
Nič.
Jo.
Nič sa nestalo, že čas, pretože swapy meniť iba jeho miestnej kópie,
čo znamená, všetky Tentoraz, kedykoľvek máme
odovzdával v argumentoch k funkciám, my sme
práve prechádzajúcej kópie týchto argumentov.
Môžete to urobiť s tým čo chcete s nimi,
ale oni budú mať žiadny vplyv na pôvodné hodnoty.
Tak to je problematické, ak vás Chcete mať funkciu ako scanf
v živote, ktorých účelom je skenovanie užívateľského vstupu z klávesnice
a potom vyplniť prázdne miesta, tak aby hovoriť, to je, dať premenné, ako je x
hodnotu, pretože keby som bol len prejsť x na scanf,
ak sa domnievate, logiku posledný týždeň, môže scanf robiť, čo chce
s kópiou x, ale to nemohlo trvalú zmenu x, keď dávame
scanf mapu pokladu, aby som tak povedal, kde x označuje miesto, pričom
míňame v adrese X tak, scanf môže ísť tam a vlastne zmena
hodnota x.
A tak naozaj, všetko že tento program robí
keď urobím scanf 0, v mojom zdroji 5 m adresár, aby scanf 0,
dot lomítko scanf, číslo prosím 50, vďaka za 50.
>> Takže to nie je všetko tak zaujímavé, ale čo sa skutočne deje
je to, že akonáhle som zavolať scanf tu, hodnotu x
sa trvale meniť.
Teraz sa to zdá pekné a dobre, a v skutočnosti je
Zdá sa, ako by sme vlastne nepotrebujeme CS50 knižnica vôbec už nie.
Napríklad, poďme bežať tento viac tu raz.
Dovoľte mi, aby som ho znova na sekundu.
Skúsme číslo, prosím, a namiesto toho hovorí, 50 ako predtým,
povedzme, nie.
OK, to je trochu divný.
OK.
A len niektoré nezmysel tu.
Takže to nevyzerá, zvládnuť chybné situácie.
Preto musíme minimálne začiatok pridá nejaká chyba v kontrole
aby sa uistil, že má užívateľ napísané v skutočného počtu, ako 50,
pretože vraj písania slova nie je detekovaný ako problematické,
ale pravdepodobne by malo byť.
>> Pozrime sa na túto verziu teraz to je môj pokus o reimplement getString.
Ak scanf má toto všetko funkčnosť postavený v roku,
Preto sme boli pustili s týmito koliesok, ako getString?
No, tu je snáď moje vlastné jednoduchá verzia getString
pričom pred týždňom, možno som už uviedol, daj mi reťazec a hovoria vyrovnávacej pamäte.
Dnes, budem začať práve povediac: char hviezdu, ktorú si spomínať,
je to len synonymá.
Vyzerá to desivejšie, ale je to presne to isté.
Tak mi daj premennú s názvom vyrovnávacej pamäte že to bude ukladať reťazec,
povedzte užívateľské reťazec, prosím, a potom, rovnako ako predtým,
Skúsme si požičať tejto lekcii scanf % S tentoraz a odovzdať do vyrovnávacej pamäte.
Teraz, rýchla kontrola zdravý rozum.
Prečo som nehovorím ampersand vyrovnávacej pamäte tentoraz?
Vyvodiť z predchádzajúceho príkladu.
Divákov: Char hviezda je ukazovateľ.
DAVID Malan: Presne tak, pretože tentoraz, char
Hviezda je už ukazovateľ, adresu, podľa definície tejto hviezdy bytia tam.
A ak scanf očakáva adresu, stačí len prejsť do vyrovnávacej pamäte.
Nepotrebujem hovoriť ampersand vyrovnávacej pamäte.
Pre zvedavá, mohol by ste niečo také.
Mala by mať iný význam.
To by vám ukazovateľ na ukazovateľ, ktorý je vlastne
platný vec C, ale pre Teraz, poďme aby to jednoduché
a udržať príbeh konzistentné.
Ja som jednoducho ísť prejsť do vyrovnávacej pamäti, a to je správne.
Problémom však je toto.
Nechaj ma ísť napred a spustenie tohto Program po kompilácii to.
Vykonajte scanf 1.
Sakra, moje kompilátora lov moja chyba.
Dajte mi jednu sekundu.
Rinčanie.
Povedzme, že scanf-1.C.
OK.
Tam sme ísť.
Potrebujem to.
CS50 ID má rôzne nastavenia konfigurácie
že vás chráni proti sebe.
Potreboval som vypnúť tie by spustenie rinčanie ručne tejto doby.
Takže reťazec prosím.
Chystám sa ísť dopredu a zadajte v mojej obľúbenej Hello World.
OK, null.
To nie je to, čo som napísal.
Takže je to svedčí o niečo mýliť.
Nechaj ma ísť dopredu a zadajte v naozaj dlhý reťazec.
Vďaka za null, a ja neviem, ak budem mať možnosť to zlyhanie.
Skúsme trochu kópie vložiť, a uvidíme, či to pomôže.
Stačí vložiť veľa to.
Je to určite väčšie string než obvykle.
Poďme sa len naozaj napísať.
Nie.
Dočerta.
Command not found.
Tak to je nesúvisí.
Je to preto, že som vložiť niektoré zlé znaky,
ale to ukáže, nebude fungovať.
>> Skúsme to ešte raz, pretože je to väčšia zábava, keď sme vlastne jeho zrútenie.
Poďme napíšte to a teraz som bude kopírovať naozaj dlhý reťazec
a teraz uvidíme, či budeme môže spôsobiť zrútenie túto vec.
Všimnite si, som vynechal priestory a Nové linky a bodkočiarkami
a všetky funky znaky.
Enter.
A teraz sieť práve bytia pomaly.
Držal som sa Command-V príliš dlhý, jasne.
Dočerta!
Command not found.
>> OK.
No, ide o to, Avšak nasledujúce.
Takže čo sa vlastne deje Na tomuto vyhláseniu
char hviezdy vyrovnávacej pamäte na riadku 16?
Takže to, čo som dostať Prehlasujem, keď ukazovateľ?
Všetko Začínam je hodnota štyroch bajtov volal vyrovnávacej pamäte, ale to, čo je vo vnútri nej
práve teraz?
Je to len nejaký odpad hodnotu.
Vzhľadom k tomu, kedykoľvek budete deklarovať premennú v C, je to len nejaký odpad hodnota,
a my teraz začíname Podrazeniu tejto reality.
Teraz, keď poviem scanf, choďte na túto adresu
a dal za akýchkoľvek užívateľ zadá.
Ak sa používateľ zadá vo ahoj svet, no, kde mám dať?
Buffer je hodnota odpadky.
>> Takže to je niečo ako šíp to je ukázal, kto vie kde.
Možno, že je to ukázal priamo tu v mojej pamäti.
A tak, keď sa používateľ druhy uvedené v hello world,
sa program pokúsi dať string hello world spätné lomítko 0
sa tým, že kus pamäte.
Ale s vysokou pravdepodobnosťou, ale zjavne nie je 100% pravdepodobnosť,
Počítač bude potom pád program pretože to nie je
pamäť Aj by malo byť umožnené na dotyk.
Takže v skratke, je tento program chybná presne z tohto dôvodu.
Ja zásadne nerobím to, čo?
Aké kroky mám vynechané, rovnako ako sme sa vynechať Binkym prvý príklad?
Jo?
>> Divákov: alokácia pamäte?
>> DAVID Malan: alokácia pamäte.
Nemám v skutočnosti pridelené akýkoľvek pamäte pre tento reťazec.
Takže môžeme opraviť v niekoľkými spôsobmi.
Jeden z nich, môžeme aby to jednoduché a v skutočnosti, teraz si
začnú vidieť rozostrenie z liniek medzi tým, čo
Pole je, aký je reťazec, aká char hviezda je to, čo rad znakov
je.
Tu je druhý príklad zahŕňajúce reťazcov a oznámenia
všetko, čo som urobil na linke 16 je, namiesto toho hovoriť
že vyrovnávacia pamäť bude char hviezda, ukazovateľ na kus pamäti,
Budem veľmi aktívne dať sám seba ako buffer pre 16 znakov,
a v skutočnosti, ak ste oboznámení s termínom vyrovnávacej pamäte,
pravdepodobne zo sveta videí, kde je video do vyrovnávacej pamäte, ukladanie do vyrovnávacej pamäte,
ukladanie do vyrovnávacej pamäte.
No, čo je tu súvislosť?
No, Vnútri YouTube a vo vnútri video prehrávača
všeobecne je pole to je väčšia ako 16 rokov.
To by mohlo byť poľa veľkosti jednej megabajt, možno 10 megabajtov,
a do tohto poľa sa váš prehliadač stiahnuť veľa bytov,
celá partia megabajtov video, a video prehrávač,
YouTube je, alebo ten, kto to začína čítanie bajtov z tohto poľa,
a kedykoľvek vidíte Slovo buffering, ukladanie do vyrovnávacej pamäte,
to znamená, že má hráč dostali na koniec tohto poľa.
Sieť je tak pomalé, že to nemá naplnil pole s viacerými bytmi
a tak ste mimo bitov Pre zobrazenie pre užívateľa.
>> Takže vyrovnávacia pamäť je výstižný termín tu v tom, že je to len pole, kus pamäte.
A to bude opraviť preto, že sa ukazuje,
že môžete liečiť pole, ako keby sú adresy, aj keď pufer
je len symbol, je to postupnosť znakov, pufer,
To je užitočné pre mňa, programátor, môžete odovzdať svoje meno okolo
ako by sa jednalo o ukazovateľ, ako by to
boli adresa bloku pamäte pre 16 znakov.
Takže to má hovoriť, môžem prejsť scanf presne to slovo
a tak teraz, keď som robiť tento program, aby scanf 2, bodka lomka scanf 2,
a zadajte hello world, Enter, že time--
>> Hmm, čo sa stalo?
String prosím.
Čo som urobil zle?
Hello world, vyrovnávacej pamäti.
Hello world.
Ach, ja viem, čo to robí.
OK.
Takže to číta up až do prvého priestoru.
Takže poďme cheat na chvíľu a hovoria Chcel som písať niečo
naozaj dlhé, ako je to dlhá veta to je jedna, dva, tri, štyri, päť,
šesť, sedem, osem, deväť, 10, 11, 12, 13, 14, 15, 16.
OK.
Je to skutočne dlhá veta.
Takže táto veta dlhší ako 16 znakov
a tak keď som stlačte klávesu Enter, čo sa bude diať?
No, v tomto prípade z príbeh, som vyhlásil, vyrovnávacie
v skutočnosti, že pole s 16 znakmi pripravený ísť.
Takže jeden, dva, tri, štyri, päť, šesť, sedem, osem, deväť, 10, 11, 12, 13, 14,
15, 16.
Takže 16 postavy, a teraz, keď som čítať v niečom, ako je to dlhá
veta, čo sa bude diať so že budem čítať v tomto je dlhá
S-E-N-T-E-N-C-E, vety.
>> Tak toto je zámerne zlá vec, ktorú som
udržať písanie za hranice Hranice môjho poľa,
za hranice mojej pamäti.
Mohol by som mať šťastie a program bude mať na chod a nie jedno,
ale všeobecne povedané, toto bude skutočne dôjsť k zlyhaniu môjho programu,
a to je chyba v mojom kód v okamihu, keď vyjdem
za hranice tohto poľa, pretože ja
Neviem, či je to nutne spadne
alebo či som len tak mať šťastie.
Takže to je problematické, pretože v Tento prípad, nezdá sa, že práca
a poďme sa pokúšať osud tu, aj keď IDE Zdá sa, že tolerovať docela dost
of--
>> Tam sme ísť.
Konečne.
Takže ja som jediný, ktorý môže vidieť.
Tak som jednoducho musel veľa zábavné písanie out naozaj dlhú skutočné frázy
že to určite prekročila 16 bajtov, pretože ja
napísaný v tejto bláznivej dlhej multi-linka frázy, a Všimnite si, čo sa stalo.
Program to skúsil tlač a potom sa dostal chybu segmentácie
a segmentácia chyby je, keď niečomu takému dôjde,
a operačný systém hovorí, Nie, nemôže dotknúť, že pamäť.
Chystáme sa zabiť program úplne.
>> Takže to vyzerá problematické.
Ja som zlepšil programu, ktorý zaručuje mať aspoň časť pamäti,
ale bude to zdá sa, že obmedziť Funkcie GetString k získaniu
reťazca nejakého konečnej dĺžky 16.
Takže ak chcete podporiť dlhšie vety ako 16 znakov,
čo robíš?
No, môžete zvýšiť veľkosť vyrovnávacej pamäte do 32
alebo že sa zdá trochu krátka.
Prečo nie my len aby to 1000, ale tlačiť späť.
Aká je odpoveď intuitívne z Len vyhnúť sa tento problém tým, že
môj vyrovnávacej pamäte väčšie, rovnako ako 1000 znakov?
Realizáciou getString týmto spôsobom.
Čo je to tu dobré alebo zlé?
Jo?
Divákov: Ak zviazať až veľa priestoru a nechcete používať,
potom nemôžete prerozdeliť ten priestor.
DAVID Malan: Rozhodne.
Je to plytvanie, ak, ak nemáte skutočne potrebujú 900 týchto bytov
a napriek tomu žiadate 1000 celkom tak ako tak,
ste práve náročný na pamäť počítač užívateľa, ako je potrebné,
a po tom všetkom, niektoré ste sa už stretli
v živote, že keď ste beh veľa programov
a jedia až veľké množstvo pamäte, to môže skutočne ovplyvniť výkon
a skúsenosti užívateľa na počítači.
Tak to je trochu lenivý riešenie, pre istotu, a naopak,
to nie je len plytvanie, aký problém stále zostáva, aj keď som sa, aby môj vyrovnávacej pamäte
1000?
Jo?
>> Divákov: Reťazec je dĺžka 1001.
DAVID Malan: Presne tak.
Ak je váš reťazec je dĺžka 1001, máte presne rovnaký problém,
a mojím argumentom, urobil by som to Len potom 2.000 robiť,
ale neviete, v vopred, ako veľký by to malo byť,
a napriek tomu, musím zostaviť svoj program predtým, než povolí ľudia používajú a download
za to.
Tak toto je presne ten druh veci, ktoré sa knižnica snažia CS50
aby nám pomohli s a my len pohľad na niektoré z podkladovej vykonávania
tu, ale je to CS50 bodka C. Táto je súbor, ktorý je už na CS50 IDE
všetky tieto týždne, ktoré ste používali.
Je to pre-skompilovaný a vy ste bola automaticky používať to
podľa povahy majúce pomlčka L CS50 vlajku s zazvonením,
ale keď som sa posunúť dole cez všetky tieto funkcie, tu je getString,
a len na vás vzniku chuť, čo sa deje,
poďme sa rýchlo pozrieť na relatívnu zložitosť.
Nie je to super dlhé funkcie, ale my nie
musieť premýšľať o všetko tvrdo ako ísť o získanie reťazca.
>> Takže tu je moja vyrovnávacej pamäte a ja zrejme inicializovať ju na hodnotu null.
To, samozrejme, je to isté ako char hviezda,
ale ja som sa rozhodol v realizáciu knižnice CS50
že ak budeme úplne dynamický,
Neviem vopred, ako velkej Užívatelia reťazec budú chcieť dostať.
Takže ja idem začať len s prázdny reťazec
a budem vybudovať toľko pamäť as Potrebujem, aby sa zmestili užívateľa reťazec
a či nemám dosť, idem sa opýtať
operačný systém pre viac pamäte.
Chystám sa presúvať svoje reťazec do väčšieho kusu pamäti
a budem uvoľniť alebo oslobodiť nedostatočne veľký kus pamäte
a my len tak k tomu opakovane.
>> Tak rýchly pohľad, tu je len premenná
s ktorou budem sledovať kapacity mojej pufra.
Koľko bytov môžem fit?
Tu je premenná n s ktorý budem držať
Trať koľko bajtov sú vlastne v vyrovnávacej pamäti, alebo že užívateľ napísali.
Ak ste ešte nevideli to predtým, vás môžete určiť, že premenná ako int
je nepodpísaný, ktorý, ako názov napovedá, znamená, že je nezáporné, a prečo by
Čo som kedy chcel obťažovať špecifikujúca že int nie je len int,
ale je to unsigned int?
To je non-negatívne int.
Čo [nepočuteľné] znamená?
>> Divákov: Je to popisujúce čiastku pamäte, ktorá môže byť [nepočuteľných].
>> DAVID Malan: Jo.
Takže keď poviem unsigned, je to vlastne ktorá vám jeden bit navyše pamäti
a zdá sa, trochu hlúpe, ale ak budete majú jeden bit prídavnej pamäte, že
znamená, že máte dvakrát toľko Hodnoty môžete zastupujú,
pretože to môže byť 0 alebo 1.
Takže v predvolenom nastavení, int môže byť hrubo negatívne 2000000000 celú cestu
až do pozitívneho 2 miliardy.
Tí, ktorí sú veľkými rozsahy, ale je to stále trochu márnotratný
ak ste len o veľkosti, ktorá sa práve intuitívne
by mala byť non-negatívne alebo kladné alebo 0, no a potom,
prečo ste strácaš 2 miliardy Možné hodnoty pre záporných čísel
ak ste nikdy používať?
Takže tým, že hovorí nepodpísaný, teraz môj int môže byť medzi 0 a približne 4 miliardy.
>> Tak tu je len int C z dôvodov, nebudeme sa do práve teraz ako
prečo je to int miesto na char, ale tu je
podstata toho, čo sa deje o, a niektorí z vás
by mohli byť za použitia, napríklad, fgetc fungovať aj v pset štyri
alebo neskôr, budeme ho vidieť opäť v probléme set päť,
fgetc je pekné, pretože ako názov druh, druh arcanely napovedá,
je to funkcia, ktorá dostane charakter, a tak,
čo je zásadne odlišná o tom, čo robíme v getString
je, že nepoužívate scanf rovnakým spôsobom.
Sme len plazivej po krok-za-krokom cez čo užívateľ zadal,
pretože môžeme vždy prideliť jeden char, a preto môžeme vždy bezpečne
sa na jednej znak v čase, a kúzlo začne diať tu.
Chystám sa nalistujte prostredný tejto funkcie
Len stručne predstaviť túto funkciu.
Rovnako ako je tu Funkcia malloc, je tu
funkcia realloc kde realloc vám umožní prerozdeliť kus pamäti
a robiť to väčšie alebo menšie.
Tak dlhý príbeh krátky as vlna mojej ruky pre dnešok,
viem, že to, čo getString robí, je, že to niečo
z magicky rastúcej alebo zmršťovanie vyrovnávacej pamäti ako užívateľ
typy vo svojom reťazci.
>> Takže v prípade, že užívateľ zadá krátky reťazec, tento kód
Iba prideľuje dosť pamäť, aby sa zmestili reťazec.
Ak užívateľ stále písať ako som to urobil znova a znova
a znovu, no, v prípade, že vyrovnávacia pamäť je spočiatku tento veľký
a program realizuje, aby počkaj, ja som z vesmíru,
to bude dvojnásobok veľkosť vyrovnávacej pamäte
a potom zdvojnásobiť veľkosť vyrovnávacej pamäte a kód, ktorý robí zdvojnásobenie,
Ak sa pozrieme na to tu, je to práve tento šikovný jednoriadkový.
Je možné, že ste videli túto syntax predtým, ale keď poviete hviezda rovná,
To je to isté, ako hovorí časy objeme 2.
Tak to jednoducho stále zdvojnásobenie kapacita pufru
a potom hovoriť realloc dať sama o sebe, že oveľa viac pamäte.
>> A teraz, ako stranou, tam sú ďalšie funkcie v tu
že nebudeme pozerať do detailov iné ako ukázať v GetInt,
používame getString v GetInt.
Overíme, že to nie je null, čo, odvolanie,
je zvláštne hodnota, ktorá znamená, že sa niečo pokazilo.
Sme z pamäte.
Lepšie skontrolovať, že.
A my sme sa vrátiť hodnotu sentinelovej.
Ale budem odložiť na pripomienky pokiaľ ide o prečo a potom sme sa použiť tento bratranec scanf
volal sscanf a ukazuje sa, že sscanf, alebo reťazec scanf,
vám umožní sa pozrieť na riadku užívateľ zadal, a nechať vás
analyzovať je v podstate, a to, čo ja som tu je Hovorím sscanf,
analyzovať bez ohľadu má užívateľ zadali a uistite sa, že% i,
je celé číslo v nej, a my nie dostať sa do dneška presne dôvod, prečo tam je tiež
A% c tu, ale že v kocke umožňuje us zistiť, či má používateľ zadanej
v niečom falošné za číslom.
Takže dôvod, že GetInt a GetString tí k opakovanie, opakovanie, opakovanie
Je to preto, zo všetkých že kód písali sme,
Je to trochu pozerá na vstupe užívateľa V uistite sa, že je to úplne číselné
alebo je to skutočný floating Bodová hodnota alebo podobne,
V závislosti na tom, aký hodnote funkciu, ktorú používate.
>> Uff.
OK.
To bolo sústo ale bod je tu
že dôvod, prečo sme mali tieto školenia kolesá na
Je tomu tak preto na najnižšej úrovni, tam je len toľko vecí, ktoré
môže ísť zle, že sme chceli preventívne zvládnuť
tieto veci určite v najskoršie týždňov triedy,
ale teraz s pset štyri a päť a pset za uvidíte, že je to skôr k
vy, ale aj vy ste schopnejší riešiť tieto druhy problémov
sami.
Akékoľvek otázky týkajúce getString alebo GetInt?
Jo?
>> Divákov: Prečo by ste zdvojnásobí kapacita pufru
skôr než len rastúce to o presné sumy?
>> DAVID Malan: Dobrá otázka.
Prečo by sme zdvojnásobiť kapacitu pufra, na rozdiel
len ju zvýšiť nejakú konštantnú hodnotu?
Bolo rozhodnutie o dizajne.
Jednoducho sme sa rozhodli, že preto, že má tendenciu byť o niečo drahšie časovo sa opýtať
operačný systém pre pamäť, my nie
chcú nakoniec dostať do situácia pre veľké reťazce
že sme sa pýtali znovu a znovu OS
a znovu a znovu Rýchla obmena pre pamäť.
Tak sme sa jednoducho rozhodli, trochu ľubovoľne, ale dúfame, že rozumne,
že, viete čo, poďme pokúsiť sa dostať pred seba
a len držať zdvojnásobenie to tak, že sme sa minimalizovalo množstvo časov
musíme zavolať malloc alebo realloc, ale celkom rozsudok
volania v neprítomnosti vedieť čo používatelia chcieť písať.
Oba spôsoby môžu byť diskutabilná.
Pravdepodobne dobre.
>> Takže poďme sa pozrieť na pár iných vedľajších účinkov pamäti,
veci, ktoré sa môžu pokaziť a nástroje, ktoré vám môžu
používajú na zachytenie tieto druhy chýb.
Ukazuje sa, že vás všetkých, aj keď check50 nepovedal ti toľko,
Boli písanie buggy kód od jedného týždňa,
aj keby všetky check50 testy prešiel, a to aj v prípade, vy a vaše TF
sú super presvedčení, že váš kód funguje, ako bolo zamýšľané.
Váš kód bol kočík alebo chybná v tom, že všetci z vás,
v pomocou knižnice CS50, Boli netesní pamäte.
Boli ste žiada operačný systém pre pamäť vo väčšine programov
ste napísali, ale vy ste vlastne nikdy dal ju späť.
Vy ste volal GetString a GetInt a GetFloat,
ale s getString, nemáš nikdy volal unGetString alebo Daj
Reťazec Back alebo podobne, ale my sme videli že GetString robí alokovať pamäť
prostredníctvom malloc alebo to Funkcie realloc, čo je len
veľmi podobný v duchu, a napriek tomu sme boli
žiada operačný systém pre pamäť a pamäť znovu a znovu
ale nikdy dávať to späť.
>> A teraz, ako stranou, sa ukazuje, že keď je program ukončený, všetky pamäte
je automaticky uvoľnená.
Takže to nebol veľký problém.
Nebude to rozbiť IDE alebo spomaľujú,
Ale keď programy sa všeobecne úniku pamäti
a oni beží na dlhú dobu.
Ak ste niekedy videli stupídny nafukovacia lopta v Mac OS alebo presýpacie hodiny
v systéme Windows, kde je to trochu spomalenie alebo myslenie alebo myslenie
alebo len naozaj začína spomaliť na prechádzanie,
Je to veľmi pravdepodobne mohlo byť výsledkom pretekanie pamäte.
Programátori, ktorí písali softvér, ktorý používate
opýtajte operačný systém pre pamäť každých pár minút, každú hodinu.
Ale ak ste beží softvér, aj keď je to
minimalizovať vo vašom počítači hodiny alebo dni na konci,
môžete sa pýtať na viac a viac Pamäť a vlastne nikdy používať
a tak váš kód môže byť, alebo programy by mohli byť netesní pamäti,
a ak začnete úniku pamäti, tam je menej pamäte pre ostatné programy,
a výsledok je pre spomaliť všetko dole.
>> Teraz, to je zďaleka jedným z tých najdesivejších programy
budete mať možnosť spustiť v CS50, pokiaľ
lebo jeho výkon je ešte viac ako ezoterická rinčať je alebo urobiť, alebo niektorý z príkazu
linka programy Urobili sme skôr, ale našťastie, vložené do jeho výstupu
je niekoľko užitočných tipov, ktoré výborný budú užitočné buď pre pset štyri
alebo rozhodne pset päť.
Takže Valgrind je nástroj , Ktoré môžu byť použité na vyzerať
pre úniky pamäte v programe.
Je relatívne jednoduché pre spustenie.
Spustiť Valgrind a potom, dokonca aj keď je to trochu ukecaný,
pomlčka únik pomlčka kontrola rovná plné, a potom dot
lomítko a názov vášho programu.
Takže Valgrind potom pobeží program a na samom konci svojho programu
beh pred tým, než ukončí a vám dáva ďalšiu výzvu,
to bude analyzovať váš Program, zatiaľ čo to bola spustená
a tí si úniku akýkoľvek pamäte a ešte lepšie,
ste sa dotknete pamäť, ktorá nepatril k vám?
To nemôže chytiť všetko, ale je to celkom dobrý v chytaní väčšinu vecí.
>> Tak tu je príklad, ktorý má moje behu tento program, majú beh Valgrind,
na programe s názvom pamäť, a ja idem
upozorniť na riadky, ktoré sú nakoniec nás zaujímajú.
Takže tam je ešte viac rozptýlenie že som vymazané zo snímky.
Ale poďme sa jednoducho vidieť, čo to Program je schopný nám hovorí.
To je schopné rozprávať nám veci ako neplatné zápisu o veľkosti 4.
Inými slovami, ak sa dotknete pamäť, konkrétne 4 bajtov pamäte
že by ste nemali mať, Valgrind vám môže povedať, že.
Neplatný zápis veľkosti 4.
Dotkol si sa štyri byty že by ste nemali mať.
Kde si to urobil?
To je krása.
Pamäť dot c linka 21 je miesto, kde vás podelal, a to je dôvod, prečo je to užitočné.
Rovnako ako GDB, môže pomôcť bod, ktorý v aktuálnom chyby.
>> Teraz, to je trochu viac verbose, ak nie mätúce.
40 bytov v 1 blokoch sú rozhodne stratený v záznam straty 1 z 1.
Čo to znamená?
No, to jednoducho znamená, že ste požiadal o 40 bytov a nikdy ju vrátil.
Volal ste malloc alebo ste volal GetString a operačný systém
ti dal 40 bytov, ale tie nikdy oslobodený alebo povolený, že pamäť,
a byť spravodlivý, nikdy sme sa ukázať, , Ako sa vrátiť pamäť.
Ukázalo sa, že tam je super jednoduchá funkcia s názvom zadarmo.
Prijíma jeden argument, vec Ak chcete uvoľniť alebo vrátiť,
ale 40 bytov, zdá sa, v tomto programe
boli stratené na riadku 20 pamäte dot c.
>> Tak uvidíme, tento program.
Je to super k ničomu.
To len dokazuje, tento konkrétny chybe.
Takže poďme sa pozrieť.
Tu je hlavné a hlavné, vývesné, hovory funkcia nazvaná f, a potom sa vráti.
Takže nie je všetko tak zaujímavé.
Čo f robiť?
Všimnite si, som sa neobťažoval s prototypom.
Chcel som, aby kód čo najmenší.
Tak som dal f nad hlavnou a to je v poriadku, určite,
pre krátke programy, ako je tento.
Takže f nič nevracia a robí neberie nič, ale je to to urobiť.
To prehlasuje, podobne ako v príklade binky,
ukazovateľ s názvom x, čo sa deje uložiť adresu int.
Tak to je ľavá strana.
V angličtine, čo je pravá strana robí?
Každý, kto?
Čo je to robí pre nás?
Jo?
>> Divákov: [Nepočuteľné] meria veľkosť int
čo je 10-krát vyššia ako [nepočuteľných]
DAVID Malan: Dobrý, a dovoľte mi zhrnúť.
Takže prideliť dostatočný priestor pre 10 celé čísla alebo 10, čo je veľkosť int,
je to štyri bajtov, takže 10 krát 4 je 40, takže pravej strane, ktoré som
zvýraznený, je dať mi 40 bajtov a uložiť adresu prvého bajtu
do x.
A teraz konečne, a tu je miesto, kde tento program je buggy, čo je
s čiarou 21 zlé na základe tejto logiky?
Čo je na riadku 21 v neporiadku?
Jo?
Divákov: Nemôžete index do x [nepočuteľných].
DAVID Malan: Jo.
Nemala by som index do x, ako je to.
Takže syntakticky, to je v poriadku.
Čo je príjemné je, rovnako ako vy môže liečiť názov poľa
, Ako keď je to ukazovateľ, podobne môžete liečiť ukazovateľ, ako keď je to
poľa, a tak môžem syntakticky hovoria x držiak niečo, x držiak i,
ale 10 je problematické.
Prečo?
>> Divákov: Pretože to nie je vo vnútri.
>> DAVID Malan: To nie je Vnútri tohto kusu pamäti.
Aká je najväčšia hodnota by som mal byť uvedení v tých hranatých zátvorkách?
9, 0 až 9.
Vzhľadom k tomu, nulového indexovanie.
Takže od 0 do 9 bude v poriadku.
Držiak 10 nie je dobrá a ale spomínam aj keď, zakaždým
Pripadá mi, že sa snaží, aby sa CS50 IDE crash zadaním falošných hodnôt,
to nie je vždy spolupracovať, a naozaj, často
šťastie len preto, že Operačný systém nie je
Všimnite si, že ste niekedy tak trochu prejsť nejaký kus pamäti,
preto, že ste zostal v technicky Váš segmentu, ale o tom viac
v triede operačných systémov, a tak sa niečo také
by mohla veľmi ľahko uniknú pozornosti.
Váš program sa nikdy havárii dôsledne ale možno raz za čas.
>> A tak sa poďme skúsiť Valgrind na to, a tu je
kde budeme dostať ohromený na výstupe za okamih.
Tak, aby pretekanie pamäte valgrind šek sa rovná plnej bodka lomítko pamäte.
A tu je dôvod, prečo Sľubujem To by premôcť.
Tu je to, čo valgrind, tu je to, čo programátor, niektoré roky ago-
rozhodol, že by to bol dobrý nápad pre výstup vyzerať.
Takže poďme zmysel tohto.
A tak celú cestu na ľavej strane side bezdôvodne
je proces ID programu my stačí spustiť, jedinečný identifikátor
pre program sme práve utiekol.
Vypúšťa sme, že z posúvač, ale tam
je niekoľko užitočných informácií tu.
>> Poďme rolovať hore až na samý vrchol.
Tu je miesto, kde sme začali.
Takže to nie je tak moc výstup.
Tu je neplatné write veľkosti 4 na riadku 21.
No, čo bolo riadku 21?
Linka 21 bolo presne to a to dáva zmysel
že som v platne písanie 4 bajty, pretože som
sa snaží dať túto číslo, čo môže byť čokoľvek,
to len sa stane byť nula, ale snažím
aby ju na mieste že nepatrí ku mne.
Okrem toho, tu dole, 40 bytov v jednom bloky sú definitívne stratené v zázname 1.
To preto, že keď volám malloc tu, som vlastne nikdy uvoľniť pamäť.
>> Tak ako môžeme opraviť?
Nechaj ma ísť ďalej a byť trochu bezpečnejšie a robiť 9 tam a dovoľte mi, aby som tu zadarmo x.
Toto je nová funkcia pre dnešok.
Keby som teraz znovu spustiť, aby spomienka dot lomítko, poďme bežať valgrind na to znova,
maximalizovať okno a stlačte Enter.
Teraz, je to dobré.
Oni pochovať dobré správy vo všetkých tohto výstupu.
Všetky haldy bloky sú zadarmo.
Vrátime sa na to, čo haldy je, ale žiadna úniky sú možné.
Takže je to len ďalší nástrojom pre vaše sade náradia
s ktorými môžete začať teraz nájsť chyby, ako to.
>> Ale poďme sa pozrieť, čo viac sa môže pokaziť tu.
Poďme prechod teraz v skutočnosti riešenie problému.
Ako stranou, ak to bude uľahčiť Trochu zmätku alebo napätia,
toto je teraz smiešny.
Jo.
To je celkom dobrý.
Vzhľadom k tomu, ukazovatele sú adresy a adresy
sú všeobecne konvencií písaný s šestnástkovej.
Ha, ha, to je teraz smiešne.
Tak či onak, takže poďme teraz v skutočnosti vyriešiť problém.
To bol výborný, extra low-level tak ďaleko,
a my môžeme vlastne robiť užitočné veci s týmito detaily low-level.
>> Preto sme zaviedli niekoľko týždňov Pred pojem pole.
Pole bolo fajn, pretože je ťažké upratať náš kód
pretože ak by sme chceli napísať program s niekoľkými študentmi
alebo viac názvov a domy a dorms a vysoké školy a všetko,
sme mohli uložiť všetko viac čisto vnútri poľa.
Ale navrhnúť jednu tienistú stránku z poľa tak ďaleko.
Aj keď ste neutrpelo sami v programe, jednoducho inštinktívne,
čo je to zlá vec o maticu, snáď?
Počul som nejaké mumlanie.
Divákov: Je to ťažké zmeniť veľkosť.
DAVID Malan: Je to ťažké zmeniť veľkosť.
Nemožno zmeniť veľkosť z poľa, v skutočnosti, samo o sebe
v C. môžete prideliť ďalšie pole, presunúť všetko od starého
do nového, a teraz mať nejaký priestor navyše,
ale nie je to asi tak, ako jazyk ako Java alebo Python
alebo ľubovoľný počet iné jazyky, s ktorými niektorí z vás
môže byť oboznámení kde na vás stačí držať pridanie veci
omrzenia na koniec poľa.
Keď máte rad veľkosť 6, to je jeho veľkosť,
a tak rovnako ako myšlienka skôr ktorý má vyrovnávaciu pamäť určitej veľkosti,
musíte uhádnuť z brány Akú veľkosť chceš, aby to bolo?
Ak máte hádať príliš veľký, strácate priestor.
Ak máte hádať príliš malá, vás nemôže uložiť, že dáta, prinajmenšom
bez oveľa viac práce.
>> Takže dnes, vďaka ukazovatele, môžeme začiatok šitia dohromady vlastné vlastné
dátové štruktúry, a fakt, tu je niečo,
že vyzerá trochu viac mystické na prvý pohľad,
ale to je to, čo budeme nazývať pripojený Zoznam a jeho meno druh zhŕňa
za to.
Je to zoznam čísel, alebo tento prípad, zoznam čísel,
ale môže to byť zoznam čohokoľvek, ale to je prepojené prostredníctvom šípok,
a len sa hádať s tým, čo technika
budeme môcť šiť dohromady,
niečo ako popcorn so závitom, prepojené zoznamy obdĺžniky tu?
Jej čísla?
Čo je základný jazyk funkcie?
>> Divákov: Ukazovateľ.
>> DAVID Malan: Ukazovateľ.
Takže každý z týchto šípok tu reprezentuje ukazovateľ alebo len adresa.
Takže inými slovami, keď budem chcieť pre uloženie zoznam čísel,
Nemôžem len ukladať, ak chcem, schopnosť rásť a zmenšiť
môj štruktúra dát v poli.
Tak som potrebné mať trochu viac prepracovanosť,
nevšimnúť, že tento obrázok druh naznačuje,
že ak ste práve dostali malé závity spojovacie všetko dohromady,
asi nie je tak ťažké, aby sa priestor medzi dve z týchto obdĺžnikov
alebo dva z týchto uzlov, ako začneme volať, vložte novú uzla,
a potom s nejakým novým závitom, len priekopa tri uzly dohromady,
prvý, posledný, a ten, že ste práve vložená do stredu.
>> A vskutku spájať zoznam, Na rozdiel od poľa, je dynamický.
To môže rásť, a to môže zmenšovať a vy nie
musí poznať alebo starostlivosť vopred, ako veľa dát budete sa skladovania,
ale ukázalo sa, musíme byť trochu Dbajte na to, ako to urobiť.
Takže najprv uvažujme, ako implementovať jeden z týchto malých obdĺžnikov.
Je to jednoduché implementovať int.
Stačí povedať int N, a získate 4 bajty pre int,
ale ako to mám dostať int, hovoria n, a potom ukazovateľ, nazvime to nabudúce.
Mohli by sme zavolať títo veci, čokoľvek chceme,
ale potrebujem štruktúru vlastné dáta.
Jo?
>> Divákov: Ampersand [Nepočuteľné].
>> DAVID Malan: Takže ampersand budeme používať na získať adresu uzla potenciálne.
Ale my potrebujeme ďalšie rysom C za účelom
mi dať schopnosť vytvárať Tento zvyk obdĺžnik, tento zvyk
Premenná ak chcete, v pamäti.
Divákov: struct.
DAVID Malan: struct.
Pripomeňme, od minulého týždňa, sme zaviedli struct, tento pomerne jednoduchý kľúčové slovo
že nám umožňuje robiť veci, ako je tento.
C neprišiel s dátami štruktúru zvanú študent.
Dodáva sa s int a plavákom a char a taký, ale to neprichádza s študent,
ale môžeme vytvoriť typ študenta dát, štruktúra študent, s touto syntaxou
sem.
A budete vidieť znova a znova.
Takže sa nemusíte báť, memorovanie kľúčové slová,
ale kľúčové slovo, ktoré je dôležité je, len to, že sme si povedali, struct
a potom sme hovorili, že študenta a vnútri študenta bolo meno a dom
alebo koľaji alebo podobne.
>> A tak teraz, dnes poďme navrhnúť toto.
Pridal som pár slov, ale ak chcem na vykonanie tohto obdĺžnik, ktorý je
dostal obaja int a ukazovateľ, viete čo, ja som
chystá vyhlásiť struct názvom uzla.
Som tiež, vnútri nej, povieš že uzol, tento obdĺžnik, má int
a my budeme nazývať n a to má ďalší ukazovateľ.
A to je trochu ukecaný, ale ak si myslíte o tom,
šípky, ktoré boli v obraze pred chvíľou sú akého dátového typu?
Tam, kde každý z týchto šípok ukazuje aký typ dátové štruktúry?
Nie je to len preto, aby ukázal int per sa.
Je to ukazujúc na Celá vec obdĺžnikový
a že obdĺžnikový vec, sme si povedali, sa nazýva uzol.
A tak sme sa trochu musieť rekurzívne definovať to, ako
že uzol, povedzme, bude obsahovať int názvom n
a ukazovateľ s názvom ďalšie a druh dátové štruktúry, ku ktorému
že ukazovateľ bodov je zrejme Bude struct uzla.
>> Tak toto je protivne ukecaný a jednoducho byť pedantská,
dôvod, prečo nemôžeme Len hovorím, čo úprimne povedané
vyzerá oveľa čitateľnejší, Je to preto, pripomeňme, že C čítať
veci zhora nadol, zľava doprava.
Nie je to až dostaneme bodkočiarka že uzol kľúčové slovo skutočne existuje.
Takže ak chceme mať tento druh cyklické referencie vnútri dáta
štruktúra, musíme to urobiť, ak hovoríme struct uzol na vrchole, ktorý
nám dáva dlhší spôsob, ako opísať to vec, potom vnútri hovoríme struct uzol,
a potom na posledný riadok hovoríme, v poriadku, C, mimochodom,
stačí zavolať celú tá prekliata vec uzol a zastaviť
pomocou kľúčového slova struct úplne.
Takže je to len niečo ako syntaxe trik, ktorý nakoniec nám umožňuje vytvárať
niečo, čo vyzerá presne takto.
>> Takže ak budeme predpokladať, teraz môžeme vykonávať túto vec C,
Ako máme vlastne začať pojazdu to?
No, v skutočnosti, všetko, čo musíte urobiť, je opakovať zľava doprava a len
druh vložiť uzlov alebo odstrániť uzly alebo hľadať veci, všade tam, kde chceme,
ale k tomu, poďme do toho a robiť o niečo reálnejšie veci, pretože to
bola mimoriadne nízkej úrovni tak ďaleko.
By niekto doslova chcel byť prvý?
OK.
Poď hore.
Ako sa voláš?
>> DAVID: David.
DAVID Malan: David.
Rád som ťa spoznal.
Ja tiež.
Dobre.
A my potrebujeme číslo 9.
Nie tak dobrý ako predtým, možno.
OK, číslo 9.
Číslo 17, prosím.
Dovoľte mi, aby som sa vrátiť o kúsok ďalej.
Číslo 22, prosím, a Ako sa o ďalej späť
či môžem vidieť žiadne ruky sa všetko svetlo, alebo nie.
Niekto sa prihlásil práve tam.
Chcete prísť?
Vaše predlaktia sa násilne stúpa.
OK, 17.
22.
26 prichádza dole.
By niekto iný chcel forcefully-- Poď hore.
Skutočný dobrovoľník.
>> Takže veľmi rýchlo, ak je vy mohol zariadiť
sami rovnako ako uzly na obrazovke.
Ďakujem.
A budete mať 26.
Všetky správne a rýchle úvody.
Takže som Dávid a ste tiež?
DAVID: David.
DAVID Malan: A vy ste?
JAKE: Jake.
SUE: Sue.
ALEX: Alex.
RAPHAEL: Raphael.
TL: taylor.
DAVID Malan: Taylor.
Výborne.
Tak to sú naši dobrovoľníci pre dnes a pokračovať
a posunúť trochu to tak, a jednoducho ísť dopredu a držať
holding vaše čísla ako vy alebo váš Prvé známkou a ľavou rukou,
choďte do toho a jednoducho realizovať Tieto šípky, len
tak, aby vaša ľavá ruka je doslova ukazuje na čo by ste sa mali ukázať
u, a dať si tak, aby nejaké miesto môžeme vizuálne vidieť ruky vlastne
bodovania, a vy môžete len bod druh u krajina je v poriadku.
>> Takže tu máme prepojeného zoznamu jedného, dva, tri, štyri, päť uzly spočiatku,
a všimnite si, máme to zvláštne ukazovateľ na začiatku, kto je
key pretože musíme sledovať celej dĺžke zoznamu nejako.
Títo chlapci, a to aj napriek tomu, že ste opustili doprava, chrbtom k sebe v pamäti,
môžu v skutočnosti byť kdekoľvek V pamäti počítača.
Takže títo ľudia môžu byť stojaci kdekoľvek na pódiu
a to je v poriadku, tak dlho, ako oni sú v skutočnosti ukazuje na seba,
ale udržať veci čistý a jednoduchý, budeme
len kresliť je zľava doprava, ako , Ale mohlo by byť masívny medzery
medzi týmito uzlami.
>> A teraz, keď chcem naozaj vložiť niektoré nová hodnota, poďme do toho a to urobiť.
Máme príležitosť teraz zvoliť iný uzol.
Povedzme, poďme začať s mallocing 55.
Nevadilo by ich niekto malloc?
OK, poď hore.
Ako sa voláš?
RAINBOW: Dúha.
DAVID Malan: Dúha?
Dobre.
Malloc Dúha.
Poď hore.
Takže teraz sa musíme pýtať sami seba, algoritmickým kde môžeme dať 55.
Takže všetci vieme, samozrejme, kde zrejme
Patrí-li, že sa snažíme aby tento zoradená
a ak by bolo vy mať jednu krok späť, takže nemáme spadnúť
fázy, to by bolo skvelé.
Takže vlastne, Dúha, začať znovu tu so mnou,
preto, že sme ako počítač teraz môže vidieť iba jednu premennú naraz.
Takže ak sa jedná o prvý uzol.
Všimnite si, že to nie je uzol, je to len ukazovateľ,
a to je dôvod, prečo je potrebné venovať sa iba veľkosť ukazovatele, nie
jeden z týchto plných obdĺžnikov.
Takže ideme skontrolovať na seba iterácie je 55 menej ako 9?
Nie.
Je 55 menej ako 17?
Nie.
Menej ako 22?
Menej ako 26?
Menej ako 34?
A tak teraz, samozrejme Dúha patrí na záver.
Tak aby bolo jasno, a to, čo bolo vaše meno, Taylor?
>> TL: taylor.
DAVID Malan: Takže medzi Taylora Ľavá ruka a rainbow ruky tu,
ktorého rúk je potrebné poukázať na to, čo v Pre vloženie 55 do tohto zoznamu?
Čo musíme urobiť?
Jo?
>> Divákov: Taylor ruka potrebuje k bodu doľava.
>> DAVID Malan: Presne tak.
Takže vloženie uzla na koniec zoznamu
je veľmi jednoduché, pretože práve Taylor má na bod, namiesto na zem
alebo budeme nazývať null, null je niečo absencia
z ukazovateľa alebo špeciálne nulový ukazovateľ, že ste
ísť k bodu s vašou ľavici ruka Rainbow a potom Rainbow,
kde by mala byť vaša doľava ruka pravdepodobne bod?
Down.
Nie je to dobré, keď jej ruka je trochu ukazovanie tu, alebo tak nejako akékoľvek off
akým spôsobom.
Ktoré by bolo považované hodnota odpadky,
ale keď poukazuje na Niektoré známe hodnoty, budeme
nazývajú nula alebo null, to je v poriadku pretože máme termín v tom
a vieme, že zoznam je teraz kompletná.
>> Takže to, čo je ďalší pomerne jednoduchý prípad?
Mohli by sme malloc 5?
Poď hore.
Ako sa voláš?
TIFFANY: Tiffany.
DAVID Malan: Je mi to ľúto?
TIFFANY: Tiffany.
DAVID Malan: Tiffany.
Dobre.
Tiffany bola malloced s hodnotou 5.
Poď hore.
Toto je relatívne ľahké taky, ale uvažujme poradí operácií teraz.
Bolo to celkom jednoduché s Taylorom na konci.
Číslo 5 je samozrejme menšie ako 9, a tak máme Davida, máme Tiffany,
a aká bola vaše meno?
>> JAKE: Jake.
>> DAVID Malan: Jake.
Tiffany Jake, a David.
Čí ruka by mali byť aktualizované ako prvé?
Čo chceš robiť?
Je tu pár možné spôsoby, ale tam je tiež jeden alebo viac zlé cesty.
>> Divákov: Začnite s úplne vľavo.
>> DAVID Malan: Začnite úplne vľavo.
Kto je tu vľavo potom?
Divákov: Prvý.
>> DAVID Malan: OK.
Takže začať s prvým a kam vás Chcete aktualizovať Dávidovi ruky byť?
Divákov: Smerom k 5.
DAVID Malan: OK.
A tak Dávid, bod v päť alebo Tiffany tu a teraz?
>> Divákov: Tiffany poukazuje na 9?
DAVID Malan: Perfect, s výnimkou Binky je Hlava tak nejako spadol, že jo?
Vzhľadom k tomu, čo je zle tento obrázok doslova?
Divákov: Nič sa ukázal.
DAVID Malan: Nič nie je ukázal na Jakom teraz.
My sme doslova osirelý 9 a 17, a my sme doslova
unikli všetky tejto pamäti, pretože tým, Prvá aktualizácia Dávidovmu ruku, to je
poriadku, ak je to správne ukázal na Tiffany teraz,
ale ak nikto mal predvídavosť poukázať na Jakea,
potom sme stratili celistvosť tohto zoznamu.
Takže poďme vrátiť späť.
Takže to bola dobrá vec, zakopnúť ale poďme napraviť teraz.
Čo by sme mali urobiť ako prvé miesto?
Jo?
>> Divákov: Tiffany by mal ukázať na 9?
DAVID Malan: Nemôžem dostať, že blízko k vám.
Kto by mal ukázať na 9?
>> Divákov: Tiffany.
>> DAVID Malan: Dobre.
Takže Tiffany by Prvý bod na 9.
Takže Tiffany by mali prijať na rovnakú hodnotu
Dávidovi, ktorý sa zdá redundantné na chvíľu,
ale to je v poriadku, pretože hneď na druhý krok, môžeme aktualizovať Dávidovmu ruku
poukázať na Tiffany, a potom v prípade my tak nejako čisté veci hore
ako by toto je druh jar-ako, Teraz to je správne vloženie.
Tak vynikajúce.
Sme skoro tam, takže teraz máme.
Poďme vložte jeden finále hodnota ako hodnota 20.
Keby sme mohli malloc jednu záverečnú dobrovoľník?
Poď hore.
Tak toto je trochu zložitejšie.
Ale vážne, kód sme písanie, aj keď slovne,
je rovnako ako mať hromadu ze ak to podmienky, nie?
Mali sme podmienku kontrolovať, či patrí
na konci, možno na počiatku.
Potrebujeme nejaký druh slučky nájsť miesto uprostred.
Takže poďme to urobiť s Ako sa voláte?
>> ERIC: Eric.
>> DAVID Malan: Eric?
Eriku.
Rád som ťa spoznal.
Takže máme 20.
Menej ako päť?
Nie.
Menej ako deväť?
Nie.
Menej ako 17?
Nie.
OK.
On sem patrí, a Vaše mená sú opäť?
SUE: Sue.
DAVID Malan: Sue.
ALEX: Alex.
DAVID Malan: Sue, Alex, a?
ERIC: Eric.
DAVID Malan: Eric.
Potrebujete, aby ste mohli aktualizovať ako prvý, ktorých ruky?
>> Divákov: Eric.
OK.
Takže Eric to by mala ukazovať na to, kde?
Na 22.
Dobre.
A teraz, čo bude ďalej?
Sue potom môžu poukázať na Eric a teraz, ak ste chlapci len
urobiť nejaký priestor, čo je v poriadku vizuálne, teraz sme urobili vloženie.
Takže poďme teraz posúdenie otázky, ale ďakujem moc za naše dobrovoľníkmi.
Veľmi dobre.
Si môžete nechať tie, ak sa vám páči.
A máme krásny darček na rozlúčku, ak by ste každý rád, aby sa stres loptičku.
Dovoľte mi to prejsť nadol.
Takže to, čo je stánok s jedlom to?
To sa zdá byť úžasná ak máme teraz
predstavil alternatívu k Pole, ktoré nie je tak obmedzený
na maticu nejakého pevnú veľkosť.
Môžu dorásť dynamicky.
>> Ale podobne ako sme videli v týždňoch minulosť, sme sa nikdy dostať niečo zadarmo,
rovnako ako určite tam je trade-off tu.
Takže sa nahor prepojeného zoznam, je táto dynamika?
Táto schopnosť rásť a úprimne povedané, sme mohli urobiť delete
a tak by sme mohli zmenšovať podľa potreby.
Akú cenu platíme?
Dvakrát toľko priestoru, prvý zo všetkých.
Ak sa pozriete na obrázok, už nie som ukladanie zoznam celých čísel.
Som ukladanie zoznam celé čísla plus ukazovatele.
Takže som zdvojnásobenie množstvo priestoru.
Teraz, možno to nie je tak veľký problém 4 bajtov, 8 bajtov,
ale mohla by určite pridať up pre veľké súbory dát.
Čo je ďalšia nevýhoda?
Jo?
>> Divákov: Musíme prejsť im jeden po druhom.
DAVID Malan: Jo.
Musíme je prejsť jeden po druhom.
Vieš čo, sme sa vzdali tento super užitočná funkcia z hranatých zátvorkách
notácie, viac vhodne známy ako náhodný prístup,
kde si môžeme len skok na jednotlivé elementy
ale teraz, keď som ešte mal moja dobrovoľníci tu,
keby som chcel nájsť číslo 22, nemôžem len
skočiť na držiak niečo niečo.
Musím sa pozrieť cez zoznam, veľa ako lineárne našich vyhľadávacích príkladov,
nájsť číslo 22.
Takže sa zdá, že zaplatili cenu tam.
Ale môžeme napriek tomu vyriešiť ďalšie problémy.
>> V skutočnosti, dovoľte mi predstaviť len pár vizuálne.
Takže ak ste boli dole Mather jedálni v poslednej dobe,
budete pripomenúť, že ich stohy zásobníkov, ako je táto,
Požičali sme tieto od Annenberg pred triedy.
Takže tento stĺpec podložiek, aj keď, je vlastne reprezentatívny
dátové štruktúry počítačovej vedy.
K dispozícii je dátová štruktúra v informatike
známy ako zásobník, ktorý veľmi pekne požičiava seba presne to vizuálne.
Takže ak každý z týchto zásobníkov nie je zásobník, ale rovnako ako rad a ja som chcel,
uloženie telefónnych čísel, ja mohol dať tu jeden dole,
a ja som mohol dať ďalší tu, a pokračovať stohovanie čísla
nad sebou, a to, čo je potenciálne užitočné o tom
je to, že to, čo je implikácia tejto dátové štruktúry?
Ktoré číslo môžem vytiahnuť Prvý najvýhodnejšie?
Najviac v súčasnosti jeden dal tam.
>> Takže to je to, čo by sme nazvali v informatika dátová štruktúra LIFO.
Last in, first out.
A uvidíme onedlho, prečo to by mohlo byť užitočné, ale pre túto chvíľu,
zváž vlastnosť.
A je to trochu hlúpe, ak si myslíte, o tom, ako ju jedáleň robí.
Zakaždým, keď čisté podnosy a dal najčerstvejšie ty na vrchole,
Tie by mohli mať skôr čisté ale nakoniec veľmi špinavé a zaprášené
zásobník na samom dne Ak ste nikdy vlastne
dostať sa až na dno, ktoré stack, pretože ste práve
udržať uvedenie novej a Čisté tie, na vrchole toho.
Rovnaká vec sa môže stať v supermarkete príliš.
Ak máte vitrínu mlieka a zakaždým CVS
alebo ten, kto dostane viac mlieka, stačí strčiť mlieka
že už máte na zadnej strane a dáte nové vpredu,
budete mať niektoré docela škaredé mlieko na konci dátové štruktúry,
pretože je to vždy na dne alebo ekvivalentne to je vždy na zadnej strane.
>> Ale je tu iný spôsob, ako premýšľať o tom, čakajú, až dáta a napríklad tento.
Ak ste jeden z tých ľudí, kto má rád na line up mimo obchodoch Apple
keď nový výrobok pochádza out, budete pravdepodobne
bez použitia zásobníka dát štruktúra, pretože vás
by odcudziť všetci ostatní, kto je zoraďovať kúpiť nejakú novú hračku.
Skôr, budete pravdepodobne používať aký druh dátové štruktúry
alebo aký druh systému v reálnom svete?
Dúfajme, že je to čiara, alebo viac správne alebo viac Briti-like, front.
A ukázalo sa, front je tiež štruktúra dát v informatike,
ale front má veľmi iný majetok.
Nie je to LIFO.
Last in, first out.
Chráň Boh.
Je to miesto FIFO.
Prvý dovnútra, prvý von.
A to je dobrá vec na poctivosti "kvôli
iste, keď ste obloženie up Super skoro ráno.
Ak sa tam dostať ako prvý, chcú sa dostať von najprv rovnako.
>> A tak sa všetky z týchto údajov štruktúry, fronty a komíny
a zväzky iných, dopadá vás môžete myslieť na to ako len pole.
Toto je pole, možno pevnú veľkosť 4, ale to by
byť celkom pekné, keby sme mohli len hromadu podnosy takmer nekonečne vysoký keby sme
majú, že mnoho zásobníky alebo čísla.
Takže možno chceme použite prepojeného zoznamu tu,
ale trade-off sa bude potenciálne, že potrebujeme viac pamäte,
zaberie trochu viac času, ale my neobmedzujú výšku stohu,
podobne ako Mather v vitríne môže obmedziť veľkosť stohu,
a preto sa jedná o rozhodnutie návrhu alebo dostupné možnosti k nám nakoniec.
Takže s týmito údajmi štruktúry, sme začali
videnie nová horná hranica potenciálne na to, čo predtým bolo veľmi rýchle
a kde necháme off ešte dnes a kde
budeme dúfať, že sa dostať do je v stredu, budeme
začať hľadať na dátach štruktúra, ktorá nám umožňuje vyhľadávať
prostredníctvom dát v čase konečného znovu prihlásiť.
A my sme videli, že, spomínam, v týždni nula a jeden s binárne vyhľadávania alebo delenie
a dobyť.
Je to vracia, a ešte lepšie, svätý grál pre túto stredu
bude prísť s Dátová štruktúra, ktorá beží skutočne
alebo teoreticky konštantný čas, pričom
nezáleží na tom, koľko milióny či miliardy vecí
máme v dátovej štruktúre, to bude trvať nás konštantný čas, možno jeden krok
alebo dva kroky, alebo 10 krokov, ale konštantný počet krokov
prehľadávať tejto štruktúry dát.
To samozrejme bude svätý grál ale o tom v stredu.
Uvidíme sa potom.
>> [Prehrávanie hudby]