[Powered by Google Translate] [Soluzione - Problema Set 5]
[Zamyla Chan - Harvard University]
[Questo è CS50. - CS50.TV]
>> Bene. Ciao a tutti, e benvenuti a Walkthrough 5.
>> Pset5 è Errori ortografici, in cui ci sarà fare un correttore ortografico.
Controllo ortografico sono estremamente importanti.
È mai capitato a voi?
Si lavora molto, molto accumulano su una carta per uno scontro
e poi ancora finisce per ottenere una luce molto rade come una D o una = D
e tutto questo perché tu sei il liverwurst spoiler nella parola balena larga.
Sì, correzione di bozze i peperoni è una questione di, l'impotenza assoluta.
Questo è un problema che colpisce virili, studenti virili.
Una volta mi fu detto dal mio torturatore grado sith che non avrei mai entrare in un buon collega.
E questo è tutto quello che ho sempre voluto, è tutto quello che ogni bambino vuole, alla mia età,
solo per entrare in un buon collega.
E non solo qualsiasi collega. No. Volevo andare a un collega d'Avorio legale.
Quindi, se non ho miglioramenti, sarebbe andato il mio sogno di andare a Harvard,
Jale, o carcere - si sa, nella prigione, nel New Jersey.
Così mi sono fatto un correttore ortografico.
Questo è un estratto da un po 'dei miei artisti preferiti spoken word, Taylor Mali.
In ogni caso, come dice lui, l'importanza di avere un correttore ortografico è molto importante.
>> Quindi benvenuti a Walkthrough 5, in cui saremo a parlare di pset5: Errori ortografici,
in cui ci sarà fare la nostra stessa correttore ortografico.
La cassetta degli attrezzi per questa settimana, il codice di distribuzione, sarà importante guardare
solo per capire le diverse funzioni che il dizionario sta per avere.
Stiamo in realtà sta per essere avere più. File c che insieme rendono la nostra pset.
E così guardando attraverso i diversi aspetti, anche se stiamo in realtà non modifica
uno dei file, speller.c, sapendo come funziona in relazione alla dictionary.c,
che ci sarà la scrittura, sarà molto importante.
Le specifiche pset contiene anche un sacco di informazioni utili
in termini di cose che si possono assumere, le regole e cose del genere,
quindi assicuratevi di leggere con attenzione le specifiche pset per le punte.
E in caso di dubbio di una regola o qualcosa di simile, quindi fare sempre riferimento alle specifiche pset
o discutere.
Questo pset sta andando fanno molto affidamento sui puntatori,
quindi vogliamo essere sicuri di comprendere la differenza tra l'aggiunta di stelle
davanti al nome del puntatore e commerciali e, come liberarli, ecc
Quindi, essere un maestro di puntatori sta andando essere molto utile in questo set problema.
Stiamo andando a guardare in liste collegate un po 'di più,
dove abbiamo elementi che chiamiamo nodi che hanno sia un valore e un puntatore
al nodo successivo, e così essenzialmente collegando diversi elementi uno dopo l'altro.
Ci sono alcune opzioni differenti di attuazione il dizionario vero e proprio.
Stiamo andando a guardare in due metodi principali, che sono le tabelle hash e poi cerca.
In entrambi questi, che comportano una sorta di idea di una lista concatenata
dove avete gli elementi collegati l'uno all'altro.
E quindi stiamo andando a guardare su come si potrebbe essere in grado di operare intorno a liste collegate,
crearli, navigare in termini di come, per esempio, inserire un nodo in esso
o libero tutti i nodi pure.
In termini di nodi di liberazione, che è veramente importante
che ogni volta che la memoria malloc, poi lo libera.
Quindi vogliamo fare in modo che nessun puntatore va unfreed, che noi non abbiamo perdite di memoria.
Stiamo per introdurre uno strumento chiamato Valgrind che esegue il programma
e verifica se la memoria allocata che si è poi liberato.
Il pset è completo solo quando funziona e ha la piena funzionalità,
ma anche, Valgrind ti dice che non hai trovato eventuali perdite di memoria.
Infine, per questa pset, ci tengo a sottolineare -
Voglio dire, come al solito, io sono sicuramente un sostenitore di usare carta e penna per le serie di problemi,
ma per questo, penso che la penna e la carta sta per essere particolarmente importante
quando si desidera essere disegnare frecce per le cose e capire come funzionano le cose.
Quindi, provare ad utilizzare carta e penna per disegnare le cose prima di arrivare codifica
perché potrebbe diventare un po 'disordinato.
>> Per prima cosa, andiamo in liste concatenate un po '.
Liste concatenate consistono di nodi, in cui ogni nodo ha un valore associato,
così come un puntatore al nodo successivo dopo.
Un paio di cose importanti con le liste concatenate sono che abbiamo bisogno di ricordare
dove il nostro primo nodo è, e poi una volta che sappiamo dove il primo nodo è,
in questo modo siamo in grado di accedere al nodo a cui punta il primo nodo a
e poi quello dopo e quello dopo.
E poi l'ultimo elemento nella lista concatenata è puntatore che nodo
sta andando sempre per puntare a NULL.
Quando un nodo punta a NULL, allora sapete che è stata raggiunta la fine della lista,
che tale nodo è l'ultimo, che non c'è niente dopo.
Qui, in questo schema, si vede che le frecce sono i puntatori,
e la sezione blu è dove il valore viene memorizzato,
e poi la scatola rossa con il puntatore è puntatore del nodo
punta al nodo successivo dopo.
E così che vedete qui, il nodo D ricorda a NULL, perché è l'ultimo elemento della lista.
>> Diamo un'occhiata a come si potrebbe definire una struttura per un nodo.
E poiché vogliamo avere più nodi,
questo sta per diventare un typedef struct
in cui stiamo andando ad avere diverse istanze di nodi.
E così lo definiscono come un nuovo tipo di dati.
Qui, abbiamo un nodo typedef struct.
In questo esempio, abbiamo a che fare con i nodi interi,
quindi abbiamo un valore intero di nome e poi abbiamo un altro puntatore,
e in questo caso, è un puntatore a un nodo, quindi abbiamo un nodo struct * chiamata successiva.
E poi stiamo chiamando questo nodo tutta la faccenda.
Assicurarsi di seguire questa sintassi.
Si noti che il nodo è in realtà fa riferimento sopra e sotto le parentesi graffe.
Poi, per tenere traccia di dove il mio primo nodo è in questa lista collegata,
poi ho un puntatore chiamato nodo testa, e malloc spazio sufficiente per le dimensioni di un nodo.
Si noti, tuttavia, che la testa è in realtà un puntatore nodo invece di un vero e proprio nodo.
Quindi la testa in realtà non contiene alcun valore,
che punti solo per qualunque sia il primo nodo nella mia lista concatenata è.
>> Per avere un migliore senso di liste collegate, perché è molto importante
per tenere traccia di fare in modo di mantenere la catena,
Mi piace pensare ad esso come persone in una linea tenendosi per mano,
dove ogni persona è mano nella mano con il prossimo.
Non si può vedere in questo disegno, ma in fondo che stanno puntando alla persona successiva
che è nella loro catena.
E quindi se si vuole attraversare una lista concatenata in cui queste persone -
immaginare tutte queste persone hanno dei valori ad essi associati
e anche il punto alla persona successiva nella linea -
se si vuole attraversare la lista concatenata, per esempio, per modificare i valori del
o la ricerca di un valore o qualcosa di simile,
allora ti consigliamo di avere un puntatore alla persona specifica.
Quindi stiamo andando ad avere un tipo di dati puntatore nodo.
Per questo esempio, chiamiamolo cursore.
Un altro modo comune per denominare questo sarebbe iteratore o qualcosa del genere
perché è l'iterazione di realtà in movimento e quale nodo sta indicando.
Questo qui sarà il nostro cursore.
Il nostro cursore in primo luogo puntare al primo elemento nella nostra lista.
E così quello che vogliamo fare è che sarebbe fondamentalmente continuerà il cursore,
spostandola da un lato all'altro.
In questo caso, vogliamo spostare all'elemento successivo nella lista.
Con gli array, quello che vorrei fare è che sarebbe solo dire che aumentare l'indice di 1.
In questo caso, quello che dobbiamo fare è trovare quale persona in realtà questa persona corrente sta puntando,
e questo sarà il valore successivo.
Quindi, se il cursore è solo un puntatore nodo, allora che cosa vogliamo fare
è che vuole ottenere il valore che il cursore sia puntato.
Vogliamo arrivare a quel nodo e poi, una volta che siamo in quel nodo, trovare dove sta indicando.
Per arrivare al nodo reale che il cursore sia puntato,
di solito noi lo indichiamo con (* cursore).
Ciò vi darà il nodo vero che il cursore sia puntato.
E poi, dopo che, quello che vogliamo fare è si vuole accedere
qualunque cosa questo valore successivo nodo è.
Per fare questo, per accedere ai valori all'interno della struttura, abbiamo l'operatore punto.
Così allora sarebbe (cursore *). Prossimo.
Ma questo è un po 'confuso in termini di avere le parentesi intorno al cursore *,
e così sostituire questa affermazione tutto con il cursore->.
Si tratta di un trattino e poi il segno più grande, in modo da fare una freccia.
cursore-> successivo.
Che in realtà farti il ​​nodo che il cursore si. Tale valore è di prossimo.
Così, invece di avere la stella e il punto, che si sta sostituendo con una freccia.
State molto attenti a fare in modo che si tenta di utilizzare questa sintassi.
>> Ora che abbiamo il nostro cursore, se vogliamo accedere al valore,
prima, abbiamo avuto cursore-> next,
ma per accedere al valore al nodo che il cursore sia puntato, abbiamo semplicemente dire
node-> valore.
Da lì, è del tipo di dati tutto ciò che abbiamo definito i valori ed i nodi di essere.
Se si tratta di un nodo int, quindi cursore-> valore è solo andare a essere un numero intero.
Così siamo in grado di fare operazioni su questo, verificare uguaglianze, assegna valori diversi, ecc
E allora che cosa si vuole fare, se si desidera spostare il cursore alla prossima persona,
effettivamente modificare il valore del cursore.
Dal momento che il cursore è un puntatore nodo, è possibile modificare l'indirizzo effettivo del puntatore
per l'indirizzo del nodo successivo nella lista.
Questo è solo un po 'di codice in cui si può scorrere.
Dove ho il commento fare qualcosa,
è lì che probabilmente stai andando per accedere al valore
o fare qualcosa a che fare con quel nodo specifico.
Per iniziare il tutto, io dico che il mio cursore inizialmente
sta per puntare al primo elemento della lista collegata.
E così avanti, l'ho definito come il capo del nodo.
>> Come ho detto prima, liberando è veramente importante.
Si vuole fare in modo che si liberare ogni elemento della lista una volta che hai finito con esso.
Quando non è necessario fare riferimento a uno qualsiasi di questi puntatori più,
si vuole fare in modo che si liberi tutti questi puntatori.
Ma si vuole essere molto attenti qui a che si vuole evitare perdite di memoria.
Se si libera una persona prematuramente, allora tutti i puntatori che che i punti di nodo per
stanno per essere persi.
Tornando all'esempio persona per renderlo un po 'più alta posta in gioco,
vediamo quali sono queste persone, solo che in questo caso sono in bilico su un lago con un mostro.
Vogliamo fare in modo che ogni volta che liberare, non perdiamo
e lasciare andare tutti i nodi prima di aver effettivamente liberato.
Per esempio, se si dovesse chiamare semplicemente gratuitamente su questo tizio qui,
allora sarebbe stato liberato, ma poi tutti questi ragazzi verrebbe allora meno
e avrebbero deriva fuori e cadere.
Così vuole fare in modo che, invece, vogliamo mantenere un collegamento con il resto.
Il puntatore di testa, che punta al primo elemento della lista.
E 'un po' come una corda di ancoraggio prima persona.
Cosa si potrebbe desiderare di fare quando si libera un elenco è di avere -
Se si desidera liberare il primo elemento, quindi si può avere un puntatore temporaneo
che punta a qualsiasi primo elemento è.
In modo da avere il puntatore temporaneo che punta qui.
In questo modo, si ha una tenuta del primo nodo.
E poi, dal momento che sappiamo che il primo nodo sta per essere liberato,
allora possiamo spostare questa corda, questa ancora, la nostra testa,
per puntare effettivamente a qualunque il primo sta puntando.
Quindi, questa testa fa effettivamente al secondo elemento ora.
Ora ci è consentito di liberare ciò che è memorizzato in temperatura,
e così siamo in grado di cancellare che senza di essa mettere in pericolo tutti gli altri nodi nella nostra lista.
Un altro modo che si possa fare questo potrebbe essere
ogni volta che si libera solo l'ultimo elemento della lista
perché la garanzia di non essere indicato nulla.
Quindi, si può solo liberare questa, poi libero questo, poi libero questo.
Che funziona sicuramente, ma è un po 'più lento perché dalla natura delle liste collegate,
non possiamo immediatamente saltare l'ultimo.
Dobbiamo attraversare ogni elemento della lista concatenata
e verificare se quello che punta a NULL, controllare ogni volta,
e poi una volta si arriva alla fine, quindi gratuito che.
Se si dovesse fare questo processo, si sarebbe in realtà essere il controllo qui,
verifica qui, poi il controllo qui, liberandola,
poi tornare indietro, controllando qui, controllare qui, liberandola,
controllo qui, e quindi liberando.
Ci vuole un po 'più. Gia '.
>> [Studente] Sarebbe possibile fare una lista collegata che memorizza un puntatore di uscita fino alla fine?
Questo sarebbe sicuramente possibile.
Ripetere la domanda, è possibile avere una struttura elenco collegato
in modo tale che si ha un puntatore che indica la fine della lista collegata?
Direi che è possibile, e ogni volta che si inserisce qualcosa nella tua lista concatenata
si dovrebbe aggiornare tale puntatore e cose del genere.
Si potrebbe avere una coda nodo *, per esempio.
Ma quando si sta implementando questa funzione, si deve pensare al trade-off,
come quante volte faccio a essere l'iterazione di questo,
Quanto è difficile sarà per tenere traccia della coda e la testa
così come il mio iteratore, e cose del genere.
Ritiene che -? >> [Studente] Si '.
E 'possibile, ma in termini di decisioni di progettazione, è necessario valutare le opzioni.
>> Qui è uno scheletro di codice che permetterebbe di liberare ogni elemento in una lista concatenata.
Anche in questo caso, dato che sono l'iterazione di una lista collegata, ho intenzione di voler avere un qualche tipo di cursore
o iteratore.
Siamo l'iterazione fino a quando il cursore è NULL.
Se non si desidera scorrere quando il cursore è NULL
perché significa che non c'è niente nella lista.
Allora qui faccio un nodo temporaneo *
indicando quello che sto considerando è il primo della mia lista,
e poi muovo il cursore avanti 1 e quindi liberare tutto quello che avevo nella memoria temporanea.
>> Ora veniamo a inserimento in liste concatenate.
Ho tre nodi nella mia lista concatenata, e andiamo con il caso semplice
dove vogliamo inserire un altro nodo alla fine della nostra lista collegata.
Per fare questo, tutto quello che vorrei fare è che si attraversano
per trovare dove la fine attuale della lista collegata è, quindi qualunque nodo è che punta a NULL -
che è questa -
e poi dire, in realtà, questo non sarà l'ultimo nodo;
stiamo in realtà sta per avere un altro.
Così avremmo questa corrente un punto a tutto ciò che state inserendo.
Così ora questa persona rosso diventa qui l'ultimo nodo della lista collegata.
E così la caratteristica dell'ultimo nodo nella lista collegata è che si punta a NULL.
E allora cosa dovremmo fare è impostare il puntatore di questo ragazzo del rosso a NULL. Ecco.
>> Ma se volessimo inserire un nodo tra la seconda e la terza?
Quello non è così semplice, perché vogliamo fare in modo
che non lasciar andare qualsiasi nodo nella nostra lista collegata.
Quello che avrebbe dovuto fare è fare in modo che noi stessi ancorare a ciascuno.
Per esempio, chiamiamo questo il secondo.
Se hai detto che la seconda ora punta a questa nuova
e hai appena fatto un puntatore lì, allora che si tradurrebbe in questo ragazzo la perdita
perché non c'è alcun legame con lui.
Invece - Io disegnare questo nuovo. Scusate le mie capacità artistiche.
Sappiamo che non possiamo collegare direttamente 2 a quella nuova.
Dobbiamo fare in modo di trattenere l'ultimo.
Quello che potrebbe desiderare di fare è avere un puntatore temporaneo
per l'elemento che sta per essere aggiunto su.
Allora abbiamo un puntatore temporaneo lì.
Poiché sappiamo che questo terzo viene tenuto traccia di,
2 può ora collegarsi al nostro unico nuovo.
E se questo nuovo ragazzo rosso sta per essere tra 2 e 3,
allora ciò che è il puntatore che tizio sta per puntare a? >> [Studente] temp.
Temp. Gia '.
Allora valore successivo questo tizio rosso sta per essere temp.
Quando si inserisce in liste collegate, abbiamo visto che abbiamo potuto
facilmente aggiungere qualcosa alla fine con la creazione di un array temporaneo,
o se volevamo aggiungere qualcosa in mezzo la nostra gamma,
allora ci vorrebbe un po 'di più in giro per mischiare.
Se si vuole, per esempio, hanno una lista ordinata collegata,
poi si deve tipo di valutare i costi ei benefici di tale
perché se si vuole avere un array ordinato, il che significa che ogni volta che si inserisce in esso,
sta andando a prendere un po 'più.
Tuttavia, se si vuole in seguito, come troveremo vorremo,
ricerca attraverso una lista concatenata, allora potrebbe essere più facile se si sa che tutto è in ordine.
Così si potrebbe desiderare di valutare i costi ei benefici di questo.
>> Un altro modo per inserire in una lista collegata è da inserire dall'inizio di un elenco.
Se tracciamo la nostra ancora qui - questo è il nostro capo -
e poi hanno queste persone ad esso collegate,
e poi abbiamo un nuovo nodo da inserire all'inizio,
allora che cosa potrebbe che vogliamo fare?
Che cosa ci sarebbe di male solo dicendo che voglio collegare il rosso al blu,
perché questo è il primo?
Cosa sarebbe successo qui?
Tutti questi tre sarebbero persi.
Quindi non vogliamo farlo.
Ancora una volta, abbiamo imparato che abbiamo bisogno di avere un qualche tipo di puntatore temporaneo.
Scegliamo di avere un punto temporaneo a questo ragazzo.
Quindi possiamo avere il blu un punto alla temporanea
e poi il punto rosso al blu.
Il motivo per cui sto usando la gente qui è perché vogliamo davvero visualizzare
aggrappandosi alle persone e fare in modo che abbiamo un link a loro
prima di lasciare andare un'altra mano o qualcosa del genere.
>> Ora che abbiamo un senso di liste concatenate - come si potrebbe creare una lista concatenata
e creare le strutture per quella consistente nella definizione di tipo per un nodo
e poi fare in modo che abbiamo un puntatore alla testa di tale lista concatenata -
una volta che abbiamo e sappiamo come attraversare attraverso un array,
accedere a vari elementi, sappiamo come inserire e sappiamo come liberarli,
allora possiamo entrare in errori di ortografia.
Come al solito, abbiamo una sezione di domande che avranno utilizzato per operare con liste concatenate
e diverse strutture, come le code e stack.
Quindi siamo in grado di muoversi in errori di ortografia.
>> Errori ortografici ha il codice di distribuzione un paio di file di importanza.
In primo luogo notiamo che abbiamo questo Makefile qui,
che non abbiamo veramente incontrato prima.
Se si guarda all'interno della cartella pset5, avresti notato che si dispone di un file. H,
allora ci sono due file. c.
Quello che fa è Makefile prima, ci basta digitare marca e poi il nome del programma
e poi vedremmo tutti questi argomenti e bandiere passato al compilatore.
Quello che il Makefile fa è ci permette di compilare più file in una sola volta
e passare le bandiere che vogliamo.
Qui dobbiamo solo vedere che c'è un file di intestazione qui.
Poi in realtà abbiamo due file di origine.
Abbiamo speller.c e dictionary.c.
Siete invitati a modificare il Makefile se lo si desidera.
Si noti che qui, se si digita pulita, quindi ciò che fa è in realtà qualcosa che non rimuove
che è il nucleo.
Se hai un errore di segmentazione, in pratica si ottiene un core dump.
Quindi questo file po 'brutto apparirà nella directory chiamato core.
Ti consigliamo di rimuovere tale per farlo pulire.
Rimuove tutti i file exe e. File o.
>> Diamo uno sguardo in dictionary.h.
Questo dice che dichiara la funzionalità di un dizionario.
Abbiamo una lunghezza massima per ogni parola nel dizionario.
Diciamo che questa sarà la parola più lunga possibile. E 'di lunghezza 45.
Quindi non stai andando ad avere tutte le parole che superano tale lunghezza.
Qui dobbiamo solo i prototipi di funzione.
Non abbiamo l'effettiva attuazione perché è quello che faremo per questo pset.
Ma ciò che questo non fa altro che da quando abbiamo a che fare con file di grandi dimensioni qui
e la funzionalità su scala più ampia, è utile disporre di un file. h
in modo che qualcun altro leggere o utilizzare il codice in grado di capire cosa sta succedendo.
E forse vogliono implementare cerca se avete fatto le tabelle hash o viceversa.
Poi dicevano la mia funzione di carico,
l'effettiva attuazione sta per diverso, ma questo prototipo non cambierà.
Qui abbiamo verificare, che restituisce true se una data parola è nel dizionario.
Poi abbiamo il carico, che è quasi esclusivamente in un file dizionario
e quindi carica in una qualche struttura dati.
Abbiamo dimensioni, che, quando viene chiamato, restituisce la dimensione del dizionario,
quante parole sono memorizzati in esso,
e poi scaricare, che libera tutta la memoria che si possono avere preso
rendendo il dizionario.
>> Diamo un'occhiata a dictionary.c.
Vediamo che sembra molto simile a dictionary.h, solo che adesso ha solo tutte queste TODOs in esso.
E perché è il tuo lavoro. Alla fine, ti verrà compilando speller.c con tutto questo codice.
Dictionary.c, quando viene eseguito, non è realmente intenzione di fare nulla,
in modo da guardare verso speller.c per vedere l'effettiva attuazione del correttore ortografico.
Anche se non avete intenzione di essere qualsiasi modifica di questo codice,
è importante leggere, capire quando è carico chiamasse, quando sto chiamando controllo,
solo per capire, mappa fuori, vedere come la funzione lavora.
Si vede che è il controllo per l'utilizzo corretto.
In sostanza, quando qualcuno corre correttore ortografico, questo indica che è opzionale
per loro di passare in un file di dizionario, perché ci sarà un file dizionario predefinito.
E poi devono passare il testo da eseguire il controllo ortografico.
Offerte rusage con il tempo perché una parte di questa pset cui ci occuperemo più avanti
non è solo ottenere un funzionamento correttore ortografico di lavoro
ma in realtà sempre per essere veloce.
E così allora è lì che rusage sta per entrare
Qui vediamo la prima chiamata a uno dei nostri file dictionary.c, che è carico.
Carico restituisce true o false - true in caso di successo, false in caso di errore.
Quindi, se il dizionario non è stato caricato correttamente, il speller.c restituirà 1 e uscire.
Ma se viene caricato correttamente, allora è destinata a continuare.
Proseguiamo, e vediamo un po 'di file I / O qui,
dove sta andando a che fare con l'apertura del file di testo.
Ecco, cosa che fa è ortografico controlla ogni singola parola nel testo.
Così che cosa sta facendo speller.c proprio qui è l'iterazione di ciascuna delle parole nel file di testo
e poi controllando nel dizionario.
Qui, abbiamo un valore booleano errori di ortografia che vedrà se il controllo restituisce vero o no.
Se la parola è in realtà nel dizionario, allora controllo restituirà true.
Ciò significa che la parola non è errato.
Così errata sarebbe falsa, ed è per questo che abbiamo il botto lì, l'indicazione.
Continuiamo ad andare, e quindi tiene traccia del numero di parole errate
ci sono nel file.
Si prosegue e chiude il file.
Poi qui, riporta il numero di parole errate hai avuto.
Si calcola la quantità di tempo impiegato per caricare il dizionario,
quanto tempo ci ha portato a controllare,
quanto tempo impiegato per calcolare la dimensione,
che, come vedremo avanti, dovrebbe essere molto piccola,
e quindi la quantità di tempo impiegato per scaricare il dizionario.
Qui sopra vediamo la chiamata a scaricare qui.
Se controlliamo per la dimensione qui,
poi si vede che è qui chiamata alla dimensione dove si determina la dimensione del dizionario.
Awesome.
>> Il nostro compito per questa pset è quello di implementare il carico, che caricherà il dizionario
struttura dei dati - a seconda di quale si sceglie, sia esso una tabella di hash o un tentativo -
con le parole del file di dizionario.
Poi ci sono dimensioni, che restituirà il numero di parole nel dizionario.
E se si implementa il carico in modo intelligente, quindi taglia dovrebbe essere abbastanza facile.
Allora avete controllo, che controllerà se una data parola è nel dizionario.
Così speller.c passa in una stringa, e poi si deve verificare se la stringa
sono contenuti nel vostro dizionario.
Si noti che in genere hanno dizionari standard,
ma in questo pset, in pratica qualsiasi dizionario passato in in qualsiasi lingua.
Quindi non possiamo dare per scontato che la parola la si trova all'interno.
Il FOOBAR parola potrebbe essere definito in un dizionario certo che passiamo trovi
E poi abbiamo scaricare, che libera il dizionario dalla memoria.
>> In primo luogo, vorrei andare oltre il metodo hash table
su come si possano implementare tutte queste quattro funzioni,
e poi vado sul metodo di prova, il modo in cui attuare queste quattro funzioni,
e alla fine il discorso su alcuni suggerimenti generali quando si sta facendo la pset
e anche come si potrebbe essere in grado di utilizzare Valgrind per verificare la presenza di perdite di memoria.
>> Entriamo nel metodo tabella hash.
Una tabella hash è costituito da un elenco di secchi.
Ogni valore, ogni parola, sta per andare in uno di questi secchi.
Una tabella hash idealmente distribuisce in modo uniforme tutti questi valori che si sta passando
e inserisce poi nel secchio tale che ogni bucket
ha circa lo stesso numero di valori in esso.
La struttura di una tabella hash, abbiamo un array di liste concatenate.
Quello che facciamo è quando si passa un valore, controlliamo, quando tale valore deve appartenere,
secchio che appartiene, e quindi inserirlo nella lista concatenata associata a quel secchio.
Ecco, quello che ho è una funzione hash.
Si tratta di una tabella di hash int.
Così, per il primo bucket, eventuali interi inferiori 10 andare nel secchio prima.
Eventuali numeri interi superiori a 10 ma inferiori a 20 go nel secondo,
e così via e così via.
Per me, ciascun segmento viene rappresenta questi numeri.
Tuttavia, dire che dovevano passare in 50, per esempio.
Sembra come se le prime tre contengono una serie di dieci numeri.
Ma voglio permettere al mio tabella hash ad accogliere qualsiasi tipo di numeri interi,
così poi avrei dovuto filtrare tutti i numeri superiori a 30 nel secchio ultima.
E così allora che si tradurrebbe in una sorta di squilibrata tabella di hash.
Per ribadire, una tabella di hash è solo una serie di secchi
dove ogni secchio è una lista concatenata.
E così, per determinare dove ogni valore va, che va in secchio,
si sta andando a voler quello che si chiama una funzione di hash
che prende un valore e poi dice questo valore corrisponde a un secchio certa.
Così in alto, in questo esempio, la mia funzione di hash ha preso ogni valore.
Controllato se era inferiore a 10.
Se fosse, sarebbe messo nel secchio prima.
Verifica se è meno di 20, la mette nella seconda se è vero,
verifica se è meno di 30, e poi si entra nel terzo secchio,
e poi tutto il resto cade proprio al secchio quarto.
Così ogni volta che ha un valore, la funzione hash
porrà tale valore nel secchio appropriata.
La funzione di hash deve fondamentalmente sapere quanti secchi che avete.
Le dimensioni della tabella hash, il numero di segmenti che hai,
che sta per essere un numero fisso che dipende da voi, per voi a decidere,
ma sarà un numero fisso.
Quindi, la funzione hash verrà basarsi su tale per determinare quale secchio ogni chiave va in
tale che è uniformemente distribuito.
Simile alla nostra implementazione di liste concatenate, ora ogni nodo della tabella hash
è in realtà sta per avere un tipo char.
Quindi abbiamo un array di caratteri chiamato parola e poi un altro puntatore al nodo successivo,
che ha un senso, perché sarà una lista concatenata.
Ricordate quando avevamo liste collegate, ho fatto un * nodo denominato testa
che è stata punta al primo nodo della lista collegata.
Ma per la nostra tabella di hash, perché abbiamo più liste concatenate,
quello che vogliamo è che vogliamo la nostra tabella di hash per essere come, "Che cosa è un secchio?"
Un secchio è semplicemente una lista di puntatori del nodo,
e così ogni elemento nel secchio è in realtà punta alla sua lista collegato corrispondente.
Per tornare a questo schema, si vede che gli stessi secchi sono le frecce,
non nodi effettivi.
Una delle proprietà essenziali di funzioni hash è che sono deterministiche.
Ciò significa che ogni volta che si hash il numero 2,
si deve sempre restituire il secchio stesso.
Ogni singolo valore che va nella funzione hash, se ripetuto,
deve ottenere lo stesso indice.
Quindi la funzione di hash restituisce l'indice della matrice
quando tale valore appartiene.
Come ho detto prima, il numero di segmenti è fisso,
e così l'indice che si torna deve essere inferiore al numero di bucket
ma maggiore di 0.
Il motivo per cui ci sono le funzioni di hash invece di uno solo sola lista collegata
o un singolo array è che vogliamo essere in grado di saltare ad una certa sezione più facilmente
se conosciamo la caratteristica di un valore -
invece di dover cercare attraverso il dizionario nel suo insieme,
essere in grado di passare a una determinata sezione di esso.
La funzione hash deve tener conto del fatto che idealmente,
ciascun segmento ha approssimativamente lo stesso numero di tasti.
Dal momento che la tabella di hash è una serie di liste collegate,
poi le liste concatenate stessi avranno più di un nodo.
Nell'esempio precedente, due numeri differenti, anche se non erano uguali,
quando hash, sarebbe tornato lo stesso indice.
Così, quando hai a che fare con le parole, una parola quando hash
sarebbe lo stesso valore di hash come un'altra parola.
Questo è ciò che noi chiamiamo una collisione, quando abbiamo un nodo che, quando hash,
l'elenco collegato in quel bucket non è vuoto.
La tecnica che noi chiamiamo c'è scansione lineare,
dove si va alla lista linkata e poi trovare dove si desidera inserire tale nodo
perché si ha una collisione.
Si può vedere che ci potrebbe essere un trade-off qui, giusto?
Se si dispone di una tabella di hash molto piccolo, un numero molto limitato di segmenti,
allora si sta andando ad avere un sacco di collisioni.
Ma poi se si fanno una tabella molto grande hash,
probabilmente stai andando a ridurre al minimo le collisioni,
ma sarà una struttura di dati molto grande.
Ci sarà compromessi con questo.
Così, quando si sta facendo la tua pset, provare a giocare
tra forse fare un tavolo più piccolo hash
ma poi sapendo che ci vorrà un po 'più tempo per attraversare i diversi elementi
di tali liste concatenate.
>> Che carico sta per fare è iterare su ogni parola nel dizionario.
Si passa in un puntatore al file di dizionario.
Quindi hai intenzione di approfittare del file funzioni I / O che è imparato a pset4
e scorrere ogni parola nel dizionario.
Volete ogni parola nel dizionario di diventare un nuovo nodo,
e si sta andando a mettere ogni uno di quei nodi all'interno della vostra struttura dizionario dei dati.
Ogni volta che si ottiene una nuova parola, si sa che sta per diventare un nodo.
Così si può andare subito e malloc un puntatore nodo per ogni nuova parola che avete.
Qui sto chiamando il mio new_node puntatore del nodo e sto mallocing cosa? La dimensione di un nodo.
Poi, per leggere la stringa effettiva da un file, perché il dizionario è in realtà memorizzati
da una parola e poi una nuova linea, quello che possiamo trarre vantaggio
è la funzione fscanf,
in base al quale è il file dizionario che stiamo passato,
quindi analizza il file per una stringa e luoghi che nella stringa l'ultimo argomento.
Se vi ricordate tornare a una delle lezioni, quando siamo andati oltre
e il tipo di pelati strati indietro sulla libreria CS50,
abbiamo visto l'implementazione di fscanf lì.
Per tornare alla fscanf, abbiamo il file che stiamo leggendo da,
siamo alla ricerca di una stringa in quel file, e poi stiamo messa in
qui ho new_node-> parola perché new_node è un puntatore nodo,
non un nodo effettivo.
Allora sto dicendo new_node, voglio andare al nodo che si sta puntando
e quindi assegnare tale valore alla parola.
Vogliamo prendere poi quella parola e inserirla nella tabella hash.
Rendetevi conto che abbiamo fatto new_node un puntatore nodo
perché stiamo andando a voler sapere che cosa l'indirizzo del nodo è
se lo inseriamo in quanto la struttura dei nodi stessi, della struttura,
è che hanno un puntatore a un nuovo nodo.
Allora qual è l'indirizzo del nodo che sta per puntare a?
Questo indirizzo sarà new_node.
Ha senso, perché stiamo facendo un new_node * nodo al contrario di un nodo?
Va bene.
Noi abbiamo una parola. Tale valore è new_node-> parola.
Che contiene la parola dal dizionario che si desidera immettere.
Quindi, quello che vogliamo fare è che si vuole chiamare la nostra funzione hash su tale stringa
perché la nostra funzione di hash prende in una stringa e poi ci restituisce un intero,
quando tale intero è l'indice in cui hashtable a tale indice rappresenta quel secchio.
Vogliamo prendere tale indice e poi andare a quella indice della tabella di hash
e quindi utilizzare tale lista collegata per inserire il nodo in new_node.
Ricorda che però si decide di inserire il nodo,
se è nel mezzo, se si desidera ordinare la
o all'inizio o alla fine, basta assicurarsi che il vostro ultimo nodo punta sempre a NULL
perché questo è l'unico modo che sappiamo dove l'ultimo elemento della nostra lista è collegata.
>> Se la dimensione è un numero intero che rappresenta il numero di parole in un dizionario,
quindi un modo per fare questo è che ogni volta che si chiama dimensione
passiamo attraverso ogni elemento nella nostra tabella di hash
e poi scorrere ogni lista collegata all'interno della tabella hash
e quindi calcolare la lunghezza di questo, aumentare il nostro contatore 1 di 1.
Ma ogni volta che le dimensioni si chiama, che ci vorrà molto tempo
perché ci sta andando ad essere linearmente sondare ogni singola lista collegata.
Invece, sarà molto più facile se si tiene traccia di quante parole sono passati trovi
Allora se si include un contatore all'interno della vostra funzione di carico
che gli aggiornamenti, se necessario, poi contro, se si imposta una variabile globale,
potranno essere accessibile dimensioni.
Così che cosa dimensioni potrebbe semplicemente fare è in una sola riga, torna il valore del contatore,
la dimensione del dizionario, che è già stato affrontato nel carico.
Questo è quello che intendevo quando ho detto che se si implementa il carico in modo utile,
quindi le dimensioni sarà abbastanza facile.
>> Così ora si arriva a controllare.
Ora abbiamo a che fare con le parole dal file di testo di input,
e quindi abbiamo intenzione di verificare se tutte queste parole di ingresso
sono in realtà nel dizionario o meno.
Simile a Scramble, vogliamo far sì che tra maiuscole e minuscole.
Si vuole fare in modo che tutte le parole passato, anche se sono maiuscole e minuscole,
quando viene chiamato con stringa di confronto, sono equivalenti.
Le parole in file di testo del dizionario sono in realtà tutti in minuscolo.
Un'altra cosa è che si può supporre che ogni parola passata, ogni stringa,
sta per essere alfabetico o contenere apostrofi.
Apostrofi saranno parole valide nel nostro dizionario.
Quindi, se avete una parola con apostrofo S, che è una parola vera legittima nel dizionario
che sta per essere uno dei nodi della tabella di hash.
Verificare opera con se la parola esiste, allora è avuto modo di essere nella nostra tabella di hash.
Se la parola è nel dizionario, allora tutte le parole del dizionario si trovano nella tabella di hash,
quindi diamo un'occhiata a questa parola nella tabella di hash.
Sappiamo che da quando abbiamo implementato la nostra funzione di hash
tale che ogni parola univoca è sempre hash allo stesso valore,
allora sappiamo che invece di cercare tra tutta la nostra intera tabella di hash,
si può effettivamente trovare l'elenco collegato che questa parola dovrebbe appartenere a.
Se fosse nel dizionario, allora sarebbe nel secchio.
Quello che possiamo fare, se la parola è il nome della nostra stringa passata,
possiamo solo hash che la parola e un'occhiata alla lista concatenata
al valore della tabella hash [hash (parola)].
Da lì, quello che possiamo fare è che abbiamo un sottoinsieme più piccolo di nodi per la ricerca di questa parola,
e così siamo in grado di attraversare la lista collegata, con un esempio in precedenza nella procedura dettagliata,
e quindi chiamare stringa confrontare sulla parola ovunque il cursore è su,
quella parola, e vedere se quelli confrontare.
A seconda del modo in cui si organizza la funzione di hash,
se è ordinato, si potrebbe essere in grado di restituire false un po 'prima,
ma se è indifferenziato, poi si desidera continuare movimento attraverso la vostra lista concatenata
fino a trovare l'ultimo elemento della lista.
E se non hai ancora trovato la parola per il tempo che hai raggiunto la fine della lista collegata,
ciò significa che la tua parola non esiste nel dizionario,
e in modo che la parola non è valido,
e controllo deve restituire false.
>> Ora veniamo a scaricare, dove vogliamo liberare tutti i nodi che abbiamo malloc'd,
così libero tutti i nodi all'interno della nostra tabella di hash.
Stiamo andando a voler scorrere tutte le liste concatenate e libera tutti i nodi in questo.
Se si guarda al di sopra nella procedura dettagliata per l'esempio in cui liberiamo una lista concatenata,
allora ti consigliamo di ripetere questo processo per ogni elemento nella tabella hash.
E io vado su questo verso la fine della procedura dettagliata,
ma Valgrind è uno strumento dove si può vedere se si è liberato correttamente
ogni nodo che hai malloc'd o qualsiasi altra cosa che hai malloc'd, qualsiasi altro puntatore.
Ecco, questo è tabelle hash, dove abbiamo un numero finito di segmenti
e una funzione di hash che avrà un valore e quindi assegnare tale valore a un secchio certa.
>> Ora veniamo a tentativi.
Tenta tipo di look in questo modo, e io anche tirare fuori un esempio.
In sostanza, si dispone di tutta una serie di lettere potenziali,
e poi ogni volta che si sta costruendo una parola,
lettera che può essere collegato ad un dizionario di una vasta gamma di possibilità.
Alcune parole iniziano con C ma poi continuare con A,
ma altri continuano con O, per esempio.
Un trie è un modo di visualizzare tutte le possibili combinazioni di queste parole.
Un trie sta per tenere traccia della sequenza di lettere che compongono le parole,
diramazione quando necessario, quando una lettera può essere seguita da un multiplo di lettere,
e alla fine indicano in ogni punto se tale parola è valido o meno
perché se si sta ortografia della parola MAT, MA non credo che sia una parola valida, ma è MAT.
E così nel trie, indicherebbe che dopo MAT che in realtà è una parola valida.
Ogni nodo nella nostra trie è in realtà sta per contenere un array di puntatori del nodo,
e stiamo andando ad avere, in particolare, 27 di questi puntatori nodo,
uno per ogni lettera dell'alfabeto e il carattere di apostrofo.
Ogni elemento dell'array si sta andando a puntare su un altro nodo.
Quindi, se questo nodo è NULL, se non c'è niente dopo che,
allora sappiamo che non ci sono altre lettere in quella sequenza di parole.
Ma se questo nodo non è NULL, il che significa che ci sono più le lettere in quella sequenza di lettere.
E poi, inoltre, ogni nodo indica se è l'ultimo carattere di una parola o meno.
>> Andiamo in un esempio di un trie.
Per prima cosa hanno spazio per 27 nodi in questo array.
Se ho la parola BAR -
Se ho la BAR parola e voglio inserire che,
la prima lettera è B, quindi se la mia trie è vuota,
B è la seconda lettera dell'alfabeto, così ho intenzione di scegliere di mettere questa qui in questo indice.
Ho intenzione di avere B qui.
B sta per essere un nodo che punta ad un altro array di tutti i personaggi possibili
che può seguire dopo la lettera B.
In questo caso, ho a che fare con la BAR parola, quindi A andrà qui.
Dopo la A, io ho la lettera R, e allora A punti ora alla sua propria combinazione,
e poi R sarà qui.
BAR è una parola completa, così poi ho intenzione di avere punto R su un altro nodo
che dice che quella parola è valida.
Tale nodo è anche intenzione di avere un array di nodi,
ma quelli che potrebbero essere NULL.
Ma in fondo, si può continuare così.
Che diventerà un po 'più chiara quando andiamo in un altro esempio,
quindi basta portare con me lì.
Ora abbiamo BAR all'interno del nostro dizionario.
Ora dire che abbiamo il BAZ parola.
Si comincia con B, e abbiamo già B come una delle lettere che ci sono nel nostro dizionario.
Questo è seguito con A. Abbiamo già una.
Ma poi, invece, abbiamo seguito Z.
Allora un elemento della nostra matrice sarà Z,
e così allora che si sta per puntare a un altro termine valido della parola.
Così vediamo che, quando continuiamo a B e poi A,
ci sono due diverse opzioni attualmente in nostro dizionario per le parole che iniziano con B e A.
Dire abbiamo voluto inserire la parola FOOBAR.
Poi ci sarebbe una voce in F.
F è un nodo che indica tutta una serie.
Vorremmo trovare O, vai a O, O collega poi a tutta una serie.
Avremmo B e poi continuare, avremmo A e poi R.
Allora FooBar attraversa tutta la strada fino a quando FOOBAR è una parola corretta.
E così allora questo sarebbe una parola valida.
Ora dire che la nostra parola successiva nel dizionario è in realtà la parola FOO.
Diremmo F. ​​Quello che segue F?
Io in realtà già di uno spazio di O, così ho intenzione di continuare.
Non ho bisogno di fare una nuova. Continua.
FOO è una parola valida in questo dizionario, così poi ho intenzione di indicare
che valido.
Se mi fermo la mia sequenza lì, che sarebbe corretto.
Ma se abbiamo continuato la nostra sequenza da FOO fino a B
e appena avuto foob, foob non è una parola, e che non è indicato come uno valido.
In un trie, avete ogni nodo indica se si tratta di una parola valida o no,
e quindi ogni nodo ha anche una serie di 27 puntatori del nodo
che poi scegliere i nodi stessi.
>> Ecco un modo di come si potrebbe desiderare di definire questo.
Tuttavia, proprio come nell'esempio di tabella hash, dove abbiamo avuto una testa nodo *
per indicare l'inizio della nostra lista collegata, stiamo anche andando a voler
qualche modo di sapere dove l'inizio della nostra trie è.
Alcuni chiamano la gente cerca di alberi, ed è lì che viene dalla radice.
Quindi vogliamo la radice del nostro albero per fare in modo di rimanere a terra
alla tua destinazione è la nostra trie.
Abbiamo già andati oltre tipo di
il modo in cui si potrebbe pensare di caricare ogni parola nel dizionario.
In sostanza, per ogni parola che si sta andando a voler scorrere la tua trie
e sapendo che ogni elemento nei bambini - abbiamo chiamato i bambini in questo caso -
corrisponde ad una lettera diversa, si sta andando a voler controllare quei valori
in quel particolare indice che corrisponde alla lettera.
Quindi, pensare tutto il viaggio di ritorno a Cesare e Vigenère,
sapendo che ogni lettera è possibile tipo di carta torna ad un indice alfabetico,
sicuramente da A a Z sta per essere abbastanza facile per mappare una lettera alfabetica,
ma purtroppo, gli apostrofi sono anche un carattere accettato a parole.
Non sono nemmeno sicuro di quello che è il valore ASCII,
quindi per questo, se si vuole trovare un indice di decidere se si desidera essere il primo
o l'ultimo, dovrete fare un controllo hardcoded per tale
e poi mettere in indice 26 che, per esempio.
Allora si sta verificando il valore ai bambini [i]
in cui [i] corrisponde a qualsiasi lettera che ci sei.
Se questo è NULL, il che significa che non vi è al momento nessuna lettera possibili
derivante da quella sequenza precedente, in modo che stai andando a voler malloc
e fare un nuovo nodo e avere che i bambini [i] punto ad esso
in modo da creare - quando abbiamo inserito una lettera nel rettangolo -
rendere i bambini non NULL e il punto in quel nuovo nodo.
Ma se questo non è NULL, come nel nostro caso di FOO
quando abbiamo già avuto FOOBAR, continuiamo,
e non siamo mai fare un nuovo nodo, ma piuttosto semplice impostazione is_word su true
al termine di tale parola.
>> Allora come prima, perché qui hai a che fare con ogni lettera alla volta,
che sarà più facile per voi per le dimensioni, invece di dover calcolare
e passare attraverso l'intero albero e calcolare quanti bambini ho
e poi diramazione, ricordando quante sono sul lato sinistro e sul lato destro
e cose del genere, che sarà molto più facile per voi
se solo tenere traccia di quante parole si sta aggiungendo in
quando hai a che fare con il carico.
E così allora che le dimensioni così può semplicemente restituire una variabile globale di dimensioni.
>> Ora veniamo a controllare.
Stessi standard di prima, dove vogliamo consentire tra maiuscole e minuscole.
Inoltre, si assume che le stringhe sono solo caratteri alfabetici o gli apostrofi
perché i bambini è un array di 27 a lungo,
così tutte le lettere dell'alfabeto, più l'apostrofo.
Per controllare ciò che si vorrà fare è ti consigliamo di iniziare alla radice
perché la radice punterà a una matrice che contiene
tutte le possibili lettere iniziali di una parola.
Hai intenzione di cominciare da lì,
e poi si sta andando a controllare questo valore NULL o meno,
perché se il valore è NULL, che significa che il dizionario non ha alcun valore
che contengono tale lettera in questo ordine particolare.
Se è NULL, allora ciò significa che la parola è errata subito.
Ma se non è NULL, allora si può continuare,
dire che la prima lettera è una lettera prima possibile in una parola,
quindi ora voglio verificare se la seconda lettera, quella sequenza, è nel mio dizionario.
Quindi hai intenzione di andare a l'indice dei figli del primo nodo
e verificare se tale seconda lettera esiste.
Poi si ripete questo processo per verificare se tale sequenza è valido o meno
all'interno trie.
Ogni volta che i bambini che i nodi in punti indice a NULL,
si sa che quella sequenza non esiste,
ma poi, se si raggiunge la fine della parola che hai immesso,
poi si vuole verificare ora che ho completato questa sequenza
e ha trovato nel mio trie, quella parola è valida o no?
E così poi si vuole verificare che, e in quel momento, se hai trovato quella sequenza,
poi si vuole verificare se quella parola è valido o meno
perché ricordo indietro nel caso precedente che ho disegnato dove abbiamo avuto foob,
che era una sequenza valida che abbiamo trovato, ma non era una parola vera in sé valido.
>> Allo stesso modo, per lo scaricamento dei tentativi che si desidera scaricare tutti i nodi del trie.
Scusi. Simile alle tabelle hash in cui si scaricano liberati tutti i nodi,
nei tentativi vogliamo liberare anche tutti i nodi.
Scaricare potrà mai funzionare più semplice dal basso verso l'alto
perché queste sono liste essenzialmente legati.
Quindi vogliamo fare in modo che ci attacchiamo a tutti i valori
e libera tutti loro in modo esplicito.
Che cosa si sta andando a voler fare se si sta lavorando con un trie
è quello di viaggiare verso il basso e libera il nodo più basso prima possibile
e poi andare fino a tutti quei bambini e quindi liberare tutti coloro,
salire e poi libero, ecc
Un po 'come fare con il livello inferiore del primo trie
e poi andare sulla parte superiore una volta che hai liberato tutto.
Questo è un buon esempio di funzione ricorsiva in cui potrebbe tornare utile.
Una volta liberato lo strato inferiore del trie,
allora si chiama scaricare sul resto di esso,
facendo in modo che si libera ogni mini -
È possibile tipo di visualizzarlo come tentativi mini.
In modo da avere la tua radice qui.
Tento solo di semplificare in modo da non dover disegnare 26 di loro.
In modo da avere questi, e quindi questi rappresentano sequenze di parole
dove tutti questi piccoli cerchi sono lettere che sono sequenze valide di lettere.
Continuiamo solo un po 'di più.
Che cosa si sta andando a voler fare è libero nella parte inferiore qui e poi libera questa
e quindi liberare questo in fondo prima di liberare quello in alto qui
perché se qualcosa di gratuito nel secondo livello qui,
allora in realtà perderebbe il valore qui.
Ecco perché è importante per scaricare in un trie per assicurarsi che si libera la parte inferiore prima.
Cosa si potrebbe desiderare di fare è di dire per ogni nodo
Voglio scaricare tutti i bambini.
>> Ora che abbiamo superato lo scarico per il metodo della tabella di hash e il metodo di trie,
stiamo andando a voler guardare Valgrind.
Valgrind si esegue con i seguenti comandi.
Hai valgrind-v.
Stai controllando per tutte le perdite quando si esegue speller dato questo determinato testo
speller perché ha bisogno di prendere in un file di testo.
Così Valgrind verrà eseguito il programma, dire quanti byte è assegnato,
il numero di byte che hai liberato, e vi dirà se è liberato appena sufficiente
o se non hai abbastanza libero,
o, talvolta, si può anche troppo libero, come libero un nodo che è già stato liberato
e così si ritorna errori.
Se si utilizza Valgrind, vi darà alcuni messaggi
che indica se si è liberato o meno che sufficiente, sufficiente,
o più volte sufficiente.
>> Una parte di questo pset, è facoltativo per sfidare il Big Board.
Ma quando abbiamo a che fare con queste strutture di dati
è una specie di divertente vedere la rapidità e l'efficienza le strutture di dati potrebbe essere.
Il vostro risultato della funzione di hash in un sacco di collisioni?
O è la dimensione di dati davvero grande?
Ci vuole un sacco di tempo per attraversare?
Nel registro del correttore ortografico, emette quanto tempo si usa per caricare,
per controllare, per condurre dimensioni, e scaricare,
e così quelli che sono pubblicati in The Big Board,
dove si può competere contro i tuoi compagni di classe
e alcuni membri del personale per vedere chi è il più veloce correttore ortografico.
Una cosa che mi piacerebbe osservare sulle tabelle hash
è che ci sono alcune funzioni molto semplici hash che si possa pensare.
Per esempio, si hanno 26 secchi, e così ogni secchio
corrisponde alla prima lettera di una parola,
ma che sta per tradursi in una tabella piuttosto sbilanciato hash
perché ci sono molte meno parole che iniziano con X che iniziano con M, per esempio.
Un modo per andare su speller è che se si vuole ottenere tutte le funzionalità altra verso il basso,
poi basta usare una semplice funzione di hash per essere in grado di ottenere il vostro codice in esecuzione
e poi tornare indietro e modificare la dimensione della tabella hash e la definizione.
Ci sono un sacco di risorse su Internet per le funzioni hash,
e così per questo pset si è permesso di ricercare funzioni di hash su Internet
per alcuni suggerimenti e ispirazione fino a quando si dovrà essere indicato dove l'hai preso.
Ti invitiamo a guardare e interpretare una funzione di hash che si trova su Internet.
Torna a questo, si potrebbe essere in grado di vedere se qualcuno ha utilizzato un trie
se la loro applicazione è più veloce del hash table o meno.
Si può presentare al consiglio di Big più volte.
Si registra la sua entrata più recente.
Quindi forse si modifica la funzione di hash e poi rendersi conto che in realtà è molto più veloce
o molto più lento rispetto a prima.
Questo è un po 'un modo divertente.
C'è sempre 1 o 2 membri del personale che cercano di rendere il dizionario più lento possibile,
così che è sempre divertente da guardare.
>> L'utilizzo per la pset è si esegue correttore ortografico con un dizionario opzionale
e quindi un file di testo obbligatorio.
Per impostazione predefinita, quando si esegue correttore ortografico con un semplice file di testo e non si specifica un dizionario,
sta andando a utilizzare il file di testo dizionario, il grande
nella cartella cs50/pset5/dictionaries.
Che uno ha più di 100.000 parole.
Hanno anche un piccolo dizionario che ha molte meno parole
CS50 che ha fatto per voi.
Tuttavia, si può facilmente solo fare il proprio dizionario
se si desidera solo di lavorare in piccoli esempi -
per esempio, se si desidera utilizzare gdb e si conoscono i valori specifici
che si desidera che la tabella di hash per tracciare a.
Quindi, si può solo fare il proprio file di testo solo con la BAR, BAZ, PIPPO, e FOOBAR,
fare che in un file di testo, separare i ciascuna con 1 linea,
e poi fare il proprio file di testo che contiene solo letteralmente, forse 1 o 2 parole
in modo da sapere esattamente che cosa l'uscita dovrebbe essere.
Alcuni dei file di testo di esempio che The Big Board quando si esegue sfida verificherà
sono Guerra e pace e un romanzo di Jane Austen o qualcosa del genere.
Così, quando sei agli inizi, è molto più facile per rendere il vostro file di testo propri
che contengono solo un paio di parole o forse 10
in modo da poter prevedere ciò che il risultato dovrebbe essere
e quindi controllare contro che, quindi più di un esempio controllato.
E così da quando abbiamo a che fare con la previsione e disegnare le cose,
Voglio ancora una volta invitiamo a utilizzare carta e penna
perché è davvero intenzione di aiutare con questo -
disegnare le frecce, come la tabella di hash o come il vostro aspetto trie,
quando si sta liberando qualcosa in cui le frecce sono in corso,
si tiene a sufficienza, vedi tutti i link scomparendo
e cadere nell'abisso della memoria persa.
Quindi, per favore, prova a disegnare le cose prima ancora di arrivare alla scrittura di codice in basso.
Disegnare le cose in modo da capire come le cose stanno andando a lavorare
perché allora vi garantisco che incorrerà in pasticci puntatore meno lì.
>> Bene.
Voglio augurare il meglio di fortuna con questo pset.
E 'probabilmente la più difficile.
Quindi cercate di iniziare presto, disegnare le cose, disegnare le cose, e buona fortuna.
Questo era Walkthrough 5.
>> [CS50.TV]