[REPRODUCCIÓ DE MÚSICA] 

ANDI Peng: Benvinguts a la setmana 6 de la secció. Ens desviem del nostre estàndard temps de la secció de dimarts a la tarda a aquesta bella matí de diumenge. Gràcies per tot el món que m'acompanyen avui, però de debò, una ronda d'aplaudiments. 

Aquesta és una molt gran esforç. Gairebé ni tan sols faig en el temps, però estava bé. Així que sé que tots vostès simplement han arribat a la prova. En primer lloc, la benvinguda a l'altra cara d'això. 

En segon lloc, parlarem sobre això. Parlarem de la prova. Parlarem de com que estàs fent a la classe. Vas a estar bé. Tinc seus qüestionaris per que al final d'aquí, així que si vostès volen tenir una mirada en ella, totalment bé. 

Així que ràpidament abans de començar, el ordre del dia d'avui és el següent. Com es pot veure, estem acomiadament bàsicament ràpida a través d'un munt d'estructures de dades molt, molt, molt ràpid. Així que, com a tal, no serà avui molt interactiva. Només serà la meva classe de crits coses que vostè, i si et confonc, si vaig massa ràpid, que em faci saber. No són més que diverses dades estructures, i com a part del conjunt de processadors per a aquest setmana que ve, podràs se li pregunti per implementar un d'ells, potser dos d'ells-- dues d'elles en el seu conjunt de processadors. OK, així que només vaig a començar amb alguns anuncis. Anem a repassar piles i cues més en profunditat que el que vam fer abans de la prova. Anem a repassar units llista de nou, una vegada més, més en profunditat del que que teníem abans de la prova. I després parlarem d'haixix taules, arbres i tries, que són tots bastant necessari per a la seva conjunt de processadors. I després anem a repassar alguns consells útils per pset5. 

OK, així que prova 0. La mitjana va ser d'un 58%. Era molt baix, i així vostès tot va fer molt, molt bé, d'acord amb aquest. 

Més o menys, regla d'or és que si vostè és dins d'una desviació estàndard de la mitjana sobretot perquè estem en un menor secció còmode, estàs totalment bé. Vostè està en pista. La vida és bona. 

Sé que és por pensar que Tinc com un 40% en aquesta prova. Vaig a deixar aquesta classe. L'prometo, no estàs va a fallar la classe. Vostè és totalment bé. 

Per a aquells de vostès que ho va superar la mitjana, impressionant, impressionant, com, de debò ben fet. Els tinc amb mi. Aquí podreu aconseguir- al final de la secció. Deixeu-me saber si vostè té qualsevol qüestions, preguntes amb elles. Si sumem la seva qualificació malament, contacteu amb nosaltres. 

OK, així pset5, això és una realitat setmana estrany per Yale en el sentit que el nostre conjunt de processadors s'ha de Dimecres al migdia inclosos a la fi del dia, pel que és en realitat a causa teòricament dimarts al migdia. Probablement ningú va acabar Dimarts al migdia. Això és totalment bé. Tindrem hores d'oficina aquesta nit, així com la nit de dilluns. I totes les seccions d'aquesta setmana ho farà en realitat convertir-se en tallers, així que sigues lliure per fer esclatar en qualsevol secció que desitgi, i estaran espècie de mini-pset tallers per a ajuda en això. Així que, com a tal, aquesta és l'única secció de on som material didàctic. Totes les altres seccions se centraran exclusivament en l'ajuda per al conjunt de processadors. Sí? 

AUDIÈNCIA: On són les hores d'oficina? 

ANDI Peng: Les hores d'oficina aquesta nit-- oh, bona pregunta. Crec que les hores d'oficina aquesta nit estan a la garjola o al Commons. Si marca en línia CS50 i vostè va a les hores d'oficina, ha d'haver un horari que on tots ells són diu. 

Jo sé bé aquesta nit o demà és trull, i crec que podem tenir béns comuns de l'altra nit. No estic segur. Bona pregunta. Comprovi en CS50. 

Cool, preguntes sobre el calendari per a la propera com tres dies? Et prometo que vostès com David va dir, es tracta de la part superior del turó. Vostès són gairebé allà. A només tres dies més. Arribar allà, i després tots ens vindrem a baix. Tindrem un bon descans CS-lliure. Tornarem. Ens submergim en la web programació i desenvolupament, coses que són molt divertit comparar a alguns dels altres conjunts de processadors. I va ser fred i tindrem un munt de diversió. Tindrem més dolços. Ho sento pels dolços. He oblidat dolços. Era un matí aspra. Així que nois està gairebé allà, i estic molt orgullós de vosaltres. 

OK, així que apila. Qui va estimar a la pregunta sobre Jack i la seva roba en el concurs? Ningú? OK, això està bé. 

Per tant, bàsicament com puguis foto de Jack, aquest noi aquí, li encanta prendre la roba de la part superior de la pila, i es posa de nou en la pila després que ha fet. Així d'aquesta manera, mai sembla estar cada vegada a la part inferior de la apilar a la seva roba. Per tant aquest tipus de descriu l'estructura de dades bàsica de com s'implementa una pila. 

Essencialment, pensar en un apilar com qualsevol pila d'objectes on posar les coses a la part superior, i després els fa esclatar cap a fora de la part superior. Així LIFO és l'acrònim que ens agrada al servei- Last In, First Out. I així, l'última en la part superior de la pila és el primer que surt. I així els dos termes ens agrada associar amb això que es diu empenta i pop. Quan empenys alguna cosa sobre la apilar, i vostè fa esclatar una còpia de seguretat. 

Així que suposo que això és una mena de concepte abstracte per a aquells de vostès que volen veure com un aplicació real d'aquest en el món real. Quants de vosaltres heu escrit un assaig potser com una hora abans que es va deure, i has esborrat accidentalment un enorme part d'ella, com per accident? I llavors el comandament fer que utilitzem per posar de nou? Control-Z, sí? Control-Z, de manera que la quantitat de vegades que Control-Z ha salvat la vida, ha salvat el cul, cada vegada que això és implementat a través d'una pila. 

Essencialment tota la informació que està en el document de Word, que és empès i es va ficar en la voluntat. I així, en essència cada vegada que esborrar res, vostè fa esclatar una còpia de seguretat. I llavors, si vostè ho necessita de nou, que empènyer-la, que és el que fa de Control-C. I la funció món tan real de l'estructura de dades del simple pot ajudar amb la seva vida quotidiana. 

Així que un struct és la forma en què que realment creem una pila. Escrivim definir estructura, i després vam anomenar la pila a la part inferior. I dins de la pila, tenim dos paràmetres que essencialment es pot manipular, així que tenim carbó capacitat cordes estrella. 

Tot el que s'està fent és la creació d'una matriu que podem emmagatzemar el que vulguis el qual podem determinar la seva capacitat. La capacitat és la quantitat màxima de articles que es poden posar en aquesta matriu. int size és el comptador que manté un registre de quants elements són actualment a la pila. Així llavors podem perdre de vista, A, tant de res la pila real és, i, B, quant d'aquesta pila omplim perquè no volem a desbordar sobre el que la nostra capacitat és. 

Així, per exemple, aquesta bella pregunta era en la seva qüestionari. En essència, com empenyem a la part superior d'una pila. Bastant simple. Si ens fixem en ella, anem a caminar a través d'aquest. Si [inaudible] size-- recordi, sempre que vol accedir a qualsevol paràmetre dins d'una estructura, ho fa el nom de la struct.parameter. 

En aquest cas, s és el nom del nostre stack. Volem accedir la mida de la mateixa, pel que fem s.size. Així que, mentre la mida no és igual a la capacitat o tan llarg ja que és menys de la capacitat, ja sigui que treballar aquí. 

Vols accedir a l'interior de la pila, per la s.strings, i vostè va a posar aquest nou número que desitja inserir en allà. Diguem que anem a voler inseriu int n a la pila, podríem fer s.strings, suports, s.size és igual a n. A causa de que la mida és on ens Actualment es troben a la pila si anem a empènyer en, simplement accedim on la mida és, la plenitud actual de la pila, i empenyem la int n en la mateixa. I després volem assegurar-nos que també estem incrementant la mida de la n, perquè puguem fer un seguiment que hem afegeix una quantitat a la pila. Ara tenim una mida més gran. Això aquí té sentit tothom, com lògicament funciona? Era una mena de ràpid. AUDIÈNCIA: Pot anar més els s.stringss.strings [s.size] de nou? ANDI Peng: És clar, i què fa s.size Actualment donar-nos? AUDIÈNCIA: És la mida actual. ANDI Peng: Exactament, de manera que el índex actual que el nostre mida és a, i pel que volem posar el nou número sencer que volem inserir en s.size. Això té sentit? A causa s.strings, tot el que és és el nom de la matriu. Tot el que és és l'accés a la matriu dins la nostra estructura, i pel que si volem col·locar n en aquest índex, només podem accedir-hi utilitzant suports s.size. Fresc. 

Molt bé, pop, em Pseudocodi fora per a vostès, sinó concepte similar. Això té sentit? Si la mida és més gran que zero, llavors vostè sap que vostè vol prendre alguna cosa perquè si la mida no és més gran que zero, llavors vostè no tenen res a la pila. 

Pel que només desitja executar aquest codi, només pot pop si hi ha alguna cosa de pop. Així que si la mida és més gran de 0, tenim menys la mida. Ens disminuir la mida i després vam tornar el que hi ha dins d'ella perquè fent esclatar, volem Accés tot el que s'emmagatzema en l'índex de la part superior de la pila. Tot té sentit? Si et vaig fer nois escriure això, Vols que nois capaços d'escriure? OK, vostès poden jugar una estona amb ell. No us preocupeu si vostè no ho entenen. No tenim temps per codificar cap a fora avui perquè hem té un munt d'aquestes estructures de passar, però essencialment pseudocodi, molt, molt similar a empènyer. Només has de seguir al llarg de la lògica. Assegureu-vos que està accedint tot el característiques de la seva estructura correctament. Sí? 

AUDIÈNCIA: Will aquestes diapositives i tot això sigui avui-ish? ANDI Peng: Sempre, si. Vaig a tractar de posar això com una hora després. Vaig per correu electrònic David, David intentarà el va posar com una hora després d'això. 

OK, així que després ens endinsem en aquest altre estructura de dades preciosa diu una cua. Com vostès poden veure aquí, una cua, per als britànics entre nosaltres, tot el que és és una línia. Així que al contrari del que creus que una pila és, una cua és exactament el lògicament vostè pensa que és. Es porta a terme per les regles de FIFO, que és First In, First Out. Si vostè és el primer una a la línia, vostè és el primer que que surt de la línia. 

Així que el que ens agrada anomenar a aquest es desencolatge i encolar. Si volem afegir alguna cosa a la nostra cua, ens enqueue. Si volem treure de la cua, o prendre una mica lluny, ens dequeue. 

Així mateix sentit que estem tipus de la creació d'elements de mida fixa que pot emmagatzemar certa coses, sinó que també pot canviar el lloc on estem col·locant paràmetres dins d'ells sobre la base de quin tipus de funcionalitat que volem. Així piles, volíem l'última un, N per ser el primer a sortir. Cola és que volem el primer en ser el primer que va sortir. 

Així que la de tipus struct definir, com es pot veure, que és una mica diferent del que era la pila perquè no només hem de seguir la pista d'on la mida és actualment, també volem fer un seguiment del cap així com en els que actualment som. Així que crec que és més fàcil si em baso això. Així que imaginem que tenim una cua, així que diguem que el cap és aquí. El cap de la línia, anem a Només cal dir que és en l'actualitat hi ha, i volem inserir alguna cosa a la cua. Vaig a trucar a mida essencialment és el mateix que la cua, Al final d'on vulgui que la seva cua és. Diguem que la mida és just aquí. 

Llavors, com pot un factiblemente inserir alguna cosa en una cua? Què índex volem col·locar on volem inserir en. Si aquest és el començament de la seva cua i aquest és el final de la mateixa o la mida de la mateixa, ¿on som que vulgueu afegir el següent objecte? 

AUDIÈNCIA: [inaudible] ANDI Peng: Exactament, voleu afegir que depenent has escrit. O això és en blanc o que està en blanc. Així que vostè vol afegir que probablement aquí perquè si la mida és-- si aquests estan plens, desitja afegir aquí mateix, no? 

I això és, encara que molt, molt simple, no és sempre correcta a causa de que la principal diferència entre una cua i una pila és que la cua pot en realitat ser manipulat de manera que els canvis del cap depenent d'on voleu el començament de la seva senyal per començar. I com a resultat, la seva cua També es canviarà. I així que fes un cop d'ull a aquest codi en aquest moment. Com també se'ls va demanar que vostès escriure en el concurs, de posada en cua. Potser anem a parlar a través de quin la resposta era el que era. 

No podia encaixar bastant aquesta línia en un, però essencialment aquest tros de codi ha d'estar en una sola línia. Passa com 30 segons. Fes un cop d'ull, i veure per què aquesta és la manera que ho és. 

Molt, estructura molt similar, molt, molt estructura similar a l'anterior apilar excepte potser una línia de codi. I que una línia de codi determina la funcionalitat. I el que realment diferencia una cua d'una pila. 

Algú vol prendre una punyalada en explicar per què has tinc aquesta cosa complicada en aquesta llista? Ens veiem el retorn del nostre meravellosa mòdul amic. Com vostès aviat vindrà a reconèixer en la programació, gairebé sempre vostè necessita alguna cosa per embolicar al voltant de qualsevol cosa, mòdul serà la forma de fer-ho. Així que sabent això, no volia que ningú per tractar d'explicar aquesta línia de codi? Sí, totes les respostes són acceptada i benvinguda. AUDIÈNCIA: Vostè està parlant amb mi? ANDI Peng: Sí. AUDIÈNCIA: Oh, no ho sento. ANDI Peng: OK, així que anem a caminar a través d'aquest codi. Així que quan vostè està tractant de afegir alguna cosa en una cua, a la bonica cas que el cap passa per ser just aquí, és molt fàcil per a nosaltres que només ha d'anar fins al final inserir alguna cosa, no? Però el punt central d'una cua és que el cap de fet pot dinàmicament canviar depenent d'on estem vol que el començament de la nostra q sigui, i com a tal, la cua També es canviarà. 

I així, imagino que això no era la cua, sinó que més aviat es tractava de la cua. Diguem que el cap és aquí. Diguem que la nostra cua es veia així. Si volguéssim canviar, on el començament de la línia és, diguem que canviem el cap d'aquesta manera i talles Aquí. 

Ara volem afegir alguna cosa a aquesta cua, però com vostès poden veure, que no és tan senzill com simplement afegir el és després que la mida perquè llavors ens quedem sense límits de la nostra gamma actual. Quan volem afegir realment és aquí. Aquesta és la bellesa d'una cua és que a nosaltres, visualment sembla que la línia és la següent, però quan s'emmagatzema en una estructura de dades, donen com com un cicle. En certa manera s'embolica al voltant a la part davantera de la mateixa manera que una línia també pot embolicar tot depenent d'on sigui que voler principi de la línia per a ser. I així, si prenem una mira aquí baix, anem a diem que volíem crear un funció de trucada en cua. Volíem afegir int n en què q. Si q.size q-- Anomenarem a que les nostres dades structure-- si el nostre queue.size no igual a la capacitat o si que és menys de la capacitat, q.strings és la matriu dins del nostre q. Anem a establir que igual a q.heads, que està just aquí, a més q.size pel mòdul de capacitat, que ens emboliqui volta per aquí. 

Així, en aquest exemple, l'índex del cap és 1, oi? L'índex de grandària és 0, 1, 2, 3, 4. Així que podem fer 1 més 4 de mòdul per la nostra capacitat, que és 5. Què ens donen? Quin és l'índex que que surt d'això? 

AUDIÈNCIA: 0. 

ANDI Peng: 0, el que passa a ser aquí, i així volem ser capaços per inserir en aquí. I així aquesta equació aquí espècie de tan sols funciona amb qualsevol nombre depenent d'on el seu cap i la seva grandària són. Si saps el que els són les coses, ja saps exactament on vol inserir tot el que sigui després de la seva cua. ¿Això té sentit per a tothom? 

Sé la classe d'un cervell sumari sobretot perquè aquest va arribar a les acaballes del seu concurs. Però esperem que tothom Ara pot entendre per què aquesta solució o aquesta funció és la forma en què ho és. Qualsevol persona una mica confús al respecte? D'ACORD. 

I ara, si vostè volgut treure de la cua, aquesta és on el nostre cap seria el canvi perquè si haguéssim de treure de la cua, no prenem fora de la final de la q. Volem treure el cap, oi? Així que, com a resultat, el cap canviarà, i és per això que quan encolar, has de mantenir un registre de on el seu cap i la seva mida han de ser capaç d'inserir en la posició correcta. 

I així quan dequeue, També Pseudocodi a terme. Siéntase lliure si vol per intentar codificar aquesta fora. Vostè vol moure el cap, oi? Si volia treure de la cua, em mouria el cap una altra vegada. Aquesta seria el cap. 

I el nostre grandària actual faria restar perquè ja no tenir quatre elements de la matriu. Només tenim tres, i després volem per tornar tot el que s'emmagatzema a l'interior del cap perquè volem aprofitar aquesta valor a terme de manera molt similar a la pila. Només vostè està prenent des d'un lloc diferent, i has de tornar a assignar el punter a diferent lloc com un resultat. Lògicament, tothom segueix? Gran. 

OK, així que anem a parlar una mica més en profunditat sobre llistes enllaçades perquè van a estar molt, molt valuosa perquè en el transcurs d'aquesta setmana de conjunts de processadors. Llistes enllaçades, com vostès record, tot el que són són nodes que són nodes de certa valors tant d'un valor i un punter que estan units entre si pels punters. I pel que l'estructura de com vam crear un node aquí és que tenir int n, que és el el valor en una botiga o cadena de n o el que vulguis cridar-ho, l'estrella carbó n. Struct estrella node, que és el punter que vostè desitja tenir en cada node, vostè va a haver de punta punter cap a la següent. Vas a tenir el cap d'una llista enllaçada que és va assenyalar la resta d' els valors així successivament i així successivament fins a arribar finalment al final. I aquest últim node és només anar a no tenir un punter. Es va a apuntar a nul, i és llavors quan saps que has arribat a la final de la llista enllaçada és quan la seva última punter no apunta res. 

Així que anirem una mica més en de profunditat respecte a com es faria possiblement cercar una llista enllaçada. Recorda el que són alguns dels inconvenients de les llistes enllaçades versos una sèrie en relació amb les recerques. Una matriu pot recerca binària, però per què no es pot fer això en una llista enllaçada? 

AUDIÈNCIA: Perquè estan tots connectats, però no sé molt bé on [Inaudible]. 

ANDI Peng: Sí, exactament per tal de recordar que la brillantor d'un array va ser el fet que teníem memòria d'accés aleatori, on si volia el valor de l'índex 06:00, jo podria dir que l'índex de sis, dóna'm aquest valor. I això és perquè les matrius es classifiquen en un espai contigu de memòria en un sol lloc, mentre que tipus de llistes enllaçades s'intercalen aleatòriament per tot arreu, i l'única manera que vostè pot trobar un és a través d'un punter que et diu l'adreça del lloc en què el pròxim node és. 

I així, com a resultat, l'única manera de per buscar a través d'una llista enllaçada és la recerca lineal. Perquè jo no sé exactament on el valor 12 a la llista enllaçada és, He de travessar la totalitat d'aquesta llista enllaçada es per un des del cap fins al primer node, al segon node, a la tercera node, tot el camí fins que finalment arribi a on aquest node que estic buscant és. I així, en aquest sentit, la recerca en una llista enllaçada és sempre n. Sempre és n. Sempre en el temps lineal. 

I pel que el codi en el qual implementem això, i això és una mica nou per a vostès des que nois realment no han parlat ni mai punters vist en la forma de cercar a través de punters, així que anem a caminar a través d' aquesta molt, molt lentament. Així que la recerca bool, dreta, imaginem que volem per crear una funció anomenada recerca que retorna true si vostè troba un valor dins de la vinculada llista, i retorna false en cas contrari. Llista d'estrelles de node és Actualment només el punter al primer element de la llista enllaçada. int n és el valor que vostè és buscar en aquesta llista. 

Així indicador de l'estrella node és igual a la llista. Això vol dir que estem configurant i la creació d'un punter al primer node dins de la llista. Tothom amb mi? Així que si ens anirem Torna aquí, tindria inicialitzat un punter que apunta a el cap del que la llista és. 

I després una vegada que arribi aquí, mentre que el punter no és igual a null, pel que és el bucle en el qual estem serà posteriorment travessar la resta de la nostra llista perquè el succeeix quan el punter equival a nul·la? Sabem que tener-- 

AUDIÈNCIA: [inaudible] 

ANDI Peng: Exactament, així que sabem que hem arribat al final de la llista, no? Si tornes aquí, cada node ha d'estar apuntant a un altre node i així successivament i així successivament fins a arribar, finalment, la cua de la llista enllaçada, que té un punter que acaba no assenyala en cap altre que no. Així que, bàsicament, saber que la llista encara és allà dalt fins que el punter no és igual a nul·la perquè una vegada que és igual a null, vostè sap que no hi ha més coses. 

Així que aquest és el bucle en el qual estem va a tenir la recerca real. I si els pointer-- fan que vegi aquest tipus de funció sageta en ella? Així que si punter apunta a n, si el punter en n és igual és igual a n, el que significa que si el punter que ets buscar a l'extrem de cada node és en realitat igual al valor que estàs buscant, llavors desitja tornar realitat. Així que, bàsicament, si vostè està en un node que té el valor que vostè està buscant, saps que has estat capaç de buscar amb èxit. 

Altrament, desitja establir el punter al següent node. Això és el que aquesta línia aquí està fent. Pointer és igual punter següent. Tothom vegi com això està treballant? 

I bàsicament vas a només recórrer la totalitat de la llista, restablir el punter cada vegada fins que finalment va colpejar el final de la llista. I vostè sap que no hi ha més nodes per buscar a través de, i llavors vostè pot tornar false perquè saps que, oh, bé, si jo he estat capaç de cercar a través de la totalitat de la llista. Si en aquest exemple, si volia per buscar el valor de 10, i em poso al capdavant, i Jo busco fins al fons, i, finalment, vaig arribar a això, que un punter que apunta a null, Sé que, merda, suposo que 10 no està en aquesta llista perquè no vaig poder trobar-lo. I estic al final de la llista. I en aquest cas vostè sap Vaig a tornar false. 

Anem que remull en una mica. Aquesta serà bastant important per a la seva conjunt de processadors. La lògica que és molt simple, potser sintàcticament simplement implementar-lo. Volen fer Assegureu-vos d'entendre. Fresc. 

OK, així que com ens hauria la inserció de nodes, la dreta, en una llista perquè recordi ¿Quins són els què dels beneficis d'haver una llista enllaçada front una matriu en termes d'emmagatzematge? 

AUDIÈNCIA: És dinàmic, així que és més fàcil A-- 

ANDI Peng: Exactament, pel que és dinàmic, que significa que pot expandir-se i contreure depenent de les necessitats de l'usuari. I així, en aquest sentit, no necessitem a perdre la memòria innecessària perquè si jo no sé quants valors que vull a la botiga, que no té sentit per a mi per crear una matriu causa si vull emmagatzemar 10 valors i puc crear una matriu de 1000, que és una gran quantitat de memòria perduda, assignat. És per això que volem utilitzar una lligat llista per ser capaç de dinàmicament canviar o reduir el nostre mida. 

I pel que fa a la inserció una mica més complicat. Ja que no podem accedir aleatòriament elements la forma en què ens d'una matriu. Si vull inserir un element en el setè índex, Jo només puc inserir en el setè índex. En una llista enllaçada, no ho fa bastant treballar amb la mateixa facilitat, i així si volíem inserir l'un aquí a la llista enllaçada, visualment, és molt fàcil de veure. Només volem inserir allà mateix, la dreta en el principi de la llista, just després del cap. 

Però la forma en què hem de reassignar els punters és una mica complicat o, lògicament, té sentit, però vostè vol assegurar-se que vostè ho té completament baix perquè l'última cosa que vull és tornar a assignar un punter al camí que estem fent aquí. Si eliminar la referència al punter del cap a 1, després, de sobte resta de la seva llista enllaçada es perd perquè vostè té en realitat no creat un gens temporal. Això es va assenyalar a la 2. Si reassigna el punter, llavors el resta de la seva llista està totalment perdut. Així que vols ser molt, molt acurat aquí per assignar la primera punter del que vol inserir en qualsevol lloc que vol, i llavors pot eliminar la referència a la resta de la seva llista. 

Així que això s'aplica a qualsevol lloc vostè està tractant d'inserir en. Si voleu inserir en el cap, si vols contestar aquí, si voleu inserir en Al final, bé, al final em suposo que ho faria només tenir cap punter, però voldrà assegurar-se que vostè no ho fa perdrà la resta de la llista. Un sempre vol assegurar- el nou node apunt cap al que vol inserir en, i llavors vostè pot afegir l'encadenament. Tothom clar? 

Això serà un dels problemes reals. Un dels problemes de la majoria de les vostè va a tenir en el seu conjunt de processadors és que vostè va a tractar de crear una llista enllaçada i les coses d'inserció però llavors només perdrà el resta de la seva llista enllaçada. I tu seràs com, no sé per què està succeint això? I és un dolor de passar per i buscar tots els seus punters. 

I et garanteixo en aquest conjunt de processadors, escriure i dibuixar aquests nodes fora serà molt, molt servicial. Així que vostè pot mantenir per complet la pista d'on tots els seus punters són, el que va malament, on tots els nodes són, el que ha de fer per accedir o inserir o eliminar o qualsevol d'ells. Tothom bé amb això? Fresc. 

Així que si volíem mirar el codi? Oh, no sé si pot veure ell-- OK, així a la part superior de tot el que és és una funció inserit anomenat on volem inserir int n en la llista enllaçada. Anem a caminar a través d'això. És una gran quantitat de codi, una gran quantitat de nova sintaxi. Estarem bé. 

Així que a la part superior, sempre que sigui volem crear res ¿Què és el que hem de fer, especialment si vostè vull que no s'emmagatzema a la pila però en el munt? Anem a un malloc, oi? Així que anem a crear un punter. Nodes, punter, nous iguals malloc la mida d'un node perquè volem que el node que es crearà. Volem que la quantitat de memòria que un node ocupa per ser assignat per al creació del nou node. 

I després anem a comprovar per veure si els nous iguals és igual a zero. Recorda el que vam dir? Facis el que malloc, ¿Què ha de fer sempre? Vostè ha de comprovar sempre per veure si és o no és nul. 

Per exemple, si el seu funcionament sistema estava completament ple, si no tingués més memòria en tot i tractes de malloc, tornaria nul per a vostè. I pel que si intenta utilitzar- quan s'estava apuntant a null, no vas a poder per accedir a aquesta informació. I així, com a tal, hem volgut fer Assegureu-vos que cada vegada que estiguis mallocing, sempre estàs comprovant si que la memòria que li ha assignat és nul. I si no ho és, llavors podem moure amb la resta del nostre codi. 

Així que anem a inicialitzar el nou node. Farem nova n és igual a n. I després farem setembre nou el punter de nou en nul perquè en aquest moment no ho fem vull res perquè apunti a. No tenim ni idea d'on que posarà vostè, i després, si volem inserir al cap, llavors podem reassignar el punter al capdavant. Tothom segueix la lògica d'on això està passant? 

Tot el que estem fent és crear una nova node, establint el punter a null, i després reassignar al cap si sabem que volem per inserir al cap. I llavors el cap va a apuntar cap a aquest nou node. Tothom d'acord amb això? 

Així que és un procés de dos passos. Cal assignar primer el que està creant. Establir aquest punter a la referència, i després pot espècie d'eliminar la referència la primera punter i apunti cap al nou node. On sigui que vol inserir, que la lògica va ser veritat. 

És una cosa així com l'assignació de variables temporals. Recordi, vostè té per assegurar-se que vostè no perdre de vista que si estàs intercanviant. Vostè vol assegurar-se que vostè té un variable temporal aquest tipus de guarda la pista d'on aquesta cosa s'emmagatzema perquè no perdi cap valor en el curs de com jugar una mica amb ell. 

OK, així que el codi estarà aquí. Vostès mirin després de la secció. Serà allà. 

Així que suposo que ho fa aquesta diferència si volíem per inserir al mig o al final? Algú té una idea del que és la pseudocodi com la referència lògica que prendríem si volíem per inserir-lo al mig? Així que si volíem per inserir-lo al cap, tot el que fem és crear un nou node. Hem creat el punter d'aquest nou node a qualsevol que sigui el cap, i després ens vam posar al cap al nou node, oi? Si volguéssim per inserir-lo al mig de la llista, el que hauríem de fer? 

AUDIÈNCIA: Seguiria ser un procés similar de com l'assignació de punter i després assignar aquest punter, però hauríem de situar allà. 

ANDI Peng: Exactament, així que exactament el mateix procés, excepte vostè que localitzar el lloc exacte que vol que el nou punter a entrar en, pel que si vull inserir en el mitjà de lligat pel·lícules-- OK, diguem que és la nostra llista enllaçada. Si volem inserir aquí mateix, crearem un nou node. Anem a malloc. Crearem un nou node. Anem a assignar el punter d'aquest node aquí. 

Però el problema que difereix des d'on el cap és és que sabíem exactament on el cap és. Va ser just en el primer, no? Però aquí hem de seguir la pista d'on estem inserir-lo en. Si estem inserint la nostra node d'aquí, tenim per assegurar-se que la anterior a aquest node és el que reassigna el punter. Llavors vostè ha de tipus de no perdre de vista dues coses. Si es manté la pista d'on aquesta node actualment està inserint en. També cal perdre de vista on el node anterior que vostè està buscant en També hi era. Tothom bé amb això? D'ACORD. 

Què hi ha de la inserció al final? Si jo volia afegir que aquí-- si volia afegir un nou node a la final d'una llista, Com podria jo anar fent això? AUDIÈNCIA: Llavors, en l'actualitat, la assenyalar l'última a nul. ANDI Peng: Sí. Exactament, així que aquest Actualment es va assenyalar a conèixer, i així que suposo que, en aquest sentit, és molt fàcil afegir al final d'una llista. Tot el que has de fer és establir que igual a null i després auge. Allà mateix, molt fàcil. Molt senzill. 

Molt similar a la cap, però lògicament que voldrà assegurar-se que els passos prendre cap fer res d'això, estàs seguint. És molt fàcil, al mig del seu codi, posar-se al dia, oh, tinc tants punters. Jo no sé d'on res està assenyalant. Ni tan sols sé què node estic. Què està passant? 

Relaxeu-vos, calmar-se, prendre una respiració profunda. Dibuixa la teva llista enllaçada. Si dius, sé on exactament Necessito inserir això en i sé exactament com reassignar meu punters, molt, molt més fàcil d'imaginar fora-- molt, molt més fàcil no perdre en els errors del seu codi. Tothom d'acord amb això? D'ACORD. 

Així que suposo que un concepte que no tenim realment parlat fins ara, i jo el crec, probablement no es trobarà molt yet-- és una espècie de concept-- avançada és que en realitat tenim una dada estructura anomenada una llista doblement enllaçada. Així com vostès poden veure, tot el que estem fent és crear un valor real, un extra capdavanter en cadascun dels nostres nodes que també apunta al node anterior. Així que no només tenim la nostra nodes apunten a la següent. També apunten a l'anterior. Vaig a ignorar aquests dos ara. 

Llavors vostè té una cadena que es pot moure en tots dos sentits, i llavors és una mica més fàcil seguir lògicament junt. Igual que aquí, en lloc de no perdre de vista, oh, ha de saber que aquest node és el que he de tornar a assignar, Jo només puc anar aquí i simplement tiri de l'anterior. Llavors sé exactament on és a dir, i llavors no han de travessar la totalitat de la llista enllaçada. És una mica més fàcil. 

Però com a tal, té una doble la quantitat de punters, això és el doble de la quantitat de memòria. És un munt de consells per a no perdre de vista. És una mica més complex, però és una mica més fàcil d'usar funció en el que estem tractant d'aconseguir. 

Així que aquest tipus de dades estructura totalment existeix, i l'estructura de és molt, molt simple, excepte tot el que està tenint és a dir, en lloc de només un punter al següent, vostè també té un punter a l'anterior. Aquesta és tota la diferència va ser. Tothom bé amb això? Fresc. 

Molt bé, així que ara estic passar molt probablement com 15 a 20 minuts o el major de la resta del temps en la secció parlant sobre taules hash. Quants de vostès han llegit spec pset5? Molt bé, molt bé. Això és més alt que el 50% dels normalment. Està bé. 

Així com vostès veuran, ets desafiament en pset5 serà la d'aplicar un diccionari on es carrega més de 140.000 paraules que li donem i corrector ortogràfic contra tot el text. Li donarem a l'atzar peces de la literatura. Li donarem l'Odissea. Li donarem la Ilíada. Li donarem Austin Powers. 

I el seu repte serà de lletrejar verificació cada paraula en tot d'aquests diccionaris essencialment amb el nostre corrector ortogràfic. I així hi ha algunes parts de la creació d'aquest conjunt de processadors, primer que vols ser capaç de carregar realitat totes les paraules en el seu diccionari, i després vull ser capaç de revisar l'ortografia de tots ells. I així, com a tal, vostè va a requerir una estructura de dades que pot fer això ràpid i eficientment i de forma dinàmica. 

Així que suposo que el més fàcil manera de fer això, probablement crear una matriu, no? La forma més senzilla d'emmagatzematge que és pot crear una matriu de 140.000 paraules i acaba de col·locar a tots allí i després travessar els binari de cerca o seleccions o no-- sento que això classificació. Pot ordenar-los i després recórrer els per recerca binària o de cerca simplement lineal i just finals de les paraules, però que té una enorme quantitat de memòria, i no és molt eficient. 

Així que anem a començar parlant de formes de fer nostre temps de funcionament més eficient. I el nostre objectiu és aconseguir constant de temps on és gairebé com arrays, on vostè té accés instantani. Si volia buscar alguna cosa, Vull ser capaç de simplement, auge, saber exactament, i tiri d'ella. I així una estructura en la qual estarem tornant molt a prop per poder accedir a la constant temps, aquest sant grial en la programació de la constant temps es diu una taula hash. I així David va esmentar anteriorment la [Inaudible] una mica en la conferència, però anem a realment busseig en profunditat aquesta setmana en una peça que està en relació amb com una taula hash funciona. 

Així que la forma en què un hash obres de taula, per exemple, si volia guardar un munt de paraules, un manat de paraules en l'idioma anglès, Jo teòricament podria posar plàtan, poma, kiwi, mango, parell, i meló tot en tot just una matriu. Tots ells podrien encaixar i ser trobar. Seria una mena de mal de buscar a través d'i l'accés, però la manera més fàcil de fer això és que podem crear en realitat una estructura cridada una taula hash on hash. Correm totes les nostres claus a través una funció hash, una equació, que tots ells es converteix en una espècie d'un valor que podem emmagatzemar en essencialment un conjunt de llista enllaçada. 

I aquí, si volíem per emmagatzemar les paraules en anglès, podríem potencialment simplement, no fer saber, convertir totes les primeres lletres en una mena d'un nombre. I així, per exemple, si volia Un ésser sinònim de Apple-- o amb l'índex de 0, i B a ser sinònim d'1, podem tenir 26 entrades que només pot emmagatzemar totes les lletres del alfabet que començarem amb. I després podem tenir poma en l'índex de 0. Podem tenir plàtan en l'índex de 1, el meló en l'índex de 2, i així successivament i així successivament. I així si volia buscar la meva hash de taula i l'accés de la poma, Sigues poma comença amb una A, i sé exactament que ha de ser i el hash taula en l'índex 0, perquè de la funció assignada prèviament. 

Així que no sé, som un programa d'usuari, on se l'acusa de no arbitrarily-- arbitràriament, amb intentar pensatiu pensar en bones equacions ser capaç de propagar- a terme tots els seus valors de manera que puguin accedir fàcilment més endavant amb com una equació que vostè, vostè mateix, saben. Així, en el sentit que si volia anar a mànec, ho sé, oh, comença amb m. Ha de ser en l'índex de 12. Jo no he de buscar a través de qualsevol cosa. Sigues exactly-- tan sols pogués anar a l'índex de 12 i tiri d'això. 

Tothom clara sobre com 1 La funció de taula hash funciona? És una espècie de només un conjunt més complex. Això és tot el que és. D'ACORD. 

Així que suposo que ens trobem aquest tema del que que passa si té diverses coses que li donen el mateix índex? Així que dir que la nostra funció, tot el que va fer va ser prendre aquesta primera carta i convertir això en un 0 respectiva a través de 25 d'índex. Això és totalment bé si és suficient amb un de cada un. Però el segon de començar tenir més, ets va a tenir el que s'anomena una col·lisió. 

Així que si intento inserir enterrar en un hash taula que ja té el plàtan en ell, el que passarà quan intenta inserir això? Les coses dolentes perquè el plàtan que ja existeix en l'índex que desitja emmagatzemar-lo en. Berry tipus de és com, ah, què faig? No sé a on anar. Com puc solucionar això? 

I així vostès faran classe de veiem que fem aquesta cosa difícil on podem tipus de realitat crear llista enllaçada a les nostres matrius. I així, la manera més fàcil per pensar en això, totes taula hash és una varietat de llistes enllaçades. I així, en aquest sentit, cal aquest bell arranjament d'apuntadors, i després cada punter en aquest valor, en aquest índex, en realitat pot apuntar a altres coses. I pel que té tots aquests separada cadenes que surten d'una gran varietat. 

I aquí, si jo volgut inserir baia, Ja ho sé, OK, vaig a l'entrada a través de la meva funció hash. Vaig a acabar amb l'índex de 1, i després em vaig a ser capaç de tenir només un subconjunt més petit d'aquest gegant diccionari de 140.000 paraules. I llavors puc simplement mirar a través de 1/26 d'això. 

I així llavors puc només cal inserir baia ja sigui abans o després de plàtan en aquest cas? Després, oi? I pel que anem a voler inserir aquest node després de plàtan, i així vas a inserir a la cua de la llista enllaçada. Vaig a tornar a aquesta diapositiva anterior, així que vostès poden veure com funció hash funciona. 

Així funció hash és aquesta equació que s'està executant la classe de la seva entrada a través d'aconseguir el Índex que desitja assignar la directa cap. I així, en aquest exemple, tot el que volíem de fer era prendre la primera lletra, convertir això en un índex, llavors nosaltres pot emmagatzemar que en la nostra funció hash. Tot el que estem fent aquí és que estem la conversió de la primera lletra. Així KeyKey [0] és només la primera lletra de qualsevol cadena que estem tenint, estem passant. Estem convertir això a superior, i estem restant per majúscules A, així que tot el que està fent ens està donant una sèrie en el qual podem hash dels nostres valors en. 

I després anem a tornar picada MIDA mòdul. Sigui molt, molt acurat perquè, en teoria, aquí seu valor de resum podria ser infinita. Només podria seguir i seguir i seguir. Podria ser alguna cosa realment, molt gran valor, sinó perquè la seva taula hash que vostè ha creat només compta amb 26 índexs, vostè vol assegurar-se que la seva modulusing perquè no run-- és el mateix cosa com la seva queue-- perquè no es quedi fora de la part inferior de la funció hash. 

Vostè vol embolicar volta de la mateixa manera a [inaudible] quan que tenia com un molt, gran carta, no vull que això n'hi ha prou amb executar fora de la final. El mateix aquí, vostè vol assegurar-se no s'executa fora de la final embolicant voltant de la part superior de la taula. Així que això és només una molt funció hash simple. Tot el que va fer va ser prendre la primera carta de qualsevol que sigui la nostra entrada era i convertir això en un índex que podríem posar a la nostra taula hash. 

Sí, i així com he dit abans, la forma en què resolem col·lisions en el nostre hash de taules estan tenint, el que anomenem, encadenament. Així que si vostè intenta inserir múltiples paraules que comencen amb la mateixa cosa, vostè va a tenir un valor de resum. Alvocats i poma, si tens executar a través de la nostra funció hash, es va a donar la mateix nombre, el nombre de 0. I així, la forma en què resoldre això és que podem realment bo de vincular- si a través de llistes enllaçades. 

I així, en aquest sentit, vostès poden veure tipus de com les estructures de dades que hem estat establint prèviament com una passa lligat llista tipus de poden unir-se en una de sola. I llavors vostè pot crear ara estructures de dades més eficients que pot manejar grans quantitats de dades, canviar la mida de forma dinàmica en funció de les seves necessitats. Tothom clar? Tothom la classe de clara en el que passa aquí? 

Si volia insert-- el que és un fruita que comença amb, no sé, B, amb excepció de la baia, plàtan. 

AUDIÈNCIA: Blackberry. 

ANDI Peng: Blackberry, blackberry. D'on ve la esbarzer anar aquí? Bé, en realitat no hem classificat això encara, però teòricament si volíem tenir aquest en ordre alfabètic, on la mora s'ha d'anar? 

AUDIÈNCIA: [inaudible] 

ANDI Peng: Exactament, després d'aquí, no? Però ja que és molt difícil reorder-- Suposo que depèn de vostès. Vostès poden totalment implementar el que vulguis. La forma més eficient de fer això potser seria per ordenar la teva vinculats una llista en ordre alfabètic, i així quan estàs inserint coses, desitja per assegurar-se inserir en ordre alfabètic perquè després, quan estigui tractant de buscar ells, vostè no ha de travessar tot. Vostè sap exactament on que és, i que és més fàcil. 

Però si que tipus de tenir coses barrejades a l'atzar, vostè encara va a tenir per travessar totes maneres. I així, si volia simplement inseriu blackberry aquí i volia buscar que, sé, oh, blackberry ha de començar amb l'índex d'1, així que saber instantàniament només la recerca en 1. I llavors puc classe de recórrer la llista enllaçada fins que arribi a la mora, i llavors-- ¿sí? 

AUDIÈNCIA: Si vostè està tractant de create-- Suposo que aquesta és una molt simple de hash funció. I si el que volíem fer múltiples capes de que igual que, OK, volem separar en com totes les lletres de l'alfabet i després una altra vegada a com un altre conjunt de les lletres de l'alfabet en què, estem posant com un hash taula dins d'una taula hash, o com una funció dins d'una funció? O és que-- 

ANDI Peng: Així que el seu picada function-- seva taula hash pot ser tan gran com vostè desitja. Així que en aquest sentit, vaig pensar va ser molt fàcil, molt simple per a mi basen només una espècie en lletres de la primera paraula. I així, només hi ha 26 opcions. Només puc obtenir 26 opcions de 0 a 25, ja que només pot començar de l'A a la Z. Però Si volies afegir, potser, una major complexitat o més ràpid el temps d'execució del seu taula hash, malgrat tot pot fer tot tipus de coses. Vostè pot fer el seu propi equació que li dóna més distribució en el seu paraules, llavors quan vostè busca, que serà més ràpid. 

És totalment de vostès com vol implementar això. Penseu en això com només cubs. Si jo volia tenir 26 cubs, vaig per ordenar les coses en aquests cubs. Però jo vaig a tenir un munt de coses a cada cub, així que si vostè vol que sigui més ràpid i més eficient, dóna'm cent cubs. 

Però llavors vostè ha de trobar una manera d'ordenar les coses pel que són en el cub adequat han d'estar en. Però després, quan en realitat que desitgi veure a la galleda, que és molt més ràpid perquè hi ha menys coses a cada cub. I així, sí, això és en realitat el truc per a vostès en pset5 és que podràs el repte de crear només tot el que és el més eficient funció que es pugui imaginar per a ser capaç d'emmagatzemar i comprovar aquests valors. 

Totalment d'vostès però vostè vol fer-ho, però això és un molt bon punt. Que el tipus de lògica que vull començar a pensar en és, també, per què no puc fer més cubs. I llavors he de buscar menys coses, i llavors potser tenir una funció de hash diferent. 

Sí, hi ha un munt de maneres de fer això pset, alguns són més ràpids que altres. Estic totalment d'anar a veure el va ser ràpid els nois de més ràpid voluntat ser capaç d'obtenir les seves funcions per treballar. OK, tots bé en taules d'encadenament i croquetes? En realitat és com un molt simple concepte, si es pensa en això. Tot el que és és el que separa les seves entrades són en cubs, classificar-los, i després buscar el llistes que no està associada amb. 

Fresc. Molt bé, ara tenim una espècie diferent d'estructura de dades que es diu un arbre. Seguim i parlar d'intents que són clarament diferents, però en la mateixa categoria. Essencialment, tot és un arbre en lloc d'organitzar les dades en la forma lineal que una taula hash que does-- sabem, té una part superior i una part inferior i quin tipus d'enllaç fora de it-- 1 arbre té un superior que es diu a l'arrel, i llavors té fulles al seu voltant. 

I així, tot el que tens aquí és només el node superior que apunta a altres nodes, que els punts a més nodes, i així successivament i així successivament. I pel que només té branques de divisió. És només una forma diferent d'organitzar dades, i perquè en diem un arbre, vostès sol-- és només modelada a buscar un arbre. És per això que en diem arbres. 

Taula hash s'assembla a una taula. Un arbre només s'assembla a un arbre. Tot el que és és una separada forma d'organitzar els nodes depenent de quines són les seves necessitats. 

Així que hi ha una arrel i llavors vostè té fulles. La forma en què podem particular pensar-hi és un arbre binari, un arbre binari és només una tipus específic d'un arbre on cada node únics punts que, en el màxim, dos nodes. I així que aquí teniu diferent simetria en el seu arbre que fa que sigui més fàcil de tipus de mirada en quins valors són perquè llavors tenir sempre a l'esquerra o la dreta. Mai hi ha com una tercera esquerra des l'esquerra o quart des de l'esquerra. És només vostè té una esquerra i una dreta i vostè pot buscar qualsevol dels dos. I per què és això útil? La forma en que això és útil és que si estàs buscant per buscar a través de valors, no? En lloc d'implementar binari buscar en una matriu d'error, si vostè vol ser capaç d'inserir nodes i treure-li nodes a voluntat i també preservar la recerca capacitats de cerca binària. Així d'aquesta manera, estem tipus de tricking-- recordar quan ens dit llistes enllaçades no pot binari de cerca? Estem espècie de la creació d'una estructura de dades que trucs que a treballar. 

I les llistes perquè vinculats són lineals, que només enllacen un després de l'altre. Podem tipus de tenir diferent tipus de punters que apunten a diferents nodes que ens pot ajudar amb la cerca. I aquí, si volia tenir un arbre de cerca binària, Jo sé que el meu mitjà si 55. Jo només vaig a crear aquest com el meu mitjà, com el meu arrel, i després em vaig a tenir valors giren fora d'ella. 

Així que aquí, si jo vaig a buscar el valor de 66, puc començar als 55. És 66 més gran que 55? Sí que ho és, així que sé que busco mus i n el punter dret d'aquest arbre. Vaig al 77. OK, és 66 menor o major que 77? És menor que, pel que sé, oh, que ha de ser el node de l'esquerra. 

Així que aquí estem tipus de preservació totes les grans coses sobre matrius, així com el canvi de mida dinàmic d'objectes, sent capaç d'inserir i eliminar a voluntat, sense haver de preocupar-se pel fix quantitat d'espai. Encara conservem tots aquestes coses meravelloses al mateix temps ser capaç de preservar la registrar i buscar el temps de recerca binària que només estàvem prèviament capaç d'obtenir una frase. 

Estructura de dades fresca, tipus de complex d'implementar, el node. Com es pot veure, tot el que és l'estructura del node és que vostè té a l'esquerra i un punter dret. Això és tot el que és. Així que en lloc de només que té una x o una anterior. Vostè té una esquerra o una dreta i després pots tipus d'enllaçar- No obstant això així ho desitja. 

OK, estem en realitat va simplement prendre uns minuts. Així que anem a tornar aquí. Com he dit anteriorment, Jo com que vaig explicar la lògica darrere de la forma en què seria buscar a través d'això. Anem a tractar pseudocoding això a veure si podem aplicar el tipus de mateixa lògica de cerca binària a un tipus diferent d'estructura de dades. Si vostès volen prendre com una parella minuts per només pensar en això. D'ACORD. Molt bé, vaig a en realitat només li donen ell-- no, parlarem sobre el pseudocodi primer. Així que no vol que ningú per donar una punyalada en el el primer que vol fer quan vostè està començant la recerca és? Si estem buscant el valor de 66, el que és el primer que volem fer en cas de volem binari buscar aquest arbre? 

AUDIÈNCIA: Vols veure a la dreta i buscar esquerra i veure [inaudible] major nombre. 

ANDI Peng: Sí, exactament. Així que anem a mirar a la seva arrel. Hi ha un munt de maneres que vostè pot trucar que, diuen a la seva gent node pare. M'agrada dir que l'arrel perquè això és com l'arrel de l'arbre. Vostè va a mirar el node arrel, i ja està veurem és 66 més que o menor que 55. I si és més gran que, a més, és més gran que, cap a on volem veure? On volem buscar, no? Volem buscar la meitat dreta d'aquest arbre. 

Així tenim que, convenientment, 1 punter que apunta a la dreta. I així llavors podem establir la nostra nova arrel per ser 77. Només podem anar on vulgui el punter està apuntant. Bé, oh, aquí estem començant als 77, i podem simplement fer això de forma recursiva i una altra. D'aquesta manera, vostè classe tenir una funció. Vostè té una manera de buscar que simplement pot repetir una i altra vegada i una altra, depenent d'on vols buscar fins que finalment arribi al valor que vostè està buscant. Té sentit? 

Estic a punt de mostrar que l'actual codi, i és una gran quantitat de codi. No hi ha necessitat de s'espanti. Parlarem a través d'ell. 

En realitat, no. Això va ser només pseudocodi. OK, això va ser només el pseudocodi, que és una mica complex, però és totalment bé. Tothom seguint al llarg d'aquí? Si l'arrel és nul, el retorn fals, perquè això significa que ni tan sols té res allà. 

Si l'arrel n és el valor, pel que si passa a ser el que vostè està mirant, llavors vostè va a tornar true perquè saps que ho has vist. Però si el valor és menor arran de n, ets anar a buscar a l'esquerra nen o el full esquerra, el que vulguis dir. I si el valor és més gran que l'arrel, vostè va a buscar l'arbre adequat, després simplement executar la funció a través de la recerca de nou. 

I si l'arrel és nul, que aquesta vol dir que ha arribat al final? Això vol dir que no té més més fulles per buscar, llavors vostè sap, oh, suposo que no hi ha aquí perquè després he mirat a través tot l'assumpte i no és aquí, que només podria no ser aquí. 

¿Això té sentit per a tothom? Així és com la recerca binària preservar les capacitats de llistes enllaçades. Fresc, de manera que el segon tipus de l'estructura de dades que vostès pot provar l'aplicació en el seu conjunt de processadors, només has de triar un mètode. Però potser un mètode alternatiu per la taula hash és el que anomenem un trie. 

Tot un trie és un tipus específic d'arbre que té valors que van a altres valors. Així que en lloc de tenir un binari arbre en el sentit que només un El pot apuntar a dos, vostè pot tenir punt d'una cosa a moltes, moltes coses. Vostè essencialment té arrays dins dels quals s'emmagatzemen punters que apunten a altres matrius. 

Així que el node de la forma en què definiria 1 trie és que volem tenir un Boole, c paraula, oi? Així que el node és de Boole com a veritable o falsa, en primer lloc al capdavant de aquesta matriu, es tracta d'una paraula? En segon lloc, vostè vol tenir punters al que la resta d'ells ho són. Una mica complex, una mica abstracte, però Vaig a explicar el que tots els mitjans. 

Així que aquí, a la part superior, si té un arsenal ja va declarar, un node on es té una de Boole valor emmagatzemat a la part davantera que li diu que és aquesta una paraula? ¿No és això una paraula? I llavors vostè té la resta de la seva matriu que realment emmagatzema tota la possibilitats del que podria ser. Així, per exemple, com a la part superior que té el primer que diu veritat o fals, sí o no, es tracta d'una paraula. 

I llavors vostè té de 0 a 26 de les lletres que es poden emmagatzemar. Si volgués buscar aquí de pal, me'n vaig a la part superior i busco B. Trobada B en el meu matriu, i pel que sé, està bé, és B una paraula? B no és una paraula, per tant, He de seguir buscant. Vaig de B, i miro a la punter que apunta cap a B i veig una altra gamma d'informació, la mateixa estructura que teníem abans. 

I aquí-- oh, la propera carta a la [inaudible] és A. Així que mirem en aquesta matriu. Ens trobem amb el vuitè valor, i després mirem a veure, oh, bo, és que una paraula, és B-A una paraula? No és una paraula. Hem de seguir buscant. 

I així llavors mirem cap a on el punter d'un punts, i apunta a una altra forma en que tenim més valor emmagatzemat. I, finalment, arribem a B-A-T, que és una paraula. I així, la propera vegada es mira, vas per tenir el registre d'entrada de, sí, aquesta funció booleana és veritable. I així, en el sentit que estem tipus d'haver un arbre amb matrius. 

Així que vostè pot classe de recerca sota. En lloc d'una funció de hash i l'assignació de valors de llista enllaçada, que només pot posar en pràctica un trie que busca downwords. Molt, molt complicat les coses. No és fàcil de pensar, perquè jo sóc com escopir tantes estructures de dades fora a tu, però ho fa a tots tipus de entendre com funciona la lògica d'això? 

D'acord, guai. Així B-A-T, i després vostè va a buscar. La propera vegada que et vas per veure, oh, bé, això és cert, per tant sé que això ha de ser una paraula. 

El mateix per al zoològic. Així que aquí està la cosa ara mateix, si volgut buscar zoològic, en aquest moment, Actualment zoològic no és un paraula en el diccionari perquè, com vostès poden veure, el primer lloc que tenim un booleà return true és al final del zoom. Tenim Z-O-O-M. 

I aquí, no en realitat tenim la paraula, el zoològic, al diccionari perquè aquesta casella no està marcada. Així que l'equip no saber que el zoològic és una paraula perquè la forma en què hem emmagatzemada, només un zoom aquí en realitat té un valor booleà això s'ha convertit cert. Així que si volem inserir el paraula, parc zoològic, en el nostre diccionari, ¿Com podríem anar fent això? Què hem de fer per assegurar-nos que el nostre ordinador sap que Z-O-O és una paraula i no és la primera paraula és Z-O-O-M? 

AUDIÈNCIA: [inaudible] 

ANDI Peng: Exactament, ens voldrà assegurar-se que aquest aquí, que el valor booleà és comprovar a part que és veritat. Z-O-O, a continuació, anem a comprovar que, així que sabem exactament, hey, el zoològic és una paraula. Vaig a dir-li al equip que és una paraula tan que quan els controls informàtics, se sap que el zoològic és una paraula. 

A causa de recordar totes aquestes dades estructures, és molt fàcil per a nosaltres dir, oh, bat d'una paraula. Zoo és una paraula. Ampliar una paraula. Però quan vostè està construint ell, l'equip té ni idea. 

Així que has de dir-li exactament ¿En quin punt es tracta d'una paraula? En quin punt no és que una paraula? I ¿en quin moment fer jo de buscar coses, i en quin moment què he d'anar ara? Tothom clara d'això? Fresc. 

I llavors ve la problema de com ho faríem anar sobre la inserció d'alguna cosa que en realitat no hi és? Així que diguem que volem inserir la paraula, bany, en la nostra trie. Com vostès poden veure com actualment tot el que tenim ara és B-A-T, i aquesta nova estructura de dades Tenia una pinta que assenyalat nul·la perquè suposem que, oh, no hi ha paraules després de B-A-T, Per què necessitem per mantenir tenir les coses després que T. 

Però el problema sorgeix si fem que vull tenir una paraula que ve després del T. Si vostè té bany, ets voldrà un dret H. I així el camí que farem això és crearem un node separat. No estem assignem qualsevol quantitat de la memòria d'aquesta nova matriu, i anem a assignar punters. 

Anem a assignar el H, En primer lloc, aquest nul·la, anem a desfer-se'n. Tindrem els baix del punt H. Si veiem una H, volem que anar a un altre lloc. 

Aquí, podem llavors marqui si. Si arribem a una H després de la T, oh, llavors sabem que es tracta d'una paraula. El booleana va tornar realitat. Tothom clara sobre com va succeir això? D'ACORD. 

Per tant, bàsicament, tots aquestes estructures de dades que hem repassat l'actualitat, tinc anat per sobre d'ells molt, molt ràpidament i no en molt detall, i això està bé. Una vegada que comenci a jugar amb ella, podràs no perdre de vista on tots els punters són, el que està passant al seu estructures de dades, etcètera. Seran molt útil, i li toca a vostè nois per esbrinar totalment com vol implementar coses. 

I així pset4, de 5-- oh, això és incorrecte. Pset5 és faltes d'ortografia. Com he dit abans, vostè va a, un cop una altra vegada, descarrega el codi font de nosaltres. No hi haurà tres principals Coses que es descarreguen. Esteu descarregar els diccionaris, kers i textos. 

Totes aquestes coses són són ja sigui diccionaris de paraules que volem que vostè comprovi o la prova de la informació que volem que el corrector ortogràfic. I així els diccionaris donem vas per donar-li paraules reals que volem que li permet emmagatzemar d'alguna manera en una forma que és més eficient que una matriu. I a continuació, els textos són va ser el que som demanant-li que corrector ortogràfic per assegurar totes les paraules són paraules reals allà. 

I així els tres blocs de programes que li donarem es diuen dictionary.c, dictionary.h, i speller.c. I després tot es fa dictionary.c el que se li demana que implementar. Càrrega paraules. S'expliquen els controls, i s'assegura que tot el que s'ha inserit correctament. 

diction.h és només un arxiu de biblioteca que declara totes aquestes funcions. I speller.c, anem a donar-li. No cal modificar res d'això. Tot speller.c no és prendre que, el carrega, comprova la velocitat de la mateixa, posa a prova el punt de referència de com la forma ràpidament que ets capaç de fer les coses. 

És un corrector ortogràfic. Simplement no vulguis saber res d'ella, però que Assegureu-vos d'entendre el que està fent. Nosaltres fem servir una funció anomenada getrusage que posa a prova el rendiment del seu encanteri corrector. Tot el que fa és bàsicament provar la temps de tot en el seu diccionari, així que assegura't que ho entens. Aneu amb compte de no ficar-se amb ella o les altres coses no funcionaran correctament. 

I la major part d'aquest desafiament és per nois Per modificar realment dictionary.c. Anem a donar-li 140.000 paraules en un diccionari. Anem a donar-li un text arxiu que té aquestes paraules, i volem que vostè sigui capaç d'organitzar en una taula de hash o trie perquè quan li demanem que lletrejar check-- imaginar si ets encanteri comprovar com l'Odissea d'Homer. És com aquest gran, gran prova ,. 

Imagineu si tots i cada un paraula que calia mirar a través d'una matriu de 140.000 valors. Això portaria per sempre per a la seva màquina per córrer. Per això volem organitzar la nostra dades en estructures de dades més eficients com una taula hash o trie. I llavors vostès poden classe de quan es busca l'accés les coses més fàcilment i amb més rapidesa. 

I així que vés amb compte per resoldre les col·lisions. Vas a tenir un munt de paraules d'aquest començament amb A. Vas a aconseguir un grapat paraules de començar amb B. Fins que nois com vols resoldre-ho. Potser hi ha més funció hash eficient que només la primera lletra alguna cosa, i pel que toca a vostè nois per fer la classe del que vulguis. 

Potser vulgueu afegir totes les lletres juntes. Potser vostè vol agradaria fer coses estranyes per tenir en compte el nombre de lletres, el que sigui. Fins que vostès el que vols fer. Si vols fer una taula hash, si vostè Intenta-ho d'un trie, totalment de vostè. Vaig a advertir davant de temps que el trie és típicament una mica més difícil només perquè hi ha molt més punters a no perdre de vista. Però totalment de vostès. És molt més eficient en la majoria dels casos. Vols ser realment capaç de mantenir un registre de tots els seus punters. Com fer la mateixa cosa que estava fent aquí. Quan vostè està tractant d'inserir valors en una taula hash o eliminar, assegureu-vos que vostè és realment fer el seguiment d'on tot és degut és molt fàcil perquè si jo sóc intentar inserir com la paraula, andy. Diguem que és una paraula real, la paraula, andy, en una llista gegant d'una paraules. 

Si el que passa és reassignar un mal indicador, oops, aquí va la totalitat de la resta de la cistella enllaçada. Ara, l'única paraula que tenir és andy, i ara totes les altres paraules diccionari s'han perdut. I pel que desitja assegurar-se que portar un registre de tots els seus punters o en cas contrari va a aconseguir enormes problemes en el seu codi. Dibuixa les coses amb cura, pas a pas. Això fa que sigui molt més fàcil d'imaginar. 

I, finalment, que desitja ser capaç de provar el rendiment del seu programa en el gran tauler. Si vostès prenen un mira CS50 en aquest moment, tenim el que es diu el gran tauler. És el full de puntuació dels més ràpids lletrejar temps de xecs a través de totes CS50 en aquest moment, crec que la part superior com 10 vegades penso que vuit d'ells són personal. Realment volem que vostès ens van guanyar. 

Tots nosaltres estàvem tractant de posar en pràctica el codi ràpid com sigui possible. Volem que vostès tracten de desafiar ens i implementar més ràpid que tots nosaltres pot. I pel que aquest és realment la primera vegada que estem demanant a vostès per fer un conjunt de processadors que vostè pot fer realitat en qualsevol mètode Vols. 

Jo sempre dic, això és més afí a una solució de la vida real, oi? Jo dic, hey, necessito que facis això. Construir un programa que fa això per mi. Fes-ho com vulguis. Només sé que vull dejunar. Aquest és el seu repte per a aquesta setmana. Vostès, que va per donar-li una tasca. Anem a donar-li un desafiament. I després li toca a vostès completament sol esbrinar ¿Quina és la més ràpida i més forma eficient per implementar això. Sí? 

AUDIÈNCIA: Estem autoritzats a si Volíem investigar maneres més ràpides fer taules hash en línia, podem fer això i citar el codi d'una altra persona? ANDI Peng: Sí, totalment bé. Així que si vostès llegeixen el especificacions, hi ha una línia en l'especificació que diu que vostès són totalment lliures a la investigació de hash funcions en el que són alguns de les funcions de hash més ràpids per executar les coses com sempre que se citi aquest codi. Així que algunes persones ja tenen descobert maneres ràpides de fer els correctors ortogràfics, de ràpid formes d'emmagatzemar informació. Totalment de vostès si vol prendre només això, oi? Assegureu-vos que està citant. El repte aquí realment que estem tractant de provar és assegurar-se que vostè sap la seva manera voltant de punters. Pel que vostè implementació la funció hash real i donar amb igual les matemàtiques per fer això, vostès poden investigar el que sigui mètodes en línia que vostès volen. Sí? 

AUDIÈNCIA: Podem citar només mitjançant l'ús de la [inaudible]? 

ANDI Peng: Sí. Vostè pot simplement, en el seu comentari, es pot citar com, oh, pres de bla, bla, Yada, funció hash. Algú té alguna pregunta? En realitat breezed a la secció d'avui. Vaig a ser aquí per respondre a les preguntes també. 

A més, com ja he dit, l'oficina hores d'aquesta nit i demà. L'especificació d'aquesta setmana és en realitat super fàcil i super curt de llegir. Jo suggeriria prendre una mirada, just llegir a través de la totalitat de la mateixa. 

I Zamyla realitat que camina a través de cadascuna de les funcions que necessita per implementar, i pel que és molt, molt clar com fer tot. Només per assegurar-se que està fer el seguiment dels punters. Es tracta d'un conjunt de processadors molt difícil. 

No és un repte perquè igual que, oh, els conceptes són molt més difícil, o vostè ha d'aprendre tant nova sintaxi de la manera que vostè va fer per última pset. Aquest conjunt de processadors és difícil perquè hi ha tants punters, i llavors és molt, molt fàcil d'una vegada vostè té un error en el seu codi que no pugui trobar on aquest error és. 

I tan completa i absoluta fe en tu nois siguin capaços de superar la nostra [inaudible] ortografia. En realitat no tinc cap mina escrita encara, però estic a punt d'escriure la meva. Així, mentre que vostè està escrivint el seu, estaré escrivint la meva. Vaig a tractar de fer mina més ràpid que el seu. Anem a veure qui té el més ràpid. 

I sí, vaig a veure tots vostès aquí dimarts. Vaig a córrer una espècie com un taller conjunt de processadors. Totes les seccions aquest setmana són tallers PSet, pel que vostès tenen moltes oportunitats a la recerca d'ajuda, les hores d'oficina com sempre, i realment espero amb interès llegir tot el codi als seus nois. Tinc proves aquí si nois volen venir aconseguir-los. Això és tot.