[Powered by Google Translate] [§ 6] [Mer komfortabelt] [Rob Bowden] [Harvard University] [Dette er CS50.] [CS50.TV] 

Vi kan dra til vår del av spørsmålene. Jeg sendte URL for plass før. Begynnelsen av den delen av spørsmålene si- tilsynelatende Jeg er ikke helt unsick-er en veldig enkelt spørsmål av akkurat hva som er Valgrind? Hva gjør Valgrind? Noen ønsker å si hva Valgrind gjør? [Student] Sjekker minnelekkasjer. Ja, er Valgrind en generell minne brikke. Det, i slutten, forteller deg om du har noen minnelekkasjer, som er det meste hva vi bruker den til, fordi hvis du ønsker å gjøre det bra i oppgavesettet eller hvis du ønsker å få på the Big Board, må du ha noen minnelekkasjer overhodet, og i tilfelle du har en minnelekkasje som du ikke kan finne, også huske på at når du åpner en fil og hvis du ikke lukke den, det er en minnelekkasje. 

Mange mennesker leter etter noen node at de ikke frigjør når du egentlig har de ikke lukke ordboken i den aller første skritt. Den forteller deg også om du har noen ugyldig leser eller skriver, som betyr at hvis du prøver og sette en verdi det er utover slutten av haugen, og det ikke skjer SEG feil men Valgrind fanger det, som du ikke bør faktisk være å skrive det, og så du definitivt ikke bør ha noen av dem heller. Hvordan bruker du Valgrind? Hvordan bruker du Valgrind? 

Det er et generelt spørsmål av slags kjøre den og se på resultatet. Utgangen er overveldende mange ganger. Det er også morsomt feil der hvis du har noen fryktelig galt ting skjer i en loop, så vil det til slutt si: "Altfor mange feil. Jeg kommer til å slutte å telle nå. " Det er i utgangspunktet tekstlig resultat som du må analysere. Til slutt, vil den fortelle deg noen minnelekkasjer som du har, hvor mange blokker, som kan være nyttig fordi Hvis det er ett kvartal unfreed, så er det som regel enklere å finne enn 1000 blokker unfreed. 1000 blokker unfreed betyr sannsynligvis at du ikke frigjør dine koblede lister hensiktsmessig eller noe. Det er Valgrind. 

Nå har vi vår del av spørsmålene, som du ikke trenger å laste ned. Du kan klikke på navnet mitt og trekke dem opp i verdensrommet. Nå klikker du på meg. Revisjon 1 vil være stack, som vi gjør først. Revisjon 2 vil være kø, og Revisjon 3 vil være enkeltvis lenket liste. Starter med stacken. Som det står her, er en stabel en av de mest grunnleggende, grunnleggende datastrukturer i datavitenskap. Den svært prototypiske eksempel er bunken av skuffer i matsalen. Det er utgangspunktet når du blir introdusert til en stabel, noen kommer til å si: "Å, som en stabel av skuffene." Du stable skuffene opp. Så når du går å trekke en skuff, den første skuffen som begynner å bli trukket er den siste som ble satt på stakken. Bunken også-som det står her- vi har segmentet av minnet som kalles bunken. Og hvorfor er det kalt stabelen? 

Fordi som en stabel datastruktur, det skyver og spretter stack rammer på stakken, hvor stack rammer er som en bestemt oppfordring til en funksjon. Og som en stabel, vil du alltid ha for å gå tilbake fra en funksjon samtale før du kan komme ned i lavere stack rammer igjen. Du kan ikke ha hoved samtale Foo samtale bar og bar tilbake til hovedsiden direkte. Det er alltid fikk til å følge riktig stabelen presser og spratt. De to operasjoner, som jeg sa, er push og pop. De er universelle vilkår. Du bør vite push og pop i form av stabler uansett hva. Vi får se køer er litt annerledes. Det gjør egentlig ikke har et universelt begrep, men push og pop er universelle for stabler. Push er akkurat satt på stakken. Pop er ta av stabelen. Og vi ser her har vi vår typedef struct stabelen, så vi har røye ** strenger. Ikke bli redd av noen **. Dette kommer til å ende opp som en rekke strenger eller en rekke pekere til tegn, der pekere til tegn tendens til å være strenger. Det trenger ikke å være strenger, men her, de kommer til å være strenger. 

Vi har en rekke strenger. Vi har en størrelse, som representerer hvor mange elementer er for tiden på stakken, og så har vi kapasitet, som er hvor mange elementer kan være på stakken. Kapasiteten skal begynne som noe større enn 1, men størrelsen kommer til å starte som 0. Nå er det i utgangspunktet tre forskjellige måter du kan tenke på en stabel. Vel, det er nok mer, men de to viktigste måtene er du kan implementere det ved hjelp av en matrise, eller du kan implementere det ved hjelp av en lenket liste. Koplede listene slags trivielt å lage stabler fra. Det er veldig enkelt å lage en stabel med koblede lister, så her, vi kommer til å lage en stack bruke matriser, og deretter bruke matriser, er det også to måter du kan tenke på det. Før, da jeg sa at vi har en kapasitet på stabelen, slik at vi kan passe et element på stakken. 

Den ene måten det kunne skje er så snart du treffer 10 elementer, så er du ferdig. Du kanskje vet at det er en øvre grense på 10 ting i verden at du aldri har mer enn 10 ting på stabelen din, i så fall kan du ha en øvre grense på størrelsen av stabelen din. Eller du kan ha din stabelen ha ubegrenset, men hvis du gjør en matrise, betyr det at hver eneste gang du treffer 10 elementer, da er du nødt til å vokse til 20 elementer, og når du treffer 20 elementer, du er nødt til å vokse rekke til 30 elementer eller 40 elementer. Du kommer til å trenge å øke kapasiteten, som er hva vi skal gjøre her. Hver eneste gang vi kommer til maksimal størrelse på stacken, når vi skyver noe annet igjen, vi kommer til å trenge for å øke kapasiteten. Her har vi presse erklært som bool push (char * str). Char * str er strengen som vi presser på stakken, og bool sier bare om vi lyktes eller mislyktes. 

Hvordan kan vi mislykkes? Hva er den eneste omstendighet at du kan tenke på der vi trenger å gå tilbake falsk? Ja. [Student] Hvis den er full, og vi bruker en avgrenset gjennomføring. Ja, så hvordan definerer-han vi svarte hvis den er full, og vi bruker en avgrenset gjennomføring. Da vil vi definitivt return false. Så snart vi traff 10 ting i matrisen, kan vi ikke passer 11, så vi return false. Hva om det er ubegrenset? Ja. Hvis du ikke kan utvide array for noen grunn. Ja, så minnet en begrenset ressurs, og til slutt, hvis vi holder skyve ting på stabelen igjen og igjen, vi kommer til å prøve og tildele en større utvalg for å passe større kapasitet, og malloc eller hva vi bruker kommer til å returnere falsk. Vel, vil malloc tilbake null. 

Husk at hver eneste gang du ringer malloc, bør du sjekke for å se om det returnerer null eller annet som er en korrekt fradrag. Siden vi ønsker å ha en ubegrenset stabelen, det eneste tilfellet vi kommer til å komme tilbake falske er hvis vi prøver å øke kapasiteten og malloc eller hva returnerer false. Så pop tar ingen argumenter, og den returnerer streng som er på toppen av stabelen. Uansett ble sist presset på stakken er det pop er tilbake, og det fjerner også det fra stabelen. Og legg merke til at den returnerer null hvis det ikke er noe på stakken. Det er alltid mulig at bunken er tom. I Java, hvis du er vant til det, eller andre språk, prøver å stikke fra en tom stabelen kan føre et unntak eller noe. 

Men i C, er null slags mye av tilfellene hvordan vi håndterer disse problemene. Retur null er hvordan vi skal markere at bunken var tom. Vi har gitt kode som vil teste stabelen funksjonalitet, implementere presse og pop. Dette vil ikke være mye kode. Jeg vil-faktisk, før vi gjør det, hint, hint- hvis du ikke har sett det, er malloc ikke den eneste funksjonen som tildeler minne på haugen for deg. Det er en familie av Alloc funksjoner. Den første er malloc, som du er vant til. Så er det calloc, som gjør det samme som malloc, men det vil null alt ut for deg. Hvis du noensinne har ønsket å sette alt til null etter mallocing noe du skal ha bare brukt calloc i første omgang i stedet for å skrive en for loop å nullstille hele blokken av minnet. 

RealLOC er som malloc og har en rekke spesielle tilfeller, men innerst inne hva RealLOC gjør er det tar en peker som allerede hadde fått tildelt. RealLOC er funksjonen du ønsker å betale oppmerksomhet til her. Det tar en peker som allerede hadde blitt returnert fra malloc. La oss si du ber om fra malloc en pekepinn på 10 bytes. Du senere innser du ønsket 20 byte, så du kaller RealLOC på at pekeren med 20 byte, og RealLOC vil automatisk kopiere over alt for deg. Hvis du nettopp har ringt malloc igjen, som jeg har en blokk med 10 byte. Nå trenger jeg en blokk med 20 byte, så hvis jeg malloc 20 bytes, så jeg må manuelt kopiere over de 10 bytes fra det første inn i andre ting og deretter gratis det første. RealLOC vil håndtere det for deg. 

Legg merke til signaturen skal være void *, som bare returnere en peker til minneblokk, Deretter void * ptr. Du kan tenke på void * som et generisk peker. Vanligvis du aldri avtale med void *, men malloc returnerer et tomrom *, og da er det bare brukt som Dette er faktisk kommer til å bli en char *. Den forrige void * som hadde blitt returnert av malloc Nå skal sendes til RealLOC, og deretter størrelse er det nye antallet byte du ønsker å fordele, slik at den nye kapasiteten. Jeg skal gi deg et par minutter, og gjøre det i vårt område. Start med Revisjon 1. Jeg vil stoppe deg etter forhåpentligvis om nok tid til å gjennomføre push, og så skal jeg gi deg en annen pause for å gjøre pop. Men det er egentlig ikke så mye kode i det hele tatt. Den mest kode er trolig den voksende ting, utvide kapasiteten. Ok, ikke noe press for å bli helt ferdig, men så lenge du føler at du er på rett vei, det er bra. 

Har noen noen kode de føler seg komfortabel med meg trekke opp? Ja, jeg vil, men har noen noen kode jeg kan trekke opp? Ok, du kan starte, lagre det, uansett hva det er? Jeg har alltid glemmer det skrittet. Ok, ser på push, vil du forklare din kode? [Student] Først av alt, økte jeg størrelsen. Jeg tror kanskje jeg bør ha som-uansett, økte jeg størrelsen, og jeg se om det er mindre enn kapasiteten. Og hvis det er mindre enn kapasiteten, legger jeg til tabellen som vi allerede har. Og hvis det ikke er det, multiplisere jeg kapasiteten med 2, og jeg omdisponere strenger array til noe med en større kapasitet størrelse nå. Og så hvis det mislykkes, jeg sier brukeren og return false, og hvis det er greit, så jeg satte strengen i det nye stedet. 

[Rob B.] også merke til at vi brukte en fin bitvis operatør her å multiplisere med 2. Husk at venstre shift alltid kommer til å bli multiplisert med 2. Høyre shift er delt på 2 så lenge du husker at det betyr divideres med 2 som i et heltall deles med 2.. Det kan avkorte en 1 her eller der. Men skift igjen av en alltid kommer til å bli multiplisert med 2, med mindre du overflow grensene for heltall, og da det ikke vil være. En side kommentar. Jeg liker å gjøre-dette ikke kommer til å endre koding noen måte, men jeg liker å gjøre noe som dette. Det faktisk kommer til å gjøre det litt lenger. Kanskje dette er ikke den perfekte saken for å vise dette, men jeg liker å segmentere det i disse blokkene av- OK, hvis dette hvis skjer, så jeg kommer til å gjøre noe, og deretter funksjonen er ferdig. Jeg trenger ikke å deretter bla mine øyne hele veien ned funksjonen å se hva som skjer etter annet. Det er hvis dette hvis skjer, så jeg bare tilbake. Det har også den fine fordelen av alt utover dette er nå flyttet til venstre en gang. Jeg trenger ikke lenger å-hvis du noen gang i nærheten latterlig lange linjer, deretter de 4 byte kan hjelpe, og også mer igjen noe er, jo mindre overveldet du føle hvis liker-okay, jeg må huske Jeg er for tiden på en stund sløyfe inne i en annen inne i en for-løkke. Hvor du kan gjøre denne avkastningen umiddelbart, jeg typen som. Det er helt valgfritt, og ikke forventet på noen måte. 

[Student] Bør det være en størrelse - i fail tilstand? Fail tilstand her er vi ikke klarte å RealLOC, så ja. Legg merke til hvordan i fail tilstand, formodentlig, med mindre vi gratis ting senere, vi alltid kommer til å mislykkes uansett hvor mange ganger vi prøver å presse noe. Hvis vi holder skyve, holder vi økes størrelse, selv om vi ikke setter noe på bunken. Vanligvis vi ikke inkrementere størrelse inntil etter at vi har lykkes sette det på stakken. Vi ville gjøre det, sier, enten her og her. Og da i stedet for å si s.size ≤ kapasitet, er det mindre enn kapasiteten, bare fordi vi flyttet hvor alt var. 

Og husk, det eneste stedet vi kunne muligens return false er her, hvor RealLOC returnerte null, og hvis du tilfeldigvis å huske standard feil, kanskje du kan vurdere dette et tilfelle hvor du ønsker å skrive ut en standard feil, så fprintf stderr i stedet for bare å skrive ut direkte til standard ut. Igjen, det er ikke en forventning, men hvis det er en feil, skriver printf, bør du kanskje ønsker å gjøre det ut til standard feil i stedet for standard ut. 

Alle som har noe annet å merke? Ja. [Student] Kan du går over [uhørlig]? [Rob B.] Ja, selve binariness av det eller hva det er? [Student] Så du multipliserer det med 2? [Rob B.] Yeah, i utgangspunktet. I binær land, har vi alltid vårt sett av sifre. Skiftende denne venstre med 1 utgangspunktet setter den her på høyre side. Tilbake til dette, bare huske at alt i binær er en potens av 2, slik at dette representerer 2 til 0, denne 2 til 1, denne 2 til 2. Ved å sette en 0 til høyre side nå, vi bare skifte alt over. Det pleide å være 2 til 0 er nå 2 til 1, er 2 til 2. Høyre side som vi satt nødvendigvis kommer til å være 0, som er fornuftig. Hvis du noen gang multiplisere et tall med 2, er det ikke kommer til å ende opp rart, så 2 til 0 stedet skal være 0, og dette er hva jeg halv advart om før er hvis du klarer å skifte utover antallet av biter i et heltall, så dette en kommer til å ende opp med å gå av. Det er den eneste bekymring hvis du tilfeldigvis skal håndtere virkelig stor kapasitet. Men på det tidspunktet, så du arbeider med en rekke av milliarder av ting, som kanskje ikke passer inn i minnet uansett. 

Nå kan vi komme til pop, som er enda enklere. Du kan gjøre det som om du tilfeldigvis komme en hel haug, og nå er du på halv kapasitet igjen. Du kan RealLOC å krympe mengden minne du har, men du trenger ikke å bekymre deg for det, er så den eneste RealLOC saken kommer til å bli voksende minne, aldri krymper minne, som kommer til å gjøre pop super lett. Nå køer, som kommer til å være som stabler, men den rekkefølgen du tar ting ut er reversert. Den prototypiske eksempel på en kø er en linje, så jeg antar at hvis du var engelsk, ville jeg ha sagt en prototypiske eksempel på en kø er en kø. Så som en linje, hvis du er den første personen i linje, du forventer å være den første personen ut av linjen. Hvis du er den siste personen i linje, skal du være den siste personen service. Vi kaller det FIFO mønster, mens stakken var LIFO mønster. Disse ordene er ganske universelle. 

Liker stabler og i motsetning matriser, køer vanligvis ikke tillate tilgang til elementer i midten. Her, en stabel, har vi push og pop. Her skjer vi å ha kalt dem Enqueue og dequeue. Jeg har også hørt dem kalt skift og unshift. Jeg har hørt folk si push og pop til også å gjelde køer. Jeg har hørt sette inn, fjerne, så presse og pop, hvis du snakker om stabler, er du presser og spratt. Hvis du snakker om køer, kan du plukke de ordene du vil bruke for innsetting og fjerning, og det er ingen enighet om hva det skal bli kalt. Men her har vi Enqueue og dequeue. Nå ser struct nesten identisk med stabelen struct. Men vi må holde styr på hodet. Jeg antar det står her nede, men hvorfor trenger vi hodet? Prototypene er i utgangspunktet identisk med presse og pop. Du kan tenke på det som push og pop. Den eneste forskjellen er pop er retur-i stedet for den siste, er det tilbake den første. 2, 1, 3, 4, eller noe. Og her er starten. Vår køen er helt full, så det er fire elementer i den. Slutten av køen vår er nå 2, og nå går vi å sette noe annet. 

Når vi ønsker å sette inn at noe annet, hva vi gjorde for stabelen versjon er vi utvidet vår blokk med minne. Hva er problemet med dette? [Student] Du flytter to. Det jeg sa tidligere om slutten av køen, Dette rimer ikke at vi starter på 1, så vi ønsker å dequeue 1, så dequeue 3, så dequeue 4, Deretter dequeue 2, deretter dequeue denne. Vi kan ikke bruke RealLOC nå, eller i det minste, må du bruke RealLOC på en annen måte. Men du sannsynligvis ikke bør bare bruke RealLOC. Du er nødt til å manuelt kopiere minne. 

Det er to funksjoner for å kopiere minne. Det er memcopy og memmove. Jeg er for tiden leser mannen sidene for å se hvilken du skal ønske å bruke. Ok, memcopy, er forskjellen at memcopy og memmove, man håndterer saken riktig hvor du kopierer inn i et område som skjer for å overlappe regionen du kopierer fra. Memcopy ikke håndterer det. Memmove gjør. Du kan tenke på problemet som- la oss si jeg ønsker å kopiere denne fyren, disse fire til denne fyren. Til slutt, hva matrisen skal se ut Etter at kopieringen er 2, 1, 2, 1, 3, 4, og deretter noen ting på slutten. Men dette er avhengig av rekkefølgen i hvilken vi faktisk kopiere, siden hvis vi ikke anser det faktum at regionen vi kopierer inn overlapper den vi kopierer fra, så vi kan gjøre som start her, kopiere to i stedet vi ønsker å gå, deretter flytte våre pekere fremover. 

Nå skal vi være her og her, og nå ønsker vi å kopiere denne fyren over denne fyren og flytte våre pekere fremover. Hva vi kommer til å ende opp med å få er 2, 1, 2, 1, 2, 1 i stedet for den aktuelle 2, 1, 2, 1, 3, 4, fordi 2, 1 overvurdere den opprinnelige 3, 4. Memmove håndterer det riktig. I dette tilfellet, i utgangspunktet bare alltid bruke memmove fordi den håndterer det riktig. Det vanligvis ikke utfører noe verre. Ideen er stedet for å starte fra begynnelsen og kopiere denne måten som vi nettopp gjorde her, starter det fra slutten og kopierer inn, og i så fall, kan du aldri ha et problem. Det er ingen ytelse tapt. Bruk alltid memmove. Aldri bekymre memcopy. Og det er der du er nødt til å separat memmove innpakket rundt delen av køen. Ingen grunn til bekymring dersom ikke helt ferdig. Dette er vanskeligere enn stack, push, og pop. 

Alle som har noen kode vi kunne jobbe med? Selv om helt ufullstendig? [Student] Ja, det er helt ufullstendig, skjønt. Helt ufullstendig er greit så lenge vi-kan du lagre revisjon? Jeg glemmer at hver eneste gang. Ok, ignorerer hva som skjer når vi trenger å endre størrelsen ting. Fullstendig ignorere resize. Forklar denne koden. Jeg sjekker først hvis størrelsen er mindre enn den kopi først av alt og så etter det, jeg setter-jeg ta hodet + størrelse, og jeg sørge for at det brytes rundt kapasiteten for tabellen, og jeg setter den nye strengen på den posisjonen. Så jeg øke størrelsen og returnere true. 

[Rob B.] Dette er definitivt en av de tilfellene der du kommer til å ønske å bruke mod. Enhver form for tilfelle der du har innpakning rundt, hvis du tror innpakning rundt, den umiddelbare tanke bør være mod. Som en rask optimalisering / gjøre koden en linje kortere, du merker at linjen umiddelbart etter dette er bare størrelse + +, så du flette det inn denne linjen, størrelse + +. Nå her nede, har vi saken hvor vi ikke har nok minne, så vi øker vår kapasitet med 2. Jeg antar du kan ha det samme problemet her, men vi kan ignorere det nå, der hvis du ikke klarte å øke kapasiteten, så du kommer til å ønske å redusere kapasiteten med 2 igjen. En annen liten notis er akkurat som du kan gjøre + =, du kan også gjøre << =. Nesten alt kan gå før lik, + =, | =, & =, << =. Char * nye er vår nye blokk med minne. Oh, over her. 

Hva synes folk om hvilken type vår nye blokk med minne? [Student] Det bør være char **. Tenker tilbake til struct vår her oppe, strenger er det vi omfordele. Vi gjør en hel ny dynamisk lagring for elementene i køen. Hva vi kommer til å bli tildeling av strenger er det vi mallocing akkurat nå, og så ny kommer til å bli en røye. ** Det kommer til å bli en rekke strenger. Så hva er tilfellet der vi kommer til å returnere falsk? [Student] Bør vi gjøre char *? [Rob B.] Ja, god samtale. [Student] Hva var det? [Rob B.] Vi ønsket å gjøre størrelsen på char * fordi vi ikke lenger er- dette ville faktisk være et veldig stort problem fordi sizeof (char) ville være en. Sizeof char * kommer til å være 4, så mange ganger når du arbeider med ints, du har en tendens til å komme unna med det fordi størrelsen på int og størrelse på int * på en 32-bit system kommer til å være det samme. Men her, sizeof (char) og sizeof (char *) skal nå være det samme. 

Hva er forholdet hvor vi return false? [Student] Nytt er null. Ja, dersom ny er null, returnerer vi false, og jeg kommer til å kaste ned her- [Student] [uhørlig] [Rob B.] Yeah, dette er greit. Du kan enten gjøre to ganger kapasiteten eller kapasitet skift 1 og deretter bare sette den ned her eller hva. Vi vil gjøre det som vi hadde det. Kapasitet >> = 1. Og du aldri kommer til å måtte bekymre deg for å miste en plass fordi du forlot forskjøvet med 1, slik at en plass er nødvendigvis en 0, så rett skiftende med 1, er du fortsatt kommer til å være i orden. [Student] Trenger du å gjøre det før retur? [Rob B.] Ja, gjør dette absolutt ingen mening. 

Nå antar vi kommer til å ende opp tilbake true til slutten. Måten vi kommer til å gjøre disse memmoves, Vi må være forsiktig med hvordan vi gjør det. Har noen noen forslag til hvordan vi gjør dem? Her er vår start. Uunngåelig, ønsker vi å starte på begynnelsen igjen og kopiere ting i fra det, 1, 3, 4, 2. Hvordan gjør man det? Først må jeg se på mannen siden for memmove igjen. Memmove, er rekkefølgen som argumentene alltid viktig. Vi ønsker vår destinasjon først, kilde andre, størrelse tredje. Det er mange funksjoner som reverserer kilde og destinasjon. Destination, kilde tendens til å være konsekvent noe. Flytte, hva er det tilbake? Den returnerer en peker til bestemmelsesstedet, uansett grunn du kanskje ønsker det. Jeg kan bilde lese den, men vi ønsker å flytte inn vår destinasjon. 

Hva er vår destinasjon kommer til å bli? [Student] Ny. [Rob B.] Ja, og hvor er vi kopierer fra? Det første vi kopierer dette er 1, 3, 4. Hva er-dette 1, 3, 4. Hva er adressen til dette 1? Hva er adressen til den 1? [Student] [uhørlig] [Rob B.] Leder + adressen til den første element. Hvordan får vi det første elementet i matrisen? [Student] kø. [Rob B.] Ja, q.strings. Husk, her er vårt hode en. Stoppe. Jeg tror det er magisk- Her er vårt hode en. Jeg kommer til å endre min farge også. Og her er strenger. Dette kan vi enten skrive det som vi gjorde over her med hode + q.strings. Mange mennesker også skrive det og q.strings [hodet]. Dette er egentlig ikke noe mindre effektiv. Du kan tenke på det som du dereferencing det og så får adressen, men kompilatoren skal oversette det til hva vi hadde før uansett, q.strings + hode. Uansett du ønsker å tenke på det. 

Og hvor mange byte vi ønsker å kopiere? [Student] Kapasitet - hodet. Kapasitet - hodet. Og så kan du alltid skrive ut et eksempel å finne ut om det er riktig. [Student] Det må deles med 2 da. Ja, så jeg antar at vi kunne bruke størrelse. Vi har fortsatt størrelse being- hjelp av størrelse, har vi størrelse lik 4. Vår størrelse er 4. Vår leder er en. Vi ønsker å kopiere disse tre elementene. Det er sunn fornuft kontrollere at størrelsen - hodet er riktig 3. Og kommer tilbake hit, som vi sa før, hvis vi brukte kapasitet, så vi måtte dele med 2 fordi vi allerede har vokst vår kapasitet, så i stedet, vi kommer til å bruke størrelse. At kopier den delen. Nå må vi kopiere den andre delen, den delen som er igjen av starten. 

Det kommer til å memmove inn hvilken posisjon? [Student] Plus størrelse - hodet. Ja, så vi har allerede kopiert i størrelse - head bytes, og så hvor vi ønsker å kopiere de resterende bytes er nytt og deretter størrelse minus-vel, antall byte vi allerede har kopiert i. Og deretter hvor vi kopierer fra? [Student] Q.strings [0]. [Rob B.] Ja, q.strings. Vi kan enten gjøre og q.strings [0]. Dette er betydelig mindre vanlig enn dette. Hvis det bare kommer til å være 0, så vil du pleier å se q.strings. Det er der vi kopierer fra. Hvor mange byte har vi igjen å kopiere? >> [Student] 10. Høyre. [Student] Har vi å formere 5 - 10 ganger størrelsen på byte eller noe? Ja, så dette er hvor-hva er det vi kopiering? [Student] [uhørlig] Hva er den type ting vi kopierer? [Student] [uhørlig] Ja, så char * s som vi kopierer, vet vi ikke hvor de kommer fra. Vel, hvor de peker til, som strengene, ender vi opp med å skyve den på køen eller enqueuing på køen. Hvor de kommer fra, aner vi ikke. Vi trenger bare å holde styr på char * s selv. Vi ønsker ikke å kopiere størrelse - head bytes. Vi ønsker å kopiere størrelse - head char * s, så vi kommer til å mangedoble dette ved sizeof (char *). Samme her nede, hodet * sizeof (char *). 

[Student] Hva med [uhørlig]? Dette her? [Student] Nei, under det, størrelsen - hodet. [Rob B.] Denne retten her? Peker aritmetikk. Hvordan pekeren aritmetiske kommer til å fungere er det multipliserer automatisk av størrelsen av den type som vi har å gjøre med. Akkurat som over her, nye + (størrelse - hode) er nøyaktig tilsvarer & nye [size - head] før vi forventer at det vil fungere riktig, siden hvis vi arbeider med en int array, så vi ikke indeksen med int- eller om det er av størrelse på 5 og du vil at fjerde element, så vi indeksen i int array [4]. Du må få [4] * størrelsen på int. Som håndterer det automatisk, og dette tilfellet er bokstavelig tilsvarende, slik at braketten syntaksen er bare kommer til å bli konvertert til dette så snart du kompilere. Det er noe du må være forsiktig med at når du legger størrelse - head du legger ikke en byte. Du legger en char *, som kan være en byte eller hva. 

Andre spørsmål? Ok, dequeue kommer til å bli lettere. Jeg skal gi deg et minutt å gjennomføre. Oh, og jeg tror dette er den samme situasjonen der hva Enqueue tilfelle, hvis vi enqueuing null, kanskje vi ønsker å håndtere det, kanskje vi ikke. Vi vil ikke gjøre det igjen her, men samme som vår stack saken. Hvis vi Enqueue null, kanskje vi ønsker å se bort fra det. Noen har noen kode jeg kan trekke opp? [Student] Jeg må bare dequeue. Versjon 2 er at-okay. Du ønsker å forklare? [Student] Først må du sikker på at det er noe i køen og at størrelsen går ned 1. Du trenger å gjøre det, og du returnere hodet og deretter bevege hodet opp en. Ok, så det er et hjørne tilfelle vi må vurdere. Ja. [Student] Hvis hodet er på det siste elementet, så du ikke vil hodet til å peke utenfor tabellen. 

Ja, slik at så snart hodet treffer slutten av matrisen vår, når vi dequeue, bør vår hodet modded tilbake til 0. Dessverre kan vi ikke gjøre det i ett trinn. Jeg antar slik jeg ville trolig fikse det er dette kommer til å bli en char *, hva vi er tilbake, uansett variabelnavn ønsker å være. Så vi ønsker å mod hodet av kapasiteten vår og deretter tilbake ret. En masse folk her de kan gjøre, dette er tilfelle for-vil du se folk gjøre hvis hodet er større enn kapasiteten, gjør hodet - kapasitet. Og det er bare å jobbe rundt hva mod er. Hode mod = kapasiteten er mye renere av en innpakning rundt enn om hodet større enn kapasiteten hodet - kapasitet. 

Spørsmål? Ok, er det siste vi har forlatt vår lenket liste. Du kan bli brukt til noen av lenket liste oppførsel hvis du gjorde knyttet lister i dine hash tabeller, hvis du gjorde en hash table. Jeg anbefaler på det sterkeste å gjøre en hash table. Du har kanskje allerede gjort en trie, men prøver er vanskeligere. I teorien er de asymptotisk bedre. Men bare se på det store bord, og prøver aldri gjøre det bedre, og de tar opp mer minne. Alt prøver om ender opp med å bli verre for mer arbeid. Det er hva David Malan løsning alltid er er han alltid innlegg hans trie løsning, og la oss se hvor han nå er. Hva var han under, David J? Han er nr. 18, så det er ikke veldig dårlig, og det kommer til å bli en av de beste prøver du kan tenke på eller en av de beste prøver av en trie. Er det ikke engang hans opprinnelige løsningen? Jeg føler at Trie løsninger har en tendens til å være mer i dette området av RAM-bruk. 

Gå ned til toppen, og RAM-bruk er i enkelttall. Gå ned mot bunnen, og deretter begynne å se prøver hvor du får helt enormt RAM-bruk, og prøver er vanskeligere. Ikke helt verdt det, men en pedagogisk opplevelse hvis du gjorde en. Det siste er vår lenket liste, og disse tre tingene, stabler, køer, og koblede lister, eventuell fremtidig ting du aldri gjøre i informatikk vil anta at du har kjennskap til disse tingene. De er bare så grunnleggende for alt. 

Knyttet lister, og her har vi en enkeltvis lenket liste kommer til å være vår gjennomføring. Hva betyr enkeltvis knyttet betyr i motsetning til dobbelt knyttet? Ja. [Student] Det peker bare til den neste pekeren snarere enn til markørene, som den forut den og den ene etter den. Ja, så i bildeformat, hva gjorde jeg nettopp? Jeg har to ting. Jeg har bilde og bilde. I bildeformat, våre enkeltvis knyttet lister, uunngåelig, har vi en slags pekepinn på hodet av vår liste, og deretter innen vår liste, vi må bare pekere, og kanskje dette peker til null. Det kommer til å være typisk tegning av en enkeltvis lenket liste. En dobbelt lenket liste, kan du gå bakover. Hvis jeg gir deg noen node i listen, så kan du nødvendigvis komme til enhver annen node i listen hvis det er en dobbelt lenket liste. Men hvis jeg får du den tredje node i listen, og det er en enkeltvis lenket liste, ingen måte du noen gang kommer til å få til den første og andre noder. Og det er fordeler og detriments, og en åpenbar en er å ta deg opp mer størrelse, og du må holde styr på hvor disse tingene peker nå. Men vi bare bryr seg om enkeltvis sammen. 

Et par ting vi er nødt til å gjennomføre. Din typedef struct node, int i: struct node * neste; node. Det typedef skal brennes inn i dine tanker. Quiz 1 bør gjerne gi en typedef av en lenket liste node, og du bør være i stand til umiddelbart rable det ned uten engang å tenke på det. Jeg antar et par spørsmål, hvorfor vi trenger struct her? Hvorfor kan ikke vi si node *? [Student] [uhørlig] Ja. Det eneste som definerer en node som en ting er typedef selv. Men som av dette punktet, når vi er slags parsing gjennom denne struct node definisjon, Vi er ikke ferdig vår typedef ennå, så da typedef ikke er ferdig, node finnes ikke. Men struct node gjør, denne noden og her, dette kan også bli kalt noe annet. Dette kan kalles n. Det kan bli kalt lenket liste node. Det kan kalles noe. Men dette struct node trenger å bli kalt det samme som denne struct node. Hva du kaller dette å også være her, og slik at besvarer også det andre punktet av spørsmålet som er grunnen til-en rekke ganger når du ser structs og typedefs av structs, vil du se anonyme structs der du bare se typedef struct, gjennomføring av struct, ordbok, eller hva. 

Hvorfor her trenger vi å si node? Hvorfor kan det ikke være en anonym struct? Det er nesten det samme svaret. [Student] Du må referere til det i struct. Ja, i struct, må du referere til struct seg selv. Hvis du ikke gi struct et navn, hvis det er en anonym struct, kan du ikke se det. Og sist men ikke minst disse bør alle være litt grei, og de skal hjelpe deg å realisere hvis du skriver dette ned at du gjør noe galt hvis disse slags ting ikke gir mening. Sist men ikke minst, hvorfor dette måtte være struct node *? Hvorfor kan det ikke bare være struct node neste? [Student] Peker til neste struct. Det er uunngåelig hva vi ønsker. Hvorfor kan det aldri bli struct node neste? Hvorfor må det være struct node * neste? Ja. [Student] Det er som en uendelig loop. Ja. [Student] Det ville alle være i ett. Ja, bare tenk på hvordan vi ville gjøre størrelsen på eller noe. Størrelsen på en struct er i utgangspunktet + eller - noe mønster her eller der. Det er i utgangspunktet kommer til å være summen av størrelsen på ting i struct. Dette her, uten å endre noe, er størrelsen kommer til å bli lett. Størrelsen på struct node kommer til å være størrelsen på i + størrelse neste. Størrelsen jeg kommer til å være 4. Størrelsen neste kommer til å være 4. Størrelsen på struct node skal være 8. Hvis vi ikke har *, tenker på sizeof, deretter sizeof (i) skal være 4. Størrelsen på struct node neste kommer til å bli størrelsen på i + størrelse struct node neste + Størrelse i + størrelse struct node neste. Det ville være en uendelig rekursjon av noder. Dette er grunnen til at dette er hvordan ting må være. 

Igjen, definitivt huske at eller i det minste forstår det nok at du kan være i stand til å Årsaken gjennom hva det skal se ut. De tingene vi kommer til å ønske å gjennomføre. Hvis lengden på listen- du kan jukse og holde rundt en global lengde eller noe, men vi kommer ikke til å gjøre det. Vi skal telle lengden av listen. Vi har inneholder, så det er i utgangspunktet som et søk, så vi har en lenket liste av heltall for å se om dette heltall er i lenket liste. Prepend skal sette på begynnelsen av listen. Tilføy skal sette på slutten. Insert_sorted kommer til å sette inn i den sorterte posisjon i listen. Insert_sorted slags forutsetter at du aldri har brukt foranstilte eller legge på dårlige veier. 

Insert_sorted når du implementere insert_sorted- la oss si at vi har vår lenket liste. Dette er hva det øyeblikket ser ut, 2, 4, 5. Jeg ønsker å sette 3, så så lenge selve lista allerede sortert, det er lett å finne hvor tre hører hjemme. Jeg starter på 2. Ok, er 3 større enn 2, så jeg ønsker å holde det gående. Oh, er 4 for stor, så jeg vet 3 kommer til å gå i mellom 2 og 4, og jeg må fikse pekere og alt det der. Men hvis vi ikke strengt bruke insert_sorted, liker la oss bare si at jeg foranstille 6, da min lenket liste kommer til å bli det. Det gjør nå ingen mening, så for insert_sorted, kan du bare anta at listen er sortert, selv om virksomheten består som kan føre til at det ikke skal sorteres, og det er det. Finn en nyttig innsats-så de er de viktigste tingene du nødt til å gjennomføre. 

For nå, ta et minutt å gjøre lengde og inneholder, og de bør være relativt rask. Nærmer stengetid, slik at alle har noe for lengde eller inneholder? De kommer til å være nesten identiske. [Student] Lengde. La oss se, revisjon. Okay. Du ønsker å forklare? [Student] jeg bare lage en peker node og initialisere den til først, som er vår globale variable, og da jeg sjekke for å se om det er null, så jeg ikke får en SEG feil og returnere 0 hvis det er tilfelle. Ellers har jeg sløyfe, holde styr på i heltall hvor mange ganger jeg har hentet det neste elementet i listen og i samme trinn operasjonen også videre at selve elementet, og da jeg kontinuerlig gjøre sjekk for å se om det er null, og hvis det er null, så det avbryter og bare returnerer antall elementer jeg har tilgang til. 

[Rob B.] Har noen noen kommentarer til noe? Dette ser bra korrekthet klok. [Student] Jeg tror ikke du trenger noden == null. Ja, så hvis node == null return 0. Men hvis node == null deretter dette-oh, det er en riktigheten problem. Det var bare du returnerer jeg, men det er ikke i omfang akkurat nå. Du trenger bare int i, så jeg = 0. Men hvis node er null, så jeg er fortsatt kommer til å være 0, og vi kommer til å returnere 0, så denne saken er identiske. En annen vanlig ting er å holde erklæringen av node innsiden av for løkke. Du kan si-oh, nei. La oss holde det som dette. Jeg ville trolig sette int i = 0 her, deretter node * node = første her. Og dette er trolig hvordan-bli kvitt dette nå. Dette er trolig hvordan jeg ville ha skrevet det. Du kan også utseende på det som dette. Dette for loop struktur her bør være nesten like naturlig for deg som for int i = 0 i er mindre enn lengden av array i + +. Hvis det er slik du iterere over en matrise, er dette hvordan du iterere over en lenket liste. 

Dette bør være andre natur på enkelte punkt. Med det i tankene, dette kommer til å være nesten det samme. Du kommer til å ønske å iterere over en lenket liste. Hvis node-Jeg har ingen anelse om hva verdien kalles. Node jeg. Hvis verdien på det node = jeg kommer tilbake sant, og det er det. Legg merke til at den eneste måten vi noen gang tilbake false er hvis vi iterere over hele lenket liste og aldri returnere true, så det er hva dette betyr. Som en side notat-vi sannsynligvis ikke vil komme til å legge til eller foranstille. 

Rask siste notat. Hvis du ser den statiske nøkkelordet, så la oss si static int count = 0, så vi teller + +, kan du i utgangspunktet tenker på det som en global variabel, selv om jeg sa dette er ikke hvordan vi skal gjennomføre lengde. Jeg gjør dette her, og så telle + +. Noen måte vi kan skrive en node i vår lenket liste vi inkrementering vår teller. Poenget med dette er hva den statiske nøkkelordet betyr. Hvis jeg bare hadde int count = 0 som ville være en vanlig gammel global variabel. Hva static int count betyr at det er en global variabel for denne filen. Det er umulig for en annen fil, liker tenke på pset 5, hvis du har startet. Du har både speller.c, og du har dictionary.c, og hvis du bare erklære en ting global, så noe i speller.c kan nås i dictionary.c og vice versa. Globale variabler er tilgjengelig for alle. C-fil, men statiske variabler er bare tilgjengelig fra selve filen, så innsiden av stavekontroll eller innsiden av dictionary.c, dette er slags hvordan jeg ville erklære min variabel for størrelsen på matrisen min eller størrelsen på min antall ord i ordboken. Siden jeg ikke ønsker å erklære en global variabel som alle har tilgang til, Jeg bare bryr seg om det for min egne formål. 

Den gode ting om dette er også hele navnet kollisjon ting. Hvis noen andre filen prøver å bruke en global variabel kalt teller, ting går veldig, veldig galt, så dette holder pent ting sikkert, og bare du kan få tilgang til den, og ingen andre kan, og hvis noen andre erklærer en global variabel kalt teller, da det ikke vil forstyrre din statisk variabel kalt teller. Det er det statiske er. Det er en fil global variabel. 

Spørsmål om noe? Alle sett. Bye. [CS50.TV]