[Powered by Google Translate] [Afsnit 6: Mindre Comfortable]
[Nate Hardison] [Harvard University]
[Dette er CS50.] [CS50.TV]
Ok. Velkommen til afsnit 6.
I denne uge vil vi tale om datastrukturer i snit,
primært fordi denne uges problem indstillet på spellr
gør en hel masse forskellige datastruktur udforskning.
Der er en masse forskellige måder, du kan gå med problemet sæt,
og jo flere datastrukturer du kender, jo mere seje ting, du kan gøre.
>> Så lad os komme i gang. Først vil vi snakke om stakke,
stakken og kø datastrukturer, som vi kommer til at snakke om.
Stakke og køer er virkelig nyttige, når vi begynder at tale om grafer,
som vi ikke kommer til at gøre så meget af lige nu.
Men de er rigtig gode til at forstå en af ​​de store fundamentale datastrukturer i CS.
Beskrivelsen i det problem indstillede specifikation,
hvis du trækker den op, fortæller om stacks som beslægtet med
bunken af ​​spisning bakker, som du har i cafeteriet ved spisesale
hvor når spise personale kommer og sætter de spise bakker ud, efter at de har renset dem,
De stable dem oven på hinanden.
Og så når børnene kommer i at få mad,
de trække bakkerne ud, først den øverste, så den ene under den, så den ene under dette.
Så i realiteten er den første bakke, spise personale lagde sidste, der bliver taget.
Den sidste at spise personale sat på er det første, der bliver taget ud til middag.
I det problem apparatets spec, du som kan hente, hvis du ikke allerede har gjort det,
vi taler om at modellere en stak data stucture bruge denne form for struct.
>> Så hvad vi har her, det svarer til, hvad der blev præsenteret i foredrag,
undtagen i foredrag vi forelagde dette med int'er i modsætning til char * s.
Dette vil være en stak, der gemmer hvad?
Daniel? Hvad skal vi opbevare i denne stak?
[Daniel] Strings? >> Vi gemmer strenge i denne stak, præcis.
Alt hvad du behøver at have for at skabe en stak er et array
af en bestemt egenskab, som i dette tilfælde
kapacitet vil være i alle caps, fordi det er en konstant.
Og derefter ud over arrayet, er alt hvad vi nødt til at spore den aktuelle størrelse af matrixen.
Én ting at bemærke her, at er lidt cool
er, at vi skaber den stablede datastruktur oven på en anden datastruktur, arrayet.
Der er forskellige måder at gennemføre stakke.
Vi vil ikke gøre det helt endnu, men forhåbentlig efter at gøre den sammenkædede-list problemer,
du vil se, hvordan du nemt kan implementere en stak på toppen af ​​en linket liste så godt.
Men for nu, vil vi holde os til arrays.
Så igen, alt hvad vi behøver er en matrix, og vi bare nødt til at spore størrelsen af ​​array.
[Sam] Beklager, hvorfor er det, at du sagde stakken er på toppen af ​​strengene?
For mig ser det ud som strengene ligger inden for stakken.
[Hardison] Yeah. Vi skaber, vi tager vores array datastruktur -
Det er et godt spørgsmål. Så spørgsmålet er, hvorfor, for de mennesker, der ser dette online,
hvorfor siger vi, at stakken er på toppen af ​​strengene,
fordi her ser det ud til strengene er inde i stakken?
Som er helt tilfældet.
Hvad jeg henviste til, var, at vi har fået et array datastruktur.
Vi har fået en række char * s, denne vifte af strenge,
og vi vil tilføje til, at for at skabe den stablede datastruktur.
>> Så en stak er lidt mere kompliceret end et array.
Vi kan bruge et array til at bygge en skorsten.
Så det er, hvor vi siger, at stakken er bygget oven på et array.
Ligeledes, som jeg sagde tidligere, kan vi bygge en stak på toppen af ​​en linket liste.
I stedet for at bruge et array til at holde vores elementer,
vi kunne bruge en sammenkædet liste til at holde vores elementer og bygge stakken omkring det.
Lad os gennemgå et par eksempler, se på noget kode,
for at se, hvad der rent faktisk sker her.
Til venstre, har jeg smidt ned, hvad der stak struct ville se ud i hukommelsen
hvis kapaciteten # blev defineret til at være fire.
Vi har vores fire-element char * array.
Vi har strings [0], strings [1], strings [2], strings [3],
og så det sidste plads til vores størrelse heltal.
Giver det mening? Okay.
Dette er, hvad der sker, hvis det, jeg gør til højre,
som vil være min kode, er at bare erklære en struct, en stablet struct kaldet s.
Det er, hvad vi får. Det fastlægger dette fodaftryk i hukommelsen.
Det første spørgsmål her er, hvad er indholdet af denne stak struct?
Lige nu er de ingenting, men de er ikke helt ingenting.
De er denne form for skrald. Vi har ingen idé om, hvad der er i dem.
Når vi erklærer stack s, er vi bare at smide det ned på toppen af ​​hukommelsen.
Det er lidt ligesom at erklære int i og ikke initialisere det.
Du ved ikke, hvad der er derinde. Du kan læse, hvad der er derinde,
men det kan ikke være super nyttige.
Én ting du vil altid huske at gøre, er initialisere hvad der skal initialiseres.
I dette tilfælde vil vi initialisere størrelse at være nul,
fordi det kommer til at vise sig at være meget vigtigt for os.
Vi kunne gå videre og initialisere alle pegepinde, alle char * s,
at være nogle forståelige værdi, sandsynligvis null.
Men det er ikke helt nødvendigt, at vi gør det.
>> Nu er de to vigtigste operationer på stakke er?
Nogen husker fra foredrag hvad du gør med stakke? Ja?
[Stella] Skubbe og popping? >> Præcis.
Pushing og popping er de to vigtigste operationer på stakke.
Og hvad betyder skub gøre? >> Det sætter noget på toppen
af stakken, og derefter popping tager det ud.
[Hardison] Præcis. Så skubber skubber noget på toppen af ​​stakken.
Det er ligesom spise personale sætte en spisestue bakke ned på tælleren.
Og popping tager en spise bakke ud af stakken.
Lad os gå gennem et par eksempler på, hvad der sker
når vi presser tingene ned i stakken.
Hvis vi skulle til at skubbe strengen 'hello' på vores stack,
dette er, hvad vores diagram ville se ud nu.
Se hvad der sker?
Vi pressede ind i den første del af vores strenge opstilling
og vi forøgede vores størrelse tæller at være 1.
Så hvis vi ser på forskellen mellem de to dias, her var 0, her er før push.
Her er efter push.
Før push,. Efter push
Og nu har vi et element i vores stak.
Det er strengen "hello", og det er det.
Alt andet i arrayet, i vores strings matrix, stadig er skrald.
Vi har ikke initialiseret det.
Lad os sige, at vi skubber en anden streng på vores stack.
Vi kommer til at skubbe "verden" på dette tidspunkt.
Så du kan se "verden" her går på toppen af ​​"hello",
og størrelsen tæller går op til 2.
Nu kan vi skubbe "CS50", og der vil gå på toppen igen.
Hvis vi går tilbage, kan du se, hvordan vi skubbe ting på toppen af ​​stakken.
Og nu får vi at pop.
Når vi dukkede noget ud af stakken, hvad skete der?
Nogen se forskellen? Det er temmelig subtil.
[Student] Størrelsen. >> Ja, størrelsen ændret.
>> Hvad ville du have forventet at ændre?
[Student] De strenge, også. >> Højre. Strengene også.
Det viser sig, at når du gør det på denne måde,
fordi vi ikke kopiering af elementerne i vores stak,
vi faktisk ikke behøver at gøre noget, og vi kan bare bruge den størrelse
at holde styr på antallet af ting i vores array
så når vi pop igen, igen vi bare formindske vores størrelse ned til 1.
Der er ingen grund til rent faktisk at gå ind og overskrive noget.
Kind of funky.
Det viser sig, at vi typisk bare lade tingene alene, fordi det er mindre arbejde for os at gøre.
Hvis vi ikke behøver at gå tilbage og overskrive noget, så hvorfor gøre det?
Så når vi pop to gange ud af stakken, alt det gør, er at formindske størrelsen et par gange.
Og igen, det er kun fordi vi ikke kopiere ting i vores stack.
Ja? Værsgo.
[Studerende, uforståelig] >> Og hvad sker der, når du skubber noget igen?
Når du trykker på noget igen, hvor er det hen?
Hvor går det hen, Basil? >> Into strings [1]? >> Højre.
Hvorfor det ikke gå ind strings [3]?
[Basil] Fordi det glemte, at der var noget i strings [1] og [2]?
[Hardison] Præcis. Vores stack væsentlige, "glemte" at det var at holde fast i noget som helst
i strings [1] eller strings [2], så når vi skubber "woot",
det bare sætter den ind i elementet ved strings [1].
Er der nogen spørgsmål om, hvordan det fungerer, på et grundlæggende niveau?
[Sam] Så det er ikke dynamisk på nogen måde, i beløb
eller i form af størrelsen af ​​stakken?
[Hardison] Præcis. Dette er - det punkt var, at dette ikke var en dynamisk growning stak.
Dette er en stak, der kan holde på de fleste, fire char * s, højst fire ting.
Hvis vi skulle forsøge at skubbe en femte ting, hvad tror du der skal ske?
[Studerende, uforståelige]
[Hardison] Præcis. Der er en række ting, der kunne ske.
Det kunne muligvis seg fejl, afhængigt af, hvad vi var -
præcis hvordan vi gennemføre back-end.
Det kunne overskrive. Det kunne have denne buffer overflow, som vi talte om i klassen.
Hvad ville være det mest oplagte ting, der kan blive overskrevet
hvis vi forsøgte at presse en ekstra ting på vores stak?
Så du nævnte en buffer overflow.
Hvad kan være ting, der ville få skrevet over eller trampet på
hvis vi overløb uheld ved at forsøge at skubbe en ekstra ting?
[Daniel, uforståelig] >> Muligt.
Men i første omgang kan der ske? Hvad hvis vi forsøgte at skubbe en fjerde ting?
Det kan overskrive den størrelse, i hvert fald med denne hukommelse diagram, som vi har.
>> I det problem indstillede specifikation, er der hvad vi kommer til at gennemføre i dag,
hvad vi ønsker at gøre, er bare returnere falsk.
Vores pushmetoden vil returnere en boolesk værdi,
og at boolean værdi vil være tilfældet, hvis push lykkes
og falsk, hvis vi ikke kan skubbe noget mere, fordi stakken er fuld.
Lad os gå gennem en lille smule af denne kodeks lige nu.
Her er vores push-funktion.
Vores push-funktion til en stak vil tage i strengen til at sætte på stakken.
Det kommer til at returnere true hvis strengen held blev skubbet
på stakken og falsk ellers.
Nogen forslag til hvad der kunne være en god første ting at gøre her?
[Sam] Hvis størrelse er lig med kapaciteten derefter vende tilbage falsk?
[Hardison] Bingo. Nice job.
Hvis størrelsen er den kapacitet, vi kommer til at returnere falsk.
Vi kan ikke sætte noget mere i vores stak.
Ellers ønsker vi at sætte noget på toppen af ​​stakken.
Hvad er "toppen af ​​stakken," i første omgang?
[Daniel] Størrelse 0? >> Size 0.
Hvad er toppen af ​​stakken efter der er én ting i stakken? Missy, kender du?
[Missy] One. >> Size er én, præcis. Du holde tilføje til den størrelse,
og hver gang du putter i det nye element til indeks størrelse i array.
Vi kan gøre det med den slags one-liner, hvis det giver mening.
Så vi har fået vores strenge array, vi kommer til at få adgang til det på den størrelse indeks,
og vi vil bare gemme vores char * derinde.
Bemærk at der er ingen snor kopiering foregår i her,
ingen dynamisk allokering af hukommelse?
Og så Missy opdraget hvad vi nu skal gøre,
fordi vi har gemt snoren på et passende sted i arrayet,
og hun sagde, at vi var nødt til at forøge størrelsen af ​​en, så vi er klar til det næste tryk.
Så vi kan gøre det med s.size + +.
På dette tidspunkt har vi skubbet ind i vores array. Hvad er det sidste, vi skal gøre?
[Student] Tilbage sandt. >> Returnere sandt.
Så det er ret simpelt, en temmelig simpel kode. Ikke for meget.
Når du har pakket dit hoved omkring hvordan stakken virker,
dette er temmelig enkel at anvende.
>> Nu er den næste del af denne popping en streng ud af stablen.
Jeg har tænkt mig at give jer lidt tid til at arbejde på dette en lille smule.
Det er næsten grundlæggende det modsatte af, hvad vi har gjort her i push.
Hvad jeg har gjort, er faktisk - oops.
Jeg er startet op på et apparat herovre, og i apparatet,
Jeg har trukket op på problemet sæt 5-specifikationen.
Hvis vi zoomer ind her, kan vi se, at jeg er ved cdn.cs50.net/2012/fall/psets/pset5.pdf.
Har du fyre downloadet denne kode, der er placeret her, section6.zip?
Ok. Hvis du ikke har gjort det, gøre det lige nu, virkelig hurtigt.
Jeg vil gøre det i min terminal vindue.
Jeg faktisk gjorde det op her. Yeah.
Ja, Sam? >> Jeg har et spørgsmål om, hvorfor sagde du s.string 's parentes af størrelse = str?
Hvad er str? Er den, der et eller andet sted før, eller - oh, i den char * str?
[Hardison] Ja, præcis. Det var argumentet. >> Åh, okay. Undskyld.
[Hardison] Vi angiver strengen til at skubbe i.
Det andet spørgsmål, der kan komme op at vi ikke virkelig tale om her var
vi tog for givet, at vi havde denne variabel kaldet s
der var i omfang og tilgængelige for os.
Vi tog for givet, at s var denne stak struct.
Så ser tilbage på denne push-kode,
du kan se, at vi gør ting med denne streng, der fik vedtaget i
men så lige pludselig, vi adgang s.size, ligesom, hvor kom s komme fra?
I den kode, vi kommer til at se på, i afsnittet arkiv
og så de ting, du vil gøre i dit problem sætter,
vi har lavet vores stak konstruere en global variabel
så vi kan få adgang til den i alle vores forskellige funktioner
uden at skulle manuelt passere den rundt og videregive det som reference,
gøre alt den slags ting til det.
Vi er bare snyder en lille smule, hvis du vil, for at gøre tingene pænere.
Og det er noget, vi laver her, fordi det er for sjov, er det lettere.
Ofte vil du se folk gøre dette, hvis de har en stor datastruktur
, der bliver opereret i løbet af deres program.
>> Lad os gå tilbage over til apparatet.
Havde alle held få section6.zip?
Alle unzip det ved hjælp lyne section6.zip?
Hvis du går ind i sektion 6 bibliotek -
aah, over det hele -
og du liste hvad der er i her, kan du se at du har fået tre forskellige. C-filer.
Du har en kø, en SLL, der er enkeltvis-linkede liste, og en stak.
Hvis du åbner op stack.c,
du kan se, at vi har fået denne struct defineret for os,
den nøjagtige struct som vi lige har talt om i dias.
Vi har vores globale variabel for stakken,
vi har fået vores push-funktion,
og så har vi vores pop funktion.
Jeg vil sætte koden for skubbe op på objektglasset her,
men hvad jeg gerne vil have jer til at gøre, er, at det bedste af dine evner,
gå og gennemføre pop-funktionen.
Når du har gennemført det, kan du samle dette med make stack,
og derefter køre den resulterende stak eksekverbare,
og der vil køre hele denne test-kode hernede, der er i main.
Og main tager sig af rent faktisk at gøre det push og pop opkald
og sikre, at alt går igennem okay.
Det er også initialiserer stakstørrelsen lige her
så du ikke behøver at bekymre dig om at initialisere det.
Du kan antage, at det har været korrekt initialiseret
af den tid, du har adgang til den i pop-funktionen.
Giver det mening?
Så her går vi. Der er push-koden.
Jeg vil give jer 5 eller 10 minutter.
Og hvis du har spørgsmål i mellemtiden, mens du kodning,
kan du bede dem højt.
Så hvis du kommer til et springende punkt, bare spørg.
Lad mig vide, lad alle andre vide.
Arbejd med din nabo også.
[Daniel] Vi er lige gennemføre pop lige nu? >> Bare pop.
Selvom du kan kopiere gennemførelsen af ​​push, hvis du vil
således at testen vil arbejde.
Fordi det er svært at teste tingene komme ind -
eller, det er svært at teste affyret ting ud af en stak, hvis der ikke er noget i stakken til at begynde med.
>> Hvad er pop formodes at være tilbage? Elementet fra toppen af ​​stakken.
Det er meningen at få elementet væk fra toppen af ​​stakken
og derefter dekrementere størrelsen af ​​stakken,
og nu har du mistet element på toppen.
Og så skal du returnere element på toppen.
[Studerende, uforståelig]
[Hardison] Så hvad sker der, hvis du gør det? [Studerende, uforståelig]
Hvad ender sker, er du sandsynligvis få adgang til enten
et element, der ikke er blevet initialiseret endnu, så din beregning
hvor det sidste element er er slukket.
Så her, hvis du bemærker, i tryk, vi adgang strenge på s.size element
fordi det er et nyt indeks.
Det er den nye toppen af ​​stakken.
Betragtninger i pop, er s.size vil være den næste plads,
den plads, der er på toppen af ​​alle elementer i din stack.
Så den øverste element er ikke s.size,
men snarere, det er under den.
>> Den anden ting at gøre, når du - i pop,
er du nødt til at formindske størrelsen.
Hvis du kan huske tilbage til vores lille diagram lige her,
virkelig, det eneste, vi så ske når vi kaldes pop
var, at denne størrelse faldt først til 2, derefter til 1.
Så når vi pressede et nyt element på, ville det gå på på det rigtige sted.
[Basil] Hvis s.size er 2, så ville det ikke gå til element 2,
og så ville du ønsker at pop dette element fra?
Så hvis vi gik til - >> Så lad os se på det igen.
Hvis dette er vores stak på dette tidspunkt
og vi kalder pop,
på hvilket indeks er det øverste element?
[Basil] På 2, men det kommer til at poppe 3. >> Højre.
Så det er, hvor vores størrelse er 3, men vi ønsker at pop elementet i indeks 2.
Det er den typiske form for off med en, som du har med nul-indeksering af arrays.
Så du ønsker at pop det tredje element, men det tredje element er ikke i indeks 3.
Og grunden til at vi ikke behøver at gøre det minus 1 når vi skubber
er fordi lige nu, bemærker du, at det øverste element,
hvis vi presse noget andet på stakken ved dette punkt,
vi ønsker at skubbe det på indeks 3.
Og det bare så sker det, at størrelsen og indeksene linje op, når du presser.
>> Hvem har en arbejdsgruppe stak gennemførelse?
Du har fået en arbejdsgruppe stak en. Har du pop arbejder endnu?
[Daniel] Ja. Det tror jeg.
>> Programmet kører og ikke seg forkastning, det udskrivning ud?
Betyder det udskrive "succes", når du kører det?
Yeah. Gør stable, kør det, hvis den udskriver "succes" og ikke går boom,
så alt er godt.
Ok. Lad os gå over til apparatet virkelig hurtigt,
og vi vil gå igennem dette.
Hvis vi ser på, hvad der sker her med pop,
Daniel, hvad der var den første ting, du gjorde?
[Daniel] Hvis s.size er større end 0..
[Hardison] Okay. Og hvorfor gjorde du det?
[Daniel] For at sikre at der var noget inde i stakken.
[Hardison] Right. Du ønsker at teste for at sikre, at s.size er større end 0;
ellers, hvad vil du have ske?
[Daniel] Return null? >> Return null, præcis.
Så hvis s.size er større end 0. Så hvad skal vi gøre?
Hvad gør vi, hvis stakken ikke er tom?
[Stella] Du dekrementere størrelse? >> Du dekrementere størrelse, okay.
Så hvordan gjorde du det? >> S.size--.
[Hardison] Great. Og hvad gjorde du?
[Stella] Og så sagde jeg tilbage s.string [s.size].
[Hardison] Great.
Ellers kan du returnere null. Ja, Sam?
[Sam] Hvorfor behøver det ikke at være s.size + 1?
[Hardison] Plus 1? >> Yeah. >> Fik det.
[Sam] Jeg tænkte, fordi du tager 1 ud,
så du kommer til at vende tilbage ikke den, som de bad om.
[Hardison] Og det var netop, hvad vi talte om med hele spørgsmålet om 0 indeks.
Så hvis vi ind herovre.
Hvis vi ser på den fyr her kan du se, at når vi pop,
vi popping element ved indeks 2.
>> Så vi reducere vores størrelse først, derefter vores størrelse matcher vores indeks.
Hvis vi ikke formindske størrelsen først, så er vi nødt til at gøre størrelse -1 og derefter Decrement.
Great. All good?
Eventuelle spørgsmål om dette?
Der er en række forskellige måder til at skrive dette.
Faktisk kan vi gøre noget selv - vi kan gøre en one-liner.
Vi kan gøre en one-line afkast.
Så vi kan faktisk formindske før vi tilbage ved at gøre det.
Så sætte - før s.size.
Det gør linjen virkelig tæt.
Hvis forskellen mellem den -. Størrelse og s.size--
er, at denne postfix - de kalder det postfix fordi - kommer efter s.size--
betyder, at s.size evalueres med henblik på at finde indekset
ligesom det er, når denne linie udført,
og derefter dette - sker efter linjen bliver henrettet.
Efter elementet ved indeks s.size tilgås.
Og det er ikke det, vi vil, fordi vi ønsker, at decrement at ske først.
Othewise, vi kommer til at få adgang til array, effektivt, out of bounds.
Vi kommer til at få adgang til elementet oven den, vi faktisk ønsker at få adgang til.
Ja, Sam? >> Er det hurtigere eller bruger mindre RAM at gøre i én linje eller ej?
[Hardison] Helt ærligt, det er virkelig afhængig.
[Sam, uforståelig] >> Ja, det afhænger af. Du kan gøre compiler tricks
at få compileren til at erkende, at som regel, jeg kan forestille mig.
>> Så vi har nævnt en lille smule om denne compiler optimering stuff
at du kan gøre ved udarbejdelsen,
og det er den slags ting, at en compiler kan være i stand til at regne ud,
ligesom oh,, hey måske jeg kan gøre det hele i én arbejdsgang,
i modsætning til ilægning af størrelsen variabel i fra RAM,
dekrementere det, gemme det ud igen, og derefter lægger det tilbage i igen
at behandle resten af ​​denne operation.
Men typisk, nej, det er ikke den slags ting
der kommer til at gøre dit program betydeligt hurtigere.
Har du flere spørgsmål om stakke?
>> Så skubber og popping. Hvis du fyre vil prøve hacker udgave,
hvad vi har gjort i hacker-udgaven er faktisk gået
og gjorde denne stak vokse dynamisk.
Udfordringen er først og fremmest op her i push-funktion,
at finde ud af, hvordan man laver den opstilling vokse
som du holde skubbe flere og flere elementer på til stakken.
Det er faktisk ikke for meget ekstra kode.
Blot en opfordring til - du er nødt til at huske at få de opfordringer til malloc derinde korrekt,
og derefter finde ud af, når du kommer til at kalde realloc.
Det er en sjov udfordring, hvis du er interesseret.
>> Men for øjeblikket, lad os komme videre, og lad os tale om køer.
Rul igennem her.
Køen er en tæt søskende af stakken.
Så i stakken, var ting, der sættes i sidste
var de første ting for derefter at blive hentet.
Vi har fået denne sidste ind, først ud, eller LIFO, bestilling.
Betragtninger i køen, som du ville forvente fra når du står i kø
den første person til at komme på linje, den første ting at komme ind i køen,
er den første ting, der bliver hentet fra køen.
Køer er også ofte bruges, når vi har at gøre med grafer,
ligesom vi talte om kort med stakke,
og køer er også praktisk for en masse andre ting.
Én ting, der kommer op ofte forsøger at opretholde, for eksempel,
en sorteret liste af elementer.
Og du kan gøre det med et array. Du kan vedligeholde en sorteret liste over ting i et array,
men hvor det bliver tricky er så du altid nødt til at finde
det rette sted at indsætte den næste ting.
Så hvis du har en bred vifte af numre, 1 til 10,
og du derefter ønsker at udvide det til alle de numre 1 til 100,
og du får disse numre i tilfældig rækkefølge og forsøger at holde alt
sorteret som du går igennem, du ender med at skulle gøre en masse gearskift.
Med visse typer af køer og visse typer af underliggende datastrukturer,
du kan faktisk holde det forholdsvis enkelt.
Du behøver ikke at tilføje noget, og derefter bytte rundt det hele hver gang.
Heller ikke du skal gøre en masse forskydning af interne elementer omkring.
Når vi ser på en kø, du se, at - også i queue.c i afsnittet kode -
den struct, som vi har givet dig er virkelig ligner den struct at vi gav dig for en stak.
>> Der er én undtagelse til dette, og at en enkelt undtagelse
er, at vi har denne ekstra heltal kaldet hovedet,
og hovedet her er til at holde styr på forrest i køen,
eller det første element i køen.
Med en stak, var vi i stand til at holde styr på det element, vi var ved at hente,
eller toppen af ​​stakken, ved blot størrelse,
hvorimod med en kø, vi skulle beskæftige sig med modsatte ender.
Vi forsøger at tack ting på i slutningen, men derefter vende tilbage tingene forfra.
Så effektivt, med hovedet har vi indekset for begyndelsen af ​​køen,
og størrelsen giver os indekset for enden af ​​køen
således at vi kan hente ting fra hovedet og tilføje ting til halen.
Henviser til stablen, var vi altid kun beskæftiger sig med toppen af ​​stack'en.
Vi havde aldrig at få adgang til bunden af ​​stakken.
Vi har kun tilføjet ting til toppen og tog ting ud af toppen
så vi ikke brug for den ekstra felt inde i vores struct.
Betyder det generelt mening?
Ok. Ja, Charlotte? [Charlotte, uforståelig]
[Hardison] Det er et stort spørgsmål, og det var en, der kom op i forelæsning.
Måske gå gennem et par eksempler vil illustrere hvorfor
Vi ønsker ikke at bruge strings [0] som leder af køen.
>> Så forestille sig, at vi har vores kø, vi vil kalde det kø.
I begyndelsen, når vi lige har instantieres det
når vi har netop erklæret det, har vi ikke initialiseret noget.
Det er alt skraldet. Så selvfølgelig vil vi gerne sikre, at vi initialisere
både størrelse og hovedet felterne til at være 0, noget fornuftigt.
Vi kunne også gå videre og null de elementer i vores kø.
Og for at gøre dette diagram fit, bemærke, at nu er vores kø kan kun holde tre elementer;
hvorimod vores stak kunne rumme fire, kan vores kø kun holde tre.
Og det er bare for at gøre diagrammet pasform.
Det første, der sker her, er vi sætte mellemlager strengen "hej".
Og ligesom vi gjorde med stakken, noget forfærdeligt anderledes her,
vi smider strengen på på strings [0] og øg vores størrelse med 1.
Vi sætte mellemlager "bye", det bliver sat på.
Så det ligner en stak for det meste.
Vi startede her, nyt element, nyt element, størrelse holder går op.
Hvad sker der på dette punkt, når vi ønsker at dequeue noget?
Når vi ønsker at dequeue, som er det element, vi ønsker at dequeue?
[Basil] Strings [0]. >> Zero. Helt rigtigt, Basil.
Vi ønsker at slippe af med den første streng, denne ene, "hi".
Så hvad var den anden ting, der ændrede?
Læg mærke til, når vi dukkede noget ud af stakken, vi bare ændret størrelse,
men her har vi et par ting at forandring.
Ikke alene deling, men hovedet ændringer.
Det går tilbage til Charlotte synspunkt tidligere:
hvorfor har vi denne hoved så godt?
Giver det mening nu, Charlotte? >> Kind of.
[Hardison] Kind of? Så hvad der skete, da vi dequeued?
Hvad gjorde hovedet gøre det nu er interessant?
[Charlotte] Åh, fordi det ændret - okay. Jeg er med.
Fordi hovedet - hvor hovedet peger på ændringer med hensyn til placeringen.
Det er ikke længere altid nul indeks én. >> Ja, præcis.
Hvad der skete var, hvis dequeueing den høje element
blev gjort, og vi havde ikke dette hoved felt
fordi vi altid kaldte denne streng ved 0 indeks i spidsen for vores kø,
så vi er nødt til at flytte resten af ​​køen ned.
Vi er nødt til at flytte "bye" fra strings [1] til strings [0].
Og strings [2] ned til strings [1].
Og vi er nødt til at gøre det for hele listen af ​​elementer,
hele systemet af elementer.
Og når vi gør det med et array, der bliver virkelig dyrt.
Så her, det er ikke en big deal. Vi har bare tre elementer i vores array.
Men hvis vi havde en kø på tusind elementer eller en million elementer,
og så lige pludselig, vi begynde at lave en masse dequeue kalder alle i en løkke,
tingene virkelig kommer til at sætte farten ned, da det skifter alt ned konstant.
Du ved, skifte med 1, skift med 1, skift med 1, skift af 1.
I stedet skal vi bruge dette hoved, vi kalder det en "pointer", selvom det er egentlig ikke en pointer
i egentlig forstand, det er ikke en pointer type.
Det er ikke en int * eller en char * eller sådan noget.
Men det peger eller angiver lederen af ​​vores kø. Ja?
>> [Student] Hvordan dequeue vide at bare pop off uanset er i spidsen?
[Hardison] Hvordan dequeue vide, hvordan man pop off hvad er i spidsen? >> Right, ja.
>> Hvad det er at se på, er bare hvad hovedet er indstillet til.
Så i denne første sag, hvis vi ser lige her,
vores hoved er 0, index 0. >> Højre.
[Hardison] Så det bare siger okay, godt, elementet ved indeks 0, strengen "hej",
er det element i spidsen for vores kø.
Så vi kommer til at dequeue den fyr.
Og det vil være det element, der bliver returneret til den, der ringer.
Ja, Saad? >> Så hovedet dybest set sætter - hvor du kommer til at indeksere det?
Det er starten på det? >> Yeah. >> Okay.
[Hardison] Det er ved at blive den nye start for vores array.
Så når du dequeue noget, alt hvad du skal gøre, er at få adgang til elementet ved indeks q.head,
og det vil være det element, du vil dequeue.
Du skal også formindske størrelsen.
Vi vil se på en lidt hvor tingene bliver lidt tricky med dette.
Vi dequeue, og nu, hvis vi sætte mellemlager igen,
hvor skal vi sætte mellemlager?
Hvor kommer det næste element gå i vores kø?
Sige at vi vil sætte mellemlager strengen "CS".
Into hvilken indeks vil det gå? [Studerende] Strings [2]. >> Two.
Hvorfor 2 og ikke 0?
[Basil] Fordi nu hovedet er 1, så det er ligesom starten af ​​listen?
[Hardison] Right. Og hvad betegner slutningen af ​​listen?
Hvad vi bruger til at betegne afslutningen på vores kø?
Hovedet er leder af vores kø, i begyndelsen af ​​vores kø.
Hvad er afslutningen på vores kø? [Studerende] størrelse. >> Størrelse, præcis.
Så vores nye elementer går ind på størrelse, og de elementer, som vi tager off komme ud på hovedet.
Når vi sætte mellemlager det næste element, vi sætter det i stedet på størrelse.
[Student] Før du lægger det i selv, størrelse var 1, right?
[Hardison] Right. Så ikke helt på størrelse. Size +, ikke +1, men + hoved.
Fordi vi flyttet alt ved hoved beløb.
Så her, nu har vi fået en kø af størrelse 1, der begynder ved indeks 1.
Halen er indeks 2. Ja?
>> [Student] Hvad sker der, når du dequeue strings [0], og de strings 'slots i hukommelsen
bare få tømt, dybest set, eller bare glemt?
[Hardison] Yeah. I den forstand er vi bare glemme dem.
Hvis vi opbevare kopier af dem for -
mange datastrukturer vil ofte gemme deres egne eksemplarer af de elementer,
således at den person styre datastrukturen ikke behøver at bekymre
om, hvor alle disse pegepinde går.
Datastrukturen holder fast i alt, holder på alle de kopier,
for at sikre, at alt fortsætter korrekt.
Men i dette tilfælde disse datastrukturer kun for nemheds skyld,
ikke lave kopier af noget, som vi opbevarer i dem.
[Student] Så er dette en kontinuerlig række af -? >> Ja.
Hvis vi ser tilbage på, hvad definitionen var af denne struktur, det er.
Det er bare en standard array som du har set,
et array af char * s.
Betyder det -? >> Ja, jeg var bare undrende
hvis du i sidste ende vil løbe tør for hukommelse, til en vis grad,
hvis du har alle disse tomme pletter i dit array?
[Hardison] Ja, det er en god pointe.
>> Hvis vi ser på hvad der er sket nu på dette tidspunkt,
vi har fyldt op vores kø, det ligner.
Men vi har ikke rigtig fyldt op vores kø
fordi vi har en kø, der er str. 2, men det begynder ved indeks 1,
fordi det er der vores hoved pointer er.
Ligesom du sagde, at element i strings [0], ved indeks 0, ikke er der i virkeligheden.
Det er ikke i vores kø længere.
Vi vidste bare ikke gider at gå ind og overskrive det, når vi dequeued det.
Så selvom det ser ud som om vi har kørt tør for hukommelse, vi virkelig ikke.
Denne spot er tilgængelige for os at bruge.
Den passende opførsel, hvis vi skulle forsøge og første dequeue noget
gerne "bye", der ville pop bye off.
Nu er vores kø begynder ved indeks 2 og er af størrelse 1.
Og nu, hvis vi prøver og sætte mellemlager noget igen, siger 50,
50 bør gå i denne plet ved indeks 0
fordi det er stadig til rådighed for os. Ja, Saad?
[Saad] Sker det automatisk?
[Hardison] Det sker ikke helt automatisk. Du er nødt til at gøre det math
at gøre det arbejde, men væsentligt, hvad vi har gjort, er at vi lige har viklet rundt.
[Saad] Og er det okay, hvis dette har et hul i midten af ​​det?
[Hardison] Det er, hvis vi kan gøre det math træne ordentligt.
>> Og det viser sig, at det er faktisk ikke så svært at gøre med mod operatøren.
Så ligesom vi gjorde med Cæsar og krypto stuff,
hjælp mod, kan vi få tingene til at vikle rundt og holde i gang
rundt og rundt og rundt med vores kø,
holde det hoved pointer bevæge sig rundt.
Bemærk, at størrelse er altid respektere antallet af elementer, der faktisk i køen.
Og det er bare hovedet pointer, der holder cykle igennem.
Hvis vi ser på, hvad der skete her, hvis vi går tilbage til begyndelsen,
og du bare se hvad der sker til hovedet
når vi sætte mellemlager noget, der skete ikke noget til hovedet.
Når vi enqueued noget andet, der skete ikke noget til hovedet.
Snart vi dequeued noget, hovedet går op for én.
Vi enqueued noget, sker der ingenting til hovedet.
Når vi dequeue noget, alle af en pludselig hovedet bliver øges.
Når vi sætte mellemlager noget, sker der ingenting til hovedet.
>> Hvad ville der ske på dette tidspunkt, hvis vi skulle dequeue noget igen?
Nogen tanker? Hvad ville der ske med hovedet?
Hvad skal der ske med hovedet
hvis vi skulle dequeue noget andet?
Hovedet lige nu ligger på indeks 2,
hvilket betyder, at lederen af ​​køen er strings [2].
[Student] Hvilket returnerer 0? >> Det burde vende tilbage til 0. Det skal vikles tilbage omkring, nøjagtigt.
Indtil videre hver gang vi kaldte dequeue, har vi været at tilføje en til hovedet,
føje en til hovedet, tilsættes en til hovedet, tilsættes en til hovedet.
Så snart det hoved pointer kommer til det sidste indeks i vores array,
så er vi nødt til at pakke den tilbage omkring til begyndelsen, gå tilbage til 0.
[Charlotte] Hvad bestemmer kapaciteten i køen i en stak?
[Hardison] I dette tilfælde har vi lige brugt en # defineret konstant. >> Okay.
[Hardison] I det faktiske. C. fil, kan du gå ind og rode med det lidt
og gøre det så stor eller så lidt som du ønsker.
[Charlotte] Så når du gør det til en kø, hvordan kan du gøre computeren vide
hvor stor du vil have stakken for at være?
[Hardison] Det er et godt spørgsmål.
Der er et par forskellige måder. Den ene er at bare definere det op foran
og sige dette vil være en kø, der har 4 elementer eller 50 elementer eller 10.000.
Den anden måde er at gøre, hvad de hacker udgave folk gør
og skabe funktioner til at have din kø vokse dynamisk som flere ting bliver tilføjet i.
>> [Charlotte] Så for at gå med den første mulighed, hvad syntaks du bruger
at fortælle programmet hvad er størrelsen af ​​køen?
[Hardison] Ah. Så lad os komme ud af dette.
Jeg er stadig i stack.c her, så jeg vil bare at rulle op til toppen her.
Kan du se denne her? Dette er den # define kapacitet 10.
Og det er næsten nøjagtig samme syntaks, som vi har til kø.
Undtagen i kø, så har vi det ekstra struct felt i her.
[Charlotte] Åh, jeg troede den kapacitet betød evnen til strengen.
[Hardison] Ah. >> At det er den maksimale længde af ordet. >> Fik det.
Yeah. Kapaciteten her - det er en stor punkt.
Og det er noget, der er tricky
fordi det, vi har erklæret her er et array af char * s.
En vifte af pegepinde.
Dette er et array af tegn.
Det er sandsynligvis, hvad du har set, når du har været at erklære dine buffere for fil I / O,
når du har været at skabe strenge manuelt på stakken.
Men det, vi har her, er en vifte af char * s.
Så det er en vifte af pegepinde.
Faktisk, hvis vi zoome ud igen, og vi ser på, hvad der sker her
i præsentationen, kan du se, at den faktiske elementer, karakter data
bliver ikke gemt i arrayet selv.
Hvad er lagret i vores array her er henvisninger til de tegndata.
Okay. Så vi har set, hvordan størrelsen af ​​køen er ligesom med stakken,
størrelsen altid overholder antallet af elementer, der i øjeblikket er i køen.
Efter at gøre 2 enqueues, er størrelsen 2.
Efter at have foretaget en dequeue størrelsen er nu 1.
Når du har foretaget en anden enqueue størrelsen er tilbage op til 2.
Så den størrelse afgjort overholder antallet af elementer i køen,
og derefter hovedet bare holder cykling.
Det går fra 0-1-2, 0-1-2, 0-1-2.
Og hver gang vi kalder dequeue, bliver hovedet pointer inkrementeres til næste indeks.
Og hvis hovedet er ved at gå over, det sløjfer tilbage omkring til 0.
Så med det, kan vi skrive det dequeue funktion.
Og vi vil forlade enqueue funktion for jer at gennemføre i stedet.
>> Når vi dequeue et element ud af vores kø,
hvad var den første ting, Daniel gjorde, da vi startede med at skrive pop funktion for stakke?
Lad mig høre fra nogen, der ikke har talt endnu.
Lad os se, Saad, kan du huske, hvad Daniel gjorde som den første ting, da han skrev pop?
[Saad] Der var, var det - >> Han testet for noget.
[Saad] Hvis størrelsen er større end 0. >> Præcis.
Og hvad var det testning for?
[Saad] Det var test for at se om der er noget inde i array.
[Hardison] Yeah. Præcis. Så du kan ikke pop noget ud af stablen, hvis den er tom.
På samme måde kan du ikke dequeue noget fra en kø, hvis den er tom.
Hvad er det første, vi skal gøre i vores dequeue funktion her, tror du?
[Saad] Hvis størrelsen er større end 0? >> Yeah.
I dette tilfælde har jeg faktisk lige prøvet at se om det er 0.
Hvis det er 0, kan vi vende tilbage null.
Men nøjagtig samme logik.
Og lad os fortsætte med dette.
Hvis størrelsen ikke er 0, hvor er det element, vi ønsker at dequeue?
[Saad] På hovedet? >> Præcis.
Vi kan bare trække sig ud det første element i vores kø
ved at åbne elementet i spidsen.
Intet crazy.
Efter dette, hvad skal vi gøre? Hvad skal der ske?
Hvad var den anden ting, som vi talte om i dequeue?
To ting er nødt til at ske, fordi vores kø er ændret.
[Daniel] Reducer størrelsen. >> Vi er nødt til at reducere størrelsen og øge hovedet? Præcis.
For at øge hovedet, kan vi ikke bare blindt at øge hovedet, husk det.
Vi kan ikke bare gøre queue.head + +.
Vi er nødt til også at omfatte denne mod af kapaciteten.
Og hvorfor har vi at moder af kapaciteten, Stella?
[Stella] Fordi det har at vikle rundt. >> Præcis.
Vi mod den kapacitet, fordi det skal vikles tilbage omkring til 0.
Så nu, på dette tidspunkt, kan vi gøre det, sagde Daniel.
Vi kan formindske størrelsen.
Og så kan vi bare returnere det element, der var på toppen af ​​køen.
Det ser lidt gnarly i første omgang. Du har måske et spørgsmål. Undskyld?
>> [Sam] Hvorfor er først på toppen af ​​køen? Hvor går det hen?
[Hardison] Det kommer fra den fjerde linje fra bunden.
Efter at vi tester for at sikre, at vores køen ikke er tom,
vi trække sig ud char * først, vi trække det element, der sidder i spidsen indeks
af vores array, af vores strings array, >> og opkald, først?
[Hardison] Og vi kalder det først. Yeah.
Blot for at følge op på det, hvorfor du mener, at vi var nødt til at gøre det?
[Sam] Hver første er bare tilbage q.strings [q.head]? >> Yeah.
>> Fordi vi laver denne forandring af q.head med MOD-funktionen,
og der er ingen måde at gøre det inden for returledningen også.
[Hardison] Præcis. Du er staffagefarve på. Sams helt staffagefarve på.
Årsagen til at vi var nødt til at trække sig ud det første element i vores kø og gemme det i en variabel
er fordi denne linje, hvor vi lige havde q.head,
der er den mod operatøren der er ikke noget, vi kan gøre
og har det virkning på hovedet uden - på én linje.
Så vi faktisk nødt til at trække sig ud det første element, og derefter justere hovedet,
justere størrelsen, og derefter returnere elementet, som vi trækkes ud.
Og det er noget, vi vil se komme op senere med
hægtede lister, som vi lege med dem.
Ofte når du frigøre eller bortskaffelse af hægtede lister
du skal huske det næste element, den næste pointer af en linket liste
før bortskaffelse af den nuværende.
Fordi ellers du smider de oplysninger af hvad der er tilbage på listen.
Nu, hvis du går til dit apparat, du åbner op queue.c--x ud af dette.
Så hvis jeg åbner queue.c, lad mig zoome ind her,
vil du se, at du har et lignende udseende fil.
Tilsvarende udseende fil til, hvad vi havde tidligere med stack.c.
Vi har fået vores struct for kø defineret ligesom vi så på dias.
>> Vi har vores enqueue funktion, som er for dig at gøre.
Og vi har den dequeue funktion her.
Den dequeue funktion i filen ikke er blevet gennemført,
men jeg vil sætte den op igen på den PowerPoint, så du kan skrive det i, hvis du vil have.
Så for de næste 5 minutter eller deromkring, arbejde gutter på enqueue
som er næsten lige det modsatte af dequeue.
Du behøver ikke at justere hoved, når du enqueueing, men hvad har du at justere?
Størrelse. Så når du enqueue, hovedet forbliver uberørt, bliver størrelsen ændret.
Men det tager en lille smule af - du bliver nødt til at lege med det mod
at finde ud af præcis, hvad indeks Det nye element skal indsættes på.
Så jeg vil give jer en lille smule, sætte dequeue tilbage op på diasset,
Og som du fyre har spørgsmål, råbe dem ud, så vi kan
taler alle om dem som en gruppe.
Også med den størrelse, du lad være - når du justere størrelsen, kan du altid bare -
har du at mod den størrelse nogensinde? [Daniel] Nej >> Du behøver ikke at mod den størrelse, højre.
Fordi størrelse altid vil, hvis Du er - forudsat du administrerer tingene korrekt,
størrelsen vil altid være mellem 0 og 3.
Hvor har du at mod, når du laver enqueue?
[Student] Kun for hovedet. >> Kun for hovedet, præcis.
Og hvorfor har du at mod overhovedet i enqueue?
Hvornår er en situation, hvor du er nødt til mod?
[Student] Hvis du har ting på plads, gerne på rum 1 og 2,
og derefter du behov for at tilføje noget til 0.
[Hardison] Ja, præcis. Så hvis dit hoved pointer er til allersidst,
eller hvis din størrelse plus dit hoved er større, eller rettere, vil ombryde omkring køen.
>> Så i denne situation, at vi har fået op her på objektglasset lige nu,
hvis jeg ønsker at sætte mellemlager noget lige nu,
vi ønsker at sætte mellemlager noget ved indeks 0.
Så hvis man ser på hvor de 50 går, og jeg kalder enqueue 50,
den går ned der i bunden. Det går i indeks 0.
Den erstatter den "hi", der allerede var dequeued.
[Daniel] Kan du ikke tage dig af det i dequeue allerede?
Hvorfor gør den noget med hovedet i enqueue?
[Hardison] Åh, så du ikke ændrer hovedet, undskyld.
Men du er nødt til at bruge mod operatøren, når du får adgang til
det element, du ønsker at sætte mellemlager når du får adgang til
det næste element i din kø.
[Basil] jeg ikke gøre det, og jeg fik "succes" på der.
[Daniel] Åh, jeg forstår, hvad du siger.
[Hardison] Så du didn't - du bare gjorde q.size?
[Basil] Yeah. Jeg har lige skiftet side, havde jeg ikke gøre noget med hovedet.
[Hardison] Du behøver faktisk ikke at nulstille hovedet at være noget,
men når du indekset i strengene array,
du rent faktisk nødt til at gå videre og beregne, hvor den næste element er,
fordi komitéens stakken, det næste element i din stack var altid
ved indekset svarende til størrelsen.
Hvis vi ser tilbage på vores stack push-funktion,
Vi kunne altid knipse i vores nye element til højre på indeks størrelse.
Betragtninger med køen, kan vi ikke gøre det
fordi hvis vi er i denne situation,
hvis vi enqueued 50 vores nye streng ville gå til højre ved strings [1]
som vi ikke ønsker at gøre.
Vi ønsker at have den nye streng gå på indeks 0.
>> Er der nogen - ja? [Student] Jeg har et spørgsmål, men det er egentlig ikke relateret.
Hvad betyder det, når nogen bare kalder noget PRED pointer?
Hvad er det navn en forkortelse af? Jeg ved, det er bare et navn.
[Hardison] Pred pointer? Lad os se. I hvilken sammenhæng?
[Student] Det var for indsatsen. Jeg kan spørge dig senere, hvis du ønsker
fordi det ikke er virkelig relateret, men jeg bare -
[Hardison] Fra Davids insert kode fra foredrag?
Vi kan trække det op og tale om det.
Vi taler om det næste, når vi kommer til hægtede lister.
>> Så lad os virkelig hurtigt se på, hvad det enqueue funktionen ser ud.
Hvad var den første ting, folk har forsøgt at gøre i din enqueue linje? Ind i denne kø?
Svarende til, hvad du gjorde for stakken skubbe.
Hvad gjorde du, Stella?
[Stella, uforståelig]
[Hardison] Præcis. Hvis (q.size == KAPACITET) -
Jeg har brug for at sætte mine seler på rette sted - returnere falsk.
Zoom ind en lille smule. Okay.
Nu hvad er det næste, at vi skulle gøre?
Ligesom med stakken, og indsat på det rigtige sted.
Og så hvad var det rigtige sted at indsætte det?
Med stakken var det indeks størrelse, med dette er det ikke helt det.
[Daniel] Jeg har q.head--eller - >> q.strings? >> Yeah.
q.strings [q.head + q.size mod KAPACITET]?
[Hardison] Vi sandsynligvis ønsker at sætte parentes omkring dette
så vi får den rette forrang og så det er cleart for alle.
Og sæt, lige? >> Til str? >> Til str. Great.
Og nu, hvad er det sidste, vi skal gøre?
Ligesom vi gjorde i stakken. >> Forøg størrelsen? >> Forøg størrelsen.
Boom. Og så, da starteren kode netop vendt tilbage falsk som standard,
Vi ønsker at ændre dette til sand hvis alt går igennem og alt går godt.
Ok. Det er en masse information om sektion.
Vi er ikke helt over. Vi ønsker at tale virkelig hurtigt om enkeltvis-hægtede lister.
Jeg vil sætte dette op, så vi kan gå tilbage til det senere.
Men lad os gå tilbage til vores præsentation for blot et par flere dias.
Så enqueue er TODO, nu vi har gjort det.
>> Lad os nu tage et kig på enkeltvis-hægtede lister.
Vi talte om disse lidt mere i foredrag.
Hvor mange af jer så demo, hvor vi havde folk
akavet peger på hinanden og bedriften numre? >> Jeg var i det.
>> Hvad gjorde du fyre tror? Gjorde det, forhåbentlig afmystificere disse en lille smule?
Med en liste, viser det sig, at vi beskæftiger os med denne type, som vi kommer til at kalde en node.
Betragtninger med køen og stakken vi havde struct, at vi ville kalde kø i stakken,
Vi havde disse nye kø i stack typer,
her en liste egentlig bare består af en flok noder.
På samme måde som strenge er bare en masse chars alle linet op ved siden af ​​hinanden.
En linket liste er bare en knude og en anden node og en anden node og en anden node.
Og i stedet for at smadre alle de noder sammen og lagre dem tilstødende
alt lige ved siden af ​​hinanden i hukommelsen,
har denne næste pointer giver os mulighed for at gemme noder i alle tilfælde, tilfældigt.
Og derefter slags tråd dem sammen til punkt fra den ene til den næste.
>> Og hvad var den store fordel, at det havde over et array?
Over lagring alt tilstødende bare fast ved siden af ​​hinanden?
Kan du huske? Ja? >> Dynamisk allokering af hukommelse?
>> Dynamisk allokering af hukommelse i hvilken forstand?
[Student] I, at du kan holde gøre det større og du behøver ikke at flytte hele din array?
[Hardison] Præcis. Så med et array, når du ønsker at sætte et nyt element ind i midten af ​​det
du nødt til at flytte alt for at gøre plads.
Og ligesom vi talte om med køen,
det er derfor vi holder det hoved pointer,
så vi ikke konstant skiftende ting.
Fordi det bliver dyrt, hvis du har en stor vifte
og du er konstant gør disse tilfældige indrykninger.
Betragtninger med en liste, er alt du skal gøre smide det på en ny node,
justere pegepinde, og du er færdig.
Hvad stinker om dette?
Bortset fra det faktum, at det ikke er så let at arbejde med som en matrix? Ja?
[Daniel] Nå, jeg tror det er meget sværere at få adgang til et bestemt element i den linkede liste?
[Hardison] Du kan ikke bare hoppe til en vilkårlig element i midten af ​​din linkede liste.
Hvordan du skal gøre det i stedet? >> Du er nødt til at gå gennem hele ting.
[Hardison] Yeah. De skal igennem en ad gangen, en ad gangen.
Det er en enorm - det er en smerte.
Hvad er den anden - der er en anden undergang til dette.
[Basil] Du kan ikke gå frem og tilbage? Du er nødt til at gå én retning?
[Hardison] Yeah. Så hvordan løser vi det nogle gange?
[Basil] Dobbelt-bundet lister? >> Præcis. Der er dobbelt-hægtede lister.
Der er også - undskyld?
>> [Sam] Er det det samme som at bruge PRED ting, -
Jeg kom lige i tanke, er det ikke hvad det PRED ting er?
Er det ikke i mellem dobbelt og enkeltvis?
[Hardison] Lad os se på, hvad han gjorde.
Så her går vi. Her er listen kode.
Her har vi predptr, herinde. Er det hvad du talte om?
Så det var - han befri en liste, og han forsøger at gemme en pegepind til det.
Dette er ikke den dobbelt, enkeltvis forbundet-lister.
Vi kan tale mere om dette senere, da dette taler om frigørelse af listen
og jeg vil gerne vise nogle andre ting først.
men det er bare - det er at huske værdien af ​​PTR
[Student] Åh, det er foregående pointer? >> Yeah.
For at vi kan derefter inkrementere ptr selv, før vi så fri, hvad predptr er.
Fordi vi ikke kan gratis ptr og derefter kalde ptr = PTR næste, right?
Det ville være skidt.
Så lad os se, tilbage til denne fyr.
>> Den anden dårlige ting om lister er, at mens med et array
vi netop har alle de elementer, selv stablede siden af ​​hinanden,
her har vi også indført denne pointer.
Så der er en ekstra bid af hukommelse, som vi skulle bruge
for ethvert element, at vi lagring i vores liste.
Vi får fleksibilitet, men det kommer til en pris.
Den leveres med denne gang omkostninger,
og det kommer med denne hukommelse omkostning også.
Tiden i den forstand, at vi nu er nødt til at gå gennem hvert element i arrayet
at finde en på indeks 10, eller som ville have været indeks 10 i et array.
>> Bare virkelig hurtigt, når vi diagram af disse lister,
vi typisk holde på hovedet af listen eller den første pointer af listen
og bemærk at dette er en sand pointer.
Det er kun 4 bytes. Det er ikke en egentlig knude selv.
Så du se, at det ikke har nogen int værdi i det, ingen næste pointer i det.
Det er bogstaveligt talt bare en pegepind.
Det kommer til at pege på noget, som er et virkeligt knudepunkt struct.
[Sam] En pegepind kaldet node? >> Dette er - nej. Dette er en pointer til noget af typen node.
Det er en pointer til en knude struct. >> Åh, okay.
Diagrammet til venstre, kode til højre.
Vi kan indstille den til null, der er en god måde at starte.
Når du diagram det, du enten skrive det som null eller hvis du lægger en linje gennem det på den måde.
>> En af de nemmeste måder at arbejde med lister
og vi beder jer ikke både prepend og tilføje at se forskellene mellem de to,
men forudstille er absolut nemmere.
Når du tilføjes i begyndelsen, det er her du - når du prepend (7),
du går og skabe node struct
og du først indstilles til at pege på det, fordi nu, da vi foranstillet det,
det vil være i begyndelsen af ​​listen.
Hvis vi prepend (3), der skaber en anden node, men nu 3 kommer før 7.
Så vi er væsentligt at skubbe tingene på vores liste.
Nu kan du se, at prepend, nogle gange folk kalder det skubbe,
fordi du presser et nyt element på din liste.
Det er også nemt at slette på forsiden af ​​en liste.
Så folk vil ofte kalde det pop.
Og på den måde, kan du emulere en stak ved hjælp af en sammenkædet liste.
Ups. Beklager, nu skal vi komme ind append. Så her er vi foranstillet (7), nu vi prepend (3).
Hvis vi foranstillet noget andet på denne liste, hvis vi foranstillet (4),
så ville vi have 4 og derefter 3 og derefter 7.
Så vi kunne pop og fjerne 4, fjern 3, fjerne 7.
Ofte mere intuitiv måde at tænke om dette er med append.
Så jeg har diagrammet ud af, hvad det ville se ud med vedhæfte her.
Her vedlagt (7), ikke ser noget anderledes
fordi der kun er ét element i listen.
Og tilføje (3) stiller den til ende.
Måske du kan se lige nu trick med append
er, at da vi kun ved, hvor starten af ​​listen er,
skal føjes til en liste, du er nødt til at gå hele vejen gennem listen
at komme til ende, stoppe, og derefter bygge dit node og klimpre alt ned.
Tilslut alle de ting op.
Så med prepend, som vi netop har rippet gennem dette virkelig hurtigt,
når du tilføjes i begyndelsen af ​​en liste, er det forholdsvis enkelt.
>> Du laver din nye node, inddrage nogle dynamisk allokering af hukommelse.
Så her vi laver en node struct med malloc.
Så malloc vi bruger, fordi der vil afsætte hukommelse for os for senere
fordi vi ikke ønsker dette - vi ønsker denne hukommelse til at vare ved i lang tid.
Og vi får en pointer til den plads i hukommelsen, som vi netop tildelt.
Vi bruger størrelse knude, vi ikke summere felterne.
Vi ikke manuelt genererer antallet af bytes,
i stedet bruger vi sizeof, så vi ved, at vi får et passende antal bytes.
Vi sørger for at teste, at vores malloc opkald lykkedes.
Dette er noget du ønsker at gøre i almindelighed.
På moderne maskiner, er ved at løbe tør for hukommelse ikke noget, der er let
medmindre du afsætte et væld af ting og gøre en enorm liste,
men hvis du bygger ting for, siger, som en iPhone eller en Android,
du har begrænset hukommelse ressourcer, især hvis du laver noget intens.
Så det er godt at få i praksis.
>> Bemærk, at jeg har brugt et par forskellige funktioner her
at du har set den er lidt nyt.
Så fprintf er ligesom printf
undtagen det første argument er den strøm, som du ønsker at udskrive.
I dette tilfælde vil vi udskrive til den standard fejlstreng
som er forskellig fra den normale outstream.
Som standard er det dukker op på samme sted.
Det udskriver også ud til terminalen, men du kan -
bruge disse kommandoer, du har lært om de omdirigering teknikker
du lærte om i Tommys video til problemer set 4, kan du rette den
til forskellige områder, og afslut, lige her, afslutter dit program.
Det er essentielt som vender hjem fra main,
medmindre vi bruge exit fordi her afkast ikke vil gøre noget.
Vi er ikke i main, er så returnere ikke afslutte programmet som vi selv ønsker.
Så vi bruger exit funktion og give det en fejlkode.
Så her har vi sat den nye node værdi felt, dets Jeg feltet at være lig med i, og så må vi wire det op.
Vi sætter det nye knudepunkt næste pointer til at pege på først,
og derefter først vil nu pege på den nye node.
Disse første linjer kode, er vi faktisk at bygge den nye node.
Ikke de to sidste linjer i denne funktion, men de første.
Man kan faktisk trækkes ud i en funktion, til en hjælpefunktion.
Det er ofte det, jeg gør, er, jeg trækker det ud i en funktion,
Jeg kalder det noget som build node,
og som holder prepend funktionen temmelig lille, det er kun 3 linier dengang.
Jeg vil foretage et opkald til min build node-funktionen, og så kan jeg wire alting op.
>> Den sidste ting jeg vil vise dig,
og jeg vil lade dig gøre append og alt det på egen hånd,
er, hvordan man gentage over en liste.
Der er en masse forskellige måder at gentage over en liste.
I dette tilfælde vil vi finde længden af ​​en liste.
Så vi starter med længde = 0.
Dette er meget ligesom at skrive strlen for en streng.
Dette er hvad jeg ønsker at vise dig, denne for-løkke lige her.
Det ser lidt funky, det er ikke den sædvanlige int i = 0, i <uanset, i + +.
I stedet er det at initialisere vores variabel n for at være begyndelsen af ​​listen.
Og så mens vores iterator variabel ikke er nul, vi holde ud.
Dette skyldes efter sædvane vil i slutningen af ​​vores liste være null.
Og så for at øge, snarere end at gøre + +,
den sammenkædede liste svarende til + + er n = n-> næste.
>> Jeg vil lade dig udfylde hullerne her, fordi vi er ude af tid.
Men holde dette i tankerne, mens du arbejder på din spellr psets.
Hægtede lister, hvis du gennemføre en hash tabel,
vil helt sikkert komme i meget handy.
Og har denne formsprog til sløjfning over ting vil gøre livet meget lettere, forhåbentlig.
Eventuelle spørgsmål, hurtigt?
[Sam] Vil du sende den udfyldte SLL og sc?
[Hardison] Yeah. Jeg sender ud afsluttede dias og afsluttede SLL stack og queue.cs.
[CS50.TV]