Jason Hirschhorn: Sexan benvidos á Sección de Sete. Estamos na semana de sete do curso. E esta próximo xoves Halloween é así que eu son vestido como unha cabaza. Eu non podía curvar e poñer en meus zapatos, entón é por iso que eu son só vestindo medias. Eu tampouco estou usando nada por baixo iso, entón eu non podo tirá-lo, se é distraendo a vostede. Pido desculpas por adiantado por iso. Non precisa de imaxinar o que está pasando. Estou usando cueca. Entón, é todo de bo. Eu teño unha longa historia sobre por que estou vestido como unha cabaza, pero eu vou gardar para máis tarde nesta sección porque quero comezar. Temos unha morea de cousas interesantes para ir ao longo desta semana. A maioría deles están directamente relacionadas con esta conxunto de problemas da semana, erros de ortografía. Nós imos estar pasando por riba conectado listas e táboas hash para toda a sección. Coloque esta lista cada semana, unha lista de recursos para que poida axudar con O material deste curso. Se a unha perda ou se buscar algunha obter máis información, confía un dos eses recursos. Unha vez máis, é pset6 erros ortográficos, pset desta semana. E tamén anima ti, e eu incentivos-lo, usar algún outro recursos especialmente para este pset. En particular, os tres que eu teño listado na pantalla - gdb, que fomos familiarizado con e usado por un tempo agora, é vai ser moi útil nesta semana. Entón eu coloque iso aquí enriba. Pero sempre que está a traballar con C, ten que sempre estar usando gdb para depurar os seus programas. Esta semana tamén Valgrind. Alguén sabe o que Valgrind fai? Audiencia: El verifica se hai perdas de memoria? Jason Hirschhorn: Valgrind comproba se hai perdas de memoria. Entón, se malloc algo no seu programa, está pedindo para a memoria. Ao final do seu programa, ten libre para escribir sobre todo o que teño malloced para dar a memoria de volta. Se non escribir libre ao final e o programa chega a unha conclusión, todo automaticamente ser liberado. E para pequenos programas, é non un gran negocio. Pero se está escribindo unha longa carreira programa que non parar, necesariamente, nun par de minutos ou unha uns segundos, a continuación, perdas de memoria pode facer un gran negocio. Así, para pset6, a esperanza é que vai ter cero derrames de memoria con seu programa. Para comprobar se hai perdas de memoria, Valgrind realizar e só pode darlle algún bo saída que permite que vostede sabe se ou non todo estaba libre. Imos practicar con el máis tarde hoxe, eu espero. Por último, a orde dif. Usou algo semellante a el en pset5 coa ferramenta espiar. Permitiu-lle ollar para dentro. Tamén usou diff, tamén, por o conxunto de problemas spec. Pero, permítelle comparar dous arquivos. Podería comparar o ficheiro de mapa de bits e Información cabeceiras dunha solución persoal e a súa solución en pset5 se Escolleu usalo. Dif permitirá que facelo, tamén. Pode comparar a resposta correcta para problema desta semana para definir a súa resposta e ver se se Aliñar ou ver en que os erros son. Polo tanto, estas son tres boas ferramentas que pode usar para esta semana, e definitivamente comprobar o seu programa con estas tres ferramentas antes de virar-lo dentro Unha vez máis, como xa mencionado cada semana, se ten algún comentario para min - tanto positiva e constructiva - sentir-se libre para ir ao sitio web na parte inferior da diapositiva e introducir-la alí. Eu realmente aprecio calquera e todos os comentarios. E se me dar cousas específicas que Que podo facer para mellorar ou que eu son facendo ben que lle gustaría que eu continuar, eu levo iso en serio e realmente se esforzo para escoitar para o seu producto. Eu non podo prometer que vou facer todo, porén, como levar unha cabaza traxe cada semana. Entón imos pasar a maior parte sección, como xa referín, fala listas ligadas e táboas de hash, que será directamente aplicable ao conxunto de problemas esta semana. Listas encadeadas, imos pasar por riba de concepto axiña, porque nós pasamos un pouco máis xusto tempo indo sobre el na sección. E entón imos directo ao codificación problemas para listas ligadas. E entón ao final imos falar táboas hash e como se aplican a este O problema da semana definido. Xa viu este código antes. Esta é unha estrutura, e que consiste en establecer algo novo chamado nó. E dentro dun nodo existe un número enteiro aquí e alí é un punteiro para outro nodo. Nós xa vimos isto antes. Iso foi chegando a un par de semanas agora. El combina os punteiros, que fomos traballar con, e estruturas, que permiten nos a combinar dous diferentes cousas nun tipo de datos. Hai moita cousa a suceder na pantalla. Pero todo isto debe ser relativamente familiarizado con vostede. Na primeira liña, nós declarar un novo nodo. E, a continuación, dentro dese novo nodo, eu definir o enteiro en que o nodo a un. Vemos a próxima liña que eu estou facendo un printf mando, pero eu xa esmaecidas a orde printf, porque a verdade parte importante é esta liña aquí - new_node.n. O que fai o punto significa? Audiencia: Ir a nó e avaliar o valor n a el. Jason Hirschhorn: Isto é exactamente correcto. Dot significa acceder a parte n deste novo nodo. A seguinte liña fai o que? Michael. Audiencia: Crea outro nodo que pode apuntar para o novo nodo. Jason Hirschhorn: Entón non fai crear un novo nodo. El crea un o que? Audiencia: Un punteiro. Jason Hirschhorn: Un enlace a un nodo, indicadas por este nodo * aquí. Así, créase un punteiro a un nodo. E cal nodo é apuntando para, Michael? Audiencia: Novo nodo? Jason Hirschhorn: Novo nodo. E está a apuntar alí porque temos dado o enderezo do novo nodo. E agora nesta liña podemos ver dous xeitos diferentes de expresando o mesmo. E eu quería salientar a forma na que estes dúas cousas son o mesmo. Na primeira liña, nós desreferenciava o punteiro. Entón imos ao nodo. Iso é o que esta estrela significa. Nós xa vimos isto antes con punteiros. Ir a aquel nó. Isto é entre parénteses. E, a continuación, acceder a través do operador punto o elemento n dese nodo. Entón, que está tomando a sintaxe vimos aquí e agora usalo cun punteiro. Por suposto, está un pouco ocupado está escribindo eses parénteses - que estrela e que punto. Queda un pouco ocupado. Polo tanto, temos un pouco de azucre sintático. E esta liña aquí - ptr_node-> n. Isto fai exactamente o mesmo. Entón, estas dúas liñas de código son equivalente e fará exactamente o mesmo. Pero eu quería sinalar aqueles antes de ir máis lonxe para que poida entender que realmente esta cousa aquí é só azucre sintático para dereferencing o punteiro e logo, indo a a parte n desta estrutura. Calquera dúbida sobre este foto? Aceptar. Entón imos pasar por unha parella de operacións que pode facer na listas ligadas. Unha lista ligada, recall, é unha serie de nós que ligan un ao outro. E nós xeralmente comezan cun punteiro chamado cabeza, en xeral, que apunta a o primeiro na lista. Entón, na primeira liña aquí, nós temos o noso L orixinal primeiros. Entón aquela cousa que pode pensar - este texto aquí pode pensar en como só o punteiro temos almacenados que nalgún lugar puntos ao primeiro elemento. E nesta lista ligada temos catro nós. Cada nó é unha caixa grande. O cadro máis grande dentro da gran caixa é a parte enteira. E entón nós temos unha parte do punteiro. Esas caixas non son atraídos a escala, xa que o grande é un número enteiro de bytes? Como gran agora? Catro. E o grande é un punteiro? Catro. Entón, realmente, se fose deseñar esta para escalar as dúas caixas sería o mesmo tamaño. Neste caso, queremos introducir algo na lista encadeada. Así pode ver aquí abaixo estamos inserindo Nós cinco atravesar o lista ligada, atopar onde cinco vai, e, a continuación, introduza-o. Imos romper ese abaixo e ir algo máis a modo. Vou apuntar para o consello. Entón, nós temos o noso nodo cinco que creamos en mallocs. Por que todos están rindo? Brincadeirinha. Aceptar. Entón nós malloced cinco. Creamos este nodo noutro lugar. Nós temo-lo preparado para ir. Comezamos diante nosa lista con dous. E nós queremos introducir dunha forma ordenada. Entón, se vemos dous e queremos poñer en cinco anos, o que facemos cando vemos algo menos que nós? O que? Queremos introducir cinco a este lista ligada, manténdose clasificada. Vemos o número dous. Entón, o que facemos? Marcus? Audiencia: Chama o punteiro ao seguinte nodo. Jason Hirschhorn: E por que imos ao seguinte? Audiencia: Porque é a seguinte nodo da lista. E só sabemos que outro local. Jason Hirschhorn: E cinco é maior que dous, en particular. Porque queremos mantelo ordenado. Así, cinco é maior que dous. Entón, imos pasar á seguinte. E agora chegamos a catro. E o que pasa cando chegamos a catro? Cinco é maior que catro. Por iso, manter-se ir. E agora estamos en seis. E o que vemos ás seis? Si, Carlos? Audiencia: Seis é maior que cinco. Jason Hirschhorn: Seis é maior que cinco. Entón é aí que queremos inserir cinco. Con todo, ten en conta que, se só ten un punteiro aquí - este é o noso punteiro extra que é percorrendo a lista. E nós estamos apuntando para seis. Perdemos a noción do que vén antes das seis. Polo tanto, se queremos introducir algo na esta lista manténdose clasificado, que probablemente precisa de cantos punteiros? Audiencia: Dous. Jason Hirschorn: Dous. Un para seguir a corrente un e un para seguir o anterior. Esta é só unha lista vinculada illadamente. El só vai unha dirección. Se tivésemos unha lista dobremente vinculada, onde todo estaba a apuntar cara a cousa despois de que el ea cousa antes, entón nós non precisamos facelo. Pero neste caso non queremos perder a par do que viñeron antes de nós, no caso necesitamos introducir cinco nalgún lugar no medio. Digamos que foron inserindo nove. Que pasaría cando chegamos a oito? Audiencia: Vostede tería que obter ese punto nulo. En vez de ter punto nulo que tería engadir un elemento e, a continuación, teñen que apuntan a nove. Jason Hirschorn: Exactamente. Entón, temos oito. Chegamos ao final da lista, xa que este está a apuntar cara null. E agora, en vez de ter que ligan con nulo, temos que apuntar para o noso novo nodo. E imos establecer o punteiro na noso novo nodo como nulo. Alguén ten algunha dúbida sobre como inserir? E se eu non me importa manter a lista ordenada? Audiencia: Cole-o na inicio ou o final. Jason Hirschorn: Cole-o na o inicio ou o final. Cal deles que temos que facer? Bobby? Por que o fin? Audiencia: Como o principio xa está cuberto. Jason Hirschorn: Aceptar. O inicio xa está cheo. Quen quere argumentar contra Bobby. Marcus. Audiencia: Ben, probablemente vai querer cola-la no inicio, xa que en caso contrario, se poñelas ao final ten que percorrer a lista enteira. Jason Hirschorn: Exactamente. Entón, se estamos a pensar en tempo de execución, o tempo de execución da inserción no extremo Sería n, o tamaño deste. Cal é a gran O tempo de execución de inserción no inicio? Tempo constante. Entón, se non lle importa en manter algo clasificado, moito mellor só inserir ao principio desta lista. E iso se pode facer en tempo constante. Aceptar. Seguinte operación é atopar, o que outros - nós formulada isto como investigación. Pero imos ollar polo lista ligada por algún obxecto. Vostedes viron o código para buscar antes na charla. Pero nós medio que fixo introducir, ou polo menos a inserción algo ordenado. Mira través, pasando nó por nodo, ata atopar o número que está a procurar. Qué acontece se chegar Ao final da lista? Digamos que eu estou buscando nove e eu acadar o final da lista. O que imos facer? Audiencia: Retorno falso? Jason Hirschorn: Return false. Non atopalo. Se chegar ao final da lista e non atopa o número que está a buscar, non está alí. Calquera dúbida sobre atopar? Se isto fose unha lista ordenada, o que sería ser diferente a nosa procura? É. Audiencia: El ía atopar o primeiro valor que é maior que aquel está a buscar e a continuación, regresar false. Jason Hirschorn: Exactamente. Entón, se é unha lista ordenada, se chegamos a algo que é maior que o que nós estamos a buscar, non necesita continuar ata o final da lista. Podemos nese punto return false porque nós non imos atopalo. A cuestión agora é, nós xa falamos sobre manter listas ligadas ordenada, manténdose os domésticos. Isto vai ser algo que está probablemente vai ter que pensar sobre cando o problema de codificación establecer cinco, se escoller unha táboa hash coa separado visión de fío, que falaremos máis tarde. Pero paga a pena manter a lista ordenada e, a continuación, ser capaz de ter quizais enquisas rápidas? Ou é mellor para inserir rapidamente algo en tempo de execución constante, pero, a continuación, ter máis tempo buscando? Isto é un intercambio alí mesmo que comeza a decidir o que é máis axeitado para o seu problema específico. E non é necesariamente un resposta absolutamente certa. Pero certamente é unha decisión que comeza de facer, e probablemente bo para defender que, digamos, un comentario ou dous por escolleu un sobre o outro. Por último, excluíndo. Vimos a borrar. É semellante a buscar. Nós miramos para o elemento. Diga que estamos tentando eliminar seis. Así, atopamos seis aquí. O único que temos que estar seguro de que facer é que todo o que está a apuntar cara seis - como podemos ver no paso dous para acá - todo o que está a apuntar cara seis necesidades para saltar seis e agora ser cambiado todo o que está a apuntar cara seis. Non quero nunca orfos resto da nosa lista por esquecer de definir que punteiro anterior. E entón, ás veces, dependendo sobre o programa, eles só eliminar este nodo enteiramente. Ás veces vai querer volver o valor que está neste nodo. Entón é así que borrar obras. Calquera dúbida sobre borrar? Audiencia: Entón, se está indo para borrar que se acaba de usar libre porque presuntamente foi malloced? Jason Hirschorn: Se quere liberar algo que é certo e malloced el. Digamos que quería retornar ese valor. Poderiamos volver seis anos e, así, libre este nodo e chamada gratuíta sobre el. Ou nós probablemente chame gratis primeiro e despois volver seis. Aceptar. Entón, imos pasar á práctica de codificación. Imos codificar tres funcións. O primeiro chámase insert_node. Entón tes o código que eu lle enviou, e se está a ver isto, máis tarde, pode acceder ao código en linked.c na páxina web do CS50. Pero en linked.c, hai algún código de esqueleto que xa está foi escrito para ti. E despois hai un par de funcións ten que escribir. Primeiro imos escribir insert_node. E o que fai insert_node sexa inserir un número enteiro. E está dando o enteiro nunha lista encadeada. E, en particular, hai que para manter a lista ordenada do menor ao maior. Ademais, non quere introducir todos os duplicados. Finalmente, como se pode ver insert_node retorna un bool. Entón está suposto de que o usuario saiba se ou non a inserción era éxito, retornando verdadeiro ou falso. Ao final deste programa - e para esta fase non é necesario preocuparse liberando nada. Entón todo o que está a facer é tomar un enteiro e inserir-lo nunha lista. Iso é o que eu estou pedindo para lle facer agora. Unha vez máis, o linked.c, onde todos teñen, é o código de esqueleto. E ten que ver para o fondo a declaración da función mostra. Con todo, antes de ir a codifica-lo en C, eu altamente incentivos-lo a ir a través dos pasos que fomos practicando cada semana. Nós xa pasamos por unha imaxe desta. Entón ten que ter algún coñecemento de como funciona isto. Pero gustaríame incentivos-lo a escribir algúns pseudocódigo antes de mergullar dentro E nós imos pasar por riba de pseudocódigo como un grupo. E, a continuación, unha vez que teña escrito o pseudocódigo, e unha vez que escribimos o noso pseudocódigo como un grupo, pode ir a codifica-lo en C. Como un heads-up, a función insert_node é probablemente a máis complicada de os tres que imos escribir, porque eu engadiu algunhas restricións adicionais para súa programación, en particular, que non está indo para introducir calquera dobre e que a lista debe permanecer ordenada. Polo tanto, este é un programa non-trivial que precisa para codificar. E por que non tira 06:55 minutos, só para se traballar na pseudocódigo eo código. E entón, imos comezar indo como un grupo. De novo, se ten algunha dúbida pode levante a man e eu vou chegar preto. . Tamén xeralmente fan estes - ou eu non explicitamente dicir que pode traballar con persoas. Pero, obviamente, eu altamente incentivos-lo, se ten dúbidas, pedir ao veciño sentado ao seu lado ou incluso traballar con alguén outra cousa, se quere. Isto non ten que ser un individuo actividade en silencio. Imos comezar coa escrita dalgúns pseudocódigo na tarxeta. Quen me pode dar a primeira liña de pseudocódigo para este programa? Para esta función, en vez - insert_node. Alden? Audiencia: Entón, o primeiro que fixen foi crear un novo punteiro para o nó e I iniciar el apuntando para o mesmo que lista está a apuntar. Jason Hirschorn: Aceptar. Entón, está creando un novo punteiro á lista, non para o nodo. Audiencia: Certo. É. Jason Hirschorn: Aceptar. E entón o que é o que queremos facer? O que hai despois? E o no? Nós non temos un nó. Nós só temos un valor. Se queremos introducir un nodo, o que nós cómpre facer antes de nós pode incluso pensar en inserir-lo? Audiencia: Oh, desculpe. necesitamos malloc espazo para un nó. Jason Hirschorn: Excelente. Imos facer - Aceptar. Non se puido chegar a esa altura. Aceptar. Estamos indo para ir para abaixo, e despois estamos a usar dúas columnas. Eu non podo ir que - Aceptar. Crear un novo nodo. Pode crear outro punteiro para consultar ou pode simplemente usar a lista, xa que existe. Realmente non ten que facelo. Entón, creamos un novo nodo. Grande. Isto é o que facer primeiro. Cal é o próximo? Audiencia: Agarde. Debemos crear un novo nodo agora ou hai que esperar para ter seguro de que non hai ningunha duplicado do nodo na lista antes de crealo? Jason Hirschorn: Boa pregunta. Imos manter isto para despois, porque a maior parte do tempo nós imos estar creando un novo nodo. Entón, imos manter isto aquí. Pero iso é unha boa pregunta. Se nós o creamos e vemos un dobre, o que debe o que facemos antes de regresar? Audiencia: Liberar-lo. Jason Hirschorn: Yeah. Probablemente liberalo la. Aceptar. O que imos facer despois de que crear un novo nodo? Annie? Audiencia: Poñemos o número do nodo? Jason Hirschorn: Exactamente. Poñemos o número - que malloc espazo. Vou deixar que todo como unha liña. Pero está certo. Nós malloc espazo, e, a continuación, imos poñer o número de polgadas Podemos incluso facer que o punteiro parte del para null. Isto é exactamente correcto. E entón o que dicir despois diso? Nós tirei esta foto no cadro. Entón, o que facemos? Audiencia: Imos a través da lista. Jason Hirschorn: Vai á lista. Aceptar. E que é o que imos comprobar a en cada nodo. Kurt, o que nós consideramos para en cada nó? Audiencia: Vexa o valor de n este nodo é maior que o valor de n do noso nodo. Jason Hirschorn: Aceptar. Vou facer - si, Aceptar. Por iso, é n - Eu vou dicir que se o valor é maior que este nodo, entón o que facemos? Audiencia: Ben, entón nós inserimos as cousas ben antes diso. Jason Hirschorn: Aceptar. Entón, se é maior que iso, entón nós queremos introducir. Pero queremos inserir-lo logo antes porque nós tamén precisaría ser manter o control e, a continuación, do que era antes. Entón, introduza antes. Entón, nós probablemente perdeu algo anteriormente. Nós probablemente hai que manter a par do que está pasando. Pero imos volver alí. Entón, o valor é menor que? Kurt, o que imos facer se valor é menor que? Audiencia: Entón só manterá a menos que sexa o último. Jason Hirschorn: Eu gusto diso. Entón, vai ao seguinte nodo. A menos que sexa o último - nós probablemente estamos comprobando para que nos termos dunha condición. Pero si, preto nó. E iso está quedando moi baixo, así que imos pasar aquí. Pero se - pode todo o mundo ve iso? Si somos iguais, o que facemos? O valor que estamos intentando introducir é igual ao valor deste nodo? Si? Audiencia: [inaudível]. Jason Hirschorn: Yeah. Dada esta - Marcus está certo. Poderiamos ter feito quizais algo diferente. Pero dado que creamos, aquí debemos liberar e despois volver. Oh boy. Está mellor? Como é iso? Aceptar. Libre e, a continuación, que é o que imos volver, [inaudível]? Aceptar. Será que estamos perdendo algo? Entón para onde estamos mantendo o control do nodo anterior? Audiencia: Coido que ía despois de crear un novo nodo. Jason Hirschorn: Aceptar. Así, a principios probablemente imos - si, podemos crear un punteiro a unha nova no, como un punteiro nodo anterior e un punteiro nodo actual. Entón, imos introducir este aquí. Crear actual e anterior punteiros para os nós. Pero cando é que imos establecer os punteiros? Onde é que imos facelo no código? Jeff? Audiencia: - condicións de valor? Jason Hirschorn: Cal un en particular? Audiencia: Eu só estou confuso. O valor é maior que este nodo, non quere dicir que quere ir ao seguinte nodo? Jason Hirschhorn: Entón se o seu valor é maior que o valor de este nodo. Audiencia: É, entón vai querer ir máis abaixo da liña, non? Jason Hirschhorn: Certo. Entón, nós non inserir-lo aquí. O valor é inferior a este nodo, logo imos ao seguinte nodo - ou entón nós inserir antes. Audiencia: Espere, o que é iso nó e que é valor? Jason Hirschhorn: Boa pregunta. Valor por esta definición de función é o que está dado. Así, o valor é o número que está dado. Entón, se o valor é menor que iso no, necesitamos tempo para inserir. O valor é maior que este nodo, imos ao seguinte nodo. E de volta á pregunta orixinal, con todo, onde - Audiencia: O valor é maior que este nodo. Jason Hirschhorn: E así Que facemos aquí? Doce. Isto é correcto. Eu só vou escribir punteiros de actualización. Pero, si, co actual actualiza-lo para apuntar á seguinte. Calquera outra cousa que falta? Entón, eu estou indo a introducir esta código en gedit. E mentres eu fai iso, pode ter un máis uns minutos para traballar na codificación esta en C. Entón, eu teño a entrada do pseudocódigo. Unha nota rápida antes de comezar. Podemos non ser capaces de completamente rematar esta en todos estas tres funcións. Hai solucións correctas para eles que eu vou enviar correo-e para vós despois de sección, e vai ser posta en CS50.net. Entón eu non incentivos-lo a ir ollar para as seccións. Estimula-vos a probar estes no seu posuír, e logo use o da práctica problemas para revisar as súas respostas. Estes foron deseñados para preto relacionar-se e unirse ao que ten que facer no set problema. Entón eu animou-vos a practicar este no seu propio país e, a continuación, usar o código para comprobar as súas respostas. Porque quero pasar ao hash mesas nalgún momento na sección. Por iso, non pode ir con el en todo momento. Pero imos facer o máximo que pudermos agora. Aceptar. Imos comezar. Asam, como é que imos crear un novo nodo? Audiencia: Vostede struct *. Jason Hirschhorn: Entón nós teñen que aquí enriba. Oh, desculpe. Vostede estaba dicindo struct *. Audiencia: E entón [? tipo?] nó ou nodo c. Jason Hirschhorn: Aceptar. Vou chamalo NEW_NODE para que poidamos estar consistente. Audiencia: E quere establecer que a cabeza, o primeiro nodo. Jason Hirschhorn: Aceptar. Entón, agora está a apuntar cara - de xeito que este non creou un novo nodo aínda. Isto é só apuntando para o primeiro nodo da lista. ¿Como crear un novo nodo? Se eu ter de espazo para crear un novo nodo. Malloc. E como grande? Audiencia: O tamaño da estrutura. Jason Hirschhorn: O tamaño da estrutura. E o que está a struct chamado? Audiencia: Nó? Jason Hirschhorn: Node. Entón malloc (sizeof (node)); dános espazo. E é nesa liña - unha cousa é incorrecta nesta liña. É NEW_NODE un punteiro a un struct? Este é un nome xenérico. Que é - no, exactamente. É un nó *. E o que imos facer logo nós malloc algo, Asan? Cal é o primeiro que facemos? E se non funciona? Audiencia: Oh, comprobar se apunta para o no? Jason Hirschhorn: Exactamente. Entón, se é igual a NEW_NODE iguais nulo, o que imos facer? Isto retorna un bool, esa función. Exactamente. Parece bo. Algo que engadir aí? Nós imos engadir cousas ao final. Pero que ata agora parece ser bo. Crear indicadores actuais e anteriores. Michael, como fago isto? Audiencia: Vostede tería para facer un nó *. Vostede tería que facer un non para NEW_NODE pero para o nós xa temos. Jason Hirschhorn: Aceptar. Así, o nodo actual no que estamos. Vou chamar a que curro. Todo ben. Nós decidimos que queremos manter dous, porque necesitamos saber o que está á súa fronte. Que son inicializados a? Audiencia: O seu valor na nosa lista. Jason Hirschhorn: Entón, cal é o primeiro na nosa lista? Ou como é que sabemos onde a inicio da nosa lista é? Audiencia: Non é pasado para a función? Jason Hirschhorn: Certo. Foi aprobada en aquí. Entón, se é pasado para a función, o inicio da lista, o que temos definir corrente igual? Audiencia: List. Jason Hirschhorn: List. Isto é exactamente correcto. Agora que ten o enderezo de o inicio da nosa lista. E que dicir anterior? Audiencia: Lista menos un? Jason Hirschhorn: Hai nada antes del. Entón o que podemos facer para significar nada? Audiencia: Null. Jason Hirschhorn: Yeah. Isto soa como unha boa idea. Perfecto. Grazas. Vai á lista. Constantino, canto tempo é que imos para percorrer a lista? Audiencia: ata chegarmos nulo. Jason Hirschhorn: Aceptar. Polo tanto, se, á vez, polo loop. O que estamos facendo? Audiencia: Quizais un loop? Jason Hirschhorn: Imos facer un loop for. Aceptar. Audiencia: E dicimos para - ata que o punteiro actual non é igual a cero. Jason Hirschhorn: Entón, se sabemos que o condición, como podemos escribir un loop baseado fóra desa condición. Que tipo de lazo que debemos usar? Audiencia: While. Jason Hirschhorn: Yeah. Isto fai máis sentido en base fóra do que dixo. Se nós só quere ir para nós sería só sei que cousa, non faría sentido de facer un loop while. Aínda actual non é igual a cero, se o valor é inferior a este nodo. Akshar, dáme desa liña. Audiencia: Se a cadea-> n n menor que o valor. Ou desfacer iso. Cambiar este soporte. Jason Hirschhorn: Sentímolo. Audiencia: Cambiar o soporte. Jason Hirschhorn: Entón, se é maior que o valor. Porque iso é confuso co comentario anterior, eu vou facelo. Pero si. O noso valor é menor que iso no, o que imos facer? Oh Teño-o aquí. Inserir antes. Aceptar. Como facemos iso? Audiencia: Éme aínda? Jason Hirschhorn: Yeah. Audiencia: Entra - NEW_NODE-> seguinte. Jason Hirschhorn: Entón, cal é que será igual? Audiencia: Vai igual actual. Jason Hirschhorn: Exactamente. E así o outro - o que máis necesitamos para actualizar? Audiencia: Asegúrese de que pasado é igual a cero. Jason Hirschhorn: se prev - por iso, se prev igual nulo. Audiencia: Isto significa que vai para facer a cabeza. Jason Hirschhorn: Isto significa que tornouse a cabeza. Entón o que facemos? Audiencia: Facemos cabeza coincide NEW_NODE. Jason Hirschhorn: Cabeza coincide NEW_NODE. E por cabeza aquí, non lista? Audiencia: Por cabeza é unha organización global variable, que é o punto de partida. Jason Hirschhorn: Sweet. Aceptar. E - Audiencia: Entón máis prev-> preto coincide NEW_NODE. E entón voltar true. Jason Hirschhorn: Onde montar final NEW_NODE? Audiencia: eu - Eu establecer que ao principio. Jason Hirschhorn: Entón o que liña? Audiencia: Tras a instrución if comprobando se é coñecido. Jason Hirschhorn: Aquí? Audiencia: Eu faría NEW_NODE-> n igual valor. Jason Hirschhorn: Parece bo. Probablemente ten sentido - non Debe saber o que estamos na lista porque estamos lidando só cunha lista. Así, unha declaración de función mellor para isto é só para se librar desa enteiramente e só introducir un valor na cabeza. Nós nin sequera ten que saber que lista que está dentro Pero vou perder la por agora e entón cambia-lo despois da actualización os diapositivas e código. Así que parece ser bo para agora. O valor - que pode facelo en liña? Se - o que facemos aquí, Noah. Audiencia: O valor é maior que curro-> n - Jason Hirschhorn: Como facer imos ao seguinte nodo? Audiencia: curro-> n é igual a NEW_NODE. Jason Hirschhorn: Entón n é que parte da estrutura? O enteiro. E NEW_NODE é un enlace a un nodo. Entón, o que parte do curro hai actualizar? Se non é n, entón o que é a outra parte? Noé, que é a outra parte. Audiencia: Oh, á beira. Jason Hirschhorn: Next, exactamente. Exactamente. A continuación é a correcta. E o que máis necesitamos para actualizar, Noah? Audiencia: Os punteiros. Jason Hirschhorn: Entón actualizamos actual. Audiencia: Prev-> seguinte. Jason Hirschhorn: Yeah. OK, imos facer unha pausa. Quen pode axudarnos aquí? Manu, o que temos que facer? Audiencia: Ten que definir el igual a curro-> seguinte. Pero facelo antes da liña anterior. Jason Hirschhorn: Aceptar. Algo máis? Akshar. Audiencia: Eu non creo que é destínase a cambiar curro-> seguinte. Eu creo que está destinado a facer iguais curro curro-> xunto a ir ao seguinte nodo. Jason Hirschhorn: So sorry, onde? En cal liña? Esta liña? Audiencia: Yeah. Fai curro igual curro-> seguinte. Jason Hirschhorn: Entón, iso é correcto porque a cadea é unha punteiro a un nodo. E queremos que el apunta ao seguinte nodo do que está a recibir actualmente apuntado. Curro si ten un lado. Pero, se fósemos actualizar curr.next, nós sería actualizar a nota real en si, non onde esta punteiro estaba apuntando. E sobre esta liña, con todo. Avi? Audiencia: Prev-> next igual curro. Jason Hirschhorn: Entón, de novo, se prev é un punteiro a un nodo, prev-> seguinte é o punteiro efectiva no nodo. Polo tanto, esta sería a actualización dun punteiro en un nó para curro. Non queremos para actualizar unha ligazón nun nodo. Queremos actualizar anterior. Entón, como imos facelo? Audiencia: Sería só prev. Jason Hirschhorn: Certo. Ant é unha ligazón a un nodo. Agora, estamos cambiando-o para un novo punteiro a un nodo. Aceptar Imos descender. Finalmente, esta última condición. Jeff, o que facemos aquí? Audiencia: O valor é igual a curro-> n. Jason Hirschhorn: Sentímolo. Oh meu Deus. O que? Valor == curro-> n. O que imos facer? Audiencia: Ía liberar o noso NEW_NODE, e entón voltar false. Jason Hirschhorn: Isto é o que temos escrito ata agora. Alguén ten algunha cousa a engadir antes de facer? Aceptar. Imos probar. Control poderá chegar ao final dunha función non baleiro. Rar, o que está a suceder? Audiencia: Debe poñer retorno certo fóra do loop while? Jason Hirschhorn: Eu non sei. Vostede me quere? Audiencia: Non importa. Non Jason Hirschhorn: Akshar? Audiencia: Coido que quería poñer retorno falso ao final do loop while. Jason Hirschhorn: Entón, onde queres que vaia? Audiencia: Como fóra do loop while. Entón, se saír do loop while que medios que xa chegou ao fin e nada aconteceu. Jason Hirschhorn: Aceptar. Entón, o que facemos aquí? Audiencia: Vostede volve teito alí tamén. Jason Hirschhorn: Oh, nós facelo en ambos os lugares? Audiencia: Yeah. Jason Hirschhorn: Aceptar. Imos? Oh meu Deus. Sinto moito. Pido desculpas para a pantalla. É unha especie de surtando sobre nós. Entón, escolle unha opción. Cero, por código, sae do programa. Un inserir algo. Imos introducir tres. A inserción non foi exitosa. Vou imprimir. Eu non teño nada. Aceptar. Talvez fose só un acaso. Insire un. Non exitosa. Aceptar. Imos percorrer GDB moi rapidamente para comprobar o que está pasando. Lembre gdb. / O nome do seu programa nos deixa en GDB. Isto é unha morea de tratar? O palpebrar? Probablemente. Pecha os ollos e tomar algunha profundidade respiracións se queda canso de ollar para el. Estou en GDB. Cal é o primeiro que fago en GDB? Temos que descubrir o que está pasando aquí. Imos ver. Temos seis minutos para a figura o que está pasando. Rompe principal. E entón o que fago? Carlos? Executar. Aceptar. Imos escoller unha opción. E o que facer N? Seguinte. É. Audiencia: Non mencionou - non dixo que a cabeza, que era iniciar con nulo ao principio. Pero eu penso que dixo que estaba ben. Jason Hirschhorn: Imos - imos ollar en GDB, e despois imos volver. Pero parece que xa ten algunhas ideas sobre o que está a suceder. Por iso, queremos introducir algo. Aceptar. Temos inserir. Por favor, introduza un int. Nós imos introducir tres. E entón eu estou nesa liña. Como fago para ir comezar a depuración función da inserción coñecido? Oh meu Deus. Isto é un monte. É que pirando moito? Audiencia: Ah, el morreu. Jason Hirschhorn: Eu só tirou-o para fora. Aceptar. Audiencia: Quizais sexa o o outro extremo do fío. Jason Hirschhorn: Guau. Así, a liña de fondo - o que dixo? Audiencia: Eu dixo a ironía de técnico dificultades nesta clase. Jason Hirschhorn: Eu sei. Se eu tivese o control sobre esta parte. [Inaudível] Isto soa moi ben. Por que vostedes non comezar a pensar sobre o que poderiamos ter feito de malo, e imos estar de volta en 90 segundos. Avica, vou preguntar a vostede como ir insert_node dentro depurá-lo. Entón é aquí que deixamos atrás. ¿Como entrar insert_node, Avica, para examinar o que está pasando? A orde GDB? Pausa non me levaría para dentro. A Marquise sabe? Audiencia: O que? Jason Hirschhorn: Cal comando GDB Eu uso para ir dentro desa función? Audiencia: Step? Jason Hirschhorn: Step vía S. Isto me leva cara a dentro. Aceptar. NEW_NODE mallocing algún espazo. Iso todo parece que vai. Imos examinar NEW_NODE. Ten algún enderezo de memoria. Imos comprobar - iso é todo correcto. Entón, todo aquí parece estar funcionando correctamente. Audiencia: Cal é a diferenza entre P e exhibición? Jason Hirschhorn: P está a imprimir. E así que está pregunta o que é o diferenza entre isto e isto? Neste caso, nada. Pero normalmente hai algunhas diferenzas. E ten que mirar na guía de GDB. Pero neste caso, nada. Nós tendemos a usar impresión, porén, porque Non necesitamos facer moito máis do que imprimir un único valor. Aceptar. Polo tanto, estamos na liña 80 do noso código, configuración nodo * curro igual a lista. Imos imprimir curro. El é igual a lista. Doce. Espera. El é igual a algo. Isto non parece certo. Alí imos nós. É porque en GDB, non si é a liña que está nel non executou aínda. Entón, ten que realmente escribir próximo para realizar a liña antes de ver os resultados. Entón aquí estamos nós. Nós só executou esta liña, anterior é igual a cero. Entón, de novo, se imprimir anterior non veremos nada raro. Pero se realmente realizar que liña, entón imos ver que a devandita liña de traballado. Polo tanto, temos curro. Estas son boas. Non? Agora estamos nesa liña aquí. Mentres curro non é igual a cero. Ben, o que fai curro iguais? Nós só vimos el igualou nulo. Imprimir lo. Vou imprimir lo de novo. Así é que, mentres lazo vai realizar? Audiencia: Non Jason Hirschhorn: Entón, cando eu escriba que liña, ve que pulou todo o camiño ata o fondo, voltar false. E entón nós estamos indo para voltar false e volver para o noso programa e finalmente, imprimir, como vimos, a inserción non foi exitosa. Entón, alguén ten algunha idea sobre o que o que necesitamos facer para solucionar isto? Vou esperar ata que eu vexa un par de mans levantadas. Non realizar este. Teña presente, este foi o primeiro que estabamos facendo. Non vou facer unha parella. Vou facer algúns. Por unha parella significa dous. Vou agardar por máis de dous. A primeira inserción, curro, por omisión é igual a cero. E este lazo só executa curro se non é nulo. Entón, como podo solucionar isto? Vexo tres mans. Vou agardar por máis de tres. Marcus, o que pensas? Audiencia: Ben, se precisa del para executar máis dunha vez, só se cambia-lo para un loop do-while. Jason Hirschhorn: Aceptar. Será que isto resolve o noso problema, entón? Audiencia: Neste caso, non debido a o feito de que a lista está baleira. Entón probablemente só precisa engadir unha declaración de que o loop logo ten que estar no extremo da da lista, en que punto pode só inserir-lo. Jason Hirschhorn: Eu gusto diso. Isto ten sentido. O circuíto sae - porque vai voltar false aquí. Entón, se o loop, entón estamos en Ao final da lista, ou que o inicio dunha lista, se non hai nada no , O que é o mesmo que o final. Entón, agora queremos introducir algo aquí. Entón, como parece que o código, Marcus? Audiencia: Se xa ten o nó malloced, podería simplemente dicir NEW_NODE-> next igual a nulo porque ten que ser ao final. Ou NEW_NODE-> next igual a nulo. Jason Hirschhorn: Aceptar. Sentímolo. NEW_NODE-> next igual a nulo porque estamos na final. Isto non poñer-lo dentro Como é que imos poñelas na lista? Correcto. Isto é só configure-lo igual a. Non coma nós, en realidade, poñelas na lista? O que está a apuntar cara o final da lista? Audiencia: Head. Jason Hirschhorn: Sentímolo? Audiencia: Cabeza está a apuntar ao final da lista. Jason Hirschhorn: Se non hai nada en a lista, a cabeza está a apuntar cara a final da lista. Entón, que vai traballar para a primeira inserción. E se hai un par cousas na lista? Do que nós non queremos para definir cabeza igual NEW_NODE. O que queremos facer alí? Si? Probablemente anterior. Será que funciona? Lembre que é só anterior un punteiro a un nodo. E anterior é unha variable local. Polo tanto, esta liña vai definir unha variable local, anterior, igual ou apuntando a este novo nodo. Isto realmente non vai poñelas na nosa lista, con todo. Como é que imos poñer-lo na nosa lista? Akchar? Audiencia: Eu creo que facer current-> seguinte. Jason Hirschhorn: Aceptar. curro-> seguinte. Entón, de novo, a única razón que nós estamos para abaixo aquí é, o que fai de corrente igual? Audiencia: Igual nulo. Jason Hirschhorn: E entón o que acontece se o facemos null-> next? O que se ve? Nós imos ter un fallo de segmento. Audiencia: Do curro igual nulo. Jason Hirschhorn: Isto é o mesmo como prev, con todo, porque non hai unha variable local que estamos definindo igual a este novo nodo. Imos volver á nosa imaxe de inserir algo. Digamos que está inserindo ao final da lista, polo que aquí. Temos un punteiro actual que é apuntando nulo e un punto anterior que está a apuntar cara 8. Entón o que necesitamos actualizar, Avi? Audiencia: Anterior-> next? Jason Hirschhorn: Anterior-> seguinte é o que queremos actualizar porque iso vai realmente inserir-lo no Ao final da lista. Aínda temos un erro, con todo, que imos correr en. ¿Que é iso erro? Si? Audiencia: Vai volver falsa neste caso? Jason Hirschhorn: Ah, e é Vai voltar false. Pero hai outro erro. Entón, imos ter para poñer en return true. Audiencia: O anterior aínda igual nula na parte superior da lista de? Jason Hirschhorn: aínda Entón anterior é igual a nulo ao principio. Entón, como podemos superar isto? Si? Audiencia: Eu creo que pode facer unha comprobación antes do loop while para ver se é unha lista baleira. Jason Hirschhorn: Aceptar. Entón imos aquí. Fai unha comprobación. Se - Audiencia: Entón, se a cabeza coincide é igual a cero. Jason Hirschhorn: Se a cabeza coincide é igual a null - que vai dicir se é unha lista baleira. Audiencia: E entón facer a cabeza é igual a novo. Jason Hirschhorn: Cabeza coincide NEW_NODE? E o que máis necesitamos facer? Audiencia: E entón voltar true. Jason Hirschhorn: Non é ben así. Estamos perdendo unha etapa. Audiencia: NEW_NODE seguinte ten que apuntar para null. Jason Hirschhorn: Exactamente, Alden. E entón podemos voltar true. Aceptar. Senón que é unha boa idea para facer as cousas ao final da lista, dereita? Todo ben. Aínda pode realmente comezar ao final da lista. Entón é este código ben se estamos na final da lista e hai algúns cousas na lista? Non? Porque aínda temos a idea de Marcus. Podemos saír deste ciclo, xa que estamos ao final da lista. Polo tanto, queremos aínda este código aquí abaixo? Audiencia: si. Jason Hirschhorn: Yeah. E o que necesitamos cambiar isto? Certo. Será que un bo son a todos ata agora? Alguén ten algunha - Rar, ten algo que engadir? Audiencia: Non Jason Hirschhorn: Aceptar. Entón, fixemos algúns cambios. Nós fixemos esta comprobación antes de nós entrou unha lista baleira. Entón, temos tido o coidado dunha lista baleira. E aquí nós tomamos o coidado de introducir algo ao final da lista. Entón, parece que esa toma loop while conta das cousas no medio, nalgún lugar da lista, se hai son cousas da lista. Aceptar. Imos realizar este programa de novo. Non exitosa. Audiencia: Non facelo. Jason Hirschhorn: Oh, Eu non fixen iso. Bo punto, Michael. Imos engadir un make conectados. Liña 87 hai un erro. Liña 87. Alden, esta foi a liña que me deu. O que hai de malo? Audiencia: Ten que ser como nulo. Jason Hirschhorn: Excelente. Exactamente. Debe ser nulo. Imos facer de novo. Compilar. Aceptar. Imos introducir tres. A inserción foi exitosa. Imos imprimir lo. Oh, se puidésemos comprobar. Pero nós non fixemos a imprimir función aínda. Imos entrar outra cousa. O que temos que entrar? Audiencia: Sete. Jason Hirschhorn: Seven? Audiencia: si. Jason Hirschhorn: Temos un fallo seg. Entón, temos un, pero claramente non pode estar dous. É 05:07. Así poderiamos depurar este por tres minutos. Pero eu vou deixar-nos aquí e seguir adiante para hash táboas. Pero, de novo, as respostas a este código Vou enviar correo-e para ti en breve. Estamos moi próximos a el. Eu altamente incentivos-lo a descubrir o que está pasando aquí e resolve-lo. Entón, eu vou enviar correo-e que este código como ben máis alá da solución - probablemente, a solución máis tarde. Primeiro este código. A outra cousa que quero facer antes de nós acabado é que non liberaron nada. Entón, quero amosar o que Valgrind parece. Se corrermos límites Valgrind no noso programa,. / activada. De novo, de acordo con esta corredías, nós debe realizar Valgrind con algún tipo de opción, neste caso - Check-baleirado = a foto. Entón imos escribir Valgrind - Check-baleirado = a foto. Polo tanto, este será executado Valgrind no noso programa. E agora o programa realmente funciona. Entón, imos executa-lo só como antes, poñer algo dentro Vou poñer en tres. Isto funciona. Eu non estou indo a tentar poñer en algo outra cousa, porque nós imos obter un falso seg nese caso. Entón, eu só vou saír. E agora ves aquí baleirar e resumo heap. Estas son as cousas boas que queira dar un ollo. Así, o resumo pila - di, en uso na saída - oito bytes nun bloque. Este bloque é o nó que malloced. Michael, dixo antes dun nodo é de oito picaduras xa que posúe o número enteiro eo punteiro. Entón, este é o noso nodo. E entón el di que usamos malloc sete veces e que liberou algo seis veces. Pero nós nunca chama libre, entón eu non teño idea do que iso está falando. Pero basta dicir que, cando o seu carreiras do programa, malloc está a ser chamado nalgúns outros lugares que nós Non se preocupe. Entón malloc probablemente foi chamado nalgúns lugares. Non se preocupe onde. Pero iso é realmente nós. Esta primeira liña é a xente. Deixamos este bloque. E podes ver que aquí no resumo baleirado. Aínda alcançável - oito bytes nun bloque. Isto significa que a memoria - que baleiraron esa memoria. Definitivamente perdida - algo está perdido para sempre. Xeralmente, non vai ver nada alí. Aínda accesible adoita onde vai ver as cousas, onde queira ollar para ver o que o código que debería liberar, pero se esqueceu de liberar. E entón, se este non foi o caso, se fixemos todo libre, podemos comprobar iso. Imos realizar o programa non poñer en calquera cousa. Vai ver aquí abaixo en uso na saída - cero bytes cero de bloques. Isto significa que non tiña máis nada cando este programa saíu. Entón, antes de virar pset6, executa Valgrind e asegúrese de que non ten calquera perdas de memoria no seu programa. Se ten algunha dúbida con Valgrind, sexa a vontade para chegar. Pero isto é como usalo. Moi simple - vexa se ter en uso na saída - calquera bytes en todos os bloques. Entón nós estabamos traballando no nó de inserción. Eu tiña dúas outras funcións aquí - imprimir nós e nós libres. De novo, estas son funcións que son vai ser bo para ti practicar porque eles van axudar non só con estes exercicios de mostra, pero tamén sobre o conxunto de problemas. Eles mapeiam en ben de preto para as cousas vai ter que facer no conxunto de problemas. Pero quero que seguro tocamos en todo. E táboas de hash tamén son cruciais para o que estamos facendo na sección deste semana - ou no conxunto problema. Entón, nós estamos indo a rematar a sección falando de táboas de hash. Se notar que fixen un mesiña hash. Isto non é o que estamos a falar sobre, con todo. Estamos falando dun diferente tipo de táboas de hash. E no seu núcleo, unha táboa hash non é máis que unha disposición unha función hash. Imos falar un pouco só para asegurarse de todo o mundo entende o que é un función hash é. E eu estou te dicindo agora que é nada máis que dúas cousas - unha matriz e unha función de hash. E aquí están os pasos a través de que esta opera. Non é a nosa matriz. Non é a nosa función. En particular, as funcións de hash ten facer un par de cousas con iso. Vou falar especificamente sobre este conxunto de problemas. El probablemente vai tomar en un cadea. E o que é o que vai volver? Que tipo de datos? Alden? A súa función hash retornar? Un enteiro. Entón é iso que o hash táboa consiste en - unha mesa en forma de abano e unha función de hash. Como funciona? Funciona en tres etapas. Nós darlle unha chave. Neste caso, nós imos dar-lle unha corda. Chamamos a función hash por unha etapa na clave e temos un valor. Especificamente, imos dicir obtemos un número enteiro. Ese número enteiro, non son moi específicos límites ao número enteiro que pode ser. Neste exemplo, a matriz é de tamaño tres. Entón, o que os números poden ser enteiro. Cal é o intervalo de valores válidos para que enteiro, o tipo de retorno dese de hash función? Cero, un e dous. O punto de partida da función hash é descubrir o lugar na matriz onde a nosa clave está indo. Hai só tres posibles lugares aquí - cero, un ou dous. Polo tanto, esta función mellor retorno cero, un ou dous. Algúns indice válido neste array. E, a continuación, dependendo de onde el retorna, podes ver que hai disposición aberta entre parénteses o valor. Isto é onde poñemos a clave. Por iso, xogar a cabaza, sairmos cero. No conxunto do soporte 0, poñemos cabaza. Xogamos en gatos, saímos un. Poñemos nun gato. Poñemos en araña. Saímos dúas. Poñemos araña en soporte disposición dous. Sería tan bo se funcionou así. Pero, desgraciadamente, como veremos, é un pouco máis complicado. Antes de chegar alí, as preguntas sobre o básico set-up dunha táboa hash? Esta é unha imaxe de exactamente o que chamou a bordo. Pero desde que o deseñou o cadro, eu Non vou entrar en lo aínda máis. Esencialmente claves, a caixa negra máxica - ou, neste caso, a caixa azul - dun función hash poñelos baldes. E, neste exemplo, estamos non poñer o nome. Estamos poñendo o teléfono asociado número do nome no balde. Pero podería moi ben só poñer o nome no balde. Este é só un retrato do que trazamos no taboleiro. Temos potenciais trampas, con todo. E hai dous en particular diapositivas que quero pasar por riba. A primeira é sobre unha función hash. Entón eu fixen a pregunta, o que fai unha boa función hash? Dou dúas respostas. O primeiro é que non é determinista. No contexto das funcións hash, o que significa isto? Si? Audiencia: Atopará o índice en tempo constante? Jason Hirschhorn: Isto non é o que ela significa. Pero iso é un bo palpite. Alguén máis ten un palpite para que isto significa? Que unha boa función de hash é determinista? Annie? Audiencia: É unha clave só se pode mapeado a un lugar na táboa de hash. Jason Hirschhorn: Isto é exactamente correcto. Cada vez que poñer na cabaza, el sempre volve cero. Se pór en cabaza ea súa mestura función devolve cero, pero ten un probabilidade de volver algo outra cousa maior que cero - quizais por iso, ás veces, pode voltar un ou dúas veces - que non é unha boa función hash. Está absolutamente certo. A súa función hash debe devolver o mesmo número enteiro exacto, neste caso, a a mesma secuencia exacta. Quizais el retorna o mesmo número enteiro exacto para a mesma secuencia exacta independentemente da capitalización. Pero, nese caso, aínda é determinista, pois moitas cousas son mapeados ao mesmo valor. Iso é bo. Mentres hai só unha saída para unha dada entrada. Aceptar. A segunda cousa é que retorna índices válidos. Trouxo-se que antes. Esta función hash - oh boy - unha función de hash debe voltar índices válidos. Entón diga - imos voltar a este exemplo. A miña función hash conta ata as letras da palabra. Esa é a función hash. E volve este número enteiro. Entón, se eu teño a palabra A, é vai volver un. E vai poñer un aquí. E se eu poñer a palabra morcego? Volverá tres. Onde o morcego ir? Non serve. Pero el que ir a algún lugar. Esta é a miña táboa hash Despois de todo, e todo ten que ir a algún lugar. Entón, a onde debe ir morcego? Calquera pensamentos? Adiviña? Bos historiadores? Audiencia: Cero. Jason Hirschhorn: Porque a cero? Audiencia: Por tres módulo tres é igual a cero? Jason Hirschhorn: Three módulo de tres é igual a cero. Isto é un gran palpite, e iso é correcto. Polo tanto, neste caso debería probablemente ir a cero. Así, unha boa forma de garantir que este hash función só retorna índices válidos é Módulo para isto por o tamaño da táboa. Se queres que este modulo retorno tres, está sempre indo para obter algo entre cero, un e dous. E se isto sempre regresa sete, e sempre modulo por tres, está sempre se ve o mesmo. Entón, aínda é determinística se módulo. Pero iso vai garantir que nunca conseguir algo - unha industria válido. Xeralmente, este módulo debe acontecer dentro da súa función de hash. Así que non se preocupe con iso. Só pode garantir que este é un indice válido. Calquera dúbida sobre este trampa potencial? Aceptar. E alí imos nós. Seguinte trampa potencial, e este é un dos grandes. E se dúas chaves mapa para o mesmo valor de? Polo tanto, hai dúas formas de tratar con isto. O primeiro chámase lineal enquisa, o que eu son non vai pasar por riba. Pero ten que estar familiarizado coa forma que funciona e que é. A segunda eu vou pasar por riba porque esta é a única que moitos persoas probablemente vai acabar decidindo para usar no seu conxunto de problemas. Por suposto, non precisa. Pero, para o conxunto de problemas, moitas persoas tenden a optar por crear unha táboa hash con fío separado para aplicar seu dicionario. Entón, nós estamos indo ir sobre o que significa isto para crear unha táboa hash coa encadeamento separado. Entón eu coloque na cabaza. El retorna cero. E eu coloque cabaza aquí. Entón eu coloque en - o que é outra cousa Halloween-temático? Audiencia: Candy. Jason Hirschhorn: doces! Isto é un gran home. Engada en doces, e doces tamén me dá cero. O que fago? Algunha idea? Porque toda a sorte de coñecer o fío separado é. Entón, algunha idea do que facer? É. Audiencia: Poñer a corda de feito, na táboa de hash. Jason Hirschhorn: Entón nós imos deseñar a boa idea por aquí. Aceptar. Audiencia: Teña o hashtable [Inaudível] o punteiro que apunta a o inicio dunha lista. E entón, cabaza ser o primeiro valor nesa lista conexionada e doces ser o segundo valor nesa lista encadeada. Jason Hirschhorn: Aceptar. Marcus, que foi excelente. Vou romper ese abaixo. Marcus di non substituír cabaza. Isto sería malo. Non coloque doces noutro lugar. Imos poñer-los a cero. Pero estamos indo para xestionar poñelos cero por creación dunha lista de cero. E imos crear unha lista de todo o que mapeada a cero. E a mellor forma que aprenden a crear unha lista que pode aumentar e diminuír dinámica non está dentro outra matriz. Polo tanto, non un array multi-dimensional. Pero só crear unha lista ligada. Entón, o que el propuxo - Eu estou indo a obter un novo - é crear unha matriz con punteiros, unha matriz de punteiros. Aceptar. Calquera idea ou suxestión que o tipo desta punteiros debe ser? Marcus? Audiencia: Punteiros para - Jason Hirschhorn: Por ti dixo unha lista ligada, por iso - Audiencia: punteiros do nodo? Jason Hirschhorn: punteiros no. Se as cousas na nosa conectado lista son os nós, entón eles debe ser punteiros do nodo. E o que eles igual inicialmente? Audiencia: Null. Jason Hirschhorn: Null. Polo tanto, non é a nosa cousa baleira. Cabaza retorna cero. O que imos facer? Camiño comigo a través dela? En realidade, Marcus xa me deu. Alguén me atravesalo-la. Que facemos cando - este é moi parecido o que nós estabamos facendo. Avi. Audiencia: Vou dar un palpite. Entón, cando comeza doces. Jason Hirschhorn: Yeah. Así, temos de cabaza. Imos buscar o noso primeiro. Temos cabaza. Audiencia: Aceptar. Cabaza retorna cero. Entón poñelas niso. Ou, en realidade, poñelas na lista encadeada. Jason Hirschhorn: Como é que nós poñelas na lista ligada? Audiencia: Oh, a sintaxe real? Jason Hirschhorn: Só ten que andar - dicir máis. O que imos facer? Audiencia: Acaba de inserir el como o primeiro nodo. Jason Hirschhorn: Aceptar. Entón, nós temos o noso nodo, cabaza. E agora como fago para inserir-lo? Audiencia: Vostede atribúe lo para o punteiro. Jason Hirschhorn: Cal punteiro? Audiencia: O punteiro do cero. Jason Hirschhorn: Entón, onde fai ese punto? Audiencia: Para nulo agora. Jason Hirschhorn: Ben, está a apuntar cara null. Pero eu estou poñendo en cabaza. Entón, onde debe apuntar? Audiencia: Para cabaza. Jason Hirschhorn: Para cabaza. Exactamente. Entón, iso apunta a cabaza. E onde é que este punteiro ao momento de cabaza? Para Audiencia: Null. Jason Hirschhorn: Para nulo. Exactamente. Entón, nós só inserido algo na lista encadeada. Nós só escribín este código para facelo. Case que case conseguiu totalmente rachado. Agora imos introducir doces. Noso doces tamén vai a cero. Entón, o que imos facer con doces? Audiencia: Depende ou Non estamos intentando resolver iso. Jason Hirschhorn: Isto é exactamente correcto. Depende de se ou non Estamos intentando resolver iso. Imos supor que non estamos indo a clasificalos lo. Audiencia: Ben, entón, como discutir antes, é máis simple só para poñelas ao comezo para que o punteiro de cero puntos a doces. Jason Hirschhorn: Aceptar. Espere un pouco. Déixeme crear doces aquí. Polo tanto, este punteiro - Audiencia: Si, debe agora estar apuntando para doces. Entón, o punteiro de punto doce para cabaza. Jason Hirschhorn: Así? E dicir que ten outro cousa para mapear a cero? Audiencia: Ben, só facer o mesmo? Jason Hirschhorn: Fai o mesmo. Polo tanto, neste caso, se non o facemos quere mantelo ordenados soa moi sinxelo. Tomamos o punteiro no indice dada pola nosa función hash. Temos que apuntan ao noso novo nodo. E entón, o que quere que estaba apuntando previamente - neste caso, nulo, o segundo caso cabaza - que, sexa o que está a apuntar cara anteriormente, engadir ao seguinte de o noso novo nodo. Estamos introducindo algo no inicio. En realidade, este é moito máis simple do que tentando manter a lista ordenada. Pero, de novo, a investigación será máis complicado aquí. Sempre teremos que ir ata o final. Aceptar. Calquera dúbida sobre o encadeamento separado? Como funciona isto? Por favor, pregunta-los agora. Eu realmente quero estar seguro de que todo entender iso antes de cabeza para fóra. Audiencia: Por que poña a cabaza e doces na mesma parte da táboa de hash? Jason Hirschhorn: Boa pregunta. Por que poñer-los na mesma parte da táboa de hash? Ben, neste caso, a nosa función de hash retorna cero para ambos. Entón, eles teñen que ir ao indice de cero porque é onde nós estamos indo buscalos se algunha vez quere procura-los. Unha vez máis, cunha visión lineal sondaxe non ía poñer-los a cero. Pero, na visión da cadea separada, imos poñer-los a cero e, a continuación, crear unha lista fóra de cero. E nós non queremos substituír cabaza simplemente por iso, porque entón nós asumir que cabaza foi nunca inserido. Se nós só manter unha cousa en local que sería malo. Entón, non habería posibilidade de nós nunca - se algunha vez tivo un dobre, entón nós sería só borrar o seu valor inicial. Entón é por iso que facemos esta visión. Ou é por iso que nós escoller - pero de novo, escolleu o achegamento de fío separado, que hai moitas outras abordaxes pódese escoller. Isto responde a súa pregunta? Aceptar. Carlos. Sondaxe lineal envolvería - se atopamos unha colisión en cero, nós ficaría no seguinte punto a ver se era aberto e poñelas alí. E entón nós miramos a próxima deporte e ver se estaba aberto e poñelas alí. Así, atopamos o seguinte dispoñible lugar aberto e poñelas alí. Algunha pregunta? Si, Avi. Audiencia: No seguimento diso, o que quere dicir con preto punto? Na táboa de hash ou nunha lista vinculada. Jason Hirschhorn: Para lineal programación, hai listas ligadas. O seguinte punto na táboa de hash. Audiencia: Aceptar. Así, a táboa hash sería iniciar a dimensión - como o número de cadeas que estaba inserindo? Jason Hirschhorn: Faria quere que sexa realmente grande. Si Aquí está unha foto do que nós acaba de deseñar o cadro. Unha vez máis, temos unha colisión ben aquí. en 152. E vai ver que creamos unha lista ligada fóra del. Unha vez máis, a táboa hash encadeamento separado visión non é o que ten que tomar para definir problemas seis, pero é un que unha morea de os alumnos tenden a tomar. Entón, con esta nota, imos falar brevemente antes de cabeza para fóra sobre o problema seis, e entón eu vou compartir unha historia con vostede. Temos tres minutos. Problema definir seis. Ten catro funcións - carga, comprobar o tamaño ea descarga. Carga - ben, imos sobre a carga agora. Trazamos carga na tarxeta. E nós nin sequera comezou a codificación de unha chea de inserción nunha lista encadeada. Así, a carga non é moito máis do que o que acabamos facendo. Check é cando ten algo cargado. É o mesmo proceso como este. As mesmas dúas primeiras partes onde xoga algo na función de hash e conseguir o seu valor. Pero agora non imos inserir-lo. Agora nós estamos mirando para el. Teño código de exemplo escrito por atopar algo nunha lista encadeada. Estimula-vos a practicar iso. Pero intuitivamente atopar algo é moi semellante ao da inserción de algo. De feito, fixo un deseño de atopar algo nunha lista encadeada, movendo-se totalmente ata que chegou ao final. E se chegou ao final e non podía atopalo, el non está alí. Entón, iso é cheque, esencialmente. A continuación é o tamaño. Imos saltar tamaño. Finalmente descargar. Unload é unha que non teñen atraído na tarxeta ou codificados aínda. Pero eu encouraged-lo a tentar codifica-lo na nosa mostra exemplo lista encadeada. Pero descargar intuitivamente é semellante ao libre - ou quero dicir é semellante para comprobar. Excepto agora cada vez que vai a través, non está simplemente comprobando a mira se tes o valor alí. Pero está tomando este nodo e liberando-o, esencialmente. Iso é o que descargar lle pide para facer. Todo gratis vostede malloced. Entón, está pasando por toda a lista unha vez máis, pasando por todo o hash mesa de novo. Esta vez, Desactive a ver que está aí. Só liberar o que está aí. E, finalmente, o tamaño. Tamaño debe ser aplicada. Se non aplicar o tamaño - Vou dicir así. Se non aplicar o tamaño exactamente unha liña de código, incluíndo a volver declaración, que é facendo tamaño incorrectamente. Polo tanto, asegúrese de que o tamaño, para o proxecto completo puntos, está facendo isto en exactamente un liña de código, incluíndo a instrución de retorno. E non aparcar aínda, Akchar. Castor Eager. Quería agradecer a vostedes para vir a sección. Teña un feliz Día das meiga. Este é o meu traxe. Eu vou estar a levar posto este xoves se eu velo en horario de oficina. E se está curioso para saber un pouco máis fondo canto a este traxe, sentir libre para comprobar a sección 2011 para unha historia sobre iso que eu son vestindo a fantasía de cabaza. E é unha historia triste. Polo tanto, comproba que tes algúns tecidos próximos. Pero por que, se ten algunha preguntas que eu vou ir por aquí fóra despois de sección. Boa sorte no conxunto de problemas seis. E como sempre, se ten calquera preguntas, deixe-me saber.