[GIOCO MUSICA]
DAVID J. MALAN: Va bene.
Questo è CS50.
Questa è la settimana di cinque continuò, e noi avere qualche buona notizia e una cattiva notizia.
Quindi buona notizia è che CS50 lancia questo Venerdì.
Se volete unirvi a noi, andare al solito URL qui.
Ancora meglio le notizie, no lezione il prossimo Lunedi 13.
Leggermente meno notizie migliori, quiz zero è Mercoledì prossimo.
Maggiori dettagli possono essere trovato a questo indirizzo qui.
E nei prossimi giorni di coppia saremo riempire gli spazi vuoti
per quanto riguarda le camere che avremo riservato.
Meglio notizia è che ci sarà essere una revisione generale e portate
sessione il prossimo Lunedi sera.
Restate sintonizzati per il corso di sito web per la posizione e dettagli.
Sezioni, anche se si tratta di un vacanza, anche incontrare pure.
Miglior notizie, lezione prossimo Venerdì.
Quindi questa è una tradizione che avere, come da programma.
Solo-- sta andando essere sorprendente.
Vedrete le cose come strutture di dati costante di tempo
e tabelle hash e alberi e tentativi.
E parleremo di problemi di compleanno.
Un sacco di roba aspetta il prossimo Venerdì.
Ok.
Comunque.
>> Quindi ricordiamo che siamo stati concentrandosi su questa immagine di ciò che è
all'interno della memoria del nostro computer.
Così memoria o RAM è dove i programmi esistere mentre li sta eseguendo.
Se si fa doppio clic su un icona per eseguire qualche programma
o doppio clic su un icona per aprire qualche file,
è caricato dal disco guidare o unità a stato solido
nella RAM, Random Access Memory, dove vive fino a quando non si spegne,
il coperchio del portatile si chiude, o si chiude il programma.
>> Ora che la memoria, di che probabilmente avete
1 gigabyte questi giorni, 2 gigabyte, o anche molto di più,
è generalmente disposto per un dato programma
in questo genere di forma rettangolare modello concettuale
per cui abbiamo la pila in basso e un mucchio di altre cose in alto.
La cosa in cima abbiamo visto in questa immagine
prima, ma mai parlato è il cosiddetto segmento di testo.
Segmento di testo è solo un modo di fantasia di dire gli zeri e quelli che
comporre il programma compilato reale.
>> Così, quando si fa doppio clic Microsoft Word sul vostro Mac o PC,
o quando si esegue puntino tagliare Mario su una Computer Linux a vostra finestra di terminale,
gli zeri e quelli che compongono Word o Mario sono memorizzati temporaneamente
nella RAM del computer nella cosiddetta segmento di testo per un particolare programma.
Sotto che va inizializzato e dati non inizializzati.
Questa è roba come variabili globali, che noi non abbiamo usato molti,
ma a volte abbiamo aveva variabili globali
o staticamente stringhe definito che è difficile parole come "ciao" codificato
che non sono prese in dall'utente che sono hardcoded nel programma.
>> Ora, giù in fondo siamo avere il cosiddetto stack.
E lo stack, finora, siamo stati usando per che tipo di scopi?
Qual è lo stack stato utilizzato per?
Sì?
>> PUBBLICO: Funzioni.
>> DAVID J. MALAN: Per le funzioni?
In che senso per funzioni?
>> PUBBLICO: Quando si chiama una funzione, il argomenti vengono copiati nello stack.
>> DAVID J. MALAN: Esattamente.
Quando si chiama una funzione, la sua argomenti vengono copiati nello stack.
Quindi, qualsiasi X o Y o di una di B o di che si sta passando in una funzione
sono temporaneamente messo su il cosiddetto stack,
proprio come uno di Annenberg vassoi sala da pranzo, e anche le cose
come variabili locali.
Se la funzione foo o lo swap funzione ha variabili locali,
come temperatura, quei due finire nella pila.
Ora, noi non parleremo troppo di li, ma queste variabili di ambiente
in fondo abbiamo visto qualche tempo fa, quando Stavo futzing alla tastiera uno giorno
e ho cominciato accesso cose come argv 100 o argv 1000,
solo elements-- dimentico il numbers-- ma che
non avrebbero dovuto essere accessibile da me.
Abbiamo iniziato a vedere un po ' simboli funky sullo schermo.
Quelli erano i cosiddetti variabili di ambiente
come impostazioni globali per il mio programma o per il mio computer, non
estranei al recente bug che abbiamo discusso,
Shellshock, che è stato che affligge un bel paio di computer.
>> Ora, infine, a fuoco di oggi saremo in ultima analisi, di essere sul mucchio.
Questo è un altro pezzo di memoria.
E fondamentalmente tutto questo la memoria è la stessa roba.
E 'lo stesso hardware.
Siamo appena sorta di trattamento di diversi cluster
di byte per scopi diversi.
L'heap è anche andando a essere dove variabili e la memoria che si domanda
dal sistema operativo temporaneamente memorizzato.
>> Ma c'è una specie di problema qui, come l'immagine implica.
Noi abbiamo due specie di navi per scontrarsi.
Perché, come si usa sempre di più della pila, e come vediamo oggi
poi, come si usa sempre di più il mucchio, sicuramente le cose brutte possono accadere.
E infatti, possiamo indurre che intenzionalmente o meno.
Così l'ultima Cliffhanger tempo era questo programma,
che non servire qualsiasi funzionale scopo diverso da quello di dimostrare
come come un ragazzo cattivo può effettivamente prendere vantaggio di bug nel programma di qualcuno
e prendere in consegna un programma o anche un intero sistema di computer o server.
Quindi, solo per un'occhiata brevemente, si notare che principale sul fondo
prende a riga di comando argomenti, come da argv.
E ha una chiamata a una funzione f, essenzialmente una funzione senza nome chiamato
f, e sta passando argv [1].
>> Quindi, qualunque parola l'utente digita in prompt dopo il nome di questo programma,
e poi questa funzione arbitraria up top, f, prende in una stringa, AKA char *,
come abbiamo cominciato a discutere, e appena lo chiama "bar".
Ma potremmo chiamarlo nulla.
E poi dichiara, dentro di f, un array di caratteri
chiamato C-- 12 tali caratteri.
>> Ora, la storia che stavo raccontando un momento fa, dove in memoria
è C, o sono quelli 12 Chars andando a finire?
Giusto per essere chiari.
Sì?
>> PUBBLICO: Sul stack.
>> DAVID J. MALAN: Sulla pila.
Quindi c è una variabile locale.
Stiamo chiedendo per 12 caratteri o 12 byte.
Coloro che stanno per finire il cosiddetto stack.
Ora finalmente è questa altra funzione che è in realtà piuttosto utile,
ma non abbiamo davvero usato noi stessi, strncopy.
Significa copia stringa, ma solo n lettere, n caratteri.
Così n caratteri saranno copiato da bar in c.
E quanti?
La lunghezza della barra.
Quindi, in altre parole, che una linea, strncopy,
sta per copiare efficacemente bar in a c.
>> Ora, giusto per tipo di anticipare la morale di questa storia,
ciò che è potenzialmente problematico qui?
Anche se stiamo controllando la lunghezza di bar e passando in strncopy,
Qual è il tuo intestino dice che si è ancora rotto su questo programma?
Sì?
>> PUBBLICO: Non include spazio per il carattere null.
DAVID J. MALAN: non include spazio per il carattere null.
Potenzialmente, diversamente prassi seguita in passato non lo facciamo nemmeno
avere così tanto come un plus 1 a accogliere tale carattere null.
Ma è ancora peggio di così.
Che altro stiamo fallendo a fare?
Sì?
>> PUBBLICO: [incomprensibile]
DAVID J. MALAN: Perfetto.
Abbiamo hardcoded 12 piuttosto arbitrariamente.
Non è tanto il problema, ma il fatto
che non stiamo nemmeno controllare se la lunghezza della barra è inferiore a 12,
nel qual caso sarà sicuro per metterlo in memoria
chiamato c che abbiamo assegnato.
Infatti, se il bar è come 20 caratteri,
questa funzione sembra essere la copia 20 caratteri da bar in C, quindi
prendere almeno 8 byte che non dovrebbe essere.
Questo è l'implicazione qui.
>> Così, in breve programma, rotto.
Non è come un grande affare.
Forse si ottiene un errore di segmentazione.
Abbiamo avuto tutti i bug nei programmi.
Noi tutti potremmo avere bug nei programmi al momento.
Ma qual è l'implicazione?
Bene, ecco una versione ingrandita di che l'immagine della memoria del mio computer.
Questo è il fondo del mio stack.
E infatti, in fondo è ciò che è chiamato pila di routine genitore, modo elegante
di dire che è principale.
Così che chi chiama la funzione f che stiamo parlando.
Quindi questo è il fondo della pila.
Indirizzo di ritorno è qualcosa di nuovo.
E 'sempre stato lì, sempre in quella foto.
Abbiamo appena mai chiamato l'attenzione ad esso.
Perché si scopre il modo in cui funziona è c che quando una funzione richiama un altro,
non fare solo gli argomenti che funzione get inserito nello stack,
non solo fare locale della funzione variabili vengono inseriti nello stack,
qualcosa chiamato un indirizzo di ritorno Inoltre viene messa in pila.
In particolare, se le chiamate principali Foo, principali di proprio indirizzo in memoria, bue qualcosa,
efficace viene messa in pila in modo che quando f è fatto eseguirlo
sa dove saltare indietro nel testo segmento per continuare l'esecuzione.
>> Quindi, se siamo qui concettualmente, in principale, allora f viene chiamato.
Come fa sapere che f a comando manuale indietro?
Beh, questo piccolo breadcrumb in rosso qui,
chiamato l'indirizzo di ritorno, solo controlli, che cosa è l'indirizzo di ritorno?
Oh, mi permetta di saltare di nuovo alla principale qui.
E questo è un po ' di una semplificazione eccessiva,
perché gli zeri e quelli per principali sono tecnicamente
qui nel segmento tecnologico.
Ma questa è l'idea. f deve solo sapere che cosa
al punto in cui il controllo va infine indietro.
>> Ma i computer modo hanno da tempo stabilito le cose
come variabili locali e argomenti è come questo.
Quindi, nella parte superiore di questa immagine nella blu è lo stack frame per f, quindi tutto
della memoria che f in particolare è in uso.
Quindi di conseguenza, si noti che bar è in questa foto.
Bar era il suo argomento.
E noi dicemmo che gli argomenti a funzioni vengono inseriti nello stack.
E C, naturalmente, è anche in questa foto.
>> E solo per scopi di notazione, notare in alto a sinistra
è quello che sarebbe c staffa 0 e poi leggermente verso il basso a destra
è c staffa 11.
Quindi, in altre parole, si può immaginare che c'è una griglia di byte
lì, prima delle quali è superiore sinistro, inferiore di cui
è l'ultimo di questi 12 byte.
>> Ma ora cercano di avanzare rapidamente.
Cosa sta per accadere se si passa in un bar stringa che è più lungo di c?
E non stiamo controllando se è infatti più lungo di 12.
Quale parte di questo quadro sta per ottenere sovrascritto da byte 0, 1, 2, 3,
dot dot dot, 11, e poi male, 12, 13 fino al 19?
Cosa succederà qui, se ne deducono l'ordine
che c staffa 0 è in alto c staffa 11 è una sorta di basso
a destra?
Sì?
>> PUBBLICO: Beh, sta andando per sovrascrivere il char * bar.
>> DAVID J. MALAN: Sì, sembra che si sta andando a sovrascrivere char * bar.
E peggio ancora, se si invia in un tempo molto lungo stringa, si potrebbe anche sovrascrivere cosa?
L'indirizzo di ritorno.
Che ancora una volta, è come un breadcrumb per dire al programma dove
per andare indietro a quando f è fatto di essere chiamato.
>> Così che cosa cattivi di solito fare è se si imbattono in un programma
che sono curioso di sapere se è sfruttabile, buggy in modo tale
che lui o lei può prendere vantaggio di tale bug,
generalmente non ottengono questo diritto la prima volta.
Hanno appena iniziare a inviare, per esempio, stringhe casuali nel vostro programma,
se alla tastiera, o francamente probabilmente
scrivere un piccolo programma di appena generano automaticamente le stringhe,
e iniziare a battere il tuo programma l'invio in un sacco di input diversi
a diverse lunghezze.
>> Non appena il tuo programma va in crash, questa è una cosa incredibile.
Perché vuol dire che o lei ha scoperto
quello che probabilmente è davvero un bug.
E poi si possono ottenere più intelligente e iniziare a concentrarsi più strettamente
su come sfruttare il bug.
In particolare, quello che lui o lei potrebbe fare è inviare, nel migliore dei casi, ciao.
No big deal.
E 'una stringa che è sufficientemente breve.
Ma cosa succede se lui o lei manda, e noi generalizziamo come,
attacco code-- così zeri e quelli che fanno cose
come rm-rf, che rimuovere tutto ciò dal disco rigido o inviare spam
o in qualche modo attaccare la macchina?
>> Quindi, se ciascuno di questi lettere A solo rappresenta,
concettualmente, attaccare, attaccare, attacco, attacco, codice cattivo
che qualcun altro ha scritto, ma se quella persona è abbastanza intelligente
non solo di includere tutti di quei RM-RFS, ma anche
avere i suoi ultimi byte essere un numero che corrisponde
l'indirizzo del suo o il proprio codice di attacco
che lui o lei passava in appena fornendo al prompt,
si può effettivamente ingannare il computer nel notare quando f è fatto esecuzione,
oh, è il momento per me di saltare torna l'indirizzo di ritorno rossa.
Ma perché lui o lei ha in qualche modo sovrapposte che indirizzo di ritorno
con il proprio numero, e sono abbastanza intelligente
di aver configurato che il numero di riferimento, come si
vedere nel super top angolo sinistro lì,
l'indirizzo effettivo nel computer la memoria di una parte del loro codice di attacco,
un cattivo ragazzo può ingannare il computer ad eseguire il proprio codice.
>> E quel codice, ancora una volta, può essere qualsiasi cosa.
E 'generalmente chiamato codice shell, che è solo
un modo per dire che non è generalmente qualcosa di semplice come rm-rf.
In realtà è qualcosa di simile a Bash, o un vero programma che gli dà
o il suo controllo programmatico per eseguire qualsiasi altra cosa che vogliono.
Così, in breve, tutto questo deriva dal semplice fatto
che questo bug coinvolto non controllare i confini della propria matrice.
E perché il modo computer lavoro è che essi
utilizzare lo stack da efficace, concettualmente,
bottom su un massimo, ma poi gli elementi si spinge nello stack crescere verso il basso,
questo è incredibilmente problematico.
Ora, ci sono modi per aggirare questo.
E, francamente, ci sono lingue con cui risolvere questo.
Java è immune, per esempio, a questo particolare problema.
Perché non ti danno i puntatori.
Non danno si indirizzi di memoria diretta.
Quindi, con questo potere che abbiamo toccare niente in memoria
noi vogliamo arriva, è vero, grande rischio.
>> Quindi tenete gli occhi aperti.
Se, francamente, nei mesi o anni a venire, in qualsiasi momento
si legge su alcuni sfruttamento di un programma o di un server,
se avete mai visto un accenno di qualcosa come un attacco di buffer overflow,
o overflow dello stack è un altro tipo di attacco, simile nello spirito,
quanto ispira il sito web del nome, se lo si conosce,
è tutto parlando solo traboccante la dimensione di qualche personaggio
array o alcune serie più in generale.
Hai domande, poi, su questo?
Non provateci a casa.
>> Bene.
Quindi malloc finora è stato il nostro nuovo amico in che siamo in grado di allocare memoria
che non necessariamente sapere in avanziamo che vogliamo così non abbiamo
codificare nel nostro numeri di programma come 12.
Una volta che l'utente ci dice quanto Dati lui o lei vuole di ingresso,
possiamo malloc che la quantità di memoria.
>> Così malloc si scopre, per la misura abbiamo usato esso,
esplicitamente l'ultima volta, e poi voi ragazzi sono state usando
per GetString inconsapevolmente per diverse settimane, tutti della memoria di malloc
deriva dal cosiddetto heap.
Ed è per questo getString, per esempio, può allocare memoria dinamicamente
senza sapere cosa si sta andando a digitare in anticipo,
si restituire un puntatore a quel ricordo, e che la memoria è ancora il vostro da mantenere,
anche dopo getString ritorni.
Perché richiamo dopo tutto quello che il pila è costantemente andando su e giù,
su e giù.
E appena va verso il basso, che significa qualsiasi memoria
questa funzione utilizzata dovrebbe non essere utilizzato da chiunque altro.
Si tratta di valori di immondizia ora.
>> Ma l'heap è qui.
E cosa c'è di bello malloc è che quando malloc alloca la memoria qui,
non è influenzato, per la maggior parte, dallo stack.
E così ogni funzione può accedere memoria che è stata malloc'd,
anche da una funzione come getString, anche dopo che è restituito.
>> Ora, il contrario di malloc è gratuito.
E infatti, la regola necessario avviare l'adozione di
è qualsiasi, qualsiasi, ogni volta che si utilizza malloc è necessario te stesso uso gratuito, alla fine,
sullo stesso puntatore.
Per tutto questo tempo abbiamo scriviamo buggy, codice buggy, per molte ragioni.
Ma uno dei quali è stato utilizzando la libreria CS50, che
si è volutamente buggy, si perde la memoria.
Ogni volta che hai chiamato getString nelle ultime settimane
stiamo chiedendo il funzionamento sistema, Linux, per la memoria.
E non avete mai dato una volta indietro.
E questo non è, in in pratica, una buona cosa.
>> E Valgrind, uno dei strumenti introdotti in Pset 4,
è tutto su di te aiutare ora trovare bug del genere.
Ma fortunatamente per Pset 4 non è necessario utilizzare la libreria CS50 o getString.
Quindi eventuali bug relativi alla memoria sono in ultima analisi, sta per essere il vostro.
>> Quindi malloc è più di un semplice conveniente per questo scopo.
Possiamo davvero ora di risolvere fondamentalmente diversi problemi,
e fondamentalmente risolvere i problemi più efficacemente come da promessa settimana zeri.
Finora questo è il più sexy struttura dati che abbiamo avuto.
E da struttura di dati Volevo solo dire un modo di memoria concettualizzare
in un modo che va oltre solo dicendo, questo è un int, questo è un char.
Possiamo iniziare a cose del cluster insieme.
>> Quindi un array sembrava questo.
E quello che era fondamentale in circa array è che ti dà
back-to-back pezzi di memoria, ciascuno dei quali
sta per essere dello stesso tipo, int, int, int, int, o char, char, char,
char.
Ma ci sono alcuni aspetti negativi.
Questo, per esempio, è un array di dimensione sei.
Supponiamo di riempire questo array con sei numeri e poi, per qualsiasi motivo,
l'utente vuole dare si un settimo numero.
Dove la metti?
>> Qual è la soluzione se si dispone di creato un array in pila,
per esempio, solo con la settimana due notazione che abbiamo introdotto,
di parentesi quadre con un numero dentro?
Beh, hai sei numeri in queste caselle.
Quali sarebbero i tuoi istinti essere?
Dove vorreste dire?
>> PUBBLICO: [incomprensibile]
>> DAVID J. MALAN: Ci dispiace?
>> PUBBLICO: Mettere sul fine.
>> DAVID J. MALAN: Metti sul fine.
Quindi poco più a destra, al di fuori di questa casella.
Quale sarebbe bello, ma risulta non è possibile farlo.
Perché se non hai chiesto per questo pezzo di memoria,
potrebbe essere una coincidenza che questa viene utilizzato da qualche altra variabile
del tutto.
Pensate di una settimana o giù di lì, quando abbiamo posto i nomi Zamyla e Davin e Gabe di
in memoria.
Erano letteralmente back to back to back.
Quindi non possiamo necessariamente fiducia che tutto ciò che di
qui è disponibile per me da usare.
>> Quindi, che cosa potrebbe fare?
Beh, una volta che la realizzazione bisogno di un array di dimensione sette,
si può solo creare un array di dimensione sette quindi utilizzare
un ciclo for o un ciclo while, copiarlo nella nuova matrice,
e quindi in qualche modo solo sbarazzarsi di questo array o semplicemente smettere di usarlo.
Ma non è particolarmente efficiente.
In breve, gli array non lasciare si ridimensiona dinamicamente.
>> Così da un lato si ottiene accesso casuale, che è incredibile.
Perché ci permette di fare cose come divide et impera,
ricerca binaria, tutti di che abbiamo parlato sullo schermo qui.
Ma si dipinge da soli in un angolo.
Non appena si preme la fine della matrice,
devi fare molto un'operazione costosa
o scrivere un sacco di codice per ora affrontare tale problema.
>> Così che cosa se invece avessimo qualcosa chiamato un elenco,
o una lista concatenata in particolare?
Che cosa succede se invece di avere rettangoli back to back to back,
abbiamo rettangoli che lasciano un po ' po 'di spazio di manovra tra di loro?
E anche se ho disegnato questo foto o adattato questa immagine
da uno dei testi qui per tornare alla back to back molto ordinata, in realtà,
uno di quei rettangoli potrebbe essere qui in memoria.
Uno di loro potrebbe essere qui.
Uno di loro potrebbe essere qui, qui, e così via.
>> Ma cosa succede se abbiamo pareggiato, in questo caso, frecce
che in qualche modo collegare questi rettangoli insieme?
Infatti, abbiamo visto un tecnico incarnazione di una freccia.
Cosa abbiamo utilizzato negli ultimi giorni che, sotto la cappa,
è rappresentativo di una freccia?
Un puntatore, giusto?
>> Così che cosa se, invece di basta memorizzare i numeri,
come 9, 17, 22, 26, 34, quello che se non memorizzato
solo un numero ma un puntatore accanto a ogni tale numero?
Così tanto come si farebbe infilare un ago attraverso un sacco di tessuto,
le cose in qualche modo di legatura insieme, allo stesso modo può
noi con i puntatori, come incarnata da frecce qui,
tipo di tessere insieme questi singoli rettangoli
da efficace utilizzando un puntatore accanto a ciascun numero
punti a qualche numero successivo, che punti a, a sua volta, qualche numero successivo?
In altre parole, ciò se davvero volessimo
di implementare qualcosa di simile?
Ebbene, purtroppo, questi rettangoli, almeno quella con 9, 17, 22,
e così via, questi non sono più belle piazze con numeri singoli.
Il fondo, rettangolo inferiore a 9, per esempio,
rappresenta ciò che dovrebbe essere un puntatore, 32 bit.
Ora, io non sono ancora a conoscenza di qualsiasi tipo di dati in C che offre non solo un int
tuttavia il puntatore del tutto.
>> Quindi qual è la soluzione, se vogliamo a inventare la nostra risposta a questo?
Sì?
>> PUBBLICO: [incomprensibile]
>> DAVID J. MALAN: Che cos'è?
>> PUBBLICO: Nuova struttura.
>> DAVID J. MALAN: Sì, quindi perché Non creiamo una nuova struttura,
o in C, una struttura?
Abbiamo visto le strutture prima, se per breve tempo, dove abbiamo affrontato con una struttura studente
come questo, che aveva un nome e una casa.
In Pset 3 breakout si usa un intero mazzo di GRect structs-- e GOvals
che Stanford creato per informazioni sul cluster insieme.
Così che cosa se prendiamo questa stessa idea di le parole chiave "typedef" e "struct"
e poi alcune cose specifiche per studente, ed evolvere questo in quanto segue:
typedef struct node-- e il nodo è solo un computer science molto generico
termine per qualcosa in una struttura di dati, un contenitore in una struttura dati.
Un nodo Rivendico sta per avere un int n, del tutto semplice,
e poi un po 'più criptico, questa seconda linea, nodo struct * prossimo.
Ma in termini meno tecnici, che cosa è che seconda linea
di codice all'interno delle parentesi graffe?
Sì?
>> PUBBLICO: [incomprensibile]
DAVID J. MALAN: A puntatore a un altro nodo.
Quindi è vero, la sintassi un po 'criptica.
Ma se lo si legge alla lettera, successivo è il nome di una variabile.
Qual è il suo tipo di dati?
E 'un po' prolissa questa volta, ma è di tipo struct nodo *.
Ogni volta che abbiamo visto qualcosa di stella, che significa che è un puntatore a quel tipo di dati.
Così la prossima è apparentemente un puntatore ad una struct nodo.
>> Ora, che cosa è un nodo struct?
Beh, nota vedete quelle stesse parole in alto a destra.
E in effetti, si vede anche la parola "Nodo" qui in basso a sinistra.
E questo è in realtà solo una comodità.
Si noti che nella nostra definizione studente c'è la parola "studente" solo una volta.
E questo perché uno studente oggetto non era autoreferenziale.
Non c'è nulla all'interno di uno studente che deve puntare a un altro studente,
persay.
Sarebbe una sorta di strano nel mondo reale.
>> Ma con un nodo in una collegata lista, noi vogliamo un nodo
essere referenziale di un oggetto simile.
E così notare il cambiamento qui non è solo ciò che c'è dentro le parentesi graffe.
Ma aggiungiamo la parola "nodo" nella parte superiore e
aggiungendo al fondo in luogo di "studente".
E questo è solo un dettaglio tecnico in modo che, ancora una volta, la struttura dati
può essere auto-referenziale, in modo che un nodo può puntare ad un altro tale nodo.
>> Così che cosa è questo in definitiva andando a significare per noi?
Beh, si, questa roba dentro è il contenuto del nostro nodo.
Questa cosa qui, in alto a destra, è proprio così
che, ancora una volta, si può fare riferimento a noi stessi.
E poi la roba più esterno, anche se il nodo è un nuovo termine,
forse, è ancora il stesso come studente e quello
era sotto il cofano in SPL.
>> Quindi, se ora volevamo iniziare l'attuazione del presente lista collegata,
come potremmo tradurre qualcosa di simile al codice?
Beh, diciamo solo vedere un esempio di un programma che
in realtà utilizza una lista collegata.
Tra il codice di distribuzione di oggi è un programma chiamato List Zero.
E se corro questo ho creato un super semplice GUI, Graphical User Interface,
ma è davvero solo printf.
E ora io stesso ho dato un paio di menu options-- Delete, Insert, Ricerca,
e Traverse.
E Quit.
Questi sono solo operazioni comuni in un struttura dati nota come un elenco di link.
>> Ora, Elimina sta per eliminare un numero dalla lista.
Inserisci sta per aggiungere un numero all'elenco.
Ricerca sta a guardare per numero nell'elenco.
E traversata è solo un modo di fantasia di dire, a piedi attraverso la lista,
stamparlo, ma questo è tutto.
Non modificare in alcun modo.
>> Quindi proviamo questo.
Andiamo avanti e digitare 2.
E poi ho intenzione di inserire il numero, dire 9.
Invio.
E ora il mio programma è solo programmato per dire, la lista è ora 9.
Ora, se vado avanti e non inserire di nuovo, lasciare
andare avanti e Zoom indietro e digitare 17.
Ora la mia lista è 9, quindi 17.
Se lo faccio inserire di nuovo, cerchiamo di saltare uno.
Invece di 22, secondo l'immagine che abbiamo stato a guardare qui, mi permetta di saltare avanti
e inserire 26 successivo.
Quindi ho intenzione di digitare 26.
La lista è come mi aspetto.
Ma ora, solo per vedere se questo codice sta per essere flessibile, lasciami ora
tipo 22, che almeno concettualmente, se siamo
Tenendo questo allineati, che è davvero sarà un altro obiettivo in questo momento,
dovrebbe andare tra 17 e 26.
Così ho colpito Invio.
Infatti, che funziona.
E così ora lasciatemi inserisco l' ultimo, per l'immagine, 34.
>> Bene.
Quindi per ora mi permetta di stabilire che Elimina e Traverse e ricerca fanno,
infatti, lavorare.
In realtà, se non me ne corro Cerca, cerchiamo di cercare il numero 22, Enter.
Ha trovato 22.
Quindi questo è ciò che questo programma Lista Zero fa.
>> Ma ciò che sta realmente succedendo su che implementa questo?
Beh, prima avrei potuto, e anzi Io ce l'ho, un file chiamato list0.h.
E da qualche parte c'è questo linea, typedef, struct nodo,
poi ho i miei parentesi graffe, int n, e allora struct-- qual era la definizione?
Struct node successivo.
Quindi abbiamo bisogno della stella.
Ora tecnicamente entriamo in l'abitudine di disegnare qui.
Si potrebbe vedere i libri di testo e riferimenti online fanno lì.
E 'funzionalmente equivalente.
In realtà, questo è un po 'più tipico.
Ma sarò coerente con quanto abbiamo fatto l'ultima volta e facciamo.
E poi, infine, ho intenzione di fare questo.
>> Quindi, in un file di intestazione da qualche parte, in list0.h
oggi è questa definizione struct, e forse alcune altre cose.
Intanto in list0c c'è sta per essere un paio di cose.
Ma stiamo andando a poco cominciare e non finire questo.
List0.h è un file che voglio di includere nel mio file C.
E poi ad un certo punto sono andando ad avere int, principale, annullare.
E poi ho intenzione di hanno qualche cosa da fare è qui.
Ho anche intenzione di avere un prototipo, come il vuoto, la ricerca, int,
n, il cui scopo nella vita è per la ricerca di un elemento.
E poi qui rivendico in codice di oggi, vuoto, di ricerca, int, n,
nessun punto e virgola ma parentesi graffe aperte.
Ed ora voglio cercare in qualche modo per un elemento in questo elenco.
Ma non abbiamo abbastanza informazioni sullo schermo ancora.
Non ho in realtà rappresentato la lista stessa.
Quindi un modo che potremmo implementare una lista collegata a un programma
è che tipo di voglia di fare qualcosa come dichiaro collegati elenco qui.
Per semplicità, ho intenzione di fare questo mondiale, anche se in generale si
non dovrebbe fare questo troppo.
Ma sarà semplificare questo esempio.
Quindi voglio dichiarare una lista collegata qui.
Ora, come potrei farlo?
>> Ecco l'immagine di una lista collegata.
E non ho davvero so al momento come
Ho intenzione di andare su rappresentanza tante cose con un solo
variabile in memoria.
Ma ripensare un attimo.
Per tutto questo tempo abbiamo avuto corde, che poi
rivelata matrici di personaggi, che poi
rivelata solo un puntatore al primo carattere
in un array di caratteri che è nullo terminato.
Così da questa logica, e con questo immagine tipo di semina vostri pensieri,
Che bisogno abbiamo effettivamente scriviamo nel nostro codice per rappresentare una lista concatenata?
Quanto di queste informazioni abbiamo bisogno per catturare in codice C, diresti?
Sì?
>> PUBBLICO: Abbiamo bisogno di un puntatore a un nodo.
DAVID J. MALAN: Un puntatore a un nodo.
In particolare, quale nodo sarebbe la tua istinti essere quello di mantenere un puntatore a?
>> PUBBLICO: Il primo nodo.
>> DAVID J. MALAN: Sì, probabilmente solo il primo.
E notare, il primo nodo è una forma diversa.
E 'solo la metà della dimensione della struttura, perché è davvero solo un puntatore.
Che cosa si può davvero fare è dichiarare una lista collegata di essere nodo di tipo *.
E facciamo solo chiamano prima e inizializzarla a null.
Quindi nulla, ancora una volta, è venuta nella foto qui.
Non solo è nullo utilizzato come come una speciale valore di ritorno per le cose come getString
e malloc, null è anche lo zero puntatore, la mancanza di un puntatore,
se si vuole.
Significa solo nulla è ancora qui.
Ora prima, avrei potuto chiamato questo nulla.
Avrei potuto chiamato "lista" o un qualsiasi numero di altre cose.
Ma sto chiamando "prima" in modo che Linee it up con questa immagine.
Quindi, proprio come una stringa può essere rappresentato con l'indirizzo del primo byte,
così può una lista collegata.
E vedremo altri dati Strutture essere rappresentati
con un solo puntatore, una freccia a 32 bit, che indica
al primo nodo della struttura.
>> Ma ora cerchiamo di anticipare un problema.
Se sto solo ricordando nel mio programma l'indirizzo
del primo nodo, il primo rettangolo in questa struttura dati,
quello che era meglio essere il caso per il l'attuazione del resto della mia lista?
Che cosa è un dettaglio fondamentale che sta succedendo per garantire questo funziona davvero?
E per "funziona davvero" I media, molto simile a una corda,
ci lascia andare dal primo carattere in nome di Davin al secondo,
al terzo, al quarto, fino alla fine,
come facciamo a sapere quando siamo alla fine di una lista collegata che assomiglia a questo?
Quando è nullo.
E ho rappresentato questa sorta di come come una forza ingegnere elettrico,
con la piccola messa a terra simbolo, di sorta.
Ma che vuol dire proprio nulla in questo caso.
Si può disegnare qualsiasi numero di modi, ma questo autore
è successo a utilizzare questo simbolo qui.
>> Finché stiamo tesatura tutti questi nodi insieme,
solo ricordare dove il primo è, così a lungo
come abbiamo messo un simbolo speciale l'ultimo nodo della lista,
e useremo nulla, perché è quello che abbiamo a nostra disposizione,
questo elenco è completo.
E anche se io solo darvi un puntatore a il primo elemento, si, il programmatore,
può certamente accedere al resto.
Ma lasciamo le vostre menti vagare un po ',
se non sono già abbastanza wandered-- ciò che è
sarà il tempo di esecuzione di trovare nulla in questa lista?
Dannazione, è grande O di n, che non è male, in tutta onestà.
Ma è lineare.
Abbiamo dato a ciò caratteristica di array spostando più
verso questa immagine di dinamica tessuti insieme o nodi collegati?
Abbiamo dato l'accesso casuale.
Un array è bello perché matematicamente tutto
è back to back to back to back.
Anche se questa immagine sembra piuttosto, e anche
anche se sembra che questi nodi sono ben distanziati, in realtà
potrebbero essere ovunque.
OX1, Ox50, Ox123, Ox99, questi nodi potrebbero essere ovunque.
Poiché malloc fa allocare memoria dal mucchio, ma ovunque nel mucchio.
Non necessariamente sapere che è sta per essere back to back to back.
E così questa immagine nella realtà di non andare a essere abbastanza questa bella.
>> Così sta andando a prendere un po 'di lavorare per implementare questa funzione.
Quindi cerchiamo di implementare la ricerca adesso.
E vedremo una specie di modo intelligente di fare questo.
Quindi se io sono una funzione di ricerca e Ho dato una variabile, intero n
a cercare, ho bisogno di sapere il nuova sintassi per guardare dentro
di una struttura che è indicato, per trovare n.
Quindi cerchiamo di fare questo.
>> Così prima ho intenzione di andare avanti e dichiarare un nodo *.
E ho intenzione di chiamare puntatore, solo per convenzione.
E ho intenzione di inizializzare a prima.
E ora posso fare questo in un numero di modi.
Ma ho intenzione di adottare un approccio comune.
Mentre puntatore non è uguale a nullo, e questo è sintassi valida.
E significa solo fare il seguente, così Finché non sei che punta a nulla.
Cosa voglio fare?
>> Se il puntatore dot n, mi permetta di tornare a che, equals-- uguale cosa?
Che valore sto cercando?
L'attuale n che è stato passato in.
Quindi, ecco un'altra caratteristica di C e di molte lingue.
Anche se il nodo struttura chiamata ha un valore n, totalmente legittimo
di avere anche un argomento locale o variabile chiamata n.
Perché anche noi, con occhi umani, riescono a distinguere
che questo n è presumibilmente diverso da questo n.
Poiché la sintassi è diversa.
Hai un punto e un puntatore, che ciò si ha nulla di simile.
Quindi questo è OK.
Questo è OK per chiamare loro le stesse cose.
>> Se io vi trovo, io sono andando a voler fare qualcosa
come annunciamo che abbiamo trovato n.
E lasceremo che come commento o codice pseudocodice.
Else, ed ecco la parte interessante, cosa
voglio fare se il nodo corrente non contenente n che mi interessa?
Come faccio a raggiungere i seguenti?
Se il mio dito contro il momento è PTR, ed è
che punta a qualsiasi prima è puntato verso,
come faccio a spostare il dito al nodo successivo nel codice?
Ebbene, qual è il breadcrumb siamo andando a seguire in questo caso?
PUBBLICO: [incomprensibile].
DAVID J. MALAN: Sì, così la prossima.
Quindi, se torno al mio codice qui, anzi, io sono
intenzione di andare avanti e dire pointer, che è solo un variable-- temporanea è
un nome strano, ptr, ma è proprio come temp--
Ho intenzione di impostare il puntatore uguale a qualsiasi puntatore è--
e di nuovo, questo sta andando essere un poco buggy per un punto moment-- successivo.
In altre parole, io vado a prendere la mia dito che sta puntando a questo nodo
qui e ho intenzione di dire, sai cosa, dare un'occhiata al campo successivo
e spostare il dito per come diavolo si punta a.
E questo sta per ripetere, ripetere, ripetere.
Ma quando lo fa il mio dito smettere di fare qualcosa?
Appena quale linea di calci di codice in?
PUBBLICO: [incomprensibile]
DAVID J. MALAN: Se il punto mentre puntatore non è uguale a null.
Ad un certo punto il mio dito del sta per essere punta a nulla
e ho intenzione di realizzare che è la fine di questo elenco.
Ora, questo è un po bugia bianca per semplicità.
Si scopre che anche se abbiamo appena appreso questa notazione dot
per le strutture, il puntatore non è una struct.
ptr è ciò?
Giusto per essere più pignoli.
E 'un puntatore a un nodo.
Non è un nodo stesso.
Se non avevo stella qui, puntatore absolutely-- si tratta di un nodo.
Questo è come una settimana la dichiarazione di una variabile,
anche se la parola "nodo" è nuovo.
>> Ma non appena si introduce un stella, è ora un puntatore a un nodo.
E purtroppo non è possibile utilizzare la notazione dot per un puntatore.
Devi usare la freccia notazione, che, sorprendentemente,
è la prima volta ogni pezzo di sintassi sembra intuitivo.
Questo appare letteralmente come una freccia.
E così che è una buona cosa.
E qui, letteralmente si presenta come una freccia.
Quindi penso che sia il la-- non lo faccio penso che io sto troppo commettere qui-- I
credo che sia l'ultimo nuovo pezzo di sintassi che andremo a vedere.
E per fortuna, è infatti un po 'più intuitivo.
>> Ora, per quelli di voi che potrebbe preferire il vecchio modo,
è comunque possibile utilizzare la notazione del punto.
Ma, come per ogni lunedì di conversazione, abbiamo prima
bisogno di andare lì, andare a quella affrontare, e quindi accedere al campo.
Quindi questo è anche corretto.
E, francamente, questo è un poco più pedante.
Stai dicendo letteralmente, dereferenziare il puntatore e andare lì.
Poi afferrare .n, il campo denominato n.
Ma francamente, nessuno vuole digitare o leggere questo.
E così il mondo inventato la notazione freccia, che
è equivalente, identico, è solo zucchero sintattico.
Quindi un modo elegante per dire questo guarda meglio, o sembra più semplice.
>> Così ora ho intenzione di fare un'altra cosa.
Io vado a dire "rompere" una volta ho trovato così non tengo in cerca di esso.
Ma questo è il succo di una funzione di ricerca.
Ma è molto più facile, in fine, non a piedi attraverso il codice.
Questo è infatti l'implementazione formale di ricerca in codice della distribuzione di oggi.
Oserei dire che inserto non è particolarmente divertente camminare attraverso
visivamente, né è eliminare, anche se al termine della giornata
si riducono a abbastanza euristiche semplici.
>> Quindi cerchiamo di fare questo.
Se ti umorismo me qui, ho fatto portare un mucchio di palle di stress.
Ho portato un po 'di numeri.
E abbiamo potuto ottenere solo pochi volontari per rappresentare 9, 17, 20, 22, 29, e 34?
Quindi in sostanza tutti che è qui oggi.
Quello era uno, due, tre, quattro, cinque, sei persone.
E mi è stato chiesto di go-- vedere, non uno nella parte posteriore solleva le mani.
OK, uno, due, tre, quattro, five-- fammi caricare balance-- sei.
OK, tu sei venuto in su.
Avremo bisogno di altre persone.
Abbiamo portato le palle stress supplementare.
E se si potesse, per solo un attimo, linea
voi stessi su appena come questa immagine qui.
>> Bene.
Vediamo, qual è il tuo nome?
>> PUBBLICO: Andrew.
>> DAVID J. MALAN: Andrew, sei il numero 9.
Piacere di conoscerti.
Ecco qui.
PUBBLICO: Jen.
DAVID J. MALAN: Jen.
David.
Numero 17.
Sì?
>> PUBBLICO: Sono Julia.
>> DAVID J. MALAN: Julia, David.
Numero 20.
PUBBLICO: Christian.
DAVID J. MALAN: Christian, David.
Numero 22.
E?
>> PUBBLICO: JP.
DAVID J. MALAN: JP.
Numero 29.
Quindi, andare avanti e ottenere dentro-- Uh oh.
Uh oh.
Standby.
20.
Qualcuno ha un pennarello?
PUBBLICO: Ho un pennarello.
DAVID J. MALAN: Hai un pennarello?
Ok.
E qualcuno ha un pezzo di carta?
Salvare la lezione.
Dai.
PUBBLICO: l'abbiamo.
DAVID J. MALAN: Abbiamo capito?
Va bene, grazie.
Eccoci qui.
Era questo da voi?
Hai appena salvato la giornata.
Così 29.
Bene.
Ho scritto male 29, ma OK.
Vai avanti.
Va bene, ti darò la penna torna momentaneamente.
Così abbiamo queste persone qui.
Facciamo un altro.
Gabe, vuoi per giocare il primo elemento qui?
Avremo bisogno di puntare a queste belle persone.
Quindi 9, 17, 20, 22, specie di 29, e poi 34.
Abbiamo perso qualcuno?
Ho un 34.
Dove did-- OK, chi vuole essere 34?
OK, andiamo su, 34.
Va bene, questo sarà vale la pena il culmine.
Come ti chiami?
>> PUBBLICO: Peter.
>> DAVID J. MALAN: Peter, vieni su.
Va bene, quindi ecco una tutta una serie di nodi.
Ognuno di voi rappresenta uno di questi rettangoli.
E Gabe, il po 'strano Man Out, rappresenta il primo.
Così il suo puntatore è un po 'più piccola sullo schermo di tutti gli altri.
E in questo caso, ognuno di sinistra mani sta per entrambi puntare verso il basso,
rappresentando quindi nullo, così solo l'assenza di un puntatore,
o che sta per essere puntamento ad un nodo accanto a voi.
>> Così adesso, se si adornano voi stessi come l'immagine
qui, andare avanti e punto a vicenda, con Gabe
in particolare che punta a numero 9 per rappresentare la lista.
OK, e il numero 34, la mano sinistra deve solo essere puntato verso il pavimento.
>> OK, quindi questa è la lista collegata.
Quindi questo è lo scenario in questione.
E in effetti, questo è rappresentativo di una classe di problemi
che si potrebbe provare a risolvere con il codice.
Si desidera inserire definitiva un nuovo elemento nella lista.
In questo caso, stiamo andando a provare a inserire il numero 55.
Ma ci sara ' diversi casi da considerare.
E in effetti, questo sta per essere uno del big-picture take away qui, è,
quali sono i diversi casi.
Quali sono i diversi se le condizioni o rami che il programma potrebbe avere?
>> Ebbene, il numero che si sta cercando di inserto, che ora sappiamo essere 55,
ma se non lo sapevate in anticipo, oserei dire
cade in almeno tre possibili situazioni.
Quando un nuovo elemento potrebbe essere?
PUBBLICO: E la fine o medio.
DAVID J. MALAN: Alla fine, in mezzo, o all'inizio.
Quindi io sostengo che ci sia almeno tre problemi che devono risolvere.
Scegliamo ciò che è forse probabilmente il più semplice
uno, dove il nuovo elemento appartiene all'inizio.
Quindi ho intenzione di avere il codice abbastanza come la ricerca, che ho appena scritto.
E ho intenzione di avere ptr, che Io rappresento qui con il mio dito,
come di solito.
>> E ricordate, che valore abbiamo inizializziamo ptr a?
Così abbiamo inizializzato a NULL inizialmente.
Ma allora cosa abbiamo fatto una volta erano all'interno della nostra funzione di ricerca?
Abbiamo impostato uguale a prima, che non significa fare questo.
Se ho impostato ptr uguale alla prima, che cosa dovrebbe davvero essere la mia mano che punta a?
Destra.
Quindi, se Gabe e io stiamo andando essere valori uguali qui,
abbiamo bisogno di entrambi punto al numero 9.
>> Quindi questo è stato l'inizio della nostra storia.
E ora questo è solo semplice, anche se la sintassi è nuovo.
Concettualmente questo è solo ricerca lineare.
Is 55, pari al 9?
O meglio, diciamo meno di 9.
Perché io sto cercando di capire dove mettere 55.
Meno 9, meno di 17, meno di 20, meno di 22, meno di 29,
meno di 34, no.
Così ora siamo nel caso uno degli almeno tre.
>> Se voglio inserire 55 qui, cosa righe di codice per necessità vengono eseguiti?
Come funziona questo quadro di gli esseri umani hanno bisogno di cambiare?
Cosa devo fare con la mia mano sinistra?
Questo dovrebbe essere nullo inizialmente, perché io sono alla fine della lista.
E che cosa dovrebbe accadere qui con Peter, vero?
Lui, ovviamente, andando a puntare a me.
Quindi io rivendico ci sono almeno due linee di codice nel codice di esempio da oggi
che sta per implementare questa scenario di aggiungere 55 alla coda.
E potrei avere qualcuno hop e solo rappresentano il 55?
Va bene, tu sei il nuovo 55.
>> Così ora che cosa se il prossimo scenario arriva,
e vogliamo inserire al inizio o il capo di questa lista?
E qual è il tuo nome, il numero 55?
>> PUBBLICO: Jack.
>> DAVID J. MALAN: Jack?
OK, piacere di conoscerti.
Benvenuto a bordo.
Così ora stiamo andando a inserire, per esempio, il numero 5.
Ecco il secondo caso del tre siamo arrivati ​​a prima.
Quindi, se 5 appartiene all'inizio, vediamo come troviamo che fuori.
Io inizializzo il mio ptr puntatore al numero 9 di nuovo.
E mi sono reso conto, oh, 5 è inferiore a 9.
Quindi fissare questa immagine per noi.
Le cui mani, Gabe di David o di o- qual è il nome del numero 9?
>> PUBBLICO: Jen.
>> DAVID J. MALAN: hands-- di Jen che delle nostre mani hanno bisogno di cambiare?
OK, così Gabe indica a che ora?
A me.
Sono il nuovo nodo.
Quindi mi limiterò solo tipo di movimento qui per vedere visivamente.
E intanto quello che faccio che punto?
Ancora dove sto indicando.
Quindi questo è tutto.
Quindi basta davvero una linea di correzioni di codice questo particolare problema, sembrerebbe.
Va bene, quindi questo è un bene.
E qualcuno può essere un segnaposto per 5?
Andiamo su.
Ti porteremo la prossima volta.
>> Va bene, così now-- e Per inciso, i nomi
Non sto facendo esplicita menzione del diritto ora, pred puntatore, puntatore predecessore
e nuovo puntatore, che è solo i nomi dato
nel codice di esempio per i puntatori o le mie mani che è tipo di punta intorno.
Come ti chiami?
>> PUBBLICO: Christine.
>> DAVID J. MALAN: Christine.
Benvenuto a bordo.
Va bene, quindi consideriamo ora uno scenario leggermente più fastidioso,
in base al quale voglio inserire qualcosa come 26 in questo.
20?
Che cosa?
Questi are-- buona cosa che abbiamo questa penna.
Va bene, 20.
Se qualcuno potrebbe ottenere un altro pezzo di carta pronto, giusto in case-- tutto bene.
Oh, interessante.
Beh, questo è un esempio di un bug lezione.
OK così che cosa è nuovo il tuo nome?
PUBBLICO: Julia.
DAVID J. MALAN: Julia, si può pop fuori e far finta che eri mai lì?
OK, questo non è mai accaduto.
Grazie.
Quindi supponiamo di voler inserire Julia in questa lista collegata.
Lei è la numero 20.
E naturalmente lei è intenzione di appartenere alla
begin-- ancora non puntare a qualche cosa.
Così la vostra mano può essere di tipo giù nullo o un valore spazzatura.
Diciamo la storia veloce.
Sto puntando al numero 5 questa volta.
Poi verifico 9.
Poi posso controllare 17.
Poi posso controllare 22.
E mi rendo conto, ooh, Julia deve andare prima del 22.
Così che cosa deve accadere?
Le cui mani hanno bisogno di cambiare?
Julia, la mia, o- cosa c'è di nuovo il tuo nome?
>> PUBBLICO: Christian.
>> DAVID J. MALAN: cristiano o?
>> PUBBLICO: Andy.
>> DAVID J. MALAN: Andy.
Cristiano o Andy?
Andy deve puntare a?
Julia.
Bene.
Così Andy, vuoi puntare a Julia?
Ma aspettate un minuto.
Nella storia finora, Io sono il tipo di una
responsabile, nel senso che puntatore è la cosa che è
si muove attraverso la lista.
Potremmo avere un nome per Andy, ma non c'è variabile chiamata Andy.
L'unica altra variabile che abbiamo è prima, che è rappresentato da Gabe.
>> Quindi questo è in realtà il motivo per cui così Fino ad ora non abbiamo bisogno di questo.
Ma ora sullo schermo c'è parlare di nuovo di puntatore pred.
Permettetemi di essere più esplicito.
Se questo è il puntatore, ho avuto meglio ottenere un po 'più intelligente
sul mio iterazione.
Se non ti dispiace il mio andare di qui di nuovo, indicando qui, indicando qui.
Ma mi permetta di avere un puntatore pred, puntatore predecessore, che è
tipo di punta verso la elemento Ero solo a.
Così quando vado qui, ora i miei aggiornamenti mano sinistra.
Quando vado qui i miei aggiornamenti della mano sinistra.
E ora non ho solo un puntatore a l'elemento che va dopo Julia,
Ho ancora un puntatore a Andy, l'elemento prima.
Così si ha accesso, in sostanza, pangrattato, se si vuole,
a tutti i puntatori necessari.
>> Quindi se sto puntando a Andy ed io sto puntando anche
a Christian, le cui mani dovrebbe ora essere osservato altrove?
Così Andy ora può puntare a Julia.
Julia ora può puntare a Christian.
Perché lei può copiare il mio puntatore di destra.
E che ti mette in modo efficace di nuovo in questo posto qui.
Così, in breve, anche se questo ci sta prendendo tipo di sempre
aggiornare realtà un lista collegata, realizzare
che le operazioni sono relativamente semplici.
E 'di uno, due, tre righe di codice in ultima analisi.
Ma avvolto attorno a quelli righe di codice presumibilmente
che è effettivamente un po 'di logica pone la domanda, a che punto siamo?
Siamo all'inizio, la metà o la fine?
>> Ora, ci sono sicuramente alcuni altri operazioni potremmo implementare.
E queste immagini qui solo raffigurano quello che abbiamo appena fatto con gli esseri umani.
Che dire di rimozione?
Se voglio, per esempio, rimuovere il numero 34 o 55,
Potrei avere lo stesso tipo di codice, ma ho intenzione di bisogno di uno o due passi.
Perché quello che c'è di nuovo?
Se rimuovo qualcuno, alla fine, come il numero 55 e poi 34,
ciò che deve anche cambiare come faccio?
Devo non evict-- cosa c'è di nuovo il tuo nome?
>> PUBBLICO: Jack.
>> DAVID J. MALAN: Jack.
Devo non solo evict-- libero Jack, così letteralmente chiamare il Jack, o almeno
il puntatore anche lì, ma ora ciò che deve cambiare con Peter?
La sua mano meglio iniziare punta verso il basso.
Perché non appena chiamo gratuito Jack, se di Peter ancora punta a Jack
e pertanto continuo attraversamento l'elenco e l'accesso questo puntatore,
che quando il nostro amico segmentazione vecchio guasto potrebbe effettivamente calci in.
Perché abbiamo dato il memoria torna a Jack.
>> Si può stare lì goffamente solo per un attimo.
Perché abbiamo solo un paio operazioni finali da considerare.
Rimuovere la testa della lista, o la beginning-- e questo proprio
un po 'fastidioso.
Perché dobbiamo sapere che Gabe è una specie di speciale in questo programma.
Perché in effetti, egli ha il suo puntatore.
Egli non è solo di essere puntato, come quasi tutti gli altri qui.
>> Così, quando la testa della lista è rimosso, le cui mani hanno bisogno di cambiare ora?
Qual è il tuo nuovo nome?
>> PUBBLICO: Christine.
>> DAVID J. MALAN: io sono terribile a nomi, a quanto pare.
Così Christine e Gabe, le cui mani hanno bisogno di cambiare
quando cerchiamo di rimuovere Christine, numero 5, dalla foto?
OK, quindi cerchiamo di fare Gabe.
Gabe sta andando al punto, presumibilmente, al numero 9.
Ma cosa dovrebbe accadere il prossimo?
PUBBLICO: Christine dovrebbe essere nullo [incomprensibile].
DAVID J. MALAN: OK, dovremmo probabilmente make-- ho sentito "nulla" da qualche parte.
PUBBLICO: Null e libera la sua.
DAVID J. MALAN: null cosa?
PUBBLICO: Null e libera la sua.
DAVID J. MALAN: Null e libera la sua.
Quindi questo è molto facile.
Ed è perfetto che ora sei specie di lì, non appartenenza.
Perché sei stato disaccoppiato dalla lista.
Sei stato efficacemente orfano dalla lista.
E così faremmo meglio a chiamare gratis su Christine dare che la memoria indietro.
In caso contrario, ogni volta che eliminare un nodo dall'elenco
potremmo essere facendo la lista più breve, ma non effettivamente decrescente
la dimensione in memoria.
E così se continuiamo aggiungendo e aggiungendo, aggiungendo cose alla lista,
il mio computer potrebbe ottenere più lento e più lento e più lento,
perché sono a corto di memoria, anche se io non sono in realtà
utilizzando i byte di Christine di memoria più.
>> Così alla fine ci sono altri scenari, di rimozione naturalmente--
nel mezzo, la rimozione alla fine, come abbiamo visto.
Ma il più interessante sfida ora è
andando a essere quello di considerare esattamente ciò che il tempo di esecuzione è.
Quindi non solo è possibile mantenere il vostro pezzi di carta, se, Gabe,
che non mi dispiacerebbe dare tutti una palla antistress.
Grazie mille alla nostra lista concatenata di volontari qui, se potessi.
>> [Applausi]
>> DAVID J. MALAN: Va bene.
Così un paio di analitica domande poi, se potessi.
Abbiamo visto questa notazione prima, O grande e omega, limiti superiori
e limiti inferiori sul tempo di qualche algoritmo esecuzione.
Quindi prendiamo in considerazione solo un paio di domande.
>> Uno, e abbiamo detto prima, che cosa è il funzionamento
tempo di ricerca di un lista in termini di grande O?
Che cosa è un limite superiore per il funzionamento tempo di cercare una lista concatenata
come attuato dai nostri volontari qui?
E 'grande O di n, lineare.
Perché nel caso peggiore, l'elemento, come 55,
potremmo essere alla ricerca di potrebbe essere dove Jack era, fino alla fine.
E purtroppo, a differenza di un array non possiamo ottenere di fantasia questa volta.
Anche se tutti i nostri uomini erano ordinati da piccoli elementi, 5,
tutto il percorso fino all'elemento più grande, 55, che di solito è una buona cosa.
Ma cosa significa questo presupposto non ci permettono di fare?
PUBBLICO: [incomprensibile]
DAVID J. MALAN: dire ancora?
PUBBLICO: accesso casuale.
DAVID J. MALAN: accesso casuale.
E a sua volta questo significa che non possiamo utilizzare più zeri deboli, l'intuizione,
e ovvietà di usare binario cercare e dividere e conquistare.
Perché anche se abbiamo gli esseri umani potrebbero ovviamente
vedere che Andy o cristiana erano all'incirca a metà della lista,
sappiamo solo che come computer scrematura della lista
fin dall'inizio.
Così abbiamo dato a tale accesso casuale.
>> Così grande O di n ora è il superiore bound sul nostro tempo di ricerca.
Che dire omega della nostra ricerca?
Qual è il limite inferiore per la ricerca per un certo numero in questo elenco?
PUBBLICO: [incomprensibile]
DAVID J. MALAN: dire ancora?
PUBBLICO: One.
DAVID J. MALAN: One.
Tempo così costante.
Nel migliore dei casi, Christine è infatti, all'inizio della lista.
E stiamo cercando numero 5, così l'abbiamo trovato.
Quindi un grosso problema.
Ma lei ha di essere al inizio della lista in questo caso.
Che dire qualcosa come Cancellare?
Che cosa succede se si desidera eliminare un elemento?
Qual è il limite superiore e il limite inferiore sull'eliminazione di qualcosa da un collegato
elencare?
PUBBLICO: [incomprensibile]
DAVID J. MALAN: dire ancora?
PUBBLICO: n.
DAVID J. MALAN: n è infatti il ​​limite superiore.
Perché nel caso peggiore proviamo per cancellare Jack, come abbiamo appena fatto.
E 'tutto il senso alla fine.
Ci prende per sempre, o n passi per trovare lui.
Quindi questo è un limite superiore.
Questo è lineare, certo.
E il caso migliore tempo di esecuzione, o i limiti inferiori nel migliore dei casi
sarebbe tempo costante.
Perché forse cerchiamo di eliminare Christine, e abbiamo appena fortunati
lei è all'inizio.
Ora aspetta un minuto.
Gabe era anche all'inizio, e abbiamo anche avuto per aggiornare Gabe.
Quindi non era solo un passo.
Quindi è davvero costante tempo, nel migliore dei casi,
per rimuovere l'elemento più piccolo?
È, anche se potrebbe essere due, tre, o anche 100 righe di codice,
se è lo stesso numero di linee, non in alcuni loop,
e indipendente dalla dimensione della lista, assolutamente.
Eliminare l'elemento in all'inizio della lista,
anche se abbiamo a che fare con Gabe, è ancora tempo costante.
>> Quindi questo sembra un enorme passo indietro.
E che una perdita di tempo se, in una settimana e settimana
pari a zero abbiamo avuto non solo Codice pseudocodice ma il codice effettivo
di implementare qualcosa che è log di base n, o log, piuttosto, di n, base 2,
in termini di tempo di esecuzione.
Allora perché diavolo dovrebbe vogliamo iniziare usando qualcosa come una lista concatenata?
Già.
>> Pubblico: Così si può aggiungere elementi all'array.
DAVID J. MALAN: Così si può aggiungere elementi all'array.
E anche questo è tematica.
E continueremo a vedere questo, questo trade-off, molto
come abbiamo visto un trade-off con merge sort.
Potremmo davvero accelerare la ricerca o l'ordinamento, piuttosto,
se passiamo un po 'più di spazio e avere un pezzo aggiuntivo di una memoria
o un array di merge sort.
Ma passiamo più spazio, ma risparmiamo tempo.
In questo caso, siamo dando il tempo ma siamo
guadagnando flessibilità, dinamismo se si vuole,
che è probabilmente una caratteristica positiva.
>> Stiamo anche spendendo spazio.
In che senso è un collegato elencare più costoso
in termini di spazio di un array?
Dove si trova lo spazio in più proviene?
Sì?
>> PUBBLICO: [incomprensibile] puntatore.
>> DAVID J. MALAN: Sì, abbiamo hanno anche il puntatore.
Quindi questo è minorly fastidioso in quanto non sono più
Ho memorizzare solo un int per rappresentare un int.
Sto memorizzazione di un int e un puntatore, che è anche 32 bit.
Così sto letteralmente il raddoppio la quantità di spazio coinvolto.
Quindi questo è un trade-off, ma che è nel caso di int.
Supponiamo che non sei memorizzazione int, ma supponiamo che ciascuno di questi rettangoli
o ciascuno di questi esseri umani rappresentava una parola, una parola inglese che
potrebbe essere cinque caratteri, 10 personaggi, forse anche di più.
Poi l'aggiunta di soli 32 più bit potrebbe essere meno di un grosso problema.
>> E se ognuno degli studenti nella dimostrazione
erano letteralmente le strutture studentesche che hanno nomi e case e forse
numeri di telefono e Twitter maniglie e simili.
Così tutti i campi abbiamo iniziato parlando l'altro giorno,
molto meno di un grande affare come i nostri nodi si fanno più interessanti
e grande per spendere, eh, un ulteriore puntatore solo per collegarli tra loro.
Ma in effetti, si tratta di un trade-off.
E infatti, il codice è più complesso, come avrete
vedere da sfogliando quel particolare esempio.
Ma cosa succede se ci fossero qualche santo graal qui.
E se noi non facciamo un passo indietro ma un passo enorme in avanti
e implementare un data struttura attraverso la quale si
possono trovare elementi come Jack o Christine o altri elementi
in questo array in vero tempo costante?
La ricerca è costante.
Elimina è costante.
Inserisci è costante.
Tutte queste operazioni sono costanti.
Sarebbe il nostro Santo Graal.
Ed è qui che abbiamo prenderà la prossima volta.
Vediamo allora.