1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> LUIDSPREKER 1: Oke, dus we zijn terug. 3 00:00:13,120 --> 00:00:14,480 Welkom op CS50. 4 00:00:14,480 --> 00:00:16,510 Dit is het einde van week zeven. 5 00:00:16,510 --> 00:00:20,200 Zo herinneren dat vorige keer, we begonnen bekeken iets meer verfijnde 6 00:00:20,200 --> 00:00:21,100 datastructuren. 7 00:00:21,100 --> 00:00:25,110 Omdat tot nu toe, al hadden we echt tot onze beschikking was dit, een array. 8 00:00:25,110 --> 00:00:29,340 >> Maar voordat we gooi de array als niet zo interessant, dat het inderdaad 9 00:00:29,340 --> 00:00:33,570 eigenlijk, wat zijn sommige van de pluspunten van deze eenvoudige gegevens 10 00:00:33,570 --> 00:00:34,560 structuur tot nu toe? 11 00:00:34,560 --> 00:00:36,110 Wat is er goed aan? 12 00:00:36,110 --> 00:00:39,450 Voor zover wij hebben gezien? 13 00:00:39,450 --> 00:00:42,540 Wat heb je? 14 00:00:42,540 --> 00:00:44,028 Niets. 15 00:00:44,028 --> 00:00:45,020 >> STUDENT: [onverstaanbaar]. 16 00:00:45,020 --> 00:00:45,395 >> LUIDSPREKER 1: Wat is dat? 17 00:00:45,395 --> 00:00:46,410 >> STUDENT: [onverstaanbaar]. 18 00:00:46,410 --> 00:00:47,000 >> LUIDSPREKER 1: Vaste grootte. 19 00:00:47,000 --> 00:00:51,260 OK, dus waarom is vaste grootte wel goed? 20 00:00:51,260 --> 00:00:53,180 >> STUDENT: [onverstaanbaar]. 21 00:00:53,180 --> 00:00:56,240 >> LUIDSPREKER 1: OK, dus het is efficiënt in de zin dat je kunt toewijzen van een 22 00:00:56,240 --> 00:01:00,070 vaste hoeveelheid ruimte, die hopelijk juist zoveel 23 00:01:00,070 --> 00:01:01,180 ruimte als je wilt. 24 00:01:01,180 --> 00:01:02,720 Zodat absoluut een plus kan. 25 00:01:02,720 --> 00:01:06,530 >> Wat is een ander up kant van een array? 26 00:01:06,530 --> 00:01:07,610 Yeah? 27 00:01:07,610 --> 00:01:08,750 >> STUDENT: [onverstaanbaar]. 28 00:01:08,750 --> 00:01:09,550 >> LUIDSPREKER 1: Alle - sorry? 29 00:01:09,550 --> 00:01:11,270 >> STUDENT: [onverstaanbaar]. 30 00:01:11,270 --> 00:01:13,620 >> LUIDSPREKER 1: Alle vakken in het geheugen of naast elkaar. 31 00:01:13,620 --> 00:01:15,220 En dat is nuttig - waarom? 32 00:01:15,220 --> 00:01:15,970 Dat is helemaal waar. 33 00:01:15,970 --> 00:01:18,611 Maar hoe kunnen we die waarheid te benutten? 34 00:01:18,611 --> 00:01:21,500 >> STUDENT: [onverstaanbaar]. 35 00:01:21,500 --> 00:01:24,490 >> LUIDSPREKER 1: Precies, we kunnen bijhouden waar alles is gewoon door te weten 36 00:01:24,490 --> 00:01:28,560 een adres, namelijk het adres van de eerste byte van dat stuk van het geheugen. 37 00:01:28,560 --> 00:01:30,420 Of in het geval van de tekenreeks het adres van de eerste 38 00:01:30,420 --> 00:01:31,460 char in die string. 39 00:01:31,460 --> 00:01:33,330 En van daar, vinden we het einde van de string. 40 00:01:33,330 --> 00:01:35,710 We kunnen het tweede element, het vinden derde element, enzovoort. 41 00:01:35,710 --> 00:01:38,740 >> En zo de mooie manier van het beschrijven van die kenmerk is dat arrays geven ons 42 00:01:38,740 --> 00:01:40,020 random access. 43 00:01:40,020 --> 00:01:44,330 Gewoon door het gebruik van de vierkante haak notatie en een nummer, kunt u naar 44 00:01:44,330 --> 00:01:48,070 een specifiek element in de array in constante tijd, big O 45 00:01:48,070 --> 00:01:49,810 van een, zo te zeggen. 46 00:01:49,810 --> 00:01:51,080 >> Maar er is al een aantal nadelen. 47 00:01:51,080 --> 00:01:53,110 Wat een array niet heel gemakkelijk te doen? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Wat is er niet goed in? 50 00:01:57,170 --> 00:01:58,810 >> STUDENT: [onverstaanbaar]. 51 00:01:58,810 --> 00:01:59,860 >> LUIDSPREKER 1: Wat is dat? 52 00:01:59,860 --> 00:02:00,530 >> STUDENT: [onverstaanbaar]. 53 00:02:00,530 --> 00:02:01,460 >> LUIDSPREKER 1: Uitbreiding in omvang. 54 00:02:01,460 --> 00:02:04,800 Dus de nadelen van de array precies het tegenovergestelde van wat de 55 00:02:04,800 --> 00:02:05,540 Pluspunten zijn. 56 00:02:05,540 --> 00:02:07,610 Dus een van de minpunten is dat het een vaste grootte. 57 00:02:07,610 --> 00:02:09,400 Dus je kunt niet echt groeien. 58 00:02:09,400 --> 00:02:13,510 U kunt een groter stuk van herverdelen geheugen, en verplaats de oude elementen 59 00:02:13,510 --> 00:02:14,460 in de nieuwe matrix. 60 00:02:14,460 --> 00:02:18,060 En dan gratis de oude array, voor Bijvoorbeeld door malloc of soortgelijk 61 00:02:18,060 --> 00:02:21,180 functie genaamd realloc, die bijstuurt in het geheugen. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, als een terzijde, probeert u geheugen dat is naast de array 63 00:02:25,490 --> 00:02:26,610 die je al hebt. 64 00:02:26,610 --> 00:02:28,740 Maar het kan dingen verplaatsen rond geheel. 65 00:02:28,740 --> 00:02:30,710 Maar in het kort, dat is duur, toch? 66 00:02:30,710 --> 00:02:33,440 Want als je een stuk van het geheugen van deze grootte, maar je echt wilt een 67 00:02:33,440 --> 00:02:36,710 van deze omvang, en u wilt behouden de oorspronkelijke elementen, je hebt 68 00:02:36,710 --> 00:02:40,510 ruwweg een lineaire tijd kopieerproces die moet gebeuren vanaf 69 00:02:40,510 --> 00:02:41,900 oude scala aan nieuwe. 70 00:02:41,900 --> 00:02:44,630 En de realiteit vraagt ​​het besturingssysteem systeem weer en 71 00:02:44,630 --> 00:02:48,340 opnieuw voor grote delen van het geheugen kan beginnen kost je wat tijd ook. 72 00:02:48,340 --> 00:02:52,250 Dus het is zowel een zegen als een vloek in verhullen dat deze arrays 73 00:02:52,250 --> 00:02:53,860 zijn van vaste grootte. 74 00:02:53,860 --> 00:02:56,790 Maar als we introduceren in plaats daarvan iets als dit, waar we wel een gekoppelde 75 00:02:56,790 --> 00:03:00,580 lijst, krijgen we een paar positieve kanten en een paar nadelen hier ook. 76 00:03:00,580 --> 00:03:05,780 >> Dus een gelinkte lijst is gewoon een data constructie bestaande uit C structs in deze 77 00:03:05,780 --> 00:03:09,850 geval, waarbij een structuur, recall, is gewoon een houder voor een of meer specifieke 78 00:03:09,850 --> 00:03:11,100 typen variabelen. 79 00:03:11,100 --> 00:03:16,110 In dit geval, wat doen de data types lijken binnenkant van de structuur dat 80 00:03:16,110 --> 00:03:17,600 laatste keer dat we wel een knoop? 81 00:03:17,600 --> 00:03:19,380 Elk van deze rechthoeken is een knooppunt. 82 00:03:19,380 --> 00:03:22,660 En elk van de kleinere rechthoeken erin een gegevenstype. 83 00:03:22,660 --> 00:03:25,300 Welke soorten hebben wij zeggen ze waren op maandag? 84 00:03:25,300 --> 00:03:26,478 Yeah? 85 00:03:26,478 --> 00:03:27,870 >> STUDENT: [onverstaanbaar]. 86 00:03:27,870 --> 00:03:30,721 >> LUIDSPREKER 1: Een variabele en een pointer, of namelijk om int voor n, 87 00:03:30,721 --> 00:03:32,180 en een pointer op de bodem. 88 00:03:32,180 --> 00:03:35,360 Deze beide toevallig 32 bits, bij minst op een computer als deze CS50 89 00:03:35,360 --> 00:03:37,980 Apparaat, en dus zijn ze even groot getekend. 90 00:03:37,980 --> 00:03:42,260 >> Dus waar met behulp van de aanwijzer hoewel voor blijkbaar? 91 00:03:42,260 --> 00:03:47,690 Waarom voeg deze pijl nu wanneer arrays waren zo mooi en schoon en eenvoudig? 92 00:03:47,690 --> 00:03:50,460 Wat is de wijzer doet voor ons in elk van deze knooppunten? 93 00:03:50,460 --> 00:03:52,160 >> STUDENT: [onverstaanbaar]. 94 00:03:52,160 --> 00:03:52,465 >> LUIDSPREKER 1: Precies. 95 00:03:52,465 --> 00:03:54,120 Het vertelt je waar de volgende is. 96 00:03:54,120 --> 00:03:57,350 Dus ik soort van gebruik van de analogie van met behulp van een draad om een ​​soort van 97 00:03:57,350 --> 00:03:59,180 rijg deze knooppunten samen. 98 00:03:59,180 --> 00:04:01,760 En dat is precies wat we doen met pointers omdat elk van deze 99 00:04:01,760 --> 00:04:06,360 delen van het geheugen al dan niet aaneengesloten, rug aan rug aan rug 100 00:04:06,360 --> 00:04:09,500 binnenkant van RAM, want elke keer dat u bellen malloc zeggen, geef mij genoeg 101 00:04:09,500 --> 00:04:12,510 bytes voor een nieuw knooppunt, het misschien hier zijn of het zou hier te zijn. 102 00:04:12,510 --> 00:04:13,120 Het zou hier te zijn. 103 00:04:13,120 --> 00:04:13,730 Het zou hier te zijn. 104 00:04:13,730 --> 00:04:14,640 Je weet het gewoon niet. 105 00:04:14,640 --> 00:04:17,880 >> Maar het gebruik van pointers in de adressen van die knopen, kunt u steek ze 106 00:04:17,880 --> 00:04:22,370 samen op een manier die lijkt visueel als een lijst, zelfs als deze dingen zijn 107 00:04:22,370 --> 00:04:26,770 allemaal verspreid door je een of je twee of uw vier gigabyte aan RAM-geheugen 108 00:04:26,770 --> 00:04:28,760 binnenkant van uw eigen computer. 109 00:04:28,760 --> 00:04:33,230 >> Dus het nadeel, dan, een gekoppelde lijst is wat? 110 00:04:33,230 --> 00:04:34,670 Wat is een prijs die we blijkbaar betalen? 111 00:04:34,670 --> 00:04:36,010 >> STUDENT: [onverstaanbaar]. 112 00:04:36,010 --> 00:04:36,920 >> LUIDSPREKER 1: Meer ruimte, toch? 113 00:04:36,920 --> 00:04:39,340 We hebben, in dit geval, een verdubbeling van het bedrag dat van de ruimte omdat we weg 114 00:04:39,340 --> 00:04:43,500 van 32 bits voor elk knooppunt voor elk int, dus nu 64 bits omdat we moeten 115 00:04:43,500 --> 00:04:45,050 houden rond een pointer ook. 116 00:04:45,050 --> 00:04:48,860 Je krijgt meer efficiency als uw struct is groter dan deze eenvoudige zaak. 117 00:04:48,860 --> 00:04:52,020 Als je eigenlijk een student binnen waarvan een paar strings voor 118 00:04:52,020 --> 00:04:55,430 naam en het huis, misschien een ID-nummer, misschien nog enkele andere gebieden helemaal. 119 00:04:55,430 --> 00:04:59,000 >> Dus als je een groot genoeg structuur, dan misschien de kosten van de aanwijzer 120 00:04:59,000 --> 00:05:00,010 niet zo'n big deal. 121 00:05:00,010 --> 00:05:03,570 Dit is een beetje een hoek geval in dat we zijn het opslaan van een dergelijke eenvoudige primitieve 122 00:05:03,570 --> 00:05:04,760 binnenzijde van de gekoppelde lijst. 123 00:05:04,760 --> 00:05:05,790 Maar hetzelfde is. 124 00:05:05,790 --> 00:05:08,230 Je bent zeker meer uitgeven geheugen, maar je krijgt 125 00:05:08,230 --> 00:05:08,990 flexibiliteit. 126 00:05:08,990 --> 00:05:12,280 Want nu als ik wil een element toe te voegen aan het begin van deze lijst, 127 00:05:12,280 --> 00:05:14,340 Ik moet een nieuw knooppunt toe te wijzen. 128 00:05:14,340 --> 00:05:17,180 En ik moet gewoon werken die pijlen of andere manier door gewoon bewegen 129 00:05:17,180 --> 00:05:17,980 sommige wijzers rond. 130 00:05:17,980 --> 00:05:20,580 >> Als ik iets wil invoegen in de midden van de lijst, heb ik niet te 131 00:05:20,580 --> 00:05:24,410 duwen iedereen opzij zoals we deden in weken 'verleden met onze vrijwilligers die 132 00:05:24,410 --> 00:05:25,700 vertegenwoordigde een array. 133 00:05:25,700 --> 00:05:29,470 Ik kan gewoon toewijzen van een nieuw knooppunt en wijs gewoon de pijlen in 134 00:05:29,470 --> 00:05:32,290 verschillende richtingen omdat het niet hebben feitelijke blijven 135 00:05:32,290 --> 00:05:35,670 geheugen een echte lijn zoals ik heb getekend het hier op het scherm. 136 00:05:35,670 --> 00:05:38,400 >> En dan tot slot, als je wilt invoegen iets aan het einde van de lijst is 137 00:05:38,400 --> 00:05:39,210 nog eenvoudiger. 138 00:05:39,210 --> 00:05:43,320 Dit is een soort van willekeurige notatie, maar 34 van de pointer, neem een ​​gok. 139 00:05:43,320 --> 00:05:46,710 Wat is de waarde van de pointer meest waarschijnlijk getekend beetje als een oude 140 00:05:46,710 --> 00:05:47,700 school-antenne daar? 141 00:05:47,700 --> 00:05:48,920 >> STUDENT: [onverstaanbaar]. 142 00:05:48,920 --> 00:05:49,900 >> LUIDSPREKER 1: Het is waarschijnlijk nul. 143 00:05:49,900 --> 00:05:52,710 En inderdaad, dat is een auteur weergave van null. 144 00:05:52,710 --> 00:05:56,310 En het is null omdat je absoluut moeten weten wanneer het einde van een gekoppelde 145 00:05:56,310 --> 00:06:00,050 lijst is, opdat je volgende te houden en volgen en het volgen van deze pijlen 146 00:06:00,050 --> 00:06:01,170 om wat vuilnis waarde. 147 00:06:01,170 --> 00:06:06,230 Dus null zal betekenen dat er geen meer knooppunten rechts van het getal 34, 148 00:06:06,230 --> 00:06:07,200 in dit geval. 149 00:06:07,200 --> 00:06:10,270 >> Dus stellen wij voor dat we kunnen implementeren dit knooppunt in de code. 150 00:06:10,270 --> 00:06:12,130 En we hebben dit soort gezien van syntax voor. 151 00:06:12,130 --> 00:06:15,090 Typedef gewoon definieert een nieuw type voor ons, geeft ons een synoniem als 152 00:06:15,090 --> 00:06:17,100 koord was voor char *. 153 00:06:17,100 --> 00:06:21,030 In dit geval gaat het om ons te geven verkorte schrijfwijze zodat struct knooppunt 154 00:06:21,030 --> 00:06:24,010 kan in plaats daarvan alleen geschreven worden als knooppunt, dat is veel schoner. 155 00:06:24,010 --> 00:06:25,360 Het is een stuk minder verbose. 156 00:06:25,360 --> 00:06:30,080 >> Binnenkant van een knooppunt is blijkbaar een int riep n, en dan is een struct knoop * 157 00:06:30,080 --> 00:06:34,670 wat betekent dat precies wat we wilden de pijlen te betekenen, een pointer naar een andere 158 00:06:34,670 --> 00:06:36,940 knoop van exact hetzelfde gegevenstype. 159 00:06:36,940 --> 00:06:40,300 En ik stel voor dat we konden implementeren van een zoekfunctie zoals deze, die op 160 00:06:40,300 --> 00:06:41,890 het eerste gezicht lijkt een beetje complex. 161 00:06:41,890 --> 00:06:43,330 Maar laten we het zien in de context. 162 00:06:43,330 --> 00:06:45,480 >> Laat me over te gaan naar het toestel hier. 163 00:06:45,480 --> 00:06:48,460 Laat ik het openen van een bestand met de naam lijst nul dot h. 164 00:06:48,460 --> 00:06:53,950 En dat alleen bevat de definitie wij zag net een moment geleden voor deze data 165 00:06:53,950 --> 00:06:55,390 soort heet een knooppunt. 166 00:06:55,390 --> 00:06:57,350 Dus hebben we dat in een punt h bestand gezet. 167 00:06:57,350 --> 00:07:01,430 >> En als een terzijde, hoewel dit programma dat u gaat zien is 168 00:07:01,430 --> 00:07:05,410 niet zo ingewikkeld, het is inderdaad conventie bij het schrijven van een programma om 169 00:07:05,410 --> 00:07:10,270 zet dingen zoals data types, te trekken constanten soms, binnenkant van uw 170 00:07:10,270 --> 00:07:13,210 header-bestand en niet noodzakelijk in Uw C-bestand, zeker als je 171 00:07:13,210 --> 00:07:17,370 programma's te krijgen groter en groter, zodat je weet waar te kijken voor zowel 172 00:07:17,370 --> 00:07:20,840 documentatie in sommige gevallen, of voor de basics zoals deze, de 173 00:07:20,840 --> 00:07:22,360 definitie van een soort. 174 00:07:22,360 --> 00:07:25,680 >> Als ik het nu open lijst nul dot c, merken een paar dingen. 175 00:07:25,680 --> 00:07:29,090 Het omvat een paar header files, de meeste waarvan wij eerder hebben gezien. 176 00:07:29,090 --> 00:07:31,980 Het omvat een eigen header file. 177 00:07:31,980 --> 00:07:35,200 >> En als een terzijde, waarom dat is dubbel citaten hier, in tegenstelling tot de hoek 178 00:07:35,200 --> 00:07:38,340 beugels op de lijn die Ik heb daar gemarkeerd? 179 00:07:38,340 --> 00:07:39,180 >> STUDENT: [onverstaanbaar]. 180 00:07:39,180 --> 00:07:40,460 >> LUIDSPREKER 1: Ja, dus het is een lokaal bestand. 181 00:07:40,460 --> 00:07:44,300 Dus als het een lokaal bestand van je eigen hier op lijn 15, bijvoorbeeld, gebruikt u 182 00:07:44,300 --> 00:07:46,570 de dubbele aanhalingstekens in plaats van de haakjes. 183 00:07:46,570 --> 00:07:48,270 >> Nu is dit soort van interessant. 184 00:07:48,270 --> 00:07:51,830 Merk op dat ik een globale heb verklaard variabele in dit programma op lijn 18 185 00:07:51,830 --> 00:07:55,910 eerste genoemd, waarbij het idee is dit naar een pointer naar de eerst 186 00:07:55,910 --> 00:07:59,190 knoop in mijn gelinkte lijst, en ik heb geïnitialiseerd op null, want ik heb 187 00:07:59,190 --> 00:08:02,310 geen werkelijke toegewezen nodes nog net. 188 00:08:02,310 --> 00:08:07,570 >> Dus dit betekent, pictorially, wat we zag daarnet in de foto als 189 00:08:07,570 --> 00:08:10,090 dat aanwijzer op de ver linkerhand. 190 00:08:10,090 --> 00:08:12,260 Dus nu, dat de wijzer heeft geen pijl. 191 00:08:12,260 --> 00:08:14,590 Het is in plaats daarvan gewoon nul. 192 00:08:14,590 --> 00:08:17,880 Maar het vertegenwoordigt wat zijn de adres van de eerste werkelijke 193 00:08:17,880 --> 00:08:19,480 knooppunt in deze lijst. 194 00:08:19,480 --> 00:08:22,120 Dus ik heb uitgevoerd is het een mondiaal omdat, zoals u zult zien, dit alles 195 00:08:22,120 --> 00:08:25,310 programma niet in het leven is te implementeren een gekoppelde lijst voor mij. 196 00:08:25,310 --> 00:08:27,050 >> Nu heb ik een paar prototypes hier. 197 00:08:27,050 --> 00:08:31,190 Ik besloot om functies zoals implementeren deletie, insertie, zoeken, en 198 00:08:31,190 --> 00:08:31,740 traversal - 199 00:08:31,740 --> 00:08:35,210 de laatste alleen maar lopen over de lijst, het afdrukken van haar elementen. 200 00:08:35,210 --> 00:08:36,750 En nu hier is mijn main routine. 201 00:08:36,750 --> 00:08:39,890 En wij zullen niet te veel tijd besteden aan deze aangezien dit soort van, hopelijk 202 00:08:39,890 --> 00:08:41,780 oude hoed van nu. 203 00:08:41,780 --> 00:08:45,370 >> Ik ga het volgende doen, terwijl de gebruiker werkt. 204 00:08:45,370 --> 00:08:47,300 Zo een, ik ga om te printen uit dit menu. 205 00:08:47,300 --> 00:08:49,420 En ik heb het zo geformatteerd netjes als ik kon. 206 00:08:49,420 --> 00:08:52,240 Als types de gebruiker in een, dat betekent ze iets willen verwijderen. 207 00:08:52,240 --> 00:08:54,560 Als types de gebruiker in twee, dat betekent ze iets willen invoegen. 208 00:08:54,560 --> 00:08:55,930 Enzovoort. 209 00:08:55,930 --> 00:08:58,270 Ik ga dan prompt dan voor een opdracht. 210 00:08:58,270 --> 00:08:59,300 En dan ga ik getInt gebruiken. 211 00:08:59,300 --> 00:09:02,790 >> Dus dit is een heel eenvoudige menuing interface waar je alleen maar te typen 212 00:09:02,790 --> 00:09:05,270 een aantal mapping een van deze opdrachten. 213 00:09:05,270 --> 00:09:08,730 En nu heb ik een mooie schone schakelaar verklaring dat gaat schakelen 214 00:09:08,730 --> 00:09:10,090 wat de gebruiker intikt: 215 00:09:10,090 --> 00:09:12,180 En als ze getypt een, ik zal roepen verwijderen en breken. 216 00:09:12,180 --> 00:09:14,380 Als ze twee getypt, ik zal bel invoegen en breken. 217 00:09:14,380 --> 00:09:16,490 >> En nu merkt dat ik heb elke gezet deze op dezelfde lijn. 218 00:09:16,490 --> 00:09:18,360 Dit is slechts een stilistische beslissing. 219 00:09:18,360 --> 00:09:20,210 Typisch dat we iets gezien als dit. 220 00:09:20,210 --> 00:09:23,260 Maar ik heb net besloten, eerlijk gezegd, mijn programma leek meer leesbaar omdat 221 00:09:23,260 --> 00:09:25,980 het was slechts vier gevallen gewoon een lijst is als volgt. 222 00:09:25,980 --> 00:09:28,360 Helemaal legitiem gebruik van stijl. 223 00:09:28,360 --> 00:09:31,480 En ik ga doen dit zolang de gebruiker heeft geen nul getypt, die ik 224 00:09:31,480 --> 00:09:33,910 besloten zal betekenen dat ze willen stoppen. 225 00:09:33,910 --> 00:09:36,630 >> Dus let nu op wat ik ben hier gaan doen. 226 00:09:36,630 --> 00:09:38,650 Ik ga naar de lijst blijkbaar bevrijden. 227 00:09:38,650 --> 00:09:40,230 Maar meer op dat in slechts een moment. 228 00:09:40,230 --> 00:09:41,640 Laten we eerst dit programma uit te voeren. 229 00:09:41,640 --> 00:09:45,250 Dus laat me een grotere terminal venster, dot slash lijst 0. 230 00:09:45,250 --> 00:09:49,510 Ik ga om te gaan en invoegen typen twee, een aantal net 50, en nu 231 00:09:49,510 --> 00:09:51,590 zie je de lijst is nu 50. 232 00:09:51,590 --> 00:09:53,380 En mijn tekst gewoon gebladerd een beetje. 233 00:09:53,380 --> 00:09:55,940 Dus nu let op de lijst bevat het nummer 50. 234 00:09:55,940 --> 00:09:58,220 >> Laten we een andere insert door het nemen van twee. 235 00:09:58,220 --> 00:10:01,630 Laten we het nummer in als een. 236 00:10:01,630 --> 00:10:03,940 Lijst nu een, gevolgd door 50. 237 00:10:03,940 --> 00:10:06,020 Dus dit is gewoon een tekstuele representatie van de lijst. 238 00:10:06,020 --> 00:10:10,550 En laten we voegen nog een nummer als het nummer 42, die hopelijk is 239 00:10:10,550 --> 00:10:14,620 gaan om te eindigen in het midden, omdat dit programma in het bijzonder sorteert het 240 00:10:14,620 --> 00:10:16,320 elementen zoals plaatst ze. 241 00:10:16,320 --> 00:10:17,220 Dus daar hebben we het. 242 00:10:17,220 --> 00:10:20,730 Super eenvoudig programma dat kan absoluut gebruik hebben gemaakt van een array, maar ik 243 00:10:20,730 --> 00:10:23,280 toevallig worden met behulp van een gelinkte lijst gewoon zo kan ik dynamisch 244 00:10:23,280 --> 00:10:24,610 groeien en krimpen. 245 00:10:24,610 --> 00:10:28,470 >> Dus laten we eens een kijkje te zoeken, als ik run command drie, ik wil zoeken 246 00:10:28,470 --> 00:10:31,040 voor bijvoorbeeld het getal 43. 247 00:10:31,040 --> 00:10:34,190 En niets was blijkbaar gevonden, want ik kreeg geen antwoord. 248 00:10:34,190 --> 00:10:35,010 Dus laten we dit opnieuw doen. 249 00:10:35,010 --> 00:10:35,690 Zoeken. 250 00:10:35,690 --> 00:10:39,520 Laten we zoeken naar 50, of liever zoeken voor 42, wat een leuke heeft 251 00:10:39,520 --> 00:10:40,850 weinig subtiele betekenis. 252 00:10:40,850 --> 00:10:42,610 En ik vond de zin van het leven daar. 253 00:10:42,610 --> 00:10:44,990 Nummer 42, als je niet weet de verwijzing, Google het. 254 00:10:44,990 --> 00:10:45,350 Oke. 255 00:10:45,350 --> 00:10:47,130 Dus wat heeft dit programma voor mij gedaan? 256 00:10:47,130 --> 00:10:50,660 Het is gewoon me toegestaan ​​om daarmee te voegen ver en zoeken naar elementen. 257 00:10:50,660 --> 00:10:53,650 >> Laten we snel vooruit, dan, om die functie hebben we een blik geworpen op 258 00:10:53,650 --> 00:10:55,360 op maandag als een teaser. 259 00:10:55,360 --> 00:10:59,620 Dus deze functie, beweren ik, zoekt naar een element in de lijst door eerst 260 00:10:59,620 --> 00:11:03,830 men, dat de gebruiker en dan bellen GetInt tot een daadwerkelijke int krijgen 261 00:11:03,830 --> 00:11:05,060 dat u wilt zoeken. 262 00:11:05,060 --> 00:11:06,460 >> Merkt dan dit. 263 00:11:06,460 --> 00:11:10,690 Ik ga een tijdelijke variabele maken in lijn 188 genaamd wijzer - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 zou hebben genoemd niets. 266 00:11:12,440 --> 00:11:16,140 En het is een pointer naar een knooppunt omdat ik zei knooppunt * er. 267 00:11:16,140 --> 00:11:19,900 En ik ben te initialiseren om gelijk te zijn eerst zodat ik daadwerkelijk heb mijn 268 00:11:19,900 --> 00:11:22,860 vinger als het ware op het eerste element van de lijst. 269 00:11:22,860 --> 00:11:27,460 Dus als mijn rechterhand hier is PTR ik ben wijzend op het zelfde ding dat eerst 270 00:11:27,460 --> 00:11:28,670 wijst op. 271 00:11:28,670 --> 00:11:31,430 >> Dus nu terug in de code, wat gebeurt er - 272 00:11:31,430 --> 00:11:35,070 Dit is een veel voorkomende paradigma toen itereren meer dan een structuur als een 273 00:11:35,070 --> 00:11:35,970 gelinkte lijst. 274 00:11:35,970 --> 00:11:40,410 Ik ga het volgende doen terwijl pointer is niet gelijk aan So null terwijl 275 00:11:40,410 --> 00:11:47,530 mijn vinger is niet wijst op een null waarde, als aanwijzer n gelijk is aan n. 276 00:11:47,530 --> 00:11:52,290 Eerst zullen we merken dat n is wat de gebruiker ingetypt per GetInts noemen hier. 277 00:11:52,290 --> 00:11:54,280 >> En aanwijzer n betekent wat? 278 00:11:54,280 --> 00:11:59,020 Nou als we terug gaan naar de foto hier, als ik een vinger wijzen naar 279 00:11:59,020 --> 00:12:02,960 dat eerste knooppunt bevat negen, pijl betekent in wezen naar die 280 00:12:02,960 --> 00:12:08,860 knooppunt en pak de waarde op locatie n, in dit geval, het gegevensveld genoemd n. 281 00:12:08,860 --> 00:12:14,120 >> Als een terzijde - en we zagen dit een paar van weken geleden, toen iemand vroeg - 282 00:12:14,120 --> 00:12:18,840 Deze syntax is nieuw, maar het doet niet geef ons krachten die we 283 00:12:18,840 --> 00:12:20,040 nog niet had. 284 00:12:20,040 --> 00:12:25,325 Wat was deze zin gelijk aan het gebruik puntnotatie en ster een paar 285 00:12:25,325 --> 00:12:29,490 van weken geleden, toen we terug gepeld deze laag een beetje te vroeg? 286 00:12:29,490 --> 00:12:31,780 >> STUDENT: [onverstaanbaar]. 287 00:12:31,780 --> 00:12:38,880 >> LUIDSPREKER 1: Precies, het was ster, en toen was het ster dot n, met 288 00:12:38,880 --> 00:12:41,930 haakjes hier, die eruit ziet, eerlijk gezegd, ik denk dat veel 289 00:12:41,930 --> 00:12:43,320 meer cryptisch te lezen. 290 00:12:43,320 --> 00:12:46,270 Maar ster pointer, zoals altijd, middelen gaan daar. 291 00:12:46,270 --> 00:12:49,090 En als je eenmaal daar bent, welke gegevens veld wilt u toegang? 292 00:12:49,090 --> 00:12:52,730 Nou je het puntnotatie gebruiken om toegang te een structs data veld, en ik 293 00:12:52,730 --> 00:12:54,140 specifiek willen n. 294 00:12:54,140 --> 00:12:56,240 >> Eerlijk gezegd, ik zou dit pleiten is gewoon moeilijker te lezen. 295 00:12:56,240 --> 00:12:58,080 Het is moeilijker te onthouden waar niet de haakjes te gaan, het 296 00:12:58,080 --> 00:12:59,030 ster en dat allemaal. 297 00:12:59,030 --> 00:13:02,150 Dus de wereld is besloten een aantal syntactische suiker, zo te zeggen. 298 00:13:02,150 --> 00:13:04,740 Gewoon een sexy manier om te zeggen, dit is gelijk, en 299 00:13:04,740 --> 00:13:05,970 misschien meer intuïtief. 300 00:13:05,970 --> 00:13:09,600 Als wijzer is inderdaad een pointer, de pijl notatie middelen gaan daar en vinden 301 00:13:09,600 --> 00:13:11,890 het veld in dit geval heet n. 302 00:13:11,890 --> 00:13:13,660 >> Dus als ik vind het, let op wat ik doe. 303 00:13:13,660 --> 00:13:17,430 Ik heb gewoon uitprinten, ik vond procent i, het aansluiten van de waarde voor die int. 304 00:13:17,430 --> 00:13:20,730 Ik roep slapen voor een seconde gewoon naar soort van de pauze dingen op het scherm om 305 00:13:20,730 --> 00:13:22,900 geven de gebruiker een tweede te absorberen wat er net gebeurd. 306 00:13:22,900 --> 00:13:24,290 En dan breken ik. 307 00:13:24,290 --> 00:13:26,330 Anders, wat moet ik doen? 308 00:13:26,330 --> 00:13:30,960 Ik wijzer update naar gelijke aanwijzer pijl naast. 309 00:13:30,960 --> 00:13:35,840 >> Dus gewoon om duidelijk te zijn, betekent dit gaan er, met behulp van mijn oude school notatie. 310 00:13:35,840 --> 00:13:39,580 Dus dit betekent gewoon naar wat je bent goed op, dat in de zeer 311 00:13:39,580 --> 00:13:43,660 eerste geval is ben ik wijzend op de structuur met negen erin. 312 00:13:43,660 --> 00:13:44,510 Dus ik heb er gegaan. 313 00:13:44,510 --> 00:13:47,880 En dan is de dot-notatie betekent, krijgen de waarde bij de volgende. 314 00:13:47,880 --> 00:13:50,470 >> Maar de waarde, ook al is getekend als een smalle, is maar een getal. 315 00:13:50,470 --> 00:13:51,720 Het is een numeriek adres. 316 00:13:51,720 --> 00:13:55,670 Dus deze ene regel code, of geschreven als dit, de meer cryptische 317 00:13:55,670 --> 00:14:00,190 manier, of als dit, de iets meer intuïtieve manier, betekent gewoon bewegen mijn hand 318 00:14:00,190 --> 00:14:03,460 vanaf het eerste knooppunt naar het volgende, en dan de volgende, en vervolgens de 319 00:14:03,460 --> 00:14:05,320 volgende, enzovoort. 320 00:14:05,320 --> 00:14:09,920 >> Dus zullen we niet stilstaan ​​bij de andere implementaties van invoegen en verwijderen 321 00:14:09,920 --> 00:14:14,030 en traversal, de eerste twee van die vrij betrokken. 322 00:14:14,030 --> 00:14:17,010 En ik denk dat het heel makkelijk te krijgen verloren bij het doen van het mondeling. 323 00:14:17,010 --> 00:14:19,890 Maar wat we hier kunnen doen is proberen te bepalen hoe 324 00:14:19,890 --> 00:14:21,640 best dit visueel doen. 325 00:14:21,640 --> 00:14:24,800 Want ik stel voor dat als we willen elementen invoegen in dit 326 00:14:24,800 --> 00:14:26,680 bestaande lijst, die heeft vijf elementen - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26 en 33 - 328 00:14:29,530 --> 00:14:33,300 als ik zou gaan om dit te implementeren in code, ik moet nadenken over hoe om te gaan 329 00:14:33,300 --> 00:14:34,160 over dit te doen. 330 00:14:34,160 --> 00:14:37,720 >> En ik stel het nemen van kleine stapjes waarbij, in dit geval bedoel ik, wat zijn 331 00:14:37,720 --> 00:14:41,090 de mogelijke scenario's die we kunnen ondervinden in het algemeen? 332 00:14:41,090 --> 00:14:44,120 Bij de uitvoering van inzetstuk voor een gekoppelde lijst, dit gewoon toevallig een 333 00:14:44,120 --> 00:14:46,090 specifiek voorbeeld van grootte vijf. 334 00:14:46,090 --> 00:14:50,420 Nou als je een nummer wilt invoegen, willen zeggen dat de nummer een, en 335 00:14:50,420 --> 00:14:53,380 behoud gesorteerde volgorde, waarbij uiteraard wel de nummer een moeten 336 00:14:53,380 --> 00:14:55,686 gaan in dit specifieke voorbeeld? 337 00:14:55,686 --> 00:14:56,840 Net als in het begin. 338 00:14:56,840 --> 00:15:00,030 >> Maar wat interessant is dat als je er een wilt invoegen in dit 339 00:15:00,030 --> 00:15:04,100 lijst, welke speciale wijzer nodig heeft te blijkbaar worden bijgewerkt? 340 00:15:04,100 --> 00:15:04,610 Eerste. 341 00:15:04,610 --> 00:15:07,830 Dus ik zou zeggen, dit is het eerste geval dat wij zou willen overwegen, een 342 00:15:07,830 --> 00:15:11,140 scenario met het invoegen op het begin van de lijst. 343 00:15:11,140 --> 00:15:15,400 >> Laten we plukken uit misschien een zo makkelijk of zelfs eenvoudiger geval, relatief gezien. 344 00:15:15,400 --> 00:15:18,110 Stel dat ik wil het invoegen nummer 35 in gesorteerde volgorde. 345 00:15:18,110 --> 00:15:20,600 Het behoort uiteraard daar. 346 00:15:20,600 --> 00:15:25,320 Dus wat wijzer uiteraard gaat moeten worden bijgewerkt in dat scenario? 347 00:15:25,320 --> 00:15:30,060 34's pointer steeds niet null maar het adres van de struct 348 00:15:30,060 --> 00:15:31,800 met het nummer 35. 349 00:15:31,800 --> 00:15:32,750 Dus dat is het geval twee. 350 00:15:32,750 --> 00:15:36,190 Dus al, ik ben een soort quantizing hoeveel werk ik moet doen hier. 351 00:15:36,190 --> 00:15:39,880 >> En tenslotte de hand liggende middelste zaak inderdaad, in het midden, als ik wil 352 00:15:39,880 --> 00:15:45,870 Steek zoiets als zeggen 23, dat gaat tussen 23 en 26, maar 353 00:15:45,870 --> 00:15:48,680 nu dingen een beetje meer betrokken omdat wat 354 00:15:48,680 --> 00:15:52,800 pointers moeten worden veranderd? 355 00:15:52,800 --> 00:15:56,680 Zo 22 moet uiteraard worden veranderd omdat hij niet kan wijzen naar 26 meer. 356 00:15:56,680 --> 00:16:00,320 Hij moet naar het nieuwe knooppunt Ik moet wijzen door te bellen naar 357 00:16:00,320 --> 00:16:01,770 malloc of een equivalent. 358 00:16:01,770 --> 00:16:05,990 >> Maar dan moet ik ook aan dat nieuwe knooppunt, 23 in dit geval, om haar pointer hebben 359 00:16:05,990 --> 00:16:07,870 wijzend op wie? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 En er komt wel een volgorde van bewerkingen hier. 362 00:16:10,380 --> 00:16:13,410 Want als ik dit doe dwaas, en ik bijvoorbeeld beginnen bij het begin van 363 00:16:13,410 --> 00:16:16,040 de lijst en mijn doel is om in te voegen 23. 364 00:16:16,040 --> 00:16:18,610 En ik check, behoort het Hier, in de buurt van negen? 365 00:16:18,610 --> 00:16:18,950 Nee. 366 00:16:18,950 --> 00:16:20,670 Het maakt hier deel van uitmaken, naast de 17? 367 00:16:20,670 --> 00:16:20,940 Nee. 368 00:16:20,940 --> 00:16:22,530 Doet het hier hoort naast de 22? 369 00:16:22,530 --> 00:16:23,300 Ja. 370 00:16:23,300 --> 00:16:26,400 >> Nu, als ik hier ben dom, en niet denken dat dit door, ik zou 371 00:16:26,400 --> 00:16:28,320 toewijzen mijn nieuwe knooppunt voor 23. 372 00:16:28,320 --> 00:16:32,080 Ik zou de aanwijzer van werken het knooppunt genaamd 22, wijzend 373 00:16:32,080 --> 00:16:33,080 het op het nieuwe knooppunt. 374 00:16:33,080 --> 00:16:36,140 En wat heb ik te updaten wijzer van de nieuwe node te zijn? 375 00:16:36,140 --> 00:16:38,120 >> STUDENT: [onverstaanbaar]. 376 00:16:38,120 --> 00:16:38,385 >> LUIDSPREKER 1: Precies. 377 00:16:38,385 --> 00:16:39,710 Wijzend op 26. 378 00:16:39,710 --> 00:16:45,590 Maar dammit als ik niet al updaten 22's pointer punt op deze man, en 379 00:16:45,590 --> 00:16:48,260 nu heb ik weeskinderen, de rest van de lijst, om zo te zeggen. 380 00:16:48,260 --> 00:16:52,140 Dus volgorde van bewerkingen hier zal belangrijk. 381 00:16:52,140 --> 00:16:55,100 >> Om dit te doen zou ik stelen, zeggen zes vrijwilligers. 382 00:16:55,100 --> 00:16:57,650 En laten we kijken of we dit kunnen doen visueel in plaats van code-wise. 383 00:16:57,650 --> 00:16:59,330 En we hebben een aantal mooie spanning ballen voor u vandaag. 384 00:16:59,330 --> 00:17:02,510 OK, hoe over een, twee, in de weer - op het einde daar. 385 00:17:02,510 --> 00:17:04,530 drie, vier, jullie allebei jongens op het einde. 386 00:17:04,530 --> 00:17:05,579 En vijf, zes. 387 00:17:05,579 --> 00:17:05,839 Tuurlijk. 388 00:17:05,839 --> 00:17:06,450 Vijf en zes. 389 00:17:06,450 --> 00:17:08,390 Oke en we zullen komen om jullie de volgende keer. 390 00:17:08,390 --> 00:17:09,640 Oke, kom op maximaal. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Oke, omdat je hier eerst, zou je graag de ene onhandig 393 00:17:14,819 --> 00:17:16,119 in Google Glass hier? 394 00:17:16,119 --> 00:17:19,075 Oke, ja, OK, Glas, opnemen van een video. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 OK, je bent goed om te gaan. 397 00:17:24,589 --> 00:17:27,950 >> Oke, dus als jullie kunnen komen over Hier, heb ik van tevoren voorbereid 398 00:17:27,950 --> 00:17:30,110 sommige nummers. 399 00:17:30,110 --> 00:17:31,240 Oke, kom eens hier. 400 00:17:31,240 --> 00:17:33,440 En waarom heb je niet een beetje gaan verder op die manier. 401 00:17:33,440 --> 00:17:35,520 En laten we eens kijken, wat is uw naam, met de Google Glass? 402 00:17:35,520 --> 00:17:35,910 >> STUDENT: Ben. 403 00:17:35,910 --> 00:17:36,230 >> LUIDSPREKER 1: Ben? 404 00:17:36,230 --> 00:17:38,380 OK, Ben, je zult eerst zijn, letterlijk. 405 00:17:38,380 --> 00:17:40,580 Dus we gaan naar je sturen aan het einde van de etappe. 406 00:17:40,580 --> 00:17:41,670 Oke, en uw naam? 407 00:17:41,670 --> 00:17:41,990 >> STUDENT: Jason. 408 00:17:41,990 --> 00:17:44,530 >> LUIDSPREKER 1: Jason, OK zul je zijn nummer negen. 409 00:17:44,530 --> 00:17:46,700 Dus als je wilt Ben die weg te volgen. 410 00:17:46,700 --> 00:17:47,010 >> STUDENT: Jill. 411 00:17:47,010 --> 00:17:49,630 >> LUIDSPREKER 1: Jill, je gaat worden 17, dat als ik dit meer had gedaan 412 00:17:49,630 --> 00:17:51,260 intelligent, zou ik begon aan het andere uiteinde. 413 00:17:51,260 --> 00:17:52,370 Je gaat die kant op. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 En jij bent? 416 00:17:53,670 --> 00:17:53,980 >> STUDENT: Mary. 417 00:17:53,980 --> 00:17:56,130 >> LUIDSPREKER 1: Maria, zult u 22. 418 00:17:56,130 --> 00:17:58,420 En uw naam is? 419 00:17:58,420 --> 00:17:58,810 >> STUDENT: Chris. 420 00:17:58,810 --> 00:18:00,100 >> LUIDSPREKER 1: Chris, zult u 26. 421 00:18:00,100 --> 00:18:00,740 En dan tot slot. 422 00:18:00,740 --> 00:18:01,400 >> STUDENT: Diana. 423 00:18:01,400 --> 00:18:02,670 >> LUIDSPREKER 1: Diana, zult u 34. 424 00:18:02,670 --> 00:18:03,920 Dus kom je over meer dan hier. 425 00:18:03,920 --> 00:18:06,360 >> Oke, dus perfectioneren naargelang bestellen reeds. 426 00:18:06,360 --> 00:18:09,600 En laten we verder gaan en doen dit zodat we kunnen echt - 427 00:18:09,600 --> 00:18:11,720 Ben je gewoon een soort van kijken uit in niets daar. 428 00:18:11,720 --> 00:18:15,670 OK, dus laten we verder gaan en verbeelden dit met armen, net als ik was, precies, 429 00:18:15,670 --> 00:18:16,250 wat er gaande is. 430 00:18:16,250 --> 00:18:19,540 Dus ga je gang en geef jezelf een voet of twee tussen uzelf. 431 00:18:19,540 --> 00:18:22,900 En ga je gang en wijzen met een hand te wie je ook moeten wijzen op 432 00:18:22,900 --> 00:18:23,470 gebaseerd. 433 00:18:23,470 --> 00:18:25,890 En als je null bent gewoon wijzen recht naar beneden naar de vloer. 434 00:18:25,890 --> 00:18:27,690 OK, so good. 435 00:18:27,690 --> 00:18:32,290 >> Dus nu hebben we een gelinkte lijst, en laat mij stel dat ik de rol van spelen 436 00:18:32,290 --> 00:18:35,110 PTR, dus ik zal niet de moeite de voortzetting van deze rond. 437 00:18:35,110 --> 00:18:37,830 En dan - iemand dom conventie - U kunt dit alles wat je wilt noemen - 438 00:18:37,830 --> 00:18:39,800 voorganger wijzer, pred wijzer - 439 00:18:39,800 --> 00:18:43,930 het is gewoon de bijnaam we gaven onze voorbeeldcode aan mijn linkerhand. 440 00:18:43,930 --> 00:18:47,240 De andere kant dat gaat worden houden bijhouden van wie is wie in de 441 00:18:47,240 --> 00:18:48,400 volgende scenario. 442 00:18:48,400 --> 00:18:52,390 >> Dus stel, eerste, ik wil eraf rukken dat eerste voorbeeld van het plaatsen, zeg 443 00:18:52,390 --> 00:18:54,330 20, in de lijst. 444 00:18:54,330 --> 00:18:57,160 Dus ik ga iemand nodig hebben belichamen het nummer 20 voor ons. 445 00:18:57,160 --> 00:18:58,950 Dus ik moet malloc iemand uit het publiek. 446 00:18:58,950 --> 00:18:59,380 Kom maar naar boven. 447 00:18:59,380 --> 00:19:00,340 Wat is je naam? 448 00:19:00,340 --> 00:19:01,300 >> STUDENT: Brian. 449 00:19:01,300 --> 00:19:05,270 >> LUIDSPREKER 1: Brian, oke, dus je stelt het knooppunt met 20 zijn. 450 00:19:05,270 --> 00:19:06,810 Oke, kom eens hier. 451 00:19:06,810 --> 00:19:10,025 En natuurlijk voorkomend doet Brian behoort? 452 00:19:10,025 --> 00:19:12,190 Dus, in het midden - eigenlijk, wacht een minuut. 453 00:19:12,190 --> 00:19:13,420 We doen dit in de juiste volgorde. 454 00:19:13,420 --> 00:19:17,170 We maken dit een stuk moeilijker dan het moet zijn op het eerste. 455 00:19:17,170 --> 00:19:21,210 OK, we gaan vrij Brian en realloc Brian als vijf. 456 00:19:21,210 --> 00:19:23,680 >> OK, dus nu willen we voegen Brian als vijf. 457 00:19:23,680 --> 00:19:25,960 Dus kom eens hier naast Ben voor slechts een moment. 458 00:19:25,960 --> 00:19:28,250 En je kunt waarschijnlijk vertellen waar dit verhaal gaat. 459 00:19:28,250 --> 00:19:30,500 Maar laten we goed nadenken over de volgorde van de bewerkingen. 460 00:19:30,500 --> 00:19:32,880 En het is juist deze visuele dat gaat line-up 461 00:19:32,880 --> 00:19:34,080 met die voorbeeldcode. 462 00:19:34,080 --> 00:19:40,120 Dus hier heb ik PTR wijst in eerste instantie Ben niet, per se, maar op welk 463 00:19:40,120 --> 00:19:43,245 waarde hij bevat, die in dit geval is - hoe heet je ook alweer? 464 00:19:43,245 --> 00:19:43,670 >> STUDENT: Jason. 465 00:19:43,670 --> 00:19:47,350 >> LUIDSPREKER 1: Jason, dus zowel Ben en ik zijn wijzend op Jason op dit moment. 466 00:19:47,350 --> 00:19:49,700 Dus nu heb ik om te bepalen, waar komt Brian behoort? 467 00:19:49,700 --> 00:19:53,500 Dus het enige wat ik heb toegang tot nu is zijn n data-item. 468 00:19:53,500 --> 00:19:58,280 Dus ik ga om te controleren, is Brian minder dan Jason? 469 00:19:58,280 --> 00:19:59,770 Het antwoord is waar. 470 00:19:59,770 --> 00:20:03,680 >> Dus wat nu moet gebeuren, in de juiste volgorde? 471 00:20:03,680 --> 00:20:07,120 Ik moet bijwerken hoeveel pointers in totaal in dit verhaal? 472 00:20:07,120 --> 00:20:10,720 Waar mijn hand is nog steeds wijzend op Jason, en je hand - als je wilt 473 00:20:10,720 --> 00:20:12,930 leg je hand als, soort van, ik weet het niet, een vraagteken. 474 00:20:12,930 --> 00:20:14,070 OK, goed. 475 00:20:14,070 --> 00:20:15,670 >> Oke, dus je hebt een paar kandidaten. 476 00:20:15,670 --> 00:20:20,500 Ofwel Ben of I of Brian of Jason of iedereen, die 477 00:20:20,500 --> 00:20:21,370 pointers moeten veranderen? 478 00:20:21,370 --> 00:20:23,260 Hoeveel in totaal? 479 00:20:23,260 --> 00:20:24,080 >> OK, dus twee. 480 00:20:24,080 --> 00:20:27,090 Mijn wijzer maakt eigenlijk niet meer uit want ik ben gewoon tijdelijk. 481 00:20:27,090 --> 00:20:31,370 Dus het is deze twee jongens, vermoedelijk, zowel Ben en Brian. 482 00:20:31,370 --> 00:20:34,410 Dus laat ik stel voor dat we een update Ben, want hij is de eerste. 483 00:20:34,410 --> 00:20:36,350 Het eerste element van deze lijst gaat nu zijn Brian. 484 00:20:36,350 --> 00:20:38,070 Dus Ben punt bij Brian. 485 00:20:38,070 --> 00:20:39,320 OK, wat nu? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Wie krijgt wees naar wie? 488 00:20:43,460 --> 00:20:44,710 >> STUDENT: [onverstaanbaar]. 489 00:20:44,710 --> 00:20:46,180 >> LUIDSPREKER 1: OK dus Brian heeft te wijzen op Jason. 490 00:20:46,180 --> 00:20:48,360 Maar ik heb verloren spoor van die pointer? 491 00:20:48,360 --> 00:20:49,980 Weet ik waar Jason is? 492 00:20:49,980 --> 00:20:50,790 >> STUDENT: [onverstaanbaar]. 493 00:20:50,790 --> 00:20:52,620 >> LUIDSPREKER 1: ik doe, want ik ben de tijdelijke pointer. 494 00:20:52,620 --> 00:20:55,110 En vermoedelijk, heb ik niet veranderd te wijzen op het nieuwe knooppunt. 495 00:20:55,110 --> 00:20:58,300 Dus we kunnen gewoon Brian punt bij wie ik wijzend op. 496 00:20:58,300 --> 00:20:59,000 En we zijn klaar. 497 00:20:59,000 --> 00:21:01,890 Dus geval een, insertie in de het begin van de lijst. 498 00:21:01,890 --> 00:21:02,950 Er waren twee belangrijke stappen. 499 00:21:02,950 --> 00:21:06,750 Een, moeten we Ben updaten, en vervolgens moeten we ook Brian updaten. 500 00:21:06,750 --> 00:21:09,230 En dan heb ik geen zorgen te maken gesjouw door de rest van de 501 00:21:09,230 --> 00:21:12,680 lijst, omdat we al vond zijn locatie, want hij behoorde tot de 502 00:21:12,680 --> 00:21:14,080 links van het eerste element. 503 00:21:14,080 --> 00:21:15,400 >> Oke, dus vrij eenvoudig. 504 00:21:15,400 --> 00:21:18,110 In feite, voelt alsof we zijn er bijna waardoor ook deze ingewikkelde. 505 00:21:18,110 --> 00:21:20,240 Dus laten we nu plukken uit het einde van de lijst, en zie waar 506 00:21:20,240 --> 00:21:21,380 de complexiteit begint. 507 00:21:21,380 --> 00:21:24,560 Dus als nu, ik alloc uit het publiek. 508 00:21:24,560 --> 00:21:25,540 Iedereen wil spelen 55? 509 00:21:25,540 --> 00:21:26,700 Oke, zag ik voor het eerst je hand. 510 00:21:26,700 --> 00:21:29,620 Kom maar naar boven. 511 00:21:29,620 --> 00:21:30,030 Yeah. 512 00:21:30,030 --> 00:21:31,177 Wat is je naam? 513 00:21:31,177 --> 00:21:32,310 >> STUDENT: [onverstaanbaar]. 514 00:21:32,310 --> 00:21:33,240 >> LUIDSPREKER 1: Habata. 515 00:21:33,240 --> 00:21:33,890 OK, kom op omhoog. 516 00:21:33,890 --> 00:21:35,730 Je zult het nummer 55 zijn. 517 00:21:35,730 --> 00:21:37,820 Zodat je, natuurlijk, behoren aan het einde van de lijst. 518 00:21:37,820 --> 00:21:41,850 Dus laten we herhalen de simulatie met mij zijnde de PTR voor slechts een moment. 519 00:21:41,850 --> 00:21:44,050 Dus ik ben eerst naar het punt op wat Ben is wijzend op. 520 00:21:44,050 --> 00:21:45,900 We zijn beiden nu op Brian wijzen. 521 00:21:45,900 --> 00:21:48,420 Dus 55 is niet minder dan vijf. 522 00:21:48,420 --> 00:21:52,510 Dus ik ga mezelf updaten door wijzend naar Brian's volgende pointer, die 523 00:21:52,510 --> 00:21:54,450 Nu is natuurlijk Jason. 524 00:21:54,450 --> 00:21:57,310 55 is niet minder dan negen, dus Ik ga PTR updaten. 525 00:21:57,310 --> 00:21:58,890 Ik ga PTR updaten. 526 00:21:58,890 --> 00:22:02,290 Ik ga PTR updaten Ik ga PTR updaten. 527 00:22:02,290 --> 00:22:05,060 En ik ga - hmm, wat is je naam ook alweer? 528 00:22:05,060 --> 00:22:05,560 >> STUDENT: Diana. 529 00:22:05,560 --> 00:22:09,190 >> LUIDSPREKER 1: Diana wijst, natuurlijk, op nul met haar linkerhand. 530 00:22:09,190 --> 00:22:13,030 Dus waar komt Habata eigenlijk duidelijk te horen? 531 00:22:13,030 --> 00:22:15,050 Naar links, hier. 532 00:22:15,050 --> 00:22:19,460 Dus hoe weet ik om haar hier te zetten Ik denk dat ik het verpest. 533 00:22:19,460 --> 00:22:22,420 Want wat is PTR kunst dit moment in de tijd? 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Dus ook al, visueel, kunnen we uiteraard al deze te zien 536 00:22:25,580 --> 00:22:26,610 jongens hier op het podium. 537 00:22:26,610 --> 00:22:29,680 Ik heb niet bijgehouden van de vorige persoon in de lijst. 538 00:22:29,680 --> 00:22:33,210 Ik heb geen een vinger wijzen, in dit geval, het nodenummer 34. 539 00:22:33,210 --> 00:22:34,760 >> Dus laten we daadwerkelijk beginnen dit over. 540 00:22:34,760 --> 00:22:37,560 Dus nu heb ik eigenlijk niet nodig een tweede lokale variabele. 541 00:22:37,560 --> 00:22:40,980 En dit is wat je ziet in de werkelijke monster C-code, waar als ik ga, 542 00:22:40,980 --> 00:22:45,860 toen ik updaten mijn rechterhand te wijzen Jason, waardoor Brian achterlatend, I 543 00:22:45,860 --> 00:22:51,440 beter beginnen met mijn linkerhand te werken waar ik was, zodat als ik ga 544 00:22:51,440 --> 00:22:52,700 door deze lijst - 545 00:22:52,700 --> 00:22:55,040 meer onhandig dan ik van plan was nu hier visueel - 546 00:22:55,040 --> 00:22:56,740 Ik ga naar de einde van de lijst. 547 00:22:56,740 --> 00:23:00,020 >> Deze hand is nog steeds nul, die vrij is nutteloos, behalve aangeven 548 00:23:00,020 --> 00:23:02,980 Ik ben duidelijk aan het einde van de lijst, maar nu heb ik tenminste dit 549 00:23:02,980 --> 00:23:08,270 voorganger wijzer hier wijzen, zodat nu wat handen en wat pointers nodig 550 00:23:08,270 --> 00:23:10,150 worden bijgewerkt? 551 00:23:10,150 --> 00:23:13,214 Wiens hand wil je opnieuw te configureren eerste? 552 00:23:13,214 --> 00:23:15,190 >> STUDENT: [onverstaanbaar]. 553 00:23:15,190 --> 00:23:16,220 >> LUIDSPREKER 1: OK, dus Diana's. 554 00:23:16,220 --> 00:23:21,110 Waar wil je naar punt Linker pointer Diana's bij? 555 00:23:21,110 --> 00:23:23,620 Bij 55, vermoedelijk, zodat we daar hebben gestoken. 556 00:23:23,620 --> 00:23:25,560 En waar moet 55 pointer gaan? 557 00:23:25,560 --> 00:23:27,000 Naar beneden, wat neerkomt op null. 558 00:23:27,000 --> 00:23:28,890 En mijn handen, op dit moment, niet doen uit want ze waren gewoon 559 00:23:28,890 --> 00:23:30,070 tijdelijke variabelen. 560 00:23:30,070 --> 00:23:31,030 Dus nu zijn we klaar. 561 00:23:31,030 --> 00:23:34,650 >> Dus de extra complexiteit daar - en het is niet zo moeilijk te implementeren, 562 00:23:34,650 --> 00:23:38,660 maar we moeten een secundaire variabele te maken ervoor dat voordat ik naar mijn rechter 563 00:23:38,660 --> 00:23:42,140 kant heb ik de waarde van mijn linker updaten de hand, pred wijzer in dit geval, dus 564 00:23:42,140 --> 00:23:45,860 dat ik een achterstand pointer bij te houden van waar ik was te houden. 565 00:23:45,860 --> 00:23:49,360 Nu als een terzijde, als je dit denkt door, dit voelt alsof het een 566 00:23:49,360 --> 00:23:51,490 beetje vervelend te moeten houden Volg dit linkerhand. 567 00:23:51,490 --> 00:23:54,015 >> Wat zou een andere oplossing dit probleem geweest? 568 00:23:54,015 --> 00:23:56,500 Als je echt om de gegevens opnieuw te ontwerpen structuur we praten 569 00:23:56,500 --> 00:23:59,630 door middel van dit moment? 570 00:23:59,630 --> 00:24:02,690 Als dit gewoon een soort van voelt een beetje vervelend te moeten, willen, twee wijzers 571 00:24:02,690 --> 00:24:08,430 het doornemen van de lijst, wie anders zou hebben, in een ideale wereld, gehandhaafd 572 00:24:08,430 --> 00:24:10,160 informatie die we nodig hebben? 573 00:24:10,160 --> 00:24:11,360 Yeah? 574 00:24:11,360 --> 00:24:12,610 >> STUDENT: [onverstaanbaar]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> LUIDSPREKER 1: Precies. 577 00:24:16,150 --> 00:24:19,130 Rechts dus er is eigenlijk een interessante kiem van een idee. 578 00:24:19,130 --> 00:24:22,470 En dit idee van een eerdere pointer, wijzend naar het vorige element. 579 00:24:22,470 --> 00:24:25,580 Wat als ik gewoon belichaamd dat binnenkant van de lijst zelf? 580 00:24:25,580 --> 00:24:27,810 En het gaat om moeilijk te visualiseren zijn dit zonder al het papier 581 00:24:27,810 --> 00:24:28,830 vallen op de vloer. 582 00:24:28,830 --> 00:24:31,860 Maar stel dat deze jongens zowel gebruikt hun handen hebben een eerdere 583 00:24:31,860 --> 00:24:35,950 wijzer, en een volgende pointer, waardoor uitvoering van wat wij een dubbel zullen noemen 584 00:24:35,950 --> 00:24:36,830 gelinkte lijst. 585 00:24:36,830 --> 00:24:41,090 Dat me zou toestaan ​​om een ​​soort van terugspoelen, veel gemakkelijker zonder mij, de 586 00:24:41,090 --> 00:24:43,800 programmeur, hoeven houden bijhouden handmatig - 587 00:24:43,800 --> 00:24:44,980 echt handmatig - 588 00:24:44,980 --> 00:24:47,280 van waar ik eerder was geweest in de lijst. 589 00:24:47,280 --> 00:24:48,110 Dus zullen we niet doen. 590 00:24:48,110 --> 00:24:50,950 We zullen het simpel te houden, want dat is gaat komen op een prijs, twee keer zo 591 00:24:50,950 --> 00:24:53,450 veel ruimte voor de pointers, als je wilt een tweede. 592 00:24:53,450 --> 00:24:55,760 Maar dat is inderdaad een gemeenschappelijke gegevensstructuur bekend als 593 00:24:55,760 --> 00:24:57,410 dubbel gelinkte lijst. 594 00:24:57,410 --> 00:25:01,310 >> Laten we het laatste voorbeeld hier en zet deze jongens uit hun ellende. 595 00:25:01,310 --> 00:25:03,270 Dus malloc 20. 596 00:25:03,270 --> 00:25:05,320 Kom maar uit het gangpad daar. 597 00:25:05,320 --> 00:25:06,280 Oke, wat is uw naam? 598 00:25:06,280 --> 00:25:07,440 >> STUDENT: [onverstaanbaar]. 599 00:25:07,440 --> 00:25:07,855 >> LUIDSPREKER 1: Sorry? 600 00:25:07,855 --> 00:25:08,480 >> STUDENT: [onverstaanbaar]. 601 00:25:08,480 --> 00:25:09,410 >> LUIDSPREKER 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK kom op omhoog. 603 00:25:10,230 --> 00:25:11,910 Je moet 20. 604 00:25:11,910 --> 00:25:14,720 Je natuurlijk gaat behoort tussen de 17 en 22. 605 00:25:14,720 --> 00:25:16,150 Dus laat ik leer mijn les. 606 00:25:16,150 --> 00:25:18,150 Ik ga om wijzer te beginnen wijzend op Brian. 607 00:25:18,150 --> 00:25:21,190 En ik ga mijn linkerhand hebben alleen update naar Brian als ik naar 608 00:25:21,190 --> 00:25:23,600 Jason, controle doet 20 minder dan negen? 609 00:25:23,600 --> 00:25:24,060 Nee. 610 00:25:24,060 --> 00:25:25,430 Is 20 minder dan 17? 611 00:25:25,430 --> 00:25:25,880 Nee. 612 00:25:25,880 --> 00:25:27,450 Is 20 minder dan 22? 613 00:25:27,450 --> 00:25:28,440 Ja. 614 00:25:28,440 --> 00:25:34,070 Dus wat pointers of handen moeten veranderen waar ze nu richten? 615 00:25:34,070 --> 00:25:37,070 >> Dus we kunnen 17 doen wijzend op 20. 616 00:25:37,070 --> 00:25:37,860 Dus dat is prima. 617 00:25:37,860 --> 00:25:40,080 Waar willen we naar punt de aanwijzer nu? 618 00:25:40,080 --> 00:25:41,330 At 22. 619 00:25:41,330 --> 00:25:45,410 En we weten waar 22 is, nogmaals dank naar mijn tijdelijke pointer. 620 00:25:45,410 --> 00:25:46,760 Dus we zijn OK daar. 621 00:25:46,760 --> 00:25:49,440 Omdat deze tijdelijke opslag Ik heb spoor hield van waar iedereen is. 622 00:25:49,440 --> 00:25:55,055 En nu kunt u visueel gaan in waar u behoort, en nu moeten we 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 stress ballen, en een applaus voor 624 00:25:58,410 --> 00:25:59,770 deze jongens, als we dat konden. 625 00:25:59,770 --> 00:26:00,410 Mooi gedaan. 626 00:26:00,410 --> 00:26:05,320 >> [Applaus] 627 00:26:05,320 --> 00:26:06,330 >> LUIDSPREKER 1: Oke. 628 00:26:06,330 --> 00:26:09,860 En je kan de stukken houden papier als aandenken. 629 00:26:09,860 --> 00:26:15,930 >> Oke, dus, geloof me het is een stuk gemakkelijker te lopen door die met 630 00:26:15,930 --> 00:26:17,680 de mens dan het is met de werkelijke code. 631 00:26:17,680 --> 00:26:22,690 Maar wat je zult in slechts een moment te vinden Nu, is dat hetzelfde - oh, dank je. 632 00:26:22,690 --> 00:26:23,630 Dank u - 633 00:26:23,630 --> 00:26:29,360 is dat je zult zien dat dezelfde gegevens structuur, een gelinkte lijst, kan eigenlijk 634 00:26:29,360 --> 00:26:33,200 gebruikt als bouwsteen nog geavanceerde data-structuren. 635 00:26:33,200 --> 00:26:37,620 >> En beseffen ook het thema hier is dat we hebben absoluut meer geïntroduceerd 636 00:26:37,620 --> 00:26:40,060 complexiteit in de uitvoering van dit algoritme. 637 00:26:40,060 --> 00:26:43,940 Inbrengen, en als we gingen er doorheen, verwijderen en zoeken, is een beetje 638 00:26:43,940 --> 00:26:46,660 ingewikkelder dan het was een array. 639 00:26:46,660 --> 00:26:48,040 Maar we krijgen een aantal dynamiek. 640 00:26:48,040 --> 00:26:50,180 We krijgen een adaptief datastructuur. 641 00:26:50,180 --> 00:26:54,010 >> Maar nogmaals, we betalen een prijs van het hebben van een aantal extra problemen, zowel 642 00:26:54,010 --> 00:26:54,910 uitvoering ervan. 643 00:26:54,910 --> 00:26:56,750 En we zijn opgegeven willekeurige toegang. 644 00:26:56,750 --> 00:27:00,450 En om eerlijk te zijn, er is geen enkele mooie schoon dia ik je kan geven dat 645 00:27:00,450 --> 00:27:03,120 zegt hier is de reden waarom een ​​gelinkte lijst is beter dan een array. 646 00:27:03,120 --> 00:27:04,100 En laat het daarbij. 647 00:27:04,100 --> 00:27:07,520 Omdat het thema terugkerende nu, zelfs meer dus in de komende weken, is 648 00:27:07,520 --> 00:27:10,200 dat er niet per se een juist antwoord. 649 00:27:10,200 --> 00:27:13,830 >> Daarom hebben we de afzonderlijke as van ontwerp voor probleem sets. 650 00:27:13,830 --> 00:27:17,700 Het zal erg contextgevoelig of u deze gegevens gebruiken 651 00:27:17,700 --> 00:27:21,750 of dat een structuur, en het zal afhankelijk van wat voor u in termen 652 00:27:21,750 --> 00:27:24,620 van middelen en complexiteit. 653 00:27:24,620 --> 00:27:28,830 >> Maar laat me voorstellen dat de ideale data structuur, de heilige graal, zou zijn 654 00:27:28,830 --> 00:27:32,200 iets dat constante tijd, ongeacht hoeveel spul is 655 00:27:32,200 --> 00:27:36,940 erin, zou het niet geweldig zijn als er een gegevensstructuur geretourneerd antwoorden 656 00:27:36,940 --> 00:27:37,920 constante tijd. 657 00:27:37,920 --> 00:27:38,330 Ja. 658 00:27:38,330 --> 00:27:40,110 Dit woord is in uw enorme woordenboek. 659 00:27:40,110 --> 00:27:41,550 Of nee, dit woord niet. 660 00:27:41,550 --> 00:27:43,270 Of een dergelijk probleem. 661 00:27:43,270 --> 00:27:46,360 Nou laten we eens kijken of we kunnen niet in ieder geval neem een ​​stap in de richting die. 662 00:27:46,360 --> 00:27:50,190 >> Laat ik een nieuwe datastructuur te stellen dat kan worden gebruikt voor verschillende dingen, 663 00:27:50,190 --> 00:27:52,260 in dit geval wel een hash table. 664 00:27:52,260 --> 00:27:55,590 En dus zijn we eigenlijk terug naar blik in een matrix, in dit geval en 665 00:27:55,590 --> 00:28:00,550 enigszins arbitrair, ik heb dit getekend hash table als een array met een soort van 666 00:28:00,550 --> 00:28:02,810 tweedimensionale matrix - 667 00:28:02,810 --> 00:28:05,410 of liever het is hier afgebeeld als een twee dimensionale array - maar dit is slechts 668 00:28:05,410 --> 00:28:10,770 een array van maat 26, zodanig dat als we roepen de array, tafel beugel 669 00:28:10,770 --> 00:28:12,440 nul de rechthoek aan de top. 670 00:28:12,440 --> 00:28:15,090 Tafel beugel 25 is de rechthoek onderaan. 671 00:28:15,090 --> 00:28:18,620 En dit is hoe ik een data zou kunnen trekken structuur waarin ik wil opslaan 672 00:28:18,620 --> 00:28:19,790 mensen namen. 673 00:28:19,790 --> 00:28:24,370 >> Dus bijvoorbeeld, en ik zal niet tekenen de hele zaak hier op de overhead, als ik 674 00:28:24,370 --> 00:28:29,160 had deze array, die ik nu ga bel een hash table, en dit is weer 675 00:28:29,160 --> 00:28:31,360 locatie nul. 676 00:28:31,360 --> 00:28:34,840 Dit hier is locatie een, enzovoort. 677 00:28:34,840 --> 00:28:37,880 Ik beweer dat ik wil deze gegevens gebruiken structuur, ter wille van de discussie, 678 00:28:37,880 --> 00:28:42,600 om namen van mensen slaan, Alice en Bob en Charlie en andere dergelijke namen. 679 00:28:42,600 --> 00:28:46,110 Dus denk aan dit nu als het begin van, zeg, een woordenboek 680 00:28:46,110 --> 00:28:47,520 met veel woorden. 681 00:28:47,520 --> 00:28:49,435 Ze toevallig namen zijn in ons voorbeeld hier. 682 00:28:49,435 --> 00:28:52,560 En dit is maar al te germane, misschien, om uitvoering van een spellingscontrole, zoals we 683 00:28:52,560 --> 00:28:54,400 misschien voor problemen stellen zes. 684 00:28:54,400 --> 00:28:59,300 >> Dus als we hebben een scala aan totale grootte 26 zodat dit het 25e locatie 685 00:28:59,300 --> 00:29:03,390 aan de onderkant, en ik beweer dat Alice is het eerste woord in het woordenboek van 686 00:29:03,390 --> 00:29:07,260 namen die ik wil invoegen in RAM, in deze datastructuur, waar zijn 687 00:29:07,260 --> 00:29:12,480 instincten vertellen dat Alice's naam moet gaan in deze serie? 688 00:29:12,480 --> 00:29:13,510 >> We hebben 26 opties. 689 00:29:13,510 --> 00:29:14,990 Waar we haar willen zetten? 690 00:29:14,990 --> 00:29:16,200 We willen haar in beugel nul, toch? 691 00:29:16,200 --> 00:29:18,280 Een voor Alice, laten we noemen dat nul. 692 00:29:18,280 --> 00:29:20,110 En B zal een, en C zullen twee. 693 00:29:20,110 --> 00:29:22,600 Dus we gaan schrijven Naam hier Alice's. 694 00:29:22,600 --> 00:29:24,890 Als we dan plaatst Bob, zijn naam zal hier gaan. 695 00:29:24,890 --> 00:29:27,280 Charlie zal hier gaan. 696 00:29:27,280 --> 00:29:30,500 Enzovoort omlaag door Deze gegevensstructuur. 697 00:29:30,500 --> 00:29:32,090 >> Dit is een prachtige datastructuur. 698 00:29:32,090 --> 00:29:32,730 Waarom? 699 00:29:32,730 --> 00:29:37,460 Tja, wat is de looptijd van de invoegen van de naam van een mens in deze 700 00:29:37,460 --> 00:29:39,850 datastructuur op dit moment? 701 00:29:39,850 --> 00:29:43,702 Gezien het feit dat deze tabel wordt geïmplementeerd, echt, als een array. 702 00:29:43,702 --> 00:29:44,940 Nou het is een constante tijd. 703 00:29:44,940 --> 00:29:45,800 Het is orde van een. 704 00:29:45,800 --> 00:29:46,360 Waarom? 705 00:29:46,360 --> 00:29:48,630 >> Nou hoe bepaal je waar Alice hoort? 706 00:29:48,630 --> 00:29:51,000 Je kijkt naar de letter van haar naam? 707 00:29:51,000 --> 00:29:51,490 De eerste. 708 00:29:51,490 --> 00:29:54,350 En je kunt er komen, als het een string, door alleen maar naar touwtje 709 00:29:54,350 --> 00:29:55,200 bracket nul. 710 00:29:55,200 --> 00:29:57,110 Dus de nulde karakter van de string. 711 00:29:57,110 --> 00:29:57,610 Dat is makkelijk. 712 00:29:57,610 --> 00:30:00,350 We deden dat in de crypto opdracht weken geleden. 713 00:30:00,350 --> 00:30:05,310 En dan als je eenmaal weet dat Alice's letter is hoofdletter A, kunnen we aftrekken 714 00:30:05,310 --> 00:30:08,160 off 65 of hoofdletter A zelf, dat geeft ons nul. 715 00:30:08,160 --> 00:30:10,940 Dus we weten nu dat Alice behoort op locatie nul. 716 00:30:10,940 --> 00:30:14,240 >> En krijgt een pointer naar deze gegevens structuur, van een soort, hoe lang duurt 717 00:30:14,240 --> 00:30:18,840 het me te vinden locatie nul in een array? 718 00:30:18,840 --> 00:30:22,080 Slechts een stap, rechts Het is een constante tijd vanwege het RAM we 719 00:30:22,080 --> 00:30:23,780 voorstel was een kenmerk van een array. 720 00:30:23,780 --> 00:30:28,570 Dus in het kort, het uitzoeken wat de index naam van Alice's is, dat, in 721 00:30:28,570 --> 00:30:32,610 dit geval is A, of laten we gewoon op te lossen dat tot nul, waarbij B en C is een 722 00:30:32,610 --> 00:30:34,900 twee, uitzoeken dat uit is constante tijd. 723 00:30:34,900 --> 00:30:38,510 Ik heb alleen maar te kijken naar haar eerste brief, uitzoeken waar nul is een 724 00:30:38,510 --> 00:30:40,460 array is ook constante tijd. 725 00:30:40,460 --> 00:30:42,140 Dus technisch is dat als twee stappen nu. 726 00:30:42,140 --> 00:30:43,330 Maar dat is nog steeds constant. 727 00:30:43,330 --> 00:30:46,880 Dus we noemen dat grote O van een, dus we hebben ingebracht Alice in deze tabel in 728 00:30:46,880 --> 00:30:48,440 constante tijd. 729 00:30:48,440 --> 00:30:50,960 >> Maar natuurlijk, ik ben wezen naïeve hier, toch? 730 00:30:50,960 --> 00:30:53,240 Wat als er een Aaron in de klas? 731 00:30:53,240 --> 00:30:53,990 Of Alicia? 732 00:30:53,990 --> 00:30:57,230 Of enige andere namen die beginnen met A. Waar gaan we heen te zetten 733 00:30:57,230 --> 00:31:00,800 die persoon, toch? 734 00:31:00,800 --> 00:31:03,420 Ik bedoel, op dit moment is er slechts drie mensen op de tafel, dus we misschien 735 00:31:03,420 --> 00:31:07,490 moet Aaron zetten op locatie nul een twee drie. 736 00:31:07,490 --> 00:31:09,480 >> Rechts, kon ik hier zetten A. 737 00:31:09,480 --> 00:31:13,350 Maar dan, als we proberen om David te voegen in deze lijst, waar gaat David heen? 738 00:31:13,350 --> 00:31:15,170 Nu ons systeem begint te breken neer, toch? 739 00:31:15,170 --> 00:31:19,210 Want nu David eindigt hier Als Aaron is eigenlijk hier. 740 00:31:19,210 --> 00:31:23,060 En dus nu dit hele idee van een schone datastructuur die ons geeft 741 00:31:23,060 --> 00:31:28,010 constante tijd inserties is niet meer constante tijd, want ik moet 742 00:31:28,010 --> 00:31:31,240 controleren, oh, verdomme, iemand is al op locatie Alice's. 743 00:31:31,240 --> 00:31:35,320 >> Laat ik sonde de rest van deze gegevens structuur, op zoek naar een plek om te zetten 744 00:31:35,320 --> 00:31:37,130 iemand als Aarons naam. 745 00:31:37,130 --> 00:31:39,390 En dus ook dat begint aan lineaire tijd duren. 746 00:31:39,390 --> 00:31:42,710 Bovendien, als je nu wilt het vinden Aaron in deze datastructuur, en u 747 00:31:42,710 --> 00:31:45,430 controleren, en Aarons naam is niet hier. 748 00:31:45,430 --> 00:31:47,960 Idealiter zou je gewoon zeggen Aaron's niet in de gegevensstructuur. 749 00:31:47,960 --> 00:31:51,530 Maar als je beginnen met het maken ruimte voor Aaron waar er moet een D zijn 750 00:31:51,530 --> 00:31:55,600 of een E, u, slechtste geval moeten controleren geheel gegevensstructuur, in 751 00:31:55,600 --> 00:31:59,480 welk geval het delegeert in iets lineair in de grootte van de tabel. 752 00:31:59,480 --> 00:32:00,920 >> Dus oke, ik zal dit oplossen. 753 00:32:00,920 --> 00:32:04,200 Het probleem is hier dat ik had 26 elementen in de array. 754 00:32:04,200 --> 00:32:05,000 Laat ik het te veranderen. 755 00:32:05,000 --> 00:32:06,010 Whoops. 756 00:32:06,010 --> 00:32:10,600 Laat ik het zo wijzigen dat in plaats van het zijn maat 26 in totaal, let op de bodem 757 00:32:10,600 --> 00:32:12,720 index gaat veranderen naar n minus 1. 758 00:32:12,720 --> 00:32:16,610 Als 26 is duidelijk te klein voor de mens ' namen, omdat er duizenden 759 00:32:16,610 --> 00:32:20,830 namen van de wereld, laten we gewoon te maken in 100 of 1000 of 10.000. 760 00:32:20,830 --> 00:32:22,960 Laten we wijzen veel meer ruimte. 761 00:32:22,960 --> 00:32:27,230 >> Nou dat niet noodzakelijkerwijs afnemen de kans dat we twee hebben 762 00:32:27,230 --> 00:32:31,510 mensen met namen die beginnen met A, en dus, je gaat proberen om A te zetten 763 00:32:31,510 --> 00:32:33,120 namen op locatie nul nog steeds. 764 00:32:33,120 --> 00:32:36,850 Ze zijn nog steeds te botsen, die betekent dat we nog steeds een oplossing te brengen moet 765 00:32:36,850 --> 00:32:41,020 Alice en Aäron en Alicia en andere namen die beginnen met A elders. 766 00:32:41,020 --> 00:32:43,460 Maar hoeveel van een probleem is dit? 767 00:32:43,460 --> 00:32:46,870 Wat is de kans dat u hebben botsingen in een data 768 00:32:46,870 --> 00:32:48,240 structuur als deze? 769 00:32:48,240 --> 00:32:52,570 >> Nou, laat ik - we komen terug om hier die vraag. 770 00:32:52,570 --> 00:32:55,530 En kijken hoe we zouden kunnen eerst oplossen. 771 00:32:55,530 --> 00:32:58,480 Laat ik trek dit voorstel hier. 772 00:32:58,480 --> 00:33:02,020 Wat we zojuist beschreven is een algoritme, een heuristische genoemd lineaire 773 00:33:02,020 --> 00:33:05,030 indringende waarbij, als je probeerde in te voegen iets wat hier in deze data 774 00:33:05,030 --> 00:33:08,920 structuur, die een hash tabel wordt genoemd, en er is geen ruimte daar, je 775 00:33:08,920 --> 00:33:12,000 echt sonde de datastructuur controleren, is deze beschikbaar? 776 00:33:12,000 --> 00:33:13,430 Is deze beschikbaar is deze beschikbaar? 777 00:33:13,430 --> 00:33:13,980 Is deze beschikbaar? 778 00:33:13,980 --> 00:33:17,550 En toen het eindelijk is, je plaatst de noemen die je oorspronkelijk bedoeld 779 00:33:17,550 --> 00:33:19,370 elders op die locatie. 780 00:33:19,370 --> 00:33:23,360 Maar in het ergste geval, de enige plek zou de onderkant van de gegevens worden 781 00:33:23,360 --> 00:33:25,090 structuur, het einde van de array. 782 00:33:25,090 --> 00:33:30,130 >> Dus lineaire sonderen, in het ergste geval, delegeert in een lineaire algoritme waar 783 00:33:30,130 --> 00:33:34,500 Aaron, als hij toevallig laatst moet worden ingevoegd in deze datastructuur, hij zou kunnen 784 00:33:34,500 --> 00:33:39,540 botsen met deze eerste plaats, maar dan uiteindelijk door pech helemaal aan het eind. 785 00:33:39,540 --> 00:33:43,940 Dus dit is geen constante tijd heilige graal voor ons. 786 00:33:43,940 --> 00:33:47,650 Deze benadering van het plaatsen van elementen in een gegevensstructuur, een hash 787 00:33:47,650 --> 00:33:52,050 tafel lijkt niet constant tijd althans niet in het algemene geval. 788 00:33:52,050 --> 00:33:54,000 Het kan delegeren in iets lineair. 789 00:33:54,000 --> 00:33:56,970 >> Dus wat als we botsingen op te lossen enigszins anders? 790 00:33:56,970 --> 00:34:00,740 Dus hier is een meer verfijnde benaderen om wat er nog 791 00:34:00,740 --> 00:34:02,800 riep een hash table. 792 00:34:02,800 --> 00:34:05,890 En door hash, als een terzijde, wat Ik bedoel is de index die 793 00:34:05,890 --> 00:34:07,070 Ik verwees naar eerder. 794 00:34:07,070 --> 00:34:09,810 Om hash iets kan zijn gezien als een werkwoord. 795 00:34:09,810 --> 00:34:13,690 >> Dus als je hash Alice is een naam, een hash-functie, om zo te zeggen, 796 00:34:13,690 --> 00:34:14,710 moet een aantal keren. 797 00:34:14,710 --> 00:34:18,199 In dit geval is nul als zij behoort bij locatie nul, een of zij behoort bij 798 00:34:18,199 --> 00:34:20,000 locatie een, enzovoort. 799 00:34:20,000 --> 00:34:24,360 Dus mijn hash-functie tot nu toe is super simpel, alleen kijken naar de 800 00:34:24,360 --> 00:34:26,159 eerste letter van iemands naam. 801 00:34:26,159 --> 00:34:29,090 Maar een hash-functie neemt als ingang een stukje van de gegevens, een 802 00:34:29,090 --> 00:34:30,210 touwtje, een int, wat dan ook. 803 00:34:30,210 --> 00:34:32,239 En hij spuugt meestal een nummer. 804 00:34:32,239 --> 00:34:35,739 En dat aantal is waar die gegevens element behoort tot een gegevensstructuur 805 00:34:35,739 --> 00:34:37,800 hier bekend als een hash table. 806 00:34:37,800 --> 00:34:41,400 >> Dus gewoon intuïtief, dit is een iets andere context. 807 00:34:41,400 --> 00:34:44,170 Dit is eigenlijk verwijst naar een voorbeeld waarbij verjaardagen, waar 808 00:34:44,170 --> 00:34:46,850 er misschien wel 31 dagen van de maand. 809 00:34:46,850 --> 00:34:52,239 Maar wat heeft deze persoon beslist om doen in geval van een aanrijding? 810 00:34:52,239 --> 00:34:55,304 Context nu zijn, niet een botsing van namen, maar een botsing van verjaardagen, 811 00:34:55,304 --> 00:35:00,760 Als twee mensen hebben dezelfde verjaardag op 2 oktober, bijvoorbeeld. 812 00:35:00,760 --> 00:35:02,120 >> STUDENT: [onverstaanbaar]. 813 00:35:02,120 --> 00:35:05,010 >> LUIDSPREKER 1: Ja, dus hier hebben we de hefboomwerking van gelinkte lijsten. 814 00:35:05,010 --> 00:35:07,830 Dus het ziet er een beetje anders dan trokken we het eerder. 815 00:35:07,830 --> 00:35:10,790 Maar we lijken moeten een array aan de linkerkant. 816 00:35:10,790 --> 00:35:13,230 Dat is een index, voor geen specifieke reden. 817 00:35:13,230 --> 00:35:14,630 Maar het is nog steeds een array. 818 00:35:14,630 --> 00:35:16,160 Het is een array van pointers. 819 00:35:16,160 --> 00:35:20,670 En elk van die elementen, elk van deze kringen of slashes - de schuine streep 820 00:35:20,670 --> 00:35:23,970 vertegenwoordigen null - elk van deze pointers is blijkbaar wijzen 821 00:35:23,970 --> 00:35:25,730 wat datastructuur? 822 00:35:25,730 --> 00:35:26,890 Een gekoppelde lijst. 823 00:35:26,890 --> 00:35:30,530 >> Dus nu hebben we de mogelijkheid om harde code in ons programma 824 00:35:30,530 --> 00:35:32,010 de grootte van de tabel. 825 00:35:32,010 --> 00:35:35,360 In dit geval, we weten dat er nooit meer dan 31 dagen in een maand. 826 00:35:35,360 --> 00:35:38,480 Zo hard coderen van een waarde als 31 wordt redelijk in die context. 827 00:35:38,480 --> 00:35:42,700 In de context van namen, harde codering 26 is het niet onredelijk dat de mensen 828 00:35:42,700 --> 00:35:46,340 alleen namen beginnen met bijvoorbeeld het alfabet met A tot en met Z. 829 00:35:46,340 --> 00:35:50,180 >> We kunnen ze allemaal proppen in die gegevens structuur zo lang, als we een 830 00:35:50,180 --> 00:35:55,330 botsing, wij niet de namen hier zetten, We denken in plaats van deze cellen 831 00:35:55,330 --> 00:36:00,270 niet als strings zichzelf, maar verwijzingen naar bijvoorbeeld Alice. 832 00:36:00,270 --> 00:36:03,660 En dan Alice kan een andere pointer hebben een andere naam ab 833 00:36:03,660 --> 00:36:06,150 A. En Bob gaat hier eigenlijk voorbij. 834 00:36:06,150 --> 00:36:10,850 >> En als er een andere naam beginnend met B, komt hij hierheen. 835 00:36:10,850 --> 00:36:15,070 En zodat elk van de elementen van deze tafel twee, als we ontwierp deze een 836 00:36:15,070 --> 00:36:17,350 beetje meer slim - 837 00:36:17,350 --> 00:36:18,125 kom op - 838 00:36:18,125 --> 00:36:22,950 als we ontwierp dit een beetje meer slim, wordt nu een adaptieve data 839 00:36:22,950 --> 00:36:27,720 structuur, waar er geen harde limiet op hoeveel elementen u kunt invoegen 840 00:36:27,720 --> 00:36:30,700 erin want als je hebt een botsing, dat is prima. 841 00:36:30,700 --> 00:36:34,690 Gewoon doorgaan en voeg deze toe aan wat we zagen een beetje geleden was 842 00:36:34,690 --> 00:36:38,290 bekend als een gelinkte lijst. 843 00:36:38,290 --> 00:36:39,690 >> Nou laten we pauze voor slechts een moment. 844 00:36:39,690 --> 00:36:42,570 Wat is de waarschijnlijkheid van een botsing in de eerste plaats? 845 00:36:42,570 --> 00:36:45,480 Goed, misschien ben ik dan denk, misschien Ik ben meer dan engineering van dit probleem, 846 00:36:45,480 --> 00:36:46,370 want weet je wat? 847 00:36:46,370 --> 00:36:49,070 Ja, ik kan komen met willekeurige voorbeelden uit de top van mijn hoofd als 848 00:36:49,070 --> 00:36:52,870 Allison en Aaron, maar in werkelijkheid, aangezien een gelijkmatige verdeling van 849 00:36:52,870 --> 00:36:56,990 ingangen, dat is wat random inserties in een gegevensstructuur, wat is eigenlijk 850 00:36:56,990 --> 00:36:58,580 de waarschijnlijkheid van een botsing? 851 00:36:58,580 --> 00:37:01,670 Wel blijkt, het is eigenlijk super hoog. 852 00:37:01,670 --> 00:37:03,850 Laat me generaliseren dit probleem als deze. 853 00:37:03,850 --> 00:37:08,890 >> Dus in een ruimte van n CS50 studenten, wat is de kans dat ten minste 854 00:37:08,890 --> 00:37:11,010 twee studenten in de kamer hebben dezelfde verjaardag? 855 00:37:11,010 --> 00:37:13,346 Dus er is wat. een paar hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 mensen hier en een aantal honderd mensen thuis vandaag. 857 00:37:16,790 --> 00:37:20,670 Dus als je wilde om ons af te vragen wat er de waarschijnlijkheid van twee mensen 858 00:37:20,670 --> 00:37:23,930 in deze kamer met dezelfde verjaardag, kunnen we dit uitzoeken. 859 00:37:23,930 --> 00:37:26,250 En ik beweer eigenlijk zijn er twee mensen met dezelfde verjaardag. 860 00:37:26,250 --> 00:37:29,560 >> Bijvoorbeeld, heeft iemand hebben vandaag jarig? 861 00:37:29,560 --> 00:37:31,340 Gisteren? 862 00:37:31,340 --> 00:37:32,590 Morgen? 863 00:37:32,590 --> 00:37:35,980 Oke, dus het voelt alsof ik ga moeten deze 363 of zo meer te doen 864 00:37:35,980 --> 00:37:39,500 keer om daadwerkelijk uit te Als we hebben wel een botsing. 865 00:37:39,500 --> 00:37:42,350 Of we kunnen doen dit wiskundig eerder dan tediously 866 00:37:42,350 --> 00:37:43,200 dit te doen. 867 00:37:43,200 --> 00:37:44,500 En stelt de volgende. 868 00:37:44,500 --> 00:37:48,740 >> Dus ik stel voor dat we konden modelleren van de waarschijnlijkheid van twee mensen die de 869 00:37:48,740 --> 00:37:55,320 dezelfde dag jarig als de kans van 1 verminderd de kans dat niemand 870 00:37:55,320 --> 00:37:56,290 op dezelfde dag jarig. 871 00:37:56,290 --> 00:37:59,960 Dus om dit te krijgen, en dit is slechts het mooie manier van schrijven van dit, voor de 872 00:37:59,960 --> 00:38:03,090 eerste persoon in de kamer, hij of zij kan een van de mogelijke hebben 873 00:38:03,090 --> 00:38:07,370 verjaardagen veronderstelling 365 dagen in het jaar, met excuses aan personen met 874 00:38:07,370 --> 00:38:08,760 de 29 februari verjaardag. 875 00:38:08,760 --> 00:38:13,470 >> Dus de eerste persoon in deze kamer is vrij aan een aantal verjaardagen hebben 876 00:38:13,470 --> 00:38:18,280 uit de 365 mogelijkheden zodat we doen dat 365 gedeeld door 365, 877 00:38:18,280 --> 00:38:18,990 die een. 878 00:38:18,990 --> 00:38:22,700 De volgende persoon in de kamer, als het doel is een botsing, kan alleen 879 00:38:22,700 --> 00:38:26,460 zijn of haar verjaardag op hoe verschillende dagen mogelijk? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Dus de tweede term in deze uitdrukking is wezen doet dat wiskunde voor ons 882 00:38:31,430 --> 00:38:33,460 door het aftrekken off een mogelijke dag. 883 00:38:33,460 --> 00:38:36,390 En dan de volgende dag, de volgende dag, de volgende dag naar het totale aantal 884 00:38:36,390 --> 00:38:38,100 van de mensen in de zaal. 885 00:38:38,100 --> 00:38:41,290 >> En als we dan overwegen, wat is dan de kans dat niet van iedereen hebben 886 00:38:41,290 --> 00:38:45,265 unieke verjaardagen, maar nogmaals 1 minus dat, wat we krijgen is een uitdrukking 887 00:38:45,265 --> 00:38:47,810 dat kan zeer grillig zo uitzien. 888 00:38:47,810 --> 00:38:50,330 Maar het is nog interessanter om te kijken naar visueel. 889 00:38:50,330 --> 00:38:55,120 Dit is een grafiek waarbij op de x-as het aantal mensen in de kamer, de 890 00:38:55,120 --> 00:38:56,180 aantal verjaardagen. 891 00:38:56,180 --> 00:38:59,840 Op de Y-as is de kans van een botsing, twee mensen 892 00:38:59,840 --> 00:39:01,230 die op dezelfde dag jarig. 893 00:39:01,230 --> 00:39:05,020 >> En de afhaalmaaltijd van deze curve is dat zodra je naar wilt 40 894 00:39:05,020 --> 00:39:11,110 studenten, je van plan bent op een kans 90% combinatorically twee 895 00:39:11,110 --> 00:39:13,550 mensen of meer hebben op dezelfde dag jarig. 896 00:39:13,550 --> 00:39:18,600 En als je eenmaal aan 58 mensen het willen bijna 100% van een kans beide 897 00:39:18,600 --> 00:39:21,310 mensen in de kamer gaat het hebben dezelfde dag jarig, ook al is er 898 00:39:21,310 --> 00:39:26,650 365 of 366 mogelijk emmers en slechts 58 mensen in de kamer. 899 00:39:26,650 --> 00:39:29,900 Net statistisch je bent waarschijnlijk krijgen botsingen, die in het kort 900 00:39:29,900 --> 00:39:31,810 motiveert deze discussie. 901 00:39:31,810 --> 00:39:35,890 Dat zelfs als we hier chique en beginnen met deze ketens, we zijn nog steeds 902 00:39:35,890 --> 00:39:36,950 zullen botsingen hebben. 903 00:39:36,950 --> 00:39:42,710 >> Zodat het de vraag, wat is de kosten van het doen van toevoegingen en schrappingen 904 00:39:42,710 --> 00:39:44,850 in een datastructuur als deze? 905 00:39:44,850 --> 00:39:46,630 Nou laat me voor te stellen - 906 00:39:46,630 --> 00:39:51,570 en laat me terug te gaan naar het scherm over hier - als we n elementen in de 907 00:39:51,570 --> 00:39:56,330 lijst, dus als we proberen in te voegen n elementen, en we hebben 908 00:39:56,330 --> 00:39:58,050 hoeveel totaal emmers? 909 00:39:58,050 --> 00:40:03,450 Laten we zeggen 31 in totaal emmers in het geval van verjaardagen. 910 00:40:03,450 --> 00:40:09,240 Wat is de maximale lengte van een van deze ketens potentieel? 911 00:40:09,240 --> 00:40:12,670 >> Als er weer is 31 mogelijk verjaardagen in een bepaalde maand. 912 00:40:12,670 --> 00:40:14,580 En we zijn gewoon klonteren iedereen - 913 00:40:14,580 --> 00:40:15,580 dat is eigenlijk een stom voorbeeld. 914 00:40:15,580 --> 00:40:16,960 Laten we in plaats daarvan 26. 915 00:40:16,960 --> 00:40:20,890 Dus als daadwerkelijk mensen wier namen beginnen met A tot Z, waardoor aan 916 00:40:20,890 --> 00:40:22,780 ons 26 mogelijkheden. 917 00:40:22,780 --> 00:40:25,920 En we zijn met behulp van een datastructuur als degene die we net zagen, waarbij we 918 00:40:25,920 --> 00:40:30,210 een array van pointers, die elk wijst op een gelinkte lijst waar de 919 00:40:30,210 --> 00:40:32,360 eerste lijst is iedereen de naam Alice. 920 00:40:32,360 --> 00:40:35,770 De tweede lijst is elke met de naam beginnend met A, beginnend 921 00:40:35,770 --> 00:40:36,980 met B, enzovoort. 922 00:40:36,980 --> 00:40:41,020 >> Wat de waarschijnlijke duur van elk van deze lijsten als we aannemen een mooie schone 923 00:40:41,020 --> 00:40:45,410 verdeling van de namen van A tot Z over de gehele datastructuur? 924 00:40:45,410 --> 00:40:50,210 Er is n mensen in de datastructuur gedeeld door 26, als ze mooi 925 00:40:50,210 --> 00:40:52,110 verspreid over het gehele gegevensstructuur. 926 00:40:52,110 --> 00:40:54,970 Zodat de lengte van elk van deze ketens is n gedeeld door 26. 927 00:40:54,970 --> 00:40:57,380 Maar in grote O notatie, wat is dat? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Wat is dat eigenlijk? 930 00:41:02,440 --> 00:41:04,150 Dus het is eigenlijk gewoon n, toch? 931 00:41:04,150 --> 00:41:06,620 Want we hebben in het verleden gezegd, dat ugh je delen door 26. 932 00:41:06,620 --> 00:41:08,710 Ja, in werkelijkheid sneller. 933 00:41:08,710 --> 00:41:12,720 Maar in theorie, het is niet fundamenteel alles sneller. 934 00:41:12,720 --> 00:41:16,040 >> Zodat we niet lijken te zijn dat alles veel dichter bij deze heilige graal. 935 00:41:16,040 --> 00:41:17,750 In feite is dit slechts lineaire tijd. 936 00:41:17,750 --> 00:41:20,790 Heck, op dit punt, waarom doen we niet gewoon gebruik maken van een enorme gelinkte lijst? 937 00:41:20,790 --> 00:41:23,510 Waarom gaan we niet gewoon gebruik maken van een enorme array om de namen van opgeslagen 938 00:41:23,510 --> 00:41:25,010 iedereen in de kamer? 939 00:41:25,010 --> 00:41:28,280 Nou, is er nog steeds iets meeslepend over een hash table? 940 00:41:28,280 --> 00:41:30,810 Is er nog iets dwingende over een gegevensstructuur 941 00:41:30,810 --> 00:41:33,940 dat ziet er zo uit? 942 00:41:33,940 --> 00:41:35,182 Dit. 943 00:41:35,182 --> 00:41:37,050 >> STUDENT: [onverstaanbaar]. 944 00:41:37,050 --> 00:41:39,840 >> LUIDSPREKER 1: Recht, en opnieuw is het maar een lineaire tijd algoritme en een 945 00:41:39,840 --> 00:41:42,780 lineaire tijd datastructuur, waarom doe ik niet gewoon opslaan ieders naam in een grote 946 00:41:42,780 --> 00:41:44,210 array of in een grote gelinkte lijst? 947 00:41:44,210 --> 00:41:47,010 En stoppen met het maken van CS zo veel moeilijker dan het moet zijn? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Wat is meeslepend over dit, zelfs hoewel ik krabde het uit? 950 00:41:53,190 --> 00:41:54,930 >> STUDENT: [onverstaanbaar]. 951 00:41:54,930 --> 00:41:57,040 >> LUIDSPREKER 1: Inlagen zijn niet? 952 00:41:57,040 --> 00:41:58,140 Duur meer. 953 00:41:58,140 --> 00:42:03,390 Dus inserties potentieel kon nog zijn constante tijd, zelfs als uw gegevens 954 00:42:03,390 --> 00:42:07,910 structuur ziet er zo uit, een array van pointers, die elk goed op 955 00:42:07,910 --> 00:42:09,550 potentieel een gelinkte lijst. 956 00:42:09,550 --> 00:42:15,220 Hoe kon je constant bereiken tijd inbrengen van namen? 957 00:42:15,220 --> 00:42:16,280 Plak deze op de voorkant, toch? 958 00:42:16,280 --> 00:42:19,290 >> Als we offeren een ontwerp doelpunt van eerder, waar we wilden houden 959 00:42:19,290 --> 00:42:22,650 ieders naam, bijvoorbeeld, gesorteerd, of alle nummers op het podium gesorteerd, 960 00:42:22,650 --> 00:42:25,020 Stel dat we een ongesorteerde gelinkte lijst. 961 00:42:25,020 --> 00:42:29,960 Het kost ons slechts een of twee stappen, zoals in het geval van Ben en Brian 962 00:42:29,960 --> 00:42:32,750 eerder een element voegen op het begin van de lijst. 963 00:42:32,750 --> 00:42:36,090 Dus als we niet de zorg over het sorteren van alle van de namen die beginnen met A of alle 964 00:42:36,090 --> 00:42:39,660 de namen die beginnen met B, kunnen we nog steeds bereiken constante tijd invoegen. 965 00:42:39,660 --> 00:42:43,900 Nu het opzoeken van Alice of Bob of naam Meer in het algemeen is nog wat? 966 00:42:43,900 --> 00:42:48,100 Het is groot O van n gedeeld door 26, in de ideale geval waar iedereen is gelijkmatig 967 00:42:48,100 --> 00:42:51,190 verdeeld, waar er zo veel A's aangezien er Z, die waarschijnlijk 968 00:42:51,190 --> 00:42:52,220 onrealistisch. 969 00:42:52,220 --> 00:42:53,880 Maar dat is nog steeds lineair. 970 00:42:53,880 --> 00:42:57,120 >> Maar hier komen we terug naar het punt van asymptotische notatie 971 00:42:57,120 --> 00:42:58,600 theoretisch waar. 972 00:42:58,600 --> 00:43:02,960 Maar in de echte wereld, als ik beweer dat mijn programma kan iets 26 keer doen 973 00:43:02,960 --> 00:43:06,210 sneller dan de jouwe, waarvan het programma ga je liever met behulp van? 974 00:43:06,210 --> 00:43:09,660 Jou of van mij, die is 26 keer sneller? 975 00:43:09,660 --> 00:43:14,320 Realistisch, de persoon van wie is 26 keer sneller, zelfs als theoretisch 976 00:43:14,320 --> 00:43:18,790 onze algoritmes draaien in dezelfde asymptotische looptijd. 977 00:43:18,790 --> 00:43:20,940 >> Laat ik een ander voorstel oplossing voor het geheel. 978 00:43:20,940 --> 00:43:24,380 En als dit niet blow your mind, we uit datastructuren. 979 00:43:24,380 --> 00:43:27,420 Dit is het dus een Trie - 980 00:43:27,420 --> 00:43:28,520 soort van een domme naam. 981 00:43:28,520 --> 00:43:32,880 Het komt van opvragingen, en het woord gespeld trie, t-r-i-e, door 982 00:43:32,880 --> 00:43:34,450 Natuurlijk retrieval klinkt als trie. 983 00:43:34,450 --> 00:43:36,580 Maar dat is de geschiedenis van het woord Trie. 984 00:43:36,580 --> 00:43:40,980 >> Dus een Trie is inderdaad een soort van boom, en het is ook een spel op dat woord. 985 00:43:40,980 --> 00:43:46,330 En ook al kun je niet helemaal zien deze visualisatie, een trie een 986 00:43:46,330 --> 00:43:50,790 boom structuur, zoals een stamboom met een voorouder aan de bovenkant en kavels 987 00:43:50,790 --> 00:43:54,530 van de kleinkinderen en de achterkleinkinderen als bladeren op de bodem. 988 00:43:54,530 --> 00:43:58,100 Maar elk knooppunt in een trie een array. 989 00:43:58,100 --> 00:44:00,680 En het is in een array - en laten we vereenvoudig voor een moment - het is een 990 00:44:00,680 --> 00:44:04,600 array, in dit geval, van maat 26, waar elk knooppunt opnieuw is een array van grootte 991 00:44:04,600 --> 00:44:09,000 26, waarbij de nulde element dat matrix vertegenwoordigt A, en de laatste 992 00:44:09,000 --> 00:44:11,810 element in elk van deze matrix vertegenwoordigt Z. 993 00:44:11,810 --> 00:44:15,520 >> Dus stel ik voor, dan, dat deze gegevens structuur, bekend als trie, kan 994 00:44:15,520 --> 00:44:17,600 ook gebruikt om woorden te slaan. 995 00:44:17,600 --> 00:44:21,740 We zagen een moment geleden hoe we kunnen opslaan woorden, of in dit geval namen en we 996 00:44:21,740 --> 00:44:25,440 zagen eerder hoe we getallen kunnen opslaan, maar als we ons richten op namen of strings 997 00:44:25,440 --> 00:44:27,460 Hier, op wat is interessant. 998 00:44:27,460 --> 00:44:32,210 Ik eis dat de naam Maxwell is binnenkant van deze gegevensstructuur. 999 00:44:32,210 --> 00:44:33,730 Waar zie je Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> STUDENT: [onverstaanbaar]. 1001 00:44:35,140 --> 00:44:36,240 >> LUIDSPREKER 1: Aan de linkerkant. 1002 00:44:36,240 --> 00:44:39,910 Dus wat is interessant met deze gegevens structuur is eerder dan de winkel 1003 00:44:39,910 --> 00:44:46,200 snaar M-A-X-W-E-L-L backslash nul all aaneengesloten, wat je doen in plaats 1004 00:44:46,200 --> 00:44:46,890 volgt. 1005 00:44:46,890 --> 00:44:50,510 Als dit een Trie als datastructuur, waarvan elk knooppunten weer een matrix, 1006 00:44:50,510 --> 00:44:54,650 en u wilt opslaan Maxwell, moet u eerst index en dus de wortel van de knoop, zodat 1007 00:44:54,650 --> 00:44:57,810 te spreken, de bovenste knoop, op locatie M, rechts, dus 1008 00:44:57,810 --> 00:44:59,160 ruwweg in het midden. 1009 00:44:59,160 --> 00:45:03,740 En dan vanaf daar volgt u een pointer naar een onderliggende knooppunten, om zo te zeggen. 1010 00:45:03,740 --> 00:45:06,150 Dus in de stamboom zin, je volgen naar beneden. 1011 00:45:06,150 --> 00:45:09,030 En die u leiden naar een ander knooppunt aan de linkerkant, die 1012 00:45:09,030 --> 00:45:10,540 gewoon een andere array. 1013 00:45:10,540 --> 00:45:14,710 >> En dan als je wilt opslaan Maxwell, u de aanwijzer die aangeeft vinden 1014 00:45:14,710 --> 00:45:16,430 A, dat deze hier. 1015 00:45:16,430 --> 00:45:17,840 Dan ga je naar het volgende knooppunt. 1016 00:45:17,840 --> 00:45:20,100 En merk - dit is de reden waarom de foto's een beetje misleidend - 1017 00:45:20,100 --> 00:45:21,990 dit knooppunt kijken super klein. 1018 00:45:21,990 --> 00:45:26,050 Maar rechts van dit Y en Z. Het is gewoon de auteur heeft afgekapt de 1019 00:45:26,050 --> 00:45:27,630 foto, zodat u eigenlijk dingen zien. 1020 00:45:27,630 --> 00:45:30,400 Anders deze foto enorm groot zou zijn. 1021 00:45:30,400 --> 00:45:36,180 Dus nu index in locatie X, dan W, dan E, dan L, dan L. Wat is er dan 1022 00:45:36,180 --> 00:45:37,380 deze nieuwsgierigheid? 1023 00:45:37,380 --> 00:45:41,250 >> Nou, als we met behulp van dit soort nieuwe nemen over hoe je een string op te slaan in een 1024 00:45:41,250 --> 00:45:44,500 datastructuur, moet je nog steeds wezen afvinken in de data 1025 00:45:44,500 --> 00:45:47,250 structuur die een woord eindigt hier. 1026 00:45:47,250 --> 00:45:50,830 Met andere woorden, elk van deze knooppunten een of andere manier heeft om te onthouden dat wij 1027 00:45:50,830 --> 00:45:53,500 eigenlijk volgde al deze pointers en worden een beetje verlaten 1028 00:45:53,500 --> 00:45:58,370 broodkruim op de bodem hier van deze structuur M-A-X-W-E-L-L is aangegeven 1029 00:45:58,370 --> 00:46:00,230 inderdaad in deze datastructuur. 1030 00:46:00,230 --> 00:46:02,040 >> Dus we kunnen dit als volgt doen. 1031 00:46:02,040 --> 00:46:06,810 Elk van de knooppunten in het beeld dat we gewoon zaag heeft een, een array van maat 27. 1032 00:46:06,810 --> 00:46:10,550 En het is nu 27, want in p set zes, we eigenlijk geven u een apostrof, 1033 00:46:10,550 --> 00:46:13,590 dus kunnen we namen als O'Reilly hebben en anderen met een apostrof. 1034 00:46:13,590 --> 00:46:14,820 Maar hetzelfde idee. 1035 00:46:14,820 --> 00:46:17,710 Elk van deze elementen in de matrix wijst naar een struct 1036 00:46:17,710 --> 00:46:19,320 knooppunt, dus gewoon een knooppunt. 1037 00:46:19,320 --> 00:46:21,430 Dit is zo erg aan denken van onze gelinkte lijst. 1038 00:46:21,430 --> 00:46:24,550 >> En dan heb ik een Boole, die ik zal bel woord, dat is gewoon gaat worden 1039 00:46:24,550 --> 00:46:29,120 waar als een woord geëindigd is knoop in de boom. 1040 00:46:29,120 --> 00:46:32,870 Het vertegenwoordigt in feite de kleine driehoek zagen we een moment geleden. 1041 00:46:32,870 --> 00:46:37,190 Als een woord eindigt op dat knooppunt in de boom, zal dat woord veld waar te zijn, 1042 00:46:37,190 --> 00:46:41,990 die conceptueel is controle uit, of we trekken deze driehoek, ja er 1043 00:46:41,990 --> 00:46:44,080 is een woord hier. 1044 00:46:44,080 --> 00:46:45,120 >> Dus dit is een Trie. 1045 00:46:45,120 --> 00:46:48,540 En nu is de vraag, wat wordt de lopende tijd? 1046 00:46:48,540 --> 00:46:49,930 Is het grote O van n? 1047 00:46:49,930 --> 00:46:51,410 Is het iets anders? 1048 00:46:51,410 --> 00:46:57,330 Nou, als je namen hebt n in deze data structuur, Maxwell is slechts een van de 1049 00:46:57,330 --> 00:47:02,330 hen, wat is de looptijd van de het plaatsen of het vinden van Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Wat is de looptijd invoegen van Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Als er n andere namen reeds in de tabel? 1053 00:47:11,740 --> 00:47:12,507 Yeah? 1054 00:47:12,507 --> 00:47:15,429 >> STUDENT: [onverstaanbaar]. 1055 00:47:15,429 --> 00:47:17,550 >> LUIDSPREKER 1: Ja, het is de lengte van de naam, toch? 1056 00:47:17,550 --> 00:47:24,420 Dus M-a-x-w-e-l-l, zodat het voelt alsof deze algoritme is big O van zeven. 1057 00:47:24,420 --> 00:47:26,580 Nu, natuurlijk, de naam variëren in lengte. 1058 00:47:26,580 --> 00:47:27,380 Misschien is het een korte naam. 1059 00:47:27,380 --> 00:47:28,600 Misschien is het een langere naam. 1060 00:47:28,600 --> 00:47:33,390 Maar wat is sleutel hier is dat Het is een constant getal. 1061 00:47:33,390 --> 00:47:36,810 En misschien is het niet echt constant, maar god, zo realistisch, in een 1062 00:47:36,810 --> 00:47:41,570 woordenboek, is er waarschijnlijk een bepaalde grens het aantal letters in een 1063 00:47:41,570 --> 00:47:43,820 naam van de persoon in een bepaald land. 1064 00:47:43,820 --> 00:47:46,940 >> En dus kunnen we ervan uitgaan dat waarde is een constante. 1065 00:47:46,940 --> 00:47:47,750 Ik weet niet wat het is. 1066 00:47:47,750 --> 00:47:50,440 Het is waarschijnlijk groter dan we denken dat het is. 1067 00:47:50,440 --> 00:47:52,720 Want er is altijd wel een hoekje geval met een gekke lange naam. 1068 00:47:52,720 --> 00:47:56,360 Dus laten we het noemen k, maar het is nog steeds een constante vermoedelijk, omdat elke 1069 00:47:56,360 --> 00:48:00,190 naam in de wereld, ten minste een bepaald land, is dat de lengte of 1070 00:48:00,190 --> 00:48:01,780 korter, dus het is constant. 1071 00:48:01,780 --> 00:48:04,490 Maar toen we zeiden iets is groot O van een constante waarde, wat is dat 1072 00:48:04,490 --> 00:48:07,760 echt gelijk aan? 1073 00:48:07,760 --> 00:48:10,420 Dat is echt hetzelfde zoals zeggend constante tijd. 1074 00:48:10,420 --> 00:48:11,530 >> Nu zijn we soort van vals spelen, toch? 1075 00:48:11,530 --> 00:48:15,340 We zijn soort hefboomwerking een theorie hier om te zeggen dat goed, volgorde van de k 1076 00:48:15,340 --> 00:48:17,450 eigenlijk gewoon bestellen van een, en het is een constante tijd. 1077 00:48:17,450 --> 00:48:18,200 Maar het is echt. 1078 00:48:18,200 --> 00:48:22,550 Omdat het belangrijk inzicht is dat Als we namen n al deze 1079 00:48:22,550 --> 00:48:26,010 datastructuur, en we insert Maxwell, is de hoeveelheid tijd die ons 1080 00:48:26,010 --> 00:48:29,530 Steek Maxwell bij alle getroffen door hoeveel andere mensen 1081 00:48:29,530 --> 00:48:31,100 zijn in de datastructuur? 1082 00:48:31,100 --> 00:48:31,670 Lijkt niet te zijn. 1083 00:48:31,670 --> 00:48:36,280 Als ik een miljard meer elementen van deze trie, en steek vervolgens Maxwell, wordt 1084 00:48:36,280 --> 00:48:38,650 hij helemaal aangetast? 1085 00:48:38,650 --> 00:48:39,050 Nee. 1086 00:48:39,050 --> 00:48:42,950 En dat is in tegenstelling tot alle van de dag gegevens structuren die we tot nu toe heb gezien, waar 1087 00:48:42,950 --> 00:48:46,820 de looptijd van je algoritme is volledig onafhankelijk van hoeveel 1088 00:48:46,820 --> 00:48:51,430 spul is of nog niet is dat gegevensstructuur. 1089 00:48:51,430 --> 00:48:54,650 >> En dus met dit biedt u nu een gelegenheid voor p set van zes, die zal 1090 00:48:54,650 --> 00:48:58,310 weer betrekken de uitvoering van uw eigen spellingcontrole, het lezen van de 150.000 1091 00:48:58,310 --> 00:49:01,050 woorden, de beste manier om te slaan dat niet noodzakelijkerwijs duidelijk. 1092 00:49:01,050 --> 00:49:04,030 En al heb ik streefde te vinden de heilige graal, doe ik niet 1093 00:49:04,030 --> 00:49:05,330 beweren dat een Trie is. 1094 00:49:05,330 --> 00:49:09,810 In feite, een hash table kan heel goed blijken veel efficiënter. 1095 00:49:09,810 --> 00:49:10,830 Maar dat zijn slechts - 1096 00:49:10,830 --> 00:49:14,620 dat is slechts een van de ontwerpbeslissingen je zal moeten maken. 1097 00:49:14,620 --> 00:49:18,920 >> Maar in het sluiten laten we eens 50 of zo seconden om een ​​blik op wat ons te nemen 1098 00:49:18,920 --> 00:49:22,190 vooruit volgende week en verder we de overgang uit deze command line 1099 00:49:22,190 --> 00:49:26,220 wereld als C-programma's om dingen web gebaseerd en talen zoals PHP en 1100 00:49:26,220 --> 00:49:30,350 JavaScript en het internet zelf, protocollen zoals HTTP, wat je hebt 1101 00:49:30,350 --> 00:49:32,870 vanzelfsprekend voor de jaren nu, en typte elkste 1102 00:49:32,870 --> 00:49:34,440 dag, misschien, of gezien. 1103 00:49:34,440 --> 00:49:37,420 En we beginnen te schillen terug de lagen van wat het internet. 1104 00:49:37,420 --> 00:49:40,650 En wat is de code die ligt ten grondslag aan de huidige instrumenten. 1105 00:49:40,650 --> 00:49:43,230 Dus 50 seconden van deze teaser hier. 1106 00:49:43,230 --> 00:49:46,570 Ik geef u Strijders van het Net. 1107 00:49:46,570 --> 00:49:51,370 >> [VIDEO AFSPELEN] 1108 00:49:51,370 --> 00:49:56,764 >> -Hij kwam met een boodschap. 1109 00:49:56,764 --> 00:50:00,687 Met een protocol dat al zijn eigen. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Hij kwam tot een wereld van wrede firewalls, onverschillig routers, en gevaren ver 1112 00:50:19,780 --> 00:50:22,600 erger dan de dood. 1113 00:50:22,600 --> 00:50:23,590 Hij is snel. 1114 00:50:23,590 --> 00:50:25,300 Hij is sterk. 1115 00:50:25,300 --> 00:50:27,700 Hij is TCPIP. 1116 00:50:27,700 --> 00:50:30,420 En hij heeft uw adres. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Krijgers van het Net. 1119 00:50:34,590 --> 00:50:35,290 >> [END VIDEO AFSPELEN] 1120 00:50:35,290 --> 00:50:38,070 >> LUIDSPREKER 1: Dat is hoe het internet Zij werken vanaf volgende week. 1121 00:50:38,070 --> 00:50:40,406