SPEAKER 1: Ok, så dette er CS50 Dette er slutten av uken fem. Og huske at sist gang vi begynte å se på mer avansert data strukturer som begynte å løse problemer, som begynte å introdusere nye problemer, men nøkkelen til dette var slags threading at vi begynte å gjøre fra node til node. Så dette er selvfølgelig en enkeltvis lenket liste. Og ved enkeltvis knyttet sammen, Jeg mener det er bare ett tråden mellom hver av disse nodene. Det viser seg at du kan gjøre mer avansert ting som dobbelt lenkede lister der du har en pil går i begge retninger, noe som kan hjelpe med visse effektivitet. Men dette løste problemet? Hva problem gjorde dette løse? Hvorfor gjorde vi bryr oss på mandag? Hvorfor, i teorien, vi bryr på mandag? Hva gjør det? 

PUBLIKUM: Vi kan dynamisk endre størrelsen. 

SPEAKER 1: OK, så vi kan dynamisk endre størrelsen. Godt gjort dere begge. Så du kan dynamisk endre størrelsen på dette datastruktur, mens en matrise, tilbakekallingen, må du vite priori hvor mye plass du vil og hvis du trenger litt mer plass, er du på en måte ute av lykken. Du må opprette en helt ny rekke. Du må flytte alle dine data fra den ene til den annen, slutt frigjøre gamle matrise hvis du kan, og deretter fortsette. Som bare føles veldig kostbart og svært ineffektiv, og faktisk det kan være. Men dette er ikke alt bra. Vi betaler en pris, det som var en av de mer åpen prisene vi betale ved hjelp av en lenket liste? 

PUBLIKUM: Vi må bruke dobbel plass for hver enkelt. SPEAKER 1: Ja, så vi trenger minst dobbelt så mye plass. Faktisk, jeg innså at dette bildets enda litt misvisende, fordi på CS50 IDE i mange moderne datamaskiner, en peker eller en adresse ikke er i virkeligheten fire bytes. Det er veldig ofte disse dager åtte bytes, som betyr den nederste rektangler der i virkeligheten er slags dobbelt så stor som det jeg har tegnet, noe som betyr at du bruker tre ganger så mye plass som vi kan ha noe annet. Nå på samme tid, er vi fremdeles snakker bytes, ikke sant? Vi er ikke nødvendigvis snakker megabyte eller gigabyte, med mindre disse data strukturer bli stor. 

Og så i dag skal vi begynne å vurdere hvordan vi kan utforske data mer effektivt hvis du er i Faktisk data blir større. Men la oss prøve å canonicalize operasjonene første som du kan gjøre på disse typer datastrukturer. Så noe sånt som en koblet liste støtter generelt operasjoner liker slette, sette inn, og søk. Og hva mener jeg med det? Det betyr bare at vanligvis, hvis folk bruker lenket liste, de eller noen andre har implementert funksjoner som å slette, sette inn, og søk, slik at du kan faktisk gjøre noe nyttig med datastrukturen. Så la oss ta en rask titt på hvordan vi kan implementere noen kode for en lenket liste som følger. 

Så dette er bare noen C-kode, ikke engang et komplett program at jeg virkelig raskt pisket opp. Det er ikke online i fordelingen kode, fordi det vil faktisk ikke kjøre. Men merker jeg har bare med en kommentar sa: dot dot dot, det er noe der, dot dot dot, noe der. Og la oss bare se på hva de saftige delene er. Så på linje tre, minne om at dette er nå Vi foreslo å erklære en node siste tid, en av de rektangulære objekter. Den har en int som vi kaller N, men vi kan kalle det noe, og deretter en struct node stjerne kalt neste. Og bare for å være klar, at andre linje, på linje seks, hva er det? Hva er det du gjør for oss? Fordi det ser absolutt mer kryptisk enn vår vanlige variabler. 

PUBLIKUM: Det gjør det flytter over en. 

SPEAKER 1: Det gjør det flytter over en. Og for å være mer presis, det vil lagre adressen av noden som er ment å være semantisk ved siden av det, ikke sant? Så det kommer ikke til å nødvendigvis bevege seg noe. Det er bare kommer til lagrer en verdi, som er kommer til å være adressen av en annen node, og det er derfor vi har sagt struct node stjerne, stjerne betegner en peker eller en adresse. OK, så nå hvis du antar at vi har dette N tilgjengelig for oss, og la oss anta at noen andre har satt inn en hel haug av heltall inn i en lenket liste. Og det lenket liste er peker på et tidspunkt en variabel kalt liste som er gått her som en parameter, hvordan går jeg om linje 14 gjennomføre søk? Med andre ord, hvis jeg implementere funksjon hvis formål i livet er å ta en int, og deretter begynnelsen av en lenket liste, som er en peker til lenket liste. Som første, som jeg tror David var vår frivillig på mandag, han peker på hele lenket liste, det er som om vi passerer David inn som vår argument her. Hvordan går vi om å gå gjennom denne listen? Vel, det viser seg at selv om pekere er relativt nytt nå til oss, vi kan gjøre dette relativt oversiktlig. 

Jeg kommer til å gå videre og erklære en midlertidig variabel som etter konvensjonen er bare kommer å bli kalt pekeren, eller PTR, men du kan kalle det hva du vil. Og jeg kommer til å initial den til starten av listen. Så du kan slags tenke på dette som meg læreren den andre dagen, slags peker på noen blant våre mennesker som frivillige. Så jeg er en midlertidig variabel som er bare å peke på det samme at vår tilfeldigvis heter frivillig David ble også peke ut. Nå mens pekeren er ikke null, fordi tilbakekalling at null er noen spesielle sentinel verdi den avgrenser enden av listen, så mens jeg ikke peker på bakken som vår siste frivillig var, la oss gå videre og gjøre følgende. Hvis pointer-- og nå jeg slags ønsker å gjøre det vi gjorde med studenten structure-- hvis pekeren dot neste equals-- heller, hvis pekeren dot N er lik lik den variable N, jo argument som er blitt vedtatt i, så jeg ønsker å gå videre og si return true. Jeg har funnet at antallet N innside en av nodene i min lenket liste. Men prikken ikke lenger arbeider i denne sammenheng fordi pekeren, PTR, er faktisk en peker, en adresse, vi faktisk kan prakt bruke endelig et stykke syntaks den slags merker intuitiv følelse og faktisk bruke en pil her, som betyr å gå fra at adressen til det heltall der i. Så det er svært like i ånd til dot operatør, men fordi pekeren er ikke en peker og ikke en faktisk struct seg selv, vi bare bruke pilen. 

Så hvis den nåværende node at jeg, midlertidig variabel, er å peke på er ikke N, hva jeg ønsker å gjøre? Vel, med mine frivillige som vi hadde her om dagen, Hvis min første mennesket er ikke den jeg ønsker, og kanskje andre menneske er ikke den jeg vil ha, og den tredje, jeg trenger for å holde fysisk bevegelse. Som hvordan kan jeg gå gjennom en liste? Da vi hadde en rekke, du bare gjorde som jeg pluss pluss. Men i dette tilfellet er det tilstrekkelig å gjøre pekeren, får, peker, neste. Med andre ord, det neste feltet er som alle de venstre hånd at våre frivillige på mandag ble brukt for å peke mot en annen node. De som var deres nærmeste naboer. 

Så hvis jeg ønsker å gå gjennom denne listen, Jeg kan ikke bare gjøre jeg pluss pluss lenger, Jeg i stedet har å si Jeg, peker, kommer til lik uansett neste feltet er, det neste feltet, er det neste felt, etter alle disse venstre hånd som vi hadde på scenen peker til noen påfølgende verdier. Og hvis jeg får gjennom at hele iterasjon, og til slutt, jeg treffer null ikke å ha funnet N ennå, jeg bare returnere false. Så igjen, alt det vi gjør her, som per i bildet en stund siden, starter ved å peke på begynnelsen av listen formodentlig. Og da jeg sjekke, er verdien Jeg leter etter lik til ni? Hvis så, jeg kommer tilbake sant og jeg er ferdig. Hvis ikke, kan jeg oppdatere min hånd, AKA pekeren, å peke ved neste pilen befinner seg, og så den neste pilen befinner seg, og den neste. Jeg er ganske enkelt å gå gjennom denne matrisen. 

Så igjen, hvem bryr seg? Som hva er dette en ingrediens for? Vel, husker at vi innførte oppfatningen av en stabel, som er en abstrakt datatype i den utstrekning det er ikke en C ting, det er ikke en CS50 ting, det er en abstrakt idé, denne ideen om stable ting oppå hverandre som kan implementeres i bunter av forskjellige måter. Og en måte vi foreslo var med en matrise, eller med en lenket liste. Og det viser seg at kanonisk, en stabelen støtter i det minste to operasjoner. Og buzz ord er push, til skyve noe på stakken, som et nytt brett i spisesal, eller pop, noe som betyr at for å fjerne den øverste brett fra stabelen i spise hall, og så kanskje noen andre operasjoner også. Så hvordan kan vi definere strukturen at vi nå kaller en bunke? 

Vel, vi har alle de nødvendige syntaks til rådighet i C. sier jeg, gi meg en type definisjon av en struct innsiden av en stabel, Jeg kommer til å si er en matrise, av en hel haug med tall og deretter størrelse. Så med andre ord, hvis jeg vil ha for å gjennomføre denne i kode, la meg gå og bare slags tegne hva denne sier. Så dette er å si, gi meg en struktur som har fått en matrise, og jeg vet ikke hva kapasiteten er, det er tydeligvis noen konstant at jeg har definert et annet sted, og det er fint. Men antar at det er bare en, to, tre, fire, fem. Så kapasiteten er 5. Dette elementet innsiden av mitt strukturen vil bli kalt tall. Og da trenger jeg en andre variable tilsynelatende kalt størrelsen som opprinnelig kommer jeg å fastsette er initialisert til null. Hvis det ikke er noe i stabelen, størrelse er null, og det er søppel verdier i tall. Jeg aner ikke hva som er der ennå. 

Så hvis jeg ønsker å presse noe på stakken, antar jeg kaller funksjonen push, og Jeg sier presse 50, som nummer 50, hvor ville du foreslå Jeg tegner det i denne array? Det finnes fem forskjellige mulige svar. Hvor ønsker du å presse nummer 50? Hvis målet her, igjen, ring Funksjonen push, passere i en krangel 50, hvor skal jeg plassere den? Fem possible-- 20% sjanse for å gjette riktig. Ja? 

PUBLIKUM: Far høyre. 

SPEAKER 1: Far høyre. Det er nå en 25% sjanse for å gjette riktig. Så det ville faktisk være i orden. Ved konvensjonen, vil jeg si med en matrise, vi ville vanligvis starter på venstre, men vi kunne sikkert starter på høyre. Så spoiler her ville være jeg er sannsynligvis kommer til å trekke den til venstre, akkurat som i en vanlig matrise der Jeg begynne å gå fra venstre til høyre. Men hvis du kan bla aritmetisk, fine. Det er bare ikke vanlig. OK, jeg trenger å gjøre en mer endring skjønt. Nå som jeg har skjøvet noe på stakken, hva blir det neste? 

Greit, jeg har for å øke størrelsen. Så la meg gå videre og bare oppdatere denne, som var null. Og i stedet nå, jeg kommer å sette i verdien en. Og nå antar jeg trykker en annen nummeret på stakken, som 51. Vel, jeg må gjøre en mer endring, som er opp til størrelsen to. Og så antar jeg trykker på en mer nummeret på stakken som 61, Nå trenger jeg å oppdatere størrelse ett mer tid, og få verdien 3 som størrelsen. Og nå antar jeg kaller pop. Nå pop, etter konvensjonen, tar ikke et argument. Med en stabel, hele punkt av skuffen metafor er at du ikke har skjønn å gå får den skuffen, kan alt du gjør er pop den øverste en fra stabelen, bare fordi. Det er det dette datastruktur gjør. 

Så ved at logikken hvis jeg si pop, hva kommer av? Så 61. Så hva er egentlig datamaskinen kommer til å gjøre i minnet? Hva gjør koden min har å gjøre? Hva ville du foreslå vi endrer på skjermen? Hva bør endres? Sorry? Så vi bli kvitt 61. Så jeg kan definitivt gjøre det. Og jeg kan bli kvitt 61. Og så hva andre endring må skje? Størrelse har sannsynligvis å gå tilbake til to. Og så er det helt greit. Men vent litt, størrelse et øyeblikk siden var tre. La oss bare gjøre en rask tilregnelighet sjekk. Hvordan fikk vi vite at vi ønsket å kvitte seg med 61? Fordi vi spratt. Og så har jeg denne andre eiendomsstørrelse. 

Vent litt, jeg er tenker tilbake til uke to da vi begynte å snakke om matriser, der dette var stedet null, dette var stedet en, dette var stedet to, er dette sted tre, fire, det ser ut som forholdet mellom størrelse og elementet som jeg ønsker å fjerne fra tabellen ser ut til å bare være det? Størrelse minus én. Og så det er hvordan som mennesker vi vet 61 kommer først. Hvordan er datamaskinen kommer til å vite? Når koden din, der du sannsynligvis ønsker å gjøre størrelse minus én, så tre minus en er to, og at betyr at vi ønsker å kvitte seg med 61. Og da kan vi faktisk oppdatere størrelsen slik at størrelsen nå går fra tre til bare to. Og bare for å være pedantisk, jeg kommer å foreslå at jeg er ferdig, ikke sant? Du foreslo intuitivt riktig jeg bør kvitte seg med 61. Men har ikke jeg slags liksom blitt kvitt 61? Jeg har effektivt glemt at det er faktisk det. Og tenker tilbake til PSET4, hvis du har lest artikkelen om etterforskning, PDF at vi måtte dere lese, eller du vil lese denne uken for PSET4. Husk at dette er faktisk viktig til hele ideen om dataetterforskning. Hva en datamaskin generelt gjør er det bare glemmer hvor noe er, men det går ikke inn og ut prøver å klø den ut eller overstyring de biter med nuller og enere eller annen tilfeldig mønster med mindre du selv gjør det bevisst. Så din intuisjon var Greit, la oss bli kvitt 61. Men i virkeligheten, trenger vi ikke å bry seg. Vi trenger bare å glemme at den er der ved å endre vår størrelse. 

Nå er det et problem med denne bunken. Hvis jeg holde skyve ting på stakken, hva er åpenbart kommer til å skje i bare noen øyeblikk tid? Vi kommer til å gå tom for plass. Og hva gjør vi? Vi er litt skrudd. Denne implementeringen ikke lar oss endre størrelsen på array, fordi du bruker dette syntaks, hvis du tenker tilbake til uke to, når du har erklært på størrelse med en matrise, vi har ikke sett en mekanisme ennå hvor endre størrelsen på matrisen. Og faktisk C ikke har denne funksjonen. Hvis du sier gi meg fem- Nths, kaller dem tall, det er alt du kommer til å få det. Så vi gjør nå som av mandag, har evnen til å uttrykke en løsning skjønt, vi trenger bare å finpusse definisjonen av stacken å ikke være noen hardkodet array, men bare for å lagre en adresse. 

Nå hvorfor er dette? Nå er vi bare nødt til å være komfortabel med det faktum at når min programmet kjører, Jeg antagelig kommer til å må spørre den menneskelige, hvor mange tall du vil lagre? Så innspill må komme fra et sted. Men når jeg vet at nummer, så jeg kan bare bruke hvilken funksjon å gi meg en blings av minne? Jeg kan bruke malloc. Og jeg kan si hvilket som helst antall byte Jeg vil tilbake for disse Nths. Og alt jeg har å lagre i tallene variabel her inne i denne struct bør være hva? Hva som faktisk går inn i Tallene i dette scenariet? Ja, en peker til den første byte av den del av minnet, eller mer spesifikt, den adresse av den første av disse bytes. Spiller ingen rolle om det er en byte eller en milliard bytes, Jeg trenger bare å bry seg om det første. Fordi hva malloc garantier og operativsystemet garantier, er at den del av minnet jeg får, kommer det til å være sammenhengende. Det kommer ikke til å være hull. Så hvis jeg har bedt om 50 byte eller 1000 bytes, de er alle kommer til å være rygg mot rygg mot rygg. Og så lenge jeg husker hvor stort, hvor mye jeg ba om, alt jeg trenger å vite er den første adressen. 

Så nå har vi muligheten i kode. Riktignok, det kommer til å ta oss mer tid til å skrive dette opp, vi kunne nå omdisponere at minnet etter bare lagre en annen adresse der hvis vi ønsker en større eller en mindre del av minnet. Så her til en trade off. Nå får vi dynamikk. Vi har fortsatt contiguousness jeg hevde. Fordi malloc vil gi oss en sammenhengende mengde minne. Men dette kommer til å være en smerte i nakken for oss, programmerer, å faktisk kode opp. Det er bare mer arbeid. Vi trenger kode beslektet med hva jeg var banging ut bare for et øyeblikk siden. Veldig gjennomførbart, men det legger kompleksitet. Og så utvikler tid, programmerer tid er enda en annen ressurs at vi kanskje trenger å bruke litt tid å få nye funksjoner. Og så selvfølgelig er det en kø. Vi vil ikke gå inn i denne en i mye detalj. Men det er svært like i ånden. Jeg kunne gjennomføre en kø, og sine tilsvarende operasjoner, enqueue eller dequeue, som legger til eller fjerner, det er bare en mer avansert måte å si det, enqueue eller dequeue, som følger. Jeg kan bare gi meg selv en struct som igjen har en rekke matrise, som igjen har en størrelse, men hvorfor gjør jeg nå trenger å holde styr på forsiden av en kø? Jeg trenger ikke å vite forsiden av stabelen min. Vel, hvis jeg igjen for en queue-- la oss bare vanskelig kode det som å ha som fem heltall i her potensielt. Så dette er null, en, to, tre, fire. Dette kommer til å være numrene igjen. Og dette vil bli kalt størrelse. 

Hvorfor er det ikke tilstrekkelig å ha bare størrelse? Vel, la oss presse de samme tallene på. Så jeg pushed-- jeg enqueued, eller dyttet. Nå skal jeg Enqueue 50, og deretter 51, og deretter 61, og dot dot dot. Så det er enqueue. Jeg enqueued 50, deretter 51, deretter 61. Og som ser identisk til en stabel så langt, bortsett fra at jeg trenger å gjøre en endring. Jeg trenger å oppdatere denne størrelsen, så jeg går fra null til en til 02:58 nå. Hvordan dequeue jeg? Hva skjer med dequeue? Hvem skal komme ut denne listen først hvis det er kø på Apple Store? Så 50. Så det er litt vanskeligere denne gangen. Mens forrige gang det var super lett å bare gjøre størrelse minus én, Jeg kommer til slutten av min matrise effektivt der tallene er, fjerner det 61. Men jeg ønsker ikke å fjerne 61. Jeg ønsker å ta 50, som var der på 5:00 å stille opp for ny iPhone eller whatnot. Og så å kvitte seg med 50, jeg kan ikke bare gjøre dette, ikke sant? Jeg kan krysse ut 50. Men vi sa vi trenger ikke å være så anal som å klø seg eller skjule data. Vi kan bare glemme hvor det er. 

Men hvis jeg endrer størrelse nå to, er dette tilstrekkelig informasjon å vite hva som skjer i min kø? Ikke egentlig. Som min størrelse er to, men hvor kommer køen begynner, spesielt hvis jeg fortsatt har de samme tallene i minnet. 50, 51, 61. Så jeg trenger å huske nå hvor fronten er. Og så så jeg foreslo opp der, vil vi nettopp har kalt Nth front, som første Verdien skal ha vært hva? Zero, bare begynnelsen av listen. Men nå i tillegg til å minske størrelsen, vi bare øke foran. Nå her er et annet problem. Så når jeg holder det gående. Antar at dette er antall som 121, 124, og så, for faen, Jeg er tom for plass. Men vent litt, jeg er ikke det. Så på dette punktet i historien, anta at størrelsen er en, to, tre, fire, slik at det antar Størrelsen er fire, foran er én, så 51 er på forsiden. Jeg ønsker å sette et annet nummer her, men, faen, jeg er tom for plass. Men jeg er ikke egentlig, ikke sant? Hvor kan jeg sette noen tilleggsverdi, som 171? Ja, jeg kunne bare slags gå tilbake dit, ikke sant? Og deretter krysse ut 50, eller bare overskrive den med 171. Og hvis du lurer på hvorfor våre tall ble så tilfeldig, disse blir ofte tatt datamaskin vitenskap kurs ved Harvard etter CS50. Men det var en god optimalisering, fordi nå er jeg ikke kaste bort plass. Jeg har fortsatt å huske hvor stor denne saken er total. Det er fem totalt. Fordi jeg ønsker ikke å begynner å overskrive 51. Så nå er jeg fortsatt tom for plass, så det samme problemet som før. Men du kan se hvordan nå i koden din, har du sannsynligvis må skrive litt mer kompleksitet å gjøre det skje. Og faktisk, hvilken operatør i C sannsynligvis lar du magisk gjøre dette sirkulariteten? Yeah modulo operatør, prosenttegnet. Så hva er litt kult om en kø, selv om vi holder tegning arrays som disse som rette linjer, hvis du slags tenke på dette som kurvet rundt som en sirkel, så bare intuitivt den slags fungerer mentalt Jeg tror litt mer renslig. Du ville fortsatt å implementere som mental modell i kode. Så det er ikke så vanskelig, til slutt, for å implementere, men vi har fortsatt miste size-- snarere evne til å endre størrelse, hvis vi ikke gjør dette. 

Vi må bli kvitt den array, vi erstatte den med en enkelt peker, og deretter et sted i koden min har jeg fått en kaller det fungere å faktisk lage array kalt tall? Malloc, eller en lignende funksjon, akkurat. Eventuelle spørsmål om stabler eller køer. Yeah? Godt spørsmål. Hva modulo ville du bruke her. Så generelt, når du bruker mod, ville du gjøre det med størrelsen av Hele datastruktur. Så noe sånt som fem eller kapasitet, hvis det er konstant, er trolig involvert. Men bare gjør modulo five sannsynligvis ikke er tilstrekkelig, fordi vi trenger å vite gjør vi vikle rundt her eller her eller her. Så du er sannsynligvis også kommer til å ønske å involvere størrelsen av ting, eller den fremre variable i tillegg. Så det er bare denne relativt enkle aritmetiske uttrykk, men modulo ville være hovedingrediensen. 

Så kortfilm om du vil. En animasjon som noen folk på et annet universitet satt sammen at vi har tilpasset for denne diskusjonen. Det innebærer Jack læring fakta om køer og statistikk. 

FILM: Det var en gang, det var en fyr som heter Jack. Når det kom til å få venner, Jack ikke har en egen evne. Så Jack gikk for å snakke med mest populære fyren han visste. Han gikk til Lou og spurte: Hva gjør jeg? Lou så at hans venn var veldig fortvilet. Vel, begynte han, bare se hvordan du er kledd. Har du ikke noen klær med et annet utseende? Ja, sa Jack. Jeg er sikker på do. Kom til huset mitt og Jeg skal vise dem til deg. Så gikk de bort til Jack. Og Jack viste Lou boksen hvor han holdt alle hans skjorter, og buksene, og hans sokker. Lou sa, jeg ser du har alle klærne i en haug. Hvorfor ikke ha noen andre gang på en stund? 

Jack sa, vel, da jeg Fjern klær og sokker, Jeg vasker dem og sette dem bort i esken. Så kommer neste morgenen, og opp jeg hoppe. Jeg går til boksen og få klærne mine utenfor toppen. Lou skjønte raskt problemet med Jack. Han holdt klær, CD-er, og bøker i bunken. Da han kom for noe å lese eller å bære, han ville velge toppen bok eller undertøy. Så når han var ferdig, han ville sette den rett tilbake. Tilbake det ville gå, på toppen av bunken. Jeg vet løsningen, sa en triumfer Loud. Du trenger å lære å begynne å bruke en kø. Lou tok Jack klær og hang dem i skapet. Og da han hadde tømt boksen, han bare kastet den. 

Så sa han, nå Jack, på slutten av dagen, sette klærne på venstre når du setter dem bort. Så i morgen tidlig når du se solen, få klærne på høyre, fra slutten av linjen. Ser du ikke? sa Lou. Det blir så fint. Du vil ha alt en gang før du bruker noe to ganger. Og med alt i køer i sitt skap og hylle, Jack begynte å føle ganske sikker på seg selv. All takk til Lou og hans fantastiske køen. SPEAKER 1: Greit, det er søtt. Så hva er egentlig skjer på under panseret nå? At vi har pekere, at vi har malloc, at vi har evnen til å skape biter av minne for oss selv dynamisk. Så dette er et bilde vi skimtes bare den andre dagen. Vi gjorde egentlig ikke dvele på det, men dette bildet har pågått under panseret i flere uker nå. Og så dette representerer, bare et rektangel som vi har trukket, datamaskinens minne. Og kanskje din datamaskin, eller CS50 ID, har en gigabyte minne eller RAM eller to gigabyte eller fire. Det spiller egentlig ingen rolle. Operativsystemet Windows eller Mac OS eller Linux, hovedsak gjør at programmet å tro at det har tilgang til helheten av datamaskinens minne, selv om du kan kjøre flere programmer samtidig. Så i virkeligheten, som ikke egentlig fungerer. Men det er slags en illusjon gitt til alle programmene dine. Så hvis du hadde to gigabyte RAM, dette er hvordan datamaskinen kan tenke på det. 

Nå tilfeldigvis, en av disse ting, en av disse segmentene av minne, kalles en stabel. Og faktisk helst så langt i å skrive kode at du har kalt en funksjon, for eksempel hoved. Husk at hver gang jeg har trukket datamaskinens minne, Jeg har alltid trekke liksom halvdelen av et rektangel her og ikke bry snakker om hva som er ovenfor. Fordi når hoved kalles, hevder jeg at du får denne snev av minne som går ned her. Og hvis hoved kalles en funksjon som swap, vel swap går her. Og det viser seg, det er hvor den ender opp. På noe som kalles en stabel innsiden av datamaskinens minne. Nå ved slutten av dagen, dette er bare adresser. Det er som å byte null, byte en, byte 2 milliarder kroner. Men hvis du tenker på det da dette rektangulært objekt, alt vi gjør hver tid kaller vi en funksjon er lagdeling en ny bit av minne. Vi gir den funksjonen en skive av sin egen hukommelse for å arbeide med. 

Og husker nå at dette er viktig. Fordi hvis vi har noe som swap og to lokale variabler som A og B og vi endre disse verdiene fra en og to til to og en, tilbakekalling at når swap returnerer, det er som om dette stykke minne er bare borte. I virkeligheten er det fortsatt det forensically. Og noe er fortsatt faktisk det. Men konseptuelt, er det som om det er helt borte. Og så hoved ikke kjenner noe av arbeidet som ble gjort i det swap funksjon med mindre det er faktisk vedtatt i de argumenter med pekeren eller ved referanse. Nå har den grunnleggende løsning til det problemet med swap passerer ting på etter adresse. Men det viser seg også, hva som er pågått over at en del av rektangelet hele denne tiden er men det er mer minne der oppe. Og når du dynamisk allokere minne, enten det er innsiden av GetString, som vi har gjort for deg i CS50 bibliotek, eller hvis dere kalle malloc og spør operativsystemet for en del av minne, betyr det ikke kommer fra bunken. Det kommer fra et annet sted i datamaskinens minne som heter haugen. Og det er ikke noe annerledes. Det er det samme RAM. Det er det samme minne. Det er bare RAM som er opp der i stedet for her nede. 

Og så hva betyr det? Vel, hvis datamaskinen har en begrenset mengde minne og stabelen vokser opp, så til å snakke, og haugen, ifølge til denne pilen, vokser ned. Med andre ord, hvert gang du ringer malloc, du blir gitt en skive minne ovenfra, så kanskje litt lavere, så litt lavere, hver gang du ringer malloc, haugen, det er bruk, er slags vokser, voksende nærmere og nærmere til hva? Stabelen. Så betyr dette virke som en god idé? Jeg mener, hvor det er egentlig ikke klar hva annet du kan gjøre hvis du bare har en begrenset mengde minne. Men dette er sikkert dårlig. De to pilene er på en Crash Course for hverandre. 

Og det viser seg at slemmingen, folk som er spesielt bra med programmering, og prøver å hacke inn i datamaskiner, kan utnytte denne virkeligheten. Faktisk, la oss vurdere en liten bit. Så dette er et eksempel du kan lese om nærmere på Wikipedia. Vi vil peke deg på artikkelen hvis nysgjerrig. Men det er et angrep generelt kjent som buffer overflow som har eksistert så lenge som mennesker har hatt muligheten til å manipulere datamaskinens minne, særlig i C. Så dette er en svært vilkårlig program, men la oss lese det fra bunnen opp. Hoved inn argc røye stjerners argv. Så det er et program som tar kommandolinjeargumenter. Og alle de viktigste ikke er tilsynelatende samtale en funksjon, kaller det F for enkelhet. Og det går i det? Argv av en. Så det går over i F uansett ordet er at brukeren har skrevet ved ledeteksten etter programmets navn i det hele tatt. Så mye som Cæsar eller Vigenère, som du kanskje husker gjør med argv. 

Så hva er F? F tar i en streng som eneste argument, AKA en char stjerne, samme ting, som en streng. Og det heter vilkårlig bar i dette eksemplet. Og så char c 12, bare i lekmann vilkår, hva er char c brakett 12 gjør for oss? Hva er det å gjøre? Tildele minne, spesielt 12 byte for 12 chars. Nøyaktig. Og så den siste linjen, rør og kopiere, har du sannsynligvis ikke sett. Dette er en streng kopi funksjon hvis formål i livet er å kopiere sin andre argument inn i sin første argument, men bare opp til en visst antall byte. Så det tredje argumentet sier: hvor mange bytes bør du kopiere? Lengden på bar, hva brukeren skrev inn. Og innholdet bar, som streng, er kopiert inn i minnet pekte på at C. 

Så dette synes slags dum, og det er. Det er en contrived eksempel men det er representative av en klasse av angrepsvektorer, en måte å angripe et program. Alt er fint og bra hvis brukeren typer i et ord som er 11 tegn eller færre, pluss backslash null. Hva om brukeren skriver inn mer enn 11 eller 12 eller 20 eller 50 tegn? Hva er dette programmet kommer til å gjøre? Potensielt SEG feil. Det kommer å blindt kopiere alt i bar opp til dens lengde, som er bokstavelig talt alt i bar, i adresse rettet mot C. Men C har bare preemptively gitt som 12 bytes. Men det er ingen ekstra sjekk. Det er ikke noe om forholdene. Det er ingen feilkontroll her. 

Og så hva dette programmet er kommer til å gjøre er å bare blindt kopiere en ting til den andre. Og så hvis vi trekker dette som et bilde, her bare en snev av plass i minnet. Så legger merke til på bunnen, vi har lokal variabel bar. Slik at pekeren som kommer til å store-- heller at lokale argument som er skal lagre strengen bar. Og deretter legge merke over den i en stabel, fordi hver gang du spør for minne på stakken, det går litt ovenfor det billedlig, merke til at vi har fått 12 bytes der. Øverst til venstre ene er C brakett null og nederst til høyre en er C brakett 11. Det er bare hvordan datamaskinene kommer til å legge den ut. Så bare intuitivt, hvis bar har mer enn 12 tegn totalt, inkludert backslash null, hvor er 12 eller C brakett 12 kommer til å gå? Eller rettere sagt hvor er den 12. karakter eller det 13. tegnet, hundrede karakter kommer å ende opp i bildet? Over eller under? 

Høyre, fordi selv om stakken vokser oppover, når du har satt ting i det, for design grunner, setter minne fra topp til bunn. Så hvis du har mer enn 12 bytes, du kommer til å begynne å overskrive bar. Nå det er en bug, men det er egentlig ikke en stor avtale. Men det er en stor avtale, fordi det er flere ting som skjer i minnet. Så her er hvordan vi kan sette hallo, for å være klar. Hvis jeg skrev i hallo ved ledeteksten. H-E-L-L-O backslash null, ender opp i disse 12 bytes, og vi er super trygg. Alt er bra. Men hvis jeg skriver noe lenger, potensielt det er kommer til å krype inn i bar plass. Men enda verre, viser det ut hele denne tiden, selv om vi aldri har snakket om det er stabelen brukes til andre ting. Det er ikke bare lokale variabler. 

C er et meget lavt nivå språk. Og den slags hemmelighet bruker stabelen også å huske på når en funksjonen kalles, hva adressen er av den foregående funksjon, slik at den kan hoppe tilbake til denne funksjonen. Så når hoved samtaler bytte, blant de tingene presset på stakken er ikke bare bytter lokale variabler, eller sine argumenter, også hemmelighet skjøvet over stabelen som representert ved den røde skive her, er adressen til hoved fysisk i datamaskinens minne, slik at når swap er gjort, datamaskinen vet at jeg trenger å gå tilbake til hoved og avslutt gjennomføre den viktigste funksjonen. Så dette er farlig nå, fordi hvis brukeren skriver i tillegg mer enn hei, slik at brukerens input clobbers eller overskriver den røde delen, logisk hvis datamaskinens bare kommer til å blindt anta at byte i at rødt skive er adressen som det skal returnere, hva om motstanderen er smart nok eller heldig nok til å sette en sekvens av bytes Det som ser ut som en adresse, men det er adressen til koden at han eller hun ønsker datamaskinen å kjøre i stedet for hoved? 

Med andre ord, hvis hva brukeren skriver på spørsmål, er ikke bare noe ufarlige som hallo, men det er faktisk kode som er tilsvarende for å slette alle denne brukerens filer? Eller send passordet sitt til meg? Eller starte logging deres tastetrykk, ikke sant? Det er en måte, la oss fastsetter i dag, at de kunne skrive inn ikke bare hallo verden eller deres navn, de kunne hovedsak passere i kode, nuller og seg, at datamaskinen feil for både kode og en adresse. Så riktignok litt abstrakt, hvis brukertyper i nok motstandere kode at vi skal generalisere her som A. A er angrepet eller motstandere. Så bare dårlige ting. Vi bryr oss ikke om tall eller nuller og ettall i dag, slik at du ender opp skrive den røde delen, Legg merke til at sekvens av bytes. O 835 C null åtte null. Og nå som Wikipedias artikkel her har foreslått, hvis du nå faktisk begynner merking av byte i din datamaskin minne, hva Wikipedia-artikkelen er foreslår er det, hva hvis adressen av det øvre venstre byte er 80 C 0 3508. 

Med andre ord, hvis skurken er smart nok med hans eller hennes kode å faktisk sette et tall her at svarer til adressen til kode han eller hun injisert inn i datamaskinen, du kan lure datamaskinen til å gjøre noe. Fjerne filer, e-post ting, sniffing trafikken, bokstavelig talt noe kunne være injiseres inn i datamaskinen. Og så en buffer overflow angrepet i sin kjerne er bare en dum, dum ordnede av en matrise som ikke har sine grenser kontrollert. Og dette er hva som er super farlig og samtidig super kraftig i C er at vi faktisk har adgang til hvor som helst i lageret. Det er opp til oss, programmerere, som skriver den opprinnelige koden å sjekke darn lengden på eventuelle arrays at vi manipulere. Så for å være klar, hva er fix? Hvis vi rulle tilbake til dette kode, skal jeg ikke bare endre lengden på baren, hva annet bør jeg sjekke? Hva annet skal jeg gjøre for å hindre dette angrepet helt? Jeg ønsker ikke å bare blindt si at du bør kopiere så mange bytes som er lengden på bar. Jeg ønsker å si, kopier som mange bytes som er i bar opp til den tilordnede minne, eller 12 maksimalt. Så jeg trenger noen form for hvis tilstanden som gjør sjekke lengden på bar, men dersom den overstiger 12, vi bare vanskelig kode 12 som den maksimalt mulige avstand. Ellers såkalt buffer flow angrep kan skje. På bunnen av disse slides, hvis du er glad i å lese mer er selve opprinnelige artikkelen Hvis du ønsker å ta en titt. 

Men nå, blant de prisene betalt her var ineffektivitet. Så det var en rask lavt nivå titt på hva problemer kan oppstå nå som vi har tilgang til datamaskinens minne. Men et annet problem vi allerede snublet på mandag var bare ineffektivitet av en lenket liste. Vi er tilbake til lineær tid. Vi har ikke lenger en sammenhengende matrise. Vi har ikke tilfeldig tilgang. Vi kan ikke bruke hakeparentes notasjon. Vi har bokstavelig talt å bruke en stund loop som den jeg skrev for et øyeblikk siden. Men på mandag, vi hevdet at vi kan krype tilbake til området for effektivitet å oppnå noe som er logaritmisk kanskje, eller det aller beste, kanskje til og med noe som er såkalt konstant tid. Så hvordan kan vi gjøre det ved hjelp av disse nye verktøy, disse adressene, disse pekere, og threading ting i vår egen? Vel, antar at her, dette er en gjeng av tall som vi ønsker å lagre i en datastruktur og søk effektivt. Vi kan absolutt spole tilbake til uke to, kaste disse inn i en matrise, og søke i dem ved hjelp av binære søk. Splitt og hersk. Og faktisk du skrev binært søk i PSET3, hvor du implementert finne programmet. Men vet du hva. Det er på en måte en mer smart måte å gjøre dette. Det er litt mer sofistikert og det kanskje tillater oss å se hvorfor binære Søket er så mye raskere. Først, la oss introdusere oppfatningen av et tre. Som selv om det i reality trær slags vokse som dette, i verden av datamaskinen vitenskap de slags vokser nedover som et familietre, hvor du har dine besteforeldre eller oldeforeldre eller whatnot på toppen, patriarken og matriarch av familien, bare ett såkalte rot, node, nedenfor som er dens barn, nedenfor som er dets barn, eller sine etterkommere mer generelt. Og noen henging bunnen av familien tre, foruten å være den yngste i familien, kan også bare være generisk kalt bladene på treet. 

Så dette er bare en haug av ord og definisjoner for noe som kalles et tre i datamaskinen vitenskap, mye som et familietre. Men det er mer avansert inkarnasjoner av trær, hvorav kalles et binært søketre. Og du kan slags tease hverandre hva denne tingen gjør. Vel, det er binær i hvilken forstand? Hvor kommer den binære kommer herfra? Sorry? Det er ikke så mye et enten eller. Det er mer at hver av nodene har ingen mer enn to barn, som vi ser her. Generelt, en tree-- og dine foreldre og besteforeldre kan ha så mange barn eller barnebarna som de faktisk ønsker, og så for eksempel der har vi tre barn off at høyre hånd node, men i et binært tre, har en node null, én eller to barn maksimalt. Og det er en fin egenskap, fordi hvis det er avkortet med to, vi kommer til å være i stand til å få en liten tømmer basen to- handlingen foregår her til slutt. Så har vi noe logaritmisk. Men mer om det i et øyeblikk. Søketre betyr at tallene er anordnet slik at den venstre barnets verdien er større enn ved roten. Og sin rett barnet er større enn roten. Med andre ord, hvis du tar noen av de noder, sirklene i dette bildet, og ser på sitt venstre barn og sin rett barnet, det første bør være mindre enn, det andre bør være større enn. Så tilregnelighet sjekk 55. Det er igjen barnet er 33. Det er mindre enn. 55, er det rett barnet 77. Det er større enn. Og det er en rekursiv definisjon. Vi kunne sjekke hver og en av dem noder og det samme mønsteret ville holde. 

Så hva er fint i en binært søketre, er at man kan vi gjennomføre det med en struct, akkurat som dette. Og selv om vi kaster massevis av strukturer på din, de er noe intuitive nå forhåpentligvis. Syntaksen er fortsatt uforståelige sikkert, men innholdet av et knutepunkt i denne context-- og vi holder ved hjelp av ordet node, enten det er et rektangel på skjermen eller en sirkel, det er bare noen generiske container, i dette tilfelle av et tre, slik at en vi så, vi trenger et heltall i hver av nodene og da trenger jeg to pekere peker til venstre barnet og retten barnet, henholdsvis. Så det er hvordan vi kan implementere det i en struct. Og hvordan kan jeg implementere det i koden? Vel, la oss ta en rask se på dette lille eksempelet. Det er ikke funksjonell, men jeg har kopiert og limt den strukturen. Og hvis min funksjon for en binær søketre kalles søk, og dette tar to argumenter, et heltall N og en peker til en node, så en peker til treet eller en peker til roten av et tre, hvordan går jeg om å lete etter N? Vel, først, fordi jeg er arbeider med pekere, Jeg kommer til å gjøre en mental helse sjekk. Hvis tre likeverdige lik null, er N i dette treet eller ikke i dette treet? Det kan ikke være, ikke sant? Hvis jeg er forbi null, det er ingenting der. Jeg kan like godt bare blindt si return false. Hvis du gir meg ingenting, jeg sikkert ikke kan finne en rekke N. Så hva annet jeg kan Sjekk nå? Jeg kommer til å si vel annet hvis N er mindre enn det som er på trenode at jeg har blitt overlevert N verdi. Med andre ord, hvis tallet er jeg leter etter, N, er mindre enn noden som jeg ser på. Og node jeg ser på kalles treet, og husker fra forrige eksempel å få på verdien i en peker, Jeg bruker pilen notasjon. Så hvis N er mindre enn tre pilen N, ønsker jeg å konseptuelt gå venstre. Hvordan kan jeg uttrykke søkingen igjen? For å være klar, hvis dette er bildet i spørsmålet, og jeg har blitt vedtatt at øverste arrow som er peker nedover. Det er mitt tre spisser. Jeg peker på roten av treet. Og jeg ser si, for antall 44, vilkårlig. Er 44 mindre enn eller større enn 55 åpenbart? Så det er mindre enn. Og så dette hvis tilstanden gjelder. Så konseptuelt, hva ønsker jeg å søke neste hvis jeg leter etter 44? Yeah? 

Akkurat, jeg ønsker å søke venstre barnet, eller venstre sub-tre av dette bildet. Og faktisk, la meg gjennom bildet her nede for bare et øyeblikk siden Jeg kan ikke avlyse dette ut. Hvis jeg begynner her på 55, og Jeg vet at verdien 44 Jeg leter etter er å venstre, det er slags som å rive telefonboken i halvparten eller rive treet i to. Jeg har ikke lenger å bry seg om Hele denne halvdelen av treet. Og likevel, merkelig i forhold til struktur, denne tingen over her at starter med 33, som selv er et binært søketre. Jeg sa ordet rekursive før fordi faktisk dette er en datastruktur som per definisjon er rekursivt. Du har kanskje et tre som er denne stor, men hver og en av sine barn representerer et tre bare litt mindre. I stedet for at det blir bestefar eller bestemor, nå er det bare mamma or-- Jeg kan ikke say-- ikke mamma eller far, det ville være rart. I stedet de to barna der ville være som bror og søsken. En ny generasjon av slektstreet. Men strukturelt, er det den samme ideen. Og det viser seg at jeg har en funksjon som jeg kan søke en binær søk treet. Det kalles søk. Jeg søker etter N i treet pil venstre annet hvis N er større enn verdien at jeg er for tiden på. 55 i historien et øyeblikk siden. Jeg har en funksjon som heter søk som jeg kan bare passere N dette og rekursivt søk sub-treet og bare retur uansett hva det svaret. Annet jeg har fått noen endelige base case her. 

Hva er det siste tilfelle? Treet er enten null. Verdien jeg heller leter etter er mindre enn eller større enn det eller lik den. Og jeg kan si lik like, men logisk er det tilsvarer bare si annet her. Så sant er hvordan jeg finner noe. Så forhåpentligvis er dette en enda mer overbevisende eksempel enn den dumme sigma funksjonen vi gjorde noen forelesninger tilbake, hvor det var like enkelt å bruke en løkke å telle opp alle tallene fra én til N. Her med en datastruktur som i seg selv er rekursivt definert og rekursivt trukket, nå er vi har evnen til å uttrykke oss i koden som selv er rekursiv. Så dette er nøyaktig samme kode her. 

Så hva andre problemer kan vi løse? Så en rask steg unna trær for bare et øyeblikk. Her er, sier den tyske flagget. Og det er helt klart en Mønsteret til dette flagget. Og det er massevis av flagg i verden som er så enkelt som dette i form av sine farger og mønstre. Men antar at dette er lagret som en GIF eller JPEG eller bitmap, eller en ping, noe grafisk filformat som du er kjent, noen som vi er spille med i PSET4. Dette virker ikke verdt å lagre svart piksel, svart piksel, svart piksel, prikk, prikk, prikk, en hel haug med svarte piksler for første avsøkningslinje, eller rad, deretter en hel haug med det samme, da en hel haug av de samme, og deretter en hel haug med røde piksler, røde piksler, røde piksler, deretter en hel haug med gule piksler, gul, ikke sant? 

Det er slik ineffektivitet her. Hvordan ville du intuitivt komprimere det tyske flagget hvis implementere det som en fil? Som hva informasjon kan vi ikke bry lagre på disk for å redusere vår filstørrelsen fra lignende en megabyte til en kilobyte, noe mindre? Hvori ligger redundans her å være klar? Hva kan du gjøre? Yeah? Nøyaktig. Hvorfor ikke heller enn å huske fargen på hver darn pixel akkurat som du gjør i PSET4 med bitmap fil format, hvorfor ikke bare representerer lengst til venstre kolonne av bildeelementer, f.eks en haug av svarte piksler, en haug rødt, og en haug med gule, og så bare liksom kode Ideen om gjenta dette 100 ganger eller gjenta dette 1000 ganger? Hvor 100 eller 1000 er bare et tall, så du kan komme unna med bare et enkelt tall istedenfor hundrevis eller tusenvis ekstra piksler. Og ja, det er hvordan vi kunne komprimere den tyske flagget. Og Hva nå om det franske flagget? Og en liten en slags mental trening, som flagg kan komprimeres mer på disken? Den tyske flagg eller fransk flagg, hvis vi tar som tilnærming? Den tyske flagget, fordi det er mer horisontal redundans. Og ved design, mange grafiske fil formater gjør faktisk fungerer som skanningslinjer horisontalt. De kunne arbeide vertikalt, bare menneskelighet besluttet år siden at vi vil vanligvis tenker på ting rad av raden i stedet for en kolonne etter kolonne. Så ja hvis du var å se på filen Størrelsen på en tysk flagg og en fransk flagg, så lenge som oppløsningen er den samme, den samme bredde og høyde, dette en her kommer til å bli større, fordi du må gjenta deg selv tre ganger. Du må spesifisere blå, gjentar selv, hvit, gjentar deg selv, rød, gjenta deg selv. Du kan ikke bare gå hele helt til høyre. Og som en digresjon, for å gjøre tømme komprimering er overalt, hvis disse er fire rammer fra en video-- deg kan huske at en film eller video er vanligvis som 29 eller 30 bilder per sekund. Det er som en liten flip bok hvor du bare se image, image, image, image, image bare super fort så det ser ut som skuespillerne på skjermen beveger seg. Her er en humlen på toppen av en haug med blomster. Og selv om det kan være slags vanskelig å se ved første øyekast, det eneste som beveger seg i denne filmen er bee. 

Hva er dum om lagring video ukomprimert? Det er litt bortkastet å lagre video som fire nesten identiske bilder som skiller seg bare i den utstrekning der bee er. Du kan kaste bort mest av denne informasjonen og husk bare, for eksempel, det første bildet og det siste bildet, nøkkelbilder hvis du har hørt ordet, og bare lagre i midten der bee er. Og du trenger ikke å lagre alle de rosa, og det blå, og den grønne verdier også. Så dette er å bare si at Kompresjonen er overalt. Det er en teknikk vi bruker ofte eller tar for gitt i disse dager. 

Men hvordan komprimere du teksten? Hvordan du går om å komprimere tekst på? Vel, hver av karakterene i Ascii er én byte, eller åtte biter. Og det er slags dum, ikke sant? Fordi du sannsynligvis type A og E og jeg og O og U mye oftere enn som W eller Q eller Z, avhengig av hvilket språk du skriver sikkert. Og så hvorfor bruker vi åtte biter for hver bokstav, inkludert minst populære bokstaver, ikke sant? Hvorfor ikke bruke færre bits for de super populære bokstaver, som E, de tingene du gjette først i Wheel of Fortune, og bruke flere biter for de mindre populære bokstavene? Hvorfor? Fordi vi bare kommer til å bruke dem sjeldnere. 

Vel, det viser seg at det har vært forsøk gjort for å gjøre dette. Og hvis du husker fra klasse skole eller videregående skole, morse. Morse har prikker og streker som kan være sendes langs en wire som lyder eller signaler av noe slag. Men morse er en super clean. Det er litt av en binær system i at du har prikker eller streker. Men hvis du ser, for eksempel, to prikker. Eller hvis du tenker tilbake til operatøren som går som pip, pip, pip, pip, treffer en liten trigger som sender et signal, Hvis du, mottakeren, får to prikker, hva meldingen du har fått? Helt vilkårlig. 

Jeg? Jeg? Eller hva om-- eller jeg? Kanskje var det bare to-E er rett? Så det er dette problemet av decodability med Morse kode, hvorved mindre person å sende deg meldingen faktisk tar en pause slik at du kan sortere på se eller høre hullene mellom bokstavene, det er ikke tilstrekkelig bare å sende en strøm av nuller og enere, eller prikker og streker, fordi det er tvetydighet. E er et enkelt punkt, så hvis du se to prikker eller høre to prikker, kanskje det er to E-eller kanskje det er en I. Så vi trenger et system som er en litt mer avanserte enn som så. Så en mann som heter Huffman år siden kom opp med akkurat dette. Så vi bare skal å ta et raskt blikk hvor trærne er relevante for dette. Anta at dette er noen dum meldingen du vil sende, sammensatt av bare A, B, C er D's og E er, men det er mye redundans her. Det er ikke ment å være engelsk. Det er ikke kryptert. Det er bare en dum melding med mye repetisjon. Så hvis du faktisk regne ut alle A, B, C, i D's, og E er, her frekvensen. 20% av bokstavene er A, 45% av bokstavene er E 's, og tre andre frekvenser. Vi telles opp manuelt og bare gjorde matte. 

Så det viser seg at Huffman, for en tid siden, skjønte det, vet du hva, hvis jeg begynner bygning et tre, eller skog av trær, om du vil, som følger, kan jeg gjøre følgende. Jeg kommer til å gi en node til hver av brevene som jeg bryr meg om og jeg kommer til å lagre innsiden av at node frekvensene som et flyttall verdi, eller du kan bruke det en N, også, men vi vil bare bruke en dupp her. Og algoritme som foreslo han er at du ta denne skogen av enkelt node trær, så super korte trær, og du begynner å koble dem med nye grupper, nye foreldre, hvis du vil. Og du gjør dette ved å velge minste to frekvenser samtidig. Så tok jeg 10% og 10%. Jeg oppretter en ny node. Og jeg kaller den nye noden 20%. 

Hvilke to noder jeg kombinere neste? Det er litt tvetydig. Så det er noen hjørne tilfeller til vurdere, men å holde ting pen, Jeg kommer til å velge 20% - Jeg nå ignorere barn. Jeg kommer til å velge 20% og 15% og tegne to nye kanter. Og nå som to noder kan jeg logisk kombinere? Ignorer alle barna, alle de barnebarn, bare se på røttene nå. Hvilke to noder ikke knytte jeg sammen? Punkt to og 0,35. Så la meg tegne to nye kanter. Og da har jeg bare fått én igjen. Så her er et tre. Og det er blitt trukket bevisst å se hva slags pen, men merker at kantene har også blitt merket null og en. Så alle venstrekantene er null vilkårlig, men konsekvent. Alle de rette kantene er de. 

Og så hva Hoffman foreslått er, Hvis du ønsker å representere en B, i stedet representerer antall 66 som en Ascii som er åtte hele biter, vet du hva, bare butikken mønsteret null, null, null, null, fordi det er den veien fra min treet, Mr. Huffman treet, til bladet fra roten. Hvis du vil lagre en E, derimot, ikke send åtte biter som representerer en E. I stedet sender hva mønster av biter? En. Og hva er fint om dette er at E er den mest populære brev, og du bruker kortest kode for det. Den nest mest populære brev ser ut som det var A. Og så hvor mange biter gjorde han foreslår å bruke for det? Zero, en. 

Og fordi det er iverksatt da dette treet, for nå la meg fastsette det ingen tvetydighet som i Morse kode, fordi alle bokstavene du bryr deg om er ved enden av disse kanter. Så det er bare ett anvendelse av et tre. Dette er-- og jeg skal vinke min hånd på hvordan du kan implementere dette som en C-struktur. Vi trenger bare å kombinere et symbol, som en char, og frekvensen i venstre og høyre. Men la oss se på to- endelige eksempler som du vil bli ganske kjent med etter quiz null i oppgavesettet fem. 

Så det er datastrukturen kjent som en hash table. Og en hash table er slags avkjøle i at den har bøtter. Og antar at det er fire bøtter her, bare fire mellomrom. Her er en kortstokk, og her er klubb, spade, klubb, diamanter, klubb, diamanter, klubb, diamanter, clubs-- slik dette er tilfeldig. Hjerter, hearts-- så jeg er bucketizing alle inngangene her. Og en hash table behov å se på dine innspill, og deretter sette den i en viss plassere basert på hva du ser. Det er en algoritme. Og jeg var bruker en super enkel visuell algoritme. Den vanskeligste delen av som var huske hva bildene var. Og så er det fire totalt ting. 

Nå stabler vokste, som er en bevisst utforming ting her. Men hva annet kan jeg gjøre? Så egentlig her har vi en haug med gamle skoleeksamen bøker. Anta at en haug med elevenes navn er på her. Her er en større hash table. I stedet for fire bøtter, Jeg har, la oss si 26. Og vi ønsker ikke å gå låne 26 ting fra utsiden [? Annenberg?], Så her er fem som representerer A til Z. Og hvis jeg se en student med navn som starter med A, Jeg kommer til å sette hans eller hennes quiz der. Hvis noen begynner med C, der borte, A-- faktisk, ønsker ikke å gjøre det. B går over her. Så jeg har fått A og B og C. Og Nå her er en annen student. Men hvis dette hash table er implementert med en matrise, Jeg er litt skrudd på dette punktet, ikke sant? Jeg slags behov for å sette dette et sted. 

Så en måte jeg kan løse dette er, alt rett, er en travel, B er opptatt, C er opptatt. Jeg kommer til å sette ham i D. Så på først må jeg tilfeldig umiddelbar tilgang til hver av bøtter for studentene. Men nå er det slags baklegns til noe lineær, fordi hvis jeg ønsker å søke etter en person med navn som starter med A, jeg sjekke her. Men hvis dette ikke er A student jeg leter etter, Jeg slags må begynne å sjekke bøtter, fordi det jeg gjorde var liksom lineært undersøke datastrukturen. En dum måte å si bare se for den første tilgjengelige åpning, og satt som en plan B, så å si, eller plan D i dette tilfellet verdien i at plasseringen i stedet. Dette er bare slik at hvis du har fikk 26 steder og ingen studenter med navnet Q eller Z, eller noe sånt at minst du bruker plassen. 

Men vi har allerede sett mer smarte løsninger her, ikke sant? Hva ville du gjøre i stedet hvis du har en kollisjon? Hvis to personer har navnet A, hva ville har vært en smartere eller mer intuitiv løsning enn bare Sette en der D er ment å være? Hvorfor kan jeg ikke bare gå utenfor [? Annenberg?] som malloc, en annen node, sette det her, og deretter sette at en student her. Slik at jeg i hovedsak har noen form for en matrise, eller kanskje mer elegant som vi er begynner å se en lenket liste. 

Og så en hash table er en struktur som kan se ut akkurat som dette, men mer smart, du noe som heter separat kjeding, der en hash table ganske enkelt er en matrise, idet hver av og hvor elementene ikke er et tall, er i seg selv en lenket liste. Slik at du får super rask tilgang bestemmer hvor du skal hash verdien til. Mye som med kort eksempel Jeg gjorde super raske beslutninger. Hjerter går her, diamanter går her. Samme her, går A her, D går her, B går her. Så super rask look-ups, og hvis du tilfeldigvis støter på en sak hvor du har fått kollisjoner, to mennesker med samme navn, vel da du bare begynne å koble dem sammen. Og kanskje du holde dem sortert alfabetisk, kanskje du ikke gjør det. Men minst nå har vi dynamikk. Så på den ene siden har vi superrask konstant tid, og hva slags lineær tid involvert hvis disse lenkede lister begynner å bli litt lang. 

Så denne typen en dum, nerdete spøk år siden. På CS50 hack-a-thon, når elevene sjekke inn, noen TF eller CA hvert år synes det er morsomt å sette opp et skilt som dette, hvor det bare betyr at hvis navnet ditt starter med en A, gå på denne måten. Hvis navnet ditt starter med en B, gå dette-- OK, det er morsomt kanskje senere i semesteret. Men det er en annen måte å gjøre dette, også. Komme tilbake til det. 

Så det er denne strukturen. Og dette er vår siste struktur for i dag, som er noe som kalles en trie. T-R-I-E, hvor det av en eller annen grunn er korte for gjenfinning, men det heter trie. Så en trie er et annet interessant amalgam av mange av disse ideene. Det er et tre, som vi har sett før. Det er ikke et binært søketre. Det er et tre med en rekke barn, men hver av barna i en trie er en matrise. En rekke størrelser, sier, 26 eller kanskje 27 Hvis du ønsker å støtte bindestreksnavn eller apostrofer i folks navn. 

Og så dette er en datastruktur. Og hvis du ser fra toppen til bunn, som hvis du ser på toppen node der, M, er peker til den nest siste tingen der, som deretter A, X, W, E, L, L. Dette er bare en datastruktur som vilkårlig er lagring av folks navn. Og Maxwell er lagret ved bare å følge en sti av array til array til array. Men hva er fantastisk om en trie er at mens en lenket liste, og selv en matrise, det beste vi noen gang har fått er lineær tid eller logaritmisk tid på å lete noen opp. I denne datastruktur av et trie, hvis min datastruktur har ett navn i det og jeg ser for Maxwell, jeg er kommer til å finne ham ganske raskt. Jeg bare ser for M-A-X-W-E-L-L. Om denne datastrukturen, derimot, Hvis N er en million, hvis det er en million navnene i denne datastruktur, Maxwell er fortsatt kommer til å være synlig etter bare M-A-X-W-E-L-L trinn. Og David-- D-A-V-I-D-trinn. Med andre ord, ved å bygge en datastruktur som er har alle disse matriser, som alle seg støtte random access, Jeg kan begynne å se opp folks navngi ved hjelp av en mengde tid det er proporsjonal ikke antallet ting i datastrukturen, som en million eksisterende navnene. Tiden det tar meg å finne M-A-X-W-E-L-L i denne datastruktur er proporsjonal ikke i størrelsen av datastrukturen, men til lengden av navnet. Og realistisk det Navnene vi leter opp aldri kommer til å bli gal lenge. Kanskje noen har en 10 tegn navn, 20 tegn navn. Det er absolutt begrenset, ikke sant? Det er et menneske på jorden som har den lengste mulige navnet men det navnet er en konstant verdi lengde, ikke sant? Det varierer ikke i noen forstand. Så på denne måten, har vi oppnås en datastruktur som er konstant tids look-up. Det tar en rekke tiltak avhengig av lengden av tilførselen men ikke antallet navnet i datastrukturen. Så hvis vi dobler antall navn neste år fra en milliard til to milliarder kroner, funn Maxwell kommer til å ta det samme antall av syv skritt for å finne ham. Og så vi synes å ha oppnådd vår hellige gral av kjøretiden. 

Så et par korte beskjeder. Quiz null kommer opp. Mer om det på kurset hjemmeside i løpet av de neste par dagene. Mandagens lecture-- det er en ferie her ved Harvard på mandag. Det er ikke i New Haven, så vi tar klassen til New Haven for forelesning på mandag. Alt vil bli filmet og streamet live som vanlig, men la oss avslutte i dag med en 30 sekunders klipp kalt "Deep Thoughts" av Daven Farnham, som ble inspirert fjor av lørdag Night Lives "Deep Thoughts" av Jack Handy, som skal nå være fornuftig. 

FILM: Og nå, "Deep Tanker "av Daven Farnham. Hash table. 

SPEAKER 1: Greit, det er det for nå. Vi sees neste uke. 

DOUG: For å se den i aksjon. Så la oss ta en titt på det akkurat nå. Så her har vi en usortert array. 

IAN: Doug, kan du gå videre og starte på nytt dette for bare ett sekund, takk. Greit, er kameraene rulle, så handling når du er klar, Doug, OK? DOUG: Greit, så hva vi har her er en usortert array. Og jeg har farget alle elementene rødt for å angi at det er faktisk usortert. Så husker at det første vi gjør er vi sortere venstre halvdel av tabellen. Da vi sortere riktig halvparten av tabellen. Og ya-da, ya-da, ya-da, vi flette dem sammen. Og vi har en helt sortert array. Så det er sånn flette slags fungerer. 

IAN: Whoa, whoa, whoa, klippe, klippe, klippe, klippe. Doug, kan du ikke bare ya-da, ya-da, ya-da, din vei gjennom merge sort. 

DOUG: Jeg bare gjorde det. Det er i orden. Vi er godt å gå. La oss bare holde rulle. Så uansett, 

IAN: Du må forklare den mer fullstendig enn det. Det er bare ikke nok. DOUG: Ian, gjør vi ikke trenger å gå tilbake til en. Det er i orden. Så uansett, hvis vi fortsetter med merge-- Ian, vi er i midten av filming. 

IAN: Jeg vet. Og vi kan ikke bare ya-da, ya-da, ya-da, gjennom hele prosessen. Du må forklare hvordan to sidene bli slått sammen. 

DOUG: Men vi har allerede forklarte hvordan de to sides-- 

IAN: Du har nettopp vist dem et flette array. DOUG: De kjenner prosessen. De er fine. Vi har gått over det ti ganger. 

IAN: Du bare hoppet rett over den. Vi går tilbake til en, du kan ikke du ya-da, ya-da over det. Greit, tilbake til en. 

DOUG: Jeg må gå tilbake gjennom alle lysbildene? Herregud. Det er som for sjette gang, Ian. Det er i orden. 

IAN: All right. Er du klar? Flott. Handling.