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

Dit is CS50, en dit is die begin van die Week 6, so 'n paar nuwe tools is nou beskikbaar vir jou voordeel te trek uit, waarvan die eerste CS50 Style genoem. Kans is as jy soos my of enige van die onderrig-genote, het jy waarskynlik 'n program gesien wie se styl lyk 'n bietjie iets soos hierdie. Miskien het jy begin sny 'n paar hoeke laat in die nag, of jy sal hanteer dit later, en dan 'n TF of CA kom gedurende kantoorure. Dan is dit moeilik vir ons om te lees. Wel, hierdie kode is sintakties korrek, en dit sal stel, en dit sal eintlik loop. Maar dit is beslis nie 'n 5 vir styl. 

Maar nou, as ons gaan in hierdie gids hier- en kennis dat ek conditions2.c- en ek loop hierdie nuwe gebod, style50, op hierdie lêer conditions2.c, Enter, opmerk dat dit my in kennis gestel dat dit is gestileerd. Gedit opgemerk dat die lêer op die skyf verander is, en as ek kliek herlaai, is nou al jou probleme geoutomatiseer. [Applous] Dit is een van die dinge wat ons gedoen het hierdie naweek. Besef dat dit onvolmaak is, want daar is 'n paar kode dat dit net sal nie in staat wees om perfek te stileer, maar besef dit is nou 'n instrument wat jy kan neem voordeel van al was dit net om op te ruim sommige van die meer errantly geplaas krullerige draadjies en die wil. 

Maar meer dwingende is nou CS50 Check. Met CS50 Check, kan jy eintlik dieselfde korrektheid toetse verrig op jou eie kode wat die onderrig genote in staat is om te. Dit is 'n command line nut wat kom nou in die toestel so gou as wat jy doen 'n update50 soos per pset 4 spesifikasies, en jy gebruik dit in wese soos hierdie. Jy loop die opdrag check50. Dan moet jy slaag in 'n command line argument, of meer algemeen bekend as 'n skakel of 'n vlag. In die algemeen, is dinge wat koppeltekens genoem 'n skakelaar aan 'n command line program, so-c spesifiseer die kontrole wat jy wil uit te voer. 

Die toetse wat jy wil uit te voer is uniek geïdentifiseer deur hierdie string, 2012/pset4/resize. Met ander woorde, dit is net 'n arbitrêre, maar unieke string wat ons gebruik om te identifiseer pset 4 se korrektheid toetse. En dan moet jy spesifiseer 'n spasie geskei lys van die lêers wat jy wil oplaai CS50 Check vir ontleding. Byvoorbeeld, as ek gaan in my oplossing hier vir resize.c- laat my oop te maak 'n groter terminale venster- en ek gaan voort en loop laat ons sê check50-c 2012/pset4/resize, en dan het ek gaan voort en gee die name van die lêers, resize.c, en dan druk Enter dit saamgepers, dit upload, dit kontroleer of dit, en ek versuim het om 'n hele klomp van die toetse. Die een in rooi op links bo sê dat resize.c en bmp bestaan. Dit was die toets. Dit was die vraag wat ons gestel het. En dit is ongelukkig omdat die antwoord vals was. Sê die wit teks onder dit verwag bmp.h om te bestaan, en dis net my skuld. Ek het vergeet om dit te laai nie, so ek moet beide lêers te laai, resize.c en bmp.h. Maar kyk nou na al die ander toetse in geel omdat hulle nie loop nie, en so die smiley gesig is vertikale, want hy is nie gelukkig of hartseer, maar ons het dat die probleem reg te stel in rooi voor die ander tjeks sal loop. 

Laat ek dit regmaak. Laat my uitzoomen en heruitzend hierdie, hierdie keer met bmp.h ook op die command line, Enter, en nou as alles goed gaan, dit gaan om te kyk en dan terug gevolg van hou asem- al die groen, wat beteken dat ek regtig goed doen op pset 4 tot dusver. Jy kan sien en aflei uit die beskrywende teks hier presies wat dit is wat ons getoets het. Ons getoets het, die eerste keer nie die lêers bestaan? Ons het toe getoets doen resize.c saamstel? Toe het ons getoets het, beteken dit nie die grootte van 'n 1x1-pixel BMP wanneer n, die grootte van faktor, is 1. Nou, as jy het geen idee wat n, sal jy wanneer jy duik in pset 4, maar dit is net 'n gesonde verstand gaan om seker te maak dat jy nie resizing 'n beeld as die grootte van faktor is 1. Indien, in teenstelling, is dit die grootte van 'n 1x1 pixel na 'n 1x1 pixel BMP 2x2 korrek wanneer n 2, dan is insgelyks, my vorm dienooreenkomstig. 

In kort, hierdie is bedoel om, een, die kruising van die vingers uit die vergelyking reg voordat jy 'jou pset. Jy sal presies weet wat jou TF binnekort sal weet wanneer jy gaan oor die stuur van sommige van hierdie probleem stelle, en ook die pedagogiese motivering is regtig te sit die geleentheid om in die voorkant van jou, sodat wanneer jy weet a priori dat daar foute in jou kode en toetse is wat nie geslaag het, jy kan sit in 'n meer effektiewe tyd aan die voorkant om die probleme op te los eerder as verloor punte, kry terugvoering van jou TF, en gaan dan, "Ahh," soos ek uitgepluis dat uit. Nou ten minste daar is 'n hulpmiddel om te help jy vind dat. Dit gaan nie om uit te wys waar die fout is, maar dit sal jou vertel wat is simptomaties is van dit. 

Besef nou die toetse is nie noodwendig volledig nie. Net omdat jy 'n skerm vol van groen smiley gesigte beteken nie dat jou kode is volmaak nie, maar dit beteken dat dit geslaag het om sekere toetse voorgeskryf deur die spec. Soms sal ons nie vry van tjeks. Byvoorbeeld, detective verhaal, een van die aspekte van pset 4, is 'n soort van teleurstellend as ons gee jou die antwoord as wat dit is, en daar is 'n aantal maniere om te openbaar wat die persoon is in daardie rooi geraas. Die spec sal altyd spesifiseer in die toekoms vir pset 5 af wat bestaan ​​kontroleer vir jou. Jy sal sien daar is hierdie wit URL aan die onderkant. Vir nou, dit is net diagnose uitloop. As jy die URL besoek, kry jy 'n hele klomp van die gek, kriptiese boodskappe dat jy is welkom om te kyk deur, maar dit is meestal vir die personeel sodat ons kan diagnoseer en te ontfout foute in check50 self. 

Sonder ado, laat ons beweeg aan waar ons opgehou het. CS50 biblioteek wat ons as vanselfsprekend aanvaar vir 'n paar weke, maar dan verlede week, het ons begin peeling terug een van die lae van dit. Ons het begin sit eenkant string ten gunste van wat plaas? [Studente] Char. Char *, wat is 'n char * al die tyd, maar nou het ons nie voor te gee dat dit 'n werklike data string-tipe. Inteendeel, dit is 'n sinoniem van spesies vir char * en 'n string is 'n reeks van karakters, so hoekom maak dit sin snare te stel as char * s? Wat beteken 'n char * verteenwoordig in die konteks van hierdie konsep van 'n string? Ja >> [Studente] Die eerste karakter. Goed, die eerste karakter, maar nie heeltemal die eerste karakter. Dit is die [Studente] Adres. Goed, die adres van die eerste karakter. Al wat nodig is om 'n string te verteenwoordig in 'n rekenaar se geheue is net die unieke adres van sy heel eerste byte. Jy hoef nie eens te weet hoe lank dit is want hoe kan jy figuur wat uit dinamies? [Studente] String lengte. Jy kan bel string lengte, 'n uitstekende, maar hoe werk string lengte? Wat doen dit? Ja. [Studente] hou gaan totdat jy die null karakter. Ja, presies, is dit iterate net met 'n for-lus, terwyl loop, ongeag van * tot aan die einde en die einde word verteenwoordig deur \ 0, die sogenaamde nul karakter, nul, moet nie verwar word met null, wat is 'n wyser, wat sal kom in 'n gesprek vandag weer. 

Ons geskil terug 'n laag van getint, en dan het ons 'n blik op GetString, en dat beide van daardie werksaamhede, of regtig onthou, GetString, was die gebruik van 'n sekere funksie om werklik te verwerk, is dat, lees of te analiseer, die gebruiker se insette. En wat was dat die nuwe funksie? Scanf of sscanf. Dit kom eintlik in 'n paar verskillende geure. Daar is scanf, daar is sscanf, daar is fscanf. Vir nou, al is, laat se fokus op die een wat die meeste maklik geïllustreer, en laat my gaan voort en oop te maak in die toestel 'n lêer soos hierdie, scanf1.c. Dit is 'n super eenvoudige program, maar wat nie iets wat ons nog nooit voorheen gedoen sonder die hulp van die CS50 biblioteek. Dit kry 'n int van 'n gebruiker. Hoe werk dit? Wel, in line 16 daar, sien dat ons 'n int genoem x verklaar, en op hierdie punt in die verhaal, wat is die waarde van x? [Onhoorbaar student reaksie] [David M.] Right, wie weet, sommige vullis waarde potensieel, so in 17, ons het net vir die gebruiker gee my 'n nommer, asseblief, en stap 18 is waar dit raak interessant. Scanf blyk 'n idee van printf te leen in die sin dat dit gebruik hierdie formaat kodes in aanhalingstekens. % D is natuurlik 'n desimale getal. Maar hoekom is ek wat in & x in plaas van net x? Die voormalige is korrek. Ja. [Onhoorbaar student reaksie] Presies, indien die doel van hierdie program, soos die funksie getint self, is om 'n int te kry van die gebruiker wat ek kan slaag funksies al die veranderlikes wat ek wil, maar as ek nie slaag nie hulle deur verwysing of deur adres of by pointer, al sinoniem vir vandag se doeleindes, dan is dat die funksie het geen vermoë om die inhoud van daardie veranderlike te verander. Dit sal in 'n kopie, net soos die karretjie weergawe van swap dat ons het gepraat oor 'n paar keer nou. 

Maar in plaas daarvan, deur dit te doen en x, ek letterlik in wat verbygaan? [Studente] Die adres. >> Die adres van x. Dit is soos die trek van 'n kaart vir die funksie met die naam scanf en sê hier, dit is aanwysings na 'n stuk van die geheue in die rekenaar wat jy kan gaan stoor sommige heelgetal. Ten einde vir sscanf te doen noudat wat die operateur, is watter stuk van die sintaksis dit gaan te hê om te gebruik Selfs al kan ons dit nie sien nie, want iemand anders het hierdie funksie? Met ander woorde - wat is dit? [Studente] X gelees. Daar gaan 'n lesing, maar slegs met betrekking tot x hier. As scanf word verby die adres van x, sintakties, watter operateur verbind tot êrens bestaan binnekant van scanf se implementering sodat scanf kan eintlik skryf 'n aantal 2 na daardie adres? Ja, so het die *. Onthou dat die * is ons dereference operateur, wat in wese beteken daar gaan. 

As jy is oorhandig 'n adres, soos hier die geval is, scanf is waarskynlik as ons werklik het om die bronkode- * x of die ekwivalent daarvan om werklik te gaan na die adres en daar 'n bietjie waarde te doen. Nou, as vir hoe scanf kry insette van die sleutelbord, ons sal beweeg ons hande uit vir vandag. Net aanneem dat die bedryfstelsel kan sscanf om te praat aan die gebruiker se sleutelbord, maar op hierdie punt nou in line 19, wanneer ons net druk x, dit blyk die geval te wees wat scanf het 'n int in x. Dit is presies hoe scanf werk, en onthou verlede week Dit is presies hoe GetString en getint en sy ander familie van funksies uiteindelik werk, al is dit met 'n effense afwyking soos sscanf, wat beteken dat 'n string in plaas van die sleutelbord te scan. Maar laat ons neem 'n blik op 'n klein afwyking van hierdie. Ek het eintlik In scanf2, screwed up. Wat is verkeerd en ek sal die kommentaar wat verduidelik soveel verberg wat is fout met hierdie program, weergawe 2? Wees so tegniese as moontlik hierdie tyd. Dit lyk redelik goed. Dit is mooi ingekeep nie, maar okay, hoe oor laat snoei dit korter vrae? Line 16. Wat is lyn 16 te doen in 'n presiese maar tegniese Engels? 'N bietjie ongemaklik. Ja, Michael. [Studente] Dit verwys na die eerste letter van 'n string. 

Okay, naby. Laat my dat 'n bietjie tweak. Wys na die eerste letter van 'n string, jy waarby 'n veranderlike genoem buffer wat verwys na die eerste adres van 'n string, of liewer, dit sal meer spesifiek na 'n char wys. Kennisgewing dit is eintlik nie te wys op enige plek, want daar is geen opdrag operateur. Daar is geen gelyke teken, sodat alles wat ons doen, is die toekenning van die veranderlike genaamd buffer. Dit gebeur te wees 32 stukkies, want dit is 'n wyser, en die inhoud van die buffer vermoedelik uiteindelik sal 'n adres van 'n char bevat, maar vir nou, wat beteken buffer bevat? Net 'n paar pseudo, wie weet, sommige vullis waarde, want ons het nie uitdruklik dit geïnisialiseer word, so moet ons nie aanvaar enigiets. Okay, so nou lyn 17 wat nie in lyn 17? Miskien is dit sal warm hierdie up. Dit druk 'n string, reg? Dit druk String asseblief. 

Line 18 is 'n soort van bekende nou dat ons nou net gesien het 'n variansie van hierdie maar met 'n ander formaat kode, so in lyn 18, ons vertel scanf hier is die adres van 'n stuk van die geheue. Ek wil in 'n tou om jou te bel, soos geïmpliseer deur% s, maar die probleem is dat ons nie 'n paar van die dinge wat hier gedoen het. Wat is een van die probleme? [Studente] Dit is probeer om 'n null-aanwijzer te dereference. Goed, null, of net anders onbekend wysers. Jy inhandiging scanf 'n adres, maar jy het net 'n oomblik gelede gesê dat adres is 'n paar vullis waarde, want ons het nie eintlik dit toewys aan enigiets, en sodat jy vertel scanf effektief gaan sit 'n string hier, maar ons weet nie waar is hier nog, so ons het eintlik nie toegeken geheue vir buffer. Verder, wat is jy ook nie eens vertel scanf? Veronderstel dit was 'n stuk van die geheue, en dit was nie 'n gemors waarde, maar jy nog steeds nie vertel scanf iets belangrik. [Studente] Waar dit eintlik is, die ampersand. Ampersand, so in hierdie geval, is dit okay. Omdat die buffer is reeds as 'n wyser verklaar met die * stuk van sintaksis, het ons nie nodig ampersand te gebruik want dit is reeds 'n adres, maar ek dink ek het dit gehoor hier. [Studente] Hoe groot is dit? Goed, ons nie vertel scanf hoe groot hierdie buffer is, wat beteken dat selfs as buffer was 'n wyser, ons sê scanf, het hier 'n string, maar hier kan wees 2 grepe, kan dit 10 grepe, kan dit 'n megabyte. Scanf het geen idee nie, want dit is 'n stuk van die geheue vermoedelik, dit is nie Nog 'n string. Dit is net 'n string wanneer jy skryf karakters en 'n \ 0 tot daardie stuk van die geheue. Nou is dit is net 'n stuk van die geheue. Scanf sal nie weet wanneer om te stop deur skriftelik daarvoor aansoek te doen by daardie adres. 

As jy 'n paar voorbeelde in die verlede waar ek lukraak op die sleutelbord getik onthou probeer om oor te loop van 'n buffer, en ons het gepraat oor presies wat op Vrydag. As 'n teenstander spuit op een of ander manier in jou program 'n veel groter woord of sin of frase wat jy verwag jy kan oorrompel 'n stuk van die geheue, wat slegte gevolge kan hê, soos die neem van oor die hele program self. Ons moet dit op een of ander manier los. Laat my zoom uit en gaan in weergawe 3 van hierdie program. Dit is 'n bietjie beter. In hierdie weergawe, let op die verskil. In lyn 16, verklaar ek weer 'n veranderlike genoem buffer, maar wat is dit nou? Dit is 'n verskeidenheid van 16 karakters. Dit is goed, want dit beteken ek kan nou scanf vertel hier is 'n werklike stuk van die geheue. Jy kan amper dink van skikkings as verwysings nou, selfs al is hulle nie eintlik ekwivalent. Hulle sal anders optree in verskillende kontekste. Maar dit is beslis die geval dat die buffer verwysingstegnieke 16 aangrensende karakters want dit is wat 'n skikking is en is vir 'n paar weke nou. 

Hier, ek vertel scanf hier is 'n stuk van die geheue. Hierdie keer, dit is eintlik 'n stuk van die geheue, maar waarom is hierdie program nog exploit? Wat is nog steeds verkeerd? Ek het gesê gee my 16 bytes maar- [Studente] Wat gebeur as hulle tik in meer as 16? Presies, wat as die gebruiker tipes in 17 karakters of 1700 karakters? Om die waarheid te sê, laat ons kyk of ons kan nie reis oor hierdie fout nou. Dit is beter, maar nie volmaak nie. Laat my voort te gaan en uit te voer maak scanf3 hierdie program saam te stel. Laat ek hardloop scanf3, String asseblief: hello, en ons lyk okay wees. Laat ek probeer om 'n bietjie langer een, hallo daar. Goed, kom ons nie daar hallo hoe gaan dit vandag, Enter. Aan die soort van gelukkig hier, laat ons sê hallo daar hoe gaan dit met jou. Damn dit. Okay, so ons het gelukkig. Kom ons kyk of ons dit nie kan regmaak. Nee, dit is nie van plan om my te laat kopieer. Kom ons probeer dit weer. Alle reg, staan. Ons sal sien hoe lank ek kan voorgee om te fokus terwyl jy nog om dit te doen. Damn dit. Dit is nogal toepaslik, eintlik. Daar gaan ons. Punt gemaak. 

Dit, verleentheid al is dit ook is, dit is ook een van die bronne van groot verwarring wanneer die skryf van programme wat foute omdat hulle manifesteer slegs een keer in 'n rukkie soms. Die werklikheid is dat selfs as jou kode is heeltemal gebreek, dit dalk net heeltemal gebreek word een keer in 'n rukkie want soms, in wese wat gebeur is die bedryfstelsel ken 'n bietjie meer geheue as wat jy werklik nodig het om watter rede ook al, en so niemand anders is met behulp van die geheue na jou stuk van 16 karakters, so as jy gaan na 17, 18, 19, wat ook al, dit is nie so 'n groot deal. Nou, die rekenaar, selfs as dit nie crash op daardie punt, kan uiteindelik gebruik byte nommer 17 of 18 of 19 vir iets anders, By watter punt jou data wat jy daar te vestig, al is dit buitensporig lank, gaan kry oorskryf potensieel deur 'n ander funksie. Dit is nie noodwendig gaan om te bly ongeskonde, maar dit sal nie noodwendig veroorsaak 'n seg skuld. Maar in hierdie geval, het ek uiteindelik genoeg karakters dat ek wesenlik oorskry my segment van die geheue, en bam, die bedryfstelsel het gesê: "Jammer, dit is nie goed nie, segmentering skuld." 

En laat ons nou sien as wat nog hier in my directory kennis dat ek hierdie lêer hier, kern. Let daarop dat hierdie is weer 'n kern dump genoem. Dit is in wese 'n lêer wat bevat die inhoud van jou program se geheue by die punt waar dit neergestort het, en net 'n klein voorbeeld om hier te probeer laat my gaan hier en hardloop gdb op scanf3 en dan 1/3 argument genoem kern spesifiseer, en hier opmerk dat as ek die kode lys, sal ons in staat wees om te begin soos gewoonlik met gdb loop deur middel van hierdie program, en ek kan hardloop en so gou as wat ek getref het-as met die stap opdrag in gdb- so gou as ek die potensieel buggy lyn getref nadat tik in 'n groot string, Ek sal in staat wees om werklik te identifiseer dit hier. Meer inligting oor hierdie, maar in artikel in terme van kern dumps en die wil sodat jy kan eintlik poke rond binnekant van die kern dump en kyk op watter lyn die program gedruip het jy. Enige vrae dan op wysers en adresse? Want vandag op, ons gaan om te begin neem as vanselfsprekend aanvaar dat hierdie dinge bestaan en ons weet presies wat hulle is. Ja. 

[Studente] Hoe kom jy nie 'n ampersand na die volgende aan die deel- Goeie vraag. Hoe kom ek het nie 'n ampersand te sit langs die karakter array soos ek gedoen het voorheen met die meeste van ons voorbeelde? Die kort antwoord is skikkings is 'n bietjie spesiale. Jy kan amper dink dat 'n buffer as eintlik 'n adres, en dit gebeur net so om die geval te wees dat die vierkantige hakienotasie is 'n gerief sodat ons kan gaan in bracket 0, bracket 1, bracket 2, sonder die * notasie te gebruik. Dit is 'n bietjie van 'n wit leuen omdat skikkings en wysers is, in werklikheid, 'n bietjie anders, maar hulle kan nie altyd dikwels, maar nie gebruik word nie uitruilbaar. In kort, as 'n funksie word verwag dat 'n wyser na 'n stuk van die geheue, jy kan slaag dit 'n adres wat deur malloc teruggestuur is, en ons sal sien malloc weer kort voor lank, of jy kan slaag dit die naam van 'n skikking. Jy hoef nie ampersand te doen met skikkings, want hulle is reeds wese graag adresse. Dit is die een uitsondering. Die vierkantige hakies maak hulle spesiaal. 

Kan jy 'n ampersand langs die buffer? Nie in hierdie geval. Dit sou werk nie, want, weer, van hierdie hoek geval waar skikkings is nie eintlik baie adresse. Maar ons sal miskien kom terug na wat voor lank met ander voorbeelde. Laat ons hier probeer om 'n probleem op te los. Ons het 'n datastruktuur wat ons het is gebruik vir 'n geruime tyd bekend as 'n skikking. Case in point, dit is wat ons moes net. Maar skikkings het 'n paar upsides en nadele. Skikkings is mooi waarom? Wat is een ding wat jy wil-tot die mate wat jy wil skikkings-oor skikkings? Wat is gerieflik oor hulle? Wat is dwingende? Hoekom het ons stel hulle in die eerste plek? Ja. [Studente] Hulle kan 'n baie van die data te stoor, en jy hoef nie 'n hele ding om te gebruik. Jy kan gebruik maak van 'n artikel. Goed, met 'n verskeidenheid wat jy kan 'n baie van die data stoor, en jy hoef nie noodwendig al van dit te gebruik, so kan jy overallocate, wat kan gerieflik wees as jy nie vooraf weet nie hoeveel van iets om te verwag. 

GetString is 'n perfekte voorbeeld. GetString, wat geskryf is deur ons, het geen idee hoeveel karakters om te verwag, so is die feit dat ons stukke van die aangrensende geheue kan toewys is goed. Skikkings ook 'n probleem wat ons het nou 'n paar weke gelede op te los waar u die kode begin oorgaan in iets baie swak ontwerp. Onthou dat ek 'n student struktuur Dawid geroep, en dan dit was eintlik 'n alternatief, maar, om met 'n veranderlike genoem naam en 'n ander veranderlike genoem, dink ek, die huis, en 'n ander veranderlike genaamd ID nie, want in daardie storie wou ek dan iets anders te stel graag Rob in die program, so toe het ek besluit om te wag 'n minuut, Ek nodig het om hierdie veranderlikes te hernoem. Kom ons noem my NAME1, ID1, house1. Kom ons noem Rob se NAME2, house2, ID2. Maar dan wag 'n minuut, wat oor Tommy? Dan het ons nog drie veranderlikes. Ons lei iemand anders, vier stelle van veranderlikes. Die wêreld het begin om te kry morsige baie vinnig, so het ons 'structs, en wat is dwingende oor 'n struct? Wat beteken 'n C struct laat jy doen? Dit is regtig 'n ongemaklike vandag. Wat >> [onhoorbaar student reaksie]? Ja, spesifiek, typedef kan jy 'n nuwe datatipe te skep, en struct, die struct navraag, kan jy kapselt konseptueel verwant stukke van data saam en daarna hulle noem iets soos 'n student. 

Dit was goed, want nou kan ons modelleer baie meer soort van konseptueel konsekwent die idee van 'n student in 'n veranderlike eerder as om na willekeur met een vir 'n string, een vir 'n ID, en so meer. Skikkings is mooi omdat hulle toelaat dat ons om te begin die skoonmaak van ons kode. Maar wat is nou 'n nadeel van 'n skikking? Wat kan jy doen nie? Ja. [Studente] Jy moet weet hoe groot dit is. Jy moet weet hoe groot dit is, so dit is soort van 'n pyn. Dié van julle met 'n vorige programming ervaring weet dat in baie tale, soos Java, kan jy vra 'n stuk van die geheue, veral 'n skikking, hoe groot is u, met 'n lengte, eiendom, om so te praat, en dit is regtig handig. In C, kan jy nie eens noem strlen op 'n generiese verskeidenheid omdat strlen, soos die woord impliseer, is slegs vir strykinstrumente, en jy kan uitvind die lengte van 'n string as gevolg van hierdie menslike konvensie met 'n \ 0, maar 'n skikking, meer generies, is net 'n stuk van die geheue. As dit is 'n verskeidenheid van ints, is daar nie tot 'n spesiale karakter aan die einde wag vir jou. Jy het om te onthou van die lengte van 'n skikking. Nog 'n nadeel van 'n skikking sy kop in GetString self. Wat is nog 'n nadeel van 'n skikking? Meneer, net ek en jy vandag. [Onhoorbaar student reaksie] >> Dit is wat? Dit is op die stapel verklaar. Goed, op die stapel verklaar. Hoekom het jy nie hou nie? [Studente], want dit raak weer gebruik. Dit word weer gebruik. Okay, as jy gebruik om 'n skikking geheue toeken, jy kan nie, byvoorbeeld, stuur dit terug, want dit is op die stapel. Goed, dit is 'n nadeel. En hoe oor 'n ander met 'n skikking? Sodra jy dit toeken, jy is soort van geskroef as jy meer ruimte nodig as dié skikking. 

Dan het ons ', onthou, malloc, wat aan ons gegee het die vermoë om dinamiese geheue toeken. Maar wat as ons probeer om 'n ander wêreld altesaam? Wat gebeur as ons wou 'n paar van die probleme op te los sodat ons plaas my pen het aan die slaap geraak hier- Wat gebeur as ons plaas wou in wese 'n wêreld wat nie meer soos hierdie? Dit is 'n skikking, en, natuurlik, hierdie soort van verswak wanneer ons die einde van die skikking getref het, en ek nou nie meer ruimte vir 'n ander heelgetal of 'n ander karakter. Wat gebeur as ons soort van preemptively goed sê, hoekom doen ons nie verslap hierdie vereiste dat al hierdie stukke van die geheue aangrensende rug aan rug, en waarom dit nie doen nie, wanneer ek nodig het 'n int of 'n char, gee my net ruimte vir een van hulle? En wanneer ek nodig het 'n ander, gee my 'n ander ruimte, en wanneer ek nodig het 'n ander, gee my 'n ander ruimte. Die voordeel van wat is nou dat as iemand anders neem die geheue hier, geen big deal nie. Ek sal hierdie bykomende stuk van die geheue hier en dan is hierdie een. 

Nou, die enigste vangs hier is dat dit byna voel soos ek het 'n hele klomp van verskillende veranderlikes. Dit voel soos vyf verskillende veranderlikes potensieel. Maar wat as ons 'n idee steel van snare waardeur ons die een of ander manier verbind hierdie dinge saam konseptueel, en wat as ek dit gedoen het? Dit is my baie swak getrek pyl. Maar veronderstel dat elk van hierdie stukke van die geheue wys na die ander, en hierdie man, wat geen broer of suster tot sy reg, het nie so 'pyl. Dit is in die feit wat genoem word 'n geskakelde lys. Dit is 'n nuwe data struktuur wat ons in staat stel om 'n stuk van die geheue toe te ken, en dan die ander, en dan die ander, en dan die ander, enige tyd wil ons tydens 'n program, en ons onthou dat hulle almal op een of ander manier verwante deur letterlik aaneenskakeling hulle saam, en ons het dit gedoen picturaal hier met 'n pyl. Maar in die kode, wat sou die meganisme via wat jy kan op een of ander manier verbind, amper soos Scratch, een stuk na 'n ander stuk? Ons kan gebruik maak van 'n wyser, reg? Omdat regtig die pyltjie wat gaan van die boonste linkerkantste blokkie, hierdie man hier aan hierdie een, kan binne bevat van hierdie vierkant nie net 'n paar ints, nie net 'n paar char, maar wat as ek eintlik toegeken 'n bietjie ekstra ruimte, sodat nou, elk van my stukke van die geheue, selfs al is dit gaan my kos, nou lyk 'n bietjie meer reghoekige waar een van die stukke van die geheue gebruik word vir 'n aantal, soos die aantal 1, en dan as hierdie man slaan die nommer 2, hierdie ander stuk van die geheue wat gebruik word vir 'n pyl, of meer konkreet, 'n wyser. En dink ek stoor die getal 3 hier terwyl Ek gebruik dit om te wys dat die man, en nou is hierdie man, laat ons veronderstel ek wil net drie sulke stukke van die geheue. Ek sal 'n streep trek deur, wat daarop dui null. Daar is geen addisionele karakter. 

Inderdaad, dit is hoe ons kan gaan oor die uitvoering van iets wat 'n geskakelde lys genoem. 'N geskakelde lys is 'n nuwe data struktuur, en dit is 'n stepping stone in die rigting van baie liefhebber data strukture wat begin om probleme op te los langs die lyne van die Facebook-tipe probleme en Google-tipe probleme waar jy het 'n groot datastelle, en dit nie meer sny dit om alles te contiguously stoor en gebruik om iets soos lineêre soek of selfs iets soos die binêre soek. Jy wil nog beter hardloop tye. Om die waarheid te sê, een van die Heilige Grails ons praat oor later hierdie week of volgende is 'n algoritme waarvan die looptyd is konstant. Met ander woorde, dit neem altyd die dieselfde hoeveelheid van die tyd maak nie saak hoe groot die inset is, en dit sou inderdaad dwingende, selfs meer so as iets logaritmiese. Wat is dit hier op die skerm? Elkeen van die reghoeke is presies wat ek net met die hand geteken het. Maar die ding wat al die pad aan die linkerkant is 'n spesiale veranderlike. Dit gaan om 'n enkele wyser wees nie, want die een Gotcha met 'n geskakelde lys, as hierdie dinge genoem word, is wat jy het om op te hang op een einde van die geskakelde lys. 

Net soos met 'n string, jy moet die adres van die eerste kar om te weet. Dieselfde deal vir geskakelde lyste. Jy het die adres van die eerste stuk van die geheue te leer ken as gevolg van daar af het, kan jy elke ander een. Nadeel. Watter prys ons betaal vir hierdie veelsydigheid van 'n dinamiese aansienlike data struktuur wat as ons ooit meer geheue nodig het, fyn, ken net nog een stuk en trek 'n verwysing van die ou na die nuwe stert van die lys? Ja. [Studente] Dit neem ongeveer twee keer soveel ruimte. Dit neem twee keer soveel ruimte, so dit is beslis 'n nadeel, en ons het dit gesien nadeel voor tussen tyd en ruimte en buigsaamheid waar deur die nou, ons hoef nie 32 stukkies vir elk van hierdie getalle. Ons regtig nodig het 64, 32 vir die aantal en 32 vir die wyser. Maar hey, ek het 'n 2 GB RAM. Voeg 'n ander 32 stukkies hier en hier lyk nie dat die groot van 'n deal. Maar vir groot datastelle, dit voeg beslis letterlik twee keer soveel. Wat is nou 'n ander nadeel, of watter funksie gee ons, as ons verteenwoordig lyste van dinge met 'n geskakelde lys en nie 'n skikking nie? [Studente] Jy kan nie deurkruis dit agteruit. Jy kan nie deurkruis dit agteruit, so jy is soort van geskroef as jy loop van links na regs met behulp van 'n lus of 'n while lus en dan moet jy besef, "O, ek wil om terug te gaan na die begin van die lys." Jy kan nie omdat hierdie wysers net gaan van links na regs as die pyle dui. 

Nou, kan jy dink aan die begin van die lys met 'n ander veranderlike, maar dit is 'n kompleksiteit in gedagte te hou. 'N skikking nie saak hoe ver jy gaan, kan jy altyd doen minus, minus, minus, minus en gaan terug waarvandaan jy gekom het. Wat is 'n ander nadeel hier? Ja. [Onhoorbaar student vraag] Jy kan dit so is, jy het eintlik net 'n datastruktuur bekend as 'n dubbel geskakelde lys voorgestel, en inderdaad, sou jy nog 'n wyser voeg aan elkeen van hierdie reghoeke wat die ander rigting gaan, die kop van is jy nou heen en weer kan deurkruis, die nadeel wat jy nou gebruik drie keer soveel geheue soos ons gebruik om te en ook die toevoeging van kompleksiteit in terme van die kode wat jy moet skryf dit reg te kry. Maar hierdie is almal miskien baie redelike werkinge, as die terugskrywing is meer belangrik. Ja. [Studente] Jy kan ook nie 'n 2D-geskakelde lys. Goed, jy kan nie regtig 'n 2D-geskakelde lys. Jy kan. Dit is nie naastenby so maklik as 'n skikking. Soos 'n skikking, jy oop bracket, geslote bracket, oop bracket, gesluit bracket, en jy kry 'n 2-dimensionele struktuur. Jy kan 'n 2-dimensionele geskakelde lys te implementeer as jy dit doen add-as jy 1/3 wyser voorgestel aan elkeen van hierdie dinge, en as jy dink oor 'n ander lys wat op jou 3D styl van die skerm vir almal van ons, wat net nog 'n ketting van 'n soort. Ons kan dit doen, maar dit is nie so eenvoudig soos die tik van oop bracket, vierkante bracket. Ja. [Onhoorbaar student vraag] Goed, so dit is 'n ware skopper. 

Hierdie algoritmes wat ons het, soos oh, binêre soek gaan verby, jy kan 'n skikking van getalle op die bord soek of 'n telefoon boek so veel vinniger as jy gebruik te verdeel en oorwin en 'n binêre soek algoritme, maar binêre soek benodig twee aannames. Een, dat die data gesorteer. Nou kan ons waarskynlik hou dit gesorteer, so miskien is dit is nie 'n probleem nie, maar binêre soek ook aanvaar wat jy gehad het random access tot die lys van getalle, en 'n skikking kan jy random access te hê, en deur random access, Ek bedoel as jy 'n skikking, hoeveel tyd neem dit jou te kry te bracket 0? Een operasie, gebruik jy net [0] en jy is reg daar. Hoeveel treë sal dit neem om te kry om plek 10? Een stap, jy gaan net na [10] en jy daar is. In teenstelling hiermee, hoe jy na die 10de heelgetal in 'n geskakelde lys? Jy het om te begin by die begin, omdat jy net onthou die begin van 'n geskakelde lys, net soos 'n string word onthou deur die adres van sy eerste kar, en dat 10th Int te vind of dat die 10de karakter in 'n string, jy moet die hele damn ding om te soek. 

Weereens, is ons nie die oplossing van al ons probleme. Ons is die bekendstelling van nuwe kinders, maar dit hang af van wat jy probeer om te ontwerp vir. In terme van die uitvoering van hierdie, kan ons 'n idee te leen van daardie student struktuur. Die sintaksis is baie soortgelyk, behalwe nou die idee is om 'n bietjie meer abstrak as huis en naam en ID. Maar ek stel voor dat ons 'n data struktuur in C wat genoem word node, as die laaste woord op die slide suggereer, binnekant van 'n nodus, en 'n node is net 'n generiese houer in rekenaarwetenskap. Dit word gewoonlik voorgestel as 'n sirkel of 'n vierkant of reghoek soos ons gedoen het. En in hierdie data struktuur, ons het 'n int, n, so dit is die getal wat ek wil om te stoor. Maar wat is hierdie tweede lyn, struct node * volgende? Hoekom is dit korrek is, of watter rol hierdie ding speel, selfs al is dit 'n bietjie kripties met die eerste oogopslag? Ja. [Onhoorbaar student reaksie] Presies, so die * soort buit dat dit is 'n wyser van een of ander aard. Die naam van die wyser is arbitrêr volgende, maar ons kan dit genoem het enigiets wat ons wil hê, maar wat doen dit wyser punt? [Studente] Nog node >> Presies, dit wys na 'n ander sodanige node. 

Nou, hierdie is 'n soort van 'n nuuskierigheid van C. Onthou dat C word gelees deur 'n samesteller van bo na onder, links na regs, wat beteken dat indien-dit is 'n bietjie anders as wat ons gedoen het met die student. Wanneer ons 'n student gedefinieer, het ons eintlik nie 'n woord nie. Dit het net gesê typedef. Dan het ons int id, string string huis, en dan student aan die onderkant van die struct. Hierdie verklaring is 'n bietjie anders, want weer, die C compiler is 'n bietjie dom. Dit gaan slegs om van bo na onder te lees, so as dit bereik die 2de lyn hier waar die volgende verklaar word en dit sien, oh, hier is 'n veranderlike genaamd volgende. Dit is 'n wyser na 'n struct node. Die opsteller gaan om te besef wat is 'n struct node? Ek het nog nooit gehoor het van hierdie ding voor, omdat die woord node anders kan verskyn nie tot op die bodem, so daar is hierdie oortolligheid. Jy het struct node om hier te sê, wat kan jy dan later verkort te danke aan typedef af hier, maar dit is omdat ons verwysing na die struktuur self binnekant van die struktuur. Dis die een Gotcha daar. 

'N paar interessante probleme gaan ontstaan. Ons het 'n lys van getalle. Hoe voeg ons in dit? Hoe soek ons ​​dit? Hoe verwyder ons van dit? Veral nou dat ons al hierdie wenke te bestuur. Jy het gedink wysers was soort van mind-buiging as jy het een van hulle net probeer om 'n int om dit te lees. Nou het ons 'n volledige lys is die moeite werd te manipuleer. Waarom neem ons nie ons 5-minute breek hier, en dan sal ons bring sommige mense op die verhoog te doen presies dit. 

C is baie meer pret as dit opgetree het. Wie sou letterlik wil eerste wees? Okay, kom op. Jy is die eerste. Wie sou wil wees 9? Okay, 9. Hoe oor 9? 17? 'N bietjie kliek hier. 22 en 26 in die voorry. En dan hoe oor iemand daar gewys. Jy is 34. Okay, 34, kom op maksimum. Eerste is daar. Okay, al vier van julle ouens. En wie het ons sê vir 9? Wie is ons 9? Wie wil regtig te wees 9? Alle reg, kom op, wees 9. Hier gaan ons. 34, sal ons julle ontmoet daar. Die eerste deel is julle lyk soos wat. 26, 22, 17, 'n goeie. As jy kan staan ​​uit na die kant, want ons gaan om jou te malloc in 'n oomblik. 

Goed, goed. Okay, uitstekend, so ons vra 'n paar vrae hier. En eintlik, wat is jou naam? >> Anita. Anita, okay, hier oor kom. Anita gaan om ons te help soort van los een van redelik eenvoudige vraag in die eerste, wat is hoe kry jy of 'n waarde is in die lys? Nou, let op dat die eerste, hier verteenwoordig deur Lucas, is 'n bietjie anders, en so sy stuk papier is doelbewus sywaarts want dit is nie heeltemal so hoog en neem nie soveel stukkies, alhoewel tegnies hy het dieselfde grootte papier gedraai. Maar hy is 'n bietjie anders in die sin dat hy slegs 32 stukkies vir 'n wyser, en al hierdie ouens is 64 stukkies, waarvan die helfte van die getal, waarvan die helfte is 'n wyser. Maar die wyser nie uitgebeeld word nie, so as julle ouens kan 'n bietjie ongemaklik Gebruik jou linkerhand om te wys op die persoon langs jou. En jy is nommer 34. Wat is jou naam? Ari. Ari, so werklik, in besit wees van die papier in jou regterhand, en linkerhand gaan reguit af. Jy verteenwoordig null aan die linkerkant. 

Nou is ons menslike beeld is baie konsekwent. Dit is eintlik hoe wysers werk. En as jy kan 'n bietjie opfrommel hierdie manier, so ek is nie in jou pad. Anita hier, vind ek die getal 22, maar neem 'n beperking van mense hou stukkies papier, maar dit is 'n lys, en jy het net Lucas om te begin met want hy is letterlik die eerste wyser. Veronderstel jy self is 'n wyser, en so moet jy ook die vermoë om te wys op iets. Hoekom het jy nie begin deur te wys presies wat Lucas wys? Goeie, en laat my verorden dit uit hier. Net ter wille van die bespreking, laat my toe om 'n leë bladsy. Hoe spel jy jou naam? >> Anita. Okay, Anita. Kom ons sê node * anita = lucas. Wel, moet ons nie noem julle lucas. Ons moet noem jy die eerste keer. Hoekom is dit in werklikheid in ooreenstemming met die werklikheid hier? Een, in die eerste bestaan ​​reeds. Eerste is vermoedelik iewers toegeken hier. Node * Eerste, en dit toegeken is 'n lys op een of ander manier. Ek weet nie hoe dit gebeur het. Wat gebeur het voor die klas begin. Hierdie geskakelde lys van die mens geskep is. En nou, op hierdie punt in die storie - dit is al op Facebook gaan blykbaar later op hierdie punt in die verhaal, het Anita geïnisialiseer om gelyk te wees na die eerste, Dit beteken nie dat Anita punte by Lucas. Inteendeel, sy wys wat hy wys na omdat die dieselfde adres en onder dieselfde naam wat is binnekant van Lucas se 32 stukkies - 1, 2, 3 is nou ook binnekant van Anita se 32 stukkies - 1, 2, 3. 

Vind nou 22. Hoe sou jy te werk gaan om dit te doen? Wat is dit? >> Point wat ookal. Verwys na wat ookal, so gaan voort en tree dit uit as beste wat jy kan hier. Goed, goed, en nou is jy wys op wat is jou naam met 22? Ramon. >> Ramon, so Ramon hou 22. Jy het nou 'n tjek gedoen. Is Ramon == 22, en indien wel, byvoorbeeld, kan ons terugkeer waar. Laat my terwyl hierdie ouens hier staan ​​ietwat ongemaklik laat my iets te doen vinnig soos Bool vind. Ek gaan om voort te gaan en sê (node ​​* lys, int n). Ek kom gou terug wees met julle ouens. Ek het net 'n kode te skryf. En nou is ek gaan om voort te gaan en doen, node * anita = lys. En ek gaan om voort te gaan en sê, terwyl (Anita = null). 

Die metafoor hier is 'n bietjie gerek, maar terwyl (anita = NULL!), Wat ek wil om dit te doen? Ek moet een of ander manier van verwysing die heelgetal dat Anita wys. In die verlede, toe ons strukture, wat 'n node is, ons gebruik die dot-notasie, en ons wil iets sê anita.n, maar die probleem hier is dat Anita nie 'n struct per se. Wat is sy? Sy is 'n wyser, so regtig, as ons wil dit dot te gebruik notasie- en dit gaan om doelbewus 'n bietjie kripties te kyk ons het iets te doen gaan net die Anita se linkerhand wys en dan kry die veld genaamd n. Anita is 'n wyser, maar wat is * anita? Wat kry jy wanneer jy na wat Anita wys? 'N struct, 'n node en 'n knoop, onthou, het 'n veld met die naam van n want dit het, onthou, hierdie 2 velde, langs en n, wat ons gesien het 'n oomblik gelede hier. 

Om werklik te boots in die kode, ons kan dit doen en sê as ((* anita) n == n), die n wat ek soek. Let daarop dat die funksie in die aantal wat ek omgee geslaag. Dan kan ek gaan voort en doen iets soos return true. Anders, as dit nie die geval is, nie wat ek wil om dit te doen? Hoe vertaal ek om te kodeer wat Anita het so intuïtief deur die loop deur die lys? Wat moet ek doen om hier te simuleer Anita neem dat die stap aan die linkerkant, dat die stap aan die linkerkant? [Onhoorbaar student reaksie] >> Wat is dit? [Onhoorbaar student reaksie] Goed, nie 'n slegte idee nie, maar in die verlede, toe ons dit gedoen het, het ons gedoen anita + + want dit sou die getal 1 byvoeg Anita wat sou tipies wys op die volgende persoon, soos Ramon, of die persoon langs hom, of die naaste aan hom persoon af die lyn. Maar dit is nie baie goed hier, want wat het hierdie ding lyk soos in die geheue? Nie dat. Ons het om te skakel. Dit lyk soos dit in die geheue, en selfs al het ek 1 en 2 en 3 naby aan mekaar getrek het, As ons regtig simuleer hierdie kan jy ouens, terwyl hy nog wys op die dieselfde mense, kan sommige van julle 'n ewekansige stap terug, sommige van julle 'n ewekansige stap vorentoe? 

Hierdie gemors is nog steeds 'n geskakelde lys, maar hierdie ouens kan enige plek in die geheue, so anita + + is nie van plan om te werk waarom? Wat is op plek anita + +? Wie weet. Dit is 'n paar ander waarde wat net so gebeur word interposed onder al van hierdie nodes deur die kans, omdat ons nie met behulp van 'n skikking. Ons toegeken elk van hierdie nodes individueel. Okay, as jy ouens kan julle skoon back-up. Laat my voor dat in plaas van anita + +, ons doen in plaas anita kry goed, hoekom ons nie gaan na watter Anita wys en dan doen. volgende? Met ander woorde, ons gaan na Ramon, wat hou van die getal 22, en dan volgende is asof Anita sou die kopiëring van sy linker hand wyser. Maar sy wou nie verder gaan as Ramon omdat ons gevind 22. Maar dit sou die idee wees. Nou, hierdie is 'n god aaklige gemors. Honestly, niemand sal ooit onthou hierdie sintaksis, en so gelukkig, dit is eintlik 'n bietjie doelbewuste-oh, het jy nie eintlik sien wat ek geskryf het. Dit sou meer oortuigend as wat jy kan. Voila! 

Agter die skerms, het ek die oplossing van die probleem op hierdie manier. Anita, om daardie stap te neem aan die linkerkant, eerste, ons gaan na die adres wat Anita wys en waar sy sal vind nie net n, wat ons net nagegaan word vir vergelyking se onthalwe, maar jy sal ook die volgende - in hierdie geval, Ramon se linkerhand verwys na die volgende nodus in die lys. Maar dit is die god-verskriklik gemors waarna ek vroeër verwys, maar dit blyk C laat ons vereenvoudig hierdie. In plaas van die skryf (* anita), kan ons plaas net skryf anita-> n, en dit is presies dieselfde ding funksioneel nie, maar dit is 'n baie meer intuïtief, en dit is 'n baie meer in ooreenstemming met die beeld wat ons het is teken al hierdie tyd met behulp van pyle. 

Ten slotte, doen wat ons moet doen is om aan die einde van hierdie program? Daar is een lyn van kode oorblywende. Teruggee wat? Vals is, want as ons deur die hele while lus en Anita is, in werklikheid, null, wat beteken sy het al die pad na die einde van die lys waar sy wys wat is jou naam nou weer? Ari >> Ari se linkerhand, wat null. Anita is nou null, en ek besef jy net hier staan ​​ongemaklik in limbo want ek gaan op 'n monoloog hier, maar ons sal behels dat jy weer in net 'n oomblik. Anita, is van nul by daardie punt in die verhaal, so die while lus beëindig, en ons het om terug te keer vals want as sy het al die pad na Ari se null pointer dan was daar geen nommer wat sy in die lys gesoek. Ons kan skoon up, maar dit is 'n redelik goeie implementering van 'n traversal funksie, 'n funksie vir 'n geskakelde lys. Dit is nog steeds lineêre soek, maar dit is nie so eenvoudig as + + 'n wyser of + + 'n i-veranderlike want nou kan ons nie raai waar elk van hierdie nodes in die geheue is. Ons het letterlik volg die spoor van broodkrummels of, meer spesifiek, pointers te kry van een node na 'n ander. 

Nou, laat ons probeer om 'n ander een. Anita, wil jy om terug te kom hier? Waarom ons nie voort te gaan en die toekenning van 'n ander persoon uit die gehoor? Malloc-wat is jou naam? >> Rebecca. Rebecca. Rebecca is malloced uit die gehoor, en sy is nou die stoor van die getal 55. En die doel by die hand is nou vir Anita te voeg Rebecca in die geskakelde lys hier in die toepaslike plek. Kom oor hier vir 'n oomblik. Ek gedoen het iets soos hierdie. Ek gedoen het node *. En wat is jou naam nou weer? Rebecca. >> Rebecca, okay. Rebecca kry malloc (sizeof (node)). Net soos ons in die verlede toegeken dinge soos studente en noem maar op, moet ons die grootte van die node, so nou is Rebekka wys op wat? Rebecca het twee velde binnekant van haar, waarvan een is 55. Kom ons doen wat, Rebecca-> = 55. Maar dan rebecca-> Volgende moet nou wees soos, haar hand is 'n soort van wie weet? Dit wys op 'n sekere vullis waarde, so hoekom doen jy nie vir 'n goeie maatreël ons ten minste doen dit sodat linkerhand is nou aan haar kant. Nou Anita, neem dit van hier af. Jy het Rebecca toegeken is. Gaan voort en vind waar ons moet sit Rebecca. Goed, baie goed. Goed, goed, en nou is ons het jou nodig om 'n bietjie van rigting te verskaf, sodat jy bereik het Ari. Sy linkerhand is, is van nul, maar Rebecca behoort duidelik aan die regterkant, so hoe het ons hierdie geskakelde lys te verander ten einde Rebecca in die toepaslike plek in te voeg? As jy kan letterlik mense se linkerhand beweeg om as dit nodig is, ons sal die probleem op daardie manier op te los. Goed, goed, en intussen, Rebecca se linkerhand is nou deur haar kant. 

Dit was te maklik. Kom ons probeer om die toekenning-we're byna gedoen het, 20. Okay, kom op. 20 toegeken is, so laat my gaan voort en sê weer hier ons het net gedoen node * saad. Ons het malloc (sizeof (node)). Ons doen dan presies dieselfde sintaks soos ons gedoen het voor vir 20, en ek sal langs = NULL doen, en nou is dit tot Anita jy in die geskakelde lys te voeg, as jy kan dat presies dieselfde rol speel. Uit te voer. Goed. Nou dink goed na voordat jy begin beweeg links hande om. Jy verreweg vandag het die mees ongemaklike rol. Wie se hand moet eerste verskuif? Okay, wag, ek 'n paar nee se ek hoor. As sommige mense sou beleefd om te help om 'n ongemaklike situasie op te los hier. Wie se linkerhand moet eers miskien bygewerk? Ja. [Studente] Saad. Okay, Saad, waarom, al is? [Onhoorbaar student reaksie] Goed so, want as ons beweeg-wat is jou naam? >> Marshall. Marshall, as ons beweeg sy hand af na nul, nou het ons letterlik wees gelaat is vier mense in hierdie lys want hy was die enigste ding wat wys op Ramon en almal aan die linkerkant, so afhangende van wat wyser was sleg. Kom ons maak ongedaan dat. Goed, en nou gaan voort en beweeg die toepaslike linkerhand wys op Ramon. Dit voel 'n bietjie oorbodig. Nou is daar twee mense wys op Ramon, maar dit is goed want nou hoe anders werk ons ​​die lys? Watter ander hand om te beweeg? Uitstekend, het ons nou 'n geheue verloor? Nee, so goed is, laat ons kyk of ons kan dit nie weer breek. 

Mallocing een laaste keer, nommer 5. Al die pad terug, op neer kom. Dit is baie opwindend. [Applous] Wat is jou naam? >> Ron. Ron, okay, jy malloced as nommer 5. Ons het net uitgevoer kode wat byna identies is aan hierdie met net 'n ander naam. Uitstekend. Nou, Anita, baie geluk invoeging nommer 5 in die lys nou. Goed is, en? Uitstekend, so dit is regtig die derde van drie in totaal gevalle. Ons moes eers iemand aan die einde, Rebecca. Ons het toe iemand in die middel. Nou het ons iemand aan die begin, en in hierdie voorbeeld, ons het nou om Lucas te werk vir die eerste keer want die eerste element in die lys het nou te wys op 'n nuwe node, wat op sy beurt, wys by node nommer 9. 

Dit was 'n uiters ongemaklike demonstrasie, ek is seker, so 'n groot applous vir hierdie ouens as jy kon. Mooi gedoen. Dis al. Jy behou jou stukkies papier as 'n bietjie geheue. Dit blyk dat om dit te doen in die kode is nie heeltemal so eenvoudig as net bewegende hande om en wys wysers op verskillende dinge. Maar besef dat wanneer dit tyd om iets soos te implementeer 'n geskakelde lys of 'n variant van dit as jy fokus op baie hierdie basiese beginsels, die byt-grootte probleme wat ek het om uit te vind, is dit hand of hierdie hand, besef dat wat andersins 'n redelik komplekse program kan, in werklikheid, verminder word tot redelik eenvoudige boustene soos hierdie. 

Kom ons neem dinge in 'n meer gesofistikeerde rigting. Ons het nou die idee van die geskakelde lys. Ons het ook te danke aan die voorstel daar agter 'n dubbel geskakelde lys, wat lyk amper dieselfde, maar nou moet ons twee wysers binnekant van die struct in plaas van een, en ons kan waarskynlik noem dié wenke vorige en die volgende of links of regs, maar ons doen, in werklikheid, moet twee van hulle. Die kode sal 'n bietjie meer betrokke. Anita sou gehad het om meer werk om hier te doen op die verhoog. Maar ons kan seker daardie soort struktuur te implementeer. In terme van die bestuur van tyd, al is, wat sou die loop van die tyd vir Anita van die vind van 'n aantal n in 'n geskakelde lys nou? Nog steeds groot O van n, so dit is nie beter as lineêre soek. Ons kan dit nie doen om die binêre soek, al is, weer. Hoekom is dit die geval? Jy kan nie rond spring. Selfs al het ons natuurlik al die mense op die verhoog sien, en Anita kon eyeballed dit en sê: "Hier is die middel van die lys," sy sou nie weet dat as sy was die program op die rekenaar omdat die enigste ding wat sy gehad het om te grendel op aan die begin van die scenario was Lucas, wat was die eerste wyser. Sy sou noodwendig die skakels te volg, tel haar totdat sy gevind dat ongeveer die middel, en selfs dan is sy nie van plan om te weet wanneer sy die middel bereik tensy sy gaan al die pad tot die einde toe om uit te vind hoeveel daar is, dan backtracks en ook dit sou moeilik wees, tensy jy gehad het 'n dubbel gekoppel lys van een of ander aard. 

Oplos van enkele probleme vandag, maar die bekendstelling van ander. Wat oor 'n ander datastruktuur altesaam? Dit is 'n foto van die bak in Mather House, en in hierdie geval het ons 'n datastruktuur ons soort het ook reeds praat. Ons het gepraat oor 'n stapel in die konteks van die geheue, en dit is doelbewus soort genoem omdat 'n stapel in die bepalings van die geheue is effektief 'n datastruktuur wat meer en meer dinge lae bo-op dit. Maar die interessante ding oor 'n stapel, soos die geval is in werklikheid, is dat dit 'n spesiale soort data struktuur. Dit is 'n datastruktuur waardeur die eerste element in is die laaste element. As jy die eerste skinkbord geplaas word op die stapel, jy gaan ongelukkig die laaste skinkbord geneem moet word van die stapel af, en dit is nie noodwendig 'n goeie ding nie. Omgekeerd, kan jy dink oor dit die ander manier om, die laaste is die eerste uit. 

Nou, 'n scenario na vore kom waar 'n stapel data struktuur waar jy daardie eiendom van die laaste in, eerste uit, is eintlik interessant? Is dit 'n goeie ding? Is dit 'n slegte ding? Dit is beslis 'n slegte ding is as die bak was nie almal identies en hulle was almal spesiale verskillende kleure of iets anders, en die kleur wat jy wil, is al die pad aan die onderkant. Van die kursus, kan jy nie kry wat sonder groot moeite. Jy het om te begin van die bo-en werk jou pad af. Net so, wat as jy een van hierdie fan seuns wat wag op die hele nag probeer om 'n iPhone en in lyn te kry op 'n plek soos hierdie? Sou dit nie lekker wees as die Apple Store was 'n stapel data struktuur? Yay? Nee? Dit is net goed vir die mense wat wys op die laaste minuut en dan die tou af geruk kry. En in die feit, die feit dat ek is so geneig om tou te sê is eintlik in ooreenstemming met wat ons sou noem hierdie soort data struktuur, een in werklikheid waar die einde maak nie saak, en jy wil die eerste een in die eerste een te wees uit indien slegs ter wille van die mens regverdigheid. Ons sal oor die algemeen noem dat 'n tou data struktuur. 

Dit blyk uit behalwe geskakelde lyste, kan ons begin deur gebruik te maak van hierdie basiese idees en begin met die skep van nuwe en verskillende tipes oplossings vir probleme. Byvoorbeeld, in die geval van 'n stapel, kan ons 'n stapel verteenwoordig met behulp van 'n data-struktuur soos hierdie, sou ek voorstel. In hierdie geval, het ek verklaar 'n struct, en ek het gesê binnekant van die struktuur is 'n skikking van getalle en dan 'n veranderlike genoem grootte, en ek gaan hierdie ding noem 'n stapel. Nou, waarom dit eintlik werk? In die geval van 'n stapel, kan ek dit effektief trek op die skerm as 'n skikking. Hier is my stapel. Dit is my nommers. En ons sal hulle trek soos hierdie, hierdie, hierdie, hierdie, hierdie. En dan het ek 'n paar ander data lid hier, wat genoem word grootte, so dit is grootte, en dit is getalle, en gesamentlik, die hele iPad hier een stapel struktuur. Nou, by verstek, grootte het vermoedelik het geïnisialiseer word na 0, en wat is binnekant van die skikking van getalle aanvanklik toe ek die eerste keer 'n skikking toeken? Gemors. Wie weet? En dit maak eintlik nie saak nie. Dit maak nie saak as dit is 1, 2, 3, 4, 5, heeltemal lukraak deur slegte geluk in my struktuur gestoor, want so lank as wat ek weet is dat die grootte van die stapel 0 is, dan weet ek programmaties, kyk nie by enige van die elemente in die skikking. Dit maak nie saak wat daar staan. Moenie kyk na hulle, as sou die implikasie van 'n grootte van 0. 

Maar dink nou ek gaan voort en voeg iets in die stapel. Ek wil hê dat die getal 5 in te voeg, so ek het nommer 5 hier, en dan wat sit ek hier neer? Nou wil ek eintlik sit 1 vir die grootte, en nou is die stapel van grootte 1. Wat gebeur as ek gaan voort en voeg die nommer, laat ons sê, 7 volgende? Dit is dan kry opgedateer 2, en dan sal ons doen 9, en dan is dit word opgedateer tot 3. Maar die interessante kenmerk van hierdie stapel is dat Ek veronderstel watter element te verwyder as ek wil pop iets af van die stapel, om so te praat? 9 sou die eerste ding om te gaan. Hoe moet die prentjie verander as ek wil 'n element van die stapel af te pop, graag 'n skinkbord in Mather? Ja >> [Studente] Set grootte 2. Presies, is al wat ek doen stel grootte 2, en wat moet ek doen met die skikking? Ek het nie iets te doen. Ek kon net anale te wees, sit daar 'n 0 of 'n -1 of iets om aan te dui dat dit nie 'n ligitieme waarde, maar dit maak nie saak nie, want Ek kan teken buite die skikking self hoe lank dit is sodat Ek weet net te kyk na die eerste twee elemente in die skikking. Nou, as ek gaan en voeg die getal 8 tot hierdie skikking, hoe verander die prentjie volgende? Dit word 8, en dit word 3. Ek sny 'n paar hoeke hier. Nou het ons 5, 7, 8, en ons is terug na 'n grootte van 3. Dit is redelik maklik om te implementeer, maar wanneer gaan ons hierdie ontwerp besluit om te betreur? Wanneer begin dinge doen baie, baie verkeerd om te gaan? Ja. [Onhoorbaar student reaksie] As jy wil om terug te gaan en kry die eerste element wat jy sit in 

Dit blyk uit hier, selfs al is 'n stapel is 'n verskeidenheid onder die kap, hierdie data strukture het ons begin praat oor die algemeen ook bekend as abstrakte data strukture waardeur hoe hulle geïmplementeer is heeltemal afgesien van die punt. 'N data struktuur soos 'n stapel veronderstel is om ondersteuning toe te voeg bedrywighede soos druk, wat stoot 'n skinkbord op die stapel, en pop, wat hef 'n element van die stapel, en dit is dit. As jy iemand anders se kode wat reeds geïmplementeer was om af te laai hierdie ding genaamd 'n stapel, sou daardie persoon geskryf het slegs twee funksies vir jou, stoot en pop, wie se enigste doel in die lewe sou wees om presies dit te doen. Jy of hom of haar wat daardie program geïmplementeer sou gewees het heeltemal die een om te besluit hoe om te implementeer die semantiek van die stoot en knal onder die kap of die funksionaliteit van stoot en knal. En ek het hier 'n bietjie kortsigtig besluit deur die implementering van van my stapel met hierdie eenvoudige data van die struktuur waarom? Wanneer gaan hierdie data struktuur breek? Op watter punt het ek 'n fout om terug te keer wanneer die gebruiker versoek druk, byvoorbeeld? [Studente] As daar geen meer ruimte. Presies, as daar is nie meer spasie, indien ek kapasiteit oorskry het, wat alle pette, want dit dui daarop dat dit 'n soort van globale konstante. Wel, dan is ek net gaan om te sê, "Jammer, ek kan nie 'n ander waarde stoot op die stapel, "graag in Mather. 

Op 'n sekere punt, gaan hulle die boonste deel van daardie klein kabinet te tref. Daar is geen meer ruimte of kapasiteit in die stapel, op watter punt is daar is 'n soort van fout. Hulle het die element om iewers anders te stel, die skinkbord iewers anders, of nêrens op alle. Nou, met 'n tou, kan ons dit implementeer 'n bietjie anders. 'N tou is 'n bietjie anders in dat onder die kap, dit geïmplementeer kan word as 'n skikking, maar waarom, in hierdie geval, ek stel ook 'n hoof element wat die hoof van die lys, die voorkant van die lys, die eerste persoon in die lyn by die Apple Store, benewens grootte? Hoekom het ek hier 'n bykomende stuk van die data? Dink terug aan watter nommers is as ek geteken het dit soos volg. Veronderstel dit is nou 'n tou in plaas van 'n stapel, die verskil wat net soos die Apple Store-queue is regverdig. Die eerste persoon in die lyn by die begin van die lys, nommer 5 in hierdie geval, hy of sy gaan word laat in die winkel eerste. Kom ons doen dit. Veronderstel dat dit die toestand van my tou op hierdie oomblik in die tyd, en nou die Apple Store oop en die eerste persoon, nommer 5, is in die winkel gelei. Hoe verander ek die prentjie nou dat ek de-queued is die eerste persoon aan die voorkant van die lyn? Wat is dit >> [Studente] Verander die tou. Verander die kop, so 5 verdwyn. In werklikheid, is dit asof die beste manier om dit te doen? In werklikheid, is dit asof hierdie man verdwyn. Wat sou nommer 7 in 'n werklike winkel? Hulle sou 'n groot stap vorentoe te neem. 

Maar wat kom ons om te waardeer wanneer dit kom by skikkings en beweeg dinge rondom? Dit is soort van 'n vermorsing van jou tyd, reg? Hoekom het jy so anale as die eerste persoon te hê aan die begin van die lyn by fisies die begin van die stuk van die geheue? Dit is heeltemal onnodig. Hoekom? Wat ek kan net onthou in plaas >> [onhoorbaar student reaksie]? Presies, ek kan net onthou met hierdie addisionele data lid kop wat nou die hoof van die lys is nie meer 0, wat dit was 'n oomblik gelede. Nou is dit eintlik die aantal 1. Op hierdie manier, ek kry 'n effense optimalisering. Net omdat ek de-queued is iemand uit lyn aan die begin van die lyn by die Apple Store beteken nie almal te skuif, wat onthou is 'n lineêre werking. Ek kan plaas konstante spandeer tyd net en dan bereik 'n baie vinniger reaksie. Maar die prys wat ek betaal is wat addisionele prestasie te verkry en nie met almal te skuif? Ja >> [onhoorbaar student antwoord]. Meer mense kan byvoeg, goed, dat die probleem is ortogonale aan die feit dat ons nie die verskuiwing van mense rondom. Dit is nog steeds 'n skikking, so of ons nie almal skuif of nie- O, ek sien wat jy bedoel, okay. Eintlik, ek stem saam met wat jy sê dat dit is amper asof ons nou nooit gaan die begin van hierdie skikking te gebruik nie want as ek verwyder 5, dan hef ek 7. Maar ek het net mense aan die regterkant. 

Dit voel asof ek mors ruimte, en uiteindelik my tou disintegreer in glad niks nie, sodat ons kan net mense wraparound, en ons kon dink regtig as 'n soort van omsendbrief struktuur van die skikking, maar ons gebruik wat operateur in C daardie soort van wraparound te doen? [Onhoorbaar student reaksie] >> Die modulo-operateur. Dit sou 'n bietjie lastig deur te dink hoe doen jy die wraparound, maar ons kan dit doen, en ons kon begin om mense wat gebruik word om die voorkant van die lyn, maar ons het net met die hoof veranderlike wat die werklike hoof van die lyn is eintlik onthou. Wat as, in plaas daarvan, ons doel uiteindelik, al is, was om te kyk getalle, soos ons hier het op die verhoog met Anita, maar ons wil regtig die beste van al hierdie wêrelde? Ons wil meer gesofistikeerd as skikking kan , want ons wil die vermoë om dinamiese groei van die data struktuur. Maar ons wil nie 'n beroep op iets wat ons daarop gewys in die eerste lesing was nie 'n optimale algoritme, wat van lineêre soek. Dit blyk dat jy kan bereik, in werklikheid, of ten minste naby aan konstante tyd, waardeur iemand soos Anita, as sy haar datastruktuur instel nie te wees 'n geskakelde lys, nie 'n stapel te wees, nie om 'n tou te word, kan, in werklikheid, kom met 'n datastruktuur wat dit moontlik maak om haar te kyk op dinge, selfs woorde, nie net getalle, in wat ons noem konstante. 

En in die feit, vooruit kyk, een van die psets in hierdie klas is byna altyd 'n implementering van 'n speltoetser, waardeur gee ons jou weer n paar 150,000 Engelse woorde en die doel is om laai wat in die geheue en vinnig in staat wees om vrae van die vorm te beantwoord is hierdie woord korrek gespel? En dit sou regtig suig as jy het om te itereer deur die hele 150.000 woorde om dit te beantwoord. Maar, in werklikheid, sal ons sien dat ons dit kan doen in 'n baie, baie vinnig tyd. En dit gaan die uitvoering van iets genoem 'n hash tafel te betrek, en selfs al met die eerste oogopslag hierdie ding genoem 'n hash tafel gaan Laat ons bereik hierdie super vinnige reaksie tye, dit blyk dat daar in werklikheid 'n probleem. Wanneer dit tyd is hierdie ding genaamd-weer te implementeer, ek doen dit weer. Ek is die enigste een hier. Wanneer dit tyd is om die implementering van hierdie ding genoem 'n hash tafel, ons gaan te hê om 'n besluit te maak. Hoe groot moet eintlik hierdie ding? En wanneer ons begin die invoeging van getalle in hierdie hash tafel, hoe gaan ons hulle in so 'n manier te stoor wat ons kan kry hulle terug so gou as ons het hulle in? Maar ons sal sien voor lank dat hierdie vraag van wanneer almal se verjaarsdag is in die klas sal wees redelik related. Dit blyk dat in hierdie kamer, het ons 'n paar honderd mense het, sodat die kans dat twee van ons het dieselfde verjaarsdag waarskynlik is redelik hoog is. Wat as daar net 40 van ons in hierdie kamer? Wat is die kans van twee mense wat dieselfde verjaarsdag? [Studente] Meer as 50%. Ja, meer as 50%. Trouens, ek het selfs 'n grafiek. Dit blyk uit-en dit is regtig net 'n sneak preview- indien daar is net 58 van ons in hierdie kamer, die waarskynlikheid van 2 van ons wat dieselfde verjaarsdag is uiters hoog, byna 100%, en dit gaan 'n hele klomp van die seer vir ons te laat op Woensdag. 

Met wat gesê het, laat ons hier verdaag. Ons sal sien dat jy op Woensdag. [Applous] [CS50.TV]