DOUG LLOYD: Així que en CS50, hem cobert un munt de diferents estructures de dades, Oi? Hem vist les matrius, i vinculats llistes i taules hash, i tries, piles i cues. També aprendrem una mica sobre els arbres i munts, però en realitat tots aquests simplement acaben sent fins variacions sobre un tema. Realment és això tipus de quatre idees bàsiques que tota la resta es redueixen a. Arrays, llistes enllaçades, taules hash i tries. I com he dit, no són variacions sobre ells, però això és bastant hi ha molt a fer per resumir tot el que anem a parlar sobre aquesta classe en termes de C. Però, ¿com fan aquests de tota mesura, no? Hem parlat sobre els pros i els contres de cada un en vídeos separats sobre ells, però hi ha un munt de nombres sent llançat voltant. Hi ha una gran quantitat de generals pensaments aconseguir llançats voltant. Anem a tractar de consolidar en un sol lloc. Anem a sospesar els pros contra els contres, i consideren que l'estructura de dades podrien ser les dades correctes estructura per a la seva situació particular, qualsevol tipus de dades que s'està emmagatzemant. No necessàriament sempre cal utilitzar la inserció super ràpid, eliminació, i la recerca d'un trie si realment no es preocupen per la inserció i eliminació massa. Si vostè necessita només ràpidament a l'atzar l'accés, pot ser que un arranjament és millor. Així que anem a destil·lar això. Anem a parlar de cada un dels quatre principals tipus d'estructures de dades que hem parlat, i simplement veure quan pot ser bo, i quan ells podrien no ser tan bo. Així que començarem amb les matrius. Així inserció, això és una cosa dolenta. 

La inserció en el final d'una matriu està bé, si estem construint un arsenal a mesura que avancem. Però si hem d'inserir elements en el medi, pensar de nou a la inserció espècie, hi ha molt de canviar per adaptar-se a un element en aquest país. I pel que si anem a inserir en qualsevol lloc, però el final d'una matriu, no crec que sigui tan gran. 

De la mateixa manera, la supressió, llevat que estiguem esborrar des del final d'una matriu, és probable que també no tan gran si no volem deixar espais buits, que en general no ho fem. Volem eliminar un element, i llavors espècie que sigui ajustat de nou. I així la supressió d'elements de una matriu, també no tan gran. 

Operacions de recerca, però, és gran. Tenim accés aleatori, recerca constant de temps. Acabem de dir 7, i ens anem a la reubicació sèrie de set. Diem 20, a la cita de reubicació sèrie 20. Nosaltres no hem de recórrer a través. Això és bastant bo. 

Les matrius també són relativament fàcils de resoldre. Cada vegada que parlem d'una classificació algoritme, com la selecció de gènere, ordenació per inserció, ordenament de bombolla, fusionar espècie, sempre fem servir matrius per fer-ho, perquè les matrius són bastant fàcils de espècie, amb relació a les estructures de dades que hem vist fins ara. 

També són relativament petites. No hi ha un munt d'espai extra. Vostè acaba de deixar de banda la mateixa mesura com sigui necessari per mantenir les seves dades, i això és pràcticament tot. Així que són bastant petites i eficient d'aquesta manera. Però un altre aspecte negatiu, però, és que estan fixos en grandària. Hem de declarar exactament com gran Volem que la nostra matriu a ser, i només tenim una oportunitat. No podem créixer i reduir la seva grandària. 

Si necessitem per créixer o encongir, ens hagi de declarar una matriu totalment nou, copiar tots els elements de la primera matriu en la segona matriu. I si calculem malament que temps, hem de fer-ho de nou. No tan fantàstic. Així matrius no ens donen la flexibilitat tenir un nombre variable d'elements. 

Amb una llista enllaçada, la inserció és bastant fàcil. Acabem de virar cap al front. Supressió també és bastant fàcil. Hem de trobar els elements. Que impliquen algunes recerques. 

Però una vegada que hagi trobat l'element que estàs buscant, tot el que ha de fer és canviar un punter, possiblement dos si té una de vinculada pel·lícules-- un doble llista enllaçada, rather-- i llavors vostè pot simplement alliberar el node. Vostè no ha de canviar tot al seu voltant. Vostè acaba de canviar dos punters, així que això és bastant ràpid. 

Operacions de recerca és dolent, oi? Per tal per a nosaltres trobar un element d'una llista enllaçada, ja sigui individualment o doblement enllaçada, hem de buscar-la en el lineal. Hem de començar pel principi i moure l'extrem, o començar pel moviment final al principi. No tenim accés aleatori més. Així que si estem fent un munt de recerca, potser una llista enllaçada no és tan bo per a nosaltres. 

També són molt difícil de resoldre, oi? L'única manera que pugui realment ordenar una llista enllaçada és per solucionar el problema a mesura que construeixes ell. Però si ordena com vostè construir-lo, ja no estàs fent insercions ràpides més. No està sol virades coses a la part frontal. Has de trobar la lloc adequat per dir-ho, i després la seva inserció es torna gairebé tan dolent com la inserció en una matriu. Així llistes enllaçades no són tan gran per a la classificació de dades. 

També són bastant petites, de mida convenient. Llista doblement enllaçada lleugerament més gran que les llistes per separat enllaçats, que són lleugerament més grans de matrius, però no és una enorme quantitat d'espai desaprofitat. Així que si l'espai és un bé escàs, però no una prima molt intens, aquest podria ser el camí correcte a seguir. 

Les taules hash. La inserció en una taula hash és bastant senzill. És un procés de dos passos. En primer lloc hem de córrer a través dels nostres dades una funció hash per obtenir un codi hash, i després inserim l'element en el taula hash en aquesta ubicació codi hash. 

Supressió, similar a la llista enllaçada, és fàcil una vegada que trobi l'element. Has de trobar-primer, però després, quan ho elimina, només ha d'intercanviar un parell de punters, si vostè està utilitzant encadenament separat. Si utilitzeu el sondeig, o si no estàs utilitzant l'encadenament en absolut en la seva taula hash, eliminació és realment molt fàcil. Tot el que necessites fer és hash de la de dades i, a continuació, anar a aquest lloc. I suposant que no ho fa tenir col·lisions, podràs eliminar ràpidament. 

Ara, la recerca és on les coses ser una mica més complicat. Està enmig d'una millor de llistes enllaçades. Si utilitzeu l'encadenament, encara té una llista enllaçada, el que significa que encara té la Cerca causi un perjudici una llista enllaçada. Però com que vostè està prenent el seu lligats llista i la seva divisió de més de 100 o 1000 o n elements en la seva taula hash, ets llistes enllaçades són tots u enèsim la mida. Tots són substancialment menor. Has n vinculats llistes vegada d'una sola llista enllaçada de mida n. 

I pel que aquest món real constant factor, que en general, no es parla de la complexitat temps, no realment fer una diferència aquí. Així de recerca segueix sent lineal buscar si vostè està utilitzant l'encadenament, però la longitud de la llista Ets a la és molt, molt curt en comparació. De nou, si la classificació és la seva objectiu aquí, taula hash de probablement no és el camí correcte a seguir. Només ha d'utilitzar una matriu si la classificació és realment important per a vostè. 

I poden funcionar la gamma de mida. És difícil dir si un taula hash és petit o gran, perquè realment depèn de la mida de la seva taula hash és. Si només vas a emmagatzemar cinc elements en la seva taula hash, i vostè té una taula hash amb 10.000 elements en els mateixos, t'estàs perdent un munt d'espai. Contrast ser que també pots té taules hash molt compactes, però el més petit de la seva taula hash es posa, com més temps cadascuna d'aquestes llistes enllaçades aconsegueix. I així, no hi ha realment cap manera de definir exactament la mida d'una taula hash, però és probablement segur dir que és en general serà més gran que una vinculada Llista d'emmagatzematge de les mateixes dades, però més petit que un trie. 

I intents són la quarta d'aquestes estructures que hem estat parlant. Inserció en un trie és complexa. Hi ha un munt de dinàmica assignació de memòria, sobretot al principi, com vas a començar a construir. Però és temps constant. No és més que l'element humà aquí que fa que sigui difícil. Haver de trobar punter nul, malloc espai, anar-hi, l'espai, possiblement malloc des d'allà de nou. El tipus de factor d'intimidació de punters en l'assignació de memòria dinàmica és l'obstacle per esborrar. Però una vegada que hagi netejat ella, la inserció en realitat ve molt simple, i sens dubte és la constant de temps. 

Supressió és fàcil. Tot el que necessites fer és navegar per una parell de punters i connexió al node, així que això és bastant bo. Operacions de cerca també és bastant ràpid. Només es basa en la longitud de les seves dades. Així que si totes les seves dades és cinc cadenes de caràcters, per exemple, vostè està emmagatzemant de cinc cadenes de caràcters en el trie, només es triga cinc passos per trobar el que estàs buscant. El cinc és només un factor constant, de manera que de nou, la inserció, eliminació i recerca aquí estan tots els temps constant, eficaç. 

Una altra cosa és que la seva trie és en realitat una mica ja ordenats, oi? En virtut del que som elements d'inserció, anant lletra per lletra del clau, o dígit a dígit de la clau, normalment, la seva trie acaba sent tipus de ordenats com el construeixes. En realitat no fa sentit de pensar en la classificació de la mateixa manera en què pensem sobre amb matrius o llistes enllaçades, o taules hash. Però en cert sentit, la seva trie està ordenada a mesura que avança. 

El desavantatge, és clar, és que 1 trie es converteix ràpidament en enormes. Des de tots els punts d'unió, és possible que tener-- si la seva clau consisteix en dígits, vostè té 10 una altra llocs als quals poden anar, que vol dir que cada node conté informació sobre les dades que desitja emmagatzemar en aquest node, més 10 punts. La qual cosa, en CS50 IDE, és de 80 bytes. Així que és almenys 80 bytes per cada node que es crea, i això sense comptar les dades. I si els seus nodes són lletres en comptes de nombres, ara tens 26 punters de cada lloc. I 26 vegades 8 és probablement 200 bytes, o alguna cosa així. I vostè té el capital i vostè pot lowercase-- veure on vaig amb això, oi? Els seus nodes poden aconseguir realment gran, i pel que el trie sí, en general, pot aconseguir realment gran, massa. Així que si l'espai és molt alta prima en el sistema, 1 trie vegada no sigui la manera correcta de vagi, tot i que els seus altres beneficis entrar en joc. Sóc Doug Lloyd. Això és CS50.