[Powered by Google Translate] [Sezione 6: meno confortevole]
[Nate Hardison] [Harvard University]
[Questo è CS50.] [CS50.TV]
Bene. Benvenuti alla sezione 6.
Questa settimana, abbiamo intenzione di parlare di strutture di dati in sezione,
in primo luogo perché il problema di questa settimana impostato spellr
fa un sacco di diversa struttura di esplorazione dei dati.
Ci sono un sacco di modi diversi si può andare con il problema proposto,
e le strutture di dati più si conoscono, le cose più interessanti che si possono fare.
>> Quindi cerchiamo di iniziare. Per prima cosa andremo a parlare di pile,
le strutture di dati di stack e code che stiamo andando a parlare.
Le pile e le code sono molto utili quando si comincia a parlare di grafici,
che non avete intenzione di fare così tanto in questo momento.
Ma sono veramente buono per capire una delle grandi strutture fondamentali dati di CS.
La descrizione nel disciplinare set problema,
se si tira su, parla di stack come affine alla
la pila di vassoi da pranzo che hai in mensa alle sale da pranzo
dove quando il personale di sala viene e mette i vassoi da pranzo dopo li hanno puliti,
li impilare uno sopra l'altro.
E poi, quando i bambini vengono a procurarsi il cibo,
tirano fuori i vassoi, prima quella superiore, quindi quello sottostante, quindi quello qui sotto che.
Così, in effetti, il primo vassoio che il personale di sala è messo giù l'ultimo che viene tolto.
L'ultimo che il personale di sala messo su è il primo che viene tolto per la cena.
In spec il problema proposto, che è possibile scaricare se non l'hai già fatto,
si parla di modellazione di un stucture dati stack utilizzando questo tipo di struttura.
>> Allora, cosa abbiamo qui, questo è simile a quello che è stato presentato in conferenza,
tranne in conferenza abbiamo presentato questo con int al contrario di char * s.
Questo sarà uno stack che memorizza cosa?
Daniel? Che cosa stiamo memorizzare in questo stack?
[Daniel] Strings? Siamo >> memorizzare stringhe in questo stack, esattamente.
Tutto quello che devi avere per creare uno stack è un array
di una capacità particolare, che in questo caso,
capacità sta per essere tutto maiuscolo perché è una costante.
E poi in aggiunta alla matrice, tutti dobbiamo tracciare è la dimensione corrente dell'array.
Una cosa da notare qui che è genere di freddo
è che stiamo creando la struttura dati impilati uno sopra un'altra struttura dati, l'array.
Ci sono diversi modi per implementare stack.
Noi non lo faremo ancora del tutto, ma si spera che dopo aver fatto le liste collegate problemi,
vedrai come si può facilmente implementare una pila in cima a una lista collegata pure.
Ma per ora, faremo riferimento agli array.
Così ancora una volta, tutto ciò che serve è una matrice e abbiamo solo bisogno di monitorare le dimensioni della matrice.
[Sam] Ci dispiace, perché è che hai detto che il pacco è in cima delle corde?
A me sembra che le corde sono all'interno della pila.
[Hardison] Si '. Stiamo creando, stiamo prendendo la nostra struttura a matrice di dati -
questa è una bella domanda. Quindi la domanda è: perché, per le persone che stanno guardando on-line,
perché stiamo dicendo che la pila è in cima delle corde,
perché qui sembra che le corde sono dentro lo stack?
Il che è del tutto così.
Quello che mi riferivo al fatto che abbiamo una struttura dati array.
Abbiamo un array di char * s, questo array di stringhe,
e stiamo per aggiungere che per creare la struttura dati impilati.
>> Così una pila è leggermente più complessa di una matrice.
Siamo in grado di utilizzare un array per creare uno stack.
Ecco dove si dice che la pila si basa su di un array.
Allo stesso modo, come ho detto prima, siamo in grado di costruire una pila in cima ad una lista concatenata.
Invece di utilizzare un array per contenere i nostri elementi,
potremmo usare una lista concatenata di tenere i nostri elementi e costruire lo stack intorno a quello.
Esaminiamo un paio di esempi, guardando un po 'di codice,
per vedere quello che succede qui.
A sinistra, ho buttato giù quello che struct pila sarà simile in memoria
se la capacità sono stati # definito per essere quattro.
Abbiamo ottenuto il nostro quattro elemento di matrice char *.
Abbiamo strings [0], strings [1], le stringhe [2], strings [3],
e poi che lo spazio per il nostro ultimo numero intero formato.
Questo ha senso? Va bene.
Questo è ciò che succede se quello che faccio sulla destra,
che sarà il mio codice, è quello di dichiarare solo una struttura, una struttura impilata chiamato s.
Questo è ciò che si ottiene. Essa stabilisce la presenza in memoria.
La prima domanda: ecco quali sono i contenuti di questa struct stack?
In questo momento non sono niente, ma non sono del tutto nulla.
Sono questo tipo di rifiuti. Non abbiamo idea di ciò che è in loro.
Quando dichiariamo s pila, stiamo solo buttando giu 'sulla parte superiore della memoria.
E 'un po' come dichiarare int i e non è l'inizializzazione.
Tu non sai cosa c'è dentro. È possibile leggere cosa c'è dentro,
ma potrebbe non essere super disponibile.
Una cosa che si vuole ricordare sempre di fare è inizializzare ciò che deve essere inizializzato.
In questo caso, andremo a inizializzare la dimensione pari a zero,
perché sta per rivelarsi molto importante per noi.
Potremmo andare avanti e inizializzare tutti i puntatori, tutti i char * s,
essere un valore comprensibile, probabilmente nullo.
Ma non è del tutto necessario che lo facciamo.
>> Ora, i due principali operazioni su stack sono?
Chiunque ricordi di lezione ciò che si fa con le pile? Sì?
[Stella] e spinta popping? >> Esattamente.
Spingendo e pop sono i due principali operazioni su stack.
E che cosa fare pressione? >> Si mette qualcosa sulla parte superiore
della pila, e quindi popping decolla.
[Hardison] Esattamente. Così spinge spinge qualcosa in cima alla pila.
E 'come il personale di sala da pranzo di mettere un vassoio sul bancone.
E popping sta prendendo un vassoio da pranzo dallo stack.
Camminiamo attraverso un paio di esempi di ciò che accade
quando spingere le cose nello stack.
Se dovessimo spingere la stringa 'ciao' sul nostro stack,
questo è ciò che il nostro diagramma assomiglierà a ora.
Vedi cosa succede?
Abbiamo spinto nel primo elemento della nostra matrice stringhe
e abbiamo aumentato il nostro numero di dimensioni a 1.
Quindi, se guardiamo la differenza tra le due slitte, qui era 0, ecco prima della spinta.
Ecco dopo la spinta.
Prima della spinta, dopo la spinta.
E ora abbiamo un elemento del nostro stack.
E 'la stringa "ciao", e questo è tutto.
Tutto il resto nella matrice, nella nostra matrice stringhe, è ancora spazzatura.
Non lo abbiamo inizializzato.
Diciamo che spingere un'altra stringa sul nostro stack.
Stiamo andando a spingere "mondo" in questo momento.
Così si può vedere "mondo" va qui sopra "ciao",
e il conteggio dimensione va fino a 2.
Ora siamo in grado di spingere "CS50", e che andrò di nuovo in cima.
Se torniamo indietro, si può vedere come stiamo spingendo le cose in cima alla pila.
Ed ora arriviamo al pop.
Quando abbiamo spuntata qualcosa fuori della pila, cosa è successo?
Chiunque vedere la differenza? E 'abbastanza sottile.
[Studente] La dimensione. >> Si ', la dimensione modificata.
>> Che altro avresti dovrebbe cambiare?
[Studente] Le corde, anche. >> Destra. Le stringhe troppo.
Si scopre che quando si sta facendo in questo modo,
perché non stiamo copiando gli elementi in nostro stack,
in realtà non c'è bisogno di fare niente, possiamo semplicemente utilizzare la dimensione
per tenere traccia del numero di cose nella nostra matrice
in modo che quando abbiamo pop di nuovo, ancora una volta abbiamo appena diminuire la nostra dimensione fino a 1.
Non c'è bisogno di andare effettivamente in e sovrascrivere qualsiasi cosa.
Tipo di funky.
Si scopre che di solito lasciare le cose solo perché è meno lavoro da fare per noi.
Se non c'è bisogno di andare indietro e sovrascrivere qualcosa, allora perché farlo?
Così, quando abbiamo pop doppio dello stack, tutto ciò che fa è diminuire la dimensione di un paio di volte.
E ancora, è solo perché non stiamo copiando le cose nel nostro stack.
Sì? Vai avanti.
[Studente, incomprensibile] >> E poi, cosa succede quando si preme di nuovo qualcosa?
Quando si preme di nuovo qualcosa, dove va a finire?
Dove va a finire, Basil? In stringhe >> [1]? >> Destra.
Perché non andare in strings [3]?
[Basilio] Perché dimenticato che ci fosse qualcosa nelle stringhe [1] e [2]?
[Hardison] Esattamente. La pila, in sostanza, "dimenticato" che si teneva a niente
nelle stringhe [1] o strings [2], in modo che quando spingiamo "Woot",
mette solo che in l'elemento in strings [1].
Ci sono domande su come funziona, a livello di base?
[Sam] Quindi questo non è in alcun modo dinamico, in termini di quantità
o in termini di dimensioni della pila?
[Hardison] Esattamente. Questo è - il punto era che non si trattava di una pila in modo dinamico growning.
Questa è una pila che può contenere al massimo quattro char * s, al massimo quattro cose.
Se dovessimo cercare di spingere una quinta cosa, cosa pensi dovrebbe accadere?
[Gli studenti, incomprensibili]
[Hardison] Esattamente. Ci sono una serie di cose che potrebbero accadere.
Si potrebbe forse errore di segmentazione, a seconda di quello che siamo stati -
esattamente come siamo stati di applicazione back-end.
Si potrebbe sovrascrivere. Si potrebbe avere quel buffer overflow di cui abbiamo parlato in classe.
Quale sarebbe la cosa più ovvia che potrebbe essere sovrascritto
se abbiamo cercato di spingere una cosa in più sul nostro stack?
Quindi, lei ha citato un buffer overflow.
Quale potrebbe essere la cosa che otterrebbe scritto sopra o calpestato
se traboccava accidentalmente cercando di spingere una cosa in più?
[Daniele, incomprensibile] Possibile >>.
Ma inizialmente, cosa potrebbe succedere? Che cosa succede se abbiamo cercato di spingere una quarta cosa?
Si potrebbe sovrascrivere le dimensioni, almeno con questo schema di memoria che abbiamo.
>> Nella definizione di un set problema, che è quello che sta andando ad essere oggi di attuazione,
quello che si vuole fare è solo restituire false.
Il nostro metodo push sta per restituire un valore booleano,
e che il valore booleano è vero se la spinta riesce
e false se non può spingere più niente perché lo stack è pieno.
Esaminiamo un po 'di quel codice al momento.
Ecco la nostra funzione push.
La nostra funzione push per una pila sta andando a prendere nella stringa di mettere in pila.
E 'intenzione di restituire true se la stringa è stata spinta con successo
in caso contrario stack e false.
Qualche suggerimento su quello che potrebbe essere una cosa buona prima a fare qui?
[Sam] Se la dimensione è uguale capacità per poi tornare falso?
[Hardison] Bingo. Bel lavoro.
Se la dimensione è la capacità, che andremo a restituire false.
Non si può mettere qualcosa di più nel nostro stack.
In caso contrario, si vuole mettere qualcosa in cima alla pila.
Che cosa è "la parte superiore della pila," inizialmente?
[Daniel] Dimensione 0? Dimensioni >> 0.
Qual è la parte superiore della pila dopo c'è una cosa che nella pila? Missy, lo sai?
[Missy] One. Dimensioni >> è uno, esattamente. È continuare ad aggiungere alle dimensioni,
e ogni volta che avete deciso di mettere nel nuovo elemento con le dimensioni di indice nella matrice.
Possiamo farlo con quel tipo di one-liner, se questo ha un senso.
Così abbiamo la nostra matrice stringhe, stiamo per accedere all'indice dimensioni,
e stiamo solo andando a conservare il nostro char * in là.
Si noti come non ci sia la copia stringa succedendo qui,
non allocazione dinamica della memoria?
E poi Missy ha portato a ciò che ora abbiamo a che fare,
perché abbiamo memorizzato la stringa nell'apposito spazio nella matrice,
e lei ha detto che abbiamo dovuto incrementare le dimensioni di uno in modo che siamo pronti per la spinta successiva.
Così possiamo farlo con s.size + +.
A questo punto, ci siamo spinti nel nostro array. Qual è l'ultima cosa che dobbiamo fare?
[Studente] Restituisce vero. Restituisce vero >>.
Quindi è abbastanza semplice, un codice molto semplice. Non troppo.
Dopo aver avvolto la testa intorno come lo stack funziona,
questo è abbastanza semplice da implementare.
>> Ora, la parte successiva di questo è popping una stringa dallo stack.
Ho intenzione di dare voi ragazzi un po 'di tempo per lavorare su questo un po'.
E 'quasi essenzialmente l'opposto di quello che abbiamo fatto qui in push.
Quello che ho fatto è in realtà - oops.
Ho avviato un apparecchio qui, e l'apparecchio,
Ho tirato su il problema set 5 specifica.
Se lo zoom qui, possiamo vedere sono a cdn.cs50.net/2012/fall/psets/pset5.pdf.
Avete voi scaricato il codice che si trova qui, section6.zip?
Bene. Se non lo avete fatto, fate che in questo momento, molto velocemente.
Lo farò nella mia finestra di terminale.
Io in realtà lo ha fatto qui. Gia '.
Sì, Sam? >> Ho una domanda sul perché hai detto tra parentesi s.string 's di dimensione = str?
Che cosa è str? È definita da qualche parte, o - oh, in str * char?
[Hardison] Sì, esattamente. Questo è stato l'argomento. >> Oh, va bene. Scusi.
[Hardison] Stiamo specificare la stringa di spingere trovi
L'altra domanda che potrebbe venire che non abbiamo davvero parlare di qui era
abbiamo preso per scontato che abbiamo avuto questa variabile chiamata s
che era in campo di applicazione e accessibile a noi.
Abbiamo preso per scontato che s era questo struct stack.
Quindi, guardando indietro a questo codice spinta,
si può vedere che stiamo facendo qualcosa con questa stringa ha passato in
ma poi tutto ad un tratto, stiamo accedendo s.size, come, da dove s viene?
Nel codice che stiamo andando a guardare in archivio sezione
e poi la roba che vi ritroverete a fare nel tuo problema imposta,
abbiamo fatto il nostro stack struct una variabile globale
in modo da poter avere accesso ad esso in tutte le nostre diverse funzioni
senza dover manualmente passare intorno e passarlo per riferimento,
fare tutto questo genere di cose ad esso.
Stiamo solo barando un po ', se si vuole, per rendere le cose più bello.
E questo è qualcosa che stiamo facendo qui perché è per divertimento, è più facile.
Spesso, vedrete persone lo fanno, se ne hanno uno grande struttura di dati
che è in corso di gestione all'interno del loro programma.
>> Torniamo verso l'apparecchio.
Tutti hanno con successo ottenere il section6.zip?
Tutti lo decomprimere utilizzando section6.zip unzip?
Se si va nella directory sezione 6 -
aah, in tutto il luogo -
e di elencare ciò che è qui dentro, si vede che hai tre diverse file. c.
Hai una coda, un SLL, che è singolarmente-linked list, e una pila.
Se si apre stack.c,
si può vedere che abbiamo questa struttura definita per noi,
struct esatto che abbiamo appena parlato nelle diapositive.
Abbiamo ottenuto la nostra variabile globale per lo stack,
abbiamo la nostra funzione push,
e poi abbiamo la nostra funzione pop.
Metto il codice per spingere il backup sulla diapositiva qui,
ma quello che mi piacerebbe che voi ragazzi fare è, al meglio delle vostre capacità,
andare a implementare la funzione pop.
Una volta che hai implementato, è possibile compilare questo con fare stack,
e quindi eseguire il file eseguibile risultante stack,
e che verrà eseguito tutto il codice di prova qui che si trova nella principale.
E si prende cura del principale effettivamente rendere il push e pop chiamate
e fare in modo che tutto passa attraverso tutto bene.
Si inizializza anche la dimensione dello stack proprio qui
in modo da non dovete preoccuparvi di inizializzazione che.
Si può supporre che sia stato correttamente inizializzato
nel momento in cui si accede nella funzione pop.
Ha senso?
Quindi qui si va. C'è il codice di spinta.
Ti darò ragazzi 5 o 10 minuti.
E se avete domande nel frattempo, mentre si sta codifica,
si prega di chiedere ad alta voce.
Quindi, se si arriva a un punto critico, basta chiedere.
Fammi sapere, far conoscere tutti gli altri.
Lavora con il tuo vicino di casa troppo.
[Daniel] Stiamo attuazione pop in questo momento? Basta inserire >>.
Anche se è possibile copiare l'attuazione di spinta se si desidera
in modo che il test funziona.
Perché è difficile verificare le cose finiscano nelle -
o, è difficile verificare le cose che appaiono su una pila se non c'è nulla nello stack per cominciare.
>> Che cosa è pop dovrebbe essere di ritorno? L'elemento dalla cima della pila.
Si suppone di ottenere l'elemento fuori della cima della pila
e quindi diminuire la dimensione dello stack,
e ora che hai perso l'elemento in alto.
E poi si ritorna l'elemento in alto.
[Studente, incomprensibile]
[Hardison] Che cosa succede se si fa questo? [Studente, incomprensibile]
Finisce sempre lì è probabilmente stai accedendo sia
un elemento che non è stato ancora inizializzato, in modo che il calcolo
di cui l'ultimo elemento è spento.
Quindi, ecco, se si nota, in push, stiamo accedendo corde in corrispondenza dell'elemento s.size
perché è un nuovo indice.
E 'la nuova cima dello stack.
Considerando che nel pop, s.size sarà spazio successivo,
lo spazio che è al di sopra di tutti gli elementi nel vostro stack.
Così il più in alto elemento non è s.size,
ma piuttosto, è sotto di esso.
>> L'altra cosa da fare quando si - nel pop,
si si ha a diminuire le dimensioni.
Se vi ricordate di nuovo al nostro piccolo diagramma proprio qui,
in realtà, l'unica cosa che abbiamo visto accadere quando abbiamo chiamato pop
è che questa dimensione caduto, prima a 2, a 1.
Poi, quando abbiamo spinto un elemento nuovo, che avrebbe continuato nel punto giusto.
[Basil] Se il s.size è 2, allora non andare all'elemento 2,
e poi che ci si vuole far apparire tale elemento fuori?
Quindi, se siamo andati a - >> Quindi diamo un'occhiata a questo nuovo.
Se questa è la pila a questo punto
e chiamiamo pop,
in cui indice è il più in alto elemento?
[Basilio] A 2 anni, ma che sta per scoppiare 3. >> Destra.
Ecco, questo è dove la nostra dimensione è 3, ma vogliamo far apparire l'elemento di indice 2.
E 'quel tipo tipico di fuori da quello che si ha con lo zero-indicizzazione di array.
Quindi, si vuole far apparire il terzo elemento, ma il terzo elemento non è indice 3.
E la ragione per cui non c'è bisogno di farlo meno 1, quando stiamo spingendo
è perché in questo momento, si nota che il più in alto elemento,
se dovessimo spingere qualcos'altro sulla pila a questo punto,
vorremmo spingere di indice 3.
E si da il caso che le dimensioni e gli indici allineati quando si sta spingendo.
>> Chi ha un implementazione dello stack di lavoro?
Hai una pila funzionante. Avete pop funziona ancora?
[Daniel] Sì. Credo di sì.
Programma >> è in esecuzione e non seg faglie, è la stampa?
Fa stampare il "successo" quando lo si esegue?
Gia '. Fai la pila, eseguirlo, se esso stampa "successo" e non va al braccio,
allora tutto va bene.
Bene. Andiamo verso la macchina molto velocemente,
e noi a piedi attraverso questo.
Se guardiamo a quello che sta succedendo qui con pop,
Daniele, qual è stata la prima cosa che hai fatto?
[Daniel] Se s.size è maggiore di 0.
[Hardison] Ok. E perché l'hai fatto?
[Daniel] Per fare in modo che ci fosse qualcosa dentro lo stack.
[Hardison] destro. Si desidera verificare fare in modo che s.size è maggiore di 0;
in caso contrario, che cosa vuoi che accada sono?
[Daniel] null ritorno? Ritorno >> nullo, esattamente.
Quindi se s.size è maggiore di 0. Allora che cosa abbiamo intenzione di fare?
Cosa fare se la pila non è vuota?
[Stella] È diminuire le dimensioni? Si >> diminuire le dimensioni, va bene.
Così come hai fatto? >> S.size--.
[Hardison] Grande. E poi cosa hai fatto?
[Stella] E poi ho detto di ritorno s.string [s.size].
[Hardison] Grande.
In caso contrario, si ritorna null. Sì, Sam?
[Sam] Perché non ne ha bisogno di essere s.size + 1?
[Hardison] Plus 1? Sì >>. >> Capito.
[Sam] ho pensato, perché si sta prendendo 1 out,
allora si sta andando ad essere di ritorno non è quello che hanno chiesto.
[Hardison] E questo era proprio quello che stavamo parlando di questo problema tutto di 0 indici.
Quindi, se Click qui.
Se guardiamo a questo tizio qui, si può vedere che quando abbiamo pop,
stiamo popping l'elemento di indice 2.
>> Così abbiamo diminuire la nostra dimensione, quindi la nostra dimensione corrisponde a nostro indice.
Se non diminuire la dimensione, quindi dobbiamo fare il formato -1 e poi decremento.
Grande. Tutto bene?
Hai domande su questo?
Ci sono un certo numero di modi diversi per scrivere questo.
In realtà, siamo in grado di fare qualcosa di più - che possiamo fare una battuta.
Possiamo fare una sola linea di ritorno.
Così si può effettivamente diminuire prima di tornare dal farlo.
Quindi mettere il - prima del s.size.
Questo rende la linea molto denso.
Qualora la differenza tra il -. S dimensione e-s.size -
è che questo postfix - lo chiamano postfix perché la - viene dopo il s.size--
significa che s.size viene valutata per la constatazione dell'indice
come avviene attualmente, quando questa linea viene eseguita,
e poi questo - si verifica dopo che la linea viene eseguito.
Dopo l'elemento in corrispondenza dell'indice s.size si accede.
E non è quello che vogliamo, perché vogliamo che il decremento per accadere prima.
Othewise, si sta andando ad essere l'accesso alla matrice, in modo efficace, fuori dai limiti.
Stiamo per essere l'accesso all'elemento superiore a quello che in realtà desidera accedere.
Si ', Sam? >> E 'più veloce o utilizzare meno RAM per fare in una sola riga o no?
[Hardison] Onestamente, in realtà dipende.
[Sam, incomprensibile] >> Si ', dipende. Si può fare trucchi del compilatore
per ottenere il compilatore a riconoscere che, di solito, immagino.
>> Proprio per questo abbiamo parlato di un po 'di questa roba ottimizzazione del compilatore
che si può fare nella compilazione,
e questo è il tipo di cose che un compilatore potrebbe essere in grado di capire,
come oh, hey, forse posso fare tutto questo in una sola operazione,
al contrario di carico variabile in dimensioni da RAM,
decrementando esso, riporlo indietro, e poi torna di nuovo carico
per elaborare il resto di questa operazione.
Ma di solito, no, questo non è il genere di cose
che sta andando a rendere il vostro programma molto più veloce.
Altre domande su pile?
>> Quindi, spingere e popping. Se voi volete provare l'edizione hacker,
quello che abbiamo fatto nel numero di hacker sta effettivamente andato
e fatto questo stack crescere in modo dinamico.
La sfida non è in primo luogo qui nella funzione di spinta,
per capire come far crescere tale matrice
come continuare a spingere sempre più gli elementi sulla pila.
In realtà non è troppo codice aggiuntivo.
Basta una chiamata a - si deve ricordare per ottenere le chiamate a malloc dentro correttamente,
e poi capire quando si sta andando a chiamare realloc.
Questa è una sfida divertente, se siete interessati.
>> Ma per il momento, andiamo avanti, e parliamo di code.
Scorrere qui.
La coda è un fratello vicino alla pila.
Così nello stack, le cose che sono state messe in ultima
erano le prime cose per poi essere recuperati.
Abbiamo ottenuto questo last in, first out, o LIFO, ordinando.
Considerando che, in coda, come ci si aspetterebbe da quando sei in piedi in linea,
la prima persona a mettersi in fila, la prima cosa per entrare in coda,
è la prima cosa che viene recuperato dalla coda.
Le code sono spesso utilizzati quando abbiamo a che fare con i grafici,
come abbiamo parlato brevemente con pile,
e le code sono anche utili per un sacco di altre cose.
Una cosa che viene spesso up sta cercando di mantenere, per esempio,
una lista ordinata di elementi.
E si può fare questo con una matrice. È possibile mantenere un elenco ordinato delle cose in un array,
ma dove che diventa difficile è poi devi sempre trovare
il luogo appropriato per inserire la prossima cosa.
Quindi, se si dispone di una matrice di numeri, da 1 a 10,
e poi si desidera espandere che a tutti i numeri da 1 a 100,
e si stanno ottenendo questi numeri in ordine casuale e cercando di tenere tutto
ordinati come si passa attraverso, si finisce per dover fare un sacco di spostamento.
Con alcuni tipi di code e alcuni tipi di strutture di dati sottostanti,
si può effettivamente mantenere abbastanza semplice.
Non c'è bisogno di aggiungere qualcosa e poi rimescolare il tutto ogni volta.
E non c'è bisogno di fare un sacco di spostamento degli elementi interni intorno.
Quando guardiamo una coda, si vede che - anche in queue.c nella sezione di codice -
la struttura che vi abbiamo dato è molto simile alla struttura che vi abbiamo dato per una pila.
>> C'è una sola eccezione a questo, e che una sola eccezione
è che abbiamo questa ulteriore numero intero chiamato il capo,
e la testa è qui per tenere traccia della testa della coda,
o il primo elemento della coda.
Con uno stack, siamo stati in grado di tenere traccia dell'elemento che stavamo per recuperare,
o la parte superiore della pila, utilizzando solo la dimensione,
mentre con una coda, stiamo avendo a che fare con estremità opposte.
Stiamo cercando di virare su cose alla fine, ma poi tornare le cose dalla parte anteriore.
Così efficacemente, con la testa, abbiamo l'indice di inizio della coda,
e la dimensione ci dà l'indice della fine della coda
in modo da poter recuperare le cose dalla testa e aggiungere cose alla coda.
Considerando che con la pila, abbiamo sempre e solo trattare con la parte superiore della pila.
Abbiamo mai dovuto accedere fondo della pila.
Abbiamo solo aggiunto le cose nella parte superiore e ha preso le cose dalla parte superiore
quindi non abbiamo bisogno di quel campo aggiuntivo all'interno della nostra struttura.
Ritiene che in generale un senso?
Bene. Sì, Charlotte? [Charlotte, incomprensibile]
[Hardison] Questa è una grande domanda, e questo era quello che è venuto in conferenza.
Forse a piedi attraverso alcuni esempi illustreranno perché
non vogliamo usare le stringhe [0] come capo della coda.
>> Quindi immaginate che abbiamo la nostra coda, che andremo a chiamare coda.
All'inizio, quando abbiamo appena creata un'istanza,
quando abbiamo appena dichiarato, non abbiamo inizializzato nulla.
E 'tutta spazzatura. Così, naturalmente, si vuole fare in modo che l'inizializzazione
sia le dimensioni ei campi testa sia 0, qualcosa di ragionevole.
Potremmo anche andare avanti e nullo gli elementi nella nostra coda.
E per rendere questa forma diagramma, si noti che ora la nostra coda può contenere solo tre elementi;
mentre la nostra pila poteva contenere quattro, la nostra coda può contenere solo tre.
E questo è solo per adattare il diagramma.
La prima cosa che accade qui è che accodare la stringa "ciao".
E proprio come abbiamo fatto con la pila, nulla di terribilmente diverso qui,
gettiamo la stringa su stringhe a [0] e incrementare la nostra dimensione di 1.
Noi accodare "bye", viene messo su.
Quindi questo sembra una pila per la maggior parte.
Abbiamo iniziato qui, elemento nuovo, nuovo elemento, la dimensione continua ad aumentare.
Che cosa succede a questo punto, quando si vuole annullare l'accodamento qualcosa?
Quando vogliamo per annullare l'accodamento, che è l'elemento che vogliamo annullare l'accodamento?
[Basilio] Strings [0]. Zero >>. Esattamente, Basil.
Ci vogliono sbarazzarsi della prima stringa, questa, "hi".
Allora, qual è stata la cosa che ha cambiato?
Notate quando abbiamo spuntata qualcosa fuori della pila, abbiamo appena cambiato le dimensioni,
ma qui, abbiamo un paio di cose che cambiano.
Non solo la modifica delle dimensioni, ma le modifiche testa.
Questo è di tornare al punto di Charlotte in precedenza:
perché abbiamo questa testa come bene?
Ha senso ora, Charlotte? Tipo di >>.
[Hardison] Tipo di? Che cosa è successo quando abbiamo rimosse dalla coda?
Che cosa ha la testa farlo ora è interessante?
[Charlotte] Oh, perché ha cambiato - va bene. Capisco.
Perché la testa - in cui la testa è rivolta verso i cambiamenti in termini di posizione.
Non è più sempre quello di indice zero. >> Sì, esattamente.
Quello che è successo è stato l'elemento se dequeueing alta
è stato fatto e non abbiamo avuto questo campo la testa
perché siamo stati sempre chiamato questa stringa a 0 indice alla testa della nostra coda,
allora avremmo dovuto spostare il resto della coda verso il basso.
Dovremmo cambiare "bye" di dal strings [1] per le stringhe [0].
E strings [2] fino a strings [1].
E avremmo dovuto fare questo per l'intero elenco di elementi,
l'intera matrice di elementi.
E quando lo facciamo con una matrice, che diventa veramente costoso.
Così qui, non è un grosso problema. Dobbiamo solo tre elementi del nostro array.
Ma se abbiamo avuto una coda di mille elementi, o un milione di elementi,
e poi tutto ad un tratto, abbiamo iniziare a fare un po 'di dequeue chiama tutti in un ciclo,
le cose stanno davvero andando a rallentare, come si sposta tutto verso il basso continuo.
Sai, cambiare di 1, entro il 1 ° turno, entro il 1 ° turno, turno di 1.
Invece, usiamo questa testa, si parla di un "puntatore", anche se non è in realtà un puntatore
in senso stretto, non è un tipo di puntatore.
Non è un * int o un char * o qualcosa di simile.
Ma è rivolta o che indica il capo della nostra coda. Si '?
>> [Studente] Come fa dequeue sapere di fare una scappatina fuori tutto ciò che è a capo?
[Hardison] Come fa dequeue sa per smontare tutto quello che è in testa? Diritto >>, si '.
>> Che cosa sta guardando è solo qualunque sia il campo della testina è impostata.
Quindi, in questo primo caso, se si guarda proprio qui,
la nostra testa è 0, 0 indice. >> Destra.
[Hardison] Così dice okay, bene, l'elemento in corrispondenza dell'indice 0, la stringa "ciao",
è l'elemento alla testa della nostra coda.
Quindi stiamo andando per annullare l'accodamento quel ragazzo.
E che sarà l'elemento che viene restituito al chiamante.
Sì, Saad? >> Allora il direttore stabilisce fondamentalmente la - dove si sta andando a indicizzarlo?
Questo è l'inizio di esso? Sì >>. Va bene >>.
[Hardison] Questo è diventando il nuovo punto di partenza per la nostra matrice.
Quindi, quando si dequeue qualcosa, tutto ciò che dovete fare è accedere all'elemento di indice q.head,
e che sarà l'elemento che si desidera annullare l'accodamento.
Hai anche a diminuire le dimensioni.
Vedremo tra un po 'le cose si fanno un po' difficile con questo.
Noi dequeue, e ora, se accodare ancora una volta,
dove siamo accodare?
Da dove viene l'elemento successivo andare nella nostra coda?
Dire che vogliamo accodare la stringa "CS".
In quale indice è andata? [Gli studenti] Strings [2]. Due >>.
Perché 2 e non 0?
[Basilio] Perché ora la testa è 1, in modo che è come l'inizio della lista?
[Hardison] destro. E che indica la fine della lista?
Cosa stavamo usando per indicare la fine della nostra coda?
La testa è il capo della nostra coda, l'inizio della nostra coda.
Qual è il fine della nostra coda? [Gli studenti] Dimensioni. Dimensioni >>, esattamente.
Così i nostri nuovi elementi vanno fino alle dimensioni, e gli elementi che abbiamo decollare venire fuori a testa.
Quando si accoda l'elemento successivo, lo stiamo mettendo alle dimensioni.
[Studente] Prima di mettere che in tuttavia, il è stato di 1, giusto?
[Hardison] destro. Quindi non proprio nelle dimensioni. Dimensione + non, +1, ma la testa +.
Perché abbiamo spostato tutto dalla quantità testa.
Ecco, ora abbiamo una coda di dimensione 1 che inizia in corrispondenza dell'indice 1.
La coda è indice 2. Sì?
>> [Studente] Che cosa succede quando si dequeue stringhe [0], e le stringhe "slot di memoria
appena arrivato svuotato, in fondo, o semplicemente dimenticato?
[Hardison] Si '. In questo senso, stiamo semplicemente dimenticare.
Se fossimo memorizzazione delle copie per -
molte strutture di dati spesso archiviare le proprie copie degli elementi
in modo che la persona che gestisce la struttura di dati non deve preoccuparsi
su cui tutti i puntatori sono in corso.
La struttura di dati aggrappa a tutto, tiene a tutte le copie,
fare in modo che tutto ciò che persiste in modo appropriato.
Tuttavia, in questo caso, queste strutture dati solo, per semplicità,
non fare copie di tutto ciò che stiamo memorizzare in loro.
[Studente] Quindi si tratta di una serie continua di -? Sì >>.
Se guardiamo indietro a ciò che è stato la definizione di questa struttura, lo è.
E 'solo un array standard come si è visto,
un array di char * s.
Ritiene che -? >> Si ', mi stavo chiedendo
se avrete finalmente a corto di memoria, in una certa misura,
se si dispone di tutti questi spazi vuoti nella propria matrice?
[Hardison] Sì, è un buon punto.
>> Se guardiamo a quello che è successo oggi, a questo punto,
abbiamo riempito la nostra coda, sembra.
Ma non abbiamo davvero riempito la nostra coda
perché abbiamo una coda che è la dimensione 2, ma inizia in corrispondenza dell'indice 1,
perché è lì che il nostro puntatore di testa è.
Come dicevi, che elemento in stringhe [0], in corrispondenza dell'indice 0, non è davvero lì.
Non è nella nostra coda di più.
Semplicemente non si è preoccupato di andare a sovrascrivere il file quando lo rimosse dalla coda.
Così, anche se sembra che è a corto di memoria, in realtà non sono.
Questo posto è disponibile per noi da usare.
Il comportamento del caso, se dovessimo cercare e prima dequeue qualcosa
come "bye", che sarebbe pop bye off.
Ora la nostra coda inizia a indice 2 ed è di dimensioni 1.
E ora, se cerchiamo di accodare qualcosa di nuovo, ad esempio 50,
50 dovrebbe andare in questo luogo in corrispondenza dell'indice 0
perché è ancora disponibile per noi. Sì, Saad?
[Saad] Succede automaticamente?
[Hardison] Non capita del tutto automatico. Devi fare i conti
per farlo funzionare, ma in sostanza quello che abbiamo fatto è che abbiamo appena finito di girare intorno.
[Saad] Ed è bene se questo ha un foro nel mezzo di esso?
[Hardison] E 'se possiamo fare la matematica funzionare in modo corretto.
>> E si scopre che questo non è in realtà così difficile da fare con l'operatore mod.
Quindi, proprio come abbiamo fatto con Cesare e il materiale crittografico,
con i mod, siamo in grado di ottenere le cose per avvolgere e andare avanti
intorno e intorno e intorno con la nostra coda,
mantenendo quel puntatore di testa si muove intorno.
Notare che la dimensione è sempre rispettando il numero di elementi nella coda.
Ed è solo il puntatore di testa che tiene in bicicletta attraverso.
Se guardiamo a quello che è successo qui, se torniamo all'inizio,
e basta guardare cosa succede alla testa
quando accodare qualcosa, non è successo niente alla testa.
Quando abbiamo accodato qualcosa d'altro, non è successo niente alla testa.
Non appena abbiamo qualcosa di accodamento, la testa va da uno.
Noi accodato qualcosa, non succede nulla alla testa.
Quando dequeue qualcosa, tutto ad un tratto la testa viene incrementato.
Quando accodare qualcosa, non succede nulla alla testa.
>> Che cosa accadrebbe a questo punto se dovessimo annullare l'accodamento qualcosa di nuovo?
Qualche idea? Che cosa accadrebbe alla testa?
Che cosa dovrebbe accadere alla testa
se dovessimo annullare l'accodamento qualcos'altro?
La testa in questo momento è in indice 2,
il che significa che la testa della coda è strings [2].
[Studente] Che restituisce 0? >> Si dovrebbe tornare a 0. Si deve andare a capo indietro intorno, esattamente.
Fino ad ora, ogni volta che abbiamo chiamato dequeue, abbiamo aggiunto uno alla testa,
aggiungere uno alla testa, aggiungere uno alla testa, aggiungere uno alla testa.
Non appena il puntatore di testa arriva l'ultimo indice nel nostro array,
allora dobbiamo avvolgere di nuovo intorno agli inizi, torna a 0.
[Charlotte] Che cosa determina la capacità della coda in una pila?
[Hardison] In questo caso, abbiamo appena usato una costante # definito. Va bene >>.
[Hardison] Nel reale. File c, si può andare nel fango e con esso un po '
e renderlo il più grande o meno come si desidera.
[Charlotte] Così, quando si sta facendo una coda, come si fa a fare il computer a sapere
quanto grande volete che lo stack di essere?
[Hardison] Questa è una grande domanda.
Ci sono un paio di modi. Uno è quello di semplicemente definire in anticipo
e dire che questo sarà una coda che ha 4 elementi o 50 elementi o 10.000.
L'altro modo è quello di fare quello che la gente di hacker edizione stanno facendo
e creare funzioni di avere la coda di crescere in modo dinamico man mano le cose vengono aggiunti trovi
>> [Charlotte] Quindi, per andare con la prima opzione, che cosa si usa la sintassi
per dire al programma quali sono le dimensioni della coda?
[Hardison] Ah. Quindi cerchiamo di uscire da questo.
Sono ancora in stack.c qui, quindi sono solo andando a scorrere fino alla cima qui.
Riuscite a vedere questa qui? Questa è la # define capacità 10.
E questa è la sintassi quasi esattamente lo stesso che abbiamo per la coda.
Tranne che in coda, abbiamo ottenuto che campo extra struct qui.
[Charlotte] Oh, ho pensato che la capacità significava la capacità per la stringa.
[Hardison] Ah. >> Ecco la lunghezza massima della parola. >> Capito.
Gia '. La capacità qui - questo è un ottimo punto.
E questo è qualcosa che è difficile
perché quello che abbiamo dichiarato qui è un array di char * s.
Un array di puntatori.
Questo è un array di caratteri.
Questo è probabilmente quello che hai visto quando hai dichiarato il tuo buffer per il file di I / O,
quando hai la creazione di stringhe manualmente sullo stack.
Tuttavia, ciò che abbiamo qui è un array di char * s.
Quindi è un array di puntatori.
In realtà, se lo zoom indietro e guardiamo a quello che sta succedendo qui
nella presentazione, si vede che gli elementi reali, i dati di carattere
non è memorizzato all'interno della matrice stessa.
Ciò che è memorizzato all'interno della nostra matrice qui sono puntatori ai dati di tipo carattere.
Va bene. Quindi abbiamo visto come la dimensione della coda è proprio come con la pila,
la dimensione rispetta sempre il numero di elementi nella coda.
Dopo aver fatto 2 accoda, la taglia 2.
Dopo aver fatto un dequeue la dimensione è 1.
Dopo aver fatto un altro enqueue la dimensione è di nuovo fino a 2.
Così la dimensione rispetta sicuramente il numero di elementi nella coda,
e poi la testa continua a andare in bicicletta.
Si va dal 0-1-2, 0-1-2, 0-1-2.
E ogni volta che chiamiamo dequeue, il puntatore di testa viene incrementato l'indice successivo.
E se la testa è in procinto di andare oltre, si riporta ad anello intorno a 0.
Quindi, con questo, possiamo scrivere la funzione di dequeue.
E abbiamo intenzione di lasciare la funzione di accodamento per voi ragazzi, invece di attuare.
>> Quando dequeue un elemento dalla nostra coda,
qual è stata la prima cosa che Daniel ha fatto quando abbiamo iniziato a scrivere la funzione pop per i camini?
Fammi sentire da qualcuno che non ha ancora parlato.
Vediamo, Saad, ti ricordi quello che Daniel ha fatto come prima cosa quando ha scritto pop?
[Saad] Non ci è stato, è stato - >> E 'testato per qualcosa.
[Saad] Se la dimensione è maggiore di 0. >> Esattamente.
E che cosa era che il test per?
[Saad] Questo è stato il test per vedere se c'è qualcosa all'interno della matrice.
[Hardison] Si '. Esattamente. Così non si può pop nulla di stack se è vuota.
Allo stesso modo, non è possibile annullare l'accodamento qualsiasi cosa, da una coda se è vuota.
Qual è la prima cosa che dobbiamo fare nella nostra funzione dequeue qui, cosa ne pensi?
[Saad] Se la dimensione è maggiore di 0? Sì >>.
In questo caso, in realtà ho solo provato a vedere se è 0.
Se è 0, siamo in grado di restituire null.
Ma la logica esattamente lo stesso.
E continuiamo con questo.
Se la dimensione non è 0, in cui è l'elemento che si vuole annullare l'accodamento?
[Saad] Alla testa? >> Esattamente.
Possiamo solo estrarre il primo elemento della nostra coda
accedendo l'elemento alla testa.
Niente di pazzesco.
Dopo di che, cosa dovremmo fare? Che cosa deve accadere?
Qual è stata l'altra cosa di cui abbiamo parlato in dequeue?
Due cose devono accadere, perché la nostra coda è cambiato.
[Daniel] Ridurre le dimensioni. >> Dobbiamo ridurre le dimensioni e aumentare la testa? Esattamente.
Per aumentare la testa, non si può ciecamente aumentare la testa, ricorda.
Non possiamo fare queue.head + +.
Dobbiamo includere anche questo mod dalla capacità.
E perché noi mod dalla capacità, Stella?
[Stella] perché deve avvolgere. >> Esattamente.
Abbiamo mod dalla capacità perché deve avvolgere indietro intorno a 0.
Così ora, a questo punto, siamo in grado di fare quello che ha detto Daniel.
Possiamo diminuire le dimensioni.
E poi si può semplicemente restituire l'elemento che era in cima alla coda.
Sembra un po 'contorto in un primo momento. Si potrebbe avere una domanda. Scusa?
>> [Sam] Perché la prima nella parte superiore della coda? Dove che vanno?
[Hardison] Proviene dalla quarta riga dal basso.
Dopo test per fare in modo che la nostra coda non è vuota,
tiriamo fuori * primo carattere, tiriamo fuori l'elemento che è seduta in corrispondenza dell'indice testa
della nostra gamma, della nostra matrice stringhe, >> e chiamata prima?
[Hardison] E noi chiamiamo prima. Gia '.
Basta dare un seguito a questo, perché pensi che abbiamo dovuto farlo?
[Sam] Ogni primo è appena rientrato q.strings [q.head]? Sì >>.
>> Perché stiamo facendo questo mutevole del q.head con la funzione mod,
e non c'è modo di farlo entro la linea di ritorno anche.
[Hardison] Esattamente. Tu sei a posto. Sam è totalmente esatte.
La ragione per cui abbiamo dovuto tirare fuori il primo elemento della nostra coda e memorizzarlo in una variabile
perché questa linea dove si è appena q.head,
c'è l'operatore mod in là non è qualcosa che possiamo fare
e lo hanno effetto sulla testa, senza - in una sola riga.
Quindi abbiamo effettivamente necessario estrarre il primo elemento, quindi regolare la testa,
regolare le dimensioni, e quindi restituire l'elemento che abbiamo tirato fuori.
E questo è qualcosa che vedremo venire più tardi con
liste concatenate, come giocare con loro.
Spesso, quando si sta liberando o lo smaltimento di liste collegate
è necessario ricordare l'elemento successivo, il puntatore successivo di una lista concatenata
prima di smaltire quello attuale.
Perché altrimenti buttare via le informazioni di quello che è rimasto nella lista.
Ora, se si va al vostro apparecchio, si apre queue.c-x-fuori.
Quindi, se mi apro queue.c, lasciami zoom qui,
vedrete che si dispone di un simile a questo file.
Simili di aspetto del file a quello che avevamo in precedenza con stack.c.
Abbiamo la nostra struttura per la coda definita proprio come abbiamo visto nelle diapositive.
>> Noi abbiamo la nostra funzione di accodamento, che è per voi di fare.
E abbiamo la funzione dequeue qui.
La funzione di rimozione in il file viene implementata,
ma io lo rimesso sul PowerPoint in modo che si può digitare, se vuoi.
Così, per i prossimi 5 minuti o giù di lì, voi ragazzi lavorare su enqueue
che è quasi l'opposto di dequeue.
Non è necessario regolare la testa quando si è enqueueing, ma che cosa si deve regolare?
Dimensione. Quindi, quando si enqueue, la testa rimane intatta, la dimensione viene cambiato.
Ma ci vuole un po 'di - si dovrà giocare con quella mod
di capire esattamente quello che indice il nuovo elemento deve essere inserito.
Perciò le darò voi ragazzi un po ', mettere dequeue il backup sulla diapositiva,
e come voi ragazzi avete domanda, gridare in modo che possiamo
tutti parlano di loro come un gruppo.
Inoltre, con la dimensione Non. - quando si regolano le dimensioni, si può sempre e solo -
dovete mod le dimensioni mai? [Daniel] >> No. Non c'è bisogno di mod le dimensioni, a destra.
Poiché la dimensione sarà sempre, se tu sei - supponendo che si sta gestendo le cose in modo appropriato,
la dimensione sarà sempre tra 0 e 3.
Dove si deve mod quando stai facendo accodare?
[Studente] Solo per la testa. >> Solo per la testa, esattamente.
E perché devi mod affatto in enqueue?
Quando è una situazione in cui dovresti mod?
[Studente] Se hai roba a spazi, come a spazi 1 e 2,
e poi avete bisogno di aggiungere qualcosa a 0.
[Hardison] Sì, esattamente. Così, se il puntatore di testa è alla fine,
o se il formato più la tua testa è più grande, o meglio, sta per avvolgere la coda.
>> Quindi, in questa situazione che abbiamo qui sulla diapositiva in questo momento,
se voglio accodare qualcosa in questo momento,
vogliamo accodare qualcosa di indice 0.
Quindi, se si guarda dove va il 50, e io chiamo enqueue 50,
va laggiù in fondo. Va in 0 indice.
Esso sostituisce il 'ciao' che è stato già rimosse dalla coda.
[Daniel] Non si prende cura di questo in dequeue già?
Perché deve fare qualsiasi cosa con la testa in enqueue?
[Hardison] Oh, quindi non sta modificando la testa, mi spiace.
Ma si deve usare l'operatore mod quando si sta accedendo
l'elemento che si desidera accodare quando si sta accedendo
l'elemento successivo in coda.
[Basilio] Io non l'ho fatto, e ho avuto "successo" in là.
[Daniel] Oh, capisco quello che stai dicendo.
[Hardison] Così si didn't - hai appena fatto a q.size?
[Basilio] Si '. Ho appena cambiato le parti, io non ho fatto niente con la testa.
[Hardison] In realtà non è necessario reimpostare la testa per essere qualsiasi cosa,
ma quando si indice nella matrice stringhe,
hai in realta 'di andare avanti e calcolare in cui l'elemento successivo è,
withe perché lo stack, l'elemento successivo nel tuo stack è sempre stato
in corrispondenza dell'indice corrispondente al formato.
Se guardiamo indietro presso la nostra funzione stack push,
possiamo sempre buttare nel nostro nuovo elemento a destra dimensione dell'indice.
Considerando che, con la coda, non si può fare
perché se siamo in questa situazione,
se messa in fila 50 La nostra nuova stringa sarebbe andato a destra stringhe [1]
che non vogliamo fare.
Vogliamo avere la stringa di nuovo andare a indice 0.
>> Qualcuno - sì? [Studente] Ho una domanda, ma non è davvero relativa.
Che cosa significa quando qualcuno chiama semplicemente qualcosa come puntatore pred?
Che cosa è che il nome breve per il? Lo so che è solo un nome.
[Hardison] puntatore Pred? Vediamo un po '. In quale contesto?
[Studente] E 'stato per l'inserto. Posso chiedere in seguito, se si desidera
perché non è realmente collegato, ma ho appena -
[Hardison] Da inserire codice di Davide dalla lezione?
Siamo in grado di tirare e che parlare di questo.
Parleremo di che il prossimo, una volta si arriva a liste concatenate.
>> Quindi cerchiamo di guardare molto in fretta ciò che la funzione enqueue assomiglia.
Qual è stata la prima cosa che la gente ha cercato di fare nella vostra linea enqueue? In questa coda?
Simile a quello che hai fatto per lo stack spingere.
Che cosa hai fatto, Stella?
[Stella, incomprensibile]
[Hardison] Esattamente. Se (q.size CAPACITA ==) -
Ho bisogno di mettere le mie parentesi al posto giusto - restituire false.
Zoom in un po '. Va bene.
Ora, qual è la prossima cosa che abbiamo dovuto fare?
Proprio come con la pila, e inserito al posto giusto.
E così quello che era il posto giusto per inserire questo?
Con la pila era dimensione dell'indice, con questo non è proprio quella.
[Daniel] Ho q.head--o - q.strings >>? Sì >>.
q.strings [q.head + q.size mod CAPACITA ']?
[Hardison] Probabilmente vogliamo mettere parentesi intorno a questo
in modo che ci stai ricevendo il caso precedenza e quindi è cleart a tutti.
E set di uguali? >> Per str? >> Per str. Grande.
E ora qual è l'ultima cosa che dobbiamo fare?
Proprio come abbiamo fatto nello stack. >> Incrementa la dimensione? Incrementa le dimensioni >>.
Boom. E poi, dato che il codice di avviamento appena tornati false per impostazione predefinita,
vogliamo cambiare questo a true se tutto va tutto e tutto va bene.
Bene. Questo è un sacco di informazioni per la sezione.
Non siamo del tutto finita. Vogliamo parlare molto velocemente in merito singolarmente legati liste.
Metto questo in modo da poter tornare in un secondo momento.
Ma torniamo alla nostra presentazione per pochi più diapositive.
Così enqueue è TODO, ora ce l'abbiamo fatta.
>> Ora diamo uno sguardo al singolarmente legati liste.
Abbiamo parlato di questi un po 'di più nella lezione.
Quanti di voi ha visto la demo in cui abbiamo avuto persone
goffamente indicando ogni altri numeri e partecipazione? >> Sono stato in questo.
>> Che cosa pensate voi ragazzi? Forse che, si spera demistificare questi un po '?
Con una lista, si scopre che abbiamo a che fare con questo tipo che andremo a chiamare un nodo.
Considerando che, con la coda e lo stack che abbiamo avuto le strutture che avevamo chiamata in coda in pila,
abbiamo avuto questi tipi di nuova coda in pila,
ecco una lista è in realtà solo costituito da una serie di nodi.
Allo stesso modo che le stringhe sono solo un mucchio di caratteri tutti in fila uno accanto all'altro.
Una lista concatenata è solo un nodo e un altro nodo e un altro nodo e un altro nodo.
E piuttosto che distruggere tutti i nodi insieme e la loro memorizzazione contiguo
va bene uno accanto all'altro in memoria,
avendo questo indicatore accanto ci consente di memorizzare i nodi ovunque, a caso.
E poi tipo di filo tutti insieme per puntare da uno all'altro.
>> E qual era il grande vantaggio che questo ha avuto su un array?
Su tutto memorizzazione contiguo appena attaccato uno accanto all'altro?
Ti ricordi? Si '? Allocazione di memoria dinamica >>?
>> Allocazione dinamica della memoria in che senso?
[Studente] In questo si può continuare a fare più grande e non c'è bisogno di spostare il vostro intero array?
[Hardison] Esattamente. Quindi, con un array, se si desidera inserire un nuovo elemento al centro di essa,
si deve spostare tutto per fare spazio.
E come abbiamo parlato con la coda,
è per questo che continuiamo a puntatore di testa,
in modo che non siamo in costante mutamento cose.
Dato che diventa costoso se hai un array grande
e si sta continuamente facendo questi inserimenti casuali.
Considerando che, con un elenco, tutto quello che dovete fare è lanciare su un nuovo nodo,
regolare i puntatori, e il gioco è fatto.
Che schifo di questo?
A parte il fatto che non è così facile da lavorare come un array? Si '?
[Daniel] Beh, credo che sia molto più difficile accedere a un elemento specifico nella lista collegata?
[Hardison] Non si può semplicemente passare a un elemento arbitrario nel bel mezzo della vostra lista collegata.
Come si fa a farlo, invece? >> È necessario scorrere l'intera cosa.
[Hardison] Si '. Si deve passare attraverso uno alla volta, uno alla volta.
Si tratta di un enorme - è un dolore.
Qual è l'altro - c'è un'altra caduta di questo.
[Basilio] Non è possibile andare avanti e indietro? Devi andare in una direzione?
[Hardison] Si '. Quindi, come possiamo risolvere questo, a volte?
[Basilio] Doppiamente-liste collegate? >> Esattamente. Ci sono liste doppiamente collegate.
Ci sono anche - scusate?
>> [Sam] E 'lo stesso che utilizzare la cosa che pred -
Mi sono appena ricordato, non è che ciò che la cosa è per pred?
Non è che tra doppiamente e singolarmente?
Sguardo [Hardison] Andiamo a cosa esattamente stava facendo.
Quindi qui si va. Ecco l'elenco dei codici.
Qui abbiamo predptr, qui dentro. E 'questo quello di cui parlavi?
Quindi questo è stato - sta liberando una lista e sta cercando di memorizzare un puntatore ad esso.
Questo non è il doppiamente, singolarmente collegate liste.
Possiamo parlare di più su questo più tardi in quanto questo sta parlando liberare l'elenco
e voglio mostrare un po 'di altre cose prima.
ma è solo - è ricordare il valore di ptr
[Studente] Oh, è puntatore precedente? Sì >>.
In modo che possiamo poi incrementare ptr stessa prima di allora ciò predptr è gratuito.
Perché non possiamo libero ptr e quindi chiamare ptr = ptr successiva, giusto?
Sarebbe male.
Quindi cerchiamo di vedere, di nuovo a questo ragazzo.
>> L'altra cosa negativa sugli elenchi è che mentre con una matrice
solo abbiamo tutti gli stessi elementi impilati uno accanto all'altro,
qui abbiamo anche introdotto questo puntatore.
Quindi c'è un pezzo aggiuntivo di memoria che stiamo avendo da usare
per ogni elemento che stiamo memorizzare nella nostra lista.
Otteniamo flessibilità, ma ha un costo.
Viene fornito con il costo di tempo,
e viene fornito con questo costo memoria troppo.
Ora, nel senso che ora dobbiamo passare attraverso ogni elemento della matrice
di trovare quello di indice 10, o che sarebbe stato indice 10 in una matrice.
>> Solo molto in fretta, quando siamo schema su queste liste,
tipicamente si trattenere la testa della lista o il puntatore prima della lista
e notare che questo è un puntatore vero.
E 'a soli 4 byte. Non è un vero e proprio nodo.
Così si vede che non ha alcun valore int in esso, nessun indicatore accanto al suo interno.
E 'letteralmente solo un puntatore.
E 'intenzione di puntare a qualcosa che è una struct nodo reale.
[Sam] Puntatore chiamato nodo? >> Questo è - no. Questo è un puntatore a qualcosa tipo di nodo.
È un puntatore a una struct nodo. >> Oh, va bene.
Schema a sinistra, a destra codice.
Possiamo impostato su null, che è un buon modo per iniziare.
Quando lo schema, hai lo scrivo come nulla o si mette una linea così.
>> Uno dei modi più semplici per lavorare con le liste,
e vi chiediamo di fare entrambe le cose anteposte e aggiungere per vedere le differenze tra i due,
ma anteponendo è sicuramente più facile.
Quando si antepone, è qui che - quando si prepend (7),
si va e creare il nodo struct
e si imposta primo a puntare, perché ora, da quando l'abbiamo anteposto,
che sta per essere all'inizio della lista.
Se si prepend (3), che crea un altro nodo, ma ora 3 viene prima 7.
Quindi stiamo spingendo in sostanza le cose sulla nostra lista.
Ora, si può vedere che anteporre, a volte lo chiamano spingere,
perché si sta spingendo un nuovo elemento sulla vostra lista.
È anche facile da eliminare al fronte di un elenco.
Così la gente spesso si richiede che il pop.
E in questo modo, è possibile emulare uno stack con una lista concatenata.
Whoops. Ci dispiace, ora stiamo entrando append. Quindi qui si anteporre (7), ora ci prepend (3).
Se anteporre qualcosa d'altro su questo elenco, se anteporre (4),
allora avremmo 4 e poi 3 e poi 7.
Allora potremmo pop e rimuovere le 4, rimuovi 3, rimuovere 7.
Spesso il modo più intuitivo di pensare a questo è con append.
Così ho diagramma che cosa sarebbe simile con aggiungere qui.
Qui, allegato (7) non ha un aspetto diverso
perché non c'è un solo elemento della lista.
E aggiungendo (3) lo mette alla fine.
Forse si può vedere in questo momento il trucco con append
è che, dal momento in cui si sa solo l'inizio della lista è,
da aggiungere a un elenco bisogna camminare tutto il percorso attraverso la lista
per arrivare alla fine, stop, quindi creare il nodo e tutto buttare giù.
Collegare tutta la roba.
Quindi, con prepend, come abbiamo appena strappato attraverso questo molto velocemente,
quando si antepone ad una lista, è abbastanza semplice.
>> Fate il vostro nuovo nodo, comportano una qualche allocazione dinamica della memoria.
Quindi qui stiamo facendo un nodo struct usando malloc.
Quindi malloc stiamo usando, perché che ti mettere da parte la memoria per noi per un successivo
perché noi non vogliamo che questo - vogliamo che questa memoria a persistere per un lungo periodo.
E si ottiene un puntatore allo spazio in memoria che abbiamo appena assegnato.
Usiamo dimensione di nodo, non sommare i campi.
Non genera manualmente il numero di byte,
invece usiamo sizeof in modo che sappiamo ci stai ricevendo il numero appropriato di byte.
Facciamo in modo di verificare che la nostra chiamata malloc riuscito.
Questo è qualcosa che si vuole fare in generale.
Sulle macchine moderne, a corto di memoria non è qualcosa che è facile
a meno che non si sta assegnando un sacco di roba e fare un elenco enorme,
ma se si sta costruendo roba per, ad esempio, come un iPhone o un Android,
si ha le risorse di memoria limitate, soprattutto se si sta facendo qualcosa di intenso.
Quindi è bene avere in pratica.
>> Si noti che ho usato un paio di funzioni diverse qui
Dopo aver visto che sono sorta di nuovo.
Così fprintf è come printf
tranne il suo primo argomento è il flusso a cui si desidera stampare.
In questo caso, si vuole stampare la stringa di errore standard
che è diverso dal outStream standard.
Per impostazione predefinita, si presenta nello stesso posto.
Stampa anche verso il terminale, ma si può -
utilizzando i comandi che avete imparato circa, le tecniche di reindirizzamento
hai imparato nel video di Tommy per il set di problema 4, è possibile indirizzare
alle diverse aree, quindi l'uscita, proprio qui, esce il tuo programma.
E 'essenzialmente come tornare da principale,
tranne che utilizzare l'uscita perché qui di ritorno non farà nulla.
Non siamo in main, ritornando così non uscire dal programma come vogliamo.
Così si usa la funzione di uscita e dare un codice di errore.
Quindi qui abbiamo impostato campo del valore del nuovo nodo, il suo campo i per essere uguale a i, e poi lo cablare.
Abbiamo impostato puntatore prossimo il nuovo nodo in modo da puntare al primo,
e poi la prima ora puntare al nuovo nodo.
Queste prime righe di codice, in realtà stiamo costruendo il nuovo nodo.
Non le ultime due righe di questa funzione, ma i primi.
Si può effettivamente tirare fuori in una funzione, in una funzione di supporto.
Questo è spesso quello che faccio è, io lo tiro fuori in una funzione,
Io lo chiamo qualcosa come nodo di generazione,
e che mantiene la funzione di anteporre piuttosto piccola, è a soli 3 linee di allora.
Effettua una chiamata alla mia funzione del nodo di generazione, e poi ho tutto filo fino.
>> L'ultima cosa che voglio mostrarvi,
e ti farò fare append e tutto ciò che da soli,
è come scorrere un elenco.
Ci sono un sacco di modi diversi per scorrere un elenco.
In questo caso, andremo a trovare la lunghezza di una lista.
Così iniziamo con lunghezza = 0.
Questo è molto simile alla scrittura strlen per una stringa.
Questo è quello che voglio visualizzare, questo ciclo for qui.
Sembra un pò funky, non è il solito int i = 0, i <qualunque, i + +.
Invece è inizializzazione nostro n variabile come l'inizio della lista.
E poi, mentre la nostra variabile di iterazione non è null, che andare avanti.
Questo perché, per convenzione, la fine della nostra lista sarà null.
E poi per aumentare, piuttosto che fare + +,
l'equivalente lista concatenata di + + è n = n-> next.
>> Ti farò riempire i vuoti qui perché siamo fuori tempo.
Ma tenere questo in mente mentre si lavora sui pset spellr.
Liste collegate, se si sta implementando una tabella hash,
sarà sicuramente molto utile.
E avendo questo idioma per ciclare su cose renderà la vita molto più facile, si spera.
Tutte le domande, in modo rapido?
[Sam] Vi invierò il completamento sll e SC?
[Hardison] Si '. Manderò le diapositive completati e stack sll completato e queue.cs.
[CS50.TV]