1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [Muziek] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: Oké. 5 00:00:12,900 --> 00:00:14,600 Iedereen welkom terug naar sectie. 6 00:00:14,600 --> 00:00:18,660 Ik hoop dat jullie allemaal zijn succes hersteld van uw quiz 7 00:00:18,660 --> 00:00:19,510 van vorige week. 8 00:00:19,510 --> 00:00:22,564 Ik weet dat het een beetje gek soms. 9 00:00:22,564 --> 00:00:25,230 Zoals ik al eerder zei: als je binnen de standaardafwijking, 10 00:00:25,230 --> 00:00:28,188 niet echt zorgen over te maken, in het bijzonder een minder comfortabel sectie. 11 00:00:28,188 --> 00:00:30,230 Dat is ongeveer waar je moet zijn. 12 00:00:30,230 --> 00:00:32,850 >> Als je deed het geweldig, dan is geweldig. 13 00:00:32,850 --> 00:00:33,650 Kudos voor jou. 14 00:00:33,650 --> 00:00:36,149 En als je het gevoel dat je nodig hebt een beetje meer hulp nodig, dan kunt u 15 00:00:36,149 --> 00:00:38,140 voel je vrij om te komen uit voor een van de TF's. 16 00:00:38,140 --> 00:00:40,030 We zijn hier allemaal om te helpen. 17 00:00:40,030 --> 00:00:40,960 >> Dat is waarom wij onderwijzen. 18 00:00:40,960 --> 00:00:44,550 Dat is waarom ik hier ben elke maandag voor u jongens en op het kantoor uren op donderdag. 19 00:00:44,550 --> 00:00:48,130 Dus aarzel niet om mij te laten weten als u zich zorgen over iets bent 20 00:00:48,130 --> 00:00:52,450 of als er iets aan de quiz dat je echt wilt pakken. 21 00:00:52,450 --> 00:00:56,940 >> Dus de agenda voor vandaag alles over datastructuren. 22 00:00:56,940 --> 00:01:01,520 Sommige van deze zijn gewoon te gewoon om aan de slag u vertrouwd gemaakt met deze. 23 00:01:01,520 --> 00:01:04,870 Je mag nooit implementeren ze in deze klasse. 24 00:01:04,870 --> 00:01:08,690 Sommigen van hen je wil, net als voor uw speller pset. 25 00:01:08,690 --> 00:01:11,380 >> U zult uw keuze tussen hash tabellen en probeert. 26 00:01:11,380 --> 00:01:13,680 Dus we zullen zeker gaan over deze. 27 00:01:13,680 --> 00:01:18,690 Het zal zeker meer van aard zijn van een level sectie hoog vandaag, hoewel, 28 00:01:18,690 --> 00:01:22,630 want er zijn veel van hen, en als gingen we naar de implementatie details 29 00:01:22,630 --> 00:01:26,490 Op al deze, zouden we niet zelfs via gelinkte lijsten 30 00:01:26,490 --> 00:01:28,520 en misschien een klein beetje hash tabellen. 31 00:01:28,520 --> 00:01:31,200 >> Dus geduld met mij. 32 00:01:31,200 --> 00:01:33,530 We gaan niet te doen zoveel coderen deze tijd. 33 00:01:33,530 --> 00:01:36,870 Als u vragen heeft over het of je wilt zien gebeuren 34 00:01:36,870 --> 00:01:39,260 of probeer het zelf, Ik zeker aanraden 35 00:01:39,260 --> 00:01:44,250 naar study.cs50.net die heeft voorbeelden van al deze. 36 00:01:44,250 --> 00:01:46,400 Het zal mijn PowerPoints hebben met de notities die we 37 00:01:46,400 --> 00:01:50,860 de neiging om te gebruiken als ook een beetje kan programmeren oefeningen, vooral wat er 38 00:01:50,860 --> 00:01:55,250 zoals gelinkte lijsten en binaire bomen stacks en cues. 39 00:01:55,250 --> 00:01:59,590 Dus iets meer hoog niveau, dat misschien wel leuk voor jullie. 40 00:01:59,590 --> 00:02:01,320 >> Dus met dat, zullen we aan de slag. 41 00:02:01,320 --> 00:02:03,060 En ook, yes-- quizzen. 42 00:02:03,060 --> 00:02:06,550 Ik denk dat de meeste van jullie die in mijn deel heb je quizzen, 43 00:02:06,550 --> 00:02:12,060 maar iedereen komt in of andere reden niet doen, ze zijn hier in de voorkant. 44 00:02:12,060 --> 00:02:12,740 >> Dus gelinkte lijsten. 45 00:02:12,740 --> 00:02:15,650 Ik weet dat dit soort gaat om een ​​back voordat je quiz. 46 00:02:15,650 --> 00:02:17,940 Dat was de week voor dat we geleerd over dit. 47 00:02:17,940 --> 00:02:21,040 Maar in dit geval, zullen we gewoon ga een beetje meer in de diepte. 48 00:02:21,040 --> 00:02:25,900 >> Dus waarom zouden we kiezen voor een gelinkte lijst over een array? 49 00:02:25,900 --> 00:02:27,130 Wat onderscheidt hen? 50 00:02:27,130 --> 00:02:27,630 Ja? 51 00:02:27,630 --> 00:02:30,464 >> Publiek: U kunt uitbreiden van een gekoppelde lijst versus een array vaste grootte. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Recht. 53 00:02:31,171 --> 00:02:33,970 Een array heeft vaste afmetingen, terwijl een gelinkte lijst heeft een variabele grootte. 54 00:02:33,970 --> 00:02:36,970 Dus als we niet weten hoe veel we willen slaan, 55 00:02:36,970 --> 00:02:39,880 een gelinkte lijst geeft ons een grote manier om dat te doen, want we kunnen gewoon 56 00:02:39,880 --> 00:02:43,730 toevoegen ander knooppunt en toevoegen andere knoop en toevoegen ander knooppunt. 57 00:02:43,730 --> 00:02:45,750 Maar wat kan een trade-off zijn? 58 00:02:45,750 --> 00:02:49,521 Herinnert iemand zich de trade-off tussen arrays en gelinkte lijsten? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> Publiek: Je moet gaan door de hele weg 61 00:02:51,460 --> 00:02:53,738 via de gelinkte lijst vind een element in een lijst. 62 00:02:53,738 --> 00:02:55,570 In een array, kunt u vind enkel een element. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Recht. 64 00:02:56,278 --> 00:02:57,120 Dus met arrays-- 65 00:02:57,120 --> 00:02:58,500 >> Publiek: [onverstaanbaar]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: Met arrays, we hebben wat heet random access. 67 00:03:01,090 --> 00:03:04,820 Betekent dat wat als we willen is ooit het vijfde punt van een lijst 68 00:03:04,820 --> 00:03:07,230 of het vijfde punt van ons array, kunnen we net pak het. 69 00:03:07,230 --> 00:03:10,440 Als het een gekoppelde lijst, we om door te herhalen, toch? 70 00:03:10,440 --> 00:03:14,020 Dus toegang tot een element in een array constant is tijd, 71 00:03:14,020 --> 00:03:19,530 terwijl met een gekoppelde lijst het zou lineaire tijd hoogstwaarschijnlijk want misschien 72 00:03:19,530 --> 00:03:21,370 onze element is helemaal aan het eind. 73 00:03:21,370 --> 00:03:23,446 We hebben om door middel van alles. 74 00:03:23,446 --> 00:03:25,320 Dus met al deze gegevens structuren gaan we 75 00:03:25,320 --> 00:03:29,330 worden uitgaven een beetje meer tijd op, wat zijn de plussen en negatieven. 76 00:03:29,330 --> 00:03:31,480 Wanneer zouden we willen Gebruik een over de ander? 77 00:03:31,480 --> 00:03:34,970 En dat is een soort van de groter ding om mee te nemen. 78 00:03:34,970 --> 00:03:40,140 >> Dus we hebben hier de definitie van een knooppunt. 79 00:03:40,140 --> 00:03:43,040 Het is als een element in onze gelinkte lijst, toch? 80 00:03:43,040 --> 00:03:46,180 Dus we zijn allemaal bekend met onze typedef structs, 81 00:03:46,180 --> 00:03:47,980 die gingen we dan in beoordeling laatste keer. 82 00:03:47,980 --> 00:03:53,180 Het was eigenlijk gewoon het creëren van een ander datatype die we konden gebruiken. 83 00:03:53,180 --> 00:03:57,930 >> En in dit geval, het is wat het knooppunt dat zal wat integer in te houden. 84 00:03:57,930 --> 00:04:00,210 En wat is dan het tweede deel hier? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Anyone? 87 00:04:05,677 --> 00:04:06,680 >> Publiek: [onverstaanbaar]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Ja. 89 00:04:07,020 --> 00:04:08,400 Het is een pointer naar het volgende knooppunt. 90 00:04:08,400 --> 00:04:12,610 Dus dit zou eigenlijk hier te worden weergegeven. 91 00:04:12,610 --> 00:04:18,790 Dit is een pointer van het type knooppunt naar het volgende ding. 92 00:04:18,790 --> 00:04:22,410 En dat is wat ze omvat onze node. 93 00:04:22,410 --> 00:04:24,060 Cool. 94 00:04:24,060 --> 00:04:29,390 >> Oké, dus met zoeken, want we waren gewoon te zeggen voor de hand, als je 95 00:04:29,390 --> 00:04:31,840 gaan doorzoeken, je moet eigenlijk herhalen 96 00:04:31,840 --> 00:04:33,660 via uw gekoppelde lijst. 97 00:04:33,660 --> 00:04:38,530 Dus als we op zoek bent naar het nummer 9, zouden we beginnen bij ons hoofd 98 00:04:38,530 --> 00:04:41,520 en dat wijst ons in het begin van onze gelinkte lijst, toch? 99 00:04:41,520 --> 00:04:44,600 En we zeggen, OK, doet dit knooppunt bevatten het nummer 9? 100 00:04:44,600 --> 00:04:45,690 Nee? 101 00:04:45,690 --> 00:04:47,500 >> Oké, ga dan naar de volgende. 102 00:04:47,500 --> 00:04:48,312 Volg het. 103 00:04:48,312 --> 00:04:49,520 Bevat het de nummer 9? 104 00:04:49,520 --> 00:04:50,570 Nee. 105 00:04:50,570 --> 00:04:51,550 Volg de volgende. 106 00:04:51,550 --> 00:04:55,490 >> Dus moeten we eigenlijk herhalen via onze gelinkte lijst. 107 00:04:55,490 --> 00:05:00,070 We kunnen niet zomaar rechtstreeks naar waar 9 is. 108 00:05:00,070 --> 00:05:05,860 En als jullie eigenlijk willen zie een aantal pseudo-code daar. 109 00:05:05,860 --> 00:05:10,420 We hebben een aantal zoekfunctie hier dat neemt in-- wat is er nodig in? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Wat denk je? 112 00:05:14,320 --> 00:05:15,960 Dus gemakkelijke. 113 00:05:15,960 --> 00:05:17,784 Wat is dit? 114 00:05:17,784 --> 00:05:18,700 Publiek: [onverstaanbaar]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: Het nummer dat we zoeken. 116 00:05:20,366 --> 00:05:20,980 Right? 117 00:05:20,980 --> 00:05:22,875 En wat zou dit overeenkomen met? 118 00:05:22,875 --> 00:05:25,020 Het is een verwijzing naar? 119 00:05:25,020 --> 00:05:26,000 >> Publiek: Een knooppunt. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: Een knooppunt aan de lijst dat we kijken naar, toch? 121 00:05:28,980 --> 00:05:33,700 Dus hebben we een aantal knooppunten zijn pointer hier. 122 00:05:33,700 --> 00:05:37,240 Dit is een punt dat gaat eigenlijk doorlopen onze lijst. 123 00:05:37,240 --> 00:05:39,630 We stellen het gelijk aan lijst want dat is gewoon 124 00:05:39,630 --> 00:05:44,380 oprichting ervan gelijk aan de start van onze gelinkte lijst. 125 00:05:44,380 --> 00:05:50,660 >> En hoewel het niet NULL, terwijl we hebben nog steeds dingen in onze lijst, 126 00:05:50,660 --> 00:05:55,580 controleren om te zien of dat knooppunt het aantal dat we zoeken. 127 00:05:55,580 --> 00:05:57,740 Return true. 128 00:05:57,740 --> 00:06:01,070 Anders werken, toch? 129 00:06:01,070 --> 00:06:04,870 >> Als het NULL, we verlaten onze while loop en return false 130 00:06:04,870 --> 00:06:08,340 want dat betekent dat we hebben het niet gevonden. 131 00:06:08,340 --> 00:06:11,048 Krijgt iedereen hoe dat werkt? 132 00:06:11,048 --> 00:06:11,548 OK. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Dus met inbrengen, je hebben drie verschillende manieren. 135 00:06:20,260 --> 00:06:25,250 U kunt prepend, u kunt toevoegen en u kunt invoegen in assorti. 136 00:06:25,250 --> 00:06:28,215 In dit geval zijn we ga een prepend doen. 137 00:06:28,215 --> 00:06:33,380 Weet iemand hoe die drie gevallen kunnen verschillen? 138 00:06:33,380 --> 00:06:36,920 >> Dus prepend betekent dat je het aan de voorzijde van uw lijst. 139 00:06:36,920 --> 00:06:39,770 Dus dat zou betekenen dat het niet uitmaakt wat uw knooppunt is, maakt niet uit 140 00:06:39,770 --> 00:06:43,160 wat de waarde is, je gaat om het goed hier op kop, OK? 141 00:06:43,160 --> 00:06:45,160 Het zal de eerste te zijn element in uw lijst. 142 00:06:45,160 --> 00:06:49,510 >> Als je het voegen, het gaat om naar de achterkant van je lijst. 143 00:06:49,510 --> 00:06:54,010 En in te voegen in assorti betekent dat je gaat daadwerkelijk in de plaats te zetten 144 00:06:54,010 --> 00:06:57,700 waar het houdt je gelinkte lijst gesorteerd worden. 145 00:06:57,700 --> 00:07:00,810 Nogmaals, hoe je het gebruikt deze en wanneer u gebruik 146 00:07:00,810 --> 00:07:02,530 ze zullen variëren afhankelijk van uw zaak. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Als het niet nodig gesorteerd worden, prepend neigt 149 00:07:07,750 --> 00:07:10,460 te zijn wat de meeste mensen gebruiken omdat je dat niet doet 150 00:07:10,460 --> 00:07:15,680 moeten gaan door de hele lijst tot het einde om het op toe te vinden, toch? 151 00:07:15,680 --> 00:07:17,720 Je kunt gewoon plak het recht in. 152 00:07:17,720 --> 00:07:21,930 >> Dus gaan we door middel van een inbrengen 1 op dit moment. 153 00:07:21,930 --> 00:07:26,360 Dus een ding dat ik ga raden op deze pset 154 00:07:26,360 --> 00:07:29,820 is om dingen uit te trekken, zoals altijd. 155 00:07:29,820 --> 00:07:35,130 Het is erg belangrijk dat u op de hoogte uw pointers in de juiste volgorde 156 00:07:35,130 --> 00:07:38,620 want als je ze bij te werken iets niet in orde, 157 00:07:38,620 --> 00:07:42,210 je gaat eindigen het verliezen van onderdelen van uw lijst. 158 00:07:42,210 --> 00:07:49,680 >> Dus bijvoorbeeld, in dit geval, we vertelt het hoofd om gewoon punt 1. 159 00:07:49,680 --> 00:07:56,070 Als we gewoon doen dat zonder op te slaan dit 1, 160 00:07:56,070 --> 00:07:58,570 we hebben geen idee wat 1 moet nu wijzen op 161 00:07:58,570 --> 00:08:02,490 omdat we hebben verloren wat de kop wees. 162 00:08:02,490 --> 00:08:05,530 Dus een ding om te onthouden wanneer je aan het doen bent een prepend 163 00:08:05,530 --> 00:08:09,630 is aan wat het te redden hoofd punten naar de eerste plaats, 164 00:08:09,630 --> 00:08:15,210 opnieuw toewijzen het dan, en dan updaten wat uw nieuwe knooppunt moet verwijzen naar. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 In dit geval, dit is een manier om het te doen. 167 00:08:22,560 --> 00:08:25,440 >> Dus als we het gedaan had op deze manier waar we gewoon opnieuw toegewezen hoofd, 168 00:08:25,440 --> 00:08:30,320 we eigenlijk onze verliezen hele lijst, toch? 169 00:08:30,320 --> 00:08:38,000 Een manier om het te doen is om 1 punt te volgende, en dan het hoofd punt 1. 170 00:08:38,000 --> 00:08:42,650 Of u kunt soort doen, zoals de tijdelijke opslag, die ik sprak over. 171 00:08:42,650 --> 00:08:45,670 >> Maar de overheveling van uw pointers in de juiste volgorde 172 00:08:45,670 --> 00:08:48,750 zal heel erg worden belangrijk deze pset. 173 00:08:48,750 --> 00:08:53,140 Anders, je gaat naar een hash hebben tafel of een keer te proberen dat gewoon gaat worden 174 00:08:53,140 --> 00:08:56,014 slechts een deel van de woorden die je willen en dan you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 Publiek: Wat was de tijdelijke opslag ding dat je het over? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: De tijdelijke opslag. 177 00:09:00,305 --> 00:09:02,760 Dus eigenlijk een andere manier kon je dit doen 178 00:09:02,760 --> 00:09:07,650 is slaan het hoofd van iets, zoals slaan de tijdelijke variabele. 179 00:09:07,650 --> 00:09:11,250 Toewijzen aan 1 en dan update 1 naar punt 180 00:09:11,250 --> 00:09:13,830 in wat head gebruikt verwijzen. 181 00:09:13,830 --> 00:09:16,920 Zo is vanzelfsprekend eleganter omdat je 182 00:09:16,920 --> 00:09:20,770 kan een tijdelijke waarde niet nodig, maar gewoon het aanbieden van een andere manier om het te doen. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 En we eigenlijk hebben een code voor dit. 185 00:09:25,790 --> 00:09:28,080 Dus voor gelinkte lijst, we eigenlijk hebben enkele code. 186 00:09:28,080 --> 00:09:31,930 Dus steek hier, dit is prepending. 187 00:09:31,930 --> 00:09:34,290 Dus dit voert aan het hoofd. 188 00:09:34,290 --> 00:09:38,820 >> Dus eerste wat, moet je creëer je nieuwe knooppunt, natuurlijk, 189 00:09:38,820 --> 00:09:40,790 en controleren op NULL. 190 00:09:40,790 --> 00:09:43,250 Altijd goed. 191 00:09:43,250 --> 00:09:47,840 En dan moet je de waarden toe te wijzen. 192 00:09:47,840 --> 00:09:51,260 Wanneer u een nieuw knooppunt te maken, je weet niet wat het is te wijzen op de volgende, 193 00:09:51,260 --> 00:09:54,560 dus je wilt om het te initialiseren op NULL. 194 00:09:54,560 --> 00:09:58,760 Als het uiteindelijk naar iets anders, het wordt opnieuw toegewezen en het is prima. 195 00:09:58,760 --> 00:10:00,740 Als het het eerste wat vermeldt, moet 196 00:10:00,740 --> 00:10:04,270 aan te wijzen, omdat NULL dit is het einde van de lijst. 197 00:10:04,270 --> 00:10:12,410 >> Dus dan om deze in te voegen, zien we hier dat we zijn het toewijzen van de volgende waarde van ons knooppunt 198 00:10:12,410 --> 00:10:17,380 om welke kop is, dat is wat we hier hadden. 199 00:10:17,380 --> 00:10:19,930 Dat is wat we net gedaan. 200 00:10:19,930 --> 00:10:25,820 En dan zijn we het toewijzen van kop tot punt om onze nieuwe knooppunt, want vergeet niet, 201 00:10:25,820 --> 00:10:31,090 nieuwe enige pointer naar een knooppunt, en dat is precies wat het hoofd is. 202 00:10:31,090 --> 00:10:34,370 Dat is precies de reden waarom we hebben deze pijl accessor. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Cool? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> Publiek: Moeten we initialiseren nieuwe naast de eerste null, 207 00:10:41,100 --> 00:10:44,240 of kunnen we gewoon initialiseren om het hoofd? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: New volgende moet NULL beginnen te 209 00:10:48,210 --> 00:10:53,760 omdat je niet weet waar het gaat worden. 210 00:10:53,760 --> 00:10:56,100 Ook dit is een soort van Net als een paradigma. 211 00:10:56,100 --> 00:10:59,900 U stelt het gelijk aan NULL gewoon om ervoor te zeker van zijn dat al uw bases gedekt 212 00:10:59,900 --> 00:11:04,070 voordat u een nieuwe toewijzing, zodat doen je bent altijd gegarandeerd dat het zal 213 00:11:04,070 --> 00:11:08,880 wijzen op een specifieke waarde versus zoals een garbage waarde. 214 00:11:08,880 --> 00:11:12,210 Omdat, ja, we toewijzen nieuwe next automatisch, 215 00:11:12,210 --> 00:11:15,420 maar het is meer net als een goede praktijken om het te initialiseren 216 00:11:15,420 --> 00:11:19,270 op die manier en vervolgens opnieuw toe te wijzen. 217 00:11:19,270 --> 00:11:23,420 >> OK, dus dubbel gelinkte nu lijsten. 218 00:11:23,420 --> 00:11:24,601 Wat vinden we? 219 00:11:24,601 --> 00:11:26,350 Wat is er anders met dubbel gelinkte lijsten? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Dus in onze gelinkte lijsten, we kunnen slechts in één richting bewegen, toch? 222 00:11:34,300 --> 00:11:35,270 We hebben slechts de volgende. 223 00:11:35,270 --> 00:11:36,760 We kunnen alleen maar vooruit gaan. 224 00:11:36,760 --> 00:11:40,300 >> Met een dubbel gelinkte lijst, we kunnen ook achteruit bewegen. 225 00:11:40,300 --> 00:11:44,810 We hebben dus niet alleen de nummer dat we willen bewaren, 226 00:11:44,810 --> 00:11:50,110 we hebben waar het wijst op volgende en waar we net vandaan kwamen. 227 00:11:50,110 --> 00:11:52,865 Dus dit maakt sommige beter traversal. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Dus dubbel gelinkte nodes, zeer vergelijkbaar zijn, toch? 230 00:12:01,240 --> 00:12:05,000 Enige verschil is nu dat we een volgende en vorige. 231 00:12:05,000 --> 00:12:06,235 Het is het enige verschil. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Dus als we prepend of append-- we geen code voor deze up hier-- hebben 234 00:12:14,790 --> 00:12:17,830 maar als je om te proberen en te steek deze, de belangrijkste 235 00:12:17,830 --> 00:12:19,980 is wat je nodig hebt om te maken zorgen dat je het toewijzen 236 00:12:19,980 --> 00:12:23,360 zowel uw vorige en uw volgende pointer correct. 237 00:12:23,360 --> 00:12:29,010 Dus in dit geval, zou je niet alleen initialiseren volgende, 238 00:12:29,010 --> 00:12:31,820 u initialiseren vorige. 239 00:12:31,820 --> 00:12:36,960 Als we aan de kop van de lijst, we zou niet alleen het hoofd gelijk nieuwe te maken, 240 00:12:36,960 --> 00:12:41,750 maar onze nieuwe voorgaande moet wijzen op het hoofd, toch? 241 00:12:41,750 --> 00:12:43,380 >> Dat is het enige verschil. 242 00:12:43,380 --> 00:12:47,200 En als je meer oefenen met willen deze met gelinkte lijsten, met invoegen, 243 00:12:47,200 --> 00:12:49,900 met het verwijderen, met insert in een gevarieerd overzicht, 244 00:12:49,900 --> 00:12:52,670 kijk dan op study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Er is een bos van grote oefeningen. 246 00:12:54,870 --> 00:12:55,870 Ik beveel ze. 247 00:12:55,870 --> 00:12:59,210 Ik wou dat we tijd hadden om te gaan door ze te maar er is een hoop datastructuren 248 00:12:59,210 --> 00:13:01,530 door te komen. 249 00:13:01,530 --> 00:13:02,650 >> OK, dus hash tabellen. 250 00:13:02,650 --> 00:13:07,070 Dit is waarschijnlijk de meest nuttig bit voor uw pset 251 00:13:07,070 --> 00:13:11,090 hier omdat je gaat worden uitvoering van een van deze, of een keer te proberen. 252 00:13:11,090 --> 00:13:12,200 Ik hou echt van hash tabellen. 253 00:13:12,200 --> 00:13:13,110 Ze zijn wel cool. 254 00:13:13,110 --> 00:13:17,080 >> Dus eigenlijk wat gebeurt is een hash table 255 00:13:17,080 --> 00:13:22,050 is wanneer we echt nodig speedy insertie, deletie, en lookup. 256 00:13:22,050 --> 00:13:25,010 Dat zijn de dingen die we prioriteren in een hash table. 257 00:13:25,010 --> 00:13:29,500 Ze kan behoorlijk groot, maar zoals we zullen zien bij de pogingen, 258 00:13:29,500 --> 00:13:33,040 er zijn dingen die veel groter zijn. 259 00:13:33,040 --> 00:13:38,330 >> Maar in principe, alle een hash tafel is een hash-functie 260 00:13:38,330 --> 00:13:47,215 dat vertelt u welke emmer te leggen elk van uw gegevens, elk van uw elementen in. 261 00:13:47,215 --> 00:13:51,140 Een eenvoudige manier om te denken van een hash table is dat het gewoon emmers van de dingen, 262 00:13:51,140 --> 00:13:51,770 toch? 263 00:13:51,770 --> 00:13:59,720 Dus als u het sorteren dingen door net als de eerste letter van hun naam, 264 00:13:59,720 --> 00:14:01,820 dat is net zoiets als een hash table. 265 00:14:01,820 --> 00:14:06,180 >> Dus als ik naar de groep jongens is in groepen van wie de naam begint 266 00:14:06,180 --> 00:14:11,670 met een meer dan hier, of wie dan ook jarig is in januari, februari, maart, 267 00:14:11,670 --> 00:14:15,220 wat dat effectief het creëren van een hash table. 268 00:14:15,220 --> 00:14:18,120 Het is gewoon het creëren van emmers die u elementen sorteren van klein naar 269 00:14:18,120 --> 00:14:19,520 zodat je ze makkelijker kunt vinden. 270 00:14:19,520 --> 00:14:22,300 Dus op deze manier als ik het nodig naar één van je vinden, 271 00:14:22,300 --> 00:14:24,680 Ik hoef niet te zoeken door elk van uw namen. 272 00:14:24,680 --> 00:14:29,490 Ik kan zijn als, oh, ik weet dat Danielle's verjaardag is in-- 273 00:14:29,490 --> 00:14:30,240 Publiek: --April. 274 00:14:30,240 --> 00:14:30,948 SPEAKER 1: April. 275 00:14:30,948 --> 00:14:33,120 Dus ik kijk in mijn april emmer, en met een beetje geluk, 276 00:14:33,120 --> 00:14:38,270 ze zal de enige in daar te zijn en mijn tijd was constant in die zin, 277 00:14:38,270 --> 00:14:41,230 terwijl als ik moet kijken door middel van een hele hoop mensen, 278 00:14:41,230 --> 00:14:43,090 het zal veel langer duren. 279 00:14:43,090 --> 00:14:45,830 Dus hash tabellen zijn eigenlijk alleen maar emmers. 280 00:14:45,830 --> 00:14:48,630 Gemakkelijke manier om te denken van hen. 281 00:14:48,630 --> 00:14:52,930 >> Dus een heel belangrijk ding over een hash table is een hash-functie. 282 00:14:52,930 --> 00:14:58,140 Dus de dingen die ik net over gesproken, zoals je eerste letter van je voornaam 283 00:14:58,140 --> 00:15:01,450 of je verjaardag maand, Dit zijn ideeën die 284 00:15:01,450 --> 00:15:03,070 echt correleren met een hashfunctie. 285 00:15:03,070 --> 00:15:08,900 Het is gewoon een manier om te bepalen welke emmer Je Bent element gaat in, OK? 286 00:15:08,900 --> 00:15:14,850 Dus voor deze PSET, kunt u opzoeken vrijwel elke hash functie die u wilt. 287 00:15:14,850 --> 00:15:16,030 >> Hoeft niet je eigen zijn. 288 00:15:16,030 --> 00:15:21,140 Er zijn een aantal echt toffe gasten uit daar dat allerlei gekke math. 289 00:15:21,140 --> 00:15:25,170 En als u wilt uw maken spellingscontrole super snel, 290 00:15:25,170 --> 00:15:27,620 Ik zou zeker kijken naar een van die. 291 00:15:27,620 --> 00:15:32,390 >> Maar er zijn ook slechten, zoals compute 292 00:15:32,390 --> 00:15:39,010 de som van de woorden, zoals elke letter een nummer. 293 00:15:39,010 --> 00:15:39,940 Bereken de som. 294 00:15:39,940 --> 00:15:42,230 Bepaalt de emmer. 295 00:15:42,230 --> 00:15:45,430 Ze hebben ook de hand liggend dat zijn net als alle van de A's hier, 296 00:15:45,430 --> 00:15:47,050 alle van de B is hier. 297 00:15:47,050 --> 00:15:48,920 Een van deze. 298 00:15:48,920 --> 00:15:55,770 >> Kortom, het is gewoon vertelt u welke array-index van uw element moet ingaan. 299 00:15:55,770 --> 00:15:58,690 Net beslissen de bucket-- het is allemaal een hash-functie is. 300 00:15:58,690 --> 00:16:04,180 Hier hebben we een voorbeeld dat gewoon de eerste letter van de string 301 00:16:04,180 --> 00:16:05,900 dat ik net over sprak. 302 00:16:05,900 --> 00:16:11,900 >> Dus heb je een aantal hash dat is slechts het eerste letter van je touwtje minus A, 303 00:16:11,900 --> 00:16:16,090 waarin u een aantal zal geven getal tussen 0 en 25. 304 00:16:16,090 --> 00:16:20,790 En wat je wilt doen is Zorg ervoor dat dit vertegenwoordigt 305 00:16:20,790 --> 00:16:24,110 de grootte van uw hash table-- hoeveel emmers er zijn. 306 00:16:24,110 --> 00:16:25,860 Met veel van deze hash functies, ze zijn 307 00:16:25,860 --> 00:16:31,630 zal terugkeren waarden die kunnen ver boven het aantal emmers 308 00:16:31,630 --> 00:16:33,610 dat je eigenlijk hebt in je hash table, 309 00:16:33,610 --> 00:16:37,240 dus je moet ervoor zeker en mod door degenen. 310 00:16:37,240 --> 00:16:42,190 Anders, het gaat om te zeggen, oh, het moet in emmer 5000 311 00:16:42,190 --> 00:16:46,040 maar heb je alleen 30 emmers in je hash table. 312 00:16:46,040 --> 00:16:49,360 En natuurlijk, we weten allemaal dat is zal resulteren in een aantal gekke fouten. 313 00:16:49,360 --> 00:16:52,870 Dus zorg ervoor dat mod door de grootte van de hash table. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Cool. 316 00:16:58,930 --> 00:17:00,506 Zo botsingen. 317 00:17:00,506 --> 00:17:02,620 Is iedereen goed tot nu toe? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> Publiek: Waarom zou het zo'n enorme waarde retourneren? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: Afhankelijk van het algoritme dat je hash-functie gebruikt. 321 00:17:09,210 --> 00:17:12,270 Sommigen doen crazy vermenigvuldiging. 322 00:17:12,270 --> 00:17:16,270 En het is allemaal over het krijgen van een gelijkmatige verdeling, 323 00:17:16,270 --> 00:17:18,490 dus ze doen wat echt gekke dingen soms. 324 00:17:18,490 --> 00:17:20,960 Dat is alles. 325 00:17:20,960 --> 00:17:22,140 Iets anders? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Zo botsingen. 328 00:17:24,480 --> 00:17:29,270 Kortom, zoals ik al eerder zei, in het beste geval, 329 00:17:29,270 --> 00:17:32,040 elke emmer Ik kijk in is gaat om een ​​ding te hebben, 330 00:17:32,040 --> 00:17:34,160 dus ik hoef niet te kijken naar alle, toch? 331 00:17:34,160 --> 00:17:37,040 Ik ofwel weet dat het er of het is niet, en dat is wat we echt willen. 332 00:17:37,040 --> 00:17:43,960 Maar als we hebben tienduizenden gegevenspunten en minder dan nummer 333 00:17:43,960 --> 00:17:48,700 emmers, we gaan te hebben botsingen waar uiteindelijk iets 334 00:17:48,700 --> 00:17:54,210 zal hebben om te eindigen in een emmer die al een element. 335 00:17:54,210 --> 00:17:57,390 >> Dus de vraag is, wat doen we in dat geval? 336 00:17:57,390 --> 00:17:58,480 Wat doen wij? 337 00:17:58,480 --> 00:17:59,300 We iets er al? 338 00:17:59,300 --> 00:18:00,060 Gooien we het gewoon uit? 339 00:18:00,060 --> 00:18:00,700 >> Nee. 340 00:18:00,700 --> 00:18:01,980 We moeten beiden houden. 341 00:18:01,980 --> 00:18:06,400 Dus de manier waarop we typisch dat doen is wat? 342 00:18:06,400 --> 00:18:08,400 Wat is de datastructuur we alleen maar over gesproken? 343 00:18:08,400 --> 00:18:09,316 Publiek: Linked lijst. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: Een gelinkte lijst. 345 00:18:10,500 --> 00:18:16,640 Nu, in plaats van elk van deze emmers gewoon met één element, 346 00:18:16,640 --> 00:18:24,020 het gaat om een ​​gekoppelde lijst bevatten de elementen die werden gehashd erin. 347 00:18:24,020 --> 00:18:27,588 OK, doet iedereen soort van dat idee? 348 00:18:27,588 --> 00:18:30,546 Omdat we een array niet konden omdat we niet weten hoeveel dingen 349 00:18:30,546 --> 00:18:31,730 gaan er in kunnen. 350 00:18:31,730 --> 00:18:36,540 Een gelinkte lijst laat ons toe om hoeft alleen het exacte aantal dat 351 00:18:36,540 --> 00:18:38,465 zijn hash in die emmer, toch? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Dus lineaire indringende is in principe is deze idea-- 354 00:18:50,500 --> 00:18:52,300 het is een manier om te gaan met een botsing. 355 00:18:52,300 --> 00:18:58,010 Wat je kunt doen is als, in dit geval, bes werd hash in 1 356 00:18:58,010 --> 00:19:01,130 en die we al hebben daar iets, je gewoon 357 00:19:01,130 --> 00:19:04,840 blijf naar beneden totdat u vindt een leeg slot. 358 00:19:04,840 --> 00:19:06,370 Dat is een manier om het te verwerken. 359 00:19:06,370 --> 00:19:09,020 De andere manier te hanteren het is met wat we zojuist 360 00:19:09,020 --> 00:19:12,280 called-- de gekoppelde lijst wordt genoemd chaining. 361 00:19:12,280 --> 00:19:20,510 >> Dus dit idee werkt als je hash table je denkt 362 00:19:20,510 --> 00:19:24,150 veel groter dan uw gegevens in te stellen of als u 363 00:19:24,150 --> 00:19:28,870 wilt proberen en te minimaliseren chaining totdat het is absoluut noodzakelijk. 364 00:19:28,870 --> 00:19:34,050 Dus een ding is lineair indringende betekent uiteraard 365 00:19:34,050 --> 00:19:37,290 dat je hash-functie is niet zo bruikbaar 366 00:19:37,290 --> 00:19:42,200 want je gaat uiteindelijk met behulp van je hash-functie, om naar een punt, 367 00:19:42,200 --> 00:19:46,400 je Linear sonde naar beneden te een plaats die beschikbaar is. 368 00:19:46,400 --> 00:19:49,670 Maar nu natuurlijk alles anders dat eindigt daar, 369 00:19:49,670 --> 00:19:52,050 je gaat te hebben om zoeken nog verder naar beneden. 370 00:19:52,050 --> 00:19:55,650 >> En er is nog veel meer zoeken uitgave die 371 00:19:55,650 --> 00:19:59,820 gaat in het invoeren van een element in je hash table nu, toch? 372 00:19:59,820 --> 00:20:05,640 En nu wanneer je gaat en proberen te vinden berry nogmaals, je gaat om het te hashen, 373 00:20:05,640 --> 00:20:07,742 en het zal zeggen: oh, kijk in emmer 1, 374 00:20:07,742 --> 00:20:09,700 en het is niet van plan te zijn in emmer 1, dus je bent 375 00:20:09,700 --> 00:20:11,970 gaat moeten doorkruisen de rest van deze. 376 00:20:11,970 --> 00:20:17,720 Dus het is soms nuttig, maar in de meeste gevallen, 377 00:20:17,720 --> 00:20:22,660 we gaan om te zeggen dat chaining is wat je wilt doen. 378 00:20:22,660 --> 00:20:25,520 >> Dus hebben we gesproken over dit eerder. 379 00:20:25,520 --> 00:20:27,812 Ik kreeg een beetje voor mezelf. 380 00:20:27,812 --> 00:20:33,560 Maar chaining is in feite dat elke emmer in je hash table 381 00:20:33,560 --> 00:20:36,120 is gewoon een gelinkte lijst. 382 00:20:36,120 --> 00:20:39,660 >> Dus een andere manier, of meer technische manier te denken van een hash table 383 00:20:39,660 --> 00:20:44,490 is dat het is gewoon een array van gelinkte lijsten, die 384 00:20:44,490 --> 00:20:49,330 als je het schrijven van je woordenboek en je probeert om het te laden, 385 00:20:49,330 --> 00:20:52,070 denk aan het als een reeks van gelinkte lijsten 386 00:20:52,070 --> 00:20:54,390 zal het veel gemakkelijker maken voor u om te initialiseren. 387 00:20:54,390 --> 00:20:57,680 >> Publiek: Dus hash table een vooraf bepaalde grootte, 388 00:20:57,680 --> 00:20:58,980 zoals een [onverstaanbaar] van emmers? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Recht. 390 00:20:59,220 --> 00:21:01,655 Dus het heeft een bepaald aantal emmers dat je determine-- 391 00:21:01,655 --> 00:21:03,530 die jullie moeten voel je vrij om mee te spelen. 392 00:21:03,530 --> 00:21:05,269 Het kan wel cool zijn om te zien wat er gebeurt 393 00:21:05,269 --> 00:21:06,810 als je je een aantal emmers veranderen. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Maar ja, het heeft een ingestelde aantal emmers. 396 00:21:11,510 --> 00:21:15,360 Wat kunt u fit als veel elementen als je nodig hebt 397 00:21:15,360 --> 00:21:19,350 is dit aparte chaining waar u hebben lijsten verbonden in elke emmer. 398 00:21:19,350 --> 00:21:22,850 Dat betekent dat uw hash table zal precies de grootte 399 00:21:22,850 --> 00:21:25,440 dat je het nodig hebt om, toch? 400 00:21:25,440 --> 00:21:27,358 Dat is het hele punt van gelinkte lijsten. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Cool. 403 00:21:32,480 --> 00:21:38,780 >> Dus iedereen OK daar? 404 00:21:38,780 --> 00:21:39,801 Prima. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Wat is er gebeurd? 407 00:21:41,860 --> 00:21:42,960 Echt nu. 408 00:21:42,960 --> 00:21:45,250 Denk dat iemand vermoordt me. 409 00:21:45,250 --> 00:21:52,060 >> OK we gaan in te gaan pogingen, die zijn een beetje gek. 410 00:21:52,060 --> 00:21:53,140 Ik hou van hash tabellen. 411 00:21:53,140 --> 00:21:54,460 Ik denk dat ze echt gaaf. 412 00:21:54,460 --> 00:21:56,710 Tries zijn koel, ook. 413 00:21:56,710 --> 00:21:59,590 >> Dus heeft iemand nog wat te proberen is? 414 00:21:59,590 --> 00:22:01,740 Je moet dan zijn gegaan Kortom in collegezaal? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Weet je nog een soort van hoe het werkt? 417 00:22:06,377 --> 00:22:08,460 Publiek: Ik ben gewoon knikken dat we gaan eroverheen. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: We gaan er overheen. 419 00:22:09,626 --> 00:22:13,100 OK, we gaan echt te gaan dan is het nu wat we zeggen. 420 00:22:13,100 --> 00:22:14,860 >> PUBLIEK: Dat is voor een retrieval boom. 421 00:22:14,860 --> 00:22:15,280 >> SPEAKER 1: Ja. 422 00:22:15,280 --> 00:22:16,196 Het is een retrieval boom. 423 00:22:16,196 --> 00:22:16,960 Awesome. 424 00:22:16,960 --> 00:22:23,610 Dus een ding om hier te merken is dat we zijn op zoek naar individuele tekens 425 00:22:23,610 --> 00:22:24,480 hier, toch? 426 00:22:24,480 --> 00:22:29,710 >> Dus voordat met onze hash-functie, we waren op zoek naar de woorden als een geheel, 427 00:22:29,710 --> 00:22:32,270 en nu zijn we nog op zoek bij de personages, toch? 428 00:22:32,270 --> 00:22:38,380 Dus hebben we Maxwell hier en Mendel. 429 00:22:38,380 --> 00:22:47,840 Dus eigenlijk een try-- een manier om na te denken hiervan is dat elk niveau hier 430 00:22:47,840 --> 00:22:49,000 is een reeks letters. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Dus dit is je root node hier, toch? 433 00:22:55,790 --> 00:23:01,980 Dit heeft alle tekens van de alfabet voor het begin van elk woord. 434 00:23:01,980 --> 00:23:06,480 >> En wat je wilt doen is laten we zeggen, OK, we hebben een aantal M woord. 435 00:23:06,480 --> 00:23:10,590 We gaan op zoek naar Maxwell, dus gaan we naar M. En M wijst op een hele 436 00:23:10,590 --> 00:23:14,800 andere een serie waar elke woorden, zolang er 437 00:23:14,800 --> 00:23:17,044 is een woord dat A heeft als de tweede letter, 438 00:23:17,044 --> 00:23:19,460 zolang er is een woord dat heeft B als de tweede letter, 439 00:23:19,460 --> 00:23:24,630 zal een pointer ga wat volgende array. 440 00:23:24,630 --> 00:23:29,290 >> Er is waarschijnlijk geen woord dat MP iets, 441 00:23:29,290 --> 00:23:32,980 dus bij de P positie in deze array, zou het gewoon NULL zijn. 442 00:23:32,980 --> 00:23:38,840 Het zou zeggen, OK, er is geen woord dat heeft M gevolgd door een P, OK? 443 00:23:38,840 --> 00:23:43,100 Dus als we denken, elke één van deze kleinere zaken 444 00:23:43,100 --> 00:23:47,990 is eigenlijk een van deze grote arrays van A tot Z. 445 00:23:47,990 --> 00:23:55,064 Dus wat zou een van de dingen dat is een soort van een nadeel van een keer te proberen? 446 00:23:55,064 --> 00:23:56,500 >> Publiek: Veel geheugen. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: Het is een ton van het geheugen, toch? 448 00:23:59,940 --> 00:24:08,750 Elk van deze blokken hier vertegenwoordigt 26 ruimtes, 26 element array. 449 00:24:08,750 --> 00:24:13,680 Dus probeert te krijgen ongelooflijk ruimte zwaar. 450 00:24:13,680 --> 00:24:17,100 >> Maar ze zijn erg snel. 451 00:24:17,100 --> 00:24:22,540 Zo ongelooflijk snel, maar echt ruimte inefficiënt. 452 00:24:22,540 --> 00:24:24,810 Soort te achterhalen uit welke je wilt. 453 00:24:24,810 --> 00:24:29,470 Dit zijn echt cool voor uw PSET, maar ze nemen veel van het geheugen, 454 00:24:29,470 --> 00:24:30,290 zodat je de handel af. 455 00:24:30,290 --> 00:24:31,480 Yeah? 456 00:24:31,480 --> 00:24:34,300 >> Publiek: Zou het mogelijk zijn het opzetten van een keer te proberen en dan 457 00:24:34,300 --> 00:24:37,967 als je eenmaal alle gegevens in het dat je need-- 458 00:24:37,967 --> 00:24:39,550 Ik weet niet of dat zinvol zou zijn. 459 00:24:39,550 --> 00:24:42,200 Ik was het wegwerken van alle NULL karakters, maar dan 460 00:24:42,200 --> 00:24:42,910 zou je niet kunnen indexeren them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Je ziet ze nog steeds nodig. 462 00:24:43,275 --> 00:24:44,854 >> PUBLIEK: - op dezelfde manier elke keer. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Ja. 464 00:24:45,520 --> 00:24:50,460 U hebt de NULL karakters te laten je weet als er geen woord daar. 465 00:24:50,460 --> 00:24:52,040 Ben heb je iets wat je wilt hebben? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 Oké, dus we gaan om een ​​beetje meer te gaan 468 00:24:54,581 --> 00:24:58,920 in de technische details achter een keer te proberen en werken door middel van een voorbeeld. 469 00:24:58,920 --> 00:25:01,490 >> OK, dus dit is het zelfde ding. 470 00:25:01,490 --> 00:25:06,290 Overwegende dat in een gelinkte lijst, onze soort van-- wat is het woord dat ik wil? - 471 00:25:06,290 --> 00:25:08,350 zoals het bouwen van blok was een knooppunt. 472 00:25:08,350 --> 00:25:12,280 In een keer te proberen, hebben we ook een knooppunt, maar het is anders gedefinieerd. 473 00:25:12,280 --> 00:25:17,000 >> Dus we hebben een aantal bool dat vertegenwoordigt of een woord eigenlijk 474 00:25:17,000 --> 00:25:23,530 Er is op deze locatie, en vervolgens we hebben een aantal scala hier-- of beter gezegd, 475 00:25:23,530 --> 00:25:27,840 Dit is een pointer naar een reeks van 27 tekens. 476 00:25:27,840 --> 00:25:33,339 En dit is in dit geval, dit 27-- Ik weet zeker dat jullie allemaal zijn als, wacht, 477 00:25:33,339 --> 00:25:34,880 er zijn 26 letters in het alfabet. 478 00:25:34,880 --> 00:25:36,010 Waarom hebben we 27? 479 00:25:36,010 --> 00:25:37,870 >> Dus afhankelijk van de manier waarop je dit te implementeren, 480 00:25:37,870 --> 00:25:43,240 dit is van een PSET dat toegestaan ​​voor de apostrof. 481 00:25:43,240 --> 00:25:46,010 Dus dat is de reden waarom de extra één. 482 00:25:46,010 --> 00:25:50,500 U zult ook in sommige gevallen de null terminator 483 00:25:50,500 --> 00:25:53,230 is als een van de tekens dat het mag zijn, 484 00:25:53,230 --> 00:25:56,120 en dat is hoe ze te controleren op te zien of het is het einde van het woord. 485 00:25:56,120 --> 00:26:01,340 Als je geïnteresseerd bent, check out Kevin's video op study.cs50, 486 00:26:01,340 --> 00:26:04,790 evenals Wikipedia heeft een aantal goede middelen daar. 487 00:26:04,790 --> 00:26:09,000 >> Maar we gaan om te gaan door gewoon een soort van hoe je zou kunnen werken via een try 488 00:26:09,000 --> 00:26:11,010 als je krijgt een. 489 00:26:11,010 --> 00:26:16,230 Dus we hebben een super eenvoudig hier dat heeft de woorden "bat" en "zoom" in hen. 490 00:26:16,230 --> 00:26:18,920 En zoals we zien hier, deze kleine ruimte hier 491 00:26:18,920 --> 00:26:22,560 vertegenwoordigt onze bool dat zegt: ja, dit is een woord. 492 00:26:22,560 --> 00:26:27,060 En dan is dit onze arrays van karakters, toch? 493 00:26:27,060 --> 00:26:33,480 >> Dus we gaan door te gaan het vinden van "bat" in deze poging. 494 00:26:33,480 --> 00:26:38,340 Dus beginnen bij de top, toch? 495 00:26:38,340 --> 00:26:46,290 En we weten dat B komt overeen met de tweede index, het tweede element 496 00:26:46,290 --> 00:26:47,840 in deze array, omdat a en b. 497 00:26:47,840 --> 00:26:51,340 Zo ongeveer de tweede. 498 00:26:51,340 --> 00:26:58,820 >> En het zegt, OK, cool, volgt dat in de volgende reeks, want als we ons herinneren, 499 00:26:58,820 --> 00:27:02,160 het is niet zo dat elk van deze eigenlijk bevat het element. 500 00:27:02,160 --> 00:27:07,110 Elk van deze arrays bevat een pointer, toch? 501 00:27:07,110 --> 00:27:10,030 Het is een belangrijk onderscheid te maken. 502 00:27:10,030 --> 00:27:13,450 >> Ik weet dat dit gaat om be-- probeert zijn echt hard op de eerste keer te krijgen, 503 00:27:13,450 --> 00:27:15,241 dus zelfs als dit het tweede of derde keer 504 00:27:15,241 --> 00:27:18,370 en het is nog steeds soort van schijnbaar moeilijk, 505 00:27:18,370 --> 00:27:21,199 Ik beloof als je horloge de korte morgen weer, 506 00:27:21,199 --> 00:27:22,740 het zal waarschijnlijk maken veel meer zin. 507 00:27:22,740 --> 00:27:23,890 Het duurt veel te verteren. 508 00:27:23,890 --> 00:27:27,800 Ik heb nog steeds wel eens ben als, wacht, wat is het proberen? 509 00:27:27,800 --> 00:27:29,080 Hoe kan ik deze gebruiken? 510 00:27:29,080 --> 00:27:33,880 >> Daarom hebben we in dit geval B, dat is onze tweede index. 511 00:27:33,880 --> 00:27:40,240 Als we hadden, laten we zeggen, c of d of andere letter, 512 00:27:40,240 --> 00:27:45,810 moeten we dat terug naar de index in kaart onze array die overeenkomt met. 513 00:27:45,810 --> 00:27:56,930 Dus we zouden nemen als rchar en we gewoon aftrekken buiten een om het opsplitsen 0 tot 25. 514 00:27:56,930 --> 00:27:58,728 Iedereen goed hoe we kaart ons karakter? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Dus we gaan naar de tweede en we zien dat, ja, het is niet op NULL. 517 00:28:05,980 --> 00:28:07,780 We kunnen doorstromen naar deze volgende array. 518 00:28:07,780 --> 00:28:12,300 Dus we gaan op naar deze volgende reeks hier. 519 00:28:12,300 --> 00:28:15,500 >> En we zeggen, OK, nu we nodig om te zien of een is hier. 520 00:28:15,500 --> 00:28:18,590 Is een null of toch niet eigenlijk vooruit? 521 00:28:18,590 --> 00:28:21,880 Dus een echt beweegt zendt in deze array. 522 00:28:21,880 --> 00:28:24,570 En we zeggen, OK, t is onze laatste brief. 523 00:28:24,570 --> 00:28:27,580 Dus gaan we naar de t op de index. 524 00:28:27,580 --> 00:28:30,120 En dan gaan we vooruit want er is een andere. 525 00:28:30,120 --> 00:28:38,340 En dit zegt in feite dat, ja, het zegt dat er een woord hier-- 526 00:28:38,340 --> 00:28:41,750 dat als je dit volgen pad, u bent gearriveerd 527 00:28:41,750 --> 00:28:43,210 in een woord, waarvan we weten dat "vleermuis." 528 00:28:43,210 --> 00:28:43,800 Ja? 529 00:28:43,800 --> 00:28:46,770 >> Publiek: Is het standaard te hebben dat als index 0 en dan een soort op 1 530 00:28:46,770 --> 00:28:47,660 of aan het eind? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: No. 532 00:28:48,243 --> 00:28:55,360 Dus als we terugkijken naar onze verklaring hier, het is een bool, 533 00:28:55,360 --> 00:28:59,490 dus het eigen element in knooppunt. 534 00:28:59,490 --> 00:29:03,331 Dus het is niet een deel van de array. 535 00:29:03,331 --> 00:29:03,830 Cool. 536 00:29:03,830 --> 00:29:08,370 Dus toen we eindigen ons woord en we zijn op deze array, wat we willen doen 537 00:29:08,370 --> 00:29:12,807 is doen een cheque voor is dit een woord. 538 00:29:12,807 --> 00:29:14,390 En in dit geval, zou ja terugkeren. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Dus op die opmerking, we weten dat "zoo" - wij kennen als mens, dat "zoo" is een woord, 541 00:29:24,090 --> 00:29:24,820 toch? 542 00:29:24,820 --> 00:29:28,990 Maar probeer hier zou zeggen, nee, het is niet. 543 00:29:28,990 --> 00:29:33,980 En het zou zeggen dat, omdat we heb het niet aangewezen als een woord hier. 544 00:29:33,980 --> 00:29:40,440 Hoewel we kunnen doorkruisen tot deze array, 545 00:29:40,440 --> 00:29:43,890 Deze try zou zeggen dat, nee, dierentuin is niet in jouw woordenboek 546 00:29:43,890 --> 00:29:47,070 want we hebben niet aangewezen als zodanig. 547 00:29:47,070 --> 00:29:52,870 >> Dus een manier om dat-- doen oh, sorry, deze. 548 00:29:52,870 --> 00:29:59,450 Dus in dit geval, "zoo" is niet een woord, maar het is in onze poging. 549 00:29:59,450 --> 00:30:05,690 Maar in dit ene, zeggen we dat willen introduceren het woord 'bad', wat er gebeurt 550 00:30:05,690 --> 00:30:08,260 is volgen we through-- b, a, t. 551 00:30:08,260 --> 00:30:11,820 We zijn in deze serie, en we gaan om te zoeken naar h. 552 00:30:11,820 --> 00:30:15,220 >> In dit geval, wanneer we kijk naar de aanwijzer op h, 553 00:30:15,220 --> 00:30:17,890 het wijzend op NULL, OK? 554 00:30:17,890 --> 00:30:20,780 Dus tenzij het expliciet verwijzing naar een andere array, 555 00:30:20,780 --> 00:30:25,000 u ervan uitgaan dat alle pointers in deze array wijzen op null. 556 00:30:25,000 --> 00:30:28,270 Dus in dit geval, is h wijst op null dus kunnen we niets doen, 557 00:30:28,270 --> 00:30:31,540 dus het zou ook terugkeren vals, "bad" is niet in hier. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Dus nu zijn we eigenlijk gaan om te gaan door 560 00:30:35,810 --> 00:30:39,790 hoe zouden we eigenlijk zeggen dat "zoo" is in onze poging. 561 00:30:39,790 --> 00:30:42,920 Hoe gaan we invoegen "dierentuin" in onze try? 562 00:30:42,920 --> 00:30:47,810 Dus op dezelfde manier dat we begonnen met onze gelinkte lijst, we beginnen bij de wortel. 563 00:30:47,810 --> 00:30:50,600 Bij twijfel, beginnen bij de wortel van deze dingen. 564 00:30:50,600 --> 00:30:53,330 >> En we zullen zeggen, OK, z. 565 00:30:53,330 --> 00:30:55,650 z bestaat hierin, en het doet. 566 00:30:55,650 --> 00:30:58,370 Dus je bent over te gaan tot uw volgende array, OK? 567 00:30:58,370 --> 00:31:01,482 En dan de volgende, wij zeggen, OK, doet o bestaan? 568 00:31:01,482 --> 00:31:03,000 Het doet. 569 00:31:03,000 --> 00:31:04,330 Dit bericht. 570 00:31:04,330 --> 00:31:08,670 >> En dus op onze volgende, hebben we gezegd, OK, "dierentuin" bestaat al hier. 571 00:31:08,670 --> 00:31:12,440 Het enige wat we moeten doen is deze gelijk te stellen true, dat er een woord daar. 572 00:31:12,440 --> 00:31:15,260 Als je alles had gevolgd tot ervóór, 573 00:31:15,260 --> 00:31:17,030 het is een woord, dus gewoon stel deze gelijk aan dergelijke. 574 00:31:17,030 --> 00:31:17,530 Ja? 575 00:31:17,530 --> 00:31:22,550 >> Publiek: Dus dan doet dat betekenen dat "ba" is een woord dat ook? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: No. 577 00:31:24,120 --> 00:31:28,870 Dus in dit geval, "ba" we zouden krijgen hier, zouden we zeggen is het een woord, 578 00:31:28,870 --> 00:31:31,590 en het zou nog niet. 579 00:31:31,590 --> 00:31:32,822 OK? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> Publiek: Dus als je eenmaal is het een woord en je zegt ja, dan is het 582 00:31:36,360 --> 00:31:38,380 bevat naar m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: dit heeft dus te maken met-- je het laden van deze in. 584 00:31:42,260 --> 00:31:43,640 Je zegt "zoo" is een woord. 585 00:31:43,640 --> 00:31:47,020 Als je naar check-- als, zeg je wilt zeggen, 586 00:31:47,020 --> 00:31:49,400 betekent "dierentuin" Er bestaan ​​in dit woordenboek? 587 00:31:49,400 --> 00:31:54,200 Je bent alleen gaat om te zoeken naar "dierentuin" en controleer om te zien of het een woord. 588 00:31:54,200 --> 00:31:57,291 Je bent nooit gaan verhuizen tot en met m, want dat is niet 589 00:31:57,291 --> 00:31:58,290 wat u zoekt. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Dus als we eigenlijk wilden add "bad" in deze poging, 592 00:32:08,070 --> 00:32:11,390 we zouden hetzelfde doen zoals we hebben gedaan met "zoo," 593 00:32:11,390 --> 00:32:15,380 behalve wij zouden dat zien als we proberen en te h, bestaat het niet. 594 00:32:15,380 --> 00:32:20,090 Zo kunt u denken aan dit als een poging naar een nieuw knooppunt toe te voegen in een gelinkte lijst, 595 00:32:20,090 --> 00:32:27,210 dus we zouden moeten naar een andere toe te voegen één van deze arrays, zoals zo. 596 00:32:27,210 --> 00:32:35,670 En wat we doen is dat we zojuist de h element van deze array die aan deze. 597 00:32:35,670 --> 00:32:39,430 >> En wat zouden we hier willen doen? 598 00:32:39,430 --> 00:32:43,110 Voeg het toe dat gelijk is aan true want het is een woord. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Cool. 601 00:32:48,150 --> 00:32:48,700 Ik weet het. 602 00:32:48,700 --> 00:32:51,170 Tries zijn niet de meest opwindende. 603 00:32:51,170 --> 00:32:54,250 Geloof me, ik weet het. 604 00:32:54,250 --> 00:32:58,040 >> Dus een ding om te beseffen met pogingen, Ik zei, ze zijn zeer efficiënt. 605 00:32:58,040 --> 00:33:00,080 Dus we hebben ze gezien nemen een ton van de ruimte. 606 00:33:00,080 --> 00:33:01,370 Ze zijn soort van verwarrend. 607 00:33:01,370 --> 00:33:03,367 Dus waarom zouden we ooit deze gebruiken? 608 00:33:03,367 --> 00:33:05,450 We gebruiken deze omdat ze ongelooflijk efficiënt. 609 00:33:05,450 --> 00:33:08,130 >> Dus als je ooit op zoek bent een woord, je bent alleen 610 00:33:08,130 --> 00:33:10,450 begrensd door de lengte van het woord. 611 00:33:10,450 --> 00:33:15,210 Dus als u op zoek bent naar een woord dat lengte vijf, 612 00:33:15,210 --> 00:33:20,940 je bent alleen maar zullen moeten maken hooguit vijf vergelijkingen, OK? 613 00:33:20,940 --> 00:33:25,780 Zo maakt het in principe een constante. 614 00:33:25,780 --> 00:33:29,150 Zoals het inbrengen en lookup zijn in principe constante tijd. 615 00:33:29,150 --> 00:33:33,750 >> Dus als je ooit kunt krijgen iets in constante tijd, 616 00:33:33,750 --> 00:33:35,150 dat is zo goed als het wordt. 617 00:33:35,150 --> 00:33:37,990 Je kan niet beter dan krijgen constante tijd voor deze dingen. 618 00:33:37,990 --> 00:33:43,150 Dat is een van de enorme plussen van pogingen. 619 00:33:43,150 --> 00:33:46,780 >> Maar het is veel ruimte. 620 00:33:46,780 --> 00:33:50,380 Dus je soort moet beslissen wat meer is belangrijk voor je. 621 00:33:50,380 --> 00:33:54,700 En op de computers van vandaag, de ruimte die een try kan duren 622 00:33:54,700 --> 00:33:57,740 misschien heeft geen invloed je dat veel, maar misschien 623 00:33:57,740 --> 00:34:01,350 je te maken hebt met iets dat heeft veel, veel meer dingen, 624 00:34:01,350 --> 00:34:02,810 en een keer te proberen is gewoon niet redelijk. 625 00:34:02,810 --> 00:34:03,000 Ja? 626 00:34:03,000 --> 00:34:05,610 >> PUBLIEK: Wacht, dus je hebt 26 letters in een ieder? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Ja, je hebt 26. 629 00:34:08,570 --> 00:34:16,984 Je hebt een aantal is woord marker en dan je hebt 26 pointers in ieder. 630 00:34:16,984 --> 00:34:17,775 En ze point-- 631 00:34:17,775 --> 00:34:20,280 >> Publiek: En elke 26, ze hebben elk 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Ja. 633 00:34:21,500 --> 00:34:27,460 En dat is waarom, als je kan zie, het heel snel uitbreidt. 634 00:34:27,460 --> 00:34:28,130 Prima. 635 00:34:28,130 --> 00:34:32,524 Dus we gaan om in bomen, die Ik voel me net is gemakkelijker en zal waarschijnlijk 636 00:34:32,524 --> 00:34:36,150 zijn een leuk klein uitstel uit probeert daar. 637 00:34:36,150 --> 00:34:39,620 Dus hopelijk de meeste van jullie hebben een boom gezien. 638 00:34:39,620 --> 00:34:41,820 Niet zoals de mooie degenen buiten, die ik 639 00:34:41,820 --> 00:34:44,340 weet niet of iemand ging buiten onlangs. 640 00:34:44,340 --> 00:34:49,230 Ik ging appel plukken dit weekend, en oh mijn god, het was prachtig. 641 00:34:49,230 --> 00:34:52,250 Ik wist niet dat bladeren eruit zou kunnen zien dat mooi. 642 00:34:52,250 --> 00:34:53,610 >> Dus dit is gewoon een boom, toch? 643 00:34:53,610 --> 00:34:56,790 Het is slechts enkele knoop, en het wijst op een heleboel andere nodes. 644 00:34:56,790 --> 00:34:59,570 Zoals je hier ziet, is dit soort van een terugkerend thema. 645 00:34:59,570 --> 00:35:03,720 Knooppunten wijst naar knooppunten is een soort van de essentie van vele datastructuren. 646 00:35:03,720 --> 00:35:06,670 Het is maar net hoe wij laten wijzen naar elkaar 647 00:35:06,670 --> 00:35:08,600 en hoe we doorkruisen door hen en hoe we 648 00:35:08,600 --> 00:35:14,500 dingen in te voegen dat bepaalt hun verschillende eigenschappen. 649 00:35:14,500 --> 00:35:17,600 >> Dus gewoon wat terminologie, die ik eerder heb gebruikt. 650 00:35:17,600 --> 00:35:20,010 Dus wortel is wat er aan de top. 651 00:35:20,010 --> 00:35:21,200 het is waar we altijd beginnen. 652 00:35:21,200 --> 00:35:23,610 Je kunt het zien als het hoofd ook. 653 00:35:23,610 --> 00:35:28,750 Maar voor bomen, hebben we de neiging om te verwijzen naar het als de wortel. 654 00:35:28,750 --> 00:35:32,820 >> Alles wat op de bodem hier-- bij de zeer, zeer bottom-- 655 00:35:32,820 --> 00:35:34,500 zijn beschouwd bladeren. 656 00:35:34,500 --> 00:35:37,210 Het gaat dus met de hele boom ding, toch? 657 00:35:37,210 --> 00:35:39,860 De bladeren zijn aan de randen van uw boom. 658 00:35:39,860 --> 00:35:45,820 >> En dan hebben we ook een paar termen te praten over knooppunten in relatie 659 00:35:45,820 --> 00:35:46,680 elkaar. 660 00:35:46,680 --> 00:35:49,700 Dus we hebben de ouders, kinderen, en broers en zussen. 661 00:35:49,700 --> 00:35:56,260 Dus in dit geval 3 is de ouder van 5, 6 en 7. 662 00:35:56,260 --> 00:36:00,370 Dus de ouder is wat is één stap boven wat je bent 663 00:36:00,370 --> 00:36:02,940 verwijzen naar, dus gewoon als een stamboom. 664 00:36:02,940 --> 00:36:07,090 Hopelijk is dit allemaal een beetje beetje meer intuïtief dan het probeert. 665 00:36:07,090 --> 00:36:10,970 >> Broers en zussen zijn enige die hebben dezelfde ouder, toch? 666 00:36:10,970 --> 00:36:13,470 Ze zijn op hetzelfde niveau hier. 667 00:36:13,470 --> 00:36:16,960 En dan, als ik was zeggen, kinderen zijn net 668 00:36:16,960 --> 00:36:22,630 wat is een stap hieronder het knooppunt in kwestie, OK? 669 00:36:22,630 --> 00:36:23,470 Cool. 670 00:36:23,470 --> 00:36:25,610 Dus een binaire boom. 671 00:36:25,610 --> 00:36:31,450 Kan iedereen maar raden op een van de kenmerken van de binaire boom? 672 00:36:31,450 --> 00:36:32,770 >> Publiek: Max twee bladeren. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Recht. 674 00:36:33,478 --> 00:36:34,640 Dus maximum van twee bladeren. 675 00:36:34,640 --> 00:36:39,730 Dus in dit ene vóór, hadden we dit één dat drie hadden, maar in een binaire boom, 676 00:36:39,730 --> 00:36:45,000 heb je een maximum van twee kinderen per ouder, toch? 677 00:36:45,000 --> 00:36:46,970 Er is een andere interessante eigenschap. 678 00:36:46,970 --> 00:36:51,550 Weet iemand dat? 679 00:36:51,550 --> 00:36:52,620 Binaire boom. 680 00:36:52,620 --> 00:37:00,350 >> Dus een binaire boom zal alles hebben Op the-- deze is niet sorted-- 681 00:37:00,350 --> 00:37:05,320 maar in een gesorteerd binaire boom, alles rechts 682 00:37:05,320 --> 00:37:08,530 groter is dan de ouder, en alles links 683 00:37:08,530 --> 00:37:10,035 kleiner is dan de oorspronkelijke. 684 00:37:10,035 --> 00:37:15,690 En dat is een quiz geweest vraag voor, dus goed om te weten. 685 00:37:15,690 --> 00:37:19,500 Dus de manier waarop we dit te definiëren, nogmaals, we hebben een ander knooppunt. 686 00:37:19,500 --> 00:37:21,880 Dit lijkt erg op wat? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Dubbel 689 00:37:28,836 --> 00:37:29,320 >> Publiek: Linked lijsten 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: Een dubbel gelinkte lijst, toch? 691 00:37:31,100 --> 00:37:33,690 Dus als we dit vervangen met vorige en volgende, 692 00:37:33,690 --> 00:37:35,670 dit zou een dubbel gelinkte lijst zijn. 693 00:37:35,670 --> 00:37:40,125 Maar in dit geval, we eigenlijk hebben links en rechts en dat is het. 694 00:37:40,125 --> 00:37:41,500 Anders is het precies hetzelfde. 695 00:37:41,500 --> 00:37:43,374 We hebben nog steeds het element u zoekt, 696 00:37:43,374 --> 00:37:45,988 en je hoeft alleen twee pointers gaan naar wat de toekomst biedt. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Ja, dus binaire zoekboom. 699 00:37:51,870 --> 00:37:57,665 Als we merken, alles op de hier is groter than-- 700 00:37:57,665 --> 00:37:59,850 of alles onmiddellijk naar rechts hier 701 00:37:59,850 --> 00:38:02,840 groter dan alles Hier is dan. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Dus als we waren te doorzoeken het, moet zeer dicht bij binary search kijken 704 00:38:14,000 --> 00:38:14,910 hier, toch? 705 00:38:14,910 --> 00:38:17,640 Behalve in plaats van naar de helft van de array, 706 00:38:17,640 --> 00:38:21,720 we alleen maar naar de linker- side of rechterkant van de boom. 707 00:38:21,720 --> 00:38:24,850 Dus het wordt een beetje eenvoudiger, denk ik. 708 00:38:24,850 --> 00:38:29,300 >> Dus als je root is NULL, uiteraard is het gewoon vals. 709 00:38:29,300 --> 00:38:33,470 En als het er is, natuurlijk is het waar. 710 00:38:33,470 --> 00:38:35,320 Als het minder dan zoeken we de linkerkant. 711 00:38:35,320 --> 00:38:37,070 Als het groter is dan, we zoeken de juiste. 712 00:38:37,070 --> 00:38:39,890 Het is precies zoals binary search, gewoon een andere datastructuur 713 00:38:39,890 --> 00:38:40,600 dat we gebruiken. 714 00:38:40,600 --> 00:38:42,790 In plaats van een array, het is gewoon een binaire boom. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, stapelt. 717 00:38:48,090 --> 00:38:51,550 En ook, het lijkt erop dat we misschien een beetje tijd. 718 00:38:51,550 --> 00:38:54,460 Als we dat doen, ik ben blij om te gaan meer dan een van deze weer. 719 00:38:54,460 --> 00:38:56,856 OK, dus stapelt. 720 00:38:56,856 --> 00:39:02,695 Weet iemand wat herinneren stacks-- enige kenmerken van een stapel? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, dus de meesten van ons, denk ik, eten in de eetzaal halls-- 723 00:39:10,400 --> 00:39:13,100 zo veel als we kunnen er niet van om. 724 00:39:13,100 --> 00:39:16,900 Maar natuurlijk kunt u denken aan een stapel letterlijk net als een stapel trays 725 00:39:16,900 --> 00:39:18,460 of een stapel van dingen. 726 00:39:18,460 --> 00:39:21,820 En wat belangrijk is om te beseffen is dat het 727 00:39:21,820 --> 00:39:26,850 something-- de karakteristieke dat noemen we het by-- is LIFO. 728 00:39:26,850 --> 00:39:28,450 Weet iemand wat dat voor staat? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> Publiek: last in, first out. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: Rechts, last in, first out. 732 00:39:32,250 --> 00:39:36,585 Dus als we weten dat, als we het stapelen dingen up, de makkelijkste om te off-- grijpen 733 00:39:36,585 --> 00:39:39,570 en misschien het enige wat we kunnen grijpen uit als onze stack is groot enough-- 734 00:39:39,570 --> 00:39:40,850 is dat top element. 735 00:39:40,850 --> 00:39:43,460 Dus wat is aan te trekken last-- zoals we hier zien, 736 00:39:43,460 --> 00:39:46,370 wat werd geduwd meeste recently-- is 737 00:39:46,370 --> 00:39:51,160 gaat de eerste te zijn ding dat we knallen, OK? 738 00:39:51,160 --> 00:39:56,324 >> Dus wat we hier hebben is andere typedef struct. 739 00:39:56,324 --> 00:39:58,740 Dit is echt net als een Spoedcursus in datastructuur, 740 00:39:58,740 --> 00:40:01,650 dus er is een hoop gegooid op je jongens. 741 00:40:01,650 --> 00:40:02,540 Ik weet het. 742 00:40:02,540 --> 00:40:04,970 Dus nog een struct. 743 00:40:04,970 --> 00:40:06,740 Yay voor structuren. 744 00:40:06,740 --> 00:40:16,660 >> En in dit geval, het is wat wijzer een array dat sommige capaciteit heeft. 745 00:40:16,660 --> 00:40:20,830 Dus dit vertegenwoordigt onze stack hier, net als onze eigenlijke serie 746 00:40:20,830 --> 00:40:22,520 die vasthoudt onze elementen. 747 00:40:22,520 --> 00:40:24,850 En dan hebben we hier een aantal grootte. 748 00:40:24,850 --> 00:40:31,170 >> En meestal, dat u wilt behouden spoor van hoe groot je stack 749 00:40:31,170 --> 00:40:36,180 want wat het gaat toestaan je moet doen is als je weet dat de grootte, 750 00:40:36,180 --> 00:40:39,170 staat het u te zeggen, OK, ben ik op de capaciteit? 751 00:40:39,170 --> 00:40:40,570 Kan ik iets meer toe te voegen? 752 00:40:40,570 --> 00:40:44,650 En het vertelt je ook waar de top van je stack 753 00:40:44,650 --> 00:40:48,180 is zodat je weet wat je daadwerkelijk kan opstijgen. 754 00:40:48,180 --> 00:40:51,760 En dat is eigenlijk gaat zijn hier een beetje meer duidelijk. 755 00:40:51,760 --> 00:40:57,350 >> Dus voor push, een ding, als je waren ooit te implementeren duwen, 756 00:40:57,350 --> 00:41:01,330 zoals ik was gewoon te zeggen, uw stack heeft een beperkte omvang, toch? 757 00:41:01,330 --> 00:41:03,990 Ons aanbod had wat capaciteit. 758 00:41:03,990 --> 00:41:04,910 Het is een matrix. 759 00:41:04,910 --> 00:41:08,930 Het is een vaste grootte, dus we moeten ervoor te zorgen dat we niet zetten meer 760 00:41:08,930 --> 00:41:11,950 in ons aanbod dan wij eigenlijk hebben ruimte voor. 761 00:41:11,950 --> 00:41:16,900 >> Dus als je het maken van een push functie, het eerste wat je doet is zeggen, OK, 762 00:41:16,900 --> 00:41:18,570 moet ik ruimte in mijn stack? 763 00:41:18,570 --> 00:41:23,330 Want als ik niet, sorry, Ik kan uw element niet bewaren. 764 00:41:23,330 --> 00:41:28,980 Als ik dat doe, dan wil je slaan het aan de top van de stack, recht? 765 00:41:28,980 --> 00:41:31,325 >> En dit is de reden waarom we hebben bij te houden van onze omvang te houden. 766 00:41:31,325 --> 00:41:35,290 Als we niet te houden van onze omvang, we weten niet waar te zetten. 767 00:41:35,290 --> 00:41:39,035 We weten niet hoeveel dingen zijn in ons aanbod al. 768 00:41:39,035 --> 00:41:41,410 Net als natuurlijk zijn er manieren dat misschien zou je het kunnen doen. 769 00:41:41,410 --> 00:41:44,610 Je kon alles initialiseren op NULL en controleer vervolgens voor de nieuwste NULL, 770 00:41:44,610 --> 00:41:47,950 maar een veel eenvoudiger ding is gewoon te zeggen, OK, bijhouden van grootte. 771 00:41:47,950 --> 00:41:51,840 Net als ik weet dat ik vier elementen in mijn array, dus de volgende ding 772 00:41:51,840 --> 00:41:55,930 dat we op, we zijn gaat slaan bij index 4. 773 00:41:55,930 --> 00:42:00,940 En dan, natuurlijk, betekent dit dat je hebt met succes iets geduwd 774 00:42:00,940 --> 00:42:03,320 op je stack, je het formaat wilt vergroten 775 00:42:03,320 --> 00:42:08,880 zodat je weet waar je bent zo dat je meer dingen kunt duwen. 776 00:42:08,880 --> 00:42:12,730 >> Dus als we proberen om pop iets uit de stapel, 777 00:42:12,730 --> 00:42:16,072 wat zou het eerste ding zijn dat we willen controleren? 778 00:42:16,072 --> 00:42:18,030 Je probeert te nemen iets van je stack. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Weet je zeker dat er iets in je stack? 781 00:42:24,781 --> 00:42:25,280 Nee. 782 00:42:25,280 --> 00:42:26,894 Dus wat zouden we willen controleren? 783 00:42:26,894 --> 00:42:27,810 >> Publiek: [onverstaanbaar]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Controleer voor de grootte? 785 00:42:29,880 --> 00:42:31,840 Size. 786 00:42:31,840 --> 00:42:38,520 Dus we willen controleren om te zien of onze omvang is groter dan 0, OK? 787 00:42:38,520 --> 00:42:44,970 En als het is, dan willen we verlagen onze omvang door 0 en terug te keren dat. 788 00:42:44,970 --> 00:42:45,840 Waarom? 789 00:42:45,840 --> 00:42:49,950 >> In de eerste waren we duwen, we duwde hem 790 00:42:49,950 --> 00:42:52,460 op grootte en vervolgens geactualiseerd grootte. 791 00:42:52,460 --> 00:42:57,850 In dit geval zijn we aflopende grootte en vervolgens het nemen van het uit, het plukken van het 792 00:42:57,850 --> 00:42:58,952 uit ons aanbod. 793 00:42:58,952 --> 00:42:59,826 Waarom zouden we dat doen? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Dus als ik een ding op mijn stack, wat mijn maat op dat punt zou zijn? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> En waar wordt element 1 opgeslagen? 798 00:43:15,180 --> 00:43:17,621 Op welke index? 799 00:43:17,621 --> 00:43:18,120 Publiek: 0. 800 00:43:18,120 --> 00:43:19,060 SPEAKER 1: 0. 801 00:43:19,060 --> 00:43:22,800 Dus in dit geval, we altijd moet maken sure-- 802 00:43:22,800 --> 00:43:27,630 in plaats van terug te keren minus 1, omdat we 803 00:43:27,630 --> 00:43:31,730 weten dat onze element is gaan 1 minder worden opgeslagen 804 00:43:31,730 --> 00:43:34,705 wat onze omvang is, dit net verzorgt het. 805 00:43:34,705 --> 00:43:36,080 Het is een iets elegantere manier. 806 00:43:36,080 --> 00:43:41,220 En we gewoon verlagen onze grootte en dan terug grootte. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> Publiek: Ik denk gewoon in het algemeen, waarom zou deze datastructuur 809 00:43:45,300 --> 00:43:47,800 nuttig zijn? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: Het hangt af van uw context. 811 00:43:50,660 --> 00:43:57,420 Dus voor sommige van de theorie, als je werkt met-- OK, 812 00:43:57,420 --> 00:44:02,750 laat me zien of er een heilzame die bijdragen tot meer dan daarbuiten 813 00:44:02,750 --> 00:44:05,420 van CS. 814 00:44:05,420 --> 00:44:15,780 Met stapels, elke keer dat je nodig hebt bij te houden van iets houden dat 815 00:44:15,780 --> 00:44:20,456 wordt de meest recent toegevoegde is wanneer je gaat te willen een stack gebruiken. 816 00:44:20,456 --> 00:44:24,770 >> En ik kan niet denken aan een goede voorbeeld van dat recht nu. 817 00:44:24,770 --> 00:44:29,955 Maar wanneer de meest recente wat is het meest belangrijk voor je is, 818 00:44:29,955 --> 00:44:31,705 dat is wanneer een stapel zal nuttig zijn. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Ik probeer te denken als er is een goed jaar voor dit. 821 00:44:39,330 --> 00:44:43,720 Als ik denk aan een goed voorbeeld in het volgende 20 minuten, ik zal zeker je vertellen. 822 00:44:43,720 --> 00:44:49,455 >> Maar over het algemeen, als er iets is, zoals ik al zei de meeste, waar de meest recente 823 00:44:49,455 --> 00:44:52,470 het belangrijkste is, dat is waar een stapel in het spel komt. 824 00:44:52,470 --> 00:44:58,860 Overwegende dat de wachtrijen zijn soort van het tegenovergestelde. 825 00:44:58,860 --> 00:44:59,870 En alle kleine honden. 826 00:44:59,870 --> 00:45:00,890 Is dit niet geweldig, toch? 827 00:45:00,890 --> 00:45:03,299 Ik voel me alsof ik zou moeten gewoon een konijntje video 828 00:45:03,299 --> 00:45:05,090 in het midden van sectie voor jullie 829 00:45:05,090 --> 00:45:08,870 omdat dit een intense sectie. 830 00:45:08,870 --> 00:45:10,480 >> Dus een wachtrij. 831 00:45:10,480 --> 00:45:12,710 In principe is een wachtrij is als een lijn. 832 00:45:12,710 --> 00:45:15,780 Jullie Ik weet zeker gebruik deze elke dag, Net als in onze eetzalen. 833 00:45:15,780 --> 00:45:18,160 Dus we moeten gaan in en krijg onze dienbladen, ik ben 834 00:45:18,160 --> 00:45:21,260 ervoor dat je hoeft te wachten in de rij te vegen of je je eten. 835 00:45:21,260 --> 00:45:24,650 >> Dus hier het verschil is dat dit FIFO. 836 00:45:24,650 --> 00:45:30,090 Dus als LIFO is voor het laatst in, eerst out, FIFO is first in, first out. 837 00:45:30,090 --> 00:45:33,400 Dus dit is waar wat je zetten op eerste is uw belangrijkste. 838 00:45:33,400 --> 00:45:35,540 Dus als je zaten te wachten in een line-- kunt u 839 00:45:35,540 --> 00:45:39,130 stel je voor als je ging naar haal de nieuwe iPhone 840 00:45:39,130 --> 00:45:42,800 en het was een stapel waarbij de laatste persoon in de rij kreeg het eerste, 841 00:45:42,800 --> 00:45:44,160 mensen zouden vermoorden elkaar. 842 00:45:44,160 --> 00:45:49,800 >> Dus FIFO, we zijn allemaal zeer vertrouwd met in hier de echte wereld, 843 00:45:49,800 --> 00:45:54,930 en het heeft allemaal te maken met het daadwerkelijk soort herscheppen van dit hele lijn 844 00:45:54,930 --> 00:45:56,900 en de rij-structuur. 845 00:45:56,900 --> 00:46:02,390 Dus terwijl de stack, we hebben push en pop. 846 00:46:02,390 --> 00:46:06,440 Met een wachtrij, we hebben enqueue en dequeue. 847 00:46:06,440 --> 00:46:10,910 Dus enqueue betekent in feite zet het op de rug, 848 00:46:10,910 --> 00:46:13,680 en dequeue middelen nemen off van het front. 849 00:46:13,680 --> 00:46:18,680 Dus onze datastructuur is een beetje meer ingewikkeld. 850 00:46:18,680 --> 00:46:21,060 We hebben een tweede ding bij te houden. 851 00:46:21,060 --> 00:46:25,950 >> Dus zonder het hoofd, dit is precies een stapel, toch? 852 00:46:25,950 --> 00:46:27,900 Dit is dezelfde structuur als een stapel. 853 00:46:27,900 --> 00:46:32,480 Het enige wat anders is dat we nu hebben dit hoofd, dat wat denk je 854 00:46:32,480 --> 00:46:34,272 gaat om bij te houden? 855 00:46:34,272 --> 00:46:35,510 >> Publiek: De eerste. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Rechts, de eerste ding dat we in. 857 00:46:38,685 --> 00:46:41,130 Het hoofd van onze wachtrij. 858 00:46:41,130 --> 00:46:42,240 Wie is de eerste in de rij. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Oké, dus als we enqueue doen. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Opnieuw met een van deze datastructuren, 863 00:46:55,920 --> 00:46:59,760 omdat we te maken hebben met een array, we moeten controleren of we nog ruimte. 864 00:46:59,760 --> 00:47:03,290 >> Dit is net zoiets als mij te vertellen jullie, als je een bestand opent, 865 00:47:03,290 --> 00:47:04,760 je nodig hebt om te controleren op null. 866 00:47:04,760 --> 00:47:08,330 Met een van deze stapels en wachtrijen, moet je 867 00:47:08,330 --> 00:47:13,420 om te zien of er ruimte omdat we maken met een vaste grootte array, 868 00:47:13,420 --> 00:47:16,030 zoals we zien hier-- 0, 1 al tot 5. 869 00:47:16,030 --> 00:47:20,690 Dus wat wij doen in dat geval is check om te zien of we nog steeds de ruimte. 870 00:47:20,690 --> 00:47:23,110 Is onze omvang kleiner dan de capaciteit? 871 00:47:23,110 --> 00:47:28,480 >> Als dat zo is, moeten we het op te slaan op de staart en we onze omvang te updaten. 872 00:47:28,480 --> 00:47:30,250 Dus wat zou de staart zijn in dit geval? 873 00:47:30,250 --> 00:47:32,360 Het is niet expliciet uitgeschreven. 874 00:47:32,360 --> 00:47:33,380 Hoe zouden we opslaan? 875 00:47:33,380 --> 00:47:34,928 Wat zou de staart zijn? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Dus laten we lopen door dit voorbeeld. 878 00:47:40,190 --> 00:47:44,590 Dus dit is een array van grootte 6, toch? 879 00:47:44,590 --> 00:47:49,220 En we hebben op dit moment, onze grootte is 5. 880 00:47:49,220 --> 00:47:55,240 En toen we hem in, het gaat in te gaan op de vijfde index, toch? 881 00:47:55,240 --> 00:47:57,030 Dus slaan bij de staart. 882 00:47:57,030 --> 00:48:05,600 >> Een andere manier om de staart te schrijven zou net zijn ons aanbod aan index van omvang, toch? 883 00:48:05,600 --> 00:48:07,560 Deze maat is 5. 884 00:48:07,560 --> 00:48:11,490 Volgende ding is in te gaan op 5 om te gaan. 885 00:48:11,490 --> 00:48:12,296 Cool? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Het wordt iets ingewikkelder wanneer we beginnen knoeien met het hoofd. 888 00:48:16,350 --> 00:48:17,060 Ja? 889 00:48:17,060 --> 00:48:20,090 >> Publiek: Betekent dit dat we zou een array hebben verklaard dat 890 00:48:20,090 --> 00:48:23,880 was vijf elementen lang en Vervolgens voegen we op het? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: No. 892 00:48:24,730 --> 00:48:27,560 Dus in dit geval, is een stapel. 893 00:48:27,560 --> 00:48:31,760 Dit wordt verklaard als een array van grootte 6. 894 00:48:31,760 --> 00:48:37,120 En in dit geval, we slechts één ruimte links. 895 00:48:37,120 --> 00:48:42,720 >> OK, dus een ding is in dit geval, als ons hoofd is op 0, 896 00:48:42,720 --> 00:48:45,270 dan kunnen we alleen maar kunnen het toevoegen aan de grootte. 897 00:48:45,270 --> 00:48:51,020 Maar het wordt een beetje lastiger omdat zelfs, zij 898 00:48:51,020 --> 00:48:52,840 heb een dia niet voor deze, dus ik ga 899 00:48:52,840 --> 00:48:56,670 om één te tekenen omdat het niet zo simpel als je eenmaal 900 00:48:56,670 --> 00:48:59,230 start het wegwerken van dingen. 901 00:48:59,230 --> 00:49:03,920 Dus terwijl met een stapel zodat u alleen 902 00:49:03,920 --> 00:49:08,920 te maken over wat de grootte is als je iets toe te voegen aan, 903 00:49:08,920 --> 00:49:15,710 met een wachtrij die u moet ook ervoor ervoor dat je hoofd wordt verantwoord, 904 00:49:15,710 --> 00:49:20,760 omdat een koele ding over wachtrijen is dat als je niet bij de capaciteit, 905 00:49:20,760 --> 00:49:23,040 je kunt eigenlijk maken het wikkelen. 906 00:49:23,040 --> 00:49:28,810 >> OK, dus één thing-- oh, dit is verschrikkelijk krijt. 907 00:49:28,810 --> 00:49:31,815 Een ding om te overwegen is het geval. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 We zullen gewoon doen vijf. 910 00:49:37,140 --> 00:49:41,810 OK, dus we gaan zeggen dat de kop is hier. 911 00:49:41,810 --> 00:49:46,140 Dit is 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> De kop is er, en neem eens dingen in hen. 913 00:49:54,210 --> 00:49:58,340 En we willen iets toe te voegen, toch? 914 00:49:58,340 --> 00:50:01,170 Dus het ding dat we nodig hebben om weten is dat het hoofd is altijd 915 00:50:01,170 --> 00:50:05,620 gaat op deze manier te bewegen en dan loop terug rond, OK? 916 00:50:05,620 --> 00:50:10,190 >> Dus deze wachtrij heeft ruimte, toch? 917 00:50:10,190 --> 00:50:13,950 Het heeft ruimte in het allereerste begin, soort Tegengesteld hieraan. 918 00:50:13,950 --> 00:50:17,920 Dus wat we moeten doen is dat we nodig om de staart te berekenen. 919 00:50:17,920 --> 00:50:20,530 Als u weet dat uw hoofd heeft niet bewogen, staart 920 00:50:20,530 --> 00:50:24,630 is gewoon de array op de index van de grootte. 921 00:50:24,630 --> 00:50:30,000 >> Maar in werkelijkheid, als je met behulp van een wachtrij, je hoofd is waarschijnlijk bijgewerkt. 922 00:50:30,000 --> 00:50:33,890 Dus wat je hoeft te doen is eigenlijk berekenen de staart. 923 00:50:33,890 --> 00:50:39,990 Dus wat we doen is deze formule hier, die ik ga u laten 924 00:50:39,990 --> 00:50:42,680 jullie denken over, en dan kunnen we erover praten. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Dus dit is de capaciteit. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Zo zal dit ook daadwerkelijk geven u een manier om het te doen. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Omdat in dit geval, wat? 931 00:51:04,330 --> 00:51:09,205 Ons hoofd is op 1, onze grootte is 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Als we mod dat door 5, krijgen we 0, dat is waar we moeten ingang het. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Dus dan in het volgende geval, als we waren om dit te doen, 936 00:51:26,080 --> 00:51:33,390 wij zeggen, OK, laten we dequeue iets. 937 00:51:33,390 --> 00:51:34,390 We dequeue dit. 938 00:51:34,390 --> 00:51:37,740 We nemen dit element, toch? 939 00:51:37,740 --> 00:51:47,930 >> En nu ons hoofd is hier te wijzen, en we willen voegen in een ander ding. 940 00:51:47,930 --> 00:51:52,470 Dit is in principe achterkant van onze lijn, toch? 941 00:51:52,470 --> 00:51:55,450 Wachtrijen kunnen wikkel rond de array. 942 00:51:55,450 --> 00:51:57,310 Dat is een van de belangrijkste verschillen. 943 00:51:57,310 --> 00:51:58,780 Stacks, kun je dit niet doen. 944 00:51:58,780 --> 00:52:01,140 >> Met wachtrijen, je kan want het enige dat telt 945 00:52:01,140 --> 00:52:03,940 is dat je weet wat werd het meest recent toegevoegd. 946 00:52:03,940 --> 00:52:10,650 Aangezien alles zal worden toegevoegd deze naar links richting, in dit geval, 947 00:52:10,650 --> 00:52:16,480 en vervolgens wikkel rond, je kan voort te zetten in nieuwe elementen 948 00:52:16,480 --> 00:52:18,830 aan de voorzijde van de matrix want het is niet echt 949 00:52:18,830 --> 00:52:20,640 de voorzijde van de matrix meer. 950 00:52:20,640 --> 00:52:26,320 U kunt denken aan het begin van de array waar je hoofd eigenlijk is. 951 00:52:26,320 --> 00:52:29,710 >> Dus deze formule is hoe je je staart te berekenen. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Is dat zinvol? 954 00:52:35,610 --> 00:52:36,110 OK. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK, dequeue, en vervolgens jullie hebben 10 minuten 957 00:52:44,040 --> 00:52:48,840 om me vragen te verduidelijken vragen je wilt, want ik weet dat het gek. 958 00:52:48,840 --> 00:52:51,980 >> Oké, dus in dezelfde way-- Ik weet niet of jullie opgevallen, 959 00:52:51,980 --> 00:52:53,450 maar CS is alles over patronen. 960 00:52:53,450 --> 00:52:57,370 Dingen zijn vrijwel hetzelfde, alleen met kleine tweaks. 961 00:52:57,370 --> 00:52:58,950 Dus hier hetzelfde. 962 00:52:58,950 --> 00:53:04,040 We moeten controleren om of we eigenlijk zien hebben iets in onze rij, toch? 963 00:53:04,040 --> 00:53:05,960 Zeggen, OK, is onze omvang groter dan 0? 964 00:53:05,960 --> 00:53:06,730 Cool. 965 00:53:06,730 --> 00:53:10,690 >> Als we dat doen, dan ons hoofd, gaan we die is wat ik net hier gedemonstreerd. 966 00:53:10,690 --> 00:53:13,870 We werken onze hoofd naar een meer te zijn. 967 00:53:13,870 --> 00:53:18,390 En dan verlagen we onze de grootte en de terugkeer van het element. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Er is veel concreter code op study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 en ik aanbevelen te gaan er doorheen als je tijd hebt, 971 00:53:29,440 --> 00:53:30,980 zelfs als het is gewoon een pseudo-code. 972 00:53:30,980 --> 00:53:35,980 En als jullie willen door middel van praten die bij mij één op één, laat het me 973 00:53:35,980 --> 00:53:37,500 ken. 974 00:53:37,500 --> 00:53:38,770 Ik zou graag. 975 00:53:38,770 --> 00:53:42,720 Gegevensstructuren als je CS 124 nemen, dan heb je 976 00:53:42,720 --> 00:53:47,830 weten dat datastructuren erg plezier en dit is nog maar net begonnen. 977 00:53:47,830 --> 00:53:50,350 >> Dus ik weet dat het moeilijk. 978 00:53:50,350 --> 00:53:51,300 Het is OK. 979 00:53:51,300 --> 00:53:52,410 We worstelen. 980 00:53:52,410 --> 00:53:53,630 Doe ik nog steeds. 981 00:53:53,630 --> 00:53:56,660 Dus niet te veel zorgen over te maken. 982 00:53:56,660 --> 00:54:02,390 >> Maar dat is in principe uw Spoedcursus in datastructuren. 983 00:54:02,390 --> 00:54:03,400 Ik weet dat het veel. 984 00:54:03,400 --> 00:54:06,860 Is er iets dat we wil om opnieuw te gaan? 985 00:54:06,860 --> 00:54:09,400 Alles wat we willen door middel van praten? 986 00:54:09,400 --> 00:54:10,060 Ja? 987 00:54:10,060 --> 00:54:16,525 >> Publiek: voor dat voorbeeld, zodat de nieuwe staart is aan 0 dan dat? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Ja. 989 00:54:17,150 --> 00:54:18,230 Publiek: OK. 990 00:54:18,230 --> 00:54:24,220 Dus dan gaan door, zou je 1 plus 4 of-- hebben 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Dus je zei, wanneer we willen gaan opnieuw doen dit? 992 00:54:27,671 --> 00:54:28,296 Publiek: Ja. 993 00:54:28,296 --> 00:54:38,290 Dus als je het uitzoeken out-- waar zijn u de berekening van de staart uit in dat? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Dus de staart was in-- ik dit veranderd. 995 00:54:44,260 --> 00:54:52,010 In dit voorbeeld hier was de array waar we naar kijken, OK? 996 00:54:52,010 --> 00:54:54,670 Dus hebben we de dingen in 1, 2, 3, en 4. 997 00:54:54,670 --> 00:55:05,850 Dus hebben we onze kop is gelijk aan 1 op dit punt, en onze wijdte 4 998 00:55:05,850 --> 00:55:07,050 op dit punt, toch? 999 00:55:07,050 --> 00:55:08,960 >> Je allemaal over eens dat het geval is? 1000 00:55:08,960 --> 00:55:14,620 Dus we doen het hoofd plus de grootte, die geeft ons 5, en dan modden we door 5. 1001 00:55:14,620 --> 00:55:20,690 We krijgen 0, die ons vertelt dat 0 is waar is onze staart, waar we de ruimte. 1002 00:55:20,690 --> 00:55:22,010 >> Publiek: Wat is een pet? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: De capaciteit. 1004 00:55:23,520 --> 00:55:24,020 Sorry. 1005 00:55:24,020 --> 00:55:29,640 Dus dat is de grootte van de array. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Ja? 1008 00:55:36,047 --> 00:55:39,210 >> Publiek: [onverstaanbaar] vóór we het element terug? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Dus gaan we de hoofd of terugkeren op het moment? 1010 00:55:46,270 --> 00:55:52,680 Dus als we een te verplaatsen, te verlagen van de grootte? 1011 00:55:52,680 --> 00:55:54,150 Hold on. 1012 00:55:54,150 --> 00:55:55,770 Ik vergat zeker een ander. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Maakt niet uit. 1015 00:56:01,990 --> 00:56:04,980 Er is niet een andere formule. 1016 00:56:04,980 --> 00:56:09,980 Ja, zou je willen terugkeren de kop en verplaats het dan terug. 1017 00:56:09,980 --> 00:56:13,270 >> Publiek: OK, omdat op dit punt, het hoofd was op 0, 1018 00:56:13,270 --> 00:56:18,452 en dan wil je om terug te keren index 0 en vervolgens het hoofd 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Recht. 1020 00:56:19,870 --> 00:56:22,820 Ik denk dat er een andere formule zoiets als dit. 1021 00:56:22,820 --> 00:56:26,970 Ik heb het niet op de top van mijn hoofd als Ik wil niet dat je de verkeerde te geven. 1022 00:56:26,970 --> 00:56:35,470 Maar ik denk dat het volkomen geldig tot laten we zeggen, OK, bewaar dit element-- wat 1023 00:56:35,470 --> 00:56:40,759 hoofd element is-- verlagen uw grootte, beweeg je hoofd over, en terugkeer 1024 00:56:40,759 --> 00:56:41,800 wat dat element is. 1025 00:56:41,800 --> 00:56:44,760 Dat is volkomen geldig. 1026 00:56:44,760 --> 00:56:45,260 OK. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Ik voel me als dit is niet zoals de most-- je bent niet 1029 00:56:53,560 --> 00:56:55,740 gaan om uit te lopen van hier als, ja, ik weet het probeert. 1030 00:56:55,740 --> 00:56:56,880 Ik heb het allemaal. 1031 00:56:56,880 --> 00:56:57,670 Dat is OK. 1032 00:56:57,670 --> 00:57:00,200 Ik beloof het. 1033 00:57:00,200 --> 00:57:05,240 Maar datastructuren zijn iets dat het kost veel tijd om te wennen aan. 1034 00:57:05,240 --> 00:57:10,010 Waarschijnlijk een van de moeilijkste dingen, denk ik, in de loop. 1035 00:57:10,010 --> 00:57:15,330 >> Dus het duurt zeker herhaling en op zoek at-- I 1036 00:57:15,330 --> 00:57:20,050 niet echt weten gelinkte lijsten totdat ik deed veel te veel met hen, 1037 00:57:20,050 --> 00:57:22,550 op dezelfde manier dat ik niet echt begrijpen pointers 1038 00:57:22,550 --> 00:57:27,040 totdat ik heb gehad om het te leren voor twee jaar en doe mijn eigen psets mee. 1039 00:57:27,040 --> 00:57:28,990 Het kost veel herhaling en tijd. 1040 00:57:28,990 --> 00:57:32,600 En uiteindelijk zal dit soort klik. 1041 00:57:32,600 --> 00:57:36,320 >> Maar in de tussentijd, als je soort hebt een hoog begrip van wat 1042 00:57:36,320 --> 00:57:39,321 deze doen, hun voor- en cons-- dat is wat 1043 00:57:39,321 --> 00:57:41,820 we echt de neiging om te benadrukken, vooral in de intro cursus. 1044 00:57:41,820 --> 00:57:45,511 Zoals, waarom zouden we gebruiken een keer te proberen over een array? 1045 00:57:45,511 --> 00:57:48,010 Zoals, wat zijn de positieve en negatieven van elk van deze? 1046 00:57:48,010 --> 00:57:51,610 >> En het begrijpen van de trade-offs tussen deze structuren 1047 00:57:51,610 --> 00:57:54,910 is wat veel belangrijker op dit moment. 1048 00:57:54,910 --> 00:57:58,140 Er kan één gek zijn vraag of twee dat is 1049 00:57:58,140 --> 00:58:03,710 ga je vragen om te implementeren push of implementeren pop of enqueue en dequeue. 1050 00:58:03,710 --> 00:58:07,340 Maar voor het grootste gedeelte heeft dat hoger niveau begrip en meer 1051 00:58:07,340 --> 00:58:09,710 van een intuïtief begrip is belangrijker dan eigenlijk 1052 00:58:09,710 --> 00:58:11,250 in staat om het te implementeren. 1053 00:58:11,250 --> 00:58:14,880 >> Het zou echt geweldig zijn als jullie allemaal kon uit te gaan en te gaan implementeren een keer te proberen, 1054 00:58:14,880 --> 00:58:19,720 maar we begrijpen dat het niet per se de meest redelijke ding nu. 1055 00:58:19,720 --> 00:58:23,370 Maar je kunt in uw PSET, als je wilt aan, en dan zul je de praktijk te krijgen, 1056 00:58:23,370 --> 00:58:27,200 en dan misschien zult echt begrijpen. 1057 00:58:27,200 --> 00:58:27,940 Ja? 1058 00:58:27,940 --> 00:58:30,440 >> Publiek: OK, dus welke zijn we bedoeld voor gebruik in de PSET? 1059 00:58:30,440 --> 00:58:31,916 Heb ik nodig om een ​​van hen te gebruiken? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Ja. 1061 00:58:32,540 --> 00:58:34,199 Dus je hebt je keuze. 1062 00:58:34,199 --> 00:58:36,740 Ik denk dat in dit geval, we kunnen praten over de pset een beetje 1063 00:58:36,740 --> 00:58:40,480 want ik liep door deze. 1064 00:58:40,480 --> 00:58:47,779 Dus in uw PSET, je hebt je keuze van pogingen of hash tabellen. 1065 00:58:47,779 --> 00:58:49,570 Sommige mensen zullen proberen en gebruik bloei filters, 1066 00:58:49,570 --> 00:58:51,840 maar die technisch gezien niet correct zijn. 1067 00:58:51,840 --> 00:58:55,804 Vanwege hun probabilistische aard ze geven valse positieven soms. 1068 00:58:55,804 --> 00:58:57,095 Ze zijn koele blik in, dat wel. 1069 00:58:57,095 --> 00:58:59,030 Zeer aan te bevelen op zoek hen tenminste. 1070 00:58:59,030 --> 00:59:03,260 Maar je hebt je keuze tussen een hash table en een keer te proberen. 1071 00:59:03,260 --> 00:59:06,660 En dat gaat zijn waar die u in uw woordenboek. 1072 00:59:06,660 --> 00:59:09,230 >> En je zult moeten kiezen je hash-functie, 1073 00:59:09,230 --> 00:59:13,420 je nodig hebt om te kiezen hoeveel Emmers je hebt, en het zal variëren. 1074 00:59:13,420 --> 00:59:17,440 Net als je meer emmers, misschien zal het sneller lopen. 1075 00:59:17,440 --> 00:59:22,790 Maar misschien je verspilt een veel ruimte op die manier, dat wel. 1076 00:59:22,790 --> 00:59:26,320 Je moet het uitzoeken. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> Publiek: U zei eerder dat kunnen we andere hash-functies te gebruiken, 1079 00:59:29,875 --> 00:59:31,750 dat we niet hoeven te het creëren van een hash-functie? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Ja, rechts. 1081 00:59:32,666 --> 00:59:38,150 Dus letterlijk voor uw hash-functie, zoals google "hash-functie" 1082 00:59:38,150 --> 00:59:40,770 en kijken naar een aantal toffe gasten. 1083 00:59:40,770 --> 00:59:43,250 U bent niet verwacht op te bouwen je eigen hash-functies. 1084 00:59:43,250 --> 00:59:46,100 Mensen besteden hun stellingen over deze dingen. 1085 00:59:46,100 --> 00:59:50,250 >> Dus maak je geen zorgen over het bouwen van je eigen. 1086 00:59:50,250 --> 00:59:53,350 Vind een online om mee te beginnen. 1087 00:59:53,350 --> 00:59:56,120 Sommigen van hen moet je manipuleren een beetje 1088 00:59:56,120 --> 00:59:59,430 om er zeker van terugkeer types overeenkomen en wat al niet, dus in het begin, 1089 00:59:59,430 --> 01:00:02,420 Ik raad je aan om iets echt makkelijk dat misschien gewoon 1090 01:00:02,420 --> 01:00:04,680 hashes op de eerste letter. 1091 01:00:04,680 --> 01:00:08,760 En dan als je eenmaal hebt dat werken, het opnemen van een koeler hash-functie. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> Publiek: Zou een keer te proberen te zijn of efficiënt, maar gewoon moeilijker om, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Dus een keer te proberen, denk ik, is intuïtief moeilijk te implementeren 1095 01:00:15,880 --> 01:00:18,310 maar is erg snel. 1096 01:00:18,310 --> 01:00:20,620 Echter, meer plaats inneemt. 1097 01:00:20,620 --> 01:00:25,270 Ook hier kunt u deze beide te optimaliseren in verschillende manieren en er zijn manieren to-- 1098 01:00:25,270 --> 01:00:26,770 Publiek: Hoe worden we beoordeeld op dit? 1099 01:00:26,770 --> 01:00:27,540 Heeft het matter-- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Dus je bent ingedeeld normale manier. 1101 01:00:29,164 --> 01:00:31,330 Je gaat om te worden beoordeeld op design. 1102 01:00:31,330 --> 01:00:36,020 Welke manier je ook doet, je wilt zorg ervoor dat het zo elegant als het kan worden 1103 01:00:36,020 --> 01:00:38,610 en zo efficiënt kan zijn. 1104 01:00:38,610 --> 01:00:41,950 Maar als je een keer te proberen of hash kiezen tafel, zolang het werkt, 1105 01:00:41,950 --> 01:00:45,350 zijn we blij mee. 1106 01:00:45,350 --> 01:00:48,370 En als je iets gebruiken dat hashes op de eerste letter, dat is prima, 1107 01:00:48,370 --> 01:00:51,410 zoals misschien als ontwerp-wijs. 1108 01:00:51,410 --> 01:00:53,410 We zijn ook het bereiken van de punt in deze semester-- 1109 01:00:53,410 --> 01:00:55,340 Ik weet niet of je jongens noticed-- als je 1110 01:00:55,340 --> 01:00:58,780 pset kwaliteiten dalen een beetje vanwege het ontwerp en wat al niet, 1111 01:00:58,780 --> 01:00:59,900 dat is prima. 1112 01:00:59,900 --> 01:01:02,960 Het wordt naar een punt waar je 's worden steeds ingewikkelder. 1113 01:01:02,960 --> 01:01:04,830 Er zijn meer plaatsen je kunt verbeteren op. 1114 01:01:04,830 --> 01:01:06,370 >> Dus het is volkomen normaal. 1115 01:01:06,370 --> 01:01:08,810 Het is niet dat je bent slechter doet op uw pset. 1116 01:01:08,810 --> 01:01:11,885 Het is gewoon dat we harder wezen op je nu. 1117 01:01:11,885 --> 01:01:13,732 Dus iedereen voelt het. 1118 01:01:13,732 --> 01:01:14,940 Ik graded al uw psets. 1119 01:01:14,940 --> 01:01:16,490 Ik weet dat iedereen voelt het. 1120 01:01:16,490 --> 01:01:19,600 >> Wees dus niet ongerust over. 1121 01:01:19,600 --> 01:01:23,580 En als je vragen hebt over voorafgaand psets of manieren waarop u kunt verbeteren, 1122 01:01:23,580 --> 01:01:27,760 Ik probeer en commentaar van de specifieke plaatsen, maar soms is het te laat 1123 01:01:27,760 --> 01:01:30,840 en ik moe. 1124 01:01:30,840 --> 01:01:34,885 Zijn er nog andere dingen over data structuren? 1125 01:01:34,885 --> 01:01:37,510 Ik weet zeker dat jullie echt niet doen wil over hen meer over praten, 1126 01:01:37,510 --> 01:01:42,650 maar als er zijn, ik ben blij om gaat over hen, evenals om het even wat 1127 01:01:42,650 --> 01:01:45,580 vanaf lezing afgelopen week of vorige week. 1128 01:01:45,580 --> 01:01:51,580 >> Ik weet van vorige week was alle review, dus we kunnen over sommige beoordeling hebben overgeslagen 1129 01:01:51,580 --> 01:01:54,190 van lezing. 1130 01:01:54,190 --> 01:01:58,230 Eventuele andere vragen die ik kan beantwoorden? 1131 01:01:58,230 --> 01:01:59,350 OK, goed. 1132 01:01:59,350 --> 01:02:02,400 Nou, jullie krijgen 15 minuten te vroeg. 1133 01:02:02,400 --> 01:02:08,370 >> Ik hoop dat dit was semi-behulpzaam tenminste, en ik zie je jongens volgende week, 1134 01:02:08,370 --> 01:02:12,150 of donderdag kantooruren. 1135 01:02:12,150 --> 01:02:15,285 Zijn er verzoeken voor snacks voor volgende week, het is het ding? 1136 01:02:15,285 --> 01:02:17,459 Omdat ik vergat snoep vandaag. 1137 01:02:17,459 --> 01:02:19,750 En ik bracht snoep laatste week, maar het was de Dag van Columbus, 1138 01:02:19,750 --> 01:02:25,400 dus er waren als zes mensen die had vier zakken snoep aan zichzelf. 1139 01:02:25,400 --> 01:02:28,820 Ik kan brengen Starbursts nogmaals als je wilt. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 OK, klinkt goed. 1142 01:02:32,250 --> 01:02:35,050 Heb een grote dag, jongens. 1143 01:02:35,050 --> 01:02:39,510