[Powered by Google Translate] [Settimana 6, continua] [David J. Malan] [Harvard University] [Questo è CS50.] [CS50.TV] Questo è CS50 e questa è la fine della settimana 6. Così CS50x, uno dei primi piatti di Harvard coinvolti nell'iniziativa edx infatti ha debuttato lo scorso Lunedi. Se volete avere un assaggio di ciò che gli altri su Internet stanno seguendo insieme, è possibile testa a x.cs50.net. Che vi reindirizza verso il luogo appropriato edx.org, che era il luogo dove questo e altri corsi del MIT e Berkeley ora vivono. Dovrai registrarti per un account, vi accorgerete che il materiale è in gran parte la stessa come hai avuto questo semestre, anche se un paio di settimane in ritardo, come abbiamo tutto pronto. Ma ciò che gli studenti in CS50x ora vedere è una interfaccia molto simile a questo. Questo, per esempio, è Zamyla leader procedura dettagliata per il set problema 0. Volta effettuato l'accesso a edx.org, uno studente CS50x vede il genere di cose ci si aspetterebbe di vedere in un corso: la lezione per il Lunedi, lezione per Mercoledì, pantaloncini, i vari set di problema, le procedure dettagliate, PDF. Inoltre, come vedete qui, macchina traduzioni delle trascrizioni inglese in cinese, giapponese, spagnolo, italiano, e un sacco di altre lingue che sarà certamente imperfetta come noi li stendere programmazione usando una cosa chiamata una API, o Application Programming Interface, da Google che ci permette di convertire Italiano per altre lingue. Ma grazie allo spirito meraviglioso di un centinaio e più volontari, persone a caso su Internet che si sono gentilmente offerti di essere coinvolti in questo progetto, saremo progressivamente migliorare la qualità di tali traduzioni avendo gli esseri umani correggere gli errori che i nostri computer hanno fatto. 

Così si scopre che avevamo alcuni studenti più visualizzato su Lunedi di quanto inizialmente previsto. Infatti, ora CS50x ha 100.000 persone che seguono insieme a casa. Così rendi conto che fanno parte di questa classe inaugurale di fare questo corso di informatica dell'istruzione in generale, più in generale, accessibile. E la realtà è ora, con alcuni di questi corsi on-line di massa, tutti iniziare con questi numeri molto alti, come sembra che abbiamo fatto qui. Ma l'obiettivo, in ultima analisi, per CS50x è davvero di ottenere il maggior numero di persone il traguardo il più possibile. In base alla progettazione, CS50x sta per essere offerto da questo passato Lunedi tutta la strada fino al 15 Aprile 2013, in modo che le persone che hanno impegni scolastici altrove, lavoro, famiglia, altri conflitti e simili, hanno un po 'più di flessibilità con cui tuffarsi in questo corso, che, è sufficiente dire, è piuttosto ambiziosamente fare se non altro nel corso di soli tre mesi nel corso di un semestre al solito. Ma questi studenti sarà affrontare il set stesso problema, la visualizzazione del contenuto stesso, avere accesso agli stessi pantaloncini e simili. Così si rendono conto che tutti siamo veramente in questo insieme. E uno degli obiettivi finali di CS50x non è solo quello di ottenere il maggior numero persone al traguardo e dare loro questa comprensione ritrovata di informatica e di programmazione, ma anche per avere loro hanno condiviso questa esperienza. Una delle caratteristiche distintive di 50 nel campus, ci auguriamo, è stato questo tipo di esperienza comune, nel bene e nel male, a volte, ma avendo queste persone a rivolgersi a verso sinistra e verso destra, e l'orario di ufficio e l'Hackathon e la fiera. E 'un po' più difficile di farlo di persona con la gente in linea, ma CS50x si concluderà nel mese di aprile con la prima CS50 Expo, che sarà un adattamento on-line della nostra idea della fiera dove queste migliaia di studenti saranno tutti invitati a presentare un 1 - a 2 minuti di video, o uno screencast del loro progetto finale o video di loro agitando Ciao e parlando di loro progetto e provare le canzoni di esso, proprio come i vostri predecessori hanno fatto qui nel campus in fiera, in modo che entro la fine del semestre, la speranza è di avere una mostra globale dei progetti finali degli studenti CS50x ', molto simile a quella che vi attende a dicembre qui al campus. Quindi, più su che nei mesi a venire. 

Con 100.000 studenti, però, arriva una necessità di una CA in più. Dato che voi ragazzi sono ardente il sentiero qui e tenendo CS50 diverse settimane di anticipo del rilascio di questo materiale per la gente su EDX, realizzare ci piacerebbe coinvolgere il maggior numero dei nostri studenti il ​​più possibile in questa iniziativa, sia durante il semestre e questo inverno e la prossima primavera. Quindi, se volete essere coinvolti in CS50x, in particolare entrare in su CS50x Discuti, la versione di edx CS50 discutere, che molti di voi hanno utilizzato nel campus, la bacheca on-line, si prega di fare capo a tale URL, facci sapere chi sei, perché ci piacerebbe costruire una squadra di studenti e personale docente e allo stesso modo nel campus che sono semplicemente suonando insieme e dare una mano. E quando vedono una domanda che è loro familiare, si sente uno studente segnalato qualche bug da qualche parte là fuori in un paese su Internet, e che suona un campanello, perché anche voi avuto questo stesso problema nel d-corridoio qualche tempo fa, si spera allora si può carillon e condividere la tua esperienza. Quindi per favore prendere se si desidera. 

Corsi di informatica di Harvard hanno un po 'di una tradizione, CS50 tra di loro, di avere un po 'di abbigliamento, alcuni vestiti, che si può indossare con orgoglio alla fine del semestre, dicendo molto orgoglio che avete finito CS50 e ha preso CS50 e simili, e cerchiamo sempre di coinvolgere gli studenti in questo processo il più possibile, per cui invitiamo, in questo periodo del semestre, gli studenti a presentare progetti utilizzando Photoshop, o qualsiasi strumento di scelta che si desidera utilizzare se sei un designer, di presentare i disegni per T-shirt e felpe e ombrelloni e bandane per i cani piccoli che ora abbiamo e simili. E tutto è poi - i vincitori ogni anno vengono esposti sul sito web del corso di store.cs50.net. Tutto è in vendita al costo di lì, ma il sito funziona solo se stessa e permette alle persone di scegliere i colori e disegni che a loro piace. Così ho pensato che avremmo semplicemente condividere alcuni dei progetti dello scorso anno che erano sul sito web oltre a questo qui, che è una tradizione annuale. "Ogni giorno mi Seg Faultn" è stata una delle conclusioni dello scorso anno, che è ancora disponibile lì per alunni. Abbiamo avuto questo ", CS50, di fondazione 1989." Uno dei nostri Bowdens, Rob, era molto popolare l'anno scorso. "Team Bowden" è nato, questo progetto è stato presentato, tra i più venduti. Come era questo qui. Molte persone avevano "Fever Bowden", secondo i registri di vendita. Rendetevi conto che che potrebbe ora essere il vostro disegno lì, su Internet. Maggiori dettagli su questo problema nel prossimo set di venire. 

Uno strumento in più: hai avuto un po 'di esposizione e, si spera ora un po 'di esperienza pratica con GDB, che è, ovviamente, un debugger e consente di manipolare il programma a un livello piuttosto basso, facendo che tipo di cose? Che cosa ti permette di fare GDB? Si '? Dammi qualcosa. [Risposta studente, incomprensibile] Buona. Passo in funzione, in modo da non solo per digitare e hanno il colpo programma attraverso tutti i suoi elementi, la stampa le cose sullo standard output. Piuttosto, è possibile scorrere riga per riga, digitando prossima andare riga per riga per riga o passo per immergersi in una funzione, in genere quello che hai scritto. Cos'altro GDB ti permette di fare? Si '? [Risposta studente, incomprensibile] Stampa variabili. Quindi, se si vuole fare un po 'di introspezione all'interno del vostro programma senza dover ricorrere alla scrittura di istruzioni printf in tutto il luogo, si può semplicemente stampare una variabile o visualizzare una variabile. Che altro si può fare con un debugger GDB come? [Risposta studente, incomprensibile] Esattamente. È possibile impostare i punti di interruzione, si può dire l'esecuzione di pausa alla funzione principale o la funzione foo. Si può dire che l'esecuzione pausa in linea 123. E i punti di interruzione sono una tecnica davvero potente perché se si ha un senso generale di dove il vostro problema probabilmente è, non c'è bisogno di perdere tempo passando attraverso elementi del programma. È possibile saltare essenzialmente proprio lì e iniziare a digitare - attraversandola con passo o successivo o simili. Ma il fermo con qualcosa di simile GDB è che ti aiuta, l'umano, ricerca di problemi e la ricerca di un bug. Non necessariamente a trovare così tanto per voi. 

Così abbiamo introdotto il style50 altro giorno, che è una breve strumento a riga di comando che cerca di stilizzare il codice un po 'più pulito di te, l'umano, avrebbe potuto fare. Ma anche questo, è in realtà solo una cosa estetica. Ma si scopre c'è questo altro strumento chiamato Valgrind che è un po 'più arcano da usare. La sua uscita è atrocemente criptico a prima vista. Ma è meravigliosamente utile, soprattutto ora che siamo nella parte del termine dove si sta iniziando a usare malloc e allocazione dinamica della memoria. Le cose possono andare molto, molto male in fretta. Perché se si dimentica di liberare la memoria, o si dereference qualche puntatore NULL, o si dereference qualche puntatore spazzatura, ciò che è in genere il sintomo che i risultati? Seg guasto. E si ottiene questo file core di un certo numero di kilobyte o in megabyte che rappresenta lo stato della memoria del programma quando si è schiantato, ma il vostro programma in ultima analisi seg errori, errore di segmentazione, il che significa che qualcosa di brutto è accaduto quasi sempre legata ad un errore relativo alla memoria che hai fatto da qualche parte. Così Valgrind ti aiuta a trovare cose come questa. E 'uno strumento che si esegue, come GDB, dopo aver compilato il programma, ma invece di eseguire il programma direttamente, si esegue Valgrind e si passa ad essa il programma, proprio come si fa con GDB. Ora, l'uso, per ottenere il miglior tipo di produzione, è un po 'lungo, per cui proprio lì in cima dello schermo vedrete Valgrind-v. "-V" quasi universalmente significa verbose quando si utilizza i programmi su un computer Linux. Quindi significa sputare più dati di quanto si possa per impostazione predefinita. "- Leak-check = pieno." Questo è solo per dire di controllo per tutte le possibili perdite di memoria, errori che avrei potuto fatto. Anche questo è un paradigma comune con i programmi Linux. In genere, se si dispone di un argomento della riga di comando che è un "interruttore", che dovrebbe cambiare il comportamento del programma, ed è una sola lettera, è-v, ma se questo è acceso, solo in base alla progettazione del programmatore, è una parola piena o una serie di parole, l'argomento della riga di comando inizia con -. Questi sono solo convenzioni umane, ma li vedrete sempre. E poi, alla fine, "a.out" è il nome arbitrario per il programma in questo esempio particolare. Ed ecco un po 'di uscita rappresentativo. 

Prima di guardare a ciò che potrebbe dire, lasciami andare verso un frammento di codice qui. E fammi spostare questo di mezzo, in arrivo, e diamo un'occhiata a memory.c, che è questo breve esempio qui. Quindi, in questo programma, vorrei ingrandire le funzioni e le domande. Abbiamo una funzione principale che chiama una funzione, f, e poi che cosa f continuerò a fare, in inglese un po 'tecnico? Che cosa f procedere fare? Che ne dici se inizierò con la linea 20, e la posizione della stella non importa, ma mi limiterò a essere coerenti con ultima lezione. Cosa c'è di linea 20 fare per noi? Sul lato sinistro. Noi lo abbattere ulteriormente. Int * x: che cosa vuol fare? Va bene. E 'dichiarazione di un puntatore, e ora cerchiamo di essere ancora più tecnico. Che cosa significa, molto concretamente, per dichiarare un puntatore? Qualcun altro? Si '? [Risposta studente, incomprensibile] Troppo lontano. Quindi stai leggendo a destra del segno di uguale. Concentriamoci solo sulla sinistra, proprio sul int * x. Questo significa "dichiarare" un puntatore, ma adesso cerchiamo di immergersi più a fondo a tale definizione. Che cosa concretamente, tecnicamente significa? Si '? [Risposta studente, incomprensibile] Va bene. Si prepara a memorizzare un indirizzo in memoria. Buona. E facciamo un ulteriore passo avanti, è dichiarazione di una variabile, x, che è a 32 bit. E so che è a 32 bit perché -? Non è perché è un int, perché è un puntatore in questo caso. Coincidenza che è uno e lo stesso con un int, ma il fatto che ci sia la stella non significa che questo è un puntatore e l'apparecchio, come con molti computer, ma non tutti, i puntatori sono a 32 bit. In più l'hardware moderno come i più recenti Mac, i più recenti PC, si potrebbe avere puntatori a 64 bit, ma l'apparecchio, queste cose sono a 32 bit. Quindi dovremo uniformare su questo. Più concretamente, la storia è la seguente: Noi "dichiarare" un puntatore, che cosa vuol dire? Prepariamo per memorizzare un indirizzo di memoria. Che cosa vuol dire? Creiamo una variabile x chiamata che occupa 32 bit che presto memorizzare l'indirizzo di un intero. E questo è probabilmente quanto di preciso come si può ottenere. Va bene andare avanti per semplificare il mondo e dire dichiarare un puntatore chiamato x. Dichiarare un puntatore, ma realizzare e capire cosa sta realmente succedendo anche nel giro di quei pochi personaggi. 

Ora, questo è quasi un po 'più facile, anche se è una espressione più lunga. Così che cosa è questo facendo, che è ora messo in evidenza: "malloc (10 * sizeof (int));" Sì? [Risposta studente, incomprensibile] Buona. E io lo accompagno. E 'assegnazione di un pezzo di memoria per dieci numeri interi. E ora immergersi in un po 'più profondo, è allocare un blocco di memoria per dieci numeri interi. Che cosa è malloc poi tornare? L'indirizzo di quel pezzo, o, più concretamente, l'indirizzo del primo byte del blocco. Come io sono, il programmatore, per sapere dove quel pezzo di fini di memoria? So che è contigua. Malloc, per definizione, vi darà un pezzo di memoria contiguo. Non ci sono lacune in esso. È possibile accedere a ogni byte in quel pezzo, back to back to back, ma come faccio a sapere dove alla fine di questo pezzo di memoria è? Quando si utilizza malloc? [Risposta studente, incomprensibile] Bene. Non lo sai. Bisogna ricordare. Devo ricordare che ho usato il valore 10, e non mi sembra nemmeno di aver fatto qui. Ma l'onere è interamente su di me. Strlen, che siamo diventati un po 'affidamento su per le stringhe, funziona solo a causa di questa convenzione di avere \ 0 o questo carattere speciale nul, NUL, alla fine di una stringa. Questo non vale solo per blocchi arbitrari di memoria. E 'a voi. Così linea 20, poi, alloca un blocco di memoria che può memorizzare dieci interi, e memorizza l'indirizzo del primo byte di quel pezzo di memoria della variabile x chiamato. Ergo, che è un puntatore. Così linea 21, purtroppo, è stato un errore. Ma in primo luogo, che cosa sta facendo? Sta dicendo negozio in posizione 10, 0 indicizzati, del pezzo di memoria chiamata x il valore 0. 

Quindi notare un paio di cose sono in corso. Anche se x è un puntatore, richiama un paio di settimane fa che è ancora possibile utilizzare la matrice-notazione parentesi quadra. Perché questo è in realtà l'abbreviazione usata per la notazione aritmetica dei puntatori più criptico di aspetto. dove avremmo fatto qualcosa di simile a questo: prendere la x indirizzo, spostare 10 posti sopra, poi andare lì a qualunque indirizzo è memorizzato in quella posizione. Ma, francamente, questo è solo atroce di leggere e mettersi a proprio agio con. Così il mondo in genere utilizza le parentesi quadre solo perché è molto più human-friendly per leggere. Ma questo è quello che sta realmente accadendo sotto il cofano; x non è un indirizzo, una matrice, per sé. Quindi questa è la conservazione 0 alla posizione 10 in x. Perché questo è male? Si '? [Risposta studente, incomprensibile] Esattamente. Abbiamo solo assegnati dieci interi, ma si contano da 0 quando si programma in C, in modo da avere accesso a 0 1 2 3 4 5 6 7 8 9, ma non 10. Quindi, sia il programma sta per colpa segmento o non lo è. Ma non lo so, questo è una sorta di comportamento non deterministico. In realtà dipende dal fatto che siamo fortunati. Se si scopre che il sistema operativo non importa se uso quel byte in più, anche se non l'ha dato a me, il mio programma non può andare in crash. E 'crudo, e' pieno di bug, ma potreste non vedere quel sintomo, oppure si potrebbe vedere solo una volta ogni tanto. Ma la realtà è che il bug è, infatti,. Ed è davvero problematico se hai scritto un programma che si vuole essere corretto, che hai venduto il programma che la gente sta usando che ogni tanto si blocca perché, naturalmente, questo non va bene. Infatti, se si dispone di un telefono Android o un iPhone e scaricare le applicazioni in questi giorni, se hai mai avuto un app appena smesso, tutto ad un tratto scompare, che è quasi sempre il risultato di un po 'di memoria problema legato, per cui il programmatore avvitato e dereferenced un puntatore che lui o lei non dovrebbe avere, e il risultato di iOS o Android è quello di uccidere solo il programma del tutto piuttosto che rischiare un comportamento indefinito o un qualche tipo di compromesso di sicurezza. 

C'è un altro bug in questo programma, oltre a questo. Che altro ho fatto un casino in questo programma? Non ho praticato quello che ho predicato. Si '? [Risposta studente, incomprensibile] Bene. Non ho liberato la memoria. Quindi la regola generale ora deve essere in qualsiasi momento si chiama malloc, è necessario chiamare gratis quando hai finito di utilizzare la memoria. Ora, quando dovrei liberare questa memoria? Probabilmente, assumendo questo prima linea era corretta, vorrei farlo qui. Perché non ho potuto, per esempio, lo faccio qui. Perché? Appena fuori del campo di applicazione. Quindi, anche se stiamo parlando di puntatori, questa è una settimana 2 o 3 problema, dove x è solo una portata all'interno delle parentesi graffe in cui è stata dichiarata. Quindi non puoi assolutamente liberarlo lì. La mia unica possibilità per liberarlo è più o meno dopo la riga 21. Questo è un programma abbastanza semplice, ma era abbastanza facile una volta che tipo di avvolto la mente intorno a ciò che il programma sta facendo, dove gli errori sono stati. E anche se non l'ho visto in un primo momento, si spera un po 'ovvio ora che questi errori sono abbastanza facilmente risolti e facilmente fatto. Ma quando un programma è più di 12 righe, è lungo 50 linee, 100 linee lungo, a piedi attraverso il codice riga per riga, pensare attraverso logicamente, è possibile, ma non è particolarmente divertente da fare, costantemente alla ricerca di bug, ed è anche difficile da fare, ed è per questo uno strumento come Valgrind esiste. Lasciatemi andare avanti e fare questo: vorrei aprire la finestra di terminale, e che io non solo correre la memoria, perché la memoria sembra andare bene. Sto diventando fortunato. Andando a quel byte aggiuntivo alla fine della matrice non sembra essere troppo problematico. Ma mi permetta, tuttavia, fare un controllo di integrità, il che significa che solo per controllare se questo è in realtà corretto. 

Allora, facciamo valgrind-v - leak-check = pieno, e quindi il nome del programma in questo caso è la memoria non a.out. Permettetemi quindi di andare avanti e farlo. Hit Enter. Caro Dio. Questa è la sua uscita, e questo è quello che ho accennato prima. Ma, se si impara a leggere tutte le sciocchezze qui, la maggior parte di questo è solo uscita di diagnosi che non è così interessante. Che l'occhio vuole davvero essere alla ricerca di è alcuna menzione di errore o non valido. Parole che suggeriscono problemi. E infatti, vediamo cosa c'è che non va qui. Ho un riassunto di qualche tipo ", in uso in uscita:. 40 byte in blocchi da 1" Io non sono davvero sicuro di quello che un blocco è ancora, ma 40 byte si sente davvero come ho potuto capire dove che viene. 40 byte. Perché i 40 byte in uso in uscita? E più in particolare, se si scorrere verso il basso qui, perché ho sicuramente perso 40 byte? Si '? [Risposta studente, incomprensibile] Perfetto. Sì, esattamente. C'erano dieci interi, e ciascuna di queste è la dimensione di 4, o 32 bit, così ho perso proprio 40 byte perché, come proposto, non ho detto libero. Questo è un bug, e ora guardiamo un po 'più in basso e vedere accanto a questo, "Non valido scrivere di dimensione 4." Ora, che cosa è questo? Questo indirizzo si esprime ciò che la notazione di base, a quanto pare? Questo è esadecimale, e ogni volta che vedi un numero che inizia con 0x, significa esadecimale, che abbiamo fatto nel lontano, credo, sezione pset 0 di domande, che era solo per fare un esercizio di riscaldamento, la conversione decimale in esadecimale in binario e così via. Esadecimale, solo per convenzione umana, di solito è usato per rappresentare i puntatori o, più in generale, indirizzi. E 'solo una convenzione, perché è un po 'più facile da leggere, è un po' più compatto qualcosa come decimale, e binario è inutile per la maggior parte degli umani da usare. Così ora che cosa significa? Beh, sembra che ci sia una scrittura non valido di dimensione 4 sulla linea 21 di memory.c. Quindi cerchiamo di tornare alla linea 21, e in effetti, è qui che la scrittura non valido. Quindi Valgrind non ha intenzione di tenere completamente la mia mano e mi dica cosa è la correzione, ma rileva che sto facendo una scrittura non valido. Sto toccando 4 byte che non dovrebbe essere, ea quanto pare questo perché, come lei ha sottolineato, sto facendo [10] invece di [9] al massimo o [0] o una via di mezzo. Con Valgrind, realizzare ogni volta che si sta ora scrivendo un programma che utilizza puntatori e utilizza la memoria, e più specificamente malloc, sicuramente ottenere l'abitudine di correre questo lungo ma molto facilmente copiato e incollato il comando della Valgrind per vedere se c'è qualche errore in là. E sarà schiacciante ogni volta che si vede l'uscita, ma solo analizzare visivamente attraverso tutta la produzione e vedere se si vedere menzioni di errori o avvisi o non valido o perso. Alcune parole che suonano come si avvitato da qualche parte. Così si rendono conto che è un nuovo strumento nel toolkit. 

Ora il Lunedi, abbiamo avuto un sacco di gente venire qui e rappresentano l'idea di una lista concatenata. E abbiamo introdotto la lista concatenata come una soluzione al problema che cosa? Si '? [Risposta studente, incomprensibile] Bene. Gli array non può avere memoria aggiunta a loro. Se si alloca un array di dimensione 10, è tutto quello che si ottiene. È possibile chiamare una funzione come realloc se inizialmente chiamato malloc, e che possono provare a crescere la matrice se vi è spazio verso la fine di esso che nessun altro sta usando, e se non c'è, sarà solo a trovare un pezzo più grande da qualche altra parte. Ma poi copierà tutti i byte nel nuovo array. Questo suona come una soluzione molto corretta. Perché questo è poco attraente? Voglio dire che funziona, gli esseri umani hanno risolto questo problema. Perché abbiamo bisogno di risolvere il problema il Lunedi con le liste collegate? Si '? [Risposta studente, incomprensibile] Si potrebbe richiedere molto tempo. In effetti, ogni volta che si sta chiamando malloc o realloc o calloc, che è ancora un altro, qualsiasi tempo, il programma, si parla al sistema operativo, si tende a rallentare il programma verso il basso. E se si sta facendo questo tipo di cose in loop, sei davvero rallentando il tutto. Tu non stai andando a notare questo per la più semplice delle "Hello World" programmi di tipo, ma in programmi molto più grandi, richiedendo al sistema operativo ancora e ancora per la memoria o dare indietro ancora e ancora tende a non essere una buona cosa. Inoltre, è solo una sorta di intellettuale - è una perdita di tempo. Perché allocare la memoria sempre più, il rischio di copiare tutto nel nuovo array, se si dispone di una alternativa che consente di allocare la memoria solo quanto hai veramente bisogno? Quindi ci sono vantaggi e svantaggi in qui. Uno dei vantaggi è ora che abbiamo dinamismo. Non importa dove i blocchi di memoria sono che sono liberi, Posso solo ordinare di creare queste briciole di pane con puntatori alla stringa la mia intera lista collegati tra loro. Ma pagare almeno un prezzo. 

Cosa devo rinunciare ad acquisire le liste collegate? Si '? [Risposta studente, incomprensibile] Bene. Hai bisogno di più memoria. Ora ho bisogno di spazio per queste indicazioni, e nel caso di questo super semplice lista collegata che sta solo cercando di memorizzare numeri interi, che sono 4 byte, si continua a dire bene, un puntatore è di 4 byte, così ora ho letteralmente raddoppiato la quantità di memoria ho bisogno solo per memorizzare questa lista. Ma ancora una volta, si tratta di un compromesso costante in informatica tra il tempo e lo spazio e lo sviluppo, lo sforzo e di altre risorse. Che è un altro svantaggio di usare una lista concatenata? Si '? [Risposta studente, incomprensibile] Buona. Non è così facile accesso. Non possiamo più sfruttare settimana 0 principi come dividere e conquistare. E più specificamente, la ricerca binaria. Perché anche se noi esseri umani può vedere o meno dove la metà di questa lista è, il computer sa solo che questa lista collegata inizia all'indirizzo chiamato per primo. E questo è 0x123 o qualcosa del genere. E l'unico modo che il programma possa trovare l'elemento centrale è quello di cercare in realtà l'intero elenco. E anche allora, ha letteralmente alla ricerca tutta la lista, perché anche una volta raggiunto l'elemento centrale seguendo i puntatori, si, il programma, non hanno idea di quanto tempo questo elenco è, potenzialmente, fino a colpire alla fine di esso, e come fai a sapere di programmazione che sei alla fine di una lista concatenata? C'è uno speciale puntatore NULL, quindi ancora una volta, una convenzione. Piuttosto che utilizzare questo puntatore, abbiamo sicuramente non voglio che sia un valore spazzatura puntamento fuori scena da qualche parte, vogliamo che sia la mano verso il basso, NULL, in modo da avere il capolinea in questa struttura dati in modo da sapere dove va a finire. 

Che cosa succede se si vuole manipolare questo? Abbiamo fatto la maggior parte di questo visivamente, e con gli esseri umani, ma se vogliamo fare un inserimento? Quindi la lista originale era 9, 17, 20, 22, 29, 34. E se poi voluto spazio malloc per il numero 55, un nodo per esso, e poi vogliamo inserire 55 nella lista come abbiamo fatto il Lunedi? Come possiamo fare questo? Beh, Anita si avvicinò e lei camminava in sostanza l'elenco. Ha iniziato al primo elemento, quindi il prossimo, il prossimo, il prossimo, il prossimo, il prossimo. Infine ha colpito la sinistra fino in fondo e realizzato oh, questo è NULL. Così che cosa la manipolazione dei puntatori si doveva fare? La persona che era alla fine, il numero 34, bisogno della sua mano sinistra sollevata per puntare a 55, 55 bisogno del loro braccio sinistro verso il basso per essere il nuovo terminatore NULL. Fatto. Abbastanza facile da inserire 55 in un elenco ordinato. E come potrebbe questo aspetto? 

Lasciatemi andare avanti e aprire un po 'di codice di esempio qui. Io aprire gedit, e lasciami aprire i due file prima. Uno è list1.h, e vorrei solo ricordare che questo era il pezzo di codice che abbiamo usato per rappresentare un nodo. Un nodo ha sia un int chiamato n e un puntatore chiamato accanto che solo i punti alla cosa successiva nell'elenco. Questo è ora in un file. H. Perché? C'è questa convenzione, e non abbiamo approfittato di questo una quantità enorme noi stessi, ma la persona che ha scritto le funzioni printf e altre ha regalato al mondo tutte quelle funzioni scrivendo un file chiamato stdio.h. E poi c'è string.h, e poi c'è Map.h, e ci sono tutti i file h che tu possa aver visto o utilizzato nel corso della durata scritta da altre persone. In genere in quelli. File h sono solo cose come typedef o le dichiarazioni di tipi personalizzati o le dichiarazioni di costanti. Non mettere le implementazioni funzioni 'in file di intestazione. Si mette, invece, solo i loro prototipi. Hai messo le cose che si desidera condividere con il mondo quello di cui hanno bisogno al fine di compilare il loro codice. Quindi, solo per entrare in questa abitudine, abbiamo deciso di fare la stessa cosa. Non c'è molto in list1.h, ma abbiamo messo qualcosa che potrebbe essere di interesse per le persone in tutto il mondo che vogliono utilizzare la nostra implementazione lista concatenata. Ora, in list1.c, non voglio passare tutta questa faccenda perché è un po 'lungo, questo programma, ma cerchiamo di farlo funzionare reale velocemente al prompt. Vorrei compilare list1, vorrei quindi eseguire list1, e quello che vedrete è abbiamo simulato un semplice programmino qui che sta per permettermi di aggiungere e rimuovere i numeri a un elenco. Permettetemi quindi di andare avanti e digitare 3 per la 3 opzione di menu. Voglio inserire il numero - facciamo il primo numero, che era 9, e ora mi hanno detto la lista è ora 9. Lasciatemi andare avanti e fare un altro inserimento, così ho colpito opzione di menu 3. Che numero devo inserire? 17. Invio. E farò solo un altro. Vorrei inserire il numero 22. Così abbiamo l'inizio della lista collegata che abbiamo avuto in forma diapositiva un momento fa. Come è questo inserimento realmente accadendo? Infatti, 22 è ora alla fine della lista. Così la storia ci ha detto sul palco il Lunedi e richiuso solo ora deve essere effettivamente accadendo nel codice. Diamo uno sguardo. Fammi scorrere verso il basso in questo file. Ci sorvolare su alcune delle funzioni, ma andiamo giù, per esempio, la funzione di inserimento. 

Vediamo come possiamo fare per l'inserimento di un nuovo nodo in questa lista collegata. Dove si trova la lista dichiarata? Bene, scorrere tutta la strada fino in cima, e notare che la mia lista concatenata è essenzialmente dichiarato come un unico puntatore che è inizialmente NULL. Quindi sto usando una variabile globale qui, che in generale abbiamo predicato contro perché rende il codice un po 'disordinato di mantenere, è una sorta di pigrizia, di solito, ma non è pigro e non è sbagliato e non è male se solo scopo del vostro programma di vita è quello di simulare una lista concatenata. Che è esattamente quello che stiamo facendo. Quindi, piuttosto che dichiararlo in principale e quindi devono passare ad ogni funzione abbiamo scritto in questo programma, ci rendiamo conto invece oh, facciamo solo rendere globale perché il vero scopo di questo programma è quello di dimostrare una ed una sola lista collegata. In modo che si sente bene. Qui sono i miei prototipi, e non passerà attraverso tutti questi, ma ho scritto una funzione di eliminazione, una funzione di ricerca, una funzione di inserimento, e una funzione di traslazione. Ma ora torna giù per la funzione di inserimento e vedere come questo funziona qui. Inserisci E 'on line - ci siamo. Inserisci. Quindi non richiede alcun argomento, perché stiamo andando a chiedere l'interno uso di questa funzione per il numero che vogliono inserire. Ma prima, ci prepariamo a dare loro un po 'di spazio. Questa è una sorta di copia e incolla da altro esempio. In questo caso, siamo stati assegnazione di un int, questa volta stiamo assegnazione di un nodo. Non mi ricordo il numero di byte è un nodo, ma va bene. Sizeof può capire che per me. E perché sto controllando NULL in linea 120? Cosa potrebbe andare storto in linea 119? Si '? [Risposta studente, incomprensibile] Buona. Solo potrebbe essere il caso che ho chiesto troppa memoria o qualcosa che non va e il sistema operativo non dispone di byte da darmi, in modo che segnali il più restituendo NULL, e se non controllare che e ho appena ciecamente procedere ad utilizzare l'indirizzo restituito, potrebbe essere NULL. Potrebbe essere un po 'di valore sconosciuto, non è una cosa buona se non - in realtà non sarà un valore sconosciuto. Potrebbe essere NULL, quindi non voglio abusarne e rischiare deferenziandolo. In tal caso, ho appena tornare e faremo finta che io non tornare la memoria a tutti. 

In caso contrario, dico che l'utente mi danno un numero da inserire, che io chiamo il nostro GetInt vecchio amico, e poi questa era la nuova sintassi abbiamo introdotto il Lunedi. 'Newptr-> n' significa prendere l'indirizzo che vi è stata data da malloc che rappresenta il primo byte di un oggetto nuovo nodo, e poi andare al campo denominato n. Una piccola domanda curiosità: questo è equivalente a quello che la linea più criptico di codice? In quale altro modo ho scritto questo? Vuoi fare un tentativo? [Risposta studente, incomprensibile] Buona. Utilizzando il. N, ma non è così semplice come questo. Che cosa ho bisogno di fare? [Risposta studente, incomprensibile] Buona. Ho bisogno di fare newptr.n *. Quindi questo sta dicendo nuovo puntatore è ovviamente un indirizzo. Perché? Perché è stato restituito da malloc. Il newptr * dicendo "vai lì" e poi una volta che sei lì, allora è possibile utilizzare il più familiare. n, ma questo sembra solo un po 'brutto, soprattutto se noi esseri umani stanno per trarne indicazioni con le frecce per tutto il tempo, il mondo ha standardizzato su questa notazione freccia, che fa esattamente la stessa cosa. Quindi, si utilizza solo il -> notazione quando la cosa a sinistra è un puntatore. In caso contrario, se si tratta di una struttura reale, utilizzare il. N. E poi questo: Perché devo inizializzare newptr-> accanto a NULL? Non vogliamo una mano penzoloni sinistra fuori della fine della fase. Vogliamo che punti verso il basso, il che significa che alla fine di questa lista potrebbe essere a questo nodo, quindi è meglio assicurarsi che sia NULL. E, in generale, l'inizializzazione le variabili oi vostri membri di dati e strutture a qualcosa è proprio buona. Basta lasciare rifiuti esistono e continueranno ad esistere in genere si mette nei guai se si dimentica di fare qualcosa in seguito. 

Ecco alcuni casi. Questo, di nuovo, è la funzione insert, e la prima cosa verificare se la variabile è chiamato per primo, che la variabile globale è NULL, che significa che non c'è lista collegata. Non abbiamo inserito alcun numero, quindi è banale inserire questo numero corrente nella lista, perché appartiene solo all'inizio della lista. Quindi questo è stato quando Anita stava in piedi qui da solo, facendo finta non c'era nessuno qui sul palco fino a quando abbiamo assegnato un nodo, poi avrebbe potuto alzare la mano per la prima volta, se tutti gli altri era salito sul palco dopo la sua Lunedi. Ora qui, questo è un po 'di controllo in cui devo dire che se il nodo del nuovo valore di n <è il valore di n nel nodo prima corrente, che significa che c'è una lista collegata che è iniziato. C'è almeno un nodo nella lista, ma questo ragazzo nuovo appartiene prima, quindi abbiamo bisogno di muovere le cose intorno. In altre parole, se la lista è iniziata con un solo, diciamo, solo il numero 17, che è il - in realtà, siamo in grado di farlo in modo più chiaro. Se cominciamo la nostra storia con un puntatore qui chiamato per primo, e inizialmente è NULL, e inseriamo il numero 9, il numero 9 appartiene chiaramente all'inizio della lista. Quindi facciamo finta che abbiamo appena malloced l'indirizzo o il numero 9 e metterlo qui. Se il primo è 9 per impostazione predefinita, il primo scenario abbiamo discusso significa solo punto cerchiamo di questo tizio qui, lasciare il valore NULL, ora abbiamo il numero 9. Il numero accanto vogliamo inserire è 17. 17 appartiene qui, quindi stiamo andando a fare qualche passo in questa logica. Quindi cerchiamo di, invece, prima di farlo, facciamo finta che abbiamo voluto inserire il numero 8. 

Quindi, solo per comodità, ho intenzione di disegnare qui. Ma ricordate, malloc può mettere più da nessuna parte. Ma per l'amor di disegno, la metterò qui. Così finta ho appena assegnato un nodo per il numero 8, questo è NULL per impostazione predefinita. Che ora deve accadere? Un paio di cose. Abbiamo fatto questo errore sul palco il Lunedi in cui abbiamo aggiornato un puntatore come questo, poi ha fatto questo, e poi ha sostenuto - siamo orfani tutti gli altri sul palco. Perché Can '- l'ordine delle operazioni qui è importante, perché ora abbiamo perso questo nodo 9, che è solo una sorta di galleggiare nello spazio. Quindi questo non è l'approccio giusto il Lunedi. Per prima cosa è necessario fare qualcosa di diverso. Lo stato del mondo si presenta così. Inizialmente, 8 è stato assegnato. Quale sarebbe un modo migliore di inserire 8? Invece di aggiornare questo primo puntatore, basta aggiornare questa qui invece. Quindi abbiamo bisogno di una riga di codice che sta per trasformare questo carattere NULL in un puntatore reale che sta puntando al nodo 9, e poi possiamo tranquillamente cambiare primo a puntare a questo ragazzo qui. Ora abbiamo una lista, una lista concatenata, di due elementi. E che cosa significa questo in realtà aspetto qui? Se guardiamo il codice, si noti che ho fatto esattamente questo. Ho detto newptr, e in questa storia, newptr stava indicando questo ragazzo. 

Permettetemi quindi di disegnare una cosa, e ho dovuto lasciare in camera un po 'più per questo. Quindi perdona il disegno piccolo piccolo. Questo ragazzo si chiama newptr. Questa è la variabile che ha dichiarato poche righe prima, in linea - appena sopra 25. Ed è che punta a 8. Quindi, quando dico newptr-> next, che significa andare alla struct che viene puntato da newptr, quindi eccoci qui, andare lì. Poi la freccia sta dicendo ottenere il campo successivo, e poi la = dice che valore messo lì? Il valore che era in prima; quale valore era in prima? In primo luogo è stato indicando questo nodo, in modo che significa che questo dovrebbe puntare a questo nodo. In altre parole, anche se quello che sembra un pasticcio ridicolo con la mia scrittura, ciò che è una semplice idea di semplicemente spostando queste frecce intorno si traduce in codice con un solo questo rivestimento uno. Conservare ciò che è nel primo campo successivo e quindi aggiornare la prima cosa che è in realtà. Andiamo avanti e avanzare rapidamente attraverso alcune di queste, e guardare solo in questo inserimento della coda, per ora. Supponiamo che io arrivare al punto in cui trovo che il campo successivo di qualche nodo è NULL. E a questo punto della storia, un dettaglio che mi sto passando sopra è che ho introdotto un altro puntatore qui in linea 142, puntatore predecessore. Essenzialmente, a questo punto della storia, una volta che la lista riceve lunga, I tipi di bisogno di camminare con due dita, perché se vado troppo lontano, Ricordo in un unico elenco di lunghezza, non si può tornare indietro. Quindi questa idea di predptr è il mio dito a sinistra, e newptr - non newptr. Un altro puntatore che è qui è il mio altro dito, e io sono solo tipo di camminare della lista. Questo è il motivo che esiste. Ma andiamo in considerazione solo uno dei casi più semplici qui. Se il campo successivo puntatore è NULL, qual è l'implicazione logica? Se l'attraversamento di questa lista e si colpisce un puntatore NULL? Sei alla fine della lista, e quindi il codice per aggiungere poi questo elemento aggiuntivo è una sorta di intuitiva avrà quel nodo la cui prossima puntatore è NULL, quindi questo è attualmente NULL, e cambiare, però, di essere l'indirizzo del nuovo nodo. Quindi siamo solo disegnando nel codice la freccia che ha sul palco alzando la mano sinistra di qualcuno. 

E il caso che io agito le mani per ora, solo perché penso che sia facile perdersi quando lo facciamo in questo tipo di ambiente, è il controllo per l'inserimento al centro della lista. Ma intuitivamente, ciò che deve accadere, se si vuole capire dove un numero appartiene al centro è che si deve camminare la con più di un dito, più di un puntatore, capire dove la sua appartenenza per il controllo è l'elemento <quello attuale, > Quello attuale, e una volta trovato quel posto, allora devi fare questo tipo di gioco delle tre carte in cui si muovono le lancette intorno con molta attenzione. E la risposta, se vuoi ragionare a casa da soli, si riduce solo a queste due righe di codice, ma l'ordine di queste linee è super importante. Perché se si lascia cadere la mano di qualcuno e sollevare qualcun altro nell'ordine sbagliato, ancora una volta, si potrebbe finire per bambini orfani della lista. Per riassumere più concettualmente, l'inserimento in coda è relativamente semplice. L'inserimento in testa è anche relativamente semplice, ma è necessario aggiornare un puntatore aggiuntivo questo momento per spremere il numero 5 nella lista qui, e poi l'inserimento nel mezzo comporta sforzo ancor più, inserire con molta attenzione il numero 20 nella sua posizione corretta, che si trova tra 17 e 22. Quindi è necessario fare qualcosa di simile hanno il nuovo nodo di 20 punti a 22, e poi, il puntatore quale nodo ha bisogno di essere aggiornato per l'ultima? E '17, per inserirlo in realtà. Quindi, di nuovo, io differire il codice vero e proprio per quella particolare implementazione. 

A prima vista, è un po 'esagerata, ma in realtà è solo un ciclo infinito che è il looping, looping, looping, looping, e la rottura non appena si preme il puntatore NULL, a questo punto si può fare l'inserimento necessaria. Questo, quindi, è rappresentativo legato codice di inserimento nell'elenco. E 'stato una specie di sacco, e ci si sente come abbiamo risolto un problema, ma abbiamo introdotto uno completamente diverso. Francamente, abbiamo passato tutto questo tempo il grande O e Ω e tempo di esecuzione, cercando di risolvere i problemi più rapidamente, e qui stiamo facendo un grande passo indietro, ci si sente. E tuttavia, se l'obiettivo è quello di memorizzare i dati, ci si sente come il Santo Graal, come abbiamo detto il Lunedi, sarebbe davvero per memorizzare le cose immediatamente. 

Infatti, si supponga che abbiamo fatto mettere da parte lista collegata per un attimo e abbiamo invece introdotto la nozione di una tabella. E facciamo solo pensare a un tavolo per un momento come una matrice. Questo array e questo caso ha qui circa 26 elementi, da 0 a 25, e supponiamo che ci voleva un po pezzo di memoria per i nomi: Alice e Bob e Charlie e simili. E avete bisogno di qualche struttura dati per memorizzare quei nomi. Beh, si potrebbe usare qualcosa di simile a una lista concatenata e si poteva camminare l'elenco inserendo Alice prima di Bob e Charlie dopo che Bob e così via. E, in effetti, se si desidera vedere il codice come quello per inciso, So che in list2.h, facciamo esattamente questo. Noi non passerà attraverso questo codice, ma questa è una variante del primo esempio che presenta una struttura altre che abbiamo visto prima studente chiamato, e poi quello che in realtà memorizza nella lista concatenata è un puntatore ad una struttura studente piuttosto che un intero semplice piccola, n. Quindi realizzare c'è un codice lì che coinvolge stringhe reali, ma se l'obiettivo a portata di mano proprio ora è quello di affrontare il problema di efficienza, non sarebbe bello se si sta per fornire un oggetto chiamato Alice, vogliamo metterla nella posizione giusta in una struttura dati, ci si sente come sarebbe davvero bello mettere solo Alice, il cui nome inizia con A, nella prima posizione. E Bob, il cui nome inizia con la B, in seconda posizione. Con un array, o cominciamo definendolo una tabella, una tabella hash a che, siamo in grado di fare esattamente questo. Se ci viene dato un nome come Alice, una stringa come Alice, in cui si fa a mettere A-l-i-c-e? Abbiamo bisogno di un euristici. Abbiamo bisogno di una funzione per prendere un po 'di input come Alice e restituire una risposta, "Metti Alice in questa posizione." E questa funzione, questa scatola nera, sta per essere chiamata una funzione di hash. 

Una funzione hash è una cosa che richiede un input, come "Alice", e ritorna a voi, in genere, la posizione numerica in qualche struttura dati in cui Alice appartiene. In questo caso, la funzione hash dovrebbe essere relativamente semplice. La nostra funzione hash dovrebbe dire, se si è data "Alice", quale personaggio dovrei preoccuparmi? La prima. Così guardo [0], e allora io dico se [0] carattere è A, restituisce il numero 0. Se è B, ritorno 1. Se si tratta di C, restituisce 2, e così via. Tutto indice 0, e che mi permettesse di inserire Alice e poi Bob e poi Charlie e così via in questa struttura dati. Ma c'è un problema. Che cosa succede se Anita arriva di nuovo? Dove mettiamo Anita? Il suo nome, anche, inizia con la lettera A, e ci si sente come se avessimo fatto un casino ancora più grande di questo problema. Ora abbiamo inserimento immediato, costante di tempo di inserimento, in una struttura dati piuttosto che peggio-caso lineare, ma cosa possiamo fare con Anita in questo caso? Quali sono le due opzioni, in realtà? Si '? [Risposta studente, incomprensibile] Va bene, in modo da poter avere un'altra dimensione. Questo è un bene. Così siamo in grado di costruire le cose in 3D, come abbiamo parlato verbalmente il Lunedi. Si potrebbe aggiungere un altro accesso qui, ma supponiamo che no, sto cercando di mantenere questo semplice. L'obiettivo intero qui è di avere immediatamente accesso in tempo costante, Ecco, questo è l'aggiunta di troppa complessità. Quali sono le altre opzioni quando si cerca di inserire Anita in questa struttura dati? Si '? [Risposta studente, incomprensibile] Bene. Così si potrebbe andare tutti gli altri verso il basso, come Charlie trilli giù Bob e Alice, e poi abbiamo messo Anita dove vuole davvero essere. 

Naturalmente, ora, c'è un effetto collaterale di questo. Questa struttura di dati è probabilmente utile non perché vogliamo inserire le persone una volta ma perché vogliamo verificare se sono disponibili più tardi se si desidera stampare tutti i nomi nella struttura dati. Stiamo per fare qualcosa con questi dati alla fine. Così ora abbiamo fregati tipo di Alice, che non è più dove si suppone che sia. Né è Bob, né Charlie. Quindi forse questa non è una buona idea. Ma in effetti, questa è una opzione. Si potrebbe spostare tutti verso il basso, o diamine, Anita arrivata in ritardo al gioco, perché non appena messo Anita non qui, non qui, non qui, facciamo solo metterla un po 'più in basso nell'elenco. Ma allora il problema inizia a devolvere nuovamente. Potreste essere in grado di trovare istantaneamente Alice, basato sul suo nome. E Bob istantaneamente, e Charlie. Ma poi si guarda per Anita, e si vede, hmm, Alice è nel modo. Beh, fammi controllare sotto Alice. Bob non è Anita. Charlie non è Anita. Oh, non vi è Anita. E se si continua quel treno della logica fino in fondo, qual è il caso peggiore tempo di esecuzione di trovare o inserire Anita in questa nuova struttura di dati? E 'O (n), giusto? Dato che nel peggiore dei casi, c'è Alice, Bob, Charlie. . . tutta la strada fino a qualcuno chiamato "Y", quindi non c'è un solo posto a sinistra. Per fortuna, non abbiamo uno chiamato "Z", e quindi abbiamo messo Anita al più basso. 

Non abbiamo davvero risolto il problema. Quindi forse abbiamo bisogno di introdurre questa terza dimensione. E si scopre, se lo facciamo presentare questa terza dimensione, non possiamo fare questo perfettamente, ma il Santo Graal sta per essere sempre tempo costante inserimento e inserimenti dinamici in modo che non abbiamo a livello di codice un array di dimensione 26. Siamo in grado di inserire i nomi che vogliamo, ma facciamo il nostro 5 minuti di pausa qui e poi farlo correttamente. Bene. Ho impostato la storia fino piuttosto artificialmente ci scegliendo Alice e Bob e poi Charlie e poi Anita, il cui nome è stato, ovviamente, andando a collidere con Alice. Ma la domanda che ci si è concluso il Lunedi con quanto è probabile che sia che si potranno ottenere questo tipo di collisioni? In altre parole, se si inizia a utilizzare questa struttura tabellare, che è in realtà solo una matrice, in questo caso di 26 posizioni, E se i nostri ingressi sono invece distribuiti uniformemente? Non è artificialmente Alice e Bob e Charlie e David, e così via in ordine alfabetico, è distribuita in modo uniforme dalla A alla Z. 

Forse dobbiamo solo avere fortuna e non abbiamo intenzione di avere due di A o due di B con probabilità molto alta, ma, come qualcuno ha sottolineato, se questo problema generalizzato e non 0-25 ma, ad esempio, da 0 a 364 o 65, spesso il numero di giorni in un anno tipico, e ha posto la domanda: "Qual è la probabilità che due di noi in questa stanza hanno la stessa data di nascita?" In altre parole, qual è la probabilità che due di noi hanno un nome che inizia con la A? Il tipo di domanda è la stessa, ma questo spazio di indirizzi, questo spazio di ricerca, è più grande in caso di compleanni, perché abbiamo più giorni così tanti durante l'anno che le lettere dell'alfabeto. Qual è la probabilità di una collisione? Be ', possiamo pensare a questo capire la matematica in senso opposto. Qual è la probabilità di collisioni? Beh, questa espressione qui dice che ciò che è la probabilità se c'è una sola persona in questa stanza, che hanno un compleanno unico? E 'al 100%. Perché se c'è una sola persona in camera, suo compleanno può essere uno qualsiasi dei 365 giorni di esercizio. Quindi, le opzioni 365/365 mi dà un valore di 1. Quindi, la probabilità in questione al momento è solo 1. Ma se c'è una seconda persona in camera, qual è la probabilità che il loro compleanno è diverso? Ci sono solo 364 giorni possibili, anni bisestili, ignorando per il loro compleanno non entrare in collisione con le altre persone. Quindi 364/365. Se una terza persona arriva, è 363/365, e così via. Quindi continuiamo a moltiplicare insieme queste frazioni, che sono sempre più piccolo, per capire che cosa è la probabilità che tutti noi abbiamo compleanni unici? Ma allora possiamo, ovviamente, basta prendere questa risposta e capovolgere in giro e fare 1 meno tutto questo, l'espressione che più volte si ottiene se vi ricordate la parte posteriore dei tuoi libri di matematica, sembra un po 'di qualcosa come questo, che è molto più facilmente interpretato graficamente. E questo grafico qui ha sull'asse x il numero di compleanni, o il numero di persone con compleanni, e sull'asse delle y è la probabilità di una partita. E ciò che questo sta dicendo è che se hai, diciamo, anche, scegliamo qualcosa come 22, 23. Se ci sono 22 o 23 persone nella stanza, la probabilità che due di quelle pochissime persone avranno la stessa data di nascita è in realtà alto super, combinatorio. 50% probabilità che in una classe di soli 22 persone, un seminario, praticamente, 2 di queste persone stanno per avere lo stesso compleanno. Perché ci sono tanti modi in cui si può avere lo stesso compleanno. Ancora peggio, se si guarda al lato destro del grafico, per il momento si dispone di una classe con 58 studenti in esso, la probabilità di 2 persone che hanno un compleanno è super, super-alta, quasi il 100%. Ora, questa è una sorta di fatto divertente della vita reale. 

Ma le implicazioni, ora, per le strutture di dati e la memorizzazione delle informazioni significa che solo assumendo che abbiate un piacevole, pulito, distribuzione uniforme dei dati e si dispone di una matrice abbastanza grande da contenere un sacco di cose non significa che si vuole convincere la gente in luoghi unici. Stai andando ad avere collisioni. Quindi, questa nozione di hashing, come si chiama, prendendo un ingresso come "Alice" e massaggio in qualche modo e poi tornare una risposta del tipo 0 o 1 o 2. Tornando un po 'di output di tale funzione è afflitto da questa probabilità di collisione. Quindi, come possiamo gestire queste collisioni? Beh, in un caso, si può prendere l'idea che è stata suggerita. Possiamo solo spostare tutti verso il basso, o forse, un po 'più semplice, piuttosto che spostare tutti gli altri, facciamo solo spostare Anita al fondo dello spot disponibili. Quindi, se Alice è in 0, Bob è in 1, Charlie è in 2, ci limiteremo a mettere Anita in posizione 3. E questa è una tecnica in strutture di dati chiamato scansione lineare. Lineare perché si sta solo a piedi questa linea, e tu sei una sorta di sondaggio per località disponibili nella struttura dati. Naturalmente, questo devolve in O (n). Se la struttura di dati è davvero completo, ci sono 25 persone in esso già, e poi Anita arriva, finisce in quello che sarebbe posizione Z, e va bene. Si adatta ancora, e possiamo trovarla in seguito. 

Ma questo era in contrasto con l'obiettivo di accelerare le cose. Che importa se abbiamo invece introdotto questa terza dimensione? Questa tecnica viene generalmente chiamato concatenazioni separate, o che hanno catene. E che una tabella di hash è ora, questa struttura tabulare, la tabella è solo un array di puntatori. Ma ciò che i puntatori puntare a indovinare che cosa è? Una lista concatenata. Che importa se prendiamo il meglio di entrambi i mondi? Usiamo gli array per gli indici iniziali nella struttura di dati in modo che possiamo immediatamente andare a [0] [1], [30] e così via, ma in modo da avere una certa flessibilità e può andare bene Anita e Alice e Adam e qualsiasi altro Un nome, noi invece lasciare che l'altro asse crescere arbitrariamente. E infine, come di Lunedi, hanno questa capacità espressiva con la lista collegata. Possiamo coltivare una struttura di dati in modo arbitrario. In alternativa, si può solo fare un enorme array a 2 dimensioni, ma che sta per essere una situazione terribile se una delle righe in un array a 2 dimensioni non è abbastanza grande per la persona in più il cui nome capita di iniziare con A. Dio non voglia che abbiamo di riassegnare un enorme 2-struttura tridimensionale solo perché ci sono così tante persone denominate A, soprattutto quando ci sono così poche persone di nome qualcosa Z. E 'solo andando a essere una struttura molto scarsa di dati. Quindi non è affatto perfetto, ma ora abbiamo almeno la possibilità di trovare immediatamente in cui Alice e Anita appartiene, almeno in termini di asse verticale, e poi non ci resta che decidere dove mettere Anita o Alice in questa lista collegata. Se non si cura di ordinamento le cose, in quanto tempo potremmo inserire Alice in una struttura come questa? E 'tempo costante. Abbiamo indice in [0], e se c'è nessuno, Alice va all'inizio di quella lista collegata. Ma non è un affare enorme. Perché se poi arriva Anita un certo numero di passi dopo, dove viene Anita appartiene? Beh, [0]. OOP. Alice è già in tale lista collegata. 

Ma se non si preoccupano di ordinamento questi nomi, possiamo semplicemente spostare Alice sopra, inserto Anita, ma anche questo è il tempo costante. Anche se ci sono Alice e Adam e tutti questi altri nomi di A, non è veramente spostare fisicamente. Perché? Dato che abbiamo appena fatto qui con la lista collegata, che conosce questi nodi sono stati comunque? Tutto quello che dovete fare è spostare le briciole di pane. Spostare le frecce intorno, non c'è bisogno di spostare fisicamente i dati in giro. Quindi possiamo inserire Anita, in quel caso, all'istante. Costante di tempo. Così abbiamo tempo costante ricerca, e costante in tempo l'inserimento di uno come Anita. Ma tipo di semplificare il mondo. E se in seguito si desidera trovare Alice? E se in seguito si desidera trovare Alice? Quanti passi è che andando a prendere? [Risposta studente, incomprensibile] Esattamente. Il numero di persone prima di Alice nella lista collegata. Quindi non è tutto perfetto, perché la nostra struttura dati, ancora una volta, ha questo accesso verticale e poi ha queste liste collegate pendenti - in realtà, cerchiamo di non tirarla un un array. Ha queste liste collegate appesa fuori di esso, che sembra un po 'di qualcosa come questo. Ma il problema è se Alice e Adam e tutti questi altri nomi di A finiscono sempre più là, trovare qualcuno potrebbe finire per prendere un po 'di passi, bcause si deve attraversare la lista collegata, che è una operazione lineare. Quindi, veramente, quindi, il tempo di inserimento è in definitiva O (n), dove n è il numero di elementi nella lista. Diviso per, diciamo arbitrariamente chiamare m, dove m è il numero di liste concatenate che abbiamo in questo asse verticale. In altre parole, se veramente assume una distribuzione uniforme dei nomi, del tutto irrealistico. Ci sono, ovviamente, più di alcune lettere di altri. 

Ma se assumiamo per il momento una distribuzione uniforme, e abbiamo n persone in totale, e m catene totali disponiamo, allora la lunghezza di ciascuna di queste catene abbastanza semplicemente sarà totale, n diviso per il numero di catene. Quindi n / m. Ma qui è dove possiamo essere tutti matematicamente intelligente. m è una costante, perché c'è un numero fisso di questi. Hai intenzione di dichiarare la matrice all'inizio, e non siamo ridimensionare l'asse verticale. Per definizione, che rimane fisso. E 'solo l'asse orizzontale, per così dire, che sta cambiando. Quindi tecnicamente, questa è una costante. Così ora, l'inserimento tempo è più o meno O (n). In modo che non si sente più di tanto meglio. Ma qual è la verità qui? Bene, tutto questo tempo, per settimane, abbiamo detto O (n ²). O (n), 2 x n ², - n, diviso per 2. . . ECH. E 'solo ² n. Ma ora, in questa parte del semestre, possiamo iniziare a parlare del mondo reale. E n / m è assolutamente più veloce di un semplice n solo. Se si dispone di mille nomi, e li suddividere in segmenti più in modo da avere solo dieci nomi in ciascuna di queste catene, dieci cose assolutamente ricerca sta per essere più veloce di mille cose. E così uno dei set di problemi imminenti sta per metterti alla prova a pensare esattamente questo, anche se, sì, asintoticamente e matematicamente, questa è ancora solo lineare, che aspira, in generale, quando si cerca di trovare le cose. In realtà, sta andando ad essere più veloce di quello a causa di questo valore. E così c'è ancora una volta sarà questo trade-off e questo conflitto tra teoria e realtà, e una delle manopole inizierà a ruotare a questo punto nel semestre è più della realtà come noi una sorta di preparazione per la fine di semster, come presentare al mondo della programmazione web, dove veramente, le prestazioni sono di andare a contare, perché gli utenti stanno per inizia a sentire e apprezzare le decisioni di progettazione poveri. 

Così come si fa a fare l'attuazione di una collegata - una tabella hash con 31 elementi? E l'esempio precedente era arbitrariamente dei compleanni. Se qualcuno ha un compleanno dal 1 ° gennaio e 1 ° febbraio ci metterli in questo secchio. Se è 2 gennaio, 2 febbraio, 2 marzo, li messo in questo secchio. Ecco perché è stato 31. Come si fa a dichiarare una tabella di hash? Può essere piuttosto semplice, tavolo * nodo è il mio nome arbitrario per questo, [31]. Questo mi dà 31 puntatori ai nodi, e che mi permette di avere 31 puntatori a liste collegate anche se tali catene sono inizialmente NULL. Cosa voglio mettere se voglio memorizzare "Alice", "Bob", "Charlie"? Bene, abbiamo bisogno di avvolgere le cose in una struttura perché abbiamo bisogno di Alice per puntare a Bob, per puntare a Charlie, e così via. Non possiamo avere il nome da solo, così ho potuto creare una nuova struttura denominata nodo qui. 

Che cosa è un nodo vero? Che cosa è un nodo in questa nuova lista collegata? La prima cosa, chiamata parola, è per il nome della persona. LUNGHEZZA, presumibilmente, riguarda la lunghezza massima del nome di un essere umano, qualunque cosa sia, 20, 30, 40 caratteri in casi angolo folli, e +1 è per che cosa? E 'solo il carattere NULL in più, \ 0. Quindi, questo nodo è avvolgente "qualcosa" all'interno di se stessa, ma dichiara anche un puntatore chiamato prossima in modo che possiamo catena di Alice a Bob a Charlie e così via. Può essere NULL, ma non deve necessariamente essere. Hai domande su queste tabelle hash? Si '? [Studente chiedendo questione, incomprensibile] Un array - buona domanda. Perché questo carattere di parola in un array e non solo char *? In questo esempio un po 'arbitraria, non volevo dover ricorrere a malloc per ciascuno dei nomi originali. Volevo dichiarare una quantità massima di memoria per la stringa modo che io possa copiare nella struttura Alice \ 0 e non avere a che fare con malloc e free e simili. Ma potrei farlo se volevo essere più consapevoli della fruizione degli spazi. Bella domanda. Quindi cerchiamo di generalizzare da questo e focalizzare la restante oggi su strutture dati più generalmente e altri problemi che si possono risolvere con i fondamenti stessi anche se le strutture di dati si potrebbero differire nei loro particolari. 

Così si scopre in informatica, gli alberi sono molto comuni. E si può pensare ad una sorta di albero come un albero genealogico, dove ci sono alcune radici, alcune matriarca o patriarca, nonna o nonno o precedente indietro, sotto il quale sono mamma e papà o fratelli diversi o simili. Così una struttura ad albero con nodi e ha figli, di solito 0 o più figli per ogni nodo. E parte del gergo che vedete in questa foto qui è uno qualsiasi dei bambini piccoli o nipoti sui bordi che non hanno le frecce provenienti da loro, questi sono i cosiddetti foglie e chiunque all'interno è un nodo interno, si può chiamare qualcosa in questo senso. Ma questa struttura è abbastanza comune. Questo è un po 'arbitraria. Abbiamo un bambino a sinistra, abbiamo tre figli a destra, due bambini in basso a sinistra. Così possiamo avere diverse dimensioni alberi, ma se cominciamo a standardizzare le cose, e si potrebbe richiamare questo dal video Patrizio sulla ricerca binaria da una breve precedente on-line, ricerca binaria non deve essere implementato con un array o pezzi di carta su una lavagna. Si supponga di voler memorizzare i numeri in una struttura più sofisticata di dati. È possibile creare un albero come questo. Si potrebbe avere un nodo dichiarata in C, e tale nodo può avere almeno due elementi all'interno di esso. Uno è il numero che si desidera memorizzare, e l'altro è - beh, abbiamo bisogno di un altro. L'altro è i suoi figli. Quindi, ecco un'altra struttura dati. Questa volta, un nodo è definito come memorizzazione di un numero n e poi due puntatori, figlio sinistro e figlio destro. E non sono arbitrarie. La cosa interessante di questo albero? 

Qual è il modello nel modo in cui abbiamo posto questo fuori o come Patrick ha esposto nel suo video? E 'abbastanza ovvio che c'è un po' di ordinamento sta succedendo qui, ma qual è la semplice regola? Si '? [Risposta studente, incomprensibile] Perfetto. Se un'occhiata a questo, si vedono i piccoli numeri a sinistra, grandi numeri a sinistra, ma questo è vero per ogni nodo. Per ogni nodo, il suo figlio sinistro a meno di essa, e il suo figlio destro più grande di essa. Che cosa questo significa che ora è se voglio cercare la struttura di dati per, ad esempio, il numero 44, Devo iniziare alla radice, perché, come con tutte queste strutture più complesse di dati ora, abbiamo solo un puntatore ad una cosa, l'inizio. E in questo caso, l'inizio è la radice. Non è la fine a sinistra, è la radice di questa struttura. Così vedo qui è 55, e sto cercando 44. In che direzione voglio andare? Beh, io voglio andare a sinistra, perché ovviamente, il diritto sta per essere troppo grande. Quindi notare qui, tu sei una sorta di concettualmente tagliare l'albero a metà perché non si è mai scendere al lato destro. Così ora vado dal 55 al 33. E 'troppo piccolo di un numero. Sto cercando per il 44, ma ora so che se 44 è in questo albero, posso andare, ovviamente, a destra. Quindi, di nuovo, io sono la potatura l'albero a metà. E 'praticamente identico concettualmente nella rubrica telefonica. E 'identico a quello che abbiamo fatto con i documenti sulla lavagna, ma è una struttura più sofisticata che ci permette di fare effettivamente questo divide et impera di progettazione dell'algoritmo, e infatti, attraversando una struttura come questa - whoops. Attraversamento di una struttura come questa, dove è solo "andare in questo modo o andare in quel modo," vuol dire tutto ciò che il codice che si è piegato la vostra mente in un primo momento, quando l'attuazione nella sezione o camminare attraverso di essa in casa, per la ricerca binaria, utilizzando la ricorsione o l'iterazione, si tratta di un dolore al collo. Trovare l'elemento centrale, quindi fare il vostro arrotondamento verso l'alto o verso il basso. 

C'è una bellezza a questo perché ora possiamo usare la ricorsione di nuovo, ma molto più pulito. Infatti, se siete al numero 55 e si desidera trovare 44, si va a sinistra, in questo caso, allora cosa fai? Si esegue l'algoritmo esattamente lo stesso. Si controlla il valore del nodo, poi si va a sinistra oa destra. Poi si controlla il valore del nodo, andare a sinistra oa destra. Questo si adatta perfettamente alla ricorsione. Quindi, anche se in passato abbiamo fatto alcuni esempi piuttosto arbitrari che comportano ricorsione che non ha bisogno di essere ricorsiva, con stuctures di dati, in particolare gli alberi, è una perfetta applicazione di questa idea di prendere un problema, contrazione, e quindi risolvere lo stesso tipo di, ma più piccola, programma. 

Quindi c'è un'altra struttura di dati che si possono introdurre. Questo è stato progettato a prima vista sembrare criptico, ma questo è incredibile. Quindi questa è una struttura di dati chiamata un trie, trie, che viene ereditata dal reperimento delle parole, che non si pronuncia ri-try-val, ma questo è ciò che il mondo chiama queste cose. Prova. T-r-i-e. Si tratta di una struttura ad albero di qualche tipo, ma tutti i nodi in un trie sembra essere cosa? E questo è un po 'fuorviante, perché è una specie di abbreviato. Ma sembra che ogni nodo in questo trie è in realtà un array. E anche se l'autore di questo schema non l'ha dimostrato, in questo caso, questo trie è una struttura di dati il ​​cui scopo nella vita è memorizzare parole come A-l-i-c-e o B-o-b. E il modo in cui tali dati memorizza Alice e Bob e Charlie e Anita, e così via si utilizza un array in base al quale per memorizzare Alice in un trie, si parte dal nodo radice che si presenta come una matrice, ed è stato scritto in notazione abbreviata. L'autore omesso abcdefg perché non vi erano i nomi con quella. Hanno solo mostrato M e P e T, ma in questo caso, passiamo lontano da Alice e Bob e Charlie ad alcuni nomi che sono qui. Maxwell è in realtà in questo diagramma. Così come ha fatto il negozio autore M-a-x-w-e-l-l? Lui o lei ha iniziato al nodo radice, e andò a [M], quindi circa 13, la posizione 13 nella matrice. Poi da lì, c'è un puntatore. Un puntatore che porta a un altro array. Da qui l'autore indicizzati in tale matrice nella posizione A, come illustrato lì in alto a sinistra, e allora lui o lei che segue il puntatore ad un altro array, e siamo andati a il puntatore nella posizione X. Poi nella posizione successiva matrice W, E, L, L, e così via, e, infine, andiamo in realtà tenta di mettere una foto a questo. Che aspetto ha un nodo come nel codice? Un nodo in un trie contiene un array di puntatori a più nodi. Ma c'è anche avuto modo di essere un qualche tipo di valore booleano, almeno in questa implementazione. Mi è capitato di chiamarlo is_word. Perché? Perché quando si sta inserendo Maxwell, non sei l'inserimento nulla in questa struttura dati. Lei non è iscritto M. Lei non è iscritto X. Tutto quello che stai facendo è seguito puntatori. Il puntatore che rappresenta M, quindi il puntatore che rappresenta A, quindi il puntatore che rappresenta X, allora W, E, L, L, ma quello che dovete fare alla fine è una sorta di andare, controllare, ho raggiunto questa posizione. C'era una parola che termina qui nella struttura dati. 

Così che cosa è un trie realmente pieno di una e l'autore ha scelto di rappresentare questi capolinea con piccoli triangoli. Questo significa solo che il fatto che questo triangolo è qui, il valore booleano true significa che se si va indietro nella struttura, questo significa che una parola di nome Maxwell è in questo. Ma la parola foo, per esempio, non è nella struttura, perché se mi metto al nodo radice qui in alto, Non c'è puntatore f, nessun puntatore o, nessun puntatore o. Foo non è un nome in questo dizionario. Ma al contrario, Turing, t-u-r-i-n-g. Anche in questo caso, non ho memorizzare t o u o r o i o n o g. Ma ho fatto conservare in questa struttura dati un valore di vero modo qui in questo nodo - nella struttura ad albero impostando questo valore booleano di is_word su true. Quindi un trie è una specie di questa struttura meta molto interessante, dove non sei veramente memorizzare le parole stesse per questo tipo di dizionario. Per essere chiari, sei solo la memorizzazione sì o no, non c'è una parola che finisce qui. 

Ora, qual è l'implicazione? Se si dispone di 150.000 parole in un dizionario che si sta cercando di memorizzare usando qualcosa come una lista concatenata, che si sta per avere 150.000 nodi nella lista collegata. E trovare una di quelle parole in ordine alfabetico potrebbe prendere O (n) tempo. Il tempo lineare. Ma nel caso di specie di un trie, qual è il tempo di esecuzione di trovare una parola? Si scopre la bellezza qui è che anche se si ha già 149.999 parole in questo dizionario, come attuato con questa struttura dati, quanto tempo ci vuole per trovare o inserire una persona in più in questo, come Alice, Alice? Beh, e 'solo 5, forse 6 passi per il carattere finale. Poiché la presense di altri nomi nella struttura non ottenere nel modo di inserimento Alice. Inoltre, trovare Alice una volta che ci sono 150.000 parole in questo dizionario non interferisce con l'attività di ricerca di Alice a tutti, perché Alice è. . . . . qui, perché ho trovato un valore booleano. E se non c'è boolean vero, allora Alice non è in questa struttura di dati di parole. In altre parole, il tempo di esecuzione di trovare cose e inserendo le cose in questa nuova struttura dei dati dei trie è O - non è n. Poiché la presense di 150.000 persone non ha alcun effetto su Alice, a quanto pare. Quindi chiamiamolo k, dove k è la lunghezza massima di una parola in inglese che in genere non più di 20-qualcosa caratteri. Quindi k è una costante. Così il Santo Graal ci sembra di aver trovato ora è quella di un trie, costante di tempo per inserti, per le ricerche, per delezioni. Poiché il numero di cose che già nella struttura, che non sono ancora fisicamente lì. Anche in questo caso, sono appena sorta di crocetta, sì o no, non ha alcun impatto sul suo tempo futuro in esecuzione. 

Ma ci deve essere un trucco, altrimenti non avremmo sprecato così tanto tempo su tutte queste strutture di dati ad altri solo per arrivare, infine, a quello segreto che è incredibile. Quindi, quale prezzo stiamo pagando per raggiungere questo obiettivo la grandezza qui? Spazio. Questa cosa è enorme. E la ragione che l'autore non lo presentiamo qui, si noti che tutte queste cose che sembrano gli array, egli non ha tratto il resto della struttura, il resto del trie, perché non sono solo rilevanti per la storia. Ma tutti questi nodi sono super wide, e ogni nodo dell'albero riprende 26 o in realtà, potrebbe essere 27 caratteri perché in questo caso mi è stato anche lo spazio per l'apostrofo in modo da poter avere le parole apostrofato. In questo caso, si tratta di matrici gamma. Così, anche se non stanno picutured, questo richiede una massiccia quantità di RAM. Il che potrebbe andare bene, especilly in hardware moderno, ma questo è il compromesso. Otteniamo meno tempo da spendere di più spazio. Allora, dove sta succedendo tutto questo? Bene, facciamo - vediamo qui. Facciamo un salto a questo ragazzo qui. 

Che ci crediate o no, il divertimento tanto quanto C è stato per qualche tempo, stiamo raggiungendo il punto nel semestre in cui è il momento di transizione verso le cose più moderne. Cose su un livello più alto. E anche se per un paio di settimane dovremo continuare a immergersi nel mondo di puntatori e gestione della memoria per ottenere che la comodità con cui si possono poi costruire, la fine del gioco è in definitiva di introdurre, per ironia della sorte, non questa lingua. Passeremo, come 10 minuti a parlare di HTML. Tutto il codice HTML è un linguaggio di markup, e quello che è un linguaggio di markup è questa serie di parentesi aperta e staffe chiuse che dicono 'fare questo bold' 'Fanno di questo corsivo' 'fare questa centrato.' Non è tutto ciò che intellettualmente interessante, ma è super utile. Ed è certamente onnipresente in questi giorni. Ma ciò che è potente sul mondo di HTML, e programmazione web più in generale, sta costruendo cose dinamici, la scrittura di codice in linguaggi come PHP o Python o Ruby o Java o C #. In realtà, qualunque sia la vostra lingua di scelta è, e la generazione di HTML dinamico. Generazione di una cosa chiamata CSS dinamicamente. I fogli di stile CSS, che è anche di estetica. E così, anche se, oggi, se vado a qualche sito come il Google.com familiare, e vado a vedere, sviluppatore, visualizza sorgente, che forse hai fatto prima, ma andando per visualizzare l'origine, questa roba sembra probabilmente abbastanza criptico. Ma questo è il codice sottostante che implementa Google.com. Sull'estremità anteriore. E in realtà tutto questo è soffice roba estetica. Si tratta di CSS qui. Se continuo a scorrimento verso il basso avremo un po 'di codice colore roba. Questo è HTML. Codice di Google sembra un casino, ma se io in realtà aprire una finestra diversa, possiamo vedere una struttura per questo. Se apro questo in su, si noti qui, è un po 'più leggibile. Stiamo andando a vedere in breve tempo questo tag, [la parola] è un tag, HTML, testa, corpo, div, script, area di testo, spanna, centrato, div. E questo è anche sorta di criptico dall'aspetto a prima vista, ma tutto questo casino segue certi schemi e modelli ripetibili, in modo che una volta che otteniamo le basi verso il basso, sarete in grado di scrivere codice come questo e quindi modificare il codice come questo utilizzando un altro linguaggio, chiamato JavaScript. E JavaScript è un linguaggio che viene eseguito all'interno di un browser oggi che usiamo sui corsi di Harvard, per lo strumento commerciale corso che utilizza le mappe di Google per darvi un sacco di dinamismo, Facebook consente di visualizzare gli aggiornamenti di stato istantanei, Twitter lo usa visualizzare tweets istantaneamente. Tutto questo inizieremo a immergerci trovi Ma per arrivarci, abbiamo bisogno di capire qualcosa su Internet. Questa clip qui è solo un lungo minuto, e supponiamo per ora questo è, infatti, come funziona Internet come un teaser per quello che sta per venire. Vi do "Guerrieri della Rete". 

[♫ ♫ musica corale lenta] [Maschio narratore] E 'venuto con un messaggio. Con un protocollo tutto suo. [♫ ♫ musica elettronica più veloce] Egli è venuto per un mondo di firewall fresco, indifferente router, e pericoli ben peggiori della morte. E 'veloce. E 'forte. E 'il protocollo TCP / IP, e lui ha il vostro indirizzo. Guerrieri della Rete. [Malan] La prossima settimana, poi. Internet. Web programmazione. Questo è CS50. [CS50.TV]