[Powered by Google Translate] [Artikel 6] [meer gemaklik] [Rob Bowden] [Harvard Universiteit] [Hierdie is CS50.] [CS50.TV] 

Ons kan die hoof aan ons afdeling van vrae. Ek het die URL vir die spasie voor. Die begin van die afdeling van die vrae sê glo ek is nie heeltemal unsick is 'n baie maklike vraag net wat valgrind? Wat beteken valgrind doen? Iemand wil hê om te sê wat valgrind doen? [Studente] Checks geheue lekkasies. Ja, valgrind is 'n algemene geheue checker. Dit, in die einde, vertel as jy 'n geheue lekkasies, wat meestal wat dit ons gebruik vir want as jy wil doen goed in die probleem te stel of as jy wil kry op die groot bord, moet jy nie die geheue lekkasies na hoegenaamd, en in die geval dat jy 'n geheue lek wat jy nie kan kry, ook in gedagte hou dat wanneer jy 'n lêer oopmaak en as jy nie naby dit, dit is 'n geheue lek. 

'N baie van die mense is op soek vir 'n paar node dat hulle nie bevry terwyl dit in werklikheid, het hulle nie naby die woordeboek in die heel eerste stap. Dit vertel ook as jy het 'n ongeldige lees of skryf, wat beteken dat as jy probeer en stel 'n waarde wat is buite die ent van die hoop, en dit nie gebeur seg skuld maar valgrind vang dit, as jy eintlik moet skryf nie daar, en sodat jy moet seker nie enige van daardie óf. Hoe gebruik jy valgrind? Hoe gebruik jy valgrind? 

Dit is 'n algemene vraag van soort van loop en kyk na die uitset. Die uitset is oorweldigend 'n klomp van die tye. Daar is ook pret foute waar as jy het 'n paar vreeslik verkeerde ding gebeur in 'n lus, dan is dit uiteindelik sal sê, "te veel foute. Ek gaan om te stop toe nou. " Dit is basies tekstuele produksie wat jy hoef te parse. Op die ou end, sal dit vir jou 'n geheue lekkasies wat jy het, hoeveel blokke, wat nuttig kan wees, omdat as dit is een blok unfreed, dan is dit gewoonlik makliker om te vind as 1000 blokke unfreed. 1000 blokke unfreed beteken waarskynlik dat jy nie bevry geskakelde lyste gepas of iets. Dis valgrind. 

Nou het ons ons deel van die vrae, wat jy nie nodig het om af te laai. Kan jy kliek op my naam en trek hulle op in die ruimte. Klik nou op my. Hersiening 1 stapel, wat ons eers doen. Hersiening 2 sal ry, en Hersiening 3 sal die enkel geskakelde lys. Die begin af met ons stapel. As dit hier sê, 'n stapel is een van die mees basiese, basiese datastrukture van rekenaarwetenskap. Die baie prototipiese voorbeeld is die stapel van die bak in die eetsaal. Dit is basies wanneer jy word bekendgestel aan 'n stapel, iemand gaan om te sê, "O, soos 'n stapel van die bak." Jy pak die bak. Dan wanneer jy gaan 'n skinkbord te trek, die eerste skinkbord wat om getrek is die laaste een wat op die stapel geplaas is. Ook die stapel soos dit sê hier- ons het die segment van die geheue genoem die stapel. En waarom word dit genoem die stapel? 

Want soos 'n stapel data struktuur, dit stoot en verskyn stapel rame op die stapel, waar stack rame is soos 'n spesifieke oproep van 'n funksie. En soos 'n stapel, sal jy altyd om terug te keer van 'n funksie oproep voordat jy kan kry in 'n laer stapel rame weer. Jy kan nie oproep foo oproep bar en kroeg terugkeer na die hoof direk. Dit is altyd die korrekte stapel stoot en knal het om te volg. Die twee operasies, soos ek sê, is druk en pop. Dit is universele terme. Druk en pop in terme van die stapels maak nie saak wat jy moet weet. Ons sal sien toue is soort van verskillende. Dit maak nie regtig 'n universele term, maar druk en pop is universeel vir stapels. Push is net op die stapel geplaas. Pop is die stapel af te neem. En ons sien hier het ons ons typedef struct stapel, so ons het char ** snare. Kry nie bang deur enige **. Dit gaan uiteindelik om 'n verskeidenheid van snare of 'n verskeidenheid van verwysings na karakters, waar verwysings na karakters is geneig om te wees snare. Dit hoef nie te wees snare, maar hier is hulle gaan wees snare. 

Ons het 'n verskeidenheid van snare. Ons het 'n grootte wat verteenwoordig hoeveel elemente is tans op die stapel, en dan het ons die kapasiteit, wat is hoeveel elemente kan wees op die stapel. Die vermoë moet begin as iets groter as 1, maar die grootte is gaan om te begin as 0. Nou, daar is basies drie verskillende maniere wat jy kan dink van 'n stapel. Wel, daar is waarskynlik meer, maar die twee hoof maniere wat jy kan implementeer dit met behulp van 'n skikking, of jy dit kan implementeer dit met behulp van 'n geskakelde lys. Geskakelde lyste is die soort van triviale stapels te maak. Dit is baie maklik om 'n stapel te maak met behulp van geskakelde lyste, so hier gaan ons 'n stapel te maak met behulp van skikkings, en dan met behulp van skikkings, daar is ook twee maniere waarop jy kan dink oor dit. Voor, toe ek gesê het ons het 'n kapasiteit vir die stapel, sodat ons kan 'n element te pas op die stapel. 

Die een manier waarop dit kan gebeur, is so gou as wat jy getref het 10 elemente, dan is jy klaar. Jy kan weet dat daar is 'n bogrens van 10 dinge in die wêreld dat jy nooit meer as 10 dinge wat op jou stapel, in welke geval jy kan 'n bogrens op die grootte van jou stapel. Of jy kan jou stapel ongeleide, maar as jy 'n skikking te doen, beteken dit dat elke keer as jy getref 10 elemente, dan is jy gaan hê om te groei tot 20 elemente, en wanneer jy druk op 20 elemente, jy gaan hê om jou skikking te groei tot 30 elemente of 40 elemente. Jy gaan nodig om die kapasiteit te verhoog, en dit is wat ons gaan doen. Elke keer as ons die maksimum grootte van ons stapel bereik, wanneer ons iets anders op te stoot, gaan ons nodig het om die kapasiteit te verhoog. Hier het ons stoot verklaar as Bool push (char * str). Char * str is die string wat ons is besig om op die stapel, en Bool sê net of ons daarin geslaag of misluk. 

Hoe kan ons nie? Wat is die enigste omstandighede waaraan jy kan dink waar ons nodig sou wees om terug te keer vals? Ja. [Studente] As dit is vol en ons is met behulp van 'n begrens implementering. Ja, so hoe definieer hy ons antwoord as dit vol is en ons met behulp van 'n begrensde implementering. Dan sal ons beslis vals terugkeer. So gou as wat ons getref het 10 dinge in die skikking, kan ons nie pas 11, sodat ons terugkeer vals. Wat as dit ongeleide? Ja. As jy nie kan die skikking vir een of ander rede uit te brei. Ja, so geheue is 'n beperkte hulpbron, en uiteindelik, as ons stoot dinge op die stapel oor en oor weer, ons gaan om te probeer en die toekenning van 'n groter verskeidenheid te pas die groter kapasiteit, en malloc of wat ookal ons gebruik gaan om terug te keer vals. Wel, sal malloc terugkeer null. 

Onthou, elke keer as jy al ooit malloc roep, moet jy beheer word om te sien of dit terug null of anders wat is 'n korrektheid aftrekking. Aangesien ons wil 'n ongeleide stapel te hê, die enigste geval ons gaan terugkeer vals is as ons probeer om verhoog die kapasiteit en malloc of wat terug vals. Dan pop neem geen argumente, en dit gee die string wat op die top van die stapel. Wat ook al is mees onlangs op die stapel gestoot is wat pop terugkeer, en dit ook verwyder dit uit die stapel. En let op dat dit terugkeer null indien daar is niks op die stapel. Dit is altyd moontlik dat die stapel is leeg. In Java, as jy gewoond is aan, of ander tale, probeer om uit 'n leë stapel te pop kan veroorsaak dat 'n uitsondering of iets. 

Maar in C, null is 'n soort van 'n baie van die gevalle hoe ons hierdie probleme hanteer. Terugkeer null is hoe ons hier gaan om aan te dui dat die stapel was leeg. Ons het voorsien kode wat sal toets jou stapel se funksionaliteit, implementeer stoot en pop. Dit sal nie 'n baie van die kode. Ek sal eintlik, voordat ons dit doen, hint, wenk- as jy dit nie gesien het, malloc is nie die enigste funksie wat ken geheue op die hoop vir jou. Daar is 'n familie van alloc funksies. Die eerste is malloc, wat jy gebruik om. Dan is daar calloc, wat nie dieselfde ding as malloc, maar dit alles sal nul vir jou. As jy al ooit wou alles te stel aan nul nadat mallocing iets jy moet net gebruik het calloc in die eerste plek in plaas van die skryf van 'n lus na nul uit die hele blok geheue. 

Realloc is soos malloc en het 'n baie spesiale gevalle, maar basies wat realloc doen, is wat dit neem om 'n wyser wat reeds toegeken is. Realloc is die funksie wat jy wil word aandag hier. Dit neem 'n wyser wat reeds van malloc teruggestuur is. Kom ons sê jy vra van malloc 'n wyser van 10 grepe. Dan later besef jy dat jy wou 20 bytes, sodat jy noem realloc op dat die wyser met 20 bytes, en realloc sal outomaties kopieer oor alles vir jou. As jy net genoem malloc weer, soos ek het 'n blok van 10 grepe. Nou moet ek 'n blok van 20 bytes, so as ek malloc 20 grepe, dan ek het met die hand te kopieer oor die 10 grepe uit die eerste ding wat in die tweede ding, en dan vry om die eerste ding. Realloc sal hanteer dit vir jou. 

Let op die handtekening gaan void * wat net 'n wyser terug na die blok van die geheue, dan nietig * ptr. Jy kan dink van void * as 'n generiese wyser. In die algemeen, sal jy nooit gaan met nietig *, maar malloc terugkeer 'n leemte *, en dan is dit net gebruik soos dit is eintlik gaan na 'n char *. Die vorige void * wat deur malloc teruggestuur is gaan nou geslaag word realloc, en dan grootte is die nuwe getal grepe wat jy wil te ken, sodat jou nuwe hoedanigheid. Ek gee jou 'n paar minute, en doen dit in ons ruimte. Begin met Hersiening 1. Ek sal keer dat jy na hopelik oor genoeg tyd om druk uit te voer, en dan gee ek jou n ander breek pop te doen. Maar dit is regtig nie veel kode op alle. Die meeste kode is waarskynlik die groeiende dinge, die uitbreiding van die kapasiteit. Okay, geen druk om te moet stiptelik uitgevoer word, maar so lank as wat jy voel jy is op die regte pad, dit is goed. 

Is daar iemand enige kode wat hulle gemaklik voel met my te trek? Ja, ek wil nie, maar nie almal het 'n kode wat ek kan trek? Goed, jy kan begin, dit stoor, wat dit ookal is? Ek het altyd vergeet dat stap. Goed, op soek na die druk, doen wat jy wil om jou kode te verduidelik? [Studente] Eerste van alles, het ek die grootte toegeneem. Ek dink miskien moet ek dat in elk geval, ek het die grootte, en ek sien as dit is minder as die kapasiteit. En as dit is minder as die kapasiteit, voeg ek die skikking wat ons reeds het. En as dit is nie, sal Ek vermenigvuldig die kapasiteit deur 2, en ek hertoeken die snare array iets met 'n groter kapasiteit grootte. En dan indien dit misluk, sê Ek vir die gebruiker en return false, en as dit is goed, dan sal ek die tou in die nuwe plek. 

[Rob B.] Let ook op dat ons hier 'n mooi bis-operateur met 2 te vermenigvuldig. Onthou, links verskuiwing is altyd gaan word vermenigvuldig met 2. Regs verskuiwing is so lank verdeel deur 2 as jy onthou dat dit beteken verdeel deur 2 as in 'n heelgetal gedeel deur 2. Dit kan afgeknot 'n 1 hier of daar nie. Maar verskuiwing gelaat deur 1 is altyd gaan word vermenigvuldig met 2, tensy jy oorloop die grense van die heelgetal, en dan sal dit nie wees nie. A-span kommentaar. Ek hou te doen dit is nie van plan om die kodering op hoegenaamd enige manier te verander, maar ek hou van iets soos hierdie te doen. Dit is eintlik gaan om te maak dit 'n bietjie langer. Miskien is dit die ideale geval om dit te wys nie, maar ek wil om dit te segment in hierdie blokke van- okay, as dit as gebeur, dan is ek gaan om iets te doen, en dan die funksie gedoen word. Ek hoef nie te blaai my oë al die pad af die funksie om te sien wat gebeur na die ander. Dit is indien dit as gebeur, dan het ek net terug te keer. Dit het ook die mooi bykomende voordeel van alles verby hierdie is nou een keer verskuif links. Ek nie meer tot-as jy ooit naby belaglik lang rye nodig het, dan die 4 bytes kan help, en ook die meer links iets is, die minder oorweldig jy voel as graag okay, ek het om te onthou Ek is tans in 'n while lus binnekant van 'n anders binnekant van 'n for-lus. Waar jy kan hierdie opgawe dadelik te doen, het ek soort van soos. Dit is heeltemal opsioneel en sal na verwagting nie op enige manier. 

[Studente] Indien daar 'n grootte - in die misluk toestand? Die misluk toestand hier is ons versuim het om te realloc, so ja. Let op hoe in die misluk toestand, vermoedelik, tensy ons free stuff later, ons is altyd gaan om te misluk maak nie saak hoeveel keer ons probeer om iets te stoot. As ons aanhou druk, hou ons verhoog van grootte, selfs al is ons nie om enigiets op die stapel. Gewoonlik inkrementeer ons nie die grootte tot nadat ons dit suksesvol op die stapel. Ons sal dit doen, sê, hetsy hier en hier. En dan in plaas van sê s.size ≤ kapasiteit, dit is minder as kapasiteit, net omdat ons verhuis waar alles is. 

En onthou, die enigste plek wat ons moontlik return false is hier, waar realloc teruggekeer null, en as jy gebeur standaard fout om te onthou, miskien kan jy dalk dit 'n geval oorweeg waar jy wil 'n standaard fout te druk, so fprintf stderr in plaas van net te druk direk na standaard uit. Weereens, dit is nie 'n verwagting, maar as dit is 'n fout, tik printf, dan kan jy dalk wil om te maak dit druk op die standaard fout in plaas van die standaard uit. 

Iemand iets anders om daarop te let? Ja. [Studente] Kan jy gaan oor die [onhoorbaar]? [Rob B.] Ja, die werklike binariness dit of presies wat dit is? [Studente] So jy vermenigvuldig dit met 2? [Rob B.] Ja, basies. In binêre land, het ons altyd ons stel van syfers. Verskuiwing hierdie links deur 1 basies inserts dit hier aan die regterkant. Terug na hierdie, net onthou dat alles wat in die binêre is 'n krag van 2, sodat hierdie verteenwoordig 2 aan die 0, hierdie 2 tot 1, 2 aan die 2. Deur die invoeging van 'n 0 aan die regterkant nou, ons het net verskuif alles oor. Wat gebruik te word 2 tot die 0 is nou 2 tot die 1, 2 aan die 2. Die regterkant dat ons plaas is nie noodwendig gaan wees 0, wat sin maak. As jy al ooit 'n getal vermenigvuldig met 2, is dit nie gaan eindig vreemd, so die 2 aan die 0 plek moet wees 0, en dit is wat ek die helfte gewaarsku oor voor is as jy gebeur om te skuif buite die aantal bisse in 'n heelgetal, dan is hierdie 1 gaan aan die einde afgaan. Dit is die enigste bekommernis as jy gebeur om te word wat met baie groot vermoëns. Maar op daardie punt, dan is jy te doen het met 'n verskeidenheid van miljarde van dinge, wat dalk nie pas in elk geval in die geheue. 

Nou kan ons kry om te pop, wat is nog makliker. Jy kan dit doen graag as jy gebeur om 'n hele klomp te pop, en nou is jy weer teen die helfte van kapasiteit. Jy kan realloc die bedrag van die geheue wat jy hoef te krimp, maar jy hoef nie te bekommerd wees oor wat, so die enigste realloc geval gaan wees groeiende geheue, nooit krimp geheue, wat gaan pop super maklik te maak. Nou toue, wat gaan wees soos stapels, maar die bevel dat jy dinge uit is, word teruggeskryf. Die proto tipiese voorbeeld van 'n tou is 'n lyn, so ek dink as jy Engels was, sou ek gesê het 'n proto tipiese voorbeeld van 'n tou is 'n tou. Dus, net soos 'n lyn, as jy die eerste persoon in die lyn, jy verwag om die eerste persoon uit van die lyn wees. As jy die laaste persoon in lyn, gaan jy na die laaste persoon bedien word. Ons doen 'n beroep dat die EIEU-patroon, terwyl stapel was LIFO patroon. Daardie woorde is redelik universele. 

Soos stapels en in teenstelling met skikkings, toue tipies toelaat nie toegang tot die elemente in die middel. Hier, 'n stapel, het ons druk en pop. Hier, ons het gebeur met hulle geroep het enqueue en Dequeue. Ek het ook gehoor hulle genoem skuif en unshift. Ek het gehoor mense sê push en pop ook van toepassing op toue. Ek het gehoor voeg, te verwyder, so stoot en pop, as jy praat oor stapels, jy is besig en knal. As jy praat oor toue, kan jy kies die woorde wat jy wil om te gebruik vir inplasing en verwydering, en daar is geen konsensus oor wat dit moet genoem word. Maar hier, ons het enqueue en Dequeue. Nou, die struct lyk byna identies aan die stapel struct. Maar ons het om tred te hou van die kop. Ek dink dit sê hier, maar waarom moet ons die kop? Die prototipes is basies identies te stoot en pop. Jy kan dink dit as push en pop. Die enigste verskil is pop terugkeer in plaas van die verlede, is dit die terugkeer van die eerste. 2, 1, 3, 4, of iets. En hier is die begin. Ons ry is heeltemal vol is, so is daar vier elemente in dit. Die einde van die tou is tans 2, en nou is ons gaan om iets anders te voeg. 

As ons wil hê dat daar iets anders in te voeg, wat ons gedoen het vir die stapel weergawe is dat ons ons blok geheue uitgebrei. Wat is die probleem met hierdie? [Studente] Jy beweeg die 2. Wat ek vroeër gesê het oor die einde van die tou, dit maak nie sin dat ons begin op 1, dan wil ons Dequeue 1, dan Dequeue 3, dan Dequeue 4, dan Dequeue 2, dan Dequeue hierdie een. Ons kan nie realloc nou, of op die heel minste, moet jy om realloc in 'n ander manier te gebruik. Maar jy moet seker nie net gebruik realloc. Jy gaan aan die hand om jou geheue te kopieer. 

Daar is twee funksies om geheue te kopieer. Daar is memcopy en memmove. Ek is tans die lees van die man bladsye om te sien watter een jy gaan wil gebruik. Okay, memcopy, is die verskil dat memcopy en memmove, een hanteer die geval korrek waar jy kopieer in 'n streek wat gebeur om die streek te oorvleuel jy kopieer. Memcopy beteken dit nie hanteer nie. Memmove nie. Jy kan dink van die probleem as Kom ons sê ek wil hierdie man te kopieer, hierdie vier hierdie man oor. Op die ou end, wat die skikking moet lyk na die kopie is 2, 1, 2, 1, 3, 4, en dan 'n paar dinge aan die einde. Maar dit is afhanklik van die volgorde waarin ons eintlik kopieer, want as ons dink nie die feit dat die streek ons ​​kopiëring in oorvleuel die een wat ons die kopiëring van, dan kan ons doen soos die begin hier, kopieer die 2 in die plek wat ons wil om te gaan, dan beweeg ons wenke vorentoe. 

Nou gaan ons hier en hier te wees, en nou is ons wil kopieer hierdie man oor hierdie man en beweeg ons wenke vorentoe. Wat gaan ons uiteindelik kry, is 2, 1, 2, 1, 2, 1 in plaas van die toepaslike 2, 1, 2, 1, 3, 4 omdat 2, 1 overrode die oorspronklike 3, 4. Memmove hanteer dat korrek. In hierdie geval, basies net altyd gebruik memmove omdat dit hanteer dit korrek. Dit is oor die algemeen nie enige erger. Die idee is om in plaas van die begin van die begin af en kopiëring van hierdie manier soos ons net hier gedoen het, dit begin by die einde en kopieë in, en in daardie geval, kan jy nooit 'n probleem. Daar is geen prestasie verloor. Altyd gebruik memmove. Nooit bekommerd oor memcopy. En dit is waar jy gaan afsonderlik memmove die toegedraai rondom gedeelte van jou tou. Geen bekommernisse indien nie heeltemal gedoen. Dit is moeiliker as wat stapel, push, en pop. 

Enigiemand het 'n kode wat ons kan werk met? Selfs as heeltemal onvolledig? [Studente] Ja, dit is heeltemal onvolledig, though. Heeltemal onvolledig is goed so lank as wat ons kan jy slaan die hersiening? Ek vergeet dat elke enkele keer. Okay, ignoreer wat gebeur wanneer ons nodig het om dinge om te verander. Heeltemal ignoreer resize. Verduidelik hierdie kode. Ek is die eerste van alles nagaan indien die grootte is minder as die kopie eerste van alles en dan na daardie, plaas ek-ek neem kop + grootte, en ek maak seker dit vou om die kapasiteit van die skikking, en ek voeg die nuwe string in daardie posisie. Toe het ek die grootte verhoog en terugkeer ware. 

[Rob B.] Dit is beslis een van daardie gevalle waar jy gaan om te wil word deur gebruik te maak van mod. Enige soort geval waar jy het om te draai, as jy dink om te draai, die onmiddellike gedagte moet mod. As 'n vinnige optimalisering / maak jou kode een lyn korter, jy sien dat die lyn onmiddellik na hierdie een is net grootte + +, so jy voeg dat in hierdie lyn, grootte + +. Nou hier, ons het die saak waar ons het nie genoeg geheue, sodat ons ons vermoë te verhoog deur 2. Ek dink jy kan dieselfde probleem hier, maar ons kan dit nou ignoreer, waar as jy nie om jou kapasiteit te verhoog, dan is jy gaan om te wil jou vermoë om te verminder deur 2 weer. Nog 'n kort nota is net soos wat jy kan doen + =, jy kan dit ook doen << =. Byna enigiets kan gaan voor gelykes, + = | =, & = << = Char * nuut is, is ons nuwe blok geheue. O, hier. 

Wat dink mense nie oor die tipe van ons nuwe blok geheue? [Studente] Dit moet char **. Dink terug aan ons struct hier, snare is wat ons tot herverdeling binne. Ons maak 'n hele nuwe dinamiese stoor vir die elemente in die ry. Wat gaan ons die toeken aan jou snare is wat ons nou mallocing, en so 'n nuwe gaan 'n char **. Dit gaan om 'n verskeidenheid van snare. Wat is dan die saak waarop ons gaan om terug te keer vals? [Studente] Moet ons doen die char *? [Rob B.] Ja, goeie oproep. [Studente] Wat was dit? [Rob B.] Ons wou grootte van char * te doen, omdat ons nie meer dit sou eintlik 'n baie groot probleem, want sizeof (char) sou wees 1. Sizeof char * gaan wees 4, so 'n baie tye wanneer jy met ints, jy is geneig om weg te kom met dit omdat die grootte van int en grootte van int * op 'n 32-bis-stelsel gaan dieselfde ding. Maar hier, sizeof (char) en sizeof (char *) word nou gaan om dieselfde ding te wees. 

Wat is die omstandighede waar ons terugkeer vals? [Studente] New null. Ja, as nuwe null, keer ons terug vals is, en ek gaan om hier neer te gooi, [Studente] [onhoorbaar] [Rob B.] Ja, dit is goed. Jy kan óf 2 keer vermoë of kapasiteit verskuiwing 1 en dan sit dit net hier of wat ookal doen. Ons sal dit doen as ons het dit. Kapasiteit >> = 1. En jy gaan nooit hoef te bekommer oor die verloor van die 1 se plek want jy het verskuif deur 1, sodat die 1 se plek is noodwendig 'n 0, so reg skuif deur 1, jy nog steeds gaan piekfyn wees. [Studente] Doen wat jy nodig het om dit te doen voor die wederkoms? [Rob B.] Ja, dit maak absoluut geen sin nie. 

Nou neem ons gaan aan die einde terugkeer getrou tot die einde toe. Die manier waarop ons gaan hierdie memmoves te doen, ons nodig het om versigtig te wees met hoe ons dit doen. Is daar iemand enige voorstelle het vir hoe ons dit doen? Hier is ons begin. Onvermydelik, ons wil weer begin by die begin en 'n afskrif dinge van daar af, 1, 3, 4, 2. Hoe doen jy dit? Eerstens, ek het om te kyk na die man bladsy vir memmove weer. Memmove, volgorde van argumente is altyd belangrik. Ons wil ons bestemming, bron tweede, grootte 3. Daar is 'n baie van die funksies wat omkeer bron en bestemming. Bestemming, bron is geneig om konsekwent te wees ietwat. Beweeg, wat is dit terugkeer? Dit stuur 'n wyser na die bestemming, vir watter rede ookal jy dalk wil hê dat. Ek kan foto lees dit, maar ons wil om te skuif na ons bestemming. 

Wat is ons bestemming gaan word? [Studente] New. [Rob B.] Ja, en waar is ons kopiëring vanaf? Die eerste ding wat ons kopieer is dit 1, 3, 4. Wat is die hierdie 1, 3, 4. Wat is die adres van hierdie 1? Wat is die adres van daardie 1? [Studente] [onhoorbaar] [Rob B.] Hoof + die adres van die eerste element. Hoe kry ons die eerste element in die skikking? [Studente] Queue. [Rob B.] Ja, q.strings. Onthou, hier, ons kop is 1. Darn dit. Ek dink net dit is mettertyd Hier, ons kop is 1. Ek gaan my kleur te verander. En hier is strings. Hierdie, ons kan óf skryf dit soos ons gedoen het hier met die hoofde + q.strings. Baie mense skryf dit ook & q.strings [hoof]. Dit is nie regtig 'n minder doeltreffende. Jy mag dalk dink dat dit as jy ontwysing en dan om die adres van maar die vertaler gaan in elk geval dit te vertaal na wat ons gehad het voordat, q.strings + kop. Óf manier waarop jy wil om te dink van dit. 

En hoeveel bytes wil ons om te kopieer? [Studente] Kapasiteit - kop. Kapasiteit - kop. En dan kan jy altyd skryf 'n voorbeeld om uit te vind of dit is reg. [Studente] Dit moet gedeel deur 2 dan. Ja, so ek dink ons ​​grootte kan gebruik. Ons het nog steeds grootte- met behulp van grootte, ons het grootte gelyk aan 4. Ons grootte is 4. Ons hoof is 1. Ons wil hierdie 3 elemente te kopieer. Dit is die gesonde verstand is so dat die grootte - kop is korrek 3. En kom terug hier, soos ons vantevore gesê het, as ons kapasiteit, dan wil hê ons te verdeel deur 2 want ons het reeds ons kapasiteit gegroei het, so plaas, ons gaan om te gebruik. Dat afskrifte daardie gedeelte. Nou moet ons die ander gedeelte, die gedeelte wat oorgebly het van die begin af te kopieer. 

Dit gaan te memmove in watter posisie? [Studente] Plus grootte - kop. Ja, ons het reeds in grootte gekopieer - kop bytes, en so waar ons wil hê dat die oorblywende bytes te kopieer is 'n nuwe en dan grootte minus-goed, die aantal grepe wat ons reeds het gekopieer. En dan waar is ons kopiëring vanaf? [Studente] Q.strings [0]. [Rob B.] Ja, q.strings. Ons kan óf doen & q.strings [0]. Dit is aansienlik minder as dit. As dit net gaan om te wees 0, dan sal jy geneig te sien q.strings. Dit is waar ons kopiëring vanaf. Hoeveel bytes het ons verlaat het om te kopieer? >> [Studente] 10. Reg. [Studente] het ons 5 te vermenigvuldig 10 keer die grootte van die grepe of iets? Ja, so dit is waar wat ons presies te kopieer? [Studente] [onhoorbaar] Wat is die tipe van die ding wat ons die kopiëring van? [Studente] [onhoorbaar] Ja, so die char * s dat ons die kopiëring, ons weet nie waar daardie kom uit. Wel, waar hulle verwys na, soos die snare, het ons uiteindelik stoot dit op die tou of enqueuing op die tou. Waar dié vandaan kom, ons het nie 'n idee nie. Ons het net nodig om tred te hou van die char * s hulself. Ons wil nie die grootte te kopieer - kop bytes. Ons wil grootte te kopieer - kop char * s, so ons gaan om dit te vermeerder deur sizeof (char *). Dieselfde hier onder, kop * sizeof (char *). 

[Studente] Wat oor [onhoorbaar]? Hierdie reg hier? [Studente] Nee, hieronder wat die grootte - kop. [Rob B.] Hierdie reg hier? Pointer rekenkunde. Hoe wyser rekenkundige gaan om te werk, is dit vermeerder outomaties deur die grootte van die tipe wat ons te doen het met. Net soos hier, nuwe + (grootte - kop) is presies gelyk is aan en nuwe [grootte - kop] totdat ons verwag dat om korrek te werk, want as ons te doen het met 'n int skikking, dan het ons dit nie doen nie indeks deur int- of as dit is van die grootte van 5 en jy wil die 4de element, dan het ons indeks in die int array [4]. Jy moenie [4] * grootte van int. Dit hanteer dit outomaties, en hierdie geval is letterlik ekwivalente, sodat die bracket sintaksis is net omgeskakel gaan word om dit so gou as wat jy stel. Dit is iets wat jy nodig het om versigtig te wees van daardie wanneer jy grootte is toe te voeg - hoof jy voeg nie een byte. Jy is 'n char *, wat kan wees een bytes of wat ookal. 

Ander vrae? Okay, Dequeue gaan makliker wees. Ek gee jou 'n minuut om te implementeer. O ja, en ek dink dit is dieselfde situasie waar wat die enqueue geval, as ons enqueuing null, miskien ons wil om dit te hanteer, miskien kan ons dit nie doen nie. Ons sal dit nie doen dit weer hier, maar dieselfde as ons stapel geval. As ons enqueue null, sou ons wil om dit te ignoreer. Enigiemand het 'n paar kode wat ek kan trek? [Studente] Ek het net Dequeue. Weergawe 2 is dat-okay. Jy wil om te verduidelik? [Studente] Eerstens, jy maak seker daar is iets in die tou en dat die grootte is om af te gaan deur 1. Wat jy nodig het om te doen, en dan die kop terug en beweeg dan die kop up 1. Okay, so daar is 'n hoek geval wat ons het om te oorweeg. Ja. [Studente] As jou kop is op die laaste element, dan wil jy nie kop buite die skikking te wys. 

Ja, so tref so gou as hoof die einde van ons verskeidenheid, wanneer ons Dequeue ons hoof moet Gemodificeerde word terug na 0. Ongelukkig kan ons nie doen wat in een stap. Ek dink die manier wat ek sou waarskynlik dit regmaak is dit gaan om 'n char * wees, wat ons terugkeer, ongeag jou veranderlike naam wil wees. Dan wil ons kop deur ons vermoë om te mod en dan terug ret. 'N baie van die mense hier wat hulle kan doen dit is die geval van-you'll sien mense doen as hoof is groter as kapasiteit, doen kop - kapasiteit. En dit is net besig om wat mod is. Hoof mod = kapasiteit is veel skoner van 'n wikkel om as as hoof groter as kapasiteit kop - kapasiteit. 

Vrae? Okay, die laaste ding wat ons verlaat het, is ons geskakelde lys. Jy kan gebruik word om sommige van die geskakelde lys gedrag as jy gedoen het geskakelde lyste in jou hash tabelle, as jy het 'n hash tafel. Ek raai die doen van 'n hash tafel. Miskien het jy al gedoen het 'n Trie, maar drieë is meer moeilik. In teorie, dit is asimptoties beter. Maar net kyk na die groot raad, en probeer nooit beter doen, en hulle neem meer geheue. Alles probeer eindig erger vir meer werk. Dit is wat David Malan se oplossing is altyd is hy altyd posts sy Trie oplossing, en laat ons sien waar hy tans is. Wat was hy onder, David J? Hy is # 18, so dit is nie vreeslik sleg, en wat gaan wees een van die beste probeer jy kan dink of een van die beste drieë van 'n Trie. Is dit nie sy oorspronklike oplossing? Ek voel soos oor die oplossings is geneig om meer in hierdie reeks RAM gebruik. 

Gaan af na die heel boonste, en RAM gebruik is in die enkele syfers. Gaan af na die bodem, en dan sal jy begin sien probeer waar jy absoluut massiewe RAM gebruik, en drieë is meer moeilik. Nie heeltemal die moeite werd nie, maar 'n opvoedkundige ervaring as jy het een. Die laaste ding wat ons geskakelde lys, en hierdie drie dinge, stapels, toue, en geskakelde lyste, enige toekomstige ding wat jy ooit sal doen in rekenaarwetenskap sal aanneem dat jy vertroud is met hierdie dinge. Hulle is net so fundamenteel tot alles. 

Geskakelde lyste, en hier het ons 'n enkel geskakelde lys gaan om die implementering te wees. Wat beteken enkel gekoppel bedoel in teenstelling met dubbel gekoppel? Ja. [Studente] Dit wys net na die volgende wyser eerder as om die wysers, soos die een wat dit voorafgaan en die een na dit. Ja, so in foto-formaat, wat het ek net doen? Ek het twee dinge. Ek het foto en foto. In die foto-formaat, ons een-een geskakelde lyste, onvermydelik, ons het 'n soort van die wyser na die kop van ons lys, en dan in ons lys, ons moet net pointers, en miskien is dit punte aan nul. Dit gaan jou tipiese tekening van 'n enkel geskakelde lys. 'N dubbel geskakelde lys, kan jy agteruit te gaan. As ek gee jou 'n knoop in die lys, dan kan jy noodwendig kry om te enige ander nodus in die lys as dit is 'n dubbel geskakelde lys. Maar as ek kry jy die derde nodus in die lys en dit is 'n enkel geskakelde lys, geen manier wat jy ooit gaan kry om die eerste en tweede nodes. En daar is voordele en detriments, en 'n ooglopende een is jy meer grootte, en jy het om tred te hou van waar hierdie dinge is nou wys. Maar ons het net sorg oor enkel gekoppel. 

'N paar dinge wat ons gaan hê om te implementeer. Jou typedef struct node, int i: struct node * volgende; node. Dit typedef moet verbrand word in jou gedagtes. Quiz 1 wil gee 'n typedef van 'n geskakelde lys node, en jy moet in staat wees om onmiddellik af krabbel sonder om selfs te dink oor dit. Ek dink 'n paar vrae, hoekom het ons nodig struct hier? Waarom kan ons nie sê node *? [Studente] [onhoorbaar] Ja. Die enigste ding wat definieer 'n node as 'n ding is die typedef self. Maar op hierdie punt, wanneer ons soort van parsing deur hierdie struct node definisie, ons het nie klaar ons typedef nie, so sedert die typedef nie klaar nie, node bestaan ​​nie. Maar struct node doen, hierdie node en hier, dit kan ook genoem word enigiets anders. Dit kan genoem word. Dit kan genoem word geskakelde lys node. Dit kan genoem word enigiets. Maar dit struct node moet genoem word, dieselfde ding as hierdie struct node. Wat jy noem dit om ook hier te wees, en sodat ook die tweede punt van die vraag beantwoord wat is die rede waarom 'n baie tye wanneer jy sien structs en typedefs van structs, jy anonieme structs sien waar jy sal net sien typedef struct, implementering van struct, woordeboek, of wat ookal. 

Hoekom hier moet ons node om te sê? Hoekom kan dit nie 'n anonieme struct? Dit is byna dieselfde antwoord. [Studente] Jy nodig het om te verwys na dit in die struct. Ja, binne die struct, wat jy nodig het om te verwys na die struct self. As jy nie die struct 'n naam, indien dit is 'n anonieme struct, kan jy nie verwys na dit. En laaste maar nie die minste moet almal 'n bietjie simpel, en hulle moet help om te besef as jy skryf dit neer dat jy iets verkeerd doen as hierdie soort van dinge nie sin maak nie. Laaste maar nie die minste nie, waarom het dit te struct node *? Hoekom kan dit nie net struct word node volgende? [Studente] Pointer na die volgende struct. Dit is onvermydelik wat ons wil hê. Hoekom kan dit nooit wees struct node volgende? Hoekom het dit struct node * volgende wees? Ja. [Studente] Dit is soos 'n oneindige lus. Ja. [Studente] Dit sou alles in een. Ja, dink net hoe sou ons of grootte van iets doen. Grootte van 'n struct is basies + of - een of ander patroon hier of daar nie. Dit is basies gaan om die som van die groottes van die dinge wat in die struct. Hierdie reg hier, sonder om enigiets, is die grootte gaan maklik wees nie. Grootte van struct node gaan grootte van i + grootte van die volgende. Grootte van i gaan wees 4. Grootte van die volgende gaan wees 4. Grootte van struct node gaan wees 8. As ons nie die *, dink sizeof dan sizeof (i) gaan wees 4. Grootte van struct node volgende gaan grootte van i + grootte van struct node volgende + Grootte van i + grootte van struct node volgende. Dit sou 'n oneindige rekursie van nodes. Dit is waarom dit is hoe dinge moet wees. 

Weereens, memoriseer beslis dat, of ten minste verstaan ​​dit nie genoeg dat jy kan in staat wees om rede deur middel van wat dit behoort te lyk. Die dinge wat ons gaan om te wil om te implementeer. As die lengte van die lys- jy kan kul en hou om 'n globale lengte of iets, maar ons is nie van plan om dit te doen. Ons gaan die lengte van die lys te tel. Ons het bevat, so wat is basies soos 'n soektog, so ons het 'n geskakelde lys van heelgetalle om te sien of hierdie heelgetal is in die geskakelde lys. Plaas jou gaan aan die begin van die lys te voeg. Append gaan te voeg aan die einde. Insert_sorted gaan in die gesorteerde posisie in die lys te voeg. Insert_sorted soort van aanvaar dat jy nooit gebruik plaas jou of voeg in 'n slegte maniere. 

Insert_sorted wanneer jy die uitvoering van insert_sorted- laat ons sê ons het ons geskakelde lys. Dit is wat dit tans lyk, 2, 4, 5. Ek wil 3 te voeg, so lank as wat die lys self is reeds gesorteer, dit is maklik om te vind waar 3 behoort. Ek begin by 2. Okay, 3 is groter as 2 is, so ek wil om voort te gaan. O, 4 is te groot, so ek weet 3 gaan om in te gaan tussen 2 en 4, en ek het wysers en al daardie dinge op te los. Maar as ons het nie streng gebruik insert_sorted, graag laat ons net sê ek prefix 6, dan my geskakelde lys gaan om hierdie. Dit maak nou geen sin nie, so vir insert_sorted, jy moet net kan aanneem dat die lys is gesorteer, hoewel bedrywighede bestaan wat kan veroorsaak dat dit nie gesorteer word, en dit is dit. Vind 'n nuttige insert-so dit is die belangrikste dinge wat jy gaan hê om te implementeer. 

Vir nou, 'n minuut neem om lengte te doen en bevat en diegene moet wees relatief vinnig. Nader sluitingstyd, sodat almal iets vir lengte of bevat? Hulle gaan byna identies te wees. [Studente] Length. Kom ons kyk, hersiening. Okay. Jy wil om te verduidelik? [Studente] Ek het nou net 'n wyser node en inisialiseer eerste, wat ons globale veranderlike, en dan sal ek kyk om te sien of dit is null, sodat ek nie 'n seg skuld kry en terugkeer 0 indien dit die geval is. Anders, ek loop deur die dop van binne integer hoeveel keer het ek toegang tot die volgende element van die lys en ook in die dieselfde inkrement werking toegang tot dat die werklike element, en dan het ek voortdurend die check om te sien of dit is null, en as dit is null, dan is dit aborteer en net gee die aantal elemente wat ek verkry. 

[Rob B.] Is daar iemand enige kommentaar op enigiets? Dit lyk fyn korrektheid wys. [Studente] Ek dink nie jy moet die node == null. Ja, so indien node == null terugkeer 0. Maar as node == null dan is dit-oh, daar is 'n korrektheid kwessie. Dit was net jy i jy terugkeer, maar dit is nie nou in omvang. Jy hoef net int i, so i = 0. Maar as node, is van nul, dan het ek nog steeds gaan wees 0, en ons gaan 0 om terug te keer, sodat hierdie geval is identies. Nog 'n algemene ding is om die verklaring te hou van node binnekant van die loop. Jy kan sê oh, no. Kom ons hou dit soos hierdie. Ek sou waarskynlik int i = 0 sit hier, dan node * node = eerste hier. En dit is waarskynlik hoe om ontslae te raak van hierdie nou. Dit is waarskynlik hoe ek dit sou geskryf het. Jy kan ook kyk na dit soos hierdie. Dit vir lusstruktuur hier moet amper so natuurlik aan jou as vir int i = 0 ek is minder as die lengte van die skikking i + +. As dit is hoe jy oor 'n skikking itereer, dit is hoe jy oor 'n geskakelde lys itereer. 

Dit moet tweede natuur op 'n sekere punt. Met dit in gedagte, gaan dit byna dieselfde ding. Jy gaan wil itereer oor 'n geskakelde lys. As die node Ek het geen idee wat die waarde genoem word. Node i. Indien die waarde op daardie node = i terugkeer waar, en dit is dit. Let daarop dat die enigste manier waarop ons ooit return false is as ons itereer oor die hele geskakelde lys en nooit weer terugkom nie ware, so dit is wat dit doen. As 'n kant nota - ons sal waarskynlik nie by te voeg of die prefix. 

Vinnige laaste noot. As jy sien die statiese navraag, so kom ons sê static int tel = 0, dan doen ons reken + +, kan jy basies dink dit as 'n globale veranderlike, selfs al het ek net gesê dit is nie hoe ons hier gaan om lengte te implementeer. Ek doen dit hier, en dan tel + +. Enige manier wat ons kan 'n nodus in ons geskakelde lys ons is verhoog van ons reken. Die punt van hierdie wat die statiese navraag beteken. As ek moes net int tel = 0 nie wat jou sal 'n gereelde ou globale veranderlike wees. Wat static int telling beteken, is dat dit 'n globale veranderlike vir hierdie lêer. Dit is onmoontlik vir 'n ander lêer, dink van pset 5, as jy het begin. Jy beide speller.c en jy dictionary.c, en as jy net verklaar 'n ding globale, dan enigiets in speller.c kan verkry word in dictionary.c en vice versa. Globale veranderlikes is toeganklik deur 'n c-lêer. maar statiese veranderlikes is slegs toeganklik vanuit die lêer self, so binnekant van die speltoetser of binnekant van dictionary.c, dit is soort van hoe ek sou my veranderlike verklaar vir die grootte van my skikking of die grootte van my aantal woorde in die woordeboek. Aangesien ek nie wil hê dat 'n globale veranderlike te verklaar dat iemand toegang tot, Ek het regtig net omgee vir my eie doeleindes. 

Die goeie ding omtrent hierdie is ook die hele naam botsing stuff. As 'n ander lêer probeer om 'n globale veranderlike genoem telling te gebruik, dinge gaan baie, baie verkeerd, so dit hou mooi dinge veilig, en net jy dit kan oopmaak, en niemand anders kan, en as iemand anders verklaar 'n globale veranderlike genoem telling, dan sal dit nie inmeng met jou statiese veranderlike genoem reken. Dit is wat staties is. Dit is 'n lêer globale veranderlike. 

Vrae oor enigiets? Al stel. Bye. [CS50.TV]