Doug LLOYD: Entón, en CS50, nós Cubrimos un gran número de diferentes estruturas de datos, non? Vimos arrays, e ligados listas e táboas de hash, e tenta, pilas e colas. Tamén imos aprender un pouco sobre árbores e montes, pero realmente todos estes acabar sendo variacións sobre un tema. Hai realmente estes tipo de catro ideas básicas que o resto pode ferver para abaixo. Arrays, listas ligadas, táboas de hash, e intenta. E como dixen, hai son variacións sobre eles, pero iso é moi moi indo para resumir todo o que vai falar Sobre esta clase en termos de C. Pero como estes todos medida, non? Nós falamos sobre os pros e contras de cada un en vídeos separados sobre eles, pero hai unha morea de números sendo xogado en torno. Hai unha morea de xeral pensamentos ser xogado ao redor. Imos tentar e consolidar Lo en só un lugar. Imos pesar os pros contra os contra, e considere cal a estrutura de datos pode ser a datos dereita estrutura para a súa situación particular, calquera tipo de datos que está a garda. Non necesariamente ten sempre usar o super rápida inserción, borrado, e investigación dunha trie se realmente non se preocupan inserir e eliminar Demasiado. Se precisa só rapidamente aleatoria acceso, quizais unha matriz é mellor. Entón, imos destilar iso. Imos falar sobre cada un dos catro principais tipos de estruturas de datos que xa falamos sobre, e basta ver cando pode ser bo, e cando poden non ser tan bo. Entón imos comezar coa matrices. Entón inserción, que é tipo de malo. 

A inserción no extremo dunha matriz é OK, se estamos a construír unha matriz como imos nós. Pero se nós necesitamos introducir elementos no medio, creo que volta a inserción tipo, hai moito de desprazamento para axustar un elemento en alí. E por iso, se nós estamos indo a introducir calquera lugar, pero ao final dunha matriz, que probablemente non é tan grande. 

Do mesmo xeito, a exclusión, a non ser que sexamos exclusión dende o extremo dunha matriz, é, probablemente, tampouco tan grande se nós non queremos deixar lagoas baleiras, que normalmente non. Queremos eliminar un elemento, e a continuación, tipo de facelo cómodo de novo. E así a exclusión de elementos unha matriz, tampouco tan grande. 

Lookup, porén, é grande. Temos de acceso aleatorio, investigación de tempo constante. Nós só dicir sete, e nós imos a matriz deslocalización sete. Dicimos 20, coa go matriz deslocalización 20. Non temos para percorrer transversalmente. Iso é moi bo. 

Arrays tamén son relativamente fáciles de clasificar. Cada vez que falamos dunha selección algoritmo, como selección de tipo, tipo de inserción, bubble sort, merge tipo, sempre utilizado matrices para facelo, porque as matrices son moi fáciles de tipo, con respecto ás estruturas de datos vimos ata agora. 

Eles tamén son relativamente pequeno. Non hai unha morea de espazo extra. Só anular exactamente tanto como precisa para almacenar os seus datos, e iso é moi fermoso isto. Entón son moi pequenos e eficiente deste xeito. Pero outra desvantaxe, con todo, é que son de tamaño fixo. Debemos declarar exactamente como gran queremos que a nosa matriz para ser, e nós só temos unha oportunidade. Non podemos crecer e reduci-lo. 

Se necesitamos crecer ou encoller-lo, nós Debe declarar unha matriz enteiramente novo, copiar todos os elementos do primeira matriz para a segunda matriz. E se calculou mal que tempo, debemos facelo de novo. Non é tan boa. Entón matrices non nos dan a flexibilidade ter número variable de elementos. 

Cunha lista ligada, inserción é moi fácil. Nós só alinhavar para adiante. Eliminación tamén é moi doado. Temos que atopar os elementos. Que implica algunha investigación. 

Pero unha vez que teña atopado o elemento está a buscar, todo o que precisa facer é cambiar un punteiro, posiblemente dous, se ten unha ligada lista-- un dobre lista ligada, rather-- e entón pode só liberar o no. Non ten que cambiar todo ao seu redor. Acaba de cambiar dous punteiros, de xeito que é moi rápido. 

Lookup é malo, non? Co fin para nós atopar un elemento nunha lista ligada, illadamente ou dobremente conectado, temos a linear busca-lo. Temos que comezar a principios e move o fin, ou comezar a finais do movemento para o inicio. Non temos acceso aleatorio máis. Entón, se estamos facendo un moita investigación, quizais unha lista ligada non é tan bo para nós. 

Eles tamén son realmente difícil de resolver, non? O único xeito que poida realmente clasificar unha lista ligada é para clasificalos lo como construílo. Pero se clasificalos lo como constrúe-lo, non é máis facendo insercións rápidas anymore. Non está só alinhavando as cousas para adiante. Ten que atopar o punto axeitado para poñelas, e, a continuación, a súa inserción pasa a ser case tan malo como a inserción nunha matriz. Entón listas ligadas non son tan grande para clasificar os datos. 

Eles tamén son moi pequeno, tamaño-wise. Dobremente lista ligada lixeiramente maior que illadamente listas ligadas, que son lixeiramente maiores de matrices, pero non é unha enorme cantidade de espazo desperdiçado. Polo tanto, se o espazo é un premio, pero non un premio moi intenso, este pode ser o camiño certo a continuación. 

As táboas de hash. Inserción nunha táboa hash é moi sinxelo. É un proceso de dúas etapas. En primeiro lugar, necesitamos realizar nosas informacións a través unha función hash para obter un código de hash, e, despois, introduza o elemento para o táboa hash naquel lugar do código hash. 

Eliminación, semellante a lista ligada, é doado xa que atopa o elemento. Ten que atopalo primeiro, pero, a continuación, cando excluílo, só precisa cambiar un par de agullas, se está a usar o fío separado. Se está usando enquisa, ou se non está usando fío en todo na súa táboa de hash, eliminación é realmente moi fácil. Todo o que precisa facer é botar o datos, e logo ir a ese lugar. E no caso de que non facer ten colisións, vai ser capaz de borrar moi rapidamente. 

Agora, a investigación é onde as cousas estar un pouco máis complicado. Está na mellor media de listas ligadas. Se está usando o fío, aínda ten unha lista ligada, o que significa que aínda ten a Busca detrimento unha lista ligada. Senón porque está tomando o seu ligada lista e división lo máis de 100 ou 1000 ou n elementos na súa táboa de hash, é listas ligadas son todos un enésimo o tamaño. Son todos substancialmente menor. Vostede listas n ligada ao contrario dunha lista ligada de tamaño n. 

E así, este mundo real constante factor, que xeralmente non falar da complexidade en tempo, fai realmente facer a diferenza aquí. Así investigación aínda é lineal buscar se está a usar o fío, pero a lonxitude da lista Estás a ver a é moi, moi curto, por comparación. De novo, a clasificación é a súa obxectivo aquí, hash de táboa de probablemente non é o camiño certo a continuación. Só ten que usar unha matriz clasificar é realmente importante para ti. 

E poden realizar a gama de tamaño. É difícil dicir se unha táboa hash é pequeno ou grande, porque realmente depende de como gran súa táboa hash é. Se está indo só para estar almacenando cinco elementos na súa táboa hash, e ten unha táboa hash con 10.000 elementos nel, probablemente está perdendo unha gran cantidade de espazo. Contraste sendo tamén pode ten táboas de hash moi compactas, pero menor súa táboa hash queda, canto máis cada unha destas listas ligadas recibe. E así non hai realmente ningunha maneira de definir exactamente o tamaño dunha táboa hash, pero pode ser seguro dicir que é xeralmente vai ser maior que un conectado lista almacenar os mesmos datos, pero menor que un trie. 

E intentos son a cuarta destas estruturas que temos que chegou a falar. A inserción nunha trie é complexo. Hai unha morea de dinámica distribución de memoria, especialmente no inicio, como está empezando a construír. Pero é tempo constante. É só o elemento humano aquí que fai que sexa complicado. Ter que atopar punteiro nulo, malloc espazo, ir alí, o espazo posiblemente malloc a partir de aí de novo. O tipo de factor de intimidación de punteiros en distribución dinámica de memoria é o obstáculo para limpar. Pero unha vez que limpou-o, inserción en realidade vén moi sinxelo, e é sen dúbida tempo constante. 

A exclusión é doado. Todo o que precisa facer é navegar abaixo a par de agullas e libre o no, de xeito que é moi bo. Lookup tamén é moi rápido. É só con base na lonxitude dos seus datos. Polo tanto, se os seus datos é cinco cadeas de caracteres, por exemplo, está almacenando cinco cadeas de caracteres no seu trie, el só ten cinco pasos para atopar o que está a procurar. Cinco é só un factor constante, polo que de novo, inserción, exclusión e investigación aquí están todos os tempos constante, de forma eficaz. 

Outra cousa é que o seu trie é de feito, medio que xa clasificadas, non? En virtude de como estamos elementos Inserir, indo letra por letra do clave, ou díxito por díxito da chave, normalmente, o trie acaba sendo tipo de clasificadas como construílo. Realmente non fai sentido pensar en clasificación do mesmo xeito que pensamos sobre con matrices ou listas ligadas, ou táboas de hash. Pero, en certo sentido, o seu trie é clasificada como vai. 

A desvantaxe, claro, é que un trie rapidamente pasa a ser enorme. De todos os puntos de intersección, pode have-- súa chave está composta de díxitos, ten 10 outros lugares que pode ir, o que significa que cada nodo contén información sobre os datos que quere gardar no nodo que, ademais de 10 punteiros. Que, en CS50 IDE, é de 80 bytes. Entón, é, polo menos, 80 bytes para cada nodo que crear, e iso non o é contando datos. E se os seus nodos son letras en vez de díxitos, agora ten 26 punteiros de todos os lugares. E 26 veces 8 pode ser 200 bytes, ou algo parecido. E ten o capital e pode lowercase-- ver onde estou indo con iso, non? Seus nós pode ser moi gran, e así a trie Se, en xeral, pode estar realmente grande, demasiado. Polo tanto, se o espazo é alta premio no seu sistema, un trie pode non ser o camiño certo para ir, a pesar dos seus outros beneficios entran en xogo. Eu son Doug Lloyd. Este é CS50.