1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> COLUMNA 1: Todo ben, entón estamos de volta. 3 00:00:13,120 --> 00:00:14,480 Benvido ao CS50. 4 00:00:14,480 --> 00:00:16,510 Isto é o fin de semana sete. 5 00:00:16,510 --> 00:00:20,200 Entón, lembro que a última vez, comezan buscando un pouco máis sofisticado 6 00:00:20,200 --> 00:00:21,100 estruturas de datos. 7 00:00:21,100 --> 00:00:25,110 Xa que, ata agora, todo o que tiña de verdade á nosa disposición era iso, un array. 8 00:00:25,110 --> 00:00:29,340 >> Pero, antes de descartar a matriz como non todo o que interesante, o que de feito 9 00:00:29,340 --> 00:00:33,570 realmente é, o que son algunhas das vantaxes destes datos sinxela 10 00:00:33,570 --> 00:00:34,560 estrutura ata agora? 11 00:00:34,560 --> 00:00:36,110 Que é que é bo? 12 00:00:36,110 --> 00:00:39,450 Ata agora, como vimos? 13 00:00:39,450 --> 00:00:42,540 O que ten? 14 00:00:42,540 --> 00:00:44,028 Nada. 15 00:00:44,028 --> 00:00:45,020 >> Estudante: [inaudível]. 16 00:00:45,020 --> 00:00:45,395 >> COLUMNA 1: ¿Que é iso? 17 00:00:45,395 --> 00:00:46,410 >> Estudante: [inaudível]. 18 00:00:46,410 --> 00:00:47,000 >> COLUMNA 1: tamaño fixo. 19 00:00:47,000 --> 00:00:51,260 Ok, entón por que é tamaño fixo bo entón? 20 00:00:51,260 --> 00:00:53,180 >> Estudante: [inaudível]. 21 00:00:53,180 --> 00:00:56,240 >> COLUMNA 1: OK, polo que é eficiente en a sensación de que pode reservar un 22 00:00:56,240 --> 00:01:00,070 cantidade fixa de espazo, que espero É precisamente tanto 23 00:01:00,070 --> 00:01:01,180 espazo como quere. 24 00:01:01,180 --> 00:01:02,720 Así que podería ser absolutamente unha vantaxe. 25 00:01:02,720 --> 00:01:06,530 >> Cal é o outro lado por un conxunto? 26 00:01:06,530 --> 00:01:07,610 Si? 27 00:01:07,610 --> 00:01:08,750 >> Estudante: [inaudível]. 28 00:01:08,750 --> 00:01:09,550 >> COLUMNA 1: Todo o - sorry? 29 00:01:09,550 --> 00:01:11,270 >> Estudante: [inaudível]. 30 00:01:11,270 --> 00:01:13,620 >> COLUMNA 1: Todas as caixas na memoria ou á beira do outro. 31 00:01:13,620 --> 00:01:15,220 E iso é útil - por que? 32 00:01:15,220 --> 00:01:15,970 Isto é ben verdade. 33 00:01:15,970 --> 00:01:18,611 Pero como podemos explorar tanto verdade? 34 00:01:18,611 --> 00:01:21,500 >> Estudante: [inaudível]. 35 00:01:21,500 --> 00:01:24,490 >> COLUMNA 1: Exactamente, podemos seguir onde todo é só por saber 36 00:01:24,490 --> 00:01:28,560 un enderezo, ou sexa, o enderezo do primeiro byte dese bloque de memoria. 37 00:01:28,560 --> 00:01:30,420 Ou, no caso da cadea, a dirección da primeira 38 00:01:30,420 --> 00:01:31,460 char que cadea. 39 00:01:31,460 --> 00:01:33,330 E a partir de aí, podemos atopar o final da cadea. 40 00:01:33,330 --> 00:01:35,710 Podemos atopar o segundo elemento, o terceiro elemento, e así por diante. 41 00:01:35,710 --> 00:01:38,740 >> E así, a forma elegante de describir que característica é que as matrices darnos 42 00:01:38,740 --> 00:01:40,020 de acceso aleatorio. 43 00:01:40,020 --> 00:01:44,330 Só mediante o corchete notación e un número, pode ir para 44 00:01:44,330 --> 00:01:48,070 un elemento específico da matriz en tempo constante, O gran 45 00:01:48,070 --> 00:01:49,810 dunha, por así dicir. 46 00:01:49,810 --> 00:01:51,080 >> Pero houbo algunhas desvantaxes. 47 00:01:51,080 --> 00:01:53,110 Que unha matriz non facer moi facilmente? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 ¿Que é iso non é bo? 50 00:01:57,170 --> 00:01:58,810 >> Estudante: [inaudível]. 51 00:01:58,810 --> 00:01:59,860 >> COLUMNA 1: ¿Que é iso? 52 00:01:59,860 --> 00:02:00,530 >> Estudante: [inaudível]. 53 00:02:00,530 --> 00:02:01,460 >> COLUMNA 1: Expansión de tamaño. 54 00:02:01,460 --> 00:02:04,800 Así, os inconvenientes da matriz son precisamente o contrario do que o 55 00:02:04,800 --> 00:02:05,540 Upside son. 56 00:02:05,540 --> 00:02:07,610 Entón, unha das desvantaxes é que é un tamaño fixo. 57 00:02:07,610 --> 00:02:09,400 Entón non pode realmente crecer. 58 00:02:09,400 --> 00:02:13,510 Podes recolocar unha porción maior memoria e, a continuación, mover os elementos antigos 59 00:02:13,510 --> 00:02:14,460 na nova matriz. 60 00:02:14,460 --> 00:02:18,060 E, entón, libre da vella matriz, para exemplo, utilizando malloc ou similar 61 00:02:18,060 --> 00:02:21,180 función chamada realloc, que realoca memoria. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, como un aparte, intenta darlle memoria que é ao lado da matriz 63 00:02:25,490 --> 00:02:26,610 que xa ten. 64 00:02:26,610 --> 00:02:28,740 Pero pode cambiar as cousas volta por completo. 65 00:02:28,740 --> 00:02:30,710 Pero, en definitiva, que é caro, non? 66 00:02:30,710 --> 00:02:33,440 Porque se ten un bloque de memoria de deste tamaño, pero o que realmente quere un 67 00:02:33,440 --> 00:02:36,710 deste tamaño, e quere conservar os elementos orixinais, ten 68 00:02:36,710 --> 00:02:40,510 preto dun proceso de copia de tempo lineal que debe pasar desde 69 00:02:40,510 --> 00:02:41,900 array antigo para o novo. 70 00:02:41,900 --> 00:02:44,630 E a realidade está pedindo ao funcionamento sistema novo e de novo e 71 00:02:44,630 --> 00:02:48,340 novo para grandes anacos de memoria pode comezar lle custa moito tempo tamén. 72 00:02:48,340 --> 00:02:52,250 Por iso, é tanto unha bendición e unha maldición en disfrazar o feito de que estas matrices 73 00:02:52,250 --> 00:02:53,860 son de tamaño fixo. 74 00:02:53,860 --> 00:02:56,790 Pero se introducir algo no canto así, o que chamamos un linked 75 00:02:56,790 --> 00:03:00,580 lista, recibimos algúns pros e algunhas desvantaxes aquí tamén. 76 00:03:00,580 --> 00:03:05,780 >> Así, unha lista ligada é simplemente un conxunto de datos estrutura composta de estruturas C neste 77 00:03:05,780 --> 00:03:09,850 caso, onde unha struct, aviso, é só un recipiente para unha ou máis específico 78 00:03:09,850 --> 00:03:11,100 tipos de variables. 79 00:03:11,100 --> 00:03:16,110 Neste caso, o que os tipos de datos parecen estar dentro da estrutura que 80 00:03:16,110 --> 00:03:17,600 última vez que chama nó? 81 00:03:17,600 --> 00:03:19,380 Cada un destes rectángulos é un nó. 82 00:03:19,380 --> 00:03:22,660 E cada un dos rectángulos pequenos dentro do que é un tipo de datos. 83 00:03:22,660 --> 00:03:25,300 Cales son os tipos que dixemos estaban o luns? 84 00:03:25,300 --> 00:03:26,478 Si? 85 00:03:26,478 --> 00:03:27,870 >> Estudante: [inaudível]. 86 00:03:27,870 --> 00:03:30,721 >> COLUMNA 1: A variable e un punteiro, ou máis especificamente, un int, a n, 87 00:03:30,721 --> 00:03:32,180 e un punteiro no fondo. 88 00:03:32,180 --> 00:03:35,360 Tanto dos que ser 32 bits ás menos nun equipo como este CS50 89 00:03:35,360 --> 00:03:37,980 Appliance, e por iso son igualmente deseñada en tamaño. 90 00:03:37,980 --> 00:03:42,260 >> Entón, o que está a usar o punteiro a pesar de parecer? 91 00:03:42,260 --> 00:03:47,690 Por que engadir esta frecha agora, cando as matrices foron tan agradable e limpo e simple? 92 00:03:47,690 --> 00:03:50,460 Qué é o punteiro facendo por nós en cada un destes nodos? 93 00:03:50,460 --> 00:03:52,160 >> Estudante: [inaudível]. 94 00:03:52,160 --> 00:03:52,465 >> COLUMNA 1: Exactamente. 95 00:03:52,465 --> 00:03:54,120 Está dicindo a vostede onde a seguinte é. 96 00:03:54,120 --> 00:03:57,350 Entón eu medio que usar a analoxía de mediante un fío de clasificar de 97 00:03:57,350 --> 00:03:59,180 enfiar eses nós xuntos. 98 00:03:59,180 --> 00:04:01,760 E iso é o que estamos facendo punteiros que cada unha delas 99 00:04:01,760 --> 00:04:06,360 anacos de memoria pode ou non ser contigua, de costas cara atrás 100 00:04:06,360 --> 00:04:09,500 dentro de RAM, xa que cada vez que chamar malloc dicindo, dáme o suficiente 101 00:04:09,500 --> 00:04:12,510 bytes para un novo nodo, que podería estar aquí ou pode ser aquí. 102 00:04:12,510 --> 00:04:13,120 Pode ser aquí. 103 00:04:13,120 --> 00:04:13,730 Pode ser aquí. 104 00:04:13,730 --> 00:04:14,640 Vostede simplemente non sabe. 105 00:04:14,640 --> 00:04:17,880 >> Pero o uso de punteiros en enderezos de os nós, pode uni-las 106 00:04:17,880 --> 00:04:22,370 xuntos de maneira que semella visual como unha lista, aínda que esas cousas son 107 00:04:22,370 --> 00:04:26,770 todos espallados por todo o seu un ou seus dous ou os seus catro gigabytes de memoria RAM 108 00:04:26,770 --> 00:04:28,760 dentro do seu propio ordenador. 109 00:04:28,760 --> 00:04:33,230 >> Entón, o lado negativo, entón, de unha lista ligada é o que? 110 00:04:33,230 --> 00:04:34,670 ¿Que é un prezo que estamos aparentemente pagando? 111 00:04:34,670 --> 00:04:36,010 >> Estudante: [inaudível]. 112 00:04:36,010 --> 00:04:36,920 >> COLUMNA 1: Máis espazo, non? 113 00:04:36,920 --> 00:04:39,340 Temos, neste caso, duplicando a cantidade de espazo, porque nós fomos 114 00:04:39,340 --> 00:04:43,500 desde 32 bits para cada nó, para cada int, agora de 64 bits, porque debemos 115 00:04:43,500 --> 00:04:45,050 manter en torno a un punteiro ben. 116 00:04:45,050 --> 00:04:48,860 Gañou máis eficiencia se o struct é maior que esa cousa sinxela. 117 00:04:48,860 --> 00:04:52,020 Se realmente ten un alumno dentro de que é un par de cordas para 118 00:04:52,020 --> 00:04:55,430 nome e casa, quizais un número de identificación, quizais algúns outros campos completamente. 119 00:04:55,430 --> 00:04:59,000 >> Entón, se ten unha gran estrutura suficiente, quizais o custo do punteiro está 120 00:04:59,000 --> 00:05:00,010 non como un gran negocio. 121 00:05:00,010 --> 00:05:03,570 Isto é un pouco de un caso de esquina no que que estamos almacenando unha simple primitivo como 122 00:05:03,570 --> 00:05:04,760 dentro da lista encadeada. 123 00:05:04,760 --> 00:05:05,790 Pero o punto é o mesmo. 124 00:05:05,790 --> 00:05:08,230 Está definitivamente gastar máis memoria, pero está a recibir 125 00:05:08,230 --> 00:05:08,990 flexibilidade. 126 00:05:08,990 --> 00:05:12,280 Porque agora se eu queira engadir un elemento no inicio da lista, 127 00:05:12,280 --> 00:05:14,340 Teño que reservar un novo nodo. 128 00:05:14,340 --> 00:05:17,180 E eu teño que actualizar os frechas de algunha maneira por só movendo 129 00:05:17,180 --> 00:05:17,980 algúns consellos redor. 130 00:05:17,980 --> 00:05:20,580 >> Se eu queira introducir algo na través da lista, eu non teño a 131 00:05:20,580 --> 00:05:24,410 empurrar todos para o lado como fixemos en pasado semanas cos nosos voluntarios que 132 00:05:24,410 --> 00:05:25,700 representada unha matriz. 133 00:05:25,700 --> 00:05:29,470 Só podo asignar un novo nó e a continuación, pode apuntar as frechas no 134 00:05:29,470 --> 00:05:32,290 diferentes direccións, porque non ten que permanecer no real 135 00:05:32,290 --> 00:05:35,670 memoria dunha liña de verdade como eu deseño aquí na pantalla. 136 00:05:35,670 --> 00:05:38,400 >> E entón, finalmente, se quere inserir algo que, ao final da lista, está 137 00:05:38,400 --> 00:05:39,210 aínda máis fácil. 138 00:05:39,210 --> 00:05:43,320 Esta é unha especie de notación arbitraria, mais punteiro de 34, dar un palpite. 139 00:05:43,320 --> 00:05:46,710 Cal é o valor do seu punteiro máis probable tipo elaborado de como un vello 140 00:05:46,710 --> 00:05:47,700 antena escola alí? 141 00:05:47,700 --> 00:05:48,920 >> Estudante: [inaudível]. 142 00:05:48,920 --> 00:05:49,900 >> COLUMNA 1: É probabelmente nulo. 143 00:05:49,900 --> 00:05:52,710 E, de feito, que é un autor representación do nulo. 144 00:05:52,710 --> 00:05:56,310 E é nulo porque é absolutamente Necesitamos saber onde o fin dun linked 145 00:05:56,310 --> 00:06:00,050 lista é, para continuar a seguir e seguindo e seguindo esas frechas 146 00:06:00,050 --> 00:06:01,170 para un valor de lixo. 147 00:06:01,170 --> 00:06:06,230 Entón nulo pode significar que non hai ningunha máis nós á dereita do número 34, 148 00:06:06,230 --> 00:06:07,200 neste caso. 149 00:06:07,200 --> 00:06:10,270 >> Así, propoñemos que podemos aplicar ese nó no código. 150 00:06:10,270 --> 00:06:12,130 E vimos este tipo de sintaxe antes. 151 00:06:12,130 --> 00:06:15,090 Typedef só define un novo tipo de nos, ofrécenos un sinónimo como 152 00:06:15,090 --> 00:06:17,100 cadea era para char *. 153 00:06:17,100 --> 00:06:21,030 Neste caso, vai dar notación abreviada para que nó struct 154 00:06:21,030 --> 00:06:24,010 pode no canto de só ser escrita como nodo, o que é moito máis limpo. 155 00:06:24,010 --> 00:06:25,360 É moito menos detallada. 156 00:06:25,360 --> 00:06:30,080 >> No interior dun nodo é aparentemente un int chamado n, e, a continuación, un nodo struct * 157 00:06:30,080 --> 00:06:34,670 o que significa exactamente o que queriamos que o frechas que dicir, un punteiro a outra 158 00:06:34,670 --> 00:06:36,940 nodo do mesmo tipo de datos exactos. 159 00:06:36,940 --> 00:06:40,300 E eu propoño que podería aplicar un función de busca coma este, que a 160 00:06:40,300 --> 00:06:41,890 primeira vista pode parecer algo complexo. 161 00:06:41,890 --> 00:06:43,330 Pero imos vela no contexto. 162 00:06:43,330 --> 00:06:45,480 >> Déixeme ir ao aparello aquí. 163 00:06:45,480 --> 00:06:48,460 Déixeme abrir un ficheiro chamado lista de cero punto h. 164 00:06:48,460 --> 00:06:53,950 E iso só contén a definición de nós só vin hai pouco a estes datos 165 00:06:53,950 --> 00:06:55,390 tipo chamado un nó. 166 00:06:55,390 --> 00:06:57,350 Entón poñemos isto nun ficheiro h punto. 167 00:06:57,350 --> 00:07:01,430 >> E como un aparte, aínda que esta programa que está a piques de ver é 168 00:07:01,430 --> 00:07:05,410 non todo o que complexo, é de feito convenio cando se escribe un programa para 169 00:07:05,410 --> 00:07:10,270 poñer as cousas como tipos de datos, para tirar constantes, ás veces, dentro do seu 170 00:07:10,270 --> 00:07:13,210 ficheiro de cabeceira, e non necesariamente en o ficheiro C, por suposto cando o seu 171 00:07:13,210 --> 00:07:17,370 programas quedan maiores e máis grandes, de xeito que sabe onde mirar tanto para 172 00:07:17,370 --> 00:07:20,840 documentación, nalgúns casos, ou ao básico como este, os 173 00:07:20,840 --> 00:07:22,360 definición de calquera tipo. 174 00:07:22,360 --> 00:07:25,680 >> Se eu agora abrir lista de cero punto c, teña en conta algunhas cousas. 175 00:07:25,680 --> 00:07:29,090 Inclúe algúns arquivos de cabeceira, a maioría dos de que nós xa vimos antes. 176 00:07:29,090 --> 00:07:31,980 Inclúe o seu propio ficheiro cabeceira. 177 00:07:31,980 --> 00:07:35,200 >> E como un aparte, por que é o dobre citas aquí, en oposición ao ángulo 178 00:07:35,200 --> 00:07:38,340 soportes na liña que Eu destacou alí? 179 00:07:38,340 --> 00:07:39,180 >> Estudante: [inaudível]. 180 00:07:39,180 --> 00:07:40,460 >> COLUMNA 1: Si iso é un ficheiro local. 181 00:07:40,460 --> 00:07:44,300 Entón, se é un ficheiro local da súa preferencia aquí na liña 15, por exemplo, pode utilizar 182 00:07:44,300 --> 00:07:46,570 as comiñas dobres no canto dos soportes angulares. 183 00:07:46,570 --> 00:07:48,270 >> Now sexa deste tipo interesante. 184 00:07:48,270 --> 00:07:51,830 Repare que eu teño declarado mundial variable neste programa na liña 18 185 00:07:51,830 --> 00:07:55,910 chamado por primeira vez, a idea é esta é Será un punteiro para o primeiro 186 00:07:55,910 --> 00:07:59,190 nó na miña lista ligada, e eu teño inicializar a nulo, porque eu teño 187 00:07:59,190 --> 00:08:02,310 non asignado calquera real nós aínda. 188 00:08:02,310 --> 00:08:07,570 >> Entón, iso representa, pictoricamente, o que vin hai pouco na imaxe como 189 00:08:07,570 --> 00:08:10,090 ese punteiro na esquina Lado esquerdo. 190 00:08:10,090 --> 00:08:12,260 Entón, agora, que o punteiro non ten unha frecha. 191 00:08:12,260 --> 00:08:14,590 É ao contrario, é simplemente nulo. 192 00:08:14,590 --> 00:08:17,880 Pero el representa o que será o enderezo da primeira real 193 00:08:17,880 --> 00:08:19,480 nodo da lista. 194 00:08:19,480 --> 00:08:22,120 Entón, eu teño aplicado é unha compañía global porque, como verás, todo iso 195 00:08:22,120 --> 00:08:25,310 programa fai na vida é aplicar unha lista ligada para min. 196 00:08:25,310 --> 00:08:27,050 >> Agora eu teño algúns prototipos aquí. 197 00:08:27,050 --> 00:08:31,190 Decidín aplicar recursos como eliminación, inserción, investigación e 198 00:08:31,190 --> 00:08:31,740 travesía - 199 00:08:31,740 --> 00:08:35,210 o último sendo só atravesar a lista, imprimir os seus elementos. 200 00:08:35,210 --> 00:08:36,750 E agora aquí está a miña rutina de inicio. 201 00:08:36,750 --> 00:08:39,890 E non imos gastar moito tempo en estes xa que esta é unha especie de, esperemos 202 00:08:39,890 --> 00:08:41,780 sombreiro vello agora. 203 00:08:41,780 --> 00:08:45,370 >> Vou facer o seguinte, mentres que o usuario coopera. 204 00:08:45,370 --> 00:08:47,300 Entón, eu estou indo para imprimir este menú. 205 00:08:47,300 --> 00:08:49,420 E eu xa formatado como limpa que puiden. 206 00:08:49,420 --> 00:08:52,240 Se o usuario escribe en un, o que significa queren borrar algo. 207 00:08:52,240 --> 00:08:54,560 Se o usuario escribe en dous, o que significa queren introducir algo. 208 00:08:54,560 --> 00:08:55,930 E así sucesivamente. 209 00:08:55,930 --> 00:08:58,270 Vou entón pedir seguida por un comando. 210 00:08:58,270 --> 00:08:59,300 E entón eu vou usar GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Polo tanto, este é un menuing moi sinxelo interface onde só precisa escribir 212 00:09:02,790 --> 00:09:05,270 un mapeamento a un número destes comandos. 213 00:09:05,270 --> 00:09:08,730 E agora eu teño unha chave limpa agradable declaración de que vai conectar 214 00:09:08,730 --> 00:09:10,090 o que o usuario inseriu dentro 215 00:09:10,090 --> 00:09:12,180 E se inseriu un, eu vou chamar borrar e romper. 216 00:09:12,180 --> 00:09:14,380 Se ingresaran dous, eu vou chamar introducir e romper. 217 00:09:14,380 --> 00:09:16,490 >> E agora repare que engada cada destes na mesma liña. 218 00:09:16,490 --> 00:09:18,360 Esta é só unha decisión estilística. 219 00:09:18,360 --> 00:09:20,210 Normalmente, vimos algo como esta. 220 00:09:20,210 --> 00:09:23,260 Pero eu decidimos, francamente, o meu programa parecía máis lexible por 221 00:09:23,260 --> 00:09:25,980 tiña só catro casos para só lista-la así. 222 00:09:25,980 --> 00:09:28,360 Uso totalmente lexítimo do estilo. 223 00:09:28,360 --> 00:09:31,480 E eu vou facelo, sempre que o usuario non teña ingresaran cero, o que me 224 00:09:31,480 --> 00:09:33,910 decidiu significará que queren deixar de fumar. 225 00:09:33,910 --> 00:09:36,630 >> Entón agora entender o que estou imos facer aquí. 226 00:09:36,630 --> 00:09:38,650 Vou liberar a lista aparentemente. 227 00:09:38,650 --> 00:09:40,230 Pero máis sobre iso aquí a pouco. 228 00:09:40,230 --> 00:09:41,640 Imos primeiro executar este programa. 229 00:09:41,640 --> 00:09:45,250 Entón deixe-me facer unha terminal máis grande fiestra, punto barra lista 0. 230 00:09:45,250 --> 00:09:49,510 Eu estou indo a ir adiante e poña por dato dous, un número similar de 50, e agora 231 00:09:49,510 --> 00:09:51,590 Vostede verá a lista é agora 50. 232 00:09:51,590 --> 00:09:53,380 E o meu texto só rolou para arriba un pouco. 233 00:09:53,380 --> 00:09:55,940 Entón agora teña en conta a lista contén o número 50. 234 00:09:55,940 --> 00:09:58,220 >> Imos facer outra inserción, tomando dous. 235 00:09:58,220 --> 00:10:01,630 Imos escribir o número como un. 236 00:10:01,630 --> 00:10:03,940 Lista é agora un, seguido por 50. 237 00:10:03,940 --> 00:10:06,020 Polo tanto, esta é só unha representación textual da lista. 238 00:10:06,020 --> 00:10:10,550 E imos introducir un número como o número 42, que é esperanza 239 00:10:10,550 --> 00:10:14,620 vai acabar no medio porque este programa en particular tipo que 240 00:10:14,620 --> 00:10:16,320 elementos, xa que os insere. 241 00:10:16,320 --> 00:10:17,220 Polo tanto, non temos. 242 00:10:17,220 --> 00:10:20,730 Super programa sinxelo que podería absolutamente usar un array, pero eu 243 00:10:20,730 --> 00:10:23,280 ocorrer de estar a usar unha lista encadeada só así podo dinámica 244 00:10:23,280 --> 00:10:24,610 crecer e reduci-lo. 245 00:10:24,610 --> 00:10:28,470 >> Entón, imos dar un ollo para a investigación, se eu mando de tres executar, quero buscar 246 00:10:28,470 --> 00:10:31,040 para, por exemplo, o número 43. 247 00:10:31,040 --> 00:10:34,190 E nada se atopou, ao parecer, porque volvín sen resposta. 248 00:10:34,190 --> 00:10:35,010 Entón, imos facelo de novo. 249 00:10:35,010 --> 00:10:35,690 Buscar. 250 00:10:35,690 --> 00:10:39,520 Imos buscar a 50, ou mellor, procurar a 42, que ten unha fermosa 251 00:10:39,520 --> 00:10:40,850 pouco significado sutil. 252 00:10:40,850 --> 00:10:42,610 E descubrín o significado da vida alí. 253 00:10:42,610 --> 00:10:44,990 Número 42, se non sabe a referencia en Google. 254 00:10:44,990 --> 00:10:45,350 Todo ben. 255 00:10:45,350 --> 00:10:47,130 Entón, o que este programa fixo por min? 256 00:10:47,130 --> 00:10:50,660 É só me permitiu introducir así lonxe e busca de elementos. 257 00:10:50,660 --> 00:10:53,650 >> Imos avanzar, entón, para que a función que mirou 258 00:10:53,650 --> 00:10:55,360 o luns como un teaser. 259 00:10:55,360 --> 00:10:59,620 Entón esa función, eu afirmo, as investigacións para un elemento na lista por primeira 260 00:10:59,620 --> 00:11:03,830 un, alertando o usuario e, a continuación, chamar GetInt para obter un int real 261 00:11:03,830 --> 00:11:05,060 que quere buscar. 262 00:11:05,060 --> 00:11:06,460 >> Entón observe iso. 263 00:11:06,460 --> 00:11:10,690 Eu estou indo para crear unha variable temporal na liña 188 chamado punteiro - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 podería telo chamado calquera cousa. 266 00:11:12,440 --> 00:11:16,140 E é un punteiro para un nó por que eu dixen no * alí. 267 00:11:16,140 --> 00:11:19,900 E estou inicializar a ser igual primeiro, para que eu efectivamente teño o meu 268 00:11:19,900 --> 00:11:22,860 dedo, por así dicir, no mesmo primeiro elemento da lista. 269 00:11:22,860 --> 00:11:27,460 Entón, se a miña man dereita aquí é PTR eu son apuntando para o mesmo que o primeiro 270 00:11:27,460 --> 00:11:28,670 está a apuntar. 271 00:11:28,670 --> 00:11:31,430 >> Entón, agora de volta o código, o que pasa a continuación - 272 00:11:31,430 --> 00:11:35,070 este é un paradigma común cando a iteración ao longo dunha estrutura como unha 273 00:11:35,070 --> 00:11:35,970 lista ligada. 274 00:11:35,970 --> 00:11:40,410 Vou facer o seguinte, mentres punteiro non é igual a null Así, mentres 275 00:11:40,410 --> 00:11:47,530 meu dedo non está apuntado nalgún nulo valor, se punteiro de frecha n é igual a n. 276 00:11:47,530 --> 00:11:52,290 Imos observar primeiro que non é o que o usuario inseriu por GetInts chamar aquí. 277 00:11:52,290 --> 00:11:54,280 >> E punteiro de frecha n significa o que? 278 00:11:54,280 --> 00:11:59,020 Ben, se nós voltar a imaxe aquí, se eu tivera un dedo apuntando para 279 00:11:59,020 --> 00:12:02,960 que o primeiro nodo que contén nove, o frecha esencialmente significa ir a aquela 280 00:12:02,960 --> 00:12:08,860 nó e pegar o valor na posición n, neste caso, o campo de datos chamado n. 281 00:12:08,860 --> 00:12:14,120 >> Como un aparte - e vimos que algunhas de semanas, cando alguén preguntou - 282 00:12:14,120 --> 00:12:18,840 esta sintaxe é novo, pero non darnos poderes que 283 00:12:18,840 --> 00:12:20,040 xa non ten. 284 00:12:20,040 --> 00:12:25,325 Cal foi esta frase equivalente a usar notación de punto e protagonista dunha parella 285 00:12:25,325 --> 00:12:29,490 de semanas, cando tirada atrás esta capa algo prematuramente? 286 00:12:29,490 --> 00:12:31,780 >> Estudante: [inaudível]. 287 00:12:31,780 --> 00:12:38,880 >> COLUMNA 1: Exactamente, foi estrela, e logo foi protagonista punto n, con 288 00:12:38,880 --> 00:12:41,930 parénteses aquí, o que parece, francamente, creo que unha morea 289 00:12:41,930 --> 00:12:43,320 máis enigmática de ler. 290 00:12:43,320 --> 00:12:46,270 Pero a estrela do punteiro, como sempre, medios para alí. 291 00:12:46,270 --> 00:12:49,090 E unha vez que está alí, que datos campo que queres acceder? 292 00:12:49,090 --> 00:12:52,730 Ben, usa a notación de punto para acceder un campo de datos estruturas, e eu 293 00:12:52,730 --> 00:12:54,140 quere especificamente n. 294 00:12:54,140 --> 00:12:56,240 >> Francamente, eu diría que este é só máis difícil de ler. 295 00:12:56,240 --> 00:12:58,080 É máis difícil lembrar de onde que os parénteses ir, o 296 00:12:58,080 --> 00:12:59,030 estrela e todo iso. 297 00:12:59,030 --> 00:13:02,150 Así, o mundo adoptaron algún sintática azucre, por así dicir. 298 00:13:02,150 --> 00:13:04,740 Só unha forma sexy de dicir: isto equivale, e 299 00:13:04,740 --> 00:13:05,970 quizais máis intuitiva. 300 00:13:05,970 --> 00:13:09,600 O punteiro é de feito un punteiro, o frecha significa notación ir alí e atopar 301 00:13:09,600 --> 00:13:11,890 o campo neste caso chamado n. 302 00:13:11,890 --> 00:13:13,660 >> Entón, se eu atopalo, entender o que fago. 303 00:13:13,660 --> 00:13:17,430 Eu simplemente impresión, penso por cento i, conectar o valor para que int. 304 00:13:17,430 --> 00:13:20,730 Eu chamo de durmir por un segundo só para tipo de pausa cousas na pantalla para 305 00:13:20,730 --> 00:13:22,900 dar ao usuario un segundo para absorber o que pasou. 306 00:13:22,900 --> 00:13:24,290 E entón eu gorgolexo. 307 00:13:24,290 --> 00:13:26,330 Se non, o que fago? 308 00:13:26,330 --> 00:13:30,960 Eu actualizar punteiro a igual frecha de punteiro próximo. 309 00:13:30,960 --> 00:13:35,840 >> Entón, só para deixar claro, isto significa ir alí, utilizando o meu notación old-school. 310 00:13:35,840 --> 00:13:39,580 Entón, iso significa só ir a calquera está apuntando para que, o moi 311 00:13:39,580 --> 00:13:43,660 primeiro caso é que eu estou apuntando para a estrutura con nove nel. 312 00:13:43,660 --> 00:13:44,510 Entón eu fun alí. 313 00:13:44,510 --> 00:13:47,880 E entón a notación de punto significa, obter o valor na próxima. 314 00:13:47,880 --> 00:13:50,470 >> Pero o valor, aínda que está deseñado como un estreito, é só un número. 315 00:13:50,470 --> 00:13:51,720 É un enderezo numérico. 316 00:13:51,720 --> 00:13:55,670 Así, esta liña de código, se escrito como este, o máis enigmático 317 00:13:55,670 --> 00:14:00,190 forma, ou así, a pouco máis xeito intuitivo, só significa mover a man 318 00:14:00,190 --> 00:14:03,460 desde o primeiro nodo ao seguinte, e logo, o seguinte, e entón a 319 00:14:03,460 --> 00:14:05,320 seguinte, e así por diante. 320 00:14:05,320 --> 00:14:09,920 >> Polo tanto, non vou me debruzouse sobre a outra implementacións de inserción e exclusión 321 00:14:09,920 --> 00:14:14,030 e transversal, os dous primeiros que son moi implicado. 322 00:14:14,030 --> 00:14:17,010 E eu creo que é moi fácil obter perdido cando facelo verbalmente. 323 00:14:17,010 --> 00:14:19,890 Pero o que podemos facer aquí é tentar determinar como 324 00:14:19,890 --> 00:14:21,640 mellor facelo visualmente. 325 00:14:21,640 --> 00:14:24,800 Porque eu estaba a propoñer que se quere inserir elementos para esa 326 00:14:24,800 --> 00:14:26,680 lista existente, o que ten cinco elementos - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26 e 33 - 328 00:14:29,530 --> 00:14:33,300 se eu estivese indo a aplicar iso en código, eu teño considerar como ir 329 00:14:33,300 --> 00:14:34,160 sobre como facelo. 330 00:14:34,160 --> 00:14:37,720 >> E gustaríame propoñer a dar pasos de bebé segundo a cal, neste caso, é dicir, cales son 331 00:14:37,720 --> 00:14:41,090 os escenarios posibles que pode atopar en xeral? 332 00:14:41,090 --> 00:14:44,120 Ao aplicar inserción dun linked lista, iso só pasa de ser un 333 00:14:44,120 --> 00:14:46,090 exemplo específico de tamaño cinco. 334 00:14:46,090 --> 00:14:50,420 Ben, se quere inserir un número, como diría o número un, e 335 00:14:50,420 --> 00:14:53,380 mantemento da orde clasificada, onde Obviamente acontece co número un ten 336 00:14:53,380 --> 00:14:55,686 ir neste exemplo específico? 337 00:14:55,686 --> 00:14:56,840 Igual no inicio. 338 00:14:56,840 --> 00:15:00,030 >> Pero o que é interesante alí é que Se desexa inserir unha nesa 339 00:15:00,030 --> 00:15:04,100 lista, o punteiro necesidades especiais actualizarse parecer? 340 00:15:04,100 --> 00:15:04,610 First. 341 00:15:04,610 --> 00:15:07,830 Entón, eu diría, este é o primeiro caso que pode querer considerar un 342 00:15:07,830 --> 00:15:11,140 escenario que implica a inserción no o inicio da lista. 343 00:15:11,140 --> 00:15:15,400 >> Imos arrincar fóra quizais unha tan fácil ou mesmo caso máis sinxelo, en concepto falando. 344 00:15:15,400 --> 00:15:18,110 Supoña que queira inserir a número 35 en orde de clasificación. 345 00:15:18,110 --> 00:15:20,600 É, obviamente, pertence alí. 346 00:15:20,600 --> 00:15:25,320 Entón, o punteiro obviamente vai Ten que ser actualizado nese escenario? 347 00:15:25,320 --> 00:15:30,060 Punteiro de 34 polo que non nulo pero a dirección da estrutura 348 00:15:30,060 --> 00:15:31,800 contén o número 35. 349 00:15:31,800 --> 00:15:32,750 Entón, iso é caso dous. 350 00:15:32,750 --> 00:15:36,190 Entón, xa, eu son unha especie de cuantización a cantidade de traballo que teño que facer aquí. 351 00:15:36,190 --> 00:15:39,880 >> E, finalmente, no caso do medio é obvio de feito, no medio, se eu queira 352 00:15:39,880 --> 00:15:45,870 introducir algo así como dicir 23, que vai entre os 23 e os 26, pero 353 00:15:45,870 --> 00:15:48,680 Agora as cousas están un pouco máis parte, porque o que 354 00:15:48,680 --> 00:15:52,800 punteiros precisa ser cambiado? 355 00:15:52,800 --> 00:15:56,680 Entón, 22 obviamente precisa ser cambiado porque non pode apuntar máis de 26. 356 00:15:56,680 --> 00:16:00,320 El que apuntar para o novo nodo Vou ter que reservar chamando 357 00:16:00,320 --> 00:16:01,770 malloc ou algún equivalente. 358 00:16:01,770 --> 00:16:05,990 >> Pero, entón, eu tamén teño o novo nodo, 23 neste caso, que o seu punteiro 359 00:16:05,990 --> 00:16:07,870 apuntando para quen? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 E aí, será unha orde das operacións aquí. 362 00:16:10,380 --> 00:16:13,410 Porque se eu fai iso locamente, e eu por exemplo, no inicio do comezo 363 00:16:13,410 --> 00:16:16,040 da lista, e meu obxectivo é introducir 23. 364 00:16:16,040 --> 00:16:18,610 E eu comprobar, pertence aquí, preto de nove? 365 00:16:18,610 --> 00:16:18,950 Non 366 00:16:18,950 --> 00:16:20,670 Será que é aquí, xunto con 17? 367 00:16:20,670 --> 00:16:20,940 Non 368 00:16:20,940 --> 00:16:22,530 Será que pertence aquí xunto a 22? 369 00:16:22,530 --> 00:16:23,300 Si 370 00:16:23,300 --> 00:16:26,400 >> Agora, se eu son tolo aquí, e non a pensar sobre iso, eu podería 371 00:16:26,400 --> 00:16:28,320 reservar meu novo nodo a 23. 372 00:16:28,320 --> 00:16:32,080 Podo actualizar o punteiro do o no chamado 22, apuntando 373 00:16:32,080 --> 00:16:33,080 en que o novo nodo. 374 00:16:33,080 --> 00:16:36,140 E entón o que eu teño que actualizar punteiro do novo nodo a ser? 375 00:16:36,140 --> 00:16:38,120 >> Estudante: [inaudível]. 376 00:16:38,120 --> 00:16:38,385 >> COLUMNA 1: Exactamente. 377 00:16:38,385 --> 00:16:39,710 Apuntando a 26. 378 00:16:39,710 --> 00:16:45,590 Pero caramba, se eu xa non actualizar Punteiro de 22 para apuntar a este cara, e 379 00:16:45,590 --> 00:16:48,260 agora eu teño orfos, o resto da lista, por así dicir. 380 00:16:48,260 --> 00:16:52,140 Así, a orde das operacións aquí será importante. 381 00:16:52,140 --> 00:16:55,100 >> Para iso eu podería roubar, digamos, seis voluntarios. 382 00:16:55,100 --> 00:16:57,650 E imos ver se a xente non pode facelo visual en vez de código-wise. 383 00:16:57,650 --> 00:16:59,330 E temos algúns encantador estrés bolas para ti hoxe. 384 00:16:59,330 --> 00:17:02,510 OK, como sobre un, dous, no de volta - a finais alí. 385 00:17:02,510 --> 00:17:04,530 tres, catro, tanto de ti caras na final. 386 00:17:04,530 --> 00:17:05,579 E, cinco, seis. 387 00:17:05,579 --> 00:17:05,839 Claro. 388 00:17:05,839 --> 00:17:06,450 Cinco e seis. 389 00:17:06,450 --> 00:17:08,390 Todo ben e nós viremos para vós a próxima vez. 390 00:17:08,390 --> 00:17:09,640 Todo ben, imos para arriba. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Todo ben, sempre que está aquí en primeiro lugar, quere ser o único xeito 393 00:17:14,819 --> 00:17:16,119 no vidro Google aquí? 394 00:17:16,119 --> 00:17:19,075 Todo ben, entón, OK, Vidro, gravar un vídeo. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 OK, está listo para ir. 397 00:17:24,589 --> 00:17:27,950 >> Todo ben, entón se vostedes poden vir aquí, eu preparei con antelación 398 00:17:27,950 --> 00:17:30,110 algúns números. 399 00:17:30,110 --> 00:17:31,240 Todo ben, veña ata aquí. 400 00:17:31,240 --> 00:17:33,440 E por que non ir un pouco aínda máis desta forma. 401 00:17:33,440 --> 00:17:35,520 E imos ver, cal é o seu nome, co vidro Google? 402 00:17:35,520 --> 00:17:35,910 >> ALUMNO: Ben. 403 00:17:35,910 --> 00:17:36,230 >> COLUMNA 1: Ben? 404 00:17:36,230 --> 00:17:38,380 OK, Ben, vai ser a primeira, literalmente. 405 00:17:38,380 --> 00:17:40,580 Por iso, imos enviar-lle cara ao final da etapa. 406 00:17:40,580 --> 00:17:41,670 Todo ben, eo seu nome? 407 00:17:41,670 --> 00:17:41,990 >> ALUMNO: Jason. 408 00:17:41,990 --> 00:17:44,530 >> COLUMNA 1: Jason, OK vai ser o número nove. 409 00:17:44,530 --> 00:17:46,700 Entón, se quere seguir Ben desa forma. 410 00:17:46,700 --> 00:17:47,010 >> ALUMNO: Jill. 411 00:17:47,010 --> 00:17:49,630 >> COLUMNA 1: Jill, está indo a ser 17, que se eu fixese iso máis 412 00:17:49,630 --> 00:17:51,260 intelixente, eu tería iniciado na outra extrema. 413 00:17:51,260 --> 00:17:52,370 Ir por ese camiño. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 E vostede é? 416 00:17:53,670 --> 00:17:53,980 >> ALUMNO: Mary. 417 00:17:53,980 --> 00:17:56,130 >> COLUMNA 1: Mary, vai ser 22. 418 00:17:56,130 --> 00:17:58,420 E o seu nome é? 419 00:17:58,420 --> 00:17:58,810 >> ALUMNO: Chris. 420 00:17:58,810 --> 00:18:00,100 >> COLUMNA 1: Chris, vai ser 26. 421 00:18:00,100 --> 00:18:00,740 E entón, finalmente. 422 00:18:00,740 --> 00:18:01,400 >> ALUMNO: Diana. 423 00:18:01,400 --> 00:18:02,670 >> COLUMNA 1: Diana, vai ser 34. 424 00:18:02,670 --> 00:18:03,920 Entón vén aquí. 425 00:18:03,920 --> 00:18:06,360 >> Todo ben, tan perfecto clasificadas encargar xa. 426 00:18:06,360 --> 00:18:09,600 E imos adiante e facelo para que poidamos realmente - 427 00:18:09,600 --> 00:18:11,720 Ben é só o tipo de busca fóra en nada alí. 428 00:18:11,720 --> 00:18:15,670 OK, entón imos seguir adiante e describir esta usando armas, así como eu era, exactamente, 429 00:18:15,670 --> 00:18:16,250 o que está pasando. 430 00:18:16,250 --> 00:18:19,540 Entón vai adiante e dar-vos un pé ou dous entre vós. 431 00:18:19,540 --> 00:18:22,900 E vai adiante e apuntar cunha man para quen ten que estar apuntando para 432 00:18:22,900 --> 00:18:23,470 derivada. 433 00:18:23,470 --> 00:18:25,890 E se é nula só apuntar directo para o chan. 434 00:18:25,890 --> 00:18:27,690 OK, todo ben. 435 00:18:27,690 --> 00:18:32,290 >> Polo tanto, agora temos unha lista ligada, e déixeme propoñer que vou desempeñar o papel 436 00:18:32,290 --> 00:18:35,110 PTR, entón eu non vou incomodar tendo esta ao redor. 437 00:18:35,110 --> 00:18:37,830 E entón - alguén convención estúpida - pode chamar iso de calquera cousa que quere - 438 00:18:37,830 --> 00:18:39,800 punteiro predecesor, punteiro pred - 439 00:18:39,800 --> 00:18:43,930 é só o apelido que demos en noso código de exemplo para a man esquerda. 440 00:18:43,930 --> 00:18:47,240 O outro lado, que será manter o control de quen é quen no 441 00:18:47,240 --> 00:18:48,400 seguintes escenarios. 442 00:18:48,400 --> 00:18:52,390 >> Entón supoño que, en primeiro lugar, quero arrincar fóra aquel primeiro exemplo de inserción de, digamos 443 00:18:52,390 --> 00:18:54,330 20, na lista. 444 00:18:54,330 --> 00:18:57,160 Entón, eu vou ter que alguén para encarnan o número 20 para nós. 445 00:18:57,160 --> 00:18:58,950 Entón eu teño de alguén para malloc do público. 446 00:18:58,950 --> 00:18:59,380 Imos para arriba. 447 00:18:59,380 --> 00:19:00,340 Cal é o seu nome? 448 00:19:00,340 --> 00:19:01,300 >> ALUMNO: Brian. 449 00:19:01,300 --> 00:19:05,270 >> COLUMNA 1: Brian, todo ben, entón debe ser o nodo que contén 20. 450 00:19:05,270 --> 00:19:06,810 Todo ben, veña ata aquí. 451 00:19:06,810 --> 00:19:10,025 E, obviamente, onde Brian non pertence? 452 00:19:10,025 --> 00:19:12,190 Así, no medio - en realidade, agarde un minuto. 453 00:19:12,190 --> 00:19:13,420 Estamos facendo isto para fóra de orde. 454 00:19:13,420 --> 00:19:17,170 Estamos facendo iso moito máis difícil do que el ten que estar en primeiro lugar. 455 00:19:17,170 --> 00:19:21,210 OK, imos libre Brian e realloc Brian cinco. 456 00:19:21,210 --> 00:19:23,680 >> OK, entón agora queremos introducir Brian como cinco. 457 00:19:23,680 --> 00:19:25,960 Entón veña aquí xunto Ben só por un momento. 458 00:19:25,960 --> 00:19:28,250 E pode dicir presuntamente onde esta historia vai dar. 459 00:19:28,250 --> 00:19:30,500 Pero imos pensar coidadosamente sobre a orde das operacións. 460 00:19:30,500 --> 00:19:32,880 E é precisamente esta visuais que vai aliñar 461 00:19:32,880 --> 00:19:34,080 con ese código de mostra. 462 00:19:34,080 --> 00:19:40,120 Entón, aquí eu PTR apuntando inicialmente non en Ben, por si só, pero en calquera 463 00:19:40,120 --> 00:19:43,245 valor que contén, o que neste caso é - cal é o seu nome? 464 00:19:43,245 --> 00:19:43,670 >> ALUMNO: Jason. 465 00:19:43,670 --> 00:19:47,350 >> COLUMNA 1: Jason, entón Ben e eu somos apuntando a Jason neste momento. 466 00:19:47,350 --> 00:19:49,700 Entón agora eu teño de determinar, onde é que Brian pertence? 467 00:19:49,700 --> 00:19:53,500 Entón o único que eu teño acceso a agora é o elemento de datos n. 468 00:19:53,500 --> 00:19:58,280 Entón eu vou dar un ollo, é Brian menos Jason? 469 00:19:58,280 --> 00:19:59,770 A resposta é verdadeira. 470 00:19:59,770 --> 00:20:03,680 >> Entón, o que ten agora de pasar, na orde correcta? 471 00:20:03,680 --> 00:20:07,120 Necesito actualizar cantos punteiros en total nesta historia? 472 00:20:07,120 --> 00:20:10,720 Onde a man aínda está a apuntar cara Jason, e súa man - se quere 473 00:20:10,720 --> 00:20:12,930 poñer a man como, de algunha maneira, eu Non sei, un punto de interrogación. 474 00:20:12,930 --> 00:20:14,070 OK, bo. 475 00:20:14,070 --> 00:20:15,670 >> Todo ben, así que ten algúns candidatos. 476 00:20:15,670 --> 00:20:20,500 Ou Ben ou eu ou Brian ou Jason ou calquera outra persoa, que 477 00:20:20,500 --> 00:20:21,370 punteiros que cambiar? 478 00:20:21,370 --> 00:20:23,260 Cantos en total? 479 00:20:23,260 --> 00:20:24,080 >> OK, entón dous. 480 00:20:24,080 --> 00:20:27,090 O meu punteiro realmente non importa máis porque eu son só temporal. 481 00:20:27,090 --> 00:20:31,370 Por iso, é estes dúas caras, presumiblemente, Ben e Brian. 482 00:20:31,370 --> 00:20:34,410 Entón deixe-me propor que nós actualizamos Ben, xa que está en primeiro lugar. 483 00:20:34,410 --> 00:20:36,350 O primeiro elemento da lista agora será Brian. 484 00:20:36,350 --> 00:20:38,070 Así punto Ben en Brian. 485 00:20:38,070 --> 00:20:39,320 OK, e agora? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Quen está apuntada para quen? 488 00:20:43,460 --> 00:20:44,710 >> Estudante: [inaudível]. 489 00:20:44,710 --> 00:20:46,180 >> COLUMNA 1: OK, entón Brian ten para ligar a Jason. 490 00:20:46,180 --> 00:20:48,360 Pero o que eu perdín a noción do que punteiro? 491 00:20:48,360 --> 00:20:49,980 Non sei onde Jason é? 492 00:20:49,980 --> 00:20:50,790 >> Estudante: [inaudível]. 493 00:20:50,790 --> 00:20:52,620 >> COLUMNA 1: fago, sempre que eu son o punteiro temporal. 494 00:20:52,620 --> 00:20:55,110 E, presuntamente, non cambiei para apuntar para o novo nodo. 495 00:20:55,110 --> 00:20:58,300 Así, podemos simplemente ter punto de Brian en quen estou apuntando. 496 00:20:58,300 --> 00:20:59,000 E estamos a facer. 497 00:20:59,000 --> 00:21:01,890 Así, un caso, a inserción na inicio da lista. 498 00:21:01,890 --> 00:21:02,950 Había dous pasos fundamentais. 499 00:21:02,950 --> 00:21:06,750 Un deles, temos que actualizar Ben, e, a continuación, Tamén temos que actualizar Brian. 500 00:21:06,750 --> 00:21:09,230 E entón eu non ten que se preocupar deambulan polo resto da 501 00:21:09,230 --> 00:21:12,680 lista, porque xa atopou o seu localización, porque pertencía ao 502 00:21:12,680 --> 00:21:14,080 esquerda do primeiro elemento. 503 00:21:14,080 --> 00:21:15,400 >> Todo ben, entón moi sinxelo. 504 00:21:15,400 --> 00:21:18,110 De feito, parece que estamos case facendo iso moi complicado. 505 00:21:18,110 --> 00:21:20,240 Entón, imos agora arrincar fóra da final da lista, e ver onde 506 00:21:20,240 --> 00:21:21,380 a complexidade comeza. 507 00:21:21,380 --> 00:21:24,560 Entón, se agora distribución do público. 508 00:21:24,560 --> 00:21:25,540 Calquera quere xogar 55? 509 00:21:25,540 --> 00:21:26,700 Todo ben, eu vin o de primeira man. 510 00:21:26,700 --> 00:21:29,620 Imos para arriba. 511 00:21:29,620 --> 00:21:30,030 Si 512 00:21:30,030 --> 00:21:31,177 Cal é o seu nome? 513 00:21:31,177 --> 00:21:32,310 >> Estudante: [inaudível]. 514 00:21:32,310 --> 00:21:33,240 >> COLUMNA 1: Habata. 515 00:21:33,240 --> 00:21:33,890 Ok, imos alí enriba. 516 00:21:33,890 --> 00:21:35,730 Vai ser o número 55. 517 00:21:35,730 --> 00:21:37,820 Entón, por suposto, pertencen ó final da lista. 518 00:21:37,820 --> 00:21:41,850 Entón, imos repetir a simulación comigo sendo o PTR só por un momento. 519 00:21:41,850 --> 00:21:44,050 Entón, eu estou indo primeiro para ligar o que Ben está a apuntar. 520 00:21:44,050 --> 00:21:45,900 Nós dous estamos apuntando agora en Brian. 521 00:21:45,900 --> 00:21:48,420 Así, 55 non é menos que cinco. 522 00:21:48,420 --> 00:21:52,510 Entón eu vou actualizar por apuntando ao seguinte punteiro de Brian, que 523 00:21:52,510 --> 00:21:54,450 agora é, por suposto, Jason. 524 00:21:54,450 --> 00:21:57,310 55 non sexa inferior a nove, de xeito Vou actualizar PTR. 525 00:21:57,310 --> 00:21:58,890 Vou actualizar PTR. 526 00:21:58,890 --> 00:22:02,290 Vou actualizar PTR Vou actualizar PTR. 527 00:22:02,290 --> 00:22:05,060 E eu vou - hmm, o que é o seu nome? 528 00:22:05,060 --> 00:22:05,560 >> ALUMNO: Diana. 529 00:22:05,560 --> 00:22:09,190 >> COLUMNA 1: Diana está apuntando, por suposto, o nulo coa man esquerda. 530 00:22:09,190 --> 00:22:13,030 Entón onde é que realmente Habata pertencen claramente? 531 00:22:13,030 --> 00:22:15,050 Á esquerda, aquí. 532 00:22:15,050 --> 00:22:19,460 Entón, como é que eu sei para poñelo aquí Eu creo que eu estraguei todo. 533 00:22:19,460 --> 00:22:22,420 Porque o que é PTR arte neste momento? 534 00:22:22,420 --> 00:22:23,240 Nulo. 535 00:22:23,240 --> 00:22:25,580 Así, aínda que, visualmente, o que pudermos ver, obviamente, todo isto 536 00:22:25,580 --> 00:22:26,610 caras aquí no escenario. 537 00:22:26,610 --> 00:22:29,680 Non teño mantido a par do anterior persoa da lista. 538 00:22:29,680 --> 00:22:33,210 Non teño un dedo apuntando cara fóra, neste caso, o número de nodo 34. 539 00:22:33,210 --> 00:22:34,760 >> Entón, imos comezar esta remate. 540 00:22:34,760 --> 00:22:37,560 Entón, agora eu realmente teño unha segunda variable local. 541 00:22:37,560 --> 00:22:40,980 E iso é o que podes ver no código C mostra real, onde, como eu vou, 542 00:22:40,980 --> 00:22:45,860 cando eu actualizar a miña man dereita para ligar Jason, deixando, así, Brian atrás, eu 543 00:22:45,860 --> 00:22:51,440 mellor comezar a usar a man esquerda actualizar onde eu estaba, para que, como eu vou 544 00:22:51,440 --> 00:22:52,700 a través desta lista - 545 00:22:52,700 --> 00:22:55,040 máis sen xeito do que eu pretendía agora aquí visual - 546 00:22:55,040 --> 00:22:56,740 Vou chegar ao final da lista. 547 00:22:56,740 --> 00:23:00,020 >> Esta man aínda é nulo, o que é moi inútil, excepto para indicar 548 00:23:00,020 --> 00:23:02,980 Son claramente ao final da lista pero agora polo menos eu teño esa 549 00:23:02,980 --> 00:23:08,270 punteiro predecesor apuntar aquí, entón agora que as mans e os punteiros que debe 550 00:23:08,270 --> 00:23:10,150 para ser actualizado? 551 00:23:10,150 --> 00:23:13,214 Cuxa man que quere reconfigurar primeiro? 552 00:23:13,214 --> 00:23:15,190 >> Estudante: [inaudível]. 553 00:23:15,190 --> 00:23:16,220 >> COLUMNA 1: OK, entón Diana. 554 00:23:16,220 --> 00:23:21,110 Onde quere apuntar Punteiro á esquerda de Diana at? 555 00:23:21,110 --> 00:23:23,620 Aos 55 anos, presume-se, de xeito que temos inserido alí. 556 00:23:23,620 --> 00:23:25,560 E onde deben ir 55 punteiro? 557 00:23:25,560 --> 00:23:27,000 Abaixo, representando nulo. 558 00:23:27,000 --> 00:23:28,890 E as mans, neste momento, non importa, porque eran só 559 00:23:28,890 --> 00:23:30,070 variables temporais. 560 00:23:30,070 --> 00:23:31,030 Polo tanto, agora estamos a facer. 561 00:23:31,030 --> 00:23:34,650 >> Así, a complexidade adicional alí - e non é tan difícil de aplicar, 562 00:23:34,650 --> 00:23:38,660 pero precisamos dunha variable secundaria para facer seguro de que antes de cambiar a miña dereita 563 00:23:38,660 --> 00:23:42,140 banda, eu actualizar o valor do meu lado esquerdo banda, o punteiro pred neste caso, de xeito 564 00:23:42,140 --> 00:23:45,860 que eu teño un punteiro de arrastre manter o control de onde eu estaba. 565 00:23:45,860 --> 00:23:49,360 Agora, como un aparte, se está a pensar que iso través, este se sente como se fose un 566 00:23:49,360 --> 00:23:51,490 pouco aburrido ter que manter seguir desa man esquerda. 567 00:23:51,490 --> 00:23:54,015 >> Cal sería outra solución a este problema foron? 568 00:23:54,015 --> 00:23:56,500 Se ten que redeseñar os datos estrutura que estamos a falar 569 00:23:56,500 --> 00:23:59,630 por agora? 570 00:23:59,630 --> 00:24:02,690 Se este tipo de só se sente un pouco aburrido ter, tipo, dous punteiros 571 00:24:02,690 --> 00:24:08,430 pasando a lista, quen máis podería ter, nun mundo ideal, mantense 572 00:24:08,430 --> 00:24:10,160 información de que necesitamos? 573 00:24:10,160 --> 00:24:11,360 Si? 574 00:24:11,360 --> 00:24:12,610 >> Estudante: [inaudível]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> COLUMNA 1: Exactamente. 577 00:24:16,150 --> 00:24:19,130 Dereito así que non hai realmente unha interesante xerme de unha idea. 578 00:24:19,130 --> 00:24:22,470 E esta idea dun punteiro anterior, apuntando para o elemento anterior. 579 00:24:22,470 --> 00:24:25,580 E se eu só incorporada que dentro da propia lista? 580 00:24:25,580 --> 00:24:27,810 E iso vai ser difícil de ver iso sen todo o papel 581 00:24:27,810 --> 00:24:28,830 caendo no chan. 582 00:24:28,830 --> 00:24:31,860 Pero supoña que estes faces usado tanto das súas mans a unha previa 583 00:24:31,860 --> 00:24:35,950 punteiro, e un punteiro próximo, así aplicar o que imos chamar un dobre 584 00:24:35,950 --> 00:24:36,830 lista ligada. 585 00:24:36,830 --> 00:24:41,090 Iso me permitiría clasificar de rewind, moito máis facilmente, sen min, o 586 00:24:41,090 --> 00:24:43,800 programador, ter que manter controlar manualmente - 587 00:24:43,800 --> 00:24:44,980 verdadeiramente a man - 588 00:24:44,980 --> 00:24:47,280 de onde eu fora anteriormente na lista. 589 00:24:47,280 --> 00:24:48,110 Polo tanto, non imos facelo. 590 00:24:48,110 --> 00:24:50,950 Imos mantelo simple, porque iso é terá un prezo, dúas veces máis 591 00:24:50,950 --> 00:24:53,450 moito máis espazo para os punteiros, se quere un segundo. 592 00:24:53,450 --> 00:24:55,760 Pero isto é de feito un común estrutura de datos coñecida como un 593 00:24:55,760 --> 00:24:57,410 lista dobremente ligada. 594 00:24:57,410 --> 00:25:01,310 >> Imos facer o último exemplo aquí e poñer estes faces fóra da súa miseria. 595 00:25:01,310 --> 00:25:03,270 Entón malloc 20. 596 00:25:03,270 --> 00:25:05,320 Imos superior do corredor alí. 597 00:25:05,320 --> 00:25:06,280 Todo ben, cal é o seu nome? 598 00:25:06,280 --> 00:25:07,440 >> Estudante: [inaudível]. 599 00:25:07,440 --> 00:25:07,855 >> COLUMNA 1: Sentímolo? 600 00:25:07,855 --> 00:25:08,480 >> Estudante: [inaudível]. 601 00:25:08,480 --> 00:25:09,410 >> COLUMNA 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK imos alí cara arriba. 603 00:25:10,230 --> 00:25:11,910 Ten que ser 20. 604 00:25:11,910 --> 00:25:14,720 Vostede, obviamente, vai pertencer entre 17 e 22. 605 00:25:14,720 --> 00:25:16,150 Entón me deixe aprender a lección. 606 00:25:16,150 --> 00:25:18,150 Vou comezar punteiro apuntando a Brian. 607 00:25:18,150 --> 00:25:21,190 E eu vou ter a miña man esquerda só actualizar a Brian como eu pasar para 608 00:25:21,190 --> 00:25:23,600 Jason, comprobación fai 20 a menos que nove? 609 00:25:23,600 --> 00:25:24,060 Non 610 00:25:24,060 --> 00:25:25,430 É de 20 a menos de 17 anos? 611 00:25:25,430 --> 00:25:25,880 Non 612 00:25:25,880 --> 00:25:27,450 É de 20 a menos de 22? 613 00:25:27,450 --> 00:25:28,440 Si 614 00:25:28,440 --> 00:25:34,070 Entón, o que os punteiros ou mans que cambiar onde están a apuntar agora? 615 00:25:34,070 --> 00:25:37,070 >> Así, podemos facer 17 apuntando a 20. 616 00:25:37,070 --> 00:25:37,860 Entón, iso é bo. 617 00:25:37,860 --> 00:25:40,080 Onde queremos apuntar o punteiro agora? 618 00:25:40,080 --> 00:25:41,330 Aos 22 anos. 619 00:25:41,330 --> 00:25:45,410 E sabemos que 22 é, unha vez máis, grazas ao meu punteiro temporal. 620 00:25:45,410 --> 00:25:46,760 Entón, nós estamos OK alí. 621 00:25:46,760 --> 00:25:49,440 Así, debido a este almacenamento temporal Eu mantiven o control de onde todo o mundo é. 622 00:25:49,440 --> 00:25:55,055 E agora pode ir a onde visual vostede pertence, e agora necesitamos 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 bolas de estrés, e unha salva de palmas para 624 00:25:58,410 --> 00:25:59,770 estes faces, se puidésemos. 625 00:25:59,770 --> 00:26:00,410 Ben feito. 626 00:26:00,410 --> 00:26:05,320 >> [Aplausos] 627 00:26:05,320 --> 00:26:06,330 >> COLUMNA 1: Todo ben. 628 00:26:06,330 --> 00:26:09,860 E pode manter as pezas mementos papel. 629 00:26:09,860 --> 00:26:15,930 >> Todo ben, entón, confíe en min é moi máis fácil entrar por aquela con 630 00:26:15,930 --> 00:26:17,680 os seres humanos do que con código real. 631 00:26:17,680 --> 00:26:22,690 Pero o que vai atopar nun momento agora, é o mesmo - Oh, moitas grazas. 632 00:26:22,690 --> 00:26:23,630 Grazas - 633 00:26:23,630 --> 00:26:29,360 é que vai descubrir que os mesmos datos estrutura, unha lista ligada, realmente pode 634 00:26:29,360 --> 00:26:33,200 ser utilizado como un bloque de construción aínda máis estruturas de datos sofisticadas. 635 00:26:33,200 --> 00:26:37,620 >> E entender tamén o tema aquí é que temos absolutamente introduciu máis 636 00:26:37,620 --> 00:26:40,060 complexidade na implantación deste algoritmo. 637 00:26:40,060 --> 00:26:43,940 Inserción, e pasou por iso, exclusión e consulta, é algo 638 00:26:43,940 --> 00:26:46,660 máis complicado do que Foi con unha matriz. 639 00:26:46,660 --> 00:26:48,040 Pero gañar un dinamismo. 640 00:26:48,040 --> 00:26:50,180 Temos unha estrutura de datos adaptativa. 641 00:26:50,180 --> 00:26:54,010 >> Pero, de novo, nós pagamos un prezo de ter algún complexidade adicional, tanto en 642 00:26:54,010 --> 00:26:54,910 implementar lo. 643 00:26:54,910 --> 00:26:56,750 E estamos desistido de acceso aleatorio. 644 00:26:56,750 --> 00:27:00,450 E para ser honesto, non hai algún bo borrar diapositivas podo dar-lle que 645 00:27:00,450 --> 00:27:03,120 Di aquí que é por iso que unha lista ligada é mellor que unha matriz. 646 00:27:03,120 --> 00:27:04,100 E deixar por iso mesmo. 647 00:27:04,100 --> 00:27:07,520 Porque o tema recurrente agora, aínda máis aínda nas próximas semanas, é 648 00:27:07,520 --> 00:27:10,200 que non é necesariamente unha resposta correcta. 649 00:27:10,200 --> 00:27:13,830 >> É por iso que temos o eixe separado do proxecto para conxuntos de problemas. 650 00:27:13,830 --> 00:27:17,700 Vai ser moi sensible ao contexto Se quere usar estes datos 651 00:27:17,700 --> 00:27:21,750 estrutura ou aquel, e vai depende do que é importante para vostede en termos 652 00:27:21,750 --> 00:27:24,620 de recursos e complexidade. 653 00:27:24,620 --> 00:27:28,830 >> Pero déixeme propoñer que os datos ideais estrutura, o Santo Graal, sería 654 00:27:28,830 --> 00:27:32,200 algo que é constante de tempo, independentemente da cantidade de material 655 00:27:32,200 --> 00:27:36,940 dentro del, non sería sorprendente se un estrutura de datos devolveu respostas 656 00:27:36,940 --> 00:27:37,920 tempo constante. 657 00:27:37,920 --> 00:27:38,330 Si 658 00:27:38,330 --> 00:27:40,110 Esta palabra está na súa enorme dicionario. 659 00:27:40,110 --> 00:27:41,550 Ou non, esta palabra non é. 660 00:27:41,550 --> 00:27:43,270 Ou calquera problema deste tipo alá. 661 00:27:43,270 --> 00:27:46,360 Ben, imos ver se non podemos, polo menos, dar un paso cara a iso. 662 00:27:46,360 --> 00:27:50,190 >> Déixeme propor unha nova estrutura de datos que se pode usar para diferentes cousas, 663 00:27:50,190 --> 00:27:52,260 neste caso denominada táboa hash. 664 00:27:52,260 --> 00:27:55,590 E por iso estamos realmente mirando cara atrás nunha matriz, no caso en apreciado, e 665 00:27:55,590 --> 00:28:00,550 arbitrariamente, eu deseño esta táboa hash como unha matriz cunha especie de 666 00:28:00,550 --> 00:28:02,810 matriz bidimensional - 667 00:28:02,810 --> 00:28:05,410 ou mellor, que se describe aquí como un dous matriz dimensional - pero este é só 668 00:28:05,410 --> 00:28:10,770 unha matriz de tamaño 26, de tal xeito que se chamar a táboa da matriz, soporte de mesa 669 00:28:10,770 --> 00:28:12,440 cero é o rectángulo na parte superior. 670 00:28:12,440 --> 00:28:15,090 Táboa soporte 25 é o rectángulo na parte inferior. 671 00:28:15,090 --> 00:28:18,620 E é así que eu podería chamar un conxunto de datos estrutura en que desexa almacenar 672 00:28:18,620 --> 00:28:19,790 nomes de persoas. 673 00:28:19,790 --> 00:28:24,370 >> Así, por exemplo, e eu non vou chamar a cousa toda aquí no alto, se eu 674 00:28:24,370 --> 00:28:29,160 tiña esa matriz, que eu estou indo agora para chamar a unha táboa hash, e este é de novo 675 00:28:29,160 --> 00:28:31,360 Lugar de cero. 676 00:28:31,360 --> 00:28:34,840 Este aquí é a situación un, e así por diante. 677 00:28:34,840 --> 00:28:37,880 Eu afirmo que quero usar estes datos estrutura, por mor da discusión, 678 00:28:37,880 --> 00:28:42,600 para gardar os nomes das persoas, Alicia e Bob e Charlie e outros nomes. 679 00:28:42,600 --> 00:28:46,110 Entón, pense nisto agora, como o inicio de, digamos, un dicionario 680 00:28:46,110 --> 00:28:47,520 con moitas palabras. 681 00:28:47,520 --> 00:28:49,435 Elas acontecen a ser nomes No noso exemplo aquí. 682 00:28:49,435 --> 00:28:52,560 E todo isto é moi pertinente, quizais, para implantación dun corrector ortográfico, como 683 00:28:52,560 --> 00:28:54,400 quizais para o problema de definir seis. 684 00:28:54,400 --> 00:28:59,300 >> Entón, se temos unha matriz de tamaño 26 de xeito que este é o lugar 25 685 00:28:59,300 --> 00:29:03,390 na parte inferior, e eu afirmo que Alicia é a primeira palabra no dicionario de 686 00:29:03,390 --> 00:29:07,260 nomes que quero introducir na RAM, a esta estrutura de datos, onde están 687 00:29:07,260 --> 00:29:12,480 instintos dicindo que Alicia nome debe ir neste array? 688 00:29:12,480 --> 00:29:13,510 >> Temos 26 opcións. 689 00:29:13,510 --> 00:29:14,990 Onde queremos colocar-la? 690 00:29:14,990 --> 00:29:16,200 Queremos que o soporte cero, non? 691 00:29:16,200 --> 00:29:18,280 Un para Alice, imos chamar iso de cero. 692 00:29:18,280 --> 00:29:20,110 E B será un, e C será de dous. 693 00:29:20,110 --> 00:29:22,600 Entón, imos escribir Nome aquí enriba de Alicia. 694 00:29:22,600 --> 00:29:24,890 Se, entón, introducir Bob, o seu nome vai aquí. 695 00:29:24,890 --> 00:29:27,280 Charlie vai pasar aquí. 696 00:29:27,280 --> 00:29:30,500 E así por diante ao longo esta estrutura de datos. 697 00:29:30,500 --> 00:29:32,090 >> Trátase dunha estrutura de datos marabilloso. 698 00:29:32,090 --> 00:29:32,730 Por que? 699 00:29:32,730 --> 00:29:37,460 Ben, o que é o tempo de execución introducir o nome dun humano a esta 700 00:29:37,460 --> 00:29:39,850 estrutura de datos agora? 701 00:29:39,850 --> 00:29:43,702 Dado que esta táboa é aplicado, verdadeiramente, como unha matriz. 702 00:29:43,702 --> 00:29:44,940 Ben, é tempo constante. 703 00:29:44,940 --> 00:29:45,800 É fin dun. 704 00:29:45,800 --> 00:29:46,360 Por que? 705 00:29:46,360 --> 00:29:48,630 >> Ben, como determina onde Alicia pertence? 706 00:29:48,630 --> 00:29:51,000 Mira para que letra do seu nome? 707 00:29:51,000 --> 00:29:51,490 A primeira. 708 00:29:51,490 --> 00:29:54,350 E pode chegar alí, se é unha cadea, só mirando para cadea 709 00:29:54,350 --> 00:29:55,200 Soporte de cero. 710 00:29:55,200 --> 00:29:57,110 Así, o carácter zeroth da cadea. 711 00:29:57,110 --> 00:29:57,610 Iso é doado. 712 00:29:57,610 --> 00:30:00,350 Fixemos iso no Crypto semanas de asignación atrás. 713 00:30:00,350 --> 00:30:05,310 E entón cando vostede sabe que Alicia A carta é a capital, podemos restar 714 00:30:05,310 --> 00:30:08,160 off 65 ou maiúscula si, que nos dá cero. 715 00:30:08,160 --> 00:30:10,940 Así, sabemos que Alicia pertence na posición cero. 716 00:30:10,940 --> 00:30:14,240 >> E dado un punteiro a estes datos estrutura, dalgunha sorte, o tempo fai 717 00:30:14,240 --> 00:30:18,840 el me levar para atopar a localización cero nun array? 718 00:30:18,840 --> 00:30:22,080 Só un paso, non é hora constante debido a que o acceso aleatorio 719 00:30:22,080 --> 00:30:23,780 proposto foi unha característica dunha matriz. 720 00:30:23,780 --> 00:30:28,570 Así, en breve, descubrir o que o índice do nome de Alicia é, que é, en 721 00:30:28,570 --> 00:30:32,610 Neste caso é A, ou imos só resolver que a cero, en que B é un C e é 722 00:30:32,610 --> 00:30:34,900 dous, imaxinando que fora É tempo constante. 723 00:30:34,900 --> 00:30:38,510 Eu só teño que mirar para a súa primeira carta, descubrir onde cero é un 724 00:30:38,510 --> 00:30:40,460 matriz tamén é de tempo constante. 725 00:30:40,460 --> 00:30:42,140 Entón, tecnicamente iso é como dous pasos agora. 726 00:30:42,140 --> 00:30:43,330 Pero iso aínda é constante. 727 00:30:43,330 --> 00:30:46,880 Entón, chamamos iso dun gran A, entón nós Alicia inserida nesta táboa 728 00:30:46,880 --> 00:30:48,440 tempo constante. 729 00:30:48,440 --> 00:30:50,960 >> Pero, por suposto, eu estou sendo inxenuo aquí, non? 730 00:30:50,960 --> 00:30:53,240 E se hai unha Aaron na clase? 731 00:30:53,240 --> 00:30:53,990 Ou Alicia? 732 00:30:53,990 --> 00:30:57,230 Ou outros nomes comezando con A. Onde imos poñer 733 00:30:57,230 --> 00:31:00,800 esa persoa, non? 734 00:31:00,800 --> 00:31:03,420 Quero dicir, agora hai só tres persoas sobre a mesa, entón quizais nós 735 00:31:03,420 --> 00:31:07,490 debe poñer Aaron no lugar cero un, dous, tres. 736 00:31:07,490 --> 00:31:09,480 >> Certo, eu podería poñer un aquí. 737 00:31:09,480 --> 00:31:13,350 Pero entón, se intentamos introducir David en Nesta lista, onde é que David ir? 738 00:31:13,350 --> 00:31:15,170 Agora o noso sistema comeza a romper abaixo, non? 739 00:31:15,170 --> 00:31:19,210 Porque agora David acaba aquí Aaron se é realmente aquí. 740 00:31:19,210 --> 00:31:23,060 E agora toda esa idea de ter un estrutura de datos limpo que nos dá 741 00:31:23,060 --> 00:31:28,010 insercións de tempo constantes, non está constante de tempo, porque eu teño que 742 00:31:28,010 --> 00:31:31,240 comprobar, oh, drogas, alguén xa está no lugar de Alicia. 743 00:31:31,240 --> 00:31:35,320 >> Déixeme investigar o resto dos datos estrutura, a buscar un lugar para poñer 744 00:31:35,320 --> 00:31:37,130 alguén como o nome de Aaron. 745 00:31:37,130 --> 00:31:39,390 E así que tamén está empezando ter tempo lineal. 746 00:31:39,390 --> 00:31:42,710 Ademais, se agora quere atopar o Aaron nesta estrutura de datos, e 747 00:31:42,710 --> 00:31:45,430 comproba, eo nome de Aaron non está aquí. 748 00:31:45,430 --> 00:31:47,960 Ideal, vostede tería só que dicir Arão non na estrutura de datos. 749 00:31:47,960 --> 00:31:51,530 Pero se comezar a facer sala para Aaron onde debería haber un D 750 00:31:51,530 --> 00:31:55,600 ou un E, ti, o peor caso, ten que comprobar Toda a estrutura de datos, en 751 00:31:55,600 --> 00:31:59,480 caso en que se transforma en algo lineal no tamaño da táboa. 752 00:31:59,480 --> 00:32:00,920 >> Entón todo ben, eu vou solucionar isto. 753 00:32:00,920 --> 00:32:04,200 O problema aquí é que eu tiña 26 elementos nesta matriz. 754 00:32:04,200 --> 00:32:05,000 Deixe me cambiar. 755 00:32:05,000 --> 00:32:06,010 Berros. 756 00:32:06,010 --> 00:32:10,600 Déixeme cambiar isto para que, no canto de ser tamaño 26 en total, teña en conta o fondo 757 00:32:10,600 --> 00:32:12,720 índice cambiará de n menos 1. 758 00:32:12,720 --> 00:32:16,610 Si 26 é claramente demasiado pequeno para os seres humanos ' nomes, porque hai miles de 759 00:32:16,610 --> 00:32:20,830 nomes do mundo, imos facer en 100 ou 1000 ou 10000. 760 00:32:20,830 --> 00:32:22,960 Nós só reservar máis espazo. 761 00:32:22,960 --> 00:32:27,230 >> Ben, iso non significa necesariamente diminuír a probabilidade de que non terá dous 762 00:32:27,230 --> 00:32:31,510 persoas con nomes que comezan con A, e así, estaba indo para tratar de poñer un 763 00:32:31,510 --> 00:32:33,120 nomes en lugar aínda a cero. 764 00:32:33,120 --> 00:32:36,850 Eles aínda van chocar, o que quere dicir que aínda que de unha solución para poñer 765 00:32:36,850 --> 00:32:41,020 Alicia e Arão e Alicia e outros nomes que comezan con A en outro lugar. 766 00:32:41,020 --> 00:32:43,460 Pero como un gran problema é ese? 767 00:32:43,460 --> 00:32:46,870 Cal é a probabilidade de que ten colisións nunha base de datos 768 00:32:46,870 --> 00:32:48,240 estrutura como esta? 769 00:32:48,240 --> 00:32:52,570 >> Ben, deixe-me - nós imos volver a esta pregunta aquí. 770 00:32:52,570 --> 00:32:55,530 E mira como poderiamos resolver-lo por primeira vez. 771 00:32:55,530 --> 00:32:58,480 Déixame sacar esta proposta aquí. 772 00:32:58,480 --> 00:33:02,020 O que acabamos de describir é un algoritmo, a heurística chamado lineal 773 00:33:02,020 --> 00:33:05,030 enquisa segundo a cal, se intentou introducir algo aquí nestes datos 774 00:33:05,030 --> 00:33:08,920 estrutura, o que é denominado táboa hash e non hai espazo alí, 775 00:33:08,920 --> 00:33:12,000 verdadeiramente sondar a estrutura de datos verificación, e está dispoñible? 776 00:33:12,000 --> 00:33:13,430 É esta dispoñible e está dispoñible? 777 00:33:13,430 --> 00:33:13,980 É esta dispoñible? 778 00:33:13,980 --> 00:33:17,550 E cando finalmente sexa, inserir a nome que orixinalmente planificado 779 00:33:17,550 --> 00:33:19,370 noutro lugar naquel local. 780 00:33:19,370 --> 00:33:23,360 Pero, no peor dos casos, o único punto pode ser a parte inferior dos datos 781 00:33:23,360 --> 00:33:25,090 estrutura, a fin do array. 782 00:33:25,090 --> 00:33:30,130 >> Entón lineal enquisa, no peor caso, transforma nun algoritmo lineal en que 783 00:33:30,130 --> 00:33:34,500 Arão, se el pasa a ser inserido último neste tipo de estrutura de datos, pode 784 00:33:34,500 --> 00:33:39,540 chocar con esta primeira posición, pero despois acaban por mala sorte na final. 785 00:33:39,540 --> 00:33:43,940 Polo tanto, esta non é unha constante tempo Santo Graal para nós. 786 00:33:43,940 --> 00:33:47,650 Esta visión para a inserción de elementos unha estrutura de datos, chamado de hash 787 00:33:47,650 --> 00:33:52,050 táboa non parecen ser de tempo constante polo menos, no caso xeral. 788 00:33:52,050 --> 00:33:54,000 Pode transformarse en algo lineal. 789 00:33:54,000 --> 00:33:56,970 >> Entón, o que se resolver conflitos un pouco diferente? 790 00:33:56,970 --> 00:34:00,740 Entón aquí vai un máis sofisticado visión para o que é aínda 791 00:34:00,740 --> 00:34:02,800 chamada de táboa de hash. 792 00:34:02,800 --> 00:34:05,890 E, de hash, como un aparte, o que Quero dicir, é o índice que 793 00:34:05,890 --> 00:34:07,070 Me referín anteriormente. 794 00:34:07,070 --> 00:34:09,810 Para hash de algo pode ser pensada como un verbo. 795 00:34:09,810 --> 00:34:13,690 >> Entón, se haxix Alicia é un nome, unha función de hash, por así dicir, 796 00:34:13,690 --> 00:34:14,710 debe devolver un número. 797 00:34:14,710 --> 00:34:18,199 Neste caso será cero a ela pertence localización cero, un, se pertence a 798 00:34:18,199 --> 00:34:20,000 un lugar, e así por diante. 799 00:34:20,000 --> 00:34:24,360 Así, a miña función de hash, ata agora, foi super sinxelo, só mirando para o 800 00:34:24,360 --> 00:34:26,159 primeira letra do nome de alguén. 801 00:34:26,159 --> 00:34:29,090 Pero unha función hash ten como entrada de algún anaco de datos, un 802 00:34:29,090 --> 00:34:30,210 cadea, un int, o que quere. 803 00:34:30,210 --> 00:34:32,239 E el cospe tipicamente un número. 804 00:34:32,239 --> 00:34:35,739 E ese número é o lugar onde os datos elemento pertence a unha estrutura de datos 805 00:34:35,739 --> 00:34:37,800 coñecido aquí como unha táboa hash. 806 00:34:37,800 --> 00:34:41,400 >> Entón, só intuitivamente, esta é unha contexto lixeiramente diferente. 807 00:34:41,400 --> 00:34:44,170 Isto, en realidade estase referindo a un exemplo inclúen aniversarios, cando 808 00:34:44,170 --> 00:34:46,850 pode haber tantos como 31 días no mes. 809 00:34:46,850 --> 00:34:52,239 Pero o que a persoa decide facer en caso dunha colisión? 810 00:34:52,239 --> 00:34:55,304 Contexto agora a ser, non unha colisión de nomes, pero unha colisión de aniversarios, 811 00:34:55,304 --> 00:35:00,760 se dúas persoas teñen a mesma data de aniversario o a 02 de outubro, por exemplo. 812 00:35:00,760 --> 00:35:02,120 >> Estudante: [inaudível]. 813 00:35:02,120 --> 00:35:05,010 >> COLUMNA 1: Si, polo que temos aquí a alavancagem de listas ligadas. 814 00:35:05,010 --> 00:35:07,830 Polo tanto, parece un pouco diferente do que chamou máis cedo. 815 00:35:07,830 --> 00:35:10,790 Pero parece que unha matriz na parte esquerda. 816 00:35:10,790 --> 00:35:13,230 Este é un índice, pois ningunha razón particular. 817 00:35:13,230 --> 00:35:14,630 Senón que é un array. 818 00:35:14,630 --> 00:35:16,160 É unha matriz de punteiros. 819 00:35:16,160 --> 00:35:20,670 E cada un deses elementos, cada un de eses círculos ou barras - a barra 820 00:35:20,670 --> 00:35:23,970 representando nula - cada unha delas punteiros é aparentemente apunta a 821 00:35:23,970 --> 00:35:25,730 que a estrutura de datos? 822 00:35:25,730 --> 00:35:26,890 Unha lista ligada. 823 00:35:26,890 --> 00:35:30,530 >> Polo tanto, agora temos a capacidade de codificar no noso programa 824 00:35:30,530 --> 00:35:32,010 o tamaño da táboa. 825 00:35:32,010 --> 00:35:35,360 Neste caso, sabemos que nunca hai máis de 31 días nun mes. 826 00:35:35,360 --> 00:35:38,480 Tan difícil codificación dun valor como 31 é razoable nese contexto. 827 00:35:38,480 --> 00:35:42,700 No contexto de nomes, codificación dura 26 non é razoable que a xente 828 00:35:42,700 --> 00:35:46,340 nomes comezan só con, por exemplo, alfabeto da a Z. inclúen 829 00:35:46,340 --> 00:35:50,180 >> Podemos meter-los todos en que os datos estrutura, sempre que, cando temos un 830 00:35:50,180 --> 00:35:55,330 colisión, non poñer os nomes aquí, no canto de pensar que esas células 831 00:35:55,330 --> 00:36:00,270 como non propias cordas, pero como punteiros para, por exemplo, Alice. 832 00:36:00,270 --> 00:36:03,660 E entón Alicia pode ter outro punteiro a outro nome comezando con 833 00:36:03,660 --> 00:36:06,150 A. E Bob realmente pasa por aquí. 834 00:36:06,150 --> 00:36:10,850 >> E se hai outro nome que comeza con B, el acaba por aquí. 835 00:36:10,850 --> 00:36:15,070 E así, cada un dos elementos do presente mesa de dous, se nos proxectos este un 836 00:36:15,070 --> 00:36:17,350 pouco máis intelixente - 837 00:36:17,350 --> 00:36:18,125 Imos - 838 00:36:18,125 --> 00:36:22,950 se nos proxectos este un pouco máis intelixentemente, torna-se agora un conxunto de datos de adaptación 839 00:36:22,950 --> 00:36:27,720 estrutura, onde non hai límite duro en cantos elementos pode introducir 840 00:36:27,720 --> 00:36:30,700 para el, xa que se ten unha colisión, iso é bo. 841 00:36:30,700 --> 00:36:34,690 Só tes que ir adiante e anexo-lo ao o que vimos un pouco atrás era 842 00:36:34,690 --> 00:36:38,290 coñecido como unha lista ligada. 843 00:36:38,290 --> 00:36:39,690 >> Ben, imos deixar por un momento. 844 00:36:39,690 --> 00:36:42,570 Cal é a probabilidade dunha colisión en primeiro lugar? 845 00:36:42,570 --> 00:36:45,480 Seguro, quizais eu estou máis a pensar, se cadra Estou sobre enxeñaría este problema, 846 00:36:45,480 --> 00:36:46,370 porque vostede sabe o que? 847 00:36:46,370 --> 00:36:49,070 Si, podo vir enriba con arbitrario exemplos enriba da miña cabeza, como 848 00:36:49,070 --> 00:36:52,870 Allison e Aaron, pero, en realidade, dada unha distribución uniforme do 849 00:36:52,870 --> 00:36:56,990 insumos, ou sexa unhas insercións aleatorias nunha estrutura de datos, o que é realmente 850 00:36:56,990 --> 00:36:58,580 a probabilidade dunha colisión? 851 00:36:58,580 --> 00:37:01,670 Ben ve, é realmente super alta. 852 00:37:01,670 --> 00:37:03,850 Déixeme xeneralizar este este problema é como. 853 00:37:03,850 --> 00:37:08,890 >> Así, nunha sala de n CS50 estudantes, o que é a probabilidade de que polo menos 854 00:37:08,890 --> 00:37:11,010 dous alumnos na sala teñen a mesma data de aniversario? 855 00:37:11,010 --> 00:37:13,346 Polo tanto, non hai o que. algúns Hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 persoas aquí e varios centos de persoas na casa hoxe. 857 00:37:16,790 --> 00:37:20,670 Entón, se quería preguntar a nós mesmos o que é a probabilidade de que dúas persoas 858 00:37:20,670 --> 00:37:23,930 nesta sala que ten o mesmo aniversario, podemos descubrir iso. 859 00:37:23,930 --> 00:37:26,250 E eu afirmo en realidade, hai dous persoas co mesmo aniversario. 860 00:37:26,250 --> 00:37:29,560 >> Por exemplo, alguén ten aniversario hoxe? 861 00:37:29,560 --> 00:37:31,340 Onte? 862 00:37:31,340 --> 00:37:32,590 Mañá? 863 00:37:32,590 --> 00:37:35,980 Todo ben, entón parece que vou ter que facer isto máis ou menos 363 864 00:37:35,980 --> 00:37:39,500 veces para realmente descubrir o se temos unha colisión. 865 00:37:39,500 --> 00:37:42,350 Ou podemos facelo matemáticamente ao contrario de tediosamente 866 00:37:42,350 --> 00:37:43,200 facelo. 867 00:37:43,200 --> 00:37:44,500 E propoñer o seguinte. 868 00:37:44,500 --> 00:37:48,740 >> Así, propoño que podería modelar o probabilidade de dúas persoas que teñen a 869 00:37:48,740 --> 00:37:55,320 mesma data de aniversario como a probabilidade dun menos a probabilidade de non ter un 870 00:37:55,320 --> 00:37:56,290 aniversario o mesmo día. 871 00:37:56,290 --> 00:37:59,960 Entón, para conseguir isto, e este é só o xeito elegante de escribir isto, ao 872 00:37:59,960 --> 00:38:03,090 primeira persoa na sala, el ou ela pode ter calquera dos posibles 873 00:38:03,090 --> 00:38:07,370 aniversarios asumindo 365 días o ano, con perdón ás persoas con 874 00:38:07,370 --> 00:38:08,760 o 29 º aniversario de febreiro. 875 00:38:08,760 --> 00:38:13,470 >> Así, a primeira persoa nesta sala é libre ter calquera número de aniversarios 876 00:38:13,470 --> 00:38:18,280 fóra das 365 posibilidades para que imos facer que 365 dividido por 365, 877 00:38:18,280 --> 00:38:18,990 , Que é un. 878 00:38:18,990 --> 00:38:22,700 A seguinte persoa na sala, se o obxectivo é evitar unha colisión, só pode 879 00:38:22,700 --> 00:38:26,460 ter o seu aniversario en como distintos días posibles? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Así, o segundo termo da expresión é esta esencialmente, facendo que a matemática para nós 882 00:38:31,430 --> 00:38:33,460 subtraindo-se fóra dun día posible. 883 00:38:33,460 --> 00:38:36,390 E despois, o día seguinte, o día seguinte, o día seguinte ata o número total 884 00:38:36,390 --> 00:38:38,100 de persoas na sala. 885 00:38:38,100 --> 00:38:41,290 >> E se entón considerar, cal é entón a probabilidade de non ter todo 886 00:38:41,290 --> 00:38:45,265 aniversarios únicas, pero de novo un menos que, o que temos é unha expresión 887 00:38:45,265 --> 00:38:47,810 que pode moi fantasiosamente semellante a esta. 888 00:38:47,810 --> 00:38:50,330 Pero é máis interesante ollar visualmente. 889 00:38:50,330 --> 00:38:55,120 Este é un gráfico no que o eixo x é o número de persoas na sala, o 890 00:38:55,120 --> 00:38:56,180 número de aniversarios. 891 00:38:56,180 --> 00:38:59,840 No eixe y representa a probabilidade dunha colisión, dúas persoas 892 00:38:59,840 --> 00:39:01,230 tendo o mesmo aniversario. 893 00:39:01,230 --> 00:39:05,020 >> E o takeaway dende esta curva é que, así que comeza a gustar 40 894 00:39:05,020 --> 00:39:11,110 estudantes, estase a unha probabilidade do 90% combinatorically de dous 895 00:39:11,110 --> 00:39:13,550 ou máis persoas que teñen aniversario o mesmo día. 896 00:39:13,550 --> 00:39:18,600 E unha vez que comeza a gustar de 58 persoas é preto de 100% de unha posibilidade ambos 897 00:39:18,600 --> 00:39:21,310 persoas na sala terá o mesma data de aniversario, aínda que non haxa 898 00:39:21,310 --> 00:39:26,650 365 ou 366 posibles baldes e só 58 persoas na sala. 899 00:39:26,650 --> 00:39:29,900 Só estatisticamente é probable que obter colisións, o que en definitiva 900 00:39:29,900 --> 00:39:31,810 motiva este fío. 901 00:39:31,810 --> 00:39:35,890 Que, aínda que comezar a fantasía aquí, e comezar a ter esas cadeas, aínda estamos 902 00:39:35,890 --> 00:39:36,950 terá colisións. 903 00:39:36,950 --> 00:39:42,710 >> Así que levanta a cuestión: o que é o custo de facer insercións e borrados 904 00:39:42,710 --> 00:39:44,850 nunha estrutura de datos como este? 905 00:39:44,850 --> 00:39:46,630 Ben, deixe-me propor - 906 00:39:46,630 --> 00:39:51,570 e déixeme volver á pantalla sobre aquí - se temos n elementos no 907 00:39:51,570 --> 00:39:56,330 lista, polo que, se estamos tentando introducir n elementos e temos 908 00:39:56,330 --> 00:39:58,050 cantos total de baldes? 909 00:39:58,050 --> 00:40:03,450 Digamos que 31 baldes totais no caso de aniversario. 910 00:40:03,450 --> 00:40:09,240 Cal é a lonxitude máxima dun destas cadeas potencialmente? 911 00:40:09,240 --> 00:40:12,670 >> Novamente non se pode 31 aniversarios en un mes. 912 00:40:12,670 --> 00:40:14,580 E estamos só a aglutinación todos - 913 00:40:14,580 --> 00:40:15,580 en realidade, iso é un exemplo parvo. 914 00:40:15,580 --> 00:40:16,960 Imos facer 26 en vez. 915 00:40:16,960 --> 00:40:20,890 Entón, se realmente ten persoas cuxos nomes comezar a Z, dando así 916 00:40:20,890 --> 00:40:22,780 nos 26 posibilidades. 917 00:40:22,780 --> 00:40:25,920 E nós estamos a usar unha estrutura de datos como o que acabamos de ver, en que temos 918 00:40:25,920 --> 00:40:30,210 unha matriz de puntos, cada un dos cales apunta a unha lista ligada, onde a 919 00:40:30,210 --> 00:40:32,360 primeira lista é de todos co nome de Alice. 920 00:40:32,360 --> 00:40:35,770 A segunda lista é cada un co nome comezar coa, comezando 921 00:40:35,770 --> 00:40:36,980 con B, e así por diante. 922 00:40:36,980 --> 00:40:41,020 >> Cal é a duración probable de cada un dos estas listas se asumirmos unha boa limpo 923 00:40:41,020 --> 00:40:45,410 distribución de nomes da a Z a través da estrutura de datos enteiro? 924 00:40:45,410 --> 00:40:50,210 Hai n persoas na estrutura de datos dividido por 26, se son ben 925 00:40:50,210 --> 00:40:52,110 espallados por todo o estrutura de datos. 926 00:40:52,110 --> 00:40:54,970 Así, a lonxitude de cada un destes cadeas é n dividido por 26. 927 00:40:54,970 --> 00:40:57,380 Pero na notación O gran, o que é iso? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 ¿Que é iso mesmo? 930 00:41:02,440 --> 00:41:04,150 Entón, é realmente só n, non? 931 00:41:04,150 --> 00:41:06,620 Porque xa dixen no pasado, Ugh que dividir por 26. 932 00:41:06,620 --> 00:41:08,710 Si, en realidade é máis rápido. 933 00:41:08,710 --> 00:41:12,720 Pero, en teoría, non é fundamentalmente todo o que máis rápido. 934 00:41:12,720 --> 00:41:16,040 >> Polo tanto, non parece ser todo o que moito máis próximo a este Santo Graal. 935 00:41:16,040 --> 00:41:17,750 En realidade, este é só o tempo lineal. 936 00:41:17,750 --> 00:41:20,790 Heck, neste punto, por que non nós non necesitará empregar unha lista ligada enorme? 937 00:41:20,790 --> 00:41:23,510 Por que non usar só un enorme matriz para almacenar os nomes das 938 00:41:23,510 --> 00:41:25,010 todos na sala? 939 00:41:25,010 --> 00:41:28,280 Ben, aínda hai algo convincente sobre unha táboa hash? 940 00:41:28,280 --> 00:41:30,810 Hai aínda algo atractivo sobre unha estrutura de datos 941 00:41:30,810 --> 00:41:33,940 que se parece con isto? 942 00:41:33,940 --> 00:41:35,182 Este. 943 00:41:35,182 --> 00:41:37,050 >> Estudante: [inaudível]. 944 00:41:37,050 --> 00:41:39,840 >> COLUMNA 1: Correcto, e, de novo, se non é máis un algoritmo de tempo lineal, e un 945 00:41:39,840 --> 00:41:42,780 estrutura de datos en tempo lineal, por que non me só almacenar o nome de todos nun gran 946 00:41:42,780 --> 00:41:44,210 matriz, ou nunha lista vinculada grande? 947 00:41:44,210 --> 00:41:47,010 E deixar de facer CS moito máis difícil do que debe ser? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 O que é interesante sobre iso, aínda aínda que rabuñou-lo? 950 00:41:53,190 --> 00:41:54,930 >> Estudante: [inaudível]. 951 00:41:54,930 --> 00:41:57,040 >> COLUMNA 1: As insercións non son? 952 00:41:57,040 --> 00:41:58,140 Expensive máis. 953 00:41:58,140 --> 00:42:03,390 Entón insercións potencialmente podería aínda ser de tempo constante, aínda que os seus datos 954 00:42:03,390 --> 00:42:07,910 estrutura parécese tanto, unha serie de enlaces, cada un dos cales está a apuntar 955 00:42:07,910 --> 00:42:09,550 potencialmente unha lista encadeada. 956 00:42:09,550 --> 00:42:15,220 Como podería conseguir constante inserción canto de nomes de? 957 00:42:15,220 --> 00:42:16,280 Cole-o na fronte, non? 958 00:42:16,280 --> 00:42:19,290 >> Sacrificarse un obxectivo do proxecto de anteriormente, onde queriamos manter 959 00:42:19,290 --> 00:42:22,650 nome de todos, por exemplo, clasificadas ou todos os números en fase clasificados, 960 00:42:22,650 --> 00:42:25,020 supoñer que temos un lista ligada indiferenciados. 961 00:42:25,020 --> 00:42:29,960 El só nos custa un ou dous pasos, como no caso de Ben e Brian 962 00:42:29,960 --> 00:42:32,750 anteriormente, para introducir un elemento en o inicio da lista. 963 00:42:32,750 --> 00:42:36,090 Entón, se non nos importa sobre a clasificación todo dos nomes comezan con un ou todos 964 00:42:36,090 --> 00:42:39,660 os nomes que comezan con B, aínda podemos acadar a inserción de tempo constante. 965 00:42:39,660 --> 00:42:43,900 Agora, ollando para Alicia ou Bob ou calquera nome máis xeral aínda o que é? 966 00:42:43,900 --> 00:42:48,100 É grande o de n dividido por 26, o caso ideal onde todo o mundo é uniforme 967 00:42:48,100 --> 00:42:51,190 distribuídos onde hai o maior número dun xa que hai de Z, o cal pode ser 968 00:42:51,190 --> 00:42:52,220 irrealista. 969 00:42:52,220 --> 00:42:53,880 Pero iso aínda é lineal. 970 00:42:53,880 --> 00:42:57,120 >> Pero aquí, volvemos ao punto de notación asintótica ser 971 00:42:57,120 --> 00:42:58,600 en teoría verdade. 972 00:42:58,600 --> 00:43:02,960 Pero no mundo real, se eu afirmar que meu programa pode facer algo 26 veces 973 00:43:02,960 --> 00:43:06,210 máis rápido que o seu, cuxo programa vai preferir usar? 974 00:43:06,210 --> 00:43:09,660 Seu ou meu, que é 26 veces máis rápido? 975 00:43:09,660 --> 00:43:14,320 Realista, a persoa de quen é 26 veces máis rápido, aínda que teoricamente 976 00:43:14,320 --> 00:43:18,790 nosos algoritmos son executados no mesmo asintótica tempo de carreira. 977 00:43:18,790 --> 00:43:20,940 >> Deixe me propoñer unha diferente solución completamente. 978 00:43:20,940 --> 00:43:24,380 E se isto non explotar a súa mente, estamos fóra de estruturas de datos. 979 00:43:24,380 --> 00:43:27,420 Polo tanto, esta é unha trie - 980 00:43:27,420 --> 00:43:28,520 tipo de un nome estúpido. 981 00:43:28,520 --> 00:43:32,880 Provén de recuperacións, ea palabra está escrito trie, t-r-i-e, por mor de 982 00:43:32,880 --> 00:43:34,450 recuperación curso soa como trie. 983 00:43:34,450 --> 00:43:36,580 Pero esta é a historia da palabra trie. 984 00:43:36,580 --> 00:43:40,980 >> Así, unha trie é de feito unha especie de árbore, e tamén é unha brincadeira coa palabra. 985 00:43:40,980 --> 00:43:46,330 E aínda que non pode velo con esta visualización, un trie é un 986 00:43:46,330 --> 00:43:50,790 árbore estructurada, como unha árbore xenealóxica con un antepasado na parte superior e moi 987 00:43:50,790 --> 00:43:54,530 de netos e bisnetos como follas na parte inferior. 988 00:43:54,530 --> 00:43:58,100 Pero cada nodo nun trie é unha matriz. 989 00:43:58,100 --> 00:44:00,680 E é nunha matriz - e imos simplificar por un momento - é unha 990 00:44:00,680 --> 00:44:04,600 matriz, neste caso, de tamaño 26, onde cada nó é de novo unha matriz de tamaño 991 00:44:04,600 --> 00:44:09,000 26, onde o elemento de orde cero, no que Unha matriz representa, ea última 992 00:44:09,000 --> 00:44:11,810 en cada elemento de tal array representa Z. 993 00:44:11,810 --> 00:44:15,520 >> Así, propoño, entón, que estes datos estrutura, coñecida como unha trie, se pode 994 00:44:15,520 --> 00:44:17,600 tamén utilizada para almacenar palabras. 995 00:44:17,600 --> 00:44:21,740 Vimos hai pouco como poderiamos almacenar palabras, ou neste caso os nomes, e nós 996 00:44:21,740 --> 00:44:25,440 vimos como podemos almacenar números, pero concentrarse en nomes ou secuencias 997 00:44:25,440 --> 00:44:27,460 aquí, entender o que é interesante. 998 00:44:27,460 --> 00:44:32,210 Eu afirmo que o nome é Maxwell dentro desta estrutura de datos. 999 00:44:32,210 --> 00:44:33,730 Onde se ve Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> Estudante: [inaudível]. 1001 00:44:35,140 --> 00:44:36,240 >> COLUMNA 1: Á esquerda. 1002 00:44:36,240 --> 00:44:39,910 Entón, o que é interesante con estes datos estrutura é, en vez de almacenar o 1003 00:44:39,910 --> 00:44:46,200 corda M-A-X-W-E-L-L invertida cero, todo contigua, o que facer en vez 1004 00:44:46,200 --> 00:44:46,890 está seguindo. 1005 00:44:46,890 --> 00:44:50,510 Se esta é unha estrutura de datos como trie, cada un dos nós cuxas é de novo unha matriz, 1006 00:44:50,510 --> 00:44:54,650 e quere almacenar Maxwell, primeiro índice e así nó da raíz, de xeito 1007 00:44:54,650 --> 00:44:57,810 dicir, o nodo superior, na posición M, certo, entón 1008 00:44:57,810 --> 00:44:59,160 aproximadamente no medio. 1009 00:44:59,160 --> 00:45:03,740 E, a continuación, a partir de aí, seguir unha punteiro para un neno nós, por así dicir. 1010 00:45:03,740 --> 00:45:06,150 Así, no sentido de árbore xenealóxica, vostede segui-lo para abaixo. 1011 00:45:06,150 --> 00:45:09,030 E que leva-lo a outro nodo Á esquerda, que é 1012 00:45:09,030 --> 00:45:10,540 só outra matriz. 1013 00:45:10,540 --> 00:45:14,710 >> E entón se quere gardar Maxwell, atopar o punteiro que representa 1014 00:45:14,710 --> 00:45:16,430 A, que é este aquí. 1015 00:45:16,430 --> 00:45:17,840 Entón vai ao seguinte nodo. 1016 00:45:17,840 --> 00:45:20,100 E teña en conta - é por iso que a imaxe do un pouco erro - 1017 00:45:20,100 --> 00:45:21,990 este nodo ollar super pequeno. 1018 00:45:21,990 --> 00:45:26,050 Pero á dereita deste é Y e Z. É só o autor ten truncado o 1019 00:45:26,050 --> 00:45:27,630 imaxe de xeito que realmente ver as cousas. 1020 00:45:27,630 --> 00:45:30,400 En caso contrario, esta imaxe sería moi grande. 1021 00:45:30,400 --> 00:45:36,180 Entón, agora índice para localización X, entón W, E, a continuación, L, entón L. Entón cal é 1022 00:45:36,180 --> 00:45:37,380 esa curiosidade? 1023 00:45:37,380 --> 00:45:41,250 >> Ben, se estamos a usar este tipo de nova asumir a forma de almacenar unha cadea nun 1024 00:45:41,250 --> 00:45:44,500 estrutura de datos, aínda que esencialmente marcar nos datos 1025 00:45:44,500 --> 00:45:47,250 estructura de que unha palabra remata aquí. 1026 00:45:47,250 --> 00:45:50,830 Noutras palabras, cada un destes nós dalgún xeito ten que lembrar que 1027 00:45:50,830 --> 00:45:53,500 en realidade, seguido todos estes punteiros e están deixando un pouco 1028 00:45:53,500 --> 00:45:58,370 migas de pan no fondo aquí deste estrutura para indicar M-A-X-W-E-L-L é 1029 00:45:58,370 --> 00:46:00,230 de feito nesta estrutura de datos. 1030 00:46:00,230 --> 00:46:02,040 >> Así, poderiamos facelo do seguinte xeito. 1031 00:46:02,040 --> 00:46:06,810 Cada un dos nós na imaxe que acabamos de ten unha serra, unha matriz de tamaño 27. 1032 00:46:06,810 --> 00:46:10,550 E agora é 27 porque, p definir seis anos, imos realmente darlle unha apóstrofe, 1033 00:46:10,550 --> 00:46:13,590 así podemos ter nomes como O'Reilly e outros con apóstrofos. 1034 00:46:13,590 --> 00:46:14,820 Pero a mesma idea. 1035 00:46:14,820 --> 00:46:17,710 Cada un destes elementos no puntos de matriz para unha struct 1036 00:46:17,710 --> 00:46:19,320 no, entón só un nó. 1037 00:46:19,320 --> 00:46:21,430 Entón iso é moi recorda da nosa lista encadeada. 1038 00:46:21,430 --> 00:46:24,550 >> E entón eu teño un valor booleano, que vou chamar palabra, que só será 1039 00:46:24,550 --> 00:46:29,120 certo se a palabra remata neste nodo da árbore. 1040 00:46:29,120 --> 00:46:32,870 El representa efectivamente poucos triángulo que vimos hai pouco. 1041 00:46:32,870 --> 00:46:37,190 Así, se unha palabra que remata no nó no árbore, aquel campo palabra será verdadeira, 1042 00:46:37,190 --> 00:46:41,990 que é conceptualmente a comprobación off, ou estamos deseñando ese triángulo, si, hai 1043 00:46:41,990 --> 00:46:44,080 é unha palabra aquí. 1044 00:46:44,080 --> 00:46:45,120 >> Polo tanto, esta é unha trie. 1045 00:46:45,120 --> 00:46:48,540 E agora a pregunta é, o que é o seu tempo de execución? 1046 00:46:48,540 --> 00:46:49,930 É grande o de n? 1047 00:46:49,930 --> 00:46:51,410 É algo máis? 1048 00:46:51,410 --> 00:46:57,330 Ben, se ten n nomes nestes datos estrutura, Maxwell sendo só un 1049 00:46:57,330 --> 00:47:02,330 los, o que é o tempo de execución inserción ou atopar Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Cal é o tempo de execución inserción de Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Se hai n outros nomes xa enriba da mesa? 1053 00:47:11,740 --> 00:47:12,507 Si? 1054 00:47:12,507 --> 00:47:15,429 >> Estudante: [inaudível]. 1055 00:47:15,429 --> 00:47:17,550 >> COLUMNA 1: Si, é a lonxitude do nome, non? 1056 00:47:17,550 --> 00:47:24,420 Entón M-a-x-w-e-l-l polo que se sente así O algoritmo é grande de sete. 1057 00:47:24,420 --> 00:47:26,580 Agora, obviamente, o nome pode variar en lonxitude. 1058 00:47:26,580 --> 00:47:27,380 Quizais sexa un nome curto. 1059 00:47:27,380 --> 00:47:28,600 Quizais sexa un nome máis longo. 1060 00:47:28,600 --> 00:47:33,390 Pero o que é importante aquí é que é un número constante. 1061 00:47:33,390 --> 00:47:36,810 E quizais non sexa realmente constante, Pero Deus, si realista, nun 1062 00:47:36,810 --> 00:47:41,570 dicionario, probabelmente hai algún límite sobre o número de letras dunha 1063 00:47:41,570 --> 00:47:43,820 o nome da persoa nun determinado país. 1064 00:47:43,820 --> 00:47:46,940 >> E así, podemos supoñer que é un valor constante. 1065 00:47:46,940 --> 00:47:47,750 Non sei o que é. 1066 00:47:47,750 --> 00:47:50,440 É, probablemente, maior que pensamos que é. 1067 00:47:50,440 --> 00:47:52,720 Porque sempre hai algún recuncho caso cun nome moi tolo. 1068 00:47:52,720 --> 00:47:56,360 Entón, imos chamalo de k, senón que é un constante, presumiblemente, que cada 1069 00:47:56,360 --> 00:48:00,190 nome no mundo, polo menos nun determinado país, é que a lonxitude ou 1070 00:48:00,190 --> 00:48:01,780 máis curto, polo que é constante. 1071 00:48:01,780 --> 00:48:04,490 Pero cando dixemos algo é grande O dun valor constante, o que é iso 1072 00:48:04,490 --> 00:48:07,760 realmente equivalente a? 1073 00:48:07,760 --> 00:48:10,420 Esta é realmente o mesmo que dicir de tempo constante. 1074 00:48:10,420 --> 00:48:11,530 >> Agora somos o tipo de trapaça, non? 1075 00:48:11,530 --> 00:48:15,340 Estamos medio alavancar algunha teoría aquí para dicir que o ben, a fin de k é 1076 00:48:15,340 --> 00:48:17,450 realmente só encargar dun, e é tempo constante. 1077 00:48:17,450 --> 00:48:18,200 Pero realmente é. 1078 00:48:18,200 --> 00:48:22,550 Porque o insight clave aquí é que si temos n nomes xa neste 1079 00:48:22,550 --> 00:48:26,010 estrutura de datos, e inserción Maxwell é a cantidade de tempo que nos leva a 1080 00:48:26,010 --> 00:48:29,530 introducir Maxwell en todos os afectados por cantas outras persoas 1081 00:48:29,530 --> 00:48:31,100 están dentro da estrutura de datos? 1082 00:48:31,100 --> 00:48:31,670 Non parece ser. 1083 00:48:31,670 --> 00:48:36,280 Se eu tivese un bilhão de máis elementos para esta trie, e entón introduza Maxwell, é 1084 00:48:36,280 --> 00:48:38,650 el en todos os afectados? 1085 00:48:38,650 --> 00:48:39,050 Non 1086 00:48:39,050 --> 00:48:42,950 E iso é distinto de calquera dos datos do día estruturas que vimos ata agora, onde 1087 00:48:42,950 --> 00:48:46,820 o tempo de execución do algoritmo é totalmente independente de canto 1088 00:48:46,820 --> 00:48:51,430 material é ou non é xa en que a estrutura de datos. 1089 00:48:51,430 --> 00:48:54,650 >> E así, con esta proporciónalle agora é un oportunidade para p conxunto de seis, que será 1090 00:48:54,650 --> 00:48:58,310 novo involucrar aplicar o seu propio corrector ortográfico, a lectura en 150 mil 1091 00:48:58,310 --> 00:49:01,050 palabras, o mellor xeito de gardar este non é necesariamente evidente. 1092 00:49:01,050 --> 00:49:04,030 E aínda que eu aspiraba a atopar o Santo Graal, eu non 1093 00:49:04,030 --> 00:49:05,330 afirman que unha trie é. 1094 00:49:05,330 --> 00:49:09,810 De feito, unha táboa hash pode moi ben probar ser moito máis eficiente. 1095 00:49:09,810 --> 00:49:10,830 Pero estes son só - 1096 00:49:10,830 --> 00:49:14,620 iso é só unha das decisións de proxecto terá que facer. 1097 00:49:14,620 --> 00:49:18,920 >> Pero no peche teremos 50 ou máis segundos para dar un ollo ao que está 1098 00:49:18,920 --> 00:49:22,190 fronte a próxima semana e que a transición ademais dende esta liña de comandos 1099 00:49:22,190 --> 00:49:26,220 mundo, programas en C para as cousas web base e linguaxes como PHP e 1100 00:49:26,220 --> 00:49:30,350 Javascript e da propia Internet, protocolos como HTTP, o que 1101 00:49:30,350 --> 00:49:32,870 tida como certa por moitos anos agora, e escribiu a maioría cada 1102 00:49:32,870 --> 00:49:34,440 día, quizais, ou ver. 1103 00:49:34,440 --> 00:49:37,420 E imos comezar a pelar a capas de cal é a Internet. 1104 00:49:37,420 --> 00:49:40,650 E cal é o código que subxacente ferramentas de hoxe. 1105 00:49:40,650 --> 00:49:43,230 Entón 50 segundos este teaser aquí. 1106 00:49:43,230 --> 00:49:46,570 Eu darlle guerreiros da rede. 1107 00:49:46,570 --> 00:49:51,370 >> [REPRODUCIÓN] 1108 00:49:51,370 --> 00:49:56,764 >> -El veu cunha mensaxe. 1109 00:49:56,764 --> 00:50:00,687 Cun protocolo de todos os seus propios. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Chegou a un mundo de firewalls crueis, routers indiferente, e os perigos lonxe 1112 00:50:19,780 --> 00:50:22,600 peor que a morte. 1113 00:50:22,600 --> 00:50:23,590 El é rápido. 1114 00:50:23,590 --> 00:50:25,300 El é forte. 1115 00:50:25,300 --> 00:50:27,700 El é TCPIP. 1116 00:50:27,700 --> 00:50:30,420 E el ten o seu enderezo. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Guerreiros da rede. 1119 00:50:34,590 --> 00:50:35,290 >> [FIN reprodución de vídeo] 1120 00:50:35,290 --> 00:50:38,070 >> COLUMNA 1: É así que a Internet debe traballar desde a próxima semana. 1121 00:50:38,070 --> 00:50:40,406