[Powered by Google Translate] [Paso a paso - conxunto de problemas 5]
[Zamyla Chan - Harvard University]
[Esta é CS50. - CS50.TV]
>> Todo ben. Ola, todos, e ben benvida ao Paso a paso 5.
>> Pset5 e erros de ortografía, en que imos estar facendo un corrector ortográfico.
Corretores ortográficos son moi importantes.
Iso xa aconteceu contigo?
Vostede traballa moito acumulan nun papel para un enfrontamento
e despois aínda acabar recibindo un rade brillo moi parecido cun D ou = D
e todo porque é o spoiler en liverwurst a palabra balea de ancho.
Si, revisión súas pemento é unha cuestión de, a impotencia máxima.
Este é un problema que afecta viris, os alumnos viris.
Me dixeron unha vez polo meu torturador grao Sith que eu nunca ía entrar nun bo compañeiro.
E iso é todo o que eu sempre quixo, iso é todo o que calquera neno quere na miña idade,
só para entrar nun bo compañeiro.
E non só calquera compañeiro. Non Eu quería ir a un compañeiro do Marfil Legal.
Entón, se eu non mellorar, aínda que serían os meus soños de ir a Harvard,
Jale, a prisión ou - vostede sabe, en prisión, Nova Jersey.
Entón, eu mesmo teño un corrector ortográfico.
Este é un fragmento pequeno de un dos meus artistas favoritos palabra falada, Taylor Mali.
En calquera caso, como el di, a importancia de ter un corrector ortográfico é moi importante.
>> Entón, benvido ao Paso a paso 5, en que imos estar fala de pset5: Erros de ortografía,
en que nós estamos facendo o noso propio corrector ortográfico.
A caixa de ferramentas para esta semana, o código de distribución, será importante ollar para
só para entender as diferentes funcións que o seu dicionario vai ter.
En realidade, estamos indo a ter varios ficheiros. C que, xuntos, forman a nosa pset.
E así mirando a través de diferentes aspectos, aínda que non estamos realmente edición
un dos arquivos, speller.c, sabendo como funciona con relación a dictionary.c,
que iremos escribir, vai ser moi importante.
A especificación pset tamén contén unha serie de información útil
en termos de cousas que pode asumir, regras e cousas así,
que non deixe de ler a especificación pset coidadosamente para suxestións.
E cando está en dúbida dunha regra ou algo así, entón sempre consultar a especificación pset
ou discutir.
Este pset vai dependen fortemente de punteiros,
por iso queremos estar seguro de que entendemos a diferenza entre estrelas engadir
diante do nome do punteiro e ampersands, como para liberalos, etc
Entón, ser un mestre de punteiros vai ser moi útil neste conxunto de problemas.
Nós imos ollar para as listas ligadas un pouco máis,
onde temos elementos que chamamos nós, que posúen tanto un valor, así como un enlace
para o próximo nó, e así, esencialmente, ligando elementos diferentes un despois do outro.
Existen algunhas opcións diferentes de implementar o seu dicionario real.
Nós imos ollar para dous métodos principais, o que é táboas de hash e entón intenta.
En ambos os, implica algún tipo de noción dunha lista ligada
onde teñen elementos conectados un ao outro.
E así imos ollar sobre como pode ser capaz de operar en torno a listas ligadas,
crealas, navegar en termos de como, por exemplo, inserir un nó que
ou libre de todos os nós, ben.
En termos de nós liberadora, que é realmente importante
que sempre que a memoria malloc, despois nos liberar.
Entón, nós queremos estar seguro de que ningún punteiro vai unfreed, que non temos ningunha derrames de memoria.
Nós imos presentar unha ferramenta chamada Valgrind que executa o programa
e comprobar toda a memoria que alocou é entón liberado.
O seu pset só é completa cando funciona e ten a funcionalidade completa,
pero tamén, Valgrind lle di que non atopou ningún escape de memoria.
Finalmente, a este pset, realmente quero salientar -
Quero dicir, como de costume, eu son sempre un defensor do uso de papel e pluma para os seus conxuntos de problemas,
pero a este, eu creo que pluma e papel vai ser especialmente importante
cando quere ser deseño frechas para as cousas e entender como as cousas funcionan.
Entón, en definitiva tentar usar pluma e papel para deseñar as cousas antes de que comece a codificación
porque podería estar un pouco confuso.
>> En primeiro lugar, imos entrar en listas ligadas un pouco.
Listas ligadas consisten de nós, onde cada nodo ten un valor asociado a ela,
, Así como un enlace ao seguinte nodo tras el.
Un par de cousas importantes coas listas ligadas son de que necesitamos nos lembrar
onde o noso primeiro nodo é, a continuación, unha vez que sabemos que o primeiro en se,
Desta forma, podemos acceder ao nodo que os primeiros puntos de nó para
e, a continuación, a outra despois diso e un despois diso.
E entón o último elemento na súa lista conexionada e punteiro que no
sempre vai apuntar a NULL.
Cando un nodo puntos para NULL, entón vostede sabe que chegou ao final da lista,
que ese nodo é o último, que non hai nada despois diso.
Aquí neste esquema, ve que as frechas son os punteiros,
ea sección de azul é onde o valor é almacenado,
e, a continuación, a caixa vermella co punteiro para el é punteiro do nodo
apuntando para o próximo nó tras el.
E así que ve aquí, o nó D ía apuntar para NULL porque é o último elemento da lista.
>> Imos ver como podemos definir unha estrutura para un nó.
E xa que queremos ter varios nós,
iso vai converterse nun typedef struct
en que nós imos ter varias instancias diferentes de nós.
E, así, define-lo como un novo tipo de datos.
Aquí temos un nó typedef struct.
Neste exemplo, estamos a tratar con nós enteiros,
por iso temos un valor enteiro chamado e despois temos outro punteiro,
e, neste caso, é un punteiro para un nó, por iso temos un nó struct * chamada seguinte.
E entón nós estamos chamando este nodo cousa toda.
Asegúrese de que siga esta sintaxe.
Teña en conta que o no está realmente enriba referenciado, así como a continuación das claves.
Entón, para manter o control de onde o meu primeiro nodo está na lista vinculada,
entón ter un punteiro no chamado cabeza, e eu malloc espazo suficiente para o tamaño dun nodo.
Teña en conta, sen embargo, que a cabeza é realmente un punteiro nó en oposición a un nodo propiamente dito.
Así, a cabeza, en realidade, non contén ningún valor,
el só apunta a que o primeiro nó na miña lista conexionada e.
>> Para ter unha noción mellor de listas ligadas, pois é moi importante
para acompañar a certeza de que manter a cadea,
Eu gusto de pensar niso como persoas nunha liña de man,
onde cada persoa está de mans dadas co próximo.
Vostede non pode ver neste deseño, pero, basicamente, están apuntando para a seguinte persoa
que está na súa cadea.
E por iso, se quere percorrer unha lista ligada onde esas persoas -
Imaxina todas esas persoas teñen valores asociados a eles
e tamén apuntar á seguinte persoa na liña -
se quere percorrer a lista ligada, por exemplo, para editar os valores
ou buscar por un valor ou algo así,
entón vai querer ter un punteiro para a persoa específica.
Entón, nós imos ter un punteiro de datos no tipo.
Para este exemplo, imos chamalo cursor.
Outra forma común de nomear este sería iterador ou algo parecido
porque está interactuando sobre e realmente mover o nodo que está apuntando.
Iso aquí vai ser o noso cursor.
O noso primeiro cursor apuntar para o primeiro elemento na nosa lista.
E entón o que queremos facer é que sería basicamente ser continuar o cursor,
movéndose de lado a lado.
Neste caso, queremos mover para o próximo elemento da lista.
Con matrices, o que nós facemos é só diría que aumentar o índice de 1.
Neste caso, o que necesitamos facer é realmente atopar o que esta persoa persoa actual está a apuntar,
e que vai ser o seguinte valor.
Entón, se o cursor é só un punteiro no, entón o que queremos facer
é que queremos chegar ao valor que o cursor está a apuntar.
Queremos chegar a ese nó e, a continuación, unha vez que estamos nese nó, atopar onde está a apuntar.
Para chegar ao nodo real que o cursor está a apuntar,
Normalmente indican-lo (cursor *).
Que lle daría o no real que o cursor está a apuntar.
E despois diso, o que queremos facer é que queremos para acceder
calquera que sexa o valor próximo ao nó é.
Para iso, para acceder os valores dentro da estructura, temos operador punto.
Entón sería (cursor *). Seguinte.
Pero iso é un pouco confuso en canto ao que os soportes arredor do cursor *,
e así imos substituír esa declaración enteira con cursor->.
Este é un guión e un sinal máis do que, polo que facendo unha frecha.
cursor-> seguinte.
Que realmente vai che dar o no que os puntos cursor. Este valor é do seguinte.
Entón, en vez de ter a estrela eo punto, está substituíndo iso cunha frecha.
Teña moito coidado para asegurarse de que Vostede tente utilizar esa sintaxe.
>> Agora que temos o noso cursor, se quere acceder ao valor,
antes, tivemos cursor-> seguinte,
pero para acceder ao valor no no que o cursor está a apuntar, nós simplemente dicir
node>-valor.
De alí, é o tipo de datos que definimos os valores e os nós a seren.
Se é un nodo int e cursor-> valor é só vai ser un enteiro.
Entón, podemos facer operacións en que comprobar igualdades, asignar valores diferentes, etc
Entón o que quere facer, se quere mover o cursor á seguinte persoa,
realmente cambiar o valor do cursor.
Dende cursor é un punteiro no, vostede cambiar o enderezo do punteiro real
ao enderezo do próximo nó na súa lista.
Este é só un código, onde podes interactuar.
Onde eu teño o comentario facer algo,
que é onde está indo probablemente para acceder o valor
ou facer algo que ver con ese nó específico.
Para inicia-lo fóra, eu digo que o meu cursor inicialmente
vai para apuntar para o primeiro elemento na lista encadeada.
E así alí na fronte, eu define-lo como o xefe do nodo.
>> Como mencionei antes, liberando é realmente importante.
Quere estar seguro de que liberar todos os elementos da lista unha vez que rematou con el.
Cando non ten que facer referencia a calquera destes punteiros máis,
quere ter seguro de que liberar todos os punteiros.
Pero quere ter moito coidado aquí que quere evitar calquera fuga de memoria.
Se unha persoa libre prematuramente, despois de todos os punteiros que os puntos de nó para
van ser perdidos.
Volvendo ao exemplo persoa para facelo un pouco máis altas apostas,
imos ter estas persoas, só que neste caso están paira sobre un lago con un monstro.
Queremos estar seguro de que cada vez que liberar, non perdemos
e deixar de ir todos os nós antes de que realmente os liberou.
Por exemplo, se fose simplemente conectar de balde sobre este cara aquí,
entón, sería liberado, pero despois todos eses caras, entón, ser perdido
e que iría durmir e caer.
Entón, nós queremos estar seguro de que en vez diso, queremos manter un vínculo co resto.
A nosa cabeza punteiro, que apunta para o primeiro elemento da lista.
É como unha especie de corda de ancoraxe primeira persoa.
O que pode querer facer cando liberar unha lista ter -
Se queres liberar o primeiro elemento primeiro, entón vostede pode ter un punteiro temporal
que apunta a que o primeiro elemento é.
Entón tes o punteiro temporal apuntando aquí.
Desta forma, temos un soto do primeiro nodo.
E entón, xa que sabemos que o primeiro en vai ser liberada,
entón podemos pasar esta corda, esa referencia, a nosa cabeza,
para realmente apuntar para o que quere que o primeiro está a apuntar.
Polo tanto, esta cabeza realmente apunta para o segundo elemento agora.
Agora estamos autorizados a liberar o que está almacenado na temperatura,
e así podemos borrar que sen el poñer en perigo os outros nós na nosa lista.
Outra forma que podería facer isto podería ser
cada vez que acaba de liberar o último elemento da lista
porque son a garantía de non ser apuntado para calquera cousa.
Entón, vostede podería simplemente liberar este, entón libre este, a continuación, un agasallo gratuíto.
Isto definitivamente funciona, pero é un pouco máis lento, porque pola natureza das listas ligadas,
non podemos simplemente ir inmediatamente para a última.
Debemos percorrer cada elemento da lista encadeada
e comproba que se está a apuntar cara NULL, comprobar cada vez,
e, a continuación, unha vez que chegar ao final, entón libre diso.
Se fose facer ese proceso, sería realmente comprobando aquí,
comprobando aquí, a continuación, comprobando aquí, liberando-o,
a continuación, volver, comprobando aquí, alomenos aquí, liberando-o,
comprobando aquí, e logo liberalo la.
Isto leva un pouco máis tempo. Si
>> [Alumno] Sería posíbel facer unha lista ligada que almacena un punteiro de saída para o fin?
Que ía ser posible.
Para repetir a pregunta, é posible ter unha estrutura de lista ligada
de tal forma que ten un punteiro que apunta para o fin da lista ligada?
Eu diría que é posible, e cada vez que introduza algo na súa lista ligada
que tería que actualizar este punteiro e cousas así.
Vostede tería unha cola * no, por exemplo.
Pero cando se está aplicando este recurso, ten que pensar no trade-offs,
gusto de cantas veces eu vou ser iteração sobre iso,
quão difícil é que vai ser a de manter o control da cola, así como a cabeza
así como a miña iterador, e cousas así.
Será que -? >> [Estudante] Yeah.
É posible, pero en termos de decisións de proxecto, ten que pesar as opcións.
>> Aquí está un esqueleto de código que lle permitiría liberar cada elemento nunha lista ligada.
Unha vez máis, dende que eu estou iterando unha lista ligada, eu vou querer ter algún tipo de cursor
ou iterador.
Estamos repetindo ata que o cursor está NULL.
Non quere repetir cando o cursor é NULL
porque iso significa que non hai nada na lista.
Entón aquí fago un nó temporal *
apuntando para o que eu estou pensando é o primeiro da miña lista,
e despois eu paso o meu cursor cara adiante e despois un libre que tiña no almacenamento temporal.
>> Agora chegamos ao inserir en listas ligadas.
Eu teño tres nós na miña lista encadeada, e imos co caso sinxelo
onde queremos inserir outro no ao final da lista ligada.
Para iso, todo o que quere facer é que sería atravesar
para atopar onde o fin actual da lista ligada é, entón calquera nodo apunta a NULL -
iso é un agasallo -
e despois din que, en realidade, este non vai ser o último nó;
estamos, en realidade, vai ter outro.
Entón teriamos este punto unha corrente de todo o que está inserindo.
Entón, agora esta persoa vermello aquí se fai o último nó na lista ligada.
E así a característica do último nodo na lista vinculada é que apunta a NULL.
Entón, o que teriamos que facer é definir esa cara punteiro vermello para NULL. Alí.
>> Pero o que se quería introducir un nó entre a segunda e terceira?
Que non é tan sinxelo, porque queremos estar seguro de
que non deixe ir de calquera nodo na lista ligada.
O que temos que facer é estar seguro de que nós ancorar cada un.
Por exemplo, imos chamar iso de un segundo.
Se dixo que o segundo apunta agora a esta nova
e acaba de facer un punteiro alí, entón, que resultaría nun cara sendo perdida
porque non hai ningunha conexión con el.
En vez diso - Vou chamar iso de novo. Sentímolo miñas habilidades artísticas.
Sabemos que non podemos simplemente chamar directamente dous para o novo.
Temos que asegurarse de que soster a última.
O que pode querer facer é ter un punteiro temporal
para o elemento que vai ser anexado en.
Entón temos un punteiro temporal alí.
Desde que sabemos que este terceiro está sometido,
2 pode agora chamar a nosa nova.
E se este cara nova vermello vai ser entre 2 e 3,
Entón o que é punteiro que cara vai apuntar? >> [Alumno] Temp.
Temp. Si
Entón próximo valor este cara vermella que vai ser temporal.
Cando está inserindo en listas ligadas, vimos que podiamos
facilmente engadir algo ao final, creando unha matriz temporal,
ou se quería engadir algo para o medio da nosa matriz,
a continuación, sería preciso un pouco máis de andar por aí.
Se queres, por exemplo, ten unha lista ordenada vinculado,
entón tes que tipo de pesar os custos e os beneficios que
porque se quere ter un array ordenado, o que significa que cada vez que insira-lo,
que vai levar un pouco máis.
Con todo, se quere, máis tarde, como veremos, queremos,
busca a través dunha lista ligada, entón pode ser máis doado se sabe que todo está en orde.
Entón podes querer pesar os custos e beneficios que.
>> Outra forma de introducir nunha lista ligada é introducir no inicio dunha lista.
Se traçarmos a nosa referencia aquí - esta é a nosa cabeza -
e despois que esas persoas ligadas a el,
e, a continuación, temos un novo nodo a ser inserido no inicio,
a continuación, o que podería queremos facer?
O que sería malo con só dicindo que quero obrigar o vermello ao azul,
porque ese é o primeiro?
O que sucedería aquí?
Todos estes tres se perdese.
Entón nós non queremos facelo.
Unha vez máis, nós aprenden que temos que ter algún tipo de punteiro temporal.
Imos optar por ter un punto temporal para este cara.
Entón, podemos ter o punto de un azul para a temporal
e, a continuación, o punto vermello ao azul.
A razón pola que eu estou usando o pobo aquí é porque realmente queremos ver
seguro coas persoas e estar seguro de que temos unha ligazón a eles
antes de deixar de ir a outra man, ou algo así.
>> Agora que temos un sentido de listas ligadas - como podemos crear unha lista encadeada
e crear as estruturas para que consiste na definición de tipo para un nodo
e, a continuación, asegurándose de que temos un punteiro para a cabeza da lista ligada -
Unha vez que temos iso e sabemos como atravesar unha matriz,
acceder varios elementos, sabemos como inserir e sabemos como liberalos,
entón podemos entrar en erros ortográficos.
Como de costume, temos unha sección de preguntas que se usou para operar con listas ligadas
e estruturas diferentes, como colas e pilas.
Entón, podemos mover-se en erros ortográficos.
>> Erros ten no código de distribución un par de arquivos de importancia.
Primeiro notamos que temos ese Makefile aquí,
que non temos realmente visto antes.
Se mirase dentro do cartafol pset5, entender que ten un. Arquivo h,
entón tes dous arquivos. c.
O que isto fai é Makefile antes, teriamos só escriba make e despois o nome do programa
e entón veriamos todos estes argumentos e bandeiras pasado para o compilador.
O que o Makefile fai é nos permite compilar varios arquivos dunha soa vez
e pasar as bandeiras que queremos.
Aquí vemos só hai un ficheiro de cabeceira aquí.
Entón en realidade temos dous arquivos de orixe.
Temos speller.c e dictionary.c.
Estás convidado a editar o Makefile se o desexa.
Teña en conta que aquí se escribe limpo, entón o que fai é realmente eliminar calquera cousa
que é o núcleo.
Se ten un fallo de segmento, basicamente consegue un core dump.
Polo tanto, este ficheiro de pouco feo aparecerá no seu directorio chamado núcleo.
Vai querer eliminar o para facelo limpo.
El elimina todos os ficheiros exe e. Arquivos o.
>> Imos dar un ollo a dictionary.h.
Este di que ela declárase a funcionalidade dun dicionario.
Temos unha lonxitude máxima para calquera palabra no dicionario.
Dicimos que esta vai ser a palabra máis longa posible. É de lonxitude 45.
Entón, nós non imos ter todas as palabras que exceden ese lonxitude.
Aquí só temos os prototipos de función.
Non temos a implementación real porque é iso que imos facer con esta pset.
Pero o que iso fai é xa que estamos lidando con arquivos maiores aquí
e funcionalidade nunha escala maior, é útil ter un. arquivo h
para que outra persoa lendo ou usando o seu código pode entender o que está a suceder.
E quizais eles queren aplicar intenta fixo táboas de hash ou viceversa.
Entón eles din que a miña función de carga,
a implementación real vai ser diferente, pero este prototipo non vai cambiar.
Aquí comprobar que retorna certo se unha determinada palabra está no dicionario.
Entón, temos de carga, que basicamente leva un ficheiro de dicionario
e leva-lo en algunha estrutura de datos.
Temos tamaño, que, cando chamado, devolve o tamaño do seu dicionario,
cantas palabras son almacenados,
e descargar, o que libera toda a memoria que pode tomar
ao mesmo tempo que o seu dicionario.
>> Imos dar un ollo a dictionary.c.
Vemos que é moi parecido dictionary.h, só que agora só ten todas esas todos nel.
E así que é o seu traballo. Finalmente, vai ser o recheo de speller.c con todo este código.
Dictionary.c, cando se executa, non é realmente vai facer algo,
por iso ollar para speller.c para ver a implementación real do corrector ortográfico.
Aínda que non vai ser a edición calquera código,
é importante ler, entender cando é chamado de carga, cando eu estou chamando de verificación,
só para entender, mapea-lo para fóra, ver como a función funciona.
Vemos que está comprobando o uso correcto.
Esencialmente, cando alguén corre Speller, iso indica que é opcional
para eles para pasar nun arquivo de dicionario, porque alí vai ser un ficheiro de dicionario por defecto.
E entón eles teñen que pasar o texto a ser comprobado feitizo.
rusage ofertas co tempo, porque unha parte deste pset que imos tratar máis tarde
é non só obter un funcionamento corrector ortográfico traballando
pero realmente conseguir que sexa rápido.
E así, entón, que é onde rusage vai vir dentro
Aquí vemos a primeira chamada para un dos nosos arquivos dictionary.c, que é carga.
Carga retorna true ou false - true en caso de éxito, falso en caso de fallo.
Entón, se o dicionario non foi posto correctamente, entón o speller.c pode voltar 1 e saia.
Pero se fai a carga correctamente, entón vai continuar.
Continuamos, e vemos algún arquivo I / O aquí,
onde vai ser xestionar a apertura do ficheiro de texto.
Aquí, o que iso fai é feitizo comprobar cada palabra no texto.
Entón, o que está facendo speller.c aquí está interactuando sobre cada unha das palabras no ficheiro de texto
e, a continuación, comprobando los no dicionario.
Aquí temos un Boolean incorrecta que vai ver se a comprobación retorna certo ou non.
Se a palabra é, en realidade, no dicionario, entón cheque volverá true.
Isto significa que a palabra non está incorrecto.
Entón incorrecta sería falsa, e é por iso que temos o estrondo alí, a indicación.
Nós manter en curso, e en seguida, el mantén o control de cantas palabras con erros ortográficos
existen no arquivo.
Continúa e pecha o arquivo.
Entón, aquí, el informa cantas palabras con erros ortográficos que tivo.
El calcula a cantidade de tempo que levou para cargar o dicionario,
canto tempo tardou para comprobar-lo,
canto tempo levou para calcular o tamaño,
que, coma nós imos seguir, debe ser moi pequena,
e despois de canto tempo que levou para descargar o dicionario.
Aquí enriba, vemos a chamada para descargar aquí.
Verificar tamaño aquí,
entón vemos que aquí é a chamada para o tamaño que determina o tamaño do dicionario.
Impresionante.
>> A nosa tarefa para este pset é aplicar carga, o que vai cargar o dicionario
estrutura de datos - o que escoller, sexa unha táboa hash ou un intento -
con palabras do ficheiro de dicionario.
Entón tes tamaño, que pode voltar o número de palabras no dicionario.
E se implantar carga de forma intelixente, entón o tamaño debe ser moi doado.
Entón comprobar que pode comprobar se unha palabra está no dicionario.
Entón speller.c pasa unha corda, e entón ten que comprobar que a cadea que
está contido dentro do seu dicionario.
Teña en conta que xeralmente temos dicionarios estándar,
pero neste pset, basicamente, calquera dicionario transmitido en calquera lingua.
Polo tanto, non podemos só supor que a palabra THE está dentro.
O FOOBAR palabra pode ser definida nun dicionario seguro que pasamos dentro
E entón temos descargar, o que libera o dicionario da memoria.
>> En primeiro lugar, gustaríame ir sobre o método de táboa hash
sobre como podemos implementar todas estas catro funcións,
e entón eu vou pasar por riba do método intenta, como podemos aplicar esas catro funcións,
e na conversa final sobre algunhas suxestións xerais cando está facendo o pset
e tamén como pode ser capaz de usar Valgrind para comprobar se hai vazamentos de memoria.
>> Imos para o método de táboa hash.
Unha táboa consta dunha lista de baldes.
Cada valor, cada palabra, está a ir nun deses baldes.
Unha táboa ideal distribúe todos eses valores que está pasando en
e logo cobre-los no balde de xeito que cada balde
ten preto de un número igual de valores na mesma.
A estrutura dunha táboa hash, temos unha serie de listas ligadas.
O que facemos é cando pasamos nun valor, nós consideramos que ese valor debería pertencer,
balde que pertence, e despois poñelas na lista ligada asociada a ese balde.
Aquí, o que eu teño é unha función hash.
É unha táboa int hash.
Así, para o primeiro balde, os enteiros baixo de 10 ir para o primeiro balde.
Calquera números enteiros riba de 10, pero por baixo de 20 ir para o segundo,
e, a continuación, así por diante e así por diante.
Para min, cada segmento é representar eses números.
Con todo, dicir que eu estaba a pasar en 50, por exemplo.
Afigura-se como se os tres primeiros conteñen unha serie de 10 números.
Pero quero deixar o meu táboa hash para tomar calquera tipo de enteiros,
entón eu tería que filtrar todos os números enriba de 30 no balde pasado.
E así, entón, que resultaría nunha especie de táboa hash desequilibrada.
Para reiterar, unha táboa hash é só unha matriz de caçambas
onde cada balde é unha lista ligada.
E así, para determinar onde cada valor vai, que vai para balde,
vai querer o que se denomina función hash
que asume un valor e, a continuación, di que este valor corresponde a un balde correcto.
Entón, alí encima, neste exemplo, a miña función hash levou cada valor.
É comprobado se foi inferior a 10.
Se fose, sería colocar-lo no primeiro balde.
El verifica se é menor que 20, coloca-o no segundo, se verdadeira,
comproba se é menor que 30, e en seguida, colócase no terceiro balde,
e despois de todo só cae no balde cuarto.
Así, sempre que ten un valor, función teu hash
vai poñer o valor dentro do balde apropiado.
A función hash, basicamente, ten que saber cantos baldes que ten.
O seu tamaño da táboa, o número de depósitos que ten,
que vai ser un número fixo que se con vostede, para decidir,
pero vai ser un número fixo.
Polo tanto, a súa función hash estará contando con iso para determinar balde de cada clave vai
de tal forma que é uniformemente distribuída.
Similar á nosa implantación de listas ligadas, agora cada nó na táboa de hash
é realmente vai ter un char tipo.
Polo tanto, temos unha matriz de char chamado palabra e, a continuación, outro punteiro ao seguinte nodo,
o que ten sentido, porque vai ser unha lista ligada.
Lembre-se de cando tiña conectado listas, fixen un * no chamado cabeza
que estaba apuntando para o primeiro nodo da lista vinculada.
Pero para a nosa táboa hash, porque temos varias listas ligadas,
o que queremos é que queremos que a nosa táboa de hash para ser como, "O que é un balde?"
Un balde é só unha lista de punteiros de nós,
e así cada elemento no balde en realidade apunta a súa lista vinculado correspondente.
Para volver este esquema, ve que os baldes en si son as frechas,
non nos reais.
Unha propiedade esencial de funcións hash é que son determinísticos.
Isto significa que sempre que hash o número 2,
debe volver sempre o mesmo balde.
Cada valor único que vai para a función hash, se repetida,
ten que obter o mesmo índice.
Polo tanto, a súa función hash retorna o índice da matriz
cando ese valor pertence.
Como mencionei antes, o número de depósitos é fixo,
e para que o seu índice que volver ten que ser menor que o número de caçambas
pero maior que 0.
A razón pola que temos funcións de hash en vez de só unha única lista vinculada
ou unha única matriz é que queremos ser capaz de ir a unha determinada sección máis facilmente
se sabemos que a característica de valor -
en vez de ter que buscar no dicionario todo,
ser capaz de ir a unha determinada sección do mesmo.
A súa función hash debe ter en conta que, idealmente,
cada balde ten aproximadamente o mesmo número de teclas.
Como a táboa hash é unha serie de listas ligadas,
a continuación, as listas ligadas propios van ter máis dun nodo.
No exemplo anterior, dous números diferentes, aínda que elas non sexan iguais,
cando desordenado, volvería o mesmo índice.
Entón, cando está lidando coas palabras, unha palabra cando hash
sería o mesmo valor hash como outra palabra.
Iso é o que chamamos unha colisión, cando temos un no que, cando hash,
a lista ligada a ese balde non está baleiro.
A técnica que chamamos hai lineal enquisa,
onde vai a lista de ligazóns e, a continuación, descubrir onde quere inserir o no
porque ten unha colisión.
Podes ver que pode haber un trade-off aquí, non?
Se vostede ten unha táboa moi pequena suma, un número moi pequeno de baldes,
entón vai ter unha morea de colisións.
Pero, entón, se fai unha táboa hash moi grande,
está indo probablemente para minimizar as colisións,
pero vai ser unha gran estrutura de datos.
Non vai ser trade-offs con iso.
Entón, cando está facendo a súa pset, proba xogar
entre quizais facer unha pequena táboa hash
pero entón sabendo que vai levar un pouco máis para atravesar os distintos elementos
desas listas ligadas.
>> O que carga vai facer é iterar sobre cada palabra no dicionario.
El pasa un punteiro para o arquivo de dicionario.
Entón, vai aproveitar o arquivo E / S funcións que dominan en pset4
e iterar sobre cada palabra no dicionario.
Quere que todas as palabras do dicionario para facer un novo nodo,
e vai poñer cada un deses nós dentro da súa estrutura de datos dicionario.
Sempre que comeza unha nova palabra, xa sabe que vai facer un nó.
Entón pode ir inmediatamente e malloc un punteiro no para cada palabra nova que ten.
Aquí estou chamando meu new_node punteiro nó e estou mallocing o que? O tamaño dun nodo.
Entón, para ler a secuencia real dun ficheiro, porque o dicionario está almacenado
por unha palabra e, a continuación, unha nova liña, o que pode aproveitar de
é a función fscanf,
cal é o ficheiro de dicionario que estamos pasada
por iso comproba o arquivo para unha cadea e lugares que cadea o último argumento.
Se se lembrar de volta para unha das conferencias, cando nós fomos
e tipo de peladas as capas de volta na biblioteca CS50,
vimos unha aplicación de fscanf alí.
Para volver ao fscanf, temos o ficheiro que estamos lendo,
Estamos á procura de unha cadea na que o ficheiro, e despois imos poñelas en
aquí eu teño new_node-> palabra porque new_node é un punteiro no,
non un nó real.
Entón eu estou dicindo new_node, quero ir para o nodo que está a apuntar cara
e despois asignar o valor á palabra.
Queremos entón tomar a palabra e inserir-lo na táboa de hash.
Entenda que fixemos new_node un punteiro nodo
porque nós imos querer saber o que o enderezo do nodo é
cando inserir-lo no porque a estrutura dos nós, da estrutura,
é que eles teñen un enlace para un novo nodo.
Entón cal é o enderezo do nodo que vai apuntar?
Este enderezo será new_node.
Isto ten sentido, porque estamos facendo un new_node * ó en oposición a un nodo?
Okay.
Temos unha palabra. Este valor é new_node-> palabra.
Que contén a palabra do dicionario que desexa inserir.
Entón, o que queremos facer é que queremos chamar a nosa función hash sobre esta secuencia
porque a nosa función hash leva nunha secuencia e despois nos devolve un número enteiro,
onde ese enteiro é o índice onde hashtable en que o índice representa que balde.
Queremos levar ese índice e, a continuación, ir ao contido da táboa hash
e despois usar esta lista ligada para introducir o nó no new_node.
Lembre que, con todo, decide introducir o nó,
se é no medio se quere solucionar isto
ou no inicio ou no final, só a certeza de que o seu último nodo sempre apunta para NULL
porque esa é a única forma que sabemos onde o último elemento da lista conexionada e.
>> Se o tamaño é un enteiro que representa o número de palabras nun dicionario,
a continuación, unha forma de facer isto é que, sempre que o tamaño é chamado
pasamos por cada elemento na nosa táboa hash
e logo percorrer cada lista ligada dentro da táboa hash
e, entón, calcular a lonxitude de que, aumentando a nosa 1 contador en 1.
Pero cada vez que o tamaño é chamado, que vai levar un longo tempo
porque imos ser linearmente sondando cada única lista vinculada.
En vez diso, vai ser moito máis doado se manter o control de cantas palabras son pasados ​​dentro
Entón se incluír un contador dentro da súa función de carga
que as actualizacións, como sexa necesario, a continuación, contador, se define-lo como unha variable global,
serán capaces de acceder polo tamaño.
Entón, o que tamaño podería simplemente facer é unha liña, pode voltar o valor do contador,
o tamaño do dicionario, que xa tratadas na carga.
Isto é o que eu quería dicir cando dixo que se aplicar carga de forma útil,
entón o tamaño vai ser moi fácil.
>> Entón, agora temos que comprobar.
Agora estamos lidando con palabras do ficheiro de texto de entrada,
e así imos estar comprobando todas esas palabras de entrada
son, en realidade, no dicionario ou non.
Semellante a Scramble, queremos permitir a insensibilidade caso.
Quere estar seguro de que todas as palabras pasada, a pesar de seren caso mixto,
cando chamado con respecto cadea, son equivalentes.
As palabras nos arquivos de texto dicionario son, en realidade, todas as letras minúsculas.
Outra cousa é que pode asumir que cada palabra pasada, cada corda,
vai ser tanto alfabética ou conter apóstrofos.
Apóstrofos van ser palabras válidas no noso dicionario.
Entón se ten unha palabra con apóstrofo S, que é unha palabra real lexítimo no seu dicionario
que vai ser un dos nós na táboa hash.
Asegúrese de que opera coa palabra existe, entón ten que estar na nosa táboa de hash.
Se a palabra está no dicionario, entón todas as palabras do dicionario están na táboa hash,
entón imos ollar para esta palabra na táboa hash.
Sabemos que dende que Implementar noso función hash
de tal xeito que cada palabra única é sempre hash para o mesmo valor,
entón sabemos que, en vez de buscar a través da nosa mesa enteira toda hash,
podemos realmente atopar unha lista ligada que esa palabra debe pertencer.
Se fose no dicionario, entón sería ese balde.
O que podemos facer, se a palabra é o nome da nosa cadea pasada
Podemos só hash que palabra e ollar para a lista ligada
por valor de hashtable [hash (palabra)].
De alí, o que podemos facer é que temos un subconjunto menor de nós para buscar esta palabra,
e para que poidamos atravesar a lista ligada, usando un exemplo máis cedo no paso a paso,
e despois chamar cadea compare coa palabra onde queira que o cursor está a apuntar,
esa palabra, e ver se os comparar.
Dependendo da forma que organizar a súa función hash,
se é ordenado, pode ser capaz de volver un pouco máis cedo falsa,
pero si é indiferenciados, entón quere seguir percorrendo a través da súa lista ligada
ata atopar o último elemento da lista.
E se aínda non atopou a palabra polo tempo que chegou ao fin da lista ligada,
que significa que a súa palabra non existe no dicionario,
e así que a palabra non é válido,
e comprobación debe retornar falso.
>> Agora imos para descargar, onde queremos liberar todos os nós que temos malloc'd,
tan libre de todos os nós dentro da nosa táboa de hash.
Nós imos querer iterar sobre as listas ligadas e libres de todos os nós que.
Se ollar por riba no paso a paso para o exemplo que liberar unha lista ligada,
entón vai querer repetir este proceso para cada elemento na táboa hash.
E eu vou pasar por riba deste cara ao final da explicación,
pero Valgrind é unha ferramenta onde podes ver se adecuadamente liberado
Cada nodo que malloc'd ou calquera outra cousa que malloc'd, calquera outro punteiro.
Entón, iso é táboas de hash, onde temos un número finito de baldes
e unha función hash, que terá un valor e despois asignar o valor para un balde correcto.
>> Agora chegamos ao tentativas.
Intenta tipo de ollar como este, e eu tamén vou sacar un exemplo.
Basicamente, ten toda unha serie de cartas de potenciais,
e entón, sempre que está construíndo unha palabra,
esa carta pode ser conectado por un dicionario para unha ampla gama de posibilidades.
Algunhas palabras comezan con C, pero a continuación, continuar a,
pero outros continúan co, por exemplo.
Un trie é un xeito de ver todas as combinacións posibles destas palabras.
Unha trie vai seguir a secuencia de letras que compoñen as palabras,
ramificados-se, cando sexa necesario, cando unha letra pode ser seguido por un múltiple de cartas,
e ao final de cada punto indican a palabra é válido ou non
porque se está Soletrando a palabra MAT, MA Eu non creo que é unha palabra válida, pero é MAT.
E así, no seu trie, iso indicaría que despois de MAT que en realidade é unha palabra válida.
Cada nodo na nosa trie está realmente indo para conter unha matriz de punteiros de nós,
e nós imos ter, especialmente, 27 dos punteiros do nodo,
un para cada letra do alfabeto, así como o carácter apóstrofo.
Cada elemento na matriz é en si que pode apuntar a outro nodo.
Entón, se ese nodo é NULL se non hai nada despois diso,
entón sabemos que non hai outras cartas en que a secuencia de palabras.
Pero se ese nodo non é NULL, o que significa que hai máis cartas en que secuencia de letras.
E despois diso, cada nodo indica se é o último carácter dunha palabra ou non.
>> Imos a un exemplo dunha trie.
Primeiro eu teño espazo para 27 nós nesta matriz.
Se eu tivera a palabra BAR -
Se eu tivera a BAR palabra e quero introducir no que,
a primeira letra é B, entón a miña trie é baleiro,
B é a segunda letra do alfabeto, entón eu vou escoller para poñer esta aquí neste índice.
Vou ter B aquí.
B vai ser un nó que apunta a outra matriz de todos os posibles caracteres
que pode seguir tras a letra B.
Neste caso, eu estou lidando con a barra de palabra, de xeito que a ira aquí.
Despois de A, eu teño a letra R, de forma seguida, un puntos agora a súa propia combinación,
e R estarei aquí.
Bar e unha palabra completa, entón eu vou ter punto R para outro no
que di que esa palabra é válido.
Este nó é tamén vai ter un conxunto de nós,
pero os poden ser NULL.
Pero, basicamente, pode seguir así.
Isto vai facer un pouco máis claro cando imos a un exemplo diferente,
por iso teña paciencia comigo alí.
Agora temos BAR dentro do noso dicionario.
Agora dicir que temos o Baz palabra.
Comezamos con B, e xa temos B como unha das cartas que están no noso dicionario.
Isto é seguido con A. Temos un posto.
Pero, entón, en vez diso, temos seguinte Z.
Entón, a continuación, un elemento da nosa matriz será Z,
e así, entón, que un vai apuntar a outro fin válido da palabra.
Así, vemos que cando seguimos a B e despois A,
hai dúas opcións diferentes actualmente no noso dicionario de palabras que comezan con B e A.
Dicir que quería introducir o FOOBAR palabra.
Entón, queremos facer unha entrada en F.
F é un nó que apunta a unha matriz enteira.
O que ía atopar, vai a O, O, a continuación, conecta a unha lista enteira.
Teriamos B e, a continuación, continuar, teriamos A e despois R.
Entón atravesa foobar todo o camiño ata FOOBAR é unha palabra correcta.
E así, entón iso sería unha palabra válida.
Agora dicir que a nosa seguinte palabra no dicionario é realmente a palabra foo.
Diriamos F. O que segue F?
En realidade, eu xa teño un espazo para o, entón eu vou seguir.
Eu non teño de facer un novo. Continuar.
Foo é unha palabra válida neste dicionario, entón eu vou para indicar
que iso é válido.
Se eu deixar o meu secuencia alí, que sería correcto.
Pero se seguimos a nosa secuencia de Foo ata B
e só tiña foob, foob non é unha palabra, e iso non é indicado como un válido.
Nunha trie, ten cada nó indicando se é unha palabra válida ou non,
e, a continuación, cada nó tamén ten unha matriz de 27 punteiros do nodo
que apunte a nós mesmos.
>> Aquí está unha forma de como pode querer axustar iso.
Con todo, como no exemplo da táboa hash, onde tiña a cabeza * ó
para indicar o inicio da nosa lista ligada, nós tamén imos querer
algunha forma de saber onde o inicio da nosa trie é.
Algúns chaman a xente intenta árbores, e é aí que vén da raíz.
Entón, nós queremos a raíz da nosa árbore para estar seguro de que imos estar aterrado
onde o noso trie é.
Nós xa medio que fun máis
a forma como podería pensar a carga de cada palabra no dicionario.
Esencialmente, para cada palabra que vai querer para percorrer o trie
e sabendo que cada elemento en que os nenos - que chamou de nenos neste caso -
corresponde a unha letra diferente, vai querer comprobar eses valores
en que o índice particular, que corresponde á letra.
Entón, pensando todo o camiño de volta a César e Vigenère,
sabendo que cada carta que podes tipo de mapa para un índice alfabético,
definitivamente da a Z vai ser moi fácil de localizar nun mapa a unha letra alfabética,
pero, desgraciadamente, as apóstrofes son tamén un carácter aceptado en palabras.
Eu nin estou seguro que o valor ASCII é,
así para que, se quere atopar un índice de decidir se quere que sexa o primeiro ou
ou o último, vai ter que facer unha proba codificado para
e despois poñer isto no índice 26, por exemplo.
Entón está comprobando o valor en nenos [i]
onde [i] corresponde a calquera carta que está.
Se isto é NULL, o que significa que non hai actualmente ningunha carta posibles
decorrente de que a secuencia anterior, de xeito que vai querer malloc
e facer un novo nodo e teñen que os nenos [i] punto para el
de modo que crear - cando inserido nunha carta para o rectángulo -
facendo os nenos non NULL e punto en que novo nodo.
Pero se iso non é NULL, como no noso exemplo de foo
cando xa FOOBAR, seguimos,
e non estamos sempre facendo un novo nodo, senón só a creación is_word para true
no fin da palabra.
>> Polo tanto, así como antes, porque aquí está lidando con cada letra de cada vez,
que vai ser máis doado para ti para o tamaño, en vez de ter que calcular
e pasar por toda a árbore e calcular cantos fillos eu teño
e, a continuación, ramificados-se, lembrar-se cantos están do lado esquerdo e lado dereito
e cousas así, vai ser moito máis doado para ti
se só manter o control de cantas palabras está engadindo a
cando está lidando con a carga.
E entón que o tamaño do camiño pode devolver só unha variable global do tamaño.
>> Agora chegamos a comprobar.
Mesmos estándares de antes, onde queremos permitir a insensibilidade caso.
Como así, imos supor que as cordas son só caracteres alfabéticos ou os apóstrofos
porque os nenos é unha matriz de 27 de lonxitude,
así todas as letras do alfabeto máis o apóstrofo.
Para comprobar o que vai querer facer é que vai querer comezar na raíz
porque a raíz ha apuntar para unha matriz que contén
todas as letras posibles a partir dunha palabra.
Vai comezar por aí,
e entón vai comprobar e este valor NULL ou non,
porque se o valor é NULL, o que significa que o dicionario non ten ningunha valores
que conteñen a carta en que a orde particular.
Se é nulo, entón iso significa que a palabra é grafada inmediatamente.
Pero se non é NULL, entón podes continuar,
dicir que a primeira letra é unha carta posíbel primeiro nunha palabra,
entón agora eu quero comprobar que a segunda letra, esa secuencia, está dentro do meu dicionario.
Entón está indo para ir ao índice de nenos do primeiro nodo
e comprobar se esa segunda carta existe.
Entón repetir este proceso para verificar que a secuencia é válido ou non
dentro do seu trie.
Sempre que os nenos no no índice apunta a NULL,
vostede sabe que a secuencia non existe,
pero se chegar ao final da palabra que escribiu,
Entón quere comprobar agora que eu completei esa secuencia
e descubriu que dentro do meu trie, que é unha palabra válida ou non?
E entón quere comprobar se, e é aí onde se atopou esa secuencia,
Entón quere comprobar se esa palabra é válido ou non
porque lembro que no caso anterior que eu deseñei, onde tivemos foob,
que era unha secuencia válida que atopamos, pero non era unha palabra real válido en si.
>> Do mesmo xeito, para descargar nos intentos que quere para descargar todos os nós na súa trie.
Sentímolo. Similares ás táboas de hash onde descargar en nós liberados todos os nós,
nos intentos tamén queremos liberar todos os nós.
Descargar realmente máis fácil traballar desde abaixo
porque estes son esencialmente conectados listas.
Entón, nós queremos estar seguro de que temos para todos os valores
e libre de todos los explicitamente.
O que vai querer facer se está a traballar con unha trie
é viaxar para o fondo e no do libre menor posible primeiro
e despois irse a todos os fillos e, entón, libre de todos aqueles,
ir cara arriba e, entón, libre, etc
Tipo de como tratar coa capa de fondo do primeiro trie
e despois vai alí enriba despois de liberar todo.
Este é un bo exemplo de que a función recursiva pode vir a cadra.
Unha vez que liberou a capa inferior da trie,
entón chámase descargar sobre o resto,
asegurarse de que liberar todos os mini -
Podes tipo de velo como intentos mini.
Entón, vostede ten a súa raíz aquí.
Estou simplificando, entón eu non teño que tirar 26 deles.
Entón tes que, e en seguida, estes representan secuencias de palabras
onde todos estes pequenos círculos son letras que son secuencias válidas de letras.
Imos continuar un pouco máis.
O que vai querer facer é libre o fondo aquí e entón libre este
e, a continuación, un agasallo libre no fondo antes de liberar o cumio aquí
porque se algo libre no segundo nivel aquí,
entón realmente vai perder este valor aquí.
É por iso que é importante na descarga de un trie para asegurarse de que liberar o fondo primeiro.
O que pode querer facer é dicir para cada nodo
Quero descargar todos os nenos.
>> Agora que xa sabemos descargar para o método de táboa hash, así como o método trie,
imos querer ollar para Valgrind.
Valgrind corre cos seguintes comandos.
Tes valgrind-v.
Vostede está comprobando todos os vazamentos cando realizar Speller dado este determinado texto
Speller porque precisa levar nun arquivo de texto.
Entón Valgrind ha realizar o seu programa, dicir cantos bytes lle asignado,
cantos bytes lle liberou, e el vai lle dicir se liberou só o suficiente
ou se non suficiente,
ou, ás veces pode ata mesmo sobre libre, como un nó libre que xa foi liberado
e así el pode voltar erros.
Se usar Valgrind, que vai che dar algunhas mensaxes
indicando se liberou ou menos que o suficiente, só o suficiente,
ou máis veces o suficiente.
>> Unha parte deste pset, é opcional para desafiar o Big Board.
Pero cando estamos lidando con esas estruturas de datos
É divertido ver como rapidamente e quão eficiente súas estruturas de datos podería ser.
Será que o seu resultado función hash en un monte de colisións?
Ou é o seu tamaño de datos realmente grande?
Leva moito tempo para atravesar?
No rexistro de Speller, el exhibe canto tempo emprega para cargar,
para comprobar, para conducir, tamaño e para descargar,
e así os foron publicados no O Big Board,
onde podes competir contra os seus compañeiros
e algúns membros do equipo para ver quen ten o máis rápido corrector ortográfico.
Unha cousa que me gustaría observar sobre as táboas de hash
é que hai algunhas funcións moi sinxelo de hash que poderiamos pensar.
Por exemplo, ten 26 baldes, e así cada balde
corresponde á primeira letra dunha palabra,
pero iso vai producir unha táboa de hash moi desequilibrada
porque hai palabras moi menos que comezan con X que comezar con M, por exemplo.
Unha forma de facer Speller é se quere obter todas as funcionalidades outra para abaixo,
despois é só usar unha simple función hash para ser capaz de obter o seu código en execución
e despois volver e cambiar o tamaño da súa táboa de hash e definición.
Hai unha serie de recursos na internet para funcións de hash,
e así a este pset que están autorizados a buscar funcións hash en internet
para algúns consellos e inspiración, sempre que asegúrese de citar onde ten que partir.
Estás convidado a mirar e interpretar algunha función hash que atopa en Internet.
Volver a iso, pode ser capaz de ver se alguén usou unha trie
a súa implementación é máis rápido que a súa táboa hash ou non.
Pode enviar o Consello Big varias veces.
Ela ha gravar a súa entrada máis recente.
Entón quizais cambiar de función hash e, a continuación, entender que en realidade é moito máis rápido
ou moito máis lento que antes.
Isto é un pouco de unha forma divertida.
Sempre hai un ou dous membros do equipo que tentan facer o dicionario máis lento posible,
de xeito que sempre divertido de ollar.
>> O uso a pset é executar Speller cun dicionario opcional
e, a continuación, un arquivo de texto obrigatoria.
Por defecto, cando realizar Speller con só un arquivo de texto e non especificar un dicionario,
vai utilizar o arquivo de texto dicionario, a unha gran
na carpeta cs50/pset5/dictionaries.
Que un ten máis de 100.000 palabras.
Eles tamén teñen un pequeno dicionario, que ten palabras considerablemente menos
CS50 que fixo para ti.
Con todo, pode moi facilmente só facer o seu propio dicionario
se só quere estar traballando en pequenos exemplos -
Por exemplo, se quere usar o gdb e vostede sabe os valores específicos
que quere que o seu táboa de hash para mapear a.
Entón só pode facer o seu propio arquivo de texto só con bar, Baz, foo, e FOOBAR,
facelo nun arquivo de texto, separar os cada un cunha liña,
e, a continuación, facer o seu propio arquivo de texto que literalmente só contén quizais unha ou dúas palabras
para que vostede sabe exactamente o que a saída debe ser.
Algúns dos arquivos de texto mostra que a Big Board cando realizar reto pode comprobar
son Guerra e Paz e unha novela de Jane Austen, ou algo así.
Entón, cando está comezando, é moito máis doado de facer os seus propios ficheiros de texto
que conteñen só un par de palabras ou talvez 10
de modo que pode prever o que o resultado debe ser
e despois comprobar se contra iso, entón un exemplo controlado.
E así xa que estamos lidando con a previsión e deseñar as cousas,
outra vez quero che fomentar a usar papel e pluma
porque realmente vai axudar con un regalo -
deseñar as frechas, como a táboa hash ou como o seu trie mira,
cando está liberando algo onde as frechas están indo,
vostede está seguro o suficiente, vostede ve todos os enlaces desaparecendo
e caendo no abismo da memoria baleirada.
Entón, por favor, por favor, ténteo de deseñar as cousas antes de chegar a escribir código para abaixo.
Debuxe as cousas para que entenda como as cousas están indo para o traballo
porque entón eu asegura que vai executar en confusións menos punteiro alí.
>> Todo ben.
Quero desexar-lle o mellor da sorte con este pset.
É probabelmente o máis difícil.
Polo tanto, proba comezar cedo, deseñar as cousas, deseñar as cousas, e boa sorte.
Este foi Walkthrough 5.
>> [CS50.TV]