[Speel van musiek] David J. Malan Alle regte. Dit is CS50. Dit is die vyfde week voortgesit, en ons het 'n paar goeie nuus en slegte nuus. So goeie nuus is dat CS50 loods hierdie Vrydag. As jy wil ons aan te sluit, kop aan die gewone URL hier. Die goeie nuus is geen lesing eerskomende Maandag die 13de. Effens minder goeie nuus, quiz nul is volgende Woensdag. Meer besonderhede kan gevind op hierdie URL hier. En oor die volgende paar dae Ons sal in die spasies te vul word met betrekking tot die kamers dat ons sal gereserveer het. Beter nuus is dat daar sal wees om 'n kursus-wye oorsig sessie eerskomende Maandag in die aand. Bly ingeskakel vir die kursus se webwerf vir die ligging en besonderhede. Afdelings, selfs al is dit 'n vakansie, sal ook aan sowel. Beste nuus, lesings volgende Vrydag. So dit is 'n tradisie wat ons het, soos per die leerplan. Just-- dit gaan wonderlik wees. Jy sal sien dinge soos konstante data strukture en hash tabelle en bome en drieë. En ons sal praat oor verjaarsdag probleme. 'N Hele klomp van die dinge wag volgende Vrydag. OK. In elk geval. So onthou dat ons al fokus op die foto van wat binnekant van ons rekenaar se geheue. So geheue of RAM is waar programme bestaan ​​terwyl jy hardloop hulle. As jy dubbel-kliek 'n ikoon 'n program uit te voer of dubbel-klik op 'n ikoon sommige lêer oop te maak, dit is gelaai uit jou harde ry of vaste toestand ry in die geheue, Random Access Memory, waar dit leef totdat die krag afgaan, die skootrekenaardeksel sluit, of jy sluit die program. 

Nou dat die geheue van wat jy waarskynlik 1 gigagreep hierdie dae, 2 GB, of selfs veel meer, is oor die algemeen uitgelê vir 'n gegewe program in hierdie soort van vierkantige konseptuele model waardeur ons die stapel aan die onderkant en 'n klomp ander dinge aan die bokant. Die ding op die top ons gesien het op die foto voor, maar nooit daaroor gepraat is die sogenaamde teks segment. Teks segment is net 'n fancy manier sê die nulle en ene wat komponeer jou werklike saamgestel program. 

So wanneer jy dubbel-kliek Microsoft Word op jou Mac of PC, of wanneer jy loop dot streep Mario op 'n Linux rekenaar by jou terminale venster, die nulle en ene wat komponeer Woord of Mario tydelik gestoor in jou rekenaar se geheue in die sogenaamde teks segment vir 'n bepaalde program. Hier wat gaan geïnisialiseer en geïnitialiseerd data. Dit is dinge soos die globale veranderlikes, dat ons nie gebruik het baie van, maar oor die geleentheid wat ons het het globale veranderlikes of staties gedefinieer snare wat hard gekodeer woorde soos "hallo" wat nie geneem uit die gebruiker wat hard-gekodeerde in jou program. 

Nou, sit aan die onderkant ons het die sogenaamde stapel. En die stapel, tot dusver, het ons gebruik vir watter soort doeleindes? Wat is die stapel is gebruik? Ja? 

Publiek: funksies. 

David J. Malan vir funksies? In watter sin vir funksies? 

Publiek: Wanneer jy bel 'n funksie, die argumente word op die stapel kopieer. 

David J. Malan Presies. Wanneer jy bel 'n funksie, sy argumente word op die stapel kopieer. So 'n X se of Y of 'n se of B se dat jy beweeg in 'n funksie tydelik op die sogenaamde stapel, net soos een van die Annenberg eetsaal bak, en ook om dinge soos plaaslike veranderlikes. As jou cat funksie of jou ruil funksie het plaaslike veranderlikes, soos temp, die twee eindig op die stapel. Nou sal ons nie te veel oor praat hulle, maar hierdie omgewing veranderlikes aan die onderkant ons het 'n ruk gelede toe Ek was futzing by die klawerbord een dag en ek het begin toegang dinge soos argv 100 of argv 1000, net elements-- ek vergeet die numbers-- maar dat is nie veronderstel om te verkry word deur my. Ons begin sien 'n paar funky simbole op die skerm. Dit was die sogenaamde omgewing veranderlikes soos globale instellings vir my program of my rekenaar, wat nie verband hou met die onlangse fout wat ons bespreek het, Shellshock, wat al teister nogal 'n paar rekenaars. 

Nou laastens, in vandag se fokus ons sal uiteindelik op die hoop. Dit is nog 'n stuk van die geheue. En fundamenteel al hierdie geheue is dieselfde dinge. Dit is dieselfde hardeware. Ons is net soort van behandeling verskillende groepe grepe vir verskillende doeleindes. Die hoop is ook gaan wees waar veranderlikes en geheue wat u versoek van die bedryfstelsel tydelik gestoor word. 

Maar daar is 'n soort van 'n probleem hier, soos die foto impliseer. Ons soort van twee skepe oor te bots. Omdat as jy meer en meer gebruik van die stapel, en as ons vandag sien af, as jy meer en meer van die gebruik hoop, sekerlik slegte dinge kan gebeur. En inderdaad, kan ons veroorsaak dat opsetlik of per ongeluk. So het die fotonische lewe laaste tyd was hierdie program wat nie 'n funksionele gedien het ander doel as om te demonstreer hoe jy as 'n slegte man kan eintlik neem voordeel van foute in iemand se program en neem oor 'n program of selfs 'n hele rekenaarstelsel of bediener. So net om te blik kortliks, jy sien dat hoof aan die onderkant neem in command line argumente, soos per argv. En dit het 'n oproep om 'n funksie f, wese 'n naamlose funksie genoem f, en dit is verby in argv [1]. 

Dus, wat woord wat die gebruiker in te die vinnige ná hierdie program se naam, en dan is dit arbitrêre funksie tot top, f, neem in 'n string, AKA kar *, as ons begin om te bespreek, en dit net noem dit "bar." Maar ons kan dit noem nie. En dan is dit verklaar, binne van f, 'n verskeidenheid van die karakters genoem c-- 12 sulke karakters. 

Nou, deur die storie wat ek vertel 'n oomblik gelede, waar in die geheue is c, of is daardie 12 karakters gaan eindig? Net om duidelik te wees. Ja? 

Publiek: Op die stapel. 

David J. Malan op die stapel. So c is 'n plaaslike veranderlike. Ons vra vir 12 karakters of 12 grepe. Diegene gaan beland op die sogenaamde stapel. Nou uiteindelik is hierdie ander funksie dit is eintlik baie handig, maar ons het nie regtig gebruik dit self, strncopy. Dit beteken string afskrif, maar net n brief, N karakters. So n karakters sal wees oorgeneem uit bar in c. En hoe baie? Die lengte van die bar. So met ander woorde, wat een lyn, strncopy, gaan kopieer effektief kroeg in te c. 

Nou, net om te soort van verwag Die moraal van hierdie storie, wat potensieel problematies hier? Selfs al het ons die beheer van die lengte van bar en om dit in strncopy, Wat is jou gut vertel jou is nog gebreek oor hierdie program? Ja? 

Publiek: Maak nie sluit ruimte vir die nul karakter. David J. Malan Sluit nie ruimte vir die nul karakter. Potensieel, in teenstelling met in die verlede het ons dit nie doen nie, selfs so veel as 'n plus 1 tot akkommodeer wat null karakter. Maar dit is nog erger as dit. Wat anders is ons versuim om te doen? Ja? 

Publiek: [onhoorbaar] David J. Malan Perfect. Ons het hard gekodeer 12 mooi arbitrêr. Dit is nie soseer die probleem nie, maar die feit dat ons nie eens seker te maak dat die lengte van die bar is minder as 12, in welke geval dit gaan wees veilig om dit in die geheue genoem c dat ons toegeken is. Inderdaad, as bar is soos 20 karakters lank, hierdie funksie blyk te wees, kopieer 20 karakters van bar in c, en sodoende neem ten minste 8 grepe dat dit nie moet wees nie. Dit is die implikasie hier. 

Dus, in kort, gebreekte program. Nie so 'n groot deal. Miskien het jy 'n segmentering skuld. Ons het almal het foute in programme. Ons almal kan foute het programme nou. Maar wat is die implikasie? Wel, hier is 'n ingezoomd-in-weergawe van die foto van my rekenaar se geheue. Dit is die onderkant van my stapel. En inderdaad, op die heel onderste is wat is genoem ouer roetine stapel, fancy manier om te sê dat die belangrikste. Sodat elkeen wat die funksie genoem f dat ons praat. So dit is die onderkant van die stapel. Terugkeer adres is iets nuuts. Dit was nog altyd daar, altyd in die foto. Ons het net nooit aandag geroep om dit te. Omdat dit blyk uit die manier c werk is dat wanneer een funksie noem 'n ander, nie net die argumente wat dit doen funksie gestoot kry op die stapel te plaas, nie net die funksie se plaaslike doen veranderlikes gestoot kry op die stapel te plaas, iets genaamd 'n terugkeer adres ook kry sit op die stapel. Spesifiek, as hoof oproepe foo, hoof se eie adres in die geheue, bees iets, effektief kry sit op die stapel sodat wanneer f gedoen die uitvoering van dit weet waar om terug te spring in die teks segment in om voort te gaan die uitvoering. 

So as ons hier is konseptueel, in die belangrikste, dan is f kry genoem. Hoe f weet wie om beheer terug? Wel, hierdie klein bread in rooi hier genoem die adres, is dit net tjeks, wat is dit terugkeer adres? O, laat my terug na die hoof spring hier. En dit is 'n bietjie van 'n oorvereenvoudiging, omdat die nulle en ene vir die hoof is tegnies hier in die tegnologie segment. Maar dit is die idee. f het net om te weet wat waar beheer gaan uiteindelik terug. 

Maar die manier waarop rekenaars het lank gelê dinge soos plaaslike veranderlikes en argumente is soos hierdie. So in die top van hierdie foto in blou is die stapel raamwerk vir f, so al van die geheue wat f spesifiek is met behulp van. So dienooreenkomstig, sien dat bar is in die prentjie. Bar was sy argument. En ons het beweer dat argumente te funksies gestoot kry op die stapel. En c, natuurlik, is ook in hierdie foto. 

En net vir notasie doeleindes, kennisgewing by die top linkerhoek word wat sou wees c bracket 0 en dan effens af aan die regterkant is c bracket 11. So met ander woorde, kan jy dink dat daar 'n rooster van grepe Daar, in die eerste wat links bo, onderkant van wat is die laaste van die 12 grepe. 

Maar nou probeer om vorentoe te vinnig. Wat gaan gebeur as ons slaag in 'n string bar dit is langer as c? En ons is nie seker te maak dat dit is inderdaad meer as 12. Watter deel van hierdie prentjie gaan kry oorskryf deur grepe 0, 1, 2, 3, dot dot dot, 11, en dan sleg, 12, 13 tot 19? Wat gaan hier gebeur nie, As jy aflei uit die bestel dat c bracket 0 is op die top en c bracket 11 is 'n soort van af aan die regterkant? Ja? 

Publiek: Wel, dit gaan te vervang die kar * bar. 

David J. MALAN: Ja, dit lyk soos jy gaan te vervang kar * bar. En nog erger, as jy stuur in 'n baie lang string, kan jy selfs oorskryf wat? Die opbrengs adres. Wat weer, is net soos 'n bread die program waar om te vertel om terug te gaan wanneer f gedoen word genoem. 

So, wat slegte ouens tipies doen is as hulle kom oor 'n program dat hulle nuuskierig of is ontginbaar, karretjie in so 'n manier dat hy of sy kan neem voordeel van die fout, algemeen hulle kry nie hierdie reg die eerste keer. Hulle het net begin stuur, byvoorbeeld, ewekansige snare in jou program, of by die klawerbord, of eerlik hulle waarskynlik skryf 'n klein program om net outomaties genereer snare, en begin klap op jou program deur stuur in baie verskillende insette op verskillende lengtes. 

Sodra jou program crashes, dit is 'n wonderlike ding. Want dit beteken hy of sy ontdek wat is waarskynlik inderdaad 'n fout. En dan kan hulle meer slim en begin meer eng fokus oor hoe dat die fout te ontgin. In die besonder, wat hy of sy mag doen is stuur, in die beste geval, hallo. Geen groot deal. Dit is 'n string wat is genoeg kort. Maar wat as hy of sy stuur, en ons sal veralgemeen dit as, aanval code-- so nulle en diegene wat dinge doen soos rm-rf, dat alles verwyder van die hardeskyf of stuur spam of een of ander manier om die masjien te val? 

So as elk van hierdie letters A net verteenwoordig, konseptueel, aanval, aanval, aanval, aanval, 'n paar slegte kode dat iemand anders geskryf het nie, maar indien daardie persoon is slim genoeg om nie net al van daardie rm-RFS nie, maar ook sy of haar laaste paar grepe 'n getal wat ooreenstem aan die adres van sy of haar eie aanval kode dat hy of sy geslaag het in net deur dit by die vinnige, jy kan die rekenaar effektief mislei in die merk wanneer f gedoen uitvoering, O ja, dit is tyd vir my om te spring terug na die rooi terugkeer adres. Maar omdat hy of sy een of ander manier oorvleuel wat terugkeer adres met hul eie nommer, en hulle is slim genoeg het ingestel wat nommer te verwys, as jy sien in die super top linkerhoek daar, die werklike adres in die rekenaar se geheue van 'n paar van hul aanval kode, 'n slegte man kan die rekenaar mislei in die uitvoering van sy of haar eie kode. 

En dat kode, weer, kan enigiets wees. Dit is algemeen bekend as dop kode, wat net 'n manier om te sê dat dit nie algemeen iets so eenvoudig soos rm-rf. Dit is eintlik iets soos Bash, of 'n werklike program wat hom gee of haar programmatiese beheer uit te voer enigiets anders wat hulle wil. Dus, in kort, dit alles afgelei van die eenvoudige feit dat hierdie fout betrokke nie nagaan die grense van jou skikking. En omdat die pad rekenaars werk, is dat hulle gebruik die stapel van effektief, konseptueel, onderaan, maar dan is die elemente jy druk op die stapel groei top-down, dit is ongelooflik problematies. Nou, daar is maniere om te werk om hierdie. En eerlik, daar is tale mee te werk om hierdie. Java is immuun, byvoorbeeld, hierdie spesifieke kwessie. Omdat hulle gee jou nie wysers. Hulle gee jou nie direkte geheue adresse. So met hierdie krag wat ons het enigiets in die geheue aan te raak Ons wil kom, weliswaar 'n groot risiko. 

So hou 'n oog uit. As, eerlik, in die maande of jare om te kom, enige tyd jy lees oor 'n paar uitbuiting van 'n program of 'n bediener, as jy ooit sien 'n wenk van iets soos 'n buffer oorloop aanval, of stapel oorloop is 'n ander soort van die aanval, soortgelyk in die gees, soveel as inspireer die webwerf se noem, as jy dit weet, dit is al praat net oorstroom die grootte van 'n paar karakter skikking of 'n skikking meer algemeen. Enige vrae, dan, op hierdie? Moenie probeer om dit by die huis nie. 

Alle regte. So malloc dusver het ons nuwe vriend in wat ons geheue toeken dat ons weet nie noodwendig in bevorder wat ons wil hê, sodat ons het nie om hard te kode in ons program getalle soos 12. Sodra die gebruiker vertel ons hoeveel data wat hy of sy wil invoer, ons kan malloc dat baie geheue. 

So malloc dit blyk, aan die mate het ons dit gebruik, uitdruklik laaste keer, en dan julle ouens gebruik dit vir getstring onwetend vir 'n paar weke, al malloc se geheue kom van die sogenaamde hoop. En dit is die rede waarom getstring, byvoorbeeld, kan geheue dinamies ken sonder om te weet wat jy gaan om te tik in advance, hand wat jy terug 'n wyser na daardie geheue, en dat die geheue is nog joune te hou, selfs nadat getstring opbrengste. Omdat herroeping na alles wat die stapel is voortdurend op en af, op en af. En so gou as wat dit gaan af, wat beteken dat 'n geheue hierdie funksie moet gebruik nie gebruik word deur enigiemand anders. Dit is vullis waardes nou. 

Maar die hoop is hier. En wat is lekker oor malloc is dat wanneer malloc ken geheue hier, dit is nie 'n impak, vir die grootste deel, deur die stapel. En so 'n funksie kan toegang geheue wat malloc'd, selfs deur 'n funksie soos getstring, selfs nadat dit teruggebring word. 

Nou, die omgekeerde van malloc is gratis. En inderdaad, die reël wat jy nodig het om te begin die aanneming enige, enige, enige tyd wat jy malloc gebruik jy moet jouself gebruik vry, uiteindelik, op dieselfde wyser. Al hierdie tyd het ons skryf karretjie, karretjie kode, vir baie redes. Maar een van wat reeds gebruik van die CS50 biblioteek, wat self is doelbewus karretjie, dit lek geheue. Enige tyd wat jy het getstring genoem oor die afgelope paar weke ons die bedryfstelsel is te vra stelsel, Linux, vir die geheue. En jy het nog nie een keer terug gegee het. En dit is nie, in oefen, 'n goeie ding. 

En Valgrind, een van die gereedskap wat in Pset 4, is alles oor jou te help vind nou foute soos dit. Maar gelukkig vir Pset 4 jy hoef nie die CS50 biblioteek of getstring te gebruik. So enige foute met betrekking tot die geheue is uiteindelik gaan jou eie wees. 

So malloc is meer as net gerieflik vir hierdie doel. Ons kan eintlik nou op te los fundamenteel verskillende probleme, en fundamenteel probleme op te los meer effektief as per week nul se belofte. Tot dusver is dit die mees sexy data struktuur wat ons gehad het. En deur die data struktuur ek net beteken 'n manier van konseptualisering geheue op 'n manier wat verder gaan as net sê, dit is 'n int, dit is 'n teken. Ons kan begin cluster dinge saam. 

So 'n skikking lyk soos hierdie. En wat die sleutel in ongeveer 'n was skikking is dat dit gee jou rug-aan-rug stukke geheue, wat elk gaan word van dieselfde soort, int, int, int, int, of kar, kar, kar, kar. Maar daar is 'n paar nadele. Dit is byvoorbeeld 'n verskeidenheid van grootte ses. Veronderstel jy hierdie verskeidenheid vul met ses nommers en dan, om watter redes, jou gebruikers wil gee jy 'n sewende nommer. Waar het jy dit doen? 

Wat is die oplossing as jy ' geskep het 'n skikking op die stapel te plaas, byvoorbeeld, net met die week twee notasie wat ons lei, vierkante hakies met 'n aantal binne? Wel, jy het ses getalle in hierdie bokse. Wat sou jou instink wees? Waar sal jy wil om dit te sit? 

Publiek: [onhoorbaar] 

David J. Malan Jammer? 

Publiek: Sit dit op die einde. 

David J. Malan Sit dit op die einde. So net meer aan die regterkant, buite die boks. Watter sal lekker wees, maar dit blyk jy kan dit nie doen nie. Want as jy het nie gevra vir hierdie stuk van die geheue, dit kan wees deur toeval dat hierdie gebruik word deur 'n ander veranderlike geheel en al. Dink terug 'n week of so wanneer ons gelê uit Zamyla en Davin en Gabe se name in die geheue. Hulle was letterlik rug aan rug aan rug. So kan ons nie noodwendig vertrou dat alles se hier is vir my om te gebruik. 

So wat anders kan jy doen? Wel, een keer besef jy nodig om 'n verskeidenheid van grootte sewe, jy kan net 'n verskeidenheid van grootte sewe gebruik dan 'n lus vir die of 'n while lus, kopieer dit in die nuwe skikking, en dan een of ander manier net ontslae te raak van hierdie reeks of net ophou om dit te gebruik. Maar dit is nie baie doeltreffend nie. In kort, skikkings moenie jy dinamiese grootte. 

So aan die een kant jy ewetoeganklike, wat is ongelooflik. Omdat dit laat ons dinge doen soos verdeel en oorwin, binêre soek, al wat ons het gepraat oor op die skerm hier. Maar jy jouself verf in 'n hoek. Sodra jy getref die einde van jou skikking, jy het 'n baie te doen duur operasie of skryf 'n hele klomp van die kode nou gaan met die probleem. 

So, wat as plaas moes ons iets genaamd 'n lys, of 'n geskakelde lys in die besonder? Wat as in plaas van om reghoeke Terug op te back, ons het reghoeke dat 'n bietjie laat bietjie wikkel kamer tussen hulle? En selfs al het ek hierdie geteken prent of aangepas hierdie foto van een van die tekste hier om terug te wees rug aan rug baie ordelike, in werklikheid, een van daardie reghoeke kon hier in die geheue wees. Een van hulle kon hier wees. Een van hulle kon hier wees, hier, en so meer. 

Maar wat as ons het, in hierdie geval, pyle dat een of ander manier verbind hierdie saam reghoeke? Inderdaad, het ons gesien dat 'n tegniese inkarnasie van 'n pyl. Wat het ons in die afgelope dae dat onder die enjinkap, verteenwoordigend is van 'n pyl? 'N wyser, reg? 

So, wat as, in plaas van net die stoor van die getalle, soos 9, 17, 22, 26, 34, Wat gebeur as ons nie gestoor net 'n nommer, maar 'n wyser langs elke sodanige nommer? So veel soos jy sou ryg 'n naald deur 'n hele klomp van die stof, een of ander manier vasmaak dinge saam, insgelyks kan ons met wysers, soos geïnkarneer word deur pyle hier soort van saam te weef hierdie individuele reghoeke deur effektief gebruik te maak van 'n wyser langs elke nommer wat dui op 'n volgende nommer, wat dui op sy beurt 'n volgende nommer? So met ander woorde, wat As ons eintlik wou iets soos hierdie te implementeer? Wel ongelukkig hierdie reghoeke, ten minste die een met 9, 17, 22, en so meer, dit is nie meer mooi blokkies met 'n enkele nommers. Die onderste, reghoek onder 9, byvoorbeeld, verteenwoordig wat moet 'n wyser, 32 stukkies. Nou, ek is nog nie bewus van enige data tipe in C wat gee jou nie net 'n int maar 'n wyser heeltemal. 

So wat is die oplossing as ons wil ons eie antwoord op hierdie uit te vind? Ja? 

Publiek: [onhoorbaar] 

David J. Malan Wat is dit? 

Publiek: Nuwe struktuur. 

David J. Malan Ja, so hoekom het ons nie 'n nuwe struktuur, of in C, 'n struct? Ons het gesien hoe structs voor, indien kortliks waar ons met 'n student struktuur soos hierdie, wat 'n naam en 'n huis gehad het. In Pset 3 tempo jy 'n hele gebruik klomp van structs-- GRect en GOvals dat Stanford geskep cluster inligting saam. So wat as ons hierdie selfde idee van die term "typedef" en "struct," en dan 'n paar student-spesifieke dinge, en ontwikkel dit in die volgende: typedef struct node-- en knoop is net 'n baie generiese rekenaarwetenskap term vir iets in 'n data struktuur, 'n houer in 'n data-struktuur. 'N knoop ek eis gaan hê 'n int n, heeltemal eenvoudig, en dan 'n bietjie meer kripties, hierdie tweede lyn, struct node * volgende. Maar in minder tegniese terme, Wat is die tweede lyn van die kode binne-in die krulhakies? Ja? 

Publiek: [onhoorbaar] David J. Malan 'n wyser na 'n ander knoop. So weliswaar, sintaksis 'n bietjie kripties. Maar as jy dit letterlik gelees, Volgende is die naam van 'n veranderlike. Wat is die data tipe? Dit is 'n bietjie verbose hierdie tyd, maar dit is van die tipe struct node *. Enige tyd wat ons het gesien iets ster wat beteken dit is 'n verwysing na die data tipe. So volgende is blykbaar 'n wyser na 'n struct node. 

Nou, wat is 'n struct node? Wel, sien jy sien die dieselfde woorde regs bo. En inderdaad, jy sien ook die woord "Knoop" hier aan die onderkant links. En dit is eintlik net 'n gerief. Let daarop dat in ons student definisie daar is die woord "student" net een keer. En dit is omdat 'n student voorwerp was nie self-referensiële. Daar is niks binnekant van 'n student wat moet wys na 'n ander student, persay. Dit sou soort wees vreemd in die werklike wêreld. 

Maar met 'n knoop in 'n gekoppelde lys, ons wil hê dat 'n knoop te referensiële aan 'n soortgelyke voorwerp wees. En so neem kennis van die verandering is hier nie net wat binne-in die krulhakies. Maar ons voeg die woord "knoop" aan die bokant sowel as dit toe te voeg aan die onderkant in plaas van "student." En dit is net 'n tegniese detail sodat, weer, jou data struktuur kan self-referensiële wees, sodat 'n knoop kan wys nog so knoop. 

So, wat is hierdie uiteindelik gaan beteken vir ons? Wel, een van hierdie dinge binne is die inhoud van ons node. Hierdie ding hier, regs bo, is net so wat weer kan ons verwys na onsself. En dan die buitenste dinge, selfs al knoop is 'n nuwe term, miskien, dit is nog steeds die dieselfde as student en wat was onder die enjinkap in SPL. 

So as ons wil nou te begin die implementering van hierdie geskakelde lys, hoe kan ons vertaal iets soos hierdie te kode? Wel, laat ons sien net 'n voorbeeld van 'n program wat eintlik gebruik van 'n geskakelde lys. Onder vandag se verspreiding-kode is 'n program genaamd Lys Zero. En as ek loop dit Ek het 'n super eenvoudige GUI, grafiese gebruikerskoppelvlak, maar dit is regtig net printf. En nou het ek myself 'n paar spyskaart gegee options-- verwyder, vul, Soek, en loop. En stop. Dit is net 'n gemeenskaplike bedrywighede op 'n data struktuur bekend as 'n skakel lys. 

Nou, verwyder gaan verwyder 'n aantal van die lys. Insetsel gaan voeg 'n aantal van die lys. Soek gaan om te kyk vir die aantal in die lys. En deurkruis is net 'n fancy manier sê, loop deur die lys, druk dit uit, maar dit is dit. Moet dit verander nie in enige manier. 

So laat ons probeer om hierdie. Kom ons gaan voort en tik 2. En dan gaan ek voeg die nommer, sê 9. Betree. En nou is my program is net geprogrammeer om te sê, lys is nou 9. Nou, as ek gaan voort en nie Voeg weer laat my voort te gaan en zoom uit en tik in 17. Nou is my lys is 9, dan is 17. As ek dit doen voeg weer laat slaan een. In plaas van 22, soos per die prentjie wat ons het is op soek na hier, laat my voor te spring en voeg 26 volgende. So ek gaan om te tik 26. Die lys is soos ek verwag. Maar nou, net om te sien of hierdie kode gaan om buigsaam te wees, laat my nou tipe 22, waarvan ten minste konseptueel, as ons Hou dit gesorteer, wat is inderdaad gaan nou 'n ander doel te wees, moet gaan in tussen 17 en 26. So ek druk Enter. Inderdaad, wat werk. En so nou laat my plaas die laaste, volgens die prentjie, 34. 

Alle regte. So vir nou, laat my bepaal dat Verwyder en loop en soek nie, in werklikheid, werk. In werklikheid, as ek loop soek, laat soek vir die nommer 22, Tik. Dit het bevind dat 22. So dit is wat hierdie program Lys Zero doen. 

Maar wat eintlik gaan op daardie implemente dit? Wel, die eerste wat ek mag hê, en inderdaad Ek het 'n lêer genaamd list0.h. En iewers in daar is dit lyn, typedef, struct node, dan het ek my krulhakies, int n, en dan struct-- wat was die definisie? Struct node volgende. Dus moet ons die sterre. Nou tegnies kry ons in die gewoonte van die opstel is dit hier. Jy kan sien en handboeke aanlyn verwysings doen dit daar. Dit is funksioneel ekwivalent. In werklikheid, dit is 'n bietjie meer tipies. Maar ek sal in ooreenstemming met wat in ons het die laaste tyd en dit doen. En dan laastens, ek gaan om dit te doen. 

So in 'n kop-lêer iewers in list0.h vandag is dit struct definisie, en miskien 'n paar ander dinge. Intussen is in list0c daar gaan 'n paar dinge om te wees. Maar ons gaan net begin en nie voltooi nie. List0.h is 'n lêer wat ek wil in te sluit in my C-lêer. En dan op 'n sekere punt wat ek gaan int te hê, hoof, tot niet. En dan gaan ek het 'n paar te-doen is hier. Ek gaan ook 'n te hê prototipe, soos leemte, soek, int, n, wie se doel in die lewe is om te soek na 'n element. En dan hier Ek eis in vandag se kode, nietig, soek, int, N, kommapunt maar oop krulhakies. En nou wil ek een of ander manier soek vir 'n element in die lys. Maar ons het nie genoeg inligting op die skerm nie. Ek het nie eintlik verteenwoordig die lys self. So een manier waarop ons kan implementeer 'n geskakelde lys in 'n program is ek soort wil om iets te doen soos verklaar gekoppel lys hier. Vir eenvoud, ek gaan maak hierdie globale, selfs al in die algemeen ons moet dit nie te veel doen. Maar dit sal hierdie voorbeeld vereenvoudig. Dus wil ek verklaar 'n geskakelde lys hier. Nou, hoe kan ek dit doen? 

Hier is die foto van 'n geskakelde lys. En ek het nie regtig weet op die oomblik hoe Ek gaan om te gaan oor verteenwoordig so baie dinge met net een veranderlike in die geheue. Maar terug dink 'n oomblik. Al hierdie tyd wat ons gehad het snare, wat ons dan geopenbaar skikkings te wees karakters, wat ons dan geopenbaar om net 'n wyser die eerste karakter in 'n verskeidenheid van die karakters dit is null beëindig. So deur die logika, en met hierdie prentjie soort loting jou gedagtes, Wat het ons eintlik skryf in ons kode 'n geskakelde lys te verteenwoordig? Hoeveel van hierdie inligting het ons nodig vas te vang in C-kode, sou jy sê? Ja? 

Publiek: Ons moet 'n verwysing na 'n knoop. David J. Malan 'n verwysing na 'n knoop. In die besonder, wat knoop sou jou instink wees om 'n wyser te hou? 

Publiek: Die eerste knoop. 

David J. Malan Ja, waarskynlik net die eerste. En sien, die eerste knoop is 'n ander vorm. Dit is net die helfte van die grootte van die struct, want dit is inderdaad net 'n wyser. So wat jy wel kan doen is om te verklaar 'n geskakelde lys te wees van die tipe knoop *. En laat ons net noem dit die eerste en inisialiseer te null. So nul, weer, is komende in die prentjie hier. Nie net is nul as soos 'n spesiale terugkeer waarde vir dinge soos getstring en malloc, nietig is ook die nul wyser, die gebrek aan 'n wyser, as jy wil. Dit beteken net mooi niks is nog hier. Nou eers kan ek het noem dit niks. Ek kon genoem het dit "lys" of enige aantal ander dinge. Maar ek noem dit "die eerste" sodat dit in lyn is met hierdie prentjie. So net soos 'n string verteenwoordig kan word met die adres van sy eerste byte, so kan 'n geskakelde lys. En ons sal ander data te sien strukture verteenwoordig word met net een muis, 'n 32-bit pyl wys op die heel eerste node in die struktuur. 

Maar laat ons nou verwag 'n probleem. As ek net onthou in my program die adres van die eerste knoop, die eerste reghoek in hierdie data struktuur, wat beter wees om die saak oor die implementering van die res van my lys? Wat is 'n belangrike detail wat gaan om te verseker dat dit eintlik werk? En deur die "eintlik werk" Ek bedoel, baie soos 'n string, laat ons gaan van die eerste karakter in Davin se naam na die tweede, na die derde, aan die vierde, tot op die einde, Hoe weet ons wanneer ons aan die einde van 'n geskakelde lys wat lyk soos hierdie? Wanneer dit is null. En ek het hierdie soort van soos verteenwoordig soos 'n elektriese ingenieur mag, met die bietjie grou simbool, van spesies. Maar dit beteken net nul in hierdie geval. Jy kan dit teken 'n aantal maniere, maar hierdie skrywer gebeur hierdie simbool om hier te gebruik. 

So lank as wat ons bedrading al hierdie nodes saam net onthou waar die eerste een is, so lank as ons 'n spesiale simbool op die heel laaste knoop in die lys, en ons sal gebruik nul, want dit is wat ons tot ons beskikking, hierdie lys is voltooi. En selfs as ek net gee jou 'n wyser na die eerste element, julle, die programmeerder, kan seker toegang tot die res van dit. Maar laat ons laat jou gedagtes dwaal 'n bietjie, as hulle nie reeds heel wandered-- wat is gaan die loop van die tyd te wees die vind van iets in die lys? Damn dit, dit is 'n groot O van n, wat is nie sleg nie, in regverdigheid. Maar dit is lineêr. Ons het opgegee wat funksie van skikkings deur die verskuiwing van meer na hierdie foto van dinamiese aanmekaar geweef of verbind nodes? Ons het opgegee ewekansige toegang. 'N skikking is mooi, want wiskundig alles is terug om terug te rug aan rug. Selfs al is hierdie foto lyk mooi, en selfs al is dit lyk soos hierdie nodes is mooi afstand van mekaar, in werklikheid hulle oral te kan wees. OX1, Ox50, Ox123, Ox99 hierdie nodes kan enige plek wees. Omdat malloc nie ken geheue van die hoop, maar nêrens in die hoop. Jy nie noodwendig weet dat dit gaan om terug te wees om terug te rug. En so hierdie foto in werklikheid se nie gaan baie van hierdie mooi. 

So dit gaan 'n bietjie van te neem werk om hierdie funksie te implementeer. So laat implementeer soek nou. En ons sal sien die soort van 'n slim manier om dit te doen. So as ek 'n soek funksie en Ek kry 'n veranderlike, heelgetal n om te kyk, ek nodig het om te weet die nuwe sintaksis vir die soek binne van 'n struktuur wat wys na, te vind N. So laat ons dit doen. 

So eerste ek gaan om te gaan voort en verklaar 'n knoop *. En ek gaan om dit te noem wyser, net deur konvensie. En ek gaan om dit te inisialiseer eerste. En nou kan ek dit doen in 'n aantal maniere. Maar ek gaan 'n gemeenskaplike benadering te neem. Terwyl wyser is nie gelyk aan nul, en dit is geldig sintaksis. En dit beteken net die volgende doen, sodat Solank as wat jy nie wys op niks. Wat wil ek doen? 

As wyser dot n, laat my terug te kom dat, gelyk equals-- wat? Watter waarde is ek op soek na? Die werklike N wat in geslaag is. So hier is nog 'n kenmerk van C en baie ander tale. Selfs al is die struktuur genoem knoop het 'n waarde n, heeltemal wettig om ook 'n plaaslike argument of veranderlike genoem n. Omdat selfs ons met menslike oë kan onderskei dat dit n vermoedelik verskil van die N. Omdat die sintaksis is anders. Jy het 'n kol en 'n wyser, terwyl hierdie een het nie so 'n ding. So dit is OK. Dit is OK om dieselfde dinge te noem. 

As ek jy dit doen, ek is gaan wil om iets te doen soos kondig dat ons gevind n. En ons sal laat dit as 'n kommentaar of pseudokode kode. Anders, en hier is die interessante deel, wat doen wat ek wil doen as die huidige knoop nie met n dat ek omgee? Hoe om die volgende te bereik nie? As my vinger op die oomblik is PTR, en dit is wys op watter eerste wys op, Hoe kan ek my vinger na die volgende knoop in die kode? Wel, wat is die bread ons gaan volg in hierdie geval? Publiek: [onhoorbaar]. David J. Malan Ja, so volgende. So as ek gaan terug na my kode hier, wel, ek is gaan om voort te gaan en sê wyser, wat is net 'n tydelike variable-- dit 'n vreemde naam, ptr, maar dit is net soos temp-- Ek gaan wyser te stel gelyk aan alles wat wyser is-- en weer, dit gaan 'n te wees karretjie vir 'n moment-- dot volgende. Met ander woorde, ek gaan neem my vinger wat is wys hierdie knoop hier en ek gaan om te sê, jy weet wat, 'n blik op die volgende gebied en beweeg jou vinger wat dit is wys. En dit gaan herhaal, herhaal, herhaal. Maar toe het my vinger stop om iets te doen nie? Sodra watter lyn van die kode skop in? Publiek: [onhoorbaar] David J. Malan As punt terwyl wyser is nie gelyk aan null. Op 'n stadium my vinger se gaan word wat dui op nul en ek gaan om te besef dit is die einde van die lys. Nou, dit is 'n bietjie wit leuen vir eenvoud. Dit blyk dat selfs al is ons Net hierdie dot-notasie geleer vir strukture, wyser is nie 'n struct. ptr is wat? Net om te wees meer nitpicky. Dit is 'n verwysing na 'n knoop. Dit is nie 'n knoop self. As ek het geen sterre hier, wyser absolutely-- dit is 'n knoop. Dit is soos 'n week een verklaring van 'n veranderlike, selfs al is die woord "knoop" is 'n nuwe. 

Maar so gou as ons 'n ster, dit is nou 'n verwysing na 'n knoop. En ongelukkig kan jy nie gebruik die dot-notasie vir 'n muis. Jy het die pyl te gebruik notasie, wat opvallend, is die eerste keer 'n stuk van sintaksis lyk intuïtief. Dit lyk letterlik soos 'n pyl. En so is dit 'n goeie ding. En hier letterlik lyk soos 'n pyl. So ek dink dit is die la-- ek doen nie dink ek oor-die pleeg here-- ek dink dit is die laaste nuwe stuk van sintaksis ons gaan om te sien. En gelukkig, dit is inderdaad 'n bietjie meer intuïtief. 

Nou, vir dié van julle wat mag verkies om die ou manier, jy kan nog steeds gebruik maak van die dot-notasie. Maar as per Maandag se gesprek, ons eerste nodig om daar te gaan, gaan na daardie spreek, en dan toegang tot die gebied. So is dit ook reg. En eerlik, dit is 'n bietjie meer pedanties. Jy letterlik gesê dereference die wyser en gaan daar. Dan gryp .n, die veld genaamd n. Maar eerlik, niemand wil om te tik of lees. En so het die wêreld uitgevind die pyl notasie, wat gelykstaande is identies, dit is net sintaktiese suiker. So 'n fancy manier om te sê hierdie lyk beter, of lyk makliker. 

So nou gaan ek 'n ander ding om te doen. Ek gaan om te sê "breek" wanneer ek het gevind dat dit so hou ek nie op soek na dit. Maar dit is die kern van 'n soek funksie. Maar dit is 'n baie makliker, in die einde, om nie te wandel deur die kode. Dit is inderdaad die formele implementering soek in vandag se verspreiding-kode. Ek waag om te sê dat die insetsel is nie veral pret deur te loop visueel, of is verwyder, selfs al aan die einde van die dag hulle neer te regverdig eenvoudige heuristiek. 

So laat ons dit doen. As jy sal humor my hier, ek het bring 'n klomp van stres balle. Ek het 'n klomp van die nommers. En kan ons net 'n paar vrywilligers 9, 17, 20, 22, 29, 34 en voor te stel? So in wese almal wie's hier vandag. Dit was een, twee, drie, vier, vyf, ses mense. En ek het gevra om go-- sien, geen een in die rug verhoog hul hande. OK, een, twee, drie, vier, five-- laat my laai balance-- ses. OK, jy ses kom op. Ons sal ander mense nodig het. Ons het ekstra stres balle. En as jy kan, vir net 'n oomblik, lyn julle het net soos hierdie prentjie hier. 

Alle regte. Kom ons kyk, wat is jou naam? 

Publiek: Andrew. 

David J. Malan Andrew, jy is nommer 9. Nice om jou te ontmoet. Hier gaan jy. Publiek: Jen. David J. Malan Jen. David. Nommer 17. Ja? 

Publiek: Ek is Julia. 

David J. Malan Julia, David. Nommer 20. GEHOOR: Christen. David J. Malan Christen, David. Nommer 22. En? 

Publiek: JP. David J. Malan JP. Nommer 29. So gaan voort en kry in-- Uh oh. Uh oh. Bystand. 20. Is daar iemand het 'n merker? Publiek: Ek het 'n Sharpie. David J. Malan Jy het 'n Sharpie? OK. En nie almal het 'n stukkie van die papier? Slaan die lesing. Kom op. Publiek: Ons het dit. David J. Malan Ons het dit? Alle reg, dankie. Hier gaan ons. Was dit van jou? Jy moet net die dag gered. So 29. Alle regte. Ek gespel 29, maar OK. Gaan voort. Alle reg, sal ek gee jou jou pen terug 'n oomblik. So ons het hierdie mense hier. Kom ons 'n ander. Gabe, wil jy om te speel die eerste element hier? Ons sal jou nodig om te wys op hierdie pragtige mense. So 9, 17, 20, 22, soort van 29, en dan 34. Het ons iemand verloor? Ek het 'n 34. Waar did-- OK, wat wil wees 34? OK, kom op, 34. Alle reg, sal dit die moeite werd om die klimaks. Wat is jou naam? 

Publiek: Peter. 

David J. Malan Petrus, kom op. Alle reg, so hier is 'n n hele klomp van knope. Elkeen van julle ouens verteenwoordig een van hierdie reghoeke. En Gabe, die effens vreemd Man Out, verteenwoordig die eerste. So sy wyser is 'n bietjie kleiner op die skerm as almal anders. En in hierdie geval, elkeen van die linkerkant hande gaan óf wys af, daardeur verteenwoordig nul, so net die afwesigheid van 'n muis, of dit gaan word wys by 'n knoop langs jou. 

So nou as jy versier julle soos die prentjie hier, gaan voort en punt na mekaar, met Gabe in die besonder wys op nommer 9 in die lys te verteenwoordig. OK, en die getal 34, jou linkerhand moet net wys op die vloer. 

OK, so dit is die geskakelde lys. So dit is die scenario in die vraag. En inderdaad, hierdie is 'n verteenwoordiger van 'n klas van probleme dat jy kan probeer om op te los met 'n kode. Jy wil om uiteindelik voeg 'n nuwe element in die lys. In hierdie geval, ons gaan probeer om die invoer van die getal 55. Maar daar gaan wees verskillende gevalle te oorweeg. En inderdaad, dit gaan om een ​​te wees van die groot-prentjie wegneemetes hier is, Wat is die verskillende gevalle. Wat is die verskil as toestande of takke wat jou program kan hê? 

Wel, die nommer wat jy probeer om te insetsel, wat ons nou weet te wees 55, maar as jy nie geweet het nie vooraf, ek daresay val in ten minste drie moontlike situasies. Waar kan 'n nuwe element? Publiek: En die einde of die middel. David J. Malan Aan die einde, in die middel, of by die begin. So ek beweer daar is ten minste drie probleme wat ons moet oplos. Kom ons kies wat miskien waarskynlik die eenvoudigste een, waar die nuwe element behoort aan die begin. So ek gaan code te hou het soos soek, wat ek net geskryf. En ek gaan ptr te hê, wat Ek sal hier verteenwoordig met my vinger, soos gewoonlik. 

En onthou, watter waarde het ons inisialiseer ptr te? So ons geïnisialiseer dit aanvanklik null. Maar wat het ons doen wanneer ons is in ons soek funksie? Ons stel dit gelyk aan die eerste, wat beteken nie om dit te doen. As ek ptr gelykstaande aan die eerste, wat moet my hand werklik wys? Right. So as ek en Gabe gaan gelyke waardes om hier te wees, Ons moet beide punt op nommer 9. 

So dit was die begin van ons storie. En nou is dit net 'n eenvoudige, selfs al is die sintaksis is 'n nuwe. Konseptueel dit is net lineêre soek. 55 gelyk aan 9? Of eerder, kom ons sê minder as 9. Omdat ek probeer uit te vind waar om te sit 55. Minder as 9, minder as 17, minder as 20, minder as 22, minder as 29, minder as 34, no. So nou is ons in die geval een van minstens drie. 

As ek wil voeg 55 hier, wat reëls van die kode behoefte om tereggestel te raak? Hoe hierdie foto van mense nodig het om te verander? Wat doen ek met my linkerhand? Dit moet aanvanklik nul, want ek is aan die einde van die lys. En wat moet gebeur hier met Petrus, was dit? Hy is natuurlik gaan om te wys vir my. So ek beweer daar is ten minste twee lyne van die kode in die voorbeeld kode van vandag wat gaan om dit te implementeer scenario van die toevoeging van 55 by die stert. En ek kon iemand hop en net verteenwoordig 55? Alle reg, jy is die nuwe 55. 

So nou wat as die volgende scenario kom saam, en ons wil te voeg by die begin of die hoof van die lys? En wat is jou naam, nommer 55? 

Publiek: Jack. 

David J. Malan Jack? OK, lekker om jou te ontmoet. Welkom aan boord. So nou gaan ons voeg, sê, die nommer 5. Hier is die tweede geval van die drie ons het met voor. So as 5 behoort aan die begin, Kom ons kyk hoe ons uitvind. Ek inisialiseer my ptr wyser te nommer 9 weer. En ek besef, o, 5 minder as 9. So los hierdie foto vir ons. Wie se hande, Gabe se of David se or-- wat is nommer 9 se naam? 

Publiek: Jen. 

David J. Malan Jen se hands-- wat van ons hande nodig om te verander? OK, so Gabe wys na wat nou? Op my. Ek is die nuwe node. So sal ek net soort van beweging hier is dit visueel sien. En intussen wat ek wys dit? Steeds waar ek wys. So dit is dit. So net regtig een lyn van kode fixes hierdie spesifieke probleem, sou dit lyk. Alle reg, sodat dit is goed. En kan iemand 'n plekhouer vir 5? Kom op. Ons kry jy die volgende keer. 

Alle reg, sodat now-- en As 'n eenkant, die name Ek is nie die maak melding van reg nou, pred wyser, voorganger wyser en nuwe wyser, wat net die name gegee in die voorbeeld kode aan die wysers of my hande dit is soort van wys rond. Wat is jou naam? 

Publiek: Christine. 

David J. Malan Christine. Welkom aan boord. Alle reg, so laat ons nou kyk 'n Bietjie meer irriterende scenario, waardeur ek wil voeg iets soos 26 in hierdie. 20? Wat? Hierdie are-- goeie ding ons het hierdie pen. Alle reg, 20. As iemand kan nog 'n stukkie van kry papier gereed, net in case-- alles reg. O, interessant. Wel, dit is 'n voorbeeld van 'n lesing fout. OK so wat is jou naam nou weer? Publiek: Julia. David J. Malan Julia, kan jy pop uit en maak asof jy was nooit daar? OK, dit het nooit gebeur nie. Dankie. So dink ons ​​wil voeg Julia in hierdie verband lys. Sy is die nommer 20. En natuurlik is sy gaan om te behoort aan die begin-- nie wys nie enigiets nie. So jou hand kan soort wees down nul of 'n gemors waarde. Kom ons vertel die vinnige storie. Ek wys op nommer 5 hierdie tyd. Dan kyk ek 9. Dan gaan ek 17. Dan gaan ek 22. En ek besef, ooh, Julia behoeftes om te gaan voor 22. So wat moet gebeur? Wie se hande nodig om te verander? Julia se, myne, or-- Wat is jou naam nou weer? 

GEHOOR: Christen. 

David J. Malan Christelike of? 

Publiek: Andy. 

David J. Malan Andy. Christen of Andy? Andy nodig om te wys op? Julia. Alle regte. So Andy, wil jy om te wys op Julia? Maar wag 'n minuut. In die storie tot dusver Ek is die soort van 'n in beheer is, in die sin dat wyser is die ding wat beweeg deur die lys. Ons kan 'n naam vir Andy, maar daar is geen veranderlike genoem Andy. Die enigste ander veranderlike ons het, is eerste, wie verteenwoordig deur Gabe. 

So dit is eintlik die rede waarom so dusver het ons nie nodig nie. Maar nou op die skerm is daar noem weer van pred wyser. So laat my meer duidelik. As dit is wyser, ek het 'n beter 'n bietjie meer intelligent oor my iterasie. As jy nie omgee nie my gaan hier deur weer, wys hier, wys hier. Maar laat my 'n pred wyser, voorganger wyser, wat soort wat dui op die element Ek was net op. So toe ek hier gaan, nou my linkerhand updates. Wanneer ek gaan hier my linkerhand updates. En nou, ek het nie net 'n verwysing na die element wat gaan na Julia, Ek het nog 'n verwysing na Andy, die element voor. So jy toegang het, in wese, broodkrummels, as jy wil, om al die nodige verwysings. 

So as ek wys op Ek en Andy is ook daarop op Christelike, wie se hande moet nou elders wys? So Andy kan nou wys op Julia. Julia kan nou wys op Christelike. Omdat sy kan kopieer my regterhand se wyser. En dit effektief jy sit terug na hierdie plek hier. Dus, in kort, selfs al is dit neem ons soort ewig om werklik te werk 'n gekoppel lys, besef dat die bedrywighede is relatief eenvoudig. Dit is van een, twee, drie reëls van die kode uiteindelik. Maar toegedraai rondom dié reëls van die kode vermoedelik is 'n bietjie van die logika wat effektief vra die vraag, waar is ons? Is ons aan die begin, die middel, of die einde? 

Nou, daar is beslis 'n paar ander bedrywighede wat ons kan implementeer. En hierdie foto's hier net uitbeeld wat ons nou net gedoen het met die mens. Wat van die verwydering? As ek wil, byvoorbeeld, verwyder die nommer 34 of 55, Ek kan dieselfde soort kode het, maar ek gaan een of twee stappe nodig. Want wat is nuut? As ek verwyder iemand aan die einde, soos nommer 55 en dan 34, wat ook moet verander as ek dit doen? Ek moet nie evict-- Wat is jou naam nou weer? 

Publiek: Jack. 

David J. Malan Jack. Ek moet nie net evict-- gratis Jack, so letterlik bel gratis Jack, of ten minste die wyser daar ook, maar nou wat nodig is om te verander met Peter? Sy hand beter begin wys het. Omdat so gou as ek bel gratis op Jack, as Peter se steeds wys na Jack en ek dus hou dwars die lys en toegang tot hierdie wyser, Dis toe dat ons ou vriend segmentering fout kan eintlik skop. Want ons het die lig van die geheue terug na Jack. 

Jy kan daar bly ongemaklik vir net 'n oomblik. Want ons het net 'n paar finale bedrywighede te oorweeg. Die verwydering van die hoof van die lys, of die beginning-- en hierdie een se 'n bietjie irriterend. Want ons het om te weet dat Gabe is 'n soort van spesiale in hierdie program. Omdat inderdaad, hy het sy eie wyser. Hy is nie net om daarop te, soos byna almal anders hier. 

En toe die hoof van die lys is verwyder, wie se hande moet nou verander? Wat is jou naam nou weer? 

Publiek: Christine. 

David J. MALAN: Ek is verskriklik by name, blykbaar. So Christine en Gabe, wie se hande nodig om te verander wanneer ons probeer Christine te verwyder, nommer 5, van die prentjie? OK, so kom ons doen Gabe. Gabe gaan wys, vermoedelik, op nommer 9. Maar wat volgende moet gebeur? Publiek: Christine moet nul [onhoorbaar]. David J. Malan OK, moet ons waarskynlik make-- Ek het gehoor "null" iewers. Publiek: Null en gratis haar. David J. Malan null wat? Publiek: Null en gratis haar. David J. Malan Null en gratis haar. So dit is baie maklik. En dit is ideaal dat jy nou soort van wat daar staan, nie deel uitmaak. Omdat jy het al ontkoppelde uit die lys. Jy het effektief is weeskinders uit die lys. En so het ons het 'n beter roep nou gratis op Christine dat die geheue terug te gee. Anders elke keer as ons verwyder 'n knoop van die lys ons kan maak die lys korter, maar nie eintlik afneem die grootte in die geheue. En so, as ons hou toe te voeg en toe te voeg, om dinge op die lys, my rekenaar kan kry stadiger en stadiger en stadiger, want ek is besig om van die geheue, selfs al is ek nie eintlik gebruik Christine se grepe geheue nie. 

So op die ou end is daar ander scenario's, van course-- verwydering in die middel, verwydering aan die einde, soos ons gesien het. Maar die meer interessant uitdaging is nou gaan wees om presies te oorweeg wat die loop van die tyd is. So nie net kan jy jou stukkies papier, indien, Gabe, jy sal nie omgee om almal 'n stress bal. Baie dankie aan ons gekoppel lys vrywilligers hier, as jy kon. 

[Applous] 

David J. Malan Alle regte. So 'n paar van die analitiese vrae dan, as ek kon. Ons het gesien dat hierdie notasie voor, groot O en omega, bogrense en laer perke op die loop van die tyd van 'n paar algoritme. So laat ons kyk net 'n paar vrae. 

Een, en ons het gesê dit voor, wat is die loop tyd van soeke na 'n lys in terme van die groot O? Wat is 'n bogrens op die lopende tyd van soek na 'n geskakelde lys soos toegepas deur ons vrywilligers hier? Dit is groot O van n, lineêr. Want in die ergste geval, die element, soos 55, ons dalk op soek na mag wees waar Jack was, al die pad aan die einde. En ongelukkig, in teenstelling met 'n verskeidenheid ons kan nie fancy hierdie tyd. Selfs al is almal van ons mense was gesorteer van die klein elemente, 5, al die pad tot by die groter element, 55, dit is gewoonlik 'n goeie ding. Maar wat beteken dat die aanname nie langer toelaat dat ons te doen? Publiek: [onhoorbaar] David J. Malan weer sê? Publiek: Random toegang. David J. Malan Random toegang. En op sy beurt beteken dit dat ons nie meer gebruik swak nulle, intuïsie, en vanselfsprekendheid van die gebruik van binêre soek en te verdeel en oorwin. Want selfs al is ons mens kon duidelik sien dat Andy of Christian was ongeveer in die middel van die lys, Ons weet net dat as 'n rekenaar deur skimming die lys van die begin af. So ons het opgegee dat ewekansige toegang. 

So groot O van N is nou die boonste gebind op ons soek tyd. Wat van omega van ons soek? Wat is die ondergrens op soek vir 'n paar nommer in die lys? Publiek: [onhoorbaar] David J. Malan weer sê? Publiek: Een. David J. Malan Een. So konstante tyd. In die beste geval, Christine is inderdaad aan die begin van die lys. En ons is op soek na nommer 5, so ons het haar. So geen groot deal. Maar sy het om te wees by die begin van die lys in hierdie geval. Wat van iets soos Verwyder? Wat gebeur as jy 'n element te verwyder? Wat is die bogrens en ondergrens op die verwydering van iets uit 'n gekoppelde lys? Publiek: [onhoorbaar] David J. Malan weer sê? Publiek: n. David J. Malan N is inderdaad die bogrens. Want in die ergste geval ons probeer Jack te verwyder, soos ons nou net gedoen het. Hy is al die pad aan die einde. Neem ons vir ewig, of N stappe om hom te vind. So dit is 'n bogrens. Dit is lineêre, seker nie. En die beste geval loop van tyd, of die onderste grense in die beste geval sou konstante tyd. Omdat ons dalk probeer om te verwyder Christine, en ons het net kry gelukkig Sy is aan die begin. Wag nou 'n minuut. Gabe was ook aan die begin, en ons het ook te werk Gabe. So dit was nie net 'n stap. So is dit inderdaad konstante tyd, in die beste geval, die kleinste element te verwyder? Dit is, selfs al is dit dalk twee, drie, of selfs 100 reëls van die kode, As dit is dieselfde aantal lyne, nie in 'n paar lus, en onafhanklik van die grootte van die lys, absoluut. Die verwydering van die element by die begin van die lys, selfs as ons te doen het met Gabe, is steeds konstant tyd. 

So dit lyk soos 'n groot stap agteruit. En wat 'n vermorsing van tyd As in week een en week zero ons het nie net pseudokode kode, maar die werklike kode iets wat log te implementeer basis N, of teken, maar eerder van N, basis 2, in terme van sy lopende tyd. So hoekom die klink sou ons wil begin die gebruik van iets soos 'n geskakelde lys? Ja. 

Publiek: So jy kan byvoeg elemente in die skikking. David J. Malan So kan jy voeg elemente in die skikking. En dit is ook tematiese. En ons sal voortgaan om te sien dit is hierdie kompromis, baie soos ons gesien het 'n trade-off met merge soort. Ons kan regtig bespoedig soek of te sorteer, eerder As ons spandeer 'n bietjie meer ruimte en 'n bykomende stuk van 'n geheue of 'n skikking merge soort. Maar ons meer bestee ruimte, maar ons tyd te bespaar. In hierdie geval, ons is gee tyd, maar ons is besig om buigsaamheid, dinamika as jy wil, wat waarskynlik 'n positiewe kenmerk. 

Ons is ook die besteding van die ruimte. In watter sin is 'n gekoppelde lys duurder in terme van ruimte as 'n skikking? Waar is die ekstra ruimte vandaan? Ja? 

Publiek: [onhoorbaar] wyser. 

David J. Malan Ja, ons ook die wyser. So dit is minorly irriterende in wat nie meer is Ek stoor net 'n int 'n int te verteenwoordig. Ek stoor 'n int en 'n wyser, wat ook 32 stukkies. So ek letterlik verdubbel die bedrag van die ruimte wat betrokke is. So dit is 'n trade-off nie, maar dit is in die geval van int. Veronderstel dat jy nie stoor int, maar veronderstel elkeen van hierdie reghoeke of elk van hierdie mense was verteenwoordig 'n woord, 'n Engelse woord wat dalk vyf karakters, 10 karakters, miskien selfs meer. Dan voeg net 32 ​​meer stukkies dalk minder van 'n groot deal. 

Wat gebeur as elkeen van die studente in die demonstrasie was letterlik student structs wat het name en huise en miskien telefoonnommers en Twitter hanteer en dies meer. So al die velde het ons begin praat oor die ander dag, veel minder van 'n groot deal as ons nodes kry meer interessant en groot te spandeer, eh, 'n bykomende wyser net om hulle te skakel. Maar inderdaad, dit is 'n trade-off. En inderdaad, die kode meer kompleks, soos jy sal sien deur skimming deur daardie spesifieke voorbeeld. Maar wat as daar sommige heilige graal hier. Wat as ons nie 'n stap te neem nie agtertoe, maar 'n groot stap vorentoe en implementering van 'n data struktuur via wat ons elemente soos Jack of kan vind Christine of enige ander elemente in hierdie verskeidenheid in ware konstante tyd? Soek konstant. Verwyder konstant. Insetsel is konstant. Al hierdie bedrywighede is konstant. Dit sou ons heilige graal wees. En dit is waar ons sal haal die volgende keer. Sien jy dan.