1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID Malan: Molt bé. 3 00:00:12,250 --> 00:00:13,860 Benvingut de nou a CS50. 4 00:00:13,860 --> 00:00:16,190 Aquest és el començament de la setmana 8. 5 00:00:16,190 --> 00:00:21,320 I recordar que un problema conjunt maig va acabar amb una mica d'un desafiament. 6 00:00:21,320 --> 00:00:25,210 Així que suposant que recuperar tota la seva Els becaris d'ensenyament i fotografies de CA 7 00:00:25,210 --> 00:00:30,480 a l'arxiu card.raw, vostè és elegible trobar ara totes aquestes persones, i 8 00:00:30,480 --> 00:00:34,510 un afortunat guanyador a casa amb una d'aquestes coses, el moviment de salt 9 00:00:34,510 --> 00:00:37,450 dispositiu que es pot utilitzar per a la final de projectes, per exemple. 10 00:00:37,450 --> 00:00:39,860 >> Aquest, cada any, porta a una mica d'esgarrifança. 11 00:00:39,860 --> 00:00:43,480 I així el que vaig pensar en fer és compartir amb vostès algunes de les notes que tenen 12 00:00:43,480 --> 00:00:47,370 anat i vingut durant la llista de personal en els últims temps. 13 00:00:47,370 --> 00:00:51,110 Per exemple, la nit anterior, cita Fi de la cita, d'un dels empleats 14 00:00:51,110 --> 00:00:55,000 membres ", que acaba de tenir un cop estudiant a la porta per fer una foto amb mi. 15 00:00:55,000 --> 00:00:59,020 Assetjadors, els dic. "Va començar, bastant descriptiu i després ens mudem 16 00:00:59,020 --> 00:01:02,830 en què, una hora més tard, "Vaig tenir un estudiant m'espera després de la secció 17 00:01:02,830 --> 00:01:06,080 i tenia tots els nostres noms i fotos en alguns fulls de paper. "Molt bé. 18 00:01:06,080 --> 00:01:09,230 Així organitzada, però no tot el que esgarrifós encara. 19 00:01:09,230 --> 00:01:12,520 >> Llavors, "jo estava fora de la ciutat aquest cap de setmana, i quan vaig tornar, hi havia un a 20 00:01:12,520 --> 00:01:12,630 el meu 21 00:01:12,630 --> 00:01:16,740 dormitori. "[El] 22 00:01:16,740 --> 00:01:20,410 DAVID Malan: Pròxima cita d'un personal membre ", un estudiant va venir a casa meva a les 23 00:01:20,410 --> 00:01:25,330 Somerville a les 4 hores d'aquest matí. "Next personal: "Jo vaig arribar al meu hotel a San 24 00:01:25,330 --> 00:01:30,016 Francesc i estudiant estava esperant em al hall d'entrada amb tres càmeres rèflex digitals. " 25 00:01:30,016 --> 00:01:31,510 Tipus de cambra. 26 00:01:31,510 --> 00:01:34,980 "Ni tan sols estic en el personal d'aquest semestre, però un estudiant va irrompre a casa meva aquesta 27 00:01:34,980 --> 00:01:40,480 matí i registrat tot l'assumpte amb Google Glass. "I després, finalment, 28 00:01:40,480 --> 00:01:43,650 "Almenys 12 persones van ser àvidament esperant per mi quan vaig sortir de la meva 29 00:01:43,650 --> 00:01:44,800 llim, i després 30 00:01:44,800 --> 00:01:46,970 despertar. "Molt bé. 31 00:01:46,970 --> 00:01:57,690 Així que entre les fotografies, ja que pot recordar, són aquest home aquí, que et 32 00:01:57,690 --> 00:02:01,850 podria saber que Milo plàtan, que viu amb Lauren Carvalho, el nostre cap 33 00:02:01,850 --> 00:02:02,905 ensenyar Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, vine aquí noi. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Això sí, ell està utilitzant Google Glass, per la li mostrarem tot això després. 38 00:02:12,230 --> 00:02:16,190 Així que això és Milo si voleu fer una fotografia amb ell després. 39 00:02:16,190 --> 00:02:18,240 Si voleu cercar a l'audiència allà. 40 00:02:18,240 --> 00:02:19,430 D'acord. 41 00:02:19,430 --> 00:02:20,200 Aquestes són bones imatges. 42 00:02:20,200 --> 00:02:22,556 Bé, Milo plàtan. 43 00:02:22,556 --> 00:02:23,941 Oh, no facis això. 44 00:02:23,941 --> 00:02:29,020 >> [El] 45 00:02:29,020 --> 00:02:29,470 >> D'acord. 46 00:02:29,470 --> 00:02:34,550 Així que una paraula i després en el que s'acosta, perquè a mesura que comencem a la transició, 47 00:02:34,550 --> 00:02:38,410 aquesta setmana específicament, de C en un entorn de línia d'ordres del PHP i 48 00:02:38,410 --> 00:02:42,720 JavaScript i SQL i HTML i CSS en un entorn basat en web, estarem 49 00:02:42,720 --> 00:02:44,490 et equipa amb tot el un major coneixement de 50 00:02:44,490 --> 00:02:46,010 potencials projectes finals. 51 00:02:46,010 --> 00:02:49,240 Amb aquesta finalitat, el curs té un tradició de la celebració de seminaris que 52 00:02:49,240 --> 00:02:50,950 són sobre temes tangencials al curs. 53 00:02:50,950 --> 00:02:54,330 Molt relacionat amb la programació i desenvolupament d'aplicacions, etc, però 54 00:02:54,330 --> 00:02:57,010 no necessàriament explorat per propi pla d'estudis del curs. 55 00:02:57,010 --> 00:03:00,250 >> Així que si vostè pot estar interessat en una o més dels seminaris d'aquest any, 56 00:03:00,250 --> 00:03:02,530 registrar-se a cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Hi ha seminaris majors en cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 I en la llista fins al moment per a aquest any són increïbles aplicacions web amb Ruby on 59 00:03:10,620 --> 00:03:13,580 Riells, que és una alternativa llenguatge PHP. 60 00:03:13,580 --> 00:03:14,900 Lingüística Computacional. 61 00:03:14,900 --> 00:03:18,710 Introducció a la IOS, que és el plataforma que s'utilitza per l'iPhone i l' 62 00:03:18,710 --> 00:03:19,850 desenvolupament iPad. 63 00:03:19,850 --> 00:03:22,890 Habilitat per a aplicacions web, anem a cobrir , Però en aquest seminari, que anirà 64 00:03:22,890 --> 00:03:24,070 en més detalls. 65 00:03:24,070 --> 00:03:27,390 >> Leap Motion, així que ja tenim una mica de realitat dels nostres amics del Moviment Leap, 66 00:03:27,390 --> 00:03:29,160 la pròpia empresa, uneix-te a nosaltres. 67 00:03:29,160 --> 00:03:31,800 Demà, de fet, per proporcionar un seminari pràctic, si 68 00:03:31,800 --> 00:03:33,320 d'interès per a vostè. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, una tècnica alternativa per usant JavaScript no en un navegador, 70 00:03:38,770 --> 00:03:39,970 però en un servidor. 71 00:03:39,970 --> 00:03:42,110 Node.js, que és molt en aquest sentit també. 72 00:03:42,110 --> 00:03:43,650 Disseny elegant i Android. 73 00:03:43,650 --> 00:03:46,990 Android és una alternativa molt popular per iOS i Windows Phone 74 00:03:46,990 --> 00:03:48,790 i altres plataformes mòbils. 75 00:03:48,790 --> 00:03:51,180 I web Active Defense Security. 76 00:03:51,180 --> 00:03:54,590 >> Així que, de fet, si vol a participar en això, permetin-me 77 00:03:54,590 --> 00:03:55,840 prengui nota d'això. 78 00:03:55,840 --> 00:03:57,790 Estem molt contents de dir que els nostres amics de Salt 79 00:03:57,790 --> 00:03:59,140 Moviment, que és un inici - 80 00:03:59,140 --> 00:04:01,300 aquest dispositiu realment vi fa uns mesos - 81 00:04:01,300 --> 00:04:05,960 gentilment ha donat 30 d'aquests dispositius a la classe per a tants estudiants, si 82 00:04:05,960 --> 00:04:08,670 desitja demanar prestat el maquinari cap al final del semestre i utilitzar-lo per 83 00:04:08,670 --> 00:04:10,390 un projecte final real. 84 00:04:10,390 --> 00:04:11,890 Donen suport a diversos idiomes. 85 00:04:11,890 --> 00:04:16,040 Cap d'ells C, cap d'ells PHP, per la compte d'un o més d'aquests seminaris 86 00:04:16,040 --> 00:04:16,899 podria resultar d'interès. 87 00:04:16,899 --> 00:04:19,730 I tots ells serà filmat en el cas que vostè no és capaç 88 00:04:19,730 --> 00:04:21,380 assistir en persona. 89 00:04:21,380 --> 00:04:25,000 L'horari serà anunciat a través del correu electrònic a mesura que consolidem habitacions. 90 00:04:25,000 --> 00:04:28,460 >> I finalment, si vostè va a projects.cs.50.net, aquest és un lloc web 91 00:04:28,460 --> 00:04:31,450 mantenim cada any que us convidem gent de la comunitat, professors, 92 00:04:31,450 --> 00:04:36,420 departaments, el personal i els dos a l'exterior del CS50 a 93 00:04:36,420 --> 00:04:37,730 proposar idees de projectes. 94 00:04:37,730 --> 00:04:39,050 Activitats d'interès per als grups d'estudiants. 95 00:04:39,050 --> 00:04:40,600 Activitats d'interès per als departaments. 96 00:04:40,600 --> 00:04:43,990 Així que al seu torn no si vostè està lluitant la incertesa quant al que 97 00:04:43,990 --> 00:04:46,700 vostè li agradaria abordar. 98 00:04:46,700 --> 00:04:51,760 >> Així que l'última vegada que presentem un dubte estructura de dades més complexa del que havia 99 00:04:51,760 --> 00:04:53,300 vist en setmanes anteriors. 100 00:04:53,300 --> 00:04:56,550 Havíem estat utilitzant arrays força feliçment com un útil si 101 00:04:56,550 --> 00:04:58,160 estructura de dades simplista. 102 00:04:58,160 --> 00:05:00,570 A continuació, presentem aquests, que per descomptat estan llistes enllaçades. 103 00:05:00,570 --> 00:05:05,470 I el que va ser una de les motivacions per la introducció d'aquesta estructura de dades? 104 00:05:05,470 --> 00:05:06,930 Sí? 105 00:05:06,930 --> 00:05:07,250 Què és això? 106 00:05:07,250 --> 00:05:08,080 >> AUDIÈNCIA: mida dinàmic. 107 00:05:08,080 --> 00:05:09,040 >> DAVID Malan: mida dinàmic. 108 00:05:09,040 --> 00:05:11,890 Així, mentre que en conjunt, cal saber la seva grandària amb anticipació quan 109 00:05:11,890 --> 00:05:12,740 el situa. 110 00:05:12,740 --> 00:05:14,380 A la llista enllaçada, no ho fa ha de saber això. 111 00:05:14,380 --> 00:05:17,610 Vostè pot simplement malloc, o més en general, assignar un addicional 112 00:05:17,610 --> 00:05:20,720 node, per així dir-ho, ja que voleu inserir més dades. 113 00:05:20,720 --> 00:05:22,670 I el node no ha determinat significat. 114 00:05:22,670 --> 00:05:25,580 És només un terme genèric que descriu una mena de contenidor que estem 115 00:05:25,580 --> 00:05:29,610 utilitzant en la nostra estructura de dades per emmagatzemar algun element d'interès, que en aquest 116 00:05:29,610 --> 00:05:31,750 cas resulten ser nombres enters. 117 00:05:31,750 --> 00:05:33,160 >> Però sempre hi ha una solució de compromís. 118 00:05:33,160 --> 00:05:38,070 Així que vam arribar mides dinàmics de les dades estructura, però Quin preu que paguem? 119 00:05:38,070 --> 00:05:40,040 Quin és el costat negatiu de les llistes enllaçades? 120 00:05:40,040 --> 00:05:41,006 Sí? 121 00:05:41,006 --> 00:05:41,980 >> AUDIÈNCIA: Requereix més memòria. 122 00:05:41,980 --> 00:05:44,240 >> DAVID Malan: Requereix més la memòria, com exactament? 123 00:05:44,240 --> 00:05:46,440 >> AUDIÈNCIA: [inaudible]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID Malan: Exactament. 125 00:05:47,050 --> 00:05:50,460 Així que ara que hem punters prenent memòria addicional que prèviament 126 00:05:50,460 --> 00:05:53,040 no calia, ja que l'avantatge d'una matriu, per descomptat, és que 127 00:05:53,040 --> 00:05:54,860 tot és contigu, de tornada per tornar a l'esquena, el que 128 00:05:54,860 --> 00:05:56,380 li dóna accés aleatori. 129 00:05:56,380 --> 00:06:00,710 Perquè només mitjançant l'ús de claudàtors notació, o més tècnicament punter 130 00:06:00,710 --> 00:06:03,580 aritmètica, a més molt simple, es pot accedir a qualsevol 131 00:06:03,580 --> 00:06:05,700 elements de constant de temps. 132 00:06:05,700 --> 00:06:08,975 I de fet, que és una espècie d'al · lusió a un altre preu que estem pagant amb un 133 00:06:08,975 --> 00:06:09,760 llista enllaçada. 134 00:06:09,760 --> 00:06:13,890 >> Què passa amb el temps d'execució de alguna cosa així com la recerca, si vull 135 00:06:13,890 --> 00:06:17,270 trobar algun valor ia l'interior d'una llista enllaçada? 136 00:06:17,270 --> 00:06:20,290 El que es converteix en el meu temps corrent? 137 00:06:20,290 --> 00:06:21,560 Big O de n. 138 00:06:21,560 --> 00:06:24,060 Si s'ordena a? 139 00:06:24,060 --> 00:06:25,440 Què passa si l'estructura de dades està ordenat? 140 00:06:25,440 --> 00:06:28,640 Puc fer alguna cosa millor que grans O de n per a la recerca? 141 00:06:28,640 --> 00:06:31,700 No, perquè en el pitjor dels casos podria molt bé ser ordenats, però el nombre 142 00:06:31,700 --> 00:06:32,950 que busca pot ser gran. 143 00:06:32,950 --> 00:06:35,370 Pot ser que sigui el número 100, que podria passar a estar 144 00:06:35,370 --> 00:06:36,410 la forma a l'extrem. 145 00:06:36,410 --> 00:06:39,950 I pel fet que només es pot accedir a una vinculada llista d'aquesta aplicació per 146 00:06:39,950 --> 00:06:42,690 camí del seu primer node, ets encara una mica fora de sort. 147 00:06:42,690 --> 00:06:47,450 Vostè ha de travessar tot l'assumpte de principi a fi per tal de trobar 148 00:06:47,450 --> 00:06:49,150 aquest gran valor, com 100. 149 00:06:49,150 --> 00:06:51,350 O, per determinar si és ni tan sols existeix. 150 00:06:51,350 --> 00:06:55,960 >> Així que no podem fer el algoritme en una base de dades estructura que s'assembla a això? 151 00:06:55,960 --> 00:06:59,460 No podem fer una recerca binària, perquè recerca binària requereix que teníem 152 00:06:59,460 --> 00:07:00,740 d'accés aleatori. 153 00:07:00,740 --> 00:07:04,500 Podríem saltar d'un lloc a ubicació sense haver de seguir 154 00:07:04,500 --> 00:07:07,080 aquestes molles de pa en forma de tots aquests indicadors. 155 00:07:07,080 --> 00:07:08,300 >> Ara, com s'implementa això? 156 00:07:08,300 --> 00:07:12,830 Bé, si anem a la pantalla d'aquí, si podem tornar a implementar ràpidament aquestes dades 157 00:07:12,830 --> 00:07:13,440 estructura - 158 00:07:13,440 --> 00:07:15,670 la meva escriptura no és tot el que molt bé aquí, però ho intentarem. 159 00:07:15,670 --> 00:07:22,030 Typedef struct Així, i el que van fer I vol anomenar aquesta cosa aquí? 160 00:07:22,030 --> 00:07:22,960 Node. 161 00:07:22,960 --> 00:07:24,580 Així que vaig a que puguem començar. 162 00:07:24,580 --> 00:07:27,860 I ara, què ha d'estar dins del l'estructura de dades perquè individualment 163 00:07:27,860 --> 00:07:28,430 llista enllaçada? 164 00:07:28,430 --> 00:07:29,950 Quants camps? 165 00:07:29,950 --> 00:07:30,450 >> Així que dos. 166 00:07:30,450 --> 00:07:31,570 Un d'ells és bastant fàcil. 167 00:07:31,570 --> 00:07:33,050 Així int n. 168 00:07:33,050 --> 00:07:35,930 I podríem anomenar n tot el que vulguem, però ha de ser un int si estem 169 00:07:35,930 --> 00:07:37,660 implementació d'una llista enllaçada de sencers. 170 00:07:37,660 --> 00:07:41,920 I ara el que fa el segon camp ha de ser? 171 00:07:41,920 --> 00:07:43,460 Struct node *. 172 00:07:43,460 --> 00:07:50,570 Així que si ho faig struct node *, i després També podeu trucar a això el que vulgui, 173 00:07:50,570 --> 00:07:53,510 però només per ser clars Trucaré al costat, com ho hem estat fent. 174 00:07:53,510 --> 00:07:55,270 I després vaig a tancar els meus claus. 175 00:07:55,270 --> 00:08:00,700 >> I ara, com l'última vegada, Vaig posar node aquí. 176 00:08:00,700 --> 00:08:03,830 Però si estic declarant això és com una node, per què em molesta ser tan 177 00:08:03,830 --> 00:08:07,320 detallat aquí a la declaració struct node * següent, en lloc 178 00:08:07,320 --> 00:08:09,210 a sol node * següent? 179 00:08:09,210 --> 00:08:09,904 Sí? 180 00:08:09,904 --> 00:08:12,810 >> AUDIÈNCIA: [inaudible]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID Malan: Exactament. 182 00:08:14,050 --> 00:08:14,530 Exactament. 183 00:08:14,530 --> 00:08:18,320 A causa C realment et porta literalment i només veu la definició de node 184 00:08:18,320 --> 00:08:21,230 fins aquí, no es pot referir-s'hi aquí. 185 00:08:21,230 --> 00:08:24,760 Així que tenim aquesta classe de preventiu declaració aquí, que és el que 186 00:08:24,760 --> 00:08:25,390 més detallat. 187 00:08:25,390 --> 00:08:27,810 Struct node, que significa ara podem accedir-hi 188 00:08:27,810 --> 00:08:29,760 a l'interior de l'estructura de dades. 189 00:08:29,760 --> 00:08:33,370 >> I en un a part, perquè es tracta d' cada vegada una mica més subjectiva ara, 190 00:08:33,370 --> 00:08:36,230 l'estrella tècnicament pot anar aquí, pot anar aquí, pot 191 00:08:36,230 --> 00:08:37,179 fins i tot anar en el medi. 192 00:08:37,179 --> 00:08:39,890 Hem adoptat, a la guia d'estil per a el curs, la convenció de posar 193 00:08:39,890 --> 00:08:42,299 l'estrella junt amb les dades tipus, que en aquest cas, 194 00:08:42,299 --> 00:08:43,460 seria node d'estructura. 195 00:08:43,460 --> 00:08:46,620 Però adonar-se una gran quantitat de llibres de text i referències en línia, vostè pot ser fet 196 00:08:46,620 --> 00:08:48,450 veure que a l'altra banda. 197 00:08:48,450 --> 00:08:52,200 No obstant això, només s'adonen que tant en realitat treballa i ha de ser simplement 198 00:08:52,200 --> 00:08:52,970 consistent. 199 00:08:52,970 --> 00:08:53,580 >> Està bé. 200 00:08:53,580 --> 00:08:55,630 Així que això va ser la nostra declaració de node d'estructura. 201 00:08:55,630 --> 00:08:59,430 Però després vam començar a fer més coses sofisticades. 202 00:08:59,430 --> 00:09:03,410 Per exemple, vam decidir introduir alguna cosa així com una taula hash. 203 00:09:03,410 --> 00:09:08,160 Així que aquí està una taula hash de grandària n, indexada des de 0 a la part superior esquerra a n 204 00:09:08,160 --> 00:09:09,690 menys d'1 en la part inferior esquerra. 205 00:09:09,690 --> 00:09:11,640 Això podria ser un hash taula per a res. 206 00:09:11,640 --> 00:09:15,340 Però, quin tipus de coses què parlem sobre l'ús d'una taula hash? 207 00:09:15,340 --> 00:09:18,370 Emmagatzematge de què? 208 00:09:18,370 --> 00:09:18,800 >> Noms. 209 00:09:18,800 --> 00:09:20,870 Podríem fer noms com vam fer l'última vegada. 210 00:09:20,870 --> 00:09:22,200 I realment, pot emmagatzemar qualsevol cosa. 211 00:09:22,200 --> 00:09:24,640 I anem a veure això de nou en PHP i JavaScript. 212 00:09:24,640 --> 00:09:28,550 Una taula hash és una bona espècie de Suïssa Navalla que li permet emmagatzemar 213 00:09:28,550 --> 00:09:33,690 gairebé tot el que vulguis dins d' que mitjançant l'associació de tecles amb els valors. 214 00:09:33,690 --> 00:09:34,770 Tecles amb valors. 215 00:09:34,770 --> 00:09:37,800 >> Ara bé, en aquest cas simple, el nostre claus són només números. 216 00:09:37,800 --> 00:09:40,380 Estem implementant un hash taula com una matriu. 217 00:09:40,380 --> 00:09:43,500 I així les claus són 0, 1, 2, i així successivament. 218 00:09:43,500 --> 00:09:47,200 I així nosaltres, com a éssers humans, va decidir el passat setmana que vostè sap què, si estem 219 00:09:47,200 --> 00:09:50,410 va a emmagatzemar noms, anem a arbitrària, però bastant raonable, 220 00:09:50,410 --> 00:09:54,680 assumir que Alice, una Un nom, només serà indexada en 0. 221 00:09:54,680 --> 00:09:58,030 I Bob, el nom de B, s'indexarà a 1, i així successivament. 222 00:09:58,030 --> 00:10:02,490 Així que vam tenir una correspondència entre les entrades, que són cadenes, i el hash 223 00:10:02,490 --> 00:10:04,560 llocs, que són nombres. 224 00:10:04,560 --> 00:10:07,740 >> Per tant aquest procés es coneix generalment com una funció hash, i vostè pot realment 225 00:10:07,740 --> 00:10:09,130 implementar en el codi. 226 00:10:09,130 --> 00:10:12,080 Si volgués aplicar una funció hash que fa exactament el que 227 00:10:12,080 --> 00:10:17,070 s'acaba de descriure de l'última vegada, jo podria declarar una funció que pren com 228 00:10:17,070 --> 00:10:18,330 d'entrada, per exemple - 229 00:10:18,330 --> 00:10:22,190 i farem això en aquest pantalla per aquí. 230 00:10:22,190 --> 00:10:26,180 Si volgués aplicar un hash funció, jo podria dir 231 00:10:26,180 --> 00:10:27,410 alguna cosa com això. 232 00:10:27,410 --> 00:10:29,030 >> Es va a tornar un int. 233 00:10:29,030 --> 00:10:33,600 Serà anomenat hash, i és va a acceptar com a argument un 234 00:10:33,600 --> 00:10:38,920 cadena, o podem ser més apropiat ara, i dir char *, l'anomenarem s. 235 00:10:38,920 --> 00:10:43,840 I després, aquesta funció té a veure, en última instància, es torna un int. 236 00:10:43,840 --> 00:10:45,990 Ara, com es fa això podria no ser tan clara. 237 00:10:45,990 --> 00:10:49,510 Vaig a posar en pràctica això sense cap forma de comprovació d'errors en aquests moments. 238 00:10:49,510 --> 00:10:55,740 Jo només vaig a dir a cegues, torneu el que estigui a escaire s 0, almenys, 239 00:10:55,740 --> 00:10:58,850 diguem, la capital un punt i coma. 240 00:10:58,850 --> 00:10:59,960 >> Totalment trencat. 241 00:10:59,960 --> 00:11:02,620 No és perfecte, perquè un, el que si s és nul? 242 00:11:02,620 --> 00:11:04,000 Les coses dolentes van a passar. 243 00:11:04,000 --> 00:11:07,940 Dos, i si la primera lletra en aquest nom no és una lletra majúscula? 244 00:11:07,940 --> 00:11:09,860 Això no va a girar fos ben tampoc. 245 00:11:09,860 --> 00:11:11,970 Pot ser que sigui una lletra minúscula o no una carta a tots. 246 00:11:11,970 --> 00:11:15,520 Així que totalment marge de millora, però aquesta és la idea bàsica. 247 00:11:15,520 --> 00:11:19,010 >> El que descrivim la setmana passada verbalment un procés d'assignació d'Alice 248 00:11:19,010 --> 00:11:23,360 0 a 1 i Bob poden expressar sens dubte més formulaically com C 249 00:11:23,360 --> 00:11:24,320 funcionar aquí. 250 00:11:24,320 --> 00:11:28,630 Crida de nou hash, pren una cadena com d'entrada, i llavors d'alguna manera fa una mica 251 00:11:28,630 --> 00:11:31,020 amb aquesta entrada per produir una sortida. 252 00:11:31,020 --> 00:11:34,130 No gaire diferent de la nostra descripció quadre negre el que hem fet sempre. 253 00:11:34,130 --> 00:11:36,550 No sé com podria ser treball sota de la caputxa. 254 00:11:36,550 --> 00:11:40,120 >> Per butlletí de problemes 6, un dels reptes és perquè vostè decideixi què 255 00:11:40,120 --> 00:11:41,920 Serà la seva funció hash? 256 00:11:41,920 --> 00:11:45,760 Què va a estar dins d'aquest negre caixa, i, presumiblement, serà un 257 00:11:45,760 --> 00:11:50,380 poc més interessant que això, i definitivament més propens a errors 258 00:11:50,380 --> 00:11:53,180 comprovar que el particular aplicació. 259 00:11:53,180 --> 00:11:54,580 >> Però poden sorgir problemes, oi? 260 00:11:54,580 --> 00:11:57,760 Si tenim una estructura de dades com aquest un, el que és un dels problemes 261 00:11:57,760 --> 00:12:01,600 es pot executar en el temps a mesura que s'insereix més i més noms a la 262 00:12:01,600 --> 00:12:02,880 taula hash? 263 00:12:02,880 --> 00:12:04,630 Vostè aconsegueix col · lisions, oi? 264 00:12:04,630 --> 00:12:07,560 Què passa si vostè té Alice i Aaron, dues persones els noms passat 265 00:12:07,560 --> 00:12:08,190 començar amb A? 266 00:12:08,190 --> 00:12:11,660 Això planteja la pregunta, en què posar el segon com un nom? 267 00:12:11,660 --> 00:12:15,050 >> Bé, potser ingènuament, només cal posar on Bob pertany, però Bob és 268 00:12:15,050 --> 00:12:17,300 tipus de rosca si intenta inseriu el nom al costat i 269 00:12:17,300 --> 00:12:18,240 no hi ha lloc per a ell. 270 00:12:18,240 --> 00:12:21,400 Així que es podria posar Bob on Charlie és, i es pot imaginar això molt ràpidament 271 00:12:21,400 --> 00:12:23,020 delegar en una mica d'un desastre. 272 00:12:23,020 --> 00:12:25,600 Una cosa lineal en el final, on només has de buscar en tot l'assumpte 273 00:12:25,600 --> 00:12:28,190 a la recerca d'Alice o Bob o Aaron o Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Així que en comptes ens proposa, en lloc de linealment sondeig d'espais oberts 275 00:12:33,230 --> 00:12:36,450 i deixant-se els noms allà, proposat un enfocament més elegant. 276 00:12:36,450 --> 00:12:41,740 Una taula hash implementat encara amb un array d'índexs, però el tipus de dades 277 00:12:41,740 --> 00:12:44,500 aquests índexs ja eren punters. 278 00:12:44,500 --> 00:12:47,360 Punters a què? 279 00:12:47,360 --> 00:12:48,730 Punters a les llistes enllaçades. 280 00:12:48,730 --> 00:12:53,330 >> Perquè recordo que una llista enllaçada és en realitat un punter a un node, i 281 00:12:53,330 --> 00:12:57,110 el node té un camp proper, i que el node té un camp següent, i així successivament. 282 00:12:57,110 --> 00:13:00,690 Així que ara pot pensar en aquest conjunt de el costat esquerre d'una taula hash com 283 00:13:00,690 --> 00:13:01,820 que condueix a una llista enllaçada. 284 00:13:01,820 --> 00:13:07,000 L'avantatge que si et donen una col · lisió entre Alice i Aaron, 285 00:13:07,000 --> 00:13:09,300 Què fer amb el segona d'aquestes persones? 286 00:13:09,300 --> 00:13:14,150 Acabes de connectar o ella a l' final, o fins i tot el principi 287 00:13:14,150 --> 00:13:15,490 d'aquesta llista enllaçada. 288 00:13:15,490 --> 00:13:17,340 >> I, de fet, anem a través de fideus que per un segon. 289 00:13:17,340 --> 00:13:18,640 On tindria la majoria del sentit? 290 00:13:18,640 --> 00:13:22,060 Si inserit Alice i ella acaba en el primer lloc, llavors intento 291 00:13:22,060 --> 00:13:25,310 inseriu el nom d'Aaron, i hi ha òbviament una col · lisió, hauria de posar 292 00:13:25,310 --> 00:13:27,400 ell al principi de la llista enllaçada? 293 00:13:27,400 --> 00:13:30,944 Això és pel que el primer lloc, o al final? 294 00:13:30,944 --> 00:13:31,440 >> AUDIÈNCIA: [inaudible]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID Malan: OK. 296 00:13:31,990 --> 00:13:32,490 Vaig sentir començant. 297 00:13:32,490 --> 00:13:33,903 Per què al principi? 298 00:13:33,903 --> 00:13:34,750 >> AUDIÈNCIA: [inaudible]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID Malan: OK. 300 00:13:34,940 --> 00:13:36,520 És per ordre alfabètic, per la qual cosa és bo. 301 00:13:36,520 --> 00:13:37,330 Aquesta és una bona propietat. 302 00:13:37,330 --> 00:13:39,335 Es em va a estalviar una mica de temps potencialment. 303 00:13:39,335 --> 00:13:43,290 No em deixa fer recerca binària, però podria almenys ser capaç de trencar 304 00:13:43,290 --> 00:13:47,340 d'un bucle si m'adono, bé, jo sóc així passat eren Aaron seria en aquest 305 00:13:47,340 --> 00:13:48,310 ordenats llista enllaçada. 306 00:13:48,310 --> 00:13:50,360 Jo no he de perdre el temps buscant tot el camí fins al final. 307 00:13:50,360 --> 00:13:51,530 Així que això és raonable. 308 00:13:51,530 --> 00:13:54,710 Per què més podria voler inserir el nom de xocar a la 309 00:13:54,710 --> 00:13:56,660 principi de la llista? 310 00:13:56,660 --> 00:13:57,397 Què és això? 311 00:13:57,397 --> 00:13:58,680 >> AUDIÈNCIA: [inaudible]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID Malan: Podria ser molt llarg per arribar al final de la llista. 313 00:14:00,820 --> 00:14:02,490 I, de fet, més i més. 314 00:14:02,490 --> 00:14:04,920 Quants més noms que s'insereix començar amb una, més que 315 00:14:04,920 --> 00:14:06,280 la cadena es posarà. 316 00:14:06,280 --> 00:14:07,890 Com més temps vinculat llista va a aconseguir. 317 00:14:07,890 --> 00:14:09,420 Així que vostè és realment just perdent el temps. 318 00:14:09,420 --> 00:14:14,070 Potser és millor mantenir temps d'inserció constant, gran O d'1, 319 00:14:14,070 --> 00:14:18,470 per sempre posant el nom al xocar el principi de la llista enllaçada, 320 00:14:18,470 --> 00:14:21,230 i no preocupar-se tant sobre l'ordenació. 321 00:14:21,230 --> 00:14:22,600 >> Quina és la millor resposta? 322 00:14:22,600 --> 00:14:23,320 No està clar. 323 00:14:23,320 --> 00:14:26,140 És una cosa que depèn del que l' distribució és, quin és el patró 324 00:14:26,140 --> 00:14:27,850 dels noms que va a inserir. 325 00:14:27,850 --> 00:14:29,430 No és necessàriament una resposta òbvia. 326 00:14:29,430 --> 00:14:33,100 Però aquí per, de nou, és una oportunitat de disseny. 327 00:14:33,100 --> 00:14:37,220 >> Així que a continuació analitzem això, que és realment l'altra gran oportunitat 328 00:14:37,220 --> 00:14:38,180 de p-6 set. 329 00:14:38,180 --> 00:14:41,770 I adonar-se, si no ho ha fet, Zamyla submergeix en tots dos, haixix 330 00:14:41,770 --> 00:14:43,260 taules i tracta, de forma més detallada. 331 00:14:43,260 --> 00:14:45,630 I el tutorial de vídeo és incrustat en p-conjunt d'especificacions. 332 00:14:45,630 --> 00:14:46,590 Aquest era un trienni - 333 00:14:46,590 --> 00:14:51,670 T-I-I-E. I el que era interessant això va ser que el temps d'execució 334 00:14:51,670 --> 00:14:59,510 de la recerca d'un nom, com Maxwell l'última vegada, era gran O de què? 335 00:14:59,510 --> 00:15:01,040 Què és això? 336 00:15:01,040 --> 00:15:01,920 >> AUDIÈNCIA: El nombre de lletres. 337 00:15:01,920 --> 00:15:02,550 >> DAVID Malan: Nombre de lletres. 338 00:15:02,550 --> 00:15:03,210 Vaig escoltar dues coses. 339 00:15:03,210 --> 00:15:04,630 Nombre de lletres i de temps constant. 340 00:15:04,630 --> 00:15:05,540 Així que anirem amb la primera. 341 00:15:05,540 --> 00:15:06,410 El nombre de lletres. 342 00:15:06,410 --> 00:15:10,195 Doncs bé, aquesta estructura de dades, recuperació, és com un arbre, un arbre de la família, cadascun 343 00:15:10,195 --> 00:15:12,860 els nodes es componen de matrius. 344 00:15:12,860 --> 00:15:16,300 I aquests arrays són punters a altres tals nodes, o altres tals 345 00:15:16,300 --> 00:15:17,670 matrius en l'arbre. 346 00:15:17,670 --> 00:15:22,890 >> Així que si volem després determinar si Maxwell és aquí, jo podria anar 347 00:15:22,890 --> 00:15:26,890 a la primera sèrie, en la part superior de la l'arbre, l'anomenada arrel, la part superior de 348 00:15:26,890 --> 00:15:30,521 el trienni i segueixi el punter m, llavors el un punter, llavors x, 349 00:15:30,521 --> 00:15:31,710 w, i, l, l. 350 00:15:31,710 --> 00:15:34,910 I quan veig algun símbol especial, denotada aquí com un triangle. 351 00:15:34,910 --> 00:15:38,480 En el codi veuràs que proposem que implementat com un bool, només dir que sí 352 00:15:38,480 --> 00:15:40,540 o no, una paraula s'atura aquí. 353 00:15:40,540 --> 00:15:45,270 >> Bé, una vegada que hem anat a la M-A-X-W-E-L-L, se sent com set, potser 354 00:15:45,270 --> 00:15:48,910 vuit si anem un passat, vuit passos per trobar Maxwell. 355 00:15:48,910 --> 00:15:53,050 O el anomenarem K. Però recordem última temps, va sostenir que si hi ha 356 00:15:53,050 --> 00:15:57,540 realista una longitud màxima d'un paraula, com els personatges de 40 i escaig, un 357 00:15:57,540 --> 00:16:00,810 longitud màxima implica un valor constant. 358 00:16:00,810 --> 00:16:05,770 Així que en realitat, sí, és tècnicament gran O de 8 o 7, o molt gran O de K. No obstant això, 359 00:16:05,770 --> 00:16:09,420 si hi ha un límit finit en el K pot ser, és una constant. 360 00:16:09,420 --> 00:16:12,080 I el que és gran O d'1 a al final del dia. 361 00:16:12,080 --> 00:16:13,040 >> No hi ha al món real. 362 00:16:13,040 --> 00:16:15,960 No és quan realment comença a veure el rellotge del seu funcionament com del seu programa. 363 00:16:15,960 --> 00:16:20,690 És absolutament va a ser una mica més lent que veritablement constant 364 00:16:20,690 --> 00:16:21,840 temps amb un pas. 365 00:16:21,840 --> 00:16:25,540 Serà set o vuit passos, però tot i així és molt, molt millor 366 00:16:25,540 --> 00:16:30,080 d'un algorisme com el gran O de n que depèn de la mida del que hi ha a la 367 00:16:30,080 --> 00:16:31,220 estructura de dades. 368 00:16:31,220 --> 00:16:34,970 >> Observeu el costat positiu aquí és que podem inserir un milió més noms en aquesta 369 00:16:34,970 --> 00:16:38,170 estructura de dades, però la quantitat de passos més és que va a portar-nos a trobar 370 00:16:38,170 --> 00:16:40,480 Maxwell, en aquest cas? 371 00:16:40,480 --> 00:16:40,780 Cap. 372 00:16:40,780 --> 00:16:41,820 És afectat. 373 00:16:41,820 --> 00:16:45,480 I fins ara, no crec que hàgim vist un exemple d'una estructura de dades o un 374 00:16:45,480 --> 00:16:48,560 algoritme que era completament afectat per externa 375 00:16:48,560 --> 00:16:50,040 comportaments així. 376 00:16:50,040 --> 00:16:51,160 Però això no pot ser increïble. 377 00:16:51,160 --> 00:16:52,900 Això no pot ser l'única solució per al p-set 378 00:16:52,900 --> 00:16:53,570 >> I no ho és. 379 00:16:53,570 --> 00:16:55,980 Això no és necessàriament les dades estructura que ha de gravitar, 380 00:16:55,980 --> 00:16:58,220 perquè igual que les taules hash, equilibri. 381 00:16:58,220 --> 00:17:00,500 Quin és el preu que es paga? 382 00:17:00,500 --> 00:17:00,940 Memòria. 383 00:17:00,940 --> 00:17:02,890 És a dir, es tracta d'una atroç quantitat de memòria. 384 00:17:02,890 --> 00:17:05,569 I no es pot veure bé aquí perquè l'autor d'aquesta imatge 385 00:17:05,569 --> 00:17:09,420 òbviament truncada totes les matrius, i no estem veient un munt d'i 386 00:17:09,420 --> 00:17:12,700 B i C i Q i I i Z de en aquestes matrius. 387 00:17:12,700 --> 00:17:13,630 Però hi són. 388 00:17:13,630 --> 00:17:17,660 >> Cadascun d'aquests nodes és tot un seguit d'uns 26 o més bytes, cadascun dels 389 00:17:17,660 --> 00:17:19,170 el que representa una lletra. 390 00:17:19,170 --> 00:17:22,920 27 en el nostre cas, pel que podem donar suport apòstrofs en el conjunt de problemes. 391 00:17:22,920 --> 00:17:27,030 Per tant aquesta estructura de dades és realment, molt densa i àmplia. 392 00:17:27,030 --> 00:17:30,880 I això només podria acabar la desacceleració les coses, o almenys li costa 393 00:17:30,880 --> 00:17:32,240 molt més espai. 394 00:17:32,240 --> 00:17:34,020 Però una vegada més, podem treure comparacions aquí. 395 00:17:34,020 --> 00:17:39,190 >> Recordem fa un temps, hem aconseguit molt més emocionant temps de funcionament en la classificació 396 00:17:39,190 --> 00:17:42,880 quan fem servir merge tipus, però el preu que paguem per aconseguir n log n de fusió 397 00:17:42,880 --> 00:17:46,930 tipus requereix que passem més el que els recursos? 398 00:17:46,930 --> 00:17:47,690 Més espai. 399 00:17:47,690 --> 00:17:50,530 Necessitàvem una matriu secundària a copiar a la gent en, igual que 400 00:17:50,530 --> 00:17:51,620 que vam fer aquí a l'escenari. 401 00:17:51,620 --> 00:17:55,880 Així que de nou, no hi ha clars guanyadors, però només el disseny subjectiva 402 00:17:55,880 --> 00:17:57,710 que es prenguin decisions. 403 00:17:57,710 --> 00:17:58,060 >> Està bé. 404 00:17:58,060 --> 00:17:59,130 Així que què hi ha d'això? 405 00:17:59,130 --> 00:18:02,050 Qualsevol persona reconeix que D-Hall? 406 00:18:02,050 --> 00:18:02,440 D'acord. 407 00:18:02,440 --> 00:18:03,170 Així que tres de nosaltres. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Així que això és per un sopar de Mather. 410 00:18:05,070 --> 00:18:09,650 Aposto a tots els menjadors tenen piles de safates els agrada. 411 00:18:09,650 --> 00:18:11,950 I això és realment representativa d'alguna cosa que hem 412 00:18:11,950 --> 00:18:13,050 òbviament vist. 413 00:18:13,050 --> 00:18:14,850 En diem literalment una pila. 414 00:18:14,850 --> 00:18:18,970 I la pila, en termes de la seva la memòria de l'ordinador, és on va dades 415 00:18:18,970 --> 00:18:20,460 mentre que les funcions estan sent cridats. 416 00:18:20,460 --> 00:18:23,410 >> Per exemple, quin tipus de coses van a la pila que fa a la 417 00:18:23,410 --> 00:18:27,420 disseny de la memòria que hem discutit en les últimes setmanes? 418 00:18:27,420 --> 00:18:28,736 Què és això? 419 00:18:28,736 --> 00:18:29,670 >> AUDIÈNCIA: Les crides a funcions. 420 00:18:29,670 --> 00:18:30,260 >> DAVID Malan: Ho sento. 421 00:18:30,260 --> 00:18:31,210 >> AUDIÈNCIA: Les crides a funcions. 422 00:18:31,210 --> 00:18:33,590 >> DAVID Malan: Les crides a funcions, però en concret, el que hi ha dins de cada un 423 00:18:33,590 --> 00:18:35,340 els marcs? 424 00:18:35,340 --> 00:18:37,220 Quin tipus de coses? 425 00:18:37,220 --> 00:18:37,460 Si. 426 00:18:37,460 --> 00:18:38,500 Per tant les variables locals. 427 00:18:38,500 --> 00:18:43,080 Cada vegada que necessitàvem alguna cosa d'emmagatzematge local, com un argument o int I, o int 428 00:18:43,080 --> 00:18:45,940 temp, o el que sigui el local variable, hem estat 429 00:18:45,940 --> 00:18:47,210 posar que a la pila. 430 00:18:47,210 --> 00:18:49,610 I en diem una pila perquè d'aquesta idea d'estratificació. 431 00:18:49,610 --> 00:18:52,940 Només tipus de partits amb la realitat, el concepte dels mateixos. 432 00:18:52,940 --> 00:18:56,650 >> Però resulta que una pila pot també ser vist com una estructura de dades, un 433 00:18:56,650 --> 00:19:00,110 alternativa a una matriu, una alternativa d'una llista enllaçada. 434 00:19:00,110 --> 00:19:02,770 Una mica conceptualment més interessant que encara pot ser 435 00:19:02,770 --> 00:19:06,030 implementat mitjançant un dels coses, però és un tipus diferent de 436 00:19:06,030 --> 00:19:09,140 estructura de dades de suport, de veritat, només dues operacions. 437 00:19:09,140 --> 00:19:11,000 Però pots afegir més elegant característiques que aquests. 438 00:19:11,000 --> 00:19:12,180 Però aquests són els fonaments - 439 00:19:12,180 --> 00:19:13,510 inserir i extreure. 440 00:19:13,510 --> 00:19:19,240 >> I la idea amb una pila és que si jo tenim aquí, amb o sense Annenberg 441 00:19:19,240 --> 00:19:22,880 saber, una safata del costat amb el número 9 en ell. 442 00:19:22,880 --> 00:19:23,870 Així que un int. 443 00:19:23,870 --> 00:19:26,990 I vull portar aquest a les dades estructura, que actualment està buida. 444 00:19:26,990 --> 00:19:28,790 Penseu en això la part inferior de la pila. 445 00:19:28,790 --> 00:19:33,150 M'agradaria portar aquest número 9 en el pila, i ara hi és. 446 00:19:33,150 --> 00:19:36,040 >> Però l'interessant d'una pila és que si ara vull empènyer 447 00:19:36,040 --> 00:19:40,210 algun altre valor, com 17, i empenyo aquesta a la pila, ho faré 448 00:19:40,210 --> 00:19:43,290 l'única cosa intuïtiva, només vaig per posar les coses bé quan els éssers humans 449 00:19:43,290 --> 00:19:45,180 m'inclinaria a posar, a la part superior. 450 00:19:45,180 --> 00:19:48,850 Però el que és interessant ara És a dir, com puc aconseguir a les 9? 451 00:19:48,850 --> 00:19:50,670 Vostè sap, jo no sense cert esforç. 452 00:19:50,670 --> 00:19:54,070 >> Així que l'interessant d' una pila és que per disseny, 453 00:19:54,070 --> 00:19:56,330 que és una estructura de dades LIFO. 454 00:19:56,330 --> 00:19:59,680 Manera tonta de descriure últim a entrar, primer a sortir. 455 00:19:59,680 --> 00:20:03,280 Així que l'últim nombre de en aquest moment tenia 17 anys. 456 00:20:03,280 --> 00:20:07,540 Així que si vull fer esclatar una mica de de la pila, només pot ser 17. 457 00:20:07,540 --> 00:20:11,890 Així que hi ha una ordre obligatòria de operacions aquí, on l'últim element 458 00:20:11,890 --> 00:20:14,260 in ha de ser el primer a sortir. 459 00:20:14,260 --> 00:20:16,440 D'aquí l'acrònim, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Per què pot ser això útil? 461 00:20:19,160 --> 00:20:22,690 Són els contextos en què havia volen una estructura de dades com aquest? 462 00:20:22,690 --> 00:20:24,810 Bé, ha estat sens dubte útil a l'interior d'un ordinador. 463 00:20:24,810 --> 00:20:29,050 Per tant els sistemes operatius utilitzen clarament tipus d'estructura de dades per a piles. 464 00:20:29,050 --> 00:20:32,800 També veurem la mateixa idea quan es tracta de pàgines web. 465 00:20:32,800 --> 00:20:35,890 Així que aquesta setmana i la propera setmana i més enllà, i en començar l'aplicació web 466 00:20:35,890 --> 00:20:39,490 pàgines en un llenguatge anomenat HTML, pot realment utilitzar una estructura de dades com 467 00:20:39,490 --> 00:20:42,690 això per determinar si la pàgina és el format correcte. 468 00:20:42,690 --> 00:20:47,170 Perquè anem a veure totes les pàgines web segueixen una mena de jerarquia, una escotadura 469 00:20:47,170 --> 00:20:52,030 que, al final del dia, ser un estructura d'arbre sota de la caputxa. 470 00:20:52,030 --> 00:20:53,620 Per tant més d'això en una mica. 471 00:20:53,620 --> 00:20:56,560 >> Però per ara, anem a proposar una Actualment, com podem anar sobre 472 00:20:56,560 --> 00:20:58,830 representant el que és una pila? 473 00:20:58,830 --> 00:21:03,370 Permetin-me proposar que implementem una pila amb un codi com aquest. 474 00:21:03,370 --> 00:21:07,990 Així que una pila va a tenir dins d'ella dues coses, una gran varietat, anomenats safates, 475 00:21:07,990 --> 00:21:09,510 només per estar en consonància amb la demo. 476 00:21:09,510 --> 00:21:12,660 I cada un dels elements de la matriu serà un tipus int. 477 00:21:12,660 --> 00:21:14,740 I la capacitat és de suposar que el que? 478 00:21:14,740 --> 00:21:18,796 Perquè jo no he escrit el la definició completa aquí. 479 00:21:18,796 --> 00:21:21,535 >> És probablement el màxim mida de la matriu. 480 00:21:21,535 --> 00:21:25,150 I és probable que va declarar com un fort definir en la part superior de l'arxiu, alguns 481 00:21:25,150 --> 00:21:28,450 espècie de constant, obtingut per la mera capitalització. 482 00:21:28,450 --> 00:21:32,250 Així en algun lloc capacitat es defineix com la mida màxima possible. 483 00:21:32,250 --> 00:21:35,590 Mentrestant, a l'interior de l'estructura de dades conegut com una pila haurà 484 00:21:35,590 --> 00:21:38,630 ser un enter només coneguda simplement com grandària. 485 00:21:38,630 --> 00:21:43,400 >> Així que si jo fos a representar aquesta empresa pictòricament, suposem que aquest 486 00:21:43,400 --> 00:21:48,070 quadre negre representa tota la meva pila. 487 00:21:48,070 --> 00:21:50,070 A l'interior de la mateixa és dues variables. 488 00:21:50,070 --> 00:21:54,780 Així que vaig a assenyalar a la primer un com grandària. 489 00:21:54,780 --> 00:21:57,420 I el segon que vaig per dibuixar com una matriu. 490 00:21:57,420 --> 00:22:01,060 >> Però només per mantenir les coses en ordre, Normalment m'agradaria anomenar una matriu com 491 00:22:01,060 --> 00:22:04,910 això, però és una mica agradable si coincideixen amb la realitat, o 492 00:22:04,910 --> 00:22:06,230 coincideixi amb el model mental. 493 00:22:06,230 --> 00:22:12,880 Així que em baso en lloc de la matriu verticalment, que és just, de nou, 494 00:22:12,880 --> 00:22:13,840 interpretació de l'artista. 495 00:22:13,840 --> 00:22:16,610 Realment no importa el que que hi ha sota el capó. 496 00:22:16,610 --> 00:22:20,350 I direm que, per defecte, capacitat va a ser tres. 497 00:22:20,350 --> 00:22:23,480 Així que aquesta serà la posició 0, serà ubicació 1, aquest 498 00:22:23,480 --> 00:22:25,740 serà ubicació 2. 499 00:22:25,740 --> 00:22:29,330 >> Si subornar amb una bola de la tensió, ho faria a algú li agrada pujar i executar el 500 00:22:29,330 --> 00:22:30,870 abordar aquí per un moment? 501 00:22:30,870 --> 00:22:31,960 Bé, vaig veure la mà primer. 502 00:22:31,960 --> 00:22:33,950 Anem amunt. 503 00:22:33,950 --> 00:22:36,500 Està bé. 504 00:22:36,500 --> 00:22:38,760 Així que crec que és Steven. 505 00:22:38,760 --> 00:22:40,035 Anem amunt. 506 00:22:40,035 --> 00:22:40,770 Està bé. 507 00:22:40,770 --> 00:22:46,760 >> Però suposem ara que rebobinar fins al primer estat del món en què 508 00:22:46,760 --> 00:22:52,180 només han declarat una pila, i és tindrà una capacitat de tres. 509 00:22:52,180 --> 00:22:54,470 Però la mida encara no s'ha determinat. 510 00:22:54,470 --> 00:22:56,100 Safates encara no ha estat determinada. 511 00:22:56,100 --> 00:22:57,300 Així que un parell de preguntes primer. 512 00:22:57,300 --> 00:23:01,310 I et donaré micròfon perquè pugui participar més activament en això. 513 00:23:01,310 --> 00:23:05,190 >> Així que el que hi ha dins de la seva grandària en aquest moment a temps si tot el que he fet és 514 00:23:05,190 --> 00:23:09,340 declarat una pila amb una línia de codi? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: No gaire. 516 00:23:10,100 --> 00:23:12,080 >> DAVID Malan: OK, no gaire. 517 00:23:12,080 --> 00:23:14,410 Sabem que hi ha dins de la seva grandària, sabem el que hi ha dins 518 00:23:14,410 --> 00:23:16,330 d'aquesta varietat aquí? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Just codi aleatori, oi? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID Malan: Sí, vaig a cridar codi, però l'atzar - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Coses. 523 00:23:23,820 --> 00:23:28,290 >> DAVID Malan: Coses com l'atzar 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID Malan: Bits, oi? 526 00:23:29,530 --> 00:23:31,190 Per tant els valors de fem, oi? 527 00:23:31,190 --> 00:23:33,470 Així permutacions de 0 i 1 de. 528 00:23:33,470 --> 00:23:35,920 Les restes d'usos anteriors d'aquesta memòria. 529 00:23:35,920 --> 00:23:38,150 I no se sap molt bé quins són els valors estem, pel que normalment els allunyarem 530 00:23:38,150 --> 00:23:38,930 com a signes d'interrogació. 531 00:23:38,930 --> 00:23:41,990 >> Així que el primer que estem suposadament voldrà fer aquí - 532 00:23:41,990 --> 00:23:46,630 i et donaré aquest camp dins d'aquí el nom - safates. 533 00:23:46,630 --> 00:23:49,540 Què hem de suposar inicialitzar mida si volem 534 00:23:49,540 --> 00:23:51,040 començar a utilitzar aquesta pila? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Tray és sub 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID Malan: Llavors, OK. 537 00:23:53,910 --> 00:23:56,710 Per ser clars, la capacitat es declara en altres llocs com tres. 538 00:23:56,710 --> 00:23:58,570 I això és el que he fet servir per assignar la matriu. 539 00:23:58,570 --> 00:24:03,535 La mida es va a fer referència a la quantitat de safates són actualment a la pila. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID Malan: Així ha de ser zero. 542 00:24:04,460 --> 00:24:07,760 Així que endavant, i amb un dit, dibuixar un zero en grandària. 543 00:24:07,760 --> 00:24:08,440 Està bé. 544 00:24:08,440 --> 00:24:10,920 Així que ara, el que hi ha dins d'aquest aquí, no sabem. 545 00:24:10,920 --> 00:24:12,160 Aquests són en realitat els valors de fem. 546 00:24:12,160 --> 00:24:14,800 Així que podríem dibuixar signes d'interrogació, però Anem a mantenir el tauler net per ara 547 00:24:14,800 --> 00:24:16,300 , Ja que no importa el que hi ha. 548 00:24:16,300 --> 00:24:19,130 No necessitem per inicialitzar la matriu per a res, perquè si sabem que 549 00:24:19,130 --> 00:24:23,100 la mida de la pila és zero, bé, no s'ha de mirar res en 550 00:24:23,100 --> 00:24:25,590 aquesta matriu de totes formes en aquest punt en el temps. 551 00:24:25,590 --> 00:24:29,970 >> Així que ara suposo que pols el número 9 a la pila. 552 00:24:29,970 --> 00:24:33,750 Com hem d'actualitzar l'estructura de dades dins d'aquest requadre negre? 553 00:24:33,750 --> 00:24:35,540 Quins valors hi ha necessitat de canviar? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Distància - 555 00:24:36,200 --> 00:24:37,400 la mida? 556 00:24:37,400 --> 00:24:37,650 >> DAVID Malan: OK. 557 00:24:37,650 --> 00:24:38,770 Mida hauria de ser què? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Mida seria un. 559 00:24:39,580 --> 00:24:39,870 >> DAVID Malan: OK. 560 00:24:39,870 --> 00:24:41,110 Així que mida ha de ser un. 561 00:24:41,110 --> 00:24:42,540 Així que vostè pot fer això en un parell de maneres. 562 00:24:42,540 --> 00:24:46,920 Et vaig a donar, ja que la seva dit és un esborrany. 563 00:24:46,920 --> 00:24:47,260 Està bé. 564 00:24:47,260 --> 00:24:49,960 Llavors ara el dit és un raspall. 565 00:24:49,960 --> 00:24:50,330 Està bé. 566 00:24:50,330 --> 00:24:52,820 I ara, què més ha de canviar, òbviament, en l'estructura de dades? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Anem a inferior a 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID Malan: 9. 569 00:24:57,760 --> 00:24:58,420 Bé, bé. 570 00:24:58,420 --> 00:25:01,550 Així que encara no importa el que està en ubicació d'un o dos, perquè són 571 00:25:01,550 --> 00:25:04,520 valors d'escombraries, però no han de preocupar buscant allà perquè la mida és 572 00:25:04,520 --> 00:25:07,540 que ens diu que només el primer element en realitat és legítima. 573 00:25:07,540 --> 00:25:10,400 Així que ara em empenta 17 a la llista. 574 00:25:10,400 --> 00:25:11,830 Què passa amb aquesta imatge? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Així que la mida va a anar a dues. 576 00:25:14,720 --> 00:25:15,300 >> DAVID Malan: OK. 577 00:25:15,300 --> 00:25:16,070 Ets esborrany - 578 00:25:16,070 --> 00:25:16,810 Ui. 579 00:25:16,810 --> 00:25:18,026 Vostè és un esborrany. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Esborrany. 581 00:25:18,840 --> 00:25:19,720 >> DAVID Malan: Ets un raspall. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID Malan: OK. 584 00:25:20,920 --> 00:25:21,600 I què més? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: I llavors - 586 00:25:22,600 --> 00:25:22,915 >> DAVID Malan: Ens va empènyer 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Ens enganxem 17 a la part superior, de manera que - 588 00:25:24,760 --> 00:25:25,710 >> DAVID Malan: OK, bo. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - caure cap avall. 590 00:25:27,040 --> 00:25:27,530 >> DAVID Malan: Molt bé. 591 00:25:27,530 --> 00:25:27,940 S'està posant fàcil. 592 00:25:27,940 --> 00:25:29,300 Jo no vaig a ajudar-te aquesta vegada. 593 00:25:29,300 --> 00:25:30,510 Empenta 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Fet. 595 00:25:31,720 --> 00:25:34,870 Convertir-se en un esborrany. 596 00:25:34,870 --> 00:25:37,340 M'estic convertint en un raspall. 597 00:25:37,340 --> 00:25:39,340 I llavors em poso 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID Malan: 22. 599 00:25:40,100 --> 00:25:40,620 Excel · lent. 600 00:25:40,620 --> 00:25:41,380 Així que una vegada més. 601 00:25:41,380 --> 00:25:44,280 Ara vaig a empènyer a la pila 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh Déu meu. 604 00:25:50,278 --> 00:25:52,520 Realment em va prendre per sorpresa. 605 00:25:52,520 --> 00:25:53,703 >> DAVID Malan: No ho vas fer veure venir això? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: No ho vaig veure venir. 607 00:25:55,930 --> 00:25:58,756 Podríem capacitat de tornar a primera? 608 00:25:58,756 --> 00:25:59,790 >> DAVID Malan: Aquesta és una bona pregunta. 609 00:25:59,790 --> 00:26:02,360 Així que hem tipus de pintem en un racó aquí. 610 00:26:02,360 --> 00:26:06,740 Realment no hi ha bona per Steven perquè hem assignat aquest array 611 00:26:06,740 --> 00:26:09,130 estàticament, per així dir-ho, a l'interior de l'estructura de dades. 612 00:26:09,130 --> 00:26:12,170 I hem codificat essencialment dur que sigui de la mida de tres. 613 00:26:12,170 --> 00:26:14,170 Així que en realitat no podem reassignar. 614 00:26:14,170 --> 00:26:20,020 >> Podríem Si tornem, ens redefinits safates per ser un punter que 615 00:26:20,020 --> 00:26:22,300 , Utilitzem la memòria malloc mà. 616 00:26:22,300 --> 00:26:25,050 Perquè si tenim la memòria d' la pila a través de malloc, que 617 00:26:25,050 --> 00:26:26,430 llavors podria alliberar-lo. 618 00:26:26,430 --> 00:26:29,630 Però abans d'alliberar-la, podríem reassignar un tros més gran de la memòria, 619 00:26:29,630 --> 00:26:31,330 actualitzar el punter, i així successivament. 620 00:26:31,330 --> 00:26:33,500 Però per ara, això és realment El millor que podem fer. 621 00:26:33,500 --> 00:26:36,360 Push i pop van presumiblement a haver d'indicar algun error. 622 00:26:36,360 --> 00:26:40,270 >> Així, per exemple, la nostra implementació d'empenta podria tornar un bool que 623 00:26:40,270 --> 00:26:42,390 prèviament retornat true, true, true. 624 00:26:42,390 --> 00:26:48,390 Però el quart temps, que tindrà perquè torni false, per exemple. 625 00:26:48,390 --> 00:26:48,540 Està bé. 626 00:26:48,540 --> 00:26:49,540 Molt ben fet. 627 00:26:49,540 --> 00:26:50,060 Enhorabona. 628 00:26:50,060 --> 00:26:52,160 T'has guanyat la bola de la tensió actual. 629 00:26:52,160 --> 00:26:53,110 >> [Aplaudiments] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Gràcies. 631 00:26:54,382 --> 00:26:55,680 >> DAVID Malan: Gràcies. 632 00:26:55,680 --> 00:26:59,740 OK, així que això sembla ser no gaire d'un pas endavant, no? 633 00:26:59,740 --> 00:27:01,410 Hem descrit aquesta estructura de dades. 634 00:27:01,410 --> 00:27:02,320 Ha estat convincent, ¿no? 635 00:27:02,320 --> 00:27:03,200 Els sistemes operatius agrada. 636 00:27:03,200 --> 00:27:06,360 Segons sembla, la web pot fer ús d'aquest, i altres aplicacions fixes. 637 00:27:06,360 --> 00:27:10,870 Però el que és una limitació estúpids que som tornar al tipus de setmana dos límits 638 00:27:10,870 --> 00:27:12,880 on hem fixat matrius de mida. 639 00:27:12,880 --> 00:27:15,010 >> Així que de fet hi ha un parell de formes en que podrien resoldre això. 640 00:27:15,010 --> 00:27:18,750 Podríem assignar dinàmicament la matriu, no per la força de codificació com he 641 00:27:18,750 --> 00:27:22,600 fet aquí, però en el seu lloc tornar a declarar això, per ser clars, com 642 00:27:22,600 --> 00:27:23,830 alguna cosa com això. 643 00:27:23,830 --> 00:27:29,040 Int * safates, no decidir en una capacitat encara. 644 00:27:29,040 --> 00:27:35,460 Però quan em declaro la pila en altres llocs en el meu codi, podria llavors cridar a malloc, 645 00:27:35,460 --> 00:27:38,250 obtenir la direcció d'un tros de memòria, i podria assignar 646 00:27:38,250 --> 00:27:39,980 que la direcció de les safates. 647 00:27:39,980 --> 00:27:43,340 >> I després, perquè és només un tros de memòria, podria seguir utilitzant quadrat 648 00:27:43,340 --> 00:27:45,450 notació de claudàtors de la forma habitual. 649 00:27:45,450 --> 00:27:49,020 Perquè de nou, hi ha una espècie d'aquest equivalent funcional de les matrius i 650 00:27:49,020 --> 00:27:50,820 trossos de memòria que vénen darrere de malloc. 651 00:27:50,820 --> 00:27:53,090 Podem tractar a un com l'altre mitjançant aritmètica de punters o 652 00:27:53,090 --> 00:27:54,440 la notació de claudàtors. 653 00:27:54,440 --> 00:27:55,660 Així que aquest és un dels enfocaments. 654 00:27:55,660 --> 00:28:00,120 >> Però, com més podem posar en pràctica aquesta mateixa estructura de dades, potencialment? 655 00:28:00,120 --> 00:28:00,280 Cert? 656 00:28:00,280 --> 00:28:04,530 Em sento com si haguéssim resolt aquest problema com fa una setmana. 657 00:28:04,530 --> 00:28:08,860 Quina va ser la solució a aquest problema que es va trobar amb Steven? 658 00:28:08,860 --> 00:28:10,370 Així llistes vinculades, cert. 659 00:28:10,370 --> 00:28:13,410 >> Si el problema és que estem pintant a nosaltres mateixos en una cantonada per l'assignació de 660 00:28:13,410 --> 00:28:17,580 en molt poca memòria endavant que ens llavors ha de tractar d'alguna manera amb, bé, 661 00:28:17,580 --> 00:28:19,880 ¿Per què no evitar que emetre en total? 662 00:28:19,880 --> 00:28:26,170 Per què no declaren safates per ser un punter a un node, ergo una llista enllaçada, 663 00:28:26,170 --> 00:28:30,740 i després simplement assignar nous nodes cada vegada que Steven necessari per ajustar a un 664 00:28:30,740 --> 00:28:32,400 nombre en l'estructura de dades. 665 00:28:32,400 --> 00:28:34,200 >> Així que la imatge hauria de canviar. 666 00:28:34,200 --> 00:28:38,220 No serà tan net i tan simple com un conjunt de tres enters. 667 00:28:38,220 --> 00:28:42,970 Ara que serà un punter a una estructura, i que es va a struct 668 00:28:42,970 --> 00:28:44,830 tenir un int i un punter de següent. 669 00:28:44,830 --> 00:28:47,670 Es durà a través d'aquest punter a un altre tal estructura a 670 00:28:47,670 --> 00:28:48,600 altra com a estructura. 671 00:28:48,600 --> 00:28:50,560 Així que la imatge en realitat ser una mica desordenat. 672 00:28:50,560 --> 00:28:52,950 I ens hem fletxes lligar tot junt. 673 00:28:52,950 --> 00:28:55,280 >> Però això està bé, bé, perquè hem vist com fer això. 674 00:28:55,280 --> 00:28:58,180 I una vegada que vostè se senti còmode alguna cosa com una aplicació vinculada 675 00:28:58,180 --> 00:29:01,450 llista, que haurà de fer si triar implementar una taula hash amb 676 00:29:01,450 --> 00:29:05,120 encadenament separat per p-set 6, pot usar-lo com un bloc de construcció, o un 677 00:29:05,120 --> 00:29:08,870 ingredient, o esgarrapades dir, un procediment, cosa que es posa, que 678 00:29:08,870 --> 00:29:12,560 crear la seva pròpia peça del trencaclosques que després es pot tornar a utilitzar. 679 00:29:12,560 --> 00:29:17,090 Compensacions que sí, però les possibles solucions que hem vist realment abans. 680 00:29:17,090 --> 00:29:20,560 >> Així que molt sovint, es veu això tots els any o dos quan llançaments d'Apple 681 00:29:20,560 --> 00:29:23,060 alguna cosa nova, i tots els bojos alineació exterior de l'illa 682 00:29:23,060 --> 00:29:27,050 botiga a comprar el seu marginal actualitzar el maquinari. 683 00:29:27,050 --> 00:29:30,420 Dic això, està bé, perquè Jo sóc una d'aquestes persones. 684 00:29:30,420 --> 00:29:35,140 Llavors, quin tipus d'estructura de dades podria representar aquesta realitat? 685 00:29:35,140 --> 00:29:36,980 >> Bé, anem a anomenar una cua, una línia. 686 00:29:36,980 --> 00:29:40,270 So British diria que és típicament un cua de totes maneres, així que és un nom bonic. 687 00:29:40,270 --> 00:29:44,960 I les dues operacions que una cua donarà suport anomenarem 1 enqueue 688 00:29:44,960 --> 00:29:48,900 funcionament i una operació de treure de la cua, els quals són similars a 689 00:29:48,900 --> 00:29:50,120 esperit per inserir i extreure. 690 00:29:50,120 --> 00:29:54,060 És només una mena de diferent en Convenció, el que anomenem aquests. 691 00:29:54,060 --> 00:29:57,680 Però per posar en cua alguna cosa significa afegir o inserir-lo en l'estructura de dades. 692 00:29:57,680 --> 00:29:59,570 Per treure de la cua consisteix en la seva eliminació. 693 00:29:59,570 --> 00:30:05,170 No obstant això, mentre que una pila de dades LIFO era un estructura, una cua és una primera a, 694 00:30:05,170 --> 00:30:06,740 primer a l'estructura de dades. 695 00:30:06,740 --> 00:30:10,050 >> Si vostè és la primera persona de la fila, vostè serà la primera persona a arribar 696 00:30:10,050 --> 00:30:12,420 fora de línia i comprar el seu nou dispositiu. 697 00:30:12,420 --> 00:30:18,070 Imagina't el mal que serien aquestes persones si Apple utilitza en el seu lloc una pila, per 698 00:30:18,070 --> 00:30:21,250 exemple, per implementar la recol · lecció de la seva nova joguina. 699 00:30:21,250 --> 00:30:24,310 Així cues tenen sentit, sens dubte, i podem pensar en tot tipus de 700 00:30:24,310 --> 00:30:27,480 aplicacions, presumiblement, per les cues, especialment quan es vol justícia. 701 00:30:27,480 --> 00:30:30,040 Així que com podem posar en pràctica aquests com una estructura de dades? 702 00:30:30,040 --> 00:30:33,680 >> Bé, jo proposo que podria ho ha de fer d'aquesta manera. 703 00:30:33,680 --> 00:30:35,225 Així que vaig a tenir ara números. 704 00:30:35,225 --> 00:30:38,190 Així que anem a mantenir simple i no necessàriament parlar en termes de safates. 705 00:30:38,190 --> 00:30:40,220 Només els números que la gent de hagudes. 706 00:30:40,220 --> 00:30:43,760 La capacitat es va a, una altra vegada, fixar el nombre total de persones que poden estar en 707 00:30:43,760 --> 00:30:46,900 aquesta línia, ja que tres o qualsevol altre valor. 708 00:30:46,900 --> 00:30:50,760 >> Però proposo que necessito per realitzar un seguiment no només de la mida de la 709 00:30:50,760 --> 00:30:52,370 cua, quantes coses hi ha. 710 00:30:52,370 --> 00:30:56,310 Així que la mida és la mida actual, la capacitat de és la mida màxima. 711 00:30:56,310 --> 00:30:58,540 Només una vegada més, la nomenclatura per convenció. 712 00:30:58,540 --> 00:31:03,680 ¿Per què necessito un int addicional dins d'una cua per realitzar un seguiment de qui està dins 713 00:31:03,680 --> 00:31:05,365 davant de la línia? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Per què he de fer això en aquest cas? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Bé, com és aquesta imatge canviarà? 718 00:31:16,190 --> 00:31:19,280 És probable que pugui tornar a utilitzar més d'aquesta imatge. 719 00:31:19,280 --> 00:31:21,480 Deixin-me seguir endavant i esborrar el que hi ha aquí. 720 00:31:21,480 --> 00:31:24,580 Donarem això una mica nom diferent aquí. 721 00:31:24,580 --> 00:31:28,930 Anem a desfer-nos dels 17, anem a desfer del 9, anem a desfer dels 3. 722 00:31:28,930 --> 00:31:30,410 I anem a afegir una cosa més. 723 00:31:30,410 --> 00:31:34,710 Proposo que he de portar un registre de al capdavant de la llista, que és només 724 00:31:34,710 --> 00:31:35,570 serà un sencer també. 725 00:31:35,570 --> 00:31:36,550 I anem a mantenir simple. 726 00:31:36,550 --> 00:31:37,740 No hi ha una llista vinculada per ara. 727 00:31:37,740 --> 00:31:40,900 >> Anem a admetre que anem a topen amb aquest límit. 728 00:31:40,900 --> 00:31:43,720 Però, ¿què és el que vull veure succeirà aquesta vegada? 729 00:31:43,720 --> 00:31:47,240 Així que suposo que vaig per davant i la primera persona que apareix en la línia, i 730 00:31:47,240 --> 00:31:48,560 és el número 9. 731 00:31:48,560 --> 00:31:49,680 Tenim boles de la tensió. 732 00:31:49,680 --> 00:31:51,330 Puc robar, per exemple, dues o tres persones? 733 00:31:51,330 --> 00:31:52,690 Un, dos, tres? 734 00:31:52,690 --> 00:31:53,120 Anem amunt. 735 00:31:53,120 --> 00:31:56,022 Des del front, perquè farem això ràpid. 736 00:31:56,022 --> 00:31:59,415 >> Cada un de vosaltres està ara serà un noi de ventilador en línia d'Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 No va a rebre els equips d'Apple al final d'això, però. 739 00:32:06,210 --> 00:32:06,500 Està bé. 740 00:32:06,500 --> 00:32:09,430 Així que vostè és el número 9, que està número 17, número 22. 741 00:32:09,430 --> 00:32:12,130 Aquests són nombres arbitraris, com ID d'estudiant o el que sigui. 742 00:32:12,130 --> 00:32:14,550 I en un moment, anem a començar per començar a afegir coses. 743 00:32:14,550 --> 00:32:16,000 I vaig a córrer el tauler aquí aquesta vegada. 744 00:32:16,000 --> 00:32:19,570 >> Així que en aquest cas, he inicialitza el front que sigui - 745 00:32:19,570 --> 00:32:22,380 En realitat no m'importa el que el davant és, perquè la mida és zero. 746 00:32:22,380 --> 00:32:24,480 Així que pot ser que també acaba de ser un signe d'interrogació. 747 00:32:24,480 --> 00:32:26,170 Tots aquests són signes d'interrogació. 748 00:32:26,170 --> 00:32:29,880 Així que ara anem a començar a veure realment alguns gent fent cua a la botiga. 749 00:32:29,880 --> 00:32:33,320 >> Així que si el nombre 9, que és el primer a les 5 AM, seguir endavant i alinear, 750 00:32:33,320 --> 00:32:34,210 o de la nit anterior. 751 00:32:34,210 --> 00:32:34,580 D'acord. 752 00:32:34,580 --> 00:32:35,940 Així que ara 9 està aquí. 753 00:32:35,940 --> 00:32:37,940 Així és 9 a la part frontal de la llista. 754 00:32:37,940 --> 00:32:41,440 Així que seguiré endavant i actualitzar la mida d'aquestes dades actuals 755 00:32:41,440 --> 00:32:44,740 estructura perquè no sigui 0 més, però per ser 1. 756 00:32:44,740 --> 00:32:47,630 Me'n vaig a posar en el 9 capdavant de la llista. 757 00:32:47,630 --> 00:32:51,020 Deixin-me seguir endavant i canviar la pantalla pel que podem veure més enllà de nosaltres. 758 00:32:51,020 --> 00:32:53,220 >> I ara, ¿què és el que vull posar al capdavant? 759 00:32:53,220 --> 00:32:56,240 Vaig a fer un seguiment que l' capdavant de la cua en aquest moment 760 00:32:56,240 --> 00:32:58,570 està en la posició 0. 761 00:32:58,570 --> 00:33:00,510 Perquè el que està al costat passarà? 762 00:33:00,510 --> 00:33:03,000 Bé, suposo que ara em Enqueue 17 també. 763 00:33:03,000 --> 00:33:04,510 Així que saltar en línia allà. 764 00:33:04,510 --> 00:33:07,060 I de nou, el tipus de porta a la botiga va a ser aquí. 765 00:33:07,060 --> 00:33:08,700 Així que ara he afegit 17. 766 00:33:08,700 --> 00:33:10,810 I malgrat que aquests nois estan bloquejant la pantalla, això està bé, 767 00:33:10,810 --> 00:33:12,300 perquè podem veure-ho aquí. 768 00:33:12,300 --> 00:33:12,910 Ho sento. 769 00:33:12,910 --> 00:33:13,810 >> AUDIÈNCIA: Podem moure - 770 00:33:13,810 --> 00:33:14,660 >> DAVID Malan: No, això està bé. 771 00:33:14,660 --> 00:33:16,000 És enorme allà. 772 00:33:16,000 --> 00:33:18,580 Així 17 és ara dins de la cua. 773 00:33:18,580 --> 00:33:21,332 Necessito actualitzar el que camps, tot i que ara? 774 00:33:21,332 --> 00:33:23,210 Bé, definitivament mida. 775 00:33:23,210 --> 00:33:26,430 ¿I què hi ha davant? 776 00:33:26,430 --> 00:33:27,040 Bé, no. 777 00:33:27,040 --> 00:33:30,200 Davant no ha de canviar, perquè a diferència d'una pila, que 778 00:33:30,200 --> 00:33:31,370 vol mantenir l'equitat. 779 00:33:31,370 --> 00:33:35,150 Així que si 9 va arribar en primer lloc, volem setembre per ser el primer a sortir de la línia de 780 00:33:35,150 --> 00:33:36,420 i dins de la botiga. 781 00:33:36,420 --> 00:33:37,220 >> De fet, anem a veure això. 782 00:33:37,220 --> 00:33:42,235 Abans que ens inserim 22, anem a seguir endavant i treure de la cua 9. 783 00:33:42,235 --> 00:33:42,970 Quin és el teu nom? 784 00:33:42,970 --> 00:33:43,680 >> AUDIÈNCIA: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID Malan: Jake va ser llevades ara. 786 00:33:45,440 --> 00:33:48,050 Així que has de caminar a la botiga. 787 00:33:48,050 --> 00:33:49,880 I pretendre que la botiga és per aquí. 788 00:33:49,880 --> 00:33:51,970 Així que ara el que cal - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 ¿Què ha de passar ara? 790 00:33:53,400 --> 00:33:54,490 Decisió de disseny. 791 00:33:54,490 --> 00:33:56,825 Així que no és un mal instint, però - Quin és el teu nom? 792 00:33:56,825 --> 00:33:57,090 >> AUDIÈNCIA: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID Malan: David. 794 00:33:57,500 --> 00:33:58,810 Així ho va fer David? 795 00:33:58,810 --> 00:34:02,590 Ell estava tractant d'ordenar de fixar les dades estructura i el moviment de la seva ubicació 796 00:34:02,590 --> 00:34:04,100 en primer lloc de Jake. 797 00:34:04,100 --> 00:34:06,740 I això està bé si estem disposats acceptar que com 798 00:34:06,740 --> 00:34:08,199 detall d'implementació. 799 00:34:08,199 --> 00:34:11,100 Però primer, anem a actualitzar les dades estructura abans de fer això. 800 00:34:11,100 --> 00:34:14,139 Perquè jo no m'està agradant la idea de tots el poble el canvi en aquesta línia. 801 00:34:14,139 --> 00:34:17,360 >> No és gran cosa si David ho fa amb un pas, però de nou, pensi en 802 00:34:17,360 --> 00:34:20,360 quan hem tingut vuit voluntaris en el escenari i el que hem fet com la inserció 803 00:34:20,360 --> 00:34:22,600 Ordena, on vam haver de començar moure tots al seu voltant. 804 00:34:22,600 --> 00:34:23,790 Això va fer car, no? 805 00:34:23,790 --> 00:34:28,330 Això em fa tremolar sobre Big O de N, O gran de n al quadrat de nou. 806 00:34:28,330 --> 00:34:30,650 No se sent com un resultat ideal. 807 00:34:30,650 --> 00:34:32,080 >> Així que anem a actualitzar això. 808 00:34:32,080 --> 00:34:35,120 Per tant la mida de la cua ja no és 2. 809 00:34:35,120 --> 00:34:37,090 Ara és simplement 1. 810 00:34:37,090 --> 00:34:40,360 Però ara puc actualitzar alguna cosa No vaig actualitzar abans, la 811 00:34:40,360 --> 00:34:41,130 capdavant de la llista. 812 00:34:41,130 --> 00:34:45,420 Jo podria dir és que la ubicació 1? 813 00:34:45,420 --> 00:34:49,770 Així que ara tenim el valor d'escombraries aquí, Valor d'escombraries aquí, i David al 814 00:34:49,770 --> 00:34:51,469 mitjà d'aquestes escombraries. 815 00:34:51,469 --> 00:34:54,980 No obstant això, l'estructura de dades encara està intacta. 816 00:34:54,980 --> 00:34:58,540 >> I, de fet, jo ni tan sols necessito canviar exnúmero de Jake 817 00:34:58,540 --> 00:35:00,460 9, ia qui li importa. 818 00:35:00,460 --> 00:35:04,470 No tinc prou informació ara al mida que sé que hi ha una persona en 819 00:35:04,470 --> 00:35:05,030 aquesta cua. 820 00:35:05,030 --> 00:35:08,340 I sé que aquesta persona està en la posició 1, no 0. 821 00:35:08,340 --> 00:35:09,760 No estic explicant. 822 00:35:09,760 --> 00:35:11,300 Així gener també. 823 00:35:11,300 --> 00:35:13,410 Així que l'estructura de dades és tot i així està bé. 824 00:35:13,410 --> 00:35:14,330 >> Bé, què passa després? 825 00:35:14,330 --> 00:35:15,010 Posarem en col - 826 00:35:15,010 --> 00:35:15,370 Quin és el teu nom? 827 00:35:15,370 --> 00:35:16,160 >> AUDIÈNCIA: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID Malan: Callen. 829 00:35:16,580 --> 00:35:20,770 Posarem en cua un Callen i 22 és ara a la cua. 830 00:35:20,770 --> 00:35:22,300 Així que ara el que ha de canviar aquí? 831 00:35:22,300 --> 00:35:24,380 Davant no va a canviar, òbviament. 832 00:35:24,380 --> 00:35:27,160 Mida canviarà per ser de nou 2. 833 00:35:27,160 --> 00:35:31,590 I 22 acaba aquí, el 9 és encara present, però és efectivament un 834 00:35:31,590 --> 00:35:32,600 valor de les escombraries ara. 835 00:35:32,600 --> 00:35:35,910 És només un romanent de Jake passat. 836 00:35:35,910 --> 00:35:39,200 >> ¿I ara què passa si I dequeue David? 837 00:35:39,200 --> 00:35:41,560 Una última operació, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Podem canviar, però anem a proposar fer el menor treball possible. 839 00:35:46,070 --> 00:35:50,280 Ara la meva estructura de dades es una còpia en grandària de 2 a 1. 840 00:35:50,280 --> 00:35:53,730 No obstant això, la part davantera de la cua ara es converteix en 2. 841 00:35:53,730 --> 00:35:56,640 No necessito canviar aquests nombres però just, perquè són 842 00:35:56,640 --> 00:35:58,230 només els valors d'escombraries. 843 00:35:58,230 --> 00:35:59,720 >> Però ara, què passa? 844 00:35:59,720 --> 00:36:03,280 Suposem que Enqueue mi mateix, 26? 845 00:36:03,280 --> 00:36:05,890 Sento que pertanyo aquí. 846 00:36:05,890 --> 00:36:06,890 Així que estic sent en cua. 847 00:36:06,890 --> 00:36:08,760 Així que tipus de pertanyo aquí. 848 00:36:08,760 --> 00:36:11,300 I tot i que no arriben apreciar aquesta visuals a l'escenari, 849 00:36:11,300 --> 00:36:15,075 perquè tenim un munt d'espai, el que hauria no ser aquí, per què? 850 00:36:15,075 --> 00:36:16,290 >> AUDIÈNCIA: Vostè està fora dels límits. 851 00:36:16,290 --> 00:36:16,370 >> DAVID Malan: Sí. 852 00:36:16,370 --> 00:36:16,940 Estic fora dels límits. 853 00:36:16,940 --> 00:36:19,330 He s'indexen més enllà de la límits d'aquesta matriu. 854 00:36:19,330 --> 00:36:23,420 Realment hauria d'estar en un dels tres possibles ubicacions. 855 00:36:23,420 --> 00:36:25,150 Ara, on és més natural que anar? 856 00:36:25,150 --> 00:36:27,760 Proposo que palanquejats una setmana un truc. 857 00:36:27,760 --> 00:36:30,150 L'operador mod, percentatge. 858 00:36:30,150 --> 00:36:36,850 Perquè estic tècnicament peu a localització 3, però jo sí la capacitat de 3 mod, 859 00:36:36,850 --> 00:36:40,250 so 3, un signe de percentatge, 3 - 860 00:36:40,250 --> 00:36:40,970 la capacitat de 3. 861 00:36:40,970 --> 00:36:41,720 Què és això? 862 00:36:41,720 --> 00:36:43,700 Què és el que queda quan es divideix 3 per 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Així que això em posa Jake es va anar, que és realment bo. 865 00:36:48,140 --> 00:36:50,370 Així que ara l'aplicació d'aquesta cosa va a 866 00:36:50,370 --> 00:36:51,250 ser una mica d'un mal de cap. 867 00:36:51,250 --> 00:36:53,740 És realment una sola línia de mal de cap, de codi. 868 00:36:53,740 --> 00:36:56,580 Però almenys ara hi ha deixalles valor aquí, però no hi ha dos 869 00:36:56,580 --> 00:36:57,910 ints legítims aquí. 870 00:36:57,910 --> 00:37:04,160 I afirmo que ara hem fet exactament el que hem de fer, sempre que 871 00:37:04,160 --> 00:37:08,600 canviem el de Jake Valor anava a ser 26. 872 00:37:08,600 --> 00:37:12,110 >> Ara tenim prou informació encara per mantenir la integritat 873 00:37:12,110 --> 00:37:13,060 d'aquesta estructura de dades. 874 00:37:13,060 --> 00:37:17,160 Encara estem una mica fora de sort quan voleu inserir quatre o més totals 875 00:37:17,160 --> 00:37:20,740 elements, però almenys puc fer força ús eficient d'aquesta constant 876 00:37:20,740 --> 00:37:21,740 temps, de fet. 877 00:37:21,740 --> 00:37:27,150 Jo no he de preocupar pel canvi tots, ja que la inclinació de David era. 878 00:37:27,150 --> 00:37:30,816 >> Qualsevol pregunta sobre les piles, o aquesta col? 879 00:37:30,816 --> 00:37:32,184 >> AUDIÈNCIA: És la raó per la vostè necessita mida perquè vostè sàpiga 880 00:37:32,184 --> 00:37:34,010 on té una persona? 881 00:37:34,010 --> 00:37:34,770 >> DAVID Malan: Exactament. 882 00:37:34,770 --> 00:37:38,230 Necessito saber la mida de la matriu perquè he de saber exactament com 883 00:37:38,230 --> 00:37:41,940 molts d'aquests valors són legítims, i perquè jo pugui trobar on posar 884 00:37:41,940 --> 00:37:42,800 la següent persona. 885 00:37:42,800 --> 00:37:43,300 Exactament. 886 00:37:43,300 --> 00:37:44,580 La mida és - 887 00:37:44,580 --> 00:37:46,360 En realitat, no ens actualitzem això encara. 888 00:37:46,360 --> 00:37:48,380 Jo vaig agregar jo en 26. 889 00:37:48,380 --> 00:37:51,760 La mida és ara, no 1, però 2. 890 00:37:51,760 --> 00:37:57,780 Així que ara aquest fet ajuda a trobar la cap de la llista, que no és 0, no 891 00:37:57,780 --> 00:37:59,250 1, però és 2. 892 00:37:59,250 --> 00:38:01,665 El front de la llista és de fet el nombre 22. 893 00:38:01,665 --> 00:38:05,120 A causa de que va arribar en primer lloc, pel que ha de ser admesos a la botiga abans de mi, 894 00:38:05,120 --> 00:38:08,780 tot i que visualment estic parat més a prop de la botiga. 895 00:38:08,780 --> 00:38:09,220 >> D'acord? 896 00:38:09,220 --> 00:38:12,410 Un aplaudiment per a aquests nois i deixarem que treure'ls d'allà. 897 00:38:12,410 --> 00:38:17,090 >> [Aplaudiments] 898 00:38:17,090 --> 00:38:18,150 >> DAVID Malan: podia deixar que a mantenir la safata. 899 00:38:18,150 --> 00:38:20,760 Vam poder veure el que passa si que vulgui, però potser no. 900 00:38:20,760 --> 00:38:21,590 Està bé. 901 00:38:21,590 --> 00:38:25,380 ¿I ara què ens deixa això? 902 00:38:25,380 --> 00:38:28,900 Bé, permetin-me proposar que hi ha un algunes altres estructures de dades que vam poder 903 00:38:28,900 --> 00:38:33,810 començar a afegir al nostre conjunt d'eines que en realitat ser molt, molt rellevant com 904 00:38:33,810 --> 00:38:35,270 ens submergim en coses web. 905 00:38:35,270 --> 00:38:38,150 Que al seu torn, té algun tipus de connexió als arbres en la forma d' 906 00:38:38,150 --> 00:38:40,550 cosa que es diu DOM, document model d'objectes. 907 00:38:40,550 --> 00:38:42,370 Però anem a veure més que en poc temps. 908 00:38:42,370 --> 00:38:46,260 >> Permetin-me proposar per definició que truqui al arbre ja ho deus saber com 909 00:38:46,260 --> 00:38:48,820 més d'un arbre, en el qual tenir algun avantpassat en el 910 00:38:48,820 --> 00:38:49,790 arrels de l'arbre. 911 00:38:49,790 --> 00:38:54,480 Una matriarca patriarcal o en la part més alta de l'arbre. 912 00:38:54,480 --> 00:38:56,700 Sense la seva cònjuge, en aquest cas. 913 00:38:56,700 --> 00:39:00,940 Però ara tenim el que anomenem els nens, que són els nodes que pengen 914 00:39:00,940 --> 00:39:05,480 fos el fill esquerre o el dret de l'infant, fletxes com s'il · lustra aquí. 915 00:39:05,480 --> 00:39:10,490 >> En altres paraules, en una estructura de dades en arbre a l'ordinador, un arbre té zero 916 00:39:10,490 --> 00:39:11,480 o més nodes. 917 00:39:11,480 --> 00:39:13,500 Si té almenys un node, que es diu l'arrel. 918 00:39:13,500 --> 00:39:15,700 Són les coses visualment que ens basem en la part superior. 919 00:39:15,700 --> 00:39:20,280 I aquest node, com qualsevol altre node, pot tenir zero, un, o dos, o tres, 920 00:39:20,280 --> 00:39:23,600 o però molts nens estructura de dades compatible. 921 00:39:23,600 --> 00:39:29,150 En aquest cas, l'arrel, l'emmagatzematge de la valor d'un, té dos fills, de 2 i 3, 922 00:39:29,150 --> 00:39:33,020 pel que generalment anomenem 2 de la esquerra nens i 3 el fill dret. 923 00:39:33,020 --> 00:39:36,940 >> I després, quan ens posem mans a la 5, 6 i 7, 6 podria ser cridat el fill del medi. 924 00:39:36,940 --> 00:39:38,940 Si vostè té quatre fills, es torna confús. 925 00:39:38,940 --> 00:39:42,260 Així que deixem d'usar aquest tipus d'accés directe verbalment. 926 00:39:42,260 --> 00:39:44,580 Però no deixa de ser un arbre genealògic. 927 00:39:44,580 --> 00:39:48,880 I les fulles aquí són els nodes que ells no tenen fills. 928 00:39:48,880 --> 00:39:52,540 Es pengen de la part inferior de l'arbre. 929 00:39:52,540 --> 00:39:56,940 >> Llavors, com podríem implementar un arbre que només té dos fills al màxim? 930 00:39:56,940 --> 00:39:58,410 L'anomenarem un arbre binari. 931 00:39:58,410 --> 00:40:00,960 Bi nou significa dues, en aquest cas, igual que amb el binari. 932 00:40:00,960 --> 00:40:04,830 I pel que pot tenir zero, un, o dos nens al màxim. 933 00:40:04,830 --> 00:40:08,650 >> Jo proposo que implementem el node perquè l'estructura amb una n int, 934 00:40:08,650 --> 00:40:11,910 i després dos punts, un anomenat a l'esquerra, un anomenat dreta. 935 00:40:11,910 --> 00:40:14,830 Però aquests són només agradables convencions arbitràries. 936 00:40:14,830 --> 00:40:18,170 I el que és bo ara, sobretot si tipus de lluitar conceptualment amb 937 00:40:18,170 --> 00:40:21,300 recursió, o pensar que no era realment una solució a res, 938 00:40:21,300 --> 00:40:23,120 especialment si es pogués quedar-se sense memòria. 939 00:40:23,120 --> 00:40:26,600 Ara que estem parlant de dades estructures i algorismes que permeten 940 00:40:26,600 --> 00:40:31,030 nosaltres travessem i manipular-los, Resulta que la recursivitat torna a 941 00:40:31,030 --> 00:40:34,240 una forma molt més convincent si no bonic camí. 942 00:40:34,240 --> 00:40:38,670 >> Així que proposo és la implementació d'una funció de cerca. 943 00:40:38,670 --> 00:40:39,870 Donades dues entrades - 944 00:40:39,870 --> 00:40:41,570 de manera que pensar en això com un quadre negre. 945 00:40:41,570 --> 00:40:46,560 Donades dues entrades, n, un enter i un punter a un arbre, un punter a una 946 00:40:46,560 --> 00:40:50,020 node, o en realitat l'arrel d'un arbre, afirmació que aquesta funció pot retornar 947 00:40:50,020 --> 00:40:53,530 vertader o fals, que el valor de n està dins d'aquest arbre. 948 00:40:53,530 --> 00:40:55,210 >> Què hi ha dins d'aquest quadre de negre? 949 00:40:55,210 --> 00:40:57,440 Bé, quatre branques. 950 00:40:57,440 --> 00:40:58,385 Comprova la primera justa. 951 00:40:58,385 --> 00:41:00,490 Si l'arbre és nul · la, torna falsa. 952 00:41:00,490 --> 00:41:04,580 Si no hi ha un node, no hi ha n, no hi ha un nombre, simplement return false. 953 00:41:04,580 --> 00:41:12,330 Si, però, n, el valor que està buscant per, és menys d'arbre de fletxa n, i 954 00:41:12,330 --> 00:41:15,180 només perquè quedi clar, el que vol dir quan Escric arbre i després la fletxa 955 00:41:15,180 --> 00:41:18,150 notació, n? 956 00:41:18,150 --> 00:41:18,690 Exactament. 957 00:41:18,690 --> 00:41:21,970 Això significa eliminar la referència que punter diu arbre. 958 00:41:21,970 --> 00:41:26,750 Anar-hi i, a continuació, entrar d'aquesta node i aconseguir el seu camp anomenat núm. 959 00:41:26,750 --> 00:41:30,810 I a continuació, comparar el núm real que era passat a la recerca contra ell. 960 00:41:30,810 --> 00:41:35,390 >> Així que si n és menor que, el valor de n en el node de l'arbre en si, bé, 961 00:41:35,390 --> 00:41:36,720 Què significa això? 962 00:41:36,720 --> 00:41:40,690 Això no vol dir res a primera vista. 963 00:41:40,690 --> 00:41:40,900 Cert? 964 00:41:40,900 --> 00:41:45,560 Igual que quan vostè té una gran varietat de valors, que et poden agradar aplicar binari 965 00:41:45,560 --> 00:41:48,290 buscar una forma de divisió i conquerir. 966 00:41:48,290 --> 00:41:51,790 Però, quines hipòtesis ens hem de fer de recerca binària per treballar en totes les 967 00:41:51,790 --> 00:41:54,510 a la guia telefònica i exemples anteriors? 968 00:41:54,510 --> 00:41:55,530 >> Com ser ordenats. 969 00:41:55,530 --> 00:41:59,490 Així que anem a refinar la definició d'arbre aquí no per ser només un arbre, que pot 970 00:41:59,490 --> 00:42:00,880 tenir qualsevol nombre de fills. 971 00:42:00,880 --> 00:42:04,700 No és només un arbre binari, el que pot tenir 0, 1 o 2 com a màxim. 972 00:42:04,700 --> 00:42:09,700 Però, com un arbre de cerca binària, o BST, que és només una forma elegant de dir que una 973 00:42:09,700 --> 00:42:15,430 arbre binari de manera que cada node fill esquerre, si està present, és 974 00:42:15,430 --> 00:42:16,830 menys que el node. 975 00:42:16,830 --> 00:42:20,170 I el dret de tot infant de node, si està present, és més gran 976 00:42:20,170 --> 00:42:21,740 que el mateix node. 977 00:42:21,740 --> 00:42:25,200 >> En altres paraules, si fos a dibuixar el cap de l'arbre, tots els números són 978 00:42:25,200 --> 00:42:30,620 curosament equilibrada com aquest, així que si Té 55 com l'arrel, 33 poden anar 979 00:42:30,620 --> 00:42:33,090 a la seva esquerra, ja que és menys de 55. 980 00:42:33,090 --> 00:42:36,430 77 pot anar a la dreta, perquè és major de 55 anys. 981 00:42:36,430 --> 00:42:40,750 Però ara compta, la mateixa definició, és una definició recursiva verbalment, 982 00:42:40,750 --> 00:42:42,600 ha de demanar 33. 983 00:42:42,600 --> 00:42:47,610 Fill esquerre de 33 ha de ser menor del que, i el fill dret de 33, 44, ha de ser 984 00:42:47,610 --> 00:42:48,580 més gran del que. 985 00:42:48,580 --> 00:42:51,670 >> Així que aquest és un arbre binari de recerca, i Proposo, amb una mica de 986 00:42:51,670 --> 00:42:53,910 recursivitat, ara podem trobar n. 987 00:42:53,910 --> 00:42:59,160 Així que si n és menor que el valor de n que és node actual, aniré 988 00:42:59,160 --> 00:43:04,090 endavant i batea, per així dir-ho, i només tornar el que la resposta és de 989 00:43:04,090 --> 00:43:08,470 la recerca de n en la fill esquerre de l'arbre. 990 00:43:08,470 --> 00:43:11,370 Note una vegada més, aquesta funció només espera un estel node, 1 991 00:43:11,370 --> 00:43:12,780 punter a un node. 992 00:43:12,780 --> 00:43:17,360 Així que sens dubte jo puc fer arbre fletxa cap a l'esquerra, el que conduirà 993 00:43:17,360 --> 00:43:18,400 em a un altre node. 994 00:43:18,400 --> 00:43:19,480 Però, què és aquest node? 995 00:43:19,480 --> 00:43:22,820 >> Bé, d'acord amb aquesta declaració, esquerra és només un punter, pel que només 996 00:43:22,820 --> 00:43:27,090 vol dir que estic passant a la funció de cerca un punter diferent, a saber, 997 00:43:27,090 --> 00:43:30,750 el que representa l'arbre del meu fill esquerre. 998 00:43:30,750 --> 00:43:36,040 Així doncs, en aquest cas, el punter a 33, si aquesta és la nostra entrada de la mostra Mentrestant, si 999 00:43:36,040 --> 00:43:40,740 n és major que el valor de n en la node actual en l'arbre, llavors jo sóc 1000 00:43:40,740 --> 00:43:43,370 va a seguir endavant i rebuig en l'altra direcció i dir, jo no 1001 00:43:43,370 --> 00:43:47,280 saber si aquest valor de n està en l'arbre, però sé que si ho és, és per la meva 1002 00:43:47,280 --> 00:43:49,090 branca dreta, per així dir-ho. 1003 00:43:49,090 --> 00:43:53,120 Així que em diuen recursivament recerca, passar un n altra vegada, però que passa en un 1004 00:43:53,120 --> 00:43:54,580 punter al meu fill dret. 1005 00:43:54,580 --> 00:44:00,020 >> En altres paraules, si estic actualment en 55 i estic a la recerca de 99, jo sé que el 99 1006 00:44:00,020 --> 00:44:04,270 és més gran que 55, pel que igual que jo vaig arrencar la setmana de l'agenda i ens fa 1007 00:44:04,270 --> 00:44:07,140 va anar a la dreta, de la mateixa manera som va a anar aquí. 1008 00:44:07,140 --> 00:44:11,960 I jo no sé si és a la meva dreta nen, i no és, el 77 hi és, però 1009 00:44:11,960 --> 00:44:13,210 Sé que és en aquesta direcció. 1010 00:44:13,210 --> 00:44:18,770 Així que dic cerca en el meu fill dret, 77, i deixar que figura recerca des 1011 00:44:18,770 --> 00:44:24,950 si hi ha 99 en aquest arbitrària exemple és realment allà. 1012 00:44:24,950 --> 00:44:26,900 >> Si no, quin és l'últim cas? 1013 00:44:26,900 --> 00:44:28,620 Si l'arbre és nul · la és un dels casos. 1014 00:44:28,620 --> 00:44:31,890 Si n és menor que el node actual de valor és un altre cas. 1015 00:44:31,890 --> 00:44:35,120 Si n és més gran que el corrent el valor de node és un tercer cas. 1016 00:44:35,120 --> 00:44:38,250 Quin és el quart i últim cas? 1017 00:44:38,250 --> 00:44:39,480 Crec que estem fora dels casos, no? 1018 00:44:39,480 --> 00:44:44,690 Deu ser que n està en el node actual que estic. 1019 00:44:44,690 --> 00:44:49,640 >> Així que si estic a la recerca de 55 en aquest moment en la història, aquesta branca de la 1020 00:44:49,640 --> 00:44:51,780 arbre tornaria realitat. 1021 00:44:51,780 --> 00:44:55,380 Així que el que és interessant aquí és que En realitat, a diferència de setmana passat, quin tipus 1022 00:44:55,380 --> 00:44:56,740 tenen de dos casos de base. 1023 00:44:56,740 --> 00:44:58,300 I ells no han de estar a la part superior. 1024 00:44:58,300 --> 00:45:01,390 La part superior és un cas base, perquè si el arbre és nul, no hi ha res a fer. 1025 00:45:01,390 --> 00:45:03,410 Simplement envieu un disc codificat valor false. 1026 00:45:03,410 --> 00:45:07,400 >> La branca inferior és una espècie de per defecte, de manera que si hem comprovat en 1027 00:45:07,400 --> 00:45:11,550 null, hem comprovat si ha de ser a l'esquerra, però no ha de ser, tenim 1028 00:45:11,550 --> 00:45:14,640 comprovar si s'ha d'estar en el cert, però no ha de ser, clarament, ha de ser 1029 00:45:14,640 --> 00:45:15,870 just on som. 1030 00:45:15,870 --> 00:45:16,780 Això és un cas base. 1031 00:45:16,780 --> 00:45:19,920 Així que hi ha dos casos recursius intercalat en el medi. 1032 00:45:19,920 --> 00:45:21,630 Però jo podria haver escrit això en qualsevol ordre. 1033 00:45:21,630 --> 00:45:24,520 Només vaig pensar que semblava una mica naturals comprovar primer per a un possible error, 1034 00:45:24,520 --> 00:45:28,340 a continuació, comproveu l'esquerra, a continuació, comprovar bé, llavors se suposa que està en el node 1035 00:45:28,340 --> 00:45:30,630 en realitat estàs buscant. 1036 00:45:30,630 --> 00:45:36,240 >> Per què pot ser això útil? 1037 00:45:36,240 --> 00:45:37,910 Així que resulta - 1038 00:45:37,910 --> 00:45:42,110 i m'ho dius a mi saltar a un teaser aquí que hi ha al web. 1039 00:45:42,110 --> 00:45:44,920 Anem a començar a utilitzar no és un llenguatge de programació al principi, però una 1040 00:45:44,920 --> 00:45:46,030 llenguatge de marques. 1041 00:45:46,030 --> 00:45:48,740 Un llenguatge de marques és un que és similars en esperit a la programació 1042 00:45:48,740 --> 00:45:51,715 llenguatge, però no li dóna la capacitat d'expressar-lògicament. 1043 00:45:51,715 --> 00:45:55,070 Només li dóna la capacitat de expressar estructuralment. 1044 00:45:55,070 --> 00:45:57,960 >> On vol posar alguna cosa a la pàgina, la pàgina web? 1045 00:45:57,960 --> 00:45:59,200 De quin color és el que vols fer això? 1046 00:45:59,200 --> 00:46:00,950 Quina mida de la lletra és el que vols fer això? 1047 00:46:00,950 --> 00:46:02,970 Quines paraules et fan realitat vulgui a la pàgina web? 1048 00:46:02,970 --> 00:46:04,060 Així que això és un llenguatge de marques. 1049 00:46:04,060 --> 00:46:07,690 Però anem a introduir ràpidament JavaScript, que és un fet i dret completa 1050 00:46:07,690 --> 00:46:08,560 llenguatge de programació. 1051 00:46:08,560 --> 00:46:12,530 Molt similar en aparença sintàcticament a C, però tindrà algun 1052 00:46:12,530 --> 00:46:15,200 agradable, més potent, més característiques d'ús fàcil. 1053 00:46:15,200 --> 00:46:18,050 >> I una de les frustracions en aquest punt en el semestre és que anem a 1054 00:46:18,050 --> 00:46:22,065 aviat aplicar corrector ortogràfic en un nombre molt menor línies de codi que utilitzen altres idiomes 1055 00:46:22,065 --> 00:46:25,580 que la mateixa C permet, però per raons de aviat anem a entendre. 1056 00:46:25,580 --> 00:46:27,750 Aquesta serà la primera tals pàgina web. 1057 00:46:27,750 --> 00:46:30,120 Serà completament decebedor, el primer que fem. 1058 00:46:30,120 --> 00:46:31,400 És simplement dir hola món. 1059 00:46:31,400 --> 00:46:34,010 Però si mai ho has vist abans, aquest és HTML, 1060 00:46:34,010 --> 00:46:35,670 Llenguatge de marcat d'hipertext. 1061 00:46:35,670 --> 00:46:39,310 >> Si vostè va a una opció de menú determinat en més qualsevol navegador, en qualsevol pàgina web en 1062 00:46:39,310 --> 00:46:43,160 l'Internet, vostè pot veure el codi HTML que algunes persones van escriure a 1063 00:46:43,160 --> 00:46:44,400 crear aquesta pàgina web. 1064 00:46:44,400 --> 00:46:47,850 I probablement no es veu tan breu o tan net com aquest. 1065 00:46:47,850 --> 00:46:51,400 Però va seguir el patró d'aquests suports oberts i talls i 1066 00:46:51,400 --> 00:46:53,660 les lletres i els números potencialment. 1067 00:46:53,660 --> 00:46:56,770 >> Vaig pensar que et donaria un teaser del que serà capaç de fer 1068 00:46:56,770 --> 00:46:57,950 després de prendre CS50. 1069 00:46:57,950 --> 00:47:02,620 Déjame anar a cs.harvard.edu / rob, pàgina d'inici del nostre propi Rob Bowden. 1070 00:47:02,620 --> 00:47:06,080 Ell va fer això per nosaltres. 1071 00:47:06,080 --> 00:47:07,490 Així que aviat serà capaç de fer això. 1072 00:47:07,490 --> 00:47:10,660 I també, què has sentit aquest matí - 1073 00:47:10,660 --> 00:47:12,480 el que has sentit aquest matí - 1074 00:47:12,480 --> 00:47:13,780 >> [Hàmster DANSA MÚSICA] 1075 00:47:13,780 --> 00:47:15,702 >> - Vostè serà capaç de fer això. 1076 00:47:15,702 --> 00:47:16,790 Que ens espera dimecres. 1077 00:47:16,790 --> 00:47:17,791 Ens veiem llavors. 1078 00:47:17,791 --> 00:47:22,950 >> [Hàmster DANSA MÚSICA] 1079 00:47:22,950 --> 00:47:24,300 DAVID Malan: En la següent CS50 - 1080 00:47:24,300 --> 00:47:31,670