[Powered by Google Translate] [Vecka 6, Fortsättning]
[David J. Malan] [Harvard University]
[Detta är CS50.] [CS50.TV]
Detta är CS50 och detta är slutet på vecka 6.
Så CS50x, en av Harvards första kurser som ingår i EDX initiativet
verkligen debuterade den gångna måndag.
Om du vill få en glimt av vad andra på Internet
följer nu tillsammans med, kan du bege dig till x.cs50.net.
Det kommer att omdirigera dig till rätt plats på edx.org,
som var där detta och andra kurser från MIT och Berkeley lever nu.
Du måste registrera dig för ett konto, hittar du att materialet är i stort sett detsamma
som du har haft denna termin, även om en försenad några veckor, eftersom vi får allt klart.
Men vad elever i CS50x ser nu är ett gränssnitt helt som denna.
Detta, till exempel, är Zamyla leder genomgång för problemet uppsättningen 0.
När du loggar in på edx.org, ser en CS50x studenten möjliga saker
du förväntar dig att se i en kurs: föreläsning för måndag,
föreläsning för onsdag, olika kortfilmer, problemet uppsättningar, de genomgångar, PDF.
Dessutom, som du ser här, maskinöversättning
av engelska avskrifter till kinesiska, japanska, spanska, italienska,
och en hel massa andra språk som säkert kommer att vara ofullständig
när vi rulla ut dem programmatiskt med hjälp av något som kallas en API,
eller application programming interface, från Google
som tillåter oss att konvertera engelska till alla språk.
Men tack vare den underbara anda av några hundra-plus frivilliga
slumpmässiga människor på Internet som vänligt erbjuds att engagera
i detta projekt kommer vi gradvis förbättra dessa översättningar
genom att människor korrigera de misstag som våra datorer har gjort.
>> Så det visar sig att vi hade några fler studenter dyker upp på måndag än vad vi väntat.
Faktum är nu CS50x har 100.000 människor följer tillsammans hemma.
Så inser du är en del av denna inledande klass att göra denna kurs i datalogi
utbildning i allmänhet, mer allmänt, tillgänglig.
Och verkligheten är nu en del av dessa massiva online-kurser,
de börjar alla med dessa mycket höga siffror, som vi tycks ha gjort här.
Men målet i sista hand för CS50x verkligen att få så många människor till mållinjen som möjligt.
Med design, CS50x kommer att erbjudas från det gångna måndag
hela vägen April 15, 2013, så att folk som har skolan åtaganden på annat håll,
arbete, familj, andra konflikter och liknande, har lite mer flexibilitet
som att dyka in i denna kurs, som är det tillräckligt att säga,
är ganska ambitiöst gjort om bara under loppet av bara tre månader under en vanlig termin.
Men dessa elever kommer att ta itu med de samma problem uppsättningar, visar samma innehåll,
ha tillgång till samma shorts och liknande.
Så inse att vi är alla verkligen i samma båt.
Och en av de slutliga målen för CS50x är inte bara att få så många människor
till mållinjen och ge dem denna nyfunna kunskap om datavetenskap
och programmering, men också att få dem har denna gemensamma erfarenhet.
En av de definierande egenskaperna hos 50 på campus, hoppas vi,
har varit denna typ av gemensamma erfarenheter, på gott och ont, ibland,
men med dessa människor att vända sig till till vänster och till höger,
och kontorstid och hackathon och det verkliga.
Det är lite svårare att göra det personligen med folk på nätet,
men CS50x avslutas i april med den allra första CS50 Expo,
som kommer att vara en online anpassning av vår uppfattning om det verkliga
där dessa tusentals studenter kommer alla att uppmanas att lämna in en 1 - till 2-minuters video,
antingen en screencast av deras slutliga projekt eller video av dem vinka hej
och talar om sitt projekt och demonstrerar den,
ungefär som era föregångare har gjort här på campus i mässan,
så att genom termins slut är förhoppningen att få en global utställning
av CS50x studenternas examensarbeten, ungefär som det som väntar dig i december här på campus.
Så mer om detta under de kommande månaderna.
>> Med 100.000 studenter, men kommer ett behov för ett par CA.
Med tanke på att ni har bräschen här och ta CS50
flera veckor i förväg av detta material är utsläpp till folket på EDX,
inser vi skulle älska att engagera så många av våra egna elever som möjligt i detta initiativ,
både under terminen samt denna vinter och den kommande våren.
Så om du vill engagera dig i CS50x,
särskilt gå in på CS50x diskutera, EDX versionen av CS50 diskutera,
som många av er har använt på campus, online anslagstavla,
du göra huvudet till denna URL, låt oss veta vem du är,
eftersom vi vill gärna bygga upp ett team av studenter och personal och lärare både
på campus som helt enkelt spelar med och hjälpa.
Och när de ser en fråga som är bekant för dem,
du hör en student rapporterar vissa programfel någonstans ute i något land på Internet,
och att ringarna en klocka för att du hade för samma fråga
i d-hallen för en tid sedan, förhoppningsvis kan du klämta i och dela dina egna erfarenheter.
Så vänligen ta del om du vill.
>> Datavetenskap kurser vid Harvard har lite av en tradition,
CS50 bland dem, att ha lite kläder, lite kläder, som du kan bära med stolthet
vid termin slut, säger ganska stolt att du klar CS50
och tog CS50 och liknande, och vi försöker alltid att engagera eleverna
i denna process så mycket som möjligt, där vi bjuder in,
här tiden av terminen, studenter lämna konstruktioner
med hjälp av Photoshop, eller vad bästa sättet du vill använda
om du är en designer, lämna mönster för T-shirts och tröjor
och paraplyer och små snusnäsdukar för hundar som vi har nu och liknande.
Och allt är så - vinnarna varje år sedan ut
på kursens hemsida store.cs50.net.
Allt säljs till självkostnadspris där, men webbplatsen just sköter sig själv
och tillåter människor att välja färger och mönster som de vill.
Så jag tänkte att vi bara skulle dela några av förra årets design
som var på webbplatsen utöver detta en här, vilket är en årlig tradition.
"Varje dag jag Seg Faultn" var en av de grunder förra året,
som fortfarande finns där för alumner.
Vi hade den här, "CS50, Etablerad 1989."
En av våra Bowdens, Rob, var mycket populär förra året.
"Team Bowden" föddes, var denna design in, bland de bästa säljarna.
Som var en hit. Många människor hade "Bowden Fever" enligt försäljningen loggar.
Inse att det nu kunde vara din design där upp på Internet.
Mer information om detta i nästa problem sätter komma.
>> En mer verktyg: du har haft viss exponering och förhoppningsvis nu
några praktisk erfarenhet GDB,
vilket naturligtvis en debugger och låter dig manipulera
ditt program på en ganska låg nivå, gör vad slags saker?
Vad låter GDB du göra?
Ja? Ge mig något. [Student svar, obegripligt]
Bra. Kliv in funktionen så att du inte bara skriva köras
och har programmet slag genom sin helhet skriva ut saker till standard ut.
Snarare kan man stega igenom rad för rad, antingen skriva nästa
att gå rad för rad för rad eller steg för att dyka in i en funktion, vanligtvis en som du skrev.
Vad låter GDB du göra? Ja? [Student svar, obegripligt]
Skriv variabler. Så om du vill göra en liten introspektion inuti ditt program
utan att behöva tillgripa skriva printf uttalanden överallt,
kan du bara skriva ut en variabel eller visa en variabel.
Vad kan du göra med en debugger som GDB?
[Student svar, obegripligt]
Exakt. Du kan ställa in brytpunkter, du kan säga break utförande
vid huvudfunktionen eller foo-funktionen.
Du kan säga paus exekvering på rad 123.
Och brytpunkter är en riktigt kraftfull teknik
för om du har en allmän känsla av var problemet
förmodligen behöver du inte slösa tid stega igenom programmets helhet.
Du kan i princip hoppa just där och då börja skriva -
stega igenom det med steg eller nästa eller liknande.
Men fångsten med något som GDB är att det hjälper dig, människan,
hitta dina problem och hitta dina buggar.
Det behöver inte nödvändigtvis hitta dem så mycket för dig.
>> Så vi introducerade häromdagen style50, som är en kort kommandoradsverktyg
som försöker att stilisera din kod lite renare än du, människa kan ha gjort.
Men det är också egentligen bara en estetisk sak.
Men det visar sig att det är det här andra verktyg som kallas Valgrind som är lite mer svårbegripliga att använda.
Dess produktion är vedervärdigt kryptiska vid första anblicken.
Men det är underbart bra, speciellt nu när vi är på den del av begreppet
där du börjar använda malloc och dynamisk minnesallokering.
Saker kan gå riktigt, riktigt fel snabbt.
För om du glömmer att frigöra ditt minne, eller om du dereference någon NULL-pekare,
eller du dereference något skräp pekare, vad är typiskt symptom som resultat?
Seg fel. Och du får denna kärna fil av ett visst antal kilobyte eller megabyte
som representerar tillståndet i ditt program minne när det kraschade,
men ditt program seg slutändan fel, segmenteringsfel,
vilket betyder något dåligt hände nästan alltid relaterat
till ett minne-relaterade misstag som du har gjort någonstans.
Så Valgrind hjälper dig att hitta saker som detta.
Det är ett verktyg som du kör, liksom GDB, efter att du har sammanställt ditt program,
men i stället köra programmet direkt, kör du Valgrind
och du skickar till den ditt program, precis som du gör med GDB.
Nu, användning, för att få den bästa typ av produktion,
är lite lång, så just där uppe på skärmen ser du Valgrind-v.
"-V" nästan överallt betyder detaljerad när du använder program på en Linux-dator.
Så det betyder att spotta ut mer data än du kanske som standard.
"- Läcka-check = full." Detta är bara säga check för alla möjliga minnesläckor,
misstag som jag kan ha gjort. Detta är också en vanlig paradigm med Linux-program.
Generellt, om du har en argumentet kommandorad som är en "switch",
som är tänkt att ändra programmets beteende, och det är en enda bokstav,
Det är-v, men om det är bytt, bara genom utformningen av programmerare,
är en helt ord eller en serie av ord, börjar kommandoraden argument med -.
Dessa är bara mänskliga konventioner, men du kommer att se dem allt.
Och, slutligen, "a.out" är godtyckligt namn för programmet i detta speciella exempel.
Och här är några representativa utgång.
>> Innan vi tittar på vad det kan innebära, låt mig gå över till en kodsträng här.
Och låt mig flytta ur vägen, kommer snart,
och låt oss ta en titt på memory.c, vilket är det korta exemplet här.
Så i det här programmet, låt mig zooma in på de funktioner och frågor.
Vi har en funktion huvud som anropar en funktion, f,
och vad finns anledning f att göra, i något teknisk engelska?
Vad finns anledning f göra?
Vad sägs om jag ska börja med linje 20, och stjärnan läge spelar ingen roll,
men jag ska bara vara konsekvent här med sista föreläsning.
Vad är linjen 20 göra för oss? På vänster sida. Vi ska bryta ner ytterligare.
Int * x: vad betyder det då?
Okej. Det förklarar en pekare, och nu ska vi bli ännu mer teknisk.
Vad betyder det, mycket konkret, att förklara en pekare? Någon annan?
Ja? [Student svar, obegripliga] för långt.
Så du läser den högra sidan av likhetstecknet.
Låt oss fokusera bara på vänster, bara på int * x.
Detta "förklarar" en pekare, men nu låt oss dyka djupare i denna definition.
Vad betyder det konkret, tekniskt menar? Ja?
[Student svar, obegripligt]
Okej. Det förbereder för att spara en adress i minnet.
Bra. Och låt oss ta detta ett steg längre, det är att förklara en variabel, x, det är 32 bitar.
Och jag vet att det är 32 bitar eftersom -?
Det är inte för att det är en int, eftersom det är en pekare i detta fall.
Tillfällighet att det är en och samma sak med en int,
men det faktum att det finns stjärnan finns innebär detta är en pekare
och i apparaten, som med många datorer, men inte alla, pekare är 32 bitar.
På modernare hårdvara som de senaste Mac, de senaste PC, kanske du har 64-bitars pekare,
men i apparaten, dessa saker är 32 bitar.
Så vi ska standardisera på det. Mer konkret går berättelsen som följer:
Vi "förklarar" en pekare, vad betyder det?
Vi förbereder för att lagra en minnesadress.
Vad betyder det?
Vi skapar en variabel kallad X som tar upp 32 bitar
som snart kommer att lagra adressen till ett heltal.
Och det är nog ungefär så exakt som vi kan få.
Det är bra att gå vidare för att förenkla världen och bara säga förklara en pekare som heter X.
Deklarera en pekare, men inse och förstå vad som faktiskt händer
även på bara dessa få tecken.
>> Nu är det här en nästan lite enklare, även om det är en längre uttryck.
Så vad är detta att göra, som är markerad nu: "malloc (10 * sizeof (int));" Ja?
[Student svar, obegripligt]
Bra. Och jag tar det där. Det tilldelning av en bit av minne för tio heltal.
Och nu ska vi dyka i något djupare, det är tilldelning av en bit av minne för tio heltal.
Vad är malloc tillbaka då?
Adressen för denna bit, eller, mer konkret, adressen för den första bitgruppen i denna bit.
Hur då är jag, programmeraren, att veta var den bit av minne slutar?
Jag vet att det är sammanhängande. Malloc, per definition, kommer att ge dig en sammanhängande bit av minnet.
Några luckor i den. Du har tillgång till varje byte i den bit,
rygg mot rygg mot rygg, men hur vet jag var i slutet av denna bit av minnet är?
När du använder malloc? [Student svar, obegripliga] Bra.
Du inte. Du måste komma ihåg.
Jag måste komma ihåg att jag använde värdet 10, och jag tror inte ens verkar ha gjort det här.
Men åligger helt på mig. Strlen, som vi har blivit något beroende för stråkar,
fungerar bara på grund av denna konvention för att ha \ 0
eller denna speciella nul karaktär, NUL, vid slutet av en sträng.
Som inte håller för bara godtyckliga bitar av minnet.
Det är upp till dig. Så ledning 20 då tilldelar en bit av minne
som kan lagra tio heltal, och det lagrar adressen för den första bitgruppen
denna bit av minnet i den variabel som kallas X.
Ergo, vilket är en pekare. Så linje 21, tyvärr var ett misstag.
Men först, vad gör den? Det säger butik på plats 10, 0 indexeras,
av bit av minne som kallas x värdet 0.
>> Så märker ett par saker pågår.
Även om x är en pekare återkalla ett par veckor sedan
att du kan fortfarande använda array-stil notation hakparentes.
Eftersom det är faktiskt kort hand notation för de mer kryptiska utseende pekare aritmetik.
där vi skulle göra något så här: Ta adressen X, flytta 10 platser över,
sedan går det till vad adress lagras på den platsen.
Men ärligt talat, det är bara förfärligt att läsa och bli bekant med.
Så världen använder vanligtvis hakparenteserna bara för att det är så mycket mer mänsklig-vänlig att läsa.
Men det är vad som verkligen händer under huven,
x är en adress, inte en array, i sig.
Så detta lagrar 0 vid läget 10 i x.
Varför är det dåligt? Ja?
[Student svar, obegripliga] Exakt.
Vi tilldelas endast tio Ints, men vi räknar från 0 vid programmering i C,
så du har tillgång till 0 1 2 3 4 5 6 7 8 9 men inte 10.
Så antingen programmet kommer att seg fel eller är det inte.
Men vi vet inte riktigt, det är typ av en nondeterministic beteende.
Det beror egentligen på om vi har tur.
Om det visar sig att operativsystemet inte emot om jag använder det extra byte,
även om det inte har gett det till mig, kanske mitt program krascha inte.
Det är rått, det är buggig, men du kanske inte se att symptom,
eller du kanske ser det bara en gång på ett tag.
Men verkligheten är att felet är i själva verket finns.
Och det är verkligen problematiskt om du har skrivit ett program som du vill vara korrekt,
att du har sålt det program som folk använder den varje gång på ett tag kraschar
eftersom, naturligtvis, är det inte bra. Faktum är att om du har en Android-telefon eller en iPhone
och du hämtar program i dessa dagar, om du någonsin haft en app bara sluta,
plötsligt försvinner, det är nästan alltid resultatet av någon minne-relaterad fråga,
varigenom programmeraren skruvas upp och dereferenced en pekare
att han eller hon bör inte ha, och resultatet av iOS eller Android är att bara döda programmet helt och hållet
hellre än att riskera odefinierat beteende eller någon form av säkerhet kompromiss.
>> Det finns en annan bugg i programmet förutom detta.
Vad har jag skruvas upp i detta program?
Jag har inte tränat som jag har predikat. Ja?
[Student svar, obegripliga] Bra.
Jag har inte befriat minnet. Så tumregel nu
måste vara när du ringer malloc, måste du ringa gratis när du är klar med detta minne.
Nu skulle när jag vill frigöra detta minne?
Förmodligen antar detta första raden var korrekt, skulle jag vilja göra det här.
Eftersom jag inte kunde till exempel göra det här nere. Varför?
Bara av omfattning. Så även om vi pratar om pekare,
Detta är en vecka 2 eller 3 fråga, där x är bara i omfattning insidan av klammerparenteser där den deklareras.
Så du definitivt inte kan befria den där. Min enda chans att frigöra den är ungefär efter linjen 21.
Detta är ett relativt enkelt program, det var ganska lätt när du typ av lindade ditt sinne
runt vad programmet gör, där misstag var.
Och även om du inte ser det först, förhoppningsvis är det lite uppenbart nu
att dessa misstag är ganska lätt att lösa och lätt gjort.
Men när ett program är mer än 12 rader lång, det är 50 rader lång, 100 rader lång,
gå igenom din kod rad för rad, tänka igenom det logiskt,
är möjligt men inte särskilt roligt att göra, ständigt letar efter fel,
och det är också svårt att göra, och det är därför ett verktyg som Valgrind finns.
Låt mig gå vidare och göra detta: Låt mig öppna mitt terminalfönster,
och låt mig inte bara köra minnet, eftersom minnet verkar vara bra.
Jag börjar bli lycklig. Gå till att ytterligare byte i slutet av uppsättningen
verkar inte vara alltför problematisk.
Men låt mig ändå göra en sanity check, vilket betyder bara att kontrollera
huruvida detta verkligen stämmer.
>> Så låt oss göra Valgrind-v - läckage-check = full,
och sedan namnet på programmet i det här fallet är minnet, inte a.out.
Så låt mig gå vidare och göra det. Hit Enter.
Käre Gud. Detta är dess produktion, och det är vad jag hänvisade till tidigare.
Men om du lär dig att läsa igenom hela nonsens här,
det mesta av detta är bara diagnostiska utgång som inte är så intressant.
Vad ögat verkligen vill vara ute efter är något omnämnande av fel eller ogiltig.
Ord som tyder på problem.
Och faktiskt, låt oss se vad som händer fel här nere.
Jag har en sammanfattning av något slag, "används vid avfart:. 40 byte i 1 block"
Jag är inte riktigt säker på vad ett block är ännu, men 40 byte
känns faktiskt som om jag skulle kunna räkna ut var det kommer ifrån.
40 byte. Varför är 40 byte i bruk vid avfart?
Och mer specifikt, om vi rulla ner här,
varför har jag förlorat definitivt 40 byte? Ja?
[Student svar, obegripliga] Perfekt. Ja, exakt.
Det fanns tio heltal, och vart och ett av dessa är storleken på 4, eller 32 bitar,
så jag har förlorat exakt 40 byte eftersom, som ni föreslog, jag har inte kallat fri.
Det är en bugg, och nu ska vi titta ner lite längre och se bredvid detta,
"Ogiltig skriva av storlek 4." Nu vad är detta?
Denna adress uttrycks vad bas notation, tydligen?
Detta är hexadecimalt, och varje gång du ser ett nummer som börjar med 0x,
det betyder hexadecimala, vilket vi gjorde redan på, tror jag, pset 0 avsnitt av frågor,
vilket var bara att göra en uppvärmning övning, konvertera decimal till hex till binärt och så vidare.
Hexadecimala, bara genom mänsklig konvention, används vanligen för att representera pekare
eller, mer allmänt, adresser. Det är bara en konvention,
eftersom det är lite lättare att läsa, det är lite mer kompakt än något som decimal,
och binär är meningslöst för de flesta människor att använda.
Så nu vad betyder det? Det ser ut som det finns en ogiltig skrivning
storlek 4 på linje 21 i memory.c.
Så låt oss gå tillbaka till rad 21, och faktiskt, här är det ogiltigt skriva.
Så Valgrind kommer inte att helt hålla min hand och berätta vad fix är,
men det är att upptäcka att jag gör en ogiltig skrivning.
Jag rör 4 byte som jag inte borde vara, och uppenbarligen det beror,
som ni påpekade, jag gör [10] istället för [9] maximalt
eller [0] eller något däremellan.
Med Valgrind inser när du bevakar nu skriva ett program
som använder pekare och använder minnet, och malloc mer specifikt,
definitivt komma in i vanan att köra denna långa
men mycket lätt kopieras och klistras behärskar Valgrind
för att se om det finns några fel i det.
Och det blir överväldigande varje gång du ser utgången,
men bara tolka igenom visuellt hela produktionen och se om du ser nämner fel
eller varningar eller ogiltiga eller förloras.
Alla ord som låter som om du skruvas upp någonstans.
Så inser att det är ett nytt verktyg i din verktygslåda.
>> Nu på måndag, hade vi en massa folk kommer hit
och representerar begreppet en länkad lista.
Och vi introducerade den länkade listan som en lösning på vilket problem?
Ja? [Student svar, obegripliga] Bra.
Arrayer kan inte ha minne som har lagts till dem.
Om du tilldela en rad storlek 10, det är allt du får.
Du kan ringa en funktion som realloc om du först kallade malloc,
och som kan försöka odla arrayen om det finns utrymme i slutet av det
att ingen annan använder, och om det inte kommer det bara att hitta en större bit någon annanstans.
Men då kommer det att kopiera alla dessa byte till den nya arrayen.
Detta låter som en mycket korrekt lösning.
Varför är det ointressant?
Jag menar det fungerar, har människan löst detta problem.
Varför behövde vi lösa det på måndag med länkade listor? Ja?
[Student svar, obegripliga] Det kan ta lång tid.
Faktum helst du ringer malloc eller realloc eller calloc, vilket är ännu en annan,
varje gång du, programmet talar med operativsystemet,
du tenderar att sakta programmet ner.
Och om du gör den här typen av saker i loopar, du saktar verkligen ner saker.
Du kommer inte att märka detta för den enklaste av "Hello World" typ program,
men i mycket större program, frågar operativsystemet och om igen för minne
eller ge det tillbaka igen och igen brukar inte vara en bra sak.
Dessutom är det bara sorts intellektuellt - det är ett fullständigt slöseri med tid.
Varför avsätta mer och mer minne, riskerar att kopiera allt i den nya arrayen,
Om du har ett alternativ som låter dig tilldela bara så mycket minne som du faktiskt behöver?
Så det finns plus och minus i här.
En av plussidan är nu att vi har dynamik.
Spelar ingen roll om de bitar av minnet är som är gratis,
Jag kan bara sortera om att skapa dessa brödsmulor via pekare
att strängen hela mitt länkad lista tillsammans.
Men jag betala minst en pris.
>> Vad måste jag ge upp att få länkade listor?
Ja? [Student svar, obegripliga] Bra.
Du behöver mer minne. Nu behöver jag utrymme för dessa tips,
och i fallet med denna super länkad enkel lista
som bara försöker lagra heltal, som är 4 byte, håller vi säger
Tja, är en pekare 4 byte, så nu har jag bokstavligen fördubblats
hur mycket minne jag behöver bara lagra den här listan.
Men återigen, detta är en ständig avvägning i datavetenskap
mellan tid och rum och utveckling, arbete och andra resurser.
Vad är en annan nackdel med att använda en länkad lista? Ja?
[Student svar, obegripligt]
Bra. Inte så lätt att komma åt. Vi kan inte längre utnyttja
vecka 0 principer som söndra och härska.
Och mer specifikt, binär sökning. För även om vi människor
kan se ungefär var i mitten av listan är,
datorn vet endast att detta länkade listan börjar vid adress kallade första.
Och det är 0x123 eller något liknande.
Och det enda sättet att programmet kan hitta den mellersta delen
är att faktiskt söka i hela listan.
Och även då måste det bokstavligen att söka hela listan eftersom
även när du når mitten delen genom att följa pekare,
du programmet har ingen aning om hur länge den här listan är potentiellt
tills du träffar i slutet av den, och hur vet du programmatiskt
att du är i slutet av en länkad lista?
Det finns en speciell NULL-pekare, så igen, en konvention.
Hellre än att använda pekare, vi vill definitivt inte att det ska vara något skräp värde
pekar utanför scenen någonstans, vi vill att det ska vara hand ner, NULL,
så att vi har denna ändstation i datastrukturen så vi vet var det slutar.
>> Tänk om vi vill manipulera detta?
Vi gjorde det mesta av detta visuellt och med människor,
men vad händer om vi vill göra en insättning?
Så den ursprungliga listan var 9, 17, 20, 22, 29, 34.
Tänk om vi ville sedan minnesallokera utrymme för nummer 55, en nod för det,
och då vi vill infoga 55 i listan precis som vi gjorde i måndags?
Hur gör vi det? Tja, kom Anita och hon huvudsakligen gick i listan.
Hon började på det första elementet, sedan nästa, nästa, nästa, nästa, nästa.
Slutligen träffade vänster hela vägen ner
och insåg åh, det här NULL. Så vad pekare manipulation måste göras?
Den person som var på slutet, nummer 34, behövde hans vänstra hand upp
att peka på 55, behövde 55 sin vänstra arm nedåt till ny NULL terminatorn. Klar.
Ganska lätt att sätta 55 i en sorterad lista.
Och hur kan detta se ut?
>> Låt mig gå vidare och öppna upp lite kod exempel här.
Jag öppnar gedit, och låt mig öppna upp två filer först.
En är list1.h, och låt mig bara påminna om att detta var bit av koden
att vi använde för att representera en nod.
En nod har både en int som kallas n och en pekare som kallas nästa som bara pekar på nästa sak på listan.
Som nu är i en. H. fil. Varför?
Det är denna konvention, och vi har inte utnyttjat denna en enorm själva,
men den person som skrev printf och andra funktioner
gav som gåva till världen alla dessa funktioner genom att skriva en fil som heter stdio.h.
Och sedan finns det string.h, och sedan finns det map.h, och det finns alla dessa h-filer
som du kanske har sett eller använt under löptiden skrivna av andra människor.
Vanligtvis i dem. H-filer är bara saker som typedefs
eller förklaringar om anpassade typer eller förklaringar konstanter.
Du lägger inte fungerar "implementeringar i header-filer.
Du sätter i stället bara deras prototyper.
Du sätter saker du vill dela med världen vad de behöver
för att sammanställa sin kod. Så bara för att komma in i denna vana,
vi beslutat att göra samma sak. Det finns inte mycket i list1.h,
men vi har lagt något som kan vara av intresse för människor i världen
som vill använda vår länkad lista genomförande.
Nu, i list1.c kommer jag inte gå igenom allt det här
eftersom det är lite långt, det här programmet, men låt oss köra den riktigt snabbt vid prompten.
Låt mig sammanställa List1, låt mig sedan köra List1, och vad du ser är
vi har simulerat ett enkelt litet program här
det kommer att tillåta mig att lägga till och ta bort nummer i en lista.
Så låt mig gå vidare och typ 3 för menyalternativet 3.
Jag vill infoga numret - låt oss göra det första numret, som var 9,
och nu är jag berättat listan är nu 9.
Låt mig gå vidare och göra en annan insättning, så jag slog menyalternativ 3.
Vilket nummer vill jag infoga? 17.
Enter. Och jag ska göra bara en.
Låt mig in numret 22.
Så vi har början till den länkade listan som vi hade i Slidform en stund sedan.
Hur detta införande sker egentligen?
Faktum är 22 nu i slutet av listan.
Så historien vi höra på scenen på måndag och påminde just nu
måste faktiskt händer i koden.
Låt oss ta en titt. Låt mig scrolla ner i denna fil.
Vi kommer släta över några av funktionerna,
men vi gå ner till, säg, Infoga funktion.
>> Låt oss se hur vi går om att infoga en ny nod i denna länkade lista.
Var är listan deklarerade? Nåväl, låt oss rulla hela vägen upp i toppen,
och märker att min länkad lista huvudsak förklaras som en enda pekare som är initialt NULL.
Så jag använder en global variabel här, som i allmänhet har vi predikat mot
eftersom det gör din kod lite rörigt att hålla,
Det är typ av lata, vanligen, men det är inte lat och det är inte fel och det är inte dåligt
Om ditt program enda syfte i livet är att simulera en länkad lista.
Vilket är exakt vad vi gör.
Så snarare än att förklara detta i huvud och sedan måste vidarebefordra den till alla funktioner
Vi har skrivit i detta program, vi istället inse Åh, låt oss bara göra det globala
eftersom hela syftet med detta program är att visa en och endast en länkad lista.
Så det känns okej. Här är mina prototyper, och vi kommer inte att gå igenom alla dessa,
men jag skrev att raderas, ett fynd funktion en insats funktion och en tvärgående funktion.
Men låt oss nu gå tillbaka till Infoga funktion
och se hur det en fungerar här.
Insatsen är på rad - nu kör vi.
Infoga. Så det inte tar några argument, eftersom vi kommer att ställa
användaren insidan av denna funktion för antalet de vill infoga.
Men först, förbereder vi att ge dem lite utrymme.
Detta är en slags kopiera och klistra in från andra exemplet.
I så fall var vi fördela en int, den här gången vi fördela en nod.
Jag vet inte riktigt ihåg hur många byte en nod är, men det är bra.
Sizeof kan räkna ut för mig.
Och varför jag kontroll av NULL i linje 120?
Vad kan gå fel i linje 119? Ja?
[Student svar, obegripligt]
Bra. Bara kunde vara så att jag har bett om för mycket minne
eller något är fel och operativsystemet inte har tillräckligt byte för att ge mig,
så det signalerar lika mycket genom att returnera NULL, och om jag inte kryssar för det
och jag bara blint fortsätta att använda adressen tillbaka, kan det vara NULL.
Det kan vara någon okänd värde, inte bra om jag inte -
faktiskt inte kommer att vara ett okänt värde. Det kan vara NULL, så jag vill inte
att missbruka den och riskera dereferencing det.
Om det händer, återvänder jag och vi ska låtsas som om jag inte fick tillbaka något minne alls.
>> Annars säger jag att användaren ge mig ett nummer att infoga, kallar jag vår gamle vän getInt,
och då detta var den nya syntaxen vi införde på måndagen.
"Newptr-> n avses ta den adress du fick av malloc
som representerar den första byten i ett nytt nod objekt,
och sedan gå till fältet som heter n.
Lite trivia fråga: Detta motsvarar vad mer kryptisk kodrad?
Hur skulle jag ha skrivit det här? Vill du ta ett knivhugg?
[Student svar, obegripligt]
Bra. Med hjälp av. N, men det är inte riktigt så enkelt som det.
Vad ska jag först måste göra? [Student svar, obegripligt]
Bra. Jag behöver göra * newptr.n.
Så detta säger nya pekare är uppenbarligen en adress. Varför?
Eftersom det var tillbaka i malloc. Den * newptr säger "gå dit"
och sedan när du är det, kan du använda den mer bekant. N,
men det ser bara lite ful, speciellt om vi människor kommer att
dra pekare med pilar hela tiden, världen har standardiserat på denna pil notation,
som gör exakt samma sak.
Så du bara använda -> notation när saken till vänster är en pekare.
Annars om det är en verklig struktur använder. N..
Och sedan detta: Varför initiera newptr-> bredvid NULL?
Vi vill inte ha en dinglande vänsterhand från slutet av scenen.
Vi vill att den pekar rakt ner, vilket innebär slutet på denna lista
skulle kunna vara på denna nod, så vi bättre att det är NULL.
Och i allmänhet, initierar dina variabler eller dina data medlemmar och structs
något är bara god praxis.
Bara låta sopor finns och fortsätta att existera i allmänhet får du i trubbel
om du glömmer att göra något senare.
>> Här är några fall. Detta, återigen, är insatsen funktionen,
och det första jag kontrollera är om variabeln kallas först,
att den globala variabeln är NULL, betyder att det inte finns någon länkad lista.
Vi har inte satt in några siffror, så det är trivialt att infoga nuvarande antalet
i listan, eftersom det tillhör bara i början av listan.
Så detta var när Anita var bara står upp här ensam, låtsas
ingen annan var här uppe på scenen tills vi tilldelades en nod,
hon kunde höja sin hand för första gången,
Om alla andra hade kommit upp på scenen efter henne på måndag.
Nu här är det lite kontroll där jag har att säga om den nya noden värde på n
är <värdet på n i den aktuella första noden,
som innebär att det finns en länkad lista som har börjat.
Det finns åtminstone en nod i listan, men denna nya killen
hör innan det, så vi måste flytta runt saker.
Med andra ord, om listan har börjat med bara, låt oss säga,
bara antalet 17, det är - faktiskt, kan vi göra detta tydligare.
Om vi ​​börjar vår berättelse med en pekare här kallas första,
och inledningsvis är det NULL, och vi för in numret 9,
numret 9 hör klart i början av listan.
Så låt oss låtsas vi bara malloced adressen eller numret 9 och lägga den här.
Om första är 9 som standard innebär det första scenariot som vi diskuterat bara låta synpunkt här killen här,
lämna detta som NULL, nu har vi nummer 9.
Nästa nummer vill vi infoga är 17.
17 hör hit, så vi kommer att behöva göra några logiska stega igenom detta.
Så låt oss istället, innan vi gör det, låt oss låtsas att vi ville in numret 8.
>> Så bara för bekvämlighets skull, kommer jag att dra här.
Men kom ihåg, kan malloc uttrycka det mest någonstans.
Men för teckning skull, jag lägger det här.
Så låtsas jag bara har tilldelats en nod för antalet 8, vilket är NULL som standard.
Vad har nu hända? Ett par saker.
Vi gjorde detta misstag på scen på måndag där vi uppdaterat en pekare som denna,
sedan gjorde detta, och vi hävdade - vi föräldralösa alla andra på scenen.
Eftersom du Värre - ordningen på verksamheten här är viktigt,
eftersom vi nu har förlorat denna nod 9 som är bara typ av flytande i rymden.
Så detta var inte rätt inställning till måndag.
Vi måste först göra något annat.
Tillståndet för världen ser ut så här. Initialt har 8 tilldelats.
Vad skulle vara ett bättre sätt att sätta 8?
Istället för att uppdatera denna pekare först bara uppdatera denna en här i stället.
Så vi behöver en kodrad som kommer att vända denna NULL tecken
till en verklig pekare som är pekar på noden 9,
och då kan vi säkert ändra först peka på den här killen här.
Nu har vi en lista, en länkad lista, av två element.
Och vad ser det faktiskt som här?
Om vi ​​tittar på koden, märker att jag har gjort just detta.
Jag har sagt newptr, och i denna berättelse, var newptr pekar på den här killen.
>> Så låt mig dra en sak, och jag skulle ha lämnat lite mer utrymme för detta.
Så förlåt den lilla lilla ritning.
Den här killen heter newptr.
Det är den variabel som vi förklarade några rader tidigare, i linje - strax över 25.
Och det pekar på 8. Så när jag säger newptr-> nästa, det betyder att gå till struct
som är som pekas på av newptr, så här är vi, gå dit.
Sedan pilen säger få nästa fält och sedan = säger sätta vilket värde där?
Det värde som var i första, vilket värde var först?
Först pekade på denna nod, så innebär det nu bör peka på denna nod.
Med andra ord ser det än en löjlig röra med min handstil,
vad är en enkel idé att bara flytta dessa pilar runt
översätter till kod med just detta en liner.
Förvara vad som är först i nästa fält och sedan uppdatera vad första faktiskt är.
Låt oss gå vidare och snabbspola genom en del av detta,
och titta bara på denna svans insättning för nu.
Anta att jag kommer till den punkt där jag tycker att nästa fält av någon nod är NULL.
Och vid denna punkt i berättelsen, en detalj som jag släta över
är att jag har infört en pekare upp här i linje 142, föregångaren pekare.
Huvudsak vid denna punkt i berättelsen, när listan blir lång,
Jag slags behöver gå den med två fingrar för om jag går för långt,
minns en enda lång lista kan du inte gå tillbaka.
Så denna idé om predptr är min vänstra finger och newptr - inte newptr.
En annan pekare som är här är min andra finger, och jag är bara typ av promenader i listan.
Det är därför som finns. Men låt oss bara betrakta en av de enklare fallen här.
Om det pekare nästa fält är NULL, vad är den logiska innebörden?
Om du korsar denna lista och du träffar en NULL-pekare?
Du är i slutet av listan, och så koden för att sedan lägga detta en ytterligare element
är typ av den intuitiva tar att nod vars nästa pekare är NULL,
så detta är för närvarande NULL, och ändra det, men för att vara adressen till den nya noden.
Så vi bara dra i kod på pilen som vi drog på scenen genom att höja någons vänstra hand.
>> Och så att jag viftar mina händer på för nu,
bara för att jag tycker det är lätt att gå vilse när vi gör det i denna typ av miljö,
kontrollerar för insättning på listans mitten.
Men bara intuitivt, behöver det hända om du vill räkna ut
där någon numret tillhör i mitten är du har att gå det
med mer än ett finger, mer än en pekare,
räkna ut där den hör hemma i kontroll är elementet <den nuvarande,
> Den nuvarande, och när du hittar denna plats,
då måste man göra denna typ av skal spel där du flyttar visarna runt mycket noggrant.
Och det svaret, om du vill att resonera igenom detta hemma på egen hand,
handlar om bara dessa två rader kod, men ordningen på dessa linjer är super viktigt.
För om du tappar någons hand och höja någon annans i fel ordning,
igen, kan du hamna föräldralösa i listan.
För att sammanfatta mer konceptuellt är införandet på svansen relativt enkelt.
Insättningen vid huvudet är också relativt enkelt,
men du måste uppdatera ytterligare pekare denna gång
att pressa nummer 5 i listan här,
och sedan insättning i mitten innebär ännu mer arbete,
att mycket noga in numret 20 i dess rätta plats,
vilken är mellan 17 och 22.
Så du måste göra något liknande har den nya noden 20 pekar på 22,
och sedan behöver vilken nod är pekare som skall uppdateras senast?
Det är 17, att faktiskt sätta in det.
Så återigen, jag skjuta den faktiska koden för just genomförandet.
>> Vid en första anblick är det lite överväldigande, men det är egentligen bara en oändlig loop
som är looping, looping, looping, looping, och bryta så fort du träffar NULL-pekare,
då du kan göra den nödvändiga insättningen.
Detta är alltså representativ länkad lista insättning kod.
Det var typ av en hel del, och det känns som vi har löst ett problem,
men vi har infört en helt annan en. Ärligt talat, vi har spenderat all denna tid
på stora O och Ω och gångtid, försöka lösa problem snabbare,
och här tar vi ett stort steg bakåt, det känns.
Och ändå, om målet är att lagra data,
det känns som den heliga Graal, som vi sade på måndagen skulle verkligen vara
att lagra saker direkt.
>> I själva verket, anta att vi gjorde avsatt länkad lista för ett ögonblick
och vi introducerade istället begreppet tabell.
Och låt oss bara tänka på ett bord för ett ögonblick som en matris.
Denna matris och detta fall har här några 26 element, 0 till 25,
och antar att du behövde bit av lagring för namn:
Alice och Bob och Charlie och liknande.
Och du behöver datastruktur för att lagra dessa namn.
Tja, kan du använda något som liknar en länkad lista
och du kan gå på listan sätter Alice före Bob och Charlie efter Bob och så vidare.
Och faktum är att om du vill se koden som det i förbigående,
vet att i list2.h vi göra just det.
Vi kommer inte att gå igenom denna kod, men detta är en variant av det första exemplet
som introducerar en annan struktur som vi har sett tidigare kallade student,
och sedan vad det faktiskt lagrar i den länkade listan är en pekare till en student struktur
snarare än en enkel liten heltal, N.
So inser att det finns kod där som innebär faktiska strängar,
men om målet till hands egentligen nu är att ta itu med effektiviteten problemet,
skulle det inte vara trevligt om vi gett ett objekt som heter Alice,
Vi vill sätta henne i rätt läge i en datastruktur,
det känns som att det skulle vara skönt att bara sätta Alice,
vars namn börjar med A i första läget.
Och Bob, vars namn börjar med B, i den andra platsen.
Med en rad, eller låt oss börja kalla det ett bord, en hash bord på det,
vi kan göra just det. Om vi ​​får ett namn som Alice,
en sträng som Alice, var du sätter en-l-i-c-e?
Vi behöver en hueristic. Vi behöver en funktion för att ta lite input som Alice
och returnera ett svar, "Put Alice på den här platsen."
Och den här funktionen svarta lådan, kommer att kallas en hashfunktion.
>> En hashfunktion är något som tar en ingång, som "Alice",
och återgår till dig, vanligen den numeriska plats i någon datastruktur där Alice hör hemma.
I detta fall bör vi hashfunktion vara relativt enkel.
Vår hashfunktion ska säga, om du får "Alice", vilken karaktär skulle jag bry mig om?
Den första. Så jag ser på [0], och sedan säger jag om [0] karaktär är A returnera antalet 0.
Om det är B, tillbaka 1. Om det är C, återvänder 2, och så vidare.
Alla 0 index, och som skulle tillåta mig att sätta Alice och sedan Bob och sedan Charlie och så vidare
i denna datastruktur. Men det finns ett problem.
Tänk om Anita kommer tillsammans igen?
Var sätter vi Anita? Hennes namn också börjar med bokstaven A,
och det känns som vi har gjort en ännu större röra av detta problem.
Vi har nu omedelbar insättning, konstant tid insättning, i en datastruktur
snarare än värre fall linjär,
men vad kan vi göra med Anita i detta fall?
Vilka är de två alternativen, egentligen? Ja?
[Student svar, obegripligt] Okej, så vi kunde få en annan dimension.
Det är bra. Så vi kan bygga saker i 3D som vi pratade om muntligt på måndag.
Vi kunde lägga till ytterligare tillgång här, men antar att nej, jag försöker hålla det enkelt.
Hela målet här är att ha omedelbar konstant tid tillgång,
så det är att lägga för mycket komplexitet.
Vilka andra alternativ när försöker sätta Anita i denna datastruktur? Ja?
[Student svar, obegripliga] Bra. Så vi kunde flytta alla andra ner,
som Charlie knuffar ned Bob och Alice, och sedan sätter vi Anita där hon verkligen vill vara.
>> Naturligtvis nu, finns det en sidoeffekt av denna.
Detta datastruktur är förmodligen bra inte för att vi vill infoga människor när
men eftersom vi vill kontrollera om de är där senare
om vi vill skriva ut alla namn i datastrukturen.
Vi ska göra något med dessa data så småningom.
Så nu har vi typ av skruvade över Alice, som inte längre var hon ska vara.
Inte heller är Bob, inte heller Charlie.
Så kanske det är inte en så bra idé.
Men i själva verket är detta en möjlighet. Vi kunde skifta alla ned,
eller fan, kom Anita sent till spelet, varför inte vi bara sätta Anita
inte här, inte här, inte här, låt oss bara sätta henne lite lägre i listan.
Men sedan detta problem börjar att överlåta igen.
Du kanske kan hitta Alice direkt, baserat på hennes förnamn.
Och Bob direkt, och Charlie. Men då du letar efter Anita,
och du ser, hmm, är Alice i vägen.
Nåväl, låt mig kolla nedan Alice. Bob är inte Anita.
Charlie är inte Anita. Åh, det är Anita.
Och om du fortsätter att tåget av logik hela vägen,
vad är det värsta gångtid hitta eller sätta Anita i denna nya datastruktur?
Det är O (n), eller hur?
Eftersom det i värsta fall, det finns Alice, Bob, Charlie. . .
ända ner till någon som heter "Y", så det finns bara en plats kvar.
Tack och lov har vi ingen kallas "Z", så vi satte Anita längst ner.
>> Vi har inte riktigt löst problemet.
Så kanske vi behöver införa detta tredje dimensionen.
Och det visar sig, om vi inför denna tredje dimension,
Vi kan inte göra det perfekt, men den heliga gralen kommer att få
konstant tid insättning och dynamiska insättningar så att
Vi behöver inte hård-kod en rad storlek 26.
Vi kan infoga så många namn som vi vill, men låt oss ta vår 5-minuters paus här
och sedan göra det ordentligt.
Okej. Jag satt historien upp ganska artificiellt där
genom att välja Alice och sedan Bob och sedan Charlie och sedan Anita,
vars namn var uppenbarligen kommer att kollidera med Alice.
Men frågan vi slutade i måndags med är hur troligt är det
att du skulle få den här typen av kollisioner? Med andra ord,
om vi börjar använda denna tabellform struktur, vilket egentligen bara en array,
i detta fall av 26 platser,
vad händer om våra insatser i stället jämnt fördelade?
Det är inte artificiellt Alice och Bob och Charlie och David och så vidare alfabetiskt,
det är jämnt fördelad över A till Z.
>> Vi kanske bara har tur och vi kommer inte att ha två A: s eller två B: s
med mycket hög sannolikhet, men som någon påpekade,
Om vi ​​generaliserat detta problem och inte göra 0 till 25
men, säg, 0 till 364 eller 65, ofta antalet dagar i en typisk år,
och ställde frågan, "Vad är sannolikheten för att två av oss i detta rum har samma födelsedag?"
Andra ord, vad är sannolikheten att två av oss har ett namn som börjar med A?
Den typ av fråga är densamma, men den här adressen utrymme,
denna sökning utrymme är större när det gäller födelsedagar,
eftersom vi har så många fler dagar på året än bokstäver i alfabetet.
Vad är sannolikheten för en kollision?
Tja, vi kan tänka på detta genom att räkna ut matten på motsatt sätt.
Vad är sannolikheten för inga kollisioner?
Bra, säger detta uttryck här att vad är sannolikheten
om det finns bara en person i detta rum, att de har en unik födelsedag?
Det är 100%. För om det finns bara en person i rummet,
hans eller hennes födelsedag kan vara någon av de 365 dagar av året.
Så 365/365 optioner ger mig ett värde av 1.
Så sannolikheten i fråga just nu är bara 1.
Men om det finns en annan person i rummet,
vad är sannolikheten att deras födelsedag är annorlunda?
Det finns bara 364 möjliga dagar, ignorerar skottår
för deras födelsedag inte kolliderar med andra personer.
Så 364/365. Om en tredje person kommer in, det är 363/365, och så vidare.
Så vi håller multiplicera ihop dessa fraktioner, som blir mindre och mindre,
att räkna ut vad är sannolikheten att vi alla har unika födelsedagar?
Men då kan vi ju bara ta det svaret och vända runt
och gör 1 minus allt detta, ett uttryck som vi kommer så småningom att få
om du kommer ihåg baksidan av din matte böcker, ser det lite ungefär så här,
vilket är mycket mer lättolkad grafiskt.
Och den här bilden här har på x-axeln antalet födelsedagar,
eller antal personer med födelsedagar, och på y-axeln är sannolikheten för en match.
Och vad detta säger är att om du har, låt oss säga, även,
låt oss välja något som 22, 23.
Om det finns 22 eller 23 personer i rummet,
sannolikheten för att två av dessa mycket få människor kommer att ha samma födelsedag
är faktiskt super hög, kombinatoriskt.
50% odds som i en klass för bara 22 personer, ett seminarium, praktiskt,
2 av dessa människor kommer att ha samma födelsedag.
Eftersom det finns så många sätt som du kan ha samma födelsedag.
Ännu värre, om man tittar på den högra sidan av diagrammet,
med den tid du har en klass med 58 elever i den,
sannolikheten för 2 personer med en födelsedag är super, super hög, nästan 100%.
Nu är den sortens en rolig faktum om verkligheten.
>> Men konsekvenserna, nu för datastrukturer och lagra information
innebär att bara förutsatt att du har en fin, ren, jämn fördelning av uppgifter
och du har en tillräckligt stor mängd för att passa en massa saker
betyder inte att du kommer att få människor i unika platser.
Du kommer att få kollisioner. Så denna föreställning om hashning, som det kallas,
ta en ingång som "Alice" och massera det på något sätt
och sedan få tillbaka ett svar som 0 eller 1 eller 2.
Att få tillbaka en del utdata från funktionen plågas av denna sannolikhet för kollision.
Så hur kan vi hantera dessa kollisioner?
Tja, å ena fallet kan vi ta tanken att föreslogs.
Vi kan bara flytta alla ner, eller kanske, lite enklare,
snarare än att flytta alla andra, låt oss bara gå Anita till botten av den tillgängliga platsen.
Så om Alice är 0, är ​​Bob i 1, Charlie i 2,
Vi ska bara sätta Anita på plats 3.
Och detta är en teknik datastrukturer som kallas linjär sondering.
Linjär eftersom du bara gå denna linje, och du är typ av sondering
för tillgängliga platser i datastrukturen.
Naturligtvis tillfaller detta i O (n).
Om datastrukturen är verkligen full, det finns 25 personer i det redan,
och sedan Anita dyker slutar hon upp på vad som skulle vara plats Z, och det är bra.
Hon passar fortfarande, och vi kan hitta henne senare.
>> Men detta var i strid med målet att påskynda saker.
Så vad händer om vi istället introducerade denna tredje dimension?
Denna teknik är i allmänhet kallas separat kedja, eller har kedjor.
Och vad en hash tabell är nu detta tabellform struktur,
ditt bord är bara en rad pekare.
Men vad dessa pekare pekar på är Gissa vad?
En länkad lista. Så vad händer om vi tar det bästa av båda dessa världar?
Vi använder arrayer för de initiala index
i datastrukturen så att vi kan gå direkt till [0] [1], [30] eller så vidare,
men så att vi har en viss flexibilitet och vi kan passa Anita och Alice och Adam
och alla andra Ett namn,
vi låter istället den andra axeln växa godtyckligt.
Och vi äntligen, och med måndag, har den uttrycksfulla kapacitet med länkad lista.
Vi kan växa en datastruktur godtyckligt.
Alternativt kan vi bara göra en stor 2-dimensionell matris,
men det kommer att bli en hemsk situation om en av raderna i en 2-dimensionell array
inte är tillräckligt stort för den extra person vars namn råkar börja med A.
Gud förbjude att vi måste omfördela en stor 2-dimensionell struktur
bara för att det finns så många människor som heter A,
särskilt när det finns så få människor som heter Z något.
Det kommer bara att vara en mycket gles datastruktur.
Så det är inte perfekt på något sätt, men nu har vi åtminstone har förmågan
att omedelbart hitta där Alice eller Anita tillhör,
åtminstone i termer av den vertikala axeln,
och sedan har vi bara bestämma var att sätta Anita eller Alice i länkad lista.
Om vi ​​inte bryr oss om sortering saker, hur snabbt vi sätter Alice i en struktur som denna?
Det är konstant tid. Vi index i [0], och om ingen är där,
Alice går i början av det länkad lista.
Men det är inte en stor affär. För om Anita kommer sedan längs
visst antal steg senare, inte var Anita tillhör?
Tja, [0]. OOP. Alice är redan i det länkade listan.
>> Men om vi inte bryr oss om sortering dessa namn,
Vi kan bara flytta Alice över, insats Anita, men även det är konstant tid.
Även om det finns Alice och Adam och alla dessa andra A namn,
Det är egentligen inte flytta dem fysiskt. Varför?
Eftersom vi just gjorde här med länkad lista, vem vet var dessa noder är egentligen?
Allt du behöver göra är att flytta brödsmulor.
Flytta pilarna runt, du behöver inte fysiskt flytta data runt.
Så vi kan sätta in Anita, i så fall, direkt. Konstant tid.
Så vi har konstant tid lookup, och konstant tid insättning av någon som Anita.
Men typ av övertydlighet världen.
Tänk om vi senare vill hitta Alice?
Hur många steg är att kommer att ta?
[Student svar, obegripligt]
Exakt. Antalet personer innan Alice i den länkade listan.
Så det är inte helt perfekt, eftersom vår datastruktur, igen, har denna vertikala tillgång
och då har dessa länkade listor hängande - faktiskt, låt oss inte dra det en en matris.
Det har de länkade listor hängande av det som ser lite ut ungefär så här.
Men problemet är om Alice och Adam och alla dessa andra A namn
hamna mer och mer borta,
hitta någon kunde sluta med ett gäng steg,
bcause du korsa den länkade listan,
vilket är en linjär operation.
Så egentligen är då införingen tiden slut O (n), där n är antalet element i listan.
Divided av, låt oss godtyckligt kalla det m, där m är antalet länkade listor
som vi har i denna vertikala axel.
Med andra ord, om vi verkligen tar en jämn fördelning av namn,
helt orealistiskt. Det finns naturligtvis mer av vissa bokstäver än andra.
>> Men om vi antar för tillfället en jämn fördelning,
och vi har n TOTALA människor och m Total kedjor
tillgänglig för oss, sedan längden av vardera av dessa kedjor
ganska enkelt kommer att bli den totala n dividerat med antalet kedjor.
Så n / m. Men här är där vi kan vara allt matematiskt smart.
m är en konstant, eftersom det finns ett fast antal av dessa.
Du kommer att deklarera din array i början,
och vi är inte storleksändring den vertikala axeln. Per definition förblir det fast.
Det är bara den horisontella axeln, så att säga, som är förändras.
Så tekniskt är detta en konstant. Så nu, införandet tiden
är ganska mycket O (n).
Så det inte känns så mycket bättre.
Men vad är sanningen här? Nåväl, hela tiden, i flera veckor,
Vi har sagt O (n ²). O (n), 2 x n ^, - n, dividerat med 2. . . ech.
Det är bara n ^. Men nu, i denna del av terminen,
Vi kan börja tala om den verkliga världen igen.
Och n / m är absolut snabbare än bara n ensam.
Om du har tusen namn, och du bryta upp dem i flera hinkar
så att du har bara tio namn i varje av dessa kedjor,
absolut söka tio saker kommer att vara snabbare än tusen saker.
Och så en av de kommande problem uppsättningar kommer att utmana dig
att tänka just att även om, ja,
asymptotiskt och matematiskt, är detta fortfarande bara linjär,
som suger i allmänhet när man försöker hitta saker.
I verkligheten kommer det att vara snabbare än den
på grund av denna divisor.
Och så finns det återigen kommer att bli denna avvägning
och denna konflikt mellan teori och verklighet,
och en av rattarna börjar vända på denna punkt i terminen
är mer av verkligheten en som vi sorts förbereda semster slut,
när vi introducerar en värld av webbprogrammering,
där verkligen är prestandan kommer att räkna eftersom användarna kommer att
börjar känna och uppskatta dåliga designbeslut.
>> Så hur kan du gå om att genomföra en länkad - en hash tabell med 31 element?
Och det tidigare exemplet var godtyckligt om födelsedagar.
Om någon har en födelsedag den 1 januari eller 1 februari kommer vi att sätta dem i detta hink.
Om det är 2 januari, 2 februari, mars 2, vi lägger dem i denna hink.
Det är därför det var 31. Hur förklarar man en hash-tabell?
Det kan vara ganska enkelt, är nod * Tabell mitt godtyckligt namn för det, [31].
Det ger mig 31 pekare till noderna,
och som gör att jag kan ha 31 pekare till länkade listor
även om dessa kedjor är initialt NULL.
Vad vill jag sätta om jag vill lagra "Alice", "Bob", "Charlie"?
Tja, vi måste packa dessa saker i en struktur
eftersom vi behöver Alice peka på Bob, peka på Charlie, och så vidare.
Vi kan inte bara ha namnen ensam, så jag kunde skapa en ny struktur som kallas nod här.
>> Vad är en verklig nod? Vad är en nod i samband nya lista?
Det första, som kallas ord, är personens namn.
LÄNGD, förmodligen, avser den maximala längden för en människas namn,
vad det är, 20, 30, 40 tecken i galna hörn fall
och en är för vad? Det är bara den extra NULL karaktär, \ 0.
Så denna nod omslag "något" inne i sig själv,
men det förklarar också en pekare som kallas nästa
så att vi kan kedjan Alice till Bob till Charlie och så vidare.
Kan vara NULL men inte nödvändigtvis vara.
Eventuella frågor om dessa hashtabeller? Ja?
[Student frågar fråga, obegripligt] En array - bra fråga.
Varför är denna char ord i en array i stället för bara char *?
I detta något godtyckliga exempel, jag vill inte behöva tillgripa
till malloc för varje ursprungliga namnen.
Jag ville förklara en maximal mängd minne för strängen
så att jag kunde kopiera i strukturen Alice \ 0 och inte måste ta itu med malloc och fri och liknande.
Men jag kunde göra det om jag ville vara mer medvetna om utrymme användning. Bra fråga.
Så låt oss försöka att generalisera bort från detta
och fokusera resten av idag om datastrukturer mer allmänt
och andra problem som vi kan lösa med hjälp av samma grundläggande
även om datastrukturer själva kan skilja på sina uppgifter.
>> Så det visar sig i datavetenskap, träd är mycket vanliga.
Och du kan tänka på ett träd ungefär som ett släktträd,
där det finns en del rötter, vissa matriark eller patriarken,
mormor eller farfar eller tidigare tillbaka,
under vilka mamma och pappa eller olika syskon eller liknande.
Så en trädstruktur har noder och har barn,
vanligen 0 eller fler barn för varje nod.
Och några av jargongen som du ser på bilden här
är någon av de små barnen eller barnbarn på kanterna
som inte har några pilar som härrör från dem,
de är de så kallade löv, och alla på insidan
är en inre nod, du kan kalla det vad som helst i den riktningen.
Men denna struktur är ganska vanligt. Den här är lite godtycklig.
Vi har ett barn till vänster, har vi tre barn till höger,
två barn på längst ner till vänster.
Så att vi kan ha olika stora träd, men om vi börjar standardisera saker,
och du kanske kommer ihåg detta från Patricks video på binärsökning från en tidigare kort
nätet, binärsökning behöver inte genomföras med en rad
eller lappar på en svart tavla.
Anta att du vill spara dina siffror i en mer sofistikerad datastruktur.
Du kan skapa ett träd som denna.
Du kunde ha en nod deklareras i C, och den noden kan ha minst två element i den.
En är det nummer du vill lagra, och den andra är - ja, vi behöver en till.
Den andra är dess barn.
Så här är en annan datastruktur. Denna gång, är en nod definieras som lagrar ett antal n
och sedan två pekare, vänster barn och höger barn.
Och de är inte godtyckliga. Det intressanta om detta träd?
>> Vad är mönstret i hur vi har lagt ut det här eller hur Patrick lade den i hans video?
Det är typ av uppenbart att det finns en viss sortering pågår här,
men vad är den enkla regeln? Ja?
[Student svar, obegripligt]
Perfekt. Om du blick på detta, ser du de små siffrorna till vänster,
stora siffror till vänster, men det är sant för varje nod.
För varje nod, dess vänstra underordnade mindre än den, och dess högra underordnade större än det.
Vad detta innebär nu är om jag vill söka denna datastruktur för, säg, antalet 44,
Jag måste börja vid roten, för som med alla dessa mer komplexa datastrukturer nu,
Vi har bara en pekare till en sak, början.
Och i detta fall, är början roten. Det är inte den vänstra änden,
Det är roten till denna struktur. Så jag ser här är 55, och jag söker 44.
Vilken riktning jag vill gå?
Tja, jag vill gå till vänster, eftersom uppenbarligen är till höger kommer att bli för stor.
Så märker här, du slags konceptuellt hugga trädet halv
eftersom man aldrig kommer ner till höger.
Så nu går jag från 55 till 33. Det är för litet för ett tal.
Jag letar efter 44, men nu vet jag om 44 är i detta träd, kan jag gå självklart till höger.
Så återigen, jag beskärning trädet i halv.
Det är ganska mycket samma begreppsmässigt i telefonboken.
Det är identiskt med vad vi gjorde med papper på tavlan,
men det är en mer sofistikerad struktur som tillåter oss att faktiskt göra
detta söndra och härska genom konstruktion av algoritmen,
och i själva verket korsar en struktur som denna - hoppsan.
Gå igenom en struktur som denna, där det är bara "gå denna väg eller gå den vägen",
innebär allt som kod som böjde dig först när dess genomförande i avsnitt
eller gå igenom det hemma, för binär sökning, med rekursion eller iteration,
Det är en smärta i nacken. Hitta den mellersta delen, så gör din avrundning uppåt eller nedåt.
>> Det finns en skönhet till detta eftersom vi nu kan använda rekursion igen,
men mycket renare. Faktum är att om du är på numret 55 och du vill hitta 44,
du går kvar i det här fallet, vad gör du? Du kör exakt samma algoritm.
Du kontrollerar värdet för noden, då du går åt höger eller vänster.
Då kan du kontrollera värdet för noden, gå vänster eller höger.
Detta passar perfekt för rekursion.
Så även i det förflutna som vi har gjort några ganska godtyckliga exempel där rekursion
som inte behöver vara rekursiv med uppgifter stuktur,
speciellt träd, det är en perfekt tillämpning av denna idé att ta ett problem,
krymper den och sedan lösa samma typ av, men mindre, programmet.
>> Så det finns en annan datastruktur som vi kan införa.
Den här är konstruerad vid en första anblick att se kryptiska, men den här är fantastiskt.
Så detta är en datastruktur som kallas en trie, trie, som ärvs från ordet hämtning
som inte uttalas försöka igen-val, men det är vad världen kallar dessa saker. Försöker. T-R-I-e.
Det är en trädstruktur av något slag, men var och en av noderna i en trie
verkar vara vad? Och detta är lite missvisande eftersom det är typ av förkortad.
Men det ser ut som varje nod i trie är faktiskt en matris.
Och även om författaren till detta diagram inte har visat det,
I det här fallet är det trie en datastruktur vars syfte i livet är att lagra ord
som A-L-I-C-E eller B-O-b.
Och det sätt på vilket dessa uppgifter lagrar Alice och Bob och Charlie och Anita och så vidare
är den använder en array där att lagra Alice i en trie,
vi börjar vid rotnoden som ser ut som en matris,
och det skrivits i stenografi notation.
Författaren utelämnas abcdefg eftersom det fanns inga namn med det.
De visade endast M och P och T, men i detta fall,
låt oss gå bort från Alice och Bob och Charlie till vissa namn som är här.
Maxwell är faktiskt i detta diagram.
Så hur gjorde författaren butiken M-A-X-w-e-l-l?
Han eller hon började på rotnoden, och gick till [M], så ungefär 13, den 13: e plats i arrayen.
Sedan därifrån, det finns en pekare.
En pekare som leder till en annan uppsättning.
Därifrån författaren indexeras i matrisen i lokal A, vilket visas där uppe till vänster,
och då han eller hon följde pekare till en annan array,
och gick till pekaren på platsen X.
Sedan i nästa arrayen platsen W, E, L, L, och så vidare,
och slutligen, låt oss faktiskt försöka lägga in en bild på detta.
Hur ser en nod se ut i kod?
En nod i en trie innehåller en array av pekare till fler noder.
Men det finns också fick vara någon form av booleskt värde, åtminstone i detta genomförande.
Jag råkar kalla det is_word. Varför?
För när du sätter Maxwell, du sätter inte
något i detta datastruktur.
Du skriver inte M. Du inte skriver X.
Allt du gör är följande pekare.
Pekaren som representerar M, då pekaren som representerar A,
då pekaren som representerar X, då är W, E, L, L,
men vad du behöver göra i slutet är typ av att gå, kontrollera nådde jag denna plats.
Det var ett ord som slutar här i datastrukturen.
>> Så vad en trie verkligen fylld med och författaren valde att representera
Dessa terminuses med små trianglar.
Det betyder bara att det faktum denna triangel är här, här booleska värdet true
innebär att om du går bakåt i trädet,
det betyder ett ord som heter Maxwell är i denna.
Men ordet foo, till exempel,
inte i trädet, för om jag börjar på rotnoden här uppe på toppen,
Det finns ingen f pekare, ingen o pekare, ingen o pekare. Foo är inte ett namn i denna ordbok.
Utan däremot Turing, t-u-r-i-n-g. Återigen, jag sparar inte t eller u eller r eller i eller n eller g.
Men jag gjorde butik i denna datastruktur värdet true ner här i nod - i trädet
genom att sätta denna booleskt värde av is_word till true.
Så en trie är typ av denna mycket intressanta meta struktur,
där du inte riktigt lagra ord själva för denna typ av ordbok.
För att vara tydlig, du bara lagrar ja eller nej, det är ett ord som slutar här.
>> Nu vad är innebörden?
Om du har 150.000 ord i en ordbok som du försöker lagra i minnet
med något som liknar en länkad lista,
du kommer att ha 150.000 noder i din länkad lista.
Och hitta en av dessa ord alfabetiskt kunde ta O (n) tid.
Linjär tid. Men i fallet här en trie,
vad är gångtiden att hitta ett ord?
Det visar sig skönheten här är att även om du har 149.999 ord redan i detta lexikon,
som genomförts med denna datastruktur,
hur mycket tid tar det att hitta eller sätta en ytterligare person till att som Alice, Alice?
Tja, det är bara 5, kanske 6 steg för efterföljande tecken.
Eftersom presense av andra namn i strukturen
blir inte i vägen för insättning Alice.
Dessutom hitta Alice när det finns 150.000 ord i denna ordbok
blir inte i vägen för att hitta Alice alls,
eftersom Alice är. . . . . här, eftersom jag hittade ett booleskt värde.
Och om det inte finns någon boolean true, så Alice är inte i denna datastruktur av ord.
Med andra ord, speltid för att hitta saker och sätta saker i detta nya
datastruktur av trie är O - det är inte n.
Eftersom presense av 150.000 människor har ingen effekt på Alice, verkar det.
Så låt oss kalla det k, där k är den maximala längden av ett ord på engelska
vilket är typiskt inte mer än 20-något tecken.
Så k är en konstant. Så den heliga gralen vi tycks ha funnit nu
är att en trie konstant tid för insatser för uppslagningar för strykningar.
Eftersom antalet saker som redan finns i strukturen,
som inte ens fysiskt där. Återigen, de är bara typ av förprickat, ja eller nej,
har ingen inverkan på dess framtida gångtid.
>> Men det mĺste finnas en hake, annars skulle vi inte ha slösat bort så mycket tid
på alla dessa andra datastrukturer bara för att äntligen komma till den hemliga ett som är fantastiskt.
Så vad pris betalar vi för att uppnå detta storhet här? Utrymme.
Denna sak är massiv. Och anledningen till att författaren
lade inte fram det här, notera att alla dessa saker som ser ut som arrayer,
han inte dra resten av trädet, resten av trie,
eftersom de är helt enkelt inte relevant för berättelsen.
Men alla dessa noder är super bred, och varje nod i trädet tar upp
26 eller faktiskt, kan vara 27 tecken eftersom i detta fall var jag bland annat utrymme för apostrof
så att vi kunde få apostrophized ord.
I detta fall, är dessa stora kedjor. Så även om de inte är picutured,
detta tar upp en stor mängd RAM-minne.
Som kan vara bra, especilly i modern hårdvara,
men det är avvägning. Vi får mindre tid genom att spendera mer utrymme.
Så var kommer detta allt?
Nåväl, låt oss göra - låt oss se här.
Låt oss göra ett hopp till den här killen här.
>> Tro det eller ej, lika roligt som C har funnits en tid nu,
vi når den punkt i termin där det är dags att övergå till saker mer moderna.
Saker på en högre nivå. Och även om för ett par veckor
vi ändå fortsätta att fördjupa oss i en värld av pekare och minneshantering
att få det bekvämt som vi sedan kan bygga vidare på,
slutspelet är ytterst att införa, ironiskt nog, inte detta språk.
Vi kommer att spendera, som 10 minuter talar om HTML.
Allt HTML är är ett märkspråk och vad en märkspråk är
är dessa serier av öppna konsoler och stängda fästen som säger "gör detta djärva"
"Göra detta kursiv '' gör denna centrerad."
Det är inte så intellektuellt intressant, men det är super bra.
Och det är verkligen överallt dessa dagar.
Men vad är kraftfull om världen av HTML och webbprogrammering mer generellt,
bygger dynamiska saker, skriva kod i språk som PHP eller Python eller Ruby eller Java eller C #.
Verkligen, oavsett ditt språk val är, och genererar HTML dynamiskt.
Generera något som kallas CSS dynamiskt.
Cascading Style Sheets, vilket också om estetik.
Och så även om idag, om jag går till någon hemsida som bekant Google.com,
och jag går att visa, utvecklare, visa källa, som kanske du har gjort tidigare,
men kommer att visa källan ser det här förmodligen ganska kryptiskt.
Men detta är den underliggande koden som implementerar Google.com.
På den främre änden. Och faktiskt allt detta är fluffigt estetik grejer.
Detta är CSS här uppe. Om jag håller rulla ner vi kommer få några färgkodade saker.
Detta är HTML. Googles kod ser ut som en enda röra, men om jag faktiskt öppna upp ett annat fönster
Vi kan se några struktur till detta.
Om jag öppnar upp, märker här, det är lite mer lättläst.
Vi kommer att se snart denna tagg, [ord] är en tagg,
HTML, huvud, kropp, div, manus, textområdet, span, centrerad, div.
Och detta är ganska också kryptiska utseende vid första anblicken,
men allt den här röran följer vissa mönster och repeterbara mönster,
så att när vi får grunderna ner, kommer du att kunna skriva kod som denna
och sedan manipulera kod som denna med ytterligare ett annat språk, som kallas JavaScript.
Och JavaScript är ett språk som körs inuti en webbläsare
idag som vi använder på Harvard kurser för kursen shoppa verktyg som Google Maps använder
för att ge dig en massa dynamik ger Facebook dig att visa omedelbar statusuppdateringar,
Twitter använder den för att visa dig tweets direkt.
Allt detta kommer vi att börja fördjupa oss i.
Men för att komma dit måste vi förstå lite om Internet.
Detta klipp här är bara en minut lång, och låt oss anta för nu är i själva verket
hur Internet fungerar som en teaser för vad som är på väg att komma. Jag ger dig "Warriors of the Net."
>> [♫ Långsam kör musik ♫]
[Man berättare] Han kom med ett budskap.
Med ett protokoll hela sin egen.
[♫ Snabbare elektronisk musik ♫]
Han kom till en värld av häftiga brandväggar, likgiltig routrar,
och faror långt värre än döden.
Han är snabb. Han är stark. Han är TCP / IP, och han har din adress.
Krigare av nätet.
[Malan] Nästa vecka, då. Internet. Webbprogrammering. Detta är CS50.
[CS50.TV]