[Musik spiller] 

[VIDEO PLAYBACK] 

-Han Lyver. 

-Om hvad? 

-Jeg ved ikke. 

-Så Hvad ved vi? 

-at På 09:15, Ray Santoya var på ATM. -Ja. Så spørgsmålet er, hvad lavede han ved 9:16? 

-Shooting 9 millimeter på noget. Måske så han snigskytte. 

-Eller Arbejdede med ham. 

-Wait. Gå tilbage en. 

-Hvad ser du? 

-Bringe Hans ansigt op fuld skærm. 

-His Briller. 

-Der Er en refleksion. 

-Det Er den Nuevitas baseball hold. Det er deres logo. 

-Og Han taler til hvem iført denne jakke. 

[END AFSPIL] 

DAVID MALAN: Okay. Dette er CS50 og dette er en smule mere af [uhørligt], som du er dypning med problemet sæt fire. I dag begynder vi at se lidt mere dybt på disse ting kaldet pointere, som selv om det er en temmelig mystisk emne, det viser sig, at det vil at være det middel, hvorved vi kan begynde at bygge og samle meget mere sofistikerede programmer. Men vi gjorde det på sidste onsdag ved hjælp af nogle claymation først. Så dette, tilbagekaldelse, er Binky og vi brugte ham at tage et kig på et program, ikke rigtig gøre noget interessant, men det gjorde afslører et par problemer. Så at begynde i dag, hvorfor vi ikke gå hurtigt gennem et par af disse trin, forsøge at destillere i humane vilkår præcis, hvad der foregår her og hvorfor det er dårligt, og derefter gå videre og faktisk begynde at bygge noget med denne teknik? Så disse var de første to linjer i dette program og i lægmandssprog, hvad er disse to linjer gør? Nogen, der er nogenlunde komfortabel med, hvad der er angivet på skærmen? Hvad er disse to linjer gør? Det er ikke alt, forskellig fra uge en, men der er nogle nye særlige symbol. Ja? Tilbage dertil. 

PUBLIKUM: Erklæring af pointers? DAVID MALAN: Sig igen? PUBLIKUM: Erklæring af pointers? DAVID MALAN: Erklæring af pointere og lad os forfine det en lille smule mere. PUBLIKUM: [uhørligt] adresse x- og y derefter. DAVID MALAN: Og så tage fat. Så specifikt, hvad vi laver er vi erklærer to variabler. Disse variabler, selv om, vil at være af typen int stjerne, som mere specifikt betyder de kommer til at gemme adressen på en int, henholdsvis x og y. Nu er der nogen værdier? Er der nogen konkrete adresser i disse to variabler på dette tidspunkt? Nej. Det er bare såkaldt skrald værdier. Hvis du faktisk ikke tildele en variabel, hvad der var i RAM tidligere kommer til at fylde med nuller og dem begge af disse variabler. Men vi ved endnu ikke, hvad de er, og det er vil være nøglen til, hvorfor Binky tabte hovedet i sidste uge. 

Så dette var claymation inkarnation af denne hvorved du har kun to variabler, små cirkulære stykker af ler, der kan lagre variabler, men som de pakket ind pile antyder, de er faktisk ikke peger til alle steder kendt. Så vi havde derefter denne linje, og det var nyt i sidste uge, malloc til hukommelse fordeling, som er blot en fancy måde at fortælle operativsystemet, Linux eller Mac OS eller Windows, hey, giv mig noget hukommelse, og alt hvad du nødt til at fortælle operativsystemet er hvad når beder det for hukommelsen. Det kommer ikke til at pleje hvad du kommer til at gøre med det, men du behøver at fortælle operativsystemet Systemet hvad ved hjælp af malloc. Ja? 

PUBLIKUM: Hvor meget? DAVID MALAN: Hvor meget? Hvor meget i bytes, og så det igen, en konstrueret eksempel er bare at sige, give mig størrelsen på en int. Nu, størrelsen af ​​en int er fire byte eller 32 bit. Så dette er bare en måde at sige, hey, operativsystem, give mig fire bytes hukommelse at jeg kan bruge til min rådighed, og specifikt, hvad betyder malloc vende tilbage med respekt denne bid af fire bytes? PUBLIKUM: Adresse? DAVID MALAN: Adressen. Adressen på den luns af fire bytes. Præcis. Og så det er, hvad der er gemt i sidste ende i x- og det er derfor vi ikke rigtig pleje hvad antallet af denne adresse er, uanset om det er OX1 eller OX2 eller nogle kryptiske hexadecimal adresse. Vi har lige pleje billedligt at denne variabel X er nu peger på, at bid af hukommelse. Så pilen repræsenterer en pegepind eller mere specifikt en hukommelsesadresse. Men igen, vi typisk ikke ligeglad hvad disse faktiske adresser er. Nu denne linje siger hvad i lægmandssprog? Stjerne x får 42 semikolon. Hvad betyder det? Du wanna go? Undgå at ridse din hals. 

PUBLIKUM: Adressen på x er på 42. 

DAVID MALAN: Adressen på x er på 42. Ikke helt. Så tæt, men ikke helt, fordi der er stjernen, der er forudfastsætte denne x. Så vi er nødt til at nappe en lille smule. Ja? 

PUBLIKUM: Den værdi, som pointer x peger på, er 42. DAVID MALAN: OK. Den værdi, markøren x er peger på, lad os sige, er 42, eller sagt på en anden måde, stjernen x siger, gå til uanset adresse er i x, uanset om det er en Oxford Street eller 33 Oxford Street eller OX1 eller OX33, uanset at numerisk adresse er, stjerne x er dereferere af x. Så gå til denne adresse og derefter sætte nummer 42 der. Så det ville være et tilsvarende måde at sige det. Så det er alt fint og derefter Vi ville repræsentere billedet som følger, hvor vi har tilføjet 42 til denne bid af fire bytes i højre side, men denne linje var, hvor tingene gik galt og Binky hoved dukkede ud på dette tidspunkt, fordi dårlige ting ske, når du dereference skrald værdier eller du dereference ugyldig pointere, og jeg siger ugyldig fordi der på dette tidspunkt i historie, hvad der er inde for y? Hvad er værdien af ​​y baseret på de sidste par skridt? Ja? Hvad er det? 

PUBLIKUM: En adresse. DAVID MALAN: En adresse. Det bør være en adresse men jeg har initialiseret det? Så jeg har ikke endnu. Så hvad der er kendt for at være derinde? Det er blot nogle skrald værdi. Det kunne være en hvilken som helst adresse fra nul til 2 milliarder, hvis du har to gigs RAM, eller nul til 4 milliarder, hvis du har fik fire gigabyte RAM. Det er nogle skrald værdi, men problemet er at operativsystemet, hvis det ikke har givet dig at chunk hukommelse specifikt at du forsøger at gå til, Det er generelt kommer til at forårsage, hvad vi har set som en segmentering fejl. Så i virkeligheden, nogen af ​​jer, der har kæmpede på problemer på kontortid eller problemer, der er mere generelt med at forsøge at finde ud af en segmentering fejl, der generelt betyder du rører et segment af hukommelse, som du ikke skal være. Du rører hukommelse, operativsystemet har ikke tillod dig at røre ved, om det er ved at gå for vidt i dit array eller starte nu, uanset om det er fordi du rører hukommelse, der bare er en vis skrald værdi. 

Så laver stjerne x her er slags udefineret adfærd. Du bør aldrig gøre det, fordi odds er, er programmet bare at gå ned, fordi du siger, gå til denne adresse og du har ingen idé om, hvor at adressen rent faktisk er. Så styresystemet sandsynligvis kommer til at gå ned dit program som et resultat, og ja, det er hvad skete der for at Binky. Så i sidste ende, Binky fast dette problem med dette. Så selve programmet var behæftet med fejl. Men hvis du slags gå videre og udføre denne linje i stedet, y er lig med x betyder blot, hvad adresse er en x, også sætte det i y. 

Og så billedligt, vi har repræsenterede dette med to pile fra x og y fra peger til det samme sted. Så semantisk, x er lig til y fordi i begge disse gemmer den samme adresse, ergo peger på 42, og nu, når du siger stjerne y, gå til adressen i y, dette har en interessant bivirkning. Så adressen i y er samme som adressen i x. Så hvis du siger gå til adressen i y og ændre værdien til 13, hvem der ellers er påvirket? X er, punkt D, så at sige, bør blive påvirket så godt. 

Og ja, hvordan Nick tegnede dette billede i claymation var præcis det. Selvom vi følger markøren y, endte vi på samme sted, og så hvis vi var til at udskrive ud x eller y s pointee, så ville vi se værdien af ​​13. Nu siger jeg pointee at være overensstemmelse med videoen. Programmører, til min viden, faktisk aldrig sige ordet pointee, det, der er tilspidset på, men for konsekvens med videoen, indser det er alt, der var betød i denne situation. Så spørgsmål om claymation eller henvisninger eller malloc bare endnu? Nej? Okay. 

Så uden yderligere ståhej, lad os tage et kig på, hvor det har faktisk været brugt i nogen tid. Så vi har haft denne CS50 bibliotek der har fået alle disse funktioner. Vi har brugt GetInt en masse, getString, sandsynligvis GetLongLong tidligere i min pset én eller deromkring, men hvad der rent faktisk er foregået? Nå, lad os tage et hurtigt kig under emhætten på et program, der inspirerer hvorfor vi give dig den CS50 bibliotek, og faktisk fra sidste uge, Vi begyndte at tage dem uddannelse hjul off. Så dette er nu sorteres en postmortem af, hvad har stået på inde i CS50 bibliotek, selv om vi nu vil begynde at bevæge væk fra det for de fleste programmer. 

Så dette er et program kaldet scanf 0. Det er super kort. Det bare har disse linjer, men det introducerer en funktion kaldet scanf at vi faktisk kommer til at se i et øjeblik inde i CS50 bibliotek, omend i en lidt anderledes form. Så dette program på linje 16 er at erklære en variabel x. Så giv mig fire byte for en int. Det er blevet fortalt bruger, nummer bedes, og derefter Dette er en interessant linje, faktisk binder sidste uge og dette. Scanf, og derefter mærke til det tager en string-format, ligesom printf, % Jeg betyder en int, og så det tager en andet argument, der ser lidt funky. Det er tegnet x, og til at huske, vi så kun denne ene gang i sidste uge. Hvad betyder tegnet x repræsenterer? Hvad betyder tegnet gøre i C? Ja? 

PUBLIKUM: Adressen på. DAVID MALAN: Adressen på. Så det er det modsatte af stjernen operatøren, mens stjernen operatøren siger, gå til denne adresse, den tegnet operatør siger, finde ud af adresse på denne variabel, og så dette er nøglen, fordi scanf formål i livet er at scanne brugerens input fra tastaturet, afhængig af hvad han eller hun typer, og derefter læse, at brugerens input i en variabel, men vi så i de seneste to uger at denne swap funktionen vi forsøgt ubesværet at gennemføre var blot brudt. Husk på, at med swap-funktion, hvis vi bare erklærede A og B som ints, vi med held skifte to variable inde i swap ligesom med mælken og EFT, men så snart swap vendte tilbage, hvad var resultatet med hensyn til x og y, de oprindelige værdier? Ingenting. Ja. Intet skete dengang, fordi swaps ændrer kun dens lokale kopier, hvilket vil sige, alle denne gang, når vi har blevet passerer argumenter til funktioner, vi er blot passerer kopier af disse argumenter. Du kan gøre med det hvad du vil med dem, men de kommer til at have nogen effekt på de oprindelige værdier. Så dette er problematisk, hvis du ønsker at have en funktion som scanf i livet, er hvis formål til at scanne brugerens input fra tastaturet og derefter udfylde de tomme felter, så at tale, dvs. give en variabel som x en værdi, fordi hvis jeg var til bare passere x for at scanf, hvis du overveje logikken i sidste uge, kan scanf gøre, hvad det vil med en kopi af x, men det ikke kunne permanent ændre x medmindre vi giver scanf et skattekort, så at sige, hvor x markerer stedet, hvor vi passerer i adressen for x, så scanf kan gå der og faktisk forandring værdien af ​​x. Og så ja, alt at dette program gør hvis jeg laver scanf 0, i min kilde 5m bibliotek, gør scanf 0, dot skråstreg scanf, nummer venligst 50, tak for 50. 

Så det er ikke alt, interessant, men hvad der faktisk sker er, at så snart jeg kalder scanf her, værdien af ​​x bliver permanent ændret. Nu, dette synes nice og godt, og i virkeligheden er det ser ud som vi ikke virkelig har brug for det CS50 biblioteket på alle længere. For eksempel, lad os køre dette endnu en gang her. Lad mig genåbne det for en anden. Lad os prøve en række venligst og stedet for at sige 50 som før, lad os bare sige nej. OK, det er lidt underligt. OK. Og blot nogle vrøvl her. Så det synes ikke at håndtere fejlagtige situationer. Så vi er nødt til minimalt starten tilføje nogle fejl-kontrol for at sikre, at brugeren har skrevet i en faktiske tal som 50, fordi tilsyneladende skrive ord genkendes ikke som problematisk, men det burde nok være. 

Lad os se på denne version nu, er mit forsøg på at reimplement getString. Hvis scanf har alt dette funktionalitet indbygget, hvorfor har vi været dypning med disse uddannelse hjul som getString? Nå, her er måske min egen simpel version af getString hvorved en uge siden, kunne jeg have sagt, give mig en snor og kalder det buffer. I dag vil jeg begynde bare siger char stjerne, som, tilbagekaldelse, det er bare synonym. Det ser mere skræmmende, men det er præcis de samme ting. Så giv mig en variabel kaldet buffer der kommer til at gemme en streng, fortælle brugeren strengen venligst, og derefter, ligesom før, lad os prøve at låne denne lektion scanf % s denne gang, og derefter sende i buffer. Nu en hurtig sanity check. Hvorfor bliver jeg siger ikke tegnet buffer denne gang? Udlede det foregående eksempel. PUBLIKUM: Char stjerne er en pointer. DAVID MALAN: Præcis, fordi denne gang, char stjerne er allerede en pegepind, en adresse, definition af denne stjerne at være der. Og hvis scanf forventer en adresse, er det tilstrækkeligt blot at passere i buffer. Jeg behøver ikke at sige tegnet buffer. For den nysgerrige, kunne du gøre noget som dette. Det ville have forskellig betydning. Dette vil give dig en pegepind til en pegepind, som faktisk er en gyldig ting i C, men for nu, lad os holde det simpelt og holde historien konsekvent. Jeg er bare kommer til at passere i buffer og det er korrekt. Problemet er dog dette. Lad mig gå videre og køre dette program efter kompilere den. Gøre scanf 1. Damn det, min compiler s fange min fejl. Giv mig et sekund. Klang. Lad os sige scanf-1.c. OK. Der vi går. Jeg har brug for det. CS50-ID har forskellige konfigurationsindstillinger at beskytte dig mod dig selv. Jeg havde brug for at deaktivere dem ved kører klang manuelt denne gang. Så snor venligst. Jeg har tænkt mig at gå videre og skrive i min favorit hej verden. OK, null. Det er ikke, hvad jeg har skrevet. Så det er betegnende for noget at være forkert. Lad mig gå videre og skrive i en virkelig lang snor. Tak for ugyldig og jeg ved ikke, hvis jeg har tænkt mig at være i stand til at gå ned den. Lad os prøve lidt kopi indsætte og se om det hjælper. Bare indsæt en masse af dette. Det er helt sikkert en større snor end normalt. Lad os bare virkelig skrive det. Nej. For pokker. Kommando ikke fundet. Så det er uafhængige. Det er fordi jeg klistret nogle dårlige karakterer, men dette viser sig ikke at gå på arbejde. 

Lad os prøve denne gang mere, fordi det er sjovere, hvis vi rent faktisk går ned det. Lad os skrive dette, og nu er jeg kommer til at kopiere en virkelig lang snor og lad os nu se, om vi kan gå ned denne ting. Bemærk, jeg udeladt rum og nye linjer og semikoloner og alle funky tegn. Enter. Og nu netværkets bare at være langsom. Jeg holdt nede Command-V for længe, ​​tydeligt. For pokker! Kommando ikke fundet. 

OK. Nå, pointen er alligevel følgende. Så hvad der rent faktisk sker på denne erklæring char stjerne buffer på linie 16? Så hvad får jeg når jeg erklærer en pointer? Alt Jeg får er en fire byte værdi kaldet buffer, men hvad der er inde i det i øjeblikket? Det er blot nogle skrald værdi. Fordi hver gang du erklære en variabel i C, det er bare nogle skrald værdi, og vi er begyndt at tur over denne virkelighed. Nu, når jeg fortæller scanf, gå til denne adresse og sætte hvad brugeren typer i. Hvis brugeren skriver i hej verden, ja, hvor skal jeg sætte det? Buffer er en skraldespand værdi. 

Så det er lidt ligesom en pil der er peger hvem ved hvor. Måske er det at pege lige her i min hukommelse. Og så når brugeren typer i hello verden, programmet forsøger at sætte snor hej verden omvendt skråstreg 0 i denne chunk hukommelse. Men med stor sandsynlighed, men tydeligvis ikke 100% sandsynlighed, computeren vil derefter ned programmet, fordi det ikke er hukommelse, jeg skal have lov til at røre ved. Så kort sagt, dette program er fejlbehæftet for netop den grund. Jeg fundamentalt ikke gør hvad? Hvilke skridt har jeg udeladt, ligesom vi udeladt med Binky første eksempel? Ja? 

PUBLIKUM: tildeling Memory? 

DAVID MALAN: tildeling Hukommelse. Jeg har faktisk ikke allokeret enhver hukommelse til denne streng. Så vi kan løse dette på et par måder. En, kan vi holde det simpelt og i virkeligheden, nu er du vil begynde at se en sløring af linjerne mellem, hvad et array er, hvad en streng er, hvad en char stjerne er, hvad en række tegn er. Her er et andet eksempel involverer strygere og varsel alt jeg har gjort på nettet 16 er, i stedet for at sige at bufferen bliver en char stjerne, en pointer til en klump hukommelse, Jeg har tænkt mig at meget proaktivt at give mig selv en buffer til 16 tegn, og i virkeligheden, hvis du er fortrolig med udtrykket buffering, sandsynligvis fra en verden af ​​videoer, hvor en video er buffering, buffering, buffering. Nå, hvad er forbindelsen her? Nå, Inde i YouTube og inde i videoafspillere generelt er en matrix der er større end 16. Det kan være en bred vifte af størrelse én megabyte, måske 10 megabyte, og ind i den matrix gør din browser downloade en hel masse bytes, en hel masse megabyte video, og video-afspiller, YouTubes eller hvem er, starter at læse bytes fra den opstilling, og hver gang du ser Ordet buffering, buffering, det betyder at spilleren har fået til slutningen af ​​denne array. Netværket er så langsom, at den ikke har genopfyldt array med flere byte og så er du ude af bits der skal vises til brugeren. 

Så buffer er en apt sigt her i, at det er bare et array, en luns af hukommelse. Og det vil ordne det fordi det viser sig at du kan behandle arrays, som om de er adresser, selvom puffer er blot et symbol, er det en sekvens af tegn, buffer, det er nyttigt for mig, programmøren, du kan videregive sit navn omkring som om det var en pointer, som om det var adressen på et stykke hukommelse til 16 tegn. Så det er at sige, kan jeg videregive den scanf præcis det ord og så nu, hvis jeg gør dette program, gøre scanf 2, dot skråstreg scanf 2, og skriv hej verden, Indtast, at time-- 

Hmm, hvad skete der? String venligst. Hvad har jeg gjort forkert? Hello world, buffer. Hej Verden. Ah, jeg ved, hvad det gør. OK. Så det er at læse op indtil den første plads. Så lad os snyde for et øjeblik og siger jeg ville bare skrive noget virkelig lang som dette er en lang sætning det er en, to, tre, fire, fem, seks, syv, otte, ni, 10, 11, 12, 13, 14, 15, 16. OK. Det er faktisk en lang sætning. Så denne sætning er længere end 16 tegn og så når jeg ramte Enter, hvad der kommer til at ske? Nå, i dette tilfælde af historie, jeg havde erklæret buffer til faktisk at være et array med 16 tegn klar til at gå. Så en, to, tre, fire, fem, seks, syv, otte, ni, 10, 11, 12, 13, 14, 15, 16. Så 16 tegn, og nu, hvor jeg læst i noget som dette er en lang sætning, hvad der kommer til at ske er at jeg har tænkt mig at læse i dette er en lang S-E-N-t-E-N-C-E, punktum. 

Så det er bevidst en dårlig ting, som jeg holde skrive over det grænserne for min array, ud over grænserne for min buffer. Jeg kunne få heldige og programmet vil holde på kører og er ligeglad, men generelt er dette vil faktisk gå ned mit program, og det er en fejl i min kode det øjeblik jeg træder ud over grænserne af denne array, fordi jeg ved ikke, om det er nødvendigvis kommer til at gå ned eller hvis jeg bare kommer til at få heldige. Så dette er problematisk, fordi i dette tilfælde betyder det ud til at virke og lad os friste skæbnen her, selvom IDE synes at tolerere en hel of-- 

Der vi går. Endelig. Så jeg er den eneste, der kan se dette. Så jeg har lige haft en masse sjov at skrive ud af en virkelig lang egentlige sætning at det helt sikkert overskredet 16 bytes, fordi jeg skrevet i denne vanvittige lang multi-line sætning, og så lægge mærke til, hvad der skete. Programmet forsøgte at udskrive det og fik derefter en segmentering fejl og segmentering fejl er, når noget som dette sker og operativsystemet siger nej, kan ikke røre, at hukommelsen. Vi kommer til at dræbe programmet helt. 

Så det synes problematisk. Jeg har forbedret programmet, hvorved i det mindste have en del af hukommelsen, men dette synes at begrænse funktionen getString til at få strenge af nogle endelig længde 16. Så hvis du ønsker at støtte længere sætninger end 16 tegn, hvad laver du? Nå, kan du øge størrelsen af ​​denne buffer til 32 eller synes slags kort. Hvorfor gør vi ikke bare gøre det 1.000 men skubbe tilbage. Hvad er svaret intuitivt for bare undgå dette problem ved at gøre min puffer større, ligesom 1.000 chars? Ved at implementere getString denne måde. Hvad er godt eller dårligt her? Ja? PUBLIKUM: Hvis du binde op en masse af plads og du ikke bruger det, så kan du ikke omfordele rummet. DAVID MALAN: Absolut. Det er spild så vidt som hvis du ikke gør faktisk har brug 900 af disse bytes og alligevel du beder om 1.000 i alt alligevel, du bare forbruge mere hukommelse på brugerens computer, end du har brug for, og efter alle, nogle af du allerede har stødt i livet, når du er kører masser af programmer og de spiser op masser af hukommelse, dette kan faktisk påvirke ydeevnen og brugerens oplevelse på computeren. Så det er sådan en doven løsning, sikker, og omvendt, det er ikke kun spild, hvilket problem stadig, selv om jeg gør min buffer 1.000? Ja? 

PUBLIKUM: Strengen er længde 1.001. DAVID MALAN: Præcis. Hvis din streng er længde 1.001, du har nøjagtig samme problem, og ved mit argument, ville jeg bare derefter gøre det 2000 men du ikke kender i forhånd, hvor stort det skal være, og dog, jeg behøver at kompilere mit program før udlejning folk bruger og downloade det. Så det er præcis den slags ting at CS50 biblioteket forsøger at hjælpe os med, og vi vil kun blik på nogle af de underliggende implementering her, men det er CS50 dot C. Denne er den fil, der har været på CS50 IDE alle disse uger, som du har brugt. Det er på forhånd kompileret og du har brugt det automatisk i kraft af at have dash L CS50 flag med klang, men hvis jeg rulle ned gennem alle disse funktioner, her er getString, og bare for at give dig en forsmag på, hvad der foregår, lad os tage et hurtigt kig på den relative kompleksitet. Det er ikke en super lang funktion, men det gjorde vi ikke nødt til at tænke alt hårdt om hvordan man kan gå om at få strenge. 

Så her er min buffer og jeg tilsyneladende initialisere den til null. Dette er naturligvis, er samme som char stjerne, men jeg besluttede i gennemførelse af CS50 biblioteket at hvis vi kommer til at være helt dynamisk, Jeg ved ikke, på forhånd, hvor stor en string brugere vil ønsker at få. Så jeg har tænkt mig at starte med blot en tom streng og jeg har tænkt mig at opbygge så meget hukommelse som jeg har brug for at passe til brugeren strengen og hvis jeg ikke har nok, jeg har tænkt mig at spørge Operativsystemet for mere hukommelse. Jeg har tænkt mig at flytte deres snor i en større del af hukommelsen og jeg har tænkt mig at frigive eller befri utilstrækkeligt stor luns af hukommelse og vi bare at gøre dette iterativt. 

Så et hurtigt blik, her er bare en variabel som jeg har tænkt mig at holde styr af kapaciteten af ​​min buffer. Hvor mange bytes kan jeg passe? Her er en variabel n med som jeg har tænkt mig at holde styr på, hvor mange bytes er faktisk i bufferen eller at brugeren har indtastet. Hvis du ikke har set det før, du kan angive, at en variabel som en int er usigneret, der som navnet antyder, betyder, at det er ikke-negativ, og hvorfor ville Jeg nogensinde ønsker at genere angivelse at en int er ikke bare en int, men det er en usigneret int? Det er en ikke-negativ int. Hvad betyder [uhørligt] betyde? 

PUBLIKUM: Det beskriver et beløb hukommelse, der kan være [uhørligt]. 

DAVID MALAN: Ja. Så hvis jeg siger usigneret, det er faktisk hvilket giver dig en smule ekstra hukommelse og det synes slags fjollet, men hvis du have en smule ekstra hukommelse, som betyder, at du har dobbelt så mange værdier, du kan repræsentere, fordi det kan være et 0 eller et 1. Så som standard, kan en int være nogenlunde negativ 2 mia hele vejen op til positiv 2 mia. De er store intervaller, men det er stadig slags spild hvis du kun bekymrer sig om størrelser, som netop intuitivt bør være ikke-negative eller positiv eller 0, ja så, hvorfor er du spilder 2 milliarder mulige værdier for negative tal hvis du aldrig kommer til at bruge dem? Så ved at sige usigneret, nu er min int kan være mellem 0 og ca. 4 mia. 

Så her er bare en int C grunde Vi vil ikke komme ind lige nu, som hvorfor det er en int i stedet af en char, men her er kernen i, hvad der foregår på, og nogle af jer bruger måske, for eksempel den fgetc funktion selv i pset fire eller senere, vil vi se det igen i problemer sæt fem, fgetc er rart, fordi som navnet slags, foreslår slags arcanely, Det er en funktion, som får en karakter og så, hvad er fundamentalt forskellige om, hvad vi laver i getString er vi ikke bruger scanf på samme måde. Vi er bare snigende langs trin-for-trin i hvad brugeren har indtastet, fordi vi kan altid afsætte en char, og så kan vi altid sikkert se på en char ad gangen, og magien begynder at ske her. Jeg har tænkt mig at rulle ned til midten af ​​denne funktion lige kort for at indføre denne funktion. Meget gerne der er en malloc-funktion, der er en realloc funktion, hvor realloc lader dig omfordele en luns af hukommelse og gøre det større eller mindre. Så lang historie kort og med en bølge af min hånd for i dag, vide, at hvad getString gør, er det er slags af magisk vokser eller krympning bufferen, når brugeren typer i hans eller hendes snor. 

Så hvis brugeren skriver en kort snor, denne kode kun allokerer nok hukommelse til at passe strengen. Hvis brugeren holder skrive som jeg gjorde det igen og igen og igen, ja, hvis buffer er oprindeligt dette store og programmet indser, at vent et øjeblik, jeg er ude af rummet, det kommer til at fordoble størrelsen af ​​bufferen og derefter dobbelt størrelse af bufferen og den kode, der gør en fordobling, hvis vi ser på det her, det er bare denne smarte one-liner. Du har måske ikke har set denne syntaks før, men hvis du siger stjerne lig, dette er det samme som siger kapacitet gange 2. Så det blot holder fordobling Den pufferens og derefter fortæller realloc at give selv så meget mere hukommelse. 

Nu, som en sidebemærkning, der er andre funktioner i her at vi ikke vil se i detaljer andet end at vise i GetInt, vi bruger getString i GetInt. Vi kontrollere, at det ikke er null, hvilket, tilbagekaldelse, er særlig værdi, betyder noget gik galt. Vi er ude af hukommelsen. Bedre kontrollere for det. Og vi vender tilbage en sentinel værdi. Men jeg vil udskyde til bemærkningerne om, hvorfor og så bruger vi denne fætter til scanf kaldte sscanf og det viser sig at sscanf, eller snor scanf, kan du tage et kig på den linje, brugeren har indtastet, og lad dig analysere det væsentlige, og hvad jeg er gør her, er jeg fortæller sscanf, analysere hvad brugeren har skrevet i, og sørg% i, Der er et helt tal i det, og vi vil ikke komme ind i dag præcis, hvorfor der er også en% c her, men i en nøddeskal tillader os at opdage, hvis brugeren har indtastet i noget fup efter nummeret. Så grunden til, at GetInt og getString fortælle dig at prøve igen, prøve igen, prøve igen er på grund af alle at kode, vi har skrevet, Det er lidt at se på brugerens input i at sikre det er helt numerisk eller det er en faktiske flydende pointværdi eller lignende, afhængigt af hvilken værdi fungere, du bruger. 

Puha. OK. Det var en mundfuld men pointen her er at årsagen til at vi havde disse uddannelse hjul på er på grund på det laveste niveau, Der er bare så mange ting, kan gå galt, at vi ønskede til forebyggende håndtere disse ting i hvert fald i tidligste uger af klassen, men nu med pset fire og pset fem og ud over vil du se at det er mere til dig, men også du er bedre i stand til løse den slags problemer dig selv. Eventuelle spørgsmål om getString eller GetInt? Ja? 

PUBLIKUM: Hvorfor ville du fordoble Den pufferens snarere end blot at øge det ved det nøjagtige beløb? 

DAVID MALAN: Godt spørgsmål. Hvorfor skulle vi fordoble kapaciteten af bufferen i modsætning til bare at øge den af nogle konstant værdi? Det var et design beslutning. Vi har lige besluttet, at fordi det har tendens til at være lidt dyrt tidsmæssigt til at spørge operativsystemet for hukommelse, vi ikke gjorde ønsker at ende med at få ind en situation til store strygere at vi bad OS igen og igen og igen og igen i hurtigt efter hinanden til hukommelsen. Så vi netop besluttet, noget vilkårligt men vi håber rimelighed, at du ved, hvad, lad os forsøge at komme foran os selv og bare holde fordoble det, så vi minimere mængden af ​​gange vi er nødt til at ringe til malloc eller realloc, men en samlet dom ringe i fravær af vide hvad brugerne måske ønsker at skrive i. Begge måder kan være diskutabel. Formentlig godt. 

Så lad os tage et kig på et par andre bivirkninger af hukommelse, ting, der kan gå galt og værktøjer, som du kan bruge til at fange den slags fejltagelser. Det viser sig, alle jer, selvom check50 har ikke fortalt dig så meget, har skrevet buggy -kode siden uge en, selv om alle check50 test er gik, og selv hvis du og din TF er super overbevist om, at din kode fungerer efter hensigten. Din kode er blevet buggy eller fejlbehæftet i, at alle jer, i at bruge CS50 bibliotek, er blevet utæt hukommelse. Du er blevet anmodet operativsystem til hukommelse i de fleste programmer du har skrevet, men du har faktisk aldrig givet det tilbage. Du har kaldt getString og GetInt og GetFloat, men med getString, du har aldrig kaldt unGetString eller Give String Tilbage eller lignende, men vi har set at getString gør allokere hukommelse i form af malloc eller dette funktion realloc, som er lige meget ens i ånden, og alligevel har vi været beder operativsystemet for hukommelse og hukommelse igen og igen men aldrig give det tilbage. 

Nu, da en side, viser det sig, at når et program afsluttes, alt hukommelse automatisk frigøres. Så det er ikke været et enormt meget. Det kommer ikke til at bryde IDE eller langsomme ting ned, men når programmer gør generelt lække hukommelse og de kører i lang tid. Hvis du nogensinde har set den dumme lille badebold i Mac OS eller timeglas på Windows, hvor det er slags bremse eller tænker eller tænker eller bare virkelig begynder at bremse til en gennemgang, det meget muligvis kunne være resultatet af en hukommelsesfejl. Programmørerne, der skrev den software, du bruger spørge operativsystemet for hukommelse hvert par minutter, hver time. Men hvis du kører software, selv om det er minimeres i din computer i timer eller dagevis, kan du spørge om mere og mere hukommelse og faktisk aldrig bruger det og så din kode kan være, eller programmer kan være utæt hukommelse, og hvis du begynder at lække hukommelse, der er mindre hukommelse til andre programmer, og virkningen er at bremse alt ned. 

Nu, dette er langt en af de mest grusomme programmer vil du have mulighed at køre i CS50 omfang som dens output er endnu mere esoteriske end klang s eller gøre os eller nogen af ​​kommandoen line programmer, vi har kørt før, men heldigvis, indlejret i sin produktion er nogle super nyttige tips, der vil være nyttig enten til pset fire eller i hvert fald POpret fem. Så Valgrind er et værktøj der kan bruges til at se for memory leaks i dit program. Det er relativt enkelt at køre. Du kører Valgrind og da, selv selvom det er lidt detaljeret, dash bindestreg lækage kontrol lig fuld, og derefter dot skråstreg og navnet på dit program. Så Valgrind vil derefter køre dit program og til allersidst af dit program kører før det afsluttes og giver dig en anden prompt, det kommer til at analysere din program, mens den er kørt og fortælle dig har du lække enhver hukommelse og bedre endnu, har du rører hukommelse, ikke tilhører dig? Det kan ikke fange alt, men det er temmelig god til at fange de fleste ting. 

Så her er et eksempel på min har kørt dette program, som har kørt Valgrind, på et program kaldet hukommelse, og jeg har tænkt mig at fremhæve de linjer, der er i sidste ende af interesse for os. Så der er endnu flere distraktioner at jeg har slettet fra slide. Men lad os bare se, hvad dette Programmet er i stand til at fortælle os. Det er i stand til at fortælle os ting ligesom ugyldig skrive størrelse 4. Med andre ord, hvis du rører hukommelsen, specielt 4 bytes hukommelse at du ikke skal have, Valgrind kan fortælle dig det. Ugyldig skrive størrelse 4. Du rørte fire bytes at du ikke skal have. Hvor har du det? Det er den skønhed. Hukommelse prik c linje 21 er, hvor du skruet op, og det er derfor, det er nyttigt. Meget gerne GDB, kan det hjælpe pege dig på det faktiske fejl. 

Nu, dette ene er lidt mere verbose, hvis ikke forvirrende. 40 bytes i 1 blokke er absolut tabt i tab post 1 af 1. Hvad betyder det? Tja, det betyder bare, du bad om 40 bytes og du aldrig gav det tilbage. Du kaldte malloc eller du kaldte GetString og operativsystemet gav dig 40 bytes, men du aldrig befriet eller frigjort, at hukommelsen, og for at være fair, har vi aldrig vise dig, hvordan du give tilbage hukommelse. Viser sig der er en super simpel funktion kaldes fri. Tager et argument, de ting du ønsker at frigøre eller give tilbage, men 40 bytes, tilsyneladende, i dette program er gået tabt på linje 20 hukommelse dot c. 

Så lad os se dette program. Det er super ubrugelig. Det viser kun denne særlige fejl. Så lad os tage et kig. Her er de vigtigste og vigtigste, skilte, opkald en funktion kaldet f og derefter vender tilbage. Så ikke alt, interessant. Hvad betyder f gøre? Bemærk, at jeg ikke gider med en prototype. Jeg ønskede at holde koden så minimale som muligt. Så jeg sætter f over hoved- og det er fint, i hvert fald, til korte programmer som dette. Så f returnerer ikke noget og gør ikke tage noget, men det gør gøre dette. Det erklærer, ligesom i Binky eksempel en pointer kaldet x, der kommer at gemme adressen på en int. Så det er den venstre side. På engelsk, hvad der er den højre side gør? Nogen? Hvad er det gør for os? Ja? 

PUBLIKUM: [uhørligt] gange større en int hvilket er 10 gange, at [uhørligt] DAVID MALAN: God og lad mig opsummere. Så afsætte nok plads til 10 heltal eller 10, hvad er på størrelse med en int, Det er fire bytes, så 10 gange 4 er 40, således at højre side, som jeg har fremhævede, er at give mig 40 bytes og gemme adressen på den første byte ind på x. Og nu endelig og her er hvor dette program er buggy, hvad er galt med linje 21, baseret på denne logik? Hvad er der galt med linje 21? Ja? PUBLIKUM: Du kan ikke indeks i x [uhørligt]. DAVID MALAN: Ja. Jeg skal ikke indeks i x som. Så syntaktisk, det er OK. Hvad er rart er, ligesom du kan behandle navnet på et array som om det er en pegepind, tilsvarende kan du behandle en pegepind, som om det er et array, og så jeg kan syntaktisk sige x beslag noget, x beslag i, men 10 er problematisk. Hvorfor? 

PUBLIKUM: Fordi det er ikke inde. 

DAVID MALAN: Det er ikke indeni, luns af hukommelse. Hvad er den største værdi, jeg skulle være at sætte i disse firkantede parenteser? 9, 0 til 9. På grund af nul indeksering. Så 0 til 9 ville være fint. Konsollen 10 er ikke god og men, husker dog, hver gang Jeg synes at forsøge at gøre CS50 IDE nedbrud ved at skrive i falske værdier, det ikke altid samarbejder, og ja, du ofte heldig bare fordi operativsystem ikke bemærke, at du nogensinde så lidt videregive nogle luns af hukommelse, fordi du holdt sig inden teknisk dit segment, men mere om det i et operativsystemer klasse, og så noget som dette kunne meget nemt gå uopdaget. Dit program er aldrig vil gå ned konsekvent, men måske en gang i et stykke tid. 

Og så lad os prøve Valgrind om dette, og her er hvor vi får overvældet af udgangen øjeblik. Så gør hukommelse Valgrind lækage kontrol lig fuld dot skråstreg hukommelse. Og her er hvorfor lover jeg dette ville overvælde. Her er hvad Valgrind, her er hvad en programmør, nogle år siden- besluttet, at det ville være en god idé for output til at ligne. Så lad os få mening ud af dette. Så hele vejen til venstre hånd side uden god grund er den proces ID af programmet vi bare køre, den entydige identifikator for det program, vi lige kørte. Vi udgår fra at dias, men der er nogle nyttige oplysninger i her. 

Lad os rulle op til toppen. Her er, hvor vi begyndte. Så det er ikke så meget output. Her er det ugyldigt skrive størrelse 4 på linie 21. Nå, hvad var linie 21? Linie 21 var præcis dette, og det giver mening at jeg er i gyldigt skrive 4 byte, fordi jeg er forsøger at sætte denne heltal, som kunne være noget, det bare sker for at være nul, men jeg prøver at sætte det på et sted der ikke tilhører mig. Desuden, hernede, 40 bytes i én blokke er afgjort tabt på rekordtid 1. Det er fordi når jeg kalder malloc her, jeg faktisk aldrig frigøre hukommelse. 

Så hvordan kan vi løse dette? Lad mig gå videre og være lidt mere sikker og gøre 9 der og lad mig her gratis på x. Dette er den nye funktion til dag. Hvis jeg nu køres igen gøre hukommelse dot skråstreg, Lad os køre Valgrind på det igen, maksimere mit vindue og tryk Enter. Nu er det godt. De begrave de gode nyheder i alt af denne produktion. Alle dynge blokke var frie. Vi vil komme tilbage til, hvad den bunke er, men ingen lækager er mulige. Så dette er blot en anden værktøj til din værktøjskasse som du kan begynde at find nu fejl som dette. 

Men lad os se, hvad mere kan gå galt her. Lad os overgang nu faktisk at løse et problem. Som en sidebemærkning, hvis det vil aflaste en lille smule forvirring eller spændinger, dette er nu sjovt. Ja. Det er temmelig godt. Fordi pointere er adresser og adresser er generelt konventionelt skrevet med hexadecimal. Ha, ha, det er sjovt nu. Under alle omstændigheder, så lad os nu faktisk løse et problem. Det har været super, Super lavt niveau hidtil, og vi kan faktisk gøre nyttig ting med disse lavt niveau detaljer. 

Så vi introducerede et par uger siden begrebet et array. Et array var rart, fordi det er svært at rydde op vores kode for hvis vi ønskede at skrive en program med flere studerende eller flere navne og huse, og sovesale og gymnasier og alt dette, vi kunne gemme alt mere rent inde i et array. Men foreslå én nedadrettede af et array hidtil. Selv hvis du ikke har lidt det selv i et program, bare instinktivt, hvad er en dårlig ting om et array, måske? Jeg hører nogle mumler. PUBLIKUM: Det er svært at ændre størrelsen. DAVID MALAN: Det er svært at ændre størrelsen. Du kan ikke ændre størrelsen af et array, i virkeligheden, i sig selv i C. Du kan tildele et andet array, flytte alt fra den gamle ind i det nye, og nu har nogle ekstra plads, men det er ikke som en sprog som Java eller Python eller en række andre sprog med hvilket nogle af jer kunne være bekendt, hvor man kan bare holde tilføje ting til bevidstløshed til enden af ​​et array. Når du har en bred vifte af størrelse 6, som er dets størrelse, og så meget lide tanken tidligere har en buffer med en vis størrelse, du nødt til at gætte ud af porten hvilken størrelse vil du have det til at være? Hvis du gætter for stor, du spilder plads. Hvis du gætter for lille, du kan ikke gemme disse data, i det mindste uden en masse mere arbejde. 

Så i dag, takket være pointere, vi kan begynde at sy sammen vores egne brugerdefinerede datastrukturer, og Faktisk her er noget der ser lidt mere kryptiske ved første øjekast, men det er det, vi vil kalde en sammenkædet listen, og dens navn slags sammenfatter det. Det er en liste over numre, eller i dette tilfælde en liste over numre, men det kunne være en liste over noget, men det er bundet sammen ved hjælp af pile, og bare tage et gæt med hvilken teknik vil vi være i stand til at sy sammen, lidt ligesom popcorn med en tråd, en sammenkædet lister rektangler her? Dens tal? Hvad er den underliggende sprog funktion? 

PUBLIKUM: En pointer. 

DAVID MALAN: En pointer. Så hver af disse pile repræsenterer her en pointer eller blot en adresse. Så med andre ord, hvis jeg vil at lagre en liste over numre, Jeg kan ikke bare gemme det, hvis jeg vil evnen til at vokse og skrumpe min datastruktur i et array. Så jeg har brug for at have en lille mere sofistikerede, men bemærker, at dette Billedet viser slags at hvis du lige har fået små tråde forbinde det hele sammen, sandsynligvis er ikke så svært at gøre plads mellem to af disse rektangler eller to af disse knudepunkter, da vi starter kalde dem, sat i en ny knude, og derefter med nogle nye tråd, bare grøft tre knudepunkter sammen, den første, den sidste og den at du bare indsat i midten. 

Og faktisk en sammenkædet liste, I modsætning til en array, er dynamisk. Det kan vokse og det kan skrumpe, og du ikke gør nødt til at vide eller pleje på forhånd, hvordan meget data du vil være opbevaring, men det viser sig, vi er nødt til at være lidt forsigtig med, hvordan man gennemfører dette. Så lad os først overveje, hvordan vi gennemfører en af ​​disse små rektangler. Det er nemt at implementere en int. Du skal bare sige int n og derefter du får 4 bytes for en int, men hvordan får jeg en int, kalder det n, og derefter en pegepind, lad os kalde det næste. Vi kunne kalde disse ting noget, vi ønsker men jeg har brug for en brugerdefineret datastruktur. Ja? 

PUBLIKUM: Ampersand [uhørligt]. 

DAVID MALAN: Så tegnet vi vil bruge til få adressen på en node potentielt. Men vi har brug for en anden træk ved C for at give mig mulighed for at oprette denne skik rektangel, denne skik variabel hvis du vil, i hukommelsen. PUBLIKUM: En struct. DAVID MALAN: A struct. Husker fra sidste uge, vi introducerede struct, denne relativt simple nøgleord der lader os gøre ting som dette. C kom ikke med en data struktur kaldet elev. Den leveres med int og float og fjeldørred og sådan, men det kommer ikke med studerende, men vi kan skabe en studerende datatype, en studerende struktur med denne syntaks her. Og du vil se det igen og igen. Så du skal ikke bekymre dig om huske de søgeord, men det søgeord, der er vigtigt, er bare det faktum, at vi sagde struct og så vi kaldte det studerende og inde af de studerende var et navn og et hus eller et kollegieværelse eller lignende. 

Og så nu i dag, lad os foreslå dette. Jeg har tilføjet et par ord, men hvis jeg ønsker at gennemføre denne rektangel, der er fik begge en int og pointer, ved du hvad, jeg er kommer til at erklære en struct kaldet node. Jeg er også, inde i den, vil sige at en node, dette rektangel, har en int og vi vil kalde det n og det har en næste pointer. Og det er lidt detaljeret, men hvis du tænker over det, pilene, der var i billedet et øjeblik siden, er af, hvad datatype? Hvor hver af disse pile peger til hvilken type af datastruktur? Det er ikke peger blot på en int per se. Det peger på Hele rektangulære ting og at rektangulære ting, vi sagde, kaldes en knude. Og så vi slags nødt til at rekursivt definere dette sådant at en node, skal vi sige, vil indeholde en int kaldes n og en pointer kaldet næste og type datastruktur, som at pointer punkter er tilsyneladende vil være struct node. 

Så dette er irriterende detaljeret og bare for at være pedantisk, grunden til, at vi ikke kan blot sige dette, som ærligt talt ser meget mere læsbar, er fordi tilbagekaldelse, at C læse ting top til bund, venstre til højre. Det er ikke, indtil vi får den semikolon at søgeordet node rent faktisk eksisterer. Så hvis vi ønsker at have denne form for cyklisk henvisning indersiden af ​​data struktur, vi er nødt til at gøre dette, hvor vi siger struct node foroven, som giver os en længere måde at beskrive dette ting, så inde vi siger struct node, og derefter i allersidste linje vi siger, okay, C, ved den måde, bare kalde hele denne forbandede ting en node og stoppe bruge søgeordet struct helt. Så dette er bare en slags syntaktisk trick, der i sidste ende lader os skabe noget, der ser ud præcis som dette. 

Så hvis vi antager nu vi kan gennemføre denne ting i C, hvordan gør vi faktisk begynde kørsel denne? Tja, i virkeligheden, alt, hvad vi skal gøre, er gentage fra venstre mod højre og lige slags indsætte knudepunkter eller slette knudepunkter eller søge efter ting, hvor vi vil, men for at gøre dette, så lad os gå videre og gøre tingene lidt mere reel, fordi dette har været super lavt niveau hidtil. Ville nogen bogstaveligt gerne være først? OK. Kom op. Hvad er dit navn? 

David: David. DAVID MALAN: David. Dejligt at møde dig. Også mig. Okay. Og vi har brug for et nummer 9. Ikke så god som første, måske. OK, nummer 9. En række 17, tak. Lad mig gå tilbage lidt længere. Nummer 22, skal du, og hvad med længere tilbage hvis jeg kan se nogen hænder med alt lys eller ingen. Nogen der bliver meldte lige der. Har du lyst til at komme op? Din underarm er magt går op. OK, 17. 22. 26 kommer ned. Vil nogen anden gerne forcefully-- Kom op. En egentlig frivillig. 

Så meget hurtigt, hvis du fyre kunne arrangere jer ligesom knudepunkterne på skærmen. Tak. Og du vil være 26. Alle rigtige og hurtige introduktioner. Så jeg er David, og du er også? David: David. DAVID MALAN: Og du er? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID MALAN: Taylor. Fremragende. Så dette er vores frivillige for i dag og gå videre og skift lidt på den måde, og bare gå videre og holde holde dine numre, som du er, eller din første tegn og bruge din venstre hånd, gå videre og bare gennemføre disse pile, bare så din venstre hånd er bogstaveligt talt peger på, hvad du skal pege på, og giv dig selv nogle rum, så vi kan visuelt se dine arme faktisk peger, og du kan bare pege slags på jorden er fint. 

Så her har vi en sammenkædet liste med en, to, tre, fire, fem knudepunkter i første omgang, og læg mærke til at vi har denne særlige pointer i begyndelsen, der er nøglen, fordi vi er nødt til at holde styr af hele længden listen eller anden måde. Disse fyre, selvom de er forladt mod højre, ryg mod ryg i hukommelsen, de rent faktisk kan være hvor som helst i computerens hukommelse. Så disse fyre kunne være stående overalt på scenen og det er fint, så længe de er faktisk peger på hinanden, men at holde tingene ren og enkel, vi får bare trække dem venstre til højre som dette, men der kunne være massive huller mellem disse knudepunkter. 

Nu, hvis jeg ønsker at faktisk indsætte nogle ny værdi, lad os gå videre og gøre dette. Vi har en mulighed nu at vælge en anden node. Sig lad os starte med mallocing 55. Ville nogen noget imod at være malloc? OK, kom op. Hvad er dit navn? RAINBOW: Rainbow. DAVID MALAN: Rainbow? Okay. Malloc Rainbow. Kom op. Så nu er vi nødt til at spørge os selv algoritmisk hvor vi kan sætte 55. Så alle os vide, naturligvis, hvor hun sandsynligvis hører, hvis vi prøver at holde denne sorteres og hvis du fyre kunne tage en skridt tilbage, så vi ikke falder af scenen, ville det være fantastisk. Så faktisk, Rainbow, starte forfra her hos mig, fordi vi som computeren nu kan kun se én variabel ad gangen. Så hvis dette er det første knudepunkt. Bemærk, han er ikke en knude, han er bare en pointer, og det er derfor han er draget til at være kun størrelsen af ​​en pegepind, ikke en af ​​de fulde rektangler. Så vi kommer til at kontrollere på hvert iteration er 55 mindre end 9? Nej. Er 55 mindre end 17? Nej. Mindre end 22? Mindre end 26? Mindre end 34? Og så nu, naturligvis Rainbow hører i slutningen. Så for at være klar, og hvad var dit navn, Taylor? 

TAYLOR: Taylor. DAVID MALAN: Så blandt Taylors venstre hånd og Rainbow hænder her, hvis hånd har brug for at pege på, hvad der i For at indsætte 55 i denne liste? Hvad skal vi gøre? Ja? 

PUBLIKUM: Taylors hånd nødt til at pege til venstre. 

DAVID MALAN: Præcis. Så indsætter en node ind i enden af ​​listen er ret enkel, fordi Taylor bare skal pege i stedet for på jorden eller vi vil kalde det null, null er sortering af fraværet af en pegepind eller en speciel nul pointer, du er kommer til at pege med venstre hånd på Rainbow og derefter Rainbow, Hvor skal din venstre hånd formentlig pege? Ned. Det er ikke godt, hvis hendes hånd er sortering at pege off her eller slags enhver hvilken vej. Det ville blive betragtet en skraldespand værdi, men hvis hun peger på nogle kendte værdi, vi får kalder det nul eller nul, det er OK fordi vi har et begreb i denne og vi ved listen er nu færdig. 

Så hvad er en anden forholdsvis enkel sag? Kunne vi malloc 5? Kom op. Hvad er dit navn? Tiffany: Tiffany. DAVID MALAN: Jeg er ked af? Tiffany: Tiffany. DAVID MALAN: Tiffany. Okay. Tiffany er blevet malloced med værdien 5. Kom op. Denne ene er forholdsvis let også, men lad os overveje rækkefølgen af ​​operationer nu. Det var temmelig let med Taylor i slutningen. Nummer 5 er naturligvis mindre end 9, og så har vi David, vi har Tiffany, og hvad var dit navn? 

JAKE: Jake. 

DAVID MALAN: Jake. Tiffany, Jake, og David. Hvis hånd bør opdateres først? Hvad vil du gøre her? Der er et par mulige måder, men der er også en eller flere forkerte måder. 

PUBLIKUM: Start med længst til venstre. 

DAVID MALAN: Start med den længst til venstre. Hvem er den længst til venstre her så? PUBLIKUM: Først. 

DAVID MALAN: OK. Så start med først og hvor har du vil opdatere Davids hænder til at være? PUBLIKUM: Mod 5. DAVID MALAN: OK. Så David, punkt fem eller Tiffany her, og nu? 

PUBLIKUM: Tiffany peger på 9? DAVID MALAN: Perfekt, undtagen Binky s leder bare lidt faldt, ikke? For hvad er der galt med dette billede bogstaveligt? PUBLIKUM: Ingenting peger. DAVID MALAN: Intet er peger på Jake nu. Vi har bogstaveligt forældreløse 9 og 17, og vi har bogstaveligt talt lækket hele denne hukommelse, fordi ved opdatering Davids hånd først, det er fint så vidt som det er korrekt peger på Tiffany nu, men hvis ingen havde fremsyn til at pege på Jake, så har vi mistet helhed af denne liste. Så lad os fortryde. Så det var en god ting at tur over men lad os rette nu. Hvad skal vi gøre først i stedet? Ja? 

PUBLIKUM: Tiffany skal pege på 9? DAVID MALAN: Jeg kan ikke få det tæt på dig. Hvem skal pege på 9? 

PUBLIKUM: Tiffany. 

DAVID MALAN: Okay. Så Tiffany bør første punkt på 9. Så Tiffany bør tage på en identisk værdi til David, som synes overflødige for et øjeblik, men det er fint, fordi nu, andet skridt, kan vi opdatere Davids hånd at pege på Tiffany, og derefter, hvis vi lige slags ren tingene op som om dette er slags forår-lignende, nu det er en korrekt isætning. Så fremragende. Så nu er vi der næsten. Lad os indsætte en sidste værdi som værdien 20. Hvis vi kunne malloc et sidste volontør? Kom op. Så denne ene er lidt mere tricky. Men virkelig, koden er vi skrivning, omend verbalt, er lige som at have en flok af hvis betingelserne nu, ikke? Vi havde en tilstand kontrollere, om det tilhører ved udgangen, måske begyndelsen. Vi har brug for en form for løkke til finde det punkt i midten. Så lad os gøre det med, hvad er dit navn? 

ERIC: Eric. 

DAVID MALAN: Eric? Eric. Dejligt at møde dig. Så vi har 20. Mindre end fem? Nej. Mindre end ni? Nej. Mindre end 17? Nej. OK. Han hører til her og jeres navne igen er? SUE: Sue. DAVID MALAN: Sue. ALEX: Alex. DAVID MALAN: Sue, Alex, og? ERIC: Eric. DAVID MALAN: Eric. Hvis hænder har brug for at få opdateret først? 

PUBLIKUM: Eric. OK. Så Erics skal pege på, hvor? Ved 22. Godt. Og nu, hvad det næste? Sue kan derefter pege på Eric og nu, hvis du fyre bare gøre nogle rum, som er fint visuelt, nu vi har gjort indsættelsen. Så lad os nu overveje et spørgsmål, men tak så meget for vores frivillige. Meget godt klaret. Du kan holde dem, hvis du vil. Og vi har en dejlig afsked gave, hvis du gerne hver gerne tage en stress bold. Lad mig blot videregive dette ned. Så hvad er takeaway dette? Dette synes at være fantastisk for så vidt vi har nu indført et alternativ til en array, der ikke er så begrænset til en matrix af en eller anden fast størrelse. De kan vokse dynamisk. 

Men meget ligesom vi har set i uger fortiden, vi aldrig få noget gratis, ligesom mon der ikke er en afvejning her. Så med en upside på en sammenkædet liste, er denne dynamik? Denne evne til at vokse og helt ærligt, vi kunne have gjort sletning og vi kunne skrumpe efter behov. Hvilken pris betaler vi? Dobbelt så meget plads, først og fremmest. Hvis du ser på billedet, der ikke længere er jeg lagring af en liste af heltal. Jeg lagring af en liste over heltal plus pointere. Så jeg fordoble mængden af ​​plads. Nu, måske det er ikke sådan en big deal 4 byte, 8 byte, men det kunne sikkert tilføje op til store datasæt. Hvad er en anden ulempe? Ja? 

PUBLIKUM: Vi er nødt til krydse dem én efter én. DAVID MALAN: Ja. Vi er nødt til at krydse dem én efter én. Ved du hvad, vi gav op denne super praktisk funktion af firkantede beslag notation, mere korrekt kendt som random access, hvor vi bare kan hoppe til et enkelt element men nu, hvis jeg stadig havde mine frivillige her, hvis jeg ønskede at finde den nummer 22, jeg kan ikke bare springe til konsollen noget noget. Jeg er nødt til at kigge over listen, meget ligesom vores søge eksempler lineært, at finde nummeret 22. Så vi synes at have betalt en pris der. Men vi kan alligevel løse andre problemer. 

Faktisk, lad mig introducere blot et par visuals. Så hvis du har været ned til Mathers Dining Hall for nylig, vil du huske, at deres stakke af bakker som denne, vi lånt disse fra Annenberg før klassen. Så denne stablen af ​​bakker, men repræsenterer faktisk af en computer science datastruktur. Der er en datastruktur i datalogi kendt som en stak, som meget pænt egner sig til netop denne visuelle. Så hvis hver af disse bakker er ikke en bakke men ligesom et nummer og jeg ønskede at lagre numre, I kunne sætte en hernede, og jeg kunne sætte en anden hernede, og fortsætte stabling numre oven på hinanden, og hvad der er potentielt nyttigt om dette er, at hvad er konsekvenserne af denne datastruktur? Hvilket nummer kan jeg trække sig ud første mest hensigtsmæssigt? Den senest én sat på der. 

Så dette er, hvad vi ville kalde i datalogi en LIFO datastruktur. Sidste ind, først ud. Og vi vil se inden længe, ​​hvorfor som kan være nyttige, men for nu, lige overveje ejendommen. Og det er lidt dum, hvis du tror om, hvordan den spisesal gør det. Hver gang de rene bakker og sætte de friskeste dem på toppen, du kunne have en tidligere rent men til sidst meget beskidt og støvede bakke i bunden hvis du aldrig faktisk komme til bunden af ​​denne stak, fordi du bare holde lægge det nye og ren dem oven på den. Det samme kan ske i et supermarked også. Hvis du har en montre mælk og hver gang CVS eller hvem får mere mælk, du bare puffe de mælk du allerede har til bagsiden og du sætte de nye op foran, du kommer til at have nogle temmelig ubehagelig mælk ved udgangen af ​​den datastruktur, fordi det er altid i bunden eller ækvivalent det er altid på bagsiden. 

Men der er en anden måde at tænke på foring op data og for eksempel, dette. Hvis du er en af ​​de mennesker, der kan lide at line op uden for Apple butikker når et nyt produkt kommer ud, er du sandsynligvis ikke bruger en stak af data struktur, fordi du ville fremmedgøre alle andre, der er kø for at købe nogle nye legetøj. Snarere, er du sandsynligvis bruge hvilken slags datastruktur eller hvilken form for systemet i den virkelige verden? Forhåbentlig er det en linje, eller mere korrekt, eller mere britisk-lignende, en kø. Og det viser sig en kø er også en datastruktur i datalogi, men en kø har en meget anden egenskab. Det er ikke LIFO. Sidste ind, først ud. Gud forbyde. Det er i stedet FIFO. Først ind, først ud. Og det er en god ting for retfærdighed 'skyld sikkert, når du foring op super tidligt om morgenen. Hvis du får der først, du ønsker at komme ud først så godt. 

Og så alle disse data strukturer, køer og stakke og klaser af andre, viser sig du kan tænke på det som bare et array. Dette er en matrix, måske en fast størrelse 4, men det ville være slags rart, hvis vi bare kunne hobe bakker næsten uendeligt høje, hvis vi have så mange bakker eller tal. Så måske vil vi bruge en sammenkædet liste her, men trade-off vil være potentielt at vi har brug for mere hukommelse, tager lidt mere tid, men vi begrænser ikke højden af ​​stablen, meget gerne Mathers montre kan begrænse størrelsen af ​​stakken, og så disse er designbeslutninger eller muligheder til rådighed for os i sidste ende. Så med disse data strukturer, vi har i gang se nye øvre grænser potentielt om, hvad der tidligere var super hurtig og hvor vi vil forlade off dag, og hvor vi håber at komme til er på onsdag, vi får begynde at se på en data struktur, der lader os søge gennem data i log sluttidspunkt igen. Og vi så, at, husker, i uge nul og en med binær søgning eller kløft og erobre. Det kommer tilbage og bedre endnu, den hellige gral for denne onsdag vil være at komme op med den datastruktur, der kører virkelig eller teoretisk i konstant tid, hvorved det er ligegyldigt, hvor mange millioner eller milliarder af ting vi har i datastruktur, vil det tage os konstant tid, måske et skridt eller to trin eller 10 trin, men konstante antal trin at søge gennem den datastruktur. Det rent faktisk vil være den hellige gral men mere om det på onsdag. Se ya derefter. 

[Musik spiller]