[Powered by Google Translate] [Avsnitt 6: mindre bekväm] [Nate Hardison] [Harvard University] [Detta är CS50.] [CS50.TV] Okej. Välkommen till avsnitt 6. Den här veckan kommer vi att tala om datastrukturer i snitt, främst eftersom denna veckas problem inställt på spellr gör en hel massa olika datastruktur prospektering. Det finns en massa olika sätt du kan gå med problemet som, och ju fler datastrukturer du känner, desto mer coola saker du kan göra. 

Så låt oss komma igång. Först ska vi prata om stackar, stapeln och kö datastrukturer som vi kommer att prata om. Stackar och köer är verkligen hjälpsam när vi börjar prata om grafer, som vi inte kommer att göra så mycket av just nu. Men de är riktigt bra för att förstå en av de stora fundamentala datastrukturer CS. Beskrivningen i problemet inställda specifikation, om du drar upp det, talar om högar som liknar högen av restauranger fack som du har i cafeterian på matsalar där när restauranger personal kommer och sätter matsal brickor ut efter att de har rengjorts dem, de stapla dem ovanpå varandra. Och sedan när barnen kommer in för att få mat, de drar facken bort först den översta en, sedan en under det, då en under den. Så i själva verket är det första facket som matsal personalen sätta ner den sista som får tas bort. Den sista som matsal personalen sätta på är den första som får tas ut för middag. I problemet apparatens spec, som du kan hämta om du inte redan har, Vi talar om modellering en stucture stack data med hjälp denna typ av struktur. 

Så vad vi har här, är det liknar det som presenterades i föreläsning, utom i föreläsning vi presenterade detta med Ints i motsats till char * s. Detta kommer att vara en bunt som lagrar vad? Daniel? Vad är det vi lagrar i denna stack? [Daniel] Strängar? >> Vi lagrar strängar i denna stack, exakt. Allt du behöver ha för att skapa en stapel är en matris av en viss kapacitet, som i detta fall, kapaciteten kommer att vara i stora bokstäver eftersom det är en konstant. Och sedan utöver arrayen är allt vi behöver för att spåra den nuvarande storleken på matrisen. En sak att notera här att det är ganska coolt är att vi skapar den staplade datastrukturen ovanpå en annan datastruktur, matrisen. Det finns olika sätt att genomföra stackar. Vi kommer inte att göra det riktigt än, men förhoppningsvis efter gör de länkade-listan problem, ser du hur du enkelt kan genomföra en bunt på toppen av en länkad lista också. Men nu kommer vi hålla oss till uppsättningarna. Så återigen, är allt vi behöver en matris och vi behöver bara följa storleken på matrisen. [Sam] Tyvärr, varför är det att du sa stapeln är på toppen av strängarna? För mig verkar det som strängarna är inom stacken. [Hardison] Ja. Vi skapar, vi tar vår array datastruktur - Det är en bra fråga. Så frågan är varför, för de människor som tittar på detta online, varför säger vi att stapeln är på toppen av strängarna, för här ser det ut som strängarna är inne i stacken? Som är helt fallet. Vad jag syftade på var att vi har en struktur array data. Vi har en rad char * s, denna array med strängar, och vi kommer att lägga till den för att skapa den staplade datastrukturen. 

Så en stapel är något mer komplicerad än en array. Vi kan använda en matris för att bygga en stapel. Så det är där vi säger att stapeln är byggd ovanpå en matris. Likaså som jag sa tidigare, kan vi bygga en stapel ovanpå en länkad lista. Istället för att använda en array för att hålla våra element, vi skulle kunna använda en länkad lista för att hålla våra element och bygga stacken runt det. Låt oss gå igenom ett par exempel, titta på några kod, att se vad som faktiskt händer här. Till vänster har jag kastat ner vad som stack struct skulle se ut i minnet Om kapaciteten skulle # definieras som fyra. Vi har våra fyra element char * array. Vi har strängar [0], stråkar [1], strängar [2], strängar [3], och sedan den sista plats för vår storlek heltal. Verkar denna mening? Okej. Detta är vad som händer om det jag gör till höger, som kommer att vara min kod, är att bara förklara en struct, ett staplat struct som kallas talet. Detta är vad vi får. Det fastställer denna fotavtryck i minnet. Den första frågan här är vad är innehållet i denna stack struct? Just nu är de ingenting, men de är inte helt ingenting. De är denna typ av skräp. Vi har ingen aning om vad som finns i dem. När vi förklarar stack s, vi kastar bara ner det på toppen av minnet. Det är ungefär som att förklara int i och inte initiera det. Du vet inte vad som finns där inne. Du kan läsa vad som finns där inne, men det kanske inte super bra. En sak som du vill alltid komma ihåg att göra är initiera vad måste initieras. I det här fallet kommer vi att initiera storleken vara noll, eftersom det kommer att visa sig vara mycket viktig för oss. Vi skulle kunna gå vidare och initiera alla pekare, alla char * s, vara några förståeligt värde, troligen null. Men det är inte helt nödvändigt att vi gör det. 

Nu är de två huvudsakliga operationer på staplar är? Någon minns från föreläsning vad du gör med högar? Ja? [Stella] Pushing och popping? >> Exakt. Trycka och popping är de två huvudsakliga verksamhet på staplar. Och vad gör tryck? >> Det sätter något på toppen av stapeln, och sedan poppande tar bort det. [Hardison] Exakt. Så trycka skjuter något på toppen av stacken. Det är som matsal personal att sätta en matsal ner förpackningen på disken. Och poppar tar en matplats fack bort från stapeln. Låt oss gå igenom ett par exempel på vad som händer När vi driva saker till stacken. Om vi ​​skulle driva strängen "Hej" på vår stack, Detta är vad vår diagrammet skulle se ut nu. Se vad som händer? Vi drev i den första delen av vår strängar array och vi folkomröstade vår storlek räkna till 1. Så om vi ser på skillnaden mellan de två bilderna, här var 0, här innan tryck. Här är efter tryck. Innan push, efter tryck. Och nu har vi en del av vår stack. Det är strängen "hello", och det är det. Allt annat i arrayen, i våra strängar array fortfarande skräp. Vi har inte initierats det. Låt oss säga att vi trycker en annan sträng på vår stack. Vi kommer att driva "världen" på den här tiden. Så du kan se "världen" här går på toppen av "hej", och storleken räkna går upp till 2. Nu kan vi trycka "CS50" och som kommer att gå på toppen igen. Om vi ​​går tillbaka, kan du se hur vi driver saker på toppen av stacken. Och nu får vi pop. När vi dök något från i stapeln, hände vad? Någon se skillnaden? Det är ganska subtila. [Student] Storleken. >> Ja, ändrade storleken. 

Vad skulle du ha förväntat sig att förändras? [Student] De strängar, också. >> Höger. Strängarna också. Det visar sig att när du gör det här sättet, eftersom vi inte kopiera element i vår stack, vi faktiskt inte behöver göra någonting, vi kan bara använda storlek att hålla reda på hur många saker i vår grupp så att när vi dyker igen, igen vi dekrementera bara vår storlek ner till 1. Det finns ingen anledning att faktiskt gå in och skriva något. Typ av funky. Det visar sig att vi oftast bara lämna saker ensam eftersom det är mindre arbete för oss att göra. Om vi ​​inte behöver gå tillbaka och skriva något, så varför göra det? Så när vi pop dubbelt upp av stapeln, är allt som gör dekrementera storleken ett par gånger. Och återigen, det är bara för att vi inte kopierar saker i vår stack. Ja? Varsågod. [Student, obegripligt] >> Och vad händer när du trycker något igen? När du trycker något igen, det var den vägen? Vart tar det vägen, Basil? >> Till strängar [1]? >> Höger. Varför inte det gå till strängar [3]? [Basil] Eftersom det glömde att det fanns något i strängar [1] och [2]? [Hardison] Exakt. Vår stack i huvudsak "glömde" att det höll på att något i strängar [1] eller strängar [2], så när vi trycker "woot", det sätter bara in det elementet vid strängar [1]. Finns det några frågor om hur det fungerar, på en grundläggande nivå? [Sam] Så detta är inte dynamisk på något sätt, i termer av mängd eller i termer av storleken på stapeln? [Hardison] Exakt. Detta är - poängen var att detta inte var en dynamiskt growning stack. Detta är en stapel som kan hålla, som mest, fyra char * s, högst fyra saker. Om vi ​​skulle försöka driva 1/5 sak, vad tror du ska hända? [Studenter, obegripliga] [Hardison] Exakt. Det finns ett antal saker som kan hända. Det kan möjligen seg fel, beroende på vad vi var - exakt hur vi genomföra back-end. Det kan skriva. Det kan ha att buffertspill som vi pratade om i klassen. Vad skulle vara det mest självklara sak som kan skrivas över om vi försökte driva en extra sak på vår stack? Så du nämnde ett buffertspill. Vad kan vara det som skulle få skrivas över eller stampade på om vi spill misstag genom att försöka driva en extra sak? [Daniel, obegripligt] >> Möjligt. Men först, vad kan hända? Tänk om vi försökte driva fjärdedel sak? Det kan skriva över storleken, åtminstone med detta minne diagram som vi har. 

I problembild specifikationen, vilket vad vi kommer att genomföra i dag, vad vi vill göra är att återvända bara falskt. Vår push-metoden kommer att returnera ett booleskt värde, och att booleskt värde kommer att vara sant om push lyckas och falskt om vi inte kan skjuta något mer eftersom stapeln är full. Låt oss gå igenom lite av den koden just nu. Här är vår push-funktion. Vår push-funktion för en stack kommer att ta i strängen att sätta på stacken. Det kommer att returnera true om strängen framgångsrikt drivit på stacken och i annat fall false. Några förslag på vad som kan vara en bra första sak att göra här? [Sam] Om storleken är lika kapaciteten sedan återvända falska? [Hardison] Bingo. Bra jobb. Om storleken är kapaciteten, kommer vi att returnera false. Vi kan inte sätta något mer i vår stack. Annars vill vi sätta något på toppen av stacken. Vad är "toppen av stacken," början? [Daniel] Storlek 0? >> Storlek 0. Vad är toppen av stacken efter det finns en sak i stapeln? Missy, vet du? [Missy] One. >> Storlek är en, exakt. Du fortsätta att lägga till storleken, och varje gång du lägger i den nya delen på indexet storlek i arrayen. Vi kan göra det med den typen av en-liner, om det är vettigt. Så vi har fått våra strängar array, vi kommer att få tillgång till det på storleken index, och vi kommer bara att lagra våra char * där. Lägg märke till hur det finns ingen sträng kopiering pågår här, ingen dynamisk allokering av minne? Och sedan Missy tog upp vad vi nu måste göra, eftersom vi har lagrat strängen på en lämplig plats i arrayen, och hon sa att vi var tvungna att öka storleken på en så att vi är redo för nästa tryck. Så vi kan göra det med s.size + +. Vid denna punkt har vi drivit i vår grupp. Vad är det sista vi behöver göra? [Student] Tillbaka sant. >> Tillbaka sant. Så det är ganska enkelt, en ganska enkel kod. Inte för mycket. När du har lindade huvudet runt hur stapeln fungerar, Detta är ganska enkel att genomföra. 

Nu är nästa del av detta poppar en sträng av av stapeln. Jag ska ge er lite tid att arbeta med detta lite. Det är nästan huvudsak motsatsen till vad vi har gjort här i tryck. Vad jag har gjort är faktiskt - oops. Jag har startat upp en apparat hit, och i apparaten, Jag har dragit upp problemet som 5 specifikationen. Om vi ​​zoomar in här, kan vi se jag är på cdn.cs50.net/2012/fall/psets/pset5.pdf. Har ni hämtat denna kod som ligger här, section6.zip? Okej. Om du inte har gjort det, gör det nu, riktigt snabbt. Jag gör det i min terminalfönster. Jag gjorde faktiskt det här uppe. Ja. Ja, Sam? >> Jag har en fråga om varför sa du s.string s konsoler storlek = str? Vad är str? Är det definierade någonstans innan, eller - åh, i char * str? [Hardison] Ja, exakt. Det var argumentet. >> Åh, okej. Ursäkta. [Hardison] Vi anger strängen för att skjuta in Den andra frågan som kan komma upp att vi verkligen inte prata om här var vi tog för givet att vi hade denna variabel som heter s som var i omfattning och tillgängliga för oss. Vi tog för givet att s var stack struct. Så ser tillbaka på denna push-kod, kan du se att vi gör saker med den här strängen som fick skickas i men då helt plötsligt, vi tillgång s.size, som, var kom s ifrån? I koden som vi kommer att titta på i avsnittet arkiv och sedan saker som du ska göra i ditt problem sätter, Vi har gjort vår stack struktur en global variabel så att vi kan få tillgång till den i alla våra olika funktioner utan att manuellt behöva föra den runt och förbi den referens, göra allt sånt till det. Vi bara fuskar lite, om du vill, för att göra saker trevligare. Och det är något som vi gör här eftersom det är på skoj, det är lättare. Ofta ser du människor gör detta om de har en stor datastruktur som är drivs på inom deras program. 

Låt oss gå tillbaka över till apparaten. Fick alla får framgångsrikt section6.zip? Alla packa upp den med unzip section6.zip? Om du går in i avsnitt 6 katalogen - aah, överallt - och du lista vad som finns här, ser du att du har tre olika. C-filer. Du har en kö, en SLL, vilket är var för sig-länkad lista, och en skorsten. Om du öppnar stack.c, kan du se att vi har denna struct definieras för oss, den exakta struktur som vi just talade om i bilderna. Vi har vårt globala variabeln för stapeln, vi har vår push-funktion, och sedan har vi vår POP-funktionen. Jag sätter koden för trycka tillbaka upp på bilden här, men vad jag skulle vilja att ni ska göra är att efter bästa förmåga, gå och genomföra pop-funktionen. När du har genomfört den kan du kompilera detta med att göra stack, och kör sedan den resulterande stacken körbara, och som kommer att köra allt detta test kod här nere som är i main. Och viktigaste sköter faktiskt göra push och pop samtal och se till att allt går igenom bra. Den initierar också marker här så du behöver inte oroa dig för att initiera det. Du kan anta att den är rätt initierats med den tid som du kommer åt den i pop-funktionen. Verkar det vettigt? Så här går vi. Det finns push-koden. Jag ska ge er 5 eller 10 minuter. Och om du har några frågor tiden medan du kodning, vänd dem högt. Så om du kommer till en stötestenen, bara att fråga. Låt mig veta, låt alla andra veta. Arbeta med din granne också. [Daniel] Vi är bara genomföra pop just nu? >> Bara pop. Även om du kan kopiera genomförandet av tryck om du vill så att testningen kommer att fungera. Eftersom det är svårt att testa saker hamnar i - eller är det svårt att testa poppar saker av en stapel om det inte finns något i stacken till att börja med. 

Vad är pop tänkt att återvända? Elementet från toppen av stacken. Det är tänkt att få elementet bort från toppen av stacken och sedan dekrementera storleken av stapeln, och nu har du förlorat elementet på toppen. Och sedan tillbaka elementet på toppen. [Student, obegripligt] [Hardison] Så vad händer om du gör det? [Student, obegripligt] Vad hamnar händer är du förmodligen komma antingen ett element som inte har initierats ännu, så din beräkning var det sista elementet är avstängd. Så här, om du märker i tryck, vi åt strängar på s.size elementet eftersom det är ett nytt index. Det är den nya toppen av stacken. Medan i pop är s.size kommer att bli nästa utrymme, det utrymme som är på toppen av alla element i din stack. Så den översta delen är inte s.size, utan snarare är det under den. 

Den andra sak att göra när du - i pop, är du behöver för att minska det stora. Om du minns tillbaka till vår lilla diagrammet här, egentligen, det enda som vi såg hända när vi kallas pop var att denna storlek sjunkit, först 2, sedan till 1. Sedan när vi drivit ett nytt element på, skulle det gå på i rätt plats. [Basil] Om s.size är 2, skulle det inte gå att elementet 2, och då du skulle vilja pop det elementet av? Så om vi gick till - >> Så låt oss titta på detta igen. Om detta är vår stack på denna punkt och vi kallar pop, där index är den översta delen? [Basil] Som 2 men det kommer att dyka 3. >> Höger. Så det är där vår storlek är 3, men vi vill att pop elementet vid index 2. Det är den typiska typen av av av en som du har med noll-indexering av matriser. Så du vill att pop det tredje elementet, men det tredje elementet är inte på index 3. Och anledningen till att vi inte behöver göra det minus 1 när vi driver beror just nu, märker du att den översta delen, om vi skulle skjuta något annat på stapeln vid denna punkt, Vi vill driva det på index 3. Och det råkar vara så att storleken och indexen rada upp när du trycker. 

Vem har en fungerande skorsten genomförande? Du har en fungerande skorsten ett. Har du pop arbetar ännu? [Daniel] Ja. Jag tror det. >> Programmet körs och inte seg förkastningar, det skrivs ut? Har skriva ut "framgång" när du kör den? Ja. Gör stack, kör den om den skriver ut "framgång" och går inte bommen, då alla är bra. Okej. Låt oss gå över till apparaten verkligen snabbt, och vi kommer att gå igenom det här. Om vi ​​tittar på vad som händer här med pop, Daniel, vad var det första du gjorde? [Daniel] Om s.size är större än 0. [Hardison] Okej. Och varför gjorde du det? [Daniel] För att säkerställa att det var något inuti stapeln. [Hardison] Höger. Du vill testa att se till att s.size är större än 0; annars vad du vill ha hända? [Daniel] Return null? >> Tillbaka null, exakt. Så om s.size är större än 0. Vad ska vi göra? Vad gör vi om stacken inte är tom? [Stella] Du dekrementera storlek? >> Dekrementera du storlek, okej. Så hur har du det? >> S.size--. [Hardison] Great. Och vad gjorde du? [Stella] Och då sa jag tillbaka s.string [s.size]. [Hardison] Great. Annars kan du returnera null. Ja, Sam? [Sam] Varför det inte behöver vara s.size + 1? [Hardison] Plus 1? >> Ja. >> Uppfattat. [Sam] Jag trodde att du tar 1 ut, då du kommer att vara tillbaka inte den som de bad om. [Hardison] Och det var precis vad vi pratade om med hela denna fråga om 0 index. Så om vi in ​​igen här. Om vi ​​tittar på den här killen här, kan du se att när vi pop, vi poppar elementet vid index 2. 

Så vi minskar vår storlek först, sedan vår storlek motsvarar vårt index. Om vi ​​inte stega storlek först, sedan vi måste göra storlek -1 och sedan minskning. Jättebra. Alla bra? Har du frågor om detta? Det finns ett antal olika sätt att skriva detta. I själva verket kan vi göra något ännu - vi kan göra en one-liner. Vi kan göra en en-line avkastning. Så vi kan faktiskt stega innan vi återvänder genom att göra det. Så sätta - före s.size. Det gör linjen verkligen tät. Om skillnaden mellan de -. Storlek och s.size-- är att detta postfix - de kallar det postfix eftersom - kommer efter s.size-- betyder att s.size utvärderas för att finna index eftersom det är närvarande när denna linje utförs, och sedan detta - händer efter raden blir avrättas. Efter elementet vid index s.size nås. Och det är inte vad vi vill, eftersom vi vill att minskning ska ske först. Othewise, vi kommer att komma arrayen, effektivt utanför marginalerna. Vi kommer att komma elementet ovanför det som vi verkligen vill komma åt. Ja, Sam? >> Är det snabbare eller använda mindre RAM att göra i en rad eller inte? [Hardison] Ärligt talat, det beror egentligen. [Sam, obegripligt] >> Ja, det beror. Du kan göra kompilatorn trick att få kompilatorn att erkänna att, vanligtvis, antar jag. 

Så vi har nämnt lite om detta kompilator optimering grejer som du kan göra att sammanställa, och det är den typ av sak som en kompilator skulle kunna räkna ut, som oh, hey, jag kanske kan göra allt detta i en operation, i motsats till laddning av storlek variabeln i från RAM, nedräkning den, lagra den tillbaka ut, och sedan ladda den igen att behandla resten av denna operation. Men typiskt, nej, detta är inte det slags saker som kommer att göra ditt program betydligt snabbare. Några fler frågor om stackar? 

Så trycka och popping. Om ni vill prova hacker upplagan, vad vi har gjort i hacker upplagan faktiskt borta och gjorde denna stack växa dynamiskt. Utmaningen finns främst här uppe i push-funktionen, att räkna ut hur man gör den arrayen växa som du håller trycka mer och mer element på till stacken. Det är faktiskt inte så mycket extra kod. Bara ett samtal till - du måste komma ihåg att få samtal till malloc där ordentligt, och sedan räkna ut när du ska ringa realloc. Det är en rolig utmaning om du är intresserad. 

Men för närvarande, låt oss gå vidare och låt oss tala om köer. Bläddra igenom här. Kön är en nära syskon av stapeln. Så i stacken, saker som sätter i förra var de första saker för att sedan hämtas. Vi har denna sist in, först ut, eller LIFO, beställning. Medan i kön, som du kan förvänta dig från när du står i linje, den första personen att komma i linje, den första sak att komma in i kön, är det första som får hämtas från kön. Köer är också ofta används när vi har att göra med grafer, som vi pratade om kort med högar, och köerna är också praktiskt för en massa andra saker. En sak som kommer upp ofta försöker upprätthålla, till exempel, en sorterad lista av element. Och du kan göra detta med en matris. Du kan ha en sorterad lista över saker i en matris, men där det blir knepigt är så har du alltid hitta rätt plats att sätta in nästa sak. Så om du har en mängd siffror, 1 till 10, och sedan vill utöka det till alla nummer 1 till 100, och du får dessa siffror i slumpmässig ordning och försöker hålla allt sorteras som du går igenom, slut dig att behöva göra en hel del växling. Med vissa typer av köer och vissa typer av underliggande datastrukturer, Du kan faktiskt hålla det ganska enkelt. Du behöver inte lägga till något och sedan blanda det hela varje gång. Inte heller behöver du göra en hel del förskjutning av de inre delarna runt. När vi tittar på en kö, ser du att - även i queue.c i avsnittet koden - den struct som vi har gett dig är verkligen liknar struct att vi gav dig för en stack. 

Det finns ett undantag till detta, och att ett undantag är att vi har denna extra heltal kallas huvudet, och huvudet här är för att hålla koll på huvudet av kön, eller det första elementet i kön. Med en stack, kunde vi hålla reda på element som vi skulle hämta, eller toppen av stacken, med bara storleken, medan med en kö, vi har att ta itu med motsatta ändar. Vi försöker please saker på slutet, men sedan tillbaka saker från fronten. Så effektivt, med huvudet, vi har index i början av kön, och storleken ger oss indexet i slutet av kön så att vi kan hämta saker från huvudet och lägga till saker till svansen. Medan med stapeln, var vi bara behandlar toppen av stacken. Vi hade aldrig att komma till botten av stapeln. Vi lade bara saker till toppen och tog saker från toppen så att vi inte behöver det extra fält inuti våra struct. Gör som generellt vettigt? Okej. Ja, Charlotte? [Charlotte, obegripligt] [Hardison] Det är en bra fråga, och det var en som kom upp i föreläsningen. Kanske gå igenom några exempel illustrerar varför vi vill inte använda strängar [0] som chef för kön. 

Så tänk att vi har vår kö, vi kommer att kalla det kö. I början, när vi har bara instansieras det, när vi bara har förklarat det, vi har initierats ingenting. Det är allt skräp. Så naturligtvis vill vi se till att vi initiera både storlek och fälten huvudet är 0, något rimligt. Vi kan också gå vidare och null ut elementen i vår kö. Och för att göra detta diagram passform, märker att nu vår kö bara kan hålla tre element; medan vår stack kunde hålla fyra, kan vår kö hålla bara tre. Och det är bara att göra diagrammet passform. Det första som händer här är att vi köa strängen "hej". Och precis som vi gjorde med stacken, inget hemskt annorlunda här, Vi kastar strängen på vid strängar [0] och öka vår storlek med 1. Vi köa "bye", blir det sätta på. Så detta ser ut som en bunt för det mesta. Vi började här, nytt inslag, nytt element, håller storlek går upp. Vad händer på denna punkt när vi vill avköa något? När vi vill avköa, som är den del som vi vill avköa? [Basil] Strings [0]. >> Zero. Exakt rätt, Basil. Vi vill bli av med den första strängen, den här, "hej". Så vad var den andra saken som förändrats? Märker när vi popped något bort av stapeln, bytte vi bara storleken, men här har vi ett par saker som förändras. Inte bara storleken ändras, men förändringarna huvudet. Det går tillbaka till Charlottes punkt tidigare: varför har vi denna huvud också? Är det vettigt nu, Charlotte? >> Typ av. [Hardison] Typ av? Så vad hände när vi ur kön? Vad gjorde huvudet göra det nu är intressant? [Charlotte] Åh, eftersom det ändrats - okej. Jag förstår. Eftersom huvudet - där huvudet pekar på förändringar i termer av platsen. Det är inte längre alltid noll index en. >> Ja, exakt. Det som hände var om avköande hög elementet gjordes och vi hade inte detta huvud område eftersom vi alltid ringa denna sträng på 0-index i spetsen för vår kö, då vi skulle behöva flytta resten av kön ner. Vi skulle behöva flytta "bye" från strängar [1] till strängarna [0]. Och strängar [2] ner till strängar [1]. Och vi skulle behöva göra detta för hela listan av element, hela matrisen av element. Och när vi gör detta med en matris blir det verkligen dyrt. Så här är det inte en stor sak. Vi har bara tre element i vår array. Men om vi hade en kö av tusen element eller en miljon delar, och sedan helt plötsligt, vi börja göra en massa dequeue kallar alla i en slinga, saker verkligen kommer att sakta ner eftersom det skiftar ned allt hela tiden. Du vet, flytta med 1, skift med 1, skift med 1, skift med 1. Istället använder vi detta huvud, vi kallar det en "pekare" även om det egentligen inte en pekare i egentlig mening, det är inte en pekare typ. Det är inte en int * eller char * eller nåt sånt. Men det pekar eller visar huvudet av vår kö. Ja? 

[Student] Hur dequeue vet att bara lossna allt som är i spetsen? [Hardison] Hur dequeue vet hur man lossna allt är på huvudet? >> Just, ja. >> Vad det tittar på är precis vad huvudet är inställt på. Så i detta första fall om vi ser här, vårt huvud är 0, index 0. >> Höger. [Hardison] Så det bara säger okej, ja, elementet vid index 0, strängen "Hej", är det element i toppen av vår kö. Så vi kommer att avköa den killen. Och det kommer att vara den faktor som får returneras till anroparen. Ja, Saad? >> Så huvudet sätter grunden - där du kommer att indexera den? Det är början på den? >> Ja. >> Okej. [Hardison] Det är att bli den nya start för vår grupp. Så när du avköa något, allt du behöver göra åt elementet vid index q.head, och det kommer att vara det element som du vill avköa. Du måste också för att minska det stora. Vi får se i lite där det blir lite knepigt med detta. Vi avköa, och nu, om vi köa igen, var ska köa vi? Vart går nästa element i vår kö? Säg att vi vill köa strängen "CS". I vilken index kommer det att gå? [Studenter] Strings [2]. >> Två. Varför 2 och inte 0? [Basil] För nu huvudet 1, så det är som i början av listan? [Hardison] Höger. Och vad betyder slutet på listan? Vad vi använder för att beteckna slutet av vår kö? Huvudet är chef för vår kö, i början av vår kö. Vad är slutet på vår kö? [Studenter] storlek. >> Storlek, exakt. Så våra nya element går in på storlek, och de element som vi tar bort lossna på huvudet. När vi köa nästa element, vi sätter den på storlek. [Student] Innan du sätter det i var dock storlek 1, eller hur? [Hardison] Höger. Så inte riktigt på storlek. Storlek +, inte +1, men + huvud. Eftersom vi skiftade allt i huvudet belopp. Så här, nu har vi en kö av storlek 1 som börjar vid index 1. Svansen är index 2. Ja? 

[Student] Vad händer när du dequeue strängar [0] och strängar "spåren i minnet bara få tömmas, i grund och botten, eller bara glömt? [Hardison] Ja. I denna mening, vi glömmer dem bara. Om vi ​​lagrar kopior av dem för - många datastrukturer kommer ofta lagra sina egna kopior av de element så att den person som ledde datastrukturen inte behöver oroa om var alla dessa pekare är på väg. Datastrukturen håller på att allt håller på att alla kopior, att se till att allt kvarstår på lämpligt sätt. Emellertid, i detta fall, dessa datastrukturer bara, för enkelhets skull, inte göra kopior av allt som vi lagrar i dem. [Student] Så är detta en kontinuerlig rad -? >> Ja. Om vi ​​ser tillbaka på vad definitionen var denna struktur är det. Det är bara en vanlig array som du har sett, en array av char * s.. Betyder det -? >> Ja, jag undrar bara Om du så småningom slut på minne, i viss mån, Om du har alla dessa tomma platser i din array? [Hardison] Ja, det är en bra sak. 

Om vi ​​tittar på vad som har hänt nu på denna punkt, Vi har fyllt upp vår kö, ser det ut som. Men vi har inte riktigt fyllt upp vår kö eftersom vi har en kö som är storlek 2, men det börjar på index 1, eftersom det är där vårt huvud pekare är. Som du sa, att element vid strängar [0], vid index 0, är ​​inte riktigt där. Det är inte i vår kö längre. Vi bara inte brydde sig om att gå in och skriva över den när vi ur kön den. Så även om det ser ut som vi har slut på minne, har vi verkligen inte. Den platsen är tillgänglig för oss att använda. Den lämpligt beteende, om vi skulle försöka och första dequeue något liknande "bye", som skulle dyka bye av. Nu vår kö börjar på index 2 och är av storlek 1. Och nu när vi försöker köa något igen, säger 50, 50 ska gå i denna plats vid index 0 eftersom det är fortfarande tillgänglig för oss. Ja, Saad? [Saad] Händer som automatiskt? [Hardison] Det händer inte helt automatiskt. Du måste göra matten att få det att fungera, men i huvudsak vad vi har gjort är att vi bara har virad runt. [Saad] Och är det okej om det har ett hål i mitten av det? [Hardison] Det är om vi kan göra matten träna ordentligt. 

Och det visar sig att det är faktiskt inte så svårt att göra med mod operatören. Så precis som vi gjorde med Caesar och krypto grejer, med mod, kan vi få saker att linda runt och fortsätta runt och runt och runt med vår kö, hålla den framvisaren flyttar runt. Observera att storleken alltid respekterar antalet element faktiskt inom kön. Och det är bara huvudet pekare som håller cykling genom. Om vi ​​tittar på vad som hände här, om vi går tillbaka till början, och du bara titta vad som händer i huvudet När vi köa något hände ingenting på huvudet. När vi kö något annat, hände ingenting på huvudet. Snart vi ur kön något går huvudet med en. Vi kö något händer ingenting mot huvudet. När vi avköa något, huvudet plötsligt blir ökas. När vi köa något händer ingenting mot huvudet. 

Vad skulle hända på denna punkt om vi skulle avköa något igen? Några tankar? Vad skulle hända med huvudet? Vad ska hända med huvudet om vi skulle avköa något annat? Huvudet just nu är på index 2, vilket innebär att chefen för kön är strängar [2]. [Student] som returnerar 0? >> Det borde gå tillbaka till 0. Den bör slå tillbaka runt, exakt. Hittills varje gång vi kallade dequeue har vi varit att lägga ett till huvudet, lägga till en till huvudet, lägga till en till huvudet, lägga till en till huvudet. Så snart den framvisaren kommer till sista index i vår grupp, då måste vi linda den tillbaka runt till början, gå tillbaka till 0. [Charlotte] Vad avgör kapacitet kön i en stack? [Hardison] I det här fallet har vi bara använt en # definierad konstant. >> Okej. [Hardison] I själva. C. fil kan du gå in och muck med det lite och göra det så stort eller så lite som du vill. [Charlotte] Så när du gör det till en kö, hur du gör datorn vet hur stor du vill att stapeln ska vara? [Hardison] Det är en bra fråga. Det finns ett par olika sätt. En är att bara definiera det på framsidan och säga att detta kommer att bli en kö som har 4 element eller 50 element eller 10.000. Det andra sättet är att göra det som hackare utgåva folk gör och skapa funktioner för att få ditt kön att växa dynamiskt eftersom fler saker blir lagt in 

[Charlotte] Så att gå med det första alternativet, vad syntax du använder att tala om för programmet vad är storleken på kön? [Hardison] Ah. Så låt oss få ut av detta. Jag är fortfarande i stack.c här, så jag ska bara rulla upp till toppen här. Kan du se denna rätt här? Detta är den # define kapacitet 10. Och detta är nästan exakt samma syntax som vi har för kön. Utom i kö har vi att extra struct område här. [Charlotte] Åh, jag trodde kapaciteten innebar kapacitet för strängen. [Hardison] Ah. >> Att det är den maximala längden av ordet. >> Uppfattat. Ja. Kapaciteten här - det är en stor punkt. Och detta är något som är svårt eftersom det vi har förklarat här är en rad char * s. En array av pekare. Detta är en uppsättning av tecken. Detta är förmodligen vad du har sett när du har att förklara dina buffertar för fil-I / O, när du har skapat strängar manuellt på stacken. Men vad vi har här är en rad char * s. Så det är en rad pekare. Egentligen, om vi zooma ut och vi tittar på vad som händer här i presentationen ser du att de faktiska element, teckendata lagras inte i matrisen i sig. Vad lagras i vår grupp här är pekare till teckendata. Okej. Så vi har sett hur storleken på kön är precis som med bunten, storleken respekterar alltid antalet element närvarande i kön. Efter att ha gjort 2 enqueues är storleken 2. Efter att ha gjort en dequeue storleken är nu 1. Efter att ha annan enqueue storleken är tillbaka upp till 2. Så storleken respekterar definitivt antalet element i kön, och sedan huvudet blir bara cykling. Det går från 0-1-2, 0-1-2, 0-1-2. Och varje gång vi kallar dequeue, blir framvisaren ökas till nästa index. Och om huvudet är på väg att gå över, loopar tillbaka runt till 0. Så med det, kan vi skriva dequeue funktionen. Och vi kommer att lämna enqueue funktionen för er att genomföra i stället. 

När vi avköa ett element ur vår kö, vad var det första som Daniel gjorde när vi började skriva pop funktion för stackar? Låt mig höra från någon som inte har talat ännu. Låt oss se, Saad, minns du vad Daniel gjorde som första sak när han skrev pop? [Saad] Det var, var det - >> Han testade för något. [Saad] Om storleken är större än 0. >> Exakt. Och vad var det testning för? [Saad] Det testade för att se om det finns något inuti matrisen. [Hardison] Ja. Exakt. Så du kan inte pop ut något av stapeln om det är tomt. På samma sätt kan du avköa inte något från en kö om det är tomt. Vad är det första vi ska göra i vår dequeue funktion här, tror du? [Saad] Om storleken är större än 0? >> Ja. I det här fallet har jag faktiskt bara testat att se om det är 0. Om det är 0, kan vi återvända null. Men exakt samma logik. Och låt oss fortsätta med detta. Om storleken inte är 0, där är det element som vi vill avköa? [Saad] På huvudet? >> Exakt. Vi kan bara dra ut det första elementet i vår kö genom att gå till elementet på huvudet. Inget galen. Efter det, vad ska vi göra? Vad måste hända? Vad var den andra saken som vi talade om i dequeue? Två saker måste hända, eftersom vår kö har förändrats. [Daniel] Minska storleken. >> Vi måste minska storleken och öka huvudet? Exakt. För att öka huvudet, kan vi inte bara blint öka huvudet, minns. Vi kan inte bara göra queue.head + +. Vi måste även inkludera denna mod av kapaciteten. Och varför mod vi av kapaciteten, Stella? [Stella] Eftersom det har att slå runt. >> Exakt. Vi mod genom förmågan eftersom det har att svepa tillbaka runt till 0. Så nu, i det här läget kan vi göra vad Daniel sa. Vi kan dekrementera storlek. Och då kan vi bara tillbaka det element som var på toppen av kön. Det ser typ av gnarly först. Du kanske har en fråga. Ursäkta? 

[Sam] Varför är först vid toppen av kön? Vart går det? [Hardison] Den kommer från den fjärde raden från botten. Efter att vi testar att se till att vår kö inte är tom, Vi drar ut char * först, dra vi ut det element som sitter på huvudet index vår grupp, vår strängar array, >> och samtal som först? [Hardison] Och vi kallar det först. Ja. Bara för att följa upp det, varför tror du att vi var tvungna att göra det? [Sam] Varje första är bara tillbaka q.strings [q.head]? >> Ja. >> Eftersom vi gör detta byte av q.head Med MOD-funktionen, och det finns inget sätt att göra det inom returledningen också. [Hardison] Exakt. Du är plats på. Sam är plats helt på. Anledningen till att vi var tvungna att dra ut det första elementet i vår kö och lagra den i en variabel beror denna linje där vi bara hade q.head, finns det mod operatören i det är inte något som vi kan göra och har tar det effekt på huvudet utan - på en rad. Så vi har faktiskt dra ut det första elementet och justera huvudet, justera storleken och sedan tillbaka det element som vi drog ut. Och detta är något som vi får se komma senare med länkade listor, som vi leka med dem. Ofta när du frigör eller göra sig av länkade listor du behöver komma ihåg nästa element, nästa pekare för en länkad lista innan du kasserar den nuvarande. Eftersom annars kasta bort information om vad som finns kvar i listan. Nu, om du går till din apparat, öppnar du upp queue.c--x av detta. Så om jag öppnar queue.c, låt mig zooma in här, du ser att du har en liknande utseende fil. Liknande utseende fil till vad vi hade tidigare med stack.c. Vi har vår struct för kön definieras på samma sätt som vi såg på bilderna. 

Vi har vår enqueue funktion som är till för dig att göra. Och vi har dequeue funktion här. Den dequeue funktion i filen ogenomförda, men jag ska lägga tillbaka upp på PowerPoint så att du kan skriva in det, om du vill. Så för de kommande 5 minuter eller så, ni arbeta enqueue vilket är nästan precis motsatsen till avköande. Du behöver inte justera huvudet när du enqueueing, men vad du behöva justera? Storlek. Så när du enqueue förblir huvudet orörda, blir storleken ändras. Men det tar lite - du måste leka med den mod att räkna ut exakt vad indexet det nya elementet ska läggas till. Så jag ska ge er lite, sätta avköa tillbaka upp på bilden, och eftersom ni har frågor, skriker ut dem så att vi kan alla talar om dem som en grupp. Även med den storlek du inte - när du justerar storleken, kan du alltid bara - behöver du mod storlek någonsin? [Daniel] Nej >> Du behöver inte mod storlek, rätt. Eftersom storleken alltid, om Du är - förutsatt att du hantera saker på rätt sätt, storleken kommer alltid att vara mellan 0 och 3. Vart har du att mod när du gör enqueue? [Student] Endast för huvudet. >> Endast för huvudet, precis. Och varför har du att mod alls enqueue? När är en situation där du måste mod? [Student] Om du har grejer på utrymmen, som på utrymmen 1 och 2, och sedan behöver lägga till något till 0. [Hardison] Ja, exakt. Så om ditt huvud pekaren är i slutet, eller om din storlek plus huvudet är större, eller snarare kommer att linda runt kön. 

Så i denna situation som vi har här uppe på bilden just nu, om jag vill köa något just nu, Vi vill köa något på index 0. Så om du tittar på var 50 går, och jag kallar enqueue 50, det går ner där på botten. Det går i index 0. Den ersätter "hej" som redan ur kön. [Daniel] du inte ta hand om det i dequeue redan? Varför gör det något med huvudet i enqueue? [Hardison] Åh, så du inte ändrar huvudet, tyvärr. Men du måste använda mod användaren när du öppnar det element som du vill köa när du öppnar nästa element i kön. [Basil] Jag gjorde inte det, och jag fick "framgång" på det. [Daniel] Åh, jag förstår vad du säger. [Hardison] Så du didn't - du gjorde på q.size? [Basil] Ja. Jag bytt sida, gjorde jag ingenting med huvudet. [Hardison] Du egentligen inte behöver återställa huvudet vara något, men när du index till strängar array, har du faktiskt gå vidare och beräkna var nästa elementet är, eftersom withe bunten, var nästa element i din stack alltid vid indexet som motsvarar storleken. Om vi ​​ser tillbaka på vårt stack push-funktion, vi kan alltid plunk i vår nya inslag höger vid index storlek. Medan med kön, kan vi inte göra det för om vi är på denna situation, om vi kö 50 vår nya sträng skulle gå rätt på strängar [1] som vi inte vill göra. Vi vill ha den nya strängen går vid index 0. 

Är det någon - ja? [Student] Jag har en fråga, men det är inte riktigt närstående. Vad betyder det när någon bara ringer något liknande pred pekare? Vad är det namnet kort för? Jag vet att det är bara ett namn. [Hardison] Pred pekare? Låt oss se. I vilket sammanhang? [Student] Det var för insatsen. Jag kan fråga dig senare om du vill eftersom det inte är riktigt relaterade, men jag - [Hardison] Från Davids insats kod från föreläsning? Vi kan dra upp det och prata om det. Vi pratar om det nästa gång vi kommer till länkade listor. 

Så låt oss verkligen snabbt titta på vad enqueue funktionen ser ut. Vad var det första som folk försökt göra i ditt enqueue linje? In i denna kö? Liknar det du gjorde för stack trycka. Vad gjorde du, Stella? [Stella, obegripligt] [Hardison] Exakt. Om (q.size == KAPACITET) - Jag måste lägga min tandställning på rätt plats - returnera false. Zooma in lite. Okej. Nu vad är nästa sak som vi var tvungna att göra? Precis som med stacken, och sätts på rätt plats. Och så vad var det rätt plats att infoga det? Med stapeln var det index storlek, med detta är det inte riktigt så. [Daniel] Jag har q.head--eller - >> q.strings? >> Ja. q.strings [q.head + q.size mod KAPACITET]? [Hardison] Vi vill nog sätta parentes kring detta så att vi får rätt prioritet och så det är cleart för alla. Och ställa det lika? >> Till str? >> Till str. Jättebra. Och nu vad är det sista som vi måste göra? Precis som vi gjorde i stacken. >> Inkrementera storlek? >> Inkrementera storlek. Boom. Och sedan, eftersom startmotorn koden just återvänt falsk som standard, Vi vill ändra detta till true om allt går igenom och allt går bra. Okej. Det är en hel del information för avsnitt. Vi är inte riktigt över. Vi vill prata verkligen snabbt om enstaka-länkade listor. Jag lägger upp detta så att vi kan gå tillbaka till det senare. Men låt oss gå tillbaka till vår presentation för några fler bilder. Så enqueue är TODO, nu har vi gjort det. 

Nu ska vi ta en titt på enstaka-länkade listor. Vi pratade om dessa lite mer i föreläsningen. Hur många av er såg demonstrationen där vi hade folk tafatt pekar på varandra och hålla tal? >> Jag var i den. >> Vad ni tycker? Gjorde det, förhoppningsvis avmystifiera dessa lite? Med en lista, visar det sig att vi tar itu med den här typen som vi kommer att kalla en nod. Medan med kön och stapeln hade vi structs att vi skulle kalla kö i stacken, Vi hade dessa nya kö i stack typer, Här en lista egentligen bara består av ett gäng noder. På samma sätt som strängar är bara en massa tecken alla uppradade bredvid varandra. En länkad lista är bara en nod och en annan nod och en annan nod och en annan nod. Och snarare än att krossa alla noder tillsammans och lagra dem intill varandra allt intill varandra i minnet, ha detta nästa pekare tillåter oss att lagra noderna var som helst, på måfå. Och sedan typ av tråd dem alla tillsammans för att peka från en till nästa. 

Och vad var den stora fördelen att det hade över en array? Under lagring allt intill varandra bara fastnat bredvid varandra? Du minns? Ja? >> Dynamisk minnesallokering? >> Dynamisk minnesallokering i vilken mening? [Student] I att du kan fortsätta att göra det större och du behöver inte flytta hela din uppsättning? [Hardison] Exakt. Så med en array, när du vill sätta ett nytt element i mitten av det, du måste flytta allt för att göra plats. Och som vi pratade om med kön, det är därför vi hålla det framvisaren, så att vi inte ständigt skiftande saker. Därför att blir dyrt om du har en stor uppsättning och du ständigt gör dessa slumpmässiga infogningar. Medan med en lista, allt du behöver göra kasta det på en ny nod, justera tips, och du är klar. Vad suger om det här? Bortsett från det faktum att det är inte så lätt att arbeta med som en array? Ja? [Daniel] Tja, jag antar att det är mycket svårare att komma åt ett specifikt element i den länkade listan? [Hardison] Du kan inte bara hoppa till en godtycklig element i mitten av länkad lista. Hur har du att göra det i stället? >> Du måste gå igenom hela saken. [Hardison] Ja. Du måste gå igenom en i taget, en i taget. Det är en enorm - det är en smärta. Vad är den andra - det finns en annan undergång till detta. [Basil] Du kan inte gå framåt och bakåt? Du måste gå en riktning? [Hardison] Ja. Så hur löser vi det, ibland? [Basil] Dubbelt band listor? >> Exakt. Det finns dubbelt länkade listor. Det finns också - ledsen? 

[Sam] Är det samma som att använda Pred sak som - Jag tänkte bara, är inte det vad det pred sak är? Är inte det i mellan dubbelt och var för sig? [Hardison] Låt oss titta på vad exakt han gjorde. Så här går vi. Här är listan koden. Här har vi predptr, här. Är detta vad du pratade om? Så detta var - han befria en lista och han försöker att lagra en pekare till det. Detta är inte dubbelt, enstaka länkade-listor. Vi kan prata mer om detta senare eftersom detta talar om att frigöra listan och jag vill visa några andra saker först. men det är bara - det är att komma ihåg värdet av PTR [Student] Oh, det föregående pekare? >> Ja. Så att vi sedan kan öka PTR själv innan vi sedan fri vad predptr är. Eftersom vi inte kan fritt PTR och sedan ringa PTR = PTR nästa, eller hur? Det skulle vara dåligt. Så låt oss se, tillbaka till den här killen. 

Den andra dåliga listor är att medan med en array Vi har bara alla element själva staplade bredvid varandra, Här har vi också infört denna pekare. Så det finns en ytterligare bit av minne som vi behöva använda för varje element som vi lagrar i vår lista. Vi får flexibilitet, men det kommer till en kostnad. Den levereras med denna tid kostnad, och det kommer med detta minne kostar också. Tid i den meningen att vi nu måste gå igenom varje element i arrayen att hitta en på index 10, eller som skulle ha varit index 10 i en array. 

Bara riktigt snabbt, när vi diagram ut dessa listor, vanligtvis vi håller fast vid huvudet av listan eller den första pekaren i listan och notera att detta är en sann pekare. Det är bara 4 byte. Det är inte en verklig nod själv. Så du ser att den inte har int värde i det, ingen nästa pekare i den. Det är bokstavligen bara en pekare. Det kommer att peka på något som är en verklig nod struct. [Sam] En pekare som kallas nod? >> Det här är - nej. Detta är en pekare till något av typ nod. Det är en pekare till en nod struct. >> Åh, okej. Diagrammet till vänster, kod till höger. Vi kan ställa in den till noll, vilket är ett bra sätt att börja. När du diagrammet, skriver du antingen det som null eller du lägger en linje genom det så. 

Ett av de enklaste sätten att arbeta med listor, och vi ber er göra både prefix och lägg se skillnaderna mellan de två, men prepending är definitivt lättare. När du lägger du, det är här du - när du prepend (7), du går och skapa noden struct och du först peka på den, för nu, eftersom vi till före det, det kommer att bli i början av listan. Om vi ​​prepend (3), som skapar en annan nod, men nu 3 kommer före 7. Så vi huvudsakligen driver saker på vår lista. Nu kan du se att prepend, ibland människor kallar det skjuta, eftersom du driver ett nytt element på din lista. Det är också lätt att ta bort på framsidan av en lista. Så att folk kommer ofta kalla det pop. Och på det sättet kan du emulera en bunt med en länkad lista. Hoppsan. Tyvärr, nu vi får in append. Så här har vi till före (7), nu har vi prepend (3). Om vi ​​till före något annat på denna lista, om vi till före (4), då skulle vi ha 4 och sedan 3 och sedan 7. Så vi kunde pop och ta bort 4, ta bort 3, ta bort 7. Ofta mer intuitivt sätt att tänka på detta är med append. Så jag har schematiskt vad det skulle se ut med lägga här. Här bifogas (7) inte ser något annorlunda eftersom det finns bara ett element i listan. Och bifoga (3) uttrycker det på slutet. Kanske kan du se just nu tricket med append är att eftersom vi bara vet var i början av listan är, som ska läggas till en lista måste du gå hela vägen igenom listan för att komma till slutet, stoppa sedan bygga din nod och Plunk allt. Koppla alla grejer upp. Så med prepend, som vi slet bara genom detta verkligen snabbt, när du lägger du till en lista, det är ganska enkelt. 

Du gör din nya nod innebära några dynamisk minnesallokering. Så här gör vi en nod struct med malloc. Så malloc vi använder eftersom det kommer att avsätta minne för oss för senare eftersom vi inte vill att detta - vi vill detta minne för att bestå under en lång tid. Och vi får en pekare till utrymme i minnet att vi bara tilldelade. Vi använder storlek nod blir slutsumman vi inte fälten. Vi inte manuellt generera antalet byte, istället använder vi sizeof så att vi vet att vi får rätt antal byte. Vi ser till att testa att våra malloc samtal lyckades. Detta är något du vill göra i allmänhet. På moderna maskiner, slut på minne är inte något som är lätt om du inte är fördela massor av saker och göra en enorm lista, men om du bygger saker för, säg, som en iPhone eller en Android, du har begränsade minnesresurser, speciellt om du gör något intensiv. Så det är bra att komma i praktiken. 

Observera att jag använt ett par olika funktioner här att du har sett som är typ av nya. Så fprintf är precis printf utom det första argumentet är den ström som du vill skriva ut. I det här fallet vill vi skriva ut till standard fel strängen som skiljer sig från den vanliga outstream. Som standard visas upp på samma plats. Den skriver också ut till terminalen, men du kan - använder dessa kommandon du lärt dig om de omdirigering teknik du lärt dig om i Tommys video för problembild 4 kan du styra den till olika områden, och sedan avsluta, just här, avslutar ditt program. Det är i huvudsak som återvänder från centrala, utom vi använder exit för här avkastning inte kommer att göra något. Vi är inte i main, inte avsluta så återvänder inte programmet som vi vill ha. Så använder vi avfarten funktionen och ge den en felkod. Så här vi satt den nya noden värde fältet, dess Jag fältet vara lika med i, och vi koppla upp det. Vi sätter den nya noden nästa pekare att peka på först, och sedan först kommer nu pekar på den nya noden. Dessa första rader kod, vi bygger faktiskt den nya noden. Inte de två sista raderna i denna funktion, men de första. Du kan faktiskt dra ut i en funktion, till en hjälpare funktion. Det är ofta det jag gör är, dra jag ut den i en funktion, Jag kallar det något i stil med bygga nod, och som håller prefix funktionen ganska små, det är bara 3 rader då. Jag ringer till min bygga nod-funktion, och sedan jag tråd allting. 

Det sista jag vill visa dig, och jag ska låta dig göra append och allt som på egen hand, är hur man iterera över en lista. Det finns en massa olika sätt att iterera över en lista. I det här fallet kommer vi att hitta längden på en lista. Så vi börjar med längd = 0. Detta är mycket likt skriva strlen efter en sträng. Detta är vad jag vill visa dig, detta för slinga här. Det ser ganska funky, det är inte de vanliga int i = 0, i <vad som helst, i + +. Istället är initiering vår variabeln n att vara början av listan. Och sedan när vi iterator variabel inte är null, håller vi igång. Detta beror, enligt konvention, kommer i slutet av vår lista vara null. Och sedan att öka, snarare än att göra + +, den länkade listan motsvarande + + är N = N-> nästa. 

Jag ska låta dig fylla i luckorna här eftersom vi är för sent. Men ha detta i åtanke när du arbetar på din spellr psets. Länkade listor, om du genomföra en hash-tabell, kommer definitivt komma väl till pass. Och med detta formspråk för looping över saker kommer att göra livet mycket enklare, förhoppningsvis. Har du frågor, snabbt? [Sam] Kommer ni att skicka ut den ifyllda SLL och SC? [Hardison] Ja. Jag skickar ut färdiga bilder och avslutade SLL stack och queue.cs. [CS50.TV]