[RIPRODUZIONE DI BRANI MUSICALI]
SPEAKER 1: Va bene.
Tutti bentornato alla sezione.
Spero che tutti voi siete con successo recuperato il quiz
dalla settimana scorsa.
Lo so che è un po 'matti, a volte.
Come dicevo prima, se siete all'interno della deviazione standard,
in realtà non ti preoccupare, in particolare per una sezione meno confortevole.
Ecco di dove si dovrebbe essere.
>> Se avete fatto grande, quindi impressionante.
Complimenti a voi.
E se si sente come avete bisogno un po 'più di aiuto, si prega di
sentitevi liberi di raggiungere fuori su qualsiasi TF.
Siamo tutti qui per aiutare.
>> È per questo che insegniamo.
È per questo che sono qui ogni Lunedi per voi ragazzi e presso l'ufficio ore il giovedì.
Quindi, non esitate a farmi sapere se siete preoccupati di nulla
o se c'è qualcosa sul quiz che vuoi davvero ad affrontare.
>> Quindi, l'ordine del giorno di oggi è Tutto su strutture dati.
Alcuni di questi sono solo andando a essere solo per farti familiarizzare con questi.
L'utente non può mai realizzare li in questa classe.
Alcuni di loro si vuole, come per il vostro pset correttore ortografico.
>> Avrete la vostra scelta tra le tabelle hash e tentativi.
Quindi dovremo sicuramente andando su quelli.
E sarà sicuramente più di tipo di una sezione di alto livello oggi, però,
perché ci sono un sacco di loro, e se siamo andati nei dettagli di implementazione
in tutti questi, non sarebbe anche ottenere attraverso liste collegate
e forse un po 'di tabelle hash.
>> Quindi abbiate pazienza con me.
Non stiamo andando a fare tanto codifica questa volta.
Se avete domande su di esso o se si vuole vederlo implementato
o provare di persona, Lo consiglio vivamente
andare a study.cs50.net, che ha esempi di tutti questi.
Avrà miei PowerPoint con le note che abbiamo
tendono ad usare così come alcuni di programmazione esercizi, soprattutto per le cose
come liste concatenate e binario alberi pile e spunti.
Così poco livello più alto, che potrebbe essere bello per voi ragazzi.
>> Quindi, con questo, noi di iniziare.
E anche, quiz yes--.
Penso che la maggior parte di voi che sono in la mia sezione hanno i tuoi quiz,
ma chiunque viene in o qualche motivo non lo fanno, sono proprio qui di fronte.
>> Quindi collegate liste.
So che questo tipo di va per eseguire prima il quiz.
Questa è stata la settimana prima che abbiamo imparato a conoscere questo.
Ma in questo caso, ci limiteremo a andare un po 'più in profondità.
>> Quindi perché potremmo scegliere un linked list su un array?
Che cosa li distingue?
Sì?
>> PUBBLICO: È possibile espandere un collegato Elenco e dimensione fissa di un array.
SPEAKER 1: Giusto.
Un array ha dimensione fissa, mentre un lista collegata ha una dimensione variabile.
Quindi, se noi non sappiamo come tanto che vogliamo memorizzare,
una lista concatenata ci dà una grande modo per farlo, perché possiamo solo
aggiungere su un altro nodo e aggiungere su un altro nodo e aggiungere su un altro nodo.
Ma quello che potrebbe essere un trade-off?
Qualcuno ricorda il trade-off tra array e liste collegate?
Mmhmm?
>> PUBBLICO: Devi passare attraverso tutto il percorso
attraverso la lista collegata trovare un elemento in un elenco.
In una matrice, è possibile basta trovare un elemento.
>> SPEAKER 1: Giusto.
Quindi, con arrays--
>> PUBBLICO: [incomprensibile].
>> SPEAKER 1: Con gli array, abbiamo quello che chiama ad accesso casuale.
Significa che se vogliamo ciò che è mai il quinto punto di un elenco
o il quinto punto del nostro array, si può semplicemente afferrarlo.
Se si tratta di una lista collegata, abbiamo per scorrere, giusto?
Quindi l'accesso a un elemento in un array è tempo costante,
mentre con una lista collegata che sarebbe molto probabilmente il tempo lineare perché forse
nostro elemento è fino alla fine.
Abbiamo per la ricerca in tutto.
Quindi, con tutti questi dati strutture che andremo
di spendere un po 'di tempo su, quali sono i vantaggi e negativi.
Quando si potrebbe desiderare di utilizzare uno sopra l'altro?
E questo è il tipo di cosa più grande da portare via.
>> Quindi, abbiamo qui la definizione di un nodo.
È come un elemento la nostra lista collegata, giusto?
Quindi siamo tutti a conoscenza con i nostri struct typedef,
che siamo andati oltre in rassegna l'ultima volta.
E 'stato fondamentalmente solo la creazione di altro tipo di dati che potremmo usare.
>> E in questo caso, è qualche nodo che si terrà in qualche intero.
E allora qual è la seconda parte qui?
Chiunque?
>> PUBBLICO: [incomprensibile].
>> SPEAKER 1: Sì.
E 'un puntatore al nodo successivo.
Quindi questo dovrebbe in realtà essere qui.
Questo è un puntatore di tipo nodo per la prossima cosa.
E questo è quello che comprende il nostro nodo.
Freddo.
>> Va bene, quindi con la ricerca, come eravamo solo dicendo prima mano, se siete
andando per la ricerca in, si deve in realtà iterare
attraverso la vostra lista collegata.
Quindi, se stiamo cercando il numero 9, vorremmo iniziare alla nostra testa
e che ci punti all'inizio della nostra lista collegata, giusto?
E noi diciamo, OK, lo fa nodo contiene il numero 9?
No?
>> Va bene, andare a quella successiva.
Seguirla.
Contiene il numero 9?
No.
Seguire il prossimo.
>> Quindi dobbiamo realmente iterare attraverso la lista collegata.
Non possiamo andare direttamente al punto in cui 9 è.
E se voi ragazzi vuole realmente vedere alcuni pseudo-codice lassù.
Abbiamo qualche funzione di ricerca qui che prende dentro-- cosa ci vuole a?
Cosa ne pensi?
Così facile.
Cos'è questo?
PUBBLICO: [incomprensibile].
SPEAKER 1: Il numero che stiamo cercando.
Giusto?
E quale sarebbe questo corrispondere a?
E 'un puntatore a?
>> PUBBLICO: Un nodo.
>> SPEAKER 1: Un nodo alla lista che stiamo guardando, giusto?
Così abbiamo alcuni nodi sono puntatore qui.
Questo è un punto che sta per in realtà scorrere la nostra lista.
Abbiamo impostato uguale a elencare perché questo è solo
porla uguale inizio della nostra lista collegata.
>> E mentre non è NULL, mentre abbiamo ancora cose nella nostra lista,
controllare per vedere se quel nodo ha il numero che stiamo cercando.
Restituisce vero.
In caso contrario, l'aggiornamento, giusto?
>> Se è NULL, usciamo il nostro ciclo while e restituire false
perché significa che non abbiamo trovato.
Ricevono tutti come funziona?
Ok.
>> Quindi, con l'inserimento, è hanno tre modi diversi.
È possibile anteporre, è possibile aggiungere ed è possibile inserire in colori assortiti.
In questo caso, siamo intenzione di fare un anteporre.
Qualcuno sa come quelli tre casi potrebbero differire?
>> Così anteporre significa che si mette nella parte anteriore della vostra lista.
Quindi, ciò significherebbe che non importa ciò che il nodo è, non importa
che cosa è il valore, si sta andando per dirla proprio qui di fronte, OK?
Sta andando essere il primo elemento nella lista.
>> Se si aggiunge che, sta andando per andare sul retro della vostra lista.
E inserire assortiti significa che siete andando a mettere realmente nel luogo
dove si mantiene la vostra lista concatenata ordinata.
Anche in questo caso, come si usa chi e quando si utilizza
essi variano a seconda del caso.
Se non deve da ordinare, anteporre tende
di essere ciò che la maggior parte delle persone utilizzare perché non lo fai
devono passare attraverso l'intera lista per trovare la fine di aggiungere su, giusto?
Si può solo attaccare proprio nel.
>> Quindi dovremo passare attraverso un inserzione di 1 ora.
Quindi, una cosa che ho intenzione di Consiglio vivamente questo pset
è quello di disegnare le cose, come sempre.
E 'molto importante che si aggiorna i puntatori nell'ordine corretto
perché se si aggiorna li leggermente fuori ordine,
si sta andando a finire perdere parti del proprio elenco.
>> Così, per esempio, in questo caso, siamo raccontando la testa di solo punto a 1.
Se abbiamo appena facciamo senza salvare 1,
non abbiamo idea di cosa 1 deve puntare ora
perché abbiamo perso quello che la testa indicò.
Quindi, una cosa da ricordare quando stai facendo un anteporre
è quello di salvare ciò che il punti a testa per primo,
poi riassegnare, e quindi aggiornare che cosa il vostro nuovo nodo deve puntare.
In questo caso, questo è un modo per farlo.
>> Quindi, se avessimo fatto in questo modo dove abbiamo appena riassegnato testa,
perdiamo in fondo il nostro tutto l'elenco, giusto?
Un modo per farlo è quello di avere 1 punto di prossimo, e poi punto a capo 1.
Oppure si può fare un po 'come il deposito temporaneo, di cui ho parlato.
>> Ma riassegnando il tuo puntatori nell'ordine corretto
sta per essere molto, molto importante per questo pset.
In caso contrario, si sta andando ad avere un hash tavolo o una prova che è solo andare a essere
solo una parte delle parole che vuole e poi you're-- mmhmm?
PUBBLICO: Qual è stata la temporanea cosa di stoccaggio di cui parlavi?
SPEAKER 1: Il deposito temporaneo.
Quindi, in pratica un'altra modo si potrebbe fare questo
è conservare la testa di qualcosa, come memorizzare la variabile temporanea.
Assegnarlo a 1 e quindi aggiornare 1 al punto
a qualunque testa usato per puntare a.
In questo modo è ovviamente più elegante perché si
non hanno bisogno di un valore temporaneo, ma solo offrendo un altro modo per farlo.
E in realtà hanno del codice per questo.
Così per la lista collegata, abbiamo in realtà avere un po 'di codice.
Quindi inserire qui, questo è preponendo.
Quindi questo vi entra in testa.
>> Quindi, prima cosa, è necessario creare il nuovo nodo, naturalmente,
e verificare la presenza di NULL.
Sempre buono.
E poi è necessario assegnare i valori.
Ogni volta che si crea un nuovo nodo, è non so cosa sta indicando il prossimo,
così si desidera inizializzare a NULL.
Se non finisce che punta a qualcosa altro, viene riassegnato e va bene.
Se è la prima cosa nella lista, di cui ha bisogno
per puntare a NULL perché questa è la fine della lista.
>> Allora per inserirlo, vediamo qui stanno assegnando il valore successivo del nostro nodo
di essere ciò che è testa, che è quello che abbiamo avuto qui.
Questo è quello che abbiamo appena fatto.
E poi stiamo assegnando testa al punto al nostro nuovo nodo, perché ricordate,
nuovo qualche puntatore a un nodo, e questo è esattamente ciò che la testa è.
Questo è esattamente il motivo per cui avere questa freccia di accesso.
Cool?
Mmhmm?
>> PUBBLICO: Dobbiamo inizializzare nuovo accanto a NULL prima,
o possiamo semplicemente inizializzarlo a testa?
>> SPEAKER 1: Nuovo accanto deve essere NULL per iniziare
perché non si sa dove sta andando essere.
Inoltre, questo è una specie di proprio come un paradigma.
Si imposta uguale a NULL solo per fare Assicurarsi che tutte le basi sono coperti
prima di fare qualsiasi riassegnazione in modo che sei sempre la garanzia che lo farà
essere che punta a un valore specifico contro come un valore spazzatura.
Perché, sì, assegniamo nuova successivo automaticamente,
ma è più proprio come un buone pratiche per inizializzarlo
in questo modo e poi riassegnare.
>> OK, quindi doppiamente legata liste ora.
Che cosa pensiamo?
Cosa c'è di diverso con doppiamente legato liste?
>> Quindi, nelle nostre liste collegate, possiamo muoversi solo in una direzione, giusto?
Abbiamo solo il prossimo.
Possiamo solo andare avanti.
>> Con una lista doppiamente concatenata, possiamo anche tornare indietro.
Così abbiamo non solo la numero che si vuole memorizzare,
abbiamo dove a cui punta il prossimo e dove siamo appena tornati da.
Quindi questo permette alcuni meglio di attraversamento.
>> Nodi in modo doppiamente collegate, molto simile, giusto?
L'unica differenza è che ora un successivo e precedente.
E 'l'unica differenza.
>> Quindi, se dovessimo anteporre o append-- noi non hanno alcun codice per questo in su qui--
ma se si dovesse cercare di inserirla, la cosa importante
è quello che dovete fare che si sta assegnando
sia il precedente e il vostro prossimo puntatore correttamente.
Quindi, in questo caso, si farebbe non solo inizializzare il prossimo,
si inizializza precedente.
Se siamo in testa alla lista, ci potrebbe non solo rendere testa pari nuovo,
ma il nostro nuovo precedente dovrebbe puntare alla testa, giusto?
>> Questa è l'unica differenza.
E se volete più pratica con questi con liste concatenate, con l'inserimento,
con l'eliminazione, con inserto in una lista di assortiti,
si prega di consultare study.cs50.net.
C'è un mucchio di grandi esercizi.
Io li consiglio vivamente.
Mi sarebbe piaciuto avere il tempo di passare attraverso di loro ma ci sono un sacco di strutture di dati
per ottenere attraverso.
>> OK, quindi tabelle hash.
Questo è probabilmente il più bit utili per il vostro pset
qui perché si sta andando ad essere attuare una di queste, o una prova.
Mi piace molto tabelle hash.
Sono piuttosto fresco.
>> Quindi, in pratica ciò che accade è una tabella hash
è quando abbiamo veramente bisogno veloce inserimento, cancellazione e ricerca.
Queste sono le cose che siamo priorità in una tabella hash.
Possono ottenere abbastanza grande, ma come vedremo con tentativi,
ci sono cose che sono molto più grandi.
>> Ma in fondo, tutto un hash tabella è una funzione hash
che ti dice che secchio per mettere ogni dei dati, ciascuno dei vostri elementi.
Un modo semplice di pensare a una tabella hash è che è solo secchi di cose,
giusto?
Così, quando si ordina le cose da come la prima lettera del loro nome,
questo è un po 'come una tabella hash.
>> Quindi, se dovessi gruppo di ragazzi è in gruppi di chiunque di nome inizia
con A qui, o chi per il compleanno è nel mese di gennaio, febbraio, marzo,
qualunque, cioè efficace la creazione di una tabella hash.
E 'solo la creazione di secchi che si ordinano gli elementi in
in modo che si può trovare più facilmente.
Così, in questo modo, quando ho bisogno per trovare uno di voi,
Non ho per la ricerca attraverso ciascuno dei vostri nomi.
Posso essere come, oh, so che Compleanno di Danielle è dentro--
PUBBLICO: --April.
SPEAKER 1: aprile.
Quindi io guardo nel mio aprile secchio, e con po 'di fortuna,
lei sarà l'unica in là e il mio tempo è stato costante in questo senso,
mentre se devo guardare attraverso un intero gruppo di persone,
sta andando a prendere molto più tempo.
Quindi, tabelle hash sono in realtà solo secchi.
Un modo semplice di pensare a loro.
>> Quindi, una cosa molto importante su una tabella di hash è una funzione di hash.
Quindi le cose che ho appena parlato, come la tua prima lettera del nome
o il tuo mese di compleanno, queste sono idee che
davvero correlare ad una funzione di hash.
E 'solo un modo di decidere quale tu sei secchio elemento va in, OK?
Quindi, per questo pset, è possibile cercare praticamente qualsiasi funzione di hash che si desidera.
>> Non deve essere il vostro.
Ci sono alcuni tra quelli davvero cool fuori lì che fare ogni sorta di matematica pazzo.
E se si desidera rendere il vostro correttore ortografico super veloce,
Mi sarebbe sicuramente guardare in uno di quelli.
>> Ma ci sono anche il quelli semplici, come il calcolo
la somma delle parole, come ogni lettera ha un numero.
Calcolare la somma.
Che determina il secchio.
Essi hanno anche i più facili che sono proprio come tutti gli A è qui,
tutta la B è qui.
Ogni uno di quelli.
>> In sostanza, si dice solo che indice dell'array vostro elemento dovrebbe andare in.
Basta decidere il bucket-- è tutto una funzione di hash è.
Quindi qui abbiamo un esempio che è solo la prima lettera della stringa
che stavo solo parlando.
>> In modo da avere un po 'di hash che è solo il prima lettera della stringa meno A,
che vi darà un po ' numero compreso tra 0 e 25.
E ciò che si vuole fare è fare in modo che questo rappresenta
la dimensione del hash table-- quanti secchi ci sono.
Con molti di questi funzioni di hash, sono
sta per essere i valori di ritorno che potrebbe essere di gran lunga superiore al numero di bucket
che in realtà hanno nella tabella hash,
quindi è necessario fare sicuro e mod da chi.
In caso contrario, si sta per dire, oh, che dovrebbe essere in secchio 5.000
ma hai solo 30 secchi nella vostra tabella hash.
E, naturalmente, sappiamo tutti che è andando a causare alcuni errori pazzeschi.
Quindi assicuratevi di mod dal dimensione della tabella hash.
Freddo.
Così le collisioni.
Sono tutti bene finora?
Mmhmm?
>> PUBBLICO: perché è vero restituire un valore così massiccio?
>> SPEAKER 1: A seconda dell'algoritmo che la vostra funzione di hash utilizza.
Alcuni di loro faranno moltiplicazione pazzo.
Ed è tutto su come ottenere una distribuzione uniforme,
in modo da fare un po 'davvero cose folli a volte.
Questo è tutto.
Qualunque altra cosa?
Ok.
>> Così le collisioni.
In sostanza, come ho detto prima, nel migliore dei casi,
qualsiasi secchio guardo è andando ad avere una cosa,
quindi non devo guardare a tutti, giusto?
Mi sia so che è lì o è non, e questo è ciò che vogliamo davvero.
Ma se abbiamo decine di migliaia di punti dati e meno di quel numero
di benne, stiamo andando ad avere collisioni in cui alla fine qualcosa
sta andando ad avere per finire in un benna che ha già un elemento.
>> Quindi la domanda è, cosa facciamo in questo caso?
Che cosa facciamo?
Abbiamo già qualcosa lì?
Dobbiamo solo buttare fuori?
>> No.
Dobbiamo continuare a ciascuno di essi.
Quindi il modo in cui tipicamente farlo è quello?
Qual è la struttura dei dati abbiamo appena parlato?
PUBBLICO: lista collegata.
SPEAKER 1: Una lista concatenata.
Così ora, invece di ciascuno di questi benne solo che hanno un elemento,
sta andando a contenere una lista concatenata di gli elementi che sono stati hash in esso.
OK, non tutti i tipi di ottenere che idea?
Perché non abbiamo potuto avere una matrice perché non sappiamo quante cose
stanno per essere lì.
Una lista concatenata ci consente di avere solo il numero esatto
sono hash in quel secchio, giusto?
>> Così scansione lineare è fondamentalmente questo idea--
è un modo per affrontare una collisione.
Che cosa si può fare è se, in questo caso, frutti di bosco è stato eseguito l'hashing in 1
e abbiamo già qualcosa lì, basta
andare avanti fino a quando a trovare uno slot vuoto.
Questo è un modo per gestire la cosa.
L'altro modo di gestire è con quello che abbiamo appena
called-- il collegato lista si chiama concatenamento.
>> Quindi questa idea funziona se la tabella hash si pensa
è molto più grande i tuoi dati impostati o se si
vuole cercare di ridurre al minimo il concatenamento fino a quando è assolutamente necessario.
Quindi una cosa è lineare sondare significa, ovviamente,
che la funzione di hash non è altrettanto utile
perché si sta andando a finire con la funzione di hash, di arrivare a un punto,
si lineare sondare fino a un posto che è disponibile.
Ma ora, naturalmente, qualsiasi cosa altra cosa che finisce lì,
si sta andando ad avere per cercare ancora più in basso.
>> E c'è molto di più Ricerca spesa che
va in immissione di un elemento nella tabella hash ora, giusto?
E ora quando si va e cercare di trovare bacche di nuovo, si sta andando ad hash esso,
e sta andando a dire, Oh, guarda nel secchio 1,
e non sarà nel secchio 1, quindi sei
andando ad avere per attraversare per il resto di questi.
Quindi è a volte utile, ma nella maggior parte dei casi,
stiamo andando a dire che concatenamento è ciò che si vuole fare.
>> Così abbiamo parlato di questo in precedenza.
Ho avuto un po 'più avanti di me stesso.
Ma concatenamento è, fondamentalmente, che ciascun segmento della tabella hash
è solo una lista collegata.
>> Quindi un altro modo, o più tecnico modo, di pensare a una tabella hash
è che è solo un array di liste collegate, che
quando si sta scrivendo il dizionario e si sta cercando di caricarlo,
pensare come un array di liste concatenate
renderà molto più facile per di inizializzare.
>> PUBBLICO: Così tabella hash ha una dimensione predeterminata,
come un [incomprensibile] di secchi?
>> SPEAKER 1: Giusto.
Così ha un determinato numero di secchi che si determine--
che voi ragazzi dovrebbero sentitevi liberi di giocare.
Può essere piuttosto fresco per vedere cosa succede
come si cambia il numero di segmenti.
Ma sì, ha un numero impostato di secchi.
Ciò che permette di montare come molti elementi di cui hai bisogno
è questo concatenazioni separate dove hanno collegato le liste in ciascun segmento.
Ciò significa che la tua tabella di hash sarà esattamente la dimensione
che è necessario che sia, giusto?
Questo è il punto centrale di liste collegate.
Freddo.
>> Così tutti OK lì?
Bene.
Ah.
Che cosa è successo?
Veramente ora.
Immagino che qualcuno mi sta uccidendo.
>> OK stiamo per andare in paesi, che sono un po 'pazzo.
Mi piace tabelle hash.
Penso che siano davvero cool.
Mete sono fresche, troppo.
>> Così qualcuno si ricorda che cosa è una prova?
Si dovrebbe avere superato brevemente in conferenza?
Ti ricordi una specie di come funziona?
PUBBLICO: Sto solo facendo un cenno che siamo andati su di esso.
SPEAKER 1: Noi andiamo su di esso.
OK, siamo davvero intenzione di andare su di esso ora è quello che stiamo dicendo.
>> PUBBLICO: Questo è un albero di recupero.
>> SPEAKER 1: Sì.
E 'un albero di recupero.
Impressionante.
Quindi, una cosa da notare qui è che noi stanno guardando i singoli caratteri
qui, giusto?
>> Quindi, prima con la nostra funzione di hash, si state guardando le parole nel suo complesso,
e ora stiamo cercando di più i personaggi, giusto?
Così abbiamo Maxwell qui e Mendel.
Quindi, fondamentalmente un try-- un modo di pensare di questo è che ogni livello qui
è una serie di lettere.
Quindi questo è il nodo radice qui, giusto?
Questo ha tutti i caratteri della alfabeto per l'inizio di ogni parola.
>> E ciò che si vuole fare è per esempio, OK, abbiamo qualche parola M.
Stiamo andando a cercare Maxwell, in modo da andiamo a M. M punti per un intero
altra una matrice dove ogni parola, finché ci
è una parola che ha un la seconda lettera,
finché c'è una parola che B ha la seconda lettera,
avrà un puntatore andare a qualche serie successiva.
>> Probabilmente non è un parola che MP qualcosa,
così nella posizione P in questa matrice, sarebbe solo essere NULL.
Sarebbe dire, OK, non c'è parola che è M seguito da una P, OK?
Quindi, se ci pensiamo bene, ogni una di queste piccole cose
è in realtà uno di questi matrici di grandi dimensioni da A a Z.
Quindi, quello che potrebbe essere una delle cose cioè tipo di inconveniente di un tentativo?
>> PUBBLICO: Un sacco di memoria.
>> SPEAKER 1: E 'un sacco di memoria, giusto?
Ognuno di questi blocchi qui rappresenta 26 spazi, 26 array di elementi.
Quindi cerca ottengono incredibilmente spazio pesante.
>> Ma sono molto veloci.
Così incredibilmente veloce, ma molto spazio inefficiente.
Tipo di dover calcolare quale quello che si desidera.
Questi sono davvero cool per il vostro pset, ma lo fanno prendere un sacco di memoria,
in modo compromesso.
Sì?
>> PUBBLICO: Sarebbe possibile di istituire una prova e poi
una volta che avete tutto il i dati in esso che si need--
Non so se questo avrebbe senso.
Mi è stato sbarazzarsi di tutte le Caratteri NULL, ma poi
non sarebbe in grado di indicizzare them--
>> SPEAKER 1: Hai ancora bisogno di loro.
>> PUBBLICO: - allo stesso modo ogni volta.
SPEAKER 1: Sì.
È necessario i caratteri NULL per far sapere se non c'è una parola lì.
Ben fatto di avere qualcosa che si desidera?
Ok.
Va bene, quindi stiamo andando per andare un po 'di più
nel dettaglio tecnico dietro una prova e lavorare con un esempio.
>> OK, quindi questo è la stessa cosa.
Mentre in una lista collegata, il principale tipo di-- qual è la parola che voglio? -
come la costruzione di blocco è stato un nodo.
In una prova, abbiamo anche un nodo, ma è definito in modo diverso.
>> Così abbiamo un po 'bool che rappresenta sia una parola in realtà
esiste in questa posizione, e quindi abbiamo alcune serie qui-- o meglio,
questo è un puntatore a un array di 27 caratteri.
E questo per, in questo caso, questo 27-- Sono sicuro che tutti voi sono come, aspetta,
ci sono 26 lettere nell'alfabeto.
Perché abbiamo 27?
>> Quindi, a seconda della modo si implementa questa,
questo è da un pset che permesso di apostrofi.
Ecco, questo è il motivo per cui l'uno in più.
Avrete anche in alcuni casi il terminatore nullo
è incluso come una delle caratteri che è permesso di essere,
ed è così che controllano a vedere se è la fine della parola.
Se siete interessati, il check-out Il video di Kevin su study.cs50,
così come Wikipedia ha alcune buone risorse là.
>> Ma stiamo andando a passare attraverso solo tipo di come si potrebbe lavorare attraverso una prova
se sei dato uno.
Così abbiamo un super semplice qui che ha la parola "pipistrello" e "zoom" in loro.
E come vediamo qui, questo piccolo spazio qui
rappresenta il nostro bool che dice, sì, questa è una parola.
E poi questo è il nostro array di caratteri, giusto?
>> Così ci accingiamo a passare attraverso trovare "bat" in questo tentativo.
Così iniziano in alto, giusto?
E sappiamo che b corrisponde a il secondo indice, il secondo elemento
in questo array, perché ae b.
Quindi circa il secondo.
>> E dice, OK, fresco, ne consegue che in l'array successivo, perché se ci ricordiamo,
non è che ciascuno di questi effettivamente contiene l'elemento.
Ognuno di questi array contiene un puntatore, giusto?
Si tratta di una distinzione importante da fare.
>> So che questo sta per essere-- tentativi sono davvero difficile andare avanti per la prima volta,
quindi, anche se questo è il seconda o terza volta
ed è ancora un po ' di sembrare difficile,
Ti prometto se si va orologio breve di nuovo domani,
che probabilmente ha molto più senso.
Ci vuole un sacco da digerire.
Io ancora a volte sono come, aspetta, che cosa è una prova?
Come si usa questo?
>> Così abbiamo B in questo caso, che è il nostro secondo indice.
Se avessimo, per esempio, c o d o qualsiasi altra lettera,
abbiamo bisogno di mappare che torna all'indice di una matrice che corrisponde.
Così vorremmo prendere come rchar e abbiamo appena sottrarre fuori una di mappa in 0 a 25.
Tutti bene il modo in cui mappa i nostri personaggi?
Ok.
>> Quindi andiamo al secondo e vedere che, sì, non è NULL.
Siamo in grado di passare a questa nuova serie.
Così andiamo avanti per la prossima serie qui.
>> E noi diciamo, OK, ora siamo bisogno di vedere se a è qui.
A è NULL o lo fa in realtà andare avanti?
Così una realtà si muove avanti in questo array.
E noi diciamo, OK, t è la nostra ultima lettera.
Quindi andiamo al t in corrispondenza dell'indice.
E allora andiamo avanti perché ce n'è un altro.
E questo in pratica dice che, sì, si dice che c'è una parola qui--
che se si segue questa percorso, siete arrivati
in una parola, che noi sappiamo è "bat".
Sì?
>> PUBBLICO: E 'normale avere quel come indice 0 e quindi avere una sorta a 1
o di avere alla fine?
>> SPEAKER 1: No.
Quindi, se guardiamo indietro al nostro dichiarazione di qui, è un bool,
quindi è il suo elemento nel nodo.
Quindi non è parte della matrice.
Freddo.
Così, quando abbiamo finito la nostra parola e siamo a questo array, quello che vogliamo fare
è fare un controllo per questo è una parola.
E in questo caso, sarebbe tornare sì.
>> Quindi, su questa nota, sappiamo che "zoo" - che noi conosciamo come gli esseri umani che "zoo" è una parola,
giusto?
Ma sono provate qui sarebbe dire, no, non lo è.
E sarebbe dire che perché noi non hanno designato come una parola qui.
Anche se siamo in grado di attraversare attraverso a questo array,
questa meta sarebbe dire che, no, zoo non è nel dizionario
perché non abbiamo designato come tale.
>> Quindi un modo per fare che-- oh, scusate, questo.
Quindi, in questo caso, "zoo" non è una parola, ma è nel nostro tentativo.
Ma in questo, diciamo che vogliamo introdurre la parola "bagno", cosa succede
è che seguiamo through-- b, a, t.
Siamo in questa matrice, e andiamo a cercare per ore.
>> In questo caso, quando guardare il puntatore h,
è che punta a NULL, OK?
Quindi a meno che non sia esplicitamente che punta a un altro array,
si assume che tutti i puntatori in questo array si punta a null.
Quindi in questo caso, h punta null in modo da non possiamo fare nulla,
quindi sarebbe anche restituire falso, "bagno" non è qui.
Così ora siamo in realtà intenzione di passare attraverso
come potremmo effettivamente dire che "zoo" è nel nostro tentativo.
Come inseriamo "zoo" in nostro tentativo?
Quindi, nello stesso modo in cui abbiamo iniziato con la nostra lista collegata, si parte alla radice.
In caso di dubbio, iniziare a la radice di queste cose.
>> E diremo, OK, z.
z esiste in questo, e lo fa.
Quindi, si sta spostando verso il vostro prossimo array, OK?
E poi su quella successiva, si dice, OK, non o esiste?
Lo fa.
Questo ancora una volta.
>> E così il nostro prossimo, abbiamo detto, OK, "zoo" è già qui.
Tutto quello che dobbiamo fare è impostare questo uguale al vero, che c'è una parola lì.
Se tu avessi seguito tutto fino a prima di tale momento,
è una parola, quindi basta impostarlo a tale.
Sì?
>> PUBBLICO: Allora fa che significa che "ba" è anche una parola?
>> SPEAKER 1: No.
Quindi, in questo caso, "ba" otterremmo qui, possiamo dire è che una parola,
e sarebbe ancora no.
Ok?
Mmhmm?
>> PUBBLICO: Quindi una volta che si tratta di un parola e lei dice di sì, allora
conterrà per andare in m?
>> SPEAKER 1: Quindi questo ha a che fare with-- si sta caricando in questo.
Tu dici "zoo" è una parola.
Quando si va a check-- come, dici che vuoi dire,
si intende per "zoo" esiste in questo dizionario?
Stai solo andando a cercare "zoo" e poi controllare per vedere se si tratta di una parola.
Non riuscirai mai a muoversi fino alla m perché non è
quello che stai cercando.
>> Quindi, se davvero volessimo aggiungere "bagno" in questo tentativo,
faremmo la stessa cosa come abbiamo fatto con "zoo"
tranne vedremmo che quando cercare di ottenere di h, non esiste.
Così si può pensare a questo come cercare aggiungere un nuovo nodo in una lista collegata,
quindi ci sarebbe bisogno di aggiungere altro uno di questi array, in questo modo.
E poi quello che facciamo è che abbiamo appena impostato il h elemento di questa matrice punta a questo.
>> E allora che cosa vorremmo fare qui?
Aggiungi uguale a vero perché è una parola.
Freddo.
Lo so.
Mete non sono la più emozionante.
Fidati di me, lo so.
>> Quindi, una cosa da realizzare con i tentativi, Ho detto, sono molto efficienti.
Così abbiamo visto che prendere un sacco di spazio.
Sono specie di confusione.
Allora perché dovremmo mai usare questi?
Usiamo questi perché sono incredibilmente efficiente.
>> Quindi, se siete mai cercando una parola, tu sei solo
delimitata dalla lunghezza della parola.
Quindi, se siete alla ricerca di un parola che è di lunghezza cinque,
si sta sempre e solo andando ad avere per rendere al massimo cinque confronti, OK?
Quindi rende praticamente costante.
Come l'inserimento e la ricerca sono sostanzialmente costante di tempo.
>> Quindi, se si può mai ottenere qualcosa in tempo costante,
questo è quanto di meglio si possa.
Non si può trovare di meglio costante di tempo per queste cose.
Quindi questo è uno degli enormi vantaggi di tentativi.
>> Ma è un sacco di spazio.
Così è sorta di decidere che cosa è più importante per voi.
E sui computer di oggi, il spazio che una prova può richiedere fino
forse non interessa più di tanto, ma forse
hai a che fare con qualcosa di che ha molto, molto di più le cose,
e una prova solo che non è ragionevole.
Sì?
>> PUBBLICO: Aspetta, in modo da avere 26 lettere in ognuno?
>> SPEAKER 1: Mmhmm.
Sì, avete 26.
Hai qualche marcatore è parola e poi si dispone di 26 puntatori a tutti.
E sono point--
>> PUBBLICO: E ogni 26, fanno ogni hanno 26?
>> SPEAKER 1: Sì.
Ed è per questo che, come si può vedere, si espande rapidamente.
Bene.
Quindi stiamo per entrare in alberi, che Mi sento come è più facile e probabilmente
essere un bel po 'di tregua da tentativi lì.
Così si spera la maggior parte di voi hanno visto un albero prima.
Non come la bella quelli di fuori, che mi
non so se qualcuno è andato fuori di recente.
Sono andato la raccolta delle mele in questo fine settimana, e oh mio Dio, è stato bellissimo.
Non sapevo che le foglie poteva guardare quella bella.
>> Quindi, questo è solo un albero, giusto?
È solo alcuni nodi, e punti a un gruppo di altri nodi.
Come potete vedere qui, questo è specie di un tema ricorrente.
Nodi che punta ai nodi è una specie di l'essenza di molte strutture dati.
Dipende solo dal modo in cui li hanno indicano reciprocamente
e come attraversiamo attraverso di loro e il modo in cui
inserire cose che determina le loro diverse caratteristiche.
>> Quindi, solo un po 'di terminologia, che ho usato prima.
Così radice è tutto ciò che è in cima.
è dove partiamo sempre.
Si può pensare ad esso come la testa anche.
Ma per gli alberi, si tende a fare riferimento ad esso come la radice.
>> Tutto ciò in qui-- fondo al più, molto bottom--
sono le foglie considerati.
Così va insieme alla tutto l'albero, giusto?
Le foglie sono ai bordi del vostro albero.
>> E poi abbiamo anche un paio di termini per parlare di nodi in relazione
tra loro.
Così abbiamo genitore, figli, e fratelli.
Quindi in questo caso, 3 è il madre di 5, 6 e 7.
Così il genitore è tutto ciò che è un gradino sopra quello che sei
riferendosi a, quindi basta come un albero genealogico.
Speriamo che questo è tutto un po ' po 'più intuitivo rispetto ai tentativi.
>> I fratelli sono quelle che hanno lo stesso genitore, giusto?
Sono allo stesso livello qui.
E poi, come mi è stato dicendo, i bambini sono solo
tutto ciò che è un gradino sotto il nodo in questione, OK?
Freddo.
Così un albero binario.
Qualcuno può azzardare un'ipotesi su una delle le caratteristiche dell'albero binario?
>> PUBBLICO: Max due foglie.
>> SPEAKER 1: Giusto.
Quindi massimo di due foglie.
Quindi, in questa prima, abbiamo avuto questo che aveva tre, ma in un albero binario,
si dispone di un massimo di due bambini per genitori, giusto?
C'è un altro Caratteristica interessante.
Qualcuno lo sa?
Albero binario.
>> Così un albero binario avrà tutto su the-- questo non è sorted--
ma in un albero binario filtrate, tutto a destra
è maggiore del genitore, e tutto a sinistra
è inferiore al genitore.
E questo è stato un quiz domanda prima, così bene da sapere.
Quindi il modo in cui definiamo questo, ancora una volta, abbiamo un altro nodo.
Questo sembra molto simile a quello che?
Doppiamente
>> PUBBLICO: Collegato liste
>> SPEAKER 1: Una doppia lista collegata, giusto?
Quindi, se sostituiamo questo con precedente e successivo,
questo sarebbe una lista doppiamente concatenata.
Ma in questo caso, abbiamo effettivamente avere a destra ea sinistra e il gioco è fatto.
In caso contrario, è esattamente lo stesso.
Abbiamo ancora l'elemento che stai cercando,
e basta avere due puntatori andare a tutto ciò che è il prossimo.
Sì, albero di ricerca in modo binario.
Se notiamo, tutto sul proprio qui è maggiore than--
o tutto e subito a destra qui
è maggiore di tutto qui è inferiore.
>> Quindi, se siamo stati per la ricerca in, è dovrebbe guardare molto vicino alla ricerca binaria
qui, giusto?
Tranne invece di guardare a metà dell'array,
stiamo solo guardando o sinistra lato o sul lato destro dell'albero.
Così diventa un po 'più semplice, credo.
>> Così, se il root è NULL, ovviamente è solo falso.
E se c'è, ovviamente, è vero.
Se è inferiore, cerchiamo sinistra.
Se è superiore, cerchiamo destra.
E 'esattamente come la ricerca binaria, solo una struttura dati diversa
che stiamo usando.
Al posto di un array, è solo un albero binario.
>> OK, pile.
E poi, sembra che ci potrebbe avere un po 'di tempo.
Se lo facciamo, io sono felice di andare su tutto questo ancora una volta.
OK, così stack.
Qualcuno ricorda cosa stacks-- eventuali caratteristiche di una pila?
>> OK, quindi la maggior parte di noi, credo, mangiare nella sala da halls--
quanto potremmo non piace.
Ma, ovviamente, si può pensare di una pila letteralmente come una pila di vassoi
o una pila di cose.
E ciò che è importante rendersi conto è che è
something-- la caratteristica che noi chiamiamo by-- è LIFO.
Qualcuno sa di cosa si sta per?
Mmhmm?
>> PUBBLICO: last in, first out.
>> SPEAKER 1: Destra, last in, first out.
Quindi, se noi sappiamo, se siamo accatastamento cose up, la cosa più facile da afferrare off--
e forse l'unica cosa che può afferrare off se il nostro stack è grande enough--
è l'elemento superiore.
Quindi, qualunque sia stato messo su last-- come vediamo qui,
tutto ciò che è stato spinto sulla maggior parte recently-- è
sarà il primo cosa che abbiamo pop off, OK?
>> Quindi, quello che abbiamo qui è un'altra struct typedef.
Questo è davvero come solo un Crash Course in struttura di dati,
quindi c'è un sacco gettato a voi ragazzi.
Lo so.
Quindi, ancora un altro struct.
Yay per le strutture.
>> E in questo caso, è qualche puntatore ad una matrice che ha una certa capacità.
Quindi questo rappresenta la nostra pila qui, come la nostra gamma attuale
che è in possesso di nostri elementi.
E poi qui abbiamo una certa dimensione.
>> E in genere, si desidera mantenere traccia di come grande il vostro stack è
perché quello che sta andando a consentire di fare è se si conosce la dimensione,
permette di dire, OK, sono io a capacità?
Posso aggiungere qualcosa di più?
E ve lo dice anche in cui la parte superiore della pila
è in modo da sapere cosa si può effettivamente decollare.
E che in realtà sta per essere un po 'più chiaro qui.
>> Così, per spinta, una cosa, se si erano mai ad attuare spinta,
come ho appena detto, la tua pila ha una dimensione limitata, giusto?
La nostra serie ha avuto una certa capacità.
Si tratta di un array.
Si tratta di una dimensione fissa, quindi abbiamo bisogno di assicurarsi che non stiamo mettendo più
nella nostra matrice di noi in realtà hanno spazio per.
>> Così, quando si sta creando una spinta funzione, prima cosa da fare è dire, OK,
devo spazio nel mio stack?
Perché se non lo faccio, mi dispiace, Non riesco a memorizzare il vostro elemento.
Se lo faccio, poi si desidera memorizzare in cima alla pila, giusto?
>> E questo è il motivo per cui abbiamo per tenere traccia delle nostre dimensioni.
Se non teniamo traccia delle nostre dimensioni, non sappiamo dove metterlo.
Non sappiamo quante cose sono la nostra gamma già.
Come, ovviamente, ci sono modi che forse si potrebbe fare.
Si potrebbe inizializzare tutto a NULL e quindi controllare per le ultime NULL,
ma una cosa molto più facile è solo per dire, OK, tenere traccia di dimensioni.
Come so che ho quattro elementi nel mio array, quindi la prossima cosa
che abbiamo messo su, siamo andando a memorizzare all'indice 4.
E poi, ovviamente, ciò significa che che avete trasmesso con successo qualcosa
sul vostro stack, vogliono aumentare le dimensioni
in modo da sapere dove sei così che si può spingere più cose su.
>> Quindi, se stiamo cercando di pop qualcosa dallo stack,
quello che potrebbe essere la prima cosa che vogliamo controllare?
Stai cercando di prendere qualcosa che il vostro stack.
Sei sicuro che non c'è qualcosa nel tuo stack?
No.
Allora, cosa potremmo desiderare di controllare?
>> PUBBLICO: [incomprensibile].
SPEAKER 1: Controllare le dimensioni?
Dimensione.
Quindi, vogliamo verificare se la nostra dimensione è maggiore di 0, OK?
E se lo è, allora vogliamo diminuire la nostra dimensione di 0 e tornare quello.
Perché?
>> Nella prima eravamo spingere, abbiamo spinto esso
sulla dimensione e la dimensione poi aggiornato.
In questo caso, stiamo decrementare dimensioni e poi toglierlo, strappando esso
dal nostro array.
Perché potremmo farlo?
Quindi, se ho una cosa sul mio stack, quello che sarebbe il mio numero a quel punto?
1.
>> E in cui è memorizzato l'elemento 1?
A quale indice?
PUBBLICO: 0.
SPEAKER 1: 0.
Quindi, in questo caso, sempre bisogno di fare sure--
invece di restituire dimensione meno 1, perché noi
sa che il nostro elemento è sta per essere conservato a 1 meno
qualunque sia la nostra dimensione è, questo appena si prende cura di esso.
E 'un modo un po' più elegante.
E abbiamo appena decrementa il nostro dimensioni e poi tornare dimensioni.
Mmhmm?
>> PUBBLICO: Credo che solo in generale, perché sarebbe questa struttura dati
essere utile?
>> SPEAKER 1: Dipende dal vostro contesto.
Così per alcuni della teoria, se si sta lavorando with-- OK,
fammi vedere se vi è una benefica cioè vantaggioso per più di fuori
di CS.
Con stack, ogni volta che si ha bisogno per tenere traccia di qualcosa che
è la più recente aggiunta è quando si sta andando a voler utilizzare una pila.
>> E non riesco a pensare ad un buon esempio di che in questo momento.
Ma quando il più recente cosa è più importante per voi,
in quel momento una pila sta per essere utile.
Sto cercando di pensare se c'è una buona per questo.
Se penso a un buon esempio nel prossimo 20 minuti, ci tornerò sicuramente dirà.
>> Ma nel complesso, se c'è qualcosa, come ho detto la maggior parte, in cui più recente
è più importante, che è dove una pila entra in gioco.
Considerando che le code sono di tipo opposto.
E tutti i piccoli cani.
Non è questo grande, giusto?
Mi sento come dovrei basta avere un video coniglio
proprio nel mezzo di sezione per voi ragazzi
perché questa è una sezione intenso.
>> Così una coda.
Fondamentalmente una coda è come una linea.
Voi ragazzi sono sicuro che uso questo tutti i giorni, proprio come nelle nostre sale da pranzo.
Quindi dobbiamo andare a e ottenere i nostri vassoi, sono
Assicurati di avere di attendere in linea di strisciare o ottenere il vostro cibo.
>> Quindi la differenza qui è che questo è FIFO.
Quindi, se LIFO ultimo entrato, primo out, FIFO è il primo entrato, primo uscito.
Quindi questo è dove tutto ciò che si mette il primo è il vostro più importante.
Quindi, se stavate aspettando in un line-- anche voi
immaginate se si è andato a andare a prendere il nuovo iPhone
ed era una pila in cui la ultima persona in linea ha in primo luogo,
persone si uccidono a vicenda.
>> Così FIFO, siamo tutti molto familiare con nel mondo reale qui
e tutto ha a che fare con la realtà tipo di ricreare tutta questa linea
e in coda la struttura.
Così, mentre con lo stack, abbiamo push e pop.
Con una coda, abbiamo accodamento e dequeue.
Così enqueue significa fondamentalmente metterlo sul retro,
e mezzi dequeue prendono dalla parte anteriore.
Così la nostra struttura dati è un po 'più complicata.
Abbiamo una seconda cosa da tenere traccia di.
>> Così, senza la testa, questo è esattamente una pila, giusto?
Questa è la stessa struttura di una pila.
L'unica cosa diversa è che ora avere questa testa, che cosa ne pensi
sta per tenere traccia di?
>> Pubblico: Il primo.
>> SPEAKER 1: a destra, il prima cosa che abbiamo messo in.
Il capo della nostra coda.
Chi è in prima linea.
Va bene, quindi se facciamo accodamento.
Ancora, con qualsiasi queste strutture di dati,
dal momento che abbiamo a che fare con una matrice, abbiamo bisogno di controllare se abbiamo spazio.
>> Questo è un po 'come dirmi voi ragazzi, se si apre un file,
è necessario controllare per nulla.
Con qualsiasi di queste pile e le code, è necessario
per vedere se c'è lo spazio perché siamo si tratta di un array di dimensione fissa,
come si vede qui-- 0, 1 tutto a 5.
Quindi, ciò che facciamo in questo caso è di controllo per vedere se abbiamo ancora spazio.
È la nostra dimensione inferiore alla capacità?
>> Se è così, abbiamo bisogno di conservarlo a la coda e aggiorniamo la nostra dimensione.
Così che cosa potrebbe essere la coda in questo caso?
Non è esplicitamente scritto fuori.
Come possiamo conservarlo?
Quale sarebbe la coda essere?
>> Quindi cerchiamo di camminare attraverso questo esempio.
Quindi questo è un array di dimensione 6, giusto?
E noi abbiamo in questo momento, il nostro formato è 5.
E quando abbiamo messo dentro, è in corso per entrare nel quinto indice, giusto?
Così conservare a coda.
>> Un altro modo di scrivere la coda sarebbe solo sia la nostra gamma all'indice di dimensioni, giusto?
Questa è la dimensione 5.
La prossima cosa sta per andare in 5.
Cool?
Ok.
Diventa un po 'più complicato quando iniziamo scherzi con la testa.
Sì?
>> PUBBLICO: Questo significa che noi avrebbe dichiarato un array che
era lunga cinque elementi e allora stiamo aggiungendo su di esso?
>> SPEAKER 1: No.
Quindi, in questo caso, si tratta di uno stack.
Questo sarebbe dichiarato come un array di dimensione 6.
E in questo caso, solo avere uno spazio a sinistra.
>> OK, quindi una cosa è in questo caso, se la nostra testa è a 0,
poi abbiamo appena possiamo aggiungere che nelle dimensioni.
Ma diventa un po 'più complicato perché in realtà, si
non hanno una diapositiva per questo, quindi ho intenzione
disegnare uno perché non è è così semplice una volta che si
iniziare a sbarazzarsi delle cose.
Così mentre con una pila solamente mai avuto
preoccuparsi di ciò che la dimensione è quando si aggiunge qualcosa,
con una coda è inoltre necessario fare Assicurarsi che la testa è rappresentato,
perché una cosa bella di code è che se non sei al massimo della capacità,
si può effettivamente rendere più avvolgente.
>> OK, così si cosa-- oh, questo è terribile gesso.
Una cosa da considerare è il caso.
Dobbiamo solo fare cinque.
OK, quindi stiamo andando a dire la testa è qui.
Questo è 0, 1, 2, 3, 4.
>> La testa è lì, e si prega di avere delle cose in loro.
E vogliamo aggiungere qualcosa, giusto?
Quindi la cosa che abbiamo bisogno di sapere è che la testa è sempre
andando a muoversi in questo modo e poi loop back in giro, OK?
>> Quindi questa coda ha spazio, giusto?
Ha spazio fin dall'inizio, tipo l'opposto di questo.
Quindi quello che dobbiamo fare è che necessario calcolare la coda.
Se sapete che il vostro testa non si è mosso, coda
è solo l'array a l'indice delle dimensioni.
>> Ma in realtà, se si sta utilizzando una coda, la testa è probabilmente in fase di aggiornamento.
Quindi quello che dovete fare è effettivamente calcolare la coda.
Quindi, quello che facciamo è questa formula qui, che ho intenzione di farvi
ragazzi pensano, e poi ne parliamo.
Quindi questa è la capacità.
>> Quindi questo sarà effettivamente vi darà un modo per farlo.
Perché in questo caso, che cosa?
La nostra testa è a 1, il nostro formato è 4.
Se noi mod che da 5, si ottiene 0, che è dove dovremmo inserirlo.
>> Dunque, nel caso successivo, se dovessimo fare questo,
si dice, OK, facciamo dequeue qualcosa.
Si dequeue questo.
Prendiamo questo elemento, giusto?
>> E ora la nostra testa è rivolta qui, e vogliamo aggiungere un'altra cosa.
Questa è fondamentalmente la posteriore della nostra linea, giusto?
Le code possono avvolgere intorno alla matrice.
Questa è una delle principali differenze.
Stacks, non si può fare questo.
>> Con le code, è possibile perché tutto quello che conta
è che si sa che cosa è stato recentemente aggiunto.
Dal momento che tutto sta per essere aggiunto questa direzione verso sinistra, in questo caso,
e poi avvolgere intorno, è possibile continuare a mettere in nuovi elementi
nella parte anteriore della matrice perché non è davvero
la parte anteriore della matrice più.
Si può pensare all'inizio del array come se la testa è in realtà.
>> Quindi, questa formula è il modo si calcola la coda.
Fa questo ha un senso?
Ok.
OK, dequeue, e poi voi ragazzi avete 10 minuti
di farmi tutte le domande chiarendo gli si vuole, perché so che è pazzesco.
>> Va bene, così nella stessa way-- Non so se voi ragazzi notato,
ma CS è tutto su modelli.
Le cose sono più o meno la stesso, solo con piccoli ritocchi.
Quindi, stessa cosa qui.
Abbiamo bisogno di controllare per vedere se abbiamo effettivamente avere qualcosa nella nostra coda, giusto?
Di ', OK, è la nostra dimensione maggiore di 0?
Freddo.
>> Se lo facciamo, allora ci spostiamo la nostra testa, che è quello che ho appena dimostrato qui.
Aggiorniamo la nostra testa di essere un altro.
E poi abbiamo decrementa il nostro dimensioni e restituire l'elemento.
>> C'è molto di più concreto codice su study.cs50.net,
e mi raccomando di andare attraverso di essa se avete tempo,
anche se è solo una pseudo-codice.
E se voi volete parlare attraverso che con me uno contro uno, per favore fatemelo
conoscere.
Sarei felice di.
Strutture di dati, se si prende CS 124, ti
sanno che le strutture di dati diventano molto divertimento e questo è solo all'inizio.
>> Quindi so che è difficile.
Va bene.
Noi lottiamo.
Faccio ancora.
Quindi non preoccupatevi troppo su di esso.
>> Ma questo è in fondo il tuo Crash Course in strutture di dati.
Lo so che è un sacco.
C'è qualcosa che noi vorrebbe andare di nuovo?
Qualsiasi cosa vogliamo parlare fino in fondo?
Sì?
>> PUBBLICO: Per questo esempio, così la nuova coda è a 0 su quella?
SPEAKER 1: Sì.
PUBBLICO: OK.
Così poi passare attraverso, avresti 1 più 4 o-
>> SPEAKER 1: Così dicevano, quando vogliamo andare farlo di nuovo?
PUBBLICO: Sì.
Quindi, se si dovesse capire fuori-- dove sono a calcolare la coda da in questo?
>> SPEAKER 1: Così la coda ero dentro-- ho cambiato questo.
Quindi in questo esempio qui, questo era l'array che stiamo guardando, OK?
Così abbiamo cose in 1, 2, 3, e 4.
Così abbiamo la nostra testa è uguale a 1 a questo punto, e il formato è uguale a 4
a questo punto, giusto?
>> Voi tutti d'accordo che è il caso?
Così facciamo la testa più il formato, che ci dà 5, e poi ci Mod per 5.
Otteniamo 0, il che ci dice che 0 è dove è la nostra coda, dove abbiamo spazio.
>> PUBBLICO: Che cosa è un tappo?
>> SPEAKER 1: La capacità.
Scusi.
In modo che è la dimensione dell'array.
Sì?
>> PUBBLICO: [incomprensibile] prima torniamo l'elemento?
>> SPEAKER 1: Così si passa il testa o restituire il momento?
Quindi, se ci muoviamo uno, diminuire le dimensioni?
Resisti.
Ho sicuramente dimenticato un'altra.
Non importa.
Non c'è un'altra formula.
Sì, si vorrebbe tornare la testa e poi spostarlo indietro.
>> PUBBLICO: OK, perché in questo punto, la testa era a 0,
e poi si desidera tornare indice 0 e poi fare capo 1?
>> SPEAKER 1: Giusto.
Penso che ci sia un altro formula un po 'come questo.
Io non ce l'ho in alto la mia testa come Non voglio darvi quella sbagliata.
Ma penso che sia perfettamente valido per esempio, OK, conservare questo element-- qualunque
elemento di testa è-- diminuire il tuo dimensione, muovere la testa su e ritorno
qualunque cosa questo elemento è.
Questo è perfettamente valido.
Ok.
Mi sento come se questo non è come il most-- non sei
andando a uscire di qui come, sì, lo so tentativi.
Ho capito tutto.
Va bene.
Prometto.
Ma le strutture di dati sono qualcosa che ci vuole un sacco di tempo per abituarsi.
Probabilmente uno dei più difficili cose, credo, nel corso.
>> Quindi ci vuole sicuramente ripetizione e guardando at-- I
non sapevamo veramente liste collegate fino a quando ho fatto troppo con loro,
nello stesso modo in cui non ho fatto davvero capire puntatori
fino a quando ho dovuto insegnare per due anni e fare la mia p-set con esso.
Ci vuole un sacco di reiterazione e di tempo.
E alla fine, sarà di tipo fare clic su.
>> Ma nel frattempo, se si dispone di genere di un elevato livello di comprensione di ciò che
questi fanno, i loro pro e cons-- che è ciò che
abbiamo davvero tendiamo a sottolineare, specialmente nel corso di introduzione.
Come, perché dovremmo usare una prova su un array?
Come, quali sono gli aspetti positivi e negativi di ciascuno di questi?
>> E la comprensione dei trade-off tra ciascuna di queste strutture
è ciò che è molto più importante in questo momento.
Ci può essere un pazzo domanda o due che è
andare a chiedere di implementare spingere o implementare pop o accodamento e dequeue.
Ma per la maggior parte, avendo tale comprensione di livello più alto e più
di una comprensione intuitiva è più importante della realtà
essere in grado di attuarla.
>> Sarebbe davvero fantastico se tutti voi potrebbe uscire e andare a realizzare una prova,
ma si capisce che non è necessariamente la cosa più ragionevole in questo momento.
Ma è possibile nel vostro pset, se si desidera di, e poi si otterrà la pratica,
e allora forse avrete davvero capirlo.
Sì?
>> PUBBLICO: OK, quindi quali sono intendevamo utilizzare nel pset?
Ho bisogno di utilizzare uno di loro?
SPEAKER 1: Sì.
In modo da avere la vostra scelta.
Credo che in questo caso, possiamo parlare del pset un po '
perché mi sono imbattuto attraverso questi.
Quindi nel tuo pset, avete la vostra scelta di tentativi o tabelle hash.
Alcune persone cercano e utilizzare filtri fioritura,
ma quelli che tecnicamente non sono corrette.
A causa della loro natura probabilistica, danno falsi positivi a volte.
Sono look fresco in, però.
Consiglio vivamente cercando a loro almeno.
Ma avete la vostra scelta tra una tabella di hash e una prova.
E che sta per essere dove si carica nel dizionario.
>> E avrete bisogno di scegliere la funzione di hash,
è necessario scegliere il numero di Benne avete, e varierà.
Come se avete più secchi, forse ti correre più veloce.
Ma forse stai sprecando un molto spazio in questo modo, però.
Devi capirlo.
Mmhmm?
>> PUBBLICO: Lei ha detto prima che siamo in grado di utilizzare altre funzioni di hash,
che non abbiamo a creare una funzione di hash?
>> SPEAKER 1: Sì, giusto.
Così letteralmente per la vostra funzione di hash, come google "funzione di hash"
e potete trovare alcuni tra quelli freddi.
Non si aspetta di costruire le proprie funzioni di hash.
Le persone trascorrono la loro tesi su queste cose.
>> Quindi non preoccuparti per costruire il proprio.
Trova uno on-line per iniziare.
Alcuni di loro si deve manipolare un po '
per assicurarsi che i tipi restituiti corrispondono e quant'altro, così in principio,
Ti consiglio di utilizzare qualcosa molto semplice che forse solo
hash sulla prima lettera.
E poi una volta che hai questo lavoro, incorpora una funzione di hash refrigerante.
Mmhmm?
>> PUBBLICO: Sarebbe una prova sia o efficiente, ma solo più difficile da, like--
>> SPEAKER 1: Quindi una prova, credo, è intuitivamente difficile da attuare
ma è molto veloce.
Tuttavia, occupa più spazio.
Anche in questo caso, è possibile ottimizzare sia di quelli in modi diversi e ci sono modi a--
PUBBLICO: Come siamo graduata su questo?
Ha matter--
>> SPEAKER 1: Quindi sei classificati come di consueto.
Si sta andando ad essere classificato sul design.
Qualunque sia il tuo modo di fare, si vuole assicurarsi che sia elegante come può essere
ed efficiente come può essere.
Ma se si sceglie una meta o hash tavolo, finché funziona,
siamo felici di questo.
E se si usa qualcosa che gli hash sulla prima lettera, va bene,
come forse come il design-saggio.
Stiamo raggiungendo anche la punto in questo semester--
Non so se si ragazzi noticed-- se siete
gradi pset declinano un po ' a causa del design e quant'altro,
che è perfettamente bene.
E 'sempre ad un punto in cui il i programmi sono sempre più complicato.
Non ci sono più posti si può migliorare.
>> Quindi è perfettamente normale.
Non è che sei facendo peggio sul vostro pset.
E 'solo che ci stanno di più su di te ora.
Così tutti si sente.
Ho appena classificato tutti i vostri p-set.
So che tutti si sente esso.
>> Quindi non essere preoccupato per questo.
E se avete domande su pset precedenti o modi per migliorare,
Cerco di commentare la specifica luoghi, ma a volte è tardi
e mi stanco.
Ci sono altre cose su strutture di dati?
Sono sicuro che voi ragazzi non lo fanno veramente voglia di parlarne più,
ma se ci sono, sono felice di andare su di loro, così come qualsiasi
dalla conferenza lo scorso settimana o la settimana scorsa.
>> So che la settimana scorsa era tutto revisione, in modo da possiamo aver saltato qualche recensione
da lezione.
Tutte le altre domande posso rispondere?
OK, va bene.
Beh, voi ragazzi uscire 15 minuti di anticipo.
>> Spero che questo era semi-utile, almeno, e ci vediamo ragazzi la prossima settimana,
o giovedì l'orario d'ufficio.
Ci sono le richieste di snack per la prossima settimana, è la cosa?
Perché ho dimenticato la caramella oggi.
E ho portato caramelle ultimo settimana, ma era Columbus Day,
quindi non erano come sei persone che aveva quattro sacchetti di caramelle a se stessi.
Posso portare Starbursts ancora una volta, se volete.
Starbursts?
OK, suona bene.
Hanno un grande giorno, ragazzi.