ALTAVEU 1: Molt bé, així que això és CS50 Aquest és el final de la cinquena setmana. I recordar que l'última vegada que començat a buscar en les dades més elegant estructures que van començar a resoldre problemes, que van començar a introduir nous problemes, però la clau d'aquest Era el tipus de roscat que començat a fer des d'un node a un altre. Així que aquest supòsit és una llista simplement enllaçada. I per separat vinculats, Vull dir que hi ha una sola fil entre cada un d'aquests nodes. Resulta que vostè pot fer més elegant coses com llistes doblement enllaçades pel que vostè té una fletxa va en dues direccions, la qual cosa pot ajudar amb certes eficiències. Però això soluciona el problema? Quin problema es resol això? Per què ens importa el dilluns? Per què, en teoria, ens cuidem el dilluns? Què fa això? 

AUDIÈNCIA: dinàmicament Podem canviar la seva mida. 

ALTAVEU 1: OK, per la qual cosa podem dinàmicament canvieu la mida. Ben fet tots dos. Així que vostè pot canviar la mida de forma dinàmica aquest estructura de dades, mentre que una matriu, record, vostè ha de saber una priori la quantitat d'espai que voleu i si vostè necessita una mica més espai, ets la classe de sort. Has de crear una nova matriu sencera. Has de moure tot el seu dades d'un a un altre, finalment alliberar la matriu d'edat si es pot, i després procedir. La qual cosa se sent molt costós i molt ineficients, i de fet pot ser. Però això no és tot el bo. Nosaltres paguem un preu, el que va ser un dels preus més òbvies pagar mitjançant l'ús d'una llista enllaçada? 

AUDIÈNCIA: Hem de fer servir doble espai per a cada un. ALTAVEU 1: Sí, pel que necessitem almenys el doble d'espai. De fet, em vaig adonar d'aquesta imatge fins i tot una mica enganyós, perquè l'IDE CS50 en molts moderna ordinadors, un punter o una adreça no és, de fet, quatre bytes. És molt sovint aquests dies 8 bytes, que significa la part inferior més rectangles hi ha en la realitat són una mena de doble de gran com el que he dibuixat, el que significa que està utilitzant tres vegades més espai que podríem tenir d'una altra manera. Ara, al mateix temps, estem sense deixar de parlar bytes, oi? No estem parlant necessàriament megabytes o gigabytes, llevat que aquestes estructures de dades es fan grans. 

I per això avui comencem a considerar com podríem explorar les dades més eficientment si en fet que les dades es fa més gran. Però anem a tractar de canonicalize les operacions de la primera que es pot fer en aquests tipus d'estructures de dades. Així que alguna cosa com un lligada llista general dóna suport operacions com esborrar, inserir i cercar. I el que vull dir amb això? Això només vol dir que en general, si la gent està utilitzant llista enllaçada, ells o algú més ha implementat funcions com esborrar, inserir, i la recerca, de manera que pot realment fer alguna cosa útil amb l'estructura de dades. Així que anem a fer una ullada ràpida en com podríem aplicar una mica de codi per a una llista enllaçada de la següent manera. 

Així que això és només una mica de codi C, ni tan sols un programa complet que realment em van assotar ràpidament. No és en línia en la distribució codi, perquè no funcionarà realment. Però noto que tinc just amb un comentari dir, punt punt punt, hi ha alguna cosa allà, dot dot dot, alguna cosa allà. I anem a mirar ¿Quines són les parts sucoses. Així que en la línia 3, recordem que això és ara ens vam proposar declarar un node última temps, un d'aquests objectes rectangulars. Té un int que anomenarem N, però podríem anomenar res, i després una estrella struct node anomenat següent. I només perquè quedi clar, que segons línia, en la línia 6, què és això? Què està fent per nosaltres? Perquè sens dubte es veu més críptica que les nostres variables habituals. 

AUDIÈNCIA: Es fa que es mogui més d'una. 

ALTAVEU 1: Es fa que es mogui més d'una. I per ser més precisos, emmagatzemarà la direcció del node que està destinat a ser semànticament al costat d'ell, oi? Per tant, no va a moure necessàriament res. És només va a emmagatzemar un valor, que és serà la direcció d'algun altre node, i és per això que hem dit struct estrella de node, que denota l'estrella un punter o una adreça. OK, així que ara si assumir que tenim aquesta N disponible per a nosaltres, i anem a assumir que algú més té inserit un munt de nombres enters en una llista enllaçada. I aquesta llista enllaçada és apuntada per algun moment una trucada llista de variables que és aprovada en aquí com un paràmetre, com faig per línia 14 implementació de cerca? En altres paraules, si m'estic posant en pràctica funció el propòsit en la vida és prendre un int i després el a partir d'una llista enllaçada, que és un punter a la llista enllaçada. Com a primera, que crec que David era la nostra voluntària dilluns ell estava assenyalant tot vinculat la llista, és com si estem passant David com la nostra discussió aquí. Com fem per travessar aquesta llista? Bé, resulta que tot i que punters són relativament nou ara a nosaltres, podem fer això relativament sense embuts. 

Vaig a seguir endavant i declarar una variable temporal que per convenció és només anar per a ser anomenat punter o PTR, però se li pot dir el que vulguis. I jo vaig a inicialitzar al començament de la llista. Així que vostè pot classe de pensar en això com jo la mestra, l'altre dia, tipus de apuntant a algú entre els nostres éssers humans com a voluntaris. Així que sóc una variable temporal que és simplement apuntant-se al mateix que el nostre coincidentment nomenat voluntari David també estava assenyalant. Ara bé, tot i que és punter no és nul, perquè recordo que nul és un valor especial sentinella la demarcació del final de la llista, així que mentre jo no estic apuntant a la sòl com la nostra última voluntari va ser, seguirem endavant i faci el següent. Si pointer-- i ara que tipus de desig a fer el que vam fer amb l'estudiant structure-- si dot punter proper equals-- més bé, si dot punter N és igual és igual a la variable N, la argument que ha estat aprovada en, llavors vull seguir endavant i dir tornar realitat. He trobat el nombre N interior un dels nodes de la cistella enllaçada. Però el punt ja no funciona en aquest context, perquè punter, PTR, és de fet un punter, una adreça, que en realitat pot meravellosament utilitzar finalment una peça de sintaxi aquest tipus de marques sentit intuïtiu i realitat utilitzar una fletxa aquí, el que significa passar de aquesta direcció al sencer més enllà en. Així que és molt similar a esperit per a l'operador punt, sinó perquè punter no és un punter i no una pròpia estructura real, només ha d'utilitzar la fletxa. 

Així que si el node actual que jo, el variable temporal, estic apuntant a ¿No és N, què és el que vull fer? Doncs bé, amb els meus voluntaris humans que vam tenir aquí l'altre dia, si el meu primer ésser humà no és el que jo vol, i potser el segon humà no és el que jo vull, i el tercer, que de mantenir físicament en moviment. Igual que com em va passar a través d'una llista? Quan vam tenir una matriu, acaba de fer com si plus plus. Però en aquest cas, només cal fer punter, aconsegueix, punter, al costat. En altres paraules, el camp següent és com totes les mans esquerres que els nostres voluntaris humans dilluns estaven usant per assenyalar en algun altre node. Aquestes van ser les seves següents veïns. 

Així que si vull fer un pas a través d'aquesta llista, No puc fer jo plus plus més, Jo en canvi he de dir Jo, punter, va per igualar qualsevol que sigui el següent camp és, el següent camp és, el següent camp és, després totes aquestes mans esquerres que teníem en l'escenari que assenyala per a alguns valors posteriors. I si em poso a través tota aquesta iteració, i, finalment, em va colpejar nul·la no tenir Vaig trobar N però, acabo de tornar falsa. Així que de nou, tot el que estem fent aquí, segons la imatge fa un moment, està començant assenyalant al a partir de la llista de suposar. I llavors puc comprovar, és el valor Busco igual a nou? Si és així, torno veritable i he acabat. Si no, puc actualitzar la meva mà, També conegut com punter, al punt en el lloc de la propera fletxa i a continuació, la ubicació de la propera fletxa, i el següent. Simplement estic caminant a través d'aquesta matriu. 

Així que de nou, a qui li importa? Igual que ho és aquest ingredient per? Bé, recordem que vam introduir la noció d'una pila, que és un tipus abstracte de dades en la mesura que és no és una cosa C, no és una cosa CS50, és una idea abstracta, aquesta idea de apilar coses a la part superior dels uns als altres que es poden implementar en raïms de diferents maneres. I una manera que vam proposar va ser amb una matriu o amb una llista enllaçada. I resulta que canònicament, 1 pila compatible amb almenys dues operacions. I les paraules de moda són d'empenta, a empènyer alguna cosa a la pila, com una nova safata al menjador, o el pop, el que significa per eliminar el més elevat safata de la pila al menjador passadís, i després potser alguns altres operacions també. Llavors, ¿com podríem definir l'estructura que ara estem cridant a una pila? 

Bé, tenim tot el necessari sintaxi a la nostra disposició en C. dic, donar-me una definició de tipus de una estructura interior d'una pila, Jo vaig a dir és una matriu, d'un tota munt de números i després la mida. En altres paraules, si vull per implementar aquesta en el codi, me n'aniré i només una mica dibuixar el que això està dient. Així que això està dient, dóna'm un estructura que té una matriu, i jo no sé el que és la capacitat, pel que sembla és una constant que tinc definits en un altre lloc, i això està bé. Però suposo que és només un, dos, tres, quatre, cinc. Així capacitat és de 5. Aquest element interior del meu estructura es dirà nombres. I llavors jo necessito un una altra variable aparentment crida mida que al principi em vaig estipular s'inicialitza a zero. Si no hi ha res en la pila, la mida és zero, i és els valors d'escombraries en nombres. No tinc idea del que hi ha allà de moment. 

Així que si vull empènyer alguna cosa a la pila, Suposo que jo anomeno la funció d'empenta, i Dic empènyer 50, com el nombre 50, on proposaria Assenyalo que en aquesta sèrie? Hi ha cinc possibles respostes diferents. On vol empènyer el nombre 50? Si l'objectiu aquí, de nou, trucar al la funció d'empenta, passar en una discussió de 50, on ho poso? Cinc possible- 20% de probabilitat d'endevinar correctament. Sí? 

AUDIÈNCIA: Extrem dret. 

ALTAVEU 1: Extrem dret. En l'actualitat existeix una probabilitat del 25% d'endevinar correctament. Així que això seria realment bé. Per convenció, ho diré amb una matriu, estaríem en general començarà a l'esquerra, Però podríem sens dubte començarà a les de la dreta. Així que l'aleró aquí seria que sóc probablement va a treure, a l'esquerra, de la mateixa manera que en una matriu normal on Començo a anar a l'esquerra a la dreta. Però si es pot donar la volta l'aritmètica, bé. És que no és convencional. OK, he de fer una més canvi però. Ara que l'he empès una mica a la pila, què segueix? 

Molt bé, he de incrementar la grandària. Així que permetin-me anar per davant i just actualitzar aquesta, que era zero. I en lloc ara, em vaig posar en valor un. I ara suposo empenyo altra número a la pila, igual que 51. Bé, he de fer una més el canvi, que és fins a la mida 02:00. I després suposo empenyo una més número a la pila com 61, ara he de actualitzar la mida d'una més temps, i obtenir el valor 3 com la mida. I ara suposo que jo anomeno pop. Ara pop, per convenció, no té un argument. Amb una pica, la totalitat punt de la metàfora de la safata és que vostè no té la discreció per anar a buscar aquesta safata, tot el que pot fer s'obrirà el de més amunt de la pila, perquè sí. Això és el que fa aquesta estructura de dades. 

Així que per aquesta lògica si diuen pop, el que surt? Així que 61. Així que el que realment és l'ordinador va a fer en la memòria? Què fa el meu codi ha de fer? Què proposaria vostè canviem a la pantalla? Què ha de canviar? Ho sentim? Així que ens desfem de 61. Així que definitivament puc fer això. I puc desfer-me d'61. I llavors, ¿quina altra el canvi ha de succeir? Mida probablement ha de tornar a dos. I així està bé. Però esperi un minut, mida Fa un moment tenia tres anys. Anem a fer una comprovació de validesa ràpid. Com sabem que estem volia desfer-se del 61? A causa de que estem fent esclatar. I així tinc aquest segon mida de la propietat. 

Espera un minut, estic pensant en tornar a la segona setmana quan vam començar a parlar de arrays, on això era lloc de zero, aquesta era la ubicació un, aquesta era la ubicació dos, això és la ubicació tres, quatre, sembla que el relació entre la mida i l'element que vull treure de la matriu sembla ser el que? Mida menys un. I així és com els humans sabem 61 que passi primer. Com està l'equip va a saber? Quan el seu codi, en el qual, probablement, vol fer mida de menys un, almenys un de tres és de dos, i que vol dir que volem desfer-nos d'61. I llavors podem efectivament actualitzar la mida de manera que la mida ara va de tres a dos. I només per ser pedant, vaig proposar que he acabat, no? Vostè va proposar intuïtivament correctament He desfer-me d'61. Però no han de tipus de tipus de rebuig de 61? M'he oblidat de manera efectiva que en realitat existeix. I pensar en tornar a PSET4, si has llegit l'article sobre medicina forense, el PDF que havíem de vostès llegir, o llegirà aquesta setmana per PSET4. Recordem que això és en realitat afí a tota la idea de la informàtica forense. El que un equip generalment fa és simplement s'oblida on és alguna cosa, però no entra i igual que tractar d'arrapar cap a fora o anul·lació aquests bits amb zeros i uns o algun altre patró aleatori llevat que vostè mateix ho fan deliberadament. Pel que la seva intuïció era Molt bé, anem a desfer-nos de 61. Però en realitat, no hem de preocupar-se. Només hem d'oblidar que que hi és canviant el nostre mida. 

Ara hi ha un problema amb aquesta pila. Si segueixo empenyent coses a la pila, el que és Òbviament passarà en tan sols uns pocs moments de temps? Anem a quedar-se sense espai. I, què fem? Estem tipus de fotuts. Aquesta aplicació no permet ens redimensionar la matriu, perquè l'ús de aquesta sintaxi, si pensar de nou a la segona setmana, una vegada que s'ha declarat la mida d'un array, no hem vist un mecanisme encara quan vostè pot canviar la mida de la matriu. I de fet C no té aquesta característica. Si dius dóna'm 5 NTHS, els diuen nombres, això és tot el que vas a aconseguir-ho. Així que anem a fer ara a partir de dilluns, tenim la capacitat d'expressar una solució però, només hem d'ajustar la definició de la nostra pila de no haver algun conjunt modificable, però només per emmagatzemar una adreça. 

Ara per què és això? Ara només hem d'estar còmode amb el fet que quan la meva programa s'executa, Estic presumiblement va ha de demanar a la humana, la quantitat de nombres és el que vols per emmagatzemar? Així que l'entrada ha de venir d'algun lloc. Però una vegada que sé que nombre, llavors jo puc només utilitzar el que funciona per donar mi una part de la memòria? Puc utilitzar malloc. I puc dir qualsevol nombre de bytes vull tornar per aquests NTHS. I tot el que tinc per emmagatzemar en els números variable d'aquí dins d'aquesta estructura hauria de ser què? El que en realitat succeeix en el nombres en aquest escenari? Sí, un punter a la primera byte d'aquest tros de memòria, o més específicament, la direcció de del primer d'aquests bytes. No importa si és un byte o mil milions de bytes, Només he de preocupar-se pel primer. Perquè ¿quines garanties malloc i meus garanties del sistema operatiu, és que la part de la memòria d'E aconseguir, que serà contigus. No va a haver-hi llacunes. Així que si jo he demanat 50 bytes o 1.000 bytes, estan tots van a ser esquena amb esquena amb esquena. I sempre que em acord de què tan gran, com tant que vaig demanar, tot el que necessito saber és la primera direcció. 

Així que ara tenim la capacitat de codi. Encara que, va portar-nos més temps per escriure això, podríem ara reassignar aquest record per simplement emmagatzemar una adreça diferent allà si volem una més gran o fins i tot un tros més petit de la memòria. Així que aquí a un fora de comerç. Ara arribem dinamisme. Encara tenim contigüitat que estic afirmant. A causa de malloc ens donarà una part contigua de la memòria. Però això serà un dolor a el coll per a nosaltres, el programador, codificar realment cap amunt. És només més feina. Necessitem codi similar al que era colpejant a terme fa un moment. Molt factible, però afegeix complexitat. I així que el temps desenvolupador, programador el temps és un altre recurs que puguem necessitar per passar una mica de temps per aconseguir noves característiques. I després, per descomptat, hi ha una cua. No entrarem en això una a molt detall. Però és molt similar en esperit. Jo podria implementar una cua, i les seves operacions corresponents, enqueue o treure de la cua, com afegir o treure, és només una forma més elegant de dir-ho, enqueue o treure de la cua, com segueix. Només em puc donar una estructura que de nou té matriu d'un nombre, que de nou té una mida, però per què faig Ara necessito fer un seguiment de la part davantera de la cua? Jo no necessito saber el front de la meva pila. Bé, si jo de nou per un queue-- anem només difícil codificar com tenint com de cinc sencers en aquí potencialment. Així que aquest és zero, un, dos, tres, quatre. Això serà números cridats de nou. I això es dirà mida. 

Per què és no suficient tenir la mida just? Bé, anem a empènyer aquests mateixos números en. Així que pushed-- I en cua, o empès. Ara vaig a posar en cua 50, i després 51, i després de 61 anys, i dot dot dot. Així que això és enqueue. Jo en cua 50, després 51, després 61. I això es veu idèntica a una pila fins al moment, sense que jo ho necessito per fer un canvi. Necessito actualitzar aquesta mida, així que vaig de zero a 1:00-02:58 ara. Com puc treure de la cua? Què passa amb dequeue? Qui ha de sortir aquesta llista primer si es tracta de la línia a la botiga d'Apple? Així que 50. Així que és una mica més difícil aquesta vegada. Mentre que l'última vegada va ser super simplement fàcil de fer mida de menys un, Arribo al final de la meva sèrie efectiva on els nombres són, elimina 61. Però jo no vull treure 61. Vull aprofitar 50 anys, que hi era en 05:00 a la línia per al nou iPhone o el que sigui. I així, per desfer-me d'50, em no només pot fer això, oi? Puc ratllar 50. Però acabem de dir ens no han de ser tan anal per guanyar-se o ocultar les dades. Només podem oblidar on és. 

Però si canvi de mida ara 2, és aquesta informació suficient saber el que està passant en la meva cua? No realment. Igual que la meva mida és dues, però On comença la cua, especialment si encara tinc aquests mateixos números a la memòria. 50, 51, 61. Així que he de recordar ara a la part davantera és. I així com em vaig proposar dalt allà, anem Acabem de trucada Front enèsim, la inicial valor ha d'haver estat el que? Zero, només el començament de la llista. Però ara, a més de decrement la mida, només incrementa el front. Ara aquí hi ha un altre problema. Així que una vegada que segueixo anant. Suposem que aquest és el nombre de com 121, 124, i després, maleïda sigui, Estic fora d'espai. Però esperi un minut, jo no ho sóc. Així que en aquest punt de la història, suposem que la mida és un, dos, tres, quatre, així que suposo que la mida és quatre, el front és un, pel que és 51 a la part davantera. Vull posar un altre nombre aquí, però, maleïda sigui, m'he quedat sense espai. Però jo no sóc realment, oi? On podria posar una mica valor addicional, igual que 171? Només Sí, vaig poder tipus de tornar per allà, oi? I després creuar la 50, o simplement sobreescriure amb 171. I si vostè s'està preguntant per què els nostres números van arribar tan a l'atzar, aquests són comunament preses equip cursos de ciències a Harvard després CS50. Però això era una bona optimització, perquè ara no estic perdent espai. Encara he de recordar el gran que és total. És cinc en total. Perquè jo no vull començar a sobreescriure 51. Així que ara estic encara sense espai, per la qual cosa el mateix problema que abans. Però es pot veure com ara en el codi, és probable que d'escriure una mica més complexitat per fer que això passi. I de fet, el que l'operador en C, probablement anem a que màgicament fa això la circularitat? Sí, l'operador de mòdul, el signe de percentatge. Llavors, ¿què és una mena de fresc sobre una cua, tot i que seguim matrius de dibuix ja que aquestes línies rectes com, si vostè tipus de pensar en això com a corba voltant com un cercle, llavors només intuïtivament quin tipus de treballs mentals Crec que una mica més neta. Vostè encara ha de posar en pràctica aquest model mental en codi. Així que no és tan difícil, en última instància, per a posar en pràctica, però encara perdem la size-- més aviat, la capacitat de canviar la mida, tret que fem això. 

Hem de desfer-nos de la matriu, es reemplaçar amb un únic punter, i després en algun lloc del meu codi tinc Una crida el que funciona per a crear realitat la matriu de nombres anomenats? Malloc, o alguns similars funció, exactament. Teniu alguna pregunta respecte piles o cues. Sí? Bona pregunta. El mòdul usaries aquí. Així que en general, quan s'utilitza mod, que ho faria amb la mida de la estructura de dades sencera. Així que una cosa així com cinc o capacitat, si és constant, és probablement involucrats. Però només fent mòdul de cinc probablement no és suficient, perquè necessitem saber què hem embolicar al voltant d'aquí o aquí o aquí. Així que vostè és probablement també voldrà involucrar la mida de la cosa, o la variable front també. Així que és només per aquesta relativament expressió aritmètica simple, però mòdul seria l'ingredient clau. 

Així curtmetratge si es vol. Una animació que alguns gent d'una altra universitat armem que hem adaptada per a aquesta discussió. Es tracta de Jack l'aprenentatge de la fets sobre les cues i estadístiques. 

PEL·LÍCULA: Hi havia una vegada, hi havia un tipus anomenat Jack. Quan es tractava de fer amics, Jack no té una habilitat especial. Així que Jack va anar a parlar amb el més noi popular que sabia. Va ser a Lou i li va preguntar: Què faig? Lou va veure que el seu amic estava molt angoixat. Bé, ell va començar, just mira com estàs vestida. No tens res de roba amb una mirada diferent? Sí, va dir Jack. És clar que sí. Vine a casa meva i Vaig a mostrar a vostès. Així es van anar a Jack. I Jack va mostrar el quadre de Lou on guardava totes les seves camises, i els seus pantalons i els mitjons. Lou va dir: Veig que tens tota la roba en una pila. Per què no et poses una mica de altres de tant en tant? 

Jack va dir, bé, quan jo treure la roba i mitjons, Jo els rento i vaig posar a les escombraries a la caixa. Després ve la següent matí, i fins i tot em salt. Vaig a la caixa i obtinc la meva roba de la part superior. Lou es va adonar ràpidament el problema amb Jack. Va mantenir roba, CD, i els llibres de la pila. Quan va arribar a alguna cosa per llegir o portar, ell triaria el llibre superior o roba interior. Després, quan va acabar, el posaria de tornada. Tornar aniria, a la part superior de la pila. Jo sé la solució, va dir un Loud triomfant. Has d'aprendre a comenci a utilitzar una cua. Lou va prendre la roba de Jack i els va penjar a l'armari. I quan ell havia buidat la caixa, ell simplement el va tirar. 

Després va dir, ara Jack, al final de el dia, posar la roba a l'esquerra quan se'ls posa lluny. Llavors demà al matí quan es veure el sol, posar-se la roba a la dreta, des del final de la línia. No ho veus? va dir Lou. Serà tan agradable. Et portes tot un cop abans que et poses alguna cosa dues vegades. I amb tot, a les cues en el seu armari i prestatge, Jack va començar a sentir molt segur de si mateix. Tot gràcies a Lou i seva meravellosa cua. ALTAVEU 1: Molt bé, és adorable. Així que el que ha estat realment va de sota la campana ara? Que tenim punters, que tenim malloc, que tenim la capacitat de crear trossos de memòria per a nosaltres mateixos dinàmicament. Així que aquesta és una imatge que ens albirat l'altre dia. Nosaltres realment no habitem en ella, però aquesta imatge ha estat succeint per sota el capó des de fa setmanes. I pel que aquesta representa, simplement un rectangle que hem dibuixat, la memòria de l'equip. I potser el seu ordinador, o CS50 Identificació, té un gigabyte de memòria o la memòria RAM o dos gigabytes o quatre. En realitat no importa. El seu sistema operatiu Windows o Mac OS o Linux, essencialment li permet al seu programa a pensar que té accés a la totalitat de la memòria de l'equip, tot i que podria estar executant diversos programes alhora. Així que en realitat, que no funciona molt bé. Però és una espècie d'il·lusió donat a tots els seus programes. Així que si vostè tenia dos gigues de RAM, aquest És així com l'equip podria pensar en ell. 

Ara és coincidència que un d'ells coses, un d'aquests segments de memòria, es diu una pila. I, en efecte qualsevol moment fins al moment en l'escriptura de codi que ha cridat funció, per exemple principal. Recordo que cada vegada que tinc la memòria de l'ordinador dibuixat, Sempre em baso tipus de mitjà d'un rectangle aquí i no et molestis a parlar sobre el que està a dalt. Perquè quan principal es diu, jo reclamo que s'obté d'aquest tros de la memòria que passa per aquí. I si una funció principal anomenat com swap, així bescanvi va aquí. I resulta, això és on està acabant. En alguna cosa que es diu una pila dins de la memòria de l'equip. Ara, al final del dia, això és només aborda. És com zero bytes, byte un, byte 2000000000. Però si es pensa en això com aquest objecte rectangular, tot el que estem fent tots els temps que anomenem una funció és capes d'un nou segment de memòria. Estem donant a aquesta funció una llesca de la seva pròpia memòria per treballar. 

I recorda ara que això és important. Perquè si tenim una mena d'intercanvi i dues variables locals com A i B i canviem els valors d'un i dos a dos i un, el record que quan torna d'intercanvi, és com si aquest tros de la memòria simplement s'ha anat. En realitat, segueix sent hi ha forense. I alguna cosa encara està realment allà. Però conceptualment, és com encara que ha desaparegut del tot. I així principal no sap qualsevol dels treballs que es va fer en aquesta funció d'intercanvi, llevat que en realitat va passar en els arguments de punter o de referència. Ara, la solució fonamental a aquest problema d'intercanvi és passar les coses en la seva direcció. Però resulta que, també, el que és estat passant per sobre d'aquesta part del rectangle de tot aquest temps és però, hi ha més memòria fins allà. I quan dinàmicament assignar memòria, ja sigui a l'interior de GetString, que que hem estat fent per a vostè en el CS50 biblioteca, o si vostès trucar a malloc i demanar el sistema operatiu d'un tros de memòria, que no ve de la pila. Ve d'un altre lloc en la memòria del seu ordinador això es diu el munt. I això no és res diferent. És la mateixa memòria RAM. És la mateixa memòria. És només la memòria RAM que és fins allà en comptes d'aquí. 

I així, què vol dir això? Bé, si l'equip té una quantitat finita de memòria i la pila està creixent, de manera que parlar, i el munt, d'acord a aquesta fletxa, està creixent cap avall. En altres paraules, cada vegada que es diu a malloc, que està sent donat una llesca de la memòria des de dalt, llavors potser una mica més baix, després una mica inferior, cada vegada que es diu a malloc, el munt, és l'ús, és una espècie de creixement, creixent més i més al que? La pila. Així que això sembla una bona idea? Vull dir, quan en realitat no és clara Què més es pot fer si només tenen una quantitat finita de memòria. Però això és segurament dolent. Aquests dos fletxes estan en una Curs accelerat per l'altre. 

I resulta que els dolents, la gent que són particularment bo amb la programació, i tractant d'introduir en els ordinadors, pot explotar aquesta realitat. De fet, considerarem un petit fragment. Així que aquest és un exemple, vostè pot llegir sobre amb més detall a la Viquipèdia. T'indiquem en el article si curiosa. Però hi ha un atac general conegut com desbordament de memòria intermèdia que ha existit durant tant de temps com els humans han tingut la capacitat de manipular la memòria de l'ordinador, especialment en C. Així que aquest és un programa molt arbitrària, però llegirem de baix a dalt. Principal a estrella argc carbó argv. Així que és un programa que usa arguments de la línia d'ordres. I tot principal no sembla és cridar una funció, en diuen F per la simplicitat. I que passa en què? Argv d'un. Per tant, passa a la F el la paraula és que l'usuari va escriure en l'indicador després de la El nom del programa en absolut. Tant com Cèsar o Vigenère, que es pot recordar fent amb argv. 

Llavors, què és F? F porta en una cadena com a únic argument, També conegut com un estel char, mateixa cosa, com una cadena. I es diu arbitràriament bar a aquest exemple. I després carbó c 12, només en termes senzills, el que és carbó c suporti 12 fent per nosaltres? Què es fa? L'assignació de memòria, específicament 12 bytes per a 12 caràcters. Exactament. I després l'última línia, remenar i còpia, vostè probablement no es veu. Aquesta és una còpia de cadena funció el propòsit en la vida és copiar el seu segon argument en el seu primer argument, però només fins a una cert nombre de bytes. Així que el tercer argument diu, quants bytes de copiar? La longitud de la barra, qualsevol que sigui l'usuari va escriure en. I el contingut de bar, aquesta cadena, són còpia en la memòria apuntada en l'C. 

Així que això sembla una mica estúpid, i ho és. És un exemple artificial, però és representativa d'una classe de vectors d'atac, una manera d'atacar un programa. Tot està bé i bo si l'usuari tipus en una paraula que és 11 caràcters o menys, a més de la barra invertida zero. Què passa si l'usuari escriu en més de 11 o 12 o 20 o 50 caràcters? Quin és aquest programa va a fer? Culpa Potencialment seg. Va copiar cegament tot el que a la barra de dalt a la seva longitud, que és literalment tot al bar, en la direcció apuntant a C. Però C només s'ha donat de manera preventiva com de 12 bytes. Però no hi ha cap comprovació addicional. No hi ha, si les condicions. No hi ha cap comprovació d'errors aquí. 

I així el que aquest programa és farem és a cegues copiar una cosa a l'altra. I així, si tracem aquest com una imatge, aquí està Només una petita porció de l'espai de memòria. Així que notem a la part inferior, que tenir la barra de variable local. Així que aquest punter que va a almacén-- més aviat que l'argument local que és va a emmagatzemar la barra de cadena. I després tan sols per sobre d'ella en una pila, perquè cada vegada que demanes per a la memòria a la pila, va una mica per sobre d'ella il·lustrat, avís que tenim 12 bytes allà. El superior esquerre és el suport C zero i la part inferior dreta és C suport d'11. Així és com els ordinadors va a asseure a terme. Així que només intuïtivament, si la barra té més de 12 caràcters en total, incloent la barra invertida zero, ¿on és el 12 o el suport de C 12 a anar? O més aviat ¿on és el dia 12 caràcter o el caràcter 13, el caràcter centèsima anar per acabar a la foto? Per sobre o per sota? 

És clar, perquè tot i que la pròpia pila creix cap amunt, una vegada que hagi posat coses en això, per raons de disseny, posa la memòria de dalt a baix. Així que si vostè té més de 12 bytes, vostè va a començar a sobreescriure bar. Això sí que és un error, però és no és realment un gran problema. Però és una gran cosa, perquè no hi ha més coses que estan passant a la memòria. Així que aquí està com podríem posar hola, per ser clars. Si he escrit en hola en l'indicador. Barra invertida zero H-E-L-L-O, acaba dins aquests 12 bytes, i estem super segur. Tot està bé. Però si escric alguna cosa més llarg, que és potencialment va arrossegar-se en l'espai bar. Però pitjor encara, resulta fora de tot aquest temps, tot i que mai hem parlat de ella, la pila s'utilitza per a altres coses. No són només les variables locals. 

C és un llenguatge de nivell molt baix. I és una espècie de secret fa servir la pila també recordar quan un funció es diu, el que la direcció és de la funció anterior, pel que pot saltar de nou a aquesta funció. Així que quan les trucades principals intercanvien, entre les coses s'insereixen en la pila no són només intercanvia variables locals, o els seus arguments, també van empènyer en secret a la pila tal com es representa per la llesca vermell aquí, és l'adreça del principal físicament en la memòria del seu ordinador, de manera que quan es fa d'intercanvi, l'ordinador sap que he de tornar a la principal i acabar l'execució de la funció principal. Així que això és perillós ara, perquè si l'usuari escriu així més de hola, de tal manera que clobbers l'entrada de l'usuari o sobreescriu aquesta secció vermella, lògicament si l'ordinador només va a assumir cegament que els bytes en aquesta llesca vermell són la direcció a la que ha de tornar, ¿I si l'adversari és prou intel·ligent o la sort de posar una seqüència de bytes cal s'assembla a una adreça, però és la direcció de codi que ell o ella vol que l'equip per executar en lloc de principal? 

En altres paraules, si el que el usuari està escrivint en l'indicador, no és només una cosa com innòcua hola, però en realitat és un codi que és equivalent eliminar tots els arxius d'aquest usuari? O un correu electrònic la contrasenya a mi? O iniciar el registre de la seva pulsacions de teclat, oi? Hi ha un camí, anem a estipulen avui, que podien escriure no només hola mundial o el seu nom, que podien essencialment Va esdevenir en codi, zeros i estimats, que l'ordinador errors tant de codi i una adreça. Així que encara que una mica abstracte, si el usuari escriu prou codi acusatori que anem a generalitzar aquí A. A és atac o adversaris. Així les coses simplement dolent. No importa el números o els zeros o uns avui en dia, de manera que vostè acaba sobreescriure aquesta secció vermella, notar que seqüència de bytes. O 835 C zero vuit zero. I ara com article de Wikipedia aquí ha proposat, si ara de començar etiquetatge dels bytes en el seu equip de la memòria, el que l'article de Wikipedia és proposant és que, què passa si la direcció d'aquest byte superior esquerra és 80 C 0 3508. 

En altres paraules, si el dolent de la pel·lícula és prou intel·ligent amb el seu codi per posar en realitat un nombre aquí que correspon a la direcció del codi ell o ella injecta en l'equip, pot enganyar l'ordinador a fer qualsevol cosa. L'eliminació d'arxius, correu electrònic coses, ensumant el seu trànsit, literalment, qualsevol cosa podria ser injectada a l'ordinador. I així un desbordament de memòria intermèdia atac en el seu nucli és només un estúpid, estúpid primordial d'una matriu que no tenen els seus límits comprovats. I això és el que és super perillós i alhora súper poderós en C és que nosaltres tenim de fet accés a qualsevol lloc de la memòria. Tot depèn de nosaltres, els programadors, que escriuen el codi original per comprovar la longitud de qualsevol maleït matrius que estem manipulant. Així que perquè quedi clar, quina és la solució? Si rodem de nou a aquest codi, no només ha de canviar la longitud de la barra, el que més he revisaré? Què més he de fer per prevenir aquest atac del tot? No vull dir simplement cegament que copiï tants bytes com és la longitud de la barra. Vull dir, copiar com molts bytes com estan a la barra fins l'assignat memòria, o 12 com a màxim. Així que necessito algun tipus de condició if que fa comprovar la longitud de la barra, però si és superior a 12, només dura codi 12 com a la distància màxima possible. Altrament, el tampó de trucada atac de desbordament pot succeir. A la part inferior de les diapositives, si tens curiositat per llegir més és l'article original real si vols fer una ullada. 

Però ara, entre els preus pagats aquí va ser ineficiències. Així que va ser una ràpida baix nivell ullada al que poden sorgir problemes ara que tenir accés a la memòria de l'ordinador. Però un altre problema que ja ensopegat dilluns era només la ineficàcia d'una llista enllaçada. Estem de tornada a temps lineal. Ja no tenim una matriu contigua. No tenim accés aleatori. No podem usar la notació de claudàtors. Literalment, cal utilitzar un bucle while com la que jo vaig escriure fa un moment. Però el dilluns, reclamem que podem colar-se de nou en l'àmbit de l'eficiència aconseguir alguna cosa que és logarítmica, potser, o millor encara, potser fins i tot una cosa que és l'anomenada constant de temps. Llavors, com podem fer que en utilitzar aquests nous eines, aquestes direccions, aquests indicadors, i roscat coses de nosaltres mateixos? Bé, suposem que aquí, es tracta d'un grup dels números que volem emmagatzemar en un estructura de dades i recerca eficient. Sens dubte ens podem retrocedir a la setmana 2, llençar aquests en una matriu, i la recerca d'ells mitjançant la recerca binària. Divideix i venceràs. I, de fet, que va escriure recerca binària en PSET3, on es va implementar el programa de cerca. Però saps què. Hi ha una espècie de més forma intel·ligent de fer-ho. És una mica més sofisticat i potser ens permet veure què binària recerca és molt més ràpid. En primer lloc, anem a introduir la noció d'un arbre. Que tot i que en arbres realitat tipus de creixent així, en el món de la informàtica la ciència que tipus de créixer cap avall com un arbre de família, on vostè ha seus avis o besavis o el que sigui en la part superior, el patriarca i la matriarca de la família, només un anomenada arrel, node, per sota quals són els seus fills, per sota del qual són els seus fills, o seus descendents en general. I qualsevol penjant la part inferior de la família arbre, a més de ser el més jove de la família, també pot ser només genèricament anomenat les fulles de l'arbre. 

Així que això és només un munt de paraules i definicions d'una cosa que es diu un arbre en equip la ciència, com un arbre genealògic. Però hi ha encarnacions més elegants d'arbres, un dels quals es diu un arbre de cerca binari. I vostè pot classe de presa de pèl a part el que fa aquesta cosa. Bé, és binari en quin sentit? D'on ve el binari ve d'aquí? Ho sentim? No és tant un bé o. És més que cada un dels nodes no té més de dos fills, com veiem aquí. En general, un tree-- i seus pares i avis pot tenir tants fills o néts, ja que realment volen, i així, per exemple, no tenim tres els nens fora d'aquest node mà dreta, però en un arbre binari, un node té zero, un o dos fills com a màxim. I això és una bona propietat, perquè si està coronada per dos, serem capaços de obtenir una mica de base de registre de dos acció passant aquí en última instància. Així que tenim alguna cosa logarítmica. Però més sobre això en un moment. Cerca arbre vol dir que els números són disposat de tal manera que el fill esquerre de valor és més gran que l'arrel. I el seu fill dret és més gran que l'arrel. En altres paraules, si vostè pren algun dels limfàtics, els cercles en aquesta imatge, i mira a la seva esquerra nen i el seu fill dret, el primer ha de ser inferior a, la segona ha de ser més gran que. Així seny comprovar 55. Es nen deixat és 33. És menys. 55, el seu fill dret és 77. És més gran que. I això és una definició recursiva. Podríem revisar cada un dels nodes i el mateix patró obstaculitzin. 

Així que el que és bo en un arbre binari de recerca, és que un, podem posar-lo en pràctica amb una estructura, igual que aquest. I tot i que estem llançant un munt d'estructures en la seva, són un tant intuïtiva ara amb sort. La sintaxi és encara arcana amb certesa, però el contingut d'un node en aquest context-- i guardem usant el node paraula, si es tracta d'un rectangle a la pantalla o un cercle, que és només una mica de contenidor genèric, en aquest cas d'un arbre, com el que es vam veure, necessitem un nombre enter en cada un dels nodes i llavors necessito dos punters apuntant al fill esquerre i el fill dret, respectivament. Així que aquesta és la forma en què podria implementar que en una estructura. I com podria jo posar en pràctica en el codi? Bé, anem a fer un ràpid mirar a aquest petit exemple. No és funcional, però he copiat i enganxat aquesta estructura. I si la meva funció per a un binari arbre de cerca es diu recerca, i això té dos arguments, 1 N sencer i un punter a un node, de manera que un punter a l'arbre o un punter a l'arrel d'un arbre, com faig per a la recerca de N? Bé, en primer lloc, perquè sóc tractar amb punters, Jo vaig a fer una comprovació de validesa. Si és igual als iguals arbre nul, és N en aquest arbre o no en aquest arbre? No pot ser, oi? Si estic passat nul, no hi ha res allà. Pot ser que també acaba de cegament dir return false. Si em dones res, segurament no pot trobar qualsevol nombre N. Llavors, què més podria jo comprovi ara? Jo vaig a dir així més si N és menys del que està en el node de l'arbre que he estat lliurar valor N. En altres paraules, si el nombre estic buscant, N, és menor que el node que estic mirant. I el node estic buscant per la qual cosa es diu arbre, i recordar l'exemple anterior per obtenir el valor d'un punter, Utilitzo la notació fletxa. Així que si n és menor que l'arbre fletxa N, vull anar conceptualment esquerra. Com puc expressar searching vaig ser? Perquè quedi clar, si això és la imatge en qüestió, i m'han passat aquesta superior arrow això està apuntant cap avall. Aquesta és la meva punter del arbre. Estic apuntant a l'arrel de l'arbre. I estic buscant per exemple, per el número 44, de manera arbitrària. És 44 menor o més gran que 55 òbviament? Així que és menys. I pel que aquesta condició s'aplica si. Així conceptualment, el que és el que vull buscar següent si estic buscant 44? Sí? 

Exactament, vull buscar el fill esquerre, o el sub-arbre de l'esquerra d'aquesta imatge. I, de fet, em va deixar a través la imatge aquí sota per un moment, ja que No puc esgarrapar això. Si començo aquí a 55, i Sé que el valor 44 Jo estic buscant és a l'esquerra, és una espècie de com arrencar la guia telefònica en mitjà o esquinçar l'arbre per la meitat. Jo ja no he de preocupar tot aquest mitjà de l'arbre. I, no obstant això, curiosament, en termes de la estructura, aquesta cosa aquí que comença amb 33, que la mateixa és un arbre de cerca binària. Vaig dir la paraula recurrent abans perquè de fet aquesta és una estructura de dades que per definició és recursiva. És possible que tingui un arbre que és això gran, però cada un dels seus fills representa un arbre una mica més petit. En lloc de que sigui l'avi o l'àvia, ara és només mare o-- No puc no dir-- mare o pare, això seria estrany. En lloc dels dos nens allà seria com germà i germana. Una nova generació de l'arbre genealògic. Però estructuralment, és la mateixa idea. I resulta que tinc una funció amb el qual puc buscar una recerca binària arbre. Es diu cerca. Busco N en arbre de fletxa esquerra else if N és més gran que el valor que sóc actualment. 55 en la història fa un moment. Tinc una funció anomenada recerca que puc simplement N passar això i buscar de forma recursiva el sub-arbre i acaba de retorn sigui quina sigui la resposta. Else Tinc una mica de cas base final aquí. 

Quin és l'últim cas? Arbre és o bé nul. El valor o jo estic buscant és menys del que o més gran que la o igual a ella. I jo podria dir igual iguals, però lògicament és equivalent a només dir més aquí. Tan cert és el que trobo alguna cosa. Així que espero que aquest és un Fins i tot exemple més convincent que la funció sigma estúpid vam fer un parell de conferències esquena, on era tan fàcil d'usar un bucle per explicar tots els números d'un a N. Aquí, amb una estructura de dades que en si és de forma recursiva Definim i recursiva atrets, ara tenir la capacitat d'expressar-nos en el codi que sí és recursiu. Així que aquest és el mateix codi exacte aquí. 

Llavors, quins altres problemes podem resoldre? Així que un ràpid pas de distància de arbres per un moment. Aquí és, diguem, la bandera alemanya. I hi ha clarament una patró per a aquest indicador. I hi ha un munt de banderes del món que són tan simple com això en termes dels seus colors i patrons. Però suposem que aquest s'emmagatzema com una GIF o JPEG, o mapa de bits o un ping, qualsevol format d'arxiu gràfic amb el qual està familiaritzat, alguns dels quals estem jugant amb en PSET4. Això no sembla que val la pena per emmagatzemar píxel negre, píxel negre, píxel negre, punt, punt, punt, un munt de píxels negres per a la primera línia d'exploració, o fila, a continuació, en el seu conjunt munt de la mateixa, llavors un grapat sencer de la mateixa, i després una tota munt de píxels vermells, píxels vermells, píxels vermells, a continuació, en el seu conjunt munt de píxels de color groc, groc, oi? 

Hi ha tal ineficiència aquí. Com faria vostè intuïtivament comprimir la bandera alemanya si la seva aplicació com un arxiu? Igual que el que la informació no podem nosaltres molestar emmagatzemar en el disc per tal per disminuir la mida del nostre arxiu de com un megabyte a un kilobyte, alguna cosa més petit? On es troba la redundància aquí per ser clar? Què podria fer? Sí? Exactament. Per què no en lloc de recordar el color de cada píxel donaran de la mateixa manera que ho està fent en PSET4 amb el format d'arxiu de mapa de bits, ¿Per què no acaba de Representes a la columna de l'esquerra de píxels, per exemple un munt de píxels negres, un grup de color vermell, i un munt de groc, i després simplement alguna manera codificar el idea de la repetició d'aquest 100 vegades o repetir això 1.000 vegades? On 100 o 1000 és només un nombre enter, de manera que pot aconseguir lluny amb prou feines un sol número en lloc de centenars o milers píxels d'addicionals. I de fet, així és com ens podria comprimir la bandera alemanya. I Ara què passa amb la bandera francesa? I una mica d'algun tipus de exercici mental, que la bandera es pot comprimir més en el disc? La bandera alemanya o els francesos bandera, si prenem aquest enfocament? La bandera alemanya, perquè hi ha redundància més horitzontal. I per disseny, molts arxius gràfic formats de fet funcionen com a línies d'escaneig horitzontalment. Podrien treballar verticalment, just la humanitat Fa anys decidit que anem a en general, pensar en fila coses per fila en lloc de la columna per columna. Així que de fet si fossis per mirar l'arxiu mida d'una bandera alemanya i francesa bandera, sempre que la resolució és el mateix, la mateixa amplada i l'altura, aquest aquí serà més gran, perquè vostè haver de repetir tres vegades. Ha d'especificar blau, repeteixi a tu mateix, blanc, repeteixi vostè mateix, vermell, et repeteixis. No es pot anar tot el camí a la dreta. I com un a part, per fer esborrar la compressió és a tot arreu, si aquestes són 4 quadres d'un vídeo-- vostè podria recordar que una pel·lícula o vídeo és generalment com 29 o 30 fotogrames per segon. És com un petit llibre de tapa on simplement veure la imatge, imatge, imatge, imatge, imatge acaba molt ràpid pel que sembla els actors de la pantalla estan movent. Aquí està una borinot en la part superior d'un ram de flors. I tot i que podria ser una mena de difícil de veure a simple vista, l'únic que es mou en aquesta pel·lícula és l'abella. 

Quin és mut sobre l'emmagatzematge vídeo sense comprimir? És una mica una pèrdua per emmagatzemar vídeo com quatre imatges gairebé idèntiques que difereixen només en la mesura que l'abella és. Vostè pot tirar més d'aquesta informació i només recordar, per exemple, el primer fotograma i l'última trama, fotogrames clau si ha Alguna vegada has sentit la paraula, i acaba d'emmagatzemar en el mig, on l'abella és. I vostè no ha de emmagatzemar la totalitat de la rosa, i el blau, i el valors verds també. Així que això és per dir només això compressió està a tot arreu. És una tècnica que utilitzem sovint o donar per fet aquests dies. 

Però, ¿com comprimir text? Com vostè va sobre la compressió de text? Bé, cada un dels personatges de ASCII és un byte, o vuit bits. I això és una mica ximple, no? Com que és probable que el tipus A i E i I i O i U molt més de les vegades com W o Q o Z, depenent de l'idioma en què estàs escrivint, sens dubte. I per què estem fent servir vuit bits per a cada lletra, inclosos els menys lletres populars, oi? Per què no utilitzar menys bits per les lletres súper populars I igual, les coses que endevinin primer a la Roda de la Fortuna, i utilitzar més bits per les lletres menys populars? Per què? A causa de que només anem a utilitzar-los amb menys freqüència. 

Bé, resulta que no tenen hagut intents de fer això. I si vostè recorda de grau l'escola o l'institut, el codi Morse. Codi Morse té punts i guions que poden ser transmesa al llarg d'un filferro com sons o senyals d'algun tipus. Però el codi Morse és un super net. És una espècie d'un sistema binari en que té punts o guions. Però si vostè veu, per exemple, dos punts. O si vostè pensa de nou a l'operador qui va com bip, bip, bip, xiulet, colpejar una mica el gallet que transmet un senyal, si, el destinatari, rep de dos punts, quin missatge han rebut? Completament arbitrària. 

I? I? O el que sobre-- o jo? Potser va ser només dos a la dreta d'E? Així que hi ha aquest problema de decodabilidad amb Morse codi, de manera que llevat que el persona que envia el missatge que en realitat entra en pausa per a vostè pot classificar de veure o escoltar els espais entre les lletres, que no és suficient només per enviar un flux de zeros i uns, o punts i ratlles, perquè no hi ha ambigüitat. I és un sol punt, de manera que si veure dos punts o escoltar dos punts, potser és dues E d'o potser és un I. Així que necessitem un sistema que és un poc més intel·ligent que això. Així que un home anomenat Huffman anys Fa passar exactament això. Així que només anem per prendre una ràpida mirada la forma en què els arbres són pertinents a aquest. Suposem que es tracta d'algun estúpid missatge que voleu enviar, composta d'anar del punt A, B, C de D's i E de, però hi ha una gran quantitat de redundància aquí. No està destinat a ser anglès. No està encriptada. És només un estúpid missatge amb un munt de repetició. Així que si vostè realment explicar tota la Atlètics, B, C de, D's, i E de, aquí està la freqüència. 20% de les cartes són A de fins a un 45% de les cartes són d'E, i tres freqüències. Comptem allà manualment i acaba de fer els càlculs. 

Així resulta que Huffman, fa algun temps, va adonar que, ja saps la qual cosa, si començo edifici un arbre, o el bosc dels arbres, si es vol, de la següent manera, puc fer el següent. Vaig a donar un node per a cada un de les cartes que m'importen i jo vaig a emmagatzemar dins d'aquest node les freqüències com a punt flotant valor, o vostè podria utilitzar una N, també, però nosaltres només farem servir un flotador aquí. I l'algoritme que proposar és que vostè prendre aquest bosc d'un sol node arbres, arbres tan super curts, i començar a connectar amb nous grups, nous pares, si es vol. I ho fa mitjançant l'elecció del dues freqüències més petits alhora. Així que vaig prendre el 10% i 10%. Crec un nou node. I que jo anomeno el nou node 20%. 

Quins dos nodes combino després? És una mica ambigua. Així que hi ha alguns casos de cantonada a considerar, però per mantenir les coses bastant, Vaig a triar 20% - Jo ara ignoro els nens. Vaig a triar 20% i 15% i dibuixa dues noves arestes. I ara que dos nodes Com puc lògicament combino? No feu cas de tots els nens, tots els néts, només cal veure les arrels ara. ¿Amb quin de dos nodes vincle junts? Punt dos i 0,35. Així que permetin-me dibuixar dues noves arestes. I llavors jo només en tinc un esquerre. Així que aquí està un arbre. I s'ha elaborat deliberadament mirar espècie de bonic, de notar que les vores tenen També ha etiquetat zero i un. Així que totes les vores esquerres són zero arbitràriament, però consistent. Totes les vores drets són estimats. 

I així ho Hoffman proposa és, si vostè vol representar una B, en lloc de representar el nombre 66 com un arxiu ASCII que és vuit bits sencers, Saps què, botiga només el patró zero, zero, zero, zero, perquè aquest és el camí del meu arbre, arbre del Sr. Huffman, al full de l'arrel. Si voleu emmagatzemar un I, per contra, no ho facis enviar vuit bits que representen una E. En el seu lloc, envieu quin patró de bits? Un. I el que és bo d'això és que E és la lletra més popular, i utilitzeu el codi més curt per a això. El següent més popular carta sembla que va ser A. I així la quantitat de bits no es proposa utilitzar per això? Zero, un. 

I com està implementat ja que aquest arbre, per ara m'ho dius a mi estipulo que hi ha sense ambigüitat com en Morse codi, perquè tot el cartes que t'importen estan a l'extrem d'aquestes vores. Així que això és només una aplicació d'un arbre. Aquesta és-- i vaig ona la meva mà en aquest com podria aplicar això com una estructura C. Només hem de combinar un símbol, com un char, i la freqüència en l'esquerra i la dreta. Però donem una ullada a les dues exemples finals que Tu arribar a ser molt familiaritzat amb després qüestionari de zero en un problema fixar cinc. 

Així que no és l'estructura de dades coneguda com una taula hash. I una taula hash és una espècie de refredar en què té galledes. I suposo que hi ha quatre cubs aquí, només quatre espais en blanc. Aquí hi ha una baralla de cartes, i aquí està club, espasa, club, diamant, club, diamants, clubs, diamants, clubs-- pel que aquest és l'atzar. Cors, Hearts-- així que estic bucketizing totes les entrades aquí. I a les necessitats de la taula de hash mirar a la seva entrada, i després posar-lo en un determinat col·locar sobre la base del que es veu. És un algoritme. I jo estava fent servir un super algoritme visual simple. La part més dura de la qual era recordant quines eren les fotos. I després hi ha quatre coses totals. 

Ara les piles estaven creixent, la qual cosa és una cosa disseny deliberat aquí. Però què més podia fer? Així que en realitat aquí tenim una munt de vells llibres de l'examen de l'escola. Suposem que un grup de noms dels estudiants són d'aquí. Aquí hi ha una taula hash més gran. En lloc de quatre cubs, He, diguem 26. I no volíem anar prestat 26 coses de fora [? Annenberg?], Pel que aquí és de cinc que representen A fins a la Z. I si jo veure a un estudiant el nom del qual comença amb A, Vaig a posar el seu qüestionari allà. Si algú comença amb C, allà, A-- realitat, no volia fer això. B passa per aquí. Així que tinc A i B i C. I Ara aquí està un altre estudiant A. Però si aquesta taula hash és implementat amb una matriu, Sóc una mena de fotut en aquest punt, no? Jo com que necessito posar això en algun lloc. 

Així que una manera de que pugui resoldre això és, tot dret, A està ocupada, B està ocupat, C està ocupat. Vaig a posar-lo en D. Així que en primer, tinc accés instantani a l'atzar a cada un dels cubs per als estudiants. Però ara és una espècie de degenerar en alguna cosa lineal, perquè si vull buscar algú el nom comença amb A, puc comprovar aquí. Però si això no és l'A estudiant que estic buscant, Jo com que he de començar a comprovar les galledes, perquè el que vaig fer era una mena de forma lineal sondejar l'estructura de dades. Una forma estúpida de dir prou amb veure per a la primera obertura disponible, i posar com un pla B, per així dir-ho, o pla D en aquest cas, el valor en aquesta ubicació. Això és just el que si ha té 26 ubicacions i no hi ha estudiants amb el nom de Q o Z, o alguna cosa així que, almenys que estigui utilitzant l'espai. 

Però ja hem vist més solucions intel·ligents aquí, oi? Què faria vostè en el seu lloc si vostè té un accident? Si dues persones tenen el nom de A, el que faria han estat més intel·ligent o més solució intuïtiva que només posar una on se suposa que D a ser? Per què no només ha d'anar [exterior? Annenberg?], com malloc, un altre node, el va posar aquí i, a continuació, posar que un estudiant aquí. Així que bàsicament tinc algun tipus d'una matriu, o potser amb més elegància que a nosaltres començant a veure una llista enllaçada. 

I així una taula hash és una estructura que podria tenir un aspecte com aquest, però més intel·ligentment, cosa anomenada encadenament separat, pel que una taula hash simplement és una matriu, cada un els elements no és un nombre, és en si mateix una llista enllaçada. Així que vostè obtingui accés súper ràpid decidir on hash del seu valor a. Igual que amb l'exemple de les targetes, Vaig fer decisions molt ràpides. Cors va aquí, els diamants va aquí. El mateix dic, A va aquí, D va aquí, B va aquí. Així super ràpid look-ups, i si li passa a executar en un cas col·lisions en el qual has, dos les persones amb el mateix nom, bé, llavors que acaba de començar que els uneix. I potser mantenir ordenats per ordre alfabètic, potser vostè no ho fa. Però almenys ara tenim el dinamisme. Així, d'una banda tenim súper ràpid constant de temps, i el tipus de temps lineal involucrats si aquestes llistes enllaçades començar a ser una mica llarga. 

Així que aquesta classe de tonto, Fa anys broma geek. Al CS50 hack-a-thon, quan els estudiants del check in, alguns TF o CA cada any pensa que és graciós que aguantar un senyal d'aquest tipus, on s'acaba vol dir que si el seu nom comença amb A, anar per aquest camí. Si el seu nom comença amb una B, aneu esto-- OK, és curiós potser més tard en el semestre. Però hi ha una altra manera de fer això, també. Torna a això. 

Així que hi ha aquesta estructura. I aquesta és la nostra última estructura per avui, que és una cosa que es diu un trie. T-R-I-I, que per alguna raó és curta per a la recuperació, però que es diu trie. Així que un trie és un altre interessant amalgama de moltes d'aquestes idees. És un arbre, el que hem vist abans. No és un arbre de cerca binària. És un arbre amb qualsevol nombre de fills, però cada un dels nens en un trie és una matriu. Una matriu de mida, diguem, 26 o potser 27 si vols donar suport noms amb guions o apòstrofs en els noms de les persones. 

I el que aquesta és una estructura de dades. I si es mira des de dalt a baix, com si mirar el node superior allà, M, és que apunta al més a l'esquerra allà, que després és A, X, W, E, L, L. Això és només una estructura de dades que de forma arbitrària és emmagatzemar noms de les persones. I Maxwell s'emmagatzema amb només seguir un camí de matriu a matriu a matriu. Però el que és sorprenent d'un trie és que, mentre que una llista enllaçada i fins i tot una matriu, el millor que hem aconseguit és temps lineal o logarítmica temps buscant a algú. En aquesta estructura de dades d'un trie, si la meva estructura de dades té un nom en ella i estic a la recerca de Maxwell, estic anar a buscar-ràpidament. Jo només busco M-A-X-W-E-L-L. Si aquesta estructura de dades, per contra, si N és un milió, si hi ha una milió de noms en aquesta estructura de dades, Maxwell encara serà detectable després de només M-A-X-W-E-L-L passos. I els passos David-- D-A-V-me-D. En altres paraules, mitjançant la construcció una estructura de dades que és aconseguit tots aquests arrays, tots els quals ells donen suport d'accés aleatori, Puc començar a buscar de la gent nom usant una quantitat de temps que és proporcional a no el nombre de les coses en l'estructura de dades, com un milió de noms existents. La quantitat de temps que em porta a trobar M-A-X-W-E-L-L en aquesta estructura de dades es proporcional no a la mida de l'estructura de dades, però a la longitud del nom. I realista el noms que estan mirant cap amunt Mai van a estar boig de llarg. Potser algú té un caràcter 10 nom, nom de 20 caràcters. Certament és finita, oi? No és un ésser humà a la Terra que té el nom més llarg possible, però aquest nom és una constant longitud de valor, no? És no varia en cap sentit. Així d'aquesta manera, tenim aconseguit una estructura de dades és a dir constant de temps de consulta. No obstant això, pren una sèrie de mesures depenent de la longitud de l'entrada, però no el nombre del nom en l'estructura de dades. Així que si dupliquem el nombre de noms l'any que ve a partir d'1000000000-2000000000, troballa Maxwell va a prendre el mateix nombre exacte de set passos per trobar-lo. I així sembla que hem aconseguit nostre sant grial de temps d'execució. 

Així que un parell d'anunciar. Qüestionari zero s'acosta. Més sobre això en la pàgina web del curs durant el pròxim parell de dies. Dilluns de lecture-- És un dia de festa aquí a Harvard dilluns. No està a New Haven, així que estem prenent la classe a New Haven de la conferència el dilluns. Tot serà filmat i transmès en viu com sempre, però anem a acabar avui amb un clip de 30 segons anomenats "Pensaments profunds" per Daven Farnham, que es va inspirar l'any passat per dissabte "Pensaments profunds" de Night Live per Jack pràctic, que Ara ha de tenir sentit. 

CINEMA: I ara, "Deep Pensaments "de Daven Farnham. Taula hash. 

ALTAVEU 1: Molt bé, això és tot per ara. Ens veiem la setmana que ve. 

DOUG: Per veure en acció. Així que anem a fer una ullada a això ara mateix. Així que aquí tenim una matriu sense classificar. 

IAN: Doug, pots seguir endavant i reinici això per només un segon, si us plau. D'acord, les càmeres estan rodant, per la qual acció cada vegada que estigui llest, Doug, ¿d'acord? DOUG: Molt bé, així que el que tenim aquí és una sèrie sense classificar. I he vaig acolorir tots els elements vermell per indicar que és, de fet, sense classificar. Així que recordem que la primera cosa que fem és classifiquem la meitat esquerra de la matriu. Després vam classificar la dreta mitjà de la matriu. I ja-da, ja-da, ja-da, els fonen. I tenim una gamma completament ordenat. Així és com fusionar tipus d'obres. 

IAN: Espera, espera, espera, tallar, tallar, tallar, tallar. Doug, no pots simplement ja-da, ja-da, ja-da, el seu camí a través de combinació de classe. 

DOUG: Em acaba de fer. Està bé. Som bons per anar. Seguim la rodadura. Així que de totes maneres, 

IAN: Vostè ha d'explicar més plenament que això. Això no és suficient. DOUG: Ian, no ho fem que hagi de tornar a un. Està bé. Així que de totes maneres, si seguim amb merge-- Ian, estem enmig de la filmació. 

IAN: Ho sé. I no podem simplement ja-da, ja-da, ja-da, a través de tot el procés. Vostè ha d'explicar com el Ambdues parts queden fusionades juntes. 

DOUG: Però ja hem va explicar com els dos sides-- 

IAN: Vostè acaba mostrarà ells una matriu de mescla. DOUG: Ells coneixen el procés. Estan bé. Hem passat més de deu vegades. 

IAN: Vostè acaba de saltar per sobre d'ella. Anem a tornar a un, ¿No és així ja-da, ja-da sobre ell. Molt bé, de nou a un. 

DOUG: He de tornar a través de totes les diapositives? Deu meu. És com la sisena vegada, Ian. Està bé. 

IAN: D'acord. Estàs preparat? Gran. Acció.