[Powered by Google Translate] [Secció 6: menys còmode]
[Nate Hardison] [Harvard University]
[Aquesta és CS50.] [CS50.TV]
Està bé. Benvinguts a la secció 6.
Aquesta setmana, estarem parlant d'estructures de dades a la secció,
sobretot perquè el problema d'aquesta setmana estableix spellr
fa un munt d'exploració estructures de dades.
Hi ha un munt de maneres diferents que vostè pot anar amb el conjunt de problemes,
i les estructures de dades més el coneixem, les coses més interessants que pots fer.
>> Així que anem a començar. En primer lloc parlarem de les piles,
les dades de la pila i la cua d'estructures que parlarem.
Les piles i les cues són realment útils quan vam començar a parlar dels gràfics,
que no farem molt d'aquests moments.
Però són molt bons per entendre una de les grans estructures de dades fonamentals de la CS.
La descripció de l'especificació conjunt de problemes,
si estirar-lo cap amunt, parla de les piles com afí a
la pila de safates de menjars que vostè té a la cafeteria als menjadors
on quan el personal del menjador ve i posa les safates de sortir a sopar després d'haver-los netejat,
que apilar un sobre l'altre.
I després, quan els nens vénen a buscar menjar,
tiren les safates de sortida, primer l'un i després la de baix, i després la de baix d'això.
Així que, en efecte, la primera safata que el personal del menjador posar és l'últim que s'ha enlairat.
L'últim que el personal del menjador posar és el primer que l'hi porten fora per al sopar.
En el conjunt d'especificacions problema, que es pot descarregar si no ho ha fet,
parlem de modelatge d'una pila stucture dades utilitzant aquest tipus d'estructura.
>> Així que el que tenim aquí, això és similar al que es va presentar a la conferència,
excepte en la conferència es van presentar amb aquest sencers en lloc de char * s.
Això serà una pila que emmagatzema què?
Daniel? Què estem emmagatzemant en aquesta pila?
[Daniel] Strings? >> Estem emmagatzemar les cadenes en aquesta pila, exactament.
Tot el que ha de tenir per a crear una pila és una matriu
d'una capacitat particular, que en aquest cas,
capacitat serà tot en majúscules perquè és una constant.
I a continuació, a més de la matriu, tot el que necessita per seguir és la mida actual de la matriu.
Una cosa per notar aquí que és una espècie de fresc
és que estem creant l'estructura de dades apilades una damunt d'una altra estructura de dades, la matriu.
Hi ha diferents maneres d'implementar piles.
No ho farem encara, però espero que després de fer els problemes de llista vinculada,
veuràs el fàcil que és implementar una pila a la part superior d'una llista enllaçada també.
Però per ara, anem a atenir-nos a les matrius.
Així que de nou, tot el que necessitem és una matriu i només hem de seguir la mida de la matriu.
[Sam] Em sap greu, com és que vostè va dir que la pila està per sobre de les cordes?
A mi em sembla que les cadenes estan dins de la pila.
[Hardison] Yeah. Estem creant, estem donant la nostra àmplia estructura de dades -
aquesta és una gran pregunta. Llavors la pregunta és per què, per les persones que estan veient aquesta línia,
Per què estem dient que la pila està per sobre de les cordes,
perquè aquí sembla que les cordes estan a l'interior de la pila?
La qual cosa és totalment el cas.
El que em referia és que tenim una estructura de dades array.
Tenim una matriu de char * s, aquesta matriu de cadenes,
i que es va a afegir a la que per tal de crear l'estructura de dades apilats.
>> Així que una pila és una mica més complex que una matriu.
Podem utilitzar una matriu per construir una pila.
Així que aquí és on diem que la pila es construeix a la part superior d'una matriu.
De la mateixa manera, com he dit abans, podem construir una pila a la part superior d'una llista enllaçada.
En lloc d'utilitzar una matriu per mantenir els nostres elements,
podem utilitzar una llista enllaçada per mantenir els nostres elements i construir la pila del voltant d'això.
Anem a veure un parell d'exemples, mirant una mica de codi,
per veure el que realment està passant aquí.
A l'esquerra, he tirat el que struct pila es veuria en la memòria
si la capacitat es van definir # per ser quatre.
Tenim els nostres quatre elements de matriu char *.
Tenim cadenes [0], les cadenes [1], les cadenes [2], cadenes [3],
i després de que l'espai per al nostre passat sencer mida.
Té això sentit? Bé.
Això és el que passa si el que faig a la dreta,
que serà el meu codi, és declarar només una estructura, una estructura apilades anomenat s.
Això és el que tenim. Estableix aquesta empremta en la memòria.
La primera pregunta aquí és: quins són els continguts d'aquesta estructura de pila?
Ara mateix no són res, però no són totalment res.
Són aquest tipus d'escombraries. No tenim idea del que hi ha en ells.
Quan declarem s de pila, només estem tirant a baix que a la part superior de la memòria.
És com declarar int i, i no ho inicialitza.
No sap el que hi ha. Vostè pot llegir el que hi ha allà,
però potser no és molt servicial.
Una de les coses que vol recordar sempre de fer és inicialitzar el que necessita ser inicialitzat.
En aquest cas, anem a inicialitzar la mida sigui zero,
perquè això arribarà a ser molt important per a nosaltres.
Podríem seguir endavant i iniciar tots els punters, tot el s * char,
a ser algun valor comprensible, probablement nul.
Però no és del tot necessari que fem això.
>> Ara, les dues operacions principals sobre les piles de veritat?
Algú es recorda de la conferència que el que vostè fa amb les piles? Sí?
[Stella] Empenyent i fent esclatar? >> Exactament.
Empenyent i fent esclatar són les dues operacions principals de piles.
I què empenta fer? >> Es posa alguna cosa a la part superior
de la pila, i després salten el treu.
[Hardison] Exactament. Així empenyent empeny una mica a la part superior de la pila.
És com el personal del menjador posant una safata de menjar al taulell.
I fer esclatar està prenent una safata de sopar de la pila.
Anem a veure un parell d'exemples del que succeeix
quan empenyem les coses a la pila.
Si anéssim a empènyer la cadena 'hola' al nostre stack,
això és el que el nostre diagrama es veuria ara.
Mireu el que passa?
Ens introdueix en el primer element de la nostra àmplia cordes
i ens va pujar el nostre recompte mida és 1.
Així que si ens fixem en la diferència entre les dues corredisses, aquí va ser de 0, és a dir abans de la inserció.
Aquí està després de la inserció.
Abans de la inserció, després de la inserció.
I ara tenim un element de la nostra pila.
És la cadena "hola", i això és tot.
Tota la resta a la matriu, en el nostre array de cadenes, segueix sent escombraries.
No ho hem inicialitzat.
Diguem que empènyer altra cadena al nostre stack.
Anem a empènyer "món" en aquest moment.
Així que vostè pot veure "món" aquí va sobre de "hola",
i el recompte de mida puja a 2.
Ara podem empènyer "CS50", i que anirà a la part superior de nou.
Si retrocedim, es pot veure com estem portant les coses a la part superior de la pila.
I ara arribem al pop.
Quan ens vam anar una mica fora de la pila, què va passar?
Algú veu la diferència? És molt subtil.
[Estudiant] La mida. >> Sí, la mida canviat.
>> Què més es pot esperar per al canvi?
[Estudiants] Les cordes, també. >> Dret. Les cordes també.
Resulta que quan ho fas d'aquesta manera,
perquè no estem copiant els elements al nostre stack,
que en realitat no ha de fer res, només podem utilitzar la mida
fer un seguiment de la quantitat de coses en la nostra àmplia
perquè quan aparegui de nou, de nou només disminuir el nostre mida a 1.
No cal anar en realitat en i sobreescriure qualsevol cosa.
Una mica funky.
Resulta que solem deixar les coses només perquè és menys treball per a nosaltres.
Si no hem de tornar enrere i sobreescriure alguna cosa, llavors per què fer-ho?
Així, quan aparegui el doble de la pila, l'únic que fa és disminuir la mida d'un parell de vegades.
I un cop més, això és només perquè no estem copiant coses al nostre stack.
Sí? Endavant.
[Estudiant, inintel · ligible] >> I llavors, què passa quan vostè empeny alguna cosa nova?
Quan es prem alguna cosa nova, on va?
On va, Basil? En cadenes >> [1]? >> Dret.
Per què no anar a cadenes [3]?
[Basil] A causa que es va oblidar que havia alguna cosa en les cadenes [1] i [2]?
[Hardison] Exactament. La nostra pila, en essència, "es va oblidar" que s'aferra a qualsevol cosa
a les cadenes [1] o cadenes [2], així que quan ens empenyen "woot"
només posa això en l'element en cadenes [1].
Hi ha alguna pregunta sobre com funciona això, a un nivell bàsic?
[Sam] Així que això no és de cap manera dinàmica, en termes de quantitat
o en termes de la mida de la pila?
[Hardison] Exactament. Això és - el punt era que no es tractava d'una pila dinàmica growning.
Aquesta és una pila que pot contenir, com a màxim, quatre char * s, en la majoria de quatre coses.
Si fóssim a tractar d'empènyer 1/5 cosa, què creu vostè que hauria de passar?
[Els estudiants], inintel · ligibles
[Hardison] Exactament. Hi ha una sèrie de coses que podrien succeir.
Possiblement podria seg culpa, depenent del que eren -
Com és exactament el que estaven executant el back-end.
Pot sobreescriure. Podria haver de desbordament de memòria intermèdia que parlem a classe.
Quina seria la cosa més òbvia que pot ser sobrescriptura
si tractem d'empènyer alguna cosa extra en la nostra pila?
Així que vostè ha esmentat un desbordament de memòria intermèdia.
Quina podria ser la cosa que s'escriuen sobre o trepitjar
si ens va desbordar accidentalment en tractar d'empènyer una cosa extra?
[Daniel, inintel · ligible] >> Possible.
Però inicialment, el que podria passar? Què passa si tractem d'empènyer 1/4 cosa?
Pot sobreescriure la mida, si més no amb aquest esquema de memòria que tenim.
>> En l'especificació conjunt de problemes, que és el que estarem implementant avui en dia,
el que vull fer és tornar false.
El nostre mètode d'empenta es va a tornar un valor booleà,
i que el valor booleà serà vertadera si l'empenta èxit
i fals si no podem empènyer més res perquè la pila està plena.
Anem a veure una mica d'aquest codi en aquests moments.
Aquesta és la nostra funció push.
La nostra funció push per una pila es prendrà en la cadena per posar a la pila.
Es tornarà true si la cadena va ser empès amb èxit
d'una altra manera a la pila i la falsedat.
Alguna suggeriment sobre el que podria ser una bona cosa primer que hem de fer aquí?
[Sam] Si la mida és igual a la capacitat de retornar false llavors?
[Hardison] Bingo. Bon treball.
Si la mida és la capacitat, tornarem false.
No podem posar res més en la nostra pila.
En cas contrari, volem posar alguna cosa a la part superior de la pila.
Què és "la part superior de la pila," inicialment?
[Daniel] Mida 0? Mida >> 0.
Quina és la part superior de la pila després hi ha una cosa a la pila? Missy, saps?
[Missy] Una. Mida >> és un, exactament. Vostè mantenir l'addició a la mida,
i cada vegada que s'està posant en el nou element en la mida de l'índex en la matriu.
Ho podem fer amb aquest tipus d'una sola línia, si això té sentit.
Així que tenim la nostra matriu de cadenes, anem a accedir-hi en l'índex de mida,
i només anem a guardar el nostre char * en aquest país.
Cal notar com hi ha cap còpia corda passant aquí,
no assignació dinàmica de la memòria?
I després Missy criat el que ara hem de fer,
perquè hem guardat la cadena al lloc apropiat en la matriu,
i ella em va dir que calia augmentar la mida d'una manera que estem preparats per la següent pulsació.
Així que podem fer això amb s.size + +.
En aquest punt, hem empès a la nostra matriu. Què és l'últim que hem de fer?
[Estudiant] Retorna true. >> Tornar veritat.
Per tant és simple, un codi bastant simple. No massa.
Una vegada que ha embolicat el cap al voltant de com funciona la pila,
això és bastant senzill d'implementar.
>> Ara, la següent part d'aquesta està apareixent una cadena de la pila.
Vaig a donar vostès una mica de temps per treballar en això una mica.
És gairebé essencialment el contrari del que hem fet aquí en empenta.
El que he fet és en realitat - oops.
He arrencat un aparell per aquí, i en l'aparell,
He tirat el problema conjunt 5 especificació.
Si el zoom aquí, podem veure que estic en cdn.cs50.net/2012/fall/psets/pset5.pdf.
Han descarregat el codi que es troba aquí, section6.zip?
Està bé. Si vostè no ha fet això, fes allò en aquest moment, molt ràpid.
Ho faré en la meva finestra de terminal.
De fet, m'ho va fer aquí. Si.
Sí, Sam? >> Tinc una pregunta sobre per què li vas dir s.string 's suports de mida = str?
Quin és str? És el definit abans en algun lloc, o - oh, en la xerrada * str?
[Hardison] Sí, exactament. Aquest va ser l'argument. >> Oh, està bé. Em sap greu.
[Hardison] Estem especificar la cadena d'empènyer polz
L'altra qüestió que pugui sorgir que realment no parlar d'aquí va ser
es donava per fet que vam tenir aquesta variable anomenada s
que era en el seu abast i accessible per a nosaltres.
Ens van donar per fet que era aquest es struct pila.
Així que mirant cap enrere en el codi d'inserció,
es pot veure que estem fent coses amb aquesta cadena que va quedar aprovada en
però després, de sobte, estem accedint s.size, com, d'on provenen de s?
En el codi que veurem a l'arxiu de la secció
i llavors les coses que vostè farà en el seu problema es posa,
hem fet la nostra pila struct una variable global
perquè puguem tenir accés a totes les nostres funcions diferents
sense haver de passar manualment voltant i passar-ho per referència,
fer tot aquest tipus de coses a ella.
Només estem enganyant una mica, si es vol, per fer les coses millor.
I això és una cosa que estem fent aquí perquè és per diversió, és més fàcil.
Sovint, vostè veurà la gent fa això si tenen una estructura de dades gran
que està sent operat dins del seu programa.
>> Anem a anar de nou cap a l'aparell.
Tots amb èxit obtenir el section6.zip?
Tothom ho descomprimeixi utilitzant section6.zip descomprimir?
Si entra a la secció 6 del directori -
aah, per tot el lloc -
i una llista del que hi ha aquí, es veu que tens tres arxius diferents. c.
Vostè té una cua, una sll, que és la llista simplement enllaçada, i una pila.
Si obre stack.c,
es pot veure que tenim aquesta estructura definida per nosaltres,
l'estructura exacta que acabem de parlar en les diapositives.
Tenim la nostra variable global de la pila,
tenim la nostra funció push,
i després tenim la nostra funció pop.
Vaig a posar el codi per fer retrocedir a la diapositiva aquí,
però el que m'agradaria que vostès fan és, potser de la seva capacitat,
anar i posar en pràctica la funció pop.
Quan hagueu posat en pràctica, pot compilar amb make aquesta pila,
a continuació, executeu el fitxer executable pila resultant,
i que s'estendrà tot aquest codi de prova aquí que està en principal.
I principal s'encarrega realment de fer el push i pop trucades
i assegurar-se que tot va a través de tot dret.
També s'inicialitza la mida de la pila aquí
per la qual cosa no ha de preocupar-se que la inicialització.
Es pot suposar que ha estat correctament inicialitzat
en el moment en què s'accedeix a la funció pop.
Això té sentit?
Així que aquí anem. Aquí està el codi d'inserció.
Vaig a donar-vos 5 o 10 minuts.
I si vostè té alguna pregunta en el interí mentre estàs codificació,
si us plau pregunteu en veu alta.
Així que si s'arriba a un punt d'estancament, només pregunti.
Deixa saber, que tothom sap.
Treballi amb el seu veí també.
[Daniel] Estem implementació pop en aquest moment? >> Just pop.
Encara que vostè pot copiar l'aplicació d'empenta si voleu
de manera que la prova funcionarà.
Com que és difícil provar que les coses es a -
o, és difícil de provar coses que fan esclatar fora d'una pila si no hi ha res a la pila, per començar.
>> Què és el pop suposa que es repeteixin? L'element de la part superior de la pila.
Se suposa que per obtenir l'element fora de la part superior de la pila
i després disminuir la mida de la pila,
i ara que ha perdut l'element en la part superior.
I tan bon punt torni l'element en la part superior.
[Estudiant, inintel · ligible]
[Hardison] Llavors, què passa si es fa això? [Estudiant, inintel · ligible]
El que acaba passant és que estàs probablement per accedir a qualsevol dels dos
un element que no s'ha inicialitzat encara, de manera que el seu càlcul
d'on l'últim element és està apagat.
Així que aquí, si et fixes, en l'impuls, estem accedint cadenes en l'element s.size
perquè es tracta d'un nou índex.
És el nou límit de la pila.
Mentre que en el pop, s.size serà el següent espai,
L'espai que hi ha a la part superior de tots els elements de la pila.
De manera que l'element de més amunt no és s.size,
sinó més aviat, que està sota.
>> L'altra cosa que fer quan - en el pop,
se li ha de disminuir la mida.
Si vostè recorda de nou al nostre petit diagrama aquí,
en realitat, l'únic que vam veure passant quan diem pop
era que aquesta mida disminuït, primer a 2, i després a 1.
Després, quan va empènyer un nou element en endavant, seguiria al lloc adequat.
[Basil] Si el s.size és 2, llavors no seria anar a l'element 2,
i després que t'agradaria fer esclatar aquest element fora?
Així que si ens vam anar a - >> Així que donem una ullada a això de nou.
Si aquesta és la nostra pila en aquest punt
i anomenem pop,
en què índex és l'element de més amunt?
[Basil] Als 2, però apareixerà 3. >> Dret.
Així que aquí és on el nostre mida és 3, però volem fer esclatar l'element en l'índex 2.
És aquest tipus típic d'apagat per una que vostè té amb el zero de la indexació d'arrays.
Així que vostè vol ficar el tercer element, però el tercer element no està en l'índex 3.
I la raó per la qual no has de fer això menys 1 quan estem empenyent
és perquè ara mateix, t'adones que l'element de més amunt,
si eren per empènyer una mica més a la pila en aquest punt,
ens agradaria que empènyer en l'índex 3.
I dóna la casualitat que la mida i els índexs alineats quan vostè està empenyent.
>> Qui té una implementació de la pila de treball?
Tens un munt de treball un. Té pop treballant encara?
[Daniel] Sí Crec que sí.
Programa >> està corrent i no segons fallamiento, s'imprimeixi?
¿S'imprimirà l '"èxit" quan s'executa?
Si. Fer apilar, executar, si imprimeix el "èxit" i no va boom,
llavors tot està bé.
Està bé. Anem a repassar l'aparell molt ràpid,
i anem a caminar a través d'aquest.
Si ens fixem en el que està passant aquí amb el pop,
Daniel, què va ser el primer que vas fer?
[Daniel] Si s.size és més gran que 0.
[Hardison] Bé. I per què has fet això?
[Daniel] Per assegurar que hi havia alguna cosa dins de la pila.
[Hardison] Dret. Vols posar a prova per assegurar-se que s.size és més gran que 0;
en cas contrari, què vols que passi?
[Daniel] null retorn? Nul >> Retorn, exactament.
Així que si s.size és més gran que 0. Llavors, què farem?
Què fem si la pila no és buida?
[Stella] Vostè disminuir la mida? >> Vostè disminuir la mida, està bé.
Llavors, com has fet això? >> S.size--.
[Hardison] Great. I llavors, què vas fer?
[Stella] I llavors em va dir que el retorn s.string [s.size].
[Hardison] Great.
En cas contrari, retorna null. Sí, Sam?
[Sam] Per què no ho necessita per ser s.size + 1?
[Hardison] Plus 1? Sí >>. >> Ho tinc.
[Sam] vaig pensar perquè vostè pren amb 1,
llavors vostè va a tornar no és el que ells van demanar.
[Hardison] I això era just el que estàvem parlant amb tot aquest tema de 0 índexs.
Així que si amplia aquí.
Si ens fixem en aquest tipus aquí, es pot veure que quan el pop,
estem fent esclatar l'element d'índex 2.
>> Per tant, disminuir la grandària de la nostra primera, llavors el nostre mida coincideix amb el nostre índex.
Si no disminuir la mida de la primera, llavors hem de veure mida -1 i decrement.
Gran. ¿Tot bé?
Teniu alguna pregunta respecte això?
Hi ha un nombre de formes diferents d'escriure això.
De fet, podem fer alguna cosa encara - podem fer una sola línia.
Podem fer una declaració d'una línia.
Així que en realitat pot disminuir abans que tornem a fer-ho.
Així que posar el - abans de la s.size.
Això fa que la línia realment dens.
Quan la diferència entre el -. S mida i s.size--
és que aquest sufix - en diuen perquè el sufix - ve després de la s.size--
significa que s.size s'avalua als efectes de trobar l'índex
com ho és en l'actualitat quan s'executa aquesta línia,
i després això - que succeeix després de la línia s'executa.
Després que l'element en s.size índex s'accedeix.
I això no és el que volem, perquè volem que el decrement que succeeixi primer.
Othewise, estarem accedint a la matriu, efectivament, fora del camp.
Estarem accedint a l'element superior a la que realment vol accedir.
Sí, Sam? >> És més ràpid i utilitza menys memòria RAM per fer en una sola línia o no?
[Hardison] Honestament, realment depèn.
[Sam, inintel · ligible] >> Sí, depèn. Vostè pot fer trucs de compilació
per obtenir el compilador de reconèixer que, en general, m'imagino.
>> Per això hem esmentat una mica sobre aquestes coses optimització del compilador
que es pot fer en la recopilació,
i aquest és el tipus de cosa que un compilador pot ser capaç d'entendre,
com oh, hey, potser pugui fer tot això en una sola operació,
en oposició a la càrrega de la variable en grandària de RAM,
decreixent, emmagatzemant a sortir, i després torneu a carregar
per processar la resta d'aquesta operació.
Però en general, no, aquest no és el tipus de coses
que farà el seu programa molt més ràpid.
Alguna pregunta més sobre les piles?
>> Així que empènyer i fer esclatar. Si vostès volen provar l'edició pirata informàtic,
el que hem fet en l'edició pirata és en realitat anat
i van fer d'aquesta pila de créixer de forma dinàmica.
El repte no és principalment aquí a la funció push,
per trobar la manera de fer créixer aquesta matriu
a mesura de seguir empenyent més i més elements a la pila.
En realitat no és un codi addicional en excés.
Només una crida a - vostè ha de recordar per aconseguir les trucades a malloc aquí correctament,
i després esbrinar quan dirà realloc.
Això és un repte divertit si t'interessa.
>> Però de moment, seguirem endavant, i parlarem de les cues.
Desplaceu-vos per aquí.
La cua és un germà prop de la pila.
Així que a la pila, les coses que es van posar en última
van ser les primeres coses per després ser recuperats.
Tenim aquest últim a entrar, primer en sortir, o UEPS, fer la comanda.
Mentre que a la cua, com era d'esperar a partir de quan s'està de peu a la fila,
la primera persona que entra a la línia, el primer que ha d'entrar en la cua,
és el primer que es recupera de la cua.
Les cues també s'utilitza sovint quan estem tractant amb gràfics,
com hem parlat breument amb piles,
i les cues també són útils per a un munt d'altres coses.
Una cosa que sorgeix sovint està tractant de mantenir, per exemple,
una llista ordenada d'elements.
I vostè pot fer això amb una matriu. Pot mantenir una llista ordenada de les coses en una matriu,
però en els que es complica és llavors sempre cal trobar
el lloc adequat per a inserir la cosa.
Així que si vostè té una matriu de nombres, de l'1 al 10,
i després vol ampliar això a tots els números d'1 a 100,
i que està rebent aquests números en ordre aleatori i tractant de mantenir tot
ordenats a mesura que avança, vostè acaba damunt d'haver de fer un munt de canvi.
Amb certs tipus de cues i certs tipus d'estructures de dades subjacents,
en realitat es pot mantenir bastant simple.
No ha d'afegir alguna cosa i després estudiar la cosa sencera cada vegada.
Tampoc cal fer un munt de desplaçament dels elements interns a la rodona.
Quan ens fixem en una cua, es veu que - també en queue.c en el codi de secció -
l'estructura que li hem donat és molt similar a l'estructura que li va donar per a una pila.
>> Hi ha una excepció a això, i que una excepció
és que tenim aquest sencer addicional diu el cap,
i el cap aquí és per fer el seguiment del cap de la cua,
o el primer element a la cua.
Amb una pila, hem estat capaços de fer un seguiment dels elements que estàvem a punt de recuperar,
o la part superior de la pila, utilitzant només la mida,
mentre que amb una cua, haurem de bregar amb els extrems oposats.
Estem tractant de virar les coses en al final, però després tornen les coses de front.
Així que efectivament, amb el cap, que té l'índex del principi de la cua,
i la mida ens dóna l'índex del final de la cua
perquè puguem recuperar les coses del cap i afegir coses a la cua.
Mentre que amb la pila, només estàvem mai tractar amb la part superior de la pila.
Mai vam haver accedir a la part inferior de la pila.
Només afegeix coses al cim i va prendre les coses fora de la part superior
així que no necessito aquest camp addicional a l'interior del nostre struct.
Això generalment té sentit?
Està bé. Sí, Charlotte? [Charlotte, inintel · ligible]
[Hardison] Això és una gran pregunta, i que va ser el que va ocórrer en la conferència.
Potser caminant a través d'alguns exemples que il · lustren per què
no volem utilitzar cadenes [0] com el cap de la cua.
>> Així que imaginin que tenim la nostra cua, anem a dir-cua.
Al principi, quan acabo d'instància,
quan acabem del declarat, no hem inicialitzat res.
És tot escombraries. Així que, per descomptat, volem estar segurs que inicialitzar
tant la mida i els camps de cap a ser 0, alguna cosa raonable.
També podríem seguir endavant i nuls els elements en la nostra cua.
I per fer aquest ajust diagrama, noti que ara la nostra cua només pot contenir tres elements;
mentre que la nostra pila podria tenir quatre, la nostra cua només pot tenir tres.
I això és només per fer l'ajust diagrama.
El primer que passa aquí és que encolar la cadena "hola".
I de la mateixa manera que vam fer amb la pila, res terriblement diferent aquí,
tirem la corda de les cordes [0] i augmentar el nostre grandària en 1.
Ens encolar "bye", aconsegueix posar.
Per tant això s'assembla a una pila en la seva major part.
Comencem aquí, nou element, l'element nou, la mida segueix pujant.
Què passa en aquest moment en què volem treure de la cua alguna cosa?
Quan volem treure de la cua, que és l'element que volem treure de la cua?
[Basil] Strings [0]. >> Zero. Exactament, Basil.
Volem desfer de la primera cadena, aquest "hola".
Llavors, ¿quina era l'altra cosa que ha canviat?
Avís quan ens vam anar una mica fora de la pila, que acaba de canviar la mida,
però en aquest cas, tenim un parell de coses que canvien.
No només el canvi de mida, però els canvis de cap.
Això va de nou a punt de Charlotte abans:
Per què tenim aquest cap també?
Té sentit ara, Charlotte? Tipus d'>>.
[Hardison] Alguna cosa així? I què va passar quan ens treu de la cua?
Què va fer el cap fer això ara és interessant?
[Charlotte] Oh, perquè va canviar - està bé. Ja veig.
A causa de que el cap - on el cap apunta als canvis en termes de la ubicació.
Ja no és sempre l'índex zero. >> Sí, exactament.
El que va succeir va ser desencolatge si l'element d'alta
es va fer i no teníem aquest camp del cap
perquè sempre estàvem trucant a aquesta cadena a 0 Índex del cap de la nostra cua,
llavors hauríem de passar la resta de la cua cap avall.
Hauríem de canviar "bye" del cadenes [1] per les cadenes [0].
I les cadenes [2] fins a arribar a les cadenes [1].
I hauríem de fer això per tota la llista d'elements,
tot el conjunt d'elements.
I quan fem això amb una matriu, que es posa molt costós.
Així que aquí, no és una gran cosa. Només tenim tres elements de la nostra matriu.
Però si tinguéssim una cua d'un miler d'elements o un milió d'elements,
i després, de sobte, vam començar a fer un munt de treure de la cua crida a tots en un bucle,
les coses realment van a disminuir a mesura que es desplaça per tot constantment.
Ja saps, canviar per 1, per un canvi, canvi per 1, canvi en 1.
En el seu lloc, s'utilitza aquest cap, l'anomenem un "punter", encara que en realitat no és un punter
en sentit estricte, no és un tipus de punter.
No és un * int o char * ni res d'això.
Però s'assenyala o indica el cap de la nostra cua. Sí?
>> [Estudiant] Com treure de la cua saber fer esclatar just al costat del que està al capdavant?
[Hardison] Com treure de la cua saber com fer esclatar tot el que està al cap? Dret >>, si.
>> El que veieu és simplement sigui quin sigui el camp de capçalera s'estableix en.
Així que en aquest primer cas, si mirem aquí mateix,
nostre cap és 0, 0 índex. >> Dret.
[Hardison] Només diu bé, bé, l'element en l'índex 0, la cadena "hola",
És l'element al capdavant de la nostra cua.
Així que anem a treure de la cua d'aquest tipus.
I això serà l'element que es retorna al llamador.
Sí, Saad? >> Així que el cap, bàsicament, estableix la - a on vas a índex?
Aquest és el començament de la mateixa? Sí >>. >> Okay.
[Hardison] Això és esdevenir el nou començament de la nostra matriu.
Així que quan vostè treure de la cua alguna cosa, tot el que has de fer és accedir a l'element en l'índex q.head,
i que serà l'element que voleu treure de la cua.
Vostè també ha de disminuir la mida.
Anem a veure una mica on les coses es posen una mica difícil amb això.
Ens treure de la cua, i ara, si ens encolar novament,
On encolar?
D'on ve l'element següent anar a la nostra col?
Diguem que volem posar en cua la cadena "CS".
En què índex s'ha anat? [Els estudiants] Strings [2]. >> Dos.
Per què no 2 i 0?
[Basil] Perquè ara el cap és 1, pel que és com l'inici de la llista?
[Hardison] Dret. I el que indica el final de la llista?
De què feiem servir per indicar el final de la nostra col?
El cap és el cap de la nostra cua, el principi de la nostra cua.
Quin és el fi de la nostra col? [Els estudiants] mida. >> Mida, exactament.
Així que els nostres nous elements a anar en grandària, i els elements que prenem de sortir al capdavant.
En posar en cua el següent element, l'estem posant a mida.
[Estudiant] Abans de posar això en si, la mida era d'1, no?
[Hardison] Dret. Així que no prou en grandària. Grandària + no, +1, però el cap +.
Com que va canviar tot per la quantitat cap.
Així que aquí, ara tenim una cua de mida 1 que comença en l'índex 1.
La cua és d'índex 2. Sí?
>> [Estudiant] Què passa quan vostè dequeue cadenes [0], i les ranures de les cordes en la memòria
només es buiden, en el fons, o simplement oblidat?
[Hardison] Yeah. En aquest sentit, ens estem oblidant.
Si estiguéssim emmagatzemar còpies d'ells -
moltes estructures de dades sovint s'emmagatzemen les seves pròpies còpies dels elements
de manera que la persona que gestiona l'estructura de dades no ha de preocupar
sobre el qual tots els punters es dirigeix.
L'estructura de dades s'aferra a tot, s'aferra a totes les còpies,
per assegurar-se que tot el que persisteix adequadament.
No obstant això, en aquest cas, aquestes estructures de dades només, per simplicitat,
no estan fent còpies de tot el que estem emmagatzemant en ells.
[Estudiant] Per tant es tracta d'una sèrie contínua de -? Sí >>.
Si mirem cap enrere en el que va ser la definició d'aquesta estructura, ho és.
És només un conjunt estàndard com s'ha vist,
una matriu de char * s.
Això - >> Sí, m'estava preguntant
si finalment es quedarà sense memòria, fins a cert punt,
si vostè té tots aquests llocs buits a la matriu?
[Hardison] Sí, això és un bon punt.
>> Si ens fixem en el que ha passat ara en aquest moment,
hem omplert la nostra cua, com es veu.
Però en realitat no hem omplert la nostra col
perquè tenim una cua que és talla 2, però comença en l'índex 1,
perquè aquí és on el nostre punter cap.
Com vostè deia, aquest element en cadenes [0], en l'índex 0, no està realment allà.
No està en la nostra cua més.
Simplement no es va molestar a entrar i escriure sobre ella quan ho tregui de la cua.
Així que, encara que sembla que ens hem quedat sense memòria, que realment no tenen.
Aquest lloc està disponible per al nostre ús.
El comportament apropiat, si fóssim a tractar de treure de la cua i la primera cosa
com "adéu", que hauria de sortir comiat fora.
Ara el nostre col comença en l'índex 2 i és de mida 1.
I ara, si tractem de posar en cua una mica més, diguem 50,
50 anys han d'anar en aquest punt en l'índex 0
perquè encara disponible. Sí, Saad?
[Saad] açò es farà de forma automàtica?
[Hardison] No passa absolutament automàticament. Cal fer els comptes
per fer que funcioni, però en essència el que hem fet és que hem acaba de finalitzar la voltant.
[Saad] I està bé si aquest té un forat al mig d'ella?
[Hardison] Ho és si podem fer que les matemàtiques funcionen de manera adequada.
>> I resulta que això no és realment tan difícil de fer amb l'operador mod.
Així que igual que vam fer amb César i el material criptogràfic,
utilitzant mod, podem fer les coses per embolicar i seguir endavant
voltant i voltant i voltant amb la nostra cua,
mantenir aquest punter cap es mou al voltant.
Observeu que la mida està respectant sempre el nombre d'elements en realitat dins de la cua.
I és només el punter de cap que es manté amb bicicleta a través.
Si ens fixem en el que va succeir aquí, si ens remuntem al principi,
i que acaba de veure el que passa al cap
quan encolar alguna cosa, no va passar res al cap.
Quan en cua una altra cosa, no va passar res al cap.
Així que es treu de la cua alguna cosa, el cap s'incrementa en un.
Tenim alguna cosa en cua, no passa res al cap.
En llevar de la cua una mica, de sobte el cap s'incrementa.
Quan encolar una cosa, no passa res al cap.
>> Què passaria en aquest moment si haguéssim de treure de la cua alguna cosa nova?
Alguna idea? Què li passaria al cap?
Què ha de passar amb el cap
si haguéssim de treure de la cua una mica més?
El cap ara mateix està en l'índex 2,
el que significa que el cap de la cua és strings [2].
[Estudiant] Això retorna 0? >> S'ha de tornar a 0. Cal embolicar la volta, exactament.
Fins ara, cada vegada que es diu treure de la cua, hem estat afegint un a cap,
afegir un al cap, afegir un a la cap, afegir un a cap.
Així que el punter de cap arriba a l'últim índex en la nostra matriu,
llavors hem de concloure la volta al principi, torna a 0.
[Charlotte] Què determina la capacitat de la cua en una pila?
[Hardison] En aquest cas, només hem estat utilitzant una constant # defineix. >> Okay.
[Hardison] en el fitxer actual. C, es pot anar en fang i amb ell una mica
i fer-ho tan gran o tan petit com vostè vulgui.
[Charlotte] Així que quan vostè està fent una cua, com fer que l'equip sap
la mida que vol que la pila sigui?
[Hardison] Això és una gran pregunta.
Hi ha un parell de maneres. Una d'elles és simplement definir per avançat
i dir que això serà una cua que té 4 elements o elements 50 o 10.000.
L'altra manera és fer el que la gent d'edició de hackers estan fent
i crear funcions perquè la seva cua creix dinàmicament a mesura que s'afegeixen més coses polz
>> [Charlotte] Així que per anar amb la primera opció, el que la sintaxi s'utilitza
per dir-li al programa quin és la mida de la cua?
[Hardison] Ah. Així que sortirem d'això.
Encara estic en stack.c aquí, així que només vaig a desplaçar-se fins la part superior aquí.
Pots veure això aquí? Aquest és el # defineix capacitat 10.
I això és gairebé exactament la mateixa sintaxi que tenim per la cua.
Excepte en la cua, hem de struct camp addicional aquí.
[Charlotte] Oh, vaig pensar que la capacitat de dir la capacitat de la cadena.
[Hardison] Ah. >> Aquesta és la longitud màxima de la paraula. >> Ho tinc.
Si. La capacitat aquí - que és un gran punt.
I això és una cosa que és difícil
perquè el que hem declarat aquí és una matriu de char * s.
Una matriu de punters.
Aquest és un arranjament de caràcters.
Això és probablement el que he vist quan he estat declarant seus buffers per l'arxiu d'E / S,
quan vostè ha estat la creació de cadenes de forma manual a la pila.
No obstant això, el que tenim aquí és una matriu de char * s.
Així que és una matriu de punters.
En realitat, si s'amplia cap a fora i veiem el que està passant aquí
a la presentació, es veu que els elements reals, les dades de caràcter
no s'emmagatzema dins de la pròpia matriu.
Què està emmagatzemada dins la nostra àmplia aquí són punters a les dades de caràcters.
Bé. Així hem vist com la mida de la cua és igual que amb la pila,
la mida respecta sempre el nombre d'elements actualment a la cua.
Després de fer 2 posa en cua, la mida és 2.
Després de fer una dequeue la mida és ara 1.
Després de fer un altre en cua la mida és una còpia de seguretat a 2.
Així, la mida definitivament respecti el nombre d'elements a la cua,
i després el cap només segueix el ciclisme.
Va de 0-1-2, 0-1-2, 0-1-2.
I cada vegada que anomenem a treure de la cua, el punter de cap s'incrementa l'índex següent.
I si el cap està a punt de passar, es torna de nou a 0.
Així que amb això, podem escriure la funció de treure de la cua.
I sortirem de la funció de posada en cua per vostès per posar en pràctica en el seu lloc.
>> En llevar de la cua un element de la nostra cua,
¿Què va ser el primer que va fer Daniel quan vam començar a escriure la funció pop per piles?
Vull sentir d'algú que no ha parlat encara.
A veure, Saad, te'n recordes del que Daniel va fer el que la primera cosa quan va escriure pop?
[Saad] No, va ser - >> Va provar per alguna cosa.
[Saad] Si la mida és major que 0. >> Exactament.
I què era que les proves d'?
[Saad] Això estava provant per veure si hi ha alguna cosa a l'interior de la matriu.
[Hardison] Yeah. Exactament. Pel que no pot fer esclatar qualsevol cosa fora de la pila si està buit.
De la mateixa manera, no es pot treure de la cua des d'una cua si està buit.
Què és el primer que hem de fer en la nostra funció de treure de la cua aquí, et sembla?
[Saad] Si la mida és més gran que 0? Sí >>.
En aquest cas, he fet només una prova per veure si és 0.
Si és 0, es pot tornar null.
Però la lògica mateixa.
I seguirem amb això.
Si la mida no és 0, on és l'element que voleu treure de la cua?
[Saad] Al capdavant? >> Exactament.
Només podem treure el primer element de la nostra cua
mitjançant l'accés a l'element al cap.
Res boig.
Després d'això, què hem de fer? ¿Què ha de passar?
Quina era l'altra cosa que hem parlat en treure de la cua?
Dues coses han de passar, perquè la nostra col ha canviat.
[Daniel] Reduir la mida. >> Hem de reduir la mida i augmentar el cap? Exactament.
Per augmentar el cap, no podem simplement a cegues augmenten el cap, recorda.
No podem fer queue.head + +.
Hem de incloure també aquest mod per la capacitat.
I per què mod per la capacitat, Stella?
[Stella] Perquè ha de embolicar. >> Exactament.
Ens mod per la capacitat, ja que ha de embolicar al voltant de nou a 0.
Així que ara, en aquest punt, podem fer el que va dir Daniel.
Podem disminuir la mida.
I llavors només pot tornar l'element que estava a la part superior de la cua.
S'assembla una mica al principi Gnarly. És possible que tingui una pregunta. Com diu?
>> [Sam] Per què és primer en la part superior de la cua? D'on ve això?
[Hardison] Ve de la quarta línia de la part inferior.
Després de realitzar proves per assegurar-se que la nostra cua no és buida,
ens retirem char * primer, treure l'element que seu en l'índex cap
de la nostra matriu, de la nostra àmplia cordes, anomenada >> i que per primera vegada?
[Hardison] I en diem primer. Si.
Només per donar seguiment a això, per què creus que havíem de fer això?
[Sam] Cada primer s'acaben de tornar q.strings [q.head]? Sí >>.
>> Perquè estem fent aquest canvi de la q.head amb la funció mod,
i no hi ha manera de fer-ho dins de la línia de retorn també.
[Hardison] Exactament. Vostè és el clau. Sam està totalment en el clau.
La raó per la qual va haver de retirar-se el primer element de la nostra cua i emmagatzemar en una variable
és perquè aquesta línia on havíem q.head just,
aquí està l'operador mod en què no és una cosa que puguem fer
i que tingui efecte al cap sense - en una sola línia.
Així que en realitat hem de treure el primer element, a continuació, ajust el cap,
ajustar la mida, i després tornar l'element que ens retirem.
I això és una cosa que veurem sorgir més tard amb
llistes enllaçades, com jugar amb ells.
Sovint, quan vostè està alliberant o l'eliminació de les llistes enllaçades
cal recordar el següent element, el punter següent d'una llista enllaçada
abans de disposar de l'actual.
Perquè d'una altra manera de desfer-se de la informació del que queda a la llista.
Ara, si vostè va al seu dispositiu, s'obre queue.c--x d'això.
Així que si obro queue.c, deixa zoom aquí,
veuràs que té un arxiu d'aspecte similar.
D'aspecte similar a l'arxiu del que teníem abans amb stack.c.
Tenim la nostra estructura de col definida tal com vam veure en les diapositives.
>> Tenim la nostra funció en cua que és per tu per fer.
I tenim la funció de treure de la cua aquí.
La funció de treure de la cua a l'arxiu no s'ha implementat,
però ho vaig a posar de nou en el PowerPoint perquè pugui escriure, si ho desitja.
Així que per als propers 5 minuts més o menys, vostès treballen en enqueue
que és gairebé el contrari de treure de la cua.
No ha d'ajustar el cap quan estàs encolem, però què s'ha d'ajustar?
Mida. Així que quan en cua, el cap es manté intacte, la mida es canvia.
Però es necessita una mica de - vostè haurà de jugar amb aquest mod
d'esbrinar exactament el que l'índex de l'element nou ha d'inserir al.
Així que vaig a donar a vostès una mica, posar treure de la cua de nou a la diapositiva,
i com vostès tenen preguntes, els criden perquè puguem
tots parlen d'ells com a grup.
A més, amb la mida que no - en ajustar la mida, sempre pots fer sol -
Què ha de mod la mida cada vegada? [Daniel] >> No No ha de mod de la mida, clar.
Com que la mida sempre, si TEU AQUESTES - assumint que vostè està manejant les coses adequadament,
la mida sempre serà d'entre 0 i 3.
On cal mod quan estàs fent en col?
[Estudiant] Només per al cap. >> Només per al cap, exactament.
I per què has de mod en absolut en enqueue?
Quan es tracta d'una situació en què hauria de mod?
[Estudiant] Si tens coses a espais, com en els espais 1 i 2,
i llavors havia de afegir alguna cosa a 0.
[Hardison] Sí, exactament. Així que si el seu cap és punter al final,
o si la mida del seu cap és més gran, o més aviat, es va a embolicar al voltant de la cua.
>> Així que en aquesta situació que tenim aquí a la diapositiva en aquest moment,
si vull posar en cua alguna cosa en aquest moment,
volem posar en cua una mica en l'índex 0.
Així que si ens fixem en que el 50 va i em crida enqueue 50,
i surt allà baix a la part inferior. Va en índex 0.
Substitueix a la 'hola' que va ser llevat de la cua ja.
[Daniel] No es té cura que en treure de la cua ja?
Per què fer alguna cosa amb el cap posat en cua?
[Hardison] Oh, així que no estem modificant el cap, em sap greu.
Però vostè ha d'utilitzar l'operador mod quan s'està accedint
l'element que voleu posar en cua quan s'està accedint
el següent element a la cua.
[Basil] Jo no ho vaig fer, i em van donar l '"èxit" en aquest país.
[Daniel] Oh, entenc el que estàs dient.
[Hardison] Així que didn't - vostè acaba de fer en q.size?
[Basil] Yeah. Acabo de canviar costats, jo no vaig fer res amb el cap.
[Hardison] En realitat no ha de restablir el cap per ser qualsevol cosa,
però quan es índex en la matriu cordes,
de fet has de seguir endavant i calcular on l'element següent és,
perquè Withe la pila, el següent de la pila sempre va ser
en l'índex corresponent a la mida.
Si mirem enrere cap a la nostra funció push pila,
sempre podem desemborsar en el nostre element nou a la dreta en la grandària de l'índex.
Mentre que amb la cua, no podem fer això
perquè si estem en aquesta situació,
si tenim en cua 50 nostra cadena de nou a la dreta en cadenes [1]
que no volem fer.
Volem tenir la nova cadena va en l'índex 0.
>> Algú - Sí? [Estudiant] Tinc una pregunta, però no és realment relacionats.
Què significa quan algú es diu alguna cosa així com punter pred?
Quina és l'abreviatura d'aquest nom? Sé que és només un nom.
[Hardison] Pred punter? Anem a veure. En quin context?
[Estudiant] Era per a la inserció. Et puc preguntar després si vols
perquè no és realment relacionats, però només I -
[Hardison] Des del codi d'inserció de David de conferència?
Podem aconseguir això i parlar-ne.
Parlarem d'això després, un cop arribem a llistes enllaçades.
>> Així que anem molt ràpid cop d'ull al que la funció de posada en cua sembla.
Què va ser el primer que la gent va tractar de fer en la seva línia de posada en cua? En aquesta cua?
Igual que el que vas fer per pila empenyent.
Què vas fer, Stella?
[Stella, inintel · ligible]
[Hardison] Exactament. Si (q.size CAPACITAT ==) -
He de posar les meves claus al lloc correcte - retorna fals.
Apropar una mica. Bé.
Ara, ¿què és el següent que hem de fer?
Igual que amb la pila, i s'insereix en el lloc correcte.
I el que era el lloc adequat per inserir això?
Amb la pila era mida de l'índex, amb això no és exactament això.
[Daniel] Tinc q.head--o - q.strings >>? >> Yeah.
q.strings [+ q.head q.size mod CAPACITAT]?
[Hardison] És probable que vulgui posar entre parèntesi aquesta
pel que estem rebent l'adequada prioritat i per això és cleart a tothom.
I estableix que la igualtat? >> Per str? >> Per str. Gran.
I ara, què és l'últim que hem de fer?
Igual que vam fer a la pila. >> Incrementar la mida? >> Incrementar la mida.
Boom. I després, ja que el codi d'arrencada només retorna false per defecte,
volem canviar aquesta propietat a true si tot va a través i tot va bé.
Està bé. Això és un munt d'informació per a la secció.
No estem molt a sobre. Volem parlar molt ràpid sobre simplement enllaçada llistes.
Vaig a posar això perquè puguem tornar-hi més tard.
Però tornem a la nostra presentació per uns pocs més diapositives.
Així enqueue és TOT, ara ho hem fet.
>> Ara donem una ullada a simplement enllaçada llistes.
Parlem d'aquests una mica més a classe.
Quants de vostès van veure la demostració en la que hi havia gent
torpemente assenyalant a cada un dels altres nombres i explotació? >> Jo estava en això.
>> Què pensen vostès? Això, espero que desmitificar aquests poc una mica?
Amb una llista, resulta que ens ocupem d'aquest tipus que anomenarem a un node.
Mentre que amb la cua i pila que ens prenem les estructures que ens criden a la cua a la pila,
teníem aquestes nova cua en els tipus de pila,
aquí una llista està realment format per un grup de nodes.
De la mateixa manera que les cadenes són més que un munt de caràcters tots alineats un al costat de l'altre.
Una llista enllaçada és només un node i node a un altre ia un altre node i el node a un altre.
I en lloc de trencar tots els nodes entre si i el seu emmagatzematge contigua
tots un al costat de l'altre en la memòria,
tenint aquest punter següent ens permet emmagatzemar els nodes on sigui, a l'atzar.
I a continuació, tipus de filferro a tots junts per assenyalar d'una a la següent.
>> I quina va ser la gran avantatge que això té sobre una matriu?
Durant tot l'emmagatzematge contigua just enganxat un al costat de l'altre?
Te'n recordes? Sí? Assignació dinàmica de memòria >>?
>> Assignació dinàmica de memòria en quin sentit?
[Estudiant] En que es pot seguir fent més gran i vostè no ha de moure el conjunt complet?
[Hardison] Exactament. Així que amb una matriu, quan vostè vol posar un nou element en el medi d'ella,
vostè ha de canviar tot per a fer lloc.
I com parlem amb la cua,
és per això que mantenir aquest punter cap,
pel que no estem canviant constantment les coses.
Com que resulta car si tens una gran varietat
i que està constantment fent aquestes insercions aleatòries.
Mentre que amb una llista, l'únic que has de fer és tirar en un nou node,
ajustar els punters, i ja està.
Què merda sobre això?
A part del fet que no és tan fàcil de treballar com una matriu? Sí?
[Daniel] Bé, crec que és molt més difícil tenir accés a un element específic de la llista enllaçada?
[Hardison] No es pot saltar a un element arbitrari en el medi de la llista enllaçada.
Com s'ha de fer en el seu lloc? >> Vostè ha de recórrer tota la cosa.
[Hardison] Yeah. Vostè ha d'anar a través d'un en un, un a la vegada.
És un enorme - és un dolor.
Quina és l'altra - no hi ha una altra caiguda a això.
[Basil] No es pot anar cap endavant i cap enrere? Has d'anar a una adreça?
[Hardison] Yeah. Llavors, ¿com resoldre això, algunes vegades?
[Basil] doblement enllaçada llistes? >> Exactament. Hi ha llistes doblement enllaçades.
Hi ha també - ho sento?
>> [Sam] És això el mateix que utilitzar el que predefinit -
Acabo de recordar, no és el que la cosa pred serveix?
No és en el medi i doblement sols?
Mirada [Hardison] Anem a què és exactament el que estava fent.
Així que aquí anem. Aquí està la llista de codis.
Aquí tenim predptr, aquí. És això el que estaves parlant?
Així que aquesta va ser - que ha alliberant una llista i que està tractant d'emmagatzemar un punter a ell.
Aquesta no és la doblement, lligada simplement llistes.
Podem parlar més sobre això més endavant ja que es parla de l'alliberament de la llista
i vull mostrar algunes altres coses primer.
però és igual - és recordar el valor de ptr
[Estudiant] Oh, és punter precedent? Sí >>.
Així que llavors sí pot incrementar ptr abans de llavors lliure predptr ho és.
Perquè no podem gratis ptr i després trucar a ptr = ptr següent, no?
Això seria dolent.
Així que anem a veure, de nou a aquest home.
>> L'altra cosa dolenta sobre les llistes és que, si bé amb una sèrie
només tenim tots els elements mateixos apilats un al costat a l'altre,
aquí també hem introduït aquest punter.
Així que hi ha una porció addicional de memòria que estem tenint d'utilitzar
per a cada element que s'està emmagatzemant en la nostra llista.
Tenim la flexibilitat, però té un cost.
Ve amb el cost de temps,
i ve amb aquest cost de memòria també.
Temps en el sentit que ara hem d'anar a través de cada element de la matriu
per trobar l'índex d'un a 10, o que hauria estat índex 10 en una matriu.
>> Només molt ràpid, quan ens diagrama terme aquestes llistes,
normalment ens aferrem al capdavant de la llista o el primer indicador de la llista
i compte que aquest és un punter veritable.
És a 4 bytes. No és un node en si.
Així que ja veus que no té cap valor int-hi, cap punter següent en el mateix.
És, literalment, només un punter.
Es va a apuntar a alguna cosa que és una struct node actual.
[Sam] Punter anomenat node? >> Aquesta és - no. Aquest és un punter a una cosa de tipus node.
És un punter a una estructura de node. >> Oh, està bé.
Diagrama sobre el codi de l'esquerra, a la dreta.
Podem posar-ho en null, el que és una bona manera de començar.
Quan ho diagrama, o bé escriure com nul o es posa una línia a través d'ell d'aquesta manera.
>> Una de les maneres més fàcils per treballar amb llistes,
i els demanem fer les dues coses anteposar i annexar a veure les diferències entre els dos,
però anteposant és definitivament més fàcil.
Quan s'anteposa, aquí és on vostè - quan vostè prepend (7),
ves i crear l'estructura de node
i s'estableix primer en assenyalar, perquè ara, ja que s'anteposa,
que estarà al principi de la llista.
Si prepend (3), que crea un altre node, però 3 ara ve abans de les 7.
Així que bàsicament estàs portant les coses a la nostra llista.
Ara, vostè pot veure que anteposar, de vegades en diuen empènyer,
perquè vostè està empenyent un nou element en la seva llista.
També és fàcil d'esborrar a la part davantera d'una llista.
Així que la gent sol anomenar a aquest pop.
I d'aquesta manera, es pot emular una pila utilitzant una llista enllaçada.
Whoops. Em sap greu, ara estem entrant en annexats. Així que aquí estem anteposat (7), ara prepend (3).
Si s'anteposa altra cosa en aquesta llista, si s'anteposa (4),
llavors tindríem 4 i després 3 i després 7.
Llavors podríem pop i treure 4, treure 3, retiri 7.
Sovint, la forma més intuïtiva de pensar en això és amb annexats.
Així que he diagramat el que es veuria amb afegir aquí.
En aquest sentit, afegeix (7) no es veu diferent
perquè només hi ha un element a la llista.
I afegint (3) el posa al final.
Potser vostè pot veure ara el truc amb append
és que des que només sap on és el principi de la llista és,
per annexar a una llista del que has de caminar tot el camí a través de la llista
per arribar a la final, detenir, a continuació, crear el node i tot plunk avall.
Cablejar totes les coses.
Així que amb prefix, com s'acaba de copiar a través d'aquest molt ràpid,
quan s'anteposa a una llista, que és bastant simple.
>> Vostè fa el seu nou node, impliquen alguna assignació de memòria dinàmica.
Així que aquí estem fent un struct node usant malloc.
Així que estem usant malloc, ja que deixarà de banda la memòria per nosaltres per més endavant
perquè no volem que això - volem que aquesta memòria a persistir durant molt de temps.
I tenim un punter a l'espai en la memòria que acaba de ser assignat.
Utilitzem mida del node, no concretem els camps.
No generar manualment el nombre de bytes,
en lloc d'això utilitzar sizeof perquè sapiguem que estem rebent la quantitat adequada de bytes.
Ens assegurem de provar que la nostra crida malloc èxit.
Això és una cosa que vull fer en general.
En les màquines modernes, quedant sense memòria no és una cosa que és fàcil
llevat que l'assignació d'un munt de coses i fer una llista enorme,
però si vostè està construint coses per, per exemple, com un iPhone o Android an,
que tenen recursos limitats de memòria, especialment si vostè està fent alguna cosa intens.
Així que és bo tenir en la pràctica.
>> Tingueu en compte que he fet servir un parell de funcions diferents aquí
que vostè ha vist que són una espècie de nou.
Així fprintf és com printf
excepte el seu primer argument és el corrent a la qual voleu imprimir.
En aquest cas, volem imprimir a la cadena d'error estàndard
que és diferent de la outStream estàndard.
Per defecte es mostra en el mateix lloc.
També imprimeix a la terminal, però es pot -
utilitzant les ordres que ha après sobre les tècniques de redireccionament,
que vam aprendre en vídeo de Tommy com a conjunt de problemes 4, pot dirigir-
a les diferents àrees, a continuació, sortir, aquí, surt del seu programa.
Bàsicament es tracta de com tornar a principal,
excepte que utilitzem sortida perquè aquí retorn no farà res.
No estem en principal, de manera que torna no se surti del programa com nosaltres volem.
Per això, utilitzem la funció de sortida i donar-li un codi d'error.
Llavors aquí ens vam posar camp del nou node de valor, el seu camp i sigui igual a i, i després el cablejar.
Hem establert punter següent del nou node per assenyalar a la primera,
i després 1 ara anirà al nou node.
Aquestes primeres línies de codi, en realitat estem construint el nou node.
No les dues últimes línies d'aquesta funció, però els primers.
En realitat es pot extreure en una funció, en una funció auxiliar.
Això és moltes vegades el que faig és que em tiri en una funció,
Jo en dic alguna cosa com a node de generació,
i que manté la funció prepend bastant petit, és només 3 línies a continuació.
Faig una crida a la meva funció de node de generació, i llavors tot filferro cap amunt.
>> L'última cosa que vull mostrar,
i deixaré que facis append i tot això pel seu compte,
és la forma d'iterar sobre una llista.
Hi ha un munt de maneres diferents per iterar sobre una llista.
En aquest cas, anem a calcular la longitud d'una llista.
Així que vam començar amb longitud = 0.
Això és molt similar a l'escriptura strlen per una cadena.
Això és el que vull mostrar, per aquest circuit aquí.
S'assembla una mica covard, no és el típic int i = 0, i <el que sigui, i + +.
En el seu lloc, hi ha la inicialització de la nostra variable n com el començament de la llista.
I llavors, mentre la variable Iterador no és nul, és seguir endavant.
Això és perquè, per convenció, al final de la llista serà nul.
I a continuació, per incrementar, en lloc de fer + +,
l'equivalent llista vinculada de + + és n = n-> següent.
>> Vaig a deixar d'omplir els buits aquí perquè estem fora de temps.
Però cal tenir això en ment a mesura que treballa en conjunts de processadors teus spellr.
Les llistes enllaçades, si està implementant una taula hash,
sens dubte vindrà en molt pràctic.
I tenir aquest idioma per recórrer les coses faran la vida molt més fàcil, amb sort.
Qualsevol pregunta, ràpidament?
[Sam] Va a enviar el acabat sll i sc?
[Hardison] Yeah. Vaig a enviar diapositives acabades i la pila completa sll i queue.cs.
[CS50.TV]