[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]