[Powered by Google Translate] [Teden 6] [David J. Malan] [Harvard University] [To je CS50.] [CS50.TV] 

To je CS50, in to je začetek tedna 6, tako nekaj novih orodij, so zdaj na voljo za vas, da izkoristijo, Prvi, ki se imenuje CS50 slog. Kvota je, če ste kot jaz ali kateri koli izmed učnih tovariši, Verjetno ste že videli program, katerega ime je videti malo kaj takega. Morda ste začeli zmanjševati nekaj kotičkov pozno ponoči, ali boste z njo ravnati kasneje, in potem TF ali CA pride v času uradnih ur. Potem je za nas težko brati. No, ta številka je sintaktično pravilna, in da bo sestavil, in bo dejansko delujejo. Ampak to definitivno ni za 5 slogu. 

Toda zdaj, če gremo v ta imenik tu- in opazil, da imam conditions2.c- jaz pa sem tekla ta nov ukaz, style50, na tej datoteki conditions2.c, Enter opazili, da se me je obvestil, da je bilo stiliziran. Gedit opazil, da se je datoteka spremenila na disku, in če kliknem osveži, so vse vaše težave, zdaj avtomatizirati. [Aplavz] To je ena od stvari, ki smo to storili konec tedna. Zavedaj se, da je nepopoln, ker so del kode da preprosto ne bodo mogli popolnoma Stilizovati, vendar zavedaš, to je zdaj orodje, ki ga lahko izkoristijo če se le da pospraviti nekaj več errantly daje zavite oklepaje in podobno. 

Toda še bolj prepričljiv je zdaj CS50 hotela. Z CS50 pregleda, lahko dejansko opravljajo enake teste pravilnosti na svojo oznako, da so učni fantje sposobni. To je zapoved črta korist, ki zdaj prihaja v aparatu takoj, ko je to update50 kot na pset 4 specifikacije in jo uporabite v bistvu, kot je ta. Zaženete ukaz check50. Potem se boste peljali v argument ukazne vrstice, ali bolj na splošno znana kot stikalo ali zastavo. Na splošno so stvari, ki so vezaje imenuje stikalo za program v ukazni vrstici, tako določa, c pregledi, ki jih želite zagnati. 

Testi, ki jih želite teči so označene z edinstveno tega niza, 2012/pset4/resize. Z drugimi besedami, to je samo samovoljna, ampak edinstven niz ki jih uporabljamo za enolično identifikacijo pset 4 v pravilnost preskusov. In potem si določite prostor ločen seznam datotek, ki jih želite naložiti da CS50 Preverite za analizo. Na primer, če grem v mojo rešitev tukaj za resize.c- Naj odpre okno večji terminal- in sem šel naprej in vodijo recimo check50-c 2012/pset4/resize, in potem sem šel naprej in določiti imena datotek, resize.c, in nato pritisnite tipko Enter, da stisne, it dodane slike, preveri, in sem ne cel kup testov. Tisti v rdeči barvi na levem pravi, da resize.c in bmp obstajajo. To je bil test. To je bilo vprašanje, smo vprašali. In to je nesrečen, ker je bil odgovor napačen. Bela besedilo pod njim piše naj bmp.h obstajati, in to je samo moja krivda. Pozabil sem, da jo naložite, tako da moram naložiti obe datoteki, resize.c in bmp.h. Toda zdaj opazil vse druge preskuse, so v rumeno, ker ne deluje, in tako obraz smiley je navpična, ker je niti vesel, niti žalosten, vendar pa moramo to vprašanje odškodnin v rdeči barvi, preden bodo te druge preglede teči. 

Naj popravim. Naj pomanjšanje in ponovite to, tokrat s bmp.h tudi v ukazni vrstici, Enter, in zdaj, če bo šlo vse dobro, to se dogaja, da preveri in se nato vrne rezultat, zadržite dih, vse zeleno, kar pomeni, da delam res dobro pset 4 do sedaj. Lahko vidite in sklepamo iz opisnega besedila tukaj kaj je to smo preverili. Testirali smo najprej narediti datoteke obstajajo? Mi testiramo pa resize.c prevedite? Nato smo preizkusili ta ne spreminjanje velikosti 1x1 slikovnih pik BMP, ko n, resize dejavnik, je 1. Torej, če nimate pojma, kaj je n boste, ko boste potopite v pset 4, ampak da preprosto sanity preverite, poskrbite, da niste resizing slika sploh če resize faktor 1. Če pa, nasprotno, to spremeni velikost je 1x1 pixel do 1x1 pixel BMP za pravilno 2x2 če je n 2, potem pa podobno, moja oblikuje ustrezno. 

Skratka, to je pomenilo, da, 1, sprejmejo prehodih prste iz enačbe tik preden oddate pset. Boste točno vedeli, kaj se bo vaše TF kmalu vedeli ko greste o predložitvi nekaterih od teh problematičnih skupin, in tudi pedagoško motivacijo je res, da dajo priložnost, ki je pred vami, tako da če veš vnaprej da obstaja hroščev v kodi, in preskusi, ki niso opravili, lahko dajo v učinkovitejšem časa spredaj za reševanje teh težav namesto izgubili točke, dobili povratne informacije od svojega TF, in potem iti, "Ah," kot bi mislil, da sem ven. Zdaj vsaj tam je orodje, ki vam pomaga najti to. To se ne bo poudariti, kjer je hrošč, vendar pa vam bo povedal, kar je značilno za to. 

Zdaj zavedaš, da testi niso nujno izčrpna. Samo zato, ker ste videli zaslon, polno zelenih smiley obrazov ne pomeni, da vaša koda ni popoln, vendar to ne pomeni, da je opravil določene teste, ki jih predpisuje spec. Včasih mi ne bomo objavili preglede. Na primer, whodunit, eden od vidikov pset 4, je nekakšno razočaranje, če vam damo odgovora na vprašanje, kaj je to, pa še več načinov, da se vidi kdo je oseba, ki je v tej rdeči hrupa. Spec bo vedno navedite v prihodnosti pset 5 naprej kar preveri obstajajo za vas. Opazili boste, da je to bela URL na dnu. Za zdaj je to samo diagnostični izhod. Če obiščete ta URL, boste dobili cel kup norih, Grobni sporočil da ste dobrodošli, da si preko, ampak je predvsem za zaposlene tako da bomo lahko diagnosticirati in odpravljati napake napake v check50 sama. 

Brez odlašanja, gremo na, kjer smo končali. CS50 knjižnica smo za samoumevno, za nekaj tednov, potem pa prejšnji teden, smo začeli piling nazaj eno od plasti njim. Začeli smo dajanje razveljavi niz v prid kaj namesto tega? [Dijaki] Char. Char *, ki je char * ves ta čas zdaj pa mi ni treba pretvarjati, da je to dejansko vrsto podatkov niz. Nasprotno, to je bilo sinonim za vrste char *, in niz je zaporedje znakov, zakaj je smiselno, da predstavljajo strune kot char * s? Kaj char * predstavljajo v okviru tega koncepta niza? Ja. >> [Študent] Prvi znak. Dobro, prvi znak, vendar ne povsem prvi znak. To so-[Dijaki] naslov. Dobro, naslov prvega značaja. Vse, kar je potrebno, da predstavlja niz v spomin računalnika je le edinstven naslov svoji prvi bajt. Vi sploh ni vedel, kako dolgo je ker kako lahko ugotovimo, da je od dinamično? [Študent] dolžina niza. Lahko pokličete niz dolžine, odlično, ampak kako deluje dolžina niza? Kaj počne? Ja. [Študent] Naj bo, dokler ne dobite null značaj. Ja, točno tako, samo ponovi z zanko, pa zanka, karkoli od * do konca, in na koncu je zastopana z \ 0, tako imenovani znak NUL, nul, Ne smemo zamenjevati z nična, kar je kazalec, , ki bo prišel v pogovoru še danes. 

Mi olupljen nazaj plast GetInt, nato pa smo si ogledali na GetString, in opozarjajo, da sta od teh funkcij, ali pa res, GetString, je bil z določeno funkcijo dejansko razčleniti, da se glasi, ali analizirati uporabnika prispevek. In kaj je bilo to novo funkcijo? Scanf ali sscanf. To je dejansko na voljo v nekaj različnih okusih. Tam je scanf, tam je sscanf, tam je fscanf. Za zdaj, čeprav, dajmo osredotočiti na tista najbolj enostavno kaže, in mi gredo naprej in odprla v aparatu datoteke, kot je ta, scanf1.c. To je super preprost program, ampak da naredi nekaj, da nikoli nismo storili brez pomočjo CS50 knjižnice. To postane int od uporabnika. Kako deluje? No, v vrstico 16 tam, Opazili smo, da razglasi int x, imenovan, in na tej točki v zgodbo, kaj je vrednost x? [Neslišno študentski odziv] [David M.] Ja, kdo ve, nekaj smeti vrednost lahko, tako da v 17, samo povej uporabnika Daj mi nekaj, prosim, in korak 18 je, če postane zanimivo. Scanf zdi, da sposoditi idejo iz printf v tem, da uporablja ta format kode v narekovajih. % D je seveda številka. Ampak zakaj sem potujejo in x namesto samo x? Prvi je pravilen. Ja. [Neslišno študentski odziv] Točno tako, če je cilj tega programa, kot je funkcija GetInt sam, je, da bi dobili int od uporabnika lahko grem mimo funkcije vse spremenljivke želim, ampak če ne bom mimo njih s sklicevanjem ali naslovom ali z kazalcem, vse sinonim za namene današnjih potem ta funkcija ni nobene možnosti, da spremeni vsebino te spremenljivke. To bi prenesli v kopiji tako kot buggy različico zamenjave da smo govorili nekaj časa sedaj. 

Toda namesto, da naredite & x, sem dobesedno poteka v kaj? [Študent] naslov. >> Naslovu x. To je kot risanje zemljevida za funkcijo, imenovano scanf in rekel sem, To so navodila za za kos pomnilnika v računalniku da lahko greš noter shranite nekaj celo število Da bi sscanf storiti zdaj, da kaj operater, katere dele sintakse se bo moral uporabljati čeprav ne moremo videti, ker je nekdo napisal to funkcijo? Z drugimi besedami - kaj je to? [Študent] X brati. Prišlo bo nekaj obravnava, vendar le v zvezi s x tukaj. Če je scanf prevalili naslov x, sintaktično, kakšna izvajalec zavezuje, da nekje obstaja znotraj izvajanja scanf, tako da scanf dejansko lahko napišete številko 2 na ta naslov? Ja, tako je *. Spomnimo se, da je naša * dereference subjekt, ki v bistvu pomeni iti tja. 

Ko ste bili predal naslov, kot v tem primeru, scanf je verjetno, če bi dejansko pogledal okoli njegove izvorne kode, počne * x enakovreden ali dejansko gredo na ta naslov in dal neko vrednost tam. Zdaj, kot za to, kako scanf dobi vhod s tipkovnice, bomo mahal z rokami ven danes. Samo domnevamo, da nam operacijski sistem sscanf govoriti na tipkovnici uporabnika, vendar v tem trenutku zdaj v vrstici 19, ko smo preprosto natisniti x, se zdi, da je tako scanf, da je dal int v x. To je točno, kako deluje scanf, in opozarjajo, prejšnji teden To je točno, kako GetString in GetInt in njegova druga družina funkcij na koncu dela, čeprav z rahlim variance kot sscanf, kar pomeni, skeniranje niz namesto tipkovnice. No, pa si oglejte nekaj variance to. V scanf2, dejansko sem zamočil. Kaj je narobe, jaz pa bom skriti komentar, ki pojasnjuje toliko, kaj je narobe s tem programom, različica 2? Bodite kot tehnično mogoče ta čas. Izgleda zelo dobro. To je lepo razgibana, toda- OK, kaj pa dajmo slivov do krajših vprašanj? Linija 16. Kaj je linija 16 počne točno, ampak tehnično angleščino? Kako malo nerodno. Ja, Michael. [Študent] To se kaže na prvi črki v nizu. 

Ok, zapri. Naj poteg, da se malo. Kaže na prvo črko niza, ki ga razglasi spremenljivko z imenom pufra , ki bo opozorila na prvi naslov niz, oziroma, da bo točko natančneje znak. Obvestilo, da se dejansko ne kaže nikamor, ker ni naloga upravljavca. Ni enačaj, da vsi delamo, je dodelitev spremenljivega ti buffer. To se zgodi, da je 32 bitov, ker je kazalec, in vsebino medpomnilnika verjetno sčasoma bo vseboval naslov char, vendar za zdaj, kaj vsebuje pufer? Samo nekaj lažne, kdo ve, nekaj smeti vrednost, ker nismo izrecno initialized, zato ne bi smeli prevzeti ničesar. Ok, zdaj se vrstica 17-kaj vrstica 17 storim? Mogoče, da bo ogrel tega. To natisne niz, kajne? To natisne String prosim. 

Vrstica 18 je nekako znano zdaj, da smo pravkar videli varianca to vendar z drugačno oznako formatu, tako da v vrstico 18, smo povedali scanf tukaj je naslov za kos pomnilnika. Želim si, da prstan v nizu, kot je vsebovano v% s ampak problem je, da smo naredili nekaj stvari tukaj. Kaj je eden od problemov? [Študent] Poskuša dereference null kazalec. Dobro, null, ali samo drugače znan kazalci. Saj predaja scanf naslov, vendar si rekel pred nekaj trenutki da je ta naslov je nekaj smeti vrednost, saj nismo dejansko dodeliti z ničemer, in tako govoriš scanf dejansko šel dal niz tukaj, vendar ne vem, kje sem pa vendar, tako da smo dejansko ne dodeli pomnilnik za pomnilnik. Poleg tega, kaj si sploh ne govorim tudi scanf? Recimo, da je to kos pomnilnika, in ni bilo smeti vrednost, vendar še vedno niste povedali scanf nekaj pomembnega. [Študent] Kadar je v resnici, je znak pove. Znak za, tako da v tem primeru, to je v redu. Ker je varovalni že deklariran kot kazalec z * kos skladnje, nam ni treba uporabljati znak '& ker je že naslov, ampak mislim, da sem ga slišal sem. [Študent] Kako velik je? Dobro, ne bomo povedali scanf kako velik medpomnilnik, kar pomeni, da tudi če bi bilo varovalni kazalec, smo govoriš scanf, dal niz tukaj, tukaj pa lahko 2 bajta, bi bilo 10 bajtov, bi bilo megabajt. Scanf nima pojma, in ker je to kos pomnilnika verjetno, da ni še niz. To je samo niz, ko pišete znake in z \ 0 do te kos pomnilnika. Zdaj je samo nekaj kos pomnilnika. Scanf ne boste vedeli, kdaj nehali pisati na ta naslov. 

Če se spomnimo nekaj primerov v preteklosti, kjer sem naključno natipkan na tipkovnici poskuša overflow pufer, in smo se pogovarjali o tem v petek točno to. Če nasprotnik nekako vbrizga v svojem programu veliko večjo besedo ali stavek ali stavek, potem pa so pričakovali, da lahko prekoračitev kos pomnilnika, kar ima lahko slabe posledice, kot prevzem celotnega programa samega. Moramo popraviti to nekako. Naj pomanjšanje in šel v različici 3 tega programa. To je nekoliko bolje. V tej različici, opazili razliko. V vrstico 16, sem spet razglasitvi spremenljivko z imenom rezervo, kaj pa je zdaj? To je niz 16 znakov. To je dobro, saj to pomeni, sem lahko zdaj povem scanf Tukaj je dejansko kos pomnilnika. Skoraj lahko misliš nizi kot kazalci zdaj, čeprav je to dejansko niso enakovredni. Te bomo obnašali drugače v različnih kontekstih. Ampak to je vsekakor res, da je navajanje varovalni 16 sosednjo znakov, ker to je tisto, kar je matrika in je bila za nekaj tednov. 

Tukaj sem govoril scanf tukaj je kos pomnilnika. Tokrat je dejansko kos pomnilnika, ampak zakaj je ta program še bolje izkoriščene? Kaj je narobe še? Rekel sem, da mi 16 bajtov pa- [Študent] Kaj pa če tip v več kot 16? Točno, kaj če uporabnik vnese v 17 znakov ali znakov 1700? Dejstvo je, da vidimo, če si ne more spotakniti te napake zdaj. To je bolje, vendar ne popolna. Naj gredo naprej in zagon, da scanf3 za pripravo tega programa. Naj teče scanf3, String prosim: halo, mi pa zdi, da so v redu. Naj poskusim nekoliko daljši 1, pozdravljena. Ok, dajmo Pozdravljeni, kako ste danes, Enter. Kako vrste srečo tukaj, recimo Pozdravljeni, kako ste. Prekleto. Ok, tako da smo imeli srečo. Poglejmo, če ne moremo popraviti. Ne, ne bo me kopirati. Poskusimo še enkrat. V redu, pripravljeni. Bomo videli, kako dolgo lahko pretvarjamo, da se osredotoči pa še to. Prekleto. To je zelo primerno, pravzaprav. Takole. Točka je. 

To je neprijetno, čeprav je bilo tudi, da je tudi eden od virov velike zmede pri pisanju programov, ki imajo napake, ker se manifestirajo samo enkrat v nekaj časa, včasih. Dejstvo je, da tudi če se vaša koda popolnoma zlomljen, da bi se lahko samo v celoti razdelijo na vsake toliko časa ker se včasih, predvsem kaj se zgodi, se nameni za operacijski sistem Malo več pomnilnika, kot ga dejansko potrebuje kakršnega koli razloga, in tako nihče ne uporablja pomnilnik takoj po vašem bloku 16 znakov, tako da, če greš na 17, 18, 19, karkoli, to ni nič takega. Zdaj, računalnik, tudi če se ne zruši na tej točki, lahko začeli uporabljati Bajt številko 17 ali 18 ali 19, za kaj drugega, V tem trenutku vaše podatke, da si dal tam, čeprav traja predolgo, bo dobil prepisana lahko s kakšno drugo funkcijo. Ni nujno, da bo ostal nedotaknjen, vendar to ne bo nujno povzročila SEG napako. Ampak v tem primeru, sem končno določa dovolj znakov da sem v bistvu presegla svoj segment pomnilnika in bum, operacijski sistem dejal: "Žal mi je, da ni dobro, segmentacijo krivda." 

In kaj je sedaj vidim, če kaj ostane tukaj, v mojem imeniku, opazil, da imam to igro tukaj, jedro. Vedite, da je ta znova pozval njegove posmrtne ostanke. To je v bistvu datoteka, ki vsebuje vsebino pomnilnika vašega programa na mestu, ki je strmoglavilo, in samo za primer, poskusite malo tu me spusti noter in vodijo gdb na scanf3 in nato določite tretjega argumenta, imenovano jedro, in opazil sem, da če bom seznam kodo, da bomo lahko kot običajno z gdb, da začnete hoditi v okviru tega programa, in ga lahko zaženete in takoj, ko sem udaril, tudi z ukazom korak v gdb- takoj, ko sem zadel potencialno hroščat linijo po vnosu v velikem nizu Bom lahko dejansko opredelijo tukaj. Več o tem, čeprav se v oddelku z vidika temeljnih odlagališč in podobno, tako da lahko dejansko suniti okrog znotraj jedro smetišče in videli, kaj linija vas program ni uspel. Vsa vprašanja, nato na kazalcev in naslove? Ker danes naprej bomo začeli jemati za samoumevno, da te stvari obstajajo in vemo, kaj so. Da. 

[Študent] Kako to, da ni bilo, naj 'in' znak ob strani, Dobro vprašanje. Kako to, da nisem imela, naj 'in' znak poleg znaka niza, kot sem že prej pri večini naših primerov? Kratek odgovor je, nizi so nekoliko posebne. Skoraj lahko misliš varovalo, kot je dejansko bil naslov, in je prav tako se zgodi, da bo v primeru, da oglati oklepaj zapis je priročno, tako da lahko gremo v razredu 0, 1 nosilec, Nosilec 2, ne da bi morali uporabiti * zapis. To je malo belo laž, saj nizi in kazalci so v resnici malo drugačna, lahko pa so pogosto, vendar ne vedno uporabljajo izmenično. Na kratko, ko je funkcija pričakuje kazalec na kos pomnilnika, lahko bodisi dajati naslov, ki je bil vrnjen s knjižnične funkcije malloc, in bomo videli malloc spet kmalu, ali pa dajati ime matrike. Ni vam treba storiti 'in' znak z nizi, ker so že v bistvu všeč naslove. To je edina izjema. Oklepaju, da jih nekaj posebnega. 

Bi lahko naredi 'in' znak poleg pomnilnika? V tem primeru ni. To ne bo delovalo, ker, spet, to vogalu primeru če nizi niso povsem dejansko naslove. Ampak bomo morda prišel nazaj, da kmalu z drugimi primeri. Poskusimo rešiti težavo. Imamo strukturo podatkov, ki smo jih s pomočjo nekaj časa znano kot matriko. Zadeva točke, to je tisto, kar smo imeli. Ampak nizi nekaj upsides in slabosti. Polja so lepe, zakaj? Kaj je ena stvar, ki vam je všeč, kolikor vam je všeč nizi, o matrikah? Kaj je prikladno za njih? Kaj posebnega? Zakaj smo jih uvedli na prvem mestu? Ja. [Študent] Te lahko shranite veliko podatkov, in ne boste morali uporabiti vso stvar. Lahko uporabite odsek. Dobro, z vrsto lahko shranite veliko podatkov, in vam ni nujno, da uporabite vse za to, da boste lahko overallocate, ki je lahko priročno, če ne veš vnaprej, koliko kaj lahko pričakuje. 

GetString je odličen primer. GetString, ki jih zapiše nas nima pojma, koliko znakov, da pričakujejo, tako da bomo lahko dodeli kose zveznega pomnilnika je dober. Polja tudi reševanje problema smo videli pred nekaj tedni zdaj če vaša koda začne prenesejo v nekaj zelo slabo načrtovan. Spomnimo se, da sem ustvaril strukturo, imenovano študentsko David, nato pa, da je dejansko alternativa, čeprav da imajo spremenljivko z imenom ime in drugo spremenljivko z imenom, mislim, house, in drugo spremenljivko imenovano ID, ker v tej zgodbi sem pa želel uvesti nekaj drugega Rob je všeč v programu, zato sem se odločil, potem počakaj malo, Moram preimenovati teh spremenljivk. Recimo moj name1, ID1, house1. Recimo Rob je ime2, house2, ID2. Potem pa počakaj malo, kaj pa Tommy? Potem smo imeli še tri spremenljivke. Uvedli smo nekoga drugega, štirje sklopi spremenljivk. Svet je začel grdo zelo hitro, Tako smo uvedli konstrukti, in kaj je izsiljevala o struct? Kaj struct C vam naredil? To je res nerodno danes. Kaj? >> [Neslišno študentski odziv] Ja, še posebej, typedef vam omogoča, da ustvarite nov podatkovni tip, in struct, struct ključnih besed, vam omogoča, da zajame konceptualno povezani deli podatkov, skupaj nato pa jih pokličete nekaj podobnega študenta. 

To je dobro, saj se zdaj lahko modelirati veliko bolj neke vrste konceptualno skladna pojem študenta v spremenljivko namesto samovoljno ob eno za vrvico, eno za ID, in tako naprej. Polja so lepo, ker nam omogočajo, da začnete čiščenje našo kodo. Toda kaj je slaba zdaj na matriki? Kaj ne moreš? Ja. [Študent], moraš vedeti, kako velik je. Moraš vedeti, kako velika je, tako da je neke vrste bolečine. Tisti, ki ste v prejšnjih izkušenj vemo, da v programskem veliko jezikov, kot Java, lahko zaprosi kos pomnilnika, posebej niza, kako veliki so vam z dolžino, lastnine, tako rekoč, in to je res priročno. V C, ne morete niti poklicati strlen na splošno matriko ker strlen, kot beseda pomeni, je samo za godala, pa lahko ugotovimo dolžino niza, saj te konvencije o človekovih da imajo \ 0, ampak z matriko, bolj generično, je le kos pomnilnika. Če je niz ints, da se ne bo nekaj posebnega značaja Na koncu te čaka. Moraš vedeti, koliko matrike. Še ena slaba stran matrike gojijo svojo glavo se GetString. Kaj je druga negativna matrike? Gospod, samo ti in jaz danes. [Neslišno študentski odziv] >> To je tisto? To je deklarirana na kupu. Ok, deklarirana na kupu. Zakaj ne bi bilo všeč? [Študent] Ker dobi ponovno to. To postane ponovno. Ok, če uporabljate niz dodeliti pomnilnika, ne moreš, na primer, ga vrnite, ker je na kupu. Ok, to je slabost. In kako približno ena z vrsto? Ko ga dodelijo, si nekako zajebali, če potrebujete več prostora kot matrika. 

Nato smo uvedli, odpoklica, malloc, ki nam je dal možnost, da dinamično dodeli spomin. Kaj pa, če smo želeli drugačen svet skupaj? Kaj pa, če želimo rešiti nekaj teh težav tako da smo namesto, moje pero je zaspal tu- Kaj če bi namesto tega želeli predvsem ustvariti svet, ki je ni več, kot je ta? To je matrika, in, seveda, ta vrsta poslabša, ko bomo zadeli konec niza, in zdaj ni več prostora za druge celo ali druge narave. Kaj, če bi nekako preemptively pravijo tudi, zakaj ne sprostijo To zahteva, da se vsi ti kosi spomin stikata back to back, in zakaj ne, ko moram int ali char, daj mi samo prostor za enega od njih? In ko rabim drugega, daj mi še en prostor, in ko rabim drugega, daj mi še en prostor. Prednost, ki zdaj je, da če nekdo drug meni spomin tukaj, ni nič takega. Jaz bom vzel to dodatno kos pomnilnika tukaj in potem je to ena. 

Zdaj je samo ulov tukaj je, da je to skoraj počuti kot sem Cel kup različnih spremenljivk. Ta občutek petih različnih spremenljivk potencialno. Kaj pa, če mi ukradel idejo od nizov , s katerim smo nekako povezati te stvari skupaj konceptualno in kaj, če sem to storil? To je moja zelo slabo sestavljena puščica. Recimo, da vsak od teh kose pomnilnika opozoril na drugi strani, in ta človek, ki nima brata na njegove pravice, nima takega puščico. To je v bistvu tisto, kar se imenuje povezani seznam. To je nova struktura podatkov, ki nam omogoča, da se dodeli kos pomnilnika, potem drugo, nato drugo, nato pa še, kadarkoli hočemo med programom, in se spomnimo, da so vsi nekako povezani z veriženjem dobesedno skupaj, in smo naredili, da slikovno tukaj s puščico. Toda v kodi, kaj bi lahko mehanizem, prek katerega bi lahko nekako povezati, skoraj kot nič, 1 kos na drug kos? Mi lahko uporabite kazalec, kajne? Ker res puščica, ki se dogaja v zgornjem levem kvadratu, ta tip tukaj, da je ta lahko v notranjosti vsebujejo te kvadrata ne le nekaj ints, ne samo nekaj char, ampak kaj, če sem dejansko dodeljeno malo več prostora, tako da je zdaj, vsak od mojih kose pomnilnika, čeprav bo to stalo, Zdaj je videti malo bolj pravokotne oblike, kjer eden od kose pomnilnika Uporablja se za več kot številka 1, in potem, če je ta človek hrani s številko 2, ta drugi kos pomnilnika se uporablja za puščice, ali bolj konkretno, kazalec. In, da sem shranite številko 3, medtem ko sem jaz to uporabijo za točko tega tipa, in zdaj ta tip, Recimo, da želim le tri takšne kose pomnilnika. Jaz bom potegnil črto čez to, kar kaže na null. Ni dodatnih znakov. 

To je sicer res, kako lahko greste o izvajanju nekaj, kar se imenuje povezani seznam. Povezani seznam, je nova struktura podatkov, in je odskočna deska proti veliko luksuznih podatkovne strukture, ki se začnejo pri reševanju problemov po zgledu težav Facebook tipa in tipa Google težav če imate velike podatkovne nize, in to več ne zniža za shranjevanje vsega contiguously in uporabite nekaj podobnega linearno iskanje ali celo nekaj takega kot binarno iskanje. Hočeš še boljše vožnjo krat. V bistvu, bo eden od svetih Grails govorimo o pozneje ta teden ali naslednji je algoritem, katerega čas vožnje je konstantna. Z drugimi besedami, vedno traja enako količino časa, ne glede na to, kako velik je vložek, in da bi resnično privlačno, še toliko bolj, kot nekaj, kar logaritemski. Kaj je to na zaslonu tukaj? Vsaka od pravokotnikov, je točno to, kar sem narisal z roko. Ampak stvar vso pot na levi je posebna spremenljivka. To bo še en kazalec, saj tisti kavelj z povezan seznam, kot se imenujejo te stvari, je, da boste morali viseti na enem koncu povezani seznam. 

Tako kot z vrvico, morate poznati naslov prvega char. Enaka ponudba za povezane sezname. Moraš vedeti, naslov, prvi kos pomnilnika ker je od tam, lahko dosežete vse drugo. Padanja. Kakšno ceno plačujemo za to vsestranskost ob dinamično precejšen strukturo podatkov, da če bomo kdaj potrebovali več pomnilnika, v redu, Samo še en kos nameniti pripravi in ​​kazalec iz starega v novo repu seznama? Ja. [Študent] To traja približno dvakrat toliko prostora. To traja dvakrat toliko prostora, tako da je vsekakor slaba, zato smo to videli kompromis med pred časom in prostorom in prilagodljivostjo če ga zdaj, ne potrebujemo 32 bitov za vsako od teh številk. Smo res potrebujejo 64, 32 za številu in 32 za kazalec. Ampak hej, imam 2 GB RAM-a. Dodajanje še 32 bitov tukaj in tukaj se ne zdi, da je velik posel. Toda za velikih zbirk podatkov, prav gotovo dodaja do dobesedno dvakrat toliko. Kaj je še slaba zdaj, ali kaj funkcije ne predamo če predstavljajo sezname stvari, povezane s seznamom in polja ne? [Študent], ne moreš prečkati nazaj. Ne moreš prečkati nazaj, torej si nekako zajebali, če ste peš Od leve proti desni z uporabo zanke for ali while zanko in potem se zavedaš, "Oh, želim se vrniti na začetek seznama." Ne moreš, ker ti kazalci le gredo od leve proti desni, kot kažejo puščice. 

Sedaj lahko spomniš začetek seznama z drugo spremenljivko, ampak to je zapletenost, da v mislih. Matrika, ne glede na to, kako daleč greš lahko vedno naredite minus, minus, minus, minus in pojdi nazaj od koder ste prišli. Kaj je še slaba tukaj? Ja. [Neslišno študentski vprašanje] Lahko, da ste dejansko le predlagano podatkovno strukturo, imenovano dvojno povezani seznam, in res, bi dodali še en kazalec za vsako od teh pravokotnikov ki gre v drugo smer, z glavo, ki Zdaj je lahko prečkala naprej in nazaj, slaba stran, ki je sedaj boste uporabljali trikrat toliko pomnilnika, kot smo vajeni in tudi dodatno zaplete v zvezi s kodo, ki jo moraš napisati priti prav. Ampak vse to so morda zelo razumne kompromise, če obrat je bolj pomembno. Ja. [Študent], prav tako ne morete imeti 2D povezan seznam. Dobro, si ne morem imeti 2D povezani seznam. Lahko bi. To še zdaleč ni tako enostavno, kot matriko. Kot matriko, imaš odprt, zaprt nosilec nosilec, oklepaj, zaprto konzole in boste dobili nekaj 2-dimenzionalno strukturo. Lahko bi izvajala 2-dimenzionalni povezani seznam če vam dodatek, kot si predlagal-1/3 kazalec za vsako od teh stvari, in če mislite o drugem seznamu, ki prihajajo na vas slog 3D od zaslona, ​​da nas vse, kar je le še ena veriga neke vrste. Mi lahko to storite, vendar to ni tako enostavno, kot tipkanje oklepaj, oglati oklepaj. Ja. [Neslišno študentski vprašanje] Dobro, tako da je to pravi trik. 

Ti algoritmi, ki smo predalčne več, kot so oh, binarnega iskanja, lahko poiščete niz številk na krovu ali telefonski imenik toliko hitreje, če ga uporabljate deli in vladaj in binarno iskanje algoritem, vendar dvojiška iskalna zahteva dve domnevi. Ena, ki je bil razvrščen podatki. Sedaj lahko verjetno bi ta urejen, tako da morda to ni zaskrbljujoče, vendar binarno iskanje prevzela tudi , ki ga je izbirni dostop do seznama številk in polje vam omogoča, da ob vsakem času dostop, ter z naključnim dostopom Mislim, če si dal niz, koliko časa trajalo, priti v razred 0? Ena operacija, ki ste jo pravkar uporabljate [0] in si tam. Koliko korakov je potrebnih, da se na mesto 10? En korak, greš na [10] in si tam. V nasprotju s tem, kako priti do 10. celo število v povezano seznamu? Moraš začeti na začetku, saj ste samo spomnimo začetek povezan seznam, tako kot niz, ki se je spomnil z naslovom svojega prvega char, in da je bil to 10. int ali da je 10. znak v nizu, boste morali iskati celo prekleto stvar. 

Še enkrat, ne bomo reševanju vseh naših problemov. Mi smo uvedbo novih, vendar je res odvisno od tega, kaj ste poskušali oblikovati za. V zvezi z izvajanjem tega lahko sposodim idejo iz tega študentskega strukture. Sintaksa je zelo podobna, razen sedaj, ideja je malo bolj abstrakten od hiše in ime in ID. Ampak jaz predlagam, da bi lahko imeli podatkovne strukture v C , ki se imenuje vozlišče, saj je bila zadnja beseda na slide kaže, znotraj vozlišča in vozlišča je le generično posoda iz računalništva. To je običajno sestavljen kot krog ali kvadrat ali pravokotnik, kot smo ga opravili. In v tem strukturo podatkov, ki smo jih int, N, tako da se je število hočem shraniti. Ampak kaj je ta druga vrstica, struct vozlišče * naslednji? Zakaj je to pravilno, ali pa kakšno vlogo igra ta stvar, čeprav je malce skrivnosten na prvi pogled? Ja. [Neslišno študentski odziv] Točno, tako da je * vrsta plena, da je to kazalec neke vrste. Ime tega kazalca je samovoljno naslednji, lahko pa smo jo imenovali kar smo želeli, ampak kaj ima to kazalec pokažite? [Študent] Druga vozlišče. >> Točno tako, da kaže na drugo takšno vozlišče. 

No, to je neke vrste radovednost C. Spomnimo se, da je C prevajalnik prebere z vrha do dna, od leve proti desni, kar pomeni, če-je to malo drugačna od tega, kar smo naredili z učencem. Ko smo definirali študenta, smo dejansko ni dal besedo tam. Prav tako je dejal typedef. Potem smo imeli int id, String ime, String hišo, in nato študent na dnu struct. Ta izjava je malo drugačna, saj Tudi v tem primeru C prevajalnik je malo neumen. To je samo, da se glasi od zgoraj navzdol, tako da, če ne doseže 2. linijo tukaj če se ob prijavi in ​​vidi, oh, tukaj je spremenljivka se imenuje naslednji. To je kazalec na struct vozlišče. Prevajalnik bo zavedaš, kaj je struct vozel? Še nikoli nisem slišal za to stvar pred, ker beseda vozlišča morda ne zdi drugače dokler se na dnu, tako da je to odveč. Moraš reči struct vozlišče tukaj, ki jih lahko nato skrajša kasneje hvala za typedef dol, vendar je to zato, ker smo se sklicujete na strukturo znotraj same strukture. To je tisti kavelj tam. 

Nekaj ​​zanimivih težave bodo nastale. Imamo seznam številk. Kako vstaviti v to? Kako ga poiskati? Kako izbrisati iz nje? Še posebej zdaj, ko imamo za upravljanje vseh teh kazalcev. Si mislil kazalci so bili nekako um-upogibni Ko je eden izmed njih samo poskušam prebrati int nanj. Zdaj moramo upravljati celoten seznam vredno. Zakaj ne vzamemo 5-minutni premor, nato pa bomo prinese nekateri ljudje na odru storiti točno to. 

C je veliko bolj zabavno, ko je to odzval. Kdo bi dobesedno želel biti prvi? V redu, pridi gor. Vi ste prvi. Kdo želi biti 9? Ok, 9. Kaj pa 9? 17? Malo klika tukaj. 22 in 26 v tej prvi vrsti. In potem, kako o nekom, ki se tam pokazal na. Vi ste 34. Ok, 34, pridi gor. Prvič je tam. Ok, vsi štirje fantje. In kdo smo rekli za 9? Kdo je naš 9? Kdo v resnici hoče biti 9? V redu, no, je 9. Pa gremo. 34, bomo veseli tam. Prvi del je, da sami izgleda tako. 26, 22, 17, dobro. Če lahko pokonci na stran, saj bomo vas malloc v trenutku. 

Dobro, dobro. V redu, odlično, tako da je zastaviti nekaj vprašanj tukaj. In dejansko, kako ti je ime? >> Anita. Anita, v redu, pridi sem. Anita se dogaja, da nam pomagajo, nekako rešiti 1 dokaj preprosto vprašanje na eni strani, ki je, kako se vam zdi, ali je vrednost na seznamu? Zdaj pa opazil, da po eni strani, ki jo tu Lucas, je malo drugačna, zato je njegov kos papirja je namenoma postrani ker to ni čisto tako visok in ne zavzame toliko bitov, čeprav tehnično ima enako velikost papirja, samo zavrti. Ampak on je malo drugačna v tem, da je samo 32 bitov za kazalec, in vse te fante je 64 bitov, polovica od tega je več, polovica od tega je kazalec. Vendar pa se kazalec ni upodobljen, tako da, če vama lahko nekoliko nerodno uporabite levo roko opozoriti na osebo poleg vas. In ti si številka 34. Kako ti je ime? Ari. Ari, tako da pravzaprav ima papir v desno roko in levo roko gre naravnost navzdol. Ti predstavljajo null na levi strani. 

Zdaj naša človeška slika je zelo dosledna. To je pravzaprav, kako kazalci delo. In če lahko scrunch malo v to smer, tako da nisem v napoto. Anita tu našli mi številko 22, ampak prevzame omejitev, ki ni ljudje držijo listov, ampak to je seznam, in imate samo Lucas za začetek ker je dobesedno prvi kazalec. Recimo, da si sam kazalec, in tako tudi vi imeli možnost, da kaže na nekaj. Zakaj ne bi začeli z opozorilom na točno to, kar se kaže na Lucas? Dobro, in mi uzakoniti tole tukaj. Samo zaradi razpravo, dovolite mi, dvigni prazno stran tukaj. Kako se napiše svoje ime? >> Anita. Ok, Anita. Recimo, da vozlišče * Anita = Lucas. No, ne bi klical Lucas. Morali bi poklicati tebe. Zakaj je to v resnici v skladu z realnostjo tukaj? Ena, prva že obstaja. Prva je bila dodeljena domnevno nekje tukaj. Node * prvi, in je bila dodeljena seznam nekako. Ne vem, kako se je to zgodilo. To se je zgodilo pred razred začne. Ta povezani seznam ljudi je bil ustvarjen. In zdaj, na tej točki v zgodbo, to se vse dogaja na Facebooku očitno pozneje, Na tej točki v zgodbo, je bila Anita initialized, da je enaka prvi, kar pa ne pomeni, da Anita točk na Lucas. Namesto, ona opozarja na tisto, kar kaže na ker isti naslov, ki je znotraj 32-bitno Lucas je - 1, 2, 3 - Zdaj je tudi v notranjosti je 32 bitov Anita - 1, 2, 3. 

Zdaj je bil 22. Kako bi šel o tem? Kaj je to? >> Pokažite na karkoli. Pokažite na karkoli, tako da gredo naprej in ga odigra kot najboljše kar lahko tukaj. Dobro, dobro, zdaj pa si gledala, kako ti je ime pri 22? Ramon. >> Ramon, Ramon da se držiš 22. Zdaj ste naredili pregled. Ali Ramon == 22, in če je tako, na primer, se lahko vrnemo res. Naj me, ko so ti fantje stojijo tukaj nekoliko nerodno, Naj naredi nekaj hitreje, kot je bil int. Grem, da gredo naprej in reči (vozlišče * seznam, int n). Takoj bom nazaj z vami. Sem moral napisati nekaj kode. In zdaj bom iti naprej in narediti to, vozlišče * Anita = seznam. In jaz bom, da gredo naprej in reči, medtem ko (Anita! = NULL). 

Metafora tukaj je že malo raztegne, vendar pa (Anita! = NULL), kaj hočem narediti? Rabim nek način primerjanje celo, da Anita pokrije. V preteklosti, ko smo imeli strukture, ki je vozlišče, smo uporabili zapis pik, mi pa bi rekel nekaj podobnega anita.n, vendar je težava v tem, da Anita ni struct po sebi. Kaj je z njo? Ona je kazalec, tako da res, če želimo uporabiti ta zapis dot- in to se dogaja, da si namenoma malce skrivnosten, moramo storiti nekaj podobnega pojdi na levi roki, ne glede na Anita kaže na in nato dobil polje z imenom n. Anita je kazalec, ampak kaj je * anita? Kaj se vam zdi, če greš na tisto, kar se kaže na Anita? Struct, vozlišče in vozlišče, odpoklic, je polje z imenom n ker je, spomnim se te 2 polja, naslednji in n, ki smo jih videli pred nekaj trenutki tukaj. 

Da bi dejansko posnemajo to oznako, bi lahko to stori, in reči, če ((* anita). n == n), n, da iščem. Obvestilo, da je bil sprejet funkcija števila mi je mar. Potem bom lahko šel naprej in naredil kaj takega zameno resnično. Drugače, če to ne gre, kaj hočem narediti? Kako prevesti za kodiranje, kaj Anita storil intuitivno s hojo po seznamu? Kaj naj storim tukaj za simulacijo Anita čemer ta korak v levo, ta korak v levo? [Neslišno študentski odziv] >> Kaj je to? [Neslišno študentski odziv] Dobro, ni slaba ideja, vendar v preteklosti, ko smo naredili to, kar smo storili anita + + ker bi, da dodate številko 1, Anita, ki bi običajno opozoriti na naslednjo osebo, kot Ramon, ali oseba, poleg njega ali ob njem oseba po vrsti. Ampak to ni čisto dobro, ker sem kaj ta stvar videti v spomin? Ne da se. Moramo onemogočiti, da. Izgleda, da je to v spomin, in čeprav sem sestaviti 1 in 2 in 3 blizu drug drugega, če bomo res to simulacijo, lahko fantje, medtem ko še vedno kaže na istih ljudi, nekatere od vas vzamejo naključni korak nazaj, nekaj od tebe naključno korak naprej? 

Ta nered je še vedno povezani seznam, vendar bi ti fantje lahko kjerkoli v pomnilniku, Tako anita + + ne bo delovalo, zakaj? Kaj je na lokaciji Anita + +? Kdo ve. To je nekaj drugega vrednost, prav tako se zgodi, da se je postavil Med vsemi temi vozlišči po naključju, saj nismo z matriko. Smo namenili vsako od teh vozlišč posamično. Ok, če lahko vi sami čistijo nazaj. Naj predlagajo, da se namesto anita + +, smo namesto tega Anita dobi- No, zakaj ne gremo kar Anita je gledala in nato naredite. naprej? Z drugimi besedami, gremo Ramon, ki je imetnik številko 22, in potem. Naslednja je, kot da bi se Anita kopiranje levo roko kazalec. Ampak ona ne bi šel dlje od Ramon, ker smo našli 22. Ampak to bi bilo ideja. Zdaj, to je bog, grozno zmešnjavo. Odkrito povedano, ne bo nihče nikoli ne pozabite, to sintakso in tako srečo je dejansko malo namerno, oh, saj dejansko ni videl, kaj sem napisal. To bi bilo bolj prepričljiv, če bi lahko. Voila! 

V ozadju sem bil reševanju problema na ta način. Anita, da bi ta korak v levo, Prvič, mi gredo na naslov, ki Anita kaže na in kje bo našla ne le n, ki smo ga pravkar preverja, zaradi primerjava je, pa boste našli tudi naprej - v tem primeru, Leva Ramon kaže na naslednje vozlišče v seznamu. Ampak to je bog, grozno zmešnjavo, ki sem ga omenil prej, vendar se izkaže, C nam omogoča poenostaviti to. Namesto pisanja (* Anita), lahko namesto samo napisati Anita-> n, in to je točno isto stvar, funkcionalno, vendar je veliko bolj intuitiven, in to je veliko bolj skladno s sliko, ki smo jih pripravi Ves ta čas z uporabo puščic. 

Končno, kaj moramo storiti na koncu tega programa? Obstaja ena vrstica kode, ki ostane. Vrnitev kaj? Ne drži, ker če pridemo skozi celotno zanko, medtem ko in Anita je v resnici, nič, kar pomeni, da je šla vse do konca seznama kam je obrnjena, kako ti je ime? Levo Arija >> Ari. Roko, ki je nična. Anita je sedaj null, in vem, da si samo stal tukaj nerodno v negotovosti ker sem zletel na monolog tukaj, pa vam bomo vključiti ponovno čez nekaj trenutkov. Anita je nič na tej točki v zgodbi, zato pa zanka konča, in bomo morali vrniti napačno, kajti če bi dobil vse do sedaj null pointer Ari je potem ni bilo več, da je iskati v tem seznamu. Mi lahko očistite to gor preveč, vendar je to zelo dobra izvedba pa za prečkanje funkcije, poiščite funkcijo povezan seznam. Še vedno linearno iskanje, vendar to ni tako enostavno, kot + + kazalec ali + + spremenljivka i, ker zdaj ne moremo uganiti kjer vsaka od teh vozlišč v spominu. Moramo dobesedno slediti sled drobtinami ali, natančneje, kazalci, da bi dobili iz enega vozlišča v drugo. 

Zdaj pa poskusimo še eno. Anita, ne želite, da pridejo nazaj? Zakaj ne gremo naprej, in dodeli eno osebo iz občinstva? Malloc, kako ti je ime? >> Rebecca. Rebecca. Rebecca je bila malloced iz občinstva, in ona je zdaj shranjevanje številko 55. In cilj pri roki Zdaj je Anita vstaviti Rebecca v povezanem seznamu tukaj v njenem primernem mestu. Pridi sem za trenutek. Sem naredil kaj takega. Sem naredil vozlišča *. In kaj ti je ime? Rebecca. >> Rebecca, v redu. Rebecca gets malloc (sizeof (vozlišče)). Tako kot smo se dodelijo stvari, kot so študenti in malenkosti v preteklosti, moramo na velikost vozlišča, tako da zdaj Rebecca kaže na kaj? Rebecca ima dve polji v njej, od katerih je 55. Naredimo kaj, rebecca-> = 55. Ampak potem rebecca-> next bi se rada, prav zdaj, njena roka je malo kdo ve? To kaže na nekaj smeti vrednosti, zakaj ne za dobro mero smo vsaj to, da leva roka je zdaj na njeni strani. Zdaj Anita, ga vzemite od tukaj. Imate Rebecca mu je bil dodeljen. Pojdi naprej in ugotoviti, kje moramo postaviti Rebecca. Dobro, zelo dobro. Dobro, dobro, zdaj pa morate zagotoviti nekaj smeri, da ste dosegli Ari. Njegova levica je nična, vendar Rebecca očitno pripada pravica, Torej, kako moramo spremeniti to povezano seznam da bi se dodala Rebecca na ustreznem mestu? Če bi lahko dobesedno premikanje ljudi leve roke okoli, kot je potrebno, bomo odpraviti težavo na ta način. Dobro, dobro, medtem, leva Rebecca je zdaj po njeni strani. 

To je bilo prelahko. Poskusimo dodeljevanje-Smo že skoraj pri koncu, 20. V redu, pridi gor. 20 je bila dodeljena, zato naj gredo naprej in ponavljam tukaj pravkar smo storili Saad vozlišča *. Imamo malloc (sizeof (vozlišče)). Nato smo narediti točno isto skladnjo, kot smo se pred tem za 20, in jaz bom naslednji = NULL, zdaj pa je čas, da Anita vstavite ga v povezanem seznamu, če bi lahko igral, da točno isto vlogo. Execute. Dobro, dobro. Zdaj pa premislite, preden začnete premikati levo roko okoli. Ti imaš daleč najbolj nerodno vlogo danes. Čigava roka je treba najprej preselil? Ok, počakaj, slišim nekaj ne je. Če bi nekateri ljudje vljudno rad pomagal rešiti nerodno situacijo. Čigav levo roko, je treba posodobiti 1. morda? Ja. [Študent] Saad je. Ok, Saad je, zakaj, kajne? [Neslišno študentski odziv] Dobro, kajti če gremo, kako ti je ime? >> Marshall. Marshall, če gremo z roko 1. do null, Zdaj smo dobesedno staršev štirje ljudje na tem seznamu ker je bil edina stvar, ki kaže na Ramon in vsi na levi strani, tako, da posodobitev kazalec Prvi je bil slab. Naj razveljavite to. Dobro, zdaj pa pojdi in se ustrezno levo roko, ki kaže na Ramon. Ta občutek malo odveč. Zdaj pa sta dva človeka, ki kažejo na Ramon, ampak to je v redu ker zdaj kako drugače bomo posodobiti seznam? Kaj drugi strani pa je, da se premaknete? Odlično, zdaj smo izgubili vsako spomin? Ne, tako dobro, da vidimo, če ne moremo razdeliti še enkrat. 

Mallocing zadnjič, številka 5. Vso pot v hrbet, pridi dol. To je zelo vznemirljivo. [Aplavz] Kako ti je ime? >> Ron. Ron, v redu, ste malloced pod številko 5. Pravkar smo izvrši kodo, ki je skoraj enaka kot ti samo z drugim imenom. Odlično. Zdaj, Anita, srečno vstavite številko 5 v seznam zdaj. Dobro, in? Odlično, tako da je to res, tretja od treh skupnih zadev. Najprej smo imeli nekoga, ki je konec, Rebecca. Nato smo imeli nekoga v sredini. Zdaj imamo nekoga na začetku, in v tem primeru, smo zdaj morali posodobiti Lucas prvič ker je prvi element na seznamu je zdaj s točko na novo vozlišče, , ta pa se kaže v vozlišču številka 9. 

To je bilo zelo nerodno, demonstracija, sem prepričan, Tako velik aplavz za te fante, če bi lahko. Lepo opravljeno. To je vse. Lahko obdržite vaše listov kot malo spomina. Izkazalo se je, da je v tem zakoniku ni tako enostavno, kot samo premika roke okoli in kaže, kazalci na različnih stvareh. Toda zavedati, da ko gre čas za izvedbo nekaj podobnega povezani seznam ali različic tega, če se osredotočite na zelo te temeljne osnove, na grižljaj velike težave, ki jih moram ugotoviti, je to ročno ali s to roko, zavedaš, da tisto, kar je sicer precej zapleten program lahko, v resnici, se skrajša na dokaj enostavne gradnikov, kot je ta. 

Vzemimo stvari v bolj sofisticirane smeri miru. Zdaj imamo pojem povezanega seznama. Imamo tudi-hvala za predlog, tam, dvojno povezan seznam, ki izgleda skoraj enako, toda zdaj imamo dva kazalca znotraj struct namesto enega, in bi mi verjetno poklical ti kazalci prejšnjega in prihodnjega ali levo ali desno, vendar pa v resnici potrebujejo dva izmed njih. Kodeks bi se malo bolj vključeni. Anita bi morala narediti več tukaj na odru. Vendar pa bi prav gotovo izvajajo to vrsto konstrukcije. Z vidika časa vožnje, čeprav bi kaj bo čas delovanja za Anito da najdejo število n v povezanem seznamu sedaj? Še vedno velik O n, tako da ni boljšega kot linearno iskanje. Tega ne moremo narediti binarno iskanje, čeprav, še enkrat. Zakaj je tako? Ne moreš okoli skakati. Čeprav smo seveda videli vse ljudi na odru, in bi Anita so jo eyeballed in reče: "Tu je sredi seznama" ona ne bi vedeli, da če bi bila računalniški program ker je edina stvar, ki je imela za zapah na na začetku scenarija je bil Lucas, ki je bil prvi kazalec. Ona bi bilo treba nujno upoštevati te povezave, Računam svojo pot, dokler ni ugotovljeno, približno na sredini, in celo tedaj, ona ne bo vedel, ko je ona prišla do sredine če ona gre vse do konca, da ugotovimo, koliko jih je, potem bi backtracks, in da je preveč težko, če si imel dvojno povezani seznam neke vrste. 

Reševanje težave danes, ampak o uvedbi druge. Kaj pa drugačno strukturo podatkov v celoti? To je fotografija pladnjev v Mather House, in v tem primeru imamo podatkovno strukturo smo tudi nekako že govoril. Pogovarjala sva se o kupu v okviru spomina, in da je vrsta namerno poimenovana zato, ker sklad v smislu spomina je dejansko podatkovna struktura, ki ima več in več stvari opira na vrhu. Vendar je zanimivo stvar kupu, kot je to primer v resnici je, da je posebna vrsta podatkovne strukture. To je struktura podatkov, pri čemer je prvi element v je zadnji element ven. Če ste prvi pladenj, ki se dajo na kup, boš žal je zadnji pladenj, da je treba odstraniti sveženj, In to ni nujno dobra stvar. Nasprotno, lahko si misliš o tem, obratno, zadnja leta je prvi ven. 

Zdaj pa vsi scenariji pridejo na misel, ko ima kup podatkovna struktura, kjer imate to lastnost na zadnji noter, prvi ven, je pravzaprav nekaj posebnega? Je to dobra stvar? Je to slabo? To je definitivno slabo, če kadi niso vsi enaki in vsi so bili posebni različnih barv ali malenkosti, in barvo želiš, je vse na dnu. Seveda ne moreš, da brez velikega truda. Moraš začeti z vrha in vaš način dela. Prav, kaj pa če si bil eden od teh fantov fan ki čaka vso noč poskuša priti iPhone in cevovodov navzgor na mestu, kot je ta? Ali ne bi bilo lepo, če bi Apple Store je bilo kup podatkov, struktura? Bravo? Nay? To je samo dobro za ljudi, ki pokažejo v zadnjem možnem trenutku in se nato pulili čakalne vrste. In v bistvu je dejstvo, da sem bil tako nagnjena reči čakalne vrste je dejansko v skladu s tem, kar bi temu lahko rekli neke vrste podatkovne strukture, 1, v resnici, če bi ne glede na to, in želite, da prvi v obstati prvi ven če je samo zaradi človeške pravičnosti. Bomo običajno zahtevajo, da čakalne vrste strukturo podatkov. 

Izkazalo se je, poleg tega, povezanih seznamov, lahko začnete uporabljati te iste osnovne ideje in začnite ustvarjati nove in drugačne vrste rešitev za probleme. Na primer, v primeru kupu, bi lahko predstavljal sklad uporablja podatkovno strukturo, kot je ta, bi predlagal. V tem primeru sem razglasil struct, in sem rekel, znotraj te strukture je niz številk in potem spremenljivka se imenuje velikost, in jaz bom poklical ta stvar kup. Torej, zakaj se to dejansko deluje? V primeru dimnika, lahko črpam to dejansko na zaslonu, kot matriko. Tukaj je moj dimnik. To so moje številke. In jih bomo pripraviti, saj je to, to, to, to, to. In potem imam še nekatere druge podatke člana tukaj, ki se imenuje velikost, tako da je to velikost, in to je številka, in skupaj za celotno iPad tukaj predstavlja eno žetonov strukturo. Zdaj, privzeto velikost je verjetno dobil, da se inicializira na 0, in kaj je v matriki števil prvotno Ko sem prvič dodeli niz? Garbage. Kdo ve? In dejansko ne važno. Ni važno, če je to 1, 2, 3, 4, 5, povsem naključno zaradi smole shranjena v moji strukturi, ker tako dolgo, da vem, da je velikost dimnika 0, potem vem, načrtno, ne glej na kateri od elementov v matriki. Ni važno, kaj je tam. Ne glej na njih, kot bi se posledice take velikosti od 0. 

Recimo, zdaj grem naprej in nekaj vstavili v dimnik. Želim vstavite številko 5, zato sem dal številko 5 tukaj, in potem kaj sem dal dol? Zdaj bi dejansko postavil 1 glede na velikost, in zdaj bo sveženj velikosti 1. Kaj pa, če grem naprej in vstavite številko, recimo, 7 naslednji? To nato postane posodobiti 2, potem pa bomo naredili 9, in potem se je ta posodobljen 3. Ampak zanimivo, zdaj to dimnika je, da Moral bi odstraniti element, ki, če želim, da pop Nekaj ​​off stack, tako rekoč? 9 bi bila prva stvar, da gredo. Kako naj bo slika spremenila, če želim, da pop off element dimnika, Podobno kot pladenj Mather? Ja. >> [Študent] Nastavi velikost do 2. Točno tako, je vse, kar sem naredil določene velikosti do 2, in kaj naj naredim z array? Nimam storiti ničesar. Jaz bi samo, da je analni, dal tja 0 ali -1 ali kaj pomenil da to ni zakonit vrednost, vendar to ni pomembno, saj Ne morem posneti zunaj samega niza, kako dolgo je tako da vem, samo pogledaš na prvih dveh elementov v tem polju. Zdaj, če grem in doda številka 8 na tem polju, kako se slika spremeni naslednje? To postane 8, in ta postane 3. Jaz sem za rezanje nekaj kotičkov tukaj. Zdaj imamo 5, 7, 8, in smo spet na velikost 3. To je zelo preprosta za uporabo, ampak ko bomo obžalovali to oblikovanje odločitev? Ko se stvari začnejo iti zelo, zelo narobe? Ja. [Neslišno študentski odziv] Če želite iti nazaj in dobili prvi del si dal noter 

Izkazalo se je, čeprav je tukaj stack polja pod pokrovom motorja, Te podatkovne strukture smo začeli govoriti o tudi splošno znani kot abstraktne podatkovne strukture, s katerim si, kako izvajajo je popolnoma poleg točke. Struktura podatkov, kot kup pa naj bi dodali podporo dejavnosti, kot pritiskom, ki potiska pladenj na kupu, in pop, ki odstrani element iz dimnika, in to je to. Če ste bili do nekoga drugega prenesti kodo, ki že izvajajo ta stvar imenovano kup, bi ta oseba napisal le dve funkcije za vas, push in pop, katere edini cilj v življenju bi bilo storiti točno to. Vi ali on ali ona, ki izvajajo ta program bi bili v celoti 1 odločiti, kako izvajati semantike potiskanje in živahen pod pokrovom ali funkcionalnost potiska in živahen. In sem se nekoliko kratkovidna odločitev tukaj z izvajanjem svoj kupček s to preprosto strukturo podatkov zakaj? Ko pa to podatkovno strukturo odmor? Na kateri točki se moram vrniti napako, ko uporabnik pokliče pritisk, na primer? [Študent] Če ni več prostora. Točno tako, če ne bo več prostora, če sem presegel zmožnosti, ki so vsi pokrovčki, saj kaže, da je to nekakšen globalni konstante. No, potem bom samo, da moram reči: "Oprosti, ne morem potisnite drugo vrednost na kupu, "podobno kot v Mather. 

Na neki točki, da boš zadel zgornji del, da je malo omaro. Ni več prostora ali zmogljivosti v plasteh, pri čemer pa obstaja neke vrste napake. Imajo postaviti element nekje drugje, pladenj nekje drugje, ali sploh nikamor. Zdaj, po prioritetnem vrstnem redu, bi morali izvajati to malo drugače. Čakalna vrsta je malo drugačna v tem, da pod pokrovom, se lahko izvajajo kot matriko, ampak zakaj v tem primeru, sem predlagala da imajo tudi glavo element, ki predstavlja glavo seznama, Sprednji del seznama, prva oseba, ki je v skladu v trgovini Apple, poleg velikosti? Zakaj potrebujem dodaten podatek tukaj? Spomnite se, kaj številke je če sem sestavljena, kot sledi. Recimo, da je to zdaj čakalne vrste namesto žetonov, razlika je v tem, tako kot Apple Store-čakalni vrsti je poštena. Prva oseba v vrsti na začetku seznama, številka 5 v tem primeru on ali ona se bo spustil v trgovini najprej. Naredimo to. Recimo, da je to stanje mojega vrsti v tem trenutku v času, in zdaj Apple Store Odpre se prva oseba, številka 5, vodi v trgovino. Kako spremeniti sliko, sedaj, ko sem v čakalni vrsti ali odstranijo prvo osebo Na sprednji strani linije? Kaj je to? >> [Študent] Spremenite vrsto. Spremenite glavo, tako da 5 izgine. V resnici pa je tako, čeprav, kako najbolje to storiti? V resnici pa je to, kot da je ta tip izgine. Kaj bi naredil številka 7 v dejanski trgovino? Želijo narediti velik korak naprej. 

Toda kaj smo prišli do tega, da ko gre za nizi in premikanje stvari okoli? To je neke vrste odpadkov svojega časa, kajne? Zakaj moraš biti tako analni kot, da bi prva oseba na začetku proge na telesno začetku kos spomin? To je popolnoma nepotrebno. Zakaj? Kaj bi lahko samo spomni namesto tega? >> [Neslišno študentski odziv] Točno tako, sem lahko samo spomnite s to dodatno glavo podatkov držav da je zdaj vodja seznamu ni več 0, kar je bilo pred nekaj trenutki. Zdaj je dejansko število 1. Na ta način sem dobil rahlo optimizacijo. Samo zato, ker sem v čakalni vrsti ali odstranijo nekoga iz linije na začetku proge v Apple trgovini ne pomeni, da ima vsak premik, ki odpoklic je linearna operacija. Lahko namesto preživijo čas samo stalno in potem doseči hitrejšega odziva. Toda cena Plačujem je, kaj pridobite dodatno zmogljivost in ne da bi morali preusmeriti vse? Ja. >> [Neslišno študentski odziv] Lahko dodate več ljudi, tudi, da težava pa je pravokotna na dejstvo, da ne bomo prestavne ljudi okoli. Še vedno je matrika, tako da ali ne prehajamo vse, ali ne, Oh, vidim, kaj misliš, v redu. Pravzaprav se strinjam s tem, kar praviš, saj je skoraj, kot da smo zdaj ne bo nikoli uporabila za začetek tega sklopa več ker če sem odstraniti 5, potem bom jaz umaknil 7. Ampak sem samo dal ljudi v desno. 

Zdi se, kot da zapravljam prostor, in na koncu sem čakalne vrste razpade v nič na vse, tako da smo lahko samo še ljudje blatnikov, in lahko si mislimo o tem polju res kot neke vrste krožno strukturo, toda kaj bomo uporabili operator v C storiti, da se takšne blatnikov? [Neslišno študentski odziv] >> operator modula. To bi bilo malo neprijetno, da misliš na kako narediti blatnikov, vendar bi to počnemo, in smo lahko začeli postavi ljudi kaj je bilo sprednji strani linije, ampak zapomni si s tem glave spremenljivke, ki so dejanski vodja linije dejansko je. Kaj, če bi namesto tega, naš cilj na koncu, čeprav, je, da pogledate številke, kot smo tukaj na odru z Anito, ampak res želimo najboljši od vseh teh svetovih? Želimo bolj prefinjena kot matrika omogoča ker želimo, sposobnost za dinamično rast podatkovno strukturo. Toda mi ne želimo zateči na nekaj, kar smo poudarili V prvem predavanju ni bil optimalen algoritem, da linearnega iskanja. Izkazalo se je, da lahko dejansko dosežejo ali vsaj blizu konstantno časa, po katerem nekdo, kot Anita, če bi nastavi svojo podatkovno strukturo, ne da bi povezani seznam, Ne bi smel biti dimnik, da ni čakalne vrste, lahko v resnici, prišli do podatkov strukturo, ki ji omogoča, da poiščete stvari, niti besede, ne samo številke, v čem bomo poklicali stalno čas. 

In v resnici v prihodnje ena od psets v tem razredu je skoraj vedno Izvajanje črkovalnik, pri čemer smo vam še nekaj 150.000 angleških besed in cilj je, da obremenitev so v spomin in hitro lahko odgovorili na vprašanja v obliki ta beseda pravilno napisano? In bi bilo res zanič, če si imel za ponovitev prek vseh 150.000 besed, da odgovorim na to. Toda v resnici, bomo videli, da bomo lahko to storite v zelo, zelo hitrem času. In to se dogaja, da gre za izvajanje nekaj, kar ti razpršena tabela, in čeprav je na prvi pogled ta stvar imenovano razpršena tabela se bo nam dosego teh super hitre odzivne čase, Izkazalo se je, da je v resnici problem. Ko pride čas za izvedbo to stvar, imenovano, še enkrat, to počnem še enkrat. Jaz sem edini tukaj. Ko pride čas za izvajanje te stvar imenovano razpršena tabela, bomo morali odločiti. Kako velika je ta stvar je dejansko bilo? In ko smo začeli vstavljanje številke v tem hash tabele, Kako bomo, da jih shrani na tak način, da bomo lahko dobili nazaj tako hitro, kot smo jih dobili? Ampak bomo videli kmalu, da je to vprašanje Ko bodo vsi rojstni dan je v skupini bo zelo upoštevna. Izkazalo se je, da je v tej sobi, imamo nekaj sto ljudi, tako da je verjetnost, da sta dva izmed nas ima enako rojstni dan, je verjetno precej visoka. Kaj pa, če je bilo le 40 nas je v tej sobi? Kakšne so možnosti, dveh ljudi, ki imajo isti rojstni dan? [Dijaki] Več kot 50%. Ja, več kot 50%. Pravzaprav sem celo prinesel grafikon. Izkazalo se je, in to je res samo hiter predogled- če pa je samo 58 nas je v tej sobi, je verjetnost, da nas je 2 ima enako rojstni dan, je zelo visoka, skoraj 100%, in da se bo to povzročilo kup bolelo za nas v sredo. 

S tem je dejal, gremo prekine tukaj. Se vidimo v sredo. [Aplavz] [CS50.TV]