[Powered by Google Translate] [§ 6: Mindre Komfortabel] [Nate Hardison] [Harvard University] [Dette er CS50.] [CS50.TV] OK. Velkommen til § 6. Denne uken skal vi snakke om datastrukturer i snitt, først og fremst fordi denne ukens problem satt på spellr gjør en hel haug med forskjellige data struktur leting. Det er en haug med forskjellige måter du kan gå med problemet sett, og jo flere datastrukturer du vet om, de mer kule ting du kan gjøre. 

Så la oss komme i gang. Først skal vi snakke om stabler, bunken og kø datastrukturer som vi kommer til å snakke om. Stabler og køer er virkelig nyttig når vi begynner å snakke om grafer, som vi ikke kommer til å gjøre så mye av akkurat nå. Men de er veldig bra å forstå en av de store fundamentale datastrukturer i CS. Beskrivelsen i oppgavesettet spesifikasjonen, Hvis du drar den opp, snakker om stabler beslektet med bunken av spisesteder skuffer som du har i kantina på spisesalene der når dining personalet kommer og setter dining skuffer ut etter at de har renset dem, de stable dem oppå hverandre. Og så når barna kommer i å få mat, de trekker skuffene ut, først den øverste, så den under det, deretter en under det. Så, i kraft, er den første skuffen som dining personalet legger ned den siste som blir tatt av. Den siste som dining personalet satt på er den første som blir tatt av til middag. I oppgavesettet er spec, som du kan laste ned hvis du ikke allerede har gjort, vi snakker om modellering en stabel data stucture bruker denne typen struct. 

Så det vi har her, er dette likt det som ble presentert i foredraget, bortsett fra i foredraget presenterte vi dette med ints i motsetning til char * s. Dette kommer til å bli en stabel som lagrer hva? Daniel? Hva er vi lagrer i denne bunken? [Daniel] Strings? >> Vi lagrer strenger i denne bunken, akkurat. Alt du trenger å ha for å skape en stabel er en matrise av en bestemt kapasitet, som i dette tilfellet, Kapasiteten skal være i store bokstaver fordi det er en konstant. Og da i tillegg til matrisen, alt vi trenger å spore gjeldende størrelsen på matrisen. En ting å merke seg her som er litt kult er at vi skaper den stablet datastrukturen på toppen av en annen datastruktur, matrisen. Det er forskjellige måter å implementere stabler. Vi vil ikke gjøre det helt ennå, men forhåpentligvis etter å gjøre den koblede-liste problemer, vil du se hvordan du enkelt kan implementere en bunke på toppen av en lenket liste også. Men for nå, vil vi holde oss til arrays. Så igjen, er alt vi trenger en matrise og vi trenger bare å spore størrelsen på tabellen. [Sam] Beklager, hvorfor er det at du sa bunken er på toppen av strengene? For meg virker det som strengene er i stabelen. [Hardison] Yeah. Vi skaper, vi tar vårt utvalg datastruktur - det er et stort spørsmål. Så spørsmålet er hvorfor, for folk som ser dette på nettet, hvorfor vi sier at bunken er på toppen av strengene, fordi her ser det ut som strengene er inne i bunken? Som er helt tilfelle. Hva jeg siktet til var at vi har fått en rekke data struktur. Vi har fått en rekke char * s, denne rekke strenger, og vi kommer til å legge til at for å skape den stablet datastruktur. 

Så en stabel er litt mer komplisert enn en matrise. Vi kan bruke en matrise for å bygge en stabel. Så det er der vi sier at bunken er bygget på toppen av en matrise. Likeledes, som jeg sa tidligere, kan vi bygge en stabel på toppen av en lenket liste. Istedenfor å bruke en matrise for å holde våre elementer, vi kunne bruke en lenket liste for å holde våre elementer og bygge stabelen rundt det. La oss gå gjennom et par eksempler, se på noen kode, å se hva som faktisk skjer her. På venstre side, har jeg kastet ned hva som stakk struct ville se ut i minnet hvis kapasiteten ble # definert å være fire. Vi har våre fire-element char * array. Vi har strenger [0], strenger [1], strenger [2], strenger [3], og deretter den siste plassen for vår størrelse heltall. Betyr dette fornuftig? Okay. Dette er hva som skjer hvis det jeg gjør på høyre side, som vil være min kode, er å bare erklære en struct, et stablet struct heter s. Dette er hva vi får. Den legger ned denne fotavtrykk i minnet. Det første spørsmålet her er hva som er innholdet i denne bunken struct? Akkurat nå er de ingenting, men de er ikke helt ingenting. De er denne slags søppel. Vi har ingen anelse om hva som er i dem. Når vi erklærer stable s, vi bare kaster det ned på toppen av minne. Det er typen som å erklære int i og ikke initialisere den. Du vet ikke hva som er der. Du kan lese hva som er der, men det kan ikke være super nyttig. En ting du ønsker å alltid huske å gjøre er initialisere hva må initialiseres. I dette tilfellet skal vi initialisere størrelsen til å være null, fordi det kommer til å vise seg å være svært viktig for oss. Vi kunne gå videre og starte alle pekere, alle char * s, å være noen forståelig verdi, sannsynligvis null. Men det er ikke helt nødvendig at vi gjør det. 

Nå, de to viktigste operasjoner på stabler er? Noen som husker fra foredraget hva du gjør med stabler? Ja? [Stella] Pushing og spratt? >> Nettopp. Skyve og spratt er de to viktigste operasjoner på stabler. Og hva gjør push? >> Det setter noe på toppen av stabelen, og deretter dukker det tar av. [Hardison] Nettopp. Så presser presser noe på toppen av bunken. Det er som servering personalet å sette en spisestue skuff ned på disken. Og spratt tar en spisestue skuff ut av bunken. La oss gå gjennom et par eksempler på hva som skjer når vi skyver ting inn i bunken. Hvis vi skulle presse strengen 'Hei' på stacken, Dette er hva vår diagram ville se ut nå. Se hva som skjer? Vi presset inn i det første element i strenger matrise og vi upped vår størrelse teller for å være en. Så hvis vi ser på forskjellen mellom de to lysbilder, her var 0, her før push. Her er etter push. Før push, etter push. Og nå har vi ett element i stacken. Det er strengen "hallo", og det er det. Alt annet i rekken, i vår strenger array, er fortsatt søppel. Vi har ikke initialisert den. La oss si at vi skyver en annen streng på stacken. Vi kommer til å presse "verden" på dette tidspunktet. Så du kan se "verden" her går på toppen av "Hallo", og størrelsen teller går opp til 2. Nå kan vi presse "CS50", og det vil gå på toppen igjen. Hvis vi går tilbake, kan du se hvordan vi presser ting på toppen av bunken. Og nå får vi til pop. Når vi popped noe ut av bunken, skjedde det? Noen se forskjellen? Det er ganske subtil. [Student] Størrelsen. >> Ja, endret størrelse. 

Hva annet vil du ha forventet å endre? [Student] Strengene, også. >> Høyre. Strengene også. Det viser seg at når du gjør det på denne måten, fordi vi ikke kopiere elementer i stacken, vi faktisk ikke trenger å gjøre noe, vi kan bare bruke størrelse å holde oversikt over hvor mange ting i matrisen vår slik at når vi pop igjen, igjen vi bare minske vår størrelse ned til 1. Det er ingen grunn til å faktisk gå inn og overskrive noe. Slags funky. Det viser seg at vi vanligvis bare la ting alene fordi det er mindre arbeid for oss å gjøre. Hvis vi ikke trenger å gå tilbake og overskrive noe, så hvorfor gjøre det? Så når vi pop dobbelt ut av bunken, er alt som betyr minske størrelsen et par ganger. Og igjen, dette er bare fordi vi ikke kopiere ting i stacken. Ja? Gå fremover. [Student, uforståelig] >> Og hva skjer når du trykker noe igjen? Når du trykker på noe nytt, ikke hvor det gå? Hvor går det, Basil? >> Into strenger [1]? >> Høyre. Hvorfor går det ikke inn strenger [3]? [Basil] Fordi det glemte at det var noe i strenger [1] og [2]? [Hardison] Nettopp. Vår stabelen, i hovedsak, "glemte" at det var å holde på til noe i strenger [1] eller strenger [2], så når vi skyver "woot", det setter bare det inn elementet på strenger [1]. Er det noen spørsmål om hvordan dette fungerer, på et grunnleggende nivå? [Sam] Så dette er ikke dynamisk på noen måte, i forhold til mengden eller i form av størrelsen på bunken? [Hardison] Nettopp. Dette er - poenget var at dette ikke var en dynamisk growning stack. Dette er en stabel som kan holde, på det meste, fire char * s, på de fleste fire ting. Hvis vi skulle prøve og presse en femte tingen, hva tror du bør skje? [Studenter, uforståelige] [Hardison] Nettopp. Det finnes en rekke ting som kan skje. Det kan muligens SEG feil, avhengig av hva vi var - hvordan akkurat vi implementere back-end. Det kan overskrive. Det kunne ha som buffer overflow som vi snakket om i klassen. Hva ville være den mest åpenbare ting som kan overskrives hvis vi prøvde å presse en ekstra ting på stacken? Så du nevnte en buffer overflow. Hva kan være ting som ville bli skrevet over eller tråkket på hvis vi overflyt uhell ved å prøve å presse en ekstra ting? [Daniel, uforståelig] >> mulig. Men i utgangspunktet, hva kan skje? Hva om vi prøvde å presse en fjerde ting? Det kan overskrive størrelse, minst med dette minnet diagram som vi har. 

I oppgavesettet spesifikasjonen, som er hva vi kommer til å gjennomføre i dag, hva vi ønsker å gjøre er å returnere bare falsk. Vår trykk metoden kommer til å returnere en boolsk verdi, og at boolean verdi vil være sant hvis push lykkes og usann hvis vi ikke kan skyve noe mer fordi bunken er full. La oss gå gjennom en liten bit av den koden akkurat nå. Her er vår push-funksjon. Vår trykk-funksjon for en stabel kommer til å ta i strengen til å sette på stakken. Det kommer til å returnere true hvis strengen var vellykket presset på stabelen og falske ellers. Noen forslag på hva som kan være en god første tingen å gjøre her? [Sam] Hvis størrelsen er lik kapasiteten, return false? [Hardison] Bingo. Fin jobb. Hvis størrelsen er kapasiteten, vi kommer til å returnere falsk. Vi kan ikke sette noe mer i stacken. Ellers ønsker vi å sette noe på toppen av bunken. Hva er "toppen av bunken," i utgangspunktet? [Daniel] Størrelse 0? >> Størrelse 0. Hva er toppen av stabelen etter at det er én ting i bunken? Missy, vet du det? [Missy] One. >> Størrelsen er én, akkurat. Du holde legge til størrelse, og hver gang du setter i den nye element på indeksen størrelsen på tabellen. Vi kan gjøre det med den slags one-liner, hvis det er fornuftig. Så vi har fått vår strenger array, vi kommer til å få tilgang til den på størrelsen indeksen, og vi bare kommer til å lagre våre char * der. Legg merke til hvordan det har ingen streng kopiering skjer i her, ingen dynamisk tildeling av minne? Og så Missy brakt opp det vi nå har å gjøre, fordi vi har lagret strengen på riktig sted i tabellen, og hun sa at vi måtte øke størrelsen ved en slik at vi er klare for neste push. Så vi kan gjøre det med s.size + +. På dette punktet har vi presset inn i matrisen vår. Hva er det siste vi trenger å gjøre? [Student] Tilbake sant. >> Tilbake sant. Så det er ganske enkelt, en ganske enkel kode. Ikke for mye. Når du har pakket hodet rundt hvordan stabelen fungerer, dette er ganske enkel å implementere. 

Nå er neste del av denne spratt en streng ut av bunken. Jeg kommer til å gi dere litt tid til å jobbe med dette litt. Det er nesten essensielt det motsatte av hva vi har gjort her i push. Hva jeg har gjort er faktisk - oops. Jeg har startet opp et apparat over her, og i apparatet, Jeg har trukket opp problemet satt 5-spesifikasjonen. Hvis vi zoome inn her, kan vi se jeg er på cdn.cs50.net/2012/fall/psets/pset5.pdf. Har dere lastet ned denne koden som er plassert her, section6.zip? OK. Hvis du ikke har gjort det, gjøre det akkurat nå, veldig raskt. Jeg skal gjøre det i mitt terminal vindu. Jeg faktisk gjorde det her oppe. Ja. Ja, Sam? >> Jeg har et spørsmål om hvorfor sa du s.string 's parentes av size = str? Hva er str? Er det definert et sted før, eller - oh, i char * str? [Hardison] Ja, akkurat. Det var argumentet. >> Å, greit. Unnskyld. [Hardison] Vi spesifiserer strengen å presse i. Det andre spørsmålet som kan komme opp at vi ikke egentlig snakke om her var vi tok for gitt at vi hadde denne variabelen kalt s som var i omfang og tilgjengelig for oss. Vi tok for gitt at s var denne bunken struct. Så ser tilbake på dette push-kode, du kan se at vi gjør ting med denne strengen som ble vedtatt i men da plutselig, vi tilgang s.size, som, hvor kom s kommer fra? I koden som vi kommer til å se på i avsnittet arkivet og deretter ting som du skal gjøre i ditt problem setter, vi har gjort vår stabelen struct en global variabel slik at vi kan ha tilgang til den i alle våre ulike funksjoner uten å måtte manuelt passerer det rundt og gi det ved henvisning, gjøre alt den slags ting til det. Vi bare juks litt, om du vil, for å gjøre ting bedre. Og det er noe vi gjør her fordi det er for moro, er det lettere. Ofte vil du se folk gjøre dette hvis de har en stor datastruktur som blir operert på i sitt program. 

La oss gå tilbake over til apparatet. Fikk alle med hell få section6.zip? Alle pakk den med unzip section6.zip? Hvis du går inn i § 6 katalog - aah, over alt - og du liste over hva som er her, ser du at du har tre forskjellige. c-filer. Du har en kø, en sll, som er enkeltvis-lenket liste, og en stabel. Hvis du åpner opp stack.c, du kan se at vi har fått denne struct definert for oss, den eksakte struct at vi bare snakket om i lysbildene. Vi har fått vår globale variable for stabelen, vi har fått vår push-funksjon, og så har vi vår pop-funksjon. Jeg skal sette inn koden for skyver opp på lysbildet her, men det jeg ønsker dere å gjøre er, etter beste evne, gå og gjennomføre pop-funksjonen. Når du har installert den, kan du kompilere dette med at bunken, og deretter kjøre den resulterende stabelen kjørbar, og som vil kjøre alle denne testen koden her nede som er i main. Og viktigste tar seg av faktisk gjør push og pop samtaler og sørge for at alt går gjennom all right. Det initialiserer også stakkstørrelsen her slik at du ikke trenger å bekymre deg initialisering det. Du kan anta at det har vært riktig initialisert av den tiden du tilgang til den i pop-funksjonen. Gjør det fornuftig? Så her går vi. Det er push-koden. Jeg skal gi dere 5 eller 10 minutter. Og hvis du har noen spørsmål i mellomtiden mens du koder, kan du be dem høyt. Så hvis du kommer til et fast punkt, bare spør. Gi meg beskjed, la alle andre vet. Arbeid med din nabo også. [Daniel] Vi bare implementere pop akkurat nå? >> Bare pop. Selv om du kan kopiere gjennomføringen av push hvis du ønsker slik at testing vil fungere. Fordi det er vanskelig å teste ting å komme inn - eller, er det vanskelig å teste spratt ting ut av en stabel hvis det ikke er noe i bunken til å begynne med. 

Hva er pop ment å være tilbake? Elementet fra toppen av stabelen. Det er ment å få elementet ut av toppen av stabelen og deretter minske størrelsen av stabelen, og nå har du mistet elementet på toppen. Og så kan du returnere element på toppen. [Student, uforståelig] [Hardison] Så hva skjer hvis du gjør det? [Student, uforståelig] Hva ender opp som skjer er du sannsynligvis få tilgang enten et element som ikke har blitt initialisert ennå, slik at beregningen hvor det siste elementet er er av. Så her hvis du merker, i push, vi tilgang strenger på s.size element fordi det er en ny indeks. Det er den nye toppen av bunken. Mens det i pop, er s.size kommer til å bli den neste plassen, plassen som er på toppen av alle elementene i stabelen din. Så den øverste elementet er ikke på s.size, men heller, det under den. 

Den andre tingen å gjøre når du - i pop, er du nødt til å minske størrelsen. Hvis du husker tilbake til vår lille diagrammet akkurat her, egentlig, det eneste som vi så skjer når vi kalte pop var at denne størrelsen droppet, først til 2, og deretter til en. Så når vi presset et nytt element på, ville det gå på på riktig sted. [Basil] Hvis s.size er to, så ville det ikke gå til element 2, og deretter du ønsker å pop som element av? Så hvis vi gikk til - >> Så la oss se på dette på nytt. Hvis dette er vårt stabelen på dette punktet og vi kaller pop, hvor indeksen er den øverste element? [Basil] På 2, men det kommer til å dukke 3. >> Høyre. Så det er der vår størrelse er 3, men vi ønsker å komme elementet på indeks 2. Det er den typiske slags av av en som du har med null-indeksering av arrays. Så du ønsker å pop tredje elementet, men det tredje elementet er ikke på indeksen 3. Og grunnen til at vi ikke trenger å gjøre det minus 1 når vi presser er fordi akkurat nå, merker du at den øverste element, hvis vi skulle presse noe annet på bunken på dette punktet, vi ønsker å presse det på indeksen 3. Og det bare skjer, slik at størrelsen og indeksene stille opp når du presser. 

Hvem har en fungerende stack gjennomføringen? Du har en fungerende stabel ett. Har du pop fungerer ennå? [Daniel] Ja. Jeg tror det. >> Program kjører og ikke SEG forkastninger, det skriver ut? Betyr skrive det ut "suksess" når du kjører det? Ja. Gjør stable kjøre den, hvis det skrives ut "suksess" og ikke går bom, så alt er bra. OK. La oss gå over til apparatet veldig raskt, og vi vil gå gjennom dette. Hvis vi ser på hva som skjer her med pop, Daniel, hva var det første du gjorde? [Daniel] Hvis s.size er større enn 0. [Hardison] Okay. Og hvorfor gjorde du det? [Daniel] For å være sikker på at det var noe inni bunken. [Hardison] Høyre. Du ønsker å teste for å være sikker på at s.size er større enn 0; ellers, hva du ønsker å ha skje? [Daniel] Return null? >> Return null, akkurat. Så hvis s.size er større enn 0. Så hva skal vi gjøre? Hva gjør vi hvis bunken ikke er tom? [Stella] Du minske størrelsen? Minske Du >> størrelse, greit. Så hvordan gjorde du det? >> S.size--. [Hardison] Great. Og hva gjorde du? [Stella] Og så sa jeg tilbake s.string [s.size]. [Hardison] Great. Ellers kan du returnere null. Ja, Sam? [Sam] Hvorfor det ikke trenger å være s.size + 1? [Hardison] Plus 1? >> Ja. >> Fikk det. [Sam] Jeg trodde fordi du tar en ut, så du kommer til å komme tilbake ikke den som de ba om. [Hardison] Og dette var akkurat hva vi snakket om med hele denne saken av 0 indeksene. Så hvis vi zoome tilbake over her. Hvis vi ser på denne fyren her, kan du se at når vi pop, vi dukker elementet på indeks 2. 

Så vi redusere vår størrelse først, og deretter vår størrelse passer vår indeks. Hvis vi ikke minske størrelsen først, så må vi gjøre størrelsen -1 og deretter minking. Flott. All good? Eventuelle spørsmål om dette? Det finnes en rekke forskjellige måter for å skrive dette også. Faktisk kan vi gjøre noe selv - vi kan gjøre en one-liner. Vi kan gjøre en en-linje retur. Så vi kan faktisk minske før vi kommer tilbake ved å gjøre det. Så setter - før s.size. Det gjør linjen virkelig tett. Hvor forskjellen mellom den -. S størrelse og s.size-- er at dette postfix - de kaller det postfix fordi - kommer etter s.size-- betyr at s.size vurderes i forbindelse med å finne indeksen som det er tiden når denne linjen er utført, og deretter dette - skjer etter linjen blir henrettet. Etter elementet på indeksen s.size åpnes. Og det er ikke det vi ønsker, fordi vi ønsker reduksjonen skal skje først. Othewise, vi kommer til å være tilgang til array, effektivt, ut over grensene. Vi kommer til å være tilgang til elementet over den som vi faktisk ønsker å få tilgang til. Ja, Sam? >> Er det raskere eller bruke mindre RAM å gjøre på én linje eller ikke? [Hardison] Ærlig talt, det avhenger egentlig. [Sam, uforståelig] >> Ja, det kommer an. Du kan gjøre kompilatoren triks å få kompilatoren til å erkjenne at, vanligvis, tenker jeg. 

Så vi har nevnt litt om dette kompilatoren optimalisering ting at du kan gjøre i kompilering, og det er den type ting som en kompilator kan være i stand til å finne ut, som oh, hei, kanskje jeg kan gjøre alt dette i én operasjon, i motsetning til lasting størrelsen variabel i fra RAM, decrementing det, lagre den ut igjen, og deretter legger det inn igjen å behandle resten av denne operasjonen. Men typisk, nei, dette er ikke den slags ting som kommer til å gjøre programmet betydelig raskere. Eventuelle flere spørsmål om stabler? 

Så presser og spratt. Hvis dere ønsker å prøve ut hacker utgave, hva vi har gjort i hacker utgaven er faktisk borte og gjort denne bunken vokse dynamisk. Utfordringen er først og fremst her oppe i push-funksjonen, å finne ut hvordan du gjør denne matrisen vokse som du holde skyve flere og flere elementer på siden av stabelen. Det er faktisk ikke så mye ekstra kode. Bare en oppfordring til - du må huske å få samtaler til malloc der riktig, og deretter finne ut når du skal ringe RealLOC. Det er en morsom utfordring hvis du er interessert. 

Men for tiden, la oss gå videre, og la oss snakke om køer. Bla gjennom her. Køen er en nær søsken av stabelen. Så i bunken, var ting som satt i sist var de første tingene å deretter bli hentet. Vi har fått denne sist inn, først ut, eller LIFO, bestilling. Mens i køen, som du forventer fra når du står i kø, den første personen til å komme på linje, den første tingen å komme inn i køen, er det første som blir hentet fra køen. Køer er også ofte brukt når vi arbeider med grafer, som vi snakket om kort med stabler, og køene er også praktisk for en haug med andre ting. En ting som kommer opp ofte forsøker å opprettholde f.eks en sortert liste over elementer. Og du kan gjøre dette med en matrise. Du kan opprettholde en sortert liste over ting i en matrise, men der det blir vanskelig da du alltid må finne riktig sted å sette den neste tingen. Så hvis du har en rekke tall, fra 1 til 10, og så du vil utvide det til alle tallene 1 til 100, og du får disse tallene i tilfeldig rekkefølge og prøver å holde alt sorteres som du går gjennom, vil du ende opp med å gjøre mye giring. Med visse typer køer og enkelte typer underliggende datastrukturer, du kan faktisk holde det ganske enkelt. Du trenger ikke å legge noe og deretter stokke hele greia hver gang. Heller ikke har du å gjøre mye giring av de interne elementene rundt. Når vi ser på en kø, ser du at - også i queue.c i delkoden - struct som vi har gitt deg er veldig lik den struct at vi ga deg for en stabel. 

Det er ett unntak til dette, og at ett unntak er at vi har denne ekstra heltall kalles hodet, og hodet her er for å holde orden på hodet av køen, eller det første elementet i køen. Med en stabel, var vi i stand til å holde orden på element som vi var i ferd med å hente, eller toppen av bunken, med bare størrelsen, mens med en kø, vi måtte håndtere motsatte ender. Vi prøver å tråkle ting på på slutten, men da returnere ting fra forsiden. Så effektivt, med hodet, har vi indeksen av begynnelsen på køen, og størrelsen gir oss indeksen av slutten av køen slik at vi kan hente ting fra hodet og legge ting til halen. Mens med bunken, var vi kun har å gjøre med toppen av bunken. Vi har aldri hatt tilgang til bunnen av bunken. Vi bare lagt ting til toppen og tok ting ut av toppen slik at vi ikke trenger den ekstra felt inne struct vår. Betyr det generelt fornuftig? OK. Ja, Charlotte? [Charlotte, uforståelig] [Hardison] Det er et stort spørsmål, og det var en som kom opp i foredraget. Kanskje vandre gjennom noen eksempler vil illustrere hvorfor Vi ønsker ikke å bruke strenger [0] som leder av køen. 

Så forestille seg at vi har vår kø, skal vi kalle det kø. I begynnelsen, når vi nettopp har instansiert det, når vi har nettopp erklært det, har vi ikke initialisert noe. Det er alt søppel. Så selvfølgelig ønsker vi å sørge for at vi initialisere både størrelsen og hodet feltene å være 0, noe fornuftig. Vi kan også gå videre og null ut elementene i kø vår. Og for å gjøre dette diagrammet passform, legge merke til at nå er vår køen kan bare holde tre elementer; mens vår stabelen kunne holde fire, kan vår køen bare holde tre. Og det er bare å gjøre diagrammet passform. Det første som skjer her er vi Enqueue strengen "Hei". Og akkurat som vi gjorde med bunken, noe veldig annerledes her, vi kaster strengen på på strenger [0] og øke vår størrelse med en. Vi Enqueue "bye", blir det satt på. Så dette ser ut som en stabel for det meste. Vi startet her, nytt element, nytt element, holder størrelsen går opp. Hva skjer på dette punktet når vi ønsker å dequeue noe? Når vi ønsker å dequeue, som er den delen som vi ønsker å dequeue? [Basil] Strings [0]. >> Zero. Helt riktig, Basil. Vi ønsker å bli kvitt den første strengen, denne, "Hei". Så hva var den andre tingen som endret? Legger merke til når vi popped noe ut av bunken, vi bare endret størrelse, men her har vi et par ting som endring. Ikke bare størrelsen endres, men hodet endringer. Dette kommer tilbake til Charlottes punkt tidligere: hvorfor har vi dette hodet også? Betyr det fornuftig nå, Charlotte? >> Kind of. [Hardison] Kind of? Så hva som skjedde da vi dequeued? Hva gjorde hodet gjøre det nå er interessant? [Charlotte] Oh, fordi det endret - OK. Jeg skjønner. Fordi hodet - der hodet peker til endringer i forhold til plasseringen. Det er ikke lenger alltid null indeksen ett. >> Ja, akkurat. Det som skjedde var om dequeueing høy element ble gjort og vi har ikke dette hodet feltet fordi vi var alltid ringer denne strengen på 0-indeksen leder av køen vår, da ville vi nødt til å skifte resten av køen ned. Vi måtte skifte "bye" fra strenger [1] til strengene [0]. Og strenger [2] ned til strenger [1]. Og vi måtte gjøre dette for hele listen over elementer, hele matrisen av elementer. Og når vi gjør dette med en matrise, blir det virkelig dyrt. Så her er det ikke en stor avtale. Vi har tre elementer i matrisen vår. Men hvis vi hadde en kø av tusen elementer eller en million elementer, og deretter plutselig, begynner vi å lage en haug med dequeue kaller alt i en loop, ting virkelig kommer til å avta når det skifter alt ned hele tiden. Du vet, skifte av 1, skift med 1, skift med 1, skift av en. I stedet bruker vi dette hodet, vi kaller det en "peker" selv om det er egentlig ikke en peker i streng forstand, det er ikke en peker type. Det er ikke en int * eller en char * eller noe sånt. Men den peker eller viser hodet av køen vår. Ja? 

[Student] Hvordan vet dequeue å bare stikke av alt som er på hodet? [Hardison] Hvordan vet dequeue hvordan å løsne alt som er på hodet? >> Høyre, ja. >> Hva det er å se på er akkurat hva hodet feltet er satt til. Så i dette første tilfellet, hvis vi ser her, vårt hode er 0, indeks 0. >> Høyre. [Hardison] Så det bare sier greit, vel, elementet på indeks 0, strengen "hei", er elementet på hodet av køen vår. Så vi kommer til å dequeue den fyren. Og det vil være element som blir returnert til den som ringer. Ja, Saad? >> Så hodet setter i utgangspunktet den - der du kommer til å indeksere den? Det er starten på det? >> Ja. >> Ok. [Hardison] Det er å bli den nye starten for array vår. Så når du dequeue noe, er alt du trenger å gjøre tilgang til elementet på indeks q.head, og som vil være element som du vil dequeue. Du må også minske størrelsen. Vi får se i litt der ting blir litt vanskelig med dette. Vi dequeue, og nå, hvis vi Enqueue igjen, hvor Enqueue vi? Hvor går neste element i køen vårt? Si at vi ønsker å Enqueue strengen "CS". Der indeksen vil det gå? [Studenter] Strings [2]. >> Two. Hvorfor 2 og ikke 0? [Basil] Fordi nå hodet er 1, så det er som starten på listen? [Hardison] Høyre. Og hva betegner slutten av listen? Hva skulle vi bruke for å betegne slutten av køen vårt? Hodet er leder av køen vår, begynnelsen av køen vår. Hva er slutten på køen vårt? [Studenter] størrelse. >> Størrelse, akkurat. Så våre nye elementer gå inn på størrelsen, og de elementene som vi tar av kommer av på hodet. Når vi Enqueue det neste elementet, vi setter det på størrelsen. [Student] Før sette deg at i skjønt, størrelse var 1, ikke sant? [Hardison] Høyre. Så ikke helt på størrelse. Størrelse +, ikke en, men + hodet. Fordi vi flyttet alt av hodet beløp. Så her, nå har vi fått en kø av størrelse 1 som begynner på indeks 1. Halen er indeksen 2. Ja? 

[Student] Hva skjer når du dequeue strenger [0], og strengene 'sporene i minnet bare bli tømt, i utgangspunktet, eller bare glemt? [Hardison] Yeah. I denne forstand, vi bare glemme dem. Hvis vi lagret kopier av dem for - mange datastrukturer vil ofte lagrer sine egne kopier av elementene slik at personen som administrerer datastrukturen ikke trenger å bekymre deg om hvor alle disse pekere går. Datastrukturen holder på alt, holder på til alle kopiene, å sørge for at alt fortsetter på riktig måte. Imidlertid, i dette tilfellet, disse datastrukturer bare, for enkelhet, er ikke å lage kopier av noe som vi lagrer i dem. [Student] Så er dette en kontinuerlig rekke -? >> Ja. Hvis vi ser tilbake på hva definisjonen var av denne strukturen, er det. Det er bare en standard utvalg som du har sett, en matrise av char * s. Betyr det -? >> Ja, jeg bare lurte Hvis du vil til slutt gå tom for minne, til en viss grad, Hvis du har alle disse tomme flekker i arrayet? [Hardison] Ja, det er et godt poeng. 

Hvis vi ser på hva som har skjedd nå på dette punktet, Vi har fylt opp vår kø, ser det ut som. Men vi har egentlig ikke fylt opp vår køen fordi vi har en kø som er størrelse 2, men det begynner på indeks 1, fordi det er der vårt hode pekeren er. Som du sa, at element ved strenger [0], på indeks 0, er egentlig ikke det. Det er ikke i kø vår lenger. Vi bare ikke bry å gå inn og overskrive det når vi dequeued det. Så selv om det ser ut som vi har kjørt ut av minnet, har vi virkelig ikke. At stedet er tilgjengelig for oss å bruke. Den aktuelle atferd, hvis vi skulle prøve og første dequeue noe som "bye", som ville pop bye av. Nå vår køen begynner på indeksen 2 og er av størrelse 1. Og nå hvis vi prøver og Enqueue noe nytt, sier 50, 50 bør gå i denne sted på indeks 0 fordi det er fremdeles tilgjengelig for oss. Ja, Saad? [Saad] Skjer det automatisk? [Hardison] Det skjer ikke helt automatisk. Du må gjøre regnestykket å gjøre det arbeidet, men i hovedsak hva vi har gjort er at vi har akkurat pakket rundt. [Saad] Og er det greit hvis dette har et hull i midten av det? [Hardison] Det er hvis vi kan gjøre regnestykket trene riktig. 

Og det viser seg at det er faktisk ikke så vanskelig å gjøre med mod operatør. Så akkurat som vi gjorde med Caesar og krypto ting, bruker mod, kan vi få ting til å vikle rundt og holde det gående rundt og rundt og rundt med kø vår, holde at hodet peker flytte rundt. Legg merke til at størrelsen er alltid respektere antall elementer inne i selve køen. Og det er bare hodet peker som holder sykling gjennom. Hvis vi ser på hva som skjedde her, hvis vi går tilbake til begynnelsen, og du bare se hva som skjer med hodet når vi Enqueue noe, skjedde det ingenting i hodet. Når vi enqueued noe annet, skjedde det ingenting i hodet. Snart vi dequeued noe, går hodet opp med én. Vi enqueued noe, skjer det ingenting mot hodet. Når vi dequeue noe, plutselig hodet blir økes. Når vi Enqueue noe, skjer det ingenting mot hodet. 

Hva ville skje på dette punktet hvis vi skulle dequeue noe igjen? Noen tanker? Hva ville skje med hodet? Hva bør skje med hodet hvis vi skulle dequeue noe annet? Hodet akkurat nå er på indeksen 2, som betyr at hodet av køen er strenger [2]. [Student] som returnerer 0? >> Det bør gå tilbake til 0. Det bør vikle tilbake rundt, akkurat. Så langt, hver gang vi kalte dequeue, har vi vært å legge en til hodet, legg til en i hodet, legge en til hodet, legge en til hodet. Så snart det hodet peker får den siste indeksen i array vår, da må vi bryte den tilbake rundt til begynnelsen, gå tilbake til 0. [Charlotte] Hva bestemmer kapasiteten køen i en stabel? [Hardison] I dette tilfellet har vi bare brukt en # definert konstant. >> Ok. [Hardison] I den faktiske. C-fil, kan du gå inn og møkk med den litt og gjøre den så stor eller så lite som du ønsker. [Charlotte] Så når du gjør det en kø, hvordan du gjør datamaskinen vet hvor stor du vil bunken for å være? [Hardison] Det er et stort spørsmål. Det er et par måter. Det ene er å bare definere det opp foran og si dette kommer til å være en kø som har 4 elementer eller 50 elementer eller 10.000. Den andre måten er å gjøre hva hacker utgave folk gjør og lage funksjoner for å ha din køen vokser dynamisk etter hvert som flere ting bli lagt i. 

[Charlotte] Så å gå med det første alternativet, hva syntaks du bruker å fortelle programmet hva er størrelsen av køen? [Hardison] Ah. Så la oss komme oss ut av dette. Jeg er fortsatt i stack.c her, så jeg skal bare rulle opp til toppen her. Kan du se dette her? Dette er den # define kapasitet 10. Og dette er nesten nøyaktig samme syntaks som vi har for køen. Bortsett fra i kø, har vi det ekstra struct feltet her. [Charlotte] Oh, jeg trodde kapasiteten mente kapasiteten for strengen. [Hardison] Ah. >> At det er den maksimale lengden på ordet. >> Fikk det. Ja. Kapasiteten her - det er et stort poeng. Og dette er noe som er vanskelig fordi det vi har erklært her er en rekke char * s. En rekke pekere. Dette er en rekke tegn. Dette er sannsynligvis det du har sett når du har vært å erklære dine buffere for fil I / O, når du har vært å skape strenger manuelt på stakken. Men hva vi har her er en rekke char * s. Så det er en rekke pekere. Egentlig, hvis vi zoome ut igjen, og vi ser på hva som skjer her i presentasjonen, ser du at den faktiske elementer, tegnet data lagres ikke i matrisen selv. Hva som er lagret i matrisen vår her er pekere til de tegndata. Okay. Så vi har sett hvordan størrelsen på køen er akkurat med bunken, størrelsen respekterer alltid antall elementer som ligger i køen. Etter at to enqueues, er størrelsen 2. Etter at en dequeue størrelsen er nå en. Etter at en annen Enqueue størrelsen er tilbake opptil 2. Slik at størrelsen respekterer definitivt antall elementer i køen, og deretter hodet holder bare sykling. Det går fra 0-1-2, 0-1-2, 0-1-2. Og hver gang vi kaller dequeue, blir hodet pekeren økes til neste indeksen. Og hvis hodet er i ferd med å gå over, looper den tilbake rundt til 0. Så med det, kan vi skrive dequeue funksjonen. Og vi kommer til å forlate Enqueue funksjon for dere å gjennomføre i stedet. 

Når vi dequeue et element ut av køen vår, hva var det første som Daniel gjorde da vi begynte å skrive pop-funksjonen for stabler? La meg høre fra noen som ikke har snakket ennå. La oss se, Saad, husker du hva Daniel gjorde som det første da han skrev pop? [Saad] Det var, var det - >> Han testet for noe. [Saad] Hvis størrelsen er større enn 0. >> Nettopp. Og hva var det testing for? [Saad] Det var testing for å se om det er noe inni tabellen. [Hardison] Yeah. Akkurat. Så du kan ikke komme noe ut av bunken hvis det er tomt. På samme måte kan du ikke dequeue noe fra en kø hvis det er tomt. Hva er det første vi bør gjøre i vår dequeue funksjon her, tror du? [Saad] Hvis størrelsen er større enn 0? >> Ja. I dette tilfellet har jeg faktisk bare testet for å se om det er 0. Hvis det er 0, kan vi returnere null. Men nøyaktig samme logikk. Og la oss fortsette med dette. Hvis størrelsen ikke er 0, der er element som vi ønsker å dequeue? [Saad] På hodet? >> Nettopp. Vi kan bare trekke ut det første elementet i køen vår ved å gå elementet på hodet. Ingenting gale. Etter det, hva skal vi gjøre? Hva må skje? Hva var det andre ting som vi snakket om i dequeue? To ting må skje, fordi vår køen har endret seg. [Daniel] Reduser størrelsen. >> Vi må redusere størrelsen, og øke hodet? Akkurat. Å øke hodet, kan vi ikke bare blindt øke hodet, husker. Vi kan ikke bare gjøre queue.head + +. Vi må også ta med denne mod av kapasiteten. Og hvorfor mod vi med kapasiteten, Stella? [Stella] Fordi det har å vikle rundt. >> Nettopp. Vi mod av kapasiteten fordi den har å vikle tilbake rundt til 0. Så nå, på dette punktet, kan vi gjøre det Daniel sa. Vi kan minske størrelsen. Og så kan vi bare returnere det elementet som var på toppen av køen. Det ser slags gnarly først. Du har kanskje et spørsmål. Beklager? 

[Sam] Hvorfor er først på toppen av køen? Hvor går det? [Hardison] Det kommer fra den fjerde linje fra bunnen. Etter at vi teste for å være sikker på at vår køen ikke er tom, Vi trekker ut char * først, trekker vi ut elementet som sitter på hodet indeksen array vår, vår strenger array, >> og samtale som først? [Hardison] Og vi kaller det første. Ja. Bare for å følge opp at hvorfor tror du vi måtte gjøre det? [Sam] Hver første er bare tilbake q.strings [q.head]? >> Ja. >> Fordi vi gjør dette endring av q.head med mod-funksjonen, og det er ingen måte å gjøre det innenfor returledning også. [Hardison] Nettopp. Du er spot on. Sam er øye helt på. Grunnen til at vi måtte trekke ut det første elementet i køen vår og lagre det i en variabel er fordi denne linjen der vi bare hadde q.head, Det er mod operatør i det ikke er noe som vi kan gjøre og ta det ha effekt på hodet uten - på én linje. Slik at vi faktisk nødt til å trekke ut det første elementet, og deretter justere hodet, justere størrelsen, og deretter returnere element som vi dro ut. Og dette er noe som vi vil se komme opp senere med knyttet lister, som vi spiller rundt med dem. Ofte når du frigjør eller avhending av koblede lister du trenger å huske det neste elementet, neste pekeren over en lenket liste før du kaster den nåværende. Fordi ellers du kaster bort informasjon om hva som er igjen på listen. Nå, hvis du går til apparatet, åpner du opp queue.c--x ut av dette. Så hvis jeg åpner opp queue.c, la meg zoome inn her, vil du se at du har en lignende utseende fil. Lignende utseende fil til hva vi hadde tidligere med stack.c. Vi har fått vår struct for kø som bare er definert som vi så på lysbildene. 

Vi har vår Enqueue funksjon som er for deg å gjøre. Og vi har dequeue funksjon her. Den dequeue funksjon i filen unimplemented, men jeg skal sette den opp igjen på PowerPoint, slik at du kan skrive det inn, hvis du ønsker. Så for de neste 5 minutter eller så, dere jobber på Enqueue som er nesten akkurat det motsatte av dequeue. Du trenger ikke å justere hodet når du enqueueing, men hva har du å justere? Størrelse. Så når du Enqueue, forblir hodet urørt, blir størrelsen endres. Men det tar litt - du må spille rundt med den mod å finne ut nøyaktig hva indeksen det nye elementet skal settes inn på. Så jeg skal gi dere en liten bit, sette dequeue opp på lysbildet, og som dere har spørsmål, rope dem ut slik at vi kan alt snakk om dem som en gruppe. Også med den størrelsen du må få med - når du justere størrelsen, kan du alltid bare - har du å mod størrelsen noensinne? [Daniel] Nei >> Du trenger ikke å mod størrelsen, ikke sant. Fordi størrelsen vil alltid, hvis du har kommet - forutsatt at du administrere ting riktig, størrelsen vil alltid ligge mellom 0 og 3. Hvor har du å mod når du gjør Enqueue? [Student] Bare for hodet. >> Bare for hodet, akkurat. Og hvorfor har du å mod det hele tatt i Enqueue? Når er en situasjon hvor du måtte mod? [Student] Hvis du har ting på områder, som på områder 1 og 2, og deretter måtte legge noe på 0. [Hardison] Nettopp. Så hvis hodet pekeren er helt i enden, eller hvis størrelse pluss hodet er større, eller rettere sagt, kommer til å vikle rundt køen. 

Så i denne situasjonen at vi har her oppe på lysbildet akkurat nå, hvis jeg ønsker å Enqueue noe akkurat nå, vi ønsker å Enqueue noe på indeks 0. Så hvis du ser på hvor de 50 går, og jeg kaller Enqueue 50, det går der nede på bunnen. Det går i indeksen 0. Det erstatter 'Hei' som allerede var dequeued. [Daniel] Tror ikke du tar vare på det i dequeue allerede? Hvorfor gjør det noe med hodet i Enqueue? [Hardison] Oh, slik at du ikke endrer hodet, beklager. Men du må bruke mod operatør når du åpner elementet du vil Enqueue når du åpner neste element i køen. [Basil] Jeg gjorde ikke det, og jeg fikk "suksess" på det. [Daniel] Oh, jeg forstår hva du sier. [Hardison] Så du didn't - du nettopp gjorde på q.size? [Basil] Yeah. Jeg bare byttet side, det gjorde jeg ikke gjøre noe med hodet. [Hardison] Du trenger ikke egentlig trenger å tilbakestille hodet å være noe, men når du indeksen i strenger array, du faktisk nødt til å gå videre og beregne hvor neste element er, fordi withe stabelen, var det neste elementet i stabelen din alltid mot referansepunktet tilsvarende størrelsen. Hvis vi ser tilbake opp på vår stabelen trykk-funksjon, vi kan alltid plunk i vår nye element rett på indeksen størrelse. Mens med køen, kan vi ikke gjøre det fordi hvis vi er på denne situasjonen, hvis vi enqueued 50 vårt nye streng ville gå rett på strenger [1] som vi ikke ønsker å gjøre. Vi ønsker å ha den nye strengen gå på indeks 0. 

Er det noen som - ja? [Student] Jeg har et spørsmål, men det er egentlig ikke i slekt. Hva betyr det når noen bare kaller noe sånt Pred pekeren? Hva er det navnet en forkortelse for? Jeg vet det er bare et navn. [Hardison] Pred pekeren? La oss se. I hvilken sammenheng? [Student] Det var for innsatsen. Jeg kan spørre deg senere hvis du vil fordi det er egentlig ikke relatert, men jeg bare - [Hardison] Fra Davids Sett inn kode fra forelesning? Vi kan trekke det opp og snakke om det. Vi skal snakke om det neste, når vi kommer til koplede listene. 

Så la oss veldig raskt se på hva Enqueue funksjonen ser ut. Hva var det første som folk prøvde å gjøre i din Enqueue linje? Inn i denne køen? I likhet med hva du gjorde for stack presser. Hva gjorde du, Stella? [Stella, uforståelig] [Hardison] Nettopp. If (q.size == KAPASITET) - Jeg trenger å sette mine tannregulering på rett sted - return false. Zoome inn litt. Okay. Nå hva er neste ting som vi måtte gjøre? Akkurat som med bunken, og satt på rett sted. Og så hva var det rette stedet å sette inn det? Med bunken var det indeksen størrelse, med dette er det ikke helt det. [Daniel] Jeg har q.head--eller - >> q.strings? >> Ja. q.strings [q.head + q.size mod KAPASITET]? [Hardison] Vi sannsynligvis ønsker å sette parentes rundt dette slik at vi får riktig prioritet og slik at det er cleart for alle. Og sett at lik? >> For å str? >> Til str. Flott. Og nå hva er det siste at vi har å gjøre? Akkurat som vi gjorde i bunken. >> Øk størrelsen? >> Inkrementere størrelsen. Boom. Og da, siden starteren koden nettopp returnert falsk som standard, vi ønsker å endre dette til true hvis alt går gjennom og alt går bra. OK. Det er mye informasjon for seksjonen. Vi er ikke helt over. Vi ønsker å snakke veldig raskt om enkeltvis-koplede listene. Jeg skal sette opp dette slik at vi kan gå tilbake til det senere. Men la oss gå tilbake til presentasjonen vår for bare noen få flere lysbilder. Så Enqueue er TODO, nå har vi gjort det. 

La oss nå ta en titt på enkeltvis-koplede listene. Vi snakket om disse litt mer i foredraget. Hvor mange av dere så demo der vi hadde folk awkwardly peker til hverandre og holder tall? >> Jeg var i det. >> Hva gjorde dere? Gjorde det, forhåpentligvis avmystifisere disse litt? Med en liste, viser det seg at vi behandler denne typen som vi kommer til å kalle en node. Mens med køen og stakk hadde vi structs at vi vil kalle kø i bunken, Vi hadde disse nye kø i stack typer, her er en liste er egentlig bare består av en haug av noder. På samme måte som strenger er bare en haug med tegn på rekke og rad ved siden av hverandre. En lenket liste er bare en node og en annen node og en annen node og en annen node. Og i stedet for å knuse alle nodene sammen og lagre dem contiguously alle rett ved siden av hverandre i minnet, å ha denne neste pekeren tillater oss å lagre nodene hvor som helst, på måfå. Og deretter slags ledning dem alle sammen for å peke fra den ene til den neste. 

Og hva var den store fordel at dette hadde over en array? Over lagring alt contiguously bare fast ved siden av hverandre? Du husker? Ja? >> Dynamisk minne allokering? >> Dynamisk minne allokering i hvilken forstand? [Student] I det du kan fortsette å lage det større og du trenger ikke å flytte hele array? [Hardison] Nettopp. Så med en matrise, når du ønsker å sette et nytt element inn i midten av den, du må skifte alt for å gjøre plass. Og som vi snakket om med køen, det er derfor vi holder det hode peker, slik at vi ikke stadig skiftende ting. Fordi det blir dyrt hvis du har en stor matrise og du stadig gjør disse tilfeldige innsettinger. Mens med en liste, er alt du trenger å gjøre kaste den på en ny node, justere pekere, og du er ferdig. Hva suger om dette? Bortsett fra det faktum at det er ikke så lett å jobbe med som en matrise? Ja? [Daniel] Vel, jeg antar det er mye vanskeligere å få tilgang til et bestemt element i lenket liste? [Hardison] Du kan ikke bare hoppe til en vilkårlig element i midten av lenket liste. Hvordan har du tenkt å gjøre det i stedet? >> Du må gå gjennom hele greia. [Hardison] Yeah. Du må gå gjennom en av gangen, en om gangen. Det er en stor - det er en smerte. Hva er den andre - det er en annen fall til dette. [Basil] Du kan ikke gå fremover og bakover? Du må gå én retning? [Hardison] Yeah. Så hvordan løser vi det, noen ganger? [Basil] Dobbelt-forbundet lister? >> Nettopp. Det er dobbelt-lenkede lister. Det er også - beklager? 

[Sam] Er det det samme som å bruke Pred ting som - Jeg bare husket, er ikke det hva Pred ting er? Er ikke det i mellom dobbelt og enkeltvis? [Hardison] La oss se på hva han gjorde. Så her går vi. Her er listen koden. Her har vi predptr, her. Er det dette du snakket om? Så dette var - han befri en liste, og han prøver å lagre en peker til den. Dette er ikke dobbelt, enkeltvis knyttet-lister. Vi kan snakke mer om dette senere siden dette er snakk om å frigjøre listen og jeg ønsker å vise noen andre ting først. men det er bare - det er å huske verdien av ptr [Student] Oh, det er foregående pekeren? >> Ja. Slik at vi kan da øke ptr seg før vi deretter gratis hva predptr er. Fordi vi ikke kan fri ptr og deretter ringe ptr = ptr neste, ikke sant? Det ville være dårlig. Så la oss se, tilbake til denne fyren. 

Den andre dårlige ting om lister, er at mens med en rekke vi må bare alle elementene selv stablet ved siden av hverandre, Her har vi også innført denne pekeren. Så det er en ekstra del av minnet som vi måtte bruke for hvert element som vi lagrer i vår liste. Vi får fleksibilitet, men det kommer til en pris. Den kommer med denne gangen kostnader, og det følger med dette minnet pris for. Tid i den forstand at vi nå må gå gjennom hvert element i matrisen å finne en på indeks 10, eller som ville ha vært indeks 10 i en matrise. 

Bare veldig raskt, når vi diagram ut disse listene, typisk vi holder på til leder av listen eller den første pekeren på listen og oppmerksom på at dette er en sann peker. Det er bare 4 bytes. Det er ikke en faktisk node selv. Så du ser at det har ingen int verdi i det, ingen neste pekeren i den. Det er bokstavelig talt bare en peker. Det kommer til å peke på noe som er en faktisk node struct. [Sam] En peker kalt node? >> Dette er - nei. Dette er en peker til noe av type node. Det er en peker til en node struct. >> Å, greit. Diagrammet til venstre, kode til høyre. Vi kan sette den til null, som er en god måte å starte. Når du diagram det, du enten skrive det som null eller du sette en linje gjennom det sånn. 

En av de enkleste måtene å arbeide med lister, og vi ber dere både foranstilt og etterstilt å se forskjellene mellom de to, men prepending er definitivt enklere. Når du foranstille, dette er hvor du - når du setter du (7), du går og lage noden struct og du setter første til å peke på det, fordi nå, siden vi foranstilles det, det kommer til å være i begynnelsen av listen. Hvis vi setter du (3), som skaper en annen node, men nå 3 kommer før 7. Så vi egentlig skyve ting på vår liste. Nå kan du se at foranstilte, noen ganger folk kaller det push, fordi du presser et nytt element på listen din. Det er også lett å slette på forsiden av en liste. Så folk vil ofte kalle det pop. Og på den måten kan du etterligne en stabel med en lenket liste. Whoops. Beklager, nå vi får inn append. Så her er vi foranstilles (7), nå er vi foranstilte (3). Hvis vi foranstilles noe annet på denne listen, hvis vi foranstilles (4), da ville vi ha 4 og deretter 3 og deretter 7. Så vi kan sette og fjerne 4, 3 fjern, fjern 7. Ofte mer intuitiv måte å tenke på dette er med append. Så jeg har skjematisk ut hva det ville se ut med føyer her. Her legges (7) ikke ser noe annerledes fordi det er bare ett element i listen. Og legge (3) uttrykker det på slutten. Kanskje du kan se akkurat nå kunsten med append er at siden vi bare kjenner hvor begynnelsen av listen er, å legge til en liste du har å gå hele veien gjennom listen å komme til slutten, stoppe, og deretter bygge din node og plunk alt ned. Wire alle ting opp. Så med foranstilte, som vi bare dratt gjennom dette veldig raskt, når du foranstille til en liste, er det ganske enkelt. 

Du gjør ditt nye node, innebære noen dynamisk minne allokering. Så her vi gjør en node struct hjelp malloc. Så malloc vi bruker fordi det vil sette minne for oss for senere fordi vi ikke ønsker dette - vi vil at dette minnet vil vedvare i lang tid. Og vi får en peker til plass i minnet at vi bare tildelt. Vi bruker størrelse node, har vi ikke summere feltene. Vi har ikke manuelt generere antall byte, i stedet bruker vi sizeof slik at vi vet at vi får riktig antall byte. Vi sørge for å teste at vår malloc samtale lyktes. Dette er noe du ønsker å gjøre generelt. På moderne maskiner, kjører ut av minnet er ikke noe som er lett med mindre du fordele massevis av ting og gjør en stor liste, men hvis du bygger ting for, si, som en iPhone eller en Android, du har begrensede minneressurser, spesielt hvis du gjør noe intens. Så det er godt å få i praksis. 

Legg merke til at jeg har brukt et par forskjellige funksjoner her som du har sett som er slags nye. Så fprintf er akkurat printf bortsett fra sin første argumentet er strømmen som du vil skrive ut. I dette tilfellet ønsker vi å skrive ut til standard feilstreng som er forskjellig fra standard outstream. Som standard viser den opp på samme sted. Den skriver også ut til terminalen, men du kan - å bruke disse kommandoene du har lært om, omdirigering teknikker du har lært om i Tommys video for oppgavesettet 4, kan du sende det til forskjellige områder, og avslutter rett her, avslutter programmet. Det er hovedsaklig som retur fra main, bortsett fra vi bruke exit fordi her retur ikke vil gjøre noe. Vi er ikke i hovedsak ikke så returnere ikke avslutte programmet som vi ønsker. Så vi bruker exit-funksjonen og gi det en feilkode. Så her har vi satt nye nodens verdi feltet, dens jeg felt til å være lik i, og vi koble den opp. Vi setter ny node neste pekeren å peke på først, og deretter første vil nå peke på den nye noden. Disse første linjene med kode, vi faktisk bygge den nye noden. Ikke de to siste linjene i denne funksjonen, men de første. Du kan faktisk trekke ut i en funksjon, i en hjelper funksjon. Det er ofte det jeg gjør er, trekker jeg det ut i en funksjon, Jeg kaller det noe sånt som build node, og som holder den foranstilte funksjonen ganske liten, er det bare 3 linjer da. Jeg ringer til min bygge node funksjon, og da jeg ledningen alt opp. 

Den siste tingen jeg vil vise deg, og jeg vil la deg gjøre append og alt som på egen hånd, er hvordan man skal iterere over en liste. Det er en haug med forskjellige måter å iterere over en liste. I dette tilfellet skal vi finne lengden på en liste. Så vi starter med lengde = 0. Dette er svært likt å skrive strlen for en streng. Dette er hva jeg ønsker å vise deg, dette for loop her. Det ser ganske funky, det er ikke vanlig int i = 0, i <uansett, i + +. I stedet er det initialiseres vår variable n å være begynnelsen av listen. Og så mens vår iterator variabel ikke er null, holder vi går. Dette er fordi, etter konvensjonen, vil slutten av vår liste være null. Og deretter å øke, heller enn å gjøre + +, den lenket liste tilsvarende + + er n = n-> neste. 

Jeg skal fortelle deg fylle ut hullene her fordi vi er ute av tiden. Men ha dette i bakhodet når du arbeider på spellr psets. Koblede lister, hvis du implementere en hash table, vil definitivt komme i svært hendig. Og å ha denne idiom for looping over ting vil gjøre livet mye enklere, forhåpentligvis. Eventuelle spørsmål, raskt? [Sam] Vil du sende ut den ferdige sll og fm? [Hardison] Yeah. Jeg sender ut fullførte lysbilder og fullførte sll stabelen og queue.cs. [CS50.TV]