Högtalare 1: Okej, så vi är tillbaka. Välkommen till CS50. Detta är slutet på vecka sju. Så minns att förra gången började vi titta på något mer sofistikerade datastrukturer. Sedan fram till nu, allt vi hade verkligen till vårt förfogande var här, en matris. Men innan vi kasta arrayen som inte så intressant, som det faktiskt egentligen är, vad är några av de plussidan av denna enkla uppgifter struktur hittills? Vad är det bra på? Så vitt vi har sett? Vad har du? Ingenting. STUDENT: [OHÖRBAR]. Högtalare 1: Vad är det? STUDENT: [OHÖRBAR]. Högtalare 1: Fast storlek. OK, så varför är fast storlek bra ändå? STUDENT: [OHÖRBAR]. Högtalare 1: OK, så det är effektivt i den meningen att du kan tilldela ett fast belopp på utrymme, vilket förhoppningsvis är precis lika mycket utrymme som du vill. Så det skulle vara absolut ett plus. Vad är en annan upp sidan av en matris? Yeah? STUDENT: [OHÖRBAR]. Högtalare 1: Alla - förlåt? STUDENT: [OHÖRBAR]. Högtalare 1: Alla rutorna i minnet eller bredvid varandra. Och det är till någon hjälp - varför? Det är helt sant. Men hur kan vi utnyttja denna sanning? STUDENT: [OHÖRBAR]. Högtalare 1: Exakt, kan vi hålla koll på där allt är bara genom att veta en adress, nämligen adressen för första byte i denna bit av minnet. Eller i fallet av strängen, adressen för den första röding i den strängen. Och därifrån kan vi hitta slutet av strängen. Vi hittar det andra elementet, tredje element, och så vidare. Och så fint sätt att beskriva det funktion är att matriser ger oss random access. Bara med hjälp av klammer notation och ett nummer, kan du hoppa till ett specifikt element i arrayen i konstant tid, big O av en, så att säga. Men det har varit några nackdelar. Vad en array inte mycket lätt? Vad det är inte bra på? STUDENT: [OHÖRBAR]. Högtalare 1: Vad är det? STUDENT: [OHÖRBAR]. Högtalare 1: Utöka i storlek. Så baksidorna av arrayen är precis motsatsen till vad upsides är. Så en av de avigsidor är att det är en fast storlek. Så du kan inte riktigt odla den. Du kan omfördela en större bit av minne, och sedan flytta de gamla elementen i den nya arrayen. Och sedan fri den gamla arrayen, för exempel, genom att använda malloc eller en liknande Funktionen kallas realloc, vilket omfördelar minne. Realloc, som åt sidan, försöker att ge dig minne som är bredvid array att du redan har. Men det kan röra sig saker runt helt och hållet. Men kort sagt, det är dyrt, eller hur? För om du har en bit av minnet av denna storlek, men du vill verkligen en av denna storlek, och du vill bevara de ursprungliga element, måste du ungefär en linjär tid kopieringen som måste ske från gamla array till nya. Och verkligheten är att be operativsystemet systemet igen och igen och igen för stora bitar av minnet kan börja att kosta dig lite tid också. Så det är både en välsignelse och en förbannelse i dölja det faktum att dessa matriser är av fast storlek. Men om vi inför i stället något som denna, som vi kallade en länkad lista, får vi några upsides och några nackdelar här också. Så en länkad lista är helt enkelt en data struktur som består av C-structs i detta fall, där en struct, återkallelse, är bara en behållare för en eller flera särskilda typer av variabler. I det här fallet, vad gör de datatyper verkar vara inne i struct som förra gången vi ringde en nod? Var och en av dessa rektanglar är en nod. Och var och en av de mindre rektanglar insidan av det är en datatyp. Vilka typer gjorde vi säger de var på måndag? Yeah? STUDENT: [OHÖRBAR]. SPEAKER 1: En variabel och en pekare, eller mer specifikt, en int, för n, och en pekare på botten. Båda av dem råkar vara 32 bitar, på åtminstone på en dator som denna CS50 Appliance, och så de är dras lika i storlek. Så vad använder pekaren men för tydligen? Varför lägga till denna pil nu när arrayer var så fin och ren och enkel? Vad pekaren gör för oss i alla dessa noder? STUDENT: [OHÖRBAR]. SPEAKER 1: Exakt. Det är att berätta om nästa är. Så jag slags använder analogin av med hjälp av en tråd att sortera på trär dessa noder tillsammans. Och det är precis vad vi gör med pekare eftersom var och en av dessa bitar av minnet kan eller inte kan vara sammanhängande, rygg mot rygg mot rygg insidan av RAM, eftersom varje gång du ringa malloc säger, ge mig tillräckligt byte för en ny nod, kanske det vara här eller det kan vara här. Det kan vara här. Det kan vara här. Du vet bara inte. Men att använda pekare i adresser dessa noder, kan du sy dem tillsammans på ett sätt som ser visuellt som en lista även om dessa saker är alla utspridda över din ena eller dina två eller dina fyra gigabyte RAM-minne insidan av din egen dator. Så nedsidan, då, om en länkad lista är vad? Vad är ett pris vi är tydligen betalar? STUDENT: [OHÖRBAR]. Högtalare 1: Mer utrymme, rätt? Vi har, i detta fall, fördubblades mängden utrymme eftersom vi har gått från 32 bitar för varje nod, för varje int, så nu 64 bitar för att vi måste hålla runt en pekare liksom. Du får mer effektivitet om din struct är större än denna enkla sak. Om du har faktiskt en elev inne av vilket är ett par strängar för namn och hus, kanske ett ID-nummer, kanske några andra områden helt och hållet. Så om du har en tillräckligt stor struct, då kanske kostnaden för pekaren är inte så stor roll. Detta är en bit av ett hörn fall, eftersom vi lagrar sådan enkel primitiv insidan av den länkade listan. Men poängen är densamma. Du är definitivt spendera mer minne, men du får flexibilitet. För nu om jag vill lägga till ett element i början av denna lista, Jag måste allokera en ny nod. Och jag måste bara uppdatera dem pilar på något sätt genom att bara flytta några tips runt. Om jag vill infoga något i mitten av listan, behöver jag inte skjuta alla åt sidan som vi gjorde i veckor tidigare med våra volontärer som representerade en matris. Jag kan bara tilldela en ny nod och sedan bara peka på pilarna i olika riktningar eftersom den inte måste förbli i själva minne en riktig linje som jag har ritat det här på skärmen. Och sedan sist, om du vill infoga något i slutet av listan, det är ännu enklare. Detta är en slags godtycklig notation, men 34 pekare, ta en gissning. Vad är värdet av dess pekare mest sannolikt dras ungefär som en gammal skola antenn där? STUDENT: [OHÖRBAR]. Högtalare 1: Det är förmodligen noll. Och faktiskt det är en författares representation av null. Och det är null eftersom du absolut behöver veta var slutet på en länkad listan är, så att du håller efter och följa och följa dessa pilar till vissa skräp värde. Så null kommer att innebära att det inte finns någon fler noder till höger om numret 34, i det här fallet. Så vi föreslår att vi kan genomföra denna nod i koden. Och vi har sett den här typen av syntax innan. Typedef definierar bara en ny typ av oss, ger oss en synonym som string var för char *. I det här fallet, det kommer att ge oss stenografi notation så att struct node kan istället bara skrivas som nod, som är mycket renare. Det är mycket mindre mångordig. Inuti en nod är tydligen en int kallas n, och sedan en struct node * vilket betyder precis vad vi ville pilarna för att betyda, en pekare till en annan nod av exakt samma datatyp. Och jag föreslår att vi skulle kunna genomföra en sökfunktion som denna, som vid första anblicken kan tyckas lite komplicerat. Men låt oss se det i sitt sammanhang. Låt mig gå över till apparaten här. Låt mig öppna en fil som heter Listan noll prick timmar. Och som bara innehåller den definition vi såg bara en stund sedan att dessa uppgifter typ som kallas en nod. Så vi har lagt in det i en punkt h-fil. Och som en parentes, även om detta program som du är på väg att se är inte så komplicerat, det är sannerligen konvent när du skriver ett program för att sätta saker som datatyper, att dra konstanter ibland, insidan av dina header-fil och inte nödvändigtvis i din C-fil, säkert när din program blir större och större, så att du vet var du ska leta för både dokumentation i vissa fall, eller för grunderna som detta, de definition av någon typ. Om jag öppnar nu upp listan noll prick c, märker några saker. Den innehåller några header-filer, de flesta som vi har sett tidigare. Den innehåller en egen header-fil. Och som en parentes, varför det är dubbelt citat här, i motsats till den vinkel fästen på den linje som Jag har markerat det? STUDENT: [OHÖRBAR]. Högtalare 1: Ja, så det är en lokal fil. Så om det är en lokal fil på din egen här på rad 15, till exempel, använder du de dubbla citattecken i stället av de vinklade parentes. Nu är det här ganska intressant. Lägg märke till att jag har deklarerat en global variabel i detta program på rad 18 kallas första, är tanken att detta kommer att vara en pekare till den första nod i min länkad lista, och jag har initieras till null, eftersom jag har inte tilldelats någon faktisk noder ännu. Så detta innebär, bildmässigt, vad vi såg nyss på bilden som att pekaren på långt vänster sida. Så just nu, att pekaren har inte en pil. Det är istället bara null. Men det representerar vad som kommer att adressen för den första egentliga nod i denna lista. Så jag har genomfört det är en global eftersom, som ni ser, allt detta Programmet gör i livet är att genomföra en länkad lista för mig. Nu har jag ett par prototyper här. Jag beslutade att implementera funktioner som deletion, insertion, söka, och traversering - det sista bara vara promenad över lista, skrivs ut dess beståndsdelar. Och nu här är min viktigaste rutin. Och vi kommer inte att spendera alltför mycket tid på dessa eftersom det är typ av, förhoppningsvis förlegat nu. Jag kommer att göra följande, medan användaren samverkar. Så en, jag ska skriva ut ut denna meny. Och jag har formaterat den som rent som jag kunde. Om användaren skriver i ett, som innebär De vill ta bort något. Om användaren skriver i två, som innebär de vill infoga något. Och så vidare. Jag ska sedan be sedan för ett kommando. Och sen ska jag använda getInt. Så det här är en riktigt enkel menuing gränssnitt där du bara behöver skriva ett nummer mappning till en av dessa kommandon. Och nu har jag en fin ren switch uttalande som kommer att slå på vad användaren skrivit i. Och om de skrivit något, jag samtal bort och bryta. Om de skrivit två, jag ringa in och bryta. Och nu märker jag har lagt varje av dessa på samma linje. Detta är bara en stilistisk beslut. Normalt har vi sett något såhär. Men jag bestämde mig bara, ärligt talat, mitt program såg mer lättläst eftersom Det var bara fyra ärenden till bara lista det så här. Helt legitim användning av stil. Och jag kommer att göra det så länge Användaren har inte skrivit noll, vilket jag beslutat kommer att innebära att de vill sluta. Så nu märker vad jag ska göra här. Jag ska befria listan tydligen. Men mer om det på bara ett ögonblick. Låt oss först köra programmet. Så låt mig göra en större terminal fönster, dot slash lista 0. Jag ska gå vidare och sätter av skriva två, ett antal som 50, och nu ser du listan är nu 50. Och min text rullas bara upp lite. Så nu märker listan innehåller numret 50. Låt oss göra en insats genom att ta två. Låt oss skriva in numret som en. Lista är nu ett, följt av 50. Så det här är bara en textuell representation i listan. Och låt oss sätta ett fler antal som numret 42, vilket är förhoppningsvis kommer att hamna i mitten, eftersom detta program särskilt sorterar det element som den sätter dem. Så där har vi det. Super enkelt program som kunde absolut ha använt en array, men jag råkar använda en länkad lista bara så jag kan dynamiskt växa och krympa den. Så låt oss ta en titt för sökning, om jag köra kommandot tre, vill jag söka för, säg, antalet 43. Och ingenting var tydligen funnit, eftersom jag fick tillbaka inget svar. Så låt oss göra det igen. Sök. Låt söka 50 eller snarare search för 42, som har en fin lite subtil innebörd. Och jag hittade meningen med livet där. Nummer 42, om du inte vet referens, googla det. Okej. Så vad har detta program gjort för mig? Det är bara tillät mig att infoga därmed långt och sök efter element. Låt oss snabbspola framåt, då, att som fungerar vi sneglade på på måndagen som en teaser. Så denna funktion, hävdar jag, söker efter ett element i listan genom att först en, uppmanar användaren och sedan ringa GetInt att få en verklig int som du vill söka efter. Sedan märker detta. Jag kommer att skapa en temporär variabel i linje 188 kallas pekare - PTR - skulle ha kallat det något. Och det är en pekare till en nod eftersom jag sa nod * där. Och jag initierade den vara lika med först så att jag faktiskt har min finger, så att säga, på den mycket första elementet i listan. Så om min högra hand här är PTR jag pekar på samma sak som första pekar på. Så nu tillbaka i koden, vad som händer härnäst - detta är ett vanligt paradigm när iteration över en struktur som en länkad lista. Jag kommer att göra följande medan pekaren inte är lika med noll Så medan mitt finger pekar inte på några null värde, om Pilpekaren n är lika n. Vi kommer att märka först att n är vad användaren har skrivit in per GetInts ringa hit. Och Pilpekaren n betyder vad? Tja, om vi går tillbaka till bilden här, om jag har ett finger som pekar på att första noden innehållande nio, den pil innebär i huvudsak gå till att nod och greppa värdet på plats n, i detta fall kallas datafältet n. Inom parentes - och vi såg detta ett par veckor sedan när någon frågade - denna syntax är nytt, men det gör det inte ge oss krafter som vi inte redan har. Vad var denna fras motsvarar användning dot notation och stjärnan ett par veckor sedan när vi skalade tillbaka detta skikt lite för tidigt? STUDENT: [OHÖRBAR]. Högtalare 1: Exakt, det var stjärna, och då var det stjärnan dot n, med parentes här, som ser, Uppriktigt sagt tror jag en hel del mer kryptiskt att läsa. Men stjärnan pekare, som alltid, medel gå dit. Och när du är det, vilka uppgifter område vill du komma? Jo du använda punktnotation att komma en structs datafält, och jag specifikt vill n. Ärligt talat, skulle jag hävda detta är bara svårare att läsa. Det är svårare att komma ihåg var gör parenteserna går, den stjärna och allt detta. Så världen antog några syntaktiska socker, så att säga. Bara ett sexigt sätt att säga, Detta är likvärdigt, och kanske mer intuitiv. Om pekaren är verkligen en pekare, det arrow notation medel gå dit och hitta fältet i det här fallet kallas n. Så om jag hittar det, märker vad jag gör. Jag kan helt enkelt skriva ut, hittade jag procent i, koppla in värdet för den int. Jag kallar sova för en sekund att bara slag av paus saker på skärmen för att ge användaren en sekund för att absorbera vad som hände precis. Och då bryter jag. Annars, vad ska jag göra? Jag uppdaterar pekaren till lika pekaren pilen bredvid. Så bara för att vara tydlig, innebär detta går där, med min gamla skolan notation. Så detta betyder bara att gå till valfri du pekar på, vilket i mycket första fallet är jag pekar på struct med nio i det. Så jag har gått där. Och sedan punktnotation betyder, får värdet på nästa. Men värdet, trots att det ritas som en smal, är bara en siffra. Det är en numerisk adress. Så här en rad kod, oavsett om skrivas så här, desto mer kryptiska sätt, eller som den här, den något mer intuitivt sätt, betyder bara flytta min hand från den första noden till den nästa, och sedan nästa, och sedan nästa, och så vidare. Så vi kommer inte att uppehålla mig vid den andra implementationer av infoga och ta bort och traversering, de två första av som är ganska involverad. Och jag tycker det är ganska lätt att få förlorad när man gör det muntligt. Men vad vi kan göra här är försöka avgöra hur bäst att göra detta visuellt. Eftersom jag skulle föreslå att om vi vill infoga element i detta befintlig lista, vilket har fem element - 9, 17, 22, 26, och 33 - Om jag skulle genomföra detta i kod, måste jag överväga hur man ska gå om att göra detta. Och jag skulle föreslå att ta baby steg varvid, i det här fallet menar jag, vad är de möjliga scenarier som vi kan stöta på i allmänhet? Vid genomförandet av insatsen för en länkad listan, händer detta bara vara en specifikt exempel på storlek fem. Tja om du vill infoga ett nummer, vilja säga nummer ett, och upprätthålla sorterad ordning, där uppenbarligen gör nummer ett måste gå i detta specifika exempel? Liksom i början. Men vad som är intressant det är att Om du vill infoga en i detta lista, vad som behöver speciell pekare ska uppdateras tydligen? First. Så jag skulle säga, detta är det första fallet att vi kanske vill överväga en scenario med insättning på början av listan. Låt oss plocka ut kanske en så enkel eller ens lättare fall, relativt sett. Anta att jag vill infoga nummer 35 i sorterad ordning. Det tillhör naturligtvis borta. Så vad pekaren uppenbarligen kommer att måste uppdateras i det scenariot? 34 pekare blir inte null men adressen till struct innehåller numret 35. Så det är fallet två. Så redan, jag slags kvantisera hur mycket arbete jag har att göra här. Och slutligen, är det uppenbart mellersta fallet faktiskt, i mitten, om jag vill infoga något som säger 23, som går mellan 23 och 26, men Nu börjar det bli lite mer inblandade eftersom det pekare behöver ändras? Så 22 måste givetvis ändras eftersom han inte kan peka på 26 längre. Han behöver peka på den nya noden som Jag måste fördela genom att ringa malloc eller något motsvarande. Men då behöver jag också att nya noden, 23 i detta fall, för att ha dess pekare pekar på vem? 26. Och det kommer att bli en ordning av verksamheten här. För om jag gör det dumt, och jag till exempel start i början av listan, och mitt mål är att sätta 23. Och jag kolla, det hör Här, nära nio? Nej. Tillhör det här, bredvid 17? Nej. Har det hör hemma här intill 22? Ja. Nu om jag är dum här, och inte tänka igenom detta, kan jag fördela min nya noden för 23. Jag kanske uppdaterar pekaren från noden kallas 22, pekar det på den nya noden. Och vad har jag att uppdatera den nya nodens pekare att vara? STUDENT: [OHÖRBAR]. SPEAKER 1: Exakt. Pekar på 26. Men dammit om jag inte redan uppdatera 22: s pekare att peka på den här killen, och nu har jag föräldralösa, resten av listan, så att säga. Så räkneordningen här kommer att vara viktigt. För att göra detta kunde jag stjäla, säga, sex frivilliga. Och låt oss se om vi inte kan göra detta visuellt i stället för kod-wise. Och vi har några härliga stressen bollar för dig idag. OK, vad sägs om en, två, i back - på slutet där. tre, fyra, ni båda killar på slutet. Och fem, sex. Visst. Fem och sex. Okej, och vi kommer till er nästa gång. Okej, kom upp. Okej, eftersom du är här uppe först, skulle du vilja vara ett olyckligt i Google Glass här? Okej, så, OK, glas, spela in en video. OK, du är bra att gå. Okej, så om ni kan komma över Här har jag förberett i förväg några siffror. Okej, kom hit. Och varför inte du gå lite vidare på det sättet. Och låt oss se, vad heter du, med Google Glass? STUDENT: Ben. Högtalare 1: Ben? OK, Ben, kommer du att vara först, bokstavligen. Så vi kommer att skicka dig till slutet av scenen. Okej, och ditt namn? STUDENT: Jason. Högtalare 1: Jason, OK kommer du vara nummer nio. Så om du vill följa Ben på det sättet. STUDENT: Jill. Högtalare 1: Jill, du kommer att bli 17, som om jag hade gjort detta mer intelligent, skulle jag ha började vid den andra änden. Du går den vägen. 22. Och du är? STUDENT: Mary. Högtalare 1: Mary, du ska vara 22. Och ditt namn är? STUDENT: Chris. Högtalare 1: Chris, du ska vara 26. Och sedan sist. STUDENT: Diana. Högtalare 1: Diana, du ska vara 34. Så du kommer på hit. Okej, så perfekt sorteras beställa redan. Och låt oss gå vidare och göra detta så att vi verkligen kan - Ben är du bara typ av ser ut i ingenstans där. OK, så låt oss gå vidare och skildra detta med vapen, ungefär som jag var, exakt, vad som händer. Så gå vidare och ge er själva en fot eller två mellan er. Och gå vidare och pekar med ena handen vem du ska peka på baserat på detta. Och om du är null bara peka rakt ner till golvet. OK, så bra. Så nu har vi en länkad lista, och låt mig föreslår att jag ska spela rollen av PTR, så jag kommer inte att bry sig bär detta runt. Och då - någon dum konvent - du kan kalla detta något du vill - föregångare pekare, pred pekare - det är bara smeknamnet vi gav i vår exempelkod på min vänstra hand. Den andra handen som kommer att hålla reda på vem som är vem i Följande scenarier. Så antar, först, jag vill plocka bort att första exemplet att infoga, säg 20, in i listan. Så jag kommer att behöva någon att förkroppsligar nummer 20 för oss. Så jag behöver malloc någon från publiken. Kom upp. Vad är ditt namn? STUDENT: Brian. Högtalare 1: Brian, okej, så du skall vara den nod som innehåller 20. Okej, kom hit. Och självklart, där hör Brian? Så, mitt i - faktiskt, vänta en minut. Vi gör detta i ordning. Vi gör detta mycket svårare än den behöver vara i början. OK, vi ska fria Brian och realloc Brian som fem. OK, så nu vill vi infoga Brian som fem. Så kom hit intill Ben för bara ett ögonblick. Och du kan antagligen berätta där denna historia går. Men låt oss tänka igenom ordningen på verksamheten. Och det är just denna visuella som kommer att rada upp med provkoden. Så här har jag PTR pekar inledningsvis inte på Ben, per se, men oavsett på vilken värdesätter han innehåller, som i detta fall är - vad heter du nu igen? STUDENT: Jason. Högtalare 1: Jason, så både Ben och jag är pekar på Jason i denna stund. Så nu måste jag bestämma, där hör Brian? Så det enda jag har tillgång till just nu är hans n dataelement. Så jag ska kolla, är Brian mindre än Jason? Svaret är sant. Så vad måste nu ske, i rätt ordning? Jag behöver uppdatera hur många pekare totalt i den här historien? Om min hand är fortfarande pekar på Jason och din hand - om du vill sätta handen som, liksom, jag vet inte, ett frågetecken. OK, bra. Okej, så du har några kandidater. Antingen Ben eller jag eller Brian eller Jason eller alla andra, vilket pekare behöver ändra? Hur många totalt? OK, så två. Min pekaren spelar egentligen ingen roll längre eftersom jag är bara tillfällig. Så det är dessa två killar, förmodligen, både Ben och Brian. Så låt mig föreslå att vi uppdaterar Ben, eftersom han är först. Den första delen av denna lista kommer nu att bli Brian. Så Ben pekar på Brian. OK, nu vad? Vem blir pekade på vem? STUDENT: [OHÖRBAR]. Högtalare 1: OK så Brian har att peka på Jason. Men jag har tappat bort den pekare? Vet jag var Jason är? STUDENT: [OHÖRBAR]. Högtalare 1: jag gör, eftersom jag är den temporära pekaren. Och förmodligen har jag inte ändrat att peka på den nya noden. Så vi kan bara ha Brian punkt på vem jag pekar på. Och vi är klara. Så fall en, insättning på början av listan. Det fanns två viktiga steg. Ett måste vi uppdatera Ben, och sedan Vi har också att uppdatera Brian. Och då jag inte behöver bry traipsing genom resten av listan, eftersom vi redan hittat hans plats, eftersom han tillhörde den kvar av det första elementet. Okej, så ganska enkelt. I själva verket känns som om vi är nästan vilket gör detta alltför komplicerat. Så låt oss nu plocka ut slutet av listan, och se var komplexiteten startar. Så om nu, alloc jag från publiken. Någon som vill spela 55? Okej, jag såg din hand först. Kom upp. Yeah. Vad är ditt namn? STUDENT: [OHÖRBAR]. SPEAKER 1: Habata. OK, kom upp. Du kommer att vara nummer 55. Så du, naturligtvis, tillhör i slutet av listan. Så låt oss spela om simuleringen med mig vara PTR för bara ett ögonblick. Så jag först kommer att peka på vad Ben pekar på. Vi är båda pekar nu på Brian. Så 55 är inte mindre än fem. Så jag kommer att uppdatera mig själv genom pekar på Brians nästa pekare, som Nu är förstås Jason. 55 är inte mindre än nio, så Jag kommer att uppdatera PTR. Jag kommer att uppdatera PTR. Jag kommer att uppdatera PTR Jag kommer att uppdatera PTR. Och jag ska - hmm, vad är ditt namn igen? STUDENT: Diana. SPEAKER 1: Diana pekar, naturligtvis, på noll med sin vänstra hand. Så var Habata faktiskt tillhör tydligt? Till vänster här. Så hur vet jag att sätta henne här Jag tror att jag har skruvat upp. För vad är PTR konst denna tidpunkt? Null. Så även om, visuellt, kan vi naturligtvis se alla dessa killarna här på scenen. Jag har inte hållit koll på de tidigare person i listan. Jag har inte ett finger pekar ut, i detta fall, det nodnummer 34. Så låt oss faktiskt börja över. Så nu har jag egentligen inte behöver en andra lokal variabel. Och detta är vad du ser i aktuella provet C-kod, där som jag går, när jag uppdaterar min högra hand för att peka Jason, vilket lämnar Brian bakom, jag bättre börja använda min vänstra hand till uppdatera där jag var, så att när jag går igenom den här listan - mer tafatt än jag tänkt nu här visuellt - Jag kommer att komma till slutet av listan. Denna handen är fortfarande noll, vilket är ganska värdelös, annat än för att indikera Jag är helt klart i slutet av listan, men nu åtminstone jag har detta föregångare pekaren pekar här, så nu vad händer och vad pekare behöver ska uppdateras? Vars hand vill du ha att konfigurera om först? STUDENT: [OHÖRBAR]. Högtalare 1: OK, så Dianas. Vart vill du peka Dianas vänstra pekaren på? Vid 55, förmodligen, så att Vi har satt dit. Och där ska 55 pekare gå? Ner, representerande null. Och mina händer, på denna punkt, inte roll eftersom de var bara temporära variabler. Så nu vi är klara. Så den extra komplexitet där - och det är inte så svårt att genomföra, men vi behöver en sekundär variabel att göra Se till att innan jag flyttar min rätt handen, uppdaterar jag värdet av min vänstra handen, pred pekaren i det här fallet, så att jag har en släpande pekare att hålla reda på var jag var. Nu som en åt sidan, om du tänker här igenom, känns det som om det är en lite irriterande att behöva hålla koll på denna vänster hand. Vad skulle en annan lösning på detta problem har varit? Om du fick göra om data struktur vi pratar igenom just nu? Om detta bara typ av känns lite irriterande att ha, liksom, två pekare gå igenom listan, kunde vem ha, i en perfekt värld, underhålls information som vi behöver? Yeah? STUDENT: [OHÖRBAR]. SPEAKER 1: Exakt. Rätt så finns det faktiskt en intressant fröet till en idé. Och denna idé om en tidigare pekare, pekar på föregående element. Vad händer om jag förkroppsligade just det insidan av själva listan? Och det kommer att vara svårt att visualisera detta utan alla papper faller till golvet. Men antar att killarna använde både av sina händer för att få en tidigare pekare, och en nästa pekare, därigenom genomföra vad vi kallar ett dubbelt länkad lista. Som skulle tillåta mig att sortera i bakåt, mycket lättare utan mig, det programmerare, behöva hålla spåra manuellt - verkligen manuellt - där jag hade tidigare i listan. Så vi kommer inte att göra det. Vi ska hålla det enkelt eftersom det är kommer att komma till ett pris, dubbelt så mycket utrymme för pekare, Om du vill ha en andra. Men det är verkligen en gemensam datastruktur känd som en dubbellänkad lista. Låt oss göra det sista exemplet här och sätta dessa killar ur deras elände. Så malloc 20. Kom upp från gången där. Okej, vad heter du? STUDENT: [OHÖRBAR]. Högtalare 1: Förlåt? STUDENT: [OHÖRBAR]. Högtalare 1: Demeron? OK Kom upp. Du ska vara 20. Du uppenbarligen kommer att hör mellan 17 och 22. Så låt mig lära min läxa. Jag ska börja pekare pekar på Brian. Och jag kommer att ha min vänstra hand bara uppdatera till Brian som jag flyttar till Jason, kontroll gör 20 mindre än nio? Nej. Är 20 mindre än 17? Nej. Är 20 mindre än 22? Ja. Så vad pekare eller händer behöver ändra där de pekar nu? Så vi kan göra 17 pekar på 20. Så det är bra. Var vill vi peka pekaren nu? Vid 22. Och vi vet var 22 är, återigen tack till min tillfälliga pekare. Så vi är OK där. Så på grund av detta tillfälliga lagring Jag har hållit koll på var alla är. Och nu kan du visuellt gå in där du hör hemma, och nu behöver vi 1, 2, 3, 4, 5, 6, 7, 8, 9 stress bollar, och en applåd för dessa killar, om vi kunde. Snyggt gjort. [Applåder] Högtalare 1: Okej. Och du kan hålla bitarna av papper som souvenirer. Okej, så, tro mig det är en hel del lättare att gå igenom det med människor än vad det är med själva koden. Men vad du hittar på bara ett ögonblick Nu är det samma - Åh, tack. Tack - är att du kommer att upptäcka att samma data struktur, en länkad lista, kan faktiskt användas som en byggsten för att ännu mer avancerade datastrukturer. Och inser också temat här är att Vi har helt infört mer komplexiteten i genomförandet av denna algoritm. Insättning, och om vi gick igenom det, radering och sökning, är en liten mer komplicerat än det var med en array. Men vi få en viss dynamik. Vi får en adaptiv datastruktur. Men återigen, vi betalar ett pris för att ha några ytterligare komplexitet, både i genomföra det. Och vi gett upp random access. Och för att vara ärlig, det finns inte några trevliga ren bild jag kan ge dig det säger här är varför en länkad lista är bättre än en array. Och stannar vid detta. Eftersom temat upprepas nu, även mer så under de kommande veckorna, är att det inte nödvändigtvis ett korrekt svar. Det är därför vi har den separat axel av design för problemsamlingar. Det kommer att bli mycket sammanhangsberoende om du vill använda dessa data struktur eller att en, och det kommer beror på vad som är viktigt för dig när det gäller av resurser och komplexitet. Men låt mig föreslå att den ideala uppgifter struktur, den heliga graal, skulle vara något som är konstant tid, oavsett hur mycket grejer är inuti det, skulle det inte vara fantastiskt om en datastruktur gav svar i konstant tid. Ja. Detta ord är i din enorma ordboken. Eller nej, är detta ord inte. Eller något sådant problem där. Nå, låt oss se om vi kan inte minst ta ett steg mot det. Låt mig föreslå en ny datastruktur som kan användas för olika saker, i detta fall kallas en hash-tabell. Och så är vi faktiskt tillbaka till ögna på en matris, i det här fallet, och något godtyckligt, har jag dragit detta hash tabell som en array med en slags tvådimensionell array - eller snarare det skildras här som en två dimensionell array - men detta är bara en matris med storlek 26, så att om vi ring arrayen tabellen, bordsfäste noll är den rektangel på toppen. Bordsfäste 25 är rektangeln längst ned. Och detta är hur jag skulle rita en data struktur där jag vill lagra folks namn. Så till exempel, och jag kommer inte att dra hela saken här på overhead, om jag hade denna matris, som jag nu kommer att ringa en hashtabell, och detta är återigen läge noll. Detta är här plats en, och så vidare. Jag hävdar att jag vill använda dessa data struktur, för diskussionens skull, att lagra människors namn, Alice och Bob och Charlie och andra sådana namn. Så tänk på det nu som början av, säg, en ordbok med massor av ord. De råkar vara namn i vårt exempel här. Och allt detta är alltför förbunden, kanske, att genomföra en stavningskontroll, som vi kanske för problem som sex. Så om vi har en rad total storlek 26 så att det är den 25: e plats längst ner, och jag hävdar att Alice är det första ordet i ordlistan för namn som jag vill infoga i RAM, i denna datastruktur, där finns instinkter som talar om att Alices namn bör gå i denna samling? Vi har 26 alternativ. Om vi ​​vill sätta henne? Vi vill ha henne i fästet noll, eller hur? A för Alice, låt oss kalla det noll. And B kommer att vara ett, och C kommer att vara två. Så vi kommer att skriva Alices namn här uppe. Om vi ​​sätter då Bob, hans Namnet kommer att gå här. Charlie kommer att gå här. Och så vidare ner genom denna datastruktur. Detta är en underbar datastruktur. Varför? Nå vad är gångtiden sätter en människas namn i detta datastruktur just nu? Med tanke på att denna tabell är implementerad, verkligen, som en matris. Jo det är konstant tid. Det är av storleksordningen en. Varför? Nå hur kan du avgöra där Alice tillhör? Du tittar på vilken bokstaven i hennes namn? Den första. Och du kan få det, om det är en sträng, genom att bara titta på snöre konsol noll. Så den nollte tecknet i strängen. Det är enkelt. Vi gjorde det i krypto Uppdraget veckor sedan. Och sedan när du vet att Alices brev är kapitalet A, kan vi subtrahera rabatt 65 eller kapitalet A självt, som ger oss noll. Så vi vet nu att Alice tillhör vid stället noll. Och med tanke på en pekare till dessa data struktur, av något slag, hur lång tid tar det tar mig att hitta plats noll i en array? Bara ett steg, höger Det är konstant tid grund av direktåtkomsten vi Förslaget var en del av en matris. Så kort sagt, räkna ut vad indexet av Alice heter, vilket är i detta fall är A, eller låt oss bara lösa att till noll, där B är en och C är två, räkna ut det är konstant tid. Jag måste bara titta på hennes första brev, räkna ut var noll är en array är också konstant tid. Så tekniskt det är som två steg nu. Men det är fortfarande konstant. Så vi kallar den stora O i en, så vi har insatt Alice in denna tabell i konstant tid. Men självklart, jag är naiva här, eller hur? Tänk om det finns en Aaron i klassen? Eller Alicia? Eller några andra namn som börjar med A. Där ska vi sätta den personen, eller hur? Jag menar, just nu finns det bara tre människor på bordet, så kanske vi bör sätta Aaron på plats noll ett två tre. Höger, kunde jag sätta en hit. Men sedan, om vi försöker att sätta David in denna lista, inte där David går? Nu vårt system börjar bryta nedåt, höger? Eftersom nu David hamnar här om Aaron är faktiskt här. Och så nu detta hela idén med att ha en ren datastruktur som ger oss konstant tid infogningar är inte längre konstant tid, eftersom jag måste kolla, åh, damnit, är någon som redan på Alice plats. Låt mig undersöka resten av dessa data struktur, letar efter en plats att sätta någon som Arons namn. Och så att alltför börjar ta linjär tid. Dessutom, om du nu vill hitta Aaron i denna datastruktur, och du kontrollera, och Arons namn är inte här. Helst skulle du bara säga Arons inte i datastrukturen. Men om du börjar göra plats för Aaron där det borde ha varit en D eller E, dig, värsta fall, måste kolla hela datastruktur, i vilket fall det överlåter till något linjär i storleken på bordet. Så okej, jag ska fixa det här. Problemet här är att jag hade 26 element i arrayen. Låt mig ändra det. Hoppsan. Låt mig ändra det så att snarare vara av storlek 26 totalt, märker botten Indexet kommer att förändras till n minus 1. Om 26 är alldeles för litet för människor " namn, eftersom det finns tusentals namnen i världen, låt oss bara göra i 100 eller 1000 eller 10.000. Låt oss bara anslå mycket mer utrymme. Tja det inte nödvändigtvis minskar sannolikheten för att vi inte kommer att ha två personer med namn som börjar med A, och så, skulle du försöka att sätta ett Namnen på plats noll fortfarande. De kommer fortfarande att kollidera, vilket innebär att vi fortfarande behöver en lösning för att sätta Alice och Aron och Alicia och andra namn som börjar med A annanstans. Men hur mycket av ett problem är det här? Vad är sannolikheten att du har kollisioner i en data struktur som denna? Nåväl, låt mig - vi kommer tillbaka på den frågan här. Och titta på hur vi kan lösa det först. Låt mig dra upp detta förslag här. Vad vi just beskrivit är en algoritm, en heuristisk kallas linjär sondering där, om du försökte sätta något här i dessa data struktur, som kallas en hash-tabell, och det finns inget utrymme där du verkligen sondera datastruktur kontroll, är det tillgängligt? Är detta Finns detta tillgängligt? Finns detta tillgängligt? Och när det äntligen är, sätter du namn som du tänkt håll på den platsen. Men i värsta fall, den enda fläcken kan vara mycket botten av data struktur, alldeles i slutet av arrayen. Så linjär sondering, i värsta fall, ankommer till en linjär algoritm där Aaron, om han råkar införas senast i denna datastruktur, kan han kolliderar med detta första läge, men sedan avsluta med otur på slutet. Så detta är inte en konstant tid heliga graal för oss. Denna metod att infoga element i en datastruktur som kallas en hash Tabellen verkar inte vara konstant tid åtminstone inte i det allmänna fallet. Det kan överlåta till något linjär. Så vad händer om vi löser kollisioner något annorlunda? Så här är en mer sofistikerad inställning till vad är fortfarande kallas en hash-tabell. Och genom hash, som en parentes, vad Jag menar är det index som Jag hänvisade till tidigare. Till hash något kan vara tänkt som ett verb. Så om du hash Alice är ett namn, en hashfunktion, så att säga, ska returnera ett tal. I detta fall är noll om hon hör hemma Platsen noll, en, om hon hör hemma plats ett, och så vidare. Så min hashfunktion hittills varit super enkelt, bara att titta på första bokstaven i någons namn. Men en hashfunktion tar så ingång viss bit data, en sträng, en int, oavsett. Och det spottar ut vanligtvis ett nummer. Och den siffran är där att data elementet hör hemma i en datastruktur känd här som en hash-tabell. Så bara intuitivt, är detta en något annorlunda sammanhang. Detta är faktiskt hänvisar till ett exempel involverar födelsedagar, där det kan finnas så många som 31 dagar i månaden. Men vad gjorde denna person beslutar att göra i händelse av en kollision? Sammanhang är nu, inte en kollision mellan namn, men en kollision på födelsedagar, Om två personer har samma födelsedag på den 2 oktober till exempel. STUDENT: [OHÖRBAR]. Högtalare 1: Ja, så här har vi den hävstångseffekt av länkade listor. Så det ser lite annorlunda än vi drog den tidigare. Men vi tycks behöva en array på vänster sida. Det är ett index, för ingen särskilda skäl. Men det är fortfarande en array. Det är en samling av pekare. Och var och en av dessa delar, var och en av dessa cirklar eller snedstreck - ett snedstreck representerar null - alla dessa pekare uppenbarligen pekar på vilken datastruktur? En länkad lista. Så nu har vi möjlighet att hårt kod i vårt program storleken på tabellen. I det här fallet, vet vi att det finns aldrig mer än 31 dagar i en månad. Så hårt kodning ett värde som 31 är rimliga i detta sammanhang. I samband med namn, hård kodning 26 är inte orimligt det folks Namnen börjar bara med, till exempel, alfabetet involverar A till Z. Vi kan klämma dem alla i dessa data struktur så länge, när vi får en kollision, sätter vi inte namnen här, vi tänker i stället för dessa celler inte som strängar själva, men som pekare till, till exempel, Alice. Och så Alice kan ha en annan pekare till ett annat namn som börjar med A. Och Bob går faktiskt över hit. Och om det finns ett annat namn som börjar med B, hamnar han hit. Och så var och en av de delar av detta bord två, om vi utformat detta en lite mer skickligt - kom igen - Om vi ​​utformat detta lite mer skickligt, blir nu en adaptiv uppgifter struktur, där det finns ingen hård gräns på hur många element som du kan infoga in i det, för om du inte har en kollision, det är bra. Bara gå vidare och lägga det till vad vi såg lite sedan var känd som en länkad lista. Nåväl låt oss stanna upp ett ögonblick. Vad är sannolikheten för en kollision i första hand? Höger, kanske jag över tänker, kanske Jag är över Engineering Denna problemet, eftersom du vet vad? Ja, kan jag komma med godtyckliga Exempel från toppen av mitt huvud som Allison och Aron, men i verkligheten, ges en likformig fördelning av ingångar, som är en del slumpmässiga insättningar i en datastruktur, vad som verkligen är sannolikheten för en kollision? Väl visar sig, det är faktiskt super hög. Låt mig generalisera detta Problemet är som denna. Så i ett rum n CS50 studenter, vad är sannolikheten för att åtminstone två studenter i rummet har samma födelsedag? Så det är vad. några hund - 200, 300 människor här och flera hundra personer hemma idag. Så om du ville fråga oss vad som är sannolikheten för två personer i det här rummet som har samma födelsedag, vi kan lista ut. Och jag hävdar faktiskt det finns två människor med samma födelsedag. Till exempel, är det någon har födelsedag idag? Igår? I morgon? Okej, så det känns som jag ska att behöva göra detta 363 eller så mer gånger för att faktiskt räkna ut om vi har en kollision. Eller så kan vi bara göra det matematiskt snarare än tediously göra detta. Och föreslår följande. Så jag föreslår att vi kunde modellera sannolikheten av två personer som har samma födelsedag som sannolikheten för ett minus sannolikheten för ingen har samma födelsedag. Så för att få den här, och detta är bara finare sätt att skriva detta, för första personen i rummet, han eller hon kan ha vilken som helst av den möjliga födelsedagar antar 365 dagar i året, med ursäkter till personer med i februari 29: e födelsedag. Så den första personen i det här rummet är gratis att ha valfritt antal födelsedagar av de 365 möjligheter så att vi kommer att göra det 365 delat med 365, vilket är ett. Nästa person i rummet, om målet är att undvika en kollision, kan endast har hans eller hennes födelsedag på hur många olika möjliga dagar? 364. Så den andra termen i detta uttryck är huvudsak gör att matte för oss genom att subtrahera bort en möjlig dag. Och sedan nästa dag, nästa dag, den nästa dag ner till det totala antalet av människor i rummet. Och om vi då överväga, vad är då sannolikheten inte att alla har unika födelsedagar, men återigen ett minus som, vad vi får är ett uttryck som kan mycket fancifully se ut så här. Men det är mer intressant att titta på visuellt. Detta är ett diagram där på x-axeln är antalet personer i rummet, det antal födelsedagar. På y-axeln är sannolikheten av en kollision, två personer har samma födelsedag. Och takeaway från denna kurva är att så fort du kommer att gilla 40 studenter, är du på en 90% sannolikhet combinatorically av två personer eller fler har samma födelsedag. Och när du kommer att gilla 58 personer är det nästan 100% av en slump de två personer i rummet kommer att ha samma födelsedag, även om det finns 365 eller 366 möjliga hinkar, och endast 58 personer i rummet. Bara statistiskt är det sannolikt att få kollisioner, vilket i korthet motiverar denna diskussion. Att även om vi får fint här, och börjar med dessa kedjor, är vi fortfarande kommer att ha kollisioner. Så det väcker frågan, vad är det kostnaden för att göra insättningar och deletioner i en datastruktur som denna? Nå, låt mig föreslå - och låt mig gå tillbaka till skärmen över här - om vi har n element i listan, så om vi försöker att infoga n element, och vi har Hur många hinkar? Låt oss säga totalt 31 skopor i fallet med födelsedagar. Vad är den maximala längden på en av dessa kedjor potentiellt? Om igen det finns 31 möjliga födelsedagar i en viss månad. Och vi bara klampa alla - faktiskt det är en dum exempel. Låt oss göra 26 istället. Så om faktiskt har personer vars namn börja med A till Z, och därmed ge us 26 möjligheter. Och vi använder en datastruktur som den vi just såg, där vi har en array av pekare, vilka var och en pekar på en länkad lista där första listan är alla med namnet Alice. Den andra listan är alla med namn som börjar med A, start med B, och så vidare. Vad är den sannolika längden av varje dessa listor om vi antar en trevlig ren fördelning av namn A till Z över hela datastrukturen? Det finns n folk i datastrukturen dividerat med 26, om de är snyggt utspridda över hela datastruktur. Så längden på var och en av dessa kedjor är n dividerat med 26. Men i stort O notation, vad är det? Vad är det egentligen? Så det är egentligen bara n, rätt? Eftersom vi har sagt tidigare, att usch du dividera med 26. Ja, i verkligheten är det snabbare. Men i teorin är det inte i grunden allt snabbare. Så vi verkar inte vara så mycket närmare denna heliga graal. I själva verket är detta bara linjär tid. Heck, på denna punkt, varför gör inte vi bara använda en enorm länkad lista? Varför inte vi använder bara en enorm array för att lagra namnen på alla i rummet? Tja, är det fortfarande något övertygande om en hash-tabell? Finns det fortfarande något övertygande om en datastruktur som ser ut så här? Detta. STUDENT: [OHÖRBAR]. Högtalare 1: Höger, och igen om det bara en linjär tid algoritm, och en linjär tid datastruktur, varför gör inte jag bara lagra allas namn i en stor array, eller i en länkad stor lista? Och sluta göra CS så mycket svårare än det behöver vara? Vad är övertygande om detta, även fast jag kliade det ut? STUDENT: [OHÖRBAR]. Högtalare 1: Infogningar inte? Dyrt längre. Så infogningar kunde potentiellt fortfarande vara konstant tid, även om dina uppgifter struktur ser ut så här, en rad pekare, är var och en pekar på potentiellt en länkad lista. Hur kan du uppnå konstant tid insättning av namnen? Stick den i fronten, eller hur? Om vi ​​offrar en konstruktion mål från tidigare, där vi ville behålla allas namn, till exempel, sorteras, eller alla nummer på scenen sorteras, Anta att vi har en osorterad länkad lista. Det kostar oss bara ett eller två steg, som i fallet med Ben och Brian tidigare, för att infoga ett element vid början av listan. Så om vi inte bryr oss om att sortera alla av de namn som börjar med A eller samtliga namnen som börjar med B, kan vi fortfarande uppnå konstant tid insättningen. Nu tittar upp Alice eller Bob eller några namn mer generellt är fortfarande vad? Det är stort O n dividerat med 26, i ideala fallet där alla är enhetligt distribueras, där det finns så många A: s som det finns Zs, vilket förmodligen är orealistiskt. Men det är fortfarande linjär. Men här kommer vi tillbaka till den punkt av asymptotisk notation som teoretiskt sant. Men i den verkliga världen, om jag hävdar att mitt program kan göra något 26 gånger snabbare än din, vars program ska du föredrar att använda? Yours eller gruvan, vilket är 26 gånger snabbare? Realistiskt, är den person vars 26 gånger snabbare, även om teoretiskt våra algoritmer körs i samma asymptotiska gångtid. Låt mig föreslå en annan lösning helt och hållet. Och om detta inte blåsa ditt sinne, vi ut ur datastrukturer. Så det här är det en trie - typ av ett dumt namn. Den kommer från hämtningar, och ordet stavas trie, t-r-i-e, på grund av Naturligtvis hämtning låter som trie. Men det är historia av ordet trie. Så en trie är faktiskt någon form av träd, och det är också en lek med det ordet. Och även om du inte riktigt kan se det med denna visualisering är en trie en träd strukturerad, som ett släktträd med en förfader på toppen och massor av barnbarn och barnbarnsbarn som löv på botten. Men varje nod i ett trie är en array. Och det är i en array - och låt oss oversimplify för ett ögonblick - det är ett array, i detta fall, med storlek 26, där varje nod är återigen en matris med storleken 26, där den nollte element i den array representerar A, och den sista elementet i varje sådan arrayen representerar Z. Så jag föreslår alltså att dessa uppgifter struktur, känd som en trie kan vara används också för att lagra ord. Vi såg en stund sedan hur vi skulle kunna lagra ord, eller i detta fall namn, och vi såg tidigare hur vi kan spara nummer, men om vi fokuserar på namn eller strängar här, märker vad som är intressant. Jag hävdar att namnet Maxwell är insidan av denna datastruktur. Var ser ni Maxwell? STUDENT: [OHÖRBAR]. Högtalare 1: Till vänster. Så vad är intressant med dessa data struktur är i stället lagra string M-A-X-W-E-L-L backslash noll, alla angränsande, vad du gör istället följer. Om detta är en trie som datastruktur, vars samtliga noder är återigen en array, och du vill lagra Maxwell, du först index och så roten nod, så att tala, den översta noden, på plats M, rätt, så ungefär i mitten. Och sedan därifrån, följer du en pekare till ett barn noder, så att säga. Så i släktträdet mening, du följer den nedåt. Och som leder dig till en annan nod till vänster där, vilket är bara en annan array. Och sedan om du vill lagra Maxwell, du hittar pekaren som representerar A, är som den här här. Då går du till nästa nod. Och notera - det är därför bildens lite lura - denna nod ser super liten. Men till höger om detta är Y och Z. Det är bara författaren har avkortat bilden så att du faktiskt se saker. Annars här bilden skulle vara enormt stort. Så nu index i plats X, sedan W, sedan E, sedan L, då L. vad är denna nyfikenhet? Tja, om vi använder denna typ av nya ta om hur du lagrar en sträng i en datastruktur, måste du ändå huvudsak bocka i data struktur som ett ord slutar här. Med andra ord, var och en av dessa noder på något sätt måste komma ihåg att vi faktiskt följt alla dessa pekare och lämnar en liten brödinkråm längst ner här i detta struktur för att indikera M-A-X-W-E-L-L är verkligen i denna datastruktur. Så vi kan göra detta på följande sätt. Var och en av noderna i den bild vi bara Sågen har en, en matris med storlek 27. Och det är nu 27, eftersom p satt sex, vi faktiskt ge dig en apostrof, så att vi kan ha namn som O'Reilly och andra med apostrofer. Men samma idé. Vart och ett av dessa element i array pekar på en struct nod, så bara en nod. Så detta är mycket påminner av vår länkad lista. Och då har jag en Boolean, som jag ska kalla ord, vilket bara kommer att bli sant om ett ord slutar vid detta nod i trädet. Den representerar effektivt det lilla triangel vi såg för en stund sedan. Så om ett ord slutar vid den noden i träd, kommer det ordet fältet vara sant, som begreppsmässigt är att bocka av, eller vi drar denna triangel, ja det är ett ord här. Så detta är en trie. Och nu är frågan, vad är dess gångtid? Är det stora O n? Är det något annat? Tja, om du har n namn i dessa data struktur, Maxwell är bara en av dem, vad är gångtiden insättning eller hitta Maxwell? Vad är gångtiden att infoga Maxwell? Om det finns n andra namn redan i tabellen? Yeah? STUDENT: [OHÖRBAR]. Högtalare 1: Ja, det är längden av namnet, eller hur? Så M-a-x-w-e-l-l så det känns som detta Algoritmen är stort O i sju. Nu, naturligtvis, namnet kommer att variera i längd. Kanske är det ett kort namn. Kanske är det ett längre namn. Men vad är nyckeln här är att det är ett konstant antal. Och kanske är det inte riktigt konstant, men gud, om realistiskt, i en lexikon, det finns förmodligen någon gräns på antalet bokstäver i ett personens namn i ett visst land. Och så kan vi anta att värde är en konstant. Jag vet inte vad det är. Det är förmodligen större än Vi tycker att det är. Eftersom det finns alltid något hörn fallet med ett galet långt namn. Så låt oss kalla det k, men det är fortfarande en konstant förmodligen, eftersom varje namn i världen, åtminstone i ett visst land, är att längden eller kortare, så det är konstant. Men när vi har sagt något är stort O för ett konstant värde, vad är det verkligen motsvarar? Det är egentligen samma sak som säger konstant tid. Nu är vi typ av fusk, eller hur? Vi är typ av hävstångseffekt viss teori här för att säga att ja, är ordningen k egentligen bara beställa av en, och det är konstant tid. Men det är egentligen. Eftersom den viktigaste insikten här är att Om vi ​​har n namn redan i detta datastruktur, och vi skär Maxwell, är den tid det tar för oss att infoga Maxwell alls påverkade av hur många andra människor är i datastrukturen? Verkar inte vara. Om jag hade en miljard fler element till detta trie och sedan in Maxwell, är han alls påverkas? Nej. Och det är till skillnad från någon av dagen uppgifter strukturer som vi har sett hittills, där speltid för din algoritm är helt oberoende av hur mycket grejer är eller inte redan i den datastruktur. Och så detta ger dig är nu en möjlighet för p set sex, vilket kommer återigen innebära att implementera en egen stavningskontroll, läsning i 150.000 ord, hur man bäst för att lagra den inte nödvändigtvis är uppenbart. Och även om jag har strävat efter att hitta den heliga graal, gör jag inte hävdar att ett trie är. Faktum är att en hash-tabell kan mycket väl visa sig vara mycket effektivare. Men de är bara - det är bara en av de designbeslut du måste göra. Men stängning låt oss ta 50 eller så sekunder för att ta en titt på vad som ligger framåt nästa vecka och därefter vi övergången från denna kommandoraden världen Om C-program till saker web baserade och språk som PHP och JavaScript och internet i sig, protokoll som HTTP, som du har tas för givet i år nu, och skrivit de flesta varje dag, kanske, eller sett. Och vi börjar att skala tillbaka lager av vad som är internet. Och vad är den kod som ligger bakom dagens verktyg. Så 50 sekunder av denna teaser här. Jag ger dig Warriors of the Net. [VIDEO SPELA] -Han kom med ett budskap. Med ett protokoll all hans eget. Han kom till en värld av grymma brandväggar, likgiltig routrar, och faror långt värre än döden. Han är snabb. Han är stark. Han är TCPIP. Och han har fått din adress. Krigare av nätet. [END VIDEOAVSPELNING] Högtalare 1: Det är hur internet ska arbeta med nästa vecka.