[MUSIK SPELA]
DAVID J. MALAN: Okej.
Detta är CS50.
Detta är vecka fem fortsatte, och vi har goda nyheter och dåliga nyheter.
Så goda nyheten är att CS50 lanserar denna fredag.
Om du vill gå med oss, bege dig till den vanliga webbadressen här.
Ännu bättre nyheter, ingen föreläsning denna kommande måndag den 13.
Något mindre bra nyheter, quiz noll är nästa onsdag.
Mer detaljer kan vara finns på webbadressen här.
Och under de kommande två dygnen vi kommer att fylla i tomrummen
när det gäller rummen att vi kommer att ha reserverat.
Bättre nyheter är att det ska vara en kurs omfattande översyn
session denna kommande Måndag på kvällen.
Håll ögonen öppna för kursens hemsida för plats och detaljer.
Sektioner, även om det är en semester, också kommer att träffas också.
Bästa nyheter, föreläsa nästa fredag.
Så det här är en tradition som vi har, enligt kursplanen.
Bara-- det kommer att bli fantastiskt.
Du kommer att se saker som konstant tidsdatastrukturer
och hashtabeller och träd och försök.
Och vi ska tala om födelsedagsproblem.
En hel massa saker inväntar nästa fredag.
OK.
Hur som helst.
>> Så minns att vi har varit med fokus på den här bilden av vad som är
insidan av vår dators minne.
Så minne eller RAM är där program existerar när du kör dem.
Om du dubbelklickar på en ikonen för att köra några program
eller dubbelklicka på ett ikonen för att öppna en fil,
det är laddat från hårda köra bil eller SSD-enheten
i RAM, Random Access Memory, där den lever tills strömmen stängs av,
den bärbara datorn locket stängs, eller om du avslutar programmet.
>> Nu när minnet av som du förmodligen
1 gigabyte i dessa dagar, 2 gigabyte, eller till och med mycket mer,
är allmänt anges för ett givet program
i denna typ av rektangulära konceptuell modell
där vi har stapeln längst ner och en massa andra saker på toppen.
Saken högst upp Vi har sett den här bilden
innan men aldrig talat om är den så kallade textsegment.
Text segment är bara ett finare sätt att säga det nollor och ettor som
komponera din faktiska sammanställt programmet.
>> Så när du dubbelklickar Microsoft Word på din Mac eller PC,
eller när du kör dot slash Mario på en Linux-dator på ditt terminalfönster,
de nollor och ettor som skriver Word eller Mario lagras tillfälligt
i datorns RAM-minne i den så kallade textsegment för ett speciellt program.
Därunder går initierats och oinitierade data.
Det här är saker som globala variabler, att vi inte har använt många av,
men ibland vi har hade globala variabler
eller statiskt definierad strängar som är hårdkodade ord som "hej"
som inte tas in från användaren som är hårdkodad i ditt program.
>> Nu, ner på botten som vi har den så kallade stacken.
Och stacken, hittills, vi har varit använder för vilka typer av ändamål?
Vad stapeln använts till?
Yeah?
>> Publik: Funktioner.
>> DAVID J. MALAN: För funktioner?
I vilken mening för funktioner?
>> PUBLIK: När du ringer en funktion, den argument kopieras till stacken.
>> DAVID J. MALAN: Exakt.
När du ringer en funktion, dess argument kopieras till stacken.
Så några X: s eller Y eller A: s eller B: s att du passerar in i en funktion
temporärt sätta på den så kallade stacken,
precis som en av Annenberg dining hall brickor och även saker
som lokala variabler.
Om foo funktion eller din swap funktionen har lokala variabler,
som temp, dessa två hamna på stacken.
Nu ska vi inte prata för mycket om dem, men dessa miljövariabler
i botten vi såg för ett tag sedan när Jag var futzing på tangentbordet en dag
och jag började komma åt saker liknande argv 100 eller argv 1000,
bara elements-- jag glömmer den numbers-- men att
var inte tänkt att nås av mig.
Vi började se lite funky symboler på skärmen.
De var så kallade miljövariabler
som globala inställningar för min program eller till min dator, inte
orelaterade till den nyligen bugg som vi diskuterade,
Shellshock, det har varit plågar en hel del datorer.
>> Nu slutligen i dagens fokus vi kommer i slutändan att vara på högen.
Detta är ytterligare en bit av minnet.
Och i grunden allt detta minnet är samma saker.
Det är samma hårdvara.
Vi är bara sorts behandla olika kluster
bitgrupper för olika ändamål.
Högen kommer också vara där variabler och minne som du begär
från operativsystemet lagras temporärt.
>> Men det är lite av en problem Här, som bilden antyder.
Vi sorts har två fartyg på väg att kollidera.
För som du använder mer och mer av stapeln, och som vi ser i dag
framåt, eftersom du använder mer och mer av heap, säkert dåliga saker kan hända.
Och faktiskt, kan vi förmå att avsiktligt eller oavsiktligt.
Så cliffhanger sista tiden var det här programmet,
som inte tjänar någon funktionell annat än att visa ändamål
hur du som en dålig kille faktiskt kan ta nytta av buggar i någons program
och ta över ett program eller till och med en hela datorsystemet eller server.
Så bara att titta kort, du märker att huvud i botten
tar i kommandoraden argument, som per argv.
Och den har ett anrop till en funktion f, väsentligen en namnlös funktion kallad
f, och det går i argv [1].
>> Så oavsett ord användaren skriver i åtmin prompten efter programmets namn,
och sedan denna godtycklig funktion upp topp, f, tar i en sträng, AKA char *,
som vi har börjat diskutera, och det bara kallar det "bar."
Men vi kan kalla det vad som helst.
Och sedan förklarar, insida av f, en array av tecken
kallas C-- 12 sådana tecken.
>> Nu, genom historien jag berättade en stund sedan, var i minnet
är c, eller är de 12 chars kommer att hamna?
Bara för att vara tydlig.
Yeah?
>> Publik: På stapeln.
>> David J. MALAN: På stapeln.
Så c är en lokal variabel.
Vi ber om 12 tecken eller 12 byte.
De kommer att hamna på den så kallade stacken.
Nu äntligen är den här andra funktion det är faktiskt ganska bra,
men vi har inte riktigt använt det själva, strncopy.
Det betyder sträng kopiera, men enbart finns N bokstäver, n tecken.
Så n tecken blir kopieras från bar till c.
Och hur många?
Längden på baren.
Så med andra ord, att en rad, strncopy,
kommer att kopiera effektivt bar in till c.
>> Nu, bara för slags förutse Sensmoralen i denna historia,
vad som är potentiellt problematiskt här?
Även om vi kollar längden av bar och går den in strncopy,
vad som är din gut berättar är fortfarande trasig om det här programmet?
Yeah?
>> PUBLIK: Inkluderar inte utrymme för tomtecknet.
DAVID J. MALAN: Inkluderar inte utrymme för tomtecknet.
Potentiellt, till skillnad från i tidigare praxis gör vi inte ens
har så mycket som en plus 1 till rymma den nolltecken.
Men det är ännu värre än så.
Vad skulle vi misslyckas med att göra?
Yeah?
>> PUBLIK: [ohörbart]
DAVID J. MALAN: Perfect.
Vi har hårdkodade 12 ganska godtyckligt.
Det är inte så mycket problem, men faktum
att vi inte ens kollar om längden på baren är mindre än 12,
i vilket fall det kommer att bli säkert att sätta in det i minnet
kallas c som vi har tilldelats.
Faktum är att om baren är som 20 tecken långa,
denna funktion verkar vara att kopiera 20 tecken från bar till c, och därigenom
tar minst 8 byte att det inte borde vara.
Det är implikationen här.
>> Så kort sagt, bruten programmet.
Inte en så stor sak.
Kanske du får en segmentering fel.
Vi har alla haft fel i programmen.
Vi alla kan ha fel i program just nu.
Men vad är innebörden?
Tja, här är en inzoomad version av den bild av min dators minne.
Detta är botten av min stack.
Och faktiskt, längst ner är det som är kallas förälder rutin stack, finare sätt
att säga att det är viktigaste.
Så att den som kallas funktionen f som vi pratar om.
Så här är botten av stapeln.
Returadressen är något nytt.
Det har alltid funnits där, alltid varit i den bilden.
Vi kallade bara aldrig uppmärksamhet till den.
Eftersom det blir som c fungerar är att när ett funktionsanrop annan,
inte bara de argument som Funktionen får skjutas på stacken,
inte bara funktionens lokala variabler får skjutas på stacken,
något som kallas en returadress också får sätta på stacken.
Särskilt om huvud samtal foo, huvud s egen adress i minnet, oxe något,
effektivt får sätta på stacken så att när f görs verkställer det
vet var att hoppa tillbaka i texten segment för att fortsätta köra.
>> Så om vi är här konceptuellt, i main, då f anropas.
Hur f veta vem till handkontroll tillbaka?
Nåväl, denna lilla breadcrumb i rött här,
kallas avsändaradressen, det bara kontroller, vad är det returadress?
Åh, låt mig gå tillbaka till huvud här.
Och det är lite av en grov förenkling,
eftersom nollor och ettor för main är tekniskt
här uppe i tech segmentet.
Men det är tanken. f bara måste veta vad
där kontrollen går till sist tillbaka.
>> Men sättet datorer har länge lagt ut saker
som lokala variabler och argumenten är så här.
Så i den övre delen av denna bild i blå är stackram för f, så alla
hos minnet att f specifikt är att använda.
Så följaktligen märker att bar är i denna bild.
Bar var sin argumentation.
Och vi hävdade att argumenten för funktioner får skjutas på stacken.
Och C, är naturligtvis även i denna bild.
>> Och bara för nota ändamål, märke i det övre vänstra hörnet
är vad som skulle vara c fäste 0 och sedan något ned till höger
är c bygel 11.
Så med andra ord, kan du tänka dig att det finns ett rutnät av byte
Det första av dessa är övre vänstra, botten som
är det sista av dessa 12 byte.
>> Men nu försöker spola framåt.
Vad håller på att hända om vi passerar i en sträng bar som är längre än c?
Och vi ska inte kontrollera om det är faktiskt mer än 12.
Vilken del av den här bilden kommer att blir över av byte 0, 1, 2, 3,
dot dot dot, 11, och sedan dåligt, 12, 13 till 19?
Vad kommer att hända här, om du dra slutsatsen beställning
att c fäste 0 är på toppen och c bygel 11 är typ av nedåt
till höger?
Yeah?
>> PUBLIK: Tja, det kommer att skriva över char * bar.
>> DAVID J. MALAN: Ja, det ser ut som du kommer att skriva över char * bar.
Och ännu värre, om du skickar in en riktigt lång sträng, kan du även skriva vad?
Avsändaradressen.
Som återigen, är precis som ett breadcrumb att tala om för programmet där
att gå tillbaka till när f sker kallas.
>> Så vad skurkarna vanligtvis gör är om de stöter på ett program
att de är nyfikna om är utnyttjas, buggy på ett sådant sätt
att han eller hon kan ta Fördelen med denna bugg,
allmänhet de inte får denna rätt första gången.
De börjar att skicka, till exempel, slumpmässiga strängar i ditt program,
vare sig på tangentbordet, eller ärligt talat de förmodligen
skriva ett litet program för att bara automatiskt generera strängar,
och börja banka på ditt program genom skicka in massor av olika ingångar
vid olika längder.
>> Så fort dina program kraschar, det är en fantastisk sak.
Eftersom det innebär att han eller hon har upptäckt
vad som troligen är verkligen en bugg.
Och då kan de få mer smart och börjar fokusera snävare
om hur man kan utnyttja denna bugg.
Framför allt vad han eller hon kanske göra är att skicka, i bästa fall, hej.
No big deal.
Det är en sträng som är tillräckligt kort.
Men tänk om han eller hon skickar, och vi ska generalisera det som,
attack code-- så nollor och de som gör saker
som rm-rf, som tar bort allt från hårddisken eller skicka skräppost
eller på något sätt angripa maskinen?
>> Så om var och en av dessa bokstäverna A bara representerar,
konceptuellt, attack, attack, attack, attack, några dåliga kod
att någon annan skrev, men om personen är smart nog
att inte bara omfatta alla av dessa rm-RFS, men också
få sina sista byte vara ett nummer som motsvarar
till adressen för sin eller hennes egen attack-kod
att han eller hon gick på bara genom att förse den vid prompten
du effektivt kan lura datorn in märker när f görs verkställande,
åh, det är dags för mig att hoppa tillbaka till den röda returadress.
Men för att han eller hon har på något sätt lappade som returadress
med sitt eget nummer, och de är tillräckligt smarta
ha konfigurerat att nummer att hänvisa, som ni
se i super toppen vänstra hörnet där,
den faktiska adressen i datorns minnet av en del av sin attack-kod,
en dålig kille kan lura datorn till verkställande sin egen kod.
>> Och den koden, återigen, kan vara vad som helst.
Det är allmänt kallas shell-kod, vilket är precis
ett sätt att säga att det inte är generellt något så enkelt som rm-rf.
Det är faktiskt något som Bash, eller en faktisk program som ger honom
eller hennes programma för att utföra något annat som de vill.
Så kort sagt, allt detta härrör från det enkla faktum
att denna bugg inblandade inte kontrollera gränserna för din array.
Och eftersom det sätt datorer fungerar är att de
använda stapeln från effektivt, begreppsmässigt,
botten på upp, men då elementen du trycker på stacken växer uppifrån och ner,
detta är oerhört problematiskt.
Nu finns det sätt att komma runt detta.
Och ärligt talat, det finns språk som man kan komma runt detta.
Java är immun, till exempel, till denna fråga.
Eftersom de inte ger dig tips.
De inte ge dig direktminnesadresser.
Så med denna kraft som vi har röra någonting i minnet
vi vill kommer visserligen stor risk.
>> Så håll utkik.
Om, ärligt talat, under månaderna eller kommande år, när som helst
du läsa om några exploatering av ett program eller en server,
Om du någonsin sett en antydan till något som ett buffertspill attack,
eller spill är en annan typ av angrepp, i samma anda,
mycket som inspirerar webbplatsens namn, om du vet det,
det är alla pratar om just fulla storleken på vissa tecken
array eller någon array mer generellt.
Alla frågor, då, på det här?
Prova inte detta hemma.
>> Okej.
Så malloc hittills har varit vår nya vän i detta kan vi tilldela minne
att vi inte nödvändigtvis vet i avancera till att vi vill ha så att vi inte har
till hård kod i vår programnummer som 12.
När användaren berättar hur mycket uppgifter som han eller hon vill ingång,
Vi kan malloc så mycket minne.
>> Så malloc visar det sig, till mån vi har använt det,
uttryckligen förra gången, och sedan ni har använt det
för GetString omedvetet för flera veckor, alla malloc minne
kommer från den så kallade heap.
Och det är därför getString, till exempel, kan allokera minne dynamiskt
utan att veta vad du är kommer att skriva i förväg,
hand du tillbaka en pekare till det minnet, och att minnet är fortfarande din att behålla,
även efter GetString avkastning.
Eftersom minns ju att stack hela tiden går upp och ner,
upp och ner.
Och så snart som det går ner, betyder att varje minne
denna funktion används bör inte användas av någon annan.
Det är sopor värden nu.
>> Men högen är här uppe.
Och vad är trevligt om malloc är att när malloc allokerar minne upp här,
det är inte påverkat, för största delen av stapeln.
Och så någon funktion kan komma åt minne som har malloc'd,
även av en funktion som getString, även efter att den återlämnas.
>> Nu är motsatsen till malloc gratis.
Och faktiskt, den regel som du måste börja anta
finns någon, några, när du använder malloc Du måste själv använda gratis, så småningom,
på samma pekare.
Hela denna tid har vi skrivit barnvagn, barnvagn kod, av många skäl.
Men en av vilka har varit använder CS50 biblioteket, som
själv är medvetet buggy, läcker det minnet.
Varje gång du har ringt getString under de senaste veckorna
vi ber drifts systemet, Linux, för minnet.
Och du har aldrig en gång gett tillbaka den.
Och detta är inte, i träna, en bra sak.
>> Och Valgrind, en av verktyg infördes Pset 4,
handlar om att hjälpa dig nu hitta buggar som.
Men turligt nog för Pset 4 du inte behöver att använda CS50 biblioteket eller getString.
Så eventuella buggar relaterade till minnet är i slutändan kommer att vara din egen.
>> Så malloc är mer än bara bekvämt för detta ändamål.
Vi kan faktiskt nu lösa fundamentalt olika problem,
och i grunden lösa problem mer effektivt som per vecka noll löfte.
Hittills är den sexigaste datastruktur som vi har haft.
Och datastruktur menar jag bara ett sätt att konceptualisering minne
på ett sätt som går utöver att bara säga, detta är en int, detta är en röding.
Vi kan börja kluster saker tillsammans.
>> Så en array såg ut så här.
Och vad som var nyckeln i ungefär en array är att det ger dig
back-to-back bitar av minne, som var och en
kommer att vara av samma typ, int int, int, int eller char, röding, röding,
röding.
Men det finns några nackdelar.
Detta är till exempel en matris med storleken sex.
Anta att du fyller denna matris med sex siffror och då, oavsett skäl,
användar vill ge du en sjunde nummer.
Var placerar du den?
>> Vad är lösningen om du har skapas en array på stacken,
till exempel, bara med den vecka två notation som vi presenterade,
av hakparenteser med ett nummer på insidan?
Tja, du har sex siffror i dessa rutor.
Vad skulle dina instinkter vara?
Var skulle du vilja sätta den?
>> PUBLIK: [ohörbart]
>> DAVID J. MALAN: Förlåt?
>> PUBLIK: Sätt den på slutet.
>> DAVID J. MALAN: Sätt den på slutet.
Så bara över till höger, utanför denna box.
Vilket skulle vara trevligt, men det visar sig att du kan inte göra det.
För om du inte har bett för denna bit av minne,
det kan vara en slump att detta används av någon annan variabel
helt och hållet.
Tänk tillbaka en vecka eller så när vi lade ut Zamyla och Davin och Gabe namnger
i minnet.
De var bokstavligen rygg mot rygg mot rygg.
Så vi kan inte nödvändigtvis lita på att det som finns
här borta är tillgänglig för mig att använda.
>> Så vad mer kan du göra?
Jo, en gång inse att du behöver en matris av storlek sju,
du kan bara skapa en matris med storlek sju använd sedan
en for-loop eller en while-slinga, kopiera den till den nya arrayen,
och sedan på något sätt bara bli av denna array eller bara sluta använda den.
Men det är inte särskilt effektivt.
Kort sagt, arrayer inte låta du dynamiskt ändra storlek.
>> Så å ena sidan får du random access, vilket är fantastiskt.
Eftersom det låter oss göra saker som söndra och härska,
binär sökning, vilka samtliga vi har pratade om på skärmen här.
Men du målar själv i ett hörn.
Så fort du träffar i slutet av din samling,
du måste göra en mycket dyr operation
eller skriva en massa kod att nu ta itu med det problemet.
>> Så vad händer om vi istället hade något som kallas en lista,
eller en lista länkad i synnerhet?
Tänk om istället för att ha rektanglar rygg mot rygg mot rygg,
vi har rektanglar som lämnar lite lite svängrum mellan dem?
Och även om jag har dragit det här bild eller anpassat den här bilden
från en av de texter som här för att vara tillbaka till rygg mot rygg mycket välordnat, i verkligheten,
en av dessa rektanglar kunde vara här uppe i minnet.
En av dem kan vara här uppe.
En av dem kan vara här uppe, hit, och så vidare.
>> Men tänk om vi drog, i det här fallet, pilar
som på något sätt koppla dessa rektanglar tillsammans?
I själva verket har vi sett en teknisk inkarnation av en pil.
Vad har vi använt under de senaste dagar som, under huven,
är representativ för en pil?
En pekare, eller hur?
>> Så vad händer om, i stället för bara lagra numren,
som 9, 17, 22, 26, 34, tänk om vi lagras inte
bara ett nummer utan en pekare bredvid varje sådant nummer?
Så att mycket som du skulle trä en nål igenom en hel massa tyg,
på något sätt knyta saker tillsammans, på liknande sätt kan
vi med pekare, som förkroppsligad genom pilar här,
slags väva samman dessa enskilda rektanglar
genom att effektivt att använda en pekare bredvid varje nummer som
pekar på något nästa nummer, som pekar på, i sin tur, en del nästa nummer?
Så med andra ord, vad om vi verkligen ville
att genomföra något sådant här?
Väl tyvärr dessa rektanglar, åtminstone en med 9, 17, 22,
och så vidare, dessa är inte längre trevliga torg med enstaka nummer.
Botten, rektangel Nedan 9, till exempel,
representerar vad ska vara en pekare, 32 bitar.
Nu är jag ännu inte till någon datatyp i C som inte bara ger dig en int
men en pekare helt.
>> Så vad är lösningen om vi vill att uppfinna våra egna svar på detta?
Yeah?
>> PUBLIK: [ohörbart]
>> DAVID J. MALAN: Vad är det?
>> PUBLIK: Ny struktur.
>> DAVID J. MALAN: Ja, så varför inte vi skapar en ny struktur,
eller C, en struct?
Vi har sett structs tidigare, om en kort stund, där vi behandlat en elev struktur
som denna, som hade ett namn och ett hus.
I Pset 3 breakout du använde en hel gäng structs-- GRect och GOvals
att Stanford skapats för att kluster informationen håller.
Så vad händer om vi tar samma uppfattning om sökorden "typedef" och "struct",
och lite studentspecifika grejer, och utvecklas här i följande:
typedef struct node-- och nod är bara en mycket generisk datavetenskap
term för något i en datastruktur, en behållare i en datastruktur.
En nod Jag hävdar kommer att ha en int n, helt enkelt,
och sedan lite mer kryptiskt, denna andra raden, struct nod * nästa.
Men i mindre tekniska termer, vad är det andra raden
för kod inuti klammerparentes?
Yeah?
>> PUBLIK: [ohörbart]
David J. MALAN: A pekare till en annan nod.
Så visserligen, syntax lite kryptiskt.
Men om du läser det bokstavligen, nästa är namnet på en variabel.
Vad är dess datatyp?
Det är lite mångordig den här gången, men det är av typen struct nod *.
Varje gång vi har sett något star, att betyder att det är en pekare till den datatypen.
Så nästa är uppenbarligen en pekare till en struct nod.
>> Nu, vad är en struct nod?
Tja, märker du dem Samma ord på upp till höger.
Och faktiskt, ser du även ordet "Nod" här nere längst ner till vänster.
Och det är faktiskt bara en bekvämlighet.
Notera att i vår definition elev det är ordet "student" bara en gång.
Och det beror på att en student Objektet var inte självrefererande.
Det finns inget inuti en student som måste peka på en annan student,
persay.
Det skulle vara slags konstig i den verkliga världen.
>> Men med en nod i en länkad lista, vill vi ha en nod
vara refererande till liknande syfte.
Och så märker förändringen här är inte precis vad som finns inuti klammerparentes.
Men vi lägga till ordet "nod" upptill samt
lägga till det till botten i stället för "student".
Och detta är bara en teknisk detalj så att, återigen, din datastruktur
kan vara självrefererande, så att en nod kan peka på en annan sådan nod.
>> Så vad är det i slutändan kommer att innebära för oss?
Jo, en, det här inne är innehållet i vår nod.
Denna sak här uppe, upp till höger, är bara så
att, återigen, kan vi hänvisa till oss själva.
Och sedan den yttersta grejer, även om noden är en ny term,
kanske, det är fortfarande det samma som student och vad
var under huven i SPL.
>> Så om vi nu ville börja genomförande av denna länkade lista,
Hur kan vi översätter ungefär så här för att koda?
Nåväl, låt oss bara ser en exempel på ett program som
faktiskt använder en länkad lista.
Bland dagens distributions kod är ett program som heter lista Zero.
Och om jag kör detta skapade jag en super enkelt GUI, grafiskt användargränssnitt,
men det är egentligen bara printf.
Och nu har jag gett mig själv ett par meny options-- Delete, Insert, Search,
och Traverse.
Och Quit.
Dessa är bara vanliga operationer på ett datastruktur som kallas en länklista.
>> Nu Radera ska ta bort ett nummer från listan.
Insert kommer att lägga ett nummer i listan.
Sök kommer att se för nummer i listan.
Och travers är bara ett finare sätt att säga, gå igenom listan,
skriva ut den, men det är det.
Ändra inte denna på något sätt.
>> Så låt oss prova det här.
Låt oss gå vidare och typ 2.
Och sedan ska jag in nummer, säger 9.
Enter.
Och nu mitt program är bara programmerad att säga, är listan nu 9.
Nu, om jag går vidare och inte in igen, låt
mig gå vidare och zooma ut och skriv in 17.
Nu är min lista är 9, därefter 17.
Om jag sätter i gång, låt oss hoppa över en.
I stället för 22, enligt bilden vi har varit att titta på här, låt mig hoppa framåt
och sätt 26 nästa.
Så jag kommer att skriva 26.
Listan är som jag förväntar mig.
Men nu, bara för att se om den här koden kommer att vara flexibla, låt mig nu
typ 22, som åtminstone begreppsmässigt, om vi
hålla denna sorteras, som visserligen är kommer att bli ytterligare ett mål just nu,
ska gå in mellan 17 och 26.
Så jag slog Enter.
I själva verket fungerar det.
Och så nu vill jag sätta in sist, enligt bilden, 34.
>> Okej.
Så nu vill jag föreskriva att Radera och Traverse och sökning gör,
i själva verket fungerar.
Faktum är att om jag kör sökning, låt oss söka efter numret 22, Enter.
Den hittade 22.
Så det är vad detta Programmet Lista Zero gör.
>> Men vad som verkligen händer den som implementerar detta?
Tja, först jag kan ha, och faktiskt Jag har en fil som heter list0.h.
Och någonstans i det här linje, typedef, struct nod,
då jag har mina klammerparenteser, int n, och sedan struct-- vad var definitionen?
Struct nod nästa.
Så vi behöver stjärnan.
Nu tekniskt vi får in för vana att dra upp den här.
Du kan se läroböcker och online-referenser gör det där.
Det är funktionellt likvärdig.
I själva verket är detta en lite mer typiska.
Men jag ska vara i linje med vad vi gjorde förra gången och gör detta.
Och slutligen, jag ska göra det här.
>> Så i en header-fil någonstans i list0.h
idag är denna struct definition, och kanske lite annat.
Under tiden i list0c finns kommer att bli ett par saker.
Men vi ska bara start och inte avsluta detta.
List0.h är en fil jag vill ha att i min C-fil.
Och sedan någon gång jag är kommer att ha int, main, ogiltig.
Och sedan ska jag har en del att göra det här.
Jag kommer även att ha en prototyp, som ogiltig, sök, int,
n är vars syfte i livet att söka efter ett element.
Och sedan ner här jag hävdar i dagens kod, tomrum, sök, int, n,
inget semikolon men öppna klammerparenteser.
Och nu vill jag på något sätt söka för ett element i den här listan.
Men vi har inte tillräckligt information på skärmen ännu.
Jag har faktiskt inte representerade själva listan.
Så ett sätt som vi skulle kunna genomföra en länkad lista i ett program
är jag liksom vill göra något som förklarar länkad lista här uppe.
För enkelhetens skull kommer jag att göra denna globala, även om vi i allmänhet
borde inte göra det för mycket.
Men det kommer att förenkla detta exempel.
Så jag vill förklara en länkad lista här.
Nu, hur kan jag göra det?
>> Här är bilden av en länkad lista.
Och jag vet inte riktigt vet just nu hur
Jag ska gå om företräder så många saker med bara en
variabel i minnet.
Men tänker tillbaka en stund.
Hela denna tid har vi haft strängar, som vi sedan
visade sig vara arrayer av tecken, som vi sedan
visade att bara vara en pekare till det första tecknet
i en matris av tecken som är null avslutas.
Så genom denna logik, och med detta bild slags seedning dina tankar,
Vad behöver vi faktiskt skriver i vår kod för att representera en länkad lista?
Hur mycket av denna information behöver vi att fånga i C-kod, skulle du säga?
Yeah?
>> Publik: Vi behöver en pekare till en nod.
David J. MALAN: En pekare till en nod.
Särskilt som nod skulle ditt instinkter vara att hålla en pekare till?
>> Publik: Den första noden.
>> DAVID J. MALAN: Ja, förmodligen bara den första.
Och märker, den första noden är en annan form.
Det är bara hälften så stor som den struct, eftersom det är faktiskt bara en pekare.
Så vad du faktiskt kan göra är att deklarera en länkad lista att vara av typ nod *.
Och låt oss bara kalla det först och initiera den till null.
Så null, återigen, är att komma in i bilden här.
Inte bara är null som som en speciell returvärde för saker som getString
och malloc är null också noll pekare, avsaknaden av en pekare,
om du kommer.
Det betyder bara ingenting är ännu här.
Nu först, kunde jag har kallade detta ingenting.
Jag kunde ha kallat det "lista" eller valfritt antal andra saker.
Men jag kallar det "första" så att den är i linje med den här bilden.
Så precis som en sträng kan representeras med adressen till sin första byte,
så kan en länkad lista.
Och vi får se andra data strukturer vara representerade
med bara en pekare, en 32-bitars pil, som pekar
på den allra första nod i strukturen.
>> Men nu ska vi räknar med ett problem.
Om jag bara minnas i mitt program adressen
av den första noden, den första rektangel i denna datastruktur,
vad hade bättre vara fallet om Genomförandet av resten av min lista?
Vad är en viktig detalj som händer att se till att detta verkligen fungerar?
Och med "faktiskt fungerar" Jag menar, ungefär som en sträng,
låter oss gå från det första tecknet i Davin namn till den andra,
till den tredje, till fjärde, till slutet,
Hur vet vi när vi är i slutet av en länkad lista som ser ut så här?
När det är null.
Och jag har företrätt denna typ av som som elingenjör makt,
med den lilla jord symbol, av slag.
Men det betyder bara null i detta fall.
Du kan rita det valfritt antal olika sätt, men denna författare
råkade använda denna symbol här.
>> Så länge vi stringing alla dessa noder tillsammans,
bara komma ihåg var den första är, så länge
som vi sätter en speciell symbol på den allra sista noden i listan,
och vi kommer att använda null, eftersom det är det vi har till vårt förfogande,
listan är klar.
Och även om jag bara ge dig en pekare till det första elementet, dig, programmerare,
kan säkert komma åt resten av den.
Men låt oss låt dina sinnen vandra lite,
om de inte redan är ganska wandered-- vad
kommer att bli speltid för hitta något i den här listan?
Fan, det är stort O i n, vilket inte är dåligt, i rättvisans namn.
Men det är linjär.
Vi har gett upp vilken funktion av matriser genom att flytta mer
mot denna bild av dynamiskt vävs samman eller länkade noder?
Vi har gett upp random access.
En array är trevligt eftersom matematiskt allt
är rygg mot rygg mot rygg mot rygg.
Även om den här bilden ser ganska, och till och med
även om det ser ut som dessa noder är snyggt åtskilda, i verkligheten
de skulle kunna vara var som helst.
OX1, Ox50, Ox123, Ox99, dessa noder kan vara var som helst.
Eftersom malloc gör tilldela minne från högen, men någonstans i högen.
Du behöver inte nödvändigtvis vet att det är kommer att vara tillbaka till tillbaka till igen.
Och så den här bilden i verkligheten är kommer inte att vara helt denna vackra.
>> Så det kommer att ta en bit av arbeta för att genomföra den här funktionen.
Så låt oss genomföra sökningen nu.
Och vi får se lite av en smart sätt att göra detta.
Så om jag är en sökfunktion och Jag får en variabel, integer n
att leta efter, jag behöver veta ny syntax för att titta inuti
en struktur som är pekade på, att hitta n.
Så låt oss göra det här.
>> Så först ska jag gå framåt och förklara en nod *.
Och jag ska kalla det pekare, bara genom konventionen.
Och jag kommer att initiera den till först.
Och nu kan jag göra det här på ett antal olika sätt.
Men jag ska ta ett gemensamt synsätt.
Även pekare är inte lika med null, och det är giltigt syntax.
Och det betyder bara göra följande, så länge du inte pekar på någonting.
Vad vill jag göra?
>> Om pekaren dot n, låt mig komma tillbaka till det, lika equals-- vad?
Vilket värde letar jag efter?
Själva n som skickades in.
Så här är en annan funktion C och många språk.
Även om den struktur som kallas nod har ett värde n, helt legitimt
att också ha en lokal argument eller variabel som heter n.
Eftersom även vi, med mänskliga ögat kan urskilja
att denna n är förmodligen annorlunda än den här n.
Eftersom syntaxen är annorlunda.
Du har en prick och en pekare, Denna man har något sådant.
Så det här är OK.
Det är OK att kalla dem samma saker.
>> Om jag hittar du här, jag är kommer att vilja göra något
liksom meddela att vi hittat n.
Och vi lämnar det som en kommentera eller pseudokoden.
Else, och här är intressanta delen, vilken
vill jag göra om den aktuella noden inte innehåller n som jag bryr mig om?
Hur gör jag för att uppnå följande?
Om fingret på nu är PTR, och det är
pekar på vad första pekar på,
Hur flyttar jag mitt finger till nästa nod i kod?
Tja, vad är länkstigen är vi kommer att följa i det här fallet?
PUBLIK: [ohörbart].
DAVID J. MALAN: Ja, så nästa.
Så om jag går tillbaka till min koden här, ja, jag är
kommer att gå vidare och säga pekare, vilket är bara en tillfällig variable-- det
ett konstigt namn, ptr, men det är precis som temp--
Jag kommer att ställa pekaren lika oavsett pekaren är--
och igen, detta kommer att bli ett liten buggy för en moment-- punkt bredvid.
Med andra ord kommer jag att ta min finger som är riktade mot denna nod
här och jag kommer att säga, du vet vad, ta en titt på nästa fält
och flytta fingret till vad det pekar på.
Och detta kommer att repetera, repetera, repetera.
Men när gör mitt finger sluta göra något alls?
Så snart det kodrad sparkar i?
PUBLIK: [ohörbart]
DAVID J. MALAN: Om punkten samtidigt Pekaren är inte lika med noll.
Någon gång mitt finger s kommer att peka på null
och jag kommer att inse det är slutet av denna lista.
Nu är detta en lite vit lögn för enkelhet.
Det visar sig att även om vi just lärt sig detta punktnotation
för konstruktioner, är pekaren inte en struct.
ptr är vad?
Bara för att vara mer nitpicky.
Det är en pekare till en nod.
Det är inte en nod i sig.
Om jag hade ingen stjärnan här, pekare absolutely-- det är en nod.
Detta är som en vecka deklaration av en variabel,
även om ordet "nod" är ny.
>> Men så fort vi införa en stjärna, det är nu en pekare till en nod.
Och tyvärr kan du inte använda den punktnotation av en pekare.
Du måste använda pilen notation, som, påfallande,
är första gången någon pjäs av syntax ser intuitivt.
Det ser bokstavligen ut som en pil.
Och så det är en bra sak.
Och här nere bokstav ser ut som en pil.
Så jag tror det är la-- jag inte tror jag över begå här-- I
tror att det är det sista nya pjäs av syntax ska vi se.
Och tack och lov är det faktiskt lite mer intuitivt.
>> Nu, för er som kanske föredrar det gamla sättet,
Du kan fortfarande använda punktnotation.
Men enligt måndagens konversation, vi först
behöver gå dit, gå till den adress, och sedan gå in i fältet.
Så detta är också korrekt.
Och ärligt talat, är detta en lite mer pedantisk.
Du är bokstavligen säger dereference pekaren och gå dit.
Sedan ta tag .n, fältet kallas n.
Men ärligt talat, vill ingen att skriva eller läsa här.
Och så världen uppfann pilen notation, vilken
är motsvarande, identiska, det är bara syntaktisk socker.
Så ett finare sätt att säga detta ser bättre ut, eller ser enklare.
>> Så nu ska jag göra en annan sak.
Jag kommer att säga "paus" när jag har fann det så jag inte fortsätta leta efter den.
Men detta är kontentan av en sökfunktion.
Men det är mycket lättare, i slut, inte att gå igenom koden.
Detta är verkligen den formella tillämpningen för sökning i dagens distributions kod.
Jag vågar säga att insatsen inte särskilt kul att gå igenom
visuellt, inte heller är radera, även men i slutet av dagen
de kokar ner till ganska enkla heuristik.
>> Så låt oss göra det här.
Om du kommer humor mig här, jag gjorde ta med en massa stress bollar.
Jag tog en massa siffror.
Och skulle vi kunna få några frivilliga att representera 9, 17, 20, 22, 29 och 34?
Så i huvudsak alla vem som är här i dag.
Det var en, två, tre, fyra, fem, sex personer.
Och jag har blivit ombedd att go-- se, nej en i ryggen höjer sina händer.
OK, en, två, tre, fyra, five-- låt mig ladda balance-- sex.
OK, du sex kom upp.
Vi behöver andra människor.
Vi väckte extra stress bollar.
Och om du kunde, för bara ett ögonblick, linje
er upp precis gillar den här bilden här.
>> Okej.
Låt oss se, vad heter du?
>> PUBLIKEN: Andrew.
>> DAVID J. MALAN: Andrew, du är nummer 9.
Trevligt att träffas.
Varsågod.
PUBLIKEN: Jen.
DAVID J. MALAN: Jen.
David.
Number 17.
Ja?
>> PUBLIK: Jag är Julia.
>> DAVID J. MALAN: Julia, David.
Number 20.
PUBLIKEN: Christian.
DAVID J. MALAN: Christian, David.
Number 22.
Och?
>> PUBLIKEN: JP.
DAVID J. MALAN: JP.
Number 29.
Så sätt igång och få in-- Uh oh.
Uh oh.
Standby.
20.
Har någon en markör?
PUBLIK: Jag har en Sharpie.
DAVID J. MALAN: Du har en Sharpie?
OK.
Och är det någon som har en bit papper?
Spara föreläsningen.
Kom igen.
PUBLIK: Vi har det.
DAVID J. MALAN: Vi fick det?
Okej, tack.
Nu kör vi.
Var detta från dig?
Du räddade precis på dagen.
Så 29.
Okej.
Jag felstavade 29, men OK.
Varsågod.
Okej, jag ska ge dig pennan tillbaka tillfälligt.
Så vi har dessa människor här.
Låt oss ha en annan.
Gabe, vill du spela det första elementet här?
Vi behöver dig för att peka på dessa fina folks.
Så 9, 17, 20, 22, sortera 29 och sedan 34.
Gjorde vi förlorar någon?
Jag har en 34.
Där did-- OK, vem vill vara 34?
OK, kom upp, 34.
Okej, detta kommer att vara väl värt klimax.
Vad heter du?
>> PUBLIKEN: Peter.
>> DAVID J. MALAN: Peter, kom upp.
Okej, så här är en massa noder.
Var och en av er representerar en av dessa rektanglar.
Och Gabe, det något udda människan ut, står först.
Så hans pekaren är lite mindre på skärmen än alla andra.
Och i detta fall, var och en av vänster händer kommer att antingen peka nedåt,
därmed representerar null, så bara frånvaron av en pekare,
eller det kommer att peka vid en nod bredvid dig.
>> Så just nu om du pryda er som bilden
här, gå vidare och peka på varandra, med Gabe
i synnerhet pekar på nummer 9 för att representera listan.
OK, och nummer 34, vänster hand ska bara peka på golvet.
>> OK, så det här är den länkade listan.
Så detta är scenariot i fråga.
Och faktiskt, det här är representativt av en klass av problem
att du kanske försöker lösa med kod.
Du vill slutligen infoga ett nytt element i listan.
I det här fallet ska vi prova att sätta numret 55.
Men det kommer att bli olika fall att tänka på.
Och faktiskt, det här kommer att bli en av den stora bilden hämtställen här är,
vilka är de olika fallen.
Vilka är de olika om villkor eller grenar som ditt program kan ha?
>> Tja, det nummer du försöker Insatsen, som vi vet nu att vara 55,
men om du inte visste i förväg, jag daresay
faller in i åtminstone tre situationer.
Där kan ett nytt element vara?
PUBLIK: Och i slutet eller mitten.
DAVID J. MALAN: I slutet, i mitten, eller i början.
Så jag hävdar att det finns åtminstone tre problem som vi måste lösa.
Låt oss välja vad som är kanske utan tvekan den enklaste
en, där det nya elementet hör i början.
Så jag kommer att få koden helt som söker, som jag skrev bara.
Och jag ska ha ptr, vilket Jag företräder här med mitt finger,
som vanligt.
>> Och kom ihåg, vilket värde vi initiera ptr till?
Så vi initieras den till null början.
Men vad gjorde vi när vi var inne vår sökfunktion?
Vi sätter det lika med första, vilket inte betyder att göra detta.
Om jag satt ptr lika med först, vad bör min hand verkligen pekar på?
Rätt.
Så om Gabe och jag kommer att vara lika värden här,
Vi behöver både peka på nummer 9.
>> Så det här var början på vår historia.
Och nu detta är bara enkelt, även om syntaxen är ny.
Begreppsmässigt är detta bara linjär sökning.
Är 55 lika med 9?
Eller snarare, låt oss säga mindre än 9.
Därför att jag försöker räkna ut var att sätta 55.
Mindre än 9, mindre än 17, mindre än 20, mindre än 22, mindre än 29,
mindre än 34, nr.
Så nu är vi i mål en av åtminstone tre.
>> Om jag vill infoga 55 hit, vad kodrader behov av att bli avrättade?
Hur fungerar denna bild av människor behöver ändra?
Vad gör jag med min vänstra hand?
Detta bör vara null initialt, eftersom jag är i slutet av listan.
Och vad som ska hända här med Peter, var det?
Han uppenbarligen kommer att peka på mig.
Så jag hävdar att det finns åtminstone två linjer av kod i exempelkod från idag
det kommer att genomföra detta scenariot att lägga 55 i svansen.
Och skulle jag ha någon hop upp och bara representerar 55?
Okej, du är den nya 55.
>> Så nu vad händer om nästa scenario kommer tillsammans,
och vi vill infoga i börjar eller chefen för den här listan?
Och vad är ditt namn, nummer 55?
>> PUBLIKEN: Jack.
>> David J. MALAN: Jack?
OK, trevligt att träffas.
Välkommen ombord.
Så nu ska vi sätt in, säg, antalet 5.
Här är det andra fallet av tre vi kom fram till tidigare.
Så om 5 tillhör i början, Låt oss se hur vi reda på det.
Jag initiera min ptr pekare till nummer 9 igen.
Och jag insåg, åh, 5 är mindre än 9.
Så fixa denna bild för oss.
Vems händer, Gabe s eller Davids eller-- vad är nummer 9 namn?
>> PUBLIKEN: Jen.
>> DAVID J. MALAN: Jens hands-- vilken av våra händer behöver ändra?
OK, så Gabe pekar på vad nu?
På mig.
Jag är den nya noden.
Så jag ska bara typ av drag här för att se det visuellt.
Och under tiden vad ska jag påpeka det?
Fortfarande där jag pekar.
Så det är det.
Så bara egentligen en rad kod fixar denna fråga verkar det.
Okej, så det är bra.
Och kan någon vara en platshållare för 5?
Kom upp.
Vi ska ta dig nästa gång.
>> Okej, så nu-- och Inom parentes namnen
Jag gör inte nämns uttryckligen rätten Nu, pred pekare, föregångare pekare
och nya pekare, det är bara namnen ges
i exempelkod till pekare eller mina händer den typen är av pekar runt.
Vad heter du?
>> PUBLIKEN: Christine.
>> DAVID J. MALAN: Christine.
Välkommen ombord.
Okej, så låt oss betrakta nu en något mer irriterande scenario,
varvid jag vill infoga ungefär 26 in i detta.
20?
Vad?
Dessa är-- bra vi har denna penna.
Okej, 20.
Om någon kunde få en annan bit av papper redo, bara i case-- okej.
Åh, intressant.
Ja detta är ett exempel av en föreläsning bugg.
OK så vad är ditt namn igen?
PUBLIKEN: Julia.
DAVID J. MALAN: Julia, kan du pop ut och låtsas att du var aldrig där?
OK, detta hände aldrig.
Tack.
Så antar att vi vill sätta in Julia in i denna länkad lista.
Hon är nummer 20.
Och naturligtvis är hon kommer att tillhöra vid
begin-- inte peka på något ännu.
Så din hand kan typ av vara ned null eller några sopor värde.
Låt oss berätta snabb historia.
Jag pekar på nummer 5 den här gången.
Sedan kollar jag 9.
Sedan kollar jag 17.
Sedan kollar jag 22.
Och jag inser, ooh, Julia måste gå före den 22.
Så vad måste hända?
Vems händer behöver ändra?
Julias, gruva, eller-- vad heter du nu igen?
>> PUBLIKEN: Christian.
>> DAVID J. MALAN: kristen eller?
>> PUBLIKEN: Andy.
>> DAVID J. MALAN: Andy.
Kristen eller Andy?
Andy behöver peka på?
Julia.
Okej.
Så Andy, vill du peka på Julia?
Men vänta lite.
I berättelsen så här långt, Jag är den typ av man
i laddning, i den meningen att pekaren är det som är
flytta genom listan.
Vi kan ha ett namn för Andy, men det finns ingen variabel som heter Andy.
Den enda andra variabeln vi har är först, vem som representeras av Gabe.
>> Så det här är faktiskt varför alltså länge har vi inte behövt det.
Men nu på skärmen finns nämna igen om Pred pekare.
Så låt mig vara tydligare.
Om detta är pekare, jag hade bättre få lite smartare
om min iteration.
Om du inte har något emot mig gå igenom här igen, pekar här, pekar här.
Men låt mig få ett Pred pekare, föregångare pekare, det är
slags pekar på elementet Jag var bara på.
Så när jag går här, nu min vänstra hand uppdateringar.
När jag går här min vänstra hand uppdateringar.
Och nu har jag inte bara en pekare till det element som går efter Julia,
Jag har fortfarande en pekare till Andy, elementet innan.
Så du har tillgång till, i huvudsak, ströbröd, om ni så vill,
till alla de erforderliga pekare.
>> Så om jag pekar på Andy och jag också peka
på Christian, vars händer bör nu pekade på annat håll?
Så Andy kan nu peka på Julia.
Julia kan nu peka på Christian.
Eftersom hon kan kopiera min högra pekare.
Och som effektivt sätter dig tillbaka till denna plats här.
Så kort sagt, även om detta tar oss slags evigt
att faktiskt uppdatera en lista kopplad, inser
att verksamheten är relativt enkla.
Den är av en, två, tre kodrader i sista hand.
Men lindade runt dem kodrader förmodligen
är lite av logik som effektivt ställer frågan, var är vi?
Är vi i början, mitten eller slutet?
>> Nu, det finns säkert någon annan verksamhet som vi skulle kunna genomföra.
Och dessa bilder här skildrar precis vad vi gjorde precis med människor.
Hur är borttagning?
Om jag vill, till exempel, bort numret 34 eller 55,
Jag kan ha samma typ av kod, men jag kommer att behöva ett eller två steg.
För vad är nytt?
Om jag tar bort någon på slutet, liknande antal 55 och sedan 34,
vad också måste förändras som jag gör det?
Jag måste inte evict-- vad heter du nu igen?
>> PUBLIKEN: Jack.
>> DAVID J. MALAN: Jack.
Jag måste inte bara evict-- gratis Jack, så bokstav ringa gratis Jack, eller åtminstone
pekaren där också, men nu vad som behöver förändras med Peter?
Hans hand bättre start pekar nedåt.
Därför att så fort jag ringer gratis Jack, om Peters fortfarande pekar på Jack
och jag håller därför traversera listan och tillgång denna pekare,
det är då vår gamle vän segmente fel kan faktiskt sparka in.
Eftersom vi har gett minnes tillbaka till Jack.
>> Du kan stanna där tafatt för bara ett ögonblick.
Eftersom vi har bara ett par slutgiltiga åtgärder att överväga.
Ta bort huvudet av listan, eller beginning-- och den här är
lite irriterande.
Eftersom vi måste veta att Gabe är typ av speciell i detta program.
Därför att ja, har han sin egen pekare.
Han inte bara vara riktad mot, som är nästan alla andra här.
>> Så när chefen för listan är avlägsnats, vars händer behöver ändra nu?
Vad heter du nu igen?
>> PUBLIKEN: Christine.
>> DAVID J. MALAN: Jag är hemskt vid namn, tydligen.
Så Christine och Gabe, vars händer måste ändra
när vi försöker ta bort Christine, nummer fem, från bilden?
OK, så låt oss göra Gabe.
Gabe kommer att peka, förmodligen, på nummer 9.
Men vad nästa ska hända?
PUBLIK: Christine bör vara null [ohörbart].
DAVID J. MALAN: OK, vi borde nog märke-- Jag hörde "null" någonstans.
PUBLIK: Null och fri henne.
DAVID J. MALAN: null vad?
PUBLIK: Null och fri henne.
DAVID J. MALAN: Null och fri henne.
Så detta är mycket enkelt.
Och det är perfekt att du är nu sorterar av att stå där, som inte tillhör.
Därför att du har varit frikopplat från listan.
Du har på ett effektivt sätt varit föräldralösa från listan.
Och så vi hade bättre ringa gratis nu Christine för att ge det minnet tillbaka.
Annars varje gång vi ta bort en nod från listan
vi kanske göra listan kortare, men faktiskt inte minskar
storleken på minnet.
Och så om vi fortsätter att lägga till och lägga till, lägga till saker till listan,
min dator kan få långsammare och långsammare och långsammare,
eftersom jag kör ut ur minne, även om jag inte faktiskt
med Christine s bytes minne längre.
>> Så i slutändan finns det andra scenarier, av course-- borttagning
i mitten, borttagning i slutet, som vi såg.
Men mer intressant Utmaningen nu är
kommer att vara att överväga exakt vad gångtid är.
Så kan du inte bara hålla din bitar av papper, om, Gabe,
du inte skulle ha något emot att ge alla en stress boll.
Tack så mycket till vår länkad lista volontärer här, om du kunde.
>> [Applåder]
>> DAVID J. MALAN: Okej.
Så ett par analytisk frågor då, om jag kunde.
Vi har sett denna notation tidigare, stort O och omega, övre gränser
och undre gränser för den gångtid viss algoritm.
Så låt oss betrakta bara ett par frågor.
>> Ett, och vi sa att det tidigare, vad är igång
tiden för sökandet efter en lista när det gäller stora O?
Vad är en övre gräns för driften tiden för att söka en länkad lista
som genomförs av våra volontärer här?
Det är stora O n, linjärt.
Därför att i det värsta fallet, elementet, liksom 55,
Vi kanske letar efter kan vara där Jack var, hela vägen i slutet.
Och tyvärr, till skillnad från en array Vi kan inte få lust den här gången.
Även om alla våra människan var sorterade från små element, fem,
hela vägen upp till den större element, 55, det är oftast en bra sak.
Men vad gör det antagandet inte längre tillåta oss att göra?
PUBLIK: [ohörbart]
DAVID J. MALAN: Säg igen?
PUBLIK: Random access.
DAVID J. MALAN: Random access.
Och i sin tur det betyder att vi kan inte längre använder svaga nollor, intuition,
och självklarhet att använda binära Sök och söndra och härska.
För även om vi människor skulle naturligtvis
se att Andy och Christian var ungefär i mitten av listan,
Vi vet bara att som en dator genom att skumma listan
från början.
Så vi har gett upp att random access.
>> Så stor o n är nu den övre bundet på vår söktid.
Hur är omega i sökandet?
Vad är den undre gränsen för att söka för vissa nummer i den här listan?
PUBLIK: [ohörbart]
DAVID J. MALAN: Säg igen?
PUBLIKEN: One.
DAVID J. MALAN: One.
Så konstant tid.
I bästa fall är Christine faktiskt i början av listan.
Och vi letar efter nummer fem, så vi hittade henne.
Så ingen big deal.
Men hon har fått vara på början av listan i detta fall.
Hur är det något liknande Delete?
Vad händer om du vill ta bort ett element?
Vad är den övre gränsen och den lägre om radering något från en länkad
listan?
PUBLIK: [ohörbart]
DAVID J. MALAN: Säg igen?
PUBLIKEN: n.
DAVID J. MALAN: n är faktiskt den övre gränsen.
Eftersom i värsta fall försöker vi ta bort Jack, som vi just gjorde.
Han är hela vägen i slutet.
Tar oss för alltid, eller n steg för att hitta honom.
Så det är en övre gräns.
Det är linjärt, visst.
Och bästa fall gångtid, eller de nedre gränserna i bästa fall
skulle vara konstant tid.
Eftersom vi kanske försöker ta bort Christine och vi bara har tur
hon är i början.
Vänta lite nu.
Gabe var även i början, och vi hade också uppdatera Gabe.
Så det var inte bara ett steg.
Så är det verkligen konstant tid, i bästa fall,
för att ta bort det minsta elementet?
Det är, även om det kan vara två, tre, eller till och med 100 rader kod,
om det är lika många linjer, inte i någon slinga,
och oberoende av storleken av listan, absolut.
Radera elementet vid början av listan,
även om vi måste ta itu med Gabe, är fortfarande konstant tid.
>> Så detta verkar vara en massiva steg bakåt.
Och vad ett slöseri med tid om, i vecka ett och vecka
noll hade vi inte bara pseudokod kod men faktiska koden
att genomföra något som är log bas n, eller logga snarare n, bas 2,
i termer av dess gångtid.
Så varför i helsike skulle vi vilja börja med hjälp av något som en länkad lista?
Yeah.
>> PUBLIK: Så du kan lägga till element till arrayen.
DAVID J. MALAN: Så du kan lägga till element till arrayen.
Och detta är för tematisk.
Och vi kommer att fortsätta att se detta, denna avvägning, mycket
som vi har sett en avvägning med merge sort.
Vi kunde verkligen påskynda sök eller sortering, snarare
Om vi ​​tillbringar lite mer utrymme och har ytterligare en bit av ett minne
eller ett system för sammanslagnings slag.
Men vi spenderar mer utrymme, men vi sparar tid.
I det här fallet är vi ge upp tid men vi är
få flexibilitet, dynamik, om man så vill,
vilket är utan tvekan ett positivt inslag.
>> Vi är också spendera utrymme.
I vilken mening är en länkad listan dyrare
vad gäller utrymme än en array?
Var är det extra utrymmet kommer från?
Yeah?
>> PUBLIK: [ohörbart] pekare.
>> DAVID J. MALAN: Ja, vi har också pekaren.
Så detta är minorly irriterande i som inte längre är
Jag lagrar bara en int att representera en int.
Jag lagrar en int och en pekare, som också är 32 bitar.
Så jag bokstavligen fördubblas mängden utrymme inblandade.
Så det är en kompromiss, men det är i fallet med int.
Anta att du inte lagrar int, men antar att alla dessa rektanglar
eller var och en av dessa människor representerade ett ord, ett engelskt ord som
kanske fem tecken, 10 tecken, kanske ännu mer.
Sedan lägga bara 32 fler bitar kan vara mindre av en stor sak.
>> Tänk om var och en av eleverna i demonstrationen
var bokstavligen elev structs som har namn och hus och kanske
telefonnummer och Twitter handtag och liknande.
Så alla fält vi började talar om häromdagen,
mycket mindre av en stor sak som våra noder blir mer intressant
och stora att spendera, eh, en extra pekaren bara för att koppla ihop dem.
Men ja, det är en kompromiss.
Och faktiskt, är koden mer komplex, eftersom du kommer
se genom att skumma igenom som särskilt exempel.
Men tänk om det fanns några heliga graal här.
Vad händer om vi inte tar ett steg bakåt men ett stort steg framåt
och genomföra en data struktur via vilken vi
kan hitta element som Jack eller Christine eller andra element
i denna samling i sann konstant tid?
Sök är konstant.
Radera är konstant.
Insert är konstant.
Alla dessa verksamheter är konstanta.
Det skulle vara vår heliga graal.
Och det är där vi kommer att plocka upp nästa gång.
Ser du sedan.