[Powered by Google Translate] [6. dio] [udobnije]
[Rob Bowden] [Sveučilište Harvard]
[Ovo je CS50.] [CS50.TV]
>> Možemo krenuti na našem dijelu pitanja.
Poslala sam URL za prostor prije.
Početak dijelu pitanja kažu-
očito nisam posve unsick-je vrlo jednostavno pitanje
samo ono što je valgrind?
Što valgrind učiniti?
Svatko tko želi reći ono što valgrind ne?
[Studentski] Provjerava memory leaks.
Da, valgrind je opća memorija provjeru.
To je, na kraju, govori vam ako imate bilo kakve memory leaks,
koja je uglavnom ono što smo ga koristiti za, jer ako želite
činiti dobro u problematiku set ili ako želite
doći na velikom brodu, morate imati nikakvih memory leaks god,
te u slučaju da imate memorijsku curenje koje ne možete naći,
Također imajte na umu da kad god otvorite datoteku
a ako ga ne zatvorite, to je gubljenje memorije.
>> Puno ljudi koji su u potrazi za nekim čvor da oni ne oslobađaju
kad stvarno, nisu zatvorili rječnika u prvom koraku.
Također će vas obavijestiti ako imate bilo nevažeća čita ili piše,
što znači da ako i pokušati postaviti vrijednost
to je izvan kraja hrpi i to se ne dogodi da SEG krivnjom
ali valgrind ga hvata, kao što ne bi zapravo trebala biti pisanje tamo,
i tako da definitivno ne bi trebali imati bilo koji od onih bilo.
Kako koristiti valgrind?
>> To je opće pitanje
vrsta pokrenite ga i pogledati na izlazu.
Izlaz se opteretimo puno vremena.
Tu je i zabava pogreške gdje, ako imate neke strašno krivu stvar
događa u petlji, onda će na kraju reći, "Put previše pogrešaka.
Ja ću prestati računajući sada. "
To je u osnovi tekstualni izlaz da morate analizirati.
Na kraju, to će vam reći nikakve memory leaks koje imate,
koliko blokova, što može biti korisno jer
ako je jedan blok unfreed, onda je obično lakše pronaći
od 1.000 blokovi unfreed.
1000 blokira unfreed vjerojatno znači da ne oslobađaju
Vaši povezani popisi primjereno ili nešto.
To je valgrind.
>> Sada imamo dio pitanja,
koji vam ne treba preuzeti.
Možete kliknuti na ime moje te ih podići u prostoru.
Sada kliknite na mene.
Revizija 1 će biti stog, koji radimo na prvom mjestu.
Revizija 2 će biti red, a Revizija 3 će biti pojedinačno povezani popis.
Počevši s našim stog.
Kao što kaže ovdje, stog je jedna od najosnovnijih,
temeljne strukture podataka računalne znanosti.
Vrlo prototipski primjer je
stog ladica u blagovaonici.
To je u osnovi kad god se uvode na hrpu,
netko će reći: "Oh, kao hrpom ladica."
Vi stog ladice gore.
Onda kada idete na izvući ladicu,
prva ladica da je dobivanje povukao je posljednji onaj koji je stavljen na stog.
Stog je također poput njega kaže ovdje-
imamo segment memorije zove stog.
A zašto se to zove stog?
>> Jer kao strukturu stog podataka,
gura i pops stog okvire na stog,
gdje stog okviri su kao posebne pozivu funkcije.
I kao stog, uvijek ćete morati vratiti
od funkcija poziva prije nego što možete spustiti u niže stog okvire opet.
Vi ne možete imati glavnu poziva foo poziva bar i bar povratak na glavni izravno.
Uvijek je dobio slijediti ispravan snop gura i iskakanje.
Dvije operacije, kao što sam rekao, su guranje i pop.
Oni su univerzalni pojmovi.
Ti bi trebao znati gurati i pop u smislu hrpe bez obzira što.
Vidjet ćemo redovi su vrste drugačiji.
To ne stvarno imati univerzalni pojam, ali guranje i pop su univerzalni za hrpe.
Push je samo staviti na stog.
Pop je skinuti hrpu.
I ovdje vidimo imamo typedef struct stog,
tako da imamo char ** konce.
Nemojte se bojati bilo kakvim **.
To će završiti kao niz stringova
ili niz strelicama znakova, gdje
upućuje na likovima imaju tendenciju da se žice.
To ne mora biti nizovi, ali ovdje, oni će biti nizovi.
>> Imamo niz žice.
Imamo veličine, što predstavlja koliko elementi su trenutno na stog,
i onda imamo kapacitet, koji je koliko elementi mogu biti na stog.
Kapacitet bi trebao krenuti kao nešto veće od 1,
ali veličina će krenuti kao 0.
Sada, u osnovi postoje tri različita načina na koje se možete sjetiti hrpu.
Pa, tu su vjerojatno i više, ali su dva glavna načina su
možete ga realizirati pomoću niz, ili ga možete provesti pomoću povezanog popisa.
Povezani su popisi vrsta trivijalno napraviti hrpe od.
To je vrlo lako napraviti hrpu koristeći povezane liste,
pa evo, idemo napraviti stog pomoću polja,
, a zatim pomoću polja, tu je i dva načina na koje možete razmišljati o tome.
Prije, kad sam rekao da ćemo imati kapacitet za stog,
tako da možemo stati element na stog.
>> Jedan način bi se moglo dogoditi je čim pogodio 10 elemenata, onda ste gotovi.
Možda znate da postoji gornja granica od 10 stvari na svijetu
da nikada nećete imati više od 10 stvari na hrpu,
u kojem slučaju možete imati gornju granicu o veličini vašeg stog.
Ili ste mogli imati svoj stack biti bezgranični,
ali ako radite niz, to znači da svaki put kada pogodak 10 elemenata,
onda ćeš morati rasti do 20 elemenata, a kada hit 20 elemenata,
ćete morati razviti svoje niz od 30 elemenata ili 40 elemenata.
Ti si idući u morati povećati kapacitete, što je ono što ćemo učiniti ovdje.
Svaki put kad smo postići maksimalnu veličinu našeg dimnjaka,
kad smo gurnuti nešto drugo, mi ćemo morati povećati kapacitete.
Evo, mi smo pritisak proglašen bool pritiskom (char * str).
Char * str je niz koji smo pritom na stog,
i bool samo kaže da li smo uspjeli ili nije.
>> Kako možemo uspjeti?
Što je samo okolnost da se možete sjetiti
gdje smo trebale bi se vratiti lažno?
Da.
[Studentski] Ako je puna, a mi smo pomoću omeđeno provedbu.
Da, pa kako smo definirali-on je odgovorio
ako je puna, a mi smo pomoću omeđen provedbu.
Tada ćemo definitivno vratiti false.
Čim smo pogodak 10 stvari u polju, ne možemo stati 11, tako da smo se vratili lažna.
Što ako je neograničeno? Da.
Ako ne možete proširiti lepezu iz nekog razloga.
Da, tako je memorija ograničen resurs,
i na kraju, ako ćemo gurati stvari na hrpu iznova i iznova,
idemo pokušati izdvojiti veću lepezu da stane
veći kapacitet, a malloc ili što god koristite će se vratiti false.
Pa, malloc će se vratiti null.
>> Zapamtite, svaki put ste ikada nazvati malloc, te bi trebao biti ček vidjeti ako to
vraća null ili što drugo što je korektnost odbitak.
Budući da želimo imati neograničen stog,
jedini slučaj da ćemo se vratiti lažna je, ako ćemo pokušati
povećati kapacitet i malloc ili što god false.
Zatim pop traje nema argumenata,
i vraća niz koji je na vrhu stoga.
Što god je nedavno gurnuo na stog je ono što pop vraća,
i to također uklanja ga iz dimnjaka.
I primijetiti da se vraća null ako ne postoji ništa na stog.
Uvijek je moguće da stog je prazan.
U Java, ako ste navikli na to, ili drugim jezicima,
pokušavajući pop iz prazne stog može uzrokovati iznimku ili nešto.
>> Ali u C, null je vrsta puno slučajeva kako ćemo obraditi tih problema.
Povratak null kako ćemo značiti da stog je prazan.
Osigurali smo kod koji će testirati vaše stog funkcionalnost,
provoditi gurati i pop.
To neće biti puno koda.
Hoću-zapravo, prije nego što smo to učinili, hint, hint-
ako niste vidjeli, malloc nije jedina funkcija
koje dodjeljuje memoriju na hrpi za vas.
Postoje obitelj alloc funkcija.
Prvi je malloc, koji ste navikli.
Zatim tu je calloc, koja čini istu stvar kao malloc,
ali to će nulu sve za vas.
Ako ste ikada željeli postaviti sve na nulu nakon mallocing nešto
trebali imati samo koristi calloc na prvom mjestu, umjesto pisanja
za petlje na nulu iz cijelog blok memorije.
>> Realloc je kao malloc i ima puno posebnim slučajevima,
ali u osnovi ono što realloc ipak
to traje pokazivač koji su već bili dodijeljeni.
Realloc je funkcija želite biti plaćati pozornost ovdje.
Potrebno je pokazivač koji je već bio vratio iz malloc.
Recimo da zatraži od malloc pokazivač od 10 bajtova.
Onda kasnije ste shvatili ste htjeli 20 bajtova,
tako zoveš realloc na tom pointer s 20 bajtova,
i realloc će automatski kopirati nad svime za vas.
Ako ste upravo zove malloc opet, kao da imam paket od 10 bajtova.
Sada trebam blok 20 bajtova,
pa ako sam malloc 20 bajtova, onda moram ručno kopirati preko 10 bajtova iz prvog stvar
u drugoj stvar, a zatim bez prva stvar.
Realloc će nositi za vas.
>> Obavijest potpis će biti nevažeće *,
koji je samo vraća pokazivač na blok memorije,
onda void * ptr.
Možete misliti void * kao generički pokazivač.
Općenito, nikada se bave void *,
ali malloc se vraća void *, a zatim je to samo koristi kao
ovo je zapravo će biti char *.
Prethodni void * koji je vraćen od strane malloc
sada će biti donesen do realloc, a zatim veličina
je novi broj bajtova koje želite izdvojiti, tako da vaš novi kapaciteti.
Ja ću vam dati par minuta, i to u našem prostoru.
Počnite s jednom reviziji.
Ja ću vas zaustaviti nakon nadamo se o dovoljno vremena za provedbu gurati,
i onda ću vam dati još jednu pauzu za napraviti pop.
No, to stvarno nije toliko kod uopće.
Najviše kod je vjerojatno širi stvari, proširenje kapaciteta.
Ok, nema pritiska da se u potpunosti biti učinjeno,
ali dokle god se osjećate kao da ste na pravom putu, to je dobro.
>> Se bilo tko imati bilo kod oni osjećaju ugodno sa mnom povlačenjem gore?
Da, hoću, ali ne bilo tko imati bilo kod mogu podići?
Ok, možete početi, spasiti ga, bez obzira na to je?
Ja uvijek zaboraviti taj korak.
Ok, gleda pritiskom,
Ne želite da objasni svoj kod?
[Studentski] Prije svega, sam povećao veličinu.
Mislim možda bih trebao imati da-ionako sam povećao veličinu,
i vidim da je to manje od kapaciteta.
A ako je to manje od kapaciteta, sam dodati polje koje već imate.
A ako nije, ja pomnožite kapacitet 2,
i ja preraspodijeliti konce niz na nešto s većim kapacitetom veličine sada.
A onda, ako to ne uspije, kažem korisnika i povratak false,
i ako je to u redu, onda sam stavio tekst u novom mjestu.
>> [Rob B.] Također primijetite da smo koristili lijepu bitovni operator ovdje
kako pomnožiti dva.
Zapamtite, lijevo pomak uvijek će biti pomnožen dva.
Pravo pomak je podijeljena po dva dokle god sjetite se da to znači
podijeliti po dva, kao u cijeli podijeljena dva.
To bi moglo skratiti na jednom ovdje ili ondje.
No, pomak je ostavio jedan uvijek će biti pomnožen 2,
osim ako se prelijevati granice na cijeli broj, a zatim ga neće biti.
Strana komentar.
Volim učiniti-to se neće promijeniti kodiranje bilo koji način,
ali ja bih to učiniti ovako nešto.
To se zapravo događa da bi ga nešto duže.
Možda ovo nije savršena slučaj pokazati,
ali ja bih ga u segmentu tih blokova-
ok, ako je to ako se dogodi, onda ću učiniti nešto,
, a zatim je funkcija učinio.
Ne trebam se onda dođite moje oči skroz funkciji
da vidi što se događa nakon drugog.
To je, ako to, ako se dogodi, onda sam se vratiti.
Ona također ima lijepu dodatnu korist od svega iznad ovog
sada se pomaknuo lijevo jednom.
Ja više ne treba-ako ikad blizini smiješno dugi redovi,
onda one 4 bajta mogu pomoći, ali i više lijevo nešto,
manje osvaja se osjećate ako želite-ok, moram se sjetiti
Ja sam trenutno u while petlji unutar nekog drugog unutrašnjosti za petlje.
Bilo gdje možete to učiniti odmah vratiti, nekako ovako.
To je potpuno opcionalno i ne očekuje se na bilo koji način.
>> [Studentski] Ako postoji veličina - u negativne stanju?
Negativne stanje ovdje se nismo uspjeli realloc, tako da.
Obavijest o tome kako u negativne stanju, vjerojatno,
osim ako smo free stuff kasnije, mi smo uvijek idemo na propast
bez obzira koliko puta ćemo pokušati gurnuti nešto.
Ako ćemo gurati, držimo povećavanjem veličine,
iako mi se ne stavlja ništa na stog.
Obično mi ne povećajte veličinu do
nakon uspješno smo ga stavili na stog.
Mi bi to, recimo, bilo ovdje i ovdje.
I onda, umjesto da se kaže s.size ≤ kapacitet, to je manje od kapaciteta,
samo zato što smo se preselili u kojoj je sve bilo.
>> I zapamtite, jedino mjesto koje bi moglo vratiti false
je ovdje, gdje realloc vratio null,
a ako vam se dogoditi da zapamtite standardnu ​​pogrešku,
možda razmislite ovaj slučaj gdje želite ispisati standardnu ​​pogrešku,
tako fprintf stderr umjesto da samo tiskanje izravno na standardne van.
Opet, to nije očekivanja, ali ako je to pogreška,
upišite printf, onda možda želite da bude ispis na standardnom pogreškom umjesto standardnog van.
>> Svatko ima nešto drugo na bilješku? Da.
[Studentski] Mogu li ići preko [nečujnog]?
[Rob B.] Da, stvarni binariness od njega ili samo što je to?
[Studentski] Pa ste ga pomnožiti sa 2?
[Rob B.] Da, u osnovi.
U binarnom zemlji, mi uvijek imamo niz znamenki.
Pomak ovaj lijevo od 1 Uglavnom umeće ovdje na desnoj strani.
Natrag na to, samo sjećanja da je sve u binarnom
je snaga 2, pa to predstavlja 2 do 0,
to 2 do 1, ova 2 2.
Umetanjem 0 do sada desnoj strani, samo smo pomak sve više.
Ono što se 2 do 0 je sada 2 do 1, je 2 do 2.
Na desnoj strani da smo umetnuta
nužno će biti 0,
što ima smisla.
Ako ste ikada pomnožite broj po dva, to neće završiti čudno,
pa 2 u 0 mjesto treba biti 0,
i to je ono što sam polovina upozorio prije nego što je, ako ti se dogoditi da smjeni
iznad broja bitova u cijeli broj,
onda je ovo jedan će završiti ide off.
To je jedina zadaća ako vam se dogoditi da se bave stvarno velikih kapaciteta.
No, u tom trenutku, onda ste se bave s nizom milijardama stvari,
koji se ne može uklopiti u memoriju svejedno.
>> Sada možemo doći do popa, koji je čak i lakše.
Ti bi mogao to ne sviđa, ako vam se dogoditi da pop hrpu,
a sada ste na pola kapaciteta ponovno.
Ti bi mogao realloc smanjiti količinu memorije imate,
ali ne morate brinuti o tome, tako da samo realloc slučaj će biti
raste memorije, nikada smanjuje memoriju,
koji će napraviti pop super jednostavno.
Sada redovi, koji će biti poput dimnjaka,
ali kako da vam se stvari obrnuta.
Prototipski primjer red je red,
tako da mislim da ako su engleski, rekao bih
prototipski primjer red je red.
Dakle, kao što su linije, ako si prva osoba u liniji,
vi očekujete da će biti prva osoba izvan linije.
Ako ste posljednja osoba u liniji, što će biti posljednja osoba servisirati.
Zovemo da FIFO uzorak, dok stog je LIFO uzorak.
Te riječi su prilično univerzalno.
>> Kao dimnjaka i za razliku od polja, redovi obično ne dopuštaju pristup elementima u sredini.
Evo, stog, imamo gurati i pop.
Evo, mi se dogoditi da su ih zvali enqueue i dequeue.
Također sam čuo da ih se zove pomak i unshift.
Ja sam čuo da su ljudi kažu guranje i pop također primijeniti na redu.
Čuo sam umetanje, uklanjanje
tako gurati i pop, ako govorimo o dimnjaka, te su pritom i iskakanje.
Ako govorimo o redovima, mogli odabrati riječi koje želite koristiti
za umetanje i uklanjanje, i ne postoji konsenzus o tome što bi trebao biti pozvan.
Ali ovdje, imamo enqueue i dequeue.
Sada, struct izgleda gotovo identičan stog struct.
No, moramo pratiti glave.
Pretpostavljam da kaže ovdje dolje, ali zašto trebamo glavu?
U prototipovi su u osnovi identičan guranje i pop.
Možete misliti o njemu kao guranje i pop.
Jedina razlika je pop vraća-umjesto zadnji, to je povratak na prvom mjestu.
2, 1, 3, 4, ili nešto.
I ovdje je početak.
Naš je red potpuno pun, tako da je četiri elementi u njemu.
Kraj našeg redu je trenutno 2,
a sada idemo ubaciti nešto drugo.
>> Kada želimo umetnuti tu nešto drugo, ono što smo učinili za stog verziji
je smo proširili naš blok memorije.
Što je problem s tim?
[Studentski] Možete premjestiti dvije.
Ono što sam rekao prije o kraju reda,
to nema smisla da mi početi na jedan,
onda želimo dequeue 1, onda dequeue 3, onda dequeue 4,
onda dequeue 2, zatim dequeue ovaj jedan.
Mi ne možemo koristiti realloc sada,
ili barem, morate koristiti realloc na drugačiji način.
Ali vjerojatno ne bi trebala koristiti realloc.
Vi ćete morati ručno kopirati svoju memoriju.
>> Postoje dvije funkcije za kopiranje memorije.
Tu je memcopy i memmove.
Ja sam trenutno čitate man stranice kako bi vidjeli koje ćete želite koristiti.
Ok, memcopy, razlika je
da memcopy i memmove, jedan obrađuje slučaj ispravno
gdje ste kopirate u regiji koja će se dogoditi da se preklapaju regiju
ti si kopirate iz.
Memcopy ga ne obrađuju. Memmove radi.
Možete misliti o tom problemu kao-
recimo želim kopirati ovog tipa,
ove četiri ovom tipu više.
Na kraju, što je polje treba izgledati
nakon je kopija 2, 1, 2, 1, 3, 4, a zatim neke stvari na kraju.
No, to ovisi o redoslijedu u kojem smo zapravo kopirati,
jer ako mi ne uzeti u obzir činjenicu da je regija smo kopiranje u
preklapa jedan smo od kopiranja,
tada smo mogli učiniti kao početak ovdje, kopiranje 2 na mjestu želimo ići,
zatim premjestiti naše naputke naprijed.
>> Sada ćemo biti ovdje i ovdje, a sada želimo kopirati
ovaj tip nad ovim tipom i premjestiti naše naputke naprijed.
Što ćemo završiti uzimajući je 2, 1, 2, 1, 2, 1
umjesto odgovarajućeg 2, 1, 2, 1, 3, 4, jer
2, 1 overrode izvorni 3, 4.
Memmove ručke da ispravno.
U tom slučaju, u osnovi samo uvijek koristiti memmove
jer ga obrađuje ispravno.
To općenito ne izvrši bilo još gore.
Ideja je umjesto počevši od početka i kopiranje na ovaj način
kao što smo upravo učinili ovdje, ona počinje od kraja i kopira u,
iu tom slučaju, nikada ne možete imati problema.
Tu se ne performanse izgubio.
Uvijek koristite memmove. Nikad brinuti o memcopy.
I to je mjesto gdje ćete morati zasebno memmove
omotan oko-dio svojem redu.
Bez brige, ako ne i potpuno učinjeno.
To je teže nego stog, gurati i popa.
>> Bilo tko imati bilo kod bismo mogli raditi s?
Čak i ako potpuno nepotpuna?
[Studentski] Da, to je sasvim nepotpuna, iako.
Potpuno nepotpuna je u redu dokle god-možete uštedjeti reviziju?
Zaboravio sam da svaki put.
Ok, ignorirajući što se događa kada trebamo veličinu stvari.
Potpuno zanemariti veličinu.
Objasni ovaj kod.
Odjavljujem ponajprije ako je veličina manja od kopirati ponajprije
i onda nakon toga, ja umetnuti-uzmem glavu + veličina,
i ja bi bili sigurni da omata svojstvu polja,
i ja umetnuti novi string na toj poziciji.
Tada sam povećati veličinu i povratak istina.
>> [Rob B.] Ovo je definitivno jedan od onih slučajeva gdje idete da želite koristiti mod.
Bilo koja vrsta slučaju gdje ste omatanje oko, ako mislite da umatanje okolo,
Neposredna misao bi trebao biti mod.
Kao brzo optimizacije / učiniti vaš broj jedan redak kraći,
primijetite da linija odmah nakon ovog jednog
je samo veličina + +, tako da spojiti da u ovoj liniji, veličina + +.
Sada ovdje imamo slučaj
gdje nemamo dovoljno memorije,
tako da smo sve naše kapacitete 2.
Mislim da bi mogao imati isti problem ovdje, ali možemo ga ignorirati sada,
gdje ako nije povećati svoj kapacitet,
onda idete da želite smanjiti svoj kapacitet dvije opet.
Još jedan kratki napomena je baš kao i što možete učiniti + =,
također možete učiniti << =.
Gotovo sve što se može ići pred jednakima, + =, | =, & =, << =.
Char * nova je naš novi blok memorije.
Oh, ovdje.
>> Što ljudi misle o vrsti našeg novog bloka memorije?
[Studentski] To bi trebao biti char **.
Osvrčući se na naš struct ovdje,
žice je ono što mi se preraspodjelom.
Mi smo stvaranje cijeli novi dinamičan prostor za pohranu elemenata u redu.
Što ćemo se dodjeljuje za svoje žice je ono što smo mallocing upravo sada,
i tako nova će biti char **.
To će biti niz žice.
Onda što je slučaj u kojem ćemo se vratiti lažno?
[Studentski] Hoćemo li se radi char *?
[Rob B.] Da, dobro poziv.
[Studentski] Što je to?
[Rob B.] Željeli smo napraviti veličinu char * jer mi se više ne-
to bi zapravo biti vrlo veliki problem jer sizeof (char) će biti jedan.
Sizeof char * će biti 4,
tako puno vremena kada ste se bave Ints,
imaju tendenciju da biste dobili daleko s njom, jer veličina int i veličinom int *
na 32-bitni sustav će biti ista stvar.
Ali ovdje, sizeof (char) i sizeof (char *) sada će biti ista stvar.
>> Što je okolnost gdje smo se vratili lažna?
[Studentski] Novi null.
Da, ako se novi null, vraćamo lažna,
i ja ću baciti ovdje dolje-
[Studentski] [nečujan]
[Rob B.] Da, to je u redu.
Ili bi mogao napraviti dva puta kapaciteta ili kapaciteta Shift 1 i tek onda ga postaviti ovdje ili što god.
Mi ćemo to učiniti kao što smo ga imali.
Kapacitet >> = 1.
I nikada si idući u morati brinuti o gubljenja jednom je mjesto
zato što je napustio pomaknut za jedan, tako da je jedan u mjesto je nužno 0,
pa upravo kreće prema jednoj, još uvijek ćeš biti u redu.
[Studentski] Da li je potrebno učiniti da se prije povratka?
[Rob B.] Da, to ga čini apsolutno nikakvog smisla.
>> Sada pretpostavimo da ćemo završiti povratka istina do kraja.
Način ćemo to učiniti ovih memmoves,
moramo biti oprezni s koliko smo ih učiniti.
Se bilo tko imati bilo kakve prijedloge kako bismo ih učiniti?
Evo naš početak.
Neizbježno, želimo početi početkom opet
i kopirati stvari u od tamo, 1, 3, 4, 2.
Kako ćete to učiniti?
Prvo, moram gledati na čovjeka stranici za memmove opet.
Memmove, kako od argumenata je uvijek važno.
Želimo naše odredište prvi, drugi izvor, veličina treći.
Postoji puno funkcija koje obrnutom izvor i odredište.
Odredište, izvor teži biti dosljedni nešto.
Pokret, što je to vraća?
To vraća pokazivač na odredište, iz bilo kojeg razloga možda želite da.
Ja mogu sliku to pročitao, ali želimo da se presele u naše odredište.
>> Što se naše odredište će biti?
[Studentski] Novi.
[Rob B.] Da, a gdje smo kopiranje iz?
Prva stvar koju smo kopiranje je to 1, 3, 4.
Što je to-1, 3, 4.
Što je adresa ovog jednog?
Što je adresa tog jednog?
[Studentski] [nečujan]
[Rob B.] Visina + adresu prvog elementa.
Kako smo dobili prvi element u nizu?
[Studentski] red.
[Rob B.] Da, q.strings.
Zapamtite, ovdje, naš šef je jedan.
To prokleto. Ja samo mislim da je magično-
Evo, naš šef je jedan. Ja ću promijeniti moje boje previše.
I ovdje je žice.
Ovaj, mi može pisati kao što smo učinili ovamo
s glave + q.strings.
Puno ljudi također pisati ga i q.strings [glava].
To zapravo i nije bilo manje učinkovit.
Vi možda mislite o njemu kao što su to dereferencing a zatim uzimajući adresu,
ali prevodilac će prevesti ga na ono što smo imali prije svejedno, q.strings + glava.
U svakom slučaju želim razmišljati o tome.
>> A koliko bajtova želimo kopirati?
[Studentski] Kapacitet - glava.
Kapacitet - glava.
I onda uvijek možete napisati primjer
shvatiti ako je to točno.
[Studentski] To treba biti podijeljen po dva tada.
Da, tako da mislim da bi mogao koristiti veličinu.
Mi još uvijek imamo veličinu bivanja-
koristeći veličinu, imamo veličinu jednak 4.
Naša veličina je 4. Naša glava je jedna.
Mi želimo kopirati ove tri elementa.
To je razum provjeriti da veličina - glava je točno tri.
I vraća ovdje, kao što smo već rekli,
ako ćemo koristiti kapacitete, onda ćemo morati podijeliti po dva
jer smo već narasla naše sposobnosti, pa umjesto toga, mi ćemo koristiti veličinu.
Da primjeraka tog dijela.
Sada, moramo kopirati druge dio, dio koji je ostao od samog početka.
>> To će memmove u kojoj poziciji?
[Studentski] plus size - glava.
Da, tako smo već kopiraju u veličini - glave bajtova,
pa gdje želimo kopirati preostale bajtova je novo
i onda veličina minus dobro, broj bajtova smo već kopirati u.
I onda gdje smo kopiranje iz?
[Studentski] Q.strings [0].
[Rob B.] Da, q.strings.
Mi ni mogao učiniti i q.strings [0].
To je znatno rjeđi nego ovo.
Ako je to samo će biti 0, onda ćete skloni vidjeti q.strings.
To je mjesto gdje smo kopirate iz.
Koliko bajtova mi ostavili kopirati? >> [Studentski] 10.
Točno.
[Studentski] Ne moramo pomnožiti 5-10 puta veći od bajtova ili nešto?
Da, tako je to u kojoj-točno ono što smo kopiranje?
[Studentski] [nečujan]
Što je vrsta stvar smo kopiranja?
[Studentski] [nečujan]
Da, tako char * a da smo kopiranje, ne znamo gdje su oni koji dolaze iz.
Pa, gdje su oni ističući da, kao što su žice, mi završiti ga gura na čekanju
ili enqueuing na red.
Gdje oni dolaze iz, nemamo pojma.
Mi samo trebamo pratiti na char * s sebe.
Mi ne želimo kopirati veličinu - glava bajtova.
Mi želimo kopirati veličinu - glava char * s,
tako da ćemo pomnožiti to sizeof (char *).
Sve ovdje dolje, glava * sizeof (char *).
>> [Studentski] Što o [nečujan]?
Ovo ovdje?
[Studentski] Ne, ispod toga, veličina - glava.
[Rob B.] Ovo ovdje?
Pointer aritmetika.
Kako pokazivač aritmetika ide na posao je
automatski umnožava po veličini vrsti da smo se bave.
Baš kao i ovdje, nova + (veličina - glava)
je točno odgovara i novi [veličini - glave]
dok očekujemo da se radi ispravno,
jer ako imamo posla s int niz, onda mi ne indeks int-
ili ako je veličine od 5 i želite četvrti element, onda ćemo indeks u
int array [4].
Vi nemojte-[4] * veličina int.
To ga obrađuje automatski, a ovaj slučaj
je doslovno ekvivalent, tako da nosač sintaksa
samo ide da se pretvaraju da to čim sastaviti.
To je nešto što morate biti oprezni da
kada se dodavanjem veličinu - glava
dodajete niti jedan bajt.
Ti si dodao jedan char *, što može biti jedan bajtova ili bilo što drugo.
>> Ostala pitanja?
Ok, dequeue će biti lakše.
Ja ću vam dati minutu za provedbu.
Oh, i mislim da je to ista situacija gdje
što Postavi u red slučaj, ako ćemo enqueuing null,
možda ga želimo nositi, možda mi ne.
Nećemo to učiniti opet ovdje, ali isto kao i naš stack slučaju.
Ako smo enqueue null, možda bismo željeli da ga zanemarite.
Svatko ima neki kod ja mogu podići?
[Studentski] Imam samo dequeue.
Verzija 2 je da-ok.
Želite li objasniti?
[Studentski] Prvo, pobrinite se da je nešto u redu
te da je veličina ide dolje do 1..
Morate to učiniti, a onda se vratiti u glavu
a zatim premjestiti glavu 1.
Ok, tako da je kut slučaj moramo uzeti u obzir. Da.
[Studentski] Ako vam je glava na zadnji element,
onda ne želite glave do točke izvan polja.
>> Da, tako čim glavu pogodi kraj našeg polja,
kad smo dequeue, naša glava treba biti modded natrag na 0.
Nažalost, ne možemo to učiniti u jednom koraku.
Valjda put bih vjerojatno popraviti je
ovo će biti char *, ono što smo se vraćaju,
bez obzira na vaše ime varijable želi biti.
Tada želimo mod glavu po našoj sposobnosti
, a zatim se vratiti u mirovini.
Puno ljudi ovdje bi mogli učiniti-
ovo je slučaj-Vidjet ćeš ljudi učiniti ako glava
je veća od kapaciteta, učiniti glavu - kapacitet.
A to je upravo ono što rade oko mod je.
Šef mod = kapacitet je mnogo čišći
od omota oko nego ako glava veća od kapaciteta glave - kapacitet.
>> Pitanja?
Ok, zadnja stvar koju smo ostavili je naš linked list.
Možda će se koristiti za neke od povezanog popisa ponašanja ako nisi
povezane liste u svojim hash tablica, ako je hash tablicu.
Ja čvrsto preporučujem radi hash tablicu.
Možda već učinio trie,
ali pokušava teže.
U teoriji, oni su asimptotski bolje.
No, samo pogled na velikom brodu,
i pokušava nikada učiniti bolje, i oni zauzimaju više memorije.
Sve o pokušava završi kao gore za više rada.
To je ono Davida Malan je rješenje uvijek je
Je li uvijek postove njegov trie rješenje, pa da vidimo gdje je trenutno.
Ono što je on pod, David J?
On je # 18, tako da nije strašno loše,
i da će biti jedan od najboljih pokušava možete misliti
ili jedan od najboljih pokušava od trie.
Je li to nije ni njegov izvorni rješenje?
Osjećam se kao trie rješenja imaju tendenciju da se više u tom rasponu RAM korištenja.
>> Idi dolje na samom vrhu, a RAM-a običaj je u jednoznamenkaste.
Idite prema dolje na dnu, a onda početi dobivati ​​pokušava
gdje ćete dobiti apsolutno masivan RAM korištenje,
i pokušava teže.
Nije u potpunosti isplati, ali obrazovnog iskustva, ako ste učinili jednom.
Zadnja stvar je naša povezana lista,
i ove tri stvari, gomila, redovi i povezane liste,
svaki budući stvar koju je ikada učiniti u informatici
će preuzeti imate upoznati s tim stvarima.
Oni su samo tako temeljno za sve.
>> Povezani liste, a ovdje smo pojedinačno povezani popis će biti naša provedba.
Što pojedinačno ne znači povezati, za razliku od dvostruko povezani? Da.
[Studentski] To samo ukazuje na sljedeću pokazivač nego na pokazivače,
poput onog koji prethodi ga i jedan nakon njega.
Da, tako je u format slike, što sam samo učiniti?
Imam dvije stvari. Imam sliku i sliku.
U format slike, naši pojedinačno povezani popisi,
neizbježno, imamo nekakav pokazivač na čelu naše liste,
i onda u roku našem popisu, samo moramo upućuje,
a možda to ukazuje na nulu.
To će biti vaš tipičan crtež pojedinačno povezane liste.
Dvostruko povezana lista, možete ići unatrag.
Ako sam vam dati bilo kakve čvor na popisu, onda nužno može doći do
bilo koji drugi čvor u listu ako je dvostruko povezana popis.
Ali, ako sam ti treći čvor u popisu i to je pojedinačno povezani popis,
ni na koji način ste ikada idući u dobiti u prvom i drugom čvorova.
I tu je prednosti i detriments, a jedan očigledan jedan
je li zauzimaju više veličina, a vi morate pratiti gdje su te stvari okrenuti sada.
Ali mi samo stalo pojedinačno povezani.
>> Prije nekoliko stvari koje smo si idući u morati provoditi.
Vaš typedef struct čvor, int i: struct node * next; čvor.
To typedef trebao biti spaljen u vašim umovima.
Kviz 1 treba mi dati typedef od povezanog popisa čvora,
i trebali biste biti u mogućnosti odmah piskarati da se razbije
čak i bez razmišljanja o tome.
Valjda par pitanja, zašto trebamo struct ovdje?
Zašto ne možemo reći čvor *?
[Studentski] [nečujan]
Da.
Jedina stvar koja definira čvor kao stvar
je typedef sama.
No, od ove točke, kad smo vrsta raščlanjivanjem kroz ove definicije struct čvora,
nismo završili naš typedef još, tako da od typedef nije završio,
čvor ne postoji.
Ali struct čvor radi, a to čvor ovdje,
to također može biti pozvan ništa drugo.
To bi se moglo nazvati n.
To bi se moglo nazvati linked popis čvor.
To bi se moglo nazvati ništa.
Ali to struct čvor treba da se zove isto kao ovaj struct čvora.
Ono što vi zovete to mora biti i ovdje,
i to tako da odgovara i na druge točke u pitanje
što je razlog zašto-puno puta kada vidite tvorevina i typedefs od tvorevina,
vidjet ćete anonimne tvorevina, gdje ćete samo vidjeti typedef struct,
Provedba struct, rječniku, ili bilo što drugo.
>> Zašto ovdje ne moramo reći čvor?
Zašto ne može biti anonimna struct?
To je gotovo isti odgovor.
[Studentski] Morate se odnosi na to unutar struct.
Da, unutar struct, trebate se odnose na struct sama.
Ako ne daju struct ime, ako je anonimni struct, ne može odnositi na njega.
I posljednje, ali ne i najmanje važno, to svi trebali biti nešto jednostavno,
i oni bi trebali pomoći da shvatite ako ste pisanje ove dolje
da radiš nešto krivo ako ovakve stvari nemaju smisla.
Posljednje, ali ne i najmanje važno, zašto to moraju biti struct node *?
Zašto ne može biti samo struct čvor sljedeći?
[Studentski] pointer na sljedeću struct.
To je neizbježno ono što želimo.
Zašto bi to nikada neće biti struct čvor sljedeći?
Zašto to mora biti struct node * sljedeći? Da.
[Studentski] To je kao beskonačnu petlju.
Da.
[Studentski] To će sve biti u jednom.
Da, samo mislim kako ćemo učiniti veličinu ili nešto.
Veličina od struct je u osnovi + ili - neki uzorak ovdje ili ondje.
To je u osnovi će biti zbroj veličina stvari u struct.
Ovo ovdje, bez mijenjanja išta, veličina će biti lako.
Veličina struct čvor će biti veličine i + veličine sljedeći.
Veličina ja će biti četiri. Veličina Sljedeća će biti četiri.
Veličina struct čvor će biti osam.
Ako mi nemamo *, misleći sizeof,
onda sizeof (i) će biti četiri.
Veličina struct čvor sljedeći će biti veličine i + veličina struct čvoru sljedeći
+ Veličina I + veličine struct čvora sljedeći.
To će biti beskonačan rekurzije čvorova.
To je razlog zašto je to kako se stvari moraju biti.
>> Opet, definitivno zapamtiti da,
ili barem to razumijem dovoljno da možete biti u mogućnosti
Razlog kroz ono što bi trebao izgledati.
Ono što mi idete da želite provesti.
Ako je duljina popisa-
mogli prevariti i držati oko
Globalna duljina ili tako nešto, ali nećemo to učiniti.
Mi ćemo računati na duljinu popisa.
Mi smo sadrži, tako da je u osnovi poput traženja,
tako smo povezani popis brojeva vidjeti ako ovaj broj je u povezane liste.
Upotrijebiti nesto će umetnuti na početku popisa.
Dodavanje će umetnuti na kraju.
Insert_sorted će umetnuti u poredani mjesta na popisu.
Insert_sorted vrsta pretpostavlja da nikada ne koristi upotrijebiti nesto ili dodati u loše načine.
>> Insert_sorted kada ste provedbi insert_sorted-
recimo imamo povezan popis.
To je ono što trenutno izgleda, 2, 4, 5.
Želim umetnuti tri, tako dugo dok popis sama već razvrstani,
to je lako pronaći gdje 3 pripada.
Ja početi u dva.
Ok, 3 veća od 2, pa želim zadržati ide.
Oh, 4 je prevelika, tako da znam tri će ići između 2 i 4,
i moram popraviti pokazivače i sve te stvari.
Ali ako nismo striktno koristiti insert_sorted,
sviđa neka je samo reći da sam upotrijebiti nesto 6,
onda je moj povezani popis će postati ovo.
Ona sada nema smisla, tako da za insert_sorted, možete samo pretpostaviti
da je popis sortiran, iako postoje operacije
što može uzrokovati da se ne razvrstani, i to je to.
Nađi pomogla umetak-tako i one su glavne stvari koje ćeš morati provesti.
>> Za sada, uzeti minutu učiniti duljinu i sadrži,
i one bi trebale biti relativno brzo.
Približavajući zatvaranja vremena, tako da svatko ima nešto za duljinu ili sadrži?
Oni će biti gotovo identičan.
[Studentski] Duljina.
Hajdemo vidjeti, reviziju.
Ok.
Želite li objasniti?
[Studentski] Ja samo stvoriti pokazivač čvor i inicijalizirati na prvi, koji je naša globalna varijabla,
i onda sam provjeriti da li je nulta tako da ne dobijete SEG kvar i vratiti 0 ako je to slučaj.
Inače, ja loop, praćenje roku cijeli
koliko sam puta pogledana sljedeći element liste
i u istom prirasta radu i pristup da stvarni element,
i onda sam stalno da provjere da li je ništavan,
i ako je nula, onda će se prekinuti i samo vraća broj elemenata sam pristupiti.
>> [Rob B.] Se bilo tko imati bilo kakve komentare o svemu?
Ovo izgleda fino ispravnost mudar.
[Studentski] Mislim da ne trebate čvor == null.
Da, pa ako čvor == null povratak 0.
Ali ako čvor == null onda je to-oh, tu je ispravnost problem.
To je bio samo ti ja vratiti, ali to nije u sklopu upravo sada.
Vi samo trebate int i, tako da sam = 0.
Ali ako čvor je nula, a zatim i dalje će biti 0,
i da ćemo se vratiti 0, tako da je ovo slučaj je identičan.
Još jedna zajednička stvar je da bi deklaraciju
od čvora unutar for petlje.
Moglo bi se reći-oh, ne.
Idemo ga zadržati što je ovaj.
Vjerojatno bih staviti int i = 0 ovdje,
onda čvor * čvor = prvi ovdje.
I to je vjerojatno kako-uzimajući osloboditi od ovaj sada.
To je vjerojatno kako bih ga napisao.
Ti bi mogao također-gleda na to ovako.
Ovo za petlje strukture ovdje
trebao biti gotovo kao prirodno da vas kao za int i = 0
i je manje od duljine niza i + +.
Ako je to kako se ponoviti tijekom niza, to je, kako se ponoviti više povezane liste.
>> Ovo bi trebao biti druga priroda u nekom trenutku.
Imajući to na umu, to će biti gotovo ista stvar.
Vi ćete želite ponoviti preko povezanu listu.
Ako čvor-ja nemam pojma što je vrijednost zove.
Ja čvora.
Ako je vrijednost u tom čvoru = ja povratak istina, i to je to.
Obavijest da je jedini način smo ikada vratiti false
je, ako ćemo ponoviti tijekom cijelog povezane liste i nikad se vratiti istina,
tako da je ono što ovaj radi.
Kao strani bilješku, mi vjerojatno neće doći do dodati ili upotrijebiti nesto.
>> Brza prošle bilješka.
Ako vidite statički ključnu riječ, pa recimo static int count = 0,
onda smo se računaju + +, te u osnovi mogu misliti o njemu kao globalne varijable,
iako sam samo rekao da to nije kako ćemo provesti duljinu.
Ja radim ovo ovdje, a zatim računati + +.
Bilo koji način možemo unijeti čvor u našoj povezanog popisa smo povećavanjem naše računati.
Poanta je to što je statična ključna riječ znači.
Ako sam imala int count = 0 da bi se redovito stara globalna varijabla.
Što static int count znači da je globalna varijabla za ovu datoteku.
Nemoguće je za neku drugu datoteku,
sviđa misliti pset 5, ako ste započeli.
Imate i speller.c, i imate dictionary.c,
i ako samo proglasiti stvar globalne, onda ništa u speller.c
može pristupiti u dictionary.c i obratno.
Globalne varijable su dostupne bilo. C datoteku,
ali statički varijable su dostupne samo unutar datoteke sama,
tako da unutar provjeru pravopisa ili unutar dictionary.c,
to je vrsta kako bih izjaviti moj varijablu za veličinu moje niz
ili veličina mog broja riječi u rječniku.
Budući da ne želim da se proglasi globalnu varijablu da svatko ima pristup,
Ja stvarno samo briga o tome za mojim vlastite svrhe.
>> Dobra stvar o tome je cijela ime sudara stvari.
Ako neki drugi file pokušava koristiti globalnu varijablu nazvanu count, stvari idu jako, jako krivo,
tako da je ovo lijepo drži stvari sigurno, i samo vi možete pristupiti,
i nitko drugi ne može, a ako netko izjavljuje globalnu varijablu nazvanu count,
onda to neće ometati vaše statičke varijable zove računati.
To je ono što je statična. To je datoteka globalna varijabla.
>> Pitanja o bilo čemu?
Sve skupa. Bok.
[CS50.TV]