1
00:00:00,000 --> 00:00:01,000
[Powered by Google Translate] [Sezione 6] [più confortevole]

2
00:00:01,000 --> 00:00:04,000
[Rob Bowden] [Harvard University]

3
00:00:04,000 --> 00:00:09,000
[Questo è CS50.] [CS50.TV]

4
00:00:09,000 --> 00:00:11,000
>> Siamo in grado di dirigersi verso la nostra sezione di domande.

5
00:00:11,000 --> 00:00:17,000
Ho mandato l'URL per lo spazio prima.

6
00:00:17,000 --> 00:00:22,000
L'inizio della sezione delle domande dire-

7
00:00:22,000 --> 00:00:26,000
a quanto pare non sono del tutto unsick-è una domanda molto semplice

8
00:00:26,000 --> 00:00:28,000
di ciò che è valgrind?

9
00:00:28,000 --> 00:00:30,000
Cosa fa valgrind fare?

10
00:00:30,000 --> 00:00:34,000
Qualcuno vuole dire cosa valgrind fa?

11
00:00:34,000 --> 00:00:36,000
[Studente] Controlli perdite di memoria.

12
00:00:36,000 --> 00:00:41,000
Si ', Valgrind è una pedina di memoria generale.

13
00:00:41,000 --> 00:00:44,000
E, alla fine, ti dice se hai perdite di memoria,

14
00:00:44,000 --> 00:00:49,000
che è in gran parte quello che stiamo usando per perché se si vuole

15
00:00:49,000 --> 00:00:54,000
fare bene nel set problema o se si desidera

16
00:00:54,000 --> 00:00:59,000
salire sulla tavola grande, è necessario non avere perdite di memoria di sorta,

17
00:00:59,000 --> 00:01:01,000
e nel caso in cui si ha una perdita di memoria che non si può trovare,

18
00:01:01,000 --> 00:01:04,000
anche tenere a mente che ogni volta che si apre un file

19
00:01:04,000 --> 00:01:07,000
e se non si chiude, che è una perdita di memoria.

20
00:01:07,000 --> 00:01:10,000
>> Un sacco di persone sono alla ricerca di un nodo che non stanno liberando

21
00:01:10,000 --> 00:01:15,000
quando in realtà, non chiudere il dizionario nel primo passo.

22
00:01:15,000 --> 00:01:19,000
Si dice anche che se una valida legge o scrive,

23
00:01:19,000 --> 00:01:22,000
il che significa che se si cerca di impostare un valore

24
00:01:22,000 --> 00:01:26,000
che va oltre la fine del mucchio e non accade per colpa seg

25
00:01:26,000 --> 00:01:30,000
ma Valgrind lo cattura, come non si dovrebbe effettivamente essere iscritto lì,

26
00:01:30,000 --> 00:01:33,000
e quindi sicuramente non dovrebbe avere una di queste due.

27
00:01:33,000 --> 00:01:38,000
Come si usa valgrind?

28
00:01:38,000 --> 00:01:42,000
Come si usa valgrind?

29
00:01:42,000 --> 00:01:45,000
>> E 'una questione generale di

30
00:01:45,000 --> 00:01:49,000
tipo di eseguirlo e guardare l'output.

31
00:01:49,000 --> 00:01:51,000
L'uscita è travolgendo un sacco di volte.

32
00:01:51,000 --> 00:01:54,000
Ci sono anche errori divertenti in cui, se avete qualche cosa di terribilmente sbagliato

33
00:01:54,000 --> 00:01:59,000
accade in un ciclo, poi alla fine dire: "Via troppi errori.

34
00:01:59,000 --> 00:02:03,000
Ho intenzione di smettere di contare ora. "

35
00:02:03,000 --> 00:02:08,000
Si tratta fondamentalmente di output testuale che si deve analizzare.

36
00:02:08,000 --> 00:02:13,000
Alla fine, vi dirà tutte le perdite di memoria che avete,

37
00:02:13,000 --> 00:02:16,000
il numero di blocchi, che può essere utile perché

38
00:02:16,000 --> 00:02:20,000
se si tratta di uno unfreed blocco, poi di solito è più facile trovare

39
00:02:20,000 --> 00:02:23,000
oltre 1.000 blocchi unfreed.

40
00:02:23,000 --> 00:02:26,000
1.000 blocchi unfreed probabilmente significa che non stai liberando

41
00:02:26,000 --> 00:02:30,000
le liste collegate in modo appropriato o qualcosa del genere.

42
00:02:30,000 --> 00:02:32,000
Questo è valgrind.

43
00:02:32,000 --> 00:02:35,000
>> Ora abbiamo la nostra sezione di domande,

44
00:02:35,000 --> 00:02:38,000
che non è necessario scaricare.

45
00:02:38,000 --> 00:02:41,000
È possibile fare clic sul mio nome e tirare in su nello spazio.

46
00:02:41,000 --> 00:02:44,000
Ora cliccate su di me.

47
00:02:44,000 --> 00:02:46,000
Revisione 1 sarà stack, che stiamo facendo per primi.

48
00:02:46,000 --> 00:02:55,000
Revisione 2 sarà coda e Revisione 3 sarà la lista concatenata.

49
00:02:55,000 --> 00:02:58,000
Partendo con il nostro stack.

50
00:02:58,000 --> 00:03:02,000
Come si dice qui, una pila è uno dei più basilari,

51
00:03:02,000 --> 00:03:07,000
strutture di dati fondamentali di informatica.

52
00:03:07,000 --> 00:03:11,000
L'esempio è molto prototipo

53
00:03:11,000 --> 00:03:13,000
la pila di vassoi nella sala da pranzo.

54
00:03:13,000 --> 00:03:16,000
E 'fondamentalmente ogni volta che sono state introdotte per una pila,

55
00:03:16,000 --> 00:03:20,000
qualcuno sta per dire: "Oh, come una pila di piatti."

56
00:03:20,000 --> 00:03:22,000
È impilare i vassoi in su.

57
00:03:22,000 --> 00:03:24,000
Poi, quando si va a tirare un vassoio,

58
00:03:24,000 --> 00:03:31,000
il primo vassoio che sta facendo è tirato l'ultimo che è stato messo in pila.

59
00:03:31,000 --> 00:03:34,000
Lo stack anche-come dice qui-

60
00:03:34,000 --> 00:03:37,000
abbiamo il segmento di memoria chiamata stack.

61
00:03:37,000 --> 00:03:40,000
E perché si chiama la pila?

62
00:03:40,000 --> 00:03:42,000
>> Poiché come una struttura di dati pila,

63
00:03:42,000 --> 00:03:46,000
spinge e si apre stack frame sullo stack,

64
00:03:46,000 --> 00:03:53,000
dove stack frame sono come una specifica chiamata di una funzione.

65
00:03:53,000 --> 00:03:57,000
E come una pila, si dovrà sempre tornare

66
00:03:57,000 --> 00:04:03,000
da una chiamata di funzione prima di poter scendere in stack frame inferiori di nuovo.

67
00:04:03,000 --> 00:04:08,000
Non si può avere principale chiamata di blocco chiamata foo e tornare direttamente alla barra principale.

68
00:04:08,000 --> 00:04:14,000
E 'sempre avuto modo di seguire la pila giusta spinta e popping.

69
00:04:14,000 --> 00:04:18,000
Le due operazioni, come ho detto, sono push e pop.

70
00:04:18,000 --> 00:04:20,000
Questi sono termini universali.

71
00:04:20,000 --> 00:04:26,000
Si deve sapere push e pop, in termini di stack non importa quale.

72
00:04:26,000 --> 00:04:28,000
Staremo a vedere le code sono un po 'diverse.

73
00:04:28,000 --> 00:04:32,000
E 'in realtà non hanno un termine universale, ma push e pop sono universale per pile.

74
00:04:32,000 --> 00:04:34,000
Push è solo messa in pila.

75
00:04:34,000 --> 00:04:37,000
Pop è togliere la pila.

76
00:04:37,000 --> 00:04:43,000
E vediamo qui abbiamo il nostro stack typedef struct,

77
00:04:43,000 --> 00:04:46,000
così abbiamo stringhe char **.

78
00:04:46,000 --> 00:04:51,000
Non avere paura di qualsiasi **.

79
00:04:51,000 --> 00:04:54,000
Questo sta per finire per essere un array di stringhe

80
00:04:54,000 --> 00:04:58,000
o un array di puntatori a caratteri, dove

81
00:04:58,000 --> 00:05:00,000
puntatori a caratteri tendono ad essere stringhe.

82
00:05:00,000 --> 00:05:05,000
Essa non deve essere stringhe, ma qui, che stanno andando a essere stringhe.

83
00:05:05,000 --> 00:05:08,000
>> Abbiamo un array di stringhe.

84
00:05:08,000 --> 00:05:14,000
Abbiamo una dimensione, che rappresenta quanti elementi sono attualmente in pila,

85
00:05:14,000 --> 00:05:19,000
e poi abbiamo la capacità, che è il numero di elementi possono essere in pila.

86
00:05:19,000 --> 00:05:22,000
La capacità dovrebbe cominciare come qualcosa di più grande di 1,

87
00:05:22,000 --> 00:05:27,000
ma la dimensione sta per iniziare come 0.

88
00:05:27,000 --> 00:05:36,000
Ora, ci sono fondamentalmente tre modi diversi si può pensare di una pila.

89
00:05:36,000 --> 00:05:39,000
Beh, ci sono probabilmente di più, ma i due modi principali sono

90
00:05:39,000 --> 00:05:43,000
è possibile implementare utilizzando un array, oppure è possibile implementare con una lista concatenata.

91
00:05:43,000 --> 00:05:48,000
Liste collegate sono un po 'banali per fare pile da.

92
00:05:48,000 --> 00:05:51,000
E 'molto facile fare una pila con liste collegate,

93
00:05:51,000 --> 00:05:55,000
ecco, stiamo andando a fare una pila l'utilizzo di matrici,

94
00:05:55,000 --> 00:05:59,000
e poi l'utilizzo di matrici, ci sono anche due modi si può pensare a questo proposito.

95
00:05:59,000 --> 00:06:01,000
Prima, quando ho detto che abbiamo una capacità di stack,

96
00:06:01,000 --> 00:06:04,000
in modo da poter inserire un elemento nello stack.

97
00:06:04,000 --> 00:06:09,000
>> L'unico modo in cui potrebbe accadere è appena colpito 10 elementi, allora il gioco è fatto.

98
00:06:09,000 --> 00:06:13,000
Si potrebbe sapere che esiste un limite superiore di 10 cose del mondo

99
00:06:13,000 --> 00:06:16,000
che non avrete mai più di 10 cose sul tuo stack,

100
00:06:16,000 --> 00:06:20,000
nel qual caso si può avere un limite superiore per la dimensione del tuo stack.

101
00:06:20,000 --> 00:06:23,000
Oppure si potrebbe avere il tuo stack essere illimitato,

102
00:06:23,000 --> 00:06:27,000
ma se si sta facendo una matrice, il che significa che ogni volta che si ha colpito 10 elementi,

103
00:06:27,000 --> 00:06:29,000
allora si sta andando ad avere per crescere fino a 20 elementi, e quando si colpisce 20 elementi,

104
00:06:29,000 --> 00:06:33,000
si sta andando ad avere per far crescere la tua matrice a 30 elementi o 40 elementi.

105
00:06:33,000 --> 00:06:37,000
Stai andando ad avere bisogno di aumentare la capacità, che è quello che andremo a fare qui.

106
00:06:37,000 --> 00:06:40,000
Ogni volta si raggiunge la dimensione massima del nostro stack,

107
00:06:40,000 --> 00:06:46,000
quando spingiamo qualcos'altro, stiamo andando ad avere bisogno per aumentare la capacità.

108
00:06:46,000 --> 00:06:50,000
Qui, abbiamo spinta dichiarata come spinta bool (char * str).

109
00:06:50,000 --> 00:06:54,000
Str * Char è la stringa che stiamo spingendo nello stack,

110
00:06:54,000 --> 00:06:58,000
bool e dice solo se ci siamo riusciti o meno.

111
00:06:58,000 --> 00:07:00,000
>> Come non?

112
00:07:00,000 --> 00:07:04,000
Qual è l'unica circostanza che si può pensare di

113
00:07:04,000 --> 00:07:07,000
dove ci sarebbe bisogno di restituire false?

114
00:07:07,000 --> 00:07:09,000
Gia '.

115
00:07:09,000 --> 00:07:12,000
[Studente] Se è pieno e che stiamo usando una applicazione limitata.

116
00:07:12,000 --> 00:07:17,000
Sì, così come si definiscono, ha risposto

117
00:07:17,000 --> 00:07:23,000
se è pieno e stiamo utilizzando una implementazione limitata.

118
00:07:23,000 --> 00:07:26,000
Poi ci ritorneremo sicuramente false.

119
00:07:26,000 --> 00:07:31,000
Non appena abbiamo raggiunto 10 cose nella matrice, non può andare bene 11, in modo da restituire false.

120
00:07:31,000 --> 00:07:32,000
E se è illimitato? Gia '.

121
00:07:32,000 --> 00:07:38,000
Se non è possibile espandere l'array per qualche motivo.

122
00:07:38,000 --> 00:07:43,000
Sì, così la memoria è una risorsa limitata,

123
00:07:43,000 --> 00:07:51,000
e alla fine, se le cose che spingono nello stack più e più volte,

124
00:07:51,000 --> 00:07:54,000
stiamo andando a cercare di allocare un array più grande per adattarsi

125
00:07:54,000 --> 00:07:59,000
la maggiore capacità, e malloc o qualsiasi altra cosa che stiamo usando sta per restituire false.

126
00:07:59,000 --> 00:08:02,000
Beh, malloc restituirà null.

127
00:08:02,000 --> 00:08:05,000
>> Ricordate, ogni volta che si chiama malloc mai, si dovrebbe controllare per vedere se

128
00:08:05,000 --> 00:08:12,000
restituisce null oppure che è una deduzione correttezza.

129
00:08:12,000 --> 00:08:17,000
Dal momento che vogliamo avere uno stack illimitato,

130
00:08:17,000 --> 00:08:21,000
l'unico caso abbiamo intenzione di tornare false è se cerchiamo di

131
00:08:21,000 --> 00:08:26,000
aumentare la capacità e malloc o qualsiasi altra cosa restituisce false.

132
00:08:26,000 --> 00:08:30,000
Poi pop non accetta argomenti,

133
00:08:30,000 --> 00:08:37,000
e restituisce la stringa che è in cima alla pila.

134
00:08:37,000 --> 00:08:41,000
Qualunque è stato recentemente inserito nello stack è quello pop sta tornando,

135
00:08:41,000 --> 00:08:44,000
ed è anche lo rimuove dalla pila.

136
00:08:44,000 --> 00:08:50,000
E notare che restituisce null se non c'è niente in pila.

137
00:08:50,000 --> 00:08:53,000
E 'sempre possibile che la pila è vuota.

138
00:08:53,000 --> 00:08:55,000
In Java, se siete abituati a questo, o altre lingue,

139
00:08:55,000 --> 00:09:01,000
cercando di pop da uno stack vuoto può causare un'eccezione o qualcosa del genere.

140
00:09:01,000 --> 00:09:09,000
>> Ma in C, null è una specie di sacco di casi come gestire questi problemi.

141
00:09:09,000 --> 00:09:13,000
Tornando nulla è come stiamo andando a significare che la pila è vuota.

142
00:09:13,000 --> 00:09:16,000
Abbiamo messo a disposizione il codice che metterà alla prova la funzionalità del vostro stack,

143
00:09:16,000 --> 00:09:19,000
implementare push e pop.

144
00:09:19,000 --> 00:09:23,000
Questo non sarà un sacco di codice.

145
00:09:23,000 --> 00:09:40,000
Lo farò-in realtà, prima di farlo, suggerimento, suggerimento-

146
00:09:40,000 --> 00:09:44,000
se non l'avete visto, malloc non è l'unica funzione

147
00:09:44,000 --> 00:09:47,000
che alloca la memoria per l'heap per voi.

148
00:09:47,000 --> 00:09:51,000
Ci sono una famiglia di funzioni alloc.

149
00:09:51,000 --> 00:09:53,000
Il primo è malloc, che siete abituati.

150
00:09:53,000 --> 00:09:56,000
Poi c'è calloc, che fa la stessa cosa come malloc,

151
00:09:56,000 --> 00:09:59,000
ma si azzererà tutto per voi.

152
00:09:59,000 --> 00:10:04,000
Se hai sempre voluto impostare tutto su null dopo mallocing qualcosa

153
00:10:04,000 --> 00:10:06,000
si dovrebbe avere appena usato calloc in primo luogo, invece di scrivere

154
00:10:06,000 --> 00:10:09,000
un ciclo for per azzerare l'intero blocco di memoria.

155
00:10:09,000 --> 00:10:15,000
>> Realloc è come malloc e ha un sacco di casi particolari,

156
00:10:15,000 --> 00:10:19,000
ma in fondo quello che fa è realloc

157
00:10:19,000 --> 00:10:24,000
ci vuole un puntatore che erano già stati assegnati.

158
00:10:24,000 --> 00:10:27,000
Realloc è la funzione che si desidera prestare attenzione a qui.

159
00:10:27,000 --> 00:10:31,000
Ci vuole un puntatore che era già stato restituito da malloc.

160
00:10:31,000 --> 00:10:35,000
Diciamo che si richiede da malloc un puntatore di 10 byte.

161
00:10:35,000 --> 00:10:38,000
Poi dopo ci si rende conto che fa per te 20 byte,

162
00:10:38,000 --> 00:10:42,000
così si chiama realloc su quel puntatore con 20 byte,

163
00:10:42,000 --> 00:10:47,000
e realloc copia automaticamente su tutto per voi.

164
00:10:47,000 --> 00:10:51,000
Se hai appena chiamato malloc di nuovo, come se avessi un blocco di 10 byte.

165
00:10:51,000 --> 00:10:53,000
Ora ho bisogno di un blocco di 20 byte,

166
00:10:53,000 --> 00:10:58,000
quindi se io malloc 20 byte, allora devo copiare manualmente nel corso dei 10 byte dalla prima cosa che

167
00:10:58,000 --> 00:11:01,000
nella seconda cosa e poi libera la prima cosa.

168
00:11:01,000 --> 00:11:04,000
Realloc si occuperà per voi.

169
00:11:04,000 --> 00:11:11,000
>> Si noti la firma sarà void *,

170
00:11:11,000 --> 00:11:15,000
che è solo restituendo un puntatore al blocco di memoria,

171
00:11:15,000 --> 00:11:17,000
poi void * ptr.

172
00:11:17,000 --> 00:11:22,000
Si può pensare di void * come un puntatore generico.

173
00:11:22,000 --> 00:11:27,000
In genere, non si tratta con void *,

174
00:11:27,000 --> 00:11:30,000
ma malloc restituisce un void *, e quindi è solo usato come

175
00:11:30,000 --> 00:11:34,000
questo è in realtà sarà un char *.

176
00:11:34,000 --> 00:11:37,000
Il * vuoto precedente che era stato restituito da malloc

177
00:11:37,000 --> 00:11:41,000
sta ora per essere passato a realloc, e quindi le dimensioni

178
00:11:41,000 --> 00:11:49,000
è il nuovo numero di byte che si desidera assegnare, in modo che il nuova capacità.

179
00:11:49,000 --> 00:11:57,000
Ti do un paio di minuti, e lo fa nel nostro spazio.

180
00:11:57,000 --> 00:12:02,000
Inizia con revisione 1.

181
00:12:16,000 --> 00:12:21,000
Ti ferma dopo circa spera abbastanza tempo per implementare spinta,

182
00:12:21,000 --> 00:12:24,000
e poi ti darò un altro break di fare pop.

183
00:12:24,000 --> 00:12:27,000
Ma in realtà non è che il codice molto a tutti.

184
00:12:27,000 --> 00:12:35,000
La maggior parte del codice è probabilmente la roba in espansione, l'espansione della capacità.

185
00:12:35,000 --> 00:12:39,000
Ok, nessuna pressione per essere completamente fatta,

186
00:12:39,000 --> 00:12:47,000
ma fino a quando ti senti come se fossi sulla strada giusta, questo è un bene.

187
00:12:47,000 --> 00:12:53,000
>> Qualcuno ha qualche codice che sentirsi a proprio agio con me, tirando verso l'alto?

188
00:12:53,000 --> 00:12:59,000
Si ', lo faro', ma qualcuno ha qualche codice che posso tirare su?

189
00:12:59,000 --> 00:13:05,000
Ok, si può avviare, salvarlo, qualunque cosa sia?

190
00:13:05,000 --> 00:13:09,000
Mi dimentico sempre quel passo.

191
00:13:09,000 --> 00:13:15,000
Ok, guardando spinta,

192
00:13:15,000 --> 00:13:18,000
vuoi spiegare il tuo codice?

193
00:13:18,000 --> 00:13:24,000
[Studente] Prima di tutto, ho aumentato la dimensione.

194
00:13:24,000 --> 00:13:28,000
Credo che forse avrei dovuto che-in ogni caso, ho aumentato la dimensione,

195
00:13:28,000 --> 00:13:31,000
e vedo se è inferiore alla capacità.

196
00:13:31,000 --> 00:13:36,000
E se è inferiore alla capacità, aggiungo alla matrice che abbiamo già.

197
00:13:36,000 --> 00:13:42,000
E se non lo è, ho la capacità di moltiplicare per 2,

198
00:13:42,000 --> 00:13:50,000
Io e riallocare l'array stringhe a qualcosa con una dimensione maggiore capacità ora.

199
00:13:50,000 --> 00:13:55,000
E poi, se non funziona, dico l'utente e restituire false,

200
00:13:55,000 --> 00:14:04,000
e se va bene, poi ho messo la stringa nel nuovo spot.

201
00:14:04,000 --> 00:14:07,000
>> [Rob B.] Si noti inoltre che abbiamo usato un operatore bit a bit bella qui

202
00:14:07,000 --> 00:14:09,000
da moltiplicare per 2.

203
00:14:09,000 --> 00:14:11,000
Ricordate, spostamento a sinistra sta andando sempre essere moltiplicato per 2.

204
00:14:11,000 --> 00:14:15,000
Spostamento a destra è diviso per 2 fino a quando si ricordi che significa

205
00:14:15,000 --> 00:14:18,000
dividere per 2 come in un intero diviso 2.

206
00:14:18,000 --> 00:14:20,000
Si potrebbe troncare un 1 qua e là.

207
00:14:20,000 --> 00:14:26,000
Ma spostamento a sinistra di 1 sta andando sempre essere moltiplicato per 2,

208
00:14:26,000 --> 00:14:32,000
meno che non si troppo pieno i limiti del numero intero, e quindi non sarà.

209
00:14:32,000 --> 00:14:34,000
Un commento lato.

210
00:14:34,000 --> 00:14:39,000
Mi piace fare, questo non sta andando a cambiare il codice qualsiasi modo,

211
00:14:39,000 --> 00:14:48,000
ma mi piace fare qualcosa di simile.

212
00:14:48,000 --> 00:14:51,000
In realtà sta per renderlo un po 'più a lungo.

213
00:15:04,000 --> 00:15:08,000
Forse questo non è il caso perfetto per mostrare questo,

214
00:15:08,000 --> 00:15:14,000
ma mi piace a dividerlo in questi blocchi di-

215
00:15:14,000 --> 00:15:17,000
Va bene, se questo accade se, poi ho intenzione di fare qualcosa,

216
00:15:17,000 --> 00:15:19,000
e quindi la funzione viene eseguita.

217
00:15:19,000 --> 00:15:22,000
Non ho bisogno di scorrere poi i miei occhi fino in fondo la funzione

218
00:15:22,000 --> 00:15:25,000
per vedere cosa succede dopo l'altro.

219
00:15:25,000 --> 00:15:27,000
E 'se questo se succede, allora ho appena ritorno.

220
00:15:27,000 --> 00:15:30,000
Essa ha anche il bel vantaggio aggiunto di ogni cosa al di là di questo

221
00:15:30,000 --> 00:15:33,000
è ora spostato a sinistra una volta.

222
00:15:33,000 --> 00:15:40,000
Non ho più bisogno di, se mai vicino ridicolmente lunghe code,

223
00:15:40,000 --> 00:15:45,000
allora quei 4 byte può aiutare, e anche la sinistra è qualcosa di più,

224
00:15:45,000 --> 00:15:48,000
meno sopraffatto vi sentireste se piace-va bene, devo ricordare

225
00:15:48,000 --> 00:15:53,000
Sono attualmente in un ciclo while all'interno di un altro all'interno di un ciclo for.

226
00:15:53,000 --> 00:15:58,000
Ovunque si può fare questo ritorno subito, ho un po 'come.

227
00:15:58,000 --> 00:16:05,000
E 'del tutto facoltativo e non previsto in alcun modo.

228
00:16:05,000 --> 00:16:12,000
>> [Studente] Dovrebbe esserci una dimensione - nella condizione di sicuro?

229
00:16:12,000 --> 00:16:19,000
La condizione di sicuro qui non siamo riusciti a realloc, quindi sì.

230
00:16:19,000 --> 00:16:22,000
Si noti come nella condizione di sicuro, presumibilmente,

231
00:16:22,000 --> 00:16:26,000
a meno che non roba gratuitamente più tardi, stiamo andando sempre a fallire

232
00:16:26,000 --> 00:16:29,000
non importa quante volte cerchiamo di spingere qualcosa.

233
00:16:29,000 --> 00:16:32,000
Se continuiamo a spingere, continuiamo a dimensione di incremento,

234
00:16:32,000 --> 00:16:36,000
anche se non mettono nulla in cima alla pila.

235
00:16:36,000 --> 00:16:39,000
Di solito non incrementare le dimensioni fino a

236
00:16:39,000 --> 00:16:43,000
dopo aver con successo messa in pila.

237
00:16:43,000 --> 00:16:50,000
Ci avrebbe fatto, per esempio, sia qui e qui.

238
00:16:50,000 --> 00:16:56,000
E poi invece di dire s.size capacità ≤, è inferiore alla capacità,

239
00:16:56,000 --> 00:17:01,000
solo perché ci siamo trasferiti dove tutto era.

240
00:17:01,000 --> 00:17:07,000
>> E ricordate, l'unico posto che potrebbe restituire false

241
00:17:07,000 --> 00:17:14,000
è qui, dove realloc restituito null,

242
00:17:14,000 --> 00:17:19,000
e se vi capita di ricordare errore standard,

243
00:17:19,000 --> 00:17:22,000
forse si potrebbe considerare questo un caso in cui si desidera stampare un errore standard,

244
00:17:22,000 --> 00:17:26,000
fprintf stderr così invece di stampare direttamente fuori standard.

245
00:17:26,000 --> 00:17:31,000
Anche in questo caso, non è una previsione, ma se si tratta di un errore,

246
00:17:31,000 --> 00:17:41,000
printf tipo, allora si potrebbe desiderare di farlo stampare errore standard, invece di standard out.

247
00:17:41,000 --> 00:17:44,000
>> Qualcuno ha altro da notare? Sì.

248
00:17:44,000 --> 00:17:47,000
[Studente] Si può andare oltre il [incomprensibile]?

249
00:17:47,000 --> 00:17:55,000
[Rob B.] Sì, la binariness reale di esso o semplicemente quello che è?

250
00:17:55,000 --> 00:17:57,000
[Studente] Quindi si moltiplica per 2?

251
00:17:57,000 --> 00:17:59,000
[Rob B.] Si ', in fondo.

252
00:17:59,000 --> 00:18:11,000
In terra binario, abbiamo sempre la nostra serie di cifre.

253
00:18:11,000 --> 00:18:22,000
Spostando questa sinistra di 1 fondamentalmente inserisce qui sul lato destro.

254
00:18:22,000 --> 00:18:25,000
Torna a questa, anche per ricordare che tutto in binario

255
00:18:25,000 --> 00:18:28,000
è una potenza di 2, quindi questo rappresenta 2 a 0,

256
00:18:28,000 --> 00:18:30,000
questo 2 alla 1, questo 2 al 2.

257
00:18:30,000 --> 00:18:33,000
Con l'inserimento di uno 0 a destra ora, dobbiamo solo spostare tutto finito.

258
00:18:33,000 --> 00:18:38,000
Quello che prima era 2 a 0 è ora la 2 alla 1, è 2 al 2.

259
00:18:38,000 --> 00:18:41,000
Il lato destro che abbiamo inserito

260
00:18:41,000 --> 00:18:44,000
è necessariamente sarà 0,

261
00:18:44,000 --> 00:18:46,000
che ha un senso.

262
00:18:46,000 --> 00:18:49,000
Se mai moltiplicare un numero per 2, non sta andando a finire dispari,

263
00:18:49,000 --> 00:18:54,000
così il 2 al posto 0 deve essere 0,

264
00:18:54,000 --> 00:18:59,000
e questo è quello che ho avvertito mezzo circa prima è che se vi capita di passare

265
00:18:59,000 --> 00:19:01,000
oltre il numero di bit in un numero intero,

266
00:19:01,000 --> 00:19:04,000
allora questo 1 sta per finire andare fuori.

267
00:19:04,000 --> 00:19:10,000
Questa è l'unica preoccupazione se vi capita di avere a che fare con capacità davvero di grandi dimensioni.

268
00:19:10,000 --> 00:19:15,000
Ma a quel punto, allora hai a che fare con una serie di miliardi di cose,

269
00:19:15,000 --> 00:19:25,000
che non potrebbe andare bene nella memoria in ogni caso.

270
00:19:25,000 --> 00:19:31,000
>> Ora siamo in grado di arrivare al pop, che è ancora più facile.

271
00:19:31,000 --> 00:19:36,000
Si potrebbe ti piace se vi capita di pop un intero gruppo,

272
00:19:36,000 --> 00:19:38,000
e ora sei a metà della capacità di nuovo.

273
00:19:38,000 --> 00:19:42,000
Si potrebbe realloc per ridurre la quantità di memoria disponibile,

274
00:19:42,000 --> 00:19:47,000
ma non devi preoccuparti di questo, quindi il caso realloc solo sta per essere

275
00:19:47,000 --> 00:19:50,000
crescente di memoria, mai restringimento memoria,

276
00:19:50,000 --> 00:19:59,000
che sta andando a fare super-pop facile.

277
00:19:59,000 --> 00:20:02,000
Ora le code, che stanno per essere come pile,

278
00:20:02,000 --> 00:20:06,000
ma l'ordine di prendere le cose è invertita.

279
00:20:06,000 --> 00:20:10,000
L'esempio tipico di una coda è una linea,

280
00:20:10,000 --> 00:20:12,000
quindi suppongo che se tu fossi inglese, avrei detto

281
00:20:12,000 --> 00:20:17,000
un esempio tipico di una coda è una coda.

282
00:20:17,000 --> 00:20:22,000
Così come una linea, se sei la prima persona in linea,

283
00:20:22,000 --> 00:20:24,000
ci si aspetta di essere la prima persona fuori dalla linea.

284
00:20:24,000 --> 00:20:31,000
Se tu sei l'ultima persona in linea, che si sta per essere l'ultima persona a manutenzione.

285
00:20:31,000 --> 00:20:35,000
Noi chiamiamo questo modello FIFO, mentre la pila era motivo LIFO.

286
00:20:35,000 --> 00:20:40,000
Queste parole sono abbastanza universali.

287
00:20:40,000 --> 00:20:46,000
>> Come pile e, a differenza di matrici, le code di solito non consentono l'accesso agli elementi nel mezzo.

288
00:20:46,000 --> 00:20:50,000
Qui, una pila, abbiamo push e pop.

289
00:20:50,000 --> 00:20:54,000
Qui, ci capita di li hanno chiamati enqueue e dequeue.

290
00:20:54,000 --> 00:20:58,000
Ho anche sentito li chiamava turno e unshift.

291
00:20:58,000 --> 00:21:02,000
Ho sentito dire push e pop di applicare anche alle code.

292
00:21:02,000 --> 00:21:05,000
Ho sentito inserire, rimuovere,

293
00:21:05,000 --> 00:21:11,000
così push e pop, se si parla di pile, si sta spingendo e popping.

294
00:21:11,000 --> 00:21:16,000
Se si parla di code, è possibile scegliere le parole che si desidera utilizzare

295
00:21:16,000 --> 00:21:23,000
per l'inserimento e la rimozione, e non c'è consenso su ciò che dovrebbe essere chiamato.

296
00:21:23,000 --> 00:21:27,000
Ma qui, abbiamo enqueue e dequeue.

297
00:21:27,000 --> 00:21:37,000
Ora, la struttura sembra quasi identico al struct stack.

298
00:21:37,000 --> 00:21:40,000
Ma dobbiamo tenere traccia di testa.

299
00:21:40,000 --> 00:21:44,000
Credo che si dice qui, ma perché abbiamo bisogno della testa?

300
00:21:53,000 --> 00:21:57,000
I prototipi sono sostanzialmente identiche a push e pop.

301
00:21:57,000 --> 00:21:59,000
Si può pensare ad esso come push e pop.

302
00:21:59,000 --> 00:22:08,000
L'unica differenza è pop-sta tornando invece dell'ultima, è il primo ritorno.

303
00:22:08,000 --> 00:22:12,000
2, 1, 3, 4, o qualcosa.

304
00:22:12,000 --> 00:22:14,000
Ed ecco l'inizio.

305
00:22:14,000 --> 00:22:17,000
La coda è completamente pieno, quindi ci sono quattro elementi in esso.

306
00:22:17,000 --> 00:22:21,000
La fine della nostra coda è attualmente 2,

307
00:22:21,000 --> 00:22:24,000
e adesso andiamo a inserire qualcosa d'altro.

308
00:22:24,000 --> 00:22:29,000
>> Quando vogliamo inserire qualcosa d'altro che, quello che abbiamo fatto per la versione dello stack

309
00:22:29,000 --> 00:22:36,000
è abbiamo prolungato il nostro blocco di memoria.

310
00:22:36,000 --> 00:22:40,000
Qual è il problema con questo?

311
00:22:40,000 --> 00:22:45,000
[Studente] Si sposta il 2.

312
00:22:45,000 --> 00:22:51,000
Quello che ho detto prima circa la fine della coda,

313
00:22:51,000 --> 00:22:57,000
questo non ha senso che partono da 1,

314
00:22:57,000 --> 00:23:01,000
poi vogliamo dequeue 1, poi dequeue 3, quindi dequeue 4,

315
00:23:01,000 --> 00:23:05,000
poi dequeue 2, quindi annullare l'accodamento questo.

316
00:23:05,000 --> 00:23:08,000
Non possiamo usare realloc ora,

317
00:23:08,000 --> 00:23:11,000
o per lo meno, bisogna usare realloc in modo diverso.

318
00:23:11,000 --> 00:23:15,000
Ma probabilmente non basta usare realloc.

319
00:23:15,000 --> 00:23:18,000
Si sta andando ad avere per copiare manualmente la memoria.

320
00:23:18,000 --> 00:23:21,000
>> Ci sono due funzioni per copiare la memoria.

321
00:23:21,000 --> 00:23:25,000
C'è memcopy e memmove.

322
00:23:25,000 --> 00:23:29,000
Attualmente sto leggendo le pagine man per vedere quale si sta andando a voler utilizzare.

323
00:23:29,000 --> 00:23:35,000
Ok, memcopy, la differenza è

324
00:23:35,000 --> 00:23:38,000
che memcopy e memmove, uno gestisce il caso correttamente

325
00:23:38,000 --> 00:23:41,000
dove si sta copiando in una regione che sembra sovrapporsi alla regione

326
00:23:41,000 --> 00:23:46,000
si sta copiando dal.

327
00:23:46,000 --> 00:23:50,000
Memcopy non gestire la cosa. Memmove fa.

328
00:23:50,000 --> 00:23:59,000
Si può pensare il problema come-

329
00:23:59,000 --> 00:24:09,000
diciamo che voglio copiare questo ragazzo,

330
00:24:09,000 --> 00:24:13,000
questi quattro a questo tizio.

331
00:24:13,000 --> 00:24:16,000
Alla fine, quello che la matrice dovrebbe essere simile

332
00:24:16,000 --> 00:24:26,000
dopo la copia è 2, 1, 2, 1, 3, 4, e quindi alcune cose alla fine.

333
00:24:26,000 --> 00:24:29,000
Ma questo dipende dall'ordine in cui effettivamente copiare,

334
00:24:29,000 --> 00:24:32,000
poiché, se non consideriamo il fatto che la regione che stiamo copiando in

335
00:24:32,000 --> 00:24:35,000
sovrappone quello che sta copiando dal,

336
00:24:35,000 --> 00:24:46,000
allora potremmo fare come inizio qui, copiare il 2 nel luogo che vogliamo andare,

337
00:24:46,000 --> 00:24:52,000
quindi spostare in avanti i nostri puntatori.

338
00:24:52,000 --> 00:24:56,000
>> Ora stiamo andando a essere qui e qui, e ora vogliamo copiare

339
00:24:56,000 --> 00:25:04,000
questo ragazzo su questo ragazzo e andare avanti i nostri puntatori.

340
00:25:04,000 --> 00:25:07,000
Quello che stiamo andando a finire per ottenere è 2, 1, 2, 1, 2, 1

341
00:25:07,000 --> 00:25:10,000
invece del caso 2, 1, 2, 1, 3, 4 perché

342
00:25:10,000 --> 00:25:15,000
2, 1 sovrascritto originale 3, 4.

343
00:25:15,000 --> 00:25:19,000
Memmove gestisce che correttamente.

344
00:25:19,000 --> 00:25:23,000
In questo caso, in fondo basta usare sempre memmove

345
00:25:23,000 --> 00:25:26,000
perché lo gestisce correttamente.

346
00:25:26,000 --> 00:25:29,000
E 'in genere non esegue peggio.

347
00:25:29,000 --> 00:25:32,000
L'idea è invece di partire dall'inizio e copiare questo modo

348
00:25:32,000 --> 00:25:35,000
come abbiamo appena fatto qui, inizia dalla fine e in copia,

349
00:25:35,000 --> 00:25:38,000
e in tal caso, non si può mai avere un problema.

350
00:25:38,000 --> 00:25:40,000
Non vi è alcun prestazioni perse.

351
00:25:40,000 --> 00:25:47,000
Utilizzare sempre memmove. Non preoccuparti memcopy.

352
00:25:47,000 --> 00:25:51,000
Ed è lì che si sta andando ad avere per memmove separatamente

353
00:25:51,000 --> 00:26:01,000
l'avvolgi parte della coda.

354
00:26:01,000 --> 00:26:04,000
Nessun problema se non completamente fatto.

355
00:26:04,000 --> 00:26:10,000
Questo è più difficile di pila, push e pop.

356
00:26:10,000 --> 00:26:15,000
>> Qualcuno ha qualche codice che potrebbe lavorare con?

357
00:26:15,000 --> 00:26:21,000
Anche se del tutto incompleta?

358
00:26:21,000 --> 00:26:23,000
[Studente] ', e' del tutto incompleto, però.

359
00:26:23,000 --> 00:26:27,000
Completamente incompleta va bene fintanto che-si può risparmiare la revisione?

360
00:26:27,000 --> 00:26:32,000
Mi dimentico che ogni singola volta.

361
00:26:32,000 --> 00:26:39,000
Ok, ignorando ciò che succede quando abbiamo bisogno di ridimensionare le cose.

362
00:26:39,000 --> 00:26:42,000
Completamente ignorare ridimensionamento.

363
00:26:42,000 --> 00:26:49,000
Spiega questo codice.

364
00:26:49,000 --> 00:26:54,000
Sto controllando prima di tutto se la dimensione è minore della prima copia di tutti

365
00:26:54,000 --> 00:27:01,000
e poi, dopo che, inserisco-prendo la testa + dimensioni,

366
00:27:01,000 --> 00:27:05,000
e assicurarsi che avvolge la capacità della matrice,

367
00:27:05,000 --> 00:27:08,000
e inserire la nuova stringa in quella posizione.

368
00:27:08,000 --> 00:27:12,000
Poi aumentare la dimensione e restituire true.

369
00:27:12,000 --> 00:27:22,000
>> [Rob B.] Questo è sicuramente uno di quei casi in cui si sta andando a voler utilizzare mod.

370
00:27:22,000 --> 00:27:25,000
Qualsiasi tipo di caso in cui avete avvolgono, se pensi che avvolgono,

371
00:27:25,000 --> 00:27:29,000
il primo pensiero dovrebbe essere mod.

372
00:27:29,000 --> 00:27:36,000
Come ottimizzazione rapida / rendere il codice una linea più breve,

373
00:27:36,000 --> 00:27:42,000
si nota che la linea subito dopo questo

374
00:27:42,000 --> 00:27:53,000
è solo dimensione + +, in modo che si uniscono in questa linea, le dimensioni + +.

375
00:27:53,000 --> 00:27:58,000
Ora qui, abbiamo il caso

376
00:27:58,000 --> 00:28:01,000
dove non si dispone di memoria sufficiente,

377
00:28:01,000 --> 00:28:05,000
quindi stiamo aumentando la nostra capacità di 2.

378
00:28:05,000 --> 00:28:09,000
Credo che si potrebbe avere lo stesso problema qui, ma siamo in grado di ignorare ora,

379
00:28:09,000 --> 00:28:13,000
dove se non siete riusciti a aumentare la capacità,

380
00:28:13,000 --> 00:28:18,000
allora si sta andando a voler diminuire la capacità di 2 nuovo.

381
00:28:18,000 --> 00:28:24,000
Un'altra breve nota è proprio come si può fare + =,

382
00:28:24,000 --> 00:28:30,000
si può anche fare << =.

383
00:28:30,000 --> 00:28:43,000
Quasi tutto può andare prima uguale, + =, | =, & =, << =.

384
00:28:43,000 --> 00:28:52,000
Char * nuovo è il nostro nuovo blocco di memoria.

385
00:28:52,000 --> 00:28:55,000
Oh, da questa parte.

386
00:28:55,000 --> 00:29:02,000
>> Che cosa la gente pensa il tipo del nostro nuovo blocco di memoria?

387
00:29:02,000 --> 00:29:06,000
[Studente] Dovrebbe essere char **.

388
00:29:06,000 --> 00:29:12,000
Ripensando alla nostra struttura qui,

389
00:29:12,000 --> 00:29:14,000
stringhe è quello che stiamo riallocazione.

390
00:29:14,000 --> 00:29:21,000
Facciamo un intero nuovo storage dinamico per gli elementi nella coda.

391
00:29:21,000 --> 00:29:25,000
Quello che sta andando ad essere l'assegnazione alle vostre stringhe è quello che stiamo mallocing in questo momento,

392
00:29:25,000 --> 00:29:30,000
e tanto nuova, sta per essere un char **.

393
00:29:30,000 --> 00:29:34,000
E 'intenzione di essere un array di stringhe.

394
00:29:34,000 --> 00:29:38,000
Allora qual è il caso in cui abbiamo intenzione di restituire false?

395
00:29:38,000 --> 00:29:41,000
[Studente] Dovremmo fare il char *?

396
00:29:41,000 --> 00:29:44,000
[Rob B.] Sì, buona chiamata.

397
00:29:44,000 --> 00:29:46,000
[Studente] Che cos'era?

398
00:29:46,000 --> 00:29:49,000
[Rob B.] Abbiamo voluto fare il formato di char *, perché non siamo più-

399
00:29:49,000 --> 00:29:53,000
questo sarebbe in realtà un problema molto grande perché sizeof (char) sarebbe 1.

400
00:29:53,000 --> 00:29:55,000
Sizeof char * sta per essere 4,

401
00:29:55,000 --> 00:29:58,000
così un sacco di volte in cui vi state occupando interi,

402
00:29:58,000 --> 00:30:01,000
si tende a farla franca perché la dimensione di int e la dimensione del int *

403
00:30:01,000 --> 00:30:04,000
su un sistema a 32 bit stanno per essere la stessa cosa.

404
00:30:04,000 --> 00:30:09,000
Ma qui, sizeof (char) e sizeof (char *) sono ora sarà la stessa cosa.

405
00:30:09,000 --> 00:30:15,000
>> Qual è la circostanza in cui si ritorna falso?

406
00:30:15,000 --> 00:30:17,000
[Studente] Nuovo è nullo.

407
00:30:17,000 --> 00:30:23,000
Si ', se nuovo è nullo, torniamo falso,

408
00:30:23,000 --> 00:30:34,000
e ho intenzione di buttare giù qui-

409
00:30:34,000 --> 00:30:37,000
[Studente] [incomprensibile]

410
00:30:37,000 --> 00:30:39,000
[Rob B.] Sì, questo va bene.

411
00:30:39,000 --> 00:30:46,000
Si potrebbe o fare 2 volte la capacità o turno di capacità 1, quindi solo impostare qui o qualsiasi altra cosa.

412
00:30:46,000 --> 00:30:52,000
Lo faremo come abbiamo avuto.

413
00:30:52,000 --> 00:30:56,000
Capacità >> = 1.

414
00:30:56,000 --> 00:31:08,000
E non si è mai costretta a preoccuparsi di perdere gli 1 posto

415
00:31:08,000 --> 00:31:12,000
perché te ne sei andato spostata di 1, per cui gli 1 posto è necessariamente uno 0,

416
00:31:12,000 --> 00:31:16,000
così giusto spostamento di 1, si sta ancora andando bene.

417
00:31:16,000 --> 00:31:19,000
[Studente] Avete bisogno di fare prima di ritorno?

418
00:31:19,000 --> 00:31:29,000
[Rob B.] Sì, questo non ha assolutamente senso.

419
00:31:29,000 --> 00:31:36,000
>> Supponiamo ora che stiamo andando a finire tornando true alla fine.

420
00:31:36,000 --> 00:31:39,000
Il modo in cui andremo a fare queste memmoves,

421
00:31:39,000 --> 00:31:45,000
dobbiamo stare attenti a come li fanno.

422
00:31:45,000 --> 00:31:50,000
Qualcuno ha qualche suggerimento per come li fanno?

423
00:32:17,000 --> 00:32:21,000
Ecco il nostro inizio.

424
00:32:21,000 --> 00:32:28,000
Inevitabilmente, vogliamo cominciare dall'inizio di nuovo

425
00:32:28,000 --> 00:32:35,000
e le cose in copia da lì, 1, 3, 4, 2.

426
00:32:35,000 --> 00:32:41,000
Come si fa a fare questo?

427
00:32:41,000 --> 00:32:52,000
In primo luogo, devo guardare la pagina man per memmove nuovo.

428
00:32:52,000 --> 00:32:57,000
Memmove, ordine degli argomenti è sempre importante.

429
00:32:57,000 --> 00:33:01,000
Vogliamo che la nostra prima destinazione, la seconda fonte, la terza dimensione.

430
00:33:01,000 --> 00:33:06,000
Ci sono molte funzioni che invertono sorgente e destinazione.

431
00:33:06,000 --> 00:33:11,000
Destinazione, sorgente tende ad essere alquanto coerente.

432
00:33:17,000 --> 00:33:21,000
Move, cosa sta tornando?

433
00:33:21,000 --> 00:33:27,000
Esso restituisce un puntatore a destinazione, per qualsiasi motivo si potrebbe desiderare che.

434
00:33:27,000 --> 00:33:32,000
Posso immaginare leggerlo, ma vogliamo andare nella nostra destinazione.

435
00:33:32,000 --> 00:33:35,000
>> Che cosa è la nostra destinazione sarà?

436
00:33:35,000 --> 00:33:37,000
[Studente] Nuovo.

437
00:33:37,000 --> 00:33:39,000
[Rob B.] Sì, e dove stiamo copiando?

438
00:33:39,000 --> 00:33:43,000
La prima cosa che la copia è questo 1, 3, 4.

439
00:33:43,000 --> 00:33:50,000
Qual è il presente-1, 3, 4.

440
00:33:50,000 --> 00:33:55,000
Qual è l'indirizzo di questo 1?

441
00:33:55,000 --> 00:33:58,000
Qual è l'indirizzo del 1?

442
00:33:58,000 --> 00:34:01,000
[Studente] [incomprensibile]

443
00:34:01,000 --> 00:34:03,000
[Rob B.] Testa + l'indirizzo del primo elemento.

444
00:34:03,000 --> 00:34:05,000
Come si ottiene il primo elemento della matrice?

445
00:34:05,000 --> 00:34:10,000
[Studente] coda.

446
00:34:10,000 --> 00:34:15,000
[Rob B.] Sì, q.strings.

447
00:34:15,000 --> 00:34:20,000
Ricordate, qui, la nostra testa è 1.

448
00:34:20,000 --> 00:34:24,000
Dannazione. Penso solo che sia magicamente-

449
00:34:24,000 --> 00:34:29,000
Qui, la nostra testa è 1. Ho intenzione di cambiare il mio colore troppo.

450
00:34:29,000 --> 00:34:36,000
Ed ecco le stringhe.

451
00:34:36,000 --> 00:34:41,000
Questo, si può scrivere come abbiamo fatto qui

452
00:34:41,000 --> 00:34:43,000
con la testa + q.strings.

453
00:34:43,000 --> 00:34:51,000
Un sacco di gente anche scrivi & q.strings [testa].

454
00:34:51,000 --> 00:34:55,000
Questo non è davvero meno efficiente.

455
00:34:55,000 --> 00:34:58,000
Si potrebbe pensare a come lo si dereferenziazione e quindi ottenere l'indirizzo,

456
00:34:58,000 --> 00:35:04,000
ma il compilatore sta per tradurlo a quello che avevamo prima in ogni caso, q.strings + testa.

457
00:35:04,000 --> 00:35:06,000
In entrambi i casi si vuole pensarci bene.

458
00:35:06,000 --> 00:35:11,000
>> E il numero di byte vogliamo copiare?

459
00:35:11,000 --> 00:35:15,000
[Studente] Capacità - testa.

460
00:35:15,000 --> 00:35:18,000
Capacità - testa.

461
00:35:18,000 --> 00:35:21,000
E poi si può sempre scrivere un esempio

462
00:35:21,000 --> 00:35:23,000
di capire se è vero.

463
00:35:23,000 --> 00:35:26,000
[Studente] Ha bisogno di essere diviso per 2 allora.

464
00:35:26,000 --> 00:35:30,000
Gia ', quindi credo che abbiamo potuto usare dimensioni.

465
00:35:30,000 --> 00:35:35,000
Abbiamo ancora dimensioni dell'essere-

466
00:35:35,000 --> 00:35:39,000
utilizzando dimensioni, abbiamo dimensioni pari a 4.

467
00:35:39,000 --> 00:35:42,000
La nostra dimensione è 4. La nostra testa è 1.

468
00:35:42,000 --> 00:35:46,000
Vogliamo copiare questi 3 elementi.

469
00:35:46,000 --> 00:35:54,000
Questo è il test di integrità che le dimensioni - testa è correttamente 3.

470
00:35:54,000 --> 00:35:58,000
E tornare qui, come abbiamo detto prima,

471
00:35:58,000 --> 00:36:00,000
se abbiamo usato la capacità, allora avremmo dovuto dividere per 2

472
00:36:00,000 --> 00:36:04,000
perché abbiamo già cresciuta la nostra capacità, così, invece, abbiamo intenzione di utilizzare dimensioni.

473
00:36:11,000 --> 00:36:13,000
Che le copie porzione.

474
00:36:13,000 --> 00:36:18,000
Ora, abbiamo bisogno di copiare l'altra parte, la parte che è a sinistra della partenza.

475
00:36:18,000 --> 00:36:28,000
>> Che sta per memmove in quale posizione?

476
00:36:28,000 --> 00:36:32,000
[Studente] Plus size - testa.

477
00:36:32,000 --> 00:36:38,000
Sì, per questo abbiamo già copiato in dimensioni - byte di testa,

478
00:36:38,000 --> 00:36:43,000
e così dove vogliamo copiare i byte rimanenti è nuovo

479
00:36:43,000 --> 00:36:48,000
e poi meno bene-formato, il numero di byte che abbiamo già copiato trovi

480
00:36:48,000 --> 00:36:52,000
E poi dove stiamo copiando?

481
00:36:52,000 --> 00:36:54,000
[Studente] Q.strings [0].

482
00:36:54,000 --> 00:36:56,000
[Rob B.] Sì, q.strings.

483
00:36:56,000 --> 00:37:02,000
Si potrebbe o fare e q.strings [0].

484
00:37:02,000 --> 00:37:05,000
Questo è molto meno comune di questo.

485
00:37:05,000 --> 00:37:14,000
Se è solo andare a essere 0, allora si tende a vedere q.strings.

486
00:37:14,000 --> 00:37:16,000
Ecco dove stiamo copiando da.

487
00:37:16,000 --> 00:37:18,000
Quanti byte ci hanno lasciato di copiare? >> [Studente] 10.

488
00:37:18,000 --> 00:37:20,000
Giusto.

489
00:37:20,000 --> 00:37:25,000
[Studente] Dobbiamo moltiplicare 5 - 10 volte la dimensione dei byte o qualcosa del genere?

490
00:37:25,000 --> 00:37:30,000
Gia ', quindi questo è dove-cosa esattamente stiamo copiando?

491
00:37:30,000 --> 00:37:32,000
[Studente] [incomprensibile]

492
00:37:32,000 --> 00:37:34,000
Qual è il tipo di cosa che stiamo copiando?

493
00:37:34,000 --> 00:37:36,000
[Studente] [incomprensibile]

494
00:37:36,000 --> 00:37:41,000
Gia ', in modo che il char * s che stiamo copiando, non sappiamo dove questi sono provenienti da.

495
00:37:41,000 --> 00:37:47,000
Beh, dove stanno indicando, come le corde, si finisce per spingerlo nella coda

496
00:37:47,000 --> 00:37:49,000
o Accodamento nella coda.

497
00:37:49,000 --> 00:37:51,000
Se quelli sono provenienti da, non abbiamo idea.

498
00:37:51,000 --> 00:37:56,000
Abbiamo solo bisogno di tenere traccia del char * s stessi.

499
00:37:56,000 --> 00:38:00,000
Non vogliamo copiare dimensioni - byte testa.

500
00:38:00,000 --> 00:38:03,000
Vogliamo copiare dimensioni - testa char * s,

501
00:38:03,000 --> 00:38:11,000
quindi stiamo andando a moltiplicare questo per sizeof (char *).

502
00:38:11,000 --> 00:38:17,000
Stesso qui, testa * sizeof (char *).

503
00:38:17,000 --> 00:38:24,000
>> [Studente] E [incomprensibile]?

504
00:38:24,000 --> 00:38:26,000
Questo qui?

505
00:38:26,000 --> 00:38:28,000
[Studente] No, al di sotto, la dimensione - testa.

506
00:38:28,000 --> 00:38:30,000
[Rob B.] Questo qui?

507
00:38:30,000 --> 00:38:32,000
Puntatore aritmetica.

508
00:38:32,000 --> 00:38:35,000
Come l'aritmetica dei puntatori è andare a lavorare è

509
00:38:35,000 --> 00:38:40,000
moltiplica automaticamente dalla dimensione del tipo che si sta trattando.

510
00:38:40,000 --> 00:38:46,000
Proprio come qui, nuovo + (dimensione - testa)

511
00:38:46,000 --> 00:38:56,000
è esattamente equivalente a & [size - testa] nuovo

512
00:38:56,000 --> 00:39:00,000
fino a quando ci aspettiamo che per funzionare correttamente,

513
00:39:00,000 --> 00:39:04,000
poiché, se abbiamo a che fare con una serie int, allora non vengono indicizzati da int-

514
00:39:04,000 --> 00:39:07,000
o se è di dimensioni di 5 e si desidera che il 4 ° elemento, poi indice nella

515
00:39:07,000 --> 00:39:10,000
int array [4].

516
00:39:10,000 --> 00:39:14,000
Tu non fare-[4] * dimensione di int.

517
00:39:14,000 --> 00:39:21,000
Che gestisce automaticamente, e questo caso

518
00:39:21,000 --> 00:39:29,000
è letteralmente equivalente, quindi la staffa sintassi

519
00:39:29,000 --> 00:39:34,000
è solo andare a essere convertiti in questo non appena si compila.

520
00:39:34,000 --> 00:39:38,000
Questo è qualcosa che è necessario stare attenti a che

521
00:39:38,000 --> 00:39:42,000
quando si aggiungono dimensioni - testa

522
00:39:42,000 --> 00:39:45,000
non si sta aggiungendo un byte.

523
00:39:45,000 --> 00:39:53,000
Stai aggiungendo un char *, che può essere uno byte o qualsiasi altra cosa.

524
00:39:53,000 --> 00:39:56,000
>> Altre domande?

525
00:39:56,000 --> 00:40:04,000
Ok, dequeue sarà più facile.

526
00:40:04,000 --> 00:40:11,000
Ti do un minuto per l'attuazione.

527
00:40:11,000 --> 00:40:18,000
Oh, e credo che questa è la stessa situazione in cui

528
00:40:18,000 --> 00:40:21,000
ciò che il caso enqueue, se siamo enqueuing null,

529
00:40:21,000 --> 00:40:24,000
forse si vuole gestire la cosa, forse non lo facciamo.

530
00:40:24,000 --> 00:40:27,000
Non lo farò più qui, ma come il nostro caso stack.

531
00:40:27,000 --> 00:40:34,000
Se accodare nullo, si potrebbe desiderare di non tenerne conto.

532
00:40:34,000 --> 00:40:40,000
Qualcuno ha qualche codice che posso tirare su?

533
00:40:40,000 --> 00:40:45,000
[Studente] Devo solo dequeue.

534
00:40:45,000 --> 00:40:56,000
La versione 2 è che, va bene.

535
00:40:56,000 --> 00:40:59,000
Vuoi spiegare?

536
00:40:59,000 --> 00:41:01,000
[Studente] In primo luogo, assicurarsi che non ci sia qualcosa nella coda

537
00:41:01,000 --> 00:41:07,000
e che la dimensione sta andando giù di 1.

538
00:41:07,000 --> 00:41:11,000
Hai bisogno di fare questo, e poi si torna alla testa

539
00:41:11,000 --> 00:41:13,000
e quindi spostare la testa 1.

540
00:41:13,000 --> 00:41:19,000
Ok, quindi non c'è un caso d'angolo dobbiamo considerare. Gia '.

541
00:41:19,000 --> 00:41:24,000
[Studente] Se la tua testa è l'ultimo elemento,

542
00:41:24,000 --> 00:41:26,000
allora non si vuole la testa al punto al di fuori della matrice.

543
00:41:26,000 --> 00:41:29,000
>> Gia ', quindi non appena testa colpisce il fine del nostro array,

544
00:41:29,000 --> 00:41:35,000
quando dequeue, la nostra testa deve essere modded a 0.

545
00:41:35,000 --> 00:41:40,000
Purtroppo, non possiamo farlo in un solo passaggio.

546
00:41:40,000 --> 00:41:44,000
Credo che il modo in cui probabilmente sarei risolvere il problema è

547
00:41:44,000 --> 00:41:52,000
questo sta andando essere un char *, quello che stiamo tornando,

548
00:41:52,000 --> 00:41:55,000
qualunque sia il tuo nome di variabile vuole essere.

549
00:41:55,000 --> 00:42:02,000
Poi vogliamo mod testa con la nostra capacità

550
00:42:02,000 --> 00:42:10,000
e poi tornare ret.

551
00:42:10,000 --> 00:42:14,000
Un sacco di gente qui si potrebbe fare-

552
00:42:14,000 --> 00:42:19,000
questo è il caso di e avrete modo di vedere le persone fare se la testa

553
00:42:19,000 --> 00:42:29,000
è superiore alla capacità, non testa - capacità.

554
00:42:29,000 --> 00:42:36,000
E questo è solo lavorando attorno a ciò che è mod.

555
00:42:36,000 --> 00:42:41,000
Capacità di testa mod = è molto più pulito

556
00:42:41,000 --> 00:42:51,000
di un involucro intorno a se la testa più grande di testa Capacità - capacità.

557
00:42:51,000 --> 00:42:56,000
>> Domande?

558
00:42:56,000 --> 00:43:02,000
Ok, l'ultima cosa che ci resta è la nostra lista concatenata.

559
00:43:02,000 --> 00:43:07,000
Potrebbe essere usato per alcuni comportamenti lista collegata se l'avete fatto

560
00:43:07,000 --> 00:43:11,000
liste collegate nelle tabelle hash, se avete fatto una tabella hash.

561
00:43:11,000 --> 00:43:15,000
Consiglio vivamente a fare una tabella di hash.

562
00:43:15,000 --> 00:43:17,000
Si potrebbe avere già fatto un trie,

563
00:43:17,000 --> 00:43:23,000
ma tentativi sono più difficili.

564
00:43:23,000 --> 00:43:27,000
In teoria, sono asintoticamente migliore.

565
00:43:27,000 --> 00:43:30,000
Ma basta guardare il tabellone,

566
00:43:30,000 --> 00:43:35,000
e cerca di non fare di meglio, e occupano più memoria.

567
00:43:35,000 --> 00:43:43,000
Tutto cerca sulla finisce per essere peggiore per più lavoro.

568
00:43:43,000 --> 00:43:49,000
E 'quello che la soluzione di David Malan è sempre

569
00:43:49,000 --> 00:43:56,000
E 'sempre la sua soluzione messaggi trie, e vediamo dove si trova attualmente.

570
00:43:56,000 --> 00:44:00,000
Quello che era sotto, David J?

571
00:44:00,000 --> 00:44:06,000
E '# 18, in modo che non è terribilmente male,

572
00:44:06,000 --> 00:44:09,000
e che sarà uno dei migliori prova si può pensare

573
00:44:09,000 --> 00:44:17,000
o uno dei migliori cerca di un trie.

574
00:44:17,000 --> 00:44:23,000
Non è forse anche la sua soluzione originale?

575
00:44:23,000 --> 00:44:29,000
Mi sento come soluzioni trie tendono ad essere più in questo range di utilizzo della RAM.

576
00:44:29,000 --> 00:44:33,000
>> Scendete fino alla cima, e utilizzo della RAM è in una sola cifra.

577
00:44:33,000 --> 00:44:36,000
Si scende verso il basso, e quindi si cerca di iniziare a vedere

578
00:44:36,000 --> 00:44:41,000
dove si ottiene l'utilizzo di RAM assolutamente enormi,

579
00:44:41,000 --> 00:44:45,000
e tentativi sono più difficili.

580
00:44:45,000 --> 00:44:53,000
Non del tutto, ma ne vale la pena un'esperienza educativa se l'avete fatto uno.

581
00:44:53,000 --> 00:44:56,000
L'ultima cosa è la nostra lista collegata,

582
00:44:56,000 --> 00:45:04,000
e queste tre cose, pile, code e liste concatenate,

583
00:45:04,000 --> 00:45:09,000
qualsiasi cosa futura che mai fare in informatica

584
00:45:09,000 --> 00:45:12,000
si suppone che si abbia familiarità con queste cose.

585
00:45:12,000 --> 00:45:19,000
Sono solo così fondamentale a tutto.

586
00:45:19,000 --> 00:45:25,000
>> Liste collegate, e qui abbiamo una lista concatenata semplice sarà la nostra implementazione.

587
00:45:25,000 --> 00:45:34,000
Cosa vuol dire semplicemente concatenata al contrario di doppio collegamento? Sì.

588
00:45:34,000 --> 00:45:37,000
[Studente] Essa sottolinea solo l'indicatore accanto piuttosto che i puntatori,

589
00:45:37,000 --> 00:45:39,000
come quello che lo precede e quello dopo.

590
00:45:39,000 --> 00:45:44,000
Si ', quindi in formato immagine, che cosa ho fatto?

591
00:45:44,000 --> 00:45:48,000
Ho due cose. Ho immagini e foto.

592
00:45:48,000 --> 00:45:51,000
In formato immagine, le nostre liste semplicemente concatenate,

593
00:45:51,000 --> 00:45:57,000
inevitabilmente, abbiamo una sorta di puntatore alla testa della nostra lista,

594
00:45:57,000 --> 00:46:02,000
e poi all'interno della nostra lista, dobbiamo solo puntatori,

595
00:46:02,000 --> 00:46:05,000
e forse questo punti a null.

596
00:46:05,000 --> 00:46:08,000
E 'intenzione di essere il vostro disegno tipico di una lista concatenata.

597
00:46:08,000 --> 00:46:14,000
Una lista doppiamente concatenata, è possibile tornare indietro.

598
00:46:14,000 --> 00:46:19,000
Se io ti do un nodo nella lista, allora si può necessariamente arrivare a

599
00:46:19,000 --> 00:46:23,000
qualsiasi altro nodo della lista, se si tratta di una lista doppiamente concatenata.

600
00:46:23,000 --> 00:46:27,000
Ma se si ottiene il terzo nodo della lista ed è una lista concatenata semplice,

601
00:46:27,000 --> 00:46:30,000
nessun modo si sta mai riusciti ad ottenere ai nodi prima e la seconda.

602
00:46:30,000 --> 00:46:34,000
E ci sono vantaggi e gli svantaggi, e uno più evidente

603
00:46:34,000 --> 00:46:42,000
vi occupano più dimensioni, e si deve tenere traccia di dove queste cose siano rivolte ora.

604
00:46:42,000 --> 00:46:49,000
Ma ci preoccupiamo soltanto concatenata.

605
00:46:49,000 --> 00:46:53,000
>> Un paio di cose che stiamo andando ad avere per l'attuazione.

606
00:46:53,000 --> 00:47:00,000
Il nodo typedef struct, int i: struct nodo * next; nodo.

607
00:47:00,000 --> 00:47:09,000
Questo typedef dovrebbe essere bruciato nelle vostre menti.

608
00:47:09,000 --> 00:47:14,000
Quiz 1 dovrebbe essere come dare un typedef di un nodo lista collegata,

609
00:47:14,000 --> 00:47:18,000
e si dovrebbe essere in grado di scarabocchiare subito che verso il basso

610
00:47:18,000 --> 00:47:22,000
senza nemmeno pensarci.

611
00:47:22,000 --> 00:47:27,000
Credo che un paio di domande, perché abbiamo bisogno di struct qui?

612
00:47:27,000 --> 00:47:32,000
Perché non possiamo dire * nodo?

613
00:47:32,000 --> 00:47:35,000
[Studente] [incomprensibile]

614
00:47:35,000 --> 00:47:38,000
Gia '.

615
00:47:38,000 --> 00:47:44,000
L'unica cosa che definisce un nodo come cosa

616
00:47:44,000 --> 00:47:47,000
è la stessa typedef.

617
00:47:47,000 --> 00:47:55,000
Ma a partire da questo punto, quando siamo un po 'di analisi attraverso questa definizione del nodo struct,

618
00:47:55,000 --> 00:48:01,000
non abbiamo ancora finito il nostro typedef ancora, quindi in quanto il typedef non ha finito,

619
00:48:01,000 --> 00:48:05,000
nodo non esiste.

620
00:48:05,000 --> 00:48:12,000
Ma struct nodo fa, e questo nodo qui,

621
00:48:12,000 --> 00:48:14,000
questo potrebbe anche essere chiamato qualsiasi altra cosa.

622
00:48:14,000 --> 00:48:16,000
Questo potrebbe essere chiamato n.

623
00:48:16,000 --> 00:48:19,000
Si potrebbe definire il nodo lista collegata.

624
00:48:19,000 --> 00:48:21,000
Si potrebbe definire nulla.

625
00:48:21,000 --> 00:48:26,000
Ma questo nodo struct deve essere chiamata la stessa cosa di questo nodo struct.

626
00:48:26,000 --> 00:48:29,000
Quello che tu chiami questo deve essere anche qui,

627
00:48:29,000 --> 00:48:32,000
e così che risponde anche al secondo punto della questione

628
00:48:32,000 --> 00:48:37,000
ed è per questo, un sacco di volte quando si vede le strutture e typedef di strutture,

629
00:48:37,000 --> 00:48:42,000
vedrete le strutture anonime in cui si vedrà solo typedef struct,

630
00:48:42,000 --> 00:48:47,000
attuazione di struct, dizionario, o qualsiasi altra cosa.

631
00:48:47,000 --> 00:48:51,000
>> Perché qui abbiamo bisogno di dire nodo?

632
00:48:51,000 --> 00:48:54,000
Perché non può essere una struttura anonima?

633
00:48:54,000 --> 00:48:56,000
E 'quasi la stessa risposta.

634
00:48:56,000 --> 00:48:58,000
[Studente] È necessario fare riferimento ad esso all'interno della struttura.

635
00:48:58,000 --> 00:49:04,000
Sì, all'interno della struttura, è necessario fare riferimento alla stessa struttura.

636
00:49:04,000 --> 00:49:10,000
Se non si danno la struttura un nome, se si tratta di una struttura anonima, non è possibile fare riferimento ad esso.

637
00:49:10,000 --> 00:49:17,000
E, ultimo ma non meno importante, questi devono essere tutti un po 'semplice,

638
00:49:17,000 --> 00:49:20,000
e dovrebbero aiutare a capire se si sta scrivendo questo in giù

639
00:49:20,000 --> 00:49:24,000
che si sta facendo qualcosa di sbagliato, se questo genere di cose non hanno senso.

640
00:49:24,000 --> 00:49:28,000
Ultimo ma non meno importante, perché questo deve essere il nodo struct *?

641
00:49:28,000 --> 00:49:34,000
Perché non può essere solo struct nodo successivo?

642
00:49:34,000 --> 00:49:37,000
[Studente] puntatore alla struttura successiva.

643
00:49:37,000 --> 00:49:39,000
Questo è inevitabilmente quello che vogliamo.

644
00:49:39,000 --> 00:49:42,000
Perché non potrebbe mai essere nodo struct prossimo?

645
00:49:42,000 --> 00:49:50,000
Perché deve essere struct nodo * prossimo? Gia '.

646
00:49:50,000 --> 00:49:53,000
[Studente] E 'come un ciclo infinito.

647
00:49:53,000 --> 00:49:55,000
Gia '.

648
00:49:55,000 --> 00:49:57,000
[Studente] Sarebbe tutto in uno.

649
00:49:57,000 --> 00:50:02,000
Si ', solo pensare a come avremmo fatto dimensioni o qualcosa del genere.

650
00:50:02,000 --> 00:50:08,000
Dimensioni di una struttura è fondamentalmente + o - qualche modello qui o là.

651
00:50:08,000 --> 00:50:15,000
E 'fondamentalmente sarà la somma delle dimensioni delle cose nella struttura.

652
00:50:15,000 --> 00:50:18,000
Questo qui, senza cambiare nulla, la dimensione sarà facile.

653
00:50:18,000 --> 00:50:24,000
Dimensione del nodo struct sarà dimensioni di grandezza i + del prossimo.

654
00:50:24,000 --> 00:50:27,000
Dimensioni i sta per essere 4. Dimensioni del prossimo sarà 4.

655
00:50:27,000 --> 00:50:30,000
Dimensione del nodo struct sarà 8.

656
00:50:30,000 --> 00:50:34,000
Se noi non abbiamo il *, pensando a sizeof,

657
00:50:34,000 --> 00:50:37,000
poi sizeof (i) sta per essere 4.

658
00:50:37,000 --> 00:50:43,000
Dimensione del nodo struct prossimo sarà dimensioni di i + tipo di struct nodo successivo

659
00:50:43,000 --> 00:50:46,000
Dimensioni + di + i dimensioni del nodo struct prossimo.

660
00:50:46,000 --> 00:50:55,000
Sarebbe una ricorsione infinita di nodi.

661
00:50:55,000 --> 00:51:00,000
Ecco perché è così che le cose devono essere.

662
00:51:00,000 --> 00:51:03,000
>> Ancora una volta, che sicuramente memorizzare,

663
00:51:03,000 --> 00:51:06,000
o almeno capire abbastanza che si può essere in grado di

664
00:51:06,000 --> 00:51:12,000
ragionare su quello che dovrebbe essere simile.

665
00:51:12,000 --> 00:51:14,000
Le cose che stiamo andando a voler implementare.

666
00:51:14,000 --> 00:51:18,000
Se la lunghezza della lista-

667
00:51:18,000 --> 00:51:21,000
si può imbrogliare e mantenere intorno a un

668
00:51:21,000 --> 00:51:24,000
lunghezza globale o qualcosa del genere, ma non abbiamo intenzione di farlo.

669
00:51:24,000 --> 00:51:28,000
Stiamo andando a contare la lunghezza della lista.

670
00:51:28,000 --> 00:51:34,000
Abbiamo contiene, così che è fondamentalmente come una ricerca,

671
00:51:34,000 --> 00:51:41,000
quindi abbiamo una lista concatenata di interi per vedere se questo intero è nella lista collegata.

672
00:51:41,000 --> 00:51:44,000
Prepend sta per inserire all'inizio della lista.

673
00:51:44,000 --> 00:51:46,000
Append sta per inserire alla fine.

674
00:51:46,000 --> 00:51:53,000
Insert_sorted sta per inserire nella posizione ordinati nell'elenco.

675
00:51:53,000 --> 00:52:01,000
Insert_sorted di tipo presuppone che non hai mai usato anteporre o aggiungere in modo cattivo.

676
00:52:01,000 --> 00:52:09,000
>> Insert_sorted quando si sta implementando insert_sorted-

677
00:52:09,000 --> 00:52:13,000
diciamo che abbiamo la nostra lista collegata.

678
00:52:13,000 --> 00:52:18,000
Questo è ciò che appare attualmente come, 2, 4, 5.

679
00:52:18,000 --> 00:52:24,000
Voglio inserire 3, quindi, purché la stessa lista è già ordinato,

680
00:52:24,000 --> 00:52:27,000
è facile trovare dove 3 appartiene.

681
00:52:27,000 --> 00:52:29,000
Comincio a 2.

682
00:52:29,000 --> 00:52:32,000
Ok, 3 è maggiore di 2, quindi voglio andare avanti.

683
00:52:32,000 --> 00:52:35,000
Oh, 4 è troppo grande, quindi so 3 è per andare tra 2 e 4,

684
00:52:35,000 --> 00:52:39,000
e devo sistemare puntatori e tutta quella roba.

685
00:52:39,000 --> 00:52:43,000
Ma se non utilizzare esclusivamente insert_sorted,

686
00:52:43,000 --> 00:52:50,000
come diciamo solo che antepongo 6,

687
00:52:50,000 --> 00:52:55,000
allora la mia lista concatenata sta per diventare tale.

688
00:52:55,000 --> 00:53:01,000
Si rende ora non ha senso, quindi per insert_sorted, si può solo supporre

689
00:53:01,000 --> 00:53:04,000
che l'elenco è ordinato, anche se le operazioni di esistere

690
00:53:04,000 --> 00:53:09,000
che può causare a non essere ordinati, e questo è tutto.

691
00:53:09,000 --> 00:53:20,000
Trova un utile inserto-so queste sono le cose principali che si sta andando ad avere per l'attuazione.

692
00:53:20,000 --> 00:53:24,000
>> Per ora, un minuto per fare lunghezza e contiene,

693
00:53:24,000 --> 00:53:30,000
e quelli dovrebbe essere relativamente veloce.

694
00:53:41,000 --> 00:53:48,000
Avvicinandosi orario di chiusura, in modo che chiunque ha niente per la lunghezza o contiene?

695
00:53:48,000 --> 00:53:50,000
Stanno per essere quasi identici.

696
00:53:50,000 --> 00:53:57,000
[Studente] Lunghezza.

697
00:53:57,000 --> 00:54:01,000
Vediamo, revisione.

698
00:54:01,000 --> 00:54:04,000
Va bene.

699
00:54:12,000 --> 00:54:15,000
Vuoi spiegare?

700
00:54:15,000 --> 00:54:21,000
[Studente] Ho appena creato un nodo puntatore e inizializzarla al primo, che è la nostra variabile globale,

701
00:54:21,000 --> 00:54:27,000
e poi controllare per vedere se è nullo, quindi non si ottiene un errore di segmento e restituire 0 se questo è il caso.

702
00:54:27,000 --> 00:54:34,000
In caso contrario, io loop through, tenendo traccia di dentro intero

703
00:54:34,000 --> 00:54:38,000
quante volte ho l'accesso al successivo elemento della lista

704
00:54:38,000 --> 00:54:43,000
e nella stessa operazione di incremento anche accedere all'elemento reale,

705
00:54:43,000 --> 00:54:47,000
e poi ho sempre fare il controllo per vedere se è nullo,

706
00:54:47,000 --> 00:54:56,000
e se è nullo, poi interrompe e restituisce il numero di elementi che ho accesso.

707
00:54:56,000 --> 00:55:01,000
>> [Rob B.] Qualcuno ha qualche commento su qualcosa?

708
00:55:01,000 --> 00:55:06,000
Questo sembra correttezza bene saggio.

709
00:55:06,000 --> 00:55:10,000
[Studente] Non credo che ti serve il nodo == null.

710
00:55:10,000 --> 00:55:13,000
Si ', per cui se il nodo == 0 ritorno null.

711
00:55:13,000 --> 00:55:18,000
Ma se il nodo == null allora questo-oh, c'è un problema di correttezza.

712
00:55:18,000 --> 00:55:23,000
Era solo sei i ritorno, ma non è portata in questo momento.

713
00:55:23,000 --> 00:55:30,000
Hai solo bisogno di int i, in modo da i = 0.

714
00:55:30,000 --> 00:55:34,000
Ma se il nodo è nullo, allora i è ancora in corso di essere 0,

715
00:55:34,000 --> 00:55:39,000
e abbiamo intenzione di restituire 0, quindi questo caso è identico.

716
00:55:39,000 --> 00:55:48,000
Un'altra cosa comune è quello di ottenere la dichiarazione

717
00:55:48,000 --> 00:55:51,000
all'interno del nodo del ciclo for.

718
00:55:51,000 --> 00:55:54,000
Si potrebbe dire-oh, no.

719
00:55:54,000 --> 00:55:56,000
Teniamo come questo.

720
00:55:56,000 --> 00:55:59,000
Io probabilmente messo int i = 0 qui,

721
00:55:59,000 --> 00:56:05,000
quindi il nodo * nodo = prima qui.

722
00:56:05,000 --> 00:56:11,000
E questo è probabilmente il modo-sbarazzarsi di questo ora.

723
00:56:11,000 --> 00:56:14,000
Questo è probabilmente il modo avrei scritto.

724
00:56:14,000 --> 00:56:21,000
Si potrebbe anche, guardando in questo modo.

725
00:56:21,000 --> 00:56:25,000
Questo per struttura ad anello qui

726
00:56:25,000 --> 00:56:30,000
dovrebbe essere quasi naturale per voi come per int i = 0

727
00:56:30,000 --> 00:56:33,000
i è minore lunghezza di array i + +.

728
00:56:33,000 --> 00:56:38,000
Se questo è il modo di eseguire iterazioni su un array, questo è il modo per scorrere una lista concatenata.

729
00:56:38,000 --> 00:56:45,000
>> Questo dovrebbe essere una seconda natura ad un certo punto.

730
00:56:45,000 --> 00:56:50,000
Con questo in mente, questa sarà quasi la stessa cosa.

731
00:56:50,000 --> 00:56:57,000
Stai andando a voler scorrere una lista concatenata.

732
00:56:57,000 --> 00:57:02,000
Se il nodo-non ho idea di quale sia il valore viene chiamato.

733
00:57:02,000 --> 00:57:04,000
Nodo i.

734
00:57:04,000 --> 00:57:15,000
Se il valore in quel nodo = i return true, e questo è tutto.

735
00:57:15,000 --> 00:57:18,000
Si noti che l'unico modo che abbiamo mai restituire false

736
00:57:18,000 --> 00:57:23,000
è se scorrere l'intera lista collegata e non tornare mai più vero,

737
00:57:23,000 --> 00:57:29,000
ed è quello che fa questo.

738
00:57:29,000 --> 00:57:36,000
Come nota a margine, probabilmente non si arriva a aggiungere o anteporre.

739
00:57:36,000 --> 00:57:39,000
>> Rapido ultima nota.

740
00:57:39,000 --> 00:57:52,000
Se si vede la parola chiave static, quindi diciamo static int count = 0,

741
00:57:52,000 --> 00:57:56,000
poi contano + +, si può sostanzialmente pensare ad esso come una variabile globale,

742
00:57:56,000 --> 00:58:00,000
anche se ho appena detto non è così che stiamo andando a implementare lunghezza.

743
00:58:00,000 --> 00:58:06,000
Lo sto facendo qui, e poi contare + +.

744
00:58:06,000 --> 00:58:11,000
In ogni modo siamo in grado di entrare in un nodo nella nostra lista collegata stiamo incrementando il nostro conteggio.

745
00:58:11,000 --> 00:58:15,000
Il punto di questo è ciò che significa la parola chiave static.

746
00:58:15,000 --> 00:58:20,000
Se ho appena avuto int count = 0 che sarebbe un normale vecchia variabile globale.

747
00:58:20,000 --> 00:58:25,000
Nei mezzi static int conta è che è una variabile globale per questo file.

748
00:58:25,000 --> 00:58:28,000
E 'impossibile per un altro file,

749
00:58:28,000 --> 00:58:34,000
piace pensare di pset 5, se avete iniziato.

750
00:58:34,000 --> 00:58:39,000
Avete entrambi speller.c, e si dispone di dictionary.c,

751
00:58:39,000 --> 00:58:42,000
e se si dichiara una cosa globale, allora qualcosa in speller.c

752
00:58:42,000 --> 00:58:45,000
si può accedere in dictionary.c e viceversa.

753
00:58:45,000 --> 00:58:48,000
Le variabili globali sono accessibili da qualsiasi file. C,

754
00:58:48,000 --> 00:58:54,000
ma le variabili statiche sono accessibili solo all'interno del file stesso,

755
00:58:54,000 --> 00:59:01,000
così all'interno del correttore ortografico o all'interno di dictionary.c,

756
00:59:01,000 --> 00:59:06,000
questo è una specie di come mi avrebbe dichiarato la mia variabile per la dimensione della mia matrice

757
00:59:06,000 --> 00:59:10,000
o le dimensioni del mio numero di parole nel dizionario.

758
00:59:10,000 --> 00:59:15,000
Dal momento che non desidera dichiarare una variabile globale che chiunque abbia accesso a,

759
00:59:15,000 --> 00:59:18,000
Mi interessa solo per i miei scopi.

760
00:59:18,000 --> 00:59:21,000
>> La cosa buona di questo è anche tutto il materiale conflitto di nomi.

761
00:59:21,000 --> 00:59:27,000
Se qualche altro file tenta di utilizzare una variabile globale chiamata conte, le cose vanno molto, molto male,

762
00:59:27,000 --> 00:59:33,000
quindi questo mantiene bene le cose al sicuro, e solo vi si possa accedere,

763
00:59:33,000 --> 00:59:38,000
e nessun altro può, e se qualcun altro dichiara una variabile globale chiamata conteggio,

764
00:59:38,000 --> 00:59:43,000
allora non interferirà con la variabile statica denominata conteggio.

765
00:59:43,000 --> 00:59:47,000
Questo è ciò che è statico. Si tratta di una variabile file globale.

766
00:59:47,000 --> 00:59:52,000
>> Domande su qualsiasi cosa?

767
00:59:52,000 --> 00:59:59,000
Tutto pronto. Bye.

768
00:59:59,000 --> 01:00:03,000
[CS50.TV]