[REPRODUCCIÓ DE MÚSICA]
ALTAVEU 1: D'acord.
Tothom la benvinguda de nou a la secció.
Espero que tots vostès estiguin amb èxit recuperat de la seva concurs
des de la setmana passada.
Sé que és una mica boig de vegades.
Com deia abans, si estàs dins de la desviació estàndard,
realment no et preocupis per això, sobretot per a una secció menys còmode.
Això és on ha d'estar.
>> Si ho va fer molt bé, llavors impressionant.
Felicitacions a vostè.
I si vostè sent que necessita una mica més d'ajuda, si us plau
no dubti a arribar a qualsevol dels TFS.
Tots estem aquí per ajudar.
>> És per això que ensenyem.
És per això que sóc aquí tots els dilluns per a vostè nois i en l'oficina hores els dijous.
Així que si us plau no dubti en fer-m'ho saber si vostè està preocupat sobre qualsevol cosa
o si hi ha alguna cosa en el concurs que realment t'agradaria abordar.
>> Així que l'ordre del dia d'avui és tot sobre les estructures de dades.
Alguns d'aquests són només serà just per ajudar a familiaritzar-se amb elles.
Alguna vegada no pot aplicar en aquesta classe.
Alguns d'ells es vol, com per a la seva conjunt de processadors ortografia.
>> Vostè té la seva opció entre taules hash i tries.
Així que sens dubte ens anem sobre aquells.
Serà, sens dubte més de classe d'una secció d'alt nivell avui en dia, però,
perquè hi ha una gran quantitat d'ells, i si entrem en els detalls d'implementació
en tots ells, que no ho faria fins i tot aconseguir a través de les llistes enllaçades
i potser una mica de taules hash.
>> Així que tinguin paciència amb mi.
No estarem fent tant de codificació d'aquest temps.
Si vostè té alguna pregunta sobre ella o desitja veure-ho en pràctica
o provar per tu mateix, Sens dubte, recomano
anar a study.cs50.net, que té exemples de tots aquests.
Tindrà les meves presentacions en PowerPoint amb les notes que ens
tendeixen a utilitzar, així com una mica de programació exercicis, sobretot per a les coses
com llistes enllaçades i binari arbres piles i senyals.
Tan poc nivell més alt, el que podria ser bo per a vostès.
>> Així que amb això, anem a començar.
I també, concursos sí-.
Crec que la majoria de vostès que estan en la meva secció té les seves proves,
però ningú ve a o alguna raó vostè no fer-ho, són aquí mateix a la part davantera.
>> Així vinculat llistes.
Sé que aquest tipus de va abans de fer una còpia del seu qüestionari.
Això va ser la setmana anterior que ens assabentem d'això.
Però en aquest cas, només haurem de anar una mica més en profunditat.
>> Llavors per què podríem triar un llista enllaçada a través d'una matriu?
Què els distingeix?
Sí?
>> AUDIÈNCIA: Vostè pot ampliar una vinculada llistar versus grandària fixa d'una matriu.
ALTAVEU 1: Dret.
Una matriu ha fixat mida mentre que una llista enllaçada té una mida variable.
Així que si no sabem com molt que volem emmagatzemar,
una llista enllaçada ens dóna una gran manera de fer això perquè podem simplement
afegir en un altre node i afegir en un altre node i afegir en un altre node.
Però el que podria ser una solució de compromís?
Algú recorda el trade-off entre matrius i llistes enllaçades?
Mmhmm?
>> AUDIÈNCIA: Vostè ha de anar a través de tot el camí
a través de la llista enllaçada trobar un element en una llista.
En una matriu, es pot simplement trobar un element.
>> ALTAVEU 1: Dret.
Així que amb arrays--
>> AUDIÈNCIA: [inaudible].
>> ALTAVEU 1: Amb els arranjaments, tenim el que s'anomena accés aleatori.
Significa que si volem el que és mai el cinquè punt de la llista
o el cinquè punt de la nostra matriu, que només pot agafar.
Si es tracta d'una llista enllaçada, tenim per recórrer, no?
Així que l'accés a un element en una matriu és la constant de temps,
mentre que amb una llista enllaçada que ho faria més probable és que el temps lineal perquè potser
el nostre element és tot el camí al final.
Hem de buscar a través de tot.
Així, amb totes aquestes dades estructures que anem
a passar una mica més de temps en, ¿Quins són els punts positius i negatius.
Quan podríem voler utilitzar un sobre l'altre?
I això és una cosa de la El més gran per emportar.
>> Així que tenim aquí la definició d'un node.
És com un dels elements la nostra llista enllaçada, oi?
Així que estem tots familiaritzats amb les nostres estructures typedef,
que ens vam anar a la revisió última vegada.
Era bàsicament la creació de un altre tipus de dades que podríem utilitzar.
>> I en aquest cas, és algun node que se celebrarà en algun sencer.
I llavors quina és la segona part aquí?
Qualsevol persona?
>> AUDIÈNCIA: [inaudible].
>> ALTAVEU 1: Sí.
És un punter al següent node.
Així que això es deu en realitat ser aquí dalt.
Això és un punter del tipus de node a la següent cosa.
I això és el que abasta la nostra node.
Refredar.
>> Molt bé, així que amb la recerca, ja que estàvem només dir abans de la mà, si estàs
anar a cercar a través de, vostè ha de repetir en realitat
a través de la seva llista enllaçada.
Així que si estem buscant el nombre 9, començaríem al nostre cap
i que ens assenyala al principi de la nostra llista enllaçada, oi?
I diem, bé, ho fa node conté el número 9?
No?
>> Molt bé, aneu a la següent.
Segueix-lo.
Conté el número 9?
No
Seguiu el següent.
>> Així que hem de recórrer en realitat a través de la nostra llista enllaçada.
No podem anar directament a on 9 és.
I si vostès realment vol veure alguns pseudo-codi allà dalt.
Tenim alguna funció de cerca aquí que pren en-- què es necessita en?
Què en penses?
Tan fàcil un.
Què és això?
AUDIÈNCIA: [inaudible].
ALTAVEU 1: El nombre que estem buscant.
Dreta?
I què seria el que correspondria a?
És un punter a?
>> AUDIÈNCIA: Un node.
>> ALTAVEU 1: Un node a la llista que estem veient, no?
Així que tenim alguns nodes són punter aquí.
Aquest és un punt que va a realment recórrer la nostra llista.
Ens vam proposar que potser a la llista perquè això és només
establint que igual a la començar de la nostra llista enllaçada.
>> I si bé no és NULL, mentre que encara tenim coses a la nostra llista,
comprovar per veure si aquest node té el nombre que estem buscant.
Retorna veritable.
En cas contrari, actualitzar-la, no?
>> Si és NULL, sortim de la nostra while i return false
perquè això significa que no hem trobat.
Tothom aconsegueix com funciona?
Okay.
>> Així que amb la inserció, es tenir tres formes diferents.
Pot anteposar, pot annexar i es pot inserir en assortiment.
En aquest cas, estem farem un prefix.
Algú sap com els tres casos poden ser diferents?
>> Així que anteposar vol dir que es posa que a la part davantera de la seva llista.
Així que això significaria que no importa el que el seu node és, no importa
el que el valor és, vas per posar-lo aquí davant, d'acord?
Serà la primera element en la seva llista.
>> Si annexa que, va per anar a la part de darrere de la seva llista.
I s'insereixen en assortiments vol dir que ets posarà realment al lloc
on manté la seva llista enllaçada ordenada.
Una vegada més, com s'utilitza aquests i quan s'utilitza
ells variaran depenent del seu cas.
Si no necessita ser ordenats, posi per davant tendeix
a ser el que la majoria de la gent utilitzar perquè no ho fa
haver de passar per tota la llista per trobar al final per afegir a, oi?
Vostè només pot enganxar-lo directament.
>> Així que anem a anar a través d'un inserció 1 en aquest moment.
Així que una cosa que vaig a Recomano altament a aquest conjunt de processadors
és dibuixar les coses, com sempre.
És molt important actualitzar seus punters en l'ordre correcte
perquè si ells actualitzar una mica fora de lloc,
vostè va a acabar perdre parts de la seva llista.
>> Així, per exemple, en aquest cas, estem comptant el cap a punt just a 1.
Si només fem sense guardar aquest 1,
no tenim idea del que 1 ha d'apuntar a ara
perquè hem perdut el que el cap va assenyalar.
Així que una cosa que cal recordar quan estàs fent un prepend
és salvar el que el punts del cap a la primera,
a continuació, tornar a assignar, i després actualitzar qual cosa el seu nou node hauria d'apuntar.
En aquest cas, aquesta és una manera de fer-ho.
>> Així que si haguéssim fet així en el qual només reassignats cap,
perdem bàsicament la nostra llista completa, no?
Una manera de fer-ho és tenir un punt de següent i, a continuació, tenir el cap a punt 1.
O vostè pot fer alguna cosa així com el l'emmagatzematge temporal, la qual vaig parlar sobre.
>> Però la reassignació de la seva punters en l'ordre correcte
serà molt, molt important per a aquest conjunt de processadors.
En cas contrari, vostè va a tenir un hash taula o una oportunitat que només serà
només una part de les paraules que volen i després you're-- mmhmm?
AUDIÈNCIA: Quin va ser el temporal El emmagatzematge que parlaves?
ALTAVEU 1: L'emmagatzematge temporal.
Així que, bàsicament, una altra manera vostè pot fer això
es guardi el cap d'alguna cosa, com emmagatzemar la variable temporal.
Assigneu a 1 i a continuació, actualitzeu 1 per assenyalar
al que el cap utilitza per apuntar.
D'aquesta manera és òbviament més elegant, ja que
no necessiten un valor temporal, però només oferir una altra manera de fer-ho.
I que en realitat tenen una mica de codi per això.
Així, per llista enllaçada, ens en realitat tenen una mica de codi.
Així que inserir aquí, això es anteposant.
Així que això entra en ell al capdavant.
>> Així que el primer, cal crear el seu nou node, per descomptat,
i comprovi que no NULL.
Sempre bo.
I llavors vostè necessita per assignar els valors.
Cada vegada que es crea un nou node, no saben el que està apuntant a la següent,
pel que desitja inicialitzar a NULL.
Si no acaben apuntant a alguna cosa una altra cosa, es va reassignar i que està bé.
Si és el primer a la llista, que necessita
per assenyalar a NULL perquè aquest és el final de la llista.
>> Així que per inserir, veiem aquí s'assigna el següent valor del nostre node
a ser el que és el cap, que és el que teníem aquí.
Això és el que acabem de fer.
I llavors estem assignant el cap a punt al nostre nou node, perquè recordi,
cap nova punter a un node, i això és exactament el que és el cap.
Això és exactament per això que tenir aquesta fletxa d'accés.
Fresc?
Mmhmm?
>> AUDIÈNCIA: Hem de inicialitzar nou al costat de NULL en primer lloc,
o podem simplement inicialitzar al capdavant?
>> ALTAVEU 1: Nou propera necessita ser NULL per començar
perquè vostè no sap on serà.
A més, això és una espècie de De la mateixa manera que un paradigma.
Es configura igual a NULL només per fer Assegureu-vos que totes les bases estan cobertes
abans de fer qualsevol canvi de destinació de manera que vostè sempre té la garantia que així serà
estar apuntant a un valor específic front com un valor de les escombraries.
Perquè, sí, assignem nou següent de forma automàtica,
però és més com un bona pràctica inicialitzar
d'aquesta manera i després reassignar.
>> OK, així doblement enllaçada llistes ara.
Què pensem?
El que és diferent amb doblement enllaçada llistes?
>> Així que a les nostres llistes enllaçades, podem només es mouen en una direcció, ¿no?
Només tenim al costat.
Només podem seguir endavant.
>> Amb una llista doblement enllaçada, també podem moure cap enrere.
Així que no només tenim la nombre que volem emmagatzemar,
tenim on apunta la següent i en el qual només venim.
Així que això permet alguns millor recorregut.
>> Així nodes doblement enllaçats, molt similar, no?
L'única diferència és que ara tenir una banda i una anterior.
És l'única diferència.
>> Així que si haguéssim de anteposar o append-- nosaltres no tenen cap codi per això aquí--
però si anés a tractar de inserir, l'important
és el que necessita per fer assegurar-se que està assignant
tant la seva anterior i el seu següent punter correctament.
Així que en aquest cas, ho faria no només inicialitzar següent,
inicialitzar anterior.
Si estem al capdavant de la llista, no només fer que el cap igual nova,
però deu el nostre nou anterior apuntar al capdavant, oi?
>> Aquesta és l'única diferència.
I si vols més pràctica amb aquests amb llistes enllaçades, amb inserció,
amb la supressió, amb inserció en una llista d'assortiment,
si us plau visiti study.cs50.net.
Hi ha un munt de grans exercicis.
El recomano.
Tant de bo haguéssim tingut temps per anar a través d'ells però hi ha una gran quantitat d'estructures de dades
aconseguir a través.
>> Acceptar, de manera que les taules hash.
Aquest és probablement el més poc útil per al conjunt de processadors
aquí perquè vostè serà la implementació d'un d'aquests, o un intent.
M'agrada molt les taules hash.
Són bastant fresc.
>> Així que, bàsicament, el que que passa és una taula hash
és quan realment necessitem ràpida inserció, eliminació i recerca.
Aquestes són les coses que estem prioritzant en una taula hash.
Poden ser bastant gran, però com veurem amb tries,
hi ha coses que són molt més grans.
>> Però, bàsicament, tot un hash taula és una funció hash
que et diu que cub per posar cadascun de les seves dades, cadascun dels seus elements a.
Una manera simple de pensar en una taula hash és que és només cubs de coses,
Oi?
Així que quan vostè està ordenant les coses per com la primera lletra del seu nom,
que és una cosa així com una taula hash.
>> Així que si jo fos a grup de nois és en grups de tot el que de nom comença
amb A per aquí, o qui sigui l'aniversari és al gener, febrer, març,
el que sigui, que és efectivament la creació d'una taula hash.
És només la creació de cubs que ordenar els elements en
per tu per trobar més fàcil.
Així d'aquesta manera quan necessito per trobar un de vosaltres,
Jo no he de buscar a través de cada un dels seus noms.
Jo puc ser com, oh, jo sé que L'aniversari de Danielle és en--
AUDIÈNCIA: --April.
ALTAVEU 1: abril.
Així que em veig en la meva abril cub, i amb una mica de sort,
ella serà l'única en la que hi ha i el meu temps era constant en aquest sentit,
mentre que si he de buscar a través d'un munt de gent,
que prendrà molt més temps.
Així taules hash són realment només cubs.
Una manera senzilla de pensar-hi.
>> Així que una cosa molt important sobre una taula hash és una funció hash.
Així que les coses que acabo de parlar, igual que la seva primera lletra del seu nom
o el seu mes d'aniversari, aquestes són idees que
realment correlacionar a una funció hash.
És només una manera de decidir quina vostè debades és EL element entra en, d'acord?
Així que per a aquest conjunt de processadors, pot mirar cap amunt gairebé qualsevol funció hash que desitja.
>> No ha de ser la seva.
Hi ha alguns realment fresc fora cal fer tot tipus de boig matemàtiques.
I si vol fer la seva corrector ortogràfic súper ràpid,
Sens dubte, mirar un d'aquests.
>> Però també n'hi ha els simples, com el còmput
la suma de les paraules, com cada lletra té un nombre.
Calculeu la suma.
Que determina el cub.
També tenen les més fàcils que són igual que tots els d'un aquí,
tots els de la B és aquí.
Qualsevol d'aquests.
>> Bàsicament, només se li diu que índex de la matriu del seu element ha d'entrar.
Només decidir el bucket-- tot és una funció de hash és.
Així que aquí tenim un exemple que és només la primera lletra de la cadena
que m'estava parlant.
>> Així que tens una mica de hash que és només la primera lletra de la cadena de menys A,
que li donarà una mica de nombre entre 0 i 25.
I el que vols fer és assegurar-se que això representa
la mida de la seva picada table-- quants cubs hi ha.
Amb molts d'aquests funcions hash, que són
serà la devolució de valors que podrien estar molt per sobre del nombre de cubs
que vostè realment té en la seva taula hash,
per la qual cosa necessita per fer Segur i mod per aquells.
En cas contrari, dirà, oh, ha de ser debades 5000
però només té 30 cubs en la seva taula hash.
I, per descomptat, tots sabem que és donarà lloc a alguns errors de bojos.
Així que assegureu-vos de mod pel mida de la taula hash.
Refredar.
Així col·lisions.
Estan tots bé fins ara?
Mmhmm?
>> AUDIÈNCIA: Per què es retornar un valor tan massiva?
>> ALTAVEU 1: Depenent de l'algoritme que la seva funció hash utilitza.
Alguns d'ells ho farà multiplicació boig.
I és tot sobre aconseguir una distribució uniforme,
pel que fan alguns realment bogeries de vegades.
Això és tot.
Una mica més?
Okay.
>> Així col·lisions.
Bàsicament, com he dit abans, en el millor dels casos,
qualsevol cub miro a és tindrà una cosa,
així que no he de mirar a tots, oi?
Jo bé sé que hi és o és no, i això és el que realment volem.
Però si tenim desenes de milers de els punts de dades i menys d'aquest nombre
de cubs, que tindrem col·lisions on finalment alguna cosa
es va a haver d'acabar en un cub que ja compta amb un element.
>> Així que la pregunta és, què Què fem en aquest cas?
Què fem?
Ja tenim alguna cosa allà?
Ens fem una ullada?
>> No
Hem de mantenir els dos.
Així que la forma en què solen fer-ho és el que?
Quina és l'estructura de dades que acabem de parlar?
AUDIÈNCIA: llista enllaçat.
ALTAVEU 1: Una llista enllaçada.
Així que ara, en lloc de cada un d'aquests cubs només tenir un element,
que contindrà una llista enllaçada de els elements que van ser ordenada en ella.
Bé, no tothom classe d'aquesta idea?
Com que no podíem tenir una matriu perquè no sabem quantes coses
hi seran.
Una llista enllaçada ens permet tenir només el nombre exacte que
es hash en aquest cub, oi?
>> Així sondeig lineal és bàsicament aquesta idea--
és una manera de fer front a una col·lisió.
El que pot fer és si, en aquest cas, baia va ser ordenada en 1
i ja tenim alguna cosa aquí, només
seguir baixant fins a trobar una ranura buida.
Aquesta és una manera de manejar la situació.
L'altra manera de gestionar que és amb el que acabem de
called-- el vinculat llista es diu encadenament.
>> Així que aquesta idea funciona si la seva taula hash vostè pensa
és molt més gran que conjunt de dades o si
volen tractar de minimitzar l'encadenament fins que sigui absolutament necessari.
Així que una cosa és lineal sondeig òbviament significa
que la seva funció hash no és tan útil
perquè vas a acabar amb la seva funció hash, arribant a un punt,
li LINEAL sondeja fins algun lloc que està disponible.
Però ara, per descomptat, qualsevol cosa una altra cosa que acaba allà,
vostè va a haver de buscar fins i tot més avall.
>> I hi ha molt més costa de recerca que
entra en la introducció d'un element en la seva taula hash ara, oi?
I ara que i tractes de trobar baia de nou, vas a hash d'ella,
i que dirà, oh, mira al cub 1,
i no serà en galleda 1, per la qual cosa és
va a haver de travessar per la resta d'aquests.
Així que de vegades és útil, però en la majoria dels casos,
direm que L'encadenament és el que vols fer.
>> Així que parlem d'això abans.
Em vaig posar una mica per davant de mi mateix.
Però l'encadenament és bàsicament que cada cub en la seva taula hash
és només una llista enllaçada.
>> Així que d'una altra manera, o més tècnic manera, pensar en una taula hash
és que és només un arranjament de les llistes enllaçades, que
quan vostè està escrivint el seu diccionari i vostè està tractant de carregar,
pensar-hi com una varietat de llistes enllaçades
farà que sigui molt més fàcil per inicialitzar.
>> AUDIÈNCIA: Així taula hash té un mida per defecte,
com un [inaudible] de cubs?
>> ALTAVEU 1: Dret.
Per tant, té un nombre determinat de cubs que determine--
que vostès han sentir-se lliure per jugar.
Pot ser molt bé a veure què passa
a mesura que canvia el seu nombre de cubs.
Però sí, té una establir el nombre de cubs.
El que li permet ajustar com molts elements que vostè necessita
és aquest encadenament separat on han vinculat les llistes a cada cub.
Això vol dir que la seva taula hash serà exactament la mida
que vostè necessita que sigui, no?
Aquest és tot el punt de les llistes enllaçades.
Refredar.
>> Així que tot el món bé allà?
Bé.
Ah.
Què acaba de succeir?
Realment ara.
Suposo que algú m'està matant.
>> Acceptar que entrarem en tries, que són una mica boig.
M'agrada taules hash.
Crec que són molt cool.
Tries són fresques, també.
>> Així que algú recorda el que és una oportunitat?
Vostè hauria d'haver anat més breument en la conferència?
Te'n recordes de classe de com funciona?
AUDIÈNCIA: Només estic assentint que ens vam anar per sobre.
ALTAVEU 1: Nosaltres anem sobre ella.
Bé, realment anirem sobre ella ara és el que estem dient.
>> AUDIÈNCIA: Això és per a un arbre de recuperació.
>> ALTAVEU 1: Sí.
És un arbre de la recuperació.
Impressionant.
Així que una cosa a notar aquí és que nosaltres estan mirant a caràcters individuals
aquí, oi?
>> Així que abans amb la nostra funció de hash, que estaven mirant les paraules en el seu conjunt,
i ara estem buscant més els personatges, no?
Així que tenim Maxwell aquí i Mendel.
Així que, bàsicament, un try-- una manera de pensar d'això és que tots els nivells aquí
és una sèrie de lletres.
Així que aquest és el seu node arrel aquí, oi?
Això té tots els caràcters de la alfabet per a l'inici de cada paraula.
>> I el que vols fer és per exemple, OK, tenim alguna paraula el Sr.
Anem a buscar Maxwell, per la qual cosa anem als punts M. i M a un tot
un altre una matriu en la qual cada paraula, mentre hi hagi
és una paraula que té un com la segona carta,
sempre que no hi ha una paraula que té B com la segona carta,
que tindrà un punter anar a algun lloc array.
>> Probablement no és un paraula que MP alguna cosa,
pel que en la posició P en aquest matriu, que només seria NULL.
Es diria, està bé, no hi ha una paraula que ha seguit d'una M P, d'acord?
Així que si ho pensem bé, cada d'aquestes coses més petites
és en realitat un d'ells grans conjunts de l'A a la Z.
Així que el que podria ser una de les coses que és una espècie d'inconvenient d'una oportunitat?
>> AUDIÈNCIA: Una gran quantitat de memòria.
>> ALTAVEU 1: És una tona de memòria, oi?
Cadascun d'aquests blocs aquí representa 26 espais, 26 element de la matriu.
Així que intenta aconseguir espai increïblement pesat.
>> Però ells són molt ràpids.
Tan increïblement ràpid, però realment espai ineficient.
Tipus d'haver de esbrinar a quin d'ells vol.
Aquests són realment fresc per a la seva conjunt de processadors, però sí tenir una gran quantitat de memòria,
de manera que el comerç fora.
Sí?
>> AUDIÈNCIA: Seria possible la creació d'una oportunitat i després
una vegada hagueu aconseguit la dades en ell que vostè need--
No sé si això té sentit.
Em va a desfer de tot el Caràcters NULL, però a continuació,
no seria capaç d'indexar ells--
>> ALTAVEU 1: Vostè encara els necessiten.
>> AUDIÈNCIA: - de la mateixa manera cada vegada.
ALTAVEU 1: Sí.
Vostè necessita els caràcters NULL perquè Com saber si no hi ha una paraula allà.
Ben no tens alguna cosa que vols?
Okay.
Molt bé, així que anem per anar una mica més
en els detalls tècnics darrere 1 tractar de treballar a través d'un exemple.
>> Acceptar, de manera que aquesta és la mateixa cosa.
Mentre que en una llista enllaçada, la nostra principal tipus de-- quina és la paraula que vull? -
com la construcció de bloc era un node.
En una oportunitat, també tenim un node, però es defineix de manera diferent.
>> Així que tenim alguns bool que representa si una paraula en realitat
existeix en aquesta ubicació, i després tenim una mica de varietat aquí-- o més aviat,
aquest és un punter a una sèrie de 27 caràcters.
I això és per a, en aquest cas, aquesta 27-- Estic segur que tots vostès són com, espero,
hi ha 26 lletres en l'alfabet.
Per què tenim 27?
>> Així que depenent de la manera d'implementar això,
això és d'un conjunt de processadors que permetre apòstrofs.
Així que per això l'un extra.
També tindrà en alguns casos, el terminador nul
s'inclou com una de les personatges que prohibeix ser,
i això és el que verifiquen veure si és el final de la paraula.
Si estàs interessat, visita Vídeo de Kevin a study.cs50,
així com Wikipedia té alguns bons recursos allà.
>> Però anem a anar a través de només una mica de com es pot treballar a través d'un provar
si et donen una.
Així que tenim un super senzill aquí que té la paraula "bat" i "zoom" a ells.
I com veiem aquí, aquest petit espai aquí
representa la nostra bool que diu, sí, aquesta és una paraula.
I llavors això té la nostra matrius de caràcters, no?
>> Així que anem a anar a través de la recerca de "ratpenat" en aquest intent.
Així que comenci per la part superior, a la dreta?
I sabem que B correspon a el segon índex, el segon element
en aquesta matriu, a causa a i b.
Així que aproximadament el segon.
>> I diu, bé, fresc, se segueix que en la següent matriu, ja que si recordem,
no és que cada un d'aquests en realitat conté l'element.
Cadascuna d'aquestes matrius conté un punter, oi?
És una distinció important a fer.
>> Sé que això serà: tries són molt difícil d'aconseguir a la primera vegada,
per la qual cosa fins i tot si aquest és el segona o tercera vegada
i és encara tipus de semblar difícil,
Et prometo que si vas rellotge el matí de nou a curt,
és probable que farà molt més sentit.
Es necessita molt per pair.
Encara de vegades sóc com, espera, el que és una oportunitat?
Com utilitzo això?
>> Així que hem B en aquest cas, que és el nostre segon índex.
Si tinguéssim, per exemple, o c d o qualsevol altra lletra,
hem de mapejar de tornar a l'índex de la nostra matriu que que correspon a.
Així que prendríem com rchar i només restar d'una a Localitzar en un mapa a 0 a 25.
Tothom bé com mapejar els nostres personatges?
Okay.
>> Així que anem a la segona, i que veure que, sí, no és NULL.
Podem passar a aquesta nova matriu.
Així que passem a aquesta propera sèrie aquí.
>> I diem, bé, ara ens que tingui a veure si a és aquí.
És un valor nul o el fa realment avançar?
Així que una es mou realment cap endavant en aquesta sèrie.
I diem, OK, t és la nostra última carta.
Així que anem a la t en l'índex.
I després ens movem cap endavant perquè no hi ha un altre.
I aquest diu bàsicament que, sí, es diu que hi ha una paraula aquí--
que si segueix aquest camí, vostè ha arribat
en una paraula, que sabem que és "ratpenat".
Sí?
>> AUDIÈNCIA: És normal haver de com l'índex 0 i després tenir una espècie en 1
o perquè al final?
>> ALTAVEU 1: No.
Així que si mirem cap enrere en la nostra declaració aquí, és un bool,
pel que és el seu propi element en el seu node.
Així que no és part de la matriu.
Refredar.
Així que quan acabem la nostra paraula i estem en aquesta matriu, el que volem fer
és fer un xec per aquesta és una paraula.
I en aquest cas, seria tornar si.
>> Així que en aquest sentit, sabem que "zoo" - que coneixem com a éssers humans que "zoo" és una paraula,
Oi?
Però es tracti d'aquí seria dir, no, no ho és.
I diria que pel fet que no han designat com una paraula aquí.
Tot i que podem travessar a través d'aquesta matriu,
aquest intent diria que no, zoològic no està en el seu diccionari
perquè nosaltres no tenim designada com a tal.
>> Així que una manera de fer-ho que-- oh, ho sento, aquesta.
Així que en aquest cas, "zoo" no és una paraula, però està en el nostre intent.
Però en aquest, diem que volem que introduir la paraula "bany", el que succeeix
és que seguim through-- b, a, t.
Estem en aquesta matriu, i anem a buscar h.
>> En aquest cas, quan mirar el punter en h,
està apuntant a NULL, d'acord?
Així que a menys que sigui explícitament apuntant a una altra matriu,
vostè assumeix que tots els punters en aquesta matriu estan apuntant a null.
Així doncs, en aquest cas, h està apuntant per anul·lar el que no podem fer res,
per la qual cosa també seria tornar falsa, "bany" no és aquí.
Així que ara estem en realitat va a anar a través de
¿Com podem realment dir que "zoo" és en el nostre intent.
Com ens inserim "zoo" en el nostre intent?
Així que de la mateixa manera que vam començar amb la nostra llista enllaçada, que comencen a l'arrel.
En cas de dubte, comenci a l'arrel d'aquestes coses.
>> I anem a dir, OK, z.
existeix z en això, i ho fa.
Així que vostè està de passar a el seu següent sèrie, d'acord?
I a continuació, en la següent, diem, bé, sí que hi ha o?
Ho fa.
Això de nou.
>> I així, en el nostre proper un, que hem dit, Acceptar, "zoo" ja existeix aquí.
Tot el que necessitem fer és establir aquesta igualtat a la veritable, que no és una paraula allà.
Si haguessis seguit tot fins abans d'aquest punt,
es tracta d'una paraula, de manera que només configurar igual a tals.
Sí?
>> AUDIÈNCIA: Llavors sí que significa que "ba" és una paraula també?
>> ALTAVEU 1: No.
Així que en aquest cas, "ba" obtindríem aquí, diríem que és una paraula,
i encara seria no.
D'acord?
Mmhmm?
>> AUDIÈNCIA: Així que una vegada que es tracta d'una paraula i diu que sí, llavors
contindrà anar al m?
>> ALTAVEU 1: Així que això té a veure con-- va a carregar això en.
Vostè diu "zoo" és una paraula.
Quan vostè va a check-- com, diguem que vostè vol dir,
existeix "zoo" en aquest diccionari?
Només vas a buscar "zoològic" i després comprovar per veure si es tracta d'una paraula.
Mai vas a moure a través de m perquè això no és
el que estàs buscant.
>> Així que si realment volíem afegir "bany" en aquest intent,
que anàvem a fer el mateix com ho vam fer amb "zoo"
excepte veuríem que quan ens tractar d'arribar a h, que no existeix.
Així que vostè pot pensar en això com tractant per afegir un nou node en una llista enllaçada,
per la qual cosa hauríem d'afegir un altre d'aquestes matrius, com a tal.
I llavors el que fem és tot just fixem el h element d'aquesta matriu que apunta a això.
>> I llavors, ¿què anàvem a voler fer aquí?
Afegeix-lo igual a veritable perquè és una paraula.
Refredar.
Ho sé.
Intents no són les més emocionants.
Confia en mi, ho sé.
>> Així que una cosa que s'adona amb tries, Jo vaig dir, són molt eficients.
Així que hem vist que portar fins a una tona d'espai.
Estan una mica confús.
Així que per què hauríem mai utilitzar aquests?
Utilitzem aquests perquè són increïblement eficient.
>> Així que si estàs buscant alguna vegada una paraula, vostè és només
limitada per la longitud de la paraula.
Així que si vostè està buscant un paraula que té una longitud de cinc,
vostè està sol mai va a haver de fer en la majoria dels cinc comparacions, d'acord?
Per tant, fa que sigui bàsicament una constant.
Igual que la inserció i recerca són bàsicament constant de temps.
>> Així que si alguna vegada es pot obtenir alguna cosa en el temps constant,
això és tan bo com es posa.
No pot ser millor que constant de temps per a aquestes coses.
Així que aquest és un dels enormes avantatges d'intents.
>> Però és un munt d'espai.
Així que tipus d'haver de decidir el que és més important per a tu.
I en els ordinadors d'avui en dia, la espai que una oportunitat pot prendre fins
potser no afecta que molt, però potser
vostè està tractant amb alguna cosa que té molt, molt més les coses,
i una oportunitat simplement no és raonable.
Sí?
>> AUDIÈNCIA: Esperi, pel que té 26 lletres en cada un?
>> ALTAVEU 1: Mmhmm.
Sí, vostè té 26.
Vostè té alguns és marcador de paraula i després vostè té 26 punters en cada un.
I estan point--
>> AUDIÈNCIA: I cada 26, és el que cada un té 26?
>> ALTAVEU 1: Sí.
I és per això, que pugui veure, s'expandeix molt ràpidament.
Bé.
Així que anem a entrar en els arbres, que Em sento com és més fàcil i probablement
ser un petit respir de tries allà.
Així que espero que la majoria de vostès han vist un arbre abans.
No com el bonic els exteriors, que jo
no sé si algú es va anar a l'aire lliure recentment.
Vaig ser recol·lecció de pomes aquest cap de setmana, i, oh, Déu meu, que era preciosa.
Jo no sabia fulles podria mirar que bonica.
>> Així que això és només un arbre, no?
És només una mica de node, i apunta a un munt d'altres nodes.
Com es veu aquí, aquest és tipus d'un tema recurrent.
Els nodes que apunta als nodes és una espècie de l'essència de moltes estructures de dades.
Només depèn de la forma en què tenen ells assenyalen l'un a l'altre
i com travessem a través d'ells i la forma en què
inserir les coses que determina les seves diferents característiques.
>> Així que només alguns dels termes, que he fet servir abans.
Així que l'arrel és el que està en la part superior.
que és on sempre comencem.
Vostè pot pensar en ell com el cap també.
Però per als arbres, tendim a es refereixen a ella com l'arrel.
>> Qualsevol cosa a la part inferior aquí-- en el molt, molt bottom--
són considerats fulles.
Per tant, va de la mà amb la El arbre sencer, no?
Les fulles són a les vores del seu arbre.
>> I després també tenim un parell de termes per parlar de nodes de relació
l'un a l'altre.
Així que tenim els pares, fills i germans.
Així doncs, en aquest cas, 3 és el matriu de 5, 6, i 7.
Així que el pare és el que és un pas per sobre del que sigui que estiguis
en referència a, de manera que només com un arbre genealògic.
Amb sort, això és tot una mica poc més intuïtiu que els intents.
>> Els germans són qualsevol que tingui el mateix pare, oi?
Estan en el mateix nivell aquí.
I llavors, com jo dient, els nens són només
el que és un pas per sota el node en qüestió, d'acord?
Refredar.
Així, un arbre binari.
Algú pot aventurar una resposta en un les característiques de l'arbre binari?
>> AUDIÈNCIA: Max dues fulles.
>> ALTAVEU 1: Dret.
Així màxim de dos fulls.
Així que en això abans, vam tenir aquest que tenia tres, però en un arbre binari,
Té un màxim de dos fills pels pares, no?
Hi ha un altre característica interessant.
Algú sap que?
Arbre binari.
>> Així que un arbre binari tindrà tot en ell-- aquest no és sorted--
però en un arbre binari ordenat, tot a la dreta
és més gran que la dels pares, i tot a l'esquerra
és menor que la dels pares.
I això ha estat un concurs qüestió que, per bo saber.
Així que la manera com definim això, una vegada més, tenim un altre node.
Això es veu molt similar al que?
Doblement
>> AUDIÈNCIA: Vinculat llistes
>> ALTAVEU 1: Una llista enllaçada doble, no?
Així que si reemplacem aquest amb anterior i següent,
això seria una llista doblement enllaçada.
Però en aquest cas, en realitat tenir a l'esquerra i la dreta i això és tot.
En cas contrari, és exactament el mateix.
Encara tenim l'element que vostè està buscant,
i només hi ha dos punters anar al que ve.
Sí, així binari arbre de cerca.
Si ens adonem, sobretot en el aquí és més gran no sigui:
o tot immediatament a la dreta aquí
és més gran que, tot aquí és inferior.
>> Així que si haguéssim de buscar a través, que ha de mirar molt a prop de recerca binària
aquí, oi?
Excepte que en comptes de mirar a la meitat de la matriu,
només estem buscant, ja sigui en l'esquerra costat o del costat dret de l'arbre.
Així que es posa una mica més simple, crec.
>> Així que si la seva arrel és NULL, òbviament és només falsa.
I si hi és, òbviament, és la veritat.
Si és menor que, busquem l'esquerra.
Si és més gran que, busquem la dreta.
És exactament igual que la recerca binària, només una estructura de dades diferent
que estem fent servir.
En lloc d'una matriu, és només un arbre binari.
>> Acceptar, piles.
I també, sembla que podria tenir una mica de temps.
Si ho fem, estic feliç d'anar sobre qualsevol d'això una altra vegada.
OK, així que piles.
Algú recorda el que stacks-- qualsevol característica d'una pila?
>> Acceptar, de manera que la majoria de nosaltres, crec, dinar al menjador halls--
tant com és possible que no els agrada.
Però, òbviament, es pot pensar en una pila literalment, igual que una pila de safates
o una pila de coses.
I el que és important és adonar-se que és
alguna cosa-- la característica que nosaltres anomenem por-- és LIFO.
Algú sap el que això representa?
Mmhmm?
>> AUDIÈNCIA: últim a entrar, primer a sortir.
>> ALTAVEU 1: Dreta, últim a entrar, primer a sortir.
Així que si sabem, si estem apilant coses dalt, la cosa més fàcil d'agafar off--
i potser l'únic que pot prendre fora si la nostra pila és gran enough--
és que element superior.
Així que qualsevol cosa es va posar en last-- com veiem aquí,
el que va ser empès en la majoria recently-- és
serà el primer cosa que ens pop fora, d'acord?
>> Així que el que tenim aquí és un altre struct typedef.
Això és realment només com un Curs accelerat en l'estructura de dades,
així que hi ha un munt llançada contra vosaltres.
Ho sé.
Així una altra struct.
Yay per a estructures.
>> I en aquest cas, es tracta d'algun punter a una matriu que té una certa capacitat.
Així que això representa la nostra pila aquí, igual que la nostra gamma actual
això és la celebració dels nostres elements.
I llavors aquí tenim una mica de mida.
>> I en general, que desitja conservar pista de com de gran és la seva pila és
perquè el que permetrà tu per fer és si vostè sap la mida,
que li permet dir, Bé, estic en capacitat?
Puc afegir alguna cosa més?
I també et diu on la part superior de la pila
és pel que vostè sap el que en realitat pot enlairar.
I això és en realitat va a ser una mica més clar aquí.
>> Així, per empenta, una cosa, si vostè van ser mai per aplicar empenta,
com jo estava dient, la seva pila té una grandària limitada, oi?
La nostra gamma tenia alguna capacitat.
És una matriu.
És una mida fixa, per la qual cosa necessitem assegurar-se que no estem posant més
en la nostra gamma del que en realitat tenen espai per a.
>> Així que quan vostè està creant una empenta funció, el primer que fas és a dir, OK,
¿Tinc espai al meu pila?
Perquè si no ho faig, ho sento, No puc desar l'ítem.
Si ho faig, llavors vostè vol emmagatzemar a la part superior de la pila, no?
>> I és per això que tenim fer un seguiment de les nostres dimensions.
Si no mantenim un registre de la nostra mida, no sabem on posar-lo.
No sabem quantes coses estan en la nostra gamma ja.
Igual que, òbviament, hi ha formes que potser vostè podria fer-ho.
Vostè podria inicialitzar tot a NULL i després comprovar si l'última NULL,
però una cosa molt més fàcil és simplement a dir, OK, no perdre de vista la mida.
De la mateixa manera que jo sé que tinc quatre elements en la meva matriu, de manera que la següent cosa
que ens posem, estem va a emmagatzemar en l'índex abril.
I llavors, és clar, això vol dir que vostè ha empès amb èxit alguna cosa
a la pica, vulgui augmentar la mida
perquè vostè sàpiga on vostè està tan que vostè pot empènyer més coses sobre.
>> Així que si estem tractant de fer esclatar alguna cosa fora de la pila,
el que podria ser la primera cosa que volem comprovar?
Vostè està tractant de prendre alguna cosa fora de la seva pila.
Segur que hi ha alguna cosa a la pica?
No
Llavors, ¿què podríem voler comprovar?
>> AUDIÈNCIA: [inaudible].
ALTAVEU 1: Comproveu la mida?
Mida.
Així que volem comprovar per veure si la nostra mida és més gran que 0, d'acord?
I si ho és, llavors volem disminuir la nostra mida per 0 i tornar això.
Per què?
>> A la primera estàvem empènyer, ens empenyem
en grandària i mida llavors actualitzat.
En aquest cas, estem decrementar la mida i després treure-se'l, desplomat que
de la nostra matriu.
Per què podríem fer això?
Així que si tinc una cosa en la meva pila, el que seria la mida de la meva en aquest moment?
1.
>> ¿I on és l'element 1 s'emmagatzema?
A quin índex?
AUDIÈNCIA: 0.
ALTAVEU 1: 0.
Així que en aquest cas, Sempre que hagi de fer sure--
en lloc de tornar mida de menys 1, ja que
sap que és el nostre element serà emmagatzemat en un menor
qualsevol que sigui la nostra mida és, aquesta només s'ocupa d'ella.
És una manera una mica més elegant.
I acabem la nostra decrementamos mida i després tornar mida.
Mmhmm?
>> AUDIÈNCIA: Crec que només en general, ¿Per què aquesta estructura de dades
ser beneficiós?
>> ALTAVEU 1: Depèn del seu context.
Així que per a alguns de la teoria, si està treballant con-- Acceptar,
m'ho dius a mi veure si hi ha un u beneficiós que és beneficiós per a més de fora
de CS.
Amb piles, qualsevol moment vostè necessita fer un seguiment d'alguna cosa que
és el més recentment afegit és quan vostè va a fer servir una pila.
>> I no puc pensar en una bona exemple d'això en aquest moment.
Però cada vegada que el més recent El que és més important per a vostè,
que és quan una pila serà d'utilitat.
Estic tractant de pensar si hi ha un bon any per a això.
Si penso en un bon exemple en la següent 20 minuts, que sens dubte li dirà.
>> Però en general, si hi ha alguna cosa, com he dit més, on més recent
és més important, això és on una pila entra en joc.
Mentre que les cues són una mica el contrari.
I tots els petits gossos.
No és genial, oi?
Em sento com que hauria només hi ha un vídeo conillet
al bell mig de secció per a vostès
perquè aquesta és una secció intensa.
>> Així que una cua.
Bàsicament una cua és com una línia.
Vostès Estic segur que aquest ús quotidià, de la mateixa manera que en els nostres menjadors.
Així que hem d'anar a i tenir a les nostres safates, estic
Segur que has d'esperar en línia per lliscar o aconseguir el seu menjar.
>> Així que la diferència aquí és que això és FIFO.
Així que si LIFO l'última a entrar, primer terme, FIFO és primer a entrar, primer a sortir.
Així que aquí és on el que poses el primer és el més important.
Així que si estaves esperant en un line-- oi
imagini si vostè va anar a anar a buscar el nou iPhone
i era una pila on el última persona de la fila ho va aconseguir en primer lloc,
persones matarien entre si.
>> Així FIFO, estem tots molt familiar amb en el món real aquí,
i tot té a veure amb la realitat espècie de recreació de tota aquesta línia
i cues estructura.
Així que mentre que amb la pila, tenim empenta i el pop.
Amb una cua, tenim enqueue i treure de la cua.
Així que, bàsicament, significa enqueue el va posar a la part del darrere,
i mitjans dequeue prenen fora de la part davantera.
Així que la nostra estructura de dades és un poc més complicat.
Tenim un segon que cal seguir la pista.
>> Així que sense el cap, aquest és exactament una pila, no?
Aquesta és la mateixa estructura que una pila.
L'única cosa diferent és que ara tenir aquest cap, que què et sembla
es va a realitzar un seguiment de?
>> AUDIÈNCIA: El primer.
>> ALTAVEU 1: Dret, la El primer que ens vam posar en.
El cap de la nostra cua.
El que és primer a la fila.
Molt bé, així que si ho fem en cua.
Una vegada més, amb qualsevol de aquestes estructures de dades,
ja que estem tractant amb una matriu, hem de comprovar si tenim espai.
>> Això és una cosa així com dient-me vostès, si s'obre un arxiu,
vostè necessita per comprovar nul·la.
Amb qualsevol d'aquestes piles i les cues, que necessiten
per veure si hi ha espai perquè som tractar amb una matriu de mida fixa,
com veiem aquí-- 0, 1 tot fins a 5.
Així que el que fem en aquest cas és xec per veure si encara tenim espai.
És el nostre grandària menor que la capacitat?
>> Si és així, tenim que el conservi en el seu la cua i actualitzem la nostra mida.
Llavors, ¿quina podria ser la cua en aquest cas?
No està escrit explícitament.
Com podríem emmagatzemar?
Quina seria la cua?
>> Així que anem a caminar a través d'aquest exemple.
Així que aquesta és una matriu de mida 6, no?
I tenim en aquest moment, el nostre grandària és 5.
I quan ho posem en, va per entrar en el cinquè índex, ¿no?
Així que emmagatzemar a la cua.
>> Una altra forma d'escriure cua faria només sigui el nostre arsenal en l'índex de mida, no?
Aquesta és la mida maig.
El següent que es va a anar a 5.
Fresc?
Okay.
Es posa una mica més complicat quan vam començar a jugar amb el cap.
Sí?
>> AUDIÈNCIA: Significa que hem de hauria declarat una matriu que
va ser cinc elements de llarg i llavors estem afegint-hi?
>> ALTAVEU 1: No.
Així doncs, en aquest cas, es tracta d'una pila.
Aquest seria declarat com una matriu de mida juny.
I en aquest cas, només hi ha una plaça d'esquerra.
>> Acceptar, de manera que una cosa és en aquest cas, si el nostre cap està a 0,
llavors només podem afegir que en la mateixa mida.
Però es posa una mica més complicat perquè en realitat,
no tenen una diapositiva per això, així que vaig
per dibuixar una perquè no és tan senzill una vegada que
començar a desfer-se de les coses.
Així que mentre que amb una pila perquè només hagi
que preocupar-se pel que la mida és quan va a afegir alguna cosa sobre,
amb una cua també ha de fer Assegureu-vos que el seu cap es comptabilitza,
perquè una cosa divertida sobre les cues és que si vostè no està en capacitat,
en realitat es pot fer que sigui embolicar al voltant.
>> Acceptar, de manera que un cosa-- oh, això és terrible guix.
Una cosa a tenir en compte és el cas.
Farem només cinc.
OK, així que anem a diuen que el cap està aquí.
Aquesta és 0, 1, 2, 3, 4.
>> El cap hi és, i si us plau tingui coses a ells.
I volem afegir alguna cosa, no?
Així que el que necessitem saber és que el cap és sempre
va a moure d'un costat a llavors bucle al voltant, d'acord?
>> Així que aquesta cua disposa d'espai, no?
Té espai en el principi, classe en cas contrari d'això.
Així que el que hem de fer és que de calcular la cua.
Si vostè sap que el seu el cap no s'ha mogut, cua
és només la seva matriu a l'índex de la mida.
>> Però en realitat, si vostè està utilitzant una cua, el seu cap, probablement s'està actualitzant.
Així que el que cal fer és realment calcular la cua.
Així que el que fem és la fórmula aquí, que vaig a deixar-te
nois pensen sobre, i llavors anem a parlar-ne.
Així que aquesta és la capacitat.
>> Així que això ho farà realitat li donarà una forma de fer-ho.
Com que en aquest cas, ¿què?
La nostra cap està en 1, la nostra mida és 4.
Si mod que per 5, obtenim 0, que és on ha d'ingressar la mateixa.
>> Així que en el següent cas, si haguéssim de fer això,
diem, OK, anem a treure de la cua alguna cosa.
Ens dequeue això.
Prenem un cop d'ull a aquest element, no?
>> I ara el nostre cap està assenyalant aquí, i volem afegir en una altra cosa.
Aquesta és bàsicament la part de darrere de la nostra línia, oi?
Les cues poden embolicar al voltant de la matriu.
Aquesta és una de les principals diferències.
Piles, no pots fer això.
>> Amb les cues, es pot perquè tot el que importa
és que vostè sap el que es va afegir més recentment.
Ja que tot serà afegit a aquesta direcció cap a l'esquerra, en aquest cas,
i després embolicar al voltant, vostè pot seguir posant en nous elements
a la part davantera de la matriu perquè no és realment
la part davantera de la matriu més.
Vostè pot pensar en l'inici de la matriu com quan el cap és en realitat.
>> Així que aquesta fórmula és com calcular la seva cua.
Això té sentit?
Okay.
Acceptar, treure de la cua, i després vostès tenen 10 minuts
en fer qualsevol preguntes aclaridores que vols, perquè sé que és una bogeria.
>> Molt bé, pel que en la mateixa manera- No sé si vostès es va donar compte,
però CS té a veure amb els patrons.
Les coses són més o menys la mateix, només amb petits retocs.
Així mateix aquí.
Hem de comprovar per veure si en realitat tenen alguna cosa en la nostra cua, no?
Digui, OK, és la nostra mida més gran que 0?
Refredar.
>> Si ho fem, llavors ens movem nostre cap, que és el que acaba de demostrar aquí.
Actualitzem el nostre cap per ser un més.
I després ens decrementamos la nostra mida i tornar l'element.
>> Hi ha molt més concret codi en study.cs50.net,
i jo recomano anar a través d'ell si tens temps,
fins i tot si és només un pseudo-codi.
I si vostès volen parlar a través de que amb mi un a un, si us plau em deixa
saber.
Jo estaria encantat de.
Les estructures de dades, si vostè pren CS 124, podràs
saben que les estructures de dades es posen molt diversió i això acaba de començar.
>> Així que sé que és difícil.
Està bé.
Lluitem.
Jo encara ho faig.
Així que no et preocupis massa per això.
>> Però això és bàsicament el seu Curs accelerat en les estructures de dades.
Sé que és molt.
Hi ha una cosa que ens li agradaria anar una altra vegada?
Qualsevol cosa que volem parlar a través de?
Sí?
>> AUDIÈNCIA: Per a aquest exemple, pel que la nova cua és a 0 sobre això?
ALTAVEU 1: Sí.
AUDIÈNCIA: OK.
Així que anar a través de, tindries 1 més 4 o--
>> ALTAVEU 1: Pel que estaven dient, quan volem anar a fer això una altra vegada?
AUDIÈNCIA: Sí.
Així que si estàs calculant fora-- on són que el càlcul de la cua d'en això?
>> ALTAVEU 1: Així que la cua Estava en-- vaig canviar això.
Així que en aquest exemple aquí, això era la matriu que estem veient, d'acord?
Així que tenim coses en 1, 2, 3, i 4.
Així que tenim el nostre cap és igual a 1 en aquest punt, i la nostra mida és igual a 4
en aquest punt, no?
>> Vostè accepta que tot és el cas?
Així que fem el cap, més la mida, el que ens dóna 5, i després ens MOD per 5.
Obtenim 0, el que ens diu que 0 és On està la nostra cua, on tenim espai.
>> AUDIÈNCIA: Què és un casquet?
>> ALTAVEU 1: La capacitat.
Ho sento.
Així que aquest és la mida del seu arsenal.
Sí?
>> AUDIÈNCIA: [inaudible] abans tornem l'element?
>> ALTAVEU 1: Així que movem el dirigir-se o tornar al moment?
Així que si ens movem un, disminuir la mida?
Espereu.
Definitivament em vaig oblidar una altra.
No importa.
No hi ha altra fórmula.
Sí, vostè vol tornar el cap i després es va moure cap enrere.
>> AUDIÈNCIA: OK, perquè en aquest punt, el cap estava a 0,
i després vol tornar l'índex 0 i després fer la cap 1?
>> ALTAVEU 1: Dret.
Crec que hi ha una altra fórmula una mica així com això.
Jo no el tinc a la part superior del meu cap com No vull donar-te la equivocada.
Però crec que és perfectament vàlid per exemple, Acceptar, guardi aquest element-- el que sigui
element de cap és-- decrementar la seva mida, moure el seu cap una altra vegada, i la tornada
qualsevol que sigui aquest element és.
Això és perfectament vàlid.
Okay.
Sento que això no és com el most-- no estàs
sortirà d'aquí com, sí, ja sé intents.
Ho tinc tot.
Això està bé.
Prometo.
Però les estructures de dades són una cosa que que es necessita una gran quantitat de temps per acostumar.
Probablement un dels més difícils les coses, crec que, en el curs.
>> Així que definitivament pren repetició i mirant at-- I
No sabia realment llistes enllaçades fins que em vaig fer massa amb ells,
de la mateixa manera que no ho vaig fer realment entendre punters
fins que m'he hagut de ensenyar-la per a dos anys i fer els meus propis conjunts de processadors amb ell.
Es necessita molt de la reiteració i el temps.
I, finalment, serà de tipus clic.
>> Però mentrestant, si vostè té tipus d'una comprensió d'alt nivell del que
aquests fan, els seus pros i que és el que cons--
que realment tendeixen a emfatitzar, especialment en el curs d'introducció.
Igual que, per què hauríem d'utilitzar una oportunitat més d'una matriu?
Igual que, quins són els aspectes positius i negatius de cada un d'aquests?
>> I la comprensió dels avantatges i desavantatges entre cadascuna d'aquestes estructures
és el que és molt més important en aquest moment.
Hi pot haver un boig o dues preguntes que és
demanarà aplicar empenta o implementar pop o de posada en cua i treure de la cua.
Però en la seva major part, havent de major comprensió de nivell i més
d'una comprensió intuïtiva és més important que en realitat
ser capaç de posar-ho en pràctica.
>> Seria realment impressionant si tots vostès podria sortir i anar implementar un intent,
però entenem que no és necessàriament el més raonable en aquest moment.
Però vostè pot en el seu conjunt de processadors, si vols per, a continuació, que obtindrà la pràctica,
i després potser vostè realment entendre-ho.
Sí?
>> AUDIÈNCIA: OK, així que quins són ens referim a utilitzar en el conjunt de processadors?
He d'utilitzar un d'ells?
ALTAVEU 1: Sí.
Així que vostè té la seva opció.
Suposo que en aquest cas, podem parlar del conjunt de processadors una mica
perquè em vaig trobar a través d'aquests.
Així que en el seu conjunt de processadors, que tingui el seu elecció d'intents o taules hash.
Algunes persones intentaran i l'ús de filtres de floració,
però els que tècnicament no són correctes.
Causa de la seva naturalesa probabilística, donen falsos positius vegades.
Són mirada fresca a, però.
Molt recomanable buscar en ells almenys.
Però vostè té la seva opció entre una taula hash i una oportunitat.
I això serà on es carrega en el seu diccionari.
>> I tu hauràs de triar la seva funció hash,
haurà de triar el nombre de cubs que té, i que variarà.
Igual que si vostè té més cubs, potser que va a córrer més ràpid.
Però potser vostè està perdent una gran quantitat d'espai d'aquesta manera, però.
Has de entendre-ho.
Mmhmm?
>> AUDIÈNCIA: Vostè va dir abans que podem utilitzar altres funcions hash,
que nosaltres no hem de crear una funció hash?
>> ALTAVEU 1: Sí, correcte.
Així que, literalment, de la seva funció de control, com google "funció hash"
i buscar alguns més fresc.
No s'espera construir les seves pròpies funcions hash.
La gent passa el seu tesi sobre aquestes coses.
>> Així que no et preocupis per la construcció de la seva pròpia.
Trobar una línia per començar.
Alguns d'ells cal manipular una mica
per fer tipus de retorn segur coincideixen i tot això, així que en principi,
Jo recomano fer servir alguna cosa molt fàcil que potser només
hashes a la primera lletra.
I a continuació, una vegada que hagi de treballar, la incorporació d'una funció hash més fresc.
Mmhmm?
>> AUDIÈNCIA: Vols provar un ésser o eficient, però només més difícil, com--
>> ALTAVEU 1: Així que un intent, crec, és intuïtivament difícil d'implementar
però és molt ràpid.
No obstant això, ocupa més espai.
Una vegada més, pot optimitzar tant dels de diferents maneres i hi ha maneres A--
AUDIÈNCIA: Com estem qualificats en això?
Es matter--
>> ALTAVEU 1: Així que tu ets classifiquen de manera normal.
Vostè va a ser classificat en el disseny.
Sigui quina sigui la forma en què ho fa, vostè vol assegureu-vos que és tan elegant com pot ser
i el més eficient possible.
Però si vostè escull un provar o haixix taula, mentre funciona,
estem contents amb això.
I si feu servir alguna cosa que hashes a la primera lletra, això està bé,
com a tal vegada com-disseny intel·ligent.
També estem arribant a la punt en aquest semester--
No sé si vostè nois noticed-- si estàs
graus PSet declinen una mica a causa del disseny i altres coses,
que està perfectament bé.
S'està fent a un punt en què el seu els programes són cada vegada més complicat.
Hi ha més llocs es pot millorar.
>> Així que és perfectament normal.
No és que vostè és fent pitjor en el seu conjunt de processadors.
És només que estem sent més dur per a vostè ara.
Així que tothom està sentint.
Acabo qualificar tots els seus conjunts de processadors.
Sé que tothom està sentint.
>> Així que no et preocupis per això.
I si vostè té alguna pregunta sobre conjunts de processadors anteriors o maneres en què pot millorar,
Tracte i comento l'específic llocs, però de vegades ja és tard
i em canso.
Hi ha altres coses sobre estructures de dades?
Estic segur que els nois realment no vull parlar-ne mai més,
però si hi ha, estic feliç de anar-hi, així com qualsevol cosa
de conferència el passat setmana o la setmana passada.
>> Sé que la setmana passada va ser tot examen, per la qual cosa podem haver saltat alguna opinió
de conferència.
Alguna altra pregunta que puc respondre?
Bé, bé.
Bé, vostès sortir 15 minuts abans.
>> Espero que això era semi-útil, com a mínim, i vaig a veure vostès la setmana que ve,
o les hores d'oficina dijous.
Hi ha sol·licituds d'aperitius per a la setmana que ve, que és la cosa?
Perquè em vaig oblidar de caramel avui.
I he portat dolços últim setmana, però que era el Dia de Colom,
pel que no eren com sis persones que tenia quatre bosses de dolços a si mateixos.
Puc portar Starbursts de nou si ho desitja.
Starbursts?
Bé, sona bé.
Que tinguin un bon dia, nois.