[Powered by Google Translate] [Vecka 6] [David J. Malan] [Harvard University] [Detta är CS50.] [CS50.TV] 

Detta är CS50, och detta är början av vecka 6, så ett par nya verktyg finns nu tillgängliga för dig att dra nytta av, Den första som kallas CS50 Style. Oddsen är om du är som mig eller någon av de pedagogiska stipendiater, Du har säkert sett ett program vars stil ser lite ut ungefär så här. Kanske du börjar skära vissa hörn sent på kvällen, eller du kommer att ta itu med det senare, och sedan en TF eller CA kommer över under kontorstid. Då är det svårt för oss att läsa. Nåväl, detta är koden syntaktiskt korrekt, och det kommer att sammanställa, och det kommer faktiskt köra. Men det är definitivt inte en 5 för stil. 

Men nu, när vi går in i den här katalogen här- och märker att jag har conditions2.c- och jag kör det här nya kommandot, style50 på denna fil conditions2.c, Enter, märker att det är informerat mig om att det har varit stiliserade. Gedit märkte att filen har ändrats på disk, och om jag klickar på ladda, alla dina problem nu automatiseras. [Applåder] Det är en av de saker vi gjorde i helgen. Inse att det är bristfälligt eftersom det finns lite kod att det helt enkelt inte att kunna stilisera perfekt, men inser att detta är nu ett verktyg som du kan dra nytta av om så bara för att städa upp några av de mer errantly placerade klammerparenteser och liknande. 

Men mer övertygande är nu CS50 Sök. Med CS50 Check kan du utföra faktiskt samma korrekthet tester på din egen kod att undervisningen stipendiater kan. Detta är en kommandorad verktyg som kommer nu i apparaten så fort du gör en update50 enligt Pset 4 specifikationer, och du använder det i huvudsak så här. Du kör kommandot check50. Då du passerar på ett argument, eller mer allmänt känd som en switch eller en flagga. Generellt är saker som har bindestreck kallas en switch till en kommandorad program anger så-C de kontroller som du vill köra. 

De tester som du vill köra identifieras unikt av denna sträng, 2012/pset4/resize. Med andra ord, det är bara en godtycklig men unik sträng som vi använder för att identifiera pset 4 är korrekthet tester. Och sedan anger ett utrymme separerat lista över de filer som du vill ladda upp till CS50 Sök för analys. Till exempel, om jag går in i min lösning här resize.c- Låt mig öppna upp en större terminalfönster- och jag gå vidare och köra låt oss säga check50-C 2012/pset4/resize, och då går jag vidare och ange namnen på de filer, resize.c, och sedan trycka Enter, det komprimerar, det uppladdningar, kontrollerar det, och jag bara misslyckats en massa tester. Den i rött uppe till vänster säger att resize.c och bmp finns. Det var testet. Det var den fråga vi ställde. Och det är olycklig eftersom svaret var falskt. Den vita texten nedan står det förväntade bmp.h att existera, och det är helt enkelt mitt fel. Jag glömde att ladda upp den, så jag måste ladda upp båda filerna, resize.c och bmp.h. Men nu märker alla andra tester i gult, eftersom de inte har kört, och så smiley är vertikal eftersom han är varken glad eller ledsen, men vi måste rätta att fråga i rött innan de andra kontroller körs. 

Jag löser det här. Låt mig zooma ut och köra detta, denna gång med bmp.h också på kommandoraden, Enter, och nu om allt går väl, det kommer att kontrollera och sedan returnera ett resultat av-hålla andan- alla gröna, vilket betyder att jag gör riktigt bra på pset 4 hittills. Du kan se och utläsa den beskrivande texten här exakt vad det är vi testat. Vi testade först göra filerna finns? Vi testade sedan gör resize.c sammanställa? Sedan testade vi det inte ändra storlek på ett 1x1 pixlar BMP när n, ändra storlek faktorn är 1. Nu, om du har ingen aning om vad n är, kommer du när du dyka in pset 4, men det är helt enkelt en sanity kontrollera att se till att du inte ändrar storlek en bild alls om resize faktorn är 1. Om däremot ändrar storlek det 1x1 pixel till en 1x1 pixel BMP till 2x2 korrekt när n är 2, då liknande, bildar min därefter. 

Kort sagt, detta tänkt att, en, ta korsar fingrarna ur ekvationen rätt innan du skickar din pset. Du kommer att veta exakt vad din TF snart kommer att veta när du går om hur du skickar några av dessa problem uppsättningar, och även pedagogiska motivationen är verkligen att sätta möjlighet framför dig så att när du vet på förhand att det finns fel i din kod och tester som inte blir godkända, du kan sätta i mer effektiv tid up front för att lösa dessa problem snarare än att förlora poäng, få feedback från din TF, och sedan gå, "Ahh," som jag borde ha listat ut. Nu åtminstone finns ett verktyg som hjälper dig att hitta det. Det kommer inte att peka ut var felet är, men det kommer att berätta vad är symptomatisk för det. 

Nu inser tester är inte nödvändigtvis uttömmande. Bara för att du får en skärm full av gröna smiley ansikten betyder inte din kod är perfekt, men det betyder att det har gått vissa tester som föreskrivs av spec. Ibland kommer vi inte att släppa kontrollen. Till exempel deckare, en av de aspekter av pset 4, är typ av en besvikelse om vi ger dig Svaret på vad det är, och det finns ett antal olika sätt att avslöja vem personen är i det röda buller. Spec kommer alltid ange i framtiden för pset 5 framåt vilka kontroller finns för dig. Du kommer att märka att det är det här vita webbadress längst ner. För nu är det bara diagnostiska utgång. Om du besöker denna webbadress får du en massa galna, kryptiska meddelanden att du är välkommen att titta igenom, men det är mest för personalen så att vi kan diagnostisera och felsöka buggar i check50 sig. 

Utan väsen, låt oss gå vidare till där vi slutade. CS50 bibliotek vi tog för givet under några veckor, men än förra veckan började vi riva en av de lager av det. Vi började lägga undan sträng till förmån för vad i stället? [Studenter] Char. Char *, som har varit en char * hela tiden, men nu har vi inte låtsas att det är en verklig datatypen sträng. Snarare har det varit en synonym slags för char *, och en sträng är en sekvens av tecken, så varför gör det meningsfullt att representera strängar som char * s? Vad representerar en char * i samband med detta koncept i en sträng? Ja. >> [Student] Det första tecknet. Bra, det första tecknet, men inte riktigt det första tecknet. Det är de-[Studenter] Adress. Bra, adressen till den första tecknet. Allt som är nödvändigt för att representera en sträng i en dators minne är bara den unika adressen för den första bitgruppen. Du behöver inte ens veta hur lång tid det är eftersom hur kan du räkna ut dynamiskt? [Student] Sträng längd. Du kan ringa stränglängd, utmärkt, men hur fungerar stränglängd? Vad gör det? Ja. [Student] Fortsätt tills du får noll karaktär. Ja, exakt, itererar bara med en for-slinga, medan slinga, vad från * till slutet, och slutet är representerad av \ 0, den så kallade nul karaktär, NUL, inte att förväxla med null, vilket är en pekare, som kommer upp i konversationen igen idag. 

Vi skalade tillbaka ett lager av getInt, och sedan tog vi en titt på GetString, och minns att båda dessa funktioner, eller egentligen, GetString var med en viss funktion att faktiskt tolka, är att läsa eller analysera användarens input. Och vad var det ny funktion? Scanf eller sscanf. Det kommer faktiskt i några olika smaker. Det finns scanf, det finns sscanf, det finns fscanf. För nu, men låt oss fokusera på det som mest lätt illustreras, och låt mig gå vidare och öppna upp i apparaten en fil som denna, scanf1.c. Detta är en super enkelt program, men som gör något som vi aldrig gjort utan hjälp av CS50 biblioteket. Detta får en int från en användare. Hur fungerar det? Tja, i linje 16 där, märker att vi förklarar en int som kallas X, och på denna punkt i berättelsen, vad är värdet av x? [Ohörbart elev svar] [David M.] Höger, vem vet, vissa skräp värde potentiellt, så i 17, säger vi bara användaren ge mig ett nummer, och steg 18 är där det blir intressant. Scanf verkar låna en idé från printf att det använder dessa format koder inom citationstecken. % D är naturligtvis ett decimaltal. Men varför jag passerar i & X istället för bara x? Den förstnämnda är korrekt. Ja. [Ohörbart elev svar] Exakt, om målet med detta program, liksom funktionen getInt själv, är att få en int från användaren jag kan passera funktioner alla variabler jag vill, men om jag inte klarar dem genom hänvisning eller efter adress eller efter pekare, alla synonymt för dagens ändamål, då denna funktion inte har någon möjlighet att ändra innehållet i den variabeln. Detta skulle passera i en kopia precis som den buggig version av swap att vi har pratat om ett par gånger nu. 

Men istället, genom att göra & X, jag passerar bokstavligen i vad? [Student] Adressen. >> Adressen till x. Det är som att rita en karta för den funktion som heter scanf och säger här, dessa är vägbeskrivning till en bit av minne i datorn att du kan gå lagra viss heltal i. För att sscanf att nu göra det vilken operatör, vad är del av syntax det kommer att behöva använda även om vi inte kan se det eftersom någon annan skrev denna funktion? Med andra ord - vad är det? [Student] X läsa. Det kommer att bli lite läsning, men bara när det gäller X här. Om scanf håller passerat adressen av x, syntaktiskt, vad operatören skyldig att existera någonstans insidan av scanf genomförande så att scanf kan faktiskt skriva ett nummer 2 till den adressen? Ja, så *. Minns att * är vår dereference aktör och som i huvudsak innebär att gå dit. 

När du har gått i arv en adress, vilket är fallet här, scanf är förmodligen-om vi såg faktiskt runt sin källkod- gör * x eller motsvarande att faktiskt gå till den adressen och sätta något värde där. Nu, som för hur scanf får input från tangentbordet, vi vifta våra händer ute för idag. Bara anta att operativsystemet tillåter sscanf att prata till användarens tangentbord, men vid denna punkt nu i linje 19, när vi helt enkelt skriva ut X, det verkar vara fallet som scanf har satt en int i x. Det är precis hur scanf fungerar och hämta förra veckan det är exakt hur GetString och getInt och dess andra familjen av funktioner slutändan fungerar, om än med liten avvikelse som sscanf, vilket innebär skanna en sträng i stället för tangentbordet. Men låt oss ta en titt på en liten varians detta. Under scanf2, skruvas jag faktiskt upp. Vad är fel, och jag gömmer den kommentar som förklarar så mycket, vad som är fel med det här programmet, version 2? Var så teknisk som möjligt den här gången. Det ser ganska bra. Det är snyggt indragen, men- okej, vad sägs om vi beskär ner till kortare frågor? Linje 16. Vad är linjen 16 gör i exakt men teknisk engelska? Att få lite pinsamt. Ja, Michael. [Student] Det pekar på första bokstaven i en sträng. 

Okej, nära. Låt mig tweak att lite. Pekar på första bokstaven i en sträng, du deklarera en variabel som heter buffert som pekar på den första adressen av en sträng, eller snarare kommer att peka mera specifikt till en char. Notera det faktiskt inte peka någonstans eftersom det inte finns någon uppgift operatör. Det finns inga likhetstecken, så allt vi gör är att fördela variabel kallad buffert. Det råkar vara 32 bitar eftersom det är en pekare, och innehållet i buffert antagligen småningom kommer att innehålla en adress till en röding, men nu, vad buffert innehålla? Bara några falska, vem vet, vissa skräp värde, eftersom vi inte har uttryckligen initierats det, så vi bör inte ta något. Okej, så nu linje 17 är-vad gör linjen 17 gör? Kanske det kommer att värma upp detta. Den skriver en sträng, eller hur? Den skriver String tack. 

Linje 18 är typ av bekant nu i att vi bara såg en varians detta men med ett annat format kod, så i linje 18, vi säger scanf här är adressen till en bit av minne. Jag vill att du ska ringa i en sträng, vilket antyds av% s, men problemet är att vi inte har gjort ett par saker här. Vad är ett av problemen? [Student] Den försöker dereference en null-pekare. Bra, null eller bara annars okända pekare. Du lämnar scanf en adress, men du sa bara för en stund sedan att den adressen är något skräp värde eftersom vi faktiskt inte tilldela den till något, och så du säger scanf effektivt gå sätta en sträng här, men vi vet inte var här ännu är, så vi har faktiskt inte allokerat minne för buffert. Dessutom, vad är du inte heller ens berätta scanf? Antar att detta var en bit av minnet, och det var inte ett skräp värde, men du är fortfarande inte berätta scanf något viktigt. [Student] Om det faktiskt är, et-tecknet. Ampersand, så i detta fall, det är okej. Eftersom buffert redan förklarat som en pekare med * bit syntax, behöver vi inte använda et-tecken eftersom det är redan en adress, men jag tror att jag hörde det här. [Student] Hur stort är det? Bra, vi berättar inte scanf hur stor denna buffert är, vilket innebär att även om bufferten var en pekare, vi säger scanf, sätta en sträng här, men här kan vara 2 byte, kan det vara 10 byte, kan det vara en megabyte. Scanf har ingen aning, och eftersom detta är en bit av minne förmodligen är det inte en sträng ännu. Det är bara en sträng när du skriver tecken och en \ 0 som bit av minnet. Nu är det bara några bit av minnet. Scanf inte vet när du ska sluta skriva till den adressen. 

Om ni minns några exempel i det förflutna där jag slumpmässigt skrivit på tangentbordet försöker spilla en buffert, och vi pratade på fredag ​​om just detta. Om en motståndare injicerar något i ditt program en mycket större ord eller mening eller fras då du väntade dig kan överskridande en bit av minnet, vilket kan få dåliga konsekvenser, som att ta över hela programmet själv. Vi måste fixa det här på något sätt. Låt mig zooma ut och gå in version 3 av programmet. Det är lite bättre. I denna version märker skillnaden. I linje 16, jag förklara igen en variabel som heter buffert, men vad är det nu? Det är en samling av 16 tecken. Detta är bra eftersom det betyder att jag nu kan berätta scanf här är en verklig bit av minnet. Du kan nästan tänka arrayer som pekare nu, även om de är faktiskt inte likvärdiga. De kommer bete sig på olika sätt i olika sammanhang. Men det är verkligen så att bufferten refererar 16 sammanhängande tecken eftersom det är vad en matris är och har varit i några veckor nu. 

Här säger jag scanf här är en bit av minne. Den här gången är det faktiskt en bit av minne, men varför är det här programmet fortfarande utnyttjas? Vad är det för fel ännu? Jag har sagt ge mig 16 byte, men- [Student] Vad händer om man skriver in mer än 16? Exakt, vad händer om användaren skriver i 17 tecken eller tecken 1700? I själva verket, låt oss se om vi inte kan snubbla över detta misstag nu. Det är bättre men inte perfekt. Låt mig gå vidare och kör make scanf3 att sammanställa detta program. Låt mig köra scanf3, String snälla: hej, och vi verkar vara okej. Låt mig försöka lite längre en, hello there. Okej, låt oss göra hello there hur mår du idag, Enter. Att få typ av tur här, låt oss säga hello there hur mår du. Fan också. Okej, så vi hade tur. Låt oss se om vi inte kan fixa det här. Nej, det kommer inte att låta mig kopiera. Låt oss prova det här igen. Okej, stand by. Vi får se hur länge jag kan låtsas att fokusera samtidigt gör detta. Fan också. Det är ganska passande, faktiskt. Där kör vi. Punkt gjort. 

Detta pinsamt men det är också, det är också en av orsakerna till stor förvirring när du skriver program som har fel eftersom de visar sig endast en gång på ett tag ibland. Verkligheten är att även om din kod är helt bruten, det kan bara vara helt brytas då och då eftersom det ibland, i huvudsak vad som händer är operativsystemet allokerar lite mer minne än du behöver faktiskt av någon anledning, och så att ingen annan använder minnet direkt efter bit av 16 tecken, så om du går till 17, 18, 19, vad som helst, det är inte så stor roll. Nu, datorn, även om det inte kraschar vid den punkten, kan så småningom användas byte nummer 17 eller 18 eller 19 för något annat, vid vilken punkt dina data som du lagt där, om än alltför lång, kommer att få skrivas över potentiellt av någon annan funktion. Det är inte nödvändigtvis kommer att förbli intakt, men det kommer inte nödvändigtvis orsaka en seg fel. Men i detta fall, förutsatt att jag äntligen tillräckligt många tecken att jag överskridit huvudsak mitt segment av minne och bam, operativsystemet sa: "Tyvärr, det är inte bra, segmenteringsfel." 

Och låt oss se nu om det som återstår här i min katalog- märker att jag har den här filen här, kärna. Observera att detta återigen kallas minnesutskriftsfil. Det är i huvudsak en fil som innehåller innehållet i programmets minne vid den punkt där det kraschade, och bara för att prova lite exempel här Låt mig gå in här och kör gdb på scanf3 och sedan ange en tredje argument som kallas kärna, och märker här att om jag lista koden Vi kommer att kunna som vanligt med gdb för att börja gå igenom detta program, och jag kan köra den och så fort jag hit-som med steg kommandot i gdb- så fort jag slog potentiellt buggig rad efter att skriva i en stor sträng, Jag kommer att kunna verkligen identifiera den här. Mer om detta, men i snitt i termer av grundläggande dumpar och liknande så att du faktiskt kan rota runt inne i kärnan dumpa och se på vilken linje programmet misslyckades dig. Har du frågor så om pekare och adresser? Eftersom idag på, kommer vi att börja ta för givet att dessa saker existerar och vi vet exakt vad de är. Ja. 

[Student] Hur kommer du inte måste sätta ett et-tecken bredvid den del- Bra fråga. Hur kommer jag inte behövde sätta ett et-tecken bredvid tecknet array som jag gjorde tidigare med de flesta av våra exempel? Det korta svaret är arrayer är lite speciell. Du kan nästan tänka en buffert som faktiskt är en adress, och det bara så råkar vara så att den fyrkantiga fästet notation är en bekvämlighet så att vi kan gå in hållaren 0, fäste 1, fäste 2, utan att behöva använda * notation. Det är lite av en vit lögn eftersom arrayer och pekare är i själva verket lite annorlunda, men de kan ofta men inte alltid användas omväxlande. Kort sagt, när en funktion förväntar en pekare till en bit av minne, kan du antingen ge det en adress som returneras av malloc, och vi får se malloc igen snart, eller så kan du ge det namnet på en matris. Du behöver inte göra ampersand med arrayer eftersom de redan väsentligen liknande adresser. Det är det enda undantaget. Hakparenteserna gör dem speciella. 

Kan du sätta ett et-tecken bredvid bufferten? Inte i detta fall. Det skulle inte fungera eftersom, återigen, detta hörn fall där arrayer är inte riktigt faktiskt adresser. Men vi ska kanske återkomma till detta inom kort med andra exempel. Låt oss försöka att lösa ett problem här. Vi har en datastruktur som vi har använt under en tid känd som en matris. Ett typexempel, det är vad vi just haft. Men arrayer har några upsides och nackdelar. Arrayer är trevliga varför? Vad är en sak som du gillar, i den mån du vill arrayer-om arrayer? Vad är bekvämt om dem? Vad är övertygande? Varför har vi introducerar dem i första hand? Ja. [Student] De kan lagra mycket data, och du behöver inte använda en hel sak. Du kan använda ett avsnitt. Bra, med en rad kan du lagra mycket data, och du behöver inte nödvändigtvis använda alla det, så att du kan overallocate, vilket kan vara praktiskt om du inte vet i förväg hur många av något att förvänta sig. 

GetString är ett perfekt exempel. GetString, skriven av oss har ingen aning om hur många tecken att förvänta sig, så att vi kan fördela bitar av sammanhängande minne är bra. Arrayer löser också ett problem som vi såg för ett par veckor sedan nu där din kod börjar att överlåta till något mycket dåligt utformade. Minns att jag skapade en student struktur som kallas David, och sedan det var faktiskt ett alternativ, men att ha en variabel som heter namn och en annan variabel som heter, tror jag, hus, och en annan variabel som heter ID eftersom den historien jag sedan ville införa något annat gillar Rob i programmet, så då bestämde jag mig vänta en minut, Jag behöver byta namn på dessa variabler. Låt oss kalla min NAME1, ID1, House1. Låt oss kalla Rob namn2, house2, ID2. Men sedan vänta en minut, hur Tommy? Sedan hade vi tre variabler. Vi introducerade någon annan, fyra uppsättningar variabler. Världen började bli rörigt väldigt snabbt, så vi introducerade structs, och vad som är övertygande om en struct? Vad låter en C struct du göra? Det är verkligen pinsamt idag. Vad? >> [Ohörbart elev svar] Ja, speciellt kan typedef du skapa en ny datatyp, och struct, det struct sökord kan du kapsla konceptuellt relaterade delar av data tillsammans och därefter kalla dem något som liknar en elev. 

Det var bra eftersom vi nu kan modellera mycket mer sorts konceptuellt konsekvent begreppet elev i en variabel snarare än godtyckligt har en för en sträng, en för ett ID, och så vidare. Arrayer är bra eftersom de tillåter oss att börja städa upp vår kod. Men vad är en nackdel nu av en matris? Vad kan du göra det? Ja. [Student] Du måste veta hur stort det är. Du måste veta hur stort det är, så det är lite av en smärta. De av er med tidigare erfarenhet av programmering vet att i många språk, som Java, kan du be en bit av minne, speciellt en array, hur stor är du, med en längd, egendom, så att säga, och det är verkligen bekvämt. I C kan du inte heller ringa strlen på en generisk rad eftersom strlen, som ordet antyder, är endast för stråkar, och du kan räkna ut längden på en sträng på grund av denna mänskliga konvention att ha en \ 0, men en array, mer allmänt, är bara en bit av minne. Om det är en rad Ints, är det inte kommer att bli några specialtecken i slutet väntar på dig. Man måste komma ihåg längden på en array. En annan nackdel med en matris fötts huvudet i getString sig. Vad är en annan nackdel av en matris? Sir, bara du och jag idag. [Ohörbart elev svar] >> Det är vad? Det uttalade på stacken. Okej, förklarade på stacken. Varför inte du det? [Student] eftersom det blir återanvändas. Det blir återanvändas. Okej, om du använder en matris för att allokera minne, Du kan till exempel inte, returnera det eftersom det är på stacken. Okej, det är en nackdel. Och vad sägs om en annan med en rad? När du fördela det, du typ av skruvade om du behöver mer utrymme än matrisen har. 

Då vi infört, minns, malloc, som gav oss möjligheten att dynamiskt allokera minne. Men vad händer om vi försökte en annan värld helt och hållet? Tänk om vi ville lösa ett par av dessa problem så vi istället-min penna har somnat här- tänk om vi istället ville huvudsak skapa en värld som inte längre så här? Detta är en matris, och, naturligtvis, försämras denna typ av när vi träffar slutet av arrayen, och jag har nu inte längre har utrymme för en annan heltal eller ett annat tecken. Tänk om vi sorts förebyggande syfte säga bra, varför inte vi slappna detta krav att alla dessa bitar av minnet vara angränsande rygg mot rygg, och varför inte, när jag behöver en int eller en röding, bara ge mig utrymme för en av dem? Och när jag behöver en annan, ge mig ett annat rum, och när jag behöver en, ge mig ett annat rum. Fördelen med som nu att om någon annan tar minnet hit, no big deal. Jag tar denna ytterligare bit av minnet här och sedan här. 

Nu är den enda fångsten här att detta nästan känns som jag har en hel massa olika variabler. Detta känns som fem olika variabler potentiellt. Men tänk om vi stjäl en idé från strängar där vi kopplar på något sätt dessa saker tillsammans begreppsmässigt, och tänk om jag gjorde det? Detta är min mycket dåligt dragen pil. Men antag att alla dessa bitar av minnet pekade på andra, och den här killen, som inte har någon syskon till sin rätt, har ingen sådan pil. Detta är i själva verket vad som kallas en länkad lista. Detta är en ny datastruktur som tillåter oss att avsätta en bit av minne, sedan en annan, sedan en annan, sedan en annan, helst vill vi under ett program, och vi komma ihåg att de är alla på något sätt relaterade genom att bokstavligen kedja ihop dem, och vi gjorde det bildmässigt här med en pil. Men i kod, vad skulle vara den mekanism genom vilken du kan på något sätt ansluta, nästan som Scratch, en bit till en annan bit? Vi skulle kunna använda en pekare, eller hur? Eftersom verkligen pilen som kommer från den övre vänstra torget, den här killen här här, kan innehålla inuti denna kvadrat inte bara vissa Ints, inte bara några röding, men vad händer om jag faktiskt tilldelade lite extra utrymme så att nu, alla mina bitar av minnet, även om detta kommer att kosta mig, nu ser lite mer rektangulärt där en av bitarna av minne används för ett antal, som nummer 1, och sedan om den här killen lagrar numret 2, denna andra bit av minnet används för en pil, eller mer konkret, en pekare. Och jag antar att lagra numret 3 hit medan jag använder detta för att peka på att killen, och nu den här killen, låt oss anta att jag bara vill ha tre sådana bitar av minnet. Jag ska göra en linje genom att ange noll. Det finns ingen extra karaktär. 

I själva verket är det så att vi kan gå till väga för att genomföra något som kallas en länkad lista. En länkad lista är en ny datastruktur, och det är en språngbräda mot mycket snyggare datastrukturer som börjar att lösa problem i linje med Facebook-typ problem och Google-typ problem där du har stora datamängder, och det inte längre skär den att lagra allt intill varandra och använda något som linjär sökning eller ens något liknande binär sökning. Du vill ännu bättre gångtider. I själva verket en av de heliga Grails vi pratar om senare i veckan eller nästa är en algoritm vars speltid är konstant. Med andra ord tar det alltid samma tid oavsett hur stor ingången är, och det skulle verkligen vara övertygande, ännu mer än något logaritmisk. Vad är det här på skärmen här? Var och en av rektanglarna är precis vad jag drog för hand. Men det hela vägen till vänster är en speciell variabel. Det kommer att vara en enda pekare eftersom en gotcha med en länkad lista, eftersom dessa saker kallas, är att du måste hänga på en ände av den länkade listan. 

Precis som med en sträng, måste du veta adressen till den första röding. Samma affär för länkade listor. Du måste veta adressen till den första bit av minnet eftersom därifrån kan du nå alla andra. Nackdelen. Vilket pris betalar vi för denna mångsidighet av att ha en dynamisk betydande datastruktur som om vi någonsin behöver mer minne, fin, bara tilldela ett ytterligare stycke och dra en pekare från det gamla till det nya svansen på listan? Ja. [Student] Det tar ungefär dubbelt så mycket utrymme. Det tar dubbelt så mycket plats, så det är definitivt en nackdel, och vi har sett det här avvägning innan mellan tid och rum och flexibilitet där vid det här laget, vi behöver inte 32 bitar för var och en av dessa nummer. Vi behöver verkligen 64, 32 för antalet och 32 för pekaren. Men hey, jag har 2 gigabyte RAM-minne. Lägga till en annan 32 bitar här och här verkar inte som stor grej. Men för stora datamängder, lägger det definitivt till bokstavligen dubbelt så mycket. Vad är en annan nackdel nu, eller vad har vi ger upp, Om vi ​​representerar listor med saker med en länkad lista och inte en array? [Student] Du kan inte korsa den bakåt. Du kan inte korsa den bakåt, så du är typ av skruvade om du går från vänster till höger med en for-slinga eller en while-slinga och då inser du, "Åh, jag vill gå tillbaka till början av listan." Du kan inte eftersom dessa tips bara gå från vänster till höger som pilarna visar. 

Nu kan du komma ihåg början av listan med en annan variabel, men det är en komplicerad att tänka på. En array, oavsett hur långt du går, du kan alltid göra minus, minus, minus, minus och gå tillbaka varifrån du kom. Vad är en nackdel här? Ja. [Ohörbart elev fråga] Du kan, så du har faktiskt just föreslagit en datastruktur som kallas en dubbelt länkad lista, och faktiskt, skulle du lägga till ytterligare pekare till var och en av dessa rektanglar som går åt andra hållet, uppsidan som Nu kan du färdas fram och tillbaka, Nackdelen som nu du använder tre gånger så mycket minne som vi brukade och även lägga komplexitet när det gäller den kod du måste skriva för att få det rätt. Men dessa är alla kanske mycket rimliga kompromisser, om återföring är viktigare. Ja. [Student] Du kan inte heller ha en 2D länkad lista. Bra, kan man inte riktigt har en 2D länkad lista. Du kunde. Det är inte alls lika lätt som en matris. Som en array, du öppna konsolen, stängd fäste, öppen hållare, stängda hållare, och du får några 2-dimensionell struktur. Man kan genomföra en 2-dimensionell länkad lista om du gör tillägg som du föreslog-tredjedel pekare till var och en av dessa saker, och om du tänker på en annan lista kommer på dig 3D stil från skärmen för oss alla, vilket är bara en annan kedja av något slag. Vi kan göra det, men det är inte så enkelt som att skriva öppet fäste, hakparentes. Ja. [Ohörbart elev fråga] Bra, så detta är en riktig kicker. 

Dessa algoritmer som vi har pined över, liksom oh, binär sökning, kan du söka en rad siffror på tavlan eller en telefonbok så mycket snabbare om du använder söndra och härska och en binär sökalgoritm, men binärsökning krävs två antaganden. Ett, att uppgifterna sorterades. Nu kan vi hålla förmodligen detta sorteras, så kanske det inte är ett problem, men binär sökning förutsätts också att du hade direktåtkomst till listan över nummer, och en rad låter dig ha direktåtkomst och genom direktåtkomst, Jag menar om du är ges en rad, hur lång tid det tar dig för att komma till konsolen 0? En operation, du bara använda [0] och du har rätt där. Hur många steg tar det att komma till platsen 10? Ett steg går du bara till [10] och du är där. Däremot, hur du kommer till den 10: e heltal i en länkad lista? Du måste börja från början eftersom du bara komma ihåg början på en länkad lista, precis som en sträng bli ihågkommen av adressen dess första röding, och upptäcker att 10:e int eller att 10. tecken i en sträng, måste du söka i hela jävla sak. 

Återigen, vi löser inte alla våra problem. Vi inför nya, men det är beroende på vad du försöker att designa för. När det gäller genomförandet av detta kan vi låna en idé från den studerandes struktur. Syntaxen är mycket likt, förutom nu är tanken lite mer abstrakt än hus och namn och ID. Men jag föreslår att vi skulle kunna ha en datastruktur i C som kallas nod, som sista ordet på bilden antyder, inne i en nod och en nod är bara en generisk behållare i datavetenskap. Det är oftast ritas som en cirkel eller en kvadrat eller rektangel som vi har gjort. Och i denna datastruktur har vi en int, n, så det är numret jag vill lagra. Men vad är detta andra raden, struct nod * nästa? Varför är detta korrekt, eller vilken roll gör det här spelet, även om det är lite kryptisk vid första anblicken? Ja. [Ohörbart elev svar] Exakt, så * slags byte att det är en pekare av något slag. Namnet på denna pekare är godtyckligt nästa, men vi kunde ha kallat det något vi vill ha, men vad har detta pekare pekar på? [Student] En annan nod. >> Exakt, pekar den på en annan sådan nod. 

Nu är denna typ av en nyfikenhet av C. Minns att C läses av en kompilator uppifrån och ned, vänster till höger, vilket innebär att om-detta är lite annorlunda från vad vi gjorde med den studerande. När vi definierat en student, vi faktiskt inte lagt ett ord där. Det sa bara typedef. Sedan hade vi int id, string namn, string hus, och därefter student vid botten av struct. Denna förklaring är lite annorlunda eftersom, återigen är C-kompilator lite dum. Det är bara att gå att läsa uppifrån och ned, så om det når 2nd line här där nästa deklareras och det ser, oh, här är en variabel som heter nästa. Det är en pekare till en struct nod. Kompilatorn kommer att inse vad som är en struct nod? Jag har aldrig hört talas om denna sak innan, eftersom ordet nod inte annars visas tills botten, så det är denna redundans. Du måste säga struct nod här, som du sedan kan förkorta senare tack vare typedef här nere, men det beror Vi refererar till själva strukturen inuti strukturen. Det är en gotcha där. 

Några intressanta problem kommer att uppstå. Vi har en lista med tal. Hur sätter vi in ​​det? Hur söker vi det? Hur tar vi av det? Speciellt nu när vi har att hantera alla dessa tips. Du trodde pekare var typ av kluriga när du hade en av dem försöker bara läsa en int till det. Nu måste vi manipulera en hel lista är värt. Varför tar vi inte vårt 5-minuters paus här, och sedan kommer vi att Vissa folk upp på scenen för att göra just detta. 

C är mycket roligare när det är agerade ut. Vem skulle bokstavligen vilja vara först? Okej, kom upp. Du är först. Vem vill vara 9? Okej, 9. Vad sägs om 9? 17? Lite klicken här. 22 och 26 i den främre raden. Och sedan hur om någon där borta som pekade på. Du är 34. Okej, 34, kom upp. Först är borta. Okej, alla fyra av er. Och vem har vi säga 9? Vem är vår 9? Vem vill egentligen bli 9? Okej, kom igen, vara 9. Nu kör vi. 34, vi träffas där. Den första delen är att göra er ser ut så. 26, 22, 17, bra. Om du kan stå åt sidan, eftersom vi kommer att minnesallokera dig om en stund. 

Bra, bra. Okej, utmärkt, så låt oss ställa ett par frågor här. Och faktiskt, vad heter du? >> Anita. Anita, okej, kom hit. Anita kommer att hjälpa oss slags lösa ett ganska enkel fråga i första, vilket är hur du hittar om en värde i listan? Nu märker att först representeras här av Lucas, är lite annorlunda, och så hans papper är medvetet sidled eftersom det inte är riktigt lika lång och tar inte upp så många bitar, även om tekniskt han har samma pappersformat bara roteras. Men han är lite annorlunda eftersom han är bara 32 bitar för en pekare, och alla dessa killar är 64 bitar, varav hälften är antalet, varav hälften är en pekare. Men pekaren inte visas, så om ni kunde något tafatt använda din vänstra hand för att peka på personen bredvid dig. Och du är nummer 34. Vad heter du? Ari. Ari, så egentligen håller papperet i höger hand och vänster hand går rakt ner. Du representerar null till vänster. 

Nu vår mänskliga bilden är mycket konsekvent. Detta är faktiskt hur pekare fungerar. Och om du kan krama lite här sättet så jag är inte i vägen. Anita här, hitta mig numret 22, men antar en begränsning av att inte människor håller upp bitar av papper, men detta är en lista, och du har bara Lucas att börja med eftersom han är bokstavligen den första pekaren. Anta att du själv är en pekare, och så du också har möjlighet att peka på något. Varför inte du börja med att peka på exakt vad Lucas pekar på? Bra, och låt mig att göra den här ut över här. Bara för diskussionens skull, låt mig dra upp en tom sida här. Hur stavar du ditt namn? >> Anita. Okej, Anita. Låt oss säga nod * anita = Lucas. Tja, ska vi kalla dig inte Lucas. Vi borde ringa dig först. Varför är det i själva verket överensstämmer med verkligheten här? En första redan existerar. Först har tilldelats förmodligen någonstans här uppe. Nod * först, och det har tilldelats en lista på något sätt. Jag vet inte hur det hände. Det hände innan klassen började. Denna länkade lista av människor har skapats. Och nu vid denna punkt i berättelsen, det är allt som händer Facebook tydligen senare vid denna punkt i berättelsen, har Anita initierats vara lika med första, vilket inte betyder att Anita pekar på Lucas. Snarare pekar hon på vad han pekar på eftersom samma adress som är inne i Lucas 32 bitar - 1, 2, 3 - är nu också inne i Anitas 32 bitar - 1, 2, 3. 

Nu hitta 22. Hur skulle du gå om att göra detta? Vad är det? >> Peka på vad som helst. Peka på vad som helst, så gå vidare och agera ut det så gott du kan här. Bra, bra, och nu är du pekar på, vad heter du med 22? Ramon. >> Ramon, så Ramon håller upp 22. Du har nu gjort en check. Har Ramon == 22, och i så fall till exempel kan vi återvända sant. Låt mig-när dessa killar står här något tafatt- Låt mig göra något snabbt som bool hitta. Jag ska gå vidare och säga (nod * lista, int n). Jag kommer strax tillbaka med er. Jag måste bara skriva lite kod. Och nu ska jag gå vidare och göra det nod * anita = lista. Och jag kommer att gå vidare och säga medan (Anita! = Null). 

Metaforen här blir lite utsträckt, men medan (Anita! = Null), vad jag vill göra? Jag behöver något sätt referera heltalet som Anita pekar på. I det förflutna, när vi hade strukturer som en nod är, Vi använde punktnotation, och vi skulle säga något i stil med anita.n, men problemet här är att Anita är inte en struktur i sig. Vad är hon? Hon är en pekare, så egentligen, om vi vill använda denna punktnotation- och detta kommer att se medvetet lite kryptiskt- vi måste göra något liknande gå till valfri Anitas vänstra hand pekar på och sedan få fältet kallas n. Anita är en pekare, men vad är * Anita? Vad tycker du när du går till vad Anita pekar på? En struct, en nod och en nod, återkallande, har ett fält som heter N eftersom det har, minns dessa 2 områden, Nästa och n, att vi såg för en stund sedan här. 

För att verkligen efterlikna detta i kod, vi kunde göra detta och säga om ((* anita). n == n), n som jag letar efter. Observera att funktionen antogs i antalet jag bryr mig om. Då kan jag gå vidare och göra något liknande avkastning sant. Annars, om det inte är fallet, vad jag vill göra? Hur översätter jag att koda vad Anita gjorde så intuitivt genom att gå igenom listan? Vad ska jag göra här uppe för att simulera Anita ta det steget till vänster, som steg till vänster? [Ohörbart elev svar] >> Vad är det? [Ohörbart elev svar] Bra, inte en dålig idé, men i det förflutna, när vi har gjort detta, har vi gjort anita + + eftersom det skulle lägga till numret 1 till Anita, som normalt skulle peka på nästa person, som Ramon, eller den person bredvid honom, eller bredvid honom personen ner linjen. Men det är inte riktigt bra här eftersom vad den här saken ser ut i minnet? Inte det. Vi måste inaktivera det. Det ser ut så här i minnet, och även om jag har ritat 1 och 2 och 3 nära varandra, om vi verkligen simulera detta-Kan ni, samtidigt pekar på samma människor, kan några av er tar en slumpmässig steg tillbaka, vissa av er en slumpmässig steg framåt? 

Denna röran är fortfarande en länkad lista, men dessa killar kunde vara var som helst i minnet, så anita + + inte kommer att fungera varför? Vad är på plats anita + +? Vem vet. Det är något annat värde som bara så råkar vara placerad bland alla dessa noder av en slump eftersom vi inte använder en matris. Vi tilldelades en av dessa noder individuellt. Okej, om ni kan rensa er tillbaka. Låt mig föreslå att istället för anita + +, vi istället gör anita får- Tja, varför inte vi gå till vad Anita pekar på och sedan göra. härnäst? Med andra ord går vi till Ramon, vem håller numret 22, och då. nästa är som om Anita skulle kopiera sin vänstra hand pekare. Men hon skulle inte gå längre än Ramon eftersom vi hittade 22. Men det skulle vara idén. Nu är detta en god-awful röra. Ärligt talat, ingen kommer ihåg någonsin här syntaxen, och så tack och lov, Det är faktiskt lite medvetet-Åh, har du faktiskt inte se vad jag skrev. Detta skulle vara mer övertygande om du kunde. Voila! 

Bakom kulisserna, jag lösa problemet på detta sätt. Anita, att ta detta steg till vänster, Först går vi till den adress som Anita pekar på och där hon kommer att hitta inte bara n, som vi bara kontrolleras för jämförelse skull, men du hittar också nästa - i detta fall, Ramons vänstra hand pekar till nästa nod i listan. Men detta är den god-awful röra som jag hänvisade till tidigare, men det visar sig C låter oss förenkla detta. Istället för att skriva (* anita), kan vi istället bara skriva anita-> n, och det är exakt samma sak funktionellt, men det är mycket mer intuitivt, och det är mycket mer överens med den bild som vi har ritning all denna tid med pilar. 

Slutligen, vad vi behöver göra i slutet av detta program? Det finns en rad kod kvar. Återgå vad? Falskt, för om vi får igenom hela while-slingan och Anita är i själva verket noll betyder att hon gick hela vägen till slutet av listan där hon pekar på, vad heter du nu igen? Ari. >> Aris vänster hand, vilket är null. Anita är nu noll, och jag inser du bara står här tafatt i limbo eftersom jag ska iväg på en monolog här, men vi engagera dig igen på bara ett ögonblick. Anita är noll vid denna punkt i berättelsen, så while-slingan avslutas, och vi måste returnera false för om hon fick hela vägen till Aris null-pekare då fanns det ingen nummer som hon sökte i listan. Vi kan städa upp det här också, men det är en ganska bra genomförande sedan en traversering funktion en sökning funktion för en länkad lista. Det är fortfarande linjär sökning, men det är inte så enkelt som + + en pekare eller + + en i variabel för nu kan vi inte gissa där var och en av dessa noder är i minnet. Vi måste bokstavligen följa spår av brödsmulor eller, mer specifikt, pekare, att ta sig från en nod till en annan. 

Nu ska vi prova en annan. Anita, vill du komma tillbaka hit? Varför inte vi gå vidare och fördela en annan person från publiken? Malloc-vad heter du? >> Rebecca. Rebecca. Rebecca har malloced från publiken, och hon nu lagra antalet 55. Och målet till hands är nu Anita att infoga Rebecca in den länkade listan här i sitt rätta ställe. Kom hit för en stund. Jag har gjort något liknande. Jag har gjort nod *. Och vad heter du nu igen? Rebecca. >> Rebecca, okej. Rebecca får malloc (sizeof (nod)). Precis som vi har tilldelats saker som studenter och allt i det förflutna, Vi behöver storleken på noden, så nu Rebecca pekar på vad? Rebecca har två fält inuti henne, varav en är 55. Låt oss göra vad, rebecca-> = 55. Men sedan rebecca-> nästa bör-liknande just nu, är hennes hand slags vem vet? Det pekar på några sopor värde, så varför inte för bra åtgärd vi åtminstone gör detta så att vänster hand är nu vid hennes sida. Nu Anita, ta det härifrån. Du har Rebecca har tilldelats. Gå vidare och hitta där vi ska lägga Rebecca. Bra, mycket bra. Okej, bra, och nu behöver vi dig att lämna lite riktning, så du har nått Ari. Hans vänstra arm är null, men Rebecca klart tillhör höger, så hur har vi att ändra detta länkad lista För att sätta Rebecca i lämpligt ställe? Om du kunde bokstavligen flytta folks vänster hand runt efter behov, vi åtgärda problemet på det sättet. Okej, bra, och under tiden är Rebecca vänstra hand nu vid hennes sida. 

Det var för lätt. Låt oss försöka fördela-Vi nästan klar, 20. Okej, kom upp. 20 har tilldelats, så låt mig gå vidare och säga igen här Vi har precis gjort Saad nod *. Vi har malloc (sizeof (nod)). Vi gör då exakt samma syntax som vi gjorde tidigare under 20, och jag ska göra härnäst = NULL, och nu är det upp till Anita att infoga dig i den länkade listan, om du kunde spela exakt samma roll. Utför. Okej, bra. Nu tänker noga innan du börjar flytta vänster hand runt. Du särklass fick mest obekväma rollen idag. Vems handen bör flyttas 1:a? Okej, vänta, jag hör lite nej-talet. Om vissa människor skulle artigt vilja hjälpa till att lösa en besvärlig situation här. Vems vänster bör uppdateras 1. Kanske? Ja. [Student] Saad s. Okej, Saad-talet, varför då? [Ohörbart elev svar] Bra, för om vi flyttar-Vad heter du? >> Marshall. Marshall, om vi flyttar sin hand först ner till noll, nu har vi bokstavligen föräldralösa fyra personer i den här listan eftersom han var den enda som pekar på Ramon och alla till vänster, så uppdaterar att pekaren första var dåligt. Låt oss ångra det. Bra, och nu gå vidare och flytta lämpliga vänstra pekar på Ramon. Detta känns lite överflödigt. Nu finns det två personer som pekar på Ramon, men det är bra för nu hur annars ska uppdaterar vi listan? Vilka andra sidan måste flytta? Utmärkt, nu har vi förlorat något minne? Nej, så bra, låt oss se om vi inte kan bryta denna gång. 

Mallocing en sista gång, nummer 5. Hela vägen i ryggen, kom ner. Det är väldigt spännande. [Applåder] Vad heter du? >> Ron. Ron, okej, du malloced som nummer 5. Vi har precis avrättades kod som är nästan identiska med dem med bara ett annat namn. Utmärkt. Nu, Anita, lycka sätta nummer 5 i listan nu. Bra, och? Utmärkt, så detta är verkligen den tredje av tre totalt fall. Först hade vi någon på slutet, Rebecca. Vi hade sedan någon i mitten. Nu har vi någon början, och i detta exempel, Vi hade nu för att uppdatera Lucas för första gången eftersom det första elementet i listan nu att peka på en ny nod, som, i sin tur, pekar på nodnummer 9. 

Detta var en enormt pinsamt demonstration, jag är säker, så en stor applåd för dessa killar om du kunde. Snyggt gjort. Det är allt. Du kan hålla dina lappar som en liten minne. Det visar sig att göra detta i kod är inte riktigt så enkelt som att bara flytta händerna runt och pekar pekare på olika saker. Men inser att när det blir dags att genomföra något liknande en länkad lista eller en variant av det om du fokuserar på riktigt dessa grundläggande fundamenta, de lagom stora problem jag har att räkna ut, Det är denna hand eller denna hand, inse att det är annars ett ganska komplext program kan i själva verket reduceras till ganska enkla byggstenar som denna. 

Låt oss ta det i en mer sofistikerad riktning fortfarande. Vi har nu begreppet den länkade listan. Vi har också-tack vare förslaget tillbaka dit-en dubbelt länkad lista, som ser nästan samma, men nu har vi två pekare inuti struct istället för en, och vi skulle förmodligen kalla dem pekare föregående och nästa eller till vänster eller höger, men vi i själva verket behöver två av dem. Koden skulle vara lite mer delaktiga. Anita skulle ha haft att göra mer arbete här på scenen. Men vi kan säkert genomföra denna typ av struktur. När det gäller körtid, men vad skulle vara gångtid för Anita att hitta ett nummer n i en länkad lista nu? Fortfarande stora O n, så det är inte bättre än linjär sökning. Vi kan inte göra binär sökning, men, igen. Varför var det så? Du kan inte hoppa runt. Även om vi ser naturligtvis alla människor på scenen, och Anita kunde ha eyeballed det och sade: "Här är mitt listan" Hon skulle inte veta att om hon var datorprogrammet eftersom det enda hon hade att haka på i början av scenariot var Lucas, som var den första pekaren. Hon skulle med nödvändighet måste följa dessa länkar, räkna sig fram tills hon hittade ungefär mitten, och även då, hon kommer inte att veta när hon nått mitten om hon inte går hela vägen till slutet för att räkna ut hur många det finns, sedan Backtracks, och det också skulle vara svårt om du inte hade en dubbelt länkad lista av något slag. 

Lösa problem i dag, men inför andra. Vad sägs om en annorlunda datastruktur helt och hållet? Detta är ett fotografi av brickorna i Mather House, och i detta fall har vi en datastruktur vi också typ av redan pratat om. Vi pratade om en stack i samband med minnet, och det är typ av avsiktligt namn eftersom en stapel i termer av minne är effektivt en datastruktur som har mer och mer saker skiktades ovanpå den. Men det intressanta med en stapel, såsom är fallet i verkligheten, är att det är en speciell typ av datastruktur. Det är en datastruktur där det första elementet i är det sista elementet ut. Om du är den första brickan sättas på stacken, du kommer att bli tyvärr den sista brickan tas bort bunten, och det är inte nödvändigtvis en bra sak. Omvänt kan man tänka på det tvärtom, den sista i den första ut. 

Nu behöver alla scenarier kommer att tänka där med en bunt datastruktur där du har den egenskapen den sista in, först ut, är faktiskt övertygande? Är det bra? Är det en dålig sak? Det är definitivt en dålig sak om magasinen var inte alla identiska och de var alla särskilda färger eller whatnot, och den färg du vill ha hela vägen längst ner. Naturligtvis kan du inte få det utan stor ansträngning. Du måste börja från toppen och arbeta dig nedåt. Likaså, vad händer om du var en av dessa fläkt pojkar som väntar uppe hela natten att försöka få en iPhone och linjer upp på en plats som denna? Skulle det inte vara trevligt om Apple Store var en stapel datastruktur? Yay? Nej? Det är bara bra för de människor som dyker upp i sista möjliga minuten och sedan få plockas bort kön. Och i själva verket på att jag var så benägen att säga kö är faktiskt överens med vad vi skulle kalla den här typen av datastruktur, en i verkligheten där ordern spelar roll, och du vill att den första i att vara först ut om så bara för sakens skull mänskliga rättvisa. Vi kommer i allmänhet kalla det en kö datastruktur. 

Det visar sig dessutom länkade listor, kan vi börja använda samma grundläggande idéer och börja skapa nya och olika typer av lösningar på problem. Till exempel, i fallet med en stapel, kan vi representera en stapel med hjälp av en datastruktur som denna, skulle jag föreslå. I det här fallet har jag deklarerat en struktur, och jag har sagt inuti denna struktur är en matris med tal, och sedan en variabel som kallas storlek, och jag kommer att kalla denna sak en skorsten. Nu, varför det fungerar egentligen? I fallet med en stapel, kan jag dra detta effektivt på skärmen som en matris. Här är min stack. De är mina nummer. Och vi kommer att dra dem som denna, det, detta, detta, detta. Och så har jag några andra uppgifter medlem här, som kallas storlek, så detta är storleken, och det är tal, och kollektivt representerar hela IPAD här en stack struktur. Nu, som standard, har storlek fick förmodligen att initieras till 0, och vad är inne i matris med tal initialt när jag först tilldela en array? Garbage. Vem vet? Och det spelar ingen roll egentligen. Det spelar ingen roll om det är 1, 2, 3, 4, 5, helt slumpmässigt av otur som lagras i min struktur eftersom så länge jag vet att storleken på stacken är 0, då vet jag programmatiskt, ser inte på någon av elementen i arrayen. Det spelar ingen roll vad som finns där. Titta inte på dem, vilket skulle vara innebörden av en storlek på 0. 

Men antar jag nu gå vidare och sätta något i stacken. Jag vill infoga numret 5, så jag satte nummer 5 här, och vad lägger jag här nere? Nu skulle jag faktiskt lägga ner 1 för storlek, och nu bunten är storlek 1. Vad händer om jag går vidare och för in numret, låt oss säga, 7 nästa? Detta sedan blir uppdaterad till 2, och då ska vi göra 9, och då detta blir uppdaterad till 3. Men det intressanta inslag nu av denna stack är att Jag ska ta bort vilket element om jag vill pop något från av stapeln, så att säga? 9 skulle vara det första att gå. Hur ska bilden förändras om jag vill att pop ett element från stacken, ungefär som en bricka i Mather? Ja. >> [Student] Ställ in storlek på 2. Exakt, allt jag gör satt storlek till 2, och vad ska jag göra med kedjan? Jag behöver inte göra någonting. Jag skulle bara vara anal, sätta en 0 där eller en -1 eller något att betyda att detta inte är en legit värde, men det spelar ingen roll eftersom Jag kan spela utanför uppsättningen själv hur lång tid det är så att jag vet bara titta på de första två delarna i denna array. Nu, om jag går och lägger numret 8 till denna array, hur bilden förändras nästa? Detta blir 8, och detta blir 3. Jag skär några hörn här. Nu har vi 5, 7, 8, och vi är tillbaka till en storlek på 3. Detta är ganska enkelt att implementera, men när kommer vi att ångra denna design beslut? När börjar saker att gå mycket, mycket fel? Ja. [Ohörbart elev svar] När du vill gå tillbaka och få det första elementet du lägger i. 

Det visar sig här även om en stapel är en matris under huven, dessa datastrukturer vi har börjat prata om är också allmänt känd som abstrakta datastrukturer där hur de genomförs är helt förutom punkten. En datastruktur som en stapel är tänkt att ge stöd operationer som tryck, som driver en bricka på stacken, och pop, som tar bort ett element från stacken, och det är det. Om du skulle hämta någon annans kod som redan genomförts denna sak kallad en skorsten, skulle den personen ha skrivit endast två funktioner för dig, tryck och pop, vars enda syfte i livet skulle vara att göra just det. Du eller honom eller henne som genomförts programmet skulle ha varit helt och hållet en att bestämma hur man ska genomföra semantiken för att trycka och poppar under huven eller funktionalitet trycka och popping. Och jag har gjort en något kortsiktig beslut här genom att genomföra min stack med denna enkla datastruktur varför? När gör detta datastruktur rast? Vid vilken punkt har jag returnera ett fel när användaren anropar push, till exempel? [Student] Om det inte finns någon mer plats. Exakt, om det inte finns mer utrymme, om jag har överskridit kapaciteten, vilket är versaler eftersom det antyder att det är någon form av global konstant. Nåväl, då jag ska bara säga, "Tyvärr, jag kan inte skjuta ett annat värde på stacken, "ungefär som i Mather. 

Vid något tillfälle, kommer de att träffa den övre delen av den lilla skåp. Det finns ingen mer plats eller kapacitet i högen, då det finns någon typ av fel. De måste sätta elementet någon annanstans, facket någon annanstans, eller ingenstans alls. Nu, med en kö kan vi genomföra det lite annorlunda. En kö är lite annorlunda eftersom under huven, kan det genomföras som en array, men varför i detta fall föreslår jag också ha ett huvudelement representerar huvudet av listan, framsidan av listan, den första personen i raden på Apple Store, förutom storlek? Varför behöver jag en extra bit data här? Tänk tillbaka till vad siffrorna är om jag har ritat det följande. Antar att detta är nu en kö i stället för en stack, Skillnaden är, precis som Apple Store-kö är rättvis. Den första personen i raden i början av listan, nummer 5 i detta fall, han eller hon kommer att släppa in i butiken först. Låt oss göra det. Antag att det är det land i min kö på denna tidpunkt, och nu Apple Store öppnas och den första personen, nummer 5, leds in i butiken. Hur ändrar jag bilden nu när jag har mins-kö den första personen på framsidan av linjen? Vad är det? >> [Student] Ändra kön. Ändra huvudet, så 5 försvinner. I verkligheten är det som om-hur man bäst gör detta? I verkligheten är det som om den här killen försvinner. Vad skulle nummer 7 gör i en verklig butik? De skulle ta ett stort steg framåt. 

Men vad har vi kommit att uppskatta när det kommer till arrayer och flytta runt saker? Det är typ av ett slöseri med din tid, eller hur? Varför måste man vara så anal att ha den första personen i början av raden vid fysiskt i början av bit av minnet? Det är helt onödigt. Varför? Vad kan jag bara komma ihåg istället? >> [Ohörbart elev svar] Exakt, kunde jag minnas bara med mer data ledamot huvud att nu chefen för listan är inte längre 0, som det var för en stund sedan. Nu är det faktiskt nummer 1. På så sätt får jag en liten optimering. Bara för att jag har mins-kö någon från ledningen i början av raden på Apple Store betyder inte att alla måste flytta, vilket minns är en linjär operation. Jag kan istället ägna konstant tid endast och uppnå sedan en mycket snabbare respons. Men priset jag betalar är vad för att få det extra prestanda och inte behöva flytta alla? Ja. >> [Ohörbart elev svar] Kan lägga till fler människor, ja, är det problemet ortogonal det faktum att vi inte flytta människor runt. Det är fortfarande en array, så om vi flytta alla eller inte- åh, jag ser vad du menar, okej. Egentligen håller jag med vad du säger att det är nästan som om Vi bevakar nu aldrig kommer att använda i början av arrayen längre för om jag tar bort 5, då jag bort 7. Men jag satte bara folk till höger. 

Det känns som om jag slösa utrymme, och så småningom min kö sönderfaller till ingenting alls, så vi kunde bara få folk wraparound, och vi kunde tänka på denna array verkligen som något slags cirkulär struktur, men vi använder det operatör i C för att göra den sortens wraparound? [Ohörbart elev svar] >> operatorn modulo. Det skulle vara lite irriterande att tänka igenom hur du gör wraparound, men vi kan göra det, och vi kunde börja sätta människor i vad som brukade vara på framsidan av linjen, men vi minns bara med detta huvud variabel som själva huvudet av raden egentligen är. Tänk om, istället vårt mål till slut, men var att slå upp nummer, som vi gjorde här på scenen med Anita, men vi vill verkligen bäst av alla dessa världar? Vi vill ha mer sofistikerade än matris tillåter eftersom vi vill ha möjlighet att dynamiskt öka datastrukturen. Men vi vill inte ta till något som vi påpekade i den första föreläsningen var inte en optimal algoritm, som linjär sökning. Det visar sig att man kan i själva verket få eller åtminstone nära konstant tid, där någon som Anita, om hon konfigurerar sin datastruktur inte vara en länkad lista, inte vara en stapel, att inte vara en kö, skulle i själva verket, komma med en datastruktur som tillåter henne att se upp saker, även ord, inte bara siffror, i vad vi kallar konstant tid. 

Och i själva verket ser framåt, är en av de psets i denna klass nästan alltid en implementation av en stavningskontroll, där Vi ger dig igen några 150.000 engelska ord och målet är att ladda dem i minnet och snabbt kunna svara på frågor i formuläret detta ord rättstavat? Och det skulle verkligen suga om du var tvungen att iterera igenom alla 150.000 ord att besvara den. Men i själva verket kommer vi se att vi kan göra det på mycket, mycket snabb tid. Och det kommer att innebära att genomföra något som kallas en hash-tabell, och även om vid första anblicken denna sak kallas en hash-tabell ska Låt oss uppnå dessa super snabba svarstider, Det visar sig att det i själva verket ett problem. När det blir dags att genomföra denna sak kallad-igen, jag gör det igen. Jag är den enda här. När det blir dags att genomföra denna sak kallad en hash-tabell, vi kommer att behöva fatta ett beslut. Hur stor bör denna sak vara egentligen? Och när vi börjar infoga siffror i denna hash tabell, Hur ska vi förvara dem på ett sådant sätt att vi kan få dem tillbaka så fort som vi fick dem? Men vi får se snart att denna fråga om när alla fyller år i klassen kommer att vara ganska relevant. Det visar sig att i detta rum har vi ett par hundra personer, så oddsen att två av oss har samma födelsedag är förmodligen ganska hög. Tänk om det fanns bara 40 av oss i det här rummet? Vad är oddsen för två personer med samma födelsedag? [Studenter] Över 50%. Ja, mer än 50%. I själva verket tog jag även ett diagram. Det visar sig, och detta är egentligen bara en förhandstitt, om det finns bara 58 av oss i detta rum, är sannolikheten för 2 av oss med samma födelsedag är enormt hög, nästan 100%, och det kommer att orsaka en hel del skada för oss på onsdag. 

Med det sagt, låt oss ajournera här. Vi ses på onsdag. [Applåder] [CS50.TV]