[Powered by Google Translate] [Sekcio 6: Malpli Komfortaj] [Nate Hardison] [Universitato Harvard] [Jen CS50.] [CS50.TV] Bone. Bonvenon sekcio 6. Ĉi tiu semajno, ni tuj parolos pri datumstrukturoj en transeco, ĉefe ĉar ĉi tiu semajno problemo surtabligis spellr faras tutan faskon da malsamaj datumstrukturo tuŝo. Ekzistas multajn malsamajn manierojn vi povas iri per la problemon aro, kaj la pli datumstrukturoj vi scias pri la pli malvarmeta aĵoj vi povas fari. 

Do ni komenci. Unue ni iras por paroli pri piloj, la pilo kaj vosto datumstrukturoj, ke ni tuj paroli. Provizejon kaj vostoj estas vere utila, kiam ni komencis paroli pri grafikaĵoj, kiuj ni ne tuj faros tiel de nun. Sed ili estas vere bona por kompreni unu el la grandaj fundamentaj datumstrukturoj de CS. La priskribo de la problemo aro specifo, se vi tiri ĝin, ĝi raportas piloj kiel simila al la amaso de manĝoĉambro pletoj, ke vi havas en la kafejo ĉe la manĝ salonoj kie al la manĝ personaro venos kaj metas la manĝ pletoj kuris post ili jam purigis ilin, ili pilo ili unu super la alia. Kaj poste, kiam la infanoj venis por ricevi manĝon, ili tiri la pletoj ekstere, unue la plej supra, tiam la sub ĝi, tiam la sub tio. Do, en efekto, la unua pleto ke la manĝ bastonon sufoki estas la lasta kiu prenas demetis. La lasta kiu la manĝ bastonon surmetis estas la unua kiu prenas demetis por vespermanĝo. En la problemon aro de spec, kiujn vi povas elŝuti, se vi ne havas jam, ni parolas pri modeli pilo datumoj stucture uzante tian struct. 

Do kion ni havas ĉi tie, ĉi tiu estas simila al kio estis prezentita en konferenco, krom en prelego ni prezentas ĉi kun ints kontraste char * s. Ĉi tuj estos pilo kiu stokas kio? Daniel? Kion ni stokante en ĉi pilo? [Daniel] Ĉenoj? >> Ni stokante kordoj en ĉi pilo, precize. Vi bezonas havi por krei pilo estas tabelo de aparta kapablo, kiu en ĉi tiu kazo, kapablo tuj estos en ĉiuj kaskedoj ĉar ĝi estas konstanto. Kaj tiam krom la tabelo, ĉiuj ni devas spuri estas la aktuala grandeco de la tabelo. Unu afero noti tie jen speco de malvarmeta estas ke ni kreas la plata datumstrukturo sur alia datumstrukturo, la tabelo. Estas malsamaj manieroj por apliki piloj. Ni ne faros ĝin sufiĉe ankoraŭ, sed espereble post fari la kunligita-listo problemoj, vi vidos, kiel vi povas facile apliki en pilo sur supro de ligitaj listo tiel. Sed nuntempe, ni batos la tabeloj. Do denove, ni nur bezonas estas tabelo kaj ni nur devas sekvi la grandeco de la tabelo. [Sam] Pardonu, kial do vi diris la pilo estas sur la kordoj? Al mi ĝi ŝajnas kiel la kordoj estas ene de la pilo. [Hardison] Yeah. Ni kreas, ni prenas niajn tabelo datumstrukturo - ke estas granda demando. Do la demando estas kial, cxar la homo kiu rigardas tiun linio, kial ni diras ke la pilo estas ĉe la kordoj, ĉar tie ĝi aspektas kiel la kordoj estas ene de la pilo? Kiu estas plene la kazo. Kion mi aludis al estis ke ni havas aron datumstrukturo. Ni havas aron da char * s, ĉi tabelo de kordoj, kaj tuj aldoni al tiu por krei la plata datumstrukturo. 

Do pilo estas iomete pli kompleksa ol tabelo. Ni povas uzi tabelo por konstrui pilo. Do tie estas kie ni diras, ke la pilo estas konstruita sur supro de tabelo. Same, kiel mi diris antaŭe, ni povas konstrui stako sur supro de ligitaj listo. Anstataŭ uzi tabelo por teni nian elementoj, ni povus uzi ligillisto teni nian elementoj kaj konstruu la pilo ĉirkaŭ tiu. Ni marŝas tra kelkaj ekzemploj, rigardante iom da kodo, por vidi kio reale okazas tie. Sur la maldekstra, mi dejxetita kion tiu pilo struct devus aspekti en memoro se kapablo estis # difinita al esti kvar. Ni havas nian kvar-era char * tabelo. Ni havas kordoj [0], kordoj [1], kordoj [2], kordoj [3], kaj poste tiu lasta spaco por niaj grandeco entjero. Ĉu ĉi sencon? Okay. Jen kio okazas, se kion mi faras sur la dekstra, kiu estos mia kodon, estas simple deklari struct, a plata struct nomita s. Ĉi tio estas kion ni ricevas. Ĝi demetas tiun spuron en memoro. La unua demando estas kio estas la enhavo de ĉi tiu pilo struct? Nun ili estas nenio, sed ili estas ne plene nenion. Ili estas ĉi tiu speco de rubo. Ni ne havas ideon kio estas en ili. Kiam ni deklaras pilo j, ni simple ĵeti ke sur supro de memoro. Estas ia kiel deklari int i kaj ne inicializar ĝin. Vi ne scias kio estas en tie. Vi povas legi kio estas en tie, sed eble ne super helpema. Unu aferon vi volas ĉiam memoras fari estas pravalorizi ajn bezonas por esti inicializado. En ĉi tiu kazo, ni iras al pravalorizi la grandecon al esti nulo, ĉar tio tuj turni ekster al esti tre grava por ni. Ni povus antaŭeniri kaj pravalorizi ĉiuj punteros, ĉiuj char * s, esti iu komprenebla valoro, probable nula. Sed ne estas plene necesa ke ni faras tion. 

Nun, la du ĉefaj operacioj sur piloj estas? Neniu memoras de prelego kion vi faras kun piloj? Jes? [Stella] Pushing kaj krevi? >> Ekzakte. Pelante kaj krevi estas la du ĉefaj operacioj sur piloj. Kaj kion tio puŝo fari? >> Ĝi metas ion sur la supro de la pilo, kaj tiam krevi prenas ĝin. [Hardison] Ekzakte. Do puŝas puŝas iun sur supro de la stako. Estas kiel la manĝ bastonon metante manĝoĉambro pleto sur la vendotablo. Kaj krevi prenas manĝoĉambro pleto off de la stako. Ni marŝas tra kelkaj ekzemploj de tio, kio okazas kiam ni puŝi aĵoj en la stako. Se ni devis puŝi la ĉenon 'saluton' sur nia stako, ĉi tio estas kion la diagramo devus aspekti nun. Vidu kio okazas? Ni puŝis en la unua elemento de nia kordoj tabelo kaj ni upped nia grandeco grafo esti 1. Do, se ni rigardas la diferencon inter la du diapozitivoj, jen 0, jen antaŭ la puŝo. Jen post la puŝo. Antaŭ la puŝo, post la puŝo. Kaj nun ni havas unu elemento en nia stako. Ĝi estas la ĉeno "saluton", kaj tio estas ĝi. Ĉio alia en la tabelo, en nia kordoj tabelo, estas ankoraŭ rubo. Ni ne inicializado ĝin. Supozu ke ni puŝi alia ĉeno sur nia stako. Ni tuj peli "mondo" en ĉi tiu tempo. Do vi povas vidi "mondo" tie iras sur "saluton", kaj la grandeco grafo iras al 2. Nun ni povas puŝi "CS50", kaj kiu iros sur denove. Se ni reiru, vi povas vidi kiel ni puŝas aĵoj sur la stako. Kaj nun ni atingos popo. Kiam ni pusxis io ekstere de la pilo, kio okazis? Neniu vidas la diferencon? Estas bela subtila. [Studenta] La grandeco. >> Jes, la grandeco ŝanĝis. 

Kion alian vi estus atendita ŝanĝi? [Studenta] La kordoj, ankaŭ. >> Ĝuste. La kordoj ankaŭ. Rezultas, ke kiam vi faras ĝin tiamaniere, ĉar ni ne kopiante la elementoj en nian pilo, ni efektive ne devas fari ion, ni povas simple uzi la grandeco teni spuro de la nombro de aĵoj en nia tabelo por ke, kiam ni popo denove, denove ni simple dekremento nia grandeco suben al 1. Ne necesas efektive iros kaj anstatauxigas nenion. Speco de funky. Ĝi rezultas ke ni tipe nur lasi aferojn sole ĉar estas malpli da laboro por ni fari. Se ni ne devas reiri kaj anstatauxigas ion, tiam kial fari ĝin? Do kiam ni popo dufoje for de la pilo, cxiuj faras estas dekremento la grandeco kelkajn fojojn. Kaj denove, ĉi tiu estas nur ĉar ni ne kopii aferojn en nian pilo. Jes? Iru antaŭen. [Studento, nekomprenebla] >> Kaj poste kio okazas kiam vi puŝi ion denove? Kiam vi puŝi ion pli, kie ĝi iras? Kie ĝi iras, Bazilo? >> Into kordoj [1]? >> Ĝuste. Kial ne iru en kordoj [3]? [Bazilo] Ĉar ĝi forgesis ke estas io en kordoj [1] kaj [2]? [Hardison] Ekzakte. Nia pilo, esence, "forgesis" kiu tenis al io en kordoj [1] aŭ kordoj [2], do, kiam ni peli "woot", ĝi simple metas ke en la elemento en kordoj [1]. Ĉu estas demandoj pri kiel tio funkcias, al baza nivelo? [Sam] Do tiu estas ne dinamika en ajna maniero, en terminoj de kvanto aŭ en terminoj de la grandeco de la pilo? [Hardison] Ekzakte. Tio estas - la punkto estis, ke tiu ne estis dinamike growning pilo. Tio ĉi estas stako kiu povas teni, maksimume, kvar char * s, maksimume kvar aĵoj. Se ni devis provi kaj puŝi kvina afero, kion vi opinias devus okazi? [Studentoj, nekomprenebla] [Hardison] Ekzakte. Estas nombro de aĵoj kiuj povus okazi. Ĝi povus seg kulpo, depende de kion ni estis - kiel ekzakte ni realiganta la dorso-fino. Ĝi povus anstataŭigi. Ĝi povus esti ke buffer overflow ke ni raportis en klaso. Kio estus la plej evidenta afero, ke eblus anstataŭigi se ni provis peli ekstra afero en nia stako? Do vi menciis buffer overflow. Kio povus esti la afero kiu get skribita super aŭ stomped sur se ni superfluis hazarde por provi puŝi ekstra afero? [Daniel, nekomprenebla] >> Eblaj. Sed komence, kio povus okazi? Kio se ni provis peli kvaran aferon? Eble anstataŭigi la grandeco, almenaŭ kun ĉi tiu memoro diagramo kiu ni havas. 

En la problemon aro specifo, kiu estas kion ni tuj estos apliki hodiaŭ, kion ni volas fari estas simple reveni falsaj. Nia puŝo metodo tuj revenos bulea valoro, kaj ke bulea valoro estos vera se la antaŭenpuŝo sukcesos kaj malvera se ni ne povas puŝi ion pli ĉar la pilo estas plena. Ni marŝas tra iom de tiu kodo nun. Jen nia puŝo funkcio. Nia puŝo funkcio por pilo tuj prenos en la ĉeno por meti sur la stako. Oni tuj revenos vera se la kordo sukcese puŝis sur la pilo kaj falsaj alie. Ajna sugestojn sur kio povus esti bona unua afero por fari tie? [Sam] Se grandeco egalas kapablon tiam revenu falsa? [Hardison] Bingo. Bela laboro. Se la grandeco estas la kapablo, ni tuj revenos falsaj. Ni ne povas meti ion pli en nia stako. Alie, ni volas meti iun sur la supro de la stako. Kio estas "la supro de la pilo," komence? [Daniel] Grandeco 0? >> Grando 0. Kio estas la pinto de la pilo post ekzistas unu afero en la pilo? Missy, ĉu vi scias? [Missy] Unu. >> Grando estas unu, precize. Vi observos aldonante al la grandeco, kaj ĉiufoje vi metante en la nova elemento en la indekso grandeco en la tabelo. Ni povas fari ĝin kun tiu speco de unu-Liner, se tiu havas sencon. Do ni havas nian kordoj tabelo, ni tuj aliri gxin cxe la grandeco indico, kaj ni ĵus tuj stoki niajn char * en tie. Rimarku kiel ne estas ŝnuro kopiado okazas en ĉi tie, neniu dinamika atribuo de memoro? Kaj tiam Missy alportis tion, kion ni nun devas fari, ĉar ni stokis la ĉenon en la taŭgan lokon en la tabelo, kaj sxi diris ke ni devis pliigo de la grandeco de unu por ke ni estas pretaj por la sekvanta puŝo. Do ni povas fari tion kun s.size + +. Je ĉi tiu punkto, ni pelis en niajn tabelo. Kio estas la lasta afero, kiun ni devas fari? [Studenta] Reveno vera. >> Return vera. Do ĝi estas bela simpla, bela simpla kodo. Ne tro multe. Kiam vi envolvis via kapo ĉirkaŭ kiel la pilo funkcias, ĉi tiu estas sufiĉe simpla por apliki. 

Nun, la sekvanta parto de ĉi tiu estas krevi ĉenon off de la stako. Mi tuj donos al vi infanoj tempon por labori pri tiu iomete. Estas preskaŭ esence la dorsflanko de kion ni faris ĉi tie en sakon. Kion mi faris fakte - oops. Mi booted aperigis aparaton super ĉi tie, kaj en la aparaton, Mi tiris supren la problemo starigis 5 specifo. Se ni zomi tie, ni povas vidi min ĉe cdn.cs50.net/2012/fall/psets/pset5.pdf. Ĉu vi infanoj elŝutebla ĉi kodo ke tio situas tie, section6.zip? Bone. Se vi ne faris tion, faru ke ĝuste nun, vere rapide. Mi faros ĝin en mia fina fenestro. Mi vere faris ĝin ĉi tie. Yeah. Jes, Sam? >> Mi havas demandon pri kial vi diras s.string-ejon krampoj de amplekso = str? Kio estas str? Estas ke difinita ie antaŭe, aŭ - ho, en la char * str? [Hardison] Jes, ĝuste. Tio estis la argumento. >> Ho, bone. Pardonu. [Hardison] Ni preciziganta la kordo peli in La alia demando kiu povus antaŭvidi ke ni ne vere parolas pri ĉi tie estis ni prenis koncedis, ke ni havis tiun variablon nomita s kiu estis en atingo kaj alirebla al ni. Ni prenis por koncedis ke s estis ĉi pilo struct. Do rigardante malantaŭen en ĉi tiu puŝo kodo, vi povas vidi, ke ni faras aĵojn kun ĉi ĉeno kiu got pasis en sed tiam subite, ni aliru s.size, kiel, kien s venis? En la kodo kiun ni iras por rigardi en la sekcio arkivo kaj tiam la aĵoj kiujn vi povas fari en via problemo aroj, ni faris nian pilo struct tutmonda variablo tiel ke ni povas havi aliron al ĝi en ĉiuj niaj malsamaj funkcioj sen devi permane pasi ĝin ĉirkaŭ kaj fordoni ilin por referenco, faru cxion tian materialon al ĝi. Ni nur cheating iomete, se vi volas, fari aĵoj pli bela. Kaj tio estas io ni faras ĉi tie, ĉar tio estas nur por amuzo, pli facilas. Ofte, vi vidos homojn fari tion se ili havas unu grandan datumstrukturo ke tio esti operaciita ene de sia programo. 

Ni iru reen super la aparaton. Ĉu ĉiuj sukcese akiri la section6.zip? Ĉiuj maldensigi ĝin uzante maldensigi section6.zip? Se vi iras en la sekcio 6 directory - Aah, la tuta loko - kaj vi listigi kio estas en tie, vi vidas, ke oni devas tri malsamaj. c dosierojn. Vi havas voston, oni SLL, kiu estas unuope-ligillisto, kaj pilo. Se vi malfermas stack.c, vi povas vidi, ke ni havas ĉi struct difinita por ni, la ĝusta struct ke ni nur parolis pri la diapozitivoj. Ni havas nian tutmondan variablo por la pilo, ni havas nian puŝo funkcio, kaj tiam ni havas niajn popo funkcio. Mi metis la kodon por peli reen sur la glito tie, sed kion mi ŝatus you guys fari estas, al la plej bonaj de via kapableco, iru kaj efektivigu la popo funkcio. Kiam vi implementado ĝin, vi povas kompili tiun kun fari pilo, kaj poste ruli la rezulta pilo ruleblan, kaj kiu kuros ĉio ĉi testo kodo cxi tie ke estas en ĉefaj. Kaj ĉefa prizorgas fakte farante la puŝo kaj pop alvokoj kaj certigi ke ĉiu iras tra ĉiuj pravas. Ĝi ankaŭ inicializa la pilo grandeco ĉi tie tial vi ne devas zorgi pri inicializar tio. Vi povas supozi, ke ĝi estas estis gxuste inicializado por la tempo kiun vi konsenti li en la populara funkcio. Ĉu tio havas sencon? Do jen ni iru. Jen la antaŭenpuŝo kodo. Mi donos al vi infanoj 5 aŭ 10 minutoj. Kaj se vi havas demandojn en la provizora dum vi kodigo, bonvolu peti ilin laŭte. Do, se vi ricevas al batas punkto, nur demandi. Lasu min scii, lasu ĉiuj aliaj scias. Labori kun via najbaro ankaŭ. [Daniel] Ni nur apliki popo nun? >> Nur popo. Kvankam vi povas kopii la efektivigo de puŝo se vi ŝatus por ke la provado funkcios. Ĉar ĝi estas malfacile kontroli tion atingi en - aŭ, estas malfacile kontroli krevi aĵoj el stako se estas nenio en la pilo por komenci. 

Kio estas popo supozis esti reveni? La elemento de la supro de la stako. Oni supozis akiri la elemento ekstere de la pinto de la stako kaj tiam dekremento de la grandeco de la pilo, kaj nun vi perdis la elemento sur la supro. Kaj tiam vi revenos al la elemento sur la supro. [Studento, nekomprenebla] [Hardison] Do kio okazas se vi faros tion? [Studento, nekomprenebla] Kio finas okazas estas ke vi probable alirante ĉu ero kiu ne estis inicializado tamen, do, via kalkulo de kie la lasta elemento estas estas malŝaltita. Do jen, se vi rimarkos, en puŝo, ni aliru kordoj ĉe la s.size elemento ĉar ĝi estas nova indekso. Ĝi estas la nova supera parto de la pilo. Dum en la popo, s.size tuj estos la venonta spaco, la spaco kiu estas sur la supro de ĉiuj elementoj en via pilo. Do la supre-pli elemento estas ne s.size, sed prefere, estas sub tio. 

La alia afero por fari, kiam vi - en popmuziko, estas vi devas dekremento la grandeco. Se vi memoras reen al nia eta figuro dekstre tie, vere, la sola afero ke ni vidis okazas kiam ni nomas popo estis, ke ĉi tiu grandeco faligis, unue al 2, tiam al 1. Tiam, kiam ni pelis nova elemento en, estus iri en konvenaj makulo. [Bazilo] Se la s.size estas 2, tiam ne estis al elemento 2, kaj tiam vi volas volas popo tiu elemento ekstere? Do, se ni iris al - >> Do ni rigardu tiun alian fojon. Se ĉi tiu estas nia stako ĉe ĉi tiu punkto kaj ni nomas popo, je kiu indico estas la supre-pli elemento? [Bazilo] Al 2, sed tuj popo 3. >> Ĝuste. Do tie estas kie nia grandeco estas 3, sed ni volas popo la elemento en indekso 2. Ĝi estas tiu tipa speco de off por kiu vi havas kun la nulo-indeksado de tabeloj. Do vi volas popo la tria elemento, sed la tria elemento estas ne indekso 3. Kaj la kialo ni ne devas fari tion minus 1 kiam ni puŝas estas ĉar ĝuste nun, vi rimarkos ke la supre-pli elemento, se ni devis puŝi ion alian sur la stako ĉe ĉi tiu punkto, ni volus peli ĝin en indekso 3. Kaj ĝuste tial okazas, ke la grandeco kaj la indicoj laŭliniigi kiam vi premas. 

Kiu havas laborante pilo efektivigo? Vi havas funkciantan pilo unu. Ĉu vi popo laboras ankoraŭ? [Daniel] Jes. Mi kredas tiel. >> Programo kuras kaj ne seg faulting, ĝi estas presi el? Ĉu ĝi presi "sukceso" kiam vi kuros ĝin? Yeah. Faru pilo, ruli ĝin, se ĝi presas el "sukceso" kaj ne iras eksplodo, tiam ĉiuj estas bonaj. Bone. Ni transiru al la aparaton vere rapide, kaj ni trairu ĉi. Se ni rigardas kio okazas ĉi tie kun popo, Daniel, kio estis la unua afero, kiun vi faris? [Daniel] Se s.size estas pli granda ol 0. [Hardison] Okay. Kaj kial vi faris tion? [Daniel] Por certigi ke io interne de la stako. [Hardison] Ĝuste. Vi volas provi certigi ke s.size estas pli granda ol 0; alie, kion vi volas esti okazos? [Daniel] Reveno nula? >> Reiri nula, precize. Do se s.size estas pli granda ol 0. Do kion ni tuj fari? Kion ni faru se la pilo ne estas malplena? [Stella] Vi dekremento la grandeco? >> Vi dekremento la grandecon, okay. Do kiel vi faris tion? >> S.size--. [Hardison] Granda. Kaj poste kion vi faris? [Stella] Kaj poste mi diris reveno s.string [s.size]. [Hardison] Granda. Alie vi revenos nula. Jes, Sam? [Sam] Kial ĝi ne bezonas esti s.size + 1? [Hardison] Plus 1? >> Jes. >> Got ĝin. [Sam] Mi pensis ke vi prenas 1 out, tiam vi tuj estos reveni ne kiu ili petis. [Hardison] Kaj jen ĝuste kion ni parolis pri kun ĉi tiu tuta afero de 0 indeksoj. Do, se ni zoom reen super tie. Se ni rigardas this guy ĉi tie, vi povas vidi, ke kiam ni popo, ni krevi la elemento en indekso 2. 

Do ni malpliigi niajn grandeco unua, tiam nia grandeco kongruas nia indekso. Se ni ne dekremento la grandeco unua, tiam ni devas fari grandeco -1 kaj tiam dekremento. Granda. Ĉiuj bonaj? Demandojn pri tiu? Estas nombro de malsamaj manieroj por skribi ĉi tiel. Fakte, ni povas fari iun eĉ - ni povas fari unu-Liner. Ni povas fari unu-linio reveno. Do ni povas reale dekremento antaŭ ol ni reveni por fari tion. Do meti la - antaŭ la s.size. Tio faras la linio vere densa. Kie la diferenco inter la - s. Grandeco kaj s.size-- estas ke ĉi postfix - ili nomas ĝin postfix ĉar la - venas post la s.size-- signifas ke s.size estas taksita la celo trovi la indekso kiel estas nuntempe kiam ĉi tiu linio estas plenumata, kaj tiam ĉi - okazas post la linio gets ekzekutita. Post la elemento en indekso s.size aliras. Kaj tio ne estas kion ni volas, ĉar ni deziras la dekremento okazi unue. Othewise, ni tuj estos alirante la tabelo, efektive, el baroj. Ni tuj estos alirante la elemento super kiu ni efektive volas aliri. Yeah, Sam? >> Ĉu estas pli rapida aŭ uzu malpli RAM fari en unu linio aŭ ne? [Hardison] Honeste, vere dependas. [Sam, nekomprenebla] >> Jes, tio dependas. Vi povas fari tradukilon lertaĵoj por ricevi la tradukilo por rekoni ke, kutime, mi imagas. 

Do ni menciis iomete pri tiu tradukilo optimumigo stuff ke vi povas fari en kompili, kaj tio estas la speco de afero kiun tradukilo povus kapabli eltrovi, kiel ho hey, eble mi povas fari ĉi ĉiujn en unu operacio, kiel kontraŭ ŝarĝante la grandeco variablo en el RAM, decrementing ĝin, stokante ĝin eksteren, kaj poste ŝarĝas ĝin en alia fojo por procesi la resto de ĉi tiu operacio. Sed tipe, ne, tio ne estas la speco de afero ke tuj faros vian programon signife pli rapide. Plu demandojn sur piloj? 

Do puŝas kaj krevi. Se vi infanoj volas provi la hacker eldono, kion ni faris en la hacker eldono estas efektive foriris kaj ili faris tiun pilo kreski dinamike. La defio estas unuavice ĝis tie en la antaŭenpuŝo funkcio, elŝeligi kiel fari, ke tabelo kreski kiel vi observu pelante pli kaj pli elementoj sur la stako. Ĝi fakte ne estas tro da aldonaj kodo. Nur alvokon al - vi devas memori por ricevi la alvokoj al malloc tien konvene, kaj poste eltrovi, kiam vi iras por voki realloc. Tio estas amuza defio se vi estas interesata. 

Sed provizore, ni movi plu, kaj ni parolos pri vostoj. Rulumu tra tie. La vosto estas proksima frato de la pilo. Do, en la pilo, aĵoj kiuj estis metitaj en la lasta estis la unuaj aferoj tiam esti konsultita. Ni havas ĉi lasta en, unua el, aŭ LIFO, ordigi. Dum en la vosto, kiel vi atendus de kiam vi staris en linio, la unua persono por ricevi en linio, la unua afero por eniri en la vosto, estas la unua aĵo kiun gets rekuperita de la vico. Vostoj estas ankaŭ ofte uzata kiam ni pritraktas grafikaĵoj, kiel ni parolis pri mallonge kun piloj, kaj vostoj estas ankaŭ utila por multaj aliaj aĵoj. Unu afero kiu venas supren ofte provas subteni, ekzemple, a ordo listo de eroj. Kaj vi povas fari tion kun tabelo. Vi povas subteni ordo listo de aferoj en tabelo, sed kie kiu alvenas malfacila estas tiam vi ĉiam devas trovi la taŭga loko por enmeti lin proksima. Do se vi havas tabelo de nombroj, 1 ĝis 10, kaj tiam vi volas pligrandigi ke ĉiuj nombroj 1 ĝis 100, kaj vi estas duumaj tiuj nombroj en hazarda ordo kaj provas teni ĉio ordo kiel vi iros tra vi finos devi fari multajn movo. Kun certaj tipoj de vostoj kaj iuj tipoj de suba datumstrukturoj, vi povas fakte teni ĝin sufiĉe simpla. Vi ne devas aldoni ion, kaj poste reshuffle la tuta afero ĉiufoje. Nek vi devas fari multajn movo de la internaj elementoj ĉirkaŭe. Kiam ni rigardas queue, vi vidos ke - same en queue.c en la sekcio kodo - la struct ke ni donis al vi estas vere simila al la struct ke ni donis al vi por pilo. 

Estas unu escepto al ĉi tio, kaj ke unu escepto estas ke ni havas cxi tiun plian entjero nomata la kapo, kaj la kapo tie estas por konservanta trako de la kapo de la vosto, aŭ la unua elemento en la vico. Kun pilo, ni povis konservi trako de la elemento, ke ni estis por elsxuti, aŭ la supro de la pilo, uzante nur la grandeco, dum kun vosto, ni devi trakti ekstremaj kontraŭaj. Ni provas Tack aĵoj sur fine, sed tiam revenu tion for de fronto. Do efektive, kun la kapo, ni havas la indekso de la komenco de la vosto, kaj la grandeco donas al ni la indekso de la fino de la vosto tiel ke ni povas elsxuti tion de la kapo kaj aldoni aferojn al la vosto. Dum kun la pilo, ni estis nur iam pritraktanta la supro de la stako. Ni neniam devis aliri al la fundo de la stako. Ni nur aldonis tion al la supro kaj prenis tion for de la supro do ni ne bezonas tiun ekstran kampo ene de nia struct. Ĉu tio ĝenerale havas sencon? Bone. Jes, Charlotte? [Charlotte, nekomprenebla] [Hardison] Tio estas granda demando, kaj kiu estis unu, kiu aperis en prelego. Eble promenante tra kelkaj ekzemploj estos ilustri kial ni ne volas uzi kordoj [0] kiel la estro de la vico. 

Do imagu, ke ni havas niajn queue, ni tuj nomas ĝin vosto. Komence, kiam ni ĵus instantiated ĝin, kiam ni nur deklaris ĝin, ni ne inicializado nenion. Estas ĉio rubo. Do kompreneble ni volas certigi, ke ni pravalorizi ambaŭ la grandeco kaj la kapo kampoj al esti 0, iu racia. Ni povus ankaŭ antaŭeniri kaj nula el la eroj en nia vico. Kaj fari tiun diagramon konvena, rimarki ke nun nia vico nur teni tri elementoj; dum nia stako povis teni kvar, nia vosto povas nur teni tri. Kaj tio estas nur por fari la diagramo indas. La unua afero kiu okazas ĉi tie estas ni enqueue la ĉeno "hi". Kaj ĝuste kiel ni faris kun la pilo, nenio terure malsamajn tie, ni ĵeti la ŝnuron en ĉe kordoj [0] kaj pliigo nia grandeco per 1. Ni enqueue "bye", ĝi prenas surmetis. Do ĉi aspektas kiel stako plejparte. Ni komencas ekstere tie, nova elemento, nova elemento, grandeco subtenas suprenirantaj. Kio okazas ĉe ĉi tiu punkto, kiam ni volas dequeue ion? Kiam ni volas dequeue, kiu estas la elemento kiu ni volas dequeue? [Bazilo] Ĉenoj [0]. >> Nulo. Ĝuste pravas, Bazilo. Ni volas forigi la unua kordo, ĉi tiu, "hi". Do kio estas la alia afero kiu ŝanĝis? Rimarku, kiam ni pusxis io ekstere de la pilo, ni ĵus ŝanĝis la grandecon, sed ĉi tie, ni havas kelkajn aĵojn kiuj ŝanĝon. Ne nur faras la grandecon ŝanĝo, sed la kapon ŝanĝojn. Tiu tuj reen al Carlota punkto antaŭa: kial ni havas ĉi kapon tiel? Ĉu havas sencon nun, Charlotte? >> Speco de. [Hardison] Speco de? Do kio okazis kiam ni dequeued? Kion la kapo fari tion nun estas interesaj? [Charlotte] Ho, ĉar ĝi ŝanĝis - okay. Mi vidas. Ĉar la kapo - kie la kapo indikante ŝanĝoj en terminoj de la loko. Ĝi ne plu ĉiam la nulo indekso unu. >> Jes, ĝuste. Kio okazis estis se dequeueing la alta elemento estis farita kaj ni ne havas tiun kapon kampo ĉar ni ĉiam nomante tiun ĉenon ĉe 0 indekso la kapo de nia vosto, tiam ni devus ŝanĝi la resto de la vosto sube. Necesus ŝanĝi "bye" el de kordoj [1] al la kordoj [0]. Kaj ŝnuro [2] malsupren al kordoj [1]. Kaj ni devus fari tion por la tuta listo de elementoj, en la tuta tabelo de elementoj. Kaj kiam ni faras tion kun tabelo, kiu alvenas vere peniga. Do jen, ne granda interkonsento. Ni nur havas tri elementoj en nia tabelo. Sed se ni havis voston el mil eroj aŭ miliono elementoj, kaj tiam subite, ni komencos fari aron da dequeue nomas ĉiujn en buklo, aĵoj vere tuj bremsi kiel ŝanĝas ĉiun malsupren senĉese. Vi scias, ŝanĝi per 1, shift per 1, shift per 1, shift per 1. Anstataŭe, ni uzas ĉi kapo, ni nomas ĝin "pointer" kvankam ĝi ne estas vere puntero en la strikta senco, temas ne puntero tipo. Ne estas int * aŭ char * aŭ io kiel tio. Sed gxi montras aŭ indikante la kapo de nia vico. Yeah? 

[Studenta] Kiel dequeue scias ĝuste popo ekstere kio ajn en la kapon? [Hardison] Kiel dequeue scias popo ekstere ajn estas en la kapo? >> Ĝuste, jes. >> Kio ĝi estas rigardanta estas ĝuste kion la kapo kampo estas agordita por. Do en tiu unua kazo, se ni rigardas ĝuste tie, nia kapo estas 0, indico 0. >> Ĝuste. [Hardison] Do nur diras bone, bone, la elemento en indekso 0, la ĉeno "hi", estas la elemento al la kapo de nia vico. Do ni tuj dequeue ke ulo. Kaj tio estos la elemento kiu prenas revenis al la telefonanto. Jes, Saad? >> Do la kapo esence fiksas la - kie vi tuj indekso ĝin? Tio estas la komenco de ĝi? >> Jes. >> Bone. [Hardison] Tio igas la nova komenco por niaj tabelo. Do kiam vi dequeue io, ĉio vi devas fari estas atingi la elemento en indekso q.head, kaj tio estos la elemento kiu vi volas dequeue. Vi ankaŭ devas dekremento la grandeco. Ni vidos en iom kie aĵoj iom malfacila per ĉi. Ni dequeue, kaj nun, se ni enqueue denove, kie ni enqueue? Kie la sekvanta elemento iri en nia vosto? Ke ni volas enqueue la ĉeno "CS". En kiun indekso ĉu ĝi iru? [Studentoj] Ĉenoj [2]. >> Du. Kial 2 kaj ne 0? [Bazilo] Ĉar nun la kapo estas 1, tiel ke estas kiel la komenco de la listo? [Hardison] Ĝuste. Kaj kion signifas la finon de la listo? Kion ni uzas por indiki la finon de nia vosto? La kapo estas la kapo de nia vosto, la komenco de nia vico. Kio estas la fino de nia vosto? [Studentoj] Grandeco. >> Grando, precize. Tiel niaj novaj elementoj iru ĉe grandeco, kaj la elementoj, ke ni demetas elspezas en kapo. Kiam ni enqueue la sekvanta elemento, ni metas ĝin en je grandeco. [Studenta] Antaŭ ol vi metis tiun en kvankam, grandeco estis 1, right? [Hardison] Ĝuste. Do ne sufiĉe je grandeco. Grandeco +, ne +1, sed + kapo. Ĉar ni ŝanĝis ĉiun por la kapo kvanto. Do jen, nun ni havas vosto de amplekso 1 kiu komenciĝas je indekso 1. La vosto estas indekso 2. Jes? 

[Studenta] Kio okazas kiam vi dequeue kordoj [0], kaj la ŝnuroj 'fendoj en memoro nur get malplenigis, esence, aŭ nur forgesis la pasvorton? [Hardison] Yeah. Tiusence, ni simple forgesas ilin. Se ni stokante kopiojn de ili por - multaj datumstrukturoj ofte stoki sia kopiojn de la elementoj por ke la persono administri la datumojn strukturo ne devas maltrankviligi pri kie ĉiuj tiuj punteros iras. La datumstrukturo tenas al ĉiu, tenas en la tuta kopioj, certigi ke ĉiu persistas taŭge. Tamen, en ĉi tiu kazo, tiuj datumstrukturoj justa, por simpleco, ne farante kopiojn de io, kio ni stokante en ili. [Studenta] Tia estas ĉi tiu kontinua tabelo de -? >> Jes. Se ni retrorigardas al kio la difino estis de ĉi tiu strukturo, ĝi estas. Estas nur normo tabelo kiel vi vidis, tabelo de char * s. Ĉu tio -? >> Jes, mi ĵus demandis se vi eventuale elĉerpas de memoro, en iu punkto, se vi havas ĉiujn tiujn malplenajn makuloj en via tabelo? [Hardison] Jes, tio estas bona punkto. 

Se ni rigardas kio okazis nun en ĉi tiu punkto, ni plenigis niajn vosto, ĝi aspektas. Sed ni ne vere plenigis niajn vosto ĉar ni havas voston jen grandeco 2, sed komenciĝas je indico 1, ĉar tie estas kie nia kapo pointer is. Kiel vi diris, ke elemento en kordoj [0], ĉe indeksa 0, estas ne vere ekzistas. Ne en nia vosto plu. Ni simple ne tedis iri en kaj anstatauxigas ĝin kiam ni dequeued ĝin. Do kvankam ĝi aspektas kiel ni ne plu havas memoron, ni vere ne havas. Tiu loko estas havebla por ni uzas. La taŭga konduto, se ni devis provi kaj unua dequeue ion kiel "bye", kiu estus popo bye malproksime. Nun nia queue komencas indekso 2 kaj estas de amplekso 1. Kaj nun se ni provas kaj enqueue io pli, diras 50, 50 iru en ĉi loko en indekso 0 ĉar ĝi estas ankoraŭ disponebla por ni. Jes, Saad? [Saad] Does kiuj okazas aŭtomate? [Hardison] Ĝi ne okazas tute aŭtomate. Vi devas fari la math fari ĝin funkcii, sed esence kion ni faris estas ni nur envolvis ĉirkaŭe. [Saad] Kaj ĉu bone se tiu havas truon en la mezo de gxi? [Hardison] Ĝi estas se ni povas fari la math ellabori konvene. 

Kaj ĝi rezultas ke tiu fakte ne estas tiel malfacila por fari kun la mod operatoro. Do same kiel ni faris kun Cezaro kaj la kripto stuff, uzante mod, ni povos atingi tion por envolver ĉirkaŭe kaj observu tuj ĉirkaŭ kaj ĉirkaŭ kaj ĉirkaŭ kun niaj vosto, subtenante ke kapo puntero movi ĉirkaŭe. Rimarku ke grandeco ĉiam respektante la nombro de eroj vere ene de la vosto. Kaj estas simple la kapo puntero kiu subtenas biciklado tra. Se ni rigardas kio okazis cxi tie, se ni reiros al la komenco, kaj vi simple rigardi kio okazas al la kapo kiam ni enqueue io, nenio okazis al la kapo. Kiam ni enqueued io alia, nenio okazis al la kapo. Tuj kiam ni dequeued io, la estro iras al oni. Ni enqueued io, nenio okazas en la kapo. Kiam ni dequeue ion, subite la kapon gets incremented. Kiam ni enqueue io, nenio okazas en la kapo. 

Kio okazus en ĉi tiu punkto se ni devis dequeue io denove? Ajna pensoj? Kio okazus al la kapo? Kion okazas al la kapo se ni devis dequeue ion alian? La kapo nun estas je indekso 2, kio signifas, ke la kapo de la vosto estas kordoj [2]. [Studenta] Kiu redonas 0? >> Ĝi devus reveni al 0. Ĝi devus kovri reen ĉirkaŭe, precize. Ĝis nun, ĉiufoje kiam ni nomas dequeue, ni estis aldono al la kapo, aldoni al la kapo, ili aldonas al la kapo, ili aldonas al la kapo. Tuj kiam tiu kapo puntero alvenas al la lasta indekso en nia tabelo, tiam ni devas kovri ĝin ĉirkaŭ la komenco, reiru al 0. [Charlotte] Kio determinas la kapablo de la vosto en pilo? [Hardison] En ĉi tiu kazo, ni ĵus uzante # difinita konstanto. >> Bone. [Hardison] En la reala. C dosiero, vi povas iri en kaj Muck per ĝi iomete kaj fari ĝin tiel granda aŭ tiel malgranda kiel vi volas. [Charlotte] Do kiam vi faras ĝin vosto, kiel vi faras la komputilo scias kiel granda vi volas ke la pilo esti? [Hardison] Tio estas granda demando. Ekzistas kelkaj manieroj. Unu estas simple difini ĝin fronto kaj diru ĉi tiu tuj estos vosto kiu havas 4 eroj aŭ 50 eroj aŭ 10.000. La alia maniero estas fari kion la hacker eldono uloj faras kaj krei funkcioj havi vian voston kreski dinamike kiel pli aĵoj get aldonis in 

[Charlotte] Do iru kun la unua eblo, kion sintakso vi uzas por diri al la programo, kio estas la grandeco de la vosto? [Hardison] Ah. Do ni eskapos de ĉi. Mi estas ankoraŭ en stack.c tie, do mi simple tuj rulumu supren al la supro tie. Ĉu vi povas vidi ĉi tie ĉi? Ĉi tiu estas la # difini kapablo 10. Kaj jen estas preskaŭ la ĝusta sama sintakso ke ni havas por vico. Krom en vosto, ni havas ke ekstra struct kampo en ĉi tie. [Charlotte] Ho, mi pensis, ke la kapablo signifis la kapablo por la kordo. [Hardison] Ah. >> Tio estas la maksimuma longeco de la vorto. >> Got ĝin. Yeah. La kapablo tie - jen granda punkto. Kaj jen estas iu kiu estas malfacila ĉar kion ni deklaras jen tabelo de char * s. Tabelo de punteros. Jen tabelo de signoj. Tio estas verŝajne tio, kion vi vidis, kiam vi estis deklari vian buffers por dosiero / S, kiam vi estis kreante kordoj permane sur la stako. Tamen, kion ni havas ĉi tie estas tabelo de char * s. Do ĝi estas tabelo de punteros. Efektive, se ni zoom reen eksteren kaj ni rigardas kio okazas ĉi tie en la prezento, vi vidas ke la reala elementoj, la karaktero datumoj ne stokas ene de la tabelo mem. Kio stokitaj en nia tabelo jen punteros al la karaktero datumoj. Okay. Do ni vidas kiel la grandeco de la vosto estas nur kiel kun la pilo, la grandeco ĉiam respektas la nombro de eroj nuntempe en la vico. Post fari 2 enqueues, la grandeco estas 2. Post fari dequeue la grandeco estas nun 1. Post fari alian enqueue la grandeco estas reen ĝis 2. Do la grandeco definitive respektas la nombro de elementoj en la vosto, kaj tiam la kapo nur subtenas biciklado. Ĝi iras de 0-1-2, 0-1-2, 0-1-2. Kaj ĉiufoje ni nomas dequeue, la estro puntero gets incremented al la sekvanta indekso. Kaj se la kapo estas por transiri, ĝi cikloj reen ĉirkaŭ al 0. Do kun tio, ni povas skribi la dequeue funkcio. Kaj ni tuj forlasi la enqueue funkcio por vi infanoj apliki anstataŭe. 

Kiam ni dequeue ero el niaj vosto, kio estis la unua kiu Daniel faris kiam ni komencis skribi la popo funkcio por piloj? Lasu min aŭdi de iu kiu ne parolis ankoraŭ. Ni vidas, Saad, ĉu vi memoras, kion Daniel faris, kiel la unua horo, kiam li skribis popo? [Saad] Ne estis, estis - >> Li provis ion. [Saad] Se grandeco estas pli granda ol 0. >> Ekzakte. Kaj kio estis tiu provoj por? [Saad] Tio estis provante vidi se estas io interne de la tabelo. [Hardison] Yeah. Ekzakte. Do vi ne povas popo ion el la stako se estas malplena. Tiel same, vi ne povas dequeue ion el vosto se estas malplena. Kio estas la unua aĵo kiun ni devas fari en nia dequeue funkcio ĉi tie, ĉu vi opinias? [Saad] Se grandeco estas pli granda ol 0? >> Jes. En ĉi tiu kazo, mi fakte nur provis vidi se ĝi estas 0. Se ĝi estas 0, ni povas reveni nula. Sed ĝusta sama logiko. Kaj ni daŭrigas kun ĉi. Se la grandeco estas ne 0, kie estas la elemento kiun ni deziras dequeue? [Saad] Al la kapo? >> Ekzakte. Ni povas nur eltiri la unua elemento de nia vosto alirante la elemento en la kapo. Nenio freneza. Post tio, kion ni faru? Kio devas okazi? Kio estis la alia afero, ke ni raportis en dequeue? Du aferoj devas okazi, ĉar nia queue ŝanĝis. [Daniel] Redukti la grandeco. >> Ni devas redukti la grandecon, kaj plimultigos la kapo? Ekzakte. Pliigi la kapon, ni ne povas simple blinde pliigi la kapo, memoru. Ni ne povas nur fari queue.head + +. Ni devas ankaŭ inkluzivi ĉi mod de la kapacito. Kaj kial ni mod per la kapablo, Stella? [Stella] Ĉar ĝi devas kovri ĉirkaŭe. >> Ekzakte. Ni mod de la kapablo ĉar ĝi havas por envolver reen ĉirkaŭ al 0. Do nun, je ĉi tiu punkto, ni povas fari kion Daniel diris. Ni povas dekremento la grandeco. Kaj tiam ni povas nur redonas la elemento kiu estis sur la supro de la vico. Ĝi aspektas ia gnarly en komenco. Vi eble havas demandon. Pardonu? 

[Sam] Kial estas unue en la supro de la vosto? Kie kiuj iras? [Hardison] Ĝi venas de la kvara linio de sube. Post kiam ni provi certigi ke nia vosto estas ne malplena, ni eltiri char * unue, ni eltiri la elemento kiu sidas ĉe la kapo indekso de nia tabelo, de nia kordoj tabelo, >> kaj alvoko tiu unua? [Hardison] Kaj ni nomas ĝin unue. Yeah. Nur sekvi sur tio, kial vi pensas, ke ni devis fari tion? [Sam] Ĉiu unua estas simple reveni q.strings [q.head]? >> Jes. >> Ĉar ni faras ĉi ŝanĝiĝanta de la q.head kun la mod funkcio, kaj tie estas neniu maniero fari tion ene reveno linio ankaŭ. [Hardison] Ekzakte. Vi estas makulo sur. Sam tute rimarki plu. La kialo ni devis eltiri la unua elemento de nia vosto kaj stoki ĝin en variablo estas ĉar tiu linio kie ni ĵus q.head, tie estas la mod operatoro en tie ne estas iu kiu povas fari kaj ĝi efektiviĝos en la kapo sen - en unu linio. Do ni vere devas eltiri la unua elemento, tiam ĝustigi la kapon, ĝustigi la grandecon, kaj tiam revenu la elemento kiu ni tiris eksteren. Kaj jen estas iu kiu ni vidas supreniru poste kun ligitaj listoj, kiel ni ludas tie kun ili. Ofte kiam vi liberigas aŭ disponi de ligitaj listoj Vi devas memori la sekva elemento, la sekvanta puntero de ligitaj listo antaŭ disponi de la aktuala. Ĉar alie vi forĵetu la informoj de kio restas en la listo. Nun, se vi iros al viaj aparaton, vi malfermas queue.c--x el ĉi. Do, se mi malfermos queue.c, lasu min zoom en ĉi tie, vi vidos, ke vi havas similan aspekto dosiero. Similaj-aspekta dosieron kion ni havis antaŭe kun stack.c. Ni havas nian struct por queue difinita ĝuste kiel ni vidis en la diapozitivoj. 

Ni havas nian enqueue funkcio kiu estas por vi fari. Kaj ni havas la dequeue funkcio ĉi tie. La dequeue funkcio en la dosiero estas unimplemented, sed mi remetis ĝin sur la PowerPoint por ke vi povas tajpi ĝin, se vi volas. Do dum la sekvaj 5 minutoj aŭ tiel, vi infanoj laboras en enqueue kiu estas preskaŭ ĝuste la malo de dequeue. Vi ne devas ĝustigi kapon kiam vi enqueueing, sed kion vi havas por ĝustigi? Grandeco. Do kiam vi enqueue, la kapo restas netuŝita, la grandeco gets ŝanĝis. Sed ĝi prenos iom el - vi devos ludi tie kun tiu mod elŝeligi precize kion indekso la nova elemento devas esti aldonitaj en. Do mi donos al vi infanoj iom, ŝovis dequeue reen sur la glito, kaj kiel vi infanoj havas demandojn, krii ilin tiel ke ni povas ĉiuj parolas pri ili kiel grupo. Ankaŭ, kun la grandeco vi ne batu - kiam vi ĝustigi la grandecon, vi povas ĉiam nur - vi devas mod la grandeco iam? [Daniel] No >> Vi ne devas mod la grandecon, dekstre. Ĉar la grandeco estos ĉiam, se you're - supozante ke vi administri aferojn taŭge, la grandeco ĉiam estos inter 0 kaj 3. Kie vi devas mod kiam vi faras enqueue? [Studenta] Nur por la kapo. >> Nur por la kapo, ĝuste. Kaj kial vi devas mod ajn en enqueue? Kiam estas situacio en kiu vi devus mod? [Studenta] Se vi havas frandajxojn cxe spacoj, kiel en spacoj 1 kaj 2, kaj tiam vi bezonis aldoni ion je 0. [Hardison] Jes, ĝuste. Do, se via kapo puntero estas ke je la fino, aŭ se via grandeco plus via kapo estas granda, aŭ pli ĝuste, tuj envolver ĉirkaŭ la vosto. 

Do en tiu situacio, ke ni havas ĉi tie sur la glito ĝuste nun, se mi volas enqueue ion nun, ni volas enqueue io en indekso 0. Do, se vi rigardas al kie la 50 iras, kaj mi nomas enqueue 50, ĝi iras tien je la fundo. Ĝi iras en indekso 0. Ĝi anstataŭas la 'hi' kiu jam dequeued. [Daniel] Cxu vi ne atentas, ke en dequeue jam? Kial gxi faras nenion kun la kapo en enqueue? [Hardison] Ho, do vi ne modifante la kapo, sorry. Sed vi devas uzi la mod operatoro kiam vi konsentas la elemento kiu vi volas enqueue kiam vi konsentas la sekvanta elemento en via vico. [Bazilo] Mi ne faris tion, kaj mi atingis "sukceso" de tie. [Daniel] Ho, mi komprenas kion vi diras. [Hardison] Do vi didn't - vi ĵus faris ĉe q.size? [Bazilo] Yeah. Mi nur ŝanĝis flankoj, mi faris nenion kun la kapo. [Hardison] Vi ne vere devas nuligi la kapon esti io, sed kiam vi indekson en la kordoj tabelo, vi fakte devas iri antaŭen kaj kalkuli kie la sekva elemento estas, ĉar withe la pilo, la sekva elemento en via pilo estis ĉiam ĉe la indico responda al la grandeco. Se ni retrorigardas ĉe nia stako puŝo funkcio, ni povis ĉiam plunk en nia nova elemento ĝuste en indeksa amplekso. Dum kun la vosto, ni ne povas fari tion ĉar se ni estas en ĉi tiu situacio, se ni enqueued 50 nian novan ĉenon irus dekstren ĉe kordoj [1] kion ni ne volas fari. Ni volas havi la novan ĉenon iru ĉe indeksa 0. 

Ĉu neniu - jes? [Studenta] Mi havas demandon sed ne vere rilataj. Kion tio signifas kiam iu simple nomas iun kiel pred puntero? Kio estas tiu nomo mallongigo? Mi scias ke estas nur nomo. [Hardison] pred puntero? Ni vidu. En kio kunteksto? [Studenta] Ĝi estis por la insert. Mi povas demandi vin poste se vi volas ĉar ĝi ne estas vere rilataj, sed mi nur - [Hardison] De David insert kodo de prelego? Ni povas tiri ke tien kaj paroli pri tio. Ni parolos pri tio baldaŭ, iam ni atingos ligitaj listoj. 

Do ni vere rapide rigardi, kion la enqueue funkcio similas. Kio estis la unua kiu homoj provis fari en via enqueue linio? En tiun vosto? Simila al tio, kion vi faris por pilo pelante. Kion vi faris, Stella? [Stella, nekomprenebla] [Hardison] Ekzakte. If (q.size == kapablo) - Mi bezonas meti mian streĉaj en la ĝusta loko - reveni falsaj. Zoom en iomete. Okay. Nun kio estas la sekvanta afero kiun ni devis fari? Ĝuste kiel kun la pilo, kaj insertos en la ĝusta loko. Kaj tiel, kio estas la ĝusta loko por enmeti tion? Kun la pilo estis indekso grandeco, kun ĉi tio ne estas sufiĉe ke. [Daniel] Mi havas q.head--aŭ - >> q.strings? >> Yeah. q.strings [q.head + q.size mod kapablo]? [Hardison] Ni probable volas meti krampojn ĉirkaŭ ĉi por ke ni ricevas la taŭga prioritaton do jen cleart al ĉiuj. Kaj starigis kiu egala? >> To str? >> To str. Granda. Kaj nun kio estas la lasta afero kiun ni devas fari? Samkiel ni faris en la stako. >> Pliigo de la grandeco? >> Pliigo la grandeco. Eksplodo. Kaj poste, ekde la malfermilo kodo ĵus revenis falsa implicite, ni volas ŝanĝi ĉi tion al vera se ĉiu iras tra kaj ĉiuj iras bone. Bone. Tio estas multe da informo por sekcio. Ni ne tute finita. Ni volas paroli vere rapide pri unuope-ligitaj listoj. Mi metis tiun supren do ni povas reiri al ĝi poste. Sed ni reiru al nia prezento por nur kelkaj pli diapozitivoj. Do enqueue estas Tōdō, nun ni jam faris. 

Nun ni rigardu unuope-ligitaj listoj. Ni parolis pri tiuj iom pli en prelego. Kiel multaj el vi infanoj vidis la demo kie ni havis popolo mallerte montrante al ĉiu alia kaj okazigon nombroj? >> Mi estis en tio. >> Kion vi pensas infanoj? Ĉu tio, mi esperas desmitificar tiuj iomete? Kun listo, rezultas ke ni trakti tiun tipon, ke ni tuj voki nodo. Dum kun la vosto kaj la stako ni havis structs ke ni volonte nomas vosto en pilo, ni havis tiujn novajn vosto en pilo tipoj, tie listo estas vere nur konsistas el aro da nodoj. En la sama maniero kiu kordoj estas nur aro da signoj ĉiuj vicigitaj apud la alia. Al ligitaj listo estas nur nodo kaj alia nodo kaj alia nodo kaj alia nodo. Kaj anstataŭ rompante ĉiuj nodoj kune kaj stokante ilin contiguously ĉiuj dekstra flanko de la alia en la memoro, havante ĉi sekva puntero nin permesas konservi la nodoj kien, al la hazardo. Kaj tiam ia draton ili ĉiuj kune noti de unu al alia. 

Kaj kio estis la granda avantaĝo ke ĉi havis super tabelo? Super provizon ĉio contiguously gluiĝis apud la alia? Vi memoras? Yeah? >> Dinamika memoro atribuo? >> Dinamika memoro atribuo en kiu senco? [Studenta] En kiu vi povas subteni farante ĝin pli granda, kaj vi ne devas movi vian tutan tabelo? [Hardison] Ekzakte. Do kun tabelo, kiam vi volas meti novan elementon en la mezon de ĝi, vi devas ŝanĝi ĉio por fari spacon. Kaj kiel ni parolis pri la vosto, jen kial ni tenas ke kapo pointer, por ke ni ne konstante sxangxigxantaj aĵoj. Ĉar kiu alvenas multekostaj se vi havas grandan tabelo kaj vi senĉese faras tiuj hazarda inserciones. Dum kun listo, ĉiuj vi devas fari estas ĵeti ĝin sur nova nodo, alĝustigi la punteros, kaj vi faris. Kio sucks pri tio? Aparte de la fakto ke ĝi ne estas tiel facila por labori kun tiel tablo? Yeah? [Daniel] Nu, mi supozas ke estas multe pli malfacile atingi specifan elemento en la ligitaj listo? [Hardison] Oni ne povas simple salti al ajna elemento en la mezo de via ligitaj listo. Kiel vi devas fari ĝin anstataŭe? >> Vi devas treti tra la tuta afero. [Hardison] Yeah. Vi devas iri tra unuope, unu post la alia. Ĝi estas grandega - temas pri doloro. Kio estas la alia - estas alia falita al ĉi tio. [Bazilo] Vi ne povas iri antaŭen kaj malantaŭen? Vi devas iri unu direkto? [Hardison] Yeah. Nu do kiel ni solvi tiun, kelkfoje? [Bazilo] duoble-ligitaj listoj? >> Ekzakte. Estas duoble-ligitaj listoj. Ekzistas ankaŭ - sorry? 

[Sam] Is that la sama kiel uzanta la pred kiu - Mi nur memoris, ne estas tio kio la pred afero estas por? Ĉu tio ne inter duoble kaj unuope? [Hardison] ni rigardu kio precize li faris. Do jen ni iru. Jen la listo kodo. Jen ni havas predptr, en ĉi tie. Ĉu ĉi tiu estas kion vi parolis? Do tio - li liberigante liston kaj li provas gardi puntero al ĝi. Tiu ne estas la duoble, unuope ligitaj-listoj. Ni povas paroli pli pri tio poste ekde ĉi parolas pri liberigo de la listo kaj mi volas montri iu alia materialo unue. sed estas nur - ĝin memorante la valoro de ptr [Studenta] Ho, estas preceeding puntero? >> Jes. Tiel ke ni povas tiam pliigo ptr mem antaŭ ol ni tiam senpaga kio predptr estas. Ĉar ni ne povas libera ptr kaj tiam nomita ptr = ptr proksima, right? Tio estus malbona. Do ni vidas, reen al ĉi tiu viro. 

La alia malbona afero pri lertaj estas kiu dum kiu kun tabelo ni nur devas ĉiujn elementojn sin plata flanko de la alia, tie ni ankaŭ enkondukis tiun puntero. Do ekzistas plia eron de memoro kiu ni devi uzi por ĉiu elemento kiu ni stokante en nia listo. Ni preni fleksebleco, sed venas al kosto. Ĝi venas kun ĉi tiu tempo kosto, kaj ĝi venas kun ĉi tiu memoro kosto ankaŭ. Tiam en la senco, ke ni nun devas iri tra ĉiu ero en la tabelo trovi la unu je indico 10, aŭ kiu estus estinta indekso 10 en tabelo. 

Nur vere rapide, kiam ni diagramon el tiuj lertaj, tipe ni tenadi la estro de la listo aŭ la unua montrilo de la listo kaj rimarku ke ĉi tio estas vera puntero. Estas nur 4 bitokoj. Ne reala nodo mem. Do vi vidas, ke ĝi havas nenian valoron int en ĝi, neniu sekva puntero en ĝi. Estas laŭvorte nur puntero. Ĝi tuj indikas iun kiu estas efektiva nodo struct. [Sam] A puntero nomita nodo? >> Jen - ne. Tio ĉi estas puntero al iu el tipo nodo. Estas puntero al nodo struct. >> Ho, bone. Diagramo maldekstre kodon en la dekstra. Ni povas agordi ĝin al nula, kio estas bona maniero por komenci. Kiam vi diagramon ĝin, vi jam estas skribi ĝin kiel nula aŭ vi metis linion tra ĝi plaĉas. 

Unu el la plej facilaj manieroj por labori kun lertaj, kaj ni demandos vi ambaŭ prepend kaj aldonas por vidi la diferencojn inter la du, sed prepending estas definitive pli facila. Kiam vi prepend, ĉi tiu estas kie vi - kiam vi prepend (7), vi iru kaj krei la nodo struct kaj vi starigis unuan atentigi al tio, ĉar nun, kiel ni prepended ĝin, ĝi tuj estos al la komenco de la listo. Se ni prepend (3), kiu kreas alia nodo, sed nun 3 venas antaŭ 7. Do ni esence pelante aĵoj sur nia listo. Nun, vi povas vidi ke prepend, foje homoj nomas ĝin puŝi, ĉar vi puŝas nova elemento sur via lerta. Estas ankaŭ facile forviŝi ĉe la fronto de listo. Do homoj ofte nomas tion popo. Kaj en tiu vojo, vi povas imiti pilo uzante ligitaj listo. Whoops. Pardonu, nun ni eniru append. Do jen ni prepended (7), nun ni prepend (3). Se ni prepended ion alian sur tiu listo, se ni prepended (4), tiam ni havus 4 kaj tiam 3 kaj poste 7. Tial ni povus popo kaj forigi 4, forigu 3, forpreni 7. Ofte la pli intuicia maniero pensi pri tiu estas kun append. Do mi diagrammed el kio ĝi devus aspekti kun aldonas tie. Ĉi tie, aldonita (7) ne aspektas ajna malsamajn ĉar tie estas nur unu elemento de la listo. Kaj appending (3) metas je la fino. Eble vi povas vidi nun la trukon per append estas ke ĉar oni nur scias, kie la komenco de la listo estas, al aldonas al listo vi devas promeni tuta vojo tra la listo alveni ĝis la fino, halti, tiam konstrui vian nodo kaj plunk ĉio sube. Telegramon ĉiuj aĵoj supren. Do kun prepend, kiel ni ĵus disŝiris tra tiu vere rapide, kiam vi prepend al listo, estas sufiĉe simpla. 

Vi faras vian novan nodon, engaĝi iu dinamika memoro atribuo. Do jen ni fari nodon struct uzante malloc. Do malloc ni uzas ĉar tio estos flankenmetis memoro por ni por posta ĉar ni ne volas ĉi - ni volas tiun memoron al persisti dum longa tempo. Kaj ni preni sagon al la spaco en memoro kiujn ni ĵus asignitaj. Ni uzas grandeco de vertico, ni ne resumi la kampoj. Ni ne permane generi la nombro de bitokoj, anstataŭ ni uzas sizeof por ke ni sciu estas duumaj la taŭga nombro da bajtoj. Ni certigu por testi ke nia malloc alvoko sukcesis. Tio estas io, kion vi volas fari en ĝenerala. Sur modernaj maŝinoj, kurante el memoro ne estas iu kiu facile se vi atribuante barelon da aĵoj kaj farante grandan liston, sed se vi konstruas ajxojn, ekzemple, kiel iPhone aŭ Android, vi ja havas limigitan memoro rimedoj, speciale se vi faras ion intensa. Do ĝi estas bona por eniri en praktiko. 

Rimarku ke mi uzis paron malsamajn funkciojn tie ke vi vidis, ke estas ia nova. Do fprintf estas ĝuste kiel printf krom lia unua argumento estas la rivereto, en kiu vi volas presi. En ĉi tiu kazo, ni volas presi al cxeferarigo kordoj kiu estas malsama de la normo outstream. Defaŭlte ĝi aperas en la sama loko. Ĝi ankaŭ presas al la fina stacio, sed vi povas - uzante tiujn ordonojn vi lernis pri la redirección teknikoj vi lernis pri en Tommy video problemo aro 4, vi povas direkti ĝin al malsamaj areoj; tiam eliru, ĉi tie, eliroj via programo. Estas esence kiel reveni de ĉefaj, krom ni uzas eliro ĉar tie reveno ne faros nenion. Ni ne en ĉefaj, tiel redonante ne eliri la programon kiel ni deziras. Do ni uzu la eliro funkcio kaj donu eraro kodo. Tiam jen ni starigis la nova nodo valoron kampo, ĝia i kampo al esti egala al i, kaj tiam ni telegramon ĝin. Ni starigis la nova vertico La sekva puntero atentigi al la unua, kaj poste unua nun indikas la nova nodo. Tiuj unuaj linioj de kodo, ni reale konstrui la nova nodo. Ne la lastaj du linioj de tiu funkcio, sed la unuaj. Vi povas vere eltiri en funkcio, en helpanto funkcio. Tio ofte kion mi faras, mi tiri gxin al funkcio, Mi nomas ĝin iu kiel muntaĵo nodo, kaj kiu gardas la prepend funkcio bela malgranda, estas nur 3 linioj tiam. Mi faras alvokon al mia build nodo funkcio, kaj tiam mi drato ĉio supren. 

La fina afero mi volas montri al vi, kaj mi ellasos vin fari append kaj cxion, kio en via propra, estas kiel persisti super listo. Ekzistas multajn malsamajn manierojn persisti super listo. En ĉi tiu kazo, ni tuj trovi la longo de listo. Do ni komencu per longeco = 0. Ĉi tio estas tre simila al la skribo strlen por linio. Jen kion mi volas montri al vi, tion por buklo gxuste cxi tie. Ĝi aspektas kinda funky, temas ne la kutima int i = 0, i <ajn, i + +. Anstataŭe ĝi estas inicializar nia variablo n al esti la komenco de la listo. Kaj poste dum nia iterator variablo estas ne nulaj, ni plu iri. Ĉi tio estas ĉar, per konvencio, la fino de nia listo estos nula. Kaj tiam al pliigo, anstataŭ fari + +, la ligitaj listo ekvivalento de + + estas n = n-> proksima. 

Mi permesos al vi plenigi la truojn tie ĉar ni estas el la tempo. Sed observu cxi tion kiel vi laboras en via spellr psets. Ligitaj listoj, se vi implementando hash tablo, definitive venis en tre oportuna. Kaj havante ĉi idiomo por looping super aĵoj faros vivo multe pli facila, espereble. Demandojn, rapide? [Sam] Cxu vi sendu la kompletigis SLL kaj sc? [Hardison] Yeah. Mi sendas kompletigis diapozitivoj kaj kompletigita SLL pilo kaj queue.cs. [CS50.TV]