JASON Hirschhorn: Benvinguts a tots a la Secció Set. Estem en la setena setmana del curs. I aquest proper dijous és Halloween, així que estic vestit com una carbassa. Jo no podia ajupir-se i posar en les meves sabates, així que és per això que estic només l'ús de mitjons. Així mateix, no porto res a sota això, així que no puc llevar si és distreure a vostè. Em disculpo per endavant per això. No cal imaginar Què està passant. Jo porto calçotets. Així que està tot bé. 

Tinc una història més llarga de per què estic vestit com una carbassa, però jo vaig a guardar per més endavant en aquesta secció perquè jo vull començar. Tenim un munt de coses interessants per repassar aquesta setmana. La majoria d'ells es refereixen directament a aquest conjunt de problemes de la setmana, les faltes d'ortografia. Anem a anar sobre lligat llistes i taules hash per a tota la secció. Poso aquesta llista cada setmana, una llista de recursos per a vostè per ajudar amb el material d'aquest curs. Si en una pèrdua o si busca alguna obtenir més informació, fes un cop d'ull a un aquests recursos. 

Un cop més, és pset6 faltes d'ortografia, conjunt de processadors d'aquesta setmana. I també t'anima, i jo animar-vos, utilitzar algun altre recursos específicament per a aquest conjunt de processadors. En particular, els tres que he enumerat a la pantalla - gdb, que hem estat familiaritzats amb i estat utilitzant des de fa un temps, és serà de molta ajuda aquesta setmana. Així que vaig posar que fins aquí. Però cada vegada que es treballa amb C, sempre s'ha d'utilitzar gdb per depurar els programes. Aquesta setmana també valgrind. Algú sap el que valgrind fa? 

AUDIÈNCIA: Comprova si hi ha fuites de memòria? 

JASON Hirschhorn: Valgrind xecs per a les pèrdues de memòria. Així que si alguna cosa malloc en el seu programa, estàs demanant memòria. Al final del seu programa, vostè té per escriure lliure de tot el que has malloced per donar la memòria. Si no escrius lliure al final i el seu programa arriba a una conclusió, tot automàticament ser alliberat. I per als petits programes, que és No és gran cosa. Però si vostè està escrivint un rodatge més llarg programa que no es tanca, necessàriament, en un parell de minuts o un parell de segons, a continuació, pèrdues de memòria pot esdevenir un gran negoci. 

Així que per pset6, l'expectativa és que vostè tindrà pèrdues de memòria zero amb seu programa. Per comprovar si hi ha fuites de memòria, valgrind executar i et vaig a donar algunes bones sortida que li permet saber si o no tot era gratis. Practicarem amb ell més endavant avui, amb sort. 

Finalment, la comanda diff. Ha utilitzat alguna cosa similar a ella en pset5 amb l'eina cop d'ull. Li ha permès observar l'interior. També vas usar diff, també, per el problema estableix especificacions. Però en que permet comparar dos arxius. Es podria comparar l'arxiu de mapa de bits i info encapçalats d'una solució personal i la seva solució en pset5 si opta per utilitzar-lo. Dif li permetrà fer això, també. Pot comparar la resposta correcta per El problema d'aquesta setmana estableix en la seva resposta i veure si s'alineï o veure on són els errors. 

Així que aquests són tres bones eines que vostè ha d'utilitzar per a aquesta setmana, i Definitivament revisar el seu programa de amb aquestes tres eines abans de donar volta polz Un cop més, com ja he esmentat totes les setmanes, si té alguna reacció per a mi - tant positiva i constructiva - no dubti en dirigir-se a la pàgina web a la part inferior d'aquesta diapositiva i l'entrada allà. Realment estima qualsevol i tots els comentaris. I si em dones les coses específiques que Que puc fer per millorar o que sóc fent així que m'agradaria Continuo, em prenc molt a pit i realment s'esforcen per escoltar per a la seva regeneració. No puc prometre que faré tot, però, com portar una carbassa disfressa cada setmana. 

Així que anem a passar la major part de secció, com ja he dit, parlant de llistes enllaçades i taules hash, que serà directament aplicable a la problema establert aquesta setmana. Les llistes enllaçades repassarem relativament ràpidament, perquè hem passat una mica just de temps d'anar-hi a la secció. I així anem a arribar directament a la problemes de codificació per a llistes enllaçades. I després, al final anem a parlar de taules hash i com s'apliquen a aquest Problema de la setmana. 

Vostè ha vist aquest codi abans. Aquesta és una estructura, i que està definint alguna cosa nova anomenat node. I dins d'un node no és un enter aquí i allà és un punter a un altre node. Hem vist això abans. Això ha estat pujant de un parell de setmanes ara. Combina els punters, que hem estat treballar amb, i estructures, que permeten ens permet combinar dos diferents coses en un sol tipus de dades. 

Hi ha molt a fer a la pantalla. Però tot això ha de ser relativament familiaritzat amb vostè. A la primera línia, que declarar un nou node. I després, dins d'aquest nou node, em vaig posar el nombre sencer en aquest node a un. Veiem en la següent línia que estic fent un printf comandament, però he atenuats la comanda printf perquè la veritat part important és aquesta línia aquí - new_node.n. Què significa el punt? 

AUDIÈNCIA: Aneu al node i avaluar el valor de n per a això. 

JASON Hirschhorn: Això és exactament correcte. Dot significa accedir a la part n d'aquest nou node. Aquesta línia següent fa què? Michael. 

AUDIÈNCIA: Es crea un altre node que s'apunti al nou node. 

JASON Hirschhorn: Així que no fa crear un nou node. Es crea un què? 

AUDIÈNCIA: Un punter. 

JASON Hirschhorn: Un punter a un node, com dictamina aquest node * aquí. Per tant, crea un punter a un node. I què node es ho apunta a, Michael? 

AUDIÈNCIA: Nou node? 

JASON Hirschhorn: Nou node. I està apuntant allà perquè hem atès que la direcció del nou node. I ara en aquesta línia veiem dues maneres diferents de expressar la mateixa cosa. I jo volia assenyalar com aquests dues coses són el mateix. A la primera línia, eliminar la referència el punter. Així que anem al node. Això és el que significa aquest estel. Hem vist que abans amb els punters. Anar a aquest node. Això està en parèntesis. I a continuació, accedir a través de l'operador de punt l'element n d'aquest node. 

Així que això prendre la sintaxi vam veure aquí i ara usar-la amb un punter. Per descomptat, es posa una mica ocupat si vostè està escrivint aquests parèntesi - aquesta estrella i aquest punt. Es posa una mica ocupat. Així que tenim una mica de sucre sintàctica. I aquesta línia aquí - ptr_node-> n. Que fa exactament el mateix. Així que aquestes dues línies de codi són equivalent i ho farà exactament el mateix. 

Però jo volia assenyalar els abans d'anar més lluny perquè vostè entengui que realment aquesta cosa aquí és només el sucre sintàctica per a eliminació de referències el punter i després anar a la part n d'aquesta estructura. Una pregunta sobre aquesta diapositiva? D'acord. 

Així que anem a anar a través d'un parell de les operacions que es poden fer en llistes enllaçades. Una llista enllaçada, el record, és una sèrie de nodes que apunten l'un a l'altre. I en general, vam començar amb un punter anomenat el cap, generalment, que apunta el primer a la llista. Així que a la primera línia aquí, tenir primer l'original L. Així que aquesta cosa que es pugui imaginar - això text aquí es pot pensar en com només el punter hem emmagatzemat en algun lloc que els punts per al primer element. I en aquesta llista enllaçada tenim quatre nodes. Cada node és una caixa gran. La caixa més gran dins de la gran caixa és la part sencera. I després tenim una part punter. 

Aquestes caixes no estan dibuixats a escala a causa del gran que és un enter en bytes? Què tan gran ara? Quatre. I què tan gran és un punter? Quatre. Així que en realitat, si haguéssim de dibuixar això és a escala dues caixes seria la mateixa mida. En aquest cas, volem inserir alguna cosa a la llista enllaçada. Així que vostè pot veure aquí baix estem inserint 05:00 Travessem a través de la llista enllaçada, on trobarà 05:00 va, i després inserir-lo. 

Anem a trencar això i van una mica més lentament. Vaig a assenyalar a la junta. Així que tenim el nostre node cinc que hem creat en mallocs. Per què s'està rient de tot el món? És broma. D'acord. Així que hem malloced 05:00. Hem creat aquest node en un altre lloc. Nosaltres ho tenim llest per anar. Comencem a la part frontal de llistat amb dos. I volem inserir d'una manera ordenada. 

Així que si veiem a dos i volem posar en cinc, què fem quan veiem una mica menys que nosaltres? Què? Volem inserir cinc en aquest llista enllaçada, mantenint ordenat. Veiem el número dos. Llavors, què fem? Marcus? 

AUDIÈNCIA: Truqui al punter al següent node. 

JASON Hirschhorn: I per què ens anem a la següent? 

AUDIÈNCIA: Perquè és la següent node de la llista. I només se sap que una altra ubicació. 

JASON Hirschhorn: I cinc és més gran de dos, en particular. Perquè volem mantenir ordenada. Així 05:00 és més gran que dos. Així que passem a la següent. I ara arribem a quatre. I què passa quan arribem a quatre? 

El cinc és més gran que quatre. Així que seguim endavant. I ara estem a les sis. I què és el que veiem a les sis? Sí, Carles? 

AUDIÈNCIA: Six és més gran que cinc. 

JASON Hirschhorn: Six és major que cinc. Així que aquí és on volem per inserir 05:00. No obstant això, tingueu en compte que si ens només tenen un punter aquí - aquest és el nostre punter extra que és travessant per la llista. I estem apuntant a sis. Hem perdut la pista del ve abans de les sis. Així que si volem inserir alguna cosa en aquesta llista mantenir ordenada, que probablement necessitarà el nombre de punters? 

AUDIÈNCIA: Dos. 

JASON Hirschhorn: Dos. Un per realitzar un seguiment del corrent un i un per realitzar un seguiment de l'anterior. Aquesta és només una llista vinculada individualment. Només va en una direcció. Si tinguéssim una llista doblement enllaçada, on tot apuntava a la cosa després d'ella i la cosa abans que, a continuació, no tindríem necessitat de fer això. Però en aquest cas no volem perdre un seguiment del que hi va haver abans de nosaltres en cas de hem d'inserir 05:00 en algun lloc en el medi. Diguem que Inserim nou. Què passaria quan arribem a les vuit? 

AUDIÈNCIA: Vostè hauria de aconseguir que el punt nul. En lloc de tenir punt nul hauries per afegir un element i després tenir que apunti a nou. 

JASON Hirschhorn: Exactament. Així que tenim vuit. Arribem al final de la llista a causa de això apunta null. I ara, en lloc d'haver de apunti a nul tenim que apunti al nostre nou node. I posem el punter a nostre nou node a null. Algú té alguna pregunta sobre la inserció? Què passa si no es preocupen per mantenir la llista ordenada? 

AUDIÈNCIA: Estic it al principi o al final. 

JASON Hirschhorn: enganxeu en al principi o al final. Quin hem de fer? Bobby? Per què al final? 

AUDIÈNCIA: Com que el principi ja està ple. 

JASON Hirschhorn: OK. El començament ja està ple. Qui vol argumentar en contra de Bobby. Marcus. 

AUDIÈNCIA: Bé, vostè probablement voldrà enganxar-lo al principi perquè en cas contrari si vostè ho posa en final que hauria de recórrer tota la llista. 

JASON Hirschhorn: Exactament. Així que si estem pensant en el temps d'execució, la temps d'execució de la inserció a l'extrem seria n, la mida d'aquest. Quin és el temps d'execució d'O d'inserció pel principi? Constant de temps. Així que si vostè no es preocupen per mantenir cosa ordenada, molt millor que només inserir al principi d'aquesta llista. I això es pot fer en temps constant. 

D'acord. Operació següent es va trobar que altres - hem redactar l'cerca. Però anem a mirar a través de la llista enllaçada per algun objecte. Vostès han vist el codi de buscar abans en la conferència. Però quin tipus de només vam fer amb inserir, o almenys la inserció alguna cosa ordenada. Et veus a través, passant pel node node, fins que trobi el nombre que vostè està buscant. Què passa si vostè arriba a al final de la llista? Diguem que jo estic buscant a les nou i em arribar al final de la llista. Què fem? 

AUDIÈNCIA: Tornar fals? 

JASON Hirschhorn: Torna fals. No ens trobarà. Si arriba al final de la llista i que no va trobar el número al qual està buscant, no hi és. Una pregunta sobre trobar? Si es tractava d'una llista ordenada, el que faria ser diferent per a la nostra recerca? Sí 

AUDIÈNCIA: Es trobaria el primer valor és major que el vostè està buscant i a continuació, tornar false. 

JASON Hirschhorn: Exactament. Així que si es tracta d'una llista ordenada, si arribem a cosa que és més gran que el que estem buscant, nosaltres no necessitem seguir endavant fins al final de la llista. Podem en aquest punt return false perquè no trobarem. La pregunta és ara, hem parlat de mantenir llistes enllaçades ordenats, mantenint sense classificar. Això serà una cosa que et probablement va a haver de pensar en quan un problema de codificació establert cinc si triar una taula hash amb separada enfocament d'encadenament, que parlarem més tard. 

Però val la pena mantenir la llista ordenada i després ser capaç de tenir potser Recerques més ràpides? O és millor per inserir ràpidament alguna cosa en temps d'execució constant, però després tenir més temps buscant? Això és un compromís just aquí que arribar a decidir què és el més apropiat per al seu problema específic. I no és necessàriament una resposta tota la raó. Però sens dubte és una decisió que vostè obté de fer, i probablement bo per defensar que en, diguem, un comentari o dos per què que va triar una sobre l'altra. 

Finalment, l'eliminació. Hem vist esborrar. És similar a la cerca. Busquem l'element. Diguem que estem tractant d'eliminar 06:00. Així ens trobem amb sis aquí. El que hem de assegurar-nos que fer és que tot el que està apuntant a 06:00 - com veiem en el pas 2 aquí baix - el que sigui que apunta a sis necessitats a saltar 06:00 ara i canviar per qualsevol que sigui sis està apuntant. No volem deixar orfe vegada la resta de llistat per l'oblit per establir que punter anterior. I a continuació, de vegades, depenent en el programa, ells només eliminar aquest node complet. De vegades vostè voldrà tornar el valor que està en aquest node. Així com la supressió de les obres. Teniu alguna pregunta respecte eliminar? 

AUDIÈNCIA: Així que si vostè va a esborrar ell, seria simplement utilitzar gratis perquè presumiblement es malloced? 

JASON Hirschhorn: Per alliberar cosa que és exactament correcte i vostè malloced ella. Diguem que volíem tornar a aquest valor. Podríem tornar sis i després lliure aquest node i connexió de trucades en ell. O és probable que anomenaríem lliure primer i després tornar 6. 

D'acord. Així que anem a passar a la pràctica de codificació. Anem a codificar tres funcions. La primera es diu insert_node. Així que tens el codi que et vaig enviar, i si estàs veient això més endavant es pot accedir al codi en linked.c en el lloc web CS50. Però en linked.c, hi ha una mica de codi esquelet que ja està ha escrit per a vostè. I després hi ha un parell de funcions que necessita per escriure. 

En primer lloc anem a escriure insert_node. I què fa insert_node és a dir insereix un sencer. I vostè està donant el nombre enter en una llista enllaçada. I, en particular, cal per mantenir la llista ordenada des del més petit al més gran. A més, no vol inseriu els duplicats. Finalment, com es pot veure insert_node retorna un bool. Així que se suposa que has de saber l'usuari si o no l'insert era èxit retornant vertader o fals. Al final d'aquest programa - i per aquesta etapa no cal de preocupar per l'alliberament de qualsevol cosa. Així que tot el que estem fent és prenent un sencer i inserint-lo en una llista. 

Això és el que t'estic demanant que facis ara. Un cop més, al linked.c, que tots tenen, és el codi d'esquelet. I cal veure cap al fons la declaració de la funció de la mostra. Abans, però, d'entrar a la codificació que en C, jo us animo a anar a través dels passos que hem estat la pràctica de cada setmana. Nosaltres ja hem passat per una foto d'això. Així que vostè ha de tenir algun coneixement de com funciona això. Però m'animo a escriure alguns pseudocodi abans de submergir polz I anem a repassar pseudocodi com un grup. I una vegada que has escrit el teu pseudocodi, i un cop hem escrit la nostra pseudocodi com a grup, pot entrar a la codificació en C. 

Com un mà a mà, la funció insert_node és probablement el més difícil de els tres que anem a escriure perquè afegit algunes limitacions al la seva programació, en particular, que no vas a inserir qualsevol duplicats i que la llista ha de romandre ordenat. Així que aquest és un programa no trivial que vostè necessita per codificar. I per què no et portes 06:55 minuts, per simplement treballar en el pseudocodi i el codi. I després anem a començar anar com un grup. Un cop més, si vostè té alguna pregunta només aixecar la mà i vaig a entrar en raó. . 

Nosaltres també, en general fem aquests - o jo no et dic explícitament pot treballar amb la gent. Però, òbviament, jo us animo, si té preguntes, demanar al veí assegut al teu costat o fins i tot treballar amb algú més si vols. Aquest no ha de ser un individu activitat silenciosa. 

Anem a començar amb l'escriptura d'alguns pseudocodi al tauler. Qui em pot donar la primera línia de pseudocodi per a aquest programa? Per a aquesta funció, en lloc - insert_node. Alden? 

AUDIÈNCIA: Així que el primer que vaig fer va ser crear un nou punter al node i jo inicialitza el que apunta a la mateixa cosa que la llista està assenyalant. 

JASON Hirschhorn: OK. Així que crearà un nou punter a la llista, no per al node. 

AUDIÈNCIA: així. Sí 

JASON Hirschhorn: OK. I llavors, què és el que volem fer? Què hi ha després d'això? Què passa amb el node? No tenim un node. Només tenim un valor. Si volem inserir un node, el que fa que necessita fer primer abans de poder tan sols pensar inserir? 

AUDIÈNCIA: Oh, ho sento. hem de malloc espai per a un node. 

JASON Hirschhorn: Excel · lent. Farem - D'acord. No es pot arribar tan alt. D'acord. Anem a anar cap avall, i després estem usant dues columnes. No puc anar a que - D'acord. Crear un nou node. Podeu crear un altre punter a la llista o simplement pot utilitzar la llista, tal com existeix. Segur que no necessita fer això. 

Així que vam crear un nou node. Gran. Això és el que fem en primer lloc. Què segueix? 

AUDIÈNCIA: Esperi. ¿Cal crear un nou node ara o hem d'esperar per assegurar-se que no hi ha duplicats del node en la llista abans que ens ho creguem? 

JASON Hirschhorn: Bona pregunta. Anem a sostenir que per més endavant perquè el major part del temps estarem creant un nou node. Així que seguirem això aquí. Però aquesta és una bona pregunta. Si creem i ens trobem un duplicat, el que ha que fem abans de tornar? 

AUDIÈNCIA: alliberar-lo. 

JASON Hirschhorn: Si. Probablement alliberar-lo. D'acord. Què fem després que crear un nou node? Annie? 

AUDIÈNCIA: Posem la nombre en el node? 

JASON Hirschhorn: Exactament. Posem el nombre - que malloc espai. Vaig a deixar que tot en una sola línia. Però tens raó. Ens malloc espai, i després posem el nombre polz Fins i tot podem establir el punter part d'ella en null. Això és exactament correcte. I llavors què passa després d'això? Dibuixem la imatge en el tauler. Llavors, què fem? 

AUDIÈNCIA: Anem a través de la llista. 

JASON Hirschhorn: Anar a través de la llista. D'acord. I què anem a comprovar en cada node. Kurt, què és el comprovar per a cada node? 

AUDIÈNCIA: Veure si el valor de n de aquest node és major que el valor de n del nostre node. 

JASON Hirschhorn: OK. Jo faré - Sí, està bé. Així que és n - Jo vaig a dir si el valor és més gran d'aquest node, llavors, què fem? 

AUDIÈNCIA: Bé, llavors ens inserim el correcte abans d'això. 

JASON Hirschhorn: OK. Així que si és més gran que aquest, llavors volem inserir. Però volem inserir just abans de perquè nosaltres també necessitem ser fer el seguiment i, a continuació, del que era abans. Així que inserir abans. Així que és probable que vam perdre alguna cosa anteriorment. Probablement necessitem estar mantenint un seguiment del que està passant. Però anem a arribar-hi. Llavors, quin valor és inferior? Kurt, què fem si valor és menor que? 

AUDIÈNCIA: A continuació, només seguir endavant llevat que sigui l'últim. 

JASON Hirschhorn: això m'agrada. Així que anar al següent node. Si no sou l'últim - és probable que estem comprovant que en els termes d'una condició. Però sí, el proper node. I això no baixi molt, així que anem a passar per aquí. Però si - Tots poden veure això? Si som iguals, què fem? Si el valor que estem tractant d'inserir és igual al valor d'aquest node? Sí? 

AUDIÈNCIA: [inaudible]. 

JASON Hirschhorn: Si. Donada aquesta - Marcus té raó. Podríem haver fet potser alguna cosa diferent. Però tenint en compte que hem creat, aquí hem alliberar i després tornar. Oh boy. Així està millor? Com és això? D'acord. Gratis i llavors, què fem nosaltres tornar, [inaudible]? D'acord. Ens estem perdent alguna cosa? Llavors, on fer el seguiment del node abans? 

AUDIÈNCIA: Crec que seria anar després de crear un nou node. 

JASON Hirschhorn: OK. Així que al principi probablement anem - sí, podem crear un punter a una nova node, com un punter de node anterior i un punter node actual. Així que anem a inserir això aquí. Crear actual i anterior punters als nodes. Però quan ens ajustem els punters? On ho fem en el codi? Jeff? 

AUDIÈNCIA: - condicions de valor? 

JASON Hirschhorn: Què un en particular? 

AUDIÈNCIA: Estic confós. Si el valor és superior a aquest node, ¿Això no significa que vostè vol anar al següent node? 

JASON Hirschhorn: Així que si el nostre valor és més gran que el valor d'aquest node. 

AUDIÈNCIA: Sí, llavors el que vol anar més avall de la línia, no? 

JASON Hirschhorn: així. Així que no inserim aquí. Si el valor és inferior a aquest node, a continuació, anem al següent node - o llavors inserir abans. 

AUDIÈNCIA: Espera, que és aquest node i que és el valor? 

JASON Hirschhorn: Bona pregunta. Valor per aquesta definició de funció és el que se'ns dóna. Així que el valor és el nombre que se'ns dóna. Així que si el valor és menor que aquest node, necessitem temps per inserir. Si el valor és superior a aquest node, anem al següent node. I tornant a la pregunta original, però, on - 

AUDIÈNCIA: Si el valor és més gran d'aquest node. 

JASON Hirschhorn: I així Què fem aquí? Sweet. Això és correcte. Jo només vaig a escriure punters d'actualització. Però això sí, amb l'actual vol actualitzar a apuntar a la següent. Qualsevol altra cosa que s'està perdent? Així que vaig a escriure això codi en gedit. I mentre faig això, vostè pot tenir una parell de minuts més per treballar en la codificació està en C. 

Així que he de ingressar el pseudocodi. Una nota ràpida abans de començar. Potser no siguem capaços de completament acabar això en tot tres d'aquestes funcions. Hi ha solucions correctes als que vaig a enviar per correu electrònic a vostès després de la secció, i ho farà es publicaran en CS50.net. Així que no us animo a anar a buscar a les seccions. T'animo a que intenti resoldre vostè posseir, i aleshores utilitzar el la pràctica problemes per comprovar les seves respostes. Totes elles han estat dissenyades per a prop relacionar-se i complir el que el que has de fer en el conjunt de problemes. Així que t'animo a practicar aquest pel seu compte i després utilitzar el codi per comprovi seves respostes. Perquè vull seguir endavant per discutir taules en algun punt de la secció. Així que podríem no aconseguir en tot moment. Però farem el més que puguem ara. 

D'acord. Comencem. Asam, com creem un nou node? 

AUDIÈNCIA: Vostè struct *. 

JASON Hirschhorn: Així que haver de fins aquí. Oh, ho sento. ¿Deies struct *. 

AUDIÈNCIA: I després [? tipus?] node o node c. 

JASON Hirschhorn: OK. Vaig a dir-new_node perquè puguem romandre constant. 

AUDIÈNCIA: I vostè desitja establir que al capdavant, el primer node. 

JASON Hirschhorn: OK. Així que ara aquesta apuntant a - pel que aquest no ha creat un nou node encara. Això és només apunta a la primer node a la llista. Com es crea un nou node? Si necessito espai per crear un nou node. Malloc. I què tan gran? 

AUDIÈNCIA: La mida de l'estructura. 

JASON Hirschhorn: El mida de l'estructura. I quina és l'estructura trucada? 

AUDIÈNCIA: Node? 

JASON Hirschhorn: Node. Així malloc (sizeof (node)); ens dóna l'espai. I és aquesta línia - una cosa és incorrecte en aquesta línia. És new_node un punter a una estructura? És un nom genèric. Què és - node, exactament. És un node *. I, què fem després que malloc alguna cosa, Asan? Què és el primer que farem? Què passa si no funciona? 

AUDIÈNCIA: Oh, comproveu si apunta al node? 

JASON Hirschhorn: Exactament. Així que si vostè new_node iguals iguals nul, què fem? Això retorna un bool, aquesta funció. Exactament. Es veu bé. Qualsevol cosa per afegir aquí? Anem a afegir coses al final. Però que fins al moment es veu bé. Crear indicadors actuals i anteriors. Michael, com puc fer això? 

AUDIÈNCIA: Vostè hauria fer un node *. Hauries de ho fa a un per new_node però per a la nodes que ja tenen. 

JASON Hirschhorn: OK. Així que el node actual estem en. Vaig a trucar a aquest curr. Està bé. Hem decidit que volem mantenir dos, perquè hem de saber el que hi ha abans d'ella. Què són inicialitzades a? 

AUDIÈNCIA: El seu valor a la nostra llista. 

JASON Hirschhorn: Llavors, quin és el El primer a la nostra llista? O, com sabem que el a partir de la nostra llista és? 

AUDIÈNCIA: No es va aprovar en la funció de? 

JASON Hirschhorn: així. Es va aprovar en aquí. Així que si es passa a la funció, la inici de la llista, què hem establir corrent igual a? 

AUDIÈNCIA: Llista. 

JASON Hirschhorn: Llista. Això és exactament correcte. Ara que té la direcció de el principi de la nostra llista. I què passa amb prèvia? 

AUDIÈNCIA: Llista menys un? 

JASON Hirschhorn: No res abans d'ella. Llavors, què podem fer per significar res? 

AUDIÈNCIA: Nul. 

JASON Hirschhorn: Si. Això sona com una bona idea. Perfect. Gràcies. Anar a través de la llista. Constantí, quant de temps anem de passar per la llista? 

AUDIÈNCIA: fins arribar a nul. 

JASON Hirschhorn: OK. Així que si, mentre que, per al bucle. Què estem fent? 

AUDIÈNCIA: Potser un bucle? 

JASON Hirschhorn: Anem a fer un bucle for. D'acord. 

AUDIÈNCIA: I diem per - fins que el punter actual no és igual a nul. 

JASON Hirschhorn: Així que si coneixem la condicions, com podem escriure un bucle amb seu fora aquesta condició. Quina classe d'un bucle hem d'utilitzar? 

AUDIÈNCIA: While. 

JASON Hirschhorn: Si. Això té més sentit amb base fora del que vas dir. Si només volem anar a que ho faria només sé que cosa, hauria sentit fer un bucle while. Mentre que el corrent no és igual a null, si el valor és inferior a aquest node. Akshar, dóna'm d'aquesta línia. 

AUDIÈNCIA: Si current-> n n menys del seu valor. O revertir això. Canvieu aquesta franja. 

JASON Hirschhorn: Ho sento. 

AUDIÈNCIA: Canvieu el suport. 

JASON Hirschhorn: Així que si és major que el valor. Perquè això és confús amb la comenti anteriorment, faré això. Però si. Si el nostre valor és menor que aquest node, què fem? Oh. Ho tinc aquí mateix. Insereix abans. D'acord. Com fem això? 

AUDIÈNCIA: Segueix sent el meu? 

JASON Hirschhorn: Si. 

AUDIÈNCIA: Vostè - new_node-> següent. 

JASON Hirschhorn: Llavors, què que serà igual? 

AUDIÈNCIA: Va a la mateixa corrent. 

JASON Hirschhorn: Exactament. I així, l'altre - el que més necessitem per actualitzar? 

AUDIÈNCIA: Comproveu si el passat és igual a nul. 

JASON Hirschhorn: Si prev - pel que si és igual prev nul. 

AUDIÈNCIA: Això vol dir que va per esdevenir el cap. 

JASON Hirschhorn: Això significa s'ha convertit en el cap. Llavors, què fem? 

AUDIÈNCIA: Fem el cap és igual new_node. 

JASON Hirschhorn: Head iguals new_node. I per què el cap aquí, no llista? 

AUDIÈNCIA: A causa de que el cap és un mundial variable, que és el punt de partida. 

JASON Hirschhorn: Sweet. D'acord. I - 

AUDIÈNCIA: Llavors, els altres prev-> següent és igual new_node. I després pot tornar realitat. 

JASON Hirschhorn: On ens vam posar fi new_node? 

AUDIÈNCIA: jo - Em vaig posar que al començament. 

JASON Hirschhorn: Llavors, quina línia? 

AUDIÈNCIA: Després de la sentència if comprovar si se sap. 

JASON Hirschhorn: Aquí mateix? 

AUDIÈNCIA: Faria new_node-> n mateix valor. 

JASON Hirschhorn: Sona bé. Probablement té sentit - no ho fem necessita saber el que la llista que estem en perquè només estem tractant amb una sola llista. Per tant una millor declaració de la funció de això és només per desfer-se d'aquest completament i només ha d'inserir un valor al cap. Ni tan sols necessitem saber el llista que estem ficats Però vaig a mantenir tot per ara i després canviar a l'actualització les diapositives i codi. Així que es veu bé, per ara. Si el valor - que pot fer aquesta línia? Si - Què fem aquí, Noah. 

AUDIÈNCIA: Si el valor és més gran de curr-> n - 

JASON Hirschhorn: Com anem al següent node? 

AUDIÈNCIA: Curr-> n és igual a new_node. 

JASON Hirschhorn: Llavors n és quina part de l'estructura? El nombre enter. I new_node és un punter a un node. Llavors, quina part de curr hem d'actualitzar? Si no és n, llavors quina és l'altra part? Noè, quina és l'altra part. 

AUDIÈNCIA: Oh, la propera. 

JASON Hirschhorn: A continuació, exactament. Exactament. Següent és la correcta. I el que més necessitem actualitzar, Noah? 

AUDIÈNCIA: Els punters. 

JASON Hirschhorn: Així actualitzem actual. 

AUDIÈNCIA: Anterior-> següent. 

JASON Hirschhorn: Si. Bé, anem a fer una pausa. Qui ens pot ajudar? Manu, què hem de fer? 

AUDIÈNCIA: Cal establir és igual a curr-> següent. Però fer això abans de la línia anterior. 

JASON Hirschhorn: OK. Alguna cosa més? Akshar. 

AUDIÈNCIA: Crec que no estàs la intenció de canviar curr-> següent. Crec que estàs destinat a fer iguals curr curr-> següent per anar al següent node. 

JASON Hirschhorn: Ho sento, on? En quina línia? Aquesta línia? 

AUDIÈNCIA: Si. Fer curr equival curr-> següent. 

JASON Hirschhorn: Així que això és correcte perquè el corrent és una punter a un node. I volem que apunti a la següent node del que està rebent en l'actualitat assenyalat. Curr en si té un següent. Però si haguéssim de actualitzar curr.next, ens seria l'actualització de la nota real en si, no on aquesta punter assenyalava. Què passa amb aquesta línia, però. Avi? 

AUDIÈNCIA: Anterior-> següent és igual curr. 

JASON Hirschhorn: Així que de nou, en cas anterior és un punter a un node, anterior-> següent és la punter actual al node. Així que aquesta seria l'actualització d'una punter en un node per curr. No volem posar al dia un punter a un node. Volem posar al dia anterior. Llavors, com fem això? 

AUDIÈNCIA: Només es preveu. 

JASON Hirschhorn: així. Anterior és un punter a un node. Ara anem a canviar a un nou punter a un node. Acceptar Belluguem-nos cap avall. Finalment, aquesta última condició. Jeff, què fem aquí? 

AUDIÈNCIA: Si el valor és igual a curr-> n. 

JASON Hirschhorn: Ho sento. Oh Déu meu. Què? Valor == curr-> n. Què fem? 

AUDIÈNCIA: Vostè seria alliberar als nostres new_node, i després et tornaries falsa. 

JASON Hirschhorn: Això és el que que hem escrit fins ara. Algú té alguna cosa afegir abans que fem? D'acord. Anem a intentar-ho. El control pot arribar a la final d'una funció no nul · la. Avi, què està passant? 

AUDIÈNCIA: Se suposa posar de retorn cert fora del bucle while? 

JASON Hirschhorn: No sé. Em vols? 

AUDIÈNCIA: No importa. No 

JASON Hirschhorn: Akshar? 

AUDIÈNCIA: Crec que la intenció de posar return false al final del bucle while. 

JASON Hirschhorn: Llavors, on Què vols que vagi? 

AUDIÈNCIA: Igual que fora del bucle while. Així que si surt del bucle while que els mitjans que ha arribat al final i no ha passat res. 

JASON Hirschhorn: OK. Així que, què fem aquí? 

AUDIÈNCIA: Vostè torna falsa allà també. 

JASON Hirschhorn: Oh, fer-ho en tots dos llocs? 

AUDIÈNCIA: Si. 

JASON Hirschhorn: OK. Cal anar? Oh Déu meu. Ho sento. Demano disculpes per la pantalla. És una mica flipant en nosaltres. Així que has de triar una opció. Zero, pel codi, es tanca el programa. Un insereix alguna cosa. Anem a inserir 03:00. El inserit no va tenir èxit. Vaig a imprimir. Jo no tinc res. D'acord. Potser això era només una casualitat. Inseriu un. No èxit. D'acord. Anem a executar a través de GDB molt ràpid per comprovar el que està passant. 

Recordi gdb. / El nom de la seva programa ens fica al BGF. És que una gran quantitat d'utilitzar? El intermitent? Probablement. Tanca els ulls i prendre una mica de profunditat respiracions si et canses de veure les coses. Sóc al BGF. Què és el primer que faig en GDB? Hem d'esbrinar Què està passant aquí. Anem a veure. Tenim sis minuts de la figura el que està passant. Trencar principal. I llavors, què faig? Carles? Executar. D'acord. Anem a escollir una opció. I què té N fer? Següent. Sí 

AUDIÈNCIA: No ho dius - què no em vas dir que el cap, que era inicialitza en null al principi. Però vaig pensar que havies dit que estava bé. 

JASON Hirschhorn: Anem - veurem en GDB, i després tornarem. Però sembla que vostè ja té algunes idees sobre el que està passant. Així que volem inserir alguna cosa. D'acord. Hem inserir. Posa un int. Nosaltres inserirem 3. I llavors estic en aquesta línia. Com puc iniciar la depuració la inserció de la funció coneguda? Oh Déu meu. Això és un munt. Això embogint molt? 

AUDIÈNCIA: Oh, va morir. 

JASON Hirschhorn: Acabo el va treure. D'acord. 

AUDIÈNCIA: Potser és el altre extrem del cable. 

JASON Hirschhorn: Wow. Així que la conclusió - Què li vas dir? 

AUDIÈNCIA: Vaig dir que la ironia de la tècnica dificultats en aquesta classe. 

JASON Hirschhorn: Ho sé. Si tan sols tingués el control sobre aquesta part. [Inaudible] Això sona molt bé. Per què no començar a pensar en els nois el que podríem haver fet malament, i estarem de tornada en 90 segons. 

AVICA, vaig a preguntar-li com anar insert_node interior per depurar. Així que aquí és on ens va deixar l'última vegada. Com em vaig endins insert_node, AVICA, examinar el que està passant? Què comandament GDB? Pausa no em portaria al seu interior. Ho sap Marquise? 

AUDIÈNCIA: Què? 

JASON Hirschhorn: Què comandament GDB Jo ús per anar dins d'aquesta funció? 

AUDIÈNCIA: Step? 

JASON Hirschhorn: Pas a través d' S. Això em porta dins. D'acord. New_node mallocing una mica d'espai. Tot això sembla que va. Anem a examinar new_node. Es va posar una mica de direcció de memòria. Anem a veure - això és tot el correcte. Així que tot el que aquí sembla estar funcionant correctament. 

AUDIÈNCIA: Quina és la diferència entre P i la pantalla? 

JASON Hirschhorn: P correspon a la impressió. I pel que s'està preguntant quina és la diferència entre això i això? En aquest cas, res. Però generalment hi algunes diferències. I vostè ha de buscar en el manual d'GDB. Però en aquest cas, res. Tenim la tendència a utilitzar la impressió, però, perquè nosaltres no hem de fer molt més que imprimir un sol valor. 

D'acord. Així que estem en la línia 80 del nostre codi, establint node * curr igual a llista. Anem a imprimim curr. És igual a la llista. Sweet. Esperi. És igual a alguna cosa. Això no em sembla correcte. Això és. És perquè en GDB, bé, si que és la línia que està en ell encara no s'ha executat. Així que cal escriure en realitat següent per executar la línia de abans de veure els resultats. Així que aquí estem. Simplement executa aquesta línia, anterior equival a nul · la. Així que de nou, si imprimim anterior no veurem res estrany. Però si realment executen a què línia, llavors veurem que aquesta línia va funcionar. 

Així que tenim curr. Aquests són els dos bons. Cert? Ara estem en aquesta línia aquí. Mentre curr no és igual a nul. Bé, el que fa curr iguals? Acabem de veure que va igualar nul. Imprimim a terme. Vaig a imprimir cap fos una altra vegada. Així és que mentre que bucle va a executar? 

AUDIÈNCIA: No 

JASON Hirschhorn: Així que quan he escrit que línia, veurà que va saltar tot el camí fins a la part inferior, tornarà false. I després anem a tornar false i tornar al nostre programa i finalment, imprimir, com hem vist, l'insert no va tenir èxit. Per tant, ningú té alguna idea sobre el que que hem de fer per arreglar això? Vaig a esperar fins que vegi un parell de mans pugen. No executem això. Tingueu en compte que aquesta va ser la primera El que estàvem fent. Jo no faré un parell. Vaig a fer alguns. Com que un parell significa dues. Vaig a esperar per més de dos. 

La primera inserció, corr, per defecte és igual a nul. I aquest cicle només s'executa si curr no és nul. Llavors, com puc solucionar això? Veig 3 mans. Vaig a esperar per més de tres. Marcus, què et sembla? 

AUDIÈNCIA: Bé, si vostè ho necessita executar més d'una vegada, només canviar-ho a un bucle do-while. 

JASON Hirschhorn: OK. Serà que resoldre el nostre problema, però? 

AUDIÈNCIA: En aquest cas no, perquè de el fet que la llista és buida. Així que és probable que només necessita afegir una declaració que si se surt del bucle llavors vostè ha d'estar al final de la la llista, moment en què vostè només pot inserir. 

JASON Hirschhorn: això m'agrada. Això té sentit. Si se surt del bucle - perquè va a tornar false aquí. Així que si se surt del bucle, llavors estem en Al final de la llista, o potser el inici d'una llista si no hi ha res a , El que és el mateix que el final. Així que ara volem inserir alguna cosa aquí. Llavors, com aquest codi mira, Marcus? 

AUDIÈNCIA: Si ja tens el node malloced, podeu dir new_node-> següent és igual a nul · la perquè ha de ser al final. O new_node-> següent és igual a nul. 

JASON Hirschhorn: OK. Ho sento. New_node-> següent és igual a nul perquè estem al final. Això no ho va posar polz Com ens posem a la llista? Dreta. Això és només la creació és igual a. No, com en realitat el va posar a la llista? El que apunta a la final de la llista? 

AUDIÈNCIA: Head. 

JASON Hirschhorn: Ho sents? 

AUDIÈNCIA: Head està apuntant al final de la llista. 

JASON Hirschhorn: Si no hi ha res a la llista, el cap està apuntant a la final de la llista. Així que això funcionarà per a la primera inserció. Què passa si hi ha un parell les coses a la llista? Que no volem establir cap igual a new_node. Què és el que volem fer allà? Sí? Probablement anterior. Funcionarà? Recordem que anterior és només un punter a un node. I anterior és una variable local. Així que aquesta línia crearà una variable local, anterior, igual o assenyalant a aquest nou node. Això no posarà realment es a la llista, però. Com ens posem en la nostra llista? Akchar? 

AUDIÈNCIA: Crec que fer actual-> següent. 

JASON Hirschhorn: OK. curr-> següent. Així que de nou, l'única raó per la qual estem sota aquí és el que fa de corrent igual? 

AUDIÈNCIA: igual a nul. 

JASON Hirschhorn: I així ho que passa si ho fem nul-> next? Què aconseguirà? Aconseguirem una fallada de segmentació. 

AUDIÈNCIA: Do curr equival a nul · la. 

JASON Hirschhorn: Això és el mateix com anterior, però, perquè no hi ha una variable local que estem establint igual a aquest nou node. Tornem a la nostra imatge d'inserir alguna cosa. Diguem que estem inserint al final de la llista, pel que aquí. Tenim un punter actual que és apuntant a null i un punt anterior això apunta a 8. Llavors, què hem de actualitzar, Avi? 

AUDIÈNCIA: Anterior-> següent? 

JASON Hirschhorn: Anterior-> següent és el que volem posar al dia causa que en realitat s'insereix en al final de la llista. Encara tenim una bestiola, però, que anem a executar en. Què és aquest bitxo? Sí? 

AUDIÈNCIA: Es va a tornar falsa en aquest cas? 

JASON Hirschhorn: Oh, és que tornarà false. Però hi ha un altre error. Així que haurem de posar a canvi veritable. 

AUDIÈNCIA: Això segueix igual nul en la part superior de la llista? 

JASON Hirschhorn: Encara Així anterior és igual a nul des del principi. Llavors, com podem superar això? Sí? 

AUDIÈNCIA: Crec que es pot fer una verificació abans que el bucle while per veure si és una llista buida. 

JASON Hirschhorn: OK. Així que anirem aquí. Feu una revisió. Si - 

AUDIÈNCIA: Així que si el cap és igual a és igual a nul. 

JASON Hirschhorn: Si el cap és igual a és igual a nul · - que ens dirà si es tracta d'una llista buida. 

AUDIÈNCIA: I llavors vostè fer el cap és igual a nou. 

JASON Hirschhorn: Head iguals new_node? I què més hem de fer? 

AUDIÈNCIA: I després pot tornar realitat. 

JASON Hirschhorn: No del tot. Ens cal un pas. 

AUDIÈNCIA: New_node següent ha d'apuntar a null. 

JASON Hirschhorn: Exactament, Alden. I llavors podem tornar true. D'acord. Però segueix sent una bona idea de fer les coses al final de la llista, no? Està bé. Encara podríem aconseguir realment al final de la llista. Així és aquest codi bé si estem en el final de la llista i hi ha alguns les coses a la llista? Cert? Com que encara tenim idea de Marcus. Podem sortir d'aquest bucle, perquè estem en el final de la llista. Llavors, encara volem aquest codi ací baix? 

AUDIÈNCIA: Si. 

JASON Hirschhorn: Si. I què és el que hem de canviar això? Veritable. ¿Sona bé a tothom fins al moment? Algú té alguna - Avi, Tens alguna cosa que afegir? 

AUDIÈNCIA: No 

JASON Hirschhorn: OK. Així que hem fet un parell de canvis. Hem fet aquesta comprovació abans que vam per a una llista buida. Així que ens hem ocupat d'una llista buida. I aquí ens ocupem de la inserció a final de la llista. Així que sembla que aquesta presa de bucle while cura de les coses en el medi, en algun lloc de la llista si hi ha són les coses a la llista. 

D'acord. Correm aquest programa de nou. No èxit. 

AUDIÈNCIA: No ho fan. 

JASON Hirschhorn: Oh, Jo no ho vaig fer. Bon punt, Michael. Anem a afegir una marca vinculada. Línia 87 hi ha un error. Línia 87. Alden, aquesta va ser la línia que em vas donar. Què passa? 

AUDIÈNCIA: Ha de ser null. 

JASON Hirschhorn: Excel · lent. Exactament dreta. Ha de ser nul. Anem a fer de nou. Compilació. D'acord. Anem a inserir 03:00. L'insert va ser reeixida. Anem a imprimir cap a fora. Oh, si tan sols poguéssim comprovar. Però no hem fet el imprimir funció encara. Ens endinsarem en una altra cosa. Què hem d'entrar? 

AUDIÈNCIA: Set. 

JASON Hirschhorn: Seven? 

AUDIÈNCIA: Si. 

JASON Hirschhorn: Tenim una falla seg. Així que ens van donar una, però clarament no pot aconseguir dues. És 05:07. Així que podem depurar aquest durant tres minuts. Però jo vaig a deixar-nos aquí i passar a taules hash. Però, de nou, les respostes d'aquest codi Vaig a enviar per correu electrònic a vostè en un moment. Estem molt a prop d'ella. Jo us animo a descobrir Què està passant aquí i arreglar-ho. Així que vaig a per correu electrònic aquest codi com així més la solució - probablement la solució més endavant. En primer lloc aquest codi. 

L'altra cosa que vull fer abans que final és que no hem alliberat a res. Així que vull que li mostri el valgrind sembla. Si correm límits valgrind en el nostre programa. / enllaçat. Un cop més, d'acord amb aquesta diapositiva, ens ha d'executar valgrind amb algun tipus de opció, en aquest cas - Fuga-check = full. Així que anem a escriure valgrind - Fuga-check = full. Així que això funcionarà valgrind en el nostre programa. I ara el programa realment funciona. Així que anem a executar com abans, posar una mica polz Em vaig a posar en tres. Això funciona. No vaig a tractar de posar en alguna cosa més perquè anem a aconseguir un fals segons en aquest cas. Així que només vaig a deixar de fumar. 

I ara que es veu aquí sota fuites i resum munt. Aquestes són les coses bones que voleu comprovar. Així que el resum del munt - diu, en ús a la sortida - 08:00 bytes en un bloc. Aquest bloc és el node que malloced. Michael, va dir abans d'un node és de vuit picades perquè té el número sencer i el punter. Així que aquest és el nostre node. I després diu que fem servir malloc set vegades i ens alliberem alguna cosa en sis ocasions. Però mai es diu lliure, així que no tinc idea del que està parlant. 

Però només cal dir que quan el seu programa s'executa, malloc s'està cridant en alguns altres llocs que no cal preocupar-se. Així malloc probablement va ser anomenat en alguns llocs. Nosaltres no hem de preocupar on. Però això és realment nosaltres. Aquesta primera línia és nosaltres. Sortim d'aquest bloc. I es pot veure que aquí en el resum de fuites. Encara assolible - 08:00 bytes en un bloc. Això vol dir que la memòria - hem escapat aquest record. Definitivament perdut - alguna cosa es perd per sempre. En general, no ho faràs veure res allà. Encara pot arribar és generalment on veuràs les coses, on voldrà de mirar per veure quin codi ha de vostè s'han alliberat però es va oblidar d'alliberar. 

I després, si aquest no era el cas, si ho féssim tot gratis, podem comprovar això. Anem a executar el programa no posar en qualsevol cosa. Vostè veurà aquí a ús en la sortida - zero bytes en zero blocs. Això vol dir que ja no tenia res quan aquest programa es tanca. Així que abans de donar volta a pset6, valgrind executar i assegureu-vos que vostè no té qualsevol pèrdues de memòria en el seu programa. Si vostè té alguna pregunta amb valgrind, no dubti en apropar-se. Però això és com ho fa servir. Molt senzill - si vostè tenir en ús a la sortida - qualsevol byte en qualsevol bloc. 

Així que estàvem treballant en el node d'inserció. Tenia dues funcions aquí - imprimir els nodes i els nodes lliures. Una vegada més, es tracta de funcions que són serà bo perquè practiquis ja que l'ajudarà no només amb aquests exercicis de mostra, sinó també en el conjunt de problemes. Es corresponen en molt de prop a les coses vostè va a haver de fer al estableix problema. Però jo vull estar segur Toquem tot. I les taules hash també són crucials per el que estem fent a la secció d'aquest setmana - o en el conjunt de problemes. 

Així que anem a acabar la secció parlant de les taules hash. Si vostè nota que vaig fer una petita taula hash. Això no és el que estem parlant sobre, però. Estem parlant d'un diferent tipus de taules hash. I en el fons, una taula hash no és més que una gamma més una funció hash. Anem a parlar una mica només per assegureu-vos que tothom entén el que és un funció hash és. I et dic ara que és res més que dues coses - una matriu i una funció hash. I aquests són els passos a través de que aquesta opera. 

Aquí està la nostra matriu. Aquí està la nostra funció. En particular, les funcions de hash necessiten fer un parell de coses amb això. Vaig a parlar específicament sobre estableix aquest problema. Probablement va a prendre en una cadena. I què tornarà? Quin tipus de dades? Alden? Retorni la seva funció hash? Un sencer. Així que això és el que el hash taula consta de - una taula en forma de matriu i una funció de hash. Com funciona? Funciona en tres passos. Li donem una clau. En aquest cas, anem a donar-li una cadena. Cridem a la funció hash pel pas 1 a la clau i obtenim un valor. 

En concret, direm obtenim un nombre enter. Aquest nombre enter, no són molt específics límits al que pot ser sencer. En aquest exemple, la nostra matriu és de grandària 3. Llavors, què números pot ser aquest sencer. Quin és el rang de valors vàlids per aquest sencer, el tipus de retorn d'aquesta funció hash? Zero, un i dos. El punt de la funció hash és esbrinar el lloc de la matriu on la clau va. Només hi ha tres possibles llocs aquí - zero, un, o dos. Així que aquesta funció millor retorn zero, un, o dos. Alguns índex vàlida en aquest array. 

I a continuació, depenent d'on torna, es pot veure que hi ha antena oberta entre parèntesis el valor. Aquí és on posem la clau. Així que tirem a la carabassa, sortim zero. En conjunt suport 0, posem carbassa. Ens tirem en els gats, tenim a un. Posem en un gat. Posem a aranya. Sortim 02:00. Posem aranya en conjunt suport de dos. Seria molt bo si funcionar d'aquesta manera. Però, per desgràcia, com veurem, que és una mica més complicat. 

Abans d'arribar-hi, qualsevol pregunta sobre aquest bàsic posada a punt d'una taula hash? Aquesta és una imatge d'exactament el que dibuixem al tauler. Però ja ho dibuixem en el tauler, em No vaig a entrar-hi encara més. Essencialment, les claus, el quadre negre de màgia - o en aquest cas, la caixa verd blavós - d'un funció hash els posa en galledes. I en aquest exemple estem no posar el nom. Estem posant el telèfon associat nombre del nom al cub. Però molt bé podria simplement posar el nom al cub. 

Això és només una imatge del que dibuixem en el tauler. Tenim dificultats potencials, però. I hi ha dues en particular Les diapositives que vull anar. La primera d'elles és d'aproximadament una funció hash. Així que vaig fer la pregunta, què fa una bona funció hash? Li dono dues respostes. La primera és que és determinista. En el context de les funcions de hash, Què vol dir això? Sí? 

AUDIÈNCIA: Podeu trobar el índex constant de temps? 

JASON Hirschhorn: Que no és el que significa. Però això és una bona suposició. Algú més té una conjectura al que això significa? Que una bona funció hash és determinista? Annie? 

AUDIÈNCIA: Que una tecla només es pot assignar a un lloc en la taula hash. 

JASON Hirschhorn: Això és exactament correcte. Cada vegada que posa a la carbassa, sempre torna zero. Si vostè posa a la carbassa i l'haixix la funció retorna zero, però té un probabilitat de tornar alguna cosa més gran que zero - així que potser pot tornar un a vegades o dues vegades - això no és una bona funció hash. Tens tota la raó. La seva funció hash ha de tornar el mateix nombre enter exacte, en aquest cas, per la mateixa cadena exacta. 

Potser retorna el mateix nombre enter exacte per a la mateixa cadena exacta independentment de la capitalització. Però en aquest cas és encara determinista perquè diverses coses s'assignen en el mateix valor. Això està bé. Mentre que només hi ha una de sortida per a una entrada donada. 

D'acord. La segona cosa és que torna índexs vàlids. Vam portar fins que abans. Aquesta funció hash - oh boy - una funció hash ha de tornar índexs vàlids. Així ho diuen - anem a tornar a aquest exemple. La meva funció hash compte fins les lletres de la paraula. Aquesta és la funció hash. I torna aquest sencer. Així que si tinc la paraula A, és tornarà un. I es posarà una aquí. Què passa si em poso en la paraula ratpenat? Es va a tornar tres. A on va ratpenat? 

No encaixa. Però ha d'anar a algun lloc. Aquest és el meu taula hash després de tot, i tot ha d'anar a algun lloc. Llavors, on ha d'anar ratpenat? Alguna idea? Conjectures? Les bones conjectures? 

AUDIÈNCIA: Zero. 

JASON Hirschhorn: Per què zero? 

AUDIÈNCIA: Perquè tres mòdul 3 és igual a zero? 

JASON Hirschhorn: Triple mòdul de tres és zero. Aquesta és una gran suposició, i això és correcte. Així que en aquest cas s'ha de Probablement vagi a zero. Així que una bona manera d'assegurar que aquest hash funció només retorna índexs vàlids es al mòdul que per la mida de la taula. Si Mòdul Sigui el torna per tres, sempre es va a aconseguir alguna cosa entre zero, un i dos. I si això sempre torna 7, i sempre Mòdul per tres, ets sempre va a aconseguir el mateix. 

Pel que és encara determinista si MÒDUL. Però això va a assegurar que vostè mai aconseguir alguna cosa - una indústria no vàlid. Generalment, mòdul que hauria de passar dins de la seva funció de hash. Així que vostè no ha de preocupar-se per això. Només assegurar-vos que aquest és un índex vàlida. Teniu alguna pregunta respecte aquest potencial escull? 

D'acord. I aquí anem. Següent error potencial i aquesta és la gran. Què passa si dues claus mapa en el mateix valor? Així que hi ha dues maneres de gestionar això. La primera es diu lineal sondeig, que estic No vaig a anar una altra vegada. Però vostè ha d'estar familiaritzat amb la forma que funciona i el que és això. 

El segon, vaig a anar més ja que és el que molts la gent probablement va a acabar de decidir per utilitzar en el seu conjunt de problemes. Per descomptat, vostè no ha de fer-ho. No obstant això, per al conjunt de problemes, moltes persones tendeixen a optar per crear una taula hash amb encadenament separat per implementar seu diccionari. Així que anirem més del que significa per crear una taula hash amb encadenament separat. 

Així que em vaig posar en carbassa. Retorna zero. I vaig posar carbassa aquí. Llavors em vaig posar en - el que és una altra cosa amb temes de Halloween? 

AUDIÈNCIA: Candy. 

JASON Hirschhorn: caramel! Això és un gran un. Vaig posar en els dolços i caramels També em fa zero. Què faig? Alguna idea? Com que tota la classe de sap el encadenament separat és. Així que qualsevol idea de què fer? Sí 

AUDIÈNCIA: Posar la cadena realitat a la taula hash. 

JASON Hirschhorn: Així que anem a dibuixar la bona idea aquí. D'acord. 

AUDIÈNCIA: Tenir la taula hash [Inaudible] el punter que apunta a el principi d'una llista. I després han carbassa ser el primer valor en aquesta llista i dolços vinculat ser el segon valor en aquesta llista enllaçada. 

JASON Hirschhorn: OK. Marcus, que era excepcional. Vaig a trencar això. Marcus està dient que no sobreescriure carbassa. Això seria dolent. No posar el caramel en un altre lloc. Anem a posar a tots dos en zero. Però anem a fer front a posant-los a zero la creació d'una llista en zero. I anem a crear una llista de tot el que s'assigna a zero. I la millor manera que hem après per crear una llista que pot créixer i encongir dinàmica no està dins una altra matriu. Així que no és una matriu multidimensional. Però n'hi ha prou amb crear una llista enllaçada. 

Així que el que ell va proposar - Vaig a aconseguir un nou - és crear una matriu amb punters, una matriu de punters. D'acord. Qualsevol idea o suggeriment del que el tipus de d'aquests indicadors hauria de ser? Marcus? 

AUDIÈNCIA: Punters a - 

JASON Hirschhorn: Com que vostè va dir una llista enllaçada, així - 

AUDIÈNCIA: punters de node? 

JASON Hirschhorn: Punters de node. Si les coses a la nostra vinculats llista de nodes són llavors ha de ser punters de node. I què és el que equivalen a un principi? 

AUDIÈNCIA: Nul. 

JASON Hirschhorn: Nul. Així que no és el nostre buit. Torna carbassa zero. Què fem? Camina amb mi a través d'ell? En realitat, Marcus ja em va donar. Algú més em caminar a través d'ell. Què fem quan - això es veu molt similar a el que estàvem fent. Avi. 

AUDIÈNCIA: Me'n vaig a prendre una conjectura. Així que quan vostè aconsegueix el caramel. 

JASON Hirschhorn: Si. Bé, tenim carbassa. Anem a la nostra primera. Tenim carbassa. 

AUDIÈNCIA: OK. Torna carbassa zero. Així ho poses en això. O en realitat, el poses en la llista enllaçada. 

JASON Hirschhorn: Com el va posar a la llista enllaçada? 

AUDIÈNCIA: Oh, la sintaxi actual? 

JASON Hirschhorn: Només cal passar - dir més. Què fem? 

AUDIÈNCIA: Només cal inserir com el primer node. 

JASON Hirschhorn: OK. Així que tenim el nostre node, carbassa. I ara com ho introdueixo? 

AUDIÈNCIA: Vostè assigna en el punter. 

JASON Hirschhorn: Què punter? 

AUDIÈNCIA: L'indicador en zero. 

JASON Hirschhorn: Llavors, on fa aquest punt? 

AUDIÈNCIA: Per nul en aquests moments. 

JASON Hirschhorn: Bé, està apuntant a null. Però em vaig a posar a la carabassa. Llavors, on hauria d'apuntar? 

AUDIÈNCIA: Per carbassa. 

JASON Hirschhorn: Per carbassa. Exactament. Així que això apunta a la carabassa. I d'on ve aquest punter en el punt de carbassa? A 

AUDIÈNCIA: Nul. 

JASON Hirschhorn: null. Exactament. Així que només ens inserim una mica a la llista enllaçada. Acabem d'escriure el codi per fer això. Gairebé gairebé ens ho completament esquerdat. Ara inserim el caramel. El nostre dolços també tendeix a zero. Llavors, què fem amb els dolços? 

AUDIÈNCIA: Depèn de si No estem tractant de resoldre. 

JASON Hirschhorn: Això és exactament correcte. Depèn de si és o no que estem tractant de solucionar el problema. Anem a suposar que no estem solucionarà el problema. 

AUDIÈNCIA: Doncs bé, com hem comentat abans, és més senzill només per posar des del principi de manera que el punter de zero punts als dolços. 

JASON Hirschhorn: OK. Espera. Déjame crear dolços aquí. Així que aquest punter - 

AUDIÈNCIA: Sí, ara ha apuntar als dolços. Després que el punter de punt de caramel per a la carabassa. 

JASON Hirschhorn: Així? I diem que tenim una altra cosa per assignar a zero? 

AUDIÈNCIA: Bé, vostè acaba de fer el mateix? 

JASON Hirschhorn: Fer el mateix. Així que en aquest cas, si no ho fem volen mantenir el resolt que Sona bastant simple. Prenem el punter en l'índex donada per la nostra funció hash. Hem de apunten al nostre nou node. I llavors el que estava assenyalant prèviament - en aquest cas nul, al segon cas carbassa - que, sigui el que està assenyalant anteriorment, s'afegeix en el següent de nostre nou node. Estem inserint alguna cosa en el començament. De fet, això és molt més simple que tractant de mantenir la llista ordenada. Però, de nou, la cerca serà més complicat aquí. Sempre haurem d'anar fins al final. 

D'acord. Una pregunta sobre encadenament separat? Com funciona? Si us plau, pregunteu ara. Tinc moltes ganes d'assegurar-se que tots els entendre això abans que ens dirigim. 

AUDIÈNCIA: Per què et poses de carbassa i els dolços en el mateix part de la taula hash? 

JASON Hirschhorn: Bona pregunta. Per què els posem en la mateixa part de la taula hash? Bé, en aquest cas la nostra funció hash retorna zero per als dos. Així que han d'anar a zero índex perquè aquí és on anem a buscar si mai voler mirar cap amunt. Una vegada més, amb un enfocament de sondeig lineal nosaltres no posaríem els dos al zero. Però en l'enfocament de la cadena independent, ens posarem a tots dos en zero a continuació, crear una llista de zero. 

I no volem sobreescriure carbassa simplement per això, perquè llavors anem a assumir que la carabassa era mai inserit. Si acabem de tenir una cosa en la ubicació que seria dolent. Llavors no hi hauria oportunitat de nosaltres - si hem tingut un duplicat, llavors seria simplement esborrar el nostre valor inicial. Així que per això fem aquest enfocament. O és per això que vam triar - però de nou, va triar l'enfocament d'encadenament separat, que hi ha molts altres enfocaments un pot triar. Respon això a la seva pregunta? 

D'acord. Carles. Sondeig lineal implicaria - si trobem una col · lisió a zero, es veuria en el punt següent per veure si que estava obert i el va posar allà. I llavors ens mirem en el següent esport i veure si estava obert i el va posar allà. Així ens trobem amb la següent disposició lloc obert i el va posar allà. Alguna altra pregunta? Sí, Avi. 

AUDIÈNCIA: Com seguiment a això, Què vol dir el proper acte? A la taula hash o en una llista enllaçada. 

JASON Hirschhorn: Per lineal programació, no hi ha llistes enllaçades. El següent punt a la taula hash. 

AUDIÈNCIA: OK. Així que la taula hash seria inicialitzat a la mida - com el nombre de cadenes que estigués inserint? 

JASON Hirschhorn: El faries vull que sigui molt gran. Sí Aquí està una foto del que acaba de dibuixar al tauler. Un cop més, tenim una col · lisió aquí. a 152. I veuràs que hem creat una llista enllaçada fora. Un cop més, la taula hash encadenament separat enfocament no és el que vostè han de prendre per establir els problemes sis, però és una que molta els estudiants tendeixen a prendre. Així que en aquest sentit, parlarem breument abans que ens dirigim a terme sobre el problema de les sis, i després vaig a compartir amb vostès una història. Tenim tres minuts. 

Problema 6 set. Vostè té quatre funcions - càrrega, comprovar, la mida i descàrrega. Load - bo, hem estat anant sobrecàrrega en aquest moment. Dibuixem la càrrega en el tauler. I fins i tot ens vam començar a codificar una gran quantitat de inserir en una llista enllaçada. Així que la càrrega no és molt més que el que hem estat fent. 

Descobreix que és un cop una mica carregat. És el mateix procés que aquest. Les mateixes dues primeres parts on vostè llança alguna cosa dins de la funció hash i obtenir el seu valor. Però ara no estem d'inserir-lo. Ara estem buscant. He escrit el codi d'exemple per trobar alguna cosa en una llista enllaçada. Us animo a practicar això. Però intuïtivament trobar alguna cosa que es bastant similar a la inserció d'alguna cosa. De fet, ens va fer un dibuix de la recerca alguna cosa en una llista enllaçada, movent-se a través fins que vam arribar a la final. I si arribem a la final i no podia troba, llavors no hi és. Així que això és xec, essencialment. 

Següent és la mida. Anem a saltar mida. Finalment has descarregar. Unload és que no hem elaborat a la pissarra o encara codificada. Però m'animo a provar a programar en la nostra mostra exemple de llista enllaçada. Però descarregar intuïtiva és similar a la lliure - o que vull dir és similar a comprovar. Excepte moment cada vegada que vostè va a través, no estàs seleccionant veure si vostè té el seu valor allà. Però vostè està prenent aquest node i alliberant, essencialment. Això és el que es baixa et demana que facis. Tot el lliure que ha malloced. Així que vas a través de tota la llista de nou, passant per tot el hash taula de nou. Aquesta vegada no marca per veure el que hi ha. Només alliberar el que hi ha. 

I finalment mida. Mida ha de ser implementat. Si no s'implementa la mida - Vaig a dir-ho d'aquesta manera. Si no s'implementa mida exactament una línia de codi que inclou el tornar declaració, vostè és fent mida incorrectament. Així que assegureu-vos que la mida, per al disseny complet punts, ho estàs fent exactament en un línia de codi, incloent la sentència return. 

I no les maletes, però, Akchar. Eager Beaver. Volia donar les gràcies nois per venir a la secció. Tingueu un feliç Halloween. Aquest és el meu disfressa. Portaré aquest dijous si et veig en horari d'oficina. I si ets curiós sobre una mica més fons per a aquest vestit, se senten lliure de visitar la secció 2011 per a una història sobre per què estic vestint el vestit de carbassa. I és una història trista. Així que segur de tindre alguns teixits propers. Però en això, si vostè té qualsevol preguntes que em quedaré per aquí fora després de la secció. Bona sort en problema sisos. I com sempre, si té alguna preguntes, que em faci saber.