[Powered by Google Translate] [Odjeljak 6: Manje Komforan]
[Nate Hardison] [Sveučilište Harvard]
[Ovo je CS50.] [CS50.TV]
U redu. Dobrodošli na sekciji šest.
Ovaj tjedan, idemo da se govori o strukturama podataka u odjeljku,
prvenstveno zato ovotjedni problema postaviti na spellr
ne cijela hrpa različitih struktura podataka istraživanja.
Postoji hrpa različitih načina na koje možete ići s problemom skup,
i više strukture podataka znate o, više cool stvari koje možete učiniti.
>> Dakle, neka je početi. Prvo ćemo govoriti o dimnjaka,
stog i red strukture podataka da ćemo razgovarati o tome.
Stacks i redovi su stvarno korisna kada smo počeli govoriti o grafovima,
što nećemo učiniti toliko upravo sada.
No, oni su jako dobro razumjeti jedan od velikih temeljnih podatkovnih struktura CS.
Opis u specifikaciji problema set,
ako ga podići, govori o stacks kao srodan
gomila blagovaona ladica da imate u kantini na blagovaonice
gdje kada blagovaonica osoblje dolazi i stavlja objedovanje ladica out nakon što ste ih čisti,
oni stog im jedan na vrhu druge.
A onda kad djeca dolaze u dobiti hranu,
oni povući ladice off, prvi vrhu jedan, onda onaj ispod njega, onda je jedan ispod toga.
Dakle, u stvari, prva ladica da blagovaonica osoblje spustio je zadnji koji se skida.
Posljednji da je osoblje staviti na dnevni je prvi koji se skida za večeru.
U Problem setu je spec., koji možete preuzeti ako već niste,
govorimo o modeliranju stucture stog podataka koristeći ovu vrstu struct.
>> Dakle, ono što imamo ovdje, to je slično onome što je predstavljen u predavanju,
osim u predavanju predstavili smo to s Ints za razliku char * s.
To će biti hrpa koja pohranjuje što?
Daniel? Što mi spremanje u ovom stog?
[Daniel] Strings? >> Mi smo pohranu konce u ovom stog, točno.
Sve što trebate imati kako bi se stvorili hrpu je niz
određenog kapaciteta, koji u ovom slučaju,
Kapacitet će biti u svim kape, jer to je konstanta.
I onda uz polje, svi moramo pratiti je trenutna veličina polja.
Jedna stvar je imati na umu da se ovdje je vrsta cool
je da smo stvaranje složeni strukturu podataka na vrhu druge strukture podataka, niz.
Postoje različiti načini za implementaciju hrpe.
Nećemo to učiniti sasvim još, ali nadamo se nakon radiš linked-popis problema,
vidjet ćete kako možete jednostavno implementirati stog na vrhu povezane liste, kao dobro.
Ali za sada, mi ćemo staviti na polja.
Pa opet, sve što trebate je niz i samo trebamo pratiti veličinu niza.
[Sam] Nažalost, zašto je to što je rekao stog je na vrhu žice?
Za mene je to izgleda kao žica u snopu.
[Hardison] Aha. Mi smo stvaranje, mi smo uzimajući naše polje strukturu podataka -
to je veliko pitanje. Dakle, postavlja se pitanje zašto, za ljude koji su gleda ovaj online,
Zato smo rekavši da je stog je na vrhu žice,
jer ovdje to izgleda kao žica unutar dimnjaka?
Koji je potpuno slučaj.
Ono što sam mislio da je da imamo jedan strukturu polje podataka.
Imamo niz char * s, ovo polje nizova,
a mi ćemo dodati da, kako bi se stvorili složeni strukturu podataka.
>> Dakle, stog je malo složeniji nego niz.
Možemo koristiti niz izgraditi stog.
Dakle, to je mjesto gdje možemo reći da je stog je izgrađen na vrhu niza.
Isto tako, kao što sam rekao ranije, možemo izgraditi stog na vrhu povezane liste.
Umjesto korištenja niz držati naše elemente,
bismo mogli koristiti povezanu listu držati naše elemente i izgraditi hrpu oko toga.
Idemo prošetati kroz nekoliko primjera, gleda na nekom kodu,
vidjeti što se zapravo događa ovdje.
Na lijevoj strani, sam bacio što je stog struct će izgledati u memoriji
ako kapaciteti # definirani su se četiri.
Imamo naše četiri elementa char * niz.
Imamo žice [0], žice [1], žice [2], žice [3],
i onda taj zadnji prostor za naše veličine cijeli.
Ima li to smisla? Ok.
To je ono što se događa ako se ono što radim na desnoj strani,
koji će biti moj broj je samo proglasiti rekonstruirati složen struct zove i.
To je ono što smo dobili. Ona propisuje ovaj trag u sjećanju.
Prvo pitanje ovdje je ono što su sadržaj ovog stog struct?
Upravo sada oni ništa, ali oni nisu potpuno ništa.
Oni ova vrsta smeća. Nemamo pojma što je u njima.
Kada smo proglasiti dimnjaka s, mi smo samo bacanje da dolje na vrhu memorije.
To je vrsta kao što su progla int i, a ne ga pokreće.
Vi ne znate što je unutra. Možete pročitati ono što je tamo,
ali to ne može biti super korisna.
Jedna stvar koju želite da se uvijek sjećati učiniti je inicijalizirati sve što treba da se ponište.
U tom slučaju, mi ćemo inicijalizirati veličinu biti nula,
jer će ispasti da se vrlo važno za nas.
Mogli smo ići naprijed i inicijalizirati sve pokazivače, sve char * s,
da se neki razumljivo vrijednost, vjerojatno null.
No, to nije potpuno nužno da ćemo to učiniti.
>> Sada, dvije glavne operacije na hrpe su?
Svatko se sjećate iz predavanja što učiniti s dimnjaka? Da?
[Stella] Guranje i iskakanje? >> Točno.
Guranje i iskakanje su dvije glavne operacije na hrpe.
A što ne gurati učiniti? >> On stavlja nešto na vrhu
iz dimnjaka, a zatim popping ga skida.
[Hardison] Točno. Dakle, gura gura nešto na vrhu dimnjaka.
To je kao blagovanje osoblja stavljajući blagovanje ladicu dolje na šalteru.
I iskakanje je uzimanje blagovaonicu ladicu off stog.
Idemo prošetati kroz nekoliko primjera što se događa
kad smo gurnuti stvari u dimnjaku.
Ako smo bili gurnuti niz 'halo' na naš dimnjak,
to je ono što naš dijagram će izgledati sada.
Pogledajte što se događa?
Mi gurnuo u prvi element našeg strings niz
i mi povisio našu veličinu računati da će jednoga.
Dakle, ako ćemo gledati na razliku između dva slajda, ovdje je 0, evo pred pritiskom.
Ovdje je nakon pritiskom.
Prije pritiskom, nakon što je pritiskom.
I sada imamo jedan element u našem stog.
To je niz "halo", i to je to.
Sve drugo u nizu, u našem strings niz, još uvijek je smeće.
Nismo ga inicijalizirana.
Ajmo reći da smo gurnuti još niz na naše stog.
Mi ćemo gurnuti "svijet" na ovaj put.
Tako možete vidjeti "svijet" ovdje ide na vrhu "halo",
i veličina Brojač ide do 2.
Sada možemo gurati "CS50", te da će ići na vrhu ponovno.
Ako se vratimo, možete vidjeti kako smo pritom stvari na vrhu dimnjaka.
A sada smo dobili pop.
Kada smo popped nešto izvan dimnjaka, što se dogodilo?
Svatko vidi razliku? To je prilično suptilno.
[Studentski] veličina. >> Da, veličina promijenio.
>> Što drugo bi ste Očekuje se da će promijeniti?
[Studentski] žice, previše. >> Točno. Žice previše.
Ispada da kada radite na ovaj način,
jer nismo kopiranje elemente u naš dimnjak,
mi zapravo ne morate ništa učiniti, a mi se samo možemo koristiti veličinu
pratiti broj stvari u našem polju
tako da kad smo pop opet, opet mi samo dekrementirati našu veličinu do jedne.
Nema potrebe da se zapravo otići i prepisati ništa.
Vrsta funky.
Ispada da smo obično samo ostaviti stvari na miru jer je manje posla za nas učiniti.
Ako mi ne moramo ići natrag i prepisati nešto, zašto onda to učiniti?
Dakle, kad smo pop dvaput isključen iz dimnjaka, sve što radi je dekrementirati veličini nekoliko puta.
I opet, to je samo zato što nismo kopiranje stvari u našoj stog.
Da? Idi naprijed.
[Student, nerazumljivo] >> I što se onda dogodi kada se gurati nešto opet?
Kada gurnuti nešto opet, gdje to ide?
Gdje to ide, bosiljak? >> Into žice [1]? >> Točno.
Zašto ne da ići u žice [3]?
[Bosiljak] Budući da je zaboravio da je nešto bilo u žice [1] i [2]?
[Hardison] Točno. Naš stog, u suštini, "zaboravio" da je drži na ništa
u žice [1] ili žice [2], pa kad smo gurnuti "woot",
to samo stavlja da je u elementu na žice [1].
Ima li kakvih pitanja o tome kako se to radi, na osnovnoj razini?
[Sam] Dakle, to nije dinamična na bilo koji način, u smislu iznosa
ili u smislu veličine stog?
[Hardison] Točno. To je - točka bila je da to nije bio dinamički growning stog.
Ovo je stog koji može izdržati, najviše, četiri char * s, u većini četiri stvari.
Ako smo bili i pokušati gurnuti petine stvar, što mislite bi se trebalo dogoditi?
[Studenti, nerazumljivih]
[Hardison] Točno. Postoji nekoliko stvari koje se mogu dogoditi.
To bi moglo SEG kvar, ovisno o tome što smo bili -
kako je točno da su provedbu back-end.
To bi moglo prepisati. To bi moglo imati taj buffer overflow koji mi je govorio o u klasi.
Što će biti najočitiji stvar koja bi mogla biti prebrisana
ako smo pokušali gurnuti dodatni stvar na našem stog?
Dakle, spomenuli ste buffer overflow.
Što bi moglo biti stvar koja bi se napisano ili otresao na
ako mi je potopilo slučajno pokušava gurnuti dodatni stvar?
[Daniel, nerazumljivo] >> Mogući.
No, u početku, što bi se moglo dogoditi? Što ako smo pokušali gurnuti četvrtine stvar?
To bi moglo prepisati veličinu, barem s ovim memorije dijagram koji smo dobili.
>> U specifikaciji problema set, što je ono što ćemo se provodi danas,
ono što želim učiniti je samo povratak false.
Naš guranje metoda će vratiti boolean vrijednost,
i da boolean vrijednost će biti istina, ako uspije gurnuti
a false ako ne možemo gurati ništa više, jer je stog pun.
Idemo prošetati malo tog koda upravo sada.
Evo naš pritisak funkcija.
Naš guranje funkcija za hrpom će uzeti u nizu staviti na stog.
To će vratiti true ako uspješno je gurnula niz
na stog i lažno drugačije.
Bilo koji sugestija o tome što bi moglo biti dobra prva stvar za učiniti ovdje?
[Sam] Ako veličina jednaka sposobnosti onda povratak false?
[Hardison] Bingo. Lijep posao.
Ako je veličina kapaciteta, idemo na povratak false.
Mi ne možemo staviti ništa više u našoj stog.
Inače, želimo staviti nešto na vrhu dimnjaka.
Što je "na vrhu dimnjaka", u početku?
[Daniel] Veličina 0? >> Veličina 0.
Što je na vrhu dimnjaka nakon Ima jedna stvar u snopu? Missy, znaš?
[Missy] Jedan. >> Veličina je jedan, točno. Vi držati dodajući od veličine,
i svaki put ste stavljanjem u novi element na indeksu veličini u polju.
Možemo to učiniti s tom vrstom jedan-liner, ako to ima smisla.
Tako smo dobili naše konce niz, idemo pristupiti na veličinu indeksa,
i mi smo samo ide za pohranu našu char * tamo.
Obavijest o tome kako da nema string kopiranje ovdje događa,
ne dinamični dodjela memorije?
I onda gospođica doveo do onoga što sada moramo učiniti,
jer smo pohranjeni tekst u odgovarajuće mjesto u polju,
i ona je rekla da smo morali povećajte veličinu jedan, tako da smo spremni za sljedeću pritiskom.
Dakle, možemo to učiniti s s.size + +.
U ovom trenutku, mi smo gurnuli u našem polju. Što je zadnja stvar koju moramo učiniti?
[Studentski] Povratak istina. >> Povratak istina.
Dakle, to je prilično jednostavna, prilično jednostavan kod. Ne previše.
Nakon što ste omotan glavu oko kako stog radi,
to je prilično jednostavan za implementaciju.
>> Sada, sljedeći dio je to iskakanje niz off stog.
Ja ću vam dati dečki malo vremena za rad na ovoj malo.
To je gotovo bitno je obrnuto od onoga što smo učinili ovdje u pritiskom.
Što sam učinio je zapravo - Ups.
Ja dignete jedan aparat ovamo, i aparata,
Ja sam izvukao Problem postaviti 5 specifikaciju.
Ako smo povećali ovdje, možemo vidjeti da sam na cdn.cs50.net/2012/fall/psets/pset5.pdf.
Jeste vi preuzeli ovaj kod koji se nalazi ovdje, section6.zip?
U redu. Ako niste učinili, učinite to upravo sada, jako brzo.
Ja ću to učiniti u mom prozor terminala.
Ja sam zapravo to učinio ovdje. Da.
Da, Sam? >> Imam pitanje o tome zašto ste rekli s.string 's konzolama veličine = str?
Što je str? Je li to definirano negdje prije, ili - oh, u char * str?
[Hardison] Da, točno. To je bio argument. >> Oh, u redu. Oprostite.
[Hardison] Mi smo se navodi niz gurnuti u.
Druga pitanje koje bi moglo doći do koje nismo stvarno govoriti o ovdje je
smo uzimali zdravo za gotovo da smo imali ovu varijablu nazvanu a
koji je bio u opsegu i pristupačnom nas.
Mi smo uzeli zdravo za gotovo da je bio taj stog struct.
Dakle, gledajući unatrag na ovom guranje koda,
možete vidjeti da radimo stvari sa ovom nizu koji je dobio donesen u
ali onda odjednom, mi smo pristup s.size, kao što je, odakle je došao iz?
U kodu koji ćemo gledati u rubrici arhive
i onda stvari koje ćete raditi u svom problemu postavlja,
smo napravili naš stog struct globalnu varijablu
tako da možemo imati pristup do njega u svim našim različitim funkcijama
bez potrebe da ručno ga zaobići i to prođe pozivom,
učiniti sve da se takve stvari u njemu.
Mi samo varanje malo, ako hoćete, da bi stvari ljepše.
I to je nešto što mi ovdje radimo, jer to je za zabavu, to je lakše.
Često, vidjet ćete ljudi to učiniti ako oni imaju jednu veliku strukturu podataka
koja se operirao u okviru svojih programa.
>> Vratimo se preko aparata.
Jeste svi uspješno dobiti section6.zip?
Svatko ga unzip pomoću unzip section6.zip?
Ako idete u odjeljku 6 imenik -
aah, sve više mjesta -
i popis onoga što je ovdje, vidjet ćete da ste je dobio tri različite. C datoteke.
Imaš red, SLL, koja je pojedinačno-linked list, i stog.
Ako vam se otvoriti stack.c,
možete vidjeti da smo dobili ovu struct definiran za nas,
točno rekonstruirati da smo samo razgovarali o u slajdovima.
Imamo našu globalnu varijablu za stog,
mi imamo naše potisnu funkciju,
i onda mi imamo našu pop funkciju.
Ja ću staviti kod za gurnuti natrag gore na slajdu ovdje,
ali ono što bih ti dečki učiniti je, da je najbolje od vaših sposobnosti,
otići i provesti pop funkciju.
Nakon što ste ga provoditi, možete sastaviti to s make stog,
, a zatim pokrenuti rezultanta izvršnu stog,
i da će pokrenuti sve ove ispitne kod ovdje da je u glavni.
A glavni brine zapravo što push i pop poziva
i pazeći da sve ide preko svih prava.
Ona također inicijalizira stog veličinu ovdje
, tako da ne morate brinuti o inicijalizacije da.
Možete pretpostaviti da je ispravno inicijaliziran
u vrijeme koje pristupate ga u pop funkciji.
Ima li to smisla?
Dakle, ovdje mi ići. Tu je pritisak kod.
Dat ću vam dečki 5 ili 10 minuta.
A ako imate bilo kakvih pitanja u međuvremenu dok ste kodiranja,
zamolite ih naglas.
Dakle, ako ste dobili na zabada točke, samo pitajte.
Dopustite mi da znam, neka svatko drugi zna.
Rad sa svojim susjedom previše.
[Daniel] Samo smo provedbu pop upravo sada? >> Samo pop.
Iako možete kopirati provedbu pritiskom ako želite
tako da testiranje će raditi.
Budući da je teško testirati stvari uzimajući u -
ili, to je teško testirati iskakanje stvari iz dimnjaka, ako ne postoji nešto u snopu za početak.
>> Što je pop trebao se vratiti? Element iz vrha dimnjaka.
To je trebao dobiti element off vrhu dimnjaka
i onda dekrementirati veličinu stog,
a sada ste izgubili element na vrhu.
A onda se vratite element na vrhu.
[Student, nerazumljivo]
[Hardison] Dakle, što se događa ako to učiniti? [Student, nerazumljivo]
Što završi događa je da ste vjerojatno pristupa ili
element koji nije inicijaliziran još, tako da vaš izračun
gdje zadnji element je isključen.
Dakle, ovdje, ako primijetite, u pritiskom, mi smo pristup konce u s.size elementa
jer to je novi indeks.
To je novi vrh stoga.
Dok je u pop, s.size će biti sljedeći prostor,
prostor koji je na vrhu svih elemenata u stogu.
Dakle, najvišu element nije na s.size,
nego, to je ispod nje.
>> Druga stvar koju treba učiniti kada - u pop,
je li moram dekrementirati veličinu.
Ako se sjećate natrag u naš mali dijagram ovdje,
stvarno, jedina stvar koju smo vidjeli događa kada smo nazvali pop
je da je to veličina pao, najprije na dvije, zatim jedan.
Onda kad smo gurnuo novi element na, to će ići na na pravilan licu mjesta.
[Bosiljak] Ako s.size je 2, onda ne bi bilo otići u elementu 2,
i onda bi htjela pop tog elementa off?
Dakle, ako smo otišli - >> Pa pogledajmo to opet.
Ako je ovo naša stog u ovom trenutku
i zovemo pop,
na kojoj je indeks najvišu elementa?
[Bosiljak] Na dvije, ali to će pop-3. >> Točno.
Dakle, to je mjesto gdje naša veličina je 3, ali želimo da se pop element na indeksu 2.
To je to tipična vrsta off po jedan da imate s nula-indeksiranje polja.
Dakle, vi ne želite da pop treći element, ali treći element nije na indeksu 3.
A razlog ne morate učiniti da minus jedan kad smo pritom
je zato što upravo sada, primijetit ćete da je najvišu element,
ako smo bili gurnuti nešto drugo na stog u ovom trenutku,
mi bi željeli da ga gurnuti na indeksu 3.
I to samo tako dogodi da je veličina i indeksi redati kada ste gura.
>> Tko je dobio radnu stog provedbu?
Imaš radnu stog jedan. Dali su pop raditi još?
[Daniel] Da. Mislim da je tako.
>> Program je trčanje, a ne SEG Faulting, to je ispis?
Da li to isprintati "uspjeh" kada ga pokrenuti?
Da. Napravite stog, pokrenuti ga, ako ga ispisuje "uspjeh" i ne ići bum,
onda sve je dobro.
U redu. Idemo na aparatu jako brzo,
a mi ćemo kroz ovo.
Ako gledamo na ono što se ovdje događa sa pop,
Daniel, što je bila prva stvar koju si učinio?
[Daniel] Ako s.size je veći od 0.
[Hardison] Ok. A zašto ste to učinili?
[Daniel] Da bi bili sigurni da je nešto unutar dimnjaka.
[Hardison] Točno. Želite li testirati kako bi bili sigurni da s.size je veća od 0;
inače, što želiš da se dogodi?
[Daniel] Povratak null? >> Povratak null, točno.
Dakle, ako s.size je veća od 0. A što ćemo učiniti?
Što ćemo učiniti ako stog nije prazan?
[Stella] Vi dekrementirati veličinu? >> Vi dekrementirati veličinu, ok.
Pa kako si to učinio? >> S.size--.
[Hardison] Veliki. A onda ono što ste radili?
[Stella] A onda sam rekao povratak s.string [s.size].
[Hardison] Veliki.
Inače vratiti null. Da, Sam?
[Sam] Zašto ne treba biti s.size + 1?
[Hardison] plus 1? >> Da. >> Jesam.
[Sam] Mislio sam, jer ste uzimanje 1,
onda ćeš se vratiti ne onaj koji su tražili.
[Hardison] A to je upravo ono što smo pričali o ovom cijelom pitanju 0 indeksa.
Dakle, ako smo povećali natrag ovamo.
Ako gledamo ovog momka ovdje, možete vidjeti da kad smo pop,
mi smo iskakanje element na indeksu 2.
>> Tako smo smanjili našu veličinu prvi, onda je naša veličina odgovara naš indeks.
Ako mi ne dekrementirati veličinu prvi, onda moramo učiniti veličinu -1 i onda smanjuju.
Izvrsno. Sve dobro?
Sva pitanja o tome?
Postoji nekoliko različitih načina pisati to kao dobro.
U stvari, možemo nešto učiniti, čak i - možemo napraviti jedan-liner.
Možemo učiniti jedan-line prijave.
Dakle, možemo zapravo dekrementirati prije nego što smo se vratili na taj.
Dakle, stavljajući - prije s.size.
To čini linija stvarno gusta.
Gdje je razlika između -. Veličine i s.size--
je da je ovaj postfix - zovu postfix jer - dolazi nakon s.size--
znači da s.size se procjenjuju u svrhu pronalaženja indeks
kao što je to trenutno kad ova linija je pogubljen,
i onda je to - događa nakon linija dobiva pogubili.
Nakon element na indeksu s.size je pogledana.
A to nije ono što želimo, jer želimo snižavanja dogoditi prvi.
Othewise, idemo se pristupa niz, učinkovito, izvan granica.
Mi ćemo se pristupa element iznad one koja mi zapravo želite pristupiti.
Da, Sam? >> Je li to brže ili koristiti manje RAM-a da bi se u jednoj liniji ili ne?
[Hardison] Iskreno, to stvarno ovisi.
[Sam, nerazumljivo] >> Da, to ovisi. Možete napraviti prevodilac trikove
da biste dobili prevodilac priznati da, obično, pretpostavljam.
>> Tako smo spomenuli malo o ovim stvarima prevodilac optimizacije
što možete učiniti u sastavljanju,
i to je vrsta stvar koja prevodilac mogli shvatiti,
kao oh, hej, možda mogu to učiniti sve u jednoj operaciji,
za razliku učitavanja veličini varijablu u od RAM-a,
ga decrementing, spremajući ga natrag van, a zatim ga učitava natrag u opet
obraditi ostatak ove operacije.
No, u pravilu, ne, ovo nije jedna od onih stvari
to će učiniti vaš program znatno brže.
Bilo više pitanja o dimnjaka?
>> Dakle, guranje i iskakanje. Ako vi želite isprobati haker izdanje,
ono što smo učinili u hakerske izdanju zapravo otišao
i napravio to stog raste dinamički.
Izazov je prije svega ovdje u push funkciji,
shvatiti kako napraviti da niz raste
kao što gurati sve više i više elemenata na na stog.
To je zapravo nije previše dodatni kod.
Samo poziv na - morate zapamtiti da biste dobili pozive za malloc tamo ispravno,
i onda shvatiti kad ideš na poziv realloc.
To je zabavno izazov, ako ste zainteresirani.
>> No, za sada, krenimo dalje, a pričajmo o redovima.
Dođite ovuda.
Red čekanja je blizu sestru stog.
Dakle, u snopu, stvari koje su stavili u posljednja
bile su prve stvari do tada biti vraćeni.
Moramo ovo posljednja u, prvi van, ili LIFO, naručivanja.
Dok je u redu, kao što očekujete od kad stojite u redu,
prva osoba koja se u redu, prva stvar da se u red,
je prva stvar koja dobiva preuzeti iz reda.
Redovi su također često koristi kada imamo posla s grafovima,
kao što smo razgovarali o nakratko s dimnjaka,
a redovi su također zgodan za hrpu drugih stvari.
Jedna stvar koja dolazi često pokušava zadržati, primjerice,
razvrstani popis elemenata.
I vi možete to učiniti s nizom. Možete održavati sortirani popis stvari u polju,
ali gdje da dobiva lukav je onda uvijek morati pronaći
prikladno mjesto za umetanje sljedeći stvar.
Dakle, ako imate niz brojeva, jedan kroz deset,
a zatim želite proširiti da na sve brojeve od 1 do 100,
a vi ste dobivanje tih brojeva u slučajnim redoslijedom i pokušava zadržati sve
razvrstani kao i ti ići kroz, te kraj gore vlasništvo to učiniti puno kreće.
Uz određene vrste redova i određenih vrsta temeljne strukture podataka,
zapravo možete držati ga prilično jednostavna.
Ne morate dodati nešto, a zatim rekonstrukciju cijela stvar svaki put.
Niti ćete morati učiniti puno pomicanja unutarnjih elemenata oko.
Kada gledamo redu, vidjet ćete da je - također u queue.c u rubrici koda -
the struct da smo vas dao je stvarno sličan struct da vam je dao za stog.
>> Postoji jedna iznimka, i to jedna iznimka
je da imamo ovaj dodatni cijeli zove glava,
i glava ovdje je za praćenje glave red,
ili prvi element u redu.
Uz hrpu, bili smo u mogućnosti pratiti elementa koji smo bili na dohvat,
ili na vrhu dimnjaka, koristeći samo veličinu,
dok s red, mi smo da se bave suprotnim krajevima.
Mi pokušavamo sklepati stvari na na kraju, ali zatim se vratiti stvari s prednje strane.
Dakle, učinkovito, s glavom, imamo indeks početku reda,
i veličina daje nam indeks kraju reda
tako da možemo dohvatiti stvari iz glave i dodati stvari na repu.
Dok s hrpom, bili smo samo ikada bave vrhu dimnjaka.
Mi nikada nisu imali pristup dno stoga.
Mi samo dodao stvari na vrh i uzeo stvari off vrhu
tako da mi nije potrebno da dodatni polje unutar našeg struct.
Znači li to da općenito ima smisla?
U redu. Da, Charlotte? [Charlotte, nerazumljivo]
[Hardison] To je veliko pitanje, a to je onaj koji je došao u predavanju.
Možda šetnju kroz nekoliko primjera će ilustrirati zašto
ne želimo koristiti Strings [0] kao čelnik red.
>> Pa zamislite da imamo red, idemo da ga zovu red.
Na početku, kad smo upravo to instanciraju,
kada smo upravo to proglasio, nismo inicijaliziran ništa.
To je sve smeće. Pa naravno da želimo biti sigurni da ćemo inicijalizirati
i veličina i glava polja biti 0, nešto razumno.
Također smo mogli ići naprijed i nulu od elemenata u našem redu.
A da bi ovaj dijagram formi, primijetiti da je sada naš red mogu držati samo tri elementa;
dok je naša stog mogao držati četiri, naš red mogu držati samo tri.
A to je samo da bi dijagram stane.
Prva stvar koja se događa ovdje je da smo enqueue string "hi".
I baš kao što smo učinili s hrpom, ništa strašno drugačiji ovdje,
bacimo niz na na žice [0] i povećavati svoju veličinu jednog.
Mi enqueue "zbogom", on dobiva staviti na.
Dakle, ovo izgleda kao stog za najveći dio.
Započeli smo ovdje, novi element, novi element, veličina čuva ide prema gore.
Što se događa u ovom trenutku, kada želimo dequeue nešto?
Kada želimo dequeue, koji je element koji želimo dequeue?
[Bosiljak] Strings [0]. >> Zero. Točno pravo, Basile.
Želimo da biste dobili osloboditi od prvog niza, ovaj jedan, "hi".
Dakle, ono što je druga stvar koja je promijenila?
Obavijest kada smo popped nešto izvan dimnjaka, samo smo promijenili veličinu,
ali ovdje, imamo nekoliko stvari koje se mijenjaju.
Ne samo veličinu promjene, ali glava promjene.
To ide natrag u Charlotte točke ranije:
zašto imamo ovu glavu, kao i?
Ima li smisla sada, Charlotte? >> Vrsta.
[Hardison] Vrsta? Dakle, ono što se dogodilo kad smo dequeued?
Što je glava to da je sada zanimljivo?
[Charlotte] Oh, jer to promijenilo - ok. Razumijem.
Budući da je glava - gdje je glava ukazuje na promjene u smislu položaja.
To više nije uvijek nula indeks jedan. >> Da, točno.
Ono što se dogodilo je, ako dequeueing visoku elementa
je učinjeno i nismo imali ovu glavu polje
jer smo uvijek bili nazivajući ovaj niz na indeksu 0 voditeljica našeg reda,
onda ćemo morati prebaciti ostatak red dolje.
Morali bismo pomak "zbogom" od od žice [1] za gudače [0].
I žice [2] do žice [1].
I mi bismo to učiniti za cijeli popis elemenata,
Cijeli niz elemenata.
A kada smo to s nizom, koji dobiva stvarno skupo.
Dakle, ovdje, to nije velika stvar. Moramo samo tri elementa u našem polju.
Ali, ako smo imali red od tisuću elemenata ili milijun elemente,
i onda odjednom, mi početi zarađivati ​​hrpu dequeue poziva sve u petlji,
stvari su stvarno ide usporiti kao što pomiče prema dolje sve stalno.
Znate, pomak od 1, pomak prema jednoj smjeni, po jedan, pomak po jedan.
Umjesto toga, mi koristimo ovu glavu, mi to zovemo "pokazivač", iako to nije stvarno pokazivač
u užem smislu, to nije pokazivač tipa.
To nije int * ili char * ili bilo što slično.
Ali to pokazuje i ukazuje na glavu našeg reda. Da?
>> [Studentski] Kako dequeue znam samo pući god je na čelu?
[Hardison] Kako dequeue znam kako pući god je na čelu? >> Točno, da.
>> Što se to gleda samo ono što glava polje postavljeno na.
Dakle, u ovom prvom slučaju, ako ćemo gledati ovdje,
naša voditeljica je 0, indeks 0. >> Točno.
[Hardison] Pa to samo govori u redu, dobro, element na indeksu 0, niz "hi",
je element na čelu naše redu.
Dakle, idemo dequeue tog tipa.
I to će biti element koji se vratio na pozivatelja.
Da, Saad? >> Dakle, glava u osnovi postavlja - gdje ćeš ga indeks?
To je početak to? >> Da. >> Ok.
[Hardison] To je postao novi početak za naše polje.
Dakle, kada ste dequeue nešto, sve što morate učiniti je pristupiti element na indeksu q.head,
i da će biti element koji želite dequeue.
Također morate dekrementirati veličinu.
Vidjet ćemo u malo gdje se stvari malo lukav s tim.
Mi dequeue, a sada, ako mi enqueue opet,
Kamo ćemo enqueue?
Odakle Sljedeći element ići u našem redu?
Recimo da želimo enqueue string "CS".
U koji indeks će to ići? [Studenti] Strings [2]. >> Dvije.
Zašto 2 i nije 0?
[Bosiljak] Jer sada je glava 1, tako da je kao početak popisa?
[Hardison] Točno. A što označava kraj popisa?
Što smo koristite za označavanje kraj našeg reda?
Glava je šef našeg reda, početak našeg reda.
Što je kraj našeg reda? [Studenti] veličini. >> Veličina, točno.
Dakle, naši novi elementi ići u na veličini, a elementi koji mi skinu otpasti na glavu.
Kada smo enqueue sljedeći element, mi smo stavljajući ga u na veličini.
[Studentski] Prije nego što stavite da ipak, veličina je jedan, zar ne?
[Hardison] Točno. Dakle, nije sasvim u veličini. Veličina +, ne jednom, ali + glava.
Budući da smo pomaknuo sve po glavi iznosu.
Dakle, ovdje, sada imamo red veličine 1 koja počinje na indeksu 1.
Rep je indeks 2. Da?
>> [Studentski] Što se događa kada dequeue žice [0], a niti 'utora za memoriju
Jednostavno se prazni, u osnovi, ili samo zaboravio?
[Hardison] Aha. U tom smislu, samo smo ih zaboravljam.
Ako smo bili spremanje kopije za -
mnogi strukture podataka često će pohraniti svoje kopije elemenata
tako da osoba koja upravlja strukturu podataka ne moraju brinuti
o tome gdje su svi ti upućuje se događa.
Podaci struktura drži na svemu, drži na svim kopijama,
kako bi bili sigurni da je sve ustraje na odgovarajući način.
Međutim, u ovom slučaju, ove strukture podataka samo, radi jednostavnosti,
ne poduzimaju kopije svega što smo skladištenje u njima.
[Studentski] Tako je to kontinuirani niz -? >> Da.
Ako se osvrnemo na ono što je definicija ove strukture, to je.
To je samo standardni niz kao što ste vidjeli,
niz char * s.
Znači li to da -? >> Da, ja sam bio pravedan izvjedljiv
ako na kraju ćete ponestane memorije, u određenoj mjeri,
ako imate sve te prazne mjesta u vašem niz?
[Hardison] Da, to je dobra stvar.
>> Ako ćemo gledati na ono što se dogodilo sada u ovom trenutku,
smo napunili našu red, to izgleda.
Ali nismo stvarno popunio naš red
jer imamo red koji je veličine 2, ali to počinje indeksom jedan,
jer to je gdje je naš glavni pokazivač.
Kao što su govorili, da se taj element na žice [0], na indeksu 0, nije stvarno tamo.
To nije u našem red više.
Mi jednostavno ne zamaram se otići i to prepisati kad smo ga dequeued.
Dakle, iako to izgleda kao da smo ponestane memorije, mi stvarno nisu.
To mjesto je dostupna za nas koristiti.
Odgovarajući ponašanje, ako smo probati i prvi dequeue nešto
sviđa "zbogom", da bi pop off bye.
Sada naš red počinje indeksom dva, te je veličine 1.
A sada, ako ćemo pokušati i enqueue nešto opet, recimo 50,
50 bi trebao ići u tom mjestu na indeksu 0
jer to je još uvijek dostupna za nas. Da, Saad?
[Saad] Znači li to da se dogoditi automatski?
[Hardison] To se ne događa sasvim automatski. Morate učiniti math
da to rade, ali u suštini ono što smo učinili je upravo smo omotan oko.
[Saad] I to je u redu ako to ima rupu u sredini njega?
[Hardison] To je, ako možemo napraviti math raditi ispravno.
>> I ispada da je to zapravo i nije tako teško učiniti s MORH operatora.
Dakle, baš kao što smo učinili s Cezarom i kripto stvari,
koristite mod, možemo dobiti stvari zaokrenuti i zadržati ide
i okolo i okolo s našim redu,
čuvanje da glava pokazivač se kreće oko.
Obavijest da je veličina uvijek poštujući broj elemenata zapravo u redu.
A to je samo glava pokazivač koji drži biciklizam kroz.
Ako ćemo gledati na ono što se ovdje dogodilo, ako se vratimo na početak,
a vi samo gledati što se događa u glavi
kad smo enqueue nešto, ništa se nije dogodilo u glavi.
Kada smo enqueued nešto drugo, ništa se nije dogodilo u glavi.
Čim smo dequeued nešto, glava ide gore po jedan.
Mi enqueued nešto, ništa se ne događa u glavi.
Kada smo dequeue nešto, odjednom je glava gets porastao.
Kada smo enqueue nešto, ništa se ne događa u glavi.
>> Što će se dogoditi u ovom trenutku, ako smo bili na dequeue nešto opet?
Bilo misli? Što će se dogoditi u glavi?
Što bi se trebalo dogoditi u glavu
ako smo bili na dequeue nešto drugo?
Glava sada je pravo na indeks 2,
što znači da je glava red je žice [2].
[Studentski] Koja vraća 0? >> On bi se trebao vratiti 0. To bi trebao završiti natrag oko, točno.
Do sada, svaki put kad smo zvali dequeue, mi smo bili dodavanjem jedne na glavi,
dodati jedan u glavu, dodati jedan do glave, dodati jedan u glavu.
Čim da glava pokazivač dobiva posljednjeg indeksa u našem polju,
onda moramo ga vratiti omotati oko početku, vratiti na 0.
[Charlotte] Što određuje kapacitet red u stog?
[Hardison] U ovom slučaju, upravo smo koristili # definirana konstanta. >> Ok.
[Hardison] U stvarna. C datoteku, možete otići i đubre s njim malo
i čine ga kao velika ili onoliko malo koliko želite.
[Charlotte] Dakle, kada ste čineći ga red, kako bi računalo zna
koliki želite stog biti?
[Hardison] To je veliko pitanje.
Postoji nekoliko načina. Jedan je to samo definirati up front
i kažu da će ovo biti red da ima četiri elemente ili 50 elemenata ili 10.000.
Drugi način je da učine ono što su hakerski izdanje ljudi rade
i stvoriti funkcije imati svoj red rasti dinamički kako dobiti više stvari dodao rezervirati
>> [Charlotte] Dakle, ići s prvom opcijom, što sintaksa ne koristite
reći program što je veličina reda?
[Hardison] Ah. Tako ćemo se iz ovoga.
Ja sam još uvijek u stack.c ovdje, tako da sam samo idem za pomicanje do vrha ovdje.
Vidite li ovo ovdje? Ovo je # define kapaciteta 10.
A to je gotovo isti sintaksa da imamo za red.
Osim u redu, mi smo dobili taj dodatni struct polje ovdje.
[Charlotte] Oh, mislio sam da je kapacitet značilo kapacitet za niz.
[Hardison] Ah. >> To je maksimalna duljina riječi. >> Jesam.
Da. Kapacitet ovdje - to je velika stvar.
A to je nešto što je lukav
jer ono što smo proglašeni ovdje je niz char * s.
Niz pokazivača.
To je niz znakova.
To je vjerojatno ono što ste vidjeli kada ste bili proglašenja svoje odbojnika za datoteku I / O,
kad ste bili stvaranje nizova ručno na stog.
Međutim, ono što imamo ovdje je niz char * s.
Dakle, to je niz pokazivača.
Zapravo, ako ćemo sliku natrag van i gledamo što se događa ovdje
u prezentaciji, vidjet ćete da je stvarni elemente, lik podataka
nije pohranjena u polju sama.
Što je pohranjen unutar našeg polja ovdje su pokazivači na karakter podataka.
Ok. Tako smo vidjeli kako je veličina redu baš kao i sa hrpom,
Veličina uvijek poštuje broj elemenata trenutno u redu.
Nakon što dva enqueues, veličina je 2.
Nakon što dequeue veličina je sada jedan.
Nakon što drugo enqueue veličina je natrag do dva.
Dakle, veličina definitivno poštuje broj elemenata u redu,
i onda glava samo čuva biciklizam.
Ona ide od 0-1-2, 0-1-2, 0-1-2.
I svaki put mi zovemo dequeue, šef pokazivač gets porastao na sljedeću indeksa.
A ako glave je oko ići preko, to petlje natrag oko 0.
Dakle, s tim, možemo napisati dequeue funkciju.
I mi ćemo napustiti enqueue funkciju za vi provesti umjesto.
>> Kada smo dequeue element iz našeg reda,
što je bila prva stvar koju Daniel učinio kada smo počeli pisati pop funkciju za hrpe?
Dopustite mi da čuti od nekoga tko nije govorio još.
Hajdemo vidjeti, Saad, sjećaš li ono Daniel je kao prva stvar kad je pisao pop?
[Saad] Tu je, to je bio - >> On testirani za nešto.
[Saad] Ako je veličina veća od 0. >> Točno.
A što je to bilo testiranje za?
[Saad] To je testiranje kako bi vidjeli je li postoji nešto unutar polja.
[Hardison] Aha. Točno. Dakle, ne možete ništa pop iz dimnjaka ako je prazna.
Isto tako, ne možete dequeue ništa od čekanja ako je prazna.
Što je prva stvar koju treba učiniti u našoj dequeue funkciju ovdje, ne mislite?
[Saad] Ako je veličina veća od 0? >> Da.
U ovom slučaju, zapravo sam samo testirani vidjeti ako je 0.
Ako je 0, možemo se vratiti null.
Ali isti logika.
I neka je nastaviti s tim.
Ako veličina nije 0, gdje je element koji želimo dequeue?
[Saad] Na glavi? >> Točno.
Mi samo možemo izvući prvi element u našem redu
pristupajući element na čelu.
Ništa luda.
Nakon toga, što bismo trebali učiniti? Što se mora dogoditi?
Što je druga stvar da smo razgovarali o u dequeue?
Dvije stvari moraju dogoditi, jer je naš red je promijenjen.
[Daniel] Smanjite veličinu. >> Moramo smanjiti veličinu i povećanje glavu? Točno.
Za povećanje glavu, ne možemo slijepo povećati glavu, zapamtite.
Ne možemo samo učiniti queue.head + +.
Moramo također uključuju u ovu moderno po kapacitetu.
A zašto mi mod po kapacitetu, Stella?
[Stella] Jer to mora zaokrenuti. >> Točno.
Mi mod po kapacitetu jer mora završiti natrag oko 0.
Dakle, sada, u ovom trenutku, možemo učiniti ono reče Daniel.
Možemo dekrementirati veličinu.
I onda mi samo možemo vratiti element koji je na vrhu reda.
Izgleda vrsta čvornovat na prvom mjestu. Možda imate pitanje. Molim?
>> [Sam] Zašto je prvi na vrhu reda? Gdje to ide?
[Hardison] Ona dolazi iz četvrtog reda od dna.
Nakon što smo testirali kako bi bili sigurni da je naš red nije prazan,
smo izvući char * prvi, mi izvucite element koji je sjedio na glavi indeksa
naše polje, naše strings polja, >> i poziv da prvi?
[Hardison] I zovemo ga prvi. Da.
Samo pratiti na to, zašto misliš da smo morali to učiniti?
[Sam] Svaka prvi samo se vraća q.strings [q.head]? >> Da.
>> Zato što smo radili ovaj mijenjanje q.head s mod funkcijom,
i ne postoji način da to učinite u roku od povratka liniji.
[Hardison] Točno. Vi ste na licu mjesta. Sam potpuno je na licu mjesta.
Razlog smo morali izvaditi prvi element u našem redu i pohraniti ga u varijablu
je zato ovu liniju gdje smo upravo q.head,
tu je mod operator u tamo nije nešto što možemo učiniti
i to stupiti na snagu na glavi bez - u jednoj liniji.
Dakle, mi zapravo moramo izvući prvi element, zatim podesite glavu,
podesiti veličinu, a zatim se vratiti element da smo izvukli.
A to je nešto što ćemo vidjeti kasnije dolazi do s
povezani popisi, kao što smo se poigrati s njima.
Često kada ste oslobađanje ili raspolaganja povezane liste
morate se sjetiti sljedeći element, sljedeći pointer od povezanih popisa
prije odlaganja postojećeg.
Jer inače bacaju informacije o tome što je ostalo na popisu.
Sada, ako idete na aparatu, otvaraju queue.c--X od ovoga.
Dakle, ako sam otvoriti queue.c, neka mi zoom ovdje,
vidjet ćete da imate slična izgleda datoteku.
Slično izgleda datoteka na ono što smo imali ranije s stack.c.
Imamo naše struct za red definiran upravo kao što smo vidjeli na slajdovima.
>> Mi imamo enqueue funkciju koja je za vas učiniti.
I mi imamo dequeue funkciju ovdje.
The dequeue funkcija u datoteci unimplemented,
ali ja ću ga staviti natrag na PowerPointu, tako da možete ga upisati, ako želite.
Dakle, za idućih pet minuta ili tako, ti dečki rade na enqueue
što je gotovo samo suprotno od dequeue.
Ne morate prilagoditi glavu kad si enqueueing, ali ono što ne morate prilagoditi?
Veličina. Dakle, kada ste Postavi u red, glava ostaje netaknuta, veličina gets promijenio.
No, to ne uzeti malo - morat ćete se poigrati s tim mod
shvatiti točno ono što Indeks novi element trebao biti stavljen na.
Dakle, ja ću vam dati dečki malo, staviti dequeue natrag na slajdu,
a kao vi imate pitanja, da ih kriknuti tako da možemo
svi govore o njima kao grupa.
Također, s veličinom Nemoj - kada podesiti veličinu, uvijek možete samo -
Ne morate mod veličinu ikada? [Daniel] No >> Vi ne morate mod veličinu, desno.
Budući da je veličina uvijek će, ako ti si - uz pretpostavku da ste upravljanje stvari na odgovarajući način,
veličina će uvijek biti između 0 i 3.
Kamo morate mod kada radite enqueue?
[Studentski] Samo za glavu. >> Samo za glavu, točno.
A zašto ne morate mod uopće u enqueue?
Kada je situacija u kojoj ne bi se mod?
[Studentski] Ako imate stvari u prostoru, kao na prostorima jedne i dvije,
i onda je potrebno dodati nešto na 0.
[Hardison] Da, točno. Dakle, ako vam je glava pokazivač je na samom kraju,
ili ako je vaša veličina plus vaša glava je veća, ili bolje rečeno, ide na zaokrenuti red.
>> Dakle, u ovoj situaciji da smo dobili ovdje na slajdu upravo sada,
ako želim enqueue nešto upravo sada,
želimo enqueue nešto na indeks 0.
Dakle, ako pogledate gdje ide 50, a ja zovem enqueue 50,
to ide dolje na dnu. To ide u indeks 0.
Ona zamjenjuje "Hi" koji je već bio dequeued.
[Daniel] Nemoj brinuti da u dequeue već?
Zašto to učiniti ništa s glavom u enqueue?
[Hardison] Oh, tako da se ne mijenja glavu, žao mi je.
Ali, morate koristiti mod operator kada pristupate
element koji želite enqueue kada ste pristupu
Sljedeći element u redu.
[Bosiljak] Nisam to učiniti, a ja sam dobio "uspjeh" na tamo.
[Daniel] Oh, shvaćam što govoriš.
[Hardison] Dakle, didn't - samo je na q.size?
[Bosiljak] Aha. Upravo sam promijenio stranu, nisam ništa s glave.
[Hardison] Vi zapravo ne morate resetirati glavu da se ništa,
ali kada indeks u strings niz,
zapravo morati ići naprijed i izračunati gdje Sljedeći element je,
jer prut snop, sljedeći element u stogu je uvijek
na indeksu odgovara veličini.
Ako gledamo natrag na naše funkcije stog pritiskom,
uvijek smo mogli bubnuti u našem novom elementu pravo na indeks veličini.
Dok s red, ne možemo to učiniti
jer ako smo u ovoj situaciji,
ako mi enqueued 50 naš novi niz će ići pravo na žice [1]
koje ne želimo učiniti.
Mi želimo imati novi niz ići na indeksu 0.
>> Da li itko - da? [Studentski] imam pitanje, ali to je stvarno ne odnosi.
Što to znači kada netko samo nazove nešto poput Pred pointer?
Što je to ime kratica za? Znam da je to samo ime.
[Hardison] Pred pokazivač? Idemo vidjeti. U ono što kontekst?
[Studentski] To je za umetka. Ja vam mogu pitati kasnije ako želite
jer to nije stvarno povezani, ali ja jednostavno -
[Hardison] Od Davida insert koda iz predavanja?
Možemo povući da se i razgovarati o tome.
Mi ćemo razgovarati o tome da će sljedeće, nakon što smo dobili na povezanim listama.
>> Tako ćemo jako brzo pogledati što Postavi u red funkcija izgleda.
Što je prva stvar koju ljudi pokušali učiniti u vašem enqueue liniji? U ovom redu?
Slično tome što si učinio za stog gura.
Što ste radili, Stella?
[Stella, nerazumljivo]
[Hardison] Točno. Ako (q.size == kapacitet) -
Trebam staviti moje aparatić na pravom mjestu - povratak false.
Zoom malo. Ok.
Sada ono što je sljedeća stvar koju smo morali učiniti?
Baš kao i sa hrpom, i umeće se na pravom mjestu.
I tako ono što je pravo mjesto za umetanje da?
Uz hrpu da je indeks veličine, s tim da to nije dosta da.
[Daniel] Imam q.head--ili - >> q.strings? >> Da.
q.strings [q.head + q.size mod KAPACITET]?
[Hardison] Mi vjerojatno želite staviti zagrade oko ovog
tako da smo uzimajući odgovarajuću prednost i to tako da je cleart svima.
I postaviti da ravnopravno? >> Da str? >> Da str. Izvrsno.
A sad ono što je posljednja stvar koju moramo učiniti?
Baš kao što smo učinili u snopu. >> Povećajte veličinu? >> Povećajte veličinu.
Boom. A onda, budući da je starter koda upravo vratio false po defaultu,
želimo promijeniti to vrijedi ako sve ide preko i sve ide dobro.
U redu. To je puno informacija za dionicu.
Nismo sasvim gotova. Želimo govoriti o stvarno brzo pojedinačno-linked liste.
Stavit ću ovo gore pa se možemo vratiti na to kasnije.
No, vratimo se na našu prezentaciju za samo nekoliko više slajdova.
Dakle Postavi u red je TODO, sada smo to učinili.
>> Sada ćemo pogledati pojedinačno povezanih s popisa.
Razgovarali smo o ovim malo više u predavanju.
Koliko od vas vidio demo gdje smo imali ljude
nespretno ističući da jedni druge i gospodarstvo brojevima? >> Bio sam u to.
>> Što vi mislite? Je li to, nadamo se demistificirati ove malo?
Uz popis, ispada da smo se bave ovom vrstom da ćemo pozvati čvor.
Dok s red i stog smo imali tvorevina, da bismo nazvati red u stog,
imali smo ove novu red u stog oblika,
ovdje popis je stvarno izmislio hrpa čvorova.
Na isti način kako žice su samo hrpa slova sve postrojilo se jedni pored drugih.
Povezani popis je samo čvor i drugi čvor, a drugi čvor, a drugi čvor.
I umjesto da razbija sve čvorove zajedno i spremati ih contiguously
dobro jedni pored drugih u sjećanju,
nakon što je ovaj sljedeći pokazivač nam omogućuje pohranu čvorova gdje god, nasumce.
I onda vrsta žice ih sve zajedno do točke s jednog na sljedeći.
>> I ono što je velika prednost da je to imao preko niza?
Tijekom pohranjivanja svega contiguously samo zaglavi jedni pored drugih?
Sjećaš se? Da? >> Dinamička dodjela memorije?
>> Dinamička dodjela memorije u kojem smislu?
[Studentski] U koje možete zadržati što veći i da ne morate da se presele cijeli niz?
[Hardison] Točno. Dakle, s nizom, kada želite staviti novi element u sredini njega,
imate pomak sve kako bi prostor.
I kao što smo razgovarali o tome s reda,
to je razlog zašto smo zadržati tu glavu pokazivač,
tako da nećemo stalno kreće stvari.
Budući da dobiva skupo ako imaš veliku lepezu
a vi stalno radite ove slučajnih umetanja.
Dok s popisa, sve što morate učiniti je baciti na novi čvor,
podešavanje naputke, a vi ste učinili.
Što je sranje o tome?
Osim činjenice da to nije tako lako raditi s kao polje? Da?
[Daniel] Pa, mislim da je mnogo teže pristupiti određeni element u povezanoj listi?
[Hardison] Ne možeš skočiti u proizvoljni element u sredini povezane liste.
Kako ste to učiniti umjesto toga? >> Morate voditi kroz cijelu stvar.
[Hardison] Aha. Morate proći kroz jedan u isto vrijeme, jednu po jednu.
To je ogroman - to je bol.
Što je ostalo - tu je još jedan pad na to.
[Bosiljak] Ne mogu ići naprijed i natrag? Vi morate ići u jednom smjeru?
[Hardison] Aha. Pa kako ćemo riješiti to, ponekad?
[Bosiljak] dvostruko povezana popise? >> Točno. Postoje dvostruko povezane liste.
Tu su i - žao?
>> [Sam] Je li to isto kao i pomoću Pred stvar da -
Upravo sam se sjetio, nije li to ono što Pred stvar je za?
Zar to nije između dvostruko i pojedinačno?
[Hardison] Pogledajmo što se točno radi.
Dakle, ovdje mi ići. Evo popis oznaka.
Ovdje imamo predptr, ovdje. Je li to ono što su to govoriš?
Dakle, ovo je bio - on je oslobađanje popis i on pokušava pohraniti pokazivač na njega.
Ovo nije dvostruko, pojedinačno povezani-liste.
Možemo razgovarati o tome kasnije jer to govori o oslobađanju popis
i želim pokazati neke druge stvari na prvom mjestu.
ali to je samo - to je prisjećajući se vrijednost ptr
[Studentski] Oh, to je Prethodni pokazivač? >> Da.
Tako da možemo onda povećajte ptr sama prije nego što smo onda slobodno ono predptr je.
Budući da ne možemo bez ptr, a zatim pozvati ptr = ptr sljedeći, zar ne?
To bi bilo loše.
Tako ćemo vidjeti, vratiti se tom čovjeku.
>> Druga loša stvar o popisima je da, dok s nizom
samo moramo sve elemente i sami naslagane jedna pored druge,
Ovdje smo također uveli ovaj pokazivač.
Dakle, tu je dodatni komad memorije koji smo potrebe da koriste
za svaki element koji smo skladištenja u našem listu.
Mi smo dobili fleksibilnost, ali to dolazi po cijeni.
Ona dolazi s ovog vremenskog troška,
i to dolazi s ovim memorije cijeni previše.
Vrijeme u smislu da sada imamo proći kroz svaki element u polju
pronaći jedan na indeks 10, ili da bi bilo indeks 10 u nizu.
>> Samo jako brzo, kad smo dijagram iz ove liste,
obično držimo na glavi popisa ili prvi pokazivač popisa
i na umu da je to istina pokazivač.
To je samo 4 bajta. To nije stvarna čvor sama.
Pa vidiš da nema int vrijednost u tome, ne sljedeći pointer u njemu.
To je doslovno samo pokazivač.
To će ukazati na nešto što je stvarna čvor struct.
[Sam] pokazivač zove čvor? >> To je - ne. Ovo je pokazivač na nešto tipa čvor.
To je pokazivač na čvor struct. >> Oh, u redu.
Dijagram na lijevoj strani, kod na desnoj strani.
Možemo ga postaviti na null, koji je dobar način za početak.
Kada ga dijagram, ili ste napisati što null ili ste stavili liniju kroz njega se sviđa.
>> Jedan od najlakših načina da rade s popisima,
i pitamo što ne i upotrijebiti nesto i dodati vidjeti razlike između dvije,
ali prepending je definitivno lakše.
Kada upotrijebiti nesto, ovo je mjesto gdje ćete - kada upotrijebiti nesto (7),
idete i stvoriti struct čvor
i postavite prvi ukazati na to, jer sada, jer smo ga prepended,
to će biti na početku popisa.
Ako ćemo upotrijebiti nesto (3), koji stvara još jedan čvor, ali sada 3 dolazi prije sedam.
Dakle, mi smo u osnovi gura stvari na našem popisu.
Sada, možete vidjeti da je upotrijebiti nesto, ljudi ponekad zovu gurati,
jer ste pritom novi element na svom popisu.
To je također lako izbrisati na prednjem dijelu popisa.
Dakle, ljudi često će nazvati taj pop.
I na taj način, možete oponašati hrpu koristeći povezane liste.
Ups. Nažalost, sada smo uzimajući u dodati. Dakle, ovdje smo prepended (7), sada smo upotrijebiti nesto (3).
Ako smo prepended nešto drugo na ovom popisu, ako mi prepended (4),
onda bi ima 4, a zatim 3 i zatim 7.
Pa onda smo mogli pojaviti i ukloniti 4, remove 3, izvadite sedam.
Često više intuitivan način razmišljati o tome je s dodati.
Tako sam diagrammed out ono što će izgledati s dodati ovdje.
Ovdje, u prilogu (7) ne izgleda nešto drugačije
jer postoji samo jedan element u popisu.
I dodavanjem (3) stavlja na kraju.
Možda možete vidjeti upravo sada trik s dodati
je da, budući da smo samo znati gdje početak popisa je,
za dodavanje na popis morate hodati skroz kroz popis
doći do kraja, zaustavi, a zatim izgraditi čvor i prebirem sve dolje.
Žicu sve stvari gore.
Dakle, s upotrijebiti nesto, kao što smo upravo ripped kroz to jako brzo,
kada upotrijebiti nesto na popisu, to je prilično jednostavan.
>> Možete napraviti svoj novi čvor, uključivati ​​neke dinamičke raspodjele memorije.
Dakle, ovdje činimo čvora struct koristeći malloc.
Dakle malloc smo koristiti, jer to će izdvojiti memorije za nas za kasnije
jer ne želimo to - želimo ova memorija ustrajati za dugo vremena.
I mi smo dobili pokazivač na prostoru u memoriji da smo upravo dodijeljen.
Mi koristimo veličinu čvora, mi ne sumirati polja.
Mi ne ručno generirati broj bajtova,
umjesto toga koristiti sizeof tako da znamo da smo uzimajući odgovarajući broj bajtova.
Mi bi bili sigurni da testirati da naša malloc poziv uspio.
To je nešto što želite učiniti u cjelini.
Na modernim strojevima, ponestaje memorije nije nešto što je lako
osim ako ste dodjele tonu stvari i izradu ogroman popis,
ali ako ste izgradnju stvari za, recimo, kao što su iPhone ili Android,
vi nemate ograničene resurse memorije, pogotovo ako radiš nešto intenzivan.
Tako da je dobro da se u praksi.
>> Primijetit ćete da sam koristiti par različitih funkcija ovdje
da ste vidjeli da su vrsta nov.
Dakle fprintf baš kao printf
osim prvog argumenta je potok na koji želite ispisati.
U ovom slučaju, želimo ispisati na standardni pogreške nizu
koji se razlikuje od standardnog outstream.
Po defaultu pokazuje se na istom mjestu.
Ona također ispisuje na terminal, ali možete -
korištenje tih naredbi ste naučili o, preusmjeravanja tehnike
ste naučili o u Tommyjeva video za problematiku set 4, možete ga usmjeriti
na različitim područjima, a zatim izlaz, upravo ovdje, izlazi vaš program.
To je bitno kao i povratka s glavnom,
osim koristimo izlaz jer ovdje povratak neće učiniti ništa.
Mi nismo u glavnom, tako da povratka ne izađete iz programa kao što smo željeli.
Dakle, mi koristimo izlaz funkciju i dati mu šifru pogreške.
Onda ovdje smo postavili novog čvora vrijednost polja, njegova sam na terenu biti jednak i, a onda ćemo ga spojiti gore.
Postavili smo nove čvora pokraj pokazivača ukazati na prvi,
i tada prvi sada će ukazati na novi čvor.
Ovi prvi linija koda, mi zapravo izgradnju novog čvora.
Nije posljednja dva retka ove funkcije, ali prvima.
Vi zapravo možete izvući u funkciji, u funkciji pomoćnika.
To je često ono što mi je činiti, ja ga izvaditi u funkciju,
Ja bih to nazvao nešto poput graditi čvor,
i da čuva upotrijebiti nesto funkcija prilično mala, to je samo tri linije onda.
Ja uputili poziv na moj build čvora funkciju, a onda sam žice sve gore.
>> Konačna stvar koju želim vam pokazati,
i ja ću ti dodati i sve to na svoje,
je kako iteraciju preko popisa.
Postoji hrpa različitih načina da se ponove preko popisa.
U tom slučaju, mi ćemo naći duljinu liste.
Tako ćemo početi sa dužinom = 0.
To je vrlo slično pisanju strlen za niz.
To je ono što vam želim pokazati, ovo za petlju ovdje.
To izgleda nekako funky, to nije uobičajeno int i = 0, i <god, ja + +.
Umjesto toga, on je inicijalizirati varijablu naš n biti početak popisa.
A onda, dok je naša iteratora varijabla nije null, držimo ide.
To je zato što, prema konvenciji, kraj našem popisu će biti nula.
A onda povećavati, nego rade + +,
povezani popis ekvivalent + + je n = n-> next.
>> Ja ću vam popuniti praznine ovdje jer smo izvan vremena.
No, imajte to na umu, kao što rade na svojim spellr psets.
Povezani popisi, ako ste provedbi hash tablicu,
definitivno će doći u vrlo zgodan.
I nakon što je ovaj idiom za petlje preko stvari učinit će život puno lakše, nadam se.
Sva pitanja, brzo?
[Sam] Hoće li poslati popunjeni SLL i SC?
[Hardison] Aha. Ja ću poslati popunjene slajdove i završio SLL stog i queue.cs.
[CS50.TV]