[Powered by Google Translate] [Uge 6] [David J. Malan] [Harvard University] [Dette er CS50.] [CS50.TV] 

Dette er CS50, og dette er begyndelsen af ​​uge 6, så et par nye værktøjer er nu tilgængelige for dig at drage fordel af, hvoraf det første kaldes CS50 Style. Odds er, hvis du er ligesom mig eller nogen af ​​de pædagogiske stipendiater, du har sikkert set et program, hvis stil minder lidt noget som dette. Måske du begynde at skære nogle hjørner sent på aftenen, eller du vil beskæftige sig med det senere, og derefter en TF eller CA kommer over i kontortiden. Så er det svært for os at læse. Nå, denne kode er syntaktisk korrekt, og det vil kompilere, og det vil faktisk køre. Men det er bestemt ikke en 5 for stil. 

Men nu, hvis vi går ind i denne mappe her- og bemærk, at jeg har conditions2.c- og jeg kører denne nye kommando, style50, om denne sag conditions2.c, Enter, bemærke, at det er meddelt mig, at det har været stiliseret. Gedit bemærket, at filen er blevet ændret på disken, og hvis jeg klikker genindlæse, er alle dine problemer nu automatiseret. [Bifald] Det er en af ​​de ting, vi gjorde denne weekend. Indse, at det er ufuldkommen, fordi der er noget kode at det ganske enkelt ikke kunne stilisere perfekt, men indser dette er nu et værktøj, du kan drage fordel af hvis der kun at rydde op nogle af de mere errantly placeret krøllede parenteser og lignende. 

Men mere overbevisende nu er CS50 Check. Med CS50 Check, kan du faktisk udfører de samme korrekthed tests på din egen kode, som de pædagogiske stipendiater er i stand til. Dette er en kommandolinje utility, der kommer nu i apparatet så snart du gør en update50 som pr Pset 4 specifikationer, og du bruger det hovedsageligt som denne. Du kører kommandoen check50. Så du passerer på en kommandolinje argument, eller mere almindeligt kendt som en switch eller et flag. Generelt er ting, der har bindestreger kaldes en switch til en kommandolinje program, specificerer så-c den kontrol, som du vil køre. 

De test, du vil køre identificeres entydigt af denne streng, 2012/pset4/resize. Med andre ord, er det bare en vilkårlig, men unik streng at vi bruger til entydigt at identificere Pset 4 korrekthed tests. Og så skal du angive et mellemrum adskilt liste over de filer, du vil uploade til CS50 Tjek for analyse. For eksempel-resize.c hvis jeg går ind i mit løsning her lad mig åbne op for en større terminal vindue- og jeg gå videre og køre lad os sige check50-c 2012/pset4/resize, og så vil jeg gå videre og angive navnene på de filer, resize.c, og derefter trykke på Enter, det komprimerer, det uploads, kontrollerer, og jeg bare ikke en hel masse tests. Den ene i rød øverst til venstre siger, at resize.c og bmp eksisterer. Det var testen. Det var det spørgsmål, vi stillede. Og det er ulykkelig, fordi svaret var falsk. Den hvide teksten nedenfor den siger forventet bmp.h at eksistere, og det er simpelthen min skyld. Jeg glemte at uploade det, så jeg er nødt til at uploade begge filer, resize.c og bmp.h. Men nu mærke alle de andre prøver er i gult, fordi de ikke har kørt, og så det smilende ansigt er lodret, fordi han er hverken tilfredse eller ked af det, men vi er nødt til at rette op på dette problem i rød før de andre kontroller vil køre. 

Lad mig ordne det. Lad mig zoome ud og kør dette, denne gang med bmp.h også på kommandolinjen, Enter, og nu, hvis alt går vel, det kommer til at kontrollere og derefter returnere et resultat af-holde vejret- alle grønne, hvilket betyder, jeg gør rigtig godt på Pset 4 indtil videre. Du kan se og udlede af beskrivende tekst her præcis hvad det er, vi testede. Vi testede først gøre filerne eksisterer? Vi derefter testet gør resize.c kompilere? Så vi testede det ikke ændre størrelsen på en 1x1-pixel BMP når n, resize faktor, er 1. Nu, hvis du har ingen idé om hvad n er, vil du, når du dykke ned i Pset 4, men det er simpelthen en sanity tjek for at sikre, at du ikke er resizing et billede på alle, hvis det resize faktoren er 1. Hvis det derimod, tilpasser det en 1x1 pixel til en 1x1 pixel BMP til 2x2 korrekt når n er 2, så er ligeledes min danner tilsvarende. 

Kort sagt er dette betød at, en, tage de krydser fingrene ud af ligningen, lige før du sender din Pset. Du vil vide præcis, hvad din TF snart vil vide når du går om at indsende nogle af disse problematiske sæt, og også den pædagogiske motivation er virkelig at sætte mulighed foran dig, så når du kender a priori at der er fejl i din kode og tests, som ikke bliver bestået, du kan sætte i en mere effektiv tid up front til at løse disse problemer snarere end at miste point, få feedback fra din TF, og derefter gå, "Ahh," som jeg burde have regnet det ud. Nu i det mindste er der et værktøj til at hjælpe dig med at finde det. Det kommer ikke til at pege på, hvor fejlen er, men det vil fortælle dig hvad er symptomatisk for det. 

Nu indser testene er ikke nødvendigvis udtømmende. Bare fordi du får en skærm fuld af grønne smiley ansigter betyder ikke, at din kode er perfekt, men det betyder at det har bestået visse prøver foreskrevet af spec. Nogle gange vil vi ikke frigive checks. For eksempel, mordmysterium et af aspekterne af Pset 4 er slags skuffende, hvis vi giver dig svaret på, hvad det er, og der er en række måder at afsløre hvem personen er i det røde støj. Den spec vil altid angive i fremtiden for Pset 5 og fremefter Hvilken kontrol eksisterer for dig. Du vil bemærke, at der er denne hvide webadresse nederst. For nu er det bare diagnostisk udgang. Hvis du besøger denne webadresse, vil du få en hel bunke af skøre, kryptiske beskeder at du er velkommen til at kigge igennem, men det er mest for personalet så vi kan diagnosticere og fejlsøge bugs i check50 selv. 

Uden ado, lad os gå videre til, hvor vi slap. CS50 bibliotek vi tog for givet i nogle uger, men så i sidste uge, begyndte vi skrælning tilbage en af ​​lagene af det. Vi begyndte at se bort streng til fordel for hvad i stedet? [Studerende] Char. Char *, som har været en char * al denne tid, men nu har vi ikke nødt til at foregive, at det er et virkeligt datatype streng. Snarere har det været et synonym slags for char *, og en streng er en række tegn, så hvorfor giver det mening at repræsentere strenge som char * s? Hvad betyder en char * repræsentere i forbindelse med dette begreb en streng? Ja. >> [Student] Det første tegn. Godt, det første tegn, men ikke helt det første tegn. Det er de-[Studerende] Adresse. Godt, adressen på det første tegn. Alt, hvad der er nødvendigt for at repræsentere en snor i en computers hukommelse er blot den entydige adresse for sin allerførste byte. Du behøver ikke engang at vide, hvor længe det er fordi hvordan kan du finde ud af dynamisk? [Student] String længde. Du kan ringe streng længde, fremragende, men hvordan gør streng længde arbejde? Hvad gør det? Yeah. [Student] holde ud, indtil du får den null-tegn. Ja, præcis, det bare gentager med en for-løkke, mens loop, uanset fra * til slutningen, og slutningen er repræsenteret ved \ 0,, den såkaldte NUL karakter, NUL ikke at forveksle med null, hvilket er en pointer, som vil komme op i samtalen igen i dag. 

Vi flåede tilbage et lag af GetInt, og derefter tog vi et kig på GetString, og minde om, at begge af disse funktioner, eller virkelig, GetString, var ved hjælp af en bestemt funktion til rent faktisk at parse, er, at læse eller analysere, brugerens input. Og hvad var det nye funktion? Scanf eller sscanf. Det faktisk kommer i et par forskellige varianter. Der er scanf, der er sscanf, der er fscanf. For nu, men lad os fokusere på den ene lettest illustreret, og lad mig gå videre og åbne op i apparatet en fil som denne, scanf1.c. Dette er et super simpelt program, men det gør noget, som vi aldrig har gjort uden hjælp af CS50 biblioteket. Dette får en int fra en bruger. Hvordan fungerer det? Tja, i linie 16 der, bemærke, at vi erklærer en int kaldet x, og på dette tidspunkt i historien, hvad er værdien af ​​x? [Uhørlig student svar] [David M.] Højre, hvem ved, nogle skrald værdi potentielt, så i 17, vi bare fortælle brugeren giv mig et nummer, please, og trin 18 er her, det bliver interessant. Scanf synes at låne en ide fra printf i, at det bruger disse formater koder i anførselstegn. % D er naturligvis et decimaltal. Men hvorfor har jeg passerer i & x stedet for bare x? Førstnævnte er korrekt. Yeah. [Uhørlig student svar] Nøjagtigt, hvis Målet med dette program, som funktion GetInt selv, er at få en int fra brugeren jeg kan passere funktioner alle de variable jeg vil, men hvis jeg ikke kan passere dem ved henvisning eller efter adresse eller pointer, alle synonym for nutidens formål så denne funktion ikke har nogen mulighed for at ændre indholdet af denne variabel. Dette ville passere i en kopi ligesom buggy version af swap at vi har talt om et par gange nu. 

Men i stedet, ved at gøre & x, jeg bogstaveligt passerer i hvad? [Student] Adressen. >> Adressen på x. Det er ligesom at tegne et kort for den funktion kaldet scanf og siger her, disse er retninger til en luns af hukommelse i computeren at du kan gå gemme nogle heltal i. For sscanf nu gøre det hvad operatør, hvad stykke syntaks det nødt til at bruge selv om vi ikke kan se det, fordi en anden skrev denne funktion? Med andre ord - hvad er det? [Student] X læse. Der kommer til at være nogle læsning, men kun med hensyn til x her. Hvis scanf bliver passeret adresse x, syntaktisk, hvad operatør forpligtet til at eksistere et eller andet sted indersiden af ​​scanf gennemførelse, således at scanf kan faktisk skrive en nummer 2 til denne adresse? Ja, så *. Husk på, at den * er vores dereference operatør, som i det væsentlige betyder derned. 

Når du har fået udleveret en adresse, som det er tilfældet her, scanf er sandsynligvis-hvis vi faktisk set omkring sin kildekode- gør * x eller tilsvarende til rent faktisk at gå til den pågældende adresse og sætte nogle værdi der. Nu, for hvordan scanf får input fra tastaturet, vi vinke vores hænder ud for i dag. Bare antage, at operativsystemet tillader sscanf at tale til brugerens tastatur, men på dette tidspunkt nu i ledningen 19, når vi enkelt udskrive x, det synes at være tilfældet at scanf har sat en int i x. Det er præcis, hvordan scanf virker, og genkalde sidste uge det er præcis, hvordan GetString og GetInt og sin anden familie af funktioner sidste ende fungerer, omend med mindre varians som sscanf, hvilket betyder scanne en streng i stedet for tastaturet. Men lad os tage et kig på en lille varians dette. I scanf2, faktisk jeg skruet op. Hvad er der galt, og jeg vil skjule den kommentar, der forklarer så meget hvad er der galt med dette program, version 2? Vær så teknisk som muligt denne gang. Det ser ret godt. Det er pænt indrykket, men- okay, hvad med lad os beskære det ned til kortere spørgsmål? Linje 16. Hvad er linie 16 gør i præcis men teknisk engelsk? Kom lidt akavet. Ja, Michael. [Student] Det peger på det første bogstav i en streng. 

Okay, tæt på. Lad mig tweak at en lille smule. Peger på det første bogstav i en streng, er du erklære en variabel kaldet buffer der vil pege på den første adresse på en snor, eller snarere vil der peger mere specifikt en char. Bemærk det er faktisk ikke peger nogen steder, fordi der er ingen opgave operatør. Der er ingen lighedstegn, så alle vi laver, er fordelingen af ​​den variable kaldet buffer. Det sker for at være 32 bit, fordi det er en pointer, og indholdet af puffer sandsynligvis med tiden vil indeholde en adresse på en char, men for nu, hvad buffer indeholde? Blot nogle falske, hvem ved, nogle skrald værdi, fordi vi ikke eksplicit har initialiseret det, så bør vi ikke noget for givet. Okay, så nu linie 17 er-hvad gør linje 17 gør? Måske vil varme det op. Den udskriver en streng, ikke? Den udskriver String behage. 

Linje 18 er slags velkendt nu i, at vi har lige set en varians af denne men med et andet format kode, så i ledningen 18, vi fortæller scanf her er adressen på en luns af hukommelse. Jeg vil have dig til at ringe i en snor, som det fremgår af% s, men problemet er, at vi ikke har gjort et par ting her. Hvad er et af problemerne? [Student] Det er at forsøge at dereference en null-pointer. Gode, null eller bare ellers ukendt pointers. Du rakte scanf en adresse, men du har lige sagt for et øjeblik siden at denne adresse er nogle skrald værdi, fordi vi faktisk ikke tildele den til noget som helst, og så du fortæller scanf faktisk gå sætte en snor her, men vi ved ikke, hvor her endnu er, så vi har faktisk ikke allokeret hukommelse til buffer. Desuden, hvad er du heller ikke selv fortæller scanf? Forestil dette var en luns af hukommelse, og det var ikke en garbage værdi, men du stadig ikke fortælle scanf noget vigtigt. [Student] Hvor det egentlig er, tegnet. Ampersand, så i dette tilfælde, er det okay. Fordi buffer allerede er erklæret som en pegepind med * stykke syntaks, behøver vi ikke at bruge tegnet fordi det er allerede en adresse, men jeg tror jeg hørte det her. [Student] Hvor stor er den? Godt, vi ikke fortæller scanf hvor stor denne buffer er, hvilket betyder, at selv om puffer var en pointer, vi siger scanf, sætte en snor her, men her kunne være 2 byte, det kunne være 10 byte, kan det være en megabyte. Scanf har ingen idé om, og fordi det er en luns af hukommelse formentlig, det er ikke en streng endnu. Det er kun en streng, når du skriver tegn og en \ 0 til at bid af hukommelse. Nu er det bare nogle bid af hukommelse. Scanf vil ikke vide, hvornår de skal stoppe med at skrive til denne adresse. 

Hvis du husker nogle eksempler i fortiden, hvor jeg tilfældigt indtastet på tastaturet forsøger at løbe en buffer, og vi talte i fredags om netop dette. Hvis en modstander eller anden måde sprøjter ind i dit program en meget større ord eller sætning eller et udtryk så du forventede, kan du overskredet en luns af hukommelse, hvilket kan have dårlige konsekvenser, ligesom at overtage hele programmet selv. Vi er nødt til at løse dette eller anden måde. Lad mig zoome ud og gå i version 3 af dette program. Det er en lille smule bedre. I denne version, se forskellen. I linje 16, jeg igen at erklære en variabel kaldet buffer, men hvad er det nu? Det er en bred vifte af 16 tegn. Det er godt, fordi det betyder jeg kan nu fortælle scanf her er et virkeligt bid af hukommelse. Man kan næsten tænke på arrays som pejlemærker nu, selvom de er faktisk ikke tilsvarende. De vil opføre sig forskelligt i forskellige sammenhænge. Men det er helt sikkert sådan, at bufferen refererer 16 sammenhængende tegn, fordi det er, hvad et array er og har været i nogle uger nu. 

Her fortæller jeg scanf her er en bid af hukommelse. Denne gang, er det faktisk en bid af hukommelse, men hvorfor er dette program stadig kan udnyttes? Hvad er der galt endnu? Jeg har sagt give mig 16 bytes men- [Student] Hvad hvis de skriver i mere end 16? Præcis, hvad nu hvis brugeren skriver i 17 tegn eller 1700 karakterer? Faktisk, lad os se om vi ikke kan snuble over denne fejl nu. Det er bedre, men ikke perfekt. Lad mig gå videre og køre make scanf3 at kompilere dette program. Lad mig løbe scanf3, String venligst: hej, og vi synes at være okay. Lad mig prøve en lidt længere, hello there. Okay, lad os gøre hello there hvordan er du i dag, Enter. Kom slags heldig her, lad os sige hello there how are you. Fandens. Okay, så vi fik heldig. Lad os se om vi ikke kan løse dette. Nej, det vil ikke lade mig kopiere. Lad os prøve det igen. Okay, stand by. Vi vil se, hvor længe jeg kan foregive at fokusere, mens du stadig gør dette. Fandens. Det er temmelig relevant, faktisk. Der vi går. Punkt,. 

Dette, pinligt selvom det også er, er det også en af ​​kilderne til stor forvirring når du skriver programmer, der har bugs, fordi de manifesterer sig kun en gang imellem til tider. Virkeligheden er, at selvom din kode helt brudt, det kan kun blive helt ødelagt en gang imellem fordi nogle gange, væsentligt, hvad der sker, er operativsystemet tildeler lidt mere hukommelse end du faktisk har brug for uanset årsagen, og så ingen andre bruger hukommelsen lige efter din bid af 16 tegn, så hvis du går til 17, 18, 19, uanset, det er ikke sådan en big deal. Nu, computeren, også selv om det ikke gå ned på det tidspunkt, kan i sidste ende bruge byte nummer 17 eller 18 eller 19 for noget andet, på hvilket tidspunkt dine data, som du lægger der, omend alt for lange, vil få overskrevet potentielt af en anden funktion. Det er ikke nødvendigvis kommer til at forblive intakt, men det vil ikke nødvendigvis medføre en seg fejl. Men i dette tilfælde, jeg endelig forudsat nok tegn at jeg hovedsagelig overskredet min segment af hukommelse, og bam, operativsystemet sagde: "Beklager, det er ikke godt, segmenteringsfejl." 

Og lad os nu se, om der er tilbage her i min mappe- bemærke, at jeg har denne fil her, kerne. Bemærk, at dette igen kaldes et core dump. Det er hovedsageligt en fil, der indeholder indholdet af dit program hukommelse på det sted, hvor det gik ned, og bare for at prøve et lille eksempel her lade mig gå ind her og køre gdb på scanf3 og derefter angive en tredje argument kaldet kerne, og læg mærke til her, at hvis jeg nævne koden, vi vil være i stand som sædvanlig med gdb at begynde at gå gennem dette program, og jeg kan køre det, og så snart jeg hit-som med trin kommandoen i gdb- så snart jeg ramte den potentielt buggy linje efter at skrive i en enorm streng, Jeg vil være i stand til rent faktisk at identificere den her. Mere om dette, men i snit med hensyn til vigtige lossepladser og lignende, så du kan faktisk stikke rundt inde i kernen dump og se på, hvilken linje programmet mislykkedes dig. Eventuelle spørgsmål derefter på pegepinde og adresser? Fordi i dag på, vi kommer til at begynde at tage for givet, at disse ting eksisterer og vi ved præcis, hvad de er. Ja. 

[Student] Hvordan kommer du ikke nødt til at sætte et og-tegn ved siden af ​​del- Godt spørgsmål. Hvordan kommer jeg behøvede ikke at sætte et og-tegn ud for tegn array, som jeg gjorde tidligere med de fleste af vores eksempler? Det korte svar er arrays er lidt speciel. Man kan næsten tænke en buffer som faktisk at være en adresse, og det bare så sker for at være tilfældet, at den firkantede beslag notation er en bekvemmelighed, så vi kan gå ind i konsollen 0, beslag 1, beslag 2, uden at skulle bruge * notation. Det er lidt af en hvid løgn fordi arrays og pointers er i virkeligheden en lille smule anderledes, men de kan ofte, men ikke altid anvendes i flæng. Kort sagt, når en funktion forventer en pointer til en bid af hukommelse du kan enten give det en adresse, der blev returneret af malloc, og vi vil se malloc igen inden længe, ​​eller man kan sende navnet på et array. Du behøver ikke at gøre tegnet med arrays, fordi de er allerede det væsentlige lignende adresser. Det er den eneste undtagelse. De kantede parenteser gør dem særligt. 

Kunne du sætte et og-tegn ved siden af ​​buffer? Ikke i dette tilfælde. Det ville ikke fungere, fordi, igen, for dette hjørne sag hvor arrays er ikke helt faktisk adresser. Men vi vil måske komme tilbage til det inden længe med andre eksempler. Lad os prøve at løse et problem her. Vi har en datastruktur, som vi har brugt i et stykke tid kendt som en matrix. Sag i punkt, det er hvad vi lige har haft. Men arrays har nogle upsides og ulemper. Arrays er nice hvorfor? Hvad er én ting, du kan lide til det omfang, du kan lide arrays-om arrays? Hvad er praktisk med dem? Hvad er overbevisende? Hvorfor har vi introducere dem i første omgang? Yeah. [Student] De kan gemme en masse data, og du behøver ikke at bruge en hel ting. Du kan bruge en sektion. Godt, med et array kan du gemme en masse data, og du behøver ikke nødvendigvis at bruge det hele, så du kan overallocate, som kan være praktisk, hvis du ikke kender på forhånd, hvor mange af noget at forvente. 

GetString er et perfekt eksempel. GetString, skrevet af os, har ingen idé om hvor mange tegn til at forvente, så det faktum, at vi kan afsætte bidder af sammenhængende hukommelse er god. Arrays også løse et problem, vi oplevede for et par uger siden nu hvor din kode begynder at udvikle sig til noget meget dårligt designet. Husk på, at jeg oprettede en studerende struktur kaldet David, og så var det faktisk et alternativ, selv om, at have en variabel kaldet navn og en anden variabel kaldet, tror jeg, hus, og en anden variabel kaldet ID fordi den historie jeg så ville indføre noget andet gerne Rob i programmet, så da jeg besluttede vente et minut, Jeg har brug for at omdøbe disse variabler. Lad os kalde mine navn1, ID1, House1. Lad os kalde Robs navn2, house2, ID2. Men så vent lige lidt, hvad med Tommy? Derefter havde vi yderligere tre variabler. Vi introducerede en anden, fire sæt variabler. Verden begyndte at få rodet meget hurtigt, så vi indført struct, og hvad der er overbevisende om en struct? Hvad betyder en C struct lade dig gøre? Det er virkelig akavet i dag. Hvad? >> [Uhørlig student svar] Ja, specifikt typedef giver dig mulighed for at oprette en ny datatype, og struct, den struct søgeordet, kan du indkapsle begrebsmæssigt relateret stykker af data sammen og derefter kalde dem noget som en elev. 

Det var godt, fordi vi nu kan modellere meget mere slags begrebsmæssigt konsekvent begrebet en elev i en variabel stedet for vilkårligt at have en for en streng, en for et ID, og ​​så videre. Arrays er rart, fordi de giver os mulighed for at begynde at rydde op vores kode. Men hvad er en downside nu af et array? Hvad kan du ikke? Yeah. [Student] Du er nødt til at vide, hvor stor den er. Du er nødt til at vide, hvor stor den er, så det er lidt af en smerte. De af jer med forudgående erfaring med programmering ved, at i mange sprog, ligesom Java, kan du bede en bid af hukommelse, specielt en array, hvor stor er du, med en længde, ejendom, så at sige, og det er virkelig praktisk. I C, kan du heller ikke ringe strlen på en generisk række fordi strlen, som ordet antyder er kun for strygere, og du kan finde ud af længden af ​​en streng på grund af denne menneskelige konvention af at have en \ 0, men et array, og mere generisk er bare en bid af hukommelse. Hvis det er en vifte af int'er, har der ikke vil være nogle særlige karakter i slutningen venter på dig. Du er nødt til at huske længden af ​​et array. En anden ulempe ved et array opdrættet sit hoved i GetString selv. Hvad er en anden ulempe ved et array? Sir, bare dig og mig i dag. [Uhørlig student svar] >> Det er hvad? Det er deklareret på stakken. Okay, erklærede på stakken. Hvorfor kan du ikke lide det? [Student] Fordi det bliver genbrugt. Det bliver genbrugt. Okay, hvis du bruger et array til at allokere hukommelse, du kan ikke, for eksempel, returnere det, fordi det er på stakken. Okay, det er en ulempe. Og hvad med en anden med et array? Når du tildeler det, du slags skruet hvis du har brug for mere plads end matrix har. 

Så vi indført, tilbagekaldelse, malloc, som gav os mulighed for dynamisk tildele hukommelse. Men hvad nu, hvis vi prøvede en anden verden helt? Hvad hvis vi ønskede at løse et par af disse problemer så vi i stedet, min pen er faldet i søvn her- hvad nu hvis vi i stedet ønskede at væsentlige skabe en verden, der ikke længere sådan? Dette er en matrix, og naturligvis forringer denne type når vi ramt ende af formationen, og jeg nu ikke længere har plads til en anden heltal eller anden karakter. Hvad hvis vi slags preemptively sige godt, hvorfor vi ikke slappe af dette krav, at alle disse klumper af hukommelsen støde op ryg mod ryg, og hvorfor ikke, når jeg har brug for en int eller en char, bare giv mig plads til en af ​​dem? Og når jeg brug for en anden, giv mig en anden plads, og når jeg brug for en anden, giv mig en anden plads. Fordelen ved som nu er, at hvis en anden tager hukommelsen herovre, no big deal. Jeg tager det ekstra bid af hukommelse her og derefter denne ene. 

Nu er den eneste fangst her er, at dette næsten føles som jeg har en hel masse forskellige variabler. Det føles som fem forskellige variabler potentielt. Men hvad hvis vi stjæle en idé fra strenge hvorved vi på en måde knytte disse ting sammen konceptuelt, og hvad hvis jeg gjorde det? Dette er min meget dårligt trukket pil. Men antag, at hver af disse klumper af hukommelse pegede på den anden, og denne fyr, der ikke har nogen søskende til sin ret, har ingen sådan pil. Det er i virkeligheden det, der kaldes en sammenkædet liste. Dette er en ny datastruktur, der giver os mulighed for at afsætte en bid af hukommelse, derefter en anden, derefter en anden, derefter en anden, helst vi ønsker i løbet af et program, og vi husker, at de er alle en eller anden måde relaterede ved bogstaveligt kæde dem sammen, og vi gjorde det billedligt her med en pil. Men i kode, hvad ville være den mekanisme, via hvilken du kan eller anden måde forbinde, næsten som Scratch,? en luns til en anden luns Vi kunne godt bruge en pegepind, right? Fordi virkelig den pil der kommer fra den øverste venstre firkant, denne fyr her til denne ene, kan indeholde inde i denne firkant ikke blot nogle int'er, ikke bare nogle char, men hvad hvis jeg rent faktisk er forbeholdt lidt ekstra plads, så nu, hver af mine bidder af hukommelsen, selvom det kommer til at koste mig, ser nu lidt mere rektangulært hvor en af ​​klumper af hukommelse anvendes til en række, som tallet 1, og derefter, hvis denne fyr gemmer tallet 2, denne anden luns af hukommelsen bruges til en pil, eller mere konkret, en pegepind. Og hvis jeg gemme nummeret 3 over her, mens jeg bruge dette til at pege på den fyr, og nu denne fyr, lad os antage jeg ønsker kun tre sådanne bidder af hukommelsen. Jeg vil tegne en linje gennem dette, hvilket indikerer null. Der er ingen yderligere tegn. 

Faktisk er det, hvordan vi kan gå om gennemførelsen noget, der hedder en sammenkædet liste. En linket liste er en ny datastruktur, og det er et springbræt mod meget mere avanceret datastrukturer, der begynder at løse problemer i lighed med Facebook-type problemer og Google-type problemer hvor du har store datasæt, og det ikke længere skærer det at gemme alt tilstødende og bruge noget lignende lineær søgning eller endda noget lignende binær søgning. Du ønsker endnu bedre køretider. Faktisk har vi et af de hellige Grails vil tale om senere i denne uge eller næste er en algoritme, hvis driftstid er konstant. Med andre ord altid det tager den samme tid, uanset hvor stor indgangen er, og det ville virkelig være overbevisende, endnu højere grad end noget logaritmisk. Hvad er det på skærmen her? Hver af de rektangler er præcis, hvad jeg netop har tegnet i hånden. Men de ting hele vejen til venstre er en speciel variabel. Det kommer til at være en enkelt pointer, fordi den ene gotcha med en linket liste, som disse ting kaldes er, at du er nødt til at holde fast i den ene ende af den linkede liste. 

Ligesom med en snor, er du nødt til at kende adressen på den første char. Samme deal for hægtede lister. Du er nødt til at kende adressen på den første bid af hukommelse fordi derfra, kan du nå hver anden. Downside. Hvilken pris betaler vi for denne alsidighed af at have en dynamisk anselig datastruktur, at hvis vi nogensinde har brug for mere hukommelse, fint, bare tildele endnu en luns og tegne en pointer fra den gamle til den nye hale af listen? Yeah. [Student] Det tager omkring dobbelt så meget plads. Det tager dobbelt så meget plads, så det er absolut en ulempe, og vi har set det tradeoff før mellem tid og rum og fleksibilitet hvor ved nu, behøver vi ikke 32 bit for hver af disse numre. Vi virkelig skal 64, 32 for antallet og 32 for markøren. Men hey, jeg har 2 GB RAM. Tilføjer en anden 32 bits her og her synes ikke så stor en deal. Men for store datasæt, det definitivt tilføjer op til bogstaveligt talt dobbelt så meget. Hvad er en anden downside nu, eller hvad funktionen giver vi op, hvis vi repræsenterer lister over ting med en linket liste og ikke et array? [Student] Du kan ikke krydse den bagud. Du kan ikke krydse den baglæns, så du slags skruet hvis du går fra venstre til højre ved hjælp af en for-løkke eller en while-løkke og derefter du indse, "Åh, jeg ønsker at gå tilbage til begyndelsen af ​​listen." Man kan ikke, fordi disse pejlemærker kun gå fra venstre mod højre som pilene viser. 

Nu kan du huske starten af ​​listen med en anden variabel, men det er en kompliceret at huske på. Et array, uanset hvor langt du går, kan du altid gøre minus, minus, minus, minus og gå tilbage hvorfra du kom. Hvad er en anden downside her? Yeah. [Uhørlig student spørgsmål] Du kan, så du har faktisk lige foreslået en datastruktur kaldet en dobbelt linket liste, og ja, ville du tilføje endnu en pegepind til hver af disse rektangler der går den anden retning, hovedet af hvilken er nu du kan krydse frem og tilbage, ulempen ved som nu du bruger tre gange så meget hukommelse som vi plejede at og også tilføje kompleksitet i forhold til den kode, du skal skrive for at få det rigtige. Men disse er alle måske meget rimelige kompromiser, hvis tilbageførslen er mere vigtigt. Yeah. [Student] Du kan heller ikke have en 2D linket liste. Godt, kan du ikke rigtig har en 2D linket liste. Du kunne. Det er ikke nær så let som en matrix. Ligesom et array, gør du åbne beslag, lukket beslag, åben beslag, lukket beslag, og du får nogle 2-dimensional struktur. Du kunne gennemføre en 2-dimensional linkede liste hvis du gør add-som De foreslog-tredjedel pointer til hver af disse ting, og hvis du tænker over en anden liste, der kommer på dig 3D-stil fra skærmen for os alle, er der bare en anden kæde af en slags. Vi kunne gøre det, men det er ikke så simpelt som at skrive open beslag, firkantet beslag. Yeah. [Uhørlig student spørgsmål] Godt, så dette er en reel kicker. 

Disse algoritmer, som vi har pined over, ligesom oh, binær søgning, kan du søge en bred vifte af numre på tavlen eller en telefonbog så meget hurtigere, hvis du bruger del og hersk og en binær søgealgoritme, men binær søgning krævede to antagelser. En, at de data blev sorteret. Nu kan vi formentlig holde det sorteret, så måske det er ikke en bekymring, men binær søgning også antaget at du havde tilfældig adgang til listen over numre, og et array tillader dig at have random access, og ved random access, Jeg mener, hvis du er givet et array, hvor meget tid det tager dig at komme til beslaget 0? En operation, du bare bruge [0] og du er lige der. Hvor mange skridt tager det at komme til placering 10? Et skridt, du bare gå til [10], og du er der. Derimod, hvordan du kommer til det 10. tal i en sammenkædet liste? Du er nødt til at starte ved begyndelsen, fordi du kun huske begyndelsen af ​​en sammenkædet liste, ligesom en streng der huskes af adressen på sin første char, og opdage, at 10:e int eller at 10:e karakter i en streng, er du nødt til at søge på hele skidtet. 

Igen, vi ikke løse alle vores problemer. Vi introducerer nye, men det virkelig afhænger af, hvad du forsøger at designe for. Med hensyn til gennemførelsen af ​​denne, kan vi låne en ide fra, at studerende struktur. Syntaksen er meget ens, bortset nu, ideen er lidt mere abstrakt end hus og navn og ID. Men jeg foreslår, at vi kunne have en datastruktur i C der kaldes knude, som det sidste ord på objektglasset antyder, indersiden af ​​en node, en node og er blot en generisk beholder i datalogi. Det er normalt tegnes som en cirkel eller en firkant eller et rektangel, som vi har gjort. Og i denne datastruktur, har vi en int, n, så det er det nummer jeg ønsker at gemme. Men hvad er denne anden linje, struct node * næste? Hvorfor er dette korrekt, eller hvilken rolle denne ting play, selvom det er lidt kryptisk ved første øjekast? Yeah. [Uhørlig student svar] Præcis, så * slags krigsbytte, at det er en pointer af en slags. Navnet på denne pointer er vilkårligt næste, men vi kunne have kaldt det noget vi vil, men hvad betyder dette pointer peger på? [Student] En anden node. >> Præcis, det peger på en anden sådan node. 

Nu, dette er en slags nysgerrighed C. Minde om, at C læses af en compiler top til bund, venstre mod højre, hvilket betyder, hvis-dette er lidt anderledes end hvad vi gjorde med den studerende. Når vi defineret en elev, vi faktisk ikke sætte et ord der. Det sagde bare typedef. Derefter havde vi int id, string name, string hus, og derefter studerende ved bunden af ​​struct. Denne erklæring er lidt anderledes, fordi, igen, C compiler er lidt dum. Det er kun kommer til at læse top til bund, så hvis det når 2. linje her hvor næste er erklæret, og den ser, oh, her er en variabel kaldet næste. Det er en pointer til en struct node. Compileren vil indse, hvad der er en struct node? Jeg har aldrig hørt om denne ting før, da ordet node ellers ikke ville forekomme indtil bunden, der så er denne redundans. Du er nødt til at sige struct node her, som du derefter kan forkorte senere takket være typedef hernede, men det er fordi Vi refererer til selve strukturen inde i strukturen. Det er den ene gotcha der. 

Nogle interessante problemer vil opstå. Vi har en liste over numre. Hvordan kan vi indsætte i det? Hvordan kan vi søge i den? Hvordan sletter vi ud af det? Især nu, hvor vi er nødt til at styre alle disse pejlemærker. Du troede pointers var slags hjernevridende når du havde en af ​​dem prøver bare at læse en int til det. Nu har vi at manipulere en hel liste værd. Hvorfor tager vi ikke vores 5-minutters pause her, og så vil vi bringe nogle folk op på scenen for at gøre netop dette. 

C er meget sjovere, når det er handlet ud. Hvem ville bogstaveligt gerne være først? Okay, kom op. Du er først. Hvem vil gerne være 9? Okay, 9. Hvordan omkring 9? 17? En lille klike her. 22 og 26 i det forreste række. Og så hvad med nogen derovre bliver peget på. Du er 34. Okay, 34, kom op. Først er derovre. Okay, alle fire af jer. Og hvem har vi sige 9? Hvem er vores 9? Der virkelig ønsker at være 9? Okay, kom nu, være 9. Her går vi. 34, vi mødes dig derovre. Den første del er at gøre jer selv se ud. 26, 22, 17, godt. Hvis du kan stå ud til siden, fordi vi vil allokere dig et øjeblik. 

Godt, godt. Okay, fremragende, så lad os stille et par spørgsmål her. Og faktisk, hvad er dit navn? >> Anita. Anita, okay, kom herover. Anita vil hjælpe os slags løse en forholdsvis enkel spørgsmål først, hvilket er hvordan kan du finde hvorvidt en værdi er på listen? Nu, bemærke, at det første, her repræsenteret ved Lucas, er lidt anderledes, og så hans stykke papir er bevidst sidelæns fordi det ikke er helt så høj og ikke optager så mange bits, skønt teknisk set har han samme størrelse papir bare roteret. Men han er lidt anderledes, idet han er kun 32 bit for en pegepind, og alle disse fyre er 64 bits, hvoraf halvdelen er antallet, hvoraf halvdelen er en pegepind. Men markøren er ikke afbildet, så hvis du fyre kunne lidt akavet bruge din venstre hånd til at pege på personen ved siden af ​​dig. Og du er nummer 34. Hvad er dit navn? Ari. Ari, så faktisk, skal du holde papiret i din højre hånd, og venstre hånd går lige ned. Du repræsenterer null til venstre. 

Nu er vores menneskelige billede er meget konsekvent. Dette er faktisk hvordan pegepinde fungerer. Og hvis du kan kradser en lille smule denne måde, så jeg ikke er i vejen. Anita her, finde mig nummeret 22, men antager en begrænsning af ikke mennesker holder op stykker papir, men dette er en liste, og du kun har Lucas til at begynde med fordi han er bogstaveligt talt den første pointer. Antag, at du selv er en pegepind, og så du også har mulighed for at pege på noget. Hvorfor starter du ikke ved at pege på præcis, hvad Lucas peger på? Godt, og lad mig vedtage denne ud herovre. Bare for af hensyn til diskussion, lad mig hente en blank side her. Hvordan staver du dit navn? >> Anita. Okay, Anita. Lad os sige node * anita = lucas. Nå, skal vi ikke kalde dig lucas. Vi bør kalde dig først. Hvorfor er dette faktisk er i overensstemmelse med virkeligheden her? En første findes allerede. Først har fået tildelt formentlig et eller andet sted her. Node * først, og det er blevet tildelt en liste eller anden måde. Jeg ved ikke, hvordan det skete. Det skete før klassen startede. Denne linkede liste af mennesker er blevet oprettet. Og nu på dette tidspunkt i historien, det er alle går på Facebook tilsyneladende senere- på dette tidspunkt i historien, er Anita blevet initialiseret at være lig med det første, hvilket ikke betyder, at Anita peger på Lucas. Snarere peger hun på, hvad han peger på fordi den samme adresse, som er inde i Lucas '32 bits - 1, 2, 3 - er nu også inde i Anitas 32 bits - 1, 2, 3. 

Nu skal du finde 22. Hvordan ville du gå om at gøre dette? Hvad er det? >> Point til hvad som helst. Peg på hvad, så gå videre og handle det ud så godt du kan her. Godt, godt, og nu er du peger på-hvad er dit navn med 22? Ramon. >> Ramon, så Ramon holder op 22. Du har nu gjort en check. Er Ramon == 22, og i bekræftende fald, for eksempel, kan vi returnere sandt. Lad mig mens disse fyre står her lidt akavet- lad mig gøre noget hurtigt som bool finde. Jeg har tænkt mig at gå videre og sige (node ​​* liste, int n). Jeg er straks tilbage med jer. Jeg behøver bare at skrive noget kode. Og nu jeg har tænkt mig at gå videre og gøre det, node * anita = liste. Og jeg har tænkt mig at gå videre og sige while (anita! = NULL). 

Metaforen her er at få lidt strakt, men while (anita! = NULL), hvad jeg ønsker at gøre? Jeg har brug for en måde at referere heltallet at Anita peger på. Før i tiden, når vi havde strukturer, som et knudepunkt er vi brugte dot-notationen, og vi ville sige noget anita.n, men problemet her er, at Anita ikke er en struct per se. Hvad er hun? Hun er en pegepind, så virkelig, hvis vi ønsker at bruge denne dot notation- og dette kommer til at se bevidst lidt kryptisk- vi er nødt til at gøre noget lignende gå til, hvad Anita venstre hånd peger på og derefter få feltet kaldet n. Anita er en pegepind, men hvad er * anita? Hvad synes du, når du går til, hvad Anita peger på? En struct, en knude, og en node, tilbagekaldelse, har et felt kaldet n fordi det har, husker, disse 2 felter, næste og n, at vi så et øjeblik siden lige her. 

For rent faktisk at efterligne dette i kode, vi kunne gøre dette og sige, hvis ((* anita). n == n), n som jeg leder efter. Bemærk, at funktionen blev vedtaget i antallet jeg ligeglad. Så jeg kan gå videre og gøre noget lignende gengæld sandt. Else, hvis det ikke er tilfældet, hvad jeg ønsker at gøre? Hvordan kan jeg oversætte til kode, hvad Anita gjorde det intuitivt ved at gå gennem listen? Hvad skal jeg gøre op her for at simulere Anita tage dette skridt til venstre, at trin til venstre? [Uhørlig student svar] >> Hvad er det? [Uhørlig student svar] Godt, ikke en dårlig idé, men i fortiden, når vi har gjort dette, har vi gjort anita + + fordi det ville tilføje nummeret 1 til Anita, som typisk vil pege på den næste person, som Ramon, eller personen ved siden af ​​ham, eller den ved siden af ​​ham person ned linjen. Men det er ikke helt godt her, fordi hvad betyder denne ting se ud i hukommelsen? Ikke det. Vi er nødt til at deaktivere dette. Det ser sådan ud i hukommelsen, og selvom jeg har uafgjort 1 og 2 og 3 tæt på hinanden, hvis vi virkelig simulere dette-kan du fyre, mens den stadig peger på de samme mennesker, kan nogle af jer tager en tilfældig skridt tilbage, nogle af jer en tilfældig skridt fremad? 

Dette rod er stadig en sammenkædet liste, men disse fyre kunne være overalt i hukommelsen, så anita + + kommer ikke til at virke hvorfor? Hvad er på stedet anita + +? Hvem ved. Det er en anden værdi, der bare så sker for at være indskudt blandt alle disse knudepunkter ved chance, fordi vi ikke bruger en array. Vi anvendes til hvert af disse knudepunkter individuelt. Okay, hvis du fyre kan rense jer op igen. Lad mig foreslå, at i stedet for anita + +, vi i stedet gøre anita får- godt, hvorfor vi ikke gå til, hvad Anita peger på, og derefter gøre. næste? Med andre ord går vi til Ramon, hvem der holder nummer 22, og derefter. næste er som om Anita ville kopiere hans venstre hånd pointer. Men hun ville ikke gå længere end Ramon, fordi vi fandt 22. Men det ville være den idé. Nu, dette er en gud-frygtelig rod. Helt ærligt, vil ingen nogensinde huske denne syntaks, og så heldigvis, det er faktisk lidt bevidst-oh, har du faktisk ikke se, hvad jeg skrev. Det ville være mere overbevisende, hvis du kunne. Voila! 

Bag kulisserne, var jeg løse problemet på denne måde. Anita, at tage dette skridt til venstre, først, går vi hen til den adresse, Anita peger på og hvor hun vil finde ikke blot n, som vi lige tjekket for sammenligning skyld, men du vil også finde næste - i dette tilfælde, Ramon venstre hånd peger på den næste node i listen. Men dette er den gud-frygtelige rod som jeg henviste til tidligere, men det viser sig C lader os forenkle dette. I stedet for at skrive (* anita), kan vi i stedet bare skrive anita-> n, og det er præcis de samme ting funktionelt, men det er meget mere intuitiv, og det er meget mere i overensstemmelse med det billede, vi har tegning al denne tid ved hjælp af pile. 

Endelig, hvad vi skal gøre ved afslutningen af ​​dette program? Der er én linje kode tilbage. Retur hvad? Falsk, for hvis vi kommer igennem det hele, mens løkken og Anita er i virkeligheden, null der betyder, at hun gik hele vejen til slutningen af ​​listen hvor hun peger på, hvad er dit navn igen? Ari. >> Ari venstre hånd, som er null. Anita er nu null, og jeg er klar over at du bare stående her akavet i limbo fordi jeg har tænkt mig ud på en monolog her, men vi vil involvere dig igen om et øjeblik. Anita er null på det tidspunkt i historien, så while-løkken slutter, og vi er nødt til at returnere falsk, fordi hvis hun fik hele vejen til Aris nulhenvisning så var der ingen tal, at hun søgte på listen. Vi kan rydde op også, men det er en temmelig god gennemførelse og derefter af en traversal funktion, finde en funktion til en linket liste. Det er stadig lineær søgning, men det er ikke så simpelt som + + en pointer eller + + en i variabel, fordi nu kan vi ikke gætte hvor hvert af disse knudepunkter er i hukommelsen. Vi er nødt til bogstaveligt følge sporet af rasp eller, mere specifikt, pegepinde, at komme fra én node til en anden. 

Lad os prøve en anden. Anita, vil du komme tilbage her? Skal vi ikke gå videre og tildele en anden person fra publikum? Malloc-hvad er dit navn? >> Rebecca. Rebecca. Rebecca er blevet malloced fra publikum, og hun er nu lagring af antallet 55. Og målet ved hånden nu, er for Anita at indsætte Rebecca ind i den linkede liste her i sin passende sted. Kom herover et øjeblik. Jeg har gjort noget som dette. Jeg har gjort node *. Og hvad er dit navn igen? Rebecca. >> Rebecca, okay. Rebecca får malloc (sizeof (node)). Ligesom vi har tildelt ting som studerende og whatnot i fortiden, vi har brug for størrelsen af ​​den knude, så nu Rebecca peger på, hvad? Rebecca har to felter inde i hende, hvoraf den ene er 55. Lad os gøre hvad, rebecca-> = 55. Men så rebecca-> næste skal-lignende lige nu, hendes hånd er lidt hvem ved? Det peger på nogle garbage værdi, så hvorfor ikke for god foranstaltning vi i det mindste gøre dette, således at venstre hånd er nu ved hendes side. Nu Anita, tager den herfra. Du har Rebecca har fået tildelt. Gå videre og find hvor vi skal sætte Rebecca. Godt, meget godt. Okay, godt, og nu har vi brug for dig til at give lidt af retning, så du har nået Ari. Hans venstre hånd er nul, men Rebecca klart hører til højre, så hvordan skal vi ændre denne linkede liste med henblik på at indsætte Rebecca på det rette sted? Hvis du bogstaveligt talt kan flytte folks venstre hånd rundt efter behov, vi vil løse problemet på den måde. Okay, godt, og i mellemtiden, Rebecca venstre hånd er nu ved hendes side. 

Det var alt for let. Lad os prøve at tildele-Vi næsten færdig, 20. Okay, kom op. 20 er blevet tildelt, så lad mig gå videre og sige igen her vi lige har gjort node * Saad. Vi har malloc (sizeof (node)). Vi derefter gøre det samme nøjagtige syntaks, som vi gjorde før i 20, og jeg vil gøre næste = NULL, og nu er det op til Anita at indsætte dig ind i den linkede liste, hvis du kunne spille det nøjagtig samme rolle. Udfør. Okay, godt. Nu tænke grundigt, før du begynder at flytte venstre hånd rundt. Du ved langt fik mest akavet rolle i dag. Hvis hånd skal flyttes først? Okay, vent, jeg hører nogle nej'er. Hvis nogle folk høfligt gerne vil bidrage til at løse en akavet situation her. Hvis venstre hånd bør ajourføres 1:e måske? Yeah. [Student] Saad er. Okay, Saad er, hvorfor dog? [Uhørlig student svar] Godt, for hvis vi flytter-hvad er dit navn? >> Marshall. Marshall, hvis vi flytter sin hånd først ned til nul, nu har vi bogstaveligt talt forældreløse fire mennesker i denne liste fordi han var den eneste, der peger på Ramon og alle til venstre, så opdatere denne pegepind første var dårlig. Lad os fortryde det. Godt, og nu gå videre og flytte den relevante venstre hånd peger på Ramon. Det føles lidt overflødige. Nu er der to mennesker peger på Ramon, men det er fint fordi nu hvor vi ellers opdatere listen? Hvad derimod er nødt til at flytte? Fremragende, nu har vi mistet enhver hukommelse? Nej, så godt, lad os se om vi ikke kan bryde denne gang mere. 

Mallocing en sidste gang, nummer 5. Hele vejen i ryggen, kom nu ned. Det er meget spændende. [Bifald] Hvad er dit navn? >> Ron. Ron, okay, er du malloced som nummer 5. Vi har netop gennemført kode, der er næsten identisk med disse med blot et andet navn. Excellent. Nu, Anita, held og lykke indsætte nummer 5 på listen nu. Godt, og? Fremragende, så er dette virkelig den tredje af tre samlede sager. Vi havde først en person i slutningen, Rebecca. Vi havde derefter en person i midten. Nu har vi en person i starten, og i dette eksempel, vi nu nødt til at opdatere Lucas for første gang fordi det første element i listen nu skal pege på en ny knude, der til gengæld peger bliver ved knudepunktet nummer 9. 

Det var en enormt akavet demonstration, jeg er sikker på, så en stor runde af bifald for disse fyre, hvis du kunne. Pænt gjort. Det er alt. Du kan holde dine stykker papir som en lille hukommelse. Det viser sig, at gøre dette i kode er ikke helt så simpelt som bare at flytte hænderne rundt og peger pointere til forskellige ting. Men indse, at når det drejer sig tid til at gennemføre noget lignende en sammenkædet liste eller en variant af det, hvis du fokuserer på virkelig disse grundlæggende fundamentals, de mundrette problemer, jeg har at regne ud, er det denne hånd eller denne hånd, indse, at hvad er ellers en ret kompleks program kan faktisk blive nedsat til enkle byggeklodser som denne. 

Lad os tage tingene i en mere sofistikeret retning endnu. Vi har nu begrebet den linkede liste. Vi har også-tak til forslaget tilbage der-en dobbelt linket liste, som ser næsten det samme, men nu har vi to pointere indersiden af ​​struct i stedet for én, og vi kunne nok kalde disse pointers forrige og næste eller til venstre eller højre, men vi har i virkeligheden brug for to af dem. Koden ville være lidt mere involveret. Anita ville have haft at gøre mere arbejde her på scenen. Men vi kan helt sikkert gennemføre denne form for struktur. Med hensyn til køretid, selv om hvad der ville være køretiden for Anita at finde et nummer n i en sammenkædet liste nu? Stadig stor O i n, så det er ikke bedre end lineær søgning. Vi kan ikke gøre binær søgning, men, igen. Hvorfor var det sådan? Du kan ikke springe rundt. Selvom vi naturligvis se alle mennesker på scenen, og Anita kunne have eyeballed det og sagde: "Her er midt på listen," hun ville ikke vide, at hvis hun var computerprogrammet fordi det eneste hun måtte hægte sig på ved starten af ​​scenariet var Lucas, der var den første pointer. Hun ville nødvendigvis nødt til at følge disse links, tælle hendes måde indtil hun fandt omtrent midten, og selv da, hun ikke kommer til at vide, hvornår hun har nået den midterste medmindre hun går hele vejen til enden for at finde ud af, hvor mange der er, derefter tilbagekalder, og det ville også være svært, medmindre du havde en dobbelt forbundet liste af en slags. 

Løse nogle problemer i dag, men indføre andre. Hvad med en anderledes datastruktur helt? Dette er et fotografi af bakkerne i Mather House, og i dette tilfælde har vi en datastruktur vi har også slags allerede talt om. Vi talte om en stak i forbindelse med hukommelse, og det er slags bevidst navn, fordi en stak i form af hukommelse er effektivt en datastruktur, der har flere og flere ting lag oven på den. Men det interessante ved en stak, som det er tilfældet i virkeligheden, er, at det er en særlig form for data struktur. Det er en datastruktur, hvor det første element i er det sidste element ud. Hvis du er den første bakke, der skal sættes på stakken, du vil være desværre den sidste bakke, der skal tages fra stakken, og det er ikke nødvendigvis en god ting. Omvendt kan du tænke over det den anden vej rundt, den sidste i den første ud. 

Nu behøver nogen scenarier kommer til at tænke hvor det at have en stak datastruktur, hvor du har denne ejendom af den sidste ind, først ud, er faktisk overbevisende? Er det en god ting? Er det en dårlig ting? Det er helt sikkert en dårlig ting, hvis bakkerne ikke var alle ens og de var alle særlige forskellige farver eller whatnot, og den farve, du ønsker, er helt i bunden. Selvfølgelig kan du ikke få det uden store anstrengelser. Du er nødt til at starte fra toppen og arbejde dig vej ned. Ligeledes, hvad nu hvis du var en af ​​disse fan drenge der venter oppe hele natten forsøger at få en iPhone og linjer op på et sted som dette? Ville det ikke være rart, hvis Apple Store var en stak datastruktur? Yay? Nay? Det er kun godt for de mennesker, der dukker op på den sidste mulige minut og derefter få plukkede køen. Og i virkeligheden, at det faktum, at jeg var så tilbøjelig sige kø er faktisk i overensstemmelse med, hvad vi ville kalde denne type datastruktur, en i virkeligheden, hvor ordren betyder noget, og du ønsker den første i at være den første ud hvis kun af hensyn til menneskelig retfærdighed. Vi vil generelt kalde det en kø datastruktur. 

Det viser sig, udover hægtede lister, kan vi begynde at bruge de samme grundlæggende ideer og begynde at skabe nye og anderledes typer af løsninger på problemerne. For eksempel i tilfælde af en stabel kunne vi repræsenterer en stak ved hjælp af en datastruktur som denne, ville jeg foreslå. I dette tilfælde har jeg erklæret en struct, og jeg har sagt inde i denne struktur er en matrix af tal og en variabel kaldet størrelse, og jeg vil kalde denne ting en stak. Nu, hvorfor dette rent faktisk arbejder? I tilfælde af en stak, jeg kunne trække dette effektivt på skærmen som en matrix. Her er min stak. Det er mine numre. Og vi vil drage dem som dette, dette, dette, dette, dette. Og så har jeg nogle andre data medlem her, som kaldes størrelse, så det er størrelse, og dette er tal, og kollektivt, hele iPad her repræsenterer en stak struktur. Nu, som standard, har størrelse formentlig nødt til at være initialiseret til 0, og hvad der er inde i den vifte af numre i første omgang når jeg først tildele et array? Garbage. Hvem ved? Og det gør faktisk ikke noget. Det betyder ikke noget, hvis det er 1, 2, 3, 4, 5, helt tilfældigt af uheld gemt i min struktur, fordi så længe jeg ved, at størrelsen af ​​stakken er 0, så ved jeg programmeringsmæssigt, ikke ser på nogle af de elementer i arrayet. Det er ligegyldigt, hvad der er. Må ikke se på dem, som ville være konsekvenserne af en størrelse på 0. 

Men sæt nu jeg gå videre og indsætte noget i stakken. Jeg ønsker at indsætte tallet 5, så jeg sætte nummer 5 her, og hvad så sætter jeg ned her? Nu vil jeg faktisk sat ned 1 for den størrelse, og nu stakken er af størrelse 1. Hvad hvis jeg gå videre og indsæt tal, lad os sige, 7 næste? Dette så bliver opdateret til 2, og så vil vi gøre 9, og derefter dette bliver opdateret til 3. Men det interessante træk nu af denne stak er, at Jeg skulle til at fjerne hvilket element, hvis jeg ønsker at pop noget ud af stakken, så at sige? 9 ville være den første ting at gå. Hvordan skal billedet ændre sig, hvis jeg ønsker at pop et element fra stakken, meget gerne en bakke i Mather? Ja. >> [Student] Indstil størrelse til 2. Præcis, er alt jeg gør sat størrelse til 2, og hvad skal jeg gøre med det array? Jeg behøver ikke at gøre noget. Jeg kunne, bare for at være anal, sætte et 0 der eller en -1 eller noget at betyde at dette ikke er en legit værdi, men det gør ikke noget, fordi Jeg kan optage uden for arrayet selv hvor længe det er så jeg kender kun se på de to første elementer i dette array. Nu, hvis jeg går og føje nummeret 8 til dette array, hvordan billedet ændrer næste? Dette bliver otte, og det bliver 3. Jeg skære et par hjørner her. Nu har vi 5, 7, 8, og vi er tilbage til en størrelse på 3. Det er ret enkel at implementere, men når vi kommer til at fortryde dette design beslutning? Hvornår tingene begynder at gå meget, meget galt? Yeah. [Uhørlig student svar] Når du ønsker at gå tilbage og få det første element, du lægger i. 

Det viser sig her, selvom en stak er et array under hætten, disse datastrukturer, vi har begyndt at tale om, er også almindeligt kendt som abstrakte datastrukturer, hvorved hvordan de er implementeret er helt ved siden af ​​punktet. En datastruktur som en stak formodes at tilføje understøttelse operationer som push, som skubber en bakke på stakken, og pop, som fjerner et element fra stakken, og det er det. Hvis du skulle hente en andens kode, der allerede er gennemført denne ting kaldet en stak, ville denne person have skrevet kun to funktioner for dig, skubbe og pop, hvis eneste formål i livet ville være at gøre netop dette. Du eller ham eller hende, der gennemføres dette program ville have været helt den ene til at beslutte, hvordan man gennemfører semantikken i at skubbe og knaldende under hætten eller funktionaliteten af ​​skubben og popping. Og jeg har lavet en noget kortsigtet beslutning her ved at gennemføre min stak med denne enkle datastruktur hvorfor? Hvornår gør dette datastruktur pause? På hvilket tidspunkt skal jeg returnere en fejl, når brugeren kalder push, for eksempel? [Student] Hvis der ikke er mere plads. Præcis, hvis der ikke er mere plads, hvis jeg har overskredet kapacitet, der er alle hætter, fordi det antyder, at det er en slags global konstant. Nå, så er jeg bare nødt til at sige, "Undskyld, jeg kan ikke skubbe en anden værdi på stakken, meget "gerne i Mather. 

På et tidspunkt, er de kommer til at ramme den øverste del af det lille kabinet. Der er ikke mere plads eller kapacitet i stakken, på hvilket tidspunkt der er en slags fejl. De skal sætte elementet et andet sted, bakken et andet sted, eller intetsteds overhovedet. Nu, med en kø, kan vi gennemføre det lidt anderledes. En kø er lidt anderledes, idet under hætten, kan det blive gennemført som en matrix, men hvorfor i dette tilfælde, foreslår jeg til også at have et hoved element, der udgøres hovedet af listen, den forreste del af listen, den første person i kø ved Apple Store, ud over størrelse? Hvorfor har jeg brug for en ekstra stykke data her? Tænk tilbage til, hvad numre er hvis jeg har tegnet det som følger. Formoder, det er nu en kø i stedet for en stak, idet forskellen er, ligesom Apple Store-kø er fair. Den første i overensstemmelse ved starten af ​​listen, nummer 5 i dette tilfælde, han eller hun vil blive lukket ind i butikken først. Lad os gøre det. Antag, at dette er den tilstand af min kø på dette tidspunkt, og nu Apple Store åbnes, og den første person, nr. 5, er ført ind i butikken. Hvordan ændrer jeg det billede, nu hvor jeg har afmeldt kø den første person foran linjen? Hvad er det? >> [Student] Skift køen. Skift hovedet, så 5 forsvinder. I virkeligheden er det som om, hvordan man bedst kan gøre dette? I virkeligheden er det som om denne fyr forsvinder. Hvad ville nummer 7 gøre i en egentlig butik? De ville tage et stort skridt fremad. 

Men hvad er vi kommet til at værdsætte, når det kommer til arrays og flytte tingene rundt? Det er lidt spild af din tid, ikke? Hvorfor skal du være så anal, at de har den første person ved begyndelsen af ​​linien ved fysisk begyndelsen af ​​bid af hukommelsen? Det er helt unødvendigt. Hvorfor? Hvad kunne jeg bare huske stedet? >> [Uhørlig student svar] Præcis, jeg kunne bare huske med denne yderligere data medlem hoved at nu hovedet af listen er ikke længere 0, som det var for et øjeblik siden. Nu er det faktisk nummer 1. På denne måde får I en lille optimering. Bare fordi jeg har afmeldt kø nogen fra linje i starten af ​​linien ved Apple Store betyder ikke alle har til at flytte, hvilket tilbagekaldelse er en lineær operation. Jeg kan i stedet bruge konstant tid kun og opnå derefter en langt hurtigere respons. Men prisen jeg betaler er hvad man skal opnå, at ekstra ydeevne og ikke at skulle flytte alle? Ja. >> [Uhørlig student svar] Kan tilføje flere mennesker, ja, det problem er ortogonale det faktum, at vi ikke flytte folk rundt. Det er stadig et array, så uanset om vi skifter alle eller ikke- Åh, jeg kan se hvad du mener, okay. Faktisk er jeg enig med hvad du siger i at det er næsten som om vi nu aldrig kommer til at bruge starten af ​​dette array længere fordi hvis jeg fjerner 5, så fjerner jeg 7. Men jeg kun sætte folk til højre. 

Det føles som om jeg spilder plads, og til sidst min kø opløses i ingenting, så vi kunne bare have folk wraparound, og vi kunne tænke på dette array virkelig som en slags cirkulær struktur, men vi bruger hvad operatør i C til at gøre den slags wraparound? [Uhørlig student svar] >> Modulo operatør. Det ville være lidt irriterende at tænke igennem hvordan gør du det wraparound, men vi kunne gøre det, og vi kunne begynde at sætte folk på, hvad der plejede at være foran i køen, men vi bare huske med denne hoved variabel som den egentlige leder af linjen faktisk er. Hvad hvis, i stedet, vores mål i sidste ende, selv om, var at søge efter numre, som vi gjorde her på scenen med Anita, men vi virkelig ønsker det bedste af alle disse verdener? Vi ønsker mere sofistikerede end matrix tillader fordi vi ønsker mulighed for dynamisk vokse datastrukturen. Men vi ønsker ikke at skulle ty til noget, som vi påpegede i den første forelæsning var ikke en optimal algoritme, den for lineær søgning. Det viser sig, at du kan faktisk opnå eller i det mindste tæt på konstant tid, hvorved en person som Anita, hvis hun konfigurerer sin datastruktur ikke at være en sammenkædet liste, ikke at være en stabel, for at være en kø, kunne i virkeligheden, komme med en datastruktur, der giver hende mulighed for at se op tingene, selv ord, ikke bare tal, i hvad vi kalder konstant tid. 

Og i virkeligheden, ser fremad, en af ​​de psets i denne klasse er næsten altid en implementering af en stavekontrol, hvorved giver vi dig igen omkring 150.000 engelske ord, og målet er at indlæse dem i hukommelsen og hurtigt være i stand til at besvare spørgsmål af formen er dette ord stavet korrekt? Og det ville virkelig suge hvis du skulle gentage gennem alle 150.000 ord at besvare dette. Men i virkeligheden, vil vi se, at vi kan gøre det i meget, meget hurtig tid. Og det kommer til at involvere gennemføre noget, der kaldes en hash tabel, og selvom ved første øjekast denne ting kaldet en hash tabel kommer til at Lad os med at nå disse super hurtige svartider, Det viser sig, at der faktisk et problem. Når det drejer sig tid til at gennemføre denne ting kaldet-igen, jeg gør det igen. Jeg er den eneste her. Når det drejer sig tid til at gennemføre denne ting kaldet en hash tabel, vi bliver nødt til at træffe en beslutning. Hvor stort skal det her egentlig være? Og når vi begynder at indsætte tal i denne hash tabel, hvordan skal vi opbevare dem på en sådan måde, at vi kan få dem ud igen så hurtigt som vi fik dem i? Men vi vil se inden længe at dette spørgsmål om når alles fødselsdag er i den klasse vil være ganske germane. Det viser sig, at der i dette rum, har vi fået et par hundrede mennesker, så oddsene, at to af os har samme fødselsdag er sandsynligvis temmelig højt. Hvad hvis der var kun 40 af os i dette rum? Hvad er odds for to personer med samme fødselsdag? [Studerende] Over 50%. Ja, mere end 50%. Faktisk har jeg selv bragte et diagram. Det viser sig, og det er egentlig bare en smagsprøve- hvis der er kun 58 af os i dette rum, at sandsynligheden for 2 af os har samme fødselsdag er enormt høj, næsten 100%, og det kommer til at forårsage en hel masse ondt for os på onsdag. 

Med det sagt, lad os udsætte her. Vi vil se dig på onsdag. [Bifald] [CS50.TV]