SPEAKER 1: Okay, så dette er CS50 Dette er slutningen af ​​ugen fem. Og minde om, at sidste gang vi begyndte at se på mere avanceret data strukturer, der er begyndt at løse problemer, der begyndte at indføre nye problemer, men nøglen til denne var slags gevindskæring, at vi begyndt at gøre fra knudepunkt til knudepunkt. Så dette er naturligvis en enkelt bundet listen. Og ved enkelt bundet, Jeg mener der er bare en tråd mellem hver af disse knudepunkter. Slår ud kan du gøre mere avanceret ting som dobbelt hægtede lister hvorved du har en pil går i begge retninger, hvilket kan hjælpe med visse effektiviteter. Men dette løst problemet? Hvilket problem har det løse? Hvorfor har vi bekymrer på mandag? Hvorfor i teorien, vi pleje på mandag? Hvad gør den? 

PUBLIKUM: Vi kan dynamisk ændre størrelsen. 

SPEAKER 1: OK, så vi kan dynamisk ændre størrelsen. Godt klaret begge du. Så du kan dynamisk ændre størrelsen dette datastruktur, mens et array, tilbagekaldelse, er du nødt til at kende en priori hvor meget plads du ønsker og hvis du har brug for lidt mere plads, er du slags ude af lykke. Du er nødt til at skabe en helt ny array. Du er nødt til at flytte alle dine data fra den ene til den anden, vinder frigøre den gamle matrix hvis du kan, og derefter gå videre. Som netop føles meget dyrt og meget ineffektive, og faktisk kan det være. Men det er ikke alle gode. Vi betaler en pris, hvad var en af de mere åbenlyse priser, vi betale ved hjælp af en sammenkædet liste? 

PUBLIKUM: Vi er nødt til at bruge dobbelt plads til hver enkelt. SPEAKER 1: Ja, så har vi brug for mindst dobbelt så meget plads. Faktisk indså jeg dette billede er endda en smule vildledende, fordi på CS50 IDE i en masse moderne computere, en pegepind eller en adresse er faktisk ikke fire bytes. Det er meget ofte disse dage otte bytes, der betyder bunden mest rektangler der i virkeligheden er slags dobbelt så store som hvad jeg har tegnet, hvilket betyder, at du bruger tre gange så meget plads, som vi måske har ellers. Nu samtidig er vi stadig taler bytes, ikke? Vi er ikke nødvendigvis taler megabyte eller gigabyte, medmindre disse data strukturer få store. 

Og så i dag vi begynder at overveje hvordan vi kan udforske data mere effektivt, hvis i Faktisk dataene bliver større. Men lad os prøve at canonicalize operationerne første at du kan gøre på disse former for datastrukturer. Så noget som en knyttet liste generelt understøtter operationer kan lide slette, indsætte, og søg. Og hvad mener jeg med det? Det betyder blot, at normalt, hvis folk bruger linket liste, de eller en anden har implementeret funktioner som delete, indsætte, og søg, så du kan rent faktisk gør noget nyttige i forbindelse med datastruktur. Så lad os tage et hurtigt kig på, hvordan vi måske gennemfører nogle kode for en forbundet liste som følger. 

Så dette er blot nogle C-kode, ikke engang et komplet program at jeg virkelig hurtigt pisket op. Det er ikke online i distributionen kode, fordi det vil faktisk ikke køre. Men bemærk jeg har bare med en kommentar sagde, dot dot dot, er der noget der, dot dot dot, noget der. Og lad os bare se på hvad de saftige dele er. Så på linje tre, minde om, at det er nu Vi foreslog at erklære en node sidste tid, en af ​​de rektangulære objekter. Det har en int, som vi vil kalde N, men vi kunne kalde det noget, og derefter en struct node stjerne kaldes næste. Og bare for at være klar, at anden linie på linie seks, hvad er det? Hvad er det gør for os? Fordi det sikkert ser mere kryptiske end vores sædvanlige variable. 

PUBLIKUM: Det gør det flytte over én. 

SPEAKER 1: Det gør det flytte over én. Og for at være mere præcis, det vil gemme adressen knudens, der er beregnet til at være semantisk siden af ​​det, ikke? Så det kommer ikke til at nødvendigvis flytte noget. Det er bare at gå til lagre en værdi, som er vil være adressen af en anden node, og det er derfor, vi har sagt struct node stjerne, stjernen betegner en pointer eller en adresse. OK, så nu, hvis du antager, at vi har denne N til rådighed for os, og lad os antage, at en anden har indsat en hel masse tal i en sammenkædet liste. Og der er forbundet liste er peget på af et tidspunkt en variabel kaldet liste, der er bestået i her som en parameter, hvordan kan jeg gå om linje 14 om gennemførelse søgning? Med andre ord, hvis jeg gennemføre funktion, hvis formål i livet er at tage en int og derefter begyndelsen af ​​en linket liste, der er en pegepind til linkede liste. Ligesom første, som jeg synes David var vores frivillige på mandag, Han pegede på hele linkede liste, det er som om vi passerer David som vores argument her. Hvordan kan vi gå om kørsel denne liste? Tja, det viser sig, at selv om pointere er relativt nye nu for os, vi kan gøre denne relativt ligefremt. 

Jeg har tænkt mig at gå videre og erklære en midlertidig variabel, konventionelt er bare at blive kaldt pointer, eller PTR, men du kan kalde det hvad du vil. Og jeg har tænkt mig at initialisere den til starten af ​​listen. Så du kan slags tænker på dette som mig læreren den anden dag, slags peger på en person blandt vores mennesker som frivillige. Så jeg er en midlertidig variabel, der er bare peger på den samme ting at vores tilfældigvis navngivet volontør David blev også påpege. Nu mens markøren er ikke null, fordi tilbagekaldelse at null er nogle særlige sentinel værdi den afgrænser enden af ​​listen, så mens jeg ikke peger på jorden som vores sidste frivillige var, lad os gå videre og gøre følgende. Hvis pointer-- og nu jeg slags ønsker at gøre, hvad vi gjorde med den studerende structure-- hvis pointer prik ud equals-- snarere Hvis markøren dot N er lig med lig den variable N, den argument, der er blevet vedtaget i, så jeg ønsker at gå videre og sige returnere sandt. Jeg har fundet antallet N indersiden af en af ​​knudepunkterne i min linkede liste. Men prikken ikke længere virker i denne forbindelse, fordi pointer, PTR, er faktisk en pegepind, en adresse, vi faktisk kan vidunderligt bruge endelig et stykke af syntaks den slags mærker intuitiv fornemmelse og faktisk bruge en pil her, hvilket betyder gå fra denne adresse til heltal der i. Så det er meget ens i ånd til dot operatør, men fordi markøren er en pegepind og ikke en egentlig struct selv, vi bare bruge pilen. 

Så hvis den aktuelle node at jeg, midlertidig variabel, am peger på ikke N, hvad ønsker jeg at gøre? Nå, med mine frivillige at vi havde her den anden dag, hvis min første menneske er ikke den, jeg ønsker, og måske den anden menneske ikke den jeg ønsker, og den tredje, jeg nødt til at holde fysisk at flytte. Ligesom hvordan kan jeg gå gennem en liste? Da vi havde en matrix, du bare kunne lide jeg plus plus. Men i dette tilfælde er det tilstrækkeligt at gør pointer, får, pointer, næste. Med andre ord, det næste felt er ligesom alle de venstre hånd at vores frivillige mandag var at bruge til at pege på nogle andre node. Det var deres næste naboer. 

Så hvis jeg ønsker at træde igennem denne liste, Jeg kan ikke bare gøre jeg plus plus længere, Jeg i stedet nødt til at sige I, pointer, der foregår til lige hvad det næste felt er, Det næste felt er, det næste felt er, efter alle disse venstre hånd at vi havde på scenen peger til nogle efterfølgende værdier. Og hvis jeg kommer igennem at hele iteration, og endelig, jeg ramte null ikke at have fundet N endnu, jeg bare return false. Så igen, alt, hvad vi laver her, som pr billedet et øjeblik siden, starter ved at pege på starten af ​​listen formentlig. Og så vil jeg tjekke, er værdien Jeg leder efter lig med ni? Hvis ja, jeg vender tilbage sandt og jeg er færdig. Hvis ikke, jeg opdatere min hånd, AKA pointer, at pege ved pilen næste beliggenhed, og derefter den næste pil beliggenhed, og den næste. Jeg blot at gå gennem denne array. 

Så igen, hvem bekymrer sig? Ligesom hvad er dette en ingrediens for? Nå, minde om, at vi introducerede begrebet en stak, som er en abstrakt data skrive det omfang det er ikke en C-ting, det er ikke en CS50 ting, Det er en abstrakt idé, denne idé om stabling ting oven på hinanden der kan gennemføres i bundter af forskellige måder. Og en måde, vi foreslog var med et array, eller med en sammenkædet liste. Og det viser sig, at canonically, en stakken understøtter mindst to operationer. Og brummer ord er skub, til skubbe noget på stakken, som en ny bakke i spisesal, eller pop, hvilket betyder at fjerne den øverste bakke fra stakken i spisesalen hallen, og så måske nogle andre operationer som godt. Så hvordan kan vi definerer strukturen at vi nu kalder en stak? 

Tja, vi har alle de nødvendige syntaks til vores rådighed i C. Jeg siger, give mig en type definition af en struct inde i en stak, Jeg har tænkt mig at sige, er et array, en hel masse tal, og derefter størrelse. Så med andre ord, hvis jeg vil at gennemføre denne i kode, lad mig gå, og bare lidt tegne, hvad det siger. Så dette siger, giv mig et struktur, der har fået et array, og jeg ved ikke, hvad kapacitet er, Det er tilsyneladende nogle konstant at jeg har defineret andetsteds, og det er fint. Men formoder, det er bare en, to, tre, fire, fem. Så kapacitet er 5. Dette element inde i min struktur vil blive kaldt numre. Og så er jeg har brug for en anden variabel tilsyneladende kaldet størrelse, der oprindeligt jeg har tænkt mig at fastsætte initialiseres til nul. Hvis der ikke er noget i stakken, størrelse er nul, og det er skrald værdier i antal. Jeg har ingen idé om, hvad der er derinde endnu. 

Så hvis jeg ønsker at presse noget på stakken, formoder jeg kalder funktionen skubbe, og Jeg siger skubbe 50, ligesom antallet 50, hvor ville du foreslå, Jeg trækker det i dette array? Der er fem forskellige mulige svar. Hvor vil du skubbe nummer 50? Hvis målet her, igen, så ring til funktion skubbe, passere i et argument 50, hvor skal jeg sætte det? Fem possible-- 20% chance for at gætte rigtigt. Ja? 

PUBLIKUM: Yderst til højre. 

SPEAKER 1: Yderst til højre. Der er nu en 25% chance for at gætte rigtigt. Så det ville faktisk være fint. Ved konvention, vil jeg sige med et array, Vi vil generelt begynde til venstre, men vi kunne sikkert starter til højre. Så spoiler her ville være jeg er sandsynligvis kommer til at trække det til venstre, ligesom i en normal vifte hvor Jeg begynder at gå venstre til højre. Men hvis du kan bladre det aritmetiske, fint. Det er bare ikke konventionelle. OK, jeg har brug for at lave en mere forandring selv. Nu, hvor jeg har skubbet noget på stakken, hvad det næste? 

Okay, jeg er nødt til at forøge størrelsen. Så lad mig gå videre og bare opdatere denne, som var nul. Og i stedet nu, jeg har tænkt mig at sætte i værdien én. Og nu tror jeg skubber en anden nummer på stakken, ligesom 51. Tja, jeg er nødt til at gøre en mere ændring, som er op til størrelsen to. Og vel så jeg skubber endnu nummeret på stakken som 61, nu har jeg brug for at opdatere størrelse endnu tid, og få værdien 3 som størrelsen. Og nu tror jeg kalder pop. Nu pop, efter sædvane, tager ikke et argument. Med en stak, hele punkt af bakken metafor er, at du ikke har diskretion gå få at bakke, kan alt du skal gøre er pop øverste en fra stakken, bare fordi. Det er, hvad disse data struktur gør. 

Så ved denne logik, hvis jeg siger pop, hvad der kommer ud? Så 61. Så hvad der virkelig er computeren vil gøre i hukommelsen? Hvad min kode skal gøre? Hvad ville du foreslå, vi ændre på skærmen? Hvad skal ændres? Undskyld? Så vi slippe af med 61. Så jeg kan helt sikkert gøre det. Og jeg kan slippe af med 61. Og hvad andre så Ændringen skal ske? Størrelse formentlig har at gå tilbage til to. Og så det er fint. Men vent et øjeblik, størrelse et øjeblik siden var tre. Lad os bare gøre en hurtig tilregnelighed check. Hvordan vidste vi, at vi ønskede at slippe af med 61? Fordi vi er popping. Og så jeg har denne anden ejendom størrelse. 

Vent et øjeblik, jeg er tænker tilbage til uge to da vi begyndte at tale om arrays, hvor dette var placering nul, dette var placering én, var dette sted to, dette er placering tre, fire, det ligner det forholdet mellem størrelse og det element, jeg vil fjerne fra arrayet synes at bare være hvad? Størrelse minus en. Og så det er sådan som mennesker vi ved 61 kommer først. Hvordan er computeren kommer til at vide? Når din kode, hvor du sandsynligvis ønsker at gøre størrelsen minus én, så tre minus en er to, og at betyder, at vi ønsker at slippe af med 61. Og så kan vi faktisk opdatere størrelsen så størrelse nu går fra tre til kun to. Og bare for at være pedantisk, jeg vil at foreslå, at jeg er færdig, ikke? Du foreslog intuitivt korrekt jeg skulle slippe af med 61. Men har ikke jeg slags slags sluppet af 61? Jeg har faktisk glemt at det faktisk er der. Og tænker tilbage på PSET4, hvis du har læst artiklen om retsvidenskab, PDF at vi havde jer læse, eller du vil læse denne uge for PSET4. Husk på, at dette er faktisk relevant for hele ideen om computer forensics. Hvad en computer generelt gør, er det bare glemmer, hvor noget er, men det går ikke ind og ligesom forsøge at ridse den ud eller overstyring disse bit med nuller og ettaller eller en anden tilfældigt mønster medmindre du selv gør det med vilje. Så din intuition var Okay, lad os slippe af med 61. Men i virkeligheden, behøver vi ikke at gider. Vi skal bare glemme, at det er der ved at ændre vores størrelse. 

Nu er der et problem med denne stak. Hvis jeg holde skubbe tingene på stakken, hvad er selvfølgelig kommer til at ske på blot et par øjeblikke tid? Vi kommer til at løbe tør for plads. Og hvad gør vi? Vi er slags skruet. Denne gennemførelse ikke lade os ændre størrelsen på array, fordi hjælp denne syntaks, hvis du tænke tilbage til uge to, når du har erklæret størrelsen af ​​et array, Vi har ikke set en mekanisme endnu hvor du kan ændre størrelsen af ​​array. Og faktisk C ikke har denne funktion. Hvis du siger give mig fem Nths, kalder dem numre, det er alt du vil få det. Så vi gør nu, som mandag den have evnen til at udtrykke en opløsning selv om, vi bare nødt til at nappe definitionen af ​​vores stack ikke være nogle hårdkodet array, men blot at lagre en adresse. 

Nu, hvorfor er dette? Nu er vi bare nødt til at være fortrolig med det faktum, at når mit program kører, Jeg formentlig vil nødt til at spørge de menneskelige, hvor mange numre vil du gemme? Så input skal komme fra et sted. Men når jeg ved, at nummer, så jeg kan bare bruge hvilken funktion at give mig en luns af hukommelse? Jeg kan bruge malloc. Og jeg kan sige et vilkårligt antal bytes Jeg vil tilbage til disse Nths. Og alt jeg har at gemme i numrene variabel her inde i denne struct bør være hvad? Hvad der rent faktisk går ind i numre i dette scenario? Ja, en pointer til den første byte af denne klump hukommelse, eller mere specifikt, adressen den første af disse bytes. Betyder ikke noget, hvis det er en byte eller en milliard bytes, Jeg har bare brug for at bekymre sig om den første. For hvad malloc garantier og mit operativsystem garantier, er, at bid af hukommelses I får, går det at være sammenhængende. Der kommer ikke til at være huller. Så hvis jeg har bedt om 50 byte eller 1.000 bytes, de er alle kommer til at være tilbage til tilbage til tilbage. Og så længe jeg kan huske, hvor stor, hvordan meget jeg bad om, alt hvad jeg behøver at vide er den første adresse. 

Så nu har vi mulighed i kode. Omend, det vil tage os mere tid til at skrive dette op, Vi kunne nu omfordele at hukommelsen ved bare lagring af en anden adresse der hvis vi ønsker en større eller endda en mindre bid af hukommelse. Så her til en afvejning. Nu får vi dynamik. Vi har stadig contiguousness Jeg påstår. Fordi malloc vil give os en sammenhængende klump hukommelse. Men det vil være en smerte i halsen for os, programmøren, faktisk at kode. Det er bare mere arbejde. Vi har brug for kode beslægtet med, hvad jeg var hamrer ud bare for et øjeblik siden. Meget gennemførligt, men det tilføjer kompleksitet. Og så udvikler tid, programmør tid er endnu en ressource at vi måske nødt til at tilbringe nogen tid at få nye funktioner. Og så selvfølgelig er der en kø. Vi vil ikke gå ind i denne en i mange detaljer. Men det er meget ens i ånd. Jeg kunne implementere en kø, og dens tilsvarende operationer, Sæt i kø eller dequeue, ligesom tilføje eller fjerne, det er bare en amatør måde at sige det, Sæt i kø eller dequeue, som følger. Jeg kan bare give mig selv en struct det igen har en række s array, det igen har en størrelse, men hvorfor gør jeg nu brug at holde styr på forsiden af ​​en kø? Jeg behøvede ikke at vide forsiden af ​​min stak. Tja, hvis jeg igen til en queue-- lad os bare hårdt kode det som at have ligesom fem heltal i her potentielt. Så det er nul, en, to, tre, fire. Dette vil være kaldte numre igen. Og det vil blive kaldt størrelse. 

Hvorfor er det ikke tilstrækkeligt at have bare størrelse? Nå, lad os skubbe de samme numre på. Så jeg pushed-- jeg kø, eller skubbes. Nu vil jeg enqueue 50, og derefter 51, og så 61, og dot dot dot. Så det er enqueue. I kø 50, derefter 51, derefter 61. Og der ser identiske til en stabel hidtil, bortset fra at jeg har brug for at lave en ændring. Jeg har brug for at opdatere denne størrelse, så jeg går fra nul til én til to til tre nu. Hvordan kan jeg dequeue? Hvad sker der med dequeue? Hvem skal komme ud denne liste først hvis det er den linje på Apple Store? Så 50. Så det er lidt tricky denne gang. Hvorimod sidste gang det var super let at bare gøre størrelse minus én, Jeg kommer til slutningen af ​​min matrix effektivt hvor tallene er, det fjerner 61. Men jeg ønsker ikke at fjerne 61. Jeg ønsker at tage 50, som var der kl 5:00 at line op til nye iPhone eller whatnot. Og så for at slippe af med 50, jeg kan ikke bare gøre det, ikke? Jeg kan krydse ud 50. Men vi sagde bare vi behøver ikke at være så anal at ridse ud eller skjule data. Vi kan bare glemme, hvor det er. 

Men hvis jeg ændre min størrelse nu til to, er det tilstrækkelig information at vide, hvad der foregår i mit kø? Ikke rigtig. Ligesom min størrelse er to, men hvor er køen begynder, især hvis jeg stadig har de samme numre i hukommelsen. 50, 51, 61. Så jeg har brug for at huske nu hvor fronten er. Og så jeg foreslog op der, vil vi lige har kaldt N'te foran, hvis oprindelige værdi skulle have været hvad? Zero, blot begyndelsen på listen. Men nu foruden decrementing størrelse, vi bare forøge foran. Nu her er et andet problem. Så når jeg holde. Formoder, at dette er antallet af ligesom 121, 124, og derefter, for fanden, Jeg er ude af rummet. Men vent et øjeblik, jeg er ikke. Så på dette punkt i historien, Antag, at størrelsen er en, to, tre, fire, så formode, at størrelse er fire, foran er en, så 51 er på forsiden. Jeg ønsker at sætte et andet nummer her, men, for fanden, jeg er ude af rummet. Men jeg er ikke rigtig, vel? Hvor kunne jeg sætte nogle yderligere værdi, ligesom 171? Ja, jeg kunne bare lidt gå tilbage derovre, ikke? Og derefter krydse ud 50, eller bare overskrive den med 171. Og hvis du undrer dig over, hvorfor vores tal fik så tilfældig, disse er almindeligt taget computer videnskab kurser på Harvard efter CS50. Men det var en god optimering, fordi nu er jeg ikke spilde plads. Jeg har stadig til at huske hvor stor denne ting er total. Det er fem i alt. Fordi jeg ønsker ikke at begynde at overskrive 51. Så nu er jeg stadig tør for plads, så det samme problem som før. Men du kan se, hvor nu i din kode, har du sandsynligvis nødt til at skrive lidt mere kompleksitet at gøre det ske. Og i virkeligheden, hvad operatør i C formentlig lader du magisk gøre dette cirkularitet? Ja modulo operatør, procenttegnet. Så hvad er slags cool om en kø, selv om vi holder tegning arrays da disse som lige linjer, hvis du slags tænker over dette som krumning rundt som en cirkel, så bare intuitivt den slags virker mentalt Jeg tror lidt mere rent. Du vil stadig nødt til at gennemføre at mental model i kode. Så ikke så svært, i sidste ende, at gennemføre, men vi stadig tabe den size-- snarere, det evne til at ændre størrelse, medmindre vi gør dette. 

Vi er nødt til at slippe af array, vi erstatte det med en enkelt pointer, og så et eller andet sted i min kode jeg har fået et opkald hvilken funktion til rent faktisk at skabe array kaldte numre? Malloc eller en lignende funktion, nøjagtigt. Eventuelle spørgsmål om stakke eller køer. Ja? Godt spørgsmål. Hvad modulo ville du bruge her. Så i almindelighed, når der anvendes mod, ville du gøre det med størrelsen af Hele datastruktur. Så noget som fem eller kapacitet, hvis det er konstant, er sandsynligvis involveret. Men bare gør modulo fem sandsynligvis ikke er tilstrækkelig, fordi vi har brug for at vide at gøre vi wrap omkring her eller her eller her. Så du er sikkert også vil ønsker at involvere størrelsen af ​​ting, eller den forreste variable samt. Så det er bare denne relativt simpelt aritmetisk udtryk, men modulo ville være den vigtigste ingrediens. 

Så kortfilm, hvis du vil. En animation, at nogle folk på et andet universitet sat sammen, at vi har tilpasset til denne diskussion. Det indebærer Jack lære fakta om køer og statistik. 

FILM: Engang, der var en fyr ved navn Jack. Da det kom til at få venner, Jack havde ikke en evne. Så Jack gik til at tale med mest populære fyr vidste han. Han gik til Lou og spurgte, hvad gør jeg? Lou så, at hans ven var virkelig bedrøvet. Nå, begyndte han, bare se, hvordan du er klædt. Har du ikke noget tøj med et andet udseende? Ja, sagde Jack. Jeg sikker gør. Kom til mit hus og Jeg vil vise dem til dig. Så de gik ud til Jack. Og Jack viste Lou kassen hvor han holdt alle hans skjorter, og hans bukser, og hans sokker. Lou sagde, jeg ser du har alt dit tøj i en bunke. Hvorfor tager du ikke bære nogle andre en gang i et stykke tid? 

Jack sagde, godt, når jeg Fjern tøj og sokker, Jeg vasker dem og sætte dem væk i kassen. Derefter kommer den næste morgenen, og op jeg hoppe. Jeg går til kassen og få mit tøj fra toppen. Lou indså hurtigt problemet med Jack. Han holdt tøj, cd'er, og bøger i stakken. Da han nåede til noget at læse eller at bære, han ville vælge den øverste bog eller undertøj. Så da han var færdig, han ville sætte det højre back. Tilbage det ville gå, på toppen af ​​stakken. Jeg kender løsningen, sagde en triumferende Loud. Du er nødt til at lære at begynde at bruge en kø. Lou tog Jack tøj og hang dem i skabet. Og da han havde tømt kassen, han bare smed det. 

Så sagde han, nu Jack, i slutningen af dagen, sætte dit tøj til venstre når du lægger dem væk. Så i morgen tidlig, når du se solskin, får dit tøj til højre, fra slutningen af ​​linjen. Kan du ikke se? sagde Lou. Det vil være så rart. Du vil bære alt en gang før du bære noget to gange. Og med alt i kø i hans skab og hylde, Jack begyndte at føle helt sikker på sig selv. Alle takket være Lou og hans vidunderlige kø. SPEAKER 1: Okay, det er bedårende. Så hvad der er blevet virkelig foregår på under kølerhjelmen nu? At vi har pointere, at vi har malloc, at vi har evnen til at skabe bidder af hukommelse til os dynamisk. Så dette er et billede, vi skimtes lige den anden dag. Vi har ikke rigtig dvæle på det, men dette billede har stået på undersiden hætten i uger nu. Og så dette repræsenterer, bare et rektangel, som vi har tegnet, computerens hukommelse. Og måske din computer eller CS50 Id, har en gigabyte hukommelse eller RAM eller to gigabyte eller fire. Det gør ikke rigtig noget. Dit operativsystem Windows eller Mac OS eller Linux, væsentlige giver dit program at tro, at den har adgang til hele computerens hukommelse, selvom du måske køre flere programmer på én gang. Så i virkeligheden, er der ikke rigtig fungere. Men det er sådan en illusion givet til alle dine programmer. Så hvis du havde to koncerter RAM, dette er, hvordan computeren kan tænke på det. 

Nu tilfældigvis, en af ​​disse ting, en af ​​disse segmenter af hukommelse, kaldes en stabel. Og faktisk enhver tid hidtil skriftligt kode at du har kaldt en funktion, for eksempel main. Husk på, at enhver tid jeg har trukket computerens hukommelse, Jeg har altid trækker slags halvdelen af ​​et rektangel her og ikke gider at tale om hvad der er ovenfor. For når vigtigste kaldes, hævder jeg at du får denne splint af hukommelse der går ned her. Og hvis vigtigste kaldes en funktion Ligesom swap, godt swap går her. Og det viser sig, det er hvor det ender. På noget, der hedder en stak indersiden af ​​computerens hukommelse. Nu ved slutningen af ​​dagen, dette er blot adresser. Det er ligesom byte nul, byte én byte 2 mia. Men hvis du tænker over det da dette rektangulære objekt, alt, hvad vi laver hver gang vi kalder en funktion er lagdeling en ny skive hukommelse. Vi giver denne funktion en skive af sin egen hukommelse at arbejde med. 

Og huske nu, at dette er vigtigt. For hvis vi har noget som swap og to lokale variabler som A og B og vi ændre disse værdier fra et og to til to og en, tilbagekaldelse at når swap vender tilbage, det er som om denne skive hukommelse er lige gået. I virkeligheden, er det stadig der retsmedicinsk. Og noget er stadig faktisk er der. Men begrebsmæssigt, er det så selvom det er helt væk. Og så main kender ikke nogen af ​​arbejdet der blev gjort i denne swap funktion, medmindre det faktisk er gået i dem argumenter ved pointer eller ved henvisning. Nu er den grundlæggende løsning på dette problem med swap passerer ting efter adresse. Men det viser sig også, hvad der er stået på ovenstående den del af rektanglet al denne tid er men der er mere hukommelse deroppe. Og når du dynamisk allokere hukommelse, uanset om det er inde i getString, som vi har gjort for dig i CS50 bibliotek, eller hvis du fyre kalder malloc og spørge Operativsystemet for en luns af hukommelse, betyder det ikke kommer fra stakken. Det kommer fra et andet sted i computerens hukommelse der hedder bunke. Og det er ikke anderledes. Det er den samme RAM. Det er den samme hukommelse. Det er bare den RAM, der er op der i stedet for hernede. 

Og så hvad betyder det? Tja, hvis din computer har en begrænset mængde hukommelse og stakken vokser op, så til at tale, og den bunke, i henhold til denne pil, vokser ned. Med andre ord, hver gang du kalder malloc, du får en skive hukommelse ovenfra, så måske en smule lavere, så lidt lavere, hver gang du kalder malloc, den bunke, det er skik, er slags vokser, vokser tættere og tættere på hvad? Stakken. Så betyder det synes som en god idé? Jeg mener, hvor det er egentlig ikke klar hvad du kan gøre, hvis du kun har en begrænset mængde hukommelse. Men det er helt sikkert dårligt. Disse to pile er på en lynkursus for hinanden. 

Og det viser sig, at dårlige fyr, folk, der er særligt godt med programmering, og forsøger at hacke sig ind computere, kan udnytte denne virkelighed. Faktisk lad os overveje lidt uddrag. Så dette er et eksempel kan du læse om nærmere på Wikipedia. Vi vil pege dig i hvis nysgerrige artiklen. Men der er et angreb generelt kendt som buffer overflow, der har eksisteret så længe mennesker har haft evnen til at manipulere computerens hukommelse, især i C. Så det er en meget vilkårlig program, men lad os læse det op fra bunden. Main ind argC char stjerne argv. Så det er et program, der tager kommandolinjeargumenter. Og alle vigtigste er tilsyneladende opkald en funktion, kalder det F for enkelhed. Og det passerer i hvad? Argv for én. Så det passerer ind F uanset ordet er, at brugeren har indtastet ved prompten efter programmets navn på alle. Så meget gerne Cæsar eller Vigenere, som du måske huske at gøre med argv. 

Så hvad er F? F tager i en streng som sit eneste argument, AKA en char stjerne, samme ting, som en streng. Og det hedder vilkårligt bar i dette eksempel. Og så char c 12, bare i lægmandssprog, hvad der er char c beslag 12 gør for os? Hvad er det så? Allokering hukommelse, specielt 12 bytes for 12 tegn. Præcis. Og så den sidste linje, rør rundt og kopi, har du sikkert ikke set. Dette er en streng kopi funktion, hvis formål i livet er at kopiere sit andet argument i sin første argument, men kun op til et række bytes. Så den tredje argument siger, hvor mange bytes skal du kopierer? Længden af ​​bar, hvad brugeren har skrevet i. Og indholdet af bar, at streng, er kopieres i hukommelsen pegede på ved C. 

Så det synes slags dumme, og det er. Det er en konstrueret eksempel, men det er repræsentativt af en klasse af angrebsvektorer, en måde at angribe et program. Alt er fint og godt, hvis brugeren typer i et ord, der er 11 tegn eller færre, plus backslash nul. Hvad hvis brugeren skriver i mere end 11 eller 12 eller 20 eller 50 tegn? Hvad er dette program kommer til at gøre? Potentielt seg fejl. Det kommer til blindt at kopiere alt i baren op dens længde, som er bogstaveligt talt alt i baren, i adressefeltet pegede på C. Men C har kun givet som forebyggende 12 bytes. Men der er ingen yderligere kontrol. Der er ingen, hvis forholdene. Der er ingen fejlkontrol her. 

Og så hvad dette program er kommer til at gøre, er bare blindt kopiere en ting til den anden. Og så hvis vi trækker denne som et billede, her er blot en splint af hukommelsesplads. Så meddelelse nederst, vi have den lokale variable bar. Så pointer, der kommer til store-- snarere, at lokale argument, der er skal opbevares strengen bar. Og så opdager bare over den i en stabel, fordi hver gang du spørger til hukommelsen på stakken, det går lidt over det billedligt, varsel, at vi har fået 12 byte der. Den øverste venstre ene er C beslag nul og nederst til højre man er C beslag 11. Det er bare, hvordan computerne kommer til at lægge det ud. Så bare intuitivt, hvis bar har mere end 12 tegn i alt, herunder det omvendt skråstreg nul, hvor er den 12 eller C beslag 12 kommer til at gå? Eller rettere hvor er det 12. tegn eller det 13. tegn, den hundrededel karakter går at ende i billedet? Over eller under? 

Ret, fordi selvom stakken selv vokser opad, når du har lagt ting i det, det konstruktionsmæssige grunde sætter hukommelsen fra top til bund. Så hvis du har fået mere end 12 bytes, du vil begynde at overskrive bar. Nu, er en fejl, men det er ikke virkelig en big deal. Men det er en big deal, fordi der er flere ting foregår i hukommelsen. Så her er hvordan vi kan sætte hej, skal være klar. Hvis jeg har skrevet i goddag ved prompten. H-E-L-L-O skråstreg nul, ender inden de 12 bytes, og vi er super sikker. Alt er godt. Men hvis jeg skriver noget længere, er det potentielt kommer til at snige sig ind bar plads. Men værre endnu, viser det sig ud al denne tid, selv om vi aldrig har talt om det bliver stakken bruges til andre ting. Det er ikke bare lokale variable. 

C er et meget lavt niveau sprog. Og det slags hemmeligt bruger stablen også at huske, når en funktion kaldes, hvad adressen af ​​den tidligere funktion, så det kan springe tilbage til denne funktion. Så når vigtigste opkald bytte, blandt de ting skubbet på stakken er ikke bare swaps lokale variable, eller sine argumenter, også hemmeligt skubbet på stakken som vist ved den røde skive her, er adressen på vigtigste fysisk i computerens hukommelse, således at når swap er gjort, computeren kender jeg nødt til at gå tilbage til hovedsiden og slut udfører den primære funktion. Så det er farligt nu, fordi hvis brugeren skriver i godt mere end goddag, således at brugerens input clobbers eller overskriver at rød sektion, logisk, hvis computerens bare gå til blindt antage at de bytes i den røde skive er den adresse, hvortil den skal returnere, hvad hvis modstanderen er smart nok eller heldig nok til at sætte en sekvens af bytes der, der ligner en adresse, men det er adressen på koden at han eller hun ønsker computeren til at udføre i stedet for main? 

Med andre ord, hvis det, bruger er at skrive ved prompten, er ikke bare noget uskadeligt ligesom goddag, men det er faktisk kode, der er tilsvarende at slette alle denne brugers filer? Eller email deres adgangskode til mig? Eller begynde at logge deres tastetryk, right? Der er en måde, lad os fastsætte dag, at de kunne skrive i ikke bare hej verden eller deres navn, de kunne i det væsentlige passere i kode, nuller og dem, at computeren fejltagelser for både kode og en adresse. Så omend lidt abstrakt, hvis brugertyper i nok kontradiktorisk kode at vi vil generalisere her som A. A er angreb eller modstandere. Så bare dårlige ting. Vi er ligeglade med om tal eller nuller eller dem i dag, sådan at du ender overskrive den røde sektion, Bemærk, at sekvensen af ​​bytes. O 835 C nul otte nul. Og nu da Wikipedias artikel her har foreslået, hvis du rent faktisk nu begynde mærkning af bytes i computerens hukommelse, hvad Wikipedia-artikel er foreslår, er, at, hvad hvis adressen af, at den øverste venstre byte er 80 C 0 3508. 

Med andre ord, hvis den dårlige fyr er smart nok med hans eller hendes kode faktisk løber nummeret her som svarer til adressen på koden han eller hun injiceret i computeren, du kan narre computeren til at gøre noget. Fjernelse af filer, e-mail ting, sniffing din trafik, bogstaveligt talt noget kunne være sprøjtes ind i computeren. Og så en buffer overflow angreb på sin kerne er bare en dum, dum altoverskyggende af et array, der havde ikke sine grænser kontrolleret. Og det er det, er super farlig og samtidig super stærk i C er, at vi faktisk har adgang til alle steder i hukommelsen. Det er op til os, de programmører, der skriver den oprindelige kode at kontrollere darn længden af ​​en eventuel arrays, at vi manipulerer. Så for at være klar, hvad er fix? Hvis vi ruller tilbage til denne kode, jeg skal ikke bare ændre længden af ​​linjen, hvilket ellers skal jeg være kontrol? Hvad skal jeg gøre for at forhindre dette angreb helt? Jeg ønsker ikke at bare blindt sige at du skal kopiere så mange bytes som er længden af ​​linjen. Jeg vil gerne sige, at kopiere som mange bytes som er i bar op til den tildelte hukommelse, eller 12 maksimalt. Så jeg har brug for en form for hvis betingelse der gør kontrollere længden af ​​baren, men hvis den overstiger 12, vi bare hårdt kode 12 som den maksimale mulige afstand. Ellers såkaldte puffer overflow angreb kan ske. I bunden af ​​disse objektglas, Hvis du er nysgerrig for at læse mere er den faktiske oprindelige artikel Hvis du gerne vil tage et kig. 

Men nu, blandt de priser betalt her var ineffektivitet. Så det var en hurtig lavt niveau kig på, hvad problemer kan opstå nu, at vi har adgang til computerens hukommelse. Men et andet problem, vi allerede snublede på mandag var bare den ineffektivitet en sammenkædet liste. Vi er tilbage til lineær tid. Vi har ikke længere en sammenhængende array. Vi har ikke random access. Vi kan ikke bruge firkantede beslag notation. Vi bogstaveligt talt nødt til at bruge en while-løkke som den jeg skrev for et øjeblik siden. Men på mandag, vi påstod, at vi kan krybe tilbage i realm af effektivitet opnå noget, der er logaritmisk måske, eller bedste endnu, måske endda noget, der er såkaldte konstant tid. Så hvordan kan vi gøre det ved hjælp af disse nye værktøj, disse adresser, disse pejlemærker, og gevindskæring ting i vores eget? Nå, formoder, at her, disse er en flok af numre, som vi ønsker at gemme i et datastruktur og søge effektivt. Vi kan absolut tilbage til uge to, smid dem i et array, og søg dem ved hjælp af binær søgning. Opdel og erobre. Og i virkeligheden, du skrev søgning binære i PSET3, hvor du implementeret finde programmet. Men ved du hvad. Der er sådan en mere smart måde at gøre det på. Det er lidt mere sofistikeret og det måske tillader os at se, hvorfor binær søgning er så meget hurtigere. Først, lad os indføre begrebet et træ. Hvilket skønt i reality træer slags vokser som denne, i en verden af ​​computeren videnskaben, de form for bliver nedadgående ligesom et stamtræ, hvor du har dine bedsteforældre eller oldeforældre eller whatnot i toppen, patriarken og matriarch af familien, bare én såkaldte rod, node, nedenfor som er dens børn, under hvilken er dens børn, eller sine efterkommere mere generelt. Og enhver hængende bunden af ​​familien træ, ud over at være yngste i familien, kan også bare være generisk kaldes bladene af træet. 

Så dette er bare en flok af ord og definitioner til noget, der hedder et træ i computer videnskab, meget gerne et stamtræ. Men der er mere avanceret inkarnationer træer, hvoraf den ene kaldes en binær søgning træ. Og du kan slags drille fra hinanden, hvad denne ting gør. Tja, det er binære i hvilken forstand? Hvor kommer den binære kommer herfra? Undskyld? Det er ikke så meget et enten eller. Det er mere, at hver af knudepunkterne har nogen mere end to børn, som vi ser her. Generelt er en tree-- og dine forældre og bedsteforældre kan have så mange børn eller børnebørnene, som de rent faktisk ønsker, og så for eksempel der har vi tre børn det højre hånd knude, men i et binært træ, en knude har nul, en eller to børn maksimalt. Og det er en nice egenskab, fordi hvis det er udjævnet med to, vi vil være i stand til få en lille log bund to handling foregår her i sidste ende. Så vi har noget logaritmisk. Men mere om det i et øjeblik. Søgetræet betyder, at tallene er anbragt således, at venstre barnets værdi er større end roden. Og dens højre barn er større end roden. Med andre ord, hvis du tager nogen af ​​de noder, cirklerne i dette billede, og ser på dens venstre barn og dets ret barn, den første bør være mindre end, den anden skal være større end. Så tilregnelighed tjekke 55. Det er tilbage barn er 33. Det er mindre end. 55, dens højre barn er 77. Det er større end. Og det er en rekursiv definition. Vi kunne kontrollere hver en af ​​dem noder og det samme mønster ville holde. 

Så hvad er rart i en binær søgning træ, er at man kan vi gennemføre den med en struct, ligesom dette. Og selvom vi smider masser af strukturer på din, de er noget intuitiv nu forhåbentlig. Syntaksen er stadig mystisk sikker, men indholdet af en knude i denne context-- og vi holder bruge ordet node, uanset om det er et rektangel på skærmen eller en cirkel, det er bare nogle generiske beholder, i dette tilfælde af et træ, som den vi så, vi har brug for et heltal i hvert af knudepunkterne og så jeg har brug for to pointere peger til venstre barnet og retten barn, henholdsvis. Så det er, hvordan vi måske gennemføre det i en struct. Og hvordan kan jeg gennemføre det i koden? Nå, lad os tage en hurtig se på dette lille eksempel. Det er ikke funktionel, men jeg har kopieres og indsættes denne struktur. Og hvis min funktion for en binær søgetræet kaldes søgning, og det tager to argumenter, et heltal N og en pointer til et knudepunkt, så en pointer til træet eller en pointer til roden af ​​et træ, hvordan kan jeg gå om at søge efter N? Nå, først, fordi jeg er beskæftiger sig med pointere, Jeg har tænkt mig at gøre en sanity check. Hvis træet ligemænd lig nul, er N i dette træ eller ikke i dette træ? Det kan ikke være, ikke? Hvis jeg forbi null, der er ikke noget der. Jeg kan lige så godt bare blindt sige return false. Hvis du giver mig noget, jeg kan vel ikke finde nogen tal N. Så hvad ellers kunne jeg Tjek nu? Jeg har tænkt mig at sige godt andet, hvis N er mindre end hvad der er på træet node at jeg har været afleveret N-værdi. Med andre ord, hvis antallet er jeg søger, N, er mindre end den node at jeg ser på. Og node jeg søger på kaldes træ, og husker fra det foregående eksempel at komme på værdien i en pegepind, Jeg bruger pilen notation. Så hvis N er mindre end træ pil N, jeg ønsker at begrebsmæssigt gå til venstre. Hvordan formulerer jeg du søger, tilbage? For at være klar, hvis det er billedet pågældende og jeg har bestået, at øverste arrow der er pegende nedad. Det er mit træ pointer. Jeg peger på roden af ​​træet. Og jeg leder sige, for antallet 44, vilkårligt. Er 44 mindre end eller på over 55 naturligvis? Så det er mindre end. Og så dette, hvis betingelse gælder. Så begrebsmæssigt, hvad ønsker jeg at søge næste hvis jeg leder efter 44? Ja? 

Præcis, jeg ønsker at søg venstre barn, eller venstre undertræ af dette billede. Og i virkeligheden, så lad mig igennem billedet hernede for bare et øjeblik, da Jeg kan ikke ridse det ud. Hvis jeg starter her ved 55, og Jeg ved, at værdien 44 Jeg leder efter, er at venstre, det er sådan ligesom rive telefonbog halvdelen eller rive træet i halve. Jeg behøver ikke længere at bekymre sig om hele denne halvdel af træet. Og dog, mærkeligt med hensyn til struktur, denne ting herovre, at starter med 33, at selv er en binær søgning træ. Jeg sagde ordet rekursive før, fordi faktisk er det en datastruktur, per definition er rekursiv. Du har måske et træ, der er det store, men hver eneste af sine børn repræsenterer et træ bare lidt mindre. I stedet for at det er bedstefar eller bedstemor, nu er det bare mor eller-- jeg kan ikke say-- ikke mor eller far, der ville være underligt. I stedet de to børn der ville være som bror og søster. En ny generation af stamtræet. Men strukturelt, det er den samme idé. Og det viser sig jeg har en funktion som kan jeg søge en binær søgning træ. Det kaldes søgning. Jeg søger efter N i træ pil til venstre ellers hvis N er større end værdien at jeg er i øjeblikket på. 55 i historien for et øjeblik siden. Jeg har en funktion kaldet søgning, som jeg kan bare pass N dette, og rekursivt søge sub-træet og bare tilbagevenden hvad det så svaret. Else Jeg har fået nogle endelige base case her. 

Hvad er det sidste tilfældet? Tree er enten nul. Værdien jeg enten leder efter, er mindre end det eller større end den eller lig med den. Og jeg kunne sige lige lige, men det er logisk svarende til blot at sige andet her. Så sandt er, hvordan jeg finder noget. Så forhåbentlig dette er en endnu mere overbevisende eksempel end den dumme sigma-funktionen vi gjorde et par foredrag tilbage, hvor det var lige så let at bruge en løkke at tælle op alle de numre fra én til N. Her med en datastruktur at selv er rekursivt defineret og rekursivt trukket, nu er vi har evnen til at udtrykke os i kode, selv er rekursivt. Så dette er nøjagtig den samme kode her. 

Så hvilke andre problemer kan vi løse? Så en hurtig skridt væk fra træer for bare et øjeblik. Her er, siger den tyske flag. Og der er helt klart en mønster dette flag. Og der er masser af flag i verden, der er så simpelt som dette i form af deres farver og mønstre. Men formoder, at dette er lagret som en .GIF Eller en JPEG eller bitmap, eller en ping, enhver grafisk filformat som du er fortrolig, hvoraf vi er spiller med i PSET4. Dette synes ikke værd at gemme sort pixel, sort pixel, sort pixel, dot, dot, dot, en hel masse sorte pixels for første scanlinie, eller række, så en hel masse det samme, så en hel masse af det samme, og derefter en hel masse røde pixels, røde pixels, rød pixel, så en hel bundt af gule pixels, gul, ikke? 

Der er sådan ineffektivitet her. Hvordan ville du intuitivt komprimere tyske flag hvis gennemføre det som en fil? Ligesom Hvilke oplysninger kan vi ikke gider at lagre på disk for at mindske vores filstørrelsen fra ligesom en megabyte til en kilobyte, noget mindre? Hvori ligger den redundans her for at være klar? Hvad kunne du gøre? Ja? Præcis. Hvorfor ikke i stedet huske farven på hver pixel darn ligesom du laver i PSET4 med bitmap filformat, hvorfor du ikke bare repræsenterer kolonnen længst til venstre af pixels, for eksempel en flok sorte pixels, en flok af rødt, og en flok gul, og så bare en eller anden måde at kode idé af Gentag dette 100 gange eller gentage dette 1.000 gange? Hvor 100 eller 1.000 er bare et heltal, så du kan slippe af sted med blot et enkelt nummer i stedet for hundreder eller tusinder yderligere pixels. Og ja, det er, hvordan vi kunne komprimere den tyske flag. Og Nu hvad med fransk flag? Og lidt en slags mental øvelse, som flag kan komprimeres mere på disken? Det tyske flag eller fransk flag, hvis vi tager denne fremgangsmåde? Den tyske flag, fordi der er mere horisontal redundans. Og ved design, mange grafiske fil formater rent faktisk arbejde som skanderingslinier vandret. De kunne arbejde lodret, lige menneskeheden besluttet år siden, at vi vil generelt tænke på ting rækken rækkevis i stedet for søjle for søjle. Så ja, hvis du var at se på filen størrelse med en tysk flag og en fransk flag, så længe opløsningen er det samme, den samme bredde og højde, denne ene her vil være større, fordi du nødt til at gentage dig selv tre gange. Du skal angive blå, gentag dig selv, hvid, gentage dig selv, rød, gentage dig selv. Du kan ikke bare gå hele vejen til højre. Og som en sidebemærkning, at gøre rydde komprimering er overalt, hvis disse er fire rammer fra en video-- du kunne huske, at en film eller video er generelt ligesom 29 eller 30 billeder i sekundet. Det er ligesom en lille flip bog, hvor du bare se billedet, billede, billede, billede, billede bare super hurtigt, så det ligner aktørerne på skærmen bevæger sig. Her er en humlebi på toppen af ​​en buket blomster. Og selv om det kan være slags svært at se ved første øjekast, det eneste, der bevæger sig i denne film er bi. 

Hvad er dum om opbevaring video komprimeret? Det er lidt spild at gemme video som fire næsten identiske billeder, adskiller sig kun i det omfang, hvor Bee. Du kan smide de fleste af disse oplysninger og husker kun, for eksempel, den første ramme og den sidste ramme, keyframes Hvis du har nogensinde hørt ordet, og bare gemme i midten, hvor bien er. Og du behøver ikke at gemme alle de lyserøde, og den blå, og grønne værdier. Så det er kun at sige, at komprimering er overalt. Det er en teknik, vi ofte bruger eller tage for givet disse dage. 

Men hvordan kan du komprimere tekst? Hvordan kan du gå om at komprimere tekst? Nå, hver af personerne i ASCII er én byte eller otte bits. Og der er slags dum, ikke? Fordi du sandsynligvis type A og E og I og O og U en masse oftere end som W eller Q eller Z, afhængigt af hvilket sprog du skriver sikkert. Og så hvorfor bruger vi otte bits for hvert bogstav, herunder de mindst populære breve, ikke? Hvorfor ikke bruge færre bit til super populære bogstaver, Ligesom E, de ting du gætte først i Wheel of Fortune, og bruge flere bit for de mindre populære bogstaver? Hvorfor? Fordi vi bare gå til bruge dem mindre hyppigt. 

Tja, det viser sig, at der har været forsøg på at gøre dette. Og hvis du husker fra lønklasse skole eller gymnasium, morsekode. Morsekode har prikker og streger, der kan være overføres langs en ledning som lyde eller signaler af en slags. Men Morse kode er en super ren. Det er lidt af et binært system at du har prikker eller streger. Men hvis du ser for eksempel, to prikker. Eller hvis du tænker tilbage til operatøren der går sådan bip, bip, bip, bip, rammer en lille trigger der overfører et signal, Hvis du, modtageren modtager to prikker, hvilket budskab har du modtaget? Helt vilkårlig. 

I? I? Eller hvad om-- eller jeg? Måske var det blot to E ret? Så der er dette problem af decodability med Morse kode, hvorved medmindre person, sende dig beskeden faktisk holder pause, så du kan sortere på se eller høre hullerne mellem bogstaverne, det er ikke nok bare at sende en strøm af nuller og ettaller, eller prikker og streger, fordi der er tvetydighed. E er en enkelt prik, så hvis du se to prikker eller hører to prikker, måske er det to E 's eller måske er det en I. Så vi har brug for et system, der er en lidt mere klog end det. Så en mand ved navn Huffman år siden kom op med netop dette. Så vi bare at tage et hurtigt blik hvordan træer er relevant for dette. Antag, at dette er en dumme meddelelse, du vil sende, sammensat af lige A, B, C s D's og E s, men der er en masse redundans her. Det er ikke ment til at være engelsk. Det er ikke krypteret. Det er bare en dum besked med masser af gentagelser. Så hvis du faktisk regne ud hele A s, BS, C'er, D's og E s, her er frekvensen. 20% af bogstaverne er A 's, 45% af bogstaverne er E s, og tre andre frekvenser. Vi tælles op der manuelt og bare gjorde det math. 

Så det viser sig, at Huffman, for nogen tid siden, indså, at, du ved hvad, hvis jeg begynder bygning et træ eller skov af træer, hvis du vil, som følger, kan jeg gøre følgende. Jeg har tænkt mig at give en node til hver af de breve, som jeg holder af og jeg har tænkt mig at gemme indersiden af ​​det pågældende knudepunkt frekvenserne som floating point værdi, eller du kan bruge det en N, også, men vi vil bare bruge en float her. Og algoritmen, som foreslog han er, at du tager denne skov af enkelt node træer, så super korte træer, og du begynder at forbinde dem med nye grupper, nye forældre, hvis du vil. Og du gør dette ved at vælge den to mindste frekvenser ad gangen. Så jeg tog 10% og 10%. Jeg opretter en ny knude. Og jeg kalder den nye knude 20%. 

Hvilke to knuder jeg kombinere næste? Det er lidt tvetydig. Så der er nogle hjørne sager til overveje, men at holde tingene smuk, Jeg har tænkt mig at vælge 20% - Jeg vil nu ignorere børnene. Jeg har tænkt mig at vælge 20% og 15% og tegne to nye kanter. Og nu hvor to knuder kan jeg logisk kombinere? Ignorere alle børnene, alle de børnebørn, bare se på rødderne nu. Hvilke to knudepunkter skal jeg binde sammen? Punkt to og 0,35. Så lad mig tegne to nye kanter. Og så har jeg kun fik én til venstre. Så her er et træ. Og det er blevet trukket med vilje at se slags smuk, men bemærker, at kanterne har også blevet mærket nul og én. Så alle de venstre kanter er nul vilkårligt, men konsekvent. Alle højre kanter er dem. 

Og så hvad Hoffman foreslået er, hvis du ønsker at repræsentere et B, i stedet repræsenterer antallet 66 som en ASCII som er otte hele bits, ved du hvad, bare butik mønsteret nul, nul, nul, nul, fordi det er den vej fra mit træ, Hr Huffman s træet, til bladet fra roden. Hvis du ønsker at gemme en E derimod ikke Send otte bits, der repræsenterer en E. I stedet sende hvad mønster af bits? One. Og hvad er nice om dette er at E er den mest populære skrivelse, og du bruger den korteste kode til det. Det næste mest populære brev ligner det var A. Og så hvor mange bits han foreslår at bruge til det? Zero, en. 

Og fordi det er implementeret som dette træ, for nu lad mig fastsætte der er ingen tvetydighed som i Morse kode, fordi alle bogstaver, du holder af er i slutningen af ​​disse kanter. Så det er bare en anvendelse af et træ. Dette is-- og jeg vil bølge min hånd på dette, hvordan du kunne gennemføre denne som en C-struktur. Vi skal bare nødt til at kombinere et symbol, som en char, og frekvensen i venstre og højre. Men lad os se på to endelige eksempler, som du vil få helt fortrolig med efter quiz nul i problemet sæt fem. 

Så der er datastrukturen kendt som en hash tabel. Og en hash tabel er slags afkøles i, at det har spande. Og formoder, at der er fire spande her, kun fire tomme rum. Her er et spil kort, og her er klub, spade, klub, diamanter, klub, diamanter, klub, diamanter, clubs-- så dette er tilfældigt. Hjerter, Hearts-- så jeg er bucketizing alle de input her. Og en hash tabel behov til at se på dit input, og derefter sætte det i en vis placere baseret på, hvad du ser. Det er en algoritme. Og jeg var ved hjælp af en super simpel visuel algoritme. Den sværeste del af som var huske, hvad billederne var. Og så er der fire i alt ting. 

Nu stablerne voksede, som er en bevidst design ting her. Men hvad kan jeg gøre? Så faktisk her har vi en bunke af gamle skole eksamen bøger. Antag, at en flok elevernes navne er på her. Her er en større hash tabel. I stedet for fire skovle, Jeg har, lad os sige 26. Og vi ønskede ikke at gå låne 26 ting udefra [? Annenberg?], Så her er fem, der repræsenterer En gennem Z. Og hvis jeg se en studerende, hvis navn starter med A, Jeg har tænkt mig at sætte hans eller hendes quiz der. Hvis nogen begynder med C, derovre, En-- faktisk, ønskede ikke at gøre det. B går herovre. Så jeg har fået A og B og C. Og nu her er en anden En studerende. Men hvis denne hash tabel er gennemføres med et array, Jeg slags skruet på dette tidspunkt, ikke? Jeg slags nødt til at sætte dette sted. 

Så en måde jeg kan løse dette er, alt højre, A er optaget, B er optaget, C er optaget. Jeg har tænkt mig at sætte ham i D. Så på først, jeg har random øjeblikkelig adgang til hver af skovle til de studerende. Men nu er det sådan decentrale til noget lineær, fordi hvis jeg ønsker at søge efter en person hvis navn starter med A, jeg tjekke her. Men hvis dette ikke er A elev, jeg leder efter, Jeg slags nødt til at begynde at kontrollere spande, fordi det, jeg gjorde var slags lineært probe datastrukturen. En dum måde at sige bare se for den første tilgængelige åbning, og lægge så en plan B, så at sige, eller plan D i denne sag, at værdien i denne placering i stedet. Det er bare så, at hvis du har fik 26 steder og ingen studerende med navnet Q eller Z, eller noget lignende at du i det mindste bruger rummet. 

Men vi har allerede set mere smarte løsninger her, ikke? Hvad ville du gøre i stedet hvis du har en kollision? Hvis to mennesker har navnet A, hvad ville har været en mere intelligent eller flere intuitiv løsning end blot sætte A hvor D formodes at være? Hvorfor kan jeg ikke bare gå uden [? Annenberg?], Ligesom malloc, anden node, sætte det her, og derefter sætte, at en studerende her. Så jeg har i det væsentlige en slags et array, eller måske mere elegant, som vi er begyndt at se en linket liste. 

Og så en hash tabel er en struktur der kunne se lige sådan ud, men mere smart, du noget, der hedder separat kæde, hvorved en hash tabel ganske enkelt er en matrix, hvor hver af hvis elementer er ikke et tal, selv er en sammenkædet liste. Så du får super hurtig adgang afgør, hvor at hash din værdi til. Meget gerne med kort eksempel, Jeg lavede super hurtige beslutninger. Hjerter går her, diamanter går her. Samme her, A går her, D går her, B går her. Så super hurtige opslag, og hvis du tilfældigvis løbe ind i en sag hvor du har fået kollisioner, to mennesker med samme navn, ja så du bare begynde at linke dem sammen. Og måske du holde dem ordnet alfabetisk, måske du ikke gør. Men i det mindste nu har vi dynamik. Så på den ene side har vi super hurtig konstant tid, og art lineær tid involveret, hvis disse linkede lister begynder at få lidt lang. 

Så denne slags en fjollet, nørdede joke år siden. På CS50 hack-a-thon, når eleverne tjekke, nogle TF eller CA hvert år synes det er sjovt at sætte op et skilt som dette, hvor det bare betyder, at hvis dit navn starter med et A, gå denne vej. Hvis dit navn starter med et B, gå denne-- OK, det er sjovt måske senere i semesteret. Men der er en anden måde at gøre det, også. Kom tilbage til. 

Så der er denne struktur. Og dette er vores sidste struktur for i dag, hvilket er noget, der hedder en trie. T-R-I-E, som en eller anden grund er kort til hentning, men det hedder trie. Så en trie er et andet interessant sammensmeltning af en masse af disse ideer. Det er et træ, som vi har set før. Det er ikke en binær søgning træ. Det er et træ med et vilkårligt antal børn, men hver af børnene i en trie er en matrix. En vifte af størrelse, siger, 26 eller måske 27 Hvis du ønsker at støtte bindestreg navne eller apostroffer i folks navne. 

Og så dette er en datastruktur. Og hvis man ser fra top til bund, ligesom hvis du se øverst node der, M, er peger på den venstre ting der, som derefter A, X, W, E, L, L. Dette er blot en datastruktur, der vilkårligt er at gemme folks navne. Og Maxwell er gemt ved blot at følge en sti af array til array til array. Men hvad er forbløffende om en trie er at, mens en linket liste, og selv et array, det bedste, vi nogensinde har fået, er lineær tid eller logaritmisk tid på at lede person op. I denne datastruktur i en trie, hvis min datastruktur har et navn i det og jeg leder efter Maxwell, jeg er kommer til at finde ham temmelig hurtigt. Jeg bare kigge efter M-A-X-W-E-L-L. Hvis denne datastruktur, derimod, Hvis N er en million, hvis der er en million navne i denne datastruktur, Maxwell stadig vil være synlig efter blot M-A-X-W-E-L-L trin. Og David-- D-A-V-I-D trin. Med andre ord, ved at bygge en datastruktur, der er fik alle disse arrays, som alle selv understøtter random access, Jeg kan begynde at kigge op folks navn med en mængde tid, der er proportional med ikke antallet af ting i datastrukturen, som en million eksisterende navne. Den tid, det tager mig at finde M-A-X-W-E-L-L i denne datastruktur er proportional ikke til størrelsen af ​​den datastruktur, men til længden af ​​navnet. Og realistisk navne, vi leder op aldrig kommer til at være vanvittigt lange. Måske nogen har en 10 tegn navn, 20 tegnnavn. Det er helt sikkert finite, ikke? Der er et menneske på Jorden, der har den længst mulige navn, men dette navn er en konstant værdi længde, ikke? Det betyder ikke varierer i nogen forstand. Så på denne måde, vi har opnået en datastruktur der er konstant tid look-up. Det tager en række skridt afhængigt af længden af ​​input, men ikke antallet af navn i datastrukturen. Så hvis vi fordoble antallet af navne næste år fra en milliard til to milliarder, fund Maxwell vil tage nøjagtig samme antal syv trin at finde ham. Og så synes vi at have opnået vores hellige gral af køretid. 

Så Et par hurtige udmeldinger. Quiz nul kommer op. Mere om det på kursets hjemmeside løbet af de næste par dage. Mandagens lecture-- det er en ferie her på Harvard i mandags. Det er ikke i New Haven, så vi tager klassen til New Haven til foredrag på mandag. Alt vil blive filmet og streamet live som sædvanlig, men lad os slutte i dag med en 30 sekunders klip kaldet "dybe tanker" af Daven Farnham, som var inspireret sidste år ved lørdag Night Lives "Deep Thoughts" af Jack Handy, som bør nu give mening. 

FILM: Og nu, "Deep Tanker "af Daven Farnham. Hash tabellen. 

SPEAKER 1: Okay, det er det for nu. Vi vil se dig i næste uge. 

DOUG: For at se det i aktion. Så lad os tage et kig på det lige nu. Så her har vi en usorteret array. 

IAN: Doug, kan du gå videre og genstart dette for bare et sekund, tak. Okay, der er kameraer rullende, så handling, når du er klar, Doug, OK? DOUG: Okay, så hvad vi har her er en usorteret array. Og jeg har farvet alle de elementer rødt for at indikere, at det er i virkeligheden, usorteret. Så minde om, at det første, vi gør er vi sortere venstre halvdel af array. Så vi sortere det rigtige halvdelen af ​​arrayet. Og ya-da, ya-da, ya-da, vi flette dem sammen. Og vi har en helt sorterede array. Så det er sådan mergesort fungerer. 

IAN: Whoa, whoa, whoa, snit, skære, snit, skære. Doug, ikke kan du bare ya-da, ya-da, ya-da, din vej gennem mergesort. 

DOUG: Jeg har lige gjorde. Det er fint. Vi er gode til at gå. Lad os bare holde rullende. Så alligevel, 

IAN: Du er nødt til at forklare det mere fuldstændigt end det. Det er bare ikke nok. DOUG: Ian, gør vi ikke nødt til at gå tilbage til en. Det er fint. Så alligevel, hvis vi fortsætter med merge-- Ian, vi er midt i optagelserne. 

IAN: Jeg kender. Og vi kan ikke bare ya-da, ya-da, ya-da, gennem hele processen. Du er nødt til at forklare, hvordan to sider bliver slået sammen. 

DOUG: Men vi har allerede forklarede, hvordan de to sides-- 

IAN: Du har lige vist dem en sammenfletning array. DOUG: De kender processen. De er fint. Vi har gået over det ti gange. 

IAN: Du har lige sprunget lige over det. Vi kommer tilbage til en, du kan du ikke ya-da, ya-da over det. Okay, tilbage til én. 

DOUG: Jeg er nødt til at gå tilbage gennem alle dias? Min Gud. Det er ligesom det sjette gang, Ian. Det er fint. 

IAN: Okay. Er du klar? Great. Handling.