[Predvaja glasba] 

[VIDEO PREDVAJANJE] 

-On Laže. 

-O čem? 

Ne vem. 

Torej kaj vemo? 

-To Ob 9:15, Ray Santoya bil na bankomatu. Ja. Torej, vprašanje je, kaj je delal na 9:16? 

-Shooting 9. milimeter na nekaj. Mogoče je videl ostrostrelca. 

-ali Je delal z njim. 

-Wait. Pojdi nazaj ena. 

-Kaj vidiš? 

-Bring Svoj obraz navzgor celotnem zaslonu. 

-His Očala. 

-Ni Je odsev. 

-To Baseball ekipa Nuevitas. To je njihov logo. 

In on je govoril, da kdor je nosil to jakno. 

[END PREDVAJANJE] 

DAVID Malan: V redu. To je CS50 in to je malo bolj od [neslišno], s katero ste dabbling s problemom nastaviti štiri. Danes smo začeli gledati malo bolj Globoko pri teh stvareh, imenovanih kazalci, ki kljub temu, da je precej Skrivnosten temo, se izkaže, da se dogaja da je sredstvo, s katerim smo Lahko začnete graditi in montaža veliko bolj sofisticirane programe. Ampak mi je uspelo na zadnjo sredo s pomočjo neke claymation prvega. Torej to, odpoklic, je Binky in smo ga uporabili da pogled na program, ki ni res kaj zanimivega, je pa razkrivajo nekaj težav. Torej, da bi začeli danes, zakaj ne hodimo hitro skozi nekaj teh korakov, poskusite destilirati v smislu človekovega točno to, kar se dogaja tukaj in zakaj je to slabo, nato pa preide na in dejansko začeli graditi nekaj s to tehniko? Torej, to so bili prvi dve vrstici v tem programu in v smislu navadnega je, kaj se ti dve vrstici delaš? Nekdo, ki je razmeroma udobno s tem, kar je izjavil na zaslonu? Kaj so ti dve vrstici delaš? To pa še ni vse, da je drugačna od enega tedna, vendar pa je nekaj novega poseben simbol. Ja? Nazaj tam. 

OBČINSTVO: Razglasitev kazalce? DAVID Malan: Ponovi? OBČINSTVO: Razglasitev kazalce? DAVID Malan: Deklariranje kazalci in dajmo omejite malo več. OBČINSTVO: [neslišno] naslov x in nato y. DAVID Malan: In potem obravnavati. Torej, še posebej, kaj delamo se bomo o razglasitvi dveh spremenljivk. Te spremenljivke, čeprav se dogaja biti tipa int zvezdo, ki je natančneje pomeni gredo za shranjevanje naslov int, zaporedju, X in Y. Zdaj obstajajo kakršne koli vrednosti? Ali obstajajo kakršne koli dejanske naslove v teh dve spremenljivki v tem trenutku? No. To je samo tako imenovane smeti vrednosti. Če ne boste dejansko dodelite spremenljiva, kar je bilo v RAM prej se dogaja, da zapolni z ničlami in tisti, oba od teh spremenljivk. Ampak še ne vem, kaj so in da je bo ključnega pomena, zakaj Binky izgubil glavo prejšnji teden. 

Torej, to je bil claymation inkarnacija tega s katerim imate le dve spremenljivki, majhne krožne kosov gline, da lahko shranite spremenljivke, ampak kot je zaokrožila puščice kažejo, oni dejansko ne kaže kjerkoli poznano samo po sebi. Torej smo imeli to linijo, in to je nova prejšnji teden, malloc za spomin dodelitev, ki je samo fancy način povedal, operacijski sistem, Linux ali Mac OS ali Windows, hej, daj mi nekaj pomnilnika, in vse, kar imaš za povedati operacijski sistem je tisto, ko ga prosi za spomin. To se ne bo kaj skrbi boš naredil z njim, vendar si morate povedati delovati sistem, kar s pomočjo knjižnične funkcije malloc. Ja? 

OBČINSTVO: Koliko? DAVID Malan: Koliko? Koliko v bajtih, in tako je to, še enkrat, izmišljeno primer, je samo rekel, daj mi velikost notr. Zdaj, velikost notr je štiri bajte ali 32 bitov. Torej je to samo način rekel, hej, operacijski sistem, dajte mi štiri bajte pomnilnika da sem lahko uporabite na mojem razpolago, in še posebej, kaj počne malloc povratek v zvezi z na ta kos štirih bajtov? OBČINSTVO: Naslov? DAVID Malan: naslov. Naslov tega kos štirih bajtov. Točno tako. In tako, da je tisto, kar je shranjeno na koncu vx in da je, zakaj smo v resnici ne zanima me, kaj se je število, ki Naslov je, ali je to ox1 ali OX2 ali nekatere Grobni šestnajstiški naslov. Pravkar Skrbimo slikovno da je ta spremenljivka x je zdaj kar kaže na to kos pomnilnika. Torej puščica predstavlja kazalec, ali natančneje, pomnilnik naslov. Ampak še enkrat, mi običajno ne skrbi kaj ti dejanski naslovi. Zdaj, ta linija pravi kaj v smislu navadnega je? Star x dobi 42 podpičjem. Kaj to pomeni? Hočeš iti? Ne praskajte vratu. 

SKUPINA: Naslov X na 42. 

DAVID Malan: Naslov X na 42. Ne čisto. Tako blizu, vendar ne povsem, ker tam zvezda, ki je prefixing to x. Zato moramo poteg malo. Ja? 

OBČINSTVO: Vrednost, da je kazalec x se kaže, da je 42. DAVID Malan: OK. Vrednost, ki je kazalec x kaže, da, recimo, mora biti 42, ali povedano drugače, zvezdo x pravi, pojdite na kakršnikoli naslov je x, ali je to 1 Oxford Street ali 33 Oxford Street ali ox1 ali ox33, karkoli da številski naslov, zvezda x Dereferenciranje x. Torej, pojdite na ta naslov in nato pa številko 42 tam. Tako, da bi bila enakovreden način rekel, da je. Tako, da je vse v redu, potem pa mi bi predstavljajo sliko takole, ko smo dodali 42 na ta kos štirih bajti na desni strani, vendar ta vrstica je bilo, kje je šlo narobe in Binky glava izstrelil nogama na tej točki, zaradi slabe stvari se dogajajo, ko ste dereference smeti vrednot ali ste dereference neveljaven kazalci, in rečem neveljavna ker na tej točki v Zgodba, kaj je notri y? Kakšna je vrednost y, ki temelji na zadnjih nekaj korakih? Ja? Kaj je to? 

OBČINSTVO: An naslov. DAVID Malan: An naslov. To bi moral biti naslov ampak sem ga inicializiran? Torej še nimam. Torej, kaj je znano, da je tam? To je samo nekaj smeti vrednost. To je lahko katera koli naslov od nič do 2 milijardi, če imate dve nastopov RAM-a, ali nič do 4 milijarde, če ste dobil štiri gigabajte pomnilnika. To je nekaj smeti vrednost, ampak problem je, da operacijski sistem, če ni vam ga je dal da je kos pomnilnika posebej da skušaš iti, to je običajno dogaja, da povzroči kaj smo videli kot napake segmentacije. Torej v resnici, kdo od vas, ki imajo boril na težave pri uradnih ur ali v težavah, ki je bolj običajno s poskuša ugotoviti, segmentacijo krivda, ki na splošno pomeni, ste dotika segment pomnilnika, ki ga ne bi smelo biti. Ste dotika spomin, da operacijski sistem nima dovoli si na dotik, ali je tako, da greste predaleč v vašem polju ali že sedaj, ali to je zato, ker ste se dotaknili pomnilnika, ki je le nekaj smeti vrednost. 

Torej delaš zvezdicami x tu nekako nedefinirano vedenja. Nikoli ne bi smeli storiti, ker kvota so, program je le, da bo crash, ker praviš, pojdite na ta naslov in nimate pojma, kje da je naslov dejansko je. Tako operacijski sistem je verjetno bo crash svoj program kot rezultat in seveda, da je kaj pa se je zgodilo, da Binky. Torej v končni fazi, Binky določen ta problem s tem. Torej tega programa je bila sama napačna. Ampak, če ste nekako korak naprej in namesto da bi izvršitev te vrstice, y enaka x samo pomeni karkoli naslov je x, prav tako ga v y. 

In tako slikovno, ki smo jih to predstavlja z dvema puščicama od x in y je obrnjena na istem mestu. Torej pomensko, x je enak y, ker obe tistih shranjujete enako naslov, ergo kaže na 42, in zdaj, ko rečeš zvezdo y, pojdite na naslov v y, to je zanimiv stranski učinek. Torej naslov v y je ista stvar kot naslov v x. Torej, če ste rekli, pojdite na naslov na y in spremenite vrednost do 13, kdo drug prizadet? X, točka D, tako rekoč, sme biti prizadeta kot dobro. 

In res, kako Nick narisal to sliko v claymation je točno to. Čeprav sledimo kazalec y, smo se znašli na istem mestu, in tako, če smo bili za tiskanje od x ali pointee Y-ov, potem bi videli vrednost 13. Zdaj pa rečem pointee biti v skladu z videom. Programerji, da moj znanje, nikoli dejansko reci pointee, tisti, ki je koničasta na, toda zaradi doslednosti z video, zavedaš to je vse, kar je bilo mišljeno v tej situaciji. Tako da kakršna koli vprašanja o claymation ali kazalci ali malloc samo še? Ne? V redu. 

Torej brez nadaljnje ado, vzemimo si oglejte v kateri ima ta dejansko niso bili uporabljeni za nekaj časa. Torej smo imeli to knjižnico CS50 da je dobil vse te funkcije. Mi smo uporabili GetInt veliko, GetString, Verjetno GetLongLong prej V mojem PSet eno ali tako, ampak kaj se dejansko dogaja? No, kaj je na hitro pogledamo Pod pokrovom na programu, ki navdihuje zakaj Ponujamo vam CS50 dal knjižnica, in seveda, kot prejšnji teden, smo začeli pri tistih, kolesa usposabljanja off. Torej je to zdaj urejeno iz Obdukcija kaj bil je dogajalo znotraj knjižnici CS50, čeprav bomo zdaj začnejo premikati proč od nje za večino programov. 

Torej, to je program, imenovan scanf 0. To je super kratek. Treba ga je le te vrstice, vendar uvaja funkcijo imenovano scanf da smo dejansko videli v trenutek znotraj knjižnice CS50, čeprav v nekoliko drugačni obliki. Torej ta program na liniji 16 se razglasi spremenljivko x. Tako mi je dala štiri bajte za notr. To je bilo pove uporabniku, Število prosim, in potem To je zanimiva vrstica, ki dejansko povezuje skupaj prejšnji teden in to. Scanf, nato pa opazite, da traja format niz, podobno kot printf, % i pomeni int, potem pa traja Drugi argument, ki izgleda malo funky. To je ampersand x, in da se spomni, smo videli samo enkrat prejšnji teden. Kaj ampersand x predstavlja? Kaj ampersand storiti v C? Ja? 

OBČINSTVO: Naslov. DAVID Malan: Naslov. Torej je nasprotno upravljavca zvezdicami, ker je operater zvezda pravi, pojdite na Ta naslov je ampersand operator pravi, ugotovimo, naslov te spremenljivke, in zato je to ključnega pomena, saj Namen scanf v življenju je za skeniranje uporabnikov vhod s tipkovnice, glede na to, kar on ali ona vrste, nato pa preberite prispevek tega uporabnika v spremenljivko, vendar smo videli v zadnjih dveh tednih da je ta funkcija swap, da smo Poskušal truda za izvedbo Samo zdrobljen. Spomnimo se, da s funkcijo zamenjave, če smo samo izjavila A in B, kot ints, nismo uspešno zamenjali dve spremenljivki znotraj zamenjave ravno tako kot z mlekom in UL, ampak čim prej vrnil swap, kakšen je bil rezultat v zvezi z za x in y, izvirne vrednote? Nič. Ja. Nič se ni zgodilo, da je čas, ker zamenjave spremeni le svoje lokalne kopije, kar pomeni, vse ta čas, ko smo imel bili kratki v argumentih do funkcij, smo pravkar poteka kopije teh trditev. To lahko storite s tem karkoli želite z njimi, ampak oni bodo morali ne Vpliv na prvotne vrednosti. Torej je to problematično, če vas želite imeti funkcijo, kot scanf v življenju, katere namen je, da skeniranje uporabnikovo vnosna in nato izpolnite prazne, tako da rekoč, to pomeni, da dobimo spremenljivko, kot je X vrednost, ker če bi bil jaz samo prenese X scanf, Če menite, da je logiko zadnji teden, scanf lahko storite karkoli hoče s kopijo x, vendar ni mogel trajno spremeniti x, če damo scanf zemljevid zaklada, tako rekoč, kjer x označuje mesto, s katerim peljemo v naslovu X, ki scanf more iti tja in dejansko sprememba vrednost x. In tako v resnici, vse da ta program ne če naredim scanf 0, v mojem viru Imenik 5m, da scanf 0, dot poševnica scanf, število prosim 50, hvala za 50. 

Torej, to ni vse, da je zanimivo, ampak kaj se dejansko dogaja je, da je takoj, ko sem poklical scanf tukaj, vrednost x se trajno spremenile. Zdaj pa se zdi to lepo in dobro, v resnici pa Zdi se, kot ne bomo res potrebujejo knjižnica CS50 sploh več. Na primer, kaj je prost še enkrat tukaj. Naj ga znova odpreti za sekundo. Poskusimo številko prosim in namesto da bi rekel 50 kot prej, kaj je samo reči ne. OK, to je malo čudno. V REDU. In le nekaj neumnosti tukaj. Torej se ne zdi, da ročaj napačne situacije. Zato moramo minimalno začetek dodal nekaj napak preverjanje se prepričajte, da ima uporabnik vnesli v dejanskem številu kot 50 let, ker očitno tipkanje besed ne zazna kot problematična, morda pa bi bilo. 

Oglejmo si te različice zdaj, da je moj poskus reimplement GetString. Če ima scanf vse to funkcionalnost vgrajeno, Zato smo bili dabbling z njimi kolesa usposabljanja, kot GetString? No, tukaj je morda moja preprosta različica GetString pri čemer je pred tednom dni, morda sem rekel, dajte mi niz in call it buffer. Danes bom šele začetek rekoč char zvezdo, ki je odpoklic, to je samo sinonim. Videti je strašnejši vendar je točno isto stvar. Torej mi spremenljivo imenovano pufer da se dogaja, da shranite niz, povej uporabniško niz prosim, in nato, tako kot prej, poskusimo sposodim to lekcijo scanf % s tem čas, nato pa preide v pufru. Zdaj, ček hitro sanity. Zakaj nisem rekel ampersand buffer ta čas? Sklepamo iz prejšnjega primera. OBČINSTVO: Char zvezda je kazalec. DAVID Malan: Točno, ker je ta čas, char zvezda je že kazalec, naslov, po definiciji te zvezde, da so tam. In če scanf pričakuje, naslov, je dovolj samo, da prenese v pufru. Ne rabim povedati ampersand buffer. Za radovedne, lahko narediti kaj takega. To bi imelo drugačen pomen. To bi vam kazalec na kazalec, ki je pravzaprav veljaven stvar C, vendar Zdaj, kaj je naj bo enostavno in obdržati zgodbo dosledni. Jaz sem le, da bo prehod v hranilnike ter da je pravilna. Problem, čeprav je to. Naj gredo naprej in vodijo to Program po njegovi izdelavi. Naredite scanf 1. Prekleto, moj prevajalnik je lov mojo napako. Daj mi eno sekundo. Jek. Recimo scanf-1.C. V REDU. Tam gremo. Rabim ga. CS50 ID ima različne konfiguracijske nastavitve da vas ščiti proti sebi. Potreboval sem onemogočiti tiste, ki jih teče Jek ročno tokrat. Torej niz prosim. Grem, da gredo naprej in tip V mojem najljubšem Hello World. OK, null. To ni tisto, kar sem tipkal. Torej, to je znak kaj pa narobe. Naj gredo naprej in tip v zelo dolgo vrvico. Hvala za nično, in ne vem, če bom lahko to sesuje. Poskusimo malo kopijo paste in videli, če to pomaga. Samo prilepite veliko tega. To je definitivno večji niz kot običajno. Naj samo res pisati. No. Prekleto. Ukaz ni bilo mogoče najti. Tako da je nepovezana. To je zato, ker sem prilepili nekaj slabih znakov, vendar se to izkaže se, ne bo šlo. 

Poskusimo še enkrat, ker to je bolj zabavno, če bomo dejansko sesuje. Naj ta tip in zdaj sem bo kopirati res dolg niz zdaj pa da vidimo, če bomo lahko crash to stvar. Opazili sem izpuščena prostore in Nove linije in podpičja in vse funky znakov. Enter. In sedaj omrežje je le da počasi. Držal sem dol Command-V predolgo, je jasno. Prekleto! Ukaz ni bilo mogoče najti. 

V REDU. No, dejstvo je, kljub temu naslednje. Torej, kaj se dejansko dogaja o tej izjavi od char zvezdicami odbojnikom na liniji 16? Torej, kaj sem že ko sem razglasi kazalec? Vse sem že je štiri byte vrednost imenuje buffer, ampak tisto, kar je znotraj njega v tem trenutku? To je samo nekaj smeti vrednost. Ker boste kadarkoli razglasi spremenljivko v C, to je samo nekaj smeti vrednost, in smo začeli spotakniti to realnost. Zdaj, ko sem povedal, scanf, pojdite na ta naslov in jih ne glede na vrste uporabnikov v. Če uporabnik vnese v zdravo world, dobro, kje sem ga dal? Pufer smeti vrednost. 

Torej, to je nekako kot puščica ki je obrnjena kdo ve kam. Morda je to obrnjena prav tukaj, v mojem spominu. In tako, ko uporabnik vrste v Hello World, Program poskuša dal Niz Zdravo svet poševnica nazaj 0 s tem, da kos pomnilnika. Vendar z veliko verjetnostjo, vendar očitno ni 100% verjetnost, računalnik se bo potem crash program, saj to ni spomin I je treba dovoliti, da se dotaknete. Torej, na kratko, je ta program napačna natanko tega razloga. Jaz sem v bistvu ne delaš, kaj? Kakšne korake sem izpuščena, prav tako kot Izpustili smo s prvim primerom Binky je? Ja? 

OBČINSTVO: dodelitev pomnilnika? 

DAVID Malan: dodelitev pomnilnika. Imam dejansko ni dodeljena katerikoli pomnilnik za ta niz. Tako bomo lahko to popraviti v nekaj načinov. Ena, lahko ga bo enostavno in v resnici, zdaj si bodo začeli videti zameglitev prog med kaj matrika je, kaj je niz je, kaj char zvezda je, kakšna niz znakov je. Tukaj je drugi primer vključuje godala in obvestila Vse sem naredil na spletu 16 je, namesto da bi rekoč da buffer se bo char zvezda, kazalec na kos pomnilnika, Bom zelo proaktivno dati Sam pufer za 16 znakov, in v resnici, če ste seznanjeni z izrazom pufrskih, Verjetno iz sveta video posnetkov, kjer je video zapufranje, pufersko, pufrno. No, kaj je povezava tukaj? No, Inside YouTubu in notranjost video predvajalniki običajno je matrika ki je večji od 16. Morda bi bilo array velikosti enega megabajt, morda 10 megabajtov, in v tem polju ne brskalnik prenesete cel kup bajtov, cel kup MB video in video predvajalnik, YouTube je ali kdo je, se začne branje bajte iz tega niza, in kadarkoli vidite Beseda zapufranje, pufersko, to pomeni, da ima igralec prišel do konca tega niza. Omrežje je tako počasi, da ima ne napolniti array z več bajti in tako ste iz bitov Za prikaz uporabniku. 

Torej pufer apt izraz tukaj s tem, da to je samo niz, kos pomnilnika. In bo to popraviti ker se je izkazalo, da lahko zdravljenje nizi, kot da so naslovi, čeprav pufer je samo simbol, to je zaporedje znakov, pufer, To je koristno za mene, programer, lahko prenese svoje ime po kot da bi bila kazalec, kot da bi to so naslov kos pomnilnika za 16 znakov. Torej, to se pravi, ne morem mimo scanf točno ta beseda in zdaj, če bi ta program, da scanf 2, pika slash scanf 2, in tip v zdravo svet, Enter, da time-- 

Hmm, kaj se je zgodilo? String prosim. Kaj sem naredila narobe? Zdravo svet, buffer. Pozdravljen, svet. Ah, vem, kaj počne. V REDU. Torej, to je branju do prvega prostora. Torej, kaj je goljufija za trenutek in reči sem hotel, da tip nekaj res dolgo, kot je to že dolgo stavek To je ena, dva, tri, štiri, pet, šest, sedem, osem, devet, 10, 11, 12, 13, 14, 15, 16. V REDU. To je res dolg stavek. Torej, ta stavek je daljše od 16 znakov in tako, ko sem pritisnite tipko Enter, kaj se bo zgodilo? No, v tem primeru zgodba, sem izjavil buffer dejansko pa niz z 16 znakov pripravljena iti. Torej ena, dva, tri, štiri, pet, šest, sedem, osem, devet, 10, 11, 12, 13, 14, 15, 16. Torej 16 znakov, in zdaj, ko sem berejo v nekaj, kot je to že dolgo stavek, kaj se bo zgodilo, je da bom prebral v to je dolgo S-E-N-t-E-N = C-E, stavka. 

Torej, to je namerno slaba stvar, ki sem voditi pisno onkraj Meje mojega array, presega meje mojega pufra. Lahko bi dobil srečen in program bo še naprej teče in ne skrbi, vendar na splošno, to bo dejansko crash svoj program, in to je napaka v mojem kodo trenutek stopim prek meja tega polja, saj sem Ne vem, če je to nujno bo crash ali če sem šele tekoč, da bi dobili srečo. Torej je to problematično, ker v V tem primeru, se zdi, da se delo in kaj je napeljala usodo tukaj, čeprav IDE zdi tolerirati zelo malo of-- 

Tam gremo. Končno. Tako da sem edini, ki lahko to videli. Tako da sem imel veliko zabave tipkanje ven res dolgo dejanskega frazo da zagotovo presežena 16 bajtov, ker sem vnesli v to noro dolge multi-line stavek, nato pa opazil, kaj se je zgodilo. Program potrudil tiskanje in nato dobil napako segmentacije in segmentacijo napake je, ko kaj takega zgodi in operacijski sistem pravi, ne, ne more dotakniti, da je spomin. Bomo ubili program v celoti. 

Torej, to se zdi problematično. Sem izboljšala programov, pri katerih vsaj nekaj spomina, to, ampak se zdi, da bodo omejili funkcija GetString za pridobivanje nizi neke končne dolžine 16. Torej, če želite, da podpirajo več kazni od 16 znakov, kaj počneš? No, lahko poveča Velikost tega blažilca do 32 ali da se zdi nekako kratek. Zakaj ne samo da je 1000, vendar potisnite nazaj. Kakšen je odziv intuitivno od Samo ne pride do tega problema, tako da moj buffer večji kot 1.000 znakov? Z izvajanjem GetString ta način. Kaj je dobro ali slabo tukaj? Ja? OBČINSTVO: Če se veže na veliko prostora in ga ne uporabljajte, potem ne more prerazporediti ta prostor. DAVID Malan: Absolutno. To je potratno, kolikor če ne dejansko potrebujejo 900 teh bajtov in vendar ste prosi za 1000 skupaj nekako, ste pravkar porabijo več pomnilnika na uporabnikov računalnik, kot ga potrebujete, in navsezadnje nekatere ste že naleteli v življenju, ko ste teče veliko programov in oni jedo veliko spomina, To lahko dejansko vpliva na delovanje in uporabnikova izkušnja na računalniku. Torej, to je nekako leni rešitev, za prepričani, in obratno, to ni samo potratna, kar problem še vedno, tudi, če naredim svoj buffer 1000? Ja? 

OBČINSTVO: Niz je dolžina 1001. DAVID Malan: Točno tako. Če je vaš niz je dolžina 1001, imaš točno isti problem, in moj argument, jaz bi samo potem bi bilo 2000, vendar ne veste, v napredovanje, kako velika bi morala biti, in še, moram sestaviti svoj program pred najemnin ljudje uporabljajo in prenos ga. Torej, to je točno vrsta stvari, ki so knjižnice poskuša CS50 da nam pomagate s in bomo samo pogled na nekatere od osnovnega izvajanja tukaj, ampak to je CS50 pika C. To je datoteka, ki je bil na CS50 IDE vse te tedne, da ste bili z uporabo. To je predhodno pripravijo in ste been using samodejno po naravi ki ima dash L CS50 zastavo z Jek, ampak če sem se pomaknite navzdol skozi vse te funkcije, tukaj je GetString, in samo, da vam okus, kaj se dogaja, Vzemimo hiter pogled na relativna kompleksnost. To ni zelo dolgo funkcija, vendar nismo morali razmišljati vsi težko o kako iti okoli dobili strune. 

Torej, tukaj je moj buffer in jaz očitno inicializacijo NULL. To seveda je ista stvar kot char zvezda, vendar sem se odločil v izvajanje knjižnico CS50 da če bomo popolnoma dinamično, Ne vem v naprej, kako velik od Uporabniki niz bodo želeli priti. Tako da bom za začetek s samo prazen niz in bom zgraditi toliko spomin kot moram, da se prilega uporabniško niz in če nimam dovolj, bom vprašal operacijski sistem za več pomnilnika. Grem, da se premaknete svoj niz v večji kos pomnilnika in jaz grem v javnost ali osvoboditi dovolj velik kos pomnilnika in smo le, da bo za to iterativno. 

Torej, hiter pogled, tukaj je samo spremenljivka s katero bom slediti zmogljivosti mojega pufra. Koliko bajtov lahko fit? Tukaj je spremenljivka n z ki grem naprej tir, koliko bajtov so dejansko varovalni ali da je uporabnik natipkan. Če ste ni videla tega, vas lahko določite, da se spremenljivka kot int je nepodpisan, ki je kot že ime pove, pomeni, da je non-negativno, in zakaj bi Sem kdaj želeli, da sitnost, ki določajo, da je int ni le int, ampak to je nepodpisani int? To je nenegativno int. Kaj [neslišno] pomeni? 

OBČINSTVO: To je opisovanje znesek pomnilnika, ki se lahko [neslišno]. 

DAVID Malan: Ja. Torej, če rečem, nepodpisana, je to dejansko vam eno malo dodatnega pomnilnika in zdi nekako neumno, ampak, če vas en bit dodatnim pomnilnikom, ki pomeni, da imate dvakrat več vrednosti, ki jih lahko predstavljajo, ker je lahko 0 ali 1. Torej privzeto, lahko int lahko v grobem negativna 2 milijardi vse tja do pozitivnega 2 milijardi. Tisti, ki so veliki razponi, vendar je še vedno nekako potratna Če vas skrbi le okoli velikosti, ki je samo intuitivno mora biti non-negativna ali pozitivna ali 0, tudi potem, zakaj ste zapravljaš 2 milijardi Možne vrednosti za negativne številke če ste nikoli ne bo za njihovo uporabo? Torej z besedami nepodpisan, zdaj moj int lahko biti med 0 in približno 4 milijarde. 

Torej, tukaj je samo int C razlogov ne bomo dobili v pravkar kot zakaj je to int namesto iz char, ampak tukaj je bistvo tega, kar se dogaja na, in nekateri od vas lahko uporabi, na primer, fgetc funkcija tudi v PSet štirih ali pozneje, bomo videli spet problem nastaviti pet, fgetc je lepo, ker kot ime vrste, nekako arcanely predlaga, je funkcija, ki dobi značaj in tako, kaj je bistveno drugačen o tem, kaj delamo v GetString se ne bomo s pomočjo scanf na enak način. Mi smo šele plazi po korak-po-korak več kot karkoli je uporabnik vtipka, ker smo lahko vedno dodeli enega char, tako da bomo lahko vedno varno poglej en char naenkrat, in magija začne dogajati tukaj. Grem, da se pomaknete navzdol Sredi te funkcije Samo na kratko predstavim to funkcijo. Podobno kot se je Funkcija malloc, tam je funkcija realloc kjer realloc upamo si prerazporedi kos pomnilnika in da je večja ali manjša. Torej skrajšam zgodbo in s val moje strani za danes, vem, da to, kar GetString počne je, da je nekako od čudežno raste ali krči pufra kot uporabnik vrste v svojem nizu. 

Torej, če uporabnik vnese kratek niz, ta koda le namenja dovolj spomin, da se prilega niz. Če uporabnik drži tipkanje kot sem ga znova in znova storil in spet, tudi, če je buffer je sprva to velik in program se zaveda, da Počakajte trenutek, da sem ven iz prostora, to se dogaja, da se podvoji velikost pufra in nato podvoji medpomnilnik in koda, ki ne podvojitev, če gledamo na to tu, to je samo to pameten one-liner. Niste morda videli to sintakso pred tem, ampak če rečeš zvezda enaka, to je isto, kot rekoč krat zmogljivosti 2. Torej je samo ohranja podvojitev kapaciteta pufra nato pa povedal realloc dati sam, da je veliko več pomnilnika. 

Zdaj, kot prahi, obstaja so druge funkcije v tukaj da ne bo videti v vsakem podrobnosti razen pokazati v GetInt, bomo uporabili GetString v GetInt. Preverite smo, da to ni null, ki, odpoklic, je posebna vrednost, ki pomeni nekaj, kar je šlo narobe. Mi smo iz spomina. Boljše preverite to. In bomo vrnili kontrolna vrednost. Ampak bom odloži do pripomb, kot da zakaj in potem bomo uporabili ta bratranec scanf imenuje sscanf in se izkaže, da sscanf ali niz scanf, upamo ste vzeli pogled na linijo, ki je uporabnik vtipka in pustil analizirati bistveno in kaj sem delaš tukaj se bom povedal sscanf, analizirali glede ima uporabnik vnesli v in se prepričajte% I, obstaja celo v njej, in ne bomo priti v danes točno, zakaj tam je tudi A% c tu, ampak da na kratko omogoča nam odkriti, če je uporabnik natipkan v nekaj lažnega po številu. Torej razlog, da GetInt in GetString vam povem, da poskusite znova, poskusite znova, poskusite znova je zaradi vse da koda smo pisno, To je nekako videti na vhodu uporabnika pri zagotavljanju, da je v celoti številsko ali je dejansko v plavajoči Vrednost točke ali podobno, odvisno od tega, kakšno vrednost delovanje, ki ga uporabljate. 

Uh. V REDU. To je bila zalogaja vendar je poanta tu da je razlog, da smo imeli ti kolesa usposabljanja o je zato, ker na najnižji ravni, Obstaja samo toliko stvari, da more iti narobe, da smo želeli da preemptively ročaj tiste stvari, zagotovo pa Prvi tedni razreda, zdaj pa z PSet štirimi in PSet pet in onstran boste videli, da je več k vi pa tudi, da ste bolj sposobni za reševanje te vrste problemov sami. Vsa vprašanja v zvezi GetString ali GetInt? Ja? 

OBČINSTVO: Zakaj bi podvojili kapaciteta pufra ne samo povečuje pa ga je točen znesek? 

DAVID Malan: Dobro vprašanje. Zakaj bi podvojili zmogljivosti pufra v nasprotju da samo povečanje z neko konstantno vrednost? To je bila odločitev, design. Pravkar smo se odločili, ker se nagiba k malo dražje čas pametno vprašati operacijski sistem za spomin, nismo želite končati dobili v situacija za velike godala da smo spraševali znova in znova OS in znova in znova v hitro menjavanje za spomin. Torej smo pravkar odločila, da nekoliko samovoljno, vendar upamo, da upravičeno, da, veš kaj, dajmo poskusite dobiti pred sebe in kar naprej jo podvojili, tako da zmanjšujemo količino časa moramo poklicati malloc ali realloc, vendar skupno sodba klic v odsotnosti vedoč kaj bi uporabniki želeli vnesti. Oba načina bi lahko bilo sporno. Verjetno dobro. 

Torej, kaj si oglejte na nekaj drugih neželenih učinkov spomina, stvari, ki lahko gredo narobe in orodja, ki jih lahko uporabljajo za lov na te vrste napak. Izkazalo se je, vse vas, čeprav check50 vam ni povedal toliko, so bili pisno buggy koda od enega tedna, čeprav so vsi testi check50 so opravil, in tudi če vi in ​​vaš TF so super prepričani, da koda deluje, kot je bilo predvideno. Vaša koda je buggy ali pomanjkljiv, da vsi vi, pri uporabi knjižnice CS50, so pušča spomin. Ste bili sprašuje operacijski sistem za spomin v večini programov ki ste jih napisal, ampak ste nikoli dejansko dal nazaj. Ste jih imenuje GetString in GetInt in GetFloat, vendar z GetString, ste nikoli poklical unGetString ali Dajte String Back ali podobno, vendar smo videli da GetString ne dodeliti pomnilnika s pomočjo knjižnične funkcije malloc ali to Funkcija realloc, ki je pravkar zelo podobni v duhu, in še, smo bili prosi operacijski sistem spomin in spomin znova ampak nikoli ne daje nazaj. 

Zdaj, kot prahi, se izkaže, da ko program zapre, vse pomnilniku se samodejno sprostil. Torej to ni bil velik posel. To se ne bo prekinil IDE ali počasi stvari navzdol, ampak ko programi storiti običajno pušča spomin in oni so tekmovanje v teku za dolgo časa. Če ste kdaj videli neumnega Little Žoga za plažo v Mac OS ali peščene ure na operacijskem sistemu Windows, kjer je vrsta upočasni ali razmišljate ali razmišljanje ali pa samo res začne upočasnila na lezenje, to bi bilo zelo verjetno bo rezultat spomin razpoka. Programerji, ki je napisal programska oprema, ki jo uporabljate vprašajte operacijski sistem za spomin vsakih nekaj minut, vsako uro. Ampak, če ste tekmovanje v teku programske opreme, tudi če je zmanjšati na vašem računalniku za več ur ali dni, na koncu, vas bo morda prosil za več in več spomin in nikoli dejansko uporabo in tako lahko vaš koda, ali Programi lahko pušča spomin, in če začneš puščati spomin, tam je manj pomnilnika za druge programe, in učinek je počasi vse navzdol. 

Zdaj, to je daleč ena najbolj krute programi boste imeli priložnosti teči v CS50 kolikor saj njena proizvodnja je še bolj ezoteričnih kot Jek je ali bi ali katero koli ukaza Programi linije smo teči prej, vendar na srečo, vgrajeni v svojem izhodu je nekaj super koristnih nasvetov, ki bo koristno niti za PSet štiri ali gotovo PSet pet. Torej valgrind je orodje ki se lahko uporablja za iskanje za spomin razpoka v vašem programu. To je relativno preprost za vožnjo. Zaženete valgrind, nato pa še čeprav je malce verbose, dash check dash puščanja enak celoti, in nato dot poševnica in ime vašega programa. Torej bo valgrind nato zaženite svoj program in na samem koncu vašega programa teče pred njim zapre in vam daje še en poziv, to se dogaja, da analizira vaš Program, medtem ko je bilo tekmovanje v teku in povedal, da si puščajo koli spomin in še bolje, si dotaknil spomin, da ne pripada tebi? To ne more ujeti vse, ampak to je zelo dober pri lovljenju večino stvari. 

Torej, tukaj je primer mojega, ki ima rok Ta program, ki ima teči valgrind, na program, imenovan spomin, in grem izpostaviti črte, ki so v končni fazi v interesu nas. Torej, tam je tudi več motečih da sem izbrisana iz diapozitiva. Ampak kaj je šele videli, kaj je to Program je sposoben nam povedali. To je sposoben nam pove stvari kot neveljavno napisati velikosti 4. Z drugimi besedami, če se dotakneš spomin, Natančneje 4 bajte spomina da ne bi smeli imeti, valgrind vam lahko povem, da. Invalid write velikosti 4. Dotaknil si štiri bajte da ne bi smeli imeti. Kje si to storila? To je lepota. Memory dot c linija 21 je, če vas zasral in to je razlog, zakaj je koristno. Podobno kot GDB, lahko pomaga vas opozarjajo na dejanske napake. 

Zdaj, ta je malo bolj verbose, če ne zmedeno. 40 bajtov 1 blokih so vsekakor izgubil v izgubo zapis 1 od 1. Kaj to pomeni? No, to samo pomeni, da boste morali za 40 bajtov in nikoli nisi dal nazaj. Klical si malloc ali ste poklicali GetString in operacijski sistem vas 40 bajtov, ampak ti je dal nikoli osvobojeni ali sprosti ta pomnilnik, in biti pošteni, smo nikoli pokazati ste, kako vračati spomin. Izkazalo se je, da je super preprosto funkcijo imenovano brezplačno. Traja en argument, stvar želite sprostiti in dati nazaj, ampak 40 bajtov, očitno, v tem programu so bili izgubljeni v vrstici 20 spomina dot c. 

Torej, da vidimo ta program. To je super neuporabna. To samo dokazuje, to predvsem napake. Torej, kaj si zdaj. Tukaj je glavni in glavni, obvestilo, klici funkcija se imenuje F in se nato vrne. Torej ni vse tako zanimivo. Kaj f storiti? Opazili nisem sitnost s prototipom. Želel sem, da kodo kot minimalno kot je mogoče. Zato sem dal f zgoraj glavni in da je v redu, seveda, za kratke programe, kot je ta. Torej f ne vrne ničesar in ne ne bo ničesar, vendar pa to storijo. To izjavlja, podobno kot na primer Binky, kazalec se imenuje x, ki se dogaja Shranjevanje naslov notr. Tako, da je leva stran. V angleščini, kar je desna stran delaš? Kdorkoli? Kaj je to za nas? Ja? 

OBČINSTVO: [neslišno] krat na velikost notr ki je 10-krat, da [neslišno] DAVID Malan: Dobro in Naj povzamem. Torej dodeli dovolj prostora za 10 celih ali 10, kaj je velikost int, to je štiri bajte, torej 10-krat 4 40, tako da je desna stran, ki sem jih poudarjeno je, dajte mi 40 bajtov in shrani naslov prvega bajta v x. In zdaj končno, in tukaj je, kjer Ta program je buggy, kaj je narobe z linijo 21, ki temelji na tej logiki? Kaj je narobe z linijo 21? Ja? OBČINSTVO: Ne moreš Indeks v x [neslišno]. DAVID Malan: Ja. Jaz ne bi kazalo na x, kot je ta. Torej skladenjsko, da je v redu. Kaj je lepo je, podobno kot tebi lahko zdravi ime matrike kot da je to kazalec, podobno lahko zdravljenje kazalec, kot da je array, in tako sem lahko skladenjsko pravijo x stopnjevanim nekaj, x nosilec i, vendar 10 je problematično. Zakaj? 

OBČINSTVO: Ker to ni notri. 

DAVID Malan: To ni znotraj te kos pomnilnika. Kaj je največja vrednost, sem moral se postavi v teh oglatih oklepajih? 9, 0 do 9. Zaradi ničelne indeksiranje. Torej 0 do 9 bi bilo v redu. Nosilec 10 ni dobro in vendar, se spomni, čeprav, vsakič Zdi se mi, da bi poskušali narediti CS50 IDE crash z vpisom lažnih vrednot, ne sodelujejo vedno, in res, ste pogosto srečo samo zato, ker Operacijski sistem ne opazili, da si vedno tako malo mimo nekaj kos pomnilnika, ker si ostal v tehnično Vaše segmenta, ampak več o tem v razredu za operacijske sisteme in tako nekako takole lahko zelo enostavno iti neopaženo. Vaš program je nikoli ne bo crash dosledno ampak morda enkrat v nekaj časa. 

In tako poskusimo valgrind v zvezi s tem, in tukaj je kjer bomo dobili preobremenjeni z izhodom za trenutek. Zato poskrbite, pomnilniške ček valgrind uhajanja enak polni dot slash spomin. In tukaj je, zakaj obljubim to bi preplavijo. Tukaj je tisto, kar valgrind, tukaj je, kaj programer, nekaj let ago- odločil, da bi bilo dobro, za izhod izgledal. Torej, kaj je smisel tega. Torej vse poti na levem stran brez razloga je proces ID programa smo samo teči, posebni identifikator Za program smo pravkar tekel. Mi črta, ki iz slide, vendar obstaja je nekaj koristnih informacij tukaj. 

Naj se pomaknite do samega vrha. Tukaj je, kjer smo začeli. Torej, to ni vse, da je veliko moč. Tukaj je, da je neveljavna write velikosti 4 on line 21. No, kaj je linija 21? Linija 21 je bil ravno to in je smiselno da sem v veljavno pisanje 4 bajte, ker sem trudijo, da bi to celo, ki je lahko karkoli, to samo zgodi, da se nič, ampak skušam da ga na mestu da ne pripada meni. Poleg tega so tu dol, 40 bajtov v enem Bloki so definitivno izgubili v zapisu 1. To je zato, ker ko sem klic malloc tukaj, nikoli nisem dejansko prost spomin. 

Torej, kako lahko to popravimo? Naj gredo naprej in se malo varnejši in ne 9 tam in pusti me tukaj brezplačno x. To je nova funkcija za danes. Če bom zdaj ponovila, da spomin dot poševnica, dajmo teči valgrind o njem še enkrat, maksimirati moje okno in pritisnite tipko Enter. Zdaj, to je dobro. Ti pokopati dobra novica V vse te proizvodnje. Vse kup blokov ni bilo. Vrnili se bomo na kakšnem kupu je, vendar ni mogoče uhajanje. Torej, to je samo še en orodje za vaše kompletom orodja s katero lahko začnete najti zdaj napake, kot je ta. 

Ampak poglejmo, kaj več ne more iti narobe tukaj. Oglejmo prehod zdaj dejansko reševanje problema. Kot prahi, če bo to razreši malo zmede ali napetosti, to je zdaj smešno. Ja. To je zelo dobro. Ker kazalci so naslovi in ​​naslovi so na splošno po dogovoru napisana z šestnajstiški. Ha, ha, to je zdaj smešno. Kakorkoli že, tako da je zdaj dejansko rešiti problem. To je bilo super, super nizko raven doslej, in bomo lahko dejansko narediti uporabno Stvari s podrobnostmi teh nizki ravni. 

Zato smo uvedli nekaj tednov Pred pojem matrike. Množica je bilo lepo, ker je težko očistiti našo kodo ker če smo želeli napisati Program s številnimi študenti ali več imen in hiše in dorms in šole in vse to, bomo lahko shranite vse več čisto znotraj matrike. Ampak predlagam eno navzdol od matrike doslej. Tudi če ste ji ni utrpela sami v programu, samo nagonsko, kaj je slaba stvar o array, morda? Slišal sem nekaj šumi. OBČINSTVO: To je težko spreminjanje velikosti. DAVID Malan: To je težko spreminjanje velikosti. Ne morete spremeniti velikost matrike, v resnici, per v C. Lahko dodeliti drugo matriko, premakniti vse od starega v novo, in zdaj imajo nekaj dodatnega prostora, vendar pa je že ni všeč jezik kot Java ali Python ali poljubno število drugih jeziki, s katerimi nekateri od vas bi biti seznanjeni, kjer vas Lahko samo vztrajati dodal stvari gadosti do konca matrike. Ko imate niz velikost 6, da je njena velikost, in toliko, kot je ideja prej ima pufer določene velikosti, boste morali ugibati izven vrata Kakšno velikost želite, da bi lahko bilo? Če uganete, prevelika, ste zapravljaš prostor. Če uganete, premajhna, vam ne more shraniti, da so podatki, vsaj brez veliko več dela. 

Torej, danes, hvala za namig, bomo lahko začetek šivi skupaj lastnega meri podatkovne strukture, in Dejstvo, tukaj je nekaj da izgleda malo bolj Grobni na prvi pogled, ampak to je tisto, kar bomo imenovali povezana seznam, in njeno ime nekako povzema ga. To je seznam številk, ali V tem primeru, seznam številk, vendar bi bilo treba seznam karkoli, vendar to je povezano skupaj s pomočjo puščic, in vzemite ugibati s tem, kar tehnika bomo mogli skupaj šiv, nekako kot kokice z nitjo, vezavni izpiše pravokotniki tukaj? Njegove številke? Kaj je osnovni jezik funkcija? 

OBČINSTVO: Kazalec. 

DAVID Malan: Kazalec. Tako je vsak od teh puščic tukaj predstavlja kazalec ali pa samo naslov. Torej, z drugimi besedami, če želim za shranjevanje seznam številk, Ne morem ga shranite, če želim sposobnost, da rastejo in se skrči moj struktura podatkov v matriki. Tako da moram imeti malo bolj prefinjena, ampak obvestilo, da je to slika nekako nakazuje da, če ste pravkar dobil malo teme povezuje vse skupaj, Verjetno ni tako težko, da bi prostor vmes dve od teh pravokotnikov ali dve od teh vozlišč, kot bomo začeti Poklical jih, dal v novo vozlišče, in nato z nekaj novega nit, samo jarku tri vozlišča skupaj, prvi, zadnji in ena ki ste jo pravkar vstavi v sredino. 

In res povezani seznam, v nasprotju z vrsto, je dinamično. To lahko rastejo in se lahko psihiater in ne boste morali vedeti, ali skrbi v naprej, kako veliko podatkov ste tekoč za shranjevanje, vendar se izkaže, da moramo biti malo previdni, o tem, kako izvajati to. Torej, najprej kaj menijo, kako izvajati ena od teh malih pravokotnikov. To je preprosto izvajati int. Pravkar ste rekli int n in nato dobiš 4 bajte za notr, ampak kako pridem int, ga pokličete n, in potem kazalec, dajmo ga pokličete naslednji. Mi lahko pokličete njih Stvari kaj hočemo ampak rabim podatkovno strukturo meri. Ja? 

OBČINSTVO: Ampersand [neslišno]. 

DAVID Malan: Torej ampersand bomo uporabili za dobil naslov vozlišča potencialno. Vendar moramo drugo značilnost C z namenom da mi možnost, da ustvarijo ta običaj pravokotnik, ta običaj spremenljivka, če hočete, v spomin. OBČINSTVO: â struct. DAVID Malan: â struct. Spomnimo, od prejšnjega tedna, smo uvedli struct, je to razmeroma enostavno ključno besedo ki nam omogoča, da se stvari, kot je ta. C ni prišel s podatki struktura imenovana študenta. Na voljo je z int in float in char in na primer, vendar ne prihajajo z študenta, vendar smo lahko ustvarili vrsto podatkov študent, struktura študent, s to sintakso tukaj. In boste to znova in znova videti. Torej, ne skrbite pomnjenja ključne besede, vendar je ključna beseda, ki je pomembno je, Samo dejstvo, da smo rekli struct in potem smo jo imenovali študenta in v notranjosti študenta je ime in hišo ali domu in podobno. 

In zdaj je danes, kaj je predlagala to. Sem dodal nekaj besed, vendar, če želim za izvajanje te pravokotnik, ki je dobil tako int in kazalec, veš kaj, jaz sem dogaja, da razglasi struct imenovano vozlišče. Jaz sem tudi, znotraj njega, reči da ima vozlišče, ta pravokotnik, int in imenovali jo bomo n in ima naslednjo kazalec. In to je malce verbose, ampak če pomislim, puščice, ki so na sliki pred nekaj trenutki so kakšni podatkovni tip? Kjer je vsak od teh puščic je obrnjena za katera vrsta strukture podatkov? To ne kaže samo, da notr per se. To kaže na Celoten pravokotne stvar in da pravokotne stvar, smo rekli, se imenuje vozlišče. In tako smo nekako morali rekurzivno opredeli ta primer da vozlišče, recimo, bo vseboval int imenovano n in kazalec imenuje zraven in tip podatkovne strukture za katero da kazalec točk je očitno bo struct vozlišče. 

Torej je to zoprno verbose in samo, da je občutljiv, razlog, zakaj ne moremo samo rekel to, kar odkrito izgleda veliko bolj berljivo, je zato, ker odpoklic da C prebrati stvari od zgoraj navzdol, od leve proti desni. To ni, dokler ne bomo dobili podpičje da dejansko obstaja vozlišče ključno besedo. Torej, če želimo, da imajo te vrste ciklična sklicevanje notranjosti podatkov strukturo, moramo to storiti, če je rečemo struct vozlišče na vrhu, ki je nam daje daljšo pot, ki opisuje to stvar, potem pa znotraj rečemo struct vozlišče, in nato na zelo zadnji vrstici smo rekli, v redu, C, mimogrede, samo pokliči vso to prekleto stvar vozlišče in stop s pomočjo ključnih besed struct celoti. Torej je to samo neke vrste skladenjska Trik, ki na koncu nam omogoča ustvarjanje nekaj, kar je videti natanko tako kot je ta. 

Torej, če predpostavimo, zdaj bomo lahko izvajati ta stvar v C, Kako nam dejansko začetek prečkajo to? No, v resnici, vse, kar moramo storiti, je, Ponovil od leve proti desni in samo vrsta Vstavljanje vozlišča ali izbrišete vozlišč ali iskati stvari, kjerkoli želimo, ampak za to, gremo naprej in da stvari malo bolj realno, ker ta je zelo nizko raven doslej. Bi kdo dobesedno želel biti prvi? V REDU. Pridi gor. Kako ti je ime? 

DAVID: David. DAVID Malan: David. Me veseli. Jaz tudi. V redu. In moramo številko 9. Ni tako dobra kot prva, morda. OK, številka 9. Število 17, prosim. Naj grem nazaj malo dlje. Številka 22, prosim, in kaj pa dlje nazaj če vidim nobene roke z vso svetlobo ali ne. Nekdo, ki se je prostovoljno javil, prav tam. Ali želite, da pridejo gor? Vaš podlakti je prisilno gredo gor. OK, 17. 22. 26 se spušča. Bi še kdo rad forcefully-- Pridi gor. Dejanska prostovoljec. 

Torej zelo hitro, če vidva lahko uredite sami samo rad vozlišča na zaslonu. Hvala. In boste 26. Vse prave in hitre vnose. Tako da sem David in ste prav? DAVID: David. DAVID Malan: In vi ste? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID Malan: Taylor. Odlično. Torej, to so naši prostovoljci za danes in gredo naprej in premik malo na ta način, in samo pojdi naprej in naprej držite svoje številke, kot ste vi ali vaši Prvi znak in uporaba levo roko, pojdi naprej in samo izvajanje te puščice, samo tako da tvoja levica, je dobesedno kaže na kar bi morali poudariti na, in da si nekaj sobi, tako da bomo lahko vizualno videli svoje roke dejansko ki kaže, in si lahko samo točko nekako na tleh, je v redu. 

Torej, tukaj imamo povezan seznam enega, dva, tri, štiri, pet vozlišč sprva in opazili smo to posebno kazalec na začetku, ki je Ključ ker moramo slediti celotnega seznama dolžino nekako. Ti fantje, čeprav oni zapustili na desno, na hrbtni strani v pomnilniku, lahko dejansko kjerkoli v pomnilniku računalnika. Torej bi ti fantje lahko stoji kjerkoli na odru in da je v redu, tako dolgo, kot oni dejansko obrnjena drug od drugega, ampak, da se stvari čiste in enostavne, da bomo samo jih pripravijo leve proti desni kot to, vendar bi lahko velike vrzeli med temi vozlišči. 

Zdaj pa, če želim, da se dejansko vstaviti nekaj nova vrednost, pojdimo naprej in to storite. Imamo priložnost zdaj izbrati drugo vozlišče. Pravijo, začnimo z mallocing 55. Bi nekdo moti, da malloc? OK, pridi gor. Kako ti je ime? RAINBOW: Rainbow. DAVID Malan: Rainbow? V redu. Malloc Rainbow. Pridi gor. Torej, zdaj se moramo vprašati, algorithmically kjer bomo lahko dal 55. Torej, vsi vemo, seveda, kjer je verjetno pripada, če poskušamo da bo to urejeno in če bi vi vzeli eno korak nazaj, tako da ne padete faza, to bi bilo super. Torej dejansko, Rainbow, začeti znova tu z menoj, saj smo kot računalnik, sedaj lahko glej samo eno spremenljivko naenkrat. Torej, če gre za prvo vozlišče. Opazili, da je ni vozlišče, on je samo kazalec, in da je, zakaj je bil sestavljen, da bo Samo velikost kazalca, ne eden od teh polnih pravokotnikov. Torej gremo preveriti na vsakem ponovitev je 55 manj kot 9? No. Je 55 manj kot 17? No. Manj kot 22? Manj kot 26? Manj kot 34? In zdaj, očitno Mavrični pripada konec. Torej, da bo jasno, in kaj je bilo vaše ime, Taylor? 

TAYLOR: Taylor. DAVID Malan: Torej, med Taylorjeva levo roko in roke tukaj mavrica je, čigar roko je treba opozoriti na kaj v naročite vstaviti 55 na tem seznamu? Kaj moramo storiti? Ja? 

OBČINSTVO: Taylorjeva roko Treba levo točko. 

DAVID Malan: Točno tako. Torej vstavljanje vozlišče v konec seznama je zelo preprosta, saj Taylor samo je točka namesto na terenu ali bomo ga pokličete null, null je nekako odsotnosti od kazalca ali posebna nič kazalec, da ste gre izpostaviti z levi roko na Rainbow in nato Rainbow, kjer naj bi svojo levo roko verjetno točko? Dol. To ni dobro, če njena roka je nekako od kaže off tukaj ali nekako koli v katero smer. To bi veljalo vrednost smeti, ampak če ona poudarja, da nekatera znana vrednost, bomo call it nič ali null, da je v redu ker imamo čas v tej in vemo, seznam je zdaj končana. 

Torej, kaj je še relativno enostaven primer? Smo lahko malloc 5? Pridi gor. Kako ti je ime? TIFFANY: Tiffany. DAVID Malan: Oprosti? TIFFANY: Tiffany. DAVID Malan: Tiffany. V redu. Tiffany je malloced z vrednostjo 5. Pridi gor. Ta je relativno enostavno preveč, vendar kaj menijo, da vrstni red operacij zdaj. Bilo je precej enostavno z Taylor konec. Število 5 je seveda manj kot 9, in tako imamo Davida, imamo Tiffany, in kaj je vaše ime? 

JAKE: Jake. 

DAVID Malan: Jake. Tiffany, Jake, in David. Čigava roka je treba najprej posodobi? Kaj želite narediti tukaj? Tukaj je nekaj možnih načinov, vendar tam je tudi ena ali več napačni poti. 

OBČINSTVO: Začnite s skrajno levo. 

DAVID Malan: Začnite z levega. Kdo je levi je tukaj potem? OBČINSTVO: First. 

DAVID Malan: OK. Torej začeli s prvo in kje ste storili želite posodobiti roke Davidovi biti? OBČINSTVO: Proti 5. DAVID Malan: OK. Torej, David, točka ob petih ali Tiffany tukaj in zdaj? 

OBČINSTVO: Tiffany opozarja na 9? DAVID Malan: Popoln, razen Binky je vodja le nekako padel, kajne? Ker kaj je narobe z ta slika dobesedno? OBČINSTVO: Nič ne kaže. DAVID Malan: Nič ni kaže, da Jake zdaj. Mi smo dobesedno osiroteli 9 in 17, in ki smo jih dobesedno razpoka vse te pomnilnika, saj ga Prva posodobitev Davidovo roko, da je v redu, če je pravilno gledala Tiffany zdaj, ampak če ni imel eden predvidevanja kažejo na Jake, potem smo izgubili celota tega seznama. Torej, kaj je razveljaviti. Tako da je bila dobra stvar spotakniti ampak dajmo popraviti zdaj. Kaj naj naredimo najprej namesto tega? Ja? 

OBČINSTVO: Tiffany je treba opozoriti na 9? DAVID Malan: ne morem dobili, da je blizu vas. Kdo naj bi kazali na 9? 

OBČINSTVO: Tiffany. 

DAVID Malan: V redu. Torej Tiffany morala prva točka na 9. Torej bi Tiffany sprejeti na enaki vrednosti Davidu, ki se zdi odveč, za trenutek, ampak to je v redu, ker zdaj, drugi korak, bomo lahko posodobite Davidovo roko opozoriti na Tiffany, in potem, če Pravkar smo nekako čistih stvari kot da je to neke vrste pomladi, kot so, zdaj, da je pravilno vstavljanje. Tako odlična. Torej, zdaj smo skoraj tam. Oglejmo vstavite en finale vrednost kot vrednosti 20. Če bi lahko malloc eno končno prostovoljca? Pridi gor. Torej, ta je malo bolj zapleteno. Ampak res, koda smo pisanje, čeprav verbalno, je tako kot imajo kup na to, če so izpolnjeni pogoji, kajne? Imeli smo stanje preverjanje, če spada na koncu, morda na začetku. Potrebujemo nekakšno zanke najti mesto v sredini. Torej, kaj je naredil, da je s tem, kar ti je ime? 

ERIC: Eric. 

DAVID Malan: Eric? Eric. Me veseli. Torej imamo 20. Manj kot pet? No. Manj kot devet? No. Manj kot 17? No. V REDU. Tukaj je njegova domovina in vaša imena so spet? SUE: Sue. DAVID Malan: Sue. ALEX: Alex. DAVID Malan: Sue, Alex, in? ERIC: Eric. DAVID Malan: Eric. Morali priti do prvega posodobljenega katerih roke? 

OBČINSTVO: Eric. V REDU. Torej, Eric je treba poudariti, kje? Ob 22. Dobro. In zdaj, kaj je naslednje? Sue lahko pokažite na Eric in zdaj, če vaju samo narediti nekaj prostora, ki je v redu vizualno, zdaj smo naredili vstavljanje. Torej, kaj je zdaj preučiti vprašanje, ampak hvala toliko za naše prostovoljce. Zelo dobro opravljeno. Lahko obdržite tiste, če ti je všeč. In imamo lepo poslovilno darilo, če kar bi vsak rad izkoristil stres žogo. Naj samo prenese ta dol. Torej, kaj je takeaway to? To se zdi neverjetno kolikor imamo zdaj predstavil alternative Niz, ki se tako ni omejena na matriko neke fiksne velikosti. Prav tako lahko rastejo dinamično. 

Ampak sem podobno kot smo videli v tednih mimo, ne bomo nikoli dobili ničesar zastonj, kot gotovo obstaja trade-off tukaj. Torej z inflacijskih pritiskov vezavni seznam, je to dinamiko? Ta sposobnost, da rastejo in odkrito, smo lahko storili brisanje in bi lahko skrči, kot je potrebno. Kakšno ceno smo plačal? Dvakrat toliko prostora, najprej. Če pogledaš na sliki, ni več sem shranjevanje seznam števil. Jaz shranjevanje seznam cela plus kazalci. Tako da sem podvoji količino prostora. Zdaj, morda to ni tako big deal 4 bajte, 8 bajti, vendar bi to vsekakor dodati do velikih podatkovnih nizov. Kaj je še ena slaba stran? Ja? 

OBČINSTVO: Moramo jim prečkala eno-by-one. DAVID Malan: Ja. Moramo jim prečkala eno-by-one. Veš kaj, smo dali gor to super priročno funkcijo kvadratni nosilec zapis, bolj pravilno znan kot bralno, kjer smo lahko samo skok posameznemu elementu zdaj pa če sem še vedno imel moji prostovoljci tukaj, če sem hotel, da bi našli Številka 22, ne morem samo skok na nosilec nečesa nekaj. Moram pogledati preko seznama, veliko kot naši iskanjem primerov linearno, poiskati številko 22. Tako se zdi, da so plačali ceno tam. Vendar smo lahko kljub temu reševanje drugih problemov. 

Dejstvo je, naj vam predstavim le nekaj vizualnost. Torej, če ste bili do Mather jedilnici pred kratkim, boste opozarjajo, da njihova skladovnice pladnjev, kot je ta, bomo sposodili teh iz Annenberg pred razredom. Torej, to skladovnica pladnjev, čeprav, je zastopnik dejansko strukture računalništva podatkov. Je podatkovna struktura v računalništvu znan kot odvodnik, ki zelo lepo dovzetni za točno to vizualno. Torej, če je vsako od teh pladnjev ne pladenj, ampak kot veliko in sem hotel za shranjevanje številk, I bi lahko dal eno dol, in jaz bi dal še en tukaj, in še naprej zlaganje številk na vrhu med seboj, in kar je potencialno koristno o tem je, da tisto, kar je bila posledica te strukture podatkov? Katerih število morem izvleči Prvi najprikladneje? Najbolj nedavno en dal tam. 

Torej, to je tisto, kar bi nas pokličite računalništva podatkovna struktura LIFO. Zadnji noter, prvi ven. In bomo videli kmalu, zakaj da bi bilo koristno, vendar za zdaj, pomislimo le na premoženje. In to je nekako neumno, če menite, o tem, kako jedilnica to počne. Vsakič, ko so čisti pladnji in dal svež tisti na vrhu, bi lahko imeli prej čisto ampak na koncu je zelo umazana in prašna pladenj na samem dnu če vas nikoli dejansko priti do dna, da stack, ker vas samo obdržati dajanje novih in čiste tisti na vrhu je. Ista stvar se lahko zgodi, v supermarketu preveč. Če imate vitrini mleka in vsakič CVS ali kdor dobi več mleka, ki ste jo pravkar zabil za mleko, že imate v hrbtu in si dal nove spredaj, boste imeli nekaj zelo grdo mleko na koncu strukture podatkov, zato, ker je vedno na dnu ali ekvivalentno je vedno na hrbtu. 

Toda obstaja še en način, da razmišljajo o podloga ki gre gor podatke in primer, je to. Če ste eden izmed tistih ljudi, ki ima rad line up zunaj trgovin Apple ko nov izdelek prihaja ven, ste verjetno ne uporabljate podatkov dimnika struktura, saj vas bi odtujiti vsakdo drug, ki je podloga ki gre gor za nakup nekaj novo igračo. Namesto, da ste verjetno uporabljate kakšne strukture podatkov ali kakšen sistem v resničnem svetu? Upajmo, da je linija, ali več pravilno ali več britansko-podobno, čakalna vrsta. In se izkaže, čakalne vrste, je tudi Struktura podatkov v računalništvu, toda čakalna vrsta ima zelo drugačna lastnina. To ni LIFO. Zadnji noter, prvi ven. Bog ne daj. To je namesto FIFO. Prvi noter, prvi ven. In to je dobra stvar za poštenost "zaradi Zagotovo, če ste podloga up super zgodaj zjutraj. Če prideš tja najprej, ti želijo, da bi dobili najprej kot dobro. 

In tako vse te podatke strukture, čakalne vrste in nizov in grozde drugih, izkaže vas Lahko pomislite na to kot samo matrike. To je niz, morda fiksna velikost 4, vendar pa bi se nekako lepo, če bi lahko samo kopičijo Pladnji skoraj neskončno visok, če bomo imajo, da je veliko pladnje ali številk. Mogoče želimo uporabite povezani seznam tukaj, vendar trade-off se bo lahko, da potrebujemo več pomnilnika, traja malo več časa, vendar smo ne omejujejo višine dimnika, podobno kot vitrina Mather je lahko omejuje velikost dimnika, in tako so ti sklepi oblikovanje ali možnosti so na voljo za nas v končni fazi. Torej s temi podatki strukture, smo začeli videnje nove zgornje meje potencialno o tem, kaj je bilo prej super hitro in kjer bomo zapustili off danes in kje bomo upam, da pridete do je v sredo, bomo začeli iskati po podatkih struktura, ki nam omogoča iskanje s pomočjo podatkov v dnevniku času končno spet. In videli smo, da se spomnimo, v ničelni tednu in ena z binarnim iskanjem ali razkoraka in vladaj. Prihaja še nazaj in bolje, sveti gral za to sredo bo prišel gor s podatkovna struktura, ki deluje resnično ali teoretično konstantna čas, pri čemer ni važno koliko milijone ali milijarde stvari imamo v strukturi podatkov, bo to nam bo konstantno časa, morda en korak ali dva koraka ali 10 korakov, vendar je konstantno število korakov iskanje po te strukture podatkov. Da bo res lahko sveti gral vendar več o tem v sredo. Se vidimo takrat. 

[Predvaja glasba]