>> 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.
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.
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.