[Powered by Google Translate] [Sezione 6] [più confortevole] [Rob Bowden] [Harvard University] [Questo è CS50.] [CS50.TV] 

Siamo in grado di dirigersi verso la nostra sezione di domande. Ho mandato l'URL per lo spazio prima. L'inizio della sezione delle domande dire- a quanto pare non sono del tutto unsick-è una domanda molto semplice di ciò che è valgrind? Cosa fa valgrind fare? Qualcuno vuole dire cosa valgrind fa? [Studente] Controlli perdite di memoria. Si ', Valgrind è una pedina di memoria generale. E, alla fine, ti dice se hai perdite di memoria, che è in gran parte quello che stiamo usando per perché se si vuole fare bene nel set problema o se si desidera salire sulla tavola grande, è necessario non avere perdite di memoria di sorta, e nel caso in cui si ha una perdita di memoria che non si può trovare, anche tenere a mente che ogni volta che si apre un file e se non si chiude, che è una perdita di memoria. 

Un sacco di persone sono alla ricerca di un nodo che non stanno liberando quando in realtà, non chiudere il dizionario nel primo passo. Si dice anche che se una valida legge o scrive, il che significa che se si cerca di impostare un valore che va oltre la fine del mucchio e non accade per colpa seg ma Valgrind lo cattura, come non si dovrebbe effettivamente essere iscritto lì, e quindi sicuramente non dovrebbe avere una di queste due. Come si usa valgrind? Come si usa valgrind? 

E 'una questione generale di tipo di eseguirlo e guardare l'output. L'uscita è travolgendo un sacco di volte. Ci sono anche errori divertenti in cui, se avete qualche cosa di terribilmente sbagliato accade in un ciclo, poi alla fine dire: "Via troppi errori. Ho intenzione di smettere di contare ora. " Si tratta fondamentalmente di output testuale che si deve analizzare. Alla fine, vi dirà tutte le perdite di memoria che avete, il numero di blocchi, che può essere utile perché se si tratta di uno unfreed blocco, poi di solito è più facile trovare oltre 1.000 blocchi unfreed. 1.000 blocchi unfreed probabilmente significa che non stai liberando le liste collegate in modo appropriato o qualcosa del genere. Questo è valgrind. 

Ora abbiamo la nostra sezione di domande, che non è necessario scaricare. È possibile fare clic sul mio nome e tirare in su nello spazio. Ora cliccate su di me. Revisione 1 sarà stack, che stiamo facendo per primi. Revisione 2 sarà coda e Revisione 3 sarà la lista concatenata. Partendo con il nostro stack. Come si dice qui, una pila è uno dei più basilari, strutture di dati fondamentali di informatica. L'esempio è molto prototipo la pila di vassoi nella sala da pranzo. E 'fondamentalmente ogni volta che sono state introdotte per una pila, qualcuno sta per dire: "Oh, come una pila di piatti." È impilare i vassoi in su. Poi, quando si va a tirare un vassoio, il primo vassoio che sta facendo è tirato l'ultimo che è stato messo in pila. Lo stack anche-come dice qui- abbiamo il segmento di memoria chiamata stack. E perché si chiama la pila? 

Poiché come una struttura di dati pila, spinge e si apre stack frame sullo stack, dove stack frame sono come una specifica chiamata di una funzione. E come una pila, si dovrà sempre tornare da una chiamata di funzione prima di poter scendere in stack frame inferiori di nuovo. Non si può avere principale chiamata di blocco chiamata foo e tornare direttamente alla barra principale. E 'sempre avuto modo di seguire la pila giusta spinta e popping. Le due operazioni, come ho detto, sono push e pop. Questi sono termini universali. Si deve sapere push e pop, in termini di stack non importa quale. Staremo a vedere le code sono un po 'diverse. E 'in realtà non hanno un termine universale, ma push e pop sono universale per pile. Push è solo messa in pila. Pop è togliere la pila. E vediamo qui abbiamo il nostro stack typedef struct, così abbiamo stringhe char **. Non avere paura di qualsiasi **. Questo sta per finire per essere un array di stringhe o un array di puntatori a caratteri, dove puntatori a caratteri tendono ad essere stringhe. Essa non deve essere stringhe, ma qui, che stanno andando a essere stringhe. 

Abbiamo un array di stringhe. Abbiamo una dimensione, che rappresenta quanti elementi sono attualmente in pila, e poi abbiamo la capacità, che è il numero di elementi possono essere in pila. La capacità dovrebbe cominciare come qualcosa di più grande di 1, ma la dimensione sta per iniziare come 0. Ora, ci sono fondamentalmente tre modi diversi si può pensare di una pila. Beh, ci sono probabilmente di più, ma i due modi principali sono è possibile implementare utilizzando un array, oppure è possibile implementare con una lista concatenata. Liste collegate sono un po 'banali per fare pile da. E 'molto facile fare una pila con liste collegate, ecco, stiamo andando a fare una pila l'utilizzo di matrici, e poi l'utilizzo di matrici, ci sono anche due modi si può pensare a questo proposito. Prima, quando ho detto che abbiamo una capacità di stack, in modo da poter inserire un elemento nello stack. 

L'unico modo in cui potrebbe accadere è appena colpito 10 elementi, allora il gioco è fatto. Si potrebbe sapere che esiste un limite superiore di 10 cose del mondo che non avrete mai più di 10 cose sul tuo stack, nel qual caso si può avere un limite superiore per la dimensione del tuo stack. Oppure si potrebbe avere il tuo stack essere illimitato, ma se si sta facendo una matrice, il che significa che ogni volta che si ha colpito 10 elementi, allora si sta andando ad avere per crescere fino a 20 elementi, e quando si colpisce 20 elementi, si sta andando ad avere per far crescere la tua matrice a 30 elementi o 40 elementi. Stai andando ad avere bisogno di aumentare la capacità, che è quello che andremo a fare qui. Ogni volta si raggiunge la dimensione massima del nostro stack, quando spingiamo qualcos'altro, stiamo andando ad avere bisogno per aumentare la capacità. Qui, abbiamo spinta dichiarata come spinta bool (char * str). Str * Char è la stringa che stiamo spingendo nello stack, bool e dice solo se ci siamo riusciti o meno. 

Come non? Qual è l'unica circostanza che si può pensare di dove ci sarebbe bisogno di restituire false? Gia '. [Studente] Se è pieno e che stiamo usando una applicazione limitata. Sì, così come si definiscono, ha risposto se è pieno e stiamo utilizzando una implementazione limitata. Poi ci ritorneremo sicuramente false. Non appena abbiamo raggiunto 10 cose nella matrice, non può andare bene 11, in modo da restituire false. E se è illimitato? Gia '. Se non è possibile espandere l'array per qualche motivo. Sì, così la memoria è una risorsa limitata, e alla fine, se le cose che spingono nello stack più e più volte, stiamo andando a cercare di allocare un array più grande per adattarsi la maggiore capacità, e malloc o qualsiasi altra cosa che stiamo usando sta per restituire false. Beh, malloc restituirà null. 

Ricordate, ogni volta che si chiama malloc mai, si dovrebbe controllare per vedere se restituisce null oppure che è una deduzione correttezza. Dal momento che vogliamo avere uno stack illimitato, l'unico caso abbiamo intenzione di tornare false è se cerchiamo di aumentare la capacità e malloc o qualsiasi altra cosa restituisce false. Poi pop non accetta argomenti, e restituisce la stringa che è in cima alla pila. Qualunque è stato recentemente inserito nello stack è quello pop sta tornando, ed è anche lo rimuove dalla pila. E notare che restituisce null se non c'è niente in pila. E 'sempre possibile che la pila è vuota. In Java, se siete abituati a questo, o altre lingue, cercando di pop da uno stack vuoto può causare un'eccezione o qualcosa del genere. 

Ma in C, null è una specie di sacco di casi come gestire questi problemi. Tornando nulla è come stiamo andando a significare che la pila è vuota. Abbiamo messo a disposizione il codice che metterà alla prova la funzionalità del vostro stack, implementare push e pop. Questo non sarà un sacco di codice. Lo farò-in realtà, prima di farlo, suggerimento, suggerimento- se non l'avete visto, malloc non è l'unica funzione che alloca la memoria per l'heap per voi. Ci sono una famiglia di funzioni alloc. Il primo è malloc, che siete abituati. Poi c'è calloc, che fa la stessa cosa come malloc, ma si azzererà tutto per voi. Se hai sempre voluto impostare tutto su null dopo mallocing qualcosa si dovrebbe avere appena usato calloc in primo luogo, invece di scrivere un ciclo for per azzerare l'intero blocco di memoria. 

Realloc è come malloc e ha un sacco di casi particolari, ma in fondo quello che fa è realloc ci vuole un puntatore che erano già stati assegnati. Realloc è la funzione che si desidera prestare attenzione a qui. Ci vuole un puntatore che era già stato restituito da malloc. Diciamo che si richiede da malloc un puntatore di 10 byte. Poi dopo ci si rende conto che fa per te 20 byte, così si chiama realloc su quel puntatore con 20 byte, e realloc copia automaticamente su tutto per voi. Se hai appena chiamato malloc di nuovo, come se avessi un blocco di 10 byte. Ora ho bisogno di un blocco di 20 byte, quindi se io malloc 20 byte, allora devo copiare manualmente nel corso dei 10 byte dalla prima cosa che nella seconda cosa e poi libera la prima cosa. Realloc si occuperà per voi. 

Si noti la firma sarà void *, che è solo restituendo un puntatore al blocco di memoria, poi void * ptr. Si può pensare di void * come un puntatore generico. In genere, non si tratta con void *, ma malloc restituisce un void *, e quindi è solo usato come questo è in realtà sarà un char *. Il * vuoto precedente che era stato restituito da malloc sta ora per essere passato a realloc, e quindi le dimensioni è il nuovo numero di byte che si desidera assegnare, in modo che il nuova capacità. Ti do un paio di minuti, e lo fa nel nostro spazio. Inizia con revisione 1. Ti ferma dopo circa spera abbastanza tempo per implementare spinta, e poi ti darò un altro break di fare pop. Ma in realtà non è che il codice molto a tutti. La maggior parte del codice è probabilmente la roba in espansione, l'espansione della capacità. Ok, nessuna pressione per essere completamente fatta, ma fino a quando ti senti come se fossi sulla strada giusta, questo è un bene. 

Qualcuno ha qualche codice che sentirsi a proprio agio con me, tirando verso l'alto? Si ', lo faro', ma qualcuno ha qualche codice che posso tirare su? Ok, si può avviare, salvarlo, qualunque cosa sia? Mi dimentico sempre quel passo. Ok, guardando spinta, vuoi spiegare il tuo codice? [Studente] Prima di tutto, ho aumentato la dimensione. Credo che forse avrei dovuto che-in ogni caso, ho aumentato la dimensione, e vedo se è inferiore alla capacità. E se è inferiore alla capacità, aggiungo alla matrice che abbiamo già. E se non lo è, ho la capacità di moltiplicare per 2, Io e riallocare l'array stringhe a qualcosa con una dimensione maggiore capacità ora. E poi, se non funziona, dico l'utente e restituire false, e se va bene, poi ho messo la stringa nel nuovo spot. 

[Rob B.] Si noti inoltre che abbiamo usato un operatore bit a bit bella qui da moltiplicare per 2. Ricordate, spostamento a sinistra sta andando sempre essere moltiplicato per 2. Spostamento a destra è diviso per 2 fino a quando si ricordi che significa dividere per 2 come in un intero diviso 2. Si potrebbe troncare un 1 qua e là. Ma spostamento a sinistra di 1 sta andando sempre essere moltiplicato per 2, meno che non si troppo pieno i limiti del numero intero, e quindi non sarà. Un commento lato. Mi piace fare, questo non sta andando a cambiare il codice qualsiasi modo, ma mi piace fare qualcosa di simile. In realtà sta per renderlo un po 'più a lungo. Forse questo non è il caso perfetto per mostrare questo, ma mi piace a dividerlo in questi blocchi di- Va bene, se questo accade se, poi ho intenzione di fare qualcosa, e quindi la funzione viene eseguita. Non ho bisogno di scorrere poi i miei occhi fino in fondo la funzione per vedere cosa succede dopo l'altro. E 'se questo se succede, allora ho appena ritorno. Essa ha anche il bel vantaggio aggiunto di ogni cosa al di là di questo è ora spostato a sinistra una volta. Non ho più bisogno di, se mai vicino ridicolmente lunghe code, allora quei 4 byte può aiutare, e anche la sinistra è qualcosa di più, meno sopraffatto vi sentireste se piace-va bene, devo ricordare Sono attualmente in un ciclo while all'interno di un altro all'interno di un ciclo for. Ovunque si può fare questo ritorno subito, ho un po 'come. E 'del tutto facoltativo e non previsto in alcun modo. 

[Studente] Dovrebbe esserci una dimensione - nella condizione di sicuro? La condizione di sicuro qui non siamo riusciti a realloc, quindi sì. Si noti come nella condizione di sicuro, presumibilmente, a meno che non roba gratuitamente più tardi, stiamo andando sempre a fallire non importa quante volte cerchiamo di spingere qualcosa. Se continuiamo a spingere, continuiamo a dimensione di incremento, anche se non mettono nulla in cima alla pila. Di solito non incrementare le dimensioni fino a dopo aver con successo messa in pila. Ci avrebbe fatto, per esempio, sia qui e qui. E poi invece di dire s.size capacità ≤, è inferiore alla capacità, solo perché ci siamo trasferiti dove tutto era. 

E ricordate, l'unico posto che potrebbe restituire false è qui, dove realloc restituito null, e se vi capita di ricordare errore standard, forse si potrebbe considerare questo un caso in cui si desidera stampare un errore standard, fprintf stderr così invece di stampare direttamente fuori standard. Anche in questo caso, non è una previsione, ma se si tratta di un errore, printf tipo, allora si potrebbe desiderare di farlo stampare errore standard, invece di standard out. 

Qualcuno ha altro da notare? Sì. [Studente] Si può andare oltre il [incomprensibile]? [Rob B.] Sì, la binariness reale di esso o semplicemente quello che è? [Studente] Quindi si moltiplica per 2? [Rob B.] Si ', in fondo. In terra binario, abbiamo sempre la nostra serie di cifre. Spostando questa sinistra di 1 fondamentalmente inserisce qui sul lato destro. Torna a questa, anche per ricordare che tutto in binario è una potenza di 2, quindi questo rappresenta 2 a 0, questo 2 alla 1, questo 2 al 2. Con l'inserimento di uno 0 a destra ora, dobbiamo solo spostare tutto finito. Quello che prima era 2 a 0 è ora la 2 alla 1, è 2 al 2. Il lato destro che abbiamo inserito è necessariamente sarà 0, che ha un senso. Se mai moltiplicare un numero per 2, non sta andando a finire dispari, così il 2 al posto 0 deve essere 0, e questo è quello che ho avvertito mezzo circa prima è che se vi capita di passare oltre il numero di bit in un numero intero, allora questo 1 sta per finire andare fuori. Questa è l'unica preoccupazione se vi capita di avere a che fare con capacità davvero di grandi dimensioni. Ma a quel punto, allora hai a che fare con una serie di miliardi di cose, che non potrebbe andare bene nella memoria in ogni caso. 

Ora siamo in grado di arrivare al pop, che è ancora più facile. Si potrebbe ti piace se vi capita di pop un intero gruppo, e ora sei a metà della capacità di nuovo. Si potrebbe realloc per ridurre la quantità di memoria disponibile, ma non devi preoccuparti di questo, quindi il caso realloc solo sta per essere crescente di memoria, mai restringimento memoria, che sta andando a fare super-pop facile. Ora le code, che stanno per essere come pile, ma l'ordine di prendere le cose è invertita. L'esempio tipico di una coda è una linea, quindi suppongo che se tu fossi inglese, avrei detto un esempio tipico di una coda è una coda. Così come una linea, se sei la prima persona in linea, ci si aspetta di essere la prima persona fuori dalla linea. Se tu sei l'ultima persona in linea, che si sta per essere l'ultima persona a manutenzione. Noi chiamiamo questo modello FIFO, mentre la pila era motivo LIFO. Queste parole sono abbastanza universali. 

Come pile e, a differenza di matrici, le code di solito non consentono l'accesso agli elementi nel mezzo. Qui, una pila, abbiamo push e pop. Qui, ci capita di li hanno chiamati enqueue e dequeue. Ho anche sentito li chiamava turno e unshift. Ho sentito dire push e pop di applicare anche alle code. Ho sentito inserire, rimuovere, così push e pop, se si parla di pile, si sta spingendo e popping. Se si parla di code, è possibile scegliere le parole che si desidera utilizzare per l'inserimento e la rimozione, e non c'è consenso su ciò che dovrebbe essere chiamato. Ma qui, abbiamo enqueue e dequeue. Ora, la struttura sembra quasi identico al struct stack. Ma dobbiamo tenere traccia di testa. Credo che si dice qui, ma perché abbiamo bisogno della testa? I prototipi sono sostanzialmente identiche a push e pop. Si può pensare ad esso come push e pop. L'unica differenza è pop-sta tornando invece dell'ultima, è il primo ritorno. 2, 1, 3, 4, o qualcosa. Ed ecco l'inizio. La coda è completamente pieno, quindi ci sono quattro elementi in esso. La fine della nostra coda è attualmente 2, e adesso andiamo a inserire qualcosa d'altro. 

Quando vogliamo inserire qualcosa d'altro che, quello che abbiamo fatto per la versione dello stack è abbiamo prolungato il nostro blocco di memoria. Qual è il problema con questo? [Studente] Si sposta il 2. Quello che ho detto prima circa la fine della coda, questo non ha senso che partono da 1, poi vogliamo dequeue 1, poi dequeue 3, quindi dequeue 4, poi dequeue 2, quindi annullare l'accodamento questo. Non possiamo usare realloc ora, o per lo meno, bisogna usare realloc in modo diverso. Ma probabilmente non basta usare realloc. Si sta andando ad avere per copiare manualmente la memoria. 

Ci sono due funzioni per copiare la memoria. C'è memcopy e memmove. Attualmente sto leggendo le pagine man per vedere quale si sta andando a voler utilizzare. Ok, memcopy, la differenza è che memcopy e memmove, uno gestisce il caso correttamente dove si sta copiando in una regione che sembra sovrapporsi alla regione si sta copiando dal. Memcopy non gestire la cosa. Memmove fa. Si può pensare il problema come- diciamo che voglio copiare questo ragazzo, questi quattro a questo tizio. Alla fine, quello che la matrice dovrebbe essere simile dopo la copia è 2, 1, 2, 1, 3, 4, e quindi alcune cose alla fine. Ma questo dipende dall'ordine in cui effettivamente copiare, poiché, se non consideriamo il fatto che la regione che stiamo copiando in sovrappone quello che sta copiando dal, allora potremmo fare come inizio qui, copiare il 2 nel luogo che vogliamo andare, quindi spostare in avanti i nostri puntatori. 

Ora stiamo andando a essere qui e qui, e ora vogliamo copiare questo ragazzo su questo ragazzo e andare avanti i nostri puntatori. Quello che stiamo andando a finire per ottenere è 2, 1, 2, 1, 2, 1 invece del caso 2, 1, 2, 1, 3, 4 perché 2, 1 sovrascritto originale 3, 4. Memmove gestisce che correttamente. In questo caso, in fondo basta usare sempre memmove perché lo gestisce correttamente. E 'in genere non esegue peggio. L'idea è invece di partire dall'inizio e copiare questo modo come abbiamo appena fatto qui, inizia dalla fine e in copia, e in tal caso, non si può mai avere un problema. Non vi è alcun prestazioni perse. Utilizzare sempre memmove. Non preoccuparti memcopy. Ed è lì che si sta andando ad avere per memmove separatamente l'avvolgi parte della coda. Nessun problema se non completamente fatto. Questo è più difficile di pila, push e pop. 

Qualcuno ha qualche codice che potrebbe lavorare con? Anche se del tutto incompleta? [Studente] ', e' del tutto incompleto, però. Completamente incompleta va bene fintanto che-si può risparmiare la revisione? Mi dimentico che ogni singola volta. Ok, ignorando ciò che succede quando abbiamo bisogno di ridimensionare le cose. Completamente ignorare ridimensionamento. Spiega questo codice. Sto controllando prima di tutto se la dimensione è minore della prima copia di tutti e poi, dopo che, inserisco-prendo la testa + dimensioni, e assicurarsi che avvolge la capacità della matrice, e inserire la nuova stringa in quella posizione. Poi aumentare la dimensione e restituire true. 

[Rob B.] Questo è sicuramente uno di quei casi in cui si sta andando a voler utilizzare mod. Qualsiasi tipo di caso in cui avete avvolgono, se pensi che avvolgono, il primo pensiero dovrebbe essere mod. Come ottimizzazione rapida / rendere il codice una linea più breve, si nota che la linea subito dopo questo è solo dimensione + +, in modo che si uniscono in questa linea, le dimensioni + +. Ora qui, abbiamo il caso dove non si dispone di memoria sufficiente, quindi stiamo aumentando la nostra capacità di 2. Credo che si potrebbe avere lo stesso problema qui, ma siamo in grado di ignorare ora, dove se non siete riusciti a aumentare la capacità, allora si sta andando a voler diminuire la capacità di 2 nuovo. Un'altra breve nota è proprio come si può fare + =, si può anche fare << =. Quasi tutto può andare prima uguale, + =, | =, & =, << =. Char * nuovo è il nostro nuovo blocco di memoria. Oh, da questa parte. 

Che cosa la gente pensa il tipo del nostro nuovo blocco di memoria? [Studente] Dovrebbe essere char **. Ripensando alla nostra struttura qui, stringhe è quello che stiamo riallocazione. Facciamo un intero nuovo storage dinamico per gli elementi nella coda. Quello che sta andando ad essere l'assegnazione alle vostre stringhe è quello che stiamo mallocing in questo momento, e tanto nuova, sta per essere un char **. E 'intenzione di essere un array di stringhe. Allora qual è il caso in cui abbiamo intenzione di restituire false? [Studente] Dovremmo fare il char *? [Rob B.] Sì, buona chiamata. [Studente] Che cos'era? [Rob B.] Abbiamo voluto fare il formato di char *, perché non siamo più- questo sarebbe in realtà un problema molto grande perché sizeof (char) sarebbe 1. Sizeof char * sta per essere 4, così un sacco di volte in cui vi state occupando interi, si tende a farla franca perché la dimensione di int e la dimensione del int * su un sistema a 32 bit stanno per essere la stessa cosa. Ma qui, sizeof (char) e sizeof (char *) sono ora sarà la stessa cosa. 

Qual è la circostanza in cui si ritorna falso? [Studente] Nuovo è nullo. Si ', se nuovo è nullo, torniamo falso, e ho intenzione di buttare giù qui- [Studente] [incomprensibile] [Rob B.] Sì, questo va bene. Si potrebbe o fare 2 volte la capacità o turno di capacità 1, quindi solo impostare qui o qualsiasi altra cosa. Lo faremo come abbiamo avuto. Capacità >> = 1. E non si è mai costretta a preoccuparsi di perdere gli 1 posto perché te ne sei andato spostata di 1, per cui gli 1 posto è necessariamente uno 0, così giusto spostamento di 1, si sta ancora andando bene. [Studente] Avete bisogno di fare prima di ritorno? [Rob B.] Sì, questo non ha assolutamente senso. 

Supponiamo ora che stiamo andando a finire tornando true alla fine. Il modo in cui andremo a fare queste memmoves, dobbiamo stare attenti a come li fanno. Qualcuno ha qualche suggerimento per come li fanno? Ecco il nostro inizio. Inevitabilmente, vogliamo cominciare dall'inizio di nuovo e le cose in copia da lì, 1, 3, 4, 2. Come si fa a fare questo? In primo luogo, devo guardare la pagina man per memmove nuovo. Memmove, ordine degli argomenti è sempre importante. Vogliamo che la nostra prima destinazione, la seconda fonte, la terza dimensione. Ci sono molte funzioni che invertono sorgente e destinazione. Destinazione, sorgente tende ad essere alquanto coerente. Move, cosa sta tornando? Esso restituisce un puntatore a destinazione, per qualsiasi motivo si potrebbe desiderare che. Posso immaginare leggerlo, ma vogliamo andare nella nostra destinazione. 

Che cosa è la nostra destinazione sarà? [Studente] Nuovo. [Rob B.] Sì, e dove stiamo copiando? La prima cosa che la copia è questo 1, 3, 4. Qual è il presente-1, 3, 4. Qual è l'indirizzo di questo 1? Qual è l'indirizzo del 1? [Studente] [incomprensibile] [Rob B.] Testa + l'indirizzo del primo elemento. Come si ottiene il primo elemento della matrice? [Studente] coda. [Rob B.] Sì, q.strings. Ricordate, qui, la nostra testa è 1. Dannazione. Penso solo che sia magicamente- Qui, la nostra testa è 1. Ho intenzione di cambiare il mio colore troppo. Ed ecco le stringhe. Questo, si può scrivere come abbiamo fatto qui con la testa + q.strings. Un sacco di gente anche scrivi & q.strings [testa]. Questo non è davvero meno efficiente. Si potrebbe pensare a come lo si dereferenziazione e quindi ottenere l'indirizzo, ma il compilatore sta per tradurlo a quello che avevamo prima in ogni caso, q.strings + testa. In entrambi i casi si vuole pensarci bene. 

E il numero di byte vogliamo copiare? [Studente] Capacità - testa. Capacità - testa. E poi si può sempre scrivere un esempio di capire se è vero. [Studente] Ha bisogno di essere diviso per 2 allora. Gia ', quindi credo che abbiamo potuto usare dimensioni. Abbiamo ancora dimensioni dell'essere- utilizzando dimensioni, abbiamo dimensioni pari a 4. La nostra dimensione è 4. La nostra testa è 1. Vogliamo copiare questi 3 elementi. Questo è il test di integrità che le dimensioni - testa è correttamente 3. E tornare qui, come abbiamo detto prima, se abbiamo usato la capacità, allora avremmo dovuto dividere per 2 perché abbiamo già cresciuta la nostra capacità, così, invece, abbiamo intenzione di utilizzare dimensioni. Che le copie porzione. Ora, abbiamo bisogno di copiare l'altra parte, la parte che è a sinistra della partenza. 

Che sta per memmove in quale posizione? [Studente] Plus size - testa. Sì, per questo abbiamo già copiato in dimensioni - byte di testa, e così dove vogliamo copiare i byte rimanenti è nuovo e poi meno bene-formato, il numero di byte che abbiamo già copiato trovi E poi dove stiamo copiando? [Studente] Q.strings [0]. [Rob B.] Sì, q.strings. Si potrebbe o fare e q.strings [0]. Questo è molto meno comune di questo. Se è solo andare a essere 0, allora si tende a vedere q.strings. Ecco dove stiamo copiando da. Quanti byte ci hanno lasciato di copiare? >> [Studente] 10. Giusto. [Studente] Dobbiamo moltiplicare 5 - 10 volte la dimensione dei byte o qualcosa del genere? Gia ', quindi questo è dove-cosa esattamente stiamo copiando? [Studente] [incomprensibile] Qual è il tipo di cosa che stiamo copiando? [Studente] [incomprensibile] Gia ', in modo che il char * s che stiamo copiando, non sappiamo dove questi sono provenienti da. Beh, dove stanno indicando, come le corde, si finisce per spingerlo nella coda o Accodamento nella coda. Se quelli sono provenienti da, non abbiamo idea. Abbiamo solo bisogno di tenere traccia del char * s stessi. Non vogliamo copiare dimensioni - byte testa. Vogliamo copiare dimensioni - testa char * s, quindi stiamo andando a moltiplicare questo per sizeof (char *). Stesso qui, testa * sizeof (char *). 

[Studente] E [incomprensibile]? Questo qui? [Studente] No, al di sotto, la dimensione - testa. [Rob B.] Questo qui? Puntatore aritmetica. Come l'aritmetica dei puntatori è andare a lavorare è moltiplica automaticamente dalla dimensione del tipo che si sta trattando. Proprio come qui, nuovo + (dimensione - testa) è esattamente equivalente a & [size - testa] nuovo fino a quando ci aspettiamo che per funzionare correttamente, poiché, se abbiamo a che fare con una serie int, allora non vengono indicizzati da int- o se è di dimensioni di 5 e si desidera che il 4 ° elemento, poi indice nella int array [4]. Tu non fare-[4] * dimensione di int. Che gestisce automaticamente, e questo caso è letteralmente equivalente, quindi la staffa sintassi è solo andare a essere convertiti in questo non appena si compila. Questo è qualcosa che è necessario stare attenti a che quando si aggiungono dimensioni - testa non si sta aggiungendo un byte. Stai aggiungendo un char *, che può essere uno byte o qualsiasi altra cosa. 

Altre domande? Ok, dequeue sarà più facile. Ti do un minuto per l'attuazione. Oh, e credo che questa è la stessa situazione in cui ciò che il caso enqueue, se siamo enqueuing null, forse si vuole gestire la cosa, forse non lo facciamo. Non lo farò più qui, ma come il nostro caso stack. Se accodare nullo, si potrebbe desiderare di non tenerne conto. Qualcuno ha qualche codice che posso tirare su? [Studente] Devo solo dequeue. La versione 2 è che, va bene. Vuoi spiegare? [Studente] In primo luogo, assicurarsi che non ci sia qualcosa nella coda e che la dimensione sta andando giù di 1. Hai bisogno di fare questo, e poi si torna alla testa e quindi spostare la testa 1. Ok, quindi non c'è un caso d'angolo dobbiamo considerare. Gia '. [Studente] Se la tua testa è l'ultimo elemento, allora non si vuole la testa al punto al di fuori della matrice. 

Gia ', quindi non appena testa colpisce il fine del nostro array, quando dequeue, la nostra testa deve essere modded a 0. Purtroppo, non possiamo farlo in un solo passaggio. Credo che il modo in cui probabilmente sarei risolvere il problema è questo sta andando essere un char *, quello che stiamo tornando, qualunque sia il tuo nome di variabile vuole essere. Poi vogliamo mod testa con la nostra capacità e poi tornare ret. Un sacco di gente qui si potrebbe fare- questo è il caso di e avrete modo di vedere le persone fare se la testa è superiore alla capacità, non testa - capacità. E questo è solo lavorando attorno a ciò che è mod. Capacità di testa mod = è molto più pulito di un involucro intorno a se la testa più grande di testa Capacità - capacità. 

Domande? Ok, l'ultima cosa che ci resta è la nostra lista concatenata. Potrebbe essere usato per alcuni comportamenti lista collegata se l'avete fatto liste collegate nelle tabelle hash, se avete fatto una tabella hash. Consiglio vivamente a fare una tabella di hash. Si potrebbe avere già fatto un trie, ma tentativi sono più difficili. In teoria, sono asintoticamente migliore. Ma basta guardare il tabellone, e cerca di non fare di meglio, e occupano più memoria. Tutto cerca sulla finisce per essere peggiore per più lavoro. E 'quello che la soluzione di David Malan è sempre E 'sempre la sua soluzione messaggi trie, e vediamo dove si trova attualmente. Quello che era sotto, David J? E '# 18, in modo che non è terribilmente male, e che sarà uno dei migliori prova si può pensare o uno dei migliori cerca di un trie. Non è forse anche la sua soluzione originale? Mi sento come soluzioni trie tendono ad essere più in questo range di utilizzo della RAM. 

Scendete fino alla cima, e utilizzo della RAM è in una sola cifra. Si scende verso il basso, e quindi si cerca di iniziare a vedere dove si ottiene l'utilizzo di RAM assolutamente enormi, e tentativi sono più difficili. Non del tutto, ma ne vale la pena un'esperienza educativa se l'avete fatto uno. L'ultima cosa è la nostra lista collegata, e queste tre cose, pile, code e liste concatenate, qualsiasi cosa futura che mai fare in informatica si suppone che si abbia familiarità con queste cose. Sono solo così fondamentale a tutto. 

Liste collegate, e qui abbiamo una lista concatenata semplice sarà la nostra implementazione. Cosa vuol dire semplicemente concatenata al contrario di doppio collegamento? Sì. [Studente] Essa sottolinea solo l'indicatore accanto piuttosto che i puntatori, come quello che lo precede e quello dopo. Si ', quindi in formato immagine, che cosa ho fatto? Ho due cose. Ho immagini e foto. In formato immagine, le nostre liste semplicemente concatenate, inevitabilmente, abbiamo una sorta di puntatore alla testa della nostra lista, e poi all'interno della nostra lista, dobbiamo solo puntatori, e forse questo punti a null. E 'intenzione di essere il vostro disegno tipico di una lista concatenata. Una lista doppiamente concatenata, è possibile tornare indietro. Se io ti do un nodo nella lista, allora si può necessariamente arrivare a qualsiasi altro nodo della lista, se si tratta di una lista doppiamente concatenata. Ma se si ottiene il terzo nodo della lista ed è una lista concatenata semplice, nessun modo si sta mai riusciti ad ottenere ai nodi prima e la seconda. E ci sono vantaggi e gli svantaggi, e uno più evidente vi occupano più dimensioni, e si deve tenere traccia di dove queste cose siano rivolte ora. Ma ci preoccupiamo soltanto concatenata. 

Un paio di cose che stiamo andando ad avere per l'attuazione. Il nodo typedef struct, int i: struct nodo * next; nodo. Questo typedef dovrebbe essere bruciato nelle vostre menti. Quiz 1 dovrebbe essere come dare un typedef di un nodo lista collegata, e si dovrebbe essere in grado di scarabocchiare subito che verso il basso senza nemmeno pensarci. Credo che un paio di domande, perché abbiamo bisogno di struct qui? Perché non possiamo dire * nodo? [Studente] [incomprensibile] Gia '. L'unica cosa che definisce un nodo come cosa è la stessa typedef. Ma a partire da questo punto, quando siamo un po 'di analisi attraverso questa definizione del nodo struct, non abbiamo ancora finito il nostro typedef ancora, quindi in quanto il typedef non ha finito, nodo non esiste. Ma struct nodo fa, e questo nodo qui, questo potrebbe anche essere chiamato qualsiasi altra cosa. Questo potrebbe essere chiamato n. Si potrebbe definire il nodo lista collegata. Si potrebbe definire nulla. Ma questo nodo struct deve essere chiamata la stessa cosa di questo nodo struct. Quello che tu chiami questo deve essere anche qui, e così che risponde anche al secondo punto della questione ed è per questo, un sacco di volte quando si vede le strutture e typedef di strutture, vedrete le strutture anonime in cui si vedrà solo typedef struct, attuazione di struct, dizionario, o qualsiasi altra cosa. 

Perché qui abbiamo bisogno di dire nodo? Perché non può essere una struttura anonima? E 'quasi la stessa risposta. [Studente] È necessario fare riferimento ad esso all'interno della struttura. Sì, all'interno della struttura, è necessario fare riferimento alla stessa struttura. Se non si danno la struttura un nome, se si tratta di una struttura anonima, non è possibile fare riferimento ad esso. E, ultimo ma non meno importante, questi devono essere tutti un po 'semplice, e dovrebbero aiutare a capire se si sta scrivendo questo in giù che si sta facendo qualcosa di sbagliato, se questo genere di cose non hanno senso. Ultimo ma non meno importante, perché questo deve essere il nodo struct *? Perché non può essere solo struct nodo successivo? [Studente] puntatore alla struttura successiva. Questo è inevitabilmente quello che vogliamo. Perché non potrebbe mai essere nodo struct prossimo? Perché deve essere struct nodo * prossimo? Gia '. [Studente] E 'come un ciclo infinito. Gia '. [Studente] Sarebbe tutto in uno. Si ', solo pensare a come avremmo fatto dimensioni o qualcosa del genere. Dimensioni di una struttura è fondamentalmente + o - qualche modello qui o là. E 'fondamentalmente sarà la somma delle dimensioni delle cose nella struttura. Questo qui, senza cambiare nulla, la dimensione sarà facile. Dimensione del nodo struct sarà dimensioni di grandezza i + del prossimo. Dimensioni i sta per essere 4. Dimensioni del prossimo sarà 4. Dimensione del nodo struct sarà 8. Se noi non abbiamo il *, pensando a sizeof, poi sizeof (i) sta per essere 4. Dimensione del nodo struct prossimo sarà dimensioni di i + tipo di struct nodo successivo Dimensioni + di + i dimensioni del nodo struct prossimo. Sarebbe una ricorsione infinita di nodi. Ecco perché è così che le cose devono essere. 

Ancora una volta, che sicuramente memorizzare, o almeno capire abbastanza che si può essere in grado di ragionare su quello che dovrebbe essere simile. Le cose che stiamo andando a voler implementare. Se la lunghezza della lista- si può imbrogliare e mantenere intorno a un lunghezza globale o qualcosa del genere, ma non abbiamo intenzione di farlo. Stiamo andando a contare la lunghezza della lista. Abbiamo contiene, così che è fondamentalmente come una ricerca, quindi abbiamo una lista concatenata di interi per vedere se questo intero è nella lista collegata. Prepend sta per inserire all'inizio della lista. Append sta per inserire alla fine. Insert_sorted sta per inserire nella posizione ordinati nell'elenco. Insert_sorted di tipo presuppone che non hai mai usato anteporre o aggiungere in modo cattivo. 

Insert_sorted quando si sta implementando insert_sorted- diciamo che abbiamo la nostra lista collegata. Questo è ciò che appare attualmente come, 2, 4, 5. Voglio inserire 3, quindi, purché la stessa lista è già ordinato, è facile trovare dove 3 appartiene. Comincio a 2. Ok, 3 è maggiore di 2, quindi voglio andare avanti. Oh, 4 è troppo grande, quindi so 3 è per andare tra 2 e 4, e devo sistemare puntatori e tutta quella roba. Ma se non utilizzare esclusivamente insert_sorted, come diciamo solo che antepongo 6, allora la mia lista concatenata sta per diventare tale. Si rende ora non ha senso, quindi per insert_sorted, si può solo supporre che l'elenco è ordinato, anche se le operazioni di esistere che può causare a non essere ordinati, e questo è tutto. Trova un utile inserto-so queste sono le cose principali che si sta andando ad avere per l'attuazione. 

Per ora, un minuto per fare lunghezza e contiene, e quelli dovrebbe essere relativamente veloce. Avvicinandosi orario di chiusura, in modo che chiunque ha niente per la lunghezza o contiene? Stanno per essere quasi identici. [Studente] Lunghezza. Vediamo, revisione. Va bene. Vuoi spiegare? [Studente] Ho appena creato un nodo puntatore e inizializzarla al primo, che è la nostra variabile globale, e poi controllare per vedere se è nullo, quindi non si ottiene un errore di segmento e restituire 0 se questo è il caso. In caso contrario, io loop through, tenendo traccia di dentro intero quante volte ho l'accesso al successivo elemento della lista e nella stessa operazione di incremento anche accedere all'elemento reale, e poi ho sempre fare il controllo per vedere se è nullo, e se è nullo, poi interrompe e restituisce il numero di elementi che ho accesso. 

[Rob B.] Qualcuno ha qualche commento su qualcosa? Questo sembra correttezza bene saggio. [Studente] Non credo che ti serve il nodo == null. Si ', per cui se il nodo == 0 ritorno null. Ma se il nodo == null allora questo-oh, c'è un problema di correttezza. Era solo sei i ritorno, ma non è portata in questo momento. Hai solo bisogno di int i, in modo da i = 0. Ma se il nodo è nullo, allora i è ancora in corso di essere 0, e abbiamo intenzione di restituire 0, quindi questo caso è identico. Un'altra cosa comune è quello di ottenere la dichiarazione all'interno del nodo del ciclo for. Si potrebbe dire-oh, no. Teniamo come questo. Io probabilmente messo int i = 0 qui, quindi il nodo * nodo = prima qui. E questo è probabilmente il modo-sbarazzarsi di questo ora. Questo è probabilmente il modo avrei scritto. Si potrebbe anche, guardando in questo modo. Questo per struttura ad anello qui dovrebbe essere quasi naturale per voi come per int i = 0 i è minore lunghezza di array i + +. Se questo è il modo di eseguire iterazioni su un array, questo è il modo per scorrere una lista concatenata. 

Questo dovrebbe essere una seconda natura ad un certo punto. Con questo in mente, questa sarà quasi la stessa cosa. Stai andando a voler scorrere una lista concatenata. Se il nodo-non ho idea di quale sia il valore viene chiamato. Nodo i. Se il valore in quel nodo = i return true, e questo è tutto. Si noti che l'unico modo che abbiamo mai restituire false è se scorrere l'intera lista collegata e non tornare mai più vero, ed è quello che fa questo. Come nota a margine, probabilmente non si arriva a aggiungere o anteporre. 

Rapido ultima nota. Se si vede la parola chiave static, quindi diciamo static int count = 0, poi contano + +, si può sostanzialmente pensare ad esso come una variabile globale, anche se ho appena detto non è così che stiamo andando a implementare lunghezza. Lo sto facendo qui, e poi contare + +. In ogni modo siamo in grado di entrare in un nodo nella nostra lista collegata stiamo incrementando il nostro conteggio. Il punto di questo è ciò che significa la parola chiave static. Se ho appena avuto int count = 0 che sarebbe un normale vecchia variabile globale. Nei mezzi static int conta è che è una variabile globale per questo file. E 'impossibile per un altro file, piace pensare di pset 5, se avete iniziato. Avete entrambi speller.c, e si dispone di dictionary.c, e se si dichiara una cosa globale, allora qualcosa in speller.c si può accedere in dictionary.c e viceversa. Le variabili globali sono accessibili da qualsiasi file. C, ma le variabili statiche sono accessibili solo all'interno del file stesso, così all'interno del correttore ortografico o all'interno di dictionary.c, questo è una specie di come mi avrebbe dichiarato la mia variabile per la dimensione della mia matrice o le dimensioni del mio numero di parole nel dizionario. Dal momento che non desidera dichiarare una variabile globale che chiunque abbia accesso a, Mi interessa solo per i miei scopi. 

La cosa buona di questo è anche tutto il materiale conflitto di nomi. Se qualche altro file tenta di utilizzare una variabile globale chiamata conte, le cose vanno molto, molto male, quindi questo mantiene bene le cose al sicuro, e solo vi si possa accedere, e nessun altro può, e se qualcun altro dichiara una variabile globale chiamata conteggio, allora non interferirà con la variabile statica denominata conteggio. Questo è ciò che è statico. Si tratta di una variabile file globale. 

Domande su qualsiasi cosa? Tutto pronto. Bye. [CS50.TV]