1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Soluzione - Problema Set 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Harvard University]

3
00:00:04,870 --> 00:00:07,190
[Questo è CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Bene. Ciao a tutti, e benvenuti a Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 è Errori ortografici, in cui ci sarà fare un correttore ortografico.

6
00:00:17,400 --> 00:00:21,030
Controllo ortografico sono estremamente importanti.

7
00:00:21,030 --> 00:00:23,390
È mai capitato a voi?

8
00:00:23,390 --> 00:00:27,170
Si lavora molto, molto accumulano su una carta per uno scontro

9
00:00:27,170 --> 00:00:33,120
e poi ancora finisce per ottenere una luce molto rade come una D o una = D

10
00:00:33,120 --> 00:00:39,390
e tutto questo perché tu sei il liverwurst spoiler nella parola balena larga.

11
00:00:39,390 --> 00:00:44,710
Sì, correzione di bozze i peperoni è una questione di, l'impotenza assoluta.

12
00:00:44,710 --> 00:00:49,140
Questo è un problema che colpisce virili, studenti virili.

13
00:00:49,140 --> 00:00:56,260
Una volta mi fu detto dal mio torturatore grado sith che non avrei mai entrare in un buon collega.

14
00:00:56,260 --> 00:01:00,250
E questo è tutto quello che ho sempre voluto, è tutto quello che ogni bambino vuole, alla mia età,

15
00:01:00,250 --> 00:01:04,569
solo per entrare in un buon collega.

16
00:01:04,569 --> 00:01:12,720
E non solo qualsiasi collega. No. Volevo andare a un collega d'Avorio legale.

17
00:01:12,720 --> 00:01:18,360
Quindi, se non ho miglioramenti, sarebbe andato il mio sogno di andare a Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, o carcere - si sa, nella prigione, nel New Jersey.

19
00:01:22,730 --> 00:01:25,170
Così mi sono fatto un correttore ortografico.

20
00:01:25,170 --> 00:01:29,380
Questo è un estratto da un po 'dei miei artisti preferiti spoken word, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
In ogni caso, come dice lui, l'importanza di avere un correttore ortografico è molto importante.

22
00:01:34,630 --> 00:01:39,440
>> Quindi benvenuti a Walkthrough 5, in cui saremo a parlare di pset5: Errori ortografici,

23
00:01:39,440 --> 00:01:44,300
in cui ci sarà fare la nostra stessa correttore ortografico.

24
00:01:44,300 --> 00:01:50,880
La cassetta degli attrezzi per questa settimana, il codice di distribuzione, sarà importante guardare

25
00:01:50,880 --> 00:01:54,950
solo per capire le diverse funzioni che il dizionario sta per avere.

26
00:01:54,950 --> 00:02:01,500
Stiamo in realtà sta per essere avere più. File c che insieme rendono la nostra pset.

27
00:02:01,500 --> 00:02:05,420
E così guardando attraverso i diversi aspetti, anche se stiamo in realtà non modifica

28
00:02:05,420 --> 00:02:10,770
uno dei file, speller.c, sapendo come funziona in relazione alla dictionary.c,

29
00:02:10,770 --> 00:02:14,100
che ci sarà la scrittura, sarà molto importante.

30
00:02:14,100 --> 00:02:16,970
Le specifiche pset contiene anche un sacco di informazioni utili

31
00:02:16,970 --> 00:02:21,360
in termini di cose che si possono assumere, le regole e cose del genere,

32
00:02:21,360 --> 00:02:24,710
quindi assicuratevi di leggere con attenzione le specifiche pset per le punte.

33
00:02:24,710 --> 00:02:29,310
E in caso di dubbio di una regola o qualcosa di simile, quindi fare sempre riferimento alle specifiche pset

34
00:02:29,310 --> 00:02:31,550
o discutere.

35
00:02:31,550 --> 00:02:34,060
Questo pset sta andando fanno molto affidamento sui puntatori,

36
00:02:34,060 --> 00:02:37,890
quindi vogliamo essere sicuri di comprendere la differenza tra l'aggiunta di stelle

37
00:02:37,890 --> 00:02:41,680
davanti al nome del puntatore e commerciali e, come liberarli, ecc

38
00:02:41,680 --> 00:02:47,550
Quindi, essere un maestro di puntatori sta andando essere molto utile in questo set problema.

39
00:02:47,550 --> 00:02:50,460
Stiamo andando a guardare in liste collegate un po 'di più,

40
00:02:50,460 --> 00:02:57,790
dove abbiamo elementi che chiamiamo nodi che hanno sia un valore e un puntatore

41
00:02:57,790 --> 00:03:02,520
al nodo successivo, e così essenzialmente collegando diversi elementi uno dopo l'altro.

42
00:03:02,520 --> 00:03:07,190
Ci sono alcune opzioni differenti di attuazione il dizionario vero e proprio.

43
00:03:07,190 --> 00:03:13,150
Stiamo andando a guardare in due metodi principali, che sono le tabelle hash e poi cerca.

44
00:03:13,150 --> 00:03:17,660
In entrambi questi, che comportano una sorta di idea di una lista concatenata

45
00:03:17,660 --> 00:03:20,790
dove avete gli elementi collegati l'uno all'altro.

46
00:03:20,790 --> 00:03:25,640
E quindi stiamo andando a guardare su come si potrebbe essere in grado di operare intorno a liste collegate,

47
00:03:25,640 --> 00:03:29,680
crearli, navigare in termini di come, per esempio, inserire un nodo in esso

48
00:03:29,680 --> 00:03:32,760
o libero tutti i nodi pure.

49
00:03:32,760 --> 00:03:34,740
In termini di nodi di liberazione, che è veramente importante

50
00:03:34,740 --> 00:03:37,700
che ogni volta che la memoria malloc, poi lo libera.

51
00:03:37,700 --> 00:03:42,910
Quindi vogliamo fare in modo che nessun puntatore va unfreed, che noi non abbiamo perdite di memoria.

52
00:03:42,910 --> 00:03:48,330
Stiamo per introdurre uno strumento chiamato Valgrind che esegue il programma

53
00:03:48,330 --> 00:03:52,260
e verifica se la memoria allocata che si è poi liberato.

54
00:03:52,260 --> 00:03:59,080
Il pset è completo solo quando funziona e ha la piena funzionalità,

55
00:03:59,080 --> 00:04:03,990
ma anche, Valgrind ti dice che non hai trovato eventuali perdite di memoria.

56
00:04:03,990 --> 00:04:06,690
Infine, per questa pset, ci tengo a sottolineare -

57
00:04:06,690 --> 00:04:11,360
Voglio dire, come al solito, io sono sicuramente un sostenitore di usare carta e penna per le serie di problemi,

58
00:04:11,360 --> 00:04:14,840
ma per questo, penso che la penna e la carta sta per essere particolarmente importante

59
00:04:14,840 --> 00:04:19,000
quando si desidera essere disegnare frecce per le cose e capire come funzionano le cose.

60
00:04:19,000 --> 00:04:24,440
Quindi, provare ad utilizzare carta e penna per disegnare le cose prima di arrivare codifica

61
00:04:24,440 --> 00:04:26,970
perché potrebbe diventare un po 'disordinato.

62
00:04:26,970 --> 00:04:30,700
>> Per prima cosa, andiamo in liste concatenate un po '.

63
00:04:30,700 --> 00:04:35,510
Liste concatenate consistono di nodi, in cui ogni nodo ha un valore associato,

64
00:04:35,510 --> 00:04:39,810
così come un puntatore al nodo successivo dopo.

65
00:04:39,810 --> 00:04:43,680
Un paio di cose importanti con le liste concatenate sono che abbiamo bisogno di ricordare

66
00:04:43,680 --> 00:04:48,810
dove il nostro primo nodo è, e poi una volta che sappiamo dove il primo nodo è,

67
00:04:48,810 --> 00:04:52,990
in questo modo siamo in grado di accedere al nodo a cui punta il primo nodo a

68
00:04:52,990 --> 00:04:55,850
e poi quello dopo e quello dopo.

69
00:04:55,850 --> 00:05:00,340
E poi l'ultimo elemento nella lista concatenata è puntatore che nodo

70
00:05:00,340 --> 00:05:02,340
sta andando sempre per puntare a NULL.

71
00:05:02,340 --> 00:05:08,230
Quando un nodo punta a NULL, allora sapete che è stata raggiunta la fine della lista,

72
00:05:08,230 --> 00:05:12,320
che tale nodo è l'ultimo, che non c'è niente dopo.

73
00:05:12,320 --> 00:05:16,970
Qui, in questo schema, si vede che le frecce sono i puntatori,

74
00:05:16,970 --> 00:05:20,290
e la sezione blu è dove il valore viene memorizzato,

75
00:05:20,290 --> 00:05:24,420
e poi la scatola rossa con il puntatore è puntatore del nodo

76
00:05:24,420 --> 00:05:27,050
punta al nodo successivo dopo.

77
00:05:27,050 --> 00:05:33,730
E così che vedete qui, il nodo D ricorda a NULL, perché è l'ultimo elemento della lista.

78
00:05:33,730 --> 00:05:38,240
>> Diamo un'occhiata a come si potrebbe definire una struttura per un nodo.

79
00:05:38,240 --> 00:05:40,130
E poiché vogliamo avere più nodi,

80
00:05:40,130 --> 00:05:43,180
questo sta per diventare un typedef struct

81
00:05:43,180 --> 00:05:46,870
in cui stiamo andando ad avere diverse istanze di nodi.

82
00:05:46,870 --> 00:05:50,850
E così lo definiscono come un nuovo tipo di dati.

83
00:05:50,850 --> 00:05:53,630
Qui, abbiamo un nodo typedef struct.

84
00:05:53,630 --> 00:05:56,160
In questo esempio, abbiamo a che fare con i nodi interi,

85
00:05:56,160 --> 00:06:00,490
quindi abbiamo un valore intero di nome e poi abbiamo un altro puntatore,

86
00:06:00,490 --> 00:06:07,390
e in questo caso, è un puntatore a un nodo, quindi abbiamo un nodo struct * chiamata successiva.

87
00:06:07,390 --> 00:06:09,520
E poi stiamo chiamando questo nodo tutta la faccenda.

88
00:06:09,520 --> 00:06:11,110
Assicurarsi di seguire questa sintassi.

89
00:06:11,110 --> 00:06:17,940
Si noti che il nodo è in realtà fa riferimento sopra e sotto le parentesi graffe.

90
00:06:17,940 --> 00:06:23,400
Poi, per tenere traccia di dove il mio primo nodo è in questa lista collegata,

91
00:06:23,400 --> 00:06:29,390
poi ho un puntatore chiamato nodo testa, e malloc spazio sufficiente per le dimensioni di un nodo.

92
00:06:29,390 --> 00:06:36,240
Si noti, tuttavia, che la testa è in realtà un puntatore nodo invece di un vero e proprio nodo.

93
00:06:36,240 --> 00:06:40,130
Quindi la testa in realtà non contiene alcun valore,

94
00:06:40,130 --> 00:06:45,590
che punti solo per qualunque sia il primo nodo nella mia lista concatenata è.

95
00:06:55,080 --> 00:06:58,340
>> Per avere un migliore senso di liste collegate, perché è molto importante

96
00:06:58,340 --> 00:07:02,220
per tenere traccia di fare in modo di mantenere la catena,

97
00:07:02,220 --> 00:07:09,990
Mi piace pensare ad esso come persone in una linea tenendosi per mano,

98
00:07:09,990 --> 00:07:14,330
dove ogni persona è mano nella mano con il prossimo.

99
00:07:14,330 --> 00:07:18,350
Non si può vedere in questo disegno, ma in fondo che stanno puntando alla persona successiva

100
00:07:18,350 --> 00:07:23,760
che è nella loro catena.

101
00:07:23,760 --> 00:07:29,270
E quindi se si vuole attraversare una lista concatenata in cui queste persone -

102
00:07:29,270 --> 00:07:32,830
immaginare tutte queste persone hanno dei valori ad essi associati

103
00:07:32,830 --> 00:07:36,590
e anche il punto alla persona successiva nella linea -

104
00:07:36,590 --> 00:07:40,810
se si vuole attraversare la lista concatenata, per esempio, per modificare i valori del

105
00:07:40,810 --> 00:07:42,830
o la ricerca di un valore o qualcosa di simile,

106
00:07:42,830 --> 00:07:48,270
allora ti consigliamo di avere un puntatore alla persona specifica.

107
00:07:48,270 --> 00:07:52,670
Quindi stiamo andando ad avere un tipo di dati puntatore nodo.

108
00:07:52,670 --> 00:07:55,580
Per questo esempio, chiamiamolo cursore.

109
00:07:55,580 --> 00:07:59,630
Un altro modo comune per denominare questo sarebbe iteratore o qualcosa del genere

110
00:07:59,630 --> 00:08:05,130
perché è l'iterazione di realtà in movimento e quale nodo sta indicando.

111
00:08:05,130 --> 00:08:14,410
Questo qui sarà il nostro cursore.

112
00:08:14,410 --> 00:08:20,180
Il nostro cursore in primo luogo puntare al primo elemento nella nostra lista.

113
00:08:20,180 --> 00:08:26,910
E così quello che vogliamo fare è che sarebbe fondamentalmente continuerà il cursore,

114
00:08:26,910 --> 00:08:29,130
spostandola da un lato all'altro.

115
00:08:29,130 --> 00:08:33,409
In questo caso, vogliamo spostare all'elemento successivo nella lista.

116
00:08:33,409 --> 00:08:38,480
Con gli array, quello che vorrei fare è che sarebbe solo dire che aumentare l'indice di 1.

117
00:08:38,480 --> 00:08:46,020
In questo caso, quello che dobbiamo fare è trovare quale persona in realtà questa persona corrente sta puntando,

118
00:08:46,020 --> 00:08:48,930
e questo sarà il valore successivo.

119
00:08:48,930 --> 00:08:53,230
Quindi, se il cursore è solo un puntatore nodo, allora che cosa vogliamo fare

120
00:08:53,230 --> 00:08:56,320
è che vuole ottenere il valore che il cursore sia puntato.

121
00:08:56,320 --> 00:09:01,350
Vogliamo arrivare a quel nodo e poi, una volta che siamo in quel nodo, trovare dove sta indicando.

122
00:09:01,350 --> 00:09:05,820
Per arrivare al nodo reale che il cursore sia puntato,

123
00:09:05,820 --> 00:09:13,160
di solito noi lo indichiamo con (* cursore).

124
00:09:13,160 --> 00:09:19,160
Ciò vi darà il nodo vero che il cursore sia puntato.

125
00:09:19,160 --> 00:09:21,730
E poi, dopo che, quello che vogliamo fare è si vuole accedere

126
00:09:21,730 --> 00:09:25,680
qualunque cosa questo valore successivo nodo è.

127
00:09:25,680 --> 00:09:32,820
Per fare questo, per accedere ai valori all'interno della struttura, abbiamo l'operatore punto.

128
00:09:32,820 --> 00:09:39,530
Così allora sarebbe (cursore *). Prossimo.

129
00:09:39,530 --> 00:09:44,840
Ma questo è un po 'confuso in termini di avere le parentesi intorno al cursore *,

130
00:09:44,840 --> 00:09:56,800
e così sostituire questa affermazione tutto con il cursore->.

131
00:09:56,800 --> 00:10:02,700
Si tratta di un trattino e poi il segno più grande, in modo da fare una freccia.

132
00:10:02,700 --> 00:10:05,840
cursore-> successivo.

133
00:10:05,840 --> 00:10:12,390
Che in realtà farti il ​​nodo che il cursore si. Tale valore è di prossimo.

134
00:10:12,390 --> 00:10:16,790
Così, invece di avere la stella e il punto, che si sta sostituendo con una freccia.

135
00:10:16,790 --> 00:10:24,820
State molto attenti a fare in modo che si tenta di utilizzare questa sintassi.

136
00:10:33,550 --> 00:10:37,620
>> Ora che abbiamo il nostro cursore, se vogliamo accedere al valore,

137
00:10:37,620 --> 00:10:40,450
prima, abbiamo avuto cursore-> next,

138
00:10:40,450 --> 00:10:46,260
ma per accedere al valore al nodo che il cursore sia puntato, abbiamo semplicemente dire

139
00:10:46,260 --> 00:10:48,070
node-> valore.

140
00:10:48,070 --> 00:10:53,600
Da lì, è del tipo di dati tutto ciò che abbiamo definito i valori ed i nodi di essere.

141
00:10:53,600 --> 00:10:59,620
Se si tratta di un nodo int, quindi cursore-> valore è solo andare a essere un numero intero.

142
00:10:59,620 --> 00:11:04,870
Così siamo in grado di fare operazioni su questo, verificare uguaglianze, assegna valori diversi, ecc

143
00:11:04,870 --> 00:11:11,090
E allora che cosa si vuole fare, se si desidera spostare il cursore alla prossima persona,

144
00:11:11,090 --> 00:11:15,270
effettivamente modificare il valore del cursore.

145
00:11:15,270 --> 00:11:19,340
Dal momento che il cursore è un puntatore nodo, è possibile modificare l'indirizzo effettivo del puntatore

146
00:11:19,340 --> 00:11:23,890
per l'indirizzo del nodo successivo nella lista.

147
00:11:23,890 --> 00:11:28,930
Questo è solo un po 'di codice in cui si può scorrere.

148
00:11:28,930 --> 00:11:31,230
Dove ho il commento fare qualcosa,

149
00:11:31,230 --> 00:11:33,850
è lì che probabilmente stai andando per accedere al valore

150
00:11:33,850 --> 00:11:37,850
o fare qualcosa a che fare con quel nodo specifico.

151
00:11:37,850 --> 00:11:43,050
Per iniziare il tutto, io dico che il mio cursore inizialmente

152
00:11:43,050 --> 00:11:48,430
sta per puntare al primo elemento della lista collegata.

153
00:11:48,430 --> 00:11:52,910
E così avanti, l'ho definito come il capo del nodo.

154
00:11:52,910 --> 00:11:57,610
>> Come ho detto prima, liberando è veramente importante.

155
00:11:57,610 --> 00:12:02,440
Si vuole fare in modo che si liberare ogni elemento della lista una volta che hai finito con esso.

156
00:12:02,440 --> 00:12:04,940
Quando non è necessario fare riferimento a uno qualsiasi di questi puntatori più,

157
00:12:04,940 --> 00:12:10,620
si vuole fare in modo che si liberi tutti questi puntatori.

158
00:12:10,620 --> 00:12:14,460
Ma si vuole essere molto attenti qui a che si vuole evitare perdite di memoria.

159
00:12:14,460 --> 00:12:25,080
Se si libera una persona prematuramente, allora tutti i puntatori che che i punti di nodo per

160
00:12:25,080 --> 00:12:26,900
stanno per essere persi.

161
00:12:26,900 --> 00:12:32,070
Tornando all'esempio persona per renderlo un po 'più alta posta in gioco,

162
00:12:32,070 --> 00:12:49,600
vediamo quali sono queste persone, solo che in questo caso sono in bilico su un lago con un mostro.

163
00:12:49,600 --> 00:12:53,200
Vogliamo fare in modo che ogni volta che liberare, non perdiamo

164
00:12:53,200 --> 00:12:58,920
e lasciare andare tutti i nodi prima di aver effettivamente liberato.

165
00:12:58,920 --> 00:13:05,730
Per esempio, se si dovesse chiamare semplicemente gratuitamente su questo tizio qui,

166
00:13:05,730 --> 00:13:15,350
allora sarebbe stato liberato, ma poi tutti questi ragazzi verrebbe allora meno

167
00:13:15,350 --> 00:13:18,450
e avrebbero deriva fuori e cadere.

168
00:13:18,450 --> 00:13:24,900
Così vuole fare in modo che, invece, vogliamo mantenere un collegamento con il resto.

169
00:13:37,630 --> 00:13:42,480
Il puntatore di testa, che punta al primo elemento della lista.

170
00:13:42,480 --> 00:13:49,990
E 'un po' come una corda di ancoraggio prima persona.

171
00:13:52,870 --> 00:13:57,470
Cosa si potrebbe desiderare di fare quando si libera un elenco è di avere -

172
00:13:57,470 --> 00:14:04,520
Se si desidera liberare il primo elemento, quindi si può avere un puntatore temporaneo

173
00:14:04,520 --> 00:14:07,370
che punta a qualsiasi primo elemento è.

174
00:14:07,370 --> 00:14:11,420
In modo da avere il puntatore temporaneo che punta qui.

175
00:14:11,420 --> 00:14:15,840
In questo modo, si ha una tenuta del primo nodo.

176
00:14:15,840 --> 00:14:18,930
E poi, dal momento che sappiamo che il primo nodo sta per essere liberato,

177
00:14:18,930 --> 00:14:24,890
allora possiamo spostare questa corda, questa ancora, la nostra testa,

178
00:14:24,890 --> 00:14:31,930
per puntare effettivamente a qualunque il primo sta puntando.

179
00:14:31,930 --> 00:14:38,760
Quindi, questa testa fa effettivamente al secondo elemento ora.

180
00:14:38,760 --> 00:14:43,980
Ora ci è consentito di liberare ciò che è memorizzato in temperatura,

181
00:14:43,980 --> 00:14:53,360
e così siamo in grado di cancellare che senza di essa mettere in pericolo tutti gli altri nodi nella nostra lista.

182
00:14:54,140 --> 00:15:05,020
Un altro modo che si possa fare questo potrebbe essere

183
00:15:05,020 --> 00:15:08,650
ogni volta che si libera solo l'ultimo elemento della lista

184
00:15:08,650 --> 00:15:11,010
perché la garanzia di non essere indicato nulla.

185
00:15:11,010 --> 00:15:15,570
Quindi, si può solo liberare questa, poi libero questo, poi libero questo.

186
00:15:15,570 --> 00:15:21,900
Che funziona sicuramente, ma è un po 'più lento perché dalla natura delle liste collegate,

187
00:15:21,900 --> 00:15:24,670
non possiamo immediatamente saltare l'ultimo.

188
00:15:24,670 --> 00:15:28,030
Dobbiamo attraversare ogni elemento della lista concatenata

189
00:15:28,030 --> 00:15:31,020
e verificare se quello che punta a NULL, controllare ogni volta,

190
00:15:31,020 --> 00:15:33,780
e poi una volta si arriva alla fine, quindi gratuito che.

191
00:15:33,780 --> 00:15:40,270
Se si dovesse fare questo processo, si sarebbe in realtà essere il controllo qui,

192
00:15:40,270 --> 00:15:44,190
verifica qui, poi il controllo qui, liberandola,

193
00:15:44,190 --> 00:15:47,470
poi tornare indietro, controllando qui, controllare qui, liberandola,

194
00:15:47,470 --> 00:15:49,660
controllo qui, e quindi liberando.

195
00:15:49,660 --> 00:15:52,880
Ci vuole un po 'più. Gia '.

196
00:15:52,880 --> 00:15:59,060
>> [Studente] Sarebbe possibile fare una lista collegata che memorizza un puntatore di uscita fino alla fine?

197
00:15:59,060 --> 00:16:01,320
Questo sarebbe sicuramente possibile.

198
00:16:01,320 --> 00:16:08,340
Ripetere la domanda, è possibile avere una struttura elenco collegato

199
00:16:08,340 --> 00:16:12,490
in modo tale che si ha un puntatore che indica la fine della lista collegata?

200
00:16:12,490 --> 00:16:18,090
Direi che è possibile, e ogni volta che si inserisce qualcosa nella tua lista concatenata

201
00:16:18,090 --> 00:16:21,470
si dovrebbe aggiornare tale puntatore e cose del genere.

202
00:16:21,470 --> 00:16:26,640
Si potrebbe avere una coda nodo *, per esempio.

203
00:16:26,640 --> 00:16:29,840
Ma quando si sta implementando questa funzione, si deve pensare al trade-off,

204
00:16:29,840 --> 00:16:32,700
come quante volte faccio a essere l'iterazione di questo,

205
00:16:32,700 --> 00:16:36,100
Quanto è difficile sarà per tenere traccia della coda e la testa

206
00:16:36,100 --> 00:16:38,400
così come il mio iteratore, e cose del genere.

207
00:16:40,730 --> 00:16:42,480
Ritiene che -? >> [Studente] Si '.

208
00:16:42,480 --> 00:16:48,270
E 'possibile, ma in termini di decisioni di progettazione, è necessario valutare le opzioni.

209
00:16:53,850 --> 00:17:01,090
>> Qui è uno scheletro di codice che permetterebbe di liberare ogni elemento in una lista concatenata.

210
00:17:01,090 --> 00:17:05,460
Anche in questo caso, dato che sono l'iterazione di una lista collegata, ho intenzione di voler avere un qualche tipo di cursore

211
00:17:05,460 --> 00:17:08,670
o iteratore.

212
00:17:08,670 --> 00:17:14,640
Siamo l'iterazione fino a quando il cursore è NULL.

213
00:17:14,640 --> 00:17:17,640
Se non si desidera scorrere quando il cursore è NULL

214
00:17:17,640 --> 00:17:20,579
perché significa che non c'è niente nella lista.

215
00:17:20,579 --> 00:17:25,069
Allora qui faccio un nodo temporaneo *

216
00:17:25,069 --> 00:17:29,610
indicando quello che sto considerando è il primo della mia lista,

217
00:17:29,610 --> 00:17:35,340
e poi muovo il cursore avanti 1 e quindi liberare tutto quello che avevo nella memoria temporanea.

218
00:17:38,460 --> 00:17:43,650
>> Ora veniamo a inserimento in liste concatenate.

219
00:18:00,200 --> 00:18:09,660
Ho tre nodi nella mia lista concatenata, e andiamo con il caso semplice

220
00:18:09,660 --> 00:18:18,970
dove vogliamo inserire un altro nodo alla fine della nostra lista collegata.

221
00:18:18,970 --> 00:18:25,980
Per fare questo, tutto quello che vorrei fare è che si attraversano

222
00:18:25,980 --> 00:18:32,100
per trovare dove la fine attuale della lista collegata è, quindi qualunque nodo è che punta a NULL -

223
00:18:32,100 --> 00:18:33,850
che è questa -

224
00:18:33,850 --> 00:18:37,260
e poi dire, in realtà, questo non sarà l'ultimo nodo;

225
00:18:37,260 --> 00:18:39,830
stiamo in realtà sta per avere un altro.

226
00:18:39,830 --> 00:18:46,260
Così avremmo questa corrente un punto a tutto ciò che state inserendo.

227
00:18:46,260 --> 00:18:50,080
Così ora questa persona rosso diventa qui l'ultimo nodo della lista collegata.

228
00:18:50,080 --> 00:18:56,080
E così la caratteristica dell'ultimo nodo nella lista collegata è che si punta a NULL.

229
00:18:56,080 --> 00:19:09,380
E allora cosa dovremmo fare è impostare il puntatore di questo ragazzo del rosso a NULL. Ecco.

230
00:19:09,380 --> 00:19:25,370
>> Ma se volessimo inserire un nodo tra la seconda e la terza?

231
00:19:25,370 --> 00:19:28,960
Quello non è così semplice, perché vogliamo fare in modo

232
00:19:28,960 --> 00:19:34,290
che non lasciar andare qualsiasi nodo nella nostra lista collegata.

233
00:19:34,290 --> 00:19:43,450
Quello che avrebbe dovuto fare è fare in modo che noi stessi ancorare a ciascuno.

234
00:19:43,450 --> 00:19:49,900
Per esempio, chiamiamo questo il secondo.

235
00:19:49,900 --> 00:19:54,390
Se hai detto che la seconda ora punta a questa nuova

236
00:19:54,390 --> 00:20:02,520
e hai appena fatto un puntatore lì, allora che si tradurrebbe in questo ragazzo la perdita

237
00:20:02,520 --> 00:20:07,830
perché non c'è alcun legame con lui.

238
00:20:07,830 --> 00:20:18,970
Invece - Io disegnare questo nuovo. Scusate le mie capacità artistiche.

239
00:20:18,970 --> 00:20:26,570
Sappiamo che non possiamo collegare direttamente 2 a quella nuova.

240
00:20:26,570 --> 00:20:30,480
Dobbiamo fare in modo di trattenere l'ultimo.

241
00:20:30,480 --> 00:20:39,200
Quello che potrebbe desiderare di fare è avere un puntatore temporaneo

242
00:20:39,200 --> 00:20:42,650
per l'elemento che sta per essere aggiunto su.

243
00:20:42,650 --> 00:20:45,140
Allora abbiamo un puntatore temporaneo lì.

244
00:20:45,140 --> 00:20:50,780
Poiché sappiamo che questo terzo viene tenuto traccia di,

245
00:20:50,780 --> 00:20:53,680
2 può ora collegarsi al nostro unico nuovo.

246
00:20:53,680 --> 00:20:57,490
E se questo nuovo ragazzo rosso sta per essere tra 2 e 3,

247
00:20:57,490 --> 00:21:05,550
allora ciò che è il puntatore che tizio sta per puntare a? >> [Studente] temp.

248
00:21:05,550 --> 00:21:07,490
Temp. Gia '.

249
00:21:07,490 --> 00:21:15,430
Allora valore successivo questo tizio rosso sta per essere temp.

250
00:21:26,090 --> 00:21:33,010
Quando si inserisce in liste collegate, abbiamo visto che abbiamo potuto

251
00:21:33,010 --> 00:21:38,260
facilmente aggiungere qualcosa alla fine con la creazione di un array temporaneo,

252
00:21:38,260 --> 00:21:42,850
o se volevamo aggiungere qualcosa in mezzo la nostra gamma,

253
00:21:42,850 --> 00:21:46,810
allora ci vorrebbe un po 'di più in giro per mischiare.

254
00:21:46,810 --> 00:21:50,240
Se si vuole, per esempio, hanno una lista ordinata collegata,

255
00:21:50,240 --> 00:21:54,880
poi si deve tipo di valutare i costi ei benefici di tale

256
00:21:54,880 --> 00:21:59,720
perché se si vuole avere un array ordinato, il che significa che ogni volta che si inserisce in esso,

257
00:21:59,720 --> 00:22:01,630
sta andando a prendere un po 'più.

258
00:22:01,630 --> 00:22:05,500
Tuttavia, se si vuole in seguito, come troveremo vorremo,

259
00:22:05,500 --> 00:22:10,280
ricerca attraverso una lista concatenata, allora potrebbe essere più facile se si sa che tutto è in ordine.

260
00:22:10,280 --> 00:22:15,340
Così si potrebbe desiderare di valutare i costi ei benefici di questo.

261
00:22:20,150 --> 00:22:27,740
>> Un altro modo per inserire in una lista collegata è da inserire dall'inizio di un elenco.

262
00:22:27,740 --> 00:22:34,700
Se tracciamo la nostra ancora qui - questo è il nostro capo -

263
00:22:34,700 --> 00:22:40,960
e poi hanno queste persone ad esso collegate,

264
00:22:40,960 --> 00:22:48,460
e poi abbiamo un nuovo nodo da inserire all'inizio,

265
00:22:48,460 --> 00:22:52,590
allora che cosa potrebbe che vogliamo fare?

266
00:22:55,220 --> 00:23:03,580
Che cosa ci sarebbe di male solo dicendo che voglio collegare il rosso al blu,

267
00:23:03,580 --> 00:23:05,790
perché questo è il primo?

268
00:23:05,790 --> 00:23:08,570
Cosa sarebbe successo qui?

269
00:23:08,570 --> 00:23:12,130
Tutti questi tre sarebbero persi.

270
00:23:12,130 --> 00:23:14,140
Quindi non vogliamo farlo.

271
00:23:14,140 --> 00:23:21,430
Ancora una volta, abbiamo imparato che abbiamo bisogno di avere un qualche tipo di puntatore temporaneo.

272
00:23:21,430 --> 00:23:34,470
Scegliamo di avere un punto temporaneo a questo ragazzo.

273
00:23:34,470 --> 00:23:39,640
Quindi possiamo avere il blu un punto alla temporanea

274
00:23:39,640 --> 00:23:43,240
e poi il punto rosso al blu.

275
00:23:43,240 --> 00:23:47,830
Il motivo per cui sto usando la gente qui è perché vogliamo davvero visualizzare

276
00:23:47,830 --> 00:23:53,180
aggrappandosi alle persone e fare in modo che abbiamo un link a loro

277
00:23:53,180 --> 00:23:57,590
prima di lasciare andare un'altra mano o qualcosa del genere.

278
00:24:05,630 --> 00:24:10,650
>> Ora che abbiamo un senso di liste concatenate - come si potrebbe creare una lista concatenata

279
00:24:10,650 --> 00:24:15,090
e creare le strutture per quella consistente nella definizione di tipo per un nodo

280
00:24:15,090 --> 00:24:19,060
e poi fare in modo che abbiamo un puntatore alla testa di tale lista concatenata -

281
00:24:19,060 --> 00:24:23,210
una volta che abbiamo e sappiamo come attraversare attraverso un array,

282
00:24:23,210 --> 00:24:28,200
accedere a vari elementi, sappiamo come inserire e sappiamo come liberarli,

283
00:24:28,200 --> 00:24:30,260
allora possiamo entrare in errori di ortografia.

284
00:24:30,260 --> 00:24:38,150
Come al solito, abbiamo una sezione di domande che avranno utilizzato per operare con liste concatenate

285
00:24:38,150 --> 00:24:41,750
e diverse strutture, come le code e stack.

286
00:24:41,750 --> 00:24:46,000
Quindi siamo in grado di muoversi in errori di ortografia.

287
00:24:46,000 --> 00:24:55,170
>> Errori ortografici ha il codice di distribuzione un paio di file di importanza.

288
00:24:55,170 --> 00:24:58,850
In primo luogo notiamo che abbiamo questo Makefile qui,

289
00:24:58,850 --> 00:25:03,040
che non abbiamo veramente incontrato prima.

290
00:25:03,040 --> 00:25:10,090
Se si guarda all'interno della cartella pset5, avresti notato che si dispone di un file. H,

291
00:25:10,090 --> 00:25:12,530
allora ci sono due file. c.

292
00:25:12,530 --> 00:25:18,920
Quello che fa è Makefile prima, ci basta digitare marca e poi il nome del programma

293
00:25:18,920 --> 00:25:25,550
e poi vedremmo tutti questi argomenti e bandiere passato al compilatore.

294
00:25:25,550 --> 00:25:30,580
Quello che il Makefile fa è ci permette di compilare più file in una sola volta

295
00:25:30,580 --> 00:25:34,650
e passare le bandiere che vogliamo.

296
00:25:34,650 --> 00:25:41,300
Qui dobbiamo solo vedere che c'è un file di intestazione qui.

297
00:25:41,300 --> 00:25:43,730
Poi in realtà abbiamo due file di origine.

298
00:25:43,730 --> 00:25:47,520
Abbiamo speller.c e dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Siete invitati a modificare il Makefile se lo si desidera.

300
00:25:54,560 --> 00:26:03,310
Si noti che qui, se si digita pulita, quindi ciò che fa è in realtà qualcosa che non rimuove

301
00:26:03,310 --> 00:26:06,340
che è il nucleo.

302
00:26:06,340 --> 00:26:09,190
Se hai un errore di segmentazione, in pratica si ottiene un core dump.

303
00:26:09,190 --> 00:26:13,260
Quindi questo file po 'brutto apparirà nella directory chiamato core.

304
00:26:13,260 --> 00:26:16,310
Ti consigliamo di rimuovere tale per farlo pulire.

305
00:26:16,310 --> 00:26:20,940
Rimuove tutti i file exe e. File o.

306
00:26:27,900 --> 00:26:30,220
>> Diamo uno sguardo in dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Questo dice che dichiara la funzionalità di un dizionario.

308
00:26:34,410 --> 00:26:39,530
Abbiamo una lunghezza massima per ogni parola nel dizionario.

309
00:26:39,530 --> 00:26:45,130
Diciamo che questa sarà la parola più lunga possibile. E 'di lunghezza 45.

310
00:26:45,130 --> 00:26:48,900
Quindi non stai andando ad avere tutte le parole che superano tale lunghezza.

311
00:26:48,900 --> 00:26:50,980
Qui dobbiamo solo i prototipi di funzione.

312
00:26:50,980 --> 00:26:55,290
Non abbiamo l'effettiva attuazione perché è quello che faremo per questo pset.

313
00:26:55,290 --> 00:26:59,940
Ma ciò che questo non fa altro che da quando abbiamo a che fare con file di grandi dimensioni qui

314
00:26:59,940 --> 00:27:06,650
e la funzionalità su scala più ampia, è utile disporre di un file. h

315
00:27:06,650 --> 00:27:11,290
in modo che qualcun altro leggere o utilizzare il codice in grado di capire cosa sta succedendo.

316
00:27:11,290 --> 00:27:17,910
E forse vogliono implementare cerca se avete fatto le tabelle hash o viceversa.

317
00:27:17,910 --> 00:27:21,850
Poi dicevano la mia funzione di carico,

318
00:27:21,850 --> 00:27:26,950
l'effettiva attuazione sta per diverso, ma questo prototipo non cambierà.

319
00:27:26,950 --> 00:27:33,280
Qui abbiamo verificare, che restituisce true se una data parola è nel dizionario.

320
00:27:33,280 --> 00:27:39,800
Poi abbiamo il carico, che è quasi esclusivamente in un file dizionario

321
00:27:39,800 --> 00:27:44,360
e quindi carica in una qualche struttura dati.

322
00:27:44,360 --> 00:27:47,500
Abbiamo dimensioni, che, quando viene chiamato, restituisce la dimensione del dizionario,

323
00:27:47,500 --> 00:27:50,310
quante parole sono memorizzati in esso,

324
00:27:50,310 --> 00:27:54,390
e poi scaricare, che libera tutta la memoria che si possono avere preso

325
00:27:54,390 --> 00:27:57,900
rendendo il dizionario.

326
00:28:01,070 --> 00:28:03,590
>> Diamo un'occhiata a dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Vediamo che sembra molto simile a dictionary.h, solo che adesso ha solo tutte queste TODOs in esso.

328
00:28:10,490 --> 00:28:16,980
E perché è il tuo lavoro. Alla fine, ti verrà compilando speller.c con tutto questo codice.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, quando viene eseguito, non è realmente intenzione di fare nulla,

330
00:28:21,540 --> 00:28:29,590
in modo da guardare verso speller.c per vedere l'effettiva attuazione del correttore ortografico.

331
00:28:29,590 --> 00:28:32,060
Anche se non avete intenzione di essere qualsiasi modifica di questo codice,

332
00:28:32,060 --> 00:28:38,050
è importante leggere, capire quando è carico chiamasse, quando sto chiamando controllo,

333
00:28:38,050 --> 00:28:42,350
solo per capire, mappa fuori, vedere come la funzione lavora.

334
00:28:42,350 --> 00:28:49,860
Si vede che è il controllo per l'utilizzo corretto.

335
00:28:49,860 --> 00:28:55,200
In sostanza, quando qualcuno corre correttore ortografico, questo indica che è opzionale

336
00:28:55,200 --> 00:29:00,950
per loro di passare in un file di dizionario, perché ci sarà un file dizionario predefinito.

337
00:29:00,950 --> 00:29:05,410
E poi devono passare il testo da eseguire il controllo ortografico.

338
00:29:05,410 --> 00:29:11,410
Offerte rusage con il tempo perché una parte di questa pset cui ci occuperemo più avanti

339
00:29:11,410 --> 00:29:14,790
non è solo ottenere un funzionamento correttore ortografico di lavoro

340
00:29:14,790 --> 00:29:17,190
ma in realtà sempre per essere veloce.

341
00:29:17,190 --> 00:29:22,040
E così allora è lì che rusage sta per entrare

342
00:29:22,040 --> 00:29:28,740
Qui vediamo la prima chiamata a uno dei nostri file dictionary.c, che è carico.

343
00:29:28,740 --> 00:29:34,720
Carico restituisce true o false - true in caso di successo, false in caso di errore.

344
00:29:34,720 --> 00:29:41,400
Quindi, se il dizionario non è stato caricato correttamente, il speller.c restituirà 1 e uscire.

345
00:29:41,400 --> 00:29:47,920
Ma se viene caricato correttamente, allora è destinata a continuare.

346
00:29:47,920 --> 00:29:50,740
Proseguiamo, e vediamo un po 'di file I / O qui,

347
00:29:50,740 --> 00:29:56,210
dove sta andando a che fare con l'apertura del file di testo.

348
00:29:56,210 --> 00:30:04,640
Ecco, cosa che fa è ortografico controlla ogni singola parola nel testo.

349
00:30:04,640 --> 00:30:09,270
Così che cosa sta facendo speller.c proprio qui è l'iterazione di ciascuna delle parole nel file di testo

350
00:30:09,270 --> 00:30:12,790
e poi controllando nel dizionario.

351
00:30:24,680 --> 00:30:32,350
Qui, abbiamo un valore booleano errori di ortografia che vedrà se il controllo restituisce vero o no.

352
00:30:32,350 --> 00:30:37,110
Se la parola è in realtà nel dizionario, allora controllo restituirà true.

353
00:30:37,110 --> 00:30:39,760
Ciò significa che la parola non è errato.

354
00:30:39,760 --> 00:30:45,330
Così errata sarebbe falsa, ed è per questo che abbiamo il botto lì, l'indicazione.

355
00:30:45,330 --> 00:30:56,320
Continuiamo ad andare, e quindi tiene traccia del numero di parole errate

356
00:30:56,320 --> 00:30:58,910
ci sono nel file.

357
00:30:58,910 --> 00:31:03,870
Si prosegue e chiude il file.

358
00:31:03,870 --> 00:31:09,250
Poi qui, riporta il numero di parole errate hai avuto.

359
00:31:09,250 --> 00:31:12,680
Si calcola la quantità di tempo impiegato per caricare il dizionario,

360
00:31:12,680 --> 00:31:15,080
quanto tempo ci ha portato a controllare,

361
00:31:15,080 --> 00:31:18,510
quanto tempo impiegato per calcolare la dimensione,

362
00:31:18,510 --> 00:31:21,260
che, come vedremo avanti, dovrebbe essere molto piccola,

363
00:31:21,260 --> 00:31:25,390
e quindi la quantità di tempo impiegato per scaricare il dizionario.

364
00:31:25,390 --> 00:31:27,700
Qui sopra vediamo la chiamata a scaricare qui.

365
00:31:27,700 --> 00:31:52,690
Se controlliamo per la dimensione qui,

366
00:31:52,690 --> 00:31:59,050
poi si vede che è qui chiamata alla dimensione dove si determina la dimensione del dizionario.

367
00:32:05,730 --> 00:32:07,100
Awesome.

368
00:32:07,100 --> 00:32:10,920
>> Il nostro compito per questa pset è quello di implementare il carico, che caricherà il dizionario

369
00:32:10,920 --> 00:32:15,480
struttura dei dati - a seconda di quale si sceglie, sia esso una tabella di hash o un tentativo -

370
00:32:15,480 --> 00:32:18,810
con le parole del file di dizionario.

371
00:32:18,810 --> 00:32:25,290
Poi ci sono dimensioni, che restituirà il numero di parole nel dizionario.

372
00:32:25,290 --> 00:32:29,860
E se si implementa il carico in modo intelligente, quindi taglia dovrebbe essere abbastanza facile.

373
00:32:29,860 --> 00:32:33,860
Allora avete controllo, che controllerà se una data parola è nel dizionario.

374
00:32:33,860 --> 00:32:38,690
Così speller.c passa in una stringa, e poi si deve verificare se la stringa

375
00:32:38,690 --> 00:32:41,610
sono contenuti nel vostro dizionario.

376
00:32:41,610 --> 00:32:46,750
Si noti che in genere hanno dizionari standard,

377
00:32:46,750 --> 00:32:53,020
ma in questo pset, in pratica qualsiasi dizionario passato in in qualsiasi lingua.

378
00:32:53,020 --> 00:32:57,040
Quindi non possiamo dare per scontato che la parola la si trova all'interno.

379
00:32:57,040 --> 00:33:03,090
Il FOOBAR parola potrebbe essere definito in un dizionario certo che passiamo trovi

380
00:33:03,090 --> 00:33:07,920
E poi abbiamo scaricare, che libera il dizionario dalla memoria.

381
00:33:07,920 --> 00:33:11,930
>> In primo luogo, vorrei andare oltre il metodo hash table

382
00:33:11,930 --> 00:33:14,630
su come si possano implementare tutte queste quattro funzioni,

383
00:33:14,630 --> 00:33:18,650
e poi vado sul metodo di prova, il modo in cui attuare queste quattro funzioni,

384
00:33:18,650 --> 00:33:22,720
e alla fine il discorso su alcuni suggerimenti generali quando si sta facendo la pset

385
00:33:22,720 --> 00:33:27,870
e anche come si potrebbe essere in grado di utilizzare Valgrind per verificare la presenza di perdite di memoria.

386
00:33:27,870 --> 00:33:30,550
>> Entriamo nel metodo tabella hash.

387
00:33:30,550 --> 00:33:35,910
Una tabella hash è costituito da un elenco di secchi.

388
00:33:35,910 --> 00:33:43,010
Ogni valore, ogni parola, sta per andare in uno di questi secchi.

389
00:33:43,010 --> 00:33:53,200
Una tabella hash idealmente distribuisce in modo uniforme tutti questi valori che si sta passando

390
00:33:53,200 --> 00:33:57,160
e inserisce poi nel secchio tale che ogni bucket

391
00:33:57,160 --> 00:34:02,000
ha circa lo stesso numero di valori in esso.

392
00:34:02,000 --> 00:34:09,630
La struttura di una tabella hash, abbiamo un array di liste concatenate.

393
00:34:09,630 --> 00:34:17,900
Quello che facciamo è quando si passa un valore, controlliamo, quando tale valore deve appartenere,

394
00:34:17,900 --> 00:34:23,840
secchio che appartiene, e quindi inserirlo nella lista concatenata associata a quel secchio.

395
00:34:23,840 --> 00:34:28,199
Ecco, quello che ho è una funzione hash.

396
00:34:28,199 --> 00:34:31,320
Si tratta di una tabella di hash int.

397
00:34:31,320 --> 00:34:38,540
Così, per il primo bucket, eventuali interi inferiori 10 andare nel secchio prima.

398
00:34:38,540 --> 00:34:42,190
Eventuali numeri interi superiori a 10 ma inferiori a 20 go nel secondo,

399
00:34:42,190 --> 00:34:44,179
e così via e così via.

400
00:34:44,179 --> 00:34:52,370
Per me, ciascun segmento viene rappresenta questi numeri.

401
00:34:52,370 --> 00:34:59,850
Tuttavia, dire che dovevano passare in 50, per esempio.

402
00:34:59,850 --> 00:35:07,490
Sembra come se le prime tre contengono una serie di dieci numeri.

403
00:35:07,490 --> 00:35:12,570
Ma voglio permettere al mio tabella hash ad accogliere qualsiasi tipo di numeri interi,

404
00:35:12,570 --> 00:35:19,860
così poi avrei dovuto filtrare tutti i numeri superiori a 30 nel secchio ultima.

405
00:35:19,860 --> 00:35:26,660
E così allora che si tradurrebbe in una sorta di squilibrata tabella di hash.

406
00:35:31,330 --> 00:35:35,640
Per ribadire, una tabella di hash è solo una serie di secchi

407
00:35:35,640 --> 00:35:38,590
dove ogni secchio è una lista concatenata.

408
00:35:38,590 --> 00:35:43,730
E così, per determinare dove ogni valore va, che va in secchio,

409
00:35:43,730 --> 00:35:46,260
si sta andando a voler quello che si chiama una funzione di hash

410
00:35:46,260 --> 00:35:55,010
che prende un valore e poi dice questo valore corrisponde a un secchio certa.

411
00:35:55,010 --> 00:36:00,970
Così in alto, in questo esempio, la mia funzione di hash ha preso ogni valore.

412
00:36:00,970 --> 00:36:03,020
Controllato se era inferiore a 10.

413
00:36:03,020 --> 00:36:05,360
Se fosse, sarebbe messo nel secchio prima.

414
00:36:05,360 --> 00:36:08,910
Verifica se è meno di 20, la mette nella seconda se è vero,

415
00:36:08,910 --> 00:36:12,880
verifica se è meno di 30, e poi si entra nel terzo secchio,

416
00:36:12,880 --> 00:36:16,990
e poi tutto il resto cade proprio al secchio quarto.

417
00:36:16,990 --> 00:36:20,110
Così ogni volta che ha un valore, la funzione hash

418
00:36:20,110 --> 00:36:25,420
porrà tale valore nel secchio appropriata.

419
00:36:25,420 --> 00:36:32,430
La funzione di hash deve fondamentalmente sapere quanti secchi che avete.

420
00:36:32,430 --> 00:36:37,960
Le dimensioni della tabella hash, il numero di segmenti che hai,

421
00:36:37,960 --> 00:36:41,190
che sta per essere un numero fisso che dipende da voi, per voi a decidere,

422
00:36:41,190 --> 00:36:43,590
ma sarà un numero fisso.

423
00:36:43,590 --> 00:36:51,840
Quindi, la funzione hash verrà basarsi su tale per determinare quale secchio ogni chiave va in

424
00:36:51,840 --> 00:36:54,450
tale che è uniformemente distribuito.

425
00:36:56,150 --> 00:37:03,820
Simile alla nostra implementazione di liste concatenate, ora ogni nodo della tabella hash

426
00:37:03,820 --> 00:37:07,000
è in realtà sta per avere un tipo char.

427
00:37:07,000 --> 00:37:14,340
Quindi abbiamo un array di caratteri chiamato parola e poi un altro puntatore al nodo successivo,

428
00:37:14,340 --> 00:37:19,010
che ha un senso, perché sarà una lista concatenata.

429
00:37:19,010 --> 00:37:24,350
Ricordate quando avevamo liste collegate, ho fatto un * nodo denominato testa

430
00:37:24,350 --> 00:37:31,060
che è stata punta al primo nodo della lista collegata.

431
00:37:31,060 --> 00:37:34,020
Ma per la nostra tabella di hash, perché abbiamo più liste concatenate,

432
00:37:34,020 --> 00:37:37,520
quello che vogliamo è che vogliamo la nostra tabella di hash per essere come, "Che cosa è un secchio?"

433
00:37:37,520 --> 00:37:43,340
Un secchio è semplicemente una lista di puntatori del nodo,

434
00:37:43,340 --> 00:37:50,620
e così ogni elemento nel secchio è in realtà punta alla sua lista collegato corrispondente.

435
00:37:56,180 --> 00:38:01,520
Per tornare a questo schema, si vede che gli stessi secchi sono le frecce,

436
00:38:01,520 --> 00:38:06,980
non nodi effettivi.

437
00:38:11,680 --> 00:38:16,420
Una delle proprietà essenziali di funzioni hash è che sono deterministiche.

438
00:38:16,420 --> 00:38:19,440
Ciò significa che ogni volta che si hash il numero 2,

439
00:38:19,440 --> 00:38:22,270
si deve sempre restituire il secchio stesso.

440
00:38:22,270 --> 00:38:26,440
Ogni singolo valore che va nella funzione hash, se ripetuto,

441
00:38:26,440 --> 00:38:29,690
deve ottenere lo stesso indice.

442
00:38:29,690 --> 00:38:34,210
Quindi la funzione di hash restituisce l'indice della matrice

443
00:38:34,210 --> 00:38:38,530
quando tale valore appartiene.

444
00:38:38,530 --> 00:38:41,790
Come ho detto prima, il numero di segmenti è fisso,

445
00:38:41,790 --> 00:38:49,630
e così l'indice che si torna deve essere inferiore al numero di bucket

446
00:38:49,630 --> 00:38:52,680
ma maggiore di 0.

447
00:38:52,680 --> 00:39:00,780
Il motivo per cui ci sono le funzioni di hash invece di uno solo sola lista collegata

448
00:39:00,780 --> 00:39:09,290
o un singolo array è che vogliamo essere in grado di saltare ad una certa sezione più facilmente

449
00:39:09,290 --> 00:39:11,720
se conosciamo la caratteristica di un valore -

450
00:39:11,720 --> 00:39:14,760
invece di dover cercare attraverso il dizionario nel suo insieme,

451
00:39:14,760 --> 00:39:18,320
essere in grado di passare a una determinata sezione di esso.

452
00:39:19,880 --> 00:39:24,440
La funzione hash deve tener conto del fatto che idealmente,

453
00:39:24,440 --> 00:39:28,980
ciascun segmento ha approssimativamente lo stesso numero di tasti.

454
00:39:28,980 --> 00:39:35,040
Dal momento che la tabella di hash è una serie di liste collegate,

455
00:39:35,040 --> 00:39:38,480
poi le liste concatenate stessi avranno più di un nodo.

456
00:39:38,480 --> 00:39:43,210
Nell'esempio precedente, due numeri differenti, anche se non erano uguali,

457
00:39:43,210 --> 00:39:46,950
quando hash, sarebbe tornato lo stesso indice.

458
00:39:46,950 --> 00:39:53,620
Così, quando hai a che fare con le parole, una parola quando hash

459
00:39:53,620 --> 00:39:57,450
sarebbe lo stesso valore di hash come un'altra parola.

460
00:39:57,450 --> 00:40:04,140
Questo è ciò che noi chiamiamo una collisione, quando abbiamo un nodo che, quando hash,

461
00:40:04,140 --> 00:40:09,610
l'elenco collegato in quel bucket non è vuoto.

462
00:40:09,610 --> 00:40:14,180
La tecnica che noi chiamiamo c'è scansione lineare,

463
00:40:14,180 --> 00:40:22,550
dove si va alla lista linkata e poi trovare dove si desidera inserire tale nodo

464
00:40:22,550 --> 00:40:25,520
perché si ha una collisione.

465
00:40:25,520 --> 00:40:28,070
Si può vedere che ci potrebbe essere un trade-off qui, giusto?

466
00:40:28,070 --> 00:40:33,760
Se si dispone di una tabella di hash molto piccolo, un numero molto limitato di segmenti,

467
00:40:33,760 --> 00:40:36,380
allora si sta andando ad avere un sacco di collisioni.

468
00:40:36,380 --> 00:40:40,460
Ma poi se si fanno una tabella molto grande hash,

469
00:40:40,460 --> 00:40:44,110
probabilmente stai andando a ridurre al minimo le collisioni,

470
00:40:44,110 --> 00:40:47,170
ma sarà una struttura di dati molto grande.

471
00:40:47,170 --> 00:40:49,310
Ci sarà compromessi con questo.

472
00:40:49,310 --> 00:40:51,310
Così, quando si sta facendo la tua pset, provare a giocare

473
00:40:51,310 --> 00:40:54,210
tra forse fare un tavolo più piccolo hash

474
00:40:54,210 --> 00:41:02,100
ma poi sapendo che ci vorrà un po 'più tempo per attraversare i diversi elementi

475
00:41:02,100 --> 00:41:04,270
di tali liste concatenate.

476
00:41:04,270 --> 00:41:09,500
>> Che carico sta per fare è iterare su ogni parola nel dizionario.

477
00:41:09,500 --> 00:41:13,180
Si passa in un puntatore al file di dizionario.

478
00:41:13,180 --> 00:41:18,050
Quindi hai intenzione di approfittare del file funzioni I / O che è imparato a pset4

479
00:41:18,050 --> 00:41:23,010
e scorrere ogni parola nel dizionario.

480
00:41:23,010 --> 00:41:26,620
Volete ogni parola nel dizionario di diventare un nuovo nodo,

481
00:41:26,620 --> 00:41:32,730
e si sta andando a mettere ogni uno di quei nodi all'interno della vostra struttura dizionario dei dati.

482
00:41:32,730 --> 00:41:36,560
Ogni volta che si ottiene una nuova parola, si sa che sta per diventare un nodo.

483
00:41:36,560 --> 00:41:46,590
Così si può andare subito e malloc un puntatore nodo per ogni nuova parola che avete.

484
00:41:46,590 --> 00:41:52,610
Qui sto chiamando il mio new_node puntatore del nodo e sto mallocing cosa? La dimensione di un nodo.

485
00:41:52,610 --> 00:41:59,190
Poi, per leggere la stringa effettiva da un file, perché il dizionario è in realtà memorizzati

486
00:41:59,190 --> 00:42:03,340
da una parola e poi una nuova linea, quello che possiamo trarre vantaggio

487
00:42:03,340 --> 00:42:06,520
è la funzione fscanf,

488
00:42:06,520 --> 00:42:10,280
in base al quale è il file dizionario che stiamo passato,

489
00:42:10,280 --> 00:42:18,900
quindi analizza il file per una stringa e luoghi che nella stringa l'ultimo argomento.

490
00:42:18,900 --> 00:42:26,890
Se vi ricordate tornare a una delle lezioni, quando siamo andati oltre

491
00:42:26,890 --> 00:42:29,320
e il tipo di pelati strati indietro sulla libreria CS50,

492
00:42:29,320 --> 00:42:33,430
abbiamo visto l'implementazione di fscanf lì.

493
00:42:33,430 --> 00:42:37,700
Per tornare alla fscanf, abbiamo il file che stiamo leggendo da,

494
00:42:37,700 --> 00:42:42,570
siamo alla ricerca di una stringa in quel file, e poi stiamo messa in

495
00:42:42,570 --> 00:42:48,340
qui ho new_node-> parola perché new_node è un puntatore nodo,

496
00:42:48,340 --> 00:42:50,380
non un nodo effettivo.

497
00:42:50,380 --> 00:42:57,100
Allora sto dicendo new_node, voglio andare al nodo che si sta puntando

498
00:42:57,100 --> 00:43:01,190
e quindi assegnare tale valore alla parola.

499
00:43:01,190 --> 00:43:08,540
Vogliamo prendere poi quella parola e inserirla nella tabella hash.

500
00:43:08,540 --> 00:43:13,750
Rendetevi conto che abbiamo fatto new_node un puntatore nodo

501
00:43:13,750 --> 00:43:18,230
perché stiamo andando a voler sapere che cosa l'indirizzo del nodo è

502
00:43:18,230 --> 00:43:23,940
se lo inseriamo in quanto la struttura dei nodi stessi, della struttura,

503
00:43:23,940 --> 00:43:26,380
è che hanno un puntatore a un nuovo nodo.

504
00:43:26,380 --> 00:43:30,820
Allora qual è l'indirizzo del nodo che sta per puntare a?

505
00:43:30,820 --> 00:43:34,550
Questo indirizzo sarà new_node.

506
00:43:34,550 --> 00:43:42,140
Ha senso, perché stiamo facendo un new_node * nodo al contrario di un nodo?

507
00:43:43,700 --> 00:43:45,700
Va bene.

508
00:43:45,700 --> 00:43:52,840
Noi abbiamo una parola. Tale valore è new_node-> parola.

509
00:43:52,840 --> 00:43:55,970
Che contiene la parola dal dizionario che si desidera immettere.

510
00:43:55,970 --> 00:44:00,210
Quindi, quello che vogliamo fare è che si vuole chiamare la nostra funzione hash su tale stringa

511
00:44:00,210 --> 00:44:03,780
perché la nostra funzione di hash prende in una stringa e poi ci restituisce un intero,

512
00:44:03,780 --> 00:44:12,090
quando tale intero è l'indice in cui hashtable a tale indice rappresenta quel secchio.

513
00:44:12,090 --> 00:44:18,260
Vogliamo prendere tale indice e poi andare a quella indice della tabella di hash

514
00:44:18,260 --> 00:44:26,960
e quindi utilizzare tale lista collegata per inserire il nodo in new_node.

515
00:44:26,960 --> 00:44:31,950
Ricorda che però si decide di inserire il nodo,

516
00:44:31,950 --> 00:44:34,370
se è nel mezzo, se si desidera ordinare la

517
00:44:34,370 --> 00:44:39,650
o all'inizio o alla fine, basta assicurarsi che il vostro ultimo nodo punta sempre a NULL

518
00:44:39,650 --> 00:44:46,730
perché questo è l'unico modo che sappiamo dove l'ultimo elemento della nostra lista è collegata.

519
00:44:50,790 --> 00:44:59,710
>> Se la dimensione è un numero intero che rappresenta il numero di parole in un dizionario,

520
00:44:59,710 --> 00:45:03,060
quindi un modo per fare questo è che ogni volta che si chiama dimensione

521
00:45:03,060 --> 00:45:05,840
passiamo attraverso ogni elemento nella nostra tabella di hash

522
00:45:05,840 --> 00:45:09,410
e poi scorrere ogni lista collegata all'interno della tabella hash

523
00:45:09,410 --> 00:45:13,770
e quindi calcolare la lunghezza di questo, aumentare il nostro contatore 1 di 1.

524
00:45:13,770 --> 00:45:16,580
Ma ogni volta che le dimensioni si chiama, che ci vorrà molto tempo

525
00:45:16,580 --> 00:45:22,120
perché ci sta andando ad essere linearmente sondare ogni singola lista collegata.

526
00:45:22,120 --> 00:45:30,530
Invece, sarà molto più facile se si tiene traccia di quante parole sono passati trovi

527
00:45:30,530 --> 00:45:36,330
Allora se si include un contatore all'interno della vostra funzione di carico

528
00:45:36,330 --> 00:45:42,430
che gli aggiornamenti, se necessario, poi contro, se si imposta una variabile globale,

529
00:45:42,430 --> 00:45:44,930
potranno essere accessibile dimensioni.

530
00:45:44,930 --> 00:45:51,450
Così che cosa dimensioni potrebbe semplicemente fare è in una sola riga, torna il valore del contatore,

531
00:45:51,450 --> 00:45:55,500
la dimensione del dizionario, che è già stato affrontato nel carico.

532
00:45:55,500 --> 00:46:05,190
Questo è quello che intendevo quando ho detto che se si implementa il carico in modo utile,

533
00:46:05,190 --> 00:46:08,540
quindi le dimensioni sarà abbastanza facile.

534
00:46:08,540 --> 00:46:11,350
>> Così ora si arriva a controllare.

535
00:46:11,350 --> 00:46:15,960
Ora abbiamo a che fare con le parole dal file di testo di input,

536
00:46:15,960 --> 00:46:19,910
e quindi abbiamo intenzione di verificare se tutte queste parole di ingresso

537
00:46:19,910 --> 00:46:22,520
sono in realtà nel dizionario o meno.

538
00:46:22,520 --> 00:46:26,520
Simile a Scramble, vogliamo far sì che tra maiuscole e minuscole.

539
00:46:26,520 --> 00:46:32,110
Si vuole fare in modo che tutte le parole passato, anche se sono maiuscole e minuscole,

540
00:46:32,110 --> 00:46:37,840
quando viene chiamato con stringa di confronto, sono equivalenti.

541
00:46:37,840 --> 00:46:42,450
Le parole in file di testo del dizionario sono in realtà tutti in minuscolo.

542
00:46:42,450 --> 00:46:49,280
Un'altra cosa è che si può supporre che ogni parola passata, ogni stringa,

543
00:46:49,280 --> 00:46:53,200
sta per essere alfabetico o contenere apostrofi.

544
00:46:53,200 --> 00:46:58,010
Apostrofi saranno parole valide nel nostro dizionario.

545
00:46:58,010 --> 00:47:06,470
Quindi, se avete una parola con apostrofo S, che è una parola vera legittima nel dizionario

546
00:47:06,470 --> 00:47:11,650
che sta per essere uno dei nodi della tabella di hash.

547
00:47:13,470 --> 00:47:18,350
Verificare opera con se la parola esiste, allora è avuto modo di essere nella nostra tabella di hash.

548
00:47:18,350 --> 00:47:22,210
Se la parola è nel dizionario, allora tutte le parole del dizionario si trovano nella tabella di hash,

549
00:47:22,210 --> 00:47:26,560
quindi diamo un'occhiata a questa parola nella tabella di hash.

550
00:47:26,560 --> 00:47:29,250
Sappiamo che da quando abbiamo implementato la nostra funzione di hash

551
00:47:29,250 --> 00:47:38,420
tale che ogni parola univoca è sempre hash allo stesso valore,

552
00:47:38,420 --> 00:47:43,340
allora sappiamo che invece di cercare tra tutta la nostra intera tabella di hash,

553
00:47:43,340 --> 00:47:48,310
si può effettivamente trovare l'elenco collegato che questa parola dovrebbe appartenere a.

554
00:47:48,310 --> 00:47:51,850
Se fosse nel dizionario, allora sarebbe nel secchio.

555
00:47:51,850 --> 00:47:57,140
Quello che possiamo fare, se la parola è il nome della nostra stringa passata,

556
00:47:57,140 --> 00:48:01,560
possiamo solo hash che la parola e un'occhiata alla lista concatenata

557
00:48:01,560 --> 00:48:06,410
al valore della tabella hash [hash (parola)].

558
00:48:06,410 --> 00:48:12,410
Da lì, quello che possiamo fare è che abbiamo un sottoinsieme più piccolo di nodi per la ricerca di questa parola,

559
00:48:12,410 --> 00:48:16,770
e così siamo in grado di attraversare la lista collegata, con un esempio in precedenza nella procedura dettagliata,

560
00:48:16,770 --> 00:48:24,110
e quindi chiamare stringa confrontare sulla parola ovunque il cursore è su,

561
00:48:24,110 --> 00:48:28,430
quella parola, e vedere se quelli confrontare.

562
00:48:30,280 --> 00:48:35,110
A seconda del modo in cui si organizza la funzione di hash,

563
00:48:35,110 --> 00:48:39,260
se è ordinato, si potrebbe essere in grado di restituire false un po 'prima,

564
00:48:39,260 --> 00:48:43,440
ma se è indifferenziato, poi si desidera continuare movimento attraverso la vostra lista concatenata

565
00:48:43,440 --> 00:48:46,480
fino a trovare l'ultimo elemento della lista.

566
00:48:46,480 --> 00:48:53,320
E se non hai ancora trovato la parola per il tempo che hai raggiunto la fine della lista collegata,

567
00:48:53,320 --> 00:48:56,890
ciò significa che la tua parola non esiste nel dizionario,

568
00:48:56,890 --> 00:48:59,410
e in modo che la parola non è valido,

569
00:48:59,410 --> 00:49:02,730
e controllo deve restituire false.

570
00:49:02,730 --> 00:49:09,530
>> Ora veniamo a scaricare, dove vogliamo liberare tutti i nodi che abbiamo malloc'd,

571
00:49:09,530 --> 00:49:14,050
così libero tutti i nodi all'interno della nostra tabella di hash.

572
00:49:14,050 --> 00:49:20,270
Stiamo andando a voler scorrere tutte le liste concatenate e libera tutti i nodi in questo.

573
00:49:20,270 --> 00:49:29,350
Se si guarda al di sopra nella procedura dettagliata per l'esempio in cui liberiamo una lista concatenata,

574
00:49:29,350 --> 00:49:35,140
allora ti consigliamo di ripetere questo processo per ogni elemento nella tabella hash.

575
00:49:35,140 --> 00:49:37,780
E io vado su questo verso la fine della procedura dettagliata,

576
00:49:37,780 --> 00:49:46,600
ma Valgrind è uno strumento dove si può vedere se si è liberato correttamente

577
00:49:46,600 --> 00:49:53,600
ogni nodo che hai malloc'd o qualsiasi altra cosa che hai malloc'd, qualsiasi altro puntatore.

578
00:49:55,140 --> 00:50:00,530
Ecco, questo è tabelle hash, dove abbiamo un numero finito di segmenti

579
00:50:00,530 --> 00:50:09,220
e una funzione di hash che avrà un valore e quindi assegnare tale valore a un secchio certa.

580
00:50:09,220 --> 00:50:13,340
>> Ora veniamo a tentativi.

581
00:50:13,340 --> 00:50:18,750
Tenta tipo di look in questo modo, e io anche tirare fuori un esempio.

582
00:50:18,750 --> 00:50:25,630
In sostanza, si dispone di tutta una serie di lettere potenziali,

583
00:50:25,630 --> 00:50:29,210
e poi ogni volta che si sta costruendo una parola,

584
00:50:29,210 --> 00:50:36,490
lettera che può essere collegato ad un dizionario di una vasta gamma di possibilità.

585
00:50:36,490 --> 00:50:40,840
Alcune parole iniziano con C ma poi continuare con A,

586
00:50:40,840 --> 00:50:42,960
ma altri continuano con O, per esempio.

587
00:50:42,960 --> 00:50:51,090
Un trie è un modo di visualizzare tutte le possibili combinazioni di queste parole.

588
00:50:51,090 --> 00:50:59,070
Un trie sta per tenere traccia della sequenza di lettere che compongono le parole,

589
00:50:59,070 --> 00:51:08,280
diramazione quando necessario, quando una lettera può essere seguita da un multiplo di lettere,

590
00:51:08,280 --> 00:51:16,630
e alla fine indicano in ogni punto se tale parola è valido o meno

591
00:51:16,630 --> 00:51:30,120
perché se si sta ortografia della parola MAT, MA non credo che sia una parola valida, ma è MAT.

592
00:51:30,120 --> 00:51:37,820
E così nel trie, indicherebbe che dopo MAT che in realtà è una parola valida.

593
00:51:41,790 --> 00:51:48,590
Ogni nodo nella nostra trie è in realtà sta per contenere un array di puntatori del nodo,

594
00:51:48,590 --> 00:51:52,970
e stiamo andando ad avere, in particolare, 27 di questi puntatori nodo,

595
00:51:52,970 --> 00:52:00,550
uno per ogni lettera dell'alfabeto e il carattere di apostrofo.

596
00:52:00,550 --> 00:52:10,450
Ogni elemento dell'array si sta andando a puntare su un altro nodo.

597
00:52:10,450 --> 00:52:14,020
Quindi, se questo nodo è NULL, se non c'è niente dopo che,

598
00:52:14,020 --> 00:52:20,550
allora sappiamo che non ci sono altre lettere in quella sequenza di parole.

599
00:52:20,550 --> 00:52:26,950
Ma se questo nodo non è NULL, il che significa che ci sono più le lettere in quella sequenza di lettere.

600
00:52:26,950 --> 00:52:32,160
E poi, inoltre, ogni nodo indica se è l'ultimo carattere di una parola o meno.

601
00:52:38,110 --> 00:52:43,170
>> Andiamo in un esempio di un trie.

602
00:52:50,500 --> 00:52:58,340
Per prima cosa hanno spazio per 27 nodi in questo array.

603
00:52:58,340 --> 00:53:03,200
Se ho la parola BAR -

604
00:53:13,310 --> 00:53:15,370
Se ho la BAR parola e voglio inserire che,

605
00:53:15,370 --> 00:53:22,700
la prima lettera è B, quindi se la mia trie è vuota,

606
00:53:22,700 --> 00:53:29,910
B è la seconda lettera dell'alfabeto, così ho intenzione di scegliere di mettere questa qui in questo indice.

607
00:53:29,910 --> 00:53:33,450
Ho intenzione di avere B qui.

608
00:53:33,450 --> 00:53:42,400
B sta per essere un nodo che punta ad un altro array di tutti i personaggi possibili

609
00:53:42,400 --> 00:53:45,870
che può seguire dopo la lettera B.

610
00:53:45,870 --> 00:53:57,610
In questo caso, ho a che fare con la BAR parola, quindi A andrà qui.

611
00:54:02,000 --> 00:54:08,990
Dopo la A, io ho la lettera R, e allora A punti ora alla sua propria combinazione,

612
00:54:08,990 --> 00:54:15,120
e poi R sarà qui.

613
00:54:15,120 --> 00:54:22,470
BAR è una parola completa, così poi ho intenzione di avere punto R su un altro nodo

614
00:54:22,470 --> 00:54:33,990
che dice che quella parola è valida.

615
00:54:36,010 --> 00:54:40,970
Tale nodo è anche intenzione di avere un array di nodi,

616
00:54:40,970 --> 00:54:45,260
ma quelli che potrebbero essere NULL.

617
00:54:45,260 --> 00:54:49,080
Ma in fondo, si può continuare così.

618
00:54:49,080 --> 00:54:54,250
Che diventerà un po 'più chiara quando andiamo in un altro esempio,

619
00:54:54,250 --> 00:54:56,780
quindi basta portare con me lì.

620
00:54:56,780 --> 00:55:02,050
Ora abbiamo BAR all'interno del nostro dizionario.

621
00:55:02,050 --> 00:55:05,980
Ora dire che abbiamo il BAZ parola.

622
00:55:05,980 --> 00:55:12,630
Si comincia con B, e abbiamo già B come una delle lettere che ci sono nel nostro dizionario.

623
00:55:12,630 --> 00:55:15,170
Questo è seguito con A. Abbiamo già una.

624
00:55:15,170 --> 00:55:19,250
Ma poi, invece, abbiamo seguito Z.

625
00:55:19,250 --> 00:55:25,490
Allora un elemento della nostra matrice sarà Z,

626
00:55:25,490 --> 00:55:30,810
e così allora che si sta per puntare a un altro termine valido della parola.

627
00:55:30,810 --> 00:55:36,930
Così vediamo che, quando continuiamo a B e poi A,

628
00:55:36,930 --> 00:55:43,480
ci sono due diverse opzioni attualmente in nostro dizionario per le parole che iniziano con B e A.

629
00:55:49,650 --> 00:55:57,460
Dire abbiamo voluto inserire la parola FOOBAR.

630
00:55:57,460 --> 00:56:05,620
Poi ci sarebbe una voce in F.

631
00:56:05,620 --> 00:56:11,320
F è un nodo che indica tutta una serie.

632
00:56:11,320 --> 00:56:22,790
Vorremmo trovare O, vai a O, O collega poi a tutta una serie.

633
00:56:22,790 --> 00:56:35,340
Avremmo B e poi continuare, avremmo A e poi R.

634
00:56:35,340 --> 00:56:43,570
Allora FooBar attraversa tutta la strada fino a quando FOOBAR è una parola corretta.

635
00:56:43,570 --> 00:56:52,590
E così allora questo sarebbe una parola valida.

636
00:56:52,590 --> 00:57:00,170
Ora dire che la nostra parola successiva nel dizionario è in realtà la parola FOO.

637
00:57:00,170 --> 00:57:03,530
Diremmo F. ​​Quello che segue F?

638
00:57:03,530 --> 00:57:06,190
Io in realtà già di uno spazio di O, così ho intenzione di continuare.

639
00:57:06,190 --> 00:57:09,150
Non ho bisogno di fare una nuova. Continua.

640
00:57:09,150 --> 00:57:15,500
FOO è una parola valida in questo dizionario, così poi ho intenzione di indicare

641
00:57:15,500 --> 00:57:21,660
che valido.

642
00:57:21,660 --> 00:57:28,370
Se mi fermo la mia sequenza lì, che sarebbe corretto.

643
00:57:28,370 --> 00:57:33,050
Ma se abbiamo continuato la nostra sequenza da FOO fino a B

644
00:57:33,050 --> 00:57:39,750
e appena avuto foob, foob non è una parola, e che non è indicato come uno valido.

645
00:57:47,370 --> 00:57:57,600
In un trie, avete ogni nodo indica se si tratta di una parola valida o no,

646
00:57:57,600 --> 00:58:05,840
e quindi ogni nodo ha anche una serie di 27 puntatori del nodo

647
00:58:05,840 --> 00:58:09,520
che poi scegliere i nodi stessi.

648
00:58:09,520 --> 00:58:12,940
>> Ecco un modo di come si potrebbe desiderare di definire questo.

649
00:58:12,940 --> 00:58:17,260
Tuttavia, proprio come nell'esempio di tabella hash, dove abbiamo avuto una testa nodo *

650
00:58:17,260 --> 00:58:21,320
per indicare l'inizio della nostra lista collegata, stiamo anche andando a voler

651
00:58:21,320 --> 00:58:29,150
qualche modo di sapere dove l'inizio della nostra trie è.

652
00:58:29,150 --> 00:58:34,110
Alcuni chiamano la gente cerca di alberi, ed è lì che viene dalla radice.

653
00:58:34,110 --> 00:58:36,910
Quindi vogliamo la radice del nostro albero per fare in modo di rimanere a terra

654
00:58:36,910 --> 00:58:39,570
alla tua destinazione è la nostra trie.

655
00:58:42,910 --> 00:58:46,300
Abbiamo già andati oltre tipo di

656
00:58:46,300 --> 00:58:50,240
il modo in cui si potrebbe pensare di caricare ogni parola nel dizionario.

657
00:58:50,240 --> 00:58:54,540
In sostanza, per ogni parola che si sta andando a voler scorrere la tua trie

658
00:58:54,540 --> 00:58:59,590
e sapendo che ogni elemento nei bambini - abbiamo chiamato i bambini in questo caso -

659
00:58:59,590 --> 00:59:04,290
corrisponde ad una lettera diversa, si sta andando a voler controllare quei valori

660
00:59:04,290 --> 00:59:08,320
in quel particolare indice che corrisponde alla lettera.

661
00:59:08,320 --> 00:59:11,260
Quindi, pensare tutto il viaggio di ritorno a Cesare e Vigenère,

662
00:59:11,260 --> 00:59:16,070
sapendo che ogni lettera è possibile tipo di carta torna ad un indice alfabetico,

663
00:59:16,070 --> 00:59:20,690
sicuramente da A a Z sta per essere abbastanza facile per mappare una lettera alfabetica,

664
00:59:20,690 --> 00:59:25,200
ma purtroppo, gli apostrofi sono anche un carattere accettato a parole.

665
00:59:25,200 --> 00:59:31,650
Non sono nemmeno sicuro di quello che è il valore ASCII,

666
00:59:31,650 --> 00:59:39,250
quindi per questo, se si vuole trovare un indice di decidere se si desidera essere il primo

667
00:59:39,250 --> 00:59:44,550
o l'ultimo, dovrete fare un controllo hardcoded per tale

668
00:59:44,550 --> 00:59:48,930
e poi mettere in indice 26 che, per esempio.

669
00:59:48,930 --> 00:59:55,300
Allora si sta verificando il valore ai bambini [i]

670
00:59:55,300 --> 00:59:58,400
in cui [i] corrisponde a qualsiasi lettera che ci sei.

671
00:59:58,400 --> 01:00:04,110
Se questo è NULL, il che significa che non vi è al momento nessuna lettera possibili

672
01:00:04,110 --> 01:00:08,150
derivante da quella sequenza precedente, in modo che stai andando a voler malloc

673
01:00:08,150 --> 01:00:13,150
e fare un nuovo nodo e avere che i bambini [i] punto ad esso

674
01:00:13,150 --> 01:00:17,890
in modo da creare - quando abbiamo inserito una lettera nel rettangolo -

675
01:00:17,890 --> 01:00:23,680
rendere i bambini non NULL e il punto in quel nuovo nodo.

676
01:00:23,680 --> 01:00:28,340
Ma se questo non è NULL, come nel nostro caso di FOO

677
01:00:28,340 --> 01:00:34,570
quando abbiamo già avuto FOOBAR, continuiamo,

678
01:00:34,570 --> 01:00:44,010
e non siamo mai fare un nuovo nodo, ma piuttosto semplice impostazione is_word su true

679
01:00:44,010 --> 01:00:47,790
al termine di tale parola.

680
01:00:50,060 --> 01:00:55,340
>> Allora come prima, perché qui hai a che fare con ogni lettera alla volta,

681
01:00:55,340 --> 01:01:01,470
che sarà più facile per voi per le dimensioni, invece di dover calcolare

682
01:01:01,470 --> 01:01:06,910
e passare attraverso l'intero albero e calcolare quanti bambini ho

683
01:01:06,910 --> 01:01:10,850
e poi diramazione, ricordando quante sono sul lato sinistro e sul lato destro

684
01:01:10,850 --> 01:01:12,850
e cose del genere, che sarà molto più facile per voi

685
01:01:12,850 --> 01:01:16,220
se solo tenere traccia di quante parole si sta aggiungendo in

686
01:01:16,220 --> 01:01:18,080
quando hai a che fare con il carico.

687
01:01:18,080 --> 01:01:22,630
E così allora che le dimensioni così può semplicemente restituire una variabile globale di dimensioni.

688
01:01:25,320 --> 01:01:28,530
>> Ora veniamo a controllare.

689
01:01:28,530 --> 01:01:33,920
Stessi standard di prima, dove vogliamo consentire tra maiuscole e minuscole.

690
01:01:33,920 --> 01:01:40,400
Inoltre, si assume che le stringhe sono solo caratteri alfabetici o gli apostrofi

691
01:01:40,400 --> 01:01:44,000
perché i bambini è un array di 27 a lungo,

692
01:01:44,000 --> 01:01:48,480
così tutte le lettere dell'alfabeto, più l'apostrofo.

693
01:01:48,480 --> 01:01:53,800
Per controllare ciò che si vorrà fare è ti consigliamo di iniziare alla radice

694
01:01:53,800 --> 01:01:58,440
perché la radice punterà a una matrice che contiene

695
01:01:58,440 --> 01:02:01,630
tutte le possibili lettere iniziali di una parola.

696
01:02:01,630 --> 01:02:03,680
Hai intenzione di cominciare da lì,

697
01:02:03,680 --> 01:02:11,590
e poi si sta andando a controllare questo valore NULL o meno,

698
01:02:11,590 --> 01:02:16,490
perché se il valore è NULL, che significa che il dizionario non ha alcun valore

699
01:02:16,490 --> 01:02:21,480
che contengono tale lettera in questo ordine particolare.

700
01:02:21,480 --> 01:02:24,970
Se è NULL, allora ciò significa che la parola è errata subito.

701
01:02:24,970 --> 01:02:27,110
Ma se non è NULL, allora si può continuare,

702
01:02:27,110 --> 01:02:34,090
dire che la prima lettera è una lettera prima possibile in una parola,

703
01:02:34,090 --> 01:02:40,630
quindi ora voglio verificare se la seconda lettera, quella sequenza, è nel mio dizionario.

704
01:02:40,630 --> 01:02:46,540
Quindi hai intenzione di andare a l'indice dei figli del primo nodo

705
01:02:46,540 --> 01:02:50,720
e verificare se tale seconda lettera esiste.

706
01:02:50,720 --> 01:02:57,440
Poi si ripete questo processo per verificare se tale sequenza è valido o meno

707
01:02:57,440 --> 01:02:59,060
all'interno trie.

708
01:02:59,060 --> 01:03:06,430
Ogni volta che i bambini che i nodi in punti indice a NULL,

709
01:03:06,430 --> 01:03:10,710
si sa che quella sequenza non esiste,

710
01:03:10,710 --> 01:03:16,230
ma poi, se si raggiunge la fine della parola che hai immesso,

711
01:03:16,230 --> 01:03:20,070
poi si vuole verificare ora che ho completato questa sequenza

712
01:03:20,070 --> 01:03:27,610
e ha trovato nel mio trie, quella parola è valida o no?

713
01:03:27,610 --> 01:03:32,480
E così poi si vuole verificare che, e in quel momento, se hai trovato quella sequenza,

714
01:03:32,480 --> 01:03:35,120
poi si vuole verificare se quella parola è valido o meno

715
01:03:35,120 --> 01:03:40,290
perché ricordo indietro nel caso precedente che ho disegnato dove abbiamo avuto foob,

716
01:03:40,290 --> 01:03:48,410
che era una sequenza valida che abbiamo trovato, ma non era una parola vera in sé valido.

717
01:03:50,570 --> 01:03:59,000
>> Allo stesso modo, per lo scaricamento dei tentativi che si desidera scaricare tutti i nodi del trie.

718
01:03:59,000 --> 01:04:04,790
Scusi. Simile alle tabelle hash in cui si scaricano liberati tutti i nodi,

719
01:04:04,790 --> 01:04:09,740
nei tentativi vogliamo liberare anche tutti i nodi.

720
01:04:09,740 --> 01:04:15,000
Scaricare potrà mai funzionare più semplice dal basso verso l'alto

721
01:04:15,000 --> 01:04:19,290
perché queste sono liste essenzialmente legati.

722
01:04:19,290 --> 01:04:22,540
Quindi vogliamo fare in modo che ci attacchiamo a tutti i valori

723
01:04:22,540 --> 01:04:25,700
e libera tutti loro in modo esplicito.

724
01:04:25,700 --> 01:04:28,840
Che cosa si sta andando a voler fare se si sta lavorando con un trie

725
01:04:28,840 --> 01:04:35,640
è quello di viaggiare verso il basso e libera il nodo più basso prima possibile

726
01:04:35,640 --> 01:04:39,190
e poi andare fino a tutti quei bambini e quindi liberare tutti coloro,

727
01:04:39,190 --> 01:04:43,050
salire e poi libero, ecc

728
01:04:43,050 --> 01:04:48,790
Un po 'come fare con il livello inferiore del primo trie

729
01:04:48,790 --> 01:04:51,940
e poi andare sulla parte superiore una volta che hai liberato tutto.

730
01:04:51,940 --> 01:04:56,720
Questo è un buon esempio di funzione ricorsiva in cui potrebbe tornare utile.

731
01:04:56,720 --> 01:05:03,830
Una volta liberato lo strato inferiore del trie,

732
01:05:03,830 --> 01:05:08,000
allora si chiama scaricare sul resto di esso,

733
01:05:08,000 --> 01:05:13,620
facendo in modo che si libera ogni mini -

734
01:05:13,620 --> 01:05:16,410
È possibile tipo di visualizzarlo come tentativi mini.

735
01:05:23,300 --> 01:05:28,990
In modo da avere la tua radice qui.

736
01:05:30,840 --> 01:05:35,230
Tento solo di semplificare in modo da non dover disegnare 26 di loro.

737
01:05:37,250 --> 01:05:43,770
In modo da avere questi, e quindi questi rappresentano sequenze di parole

738
01:05:43,770 --> 01:05:54,620
dove tutti questi piccoli cerchi sono lettere che sono sequenze valide di lettere.

739
01:06:03,040 --> 01:06:07,160
Continuiamo solo un po 'di più.

740
01:06:15,110 --> 01:06:25,750
Che cosa si sta andando a voler fare è libero nella parte inferiore qui e poi libera questa

741
01:06:25,750 --> 01:06:31,640
e quindi liberare questo in fondo prima di liberare quello in alto qui

742
01:06:31,640 --> 01:06:38,180
perché se qualcosa di gratuito nel secondo livello qui,

743
01:06:38,180 --> 01:06:47,230
allora in realtà perderebbe il valore qui.

744
01:06:47,230 --> 01:06:54,780
Ecco perché è importante per scaricare in un trie per assicurarsi che si libera la parte inferiore prima.

745
01:06:54,780 --> 01:06:59,480
Cosa si potrebbe desiderare di fare è di dire per ogni nodo

746
01:06:59,480 --> 01:07:06,430
Voglio scaricare tutti i bambini.

747
01:07:16,060 --> 01:07:22,140
>> Ora che abbiamo superato lo scarico per il metodo della tabella di hash e il metodo di trie,

748
01:07:22,140 --> 01:07:27,020
stiamo andando a voler guardare Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind si esegue con i seguenti comandi.

750
01:07:29,640 --> 01:07:32,700
Hai valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Stai controllando per tutte le perdite quando si esegue speller dato questo determinato testo

752
01:07:40,960 --> 01:07:46,980
speller perché ha bisogno di prendere in un file di testo.

753
01:07:46,980 --> 01:07:52,330
Così Valgrind verrà eseguito il programma, dire quanti byte è assegnato,

754
01:07:52,330 --> 01:07:57,150
il numero di byte che hai liberato, e vi dirà se è liberato appena sufficiente

755
01:07:57,150 --> 01:07:58,930
o se non hai abbastanza libero,

756
01:07:58,930 --> 01:08:02,850
o, talvolta, si può anche troppo libero, come libero un nodo che è già stato liberato

757
01:08:02,850 --> 01:08:05,140
e così si ritorna errori.

758
01:08:05,140 --> 01:08:11,600
Se si utilizza Valgrind, vi darà alcuni messaggi

759
01:08:11,600 --> 01:08:15,970
che indica se si è liberato o meno che sufficiente, sufficiente,

760
01:08:15,970 --> 01:08:19,609
o più volte sufficiente.

761
01:08:24,370 --> 01:08:30,410
>> Una parte di questo pset, è facoltativo per sfidare il Big Board.

762
01:08:30,410 --> 01:08:35,790
Ma quando abbiamo a che fare con queste strutture di dati

763
01:08:35,790 --> 01:08:40,689
è una specie di divertente vedere la rapidità e l'efficienza le strutture di dati potrebbe essere.

764
01:08:40,689 --> 01:08:44,490
Il vostro risultato della funzione di hash in un sacco di collisioni?

765
01:08:44,490 --> 01:08:46,300
O è la dimensione di dati davvero grande?

766
01:08:46,300 --> 01:08:49,420
Ci vuole un sacco di tempo per attraversare?

767
01:08:49,420 --> 01:08:54,800
Nel registro del correttore ortografico, emette quanto tempo si usa per caricare,

768
01:08:54,800 --> 01:08:57,700
per controllare, per condurre dimensioni, e scaricare,

769
01:08:57,700 --> 01:09:00,720
e così quelli che sono pubblicati in The Big Board,

770
01:09:00,720 --> 01:09:03,600
dove si può competere contro i tuoi compagni di classe

771
01:09:03,600 --> 01:09:11,350
e alcuni membri del personale per vedere chi è il più veloce correttore ortografico.

772
01:09:11,350 --> 01:09:14,760
Una cosa che mi piacerebbe osservare sulle tabelle hash

773
01:09:14,760 --> 01:09:20,470
è che ci sono alcune funzioni molto semplici hash che si possa pensare.

774
01:09:20,470 --> 01:09:27,240
Per esempio, si hanno 26 secchi, e così ogni secchio

775
01:09:27,240 --> 01:09:30,200
corrisponde alla prima lettera di una parola,

776
01:09:30,200 --> 01:09:35,229
ma che sta per tradursi in una tabella piuttosto sbilanciato hash

777
01:09:35,229 --> 01:09:40,979
perché ci sono molte meno parole che iniziano con X che iniziano con M, per esempio.

778
01:09:40,979 --> 01:09:47,890
Un modo per andare su speller è che se si vuole ottenere tutte le funzionalità altra verso il basso,

779
01:09:47,890 --> 01:09:53,240
poi basta usare una semplice funzione di hash per essere in grado di ottenere il vostro codice in esecuzione

780
01:09:53,240 --> 01:09:58,650
e poi tornare indietro e modificare la dimensione della tabella hash e la definizione.

781
01:09:58,650 --> 01:10:03,430
Ci sono un sacco di risorse su Internet per le funzioni hash,

782
01:10:03,430 --> 01:10:08,250
e così per questo pset si è permesso di ricercare funzioni di hash su Internet

783
01:10:08,250 --> 01:10:15,560
per alcuni suggerimenti e ispirazione fino a quando si dovrà essere indicato dove l'hai preso.

784
01:10:15,560 --> 01:10:22,060
Ti invitiamo a guardare e interpretare una funzione di hash che si trova su Internet.

785
01:10:22,060 --> 01:10:27,460
Torna a questo, si potrebbe essere in grado di vedere se qualcuno ha utilizzato un trie

786
01:10:27,460 --> 01:10:31,700
se la loro applicazione è più veloce del hash table o meno.

787
01:10:31,700 --> 01:10:35,290
Si può presentare al consiglio di Big più volte.

788
01:10:35,290 --> 01:10:37,660
Si registra la sua entrata più recente.

789
01:10:37,660 --> 01:10:44,300
Quindi forse si modifica la funzione di hash e poi rendersi conto che in realtà è molto più veloce

790
01:10:44,300 --> 01:10:46,780
o molto più lento rispetto a prima.

791
01:10:46,780 --> 01:10:50,960
Questo è un po 'un modo divertente.

792
01:10:50,960 --> 01:10:57,190
C'è sempre 1 o 2 membri del personale che cercano di rendere il dizionario più lento possibile,

793
01:10:57,190 --> 01:11:00,210
così che è sempre divertente da guardare.

794
01:11:00,210 --> 01:11:07,630
>> L'utilizzo per la pset è si esegue correttore ortografico con un dizionario opzionale

795
01:11:07,630 --> 01:11:12,840
e quindi un file di testo obbligatorio.

796
01:11:12,840 --> 01:11:18,380
Per impostazione predefinita, quando si esegue correttore ortografico con un semplice file di testo e non si specifica un dizionario,

797
01:11:18,380 --> 01:11:24,410
sta andando a utilizzare il file di testo dizionario, il grande

798
01:11:24,410 --> 01:11:27,920
nella cartella cs50/pset5/dictionaries.

799
01:11:27,920 --> 01:11:32,760
Che uno ha più di 100.000 parole.

800
01:11:32,760 --> 01:11:37,950
Hanno anche un piccolo dizionario che ha molte meno parole

801
01:11:37,950 --> 01:11:40,730
CS50 che ha fatto per voi.

802
01:11:40,730 --> 01:11:44,050
Tuttavia, si può facilmente solo fare il proprio dizionario

803
01:11:44,050 --> 01:11:47,150
se si desidera solo di lavorare in piccoli esempi -

804
01:11:47,150 --> 01:11:51,140
per esempio, se si desidera utilizzare gdb e si conoscono i valori specifici

805
01:11:51,140 --> 01:11:53,560
che si desidera che la tabella di hash per tracciare a.

806
01:11:53,560 --> 01:12:00,430
Quindi, si può solo fare il proprio file di testo solo con la BAR, BAZ, PIPPO, e FOOBAR,

807
01:12:00,430 --> 01:12:04,860
fare che in un file di testo, separare i ciascuna con 1 linea,

808
01:12:04,860 --> 01:12:12,670
e poi fare il proprio file di testo che contiene solo letteralmente, forse 1 o 2 parole

809
01:12:12,670 --> 01:12:15,950
in modo da sapere esattamente che cosa l'uscita dovrebbe essere.

810
01:12:15,950 --> 01:12:21,870
Alcuni dei file di testo di esempio che The Big Board quando si esegue sfida verificherà

811
01:12:21,870 --> 01:12:25,580
sono Guerra e pace e un romanzo di Jane Austen o qualcosa del genere.

812
01:12:25,580 --> 01:12:30,450
Così, quando sei agli inizi, è molto più facile per rendere il vostro file di testo propri

813
01:12:30,450 --> 01:12:34,160
che contengono solo un paio di parole o forse 10

814
01:12:34,160 --> 01:12:38,280
in modo da poter prevedere ciò che il risultato dovrebbe essere

815
01:12:38,280 --> 01:12:42,880
e quindi controllare contro che, quindi più di un esempio controllato.

816
01:12:42,880 --> 01:12:45,820
E così da quando abbiamo a che fare con la previsione e disegnare le cose,

817
01:12:45,820 --> 01:12:48,690
Voglio ancora una volta invitiamo a utilizzare carta e penna

818
01:12:48,690 --> 01:12:50,700
perché è davvero intenzione di aiutare con questo -

819
01:12:50,700 --> 01:12:55,620
disegnare le frecce, come la tabella di hash o come il vostro aspetto trie,

820
01:12:55,620 --> 01:12:57,980
quando si sta liberando qualcosa in cui le frecce sono in corso,

821
01:12:57,980 --> 01:13:01,730
si tiene a sufficienza, vedi tutti i link scomparendo

822
01:13:01,730 --> 01:13:05,750
e cadere nell'abisso della memoria persa.

823
01:13:05,750 --> 01:13:11,070
Quindi, per favore, prova a disegnare le cose prima ancora di arrivare alla scrittura di codice in basso.

824
01:13:11,070 --> 01:13:14,520
Disegnare le cose in modo da capire come le cose stanno andando a lavorare

825
01:13:14,520 --> 01:13:22,750
perché allora vi garantisco che incorrerà in pasticci puntatore meno lì.

826
01:13:24,270 --> 01:13:25,910
>> Bene.

827
01:13:25,910 --> 01:13:28,780
Voglio augurare il meglio di fortuna con questo pset.

828
01:13:28,780 --> 01:13:31,980
E 'probabilmente la più difficile.

829
01:13:31,980 --> 01:13:40,360
Quindi cercate di iniziare presto, disegnare le cose, disegnare le cose, e buona fortuna.

830
01:13:40,360 --> 01:13:42,980
Questo era Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]