[Muziek] DAVID J. MALAN: Oke. Dit is CS50. Dit is week vijf voortgezet, en we heb goed nieuws en slecht nieuws. Dus goede nieuws is dat CS50 lanceert deze vrijdag. Als u graag om met ons mee, hoofd naar de gebruikelijke URL hier. Nog beter nieuws, geen lezing deze komende maandag de 13e. Iets minder beter nieuws, quiz nul is volgende week woensdag. Meer informatie kan worden vinden op deze URL hier. En in de komende paar dagen we zullen invuloefeningen met betrekking tot de kamers dat we hebben gereserveerd. Beter nieuws is dat er zal is een cursus-brede beoordeling sessie aanstaande Maandag in de avond. Blijf op de hoogte van de cursus website voor de locatie en details. Secties, hoewel het een vakantie, zal ook te ontmoeten. Beste nieuws, lezing volgende week vrijdag. Dus dit is een traditie die we hebben, zoals in de syllabus. Alleen-- het gaat geweldig zijn. Je zult dingen zoals te zien constante tijd datastructuren en hash tabellen en bomen en probeert. En we praten over verjaardag problemen. Een hele hoop dingen wacht volgende week vrijdag. OK. Hoe dan ook. Dus herinneren dat we geweest zijn gericht op deze foto van wat er binnenkant van het geheugen van onze computer. Dus geheugen of RAM is waar programma bestaan ​​terwijl je ze lopen. Als u dubbelklikt op een pictogram om een ​​aantal programma uit te voeren of dubbelklik op een pictogram om een ​​bestand te openen, het is geladen vanaf de vaste rijden of solid state drive in het RAM, Random Access Memory, waar het leeft, totdat de stroom wordt uitgeschakeld, de laptop deksel sluit, of je stopt het programma. 

Nu geheugen van die heb je waarschijnlijk 1 gigabyte deze dagen, 2 gigabytes, of zelfs veel meer, wordt algemeen ingedeeld voor een bepaald programma in dit soort rechthoekige conceptueel model waarbij we de stapel aan de onderkant en een heleboel andere dingen aan de top. Het ding op de top we hebben gezien op deze foto voordat, maar nooit over gesproken is de zogenaamde text segment. Tekstsegment is gewoon een mooie manier zeggen de nullen en enen die stel uw werkelijke gecompileerde programma. 

Dus wanneer u dubbelklikt op Microsoft Word op uw Mac of pc, of wanneer u dot draaien slash Mario op een Linux-computer op uw terminal venster, de nullen en enen dat componeren Word of Mario worden tijdelijk opgeslagen in het RAM-geheugen van uw computer in de zogenaamde tekstsegment voor een bepaald programma. Onder dat gaat geïnitialiseerd en uninitialized gegevens. Dit is dingen zoals globale variabelen, dat we niet veel van heb gebruikt, maar af en toe we hebben had globale variabelen of statisch gedefinieerde tekenreeksen die is hard gecodeerd woorden als "hello" die niet zijn opgenomen in door de gebruiker die zijn hard-coded in uw programma. 

Nu, op de bodem die we de zogenaamde stack. En de stapel, tot nu toe, we zijn geweest gebruik voor wat allerlei doeleinden? Wat is de stack gebruikt voor? Yeah? 

PUBLIEK: Functies. 

DAVID J. MALAN: Voor functies? In welke zin voor functies? 

PUBLIEK: Als u een functie aan te roepen, de argumenten worden gekopieerd op de stapel. 

DAVID J. MALAN: Precies. Wanneer u een functie aan te roepen, haar argumenten worden gekopieerd op de stapel. Dus elke X of Y of A of B's dat je voorbij in een functie worden tijdelijk in de de zogenaamde stack, net als een van de Annenberg eetzaal trays, en ook de dingen als lokale variabelen. Als uw foo functie of je swap functie lokale variabelen, zoals temp, die twee belanden op de stapel. Nu zullen we niet te veel over praten hen, maar deze omgevingsvariabelen aan de onderkant hebben we een tijdje geleden, toen zag Ik was gepruts bij het toetsenbord een dag en ik begon toegang dingen zoals argv 100 of argv 1000, net elements-- ik vergeet de numbers-- maar werden niet verondersteld te worden benaderd door mij. We begonnen met het zien van enkele funky symbolen op het beeldscherm. Dat waren zogenaamde omgevingsvariabelen zoals de algemene instellingen voor mijn programma of voor mijn computer, niet los van de recente bug die we besproken hebben, Shellshock, dat is al teistert een flink aantal computers. 

Nu ten slotte, in de focus van vandaag we uiteindelijk op de heap. Dit is een stuk geheugen. En fundamenteel al deze geheugen is hetzelfde spul. Het is dezelfde hardware. We zijn gewoon een soort van behandelen van verschillende clusters bytes voor verschillende doeleinden. De hoop wordt ook gaat worden, waar variabelen en het geheugen die u aanvraagt van het besturingssysteem tijdelijk wordt opgeslagen. 

Maar er is een soort van een probleem hier, als het beeld inhoudt. We soort hebben twee schepen over te botsen. Want als je meer en meer gebruik maken van van de stapel, en zoals we vandaag zien verder, als je meer en meer van de te gebruiken hoop, zeker slechte dingen kunnen gebeuren. En inderdaad, we kunnen veroorzaken dat al dan niet opzettelijk. Dus de laatste cliffhanger bedroeg dit programma, die geen functionele geserveerd hebben ander doel dan om aan te tonen hoe je als een bad guy eigenlijk kan nemen voordeel van bugs in programma iemands en de overname van een programma of zelfs een hele computer systeem of server. Dus gewoon een blik te werpen in het kort, je merken dat de belangrijkste op de bodem neemt in de command line argumenten, zoals per argv. En het heeft een oproep naar een functie f, wezen een naamloos functie genaamd f, en het is voorbij in argv [1]. 

Dus wat het woord van de gebruiker typt in bij de vraag achter de naam van dit programma, en dan is deze willekeurige functie op top, f, neemt in een string, AKA char *, als we begonnen te bespreken, en het gewoon noemt het "bar." Maar we konden het iets noemen. En dan verklaart, binnen of f, een reeks karakters riep c-- 12 dergelijke tekens. 

Nu, door het verhaal dat ik vertelde een moment geleden, waar in het geheugen is c, of zijn die 12 Chars gaat uiteindelijk? Even voor de duidelijkheid. Yeah? 

PUBLIEK: Op de stapel. 

DAVID J. Malan: Op de stapel. Dus c een lokale variabele. We vragen om 12 tekens of 12 bytes. Die gaan uiteindelijk op de zogenaamde stack. Nu eindelijk is deze andere functie dat is eigenlijk best handig, maar we hebben niet echt gebruikt het zelf, strncopy. Het betekent draad exemplaar, maar slechts n letters, n tekens. Zo n tekens zal zijn gekopieerd van de bar in de c. En hoeveel? De lengte van de bar. Dus met andere woorden, dat een regel, strncopy, gaat kopiëren effectief bar in te c. 

Nu, gewoon om soort te anticiperen de moraal van dit verhaal, wat is potentieel problematisch hier? Ook al zijn we het controleren van de lengte van de bar en het passeren van het in strncopy, wat is je darmen te vertellen is nog steeds kapot over dit programma? Yeah? 

PUBLIEK: Omvat niet ruimte voor het nul karakter. DAVID J. MALAN: Omvat niet ruimte voor het nul karakter. Potentieel tegenstelling tot praktijk van het verleden doen we niet eens hebben zo veel als een plus van 1 tot huisvesten die null karakter. Maar het is nog erger dan dat. Wat anders zijn we niet te doen? Yeah? 

PUBLIEK: [onverstaanbaar] DAVID J. MALAN: Perfect. We hebben hard coded 12 vrij willekeurig. Dat is niet zozeer de probleem, maar het feit dat we niet eens kijken of de lengte van de bar is minder dan 12, in welk geval het gaat worden veilig om het in het geheugen genaamd c die we hebben toegewezen. Immers, indien bar is als 20 tekens lang zijn, Deze functie lijkt te kopiëren 20 personages uit bar in c, waardoor waarbij ten minste 8 bytes dat het niet moet. Dat is de implicatie hier. 

Dus in het kort, gebroken programma. Niet zo'n big deal. Misschien krijg je een segmentation fault. We hebben allemaal wel bugs in programma's. We hebben allemaal kunnen bugs hebben in programma's op dit moment. Maar wat is de implicatie? Nou, hier is een ingezoomde versie van dat beeld van het geheugen van mijn computer. Dit is de bodem van mijn stack. En inderdaad, op de bodem is wat riep ouder routine stapel, mooie manier om om te zeggen dat is belangrijkste. Zo dat wie de functie genaamd f dat we het over hebben. Dit is de bodem van de stapel. Retouradres is iets nieuws. Het is er altijd geweest, altijd in dat beeld zijn. We belde nooit aandacht aan. Omdat blijkt hoe c werkt is dat wanneer een functie noemt een ander, niet alleen de argumenten aan functie krijgen geduwd op de stack, niet alleen lokaal de functie variabelen krijgen geduwd op de stack, zoiets als een retouradres Ook wordt gezet op de stapel. In het bijzonder, als belangrijkste oproepen foo, main's eigen adres in het geheugen, os iets, effectief wordt gezet op de stapel zodat wanneer f gebeurt uitvoeren hiervan weet waar om terug te springen in de tekst segment om te kunnen blijven uitvoeren. 

Dus als we hier conceptueel, in de belangrijkste, dan is f wordt aangeroepen. Hoe werkt f weten wie naar handbediening terug? Nou, deze kleine breadcrumb in rood hier, riep het retouradres, het is gewoon cheques, wat is dat retouradres? Oh, laat me terug naar de hoofdpagina te springen hier. En dat is een beetje van een oversimplificatie, omdat de nullen en enen voor de belangrijkste zijn technisch hier in de tech segment. Maar dat is het idee. f moet gewoon weten wat waar controle gaat uiteindelijk terug. 

Maar zoals computers hebben lang dingen aangelegd als lokale variabelen en argumenten is als dit. Dus in de top van deze afbeelding in blauw is de stack frame voor f, zodat alle van het geheugen dat f specifiek is gebruikt. Dus daarom, merken dat bar is op deze foto. Bar was zijn argument. En wij aangevoerd dat de argumenten om functies krijgen geduwd op de stack. En c, natuurlijk ook in dit plaatje. 

En net voor notationeel doeleinden, merken in de linker bovenhoek wordt wat zou c beugel 0 en vervolgens iets naar beneden naar rechts is c beugel 11. Dus met andere woorden, kun je je voorstellen dat er een raster van bytes daar eerste is linksboven, onder in die is de laatste van de 12 bytes. 

Maar nu proberen om vooruit te spoelen. Wat er gaat gebeuren als we passeren in een string bar dat is langer dan c? En we zijn niet te controleren of Het is inderdaad langer dan 12. Welk deel van deze foto gaat overschreven door bytes 0, 1, 2, 3, dot dot dot, 11, en vervolgens slecht, 12, 13 tot 19? Wat gaat er hier gebeuren, als je afleiden uit het bestelproces dat c beugel 0 is op de bovenste en c beugel 11 is een soort van naar beneden rechts? Yeah? 

PUBLIEK: Nou, het gaat aan de char * bar overschrijven. 

DAVID J. MALAN: Ja, het lijkt erop dat je gaat naar char * bar overschrijven. En nog erger, als je in een hele lange sturen snaar, zou je zelfs overschrijven wat? Het retouradres. Die weer, is net als een breadcrumb om het programma waar vertellen om terug te gaan naar toen f gebeurt wordt genoemd. 

Dus wat slechteriken meestal doen is als ze over een programma komen dat ze zijn benieuwd of is exploiteerbare, buggy op een zodanige wijze dat hij kan nemen voordeel dat insect, zij over het algemeen niet krijgen dit recht de eerste keer. Ze beginnen gewoon verzenden, bijvoorbeeld, willekeurige tekenreeksen in uw programma, zowel op het toetsenbord, of eerlijk gezegd waarschijnlijk dat ze een klein programma schrijven om gewoon automatisch genereren van strijkers, en beginnen bonzen op uw programma door verzenden in veel verschillende ingangen bij verschillende lengtes. 

Zodra je het programma crasht, dat is een geweldig ding. Want het betekent dat hij of zij heeft ontdekt wat waarschijnlijk inderdaad een bug. En dan kunnen ze slimmer krijgen en zich te concentreren beginnen enger over hoe je die bug te exploiteren. In het bijzonder, wat hij of zij zou kunnen doen is, in het beste geval, hello. Geen big deal. Het is een string dat is kort genoeg. Maar wat als hij of zij stuurt, en we zullen het generaliseren als, aanval code-- dus nullen en degenen die dingen te doen zoals rm-rf, dat alles verwijderen van de harde schijf of spam versturen of andere manier de machine aan te vallen? 

Als elk van deze letters A gewoon vertegenwoordigt, conceptueel, aanval, aanval, aanval, aanval, een aantal slechte code dat iemand anders geschreven, maar als die persoon slim genoeg om niet alleen zijn allemaal voorzien van deze rm-RFS, maar ook zijn of haar laatste paar bytes is een nummer dat correspondeert het adres van zijn of haar eigen aanval code dat hij of zij in net voorbij door deze te voorzien op de prompt, u effectief kunt misleiden de computer in het opmerken wanneer f wordt gedaan uitvoeren, oh, het is tijd voor mij om te springen terug naar de rode retouradres. Maar omdat hij of zij heeft een of andere manier overlapt dat retouradres met hun eigen nummer, en ze zijn slim genoeg te hebben geconfigureerd dat nummer te verwijzen, zoals u zien in de super top linkerhoek er, het actuele adres van de computer herinnering van sommige aanval code, een bad guy kan de computer te misleiden in het uitvoeren van zijn of haar eigen code. 

En die code, nogmaals, kan van alles zijn. Het wordt over het algemeen genoemd shell code, dat is gewoon een manier om te zeggen dat het niet over het algemeen iets eenvoudigs als rm-rf. Het is eigenlijk zoiets als Bash, of een echte programma geeft hem of haar programmatische controle uit te voeren iets anders dat ze willen. Dus in het kort, dit alles komt voort uit het simpele feit dat deze bug betrokken niet controleren de grenzen van de array. En omdat de manier computers werk dat zij Gebruik de stapel uit effectief, conceptueel, bottom up op, maar dan is de elementen u op de stapel te duwen groeien boven naar beneden, Dit is ongelooflijk problematisch. Nu, er zijn manieren om te werken rond dit. En eerlijk gezegd, er zijn talen om mee te werken rond dit. Java immuun bijvoorbeeld om deze specifieke kwestie. Omdat ze niet geven u tips. Ze geven je niet directe geheugenadressen. Dus met deze kracht die we hebben om iets aan te raken in het geheugen We willen komt, toegegeven, een groot risico. 

Dus houd een oogje in het zeil. Als, eerlijk gezegd, in de maanden of de komende jaren, op elk moment je leest over enkele uitbuiting van een programma of een server, als je ooit een hint van iets te zien als een buffer overflow aanval, of stack overflow is een ander type van de aanval, in dezelfde geest, zoveel inspireert de website te noemen, als je het weet, het is allemaal over slechts overlopen de omvang van sommige karakter matrix of een matrix algemeen. Heeft u vragen, dan, op deze? Probeer dit niet thuis. 

Oke. Dus malloc tot nu toe heeft onze nieuwe geweest vriend in dat we kunnen geheugen toe te wijzen dat we niet per se te weten in vooruit dat we willen, zodat we niet hebben hard code in onze programmanummers zoals 12. Zodra de gebruiker vertelt ons hoeveel gegevens die hij of zij wil ingang, kunnen we dat veel geheugen malloc. 

Dus malloc zo blijkt, naar de zover wij dat al het gebruik ervan, expliciet de vorige keer, en dan Jullie zijn met behulp van het voor getString onbewust voor enkele weken, het hele geheugen malloc's komt van de zogenaamde heap. En daarom getString bijvoorbeeld dynamisch geheugen toe te wijzen zonder te weten wat je bent gaan om te typen op voorhand, geef je terug een pointer naar dat geheugen, en dat geheugen is nog steeds van jou te houden, zelfs na getString rendement. Omdat recall na al dat de stack is voortdurend op en neer, op en neer. En zodra het gaat neer, dat betekent dat alle vormen van geheugen deze functie gebruikt moet niet gebruikt worden door iemand anders. Het is nu vuilnis waarden. 

Maar de hoop is hier boven. En wat is er leuk aan malloc is dat wanneer malloc wijst geheugen hier, het is niet beïnvloed, want de hoofdzaak door de stack. En dus elke functie kan toegang geheugen dat is malloc'd, zelfs door een functie als getString, zelfs nadat het is geretourneerd. 

Nu is het omgekeerde van malloc is gratis. En inderdaad, de regel die u moeten beginnen met het goedkeuren is elke, elke, elke keer dat je malloc gebruiken je moet zelf gebruik maken van gratis, uiteindelijk, op dezelfde pointer. Al die tijd hebben we het schrijven van buggy, buggy code, om vele redenen. Maar een van die is met de CS50 bibliotheek, die zelf bewust buggy, het lekt geheugen. Elke keer dat je getString moeten bellen de afgelopen weken we de operationele vragen systeem, Linux, voor het geheugen. En je hebt nooit het ooit teruggegeven. Dit is niet in oefenen, een goede zaak. 

En Valgrind, een van de gereedschappen geïntroduceerd in Pset 4, is alles over u te helpen nu vinden bugs als dat. Maar gelukkig voor Pset 4 je niet nodig hebt de CS50 bibliotheek of getString gebruiken. Dus bugs met betrekking tot het geheugen zijn uiteindelijk gaat om uw eigen zijn. 

Dus malloc is meer dan alleen geschikt voor dit doel. We kunnen eigenlijk nu op te lossen fundamenteel verschillende problemen, en fundamenteel problemen meer effectief per week zero's belofte. Tot nu toe is dit de meest sexy datastructuur die we hebben gehad. En door datastructuur ik bedoel een manier van het conceptualiseren van het geheugen op een manier die verder gaat dan alleen maar te zeggen, Dit is een int, dit is een char. We kunnen samen gaan cluster dingen. 

Dus een scala leek dit. En wat sleutel in ongeveer een was array is dat het je geeft back-to-back brokken geheugen, die elk gaat van hetzelfde type zijn, int, int, int, int of char, char, char, char. Maar er zijn een paar nadelen. Dit is bijvoorbeeld een array van grootte zes. Stel dat je deze array te vullen met zes nummers en dan, om wat voor reden, je gebruiker wil geven je een zevende nummer. Waar haal je het? 

Wat is de oplossing als u creëerde een matrix op de stack, bijvoorbeeld alleen met de week twee notatie die we geïntroduceerd, van vierkante haken met een aantal binnen? Nou, je hebt zes nummers in deze vakken. Wat zou je instinct zijn? Waar zou je het wilt zetten? 

PUBLIEK: [onverstaanbaar] 

DAVID J. MALAN: Sorry? 

PUBLIEK: Zet het op het einde. 

DAVID J. MALAN: Zet het op het einde. Dus naar rechts, buiten dit vak. Dat zou leuk zijn, maar het blijkt dat je dat niet kan doen. Want als je niet hebt gevraagd dit stuk geheugen, het zou kunnen zijn door het toeval dat deze wordt gebruikt door een andere variabele helemaal. Denk terug een week of zo toen we gelegd uit Zamyla en Davin en Gabe's namen in het geheugen. Ze waren letterlijk rug aan rug aan rug. Dat kunnen wij ook niet per se vertrouwen dat wat de hier is beschikbaar voor mij om te gebruiken. 

Dus wat zou je doen? Nou, als je eenmaal het realiseren moet een array van grootte zeven, kon je gewoon zorgen voor een waaier van grootte zeven gebruik dan een lus of een while loop, kopiëren naar de nieuwe matrix, en dan een of andere manier gewoon te ontdoen van deze array of gewoon stoppen met het gebruik. Maar dat is niet bijzonder efficiënt. Kortom, arrays niet laten u dynamisch wijzigen. 

Dus aan de ene kant krijg je random access, die is geweldig. Omdat het laat ons dingen doen als verdeel en heers, binary search, die we hebben sprak over op het scherm hier. Maar u zelf te schilderen in een hoek. Zodra je raken het einde van de array, je moet een zeer doen dure operatie of schrijf er een hele hoop code om nu te gaan met dat probleem. 

Dus wat als we in plaats daarvan hadden zoiets als een lijst, of een gekoppelde lijst name? Wat als in plaats van het hebben van rechthoeken back to back to back, we rechthoeken die iets reactie beetje speelruimte tussen hen? En ook al heb ik dit getekend foto of aangepast deze foto ve van de teksten hier terug te rug aan rug zeer ordelijk, in werkelijkheid, een van deze rechthoeken kan hier in het geheugen zijn. Een van hen kon hier te worden weergegeven. Een van hen kon hier up te zijn, hier, enzovoort. 

Maar wat als we trokken, in dit geval pijlen dat een of andere manier verwijzen deze rechthoeken bij elkaar? Inderdaad, we hebben een technisch gezien incarnatie van een pijl. Wat hebben we in de afgelopen dagen dat, onder de motorkap, representeert een pijl? Een wijzer, toch? 

Dus wat als, in plaats van alleen het opslaan van de nummers, zoals 9, 17, 22, 26, 34, wat als we niet opgeslagen slechts enkele maar een pointer naast elk dergelijk nummer? Zodat veel als je een zou rijgen naald door een hele hoop stof, een of andere manier koppelverkoop dingen samen, eveneens kan we met pointers, zoals geïncarneerd door pijlen hier, soort bij elkaar te weven deze individuele rechthoeken door het effectief gebruik van een pointer naast elk nummer dat wijst op een aantal volgende nummer, dat wijst op zijn beurt een volgende nummer? Dus in andere woorden, wat als we eigenlijk wilden om iets als dit te implementeren? Wel Helaas deze rechthoeken, ten minste een met 9, 17, 22, enzovoort, die niet langer mooie pleinen met enkele nummers. De bodem, rechthoek 9 hieronder bijvoorbeeld vertegenwoordigt wat moet een pointer, 32 bits. Nu, ik ben nog niet op de hoogte van elk type data in C, dat geeft je niet alleen een int maar een pointer geheel. 

Dus wat is de oplossing als we willen om ons eigen antwoord op deze uitvinden? Yeah? 

PUBLIEK: [onverstaanbaar] 

DAVID J. MALAN: Wat is dat? 

PUBLIEK: Nieuwe structuur. 

DAVID J. MALAN: Ja, dus waarom gaan we niet een nieuwe structuur, of C, een struct? We hebben eerder gezien structuren, zo kort, waar we mee met een student structuur als deze, die een naam en een huis had. In Pset 3 breakout u gebruik gemaakt van een geheel stelletje structs-- GRect en GOvals dat Stanford gemaakt om cluster informatie bij elkaar. Dus wat als we dit zelfde idee van de keywords "typedef" en "structuur" en dan nog wat student-specifieke dingen, en evolueren deze in de volgende: typedef struct node-- en knooppunt slechts een zeer generiek computer science term iets in een gegevensstructuur, een houder in een gegevensstructuur. Een knooppunt Ik claim zal hebben een int n, helemaal recht door zee, en dan een beetje meer cryptisch, deze tweede lijn, struct knoop * volgende. Maar in minder technische termen, wat dat tweede regel van code binnen de accolades? Yeah? 

PUBLIEK: [onverstaanbaar] DAVID J. MALAN: A pointer naar een ander knooppunt. Dus inderdaad, de syntax een beetje cryptisch. Maar als je het letterlijk leest, naast de naam van een variabele. Wat is het gegevenstype? Het is een beetje verbose deze tijd, maar het is van het type struct knoop *. Elke keer dat we iets ster gezien, dat betekent dat het een pointer naar dat soort gegevens. Dus de volgende is blijkbaar een pointer naar een struct knoop. 

Nu, wat is een struct knoop? Nou, let zie je die Dezelfde woorden rechtsboven. En inderdaad, je ziet ook het woord "Knooppunt" hier beneden in de linkerbenedenhoek. En dit is eigenlijk gewoon een gemak. Merk op dat in onze student definitie daar is het woord "student" slechts een keer. En dat komt omdat een student object was niet zichzelf verwijst. Er is niets binnenkant van een student dat moet verwijzen naar een andere student, persay. Dat zou een soort van zijn raar in de echte wereld. 

Maar met een knooppunt in een gekoppelde lijst, we willen wel een knooppunt te zijn referentiële een soortgelijk voorwerp. En zo ziet de verandering is hier niet gewoon wat er binnen de accolades. Maar wij voegen het woord "knooppunt" boven en toe te voegen aan de bodem in plaats van "student." En dit is slechts een technisch detail zo dat, nogmaals, je datastructuur kan zelf-referentiële, zodat een knooppunt kan wijzen aan een andere knoop. 

Dus wat is dit uiteindelijk gaat betekenen voor ons? Nou ja, een, dit spul binnen is de inhoud van onze knooppunt. Dit ding hier, rechtsboven, is gewoon zo dat, opnieuw, kunnen we verwijzen naar onszelf. En dan de buitenste spul, ook al is het knooppunt is een nieuwe term, misschien, het is nog steeds de hetzelfde als student en wat was onder de motorkap in de SPL. 

Dus als we wilden nu beginnen uitvoering van deze gelinkte lijst, hoe kunnen we vertalen iets als dit te coderen? Nou, laten we zien enkel een voorbeeld van een programma dat eigenlijk maakt gebruik van een gelinkte lijst. Onder de huidige verdeelsleutel is een programma genaamd Lijst Nul. En als ik dit run heb ik een super eenvoudige GUI, Graphical User Interface, maar het is echt gewoon printf. En nu heb ik mezelf een paar menu gegeven options-- Delete, Insert, Zoeken, en Traverse. En Quit. Dit zijn slechts gemeenschappelijke operaties op een datastructuur die bekend staat als een link lijst. 

Nu, Verwijderen gaat een nummer uit de lijst te verwijderen. Invoegen gaat voegen een nummer aan de lijst. Zoeken is gaan kijken voor nummer in de lijst. En traverse is gewoon een mooie manier van te zeggen, loop door de lijst, print het uit, maar dat is het. Doe het niet veranderen in any way. 

Dus laten we dit proberen. Laten we verder gaan en type 2. En dan ga ik nummer, zeggen 9. Enter. En nu mijn programma is gewoon geprogrammeerd zeggen lijst is nu 9. Nu, als ik ga je gang en denk opnieuw invoegen, laat mij ga je gang en uit te zoomen en typ in 17. Nu is mijn lijst is 9, dan 17. Als ik weer in te voegen, laten we slaan een. In plaats van 22, zoals in de foto we hebben gekeken naar hier, laat me springen vooruit en plaats 26 volgende. Dus ik ga om te typen 26. De lijst is als ik verwacht. Maar nu, alleen maar om te zien of deze code gaat om flexibel te zijn, laat me nu type 22, dat ten minste conceptueel, als we Het houden van dit opgelost, dat is inderdaad gaat nog een doelpunt op dit moment zijn, moet gaan tussen de 17 en 26. Dus ik druk op Enter. Inderdaad, dat werkt. En dus nu laat ik steek de laatste, per de foto, 34. 

Oke. Dus voor nu laat ik bepalen dat Verwijderen en Traverse en zoeken te doen, in feite werken. In feite, als ik lopen zoeken, laten we zoeken naar het nummer 22, Enter. Het vond 22. Dus dat is wat dit programma Lijst Nul doet. 

Maar wat er werkelijk gaande is Op dat implementeert dit? Nou, ten eerste ik zou kunnen hebben, en inderdaad Ik heb wel een bestand genaamd list0.h. En ergens is er dit lijn, typedef, struct knoop, dan heb ik mijn accolades, int n, en dan struct-- wat was de definitie? Struct knooppunt volgende. Dus moeten we de ster. Nu technisch gezien komen we in de gewoonte om hier tekenen het. Je zou leerboeken zien en keer gevonden doe het daar. Het is functioneel equivalent. In feite is dit wat typischer. Maar ik zal in overeenstemming met wat zijn we hebben de laatste tijd en doe dit. En dan tot slot, ik ga dit doen. 

Dus in een header file ergens, in list0.h vandaag de dag is dit struct definitie, en misschien nog enkele andere dingen. Ondertussen in list0c er gaan een paar dingen zijn. Maar we gaan gewoon starten en deze niet af te maken. List0.h is een bestand dat ik wil op te nemen in mijn C-bestand. En dan op een gegeven moment ben ik gaat int hebben, belangrijkste, ongeldig maken. En dan ga ik hebben een aantal te-doen is hier. Ik ga ook een hebben prototype, zoals leegte, zoeken, int, n, waarvan het doel in het leven is om te zoeken naar een element. En dan hier beneden Ik claim in de huidige code, leegte, zoeken, int, n, geen komma, maar open accolades. En nu wil ik een of andere manier te zoeken Een element in deze lijst. Maar we hebben niet genoeg informatie op het scherm nog niet. Ik heb eigenlijk niet vertegenwoordigde de lijst zelf. Dus een manier waarop we kunnen implementeren een gekoppelde lijst een programma is wil ik soort van om iets te doen zoals verklaren gelinkte lijst hierboven. Voor de eenvoud ga ik maken deze wereldwijde, hoewel in het algemeen hebben we moet dit niet te veel doen. Maar dit voorbeeld vereenvoudigd. Dus ik wil verklaren een gekoppelde hier om de lijst up. Nu, hoe kan ik dat doen? 

Hier is de foto van een gelinkte lijst. En ik niet echt momenteel weten hoe Ik ga om te gaan over wat neerkomt zo veel dingen met slechts een variabele in het geheugen. Maar denk terug een moment. Al die tijd die we hebben gehad strings, die we vervolgens geopenbaard aan arrays zijn van personages, die we vervolgens geopenbaard aan slechts een pointer om het eerste teken in een array karakters dat is beëindigd met null. Dus tegen die logica en daardoor foto soort van zaaien je gedachten, wat moeten we eigenlijk schrijven in ons code om een ​​gekoppelde lijst vertegenwoordigen? Hoeveel van deze informatie hebben we nodig vast te leggen in de C-code, zou je dan zeggen? Yeah? 

PUBLIEK: We hebben een pointer naar een knooppunt. DAVID J. MALAN: Een pointer naar een knooppunt. Vooral dat knooppunt zou je instincten zijn om een ​​pointer te houden? 

Publiek: Het eerste knooppunt. 

DAVID J. MALAN: Ja, waarschijnlijk gewoon de eerste. En merk op, de eerste knooppunt een andere vorm. Het is slechts de helft van de grootte van de structuur, omdat het immers maar een pointer. Dus wat je wel kunt doen is te verklaren een gelinkte lijst te zijn van het type knooppunt *. En laten we eerst het noemen en initialiseren op nul. Dus null, nogmaals, is komen in de foto hier. Niet alleen wordt null gebruikt als als een speciale return waarde voor dingen als getString en malloc, null is ook de nul pointer, het ontbreken van een pointer, als je wil. Het betekent gewoon dat er niets is nog hier. Nu eerst, ik had kunnen noemde dit alles. Ik kon het hebben genoemd "lijst" of een aantal andere zaken. Maar ik doe het bellen "eerste", zodat deze lijn staat met deze foto. Dus net als een string kan worden weergegeven met het adres van de eerste byte, zo kan een gelinkte lijst. En we zullen zien andere data structuren worden vertegenwoordigd met slechts een wijzer, een 32-bits pijl, wijzend op het eerste knooppunt in de structuur. 

Maar laten we nu anticiperen op een probleem. Als ik alleen herinneren in mijn programma het adres van het eerste knooppunt, de eerste rechthoek in deze datastructuur, wat had beter de zaak over de te uitvoering van de rest van mijn lijst? Wat is een belangrijk detail dat gaat te zorgen dat dit echt werkt? En met "echt werkt" Ik betekenen, zoals een koord, laat ons gaan van het eerste teken in Davin's naam aan de tweede, de derde, de vierde, aan het einde, hoe weten we wanneer we aan het eind van een gelinkte lijst die er zo uitziet? Wanneer het is null. En ik heb dit soort als vertegenwoordigd zoals een elektrisch ingenieur macht, met de kleine aarding symbool, van soorten. Maar dat betekent nul in dit geval. U kunt het tekenen elk nummer manieren, maar deze auteur is er gebeurd met dit symbool gebruiken hier. 

Zolang we rijgen al deze knooppunten samen, alleen herinneren waar de eerste is, zolang als we een speciaal symbool op het laatste knooppunt in de lijst, en we zullen gebruiken null, want dat is wat we tot onze beschikking, deze lijst compleet is. En al is het maar ik geef je een pointer naar het eerste element, u, de programmeur, zeker in de rest ervan. Maar laten we laat uw gedachten dwalen een beetje, als ze niet al heel wandered-- wat is naar de looptijd zijn van iets in deze lijst vinden? Verdomme, het is big O van n, dat is niet slecht, in alle eerlijkheid. Maar het is lineair. We hebben op wat functie gegeven arrays door meer te bewegen in de richting van deze foto van dynamisch verweven en verbonden knopen? We hebben opgegeven random access. Een array is leuk omdat mathematisch alles is rug aan rug aan rug aan rug. Hoewel deze foto ziet er mooi, en zelfs maar het lijkt erop dat deze knooppunten zijn mooi afstand van elkaar, in werkelijkheid ze kan overal zijn. OX1, Ox50, Ox123, Ox99, deze knooppunten kan overal zijn. Omdat malloc doet geheugen toewijzen van de hoop, maar overal in de heap. Je hoeft niet per se weten dat het ga terug naar back to back. En dus is deze foto in werkelijkheid is niet van plan heel dit mooi zijn. 

Dus het gaat om een ​​beetje van te nemen werken om deze functie uit te voeren. Dus laten we zoekopdracht uit te voeren nu. En we zien wel een soort van een slimme manier om dit te doen. Dus als ik een zoekfunctie en Ik kreeg een variabele, integer n te zoeken, ik moet het weten nieuwe syntax voor het kijken van binnen of een structuur die wees aan n vinden. Dus laten we dit doen. 

Dus eerst ga ik om te gaan vooruit en verklaren een knooppunt *. En ik ga het ook noemen wijzer, gewoon volgens afspraak. En ik ga het initialiseren naar eerste. En nu kan ik dit doen in een aantal manieren. Maar ik ga naar een gemeenschappelijke aanpak. Hoewel pointer is niet gelijk null, en dat is geldig syntax. En het betekent gewoon het volgende doen, dus Zolang je niet te wijzen op niets. Wat wil ik doen? 

Als wijzer dot n, laat me terug te komen om dat, gelijk aan equals-- wat? Welke waarde moet ik naar zoeken? De werkelijke n dat werd aangenomen in. Dus hier is een andere functie van C en vele talen. Hoewel de structuur die knooppunt n heeft een waarde, volledig gewettigd ook een lokaal argument of variabele genoemd n. Want ook wij, met menselijk oog kan onderscheiden dat dit n vermoedelijk verschillend van deze n. Omdat de syntax is anders. Je hebt een punt en een pointer gekregen, terwijl deze heeft niet zoiets. Dus dit is OK. Dat is OK ze dezelfde dingen te noemen. 

Als ik u dit vinden, ben ik gaat te willen om iets te doen zoals aankondigen dat we gevonden n. En we laten dat als een reageren of pseudo-code. Anders, en hier is de interessante deel, wat doen wat ik wil doen als het huidige knooppunt is niet met n dat ik de zorg over? Hoe krijg ik het volgende te bereiken? Als mijn vinger naar de Momenteel is PTR, en het is wijzend op wat eerste wijst op, hoe kan ik mijn vinger bewegen naar de volgende knoop in code? Nou ja, wat is de breadcrumb we zal volgen in dit geval? PUBLIEK: [onverstaanbaar]. DAVID J. MALAN: Ja, dus naast. Dus als ik ga terug naar mijn code hier, inderdaad, ik ben ga je gang gaan en zeggen wijzer, die is slechts een tijdelijke variable-- het is een rare naam, ptr, maar het is net als temp-- Ik ga aanwijzer instellen gelijk aan wat wijzer is-- en nogmaals, dit gaat om een ​​te zijn kleine buggy voor een moment-- stip. Met andere woorden, ga ik neem mijn vinger die is te wijzen op dit knooppunt hier en ik ga zeggen, weet je wat, neem een ​​kijkje op het volgende veld en beweeg uw vinger naar wat het ook is wijzend op. En dit gaat herhalen, herhalen, herhalen. Maar wanneer komt mijn vinger stop helemaal niets doen? Zodra welke regel code kicks in? PUBLIEK: [onverstaanbaar] DAVID J. MALAN: Als punt terwijl pointer is niet gelijk aan nul. Op een gegeven moment mijn vinger's gaat worden wijzend op null en ik ga om te beseffen dat is het einde van deze lijst. Nu is dit een beetje leugentje om bestwil voor eenvoud. Het blijkt dat, hoewel we net geleerd dit dot notatie voor structuren, wijzer is geen structuur. ptr is wat? Gewoon om meer nitpicky zijn. Het is een pointer naar een knooppunt. Het is niet een node zelf. Als ik had geen ster hier, wijzer absolutely-- het is een knooppunt. Dit is net als een week verklaring van een variabele, hoewel het woord "knooppunt" is nieuw. 

Maar zodra we de invoering van een ster, het is nu een pointer naar een knooppunt. En helaas kan je niet gebruiken de puntnotatie een pointer. Je moet de pijl te gebruiken notatie, die opvallend, is de eerste keer dat een stuk van syntax ziet er intuïtief. Dit ziet er letterlijk als een pijl. En dus dat is een goede zaak. En hier beneden letterlijk ziet eruit als een pijl. Dus ik denk dat dat de la-- ik niet denk dat ik over-plegen hier-- I denk dat dat de laatste nieuwe stuk van syntax we zullen gaan zien. En gelukkig, het is inderdaad wat intuïtiever. 

Nu, voor degenen onder u die zou de oude manier wilt, kunt u nog steeds gebruik maken van de dot-notatie. Maar als per maandag gesprek, we eerst nodig hebt om er naartoe te gaan, naar die aan te pakken, en vervolgens toegang tot het gebied. Dus dit is ook correct. En eerlijk gezegd, dit is een beetje pedant. Je bent letterlijk zeggen, dereferentie de wijzer en ga daar. Grijp dan .n, het veld met de naam n. Maar eerlijk gezegd, niemand wil te typen of te lezen dit. En zo de wereld uitgevonden de pijl notatie die gelijk, identiek, het is gewoon syntactische suiker. Dus een mooie manier om dit te zeggen ziet er beter uit, of ziet er eenvoudiger. 

Dus nu ga ik een ander ding te doen. Ik ga zeggen "break" zodra ik heb vond het zo ik niet blijven kijken naar het. Maar dit is de kern van een zoekfunctie. Maar het is een stuk makkelijker, in de einde, niet te lopen door de code. Dit is inderdaad de formele implementatie van de zoekopdracht in de huidige verdeelsleutel. Ik durf te zeggen dat de insert is niet bijzonder leuk om te lopen door visueel, noch is te verwijderen, zelfs maar aan het eind van de dag ze neer op tamelijk eenvoudige heuristiek. 

Dus laten we dit doen. Als u zult humor me hier, ik deed brengen een heleboel stress ballen. Ik bracht een heleboel getallen. En konden we slechts een paar vrijwilligers te vertegenwoordigen 9, 17, 20, 22, 29 en 34? Dus in wezen iedereen wie we hier vandaag. Dat was een, twee, drie, vier, vijf, zes personen. En ik ben gevraagd om gaan-- zien, geen een aan de achterkant verhoogt hun handen. OK, een, twee, drie, vier, five-- laat me laden balance-- zes. OK, je zes komen op maximaal. We zullen andere mensen nodig. We brachten extra stress ballen. En als je zou kunnen, voor slechts een moment, lijn jezelf omhoog enkel graag deze foto hier. 

Oke. Laten we eens kijken, wat is uw naam? 

PUBLIEK: Andrew. 

DAVID J. MALAN: Andrew, je bent nummer 9. Leuk je te ontmoeten. Hier ga je. PUBLIEK: Jen. DAVID J. MALAN: Jen. David. Nummer 17. Ja? 

Publiek: Ik ben Julia. 

DAVID J. MALAN: Julia, David. Nummer 20. PUBLIEK: Christian. DAVID J. MALAN: Christian, David. Nummer 22. En? 

PUBLIEK: JP. DAVID J. MALAN: JP. Nummer 29. Dus ga je gang en krijg in-- Uh oh. Uh oh. Standby. 20. Heeft iemand een marker? PUBLIEK: Ik heb een Sharpie. DAVID J. MALAN: Je hebt een Sharpie? OK. En heeft iemand een stuk papier? Sla de lezing. Kom op. PUBLIEK: We hebben het. DAVID J. MALAN: We got it? Oke, dank je wel. Hier gaan we. Was dit van u? Je redde net de dag. So 29. Oke. Ik verkeerd gespeld 29, maar OK. Ga je gang. Oke, ik geef je je pen even terug. Dus hebben we deze mensen hier. Laten we eens een andere. Gabe, wil je spelen het eerste element hier? We zullen je nodig hebt om te wijzen bij deze fijne mensen. Dus 9, 17, 20, 22, sorteren van 29, en dan 34. Hebben we iemand verliezen? Ik heb wel een 34. Waar did-- OK, wie wil zijn 34? OK, kom op, 34. Oke, dit zal de moeite waard om de climax. Wat is je naam? 

PUBLIEK: Peter. 

DAVID J. MALAN: Peter, kom op. Oke, dus hier is een hele hoop van knooppunten. Ieder van jullie is een van deze rechthoeken. En Gabe, het enigszins vreemd man uit, vertegenwoordigt eerste. Dus zijn pointer is een beetje kleiner op het scherm dan iedereen anders. En in dit geval, elk van uw linkerhand handen gaat ofwel naar beneden wijzen, waardoor die null, dus maar het ontbreken van een pointer, of het gaat om te wijzen op een knooppunt naast je. 

Dus nu als je sieren jezelf als het beeld hier, ga je gang en punt naar elkaar, met Gabe in het bijzonder richten op nummer 9 naar de lijst vertegenwoordigen. OK, en nummer 34, je linkerhand moet gewoon worden wijzend op de vloer. 

OK, dus dit is de gelinkte lijst. Dit is het scenario betrokken. En inderdaad, dit is representatief een categorie problemen dat je zou kunnen proberen op te lossen met een code. Je wilt uiteindelijk voegen Een nieuw element in de lijst. In dit geval gaan we probeer het plaatsen van de nummer 55. Maar er gaat worden verschillende gevallen te overwegen. En inderdaad, dit gaat om een ​​te zijn van de big-picture afhaalrestaurants hier is, wat zijn de verschillende gevallen. Wat zijn de verschillende als voorwaarden of takken die het programma zou kunnen hebben? 

Nou, het nummer dat u probeert te insert, waarvan we nu weten zijn 55, maar als je het niet wist van tevoren, ik durf te zeggen valt in ten minste drie situaties. Waar zou een nieuw element zijn? PUBLIEK: En het einde of in het midden. DAVID J. MALAN: Aan het einde in het midden of aan het begin. Dus ik beweren dat er op zijn minst drie problemen die we moeten oplossen. Laten we kiezen wat het misschien misschien wel de eenvoudigste men, wanneer het nieuwe element behoort bij het begin. Dus ik ga naar code vrij hebben zoals zoeken, wat ik net schreef. En ik ga PTR hebben, die Ik zal hier vertegenwoordig met mijn vinger, zoals gewoonlijk. 

En vergeet niet, welke waarde hebben we initialiseren ptr naar? Dus we geïnitialiseerd is om in eerste instantie null. Maar wat hebben we gedaan toen we binnen waren onze zoekfunctie? We stellen het gelijk aan de eerste, wat niet betekent dat dit te doen. Als ik ptr gelijk aan de eerste, wat moet mijn hand echt te wijzen op? Rechts. Dus als Gabe en ik gaan gelijke waarden hier zijn, we nodig hebben om zowel punt op nummer 9. 

Dus dit was het begin van ons verhaal. En nu dit is gewoon rechttoe rechtaan, ook al is de syntax is nieuw. Conceptueel is dit gewoon lineair zoeken. 55 is gelijk aan 9? Of liever gezegd, laten we minder dan 9 zeggen. Want ik ben op zoek naar achterhalen waar te 55 zetten. Minder dan 9, minder dan 17, minder dan 20, minder dan 22, minder dan 29, minder dan 34, nee. Dus nu zijn we in het geval een van ten minste drie. 

Als ik hier wil invoegen 55 over, wat regels code nodig om geëxecuteerd? Hoe werkt deze foto van mensen moeten veranderen? Wat doe ik met mijn linkerhand? Dit moet in eerste instantie nul zijn, want ik ben aan het einde van de lijst. En wat er moet gebeuren hier samen met Peter, was het? Hij is duidelijk gaat wijzen naar mij. Dus ik beweer dat er ten minste twee lijnen van code in de voorbeeldcode van vandaag dat gaat om dit te implementeren scenario van het toevoegen van 55 aan de staart. En mag ik iemand hop up en slechts 55 voor? Oke, jij bent de nieuwe 55. 

Dus wat nu als de volgende scenario komt langs, en we willen voegen aan de begin of het hoofd van deze lijst? En wat is je naam, nummer 55? 

PUBLIEK: Jack. 

DAVID J. MALAN: Jack? OK, leuk je te ontmoeten. Welkom aan boord. Dus nu gaan we naar invoegen, bijvoorbeeld het getal 5. Hier is het tweede geval van de drie kwamen we met voorheen. Dus als 5 behoort bij het begin, laten we eens kijken hoe we dat te weten komen. Ik initialiseren mijn ptr pointer naar nummer 9 weer. En ik realiseerde me, oh, 5 minder dan 9. Dus fix dit beeld voor ons. Wiens handen, Gabe's of David's of-- wat is nummer 9 van de naam? 

PUBLIEK: Jen. 

DAVID J. MALAN: Jen's hands-- die van onze handen moeten veranderen? OK, dus Gabe wijst naar wat nu? Bij mij. Ik ben het nieuwe knooppunt. Dus ik zal gewoon een soort van verhuizing hier om het visueel te zien. En ondertussen wat doe ik dat punt? Nog steeds waar ik wijzen. Dus dat is het. Dus gewoon echt een regel code fixes deze specifieke kwestie, lijkt het. Oke, dus dat is goed. En kan iemand zijn placeholder voor 5? Kom maar naar boven. We halen je de volgende keer. 

Oke, dus nu-- en als een terzijde, de namen Ik ben niet het maken expliciet melding van het recht nu, pred wijzer, voorganger wijzer en pointer, dat alleen de namen van in de voorbeeldcode om de pointers of mijn handen dat soort is te wijzen rond. Wat is je naam? 

PUBLIEK: Christine. 

DAVID J. MALAN: Christine. Welkom aan boord. Oke, dus laten we eens kijken nu een iets vervelend scenario waarbij ik wil invoegen zoiets 26 in deze. 20? Wat? Deze zijn-- goed dat we hebben deze pen. Goed, 20. Als iemand een ander stuk van kon krijgen papier klaar, net op geval-- goed. Oh, interessant. Nou, dit is een voorbeeld van een lezing bug. OK dus wat heet je ook alweer? PUBLIEK: Julia. DAVID J. MALAN: Julia, kunt u pop uit en doen alsof je er nooit? OK, dit is nooit gebeurd. Dank je wel. Dus stel dat we willen invoegen Julia in deze gelinkte lijst. Zij is het getal 20. En natuurlijk is ze naar behoren bij de begin-- nog niets aan te wijzen. Dus je hand kan soort zijn beneden nul of een garbage waarde. Laten we zeggen de snelle verhaal. Ik wees naar nummer 5 dit keer. Dan check ik 9. Dan check ik 17. Dan check ik 22. En ik realiseer me, ooh, Julia moet gaan voor 22. Dus wat moet er gebeuren? Moeten wiens handen om te veranderen? Julia's, de mijne, of-- hoe heet je ook alweer? 

PUBLIEK: Christian. 

DAVID J. MALAN: christen of? 

PUBLIEK: Andy. 

DAVID J. MALAN: Andy. Christelijke of Andy? Moet Andy te wijzen op? Julia. Oke. Dus Andy, wil je wijzen op Julia? Maar wacht eens even. In het verhaal tot nu toe, Ik ben het soort van een de leiding, in de zin dat pointer is het ding dat is bewegen door de lijst. We zouden een naam voor Andy, maar er is geen variabele genaamd Andy. De enige andere variabele die we hebben is eerste, wie vertegenwoordigd door Gabe. 

Dus dit is eigenlijk daarom aldus toe hebben we dit niet nodig is. Maar nu op het scherm is er opnieuw te vermelden van pred pointer. Dus laat me explicieter. Als dit is wijzer, ik had beter een beetje intelligenter over mijn iteratie. Als je het niet erg vindt dat ik het gaan door hier weer, hier richten, hier wijzend. Maar laat me een pred wijzer, voorganger wijzer, dat is soort te wijzen op de element Ik was gewoon op. Dus als ik ga hier nu mijn linkerhand updates. Als ik ga hier mijn linkerhand updates. En nu heb ik niet alleen een verwijzing naar het element dat gaat na Julia, Ik heb nog een pointer naar Andy, het element voor. Zodat u toegang hebt, in wezen, paneermeel, als je wil, om alle vereiste pointers. 

Dus als ik wijzend op Andy en ik ben ook wijzen bij Christian, wiens handen moet nu elders worden opgemerkt? Dus Andy kunnen nu wijzen op Julia. Julia kan nu wijzen op Christian. Omdat ze kan kopiëren mijn pointer rechterhand. En dat effectief u zet terug naar deze plek hier. Dus in het kort, ook al is dit is een soort die ons van eeuwigheid daadwerkelijk werken een gelinkte lijst, realiseren dat de operaties zijn relatief eenvoudig. Het is een, twee, drie regels code uiteindelijk. Maar rond deze regels code vermoedelijk is een beetje logica die effectief stelt de vraag, waar zijn we? Zijn we aan het begin, het midden of het einde? 

Nu zijn er zeker enkele andere operaties die we kunnen implementeren. En deze foto's hier gewoon verbeelden wat we net gedaan met mensen. Hoe zit het met het verwijderen? Als ik wil bijvoorbeeld verwijder het nummer 34 of 55, Ik zou dezelfde soort code zijn, maar ik ga naar een of twee stappen nodig. Want wat is er nieuw? Als ik iemand te verwijderen aan het einde, als nummer 55 en 34, wat moet ook veranderen als ik dat doe? Ik moet niet evict-- hoe heet je ook alweer? 

PUBLIEK: Jack. 

DAVID J. MALAN: Jack. Ik moet niet alleen evict-- vrij Jack, dus letterlijk gratis bellen Jack, of op zijn minst de aanwijzer er ook, maar nu wat er moet veranderen met Peter? Zijn hand beter beginnen naar beneden. Want zodra ik gratis bellen op Jack, als Peter's nog steeds wijzend op Jack en ik dan ook blijven doorkruisen de lijst en toegang tot deze wijzer, dat is wanneer onze oude vriend segmentatie fout zou eigenlijk schoppen. Omdat we hebben gezien de geheugen terug naar Jack. 

Je kunt er overnachten onhandig voor slechts een moment. Want we hebben slechts een paar laatste operaties te overwegen. Het verwijderen van de kop van de lijst, of de beginning-- en deze is een beetje vervelend. Want we moeten weten dat Gabe is een beetje speciaal in dit programma. Want inderdaad, hij heeft zijn eigen pointer. Hij is niet alleen hun gewezen wordt, zoals bijna iedereen hier. 

Dus wanneer het hoofd van de lijst verwijderd, wier handen moeten nu veranderen? Wat heet je ook alweer? 

PUBLIEK: Christine. 

DAVID J. MALAN: Ik ben vreselijk op namen, blijkbaar. Dus Christine en Gabe, wiens handen moeten veranderen wanneer we proberen om Christine te verwijderen, nummer 5, van de foto? OK, dus laten we het doen Gabe. Gabe gaat wijzen, vermoedelijk, op nummer 9. Maar wat er nu moet gebeuren? PUBLIEK: Christine moet null [onverstaanbaar]. DAVID J. MALAN: OK, moeten we waarschijnlijk make-- Ik hoorde "null" ergens. PUBLIEK: Null en vrij haar. DAVID J. MALAN: NULL wat? PUBLIEK: Null en vrij haar. DAVID J. MALAN: Null en vrij haar. Dus dit is zeer eenvoudig. En het is perfect dat je nu een soort van daar staan, die niet behoren. Want je bent geweest losgekoppeld van de lijst. Je hebt effectief geweest weeskinderen uit de lijst. En dus hadden we het beter noemen nu gratis op Christine aan dat het geheugen terug te geven. Anders elke keer als we verwijderen uit de lijst een knooppunt we zouden kunnen maken van de lijst korter, maar niet echt afnemende de grootte van het geheugen. En dus als we blijven toevoegen en voegen, dingen toe te voegen aan de lijst, mijn computer kan langzamer en trager en trager, want ik ben bijna geen geheugen, zelfs als ik niet eigenlijk met Christine's bytes geheugen meer. 

Dus uiteindelijk zijn er andere scenario's, van course-- verwijderen in het midden, het verwijderen op het einde, zoals we zagen. Maar de meest interessante uitdaging is nu zal zijn precies verhelpen wat de looptijd is. Dus niet alleen kan je je stukjes papier, indien, Gabe, zou je niet willen geven iedereen een stressbal. Dank je wel aan onze gelinkte lijst vrijwilligers hier, als je kon. 

[Applaus] 

DAVID J. MALAN: Oke. Dus een paar analytische vragen dan, als ik kon. We hebben deze notatie eerder gezien, big O en omega, bovengrenzen en ondergrenzen van de looptijd van een algoritme. Dus laten we eens gewoon een paar vragen. 

Een, en we zeiden dat het voor, wat is de running tijd van zoeken naar een lijst in termen van grote O? Wat is een bovengrens voor de lopende tijd van zoeken een gekoppelde lijst zoals uitgevoerd door onze vrijwilligers hier? Het is groot O van n, lineair. Omdat in het ergste geval, het element, zoals 55, we misschien op zoek naar misschien wel waar Jack, helemaal aan het einde. En helaas, anders dan een matrix kunnen we niet chique deze tijd. Hoewel al onze mensen waren gesorteerd van kleine elementen, 5, helemaal tot aan de grotere element, 55, dat is meestal een goede zaak. Maar wat betekent dat de veronderstelling niet meer kunnen we doen? PUBLIEK: [onverstaanbaar] DAVID J. MALAN: weer zeggen? PUBLIEK: Random access. DAVID J. MALAN: Random access. En op zijn beurt dat betekent dat we kunnen geen gebruik meer maken van zwakke nullen, intuïtie, en het evidente karakter van het gebruik van binaire zoeken en verdeel en heers. Want hoewel we mensen kunnen natuurlijk zien dat Andy of christelijk waren ongeveer in het midden van de lijst, we weten alleen dat als een computer door het afromen van de lijst vanaf het allereerste begin. Dus we hebben opgegeven dat random access. 

Zo groot O van n is nu de bovenste gebonden op onze zoektijd. Hoe zit het met omega van ons zoeken? Wat is de ondergrens op te zoeken gedurende een aantal in dit overzicht? PUBLIEK: [onverstaanbaar] DAVID J. MALAN: weer zeggen? PUBLIEK: One. DAVID J. MALAN: One. Dus constante tijd. In het beste geval, Christine is immers aan het begin van de lijst. En we zijn op zoek naar nummer 5, dus hebben we haar gevonden. Dus geen big deal. Maar ze heeft om in de begin van de lijst in dit geval. Hoe zit het met iets als Delete? Wat als u een element wilt verwijderen? Wat is de bovengrens en ondergrens op iets uit een gekoppeld te verwijderen lijst? PUBLIEK: [onverstaanbaar] DAVID J. MALAN: weer zeggen? PUBLIEK: n. DAVID J. MALAN: n is inderdaad de bovengrens. Want in het ergste geval proberen we Jack verwijderen, zoals we net gedaan. Hij is helemaal aan het eind. Neemt ons altijd, of n stappen om hem te vinden. Dus dat is een bovengrens. Dat is lineair, zeker. En het beste geval looptijd, of de ondergrens in het beste geval zou constante tijd. Want misschien proberen we om te verwijderen Christine, en we krijgen gewoon geluk ze is in het begin. Wacht eens even. Gabe was aan het begin, en we moesten ook Gabe updaten. Dus dat was niet zomaar een stap. Dus is het inderdaad constant tijd, in het beste geval, om het kleinste element te verwijderen? Het is, hoewel het misschien twee, drie of zelfs 100 regels code, als het hetzelfde aantal lijnen, niet in een lus, en onafhankelijk van de grootte van de lijst, absoluut. Het element bij het verwijderen het begin van de lijst zelfs als we te maken hebben met Gabe, blijft constant tijd. 

Dus dit lijkt een enorme stap achteruit. En wat een verspilling van tijd indien, in week een en week nul hadden we niet alleen pseudocode code maar de werkelijke code naar iets dat log implementeren base n, of meld u, in plaats van n, basis 2, qua looptijd. Dus waarom de heck zouden we willen beginnen met behulp van iets als een gelinkte lijst? Yeah. 

PUBLIEK: Dus u kunt toevoegen elementen aan de array. DAVID J. MALAN: Dus je kan elementen aan de array voegen. En ook dit is thematisch. En we zullen blijven zien deze, deze trade-off, veel zoals we hebben gezien een trade-off met merge sort. We konden echt versnellen zoeken of sorteren, liever, Als we besteden een beetje meer ruimte en hebben een extra stuk van een herinnering of een array voor merge sort. Maar we besteden meer ruimte, maar we tijd besparen. In dit geval zijn we het opgeven van de tijd, maar we zijn verkrijgen flexibiliteit dynamiek als je wil, dat is misschien wel een positief punt. 

We zijn ook de besteding van de ruimte. In welke zin is een gekoppelde lijst duurder in termen van ruimte dan een array? Waar is de extra ruimte vandaan? Yeah? 

PUBLIEK: [onverstaanbaar] wijzer. 

DAVID J. MALAN: Ja, we hebben ook de pointer. Dus dit is minorly vervelend dat niet meer am Ik opbergen gewoon een int naar een int te vertegenwoordigen. Ik ben het opslaan van een int en een pointer, die ook 32 bits. Dus ik ben letterlijk verdubbelen de hoeveelheid ruimte betrokken. Dus dat is een trade-off, maar dat is in het geval van int. Stel dat je niet opslaan van int, maar stel dat elk van deze rechthoeken of elk van deze mensen vertegenwoordigde een woord, een Engels woord dat misschien vijf tekens, 10 personages, misschien zelfs meer. Dan het toevoegen van slechts 32 meer bits misschien minder van een big deal te zijn. 

Wat als elk van de studenten in de demonstratie waren letterlijk student structuren die hebben namen en huizen en misschien telefoonnummers en Twitter handgrepen en dergelijke. Dus alle velden we begonnen praten over de andere dag, veel minder een big deal als onze knooppunten krijgen interessanter en groot te brengen, eh, een extra wijzer alleen om ze met elkaar te verbinden. Maar inderdaad, het is een trade-off. En inderdaad, de code is complexer, zoals u zult zie door het afromen door middel van die specifieke voorbeeld. Maar wat als er sommige heilige graal hier. Wat als we niet een stap te zetten achteruit maar een grote stap voorwaarts en implementeren van een data structuur via welke we kunnen elementen zoals Jack of zoek Christine of andere elementen in deze array in ware constante tijd? Search is een constante. Delete is constant. Insert is constant. Al deze activiteiten zijn constant. Dat zou onze heilige graal zijn. En dat is waar we pikt de volgende keer. Zie je dan.