[Powered by Google Translate] [Deel 6] [Meer Comfortabele] [Rob Bowden] [Harvard University] [Dit is CS50.] [CS50.TV] 

We kunnen terecht in onze rubriek vragen. Ik stuurde de URL voor de ruimte voor. Het begin van het gedeelte van de vragen zeg- blijkbaar ben ik niet helemaal unsick-is een zeer gemakkelijke vraag van precies wat valgrind? Wat doet valgrind doen? Wil iemand zeggen wat valgrind doet? [Student] Controles geheugenlekken. Ja, valgrind is een algemene geheugen checker. Het, op het einde, vertelt u als u een geheugen lekken, dat is meestal wat we met behulp van voor, want als je wilt doen het goed in het probleem set of als u wilt krijgen op het grote bord, moet je dan ook hebben geen geheugen lekken, en in het geval u een geheugenlek die u niet kunt vinden, ook rekening mee houden dat wanneer u een bestand opent en als je niet sluit, dat is een geheugenlek. 

Veel mensen zijn op zoek naar een aantal knooppunt dat ze niet bevrijden terwijl het in feite, hebben ze niet het woordenboek sluit in de eerste stap. Het vertelt je ook als u een ongeldige leest of schrijft, wat betekent dat als je probeert en stel een waarde dat is dan het einde van de hoop en het is niet toevallig seg fout maar valgrind vangt hem, als je niet zou eigenlijk daar moeten schrijven, en dus je moet zeker geen van die beide. Hoe gebruik je valgrind? Hoe gebruik je valgrind? 

Het is een algemene vraag van soort voer het uit en kijk naar de uitgang. De uitgang is overweldigend vele malen. Er is ook leuk fouten waar als je wat vreselijk verkeerde dingen gebeurt in een lus, dan zal uiteindelijk zeggen: "Veel te veel fouten. Ik ga stoppen met het tellen van nu. " Het is eigenlijk tekstuele output die je moet ontleden. Op het einde, zal het u vertellen welke geheugen lekken die je hebt, hoeveel blokken, die nuttig kan zijn omdat als het een blok unfreed, dan is het meestal gemakkelijker te vinden dan 1.000 blokken unfreed. 1.000 blokken unfreed betekent waarschijnlijk dat je niet bevrijden uw gekoppelde lijsten juiste of zoiets. Dat is valgrind. 

Nu hebben we onze rubriek vragen, die u niet nodig hebt om te downloaden. U kunt op mijn naam en trek ze omhoog in de ruimte. Klik nu op mij. Herziening 1 zal stack, die we eerst het doen zijn. Herziening 2 zal wachtrij, en Revision 3 zal de enkelvoudig gelinkte lijst te zijn. Te beginnen met onze stack. Zoals hier staat een stapel is een van de meest fundamentele, fundamentele datastructuren van de informatica. Het prototypische voorbeeld de stapel trays in de eetzaal. Het is eigenlijk wanneer je wordt voorgesteld aan een stapel, iemand zal zeggen: "O, als een stapel trays." Je stapelt de laden op. Dan wanneer je naar een lade te trekken, de eerste lade die is wordt getrokken is de laatste die werd gelegd op de stapel. De stapel ook-zoals hier staat- we hebben het segment van het geheugen genoemd stack. En waarom wordt het genoemd de stapel? 

Omdat als een stapel datastructuur, duwt en knalt stack frames op de stapel, waar stack frames zijn als een specifieke oproep van een functie. En net als een stapel, zul je altijd moeten terugkeren van een functie-aanroep voordat u weer naar beneden te krijgen in lagere stack frames. Je kunt niet de belangrijkste oproep foo oproep bar en bar terug te keren naar de belangrijkste direct. Het heeft altijd op de juiste stapel te duwen en popping volgen. De twee operaties, zoals ik al zei, zijn push en pop. Dat zijn universele termen. U moet weten push en pop in termen van stapels wat er ook gebeurt. We zullen zien wachtrijen zijn soort verschillend. Het heeft niet echt een universele term, maar push en pop zijn universeel voor stacks. Push is gewoon op de stapel gelegd. Pop is opstijgen de stapel. En we zien hier hebben we onze typedef struct stapel, dus we hebben char ** snaren. Laat je niet afschrikken door eventuele **. Dit gaat uiteindelijk op een een array van strings of een array van pointers naar tekens, waar verwijzingen naar tekens vaak strings. Het hoeft niet zo te zijn snaren, maar hier, ze zullen zijn strings. 

We hebben een array van strings. We hebben een grootte, wat neerkomt op hoeveel elementen zijn op dit moment op de stapel, en dan hebben we de capaciteit, die is hoeveel elementen kunnen op de stapel. De capaciteit moet beginnen als iets dat groter is dan 1, maar de grootte gaat beginnen als 0. Nu, zijn er in principe drie verschillende manieren waarop u kunt denken aan een stapel. Nou, er zijn waarschijnlijk meer, maar de twee belangrijkste manieren zijn u kunt uitvoeren met behulp van een array, of u kunt implementeren met behulp van een gekoppelde lijst. Gelinkte lijsten zijn soort triviale om stapels te maken van. Het is heel gemakkelijk om een ​​stapel met behulp van gelinkte lijsten, dus even, we gaan naar een stapel maken met behulp van arrays, en vervolgens met behulp van arrays, is er ook nog twee manieren waarop je kunt denken. Vroeger, toen ik zei dat we hebben een capaciteit voor de stapel, zodat we kunnen passen een element op de stapel. 

De enige manier waarop het kan gebeuren is, zodra je geraakt 10 elementen, dan ben je klaar. Je zou weten dat er een bovengrens van 10 dingen in de wereld dat je nooit meer dan 10 dingen op je stack, In dat geval kunt u een bovengrens voor de grootte van je stack. Of je zou kunnen hebben je stack worden onbegrensd, maar als je aan het doen bent een array, dat betekent dat elke keer dat u 10 elementen te raken, dan zul je moeten groeien tot 20 elementen, en wanneer je 20 elementen, je gaat te hebben om uw array groeien tot 30 elementen of 40 elementen. Je gaat nodig hebben om de capaciteit, dat is wat we gaan doen hier te verhogen. Elke keer als we bij de maximale grootte van onze stack, als we iets anders op te duwen, gaan we nodig hebben om de capaciteit te verhogen. We hebben hier aangegeven als push push bool (char * str). Char * str is de string die we duwen op de stack, en bool zegt alleen of we geslaagd of mislukt. 

Hoe kunnen we dat niet? Wat is de enige omstandigheid die je maar kunt bedenken waar we zouden moeten terugkeren vals? Ja. [Student] Als het vol is en we het gebruik van een begrensd implementatie. Ja, dus hoe definiëren we-antwoordde hij als het vol en we gebruiken een begrensde implementatie. Dan zullen we zeker terugkeren vals. Zodra we 10 dingen raken in de array, kunnen we niet 11 passen, dus we valse terugkeren. Wat als het is onbegrensd? Ja. Als je niet kan uitbreiden van de array voor een of andere reden. Ja, dus het geheugen is een beperkte hulpbron, en uiteindelijk, als we blijven pushen dingen op de stapel over en weer, we gaan proberen en toe te wijzen een groter scala aan te passen de grotere capaciteit, en malloc of wat we gebruiken gaat return false. Nou, malloc terug null. 

Vergeet niet, elke keer dat je belt malloc, moet je controleren om te zien of het null geretourneerd of anders, dat is een juistheid aftrek. Omdat we willen een onbegrensde stack te hebben, het enige geval gaan we om terug te keren vals is, als we proberen te de capaciteit en de malloc of wat dan ook false. Dan pop heeft geen argumenten, en retourneert de tekenreeks die op de bovenkant van de stapel. Wat is voor het laatst gedrukt op de stapel is wat pop keert terug, en het is ook verwijderd uit de stapel. En merken dat het null terugkeert als er niets op de stapel. Het is altijd mogelijk dat de stapel leeg is. Op Java, als je gewend bent aan die, of andere talen, proberen om pop uit een lege stack kan leiden tot een uitzondering of zoiets. 

Maar in C, null is een soort van een groot deel van de gevallen de manier waarop we deze problemen te behandelen. Terugkeren null is hoe we gaan om aan te geven dat de stapel leeg was. We hebben code in die je stack de functionaliteit van de proef, implementeren push en pop. Dit zal niet veel code. Ik zal-in feite, voordat we dat doen, hint, hint- als je nog niet gezien, malloc is niet de enige functie dat wijst geheugen op de heap voor u. Er zijn een familie van Alloc functies. De eerste is malloc, die u gewend bent. Dan is er calloc, die hetzelfde als malloc doet, maar het zal nul alles voor u uit. Als u ooit hebt willen alles ingesteld op null na mallocing iets moet je gewoon hebben gebruikt calloc in de eerste plaats in plaats van het schrijven van een lus op nul uit het hele blok van het geheugen. 

Realloc is als malloc en heeft veel bijzondere gevallen, maar eigenlijk wat realloc doet is het duurt een pointer die reeds waren toegewezen. Realloc is de functie die u wilt worden aandacht te besteden aan hier. Het duurt een pointer die reeds teruggekeerd van malloc. Laten we zeggen dat u een verzoek van malloc een pointer van 10 bytes. Later realiseer je je wilde 20 bytes, zo noem je realloc op die wijzer met 20 bytes, en realloc automatisch over te kopieren alles voor je. Als je gewoon de naam malloc weer, alsof ik een blok van 10 bytes. Nu moet ik een blok van 20 bytes, dus als ik malloc 20 bytes, dan moet ik handmatig te kopiëren over de 10 bytes van de eerste ding in de tweede ding en dan gratis het eerste wat. Realloc zal behandelen die bij u passen. 

Let op de handtekening gaat void * zijn, die net weer een pointer naar het geheugenblok, dan void * ptr. U kunt denken aan void * als een generieke pointer. Over het algemeen, je nooit omgaan met void *, maar malloc is het terugsturen van een void *, en dan is het gewoon gebruikt als Dit is eigenlijk gaat om een ​​char * zijn. De vorige void * die waren geretourneerd door malloc nu zal worden doorgegeven aan realloc, waarna vervolgens is het nieuwe aantal bytes dat u wilt toewijzen, zodat uw nieuwe capaciteit. Ik geef je een paar minuten, en doe het in onze ruimte. Begin met Herziening 1. Ik stop je na hopelijk over voldoende tijd om push uit te voeren, en dan geef ik je nog een pauze om pop te doen. Maar het is echt niet zo veel code op alle. De meeste code is waarschijnlijk de groeiende dingen, het uitbreiden van de capaciteit. Okay, geen druk volledig gebeuren, maar zo lang als je het gevoel alsof je op het juiste pad, dat is goed. 

Heeft iemand enig code ze zich comfortabel voelen bij mij omhoog te trekken? Ja, ik wil, maar heeft iemand nog een code kan ik optrekken? Oke, kunt u beginnen, sla het, wat het ook is? Ik vergeet altijd die stap. Oke, kijkend naar duwen, wilt u uw code uit te leggen? [Student] Allereerst, ik verhoogde de grootte. Ik denk dat misschien moet ik dat-hoe dan ook, ik steeg de omvang, en ik kijk of het is minder dan de capaciteit. En als het minder dan de capaciteit, voeg ik aan de array die we al hebben. En als het niet, ik vermenigvuldig de capaciteit met 2, en ik herverdelen de snaren array iets met een grotere capaciteit formaat nu. En als dat niet lukt, zeg ik tegen de gebruiker en return false, en als het is prima, dan heb ik de string in de nieuwe plek. 

[Rob B.] Merk ook op dat we een mooie logische bewerking die hier gebruikt te vermenigvuldigen met 2. Vergeet niet, is naar links verplaatsen altijd zal worden vermenigvuldigd met 2. Rechter shift wordt gedeeld door 2, zolang je niet vergeten dat het betekent delen door 2 als in een geheel getal gedeeld door 2. Het kan afkappen een 1 hier of daar. Maar shift links met 1 zal altijd worden vermenigvuldigd met 2, tenzij je overloop de grenzen van het gehele getal, en dan zal het niet zijn. Een kant commentaar. Ik graag doe-dit is niet van plan om te veranderen van de codering welke wijze dan ook, maar ik wil graag iets als dit te doen. Het is eigenlijk gaat om het iets langer. Misschien is dit niet de perfecte case om dit te laten zien, maar ik wil segment het in deze blokken- oke, als dit zo gebeurt, dan ga ik iets doen, en wordt de functie uitgevoerd. Ik hoef niet om te scrollen en mijn ogen helemaal naar beneden de functie om te zien wat er gebeurt na de ander. Het is als dit zo gebeurt, dan ga ik gewoon terug. Het heeft ook de mooie extra voordeel van alles voorbij deze wordt nu verschoven keer verliet. Ik niet meer nodig om, als je ooit in de buurt belachelijk lange lijnen, dan zijn die 4 bytes kunnen helpen, en ook de meer linkse iets is, hoe minder overweldigd jij je voelen als willen-oke, ik moet niet vergeten Ik ben momenteel in een while-lus binnenkant van een ander binnen van een for-lus. Overal kun je deze terugkeer onmiddellijk, ik een soort. Het is volledig optioneel en niet verwacht in een willekeurige manier. 

[Student] Moet er een grootte - in de fail conditie? De fail voorwaarde hier is dat we niet realloc, dus ja. Merk op hoe in de fail toestand, vermoedelijk, tenzij wij gratis spullen later, zijn we altijd ploft het maakt niet uit hoe vaak we proberen iets te duwen. Als we blijven pushen, houden we oplopende grootte, ook al zijn we niet zetten niets op de stapel. Meestal we de grootte niet verhoogd tot nadat we hebben met succes zet het op de stapel. Wij zouden het doen, laten we zeggen, hetzij hier en hier. En dan in plaats van te zeggen s.size ≤ capaciteit, het is minder dan de capaciteit, alleen omdat we verhuisd waar alles was. 

En vergeet niet, de enige plaats waar we zouden kunnen return false is hier, waar realloc terug null, en als je toevallig standaardfout herinneren, misschien kunt u overwegen dit een geval waar u een standaardfout af te drukken, dus fprintf stderr in plaats van alleen rechtstreeks afdrukken naar een standaard uit. Nogmaals, dat is niet een verwachting, maar als het een fout, typ printf, dan je zou willen om het af te drukken standaardfout in plaats van de standaard uit. 

Iedereen heeft iets anders op te merken? Ja. [Student] Kun je over de [onverstaanbaar]? [Rob B.] Ja, de werkelijke binariness ervan of gewoon wat het is? [Student] Dus u deze vermenigvuldigen met 2? [Rob B.] Ja, in principe. In binaire land, hebben we altijd onze set van cijfers. Shifting deze links op 1 principe voegt het hier aan de rechterkant. Terug naar deze, gewoon onthouden dat alles in binaire is een macht van 2, dus overeen met 2 een 0, dit 2 tot 1, deze 2 naar de 2. Door het plaatsen van een 0 aan de rechterkant nu, we verschuiven alles over. Wat vroeger 2 zijn de 0 is nu 2 tot 1 is 2 van de 2. Aan de rechterkant dat we door het invoeren noodzakelijkerwijs zal worden 0, wat logisch is. Als je ooit een aantal vermenigvuldigen met 2, het is niet van plan om uiteindelijk vreemd, dus de 2 naar de 0 plaats 0 moeten zijn, en dit is wat ik half gewaarschuwd voordat is als je toevallig om te wisselen wanneer het aantal bits in een integer, dan is dit een gaat uiteindelijk afgaan. Dat is de enige zorg als je toevallig te maken te hebben met echt grote capaciteiten. Maar op dat moment, dan heb je te maken hebt met een array van miljarden van de dingen, die misschien niet toch past in het geheugen. 

Nu we kunnen krijgen om pop, dat is nog makkelijker. Je zou kunnen doen het leuk vinden als je toevallig een hele hoop pop, en nu ben je op de helft van de capaciteit weer. Je kon realloc om de hoeveelheid geheugen je hebt krimpen, maar je geen zorgen te maken over dat is dus de enige realloc geval zal zijn groeiende geheugen, nooit krimpen geheugen, die gaat maken pop super eenvoudig. Nu wachtrijen, die de bus zou komen stapels, maar de volgorde waarin je dingen nemen wordt omgekeerd. De prototypische voorbeeld van een wachtrij is een lijn, dus ik denk dat als je Engels was, zou ik gezegd hebben een prototypisch voorbeeld van een wachtrij is een wachtrij. Dus als een lijn, als je de eerste persoon in de rij, je verwachten dat de eerste persoon uit de lijn. Als je de laatste persoon in de rij, ga je de laatste persoon worden onderhouden. Wij noemen dat FIFO patroon, terwijl stack was LIFO patroon. Die woorden zijn vrij universeel. 

Net als stapels en in tegenstelling tot arrays, wachtrijen meestal geen toegang tot elementen in het midden. Hier, een stapel, we hebben push en pop. Hier, we toevallig hen geroepen heb enqueue en dequeue. Ik heb ook gehoord ze noemde verschuiving en unshift. Ik heb mensen horen zeggen push en pop tot ook van toepassing op wachtrijen. Ik heb gehoord plaatst, verwijdert, dus duwen en pop, als je het over stapels, u bent duwen en popping. Als je het hebt over wachtrijen, kon je kiest de woorden die u wilt gebruiken voor het inbrengen en verwijderen, en er is geen consensus over wat moet worden genoemd. Maar hier hebben we enqueue en dequeue. Nu de struct ziet er bijna identiek aan de stack struct. Maar we moeten bijhouden van het hoofd. Ik denk dat er staat hier beneden, maar waarom hebben we nodig het hoofd? De prototypes zijn in principe identiek aan duwen en pop. U kunt denken aan het als push en pop. Het enige verschil is pop is terug te keren-in plaats van de laatste, het is weer de eerste. 2, 1, 3, 4, of zoiets. En hier is het begin. Onze wachtrij is helemaal vol, dus er is vier elementen erin. Het einde van onze rij op dit moment 2, en nu gaan we naar iets anders in te voegen. 

Als we willen dat er iets anders, wat we deden in te voegen voor de stapel-versie is hebben we ons blok van het geheugen. Wat is het probleem met dit? [Student] Je beweegt de 2. Wat ik al eerder zei over het einde van de wachtrij, dit betekent gevoel dat we beginnen niet bij 1, dan willen we dequeue 1, dan dequeue 3, dan dequeue 4, dan dequeue 2, dan dequeue deze. We kunnen nu niet gebruiken realloc, of althans, je realloc gebruiken op een andere manier. Maar je waarschijnlijk niet gewoon gebruik maken van realloc. Je gaat te hebben om handmatig te kopiëren uw geheugen. 

Er zijn twee functies te kopiëren. Er is memcopy en memmove. Ik ben momenteel het lezen van de man pagina's om te zien welke je gaat te willen gebruiken. Oke, memcopy, het verschil is dat memcopy en memmove, een zorgt voor de behuizing op de juiste waar u wilt kopiëren in een regio die toevallig overlappen de regio u van een. Memcopy niet mee omgaan. Memmove doet. U kunt denken aan het probleem- laten we zeggen dat ik wil deze man te kopiëren, deze vier van deze kerel. Op het einde van de array, wat moet eruit nadat de kopie is 2, 1, 2, 1, 3, 4, en dan nog wat dingen aan het eind. Maar dit is afhankelijk van de volgorde waarin we copieren, want als we geen rekening met het feit dat de regio we kopiëren naar overlapt degene die we kopieert, dan zouden we hier doen, zoals start, kopieert u de 2 in de plaats waar we willen gaan, dan vooruit onze pointers. 

Nu gaan we hier en hier te zijn, en nu willen we kopiëren deze man over deze man en verder te gaan onze pointers. Wat we gaan uiteindelijk krijgt is 2, 1, 2, 1, 2, 1 plaats van het geschikte 2, 1, 2, 1, 3, 4 omdat 2, 1 uitschakelde de oorspronkelijke 3, 4. Memmove handvatten die correct. In dit geval, eigenlijk gewoon altijd memmove omdat het verwerkt het goed. In het algemeen zijn geen enkele erger. Het idee is in plaats van vanaf het begin en kopiëren deze manier zoals we net gedaan hier, het begint bij het einde en kopieert in, en in dat geval, kun je nooit een probleem. Er is geen prestatie verlies. Gebruik altijd memmove. Nooit zorgen over memcopy. En dat is waar je naartoe gaat om te dienen apart memmove de omwikkelde gedeelte van uw wachtrij. Geen zorgen zo niet volledig gedaan. Dit is moeilijker dan stack, push en pop. 

Iemand enig code kunnen we samenwerken? Zelfs als geheel onvolledig? [Student] Ja, het is volkomen onvolledig, dat wel. Volledig onvolledig is prima, zolang we-kunt u de revisie? Ik vergeet dat elke keer weer. Oke, het negeren van wat er gebeurt als we nodig hebben om dingen te wijzigen. Volledig negeren resize. Leg uit deze code. Ik eerst controleren of het kleiner is dan het eerste exemplaar en dan na dat, ik steek-ik neem kop + grootte, en ik zorg ervoor dat wraps rond de capaciteit van de array, en ik plaats de nieuwe string op die positie. Daarna heb ik de grootte en de return true. 

[Rob B.] Dit is zeker een van die gevallen waar je naartoe gaat om te willen worden met behulp van mod. Elke vorm van geval waar u rond wikkelen, als je denkt dat rond wikkelen, de onmiddellijke gedachte zou moeten zijn mod. Als een snelle optimalisatie / uw code een regel korter, u merkt dat de lijn onmiddellijk deze na is gewoon formaat + +, zodat u samen te voegen dat in deze lijn, grootte + +. Nu hier beneden, hebben we de zaak waar we hebben niet genoeg geheugen, dus we zijn het vergroten van onze capaciteit door 2. Ik denk dat je zou kunnen hetzelfde probleem hier, maar we kunnen nu negeren, waar als u niet aan uw capaciteit te vergroten, dan zul je te willen uw capaciteit weer afnemen met 2. Nog een korte opmerking is net zoals je kunt doen + =, U kunt dit ook doen << =. Bijna alles kan gaan voordat gelijken, + =, | =, & =, << =. Char * nieuw is onze nieuwe blok van het geheugen. Oh, hier. 

Wat doen mensen denken over het type van onze nieuwe blok van het geheugen? [Student] Het moet char **. Terugdenkend aan onze struct hier, strings is wat we herverdelen. We maken een geheel nieuwe dynamische opslag voor de elementen in de rij. Wat we gaan worden toewijzen aan uw snaren is wat we nu mallocing, en zo nieuw gaat worden een char **. Het gaat om een ​​array van strings zijn. Wat is dan het geval is op grond waarvan we gaan om terug te keren vals? [Student] Moeten we moeten doen de char *? [Rob B.] Ja, goed gesprek. [Student] Wat was dat? [Rob B.] We wilden de grootte van de char * doen omdat we niet langer- Dit zou eigenlijk een heel groot probleem, omdat sizeof (char) zou zijn: 1. Sizeof char * gaat worden 4, dus veel momenten waarop je met ints, je de neiging om weg te komen met het omdat grootte van int en de grootte van int * op een 32-bits systeem zullen hetzelfde zijn. Maar hier, sizeof (char) en sizeof (char *) gaan nu hetzelfde zijn. 

Wat is de omstandigheid waar we return false? [Student] Nieuw is null. Ja, als nieuwe null is, keren we terug vals, en ik ga naar beneden te gooien hier- [Student] [onverstaanbaar] [Rob B.] Ja, dit is prima. Je kan ofwel doen 2 keer de capaciteit of de capaciteit shift 1 en dan nog alleen zette het neer hier of wat dan ook. We doen het zoals wij het hadden. Capaciteit >> = 1. En je zult nooit zorgen te maken over het verliezen van de 1 de plaats van omdat je links verschoven 1, dus de 1 de plaats is noodzakelijkerwijs een 0, zo goed verschuiven met 1, je bent nog steeds in orde. [Student] Hou je nodig hebt om dat te doen voordat u deze terugstuurt? [Rob B.] Ja, dit heeft absoluut geen zin. 

Nu neem aan dat we gaan eindigen weer trouw aan het einde. De manier waarop we gaan deze memmoves doen, moeten we voorzichtig zijn met de manier waarop we dat doen ze. Heeft iemand nog suggesties voor de manier waarop we dat doen ze? Hier is onze start. Onvermijdelijk, willen we opnieuw beginnen aan het begin en kopiëren dingen van daar, 1, 3, 4, 2. Hoe doe je dat? Ten eerste, ik moet naar de man pagina opnieuw zoeken memmove. Memmove, volgorde van argumenten is altijd belangrijk. We willen dat onze bestemming eerste, bron seconden, grootte derde. Er zijn een heleboel van de functies die de bron en de bestemming te keren. Bestemming, bron heeft de neiging om een ​​beetje consequent zijn. Move, wat is het weer? Het geeft een pointer naar bestemming, om welke reden dan je zou willen dat. Ik kan het plaatje lezen, maar we willen verhuizen naar onze bestemming. 

Wat is onze bestemming zal worden? [Student] Nieuwe. [Rob B.] Ja, en waar gaan we kopieert? Het eerste wat we kopieert is dit 1, 3, 4. Wat is de-this 1, 3, 4. Wat is het adres van deze 1? Wat is het adres van dat 1? [Student] [onverstaanbaar] [Rob B.] Head + het adres van het eerste element. Hoe krijgen we het eerste element in de array? [Student] Queue. [Rob B.] Ja, q.strings. Vergeet niet, hier, ons hoofd: 1. Verdorie. Ik denk dat het magisch- Hier ons hoofd 1. Ik ga mijn kleur te veranderen. En hier is strings. Dit kunnen we ofwel schrijf het uit als we deden hier met kop + q.strings. Veel mensen schrijven ook it & q.strings [hoofd]. Dit is niet echt een minder efficiënt. Je zou kunnen denken aan het als u dereferentie en dan krijgt het adres van, maar de compiler gaat om het te vertalen naar wat we hadden eerder toch, q.strings + hoofd. Hoe dan ook je wilt denken. 

En hoeveel bytes willen we kopiëren? [Student] Capaciteit - hoofd. Capaciteit - hoofd. En dan kun je altijd schrijven een voorbeeld om erachter te komen of dat klopt. [Student] Het moet worden gedeeld door 2 dan. Ja, dus ik denk dat we konden formaat te gebruiken. We hebben nog steeds grootte is- met behulp van grootte moeten we maaswijdte 4. Onze omvang is 4. Ons hoofd: 1. We willen deze 3 elementen te kopiëren. Dat is de geestelijke gezondheid te controleren die grootte - hoofd op de juiste 3. En hier terug te komen, zoals we al eerder zeiden, Als we de capaciteit, dan zouden we moeten delen door 2 want we hebben al uitgegroeid onze capaciteit, dus in plaats daarvan gaan we op maat te gebruiken. Dat kopieën dat gedeelte. Nu moeten we het andere deel, het deel dat overblijft van de start te kopiëren. 

Dat gaat memmove in welke positie? [Student] Plus size - hoofd. Ja, dus we hebben al gekopieerd in omvang - hoofd bytes, en dus waar we willen om de resterende bytes te kopiëren is nieuw en dan omvang min, nou ja, het aantal bytes dat we al gekopieerd inch En waar zijn we kopieert? [Student] Q.strings [0]. [Rob B.] Ja, q.strings. We kunnen dit doen & q.strings [0]. Dit is aanzienlijk minder vaak dan dit. Als het gaat gewoon op 0, dan zul je de neiging om q.strings zien. Dat is waar we het kopiëren van. Hoeveel bytes hebben we nog te kopiëren? >> [Student] 10. Juist. [Student] Moeten we 5 vermenigvuldigen - 10 keer de grootte van de bytes of zo? Ja, dus dit is waar-wat we precies te kopiëren? [Student] [onverstaanbaar] Wat is het type van het ding dat we kopiëren? [Student] [onverstaanbaar] Ja, dus de char * s dat we het kopiëren, weten we niet waar die vandaan komen. Nou, waar zijn ze te wijzen op, net als de strings, belanden we duwen op de wachtrij of enqueuing op de wachtrij. Wanneer deze vandaan komen, we hebben geen idee. We hoeven alleen maar om bij te houden van de char * s zelf. We willen niet op maat kopiëren - hoofd bytes. We willen op maat kopiëren - hoofd char * s, dus we gaan dit vermenigvuldigen met sizeof (char *). Zelfde hier beneden, hoofd * sizeof (char *). 

[Student] Hoe zit het met [onverstaanbaar]? Dit recht hier? [Student] Nee, daaronder, de grootte - hoofd. [Rob B.] Dit recht hier? Pointers. Hoe pointers gaat werken is Het vermenigvuldigt automatisch door de grootte van het type dat we te maken hebben met. Net als hier boven, nieuwe + (grootte - hoofd) is precies gelijk aan & nieuwe [size - hoofd] totdat we verwachten dat om volledig te kunnen functioneren, want als we te maken hebben met een int array, dan doen we niet indexeren door int- of als het van grootte van 5 en u wilt de 4e element, dan hebben we index in de int array [4]. Je Niet te [4] * grootte van de int. Dat regelt het automatisch, en dit geval letterlijk equivalent, zodat de beugel syntax is gewoon te worden omgezet naar deze zodra u samen te stellen. Dat is iets wat je moet voorzichtig zijn van die als je maat toe te voegen - het hoofd die u toevoegt niet een byte. Je het toevoegen van een char *, die kan als een bytes of wat dan ook. 

Andere vragen? Oke, dequeue gaat makkelijker. Ik geef je een minuut om te implementeren. Oh, en ik denk dat dit is dezelfde situatie waarin wat de enqueue geval, als we enqueuing null, Misschien willen we het te behandelen, misschien doen we niet. We zullen het nooit meer doen hier, maar hetzelfde als onze stapel geval. Als we Enqueue null, zouden we willen negeren. Iedereen heeft een aantal code die ik kan trekken? [Student] Ik heb alleen dequeue. Versie 2 is dat-oke. U wilt uitleggen? [Student] Eerst moet je ervoor zorgen dat er iets in de wachtrij en dat de grootte naar beneden gaat met 1. Je moet om dat te doen, en dan moet je terug de kop en verplaats dan de hoofd omhoog 1. Oke, dus er is een hoek het geval dat we moeten overwegen. Ja. [Student] Als je hoofd is op het laatste element, dan hoef je je niet wilt dat het hoofd te wijzen buiten de array. 

Ja, dus zodra het hoofd raakt het einde van ons aanbod, wanneer we dequeue, moeten ons hoofd worden modded terug naar 0. Helaas kunnen we dat niet doen in een stap. Ik denk dat de manier waarop ik zou waarschijnlijk fix it is dit gaat om een ​​char * zijn, wat we terug te keren, ongeacht uw variabele wil zijn. Dan willen we het hoofd van onze capaciteit mod en dan terug ret. Veel mensen hier zijn ze zouden kunnen doen- dit is het geval van-je zult zien dat mensen doen als hoofd groter is dan de capaciteit, doe hoofd - capaciteit. En dat is gewoon aan het werk rond wat mod is. Hoofd mod = capaciteit is veel schoner van een omhulsel rond dan wanneer het hoofd groter is dan de capaciteit hoofd - capaciteit. 

Vragen? Oke, het laatste wat we hebben is onze gelinkte lijst. Je zou kunnen worden gebruikt om een ​​deel van de gekoppelde lijst gedrag als je dat deed gelinkte lijsten in uw hash tabellen, als je dat deed een hash table. Ik raden het doen van een hash-tabel. Je zou al hebben gedaan een trie, maar probeert zijn moeilijker. In theorie zijn ze asymptotisch beter. Maar kijk eens naar het grote bord, en probeert nooit beter doen, en ze nemen meer geheugen. Alles probeert over eindigt als slechter voor meer werk. Het is wat David Malan's oplossing altijd is hij altijd zijn trie oplossing posten, en laten we zien waar hij op dit moment is. Wat was hij onder, David J? Hij is # 18, dus dat is niet vreselijk slecht, en dat gaat als een van de beste probeert u maar kunt bedenken of een van de best probeert een trie. Is het niet eens zijn oorspronkelijke oplossing? Ik voel me als trie solutions hebben de neiging om meer in deze reeks van RAM gebruik. 

Ga naar beneden naar de top, en RAM gebruik is in de enkele cijfers. Ga naar beneden naar de onderkant, en dan moet je beginnen met het zien probeert waar je absoluut enorme RAM-gebruik te krijgen, en pogingen zijn moeilijker. Niet helemaal de moeite waard, maar een leerzame ervaring als je dat deed een. Het laatste wat is onze gelinkte lijst, en deze drie dingen, stapels, wachtrijen en gelinkte lijsten, eventuele toekomstige wat je ooit doen in de informatica zullen veronderstellen dat u vertrouwd zijn met deze dingen. Ze zijn gewoon zo fundamenteel voor alles. 

Gelinkte lijsten, en hier hebben we een enkelvoudig gelinkte lijst gaat onze implementatie. Wat betekent afzonderlijk verbonden betekenen ten opzichte van dubbel gelinkte? Ja. [Student] Het verwijst uitsluitend naar het volgende pointer niet aan de pointers, als dat van de vorige en die na. Ja, dus in beeldformaat, heb wat ik doe? Ik heb twee dingen. Ik heb beeld en beeld. In beeldformaat, onze afzonderlijk gelinkte lijsten, onvermijdelijk, we hebben een soort van pointer naar het hoofd van onze lijst, en vervolgens binnen onze lijst, we hoeven alleen maar pointers, en misschien wijst dit op null. Het zal uw typische tekening van een enkelvoudig gelinkte lijst te zijn. Een dubbel gelinkte lijst, kunt u achteruit gaan. Als ik u een knooppunt in de lijst, dan kunt u altijd naar welk ander knooppunt in de lijst als het een dubbel gebonden lijst. Maar als ik je de derde knooppunt in de lijst en het is een afzonderlijk gekoppeld lijst, op geen enkele manier die je ooit zult krijgen om de eerste en tweede knooppunten. En er is voor-en nadelen, en een voor de hand liggende wordt u nemen meer grootte, en je moet bijhouden waar deze dingen zijn nu wijzen. Maar we alleen de zorg over afzonderlijk met elkaar verbonden. 

Een paar dingen die we gaan moeten implementeren. Uw typedef struct knoop, int i: struct knoop * volgende; node. Dat typedef moet worden verbrand in jullie geest. Quiz 1 moet worden willen geven een typedef van een gekoppelde lijst knooppunt, en je moet in staat zijn om onmiddellijk krabbelen dat neer zonder erover na te denken. Ik denk dat een paar vragen, waarom moeten we struct hier? Waarom kunnen we niet zeggen knooppunt *? [Student] [onverstaanbaar] Ja. Het enige dat een knooppunt definieert als een ding de typedef zelf. Maar vanaf dit punt, als we soort van parsing door middel van deze struct knoop definitie, we zijn nog niet klaar onze typedef nog, daar de typedef niet is voltooid, knooppunt bestaat niet. Maar struct knoop doet, dit knooppunt en hier, dit kan ook worden opgeroepen iets anders. Dit kan worden genoemd n. Het kan worden genoemd gelinkte lijst node. Het kan worden genoemd niets. Maar deze struct knoop moet worden aangeroepen hetzelfde als deze struct node. Wat noem je dit moet ook hier te zijn, en zo dat beantwoordt ook het tweede punt van de vraag dat is waarom-veel momenten waarop je structs en typedefs van structs te zien, zie je anoniem structs waar je gewoon zien typedef struct, uitvoering van struct, woordenboek, of wat dan ook. 

Waarom hier moeten we knooppunt zeggen? Waarom kan het niet een anoniem struct? Het is bijna hetzelfde antwoord. [Student] Je moet om het te verwijzen in de struct. Ja, binnen de struct, moet u verwijzen naar de struct zelf. Als u niet geven de struct een naam, als het een anonieme struct, kunt u niet verwijzen naar het. En last but not least-deze moeten allemaal een beetje simpel, en ze moeten helpen je je realiseert dat als je het schrijven van dit neer dat je doet iets mis als dit soort dingen niet zinvol. Last but not least, waarom dit te struct knoop * zijn? Waarom kan het niet gewoon worden struct knoop nu? [Student] Pointer naar de volgende struct. Dat is onvermijdelijk wat we willen. Waarom kon het nooit struct knoop volgende? Waarom moet het naar struct knoop * volgende zijn? Ja. [Student] Het is als een oneindige lus. Ja. [Student] Het zou allemaal in een. Ja, denk maar aan de manier waarop we zouden omvang van of iets te doen. Grootte van een struct is eigenlijk + of - enkele patroon hier of daar. Het is eigenlijk gaat om de som van de afmetingen van de dingen in de struct zijn. Dit hier, zonder iets te veranderen, wordt het formaat makkelijk zal zijn. Grootte van struct knoop gaat om de grootte van i + grootte van de volgende zijn. Grootte van i zal worden 4. Grootte van het volgende gaat worden 4. Grootte van struct knoop gaat worden 8. Als we niet over de *, denkend aan sizeof, Vervolgens sizeof (i) zal worden 4. Grootte van struct knoop ligt naast gaan grootte van i be + grootte van struct knoop volgende + Grootte van i + grootte van de struct knoop volgende. Het zou een oneindige herhaling van knooppunten. Dit is de reden waarom dit is hoe dingen moeten. 

Nogmaals, zeker onthouden dat, of in ieder geval genoeg te begrijpen dat je kunt in staat zijn om reden door wat eruit moet zien. De dingen die we gaan willen implementeren. Als lengte van de lijst- je zou kunnen bedriegen en te houden rond een globale lengte of iets, maar we gaan niet om dat te doen. We gaan om de lengte van de lijst tellen. We hebben bevat, dus dat is in principe net als een zoekopdracht, We hebben dus een gekoppelde lijst van integers te zien of dit integer is in de gekoppelde lijst. Prepend gaat voegen aan het begin van de lijst. Append gaat Aan het eind. Insert_sorted gaat voegen in de gesorteerde positie in de lijst. Insert_sorted soort gaat ervan uit dat je nooit prepend gebruikt of voegen in slechte manieren. 

Insert_sorted als je de uitvoering insert_sorted- laten we zeggen dat we onze verbonden lijst. Dit is wat het moment lijkt, 2, 4, 5. Ik wil tot en met 3 invoegen, dus zolang de lijst zelf al gesorteerd is, het is gemakkelijk te vinden waar 3 behoort. Ik begin bij 2. Oke, 3 groter is dan 2, dus ik wil om door te gaan. Oh, 4 is te groot, dus ik weet 3 zal in gaan tussen 2 en 4, en ik moet pointers en al dat spul op te lossen. Maar als we niet strikt te gebruiken insert_sorted, graag laten we gewoon zeggen dat ik vooraf gaan 6, dan is mijn gelinkte lijst gaat worden dit. Het maakt nu geen zin, dus voor insert_sorted, u kunt gewoon aannemen dat de lijst is gesorteerd, ook al operaties bestaan die kan leiden tot het niet worden gesorteerd, en dat is het. Zoek een nuttig insert-zo dat zijn de belangrijkste dingen die je gaat te hebben om uit te voeren. 

Voor nu, neem een ​​minuut de tijd om lengte te doen en bevat, en die moet betrekkelijk snel. Bijna sluitingstijd, zodat iedereen iets voor lengte of bevat? Ze gaan vrijwel identiek. [Student] Lengte. Laten we eens kijken, revisie. Oke. U wilt uitleggen? [Student] Ik maak een pointer knooppunt en het eerst, dat is onze globale variabele te initialiseren, en dan moet ik controleren om te zien of het null, dus ik krijg geen seg fout en terug te keren 0 als dat het geval is. Anders, ik loop door, het bijhouden van binnen geheel getal hoe vaak heb ik toegang tot het volgende element van de lijst en in hetzelfde increment operatie ook toegang krijgen tot dat de werkelijke element, en dan heb ik continu maken van de controle om te zien of het null, en als het null, dan is afgebroken en alleen geeft het aantal elementen die ik heb gebruikt. 

[Rob B.] Heeft iemand enig commentaar op alles? Dit ziet er verstandig prima correctheid. [Student] Ik denk niet dat je nodig hebt het knooppunt == null. Ja, dus als knooppunt == null return 0. Maar als knooppunt == null dan is dit-o, er is een juistheid kwestie. Het was gewoon dat je i terug te keren, maar het is niet in omvang op dit moment. Je hoeft alleen maar int i, dus i = 0. Maar als knooppunt null is, dan moet ik gaat nog steeds op 0, en we gaan naar 0 terug, dus dit geval identiek is. Een andere veel voorkomende ding is om de verklaring van knooppunt binnenkant van de for-lus. Je zou kunnen zeggen-oh, nee. Laten we het als dit. Ik zou waarschijnlijk zet int i = 0 hier, Vervolgens knoop * knooppunt = eerste hier. En dit is waarschijnlijk hoe-om nu ontdoen van deze. Dit is waarschijnlijk hoe ik zou hebben geschreven. U kunt ook-naar te kijken als deze. Dit voor lusstructuur hier moet bijna zo natuurlijk aan u als voor int i = 0 i kleiner is dan de lengte van de array i + +. Als dat is hoe je itereren over een array, dit is hoe je itereren over een gekoppelde lijst. 

Dit moet een tweede natuur op een bepaald punt te zijn. Met dat in gedachten, gaat dit bijna hetzelfde zijn. Je gaat te willen itereren over een gelinkte lijst. Als de node-Ik heb geen idee wat de waarde wordt genoemd. Knooppunt i. Als de waarde op dat knooppunt = i return true, en dat is het. Merk op dat de enige manier waarop we ooit terug te keren vals is als we itereren over de gehele gekoppelde lijst en nooit meer terug waar, Dus dat is wat dit doet. Als een kanttekening, we waarschijnlijk niet toe te voegen of vooraf gaan. 

Quick laatste noot. Als u het sleutelwoord static, dus laten we zeggen static int count = 0, dan doen we tellen + +, kun je in principe het beste gezien worden als een globale variabele, ook al heb ik net gezegd dit is niet hoe we gaan op lengte te implementeren. Ik doe dit hier, en dan tel + +. Elke manier kunnen we een knoop in te voeren in onze gelinkte lijst zijn we verhogen ons tellen. Het punt van dit is wat het sleutelwoord static betekent. Als ik gewoon int count had = 0 dan zou het een oude globale variabele te zijn. Wat static int count betekent is dat het gaat om een ​​globale variabele voor dit bestand. Het is onmogelijk een ander bestand, graag denken van PSET 5, als u zijn begonnen. U heeft zowel speller.c, en je hebt dictionary.c, en als je gewoon declareren een ding wereldwijde, dan is alles in speller.c kan worden geraadpleegd in dictionary.c en vice versa. Globale variabelen zijn toegankelijk door een. C bestand, maar statische variabelen zijn alleen toegankelijk vanuit het bestand zelf, dus de binnenkant van spellingcontrole of binnenkant van dictionary.c, Dit is een soort van hoe ik zou mijn variabele te declareren voor de grootte van mijn array of de grootte van mijn aantal woorden in het woordenboek. Aangezien ik niet wil een globale variabele te verklaren dat iedereen toegang heeft tot Ik heb echt alleen de zorg over het voor mijn eigen doeleinden. 

Het goede ding over dit is ook de hele naam botsing spul. Als een ander bestand probeert te gebruiken een globale variabele genaamd tellen, gaat het heel erg mis, dus dit houdt mooi dingen veilig, en alleen u toegang hebt tot, en niemand anders kan, en als iemand anders verklaart een globale variabele genaamd tellen, dan zal het niet interfereren met uw statische variabele genaamd tellen. Dat is wat statisch is. Het is een bestand globale variabele. 

Vragen over iets? Alle set. Bye. [CS50.TV]