[Powered by Google Translate] [Week 6] [David J. Malan] [Harvard University] [Dit is CS50.] [CS50.TV] 

Dit is CS50, en dit is het begin van week 6 dus een paar nieuwe tools zijn nu beschikbaar voor u om te profiteren van, waarvan de eerste wordt genoemd CS50 stijl. Odds zijn als je net als ik of een van de leer fellows, je hebt waarschijnlijk gezien een programma waarvan de stijl ziet er een beetje iets als dit. Misschien heb je begint te zagen sommige hoeken 's avonds laat, of je later mee omgaan, en dan een TF of CA komt over tijdens de kantooruren. Dan is het moeilijk voor ons om te lezen. Nou, deze code is syntactisch correct, en het compileren wordt, en het ook daadwerkelijk uit te voeren. Maar het is zeker geen 5 voor stijl. 

Maar nu, als we naar deze map hier- en merk dat ik conditions2.c-have en ik run deze nieuwe opdracht, style50, op dit bestand conditions2.c, Enter, merken dat het is me op de hoogte dat het gestileerde geweest. Gedit merkte dat het bestand is gewijzigd op de schijf, en als ik klik op laden, zijn al je problemen nu geautomatiseerd. [Applaus] Dat is een van de dingen die we deden dit weekend. Realiseer je dat het onvolmaakt is, want er zijn een aantal code dat het gewoon niet in staat zijn om perfect te stileren, realiseren, maar dit is nu een tool die u kunt profiteren van al was het maar op te ruimen een aantal van de meer moedwillig een verkeerde geplaatste accolades en dergelijke. 

Maar meer dwingende is nu CS50 Check. Met CS50 Check, kun je eigenlijk het uitvoeren van dezelfde juistheid testen op uw eigen code die de leer fellows kunnen. Dit is een command line utility dat nu komt in het apparaat zodra u een update50 per doen PSET 4 specificaties, en je gebruikt het in wezen als dit. U voert de opdracht check50. Dan passeert u op een opdrachtregel argument, of meer algemeen bekend als een schakelaar of een vlag. Over het algemeen zijn dingen die koppeltekens hebben wel een schakelaar om een ​​command line programma, dus-c geeft aan de controles die u wilt uitvoeren. 

De tests die u wilt uitvoeren worden geïdentificeerd uniek door deze string, 2012/pset4/resize. Met andere woorden, dat is gewoon een willekeurige, maar unieke string die we gebruiken om uniek te identificeren PSET 4's juistheid tests. En dan geeft u een spatie gescheiden lijst van de bestanden die u wilt uploaden om CS50 Controleer voor analyse. Bijvoorbeeld, als ik in mijn oplossing hier voor resize.c- Laat me open te stellen een grotere terminal venster- en ik ga je gang en lopen laten we zeggen check50-c 2012/pset4/resize, en dan ga ik ga je gang en geef de namen van de bestanden, resize.c, en druk dan op Enter, het comprimeert, Het uploads, controleert, en ik net niet een hele hoop tests. De een op de rode linksboven zegt dat er resize.c en bmp. Dat was de test. Dat was de vraag die we stelden. En het is ongelukkig omdat het antwoord was vals. De witte tekst eronder staat naar verwachting bmp.h te bestaan, en dat is gewoon mijn schuld. Ik ben vergeten om het te uploaden, dus ik moet beide bestanden te uploaden, resize.c en bmp.h. Maar let nu op alle andere tests zijn in het geel, omdat ze nog niet hebt uitgevoerd, en zo de smiley verticaal is, want hij is noch tevreden, noch verdrietig, maar we moeten deze kwestie verhaal in het rood voor die andere controles worden uitgevoerd. 

Laat mij dit oplossen. Laat me uit te zoomen en herstart deze, dit keer met bmp.h ook op de opdrachtregel, Enter, en nu als alles goed gaat, het gaat om te controleren en dan terug naar aanleiding van-je adem- alle groene, wat betekent dat ik ben echt goed op PSET 4 tot nu toe. U kunt zien en afleiden uit de beschrijvende tekst hier precies wat het is die we hebben getest. We testten eerst de bestanden bestaan ​​er? Vervolgens hebben we getest doet resize.c compileren? Dan hebben we getest is het niet de grootte van een 1x1-pixel BMP als n, het formaat wijzigen factor, is 1. Nu, als je geen idee wat n is, zult u zodra u een duik nemen in PSET 4, maar dat is gewoon een controle op een gezond verstand om ervoor te zorgen dat je niet resizen een beeld helemaal als het formaat wijzigen factor is 1. Indien daarentegen het formaat van een 1x1 pixel een 1x1 pixel BMP kunnen tot 2x2 wanneer n 2 dan evenzo mine vormt dan. 

Kortom, dit is bedoeld om, een, neem de oversteken van de vingers uit de vergelijking vlak voordat u uw PSET. U weet precies wat uw TF binnenkort zal weten als je gaat over het indienen van een aantal van deze problemen sets, en ook de pedagogische motivatie is echt te maken aan de mogelijkheid voor u, zodat wanneer u bij voorbaat weet dat er bugs in de code en tests die nog niet worden doorgegeven, u kunt in meer effectieve tijd van te voren om die problemen op te lossen in plaats van verliest punten, feedback te krijgen van uw TF, en ga dan, "Ahh," alsof ik zou hebben bedacht dat uit. Nu in ieder geval is er een hulpmiddel om u te helpen dat. Het gaat niet om erop te wijzen waar de bug is, maar het zal u vertellen wat is symptomatisch voor het. 

Nu beseffen de tests zijn niet noodzakelijkerwijs volledig. Alleen maar omdat je op een scherm vol met groene smiley gezichten betekent niet dat uw code is perfect, maar het betekent wel dat het voorbij is bepaalde tests voorgeschreven door de spec. Soms zullen we niet vrijgeven controles. Bijvoorbeeld whodunit een van de aspecten van PSET 4, is een beetje teleurstellend als we geven u de antwoord op de vraag wat het is, en er is een aantal manieren om te onthullen wie de persoon is in die rode ruis. De spec zal altijd aangeven in de toekomst voor PSET 5 verder welke controles er voor u. U zult merken dat er dit witte URL aan de onderkant. Voor nu, dit is gewoon diagnose-uitgang. Als u een bezoek dat URL, krijg je een hele hoop gekke, cryptische berichten dat u bent van harte welkom om te kijken door, maar het is vooral voor het personeel zodat wij kunnen diagnosticeren en debuggen bugs in check50 zelf. 

Zonder omhaal, laten we verder gaan waar we gebleven waren. CS50 bibliotheek namen we voor lief voor enkele weken, maar dan vorige week, zijn we begonnen met peeling terug een van de lagen van het. We zijn begonnen met terzijdestelling reeks ten gunste van wat in plaats daarvan? [Studenten] Char. Char *, dat is een char * al die tijd, maar nu hebben we niet te doen alsof dat het een feitelijke gegevenstype string. Integendeel, het is een synoniem van soorten voor char *, en een string is een reeks tekens, dus waarom heeft het zin om strings te vertegenwoordigen als char * s? Wat doet een char * vertegenwoordigen in het kader van dit concept van een string? Ja. >> [Student] Het eerste teken. Goed, het eerste teken, maar niet helemaal het eerste teken. Het is de-[Studenten] Adres. Good, het adres van het eerste teken. Alles wat nodig is om een ​​string te vertegenwoordigen in het geheugen van een computer ligt het unieke adres van de eerste byte. Je hoeft niet eens te weten hoe lang het is want hoe kun je erachter dat uit dynamisch? [Student] String lengte. U kunt bellen tekstlengte, uitstekend, maar hoe werkt string lengte werk? Wat doet het? Ja. [Student] Blijf doorgaan totdat je de nul karakter. Ja, precies, het herhaalt enkel met een for-lus, while-lus, wat van * tot het einde, en het einde is vertegenwoordigd door \ 0, de zogenaamde nul karakter, nul, niet te verwarren met null, een pointer, die zal wederkomen in gesprek vandaag. 

We geschild terug een laagje GetInt, en toen namen we een kijkje op GetString, en herinneren eraan dat deze beide functies, of eigenlijk, GetString, was het gebruik van een bepaalde functie om daadwerkelijk ontleden, is dat, te lezen of te analyseren, invoer van de gebruiker. En wat was dat nieuwe functie? Scanf of sscanf. Het komt eigenlijk in een paar verschillende smaken. Er is scanf, er is sscanf, is er fscanf. Voorlopig echter, laten we focussen op het meest simpele illustratie, en laat mij door te gaan en open te stellen in het apparaat een bestand als dit, scanf1.c. Dit is een super eenvoudig programma, maar dat doet iets dat we nooit hebben gedaan zonder de hulp van de CS50 bibliotheek. Dit wordt een int van een gebruiker. Hoe werkt het? Nou, in lijn 16 daar, merken dat we een int genaamd x verklaren, en op dit punt in het verhaal, wat is de waarde van x? [Onverstaanbaar student reactie] [David M.] Rechts, wie weet, wat vuilnis waarde potentieel, dus in 17, we vertellen de gebruiker geef me een nummer, neem dan, en stap 18 is waar het interessant wordt. Scanf lijkt te lenen een idee van printf in zoverre dat het deze indeling codes gebruikt tussen aanhalingstekens. % D is natuurlijk een decimaal getal. Maar waarom ben ik passeren in en x in plaats van alleen x? De eerste is correct. Ja. [Onverstaanbaar student reactie] Precies, als het doel van dit programma, zoals de functie GetInt zelf, wordt naar een int te krijgen van de gebruiker Ik kan passeren functies alle variabelen ik wil, maar als ik het niet door te geven aan de hand of op adres of pointer, alle synoniem voor doeleinden van vandaag, dan die functie heeft geen mogelijkheid om de inhoud van die variabele. Dit zou pas in een exemplaar, net als de buggy versie van swap dat we hebben gesproken over een paar keer. 

Maar in plaats daarvan, door het doen van & x, ik ben letterlijk voorbij in wat? [Student] Het adres. >> Het adres van x. Het is als het tekenen van een kaart voor de functie genaamd scanf en zeggen hier, dit zijn aanwijzingen om een ​​stuk van het geheugen in de computer dat u kunt gaan slaan een geheel getal in Om sscanf te doen nu wat operator, is wat stuk syntaxis gaat het om het gebruik van ook al kunnen we het niet zien omdat iemand anders schreef deze functie? Met andere woorden - wat is dat? [Student] X te lezen. Er gaat wat te lezen, maar alleen met betrekking tot x hier. Als scanf wordt doorgegeven het adres van x, syntactisch, is wat operator gebonden aan ergens bestaan binnenkant van de uitvoering scanf's, zodat scanf kan een nummer 2 eigenlijk schrijven naar dat adres? Ja, dus de *. Bedenk dat het * is onze dereference operator, die in wezen betekent dat er heen gaan. 

Als je eenmaal hebt ingeleverd een adres, zoals hier het geval is, scanf is waarschijnlijk, als we echt keek om zich heen de broncode- doet * x of het equivalent om daadwerkelijk te gaan naar dat adres en plaats daar enige waarde. Nu, als voor de manier waarop scanf inbreng krijgt van het toetsenbord, we zwaaien onze handen uit voor vandaag. Gewoon aannemen dat het besturingssysteem maakt het mogelijk sscanf om te praten de gebruiker het toetsenbord, maar op dit punt nu in lijn 19, als we gewoon afdrukken x lijkt het geval dat scanf heeft een int in x. Dat is precies hoe scanf werkt, en herinneren van vorige week dat is precies hoe GetString en GetInt en de andere familie van functies uiteindelijk werkt, zij het met een lichte variatie zoals sscanf, wat betekent dat scannen een string in plaats van het toetsenbord. Maar laten we een kijkje nemen op een beetje variantie van deze. In scanf2, ik eigenlijk verpest. Wat is er mis-en ik zal verstoppen de opmerking dat zo veel-licht wat is er mis met dit programma, versie 2? Wees als technisch mogelijk deze tijd. Het ziet er goed uit. Het is mooi ingesprongen, maar- oke, wat dacht je van laten we snoeien het naar beneden tot kortere vragen? Leiding 16. Wat is lijn 16 doet in precieze, maar technisch Engels? Het krijgen van een beetje lastig. Ja, Michael. [Student] Het is te wijzen op de eerste letter van een string. 

Oke, in de buurt. Laat ik tweak dat een beetje. Wijzend op de eerste letter van een string, bent u verklaren van een variabele genaamd buffer dat wijst naar het eerste adres van een string, of liever, zal dit punt meer specifiek op een char. Let op het is niet echt gericht ergens omdat er geen opdracht operator. Er is geen gelijkteken, dus alles wat we doen is de verdeling van de variabele genaamd buffer. Het gebeurt te zijn 32 bits, want het is een pointer, en de inhoud van buffer waarschijnlijk uiteindelijk bevat het adres van een char, maar voor nu, wat betekent buffer bevatten? Zomaar wat onzin, wie weet, wat vuilnis waarde, want wij hebben niet expliciet geïnitialiseerd, dus moeten we er niet van uitgaan niets. Oke, dus nu lijn 17 is-wat doet lijn 17 doen? Misschien is dat zal warm deze op. Hij drukt een string, toch? Hij drukt u String. 

Lijn 18 is een soort van bekende nu in dat we slechts een verschil van dit zag maar met een andere indeling, zodat in leiding 18 we vertellen scanf hier is het adres van een stuk van het geheugen. Ik wil dat je ring in een tekenreeks, zoals geïmpliceerd door% s, maar het probleem is dat we niet hebben een paar dingen gedaan hier. Wat is een van de problemen? [Student] Het probeert dereference een null pointer. Goed, null of gewoon op een andere manier bekend pointers. Je overhandigen scanf een adres, maar je zei het zojuist al dat dit hetzelfde adres is wat vuilnis waarde, omdat we niet echt toe te wijzen aan iets, en dus je vertelt scanf effectief gaan hier zet een string, maar we weten niet waar hier nog is, dus we hebben niet echt toegewezen geheugen voor buffer. Bovendien, wat zijn je ook niet eens te vertellen scanf? Stel dat dit was een stuk van het geheugen, en het was geen vuilnis waarde, maar je bent nog steeds niet vertellen scanf iets belangrijks. [Student] Waar het in werkelijkheid is, het en-teken. Ampersand, dus in dit geval, het is oke. Omdat buffer is al gedeclareerd als een pointer met de * stuk van syntax, hoeven we niet te ampersand gebruiken want het is al een adres, maar ik denk dat ik hoorde hier. [Student] Hoe groot is het? Goed, we zijn niet te vertellen scanf hoe groot deze buffer is, wat betekent dat zelfs als buffer waren pointer, we zeggen scanf, zet een string hier, maar hier kan 2 bytes, het zou kunnen zijn 10 bytes, kan het een megabyte. Scanf heeft geen idee, en omdat dit is een stuk van het geheugen vermoedelijk, het is niet een string nog niet. Het is slechts een string als je eenmaal schrijven tekens en een \ 0 tot dat stuk van het geheugen. Nu is het gewoon een stuk van het geheugen. Scanf zal niet weten wanneer te stoppen met schrijven naar dat adres. 

Misschien herinner je je een aantal voorbeelden in het verleden waar willekeurig ik getypt op het toetsenbord proberen om overflow een buffer, en we spraken vrijdag over precies dat. Als een tegenstander injecteert een of andere manier in uw programma een veel groter woord of zin of zin dan je verwachtte je overspoeld een stuk van het geheugen, die kan slechte gevolgen hebben, zoals de overname van het hele programma zelf. We moeten een of andere manier oplossen. Laat me uit te zoomen en gaan in versie 3 van dit programma. Dat is een beetje beter. In deze versie, het verschil merken. In regel 16, ben ik weer waarbij een variabele genaamd buffer, maar wat is het nu? Het is een reeks van 16 tekens. Dit is goed omdat dit betekent dat ik kan nu vertellen scanf hier is een echte brok van het geheugen. U kunt bijna denken van arrays als pointers nu, hoewel ze niet zijn eigenlijk gelijkwaardig. Ze zullen zich anders gedragen in verschillende contexten. Maar het is zeker zo dat buffer wordt verwijst 16 aaneengesloten tekens want dat is wat een array is en dat is al een paar weken. 

Hier, ik vertel scanf hier is een stuk van het geheugen. Deze keer is het eigenlijk een stuk van het geheugen, maar waarom is dit programma nog steeds misbruikt? Wat is er mis nog steeds? Ik heb gezegd geef me 16 bytes, maar- [Student] Wat als ze typen in meer dan 16? Precies, wat als de gebruiker typt in 17 tekens of 1700 tekens? In feite, laten we eens kijken of we er niet over struikelen deze fout nu. Het is beter, maar niet perfect. Laat me gaan en lopen te maken scanf3 om dit programma te compileren. Laat me lopen scanf3, String alsjeblieft: hallo, en we lijken wel goed. Laat me proberen een iets langere een, hello there. Oke, laten we het doen hello there hoe gaat het vandaag, op Enter. Aan de vorm van geluk hier, laten we zeggen hello there how are you. Verdomme. Oke, dus we hadden geluk. Laten we eens kijken of we niet oplossen. Nee, het is niet gaan om mij te laten kopiëren. Laten we het opnieuw proberen. Oke, stand-by. We zullen zien hoe lang ik kan doen alsof om zich te concentreren, terwijl nog steeds om dit te doen. Verdomme. Dat is nogal geval, eigenlijk. Daar gaan we dan. Punt gemaakt. 

Dit gênant hoewel het ook is, het is ook een van de bronnen van grote verwarring bij het schrijven van programma's die bugs hebben, omdat zij zich manifesteren slechts een keer in de zoveel tijd wel eens. De realiteit is dat zelfs als uw code volledig is gebroken, het kan slechts eenmaal volledig gebroken tijd want soms, in wezen wat er gebeurt is het besturingssysteem wijst een beetje meer geheugen dan je eigenlijk nodig hebt om wat voor reden dan ook, en dus niemand anders gebruikt het geheugen direct na uw stuk van 16 tekens, dus als je naar 17, 18, 19, wat dan ook, het is niet zo'n big deal. Nu, de computer, zelfs als het niet crashen op dat moment, zou byte nummer 17 of 18 of 19 eventueel te gebruiken voor iets anders, op welk punt je gegevens die je daar te zetten, zij het veel te lange, gaat om potentieel overschreven door een andere functie. Het is niet per se zal intact blijven, maar het zal niet noodzakelijk leiden tot een seg fout. Maar in dit geval, heb ik eindelijk mits voldoende karakters dat ik in wezen overtrof mijn segment van het geheugen, en bam, het besturingssysteem zei: "Sorry, dat is niet goed, segmentation fault." 

En laten we nu zien of wat blijft hier in mijn directory- merk dat ik dit bestand hier hebben, kern. Merk op dat dit weer is een core dump genoemd. Het is in wezen een bestand dat de inhoud van het geheugen van uw programma's bevat op het punt waar het neerstortte, en alleen maar om een ​​klein voorbeeld hier proberen laat me gaan hier en uit te voeren gdb op scanf3 en geef vervolgens een derde argument genoemd kern, en hier opmerken dat als ik een lijst van de code, zullen we in staat zoals gebruikelijk met gdb om te beginnen met een wandeling door dit programma, en ik kan draaien en zodra ik hit-als bij de stap commando in gdb- zodra ik raakte de potentieel buggy lijn na het typen in een enorme reeks, Ik zal in staat zijn om daadwerkelijk hier identificeren. Meer over dit, hoewel, in rubriek in termen van core dumps en dergelijke, zodat je daadwerkelijk kunt binnen steken rond de core dump en te zien op welke lijn het programma dat u gefaald. Hebt u vragen dan op aanwijzingen en op adressen? Want vandaag op, we gaan om te beginnen met het nemen van uit dat deze dingen bestaan en we weten precies wat ze zijn. Ja. 

[Student] Hoe komt het dat je niet hoeft om een ​​ampersand zetten naast de part- Goede vraag. Hoe komt het dat ik niet hoefde te een ampersand zetten naast de karakter array als ik eerder met de meeste van onze voorbeelden? Het korte antwoord is arrays zijn een beetje speciaal. U kunt ook een buffer bijna denken als daadwerkelijk een adres, en het gewoon zo gebeurt het geval te zijn, dat het plein haakjesnotering is een gemak, zodat we kunnen gaan in de houder 0, beugel 1, draagconstructie 2, zonder de * notatie. Dat is een beetje een leugentje om bestwil, omdat arrays en pointers zijn in feite iets anders, maar ze kunnen vaak maar niet altijd elkaar worden gebruikt. Kortom, wanneer een functie wordt verwacht een pointer naar een stuk van het geheugen, kunt u ofwel het doorgeven van een adres dat werd geretourneerd door malloc, en we zullen weer te zien malloc het duurde niet lang, of u kunt doorgeven van de naam van een array. Je hoeft niet te ampersand maken met arrays omdat ze al wezen als adressen. Dat is de enige uitzondering. De vierkante haken ze speciaal. 

Kon je een ampersand naast de buffer? In dit geval niet. Dat zou niet werken, omdat, nogmaals, van deze hoek zaak waar arrays zijn niet helemaal eigenlijk adressen. Maar we zullen nog even op dat het duurde niet lang met andere voorbeelden. Laten we proberen om hier een probleem op te lossen. We hebben een data structuur die we hebben gebruikt voor enige tijd bekend als een array. Case in point, dat is wat we net hadden. Maar arrays hebben een aantal positieve kanten en nadelen. Arrays zijn leuk waarom? Wat is een ding dat u wilt-in de mate je arrays-over arrays? Wat is handig over hen? Wat is er dwingende? Waarom hebben we introduceren ze in de eerste plaats? Ja. [Student] Ze kunnen heel wat gegevens op te slaan, en je hoeft niet een hele ding te gebruiken. U kunt gebruik maken van een sectie. Goed, met een scala kunt u veel gegevens op te slaan, en je hoeft niet per se om alles te gebruiken, zodat u kunt overallocate, die misschien handig als je niet weet op voorhand hoeveel van iets te verwachten. 

GetString is een perfect voorbeeld. GetString, geschreven door ons, heeft geen idee hoeveel tekens te verwachten, dus het feit dat we kunnen stukken aaneengesloten geheugen toe te wijzen is goed. Arrays ook het oplossen van een probleem zagen we een paar weken geleden waar je begint te evolueren in iets heel slecht ontworpen. Bedenk dat ik een student structuur genaamd David gemaakt, en toen dat was eigenlijk een alternatief, hoewel, aan het hebben van een variabele genaamd naam en een andere variabele met de naam, denk ik, huis, en een andere variabele met de naam ID want in dat verhaal dat ik toen wilde iets anders te introduceren zoals Rob in het programma, dus toen besloot ik wacht eens even, Ik moet deze variabelen hernoemen. Laten we de mijne name1, ID1, House1. Laten we Rob's naam2, house2, ID2. Maar wacht eens even, hoe zit het met Tommy? Dan hebben we nog drie variabelen. We introduceerden iemand anders, vier sets van variabelen. De wereld begon te krijgen rommelig zeer snel, dus introduceerden we structs, en wat is meeslepend over een struct? Wat doet een C struct laten doen? Het is echt lastig vandaag. Wat is er? >> [Onverstaanbaar student reactie] Ja, in het bijzonder, typedef stelt u in staat om een ​​nieuwe data type, en struct, de struct trefwoord, kunt u in te kapselen om conceptueel gerelateerd stukjes data samen en daarna noemen ze zoiets als een student. 

Dat was goed, want nu kunnen we modelleren veel meer soort van conceptueel consequent de notie van een student in een variabele niet willekeurig met een voor een tekenreeks, een voor een ID, enzovoort. Arrays zijn leuk omdat ze ons in staat stellen om te beginnen met het opruimen van onze code. Maar wat is een nadeel nu van een array? Wat kun je niet doen? Ja. [Student] Je moet weten hoe groot het is. Je moet weten hoe groot het is, dus het is een beetje vervelend. Degenen onder jullie met voorafgaande programmeerervaring weten dat in een groot aantal talen, zoals Java, kunt u vragen een stuk van het geheugen, in het bijzonder een array, hoe groot bent u, met een lengte, onroerend goed, zo te zeggen, en dat is echt handig. In C kun je niet eens bellen strlen op een generieke reeks omdat strlen, zoals het woord al zegt, is alleen voor strijkers, en je kunt achterhalen van de lengte van een string als gevolg van deze menselijke conventie van het hebben van een \ 0, maar een array, meer in het algemeen, is slechts een deel van het geheugen. Als het een array van ints, is er niet van plan om een ​​aantal speciale tekens worden aan het eind voor u klaar. U de lengte van een array onthouden. Een ander nadeel van een array stak de kop in getString zelf. Wat is een ander nadeel van een array? Meneer, alleen jij en ik vandaag. [Onverstaanbaar student reactie] >> Het is wat? Het is verklaard op de stapel. Oke, verklaarde op de stapel. Waarom ga je niet zo? [Student] Omdat het wordt hergebruikt. Het wordt hergebruikt. Oke, als je gebruik maken van een array om geheugen toe te wijzen, je kunt niet, bijvoorbeeld, terug te sturen omdat het op de stapel. Oke, dat is een nadeel. En wat te denken van een ander met een array? Zodra u toewijzen, je bent een soort van geschroefd als u meer ruimte nodig dan array. 

Dan hebben we geïntroduceerd, recall, malloc, die gaf ons de mogelijkheid om dynamisch geheugen toewijzen. Maar wat als we probeerden een andere wereld bij elkaar? Wat als we wilden een paar van die problemen op te lossen dus we plaats-mijn pen is in slaap gevallen hier- wat als we in plaats daarvan wilden wezen een wereld die niet langer is zoals dit? Dit is een array, en, natuurlijk, dergelijke verslechtert wanneer we het einde van de array raken, en ik heb nu niet meer ruimte voor een ander geheel getal of een ander teken. Wat als we soort van preventief wel zeggen, waarom we niet te ontspannen deze eis dat al deze delen van het geheugen aaneengesloten zijn rug aan rug, en waarom niet, als ik moet een int of een char, Geef me ruimte voor een van hen? En als ik een andere nodig hebt, geef me nog een ruimte, en als ik een andere nodig hebt, geef me nog een ruimte. Het voordeel daarvan is nu dat als iemand neemt het geheugen hier, geen big deal. Ik neem deze extra stuk van het geheugen hier en dan is dit een. 

Nu, de enige vangst is dat dit bijna voelt alsof ik een hele hoop verschillende variabelen. Dit voelt als vijf verschillende variabelen mogelijk. Maar wat als we stelen een idee van strings waarbij we een of andere manier met elkaar te verbinden deze dingen conceptueel, en wat als ik dit deed? Dit is mijn zeer slecht opgesteld pijl. Maar stel dat elk van deze delen van het geheugen wees naar de andere, en deze kerel, die geen broer of zus aan zijn recht, geen dergelijke pijl. Dit is in feite wat heet een gelinkte lijst. Dit is een nieuwe datastructuur die ons in staat stelt toe te wijzen een stuk van het geheugen, toen nog een, en nog een, en nog een, elke keer als we willen tijdens een programma, en we bedenken dat ze allemaal een of andere manier verbonden door letterlijk chaining ze samen, en we deden dat picturaal hier met een pijl. Maar in code, wat zou het zijn het mechanisme via welke je zou kunnen een of andere manier aan te sluiten, bijna als Scratch, een brok naar de andere brok? We konden gebruik maken van een pointer, toch? Want echt op de pijl die gaat vanuit de linkerbovenhoek plein, deze man hier om deze, binnen kon bevatten van dit plein niet zomaar een ints, niet zomaar een char, maar wat als ik eigenlijk toegewezen een beetje extra ruimte, zodat nu, elk van mijn delen van het geheugen, ook al is dit gaat me kosten, Nu er een beetje meer rechthoekige waarbij een van de delen van het geheugen wordt gebruikt voor een aantal, zoals het getal 1, en dan als deze kerel slaat het nummer 2, dit andere deel van het geheugen wordt gebruikt voor een pijl, of meer concreet, een pointer. En stel dat ik de nummer 3 op te slaan hier, terwijl ik gebruik deze om te wijzen op die vent, en nu deze man, laten we aannemen dat ik maar drie van zulke delen van het geheugen wilt. Ik trek een lijn door dat aan te geven null. Er is geen extra karakter. 

Inderdaad, dit is hoe we kunnen gaan over het implementeren iets dat heet een gekoppelde lijst. Een gelinkte lijst is een nieuwe datastructuur, en het is een opstap naar veel liefhebber datastructuren die beginnen om problemen op te lossen langs de lijnen van Facebook-type problemen en Google-type problemen waar je enorme datasets en het niet langer snijdt het om aansluitend op te slaan alles en gebruiken iets als lineair zoeken of zelfs zoiets als binaire zoekopdracht. U wilt nog beter looptijden. In feite, een van de heilige Grails we praten over later deze week of volgende is een algoritme waarvan looptijd constant is. In andere woorden, het is altijd dezelfde hoeveelheid tijd ongeacht hoe groot de ingang is, en dat zou inderdaad dwingende, meer nog dan iets logaritmisch. Wat is dit op het scherm hier? Elk van de rechthoeken is precies wat ik net getekend met de hand. Maar het ding helemaal aan de linkerkant is een speciale variabele. Het gaat om een ​​enkele wijzer zijn, omdat het een gotcha met een gekoppelde lijst, als deze dingen worden genoemd, is dat je om op te hangen op het ene uiteinde van de gekoppelde lijst. 

Net als bij een string, moet u het adres van de eerste char te leren kennen. Dezelfde deal voor gelinkte lijsten. Je moet het adres van de eerste deel van het geheugen weten want van daaruit kunt u bij elke andere. Downside. Welke prijs betalen we voor deze veelzijdigheid van het hebben van een dynamisch omvangrijke data structuur dat als we ooit behoefte aan meer geheugen, fijn, slechts toe te wijzen nog een stuk en trek een aanwijzer van de oude naar de nieuwe staart van de lijst? Ja. [Student] Het duurt ongeveer twee keer zo veel ruimte. Het duurt twee keer zo veel ruimte, zodat zeker een nadeel, en we hebben gezien dit afweging voor tussen tijd en ruimte en flexibiliteit indien nu moeten we niet 32 ​​bits voor elk van deze nummers. We moeten echt 64, 32 voor het aantal en de 32 voor de aanwijzer. Maar hey, ik heb 2 gigabyte aan RAM-geheugen. Het toevoegen van een andere 32 bits hier en hier lijkt niet zo groot van een deal. Maar voor grote datasets, het voegt zeker tot letterlijk twee keer zo veel. Wat is een ander nadeel nu, of wat functie geven we op, Als wij vertegenwoordigen lijsten van dingen met een gekoppelde lijst en geen array? [Student] U kunt niet achteruit doorkruisen het. Je kunt het niet naar achteren doorlopen, dus je bent soort geschroefd als je loopt van links naar rechts met behulp van een for-lus of een while-lus en dan realiseer je je: "O, ik wil om terug te gaan naar het begin van de lijst." U niet omdat deze pointers alleen van links naar rechts de pijlen. 

Nu, je zou het begin van de lijst onthouden met een andere variabele, maar dat is een complexiteit om in gedachten te houden. Een array, maakt niet uit hoe ver je gaat, kun je altijd doen min, min, min, min en terug te gaan naar waar je vandaan komt. Wat is een ander nadeel hier? Ja. [Onverstaanbaar student vraag] Je kon, dus je hebt eigenlijk alleen maar voorgesteld een gegevensstructuur genaamd een dubbel gelinkte lijst, en inderdaad, je zou een andere aanwijzer toe te voegen aan elk van deze rechthoeken dat gaat de andere richting, de bovenkant waarvan is nu kun je doorkruisen heen en weer, de keerzijde van dat nu je gebruikt drie keer zoveel geheugen als we vroeger en ook het toevoegen van complexiteit in termen van de code die u moet schrijven om het goed te krijgen. Maar deze zijn misschien redelijke compromissen, indien de terugname belangrijker. Ja. [Student] U kunt niet over een 2D-gelinkte lijst. Goed, kun je niet echt een 2D-gelinkte lijst. Je zou kunnen. Het is niet zo eenvoudig als een array. Net als een array, je doet open beugel, gesloten beugel, open beugel, gesloten beugel, en je krijgt een aantal 2-dimensionale structuur. Je kon implementeren van een 2-dimensionale verbonden lijst als je add-zoals u voorgesteld-derde wijzer naar elk van deze dingen, en als je na te denken over een andere lijst komt op je 3D-stijl van het scherm voor ons allen, dat is gewoon een keten van een soort. We kunnen het doen, maar het is niet zo eenvoudig als het typen van open beugel, vierkant haakje. Ja. [Onverstaanbaar student vraag] Goed, dus dit is een echte kicker. 

Deze algoritmen die we hebben kwijnde over, net als oh, binair zoeken, u kunt zoeken een reeks van nummers op het bord of een telefoonboek zo veel sneller als u verdeel en heers en een binaire zoekalgoritme, maar binaire zoekopdracht vereiste twee veronderstellingen. Een, dat de gegevens zijn gesorteerd. Nu kunnen we vermoedelijk houden deze gesorteerd, dus misschien is dat geen probleem, maar binaire zoekopdracht ook aangenomen u had willekeurige toegang tot de lijst met nummers en een reeks kunt u over random access, en door random access, Ik bedoel als je een array, hoeveel tijd kost het u om naar beugel 0? Een bewerking, u gewoon gebruik maken van [0] en je bent daar. Hoeveel stappen duurt het om naar locatie 10? Een stap, je gewoon naar [10] en je daar bent. Daarentegen, hoe kom je aan de 10e geheel getal in een gekoppelde lijst? Je moet beginnen bij het begin, omdat je alleen herinneren het begin van een gekoppelde lijst, net als een string wordt herinnerd door het adres van de eerste char, en vinden dat 10e int of dat 10e teken in een string, moet je de hele verdomde ding te zoeken. 

Nogmaals, we zijn niet het oplossen van al onze problemen. Introduceren we nieuwe, maar het is echt afhankelijk van wat je probeert te ontwerpen voor. In termen van de uitvoering van deze, kunnen we een idee lenen van die student structuur. De syntax is zeer vergelijkbaar, behalve nu, het idee is een beetje meer abstracte dan huis en naam en ID. Maar ik stel voor dat we een datastructuur in C hebben dat heet knooppunt, als het laatste woord op de dia al doet vermoeden, binnenkant van een knooppunt, en een knooppunt is gewoon een generieke container in de informatica. Het wordt meestal getekend als een cirkel of een vierkant of rechthoek als we hebben gedaan. En in deze gegevensstructuur hebben we een int, n, dus dat is het nummer dat ik wil opslaan. Maar wat is deze tweede lijn, struct knoop * volgende? Waarom is dit juist is, of welke rol speelt dit ding te spelen, ook al is het een beetje cryptisch op het eerste gezicht? Ja. [Onverstaanbaar student reactie] Precies, dus de * soort buit dat het een pointer van een soort. De naam van deze wijzer is willekeurig volgende, maar we konden noemen het alles wat we willen, maar wat betekent dit pointer wijst u? [Student] Een andere node. >> Precies, het wijst op nog zo'n knooppunt. 

Nu, dit is een soort nieuwsgierigheid van C. Bedenk dat C wordt gelezen door een compiler boven naar beneden, links naar rechts, wat betekent dat als-dit is een weinig verschillend van wat we hebben gedaan met de student. Wanneer we een student gedefinieerd, hebben we eigenlijk niet daar legde een woord. Het is gewoon gezegd typedef. Dan hadden we int id, string naam, string huis, en student onderaan de struct. Deze verklaring is een beetje anders, omdat, nogmaals, de C-compiler is een beetje dom. Het wordt alleen maar om te lezen van boven naar beneden, dus als het bereiken van de 2e lijn hier waar naast wordt verklaard en het ziet, oh, hier is een variabele genaamd volgende. Het is een pointer naar een struct node. De compiler gaat beseffen wat is een struct knoop? Ik heb nog nooit gehoord van deze zaak voor, omdat het woord knooppunt anders niet zouden worden weergegeven tot de bodem, zodat er deze redundantie. Je moet struct knoop hier zeggen, die u vervolgens kunt verkorten later dankzij typedef hier beneden, maar dit komt doordat we verwijzen naar de structuur zelf binnenzijde van de constructie. Dat is de enige gotcha daar. 

Een aantal interessante problemen zullen ontstaan. We hebben een lijst met getallen. Hoe kunnen we in te voegen in het? Hoe zoeken we het? Hoe kunnen we verwijderen van? Zeker nu dat we al deze pointers te beheren. Je dacht dat pointers waren soort van mind-bending als je had een van hen alleen maar proberen om een ​​int lezen om het te. Nu moeten we een hele lijst is de moeite waard te manipuleren. Waarom gaan we niet hier nemen onze 5-minuten pauze, en dan zullen we brengen sommige mensen op het podium om precies dat te doen. 

C is veel leuker als het nagespeeld. Wie zou letterlijk graag eerst? Oke, komen op. Je bent eerst. Wie zou willen zijn 9? Oke, 9. Hoe zit het met 9? 17? Een beetje kliek hier. 22 en 26 in die eerste rij. En dan wat te denken van iemand die daar worden gewezen. Je bent 34. Oke, kom 34, op maximaal. Ten eerste is daar. Oke, alle vier van jullie. En wie hebben we zeggen voor 9? Wie is onze 9? Wie wil zo graag 9? Oke, kom op, wees 9. Daar gaan we. 34, zullen we ontmoeten u daar. Het eerste deel is het maken van jezelf lijken. 26, 22, 17, goed. Als je af staan ​​aan de kant, want we gaan je malloc in een moment. 

Goed, goed. Oke, prima, dus laten we hier vragen een paar vragen. En eigenlijk, wat is je naam? >> Anita. Anita, okay, kom hier. Anita gaat om ons te helpen soort van het oplossen van een vrij eenvoudige vraag in de eerste, dat is hoe vind je al dan niet een waarde in de lijst voorkomt? Let nu op die eerste, hier vertegenwoordigd door Lucas, is een beetje anders, en dus zijn stuk papier is bewust opzij want het is niet zo groot en niet in beslag nemen zo veel bits, hoewel technisch heeft hij het papier van hetzelfde formaat gewoon gedraaid. Maar hij is een beetje anders in dat hij slechts 32 bits voor een pointer, en al deze jongens zijn 64 bits, waarvan de helft van het aantal, waarvan de helft een pointer. Maar de aanwijzer wordt niet weergegeven, dus als jullie kunnen een beetje onhandig gebruik uw linkerhand om te wijzen naar de persoon naast je. En je bent nummer 34. Wat is je naam? Ari. Ari, dus eigenlijk, houdt het papier in uw rechterhand en linkerhand gaat recht naar beneden. U vertegenwoordigt null aan de linkerkant. 

Nu onze menselijke beeld is zeer consistent. Dit is eigenlijk hoe pointers werken. En als je een beetje op deze manier samenperst, dus ik ben niet in de weg. Anita hier, vind ik het nummer 22, maar gaan uit van een beperking van het niet mensen houden tot stukjes papier, maar dit is een lijst, en heb je alleen Lucas om te beginnen met want hij is letterlijk de eerste pointer. Stel, je bent zelf een pointer, en dus moet je ook de mogelijkheid om te wijzen op iets. Waarom ga je niet beginnen door te wijzen op wat Lucas wijst op? Goed, en laat mij dit uit te vaardigen hier. Net omwille van de discussie, laat me trek hier een lege pagina. Hoe schrijf je je naam? >> Anita. Oke, Anita. Laten we zeggen dat knooppunt * anita = lucas. Nou, moeten we niet bellen u lucas. We moeten bellen u voor het eerst. Waarom is dit in feite overeen met de werkelijkheid hier? Een, eerst al bestaat. Eerste is vermoedelijk ergens hier toegewezen. Node * eerste, en het is al toegewezen een lijst een of andere manier. Ik weet niet hoe dat gebeurd is. Dat gebeurde voor de les begon. Deze gelinkte lijst van mensen is gemaakt. En nu op dit punt in het verhaal, dit is allemaal op Facebook blijkbaar later- op dit punt in het verhaal, Anita geïnitialiseerd gelijk aan eerste, wat niet betekent dat Anita wijst naar Lucas. Integendeel, zij wijst naar wat hij wijst naar omdat hetzelfde adres dat binnen is van Lucas 32 bits - 1, 2, 3 - nu ook binnenkant van Anita's 32 bits - 1, 2, 3. 

Kijk nu 22. Hoe zou je dat doen? Wat is dat? >> Point to wat dan ook. Wijs wat dan ook, dus ga je gang en doen het uit zo goed mogelijk hier. Goed, goed, en nu ben je te wijzen op-hoe heet je met 22? Ramon. >> Ramon, dus Ramon houdt met 22. U heeft nu gedaan een cheque. Heeft Ramon == 22, en zo ja, bijvoorbeeld, kunnen we return true. Laat me-terwijl deze jongens sta hier een beetje onhandig- laat me snel iets doen als bool te vinden. Ik ga om verder te gaan en te zeggen (knooppunt * lijst, int n). Ik ben zo terug met jullie. Ik moet gewoon wat code te schrijven. En nu ga ik verder te gaan en dit, knoop * anita = do list. En ik ga om verder te gaan en te zeggen, terwijl (anita! = NULL). 

De metafoor is hier een beetje uitgerekt, maar terwijl (anita! = NULL), wat wil ik doen? Ik moet een manier verwijzen naar het gehele getal dat Anita wijst op. In het verleden, wanneer we structuren hadden, die een knooppunt, gebruikten we de punt-notatie, en we zouden iets zeggen anita.n, maar het probleem hier is dat Anita niet een struct als zodanig. Wat is ze? Ze is een pointer, dus echt, als we willen dit punt te gebruiken notatie- en dit eruit komt te zien met opzet een beetje cryptisch- we moeten iets doen, zoals naar de linkerhand wat Anita's wijst op en krijgen dan het veld met de naam n. Anita is een pointer, maar wat is * anita? Wat vind je als je naar wat Anita wijst op? Een struct, een knooppunt en een knooppunt, recall, heeft een veld n omdat het, herinneren, deze 2 velden, naast en n, dat zagen we een ogenblik geleden hier. 

Om daadwerkelijk na te bootsen dit in de code, we konden doen en zeggen if ((* anita). n == n), de n dat ik ben op zoek naar. Merk op dat de functie werd in het aantal waar ik om geef. Dan kan ik verder gaan en doen iets als return true. Anders, als dat niet het geval is, wat ik wil doen? Hoe vertaal ik naar blauwdruk van wat Anita deed dat intuïtief door een wandeling door de lijst? Wat moet ik hier doen tot simuleren Anita het nemen van die stap naar links, die stap naar links? [Onverstaanbaar student reactie] >> Wat is dat? [Onverstaanbaar student reactie] Goed, geen slecht idee, maar in het verleden, toen we dit hebt gedaan, hebben we gedaan anita + + want dat zou de nummer 1 toe te voegen aan Anita, die typisch zou wijzen op de volgende persoon, zoals Ramon, of de persoon naast hem, of de naast hem iemand langs de lijn. Maar dat is niet helemaal goed hier want wat doet dit ding eruit in het geheugen? Niet dat. We moeten die schakelen. Het lijkt erop dat deze in het geheugen, en ook al heb ik 1 en 2 en 3 dicht bij elkaar getrokken, als we echt simuleren-can jullie, terwijl nog steeds wijst naar dezelfde mensen, kunnen sommige van u een willekeurige stap terug, sommigen van jullie een willekeurige stap voorwaarts? 

Deze puinhoop is nog steeds een gelinkte lijst, maar deze jongens kan overal in het geheugen zijn, dus anita + + is niet van plan om te werken waarom? Wat is op de locatie van anita + +? Wie weet. Het is een andere waarde die net zo gebeurt te worden tussengevoegd tussen al deze knooppunten bij toeval omdat we niet met behulp van een array. We toegewezen elk van deze knooppunten afzonderlijk. Oke, als jullie kunnen schoonmaken jezelf een back-up. Laat me voorstellen dat in plaats van anita + +, we doen in plaats anita gets- goed, waarom gaan we niet naar wat Anita wijst op en dan doen. volgende stap? Met andere woorden, we gaan naar Ramon, wie houdt het nummer 22, en dan. volgende is alsof Anita zou het kopiëren van zijn linkerhand pointer. Maar ze zou niet verder gaan dan Ramon, omdat we vinden 22. Maar dat zou het idee zijn. Nu, dit is een god-awful puinhoop. Eerlijk gezegd, zal niemand ooit vergeet deze syntaxis, en zo gelukkig, het is eigenlijk een beetje bewust-oh, je niet echt zien wat ik schreef. Dit zou meer overtuigend als je kon. Voila! 

Achter de schermen, was ik het oplossen van het probleem op deze manier. Anita, dat stap opzij nemen, eerst, gaan we naar het adres dat Anita wijst op en waar ze vinden niet alleen n, die we gewoon gecontroleerd ter vergelijking, maar je vindt er ook volgende - in dit geval, Linkerhand Ramon wijst naar het volgende knooppunt in de lijst. Maar dit is de god-awful puinhoop waar ik het eerder, maar het blijkt dat C laat ons vereenvoudigen dit. In plaats van het schrijven (* anita), kunnen we in plaats daarvan gewoon schrijven anita-> n, en het is precies hetzelfde functioneel, maar het is veel meer intuïtief, en het is nog veel meer in overeenstemming is met het beeld dat we al tekenen al die tijd met behulp van pijlen. 

Tot slot, wat we moeten doen aan het eind van dit programma? Er is een regel code over. Keer terug wat? False, want als we door het hele while loop Anita en is in feite null, dat betekent dat ze ging helemaal naar het einde van de lijst waar ze wees naar-hoe heet je ook alweer? Linkerhand Ari. >> Ari, die is null. Anita is nu nul, en ik realiseer me dat je alleen hier staan ​​onhandig in het ongewisse want ik ga af op een monoloog hier, maar we zullen weer betrekken u in slechts een moment. Anita null is op dat punt in het verhaal, zodat de while-lus wordt beëindigd, en we hebben om terug te keren vals, want als ze kreeg helemaal naar null pointer Ari's er was geen nummer dat ze gezocht in de lijst. We kunnen ruimen dit ook, maar dit is een vrij goede uitvoering dan van een traversal functie, een zoekfunctie voor een gelinkte lijst. Het is nog steeds lineair zoeken, maar het is niet zo eenvoudig als + + een pointer of + + Een i variabele, want nu kunnen we niet raden waarbij elk van deze knooppunten in het geheugen. We moeten letterlijk volgen het spoor van broodkruimels of, meer specifiek, pointers, om van de ene knooppunt naar het andere. 

Nu gaan we proberen een andere. Anita, wil je hier terug te komen? Waarom gaan we niet verder te gaan en toe te wijzen een andere persoon uit het publiek? Malloc-wat is je naam? >> Rebecca. Rebecca. Rebecca is malloced van het publiek, en ze is nu het opslaan van het nummer 55. En het doel bij de hand is nu voor Anita te plaatsen om Rebecca in de gelinkte lijst hier in zijn juiste plaats. Kom hier voor een moment. Ik heb gedaan iets als dit. Ik heb gedaan knooppunt *. En hoe heet je ook alweer? Rebecca. >> Rebecca, oke. Rebecca krijgt malloc (sizeof (node)). Net zoals we hebben toegewezen zaken als studenten en wat al niet in het verleden, moeten we de grootte van de knoop, dus nu Rebecca wijst op wat? Rebecca heeft twee velden binnenkant van haar, waarvan er 55. Laten we doen wat, rebecca-> = 55. Maar dan rebecca-> volgende moet-worden wil op dit moment, haar hand is een soort van wie weet? Het is te wijzen op een aantal vuilnis waarde, dus waarom niet voor een goede maatregel we op zijn minst doen dit zodat linkerhand is nu aan haar zijde. Nu Anita, neem het van hier. Je hebt Rebecca te zijn toegewezen. Ga je gang en vinden waar we moeten zetten Rebecca. Goed, heel goed. Oke, goed, en nu moeten we je een beetje van richting te geven, dus je hebt bereikt Ari. Zijn linkerhand is null, maar Rebecca duidelijk behoort tot de juiste, dus hoe moeten we deze gelinkte lijst wijzigen om Rebecca te voegen in de juiste plaats? Als je zou kunnen letterlijk mensen linker handen bewegen als dat nodig is, zullen we het probleem oplossen op die manier. Oke, goed, en ondertussen, linkerhand Rebecca's is nu aan haar zijde. 

Dat was te gemakkelijk. Laten we proberen de toewijzing-We zijn bijna klaar, 20. Oke, komen op. 20 is toegekend, dus laat me ga je gang en hier nog een keer zeggen we hebben net gedaan knooppunt * Saad. We hebben malloc (sizeof (node)). We dan doen precies dezelfde syntax als voorheen voor 20, en ik doe next = NULL, en nu is het aan Anita om u in te voegen in de gelinkte lijst, als je zou kunnen dat exact dezelfde rol spelen. Uitvoeren. Oke, goed. Nu goed nadenken alvorens te beginnen met bewegen linker handen rond. Je veruit kreeg de meeste lastige rol vandaag. Wiens hand moet eerst worden verplaatst? Oke, wacht, ik ben een aantal no's horen. Als sommige mensen zou beleefd willen helpen hier op te lossen een lastige situatie. Wiens linkerhand moet eerst misschien worden bijgewerkt? Ja. [Student] Saad's. Oke, Saad, waarom, hoewel? [Onverstaanbaar student reactie] Goed, want als we verhuizen-wat is je naam? >> Marshall. Marshall, als we verhuizen zijn hand first down op null, nu hebben we letterlijk wees vier mensen in deze lijst want hij was het enige wat wijst op Ramon en iedereen naar links, zodat bijwerken van die wijzer eerste was slecht. Laten we ongedaan te maken dat. Goed, en nu ga je gang en zet de juiste linkerhand wijst naar Ramon. Dit voelt een beetje overbodig. Nu is er twee mensen te wijzen op Ramon, maar dat is prima want nu hoe anders kunnen we het actualiseren van de lijst? Welke andere kant heeft te bewegen? Uitstekend, nu we verloren geen geheugen? Nee, zo goed, laten we eens kijken of we niet breken dit nogmaals. 

Mallocing een laatste keer, nummer 5. Helemaal in de rug, kom naar beneden. Het is heel spannend. [Applaus] Wat is je naam? >> Ron. Ron, oke, je malloced als nummer 5. We hebben net uitgevoerde code die bijna identiek is aan deze met alleen een andere naam. Uitstekend. Nu, Anita, veel succes het plaatsen van nummer 5 in de lijst nu. Goed, en? Uitstekend, dus dit is echt de derde van drie totale gevallen. We moesten eerst iemand aan het eind, Rebecca. We hadden iemand in het midden. Nu hebben we iemand bij het begin, en in dit voorbeeld we nu moesten Lucas werken voor de eerste keer omdat de eerste element in de lijst nu te wijzen op een nieuwe node, die op zijn beurt wijst naar knooppunt nummer 9. 

Dit was een enorm lastige demonstratie, ik ben er zeker van, dus een groot applaus voor deze jongens als je kon. Mooi gedaan. Dat is alles. U kunt u uw stukjes papier als een kleine herinnering. Het blijkt dat dit te doen in de code is niet zo eenvoudig als gewoon bewegen handen rond en wees pointers op verschillende dingen. Maar beseffen dat wanneer het tijd is om iets als te implementeren een gekoppelde lijst of een variant ervan als je je richt op echt deze fundamentele grondslagen, de hapklare problemen die ik moet uitzoeken, is het deze hand of deze hand, beseffen dat wat anders is een vrij complex programma kan in feite worden gereduceerd tot vrij eenvoudige bouwstenen zoals deze. 

Laten we dingen nog te nemen aan een meer verfijnde richting. We hebben nu het idee van de gekoppelde lijst. We hebben ook-dankzij de suggestie daar-een dubbel gelinkte lijst, die ziet er bijna hetzelfde, maar nu hebben we twee pointers binnenkant van de struct in plaats van een, en we kunnen waarschijnlijk noemen die pointers vorige en volgende of naar links of rechts, maar wij, in feite, hebben twee van hen. De code zou een beetje meer betrokken. Anita had moeten meer werk doen hier op het podium. Maar we kunnen zeker implementeren dat soort structuur. In termen van looptijd, hoewel, Wat zou de looptijd voor Anita van het vinden van een getal n in een gekoppelde lijst nu? Nog steeds grote O van n, dus het is niet beter dan lineair zoeken. We kunnen niet binair zoeken, maar, nogmaals. Waarom was dat zo? Je kunt niet rond te springen. Hoewel we natuurlijk bekijk alle mensen op het podium, en Anita had kunnen eyeballed het en zei: "Hier is het midden van de lijst," ze zou niet weten dat als zij het computerprogramma omdat het enige wat ze hadden aan te haken bij het begin van het scenario was Lucas, die de eerste pointer. Ze zou per se om die links te volgen, tellen haar weg tot ze ongeveer het midden, en zelfs dan, ze niet van plan om te weten wanneer ze bereikte het midden tenzij ze gaat helemaal naar het eind om erachter te komen hoeveel het er zijn, dan Backtracks, en ook dat zou moeilijk zijn, tenzij je had een dubbel gelinkte lijst van een soort. 

Het oplossen van een aantal problemen van vandaag, maar de invoering van anderen. Hoe zit het met een andere datastructuur bij elkaar? Dit is een foto van de trays in Mather House, en in dit geval hebben we een datastructuur hebben we ook een soort van al het over had. We spraken over een stapel in het kader van het geheugen, en dat is soort van bewust genoemd omdat een stapel in de termen van het geheugen daadwerkelijk een datastructuur die meer materiaal gelaagd bovenop heeft. Maar het interessante ding over een stapel, zoals het geval is in de werkelijkheid, is dat het een speciaal soort datastructuur. Het is een datastructuur waarbij het eerste element in is het laatste element uit. Als je de eerste lade worden geplaatst op de stack, je gaat helaas de laatste lade te nemen van de stapel, en dat is niet per se een goede zaak. Omgekeerd kunt u denken andersom, de laatste in het eerste uit. 

Nu, geen enkele scenario's komen te letten op waar het hebben van een stapel datastructuur waar je die eigenschap van de last in, first out, is eigenlijk dwingend? Is dat een goede zaak? Is dat een slechte zaak? Het is zeker een slechte zaak als de lades waren niet allemaal identiek en ze waren allemaal speciale kleuren of wat al niet, en de kleur die je wilt is helemaal aan de onderkant. Natuurlijk kun je niet krijgen dat zonder veel moeite. Je moet beginnen vanaf de bovenkant en werk je weg naar beneden. Ook wat als je een van deze ventilator jongens die wacht de hele nacht proberen om een ​​iPhone en lijnen op te staan op een plek als deze? Zou het niet mooi zijn als de Apple Store waren stack datastructuur? Yay? Neen? Het is alleen maar goed voor de mensen die opdagen op de laatste minuut en dan krijg geplukt uit de wachtrij. En in feite, om het feit dat ik zo was geneigd te zeggen wachtrij is eigenlijk overeen met wat we zouden dit soort data structuur noemen, een in werkelijkheid waar de bestelling er wel toe doet, en u wilt dat de eerste in om als eerste een op al was het maar omwille van de menselijke rechtvaardigheid. We zullen over het algemeen noemen dat een wachtrij datastructuur. 

Het blijkt bovendien gelinkte lijsten, kunnen we beginnen met het gebruik van deze dezelfde basisideeën en beginnen nieuwe en verschillende oplossingen voor problemen. Bijvoorbeeld in het geval van een stapel kunnen we vormen een stapel met behulp van een data structuur als dit, zou ik voorstellen. In dit geval heb ik uitgeroepen tot een struct, en ik heb gezegd binnenkant van deze structuur is een reeks getallen en een variabele genaamd omvang en ik ga dit ding noemen een stapel. Nu, waarom dit eigenlijk? In het geval van een stapel, kon dit effectief tekenen op het scherm als een array. Hier is mijn stack. Dat zijn mijn nummers. En we trekken ze als dit, dit, dit, dit, dit. En dan heb ik een aantal andere gegevens-lid hier, die heet grootte, zodat dit formaat, en dit is nummers en gezamenlijk de gehele iPad hier vertegenwoordigt een stapel structuur. Nu, bij verstek, heeft grootte vermoedelijk moet worden geïnitialiseerd op 0, en wat er in de reeks van getallen in eerste instantie toen ik voor het eerst een array toe te wijzen? Garbage. Wie weet? En het maakt niet echt uit. Het maakt niet uit of dit 1, 2, 3, 4, 5, volledig willekeurig door pech opgeslagen in mijn structuur, want zolang ik weet dat de grootte van de stack 0 is, dan weet ik programmatisch, niet kijken naar een van de elementen in de array. Het maakt niet uit wat er staat. Kijk niet naar hen, zoals zou de implicatie van een grootte van 0. 

Maar stel nu ik ga je gang en steek iets in de stapel. Ik wil de nummer 5 invoegen, dus heb ik nummer 5 hier, en wat doe ik hier neer te zetten? Nu zou ik eigenlijk neergezet 1 voor de grootte, en nu de stapel moet van grootte 1. Wat als ik ga je gang en nummer, laten we zeggen, 7 next? Deze krijgt dan bijgewerkt tot en met 2, en dan zullen we doen 9, en dit wordt bijgewerkt tot 3. Maar het interessante functie nu van deze stapel is dat Ik moet welk element te verwijderen als ik wil knallen iets af van de stapel, om zo te zeggen? 9 zou het eerste ding om te gaan. Hoe moet de afbeelding veranderen als ik wil een element pop uit de stapel, Net als een lade in Mather? Ja. >> [Student] Setformaat naar 2. Precies, is alles wat ik doe ingesteld grootte tot 2, en wat moet ik doen met de array? Ik heb niets te doen. Ik kon, alleen maar om anaal, zet een 0 is er of een -1 of iets te betekenen dat dit niet een legit waarde, maar het maakt niet uit, omdat Ik kan opnemen buiten de array zelf hoelang deze zodat ik weet alleen kijken naar de eerste twee elementen in deze array. Nu, als ik ga en voeg de nummer 8 van deze array, maakt het plaatje hoe te veranderen nu? Dit wordt 8 en wordt dit 3. Ik ben het snijden van een paar bochten hier. Nu hebben we 5, 7, 8, en we zijn terug naar een grootte van 3. Dit is vrij eenvoudig te implementeren, maar wanneer gaan we dit ontwerp beslissing spijt van? Wanneer dingen beginnen te gaan heel erg mis? Ja. [Onverstaanbaar student reactie] Als u terug wilt gaan en het eerste element dat u zetten inch te krijgen 

Het blijkt hier ook al een stapel is een array onder de motorkap, deze data structuren die we hebben begonnen te praten over zijn ook algemeen bekend als abstracte gegevensstructuren, waarbij de manier waarop ze geïmplementeerd geheel terzijde. Een gegevensstructuur, zoals een stapel wordt verondersteld te ondersteuning toe te voegen operaties zoals push, die een lade duwt op de stack, en pop, die een element verwijdert uit de stapel, en dat is het. Als je aan iemand anders code die reeds geïmplementeerd downloaden dit ding heet een stapel, zou die persoon hebben geschreven slechts twee functies voor u, push en pop, wiens enige doel in het leven zou zijn om precies dat te doen. U of hem of haar, die geïmplementeerd dat programma zou zijn geweest volledig de een om te beslissen hoe te implementeren de semantiek van duwen en popping onder de motorkap of de functionaliteit van het duwen en popping. En ik heb een wat kortzichtige beslissing hier door het implementeren van mijn stack met deze eenvoudige datastructuur waarom? Wanneer gaat deze datastructuur pauze? Op welk punt moet ik een foutmelding wanneer de gebruiker vraagt ​​push, bijvoorbeeld? [Student] Als er geen ruimte meer. Precies, als er geen ruimte meer, als ik de capaciteit overschreden, die alle doppen omdat het suggereert dat het een soort van globale constante. Nou, dan ga ik gewoon te hebben om te zeggen: "Sorry, ik kan niet een andere waarde te duwen op de stapel, "net als in Mather. 

Op een gegeven moment, ze gaan om het bovenste deel van dat kastje te raken. Er is geen ruimte meer of capaciteit in de stapel, op welk punt er een soort van fout. Ze moeten het element zetten ergens anders, de lade ergens anders, of helemaal nergens. Nu, met een wachtrij, konden we implementeren een beetje anders. Een wachtrij is een beetje anders in dat er onder de motorkap, het kan worden toegepast als een array, maar waarom, in dit geval, stel ik voor om ook een hoofd element dat staat voor de kop van de lijst, de voorkant van de lijst, de eerste persoon in de rij bij de Apple Store, in aanvulling op maat? Waarom heb ik hier behoefte aan een extra stuk van de gegevens? Denk eens terug aan wat getallen is als ik getekend heb het als volgt. Stel dat dit is nu een wachtrij in plaats van een stapel, het verschil is-net als de Apple Store-wachtrij is eerlijk. De eerste lijn in het begin van de lijst, nummer 5 in dit geval hij of zij er eerst laten worden in de winkel. Laten we dat doen. Stel dat dit de toestand van mijn rij op dit moment in de tijd, nu en de Apple Store wordt geopend en de eerste persoon, nummer 5, wordt geleid in de winkel. Hoe kan ik nu de foto dat ik de eerste persoon afgemeld wachtrij aan de voorkant van de lijn? Wat is dat? >> [Student] Verander de wachtrij. Wijzig de kop, dus 5 verdwijnt. In werkelijkheid, het is alsof-de beste manier om dit te doen? In werkelijkheid, is het net alsof deze man verdwijnt. Wat zou nummer 7 doen in een echte winkel? Ze zou een grote stap voorwaarts. 

Maar wat hebben we weten te waarderen als het gaat om arrays en verplaatsen van dingen rond? Dat is een soort van een verspilling van je tijd, toch? Waarom doe je nou zo anaal als de eerste persoon zijn aan het begin van de lijn op fysiek het begin van het deel van geheugen? Dat is helemaal niet nodig. Waarom? Wat kon ik gewoon in plaats weet je nog? >> [Onverstaanbaar student reactie] Precies, kon ik alleen niet vergeten met deze aanvullende gegevens lid hoofd die nu de kop van de lijst is niet meer 0, wat was het een moment geleden. Nu is het eigenlijk de nummer 1. Op deze manier krijg ik een lichte optimalisatie. Gewoon omdat ik heb afgemeld wachtrij iemand van lijn aan het begin van de lijn bij de Apple Store betekent niet dat iedereen moet verschuiven, wat recall is een lineaire werking. Ik kan in plaats daarvan besteden constante tijd alleen en dan het bereiken van een veel snellere respons. Maar de prijs ik betaal is wat te winnen die extra prestaties en niet met iedereen te verschuiven? Ja. >> [Onverstaanbaar student reactie] Kunnen meer mensen, nou ja, dat probleem is orthogonaal aan het feit dat we niet mensen verschuiven rond. Het is nog steeds een array, dus of we iedereen verschuiven of niet- oh, ik zie wat je bedoelt, oke. Eigenlijk ben ik het eens met wat je zegt in dat het bijna alsof we nu nooit naar het begin van deze array meer gebruiken want als ik verwijderen 5, dan verwijder ik 7. Maar ik alleen zet mensen aan de rechterkant. 

Het voelt alsof ik verspilling van ruimte, en uiteindelijk mijn wachtrij uiteen in helemaal niets, dus we konden gewoon mensen wraparound, en we konden echt denken van deze array als een soort cirkelvormige structuur, maar we gebruiken wat operator in C om dat soort omhullend doen? [Onverstaanbaar student response] >> De modulo operator. Het zou een beetje vervelend om na te denken door middel van hoe doe je het wraparound doen, maar we konden doen, en we konden beginnen met het zetten van mensen op wat vroeger de voorkant van de lijn, maar we herinneren met deze kop variabele die het feitelijke hoofd van de lijn eigenlijk is. Wat als, in plaats daarvan, ons doel uiteindelijk, hoewel, was om nummers opzoeken, zoals we hier op het podium maakte met Anita, maar we willen echt het beste van al deze werelden? We willen meer verfijning dan array kunt omdat we de mogelijkheid om dynamisch te groeien de datastructuur willen. Maar we willen niet hun toevlucht moeten nemen tot iets dat we erop gewezen in de eerste lezing was niet optimaal algoritme, die van lineair zoeken. Het blijkt dat je in feite te bereiken, of in ieder geval dicht bij constante tijd, waarbij iemand als Anita, als ze configureert haar gegevens structuur niet aan een gekoppelde lijst te zijn, niet een stapel, niet aan een wachtrij, zou in feite komen met een datastructuur die het mogelijk maakt haar te zoeken dingen, zelfs woorden, niet alleen getallen, in wat we noemen constante tijd. 

En in feite vooruitkijken een van de psets in deze klasse is bijna altijd een implementatie van een spellingscontrole, waarbij geven wij u weer zo'n 150.000 woorden Engels en het doel is om laden die in het geheugen en snel in staat zijn om vragen van het formulier te beantwoorden wordt dit woord juist gespeld? En het zou echt slecht als je moest doorlopen alle 150.000 woorden om die te beantwoorden. Maar in feite, zullen we zien dat we dit kunnen doen in zeer, zeer snelle tijd. En het gaat om de uitvoering zoiets als een hash-tabel te betrekken, en hoewel op het eerste gezicht dit ding heet een hash-tabel gaat Laten we het bereiken van deze super snelle reactietijden, blijkt dat er in feite een probleem. Toen het tijd om dit ding-weer gebeld te implementeren komt, ik doe het nog eens. Ik ben de enige hier. Als het tijd is om de uitvoering van dit ding heet een hash table, We gaan te hebben om een ​​beslissing te nemen. Hoe groot moet dit ding eigenlijk? En als we beginnen met het plaatsen van getallen in deze hash-tabel, hoe gaan we om ze op te slaan op een zodanige wijze dat we ze terug te krijgen zo snel hebben we ze in? Maar we zullen zien het duurde niet lang dat deze vraag van wanneer iedereen jarig is in de klas zal heel germane. Het blijkt dat in deze kamer, we hebben een paar honderd mensen kregen, zodat de kans dat twee van ons hebben op dezelfde dag jarig is waarschijnlijk behoorlijk hoog. Wat als er slechts 40 van ons in deze kamer? Wat zijn de kansen van twee mensen die op dezelfde dag jarig? [Studenten] Meer dan 50%. Ja, meer dan 50%. Sterker nog, ik bracht zelfs een grafiek. Het blijkt-en dit is eigenlijk gewoon een sneak preview- als er slechts 58 van ons in deze kamer, de waarschijnlijkheid van ons 2 met op dezelfde dag jarig is enorm hoog, bijna 100%, en dat gaat een hele hoop pijn voor ons veroorzaken op woensdag. 

Met dat gezegd, laten we hier verdagen. We zien je op woensdag. [Applaus] [CS50.TV]