>> ALTAVEU 1: D'acord, estem de tornada.
Benvingut a CS50.
Aquest és el final de la setena setmana.
Així que recorda que l'última vegada, comencem mirar una mica més sofisticat
estructures de dades.
Com fins ara, tot el que tenia realment a la nostra disposició era això, una matriu.
>> Però abans de descartar la matriu que no tot el que interessant, que de fet es
en realitat és, quins són alguns dels avantatges d'aquests senzills dades
estructura fins ara?
Com és bo?
Pel que hem vist?
Què tens?
Res.
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Què és això?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Mida fix.
OK, així que per què és bo, encara que de mida fixa?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: OK, així que és eficient en la el sentit que es pot assignar un
quantitat fixa d'espai, que s'espera és precisament tant
l'espai que desitgi.
Així que podria ser absolutament un avantatge.
>> Quin és l'altre costat d'una matriu?
Sí?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Tots els - ho sento?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Tots els quadres en la memòria o un al costat de l'altre.
I això és útil - per què?
Això és molt cert.
Però com podem aprofitar aquesta veritat?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Exactament, es pot realitzar un seguiment de on tot és només saber
una adreça, a saber, la direcció de la primer byte d'aquest tros de la memòria.
O en el cas de la cadena, la direcció de la primera
xerrada en aquesta cadena.
I a partir d'aquí, podem trobar al final de la cadena.
Podem trobar la segona part, el tercer element, i així successivament.
>> I així, la forma elegant de descriure que característica és que les matrius ens donen
d'accés aleatori.
Només mitjançant l'ús dels claudàtors notació i un nombre, pot saltar a
un element específic de la matriu en temps constant, gran O
d'un, per dir-ho.
>> Però hi ha hagut alguns inconvenients.
El que una matriu no fer molt fàcilment?
Què no fer bé?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Què és això?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Ampliació de mida.
Així que els aspectes negatius de la matriu són precisament el contrari del que el
Upside són.
Així que una de les desavantatges és que és una mida fixa.
Així que realment no es pot créixer.
Pot reassignar una part més gran de la memòria i, a continuació, mogui els elements antics
en la nova matriu.
I llavors lliure de l'antiga matriu, per exemple, mitjançant l'ús de malloc o similar
funció anomenada realloc, que reassignació memòria.
>> Realloc, en un apart, intenta donar-li memòria que està al costat de la matriu
que vostè ja té.
Però podria canviar les coses al voltant de per complet.
Però en fi, això és car, no?
Perquè si tens un tros de memòria de aquesta mida, però realment vull un
d'aquesta mida, i desitja conservar els elements originals, que tenen
més o menys un procés de còpia temps lineal això ha de succeir d'
antiga matriu a la nova.
I la realitat està demanant a l'operació sistema d'una i altra vegada i
de nou per grans trossos de la memòria pot començar a costar algun temps també.
Així que és tant una benedicció com una maledicció en disfressa, el fet que aquestes matrius
són de grandària fixa.
Però si introduïm vegada alguna cosa així, el que anomenem una vinculada
llista, tenim alguns avantatges i alguns desavantatges també aquí.
>> Així que una llista enllaçada és simplement un conjunt de dades estructura composta per estructures de C en aquest
cas, en què una estructura, el record, és només un contenidor per a una o més específica
tipus de variables.
En aquest cas, el que ho fan els tipus de dades semblen estar dins de l'estructura que
última vegada que es diu un node?
Cada un d'aquests rectangles és un node.
I cada un dels rectangles més petits dins d'ella és un tipus de dades.
Quins tipus vam dir estaven el dilluns?
Sí?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Una variable i un punter, o més específicament, un int, per a n,
i un punter a la part inferior.
Tant dels que resulten ser de 32 bits, per la qual almenys en un equip com aquest CS50
Appliance i pel que són dibuixat per igual en grandària.
>> Llavors, què estan utilitzant el punter encara que per semblar?
Per què afegir aquesta fletxa ara, quan les matrius van ser molt agradable i net i simple?
Què està fent el punter per nosaltres en cada un d'aquests nodes?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Exactament.
Li està dient que el següent és.
Així que en certa manera em utilitzo l'analogia de utilitzant un fil a la classe de
enfilar aquests nodes entre si.
I això és exactament el que estem fent amb punters perquè cada un d'aquests
trossos de memòria poden o poden no estar contigua, esquena amb esquena amb esquena
interior de RAM, perquè cada vegada que trucar a malloc dient dóna'm suficient
bytes d'un nou node, podria ser aquí o podria ser aquí.
Podria ser aquí.
Vostè simplement no sap.
>> Però l'ús de punters a les adreces d' els nodes, pot cosir
junts d'una manera que sembla visualment com una llista, fins i tot si aquestes coses són
totes disperses en tot el seu ser o els dos o els quatre gigabytes de RAM
dins del seu propi equip.
>> Així que la banda negativa, doncs, de una llista enllaçada és què?
Què és un preu que estem Aparentment pagar?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Més espai, no?
Tenim, en aquest cas, es va duplicar la quantitat l'espai, ja que hem anat
de 32 bits per a cada node, per a cadascun int, de manera que ara de 64 bits perquè hem de
mantenir al voltant d'un punter també.
Vostè obté més eficiència si la seva estructura és més gran que aquesta cosa simple.
Si vostè té actualment un estudiant a l'interior dels quals és un parell de cadenes de
nom i la casa, potser un número d'identificació, potser alguns altres camps en total.
>> Així que si vostè té una gran estructura suficient, llavors potser el cost del punter està
no és un gran problema.
Això és una mica d'un cas de la cantonada en què estem emmagatzemant una simple primitiva tals
dins de la llista enllaçada.
Però el punt és el mateix.
Definitivament estàs gastant més memòria, però que està rebent
flexibilitat.
Perquè ara si vull afegir un element al principi d'aquesta llista,
He de assignar un nou node.
I he de actualitzar només els fletxes d'alguna manera, amb només moure
alguns indicadors voltant.
>> Si vull inserir alguna cosa al meitat de la llista, no té per què
empènyer a tots a un costat com ho vam fer en passat setmanes amb els nostres voluntaris que
representa una matriu.
Només puc assignar un nou node i després simplement apuntar les fletxes
diferents direccions, ja que no haurà de romandre en el reial
memòria d'una veritable línia com he dibuixat aquí a la pantalla.
>> I finalment, si voleu inserir cosa que al final de la llista, és
encara més fàcil.
Aquesta és una espècie de notació arbitrària, però un triple de 34, prendre una conjectura.
Quin és el valor del seu indicador més probablement una mena de dibuixat com un vell
antena de l'escola allà?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Probablement és nul.
I de fet aquesta és una de l'autor representació de nul.
I és nul · la, perquè malgrat tot necessitat de saber on és el final d'un vinculat
llista és, perquè no es manté després i seguint i seguint aquestes fletxes
a un valor d'escombraries.
Així nul significarà que no hi ha més nodes a la dreta del número 34,
en aquest cas.
>> Per tant, proposem que podem posar en pràctica aquest node en el codi.
I hem vist aquest tipus abans de la sintaxi.
Typedef simplement defineix un nou tipus de nosaltres, ens dóna un sinònim com
cadena era per char *.
En aquest cas, ens donarà notació abreujada per a aquest node struct
pot en el seu lloc només pot escriure com node, que és molt més net.
És molt menys detallat.
>> A l'interior d'un node és aparentment un int anomenada n, i a continuació, un node d'estructura *
el que significa exactament el que volíem la fletxes per dir, un punter a un altre
node del mateix tipus de dades exacta.
I proposo que podríem implementar un funció de cerca d'aquest tipus, que en
primera vista pot semblar una mica complex.
Però anem a veure-ho en el seu context.
>> Vull passar l'aparell aquí.
Permetin-me obrir un fitxer anomenat llista de punts h zero.
I que només conté la definició que acabo de veure fa un moment per a aquestes dades
Tipus El node.
Així que hem posat això en un arxiu de punts h.
>> I en un a part, tot i que aquesta programa que està a punt de veure és
no és tan complexa, que és de fet convencions en escriure un programa per
posar les coses com els tipus de dades, per treure constants, de vegades, dins del seu
arxiu de capçalera i no necessàriament en l'arxiu de C, sobretot quan el seu
programes es fan més grans i més grans, pel que vostè sap on buscar, tant per
documentació en alguns casos, o per el bàsic com aquest, els
definició d'algun tipus.
>> Si ara obro llista de zero punts c, es va adonar d'algunes coses.
Conté una sèrie d'arxius de capçalera, la majoria dels dels quals hem vist abans.
Inclou el seu propi arxiu de capçalera.
>> I en un a part, per què això és doble cites aquí, en contraposició a l'angle
suports en la línia que He destacat allà?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Sí, per la qual cosa és un fitxer local.
Així que si és un fitxer local de la seva pròpia aquí en la línia 15, per exemple, s'utilitza
les cometes dobles en lloc dels suports en angle.
>> Ara bé, això és una cosa interessant.
Tingueu en compte que he declarat un Mundial variable en aquest programa a la línia 18
va cridar en primer lloc, la idea d'això és serà un punter a la primera
node a la meva llista enllaçada, i he inicialitza a null, perquè he
no assignat cap real nodes encara.
>> Així que això representa, gràficament, el que vaig veure fa un moment en la imatge com
aquest punter a l'extrem esquerra costat.
Així que ara mateix, aquest punter no té una fletxa.
En el seu lloc, és nul.
Però representa el que serà el direcció del primer real
node en aquesta llista.
Així que he implementat és un mundial perquè, com es veurà, tot això
programa no a la vida és posar en pràctica una llista enllaçada per a mi.
>> Ara tinc uns prototips aquí.
Vaig decidir implementar característiques com eliminació, inserció, recerca i
de recorregut -
l'últim només estar a peu a través de la llista, imprimint els seus elements.
I ara aquí està la meva rutina principal.
I no anem a passar molt temps en aquestes ja que aquesta és una espècie de, tant de bo
barret vell ja.
>> Vaig a fer el següent, mentre que l'usuari col · labora.
Així que un, vaig a imprimir aquest menú.
I he formatat com netament com vaig poder.
Si l'usuari escriu en un, això significa volen esborrar alguna cosa.
Si l'usuari escriu en dos, el que significa volen inserir alguna cosa.
I així successivament.
Vaig a suggerir a continuació, a continuació d'un comando.
I llavors vaig a utilitzar GetInt.
>> Així que aquesta és una molt simple menuing interfície en la qual només ha d'escriure
una assignació de número a un d'aquests comandaments.
I ara tinc un interruptor net agradable declaració que canviarà el
tot el que l'usuari va escriure polz
I si s'escriuen un, vaig a trucar a esborrar i trencar.
Si escriuen dues, vaig a trucar a inserir i trencar-se.
>> I ara noto que he posat cada d'aquests en la mateixa línia.
Això és només una decisió estilística.
En general hem vist alguna cosa d'aquesta manera.
Però vaig decidir, francament, el meu programa semblava més fàcil de llegir, perquè
era només quatre casos a només la llista així.
Totalment ús legítim d'estil.
I jo faré això sempre que el persona no ha posat zero, el que em
decidir significarà que volen deixar de fumar.
>> Així que ara compta del que sóc farem aquí.
Vaig a alliberar la llista aparentment.
Però més sobre això en un moment.
Primer anem a executar aquest programa.
Així que permetin-me fer un terminal més gran finestra, punt slash llista 0.
Vaig a seguir endavant i inseriu a la escriure dos un nombre com 50, i ara
veuràs la llista és ara 50.
I el meu text només desplaça una mica.
Així que ara compta la llista conté el número 50.
>> Anem a fer un altre inserit prenent dos.
Escriurem el nombre com a tal.
Llista és ara un, seguit per 50.
Així que això és només una representació textual de la llista.
I anem a inserir una més igual nombre el número 42, que és d'esperar
va a acabar en el medi, perquè aquest programa a les classes particulars que
elements, ja que els insereix.
Així que aquí ho tenim.
Programa Súper simple que podria absolutament he utilitzat una matriu, però
passar a ser l'ús d'una llista enllaçada perquè jo pugui dinàmicament
créixer i reduir la seva grandària.
>> Així que anem a fer una ullada per a la recerca, si ordre de tres funcionar, vull buscar
per, per exemple, el nombre 43.
I res es va trobar que sembla, perquè vaig tornar resposta.
Així que anem a fer això una altra vegada.
Cercar.
Buscarem 50, o més aviat buscar el 42, que té un bon
poc significat subtil.
I vaig trobar el significat de la vida allà.
Número 42, si vostè no sap la referència, google.
Està bé.
Llavors, què té aquest programa fet per mi?
És que m'ha permès inserir tant al llarg i recerca d'elements.
>> Anem a avançar ràpidament, llavors, aquesta funció ens va mirar a
dilluns com un reclam.
Així que aquesta funció, reclam, busca un element a la llista per primera
un, preguntar a l'usuari i després trucar GetInt per obtenir un int real
que voleu cercar.
>> Després compte d'això.
Vaig a crear una variable temporal en la línia 188 diu punter -
PTR -
podria haver anomenat res.
I és un punter a un node perquè he dit node * allà.
I estic inicialitzant que sigui igual a primer perquè efectivament tinc el meu
dit, per així dir-ho, en el mateix primer element de la llista.
Així que si la meva mà aquí és PTR estic apuntant al mateix que la primera
està assenyalant.
>> Així que ara de nou en el codi, Què passa després -
aquest és un paradigma comú quan es repeteix sobre una estructura com un
llista enllaçada.
Jo faré el següent mentre punter no és igual a null Així, mentre que
el meu dit no assenyala en algun nul valor, si el punter fletxa n és igual a n.
Ens vam adonar per primera vegada que n és el que el usuari va escriure en per GetInts cridar aquí.
>> I punter de fletxa n vol dir què?
Bé, si ens remuntem a la imatge aquí, si tinc un dit apuntant a
que primer node que conté nou, la fletxa essencialment vol dir anar a la
node i prendre el valor en la posició n, en aquest cas, el camp de dades flama n.
>> Com acotació al marge - i ens vam veure un parell de setmanes enrere, quan algú li va preguntar -
aquesta sintaxi és nou, però no ho fa donar-nos poders que
no tenen ja.
Quin era aquesta frase equival a utilitzar notació de punts i l'estrella d'un parell
de setmanes quan va desprendre aquesta capa una mica abans de temps?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Exactament, era l'estrella, i després va ser l'estrella del punt n, amb
parèntesi aquí, el que es veu, Francament, crec que molts
més críptic de llegir.
Però indicador de l'estrella, com sempre, significa anar-hi.
I una vegada que estàs allà, quines dades camp és el que vols accedir?
Bé utilitza la notació de punts d'accés un camp de dades d'estructures, i
específicament vol n.
>> Francament, jo diria que aquest només és més difícil de llegir.
És més difícil de recordar on Com els parèntesis anar, el
estrelles i tot això.
Així que el món s'ha adoptat alguna sintàctica sucre, per dir-ho.
Només una forma atractiva de dir, això és equivalent, i
potser més intuïtiu.
Si punter és de fet un punter, el fletxa mitjans notació anar allà i trobar
el camp, en aquest cas anomenat núm.
>> Així que si el trobo, adonar-se del que faig.
Simplement em imprimeixo, vaig trobar cent i, endollar el valor per a aquest int.
Truco dormir durant un segon sol a la classe de pausa les coses a la pantalla per
donar a l'usuari un segon per absorbir el que acaba de succeir.
I llavors trenco.
En cas contrari, què faig?
Com actualitzo punter a la igualtat de fletxa de punter següent.
>> Així que per ser clars, això vol dir anar allà, amb la meva notació de la vella escola.
Així que això només significa anar a qualsevol vostè està apuntant a que, en el
primer cas és que estic assenyalant l'estructura amb nou en el mateix.
Així que he anat.
I a continuació, significa la notació de punts, obtenir el valor al següent.
>> Però el valor, tot i que ha dibuixat com un estret, és només un nombre.
És una adreça numèrica.
Així que una línia de codi, ja sigui escrit com aquest, el més críptic
així, o així, els poc més manera intuïtiva, simplement vol dir moure la mà
des del primer node al següent, i després el següent, i a continuació, la
següent, i així successivament.
>> Així que no vaig a detenir-me en l'altre implementacions d'inserir i eliminar
i el recorregut, els dos primers de que són bastant implicats.
I crec que és molt fàcil d'aconseguir perdut en fer-ho verbalment.
Però el que podem fer aquí és tractar de determinar com
millor fer-ho visualment.
Perquè jo proposaria que si voleu inserir elements en aquesta
llista existent, que té cinc elements -
9, 17, 22, 26, i 33 -
si jo fos a implementar això en codi, he d'estudiar la forma d'anar
fent això.
>> I jo proposaria prendre passos de nadó pel que, en aquest cas em refereixo al que són
els possibles escenaris que poden sorgir en general?
Quan l'aplicació d'inserció per a un lligat llista, això només passa a ser un
exemple específic de mida de cinc.
Bé, si vol inserir un número, com diuen el número u, i
mantenir l'ordre establert, on òbviament, fa el número u necessita
anar en aquest exemple concret?
Igual que al principi.
>> Però el més interessant no és que si voleu inserir una en aquest
llista, el que necessita punter especial ser actualitzat aparentment?
En primer lloc.
Així que jo diria, aquest és el primer cas que el que es vol tenir en compte, un
escenari en el qual la inserció en el principi de la llista.
>> Anem a arrencar potser una tan fàcil o fins i tot el cas més senzill, en termes relatius.
Suposem que vull inserir la el número 35 en l'ordre establert.
Òbviament pertany allà.
Llavors, quin indicador òbviament va a d'actualitzar en aquest escenari?
Punter de 34 convertint no nul · la però la direcció de l'estructura
que conté el número 35.
Així que això és el cas de dos.
Així que ja, jo sóc una mena de quantificació la quantitat de treball que he de fer aquí.
>> I, finalment, el cas mitjà és obvi de fet, en el medi, si vull
inserir una cosa així com dir 23, que va entre el 23 i el 26, però
Ara les coses es posen una mica més participar perquè ho
punters necessiten ser canviat?
Així que, òbviament, 22 necessita ser canviat perquè no pot apuntar a 26 més.
Ell ha d'apuntar al nou node que Vaig a haver de destinar trucant
malloc o algun equivalent.
>> Però també necessito que el nou node, 23 en aquest cas, per tenir la seva punter
assenyalant a qui?
26.
I no serà un ordre de les operacions aquí.
Perquè si ho faig tontament, i per exemple inici al començament de
la llista, i el meu objectiu és inserir 23.
I comprovo, li pertany Aquí, prop de nou?
No
Pertany aquí, al costat 17?
No
Li pertany a aquest lloc al costat de 22?
Sí
>> Ara bé, si sóc tonto aquí, i no pensant en això, jo podria
assignar meu nou node 23.
Jo podria actualitzar el punter del el node de flama 22, que assenyala
que en el nou node.
I llavors, ¿què he de actualitzar Punter del nou node sigui?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Exactament.
Assenyalant a 26.
Però maleïda sigui si no ja actualitzo Punter de 22 per assenyalar a aquest tipus, i
ara tinc orfes, la resta de la llista, per dir-ho.
Així que la finalitat de les operacions aquí serà important.
>> Per a això podria robar, dir, sis voluntaris.
I anem a veure si podem fer això visualment en lloc del codi es refereix.
I tenim una mica d'estrès encantadora boles per al dia d'avui.
Bé, què hi ha d'una, dues, al tornada - a l'extrem allà.
tres, quatre, els dos nois a la final.
I cinc, sis.
Clar.
Cinc-sis.
Està bé i anem a arribar amb vostès la propera vegada.
Bé, anem amunt.
>> Bé, ja que ets aquí primer, T'agradaria ser la malaptesa
a Google Glass aquí?
D'acord, llavors, OK, Glass, gravar un vídeo.
Bé, ja està bo per anar.
>> Molt bé, així que si vostès poden venir aquí, he preparat amb antelació
alguns números.
Bé, anem per aquí.
¿I per què no et vas una mica més d'aquesta manera.
I anem a veure, quin és el teu nom, amb el vidre de Google?
>> ESTUDIANT: Ben.
>> ALTAVEU 1: Ben?
Bé, Ben, que serà la primera, literalment.
Així que anem a enviar al final de l'etapa.
Molt bé, i el teu nom?
>> ESTUDIANT: Jason.
>> ALTAVEU 1: Jason, OK Vas ser el número nou.
Així que si vols seguir Ben així.
>> ESTUDIANT: Jill.
>> ALTAVEU 1: Jill, que serà 17, que si hagués fet això més
intel · ligent, hauria començat en l'altre extrem.
Pots anar per aquest camí.
22.
I vostè és?
>> ESTUDIANT: Maria.
>> ALTAVEU 1: Mary, podràs 22.
I el seu nom és?
>> ESTUDIANT: Chris.
>> ALTAVEU 1: Chris, seràs 26.
I a continuació, finalment.
>> ESTUDIANT: Diana.
>> ALTAVEU 1: Diana, que serà 34.
Així que véns per aquí.
>> Molt bé, així que perfecte ordenats ordenar ia.
I seguirem endavant i fer això perquè puguem realment -
Ben vostè és només una mica de mirar cap al no res allà.
OK, així que seguirem endavant i representen el l'ús d'armes, igual que jo, precisament,
el que està passant.
Així que endavant i donen-1 o dos peus entre vosaltres.
I seguir endavant i apuntar amb una mà per qualsevol que ha d'apuntar a
en base a això.
I si vostè és nul · la simplement apunt directament cap a terra.
Bé, molt bé.
>> Així que ara tenim una llista enllaçada, i em va deixar Proposo que jugaré el paper de
PTR, així que no et molestis portar això al voltant.
I llavors - a algú convenció estúpid - es pot trucar a això tot el que vulguis -
punter predecessor, punter pred -
és només el sobrenom que li vam donar a nostre codi d'exemple per a la mà esquerra.
L'altre, que mantindrà un registre de qui és qui en el
següents escenaris.
>> Així que suposo que, en primer lloc, vull arrencar que primer exemple de la inserció de, diguem
20, a la llista.
Així que vaig a necessitar a algú que encarnar el número 20 per a nosaltres.
Així que necessito a algú malloc de l'audiència.
Anem amunt.
Com et dius?
>> ESTUDIANT: Brian.
>> ALTAVEU 1: Brian, d'acord, per la qual cosa serà el node que conté 20.
Bé, anem per aquí.
I, òbviament, on pertany Brian?
Així, enmig de - en realitat, Espera un minut.
Estem fent aquesta fora d'ordre.
Estem fent això molt més difícil del que ha de ser en un principi.
Bé, anem a la lliure Brian i realloc Brian com cinc.
>> OK, així que ara volem inserir Brian com cinc.
Així que veuen aquí al costat Ben per un moment.
I vostè pot dir probablement quan aquesta història va.
Però anem a pensar acuradament sobre l'ordre de les operacions.
I és precisament aquesta visual que va a alinear
amb aquest codi de mostra.
Així que aquí he PTR apuntant inicialment no en Ben, per se, sinó en el que sigui
valoren que conté, que en aquest cas és - ¿quin és el teu nom?
>> ESTUDIANT: Jason.
>> ALTAVEU 1: Jason, per tant Ben i jo som assenyalant a Jason en aquest moment.
Així que ara he de determinar, on pertany Brian?
Així que l'únic que tinc accés a ara és el seu element de dades n.
Així que vaig a comprovar, està Brian menys de Jason?
La resposta és vertadera.
>> ¿I ara què ha de succeir, en l'ordre correcte?
Necessito actualitzar quants punters en total en aquesta història?
Quan la meva mà se segueix apuntant a Jason, i la seva mà - si vol
posar la seva mà com, més o menys, em no sé, un signe d'interrogació.
Bé, bé.
>> Bé, pel que té alguns candidats.
Qualsevol de Ben, jo o Brian o Jason o qualsevol altra persona, que
punters han de canviar?
Quants en total?
>> OK, així que dos.
El meu punter en realitat no importa ja perquè jo sóc només temporal.
Així que aquests dos homes, presumiblement, tant Ben i Brian.
Així que em proposo que actualitzem Ben, ja que ell és primer.
El primer element de la llista Ara serà Brian.
Així que el punt a Ben Brian.
Bé, i ara què?
>> Qui aconsegueix assenyalar qui?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Acceptar el que Brian té per apuntar a Jason.
Però he perdut el compte de que el punter?
Sé que Jason és?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: jo, com sóc el punter temporal.
I presumiblement, no he canviat per assenyalar en el nou node.
Així que podem tenir simplement el punt Brian en què estic assenyalant.
I ja està.
Així cas que un, la inserció en el principi de la llista.
Hi havia dos passos clau.
Un d'ells, hem de actualitzar Ben, i després també hem de actualitzar Brian.
I llavors no he de preocupar penosament a través de la resta de la
llista, perquè ja trobem la seva lloc, perquè pertanyia a la
a l'esquerra del primer element.
>> Molt bé, així que bastant senzill.
De fet, se sent com que estem gairebé fent això massa complicat.
Així que ara arrencar al final de la llista, i veure on
s'inicia la complexitat.
Així que si ara, Alloc de l'audiència.
Algú vol jugar a 55?
Bé, vaig veure la seva mà primer.
Anem amunt.
Si.
Com et dius?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Habata.
Bé, anem amunt.
Vostè serà el número 55.
Així que, per descomptat, pertany al final de la llista.
Així que anem a reproduir la simulació amb mi sent el PTX per un moment.
Així que estic primer va a apuntar a Ben ho està apuntant.
Els dos estem apuntant ara a Brian.
Així que 55 no sigui inferior a cinc.
Així que vaig a actualitzar el meu mateix apuntant a la triple de Brian, que
Ara és, per descomptat, Jason.
55 No és menys de nou anys, per la Vaig a actualitzar PTR.
Vaig a actualitzar PTR Em va a actualitzar PTR.
I jo vaig a - hmm, què el teu nom?
>> ESTUDIANT: Diana.
>> ALTAVEU 1: Diana està assenyalant, per descomptat, en nul amb la mà esquerra.
Llavors, on Habata realitat pertanyen clarament?
A l'esquerra, aquí.
Llavors, com puc saber que posar aquí Crec que m'he cagat.
Perquè el que és l'art PTR aquest moment en el temps?
Null.
Així que tot i que, visualment, podem òbviament veure tots aquests
nois aquí a l'escenari.
No he seguit la pista dels anteriors persona en la llista.
Jo no tinc un dit assenyalant, en aquest cas, el nombre de node 34.
>> Així que anem a començar realment sobre això.
Així que ara realment necessito una segona variable local.
I això és el que veuràs al codi C mostra real, en tant que jo vaig,
quan actualitzo la meva mà dreta per indicar Jason, deixant per tant darrere de Brian, em
millor començar a utilitzar la mà esquerra per actualitzar on era, pel que a mesura que vagi
a través d'aquesta llista -
més maldestre del que pensava Ara aquí visual -
Vaig a arribar a la final de la llista.
>> Aquesta part segueix sent nul, la qual cosa és bastant inútil, excepte per indicar
Estic clarament al final de la llista, però ara almenys tinc aquesta
punter predecessor assenyalant aquí, així ¿I ara què mans i quins indicadors s'han
d'actualitzar?
Qual la mà és el que vols tornar a configurar per primera vegada?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: OK, així que Diana.
On vol assenyalar Punter esquerre de Diana a?
En 55, presumiblement, de manera que hem inserit allà.
¿I on hauria d'anar 55 punter?
Pressionat, que representa un valor nul.
I les mans, en aquest punt, no importa perquè no eren més que
variables temporals.
Així que ara que hem acabat.
>> Així que la complexitat addicional allà - i que no és tan difícil d'implementar,
però necessitem una variable secundària per fer Assegureu-vos que abans de passar al meu dret
banda, puc actualitzar el valor de la meva esquerra mà, punter pred en aquest cas, per la
que tinc un indicador de seguiment fer un seguiment d'on era.
Ara, en un apart, si estàs pensant en aquest a través, això se sent com si fos un
mica molest haver de mantenir seguiment d'aquesta mà esquerra.
>> Com seria una altra solució a aquest problema han estat?
Si has arribat a redissenyar les dades estructura que estem parlant
a través d'aquests moments?
Si aquest tipus només se sent una mica de molest tenir, com, dos punters
passant per la llista, qui més podria han, en un món ideal, mantingut
informació que necessitem?
Sí?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Exactament.
Just el que en realitat hi ha una interessant germen d'una idea.
I aquesta idea d'un punter anterior, assenyalant l'element anterior.
Què passa si jo encarnat que dins de la pròpia llista?
I serà difícil de visualitzar això sense tot el paper
caure a terra.
Però suposem que aquests nois utilitzen tant de les seves mans per tenir una prèvia
punter, i un indicador de següent, així aplicació del que anem a trucar a un doble
llista enllaçada.
Això em permetrà espècie de rebobinat, molt més fàcil i sense mi, el
programador, haver de mantenir seguiment manual -
veritablement manualment -
d'on havia estat prèviament a la llista.
Així que no farem això.
Anem a mantenir simple, perquè això és tindrà un preu, el doble de
molt espai per als punters, si vols una segona.
Però això és realment un comú estructura de dades coneguda com
llista doblement enllaçada.
>> Anem a fer l'últim exemple aquí i posar aquests nois de la seva misèria.
Així malloc 20.
Anem a partir del passadís allà.
Bé, quin és el teu nom?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Com?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Demeron?
Acceptar anem amunt.
Vostè serà el 20.
Vostè, evidentment, va a pertanyen entre el 17 i el 22.
Així que anem a aprendre la lliçó.
Vaig a començar punter assenyalant a Brian.
I jo tindré la meva mà esquerra només actualitzar a Brian com em mut a
Jason, la comprovació de fa 20 a menys de nou?
No
És 20 menys de 17?
No
És 20 menys de 22?
Sí
Llavors, ¿quins consells o les mans han de canviar on estan apuntant ara?
>> Així que podem fer 17 apuntant a 20.
Així està bé.
On volem assenyalar el punter ara?
Als 22 anys.
I sabem que 22 és, de nou, gràcies al meu punter temporal.
Així que estem bé.
Així que per la seva emmagatzematge temporal He mantingut un seguiment d'on és cadascú.
I ara vostè pot anar visualment on al qual pertany, i ara necessita 1, 2, 3,
4, 5, 6, 7, 8, 9 boles de la tensió, i una ronda d'aplaudiments per
aquests nois, si poguéssim.
Molt ben fet.
>> [Aplaudiments]
>> ALTAVEU 1: D'acord.
I és possible mantenir les peces de paper com records.
>> D'acord, llavors, confia en mi, és molt fàcil de caminar a través que, amb
els humans del que és amb codi real.
Però el que trobarà en un moment Ara, és el mateix - Oh, gràcies.
Gràcies -
és que trobareu que les mateixes dades estructura, una llista enllaçada, en realitat es pot
pot utilitzar com un bloc de construcció per més estructures de dades sofisticades.
>> I compte també el tema aquí és que hem absolutament introduït més
complexitat en la implementació d'aquest algorisme.
Inserció, i si passem per ella, eliminació i recerca, és una mica
més complicat del que estava amb una matriu.
Però vam guanyar cert dinamisme.
Tenim una estructura de dades d'adaptació.
>> Però, de nou, hem de pagar un preu de tenir algun complexitat addicional, tant en
seva aplicació.
I se'ns dóna l'accés aleatori.
I per ser honest, no hi ha algun bon netejar diapositiva que puc donar-te que
diu aquí és per què una llista enllaçada és millor que una matriu.
I deixar les coses així.
A causa de que el tema es repeteixi ara, fins i tot més en les pròximes setmanes, és
que no és necessàriament una resposta correcta.
>> És per això que tenim l'eix independent de disseny per als butlletins de problemes.
Serà molt sensibles al context si voleu utilitzar aquestes dades
estructura o allò, i ho farà dependrà del que li importa a vostè en termes
dels recursos i la complexitat.
>> Però permetin-me proposar que les dades ideals estructura, el sant grial, seria
una cosa que és constant de temps, independentment de la quantitat de coses és
dins d'ella, no seria increïble si un estructura de dades retornada en respostes
constant de temps.
Sí
Aquesta paraula està en la seva enorme diccionari.
O no, aquesta paraula no és.
O qualsevol problema.
Bé anem a veure si no podem, almenys, fer un pas en aquesta direcció.
>> Permetin-me proposar una nova estructura de dades que es pot utilitzar per a diferents coses,
en aquest cas es diu una taula hash.
I pel que estem realment tornar a mirar en una matriu, en aquest cas, i
tant arbitràriament, he dibuixat aquesta taula hash com una matriu amb una mena de
matriu de dues dimensions -
o més aviat que està representat aquí com una de dues matriu bidimensional - però això és només
una matriu de mida 26, de manera que si ens truqui a la taula d'arranjament, suport de taula
zero és el rectangle a la part superior.
Taula suport 25 és el rectangle a la part inferior.
I així és com jo podria dibuixar un conjunt de dades estructura en què vull guardar
noms de les persones.
>> Així, per exemple, i no vaig a assenyalar a la Tot aquí al cap, si em
tingut aquesta sèrie, que ara vaig a cridar a una taula hash, i això és nou
posició zero.
Això aquí és la ubicació un, i així successivament.
Afirmo que vull utilitzar aquestes dades estructura, pel bé de la discussió,
per emmagatzemar noms de les persones, Alice i Bob i Charlie i altres noms.
Així que pensar en aquest moment com l'inici de, per exemple, un diccionari
amb un munt de paraules.
Ells resulten ser noms en el nostre exemple.
I això és molt pertinent, potser, la implementació d'un corrector ortogràfic, ja que
podrien, per problema plantejat 06:00.
>> Així que si tenim una matriu de mida total de 26 pel que aquesta és la ubicació 25a
a la part inferior, i jo sostinc que Alice és la primera paraula en el diccionari de
noms que voleu inserir en la memòria RAM, en aquesta estructura de dades, on són
instint li diu que d'Alice nom ha d'anar en aquesta sèrie?
>> Comptem amb 26 opcions.
On volem posar?
Nosaltres la volem en suport de zero, no?
Una d'Alice, anem a trucar a aquest zero.
I B serà un, i C serà de dos.
Així que anem a escriure El nom d'Alice aquí.
Si després inserim Bob, la seva nom anirà aquí.
Charlie es veu aquí.
I així successivament al llarg de aquesta estructura de dades.
>> Aquesta és una estructura de dades meravellosa.
Per què?
Bé, què és el temps d'execució de inserir el nom d'un ésser humà en aquest
estructura de dades en aquest moment?
Tenint en compte que aquesta taula s'implementa, realment, com una matriu.
Bé, és la constant de temps.
És la fi d'un.
Per què?
>> Bé, com determinar on Alice pertany?
Et veus en quina lletra del seu nom?
El primer.
I es pot arribar, si es tracta d'una cadena, amb només mirar cadena
suport de zero.
Per tant el caràcter zero de la cadena.
Això és fàcil.
Vam fer això en la criptografia Fa setmanes assignació.
I després un cop heu escoltat que Alice carta està Capital, podem restar
de 65 o de capital A si mateix, això ens dóna zero.
Així que ara sabem que Alice pertany en la posició zero.
>> I com un punter a aquestes dades estructura, d'algun tipus, quant de temps fa
que em porti a trobar la ubicació zero en una matriu?
A només un pas, no és la constant de temps causa de l'accés aleatori que
proposat era una característica d'una matriu.
Així que en resum, esbrinar el que l'índex de del nom d'Alice és, que és, en
aquest cas, és A, o només anem a resoldre que a zero, on B és un i C és
2, pensant que fos és la constant de temps.
Només he de mirar en la seva primera carta, esbrinar on zero és un
matriu és també constant de temps.
Així que tècnicament això és com dos passos ara.
Però això segueix sent constant.
Així que cridem a aquest gran O d'un, pel que hem Alice s'insereix en aquesta taula en
constant de temps.
>> Però, per descomptat, estic sent ingenu, no?
Què passa si hi ha un Aaron a la classe?
O Alícia?
O qualsevol altre nom a partir d' A. On posarem
aquesta persona, oi?
Vull dir, ara mateix només hi ha tres la gent a taula, així que potser
ha de posar Aaron en la ubicació zero, un, dos, tres.
>> Bé, jo podria posar una aquí.
Però llavors, si es vol inserir en David aquesta llista, a on va David?
Ara el nostre sistema comença a analitzar baix, dreta?
Perquè ara David acaba aquí si Aaron és en realitat aquí.
I ara tota aquesta idea de tenir un estructura de dades neta que ens dóna
insercions constant de temps ja no és constant de temps, perquè he de
veure, oh, maleïda sigui, algú que ja és en la ubicació d'Alice.
>> Déjame investigar la resta d'aquestes dades estructura, a la recerca d'un lloc per posar
algú com el nom d'Aaron.
I això també està començant prendre el temps lineal.
D'altra banda, si ara vol trobar la Aaron en aquesta estructura de dades, i
verificació, i el nom d'Aaron no és aquí.
L'ideal seria que vostè acaba de dir d'Aaron no en l'estructura de dades.
Però si ho fa començar a fer espai per Aaron on no hauria d'haver estat un D
o un correu, vostè, pitjor dels casos, ha de comprovar tota l'estructura de dades, en
aquest cas es convertís en alguna cosa lineal en la mida de la taula.
>> Així bé, vaig a arreglar això.
El problema aquí és que vaig tenir 26 elements d'aquesta matriu.
Permetin-me canviar-lo.
Vaya.
Déjame canviar de manera que en lloc de ser de talla 26 en total, compte de la part inferior
índex es canviarà a n almenys 1.
Si 26 és clarament massa petit per als éssers humans ' noms, perquè hi ha milers de
noms del món, farem en 100 o 1000 o 10000.
Anem a assignar molt més espai.
>> Bé, això no disminueix necessàriament la probabilitat que no tindrem dos
persones amb noms que comencin amb A, i així, que anava a tractar de posar un
noms a zero lloc encara.
Encara van a col · lisionar, el que vol dir que encara tenim una solució per posar
Alice i Aaron i Alicia i altres noms que comencin amb A qualsevol altre lloc.
Però, quant d'un problema és això?
Quina és la probabilitat que tenir col · lisions en un conjunt de dades
estructura com aquesta?
>> Bé, deixa - tornarem a aquesta pregunta aquí.
I mira com podríem resoldre primer.
Déjame treure aquesta proposta aquí.
El que acabem de descriure és un algorisme, una heurística anomenada lineal
sondeig segons el qual, si tractes d'inserir alguna cosa aquí en aquestes dades
estructura, que es diu una taula hash, i no hi ha lloc allà,
veritablement sondejar l'estructura de dades comprovació, és aquesta disponible?
Està aquesta disponible és aquesta disponible?
És aquesta disponible?
I quan per fi és, inserir el nom que vostè pretén inicialment
en un altre lloc en aquesta ubicació.
Però en el pitjor dels casos, l'únic punt podria ser la part més baixa de les dades
estructura, el final de la sèrie.
>> Així que intento lineal, en el pitjor dels casos, recau en un algoritme lineal on
Aaron, si passa a ser inserit darrera en aquesta estructura de dades, que podria
topar amb aquesta primera ubicació, però després acabar la mala sort al final.
Així que això no és una constant temps sant grial per a nosaltres.
Aquest enfocament dels elements d'inserció en una estructura de dades anomenada hash
taula no sembla ser la constant de temps almenys no en el cas general.
Pot delegar en alguna cosa lineal.
>> I què si resolem col · lisions alguna cosa diferent?
Així que aquí està una més sofisticada acostar-se al que és encara
anomenada taula hash.
I als resums, en un apart, el que És a dir és l'índex que
M'he referit abans.
Per a alguna cosa hash pot ser considerat com un verb.
>> Així que si vostè haixix Alice és un nom, una funció hash, per així dir-ho,
ha de retornar un nombre.
En aquest cas és zero si pertany al posició zero, un, si pertany a
ubicació un, i així successivament.
Així que la meva funció hash fins ara ha estat super simple, només mirant a la
primera lletra del nom d'algú.
No obstant això, una funció hash pren com entrada d'algun dada, un
cadena, un enter, el que sigui.
I escup típicament un nombre.
I aquest nombre és on les dades element pertany a una estructura de dades
coneguda aquí com una taula hash.
>> Així que només intuïtivament, es tracta d'una lleugerament diferent context.
En realitat, això es refereix a un exemple aniversari impliquen, si
pot haver tants com 31 dies al mes.
Però, ¿què aquesta persona decideix fer en cas d'una col · lisió?
Context sent ara, no és un xoc de noms, però una col · lisió dels aniversaris,
si dues persones tenen la mateixa data de naixement en el 2 d'octubre, per exemple.
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Sí, així que aquí tenim l'aprofitament de les llistes enllaçades.
Així es veu una mica diferent que traiem abans.
Però sembla que tenim un array a la banda esquerra.
Això és un índex, per no raó en particular.
Però segueix sent una matriu.
És una matriu de punters.
I cada un d'aquests elements, cadascun dels aquests cercles o barres - la barra
que representa null - cada un d'aquests punters és aparentment apunten
quina estructura de dades?
Una llista enllaçada.
>> Així que ara tenim la capacitat de codificar en el nostre programa
la mida de la taula.
En aquest cas, sabem que mai cal més de 31 dies en un mes.
Tan difícil de codificar un valor com 31 es raonable en aquest context.
En el context dels noms, difícil de codificació 26 no és raonable que la gent
només noms comencen amb, per exemple, l'alfabet de l'A a la Z. participació
>> Podem ficar a tots en què les dades estructura, sempre que, quan arribem a
col · lisió, no posem els noms aquí, que en lloc de pensar en aquestes cèl · lules
no com a propis cadenes, però com punters a, per exemple, Alice.
I després Alice pot tenir un altre punter a un altre nom que comenci amb
A. I Bob realitat va per aquí.
>> I si hi ha un altre nom que comença amb B, acaba aquí.
I així cada un dels elements d'aquest taula dos, si hem dissenyat aquest 1
poc més intel · ligentment -
anem -
si hem dissenyat aquest una mica més intel · ligentment, ara es converteix en un conjunt de dades d'adaptació
estructura, on no hi ha límit físic de la quantitat d'elements que es poden inserir
en ella, perquè si vostè té una col · lisió, això està bé.
Només has d'anar endavant i afegir-lo al el que vam veure fa poc era
coneguda com una llista enllaçada.
>> Bé, fem una pausa per un moment.
Quina és la probabilitat d'una col · lisió en el primer lloc?
Bé, potser estic més pensant, potser Jo sóc més de l'enginyeria d'aquest problema,
perquè saps què?
Sí, puc arribar a arbitrària exemples de la part superior del meu cap, com
Allison i Aaron, però en realitat, donada una distribució uniforme dels
entrades, és a dir algunes insercions aleatòries en una estructura de dades, el que realment és
la probabilitat d'una col · lisió?
Doncs resulta que, en realitat és molt alta.
Permetin-me generalitzar aquest problema és com aquest.
>> Així que en una habitació de n CS50 estudiants, el que és la probabilitat que almenys
dos estudiants de l'habitació tenir la mateixa data de naixement?
Així que no ho. uns pocs Hund -
200, 300 persones aquí i diversos centenars de persones al país avui en dia.
Així que si volia que preguntar-nos què és la probabilitat que dues persones
en aquesta sala que té el mateix aniversari, podem resoldre això.
I jo pretenc en realitat hi ha dos les persones amb el mateix aniversari.
>> Per exemple, algú té aniversari avui?
Ahir?
Demà?
Molt bé, així que se sent com que vaig a haver de fer això 363 o així més
vegades per esbrinar realment a terme Si tenim una col · lisió.
O podríem fer això matemàticament en lloc de tediosament
fent això.
I proposar la següent.
>> Així que proposo que podríem modelar el probabilitat que dues persones tinguin el
mateix dia que la probabilitat d'1 menys la probabilitat de no tenir-ne un
el mateix aniversari.
Així que per aconseguir això, i això és només el forma elegant d'escriure això, per a la
primera persona a l'habitació, ell o ella pot tenir qualsevol de la possible
aniversari suposant 365 dies de l'any, amb perdó de les persones amb
l'aniversari nombre 29 de febrer.
>> Així que la primera persona en aquesta sala és gratis per tenir qualsevol nombre d'aniversari
de les 365 possibilitats perquè farem que 365 dividit per 365,
que és un.
La següent persona a l'habitació, si l'objectiu és evitar una col · lisió, només pot
tenir el seu aniversari en forma molts dies diferents possibles?
364.
Així que el segon terme d'aquesta expressió és essencialment és fer que les matemàtiques per a nosaltres
restant Configuració d'un dia possible.
I a continuació, el dia següent, el dia següent, la dia següent fins al nombre total
de persones a l'habitació.
>> I si considerem a continuació, què és, llavors, la probabilitat que no totes les persones tinguin
aniversari únics, però de nou 1 menys que, el que tenim és una expressió
que pot molt capritxosament aquest aspecte.
Però és més interessant a veure visualment.
Aquest és un gràfic on en l'eix x és el nombre de persones a l'habitació, el
nombre d'aniversari.
A l'eix i és la probabilitat d'una col · lisió, dues persones
que té el mateix aniversari.
>> I el menjar per emportar d'aquesta corba és que tan aviat com s'arriba a rebre 40
estudiants, que estan fent a una probabilitat del 90% combinatorically de dos
persones o més tenen el mateix aniversari.
I una vegada que arribi a agradar 58 persones és gairebé el 100% d'una ocasió els dos
persones a la sala van a tenir la mateix dia, tot i que no hi ha
365 o 366 possibles cubs i només 58 persones a la sala.
Només estadísticament és molt probable que aconseguir col · lisions, que en definitiva
motiva aquesta discussió.
Que fins i tot si aconseguim extravagàncies, i començar a tenir aquestes cadenes, seguim sent
tindrà col · lisions.
>> Així que planteja la pregunta, quin és el cost de fer insercions i delecions
en una estructura de dades com aquest?
Bé, permetin-me proposar -
i m'ho dius a mi tornar a la pantalla durant aquí - si tenim n elements en el
llista, pel que si estem tractant d'inserir n elements, i tenim
quants cubs total de?
Diguem que 31 cubs en total en el cas dels aniversaris.
Quina és la longitud màxima d'un potencialment d'aquestes cadenes?
>> Si de nou no hi ha 31 possibles aniversari en un mes determinat.
I només estem aglutinació tots -
En realitat això és un exemple ximple.
Farem 26 al seu lloc.
Així que si realment tenen les persones els noms començar amb l'A a la Z, el que dóna
som 26 possibilitats.
I estem utilitzant una estructura de dades com el que acabem de veure, pel que tenim
una matriu de punters, cadascun dels quals apunta a una llista enllaçada que l'
primera llista és de tots amb el nom d'Alice.
La segona llista és tota la nom que comencin amb A, a partir
amb B, i així successivament.
>> Quina és la durada probable de cadascuna de aquestes llistes si assumim un bonic i net
distribució dels noms de l'A a la Z a través de l'estructura de dades de conjunt?
No hi ha n persones en l'estructura de dades dividit per 26, si estan ben
distribuïts a la totalitat estructura de dades.
Per tant la longitud de cada un d'aquests cadenes és n dividit per 26.
Però en notació O gran, què és això?
Què és això en realitat?
Així que no deixa de ser n, oi?
Com hem dit en el passat, uf que es divideix per 26.
Sí, en realitat és més ràpid.
No obstant això, en teoria, no és fonamentalment tot el que més ràpid.
>> Així que no sembla que tot el que molt més a prop d'aquest sant grial.
De fet, això és només el temps lineal.
Heck, en aquest punt, per què no fem nosaltres només ha d'utilitzar una gran llista enllaçada?
Per què no només ha d'utilitzar una gran matriu per emmagatzemar els noms dels
tots a la sala?
Bé, hi ha encara alguna cosa convincent sobre una taula hash?
Hi ha encara alguna cosa convincent sobre una estructura de dades
que s'assembla a això?
Est.
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Sí, una vegada i una altra si és només un algorisme de temps lineal, i un
estructura de dades de temps lineal, per què no ho faig jo simplement emmagatzemar el nom de tots en una gran
matriu o en una llista enllaçada gran?
I deixar de fer CS molt més difícil del que ha de ser?
Què és convincent sobre això, fins i tot encara que em rasqui la treu?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Insercions no ho són?
Car ja.
Així insercions potencialment podria encara ser constant de temps, fins i tot si les dades
estructura són aquestes, una sèrie de indicadors, cadascun dels quals està apuntant a
potencialment una llista enllaçada.
Com pots aconseguir constant temps d'inserció dels noms?
S'adhereixen a la part davantera, la dreta?
>> Si sacrifiquem un objectiu de disseny de abans, on ens volíem mantenir
el nom de tots, per exemple, classificar, o la totalitat dels nombres en l'escenari ordenats,
Suposem que tenim un llista enllaçada sense classificar.
Només ens costa un o dos passos, com en el cas de Ben i Brian
abans, per inserir un element en el principi de la llista.
Així que si no ens preocupem de la classificació totes dels noms que comencin amb A o la totalitat
els noms que comencen amb B, que encara pot aconseguir la inserció de temps constant.
Ara, mirant a Alice o Bob o qualsevol nom més en general segueix sent què?
És gran O de n dividit per 26, al cas ideal, on tothom té un aspecte uniformement
distribuïda, on hi ha el major número d'A ja que hi ha Z, que és probablement
poc realista.
Però això segueix sent lineal.
>> Però aquí tornem al punt de la notació asimptòtica ser
teòricament cert.
Però en el món real, si afirmo que el meu programa pot fer alguna cosa 26 vegades
més ràpid que el teu, el programa vas a preferir l'ús de?
Teva o la meva, que és 26 vegades més ràpid?
Sent realistes, la persona que és 26 vegades més ràpid, fins i tot si teòricament
nostres algoritmes s'executen en el mateix execució asimptòtica temps.
>> Permetin-me proposar a una altra persona solució en conjunt.
I si això no bufi la seva ment, estem fora de les estructures de dades.
Així que això és un trienni -
classe de nom estúpid.
Ve de recuperacions, i la paraula s'escriu trie, t-r-i-i, a causa d'
recuperació de golf sona com triennis.
Però aquesta és la història de la paraula trie.
>> Així que un trienni és de fet una espècie d'arbre, i també és un joc de la paraula.
I encara que vostè no pot veure-ho del tot amb aquesta visualització, 1 trie és un
arbre estructurat, com un arbre de la família amb un avantpassat a la part superior i un munt
dels néts i besnéts com les fulles al fons.
Però cada node en un trienni és una matriu.
I està en una matriu - i anem a simplificar en excés per un moment - és una
matriu, en aquest cas, de mida 26, on cada node de nou és una matriu de mida
26, on l'element d'ordre zero en aquest matriu representa A, i l'últim
element en cada un d'aquests matriu representa Z.
>> Així que proposo, doncs, que aquestes dades estructura, coneguda com un trienni, pot ser
utilitzat també per emmagatzemar paraules.
Ens vam veure fa un moment com podríem emmagatzemar És a dir, o en aquest cas els noms, i
Vam veure anteriorment com podem emmagatzemar números, però si ens centrem en els noms o cadenes
aquí, fixa't el que és interessant.
Jo sostinc que el nom és Maxwell a l'interior d'aquesta estructura de dades.
On veu vostè Maxwell?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: A l'esquerra.
Així que el que és interessant amb aquestes dades estructura és en lloc d'emmagatzemar la
cadena M-A-X-W-E-L-L barra invertida zero, tot contigua, el que en lloc de fer
està seguint.
Si aquest és un trie com a estructura de dades, cada un dels nodes és de nou una matriu,
i desitja emmagatzemar Maxwell, primer índex i així node de l'arrel, de manera que
dir-ho, el primer node, en la posició M, la dreta, per la
més o menys en el centre.
I a partir d'aquí, se segueix una punter a un nen nodes, per dir-ho.
Així doncs, en el sentit d'arbre, vostè segueix cap avall.
I que et porten a un altre node A l'esquerra, que és
només un altre array.
>> I després, si voleu emmagatzemar Maxwell, vostè troba el punter que representa
A, que és aquest d'aquí.
Després d'anar al següent node.
I noti - aquesta és la raó de la foto una mica enganyós -
aquest node mirada súper petit.
Però a la dreta d'aquest és Y i Z. És que l'autor ha truncat la
foto, així que en realitat veure les coses.
En cas contrari aquesta imatge seria enormement àmplia.
Així que ara vostè índex en lloc X, llavors W, A continuació, E, L i després, a continuació, L. Llavors, què
aquesta curiositat?
>> Bé, si farem servir aquest tipus de nou assumir la forma d'emmagatzemar una cadena en un
estructura de dades, vostè encara ha de essencialment marcar en les dades
estructura que una paraula acaba aquí.
En altres paraules, cada un d'aquests nodes d'alguna manera ha de recordar que
realment seguit tots aquests punters i estan deixant una mica
molla de pa a la part inferior d'aquest aquí estructura per indicar M-A-X-W-E-L-L és
de fet, en aquesta estructura de dades.
>> Així que podríem fer-ho de la següent manera.
Cadascun dels nodes de la imatge que acaba de serra té un, una matriu de mida 27.
I és ara de 27 anys, ja que en conjunt P 6, farem realitat li donem un apòstrof,
perquè puguem tenir noms com O'Reilly i altres amb apòstrofs.
Però mateixa idea.
Cadascun d'aquests elements en el array apunta a una struct
node, de manera que només un node.
Així que això és molt reminiscent de la nostra llista enllaçada.
>> I després tinc un booleà, que ho faré truqui paraula, que només serà
cert si una paraula acaba en aquest node a l'arbre.
Es representa efectivament la petita triangle que vam veure fa un moment.
Així que si una paraula acaba en aquest node al arbre, aquest camp paraula serà veritat,
que és conceptualment marcant o estem dibuixant aquest triangle, sí que hi ha
és una paraula aquí.
>> Així que aquest és un trienni.
I ara la pregunta és, què és el seu temps d'execució?
És gran O de n?
És alguna cosa més?
Bé, si vostè té n els noms d'aquestes dades estructura, Maxwell és només un
ells, el que és el temps d'execució de la inserció o la recerca de Maxwell?
Quin és el temps d'execució de la inserció de Maxwell?
Si hi ha n altres noms ja a taula?
Sí?
>> ESTUDIANT: [inaudible].
>> ALTAVEU 1: Sí, és la longitud del nom, oi?
Així que M-a-x-w-e-l-l així que se sent com això algorisme és O gran de set.
Bé, és clar, el nom variarà en longitud.
Potser és un nom curt.
Potser és un nom més llarg.
Però el que és clau aquí és que és un nombre constant.
I potser en realitat no és constant, però déu, si essent realistes, en un
diccionari, és probable que hi hagi algun límit sobre el nombre de lletres en una
nom de la persona en un país en particular.
>> I pel que podem assumir que és un valor constant.
No sé el que és.
És probable que sigui més gran que creiem que és.
Perquè sempre hi ha un racó cas amb un nom llarg boja.
Així que anem a cridar k, però segueix sent un constant presumiblement, perquè cada
nom en el món, almenys en una país en particular, és que la longitud o
més curt, pel que és constant.
Però quan hem dit alguna cosa és gran O d'un valor constant, què és això
realment equivalent a?
Aquesta és realment la mateixa cosa dient que la constant de temps.
>> Ara estem una mica trampa, no?
Estem una mica aprofitant alguna teoria aquí per dir que així, l'ordre de k és
realment només demanar un, i és la constant de temps.
Però el que realment és.
A causa de que la idea clau aquí és que si tenim n noms ja en aquest
estructura de dades, i d'inserció Maxwell, és la quantitat de temps que ens porti a
inseriu Maxwell a tots els afectats la quantitat de gent una altra
es troben en l'estructura de dades?
No sembla ser.
Si tingués mil milions d'més elements a aquesta trie, i després inserir Maxwell, es
es veu afectat en absolut?
No
I això és a diferència de qualsevol de les dades del dia estructures que hem vist fins ara, on
el temps d'execució de l'algorisme és completament independent de la quantitat de
material és o no és ja en aquesta estructura de dades.
>> I així, amb aquesta li produeix ara és una oportunitat per p conjunt de sis, que
nou implica la implementació de la seva pròpia corrector ortogràfic, la lectura en 150.000
És a dir, la millor manera d'emmagatzemar aquesta no és necessàriament evident.
I encara que he aspirat a trobar el sant grial, jo no
afirmen que un trienni és.
De fet, una taula hash pot molt bé arribar a ser molt més eficient.
Però aquests són només -
això és només una de les decisions de disseny vostè haurà de fer.
>> Però en acabar anem a prendre 50 o més segons per fer una ullada al que està
amb antelació la propera setmana i més enllà que la transició a partir d'aquesta línia d'ordres
món si els programes en C per coses web base i llenguatges com PHP i
JavaScript i la pròpia Internet, protocols com HTTP, que vostè ha
es dóna per fet des de fa anys ara, i el més teclejat tots els
dia, potser, o vist.
I anem a començar a pelar la capes del que és l'internet.
¿I quin és el codi que subjacent a les eines actuals.
Així que 50 segons d'aquest teaser aquí.
Et dono Guerrers de la xarxa.
>> [REPRODUIR VIDEO]
>> -Ell va venir amb un missatge.
Amb un protocol de tots els seus.
Va arribar a un món de tallafocs cruels, routers indiferents i perills lluny
pitjor que la mort.
És ràpid.
És fort.
És TCPIP.
I té la seva direcció.
Guerrers de la xarxa.
>> [FI REPRODUCCIÓ DE VÍDEO]
>> ALTAVEU 1: Així és com l'internet es treballarà a partir de la setmana que ve.