1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Música tocando] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Malan: Este é CS50. 5 00:00:14,010 --> 00:00:18,090 E isto é tanto o inicio eo end-- como literally-- case o final 6 00:00:18,090 --> 00:00:18,825 de seis semanas. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Eu penso que eu ía compartir un pouco dun feito divertido. 9 00:00:22,640 --> 00:00:25,370 Eu puxei iso desde un datos do semestre pasado definido. 10 00:00:25,370 --> 00:00:29,710 Debe lembrar que pedimos que en cada forma conxunto p se asistiu en liña 11 00:00:29,710 --> 00:00:31,580 ou se xa asistiu en persoa. 12 00:00:31,580 --> 00:00:33,020 E aquí están os datos. 13 00:00:33,020 --> 00:00:34,710 Entón, hoxe foi moi previsible. 14 00:00:34,710 --> 00:00:37,126 Pero queriamos pasar un pouco de tempo con vostede, con todo. 15 00:00:37,126 --> 00:00:40,599 Alguén quere conjecturar por que isto gráfico é tan irregular, ata abaixo, arriba abaixo, 16 00:00:40,599 --> 00:00:41,265 de forma consistente? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Que cada un dos picos e depresións representan? 19 00:00:45,130 --> 00:00:46,005 >> Audiencia: [inaudível] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Malan: De feito. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 E máis divertidamente, Deus me libre, temos unha charla o venres 24 00:00:55,480 --> 00:00:58,960 ao comezo do semestre, iso é o que vemos suceder. 25 00:00:58,960 --> 00:01:03,430 Entón, hoxe, nós participamos dun pouco máis sobre estruturas de datos. 26 00:01:03,430 --> 00:01:06,660 E, para darlle máis dun sólido modelo mental para problemas en cinco, 27 00:01:06,660 --> 00:01:07,450 que agora está fóra. 28 00:01:07,450 --> 00:01:10,817 Erros de ortografía, no cal, nós imos entregarlle un ficheiro de texto algúns 100.000 29 00:01:10,817 --> 00:01:12,650 máis palabras en inglés, e vai ter 30 00:01:12,650 --> 00:01:17,770 para descubrir como para cargalos de forma intelixente en memoria, na memoria RAM, utilizando-se algúns datos 31 00:01:17,770 --> 00:01:19,330 estrutura da súa elección. 32 00:01:19,330 --> 00:01:22,470 >> Agora, unha estrutura de datos podería ser, pero probablemente non debe ser, 33 00:01:22,470 --> 00:01:25,630 a lista ligada bastante simplista, que introducimos última vez. 34 00:01:25,630 --> 00:01:29,220 E unha lista ligada tiñan polo menos unha vantaxe sobre unha matriz. 35 00:01:29,220 --> 00:01:32,096 ¿Que é unha vantaxe de unha lista ligada sen dúbida? 36 00:01:32,096 --> 00:01:32,950 >> Audiencia: Inclusión. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: Inclusión. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 O que quere dicir con iso? 40 00:01:35,196 --> 00:01:37,872 >> Audiencia: En calquera lugar ao longo lista [inaudível]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Good. 42 00:01:38,770 --> 00:01:42,090 Así, pode introducir un elemento sempre quere no medio da lista 43 00:01:42,090 --> 00:01:45,490 sen ter que embaralhar calquera cousa, que concluíu, na nosa clasificación 44 00:01:45,490 --> 00:01:47,630 discusións, non é necesariamente unha cousa boa, 45 00:01:47,630 --> 00:01:51,200 porque leva tempo para realmente moverse todos os seres humanos cara á esquerda ou cara á dereita. 46 00:01:51,200 --> 00:01:55,540 E así, cunha lista ligada, pode só reservar con malloc, un novo nodo, 47 00:01:55,540 --> 00:01:58,385 e logo, actualizar un par de pointers-- dous, tres operacións max-- 48 00:01:58,385 --> 00:02:01,480 e somos capaces de encaixar alguén en calquera lugar nunha lista. 49 00:02:01,480 --> 00:02:03,550 >> Que máis se vantaxoso aproximadamente unha lista ligada? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Si? 52 00:02:05,659 --> 00:02:06,534 >> Audiencia: [inaudível] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID Malan: Perfecto. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perfecto. 57 00:02:11,090 --> 00:02:12,070 É moi dinámico. 58 00:02:12,070 --> 00:02:15,100 E que non está cometendo, anticipadamente, ata certo tamaño fixo 59 00:02:15,100 --> 00:02:18,750 anaco de memoria, como tería para con unha matriz, o cabeza de que 60 00:02:18,750 --> 00:02:22,455 é que pode reservar os nós só en demanda utilizando así só a cantidade de espazo 61 00:02:22,455 --> 00:02:23,330 como o que realmente precisa. 62 00:02:23,330 --> 00:02:26,830 En contraste con un array, pode accidentalmente reservar moi pouco. 63 00:02:26,830 --> 00:02:28,871 E despois é só ir ser unha dor no pescozo 64 00:02:28,871 --> 00:02:32,440 para recolocar unha nova matriz maior, copiar todo máis, liberar a matriz vella, 65 00:02:32,440 --> 00:02:33,990 e despois pasar sobre a súa empresa. 66 00:02:33,990 --> 00:02:37,479 Ou peor, pode reservar forma máis memoria do que realmente precisa, 67 00:02:37,479 --> 00:02:40,520 e así vai ter unha moi matriz escasamente poboada, por así dicir. 68 00:02:40,520 --> 00:02:44,350 >> Así, unha lista ligada dálle estas vantaxes de dinamismo e flexibilidade 69 00:02:44,350 --> 00:02:46,080 con insercións e borrados. 70 00:02:46,080 --> 00:02:48,000 Pero certamente debe haber un prezo a pagar. 71 00:02:48,000 --> 00:02:50,000 De feito, un dos temas explotada no cuestionario de cero 72 00:02:50,000 --> 00:02:52,430 era un par de os trade-offs vimos ata agora. 73 00:02:52,430 --> 00:02:56,161 Entón, o que é un prezo pagado ou a desvantaxe dunha lista ligada? 74 00:02:56,161 --> 00:02:56,660 Si. 75 00:02:56,660 --> 00:02:57,560 >> Audiencia: Sen acceso aleatorio. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: Sen acceso aleatorio. 77 00:02:58,809 --> 00:02:59,540 Pero quen lle importa? 78 00:02:59,540 --> 00:03:01,546 De acceso aleatorio non soa convincente. 79 00:03:01,546 --> 00:03:02,421 >> Audiencia: [inaudível] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Exactamente. 82 00:03:05,740 --> 00:03:07,580 Se queres ter un certo algorithm-- 83 00:03:07,580 --> 00:03:10,170 e déixeme realmente propoñer busca binaria, en particular, que 84 00:03:10,170 --> 00:03:12,600 é un que usei moito bit-- se non ten acceso aleatorio, 85 00:03:12,600 --> 00:03:15,516 non pode facelo aritmética simple de como atopar o elemento do medio 86 00:03:15,516 --> 00:03:16,530 e saltando dereito a ela. 87 00:03:16,530 --> 00:03:20,239 Non ten que comezar na primeira elemento e linearmente busca esquerda 88 00:03:20,239 --> 00:03:22,780 á dereita, se quere atopar a media ou de calquera outro elemento. 89 00:03:22,780 --> 00:03:24,410 >> Audiencia: Probablemente ocupa máis memoria. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Malan: ocupa máis memoria. 91 00:03:25,040 --> 00:03:27,464 Onde é que adicional custa vindo na memoria? 92 00:03:27,464 --> 00:03:28,339 >> Audiencia: [inaudível] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Exactamente. 95 00:03:33,440 --> 00:03:35,679 Neste caso aquí, tivemos unha lista encadeada de números enteiros, 96 00:03:35,679 --> 00:03:37,470 e aínda estamos dobrando a cantidade de memoria 97 00:03:37,470 --> 00:03:39,680 necesitamos tamén por almacenar eses punteiros. 98 00:03:39,680 --> 00:03:42,090 Agora menos de un gran negocio como súas estruturas quedan maiores 99 00:03:42,090 --> 00:03:45,320 e está almacenando non un número, pero quizais un estudante ou algún outro obxecto. 100 00:03:45,320 --> 00:03:46,880 Pero o punto seguro permanece. 101 00:03:46,880 --> 00:03:49,421 E así un certo número de tarefas en listas ligadas foron chamados 102 00:03:49,421 --> 00:03:50,570 eran grandes O lineal de n--. 103 00:03:50,570 --> 00:03:54,730 Cousas como inserción ou busca ou exclusión no caso dun elemento 104 00:03:54,730 --> 00:03:57,720 Aconteceu o final da a lista se está clasificado ou non. 105 00:03:57,720 --> 00:04:01,167 >> Ás veces pode ter sorte e en límites tan baixos sobre estas operacións 106 00:04:01,167 --> 00:04:04,250 pode tamén ser de tempo constante, se está sempre mirando para o primeiro elemento, 107 00:04:04,250 --> 00:04:05,070 por exemplo. 108 00:04:05,070 --> 00:04:09,360 Pero, ao final, que prometeu para alcanzar o Santo Graal 109 00:04:09,360 --> 00:04:12,630 de estruturas de datos, ou algúns destes aproximación, 110 00:04:12,630 --> 00:04:14,290 por medio de constante de tempo. 111 00:04:14,290 --> 00:04:17,579 Podemos atopar elementos ou engadir elementos ou eliminar elementos dunha lista? 112 00:04:17,579 --> 00:04:19,059 Veremos en breve. 113 00:04:19,059 --> 00:04:21,100 E verifícase que un dos mecanismos que estamos 114 00:04:21,100 --> 00:04:23,464 comezará a usar hoxe, utilización anual en p establecer cinco, 115 00:04:23,464 --> 00:04:24,630 é realmente moi familiar. 116 00:04:24,630 --> 00:04:27,430 Por exemplo, se se trata dun grupo libros de exame, cada un dos cales 117 00:04:27,430 --> 00:04:29,660 ten un alumno de primeira nome e apelidos, 118 00:04:29,660 --> 00:04:31,820 e eu busca-las a partir de ao final dun exame, 119 00:04:31,820 --> 00:04:33,746 e todos eles son moi moi nunha orde aleatoria, 120 00:04:33,746 --> 00:04:36,370 e queremos ir sobre a clasificación estes exames, de modo que, unha vez clasificado 121 00:04:36,370 --> 00:04:38,661 é só moito máis fácil e máis rápido para entrega-los de volta para fóra 122 00:04:38,661 --> 00:04:40,030 para os alumnos por orde alfabética. 123 00:04:40,030 --> 00:04:42,770 Que os seus instintos ser para unha pila de exames como este? 124 00:04:42,770 --> 00:04:45,019 >> Ben, se vostede é como eu, vostede verás que iso é m, 125 00:04:45,019 --> 00:04:48,505 entón eu vou especie de poñer isto en, se esta é a miña mesa ou o meu piso, onde 126 00:04:48,505 --> 00:04:50,650 Estou espallando cousas out-- ou miña matriz realmente-- 127 00:04:50,650 --> 00:04:52,210 Podería poñer todo o Ms alí dentro. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Velaquí un A. Entón eu podería Como poñer os aquí. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Aquí está outro A. Vou poñer isto aquí. 132 00:04:57,980 --> 00:05:02,490 Velaquí un Z. Aquí está outro M. E así Podería comezar a facer pilas como esta. 133 00:05:02,490 --> 00:05:06,620 E entón quizais eu ía máis tarde e tipo de moi detallista-ly tipo 134 00:05:06,620 --> 00:05:07,710 as pilas individuais. 135 00:05:07,710 --> 00:05:11,300 Pero o punto é que eu quedaría na entrada que eu son destro 136 00:05:11,300 --> 00:05:14,016 e gustaríame facer un calculado decisión con base nesa entrada. 137 00:05:14,016 --> 00:05:15,640 Se comeza con A, colocar-lo alí. 138 00:05:15,640 --> 00:05:18,980 Se comeza con Z, poñelas sobre alí, e todo máis. 139 00:05:18,980 --> 00:05:22,730 >> Polo tanto, esta é unha técnica que é xeralmente coñecido como hashing-- H-A-S-h-- 140 00:05:22,730 --> 00:05:26,550 o que xeralmente significa tomar como de entrada e usando que a entrada para calcular 141 00:05:26,550 --> 00:05:30,940 un valor, xeralmente, un número, e que número é o índice para un dispositivo de almacenamento 142 00:05:30,940 --> 00:05:32,260 recipiente, como unha matriz. 143 00:05:32,260 --> 00:05:35,490 Polo tanto, noutras palabras, eu podería ter un función de hash, como fago na miña cabeza, 144 00:05:35,490 --> 00:05:37,940 que, se eu vexo alguén é nome que comeza con A, 145 00:05:37,940 --> 00:05:40,190 Eu estou indo a mapear que a cero na miña cabeza. 146 00:05:40,190 --> 00:05:44,160 E se eu vexo alguén con Z, eu son vai mapear que a 25 na miña cabeza 147 00:05:44,160 --> 00:05:46,220 e logo, poñer isto en o último máis pila. 148 00:05:46,220 --> 00:05:50,990 >> Agora, se pensar en non meu cerebro Pero un programa C, o que os números poderían 149 00:05:50,990 --> 00:05:53,170 confiar para lograr este mesmo resultado? 150 00:05:53,170 --> 00:05:55,594 Noutras palabras, se tiña o carácter ASCII A, 151 00:05:55,594 --> 00:05:57,510 como é posible determinar o balde para poñelas? 152 00:05:57,510 --> 00:05:59,801 Probablemente non quere poñelas balde de 65 anos, que 153 00:05:59,801 --> 00:06:01,840 Sería como alí sen unha boa razón. 154 00:06:01,840 --> 00:06:04,320 Onde queiras poñer un en termos do seu valor ASCII? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Onde quere facer para o seu ASCII valor para chegar a un balde de forma máis intelixente 157 00:06:08,920 --> 00:06:09,480 para poñelas? 158 00:06:09,480 --> 00:06:10,206 >> Audiencia: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Yeah. 160 00:06:10,956 --> 00:06:13,190 Así, menos un ou menos especialmente 65 se é 161 00:06:13,190 --> 00:06:18,240 un capital A. Ou 98 se é unha minúscula a. 162 00:06:18,240 --> 00:06:21,300 E así que nos permiten, moi de xeito sinxelo e moi aritmeticamente, 163 00:06:21,300 --> 00:06:23,260 poñer algo en un balde así. 164 00:06:23,260 --> 00:06:26,010 Entón non é que realmente facemos este ben mesmo cos quizzes. 165 00:06:26,010 --> 00:06:29,051 >> Así, pode lembrar que circulou seu Nome ensino compañeiro na capa. 166 00:06:29,051 --> 00:06:32,270 E os nomes do TF organizáronse estas columnas en orde alfabética, 167 00:06:32,270 --> 00:06:34,400 Ben, cren ou non, cando todos 80 máis de nós 168 00:06:34,400 --> 00:06:37,800 reuníronse na outra noite para grao, o último paso no noso proceso de clasificación 169 00:06:37,800 --> 00:06:41,830 é para picar os cuestionarios nunha gran espazo de chan no [inaudível] 170 00:06:41,830 --> 00:06:45,110 e establecer quizzes de todos para fóra exactamente na orde dos seus TF de 171 00:06:45,110 --> 00:06:47,700 nomes na portada, xa entón é moito máis doado para nós 172 00:06:47,700 --> 00:06:51,290 a procura a través de que o uso lineal buscar ou algún tipo de intelixencia 173 00:06:51,290 --> 00:06:54,050 para un TF para atopar o seu ou quizzes dos seus alumnos. 174 00:06:54,050 --> 00:06:56,060 >> Entón, esa idea de hashing que verá é 175 00:06:56,060 --> 00:07:00,520 moi poderoso é realmente moi banal e moi intuitiva, 176 00:07:00,520 --> 00:07:03,000 moi parecido, quizais, e dividir conquista foi a semana cero. 177 00:07:03,000 --> 00:07:05,250 Eu avance rápido á hackathon un par de anos. 178 00:07:05,250 --> 00:07:08,040 Este foi Zamyla e un par de outros alumnos saúdo persoal 179 00:07:08,040 --> 00:07:09,030 como eles entraron. 180 00:07:09,030 --> 00:07:12,680 E tivemos unha morea de dobradura mesas alí con etiquetas de nome. 181 00:07:12,680 --> 00:07:15,380 E nós tiñamos as etiquetas de nome organizado con como os Como por alí 182 00:07:15,380 --> 00:07:16,690 eo ZS alí. 183 00:07:16,690 --> 00:07:20,350 E así un dos TFS moi intelixente escribiu isto como as instrucións 184 00:07:20,350 --> 00:07:21,030 ao día. 185 00:07:21,030 --> 00:07:24,480 E a semana 12 do semestre este todo fixo sentido perfecto e todos 186 00:07:24,480 --> 00:07:25,310 sabía o que facer. 187 00:07:25,310 --> 00:07:27,900 Pero sempre que teño enfileirados no mesmo xeito, 188 00:07:27,900 --> 00:07:30,272 está aplicando o mesma noción dun hash. 189 00:07:30,272 --> 00:07:31,730 Entón, imos formalizar-lo un pouco. 190 00:07:31,730 --> 00:07:32,890 Aquí é unha matriz. 191 00:07:32,890 --> 00:07:36,820 El está deseñado para ser un pouco gran só para describir, visualmente, 192 00:07:36,820 --> 00:07:38,920 para que poidamos poñer cordas en algo como isto. 193 00:07:38,920 --> 00:07:41,970 E esa matriz é claramente de tamaño 26 total. 194 00:07:41,970 --> 00:07:43,935 E a cousa chámase mesa de forma arbitraria. 195 00:07:43,935 --> 00:07:48,930 Pero esta é só capitulación dun artista que unha táboa hash pode ser. 196 00:07:48,930 --> 00:07:52,799 >> Así, unha táboa hash agora vai ser unha estrutura de datos de nivel superior. 197 00:07:52,799 --> 00:07:54,840 Ao final do día estamos a piques de ver que 198 00:07:54,840 --> 00:07:58,700 pode aplicar unha táboa hash, que é moi parecido a liña de facturación 199 00:07:58,700 --> 00:08:02,059 a unha hackathon moi parecido con este táboa usada para clasificar os libros de exame. 200 00:08:02,059 --> 00:08:03,850 Pero unha táboa hash é especie de agasallo de alto nivel 201 00:08:03,850 --> 00:08:08,250 concepto que podería usar unha matriz debaixo do capó para implementar lo, 202 00:08:08,250 --> 00:08:11,890 ou pode usar unha lista de lonxitude, ou mesmo quizais algunhas outras estruturas de datos. 203 00:08:11,890 --> 00:08:15,590 E agora que é a toma theme-- algúns destes ingredientes fundamentais 204 00:08:15,590 --> 00:08:18,310 como un array e este edificio bloquear agora dunha lista de lonxitude 205 00:08:18,310 --> 00:08:21,740 e ver o que máis podemos construír enriba de quen, como ingredientes 206 00:08:21,740 --> 00:08:26,550 nunha receita, tornándose cada vez máis resultados finais interesantes e útiles. 207 00:08:26,550 --> 00:08:28,680 >> Así, coa táboa hash podemos implementar lo 208 00:08:28,680 --> 00:08:32,540 na memoria pictoricamente como este, pero como pode realmente ser codificado enriba? 209 00:08:32,540 --> 00:08:33,789 Ben, quizais simplemente como é iso. 210 00:08:33,789 --> 00:08:38,270 Se a capacidade en todas as tapas, é só algúns constant-- por exemplo 26, 211 00:08:38,270 --> 00:08:42,030 para 26 letras do alphabet-- Podería chamar de miña mesa variable, 212 00:08:42,030 --> 00:08:45,630 e eu podería dicir que eu vou poñer estrelas de char alí, ou cadea. 213 00:08:45,630 --> 00:08:49,880 Por iso, é tan sinxelo coma iso se quere aplicar unha táboa hash. 214 00:08:49,880 --> 00:08:51,490 E, con todo, iso é realmente só unha matriz. 215 00:08:51,490 --> 00:08:53,198 Pero, de novo, un hash táboa é agora o que imos 216 00:08:53,198 --> 00:08:57,470 chamar un tipo abstracto de datos que é só unha especie de estratificación conceptual na parte superior 217 00:08:57,470 --> 00:09:00,780 de algo máis mundano agora como un array. 218 00:09:00,780 --> 00:09:02,960 >> Agora, como é que imos sobre a resolución de problemas? 219 00:09:02,960 --> 00:09:06,980 Ben, en principio eu tiven o luxo de ter espazo suficiente mesa aquí 220 00:09:06,980 --> 00:09:09,460 para que eu puidese poñer o quizzes en calquera lugar que eu quería. 221 00:09:09,460 --> 00:09:10,620 Entón, como pode ir aquí. 222 00:09:10,620 --> 00:09:12,100 Zs pode ir aquí. 223 00:09:12,100 --> 00:09:13,230 MS pode ir aquí. 224 00:09:13,230 --> 00:09:14,740 E entón eu tiven un pouco de espazo extra. 225 00:09:14,740 --> 00:09:18,740 Pero iso é un pouco de un dereito de fraude agora, porque esta táboa, se realmente 226 00:09:18,740 --> 00:09:22,720 penso niso como unha matriz, é só será de preto de tamaño fixo. 227 00:09:22,720 --> 00:09:25,380 >> Entón, tecnicamente, se eu tirar se cuestionario doutro alumno 228 00:09:25,380 --> 00:09:28,490 e ver, oh, esta persoa de nome comeza cun A tamén, 229 00:09:28,490 --> 00:09:30,980 Eu medio que quero poñer-lo alí. 230 00:09:30,980 --> 00:09:34,740 Pero así que eu colocar-lo alí, se esta táboa de feito representa unha matriz, 231 00:09:34,740 --> 00:09:37,840 Eu vou estar substituíndo ou sobrepasar quen cuestionario deste alumno é. 232 00:09:37,840 --> 00:09:38,340 Non? 233 00:09:38,340 --> 00:09:41,972 Se este é un array, só unha cousa pode ir en cada unha destas células ou elementos. 234 00:09:41,972 --> 00:09:43,680 E entón eu medio que teño de escoller. 235 00:09:43,680 --> 00:09:45,735 >> Agora antes de que eu tipo de enganado e fixo iso ou eu 236 00:09:45,735 --> 00:09:47,526 só unha especie de empilhados Los por riba da outra. 237 00:09:47,526 --> 00:09:49,170 Pero iso non vai voar no código. 238 00:09:49,170 --> 00:09:52,260 Entón, onde eu podería poñer o segundo alumno cuxo nome 239 00:09:52,260 --> 00:09:54,964 é A, se todo o que eu tiña é este dispoñible espazo de táboa? 240 00:09:54,964 --> 00:09:57,880 E eu usei tres slots e que Parece que hai só uns doutros. 241 00:09:57,880 --> 00:09:58,959 O que podería facer? 242 00:09:58,959 --> 00:09:59,834 Audiencia: [inaudível] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Malan: Yeah. 245 00:10:01,315 --> 00:10:02,370 Quizais imos mantelo simple. 246 00:10:02,370 --> 00:10:02,660 Non? 247 00:10:02,660 --> 00:10:04,243 Ela non encaixa onde quero poñelas. 248 00:10:04,243 --> 00:10:07,450 Entón, eu vou poñelas tecnicamente, onde un B ía. 249 00:10:07,450 --> 00:10:09,932 Agora, por suposto, eu estou empezando a pintar-me nunha esquina. 250 00:10:09,932 --> 00:10:11,890 Se eu chegar a un estudante cuxo nome é, en realidade, B, 251 00:10:11,890 --> 00:10:14,840 agora B será movido algo para adiante, como pode pasar, si, 252 00:10:14,840 --> 00:10:17,530 se este é un B, agora ten que ir aquí. 253 00:10:17,530 --> 00:10:20,180 >> E por iso esta moi rapidamente podería chegar a ser problemático, 254 00:10:20,180 --> 00:10:23,850 pero é unha técnica que, en realidade, se refire como lineal de sondaxe, 255 00:10:23,850 --> 00:10:26,650 en que considerar só o seu matriz de ser ao longo da liña. 256 00:10:26,650 --> 00:10:29,680 E só tipo de sonda ou inspeccionar cada elemento dispoñible 257 00:10:29,680 --> 00:10:31,360 buscando un lugar dispoñible. 258 00:10:31,360 --> 00:10:34,010 E así que atopa un, large-lo alí dentro. 259 00:10:34,010 --> 00:10:38,390 >> Agora, o prezo a ser pago agora para esta solución é o que? 260 00:10:38,390 --> 00:10:41,300 Temos unha matriz de tamaño fixo, e cando inserir nomes 261 00:10:41,300 --> 00:10:44,059 para el, polo menos inicialmente, o que é o tempo de execución de inserción 262 00:10:44,059 --> 00:10:46,350 para poñer os alumnos quizzes nos baldes non? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O de que? 265 00:10:50,002 --> 00:10:51,147 >> Audiencia: n. 266 00:10:51,147 --> 00:10:52,480 DAVID Malan: Eu oín gran O de n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Non é certo. 269 00:10:54,300 --> 00:10:56,490 Pero nós imos provocar unha separación por que en só un momento. 270 00:10:56,490 --> 00:10:57,702 O que máis podería ser? 271 00:10:57,702 --> 00:10:58,755 >> Audiencia: [inaudível] 272 00:10:58,755 --> 00:11:00,380 DAVID Malan: E déixeme facelo visualmente. 273 00:11:00,380 --> 00:11:04,720 Entón, supoñamos que esta é a letra S. 274 00:11:04,720 --> 00:11:05,604 >> Audiencia: É unha. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: É unha. 276 00:11:06,520 --> 00:11:06,710 Non? 277 00:11:06,710 --> 00:11:08,950 Esta é unha matriz, que significa que temos acceso aleatorio. 278 00:11:08,950 --> 00:11:11,790 E se pensamos desa como cero e iso como 25, 279 00:11:11,790 --> 00:11:13,800 e entendemos que, oh, aquí está a miña entrada S, 280 00:11:13,800 --> 00:11:16,350 Eu certamente podo converter S, un carácter ASCII, 281 00:11:16,350 --> 00:11:18,540 a un número correspondente entre cero e 25 282 00:11:18,540 --> 00:11:20,910 e, a continuación, inmediatamente poñelas onde pertence. 283 00:11:20,910 --> 00:11:26,120 >> Pero, claro, así que eu chegar ao segunda persoa cuxo nome é A ou B ou C 284 00:11:26,120 --> 00:11:29,300 finalmente, se eu usei o lineal enquisa como a miña solución, 285 00:11:29,300 --> 00:11:31,360 o tempo de execución inserción no peor caso 286 00:11:31,360 --> 00:11:33,120 é realmente vai transformarse en que? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 E eu oín-lo aquí correctamente desde o principio. 289 00:11:36,045 --> 00:11:36,920 Audiencia: [inaudível] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Así é, de feito, xa n ten unha suficientemente grande conxunto de datos. 291 00:11:41,620 --> 00:11:44,410 Así, por unha banda, se a matriz é grande abondo 292 00:11:44,410 --> 00:11:48,287 e os seus datos é escasa o suficiente, obter este tempo constante bonito. 293 00:11:48,287 --> 00:11:50,620 Pero así que comezar a quedando máis e máis elementos, 294 00:11:50,620 --> 00:11:53,200 e só estatisticamente que comeza máis persoas coa letra 295 00:11:53,200 --> 00:11:56,030 Unha como o seu nome ou a letra B, que podería potencialmente 296 00:11:56,030 --> 00:11:57,900 transformarse en algo máis lineal. 297 00:11:57,900 --> 00:11:59,640 Entón, non é absolutamente perfecto. 298 00:11:59,640 --> 00:12:00,690 Entón, poderíamos facer mellor? 299 00:12:00,690 --> 00:12:03,210 >> Ben, o que foi a nosa solución antes cando nós 300 00:12:03,210 --> 00:12:06,820 quere ter máis dinamismo do que algo así como unha matriz permitido? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 Audiencia: [inaudível] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: O que nós presentamos? 304 00:12:10,030 --> 00:12:10,530 Si. 305 00:12:10,530 --> 00:12:11,430 Así, unha lista ligada. 306 00:12:11,430 --> 00:12:14,430 Ben, imos ver o que un conectado lista pode facer por nós no seu lugar. 307 00:12:14,430 --> 00:12:17,630 Ben, deixe-me propor que deseñar a imaxe do seguinte xeito. 308 00:12:17,630 --> 00:12:19,620 Agora este é un diferente imaxe dun exemplo 309 00:12:19,620 --> 00:12:24,750 a partir dun texto diferente, de feito, que é, en realidade, usando unha matriz de tamaño 31. 310 00:12:24,750 --> 00:12:28,220 E este autor simplemente decidiu botar cordas 311 00:12:28,220 --> 00:12:32,430 non en base a nomes da persoa, pero en base ás súas datas de nacemento. 312 00:12:32,430 --> 00:12:35,680 Independentemente do mes, figuraron se naceu o primeiro día dun mes 313 00:12:35,680 --> 00:12:39,580 ou o día 31 dun mes, o autor vai botar en base nese valor, 314 00:12:39,580 --> 00:12:44,154 de forma a difundir os nomes un pouco máis que 26 puntos pode permitir. 315 00:12:44,154 --> 00:12:47,320 E quizais sexa un pouco máis uniforme que ir coas letras do alfabeto, 316 00:12:47,320 --> 00:12:50,236 porque está claro que hai, probablemente, máis persoas no mundo con nomes 317 00:12:50,236 --> 00:12:54,020 que comezar con unha que seguramente algunhas outras letras do alfabeto. 318 00:12:54,020 --> 00:12:56,380 Entón quizais iso sexa un pouco máis uniforme, asumindo 319 00:12:56,380 --> 00:12:58,640 unha distribución uniforme de bebés a través dun mes. 320 00:12:58,640 --> 00:12:59,990 >> Pero, por suposto, iso aínda é imperfecto. 321 00:12:59,990 --> 00:13:00,370 Non? 322 00:13:00,370 --> 00:13:01,370 Estamos tendo colisións. 323 00:13:01,370 --> 00:13:04,680 Varias persoas nesta estrutura de datos aínda son 324 00:13:04,680 --> 00:13:08,432 tendo a mesma data de nacemento, polo menos vostede independentemente do mes. 325 00:13:08,432 --> 00:13:09,640 Pero o que o autor fixo? 326 00:13:09,640 --> 00:13:13,427 Ben, parece que temos un array no lado da man esquerda tomada en vertical, 327 00:13:13,427 --> 00:13:15,010 pero iso é só interpretación dun artista. 328 00:13:15,010 --> 00:13:18,009 Non importa que dirección ten deseñar unha matriz, que aínda é un array. 329 00:13:18,009 --> 00:13:20,225 ¿Que é iso unha serie de parecer? 330 00:13:20,225 --> 00:13:21,500 >> Audiencia: lista encadeada. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Yeah. 332 00:13:21,650 --> 00:13:23,490 Parece que é unha matriz de lista ligada. 333 00:13:23,490 --> 00:13:26,490 Entón, de novo, a este punto de tipo de usar esas estruturas de datos agora 334 00:13:26,490 --> 00:13:28,550 como ingredientes a máis solucións interesantes, 335 00:13:28,550 --> 00:13:30,862 pode perfectamente ter un fundamentais, como unha matriz, 336 00:13:30,862 --> 00:13:33,320 e logo tomar algo máis interesante como unha lista ligada 337 00:13:33,320 --> 00:13:36,660 e mesmo combina-los nun mesmo estrutura de datos máis interesante. 338 00:13:36,660 --> 00:13:39,630 E, de feito, iso tamén sería ser chamado unha táboa hash, 339 00:13:39,630 --> 00:13:42,610 polo que a matriz é realmente a táboa hash, 340 00:13:42,610 --> 00:13:45,600 pero que ten táboa hash correntes, por así dicir, 341 00:13:45,600 --> 00:13:50,220 que pode crecer ou psiquiatra con base no número de elementos que quere inserir. 342 00:13:50,220 --> 00:13:52,990 >> Agora, nese sentido, o que é o tempo de execución agora? 343 00:13:52,990 --> 00:13:58,030 Se eu queira inserir alguén cuxo aniversario é o 31 de outubro de 344 00:13:58,030 --> 00:13:59,040 onde é que el ou ela vai? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Todo correcto. 347 00:14:01,030 --> 00:14:02,819 Na parte inferior, onde el di que 31. 348 00:14:02,819 --> 00:14:03,610 E iso é perfecto. 349 00:14:03,610 --> 00:14:05,060 Ese foi o tempo constante. 350 00:14:05,060 --> 00:14:08,760 Pero o que se atopar alguén cuxo aniversario é, imos ver, 351 00:14:08,760 --> 00:14:10,950 Outubro, novembro, 31 de decembro? 352 00:14:10,950 --> 00:14:12,790 Onde é que el ou ela vai? 353 00:14:12,790 --> 00:14:13,290 Mesmo. 354 00:14:13,290 --> 00:14:13,970 Dúas etapas aínda. 355 00:14:13,970 --> 00:14:15,303 Isto é constante, aínda que, non é? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Todo correcto. 358 00:14:16,860 --> 00:14:17,840 No momento en que ela é. 359 00:14:17,840 --> 00:14:20,570 Pero, no caso xeral, canto máis a xente que agregan, 360 00:14:20,570 --> 00:14:23,790 probabilisticamente, imos para obter máis e máis colisións. 361 00:14:23,790 --> 00:14:26,820 >> Agora iso é un pouco mellor, porque técnicamente 362 00:14:26,820 --> 00:14:34,580 Agora miñas cadeas poderían estar en o peor caso canto tempo? 363 00:14:34,580 --> 00:14:38,890 Se eu inserir n persoas a este máis estrutura de datos sofisticado, n persoas, 364 00:14:38,890 --> 00:14:41,080 no peor dos casos vai ser n. 365 00:14:41,080 --> 00:14:41,815 Por que? 366 00:14:41,815 --> 00:14:43,332 >> Audiencia: Por se todo o mundo ten o mesmo aniversario, 367 00:14:43,332 --> 00:14:44,545 están indo a ser unha liña. 368 00:14:44,545 --> 00:14:45,420 DAVID Malan: Perfecto. 369 00:14:45,420 --> 00:14:47,480 Pode ser un pouco artificial, pero realmente, no peor caso, 370 00:14:47,480 --> 00:14:50,117 se todo o mundo ten o mesmo aniversario, dadas as entradas que ten, 371 00:14:50,117 --> 00:14:51,950 vai ter un masivamente cadea longa. 372 00:14:51,950 --> 00:14:54,241 E así, podería chamalo de un Hash Table, pero realmente é 373 00:14:54,241 --> 00:14:56,810 só unha enorme lista ligada unha morea de espazo desperdiçado. 374 00:14:56,810 --> 00:15:00,460 Pero, en xeral, se asumirmos que polo menos, os aniversarios son uniform-- 375 00:15:00,460 --> 00:15:01,750 e probablemente non é. 376 00:15:01,750 --> 00:15:02,587 Eu estou facendo iso. 377 00:15:02,587 --> 00:15:04,420 Pero se asumirmos, por a causa da discusión 378 00:15:04,420 --> 00:15:07,717 que son, entón, en teoría, se esta é a representación verticais 379 00:15:07,717 --> 00:15:11,050 da matriz, así, entón espero que está se ve cadeas que son, vostede sabe, 380 00:15:11,050 --> 00:15:15,880 aproximadamente a mesma lonxitude, onde cada un dos deles representa un día do mes. 381 00:15:15,880 --> 00:15:19,930 >> Agora, se hai 31 días no mes, isto significa que o meu tempo de carreira realmente 382 00:15:19,930 --> 00:15:25,230 é grande O de n máis de 31, que sente mellor que linear. 383 00:15:25,230 --> 00:15:27,950 Pero o que era un dos nosos compromisos de algunhas semanas 384 00:15:27,950 --> 00:15:31,145 sempre hai que se trataba de expresar o tempo de execución dun algoritmo? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Basta só ollar para o termo de orde superior. 387 00:15:35,190 --> 00:15:35,690 Non? 388 00:15:35,690 --> 00:15:37,400 31 é sempre útil. 389 00:15:37,400 --> 00:15:39,610 Pero iso aínda é grande O de n. 390 00:15:39,610 --> 00:15:41,730 Pero un dos temas do conxunto de problemas de cinco 391 00:15:41,730 --> 00:15:43,950 será a recoñecer que absolutamente, 392 00:15:43,950 --> 00:15:47,320 asintótica, teoricamente esta estrutura de datos 393 00:15:47,320 --> 00:15:50,470 non é mellor que só unha lista ligada maciza. 394 00:15:50,470 --> 00:15:53,550 E, de feito, no peor dos casos, este táboa hash pode transformarse en que. 395 00:15:53,550 --> 00:15:57,620 >> Pero no mundo real, con nós seres humanos que os propios Macs ou PC ou o que quere 396 00:15:57,620 --> 00:16:01,240 e están en execución no mundo real software en datos do mundo real, 397 00:16:01,240 --> 00:16:03,260 algoritmo que vai preferir? 398 00:16:03,260 --> 00:16:09,180 Aquel que toma medidas finais ou á que leva n dividido por 31 pasos 399 00:16:09,180 --> 00:16:12,900 para atopar algunha peza de datos ou para buscar información? 400 00:16:12,900 --> 00:16:16,580 Quero dicir, absolutamente as 31 marcas unha diferenza no mundo real. 401 00:16:16,580 --> 00:16:18,540 É 31 veces máis rápido. 402 00:16:18,540 --> 00:16:20,880 E nós, os seres humanos son, sen dúbida, vai apreciar isto. 403 00:16:20,880 --> 00:16:23,004 >> Así, entender a dicotomía en realidade existe entre 404 00:16:23,004 --> 00:16:25,920 falando cousas teoricamente e asintótica que definitivamente 405 00:16:25,920 --> 00:16:28,760 ten valor como vimos, pero no mundo real, 406 00:16:28,760 --> 00:16:32,930 se se preocupa só facendo o feliz humano para as entradas xerais, 407 00:16:32,930 --> 00:16:36,010 pode moi ben querer aceptar o feito de que, si, é dicir lineal, 408 00:16:36,010 --> 00:16:38,360 pero é 31 veces máis rápido que se pode lineal. 409 00:16:38,360 --> 00:16:41,610 E mellor aínda, non só temos que facer algo arbitrario como a data de nacemento, 410 00:16:41,610 --> 00:16:44,030 poderiamos pasar un pouco máis tempo e intelixencia 411 00:16:44,030 --> 00:16:47,140 e pensar sobre o que poderiamos facer, dado o nome dunha persoa e quizais 412 00:16:47,140 --> 00:16:50,130 a súa data de nacemento para combinar os ingredientes para descubrir algo 413 00:16:50,130 --> 00:16:52,720 que é verdadeiramente máis uniforme e menos irregular, 414 00:16:52,720 --> 00:16:56,250 por así dicir que esta foto actualmente suxire que podería ser. 415 00:16:56,250 --> 00:16:57,750 Como podemos aplicar isto no código? 416 00:16:57,750 --> 00:17:00,280 Ben, deixe-me propor que só pedir algún sintaxe temos 417 00:17:00,280 --> 00:17:01,799 utilizado un par de veces ata agora. 418 00:17:01,799 --> 00:17:03,590 E eu estou indo a definir un nó, que de novo 419 00:17:03,590 --> 00:17:06,812 é un termo xenérico para uns poucos recipiente para algunha estrutura de datos. 420 00:17:06,812 --> 00:17:09,020 Vou propoñer que unha secuencia que vai dentro. 421 00:17:09,020 --> 00:17:11,369 Pero imos comezar a tomar aquelas rodinhas fóra agora. 422 00:17:11,369 --> 00:17:13,230 >> Non hai máis biblioteca CS50 realmente, a menos que quere 423 00:17:13,230 --> 00:17:15,230 usalo para o seu final, proxecto, que é bo, 424 00:17:15,230 --> 00:17:18,569 pero agora estamos indo para tirar a cortina e dicir que é só unha estrela de char. 425 00:17:18,569 --> 00:17:22,069 Así, a palabra non será o nome da persoa en cuestión. 426 00:17:22,069 --> 00:17:25,079 E agora eu teño unha ligazón aquí ao seguinte nodo 427 00:17:25,079 --> 00:17:28,170 para que estes representan cada un dos nós 428 00:17:28,170 --> 00:17:30,950 na cadea, potencialmente, dunha lista ligada. 429 00:17:30,950 --> 00:17:34,090 >> E agora como fago para declarar propia táboa de hash? 430 00:17:34,090 --> 00:17:36,660 ¿Como declarar toda esta estrutura? 431 00:17:36,660 --> 00:17:40,960 Ben, en realidade, moi parecido que eu usei un punteiro para só o primeiro elemento dunha lista 432 00:17:40,960 --> 00:17:44,510 antes, do mesmo xeito podo só dicir Eu só teño unha morea de punteiros 433 00:17:44,510 --> 00:17:46,270 para aplicar esta táboa hash todo. 434 00:17:46,270 --> 00:17:49,484 Vou ter un array chamada de táboa para a táboa hash. 435 00:17:49,484 --> 00:17:50,900 Será de capacidade tamaño. 436 00:17:50,900 --> 00:17:52,525 É así que moitos elementos poden caber nel. 437 00:17:52,525 --> 00:17:56,180 E cada un deses elementos neste matriz vai ser unha estrela no. 438 00:17:56,180 --> 00:17:56,810 Por que? 439 00:17:56,810 --> 00:18:00,160 Ben, por esta foto, o que eu son aplicar a táboa de hash como 440 00:18:00,160 --> 00:18:04,330 principalmente no inicio é só esa matriz que temos deseñado en vertical, 441 00:18:04,330 --> 00:18:06,820 cada un de cuxos cadrados representa un punteiro. 442 00:18:06,820 --> 00:18:09,170 Que aqueles que teñen barras a través deles son só nulo. 443 00:18:09,170 --> 00:18:11,410 E os que teñen frechas que van cara á dereita 444 00:18:11,410 --> 00:18:16,140 son punteiros reais para nós reais, ergo o inicio dunha lista ligada. 445 00:18:16,140 --> 00:18:19,050 >> Entón, aquí, entón, é como podemos aplicar unha táboa hash que 446 00:18:19,050 --> 00:18:21,580 aplica o encadeamento separado. 447 00:18:21,580 --> 00:18:22,840 Agora podemos facer mellor? 448 00:18:22,840 --> 00:18:25,632 Todo ben que prometín a última vez que poderiamos conseguir tempo constante. 449 00:18:25,632 --> 00:18:27,381 E eu medio que lle deu constante de tempo aquí, 450 00:18:27,381 --> 00:18:29,850 pero logo non dixo realmente constante de tempo porque aínda é 451 00:18:29,850 --> 00:18:31,890 dependente do total número de elementos 452 00:18:31,890 --> 00:18:34,500 está introducindo en a estrutura de datos. 453 00:18:34,500 --> 00:18:35,980 Pero supoña que fixemos iso. 454 00:18:35,980 --> 00:18:39,550 Déixeme volver á pantalla aquí. 455 00:18:39,550 --> 00:18:44,520 Permítanme tamén proxectar esta aquí enriba, claro da pantalla, e supoño que eu fixen iso. 456 00:18:44,520 --> 00:18:49,300 Supoña que eu quería introducir o nome Daven en na miña estrutura de datos. 457 00:18:49,300 --> 00:18:52,100 >> Entón, quero introducir unha cadea Daven na estrutura de datos. 458 00:18:52,100 --> 00:18:54,370 E se eu non usar un Hash Table, pero eu uso 459 00:18:54,370 --> 00:18:56,980 algo que é máis do tipo árbore como unha árbore xenealóxica, onde 460 00:18:56,980 --> 00:18:59,670 tes algunha raíz no nós e follas superiores e, a continuación, 461 00:18:59,670 --> 00:19:01,440 que ir para abaixo e para fóra. 462 00:19:01,440 --> 00:19:04,450 Supoñamos, entón, que eu quere inserir Daven de 463 00:19:04,450 --> 00:19:06,430 en que é actualmente unha lista baleira. 464 00:19:06,430 --> 00:19:09,780 Vou facer o seguinte: Eu son vai crear un nó desta familia 465 00:19:09,780 --> 00:19:15,170 árbore-como estrutura de datos que parece algo parecido con iso, cada unha das cales 466 00:19:15,170 --> 00:19:19,640 rectángulos ten, digamos, para agora 26 elementos nel. 467 00:19:19,640 --> 00:19:21,650 E cada unha das células nesta matriz vai 468 00:19:21,650 --> 00:19:23,470 para representar a letra dun alfabeto. 469 00:19:23,470 --> 00:19:28,190 >> En concreto, eu estou indo para o tratamento este é A, entón B, entón C, entón D, 470 00:19:28,190 --> 00:19:29,310 este aquí. 471 00:19:29,310 --> 00:19:32,940 Entón, iso vai efectivamente representar a letra D. 472 00:19:32,940 --> 00:19:36,040 Pero para introducir todos Daven de nome eu teño que facer un pouco máis. 473 00:19:36,040 --> 00:19:37,840 Entón, eu estou indo primeiro para mestura, por así dicir. 474 00:19:37,840 --> 00:19:41,049 Vou ollar para a primeira letra en Daven do que é, obviamente, unha D, 475 00:19:41,049 --> 00:19:42,840 e eu estou indo a reservar un nó que parece 476 00:19:42,840 --> 00:19:45,570 como isto-- un gran rectángulo grande abondo para caber todo o alfabeto. 477 00:19:45,570 --> 00:19:47,140 >> Agora D está feito. 478 00:19:47,140 --> 00:19:49,720 Agora A. D-A-V-E-N é o obxectivo. 479 00:19:49,720 --> 00:19:51,220 Entón agora o que vou facer é esta. 480 00:19:51,220 --> 00:19:54,027 Así que comecei a notificación D non hai ningún punteiro alí. 481 00:19:54,027 --> 00:19:56,860 É valores de lixo, no momento, ou eu podería arrincar a null. 482 00:19:56,860 --> 00:19:59,630 Pero déixeme continuar esta idea de construír unha árbore. 483 00:19:59,630 --> 00:20:04,260 Déixeme reservar un deses nodos que contén 26 elementos nel. 484 00:20:04,260 --> 00:20:05,150 >> E vostede sabe o que? 485 00:20:05,150 --> 00:20:09,130 Se este é só un nó na memoria que Eu creei con malloc, usando unha struct 486 00:20:09,130 --> 00:20:11,240 como veremos en breve, Vou facer isso- 487 00:20:11,240 --> 00:20:14,450 Vou debuxar unha frecha de a cousa que representase D abaixo 488 00:20:14,450 --> 00:20:15,860 para este novo nodo. 489 00:20:15,860 --> 00:20:19,240 E agora, por primeira vez o seguinte carta en nome de Daven, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- vou ir adiante e deseñar outro nodo como este, 491 00:20:24,150 --> 00:20:30,150 polo que, os elementos de V, que aquí imos chamar de berros instance--. 492 00:20:30,150 --> 00:20:31,020 Non imos sacar alí. 493 00:20:31,020 --> 00:20:31,936 Vai aquí. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Entón nós imos consideran que se trata V. 496 00:20:35,712 --> 00:20:44,920 E entón aquí imos índice abaixo de V ao que imos considerar E. 497 00:20:44,920 --> 00:20:50,100 E entón dende aquí imos vaia ter un destes nós aquí. 498 00:20:50,100 --> 00:20:52,930 E agora temos unha pregunta para responder. 499 00:20:52,930 --> 00:20:57,840 Eu teño algunha maneira indican que estamos na fin da cadea Daven. 500 00:20:57,840 --> 00:20:59,490 Entón, eu podería deixar lo nulo. 501 00:20:59,490 --> 00:21:02,670 >> Pero o que se ten de Daven nome completo tamén, que 502 00:21:02,670 --> 00:21:04,280 é, como xa dixemos, Davenport? 503 00:21:04,280 --> 00:21:06,970 Entón, o que si é Daven realmente unha substring, 504 00:21:06,970 --> 00:21:08,960 un prefixo dunha secuencia moito máis tempo? 505 00:21:08,960 --> 00:21:11,450 Non podemos simplemente permanentemente dicir nada vai 506 00:21:11,450 --> 00:21:14,410 para ir alí, porque podiamos nunca, introduce unha palabra como Davenport 507 00:21:14,410 --> 00:21:15,840 para esta estrutura de datos 508 00:21:15,840 --> 00:21:19,560 >> Entón, o que poderiamos facer é no canto tratar cada un destes elementos 509 00:21:19,560 --> 00:21:22,170 Tendo como quizais dous elementos dentro deles. 510 00:21:22,170 --> 00:21:24,810 Un deles é un punteiro, de feito, como eu veño facendo. 511 00:21:24,810 --> 00:21:27,100 Así, cada unha destas caixas non é só un teléfono móbil. 512 00:21:27,100 --> 00:21:29,855 Pero e se o cumio um-- do un fondo 513 00:21:29,855 --> 00:21:32,230 será nulo, xa que non hai Davenport aínda. 514 00:21:32,230 --> 00:21:34,197 E se o cumio é algún valor especial? 515 00:21:34,197 --> 00:21:36,530 E iso vai ser un pouco difícil deséñase la deste tamaño. 516 00:21:36,530 --> 00:21:38,130 Pero creo que é só unha marca de verificación. 517 00:21:38,130 --> 00:21:38,920 Consulte. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N é unha secuencia nesta estrutura de datos. 519 00:21:44,230 --> 00:21:48,350 >> Mentres tanto, se eu tivese máis espazo aquí, eu podería facer P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 e eu podería poñer facturar o no que ten a letra T ao final. 521 00:21:52,650 --> 00:21:55,460 Polo tanto, este é un masivamente estrutura de datos de aparencia complexa. 522 00:21:55,460 --> 00:21:57,210 E a miña letra certamente non axuda. 523 00:21:57,210 --> 00:22:00,043 Pero se eu quería introducir algo outra cousa, considerada o que fariamos. 524 00:22:00,043 --> 00:22:03,370 Se quixésemos poñer David na, nós seguen a mesma lóxica, D-A-V, 525 00:22:03,370 --> 00:22:08,802 pero agora eu apuntaría a próxima elemento non desde E, aínda que a partir de I a D. 526 00:22:08,802 --> 00:22:10,760 Polo tanto, non será máis nós nesta árbore. 527 00:22:10,760 --> 00:22:12,325 Nós imos ter chamada malloc máis. 528 00:22:12,325 --> 00:22:14,700 Pero eu non quero facer unha desorde completa da imaxe. 529 00:22:14,700 --> 00:22:17,710 Entón, imos ollar a unha vez que foi pre-formuladas 530 00:22:17,710 --> 00:22:21,810 así con non punto, punto, puntos, pero só matrices abreviados. 531 00:22:21,810 --> 00:22:23,950 Pero cada un dos nós nesta árbore-se aquí 532 00:22:23,950 --> 00:22:26,700 representa o mesmo coisa-- unha serie de Ray tamaño 26. 533 00:22:26,700 --> 00:22:28,860 >> Ou, se quere ser realmente bo momento, o que 534 00:22:28,860 --> 00:22:30,790 se o nome de alguén como un apóstrofo, imos 535 00:22:30,790 --> 00:22:35,560 supoñer que cada nodo ten realmente como 27 índices en que, non só 26. 536 00:22:35,560 --> 00:22:42,020 Entón, iso agora será un dos datos unha estrutura chamada trie-- T-R-I-e. 537 00:22:42,020 --> 00:22:46,120 Unha trie, que supostamente é historicamente un nome intelixente para unha árbore 538 00:22:46,120 --> 00:22:49,040 optimizado para de recuperación, o que, por suposto, 539 00:22:49,040 --> 00:22:50,870 é soletrado cun I-E por iso é trie. 540 00:22:50,870 --> 00:22:52,710 Pero esa é a historia da trie. 541 00:22:52,710 --> 00:22:55,860 >> Así, unha trie é estes datos en árbore estrutura como unha árbore xenealóxica 542 00:22:55,860 --> 00:22:57,510 que en definitiva se comporta así. 543 00:22:57,510 --> 00:23:00,890 E aquí é só un exemplo dunha todo morea de nomes doutras persoas. 544 00:23:00,890 --> 00:23:03,540 Pero a cuestión agora na man é o que ten 545 00:23:03,540 --> 00:23:08,070 gañamos a través da introdución dun indiscutibelmente máis estrutura de datos complicado, e un, 546 00:23:08,070 --> 00:23:09,870 francamente, que utiliza unha gran cantidade de memoria. 547 00:23:09,870 --> 00:23:11,703 >> Porque aínda que, no momento, eu só estou 548 00:23:11,703 --> 00:23:15,050 usando punteiro D e A e V e Es e Ns, 549 00:23:15,050 --> 00:23:16,700 Estou perdendo unha peza de moita memoria. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Pero onde eu pasar un recurso, Eu tendo a non gañar de volta outro. 552 00:23:22,660 --> 00:23:26,020 Entón, se eu estou gastan máis espazo, o que é, probablemente, a esperanza? 553 00:23:26,020 --> 00:23:27,407 Que eu estou gastan menos co que? 554 00:23:27,407 --> 00:23:28,240 Audiencia: Menos tempo. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: Equipo. 556 00:23:28,990 --> 00:23:30,320 Agora, por que pode ser iso? 557 00:23:30,320 --> 00:23:33,880 Ben, o que é a inserción tempo, en termos de gran ó momento, 558 00:23:33,880 --> 00:23:37,660 dun nome como Daven ou Davenport ou David? 559 00:23:37,660 --> 00:23:39,340 Ben, Daven era de cinco etapas. 560 00:23:39,340 --> 00:23:42,350 Davenport sería nove etapas, polo que sería máis algúns pasos. 561 00:23:42,350 --> 00:23:44,250 David sería cinco pasos ben. 562 00:23:44,250 --> 00:23:47,230 Polo tanto, estas son de formigón números, pero certamente hai 563 00:23:47,230 --> 00:23:49,550 un límite superior sobre o lonxitude do nome de alguén. 564 00:23:49,550 --> 00:23:52,240 E, de feito, no problema conxuntos de cinco especificación, 565 00:23:52,240 --> 00:23:54,050 imos propoñer que é algo 566 00:23:54,050 --> 00:23:55,470 que é de 40 caracteres e tantos. 567 00:23:55,470 --> 00:23:58,180 >> Realista, ninguén ten un nome infinitamente longo, 568 00:23:58,180 --> 00:24:01,542 o que quere dicir que a lonxitude dun nome ou a lonxitude dunha cadea que pode 569 00:24:01,542 --> 00:24:03,750 estar seguro de que o estado de estrutura é sen dúbida o que? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 É constante. 572 00:24:06,250 --> 00:24:06,430 Non? 573 00:24:06,430 --> 00:24:09,310 Pode ser unha gran constante como 40 e poucos anos, pero é constante. 574 00:24:09,310 --> 00:24:13,752 E iso non ten ningunha dependencia de cantos outros nomes están nesta estrutura de datos. 575 00:24:13,752 --> 00:24:15,460 Noutras palabras, se I quería agora introducir 576 00:24:15,460 --> 00:24:20,540 Colton ou Gabriel ou Rob ou Zamyla ou Alison ou Belinda ou outros nomes 577 00:24:20,540 --> 00:24:23,940 do equipo en datos estrutura, é o tempo de execución 578 00:24:23,940 --> 00:24:26,750 de introducir outros nomes será en todo impactaram 579 00:24:26,750 --> 00:24:30,220 pola forma como moitos outros elementos son na estrutura de datos xa? 580 00:24:30,220 --> 00:24:31,040 Non é. 581 00:24:31,040 --> 00:24:31,540 Non? 582 00:24:31,540 --> 00:24:36,150 Porque nós estamos efectivamente usando esta táboa hash de multi-capa. 583 00:24:36,150 --> 00:24:38,280 E o tempo de execución de calquera destas operacións 584 00:24:38,280 --> 00:24:41,510 non é dependente do número de elementos que se atopan na estrutura de datos 585 00:24:41,510 --> 00:24:43,090 ou que son, finalmente, indo estar na estrutura de datos, 586 00:24:43,090 --> 00:24:44,714 pero na lonxitude do que especificamente? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> A secuencia de estar inserida, o que fai 589 00:24:49,200 --> 00:24:52,580 este asintótica constante tempo-- gran O dun. 590 00:24:52,580 --> 00:24:54,720 E, francamente, só en o mundo real, este 591 00:24:54,720 --> 00:24:58,380 significa introducir o nome de Daven leva como cinco etapas, ou Davenport nove 592 00:24:58,380 --> 00:25:00,100 etapas, ou David cinco etapas. 593 00:25:00,100 --> 00:25:03,071 Isto é moi danado pequenos tempos de execución. 594 00:25:03,071 --> 00:25:05,320 E, de feito, iso é moi O bo, especialmente cando 595 00:25:05,320 --> 00:25:08,126 non é dependente do total número de elementos de alí. 596 00:25:08,126 --> 00:25:10,500 Entón, como podemos aplicar esta tipo de estrutura en código? 597 00:25:10,500 --> 00:25:12,900 É un pouco máis complexo, senón que é 598 00:25:12,900 --> 00:25:15,050 só unha aplicación de bloques de construción básicos. 599 00:25:15,050 --> 00:25:17,830 Eu estou indo a axustar nos nó como segue: 600 00:25:17,830 --> 00:25:21,100 booleano chamado word-- e esta podería chamarse de calquera cousa. 601 00:25:21,100 --> 00:25:23,970 Pero o representa booleano o que eu deseño como unha marca de verificación. 602 00:25:23,970 --> 00:25:24,490 Si. 603 00:25:24,490 --> 00:25:26,720 Esta é o extremo dunha corda nesta estrutura de datos. 604 00:25:26,720 --> 00:25:30,702 >> E, por suposto, a estrela nodo non está referíndose a nenos. 605 00:25:30,702 --> 00:25:32,410 E, de feito, así como unha árbore de familia, ten 606 00:25:32,410 --> 00:25:34,370 consideraría os nós que son colgado 607 00:25:34,370 --> 00:25:36,920 da parte inferior de algúns dos pais elemento a ser nenos. 608 00:25:36,920 --> 00:25:40,510 E así os nenos vai ser unha matriz de 27, a unha 27th 609 00:25:40,510 --> 00:25:41,680 sendo só para apóstrofo. 610 00:25:41,680 --> 00:25:43,390 Estamos indo para clasificar de caso especial que. 611 00:25:43,390 --> 00:25:45,400 Entón pode que seguro nomes con apóstrofo. 612 00:25:45,400 --> 00:25:47,399 Quizais ata guión debe vaia alí, pero 613 00:25:47,399 --> 00:25:50,330 ver xuntos p 5 só coidado sobre letras e apóstrofos. 614 00:25:50,330 --> 00:25:52,990 >> E entón como é que representa a propia estrutura de datos? 615 00:25:52,990 --> 00:25:56,454 Como representar a raíz desta trie, por así dicir? 616 00:25:56,454 --> 00:25:59,620 Ben, así como cunha lista ligada, ten precisa dun punteiro para o primeiro elemento. 617 00:25:59,620 --> 00:26:04,270 Cunha trie só precisa dun punteiro para a raíz desta trie. 618 00:26:04,270 --> 00:26:07,290 E a partir de aí pode botar o seu camiño cada vez máis fondo 619 00:26:07,290 --> 00:26:10,460 para todos os outros nós na estrutura. 620 00:26:10,460 --> 00:26:13,440 Entón simplemente con esta lata representamos que struct. 621 00:26:13,440 --> 00:26:15,877 >> Agora Meanwhile-- Oh, pregunta. 622 00:26:15,877 --> 00:26:17,220 >> Audiencia: Cal é palabra bool? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: palabra bool é só nesta encarnación C 624 00:26:20,490 --> 00:26:22,920 do que eu describín nesa caixa aquí, cando 625 00:26:22,920 --> 00:26:26,000 Comecei dividindo cada un dos elementos en dúas pezas da matriz. 626 00:26:26,000 --> 00:26:27,600 Un deles é un punteiro ao seguinte nodo. 627 00:26:27,600 --> 00:26:30,280 A outra ten que ser algo así como unha caixa de verificación 628 00:26:30,280 --> 00:26:33,770 dicir que si, hai unha Daven palabra que termina aquí, 629 00:26:33,770 --> 00:26:35,610 porque non queremos, no momento, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Aínda que Dave será un palabra lexítima, non está no trie 631 00:26:39,320 --> 00:26:39,830 Aínda. 632 00:26:39,830 --> 00:26:40,950 E D non é unha palabra. 633 00:26:40,950 --> 00:26:42,770 E D-A non é unha palabra ou un nome. 634 00:26:42,770 --> 00:26:45,020 Así, a marca de verificación indica só unha vez 635 00:26:45,020 --> 00:26:48,190 acadar este nodo é o traxectoria anterior de personaxes 636 00:26:48,190 --> 00:26:50,700 en realidade, unha secuencia de carácteres que inseriu. 637 00:26:50,700 --> 00:26:53,660 Entón, iso é todo o bool non está facendo por nós. 638 00:26:53,660 --> 00:26:55,500 >> Calquera outras preguntas sobre intentos? 639 00:26:55,500 --> 00:26:56,215 Si. 640 00:26:56,215 --> 00:26:58,035 >> Audiencia: Cal é a superposición? 641 00:26:58,035 --> 00:26:59,945 E se ten un Dave e un Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID Malan: Perfecto. 643 00:27:00,820 --> 00:27:02,580 E se ten un Dave e un Daven? 644 00:27:02,580 --> 00:27:06,240 Entón, se nós inserimos, digamos, un apelido, para David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Esta é realmente super sinxelo. 647 00:27:08,700 --> 00:27:10,325 Entón nós só imos levar catro etapas. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-e. E o que eu teño que facer, xa que eu bati cuarta nodo? 650 00:27:15,847 --> 00:27:16,680 Só tes que ir comprobar. 651 00:27:16,680 --> 00:27:18,000 Xa está preparado para ir. 652 00:27:18,000 --> 00:27:18,840 Feito. 653 00:27:18,840 --> 00:27:19,750 Catro pasos. 654 00:27:19,750 --> 00:27:21,590 Constante de tempo asintótica. 655 00:27:21,590 --> 00:27:26,300 E agora que xa indicaron que tanto Dave e Daven son cadeas na estrutura. 656 00:27:26,300 --> 00:27:27,710 Entón, non é un problema. 657 00:27:27,710 --> 00:27:30,200 E teña en conta como a presenza Daven de non facelo 658 00:27:30,200 --> 00:27:34,750 levar máis tempo ou menos tempo para Dave e viceversa. 659 00:27:34,750 --> 00:27:36,000 >> Entón o que máis podemos facer? 660 00:27:36,000 --> 00:27:40,680 Usamos esta metáfora antes bandexas de representar algo. 661 00:27:40,680 --> 00:27:43,380 Pero parece que a pila de taboleiros é realmente 662 00:27:43,380 --> 00:27:47,187 demostrativo doutro abstracto de datos type-- unha estrutura de datos de nivel superior 663 00:27:47,187 --> 00:27:49,770 que, ao final do día é só como unha matriz ou unha lista ligada 664 00:27:49,770 --> 00:27:50,970 ou algo máis mundano. 665 00:27:50,970 --> 00:27:53,270 Pero é unha máis interesante concepto conceptual. 666 00:27:53,270 --> 00:27:56,440 Unha pila, como estes Bandexas aquí en Mather, 667 00:27:56,440 --> 00:27:58,750 son xeralmente chamados só que-- unha pila. 668 00:27:58,750 --> 00:28:02,540 >> E, neste tipo de estrutura de datos ten dúas operations-- 669 00:28:02,540 --> 00:28:05,880 ten un chamado de impulso para engadindo algo para a pila, 670 00:28:05,880 --> 00:28:08,320 como poñer outra bandexa atrás sobre o cume da pila. 671 00:28:08,320 --> 00:28:11,350 E logo pop, o que significa que tomar o máis alto para fóra da bandexa. 672 00:28:11,350 --> 00:28:16,210 Pero o que é importante sobre unha pila é que el ten esa característica curiosa. 673 00:28:16,210 --> 00:28:19,560 Como o equipo de comedor son rearranjar as bandexas para a próxima comida, 674 00:28:19,560 --> 00:28:21,380 o que vai ser verdade sobre como os alumnos 675 00:28:21,380 --> 00:28:22,856 interactuar con esta estrutura de datos? 676 00:28:22,856 --> 00:28:24,480 Audiencia: Eles están indo estalar un fóra. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: Eles van estalar un fóra, espero que o cumio. 678 00:28:26,550 --> 00:28:28,910 Se non, é só unha especie de estúpida para percorrer todo o camiño ata o fondo. 679 00:28:28,910 --> 00:28:29,070 Non? 680 00:28:29,070 --> 00:28:31,620 A estrutura de datos realmente non permite incorporarse a bandexa inferior, polo menos, 681 00:28:31,620 --> 00:28:32,520 facilmente. 682 00:28:32,520 --> 00:28:35,040 Entón hai ese curioso propiedade dunha pila 683 00:28:35,040 --> 00:28:39,730 que o último elemento é vai ser o primeiro en saír. 684 00:28:39,730 --> 00:28:43,400 E os científicos da computación chaman este LIFO-- último a entrar, primeiro en saír. 685 00:28:43,400 --> 00:28:45,540 E realmente ten aplicacións interesantes. 686 00:28:45,540 --> 00:28:50,090 Non é necesariamente tan obvio como algúns outros, pero pode, de feito, ser útil, 687 00:28:50,090 --> 00:28:54,040 e pode, de feito, ser aplicado nun par de formas diferentes. 688 00:28:54,040 --> 00:28:58,550 >> Entón, un, e de feito, imos me para mergullo niso. 689 00:28:58,550 --> 00:28:59,860 Imos facelo no seu lugar. 690 00:28:59,860 --> 00:29:03,700 Imos ollar un que é case o mesma idea, pero é un pouco máis xusto. 691 00:29:03,700 --> 00:29:04,200 Non? 692 00:29:04,200 --> 00:29:07,560 Se vostede é un destes nenos fans ou nenas que realmente lle gusta de produtos de Apple 693 00:29:07,560 --> 00:29:10,130 e espertou ás 3h00 para aliñar nalgunha tenda 694 00:29:10,130 --> 00:29:14,150 para obter a última iPhone, vostede podería cola coma este. 695 00:29:14,150 --> 00:29:15,800 >> Agora a cola é moi deliberadamente nomeado. 696 00:29:15,800 --> 00:29:18,190 É unha liña porque non hai algunha xustiza a el. 697 00:29:18,190 --> 00:29:18,690 Non? 698 00:29:18,690 --> 00:29:21,690 Sería unha especie de sugado se ten chegou primeiro na Apple Store 699 00:29:21,690 --> 00:29:25,700 pero é efectivamente o bottommost bandexa porque os empregados de Apple, a continuación, 700 00:29:25,700 --> 00:29:28,189 estalar a última persoa que realmente ten na liña. 701 00:29:28,189 --> 00:29:31,230 Entón, pilas e colas, aínda funcionalmente son tipo do same-- 702 00:29:31,230 --> 00:29:33,105 é só esta colección de recursos que é 703 00:29:33,105 --> 00:29:36,210 vai medrar e shrink-- existe este aspecto xustiza a el, 704 00:29:36,210 --> 00:29:39,634 polo menos, no mundo real, onde as operacións se exercita 705 00:29:39,634 --> 00:29:40,800 son fundamentalmente diferentes. 706 00:29:40,800 --> 00:29:43,360 Un stack-- unha fila rather-- dise ter 707 00:29:43,360 --> 00:29:45,320 dúas operacións: cola de n e d fila. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Ou pode chamalos unha serie de cousas. 710 00:29:48,090 --> 00:29:50,770 Pero só quere capturar a noción de que unha é a suma de 711 00:29:50,770 --> 00:29:53,230 e unha definitiva, é subtraindo. 712 00:29:53,230 --> 00:29:58,840 >> Agora baixo o capó, tanto a pila e unha cola podería ser aplicado como? 713 00:29:58,840 --> 00:30:01,390 Non imos entrar no código de xa que o nivel máis elevado 714 00:30:01,390 --> 00:30:03,387 idea é unha especie de máis evidente. 715 00:30:03,387 --> 00:30:04,470 Quero dicir, o que os humanos fan? 716 00:30:04,470 --> 00:30:07,030 Se eu son a primeira persoa en Apple Almacenar e esta é a porta de entrada, 717 00:30:07,030 --> 00:30:08,130 vostede sabe, eu vou estar aquí. 718 00:30:08,130 --> 00:30:09,750 E a seguinte persoa se ve aquí. 719 00:30:09,750 --> 00:30:11,500 E a seguinte persoa se ve aquí. 720 00:30:11,500 --> 00:30:13,792 Entón, o que estrutura de datos préstase a unha fila? 721 00:30:13,792 --> 00:30:14,542 >> Audiencia: A cola. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: Ben, unha cola. 723 00:30:15,667 --> 00:30:16,390 Claro. 724 00:30:16,390 --> 00:30:16,920 Que máis? 725 00:30:16,920 --> 00:30:17,600 >> Audiencia: Unha lista ligada. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: un conectado lista que podería aplicar. 727 00:30:18,990 --> 00:30:22,500 E unha lista ligada é bo porque despois pode crecer arbitrariamente longa en oposición 728 00:30:22,500 --> 00:30:24,880 para ter un número fixo de persoas na tenda. 729 00:30:24,880 --> 00:30:27,030 Pero quizais un número fixo de prazas é lexítimo. 730 00:30:27,030 --> 00:30:30,350 Porque se eles só teñen como 20 iPhones o primeiro día, quizais 731 00:30:30,350 --> 00:30:33,930 eles só precisan dunha matriz de tamaño 20 para representar esa cola, que 732 00:30:33,930 --> 00:30:37,070 é só para dicir agora, xa que comezar a falar sobre estes problemas de nivel superior, 733 00:30:37,070 --> 00:30:38,890 pode implementar lo en calquera número de formas. 734 00:30:38,890 --> 00:30:42,030 E non hai, probablemente, só vai ser un trade off no espazo e no tempo 735 00:30:42,030 --> 00:30:43,950 ou só na súa propia complexidade do código. 736 00:30:43,950 --> 00:30:45,380 >> Que tal unha pila? 737 00:30:45,380 --> 00:30:48,190 Ben, unha pila, vimos tamén podería ser só estas bandexas. 738 00:30:48,190 --> 00:30:50,007 E podería aplicar esta unha matriz. 739 00:30:50,007 --> 00:30:53,090 Pero nalgún momento, se usa unha matriz, o que vai pasar coas bandexas 740 00:30:53,090 --> 00:30:54,173 estás a poñer para abaixo? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Todo correcto. 743 00:30:55,670 --> 00:30:57,490 Só vai poder ir tan alto. 744 00:30:57,490 --> 00:31:00,156 E eu creo que están en Mather de feito, en que a apertura do receso. 745 00:31:00,156 --> 00:31:01,950 Entón, en realidade, é case como Mather está a usar 746 00:31:01,950 --> 00:31:03,783 unha matriz de tamaño fixo, porque só pode 747 00:31:03,783 --> 00:31:08,302 caber tantas bandexas en que a apertura de a parede abaixo xeonllos das persoas. 748 00:31:08,302 --> 00:31:10,010 E, de xeito que se pode Dise que unha matriz, 749 00:31:10,010 --> 00:31:14,300 pero nós certamente podería aplicar esta de modo máis xeral, con unha lista ligada. 750 00:31:14,300 --> 00:31:16,390 >> Ben, o que dicir de outra estrutura de datos? 751 00:31:16,390 --> 00:31:18,760 Déixeme puxar arriba outro visuais aquí. 752 00:31:18,760 --> 00:31:24,710 Algo así como que tal esta aquí? 753 00:31:24,710 --> 00:31:28,920 Por que pode ser útil para non ter algo tan extravagante como unha trie, que 754 00:31:28,920 --> 00:31:32,370 vimos que tiña eses nós moi anchas, cada un dos cales está nunha matriz? 755 00:31:32,370 --> 00:31:35,740 Pero o que se facer algo máis simplemente, como unha árbore xenealóxica da vella escola, 756 00:31:35,740 --> 00:31:38,110 cada un de cuxos nós aquí é só almacenar un número. 757 00:31:38,110 --> 00:31:42,180 En vez de un nome ou un descendente é só almacenar un número como esta. 758 00:31:42,180 --> 00:31:45,250 >> Ben, o argot que usan en estruturas de datos é dous intentos 759 00:31:45,250 --> 00:31:49,510 e árbores, onde unha trie, de novo, é só unha cuxos nós son matrices, 760 00:31:49,510 --> 00:31:51,680 aínda é o que se pode usar da escola de clase 761 00:31:51,680 --> 00:31:53,860 cando fixo unha familia tree-- follas ea raíz 762 00:31:53,860 --> 00:31:57,250 da árbore e nenos do pais e irmáns dos mesmos. 763 00:31:57,250 --> 00:32:03,670 E poderiamos aplicar unha árbore, por exemplo, como simplemente como este. 764 00:32:03,670 --> 00:32:07,420 Unha árbore, coma se un nó, un dos estes círculos que contén un número, 765 00:32:07,420 --> 00:32:09,947 non vai ter un punteiro, pero dúas. 766 00:32:09,947 --> 00:32:11,780 E así que engadir un segundo punteiro, ten 767 00:32:11,780 --> 00:32:13,905 agora pode realmente facer tipo de datos bidimensional 768 00:32:13,905 --> 00:32:14,780 estruturas en memoria. 769 00:32:14,780 --> 00:32:16,660 Moi parecido un bidimensional array, pode 770 00:32:16,660 --> 00:32:18,904 ter tipo de bidimensional listas ligadas, pero os 771 00:32:18,904 --> 00:32:20,820 que seguen un patrón onde non hai ciclos. 772 00:32:20,820 --> 00:32:24,487 É verdadeiramente unha árbore cunha xeito avó aquí e despois para arriba 773 00:32:24,487 --> 00:32:27,320 algúns pais e fillos e netos e bisnetos. 774 00:32:27,320 --> 00:32:28,370 e así por diante. 775 00:32:28,370 --> 00:32:32,390 >> Pero o que é realmente interesante sobre iso tamén, só para provoca-lo con algo de código, 776 00:32:32,390 --> 00:32:35,370 recordo de recursão algún tempo, no que 777 00:32:35,370 --> 00:32:38,220 escribir unha función que chama a si mesmo. 778 00:32:38,220 --> 00:32:41,140 Esta é unha fermosa oportunidade para aplicar algo 779 00:32:41,140 --> 00:32:42,920 como recursão, porque considerar isto. 780 00:32:42,920 --> 00:32:43,860 >> Esta é unha árbore. 781 00:32:43,860 --> 00:32:48,040 E eu teño sido un pouco anal coa forma como Engada os números enteiros para a rúa. 782 00:32:48,040 --> 00:32:51,020 Tanto é así que ten unha especial nome-- unha árbore de busca binaria. 783 00:32:51,020 --> 00:32:53,460 Agora nós xa escoitou falar de binario buscar, pero pode 784 00:32:53,460 --> 00:32:55,180 traballar cara atrás desde o nome desta cousa? 785 00:32:55,180 --> 00:32:59,280 Cal é o estándar de como eu inseridos os números enteiros para esta árbore? 786 00:32:59,280 --> 00:33:00,696 Non é arbitraria. 787 00:33:00,696 --> 00:33:01,570 Hai algún defecto. 788 00:33:01,570 --> 00:33:02,090 Si. 789 00:33:02,090 --> 00:33:03,370 >> Audiencia: Os menores de esquerda. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Malan: Yeah. 791 00:33:03,690 --> 00:33:05,062 Os menores están á esquerda. 792 00:33:05,062 --> 00:33:06,270 As maiores son na dereita. 793 00:33:06,270 --> 00:33:12,940 De tal forma que unha afirmación verdadeira é unha pai é maior que o seu fillo esquerdo, 794 00:33:12,940 --> 00:33:14,850 pero menos que o seu fillo dereito. 795 00:33:14,850 --> 00:33:17,750 E só iso é mesmo un definición verbal recursiva 796 00:33:17,750 --> 00:33:20,500 porque pode aplicar ese mesma lóxica para cada nodo 797 00:33:20,500 --> 00:33:23,080 E só Bottoms a fóra, un caso base, se 798 00:33:23,080 --> 00:33:25,740 ganas, cando bate un dos as follas, por así dicir, 799 00:33:25,740 --> 00:33:28,580 onde unha licenza non ten fillos aínda. 800 00:33:28,580 --> 00:33:30,614 >> Agora, como pode atopar o número 44? 801 00:33:30,614 --> 00:33:32,280 Podería comezar na raíz e dicir, hm. 802 00:33:32,280 --> 00:33:35,690 55 non é 44 Entón eu quero ir dereito ou quero ir á esquerda? 803 00:33:35,690 --> 00:33:37,190 Ben, obviamente quere ir esquerdo. 804 00:33:37,190 --> 00:33:40,060 E así é como o teléfono exemplo libro en busca binaria 805 00:33:40,060 --> 00:33:41,099 de modo máis xeral. 806 00:33:41,099 --> 00:33:43,390 Pero estamos implementar lo agora un pouco máis dinámica 807 00:33:43,390 --> 00:33:45,339 que unha matriz pode permitir. 808 00:33:45,339 --> 00:33:48,130 E, de feito, se quere ollar no código, a primeira vista, con certeza. 809 00:33:48,130 --> 00:33:49,671 Parece que unha morea de liñas. 810 00:33:49,671 --> 00:33:51,220 Pero é ben sinxelo. 811 00:33:51,220 --> 00:33:54,490 Se quere aplicar unha función chamada investigación cuxo propósito na vida 812 00:33:54,490 --> 00:33:57,290 é a procura dun valor como n, un enteiro, 813 00:33:57,290 --> 00:34:01,756 e que pasou nun pointer-- un enlace para o no das raíces, 814 00:34:01,756 --> 00:34:04,380 ao contrario, de que árbore da cal podes acceder todo o máis, 815 00:34:04,380 --> 00:34:08,850 observe como directamente pode aplicar a lóxica. 816 00:34:08,850 --> 00:34:10,880 Se árbore é nulo, obviamente non está alí. 817 00:34:10,880 --> 00:34:11,880 Nós só retornar falso. 818 00:34:11,880 --> 00:34:12,000 Non? 819 00:34:12,000 --> 00:34:14,040 Se entrega-lo nada, non hai nada alí. 820 00:34:14,040 --> 00:34:17,900 >> Logo, se n é inferior a árbore frecha n-- agora arrow n, 821 00:34:17,900 --> 00:34:20,670 lembrar que introducimos Super brevemente o outro día, 822 00:34:20,670 --> 00:34:25,100 e que só significa de-referencia a punteiro e ollar para o campo chamado n. 823 00:34:25,100 --> 00:34:27,690 Entón isto significa ir alí e ollar para o campo chamado n. 824 00:34:27,690 --> 00:34:33,810 Entón, se n, o valor que se recibe, é menos en que o valor do enteiro árbores, 825 00:34:33,810 --> 00:34:35,449 onde quere ir? 826 00:34:35,449 --> 00:34:36,389 Á esquerda. 827 00:34:36,389 --> 00:34:37,780 >> Entón, observe a recursividade. 828 00:34:37,780 --> 00:34:39,860 Estou returning-- non é verdade. 829 00:34:39,860 --> 00:34:40,989 Non falsa. 830 00:34:40,989 --> 00:34:45,670 Estou volvendo calquera que sexa a resposta é a partir dunha chamada para min, pasando 831 00:34:45,670 --> 00:34:50,100 un n de novo, o que é redundante, pero o que é un pouco diferente agora? 832 00:34:50,100 --> 00:34:51,989 Como eu estou facendo o problema menor? 833 00:34:51,989 --> 00:34:54,920 Estou pasando como a segunda argumento, non a raíz da árbore, 834 00:34:54,920 --> 00:34:59,616 pero o fillo esquerdo neste caso. 835 00:34:59,616 --> 00:35:00,990 Entón, eu estou pasando o fillo esquerdo. 836 00:35:00,990 --> 00:35:04,720 >> Por outra banda, se n é maior que o no Actualmente estou mirando, 837 00:35:04,720 --> 00:35:06,690 Eu busco o lado dereito. 838 00:35:06,690 --> 00:35:10,880 Outra cousa, se a árbore non é nulo, e Se o elemento non está á esquerda 839 00:35:10,880 --> 00:35:13,240 e non é a dereita, o que é marabillosas o caso? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Nós realmente atopamos o no en pregunta, e así volvemos verdade. 842 00:35:18,440 --> 00:35:21,490 >> Entón, nós só arranhamos a superficie agora algunhas destas estruturas de datos. 843 00:35:21,490 --> 00:35:24,370 No conxunto de problemas de cinco vai explotar estes aínda máis lonxe, 844 00:35:24,370 --> 00:35:27,250 e será dado o seu proxecto elección como ir sobre iso. 845 00:35:27,250 --> 00:35:30,250 O que me gustaría terminar sobre é só un segundo teaser 30 846 00:35:30,250 --> 00:35:32,080 do que nos espera a próxima semana e alén. 847 00:35:32,080 --> 00:35:35,390 >> Como nós begin-- sorte podes penso-- nosa transición lenta 848 00:35:35,390 --> 00:35:38,680 do mundo da C e menor detalles de implementación nivel, 849 00:35:38,680 --> 00:35:42,090 a un mundo no que podemos tomar para seguro que alguén ten, finalmente, 850 00:35:42,090 --> 00:35:44,010 aplicado estes datos estruturas para nós, 851 00:35:44,010 --> 00:35:47,570 e imos comezar a entender o mundo real significa de implantación 852 00:35:47,570 --> 00:35:50,560 programas baseados na web e sitios máis xeralmente 853 00:35:50,560 --> 00:35:52,910 e tamén a propia seguridade implicacións que nós só 854 00:35:52,910 --> 00:35:54,850 comezaron a rabuñar a superficie do. 855 00:35:54,850 --> 00:35:57,320 Aquí está o que nos espera os días que virán. 856 00:35:57,320 --> 00:36:00,480 >> [REPRODUCIÓN DE VIDEO] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -El Veu cunha mensaxe, cun protocolo de todos os seus propios. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 El veu para un mundo de cruel firewalls, routers indiferente, 861 00:36:30,894 --> 00:36:33,368 e perigos moito peores que a morte. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 El é rápido. 864 00:36:36,236 --> 00:36:37,980 El é forte. 865 00:36:37,980 --> 00:36:42,830 El é o TCP / IP, e el ten o seu enderezo. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Guerreiros da rede." 868 00:36:48,074 --> 00:36:49,660 [FIN REPRODUCIÓN DE VIDEO] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: Na próxima semana. 870 00:36:50,910 --> 00:36:51,880 Imos velo axiña. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [REPRODUCIÓN DE VIDEO] 873 00:36:56,060 --> 00:36:59,240 -E Agora, "Pensamentos Profundos" por Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Comeza sempre conferencias con: "Todo ben." 876 00:37:05,820 --> 00:37:08,750 Por que non, "Aquí está a solución ao conxunto de problemas esta semana " 877 00:37:08,750 --> 00:37:12,180 ou "Estamos dando a todos vostedes un A?" 878 00:37:12,180 --> 00:37:13,380 [Risas] 879 00:37:13,380 --> 00:37:15,530 [FIN REPRODUCIÓN DE VIDEO]