1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [REPRODUCCIÓ DE MÚSICA] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 ALTAVEU 1: D'acord. 5 00:00:12,900 --> 00:00:14,600 Tothom la benvinguda de nou a la secció. 6 00:00:14,600 --> 00:00:18,660 Espero que tots vostès estiguin amb èxit recuperat de la seva concurs 7 00:00:18,660 --> 00:00:19,510 des de la setmana passada. 8 00:00:19,510 --> 00:00:22,564 Sé que és una mica boig de vegades. 9 00:00:22,564 --> 00:00:25,230 Com deia abans, si estàs dins de la desviació estàndard, 10 00:00:25,230 --> 00:00:28,188 realment no et preocupis per això, sobretot per a una secció menys còmode. 11 00:00:28,188 --> 00:00:30,230 Això és on ha d'estar. 12 00:00:30,230 --> 00:00:32,850 >> Si ho va fer molt bé, llavors impressionant. 13 00:00:32,850 --> 00:00:33,650 Felicitacions a vostè. 14 00:00:33,650 --> 00:00:36,149 I si vostè sent que necessita una mica més d'ajuda, si us plau 15 00:00:36,149 --> 00:00:38,140 no dubti a arribar a qualsevol dels TFS. 16 00:00:38,140 --> 00:00:40,030 Tots estem aquí per ajudar. 17 00:00:40,030 --> 00:00:40,960 >> És per això que ensenyem. 18 00:00:40,960 --> 00:00:44,550 És per això que sóc aquí tots els dilluns per a vostè nois i en l'oficina hores els dijous. 19 00:00:44,550 --> 00:00:48,130 Així que si us plau no dubti en fer-m'ho saber si vostè està preocupat sobre qualsevol cosa 20 00:00:48,130 --> 00:00:52,450 o si hi ha alguna cosa en el concurs que realment t'agradaria abordar. 21 00:00:52,450 --> 00:00:56,940 >> Així que l'ordre del dia d'avui és tot sobre les estructures de dades. 22 00:00:56,940 --> 00:01:01,520 Alguns d'aquests són només serà just per ajudar a familiaritzar-se amb elles. 23 00:01:01,520 --> 00:01:04,870 Alguna vegada no pot aplicar en aquesta classe. 24 00:01:04,870 --> 00:01:08,690 Alguns d'ells es vol, com per a la seva conjunt de processadors ortografia. 25 00:01:08,690 --> 00:01:11,380 >> Vostè té la seva opció entre taules hash i tries. 26 00:01:11,380 --> 00:01:13,680 Així que sens dubte ens anem sobre aquells. 27 00:01:13,680 --> 00:01:18,690 Serà, sens dubte més de classe d'una secció d'alt nivell avui en dia, però, 28 00:01:18,690 --> 00:01:22,630 perquè hi ha una gran quantitat d'ells, i si entrem en els detalls d'implementació 29 00:01:22,630 --> 00:01:26,490 en tots ells, que no ho faria fins i tot aconseguir a través de les llistes enllaçades 30 00:01:26,490 --> 00:01:28,520 i potser una mica de taules hash. 31 00:01:28,520 --> 00:01:31,200 >> Així que tinguin paciència amb mi. 32 00:01:31,200 --> 00:01:33,530 No estarem fent tant de codificació d'aquest temps. 33 00:01:33,530 --> 00:01:36,870 Si vostè té alguna pregunta sobre ella o desitja veure-ho en pràctica 34 00:01:36,870 --> 00:01:39,260 o provar per tu mateix, Sens dubte, recomano 35 00:01:39,260 --> 00:01:44,250 anar a study.cs50.net, que té exemples de tots aquests. 36 00:01:44,250 --> 00:01:46,400 Tindrà les meves presentacions en PowerPoint amb les notes que ens 37 00:01:46,400 --> 00:01:50,860 tendeixen a utilitzar, així com una mica de programació exercicis, sobretot per a les coses 38 00:01:50,860 --> 00:01:55,250 com llistes enllaçades i binari arbres piles i senyals. 39 00:01:55,250 --> 00:01:59,590 Tan poc nivell més alt, el que podria ser bo per a vostès. 40 00:01:59,590 --> 00:02:01,320 >> Així que amb això, anem a començar. 41 00:02:01,320 --> 00:02:03,060 I també, concursos sí-. 42 00:02:03,060 --> 00:02:06,550 Crec que la majoria de vostès que estan en la meva secció té les seves proves, 43 00:02:06,550 --> 00:02:12,060 però ningú ve a o alguna raó vostè no fer-ho, són aquí mateix a la part davantera. 44 00:02:12,060 --> 00:02:12,740 >> Així vinculat llistes. 45 00:02:12,740 --> 00:02:15,650 Sé que aquest tipus de va abans de fer una còpia del seu qüestionari. 46 00:02:15,650 --> 00:02:17,940 Això va ser la setmana anterior que ens assabentem d'això. 47 00:02:17,940 --> 00:02:21,040 Però en aquest cas, només haurem de anar una mica més en profunditat. 48 00:02:21,040 --> 00:02:25,900 >> Llavors per què podríem triar un llista enllaçada a través d'una matriu? 49 00:02:25,900 --> 00:02:27,130 Què els distingeix? 50 00:02:27,130 --> 00:02:27,630 Sí? 51 00:02:27,630 --> 00:02:30,464 >> AUDIÈNCIA: Vostè pot ampliar una vinculada llistar versus grandària fixa d'una matriu. 52 00:02:30,464 --> 00:02:31,171 ALTAVEU 1: Dret. 53 00:02:31,171 --> 00:02:33,970 Una matriu ha fixat mida mentre que una llista enllaçada té una mida variable. 54 00:02:33,970 --> 00:02:36,970 Així que si no sabem com molt que volem emmagatzemar, 55 00:02:36,970 --> 00:02:39,880 una llista enllaçada ens dóna una gran manera de fer això perquè podem simplement 56 00:02:39,880 --> 00:02:43,730 afegir en un altre node i afegir en un altre node i afegir en un altre node. 57 00:02:43,730 --> 00:02:45,750 Però el que podria ser una solució de compromís? 58 00:02:45,750 --> 00:02:49,521 Algú recorda el trade-off entre matrius i llistes enllaçades? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> AUDIÈNCIA: Vostè ha de anar a través de tot el camí 61 00:02:51,460 --> 00:02:53,738 a través de la llista enllaçada trobar un element en una llista. 62 00:02:53,738 --> 00:02:55,570 En una matriu, es pot simplement trobar un element. 63 00:02:55,570 --> 00:02:56,278 >> ALTAVEU 1: Dret. 64 00:02:56,278 --> 00:02:57,120 Així que amb arrays-- 65 00:02:57,120 --> 00:02:58,500 >> AUDIÈNCIA: [inaudible]. 66 00:02:58,500 --> 00:03:01,090 >> ALTAVEU 1: Amb els arranjaments, tenim el que s'anomena accés aleatori. 67 00:03:01,090 --> 00:03:04,820 Significa que si volem el que és mai el cinquè punt de la llista 68 00:03:04,820 --> 00:03:07,230 o el cinquè punt de la nostra matriu, que només pot agafar. 69 00:03:07,230 --> 00:03:10,440 Si es tracta d'una llista enllaçada, tenim per recórrer, no? 70 00:03:10,440 --> 00:03:14,020 Així que l'accés a un element en una matriu és la constant de temps, 71 00:03:14,020 --> 00:03:19,530 mentre que amb una llista enllaçada que ho faria més probable és que el temps lineal perquè potser 72 00:03:19,530 --> 00:03:21,370 el nostre element és tot el camí al final. 73 00:03:21,370 --> 00:03:23,446 Hem de buscar a través de tot. 74 00:03:23,446 --> 00:03:25,320 Així, amb totes aquestes dades estructures que anem 75 00:03:25,320 --> 00:03:29,330 a passar una mica més de temps en, ¿Quins són els punts positius i negatius. 76 00:03:29,330 --> 00:03:31,480 Quan podríem voler utilitzar un sobre l'altre? 77 00:03:31,480 --> 00:03:34,970 I això és una cosa de la El més gran per emportar. 78 00:03:34,970 --> 00:03:40,140 >> Així que tenim aquí la definició d'un node. 79 00:03:40,140 --> 00:03:43,040 És com un dels elements la nostra llista enllaçada, oi? 80 00:03:43,040 --> 00:03:46,180 Així que estem tots familiaritzats amb les nostres estructures typedef, 81 00:03:46,180 --> 00:03:47,980 que ens vam anar a la revisió última vegada. 82 00:03:47,980 --> 00:03:53,180 Era bàsicament la creació de un altre tipus de dades que podríem utilitzar. 83 00:03:53,180 --> 00:03:57,930 >> I en aquest cas, és algun node que se celebrarà en algun sencer. 84 00:03:57,930 --> 00:04:00,210 I llavors quina és la segona part aquí? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Qualsevol persona? 87 00:04:05,677 --> 00:04:06,680 >> AUDIÈNCIA: [inaudible]. 88 00:04:06,680 --> 00:04:07,020 >> ALTAVEU 1: Sí. 89 00:04:07,020 --> 00:04:08,400 És un punter al següent node. 90 00:04:08,400 --> 00:04:12,610 Així que això es deu en realitat ser aquí dalt. 91 00:04:12,610 --> 00:04:18,790 Això és un punter del tipus de node a la següent cosa. 92 00:04:18,790 --> 00:04:22,410 I això és el que abasta la nostra node. 93 00:04:22,410 --> 00:04:24,060 Refredar. 94 00:04:24,060 --> 00:04:29,390 >> Molt bé, així que amb la recerca, ja que estàvem només dir abans de la mà, si estàs 95 00:04:29,390 --> 00:04:31,840 anar a cercar a través de, vostè ha de repetir en realitat 96 00:04:31,840 --> 00:04:33,660 a través de la seva llista enllaçada. 97 00:04:33,660 --> 00:04:38,530 Així que si estem buscant el nombre 9, començaríem al nostre cap 98 00:04:38,530 --> 00:04:41,520 i que ens assenyala al principi de la nostra llista enllaçada, oi? 99 00:04:41,520 --> 00:04:44,600 I diem, bé, ho fa node conté el número 9? 100 00:04:44,600 --> 00:04:45,690 No? 101 00:04:45,690 --> 00:04:47,500 >> Molt bé, aneu a la següent. 102 00:04:47,500 --> 00:04:48,312 Segueix-lo. 103 00:04:48,312 --> 00:04:49,520 Conté el número 9? 104 00:04:49,520 --> 00:04:50,570 No 105 00:04:50,570 --> 00:04:51,550 Seguiu el següent. 106 00:04:51,550 --> 00:04:55,490 >> Així que hem de recórrer en realitat a través de la nostra llista enllaçada. 107 00:04:55,490 --> 00:05:00,070 No podem anar directament a on 9 és. 108 00:05:00,070 --> 00:05:05,860 I si vostès realment vol veure alguns pseudo-codi allà dalt. 109 00:05:05,860 --> 00:05:10,420 Tenim alguna funció de cerca aquí que pren en-- què es necessita en? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Què en penses? 112 00:05:14,320 --> 00:05:15,960 Tan fàcil un. 113 00:05:15,960 --> 00:05:17,784 Què és això? 114 00:05:17,784 --> 00:05:18,700 AUDIÈNCIA: [inaudible]. 115 00:05:18,700 --> 00:05:20,366 ALTAVEU 1: El nombre que estem buscant. 116 00:05:20,366 --> 00:05:20,980 Dreta? 117 00:05:20,980 --> 00:05:22,875 I què seria el que correspondria a? 118 00:05:22,875 --> 00:05:25,020 És un punter a? 119 00:05:25,020 --> 00:05:26,000 >> AUDIÈNCIA: Un node. 120 00:05:26,000 --> 00:05:28,980 >> ALTAVEU 1: Un node a la llista que estem veient, no? 121 00:05:28,980 --> 00:05:33,700 Així que tenim alguns nodes són punter aquí. 122 00:05:33,700 --> 00:05:37,240 Aquest és un punt que va a realment recórrer la nostra llista. 123 00:05:37,240 --> 00:05:39,630 Ens vam proposar que potser a la llista perquè això és només 124 00:05:39,630 --> 00:05:44,380 establint que igual a la començar de la nostra llista enllaçada. 125 00:05:44,380 --> 00:05:50,660 >> I si bé no és NULL, mentre que encara tenim coses a la nostra llista, 126 00:05:50,660 --> 00:05:55,580 comprovar per veure si aquest node té el nombre que estem buscant. 127 00:05:55,580 --> 00:05:57,740 Retorna veritable. 128 00:05:57,740 --> 00:06:01,070 En cas contrari, actualitzar-la, no? 129 00:06:01,070 --> 00:06:04,870 >> Si és NULL, sortim de la nostra while i return false 130 00:06:04,870 --> 00:06:08,340 perquè això significa que no hem trobat. 131 00:06:08,340 --> 00:06:11,048 Tothom aconsegueix com funciona? 132 00:06:11,048 --> 00:06:11,548 Okay. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Així que amb la inserció, es tenir tres formes diferents. 135 00:06:20,260 --> 00:06:25,250 Pot anteposar, pot annexar i es pot inserir en assortiment. 136 00:06:25,250 --> 00:06:28,215 En aquest cas, estem farem un prefix. 137 00:06:28,215 --> 00:06:33,380 Algú sap com els tres casos poden ser diferents? 138 00:06:33,380 --> 00:06:36,920 >> Així que anteposar vol dir que es posa que a la part davantera de la seva llista. 139 00:06:36,920 --> 00:06:39,770 Així que això significaria que no importa el que el seu node és, no importa 140 00:06:39,770 --> 00:06:43,160 el que el valor és, vas per posar-lo aquí davant, d'acord? 141 00:06:43,160 --> 00:06:45,160 Serà la primera element en la seva llista. 142 00:06:45,160 --> 00:06:49,510 >> Si annexa que, va per anar a la part de darrere de la seva llista. 143 00:06:49,510 --> 00:06:54,010 I s'insereixen en assortiments vol dir que ets posarà realment al lloc 144 00:06:54,010 --> 00:06:57,700 on manté la seva llista enllaçada ordenada. 145 00:06:57,700 --> 00:07:00,810 Una vegada més, com s'utilitza aquests i quan s'utilitza 146 00:07:00,810 --> 00:07:02,530 ells variaran depenent del seu cas. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Si no necessita ser ordenats, posi per davant tendeix 149 00:07:07,750 --> 00:07:10,460 a ser el que la majoria de la gent utilitzar perquè no ho fa 150 00:07:10,460 --> 00:07:15,680 haver de passar per tota la llista per trobar al final per afegir a, oi? 151 00:07:15,680 --> 00:07:17,720 Vostè només pot enganxar-lo directament. 152 00:07:17,720 --> 00:07:21,930 >> Així que anem a anar a través d'un inserció 1 en aquest moment. 153 00:07:21,930 --> 00:07:26,360 Així que una cosa que vaig a Recomano altament a aquest conjunt de processadors 154 00:07:26,360 --> 00:07:29,820 és dibuixar les coses, com sempre. 155 00:07:29,820 --> 00:07:35,130 És molt important actualitzar seus punters en l'ordre correcte 156 00:07:35,130 --> 00:07:38,620 perquè si ells actualitzar una mica fora de lloc, 157 00:07:38,620 --> 00:07:42,210 vostè va a acabar perdre parts de la seva llista. 158 00:07:42,210 --> 00:07:49,680 >> Així, per exemple, en aquest cas, estem comptant el cap a punt just a 1. 159 00:07:49,680 --> 00:07:56,070 Si només fem sense guardar aquest 1, 160 00:07:56,070 --> 00:07:58,570 no tenim idea del que 1 ha d'apuntar a ara 161 00:07:58,570 --> 00:08:02,490 perquè hem perdut el que el cap va assenyalar. 162 00:08:02,490 --> 00:08:05,530 Així que una cosa que cal recordar quan estàs fent un prepend 163 00:08:05,530 --> 00:08:09,630 és salvar el que el punts del cap a la primera, 164 00:08:09,630 --> 00:08:15,210 a continuació, tornar a assignar, i després actualitzar qual cosa el seu nou node hauria d'apuntar. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 En aquest cas, aquesta és una manera de fer-ho. 167 00:08:22,560 --> 00:08:25,440 >> Així que si haguéssim fet així en el qual només reassignats cap, 168 00:08:25,440 --> 00:08:30,320 perdem bàsicament la nostra llista completa, no? 169 00:08:30,320 --> 00:08:38,000 Una manera de fer-ho és tenir un punt de següent i, a continuació, tenir el cap a punt 1. 170 00:08:38,000 --> 00:08:42,650 O vostè pot fer alguna cosa així com el l'emmagatzematge temporal, la qual vaig parlar sobre. 171 00:08:42,650 --> 00:08:45,670 >> Però la reassignació de la seva punters en l'ordre correcte 172 00:08:45,670 --> 00:08:48,750 serà molt, molt important per a aquest conjunt de processadors. 173 00:08:48,750 --> 00:08:53,140 En cas contrari, vostè va a tenir un hash taula o una oportunitat que només serà 174 00:08:53,140 --> 00:08:56,014 només una part de les paraules que volen i després you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 AUDIÈNCIA: Quin va ser el temporal El emmagatzematge que parlaves? 176 00:08:58,930 --> 00:09:00,305 ALTAVEU 1: L'emmagatzematge temporal. 177 00:09:00,305 --> 00:09:02,760 Així que, bàsicament, una altra manera vostè pot fer això 178 00:09:02,760 --> 00:09:07,650 es guardi el cap d'alguna cosa, com emmagatzemar la variable temporal. 179 00:09:07,650 --> 00:09:11,250 Assigneu a 1 i a continuació, actualitzeu 1 per assenyalar 180 00:09:11,250 --> 00:09:13,830 al que el cap utilitza per apuntar. 181 00:09:13,830 --> 00:09:16,920 D'aquesta manera és òbviament més elegant, ja que 182 00:09:16,920 --> 00:09:20,770 no necessiten un valor temporal, però només oferir una altra manera de fer-ho. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 I que en realitat tenen una mica de codi per això. 185 00:09:25,790 --> 00:09:28,080 Així, per llista enllaçada, ens en realitat tenen una mica de codi. 186 00:09:28,080 --> 00:09:31,930 Així que inserir aquí, això es anteposant. 187 00:09:31,930 --> 00:09:34,290 Així que això entra en ell al capdavant. 188 00:09:34,290 --> 00:09:38,820 >> Així que el primer, cal crear el seu nou node, per descomptat, 189 00:09:38,820 --> 00:09:40,790 i comprovi que no NULL. 190 00:09:40,790 --> 00:09:43,250 Sempre bo. 191 00:09:43,250 --> 00:09:47,840 I llavors vostè necessita per assignar els valors. 192 00:09:47,840 --> 00:09:51,260 Cada vegada que es crea un nou node, no saben el que està apuntant a la següent, 193 00:09:51,260 --> 00:09:54,560 pel que desitja inicialitzar a NULL. 194 00:09:54,560 --> 00:09:58,760 Si no acaben apuntant a alguna cosa una altra cosa, es va reassignar i que està bé. 195 00:09:58,760 --> 00:10:00,740 Si és el primer a la llista, que necessita 196 00:10:00,740 --> 00:10:04,270 per assenyalar a NULL perquè aquest és el final de la llista. 197 00:10:04,270 --> 00:10:12,410 >> Així que per inserir, veiem aquí s'assigna el següent valor del nostre node 198 00:10:12,410 --> 00:10:17,380 a ser el que és el cap, que és el que teníem aquí. 199 00:10:17,380 --> 00:10:19,930 Això és el que acabem de fer. 200 00:10:19,930 --> 00:10:25,820 I llavors estem assignant el cap a punt al nostre nou node, perquè recordi, 201 00:10:25,820 --> 00:10:31,090 cap nova punter a un node, i això és exactament el que és el cap. 202 00:10:31,090 --> 00:10:34,370 Això és exactament per això que tenir aquesta fletxa d'accés. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Fresc? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> AUDIÈNCIA: Hem de inicialitzar nou al costat de NULL en primer lloc, 207 00:10:41,100 --> 00:10:44,240 o podem simplement inicialitzar al capdavant? 208 00:10:44,240 --> 00:10:48,210 >> ALTAVEU 1: Nou propera necessita ser NULL per començar 209 00:10:48,210 --> 00:10:53,760 perquè vostè no sap on serà. 210 00:10:53,760 --> 00:10:56,100 A més, això és una espècie de De la mateixa manera que un paradigma. 211 00:10:56,100 --> 00:10:59,900 Es configura igual a NULL només per fer Assegureu-vos que totes les bases estan cobertes 212 00:10:59,900 --> 00:11:04,070 abans de fer qualsevol canvi de destinació de manera que vostè sempre té la garantia que així serà 213 00:11:04,070 --> 00:11:08,880 estar apuntant a un valor específic front com un valor de les escombraries. 214 00:11:08,880 --> 00:11:12,210 Perquè, sí, assignem nou següent de forma automàtica, 215 00:11:12,210 --> 00:11:15,420 però és més com un bona pràctica inicialitzar 216 00:11:15,420 --> 00:11:19,270 d'aquesta manera i després reassignar. 217 00:11:19,270 --> 00:11:23,420 >> OK, així doblement enllaçada llistes ara. 218 00:11:23,420 --> 00:11:24,601 Què pensem? 219 00:11:24,601 --> 00:11:26,350 El que és diferent amb doblement enllaçada llistes? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Així que a les nostres llistes enllaçades, podem només es mouen en una direcció, ¿no? 222 00:11:34,300 --> 00:11:35,270 Només tenim al costat. 223 00:11:35,270 --> 00:11:36,760 Només podem seguir endavant. 224 00:11:36,760 --> 00:11:40,300 >> Amb una llista doblement enllaçada, també podem moure cap enrere. 225 00:11:40,300 --> 00:11:44,810 Així que no només tenim la nombre que volem emmagatzemar, 226 00:11:44,810 --> 00:11:50,110 tenim on apunta la següent i en el qual només venim. 227 00:11:50,110 --> 00:11:52,865 Així que això permet alguns millor recorregut. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Així nodes doblement enllaçats, molt similar, no? 230 00:12:01,240 --> 00:12:05,000 L'única diferència és que ara tenir una banda i una anterior. 231 00:12:05,000 --> 00:12:06,235 És l'única diferència. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Així que si haguéssim de anteposar o append-- nosaltres no tenen cap codi per això aquí-- 234 00:12:14,790 --> 00:12:17,830 però si anés a tractar de inserir, l'important 235 00:12:17,830 --> 00:12:19,980 és el que necessita per fer assegurar-se que està assignant 236 00:12:19,980 --> 00:12:23,360 tant la seva anterior i el seu següent punter correctament. 237 00:12:23,360 --> 00:12:29,010 Així que en aquest cas, ho faria no només inicialitzar següent, 238 00:12:29,010 --> 00:12:31,820 inicialitzar anterior. 239 00:12:31,820 --> 00:12:36,960 Si estem al capdavant de la llista, no només fer que el cap igual nova, 240 00:12:36,960 --> 00:12:41,750 però deu el nostre nou anterior apuntar al capdavant, oi? 241 00:12:41,750 --> 00:12:43,380 >> Aquesta és l'única diferència. 242 00:12:43,380 --> 00:12:47,200 I si vols més pràctica amb aquests amb llistes enllaçades, amb inserció, 243 00:12:47,200 --> 00:12:49,900 amb la supressió, amb inserció en una llista d'assortiment, 244 00:12:49,900 --> 00:12:52,670 si us plau visiti study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Hi ha un munt de grans exercicis. 246 00:12:54,870 --> 00:12:55,870 El recomano. 247 00:12:55,870 --> 00:12:59,210 Tant de bo haguéssim tingut temps per anar a través d'ells però hi ha una gran quantitat d'estructures de dades 248 00:12:59,210 --> 00:13:01,530 aconseguir a través. 249 00:13:01,530 --> 00:13:02,650 >> Acceptar, de manera que les taules hash. 250 00:13:02,650 --> 00:13:07,070 Aquest és probablement el més poc útil per al conjunt de processadors 251 00:13:07,070 --> 00:13:11,090 aquí perquè vostè serà la implementació d'un d'aquests, o un intent. 252 00:13:11,090 --> 00:13:12,200 M'agrada molt les taules hash. 253 00:13:12,200 --> 00:13:13,110 Són bastant fresc. 254 00:13:13,110 --> 00:13:17,080 >> Així que, bàsicament, el que que passa és una taula hash 255 00:13:17,080 --> 00:13:22,050 és quan realment necessitem ràpida inserció, eliminació i recerca. 256 00:13:22,050 --> 00:13:25,010 Aquestes són les coses que estem prioritzant en una taula hash. 257 00:13:25,010 --> 00:13:29,500 Poden ser bastant gran, però com veurem amb tries, 258 00:13:29,500 --> 00:13:33,040 hi ha coses que són molt més grans. 259 00:13:33,040 --> 00:13:38,330 >> Però, bàsicament, tot un hash taula és una funció hash 260 00:13:38,330 --> 00:13:47,215 que et diu que cub per posar cadascun de les seves dades, cadascun dels seus elements a. 261 00:13:47,215 --> 00:13:51,140 Una manera simple de pensar en una taula hash és que és només cubs de coses, 262 00:13:51,140 --> 00:13:51,770 Oi? 263 00:13:51,770 --> 00:13:59,720 Així que quan vostè està ordenant les coses per com la primera lletra del seu nom, 264 00:13:59,720 --> 00:14:01,820 que és una cosa així com una taula hash. 265 00:14:01,820 --> 00:14:06,180 >> Així que si jo fos a grup de nois és en grups de tot el que de nom comença 266 00:14:06,180 --> 00:14:11,670 amb A per aquí, o qui sigui l'aniversari és al gener, febrer, març, 267 00:14:11,670 --> 00:14:15,220 el que sigui, que és efectivament la creació d'una taula hash. 268 00:14:15,220 --> 00:14:18,120 És només la creació de cubs que ordenar els elements en 269 00:14:18,120 --> 00:14:19,520 per tu per trobar més fàcil. 270 00:14:19,520 --> 00:14:22,300 Així d'aquesta manera quan necessito per trobar un de vosaltres, 271 00:14:22,300 --> 00:14:24,680 Jo no he de buscar a través de cada un dels seus noms. 272 00:14:24,680 --> 00:14:29,490 Jo puc ser com, oh, jo sé que L'aniversari de Danielle és en-- 273 00:14:29,490 --> 00:14:30,240 AUDIÈNCIA: --April. 274 00:14:30,240 --> 00:14:30,948 ALTAVEU 1: abril. 275 00:14:30,948 --> 00:14:33,120 Així que em veig en la meva abril cub, i amb una mica de sort, 276 00:14:33,120 --> 00:14:38,270 ella serà l'única en la que hi ha i el meu temps era constant en aquest sentit, 277 00:14:38,270 --> 00:14:41,230 mentre que si he de buscar a través d'un munt de gent, 278 00:14:41,230 --> 00:14:43,090 que prendrà molt més temps. 279 00:14:43,090 --> 00:14:45,830 Així taules hash són realment només cubs. 280 00:14:45,830 --> 00:14:48,630 Una manera senzilla de pensar-hi. 281 00:14:48,630 --> 00:14:52,930 >> Així que una cosa molt important sobre una taula hash és una funció hash. 282 00:14:52,930 --> 00:14:58,140 Així que les coses que acabo de parlar, igual que la seva primera lletra del seu nom 283 00:14:58,140 --> 00:15:01,450 o el seu mes d'aniversari, aquestes són idees que 284 00:15:01,450 --> 00:15:03,070 realment correlacionar a una funció hash. 285 00:15:03,070 --> 00:15:08,900 És només una manera de decidir quina vostè debades és EL element entra en, d'acord? 286 00:15:08,900 --> 00:15:14,850 Així que per a aquest conjunt de processadors, pot mirar cap amunt gairebé qualsevol funció hash que desitja. 287 00:15:14,850 --> 00:15:16,030 >> No ha de ser la seva. 288 00:15:16,030 --> 00:15:21,140 Hi ha alguns realment fresc fora cal fer tot tipus de boig matemàtiques. 289 00:15:21,140 --> 00:15:25,170 I si vol fer la seva corrector ortogràfic súper ràpid, 290 00:15:25,170 --> 00:15:27,620 Sens dubte, mirar un d'aquests. 291 00:15:27,620 --> 00:15:32,390 >> Però també n'hi ha els simples, com el còmput 292 00:15:32,390 --> 00:15:39,010 la suma de les paraules, com cada lletra té un nombre. 293 00:15:39,010 --> 00:15:39,940 Calculeu la suma. 294 00:15:39,940 --> 00:15:42,230 Que determina el cub. 295 00:15:42,230 --> 00:15:45,430 També tenen les més fàcils que són igual que tots els d'un aquí, 296 00:15:45,430 --> 00:15:47,050 tots els de la B és aquí. 297 00:15:47,050 --> 00:15:48,920 Qualsevol d'aquests. 298 00:15:48,920 --> 00:15:55,770 >> Bàsicament, només se li diu que índex de la matriu del seu element ha d'entrar. 299 00:15:55,770 --> 00:15:58,690 Només decidir el bucket-- tot és una funció de hash és. 300 00:15:58,690 --> 00:16:04,180 Així que aquí tenim un exemple que és només la primera lletra de la cadena 301 00:16:04,180 --> 00:16:05,900 que m'estava parlant. 302 00:16:05,900 --> 00:16:11,900 >> Així que tens una mica de hash que és només la primera lletra de la cadena de menys A, 303 00:16:11,900 --> 00:16:16,090 que li donarà una mica de nombre entre 0 i 25. 304 00:16:16,090 --> 00:16:20,790 I el que vols fer és assegurar-se que això representa 305 00:16:20,790 --> 00:16:24,110 la mida de la seva picada table-- quants cubs hi ha. 306 00:16:24,110 --> 00:16:25,860 Amb molts d'aquests funcions hash, que són 307 00:16:25,860 --> 00:16:31,630 serà la devolució de valors que podrien estar molt per sobre del nombre de cubs 308 00:16:31,630 --> 00:16:33,610 que vostè realment té en la seva taula hash, 309 00:16:33,610 --> 00:16:37,240 per la qual cosa necessita per fer Segur i mod per aquells. 310 00:16:37,240 --> 00:16:42,190 En cas contrari, dirà, oh, ha de ser debades 5000 311 00:16:42,190 --> 00:16:46,040 però només té 30 cubs en la seva taula hash. 312 00:16:46,040 --> 00:16:49,360 I, per descomptat, tots sabem que és donarà lloc a alguns errors de bojos. 313 00:16:49,360 --> 00:16:52,870 Així que assegureu-vos de mod pel mida de la taula hash. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Refredar. 316 00:16:58,930 --> 00:17:00,506 Així col·lisions. 317 00:17:00,506 --> 00:17:02,620 Estan tots bé fins ara? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> AUDIÈNCIA: Per què es retornar un valor tan massiva? 320 00:17:05,900 --> 00:17:09,210 >> ALTAVEU 1: Depenent de l'algoritme que la seva funció hash utilitza. 321 00:17:09,210 --> 00:17:12,270 Alguns d'ells ho farà multiplicació boig. 322 00:17:12,270 --> 00:17:16,270 I és tot sobre aconseguir una distribució uniforme, 323 00:17:16,270 --> 00:17:18,490 pel que fan alguns realment bogeries de vegades. 324 00:17:18,490 --> 00:17:20,960 Això és tot. 325 00:17:20,960 --> 00:17:22,140 Una mica més? 326 00:17:22,140 --> 00:17:22,829 Okay. 327 00:17:22,829 --> 00:17:24,480 >> Així col·lisions. 328 00:17:24,480 --> 00:17:29,270 Bàsicament, com he dit abans, en el millor dels casos, 329 00:17:29,270 --> 00:17:32,040 qualsevol cub miro a és tindrà una cosa, 330 00:17:32,040 --> 00:17:34,160 així que no he de mirar a tots, oi? 331 00:17:34,160 --> 00:17:37,040 Jo bé sé que hi és o és no, i això és el que realment volem. 332 00:17:37,040 --> 00:17:43,960 Però si tenim desenes de milers de els punts de dades i menys d'aquest nombre 333 00:17:43,960 --> 00:17:48,700 de cubs, que tindrem col·lisions on finalment alguna cosa 334 00:17:48,700 --> 00:17:54,210 es va a haver d'acabar en un cub que ja compta amb un element. 335 00:17:54,210 --> 00:17:57,390 >> Així que la pregunta és, què Què fem en aquest cas? 336 00:17:57,390 --> 00:17:58,480 Què fem? 337 00:17:58,480 --> 00:17:59,300 Ja tenim alguna cosa allà? 338 00:17:59,300 --> 00:18:00,060 Ens fem una ullada? 339 00:18:00,060 --> 00:18:00,700 >> No 340 00:18:00,700 --> 00:18:01,980 Hem de mantenir els dos. 341 00:18:01,980 --> 00:18:06,400 Així que la forma en què solen fer-ho és el que? 342 00:18:06,400 --> 00:18:08,400 Quina és l'estructura de dades que acabem de parlar? 343 00:18:08,400 --> 00:18:09,316 AUDIÈNCIA: llista enllaçat. 344 00:18:09,316 --> 00:18:10,500 ALTAVEU 1: Una llista enllaçada. 345 00:18:10,500 --> 00:18:16,640 Així que ara, en lloc de cada un d'aquests cubs només tenir un element, 346 00:18:16,640 --> 00:18:24,020 que contindrà una llista enllaçada de els elements que van ser ordenada en ella. 347 00:18:24,020 --> 00:18:27,588 Bé, no tothom classe d'aquesta idea? 348 00:18:27,588 --> 00:18:30,546 Com que no podíem tenir una matriu perquè no sabem quantes coses 349 00:18:30,546 --> 00:18:31,730 hi seran. 350 00:18:31,730 --> 00:18:36,540 Una llista enllaçada ens permet tenir només el nombre exacte que 351 00:18:36,540 --> 00:18:38,465 es hash en aquest cub, oi? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Així sondeig lineal és bàsicament aquesta idea-- 354 00:18:50,500 --> 00:18:52,300 és una manera de fer front a una col·lisió. 355 00:18:52,300 --> 00:18:58,010 El que pot fer és si, en aquest cas, baia va ser ordenada en 1 356 00:18:58,010 --> 00:19:01,130 i ja tenim alguna cosa aquí, només 357 00:19:01,130 --> 00:19:04,840 seguir baixant fins a trobar una ranura buida. 358 00:19:04,840 --> 00:19:06,370 Aquesta és una manera de manejar la situació. 359 00:19:06,370 --> 00:19:09,020 L'altra manera de gestionar que és amb el que acabem de 360 00:19:09,020 --> 00:19:12,280 called-- el vinculat llista es diu encadenament. 361 00:19:12,280 --> 00:19:20,510 >> Així que aquesta idea funciona si la seva taula hash vostè pensa 362 00:19:20,510 --> 00:19:24,150 és molt més gran que conjunt de dades o si 363 00:19:24,150 --> 00:19:28,870 volen tractar de minimitzar l'encadenament fins que sigui absolutament necessari. 364 00:19:28,870 --> 00:19:34,050 Així que una cosa és lineal sondeig òbviament significa 365 00:19:34,050 --> 00:19:37,290 que la seva funció hash no és tan útil 366 00:19:37,290 --> 00:19:42,200 perquè vas a acabar amb la seva funció hash, arribant a un punt, 367 00:19:42,200 --> 00:19:46,400 li LINEAL sondeja fins algun lloc que està disponible. 368 00:19:46,400 --> 00:19:49,670 Però ara, per descomptat, qualsevol cosa una altra cosa que acaba allà, 369 00:19:49,670 --> 00:19:52,050 vostè va a haver de buscar fins i tot més avall. 370 00:19:52,050 --> 00:19:55,650 >> I hi ha molt més costa de recerca que 371 00:19:55,650 --> 00:19:59,820 entra en la introducció d'un element en la seva taula hash ara, oi? 372 00:19:59,820 --> 00:20:05,640 I ara que i tractes de trobar baia de nou, vas a hash d'ella, 373 00:20:05,640 --> 00:20:07,742 i que dirà, oh, mira al cub 1, 374 00:20:07,742 --> 00:20:09,700 i no serà en galleda 1, per la qual cosa és 375 00:20:09,700 --> 00:20:11,970 va a haver de travessar per la resta d'aquests. 376 00:20:11,970 --> 00:20:17,720 Així que de vegades és útil, però en la majoria dels casos, 377 00:20:17,720 --> 00:20:22,660 direm que L'encadenament és el que vols fer. 378 00:20:22,660 --> 00:20:25,520 >> Així que parlem d'això abans. 379 00:20:25,520 --> 00:20:27,812 Em vaig posar una mica per davant de mi mateix. 380 00:20:27,812 --> 00:20:33,560 Però l'encadenament és bàsicament que cada cub en la seva taula hash 381 00:20:33,560 --> 00:20:36,120 és només una llista enllaçada. 382 00:20:36,120 --> 00:20:39,660 >> Així que d'una altra manera, o més tècnic manera, pensar en una taula hash 383 00:20:39,660 --> 00:20:44,490 és que és només un arranjament de les llistes enllaçades, que 384 00:20:44,490 --> 00:20:49,330 quan vostè està escrivint el seu diccionari i vostè està tractant de carregar, 385 00:20:49,330 --> 00:20:52,070 pensar-hi com una varietat de llistes enllaçades 386 00:20:52,070 --> 00:20:54,390 farà que sigui molt més fàcil per inicialitzar. 387 00:20:54,390 --> 00:20:57,680 >> AUDIÈNCIA: Així taula hash té un mida per defecte, 388 00:20:57,680 --> 00:20:58,980 com un [inaudible] de cubs? 389 00:20:58,980 --> 00:20:59,220 >> ALTAVEU 1: Dret. 390 00:20:59,220 --> 00:21:01,655 Per tant, té un nombre determinat de cubs que determine-- 391 00:21:01,655 --> 00:21:03,530 que vostès han sentir-se lliure per jugar. 392 00:21:03,530 --> 00:21:05,269 Pot ser molt bé a veure què passa 393 00:21:05,269 --> 00:21:06,810 a mesura que canvia el seu nombre de cubs. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Però sí, té una establir el nombre de cubs. 396 00:21:11,510 --> 00:21:15,360 El que li permet ajustar com molts elements que vostè necessita 397 00:21:15,360 --> 00:21:19,350 és aquest encadenament separat on han vinculat les llistes a cada cub. 398 00:21:19,350 --> 00:21:22,850 Això vol dir que la seva taula hash serà exactament la mida 399 00:21:22,850 --> 00:21:25,440 que vostè necessita que sigui, no? 400 00:21:25,440 --> 00:21:27,358 Aquest és tot el punt de les llistes enllaçades. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Refredar. 403 00:21:32,480 --> 00:21:38,780 >> Així que tot el món bé allà? 404 00:21:38,780 --> 00:21:39,801 Bé. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Què acaba de succeir? 407 00:21:41,860 --> 00:21:42,960 Realment ara. 408 00:21:42,960 --> 00:21:45,250 Suposo que algú m'està matant. 409 00:21:45,250 --> 00:21:52,060 >> Acceptar que entrarem en tries, que són una mica boig. 410 00:21:52,060 --> 00:21:53,140 M'agrada taules hash. 411 00:21:53,140 --> 00:21:54,460 Crec que són molt cool. 412 00:21:54,460 --> 00:21:56,710 Tries són fresques, també. 413 00:21:56,710 --> 00:21:59,590 >> Així que algú recorda el que és una oportunitat? 414 00:21:59,590 --> 00:22:01,740 Vostè hauria d'haver anat més breument en la conferència? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Te'n recordes de classe de com funciona? 417 00:22:06,377 --> 00:22:08,460 AUDIÈNCIA: Només estic assentint que ens vam anar per sobre. 418 00:22:08,460 --> 00:22:09,626 ALTAVEU 1: Nosaltres anem sobre ella. 419 00:22:09,626 --> 00:22:13,100 Bé, realment anirem sobre ella ara és el que estem dient. 420 00:22:13,100 --> 00:22:14,860 >> AUDIÈNCIA: Això és per a un arbre de recuperació. 421 00:22:14,860 --> 00:22:15,280 >> ALTAVEU 1: Sí. 422 00:22:15,280 --> 00:22:16,196 És un arbre de la recuperació. 423 00:22:16,196 --> 00:22:16,960 Impressionant. 424 00:22:16,960 --> 00:22:23,610 Així que una cosa a notar aquí és que nosaltres estan mirant a caràcters individuals 425 00:22:23,610 --> 00:22:24,480 aquí, oi? 426 00:22:24,480 --> 00:22:29,710 >> Així que abans amb la nostra funció de hash, que estaven mirant les paraules en el seu conjunt, 427 00:22:29,710 --> 00:22:32,270 i ara estem buscant més els personatges, no? 428 00:22:32,270 --> 00:22:38,380 Així que tenim Maxwell aquí i Mendel. 429 00:22:38,380 --> 00:22:47,840 Així que, bàsicament, un try-- una manera de pensar d'això és que tots els nivells aquí 430 00:22:47,840 --> 00:22:49,000 és una sèrie de lletres. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Així que aquest és el seu node arrel aquí, oi? 433 00:22:55,790 --> 00:23:01,980 Això té tots els caràcters de la alfabet per a l'inici de cada paraula. 434 00:23:01,980 --> 00:23:06,480 >> I el que vols fer és per exemple, OK, tenim alguna paraula el Sr. 435 00:23:06,480 --> 00:23:10,590 Anem a buscar Maxwell, per la qual cosa anem als punts M. i M a un tot 436 00:23:10,590 --> 00:23:14,800 un altre una matriu en la qual cada paraula, mentre hi hagi 437 00:23:14,800 --> 00:23:17,044 és una paraula que té un com la segona carta, 438 00:23:17,044 --> 00:23:19,460 sempre que no hi ha una paraula que té B com la segona carta, 439 00:23:19,460 --> 00:23:24,630 que tindrà un punter anar a algun lloc array. 440 00:23:24,630 --> 00:23:29,290 >> Probablement no és un paraula que MP alguna cosa, 441 00:23:29,290 --> 00:23:32,980 pel que en la posició P en aquest matriu, que només seria NULL. 442 00:23:32,980 --> 00:23:38,840 Es diria, està bé, no hi ha una paraula que ha seguit d'una M P, d'acord? 443 00:23:38,840 --> 00:23:43,100 Així que si ho pensem bé, cada d'aquestes coses més petites 444 00:23:43,100 --> 00:23:47,990 és en realitat un d'ells grans conjunts de l'A a la Z. 445 00:23:47,990 --> 00:23:55,064 Així que el que podria ser una de les coses que és una espècie d'inconvenient d'una oportunitat? 446 00:23:55,064 --> 00:23:56,500 >> AUDIÈNCIA: Una gran quantitat de memòria. 447 00:23:56,500 --> 00:23:59,940 >> ALTAVEU 1: És una tona de memòria, oi? 448 00:23:59,940 --> 00:24:08,750 Cadascun d'aquests blocs aquí representa 26 espais, 26 element de la matriu. 449 00:24:08,750 --> 00:24:13,680 Així que intenta aconseguir espai increïblement pesat. 450 00:24:13,680 --> 00:24:17,100 >> Però ells són molt ràpids. 451 00:24:17,100 --> 00:24:22,540 Tan increïblement ràpid, però realment espai ineficient. 452 00:24:22,540 --> 00:24:24,810 Tipus d'haver de esbrinar a quin d'ells vol. 453 00:24:24,810 --> 00:24:29,470 Aquests són realment fresc per a la seva conjunt de processadors, però sí tenir una gran quantitat de memòria, 454 00:24:29,470 --> 00:24:30,290 de manera que el comerç fora. 455 00:24:30,290 --> 00:24:31,480 Sí? 456 00:24:31,480 --> 00:24:34,300 >> AUDIÈNCIA: Seria possible la creació d'una oportunitat i després 457 00:24:34,300 --> 00:24:37,967 una vegada hagueu aconseguit la dades en ell que vostè need-- 458 00:24:37,967 --> 00:24:39,550 No sé si això té sentit. 459 00:24:39,550 --> 00:24:42,200 Em va a desfer de tot el Caràcters NULL, però a continuació, 460 00:24:42,200 --> 00:24:42,910 no seria capaç d'indexar ells-- 461 00:24:42,910 --> 00:24:43,275 >> ALTAVEU 1: Vostè encara els necessiten. 462 00:24:43,275 --> 00:24:44,854 >> AUDIÈNCIA: - de la mateixa manera cada vegada. 463 00:24:44,854 --> 00:24:45,520 ALTAVEU 1: Sí. 464 00:24:45,520 --> 00:24:50,460 Vostè necessita els caràcters NULL perquè Com saber si no hi ha una paraula allà. 465 00:24:50,460 --> 00:24:52,040 Ben no tens alguna cosa que vols? 466 00:24:52,040 --> 00:24:52,540 Okay. 467 00:24:52,540 --> 00:24:54,581 Molt bé, així que anem per anar una mica més 468 00:24:54,581 --> 00:24:58,920 en els detalls tècnics darrere 1 tractar de treballar a través d'un exemple. 469 00:24:58,920 --> 00:25:01,490 >> Acceptar, de manera que aquesta és la mateixa cosa. 470 00:25:01,490 --> 00:25:06,290 Mentre que en una llista enllaçada, la nostra principal tipus de-- quina és la paraula que vull? - 471 00:25:06,290 --> 00:25:08,350 com la construcció de bloc era un node. 472 00:25:08,350 --> 00:25:12,280 En una oportunitat, també tenim un node, però es defineix de manera diferent. 473 00:25:12,280 --> 00:25:17,000 >> Així que tenim alguns bool que representa si una paraula en realitat 474 00:25:17,000 --> 00:25:23,530 existeix en aquesta ubicació, i després tenim una mica de varietat aquí-- o més aviat, 475 00:25:23,530 --> 00:25:27,840 aquest és un punter a una sèrie de 27 caràcters. 476 00:25:27,840 --> 00:25:33,339 I això és per a, en aquest cas, aquesta 27-- Estic segur que tots vostès són com, espero, 477 00:25:33,339 --> 00:25:34,880 hi ha 26 lletres en l'alfabet. 478 00:25:34,880 --> 00:25:36,010 Per què tenim 27? 479 00:25:36,010 --> 00:25:37,870 >> Així que depenent de la manera d'implementar això, 480 00:25:37,870 --> 00:25:43,240 això és d'un conjunt de processadors que permetre apòstrofs. 481 00:25:43,240 --> 00:25:46,010 Així que per això l'un extra. 482 00:25:46,010 --> 00:25:50,500 També tindrà en alguns casos, el terminador nul 483 00:25:50,500 --> 00:25:53,230 s'inclou com una de les personatges que prohibeix ser, 484 00:25:53,230 --> 00:25:56,120 i això és el que verifiquen veure si és el final de la paraula. 485 00:25:56,120 --> 00:26:01,340 Si estàs interessat, visita Vídeo de Kevin a study.cs50, 486 00:26:01,340 --> 00:26:04,790 així com Wikipedia té alguns bons recursos allà. 487 00:26:04,790 --> 00:26:09,000 >> Però anem a anar a través de només una mica de com es pot treballar a través d'un provar 488 00:26:09,000 --> 00:26:11,010 si et donen una. 489 00:26:11,010 --> 00:26:16,230 Així que tenim un super senzill aquí que té la paraula "bat" i "zoom" a ells. 490 00:26:16,230 --> 00:26:18,920 I com veiem aquí, aquest petit espai aquí 491 00:26:18,920 --> 00:26:22,560 representa la nostra bool que diu, sí, aquesta és una paraula. 492 00:26:22,560 --> 00:26:27,060 I llavors això té la nostra matrius de caràcters, no? 493 00:26:27,060 --> 00:26:33,480 >> Així que anem a anar a través de la recerca de "ratpenat" en aquest intent. 494 00:26:33,480 --> 00:26:38,340 Així que comenci per la part superior, a la dreta? 495 00:26:38,340 --> 00:26:46,290 I sabem que B correspon a el segon índex, el segon element 496 00:26:46,290 --> 00:26:47,840 en aquesta matriu, a causa a i b. 497 00:26:47,840 --> 00:26:51,340 Així que aproximadament el segon. 498 00:26:51,340 --> 00:26:58,820 >> I diu, bé, fresc, se segueix que en la següent matriu, ja que si recordem, 499 00:26:58,820 --> 00:27:02,160 no és que cada un d'aquests en realitat conté l'element. 500 00:27:02,160 --> 00:27:07,110 Cadascuna d'aquestes matrius conté un punter, oi? 501 00:27:07,110 --> 00:27:10,030 És una distinció important a fer. 502 00:27:10,030 --> 00:27:13,450 >> Sé que això serà: tries són molt difícil d'aconseguir a la primera vegada, 503 00:27:13,450 --> 00:27:15,241 per la qual cosa fins i tot si aquest és el segona o tercera vegada 504 00:27:15,241 --> 00:27:18,370 i és encara tipus de semblar difícil, 505 00:27:18,370 --> 00:27:21,199 Et prometo que si vas rellotge el matí de nou a curt, 506 00:27:21,199 --> 00:27:22,740 és probable que farà molt més sentit. 507 00:27:22,740 --> 00:27:23,890 Es necessita molt per pair. 508 00:27:23,890 --> 00:27:27,800 Encara de vegades sóc com, espera, el que és una oportunitat? 509 00:27:27,800 --> 00:27:29,080 Com utilitzo això? 510 00:27:29,080 --> 00:27:33,880 >> Així que hem B en aquest cas, que és el nostre segon índex. 511 00:27:33,880 --> 00:27:40,240 Si tinguéssim, per exemple, o c d o qualsevol altra lletra, 512 00:27:40,240 --> 00:27:45,810 hem de mapejar de tornar a l'índex de la nostra matriu que que correspon a. 513 00:27:45,810 --> 00:27:56,930 Així que prendríem com rchar i només restar d'una a Localitzar en un mapa a 0 a 25. 514 00:27:56,930 --> 00:27:58,728 Tothom bé com mapejar els nostres personatges? 515 00:27:58,728 --> 00:28:00,440 Okay. 516 00:28:00,440 --> 00:28:05,980 >> Així que anem a la segona, i que veure que, sí, no és NULL. 517 00:28:05,980 --> 00:28:07,780 Podem passar a aquesta nova matriu. 518 00:28:07,780 --> 00:28:12,300 Així que passem a aquesta propera sèrie aquí. 519 00:28:12,300 --> 00:28:15,500 >> I diem, bé, ara ens que tingui a veure si a és aquí. 520 00:28:15,500 --> 00:28:18,590 És un valor nul o el fa realment avançar? 521 00:28:18,590 --> 00:28:21,880 Així que una es mou realment cap endavant en aquesta sèrie. 522 00:28:21,880 --> 00:28:24,570 I diem, OK, t és la nostra última carta. 523 00:28:24,570 --> 00:28:27,580 Així que anem a la t en l'índex. 524 00:28:27,580 --> 00:28:30,120 I després ens movem cap endavant perquè no hi ha un altre. 525 00:28:30,120 --> 00:28:38,340 I aquest diu bàsicament que, sí, es diu que hi ha una paraula aquí-- 526 00:28:38,340 --> 00:28:41,750 que si segueix aquest camí, vostè ha arribat 527 00:28:41,750 --> 00:28:43,210 en una paraula, que sabem que és "ratpenat". 528 00:28:43,210 --> 00:28:43,800 Sí? 529 00:28:43,800 --> 00:28:46,770 >> AUDIÈNCIA: És normal haver de com l'índex 0 i després tenir una espècie en 1 530 00:28:46,770 --> 00:28:47,660 o perquè al final? 531 00:28:47,660 --> 00:28:48,243 >> ALTAVEU 1: No. 532 00:28:48,243 --> 00:28:55,360 Així que si mirem cap enrere en la nostra declaració aquí, és un bool, 533 00:28:55,360 --> 00:28:59,490 pel que és el seu propi element en el seu node. 534 00:28:59,490 --> 00:29:03,331 Així que no és part de la matriu. 535 00:29:03,331 --> 00:29:03,830 Refredar. 536 00:29:03,830 --> 00:29:08,370 Així que quan acabem la nostra paraula i estem en aquesta matriu, el que volem fer 537 00:29:08,370 --> 00:29:12,807 és fer un xec per aquesta és una paraula. 538 00:29:12,807 --> 00:29:14,390 I en aquest cas, seria tornar si. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Així que en aquest sentit, sabem que "zoo" - que coneixem com a éssers humans que "zoo" és una paraula, 541 00:29:24,090 --> 00:29:24,820 Oi? 542 00:29:24,820 --> 00:29:28,990 Però es tracti d'aquí seria dir, no, no ho és. 543 00:29:28,990 --> 00:29:33,980 I diria que pel fet que no han designat com una paraula aquí. 544 00:29:33,980 --> 00:29:40,440 Tot i que podem travessar a través d'aquesta matriu, 545 00:29:40,440 --> 00:29:43,890 aquest intent diria que no, zoològic no està en el seu diccionari 546 00:29:43,890 --> 00:29:47,070 perquè nosaltres no tenim designada com a tal. 547 00:29:47,070 --> 00:29:52,870 >> Així que una manera de fer-ho que-- oh, ho sento, aquesta. 548 00:29:52,870 --> 00:29:59,450 Així que en aquest cas, "zoo" no és una paraula, però està en el nostre intent. 549 00:29:59,450 --> 00:30:05,690 Però en aquest, diem que volem que introduir la paraula "bany", el que succeeix 550 00:30:05,690 --> 00:30:08,260 és que seguim through-- b, a, t. 551 00:30:08,260 --> 00:30:11,820 Estem en aquesta matriu, i anem a buscar h. 552 00:30:11,820 --> 00:30:15,220 >> En aquest cas, quan mirar el punter en h, 553 00:30:15,220 --> 00:30:17,890 està apuntant a NULL, d'acord? 554 00:30:17,890 --> 00:30:20,780 Així que a menys que sigui explícitament apuntant a una altra matriu, 555 00:30:20,780 --> 00:30:25,000 vostè assumeix que tots els punters en aquesta matriu estan apuntant a null. 556 00:30:25,000 --> 00:30:28,270 Així doncs, en aquest cas, h està apuntant per anul·lar el que no podem fer res, 557 00:30:28,270 --> 00:30:31,540 per la qual cosa també seria tornar falsa, "bany" no és aquí. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Així que ara estem en realitat va a anar a través de 560 00:30:35,810 --> 00:30:39,790 ¿Com podem realment dir que "zoo" és en el nostre intent. 561 00:30:39,790 --> 00:30:42,920 Com ens inserim "zoo" en el nostre intent? 562 00:30:42,920 --> 00:30:47,810 Així que de la mateixa manera que vam començar amb la nostra llista enllaçada, que comencen a l'arrel. 563 00:30:47,810 --> 00:30:50,600 En cas de dubte, comenci a l'arrel d'aquestes coses. 564 00:30:50,600 --> 00:30:53,330 >> I anem a dir, OK, z. 565 00:30:53,330 --> 00:30:55,650 existeix z en això, i ho fa. 566 00:30:55,650 --> 00:30:58,370 Així que vostè està de passar a el seu següent sèrie, d'acord? 567 00:30:58,370 --> 00:31:01,482 I a continuació, en la següent, diem, bé, sí que hi ha o? 568 00:31:01,482 --> 00:31:03,000 Ho fa. 569 00:31:03,000 --> 00:31:04,330 Això de nou. 570 00:31:04,330 --> 00:31:08,670 >> I així, en el nostre proper un, que hem dit, Acceptar, "zoo" ja existeix aquí. 571 00:31:08,670 --> 00:31:12,440 Tot el que necessitem fer és establir aquesta igualtat a la veritable, que no és una paraula allà. 572 00:31:12,440 --> 00:31:15,260 Si haguessis seguit tot fins abans d'aquest punt, 573 00:31:15,260 --> 00:31:17,030 es tracta d'una paraula, de manera que només configurar igual a tals. 574 00:31:17,030 --> 00:31:17,530 Sí? 575 00:31:17,530 --> 00:31:22,550 >> AUDIÈNCIA: Llavors sí que significa que "ba" és una paraula també? 576 00:31:22,550 --> 00:31:24,120 >> ALTAVEU 1: No. 577 00:31:24,120 --> 00:31:28,870 Així que en aquest cas, "ba" obtindríem aquí, diríem que és una paraula, 578 00:31:28,870 --> 00:31:31,590 i encara seria no. 579 00:31:31,590 --> 00:31:32,822 D'acord? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> AUDIÈNCIA: Així que una vegada que es tracta d'una paraula i diu que sí, llavors 582 00:31:36,360 --> 00:31:38,380 contindrà anar al m? 583 00:31:38,380 --> 00:31:42,260 >> ALTAVEU 1: Així que això té a veure con-- va a carregar això en. 584 00:31:42,260 --> 00:31:43,640 Vostè diu "zoo" és una paraula. 585 00:31:43,640 --> 00:31:47,020 Quan vostè va a check-- com, diguem que vostè vol dir, 586 00:31:47,020 --> 00:31:49,400 existeix "zoo" en aquest diccionari? 587 00:31:49,400 --> 00:31:54,200 Només vas a buscar "zoològic" i després comprovar per veure si es tracta d'una paraula. 588 00:31:54,200 --> 00:31:57,291 Mai vas a moure a través de m perquè això no és 589 00:31:57,291 --> 00:31:58,290 el que estàs buscant. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Així que si realment volíem afegir "bany" en aquest intent, 592 00:32:08,070 --> 00:32:11,390 que anàvem a fer el mateix com ho vam fer amb "zoo" 593 00:32:11,390 --> 00:32:15,380 excepte veuríem que quan ens tractar d'arribar a h, que no existeix. 594 00:32:15,380 --> 00:32:20,090 Així que vostè pot pensar en això com tractant per afegir un nou node en una llista enllaçada, 595 00:32:20,090 --> 00:32:27,210 per la qual cosa hauríem d'afegir un altre d'aquestes matrius, com a tal. 596 00:32:27,210 --> 00:32:35,670 I llavors el que fem és tot just fixem el h element d'aquesta matriu que apunta a això. 597 00:32:35,670 --> 00:32:39,430 >> I llavors, ¿què anàvem a voler fer aquí? 598 00:32:39,430 --> 00:32:43,110 Afegeix-lo igual a veritable perquè és una paraula. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Refredar. 601 00:32:48,150 --> 00:32:48,700 Ho sé. 602 00:32:48,700 --> 00:32:51,170 Intents no són les més emocionants. 603 00:32:51,170 --> 00:32:54,250 Confia en mi, ho sé. 604 00:32:54,250 --> 00:32:58,040 >> Així que una cosa que s'adona amb tries, Jo vaig dir, són molt eficients. 605 00:32:58,040 --> 00:33:00,080 Així que hem vist que portar fins a una tona d'espai. 606 00:33:00,080 --> 00:33:01,370 Estan una mica confús. 607 00:33:01,370 --> 00:33:03,367 Així que per què hauríem mai utilitzar aquests? 608 00:33:03,367 --> 00:33:05,450 Utilitzem aquests perquè són increïblement eficient. 609 00:33:05,450 --> 00:33:08,130 >> Així que si estàs buscant alguna vegada una paraula, vostè és només 610 00:33:08,130 --> 00:33:10,450 limitada per la longitud de la paraula. 611 00:33:10,450 --> 00:33:15,210 Així que si vostè està buscant un paraula que té una longitud de cinc, 612 00:33:15,210 --> 00:33:20,940 vostè està sol mai va a haver de fer en la majoria dels cinc comparacions, d'acord? 613 00:33:20,940 --> 00:33:25,780 Per tant, fa que sigui bàsicament una constant. 614 00:33:25,780 --> 00:33:29,150 Igual que la inserció i recerca són bàsicament constant de temps. 615 00:33:29,150 --> 00:33:33,750 >> Així que si alguna vegada es pot obtenir alguna cosa en el temps constant, 616 00:33:33,750 --> 00:33:35,150 això és tan bo com es posa. 617 00:33:35,150 --> 00:33:37,990 No pot ser millor que constant de temps per a aquestes coses. 618 00:33:37,990 --> 00:33:43,150 Així que aquest és un dels enormes avantatges d'intents. 619 00:33:43,150 --> 00:33:46,780 >> Però és un munt d'espai. 620 00:33:46,780 --> 00:33:50,380 Així que tipus d'haver de decidir el que és més important per a tu. 621 00:33:50,380 --> 00:33:54,700 I en els ordinadors d'avui en dia, la espai que una oportunitat pot prendre fins 622 00:33:54,700 --> 00:33:57,740 potser no afecta que molt, però potser 623 00:33:57,740 --> 00:34:01,350 vostè està tractant amb alguna cosa que té molt, molt més les coses, 624 00:34:01,350 --> 00:34:02,810 i una oportunitat simplement no és raonable. 625 00:34:02,810 --> 00:34:03,000 Sí? 626 00:34:03,000 --> 00:34:05,610 >> AUDIÈNCIA: Esperi, pel que té 26 lletres en cada un? 627 00:34:05,610 --> 00:34:07,440 >> ALTAVEU 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Sí, vostè té 26. 629 00:34:08,570 --> 00:34:16,984 Vostè té alguns és marcador de paraula i després vostè té 26 punters en cada un. 630 00:34:16,984 --> 00:34:17,775 I estan point-- 631 00:34:17,775 --> 00:34:20,280 >> AUDIÈNCIA: I cada 26, és el que cada un té 26? 632 00:34:20,280 --> 00:34:21,500 >> ALTAVEU 1: Sí. 633 00:34:21,500 --> 00:34:27,460 I és per això, que pugui veure, s'expandeix molt ràpidament. 634 00:34:27,460 --> 00:34:28,130 Bé. 635 00:34:28,130 --> 00:34:32,524 Així que anem a entrar en els arbres, que Em sento com és més fàcil i probablement 636 00:34:32,524 --> 00:34:36,150 ser un petit respir de tries allà. 637 00:34:36,150 --> 00:34:39,620 Així que espero que la majoria de vostès han vist un arbre abans. 638 00:34:39,620 --> 00:34:41,820 No com el bonic els exteriors, que jo 639 00:34:41,820 --> 00:34:44,340 no sé si algú es va anar a l'aire lliure recentment. 640 00:34:44,340 --> 00:34:49,230 Vaig ser recol·lecció de pomes aquest cap de setmana, i, oh, Déu meu, que era preciosa. 641 00:34:49,230 --> 00:34:52,250 Jo no sabia fulles podria mirar que bonica. 642 00:34:52,250 --> 00:34:53,610 >> Així que això és només un arbre, no? 643 00:34:53,610 --> 00:34:56,790 És només una mica de node, i apunta a un munt d'altres nodes. 644 00:34:56,790 --> 00:34:59,570 Com es veu aquí, aquest és tipus d'un tema recurrent. 645 00:34:59,570 --> 00:35:03,720 Els nodes que apunta als nodes és una espècie de l'essència de moltes estructures de dades. 646 00:35:03,720 --> 00:35:06,670 Només depèn de la forma en què tenen ells assenyalen l'un a l'altre 647 00:35:06,670 --> 00:35:08,600 i com travessem a través d'ells i la forma en què 648 00:35:08,600 --> 00:35:14,500 inserir les coses que determina les seves diferents característiques. 649 00:35:14,500 --> 00:35:17,600 >> Així que només alguns dels termes, que he fet servir abans. 650 00:35:17,600 --> 00:35:20,010 Així que l'arrel és el que està en la part superior. 651 00:35:20,010 --> 00:35:21,200 que és on sempre comencem. 652 00:35:21,200 --> 00:35:23,610 Vostè pot pensar en ell com el cap també. 653 00:35:23,610 --> 00:35:28,750 Però per als arbres, tendim a es refereixen a ella com l'arrel. 654 00:35:28,750 --> 00:35:32,820 >> Qualsevol cosa a la part inferior aquí-- en el molt, molt bottom-- 655 00:35:32,820 --> 00:35:34,500 són considerats fulles. 656 00:35:34,500 --> 00:35:37,210 Per tant, va de la mà amb la El arbre sencer, no? 657 00:35:37,210 --> 00:35:39,860 Les fulles són a les vores del seu arbre. 658 00:35:39,860 --> 00:35:45,820 >> I després també tenim un parell de termes per parlar de nodes de relació 659 00:35:45,820 --> 00:35:46,680 l'un a l'altre. 660 00:35:46,680 --> 00:35:49,700 Així que tenim els pares, fills i germans. 661 00:35:49,700 --> 00:35:56,260 Així doncs, en aquest cas, 3 és el matriu de 5, 6, i 7. 662 00:35:56,260 --> 00:36:00,370 Així que el pare és el que és un pas per sobre del que sigui que estiguis 663 00:36:00,370 --> 00:36:02,940 en referència a, de manera que només com un arbre genealògic. 664 00:36:02,940 --> 00:36:07,090 Amb sort, això és tot una mica poc més intuïtiu que els intents. 665 00:36:07,090 --> 00:36:10,970 >> Els germans són qualsevol que tingui el mateix pare, oi? 666 00:36:10,970 --> 00:36:13,470 Estan en el mateix nivell aquí. 667 00:36:13,470 --> 00:36:16,960 I llavors, com jo dient, els nens són només 668 00:36:16,960 --> 00:36:22,630 el que és un pas per sota el node en qüestió, d'acord? 669 00:36:22,630 --> 00:36:23,470 Refredar. 670 00:36:23,470 --> 00:36:25,610 Així, un arbre binari. 671 00:36:25,610 --> 00:36:31,450 Algú pot aventurar una resposta en un les característiques de l'arbre binari? 672 00:36:31,450 --> 00:36:32,770 >> AUDIÈNCIA: Max dues fulles. 673 00:36:32,770 --> 00:36:33,478 >> ALTAVEU 1: Dret. 674 00:36:33,478 --> 00:36:34,640 Així màxim de dos fulls. 675 00:36:34,640 --> 00:36:39,730 Així que en això abans, vam tenir aquest que tenia tres, però en un arbre binari, 676 00:36:39,730 --> 00:36:45,000 Té un màxim de dos fills pels pares, no? 677 00:36:45,000 --> 00:36:46,970 Hi ha un altre característica interessant. 678 00:36:46,970 --> 00:36:51,550 Algú sap que? 679 00:36:51,550 --> 00:36:52,620 Arbre binari. 680 00:36:52,620 --> 00:37:00,350 >> Així que un arbre binari tindrà tot en ell-- aquest no és sorted-- 681 00:37:00,350 --> 00:37:05,320 però en un arbre binari ordenat, tot a la dreta 682 00:37:05,320 --> 00:37:08,530 és més gran que la dels pares, i tot a l'esquerra 683 00:37:08,530 --> 00:37:10,035 és menor que la dels pares. 684 00:37:10,035 --> 00:37:15,690 I això ha estat un concurs qüestió que, per bo saber. 685 00:37:15,690 --> 00:37:19,500 Així que la manera com definim això, una vegada més, tenim un altre node. 686 00:37:19,500 --> 00:37:21,880 Això es veu molt similar al que? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Doblement 689 00:37:28,836 --> 00:37:29,320 >> AUDIÈNCIA: Vinculat llistes 690 00:37:29,320 --> 00:37:31,100 >> ALTAVEU 1: Una llista enllaçada doble, no? 691 00:37:31,100 --> 00:37:33,690 Així que si reemplacem aquest amb anterior i següent, 692 00:37:33,690 --> 00:37:35,670 això seria una llista doblement enllaçada. 693 00:37:35,670 --> 00:37:40,125 Però en aquest cas, en realitat tenir a l'esquerra i la dreta i això és tot. 694 00:37:40,125 --> 00:37:41,500 En cas contrari, és exactament el mateix. 695 00:37:41,500 --> 00:37:43,374 Encara tenim l'element que vostè està buscant, 696 00:37:43,374 --> 00:37:45,988 i només hi ha dos punters anar al que ve. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Sí, així binari arbre de cerca. 699 00:37:51,870 --> 00:37:57,665 Si ens adonem, sobretot en el aquí és més gran no sigui: 700 00:37:57,665 --> 00:37:59,850 o tot immediatament a la dreta aquí 701 00:37:59,850 --> 00:38:02,840 és més gran que, tot aquí és inferior. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Així que si haguéssim de buscar a través, que ha de mirar molt a prop de recerca binària 704 00:38:14,000 --> 00:38:14,910 aquí, oi? 705 00:38:14,910 --> 00:38:17,640 Excepte que en comptes de mirar a la meitat de la matriu, 706 00:38:17,640 --> 00:38:21,720 només estem buscant, ja sigui en l'esquerra costat o del costat dret de l'arbre. 707 00:38:21,720 --> 00:38:24,850 Així que es posa una mica més simple, crec. 708 00:38:24,850 --> 00:38:29,300 >> Així que si la seva arrel és NULL, òbviament és només falsa. 709 00:38:29,300 --> 00:38:33,470 I si hi és, òbviament, és la veritat. 710 00:38:33,470 --> 00:38:35,320 Si és menor que, busquem l'esquerra. 711 00:38:35,320 --> 00:38:37,070 Si és més gran que, busquem la dreta. 712 00:38:37,070 --> 00:38:39,890 És exactament igual que la recerca binària, només una estructura de dades diferent 713 00:38:39,890 --> 00:38:40,600 que estem fent servir. 714 00:38:40,600 --> 00:38:42,790 En lloc d'una matriu, és només un arbre binari. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> Acceptar, piles. 717 00:38:48,090 --> 00:38:51,550 I també, sembla que podria tenir una mica de temps. 718 00:38:51,550 --> 00:38:54,460 Si ho fem, estic feliç d'anar sobre qualsevol d'això una altra vegada. 719 00:38:54,460 --> 00:38:56,856 OK, així que piles. 720 00:38:56,856 --> 00:39:02,695 Algú recorda el que stacks-- qualsevol característica d'una pila? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> Acceptar, de manera que la majoria de nosaltres, crec, dinar al menjador halls-- 723 00:39:10,400 --> 00:39:13,100 tant com és possible que no els agrada. 724 00:39:13,100 --> 00:39:16,900 Però, òbviament, es pot pensar en una pila literalment, igual que una pila de safates 725 00:39:16,900 --> 00:39:18,460 o una pila de coses. 726 00:39:18,460 --> 00:39:21,820 I el que és important és adonar-se que és 727 00:39:21,820 --> 00:39:26,850 alguna cosa-- la característica que nosaltres anomenem por-- és LIFO. 728 00:39:26,850 --> 00:39:28,450 Algú sap el que això representa? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> AUDIÈNCIA: últim a entrar, primer a sortir. 731 00:39:30,650 --> 00:39:32,250 >> ALTAVEU 1: Dreta, últim a entrar, primer a sortir. 732 00:39:32,250 --> 00:39:36,585 Així que si sabem, si estem apilant coses dalt, la cosa més fàcil d'agafar off-- 733 00:39:36,585 --> 00:39:39,570 i potser l'únic que pot prendre fora si la nostra pila és gran enough-- 734 00:39:39,570 --> 00:39:40,850 és que element superior. 735 00:39:40,850 --> 00:39:43,460 Així que qualsevol cosa es va posar en last-- com veiem aquí, 736 00:39:43,460 --> 00:39:46,370 el que va ser empès en la majoria recently-- és 737 00:39:46,370 --> 00:39:51,160 serà el primer cosa que ens pop fora, d'acord? 738 00:39:51,160 --> 00:39:56,324 >> Així que el que tenim aquí és un altre struct typedef. 739 00:39:56,324 --> 00:39:58,740 Això és realment només com un Curs accelerat en l'estructura de dades, 740 00:39:58,740 --> 00:40:01,650 així que hi ha un munt llançada contra vosaltres. 741 00:40:01,650 --> 00:40:02,540 Ho sé. 742 00:40:02,540 --> 00:40:04,970 Així una altra struct. 743 00:40:04,970 --> 00:40:06,740 Yay per a estructures. 744 00:40:06,740 --> 00:40:16,660 >> I en aquest cas, es tracta d'algun punter a una matriu que té una certa capacitat. 745 00:40:16,660 --> 00:40:20,830 Així que això representa la nostra pila aquí, igual que la nostra gamma actual 746 00:40:20,830 --> 00:40:22,520 això és la celebració dels nostres elements. 747 00:40:22,520 --> 00:40:24,850 I llavors aquí tenim una mica de mida. 748 00:40:24,850 --> 00:40:31,170 >> I en general, que desitja conservar pista de com de gran és la seva pila és 749 00:40:31,170 --> 00:40:36,180 perquè el que permetrà tu per fer és si vostè sap la mida, 750 00:40:36,180 --> 00:40:39,170 que li permet dir, Bé, estic en capacitat? 751 00:40:39,170 --> 00:40:40,570 Puc afegir alguna cosa més? 752 00:40:40,570 --> 00:40:44,650 I també et diu on la part superior de la pila 753 00:40:44,650 --> 00:40:48,180 és pel que vostè sap el que en realitat pot enlairar. 754 00:40:48,180 --> 00:40:51,760 I això és en realitat va a ser una mica més clar aquí. 755 00:40:51,760 --> 00:40:57,350 >> Així, per empenta, una cosa, si vostè van ser mai per aplicar empenta, 756 00:40:57,350 --> 00:41:01,330 com jo estava dient, la seva pila té una grandària limitada, oi? 757 00:41:01,330 --> 00:41:03,990 La nostra gamma tenia alguna capacitat. 758 00:41:03,990 --> 00:41:04,910 És una matriu. 759 00:41:04,910 --> 00:41:08,930 És una mida fixa, per la qual cosa necessitem assegurar-se que no estem posant més 760 00:41:08,930 --> 00:41:11,950 en la nostra gamma del que en realitat tenen espai per a. 761 00:41:11,950 --> 00:41:16,900 >> Així que quan vostè està creant una empenta funció, el primer que fas és a dir, OK, 762 00:41:16,900 --> 00:41:18,570 ¿Tinc espai al meu pila? 763 00:41:18,570 --> 00:41:23,330 Perquè si no ho faig, ho sento, No puc desar l'ítem. 764 00:41:23,330 --> 00:41:28,980 Si ho faig, llavors vostè vol emmagatzemar a la part superior de la pila, no? 765 00:41:28,980 --> 00:41:31,325 >> I és per això que tenim fer un seguiment de les nostres dimensions. 766 00:41:31,325 --> 00:41:35,290 Si no mantenim un registre de la nostra mida, no sabem on posar-lo. 767 00:41:35,290 --> 00:41:39,035 No sabem quantes coses estan en la nostra gamma ja. 768 00:41:39,035 --> 00:41:41,410 Igual que, òbviament, hi ha formes que potser vostè podria fer-ho. 769 00:41:41,410 --> 00:41:44,610 Vostè podria inicialitzar tot a NULL i després comprovar si l'última NULL, 770 00:41:44,610 --> 00:41:47,950 però una cosa molt més fàcil és simplement a dir, OK, no perdre de vista la mida. 771 00:41:47,950 --> 00:41:51,840 De la mateixa manera que jo sé que tinc quatre elements en la meva matriu, de manera que la següent cosa 772 00:41:51,840 --> 00:41:55,930 que ens posem, estem va a emmagatzemar en l'índex abril. 773 00:41:55,930 --> 00:42:00,940 I llavors, és clar, això vol dir que vostè ha empès amb èxit alguna cosa 774 00:42:00,940 --> 00:42:03,320 a la pica, vulgui augmentar la mida 775 00:42:03,320 --> 00:42:08,880 perquè vostè sàpiga on vostè està tan que vostè pot empènyer més coses sobre. 776 00:42:08,880 --> 00:42:12,730 >> Així que si estem tractant de fer esclatar alguna cosa fora de la pila, 777 00:42:12,730 --> 00:42:16,072 el que podria ser la primera cosa que volem comprovar? 778 00:42:16,072 --> 00:42:18,030 Vostè està tractant de prendre alguna cosa fora de la seva pila. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Segur que hi ha alguna cosa a la pica? 781 00:42:24,781 --> 00:42:25,280 No 782 00:42:25,280 --> 00:42:26,894 Llavors, ¿què podríem voler comprovar? 783 00:42:26,894 --> 00:42:27,810 >> AUDIÈNCIA: [inaudible]. 784 00:42:27,810 --> 00:42:29,880 ALTAVEU 1: Comproveu la mida? 785 00:42:29,880 --> 00:42:31,840 Mida. 786 00:42:31,840 --> 00:42:38,520 Així que volem comprovar per veure si la nostra mida és més gran que 0, d'acord? 787 00:42:38,520 --> 00:42:44,970 I si ho és, llavors volem disminuir la nostra mida per 0 i tornar això. 788 00:42:44,970 --> 00:42:45,840 Per què? 789 00:42:45,840 --> 00:42:49,950 >> A la primera estàvem empènyer, ens empenyem 790 00:42:49,950 --> 00:42:52,460 en grandària i mida llavors actualitzat. 791 00:42:52,460 --> 00:42:57,850 En aquest cas, estem decrementar la mida i després treure-se'l, desplomat que 792 00:42:57,850 --> 00:42:58,952 de la nostra matriu. 793 00:42:58,952 --> 00:42:59,826 Per què podríem fer això? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Així que si tinc una cosa en la meva pila, el que seria la mida de la meva en aquest moment? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> ¿I on és l'element 1 s'emmagatzema? 798 00:43:15,180 --> 00:43:17,621 A quin índex? 799 00:43:17,621 --> 00:43:18,120 AUDIÈNCIA: 0. 800 00:43:18,120 --> 00:43:19,060 ALTAVEU 1: 0. 801 00:43:19,060 --> 00:43:22,800 Així que en aquest cas, Sempre que hagi de fer sure-- 802 00:43:22,800 --> 00:43:27,630 en lloc de tornar mida de menys 1, ja que 803 00:43:27,630 --> 00:43:31,730 sap que és el nostre element serà emmagatzemat en un menor 804 00:43:31,730 --> 00:43:34,705 qualsevol que sigui la nostra mida és, aquesta només s'ocupa d'ella. 805 00:43:34,705 --> 00:43:36,080 És una manera una mica més elegant. 806 00:43:36,080 --> 00:43:41,220 I acabem la nostra decrementamos mida i després tornar mida. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> AUDIÈNCIA: Crec que només en general, ¿Per què aquesta estructura de dades 809 00:43:45,300 --> 00:43:47,800 ser beneficiós? 810 00:43:47,800 --> 00:43:50,660 >> ALTAVEU 1: Depèn del seu context. 811 00:43:50,660 --> 00:43:57,420 Així que per a alguns de la teoria, si està treballant con-- Acceptar, 812 00:43:57,420 --> 00:44:02,750 m'ho dius a mi veure si hi ha un u beneficiós que és beneficiós per a més de fora 813 00:44:02,750 --> 00:44:05,420 de CS. 814 00:44:05,420 --> 00:44:15,780 Amb piles, qualsevol moment vostè necessita fer un seguiment d'alguna cosa que 815 00:44:15,780 --> 00:44:20,456 és el més recentment afegit és quan vostè va a fer servir una pila. 816 00:44:20,456 --> 00:44:24,770 >> I no puc pensar en una bona exemple d'això en aquest moment. 817 00:44:24,770 --> 00:44:29,955 Però cada vegada que el més recent El que és més important per a vostè, 818 00:44:29,955 --> 00:44:31,705 que és quan una pila serà d'utilitat. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Estic tractant de pensar si hi ha un bon any per a això. 821 00:44:39,330 --> 00:44:43,720 Si penso en un bon exemple en la següent 20 minuts, que sens dubte li dirà. 822 00:44:43,720 --> 00:44:49,455 >> Però en general, si hi ha alguna cosa, com he dit més, on més recent 823 00:44:49,455 --> 00:44:52,470 és més important, això és on una pila entra en joc. 824 00:44:52,470 --> 00:44:58,860 Mentre que les cues són una mica el contrari. 825 00:44:58,860 --> 00:44:59,870 I tots els petits gossos. 826 00:44:59,870 --> 00:45:00,890 No és genial, oi? 827 00:45:00,890 --> 00:45:03,299 Em sento com que hauria només hi ha un vídeo conillet 828 00:45:03,299 --> 00:45:05,090 al bell mig de secció per a vostès 829 00:45:05,090 --> 00:45:08,870 perquè aquesta és una secció intensa. 830 00:45:08,870 --> 00:45:10,480 >> Així que una cua. 831 00:45:10,480 --> 00:45:12,710 Bàsicament una cua és com una línia. 832 00:45:12,710 --> 00:45:15,780 Vostès Estic segur que aquest ús quotidià, de la mateixa manera que en els nostres menjadors. 833 00:45:15,780 --> 00:45:18,160 Així que hem d'anar a i tenir a les nostres safates, estic 834 00:45:18,160 --> 00:45:21,260 Segur que has d'esperar en línia per lliscar o aconseguir el seu menjar. 835 00:45:21,260 --> 00:45:24,650 >> Així que la diferència aquí és que això és FIFO. 836 00:45:24,650 --> 00:45:30,090 Així que si LIFO l'última a entrar, primer terme, FIFO és primer a entrar, primer a sortir. 837 00:45:30,090 --> 00:45:33,400 Així que aquí és on el que poses el primer és el més important. 838 00:45:33,400 --> 00:45:35,540 Així que si estaves esperant en un line-- oi 839 00:45:35,540 --> 00:45:39,130 imagini si vostè va anar a anar a buscar el nou iPhone 840 00:45:39,130 --> 00:45:42,800 i era una pila on el última persona de la fila ho va aconseguir en primer lloc, 841 00:45:42,800 --> 00:45:44,160 persones matarien entre si. 842 00:45:44,160 --> 00:45:49,800 >> Així FIFO, estem tots molt familiar amb en el món real aquí, 843 00:45:49,800 --> 00:45:54,930 i tot té a veure amb la realitat espècie de recreació de tota aquesta línia 844 00:45:54,930 --> 00:45:56,900 i cues estructura. 845 00:45:56,900 --> 00:46:02,390 Així que mentre que amb la pila, tenim empenta i el pop. 846 00:46:02,390 --> 00:46:06,440 Amb una cua, tenim enqueue i treure de la cua. 847 00:46:06,440 --> 00:46:10,910 Així que, bàsicament, significa enqueue el va posar a la part del darrere, 848 00:46:10,910 --> 00:46:13,680 i mitjans dequeue prenen fora de la part davantera. 849 00:46:13,680 --> 00:46:18,680 Així que la nostra estructura de dades és un poc més complicat. 850 00:46:18,680 --> 00:46:21,060 Tenim un segon que cal seguir la pista. 851 00:46:21,060 --> 00:46:25,950 >> Així que sense el cap, aquest és exactament una pila, no? 852 00:46:25,950 --> 00:46:27,900 Aquesta és la mateixa estructura que una pila. 853 00:46:27,900 --> 00:46:32,480 L'única cosa diferent és que ara tenir aquest cap, que què et sembla 854 00:46:32,480 --> 00:46:34,272 es va a realitzar un seguiment de? 855 00:46:34,272 --> 00:46:35,510 >> AUDIÈNCIA: El primer. 856 00:46:35,510 --> 00:46:38,685 >> ALTAVEU 1: Dret, la El primer que ens vam posar en. 857 00:46:38,685 --> 00:46:41,130 El cap de la nostra cua. 858 00:46:41,130 --> 00:46:42,240 El que és primer a la fila. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Molt bé, així que si ho fem en cua. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Una vegada més, amb qualsevol de aquestes estructures de dades, 863 00:46:55,920 --> 00:46:59,760 ja que estem tractant amb una matriu, hem de comprovar si tenim espai. 864 00:46:59,760 --> 00:47:03,290 >> Això és una cosa així com dient-me vostès, si s'obre un arxiu, 865 00:47:03,290 --> 00:47:04,760 vostè necessita per comprovar nul·la. 866 00:47:04,760 --> 00:47:08,330 Amb qualsevol d'aquestes piles i les cues, que necessiten 867 00:47:08,330 --> 00:47:13,420 per veure si hi ha espai perquè som tractar amb una matriu de mida fixa, 868 00:47:13,420 --> 00:47:16,030 com veiem aquí-- 0, 1 tot fins a 5. 869 00:47:16,030 --> 00:47:20,690 Així que el que fem en aquest cas és xec per veure si encara tenim espai. 870 00:47:20,690 --> 00:47:23,110 És el nostre grandària menor que la capacitat? 871 00:47:23,110 --> 00:47:28,480 >> Si és així, tenim que el conservi en el seu la cua i actualitzem la nostra mida. 872 00:47:28,480 --> 00:47:30,250 Llavors, ¿quina podria ser la cua en aquest cas? 873 00:47:30,250 --> 00:47:32,360 No està escrit explícitament. 874 00:47:32,360 --> 00:47:33,380 Com podríem emmagatzemar? 875 00:47:33,380 --> 00:47:34,928 Quina seria la cua? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Així que anem a caminar a través d'aquest exemple. 878 00:47:40,190 --> 00:47:44,590 Així que aquesta és una matriu de mida 6, no? 879 00:47:44,590 --> 00:47:49,220 I tenim en aquest moment, el nostre grandària és 5. 880 00:47:49,220 --> 00:47:55,240 I quan ho posem en, va per entrar en el cinquè índex, ¿no? 881 00:47:55,240 --> 00:47:57,030 Així que emmagatzemar a la cua. 882 00:47:57,030 --> 00:48:05,600 >> Una altra forma d'escriure cua faria només sigui el nostre arsenal en l'índex de mida, no? 883 00:48:05,600 --> 00:48:07,560 Aquesta és la mida maig. 884 00:48:07,560 --> 00:48:11,490 El següent que es va a anar a 5. 885 00:48:11,490 --> 00:48:12,296 Fresc? 886 00:48:12,296 --> 00:48:13,290 Okay. 887 00:48:13,290 --> 00:48:16,350 Es posa una mica més complicat quan vam començar a jugar amb el cap. 888 00:48:16,350 --> 00:48:17,060 Sí? 889 00:48:17,060 --> 00:48:20,090 >> AUDIÈNCIA: Significa que hem de hauria declarat una matriu que 890 00:48:20,090 --> 00:48:23,880 va ser cinc elements de llarg i llavors estem afegint-hi? 891 00:48:23,880 --> 00:48:24,730 >> ALTAVEU 1: No. 892 00:48:24,730 --> 00:48:27,560 Així doncs, en aquest cas, es tracta d'una pila. 893 00:48:27,560 --> 00:48:31,760 Aquest seria declarat com una matriu de mida juny. 894 00:48:31,760 --> 00:48:37,120 I en aquest cas, només hi ha una plaça d'esquerra. 895 00:48:37,120 --> 00:48:42,720 >> Acceptar, de manera que una cosa és en aquest cas, si el nostre cap està a 0, 896 00:48:42,720 --> 00:48:45,270 llavors només podem afegir que en la mateixa mida. 897 00:48:45,270 --> 00:48:51,020 Però es posa una mica més complicat perquè en realitat, 898 00:48:51,020 --> 00:48:52,840 no tenen una diapositiva per això, així que vaig 899 00:48:52,840 --> 00:48:56,670 per dibuixar una perquè no és tan senzill una vegada que 900 00:48:56,670 --> 00:48:59,230 començar a desfer-se de les coses. 901 00:48:59,230 --> 00:49:03,920 Així que mentre que amb una pila perquè només hagi 902 00:49:03,920 --> 00:49:08,920 que preocupar-se pel que la mida és quan va a afegir alguna cosa sobre, 903 00:49:08,920 --> 00:49:15,710 amb una cua també ha de fer Assegureu-vos que el seu cap es comptabilitza, 904 00:49:15,710 --> 00:49:20,760 perquè una cosa divertida sobre les cues és que si vostè no està en capacitat, 905 00:49:20,760 --> 00:49:23,040 en realitat es pot fer que sigui embolicar al voltant. 906 00:49:23,040 --> 00:49:28,810 >> Acceptar, de manera que un cosa-- oh, això és terrible guix. 907 00:49:28,810 --> 00:49:31,815 Una cosa a tenir en compte és el cas. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Farem només cinc. 910 00:49:37,140 --> 00:49:41,810 OK, així que anem a diuen que el cap està aquí. 911 00:49:41,810 --> 00:49:46,140 Aquesta és 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> El cap hi és, i si us plau tingui coses a ells. 913 00:49:54,210 --> 00:49:58,340 I volem afegir alguna cosa, no? 914 00:49:58,340 --> 00:50:01,170 Així que el que necessitem saber és que el cap és sempre 915 00:50:01,170 --> 00:50:05,620 va a moure d'un costat a llavors bucle al voltant, d'acord? 916 00:50:05,620 --> 00:50:10,190 >> Així que aquesta cua disposa d'espai, no? 917 00:50:10,190 --> 00:50:13,950 Té espai en el principi, classe en cas contrari d'això. 918 00:50:13,950 --> 00:50:17,920 Així que el que hem de fer és que de calcular la cua. 919 00:50:17,920 --> 00:50:20,530 Si vostè sap que el seu el cap no s'ha mogut, cua 920 00:50:20,530 --> 00:50:24,630 és només la seva matriu a l'índex de la mida. 921 00:50:24,630 --> 00:50:30,000 >> Però en realitat, si vostè està utilitzant una cua, el seu cap, probablement s'està actualitzant. 922 00:50:30,000 --> 00:50:33,890 Així que el que cal fer és realment calcular la cua. 923 00:50:33,890 --> 00:50:39,990 Així que el que fem és la fórmula aquí, que vaig a deixar-te 924 00:50:39,990 --> 00:50:42,680 nois pensen sobre, i llavors anem a parlar-ne. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Així que aquesta és la capacitat. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Així que això ho farà realitat li donarà una forma de fer-ho. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Com que en aquest cas, ¿què? 931 00:51:04,330 --> 00:51:09,205 La nostra cap està en 1, la nostra mida és 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Si mod que per 5, obtenim 0, que és on ha d'ingressar la mateixa. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Així que en el següent cas, si haguéssim de fer això, 936 00:51:26,080 --> 00:51:33,390 diem, OK, anem a treure de la cua alguna cosa. 937 00:51:33,390 --> 00:51:34,390 Ens dequeue això. 938 00:51:34,390 --> 00:51:37,740 Prenem un cop d'ull a aquest element, no? 939 00:51:37,740 --> 00:51:47,930 >> I ara el nostre cap està assenyalant aquí, i volem afegir en una altra cosa. 940 00:51:47,930 --> 00:51:52,470 Aquesta és bàsicament la part de darrere de la nostra línia, oi? 941 00:51:52,470 --> 00:51:55,450 Les cues poden embolicar al voltant de la matriu. 942 00:51:55,450 --> 00:51:57,310 Aquesta és una de les principals diferències. 943 00:51:57,310 --> 00:51:58,780 Piles, no pots fer això. 944 00:51:58,780 --> 00:52:01,140 >> Amb les cues, es pot perquè tot el que importa 945 00:52:01,140 --> 00:52:03,940 és que vostè sap el que es va afegir més recentment. 946 00:52:03,940 --> 00:52:10,650 Ja que tot serà afegit a aquesta direcció cap a l'esquerra, en aquest cas, 947 00:52:10,650 --> 00:52:16,480 i després embolicar al voltant, vostè pot seguir posant en nous elements 948 00:52:16,480 --> 00:52:18,830 a la part davantera de la matriu perquè no és realment 949 00:52:18,830 --> 00:52:20,640 la part davantera de la matriu més. 950 00:52:20,640 --> 00:52:26,320 Vostè pot pensar en l'inici de la matriu com quan el cap és en realitat. 951 00:52:26,320 --> 00:52:29,710 >> Així que aquesta fórmula és com calcular la seva cua. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Això té sentit? 954 00:52:35,610 --> 00:52:36,110 Okay. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 Acceptar, treure de la cua, i després vostès tenen 10 minuts 957 00:52:44,040 --> 00:52:48,840 en fer qualsevol preguntes aclaridores que vols, perquè sé que és una bogeria. 958 00:52:48,840 --> 00:52:51,980 >> Molt bé, pel que en la mateixa manera- No sé si vostès es va donar compte, 959 00:52:51,980 --> 00:52:53,450 però CS té a veure amb els patrons. 960 00:52:53,450 --> 00:52:57,370 Les coses són més o menys la mateix, només amb petits retocs. 961 00:52:57,370 --> 00:52:58,950 Així mateix aquí. 962 00:52:58,950 --> 00:53:04,040 Hem de comprovar per veure si en realitat tenen alguna cosa en la nostra cua, no? 963 00:53:04,040 --> 00:53:05,960 Digui, OK, és la nostra mida més gran que 0? 964 00:53:05,960 --> 00:53:06,730 Refredar. 965 00:53:06,730 --> 00:53:10,690 >> Si ho fem, llavors ens movem nostre cap, que és el que acaba de demostrar aquí. 966 00:53:10,690 --> 00:53:13,870 Actualitzem el nostre cap per ser un més. 967 00:53:13,870 --> 00:53:18,390 I després ens decrementamos la nostra mida i tornar l'element. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Hi ha molt més concret codi en study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 i jo recomano anar a través d'ell si tens temps, 971 00:53:29,440 --> 00:53:30,980 fins i tot si és només un pseudo-codi. 972 00:53:30,980 --> 00:53:35,980 I si vostès volen parlar a través de que amb mi un a un, si us plau em deixa 973 00:53:35,980 --> 00:53:37,500 saber. 974 00:53:37,500 --> 00:53:38,770 Jo estaria encantat de. 975 00:53:38,770 --> 00:53:42,720 Les estructures de dades, si vostè pren CS 124, podràs 976 00:53:42,720 --> 00:53:47,830 saben que les estructures de dades es posen molt diversió i això acaba de començar. 977 00:53:47,830 --> 00:53:50,350 >> Així que sé que és difícil. 978 00:53:50,350 --> 00:53:51,300 Està bé. 979 00:53:51,300 --> 00:53:52,410 Lluitem. 980 00:53:52,410 --> 00:53:53,630 Jo encara ho faig. 981 00:53:53,630 --> 00:53:56,660 Així que no et preocupis massa per això. 982 00:53:56,660 --> 00:54:02,390 >> Però això és bàsicament el seu Curs accelerat en les estructures de dades. 983 00:54:02,390 --> 00:54:03,400 Sé que és molt. 984 00:54:03,400 --> 00:54:06,860 Hi ha una cosa que ens li agradaria anar una altra vegada? 985 00:54:06,860 --> 00:54:09,400 Qualsevol cosa que volem parlar a través de? 986 00:54:09,400 --> 00:54:10,060 Sí? 987 00:54:10,060 --> 00:54:16,525 >> AUDIÈNCIA: Per a aquest exemple, pel que la nova cua és a 0 sobre això? 988 00:54:16,525 --> 00:54:17,150 ALTAVEU 1: Sí. 989 00:54:17,150 --> 00:54:18,230 AUDIÈNCIA: OK. 990 00:54:18,230 --> 00:54:24,220 Així que anar a través de, tindries 1 més 4 o-- 991 00:54:24,220 --> 00:54:27,671 >> ALTAVEU 1: Pel que estaven dient, quan volem anar a fer això una altra vegada? 992 00:54:27,671 --> 00:54:28,296 AUDIÈNCIA: Sí. 993 00:54:28,296 --> 00:54:38,290 Així que si estàs calculant fora-- on són que el càlcul de la cua d'en això? 994 00:54:38,290 --> 00:54:44,260 >> ALTAVEU 1: Així que la cua Estava en-- vaig canviar això. 995 00:54:44,260 --> 00:54:52,010 Així que en aquest exemple aquí, això era la matriu que estem veient, d'acord? 996 00:54:52,010 --> 00:54:54,670 Així que tenim coses en 1, 2, 3, i 4. 997 00:54:54,670 --> 00:55:05,850 Així que tenim el nostre cap és igual a 1 en aquest punt, i la nostra mida és igual a 4 998 00:55:05,850 --> 00:55:07,050 en aquest punt, no? 999 00:55:07,050 --> 00:55:08,960 >> Vostè accepta que tot és el cas? 1000 00:55:08,960 --> 00:55:14,620 Així que fem el cap, més la mida, el que ens dóna 5, i després ens MOD per 5. 1001 00:55:14,620 --> 00:55:20,690 Obtenim 0, el que ens diu que 0 és On està la nostra cua, on tenim espai. 1002 00:55:20,690 --> 00:55:22,010 >> AUDIÈNCIA: Què és un casquet? 1003 00:55:22,010 --> 00:55:23,520 >> ALTAVEU 1: La capacitat. 1004 00:55:23,520 --> 00:55:24,020 Ho sento. 1005 00:55:24,020 --> 00:55:29,640 Així que aquest és la mida del seu arsenal. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Sí? 1008 00:55:36,047 --> 00:55:39,210 >> AUDIÈNCIA: [inaudible] abans tornem l'element? 1009 00:55:39,210 --> 00:55:46,270 >> ALTAVEU 1: Així que movem el dirigir-se o tornar al moment? 1010 00:55:46,270 --> 00:55:52,680 Així que si ens movem un, disminuir la mida? 1011 00:55:52,680 --> 00:55:54,150 Espereu. 1012 00:55:54,150 --> 00:55:55,770 Definitivament em vaig oblidar una altra. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 No importa. 1015 00:56:01,990 --> 00:56:04,980 No hi ha altra fórmula. 1016 00:56:04,980 --> 00:56:09,980 Sí, vostè vol tornar el cap i després es va moure cap enrere. 1017 00:56:09,980 --> 00:56:13,270 >> AUDIÈNCIA: OK, perquè en aquest punt, el cap estava a 0, 1018 00:56:13,270 --> 00:56:18,452 i després vol tornar l'índex 0 i després fer la cap 1? 1019 00:56:18,452 --> 00:56:19,870 >> ALTAVEU 1: Dret. 1020 00:56:19,870 --> 00:56:22,820 Crec que hi ha una altra fórmula una mica així com això. 1021 00:56:22,820 --> 00:56:26,970 Jo no el tinc a la part superior del meu cap com No vull donar-te la equivocada. 1022 00:56:26,970 --> 00:56:35,470 Però crec que és perfectament vàlid per exemple, Acceptar, guardi aquest element-- el que sigui 1023 00:56:35,470 --> 00:56:40,759 element de cap és-- decrementar la seva mida, moure el seu cap una altra vegada, i la tornada 1024 00:56:40,759 --> 00:56:41,800 qualsevol que sigui aquest element és. 1025 00:56:41,800 --> 00:56:44,760 Això és perfectament vàlid. 1026 00:56:44,760 --> 00:56:45,260 Okay. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Sento que això no és com el most-- no estàs 1029 00:56:53,560 --> 00:56:55,740 sortirà d'aquí com, sí, ja sé intents. 1030 00:56:55,740 --> 00:56:56,880 Ho tinc tot. 1031 00:56:56,880 --> 00:56:57,670 Això està bé. 1032 00:56:57,670 --> 00:57:00,200 Prometo. 1033 00:57:00,200 --> 00:57:05,240 Però les estructures de dades són una cosa que que es necessita una gran quantitat de temps per acostumar. 1034 00:57:05,240 --> 00:57:10,010 Probablement un dels més difícils les coses, crec que, en el curs. 1035 00:57:10,010 --> 00:57:15,330 >> Així que definitivament pren repetició i mirant at-- I 1036 00:57:15,330 --> 00:57:20,050 No sabia realment llistes enllaçades fins que em vaig fer massa amb ells, 1037 00:57:20,050 --> 00:57:22,550 de la mateixa manera que no ho vaig fer realment entendre punters 1038 00:57:22,550 --> 00:57:27,040 fins que m'he hagut de ensenyar-la per a dos anys i fer els meus propis conjunts de processadors amb ell. 1039 00:57:27,040 --> 00:57:28,990 Es necessita molt de la reiteració i el temps. 1040 00:57:28,990 --> 00:57:32,600 I, finalment, serà de tipus clic. 1041 00:57:32,600 --> 00:57:36,320 >> Però mentrestant, si vostè té tipus d'una comprensió d'alt nivell del que 1042 00:57:36,320 --> 00:57:39,321 aquests fan, els seus pros i que és el que cons-- 1043 00:57:39,321 --> 00:57:41,820 que realment tendeixen a emfatitzar, especialment en el curs d'introducció. 1044 00:57:41,820 --> 00:57:45,511 Igual que, per què hauríem d'utilitzar una oportunitat més d'una matriu? 1045 00:57:45,511 --> 00:57:48,010 Igual que, quins són els aspectes positius i negatius de cada un d'aquests? 1046 00:57:48,010 --> 00:57:51,610 >> I la comprensió dels avantatges i desavantatges entre cadascuna d'aquestes estructures 1047 00:57:51,610 --> 00:57:54,910 és el que és molt més important en aquest moment. 1048 00:57:54,910 --> 00:57:58,140 Hi pot haver un boig o dues preguntes que és 1049 00:57:58,140 --> 00:58:03,710 demanarà aplicar empenta o implementar pop o de posada en cua i treure de la cua. 1050 00:58:03,710 --> 00:58:07,340 Però en la seva major part, havent de major comprensió de nivell i més 1051 00:58:07,340 --> 00:58:09,710 d'una comprensió intuïtiva és més important que en realitat 1052 00:58:09,710 --> 00:58:11,250 ser capaç de posar-ho en pràctica. 1053 00:58:11,250 --> 00:58:14,880 >> Seria realment impressionant si tots vostès podria sortir i anar implementar un intent, 1054 00:58:14,880 --> 00:58:19,720 però entenem que no és necessàriament el més raonable en aquest moment. 1055 00:58:19,720 --> 00:58:23,370 Però vostè pot en el seu conjunt de processadors, si vols per, a continuació, que obtindrà la pràctica, 1056 00:58:23,370 --> 00:58:27,200 i després potser vostè realment entendre-ho. 1057 00:58:27,200 --> 00:58:27,940 Sí? 1058 00:58:27,940 --> 00:58:30,440 >> AUDIÈNCIA: OK, així que quins són ens referim a utilitzar en el conjunt de processadors? 1059 00:58:30,440 --> 00:58:31,916 He d'utilitzar un d'ells? 1060 00:58:31,916 --> 00:58:32,540 ALTAVEU 1: Sí. 1061 00:58:32,540 --> 00:58:34,199 Així que vostè té la seva opció. 1062 00:58:34,199 --> 00:58:36,740 Suposo que en aquest cas, podem parlar del conjunt de processadors una mica 1063 00:58:36,740 --> 00:58:40,480 perquè em vaig trobar a través d'aquests. 1064 00:58:40,480 --> 00:58:47,779 Així que en el seu conjunt de processadors, que tingui el seu elecció d'intents o taules hash. 1065 00:58:47,779 --> 00:58:49,570 Algunes persones intentaran i l'ús de filtres de floració, 1066 00:58:49,570 --> 00:58:51,840 però els que tècnicament no són correctes. 1067 00:58:51,840 --> 00:58:55,804 Causa de la seva naturalesa probabilística, donen falsos positius vegades. 1068 00:58:55,804 --> 00:58:57,095 Són mirada fresca a, però. 1069 00:58:57,095 --> 00:58:59,030 Molt recomanable buscar en ells almenys. 1070 00:58:59,030 --> 00:59:03,260 Però vostè té la seva opció entre una taula hash i una oportunitat. 1071 00:59:03,260 --> 00:59:06,660 I això serà on es carrega en el seu diccionari. 1072 00:59:06,660 --> 00:59:09,230 >> I tu hauràs de triar la seva funció hash, 1073 00:59:09,230 --> 00:59:13,420 haurà de triar el nombre de cubs que té, i que variarà. 1074 00:59:13,420 --> 00:59:17,440 Igual que si vostè té més cubs, potser que va a córrer més ràpid. 1075 00:59:17,440 --> 00:59:22,790 Però potser vostè està perdent una gran quantitat d'espai d'aquesta manera, però. 1076 00:59:22,790 --> 00:59:26,320 Has de entendre-ho. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> AUDIÈNCIA: Vostè va dir abans que podem utilitzar altres funcions hash, 1079 00:59:29,875 --> 00:59:31,750 que nosaltres no hem de crear una funció hash? 1080 00:59:31,750 --> 00:59:32,666 >> ALTAVEU 1: Sí, correcte. 1081 00:59:32,666 --> 00:59:38,150 Així que, literalment, de la seva funció de control, com google "funció hash" 1082 00:59:38,150 --> 00:59:40,770 i buscar alguns més fresc. 1083 00:59:40,770 --> 00:59:43,250 No s'espera construir les seves pròpies funcions hash. 1084 00:59:43,250 --> 00:59:46,100 La gent passa el seu tesi sobre aquestes coses. 1085 00:59:46,100 --> 00:59:50,250 >> Així que no et preocupis per la construcció de la seva pròpia. 1086 00:59:50,250 --> 00:59:53,350 Trobar una línia per començar. 1087 00:59:53,350 --> 00:59:56,120 Alguns d'ells cal manipular una mica 1088 00:59:56,120 --> 00:59:59,430 per fer tipus de retorn segur coincideixen i tot això, així que en principi, 1089 00:59:59,430 --> 01:00:02,420 Jo recomano fer servir alguna cosa molt fàcil que potser només 1090 01:00:02,420 --> 01:00:04,680 hashes a la primera lletra. 1091 01:00:04,680 --> 01:00:08,760 I a continuació, una vegada que hagi de treballar, la incorporació d'una funció hash més fresc. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> AUDIÈNCIA: Vols provar un ésser o eficient, però només més difícil, com-- 1094 01:00:13,020 --> 01:00:15,880 >> ALTAVEU 1: Així que un intent, crec, és intuïtivament difícil d'implementar 1095 01:00:15,880 --> 01:00:18,310 però és molt ràpid. 1096 01:00:18,310 --> 01:00:20,620 No obstant això, ocupa més espai. 1097 01:00:20,620 --> 01:00:25,270 Una vegada més, pot optimitzar tant dels de diferents maneres i hi ha maneres A-- 1098 01:00:25,270 --> 01:00:26,770 AUDIÈNCIA: Com estem qualificats en això? 1099 01:00:26,770 --> 01:00:27,540 Es matter-- 1100 01:00:27,540 --> 01:00:29,164 >> ALTAVEU 1: Així que tu ets classifiquen de manera normal. 1101 01:00:29,164 --> 01:00:31,330 Vostè va a ser classificat en el disseny. 1102 01:00:31,330 --> 01:00:36,020 Sigui quina sigui la forma en què ho fa, vostè vol assegureu-vos que és tan elegant com pot ser 1103 01:00:36,020 --> 01:00:38,610 i el més eficient possible. 1104 01:00:38,610 --> 01:00:41,950 Però si vostè escull un provar o haixix taula, mentre funciona, 1105 01:00:41,950 --> 01:00:45,350 estem contents amb això. 1106 01:00:45,350 --> 01:00:48,370 I si feu servir alguna cosa que hashes a la primera lletra, això està bé, 1107 01:00:48,370 --> 01:00:51,410 com a tal vegada com-disseny intel·ligent. 1108 01:00:51,410 --> 01:00:53,410 També estem arribant a la punt en aquest semester-- 1109 01:00:53,410 --> 01:00:55,340 No sé si vostè nois noticed-- si estàs 1110 01:00:55,340 --> 01:00:58,780 graus PSet declinen una mica a causa del disseny i altres coses, 1111 01:00:58,780 --> 01:00:59,900 que està perfectament bé. 1112 01:00:59,900 --> 01:01:02,960 S'està fent a un punt en què el seu els programes són cada vegada més complicat. 1113 01:01:02,960 --> 01:01:04,830 Hi ha més llocs es pot millorar. 1114 01:01:04,830 --> 01:01:06,370 >> Així que és perfectament normal. 1115 01:01:06,370 --> 01:01:08,810 No és que vostè és fent pitjor en el seu conjunt de processadors. 1116 01:01:08,810 --> 01:01:11,885 És només que estem sent més dur per a vostè ara. 1117 01:01:11,885 --> 01:01:13,732 Així que tothom està sentint. 1118 01:01:13,732 --> 01:01:14,940 Acabo qualificar tots els seus conjunts de processadors. 1119 01:01:14,940 --> 01:01:16,490 Sé que tothom està sentint. 1120 01:01:16,490 --> 01:01:19,600 >> Així que no et preocupis per això. 1121 01:01:19,600 --> 01:01:23,580 I si vostè té alguna pregunta sobre conjunts de processadors anteriors o maneres en què pot millorar, 1122 01:01:23,580 --> 01:01:27,760 Tracte i comento l'específic llocs, però de vegades ja és tard 1123 01:01:27,760 --> 01:01:30,840 i em canso. 1124 01:01:30,840 --> 01:01:34,885 Hi ha altres coses sobre estructures de dades? 1125 01:01:34,885 --> 01:01:37,510 Estic segur que els nois realment no vull parlar-ne mai més, 1126 01:01:37,510 --> 01:01:42,650 però si hi ha, estic feliç de anar-hi, així com qualsevol cosa 1127 01:01:42,650 --> 01:01:45,580 de conferència el passat setmana o la setmana passada. 1128 01:01:45,580 --> 01:01:51,580 >> Sé que la setmana passada va ser tot examen, per la qual cosa podem haver saltat alguna opinió 1129 01:01:51,580 --> 01:01:54,190 de conferència. 1130 01:01:54,190 --> 01:01:58,230 Alguna altra pregunta que puc respondre? 1131 01:01:58,230 --> 01:01:59,350 Bé, bé. 1132 01:01:59,350 --> 01:02:02,400 Bé, vostès sortir 15 minuts abans. 1133 01:02:02,400 --> 01:02:08,370 >> Espero que això era semi-útil, com a mínim, i vaig a veure vostès la setmana que ve, 1134 01:02:08,370 --> 01:02:12,150 o les hores d'oficina dijous. 1135 01:02:12,150 --> 01:02:15,285 Hi ha sol·licituds d'aperitius per a la setmana que ve, que és la cosa? 1136 01:02:15,285 --> 01:02:17,459 Perquè em vaig oblidar de caramel avui. 1137 01:02:17,459 --> 01:02:19,750 I he portat dolços últim setmana, però que era el Dia de Colom, 1138 01:02:19,750 --> 01:02:25,400 pel que no eren com sis persones que tenia quatre bosses de dolços a si mateixos. 1139 01:02:25,400 --> 01:02:28,820 Puc portar Starbursts de nou si ho desitja. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 Bé, sona bé. 1142 01:02:32,250 --> 01:02:35,050 Que tinguin un bon dia, nois. 1143 01:02:35,050 --> 01:02:39,510