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

Dette er CS50, og dette er begynnelsen av uke 6, så et par nye verktøy er nå tilgjengelig for deg å dra nytte av, hvorav den første heter CS50 Style. Odds er hvis du er som meg eller noen av de pedagogiske fellows, du har sikkert sett et program der stilen ser litt noe sånt som dette. Kanskje du begynner å kutte noen hjørner sent på kvelden, eller du vil takle det senere, og deretter en TF eller CA kommer over i kontortiden. Da er det vanskelig for oss å lese. Vel, er denne koden syntaktisk korrekt, og det vil kompilere, og det vil faktisk kjøre. Men det er definitivt ikke en 5 for stil. 

Men nå, hvis vi går inn i denne katalogen her- og merker at jeg har conditions2.c- og jeg kjører denne nye kommandoen, style50, på denne filen conditions2.c, Enter, legge merke til at det er informert meg om at det har vært stilisert. Gedit merke til at filen er blitt endret på disk, og hvis jeg klikker laste, er alle dine problemer nå automatisert. [Applaus] Det er en av de tingene vi gjorde denne helgen. Innse at det er ufullkommen fordi det er noen kode at det ganske enkelt ikke vil være i stand til å stylize perfekt, men innser at dette er nå et verktøy du kan dra nytte av hvis bare å rydde opp noen av de mer errantly plassert klammeparentes og lignende. 

Men mer oppsiktsvekkende er nå CS50 Check. Med CS50 sjekk, kan du faktisk utføre de samme korrekthet tester på din egen kode som de pedagogiske stipendiatene er i stand til. Dette er et kommandolinjeverktøy som kommer nå i apparatet så snart du gjør en update50 som per pset 4 spesifikasjoner, og du bruker det i hovedsak som dette. Du kjører kommandoen check50. Så du passerer i en kommandolinje argument, eller mer generelt kjent som en bryter eller et flagg. Vanligvis er ting som har bindestrek kalles en switch til en kommandolinje program, spesifiserer så-c kontrollene som du ønsker å kjøre. 

De testene du vil kjøre identifiseres unikt ved denne strengen, 2012/pset4/resize. Med andre ord, det er bare en tilfeldig, men unike streng som vi bruker for å identifisere pset 4 er korrekthet tester. Og så du angir et mellomrom separert liste over filene du vil laste opp til CS50 Sjekk for analyse. For eksempel, hvis jeg går inn løsningen min her for resize.c- la meg åpne opp et større terminal vindu- og jeg går videre og kjøre la oss si check50-c 2012/pset4/resize, og da jeg går videre og angi navn på filene, resize.c, og trykk Enter, det komprimerer, han laster opp, sjekker det, og jeg bare ikke klarte en hel haug med tester. Den i rødt øverst til venstre sier at resize.c og bmp eksisterer. Som var testen. Det var spørsmålet vi spurte. Og det er ulykkelig fordi svaret var falsk. Den hvite teksten nedenfor står det forventes bmp.h å eksistere, og det er bare min feil. Jeg glemte å laste den opp, så jeg trenger å laste opp begge filene, resize.c og bmp.h. Men nå merke alle de andre testene er i gul fordi de ikke har kjørt, og så smilefjes er loddrett fordi han er verken glad eller trist, men vi må oppreisning at problemet i rødt før de andre kontroller vil kjøre. 

La meg fikse dette. La meg zoome ut og kjøre denne, denne gangen med bmp.h også på kommandolinjen, Enter, og nå hvis alt går bra, det kommer til å sjekke og deretter returnere et resultat av-hold pusten- alle grønne, som betyr at jeg gjør det veldig bra på pset 4 så langt. Du kan se og slutte fra den beskrivende teksten her nøyaktig hva det er vi testet. Vi testet først gjøre filene eksisterer? Vi testet gjør resize.c kompilere? Da vi testet den ikke endre størrelsen på et 1x1-pixel BMP når n, endre størrelse faktor, er en. Nå, hvis du ikke har noen anelse om hva n er, vil du når du dykke inn pset 4, men det er rett og slett en mental helse sjekk for å være sikker på at du ikke er resizing et bilde i det hele tatt hvis resize faktoren er en. Hvis derimot, endrer det en 1x1 pixel til en 1x1 piksel BMP til 2x2 riktig når n er 2, da tilsvarende danner gruven tilsvarende. 

Kort sagt, er dette ment å, en, ta krysset fingrene ut av ligningen rett før du sender inn pset. Vil du vite nøyaktig hva TF vil snart vite når du går om å sende inn noen av disse oppgavesett, og også den pedagogiske motivasjonen er virkelig å sette muligheten foran deg, slik at når du vet a priori at det er feil i koden din og tester som ikke blir bestått, du kan putte i mer effektiv tid foran for å løse disse problemene snarere enn å miste poeng, få tilbakemeldinger fra TF din, og deretter gå, "Ahh," som jeg skulle ha funnet det ut. Nå minst er det et verktøy som hjelper deg med å finne det. Det er ikke til å påpeke hvor feilen er, men det vil fortelle deg hva er symptomatisk for den. 

Nå innser testene er ikke nødvendigvis uttømmende. Bare fordi du får en skjerm full av grønne smilefjes betyr ikke det at koden er perfekt, men det betyr at det har gått visse tester foreskrevet av spec. Noen ganger er vi ikke slipper sjekker. For eksempel, whodunit, en av de aspektene av pset 4, er litt skuffende hvis vi gir deg svaret på hva det er, og det er en rekke måter å avsløre hvem personen er i det røde støy. Spec vil alltid spesifisere i fremtiden for pset 5 videre hva sjekker finnes for deg. Du vil merke det er denne hvite nettadressen nederst. For nå, dette er bare diagnostisk utgang. Hvis du besøker denne webadressen, vil du få en hel haug med gale, kryptiske meldinger at du er velkommen til å se gjennom, men det er mest for de ansatte slik at vi kan diagnostisere og feilsøke bugs i check50 selv. 

Uten ado, la oss gå videre til der vi slapp. CS50 bibliotek vi tok for gitt for noen uker, men deretter siste uke, startet vi peeling tilbake en av lagene i den. Vi begynte å sette til side streng i favør av hva stedet? [Studenter] Char. Char *, som har vært en char * all denne tiden, men nå har vi ikke trenger å late som det er en faktisk datatype streng. Snarere har det vært et synonym slags for char *, og en streng er en sekvens av tegn, så hvorfor gjør det fornuftig å representere strenger som char * s? Hva representerer en char * i sammenheng med dette konseptet av en streng? Ja. >> [Student] Det første tegnet. Bra, det første tegnet, men ikke helt det første tegnet. Det er de-[Studenter] Adresse. Bra, adressen til den første tegnet. Alt som er nødvendig for å representere en streng i datamaskinens minne er bare den unike adressen sin aller første byte. Du trenger ikke engang å vite hvor lenge det er fordi hvordan kan du finne det ut dynamisk? [Student] String lengde. Du kan ringe hyssinglengde, utmerket, men hvordan streng lengde arbeid? Hva gjør den? Ja. [Student] Fortsett til du får null karakter. Ja, akkurat, gjentar det bare med en for løkke, mens loop, uansett fra * til slutten, og slutten er representert av \ 0, den såkalte nul karakter, nul, ikke å forveksles med null, som er en peker, som vil komme opp i samtalen igjen i dag. 

Vi skrelles tilbake et lag av GetInt, og vi tok en titt på GetString, og huske at begge disse funksjonene, eller egentlig, GetString, var å bruke en bestemt funksjon å faktisk analysere, er at, lese eller analysere, brukerens input. Og hva var det ny funksjon? Scanf eller sscanf. Den kommer faktisk i et par forskjellige smaker. Det er scanf, det er sscanf, det er fscanf. For nå, men la oss fokusere på den ene lettest illustrert, og la meg gå videre og åpne opp i apparatet en fil som dette, scanf1.c. Dette er en super enkelt program, men som gjør noe som vi aldri har gjort uten hjelp av CS50 biblioteket. Dette får en int fra en bruker. Hvordan virker det? Vel, i linje 16 der, legge merke til at vi erklærer en int kalt x, og på dette punktet i historien, hva er verdien av x? [Uhørlig student respons] [David M.] Høyre, hvem vet, noen søppel verdi potensielt, så i 17, vi bare fortelle brukeren gi meg et nummer, takk, og trinn 18 er der det blir interessant. Scanf synes å låne en idé fra printf i at den bruker disse formatkoder i anførselstegn. % D er selvfølgelig et desimaltall. Men hvorfor jeg passerer og x i stedet for bare x? Den tidligere er riktig. Ja. [Uhørlig student respons] Akkurat, hvis målet med dette programmet, som funksjon GetInt selv, er å få en int fra brukeren jeg kan passere funksjoner alle variablene jeg vil, men hvis jeg ikke passere dem ved henvisning eller ved adresse eller etter pekeren, alle synonymt for dagens formål, da funksjonen har ingen mulighet til å endre innholdet i den variabelen. Dette ville passere en kopi akkurat som buggy versjonen av swap som vi har snakket om et par ganger nå. 

Men i stedet, ved å gjøre og x, jeg bokstavelig talt passerer i hva? [Student] Adressen. >> Adressen til x. Det er som å tegne et kart for funksjonen kalles scanf og sier her, disse er veibeskrivelse til en del av minnet i datamaskinen at du kan gå lagre noe heltall i. For at sscanf å nå gjøre det hva operatør, er hva stykke syntaks det nødt til å bruke selv om vi ikke kan se det fordi noen andre skrev denne funksjonen? Med andre ord - hva er det? [Student] X lest. Det kommer til å bli litt lesing, men bare med hensyn til x her. Hvis scanf blir passert adressen x, syntaktisk, hva operatøren bundet til å eksistere et sted innsiden av scanf implementering slik at scanf kan faktisk skrive en nummer 2 til denne adressen? Ja, så *. Husker at den * er vår dereferanse operatør, noe som betyr gå dit. 

Når du har blitt overlevert en adresse, slik tilfellet er her, scanf er trolig-hvis vi faktisk sett rundt sin kildekode- gjør * x eller tilsvarende til å faktisk gå til denne adressen og sette noen verdi der. Nå, som for hvordan scanf får inndata fra tastatur, vi vil bølge våre hender ut for i dag. Bare anta at operativsystemet lar sscanf å snakke til brukerens tastaturet, men på dette punktet nå i linje 19, når vi bare skrive ut x, synes det å være tilfelle at scanf har satt en int i x. Det er nøyaktig hvordan scanf fungerer, og husker forrige uke det er akkurat hvordan GetString og GetInt og andre familie av funksjoner slutt fungerer, om enn med litt variasjon som sscanf, som betyr skanne en streng i stedet for tastaturet. Men la oss ta en titt på en liten varians dette. I scanf2 jeg faktisk skrudd opp. Hva er galt og jeg vil skjule kommentar som forklarer så mye hva er galt med dette programmet, versjon 2? Vær så teknisk som mulig denne gangen. Det ser ganske bra. Det er pent innrykket, men- okay, hva med la oss beskjære det ned til kortere spørsmål? Linje 16. Hva er linje 16 gjør i presis, men teknisk engelsk? Får en litt klosset. Ja, Michael. [Student] Det er peker til den første bokstaven i en streng. 

Ok, nær. La meg tweak som en liten bit. Peker til den første bokstaven i en streng, er du erklære en variabel kalt buffer som vil peke til den første adressen til en streng, eller rettere sagt, vil det peke mer spesifikt til en røye. Legg merke til det er faktisk ikke peker noe sted fordi det er ingen oppdrag operatør. Det er ingen likhetstegn, så alt vi gjør er å fordele variabel kalt buffer. Det skjer for å være 32 bits fordi det er en peker, og innholdet av buffer formodentlig slutt vil inneholde adressen til en røye, men for nå, hva buffer inneholde? Bare noen falsk, hvem vet, noen søppel verdi, fordi vi ikke har eksplisitt initialisert den, så vi skal ikke anta noe. Ok, så nå linje 17 er-hva linje 17 gjøre? Kanskje som vil varme opp dette. Det skriver en streng, ikke sant? Det skriver String please. 

Linje 18 er slags kjent nå i at vi bare så en variasjon av dette men med et annet format kode, så i linje 18, vi forteller scanf her er adressen til en del av minnet. Jeg vil at du skal ringe i en streng, som underforstått av% s, men problemet er at vi ikke har gjort et par ting her. Hva er ett av problemene? [Student] Det prøver å dereference en nullpeker. God, null eller bare ellers ukjent pekere. Du overlate scanf en adresse, men du sa for et øyeblikk siden at den adressen er noen søppel verdi fordi vi ikke egentlig tilordne den til noe, og så forteller du scanf effektivt gå sette en streng her, men vi vet ikke hvor her ennå er, så vi har faktisk ikke allokert minne for buffer. Dessuten, hva er du heller ikke selv forteller scanf? Antar at dette var en del av minnet, og det var ikke en søppel verdi, men du fortsatt ikke fortelle scanf noe viktig. [Student] Hvor det faktisk er, tegnet. -Tegn, så i dette tilfellet, er det greit. Fordi bufferen er allerede erklært som en peker med * stykke syntaks, trenger vi ikke å bruke ampersand fordi det er allerede en adresse, men jeg tror jeg hørte det her. [Student] Hvor stort er det? Bra, vi ikke fortelle scanf hvor stor denne bufferen er, noe som betyr at selv om buffer var en peker, vi sier scanf, sette en streng her, men her kan være to bytes, kan det være 10 bytes, kan det være en megabyte. Scanf har ingen anelse, og fordi dette er en del av minnet formodentlig, det er ikke en streng ennå. Det er bare en streng når du skriver tegn og et \ 0 til at del av minnet. Nå er det bare noen del av minnet. Scanf vil ikke vite når du skal slutte å skrive til denne adressen. 

Hvis du husker noen eksempler i det siste hvor jeg tilfeldig skrevet på tastaturet prøver å overflow en buffer, og vi snakket på fredag ​​om akkurat det. Hvis en motstander injiserer liksom inn i programmet en mye større ord eller setningsoppbygning så du ventet du kan overkjørt en del av minne, som kan ha dårlige konsekvenser, som å ta over hele programmet selv. Vi trenger å fikse dette liksom. La meg zoome ut og gå inn versjon 3 av dette programmet. Det er litt bedre. I denne versjonen, merke forskjellen. I linje 16, jeg igjen erklære en variabel kalt buffer, men hva er det nå? Det er en rekke av 16 tegn. Dette er bra fordi dette betyr at jeg nå kan fortelle scanf her er en faktisk del av minnet. Du kan nesten tenke på arrays som pekere nå, selv om de er faktisk ikke tilsvarende. De vil oppføre seg forskjellig i ulike sammenhenger. Men det er sikkert slik at bufferen refererer 16 sammenhengende tegn fordi det er hva en matrise er og har vært i noen uker nå. 

Her forteller jeg scanf her er en del av minnet. Denne gangen er det faktisk en del av minnet, men hvorfor er dette programmet fortsatt utnyttes? Hva er galt likevel? Jeg har sagt gi meg 16 bytes, men- [Student] Hva om de skriver i mer enn 16 år? Akkurat, hva om brukeren skriver i 17 tegn eller 1700 tegn? Faktisk, la oss se om vi ikke kan snuble i denne feilen nå. Det er bedre, men ikke perfekt. La meg gå videre og kjør make scanf3 å kompilere dette programmet. La meg kjøre scanf3, String takk: Hei, og vi synes å være i orden. La meg prøve en litt lengre, hello there. Ok, la oss gjøre hello there hvordan er du i dag, Enter. Komme slags heldige her, la oss si hello there hvordan du er. Pokker. Ok, så vi hadde flaks. La oss se om vi ikke kan fikse dette. Nei, det er ikke til å la meg kopiere. La oss prøve dette igjen. Greit, stå ved. Vi får se hvor lenge jeg kan late til å fokusere mens du fremdeles gjør dette. Pokker. Det er heller hensiktsmessig, faktisk. Det vi går. Punktet laget. 

Dette, pinlig selv om det også er, er det også en av kildene til stor forvirring når du skriver programmer som har feil fordi de manifesterer seg bare én gang på en stund noen ganger. Realiteten er at selv om koden er fullstendig ødelagt, det kan bare være helt brutt gang på en stund fordi noen ganger, i hovedsak hva som skjer er operativsystemet tildeler litt mer minne enn du faktisk trenger uansett grunn, og slik at ingen andre bruker minnet rett etter at del av 16 tegn, så hvis du går til 17, 18, 19, uansett, det er ikke en så stor avtale. Nå, datamaskinen, selv om det ikke krasjer på det tidspunktet, kan til slutt bruke byte nummer 17 eller 18 eller 19 for noe annet, noe som medførte dine data som du setter der, om enn svært lange, kommer til å bli overskrevet potensielt av en annen funksjon. Det er ikke nødvendigvis kommer til å forbli intakt, men det vil ikke nødvendigvis føre til en SEG feil. Men i dette tilfellet, jeg endelig gitt nok tegn at jeg egentlig overskredet min del av minnet, og bam, operativsystemet sa: "Beklager, det er ikke bra, segmentering feil." 

Og la oss se nå om det fortsatt her i min katalog- merker at jeg har denne filen her, kjerne. Legg merke til at dette er igjen kalt en kjerne dump. Det er egentlig en fil som inneholder innholdet i programmet minne på det punktet der det krasjet, og bare for å prøve et lite eksempel her la meg gå inn her og kjøre gdb på scanf3 og deretter angi en tredje argumentet kalles kjernen, og legge merke til her at hvis jeg liste koden, vi vil være i stand som vanlig med gdb å begynne å gå gjennom dette programmet, og jeg kan kjøre den, og så snart jeg hit-som med trinn-kommandoen i gdb- så snart jeg traff potensielt buggy linje etter å skrive i en stor streng, Jeg vil være i stand til å faktisk identifisere det her. Mer om dette, men i snitt i form av kjernen dumper og lignende, slik at du faktisk kan rote rundt inne i kjernen dump og se på hvilken linje programmet sviktet deg. Eventuelle spørsmål deretter på pekere og adresser? Fordi i dag igjen, vi kommer til å begynne å ta for gitt at disse tingene eksisterer og vi vet nøyaktig hva de er. Ja. 

[Student] Hvordan kommer du ikke trenger å sette en ampersand ved siden av del- Godt spørsmål. Hvordan kommer jeg ikke måtte sette en ampersand ved siden av tegn array som jeg gjorde tidligere med de fleste av våre eksempler? Det korte svaret er arrays er litt spesiell. Du kan nesten tenke en buffer som faktisk er en adresse, og det bare så skjer for å være tilfelle at hakeparentes notasjon er en praktisk, slik at vi kan gå inn 0 brakett, brakett 1, 2 brakett, uten å måtte bruke * notasjon. Det er litt av en hvit løgn, fordi arrays og pekere er faktisk litt annerledes, men de kan ofte, men ikke alltid brukes om hverandre. Kort sagt, når en funksjon er ventet en peker til en del av minnet, du kan enten sende det en adresse som ble returnert av malloc, og vi vil se malloc igjen før lenge, eller du kan sende det navnet på en matrise. Du trenger ikke å gjøre ampersand med matriser fordi de allerede er hovedsak liker adresser. Det er ett unntak. Klammeparentesene gjør dem spesielle. 

Kan du sette en ampersand ved siden av buffer? Ikke i dette tilfellet. Det ville ikke fungere fordi, igjen, av denne hjørne saken hvor arrays er ikke helt faktisk adresser. Men vi vil kanskje komme tilbake til før lenge med andre eksempler. La oss prøve å løse et problem her. Vi har en datastruktur som vi har brukt på en stund kjent som en matrise. Case in point, det er det vi nettopp hadde. Men arrays har noen oppsider og ulemper. Arrays er fine hvorfor? Hva er en ting som du liker til den grad du liker arrays-om arrays? Hva er praktisk om dem? Hva er attraktiv? Hvorfor gjorde vi introdusere dem i første omgang? Ja. [Student] De kan lagre mye data, og du trenger ikke å bruke en hel ting. Du kan bruke en del. Bra, med en rekke du kan lagre mye data, og du trenger ikke nødvendigvis å bruke alt sammen, slik at du kan overallocate, som kan være praktisk hvis du ikke vet på forhånd hvor mange av noe du kan forvente. 

GetString er et perfekt eksempel. GetString, skrevet av oss, har ingen anelse om hvor mange tegn du kan forvente, så det faktum at vi kan fordele biter av sammenhengende minne er bra. Arrays også løse et problem vi så et par uker siden nå hvor koden begynner å devolve til noe svært dårlig utformet. Husker at jeg opprettet en student struktur kalt David, og da det var faktisk et alternativ, skjønt, til å ha en variabel kalt navn og en annen variabel kalt, tror jeg, huset, og en annen variabel kalt ID fordi i den historien da jeg ønsket å introdusere noe annet liker Rob inn i programmet, så da bestemte jeg meg vente et øyeblikk, Jeg trenger å endre navn på disse variablene. La oss kalle meg navn1, ID1, House1. La oss kalle Rob navn2, house2, ID2. Men så vent litt, hva om Tommy? Da hadde vi tre variabler. Vi introduserte noen andre, fire sett med variabler. Verden begynte å bli rotete svært raskt, så vi introduserte structs, og hva som er overbevisende om en struct? Hva lar en C struct du gjøre? Det er virkelig pinlig i dag. Hva? >> [Uhørlig student respons] Ja, spesielt, kan typedef du opprette en ny datatype, og struct, struct søkeord, kan du kapsle konseptuelt knyttet biter av data sammen og deretter ringe dem noe sånt som en student. 

Det var bra fordi vi nå kan modellere mye mer slags begrepsmessig konsekvent begrepet om en student i en variabel snarere enn å ha en vilkårlig for en streng, en for en ID, og ​​så videre. Arrays er fint fordi de tillater oss å begynne å rydde opp vår kode. Men hva er en ulemper nå av en array? Hva kan du ikke gjøre? Ja. [Student] Du må vite hvor stort det er. Du må vite hvor stort det er, så det er litt vondt. De av dere med tidligere erfaring med programmering vet at i en rekke språk, som Java, kan du be en del av minnet, spesielt en matrise, hvor stor du er, med en lengde, eiendom, så å si, og det er veldig praktisk. I C, kan du ikke engang kalle strlen på en generisk utvalg fordi strlen, som ordet antyder, er bare for strykere, og du kan finne ut lengden på en streng på grunn av denne menneskelige konvensjonen av å ha en \ 0, men en rekke, mer generelt, er bare en del av minnet. Hvis det er en rekke ints, er det ikke kommer til å være noen spesiell karakter på slutten venter på deg. Du må huske lengden på en matrise. En annen ulemper av en rekke reared hodet i GetString seg selv. Hva er en annen ulempe i en matrise? Sir, bare du og meg i dag. [Uhørlig student respons] >> Det er hva? Det er erklært på stakken. Ok, erklærte på stakken. Hvorfor liker du ikke det? [Student] Fordi det blir gjenbrukt. Det blir gjenbrukt. Ok, hvis du bruker en matrise for å allokere minne, du kan ikke for eksempel returnere det fordi det er på stakken. Ok, det er en ulempe. Og hva med en annen med en rekke? Når du tildeler det, er du slags skrudd hvis du trenger mer plass enn denne matrisen har. 

Da vi introduserte, tilbakekalling, malloc, som ga oss muligheten til å dynamisk allokere minne. Men hva om vi prøvde en annen verden helt? Hva hvis vi ønsket å løse et par av disse problemene så vi i stedet-min penn har sovnet her- hva om vi i stedet ønsket å hovedsak skape en verden som ikke lenger som dette? Dette er en matrise, og, selvfølgelig, forringes denne typen når vi treffer enden av matrisen, og jeg nå ikke lenger har plass til et annet heltall eller en annen karakter. Hva om vi liksom preemptively si vel, hvorfor ikke vi slappe dette kravet at alle disse biter av minnet være sammenhengende rygg mot rygg, og hvorfor ikke, når jeg trenger en int eller røye, bare gi meg plass til en av dem? Og når jeg trenger en annen, gi meg en annen plass, og når jeg trenger en annen, gi meg en annen plass. Fordelen som er nå at hvis noen andre tar minnet over her, ikke så farlig. Jeg tar denne ekstra mengde minne her og deretter denne. 

Nå er den eneste fangsten her at dette nesten føles som om jeg har en hel haug med forskjellige variabler. Dette føles som fem ulike variabler potensielt. Men hva om vi stjele en idé fra strenger hvor vi liksom koble disse tingene sammen konseptuelt, og hva om jeg gjorde dette? Dette er min aller dårlig tegnet pilen. Men anta at hver av disse biter av minne pekte til den andre, og denne fyren, som ikke har noen søsken til sin rett, har ingen slik pil. Dette er faktisk det som kalles en lenket liste. Dette er en ny datastruktur som tillater oss å fordele en del av minnet, deretter en annen, og deretter en annen, og deretter en annen, helst vi ønsker løpet av et program, og vi husker at de er alle en eller annen måte relatert ved bokstavelig talt chaining dem sammen, og vi gjorde det billedlig her med en pil. Men i koden, hva ville være den mekanismen via hvor du kunne liksom koble til, nesten som Scratch, en del til en annen del? Vi kunne bruke en peker, ikke sant? Fordi virkelig pilen som kommer fra øvre venstre torget, denne fyren her til denne, kan inneholde innsiden av denne plassen ikke bare noen ints, ikke bare noen røye, men hva hvis jeg faktisk tildelt litt ekstra plass slik at nå, hver av mine biter av minnet, selv om dette kommer til å koste meg, nå ser litt mer rektangulær hvor ett av biter av minne brukes for en rekke, som nummer 1, og hvis denne fyren lagrer nummer 2, denne andre del av minnet brukes til en pil, eller mer konkret, en peker. Og jeg antar lagre nummeret 3 over her mens jeg bruke dette til å peke på den fyren, og nå denne fyren, la oss anta jeg vil bare tre slike mengder minne. Jeg vil trekke en linje gjennom det, indikerer null. Er det ingen ekstra tegn. 

Faktisk er dette hvordan vi kan gå om å implementere noe som kalles en lenket liste. En lenket liste er en ny datastruktur, og det er et springbrett mot mye mer avansert datastrukturer som begynner å løse problemer langs linjene av Facebook-type problemer og Google-type problemer der du har store datasett, og det ikke lenger skjærer det til å lagre alt contiguously og bruke noe som lineær søk eller noe sånt binært søk. Du vil ha enda bedre kjører ganger. Faktisk en av de hellige gral vi snakke om senere denne uken eller neste er en algoritme som kjøretid er konstant. Med andre ord, tar det alltid den samme mengde av tid uansett hvor stor inngangen er, og det ville faktisk være overbevisende, enda mer enn noe logaritmisk. Hva er dette på skjermen her? Hver av rektangler er akkurat hva jeg bare trakk hånd. Men ting helt til venstre er en spesiell variabel. Det kommer til å være et enkelt peker fordi den ene fikser med en lenket liste, da disse tingene er kalt, er at du må henge på den ene enden av lenket liste. 

Akkurat som med en streng, må du vite adressen til den første røye. Samme avtale for koplede listene. Du må vite adressen til den første del av minnet fordi derfra, kan du nå alle andre. Ulemper. Hvilken pris vi betaler for denne allsidigheten av å ha en dynamisk sizable datastruktur som om vi skulle trenge mer minne, fine, bare tilordne en mer blings og trekke en peker fra den gamle til den nye halen av listen? Ja. [Student] Det tar omtrent dobbelt så mye plass. Det tar dobbelt så mye plass, så det er definitivt en ulemper, og vi har sett dette tradeoff før mellom tid og rom og fleksibilitet hvor nå, trenger vi ikke 32 bits for hver av disse tallene. Vi trenger virkelig 64, 32 for antall og 32 for pekeren. Men hei, jeg har 2 gigabyte RAM. Legge til en annen 32 biter her og her synes ikke så stor av en avtale. Men for store datasett, legger det definitivt opp til bokstavelig talt dobbelt så mye. Hva er en annen ulempe nå, eller hva funksjonen gir vi opp, hvis vi representerer lister over ting med en lenket liste og ikke en array? [Student] Du kan ikke krysse den bakover. Du kan ikke krysse den bakover, slik at du er typen skrudd hvis du vandre fra venstre til høyre ved hjelp av en for løkke eller en stund loop og du skjønner, "Å, jeg ønsker å gå tilbake til begynnelsen av listen." Du kan ikke fordi disse pekerne bare gå fra venstre til høyre som pilene viser. 

Nå kan du huske starten av listen med en annen variabel, men det er en kompleksitet å huske på. En matrise, uansett hvor langt du går, kan du alltid gjøre minus, minus, minus, minus og gå tilbake hvor dere kom fra. Hva er en annen ulempe her? Ja. [Uhørlig student spørsmål] Du kan, slik at du har faktisk bare foreslått en datastruktur som kalles en dobbelt lenket liste, og ja, ville du legge til en annen pekeren til hver av disse rektangler som går den andre retningen, oppsiden hvorav er nå kan du krysse fram og tilbake, nedsiden av som nå du bruker tre ganger så mye minne som vi pleide å og også legge kompleksitet i form av koden må du skrive for å få det riktig. Men disse er alle kanskje svært rimelige avveininger, dersom reverseringen er viktigere. Ja. [Student] Du kan heller ikke ha en 2D lenket liste. Bra, kan du egentlig ikke har en 2D lenket liste. Du kunne. Det er ikke på langt nær så lett som en matrise. Som en matrise, gjør du åpen brakett, lukket brakett, åpen brakett, lukket brakett, og du får noen 2-dimensjonal struktur. Du kan gjennomføre en 2-dimensjonal lenket liste hvis du gjør tillegget som du foreslo-tredjedeler peker til hver av disse tingene, og hvis du tenker på en annen liste som kommer mot deg 3D-stil fra skjermen for oss alle, som er bare en annen kjede av noe slag. Vi kunne gjøre det, men det er ikke så enkelt som å skrive åpen brakett, hakeparentes. Ja. [Uhørlig student spørsmål] Bra, så dette er en virkelig kicker. 

Disse algoritmene som vi har pined over, som oh, binær søk, du kan søke en rekke tall på bordet eller en telefonbok så mye raskere hvis du bruker splitt og hersk og et binært søk algoritmen, men binære søk kreves to forutsetninger. En, at dataene ble sortert. Nå kan vi antagelig holde dette sortert, så kanskje det er ikke en bekymring, men binære søk også antatt at du hadde direkte tilgang til listen over numre, og en rekke lar deg ha direkte tilgang, og ved direkte tilgang, Jeg mener hvis du får en rekke, hvor mye tid det tar deg å komme til braketten 0? En operasjon, du bare bruke [0] og du har rett der. Hvor mange skritt tar det å komme til plassering 10? Ett skritt, du bare gå til [10], og du er der. Derimot, hvordan får du til det 10. heltall i en lenket liste? Du må starte på begynnelsen fordi du bare huske begynnelsen på en lenket liste, akkurat som en streng blir husket av adressen sin første røye, til og finner ut at 10nde int eller at 10nde tegnet i en streng, må du søke på hele greia. 

Igjen, vi ikke løse alle våre problemer. Vi introduserer nye, men det er egentlig avhengig av hva du prøver å designe for. I form av å implementere dette, kan vi låne en idé fra at studenten struktur. Syntaksen er svært lik, bortsett fra nå, er ideen litt mer abstrakt enn hus og navn og ID. Men jeg foreslår at vi kunne ha en datastruktur i C som kalles node, som det siste ordet på lysbildet antyder, innsiden av en node, og en node er bare en generisk container i informatikk. Det er vanligvis tegnet som en sirkel eller et kvadrat eller rektangel som vi har gjort. Og i denne datastrukturen, har vi en int, n, så det er nummeret jeg ønsker å lagre. Men hva er dette andre linjen, struct node * neste? Hvorfor er dette riktig, eller hvilken rolle denne tingen spille, selv om det er litt kryptisk ved første øyekast? Ja. [Uhørlig student respons] Nøyaktig, slik at * slags krigsbytte at det er en peker av noe slag. Navnet på denne pekeren er vilkårlig neste, men vi kunne ha kalt det noe vi ønsker, men hva gjør denne pekeren peker på? [Student] En annen node. >> Akkurat, det peker til en annen slik node. 

Nå er denne typen av en kuriositet av C. Husker at C blir lest av en kompilator topp til bunn, fra venstre mot høyre, som betyr at hvis-dette er litt forskjellig fra hva vi gjorde med studenten. Når vi definert en student, vi faktisk ikke sette et ord der. Det sa typedef. Da vi hadde int id, string navn, string hus, og deretter student nederst struct. Denne erklæringen er litt annerledes fordi, igjen, er C-kompilator litt dum. Det er bare kommer til å lese topp til bunn, så hvis den når andre linje her hvor neste er erklært og det ser, oh, her er en variabel kalt neste. Det er en peker til en struct node. Kompilatoren kommer til å innse hva som er en struct node? Jeg har aldri hørt om denne tingen før, fordi ordet node ellers kanskje ikke ville synes til bunnen, så det er dette redundans. Du har å si struct node her, som du deretter kan forkorte senere takket være typedef her nede, men dette er fordi vi refererer selve strukturen innsiden av strukturen. Det er den fikser det. 

Noen interessante problemstillinger kommer til å oppstå. Vi har en liste med tall. Hvordan setter vi inn i det? Hvordan søker vi det? Hvordan sletter vi av det? Spesielt nå som vi har til å administrere alle disse pekerne. Du trodde pekere var liksom mind-bending når du hadde en av dem prøver bare å lese en int til det. Nå må vi manipulere en hel liste er verdt. Hvorfor ikke vi ta vår 5-minutters pause her, og så får vi ta noen folk opp på scenen for å gjøre akkurat det. 

C er mye mer moro når det er handlet ut. Hvem ville bokstavelig talt liker å være først? Ok, kom igjen opp. Du er først. Hvem ønsker å være 9? Ok, 9. Hva med 9? 17? En liten klikken her. 22 og 26 i den første rad. Og deretter hvordan om noen der å peke på. Du er 34. Ok, 34, kom igjen opp. Først er der borte. Ok, alle fire av dere. Og hvem sa vi for 9? Hvem er våre 9? Hvem ønsker egentlig å være 9? Greit, kom igjen, være 9. Here we go. 34, vil vi møte deg der borte. Den første delen er å gjøre dere se slik ut. 26, 22, 17, god. Hvis du kan stå ut til siden, fordi vi kommer til å malloc et øyeblikk. 

Bra, bra. Ok, utmerket, så la oss spørre et par spørsmål her. Og faktisk, hva heter du? >> Anita. Anita, okay, kom over her. Anita kommer til å hjelpe oss med å sortere av løse et ganske enkelt spørsmål i første, som er hvordan finner du hvorvidt en verdi i listen? Nå merke til at første, her representert ved Lucas, er litt annerledes, og så hans stykke papir er bevisst sidelengs fordi det er ikke fullt så høy og tar ikke opp så mange biter, selv om teknisk han har samme størrelse på papiret bare rotert. Men han er litt annerledes ved at han er bare 32 bits for en peker, og alle disse gutta er 64 bits, hvorav halvparten er antall, hvorav halvparten er en peker. Men pekeren ikke er avbildet, så hvis dere kunne noe klønete bruke venstre hånd til å peke på den personen ved siden av deg. Og du er nummer 34. Hva heter du? Ari. Ari, så egentlig, holder papiret i høyre hånd, og venstre hånd går rett ned. Du representerer null til venstre. 

Nå er vår menneskelige bildet er veldig konsekvent. Dette er faktisk hvordan pekere fungerer. Og hvis du kan knuse litt på denne måten, så jeg er ikke i veien. Anita her finner meg nummer 22, men antar en begrensning av ikke mennesker holder opp biter av papir, men dette er en liste, og du bare har Lucas til å begynne med fordi han er bokstavelig talt den første pekeren. Tenk deg at du er deg selv en peker, og slik at du også har muligheten til å peke på noe. Hvorfor ikke begynne med å peke på nøyaktig hva Lucas peker på? Bra, og la meg vedta dette ut over her. Bare for moro skyld diskusjonen, la meg trekke opp en blank side her. Hvordan staver du navnet ditt? >> Anita. Ok, Anita. La oss si node * anita = lucas. Vel, vi burde ikke kalle deg lucas. Vi burde ringe deg først. Hvorfor er dette faktisk forenlig med virkeligheten her? En, først eksisterer allerede. Først har fått tildelt antagelig et sted her oppe. Node * først, og det er blitt tildelt en liste eller annen måte. Jeg vet ikke hvordan det skjedde. Det skjedde før klassen startet. Dette lenket liste av mennesker har blitt opprettet. Og nå på dette punktet i historien-dette er alt som skjer Facebook tilsynelatende senere- på dette punktet i historien, har Anita blitt initialisert å være lik første, som ikke betyr at Anita poeng i Lucas. Snarere peker hun på hva han peker på fordi den samme adressen som er på innsiden av Lucas 32 biter - 1, 2, 3 - er nå også inne i Anitas 32 biter - 1, 2, 3. 

Nå finne 22. Hvordan vil du gå om du gjør dette? Hva er det? >> Pek på uansett. Peke på noe, så gå videre og handle det ut som best du kan her. Bra, bra, og nå er du peker på-hva er ditt navn med 22? Ramon. >> Ramon, så Ramon holder opp 22. Du har nå gjort en sjekk. Har Ramon == 22, og hvis så, for eksempel, kan vi returnere true. La meg-mens disse gutta står her litt klønete- la meg gjøre noe raskt som bool finne. Jeg kommer til å gå foran og si (node ​​* liste, int n). Jeg kommer straks tilbake med dere. Jeg må bare skrive noe kode. Og nå skal jeg gå videre og gjøre dette, node * anita = liste. Og jeg kommer til å gå foran og si mens (anita! = NULL). 

Metaforen her blir litt strukket, men mens (anita! = NULL), hva jeg ønsker å gjøre? Jeg trenger noen måte å referere heltallet at Anita peker på. I det siste, da vi hadde strukturer, som en node er, vi brukte dot notasjon, og vi vil si noe sånt anita.n, men problemet her er at Anita ikke er en struct per se. Hva er hun? Hun er en peker, så egentlig, hvis vi ønsker å bruke denne dot notasjon- og dette kommer til å se bevisst litt kryptisk- vi må gjøre noe sånt gå til hva Anita venstre hånd peker på og deretter få felt kalt n. Anita er en peker, men hva er * anita? Hva synes du når du går til hva Anita peker på? En struct, en node, og en node, tilbakekalling, har et felt som heter n fordi det har husker, disse to feltene, neste og n, at vi så et øyeblikk siden her. 

Å faktisk imitere dette i kode, vi kunne gjøre dette, og sier at hvis ((* anita). n == n), n som jeg leter etter. Legg merke til at funksjonen ble vedtatt i antall jeg bryr meg om. Da kan jeg gå videre og gjøre noe sånt return true. Annet, hvis det ikke er tilfelle, hva jeg ønsker å gjøre? Hvordan oversetter jeg å kode hva Anita gjorde det intuitivt ved å vandre gjennom listen? Hva bør jeg gjøre her oppe for å simulere Anita tar det skrittet til venstre, som steg til venstre? [Uhørlig student respons] >> Hva er det? [Uhørlig student respons] Bra, ikke en dårlig idé, men i det siste, når vi har gjort dette, har vi gjort anita + + fordi det ville legge til nummer 1 til Anita, som vanligvis ville peke på den neste personen, som Ramon, eller personen ved siden av ham, eller ved siden av ham person ned linjen. Men det er ikke helt bra her fordi det ser denne tingen som i minnet? Ikke det. Vi må deaktivere det. Det ser ut som dette i minnet, og selv om jeg har trukket 1 og 2 og 3 nær hverandre, hvis vi virkelig simulere dette-kan dere, samtidig peker på de samme menneskene, kan noen av dere ta en tilfeldig skritt tilbake, noen av dere en tilfeldig skritt fremover? 

Dette rotet er fortsatt en lenket liste, men disse gutta kan være hvor som helst i minnet, så anita + + ikke kommer til å jobbe hvorfor? Hva er på stedet anita + +? Hvem vet. Det er en annen verdi som bare så skjer for å være innlagt blant alle disse nodene ved en tilfeldighet fordi vi ikke bruker en matrise. Vi tildelt hver av disse nodene individuelt. Ok, hvis dere kan rydde dere opp igjen. La meg foreslå at i stedet for anita + +, vi i stedet gjør anita får- vel, hvorfor ikke vi gå til det Anita peker på, og deretter gjøre. neste? Med andre ord, vi går til Ramon, som er rangert som nummer 22, og da. neste er som om Anita skulle kopiere sin venstre hånd peker. Men hun ville ikke gå lenger enn Ramon fordi vi fant 22. Men det ville være ideen. Nå, dette er en gud-forferdelig søl. Ærlig, vil ingen noensinne huske denne syntaksen, og så heldigvis, det er faktisk litt bevisst-oh, gjorde du faktisk ikke se hva jeg skrev. Dette ville være mer overbevisende hvis du kunne. Voila! 

Bak kulissene, ble jeg løse problemet på denne måten. Anita, for å ta det skrittet til venstre, først, skal vi gå til den adressen som Anita peker på og hvor hun vil finne ikke bare n, som vi bare sjekket for sammenligning skyld, men du vil også finne neste - i dette tilfellet, Ramons venstre hånd peker til neste node i listen. Men dette er gud-forferdelig søl som jeg refererte tidligere, men det viser seg C lar oss forenkle dette. I stedet for å skrive (* anita), kan vi i stedet bare skrive anita-> n, og det er akkurat det samme funksjonelt, men det er mye mer intuitivt, og det er mye mer i samsvar med det bildet som vi har vært å tegne hele denne tiden ved hjelp av piler. 

Til slutt, hva vi trenger å gjøre på slutten av dette programmet? Det er en linje med kode som gjenstår. Returnere det? Usant, fordi hvis vi får gjennom hele mens loop og Anita er faktisk null, betyr at hun gikk helt til slutten av listen hvor hun pekte på-hva heter du igjen? Ari. >> Ari venstre hånd, som er null. Anita er nå null, og jeg skjønner du bare står her awkwardly i limbo fordi jeg skal ut på en monolog her, men vi vil involvere deg igjen i løpet av et øyeblikk. Anita er null på det punktet i historien, så mens loop opphører, og vi må tilbake false fordi hvis hun fikk hele veien til Ari nullpeker så var det ingen tall som hun søkte på listen. Vi kan rydde opp også, men dette er en ganske god gjennomføring og av en traversering funksjon, en finne funksjon for en lenket liste. Det er fortsatt lineær søk, men det er ikke så enkelt som + + en peker eller + + en i variabel fordi nå kan vi ikke gjette der hver av disse nodene er i minnet. Vi må bokstavelig talt følge sporet av brødsmuler, eller mer spesifikt, pekere, for å komme fra en node til en annen. 

Nå la oss prøve en annen. Anita, vil du komme tilbake hit? Hvorfor ikke vi gå videre og tildele en annen person fra publikum? Malloc-hva heter du? >> Rebecca. Rebecca. Rebecca er malloced fra publikum, og hun er nå lagrer nummer 55. Og målet for hånden er nå for Anita å sette Rebecca i lenket liste her i dens passende sted. Kom bort hit for et øyeblikk. Jeg har gjort noe som dette. Jeg har gjort node *. Og hva heter du igjen? Rebecca. >> Rebecca, ok. Rebecca får malloc (sizeof (node)). Akkurat som vi har tildelt ting som studenter og whatnot i det siste, vi trenger størrelsen på noden, så nå Rebecca peker på hva? Rebecca har to felt inne i henne, hvorav ett er 55 år. La oss gjøre hva, rebecca-> = 55. Men så rebecca-> neste bør-lignende akkurat nå, er hennes hånd slags hvem vet? Den peker på noen søppel verdi, så hvorfor ikke for godt mål vi i det minste gjøre dette slik at venstre hånd er nå på hennes side. Nå Anita, ta det herfra. Du har Rebecca har blitt tildelt. Gå videre og finne ut hvor vi bør sette Rebecca. Bra, veldig bra. Ok, bra, og nå trenger vi deg til å gi litt av retning, slik at du har nådd Ari. Hans venstre hånd er null, men Rebecca tydelig tilhører høyre, så hvordan har vi å endre dette lenket liste for å sette Rebecca i riktig sted? Hvis du kan bokstavelig talt flytte folks venstre hånd rundt etter behov, vi vil fikse problemet på den måten. Ok, bra, og i mellomtiden, er Rebecca venstre hånd nå ved hennes side. 

Det var for enkelt. La oss prøve tildeling-vi nesten ferdig, 20. Ok, kom igjen opp. 20 har fått tildelt, så la meg gå videre og si igjen her Vi har nettopp gjort node * Saad. Vi har malloc (sizeof (node)). Vi gjør de samme syntaks som vi gjorde før i 20, og jeg vil gjøre neste = NULL, og nå er det opp til Anita å sette deg inn i lenket liste, hvis du kunne spille den samme rollen. Execute. Ok, bra. Nå tenker nøye før du begynner å bevege venstre hånd rundt. Du langt fått mest pinlige rolle i dag. Hvis hånd bør flyttes først? Ok, vent, jeg hører noen ikke-tallet. Hvis noen folk ville høflig liker å bidra til å løse en vanskelig situasjon her. Som venstre hånd må oppdateres først kanskje? Ja. [Student] Saad-tallet. Ok, Saad-tallet, hvorfor, skjønt? [Uhørlig student respons] Bra, fordi hvis vi flytter-hva heter du? >> Marshall. Marshall, hvis vi flytter sin hånd først ned til null, nå har vi bokstavelig talt foreldreløs fire personer i denne listen fordi han var den eneste som peker på Ramon og alle til venstre, så oppdaterer at pekeren første var dårlig. La oss angre det. God, og nå gå videre og flytte den aktuelle venstre peker på Ramon. Dette føles litt overflødig. Nå er det to personer som peker på Ramon, men det er fint fordi nå hvordan andre oppdaterer vi listen? Hva derimot må flytte? Utmerket, nå har vi mistet noen minne? Nei, så bra, la oss se om vi ikke kan bryte denne gang. 

Mallocing en siste gang, nummer 5. Hele veien i ryggen, kom ned. Det er veldig spennende. [Applaus] Hva heter du? >> Ron. Ron, ok, du malloced som nummer fem. Vi har nettopp gjennomført kode som er nesten identisk med disse med bare et annet navn. Utmerket. Nå, Anita, lykke sette nummer 5 i listen nå. God, og? Utmerket, så dette er virkelig den tredje av tre totalt tilfeller. Først hadde vi noen på slutten, Rebecca. Vi hadde noen i midten. Nå har vi noen i begynnelsen, og i dette eksempelet, vi nå måtte oppdatere Lucas for første gang fordi det første element i listen nå har til å peke på en ny node, som i sin tur peker på node nummer 9. 

Dette var en enormt vanskelig demonstrasjon, jeg er sikker på, så en stor applaus for disse gutta hvis du kunne. Pent gjort. Det er alt. Du kan holde papirlapper som et lite minne. Det viser seg at du gjør dette i koden er ikke fullt så enkelt som bare å flytte hendene rundt og peker pekere til forskjellige ting. Men innser at når det gjelder tid til å gjennomføre noe sånt en lenket liste eller en variant av det hvis du fokuserer på virkelig disse grunnleggende fundamentale forhold, de bite-size problemer jeg må finne ut, er det denne hånden eller denne hånden, skjønner at det som ellers er en ganske kompleks program kan faktisk reduseres til forholdsvis enkle byggesteiner som dette. 

La oss ta ting i en mer sofistikert retning likevel. Vi har nå forestillingen om den lenket liste. Vi har også, takket være forslaget tilbake dit-en dobbelt lenket liste, som ser nesten det samme, men nå har vi to pekere innsiden av struct i stedet for én, og vi kunne sannsynligvis kalle disse pekere forrige og neste eller til venstre eller høyre, men vi gjør det, faktisk, trenger to av dem. Koden vil være litt mer involvert. Anita ville ha hatt å gjøre mer arbeid her på scenen. Men vi kan sikkert gjennomføre den slags struktur. I form av løpende tid, men hva ville være kjøretiden for Anita å finne et tall n i en lenket liste nå? Fortsatt stor O av n, så det er ikke noe bedre enn lineær søk. Vi kan ikke gjøre binære søk, men, igjen. Hvorfor var det slik? Du kan ikke hoppe rundt. Selv om vi selvsagt se alle menneskene på scenen, og Anita kunne ha eyeballed det og sa: «Her er midt på listen," Hun ville ikke vite at hvis hun var dataprogrammet fordi det eneste hun hadde å klinke til på begynnelsen av scenariet var Lucas, som var den første pekeren. Hun ville nødvendigvis må følge disse koblingene, telle hennes måte før hun fant omtrent på midten, og selv da, hun kommer ikke til å vite når hun har nådd midten med mindre hun går hele veien til enden for å finne ut hvor mange det er, Deretter backtracks, og som også vil være vanskelig med mindre du hadde en dobbelt lenket liste av noe slag. 

Løse noen problemer i dag, men å innføre andre. Hva om en annen datastruktur helt? Dette er et fotografi av skuffene i Mather House, og i dette tilfellet har vi en datastruktur vi har også slags allerede blitt snakket om. Vi snakket om en stabel i sammenheng med minne, og det er liksom bevisst kalt fordi en stabel i form av minne er effektivt en datastruktur som har mer og mer ting lagvis oppå den. Men det interessante ting om en stabel, slik tilfellet er i virkeligheten, er at det er en spesiell type datastruktur. Det er en datastruktur hvorved det første elementet i er det siste elementet ut. Hvis du er den første skuffen for å bli satt på stakken, du kommer til å være dessverre den siste skuffen for å bli tatt av stabelen, og som ikke er nødvendigvis en god ting. Omvendt kan du tenke på det den andre veien rundt, den siste i den første ut. 

Nå, noen scenarier kommer til tankene der har en stabel datastruktur hvor du har den egenskapen av sist inn, først ut, er faktisk overbevisende? Er det en god ting? Er det en dårlig ting? Det er definitivt en dårlig ting hvis magasinene var ikke alle identiske og de var alle spesielle forskjellige farger eller whatnot, og den fargen du ønsker er helt nederst. Selvfølgelig kan du ikke få det uten store anstrengelser. Du må starte fra toppen og jobb deg nedover. Tilsvarende, hva om du var en av disse fan gutter som venter oppe hele natten prøver å få en iPhone og linjer opp på et sted som dette? Ville det ikke vært fint hvis Apple Store var en stabel datastruktur? Yay? Nei? Det er bare bra for folk som dukker opp på den siste mulige øyeblikk og deretter få revet av køen. Og faktisk, det faktum at jeg var så tilbøyelig si kø er faktisk i tråd med det vi vil kalle denne typen data struktur, en i virkeligheten der rekkefølgen spiller ingen rolle, og du vil den første i å være den første ut hvis bare for moro skyld menneskelig rettferdighet. Vi vil generelt kalle det en kø datastruktur. 

Det viser seg dessuten knyttet listene, kan vi begynne å bruke de samme grunnleggende ideer og begynne å lage nye og ulike typer løsninger på problemer. For eksempel, i tilfelle av en stabel, kan vi representerer en stabel ved hjelp av en datastruktur som dette, ville jeg foreslå. I dette tilfellet har jeg erklært en struct, og jeg har sagt innsiden av denne strukturen er en matrise av tall, og deretter en variabel kalt størrelse, og jeg kommer til å kalle denne tingen en stabel. Nå, hvorfor dette faktisk fungerer? I tilfelle av en stabel, kan jeg trekke dette effektivt på skjermen som en matrise. Her er mitt stabelen. De er mine tall. Og vi vil trekke dem som dette, dette, dette, dette, dette. Og så har jeg noen andre data medlem her, som kalles størrelse, så dette er størrelsen, og dette er tall, og kollektivt representerer hele iPad her en stabel struktur. Nå, som standard, har størrelsen antagelig fått til å være initialisert til 0, og hva er inni rekken av tall i utgangspunktet når jeg først tildele en array? Søppel. Hvem vet? Og det spiller ingen rolle egentlig. Det spiller ingen rolle om det er 1, 2, 3, 4, 5, helt tilfeldig av uflaks lagret i strukturen min fordi så lenge jeg vet at størrelsen av stabelen er 0, så jeg vet programmatisk, ikke se på noen av elementene i matrisen. Det spiller ingen rolle hva som er der. Ikke se på dem, som ville være konsekvensen av en slik størrelse fra 0. 

Men antar nå jeg gå videre og sette noe inn i bunken. Jeg vil sette inn nummer 5, så jeg satte nummer 5 her, og hva setter jeg her nede? Nå vil jeg faktisk sette ned en for størrelsen, og nå bunken er av størrelse 1. Hva hvis jeg går videre og sette inn nummeret, la oss si, 7 neste? Dette blir deretter oppdatert til 2, og så får vi gjøre 9, og så dette blir oppdatert til 3. Men det interessante funksjonen nå i denne stabelen er at Jeg skal fjerne hvilket element hvis jeg ønsker å komme noe ut av bunken, så å si? 9 ville være den første tingen å gå. Hvordan skal bildet endres hvis jeg ønsker å komme et element av stabelen, mye som en skuff i Mather? Ja. >> [Student] Set størrelse til 2. Akkurat, er alt jeg gjør satt størrelsen til 2, og hva gjør jeg med array? Jeg trenger ikke å gjøre noe. Jeg kunne, bare for å være anal, sette en 0 der eller en -1 eller noe å betegne at dette ikke er en legit verdi, men det spiller ingen rolle fordi Jeg kan spille utenfor matrisen selv hvor lenge det er slik at jeg vet bare se på de to første elementene i denne matrisen. Nå, hvis jeg går og legger til nummer 8 til denne tabellen, hvordan bildet endres neste? Dette blir 8, og dette blir 3. Jeg kutter noen hjørner her. Nå har vi 5, 7, 8, og er vi tilbake til en størrelse på 3. Dette er ganske enkelt å implementere, men når vi kommer til å angre på dette utformingsavgjørelsen? Når begynner ting du å gå veldig, veldig galt? Ja. [Uhørlig student respons] Når du ønsker å gå tilbake og få det første elementet du setter inn 

Det viser seg her, selv om en stabel er en rekke under panseret, disse datastrukturer vi har begynt å snakke om er også allment kjent som abstrakte datastrukturer der hvor de er implementert er helt foruten poenget. En datastruktur som en stabel er ment å legge til støtte operasjoner som push, som presser en skuff på stakken, og pop, som fjerner et element fra bunken, og det er det. Hvis du var å laste ned andres kode som allerede iverksatt dette som kalles en stabel, ville vedkommende har skrevet bare to funksjoner for deg, trykk og pop, hvis eneste mål i livet ville være å gjøre akkurat det. Du eller ham eller henne som gjennomføres det programmet ville ha vært helt en å bestemme hvordan de skal gjennomføre semantikk presser og spratt under panseret eller funksjonaliteten til å skyve og spratt. Og jeg har gjort en noe kortsiktig avgjørelse her ved å implementere min stabel med denne enkle datastruktur hvorfor? Når gjør dette datastruktur pause? På hvilket punkt må jeg returnere en feil når brukeren ringer push, for eksempel? [Student] Hvis det ikke mer plass. Akkurat, hvis det er ikke mer plass, hvis jeg har overskredet kapasitet, som er alle caps fordi det antyder at det er en slags global konstant. Vel, da er jeg bare nødt til å si: "Beklager, jeg kan ikke presse en annen verdi på bunken, "mye som i Mather. 

På et tidspunkt, de kommer til å treffe den øverste delen av den lille kabinettet. Det er ikke mer plass eller kapasitet i bunken, og da er det noen form for feil. De må sette elementet et annet sted, skuffen et annet sted, eller ingen steder. Nå, med en kø, kunne vi gjennomføre det litt annerledes. En kø er litt annerledes ved at under panseret, kan det settes i verk som en matrise, men hvorfor, i dette tilfellet, er jeg foreslår å også ha et hode element representerer hodet av listen, fronten av listen, den første personen i linje på Apple butikken, i tillegg til størrelse? Hvorfor trenger jeg en ekstra stykke data her? Tenk tilbake til hva tallene er hvis jeg har trukket den som følger. Antar at dette er nå en kø i stedet for en stabel, forskjellen blir, akkurat som Apple Store-køen er rettferdig. Den første personen i linje ved starten av listen, nummer 5 i dette tilfellet, han eller hun kommer til å bli sluppet inn i butikken først. La oss gjøre det. Anta at dette er staten køen min på dette tidspunkt, og nå Apple Store åpner og den første personen, nummer 5, ledes inn i butikken. Hvordan endrer jeg bildet nå som jeg har DE-kø den første personen på forsiden av linjen? Hva er det? >> [Student] Endre køen. Endre hodet, så 5 forsvinner. I virkeligheten er det som om-hvordan best å gjøre dette? I virkeligheten er det som om denne fyren forsvinner. Hva ville nummer 7 gjøre i en faktisk butikk? De ville ta et stort skritt fremover. 

Men hva har vi kommet til å verdsette når det kommer til arrays og flytte ting rundt? Det er litt av en sløsing med tid, ikke sant? Hvorfor har du å være så anal som å ha den første personen ved starten av linjen ved fysisk starten av mengde minne? Det er helt unødvendig. Hvorfor? Hva kan jeg bare huske stedet? >> [Uhørlig student respons] Akkurat, jeg kunne bare huske med denne ekstra data medlem hodet som nå leder av listen er ikke lenger 0, som det var for et øyeblikk siden. Nå er det faktisk nummer 1. På denne måten får jeg en liten optimalisering. Bare fordi jeg har de-kø noen fra linjen ved starten av linjen på Apple Store betyr ikke at alle har til å skifte, som tilbakekallingen er en lineær operasjon. Jeg kan i stedet bruke konstant tid bare og oppnå så mye raskere respons. Men prisen jeg betaler er hva du får som ekstra ytelse og ikke trenger å skifte alle? Ja. >> [Uhørlig student respons] Kan legge til flere mennesker, vel, er det problemet ortogonale til det faktum at vi ikke er skiftende folk rundt. Det er fortsatt en matrise, så om vi flytter alle eller ikke- oh, jeg ser hva du mener, ok. Egentlig, jeg er enig med det du sier i at det er nesten som om Vi overvåker nå aldri kommer til å bruke starten av denne tabellen lenger fordi hvis jeg fjerner 5, så jeg fjerne 7. Men jeg bare sette folk til høyre. 

Det føles som om jeg kaster bort plass, og til slutt min køen disintegrates inn noe i det hele tatt, slik at vi kunne bare ha folk wraparound, og vi kunne tenke på denne tabellen egentlig som en slags sirkulær struktur, men vi bruker det operatøren i C for å gjøre den slags wraparound? [Uhørlig student respons] >> Den modulo operatør. Det ville være litt irriterende å tenke gjennom hvordan du gjør wraparound, men vi kunne gjøre det, og vi kunne begynne å sette folk på det pleide å være på forsiden av linjen, men vi bare huske med dette hodet variabelen som selve hodet av linjen faktisk er. Hva om, i stedet, vårt mål til slutt, skjønt, var å slå opp numre, som vi gjorde her på scenen med Anita, men vi virkelig ønsker det beste av alle disse verdener? Vi ønsker mer raffinement enn matrise kan fordi vi ønsker muligheten til dynamisk vokse datastrukturen. Men vi ønsker ikke å måtte ty til noe som vi påpekte i den første forelesningen var ikke en optimal algoritme, at av lineær søk. Det viser seg at du kan faktisk oppnå eller i det minste nær konstant tid, hvorved en som Anita, hvis hun konfigurerer sin datastruktur ikke å være en lenket liste, ikke å være en stabel, for ikke å være en kø, kunne faktisk komme opp med en datastruktur som gjør henne til å slå opp ting, selv ord, ikke bare tall, i det vi kaller konstant tid. 

Og faktisk, ser fremover, er en av de i denne klassen psets nesten alltid en implementering av en stavekontroll, der gir vi deg igjen noen 150000 engelske ord og målet er å laste dem inn i minnet og raskt kunne svare på spørsmål i skjemaet er dette ordet stavet riktig? Og det ville virkelig suge hvis du måtte iterate gjennom alle 150000 ord for å svare på det. Men, faktisk, vil vi se at vi kan gjøre det i veldig, veldig rask tid. Og det kommer til å innebære å implementere noe som kalles en hash table, og selv om ved første øyekast dette som kalles en hash table kommer til å la oss få disse super rask responstid det viser seg at det er faktisk et problem. Når det gjelder tid til å implementere dette som kalles-igjen, jeg gjør det igjen. Jeg er den eneste her. Når det gjelder tid til å implementere dette som kalles en hash table, vi nødt til å ta en beslutning. Hvor stor bør denne tingen egentlig være? Og når vi begynner å sette inn tallene i denne hash table, hvordan skal vi lagre dem på en slik måte at vi kan få dem ut igjen så raskt som vi fikk dem inn? Men vi får se før lenge at dette spørsmålet når alles bursdag i klassen vil være ganske germane. Det viser seg at i dette rommet, har vi et par hundre mennesker, så oddsen for at to av oss har samme bursdag er trolig ganske høy. Hva hvis det var bare 40 av oss i dette rommet? Hva er oddsen for to personer med samme bursdag? [Studenter] Over 50%. Ja, over 50%. Faktisk, jeg selv tok et diagram. Det viser seg, og dette er egentlig bare en smakebit- hvis det er bare 58 av oss i dette rommet, er sannsynligheten for 2 av oss har samme bursdag er enormt høy, nesten 100%, og det kommer til å føre til en hel haug med skade for oss på onsdag. 

Med det sagt, la oss utsette her. Vi vil se deg på onsdag. [Applaus] [CS50.TV]