[Powered by Google Translate] [Avsnitt 6] [Mer Bekväm] [Rob Bowden] [Harvard University] [Detta är CS50.] [CS50.TV] 

Vi kan gå till vår sektion med frågor. Jag skickade URL för utrymmet innan. Början av den del av frågorna säga- tydligen är jag inte helt unsick-är en mycket enkel fråga om precis vad som valgrind? Vad gör Valgrind? Någon som vill säga vad Valgrind gör? [Student] Kontroller minnesläckor. Ja, det är Valgrind en allmän minne bricka. Det, i slutändan, säger om du har några minnesläckor, som oftast vad vi använder det för att om du vill göra bra i problemet apparaten eller om du vill få på den stora styrelsen, måste du ha någon minnesläckor som helst, och om du har en minnesläcka som du inte kan hitta, också ihåg att när du öppnar en fil och om du inte stänga den, det är en minnesläcka. 

Många människor söker efter någon nod som de inte befria när det verkligen, de stänger inte i ordlistan i det allra första steget. Den berättar också om du har några ogiltiga läser eller skriver, vilket innebär att om du försöker och ange ett värde det är bortom slutet på högen, och det händer inte på seg fel men Valgrind fångar den, eftersom du egentligen inte borde skriva det, och så du definitivt inte ha någon av dem heller. Hur använder du valgrind? Hur använder du valgrind? 

Det är en allmän fråga om typ av kör det och titta på utgången. Utgången är överväldigande många gånger. Det finns också roliga fel där om du har några fruktansvärt fel sak händer i en slinga, så kommer det så småningom att säga, "Sätt för många fel. Jag ska sluta räkna nu. " Det är i princip textuell utgång som du har att tolka. I slutändan kommer det att berätta någon minnesläckor som du har, hur många block, som kan vara användbart eftersom om det är ett kvarter unfreed, då är det oftast lättare att hitta än 1.000 block unfreed. 1.000 block unfreed betyder förmodligen att du inte frigöra dina länkade listor lämpligt sätt eller något. Det är valgrind. 

Nu har vi vår del av frågor, som du inte behöver ladda ner. Du kan klicka på mitt namn och dra upp dem i rymden. Klicka nu på mig. Revidering 1 blir stack, som vi gör först. Revision 2 kommer att vara kö, och Revision 3 kommer att vara den enskilt länkade listan. Det började med vår stack. Som det står här, är en bunt en av de mest grundläggande, grundläggande datastrukturer datavetenskap. Den mycket prototypiska exemplet är bunten av brickor i matsalen. Det är i grunden när du håller på att introduceras till en skorsten, någon kommer att säga, "Åh, som en stapel av brickor." Du stapla brickorna upp. Sen när du går att dra en bricka, det första facket som är få dras är den sista som sattes på stacken. Bunten också, som det står här- vi har segmentet av minnet kallas stapeln. Och varför kallas det stapeln? 

Eftersom som en stack datastruktur, den pressar och poppar stack ramar på stacken, där stack ramar är som en särskild inbjudan av en funktion. Och som en stapel, kommer du alltid att återvända från ett funktionsanrop innan du kan komma ner till lägre stack ramar igen. Du kan inte ha stora samtal foo samtal bar och bar tillbaka till huvud direkt. Det har alltid fått följa rätt stacken trycka och popping. De två operationer, som jag sa, är push och pop. De är universella termer. Du bör känna till tryck och pop i form av staplar oavsett vad. Vi får se köer är typ av olika. Det har egentligen en universell term, men push och pop är universella för stackar. Push är bara sätta på stacken. Pop är ta av stapeln. Och vi ser här har vi vår typedef struct stack, så vi har röding ** strängar. Bli inte rädd av några **. Detta kommer att hamna en array med strängar eller en uppsättning pekare till tecken, där pekare till tecken tenderar att vara strängar. Det behöver inte vara strängar, men här kommer de att bli strängar. 

Vi har en array med strängar. Vi har en storlek, som representerar hur många element är närvarande på stacken, och då vi har kapacitet, vilket är hur många element kan vara på stacken. Kapaciteten ska börja som något större än 1, men storleken kommer att börja som 0. Nu finns det i princip tre olika sätt du kan tänka dig en bunt. Nåväl, det finns förmodligen fler, men de två huvudsakliga sätt är du kan genomföra den med en array, eller så kan du genomföra det med hjälp av en länkad lista. Länkade listor är typ av trivialt att göra travar från. Det är mycket lätt att göra en stapel med länkade listor, så här ska vi göra en stack med arrayer, och sedan använda arrayer, det finns också två sätt du kan tänka på det. Förut när jag sa att vi har en kapacitet för stacken, så att vi kan anpassa ett element på stacken. 

Det enda sättet det kan ske är när du träffar 10 element, då du är klar. Du kanske vet att det finns en övre gräns på 10 saker i världen att du aldrig kommer att ha mer än 10 saker på din stack, i vilket fall du kan ha en övre gräns på storleken på din stack. Eller du kan ha din stack vara obegränsad, men om du gör en array, innebär att varje gång du träffar 10 element, då du kommer att behöva växa till 20 element, och när du träffar 20 element, du kommer att behöva öka din array för att 30 element eller 40 element. Du kommer att behöva öka kapaciteten, vilket är vad vi ska göra här. Varje enskild tid vi når den maximala storleken på vår stack, När vi trycker något annat på, vi kommer att behöva öka kapaciteten. Här har vi förklarat tryck som bool tryck (char * str). Char * str är strängen som vi driver på stacken, och bool säger bara om vi lyckades eller misslyckades. 

Hur kan vi misslyckas? Vad är det enda omständighet som du kan tänka på där vi skulle behöva returnera false? Ja. [Student] Om det är fullt och vi använder en begränsad implementering. Ja, så hur definierar, han vi besvarat om det är fullt och vi använder en begränsad implementering. Då kommer vi definitivt att returnera false. Så snart vi träffar 10 saker i arrayen, kan vi inte passar 11, så vi returnera false. Tänk om det är obegränsad? Ja. Om du inte kan expandera arrayen av någon anledning. Ja, det är så minne en begränsad resurs, och så småningom, om vi fortsätter trycka saker på stacken om och om igen, vi ska försöka fördela en större mängd för att passa den större kapacitet och malloc eller vad vi använder kommer att returnera false. Tja, kommer malloc returnera null. 

Kom ihåg att varje gång du någonsin ringa malloc, bör du kontrollera om det returnerar null eller annat som är en korrekt avdrag. Eftersom vi vill ha en obegränsad stack, det enda fall vi kommer att vara tillbaka falska är om vi försöker öka kapaciteten och malloc eller vad returnerar false. Sedan pop tar inga argument, och det returnerar strängen som är på toppen av stacken. Oavsett var senast tryckte på stacken är vad pop återvänder, och det tar också bort det från stapeln. Och märker att det returnerar null om det inte finns något på stacken. Det är alltid möjligt att stacken är tom. I Java, om du är van vid det, eller andra språk, försöker pop från en tom stack kan orsaka ett undantag eller något. 

Men i C, null slags många av de fall hur vi hanterar dessa problem. Återvänder null är hur vi ska betyda att stacken var tom. Vi ger kod som kommer att testa din stack funktionalitet, genomföra skjuta och pop. Detta kommer inte att finnas en hel del kod. Jag kommer-faktiskt, innan vi gör det, tips, tips, Om du inte har sett det, är malloc inte den enda funktionen som fördelar minne på heap för dig. Det finns en familj av Alloc funktioner. Den första är malloc, som du är van vid. Sedan finns calloc, som gör samma sak som malloc, men det kommer noll allting för dig. Om du någonsin velat ställa allt till null efter mallocing något Du bör bara använt calloc i första hand istället för att skriva en for-slinga för att nollställa hela block av minne. 

Realloc är som malloc och har en hel del speciella fall, men i stort sett vad realloc gör är det tar en pekare som redan hade tilldelats. Realloc är den funktion som du vill ska uppmärksamma här. Det tar en pekare som redan återvänt från malloc. Låt oss säga att du begär från malloc en pekare på 10 byte. Senare inser du att du ville 20 byte, så du kallar realloc på den pekare med 20 byte, och realloc kommer automatiskt kopiera över allt för dig. Om du ringde bara malloc igen, som jag har ett block med 10 byte. Nu behöver jag ett block med 20 byte, så om jag malloc 20 byte, då måste jag manuellt kopiera över de 10 byte från första i den andra sak och sedan fri det första. Realloc kommer att hantera det åt dig. 

Lägg märke till signaturen kommer att vara ogiltiga * som just returnerar en pekare till blocket av minnet, sedan void * ptr. Du kan tänka på void * som en generisk pekare. Generellt hanterar du aldrig med void *, men malloc återvänder ett tomrum *, och sedan är det bara används som Detta är faktiskt kommer att bli en char *. Den tidigare void * som hade återvänt från malloc kommer nu att föras till realloc och sedan storlek är det nya antalet byte som du vill tilldela, så att din nya kapacitet. Jag ska ge er ett par minuter, och göra det i vårt utrymme. Börja med Revision 1. Jag ska sluta dig efter förhoppningsvis om tillräckligt med tid att genomföra push, och sedan ska jag ge er ett annat paus för att göra pop. Men det är verkligen inte så mycket kod alls. Den mest koden är förmodligen den expanderande grejer, utöka kapaciteten. Okej, ingen press att vara helt klar, men så länge du känner att du är på rätt väg, det är bra. 

Har någon någon kod som de känner sig bekväma med mig att dra upp? Ja, det ska jag, men någon har någon kod jag kan dra upp? Okej, kan du starta, spara den, vad är det? Jag glömmer alltid det steget. Okej, titta på push, vill du förklara din kod? [Student] Först av allt, ökade jag storleken. Jag antar kanske jag borde ha det, hur som helst, ökade jag storleken, och jag se om det är mindre än kapaciteten. Och om det är mindre än kapaciteten, lägger jag till array som vi redan har. Och om det inte är, multiplicera jag kapaciteten med 2, och jag omfördela strängar array för att något med en större kapacitet storlek nu. Och sedan om det misslyckas, säger jag användaren och returnera false, och om det är bra, då jag satte strängen i den nya platsen. 

[Rob B.] också märke till att vi använde en fin bitvis här att multiplicera med 2. Kom ihåg att vänster skift kommer alltid att multipliceras med 2. Högerskift divideras med 2, så länge du kommer ihåg att det betyder dividera med 2 såsom i ett heltal delat med 2. Det kan trunkera en 1 här eller där. Men skift kvar av 1 kommer alltid att multipliceras med 2, om du inte svämma över gränserna för heltal och då det inte kommer att bli. En sida kommentar. Jag tycker om att göra, det kommer inte att ändra kodningen något sätt, men jag gillar att göra något sånt här. Det faktiskt kommer att göra det lite längre. Kanske är detta inte den perfekta fallet för att visa detta, men jag gillar att dela det i dessa block- Okej, om detta om händer, då kommer jag att göra något, och därefter funktionen görs. Jag behöver inte rulla mina ögon hela vägen ner funktionen att se vad som händer efter annat. Det är om detta om händer, då jag återvänder bara. Det har också den trevliga fördelen av allt utöver detta Nu flyttas till vänster en gång. Jag behöver inte längre, om du någonsin nära löjligt långa rader, då de 4 byte kan hjälpa, och även mer vänster något är, mindre överväldigade du känna dig om vill-Okej, jag måste komma ihåg Jag är just nu i en while-slinga inuti en annan inne i en for-slinga. Var du kan göra detta omedelbart återvända, jag gillar. Det är helt frivilligt och inte förväntas på något sätt. 

[Student] Skulle det finnas en storlek - i misslyckas skick? Den misslyckas villkoret här är att vi inte realloc, så ja. Lägg märke till hur i misslyckas skick, förmodligen, om vi gratis saker senare, vi kommer alltid att misslyckas oavsett hur många gånger vi försöker driva något. Om vi ​​fortsätter att trycka håller vi uppräkning storlek, även om vi inte sätter något på stacken. Vanligtvis vi öka inte storleken förrän efter att vi har lagt ett framgångsrikt det på stacken. Vi skulle göra det, säger, antingen här och här. Och sedan istället för att säga s.size ≤ kapacitet, det är mindre än kapaciteten, bara för att vi flyttade där allt var. 

Och kom ihåg, den enda plats som vi kunde eventuellt returnera false är här, där realloc återvände null, och om du råkar komma ihåg standardfel, kanske du kan överväga detta ett fall där du vill skriva ut en standardavvikelse, så fprintf stderr istället för att bara skriva ut direkt till standard ut. Återigen, det är inte en förväntan, men om det är ett fel, typ printf, då kanske du vill göra det ut på standard fel istället för vanlig ut. 

Någon har något annat att notera? Ja. [Student] Kan du gå över [ohörbart]? [Rob B.] Ja, det faktiska binariness av det eller bara vad det är? [Student] Så du multiplicera det med 2? [Rob B.] Ja, i princip. I binär mark, har vi alltid vår uppsättning siffror. Växling denna vänster med 1 princip infogar det här på höger sida. Tillbaka till detta, bara komma ihåg att allt i binär är en effekt av 2, så detta är 2 till 0, Detta 2 till 1, det 2 till 2. Genom att sätta in en 0 på höger sida nu, flyttar vi bara allt över. Vad som brukade vara 2 till 0 nu 2 till 1, 2 till 2. Den högra sidan som vi in nödvändigtvis kommer att bli 0, vilket är vettigt. Om du någonsin multiplicera ett tal med 2, det kommer inte att sluta udda, så 2 till 0 plats bör vara 0, och detta är vad jag halv varnade innan är om du råkar flytta bortom antalet bitar i ett heltal, då denna 1 kommer att sluta gå ut. Det är den enda oroa dig om du råkar ha att göra med riktigt stor kapacitet. Men på den punkten, då du arbetar med en rad miljarder saker, som kanske inte passar in i minnet ändå. 

Nu kan vi få till pop, som är ännu enklare. Du kan göra det som om du råkar pop en massa, och nu är du på halv kapacitet igen. Du kunde realloc att krympa hur mycket minne du har, men du behöver inte oroa dig för det, är så det enda realloc fall kommer att vara växande minne, aldrig krympande minne, vilket kommer att göra pop super lätt. Nu köer, som kommer att vara som staplar, men den ordning du tar saker är omvänd. Den prototypiska exemplet på en kö är en linje, så jag antar att om du var engelska, skulle jag ha sagt en prototypisk exempel på en kö är en kö. Så som en linje, om du är den första personen i raden, du förväntar dig att vara den första personen ur linjen. Om du är den sista personen i linje, du kommer att bli den sista personen på service. Vi kallar det FIFO mönster, medan stapeln var LIFO mönster. Dessa ord är ganska universella. 

Som stackar och till skillnad från arrayer, köer vanligtvis inte tillåter åtkomst till element i mitten. Här, en stack, har vi push och pop. Här råkar vi ha kallat dem enqueue och dequeue. Jag har också hört dem kallas skift och unshift. Jag har hört folk säga push-och pop även gälla köer. Jag har hört infoga, ta bort, så tryck och pop, om du talar om stackar, du trycka och popping. Om du pratar om köer, kan du välja de ord som du vill använda för insättning och borttagning, och det finns ingen konsensus om vad den ska heta. Men här har vi enqueue och dequeue. Nu ser struct nästan identisk till stapeln struct. Men vi måste hålla reda på huvudet. Jag antar att det står här nere, men varför behöver vi huvudet? Prototyperna är i princip identiska att driva och pop. Du kan se det som push och pop. Den enda skillnaden är pop återvänder-istället för sist, det tillbaka den första. 2, 1, 3, 4, eller något. Och här är början. Vår kö är helt full, så det finns fyra element i den. I slutet av vår kö är för närvarande 2, och nu går vi för att infoga något annat. 

När vi vill infoga det något annat, vad vi gjorde för stapeln versionen är vi utökat vår block av minne. Vad är problemet med detta? [Student] Du flyttar 2. Vad jag sa tidigare om slutet av kön, Detta är inte rimligt att vi börjar vid 1, då vill vi dequeue 1, sedan dequeue 3, sedan dequeue 4, sedan avköande 2, sedan avköa här. Vi kan inte använda realloc nu, eller åtminstone, måste du använda realloc på ett annat sätt. Men du förmodligen inte bara använda realloc. Du kommer att behöva manuellt kopiera ditt minne. 

Det finns två funktioner att kopiera minne. Det finns memcopy och memmove. Jag läser just nu de man-sidor för att se vilken du kommer att vilja använda. Okej, memcopy är skillnaden att memcopy och memmove, en hanterar ärendet korrekt där du kopierar in i ett område som råkar överlappa regionen du kopierar från. Memcopy hanterar inte det. Memmove gör. Du kan tänka på problemet som- låt oss säga att jag vill kopiera den här killen, Dessa fyra till den här killen över. I slutändan, vad gruppen bör se ut Efter kopian är 2, 1, 2, 1, 3, 4, och lite grejer i slutet. Men detta är beroende på i vilken ordning vi faktiskt kopiera, eftersom om vi inte anser att regionen vi kopierar in överlappar en vi kopiera från, då vi kan göra som start här, kopiera 2 i den plats vi vill gå, flytta sedan våra pekare framåt. 

Nu ska vi vara här och här och nu vill vi kopiera den här killen över den här killen och flytta våra pekare framåt. Vad vi ska i slutändan får är 2, 1, 2, 1, 2, 1 istället för den lämpliga 2, 1 2,, 1, 3, 4, eftersom 2, 1 överskred den ursprungliga 3, 4. Memmove handtag som korrekt. I det här fallet, i princip bara alltid memmove eftersom det hanterar det på rätt sätt. Det i allmänhet inte utför något värre. Tanken är i stället för att börja från början och kopiera det här sättet som vi just gjorde här, börjar det från slutet och kopierar in, och i så fall, kan du aldrig ett problem. Det finns ingen prestanda förlorad. Använd alltid memmove. Aldrig oroa memcopy. Och det är där du kommer att behöva separat memmove den förpackade runt del av ditt kön. Inga problem om inte helt klar. Detta är svårare än stack, push, och pop. 

Någon har någon kod vi kan arbeta med? Även om helt ofullständig? [Student] Ja, det är helt ofullständig, dock. Helt ofullständig är bra så länge vi-kan du spara översynen? Jag glömmer att varje gång. Okej, strunta vad som händer när vi behöver ändra storlek saker. Helt ignorera ändra storlek. Förklara denna kod. Jag kollar först om storleken är mindre än kopian först och sedan efter det, jag sätter-Jag tar huvud + storlek, och jag se till att det sveper runt kapacitet arrayen, och jag sätter den nya strängen i den positionen. Då jag öka storleken och returnera sant. 

[Rob B] Detta är definitivt en av de fall där du kommer att vilja använda mod. Varje typ av fall där du har omslag runt, om du tror omslag runt, den omedelbara tanken bör vara mod. Som en snabb optimering / gör din kod en rad kortare, du märker att raden omedelbart efter detta en är bara storleken + +, så du kopplar in det i denna linje, storlek + +. Nu här nere har vi fallet där vi inte har tillräckligt med minne, så vi ökar vår kapacitet med 2. Jag antar att man kan ha samma problem här, men vi kan ignorera det nu, där om du inte öka din förmåga, då du kommer att vilja minska din förmåga med 2 igen. En annan kort anmärkning är precis som du kan göra + =, Du kan också göra << =. Nästan vad som helst kan gå innan jämlikar, + =, | =, & =, << =. Char * ny är vår nya block av minne. Åh, här borta. 

Vad tycker folk om vilken typ av vår nya block av minne? [Student] Det bör vara röding **. Tänker tillbaka på vår struct här uppe, strängar är vad vi omfördela. Vi gör en helt ny dynamisk lagring för elementen i kön. Vad vi kommer att tilldela dina strängar är vad vi mallocing just nu, och så nya kommer att bli en röding **. Det kommer att bli en array med strängar. Vad som är fallet enligt vilken vi kommer att återvända falska? [Student] Ska vi göra det char *? [Rob B.] Ja, bra samtal. [Student] Vad var det? [Rob B.] Vi ville göra storleken på char * eftersom vi inte längre Detta skulle faktiskt vara ett mycket stort problem eftersom sizeof (char) skulle vara 1. Sizeof char * kommer att bli 4, så många gånger när du arbetar med Ints, du brukar komma undan med det eftersom storleken på int och storlek int * på en 32-bitars system kommer att bli samma sak. Men här, sizeof (char) och sizeof (char *) nu kommer att vara samma sak. 

Vad är situation då vi returnera false? [Student] Ny är null. Ja, om nya är null, återvänder vi falska, och jag kommer att kasta ner här- [Student] [ohörbart] [Rob B.] Ja, det här bra. Du kan antingen göra 2 gånger kapacitet eller kapacitet skift 1 och sedan bara sätter ner här eller vad som helst. Vi gör det som vi hade det. Kapacitet >> = 1. Och du aldrig kommer att behöva oroa sig för att förlora 1 plats eftersom du lämnade flyttas med 1, så 1 plats är nödvändigtvis en 0, så rätt förskjutning av 1, du kommer fortfarande vara bra. [Student] Behöver du göra det innan retur? [Rob B.] Ja, gör detta helt meningslöst. 

Nu antar vi ska sluta återvänder sant till slutet. Hur vi ska göra dessa memmoves, Vi måste vara försiktiga med hur vi gör dem. Har någon några förslag på hur vi gör dem? Här är vår början. Oundvikligen vill vi börja från början igen och kopiera saker i därifrån, 1, 3, 4, 2. Hur gör man det? Först måste jag titta på manualsidan för memmove igen. Memmove är ordning argument alltid viktigt. Vi vill att vår destination först, källa andra storlek trea. Det finns en hel del funktioner som vända källa och destination. Destination, källa tenderar att vara konsekvent något. Flytta, vad är det tillbaka? Den returnerar en pekare till destination, oavsett anledning kanske du vill det. Jag kan bilden läste det, men vi vill flytta in vår destination. 

Vad är vårt mål kommer att? [Student] Ny. [Rob B.] Ja, och vart är vi på kopiera från? Det första vi kopierar detta 1, 3, 4. Vad är-det 1, 3, 4. Vad är adressen till detta 1? Vad är adressen till den 1? [Student] [ohörbart] [Rob B.] Huvud + adressen till det första elementet. Hur får vi det första elementet i arrayen? [Elev] kö. [Rob B.] Ja, q.strings. Kom ihåg, här är vår huvud 1. Banne mej. Jag tycker bara att det är magiskt, Här är vår huvud 1. Jag ska ändra min färg också. Och här är strängar. Detta kan vi skriva antingen det som vi gjorde hit med huvud + q.strings. Många människor också skriva det och q.strings [huvud]. Detta är egentligen inte något mindre effektiv. Du kanske tänker på det som du dereferencing det och sedan få adressen till, men kompilatorn kommer att översätta det till vad vi hade tidigare i alla fall, q.strings + huvud. Oavsett vad du vill tänka på det. 

Och hur många bytes vi vill kopiera? [Student] Kapacitet - huvud. Kapacitet - huvud. Och då kan du alltid skriva ut ett exempel ta reda på om det är rätt. [Student] Det måste delas med 2 då. Ja, så jag antar att vi skulle kunna använda storlek. Vi har fortfarande storlek är- använda storlek, har vi storlek lika med 4. Vår storlek är 4. Vår huvud är 1. Vi vill kopiera dessa 3 element. Det är förstånd kontrollera att storlek - huvudet är korrekt 3. Och komma tillbaka hit, som vi sagt tidigare, om vi använde kapacitet, så vi skulle behöva dela med 2 eftersom vi har redan vuxit vår kapacitet, så istället, vi kommer att använda storlek. Att kopior denna del. Nu behöver vi kopiera den andra delen, den del som är kvar av starten. 

Det kommer att memmove i vad läge? [Student] Plus size - huvud. Ja, så har vi redan kopierat i storlek - huvud byte, och så var vi vill kopiera de återstående byte är nytt och sedan storlek minus-ja, det antal byte som vi redan har kopierat in Och sedan var vi kopiera från? [Student] Q.strings [0]. [Rob B.] Ja, q.strings. Vi kan antingen göra och q.strings [0]. Detta är betydligt mindre vanligt än detta. Om det bara kommer att bli 0, så kommer du tenderar att se q.strings. Det är där vi kopiera från. Hur många bytes har vi kvar att kopiera? >> [Student] 10. Rätt. [Student] Har vi multiplicera 5 till 10 gånger större byte eller något? Ja, så det är där-vad exakt vi kopierar? [Student] [ohörbart] Vilken typ av sak vi kopierar? [Student] [ohörbart] Ja, så char * s att vi kopierar, vet vi inte var de kommer ifrån. Jo, där de pekar på, liksom strängarna hamnar vi driver den på kön eller enqueuing på kön. Där de kommer ifrån, vi har ingen aning. Vi behöver bara hålla reda på char * s själva. Vi vill inte kopiera storlek - huvud byte. Vi vill kopiera storlek - huvud char * s, så vi kommer att multiplicera med sizeof (char *). Samma här nere, chef * sizeof (char *). 

[Student] Hur [ohörbart]? Denna rätt här? [Student] Nej, under den, storlek - huvudet. [Rob B.] Denna rätt här? Pointer aritmetik. Hur pekare aritmetik kommer att fungera är den multiplicerar automatiskt av storleken av den typ som vi har att göra med. Precis som här, ny + (storlek - huvud) är exakt lika med och nya [storlek - huvud] tills vi förväntar oss att arbeta på rätt sätt, eftersom om vi har att göra med en int array, så vi inte index med int- eller om det är av storlek 5 och du vill den 4: e delen, då vi index till int array [4]. Du du inte får [4] * storlek int. Som hanterar det automatiskt, och detta fall är bokstavligen lika, så fästet syntaxen är bara kommer att konverteras till detta så snart som du kompilerar. Det är något du måste vara försiktig med att När du lägger till storlek - huvud du lägger inte en byte. Du lägger en char *, som kan vara en byte eller vad som helst. 

Övriga frågor? Okej, dequeue kommer att bli lättare. Jag ska ge er en minut att genomföra. Åh, och jag antar att detta är samma situation där vad enqueue fallet, om vi enqueuing null, kanske vi vill hantera det, vi kanske inte. Vi kommer inte att göra det igen här, men samma som vår stack fall. Om vi ​​köa null, kanske vi vill bortse från det. Någon har någon kod jag kan dra upp? [Student] Jag har bara dequeue. Version 2 är att-okej. Vill du förklara? [Student] Först gör du att det finns något i kön och att storleken går ner med 1. Du måste göra det, och sedan tillbaka huvudet och sedan flytta huvudet uppåt 1. Okej, så det är ett hörn fall måste vi ta hänsyn till. Ja. [Student] Om ditt huvud är det sista elementet, då du inte vill huvud peka utanför arrayen. 

Ja, så snart som chef träffar slutet av vår grupp, När vi avköa bör vår huvudet modded till 0. Tyvärr kan vi inte göra det i ett steg. Jag antar det sätt jag skulle nog fixa det är Detta kommer att bli en char *, vad vi tillbaka, oavsett din variabelnamn vill vara. Sen vill vi mod huvudet av vår kapacitet och sedan tillbaka ret. Många människor här de kan göra, detta är fallet med-du se folk göra om huvudet är större än kapaciteten, gör huvudet - kapacitet. Och det är bara att arbeta kring vad mod är. Chef mod = kapacitet är mycket renare av ett omslag runt än om huvudet är större än kapaciteten huvud - kapacitet. 

Frågor? Okej, är det sista vi har kvar vår länkad lista. Du skulle kunna användas till några av de länkade listan beteende om du gjorde länkade listor i dina hashtabeller, om du gjorde en hash-tabell. Jag rekommenderar starkt att göra en hash-tabell. Du kanske redan har gjort en trie, men försök är svårare. I teorin är de asymptotiskt bättre. Men titta bara på den stora styrelsen, och försöker aldrig göra bättre, och de tar upp mer minne. Allt försöker om slutar som värre för mer arbete. Det är vad David Malan lösning alltid är Är han alltid inlägg hans trie lösning, och låt oss se var han för närvarande är. Vad var han under, David J? Han är # 18, så det är inte så väldigt dåligt, och det kommer att bli en av de bästa försöker man kan tänka eller en av de bästa försök av en trie. Är det inte ens hans ursprungliga lösning? Jag känner mig som Trie lösningar tenderar att vara mer i denna serie av RAM-användning. 

Gå ner till den absoluta toppen, och RAM-användning i de enskilda siffror. Gå ner mot botten, och sedan börjar se försöker där du får absolut massiv RAM-användning, och försöker är svårare. Inte helt värt det men en lärorik erfarenhet om du gjorde en. Det sista är vår länkad lista, och dessa tre saker, stackar, köer och länkade listor, framtida sak du någonsin gör i datavetenskap kommer att anta att du har kännedom om dessa saker. De är bara så grundläggande för allt. 

Länkade listor, och här har vi en enskilt länkad lista kommer att bli vårt genomförande. Vad enskilt kopplade innebär i motsats till dubbelt länkad? Ja. [Student] Den pekar bara till nästa pekaren istället för pekare, liknande det som föregick den och den ena efter den. Ja, så i bildformat, vad jag gör just? Jag har två saker. Jag har bild och bild. I bildformat, våra enstaka länkade listor, oundvikligen har vi någon form av pekare till chefen för vår lista, och sedan inom vår lista har vi bara pekare, och kanske tyder detta på null. Det kommer att vara din typiska ritning av en länkad enskilt lista. En dubbelt länkad lista, kan du gå bakåt. Om jag ger dig något nod i listan, kan du nödvändigtvis få till någon annan nod i listan om den är en dubbelt länkad lista. Men om jag får du den tredje noden i listan och det är en enstaka länkad lista, inget sätt du någonsin kommer att få den första och andra noder. Och det finns fördelar och nackdelar, och en uppenbar en är att ta dig upp mer storlek och du måste hålla reda på var dessa saker pekar nu. Men vi bryr sig bara om enstaka länkade. 

Några saker vi kommer att behöva genomföra. Din typedef struct nod, int i: struct nod * nästa; nod. Det typedef bör brännas in i dina sinnen. Quiz 1 ska vara som ger en typedef av en länkad lista nod, och du bör omedelbart kunna klottra ner det utan att ens tänka på det. Jag antar ett par frågor, varför behöver vi Struct här? Varför kan vi inte säga nod *? [Student] [ohörbart] Ja. Det enda som definierar en nod som en sak är den typedef själv. Men som på denna punkt, när vi är typ av tolkning genom denna struct nod definition, vi har inte avslutat vår typedef ännu, så då typedef inte är klar, nod existerar inte. Men struct nod gör denna nod och här, Detta skulle också kunna kallas något annat. Detta skulle kunna kallas N. Det skulle kunna kallas länkad lista nod. Det skulle kunna kallas något. Men denna struct nod måste kallas samma sak som denna struct nod. Vad du kallar detta måste också vara här, och så att också ett svar på andra punkten i frågan vilket är anledningen till-många gånger när du ser structs och typedefs av structs, ser du anonyma structs där du bara se typedef struct, genomförandet av struktur, ordbok, eller något annat. 

Varför här behöver vi säga nod? Varför kan det inte vara en anonym struktur? Det är nästan samma svar. [Student] Du måste hänvisa till den inom struct. Ja, inom struct måste du referera till struct själv. Om du inte ger struct ett namn, om det är en anonym struct kan du inte hänvisa till den. Och sist men inte minst bör dessa alla vara något enkelt, och de bör hjälpa dig att inse om du skriver ner det att du gör något fel om dessa typer av saker inte vettigt. Sist men inte minst, varför det måste vara struct nod *? Varför kan det inte bara vara struct nod härnäst? [Student] Pekare till nästa struct. Det är oundvikligen vad vi vill. Varför kunde det aldrig struct nod härnäst? Varför måste det vara struct nod * nästa? Ja. [Student] Det är som en oändlig slinga. Ja. [Student] Det skulle alla vara i en. Ja, tänk bara på hur vi skulle göra storlek eller något. Storleken på en struktur är i grunden + eller - någon mönster här eller där. Det är i princip kommer att vara summan av storleken på saker i struct. Denna rätt här, utan att ändra något, är storleken kommer att bli lätt. Storlek på struct nod kommer att vara storleken på i + storlek nästa. Storlek I kommer att bli 4. Storlek på nästa kommer att bli 4. Storlek på struct nod kommer att bli 8. Om vi ​​inte har *, tänker på sizeof, sedan sizeof (i) kommer att vara 4. Storlek på struct nod nästa kommer att vara storleken på i + storlek struct nod nästa + Storlek i + storlek struct nod nästa. Det skulle vara en oändlig rekursion av noder. Det är därför det är så det måste vara. 

Återigen, definitivt memorera det, eller åtminstone förstå det nog att du kan ha möjlighet att Därför igenom vad den ska se ut. De saker vi kommer att vilja genomföra. Om längden av listan- du kunde fuska och hålla runt en globala längd eller något, men vi kommer inte att göra det. Vi kommer att räkna längden på listan. Vi har innehåller, så det är i princip som en sökning, så vi har en länkad lista av heltal för att se om detta är heltal i den länkade listan. Prepend kommer att infoga i början av listan. Append kommer att infoga i slutet. Insert_sorted kommer att infoga i den sorterade position i listan. Insert_sorted typ av förutsätter att du aldrig använt prefix eller lägga i dåliga sätt. 

Insert_sorted när du genomföra insert_sorted- låt oss säga att vi har vår länkad lista. Detta är vad det för närvarande ser ut, 2, 4, 5. Jag vill infoga 3, så länge som själva listan redan sorteras, det är lätt att hitta där 3 hör. Jag börjar på 2. Okej, är 3 större än 2, så jag vill fortsätta. Åh, 4 för stor, så jag vet 3 kommer att gå mellan 2 och 4, och jag måste fixa pekare och allt det där. Men om vi inte strikt använder insert_sorted, liknande låt oss bara säga jag lägger du 6, då min länkad lista kommer att bli det. Det gör nu ingen mening, så för insert_sorted, kan du bara ta att listan är sorterad, även om verksamheten finns vilket kan göra att det inte sorteras, och det är det. Hitta en bra insats, så de är de viktigaste sakerna du kommer att behöva genomföra. 

För nu, ta en minut att göra längd och innehåller, och de bör vara relativt snabb. Nearing stängningstid, så någon har något för längd eller innehåller? De kommer att vara nästan identiska. [Elev] Längd. Låt oss se, ses över. Okej. Vill du förklara? [Student] Jag bara skapa en pekare nod och initiera den till först, vilket är vårt globala variabel, och då jag kontrollera om det är noll så jag inte får en seg fel och returnerar 0 om så är fallet. Annars jag genomkoppling, hålla reda på inom heltal hur många gånger jag har öppnat nästa element i listan och i samma inkrement verksamheten också komma att den faktiska element, och då gör jag hela tiden kontrollen för att se om det är noll, och om det är noll, då avbryter och bara returnerar antalet element jag har åtkomst. 

[Rob B.] Har någon några synpunkter på något? Detta ser bra ut korrekthet klokt. [Student] Jag tror inte du behöver noden == null. Ja, så om nod == null avkastning 0. Men om nod == null då detta-Åh, det är en riktig fråga. Det var bara du tillbaka i, men det är inte i omfattning just nu. Du behöver bara int i, så jag = 0. Men om noden är null, så jag är fortfarande kommer att vara 0, och vi kommer att återvända 0, så det här fallet är identiska. En annan vanlig sak är att intyget av nod inuti for-slingan. Man skulle kunna säga-åh, nej. Låt oss hålla det som denna. Jag skulle förmodligen sätta int i = 0 här, då nod * nod = första här. Och detta är förmodligen hur-att bli av detta nu. Detta är förmodligen hur jag skulle ha skrivit den. Du kan också, titta på det så här. Detta för öglestruktur här bör vara nästan lika naturligt för dig som för int i = 0 i är mindre än längden av matris i + +. Om det är hur du iterera över en array, det är hur du iterera över en länkad lista. 

Detta bör vara en självklarhet vid något tillfälle. Med detta i åtanke, detta kommer att bli nästan samma sak. Du kommer att vilja att iterera över en länkad lista. Om nod-Jag har ingen aning om vad värdet heter. Nod i.. Om värdet vid den noden = jag tillbaka sant, och det är det. Observera att det enda sättet vi någonsin återvända falska är om vi iterera över den länkade hela listan och aldrig återvända sant, så det är vad det gör. Som en sida noterar, vi förmodligen inte kommer att få lägga eller lägger du. 

Snabb sista anmärkning. Om du ser nyckelordet static, så låt oss säga static int count = 0, vi räknas + +, kan du i princip se det som en global variabel, även om jag sagt just detta är inte hur vi ska genomföra längd. Jag gör det här, och sedan räkna + +. Något sätt vi kan ange en nod i vår länkad lista vi uppräkning vår räkning. Poängen med detta är vad nyckelordet static betyder. Om jag bara hade int count = 0 som skulle vara en vanlig gammal global variabel. Vilka static int count betyder att det är en global variabel för denna fil. Det är omöjligt för någon annan fil, gillar att tänka på pset 5, om du har börjat. Du har både speller.c, och du har dictionary.c, och om du deklarerar bara en sak global, sedan något i speller.c kan nås i dictionary.c och vice versa. Globala variabler är tillgängliga för alla. C. fil, men statiska variabler är endast tillgängliga inifrån själva filen, så inne i stavningskontroll eller insidan av dictionary.c, Detta är typ av hur jag skulle förklara min variabel för storleken på min array eller storleken på min antal ord i ordlistan. Eftersom jag inte vill att deklarera en global variabel som någon har tillgång till, Jag verkligen bara bryr sig om det för mina egna syften. 

Det som är bra med detta är också hela namnet kollision grejer. Om någon annan fil försöker använda en global variabel som heter räkna, det går mycket, mycket fel, så detta håller fint saker säkert och bara du kan komma åt den, och ingen annan kan, och om någon annan deklarerar en global variabel som heter räkna, då det inte kommer att störa din statisk variabel som kallas räknas. Det är vad statisk är. Det är en fil global variabel. 

Frågor om vad som helst? Allt klart. Hej då. [CS50.TV]