1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Sezione 6: meno confortevole]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Questo è CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Bene. Benvenuti alla sezione 6.

5
00:00:11,840 --> 00:00:14,690
Questa settimana, abbiamo intenzione di parlare di strutture di dati in sezione,

6
00:00:14,690 --> 00:00:19,780
in primo luogo perché il problema di questa settimana impostato spellr

7
00:00:19,780 --> 00:00:24,410
fa un sacco di diversa struttura di esplorazione dei dati.

8
00:00:24,410 --> 00:00:26,520
Ci sono un sacco di modi diversi si può andare con il problema proposto,

9
00:00:26,520 --> 00:00:31,570
e le strutture di dati più si conoscono, le cose più interessanti che si possono fare.

10
00:00:31,570 --> 00:00:34,990
>> Quindi cerchiamo di iniziare. Per prima cosa andremo a parlare di pile,

11
00:00:34,990 --> 00:00:37,530
le strutture di dati di stack e code che stiamo andando a parlare.

12
00:00:37,530 --> 00:00:40,560
Le pile e le code sono molto utili quando si comincia a parlare di grafici,

13
00:00:40,560 --> 00:00:44,390
che non avete intenzione di fare così tanto in questo momento.

14
00:00:44,390 --> 00:00:52,820
Ma sono veramente buono per capire una delle grandi strutture fondamentali dati di CS.

15
00:00:52,820 --> 00:00:54,880
La descrizione nel disciplinare set problema,

16
00:00:54,880 --> 00:00:59,260
se si tira su, parla di stack come affine alla

17
00:00:59,260 --> 00:01:05,239
la pila di vassoi da pranzo che hai in mensa alle sale da pranzo

18
00:01:05,239 --> 00:01:09,680
dove quando il personale di sala viene e mette i vassoi da pranzo dopo li hanno puliti,

19
00:01:09,680 --> 00:01:12,000
li impilare uno sopra l'altro.

20
00:01:12,000 --> 00:01:15,050
E poi, quando i bambini vengono a procurarsi il cibo,

21
00:01:15,050 --> 00:01:19,490
tirano fuori i vassoi, prima quella superiore, quindi quello sottostante, quindi quello qui sotto che.

22
00:01:19,490 --> 00:01:25,190
Così, in effetti, il primo vassoio che il personale di sala è messo giù l'ultimo che viene tolto.

23
00:01:25,190 --> 00:01:32,330
L'ultimo che il personale di sala messo su è il primo che viene tolto per la cena.

24
00:01:32,330 --> 00:01:38,100
In spec il problema proposto, che è possibile scaricare se non l'hai già fatto,

25
00:01:38,100 --> 00:01:46,730
si parla di modellazione di un stucture dati stack utilizzando questo tipo di struttura.

26
00:01:46,730 --> 00:01:51,070
>> Allora, cosa abbiamo qui, questo è simile a quello che è stato presentato in conferenza,

27
00:01:51,070 --> 00:01:58,120
tranne in conferenza abbiamo presentato questo con int al contrario di char * s.

28
00:01:58,120 --> 00:02:06,250
Questo sarà uno stack che memorizza cosa?

29
00:02:06,250 --> 00:02:09,009
Daniel? Che cosa stiamo memorizzare in questo stack?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? Siamo >> memorizzare stringhe in questo stack, esattamente.

31
00:02:15,260 --> 00:02:20,950
Tutto quello che devi avere per creare uno stack è un array

32
00:02:20,950 --> 00:02:23,920
di una capacità particolare, che in questo caso,

33
00:02:23,920 --> 00:02:28,020
capacità sta per essere tutto maiuscolo perché è una costante.

34
00:02:28,020 --> 00:02:36,340
E poi in aggiunta alla matrice, tutti dobbiamo tracciare è la dimensione corrente dell'array.

35
00:02:36,340 --> 00:02:38,980
Una cosa da notare qui che è genere di freddo

36
00:02:38,980 --> 00:02:47,060
è che stiamo creando la struttura dati impilati uno sopra un'altra struttura dati, l'array.

37
00:02:47,060 --> 00:02:50,110
Ci sono diversi modi per implementare stack.

38
00:02:50,110 --> 00:02:54,250
Noi non lo faremo ancora del tutto, ma si spera che dopo aver fatto le liste collegate problemi,

39
00:02:54,250 --> 00:03:00,520
vedrai come si può facilmente implementare una pila in cima a una lista collegata pure.

40
00:03:00,520 --> 00:03:02,640
Ma per ora, faremo riferimento agli array.

41
00:03:02,640 --> 00:03:06,350
Così ancora una volta, tutto ciò che serve è una matrice e abbiamo solo bisogno di monitorare le dimensioni della matrice.

42
00:03:06,350 --> 00:03:09,850
[Sam] Ci dispiace, perché è che hai detto che il pacco è in cima delle corde?

43
00:03:09,850 --> 00:03:13,440
A me sembra che le corde sono all'interno della pila.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Si '. Stiamo creando, stiamo prendendo la nostra struttura a matrice di dati -

45
00:03:16,790 --> 00:03:22,130
questa è una bella domanda. Quindi la domanda è: perché, per le persone che stanno guardando on-line,

46
00:03:22,130 --> 00:03:24,140
perché stiamo dicendo che la pila è in cima delle corde,

47
00:03:24,140 --> 00:03:27,990
perché qui sembra che le corde sono dentro lo stack?

48
00:03:27,990 --> 00:03:31,050
Il che è del tutto così.

49
00:03:31,050 --> 00:03:34,660
Quello che mi riferivo al fatto che abbiamo una struttura dati array.

50
00:03:34,660 --> 00:03:39,290
Abbiamo un array di char * s, questo array di stringhe,

51
00:03:39,290 --> 00:03:45,300
e stiamo per aggiungere che per creare la struttura dati impilati.

52
00:03:45,300 --> 00:03:48,620
>> Così una pila è leggermente più complessa di una matrice.

53
00:03:48,620 --> 00:03:51,890
Siamo in grado di utilizzare un array per creare uno stack.

54
00:03:51,890 --> 00:03:55,810
Ecco dove si dice che la pila si basa su di un array.

55
00:03:55,810 --> 00:04:02,510
Allo stesso modo, come ho detto prima, siamo in grado di costruire una pila in cima ad una lista concatenata.

56
00:04:02,510 --> 00:04:04,960
Invece di utilizzare un array per contenere i nostri elementi,

57
00:04:04,960 --> 00:04:10,070
potremmo usare una lista concatenata di tenere i nostri elementi e costruire lo stack intorno a quello.

58
00:04:10,070 --> 00:04:12,420
Esaminiamo un paio di esempi, guardando un po 'di codice,

59
00:04:12,420 --> 00:04:14,960
per vedere quello che succede qui.

60
00:04:14,960 --> 00:04:23,400
A sinistra, ho buttato giù quello che struct pila sarà simile in memoria

61
00:04:23,400 --> 00:04:28,330
se la capacità sono stati # definito per essere quattro.

62
00:04:28,330 --> 00:04:33,490
Abbiamo ottenuto il nostro quattro elemento di matrice char *.

63
00:04:33,490 --> 00:04:38,110
Abbiamo strings [0], strings [1], le stringhe [2], strings [3],

64
00:04:38,110 --> 00:04:43,800
e poi che lo spazio per il nostro ultimo numero intero formato.

65
00:04:43,800 --> 00:04:46,270
Questo ha senso? Va bene.

66
00:04:46,270 --> 00:04:48,790
Questo è ciò che succede se quello che faccio sulla destra,

67
00:04:48,790 --> 00:04:55,790
che sarà il mio codice, è quello di dichiarare solo una struttura, una struttura impilata chiamato s.

68
00:04:55,790 --> 00:05:01,270
Questo è ciò che si ottiene. Essa stabilisce la presenza in memoria.

69
00:05:01,270 --> 00:05:05,590
La prima domanda: ecco quali sono i contenuti di questa struct stack?

70
00:05:05,590 --> 00:05:09,250
In questo momento non sono niente, ma non sono del tutto nulla.

71
00:05:09,250 --> 00:05:13,300
Sono questo tipo di rifiuti. Non abbiamo idea di ciò che è in loro.

72
00:05:13,300 --> 00:05:17,000
Quando dichiariamo s pila, stiamo solo buttando giu 'sulla parte superiore della memoria.

73
00:05:17,000 --> 00:05:19,840
E 'un po' come dichiarare int i e non è l'inizializzazione.

74
00:05:19,840 --> 00:05:21,730
Tu non sai cosa c'è dentro. È possibile leggere cosa c'è dentro,

75
00:05:21,730 --> 00:05:27,690
ma potrebbe non essere super disponibile.

76
00:05:27,690 --> 00:05:32,680
Una cosa che si vuole ricordare sempre di fare è inizializzare ciò che deve essere inizializzato.

77
00:05:32,680 --> 00:05:35,820
In questo caso, andremo a inizializzare la dimensione pari a zero,

78
00:05:35,820 --> 00:05:39,960
perché sta per rivelarsi molto importante per noi.

79
00:05:39,960 --> 00:05:43,450
Potremmo andare avanti e inizializzare tutti i puntatori, tutti i char * s,

80
00:05:43,450 --> 00:05:49,670
essere un valore comprensibile, probabilmente nullo.

81
00:05:49,670 --> 00:05:58,270
Ma non è del tutto necessario che lo facciamo.

82
00:05:58,270 --> 00:06:04,200
>> Ora, i due principali operazioni su stack sono?

83
00:06:04,200 --> 00:06:07,610
Chiunque ricordi di lezione ciò che si fa con le pile? Sì?

84
00:06:07,610 --> 00:06:09,700
[Stella] e spinta popping? >> Esattamente.

85
00:06:09,700 --> 00:06:13,810
Spingendo e pop sono i due principali operazioni su stack.

86
00:06:13,810 --> 00:06:17,060
E che cosa fare pressione? >> Si mette qualcosa sulla parte superiore

87
00:06:17,060 --> 00:06:19,300
della pila, e quindi popping decolla.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Esattamente. Così spinge spinge qualcosa in cima alla pila.

89
00:06:23,150 --> 00:06:27,700
E 'come il personale di sala da pranzo di mettere un vassoio sul bancone.

90
00:06:27,700 --> 00:06:33,630
E popping sta prendendo un vassoio da pranzo dallo stack.

91
00:06:33,630 --> 00:06:36,460
Camminiamo attraverso un paio di esempi di ciò che accade

92
00:06:36,460 --> 00:06:39,720
quando spingere le cose nello stack.

93
00:06:39,720 --> 00:06:45,110
Se dovessimo spingere la stringa 'ciao' sul nostro stack,

94
00:06:45,110 --> 00:06:49,760
questo è ciò che il nostro diagramma assomiglierà a ora.

95
00:06:49,760 --> 00:06:53,410
Vedi cosa succede?

96
00:06:53,410 --> 00:06:56,530
Abbiamo spinto nel primo elemento della nostra matrice stringhe

97
00:06:56,530 --> 00:07:01,420
e abbiamo aumentato il nostro numero di dimensioni a 1.

98
00:07:01,420 --> 00:07:05,340
Quindi, se guardiamo la differenza tra le due slitte, qui era 0, ecco prima della spinta.

99
00:07:05,340 --> 00:07:08,690
Ecco dopo la spinta.

100
00:07:08,690 --> 00:07:13,460
Prima della spinta, dopo la spinta.

101
00:07:13,460 --> 00:07:16,860
E ora abbiamo un elemento del nostro stack.

102
00:07:16,860 --> 00:07:20,970
E 'la stringa "ciao", e questo è tutto.

103
00:07:20,970 --> 00:07:24,440
Tutto il resto nella matrice, nella nostra matrice stringhe, è ancora spazzatura.

104
00:07:24,440 --> 00:07:27,070
Non lo abbiamo inizializzato.

105
00:07:27,070 --> 00:07:29,410
Diciamo che spingere un'altra stringa sul nostro stack.

106
00:07:29,410 --> 00:07:32,210
Stiamo andando a spingere "mondo" in questo momento.

107
00:07:32,210 --> 00:07:35,160
Così si può vedere "mondo" va qui sopra "ciao",

108
00:07:35,160 --> 00:07:40,040
e il conteggio dimensione va fino a 2.

109
00:07:40,040 --> 00:07:44,520
Ora siamo in grado di spingere "CS50", e che andrò di nuovo in cima.

110
00:07:44,520 --> 00:07:51,110
Se torniamo indietro, si può vedere come stiamo spingendo le cose in cima alla pila.

111
00:07:51,110 --> 00:07:53,320
Ed ora arriviamo al pop.

112
00:07:53,320 --> 00:07:58,910
Quando abbiamo spuntata qualcosa fuori della pila, cosa è successo?

113
00:07:58,910 --> 00:08:01,540
Chiunque vedere la differenza? E 'abbastanza sottile.

114
00:08:01,540 --> 00:08:05,810
[Studente] La dimensione. >> Si ', la dimensione modificata.

115
00:08:05,810 --> 00:08:09,040
>> Che altro avresti dovrebbe cambiare?

116
00:08:09,040 --> 00:08:14,280
[Studente] Le corde, anche. >> Destra. Le stringhe troppo.

117
00:08:14,280 --> 00:08:17,110
Si scopre che quando si sta facendo in questo modo,

118
00:08:17,110 --> 00:08:21,960
perché non stiamo copiando gli elementi in nostro stack,

119
00:08:21,960 --> 00:08:24,670
in realtà non c'è bisogno di fare niente, possiamo semplicemente utilizzare la dimensione

120
00:08:24,670 --> 00:08:28,630
per tenere traccia del numero di cose nella nostra matrice

121
00:08:28,630 --> 00:08:33,780
in modo che quando abbiamo pop di nuovo, ancora una volta abbiamo appena diminuire la nostra dimensione fino a 1.

122
00:08:33,780 --> 00:08:39,440
Non c'è bisogno di andare effettivamente in e sovrascrivere qualsiasi cosa.

123
00:08:39,440 --> 00:08:41,710
Tipo di funky.

124
00:08:41,710 --> 00:08:46,520
Si scopre che di solito lasciare le cose solo perché è meno lavoro da fare per noi.

125
00:08:46,520 --> 00:08:50,060
Se non c'è bisogno di andare indietro e sovrascrivere qualcosa, allora perché farlo?

126
00:08:50,060 --> 00:08:54,150
Così, quando abbiamo pop doppio dello stack, tutto ciò che fa è diminuire la dimensione di un paio di volte.

127
00:08:54,150 --> 00:08:59,120
E ancora, è solo perché non stiamo copiando le cose nel nostro stack.

128
00:08:59,120 --> 00:09:01,320
Sì? Vai avanti.

129
00:09:01,320 --> 00:09:04,460
[Studente, incomprensibile] >> E poi, cosa succede quando si preme di nuovo qualcosa?

130
00:09:04,460 --> 00:09:08,570
Quando si preme di nuovo qualcosa, dove va a finire?

131
00:09:08,570 --> 00:09:12,390
Dove va a finire, Basil? In stringhe >> [1]? >> Destra.

132
00:09:12,390 --> 00:09:14,530
Perché non andare in strings [3]?

133
00:09:14,530 --> 00:09:19,410
[Basilio] Perché dimenticato che ci fosse qualcosa nelle stringhe [1] e [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Esattamente. La pila, in sostanza, "dimenticato" che si teneva a niente

135
00:09:24,040 --> 00:09:29,480
nelle stringhe [1] o strings [2], in modo che quando spingiamo "Woot",

136
00:09:29,480 --> 00:09:36,670
mette solo che in l'elemento in strings [1].

137
00:09:36,670 --> 00:09:41,590
Ci sono domande su come funziona, a livello di base?

138
00:09:41,590 --> 00:09:45,160
[Sam] Quindi questo non è in alcun modo dinamico, in termini di quantità

139
00:09:45,160 --> 00:09:47,620
o in termini di dimensioni della pila?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Esattamente. Questo è - il punto era che non si trattava di una pila in modo dinamico growning.

141
00:09:56,750 --> 00:10:02,850
Questa è una pila che può contenere al massimo quattro char * s, al massimo quattro cose.

142
00:10:02,850 --> 00:10:07,580
Se dovessimo cercare di spingere una quinta cosa, cosa pensi dovrebbe accadere?

143
00:10:07,580 --> 00:10:11,870
[Gli studenti, incomprensibili]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Esattamente. Ci sono una serie di cose che potrebbero accadere.

145
00:10:14,600 --> 00:10:19,330
Si potrebbe forse errore di segmentazione, a seconda di quello che siamo stati -

146
00:10:19,330 --> 00:10:22,530
esattamente come siamo stati di applicazione back-end.

147
00:10:22,530 --> 00:10:31,740
Si potrebbe sovrascrivere. Si potrebbe avere quel buffer overflow di cui abbiamo parlato in classe.

148
00:10:31,740 --> 00:10:35,240
Quale sarebbe la cosa più ovvia che potrebbe essere sovrascritto

149
00:10:35,240 --> 00:10:42,370
se abbiamo cercato di spingere una cosa in più sul nostro stack?

150
00:10:42,370 --> 00:10:44,550
Quindi, lei ha citato un buffer overflow.

151
00:10:44,550 --> 00:10:47,870
Quale potrebbe essere la cosa che otterrebbe scritto sopra o calpestato

152
00:10:47,870 --> 00:10:52,320
se traboccava accidentalmente cercando di spingere una cosa in più?

153
00:10:52,320 --> 00:10:54,730
[Daniele, incomprensibile] Possibile >>.

154
00:10:54,730 --> 00:10:58,440
Ma inizialmente, cosa potrebbe succedere? Che cosa succede se abbiamo cercato di spingere una quarta cosa?

155
00:10:58,440 --> 00:11:06,220
Si potrebbe sovrascrivere le dimensioni, almeno con questo schema di memoria che abbiamo.

156
00:11:06,220 --> 00:11:10,880
>> Nella definizione di un set problema, che è quello che sta andando ad essere oggi di attuazione,

157
00:11:10,880 --> 00:11:16,030
quello che si vuole fare è solo restituire false.

158
00:11:16,030 --> 00:11:20,030
Il nostro metodo push sta per restituire un valore booleano,

159
00:11:20,030 --> 00:11:22,920
e che il valore booleano è vero se la spinta riesce

160
00:11:22,920 --> 00:11:29,730
e false se non può spingere più niente perché lo stack è pieno.

161
00:11:29,730 --> 00:11:33,620
Esaminiamo un po 'di quel codice al momento.

162
00:11:33,620 --> 00:11:36,400
Ecco la nostra funzione push.

163
00:11:36,400 --> 00:11:40,380
La nostra funzione push per una pila sta andando a prendere nella stringa di mettere in pila.

164
00:11:40,380 --> 00:11:45,820
E 'intenzione di restituire true se la stringa è stata spinta con successo

165
00:11:45,820 --> 00:11:51,820
in caso contrario stack e false.

166
00:11:51,820 --> 00:11:59,740
Qualche suggerimento su quello che potrebbe essere una cosa buona prima a fare qui?

167
00:11:59,740 --> 00:12:20,630
[Sam] Se la dimensione è uguale capacità per poi tornare falso?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Bel lavoro.

169
00:12:23,320 --> 00:12:26,310
Se la dimensione è la capacità, che andremo a restituire false.

170
00:12:26,310 --> 00:12:29,270
Non si può mettere qualcosa di più nel nostro stack.

171
00:12:29,270 --> 00:12:36,900
In caso contrario, si vuole mettere qualcosa in cima alla pila.

172
00:12:36,900 --> 00:12:41,670
Che cosa è "la parte superiore della pila," inizialmente?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Dimensione 0? Dimensioni >> 0.

174
00:12:43,650 --> 00:12:49,990
Qual è la parte superiore della pila dopo c'è una cosa che nella pila? Missy, lo sai?

175
00:12:49,990 --> 00:12:52,720
[Missy] One. Dimensioni >> è uno, esattamente. È continuare ad aggiungere alle dimensioni,

176
00:12:52,720 --> 00:13:01,690
e ogni volta che avete deciso di mettere nel nuovo elemento con le dimensioni di indice nella matrice.

177
00:13:01,690 --> 00:13:05,470
Possiamo farlo con quel tipo di one-liner, se questo ha un senso.

178
00:13:05,470 --> 00:13:11,910
Così abbiamo la nostra matrice stringhe, stiamo per accedere all'indice dimensioni,

179
00:13:11,910 --> 00:13:14,780
e stiamo solo andando a conservare il nostro char * in là.

180
00:13:14,780 --> 00:13:19,340
Si noti come non ci sia la copia stringa succedendo qui,

181
00:13:19,340 --> 00:13:29,680
non allocazione dinamica della memoria?

182
00:13:29,680 --> 00:13:34,440
E poi Missy ha portato a ciò che ora abbiamo a che fare,

183
00:13:34,440 --> 00:13:40,570
perché abbiamo memorizzato la stringa nell'apposito spazio nella matrice,

184
00:13:40,570 --> 00:13:49,230
e lei ha detto che abbiamo dovuto incrementare le dimensioni di uno in modo che siamo pronti per la spinta successiva.

185
00:13:49,230 --> 00:13:53,950
Così possiamo farlo con s.size + +.

186
00:13:53,950 --> 00:13:59,330
A questo punto, ci siamo spinti nel nostro array. Qual è l'ultima cosa che dobbiamo fare?

187
00:13:59,330 --> 00:14:10,110
[Studente] Restituisce vero. Restituisce vero >>.

188
00:14:10,110 --> 00:14:14,690
Quindi è abbastanza semplice, un codice molto semplice. Non troppo.

189
00:14:14,690 --> 00:14:17,070
Dopo aver avvolto la testa intorno come lo stack funziona,

190
00:14:17,070 --> 00:14:21,910
questo è abbastanza semplice da implementare.

191
00:14:21,910 --> 00:14:26,390
>> Ora, la parte successiva di questo è popping una stringa dallo stack.

192
00:14:26,390 --> 00:14:29,410
Ho intenzione di dare voi ragazzi un po 'di tempo per lavorare su questo un po'.

193
00:14:29,410 --> 00:14:34,320
E 'quasi essenzialmente l'opposto di quello che abbiamo fatto qui in push.

194
00:14:34,320 --> 00:14:38,510
Quello che ho fatto è in realtà - oops.

195
00:14:38,510 --> 00:14:48,160
Ho avviato un apparecchio qui, e l'apparecchio,

196
00:14:48,160 --> 00:14:53,600
Ho tirato su il problema set 5 specifica.

197
00:14:53,600 --> 00:15:02,560
Se lo zoom qui, possiamo vedere sono a cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Avete voi scaricato il codice che si trova qui, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Bene. Se non lo avete fatto, fate che in questo momento, molto velocemente.

200
00:15:15,030 --> 00:15:22,130
Lo farò nella mia finestra di terminale.

201
00:15:22,130 --> 00:15:25,090
Io in realtà lo ha fatto qui. Gia '.

202
00:15:25,090 --> 00:15:34,730
Sì, Sam? >> Ho una domanda sul perché hai detto tra parentesi s.string 's di dimensione = str?

203
00:15:34,730 --> 00:15:42,910
Che cosa è str? È definita da qualche parte, o - oh, in str * char?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Sì, esattamente. Questo è stato l'argomento. >> Oh, va bene. Scusi.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Stiamo specificare la stringa di spingere trovi

206
00:15:49,470 --> 00:15:55,220
L'altra domanda che potrebbe venire che non abbiamo davvero parlare di qui era

207
00:15:55,220 --> 00:15:58,810
abbiamo preso per scontato che abbiamo avuto questa variabile chiamata s

208
00:15:58,810 --> 00:16:02,710
che era in campo di applicazione e accessibile a noi.

209
00:16:02,710 --> 00:16:06,960
Abbiamo preso per scontato che s era questo struct stack.

210
00:16:06,960 --> 00:16:08,930
Quindi, guardando indietro a questo codice spinta,

211
00:16:08,930 --> 00:16:13,450
si può vedere che stiamo facendo qualcosa con questa stringa ha passato in

212
00:16:13,450 --> 00:16:19,210
ma poi tutto ad un tratto, stiamo accedendo s.size, come, da dove s viene?

213
00:16:19,210 --> 00:16:23,020
Nel codice che stiamo andando a guardare in archivio sezione

214
00:16:23,020 --> 00:16:27,100
e poi la roba che vi ritroverete a fare nel tuo problema imposta,

215
00:16:27,100 --> 00:16:32,440
abbiamo fatto il nostro stack struct una variabile globale

216
00:16:32,440 --> 00:16:36,380
in modo da poter avere accesso ad esso in tutte le nostre diverse funzioni

217
00:16:36,380 --> 00:16:40,630
senza dover manualmente passare intorno e passarlo per riferimento,

218
00:16:40,630 --> 00:16:44,870
fare tutto questo genere di cose ad esso.

219
00:16:44,870 --> 00:16:52,280
Stiamo solo barando un po ', se si vuole, per rendere le cose più bello.

220
00:16:52,280 --> 00:16:57,430
E questo è qualcosa che stiamo facendo qui perché è per divertimento, è più facile.

221
00:16:57,430 --> 00:17:02,800
Spesso, vedrete persone lo fanno, se ne hanno uno grande struttura di dati

222
00:17:02,800 --> 00:17:07,750
che è in corso di gestione all'interno del loro programma.

223
00:17:07,750 --> 00:17:09,560
>> Torniamo verso l'apparecchio.

224
00:17:09,560 --> 00:17:15,240
Tutti hanno con successo ottenere il section6.zip?

225
00:17:15,240 --> 00:17:20,440
Tutti lo decomprimere utilizzando section6.zip unzip?

226
00:17:20,440 --> 00:17:27,200
Se si va nella directory sezione 6 -

227
00:17:27,200 --> 00:17:29,220
aah, in tutto il luogo -

228
00:17:29,220 --> 00:17:32,840
e di elencare ciò che è qui dentro, si vede che hai tre diverse file. c.

229
00:17:32,840 --> 00:17:38,350
Hai una coda, un SLL, che è singolarmente-linked list, e una pila.

230
00:17:38,350 --> 00:17:44,600
Se si apre stack.c,

231
00:17:44,600 --> 00:17:47,330
si può vedere che abbiamo questa struttura definita per noi,

232
00:17:47,330 --> 00:17:51,330
struct esatto che abbiamo appena parlato nelle diapositive.

233
00:17:51,330 --> 00:17:56,340
Abbiamo ottenuto la nostra variabile globale per lo stack,

234
00:17:56,340 --> 00:18:00,110
abbiamo la nostra funzione push,

235
00:18:00,110 --> 00:18:04,230
e poi abbiamo la nostra funzione pop.

236
00:18:04,230 --> 00:18:08,320
Metto il codice per spingere il backup sulla diapositiva qui,

237
00:18:08,320 --> 00:18:10,660
ma quello che mi piacerebbe che voi ragazzi fare è, al meglio delle vostre capacità,

238
00:18:10,660 --> 00:18:13,790
andare a implementare la funzione pop.

239
00:18:13,790 --> 00:18:18,480
Una volta che hai implementato, è possibile compilare questo con fare stack,

240
00:18:18,480 --> 00:18:22,540
e quindi eseguire il file eseguibile risultante stack,

241
00:18:22,540 --> 00:18:28,390
e che verrà eseguito tutto il codice di prova qui che si trova nella principale.

242
00:18:28,390 --> 00:18:31,060
E si prende cura del principale effettivamente rendere il push e pop chiamate

243
00:18:31,060 --> 00:18:33,220
e fare in modo che tutto passa attraverso tutto bene.

244
00:18:33,220 --> 00:18:36,820
Si inizializza anche la dimensione dello stack proprio qui

245
00:18:36,820 --> 00:18:39,780
in modo da non dovete preoccuparvi di inizializzazione che.

246
00:18:39,780 --> 00:18:42,310
Si può supporre che sia stato correttamente inizializzato

247
00:18:42,310 --> 00:18:48,000
nel momento in cui si accede nella funzione pop.

248
00:18:48,000 --> 00:18:53,530
Ha senso?

249
00:18:53,530 --> 00:19:00,100
Quindi qui si va. C'è il codice di spinta.

250
00:19:00,100 --> 00:19:13,210
Ti darò ragazzi 5 o 10 minuti.

251
00:19:13,210 --> 00:19:15,690
E se avete domande nel frattempo, mentre si sta codifica,

252
00:19:15,690 --> 00:19:17,710
si prega di chiedere ad alta voce.

253
00:19:17,710 --> 00:19:23,080
Quindi, se si arriva a un punto critico, basta chiedere.

254
00:19:23,080 --> 00:19:26,030
Fammi sapere, far conoscere tutti gli altri.

255
00:19:26,030 --> 00:19:28,160
Lavora con il tuo vicino di casa troppo.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Stiamo attuazione pop in questo momento? Basta inserire >>.

257
00:19:30,360 --> 00:19:34,200
Anche se è possibile copiare l'attuazione di spinta se si desidera

258
00:19:34,200 --> 00:19:37,780
in modo che il test funziona.

259
00:19:37,780 --> 00:19:41,940
Perché è difficile verificare le cose finiscano nelle -

260
00:19:41,940 --> 00:19:49,030
o, è difficile verificare le cose che appaiono su una pila se non c'è nulla nello stack per cominciare.

261
00:19:49,030 --> 00:19:55,250
>> Che cosa è pop dovrebbe essere di ritorno? L'elemento dalla cima della pila.

262
00:19:55,250 --> 00:20:01,260
Si suppone di ottenere l'elemento fuori della cima della pila

263
00:20:01,260 --> 00:20:05,780
e quindi diminuire la dimensione dello stack,

264
00:20:05,780 --> 00:20:07,810
e ora che hai perso l'elemento in alto.

265
00:20:07,810 --> 00:20:11,420
E poi si ritorna l'elemento in alto.

266
00:20:11,420 --> 00:20:20,080
[Studente, incomprensibile]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Che cosa succede se si fa questo? [Studente, incomprensibile]

268
00:20:28,810 --> 00:20:34,000
Finisce sempre lì è probabilmente stai accedendo sia

269
00:20:34,000 --> 00:20:37,350
un elemento che non è stato ancora inizializzato, in modo che il calcolo

270
00:20:37,350 --> 00:20:39,990
di cui l'ultimo elemento è spento.

271
00:20:39,990 --> 00:20:46,260
Quindi, ecco, se si nota, in push, stiamo accedendo corde in corrispondenza dell'elemento s.size

272
00:20:46,260 --> 00:20:48,560
perché è un nuovo indice.

273
00:20:48,560 --> 00:20:51,460
E 'la nuova cima dello stack.

274
00:20:51,460 --> 00:21:01,100
Considerando che nel pop, s.size sarà spazio successivo,

275
00:21:01,100 --> 00:21:05,210
lo spazio che è al di sopra di tutti gli elementi nel vostro stack.

276
00:21:05,210 --> 00:21:10,050
Così il più in alto elemento non è s.size,

277
00:21:10,050 --> 00:21:14,930
ma piuttosto, è sotto di esso.

278
00:21:14,930 --> 00:21:19,640
>> L'altra cosa da fare quando si - nel pop,

279
00:21:19,640 --> 00:21:22,030
si si ha a diminuire le dimensioni.

280
00:21:22,030 --> 00:21:28,750
Se vi ricordate di nuovo al nostro piccolo diagramma proprio qui,

281
00:21:28,750 --> 00:21:30,980
in realtà, l'unica cosa che abbiamo visto accadere quando abbiamo chiamato pop

282
00:21:30,980 --> 00:21:36,150
è che questa dimensione caduto, prima a 2, a 1.

283
00:21:36,150 --> 00:21:42,620
Poi, quando abbiamo spinto un elemento nuovo, che avrebbe continuato nel punto giusto.

284
00:21:42,620 --> 00:21:49,610
[Basil] Se il s.size è 2, allora non andare all'elemento 2,

285
00:21:49,610 --> 00:21:54,400
e poi che ci si vuole far apparire tale elemento fuori?

286
00:21:54,400 --> 00:21:59,510
Quindi, se siamo andati a - >> Quindi diamo un'occhiata a questo nuovo.

287
00:21:59,510 --> 00:22:07,730
Se questa è la pila a questo punto

288
00:22:07,730 --> 00:22:12,130
e chiamiamo pop,

289
00:22:12,130 --> 00:22:16,150
in cui indice è il più in alto elemento?

290
00:22:16,150 --> 00:22:19,300
[Basilio] A 2 anni, ma che sta per scoppiare 3. >> Destra.

291
00:22:19,300 --> 00:22:24,220
Ecco, questo è dove la nostra dimensione è 3, ma vogliamo far apparire l'elemento di indice 2.

292
00:22:24,220 --> 00:22:29,900
E 'quel tipo tipico di fuori da quello che si ha con lo zero-indicizzazione di array.

293
00:22:29,900 --> 00:22:36,430
Quindi, si vuole far apparire il terzo elemento, ma il terzo elemento non è indice 3.

294
00:22:36,430 --> 00:22:39,430
E la ragione per cui non c'è bisogno di farlo meno 1, quando stiamo spingendo

295
00:22:39,430 --> 00:22:44,120
è perché in questo momento, si nota che il più in alto elemento,

296
00:22:44,120 --> 00:22:47,600
se dovessimo spingere qualcos'altro sulla pila a questo punto,

297
00:22:47,600 --> 00:22:50,360
vorremmo spingere di indice 3.

298
00:22:50,360 --> 00:23:03,550
E si da il caso che le dimensioni e gli indici allineati quando si sta spingendo.

299
00:23:03,550 --> 00:23:06,960
>> Chi ha un implementazione dello stack di lavoro?

300
00:23:06,960 --> 00:23:09,690
Hai una pila funzionante. Avete pop funziona ancora?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Sì. Credo di sì.

302
00:23:11,890 --> 00:23:14,610
Programma >> è in esecuzione e non seg faglie, è la stampa?

303
00:23:14,610 --> 00:23:17,520
Fa stampare il "successo" quando lo si esegue?

304
00:23:17,520 --> 00:23:22,630
Gia '. Fai la pila, eseguirlo, se esso stampa "successo" e non va al braccio,

305
00:23:22,630 --> 00:23:26,000
allora tutto va bene.

306
00:23:26,000 --> 00:23:34,070
Bene. Andiamo verso la macchina molto velocemente,

307
00:23:34,070 --> 00:23:46,100
e noi a piedi attraverso questo.

308
00:23:46,100 --> 00:23:51,110
Se guardiamo a quello che sta succedendo qui con pop,

309
00:23:51,110 --> 00:23:55,220
Daniele, qual è stata la prima cosa che hai fatto?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Se s.size è maggiore di 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Ok. E perché l'hai fatto?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Per fare in modo che ci fosse qualcosa dentro lo stack.

313
00:24:05,610 --> 00:24:10,950
[Hardison] destro. Si desidera verificare fare in modo che s.size è maggiore di 0;

314
00:24:10,950 --> 00:24:13,280
in caso contrario, che cosa vuoi che accada sono?

315
00:24:13,280 --> 00:24:16,630
[Daniel] null ritorno? Ritorno >> nullo, esattamente.

316
00:24:16,630 --> 00:24:20,740
Quindi se s.size è maggiore di 0. Allora che cosa abbiamo intenzione di fare?

317
00:24:20,740 --> 00:24:25,890
Cosa fare se la pila non è vuota?

318
00:24:25,890 --> 00:24:31,210
[Stella] È diminuire le dimensioni? Si >> diminuire le dimensioni, va bene.

319
00:24:31,210 --> 00:24:34,440
Così come hai fatto? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Grande. E poi cosa hai fatto?

321
00:24:37,030 --> 00:24:44,140
[Stella] E poi ho detto di ritorno s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Grande.

323
00:24:48,560 --> 00:24:51,940
In caso contrario, si ritorna null. Sì, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Perché non ne ha bisogno di essere s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? Sì >>. >> Capito.

326
00:24:58,430 --> 00:25:00,980
[Sam] ho pensato, perché si sta prendendo 1 out,

327
00:25:00,980 --> 00:25:04,290
allora si sta andando ad essere di ritorno non è quello che hanno chiesto.

328
00:25:04,290 --> 00:25:09,400
[Hardison] E questo era proprio quello che stavamo parlando di questo problema tutto di 0 indici.

329
00:25:09,400 --> 00:25:11,380
Quindi, se Click qui.

330
00:25:11,380 --> 00:25:15,650
Se guardiamo a questo tizio qui, si può vedere che quando abbiamo pop,

331
00:25:15,650 --> 00:25:19,340
stiamo popping l'elemento di indice 2.

332
00:25:19,340 --> 00:25:25,200
>> Così abbiamo diminuire la nostra dimensione, quindi la nostra dimensione corrisponde a nostro indice.

333
00:25:25,200 --> 00:25:39,650
Se non diminuire la dimensione, quindi dobbiamo fare il formato -1 e poi decremento.

334
00:25:39,650 --> 00:25:45,270
Grande. Tutto bene?

335
00:25:45,270 --> 00:25:47,530
Hai domande su questo?

336
00:25:47,530 --> 00:25:54,050
Ci sono un certo numero di modi diversi per scrivere questo.

337
00:25:54,050 --> 00:26:03,290
In realtà, siamo in grado di fare qualcosa di più - che possiamo fare una battuta.

338
00:26:03,290 --> 00:26:05,770
Possiamo fare una sola linea di ritorno.

339
00:26:05,770 --> 00:26:12,980
Così si può effettivamente diminuire prima di tornare dal farlo.

340
00:26:12,980 --> 00:26:18,320
Quindi mettere il - prima del s.size.

341
00:26:18,320 --> 00:26:22,060
Questo rende la linea molto denso.

342
00:26:22,060 --> 00:26:30,940
Qualora la differenza tra il -. S dimensione e-s.size -

343
00:26:30,940 --> 00:26:40,130
è che questo postfix - lo chiamano postfix perché la - viene dopo il s.size--

344
00:26:40,130 --> 00:26:47,430
significa che s.size viene valutata per la constatazione dell'indice

345
00:26:47,430 --> 00:26:50,410
come avviene attualmente, quando questa linea viene eseguita,

346
00:26:50,410 --> 00:26:54,290
e poi questo - si verifica dopo che la linea viene eseguito.

347
00:26:54,290 --> 00:27:00,340
Dopo l'elemento in corrispondenza dell'indice s.size si accede.

348
00:27:00,340 --> 00:27:07,260
E non è quello che vogliamo, perché vogliamo che il decremento per accadere prima.

349
00:27:07,260 --> 00:27:10,990
Othewise, si sta andando ad essere l'accesso alla matrice, in modo efficace, fuori dai limiti.

350
00:27:10,990 --> 00:27:16,850
Stiamo per essere l'accesso all'elemento superiore a quello che in realtà desidera accedere.

351
00:27:16,850 --> 00:27:23,840
Si ', Sam? >> E 'più veloce o utilizzare meno RAM per fare in una sola riga o no?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Onestamente, in realtà dipende.

353
00:27:29,620 --> 00:27:34,220
[Sam, incomprensibile] >> Si ', dipende. Si può fare trucchi del compilatore

354
00:27:34,220 --> 00:27:41,580
per ottenere il compilatore a riconoscere che, di solito, immagino.

355
00:27:41,580 --> 00:27:44,840
>> Proprio per questo abbiamo parlato di un po 'di questa roba ottimizzazione del compilatore

356
00:27:44,840 --> 00:27:47,400
che si può fare nella compilazione,

357
00:27:47,400 --> 00:27:50,580
e questo è il tipo di cose che un compilatore potrebbe essere in grado di capire,

358
00:27:50,580 --> 00:27:54,710
come oh, hey, forse posso fare tutto questo in una sola operazione,

359
00:27:54,710 --> 00:27:59,420
al contrario di carico variabile in dimensioni da RAM,

360
00:27:59,420 --> 00:28:03,770
decrementando esso, riporlo indietro, e poi torna di nuovo carico

361
00:28:03,770 --> 00:28:08,000
per elaborare il resto di questa operazione.

362
00:28:08,000 --> 00:28:10,710
Ma di solito, no, questo non è il genere di cose

363
00:28:10,710 --> 00:28:20,770
che sta andando a rendere il vostro programma molto più veloce.

364
00:28:20,770 --> 00:28:26,000
Altre domande su pile?

365
00:28:26,000 --> 00:28:31,360
>> Quindi, spingere e popping. Se voi volete provare l'edizione hacker,

366
00:28:31,360 --> 00:28:33,660
quello che abbiamo fatto nel numero di hacker sta effettivamente andato

367
00:28:33,660 --> 00:28:37,670
e fatto questo stack crescere in modo dinamico.

368
00:28:37,670 --> 00:28:43,190
La sfida non è in primo luogo qui nella funzione di spinta,

369
00:28:43,190 --> 00:28:48,820
per capire come far crescere tale matrice

370
00:28:48,820 --> 00:28:52,450
come continuare a spingere sempre più gli elementi sulla pila.

371
00:28:52,450 --> 00:28:56,000
In realtà non è troppo codice aggiuntivo.

372
00:28:56,000 --> 00:29:00,080
Basta una chiamata a - si deve ricordare per ottenere le chiamate a malloc dentro correttamente,

373
00:29:00,080 --> 00:29:03,310
e poi capire quando si sta andando a chiamare realloc.

374
00:29:03,310 --> 00:29:06,090
Questa è una sfida divertente, se siete interessati.

375
00:29:06,090 --> 00:29:11,550
>> Ma per il momento, andiamo avanti, e parliamo di code.

376
00:29:11,550 --> 00:29:15,680
Scorrere qui.

377
00:29:15,680 --> 00:29:19,340
La coda è un fratello vicino alla pila.

378
00:29:19,340 --> 00:29:25,380
Così nello stack, le cose che sono state messe in ultima

379
00:29:25,380 --> 00:29:28,810
erano le prime cose per poi essere recuperati.

380
00:29:28,810 --> 00:29:33,600
Abbiamo ottenuto questo last in, first out, o LIFO, ordinando.

381
00:29:33,600 --> 00:29:38,390
Considerando che, in coda, come ci si aspetterebbe da quando sei in piedi in linea,

382
00:29:38,390 --> 00:29:41,980
la prima persona a mettersi in fila, la prima cosa per entrare in coda,

383
00:29:41,980 --> 00:29:47,630
è la prima cosa che viene recuperato dalla coda.

384
00:29:47,630 --> 00:29:51,490
Le code sono spesso utilizzati quando abbiamo a che fare con i grafici,

385
00:29:51,490 --> 00:29:55,560
come abbiamo parlato brevemente con pile,

386
00:29:55,560 --> 00:30:00,260
e le code sono anche utili per un sacco di altre cose.

387
00:30:00,260 --> 00:30:06,180
Una cosa che viene spesso up sta cercando di mantenere, per esempio,

388
00:30:06,180 --> 00:30:12,310
una lista ordinata di elementi.

389
00:30:12,310 --> 00:30:17,650
E si può fare questo con una matrice. È possibile mantenere un elenco ordinato delle cose in un array,

390
00:30:17,650 --> 00:30:20,650
ma dove che diventa difficile è poi devi sempre trovare

391
00:30:20,650 --> 00:30:26,160
il luogo appropriato per inserire la prossima cosa.

392
00:30:26,160 --> 00:30:28,250
Quindi, se si dispone di una matrice di numeri, da 1 a 10,

393
00:30:28,250 --> 00:30:31,630
e poi si desidera espandere che a tutti i numeri da 1 a 100,

394
00:30:31,630 --> 00:30:33,670
e si stanno ottenendo questi numeri in ordine casuale e cercando di tenere tutto

395
00:30:33,670 --> 00:30:40,650
ordinati come si passa attraverso, si finisce per dover fare un sacco di spostamento.

396
00:30:40,650 --> 00:30:43,910
Con alcuni tipi di code e alcuni tipi di strutture di dati sottostanti,

397
00:30:43,910 --> 00:30:46,670
si può effettivamente mantenere abbastanza semplice.

398
00:30:46,670 --> 00:30:50,640
Non c'è bisogno di aggiungere qualcosa e poi rimescolare il tutto ogni volta.

399
00:30:50,640 --> 00:30:56,770
E non c'è bisogno di fare un sacco di spostamento degli elementi interni intorno.

400
00:30:56,770 --> 00:31:02,990
Quando guardiamo una coda, si vede che - anche in queue.c nella sezione di codice -

401
00:31:02,990 --> 00:31:10,950
la struttura che vi abbiamo dato è molto simile alla struttura che vi abbiamo dato per una pila.

402
00:31:10,950 --> 00:31:13,770
>> C'è una sola eccezione a questo, e che una sola eccezione

403
00:31:13,770 --> 00:31:21,700
è che abbiamo questa ulteriore numero intero chiamato il capo,

404
00:31:21,700 --> 00:31:28,120
e la testa è qui per tenere traccia della testa della coda,

405
00:31:28,120 --> 00:31:32,160
o il primo elemento della coda.

406
00:31:32,160 --> 00:31:37,470
Con uno stack, siamo stati in grado di tenere traccia dell'elemento che stavamo per recuperare,

407
00:31:37,470 --> 00:31:40,800
o la parte superiore della pila, utilizzando solo la dimensione,

408
00:31:40,800 --> 00:31:44,220
mentre con una coda, stiamo avendo a che fare con estremità opposte.

409
00:31:44,220 --> 00:31:49,000
Stiamo cercando di virare su cose alla fine, ma poi tornare le cose dalla parte anteriore.

410
00:31:49,000 --> 00:31:54,640
Così efficacemente, con la testa, abbiamo l'indice di inizio della coda,

411
00:31:54,640 --> 00:31:58,920
e la dimensione ci dà l'indice della fine della coda

412
00:31:58,920 --> 00:32:03,730
in modo da poter recuperare le cose dalla testa e aggiungere cose alla coda.

413
00:32:03,730 --> 00:32:06,890
Considerando che con la pila, abbiamo sempre e solo trattare con la parte superiore della pila.

414
00:32:06,890 --> 00:32:08,900
Abbiamo mai dovuto accedere fondo della pila.

415
00:32:08,900 --> 00:32:12,220
Abbiamo solo aggiunto le cose nella parte superiore e ha preso le cose dalla parte superiore

416
00:32:12,220 --> 00:32:17,470
quindi non abbiamo bisogno di quel campo aggiuntivo all'interno della nostra struttura.

417
00:32:17,470 --> 00:32:20,590
Ritiene che in generale un senso?

418
00:32:20,590 --> 00:32:27,670
Bene. Sì, Charlotte? [Charlotte, incomprensibile]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Questa è una grande domanda, e questo era quello che è venuto in conferenza.

420
00:32:32,660 --> 00:32:36,290
Forse a piedi attraverso alcuni esempi illustreranno perché

421
00:32:36,290 --> 00:32:41,400
non vogliamo usare le stringhe [0] come capo della coda.

422
00:32:41,400 --> 00:32:46,770
>> Quindi immaginate che abbiamo la nostra coda, che andremo a chiamare coda.

423
00:32:46,770 --> 00:32:49,210
All'inizio, quando abbiamo appena creata un'istanza,

424
00:32:49,210 --> 00:32:53,330
quando abbiamo appena dichiarato, non abbiamo inizializzato nulla.

425
00:32:53,330 --> 00:32:56,790
E 'tutta spazzatura. Così, naturalmente, si vuole fare in modo che l'inizializzazione

426
00:32:56,790 --> 00:33:00,950
sia le dimensioni ei campi testa sia 0, qualcosa di ragionevole.

427
00:33:00,950 --> 00:33:05,770
Potremmo anche andare avanti e nullo gli elementi nella nostra coda.

428
00:33:05,770 --> 00:33:09,930
E per rendere questa forma diagramma, si noti che ora la nostra coda può contenere solo tre elementi;

429
00:33:09,930 --> 00:33:13,150
mentre la nostra pila poteva contenere quattro, la nostra coda può contenere solo tre.

430
00:33:13,150 --> 00:33:18,680
E questo è solo per adattare il diagramma.

431
00:33:18,680 --> 00:33:26,150
La prima cosa che accade qui è che accodare la stringa "ciao".

432
00:33:26,150 --> 00:33:30,380
E proprio come abbiamo fatto con la pila, nulla di terribilmente diverso qui,

433
00:33:30,380 --> 00:33:39,230
gettiamo la stringa su stringhe a [0] e incrementare la nostra dimensione di 1.

434
00:33:39,230 --> 00:33:42,720
Noi accodare "bye", viene messo su.

435
00:33:42,720 --> 00:33:45,870
Quindi questo sembra una pila per la maggior parte.

436
00:33:45,870 --> 00:33:53,230
Abbiamo iniziato qui, elemento nuovo, nuovo elemento, la dimensione continua ad aumentare.

437
00:33:53,230 --> 00:33:56,330
Che cosa succede a questo punto, quando si vuole annullare l'accodamento qualcosa?

438
00:33:56,330 --> 00:34:01,280
Quando vogliamo per annullare l'accodamento, che è l'elemento che vogliamo annullare l'accodamento?

439
00:34:01,280 --> 00:34:04,110
[Basilio] Strings [0]. Zero >>. Esattamente, Basil.

440
00:34:04,110 --> 00:34:10,960
Ci vogliono sbarazzarsi della prima stringa, questa, "hi".

441
00:34:10,960 --> 00:34:13,170
Allora, qual è stata la cosa che ha cambiato?

442
00:34:13,170 --> 00:34:17,010
Notate quando abbiamo spuntata qualcosa fuori della pila, abbiamo appena cambiato le dimensioni,

443
00:34:17,010 --> 00:34:22,080
ma qui, abbiamo un paio di cose che cambiano.

444
00:34:22,080 --> 00:34:27,440
Non solo la modifica delle dimensioni, ma le modifiche testa.

445
00:34:27,440 --> 00:34:31,020
Questo è di tornare al punto di Charlotte in precedenza:

446
00:34:31,020 --> 00:34:38,699
perché abbiamo questa testa come bene?

447
00:34:38,699 --> 00:34:42,110
Ha senso ora, Charlotte? Tipo di >>.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Tipo di? Che cosa è successo quando abbiamo rimosse dalla coda?

449
00:34:47,500 --> 00:34:54,340
Che cosa ha la testa farlo ora è interessante?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, perché ha cambiato - va bene. Capisco.

451
00:34:56,449 --> 00:35:02,090
Perché la testa - in cui la testa è rivolta verso i cambiamenti in termini di posizione.

452
00:35:02,090 --> 00:35:07,200
Non è più sempre quello di indice zero. >> Sì, esattamente.

453
00:35:07,200 --> 00:35:17,660
Quello che è successo è stato l'elemento se dequeueing alta

454
00:35:17,660 --> 00:35:20,590
è stato fatto e non abbiamo avuto questo campo la testa

455
00:35:20,590 --> 00:35:26,880
perché siamo stati sempre chiamato questa stringa a 0 indice alla testa della nostra coda,

456
00:35:26,880 --> 00:35:30,170
allora avremmo dovuto spostare il resto della coda verso il basso.

457
00:35:30,170 --> 00:35:36,010
Dovremmo cambiare "bye" di dal strings [1] per le stringhe [0].

458
00:35:36,010 --> 00:35:38,760
E strings [2] fino a strings [1].

459
00:35:38,760 --> 00:35:43,050
E avremmo dovuto fare questo per l'intero elenco di elementi,

460
00:35:43,050 --> 00:35:45,110
l'intera matrice di elementi.

461
00:35:45,110 --> 00:35:50,490
E quando lo facciamo con una matrice, che diventa veramente costoso.

462
00:35:50,490 --> 00:35:53,340
Così qui, non è un grosso problema. Dobbiamo solo tre elementi del nostro array.

463
00:35:53,340 --> 00:35:57,230
Ma se abbiamo avuto una coda di mille elementi, o un milione di elementi,

464
00:35:57,230 --> 00:36:00,060
e poi tutto ad un tratto, abbiamo iniziare a fare un po 'di dequeue chiama tutti in un ciclo,

465
00:36:00,060 --> 00:36:03,930
le cose stanno davvero andando a rallentare, come si sposta tutto verso il basso continuo.

466
00:36:03,930 --> 00:36:07,320
Sai, cambiare di 1, entro il 1 ° turno, entro il 1 ° turno, turno di 1.

467
00:36:07,320 --> 00:36:13,650
Invece, usiamo questa testa, si parla di un "puntatore", anche se non è in realtà un puntatore

468
00:36:13,650 --> 00:36:16,430
in senso stretto, non è un tipo di puntatore.

469
00:36:16,430 --> 00:36:19,410
Non è un * int o un char * o qualcosa di simile.

470
00:36:19,410 --> 00:36:28,930
Ma è rivolta o che indica il capo della nostra coda. Si '?

471
00:36:28,930 --> 00:36:38,800
>> [Studente] Come fa dequeue sapere di fare una scappatina fuori tutto ciò che è a capo?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Come fa dequeue sa per smontare tutto quello che è in testa? Diritto >>, si '.

473
00:36:43,620 --> 00:36:49,050
>> Che cosa sta guardando è solo qualunque sia il campo della testina è impostata.

474
00:36:49,050 --> 00:36:52,710
Quindi, in questo primo caso, se si guarda proprio qui,

475
00:36:52,710 --> 00:36:55,690
la nostra testa è 0, 0 indice. >> Destra.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Così dice okay, bene, l'elemento in corrispondenza dell'indice 0, la stringa "ciao",

477
00:37:00,500 --> 00:37:03,050
è l'elemento alla testa della nostra coda.

478
00:37:03,050 --> 00:37:05,570
Quindi stiamo andando per annullare l'accodamento quel ragazzo.

479
00:37:05,570 --> 00:37:09,800
E che sarà l'elemento che viene restituito al chiamante.

480
00:37:09,800 --> 00:37:14,540
Sì, Saad? >> Allora il direttore stabilisce fondamentalmente la - dove si sta andando a indicizzarlo?

481
00:37:14,540 --> 00:37:17,750
Questo è l'inizio di esso? Sì >>. Va bene >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Questo è diventando il nuovo punto di partenza per la nostra matrice.

483
00:37:22,900 --> 00:37:28,930
Quindi, quando si dequeue qualcosa, tutto ciò che dovete fare è accedere all'elemento di indice q.head,

484
00:37:28,930 --> 00:37:32,240
e che sarà l'elemento che si desidera annullare l'accodamento.

485
00:37:32,240 --> 00:37:34,930
Hai anche a diminuire le dimensioni.

486
00:37:34,930 --> 00:37:39,430
Vedremo tra un po 'le cose si fanno un po' difficile con questo.

487
00:37:39,430 --> 00:37:46,520
Noi dequeue, e ora, se accodare ancora una volta,

488
00:37:46,520 --> 00:37:51,300
dove siamo accodare?

489
00:37:51,300 --> 00:37:55,000
Da dove viene l'elemento successivo andare nella nostra coda?

490
00:37:55,000 --> 00:37:57,980
Dire che vogliamo accodare la stringa "CS".

491
00:37:57,980 --> 00:38:02,240
In quale indice è andata? [Gli studenti] Strings [2]. Due >>.

492
00:38:02,240 --> 00:38:04,980
Perché 2 e non 0?

493
00:38:04,980 --> 00:38:13,570
[Basilio] Perché ora la testa è 1, in modo che è come l'inizio della lista?

494
00:38:13,570 --> 00:38:21,220
[Hardison] destro. E che indica la fine della lista?

495
00:38:21,220 --> 00:38:23,290
Cosa stavamo usando per indicare la fine della nostra coda?

496
00:38:23,290 --> 00:38:25,970
La testa è il capo della nostra coda, l'inizio della nostra coda.

497
00:38:25,970 --> 00:38:29,530
Qual è il fine della nostra coda? [Gli studenti] Dimensioni. Dimensioni >>, esattamente.

498
00:38:29,530 --> 00:38:36,360
Così i nostri nuovi elementi vanno fino alle dimensioni, e gli elementi che abbiamo decollare venire fuori a testa.

499
00:38:36,360 --> 00:38:45,390
Quando si accoda l'elemento successivo, lo stiamo mettendo alle dimensioni.

500
00:38:45,390 --> 00:38:48,530
[Studente] Prima di mettere che in tuttavia, il è stato di 1, giusto?

501
00:38:48,530 --> 00:38:55,690
[Hardison] destro. Quindi non proprio nelle dimensioni. Dimensione + non, +1, ma la testa +.

502
00:38:55,690 --> 00:38:59,990
Perché abbiamo spostato tutto dalla quantità testa.

503
00:38:59,990 --> 00:39:14,270
Ecco, ora abbiamo una coda di dimensione 1 che inizia in corrispondenza dell'indice 1.

504
00:39:14,270 --> 00:39:20,730
La coda è indice 2. Sì?

505
00:39:20,730 --> 00:39:25,780
>> [Studente] Che cosa succede quando si dequeue stringhe [0], e le stringhe "slot di memoria

506
00:39:25,780 --> 00:39:29,420
appena arrivato svuotato, in fondo, o semplicemente dimenticato?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Si '. In questo senso, stiamo semplicemente dimenticare.

508
00:39:34,700 --> 00:39:42,640
Se fossimo memorizzazione delle copie per -

509
00:39:42,640 --> 00:39:46,310
molte strutture di dati spesso archiviare le proprie copie degli elementi

510
00:39:46,310 --> 00:39:51,760
in modo che la persona che gestisce la struttura di dati non deve preoccuparsi

511
00:39:51,760 --> 00:39:53,650
su cui tutti i puntatori sono in corso.

512
00:39:53,650 --> 00:39:56,000
La struttura di dati aggrappa a tutto, tiene a tutte le copie,

513
00:39:56,000 --> 00:39:59,580
fare in modo che tutto ciò che persiste in modo appropriato.

514
00:39:59,580 --> 00:40:03,140
Tuttavia, in questo caso, queste strutture dati solo, per semplicità,

515
00:40:03,140 --> 00:40:05,580
non fare copie di tutto ciò che stiamo memorizzare in loro.

516
00:40:05,580 --> 00:40:08,630
[Studente] Quindi si tratta di una serie continua di -? Sì >>.

517
00:40:08,630 --> 00:40:14,350
Se guardiamo indietro a ciò che è stato la definizione di questa struttura, lo è.

518
00:40:14,350 --> 00:40:19,110
E 'solo un array standard come si è visto,

519
00:40:19,110 --> 00:40:24,280
un array di char * s.

520
00:40:24,280 --> 00:40:26,340
Ritiene che -? >> Si ', mi stavo chiedendo

521
00:40:26,340 --> 00:40:29,130
se avrete finalmente a corto di memoria, in una certa misura,

522
00:40:29,130 --> 00:40:32,330
se si dispone di tutti questi spazi vuoti nella propria matrice?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Sì, è un buon punto.

524
00:40:36,390 --> 00:40:41,530
>> Se guardiamo a quello che è successo oggi, a questo punto,

525
00:40:41,530 --> 00:40:46,350
abbiamo riempito la nostra coda, sembra.

526
00:40:46,350 --> 00:40:50,390
Ma non abbiamo davvero riempito la nostra coda

527
00:40:50,390 --> 00:40:57,710
perché abbiamo una coda che è la dimensione 2, ma inizia in corrispondenza dell'indice 1,

528
00:40:57,710 --> 00:41:02,160
perché è lì che il nostro puntatore di testa è.

529
00:41:02,160 --> 00:41:08,400
Come dicevi, che elemento in stringhe [0], in corrispondenza dell'indice 0, non è davvero lì.

530
00:41:08,400 --> 00:41:10,450
Non è nella nostra coda di più.

531
00:41:10,450 --> 00:41:16,460
Semplicemente non si è preoccupato di andare a sovrascrivere il file quando lo rimosse dalla coda.

532
00:41:16,460 --> 00:41:18,700
Così, anche se sembra che è a corto di memoria, in realtà non sono.

533
00:41:18,700 --> 00:41:23,270
Questo posto è disponibile per noi da usare.

534
00:41:23,270 --> 00:41:29,310
Il comportamento del caso, se dovessimo cercare e prima dequeue qualcosa

535
00:41:29,310 --> 00:41:34,420
come "bye", che sarebbe pop bye off.

536
00:41:34,420 --> 00:41:38,460
Ora la nostra coda inizia a indice 2 ed è di dimensioni 1.

537
00:41:38,460 --> 00:41:42,240
E ora, se cerchiamo di accodare qualcosa di nuovo, ad esempio 50,

538
00:41:42,240 --> 00:41:47,880
50 dovrebbe andare in questo luogo in corrispondenza dell'indice 0

539
00:41:47,880 --> 00:41:51,270
perché è ancora disponibile per noi. Sì, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Succede automaticamente?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Non capita del tutto automatico. Devi fare i conti

542
00:41:56,150 --> 00:42:00,380
per farlo funzionare, ma in sostanza quello che abbiamo fatto è che abbiamo appena finito di girare intorno.

543
00:42:00,380 --> 00:42:04,070
[Saad] Ed è bene se questo ha un foro nel mezzo di esso?

544
00:42:04,070 --> 00:42:08,720
[Hardison] E 'se possiamo fare la matematica funzionare in modo corretto.

545
00:42:08,720 --> 00:42:15,470
>> E si scopre che questo non è in realtà così difficile da fare con l'operatore mod.

546
00:42:15,470 --> 00:42:20,040
Quindi, proprio come abbiamo fatto con Cesare e il materiale crittografico,

547
00:42:20,040 --> 00:42:25,190
con i mod, siamo in grado di ottenere le cose per avvolgere e andare avanti

548
00:42:25,190 --> 00:42:28,090
intorno e intorno e intorno con la nostra coda,

549
00:42:28,090 --> 00:42:32,180
mantenendo quel puntatore di testa si muove intorno.

550
00:42:32,180 --> 00:42:38,840
Notare che la dimensione è sempre rispettando il numero di elementi nella coda.

551
00:42:38,840 --> 00:42:43,110
Ed è solo il puntatore di testa che tiene in bicicletta attraverso.

552
00:42:43,110 --> 00:42:49,660
Se guardiamo a quello che è successo qui, se torniamo all'inizio,

553
00:42:49,660 --> 00:42:55,020
e basta guardare cosa succede alla testa

554
00:42:55,020 --> 00:42:58,240
quando accodare qualcosa, non è successo niente alla testa.

555
00:42:58,240 --> 00:43:00,970
Quando abbiamo accodato qualcosa d'altro, non è successo niente alla testa.

556
00:43:00,970 --> 00:43:04,130
Non appena abbiamo qualcosa di accodamento, la testa va da uno.

557
00:43:04,130 --> 00:43:06,600
Noi accodato qualcosa, non succede nulla alla testa.

558
00:43:06,600 --> 00:43:11,060
Quando dequeue qualcosa, tutto ad un tratto la testa viene incrementato.

559
00:43:11,060 --> 00:43:14,660
Quando accodare qualcosa, non succede nulla alla testa.

560
00:43:14,660 --> 00:43:20,240
>> Che cosa accadrebbe a questo punto se dovessimo annullare l'accodamento qualcosa di nuovo?

561
00:43:20,240 --> 00:43:23,240
Qualche idea? Che cosa accadrebbe alla testa?

562
00:43:23,240 --> 00:43:27,190
Che cosa dovrebbe accadere alla testa

563
00:43:27,190 --> 00:43:32,990
se dovessimo annullare l'accodamento qualcos'altro?

564
00:43:32,990 --> 00:43:35,400
La testa in questo momento è in indice 2,

565
00:43:35,400 --> 00:43:38,920
il che significa che la testa della coda è strings [2].

566
00:43:38,920 --> 00:43:44,280
[Studente] Che restituisce 0? >> Si dovrebbe tornare a 0. Si deve andare a capo indietro intorno, esattamente.

567
00:43:44,280 --> 00:43:48,440
Fino ad ora, ogni volta che abbiamo chiamato dequeue, abbiamo aggiunto uno alla testa,

568
00:43:48,440 --> 00:43:50,960
aggiungere uno alla testa, aggiungere uno alla testa, aggiungere uno alla testa.

569
00:43:50,960 --> 00:43:58,400
Non appena il puntatore di testa arriva l'ultimo indice nel nostro array,

570
00:43:58,400 --> 00:44:05,650
allora dobbiamo avvolgere di nuovo intorno agli inizi, torna a 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] Che cosa determina la capacità della coda in una pila?

572
00:44:09,900 --> 00:44:13,120
[Hardison] In questo caso, abbiamo appena usato una costante # definito. Va bene >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] Nel reale. File c, si può andare nel fango e con esso un po '

574
00:44:19,590 --> 00:44:21,710
e renderlo il più grande o meno come si desidera.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Così, quando si sta facendo una coda, come si fa a fare il computer a sapere

576
00:44:25,310 --> 00:44:29,120
quanto grande volete che lo stack di essere?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Questa è una grande domanda.

578
00:44:31,700 --> 00:44:34,800
Ci sono un paio di modi. Uno è quello di semplicemente definire in anticipo

579
00:44:34,800 --> 00:44:42,050
e dire che questo sarà una coda che ha 4 elementi o 50 elementi o 10.000.

580
00:44:42,050 --> 00:44:45,430
L'altro modo è quello di fare quello che la gente di hacker edizione stanno facendo

581
00:44:45,430 --> 00:44:52,310
e creare funzioni di avere la coda di crescere in modo dinamico man mano le cose vengono aggiunti trovi

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Quindi, per andare con la prima opzione, che cosa si usa la sintassi

583
00:44:54,740 --> 00:44:57,830
per dire al programma quali sono le dimensioni della coda?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Quindi cerchiamo di uscire da questo.

585
00:45:04,780 --> 00:45:12,650
Sono ancora in stack.c qui, quindi sono solo andando a scorrere fino alla cima qui.

586
00:45:12,650 --> 00:45:17,920
Riuscite a vedere questa qui? Questa è la # define capacità 10.

587
00:45:17,920 --> 00:45:24,600
E questa è la sintassi quasi esattamente lo stesso che abbiamo per la coda.

588
00:45:24,600 --> 00:45:28,390
Tranne che in coda, abbiamo ottenuto che campo extra struct qui.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, ho pensato che la capacità significava la capacità per la stringa.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Ecco la lunghezza massima della parola. >> Capito.

591
00:45:36,770 --> 00:45:41,180
Gia '. La capacità qui - questo è un ottimo punto.

592
00:45:41,180 --> 00:45:44,000
E questo è qualcosa che è difficile

593
00:45:44,000 --> 00:45:49,480
perché quello che abbiamo dichiarato qui è un array di char * s.

594
00:45:49,480 --> 00:45:52,770
Un array di puntatori.

595
00:45:52,770 --> 00:45:56,690
Questo è un array di caratteri.

596
00:45:56,690 --> 00:46:01,690
Questo è probabilmente quello che hai visto quando hai dichiarato il tuo buffer per il file di I / O,

597
00:46:01,690 --> 00:46:06,840
quando hai la creazione di stringhe manualmente sullo stack.

598
00:46:06,840 --> 00:46:09,090
Tuttavia, ciò che abbiamo qui è un array di char * s.

599
00:46:09,090 --> 00:46:13,400
Quindi è un array di puntatori.

600
00:46:13,400 --> 00:46:18,350
In realtà, se lo zoom indietro e guardiamo a quello che sta succedendo qui

601
00:46:18,350 --> 00:46:23,140
nella presentazione, si vede che gli elementi reali, i dati di carattere

602
00:46:23,140 --> 00:46:26,180
non è memorizzato all'interno della matrice stessa.

603
00:46:26,180 --> 00:46:42,690
Ciò che è memorizzato all'interno della nostra matrice qui sono puntatori ai dati di tipo carattere.

604
00:46:42,690 --> 00:46:52,560
Va bene. Quindi abbiamo visto come la dimensione della coda è proprio come con la pila,

605
00:46:52,560 --> 00:46:58,670
la dimensione rispetta sempre il numero di elementi nella coda.

606
00:46:58,670 --> 00:47:02,720
Dopo aver fatto 2 accoda, la taglia 2.

607
00:47:02,720 --> 00:47:07,110
Dopo aver fatto un dequeue la dimensione è 1.

608
00:47:07,110 --> 00:47:09,330
Dopo aver fatto un altro enqueue la dimensione è di nuovo fino a 2.

609
00:47:09,330 --> 00:47:12,340
Così la dimensione rispetta sicuramente il numero di elementi nella coda,

610
00:47:12,340 --> 00:47:15,580
e poi la testa continua a andare in bicicletta.

611
00:47:15,580 --> 00:47:20,210
Si va dal 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
E ogni volta che chiamiamo dequeue, il puntatore di testa viene incrementato l'indice successivo.

613
00:47:25,620 --> 00:47:29,930
E se la testa è in procinto di andare oltre, si riporta ad anello intorno a 0.

614
00:47:29,930 --> 00:47:34,870
Quindi, con questo, possiamo scrivere la funzione di dequeue.

615
00:47:34,870 --> 00:47:40,200
E abbiamo intenzione di lasciare la funzione di accodamento per voi ragazzi, invece di attuare.

616
00:47:40,200 --> 00:47:45,880
>> Quando dequeue un elemento dalla nostra coda,

617
00:47:45,880 --> 00:47:55,490
qual è stata la prima cosa che Daniel ha fatto quando abbiamo iniziato a scrivere la funzione pop per i camini?

618
00:47:55,490 --> 00:48:00,490
Fammi sentire da qualcuno che non ha ancora parlato.

619
00:48:00,490 --> 00:48:06,710
Vediamo, Saad, ti ricordi quello che Daniel ha fatto come prima cosa quando ha scritto pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Non ci è stato, è stato - >> E 'testato per qualcosa.

621
00:48:08,860 --> 00:48:12,140
[Saad] Se la dimensione è maggiore di 0. >> Esattamente.

622
00:48:12,140 --> 00:48:14,390
E che cosa era che il test per?

623
00:48:14,390 --> 00:48:19,090
[Saad] Questo è stato il test per vedere se c'è qualcosa all'interno della matrice.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Si '. Esattamente. Così non si può pop nulla di stack se è vuota.

625
00:48:23,210 --> 00:48:26,510
Allo stesso modo, non è possibile annullare l'accodamento qualsiasi cosa, da una coda se è vuota.

626
00:48:26,510 --> 00:48:30,420
Qual è la prima cosa che dobbiamo fare nella nostra funzione dequeue qui, cosa ne pensi?

627
00:48:30,420 --> 00:48:33,860
[Saad] Se la dimensione è maggiore di 0? Sì >>.

628
00:48:33,860 --> 00:48:37,710
In questo caso, in realtà ho solo provato a vedere se è 0.

629
00:48:37,710 --> 00:48:42,240
Se è 0, siamo in grado di restituire null.

630
00:48:42,240 --> 00:48:45,280
Ma la logica esattamente lo stesso.

631
00:48:45,280 --> 00:48:49,110
E continuiamo con questo.

632
00:48:49,110 --> 00:48:54,600
Se la dimensione non è 0, in cui è l'elemento che si vuole annullare l'accodamento?

633
00:48:54,600 --> 00:48:58,550
[Saad] Alla testa? >> Esattamente.

634
00:48:58,550 --> 00:49:01,720
Possiamo solo estrarre il primo elemento della nostra coda

635
00:49:01,720 --> 00:49:07,040
accedendo l'elemento alla testa.

636
00:49:07,040 --> 00:49:14,630
Niente di pazzesco.

637
00:49:14,630 --> 00:49:19,620
Dopo di che, cosa dovremmo fare? Che cosa deve accadere?

638
00:49:19,620 --> 00:49:23,740
Qual è stata l'altra cosa di cui abbiamo parlato in dequeue?

639
00:49:23,740 --> 00:49:28,130
Due cose devono accadere, perché la nostra coda è cambiato.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Ridurre le dimensioni. >> Dobbiamo ridurre le dimensioni e aumentare la testa? Esattamente.

641
00:49:35,640 --> 00:49:40,600
Per aumentare la testa, non si può ciecamente aumentare la testa, ricorda.

642
00:49:40,600 --> 00:49:45,080
Non possiamo fare queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Dobbiamo includere anche questo mod dalla capacità.

644
00:49:51,630 --> 00:49:54,740
E perché noi mod dalla capacità, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] perché deve avvolgere. >> Esattamente.

646
00:49:58,680 --> 00:50:04,750
Abbiamo mod dalla capacità perché deve avvolgere indietro intorno a 0.

647
00:50:04,750 --> 00:50:07,400
Così ora, a questo punto, siamo in grado di fare quello che ha detto Daniel.

648
00:50:07,400 --> 00:50:12,700
Possiamo diminuire le dimensioni.

649
00:50:12,700 --> 00:50:29,170
E poi si può semplicemente restituire l'elemento che era in cima alla coda.

650
00:50:29,170 --> 00:50:34,000
Sembra un po 'contorto in un primo momento. Si potrebbe avere una domanda. Scusa?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Perché la prima nella parte superiore della coda? Dove che vanno?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Proviene dalla quarta riga dal basso.

653
00:50:42,480 --> 00:50:46,060
Dopo test per fare in modo che la nostra coda non è vuota,

654
00:50:46,060 --> 00:50:54,100
tiriamo fuori * primo carattere, tiriamo fuori l'elemento che è seduta in corrispondenza dell'indice testa

655
00:50:54,100 --> 00:50:58,680
della nostra gamma, della nostra matrice stringhe, >> e chiamata prima?

656
00:50:58,680 --> 00:51:04,500
[Hardison] E noi chiamiamo prima. Gia '.

657
00:51:04,500 --> 00:51:09,850
Basta dare un seguito a questo, perché pensi che abbiamo dovuto farlo?

658
00:51:09,850 --> 00:51:18,270
[Sam] Ogni primo è appena rientrato q.strings [q.head]? Sì >>.

659
00:51:18,270 --> 00:51:23,830
>> Perché stiamo facendo questo mutevole del q.head con la funzione mod,

660
00:51:23,830 --> 00:51:27,810
e non c'è modo di farlo entro la linea di ritorno anche.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Esattamente. Tu sei a posto. Sam è totalmente esatte.

662
00:51:31,640 --> 00:51:36,800
La ragione per cui abbiamo dovuto tirare fuori il primo elemento della nostra coda e memorizzarlo in una variabile

663
00:51:36,800 --> 00:51:43,030
perché questa linea dove si è appena q.head,

664
00:51:43,030 --> 00:51:47,030
c'è l'operatore mod in là non è qualcosa che possiamo fare

665
00:51:47,030 --> 00:51:51,230
e lo hanno effetto sulla testa, senza - in una sola riga.

666
00:51:51,230 --> 00:51:54,480
Quindi abbiamo effettivamente necessario estrarre il primo elemento, quindi regolare la testa,

667
00:51:54,480 --> 00:52:00,430
regolare le dimensioni, e quindi restituire l'elemento che abbiamo tirato fuori.

668
00:52:00,430 --> 00:52:02,680
E questo è qualcosa che vedremo venire più tardi con

669
00:52:02,680 --> 00:52:04,920
liste concatenate, come giocare con loro.

670
00:52:04,920 --> 00:52:08,410
Spesso, quando si sta liberando o lo smaltimento di liste collegate

671
00:52:08,410 --> 00:52:13,500
è necessario ricordare l'elemento successivo, il puntatore successivo di una lista concatenata

672
00:52:13,500 --> 00:52:16,330
prima di smaltire quello attuale.

673
00:52:16,330 --> 00:52:23,580
Perché altrimenti buttare via le informazioni di quello che è rimasto nella lista.

674
00:52:23,580 --> 00:52:34,160
Ora, se si va al vostro apparecchio, si apre queue.c-x-fuori.

675
00:52:34,160 --> 00:52:39,390
Quindi, se mi apro queue.c, lasciami zoom qui,

676
00:52:39,390 --> 00:52:44,970
vedrete che si dispone di un simile a questo file.

677
00:52:44,970 --> 00:52:49,200
Simili di aspetto del file a quello che avevamo in precedenza con stack.c.

678
00:52:49,200 --> 00:52:54,690
Abbiamo la nostra struttura per la coda definita proprio come abbiamo visto nelle diapositive.

679
00:52:54,690 --> 00:52:59,870
>> Noi abbiamo la nostra funzione di accodamento, che è per voi di fare.

680
00:52:59,870 --> 00:53:04,340
E abbiamo la funzione dequeue qui.

681
00:53:04,340 --> 00:53:06,870
La funzione di rimozione in il file viene implementata,

682
00:53:06,870 --> 00:53:13,230
ma io lo rimesso sul PowerPoint in modo che si può digitare, se vuoi.

683
00:53:13,230 --> 00:53:16,690
Così, per i prossimi 5 minuti o giù di lì, voi ragazzi lavorare su enqueue

684
00:53:16,690 --> 00:53:22,570
che è quasi l'opposto di dequeue.

685
00:53:22,570 --> 00:53:29,560
Non è necessario regolare la testa quando si è enqueueing, ma che cosa si deve regolare?

686
00:53:29,560 --> 00:53:38,920
Dimensione. Quindi, quando si enqueue, la testa rimane intatta, la dimensione viene cambiato.

687
00:53:38,920 --> 00:53:46,920
Ma ci vuole un po 'di - si dovrà giocare con quella mod

688
00:53:46,920 --> 00:53:57,560
di capire esattamente quello che indice il nuovo elemento deve essere inserito.

689
00:53:57,560 --> 00:54:03,080
Perciò le darò voi ragazzi un po ', mettere dequeue il backup sulla diapositiva,

690
00:54:03,080 --> 00:54:05,200
e come voi ragazzi avete domanda, gridare in modo che possiamo

691
00:54:05,200 --> 00:54:09,220
tutti parlano di loro come un gruppo.

692
00:54:09,220 --> 00:54:13,960
Inoltre, con la dimensione Non. - quando si regolano le dimensioni, si può sempre e solo -

693
00:54:13,960 --> 00:54:18,720
dovete mod le dimensioni mai? [Daniel] >> No. Non c'è bisogno di mod le dimensioni, a destra.

694
00:54:18,720 --> 00:54:24,260
Poiché la dimensione sarà sempre, se tu sei - supponendo che si sta gestendo le cose in modo appropriato,

695
00:54:24,260 --> 00:54:30,840
la dimensione sarà sempre tra 0 e 3.

696
00:54:30,840 --> 00:54:38,680
Dove si deve mod quando stai facendo accodare?

697
00:54:38,680 --> 00:54:41,060
[Studente] Solo per la testa. >> Solo per la testa, esattamente.

698
00:54:41,060 --> 00:54:44,620
E perché devi mod affatto in enqueue?

699
00:54:44,620 --> 00:54:48,830
Quando è una situazione in cui dovresti mod?

700
00:54:48,830 --> 00:54:53,630
[Studente] Se hai roba a spazi, come a spazi 1 e 2,

701
00:54:53,630 --> 00:54:55,950
e poi avete bisogno di aggiungere qualcosa a 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Sì, esattamente. Così, se il puntatore di testa è alla fine,

703
00:55:02,570 --> 00:55:14,210
o se il formato più la tua testa è più grande, o meglio, sta per avvolgere la coda.

704
00:55:14,210 --> 00:55:17,830
>> Quindi, in questa situazione che abbiamo qui sulla diapositiva in questo momento,

705
00:55:17,830 --> 00:55:24,370
se voglio accodare qualcosa in questo momento,

706
00:55:24,370 --> 00:55:31,110
vogliamo accodare qualcosa di indice 0.

707
00:55:31,110 --> 00:55:35,450
Quindi, se si guarda dove va il 50, e io chiamo enqueue 50,

708
00:55:35,450 --> 00:55:40,840
va laggiù in fondo. Va in 0 indice.

709
00:55:40,840 --> 00:55:44,160
Esso sostituisce il 'ciao' che è stato già rimosse dalla coda.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Non si prende cura di questo in dequeue già?

711
00:55:46,210 --> 00:55:50,550
Perché deve fare qualsiasi cosa con la testa in enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, quindi non sta modificando la testa, mi spiace.

713
00:55:55,770 --> 00:56:02,310
Ma si deve usare l'operatore mod quando si sta accedendo

714
00:56:02,310 --> 00:56:04,250
l'elemento che si desidera accodare quando si sta accedendo

715
00:56:04,250 --> 00:56:06,960
l'elemento successivo in coda.

716
00:56:06,960 --> 00:56:10,960
[Basilio] Io non l'ho fatto, e ho avuto "successo" in là.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, capisco quello che stai dicendo.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Così si didn't - hai appena fatto a q.size?

719
00:56:16,240 --> 00:56:20,670
[Basilio] Si '. Ho appena cambiato le parti, io non ho fatto niente con la testa.

720
00:56:20,670 --> 00:56:24,300
[Hardison] In realtà non è necessario reimpostare la testa per essere qualsiasi cosa,

721
00:56:24,300 --> 00:56:31,650
ma quando si indice nella matrice stringhe,

722
00:56:31,650 --> 00:56:39,500
hai in realta 'di andare avanti e calcolare in cui l'elemento successivo è,

723
00:56:39,500 --> 00:56:44,230
withe perché lo stack, l'elemento successivo nel tuo stack è sempre stato

724
00:56:44,230 --> 00:56:48,740
in corrispondenza dell'indice corrispondente al formato.

725
00:56:48,740 --> 00:56:55,850
Se guardiamo indietro presso la nostra funzione stack push,

726
00:56:55,850 --> 00:57:03,100
possiamo sempre buttare nel nostro nuovo elemento a destra dimensione dell'indice.

727
00:57:03,100 --> 00:57:06,710
Considerando che, con la coda, non si può fare

728
00:57:06,710 --> 00:57:10,340
perché se siamo in questa situazione,

729
00:57:10,340 --> 00:57:18,130
se messa in fila 50 La nostra nuova stringa sarebbe andato a destra stringhe [1]

730
00:57:18,130 --> 00:57:20,540
che non vogliamo fare.

731
00:57:20,540 --> 00:57:41,200
Vogliamo avere la stringa di nuovo andare a indice 0.

732
00:57:41,200 --> 00:57:44,320
>> Qualcuno - sì? [Studente] Ho una domanda, ma non è davvero relativa.

733
00:57:44,320 --> 00:57:48,160
Che cosa significa quando qualcuno chiama semplicemente qualcosa come puntatore pred?

734
00:57:48,160 --> 00:57:51,260
Che cosa è che il nome breve per il? Lo so che è solo un nome.

735
00:57:51,260 --> 00:57:59,110
[Hardison] puntatore Pred? Vediamo un po '. In quale contesto?

736
00:57:59,110 --> 00:58:01,790
[Studente] E 'stato per l'inserto. Posso chiedere in seguito, se si desidera

737
00:58:01,790 --> 00:58:03,920
perché non è realmente collegato, ma ho appena -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Da inserire codice di Davide dalla lezione?

739
00:58:07,300 --> 00:58:10,860
Siamo in grado di tirare e che parlare di questo.

740
00:58:10,860 --> 00:58:15,550
Parleremo di che il prossimo, una volta si arriva a liste concatenate.

741
00:58:15,550 --> 00:58:21,440
>> Quindi cerchiamo di guardare molto in fretta ciò che la funzione enqueue assomiglia.

742
00:58:21,440 --> 00:58:26,530
Qual è stata la prima cosa che la gente ha cercato di fare nella vostra linea enqueue? In questa coda?

743
00:58:26,530 --> 00:58:29,960
Simile a quello che hai fatto per lo stack spingere.

744
00:58:29,960 --> 00:58:32,080
Che cosa hai fatto, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, incomprensibile]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Esattamente. Se (q.size CAPACITA ==) -

747
00:58:45,700 --> 00:58:54,720
Ho bisogno di mettere le mie parentesi al posto giusto - restituire false.

748
00:58:54,720 --> 00:59:01,370
Zoom in un po '. Va bene.

749
00:59:01,370 --> 00:59:03,800
Ora, qual è la prossima cosa che abbiamo dovuto fare?

750
00:59:03,800 --> 00:59:11,370
Proprio come con la pila, e inserito al posto giusto.

751
00:59:11,370 --> 00:59:16,010
E così quello che era il posto giusto per inserire questo?

752
00:59:16,010 --> 00:59:23,170
Con la pila era dimensione dell'indice, con questo non è proprio quella.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Ho q.head--o - q.strings >>? Sì >>.

754
00:59:30,210 --> 00:59:40,470
q.strings [q.head + q.size mod CAPACITA ']?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Probabilmente vogliamo mettere parentesi intorno a questo

756
00:59:42,740 --> 00:59:48,830
in modo che ci stai ricevendo il caso precedenza e quindi è cleart a tutti.

757
00:59:48,830 --> 00:59:55,800
E set di uguali? >> Per str? >> Per str. Grande.

758
00:59:55,800 --> 01:00:00,160
E ora qual è l'ultima cosa che dobbiamo fare?

759
01:00:00,160 --> 01:00:06,780
Proprio come abbiamo fatto nello stack. >> Incrementa la dimensione? Incrementa le dimensioni >>.

760
01:00:06,780 --> 01:00:13,830
Boom. E poi, dato che il codice di avviamento appena tornati false per impostazione predefinita,

761
01:00:13,830 --> 01:00:27,460
vogliamo cambiare questo a true se tutto va tutto e tutto va bene.

762
01:00:27,460 --> 01:00:33,050
Bene. Questo è un sacco di informazioni per la sezione.

763
01:00:33,050 --> 01:00:39,480
Non siamo del tutto finita. Vogliamo parlare molto velocemente in merito singolarmente legati liste.

764
01:00:39,480 --> 01:00:44,010
Metto questo in modo da poter tornare in un secondo momento.

765
01:00:44,010 --> 01:00:50,850
Ma torniamo alla nostra presentazione per pochi più diapositive.

766
01:00:50,850 --> 01:00:53,790
Così enqueue è TODO, ora ce l'abbiamo fatta.

767
01:00:53,790 --> 01:00:57,430
>> Ora diamo uno sguardo al singolarmente legati liste.

768
01:00:57,430 --> 01:01:00,040
Abbiamo parlato di questi un po 'di più nella lezione.

769
01:01:00,040 --> 01:01:02,540
Quanti di voi ha visto la demo in cui abbiamo avuto persone

770
01:01:02,540 --> 01:01:08,220
goffamente indicando ogni altri numeri e partecipazione? >> Sono stato in questo.

771
01:01:08,220 --> 01:01:16,620
>> Che cosa pensate voi ragazzi? Forse che, si spera demistificare questi un po '?

772
01:01:16,620 --> 01:01:25,990
Con una lista, si scopre che abbiamo a che fare con questo tipo che andremo a chiamare un nodo.

773
01:01:25,990 --> 01:01:32,520
Considerando che, con la coda e lo stack che abbiamo avuto le strutture che avevamo chiamata in coda in pila,

774
01:01:32,520 --> 01:01:34,860
abbiamo avuto questi tipi di nuova coda in pila,

775
01:01:34,860 --> 01:01:39,240
ecco una lista è in realtà solo costituito da una serie di nodi.

776
01:01:39,240 --> 01:01:45,920
Allo stesso modo che le stringhe sono solo un mucchio di caratteri tutti in fila uno accanto all'altro.

777
01:01:45,920 --> 01:01:50,650
Una lista concatenata è solo un nodo e un altro nodo e un altro nodo e un altro nodo.

778
01:01:50,650 --> 01:01:55,080
E piuttosto che distruggere tutti i nodi insieme e la loro memorizzazione contiguo

779
01:01:55,080 --> 01:01:58,090
va bene uno accanto all'altro in memoria,

780
01:01:58,090 --> 01:02:04,470
avendo questo indicatore accanto ci consente di memorizzare i nodi ovunque, a caso.

781
01:02:04,470 --> 01:02:10,500
E poi tipo di filo tutti insieme per puntare da uno all'altro.

782
01:02:10,500 --> 01:02:15,850
>> E qual era il grande vantaggio che questo ha avuto su un array?

783
01:02:15,850 --> 01:02:21,680
Su tutto memorizzazione contiguo appena attaccato uno accanto all'altro?

784
01:02:21,680 --> 01:02:24,190
Ti ricordi? Si '? Allocazione di memoria dinamica >>?

785
01:02:24,190 --> 01:02:27,220
>> Allocazione dinamica della memoria in che senso?

786
01:02:27,220 --> 01:02:31,780
[Studente] In questo si può continuare a fare più grande e non c'è bisogno di spostare il vostro intero array?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Esattamente. Quindi, con un array, se si desidera inserire un nuovo elemento al centro di essa,

788
01:02:40,940 --> 01:02:45,320
si deve spostare tutto per fare spazio.

789
01:02:45,320 --> 01:02:47,880
E come abbiamo parlato con la coda,

790
01:02:47,880 --> 01:02:50,080
è per questo che continuiamo a puntatore di testa,

791
01:02:50,080 --> 01:02:52,050
in modo che non siamo in costante mutamento cose.

792
01:02:52,050 --> 01:02:54,520
Dato che diventa costoso se hai un array grande

793
01:02:54,520 --> 01:02:57,130
e si sta continuamente facendo questi inserimenti casuali.

794
01:02:57,130 --> 01:03:00,820
Considerando che, con un elenco, tutto quello che dovete fare è lanciare su un nuovo nodo,

795
01:03:00,820 --> 01:03:06,330
regolare i puntatori, e il gioco è fatto.

796
01:03:06,330 --> 01:03:10,940
Che schifo di questo?

797
01:03:10,940 --> 01:03:16,830
A parte il fatto che non è così facile da lavorare come un array? Si '?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Beh, credo che sia molto più difficile accedere a un elemento specifico nella lista collegata?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Non si può semplicemente passare a un elemento arbitrario nel bel mezzo della vostra lista collegata.

800
01:03:30,470 --> 01:03:33,800
Come si fa a farlo, invece? >> È necessario scorrere l'intera cosa.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Si '. Si deve passare attraverso uno alla volta, uno alla volta.

802
01:03:35,660 --> 01:03:38,480
Si tratta di un enorme - è un dolore.

803
01:03:38,480 --> 01:03:41,550
Qual è l'altro - c'è un'altra caduta di questo.

804
01:03:41,550 --> 01:03:45,340
[Basilio] Non è possibile andare avanti e indietro? Devi andare in una direzione?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Si '. Quindi, come possiamo risolvere questo, a volte?

806
01:03:48,570 --> 01:03:53,370
[Basilio] Doppiamente-liste collegate? >> Esattamente. Ci sono liste doppiamente collegate.

807
01:03:53,370 --> 01:03:55,540
Ci sono anche - scusate?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] E 'lo stesso che utilizzare la cosa che pred -

809
01:03:57,620 --> 01:04:01,090
Mi sono appena ricordato, non è che ciò che la cosa è per pred?

810
01:04:01,090 --> 01:04:05,850
Non è che tra doppiamente e singolarmente?

811
01:04:05,850 --> 01:04:10,020
Sguardo [Hardison] Andiamo a cosa esattamente stava facendo.

812
01:04:10,020 --> 01:04:15,760
Quindi qui si va. Ecco l'elenco dei codici.

813
01:04:15,760 --> 01:04:25,620
Qui abbiamo predptr, qui dentro. E 'questo quello di cui parlavi?

814
01:04:25,620 --> 01:04:30,750
Quindi questo è stato - sta liberando una lista e sta cercando di memorizzare un puntatore ad esso.

815
01:04:30,750 --> 01:04:35,000
Questo non è il doppiamente, singolarmente collegate liste.

816
01:04:35,000 --> 01:04:40,090
Possiamo parlare di più su questo più tardi in quanto questo sta parlando liberare l'elenco

817
01:04:40,090 --> 01:04:42,900
e voglio mostrare un po 'di altre cose prima.

818
01:04:42,900 --> 01:04:51,480
ma è solo - è ricordare il valore di ptr

819
01:04:51,480 --> 01:04:54,170
[Studente] Oh, è puntatore precedente? Sì >>.

820
01:04:54,170 --> 01:05:04,070
In modo che possiamo poi incrementare ptr stessa prima di allora ciò predptr è gratuito.

821
01:05:04,070 --> 01:05:09,130
Perché non possiamo libero ptr e quindi chiamare ptr = ptr successiva, giusto?

822
01:05:09,130 --> 01:05:11,260
Sarebbe male.

823
01:05:11,260 --> 01:05:20,940
Quindi cerchiamo di vedere, di nuovo a questo ragazzo.

824
01:05:20,940 --> 01:05:23,900
>> L'altra cosa negativa sugli elenchi è che mentre con una matrice

825
01:05:23,900 --> 01:05:26,520
solo abbiamo tutti gli stessi elementi impilati uno accanto all'altro,

826
01:05:26,520 --> 01:05:29,050
qui abbiamo anche introdotto questo puntatore.

827
01:05:29,050 --> 01:05:34,060
Quindi c'è un pezzo aggiuntivo di memoria che stiamo avendo da usare

828
01:05:34,060 --> 01:05:37,910
per ogni elemento che stiamo memorizzare nella nostra lista.

829
01:05:37,910 --> 01:05:40,030
Otteniamo flessibilità, ma ha un costo.

830
01:05:40,030 --> 01:05:42,230
Viene fornito con il costo di tempo,

831
01:05:42,230 --> 01:05:45,270
e viene fornito con questo costo memoria troppo.

832
01:05:45,270 --> 01:05:47,800
Ora, nel senso che ora dobbiamo passare attraverso ogni elemento della matrice

833
01:05:47,800 --> 01:05:58,670
di trovare quello di indice 10, o che sarebbe stato indice 10 in una matrice.

834
01:05:58,670 --> 01:06:01,230
>> Solo molto in fretta, quando siamo schema su queste liste,

835
01:06:01,230 --> 01:06:05,980
tipicamente si trattenere la testa della lista o il puntatore prima della lista

836
01:06:05,980 --> 01:06:08,010
e notare che questo è un puntatore vero.

837
01:06:08,010 --> 01:06:11,100
E 'a soli 4 byte. Non è un vero e proprio nodo.

838
01:06:11,100 --> 01:06:17,120
Così si vede che non ha alcun valore int in esso, nessun indicatore accanto al suo interno.

839
01:06:17,120 --> 01:06:20,790
E 'letteralmente solo un puntatore.

840
01:06:20,790 --> 01:06:23,550
E 'intenzione di puntare a qualcosa che è una struct nodo reale.

841
01:06:23,550 --> 01:06:28,480
[Sam] Puntatore chiamato nodo? >> Questo è - no. Questo è un puntatore a qualcosa tipo di nodo.

842
01:06:28,480 --> 01:06:32,540
È un puntatore a una struct nodo. >> Oh, va bene.

843
01:06:32,540 --> 01:06:36,870
Schema a sinistra, a destra codice.

844
01:06:36,870 --> 01:06:42,190
Possiamo impostato su null, che è un buon modo per iniziare.

845
01:06:42,190 --> 01:06:49,850
Quando lo schema, hai lo scrivo come nulla o si mette una linea così.

846
01:06:49,850 --> 01:06:53,910
>> Uno dei modi più semplici per lavorare con le liste,

847
01:06:53,910 --> 01:06:57,430
e vi chiediamo di fare entrambe le cose anteposte e aggiungere per vedere le differenze tra i due,

848
01:06:57,430 --> 01:07:01,320
ma anteponendo è sicuramente più facile.

849
01:07:01,320 --> 01:07:05,790
Quando si antepone, è qui che - quando si prepend (7),

850
01:07:05,790 --> 01:07:10,050
si va e creare il nodo struct

851
01:07:10,050 --> 01:07:13,870
e si imposta primo a puntare, perché ora, da quando l'abbiamo anteposto,

852
01:07:13,870 --> 01:07:17,240
che sta per essere all'inizio della lista.

853
01:07:17,240 --> 01:07:22,540
Se si prepend (3), che crea un altro nodo, ma ora 3 viene prima 7.

854
01:07:22,540 --> 01:07:31,130
Quindi stiamo spingendo in sostanza le cose sulla nostra lista.

855
01:07:31,130 --> 01:07:34,720
Ora, si può vedere che anteporre, a volte lo chiamano spingere,

856
01:07:34,720 --> 01:07:39,600
perché si sta spingendo un nuovo elemento sulla vostra lista.

857
01:07:39,600 --> 01:07:43,270
È anche facile da eliminare al fronte di un elenco.

858
01:07:43,270 --> 01:07:45,650
Così la gente spesso si richiede che il pop.

859
01:07:45,650 --> 01:07:52,200
E in questo modo, è possibile emulare uno stack con una lista concatenata.

860
01:07:52,200 --> 01:07:57,880
Whoops. Ci dispiace, ora stiamo entrando append. Quindi qui si anteporre (7), ora ci prepend (3).

861
01:07:57,880 --> 01:08:02,600
Se anteporre qualcosa d'altro su questo elenco, se anteporre (4),

862
01:08:02,600 --> 01:08:06,540
allora avremmo 4 e poi 3 e poi 7.

863
01:08:06,540 --> 01:08:14,220
Allora potremmo pop e rimuovere le 4, rimuovi 3, rimuovere 7.

864
01:08:14,220 --> 01:08:16,500
Spesso il modo più intuitivo di pensare a questo è con append.

865
01:08:16,500 --> 01:08:20,310
Così ho diagramma che cosa sarebbe simile con aggiungere qui.

866
01:08:20,310 --> 01:08:23,380
Qui, allegato (7) non ha un aspetto diverso

867
01:08:23,380 --> 01:08:25,160
perché non c'è un solo elemento della lista.

868
01:08:25,160 --> 01:08:28,620
E aggiungendo (3) lo mette alla fine.

869
01:08:28,620 --> 01:08:31,020
Forse si può vedere in questo momento il trucco con append

870
01:08:31,020 --> 01:08:36,600
è che, dal momento in cui si sa solo l'inizio della lista è,

871
01:08:36,600 --> 01:08:39,450
da aggiungere a un elenco bisogna camminare tutto il percorso attraverso la lista

872
01:08:39,450 --> 01:08:46,500
per arrivare alla fine, stop, quindi creare il nodo e tutto buttare giù.

873
01:08:46,500 --> 01:08:50,590
Collegare tutta la roba.

874
01:08:50,590 --> 01:08:55,170
Quindi, con prepend, come abbiamo appena strappato attraverso questo molto velocemente,

875
01:08:55,170 --> 01:08:58,170
quando si antepone ad una lista, è abbastanza semplice.

876
01:08:58,170 --> 01:09:02,960
>> Fate il vostro nuovo nodo, comportano una qualche allocazione dinamica della memoria.

877
01:09:02,960 --> 01:09:09,830
Quindi qui stiamo facendo un nodo struct usando malloc.

878
01:09:09,830 --> 01:09:14,710
Quindi malloc stiamo usando, perché che ti mettere da parte la memoria per noi per un successivo

879
01:09:14,710 --> 01:09:20,350
perché noi non vogliamo che questo - vogliamo che questa memoria a persistere per un lungo periodo.

880
01:09:20,350 --> 01:09:25,350
E si ottiene un puntatore allo spazio in memoria che abbiamo appena assegnato.

881
01:09:25,350 --> 01:09:29,260
Usiamo dimensione di nodo, non sommare i campi.

882
01:09:29,260 --> 01:09:31,899
Non genera manualmente il numero di byte,

883
01:09:31,899 --> 01:09:39,750
invece usiamo sizeof in modo che sappiamo ci stai ricevendo il numero appropriato di byte.

884
01:09:39,750 --> 01:09:43,660
Facciamo in modo di verificare che la nostra chiamata malloc riuscito.

885
01:09:43,660 --> 01:09:47,939
Questo è qualcosa che si vuole fare in generale.

886
01:09:47,939 --> 01:09:52,590
Sulle macchine moderne, a corto di memoria non è qualcosa che è facile

887
01:09:52,590 --> 01:09:56,610
a meno che non si sta assegnando un sacco di roba e fare un elenco enorme,

888
01:09:56,610 --> 01:10:02,220
ma se si sta costruendo roba per, ad esempio, come un iPhone o un Android,

889
01:10:02,220 --> 01:10:05,230
si ha le risorse di memoria limitate, soprattutto se si sta facendo qualcosa di intenso.

890
01:10:05,230 --> 01:10:08,300
Quindi è bene avere in pratica.

891
01:10:08,300 --> 01:10:10,510
>> Si noti che ho usato un paio di funzioni diverse qui

892
01:10:10,510 --> 01:10:12,880
Dopo aver visto che sono sorta di nuovo.

893
01:10:12,880 --> 01:10:15,870
Così fprintf è come printf

894
01:10:15,870 --> 01:10:21,320
tranne il suo primo argomento è il flusso a cui si desidera stampare.

895
01:10:21,320 --> 01:10:23,900
In questo caso, si vuole stampare la stringa di errore standard

896
01:10:23,900 --> 01:10:29,410
che è diverso dal outStream standard.

897
01:10:29,410 --> 01:10:31,620
Per impostazione predefinita, si presenta nello stesso posto.

898
01:10:31,620 --> 01:10:34,600
Stampa anche verso il terminale, ma si può -

899
01:10:34,600 --> 01:10:38,790
utilizzando i comandi che avete imparato circa, le tecniche di reindirizzamento

900
01:10:38,790 --> 01:10:42,290
hai imparato nel video di Tommy per il set di problema 4, è possibile indirizzare

901
01:10:42,290 --> 01:10:47,900
alle diverse aree, quindi l'uscita, proprio qui, esce il tuo programma.

902
01:10:47,900 --> 01:10:50,440
E 'essenzialmente come tornare da principale,

903
01:10:50,440 --> 01:10:53,600
tranne che utilizzare l'uscita perché qui di ritorno non farà nulla.

904
01:10:53,600 --> 01:10:57,140
Non siamo in main, ritornando così non uscire dal programma come vogliamo.

905
01:10:57,140 --> 01:11:03,020
Così si usa la funzione di uscita e dare un codice di errore.

906
01:11:03,020 --> 01:11:11,890
Quindi qui abbiamo impostato campo del valore del nuovo nodo, il suo campo i per essere uguale a i, e poi lo cablare.

907
01:11:11,890 --> 01:11:15,530
Abbiamo impostato puntatore prossimo il nuovo nodo in modo da puntare al primo,

908
01:11:15,530 --> 01:11:20,460
e poi la prima ora puntare al nuovo nodo.

909
01:11:20,460 --> 01:11:25,120
Queste prime righe di codice, in realtà stiamo costruendo il nuovo nodo.

910
01:11:25,120 --> 01:11:27,280
Non le ultime due righe di questa funzione, ma i primi.

911
01:11:27,280 --> 01:11:30,290
Si può effettivamente tirare fuori in una funzione, in una funzione di supporto.

912
01:11:30,290 --> 01:11:32,560
Questo è spesso quello che faccio è, io lo tiro fuori in una funzione,

913
01:11:32,560 --> 01:11:36,040
Io lo chiamo qualcosa come nodo di generazione,

914
01:11:36,040 --> 01:11:40,410
e che mantiene la funzione di anteporre piuttosto piccola, è a soli 3 linee di allora.

915
01:11:40,410 --> 01:11:48,710
Effettua una chiamata alla mia funzione del nodo di generazione, e poi ho tutto filo fino.

916
01:11:48,710 --> 01:11:51,970
>> L'ultima cosa che voglio mostrarvi,

917
01:11:51,970 --> 01:11:54,030
e ti farò fare append e tutto ciò che da soli,

918
01:11:54,030 --> 01:11:57,500
è come scorrere un elenco.

919
01:11:57,500 --> 01:12:00,780
Ci sono un sacco di modi diversi per scorrere un elenco.

920
01:12:00,780 --> 01:12:03,140
In questo caso, andremo a trovare la lunghezza di una lista.

921
01:12:03,140 --> 01:12:06,570
Così iniziamo con lunghezza = 0.

922
01:12:06,570 --> 01:12:11,580
Questo è molto simile alla scrittura strlen per una stringa.

923
01:12:11,580 --> 01:12:17,780
Questo è quello che voglio visualizzare, questo ciclo for qui.

924
01:12:17,780 --> 01:12:23,530
Sembra un pò funky, non è il solito int i = 0, i <qualunque, i + +.

925
01:12:23,530 --> 01:12:34,920
Invece è inizializzazione nostro n variabile come l'inizio della lista.

926
01:12:34,920 --> 01:12:40,620
E poi, mentre la nostra variabile di iterazione non è null, che andare avanti.

927
01:12:40,620 --> 01:12:46,340
Questo perché, per convenzione, la fine della nostra lista sarà null.

928
01:12:46,340 --> 01:12:48,770
E poi per aumentare, piuttosto che fare + +,

929
01:12:48,770 --> 01:12:57,010
l'equivalente lista concatenata di + + è n = n-> next.

930
01:12:57,010 --> 01:13:00,410
>> Ti farò riempire i vuoti qui perché siamo fuori tempo.

931
01:13:00,410 --> 01:13:09,300
Ma tenere questo in mente mentre si lavora sui pset spellr.

932
01:13:09,300 --> 01:13:11,650
Liste collegate, se si sta implementando una tabella hash,

933
01:13:11,650 --> 01:13:14,010
sarà sicuramente molto utile.

934
01:13:14,010 --> 01:13:21,780
E avendo questo idioma per ciclare su cose renderà la vita molto più facile, si spera.

935
01:13:21,780 --> 01:13:25,910
Tutte le domande, in modo rapido?

936
01:13:25,910 --> 01:13:28,920
[Sam] Vi invierò il completamento sll e SC?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Si '. Manderò le diapositive completati e stack sll completato e queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]