TALARE 1: Okej, så det här är CS50 Detta är slutet av veckan fem. Och minns att förra gången vi började titta på snyggare uppgifter strukturer som började lösa problem, som började införa nya problem, men nyckeln till detta var den typ av gäng som vi började göra från nod till nod. Så det här är naturligtvis en enskilt länkad lista. Och genom att var för sig kopplade, Jag menar att det finns bara en tråd mellan var och en av dessa noder. Slår ut kan du göra snyggare saker som dubbelt länkade listor där du har en pil går i båda riktningarna, vilket kan hjälpa till med vissa effektivitetsvinster. Men detta löste problemet? Vilket problem kunde detta lösa? Varför vi bryr oss på måndag? Varför, i teorin, vi bryr oss på måndag? Vad gör den? 

PUBLIK: Vi kan dynamiskt ändra storlek på den. 

TALARE 1: OK, så vi kan dynamiskt ändra storlek på den. Bra gjort både av er. Så du kan dynamiskt ändra storlek här datastruktur, medan en matris, minns, måste du veta en priori hur mycket utrymme du vill och om du behöver lite mer utrymme, är du typ av av lycka. Du måste skapa en helt ny uppsättning. Du måste flytta alla dina data från en till den andra, småningom befria gamla array om du kan, och sedan fortsätta. Vilket känns bara mycket kostsamt och mycket ineffektiv, och faktiskt kan det vara. Men detta är inte allt bra. Vi betalar ett pris, vad som var en av de mer uppenbara priser vi betala med hjälp av en länkad lista? 

PUBLIK: Vi måste använda dubbel utrymme för var och en. TALARE 1: Ja, så vi behöver minst dubbelt så mycket plats. I själva verket, insåg jag att detta bildens även lite missvisande, eftersom på CS50 IDE i en hel del modern datorer, en pekare eller en adress är i själva verket inte fyra byte. Det är ofta dessa dagar åtta byte, som : den nedersta rektanglar där i verkligheten är typ av dubbelt så stor som vad jag har ritat, vilket innebär att du använder tre gånger så mycket utrymme som vi skulle ha annars. Nu samtidigt, vi är fortfarande talar byte, eller hur? Vi är inte nödvändigtvis talar megabyte eller gigabyte, såvida dessa uppgifter strukturer blir stora. 

Och så idag börjar vi att överväga hur vi kan utforska data mer effektivt om i Faktum är att uppgifterna blir större. Men låt oss försöka canonicalize verksamheten först att du kan göra på dessa typer av datastrukturer. Så något som en länkad Listan stöder generellt operationer gillar bort, infoga och söka. Och vad menar jag med det? Det betyder bara att vanligtvis om folk använder länkad lista, de eller någon annan har genomfört funktioner som radera, infoga, och söka, så att du kan faktiskt göra något användbar med datastrukturen. Så låt oss ta en snabb titt på hur vi kan genomföra lite kod för en länkad lista som följer. 

Så det här är bara några C-kod, inte ens ett komplett program att jag verkligen snabbt piskade upp. Det är inte online i distributionen kod, eftersom det kommer faktiskt inte köra. Men märker jag har bara med en kommentar sade, dot dot dot, det finns något där dot dot dot, något där. Och låt oss titta bara på vad saftiga delar. Så på linje tre, påminna om att detta är nu Vi föreslog att förklara en nod sista tiden, en av de rektangulära föremål. Den har en int som vi kallar N, men vi skulle kunna kalla det något, och sedan en struct nod stjärna kallas nästa. Och bara för att vara tydlig, det andra line, on line sex, vad är det? Vad gör den för oss? Eftersom det verkligen ser mer kryptiska än våra vanliga variabler. 

PUBLIK: Det gör det gå över en. 

TALARE 1: Det gör det gå över en. Och för att vara mer exakt, det kommer att lagra adressen av den nod som är tänkt att vara semantiskt bredvid den, eller hur? Så det kommer inte att nödvändigtvis flytta någonting. Det är bara att gå till lagra ett värde, som är kommer att vara den adress av någon annan nod, och det är därför vi har sagt struct nod stjärna, stjärnan betecknar en pekare eller en adress. OK, så nu om du antar att vi har denna N tillgängliga för oss, och låt oss antar att någon annan har infört en massa heltal in i en länkad lista. Och det länkade listan är pekas på av någon punkt en variabel som heter lista som är passerade här som en parameter, Hur gör jag linje 14 genomförande sökning? Med andra ord, om jag genomföra funktion vars syfte i livet är att ta en int och sedan början av en länkad lista, som är en pekare till den länkade listan. Liksom första, som jag tror David var vår volontär på måndag, Han pekade på hela länkad lista, det är som om vi passerar David i vår argument här. Hur ska vi göra gå igenom den här listan? Tja, visar det sig att även om pekare är relativt nya nu till oss, Vi kan göra detta relativt rättframt. 

Jag kommer att gå vidare och deklarerar en temporär variabel som enligt praxis är att bara gå att kallas pekare eller PTR, men du kan kalla det vad du vill. Och jag kommer att initiera det till början av listan. Så du kan slags tänka på detta som jag läraren häromdagen, typ av pekar på någon bland våra människor som volontärer. Så jag är en temporär variabel som är bara pekar på samma sak att vår tillfällighet namnges volontär David var också påpeka. Nu när pekaren inte null, eftersom återkallelse att noll är några speciella sentinel värde den avgränsar slutet av listan, så medan jag inte pekar på marken som vår sista volontär var, låt oss gå vidare och gör följande. Om pointer-- och nu har jag slags vill att göra vad vi gjorde med studenten structure-- om pekare dot nästa equals-- snarare, om pekaren dot N är lika lika med variabeln N, varvid argument som har förts in, då jag vill gå vidare och säga return true. Jag har hittat antalet N insida en av noderna i min länkad lista. Men punkten inte längre fungerar i detta sammanhang, eftersom pekare, PTR, är verkligen en pekare, en adress, vi faktiskt kan underbart Använd slutligen en bit av syntax den typen av fabrikat intuitiv känsla och faktiskt Använd en pil här, vilket innebär att gå från adressen till heltal där i. Så det är väldigt lika i anda att punktoperatorn, men eftersom pekaren är inte en pekare och inte en faktisk struct själv, vi använder bara pilen. 

Så om den aktuella noden att jag, temporär variabel, am pekar på är inte N, vad vill jag göra? Tja, med mina frivilliga försökspersoner att vi hade här häromdagen, om mitt första människa är inte den jag vill, och kanske andra människors inte den jag vill, och den tredje, jag behöver för att hålla fysiskt i rörelse. Liksom hur gör jag stega igenom en lista? När vi hade en matris, du just gjorde som jag plus plus. Men i detta fall är det tillräckligt att gör pekare blir, pekare, nästa. Med andra ord, nästa fält är som alla vänster hand att våra frivilliga på måndag använde för att peka på någon annan nod. Det var deras nästa grannar. 

Så om jag vill gå igenom den här listan, Jag kan inte bara jag plus plus längre, Jag har i stället för att säga I pekare, går till lika oavsett nästa fält är, nästa fält, är nästa fält, efter alla dessa vänster hand att vi hade på scenen pekar till vissa efterföljande värden. Och om jag får igenom att hela iteration, och slutligen, jag slog null inte ha hittade N ändå, jag tillbaka bara falskt. Så återigen, allt som vi gör här, enligt bilden för en stund sedan, börjar genom att peka på i början av listan förmodligen. Och då jag kolla, är värdet Jag letar efter lika med nio? Om så är fallet, återvänder jag sanna och jag är klar. Om inte, uppdaterar jag min hand, AKA pekare, peka vid nästa pilen läge, och sedan nästa pilen läge, och nästa. Jag är helt enkelt gå igenom denna uppsättning. 

Så återigen, vem bryr sig? Liksom vad är detta en ingrediens för? Tja, minns att vi införde begreppet en stapel, som är en abstrakt datatyp i den mån det är inte C sak, det är inte en CS50 sak, Det är en abstrakt idé, denna idé om stapla saker ovanpå varandra som kan genomföras i klasar av olika sätt. Och ett sätt som vi föreslog var med en array, eller med en länkad lista. Och det visar sig att canonically, en stack stödjer åtminstone två operationer. Och modeord är push, till skjut något på stacken, som en ny bricka i matsalen, eller pop, vilket innebär att ta bort den översta bricka från stapeln i matsalen hall, och sedan kanske en del övrig verksamhet samt. Så hur kan vi definierar strukturen att vi nu kallar en stapel? 

Tja, vi har alla erforderliga syntax till vårt förfogande i C. Jag säger, ge mig en definition typ av en struct inne i en stapel, Jag kommer att säga är en uppsättning av en massa siffror och sedan storlek. Så med andra ord, om jag vill att genomföra detta i koden, låt mig gå och bara typ av rita vad det säger. Så detta säger, ge mig en struktur som har fått en array, och jag vet inte vilken egenskap är, Det är tydligen någon konstant som jag har definieras på annat håll, och det är bra. Men antar att det är bara en, två, tre, fyra, fem. Så kapacitet är 5. Denna del insidan av min struktur kommer att kallas nummer. Och då behöver jag en annan variabel tydligen kallas storlek som ursprungligen kommer jag att föreskriva initieras till noll. Om det finns inget i stapeln, storleken är noll, och det är sopor värden i antal. Jag har ingen aning om vad som finns där ännu. 

Så om jag vill driva något på stacken, antar att jag kallar funktionen push, och Jag säger skjuta 50, liksom antalet 50, var skulle du föreslå Jag drar det i denna samling? Det finns fem olika svarsalternativ. Var vill du att driva antalet 50? Om målet här, igen, ring funktions skjuta, passera i ett argument 50, var ska jag uttrycka det? Fem possible-- 20% chans att gissa korrekt. Ja? 

PUBLIK: Längst till höger. 

TALARE 1: Längst till höger. Det finns nu en chans 25% att gissa korrekt. Så det skulle faktiskt vara bra. Av konvention, ska jag säga med en array, Vi skulle i allmänhet börja från vänster, men vi kunde säkert starta vid rätt. Så spoiler här skulle vara jag förmodligen kommer att dra den till vänster, precis som i en vanlig array där Jag börja gå från vänster till höger. Men om du kan vända det aritmetiska, bra. Det är bara inte konventionella. OK, jag måste göra en mer förändring men. Nu när jag har drivit något på stacken, vad händer nu? 

Okej, jag måste öka storleken. Så låt mig gå vidare och bara uppdatera denna, som var noll. Och i stället nu, jag ska att sätta i värdet ett. Och nu antar att jag trycker en annan numret på stacken, som 51. Tja, jag måste göra en mer förändring, som är upp till storlek två. Och sedan antar jag trycker en mer numret på stacken som 61, Nu måste jag uppdatera storlek ytterligare tid, och få värdet 3 som storleken. Och nu antar att jag kallar pop. Nu pop, enligt konvention, tar inte ett argument. Med en stapel, hela punkt av brickan metafor är att du inte har handlingsfrihet att gå få det facket, kan du göra är pop översta en från stacken, bara för att. Det är vad denna datastruktur gör. 

Så genom denna logik, om jag säger pop, vad som kommer ut? Så 61. Så vad som verkligen är datorn kommer att göra i minnet? Vad min kod måste göra? Vad skulle du föreslå vi ändrar på skärmen? Vad ska förändras? Förlåt? Så vi bli av med 61. Så jag kan definitivt göra det. Och jag kan bli av med 61. Och sedan vad andra förändringen måste ske? Storlek har antagligen gå tillbaka till två. Och så går det bra. Men vänta en minut, storlek en stund sedan var tre. Låt oss bara göra en snabb kontroll förstånd. Hur visste vi att vi ville bli av med 61? Eftersom vi poppar. Och så jag har denna andra fastigheternas storlek. 

Vänta lite, jag är tänker tillbaka till vecka två när vi började prata om matriser, där detta läge noll, detta var platsen en, var denna plats två, detta är platsen tre, fyra, det ser ut som förhållande mellan storlek och element som jag vill ta bort från gruppen verkar vara det? Storlek minus ett. Och så det är hur som människor vi vet 61 kommer först. Hur är datorn kommer att veta? När koden, där du förmodligen vill göra storlek minus ett, så tre minus ett är två, och att innebär att vi vill bli av med 61. Och då kan vi verkligen uppdatera storleken så att storlek går från tre till endast två. Och bara för att vara pedantisk, jag kommer att föreslå att jag är klar, eller hur? Ni föreslog intuitivt korrekt jag skulle bli av med 61. Men har jag inte typ av sorts gjort sig av 61? Jag har faktiskt glömt att det är faktiskt där. Och tänker tillbaka på PSET4, om du har läst artikeln om kriminalteknik, PDF att vi hade ni läsa, eller om du kommer att läsa denna vecka för PSET4. Minns att detta är faktiskt relevant för hela idén med dator kriminalteknik. Vilken dator gör i allmänhet är det bara glömmer där något är, men det inte gå in och ut försöka skrapa ut eller överstyrning dessa bitar med nollor och ettor eller någon annan slumpmässigt mönster om du inte själv göra det medvetet. Så din intuition var Okej, låt oss bli av med 61. Men i verkligheten, har vi inte bry. Vi behöver bara att glömma att den finns där genom att ändra vår storlek. 

Nu finns det ett problem med den här stack. Om jag hålla driver saker på stacken, vad är uppenbarligen kommer att hända på bara några ögonblick tid? Vi kommer att köra ut i rymden. Och vad gör vi? Vi slags skruvad. Denna implementering inte låta oss ändra storlek på matrisen, eftersom att använda denna syntax, om du tänker tillbaka på vecka två, när du har deklarerat storleken på en array, Vi har inte sett den mekanism där Du kan ändra storleken på matrisen. Och faktiskt C inte har den funktionen. Om du säger ge mig fem Nths, kallar dem tal, det är allt du kommer att få det. Så vi gör nu som måndagen, har förmågan att uttrycka en lösning Men vi behöver bara justera Definitionen av vår stack att inte vara en del hårdkodade array, men bara för att lagra en adress. 

Nu varför är detta? Nu har vi bara att vara bekväm med det faktum att när mitt program körs Jag förmodligen kommer att måste be människa, hur många nummer vill du spara? Så ingången måste komma någonstans ifrån. Men när jag vet att nummer, så jag kan bara använda vilken funktion att ge mig en bit av minne? Jag kan använda malloc. Och jag kan säga valfritt antal bytes Jag vill tillbaka för dessa Nths. Och allt jag har att lagra i siffrorna variabel här insidan av denna struct bör vara vad? Vad som faktiskt går in i siffror i detta scenario? Ja, en pekare till den första byten i den bit av minne, eller mer specifikt, till adressen den första av dessa byte. Spelar ingen roll om det är en byte eller en miljard byte, Jag behöver bara bry sig om den första. För vad malloc garantier och mitt operativsystem garantier, är att bit av minnes I få, det kommer att vara sammanhängande. Det kommer inte att finnas luckor. Så om jag har bett om 50 bytes eller 1000 bytes, De kommer alla att vara rygg mot rygg mot rygg. Och så länge jag minns hur stor, hur mycket jag bad om, allt jag behöver veta är den första adressen. 

Så nu har vi möjlighet i koden. Om än, det kommer att ta oss mer tid att skriva upp detta, Vi kunde nu omfördela att minnet av bara lagra en annan adress där Om vi ​​vill ha en större eller ens en mindre bit av minnet. Så här till en avvägning. Nu får vi dynamik. Vi har fortfarande contiguousness Jag påstår. Eftersom malloc kommer att ge oss en sammanhängande del av minnet. Men detta kommer att vara en smärta i nacken för oss, programmeraren, att faktiskt koda upp. Det är bara mer arbete. Vi behöver kod besläktad med vad jag var banka ut bara för en stund sedan. Mycket genomförbart, men det tillför komplexitet. Och så utvecklare tid, programmerare tid är ännu en resurs att vi kan behöva tillbringa lite tid att få nya funktioner. Och så naturligtvis finns det en kö. Vi kommer inte att gå in på detta en i stor detalj. Men det är väldigt lika i anden. Jag skulle kunna genomföra en kö, och dess motsvarande verksamhet, enqueue eller dequeue, liksom lägga till eller ta bort, det är bara en finare sätt att säga det, enqueue eller dequeue, enligt följande. Jag kan bara ge mig en struct som återigen har ett antal s array, som återigen har en storlek, men varför gör jag nu behöver att hålla reda på den främre delen av en kö? Jag behövde inte veta framsidan av min stack. Tja, om jag återigen för en queue-- låt oss bara hårt koda det som har som fem heltal i här potentiellt. Så det här är noll, ett, två, tre, fyra. Detta kommer att bli uppringda numren igen. Och detta kommer att kallas storlek. 

Varför är det inte tillräckligt att bara storlek? Nåväl, låt oss skjuta samma nummer på. Så jag pushed-- jag kö, eller trycks in. Nu ska jag köa 50, och sedan 51, och sedan 61, och dot dot dot. Så det är enqueue. Jag kö 50, sedan 51, sedan 61. Och som ser identisk till en stapel så här långt, förutom att jag behöver göra en förändring. Jag behöver uppdatera denna storlek, så jag går från noll till en till 2 till tre nu. Hur gör jag avköa? Vad händer med dequeue? Vem ska lossna här listan först om det är ledningen på Apple Store? Så 50. Så det är typ av svårare den här gången. Medan förra gången det var super lätt att bara göra storlek minus ett, Jag kommer till slutet av min samling effektivt där siffrorna är, tar bort det 61. Men jag vill inte ta bort 61. Jag vill ta 50, som var där vid 05:00 att rada upp för ny iPhone eller whatnot. Och så för att bli av 50, jag kan inte bara göra det, eller hur? Jag kan stryka 50. Men vi sa bara vi behöver inte vara så anal att skrapa ut eller dölja data. Vi kan bara glömma där det är. 

Men om jag ändrar min storlek nu två, är detta tillräckligt med information att veta vad som händer i mitt kön? Inte riktigt. Liksom min storlek är två, men Vari kön börjar, speciellt om jag har fortfarande samma nummer i minnet. 50, 51, 61. Så jag måste komma ihåg nu där den främre är. Och så jag föreslog upp där vi har bara kallas N: te front, vars ursprungliga värde borde ha varit vad? Zero, bara början på listan. Men nu förutom nedräkning storlek, vi bara öka fronten. Nu här är ett annat problem. Så när jag hålla kommer. Antag att detta är antalet liknande 121, 124, och sedan, helvete, Jag är ute i rymden. Men vänta en minut, jag inte. Så vid denna tidpunkt i historien, antar att storleken är en, två, tre, fyra, så anta att storlek är fyra, fronten är en, så 51 är vid fronten. Jag vill sätta ett annat nummer här, men, helvete, jag är ute i rymden. Men jag är inte riktigt, eller hur? Var kan jag sätta några mervärde, som 171? Ja, jag kunde bara typ av gå tillbaka dit, eller hur? Och sedan stryka 50, eller bara skriva det med 171. Och om du undrar varför våra siffror fick så slumpmässigt, dessa är vanligen tas dator vetenskap kurser på Harvard efter CS50. Men det var en bra optimering, för nu jag inte slösa utrymme. Jag har fortfarande komma ihåg hur stor denna sak är total. Det är fem totalt. Eftersom jag inte vill börja skriva över 51. Så nu är jag fortfarande slut på utrymme, så samma problem som tidigare. Men du kan se hur nu i din kod, du förmodligen måste skriva lite mer komplexitet för att förverkliga detta. Och faktiskt, vad operatör i C förmodligen låter du magiskt göra detta cirkularitet? Ja modulo operatör, procenttecknet. Så vad är ganska coolt om en kö, även om vi håller ritning arrayer eftersom dessa liknande raka linjer, om du typ av tycker om detta som krökning runt som en cirkel, sedan bara intuitivt det slags fungerar mentalt Jag tror att en lite renare. Du skulle fortfarande behöva genomföra att mental modell i koden. Så inte så svårt, i slutändan, att genomföra, men vi fortfarande förlorar size-- snarare möjligheten att ändra storlek, om vi inte gör detta. 

Vi måste bli av med array, vi ersätta den med en enda pekare, och sedan någonstans i min kod jag har ett samtal vilken funktion att faktiskt skapa arrayen uppringda numren? Malloc, eller något liknande funktion, exakt. Har du frågor om staplar eller köer. Yeah? Bra fråga. Vad modulo skulle du använda här. Så generellt, när du använder mod, skulle du göra det med storleken av den Hela datastruktur. Så något som fem eller kapacitet, om Det är konstant, är troligen inblandade. Men bara göra modulo fem förmodligen inte är tillräckligt, eftersom vi behöver veta vi lindas runt här eller här eller här. Så du är förmodligen också kommer att vilja engagera storleken på sak, eller front variabeln också. Så det är just detta relativt enkla aritmetiska uttryck, men modulo skulle vara den viktigaste ingrediensen. 

Så kortfilm om du kommer. En animering som en del folks vid ett annat universitet sätta ihop att vi har anpassad för denna diskussion. Det handlar om Jack lära sig fakta om köer och statistik. 

FILM: En gång i tiden, Det var en kille som heter Jack. När det kom till att göra vänner, Jack hade inte en talang. Så Jack gick att prata med mest populär kille han kände. Han gick till Lou och frågade, vad ska jag göra? Lou såg att hans vän var verkligen bedrövad. Tja, började han, precis se hur du är klädd. Har du inte ha några kläder med ett annorlunda utseende? Ja, säger Jack. Jag säker gör. Kom till mitt hus och Jag ska visa dem till dig. Så de gick till Jack. Och Jack visade Lou rutan där han höll alla hans skjortor, och hans byxor och hans strumpor. Lou sa, jag ser att du har alla dina kläder i en hög. Varför inte du bära vissa andra gång på ett tag? 

Jack sa, ja, när jag ta bort kläder och strumpor, Jag tvättar dem och sätta bort dem i lådan. Sedan kommer nästa morgon, och upp mig hopp. Jag går till lådan och få mina kläder utanför toppen. Lou insåg snabbt problemet med Jack. Han höll kläder, CD-skivor, och böcker i stapeln. När han sträckte sig efter något att läsa eller att bära, han skulle välja den övre bok eller underkläder. Sen när han var klar, han skulle uttrycka det tillbaka. Tillbaka det skulle gå, ovanpå stapeln. Jag vet lösningen, sade en triumferande Loud. Du måste lära dig att börja använda en kö. Lou tog Jack kläder och hängde dem i garderoben. Och när han hade tömt rutan, han bara kastade den. 

Då sade han, nu Jack, i slutet av dagen, sätta dina kläder på vänster när du lägger undan dem. Sedan i morgon bitti när du se solen, få dina kläder till höger, från slutet av raden. Ser du inte? sade Lou. Det ska bli så skönt. Du kommer att ha allt en gång innan du bär något två gånger. Och med allt i köer i sin garderob och hylla, Jack började känna helt säker på sig själv. Allt tack vare Lou och hans underbara kö. TALARE 1: Okej, det är bedårande. Så vad har egentligen kommer på under huven nu? Att vi har pekare, att vi har malloc, att vi har förmågan att skapa bitar av minne för oss dynamiskt. Så det här är en bild vi skymtade bara häromdagen. Vi visste inte riktigt bo på det, men den här bilden har pågått under huven i flera veckor nu. Och så detta representerar bara en rektangel som vi har ritat, datorns minne. Och kanske din dator, eller CS50 ID, har en gigabyte minne eller RAM eller två gigabyte eller fyra. Det spelar egentligen ingen roll. Operativsystemet Windows eller Mac OS eller Linux, i huvudsak gör ditt program att tro att det har tillgång till helheten av datorns minne, även om du kanske köra flera program samtidigt. Så i verkligheten, som egentligen inte fungerar. Men det är typ av en illusion ges till alla dina program. Så om du hade två gig RAM, detta är hur datorn kan tänka på det. 

Nu tillfällighet, en av dessa saker, ett av dessa segment av minnet, kallas en stapel. Och faktiskt helst hittills i att skriva kod att du har ringt en funktion, till exempel huvud. Minns att varje gång jag har dragen datorns minne, Jag drar alltid sorts hälften av en rektangel här och inte bryr sig prata om vad som är ovan. För när huvud kallas, hävdar jag att du får den här flisa av minne som går här nere. Och om huvud kallas en funktion som swap, väl swap går här. Och det visar sig, det är där det hamna. På något som kallas en stapel insidan av din dators minne. Nu vid slutet av dagen, detta är bara adresser. Det är som byte noll, byte en, byte 2 miljarder kronor. Men om man tänker på det eftersom detta rektangulärt föremål, allt vi gör varje När vi kallar en funktion är skiktning en ny skiva minne. Vi ger denna funktion en skiva av sitt eget minne för att arbeta med. 

Och minns nu att detta är viktigt. För om vi har något liknande swap och två lokala variabler som A och B och vi ändra dessa värden från en och två till två och en, minns att när växlings returnerar, det är som om detta segment minne är bara borta. I verkligheten är det fortfarande där forensically. Och något är fortfarande faktiskt där. Men begreppsmässigt är det som om det är helt borta. Och så huvud inte känner någon av arbetet som gjordes i den swap-funktion, om det är faktiskt gått i dessa argument från pekare eller med hänvisning. Nu, den grundläggande lösningen till det problemet med swap passerar saker i efter adress. Men det visar sig också, vad är pågått över den delen av rektangeln hela denna tid är men det finns mer minne uppe. Och när du dynamiskt allokera minne, oavsett om det är inne i getString, som vi har gjort på dig i CS50 bibliotek, eller om ni ringa malloc och fråga operativsystemet för en bit av minne, men det kommer inte från stapeln. Den kommer från en annan plats i datorns minne som kallas högen. Och det är inte annorlunda. Det är samma RAM. Det är samma minne. Det är bara RAM som är upp där i stället för här nere. 

Så vad betyder det? Tja, om datorn har en begränsad mängd minne och stapeln växer upp, så att tala, och högen, enligt till den här pilen, växer ned. Med andra ord, varje gång du ringer malloc, du får en skiva minne från ovan, då kanske en lite lägre, sedan lite lägre, varje gång du ringer malloc, högen, det är användning, är typ att växa, allt närmare och närmare till vad? Stapeln. Det gör detta verka som en bra idé? Jag menar, om det inte är riktigt klart vad du kan göra om du bara har en begränsad mängd minne. Men detta är ju dåligt. Dessa två pilar är på en krascha kurs för varandra. 

Och det visar sig att skurken, folk som är särskilt bra med programmering, och försöker hacka in i datorer, kan utnyttja denna verklighet. I själva verket, låt oss betrakta lite kodavsnitt. Så det här är ett exempel som du kan läsa om närmare på Wikipedia. Vi kommer att peka dig i artikeln om nyfikna. Men det finns en attack i allmänhet känd som buffertspill som har funnits så länge som människor har haft förmågan att manipulera datorns minne, i synnerhet i C. Så det här är ett mycket godtyckligt program, men låt oss läsa det nerifrån och upp. Huvud in argC röding stjärna argv. Så det är ett program som tar kommandoradsargument. Och alla huvud gör tydligen är samtal en funktion, kalla det F för enkelhetens skull. Och det passerar i vad? Argv av en. Så det passerar in F oavsett ordet är att användaren har skrivit vid prompten efter programmets namn alls. Så mycket som Caesar eller Vigenère, som Du kanske kommer ihåg att göra med argv. 

Så vad är F? F tar i en sträng som enda argument, AKA en röding stjärna, samma sak, som en sträng. Och det kallas godtyckligt bar i detta exempel. Och sedan char c 12, bara i lekmannaspråk, vad är char c fästet 12 gör för oss? Hur är det att göra? Allokering av minne, speciellt 12 byte för 12 tecken. Exakt. Och sedan den sista raden, rör om och kopia, har du antagligen inte sett. Detta är en sträng kopia funktion vars syfte i livet är att kopiera sitt andra argument i sitt första argument, men bara upp till en visst antal bitgrupper. Så det tredje argumentet säger, hur många bytes bör du mig? Längden på bar, oavsett användaren har skrivit in. Och innehållet i bar, den strängen, är kopieras till minnet pekade på vid C. 

Så detta verkar vara lite dum, och det är. Det är en konstruerad exempel, men det är representativt av en klass av attack vektorer ett sätt att angripa ett program. Allt är fint och bra om användaren typer i ett ord som är 11 tecken eller färre, plus backslash noll. Vad händer om användaren skriver i mer än 11 eller 12 eller 20 eller 50 tecken? Vad är det här programmet kommer att göra? Potentiellt seg fel. Det går blint kopiera allt i bar upp med dess längd, som är bokstavligen allt i bar, i adress pekade på C. Men C har endast förebyggande syfte ges som 12 byte. Men det finns ingen ytterligare kontroll. Det finns inget om förhållandena. Det finns ingen felkontroll här. 

Och så vad detta program är kommer att göra är bara blint kopiera en sak till en annan. Och så om vi dra denna som en bild, här är bara en flisa av minnesutrymmet. Så märker på botten, vi har den lokala variabeln baren. Så att pekare som kommer att store-- snarare att lokal argument som är kommer att lagra strängen bar. Och sedan märker bara över den i en stapel, eftersom varje gång du frågar för minnes på stacken, Det går lite ovanför pictorially, märker att vi har 12 byte där. Den övre vänstra är C fäste noll och det nedre högra en är Ci konsol 11. Det är bara hur datorerna kommer att lägga ut det. Så bara intuitivt, om bar har mer än 12 tecken totalt, inklusive backslash noll, där är 12 eller C fästet 12 kommer att gå? Eller snarare var är den 12: e förmåga eller 13 tecken, hundrade karaktär går att hamna i bilden? Över eller under? 

Höger, för även om stapeln själv växer uppåt, När du har lagt saker i det, konstruktionstekniska skäl, sätter minnet från topp till botten. Så om du har mer än 12 byte, du kommer att börja skriva bar. Nu det är en bugg, men det är egentligen inte en big deal. Men det är en stor sak, eftersom det finns mer grejer på gång i minnet. Så här är hur vi kanske sätta hej, att vara tydlig. Om jag skrev i hello vid prompten. H-E-L-L-O snedstreck noll, hamnar inom dessa 12 bytes, och vi är mycket säkra. Allt är bra. Men om jag skriver något längre, potentiellt är det kommer att krypa in bar utrymme. Men ännu värre, visar det ut hela tiden, även om vi aldrig har talat om Det är stacken används för andra saker. Det är inte bara lokala variabler. 

C är ett språk mycket låg nivå. Och det slags hemlighet använder stapeln också att komma ihåg när ett funktionen kallas, vad adressen är av den föregående funktion, så det kan gå tillbaka till denna funktion. Så när huvud samtal byta, bland de saker skjutas på stacken är inte bara byter lokala variabler, eller sina argument, också i hemlighet drivit på stacken såsom representeras av den röda skivan här, är adressen till huvud fysiskt i datorns minne, så att när växlings är gjort, datorn vet att jag måste gå tillbaka till huvud och avsluta exekvera den viktigaste funktionen. Så det här är farligt nu, för om användaren skriver på väl mer än hej, sådan att användarens indata clobbers eller skriver att röda delen, logiskt om datorns bara att blint anta att de bytes i den röda skiva är adressen som den ska returnera, vad händer om motståndaren är smart nog eller turen att sätta en sekvens av bytes Det som ser ut som en adress, men det är adressen till koden att han eller hon vill ha datorn att köra i stället för huvud? 

Med andra ord, om det som användaren är att skriva vid prompten, är inte bara något ofarlig som hej, men det är faktiskt kod som är likvärdig att ta bort alla här användarens filer? Eller mejla sitt lösenord till mig? Eller börja logga deras tangenttryckningar, eller hur? Det finns ett sätt, låt oss fastställa dag, att de kunde skriva in inte bara hej värld eller deras namn, de kunde i huvudsak passera kod, nollor och sådana, att datorn misstag för både kod och en adress. Så om än något abstrakt, om användartyper i tillräckligt kontradiktoriska kod att vi ska generalisera här som A. A är attack eller motståndare. Så bara dåliga grejer. Vi bryr oss inte om siffror eller nollor och ettor idag, så att du hamnar skrivs det röda delen, märker att bytesekvensen. O 835 C noll åtta noll. Och nu som Wikipedias artikel här har föreslagit, om du nu verkligen börjar märkning av byte i datorns minne, vad Wikipedia artikeln föreslå är att, tänk om adressen av det övre vänstra byte är 80 C 0 3508. 

Med andra ord, om den onde är smart nog med hans eller hennes kod att faktiskt sätta ett antal här som motsvarar adressen av koden han eller hon injicerade i datorn, du kan lura datorn till att göra någonting. Ta bort filer, e-post saker, sniffa din trafik, bokstavligen allt kan vara sprutas in i datorn. Och så en buffer overflow attack i sin kärna är bara en dum, dum tvingande av en matris som inte har sina gränser kontrolleras. Och detta är vad är super farligt och samtidigt super kraftfull i C är att vi har faktiskt tillgång till någonstans i minnet. Det är upp till oss, programmerare, som skriver den ursprungliga koden att kontrollera allra längden på arrayer som vi manipulerar. Så för att vara tydlig, vad är fix? Om vi ​​rullar tillbaka till denna kod, jag borde inte bara ändra längden på baren, vad annars ska jag kontrollera? Vad ska jag göra för att förhindra denna attack helt? Jag vill inte bara blint säga att du bör kopiera så många bytes som är längden på baren. Jag vill säga, kopiera som många bytes som finns i bar upp till den tilldelade minne, eller 12 maximalt. Så jag behöver någon form av om tillstånd som gör kontrollera längden på baren, men om den överstiger 12, vi bara hårdkoda 12 som den största möjliga avstånd. Annars så kallade buffert overflow attack kan hända. Längst ner på dessa bilder, Om du är nyfiken på att läsa mer är den faktiska ursprungliga artikeln Om du vill ta en titt. 

Men nu, bland priserna betalade här var ineffektivitet. Så det var en snabb låg look nivå på vad problem kan uppstå nu när vi har tillgång till datorns minne. Men ett annat problem som vi redan snubblat på måndag var bara ineffektivitet av en länkad lista. Vi är tillbaka till linjär tid. Vi har inte längre en sammanhängande matris. Vi har inte random access. Vi kan inte använda klammer notation. Vi har bokstavligen att använda en while-slinga som jag skrev för en stund sedan. Men på måndag, hävdade vi att vi kan krypa tillbaka in i sfären av effektivitet uppnå något som är logaritmisk kanske, eller bästa ännu, kanske till och med något som är s.k. konstant tid. Så hur kan vi göra det genom att använda dessa nya verktyg, dessa adresser, dessa pekare, och gäng saker i vår egen? Tja, antar att här, det är ett gäng av siffror som vi vill lagra i en datastruktur och sökning effektivt. Vi kan absolut spola tillbaka till vecka två, kasta dessa i en matris, och söka dem med binär sökning. Söndra och härska. Och i själva verket du skrev binär sökning i PSET3, där du genomfört hitta programmet. Men vet du vad. Det är lite av en mer smart sätt att göra detta. Det är lite mer sofistikerade och det kanske tillåter oss att se varför binära Sökningen är så mycket snabbare. Låt oss först införa föreställningen av ett träd. Vilket även om det i reality träd typ av växa så här, i en värld av dator vetenskap de slags växa nedåt som ett släktträd, där du har dina morföräldrar eller stora morföräldrar eller allt på toppen, patriarken och matriark av familjen, bara en s.k. rot, nod, nedan som är dess barn, under vilken det är dess barn, eller dess ättlingar mer allmänt. Och den hängande botten av familjen träd, förutom att vara den yngst i familjen, kan också bara vara generiskt kallas blad av trädet. 

Så det här är bara ett gäng ord och definitioner för något som kallas ett träd i dator vetenskap, ungefär som ett släktträd. Men det finns snyggare inkarnationer av träd, en av vilka kallas ett binärt sökträd. Och du kan typ av tease isär vad den här saken gör. Tja, det är binär i vilken mening? Varifrån kommer den binära kommer härifrån? Förlåt? Det är inte så mycket ett antingen eller. Det är mer att var och en av noderna har ingen mer än två barn, som vi ser här. I allmänhet är ett tree-- och dina föräldrar och farföräldrar kan ha så många barn eller barnbarn som de faktiskt vill, och så till exempel där har vi tre barn utanför den högra noden, men i ett binärt träd, har en nod noll, en eller två barn maximalt. Och det är en bra egenskap, för om det är täckt av två, vi kommer att kunna få lite log bas två åtgärder som pågår här i slutändan. Så vi har något logaritmisk. Men mer om det i ett ögonblick. Sökträd innebär att siffrorna är anordnade så att den vänstra barnets värdet är större än roten. Och dess rätt barn är större än roten. Med andra ord, om du tar något av noder, cirklarna i den här bilden, och tittar på dess vänstra barn och dess rätt barn, den första bör vara mindre än, den andra bör vara större än. Så sanity ta 55. Det som är kvar barnet är 33. Det är mindre än. 55, är dess högra underordnade 77. Det är större än. Och det är en rekursiv definition. Vi kan kontrollera varenda en av dem noder och samma mönster skulle hålla. 

Så vad är trevligt i en binärt sökträd, är att man kan vi genomföra det med en struct, precis som detta. Och även om vi kastar massor av strukturer på din, de är något intuitiv nu förhoppningsvis. Syntaxen är fortfarande svårbegripliga för säker, men innehållet i en nod i detta context-- och vi håller använda ordet nod, oavsett om det är en rektangel på skärmen eller en cirkel, Det är bara några generiska behållare, i detta fall av ett träd, som en vi såg, vi behöver ett heltal i var och en av noderna och då jag behöver två pekare pekar till vänster barnet och högra underordnade, respektive. Så det är hur vi kanske genomföra detta i en struct. Och hur kan jag genomföra det i koden? Nåväl, låt oss ta en snabb titta på denna lilla exempel. Det är inte funktionell, men jag har kopierat och klistrat denna struktur. Och om min funktion för en binär sökträd kallas sökning, och detta tar två argument, ett heltal N och en pekare till en nod, så en pekare till trädet eller en pekare till roten av ett träd, Hur gör jag för att söka efter N? Tja, först, eftersom jag är behandlar pekare, Jag kommer att göra en sanity check. Om träd jämlikar är lika med noll, är N I det här trädet eller inte i detta träd? Det kan inte vara rätt? Om jag förbi null, det finns inget där. Jag kan lika gärna bara blint säger return false. Om du ger mig ingenting, jag kan ju inte hitta valfritt antal N. Så vad mer jag kan Kontrollera nu? Jag kommer att säga bra annars om N är mindre än vad som är på trädet noden att jag har gått i arv N-värdet. Med andra ord, om numret är jag söker, N, är mindre än den nod att jag tittar på. Och noden jag ser vid kallas träd, och minns från föregående exempel att komma åt värdet i en pekare, Jag använder pilen notation. Så om N är mindre än träd pil N, jag vill begrepps gå vänster. Hur gör jag uttrycker SÖKA kvar? För att vara tydlig, om detta är bilden i fråga, och jag har gått att översta arrow som är pekar nedåt. Det är mitt träd pekare. Jag pekar på roten av trädet. Och jag ser att säga, för siffran 44, godtyckligt. Är 44 mindre än eller större än 55 självklart? Så det är mindre än. Och så detta om villkor gäller. Så begreppsmässigt, vad jag vill Sök nästa om jag letar efter 44? Yeah? 

Just det, jag vill söka i vänstra underordnade, eller vänster underträd av denna bild. Och i själva verket, låt mig igenom bilden här nere för bara ett ögonblick, eftersom Jag kan inte repa detta. Om jag börjar här vid 55, och Jag vet att värdet 44 Jag letar efter är att vänster, det är typ som att riva telefonboken i halv eller riva trädet på mitten. Jag behöver inte längre bry sig om hela denna hälften av trädet. Och ändå, märkligt i termer av struktur, denna sak hit att börjar med 33, som i sig är ett binärt sökträd. Jag sa ordet rekursiva innan eftersom faktiskt detta är en datastruktur som per definition är rekursiv. Du kanske har ett träd som det här stor, men var och en av sina barn representerar ett träd bara lite mindre. I stället för att det är morfar eller mormor, nu är det bara mamma eller-- jag kan inte säga-- inte mamma eller pappa, skulle det vara konstigt. Istället de två barnen där skulle vara som bror och syskon. En ny generation av släktträdet. Men strukturellt, det är samma idé. Och det visade sig att jag har en funktion som jag kan söka en binär sökning träd. Det kallas sökning. Jag söker efter N träd pil vänster annars om N är större än värdet att jag är för närvarande på. 55 i berättelsen för en stund sedan. Jag har en funktion som kallas sökmotor som jag kan bara passera N detta och rekursivt söka sub-trädet och bara avkastning vad det svaret. Annars har jag några slutliga bas fallet här. 

Vad är det sista fallet? Tree är antingen noll. Värdet jag antingen letar efter är mindre än den eller större än den eller lika med det. Och jag kunde säga lika lika, men logiskt är det motsvarar bara säga annat här. Så sant är hur jag hittar något. Så förhoppningsvis är ett ännu mer övertygande exempel än den dumma sigma funktionen Vi gjorde några föreläsningar tillbaka, där det var lika enkelt att använda en slinga att räkna upp alla nummer från en till N. Här med en datastruktur som i sig själv är rekursivt definierade och rekursivt dras, nu vi har förmågan att uttrycka oss i kod som själv är rekursiv. Så det här är exakt samma kod här. 

Så vad andra problem kan vi lösa? Så en snabb steg bort från träd för bara ett ögonblick. Här är, säger den tyska flaggan. Och det är helt klart en mönstret till denna flagga. Och det finns massor av flaggor i världen som är så enkla som detta i termer av deras färger och mönster. Men antag att detta lagras som en GIF, eller JPEG eller bitmapp, eller en ping, något grafiskt filformat som du är bekant, varav vi är leka med i PSET4. Detta verkar inte värt att lagra svart pixel, svart pixel, svart pixel, dot, punkt, punkt, en massa svarta pixlar för den första avsökningsraden, eller rad, sedan en massa densamma, sedan en hel drös av densamma, och sedan en massa röda pixlar, röda pixlar, röda pixlar, sedan en hel gäng gula pixlar, gul, eller hur? 

Det är en sådan ineffektivitet här. Hur skulle du intuitivt komprimera den tyska flaggan om att genomföra det som en fil? Liksom vilken information kan vi inte bry lagring på disk för att minska vår filstorleken från liknande en megabyte till ett kilobyte, något mindre? Vari ligger redundans här för att vara klart? Vad kan du göra? Yeah? Exakt. Varför inte i stället minnas färgen på varje darn pixel precis som du gör i PSET4 med bitmap-format, varför inte du bara representera vänstra kolumnen av pixlar, t.ex. ett gäng svarta pixlar, ett gäng rött, och ett gäng gul, och sedan bara något koda idé upprepa detta 100 gånger eller upprepa detta 1000 gånger? Där 100 eller 1000 är bara ett heltal, så att du kan komma undan med bara ett enda nummer i stället för hundratals eller tusentals av ytterligare pixlar. Och faktiskt, det är hur vi kan komprimera den tyska flaggan. Och Nu vad om fransk flagg? Och lite något slags mental träning, vilken flagga kan komprimeras mer på disk? Den tyska flaggan eller franska flagga, om vi tar detta synsätt? Den tyska flaggan, eftersom det finns mer övergripande redundans. Och genom design, många grafiska filen format gör verkligen fungerar som sveplinjer horisontellt. De kunde arbeta vertikalt, precis mänskligheten beslutade år sedan att vi ska i allmänhet tänka på saker rad genom rad istället för kolumn för kolumn. Så ja om du var att titta på filen storleken på en tysk flagga och en fransk flagga, så länge som upplösningen är samma, samma bredd och höjd, här här kommer att bli större, eftersom du måste upprepa dig tre gånger. Du måste ange blått, upprepa själv, vit, upprepa dig själv, rött, upprepa dig själv. Du kan inte bara gå alla vägen till höger. Och som en sidoreplik, att göra rensa kompression är överallt, om dessa fyra bildrutor från en video-- du kanske kommer ihåg att en film eller video är i allmänhet som 29 eller 30 bilder per sekund. Det är som en liten blädderbok där du bara se bild, bild, bild, bild, image bara supersnabb så det ser ut aktörerna på skärmen rör sig. Här är en humla på toppen av en blombukett. Och även om det kan vara typ av svårt att se vid första anblicken, det enda som rör sig i den här filmen är biet. 

Vad är dum om att lagra video okomprimerad? Det är typ av avfall för att lagra video som fyra nästan identiska bilder som skiljer sig endast i den mån där biet är. Du kan kasta bort det mesta av denna information och minns bara, till exempel, den första ramen och den sista ramen, nyckelrutor Om du har någonsin hört ordet, och bara lagra i mitten där biet är. Och du behöver inte lagra alla rosa, och det blå, och gröna värden. Så detta är att bara säga att komprimering är överallt. Det är en teknik som vi använder ofta eller tar för givet dessa dagar. 

Men hur gör du komprimera text? Hur går du om att komprimera texten? Tja, vart och ett av tecknen i ASCII är en bitgrupp, eller åtta bitar. Och det är ganska dum, eller hur? Eftersom du förmodligen typ A och E och I och O och U mycket oftare än som W eller Q eller Z, beroende på vilket språk du skriver verkligen. Och så varför använder vi åtta bitar för varje bokstav, inklusive minst populära bokstäver, eller hur? Varför inte använda färre bitar för super populära bokstäver, som E, de saker du gissa först i Wheel of Fortune, och använda fler bitar för mindre populära breven? Varför? Eftersom vi bara kommer att använder dem mindre ofta. 

Tja, visar det sig att det har kommit försök gjorts för att göra detta. Och om du minns från årskurs skolan eller gymnasiet, morsekod. Morsekod har prickar och streck som kan vara överförs utmed en tråd som ljud eller signaler av någon form. Men morsekod är en super clean. Det är lite av en binär system att du har prickar eller streck. Men om du ser, till exempel, två punkter. Eller om du tänker tillbaka till operatören som går som pip, pip, pip, pip, slå en liten trigger som sänder en signal, om du, mottagaren, får två prickar, vilket budskap har du fått? Helt godtyckligt. 

Jag? Jag? Eller vad about-- eller jag? Kanske var det bara två E rätt? Så det finns detta problem av decodability med Morse kod, varmed om inte den person som skickar meddelandet du faktiskt paus så att du kan sortera av se eller höra klyftorna mellan bokstäverna, det är inte tillräckligt att endast skicka en ström av ettor och nollor, eller prickar och streck, eftersom det finns tvetydighet. E är en enda prick, så om du se två punkter eller höra två punkter, kanske är det två E: s eller kanske är det ett I. Så vi behöver ett system som är en lite mer smart än så. Så en man vid namn Huffman år sedan kom fram till just detta. Så vi ska bara att ta en snabb blick hur träden är relevant för detta. Antag att detta är någon dum meddelande som du vill skicka, sammansatt av bara A, B, C: s D: s och E: s, men det finns en hel del redundans här. Det är inte tänkt att vara engelska. Det är inte krypterad. Det är bara en dum meddelande med massor av upprepning. Så om du verkligen räkna ut alla A: s, B: s, C: s, D's, och E-talet, här är frekvensen. 20% av bokstäverna är A: s, 45% av bokstäverna är E-talet, och tre andra frekvenser. Vi räknade upp det manuellt och bara gjorde matten. 

Så visar det sig att Huffman, för en tid sedan, insett att du vet vad, om jag börjar byggnad ett träd eller skog av träd, om ni så vill, enligt följande, kan jag göra följande. Jag kommer att ge en nod för varje av de brev som jag bryr mig om och jag kommer att lagra insidan av denna nod frekvenserna som ett flyttal värde, eller så kan du använda det en N, också, men vi bara använda en flottör här. Och algoritmen som han föreslog är att du ta denna skog av enda nod träd, så super korta träd, och du börjar ansluta dem med nya grupper, nya föräldrar, om du kommer. Och du gör det genom att välja två minsta frekvenserna åt gången. Så jag tog 10% och 10%. Jag skapar en ny nod. Och jag kallar den nya noden 20%. 

Vilka två noder jag kombinera nästa? Det är lite tvetydigt. Så det finns vissa hörn fall till överväga, men att hålla saker ganska, Jag kommer att välja 20% - Jag ignorerar nu barnen. Jag kommer att välja 20% och 15% och rita två nya kanter. Och nu som två noder jag logiskt kombinera? Ignorera alla barn, alla barnbarn, titta bara på rötterna nu. Vilka två noder jag knyta ihop? Punkt två och 0,35. Så låt mig rita två nya kanter. Och då har jag bara fått en vänster. Så här är ett träd. Och det dragits medvetet att titta slags söt, men märker att kanterna har även märkts noll och ett. Så alla de vänsterkant är noll godtyckligt, men konsekvent. Alla högra kanten är sådana. 

Och så vad Hoffman föreslagna, Om du vill representera en B, snarare än representerar antal 66 som en ASCII som är åtta hela bitar, vet du vad, bara butiken mönstret noll, noll, noll, noll, eftersom det är den väg från mitt träd, Mr. Huffman träd, till bladet från roten. Om du vill spara en E, däremot, inte skicka åtta bitar som representerar ett E. Istället skickar vilket mönster bitar? En. Och vad är trevligt om det här är att E är den mest populära brev, och du använder kortaste kod för det. Den näst mest populära brev ser ut som det var A. Och så hur många bitar gjorde han föreslår att använda för det? Noll, en. 

Och eftersom det är genomförs som detta träd, för nu Låt mig fastställa att det finns ingen tvetydighet som i Morse kod, eftersom alla bokstäver du bryr dig om är i slutet av dessa kanter. Så det är bara en applicering av ett träd. Detta är-- och jag våg min hand på hur du kan genomföra detta som en C-struktur. Vi behöver bara kombinera en symbol, som en röding, och frekvensen i vänster och höger. Men låt oss titta på två slutliga exempel som du kan bli ganska bekant med efter quiz noll problem set fem. 

Så det finns datastrukturen känd som en hashtabell. Och en hashtabell är typ av kyla genom att den har hinkar. Och antar att det finns fyra hinkar Här, bara fyra tomma utrymmen. Här är en kortlek, och här är klubb, spade, klubba, diamanter, klubba, diamanter, klubba, diamanter, clubs-- så detta är slumpmässigt. Hearts, Hearts-- så jag är bucketizing alla ingångarna här. Och en hashtabell behöver att titta på din input, och sedan lägga den i en viss Placera baserat på vad du ser. Det är en algoritm. Och jag använde en super enkel visuell algoritm. Den svåraste delen av som var komma ihåg vad bilderna var. Och sedan finns det fyra totalt saker. 

Nu travar växte, vilket är en avsiktlig konstruktion sak här. Men vad kan jag göra? Så faktiskt här vi har en gäng gamla skolan examen böcker. Antag att ett gäng elevernas namn är här. Här är en större hash-tabell. I stället för fyra hinkar, Jag har, låt oss säga 26. Och vi ville inte gå låna 26 saker från utsidan [? Annenberg?], Så Här är fem som representerar A till Z. Och om jag se en student vars namn börjar med A, Jag kommer att sätta sin frågesport där. Om någon börjar med C, där borta, A-- faktiskt, inte vill göra det. B går hit. Så jag har A och B och C. And nu här är en annan student. Men om detta hash-tabell är genomförs med en array, Jag slags skruvad vid denna tidpunkt, eller hur? Jag slags behöver för att sätta den här någonstans. 

Så ett sätt jag kan lösa detta är, allt höger, är en upptagen, B är upptagen, C är upptagen. Jag kommer att sätta honom i D. Så vid först, jag har random omedelbar tillgång till var och en av skopor till eleverna. Men nu är det typ av decentraliserade till något linjär, för om jag vill söka efter någon vars namn börjar med A, kolla jag här. Men om detta inte är en elev jag letar efter, Jag slags måste börja kontrollera hinkar, eftersom vad jag gjorde var typ av linjärt sond datastrukturen. En dum sätt att säga bara titta för första tillgängliga öppningen, och satte som en plan B, så att säga, eller en plan D i detta fall värdet på den platsen i stället. Detta är bara så att om du har fick 26 platser och inga studenter med namnet Q eller Z, eller något liknande att åtminstone du använder utrymmet. 

Men vi har redan sett mer smarta lösningar här, eller hur? Vad skulle du göra istället Om du har en kollision? Om två personer har namnet A, vad skulle har varit ett smartare eller mer intuitiv lösning än bara sätta A där D är tänkt att vara? Varför jag inte bara gå utanför [? Annenberg?], som malloc, en annan nod, uttryckte det här, och sedan lägga att en student här. Så att jag har väsentligen någon form av en matris, eller kanske mer elegant som vi är börjar se en länkad lista. 

Och så en hashtabell är en struktur som kan se ut precis som detta, men mer skickligt, du något som kallas separat kedja, varvid en hashtabell helt enkelt är en array, vart och ett av vars element är inte ett nummer, själv är en länkad lista. Så att du får supersnabb tillgång besluta om att hash ditt värde för. Ungefär som med kort exempel Jag gjorde super snabba beslut. Hjärtan går här, diamanter går här. Samma här, går A här, D går här, B går här. Så supersnabb uppslagningar, och om du råkar stöta på ett fall där du har fått kollisioner, två personer med samma namn, ja då du bara börja länka ihop dem. Och kanske du hålla dem sorterade alfabetiskt, kanske du inte. Men åtminstone nu har vi dynamik. Så å ena sidan har vi supersnabb konstant tid, och typ av linjär tid inblandade om dessa länkade listor börjar bli lite lång. 

Så denna typ av en dum, geeky skämt år sedan. Vid CS50 hacka-a-thon, när eleverna checkar in, vissa TF eller CA varje år tycker att det är roligt att sätta upp ett tecken som detta, där det bara innebär att om ditt namn börjar med en A, gå denna väg. Om ditt namn börjar med ett B, gå this-- OK, det är roligt kanske senare under terminen. Men det finns en annan sätt att göra detta också. Kom tillbaka till det. 

Så det finns denna struktur. Och detta är vår sista struktur för idag, vilket är något som kallas en trie. T-R-I-E, som av någon anledning är kort för hämtning, men det heter trie. Så en trie är en annan intressant blandning av en hel del av dessa idéer. Det är ett träd, som vi har sett förut. Det är inte ett binärt sökträd. Det är ett träd med valfritt antal barn, men vart och ett av barnen i en trie är en array. En array av storlek, säger, 26 eller kanske 27 Om du vill stödja bindestreck namn eller apostrofer i människors namn. 

Och så detta är en datastruktur. Och om man tittar uppifrån till botten, precis som om du titta på toppnoden där, M, är pekar på vänstra sak där, vilken sedan A, X, W, E, L, L. Detta är bara en datastruktur som godtyckligt lagrar människors namn. Och Maxwell lagras genom att bara följa en väg av matris till matris till matris. Men vad som är fantastiskt om en trie är att, medan en länkad lista och även en array, är det bästa som vi någonsin har fått linjär tid eller logaritmisk tid på att leta upp någon. I denna datastruktur av en trie, om min datastruktur har ett namn i det och jag letar efter Maxwell, jag kommer att hitta honom ganska snabbt. Jag ser bara för M-A-X-W-E-L-L. Om denna datastruktur, däremot, Om N är en miljon, om det finns en miljoner namn i denna datastruktur, Maxwell fortfarande kommer att vara upptäckbar efter bara M-A-X-W-E-L-L steg. Och David-- D-A-V-l-D steg. Med andra ord, genom att bygga en datastruktur som är fick alla dessa matriser, vilka alla själva stöder random access, Jag kan börja leta upp människors namn med en tid som är proportionell mot inte antalet saker i datastrukturen, som en miljon befintliga namn. Hur lång tid det tar mig att hitta M-A-X-W-E-L-L i denna datastruktur är proportionell inte till den storleken av den datastruktur, men till längden av namnet. Och realistiskt namn vi letar upp kommer aldrig att vara galen lång. Kanske någon har en 10 tecken namn, 20 teckennamn. Det är verkligen begränsad, eller hur? Det finns en människa på jorden som har den längsta möjliga namn, men det namnet är en konstant värde längd, eller hur? Det varierar inte på något sätt. Så på detta sätt, vi har uppnått en datastruktur som är konstant tidsuppslags. Det tar ett antal steg beroende på längden av den ingående, men inte antalet namn i datastrukturen. Så om vi fördubbla antalet namn nästa år från en miljard till två miljarder kronor, slutsats Maxwell kommer att ta exakt samma antal sju steg att hitta honom. Och så vi tycks ha uppnått vår heliga graal gångtid. 

Så ett par snabba meddelanden. Quiz noll kommer upp. Mer om det på kursens hemsida under de kommande dagarna. Måndagens lecture-- det är en helgdag här på Harvard på måndag. Det är inte i New Haven, så vi tar klassen New Haven för föreläsning på måndag. Allt kommer att filmas och streamas live som vanligt, men låt oss avsluta idag med en 30 sekunders klipp kallade "djupa tankar" av Daven Farnham, som inspirerades förra året med lördag Night Live: s "djupa tankar" av Jack Handy, som bör nu vara meningsfullt. 

FILM: Och nu, "Djup Tankar "av Daven Farnham. Hashtabell. 

TALARE 1: Okej, det är det för nu. Vi ses nästa vecka. 

DOUG: För att se det i handling. Så låt oss ta en titt på det just nu. Så här har vi en osorterad array. 

IAN: Doug, kan du gå vidare och starta om detta för bara en sekund, snälla. Okej, är kamerorna rullar, så åtgärd när du är klar, Doug, OK? DOUG: Okej, så vad vi har här är en osorterad array. Och jag har färgat alla element rött för att indikera att det är i själva verket, osorterat. Så minns att det första vi gör är vi sorterar vänstra halvan av gruppen. Då kan vi sortera rätt halv av arrayen. Och ya-da, ya-da, ya-da, Vi sammanfoga dem tillsammans. Och vi har en helt sorterad array. Så det är hur merge sort fungerar. 

IAN: Whoa, whoa, whoa, cut, cut, cut, cut. Doug kan du inte bara ya-da, ya-da, ya-da, din väg genom sammanslagning slag. 

DOUG: Jag gjorde bara. Det är bra. Vi är bra att gå. Låt oss bara hålla rullande. Så hur som helst, 

IAN: Du måste förklara det mera fullständigt än så. Det är bara inte tillräckligt. DOUG: Ian, gör vi inte behöver gå tillbaka till en. Det är bra. Så hur som helst, om vi fortsätter med merge-- Ian, vi är mitt i inspelningen. 

IAN: Jag vet. Och vi kan inte bara ya-da, ya-da, ya-da, genom hela processen. Du måste förklara hur två sidor slås ihop. 

DOUG: Men vi har redan förklarade hur de två sides-- 

IAN: Du har just visat dem en sammanfogning matris. DOUG: De vet processen. De är bra. Vi har gått över den tio gånger. 

IAN: Du hoppade precis rätt över det. Vi kommer tillbaka till en, kan du inte ya-da, ya-da över den. Okej, tillbaka till en. 

DOUG: Jag måste gå tillbaka igenom alla bilderna? Herregud. Det är som sjätte gången, Ian. Det är bra. 

IAN: Okej. Är du redo? Bra. Action.