[Powered by Google Translate] [Afsnit 6] [Mere Comfortable] [Rob Bowden] [Harvard University] [Dette er CS50.] [CS50.TV] 

Vi kan gå til vores afsnit med spørgsmål. Jeg sendte URL'en til rummet før. I begyndelsen af ​​det afsnit af spørgsmålene sige- tilsyneladende er jeg ikke helt unsick-er en meget nem spørgsmål af bare, hvad der Valgrind? Hvad gør Valgrind gøre? Enhver, der ønsker at sige, hvad Valgrind gør? [Student] Kontrol memory leaks. Ja, Valgrind er en generel hukommelse checker. Det i sidste ende, fortæller dig, hvis du har memory leaks, der er for det meste hvad vi bruger det til, fordi hvis du ønsker at gøre godt i det problem sæt eller hvis du ønsker at komme på den store bord, skal du have nogen memory leaks overhovedet, og i tilfælde af at du har en hukommelsesfejl, som du ikke kan finde, også huske på, at hver gang du åbner en fil og hvis du ikke lukker det, det er en hukommelsesfejl. 

En masse mennesker er på udkig efter nogle node at de ikke er at befri når der virkelig, de ikke lukke ordbogen i det allerførste skridt. Det fortæller dig også, hvis du har nogen ugyldig læser eller skriver, hvilket betyder, at hvis du prøver og indstille en værdi Det er ud over enden af ​​bunken, og det ikke ske for seg fejl men Valgrind fanger det, som du ikke burde faktisk være at skrive der, og så du absolut bør ikke have nogen af ​​dem, der enten. Hvordan bruger du Valgrind? Hvordan bruger du Valgrind? 

Det er et generelt spørgsmål om slags køre det og se på outputtet. Udgangen overvældende mange gange. Der er også sjove fejl, hvor, hvis du har nogle forfærdeligt forkerte ting sker i en løkke, så vil det i sidste ende sige, "Alt for mange fejl. Jeg har tænkt mig at stoppe tællingen nu. " Det er dybest set tekstuelle output, som du er nødt til at parse. I sidste ende vil det fortælle dig noget memory leaks, som du har, hvor mange blokke, som kan være nyttige, fordi hvis det er en blok unfreed, så er det som regel lettere at finde 1.000 blokke unfreed. 1.000 blokke unfreed sandsynligvis betyder, at du ikke frigøre dine linkede lister passende vis eller noget. Det er Valgrind. 

Nu har vi vores afsnit med spørgsmål, som du ikke behøver at downloade. Du kan klikke på mit navn og trække dem op i rummet. Klik nu på mig. Revision 1 vil være stakken, som vi gør først. Revision 2 vil være kø, og Revision 3 bliver den enkeltvis linkede liste. Starter ud med vores stack. Som der står her, en stak er en af ​​de mest grundlæggende, fundamentale datastrukturer for Datalogi. Den meget prototypisk eksempel er stakken af ​​bakker i spisesalen. Det er dybest set, når du er ved at blive introduceret til en stak, er nogen, der vil sige, "Åh, som en stak af bakker." Du stable bakkerne op. Så når du går til at trække en bakke, den første bakke, er at få trukket den sidste, der blev lagt på stakken. Stakken også-lignende der står her- vi har segment af hukommelse kaldet stakken. Og hvorfor er det hedder stakken? 

Fordi som en stak datastruktur, det skubber og popper stakrammer på stakken, hvor stakrammer er som en specifik indkaldelse af en funktion. Og som en stak, vil du altid nødt til at vende tilbage fra en funktion opkald, før du kan komme ned i lavere stakrammer igen. Du kan ikke have hovedindkaldelse Foo kald bar og bar tilbagevenden til main direkte. Det har altid fået at følge den korrekte stak skubbe og popping. De to operationer, som jeg sagde, er push og pop. Det er universelle vilkår. Du skal vide, push og pop i form af stabler uanset hvad. Vi vil se køer er slags forskellige. Det behøver ikke virkelig har en universel sigt, men push og pop er universelle for stakke. Push er lige sat i stakken. Pop er tag stakken. Og vi ser her vi har vores typedef struct stack, så vi har char ** strenge. Må ikke få skræmt af nogen **. Dette vil ende med at blive en vifte af strenge eller et array af pointere til figurer, hvor henvisninger til tegn tendens til at være strenge. Det behøver ikke at være strenge, men her, så vil de være strenge. 

Vi har en bred vifte af strenge. Vi har en størrelse, som repræsenterer, hvor mange elementer er i øjeblikket på stakken, og så har vi den kapacitet, der er, hvor mange elementer kan være på stakken. Kapaciteten starter som noget større end 1, men størrelsen kommer til at starte med 0.. Nu er der grundlæggende tre forskellige måder, du kan tænke på en stak. Nå, der er nok flere, men de to vigtigste måder er du kan gennemføre det ved hjælp af et array, eller du kan implementere det ved hjælp af en sammenkædet liste. Sammenkædede lister slags trivielt at lave stakke fra. Det er meget nemt at lave en stak med hægtede lister, så her, vi kommer til at lave en stak ved hjælp af arrays, og derefter bruge arrays, er der også to måder, du kan tænke over det. Før, da jeg sagde, at vi har en kapacitet til stakken, så vi kan passe et element på stakken. 

Den ene måde, det kunne ske, er, så snart du rammer 10 elementer, så er du færdig. Du kan vide, at der er en øvre grænse på 10 ting i verden at du aldrig vil have mere end 10 ting på din stack, i hvilket tilfælde du kan have en øvre grænse på størrelsen af ​​din stack. Eller du kan have din stack blive ubegrænset, men hvis du laver et array, der betyder, at hver eneste gang du rammer 10 elementer, så er du nødt til at vokse til 20 elementer, og når du rammer 20 elementer, du er nødt til at dyrke din array til 30 elementer eller 40 elementer. Du vil få brug for at øge kapaciteten, hvilket er, hvad vi skal gøre her. Hver eneste gang vi når den maksimale størrelse på vores stak, når vi skubbe noget andet på, vi vil få brug for at øge kapaciteten. Her har vi skub erklæret som bool tryk (char * str). Char * str er den streng, vi presser på stakken, og bool bare siger, om det lykkedes eller mislykkedes. 

Hvordan kan man undgå? Hvad er den eneste omstændighed, at du kan tænke på hvor vi skulle returnere falsk? Yeah. [Student] Hvis det er fuld, og vi bruger en afgrænset implementering. Ja, så hvordan kan vi definere, han svarede hvis det er fuld, og vi bruger en afgrænset implementering. Så vil vi helt sikkert vende tilbage falsk. Så snart vi ramte 10 ting i array, kan vi ikke passe 11, så vi vender tilbage falsk. Hvad hvis det er ubegrænset? Yeah. Hvis du ikke kan udvide den vifte af en eller anden grund. Ja, så hukommelsen er en begrænset ressource, og til sidst, hvis vi holder presser tingene ned på stakken igen og igen, vi vil forsøge at afsætte en større vifte til at passe den større kapacitet, og malloc eller hvad vi bruger kommer til at returnere falsk. Nå, vil malloc returnere null. 

Husk, hver eneste gang du nogensinde kalde malloc, bør du kontrollere at se, om det returnerer null eller andet, der er en korrekthed fradrag. Da vi ønsker at have en grænseløs stack, den eneste sag, vi vil vende tilbage falsk er, hvis vi forsøger at øge kapaciteten og malloc eller hvad returnerer falsk. Så pop tager ingen argumenter, og den returnerer den streng, der er på toppen af ​​stakken. Uanset hvad blev senest skubbet på stakken er, hvad pop er på vej tilbage, og det også fjerner den fra stablen. Og bemærke, at den returnerer null hvis der ikke er noget på stakken. Det er altid muligt, at stakken er tom. I Java, hvis du er vant til det, eller andre sprog forsøger at pop fra en tom stak kan forårsage en undtagelse eller noget. 

Men i C, er null slags en masse af de tilfælde, hvordan vi håndterer disse problemer. Returning null er, hvordan vi vil betyde, at stakken var tom. Vi har forudsat kode, der vil teste din stack funktionalitet, gennemføre skubbe og pop. Dette vil ikke være en masse kode. Jeg vil-faktisk, før vi gør det, hint, hint- hvis du ikke har set det, malloc er ikke den eneste funktion der allokerer hukommelse på heapen for dig. Der er en familie af Alloc funktioner. Den første er malloc, som du er vant til. Så er der calloc, der gør det samme som malloc, men det vil nul alt ud for dig. Hvis du nogensinde har ønsket at indstille alt til null efter mallocing noget bør du lige har brugt calloc i første omgang i stedet for at skrive en for-løkke til nul ud hele blok af hukommelse. 

Realloc er ligesom malloc og har en masse specielle tilfælde, men dybest set, hvad realloc gør, er det tager en pointer, der allerede er blevet fordelt. Realloc er den funktion, du ønsker at være opmærksom på her. Det tager en pointer der allerede var blevet returneret fra malloc. Lad os sige, at du anmode malloc en pegepind på 10 bytes. Så senere du indser du ønskede 20 byte, så du kalder realloc på denne pegepind med 20 bytes, og realloc vil automatisk kopiere over alt for dig. Hvis du har lige ringet malloc igen, ligesom jeg har en blok på 10 bytes. Nu har jeg brug for en blok på 20 bytes, så hvis jeg malloc 20 bytes, så er jeg nødt til manuelt at kopiere over de 10 bytes fra den første ting ind i den anden ting, og derefter fri den første ting. Realloc vil håndtere det for dig. 

Bemærk signaturen bliver ugyldig *, som blot returnere en markør til blokken af ​​hukommelsen, så void * ptr. Du kan tænke på void * som en generisk pointer. Generelt skal du aldrig beskæftige sig med void *, men malloc vender tilbage en void *, og så er det bare brugt som dette er faktisk vil være en char *. Den tidligere void *, der var blevet returneret af malloc vil nu blive videregivet til realloc, og derefter størrelse er det nye nummer af bytes, du ønsker at tildele, så den nye kapacitet. Jeg vil give dig et par minutter, og gøre det i vores rum. Start med revision 1. Jeg vil stoppe dig efter forhåbentlig om nok tid til at gennemføre push, og så vil jeg give dig en anden pause til at gøre pop. Men det er virkelig ikke så meget kode på alle. Den mest koden er nok det ekspanderende ting, udvide kapaciteten. Okay, ingen pres for at blive helt færdig, men så længe du har lyst, du er på rette vej, det er godt. 

Er der nogen der har nogen kode, de føler sig trygge med mig trække op? Ja, jeg vil, men nogen der har nogen kode jeg kan trække op? Okay, kan du begynde, gemme det, uanset hvad det er? Jeg glemmer altid dette skridt. Okay, ser på push, vil du forklare din kode? [Student] Først og fremmest jeg øget størrelsen. Jeg tror måske jeg skulle have at-anyway, jeg øget størrelsen, og jeg se om det er mindre end kapaciteten. Og hvis det er mindre end den kapacitet, jeg tilføje til array, vi allerede har. Og hvis det ikke er, jeg mangedoble kapaciteten med 2, og jeg omfordele strings array til noget med en større kapacitet størrelse nu. Og så hvis det ikke virker, jeg fortælle brugeren og returnere falsk, og hvis det er fint, så jeg satte strengen i den nye plet. 

[Rob B.] Bemærk også, at vi brugte en dejlig bitvis operatør her at gange med 2. Husk, at venstre skift vil altid ganges med 2. Højre skift er divideret med 2, så længe du husker, at det betyder dividere med 2 som i et helt tal divideret med to. Det kan afkorte en 1 her eller der. Men skift tilbage med 1 vil altid ganges med 2, medmindre du overflow grænserne for det heltal, og så vil det ikke være. En side kommentar. Jeg kan lide at gøre, er dette ikke kommer til at ændre kodningen nogen måde, men jeg vil gerne gøre noget som dette. Det faktisk vil gøre det lidt længere. Måske er det ikke den perfekte sagen for at vise dette, men jeg vil gerne segment det i disse blokke af- okay, hvis dette, hvis der sker, så jeg har tænkt mig at gøre noget, og derefter funktionen udføres. Jeg behøver ikke at rul derefter mine øjne hele vejen ned funktionen for at se, hvad der sker efter andet. Det er hvis dette, hvis der sker, så jeg bare vende tilbage. Det har også den dejlig sidegevinst af alt ud over dette er nu flyttet tilbage én gang. Jeg behøver ikke længere at-hvis du nogensinde nær latterligt lange linjer, så de 4 byte kan hjælpe, og også mere til venstre noget er, jo mindre overvældet du føle, hvis lignende-okay, jeg er nødt til at huske Jeg er i øjeblikket i en while-løkke inde i en ellers inde i en for-løkke. Overalt kan du gøre dette afkast med det samme, jeg kan godt lide. Det er helt frivilligt og ikke forventes på nogen måde. 

[Student] Skulle der være en størrelse - i fail tilstand? Fail betingelse her er vi undlod at realloc, så ja. Bemærk hvordan i fail tilstand, formodentlig medmindre vi gratis ting senere, er vi altid kommer til at mislykkes uanset hvor mange gange vi forsøger at skubbe noget. Hvis vi holder skubbe, vi holder forøgelsen størrelse, selv om vi ikke sætte noget på stakken. Normalt vi ikke forøge størrelsen indtil efter at vi med succes har sat det på stakken. Vi ville gøre det, siger, enten her og her. Og så i stedet for at sige s.size ≤ kapacitet, er det mindre end kapaciteten, kun fordi vi flyttede, hvor alt var. 

Og husk, det eneste sted, vi eventuelt kunne returnere falsk er her, hvor realloc returneres null, og hvis du tilfældigvis huske standardfejlen måske du måske overveje dette en sag, hvor du ønsker at udskrive en standard fejl, så fprintf stderr i stedet for bare at udskrive direkte til standard ud. Igen, det er ikke en forventning, men hvis det er en fejl, skriv printf, så er du måske ønsker at gøre det udskrive til standard fejl i stedet for standard ud. 

Nogen der har noget andet at bemærke? Ja. [Student] Kan du gå over [uhørligt]? [Rob B.] Ja, det faktiske binariness af det eller bare hvad det er? [Student] Så du gange det med 2? [Rob B.] Ja, dybest set. I binær land, vi altid har vores sæt af cifre. Shifting denne venstre med 1 dybest set indsætter det her på den rigtige side. Tilbage til dette, bare huske, at alt i binær er en potens af 2, så dette repræsenterer 2 til 0, denne 2 til 1, denne 2 til 2. Ved at indsætte et 0 på højre side nu, bare vi skifter alt over. Hvad bruges til at være 2 til 0 er nu 2 til 1, 2 til 2. Den højre side, som vi indsatte nødvendigvis vil være 0, der giver mening. Hvis du nogensinde gang et tal med 2, er det ikke kommer til at ende op ulige, så 2 til 0 sted, bør være 0, og det er hvad jeg halv advaret om før, er, hvis du kommer til at flytte ud over antallet af bit i et helt tal, så denne 1 kommer til at ende med at gå ud. Det er den eneste bekymring, hvis du tilfældigvis beskæftige sig med virkelig store kapaciteter. Men på det tidspunkt, så du beskæftiger sig med en bred vifte af milliarder af ting, som måske ikke passer ind i hukommelsen alligevel. 

Nu kan vi komme til pop, der er endnu lettere. Du kunne gøre det sådan, hvis du tilfældigvis at pop en hel masse, og nu er du på halv kapacitet igen. Du kunne realloc at skrumpe den mængde hukommelse du har, men du behøver ikke at bekymre dig om det, er så den eneste realloc sagen vil være voksende hukommelse, aldrig faldende hukommelse, som vil gøre pop super nemt. Nu køer, der kommer til at være ligesom stakke, men den rækkefølge, du tager tingene ud er vendt. Det prototypiske eksempel på en kø er en linje, så jeg gætte, hvis du var engelsk, ville jeg have sagt et prototypisk eksempel på en kø er en kø. Så som en linje, hvis du er den første person på linje du forventer at være den første person ud af linjen. Hvis du er den sidste person i rækken, vil du være den sidste person, der serviceres. Vi kalder det FIFO mønster, hvorimod stakken var LIFO mønster. Disse ord er temmelig universelle. 

Ligesom stakke og i modsætning til arrays, typisk køer giver ikke adgang til elementer i midten. Her en stak, vi har push og pop. Her vil vi tilfældigvis har kaldt dem enqueue og dequeue. Jeg har også hørt dem kaldt skift og ophæve omskiftningen. Jeg har hørt folk sige push og pop til også gælder for køer. Jeg har hørt indsætte, fjerne, så skubbe og pop, hvis du taler om stakke, er du skubber og popping. Hvis du taler om køer, kan du vælge de ord, du vil bruge for indsættelse og fjernelse, og der er ikke enighed om, hvad det skal hedde. Men her har vi enqueue og dequeue. Nu, at struct ser næsten identisk med stakken struct. Men vi er nødt til at holde styr på hovedet. Jeg gætter det siger hernede, men hvorfor har vi brug hovedet? Prototyperne er grundlæggende identiske at skubbe og pop. Du kan tænke på det som push og pop. Den eneste forskel er pop er på vej tilbage-i stedet for den sidste, er det tilbage den første. 2, 1, 3, 4, eller noget. Og her er starten. Vores kø er helt fyldt, så der er fire elementer i det. Slutningen af ​​vores kø er i øjeblikket 2, og nu skal vi gå for at indsætte noget andet. 

Når vi ønsker at indsætte, at noget andet, hvad vi gjorde for stakken versionen er vi udvidet vores blok af hukommelse. Hvad er problemet med dette? [Student] Du flytter 2. Hvad jeg sagde før omkring slutningen af ​​køen, Dette giver ingen mening, at vi begynder med 1, så vi ønsker at dequeue 1, så dequeue 3 og derefter dequeue 4, så dequeue 2 og derefter dequeue denne ene. Vi kan ikke bruge realloc nu, eller i det mindste, skal du bruge realloc på en anden måde. Men du burde nok ikke bare bruge realloc. Du er nødt til manuelt at kopiere din hukommelse. 

Der er to funktioner til at kopiere hukommelsen. Der er memcopy og memmove. Jeg er i øjeblikket læser man-siderne for at se, hvilken en du vil ønsker at bruge. Okay, memcopy, forskellen er at memcopy og memmove, et håndtag tilfældet korrekt hvor du kopierer ind i en region, der sker for at overlappe regionen du kopierer fra. Memcopy ikke håndtere det. Memmove gør. Du kan tænke på problemet som- lad os sige jeg ønsker at kopiere denne fyr, Disse fire til denne fyr over. I sidste ende array hvad skal se ud efter kopien er 2, 1, 2, 1, 3, 4, og derefter nogle ting i slutningen. Men dette er afhængig af den rækkefølge, som vi faktisk kopiere, for hvis vi ikke mener, at den region, vi kopierer ind overlapper den, vi kopierer fra, så vi kan gøre som starter her, skal du kopiere 2 ind det sted, vi ønsker at gå, derefter flytte vores pointers fremad. 

Nu vil vi være her og her, og nu vil vi kopiere denne fyr over denne fyr og flytte vores pointers fremad. Hvad vi kommer til at ende med at få, er 2, 1, 2, 1, 2, 1 stedet for den passende 2, idet 1, 2, 1, 3, 4 2, 1 tilsidesatte oprindelige 3, 4. Memmove håndterer det korrekt. I dette tilfælde bare altid dybest set bruge memmove fordi den håndterer det korrekt. Det generelt udfører ikke nogen værre. Ideen er i stedet for at starte fra begyndelsen og kopiere denne måde ligesom vi lige gjorde her, det starter fra slutningen og kopierer ind, og i så fald, kan du aldrig har et problem. Der er ingen forestilling tabt. Brug altid memmove. Aldrig bekymre dig om memcopy. Og det er her, du bliver nødt til at særskilt memmove den indpakkede-around del af din kø. Ingen bekymringer, hvis ikke helt færdig. Det er sværere end stack, push, og pop. 

Nogen der har nogen kode, vi kan arbejde med? Selv hvis helt ufuldstændig? [Student] Ja, det er helt ufuldstændig, selv om. Helt ufuldstændig er fint, så længe vi-kan du gemme revision? Jeg glemmer, at hver eneste gang. Okay, ignorerer, hvad der sker, når vi er nødt til at ændre størrelsen på tingene. Helt ignorere resize. Forklar denne kode. Jeg tjekker først og fremmest, hvis størrelse er mindre end kopien første og så efter det, jeg indsætter-jeg tager hovedet + størrelse, og jeg sørg for at det ombrydes omkring kapaciteten af ​​array, og jeg indsætte den nye streng i den position. Så jeg forøge størrelsen og returnere sandt. 

[Rob B.] Dette er absolut et af de tilfælde, hvor du vil ønsker at bruge mod. Enhver form for tilfælde, hvor du har indpakning omkring, hvis du tror indpakning omkring, Den umiddelbare tanke skal være mod. Som en hurtig optimering / gøre din kode én linje kortere, du opdager, at den linje umiddelbart efter denne ene er bare størrelse + +, så du flette det ind i denne linje, størrelse + +. Nu hernede, har vi sagen hvor vi ikke har nok hukommelse, så øger vi vores kapacitet med 2. Jeg gætte, du kunne have det samme problem her, men vi kan ignorere det nu, hvor hvis du har undladt at øge din kapacitet, så er du vil ønsker at nedsætte din kapacitet med 2 igen. En anden kort bemærkning er ligesom du kan gøre + =, du kan også gøre << =. Næsten alt kan gå før ligemænd, + =, | =, & =, << =. Char * ny er vores nye blok af hukommelse. Åh, herovre. 

Hvad tror folk om den type af vores nye blok af hukommelse? [Student] Det bør være char **. Tænker tilbage til vores struct op her, strings er det, vi omfordeler. Vi gør en hel ny dynamisk oplagring af de elementer i køen. Hvad vi kommer til at tildele til dine strenge er, hvad vi mallocing lige nu, og så ny bliver en char **. Det kommer til at være et array af strenge. Så hvad der er tilfældet i henhold til hvilken vi skal returnere falsk? [Student] Skal vi gøre det char *? [Rob B.] Ja, god opkald. [Student] Hvad var det? [Rob B.] Vi ønskede at gøre størrelsen af ​​char *, fordi vi er ikke længere Dette ville faktisk være et meget stort problem, fordi sizeof (char) ville være 1. Sizeof char * kommer til at være 4, så en masse gange, når du arbejder med int'er, du har tendens til at slippe af sted med det, fordi størrelsen af ​​int og størrelsen af ​​int * på en 32-bit system vil være det samme. Men her, sizeof (char) og sizeof (char *) skal nu være det samme. 

Hvad er den omstændighed, hvor vi vender tilbage falsk? [Student] New er null. Ja, hvis nye er null, vi vender tilbage falsk, og jeg har tænkt mig at smide ned her- [Student] [uhørligt] [Rob B.] Ja, det er fint. Du kan enten gøre 2 gange kapacitet eller kapacitet shift 1 og derefter kun sætte den ned her eller hvad. Vi gør det, som vi havde det. Kapacitet >> = 1. Og du vil aldrig behøver at bekymre dig om at miste den 1 plads fordi du forlod forskydes med 1, så den 1 plads er nødvendigvis et 0, så højreforskydning med 1, er du stadig vil være fint. [Student] Har du brug for at gøre det før afkast? [Rob B.] Ja, det giver absolut ingen mening. 

Nu antager vi vil ende med at vende tilbage tro mod enden. Den måde, vi kommer til at gøre disse memmoves, vi er nødt til at være forsigtige med, hvordan vi gør dem. Er der nogen der har nogen forslag til, hvordan vi gør dem? Her er vores start. Uundgåeligt, vi ønsker at starte ved begyndelsen igen og kopiere ting i derfra, 1, 3, 4, 2. Hvordan gør du det? Først vil jeg nødt til at se på manden side for memmove igen. Memmove, rækkefølgen af ​​argumenterne er altid vigtig. Vi vil have vores destination først, source andet, størrelse tredjedel. Der er en masse funktioner, som vende kilde og destination. Destination, kilde tendens til at være konsekvent noget. Flyt, hvad er det tilbage? Den returnerer en pointer til destination, uanset af hvilken grund du måske ønsker det. Jeg kan billedet læse det, men vi ønsker at flytte ind i vores destination. 

Hvad er vores destination vil blive? [Student] New. [Rob B.] Ja, og hvor er vi kopierer fra? Det første, vi kopierer, er denne 1, 3, 4. Hvad er-det 1, 3, 4. Hvad er adressen på denne 1? Hvad er adressen på det 1? [Student] [uhørligt] [Rob B.] Head + adressen på det første element. Hvordan får vi det første element i array? [Student] kø. [Rob B.] Ja, q.strings. Husk her, vores hoved er 1. Darn det. Jeg synes bare det er magisk- Her vores hoved er 1. Jeg har tænkt mig at ændre min farve også. Og her er strenge. Det kan vi enten skrive det, som vi gjorde herovre med hoved + q.strings. En masse mennesker også skrive det & q.strings [hovedet]. Dette er ikke rigtig nogen mindre effektiv. Du kan tænke på det som du dereferere det og derefter få adressen på, men compileren vil oversætte det til, hvad vi havde før alligevel, q.strings + hoved. Uanset hvad du ønsker at tænke på det. 

Og hvor mange bytes ønsker vi at kopiere? [Student] Kapacitet - hoved. Kapacitet - hoved. Og så kunne du altid skrive et eksempel at regne ud, hvis det er rigtigt. [Student] Det skal divideres med 2 og derefter. Ja, så jeg gætte vi kunne bruge størrelse. Vi har stadig størrelse væren- bruger størrelse, vi har størrelse lig med 4. Vores størrelse er 4. Vores hoved er 1. Vi ønsker at kopiere disse 3 elementer. Det er den tilregnelighed kontrollere, at størrelse - hoved er korrekt 3. Og kommer tilbage her, ligesom vi sagde før, hvis vi brugte kapacitet, så vi er nødt til at dividere med 2 fordi vi allerede har øget vores kapacitet, så i stedet, vi kommer til at bruge størrelse. At kopier, del. Nu er vi nødt til at kopiere den anden del, den del, der er tilbage af starten. 

Det kommer til at memmove i hvad stilling? [Student] Plus size - hoved. Ja, så har vi allerede kopieret i størrelse - head bytes, og så, hvor vi ønsker at kopiere de resterende bytes er ny og derefter størrelse minus-godt, at antallet af bytes vi allerede har kopieret i. Og så hvor skal vi kopierer fra? [Student] Q.strings [0]. [Rob B.] Ja, q.strings. Vi kunne enten gøre & q.strings [0]. Det er væsentligt mindre udbredt end dette. Hvis det bare kommer til at være 0, så vil du tendens til at se q.strings. Det er, hvor vi kopierer fra. Hvor mange bytes har vi tilbage at kopiere? >> [Student] 10. Right. [Student] Har vi at formere 5 - 10 gange størrelsen af ​​bytes eller noget? Ja, så er det her, hvad vi helt præcist kopiering? [Student] [uhørligt] Hvad er den type af ting, vi kopiering? [Student] [uhørligt] Ja, så den char * s at vi kopierer, ved vi ikke, hvor de kommer fra. Tja, hvor de peger på, ligesom strengene, vi ender med at skubbe det over på køen eller enqueuing på køen. Når disse kommer fra, har vi ingen idé. Vi skal bare holde styr på char * s selv. Vi ønsker ikke at kopiere størrelse - head bytes. Vi ønsker at kopiere størrelse - head char * s, så vi vil formere dette ved sizeof (char *). Samme hernede, hoved * sizeof (char *). 

[Student] Hvad med [uhørligt]? Denne ret her? [Student] Nej, under det, størrelsen - hovedet. [Rob B.] Denne ret her? Pointer aritmetik. Hvordan pointer aritmetik kommer til at arbejde, er det automatisk formerer af størrelsen af ​​den type, som vi har at gøre med. Ligesom herovre, ny + (størrelse - hoved) er præcis svarer til & ny [size - head] indtil vi forventer at det skal fungere korrekt, for hvis vi har at gøre med en int array, så gør vi ikke indeks ved int- eller hvis det er af størrelse på 5 og du ønsker det 4. element, så vi indeks til int array [4]. Du lad være-[4] * størrelse int. Der håndterer det automatisk, og denne sag er bogstaveligt talt ækvivalent, så konsollen syntaks er bare at blive konverteret til dette, så snart du kompilere. Det er noget, du skal være forsigtig med at når du tilføjer størrelse - head du tilføjer ikke en byte. Du tilføje en char *, som kan være en byte eller whatever. 

Andre spørgsmål? Okay, dequeue vil være lettere. Jeg vil give dig et minut til at gennemføre. Åh, og jeg tror det er den samme situation, hvor hvad det enqueue sag, hvis vi enqueuing null, måske vi ønsker at håndtere det, måske gør vi ikke. Vi vil ikke gøre det igen her, men samme som vores stak sagen. Hvis vi sætte mellemlager null, måske vi ønsker at se bort fra det. Nogen der har noget kode jeg kan trække op? [Student] Jeg har kun dequeue. Version 2 er, at-okay. Du ønsker at forklare? [Student] Først skal du sørge for at der er noget i køen og at størrelsen er på vej ned med 1. Du er nødt til at gøre det, og så skal du returnere hovedet og derefter flytte hovedet op 1. Okay, så der er et hjørne tilfælde vi nødt til at overveje. Yeah. [Student] Hvis dit hoved er på det sidste element, så du ikke ønsker hoved at pege uden for array. 

Ja, så snart hoved hits i slutningen af ​​vores array, når vi dequeue, bør vores hovedet modded tilbage til 0. Desværre kan vi ikke gøre det i én arbejdsgang. Jeg tror den måde, jeg ville sandsynligvis ordne det er dette vil være en char *, hvad vi vender tilbage, uanset din variabelnavn ønsker at være. Så vi ønsker at mod hovedet ved vores kapacitet og derefter vende tilbage RET. En masse mennesker her de måske gør- dette er tilfældet for-vil du se folk gøre, hvis hoved er større end kapaciteten, gøre hoved - kapacitet. Og det er bare arbejder omkring hvad mod er. Hoved mod = kapacitet er meget renere af en indpakning rundt, end hvis hoved er større end kapaciteten hoved - kapacitet. 

Spørgsmål? Okay, det sidste vi har tilbage er vores linkede liste. Du kan blive brugt til nogle af de linkede liste adfærd, hvis du gjorde knyttet lister i dine hash tabeller, hvis du gjorde en hash tabel. Jeg stærkt anbefale gør en hash tabel. Du har måske allerede gjort en Trie, men forsøg er mere vanskeligt. I teorien, de er asymptotisk bedre. Men bare se på det store bord, og forsøger aldrig gøre det bedre, og de fylder mere hukommelse. Alt om prøver ender med at blive værre for mere arbejde. Det er, hvad David Malan løsning altid er er han altid stillinger hans Trie løsning, og lad os se, hvor han i øjeblikket er. Hvad var han under, David J? Han er nr. 18, så det er ikke frygtelig dårlig, og det kommer til at blive en af ​​de bedste prøver du kan tænke på eller en af ​​de bedste prøver af en trie. Er det ikke engang hans oprindelige løsning? Jeg har lyst til Trie-løsninger tendens til at være mere i denne række af RAM forbrug. 

Gå ned til den øverste top, og RAM forbrug er i det indre cifre. Gå ned mod bunden, og så du begynder at se prøver hvor du får absolut massiv RAM forbrug, og forsøg er vanskeligere. Ikke helt det værd, men en lærerig oplevelse, hvis du gjorde en. Den sidste ting er vores linkede liste, og disse tre ting, stakke, køer, og sammenkædede lister, enhver fremtidig ting du nogensinde gøre i datalogi vil antage, at du har kendskab til disse ting. De er bare så grundlæggende for alt. 

Forbundet lister, og her har vi en enkeltvis forbundet liste vil være vores implementering. Hvad betyder enkeltvis forbundet betyder i modsætning til dobbelt forbundet? Ja. [Student] Det er kun henvist til den næste pointer i stedet for til pegepinde, som det sidste før den og den ene efter den. Ja, så i billedformat, hvad gjorde jeg bare gøre? Jeg har to ting. Jeg har billede og billede. I billedformat, vores enkeltvis hægtede lister uundgåeligt, at vi har en form for pointer til hovedet på vores liste, og derefter inden for vores liste, vi bare har pegepinde, og måske dette peger til null. Det kommer til at være din typiske tegning af en enkeltvis linket liste. En dobbelt linkede liste, kan du gå baglæns. Hvis jeg giver dig nogen knude på listen, så kan du nødvendigvis komme til ethvert andet knudepunkt i listen hvis det er en dobbelt forbundet liste. Men hvis jeg får dig den tredje knude på listen, og det er en enkeltvis linket liste, ingen måde, du nogensinde vil komme til den første og anden noder. Og der er fordele og negative, og en oplagt en er du fylder mere størrelse, og du er nødt til at holde styr på, hvor disse ting peger nu. Men vi kun interesserer os enkeltvis forbundet. 

Et par ting vi bliver nødt til at gennemføre. Din typedef struct node, int i: struct node * næste; node. Denne typedef skulle brændes ind i jeres sind. Quiz 1 skal gerne give en typedef af en linket liste node, og du bør være i stand til straks at kradse det ned uden at tænke over det. Jeg gætte et par spørgsmål, hvorfor har vi brug struct her? Hvorfor kan vi ikke sige node *? [Student] [uhørligt] Yeah. Det eneste, der definerer et knudepunkt som en ting er typedef selv. Men som i dette punkt, når vi er slags parsing gennem denne struct node definition Vi har ikke afsluttet vores typedef endnu, så da den typedef er ikke færdig, knudepunktet findes ikke. Men struct node gør, dette knudepunkt og i her, Dette kunne også kaldes noget andet. Dette kunne kaldes n. Det kunne kaldes linkede liste node. Det kunne kaldes noget. Men denne struct node behov for at anvende det samme som denne struct node. Hvad du kalder dette skal også være her, og så besvarer også det andet punkt i spørgsmålet hvilket er grunden til, en masse gange, når du ser struct og typedefs af struct, vil du se anonyme strukturer, hvor du bare se typedef struct, gennemførelsen af ​​struct, ordbog, eller hvad. 

Hvorfor her behøver vi at sige knude? Hvorfor kan det ikke være en anonym struct? Det er næsten det samme svar. [Student] Du er nødt til at henvise til det i struct. Ja, inden for den struct, skal du henvise til struct selv. Hvis du ikke giver den struct et navn, hvis det er en anonym struct, kan du ikke henvise til den. Og sidst men ikke mindst disse bør alle være noget ligetil, og de bør hjælpe dig indse, hvis du skriver det ned at du laver noget galt, hvis den slags ting ikke giver mening. Sidst, men ikke mindst, hvorfor det skal være struct node *? Hvorfor kan det ikke bare være struct node næste? [Student] Pointer til næste struct. Det er uundgåeligt, hvad vi ønsker. Hvorfor kunne det aldrig være struct node næste? Hvorfor skal det være struct node * næste? Yeah. [Student] Det er ligesom en uendelig løkke. Yeah. [Student] Det ville alle være i ét. Ja, tænk bare på, hvordan vi ville gøre størrelse eller noget. Størrelse af en struct er dybest set + eller - nogle mønster her eller der. Det er dybest set kommer til at være summen af ​​størrelserne af de ting i struct. Denne ret her, uden at ændre noget, er størrelsen vil være let. Størrelse af struct node bliver størrelse i + størrelse næste. Størrelse af i kommer til at være 4. Størrelse af næste bliver 4. Størrelse af struct node bliver 8. Hvis vi ikke har den *, tænker på sizeof, så sizeof (i) vil være 4. Størrelse af struct node næste bliver størrelse i + størrelse struct node næste + Størrelse i + størrelse struct node næste. Det ville være en uendelig løkke af knudepunkter. Dette er grunden til dette er, hvordan tingene skal være. 

Igen, definitivt huske, at eller i det mindste forstå det nok, at du kan være i stand til Grunden igennem, hvad det skal se ud. De ting, vi vil ønsker at gennemføre. Hvis længden af ​​liste- du kunne snyde og holde omkring en global længde eller noget, men vi vil ikke gøre det. Vi kommer til at tælle længden af ​​listen. Vi har indeholder, så det er dybest set ligesom en søgning, så vi har en linket liste af heltal at se, om denne heltal er i den linkede liste. Prepend vil indsætte ved begyndelsen af ​​listen. Append vil indsætte i slutningen. Insert_sorted vil indsætte i den sorterede placering på listen. Insert_sorted slags forudsætter, at du aldrig har brugt prepend eller vedhæfte i dårlige måder. 

Insert_sorted når du gennemføre insert_sorted- lad os sige, at vi har vores linkede liste. Dette er, hvad det i øjeblikket ser ud, 2, 4, 5. Jeg ønsker at indsætte 3, så længe selve listen allerede er sorteret, det er let at finde, hvor 3 hører til. Jeg starter ved 2. Okay, 3 er større end 2, så jeg vil holde i gang. Åh, 4 er for stor, så jeg ved 3 kommer til at gå i mellem 2 og 4, og jeg er nødt til at fastsætte pointere og alt det der. Men hvis vi ikke strengt bruge insert_sorted, gerne lad os bare sige jeg tilføjes i begyndelsen 6, så min linkede liste vil blive det. Det er nu giver ingen mening, så for insert_sorted, kan du bare gå ud at listen er sorteret, selvom operationer findes hvilket kan få det til at ikke blive sorteret, og det er det. Find en nyttig indsats, så dem er de vigtigste ting, du bliver nødt til at gennemføre. 

For nu, tage et minut til at gøre længde og indeholder, og de bør være relativt hurtig. Nærmer lukketid, så alle har noget til længde eller indeholder? De kommer til at være næsten identiske. [Student] Længde. Lad os se, revision. Okay. Du ønsker at forklare? [Student] Jeg har lige oprette en pegepind node og initialisere den til først, hvilket er vores globale variabel, og så vil jeg tjekke for at se, om det er nul, så jeg ikke får en seg fejl og returnere 0, hvis det er tilfældet. Ellers kan jeg sløjfe gennem, holde styr på i heltal hvor mange gange jeg har åbnet det næste element i listen og i samme tilvækst operation også adgang at de faktiske element, og så har jeg hele tiden gøre check for at se, om det er null, og hvis det er null, så det afbryder og bare returnerer antallet af elementer, jeg har adgang til. 

[Rob B.] Er der nogen der har nogen kommentarer til noget? Det ser fint korrekthed klogt. [Student] Jeg tror ikke, du har brug for node == null. Ja, så hvis node == null return 0. Men hvis node == null derefter dette-oh, der er en korrekthed spørgsmål. Det var bare du vender tilbage i, men det er ikke i omfang lige nu. Du skal bare have int i, så i = 0. Men hvis node er nul, så jeg stadig vil være 0, og vi vil vende tilbage 0, så denne sag er identisk. En anden almindelig er at holde angivelsen af node inde i for-løkken. Man kan sige, åh, nej. Lad os holde det som dette. Jeg ville nok sætte int i = 0 her, så node * node = første herinde. Og det er nok how-komme af med denne nu. Dette er sandsynligvis, hvordan jeg ville have skrevet det. Du kan også-se på det på denne måde. Dette for-løkke struktur lige her bør være næsten lige så naturligt for dig som for int i = 0 i er mindre end længden af ​​array-i + +. Hvis det er hvordan du gentage over et array, dette er, hvordan du gentage over en linket liste. 

Dette bør være anden natur på et tidspunkt. Med det i tankerne, vil dette være næsten det samme. Du vil ønsker at gentage over en sammenkædet liste. Hvis node-jeg har ingen idé om, hvad den værdi kaldes. Node in. Hvis værdien på det pågældende node = jeg vender tilbage sandt, og det er det. Bemærk, at den eneste måde, vi nogensinde vender tilbage falsk er, hvis vi gentage over hele linkede liste og aldrig returnere sandt, så det er hvad dette betyder. Som en side bemærkning, vi sandsynligvis ikke komme til at tilføje eller tilføjes i begyndelsen. 

Quick sidste note. Hvis du ser den statiske søgeord, så lad os sige static int count = 0, så gør vi tæller + +, kan du dybest set tænke på det som en global variabel, selvom jeg lige har sagt dette er ikke, hvordan vi skal gennemføre længde. Jeg gør dette her, og derefter tælle + +. Nogen måde vi kan indtaste en knude i vores linkede liste, vi forøgelse vores tæller. Pointen i dette er, hvad den statiske nøgleordet betyder. Hvis jeg bare havde int count = 0, der ville være en regelmæssig gammel global variabel. Hvad static int count betyder er, at det er en global variabel for denne fil. Det er umuligt for en anden fil, gerne tænke 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å noget i speller.c kan tilgås på dictionary.c og omvendt. Globale variabler er tilgængelige for enhver. C fil, men statiske variable er kun tilgængelige inde fra selve filen, så indersiden af ​​stavekontrol eller indersiden af ​​dictionary.c, det er lidt hvordan jeg ville erklære min variabel for størrelsen af ​​mit array eller størrelsen af ​​mit antal ord i ordbogen. Da jeg ikke ønsker at erklære en global variabel, som alle har adgang til, Jeg har egentlig kun bekymrer sig om det til mine egne formål. 

Det gode ved dette er også hele navnet kollision stuff. Hvis en anden fil forsøger at bruge en global variabel kaldet count, tingene går meget, meget forkert, så dette pænt holder tingene sikkert, og kun du kan få adgang til det, og ingen andre kan, og hvis en anden erklærer en global variabel kaldet tælle, så vil det ikke forstyrre din statiske variabel kaldet tæller. Det er, hvad statiske er. Det er en fil global variabel. 

Spørgsmål om noget? Alle sæt. Bye. [CS50.TV]