[Powered by Google Translate] [Deel 6: minder comfortabel] [Nate Hardison] [Harvard University] [Dit is CS50.] [CS50.TV] Oke. Welkom bij hoofdstuk 6. Deze week gaan we het hebben over datastructuren in doorsnede, vooral omdat deze week probleem zich op spellr doet een hele hoop verschillende datastructuur exploratie. Er zijn een aantal verschillende manieren waarop u kunt gaan met het probleem set, en hoe meer data structuren die je kent over, hoe meer leuke dingen die je kunt doen. 

Dus laten we beginnen. Eerst gaan we het hebben over stapels, de stapel en wachtrij data structuren die we gaan praten. Stapels en wachtrijen zijn erg behulpzaam wanneer we beginnen te praten over grafieken, die niet we gaan nu niet zo veel van het recht. Maar ze zijn echt goed om een ​​van de grote fundamentele datastructuren van CS te begrijpen. De beschrijving in het probleem set specificatie, als je het omhoog te trekken, spreekt over stacks als verwant aan de stapel dineren trays die je in de kantine hebben bij de eetzalen waar toen de eetkamer personeel komt en zet de eetkamer laden uit nadat ze schoongemaakt hen, ze stapelen ene boven de andere. En dan als kinderen komen om voedsel te krijgen, ze trekken de laden af, eerst de bovenste, dan de hieronder, dan het onderstaande dat. Dus, in feite, de eerste lade die de eetzaal personeel neer te zetten is de laatste die wordt gehaald. De laatste die de eetkamer personeel op de eerste is die wordt af genomen voor het diner. In spec van het probleem-toestel u, die kunt downloaden als u dat nog niet gedaan, we praten over het modelleren van een stapel gegevens Structuur van het gebruik van dit soort struct. 

Dus wat we hier hebben, dit is vergelijkbaar met wat werd gepresenteerd in lezing, behalve in lezing presenteerden we dit met ints in tegenstelling tot char * s. Dit gaat een stapel die winkels dan zijn? Daniel? Wat gaan we opslaan in deze stapel? [Daniel] Strings? >> Wij zijn het opslaan van strings in deze stapel, precies. Alles wat je nodig hebt om een ​​stapel te maken is een array van een bepaalde functie, in dit geval, capaciteit zal worden in hoofdletters want het is een constante. En naast de array, we moeten volgen is de huidige omvang van de array. Een ding om op te merken is dat wel cool is dat we de gestapelde datastructuur te creëren op de top van een andere datastructuur, de array. Er zijn verschillende manieren om stapels voeren. We zullen het niet doen helemaal nog niet, maar hopelijk na het doen van de linked-lists problemen, je zult zien hoe je eenvoudig kunt een stapel op de top van een gekoppelde lijst en implementeren. Maar voor nu, zullen we vasthouden aan de arrays. Dus nogmaals, alles wat we nodig hebben is een array en we hoeven alleen maar om de grootte van de array te volgen. [Sam] Sorry, waarom is het dat je zei dat de stapel is op de top van de gitaar? Voor mij lijkt het alsof de snaren in de stapel. [Hardison] Ja. We creëren, we ons aanbod datastructuur te nemen - dat is een goede vraag. Dus de vraag is waarom, voor de mensen die kijken naar deze online, Daarom zeggen we dat de stapel op de top van de snaren, want hier lijkt het alsof de snaren zijn in de stapel? Dat is helemaal het geval is. Wat ik doelde op was dat we een array datastructuur kreeg. We hebben een reeks van char * s, deze array van strings, en we gaan aan toe te voegen om de data gestapelde structuur. 

Dus een stapel iets complexer dan een array. We kunnen een array om een ​​stapel te bouwen. Dus dat is waar we zeggen dat de stapel is gebouwd op de top van een array. Ook, zoals ik al eerder zei, kunnen we een stapel te bouwen op de top van een gekoppelde lijst. In plaats van een array aan onze gegevens beschikken, kunnen we gebruik maken van een gelinkte lijst van onze elementen vast te houden en de stapel te bouwen rond dat. Laten we lopen door een paar voorbeelden, op zoek naar enkele code, om te zien wat er werkelijk hier gebeurt. Aan de linkerkant, heb ik afgebroken wat dat stapel struct eruit zou zien in het geheugen indien de capaciteit werden # gedefinieerd als vier. We hebben onze vier elementen char * array. We hebben strings [0], strijkers [1], strijkers [2], strijkers [3], en dan die laatste plaats voor onze omvang integer. Is dit logisch? Oke. Dit is wat er gebeurt als wat ik doe aan de rechterkant, die zal worden mijn code, is om gewoon te verklaren een struct, een gestapelde struct genaamd s. Dit is wat we krijgen. Zij stelt deze voetafdruk in het geheugen. De eerste vraag hier is wat is de inhoud van deze stapel struct? Op dit moment zijn ze niets, maar ze zijn niet helemaal niets. Ze zijn dit soort afval. We hebben geen idee wat er in hen. Wanneer we stack s verklaren, we zijn gewoon gooien die naar beneden op de top van het geheugen. Het is net zoiets als te verklaren int i en niet initialiseren. Je weet niet wat er in zit. U kunt lezen wat er in zit, maar het is misschien niet super vriendelijk. Een ding dat je wilt altijd onthouden om te doen is te initialiseren wat moet worden geïnitialiseerd. In dit geval gaan we om de grootte te initialiseren aan nul, want dat gaat blijken zeer belangrijk te zijn voor ons. We konden gaan en initialiseren alle pointers, alle char * s, bepaalde waarde begrijpelijk, waarschijnlijk null zijn. Maar het is niet helemaal nodig dat we dat doen. 

Nu, de twee belangrijkste activiteiten op stapels zijn? Iedereen herinnert van lezing wat je doet met stapels? Ja? [Stella] Duwen en popping? >> Precies. Duwen en popping zijn de twee belangrijkste operaties op stapels. En wat doet push doen? >> Het zet iets op de bovenkant van de stapel, en dan knallend haalt u het uit. [Hardison] Precies. Dus duwen duwt iets op de top van de stapel. Het is net als de eetkamer personeel zetten van een dienblad op de toonbank. En knallen is het nemen van een eet-uitvoerlade niet in de stapel. Laten we lopen door een paar voorbeelden van wat er gebeurt wanneer we dingen te duwen in de stapel. Als we de string 'hello' op onze stack duwen, dit is wat ons diagram nu uit zou zien. Zie wat er gebeurt? We geduwd in het eerste element van onze strings serie en we upped onze omvang tellen als 1. Dus als we kijken naar het verschil tussen de twee dia's, hier was 0, hier is voor de druk. Hier is na de push. Voordat de druk, na de push. En nu hebben we een element in onze stack. Het is de string "hallo", en dat is het. Al het andere in de array, in onze strings array, is nog steeds afval. We hebben niet geïnitialiseerd is. Laten we zeggen dat we een andere string te duwen op onze stack. We gaan 'wereld' push op dit moment. Dus je kunt zien "wereld" hier gaat op de top van "hallo", en de grootte telling gaat tot 2. Nu kunnen we pushen "CS50", en dat zal weer gaan op de top. Als we terug gaan, kunt u zien hoe we dingen duwen op de top van de stapel. En nu krijgen we tot pop. Als we iets af van de stapel dook, wat is er gebeurd? Heeft iemand het verschil? Het is vrij subtiel. [Student] De grootte. >> Ja, de grootte veranderd. 

Wat zou je anders hebben verwacht om te veranderen? [Student] De snaren ook. >> Juist. De snaren ook. Het blijkt dat wanneer je doet het op deze manier, omdat we niet het kopiëren van de elementen in onze stack, we eigenlijk niet niets te doen, we kunnen gewoon gebruik maken van de grootte bij te houden van het aantal zaken in ons aanbod zodat wanneer we weer knallen, we weer gewoon te verlagen onze omvang tot 1. Het is niet nodig om daadwerkelijk te gaan in en overschrijven alles. Kind van funky. Het blijkt dat we gewoon typisch dingen met rust te laten, want het is minder werk voor ons te doen. Als we niet hebben om terug te gaan en iets te overschrijven, dan waarom? Dus toen we pop twee keer af van de stapel, al wat doet is verlagen van de grootte van een paar keer. En nogmaals, dit is alleen omdat we niet meer te kopiëren in onze stack. Ja? Ga je gang. [Student, onverstaanbaar] >> En wat gebeurt er dan als je nogmaals op iets? Als je iets nogmaals op, het is waar naar toe? Waar gaat het heen, Basil? >> In strings [1]? >> Juist. Waarom werkt het niet ingaan op strings [3]? [Basil] Omdat het vergat dat er iets in strings [1] en [2]? [Hardison] Precies. Onze stapel, in wezen, "vergeten" dat het vasthouden aan iets in strings [1] of strings [2], dus toen we 'woot "duwen, het stelt alleen dat in het element strings [1]. Zijn er nog vragen over hoe dit werkt, op een basisniveau? [Sam] Dit is dus niet dynamisch op enigerlei wijze, in termen van hoeveelheid of in termen van de grootte van de stack? [Hardison] Precies. Dit is - het punt was dat dit niet een dynamisch growning stapel. Dit is een stapel kan houden ten hoogste vier char * s, maximaal vier dingen. Als we proberen te duwen vijfde ding, wat denk je dat er moet gebeuren? [Studenten, onverstaanbaar] [Hardison] Precies. Er zijn een aantal dingen die kunnen gebeuren. Het zou kunnen seg fout, afhankelijk van wat we waren - hoe precies we de uitvoering van de back-end. Het kan overschrijven. Het kan zijn dat buffer overflow waarover we hebben gesproken in de klas. Wat zou de meest voor de hand liggende ding dat kan worden overschreven worden als we geprobeerd om een ​​extra ding op onze stack duwen? Dus u had het over een buffer overflow. Wat zou het ding dat zou krijgen geschreven over of stampte op zijn als we overspoeld per ongeluk door te proberen om een ​​extra ding te duwen? [Daniel, onverstaanbaar] >> Mogelijke. Maar in eerste instantie, wat zou er gebeuren? Wat als we geprobeerd om een ​​vierde ding te duwen? Het kan overschrijven van de grootte, in ieder geval met dit geheugen diagram dat we hebben. 

In het probleem set specificatie, en dat is wat we gaan worden de uitvoering van vandaag, wat we wel willen doen is gewoon return false. Onze push-methode wordt een boolean waarde terug, en dat booleaanse waarde is waar als de push slaagt en false als we niet kunnen iets meer duwen, omdat de stapel vol is. Laten we lopen door een klein beetje van die code op dit moment. Hier is onze Push-functie. Onze-Push-functie voor een stapel gaat nemen in de string te zetten op de stapel. Het zal true teruggeven als de string met succes werd geduwd op de stapel en anders false. Eventuele suggesties over wat misschien een goede eerste wat je moet doen hier te zijn? [Sam] Als de grootte gelijk is aan de capaciteit dan return false? [Hardison] Bingo. Nice job. Als de grootte van de capaciteit, we gaan om terug te keren vals. We kunnen niet alles meer in onze stack. Anders willen we iets op de bovenkant van de stapel. Wat is "de top van de stapel," in eerste instantie? [Daniel] Grootte 0? >> Grootte 0. Wat is de top van de stack na er een ding in de stapel? Missy, weet je dat? [Missy] One. >> Grootte is een, precies. Je blijven toevoegen aan de grootte, en elke keer dat je de invoering van het nieuwe element in de index grootte in de array. We kunnen het met dat soort van one-liner, als dat zinvol is. Dus we hebben onze snaren array, gaan we toegang krijgen op de grootte-index, en we gaan gewoon naar onze char * op te slaan in. Merk op hoe er is geen touw kopiëren hier aan de hand, geen dynamische toewijzing van geheugen? En dan Missy bracht wat we nu moeten doen, omdat we de opgeslagen snaar op de juiste plaats in de array, en ze zei dat we moesten aan de grootte met een te verhogen, zodat we klaar zijn voor de volgende druk. Dus we kunnen dat doen met s.size + +. Op dit punt hebben we geduwd ons aanbod. Wat is het laatste wat we moeten doen? [Student] Terug waar. >> Terug waar. Dus het is vrij eenvoudig, een vrij simpele code. Niet te veel. Als je eenmaal hebt gewikkeld je hoofd rond hoe de stapel werkt, Dit is vrij eenvoudig te implementeren. 

Nu is het volgende deel van deze popping een reeks af van de stapel. Ik ga geven jullie wat tijd om te werken aan dit een beetje. Het is bijna het tegenovergestelde van wat we hier in push gedaan. Wat ik heb gedaan is eigenlijk - oops. Ik heb opgestart van een apparaat hier, en in het apparaat, Ik heb trok het probleem set 5-specificatie. Als we inzoomen hier, kunnen we zien dat ik bij cdn.cs50.net/2012/fall/psets/pset5.pdf. Hebben jullie gedownload deze code die hier gevestigd, section6.zip? Oke. Als u nog niet gedaan hebt, op dit moment doen, heel snel. Ik doe het in mijn terminal-venster. Ik heb eigenlijk deed het hier. Ja. Ja, Sam? >> Ik heb een vraag over waarom zei je s.string 's beugels van size = str? Wat is str? Is dat ergens gedefinieerd, of - oh, in het char * str? [Hardison] Ja, precies. Dat was het argument. >> Oh, oke. Sorry. [Hardison] We zijn het opgeven van de snaar te duwen inch De andere vraag die zou kunnen komen dat we niet echt over praten was hier We gingen er van uit dat we deze variabele genaamd s had dat was in omvang en toegankelijk voor ons. We gingen er van uit dat s was deze stapel struct. Dus kijken terug op deze push-code, kunt u zien dat we dingen doen met deze string die werd doorgegeven in maar dan opeens zijn we toegang tot s.size, zoals, waar kwam s vandaan? In de code die we gaan om naar te kijken in de sectie archief en dan de dingen die je zult moeten doen in uw probleem stelt, hebben we onze stapel struct een globale variabele zodat wij toegang hebben tot het in al onze verschillende functies zonder handmatig het uitdelen en doorgeven aan de hand, alles doen dat soort dingen aan. We zijn net bedriegt een beetje, als je wil, om dingen te maken mooier. En dat is iets wat we hier doen, want het is voor de lol, het is makkelijker. Vaak zie je mensen doen dit als ze een grote datastructuur dat wordt geopereerd binnen hun programma. 

Laten we terug gaan naar het apparaat. Heeft iedereen succes te krijgen de section6.zip? Iedereen unzip het met unzip section6.zip? Als je in de rubriek 6 directory - aah, all over the place - en u een lijst van wat er in hier, zie je dat je hebt drie verschillende. c bestanden hebt. Je hebt een wachtrij, een SLL, dat is enkelvoudig gelinkte lijst, en een stapel. Als je open te stellen stack.c, kunt u zien dat we dit struct gedefinieerd voor ons heeft, de exacte struct die we net over gesproken in de dia's. We hebben onze globale variabele voor de stack, we hebben onze-Push-functie, en dan hebben we onze pop-functie. Ik zal de code voor terug te duwen op de glijbaan hier, maar wat ik zou willen dat jullie doen is, om het beste van uw vermogen, gaan en implementeren van de pop-functie. Als je eenmaal hebt geïmplementeerd, kunt u slaat deze met make stapel, en vervolgens het resulterende stapel uitvoerbare, en dat loopt allemaal van deze test code hier beneden dat is in de belangrijkste. En de belangrijkste zorgt voor het daadwerkelijk maken van de push en pop gesprekken en ervoor te zorgen dat alles gaat door in orde. Het initialiseert ook de stack size hier zodat u zich geen zorgen te maken over het initialiseren van dat. U kunt ervan uitgaan dat dat het goed is geïnitialiseerd tegen de tijd dat u het in de pop te activeren. Is dat logisch? Dus hier gaan we dan. Er is de push-code. Ik geef jullie 5 of 10 minuten. En als u vragen heeft in de tussentijd terwijl je coderen, vraag ze hardop. Dus als je op een knelpunt, gewoon vragen. Laat het me weten, laat iedereen weten. Ook werken met je buurman. [Daniel] We zijn net uitvoering pop op dit moment? >> Gewoon pop. Hoewel u kunt de uitvoering van push als je wilt zodat het testen zal werken. Omdat het moeilijk is om te testen wat het krijgen in - of, het is moeilijk om popping dingen te testen op een stapel als er niets in de stapel om te beginnen. 

Wat is pop verondersteld om terug te keren? Het element van de bovenkant van de stapel. Het moet het element uitstappen van de bovenkant van de stapel en verlagen de grootte van de stack, en nu je hebt verloren het element op de top. En dan moet je terug het element aan de bovenkant. [Student, onverstaanbaar] [Hardison] Dus wat gebeurt er als je dat doet? [Student, onverstaanbaar] Wat uiteindelijk gebeurt is dat je waarschijnlijk toegang tot een van beide een element dat nog niet is geïnitialiseerd, zodat uw berekening waar het laatste element is uitgeschakeld. Dus hier, als u opmerkt, in push, we toegang tot snaren op de s.size element want het is een nieuwe index. Het is de nieuwe top van de stapel. Overwegende dat de in pop, wordt s.size naar de volgende ruimte, de ruimte die op de top van alle elementen in je stack. Dus de bovenste element niet s.size, maar is het eronder. 

Het andere ding om te doen als je - in pop, wordt u hoeft de grootte te verlagen. Als je nog terug naar onze kleine afbeelding hier, echt, het enige wat we zagen gebeuren als we belden pop was dat deze maat gedaald, eerste 2 en vervolgens naar 1. Toen we een nieuw element op geduwd, zou het gaan op de juiste plek. [Basil] Als de s.size 2 is, dan zou het niet gaan element 2, en dan zou je willen dat element knallen? Dus als we naar - >> Dus laten we eens kijken naar dit. Als dit het stack op dit punt en we noemen pop, waarbij index is de bovenste element? [Basil] Op 2, maar het gaat om 3 pop. >> Juist. Dus dat is waar onze grootte is 3, maar we willen het element pop bij index 2. Het is dat typische soort uit door een die je hebt met de nul-indexering van arrays. Dus u wilt het derde element pop, maar de derde element is niet bij index 3. En de reden dat we niet om dat min 1 doen als we duwen is omdat op dit moment, je merkt dat de bovenste element, als we iets anders op de stapel te duwen op dit punt, we zouden willen duwen op index 3. En het is gewoon zo gebeurt het dat de grootte en de indices line-up als je te duwen. 

Wie heeft er een werkende stack implementatie? Je hebt een werkende stack is. Heb je pop hebt werkt nog? [Daniel] Ja. Ik denk het wel. >> Programma draait en niet seg breuken, het afdrukken van? Is het uit te printen "succes" als u het uitvoert? Ja. Maak stapelen, voer het uit, als het print "succes" en gaat niet verder boom, dan is alles goed. Oke. Laten we over te gaan naar het apparaat heel snel, en we lopen door dit. Als we kijken naar wat er hier aan de hand met pop, Daniel, wat was het eerste wat je deed? [Daniel] Als s.size groter is dan 0. [Hardison] Oke. En waarom heb je dat gedaan? [Daniel] Om ervoor te zorgen dat er iets in de stapel. [Hardison] Juist. U wilt testen om ervoor te zorgen dat s.size groter is dan 0; anders, wat wil je dat er gebeurt? [Daniel] Return null? >> Terug null, precies. Als s.size groter is dan 0. Dan wat gaan we doen? Wat doen we als de stack niet leeg is? [Stella] U verlagen de maat? >> U verlagen van de grootte, oke. Hoe heb je dat gedaan? >> S.size--. [Hardison] Grote. En wat heb je gedaan? [Stella] En toen zei ik terug s.string [s.size]. [Hardison] Grote. Anders zou je terug null. Ja, Sam? [Sam] Waarom is het niet nodig om s.size + 1? [Hardison] Plus 1? >> Ja. >> Ik heb het. [Sam] Ik dacht dat omdat je neemt 1 uit, dan zul je om terug te keren niet degene die ze vroegen. [Hardison] En dit was precies wat we aan het praten waren over deze hele kwestie van 0 indices. Dus als we weer uit te zoomen hier. Als we kijken naar deze man hier, kunt u zien dat wanneer we pop, we knallen het element bij index 2. 

Dus eerst verlagen onze omvang, dan is onze omvang onze index overeenkomt. Als we niet eerst verlagen van de grootte, dan moeten we op maat maken -1 en vervolgens verlagen. Geweldig. Alle goede? Eventuele vragen over dit? Er zijn verschillende manieren om dit ook te schrijven. In feite kunnen we zelfs iets doen - kunnen we een one-liner te doen. Dat kunnen we doen een regel terug. Dus we kunnen eigenlijk verlagen voordat we terug door dat te doen. Dus zetten de - voor de s.size. Dat maakt de lijn echt dicht. Wanneer het verschil tussen de -. Omvang en de s.size-- is dat dit postfix - ze noemen het postfix omdat de - komt na de s.size-- betekent dat s.size wordt geëvalueerd met het oog op het vinden van de index zoals thans als deze regel wordt uitgevoerd, en dan is dit - gebeurt er na de regel wordt uitgevoerd. Na het element bij index s.size wordt geopend. En dat is niet wat we willen, omdat we willen dat de decrement eerst gebeuren. Othewise, we gaan gebruikmaakt van de array, effectief, out of bounds. We gaan gebruikmaakt van het element boven de een die we eigenlijk willen bereiken. Ja, Sam? >> Is het sneller of gebruik minder RAM te maken in een lijn of niet? [Hardison] Eerlijk gezegd, het hangt een beetje af. [Sam, onverstaanbaar] >> Ja, dat hangt ervan af. U kunt dit doen compiler trucs aan de compiler naar die herkennen, meestal, denk ik. 

Dus hebben we gezegd een beetje over deze compiler optimalisatie stuff die je kunt doen in het samenstellen, en dat is het soort ding dat een compiler zou kunnen achterhalen, zoals oh, hey, misschien kan ik doen dit alles in een handeling, in tegenstelling tot het laden van de grootte van variabele in RAM, aflopende het, op te slaan terug, en dan laden er weer in de rest van het bewerkingsproces. Maar meestal, nee, dit is niet het soort dingen dat gaat je programma te maken aanzienlijk sneller. Nog meer vragen over stapels? 

Dus duwen en popping. Als jullie willen proberen de hacker editie, wat we hebben gedaan in de hacker editie is eigenlijk verdwenen en maakte deze stack dynamisch groeien. De uitdaging is er in de eerste plaats hier in de push-functie, om erachter te komen hoe je die array groeien als je blijft duwen meer elementen aan de stack. Het is eigenlijk niet te veel extra code. Gewoon een oproep aan - je moet niet vergeten om de oproepen naar malloc daar goed, en dan erachter te komen wanneer je gaat realloc bellen. Dat is een leuke uitdaging als je geïnteresseerd bent. 

Maar voor het moment, laten we verder gaan, en laten we praten over wachtrijen. Hier Blader door. De wachtrij is een nauwe broertje van de stapel. Dus in de stapel, werden dingen die gezet in de laatste waren de eerste dingen om vervolgens te worden opgehaald. We hebben deze last in, first out of LIFO, bestellen. Terwijl in de wachtrij, zoals je zou verwachten van als je in de rij staan, de eerste persoon die in de rij, de eerste ding om te krijgen in de wachtrij, is het eerste ding dat wordt opgehaald uit de wachtrij. Wachtrijen worden ook vaak gebruikt wanneer we te maken hebben met grafieken, zoals we gesproken over kort met stapels, en wachtrijen zijn ook handig voor een heleboel andere dingen. Een ding dat komt vaak tracht te handhaven, bijvoorbeeld een gesorteerde lijst van elementen. En u kunt dit doen met een array. U kunt handhaven van een gesorteerde lijst van dingen in een array, maar waar dat lastig wordt dan is dat je altijd te vinden de geschikte plaats om het volgende ding in te voegen. Dus als je een array van getallen, 1 tot en met 10, en dan wilt u dat uit te breiden naar alle getallen 1 tot en met 100, en je krijgt deze nummers in willekeurige volgorde af en proberen om alles te houden gesorteerd als je door, je uiteindelijk met een veel geschakeld te doen. Bij bepaalde vormen van wachtrijen en bepaalde vormen van de onderliggende datastructuren, je kunt eigenlijk houd het vrij eenvoudig. Je hoeft niet om iets toe te voegen en vervolgens de hele zaak herschikking per keer. Ook heb je te veel verschuiven van de interne elementen rond te doen. Wanneer we kijken naar een wachtrij, zie je dat - ook in queue.c in de sectie code - de struct dat we je gegeven is echt vergelijkbaar met de struct dat wij u gaf voor een stapel. 

Er is een uitzondering op deze, en dat op een uitzondering na is dat we deze extra integer genoemd het hoofd hebben, en het hoofd hier voor het bijhouden van de kop van de wachtrij of het eerste element in de wachtrij. Met een stack, waren we in staat om bij te houden van het element dat we over te halen, of de top van de stapel, met slechts de grootte, terwijl bij een wachtrij, we hebben te maken met tegengestelde uiteinden. We proberen overstag dingen op aan het einde, maar dan dingen terug van het front. Zo effectief, met het hoofd, hebben we de index van het begin van de wachtrij, en de grootte geeft de index van het einde van de wachtrij zodat wij halen dingen uit het hoofd en voeg dingen op aan de staart. Dat de stack, waren we alleen maar te maken met de bovenkant van de stapel. We hadden nog nooit naar de bodem van de stapel te openen. We hebben alleen toegevoegde dingen naar de top en nam dingen uit van de top- dus we hebben geen behoefte aan die extra veld in onze struct. Is dat over het algemeen zinvol? Oke. Ja, Charlotte? [Charlotte, onverstaanbaar] [Hardison] Dat is een grote vraag, en dat was een, die tijdens college. Misschien lopen door een paar voorbeelden illustreren waarom we willen niet te gebruiken strings [0] als het hoofd van de wachtrij. 

Dus stel dat we onze wachtrij hebben, gaan we noemen wachtrij. In het begin, toen we net geïnstantieerd het, toen we net verklaarde, hebben we niet geïnitialiseerd niets. Het is allemaal rotzooi. Dus natuurlijk willen we ervoor zorgen dat we initialiseren zowel de grootte en de kop velden 0, iets redelijk. We kunnen ook verder gaan en null uit de elementen in onze wachtrij. En om dit diagram te laten passen, merken dat nu onze wachtrij alleen kan drie elementen te houden; terwijl onze stack kon houden vier jaar kunnen onze wachtrij alleen houden drie. En dat is alleen maar om het diagram pasvorm. Het eerste wat hier gebeurt is dat we Enqueue de string "hi". En net zoals wij deden met de stack, niets vreselijk hier anders, gooien we de string op in strings [0] en onze omvang verhoogd met 1. We Enqueue "bye", wordt het op. Dus dit lijkt op een stapel voor het grootste deel. We begonnen hier uit, nieuw element, nieuw element, de grootte blijft stijgen. Wat gebeurt er op dit punt als we iets willen dequeue? Wanneer we willen dequeue, het element dat we willen dequeue? [Basil] Strings [0]. >> Zero. Precies goed, Basil. We willen om zich te ontdoen van de eerste reeks, deze, "hi". Dus wat was het andere ding dat veranderd? Let op als we iets af van de stapel dook, we veranderde de grootte, maar hier, we hebben een paar dingen die veranderen. Niet alleen de grootte veranderen, maar het hoofd verandert. Dit gaat terug tot punt Charlotte's eerder: Daarom hebben we dit hoofd ook? Is het nu zinvol, Charlotte? >> Zoiets. [Hardison] Soort? Dus wat er gebeurde toen we dequeued? Wat heeft het hoofd doen dat nu interessant is? [Charlotte] Oh, omdat het veranderd - oke. Ik begrijp het. Omdat het hoofd - waar het hoofd wijst naar veranderingen in termen van de locatie. Het is niet langer altijd de nul-index is. >> Ja, precies. Wat is er gebeurd was als dequeueing de hoge element werd gedaan en we hadden geen dit hoofd veld omdat we altijd bellen deze string op 0-index het hoofd van onze wachtrij, dan zouden we de rest van de wachtrij terug te schakelen. We zouden moeten "bye" verschuiven van van strings [1] om de strings [0]. En strijkers [2] tot strings [1]. En we hebben om dit te doen voor de gehele lijst van elementen, de gehele reeks elementen. En wanneer we dit doen met een array, dat wordt echt kostbaar. Dus hier, het is niet een groot probleem. We hebben drie elementen in ons aanbod. Maar als we een rij van duizend elementen of een miljoen elementen, en dan ineens, we beginnen met het maken van een heleboel dequeue roept alle in een lus, dingen echt te vertragen als het verschuift alles naar beneden voortdurend. Je weet wel, verschuiven met 1, verschuiving met 1, verschuiving met 1, verschuiving met 1. In plaats daarvan gebruiken we dit hoofd, noemen we het een "pointer" ook al is het niet echt een pointer in de strikte zin, het is niet een pointer type. Het is niet een int * of een char * of iets dergelijks. Maar het is gericht of met vermelding van de hoofd van onze wachtrij. Ja? 

[Student] Hoe dequeue weet gewoon knallen wat er aan het hoofd? [Hardison] Hoe dequeue weet hoe knallen wat er ook aan het hoofd? >> Juist, ja. >> Wat het is te kijken naar is net wat het hoofd is ingesteld op. Dus in dit eerste geval, als we kijken hier, ons hoofd is 0, index 0. >> Juist. [Hardison] Dus het gewoon zegt oke, nou ja, het element op index 0, de string "hi", het element aan het hoofd van onze wachtrij. Dus we gaan met die jongen dequeue. En dat het element dat wordt teruggegeven aan de beller. Ja, Saad? >> Dus de kop zet in feite de - waar je naartoe gaat om te indexeren? Dat is het begin van het? >> Ja. >> Oke. [Hardison] Dat is steeds de nieuwe start voor ons aanbod. Dus als je iets dequeue, alles wat je hoeft te doen is toegang tot het element bij index q.head, en dat zal het element dat u wilt dequeue zijn. Je hebt ook de grootte te verlagen. We zien een beetje waar de dingen een beetje lastig met deze. Wij dequeue, en nu, als we Enqueue weer, waar moeten we Enqueue? Waar komt het volgende element te gaan in onze wachtrij? Stel dat we willen de string "CS" Enqueue. In welke index zal het gaan? [Studenten] Strings [2]. >> Twee. Waarom 2 en niet 0? [Basil] Want nu het hoofd is 1, dus dat is net als het begin van de lijst? [Hardison] Juist. En wat geeft het einde van de lijst? Wat moesten we met behulp van aan het einde van onze rij aan te duiden? Het hoofd is het hoofd van onze wachtrij, het begin van onze wachtrij. Wat is het einde van onze wachtrij? [Studenten] Size. >> Maat, precies. Dus onze nieuwe elementen gaan in op grootte, en de elementen die we uit uit komen op het hoofd. Toen we de volgende element Enqueue, we zetten het in op grootte. [Student] Voordat je dat in al, de grootte was 1, toch? [Hardison] Juist. Dus niet helemaal op maat. Maat +, niet +1, maar + hoofd. Omdat we verschoven alles door het hoofd bedrag. Dus hier, nu hebben we een wachtrij van grootte 1 dat begint bij index 1. De staart is index 2. Ja? 

[Student] Wat gebeurt er als je dequeue strings [0], en de snaren 'slots in het geheugen krijgt gewoon geleegd, in principe, of gewoon vergeten? [Hardison] Ja. In die zin zijn we gewoon vergeten wordt. Als we het opslaan van kopieën van hen voor - veel data structuren zullen vaak slaan hun eigen kopieën van de elementen zodat de beheerder van de datastructuur geen zorgen te maken over waar al die pointers gaan. De gegevensstructuur vasthoudt aan alles, houdt vast aan alle kopieën, om ervoor te zorgen dat alles op de juiste wijze blijft bestaan. In dit geval zijn deze datastructuren alleen voor de eenvoud niet het maken van kopieën van alles wat we opslaan in hen. [Student] Dus is dit een continue reeks van -? >> Ja. Als we terugkijken naar wat de definitie was van deze structuur, is het. Het is gewoon een standaard serie, zoals je hebt gezien, een array van char * s. Is dat -? >> Ja, ik vroeg me af Als je uiteindelijk opraken van het geheugen, tot op zekere hoogte, als je al die lege plekken in uw array? [Hardison] Ja, dat is een goed punt. 

Als we kijken naar wat er gebeurd is nu op dit punt, hebben we gevuld onze wachtrij, het eruit ziet. Maar we hebben niet echt gevuld onze wachtrij want we hebben een wachtrij die is maat 2, maar het begint bij index 1, want dat is waar ons hoofd pointer is. Net als u zeiden, dat element op strings [0], met index 0, is niet echt aanwezig. Het is niet in ons rij niet meer. We wilden gewoon niet de moeite om te gaan en het overschrijven wanneer we dequeued het. Dus ook al lijkt het erop dat we onvoldoende geheugen, we hebben echt niet. Die plek is voor ons gebruiken. De juiste gedrag, als we zouden proberen en eerste dequeue iets als "bye", dat zou pop bye uit. Nu onze wachtrij begint bij index 2 en is van grootte 1. En nu, als we proberen weer Enqueue iets, laten we zeggen 50, 50 moet gaan op deze plek op index 0 want het is nog steeds beschikbaar voor ons. Ja, Saad? [Saad] Is dat automatisch gebeuren? [Hardison] Dat gebeurt niet automatisch. Je moet de wiskunde te doen om het te laten werken, maar in wezen wat we gedaan hebben is dat we gewoon rond. [Saad] En is het goed als dit heeft een gat in het midden van het? [Hardison] Het is of we kunnen de wiskunde goed uit te werken. 

En het blijkt dat die eigenlijk niet zo moeilijk om te doen met de mod operator. Dus net zoals wij deden met Caesar en de crypto dingen, met behulp van mod, kunnen we dingen te wikkelen en door te gaan rond en rond en rond met onze wachtrij, het houden van dat hoofd wijzer bewegen. Merk op dat de grootte altijd respect voor het aantal elementen daadwerkelijk in de wachtrij. En het is gewoon het hoofd pointer die houdt fietsen door. Als we kijken naar wat hier gebeurd is, als we teruggaan naar het begin, en je gewoon kijken wat er gebeurt met het hoofd als we iets Enqueue, gebeurde er niets op het hoofd. Als we iets anders enqueued, gebeurde er niets op het hoofd. Zodra we dequeued iets, het hoofd omhoog gaat met een. We enqueued iets, gebeurt er niets op het hoofd. Als we iets dequeue, alle van een plotselinge het hoofd wordt verhoogd. Als we iets Enqueue, gebeurt er niets op het hoofd. 

Wat zou er gebeuren op dit punt als we weer dequeue iets? Elke gedachten? Wat zou er met het hoofd? Wat moet er gebeuren om het hoofd als we iets anders dequeue? Het hoofd op dit moment is bij index 2, waardoor de kop van de wachtrij strings [2]. [Student] Welke 0 terug? >> Het moet terug naar 0. Het moet weer omheen, precies. Tot nu toe, elke keer als we belden dequeue, we zijn het toevoegen van een aan het hoofd, voeg een aan het hoofd, een aan het hoofd, voeg een aan het hoofd. Zodra dat hoofd pointer wordt de laatste index in onze array, dan moeten we het aantal teruggebracht rond naar het begin, terug naar 0. [Charlotte] Wat bepaalt de capaciteit van de wachtrij in een stapel? [Hardison] In dit geval hebben we net met behulp van een # gedefinieerde constante. >> Oke. [Hardison] In de huidige. C bestand, kunt u in-en modder te gaan met het een beetje en maak het zo groot of zo weinig als je wilt. [Charlotte] Dus als je het maken van het een wachtrij, u hoe te maken van de computer weten hoe groot u wilt dat de stapel te zijn? [Hardison] Dat is een goede vraag. Er zijn een paar manieren. Een daarvan is om gewoon definiëren van te voren en zeggen dat dit gaat om een ​​wachtrij die 4 elementen of 50 elementen of 10.000 moet zijn. De andere manier is om te doen wat de hacker editie mensen aan het doen zijn en creëren functies om uw wachtrij groeien dynamisch als meer dingen krijgen toegevoegd inch 

[Charlotte] Dus om te gaan met de eerste optie, wat syntaxis om te vertellen het programma wat is de grootte van de wachtrij? [Hardison] Ah. Dus laten we uit deze. Ik ben nog steeds in stack.c hier, dus ik ga gewoon hier gaat u naar de top. Kun je zien dit hier? Dit is de # define capaciteit 10. En dit is bijna exact dezelfde syntax die we hebben voor wachtrij. Behalve in wachtrij, we hebben die extra struct veld in hier. [Charlotte] Oh, ik dacht dat de capaciteit betekende dat de capaciteit voor de string. [Hardison] Ah. >> Dat is het de maximale lengte van het woord. >> Ik heb het. Ja. De capaciteit hier - dat is een groot punt. En dit is iets dat is lastig want wat we hier hebben verklaard is een array van char * s. Een array van pointers. Dit is een array van chars. Dit is waarschijnlijk wat je hebt gezien als je al verklaren uw buffers voor file I / O, als je het creëren van strings handmatig op de stapel. Maar wat we hier hebben is een array van char * s. Dus het is een array van pointers. Eigenlijk, als we weer uit te zoomen en we kijken naar wat er hier aan de hand in de presentatie, zie je dat de werkelijke elementen, het karakter van gegevens niet opgeslagen in de array zelf. Wat is opgeslagen in ons aanbod hier zijn verwijzingen naar het karakter van gegevens. Oke. Dus we hebben gezien hoe de grootte van de wachtrij is net als met de stapel, de grootte respecteert altijd het aantal elementen waaraan in de wachtrij. Na het maken van 2 enqueues, de grootte is 2. Na het maken van een dequeue de grootte is nu 1. Na het maken van een andere enqueue de maat weer tot 2. Dus de grootte respecteert zeker het aantal elementen in de wachtrij, en dan het hoofd blijft maar fietsen. Het gaat van 0-1-2, 0-1-2, 0-1-2. En elke keer als we noemen dequeue, wordt het hoofd aanwijzer verhoogd naar de volgende index. En als het hoofd is over te gaan over, het lus terug rond naar 0. Dus met dat, kunnen we schrijven de dequeue functie. En we gaan de enqueue functie te verlaten voor jullie om in plaats daarvan te implementeren. 

Als we een element dequeue uit onze wachtrij, wat was het eerste wat Daniël deed toen we begonnen met het schrijven van de pop-functie voor stapels? Laat me horen van iemand die nog niet heeft gesproken. Laten we eens kijken, Saad, weet je nog wat Daniël deed als het eerste wat toen hij pop schreef? [Saad] Er werd, was het - >> Hij testte voor iets. [Saad] Als de grootte groter is dan 0. >> Precies. En wat was dat het testen voor? [Saad] Dat was het testen om te zien of er iets in de array. [Hardison] Ja. Precies. Dus je kunt niet pop iets uit de stapel als het leeg is. Ook kunt u niet dequeue niets uit een wachtrij als het leeg is. Wat is het eerste wat we moeten doen hier in onze dequeue functie, denk je? [Saad] Als grootte is groter dan 0? >> Ja. In dit geval heb ik eigenlijk alleen maar getest om te zien of het is 0. Indien het 0 is, kunnen we terugkeren null. Maar exact dezelfde logica. En laten we verder gaan met deze. Als het formaat niet 0 is, waar is het element dat we willen dequeue? [Saad] Aan het hoofd? >> Precies. We kunnen gewoon de stekker uit het eerste element in onze wachtrij door naar het element aan het hoofd. Niets gek. Daarna, wat moeten we doen? Wat moet er gebeuren? Wat was het andere ding dat we over gesproken in dequeue? Twee dingen moeten gebeuren, omdat onze wachtrij is veranderd. [Daniel] Verminder de grootte. >> We moeten de omvang te verminderen, en het hoofd te verhogen? Precies. Om het hoofd te verhogen, kunnen we niet zomaar blindelings verhoging van de kop, weet je nog. We kunnen niet zomaar doen queue.head + +. We moeten ook deze mod door de capaciteit. En waarom hebben we mod door de capaciteit, Stella? [Stella] Omdat het te wikkelen rond. >> Precies. We mod door de capaciteit omdat het terug wikkelen op 0. Dus nu, op dit moment, kunnen we doen wat Daniël gezegd. We kunnen verlagen van de grootte. En dan kunnen we net terug van het element, dat was op de top van de wachtrij. Het ziet er soort van knoestige op het eerste. Misschien heb je een vraag. Sorry? 

[Sam] Waarom is eerst aan de top van de wachtrij? Waar komt die verder gaan? [Hardison] Het komt uit de vierde regel van de bodem. Nadat we testen om ervoor te zorgen dat onze wachtrij niet leeg is, trekken we onze eerste char *, we trekken uit het element dat zit aan het hoofd index van ons aanbod, onze strings array, >> en bel die eerste? [Hardison] En we noemen het eerst. Ja. Gewoon om op te volgen dat, waarom denk je dat we moesten dat doen? [Sam] Elke eerste is net terug q.strings [q.head]? >> Ja. >> Omdat we dit doen veranderende van de q.head met de MOD-functie, en er is geen manier om dat ook te doen binnen retourleiding. [Hardison] Precies. Je bent precies goed. Sam is helemaal perfect. De reden dat we moesten trekken uit het eerste element in onze rij en op te slaan in een variabele is omdat deze lijn, waar we hadden net q.head, er is de mod operator daar is niet iets dat we kunnen doen en het hebben invloed op het hoofd nemen zonder - in een lijn. Dus we hebben eigenlijk te trekken uit het eerste element, pas dan het hoofd, U kunt de grootte, en dan terug het element dat we uitgetrokken. En dit is iets dat we zullen zien komen later met gelinkte lijsten, zoals we spelen rond met hen. Vaak als je het vrijmaken of afstoten van gelinkte lijsten moet u het volgende element, de volgende pointer van een gekoppelde lijst herinneren voordat het wordt verwijderd van de huidige. Want anders gooi je weg de informatie van wat er over is in de lijst. Nu, als je naar het apparaat, je open te stellen queue.c--x uit deze. Dus als ik open queue.c, ik zoom laat hier, je zult zien dat je een vergelijkbaar uitziende bestand. Vergelijkbare uitziende bestand naar wat we hadden eerder met stack.c. We hebben onze struct voor wachtrij net gedefinieerd als we zagen op de dia's. 

Wij hebben onze enqueue functie die is voor jou te doen. En we hebben de dequeue functie hier. De dequeue functie in het bestand wordt niet uitgevoerd, maar ik kom terug zet het op de PowerPoint, zodat u het kunt typen, als je wilt. Dus voor de komende 5 minuten of zo, jullie werken aan enqueue dat is bijna het tegenovergestelde van dequeue. Je hoeft niet naar het hoofd aan te passen als je enqueueing, maar wat heb je aan te passen? Size. Dus als je enqueue, het hoofd ongerepte blijft, wordt de grootte veranderd. Maar het vergt wel een beetje - je zal moeten spelen met die mod om precies te achterhalen wat de index van de nieuwe element moet worden ingevoegd op. Dus ik geef jullie een klein beetje, zet een back-up dequeue op de dia, en als jullie vragen hebben, schreeuwen ze uit, zodat we kunnen al het gepraat over hen als een groep. Ook met de grootte die je Doe niet - als u de grootte, kunt u altijd gewoon - moet je de grootte ooit mod? [Daniel] Nee. >> Je hoeft niet om de grootte mod, rechts. Omdat de grootte zal altijd, als je bent - ervan uitgaande dat je het beheer van dingen op de juiste wijze, de grootte altijd tussen 0 en 3. Waar moet je mod als je aan het doen bent enqueue? [Student] Alleen voor het hoofd. >> Alleen voor het hoofd, precies. En waarom moet je op alle mod in enqueue? Wanneer is een situatie waarin je zou moeten mod? [Student] Als je dingen op ruimtes, zoals bij ruimtes 1 en 2, en dan moet je die nodig zijn om iets toe te voegen op 0. [Hardison] Ja, precies. Dus als je hoofd wijzer zich helemaal aan het eind, of als uw maat plus je hoofd is groter, of beter gezegd, gaat wikkelen rond de wachtrij. 

Dus in deze situatie dat we hebben hier op de slide op dit moment, Als ik iets wil Enqueue op dit moment, we willen iets Enqueue op index 0. Dus als je kijkt naar waar de 50 gaat, en ik roep enqueue 50, het gaat daar aan de onderkant. Het gaat in de index 0. Het vervangt de 'hi' dat al dequeued. [Daniel] Maak je geen zorgen dat al nemen dequeue? Waarom duurt het iets met de kop in enqueue? [Hardison] Oh, dus je bent niet het wijzigen van de kop, sorry. Maar je moet de mod operator te gebruiken wanneer u toegang het element dat u wilt Enqueue als je toegang tot het volgende element in uw wachtrij. [Basil] Ik heb dat niet gedaan, en ik kreeg "succes" op daar. [Daniel] Oh, ik begrijp wat je bedoelt. [Hardison] Dus u didn't - je gewoon deed op q.size? [Basil] Ja. Ik zijden veranderd, ik heb niets met het hoofd. [Hardison] Je hoeft niet echt het hoofd terug te zetten naar van alles zijn, maar als je index in de snaren array, je eigenlijk moeten gaan en waar de volgende element te berekenen, omdat withe de stapel, het volgende element in je stack was altijd de index die overeenkomt met de grootte. Als we terugkijken op onze stapel-Push-functie, konden we altijd plunk in onze nieuwe element rechts bij index grootte. Overwegende dat het met de wachtrij, kunnen we niet doen want als we op deze situatie, als we enqueued 50 onze nieuwe string goed zou gaan op strings [1] die we niet willen doen. We willen de nieuwe string te gaan op index 0. 

Heeft iemand - ja? [Student] Ik heb een vraag, maar het is niet echt iets te maken. Wat betekent het als iemand net noemt zoiets als Pred pointer? Wat is die naam een ​​afkorting van? Ik weet dat het is maar een naam. [Hardison] Pred pointer? Laten we eens kijken. In welke context? [Student] Het was voor de insert. Ik kan later vragen of u wilt want het is niet echt gerelateerd, maar ik - [Hardison] Van insert Davids code van college? We kunnen trekken dat omhoog en over praten. We praten over dat de volgende, als we eenmaal aan gelinkte lijsten. 

Dus laten we heel snel kijken naar wat de enqueue functie eruit ziet. Wat was het eerste dat mensen probeerden om te doen in uw enqueue lijn? In deze wachtrij? Vergelijkbaar met wat je hebt gedaan voor stack duwen. Wat heb je gedaan, Stella? [Stella, onverstaanbaar] [Hardison] Precies. Als (q.size == CAPACITEIT) - Ik moet mijn beugel op de juiste plaats - return false. Zoom in een beetje. Oke. Nu, wat is het volgende ding dat we moesten doen? Net als bij de stack, en ingevoegd op de juiste plaats. En dus wat was de juiste plaats om die te voegen? Met de stapel was index grootte, met deze is het niet helemaal zo. [Daniel] Ik heb q.head--of - >> q.strings? >> Ja. q.strings [q.head + q.size mod CAPACITEIT]? [Hardison] We waarschijnlijk willen haakjes rond deze zodat we krijgen de juiste prioriteit en dus dat is cleart voor iedereen. En stel dat gelijk? >> Naar str? >> Naar str. Geweldig. En nu, wat is het laatste wat we moeten doen? Net zoals wij deden in de stapel. >> Verhoog de maat? >> Verhoog de grootte. Boom. En dan, omdat de starter code net terug valse standaard, willen we deze te wijzigen in het geval als alles goed gaat door en alles goed gaat. Oke. Dat is een hoop informatie voor sectie. We zijn nog niet helemaal voorbij. We willen heel snel praten over enkelvoudig gelinkte lijsten. Ik zet dit op zodat we kunnen later terug gaan om het te. Maar laten we terug gaan naar onze presentatie voor slechts een paar dia's. Dus enqueue TODO is, nu hebben we het gedaan. 

Laten we nu eens een kijkje nemen op enkelvoudig gelinkte lijsten. We spraken over deze een beetje meer in college. Hoeveel van jullie zag de demo waar we mensen onhandig wijst naar elkaar en houden nummers? >> Ik was in die. >> Wat hebben jullie? Dat deed, hopelijk demystificeren deze een beetje? Met een lijst, blijkt dat we met dit soort dat we gaan naar een knooppunt te bellen. Overwegende dat, met de wachtrij en de stapel hadden we structs dat we zouden wachtrij noemen in stack, hadden we deze nieuwe rij in stack types, hier een lijst is eigenlijk alleen maar bestaat uit een stel van knopen. Op dezelfde manier dat strings zijn gewoon een stelletje chars alle rij naast elkaar. Een verbonden lijst slechts een knooppunt en ander knooppunt en ander knooppunt en ander knooppunt. En niet breken alle knooppunten samen en slaan aaneengesloten alle naast elkaar in het geheugen, met deze volgende pointer laat ons toe om de knooppunten waar op te slaan, in willekeurige volgorde. En dan soort van draad ze allemaal samen te wijzen van de ene naar de volgende. 

En wat was het grote voordeel dat deze had meer dan een array? Meer dan het opslaan van alles aansluitend gewoon naast elkaar zitten? Weet je nog? Ja? >> Dynamisch toewijzen van geheugen? >> Dynamisch toewijzen van geheugen in welke zin? [Student] In dat je kunt houden waardoor het groter en je hoeft niet om je hele array verplaatsen? [Hardison] Precies. Dus met een array, wanneer u een nieuw element zet in het midden van het, je moet alles verschuiven om ruimte te maken. En zoals we het gehad over de wachtrij, dat is waarom we houden dat hoofd wijzer, zodat we niet constant verschuivende dingen. Want dat wordt duur als je hebt een grote reeks en je bent constant bezig deze willekeurige inserties. Overwegende dat de met een lijst, alles wat je hoeft te doen is gooien het op een nieuw knooppunt, pas de pointers, en je bent klaar. Wat zuigt je hiervan? Afgezien van het feit dat het niet zo eenvoudig om mee te werken als een array? Ja? [Daniel] Nou, ik denk dat het veel moeilijker om toegang tot een specifiek element in de gekoppelde lijst? [Hardison] Je kunt niet zomaar springen naar een willekeurig element in het midden van uw gekoppelde lijst. Hoe moet je in plaats daarvan doen? >> Je moet doorlopen het hele ding. [Hardison] Ja. Je doorlopen een voor een, een voor een. Het is een enorme - het is een pijn. Wat is het andere - is er nog een nadeel aan deze. [Basil] Je kunt niet naar voren en naar achteren? Je moet een richting gaan? [Hardison] Ja. Dus hoe kunnen we dat oplossen, soms? [Basil] Dubbel-gelinkte lijsten? >> Precies. Er zijn dubbel-gelinkte lijsten. Er zijn ook - sorry? 

[Sam] Is dat hetzelfde als het gebruik van de Pred ding dat - Ik herinner me net, is dat niet wat de Pred ding is? Is dat niet tussen dubbel en enkel? [Hardison] Laten we eens kijken naar wat hij precies aan het doen was. Dus hier gaan we dan. Hier is de lijst code. Hier hebben we predptr, hier. Is dit wat je het over? Dus dit was - hij is het vrijmaken van een lijst en hij probeert met een pointer op te slaan aan. Dit is niet het dubbel, afzonderlijk verbonden-lijsten. We kunnen later praten meer over weten omdat dit over het vrijmaken van de lijst en ik wil een aantal andere dingen eerst te tonen. maar het is gewoon - het is het onthouden van de waarde van ptr [Student] Oh, het is voorafgaande pointer? >> Ja. Zodat we kunnen dan verhogen ptr zelf voordat we dan vrij wat predptr is. Omdat we niet kunnen gratis ptr en dan bellen ptr = ptr volgende, toch? Dat zou slecht zijn. Dus laten we eens kijken, terug naar deze man. 

Het andere slechte ding over lijsten is dat terwijl met een array We hebben alle elementen zelf gestapeld naast elkaar, hier hebben we ook geïntroduceerd deze pointer. Dus er is een extra stuk van het geheugen dat we hebben om te gebruiken voor elk element dat we opslaan in onze lijst. We krijgen flexibiliteit, maar het komt op een kostprijs. Het wordt geleverd met deze tijd kosten, en het komt met dit geheugen kost ook. Tijd in de zin dat we nu moeten werken om elk element te gaan in de array de index een op 10, of die zou zijn geweest index 10 in een array vinden. 

Gewoon heel snel, als we diagram uit deze lijsten, meestal houden we vast aan de kop van de lijst of de eerste aanwijzer van de lijst en er rekening mee dat dit een echte pointer. Het is slechts 4 bytes. Het is niet een echte knoop zelf. Zo zie je maar dat het geen int waarde in, geen volgende pointer in zich heeft. Het is letterlijk slechts een wijzer. Het gaat om te wijzen op iets dat een echte knoop struct. [Sam] Een pointer genaamd knoop? >> Dit is - nee. Dit is een verwijzing naar iets van het type node. Het is een pointer naar een knooppunt struct. >> Oh, oke. Diagram links, rechts code. Wij kunnen het aan nul, dat is een goede manier om te beginnen. Wanneer u diagram, je ofwel schrijf het uit als nietig of je zet een streep erdoor zo. 

Een van de makkelijkste manieren om te werken met lijsten, en we vragen u zowel prepend en toe te voegen aan de verschillen tussen de twee te zien, maar prepending is zeker makkelijker. Wanneer u vooraf gaan, dit is waar je - als je prepend (7), je gaat en maakt het knooppunt struct en u stelt als eerste punt aan, want nu, omdat we prepended het, het gaat om aan het begin van de lijst. Als we prepend (3), dat een ander knooppunt maakt, maar nu 3 komt vóór 7. Dus we wezen duwen dingen op onze lijst. Nu, kun je zien dat prepend soms, mensen noemen het duwen, omdat je het duwen van een nieuw element op uw lijst. Het is ook gemakkelijk te verwijderen aan de voorzijde van een lijst. Dus mensen zullen vaak roepen dat pop. En op die manier, kun je emuleren een stapel met behulp van een gekoppelde lijst. Whoops. Sorry, nu zijn we het krijgen in append. Dus hier zijn we prepended (7), nu zijn we prepend (3). Als we voorgevoegd iets anders op deze lijst als we voorgevoegd (4), dan zouden we hebben 4 en vervolgens op 3 en vervolgens op 7. Dus dan kunnen we knallen en verwijder 4, verwijderen 3, verwijderen 7. Vaak is de meer intuïtieve manier om na te denken over dit is met append. Dus ik heb schematisch hoe het eruit zou zien met voegen hier. Hier, toegevoegd (7) ziet er niet anders want er is slechts een element in de lijst. En het toevoegen van (3) zet het op het einde. Misschien kun je nu zien de truc met append is dat omdat we alleen weten waar het begin van de lijst is, toe te voegen aan een lijst die u moet wandelen de weg door de lijst om naar het einde, stop, dan bouw je node en plunk alles op. Bedraad alle spullen op. Dus met prepend, zoals we net geript door deze heel snel, wanneer u vooraf gaan aan een lijst, het is vrij eenvoudig. 

U maakt uw nieuwe node, tot op zekere hoogte dynamisch geheugen toewijzing. Dus hier maken we een knooppunt struct malloc gebruikt. Dus malloc we gebruiken, want dat zal gereserveerd geheugen voor ons voor later omdat we niet willen dat dit - we willen dat dit geheugen blijven voor een lange tijd. En krijgen we een pointer naar de ruimte in het geheugen, dat we gewoon toegewezen. We maken gebruik van grootte van de knoop, we het totaal niet de velden. We hebben geen handmatig genereren aantal bytes, in plaats daarvan gebruiken we sizeof, zodat we weten dat we het juiste aantal bytes krijgt. Wij zorgen ervoor om te testen of onze malloc oproep gelukt. Dit is iets wat je wilt doen in het algemeen. Op moderne computers, een tekort aan geheugen is niet iets dat is gemakkelijk tenzij je het toewijzen van een heleboel dingen en het maken van een enorme lijst, maar als je het bouwen van spullen voor, laten we zeggen, zoals een iPhone of een Android, je hoeft weinig geheugen middelen, vooral als je iets intens. Het is dus goed om in de praktijk. 

Merk op dat ik heb een paar verschillende functies die hier gebruikt dat je hebt gezien dat zijn een soort van nieuwe. Dus fprintf is net printf graag behalve het eerste argument is de stroom waarop u wilt afdrukken. In dit geval willen we afdrukken naar de standaardfout snaar dat verschilt van de standaard uitstroom. Standaard wordt dit in dezelfde plaats. Hij drukt ook uit naar de terminal, maar u kunt - het gebruik van deze commando's die je geleerd over de omleiding technieken je geleerd over in de video Tommy's voor probleem set 4, kunt u direct het naar verschillende gebieden; verlaat, exact hier, verlaat het programma. Het is in wezen net terug van de belangrijkste, behalve dat we gebruik maken van afslag omdat hier terug zal niets doen. We zijn niet in de belangrijkste, is dus terug te keren niet verlaat het programma zoals we willen. Dus gebruiken we de functie Exit en geef het een foutcode. Dan hier zetten we de nieuwe node waarde veld, de i veld gelijk aan i, en dan gaan we bedraden it up. We zetten de nieuwe node volgende pointer te wijzen naar de eerste, en dan eerst zal nu naar de nieuwe node. Deze eerste regels code, we eigenlijk de bouw van de nieuwe node. Niet de laatste twee regels van deze functie, maar de eersten. Je kunt eigenlijk trek in een functie, in een helper functie. Dat is vaak wat ik doe is, ik trek het uit in een functie, Ik noem het iets als build knooppunt, en dat houdt de prepend functie vrij klein, het is slechts 3 lijnen dan. Ik een oproep op mijn build knooppunt functie, en dan heb ik draad alles op. 

Het laatste wat ik wil laten zien, en ik zal u laten doen append en alles wat op uw eigen, is hoe itereren over een lijst. Er zijn een aantal verschillende manieren om itereren over een lijst. In dit geval gaan we de lengte van een lijst. Dus we beginnen met lengte = 0. Dit is vergelijkbaar met het schrijven strlen een string. Dit is wat ik je wil laten zien, dit voor loop hier. Het ziet er een beetje funky, het is niet de gebruikelijke int i = 0, i <wat dan ook, i + +. In plaats daarvan is het initialiseren van onze variabele n naar het begin van de lijst. En dan terwijl onze iterator variabele niet null is, we blijven gaan. Dit is omdat, volgens afspraak, het einde van onze lijst is null. En dan te, verhogen in plaats van het doen van + +, de gekoppelde lijst equivalent + + is n = n-> volgende. 

Ik laat je de hiaten opvullen hier omdat we geen tijd meer. Maar houd dit in gedachten als u aan uw spellr psets. Gelinkte lijsten, als je de implementatie van een hash-tabel, zal zeker komen in zeer handig. En met dit idioom voor het doorlussen over dingen maakt het leven een stuk eenvoudiger, hopelijk. Heeft u vragen, snel? [Sam] Stuurt u de ingevulde sll en sc? [Hardison] Ja. Ik zending komt ingevulde dia's en afgerond sll stack en queue.cs. [CS50.TV]