[Powered by Google Translate] [Article 6] [més còmode] [Rob Bowden] [Harvard University] [Aquesta és CS50.] [CS50.TV] 

Ens pot dirigir-se a les preguntes. Vaig enviar a l'adreça de l'espai abans. El principi de la secció de les preguntes-dir pel que sembla, no estic del tot unsick-És una pregunta molt fàcil del que s'acaba de Valgrind? Què Valgrind fer? Algú vol dir el Valgrind fa? [Estudiant] comprova la memòria de fuites. Sí, Valgrind és un corrector de memòria general. És, en definitiva, li diu si té alguna pèrdua de memòria, que és sobre tot el que s'està fent servir per perquè si vols bé en el conjunt de problemes o desitja aconseguir en el gran tauler, cal no tenir pèrdues de memòria en absolut, i en cas de tenir una pèrdua de memòria que no es pot trobar, També tingui en compte que cada vegada que obri un arxiu i si no el tanca, això és una pèrdua de memòria. 

Molta gent està buscant algun node que no estan alliberant quan en realitat, no tancar el diccionari en el primer pas. També li indica si vostè té qualsevol invàlid llegeix o escriu, el que significa que si vostè tracta d'establir un valor que està més enllà del final de la pila i no passa a la culpa seg però Valgrind l'agafa, ja que en realitat no hauria d'estar escrivint allà, i pel que definitivament no hauria de tenir cap d'aquests tampoc. Com s'utilitza Valgrind? Com s'utilitza Valgrind? 

És un problema general de tipus d'executar i veure el resultat. La sortida està aclaparant un munt de vegades. També hi ha errors de diversió on si tenen alguna cosa malament, molt malament ocorre en un bucle, a continuació, amb el temps es diu: "Massa errors. Vaig a deixar de comptar ara ". Es tracta bàsicament d'una sortida de text que cal analitzar. Al final, li dirà qualsevol fuga de memòria que té, quants blocs, que pot ser útil perquè si es tracta d'un unfreed bloc, llavors en general és més fàcil de trobar de 1.000 blocs unfreed. 1.000 blocs unfreed probablement vol dir que no estàs alliberant seves llistes enllaçades adequadament o alguna cosa així. Això Valgrind. 

Ara tenim les preguntes, que no és necessari per a descarregar. Podeu fer clic en el meu nom i tiri cap amunt a l'espai. Ara feu clic a mi. Revisió 1 serà pila, el que estem fent en primer lloc. Revisió 2 serà cua i Revisió 3 serà la llista lligada senzilla. Partint de la nostra pila. Com es diu aquí, una pila és un dels més bàsics, estructures de dades fonamentals de la informàtica. L'exemple prototípic és molt la pila de safates al menjador. És, bàsicament, cada vegada que s'introdueixen a una pila, algú dirà: "Oh, com una pila de safates". Vostè apilar les safates de dalt. Llavors, quan vostè va a tirar una safata, la primera safata que està deixant-nos arrossegar és l'últim que es va posar a la pila. La pila també-com diu aquí- tenim el segment de memòria anomenada pila. I per què es diu la pila? 

Perquè igual que una estructura de dades pila, l'empeny i fa esclatar els marcs de pila a la pila, on els marcs de pila és com una crida d'una funció. I igual que una pila, sempre haurà de tornar a partir d'una crida a la funció abans que pugui posar-se en marcs de pila baixa de nou. No es pot tenir anomenada principal bar anomenat foo bar i tornar a directament principal. Sempre ha de seguir la pila correcta empenyent i fent esclatar. Les dues operacions, com he dit, són push i pop. Aquests són termes universals. Vostè ha de saber push i pop en termes de piles sense importar el que passi. Anem a veure les cues són una mica diferents. En realitat no tenen un terme universal, però push i pop són universals per a piles. Inserció s'acaba de posar a la pila. Pop és treure la pila. I veiem aquí tenim la nostra pila struct typedef, així que tenim carbó cordes **. No t'espantis per qualsevol **. Això acabarà sent una matriu de cadenes o una matriu de punters a caràcters, on punters a caràcters tendeixen a ser cadenes. No ha de ser cadenes, però aquí, que seran cadenes. 

Tenim una matriu de cadenes. Tenim una mida, que representa quants elements hi ha actualment a la pila, i llavors tenim la capacitat, que és com els elements reflectides a la pila. La capacitat ha de començar com una cosa més gran que 1, però la mida que començarà a 0. Ara, hi ha bàsicament tres maneres diferents que vostè pot pensar en una pila. Bé, probablement hi ha més, però són les dues formes principals es pot implementar utilitzant una matriu, o es pot implementar utilitzant una llista enllaçada. Les llistes enllaçades són una espècie de trivial de fer munts de. És molt fàcil fer una pila amb llistes enllaçades, Així que aquí, farem una pila amb matrius, i després usant arrays, també hi ha dues maneres de pensar-hi. Abans, quan em va dir que tenim una capacitat de la pila, pel que pot encaixar un element a la pila. 

L'única manera que podria passar és així que es va colpejar 10 elements, llavors ja està. Vostè pot saber que hi ha un límit superior de 10 coses al món que mai tindrà més de 10 coses a la pica, en aquest cas pot tenir un límit superior en la grandària del seu stack. O vostè podria tenir el seu stack ser il · limitada, però si vostè està fent un arranjament, el que significa que cada vegada que va connectar 10 elements, llavors vostè haurà de créixer a 20 elements, i quan arribi a 20 elements, vostè haurà de fer créixer la seva matriu a 30 elements o elements 40. Vas a haver d'augmentar la capacitat, que és el que farem aquí. Cada vegada que arribi la mida màxima del nostre stack, quan empenyem una mica més endavant, haurem de augmentar la capacitat. Aquí, hem declarat com empenta empenta bool (char * str). * Char str és la cadena que estem impulsant a la pila, bool i només diu si hem tingut èxit o ha fracassat. 

Com no? Quina és l'única circumstància que es pugui imaginar on ens havíem de tornar falsa? Si. [Estudiant] Si és complet i estem usant una aplicació limitada. Sí, així que com podem definir-va respondre si és ple i estem usant una aplicació limitada. Llavors sens dubte tornarem falsa. Així que vam arribar a les 10 coses de la matriu, no podem encaixar 11, de manera que retorna fals. I si no té límits? Si. Si no es pot expandir la matriu per alguna raó. Sí, així que la memòria és un recurs limitat, i, finalment, si guardem les coses que empenyen a la pila una i altra vegada, tractarem d'assignar una matriu més gran per encaixar el de major capacitat, i malloc o el que sigui que estem fent servir es tornarà false. Bé, malloc tornarà null. 

Recordeu, cada vegada que tornis a cridar malloc, vostè ha de comprovar per veure si retorna un valor nul o del que és una deducció correcta. Com volem tenir una pila sense límits, l'únic cas que tornarem false si és que tractem de augmentar la capacitat i malloc o el torna false. Després pop no té arguments, i retorna la cadena que està a la part superior de la pila. El més recent va ser a la pila pop és el que va a tornar, i també s'elimina de la pila. I noti que retorna null si no hi ha res a la pila. Sempre és possible que la pila està buida. En Java, si estàs acostumat a això, o en altres idiomes, tractant de fer esclatar d'una pila buida pot provocar una excepció o alguna cosa així. 

Però en C, null és una cosa que molts dels casos, com manejar aquests problemes. Tornant nul és com anem a indicar que la pila estava buit. Hem proporcionat el codi que posarà a prova la funcionalitat de la seva pila, el implementar push i pop. Això no hi haurà un munt de codi. Ho faré-en realitat, abans de fer això, pista, pista- si vostè no ho ha vist, malloc no és l'única funció que assigna memòria en el munt per a vostè. Hi ha una família de funcions Alloc. La primera és malloc, que estem acostumats. Després hi calloc, que fa el mateix que malloc, però va a zero tot per a tu. Si alguna vegada has volgut posar tot en nul després mallocing alguna cosa vostè ha d'haver utilitzat calloc en primer lloc en comptes d'escriure un bucle for per posar en zero el bloc de memòria. 

Realloc és com malloc i té un munt de casos especials, però bàsicament el que fa és realloc Es triga un punter que ja havia estat assignat. Realloc és la funció que desitgi prestar atenció a aquí. Es pren un punter que ja s'havien tornat de malloc. Diguem de sol · licitar a malloc un punter de 10 bytes. Després, més tard t'adones que volien 20 bytes, així que truqui realloc en aquest punter amb 20 bytes, i realloc copiat automàticament sobre totes les coses per a vostè. Si vostè acaba de trucar a malloc nou, com si tingués un bloc de 10 bytes. Ara necessito un bloc de 20 bytes, així que si malloc 20 bytes, llavors he de copiar manualment durant els 10 bytes de la primera cosa en el segon i després alliberar la primera cosa. Realloc s'encarregarà d'això per tu. 

Note la signatura serà void *, que s'acaba de tornar un punter al bloc de memòria, llavors void * ptr. Vostè pot pensar void * com a punter genèric. En general, no ha de tractar amb void *, però malloc retorna un void *, i llavors és només utilitzat com això és en realitat serà un char *. La void * anterior que havia estat retornat per malloc ara passarà a realloc, i després la mida és el nou número de bytes que voleu assignar, de manera que la seva nova capacitat. Et vaig a donar un parell de minuts, i fer-ho al nostre espai. Comenceu amb Revisió 1. Et vaig a parar després d'esperar al voltant de temps suficient per aplicar pressió, i després em vaig a donar un altre descans per fer pop. Però en realitat no és que el codi molt a tots. La majoria del codi és probablement la matèria en expansió, l'expansió de la capacitat. Està bé, no hi ha pressió per estar completament acabat, però sempre que vostè se sent com si estiguessis en el camí correcte, això és bo. 

Algú té algun codi que se sentin còmodes amb mi tirant cap amunt? Sí, ho faré, però algú té algun codi que pugui aixecar? D'acord, pot començar, el guarda, el que sigui? Sempre se m'oblida aquest pas. Bé, mirant push, Vols explicar la teva codi? [Estudiant] En primer lloc, he augmentat la mida. Suposo que potser jo hauria de tenir això, de tota manera, he augmentat la mida, i veig si és menor que la capacitat. I si és inferior a la capacitat, que s'afegeixen al sistema que ja tenim. I si no ho és, jo multiplicar la capacitat per 2, i reassignar la matriu de cadenes a alguna cosa amb una mida major capacitat ara. I si això no funciona, li dic a l'usuari i retornar false, i si està bé, llavors vaig posar la cadena al nou lloc. 

[Rob B.] Observeu també que es va utilitzar un bon operador de bits aquí a multiplicar per 2. Recordeu, desviació a l'esquerra sempre serà multiplicat per 2. Desplaçament a la dreta es divideix per 2, sempre que recordi que això significa dividir per 2 com en un nombre enter dividit per 2. Pot truncar 1 gen aquí o allà. Però desplaçament a l'esquerra per una sempre serà multiplicat per 2, llevat que desbordament dels límits del nombre enter, i llavors no serà. Un comentari al marge. M'agrada fer, això no canviarà la codificació de qualsevol manera que sigui, però m'agradaria fer alguna cosa com això. En realitat, es farà una mica més. Potser aquest no és el cas perfecte per demostrar això, però m'agrada segment que en aquests blocs de- bé, si això si succeeix, llavors jo vaig a fer alguna cosa, i llavors la funció es porta a terme. Jo no hagi de desplaçar després meus ulls tot el camí per la funció per veure el que passa després de l'altra persona. És aquest cas, si s'escau, llavors simplement tornar. També té el benefici afegit de totes les coses bones més enllà d'aquesta està desplaçat a l'esquerra un cop. Ja no necessito si mai prop ridículament llargues files, llavors aquests 4 bytes pot ajudar, i també és el una mica més a l'esquerra, el menor es senti aclaparat si agrada-bo, he de recordar Actualment estic en un bucle while dins d'un interior més d'un bucle for. En qualsevol lloc que vostè pot fer aquest canvi immediatament, m'agrada bastant. És totalment opcional i no s'espera de cap manera. 

[Estudiant] Hi ha d'haver una mida - en la condició de fallada? La condició de falla aquí és que no realloc, així que sí. Observi com en la condició de fallada, presumiblement, llevat que la matèria lliure més tard, sempre fallarem no importa quantes vegades tractem d'empènyer alguna cosa. Si seguim pressionant, seguim incrementant la mida, tot i que no està posant res a la pila. En general, no incrementen la mida fins després hem aconseguit posar a la pila. Pel que li fem, diem, ja sigui aquí i aquí. I llavors, en lloc de dir s.size capacitat ≤, és inferior a la capacitat, només perquè ens mudem on era tot. 

I recordi, l'únic lloc que podria tornar false És aquí, on realloc retorna null, i si et quedes a recordar error estàndard, potser vostè podria considerar aquest cas, una en què voleu imprimir un error estàndard, stderr fprintf així en lloc d'imprimir directament a la sortida estàndard. Un cop més, això no és una expectativa, però si es tracta d'un error, escriure printf, llavors és possible que vulgueu fer que imprimeixi a un error estàndard en lloc de la sortida estàndard. 

Algú té alguna cosa més que observar? Sí [Estudiant] Es pot passar el [inaudible]? [Rob B.] Sí, el binariness real d'ell o només el que és? [Estudiant] Així ho multipliques per 2? [Rob B.] Sí, bàsicament. En terra binari, sempre tenim el nostre conjunt de dígits. Desplaçament d'aquesta esquerra per un Bàsicament s'insereix aquí al costat dret. Tornar a això, només recordar que tot en binari és una potència de 2, de manera que això representa 2 al 0, aquest 2 a la 1, 2 està a la 2. Mitjançant la inserció d'un 0 a un costat ara mateix, simplement canviar tot de nou. El que solia ser de 2 a 0 és ara de 2 a 1, és 2 a la 2. El costat dret que inserim necessàriament serà 0, la qual cosa té sentit. Si mai multiplicar un nombre per 2, que no acabarà estrany, pel que el 2 a 0 el lloc ha de ser 0, i això és el que hi ha advertit abans és que si et quedes a passar més enllà del nombre de bits en un nombre sencer, llavors aquest 1 acabarà sonant. Aquesta és l'única preocupació si vostè passa estar tractant amb capacitats molt grans. Però en aquest moment, llavors vostè està tractant amb un arsenal de milers de milions de coses, que no va poder cabre en la memòria de totes maneres. 

Ara podem arribar a pop, la qual cosa és encara més fàcil. Podries m'agrada si et passa fer esclatar un munt, i ara està a la meitat de la capacitat de nou. Vostè podria realloc per reduir la quantitat de memòria que té, però vostè no ha de preocupar per això, de manera que el cas realloc només serà creixent memòria, mai encongiment memòria, que farà súper pop fàcil. Ara cues, que seran com piles, però la finalitat que es prengui les coses s'inverteix. En l'exemple prototípic d'una cua és una línia, així que suposo que si fossis Anglès, hauria dit un exemple prototípic d'una cua és una cua. Així com una línia, si vostè és la primera persona a la fila, que espera ser la primera persona fora de la línia. Si vostè és l'última persona a la fila, vostè serà la persona atesa passat. D'això en diem model FIFO, mentre pila era patró LIFO. Aquestes paraules són bastant universal. 

Igual que les piles i no com els arrays, les cues no solen permetre l'accés als elements del medi. Aquí, una pila, tenim push i pop. A continuació, passem a els he anomenat en cua i treure de la cua. També he sentit que diu canvi i unshift. He sentit a gent dir push i pop també s'apliquen a les cues. He sentit a inserir, eliminar, així push i pop, si vostè està parlant de piles, que està empenyent i fent esclatar. Si vostè està parlant sobre les cues, es pot escollir les paraules que voleu utilitzar per a la inserció i eliminació, i no hi ha consens sobre el que ha de ser anomenat. Però aquí, hem de posar en cua i treure de la cua. Ara bé, l'estructura es veu gairebé idèntica a l'estructura de la pila. Però hem de fer un seguiment del cap. Suposo que ho diu per aquí, però per què necessitem el cap? Els prototips són bàsicament idèntics push i pop. Vostè pot pensar en ell com push i pop. L'única diferència és pop torna-en lloc de l'última, està tornant la primera. 2, 1, 3, 4, o alguna cosa així. I aquí hi ha el principi. La nostra cua està completament ple, així que hi ha quatre elements que conté. El final de la nostra cua és actualment 2, i ara anem a inserir una altra cosa. 

Quan volem inserir aquesta cosa més, el que vam fer per a la versió de pila Es ampliem el nostre bloc de memòria. Quin és el problema amb això? [Estudiant] Mou el 2. El que vaig dir abans sobre l'extrem de la cua, això no té sentit que comencem a 1, llavors volem treure de la cua 1, després treure de la cua 3, després treure de la cua 4, a continuació, treure de la cua 2, a continuació, treure de la cua d'aquest. No podem utilitzar realloc ara, o si més no, vostè ha d'utilitzar realloc d'una manera diferent. Però és probable que no només ha d'utilitzar realloc. Vostè haurà de copiar manualment la memòria. 

Hi ha dues funcions per copiar la memòria. Hi ha memcopy i memmove. Actualment estic llegint les pàgines del manual per veure quin et voldrà utilitzar. Bé, memcopy, la diferència és que memcopy i memmove, un maneja el cas correctament on està copiant en una regió que passa a superposar-se a la regió que està copiant. Memcopy no manejar. Memmove fa. Vostè pot pensar en el problema, ja que- diguem que voleu copiar aquest tipus, aquests quatre a aquest tipus de nou. Al final, el que la matriu ha de ser similar després que la còpia és 2, 1, 2, 1, 3, 4, i després una mica de matèria en l'extrem. Però això depèn de l'ordre en què realment copiar, ja que si no considerem el fet que la regió s'està copiant en es superposa a la qual estem copiant d', llavors podríem fer aquí com a inici, copieu el 2 en el lloc on voleu anar, a continuació, passar els nostres punters cap endavant. 

Ara anem a ser aquí i aquí, i ara volem copiar aquest tipus a través d'aquest tipus i moure nostres punters cap endavant. El que anem a acabar rebent és de 2, 1, 2, 1, 2, 1 en lloc de la 2, 1, 2, 1, 3, 4 perquè 2, 1 va fer cas omís de l'original 3, 4. Memmove que maneja correctament. En aquest cas, bàsicament, només utilitzeu sempre memmove perquè es maneja correctament. En general, no realitza cap pitjor. La idea és en lloc de començar des del principi i la còpia d'aquesta manera com ho acaba de fer aquí, s'inicia des de l'extrem i el copia en, i en aquest cas, mai es pot tenir un problema. No hi ha pèrdua de rendiment. Utilitzeu sempre memmove. No et preocupis per memcopy. I aquí és on vostè va a haver de memmove per separat la porció embolicada-al voltant de la seva cua. No us preocupeu si no està completament acabat. Això és més difícil que la pila, empenta, i el pop. 

Algú té algun codi que podríem treballar? Encara totalment incomplet? [Estudiant] Sí, és totalment incomplet, però. Completament incomplet està bé, sempre i quan, es pot estalviar la revisió? Em oblit que cada vegada. Bé, fent cas omís del que passa quan hem de canviar la mida de les coses. Ignoren completament canvi de mida. Explicar aquest codi. Estic comprovant en primer lloc si la mida és menor que la primera còpia de tots i després d'això, inserit-R + prendre el cap de mida, i m'asseguro que s'embolica al voltant de la capacitat de la matriu, i puc inserir la nova cadena en aquesta posició. Llavors puc augmentar la mida i tornar true. 

[Rob B.] Aquest és definitivament un d'aquells casos en què vas a voler utilitzar mod. Qualsevol tipus de cas en què ha d'embolicar al voltant, si et sembla embolicar al voltant, el primer pensament ha de ser mod. Com una optimització ràpida / fer que el codi una línia més curta, t'adones que la línia immediatament després d'aquest és només la mida + +, de manera que es fusionen en aquesta línia, la mida + +. Ara aquí baix, tenim el cas en el qual no té prou memòria, pel que estem augmentant la nostra capacitat per 2. Crec que es pot tenir el mateix problema aquí, però podem ignorar ara, on si no per augmentar la seva capacitat, llavors vostè va a voler disminuir la seva capacitat de 2 de nou. Una altra nota curta és igual que ho pot fer + =, també es pot fer << =. Gairebé qualsevol cosa pot passar abans d'iguals, + =, | =, + =, << =. Char * nou és el nostre nou bloc de memòria. Oh, per aquí. 

Què pensa la gent de la classe del nostre nou bloc de memòria? [Estudiant] Ha de ser char **. Pensant en la nostra estructura fins aquí, cadenes és el que estem reassignant. Estem fent tota una nova dinàmica per a l'emmagatzematge dels elements de la cua. El que anem a assignar a les cadenes és el que estem mallocing en aquest moment, i tan nou que serà un char **. Serà una matriu de cadenes. Llavors, quin és el cas en què ens tornarem fals? [Estudiant] Hauríem d'estar fent char *? [Rob B.] Sí, bona idea. [Estudiant] Què va ser això? [Rob B.] Volíem fer mida de char * perquè ja no som- en realitat això seria un problema molt gran perquè sizeof (char) seria 1. Sizeof char * serà 4, de manera que una gran quantitat d'ocasions en què estem tractant sencers, es tendeix a sortir amb la seva perquè la mida de int i la mida de int * en un sistema de 32-bit serà la mateixa cosa. Però aquí, sizeof (char) i sizeof (char *) són ara serà la mateixa cosa. 

Quina és la circumstància en què tornem fals? [Estudiant] Nou és nul. Sí, si és nou és nul, es retorna fals, i em vaig a tirar per aquí- [Estudiant] [inaudible] [Rob B.] Sí, això està molt bé. Vostè podria fer 2 vegades la capacitat o la capacitat d'un canvi, i només llavors la col · loqui aquí o el que sigui. Ho farem com ho teníem. Capacitat >> = 1. I mai anem a haver de preocupar de perdre el seu lloc l'1 perquè et vas canviat per 1, de manera que l'1 de lloc és necessàriament un 0, tan a la dreta per un canvi, vostè encara estarà bé. [Estudiant] Cal fer-ho abans de la tornada? [Rob B.] Sí, això no té cap sentit. 

Ara suposem que acabarem tornant true fins al final. La manera com farem aquestes memmoves, hem de anar amb compte amb la manera com ells ho fan. Algú té algun suggeriment de com ho fem? Aquest és el nostre principi. Inevitablement, volem començar des del principi una altra vegada i coses de còpia en des d'allà, 1, 3, 4, 2. Com es fa això? En primer lloc, he de mirar a la pàgina del manual de memmove nou. Memmove, l'ordre dels arguments de sempre és important. Volem que el nostre primer destí, la segona font, la tercera mida. Hi ha una gran quantitat de funcions que reverteixen origen i destinació. Destinació, la font tendeix a ser una mica consistent. Moure, el que l'hi tornarà? Retorna un punter a la destinació, per qualsevol raó vostè podria voler això. M'imagino a llegir, però volem avançar en el nostre destí. 

Quin és el nostre destí serà? [Estudiant] Nou. [Rob B.] Sí, i on som copiant? El primer que està copiant és aquest 1, 3, 4. Quin és l'est-1, 3, 4. Quina és l'adreça d'aquest 1? Quina és la direcció que 1? [Estudiant] [inaudible] [Rob B.] + Cara la direcció del primer element. Com fem perquè el primer element de la matriu? [Estudiant] Queue. [Rob B.] Sí, q.strings. Recordeu, aquí, el nostre cap: 1. Maleïda sigui. Jo només crec que és per art de màgia- Aquí, el nostre cap és 1. Vaig a canviar el meu color també. I aquí està cordes. Això, ens pot escriure com ho vam fer aquí amb caps + q.strings. Molta gent també escriu i q.strings [cap]. Això no és realment una mica menys eficient. Es podria pensar-hi com ho està dereferencing i després obtenir l'adreça de, el compilador traduirà al que teníem abans de tota manera, q.strings + cap. De qualsevol manera desitjada pensar-hi. 

I quants octets volem copiar? [Estudiant] Capacitat - cap. Capacitat - cap. I llavors sempre es pot escriure un exemple per esbrinar si és cert. [Estudiant] Ha de ser dividit per 2 a continuació. Sí, així que suposo que podria utilitzar grandària. Encara tenim mida és- usant mida, que tenen una mida igual a 4. El nostre mida és 4. La nostra cap és 1. Volem copiar aquests 3 elements. Aquesta és la comprovació de validesa d'aquesta mida - cap està correctament 3. I tornant aquí, com hem dit abans, si utilitzem la capacitat, llavors hauríem de dividir per 2 perquè ja hem crescut nostra capacitat, de manera que en el seu lloc, utilitzarem la mida. Que les còpies de les porcions. Ara, hem de copiar l'altra part, la part que queda de la sortida. 

Això va a memmove en quina posició? [Estudiant] més de la mida - el cap. Sí, de manera que ja ha copiat en la mida - bytes del cap, i per tant on volem copiar els bytes restants és nou i després la mida de menys-bé, el nombre de bytes que ja hem copiat polz I llavors, on som copiant? [Estudiant] Q.strings [0]. [Rob B.] Sí, q.strings. Podíem fer i q.strings [0]. Això és significativament menys freqüent que això. Si només serà 0, llavors vostè tendeix a veure q.strings. Aquí és on estem copiant. Quants bytes què ens queda per copiar? >> [Estudiant] 10. Dreta. [Estudiant] Hem de multiplicar 5 - 10 vegades la mida dels bytes o alguna cosa així? Sí, així és, què és exactament on estem copiant? [Estudiant] [inaudible] Quin és el tipus de cosa que està copiant? [Estudiant] [inaudible] Sí, de manera que el char * s que estem copiant, no sé d'on els estan venint. Bé, on són assenyalant, com les cordes, acabem empenyent a la cua o enqueuing a la cua. Quan els estan venint, no tenim ni idea. Només hem de perdre de vista el char * s mateixos. No volem copiar mida - octets cap. Volem copiar mida - cap char * s, així que anem a multiplicar per sizeof (char *). Igual aquí baix, el cap * sizeof (char *). 

[Estudiant] Què passa amb [inaudible]? Aquest dret aquí? [Estudiant] No, més avall, la mida - el cap. [Rob B.] Aquest dret aquí? Aritmètica de punters. Com aritmètica de punters es treballarà és automàticament es multiplica per la mida del tipus que estem tractant. Igual que aquí, nou + (mida - el cap) és exactament equivalent a & [size - cap] nou fins que esperem que funcioni correctament, ja que si estem tractant amb una matriu int, llavors no ho fem índex int- o si és d'una mida de 5 i desitja que el 4 º element, llavors l'índex en int matriu [4]. No-[4] * La mida de int. Això es gestiona de forma automàtica, i en aquest cas és, literalment, equivalent, de manera que la sintaxi de suport és només serà convertit en això tan aviat com es compila. Això és una cosa que has de tenir cura que en agregar mida - cap va a afegir no un byte. Vostè va a afegir un char *, que pot ser una bytes o el que sigui. 

Altres preguntes? Està bé, treure de la cua serà més fàcil. Et vaig a donar un minut d'implementar. Oh, i suposo que aquesta és la mateixa situació en què el que el cas en cua, si estem enqueuing nul, potser volem tractar-lo, potser no ho fem. No ho tornaré a fer aquí, però igual que el nostre cas pila. Si encolar nul, el que es vol és passar per alt. Algú té algun codi que pot aixecar? [Estudiant] Només tinc treure de la cua. La versió 2 és que-bé. Vostè vol explicar? [Estudiant] En primer lloc, assegureu-vos que hi ha alguna cosa a la cua i que la grandària va a la baixa a 1. Que ha de fer això, i després que torni el cap i després moure el cap cap amunt 1. Està bé, així que hi ha un cas de la cantonada hem de tenir en compte. Si. [Estudiant] Si el teu cap està en l'últim element, llavors vostè no vol el cap per assenyalar fora de la matriu. 

Sí, tan aviat com el cap a la final de la nostra matriu, quan treure de la cua, el cap ha de ser MODDED nou a 0. Desafortunadament, no podem fer això en un sol pas. Crec que la manera com probablement solucionar és això serà un char *, el que estem tornant, independentment del nom de la variable vol ser. Llavors volem mod cap per la nostra capacitat i després tornar ret. Molta gent d'aquí es podria fer- Aquest és el cas de-vostè veure la gent fer si el cap és més gran que la capacitat, fer el cap - la capacitat. I això és només treballar en entorn del que és mod. Cap mod = capacitat és molt més net d'un embolcall al voltant de si el cap més gran que el cap de capacitat - capacitat. 

Preguntes? Bé, l'últim que ens queda és la nostra llista enllaçada. Pot ser utilitzat per alguns dels comportaments llista enllaçada si ho has fet llistes enllaçades a les taules hash, si es va fer una taula hash. Recomano fer una taula hash. És possible que ja han fet un triennis, sinó que tracta són més difícils. En teoria, són asimptòticament millor. Però n'hi ha prou amb veure la gran pissarra, i tracta de no fer millor, i ocupen més memòria. Tot el relacionat intenta acaba sent pitjor per a un treball més. És el que David Malan solució sempre és Sempre posts seva solució triennis, i veurem on actualment està. El que ell estava sota, David J? És número 18, de manera que no és terriblement dolent, i que serà un dels millors intents que es pugui imaginar o un dels millors tracta d'un triennis. No és tan sols el seu solució original? Em sento com triennis solucions tendeixen a ser més en aquest rang d'ús de memòria RAM. 

Ves a la part superior, i l'ús de la memòria RAM és d'un sol dígit. Anar cap al fons, i després es comencen a veure intenta on s'obté l'ús de RAM absolutament massiva, i tries són més difícils. No del tot, però val la pena una experiència educativa si es va fer una. L'últim és la llista enllaçada, i aquestes tres coses, piles, cues i llistes enllaçades, qualsevol cosa futur el que fas a la informàtica assumirà que té familiaritat amb aquestes coses. Ells són tan fonamental per a tot. 

Llistes enllaçades, i aquí tenim una llista lligada simple serà la nostra implementació. Què significa enllaç simple en comparació amb doblement enllaçada? Sí [Estudiant] només apunta al següent punter en lloc dels punters, com la que li precedeix i el que el segueix. Sí, i en format de imatge, què he fet? Tinc dues coses. Tinc imatge i imatge. En format d'imatge, la nostra llista lligada simple, inevitablement, tenim algun tipus de punter al capdavant de la llista, i després dins de la llista, només tenim punters, i potser això apunta null. Serà un dibuix típic d'una llista lligada senzilla. Una llista doblement enllaçada, pot anar cap enrere. Si et dono un node a la llista, llavors necessàriament pot arribar a qualsevol altre node a la llista si es tracta d'una llista doblement enllaçada. Però si vostè aconsegueix el tercer node de la llista i es tracta d'una llista lligada simple, hi ha manera que mai arribarà als nodes de primera i segona. I hi ha avantatges i inconvenients, i un una evident Se li ocupen més grandària, i s'ha de perdre de vista que aquestes coses estan apuntant ara. Però només es preocupen per enllaç simple. 

Un parell de coses que haurem d'implementar. El node typedef struct, int i: struct node * següent; node. Això typedef ha de ser cremat en les seves ments. Quiz 1 ha d'ésser com donar un typedef d'un node de llista enllaçada, i vostè hauria de ser capaç de fer gargots que immediatament sota sense tan sols pensar-hi. Suposo que un parell de preguntes, per què necessitem struct aquí? Per què no podem dir * node? [Estudiant] [inaudible] Si. L'única cosa que defineix un node com una cosa és el propi typedef. Però a partir d'aquest moment, quan estem com l'anàlisi a través d'aquesta definició de node estructura, no hem acabat el nostre typedef encara, així que des del typedef no ha acabat, node no existeix. Però struct node fa, i aquest node aquí, això també podria ser cridat qualsevol altra cosa. Això podria anomenar núm. Es podria dir node de la llista enllaçada. Es podria dir qualsevol cosa. Però aquest node d'estructura ha de ser anomenat el mateix que aquest node d'estructura. El que vostè diu això ha de ser també aquí, i de manera que també respon al segon punt de la qüestió raó per la qual, moltes vegades, quan vostè veu les estructures i typedefs de les estructures, podràs veure les estructures anònimes on vostè acaba de veure typedef struct, implementació d'estructura, diccionari, o el que sigui. 

Per què aquí hem de dir node? Per què no pot ser una struct anònim? És gairebé la mateixa resposta. [Estudiant] Cal fer referència en l'estructura. Sí, dins de l'estructura, cal fer referència a la pròpia estructura. Si no dóna l'estructura d'un nom, si és un struct anònim, no es pot fer referència a ella. I finalment, aquests no han de ser tan senzill alguna cosa, i ells l'ajudaran a adonar-se que si estàs escrivint això que vostè està fent alguna cosa malament si aquest tipus de coses no tenen sentit. Finalment, però no menys important, per què té això de ser * struct node? Per què no poden simplement ser struct node següent? [Estudiant] Punter a l'estructura següent. Això és inevitable el que volem. Per què mai podia ser struct node següent? Per què ha de ser node * següent estructura? Si. [Estudiant] És com un bucle infinit. Si. [Estudiant] Tot seria en un. Sí, només pensar en el que faríem mida o alguna cosa així. Mida d'una estructura és bàsicament + o - algun patró aquí o allà. És, bàsicament, serà la suma de les mides de les coses en l'estructura. Aquest dret aquí, sense canviar res, la mida serà fàcil. Mida de node struct serà la mida de i + de mida pròxim. Mida d'i serà 4. Mida de la que ve serà 4. Mida de node struct serà 8. Si no tenim el *, pensant en sizeof, a continuació, sizeof (i) serà 4. Mida de node struct següent serà la mida de i + mida de node struct següent + Mida de i + mida de struct node següent. Seria una recursió infinita de nodes. Per això, és així com les coses han de ser. 

Un cop més, sens dubte que memoritzar, o almenys ho entenc bastant que vostè pot ser capaç de raó per la qual cosa ha de ser similar. Les coses que anem a voler implementar. Si la longitud de la llista- vostè podria enganyar i mantenir al voltant d'un longitud global o alguna cosa, però no farem això. Anem a explicar la longitud de la llista. Hem conté, de manera que, bàsicament, com una recerca, així que tenim una llista enllaçada d'enters per veure si aquest sencer és a la llista enllaçada. Anteposar es va a inserir en el començament de la llista. Append es va a inserir al final. Insert_sorted es va a inserir en la posició de la llista ordenada. Tipus de Insert_sorted assumeix que mai ha utilitzat anteposar o annexar en mals passos. 

Insert_sorted quan estàs implementant insert_sorted- diguem que tenim la nostra llista enllaçada. Això és el que actualment sembla, 2, 4, 5. Vull inserir 3, així que sempre que la llista en si ja està ordenat, és fàcil de trobar en 3 pertany. Començo a 2. D'acord, 3 és més gran que 2, així que vull seguir endavant. Oh, 4 és massa gran, així que sé 3 va a anar entre 2 i 4, i he de arreglar els punters i totes aquestes coses. Però si no ens utilitzin exclusivament insert_sorted, com direm d'anteposar 6, llavors la meva llista enllaçada es convertirà això. Ara no té sentit, així que per insert_sorted, només pot assumir que la llista està ordenada, tot i que hi ha operacions que pot fer que no es classifiquen, i això és tot. Trobi un útil insert-aquestes són les coses principals que vostè va a haver de posar en pràctica. 

Per ara, prengui un minut per fer la longitud i conté, i els que han de ser relativament ràpida. En apropar l'hora de tancament, de manera que ningú té res per llarg o conté? Seran gairebé idèntics. [Estudiant] Longitud. A veure, a revisió. Bé. Vostè vol explicar? [Estudiant] Acabo de crear un node punter i inicializarla a la primera, que és la nostra variable global, i després comprovo per veure si és nul, així que no et donen una falla seg i tornar 0 si aquest és el cas. En cas contrari, recórrer, fer el seguiment de dins sencera quantes vegades m'he accedit al següent element de la llista i en l'operació d'increment mateixa també accés a aquest element real, i llavors jo contínuament fer el xec per veure si és nul, i si és nul, llavors s'avorta i només retorna el nombre d'elements que he accedit. 

[Rob B.] Algú té algun comentari sobre qualsevol cosa? Això es veu molt bé la correcció savi. [Estudiant] No crec que es necessita el node == null. Sí, i si el node == 0 retorna null. Però si el node == null llavors aquesta-oh, hi ha un problema de correcció. Era just que estiguis i tornar, però no és d'abast en aquests moments. Només té int i, pel que = 0. Però si el node és nul, llavors jo encara serà 0, i tornarem 0, de manera que aquest cas és idèntic. Una altra cosa comuna és mantenir la declaració de node dins del bucle for. Es podria dir que-oh, no. Anem a mantenir-lo com aquest. Probablement em posaria int i = 0 aquí, llavors el node node = * primer aquí. I aquesta és probablement la forma-desfer d'això ara. Aquesta és probablement la forma en què ho hagi escrit. Vostè podria també-veure-ho així. Aquesta estructura de bucle aquí ha de ser gairebé tan natural per a tu com per int i = 0 i és menor que la longitud d'array i + +. Si així és com iterar sobre una matriu, així és com recórrer un llista enllaçada. 

Aquesta ha de ser la naturalesa segons en algun moment. Amb això en ment, això serà gairebé el mateix. Vostè va a voler per iterar sobre una llista enllaçada. Si el node-No tinc ni idea de quin és el valor que es diu. Node i. Si el valor en el node i = return true, i això és tot. Tingueu en compte que l'única manera que alguna vegada torno fals si és iterar sobre la llista sencera vinculats i mai tornar true, així que això és el que fa. Com a nota lateral, és probable que no s'arriba a afegir o anteposar. 

Última nota ràpida. Si vostè veu la paraula clau static, pel que direm static int compte = 0, llavors el que fem compte + +, bàsicament es pot pensar en ella com una variable global, tot i que acabo de dir no és així com anem a implementar longitud. Estic fent això aquí, i després comptar + +. De qualsevol manera que puguem entrar en un node a la llista enllaçada estem incrementant el nostre compte. El punt d'això és el que significa la paraula clau static. Si només tingués int count = 0 que seria un habitual variable global edat. Quins mitjans estàtic int compte és que es tracta d'una variable globals d'aquest fitxer. És impossible per algun altre arxiu, agrada pensar en pset 5, si vostè ha començat. Vostè té tant speller.c, i vostè té dictionary.c, i si el que declara una cosa global, llavors qualsevol cosa en speller.c Es pot accedir a dictionary.c i viceversa. Les variables globals són accessibles a qualsevol arxiu. C, però les variables estàtiques només es pot accedir des del propi arxiu, així que dins de corrector ortogràfic oa l'interior de dictionary.c, això és una mica com havia de declarar la meva variable per la mida de la meva matriu o la mida del número de paraules al diccionari. Com que no és necessari declarar una variable global que ningú té accés, En realitat només es preocupen per ell per als meus propis fins. 

El millor d'això és també la matèria col · lisió nom complet. Si algun altre arxiu intenta utilitzar una variable global anomenada recompte, les coses van malament, molt malament, pel que aquesta bé manté les coses segures, i només es pot accedir, i ningú més pot fer-ho, i si algú es declara una variable global anomenada recompte llavors no va a interferir amb la variable estàtica anomenada recompte. Això és el que és estàtic. És una variable global d'arxius. 

Les preguntes sobre qualsevol cosa? Tot llest. Bye. [CS50.TV]