1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID MALAN: Va bene. 3 00:00:12,250 --> 00:00:13,860 Bentornati CS50. 4 00:00:13,860 --> 00:00:16,190 Questo è l'inizio della settimana 8. 5 00:00:16,190 --> 00:00:21,320 E ricordare che il problema insieme 5 conclusa con un po 'di una sfida. 6 00:00:21,320 --> 00:00:25,210 Quindi, supponendo che avete recuperato tutti i tuoi Fellows insegnamento e fotografie di CA 7 00:00:25,210 --> 00:00:30,480 nel file card.raw, si ha diritto per ora trovare tutte quelle persone, e 8 00:00:30,480 --> 00:00:34,510 un fortunato vincitore porterà a casa con uno di queste cose, il movimento salto 9 00:00:34,510 --> 00:00:37,450 dispositivo che è possibile utilizzare per la finale progetti, per esempio. 10 00:00:37,450 --> 00:00:39,860 >> Questo, ogni anno, porta a un po 'di creepiness. 11 00:00:39,860 --> 00:00:43,480 E così quello che ho pensato di fare è di condividere con voi alcune delle note che hanno 12 00:00:43,480 --> 00:00:47,370 andato avanti e indietro su l'elenco del personale di ritardo. 13 00:00:47,370 --> 00:00:51,110 Per esempio, proprio ieri sera, citazione unquote, da uno del personale 14 00:00:51,110 --> 00:00:55,000 membri, "Ho appena avuto una botta studente alla mia porta per fare una foto con me. 15 00:00:55,000 --> 00:00:59,020 Stalkers, vi dico. "Iniziato abbastanza descrittivo e poi ci siamo trasferiti 16 00:00:59,020 --> 00:01:02,830 a, circa un'ora dopo, "ho avuto un studente mi aspetta dopo la sezione 17 00:01:02,830 --> 00:01:06,080 e aveva tutti i nostri nomi e le foto su alcuni fogli di carta. «Va bene. 18 00:01:06,080 --> 00:01:09,230 Così organizzato, ma non tutto questo raccapricciante ancora. 19 00:01:09,230 --> 00:01:12,520 >> Poi, "Ero fuori città questo fine settimana, e quando sono tornato, non c'era uno in 20 00:01:12,520 --> 00:01:12,630 il mio 21 00:01:12,630 --> 00:01:16,740 camera da letto. "[risate] 22 00:01:16,740 --> 00:01:20,410 DAVID MALAN: Avanti citazione da uno staff membro ", uno studente è venuto a casa mia a 23 00:01:20,410 --> 00:01:25,330 Somerville alle 4:00 di questa mattina. "Avanti personale ", ho avuto al mio albergo a San 24 00:01:25,330 --> 00:01:30,016 Francisco e uno studente stava aspettando me alla hall con tre reflex digitali. " 25 00:01:30,016 --> 00:01:31,510 Tipo di fotocamera. 26 00:01:31,510 --> 00:01:34,980 "Non sono nemmeno sul personale in questo semestre, ma uno studente entrato in casa mia questa 27 00:01:34,980 --> 00:01:40,480 mattina e registrato il tutto con Google Glass. "E poi, infine, 28 00:01:40,480 --> 00:01:43,650 "Almeno 12 persone sono state avidamente attesa per me quando ho ottenuto dalla mia 29 00:01:43,650 --> 00:01:44,800 limo, e poi ho 30 00:01:44,800 --> 00:01:46,970 svegliò. «Va bene. 31 00:01:46,970 --> 00:01:57,690 Così tra le fotografie, come si può ricordare, è questo tizio qui, che si 32 00:01:57,690 --> 00:02:01,850 potrebbe sapere come Milo Banana, che vive con Lauren Carvalho, la nostra testa 33 00:02:01,850 --> 00:02:02,905 Teaching Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, vieni qui ragazzo. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Intendiamoci, indossa Google Glass, così vi mostreremo tutto questo dopo. 38 00:02:12,230 --> 00:02:16,190 Quindi questo è Milo, se si desidera scattare una fotografia con lui dopo. 39 00:02:16,190 --> 00:02:18,240 Se vuoi guardare fuori presso il pubblico lì. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Questo è un bene metraggio. 42 00:02:20,200 --> 00:02:22,556 Beh, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, non farlo. 44 00:02:23,941 --> 00:02:29,020 >> [Risata] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Così una parola poi su quello che ci aspetta, perché come si comincia a transizione, 47 00:02:34,550 --> 00:02:38,410 questa settimana specificamente, da C in un ambiente a riga di comando di PHP e 48 00:02:38,410 --> 00:02:42,720 Javascript e SQL e HTML e CSS in un ambiente web-based, saremo 49 00:02:42,720 --> 00:02:44,490 dotare voi con tutto l' più conoscenza per 50 00:02:44,490 --> 00:02:46,010 potenziali progetti finali. 51 00:02:46,010 --> 00:02:49,240 A questo scopo, il corso ha un tradizione di organizzazione di seminari che 52 00:02:49,240 --> 00:02:50,950 sono su temi tangenziali al corso. 53 00:02:50,950 --> 00:02:54,330 Molto legati alla programmazione e al lo sviluppo di applicazioni e così via, ma 54 00:02:54,330 --> 00:02:57,010 non necessariamente esplorato da proprio piano di studi del corso. 55 00:02:57,010 --> 00:03:00,250 >> Quindi, se si potrebbe essere interessati a una o più dei seminari di quest'anno, 56 00:03:00,250 --> 00:03:02,530 registrarsi al cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Ci sono seminari anziani a cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 E nel roster finora per quest'anno sono sorprendenti applicazioni Web con Ruby on 59 00:03:10,620 --> 00:03:13,580 Rails, che è un'alternativa linguaggio di PHP. 60 00:03:13,580 --> 00:03:14,900 Linguistica Computazionale. 61 00:03:14,900 --> 00:03:18,710 Introduzione a iOS, che è la piattaforma che viene utilizzata per iPhone e 62 00:03:18,710 --> 00:03:19,850 sviluppo iPad. 63 00:03:19,850 --> 00:03:22,890 JavaScript per applicazioni web, vedremo che, ma in questo seminario, andrai 64 00:03:22,890 --> 00:03:24,070 in più particolare. 65 00:03:24,070 --> 00:03:27,390 >> Leap Movimento, quindi dovremo effettivamente avere qualche dei nostri amici di Leap Movimento, 66 00:03:27,390 --> 00:03:29,160 l'azienda stessa, unisciti a noi. 67 00:03:29,160 --> 00:03:31,800 Domani, infatti, per fornire un hands-on seminario, se 68 00:03:31,800 --> 00:03:33,320 di interesse per voi. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, una tecnica alternativa per utilizzando JavaScript non in un browser, 70 00:03:38,770 --> 00:03:39,970 ma su un server. 71 00:03:39,970 --> 00:03:42,110 Node.js, che è molto in quella vena pure. 72 00:03:42,110 --> 00:03:43,650 Design elegante Android. 73 00:03:43,650 --> 00:03:46,990 Android essendo una alternativa molto popolare a iOS e Windows Phone 74 00:03:46,990 --> 00:03:48,790 e altre piattaforme mobili. 75 00:03:48,790 --> 00:03:51,180 E Web Defense Active Security. 76 00:03:51,180 --> 00:03:54,590 >> Quindi, in realtà, se si desidera di impegnarsi in questo, mi permetta 77 00:03:54,590 --> 00:03:55,840 prendere atto di questo. 78 00:03:55,840 --> 00:03:57,790 Siamo molto felici di dire che i nostri amici di Leap 79 00:03:57,790 --> 00:03:59,140 Movimento, che è una startup - 80 00:03:59,140 --> 00:04:01,300 questo dispositivo davvero appena arrivato un paio di mesi fa - 81 00:04:01,300 --> 00:04:05,960 ha gentilmente donato 30 tali dispositivi alla classe per altrettanti studenti, se 82 00:04:05,960 --> 00:04:08,670 vuoi prendere in prestito l'hardware verso la fine del semestre e utilizzarlo per 83 00:04:08,670 --> 00:04:10,390 un progetto finale vero e proprio. 84 00:04:10,390 --> 00:04:11,890 Essi sostengono un certo numero di lingue. 85 00:04:11,890 --> 00:04:16,040 Nessuno di loro C, nessuno di loro PHP, così realizzare uno o più di questi seminari 86 00:04:16,040 --> 00:04:16,899 potrebbe rivelarsi di interesse. 87 00:04:16,899 --> 00:04:19,730 E tutti loro sarà girato in caso in cui non si è in grado 88 00:04:19,730 --> 00:04:21,380 partecipare di persona. 89 00:04:21,380 --> 00:04:25,000 Il calendario sarà annunciato tramite mail come abbiamo solidificare camere. 90 00:04:25,000 --> 00:04:28,460 >> E, infine, se si va a projects.cs.50.net, questo è un sito 91 00:04:28,460 --> 00:04:31,450 sosteniamo ogni anno, che vi invitiamo gente della comunità, docenti, 92 00:04:31,450 --> 00:04:36,420 reparti, personale, ed entrambi in un fuori di CS50 per 93 00:04:36,420 --> 00:04:37,730 proporre idee progettuali. 94 00:04:37,730 --> 00:04:39,050 Le cose di interesse per gruppi di studenti. 95 00:04:39,050 --> 00:04:40,600 Motivi di interesse ai reparti. 96 00:04:40,600 --> 00:04:43,990 Quindi girare lì, se stai lottando con l'incertezza di ciò che si 97 00:04:43,990 --> 00:04:46,700 lei vorrebbe affrontare. 98 00:04:46,700 --> 00:04:51,760 >> Così l'ultima volta abbiamo introdotto un dubbio struttura dati più complessa di quanto ci saremmo 99 00:04:51,760 --> 00:04:53,300 visto nelle ultime settimane. 100 00:04:53,300 --> 00:04:56,550 Ci era stato l'utilizzo di matrici piuttosto felicemente come un utile se 101 00:04:56,550 --> 00:04:58,160 struttura dati semplicistico. 102 00:04:58,160 --> 00:05:00,570 Poi abbiamo introdotto questi, che naturalmente sono legati liste. 103 00:05:00,570 --> 00:05:05,470 E quale fu una delle motivazioni per l'introduzione di questa struttura dati? 104 00:05:05,470 --> 00:05:06,930 Sì? 105 00:05:06,930 --> 00:05:07,250 Che cos'è? 106 00:05:07,250 --> 00:05:08,080 >> AUDIENCE: Dimensione dinamica. 107 00:05:08,080 --> 00:05:09,040 >> DAVID MALAN: Dimensione dinamica. 108 00:05:09,040 --> 00:05:11,890 Quindi, mentre in array, si deve conoscerne la dimensione in anticipo quando 109 00:05:11,890 --> 00:05:12,740 si alloca esso. 110 00:05:12,740 --> 00:05:14,380 Nella lista collegata, non è necessario devono sapere che. 111 00:05:14,380 --> 00:05:17,610 Si può solo malloc, o più in generale, stanziare un ulteriore 112 00:05:17,610 --> 00:05:20,720 nodo, per così dire, ogni volta che si desidera inserire più dati. 113 00:05:20,720 --> 00:05:22,670 E il nodo non ha alcun significato predeterminato. 114 00:05:22,670 --> 00:05:25,580 E 'solo un termine generico che descrive una sorta di contenitore che siamo 115 00:05:25,580 --> 00:05:29,610 utilizzando nella nostra struttura dati per memorizzare qualche elemento di interesse, che in questo 116 00:05:29,610 --> 00:05:31,750 caso capita di essere numeri interi. 117 00:05:31,750 --> 00:05:33,160 >> Ma c'è sempre un compromesso. 118 00:05:33,160 --> 00:05:38,070 Così otteniamo dimensioni dinamiche dei dati struttura, ma che prezzo paghiamo? 119 00:05:38,070 --> 00:05:40,040 Qual è il lato negativo di liste collegate? 120 00:05:40,040 --> 00:05:41,006 Sì? 121 00:05:41,006 --> 00:05:41,980 >> AUDIENCE: richiede più memoria. 122 00:05:41,980 --> 00:05:44,240 >> DAVID MALAN: Si richiede di più memoria, come esattamente? 123 00:05:44,240 --> 00:05:46,440 >> AUDIENCE: [incomprensibile]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID MALAN: Esattamente. 125 00:05:47,050 --> 00:05:50,460 Così ora abbiamo puntatori riprendendo memoria aggiuntiva che abbiamo precedentemente 126 00:05:50,460 --> 00:05:53,040 non aveva bisogno, perché il vantaggio di un array, naturalmente, è che 127 00:05:53,040 --> 00:05:54,860 tutto è contiguo, indietro to back to back, che 128 00:05:54,860 --> 00:05:56,380 ti dà accesso casuale. 129 00:05:56,380 --> 00:06:00,710 Perché semplicemente utilizzando parentesi quadra notazione, o più tecnicamente puntatore 130 00:06:00,710 --> 00:06:03,580 aritmetica, molto semplice addizione, si può accedere a qualsiasi 131 00:06:03,580 --> 00:06:05,700 elementi in tempo costante. 132 00:06:05,700 --> 00:06:08,975 E in effetti, questo è tipo di accennare a un altro prezzo che stiamo pagando con un 133 00:06:08,975 --> 00:06:09,760 lista collegata. 134 00:06:09,760 --> 00:06:13,890 >> Cosa succede al tempo di esecuzione di qualcosa di simile a Search, se voglio 135 00:06:13,890 --> 00:06:17,270 trovare qualche valore e dentro di una lista collegata? 136 00:06:17,270 --> 00:06:20,290 Che cosa fa il mio tempo di esecuzione diventi? 137 00:06:20,290 --> 00:06:21,560 Big O di n. 138 00:06:21,560 --> 00:06:24,060 Se si è ordinato al? 139 00:06:24,060 --> 00:06:25,440 Che cosa succede se la struttura dei dati è ordinato? 140 00:06:25,440 --> 00:06:28,640 Posso fare meglio di grande O di n per la ricerca? 141 00:06:28,640 --> 00:06:31,700 No, perché nel caso peggiore potrebbe benissimo essere ordinati, ma il numero 142 00:06:31,700 --> 00:06:32,950 stai cercando potrebbe essere grande. 143 00:06:32,950 --> 00:06:35,370 Potrebbe essere il numero 100, che potrebbe accadere di essere tutti 144 00:06:35,370 --> 00:06:36,410 il modo alla fine. 145 00:06:36,410 --> 00:06:39,950 E perché si può accedere solo un linked elenco in questa applicazione da parte 146 00:06:39,950 --> 00:06:42,690 via del suo primo nodo, sei ancora un po 'di fortuna. 147 00:06:42,690 --> 00:06:47,450 Devi attraversare il tutto dal primo all'ultimo, al fine di trovare 148 00:06:47,450 --> 00:06:49,150 che grande valore come 100. 149 00:06:49,150 --> 00:06:51,350 O per determinare se è nemmeno lì. 150 00:06:51,350 --> 00:06:55,960 >> Quindi non possiamo fare quello che l'algoritmo in un dato struttura che assomiglia a questo? 151 00:06:55,960 --> 00:06:59,460 Non possiamo fare ricerca binaria, perché ricerca binaria richieste che abbiamo avuto 152 00:06:59,460 --> 00:07:00,740 accesso casuale. 153 00:07:00,740 --> 00:07:04,500 Potremmo saltare da un luogo all'altro posizione senza dover seguire 154 00:07:04,500 --> 00:07:07,080 queste briciole di pane in forma di tutti questi puntatori. 155 00:07:07,080 --> 00:07:08,300 >> Ora, come abbiamo fatto a implementare questo? 156 00:07:08,300 --> 00:07:12,830 Beh, se andiamo alla schermata qui, se siamo in grado di implementare di nuovo rapidamente questi dati 157 00:07:12,830 --> 00:07:13,440 struttura - 158 00:07:13,440 --> 00:07:15,670 la mia scrittura non è tutto ciò che grande qui, ma ci proveremo. 159 00:07:15,670 --> 00:07:22,030 Così typedef struct, e cosa ho consiglia di chiamare questa cosa qui? 160 00:07:22,030 --> 00:07:22,960 Nodo. 161 00:07:22,960 --> 00:07:24,580 Così prendo iniziare. 162 00:07:24,580 --> 00:07:27,860 E ora, che cosa deve essere all'interno di la struttura dati per tale singolarmente 163 00:07:27,860 --> 00:07:28,430 lista collegata? 164 00:07:28,430 --> 00:07:29,950 Quanti campi? 165 00:07:29,950 --> 00:07:30,450 >> Quindi due. 166 00:07:30,450 --> 00:07:31,570 Uno è abbastanza facile. 167 00:07:31,570 --> 00:07:33,050 Quindi, int n. 168 00:07:33,050 --> 00:07:35,930 E potremmo chiamare n tutto ciò che vogliamo, ma dovrebbe essere un int se siamo 169 00:07:35,930 --> 00:07:37,660 l'attuazione di una lista collegata per int. 170 00:07:37,660 --> 00:07:41,920 E adesso cosa fa il secondo campo deve essere? 171 00:07:41,920 --> 00:07:43,460 Struct nodo *. 172 00:07:43,460 --> 00:07:50,570 Quindi se faccio struct nodo *, e poi ho può chiamare questo anche ciò che voglio, 173 00:07:50,570 --> 00:07:53,510 ma tanto per essere chiari chiamerò la prossima, come abbiamo fatto. 174 00:07:53,510 --> 00:07:55,270 E allora io chiudo parentesi graffe. 175 00:07:55,270 --> 00:08:00,700 >> E ora, come l'ultima volta, Ho messo nodo quaggiù. 176 00:08:00,700 --> 00:08:03,830 Ma se sto dichiarando questo è come un nodo, perché ho fastidio essere così 177 00:08:03,830 --> 00:08:07,320 verbose qui nel dichiarare struct nodo * prossimo, in contrapposizione 178 00:08:07,320 --> 00:08:09,210 al proprio nodo * prossimo? 179 00:08:09,210 --> 00:08:09,904 Sì? 180 00:08:09,904 --> 00:08:12,810 >> AUDIENCE: [incomprensibile]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID MALAN: Esattamente. 182 00:08:14,050 --> 00:08:14,530 Esattamente. 183 00:08:14,530 --> 00:08:18,320 Poiché C si prende davvero letteralmente e vede solo la definizione del nodo 184 00:08:18,320 --> 00:08:21,230 fin qui, non è possibile fare riferimento ad esso qui. 185 00:08:21,230 --> 00:08:24,760 Quindi abbiamo questa sorta di prelazione dichiarazione qui, che è certamente 186 00:08:24,760 --> 00:08:25,390 più prolisso. 187 00:08:25,390 --> 00:08:27,810 Struct nodo, che significa ora possiamo accedervi 188 00:08:27,810 --> 00:08:29,760 all'interno della struttura dati. 189 00:08:29,760 --> 00:08:33,370 >> E per inciso, perché questo è diventando un po 'più soggettivo ora, 190 00:08:33,370 --> 00:08:36,230 la stella può tecnicamente andare qui, si può andare qui, si può 191 00:08:36,230 --> 00:08:37,179 anche andare nel mezzo. 192 00:08:37,179 --> 00:08:39,890 Abbiamo adottato, nel Manuale per il corso, la convenzione di mettere 193 00:08:39,890 --> 00:08:42,299 la stella a destra accanto ai dati tipo, che in questo caso, 194 00:08:42,299 --> 00:08:43,460 sarebbe nodo struct. 195 00:08:43,460 --> 00:08:46,620 Ma realizzare in un sacco di libri di testo e riferimenti on-line, si potrebbe infatti 196 00:08:46,620 --> 00:08:48,450 vedere sull'altro lato. 197 00:08:48,450 --> 00:08:52,200 Ma proprio conto che entrambi saranno effettivamente lavora e si dovrebbe semplicemente essere 198 00:08:52,200 --> 00:08:52,970 coerente. 199 00:08:52,970 --> 00:08:53,580 >> D'accordo. 200 00:08:53,580 --> 00:08:55,630 In modo che è stata la nostra dichiarazione del nodo struct. 201 00:08:55,630 --> 00:08:59,430 Ma poi abbiamo iniziato a fare di più cose sofisticate. 202 00:08:59,430 --> 00:09:03,410 Per esempio, abbiamo deciso di introdurre qualcosa di simile a una tabella hash. 203 00:09:03,410 --> 00:09:08,160 Così qui è una tabella hash di dimensione n, indicizzato da 0 in alto a sinistra per n 204 00:09:08,160 --> 00:09:09,690 meno 1 in basso a sinistra. 205 00:09:09,690 --> 00:09:11,640 Questo potrebbe essere un hash tavolo per qualsiasi cosa. 206 00:09:11,640 --> 00:09:15,340 Ma che tipo di cose abbiamo parlato su come utilizzare una tabella hash per? 207 00:09:15,340 --> 00:09:18,370 Memorizzazione di che cosa? 208 00:09:18,370 --> 00:09:18,800 >> Nomi. 209 00:09:18,800 --> 00:09:20,870 Potremmo fare nomi come abbiamo fatto l'ultima volta. 210 00:09:20,870 --> 00:09:22,200 E davvero, è possibile memorizzare qualsiasi cosa. 211 00:09:22,200 --> 00:09:24,640 E vedremo di nuovo in PHP e JavaScript. 212 00:09:24,640 --> 00:09:28,550 Una tabella hash è una bella specie di Svizzera Coltellino che consente di memorizzare 213 00:09:28,550 --> 00:09:33,690 praticamente tutto ciò che si desidera all'interno di esso da chiavi con valori associare. 214 00:09:33,690 --> 00:09:34,770 Tasti con i valori. 215 00:09:34,770 --> 00:09:37,800 >> Ora, in questo caso semplice, il nostro chiavi sono solo numeri. 216 00:09:37,800 --> 00:09:40,380 Stiamo implementando un hash tavolo come un array. 217 00:09:40,380 --> 00:09:43,500 E così le chiavi sono 0, 1, 2, e così via. 218 00:09:43,500 --> 00:09:47,200 E così noi, come esseri umani, abbiamo deciso all'ultimo settimana che si sa che cosa, se siamo 219 00:09:47,200 --> 00:09:50,410 andando a memorizzare nomi, diciamo solo arbitrariamente, ma piuttosto ragionevolmente, 220 00:09:50,410 --> 00:09:54,680 supporre che Alice, un Un nome, sarà solo essere indicizzati in 0. 221 00:09:54,680 --> 00:09:58,030 E Bob, un nome di B, sarà indicizzato in 1, e così via. 222 00:09:58,030 --> 00:10:02,490 Così abbiamo avuto un mapping tra gli ingressi, quali sono le stringhe, e l'hash 223 00:10:02,490 --> 00:10:04,560 luoghi, che sono i numeri. 224 00:10:04,560 --> 00:10:07,740 >> Modo che il processo è generalmente noto come una funzione di hash, e si può veramente 225 00:10:07,740 --> 00:10:09,130 recepirlo nel codice. 226 00:10:09,130 --> 00:10:12,080 Se avessi voluto implementare una funzione di hash che fa esattamente quello che abbiamo 227 00:10:12,080 --> 00:10:17,070 appena descritta dall'ultima volta, potrei dichiarare una funzione che prende, come 228 00:10:17,070 --> 00:10:18,330 Ingresso per esempio - 229 00:10:18,330 --> 00:10:22,190 e facciamolo su questo schermata qui. 230 00:10:22,190 --> 00:10:26,180 Se volessi realizzare un hash funzione, mi potrebbe dire 231 00:10:26,180 --> 00:10:27,410 qualcosa di simile a questo. 232 00:10:27,410 --> 00:10:29,030 >> E 'intenzione di restituire un int. 233 00:10:29,030 --> 00:10:33,600 E 'intenzione di essere chiamato hash, ed è intenzione di accettare come argomento un 234 00:10:33,600 --> 00:10:38,920 stringa, o possiamo essere più proprio ora, e di 'char *, che chiameremo s. 235 00:10:38,920 --> 00:10:43,840 E poi tutta questa funzione ha a che fare, in ultima analisi, è restituire un int. 236 00:10:43,840 --> 00:10:45,990 Ora, come lo fa, che potrebbe non essere così chiara. 237 00:10:45,990 --> 00:10:49,510 Ho intenzione di implementare questo senza alcun forma di controllo degli errori al momento. 238 00:10:49,510 --> 00:10:55,740 Sto solo andando a dire alla cieca, ritorno tutto ciò che è a s staffa 0, meno, 239 00:10:55,740 --> 00:10:58,850 diciamo, capitale Un punto e virgola. 240 00:10:58,850 --> 00:10:59,960 >> Totalmente rotto. 241 00:10:59,960 --> 00:11:02,620 Non è perfetto, perché uno, quello che se s è nullo? 242 00:11:02,620 --> 00:11:04,000 Brutte cose stanno per accadere. 243 00:11:04,000 --> 00:11:07,940 Due, quello che se la prima lettera in questo nome non è una lettera maiuscola? 244 00:11:07,940 --> 00:11:09,860 Che non sta andando a girare bene neanche. 245 00:11:09,860 --> 00:11:11,970 Potrebbe essere una lettera minuscola o no una lettera a tutti. 246 00:11:11,970 --> 00:11:15,520 Così totalmente margini di miglioramento qui, ma questa è l'idea di base. 247 00:11:15,520 --> 00:11:19,010 >> Ciò che abbiamo descritto la settimana scorsa verbalmente come solo un processo di mappatura di Alice 248 00:11:19,010 --> 00:11:23,360 0 e Bob a 1 possono essere espressi certamente più formulaically come C 249 00:11:23,360 --> 00:11:24,320 funzionare qui. 250 00:11:24,320 --> 00:11:28,630 Chiamato di nuovo hash, prende una stringa come ingresso, e quindi in qualche modo fa qualcosa 251 00:11:28,630 --> 00:11:31,020 con tale ingresso per produrre un output. 252 00:11:31,020 --> 00:11:34,130 Non diversamente il nostro descrizione scatola nera che abbiamo fatto a lungo. 253 00:11:34,130 --> 00:11:36,550 Non so come questo potrebbe essere lavorando sotto la cappa. 254 00:11:36,550 --> 00:11:40,120 >> Per set problema 6, una delle sfide è per voi a decidere che cosa 255 00:11:40,120 --> 00:11:41,920 avrà la funzione di hash essere? 256 00:11:41,920 --> 00:11:45,760 Che cosa sta per essere all'interno di quello nero scatola, e presumibilmente, sarà un 257 00:11:45,760 --> 00:11:50,380 poco più interessante di questo, e decisamente più incline all'errore 258 00:11:50,380 --> 00:11:53,180 verifica di questo particolare attuazione. 259 00:11:53,180 --> 00:11:54,580 >> Ma possono sorgere problemi, giusto? 260 00:11:54,580 --> 00:11:57,760 Se abbiamo una struttura di dati come questo uno, quello che è uno dei problemi 261 00:11:57,760 --> 00:12:01,600 si può incorrere in corso del tempo, come si inserisce sempre più nomi nella 262 00:12:01,600 --> 00:12:02,880 tabella di hash? 263 00:12:02,880 --> 00:12:04,630 È possibile ottenere le collisioni, giusto? 264 00:12:04,630 --> 00:12:07,560 Che cosa succede se si dispone di Alice e Aronne, due persone i cui nomi successo 265 00:12:07,560 --> 00:12:08,190 iniziare con un? 266 00:12:08,190 --> 00:12:11,660 Che pone la domanda, in cui si mettere il secondo ad un nome? 267 00:12:11,660 --> 00:12:15,050 >> Beh, si potrebbe ingenuamente basta metterlo dove Bob appartiene, ma poi Bob è 268 00:12:15,050 --> 00:12:17,300 tipo di vite, se si tenta di inserire il suo nome accanto e 269 00:12:17,300 --> 00:12:18,240 non c'è spazio per lui. 270 00:12:18,240 --> 00:12:21,400 Così si potrebbe mettere Bob dove Charlie, e si può immaginare questo molto rapidamente 271 00:12:21,400 --> 00:12:23,020 devolvendo in un po 'di confusione. 272 00:12:23,020 --> 00:12:25,600 Qualcosa lineare, alla fine, in cui si basta cercare il tutto 273 00:12:25,600 --> 00:12:28,190 alla ricerca di Alice o Bob o Aaron o Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Così invece abbiamo proposto, invece di linearmente sondaggio per spazi aperti 275 00:12:33,230 --> 00:12:36,450 e plopping i nomi, ci siamo proposto un approccio più elaborato. 276 00:12:36,450 --> 00:12:41,740 Una tabella hash implementato ancora con un serie di indici, ma il tipo di dati di 277 00:12:41,740 --> 00:12:44,500 tali indici ora sono puntatori. 278 00:12:44,500 --> 00:12:47,360 Puntatori a che cosa? 279 00:12:47,360 --> 00:12:48,730 Puntatori a liste collegate. 280 00:12:48,730 --> 00:12:53,330 >> Perché ricordo che una lista concatenata è in realtà solo un puntatore a un nodo, e 281 00:12:53,330 --> 00:12:57,110 il nodo ha un campo vicino, e tale nodo ha un campo successivo, e così via. 282 00:12:57,110 --> 00:13:00,690 Così ora è possibile pensare a questa matrice su il lato sinistro di una tabella hash come 283 00:13:00,690 --> 00:13:01,820 portando a una lista collegata. 284 00:13:01,820 --> 00:13:07,000 Il vantaggio di cui è se si ottiene un collisione tra Alice e Aronne, 285 00:13:07,000 --> 00:13:09,300 cosa fare con il secondo tale persona? 286 00:13:09,300 --> 00:13:14,150 È lui solo collegare o lei al end, o anche l'inizio 287 00:13:14,150 --> 00:13:15,490 di quella lista collegata. 288 00:13:15,490 --> 00:13:17,340 >> E in realtà, diciamo solo tagliatella attraverso che solo per un secondo. 289 00:13:17,340 --> 00:13:18,640 Dove renderebbe più senso? 290 00:13:18,640 --> 00:13:22,060 Se inserisco Alice e lei finisce a la prima posizione, poi cerco di 291 00:13:22,060 --> 00:13:25,310 inserire il nome di Aaron, e non c'è ovviamente una collisione, devo mettere 292 00:13:25,310 --> 00:13:27,400 lui all'inizio della lista collegata? 293 00:13:27,400 --> 00:13:30,944 Che è in primo luogo che, o alla fine? 294 00:13:30,944 --> 00:13:31,440 >> AUDIENCE: [incomprensibile]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID MALAN: OK. 296 00:13:31,990 --> 00:13:32,490 Ho sentito all'inizio. 297 00:13:32,490 --> 00:13:33,903 Perché all'inizio? 298 00:13:33,903 --> 00:13:34,750 >> AUDIENCE: [incomprensibile]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID MALAN: OK. 300 00:13:34,940 --> 00:13:36,520 E 'alfabetico, in modo che è bello. 301 00:13:36,520 --> 00:13:37,330 Questo è un buon albergo. 302 00:13:37,330 --> 00:13:39,335 Mi farà risparmiare un po 'di tempo potenzialmente. 303 00:13:39,335 --> 00:13:43,290 Non mi permette di fare la ricerca binaria, ma io potrebbe almeno essere in grado di uscire 304 00:13:43,290 --> 00:13:47,340 di un ciclo se mi rendo conto, beh, io sono via passato erano Aaron sarebbe in questo 305 00:13:47,340 --> 00:13:48,310 ordinati lista collegata. 306 00:13:48,310 --> 00:13:50,360 Io non devo sprecare il mio tempo alla ricerca fino alla fine. 307 00:13:50,360 --> 00:13:51,530 Ecco, questo è ragionevole. 308 00:13:51,530 --> 00:13:54,710 Perché altrimenti si potrebbe desiderare di inserire il nome collisione al 309 00:13:54,710 --> 00:13:56,660 inizio della lista? 310 00:13:56,660 --> 00:13:57,397 Che cos'è? 311 00:13:57,397 --> 00:13:58,680 >> AUDIENCE: [incomprensibile]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID MALAN: Si potrebbe richiedere molto tempo per arrivare alla fine della lista. 313 00:14:00,820 --> 00:14:02,490 E infatti, più a lungo e più a lungo. 314 00:14:02,490 --> 00:14:04,920 Gli altri nomi che si inserisce Inizia con una, la più lunga che 315 00:14:04,920 --> 00:14:06,280 catena sta per arrivare. 316 00:14:06,280 --> 00:14:07,890 Quanto più a lungo che collegava lista sta per arrivare. 317 00:14:07,890 --> 00:14:09,420 Quindi sei davvero solo sprecare il vostro tempo. 318 00:14:09,420 --> 00:14:14,070 Forse è meglio mantenere tempo di inserzione costante, O grande di 1, 319 00:14:14,070 --> 00:14:18,470 da sempre mettendo il nome di collisione in l'inizio della lista collegata, 320 00:14:18,470 --> 00:14:21,230 e non preoccuparsi tanto sull'ordinamento. 321 00:14:21,230 --> 00:14:22,600 >> Qual è la migliore risposta? 322 00:14:22,600 --> 00:14:23,320 Non è chiaro. 323 00:14:23,320 --> 00:14:26,140 E 'sorta di dipende da ciò che il distribuzione è, ciò che il modello è 324 00:14:26,140 --> 00:14:27,850 dei nomi che si sta inserendo. 325 00:14:27,850 --> 00:14:29,430 Non è necessariamente una risposta ovvia. 326 00:14:29,430 --> 00:14:33,100 Ma qui per, ancora una volta, è un'opportunità disegno. 327 00:14:33,100 --> 00:14:37,220 >> Così abbiamo poi guardato questa cosa, che è davvero l'altra grande opportunità 328 00:14:37,220 --> 00:14:38,180 per p-set 6. 329 00:14:38,180 --> 00:14:41,770 E realizzare, se non l'hai già fatto, Immersioni Zamyla in entrambi questi, hash 330 00:14:41,770 --> 00:14:43,260 tavoli e cerca, più in dettaglio. 331 00:14:43,260 --> 00:14:45,630 E il video walkthrough è incorporato in p-set spec. 332 00:14:45,630 --> 00:14:46,590 Questo è stato un trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. E che cosa era interessante questo era un tempo di rotazione 334 00:14:51,670 --> 00:14:59,510 di ricerca di un nome, come Maxwell ultima volta, era grande O di che cosa? 335 00:14:59,510 --> 00:15:01,040 Che cos'è? 336 00:15:01,040 --> 00:15:01,920 >> PUBBLICO: Il numero di lettere. 337 00:15:01,920 --> 00:15:02,550 >> DAVID MALAN: numero di lettere. 338 00:15:02,550 --> 00:15:03,210 Ho sentito due cose. 339 00:15:03,210 --> 00:15:04,630 Numero di lettere e di tempo costante. 340 00:15:04,630 --> 00:15:05,540 Allora andiamo con quella prima. 341 00:15:05,540 --> 00:15:06,410 Il numero di lettere. 342 00:15:06,410 --> 00:15:10,195 Beh, questa struttura di dati, richiamo, è Come un albero, un albero genealogico, ciascuno dei 343 00:15:10,195 --> 00:15:12,860 i cui nodi sono costituiti da matrici. 344 00:15:12,860 --> 00:15:16,300 E questi array sono puntatori a altri tali nodi, o altri tali 345 00:15:16,300 --> 00:15:17,670 array nella struttura. 346 00:15:17,670 --> 00:15:22,890 >> Quindi se volessimo quindi determinare se Maxwell è qui, potrei andare 347 00:15:22,890 --> 00:15:26,890 alla prima matrice, al vertice di l'albero, la cosiddetta radice, cima 348 00:15:26,890 --> 00:15:30,521 trie, e quindi seguire il puntatore m, poi l'un puntatore, allora x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 E poi quando vedo qualche simbolo speciale, indicata qui come un triangolo. 351 00:15:34,910 --> 00:15:38,480 Nel codice vedrete Vi proponiamo di implementato come un bool, basta dire sì 352 00:15:38,480 --> 00:15:40,540 o no, una parola si ferma qui. 353 00:15:40,540 --> 00:15:45,270 >> Bene, una volta che siamo andati a M-A-X-W-E-L-L, si sente come sette, forse 354 00:15:45,270 --> 00:15:48,910 otto se andiamo un passato, otto procedura per trovare Maxwell. 355 00:15:48,910 --> 00:15:53,050 O chiamiamolo K. non ricordare scorso tempo, ho sostenuto che se c'è 356 00:15:53,050 --> 00:15:57,540 realisticamente una lunghezza massima su un parola, come i personaggi 40-qualche-dispari, un 357 00:15:57,540 --> 00:16:00,810 massima lunghezza implica un valore costante. 358 00:16:00,810 --> 00:16:05,770 Quindi, in realtà, sì, è tecnicamente grande O di 8 o 7, o davvero grande O di K. Ma 359 00:16:05,770 --> 00:16:09,420 se c'è un limite finito su ciò K potrebbe essere, è una costante. 360 00:16:09,420 --> 00:16:12,080 E così è grande O di 1 a Alla fine della giornata. 361 00:16:12,080 --> 00:16:13,040 >> Non nel mondo reale. 362 00:16:13,040 --> 00:16:15,960 Non quando in realtà inizia a guardare il vostro orologio da corsa del vostro programma. 363 00:16:15,960 --> 00:16:20,690 E 'assolutamente intenzione di essere un po' lento di veramente costante 364 00:16:20,690 --> 00:16:21,840 tempo con un solo passaggio. 365 00:16:21,840 --> 00:16:25,540 Sta andando essere sette o otto gradini, ma questo è molto, molto meglio 366 00:16:25,540 --> 00:16:30,080 di un algoritmo simile grande O di n che dipende dalle dimensioni di ciò che è nel 367 00:16:30,080 --> 00:16:31,220 struttura dati. 368 00:16:31,220 --> 00:16:34,970 >> Notate la testa qui è che possiamo inserire un milione di nomi in questa 369 00:16:34,970 --> 00:16:38,170 struttura dei dati, ma quanti più passaggi sta andando a prendere noi per trovare 370 00:16:38,170 --> 00:16:40,480 Maxwell in quel caso? 371 00:16:40,480 --> 00:16:40,780 Nessuna. 372 00:16:40,780 --> 00:16:41,820 Lui è inalterato. 373 00:16:41,820 --> 00:16:45,480 E fino ad oggi, non credo che abbiamo visto un esempio di una struttura di dati o un 374 00:16:45,480 --> 00:16:48,560 algoritmo che è stato completamente influenzato da esterno 375 00:16:48,560 --> 00:16:50,040 comportamenti del genere. 376 00:16:50,040 --> 00:16:51,160 Ma questo non può essere sorprendente. 377 00:16:51,160 --> 00:16:52,900 Questo non può essere l'unica soluzione per il p-set 378 00:16:52,900 --> 00:16:53,570 >> E non è. 379 00:16:53,570 --> 00:16:55,980 Questo non è necessariamente i dati struttura che dovrebbe gravitare verso, 380 00:16:55,980 --> 00:16:58,220 perché come tabelle hash, compromesso. 381 00:16:58,220 --> 00:17:00,500 Qual è il prezzo che si paga qui? 382 00:17:00,500 --> 00:17:00,940 Memoria. 383 00:17:00,940 --> 00:17:02,890 Voglio dire, questo è un atroce quantità di memoria. 384 00:17:02,890 --> 00:17:05,569 E non riesco a vedere qui perché l'autore di questa immagine 385 00:17:05,569 --> 00:17:09,420 ovviamente troncata tutti gli array, e non stiamo vedendo un sacco di A e 386 00:17:09,420 --> 00:17:12,700 B e C e Q e Y del e le Z in questi array. 387 00:17:12,700 --> 00:17:13,630 Ma sono lì. 388 00:17:13,630 --> 00:17:17,660 >> Ciascuno di questi nodi è un'intera matrice di circa 26 o più byte, ciascuno dei 389 00:17:17,660 --> 00:17:19,170 che rappresenta una lettera. 390 00:17:19,170 --> 00:17:22,920 27 nel nostro caso, in modo da poter sostenere apostrofi del problema proposto. 391 00:17:22,920 --> 00:17:27,030 Quindi, questa struttura dati è davvero, molto denso e largo. 392 00:17:27,030 --> 00:17:30,880 E che da solo potrebbe finire per rallentare le cose, o almeno costare un 393 00:17:30,880 --> 00:17:32,240 molto più spazio. 394 00:17:32,240 --> 00:17:34,020 Ma ancora una volta, possiamo trarre comparazioni qui. 395 00:17:34,020 --> 00:17:39,190 >> Ricordiamo un po 'indietro, abbiamo ottenuto molto più emozionante tempo di esecuzione in ordinamento 396 00:17:39,190 --> 00:17:42,880 quando usiamo merge sort, ma il prezzo abbiamo pagato per ottenere n log n per merge 397 00:17:42,880 --> 00:17:46,930 sorta richiesto che spendiamo più che cosa risorsa? 398 00:17:46,930 --> 00:17:47,690 Più spazio. 399 00:17:47,690 --> 00:17:50,530 Avevamo bisogno di una serie secondaria di copiare la gente in, proprio come 400 00:17:50,530 --> 00:17:51,620 abbiamo fatto qui sul palco. 401 00:17:51,620 --> 00:17:55,880 Quindi, di nuovo, senza chiari vincitori, ma proprio disegno soggettivo 402 00:17:55,880 --> 00:17:57,710 decisioni da prendere. 403 00:17:57,710 --> 00:17:58,060 >> D'accordo. 404 00:17:58,060 --> 00:17:59,130 Così come su questo? 405 00:17:59,130 --> 00:18:02,050 Chiunque riconosce che D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Così tre di noi fanno. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Quindi questo è per il pranzo di Mather. 410 00:18:05,070 --> 00:18:09,650 Scommetto tutte le sale da pranzo hanno pile di vassoi come questo. 411 00:18:09,650 --> 00:18:11,950 E questo è in realtà rappresentativo di qualcosa che abbiamo 412 00:18:11,950 --> 00:18:13,050 ovviamente visto già. 413 00:18:13,050 --> 00:18:14,850 Lo abbiamo chiamato letteralmente una pila. 414 00:18:14,850 --> 00:18:18,970 E la pila, in termini di vostro memoria del computer, è dove i dati vanno 415 00:18:18,970 --> 00:18:20,460 mentre le funzioni sono chiamati. 416 00:18:20,460 --> 00:18:23,410 >> Per esempio, che tipo di cose vanno sulla pila rispetto alla 417 00:18:23,410 --> 00:18:27,420 layout di memoria che abbiamo discusso nelle ultime settimane? 418 00:18:27,420 --> 00:18:28,736 Che cos'è? 419 00:18:28,736 --> 00:18:29,670 >> AUDIENCE: chiamate a funzioni. 420 00:18:29,670 --> 00:18:30,260 >> DAVID MALAN: Mi dispiace. 421 00:18:30,260 --> 00:18:31,210 >> AUDIENCE: chiamate a funzioni. 422 00:18:31,210 --> 00:18:33,590 >> DAVID MALAN: Le chiamate a funzioni, ma In particolare, ciò che è dentro di ognuno di 423 00:18:33,590 --> 00:18:35,340 quei fotogrammi? 424 00:18:35,340 --> 00:18:37,220 Che tipo di cose? 425 00:18:37,220 --> 00:18:37,460 Già. 426 00:18:37,460 --> 00:18:38,500 Quindi, le variabili locali. 427 00:18:38,500 --> 00:18:43,080 Ogni volta che avevamo bisogno di un po 'di memoria locale, come un argomento, o INT o int 428 00:18:43,080 --> 00:18:45,940 temp, o qualunque sia il locale variabile è, siamo stati 429 00:18:45,940 --> 00:18:47,210 mettendo che in pila. 430 00:18:47,210 --> 00:18:49,610 E noi lo chiamiamo una pila perché di quell'idea stratificazione. 431 00:18:49,610 --> 00:18:52,940 Solo tipo di match up con la realtà, il concetto della stessa. 432 00:18:52,940 --> 00:18:56,650 >> Ma si scopre che una pila può anche essere visto come una struttura dati, un 433 00:18:56,650 --> 00:19:00,110 alternativa ad un array, in alternativa ad un elenco collegato. 434 00:19:00,110 --> 00:19:02,770 Qualcosa di concettualmente più interessante che può ancora essere 435 00:19:02,770 --> 00:19:06,030 implementato utilizzando uno di questi le cose, ma è un diverso tipo di 436 00:19:06,030 --> 00:19:09,140 struttura dati di supporto, in realtà, solo due operazioni. 437 00:19:09,140 --> 00:19:11,000 Ma si può aggiungere su amatore caratteristiche di questi. 438 00:19:11,000 --> 00:19:12,180 Ma queste sono le basi - 439 00:19:12,180 --> 00:19:13,510 inserire ed estrarre. 440 00:19:13,510 --> 00:19:19,240 >> E l'idea con uno stack è che se io sono qui, con o senza Annenberg 441 00:19:19,240 --> 00:19:22,880 sapendo, un vassoio della porta accanto con il numero 9 su esso. 442 00:19:22,880 --> 00:19:23,870 Quindi, solo un int. 443 00:19:23,870 --> 00:19:26,990 E voglio spingere questo sui dati struttura, che attualmente è vuoto. 444 00:19:26,990 --> 00:19:28,790 Considerate questo il fondo della pila. 445 00:19:28,790 --> 00:19:33,150 Vorrei spingere questo numero 9 sulla Catasta, e ora è proprio lì. 446 00:19:33,150 --> 00:19:36,040 >> Ma la cosa interessante di una pila è che se ora voglio spingere 447 00:19:36,040 --> 00:19:40,210 qualche altro valore, come il 17, e mi spingo presente nello stack, ho intenzione di fare 448 00:19:40,210 --> 00:19:43,290 l'unica cosa intuitiva, sto solo andando per dirla proprio dove noi umani 449 00:19:43,290 --> 00:19:45,180 sarebbe propenso a metterlo, in cima. 450 00:19:45,180 --> 00:19:48,850 Ma ciò che è interessante ora è, come faccio ad avere alle 9? 451 00:19:48,850 --> 00:19:50,670 Sai, io non senza qualche sforzo. 452 00:19:50,670 --> 00:19:54,070 >> Quindi cosa c'è di interessante uno stack è che dal disegno, 453 00:19:54,070 --> 00:19:56,330 si tratta di una struttura dati LIFO. 454 00:19:56,330 --> 00:19:59,680 Modo stupido di descrivere last in, first out. 455 00:19:59,680 --> 00:20:03,280 Così l'ultimo numero in in questo momento era 17. 456 00:20:03,280 --> 00:20:07,540 Quindi, se voglio qualcosa di pop off della pila, può essere solo 17. 457 00:20:07,540 --> 00:20:11,890 Quindi c'è un ordine obbligatorio di operazioni qui, dove l'ultimo elemento 458 00:20:11,890 --> 00:20:14,260 in deve essere il primo ad uscire. 459 00:20:14,260 --> 00:20:16,440 Da qui l'acronimo, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Allora, perché questo potrebbe essere utile? 461 00:20:19,160 --> 00:20:22,690 Sono i loro contesti in cui faresti vuole una struttura dati come questo? 462 00:20:22,690 --> 00:20:24,810 Beh, è ​​sicuramente stato utile all'interno di un computer. 463 00:20:24,810 --> 00:20:29,050 Sistemi operativi in ​​modo da utilizzare in modo chiaro questo tipo di struttura dati per le pile. 464 00:20:29,050 --> 00:20:32,800 Vedremo anche la stessa idea quando si tratta di pagine web. 465 00:20:32,800 --> 00:20:35,890 Così questa settimana e la prossima settimana e oltre, e come si inizia l'implementazione web 466 00:20:35,890 --> 00:20:39,490 pagine in un linguaggio chiamato HTML, è possibile effettivamente utilizzare una struttura dati simile 467 00:20:39,490 --> 00:20:42,690 questo per determinare se la pagina è formattato correttamente. 468 00:20:42,690 --> 00:20:47,170 Perché vedremo tutte le pagine web seguono una sorta di gerarchia, una rientranza 469 00:20:47,170 --> 00:20:52,030 che, al termine della giornata, essere un struttura ad albero sotto la cappa. 470 00:20:52,030 --> 00:20:53,620 Quindi, più che in appena un po '. 471 00:20:53,620 --> 00:20:56,560 >> Ma per ora, cerchiamo di proporre un momento, come potremmo fare per 472 00:20:56,560 --> 00:20:58,830 rappresentando ciò che una pila è? 473 00:20:58,830 --> 00:21:03,370 Lasciatemi propongo implementiamo una pila con codice come questo. 474 00:21:03,370 --> 00:21:07,990 Così una pila sta per avere all'interno di esso due cose, un array, chiamati vassoi, 475 00:21:07,990 --> 00:21:09,510 tanto per essere coerente con la demo. 476 00:21:09,510 --> 00:21:12,660 E ciascuna delle voci che la matrice sta per essere un tipo int. 477 00:21:12,660 --> 00:21:14,740 E la capacità è probabilmente quello che? 478 00:21:14,740 --> 00:21:18,796 Perché io non ho scritto la definizione completa qui. 479 00:21:18,796 --> 00:21:21,535 >> E 'probabilmente il massimo dimensione della matrice. 480 00:21:21,535 --> 00:21:25,150 E probabilmente è dichiarato come un forte definire all'inizio del file, alcuni 481 00:21:25,150 --> 00:21:28,450 sorta di costante implicita la mera capitalizzazione. 482 00:21:28,450 --> 00:21:32,250 Così da qualche capacità è definita come la dimensione massima possibile. 483 00:21:32,250 --> 00:21:35,590 Nel frattempo, all'interno della struttura dei dati noto come stack ci sarà 484 00:21:35,590 --> 00:21:38,630 essere un numero intero appena conosciuta semplicemente come dimensione. 485 00:21:38,630 --> 00:21:43,400 >> Quindi, se dovessi rappresentare questa società pittoricamente, supponiamo che questo 486 00:21:43,400 --> 00:21:48,070 tutta la scatola nera rappresenta il mio stack. 487 00:21:48,070 --> 00:21:50,070 All'interno di esso è due variabili. 488 00:21:50,070 --> 00:21:54,780 Quindi ho intenzione di disegnare il primo come dimensione. 489 00:21:54,780 --> 00:21:57,420 E il secondo vado a disegnare come un array. 490 00:21:57,420 --> 00:22:01,060 >> Ma solo per mantenere le cose ordinate, normalmente vorrei richiamare un array come 491 00:22:01,060 --> 00:22:04,910 questo, ma è una specie di bella se abbiniamo la realtà, o 492 00:22:04,910 --> 00:22:06,230 corrispondere al modello mentale. 493 00:22:06,230 --> 00:22:12,880 Così mi permetta invece disegnare la matrice verticalmente, che è proprio, di nuovo, 494 00:22:12,880 --> 00:22:13,840 interpretazione dell'artista. 495 00:22:13,840 --> 00:22:16,610 Non importa quello che è sotto il cofano. 496 00:22:16,610 --> 00:22:20,350 E diremo che, per impostazione predefinita, capacità sta per essere tre. 497 00:22:20,350 --> 00:22:23,480 Quindi questo sarà posizione 0, questo sarà location 1, questa 498 00:22:23,480 --> 00:22:25,740 sarà in posizione 2. 499 00:22:25,740 --> 00:22:29,330 >> Se io corrompere con una palla di stress, sarebbe qualcuno piace venire ed eseguire il 500 00:22:29,330 --> 00:22:30,870 bordo qui solo per un momento? 501 00:22:30,870 --> 00:22:31,960 OK, ha visto prima la tua mano. 502 00:22:31,960 --> 00:22:33,950 Andiamo su. 503 00:22:33,950 --> 00:22:36,500 D'accordo. 504 00:22:36,500 --> 00:22:38,760 Quindi credo che sia Steven. 505 00:22:38,760 --> 00:22:40,035 Andiamo su. 506 00:22:40,035 --> 00:22:40,770 D'accordo. 507 00:22:40,770 --> 00:22:46,760 >> Ma supponiamo ora ci Rewind a quella iniziale stato del mondo in cui mi 508 00:22:46,760 --> 00:22:52,180 hanno appena dichiarato una pila, ed è andando ad essere di capacità tre. 509 00:22:52,180 --> 00:22:54,470 Ma taglia non è ancora stata determinata. 510 00:22:54,470 --> 00:22:56,100 Vassoi non è ancora stata determinata. 511 00:22:56,100 --> 00:22:57,300 Così un paio di domande prima. 512 00:22:57,300 --> 00:23:01,310 E permettetemi di darvi microfono in modo da poter partecipare più attivamente a questo. 513 00:23:01,310 --> 00:23:05,190 >> Quindi, ciò che è dentro di dimensioni in questo momento nel tempo se tutto quello che ho fatto è 514 00:23:05,190 --> 00:23:09,340 dichiarato una pila con una riga di codice? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Non molto. 516 00:23:10,100 --> 00:23:12,080 >> DAVID MALAN: OK, non molto. 517 00:23:12,080 --> 00:23:14,410 Sappiamo che cosa c'è dentro di dimensioni, facciamo a sapere cosa c'è dentro 518 00:23:14,410 --> 00:23:16,330 di questa matrice qui? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: codice Proprio casuale, giusto? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID MALAN: Sì, ho intenzione di chiamarlo codice, ma casuale - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Le cose. 523 00:23:23,820 --> 00:23:28,290 >> DAVID MALAN: Cose come casuale 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bit. 525 00:23:28,870 --> 00:23:29,530 >> DAVID MALAN: Bit, giusto? 526 00:23:29,530 --> 00:23:31,190 Quindi i valori di immondizia, giusto? 527 00:23:31,190 --> 00:23:33,470 Così permutazioni di 0 e di 1. 528 00:23:33,470 --> 00:23:35,920 Resti di usi precedenti di questa memoria. 529 00:23:35,920 --> 00:23:38,150 E noi non sappiamo veramente quali sono i valori stiamo, quindi abbiamo in genere li disegniamo 530 00:23:38,150 --> 00:23:38,930 come punti interrogativi. 531 00:23:38,930 --> 00:23:41,990 >> Quindi la prima cosa che siamo presumibilmente intenzione di voler fare qui - 532 00:23:41,990 --> 00:23:46,630 e lasciatemi fare questo campo all'interno di là di un nome - vassoi. 533 00:23:46,630 --> 00:23:49,540 Cosa dovremmo presumibilmente inizializzare dimensioni per se vogliamo 534 00:23:49,540 --> 00:23:51,040 iniziare a utilizzare questo stack? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Tray è sub 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID MALAN: Quindi, OK. 537 00:23:53,910 --> 00:23:56,710 Per essere chiari, la capacità viene dichiarato altrove come tre. 538 00:23:56,710 --> 00:23:58,570 Ed è quello che ho usato per allocare l'array. 539 00:23:58,570 --> 00:24:03,535 Dimensione sta per fare riferimento a quanti vassoi sono attualmente in pila. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID MALAN: Quindi dovrebbe essere pari a zero. 542 00:24:04,460 --> 00:24:07,760 Quindi, andare avanti, e con un dito, disegnare uno zero nel formato. 543 00:24:07,760 --> 00:24:08,440 D'accordo. 544 00:24:08,440 --> 00:24:10,920 Così ora, quello che c'è dentro di questa qui, non lo sappiamo. 545 00:24:10,920 --> 00:24:12,160 Questi sono in realtà solo i valori della spazzatura. 546 00:24:12,160 --> 00:24:14,800 Così potremmo disegnare punti interrogativi, ma cerchiamo di mantenere la tavola pulita per ora 547 00:24:14,800 --> 00:24:16,300 perché non importa cosa c'è. 548 00:24:16,300 --> 00:24:19,130 Non abbiamo bisogno di inizializzare l'array a nulla, perché se sappiamo che 549 00:24:19,130 --> 00:24:23,100 la dimensione dello stack è zero, bene, abbiamo non dovrebbe essere guardando qualcosa nel 550 00:24:23,100 --> 00:24:25,590 questa matrice in ogni caso a questo punto nel tempo. 551 00:24:25,590 --> 00:24:29,970 >> Così ora immagino che premo il numero 9 in cima alla pila. 552 00:24:29,970 --> 00:24:33,750 Come dovremmo aggiornare la struttura dei dati all'interno di questa scatola nera? 553 00:24:33,750 --> 00:24:35,540 Quali valori bisogno di cambiare? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Within - 555 00:24:36,200 --> 00:24:37,400 le dimensioni? 556 00:24:37,400 --> 00:24:37,650 >> DAVID MALAN: OK. 557 00:24:37,650 --> 00:24:38,770 Dimensione dovrebbe diventare cosa? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Dimensione sarebbe uno. 559 00:24:39,580 --> 00:24:39,870 >> DAVID MALAN: OK. 560 00:24:39,870 --> 00:24:41,110 Così dimensione dovrebbe diventarlo. 561 00:24:41,110 --> 00:24:42,540 Così si può fare questo in un paio di modi. 562 00:24:42,540 --> 00:24:46,920 Permettetemi di fare, ora il tuo dito è una gomma. 563 00:24:46,920 --> 00:24:47,260 D'accordo. 564 00:24:47,260 --> 00:24:49,960 Quindi ora il dito è un pennello. 565 00:24:49,960 --> 00:24:50,330 D'accordo. 566 00:24:50,330 --> 00:24:52,820 E ora che altro deve cambiare, ovviamente, nella struttura dati? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Stiamo andando da basso fino a 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID MALAN: 9. 569 00:24:57,760 --> 00:24:58,420 OK, Good. 570 00:24:58,420 --> 00:25:01,550 Quindi ancora non importa ciò che è in posizione uno o due perché sono 571 00:25:01,550 --> 00:25:04,520 valori della spazzatura, ma non dovrebbero preoccuparsi guardando lì perché la dimensione è 572 00:25:04,520 --> 00:25:07,540 che ci dice che solo il primo elemento in realtà è legittima. 573 00:25:07,540 --> 00:25:10,400 Così ora mi spingo 17 sulla lista. 574 00:25:10,400 --> 00:25:11,830 Che cosa succede a questa immagine? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Così dimensioni sta per andare in due. 576 00:25:14,720 --> 00:25:15,300 >> DAVID MALAN: OK. 577 00:25:15,300 --> 00:25:16,070 Sei gomma - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Sei una gomma. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID MALAN: Sei un pennello. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID MALAN: OK. 584 00:25:20,920 --> 00:25:21,600 E che altro? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: E poi - 586 00:25:22,600 --> 00:25:22,915 >> DAVID MALAN: abbiamo spinto 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Attacchiamo 17 sulla parte superiore, in modo - 588 00:25:24,760 --> 00:25:25,710 >> DAVID MALAN: OK, bene. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - cadere giù. 590 00:25:27,040 --> 00:25:27,530 >> DAVID MALAN: Va bene. 591 00:25:27,530 --> 00:25:27,940 E 'sempre facile. 592 00:25:27,940 --> 00:25:29,300 Non ho intenzione di aiutarvi a questo momento. 593 00:25:29,300 --> 00:25:30,510 Spingere 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Fatto. 595 00:25:31,720 --> 00:25:34,870 Diventare una gomma. 596 00:25:34,870 --> 00:25:37,340 Sto diventando un pennello. 597 00:25:37,340 --> 00:25:39,340 E poi sto mettendo 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID MALAN: 22. 599 00:25:40,100 --> 00:25:40,620 Eccellente. 600 00:25:40,620 --> 00:25:41,380 Quindi, ancora una volta. 601 00:25:41,380 --> 00:25:44,280 Ora sto andando a spingere sulla pila 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh Gosh. 604 00:25:50,278 --> 00:25:52,520 Davvero mi ha colto alla sprovvista. 605 00:25:52,520 --> 00:25:53,703 >> DAVID MALAN: Non l'hai fatto vedere il prossimo? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Non ho visto questa venuta. 607 00:25:55,930 --> 00:25:58,756 Potremmo capacità di ri-iniziale? 608 00:25:58,756 --> 00:25:59,790 >> DAVID MALAN: Questa è una buona domanda. 609 00:25:59,790 --> 00:26:02,360 Così abbiamo sorta di dipinto noi stessi in un angolo qui. 610 00:26:02,360 --> 00:26:06,740 Non c'è davvero nulla di buono per Steven perché abbiamo assegnato questo array 611 00:26:06,740 --> 00:26:09,130 staticamente, per così dire, all'interno della struttura dati. 612 00:26:09,130 --> 00:26:12,170 E abbiamo essenzialmente rigido codificato rendere della dimensione tre. 613 00:26:12,170 --> 00:26:14,170 Quindi non possiamo davvero riallocare esso. 614 00:26:14,170 --> 00:26:20,020 >> Potremmo, se siamo tornati, abbiamo ridefiniti i vassoi di essere un puntatore che 615 00:26:20,020 --> 00:26:22,300 Abbiamo quindi utilizzare malloc alla memoria a mano a. 616 00:26:22,300 --> 00:26:25,050 Perché se abbiamo ottenuto la memoria da il mucchio tramite malloc, abbiamo 617 00:26:25,050 --> 00:26:26,430 potrebbe poi liberarlo. 618 00:26:26,430 --> 00:26:29,630 Ma prima di liberarla, abbiamo potuto riallocare un pezzo più grande di memoria, 619 00:26:29,630 --> 00:26:31,330 aggiornare il puntatore, e così via. 620 00:26:31,330 --> 00:26:33,500 Ma per ora, questo è davvero Il meglio che possiamo fare. 621 00:26:33,500 --> 00:26:36,360 Spingere e pop sono presumibilmente andando di avere a segnalare qualche errore. 622 00:26:36,360 --> 00:26:40,270 >> Così, per esempio, la nostra implementazione di spinta potrebbe restituire un bool che 623 00:26:40,270 --> 00:26:42,390 precedentemente restituito vero, vero, vero. 624 00:26:42,390 --> 00:26:48,390 Ma la quarta volta, sta andando ad avere per restituire false, per esempio. 625 00:26:48,390 --> 00:26:48,540 D'accordo. 626 00:26:48,540 --> 00:26:49,540 Molto ben fatto. 627 00:26:49,540 --> 00:26:50,060 Congratulazioni. 628 00:26:50,060 --> 00:26:52,160 Ti sei guadagnato la tua palla antistress oggi. 629 00:26:52,160 --> 00:26:53,110 >> [Applausi] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Grazie. 631 00:26:54,382 --> 00:26:55,680 >> DAVID MALAN: Grazie. 632 00:26:55,680 --> 00:26:59,740 OK, quindi questo sembra essere non molto di un passo in avanti, giusto? 633 00:26:59,740 --> 00:27:01,410 Abbiamo descritto questa struttura dati. 634 00:27:01,410 --> 00:27:02,320 E 'stato interessante, no? 635 00:27:02,320 --> 00:27:03,200 Sistemi operativi piace. 636 00:27:03,200 --> 00:27:06,360 A quanto pare il web può fare uso di questa, e altre applicazioni ancora. 637 00:27:06,360 --> 00:27:10,870 Ma che stupida limitazione che siamo back to sorta di settimana due limiti 638 00:27:10,870 --> 00:27:12,880 dove abbiamo fissato array dimensioni. 639 00:27:12,880 --> 00:27:15,010 >> Quindi, ci sono infatti un paio di modi potremmo risolvere questo. 640 00:27:15,010 --> 00:27:18,750 Potremmo allocare dinamicamente la matrice, non da codificare come ho 641 00:27:18,750 --> 00:27:22,600 fatto qui, ma invece ri-dichiarando questo, tanto per essere chiari, come 642 00:27:22,600 --> 00:27:23,830 qualcosa di simile a questo. 643 00:27:23,830 --> 00:27:29,040 Int * vassoi, non decidere su ancora una capacità. 644 00:27:29,040 --> 00:27:35,460 Ma quando dichiaro la pila altrove nel mio codice, ho potuto quindi chiamare malloc, 645 00:27:35,460 --> 00:27:38,250 ottenere l'indirizzo di un pezzo di memoria, e potrei assegnare 646 00:27:38,250 --> 00:27:39,980 che l'indirizzo di vassoi. 647 00:27:39,980 --> 00:27:43,340 >> E poi, perché è solo un pezzo di memoria, ho potuto continuare a utilizzare piazza 648 00:27:43,340 --> 00:27:45,450 notazione parentesi nel solito modo. 649 00:27:45,450 --> 00:27:49,020 Perché ancora una volta, c'è una sorta di presente equivalente funzionale di array e 650 00:27:49,020 --> 00:27:50,820 blocchi di memoria che vengono di ritorno da malloc. 651 00:27:50,820 --> 00:27:53,090 Possiamo trattare uno come l'altra utilizzando l'aritmetica dei puntatori o 652 00:27:53,090 --> 00:27:54,440 piazza notazione staffa. 653 00:27:54,440 --> 00:27:55,660 Ecco, questo è un approccio. 654 00:27:55,660 --> 00:28:00,120 >> Ma altrimenti come potremmo realizzare questo stessa struttura dati, potenzialmente? 655 00:28:00,120 --> 00:28:00,280 Giusto? 656 00:28:00,280 --> 00:28:04,530 Mi sento come abbiamo appena risolto questo problema come una settimana fa. 657 00:28:04,530 --> 00:28:08,860 Qual è stata la soluzione a questo problema che Steven ha incontrato? 658 00:28:08,860 --> 00:28:10,370 Liste collegate Così, giusto. 659 00:28:10,370 --> 00:28:13,410 >> Se il problema è che stiamo dipingendo noi stessi in un angolo assegnando 660 00:28:13,410 --> 00:28:17,580 in anticipo troppo poca memoria che abbiamo poi avere a che fare in qualche modo con, bene, 661 00:28:17,580 --> 00:28:19,880 perché non solo evitare che rilasciare del tutto? 662 00:28:19,880 --> 00:28:26,170 Perché non dichiarano i vassoi per essere un puntatore a un nodo, ergo una lista concatenata, 663 00:28:26,170 --> 00:28:30,740 e poi semplicemente allocare nuovi nodi ogni volta Steven necessario misura un 664 00:28:30,740 --> 00:28:32,400 numero nella struttura dati. 665 00:28:32,400 --> 00:28:34,200 >> Quindi l'immagine dovrebbe cambiare. 666 00:28:34,200 --> 00:28:38,220 Non sta andando essere il più pulito e come semplice come un array di tre interi. 667 00:28:38,220 --> 00:28:42,970 Ora si sta andando ad essere un puntatore ad una struct, e che la struttura sta per 668 00:28:42,970 --> 00:28:44,830 avere un int e un indicatore accanto. 669 00:28:44,830 --> 00:28:47,670 E 'intenzione di portare via quel puntatore ad un altro tale struttura per 670 00:28:47,670 --> 00:28:48,600 un altro esempio struct. 671 00:28:48,600 --> 00:28:50,560 Quindi, l'immagine sarebbe in realtà ottenere un po 'incasinato. 672 00:28:50,560 --> 00:28:52,950 E avremmo frecce legando tutto insieme. 673 00:28:52,950 --> 00:28:55,280 >> Ma va bene, giusto, perché abbiamo visto come fare questo. 674 00:28:55,280 --> 00:28:58,180 E una volta che si ottiene confortevole attuare qualcosa di simile a una linked 675 00:28:58,180 --> 00:29:01,450 lista, che dovrete fare se scegliere di implementare una tabella hash con 676 00:29:01,450 --> 00:29:05,120 concatenazioni separate per p-set di 6, è possibile usarlo come un blocco di costruzione, o di un 677 00:29:05,120 --> 00:29:08,870 ingrediente, o in Scratch dire, un procedura, qualcosa che si mette, si 678 00:29:08,870 --> 00:29:12,560 creato il proprio pezzo di puzzle che si può riutilizzare. 679 00:29:12,560 --> 00:29:17,090 Compromessi così, ma le possibili soluzioni che abbiamo effettivamente visto prima. 680 00:29:17,090 --> 00:29:20,560 >> Quindi, molto spesso, si vede questo ogni anno o due, quando Apple rilascia 681 00:29:20,560 --> 00:29:23,060 qualcosa di nuovo, e tutti i matti line up al di fuori del Mela 682 00:29:23,060 --> 00:29:27,050 negozio per comprare il loro marginale aggiornare l'hardware. 683 00:29:27,050 --> 00:29:30,420 Dico questo, va bene, perché Io sono una di quelle persone. 684 00:29:30,420 --> 00:29:35,140 Quindi, che tipo di struttura dati potrebbe rappresentare questa realtà? 685 00:29:35,140 --> 00:29:36,980 >> Beh, chiamiamola una coda, una linea. 686 00:29:36,980 --> 00:29:40,270 So British chiamerebbe in genere una coda in ogni caso, quindi è un bel nome. 687 00:29:40,270 --> 00:29:44,960 E le due operazioni che una coda sostiene che chiameremo un enqueue 688 00:29:44,960 --> 00:29:48,900 funzionamento e una operazione dequeue, quali sono simili a 689 00:29:48,900 --> 00:29:50,120 spirito di spingere e pop. 690 00:29:50,120 --> 00:29:54,060 E 'solo una sorta di diversa convenzione, quello che stiamo chiamando questi. 691 00:29:54,060 --> 00:29:57,680 Ma per accodare qualcosa significa aggiungere o inserirlo alla struttura di dati. 692 00:29:57,680 --> 00:29:59,570 Per annullare l'accodamento significa per rimuoverlo. 693 00:29:59,570 --> 00:30:05,170 Ma mentre una pila era dati LIFO struttura, una coda è una prima in, 694 00:30:05,170 --> 00:30:06,740 first out struttura dati. 695 00:30:06,740 --> 00:30:10,050 >> Se è la prima persona in linea, sarai la prima persona a ottenere 696 00:30:10,050 --> 00:30:12,420 fuori linea e comprare il vostro nuovo dispositivo. 697 00:30:12,420 --> 00:30:18,070 Immaginate come sconvolto queste persone sarebbero se Apple invece utilizzato uno stack, per 698 00:30:18,070 --> 00:30:21,250 esempio, di attuare la raccolta up del vostro nuovo giocattolo. 699 00:30:21,250 --> 00:30:24,310 Quindi, le code hanno senso, certamente, e siamo in grado di pensare a tutti i tipi di 700 00:30:24,310 --> 00:30:27,480 applicazioni, presumibilmente, per le code, soprattutto quando si vuole equità. 701 00:30:27,480 --> 00:30:30,040 Così come potremmo implementare questi come struttura di dati? 702 00:30:30,040 --> 00:30:33,680 >> Ebbene, propongo che potremmo bisogno di farlo in questo modo. 703 00:30:33,680 --> 00:30:35,225 Quindi ho intenzione di ora hanno i numeri. 704 00:30:35,225 --> 00:30:38,190 Quindi dovremo fare cose semplici e non necessariamente parlare in termini di vassoi. 705 00:30:38,190 --> 00:30:40,220 Solo numeri che le persone di ottenuti. 706 00:30:40,220 --> 00:30:43,760 Capacità sta andando, ancora una volta, fissare il numero totale di persone che possono essere in 707 00:30:43,760 --> 00:30:46,900 questa linea, come tre o qualunque altro valore. 708 00:30:46,900 --> 00:30:50,760 >> Ma io propongo che ho bisogno di tenere traccia non solo delle dimensioni del 709 00:30:50,760 --> 00:30:52,370 coda, quante cose sono in esso. 710 00:30:52,370 --> 00:30:56,310 Quindi, la dimensione è la dimensione corrente, la capacità è la dimensione massima. 711 00:30:56,310 --> 00:30:58,540 Proprio di nuovo, nomenclatura per convenzione. 712 00:30:58,540 --> 00:31:03,680 Perché ho bisogno di un int aggiuntivo all'interno di una coda per tenere traccia di chi è dentro 713 00:31:03,680 --> 00:31:05,365 davanti alla linea? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Perché ho bisogno di farlo in questo caso? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Beh, come è questa immagine andando a cambiare? 718 00:31:16,190 --> 00:31:19,280 Probabilmente può riutilizzare più di questa immagine. 719 00:31:19,280 --> 00:31:21,480 Lasciami andare avanti e cancellare quello che c'è qui. 720 00:31:21,480 --> 00:31:24,580 Daremo questo un po ' Nome quassù diverso. 721 00:31:24,580 --> 00:31:28,930 Liberiamoci del 17 Liberiamoci del 9, liberiamoci del 3. 722 00:31:28,930 --> 00:31:30,410 E andiamo ad aggiungere un'altra cosa. 723 00:31:30,410 --> 00:31:34,710 Propongo che ho bisogno di tenere traccia di la parte anteriore della lista, che è solo 724 00:31:34,710 --> 00:31:35,570 andando essere un int pure. 725 00:31:35,570 --> 00:31:36,550 E abbiamo intenzione di mantenere le cose semplici. 726 00:31:36,550 --> 00:31:37,740 Nessun lista collegata per ora. 727 00:31:37,740 --> 00:31:40,900 >> Ci ammettere che stiamo andando a urtare contro questo limite. 728 00:31:40,900 --> 00:31:43,720 Ma quello che voglio vedere succederà questa volta? 729 00:31:43,720 --> 00:31:47,240 Quindi suppongo io vado avanti e il primo persona viene in su in linea, e 730 00:31:47,240 --> 00:31:48,560 è il numero 9. 731 00:31:48,560 --> 00:31:49,680 Noi abbiamo le palle stress. 732 00:31:49,680 --> 00:31:51,330 Posso rubare, diciamo, due o tre persone? 733 00:31:51,330 --> 00:31:52,690 Uno, due, tre? 734 00:31:52,690 --> 00:31:53,120 Andiamo su. 735 00:31:53,120 --> 00:31:56,022 Destra dalla parte anteriore, perché faremo questo rapido. 736 00:31:56,022 --> 00:31:59,415 >> Ognuno di voi è ora sta per essere un ragazzo fan in fila alla Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Non riceverete hardware Apple al termine di questo però. 739 00:32:06,210 --> 00:32:06,500 D'accordo. 740 00:32:06,500 --> 00:32:09,430 Quindi sei il numero 9, si è numero 17, numero 22. 741 00:32:09,430 --> 00:32:12,130 Questi sono numeri arbitrari, come studente gli ID o roba del genere. 742 00:32:12,130 --> 00:32:14,550 E in un attimo, cominciamo per iniziare ad aggiungere le cose. 743 00:32:14,550 --> 00:32:16,000 E io corro il consiglio qui questa volta. 744 00:32:16,000 --> 00:32:19,570 >> Quindi, in questo caso, ho inizializzato il fronte di essere - 745 00:32:19,570 --> 00:32:22,380 Io in realtà non mi interessa quello che la anteriore è, perché la dimensione è zero. 746 00:32:22,380 --> 00:32:24,480 Quindi questo potrebbe anche solo essere un punto di domanda. 747 00:32:24,480 --> 00:32:26,170 Questi sono tutti punti interrogativi. 748 00:32:26,170 --> 00:32:29,880 Così ora inizieremo a vedere in realtà un po 'di persone in fila al negozio. 749 00:32:29,880 --> 00:32:33,320 >> Quindi, se il numero 9, che sei il primo lì a 5:00, andare avanti e allineare, 750 00:32:33,320 --> 00:32:34,210 o la sera prima. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Così ora 9 è qui. 753 00:32:35,940 --> 00:32:37,940 9 è così in testa alla lista. 754 00:32:37,940 --> 00:32:41,440 Quindi ho intenzione di andare avanti e di aggiornare la dimensione di questi dati correnti 755 00:32:41,440 --> 00:32:44,740 struttura per non essere più 0, ma per essere 1. 756 00:32:44,740 --> 00:32:47,630 Ho intenzione di mettere 9 al anteriore della lista. 757 00:32:47,630 --> 00:32:51,020 Lasciami andare avanti e di attivare o disattivare la schermata così possiamo vedere davanti a noi qui. 758 00:32:51,020 --> 00:32:53,220 >> E ora che cosa voglio di mettere a fronte? 759 00:32:53,220 --> 00:32:56,240 Ho intenzione di tenere traccia che l' anteriore della coda in questo momento 760 00:32:56,240 --> 00:32:58,570 è in posizione 0. 761 00:32:58,570 --> 00:33:00,510 Perché quello che sta accanto sta per accadere? 762 00:33:00,510 --> 00:33:03,000 Beh, immagino che ora mi Enqueue 17 pure. 763 00:33:03,000 --> 00:33:04,510 Così hop in linea lì. 764 00:33:04,510 --> 00:33:07,060 E ancora, il tipo di porta per la negozio sta per essere qui. 765 00:33:07,060 --> 00:33:08,700 Così ora ho aggiunto 17. 766 00:33:08,700 --> 00:33:10,810 E anche se questi ragazzi stanno bloccando lo schermo, che è OK, 767 00:33:10,810 --> 00:33:12,300 perché possiamo vederlo da qui. 768 00:33:12,300 --> 00:33:12,910 Mi dispiace. 769 00:33:12,910 --> 00:33:13,810 >> AUDIENCE: Siamo in grado di muoversi - 770 00:33:13,810 --> 00:33:14,660 >> DAVID MALAN: No, va bene così. 771 00:33:14,660 --> 00:33:16,000 È enorme lassù. 772 00:33:16,000 --> 00:33:18,580 Quindi 17 è ora all'interno della coda. 773 00:33:18,580 --> 00:33:21,332 Ho bisogno di aggiornare i quali campi ora però? 774 00:33:21,332 --> 00:33:23,210 OK, sicuramente dimensioni. 775 00:33:23,210 --> 00:33:26,430 E che dire di fronte? 776 00:33:26,430 --> 00:33:27,040 OK, no. 777 00:33:27,040 --> 00:33:30,200 Anteriore non dovrebbe cambiare, perché a differenza di una pila, abbiamo 778 00:33:30,200 --> 00:33:31,370 vogliono mantenere l'equità. 779 00:33:31,370 --> 00:33:35,150 Quindi se 9 è venuto in primo luogo, vogliamo 9 di essere il primo fuori dalla linea 780 00:33:35,150 --> 00:33:36,420 e in negozio. 781 00:33:36,420 --> 00:33:37,220 >> In effetti, vediamo che. 782 00:33:37,220 --> 00:33:42,235 Prima inseriamo 22, diamo andare avanti e dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Qual è il tuo nome? 784 00:33:42,970 --> 00:33:43,680 >> AUDIENCE: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID MALAN: Jake sta andando essere rimosse dalla coda ora. 786 00:33:45,440 --> 00:33:48,050 Così si arriva a piedi in negozio. 787 00:33:48,050 --> 00:33:49,880 E far finta che il negozio è finita lì. 788 00:33:49,880 --> 00:33:51,970 Così ora che cosa ha bisogno - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Cosa deve accadere ora? 790 00:33:53,400 --> 00:33:54,490 Decisione di progettazione. 791 00:33:54,490 --> 00:33:56,825 Quindi non è un cattivo istinto, ma - qual è il tuo nome? 792 00:33:56,825 --> 00:33:57,090 >> AUDIENCE: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID MALAN: David. 794 00:33:57,500 --> 00:33:58,810 Così che cosa fece Davide? 795 00:33:58,810 --> 00:34:02,590 Stava cercando di ordinare di fissare i dati struttura e mossa dalla sua posizione 796 00:34:02,590 --> 00:34:04,100 in primo luogo di Jake. 797 00:34:04,100 --> 00:34:06,740 E va bene, se siamo disposti di accettare che come un 798 00:34:06,740 --> 00:34:08,199 dettaglio di implementazione. 799 00:34:08,199 --> 00:34:11,100 Ma in primo luogo, cerchiamo di aggiornare i dati struttura prima di farlo. 800 00:34:11,100 --> 00:34:14,139 Perché non mi piaceva l'idea di tutti le persone spostando in questa linea. 801 00:34:14,139 --> 00:34:17,360 >> Non è un grosso problema se Davide lo fa con un passo, ma ancora una volta, ripensare a 802 00:34:17,360 --> 00:34:20,360 quando abbiamo avuto otto volontari sul palco e abbiamo fatto come l'inserimento 803 00:34:20,360 --> 00:34:22,600 sorta, dove abbiamo dovuto cominciare spostare tutti intorno. 804 00:34:22,600 --> 00:34:23,790 Che ha ottenuto costoso, giusto? 805 00:34:23,790 --> 00:34:28,330 Questo mi fa rabbrividire di grande O di N, O grande di n al quadrato di nuovo. 806 00:34:28,330 --> 00:34:30,650 E 'non sentirsi come un risultato ideale. 807 00:34:30,650 --> 00:34:32,080 >> Così facciamo solo aggiornare questo. 808 00:34:32,080 --> 00:34:35,120 Quindi la dimensione della coda non è più 2. 809 00:34:35,120 --> 00:34:37,090 Ora è semplicemente 1. 810 00:34:37,090 --> 00:34:40,360 Ma ora posso aggiornare qualcosa Non è stato aggiornato in precedenza, la 811 00:34:40,360 --> 00:34:41,130 anteriore della lista. 812 00:34:41,130 --> 00:34:45,420 Potrei solo dire, è che posizione 1? 813 00:34:45,420 --> 00:34:49,770 Così ora abbiamo valore spazzatura qui, valore spazzatura qui, e David nel 814 00:34:49,770 --> 00:34:51,469 mezzo di questa spazzatura. 815 00:34:51,469 --> 00:34:54,980 Ma la struttura di dati è ancora intatta. 816 00:34:54,980 --> 00:34:58,540 >> E in effetti, non ho nemmeno bisogno di cambiare ex numero di Jake 817 00:34:58,540 --> 00:35:00,460 9, perché chi se ne frega. 818 00:35:00,460 --> 00:35:04,470 Non ho abbastanza informazioni ora in dimensione che so c'è una persona in 819 00:35:04,470 --> 00:35:05,030 questa coda. 820 00:35:05,030 --> 00:35:08,340 E so che quella persona è in posizione 1, non 0. 821 00:35:08,340 --> 00:35:09,760 Non sto contando. 822 00:35:09,760 --> 00:35:11,300 Così pure 1. 823 00:35:11,300 --> 00:35:13,410 Quindi la struttura di dati è ancora OK. 824 00:35:13,410 --> 00:35:14,330 >> Ebbene, che cosa succede dopo? 825 00:35:14,330 --> 00:35:15,010 Enqueue Facciamo - 826 00:35:15,010 --> 00:35:15,370 come ti chiami? 827 00:35:15,370 --> 00:35:16,160 >> AUDIENCE: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID MALAN: Callen. 829 00:35:16,580 --> 00:35:20,770 Facciamo enqueue un Callen, e 22 è ora nella coda. 830 00:35:20,770 --> 00:35:22,300 Così ora che cosa deve cambiare qui? 831 00:35:22,300 --> 00:35:24,380 Anteriore non ha intenzione di cambiare, ovviamente. 832 00:35:24,380 --> 00:35:27,160 Dimensione sta per cambiare per essere di nuovo 2. 833 00:35:27,160 --> 00:35:31,590 E 22 finisce qui, 9 è ancora presente, ma è efficace un 834 00:35:31,590 --> 00:35:32,600 valore spazzatura adesso. 835 00:35:32,600 --> 00:35:35,910 E 'solo un residuo di Jake passato. 836 00:35:35,910 --> 00:35:39,200 >> Così ora che cosa succede se Ho Dequeue David? 837 00:35:39,200 --> 00:35:41,560 Un'ultima operazione, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Potremmo spostare, ma propongo ti permette di fare il meno lavoro possibile. 839 00:35:46,070 --> 00:35:50,280 Ora la mia struttura dati va eseguire nel formato da 2 a 1. 840 00:35:50,280 --> 00:35:53,730 Ma la parte anteriore della coda ora diventa 2. 841 00:35:53,730 --> 00:35:56,640 Non ho bisogno di cambiare questi numeri appena ancora, perché sono 842 00:35:56,640 --> 00:35:58,230 solo i valori della spazzatura. 843 00:35:58,230 --> 00:35:59,720 >> Ma ora che cosa succede? 844 00:35:59,720 --> 00:36:03,280 Supponiamo che io enqueue me stesso, 26? 845 00:36:03,280 --> 00:36:05,890 Mi sento come se io appartengo qui. 846 00:36:05,890 --> 00:36:06,890 Quindi sono stati accodati. 847 00:36:06,890 --> 00:36:08,760 Così ho sorta di appartengo a questo posto. 848 00:36:08,760 --> 00:36:11,300 E anche se lo fai non abbastanza apprezzare questo visivamente sul palcoscenico, 849 00:36:11,300 --> 00:36:15,075 perché abbiamo un sacco di spazio, dovrei non essere in piedi qui, perché? 850 00:36:15,075 --> 00:36:16,290 >> PUBBLICO: Sei fuori dai limiti. 851 00:36:16,290 --> 00:36:16,370 >> DAVID MALAN: Giusto. 852 00:36:16,370 --> 00:36:16,940 Io sono fuori dai limiti. 853 00:36:16,940 --> 00:36:19,330 Ho indicizzati al di là del limiti di questo array. 854 00:36:19,330 --> 00:36:23,420 Mi dovrebbe essere in uno dei tre possibili posizioni. 855 00:36:23,420 --> 00:36:25,150 Ora, dove c'è di più naturale di andare? 856 00:36:25,150 --> 00:36:27,760 Propongo di leveraged una settimana un trucco. 857 00:36:27,760 --> 00:36:30,150 L'operatore mod, percentuale. 858 00:36:30,150 --> 00:36:36,850 Perché io sono tecnicamente in piedi al posizione 3, ma mi fanno 3 Capacità di mod, 859 00:36:36,850 --> 00:36:40,250 così 3, un segno di percentuale, 3 - 860 00:36:40,250 --> 00:36:40,970 capacità è 3. 861 00:36:40,970 --> 00:36:41,720 Che cos'è? 862 00:36:41,720 --> 00:36:43,700 Qual è il resto quando si divide 3 da 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> In modo che mi mette fosse Jake era, che in realtà è buono. 865 00:36:48,140 --> 00:36:50,370 Così ora l'attuazione di questa cosa sta andando a 866 00:36:50,370 --> 00:36:51,250 essere un po 'di mal di testa. 867 00:36:51,250 --> 00:36:53,740 E 'davvero solo una riga della cefalea, del codice. 868 00:36:53,740 --> 00:36:56,580 Ma almeno adesso c'è immondizia valore qui, ma ci sono due 869 00:36:56,580 --> 00:36:57,910 int legittimi qui. 870 00:36:57,910 --> 00:37:04,160 E io sostengo che ora abbiamo fatto esattamente quello che dobbiamo fare, purché 871 00:37:04,160 --> 00:37:08,600 cambiamo quello che Jake valore doveva essere 26. 872 00:37:08,600 --> 00:37:12,110 >> Ora abbiamo abbastanza informazioni ancora per mantenere l'integrità 873 00:37:12,110 --> 00:37:13,060 di questa struttura dati. 874 00:37:13,060 --> 00:37:17,160 Siamo ancora un po 'di fortuna, quando abbiamo desidera inserire quattro o più totale 875 00:37:17,160 --> 00:37:20,740 elementi, ma posso almeno fare abbastanza uso efficiente di questa costante 876 00:37:20,740 --> 00:37:21,740 tempo, infatti. 877 00:37:21,740 --> 00:37:27,150 Io non devo preoccuparmi di spostamento tutti, come l'inclinazione di David era. 878 00:37:27,150 --> 00:37:30,816 >> Tutte le domande su pile, o questa coda? 879 00:37:30,816 --> 00:37:32,184 >> PUBBLICO: E 'la ragione per la quale avete bisogno del formato in modo da sapere 880 00:37:32,184 --> 00:37:34,010 dove per avere una persona? 881 00:37:34,010 --> 00:37:34,770 >> DAVID MALAN: Esattamente. 882 00:37:34,770 --> 00:37:38,230 Ho bisogno di sapere la dimensione della matrice perché ho bisogno di sapere esattamente come 883 00:37:38,230 --> 00:37:41,940 molti di questi valori sono legittimi, e in modo che possa trovare dove mettere 884 00:37:41,940 --> 00:37:42,800 la prossima persona. 885 00:37:42,800 --> 00:37:43,300 Esattamente. 886 00:37:43,300 --> 00:37:44,580 La dimensione è - 887 00:37:44,580 --> 00:37:46,360 in realtà, non abbiamo ancora aggiorniamo questo. 888 00:37:46,360 --> 00:37:48,380 Io ho aggiunto a 26. 889 00:37:48,380 --> 00:37:51,760 La dimensione è ora, non 1, ma 2. 890 00:37:51,760 --> 00:37:57,780 Così ora questo davvero mi aiuta a trovare il capo della lista, che non è 0, non 891 00:37:57,780 --> 00:37:59,250 1, ma è 2. 892 00:37:59,250 --> 00:38:01,665 La parte anteriore della lista è infatti il ​​numero 22. 893 00:38:01,665 --> 00:38:05,120 Perché lui è venuto in primo luogo, così egli dovrebbe essere consentito in negozio prima di me, 894 00:38:05,120 --> 00:38:08,780 anche se visivamente sto in piedi più vicino al negozio. 895 00:38:08,780 --> 00:38:09,220 >> D'accordo? 896 00:38:09,220 --> 00:38:12,410 Un applauso a questi ragazzi e noi li lasciamo fuori di lì. 897 00:38:12,410 --> 00:38:17,090 >> [Applausi] 898 00:38:17,090 --> 00:38:18,150 >> DAVID MALAN: potrei lasciare si mantiene il cassetto. 899 00:38:18,150 --> 00:38:20,760 Abbiamo potuto vedere che cosa succede se si vuole, ma forse no. 900 00:38:20,760 --> 00:38:21,590 D'accordo. 901 00:38:21,590 --> 00:38:25,380 Così che ora a che punto siamo? 902 00:38:25,380 --> 00:38:28,900 Bene, lasciate che propongo che ci sia un alcune strutture di altri dati che potremmo 903 00:38:28,900 --> 00:38:33,810 iniziare ad aggiungere al nostro kit di strumenti che saranno effettivamente essere molto, molto rilevante come 904 00:38:33,810 --> 00:38:35,270 ci immergiamo in roba web. 905 00:38:35,270 --> 00:38:38,150 Che ancora una volta, ha un qualche tipo di collegamento per alberi sotto forma di 906 00:38:38,150 --> 00:38:40,550 qualcosa chiamato DOM, documento modello a oggetti. 907 00:38:40,550 --> 00:38:42,370 Ma vedremo più di che tra non molto. 908 00:38:42,370 --> 00:38:46,260 >> Lasciatemi Propongo definitionally che abbiamo chiamare albero ora quello che si potrebbe sapere come 909 00:38:46,260 --> 00:38:48,820 più di un albero genealogico, in cui si avere qualche antenato al 910 00:38:48,820 --> 00:38:49,790 radici dell'albero. 911 00:38:49,790 --> 00:38:54,480 Una matriarca patriarcale o presso la cima dell'albero. 912 00:38:54,480 --> 00:38:56,700 Senza il loro coniuge, in questo caso. 913 00:38:56,700 --> 00:39:00,940 Ma ora abbiamo quello che chiameremo bambini, che sono i nodi che pendono 914 00:39:00,940 --> 00:39:05,480 fuori il figlio sinistro o il bambino a destra, frecce, come raffigurato qui. 915 00:39:05,480 --> 00:39:10,490 >> In altre parole, in una struttura di dati ad albero in informatica, un albero è pari a zero 916 00:39:10,490 --> 00:39:11,480 o più nodi. 917 00:39:11,480 --> 00:39:13,500 Se ha almeno un nodo, che chiama la radice. 918 00:39:13,500 --> 00:39:15,700 Sono le cose visivamente che ci avviciniamo al top. 919 00:39:15,700 --> 00:39:20,280 E questo nodo, come qualsiasi altro nodo, può avere zero, uno, o due, o tre, 920 00:39:20,280 --> 00:39:23,600 o comunque molti bambini la struttura di dati supporta. 921 00:39:23,600 --> 00:39:29,150 In questo caso, la radice, la memorizzazione valore di uno, ha due figli, 2 e 3, 922 00:39:29,150 --> 00:39:33,020 così noi generalmente chiamiamo 2 sinistra bambino e 3 il bambino giusto. 923 00:39:33,020 --> 00:39:36,940 >> E poi, quando ci mettiamo a 5, 6, e 7, 6 potrebbe essere chiamato il figlio di mezzo. 924 00:39:36,940 --> 00:39:38,940 Se si dispone di quattro figli, esso si confonde. 925 00:39:38,940 --> 00:39:42,260 Quindi smettiamo di usare quel tipo di scelta rapida verbalmente. 926 00:39:42,260 --> 00:39:44,580 Ma è davvero solo un albero genealogico. 927 00:39:44,580 --> 00:39:48,880 E le foglie qui sono i nodi che si hanno figli. 928 00:39:48,880 --> 00:39:52,540 Sono appesi fuori la parte inferiore della struttura. 929 00:39:52,540 --> 00:39:56,940 >> Così come potremmo implementare un albero che ha solo due figli al massimo? 930 00:39:56,940 --> 00:39:58,410 Lo chiameremo un albero binario. 931 00:39:58,410 --> 00:40:00,960 Bi nuovo significato a due, in questo caso, come con binario. 932 00:40:00,960 --> 00:40:04,830 E così si può avere zero, uno, o al massimo due bambini. 933 00:40:04,830 --> 00:40:08,650 >> Io propongo di attuare il nodo per quella struttura con un int n, 934 00:40:08,650 --> 00:40:11,910 e poi due puntatori, uno chiamato a sinistra, uno chiamato destra. 935 00:40:11,910 --> 00:40:14,830 Ma questi sono solo belle convenzioni arbitrarie. 936 00:40:14,830 --> 00:40:18,170 E cosa c'è di bello oggi, soprattutto se si genere di lottato concettualmente con 937 00:40:18,170 --> 00:40:21,300 ricorsione, o pensato che non fosse davvero una soluzione a nulla, 938 00:40:21,300 --> 00:40:23,120 soprattutto se si potesse esaurito la memoria. 939 00:40:23,120 --> 00:40:26,600 Ora che stiamo parlando di dati strutture e algoritmi che consentono 940 00:40:26,600 --> 00:40:31,030 noi di attraversare e di manipolarle, Risulta che la ricorsione torna in 941 00:40:31,030 --> 00:40:34,240 una molto più convincente se non bellissimo modo. 942 00:40:34,240 --> 00:40:38,670 >> Quindi questo vi propongo è l'attuazione di una funzione di ricerca. 943 00:40:38,670 --> 00:40:39,870 Dati due ingressi - 944 00:40:39,870 --> 00:40:41,570 quindi pensare a questo come una scatola nera. 945 00:40:41,570 --> 00:40:46,560 Dati due ingressi, n, int, e un puntatore a un albero, un puntatore ad una 946 00:40:46,560 --> 00:40:50,020 nodo, o realmente la radice di un albero, mi affermazione che questa funzione può restituire 947 00:40:50,020 --> 00:40:53,530 vero o falso, che il valore di n è all'interno di questo albero. 948 00:40:53,530 --> 00:40:55,210 >> Che cosa è all'interno di questa scatola nera? 949 00:40:55,210 --> 00:40:57,440 Beh, quattro rami. 950 00:40:57,440 --> 00:40:58,385 Il primo solo assegni. 951 00:40:58,385 --> 00:41:00,490 Se albero è nullo, solo restituire false. 952 00:41:00,490 --> 00:41:04,580 Se non c'è nodo, non c'è n, non c'è nessun numero, solo restituiscono false. 953 00:41:04,580 --> 00:41:12,330 Se, però, n, il valore che stai cercando per, è inferiore albero freccia n, e 954 00:41:12,330 --> 00:41:15,180 tanto per essere chiari, che cosa significa quando Scrivo albero e poi la freccia 955 00:41:15,180 --> 00:41:18,150 notazione, n? 956 00:41:18,150 --> 00:41:18,690 Esattamente. 957 00:41:18,690 --> 00:41:21,970 Significa che dereferenziare puntatore chiamato albero. 958 00:41:21,970 --> 00:41:26,750 Vai lì, e poi entrare di che nodo e ottenere il suo campo chiamato n. 959 00:41:26,750 --> 00:41:30,810 E quindi confrontare il n effettivo che era passato nella ricerca contro di essa. 960 00:41:30,810 --> 00:41:35,390 >> Quindi se n è inferiore, il valore n nel nodo della struttura stessa, bene, 961 00:41:35,390 --> 00:41:36,720 che cosa vuol dire? 962 00:41:36,720 --> 00:41:40,690 Ciò significa nulla a prima vista. 963 00:41:40,690 --> 00:41:40,900 Giusto? 964 00:41:40,900 --> 00:41:45,560 Proprio come quando si dispone di una serie di valori, come si potrebbe applicare binario 965 00:41:45,560 --> 00:41:48,290 cercare come una forma di divisione e conquistare. 966 00:41:48,290 --> 00:41:51,790 Ma quello presupposto abbiamo bisogno di fare per la ricerca binaria funzioni tutto 967 00:41:51,790 --> 00:41:54,510 nella rubrica e esempi precedenti? 968 00:41:54,510 --> 00:41:55,530 >> Come da ordinare. 969 00:41:55,530 --> 00:41:59,490 Quindi cerchiamo di perfezionare la definizione di albero qui di non essere solo un albero, che può 970 00:41:59,490 --> 00:42:00,880 avere qualsiasi numero di bambini. 971 00:42:00,880 --> 00:42:04,700 Non solo un albero binario, che può avere 0, 1 o 2 al massimo. 972 00:42:04,700 --> 00:42:09,700 Ma come un albero binario di ricerca, o BST, che è solo un modo elegante per dire un 973 00:42:09,700 --> 00:42:15,430 albero binario tale che ogni nodo figlio sinistro, se presente, è 974 00:42:15,430 --> 00:42:16,830 meno del nodo. 975 00:42:16,830 --> 00:42:20,170 E figlio destro di ogni nodo, se presente, è maggiore 976 00:42:20,170 --> 00:42:21,740 rispetto al nodo stesso. 977 00:42:21,740 --> 00:42:25,200 >> Quindi, in altre parole, se si dovesse disegnare l'albero fuori, tutti i numeri sono 978 00:42:25,200 --> 00:42:30,620 accuratamente equilibrato come questo in modo che se avete 55 come la radice, il 33 può andare 979 00:42:30,620 --> 00:42:33,090 alla sua sinistra, perché è meno di 55. 980 00:42:33,090 --> 00:42:36,430 77 può andare alla sua destra perché è maggiore di 55. 981 00:42:36,430 --> 00:42:40,750 Ma ora notare, la stessa definizione, si tratta di una definizione ricorsiva verbalmente, 982 00:42:40,750 --> 00:42:42,600 deve applicare per 33. 983 00:42:42,600 --> 00:42:47,610 33 del bambino di sinistra deve essere minore di esso, e il figlio destro di 33, 44, deve essere 984 00:42:47,610 --> 00:42:48,580 grande di esso. 985 00:42:48,580 --> 00:42:51,670 >> Quindi questo è un albero binario di ricerca, e Propongo, usando un po 'di 986 00:42:51,670 --> 00:42:53,910 ricorsione, possiamo ora trovare n. 987 00:42:53,910 --> 00:42:59,160 Quindi se n è minore del valore n che è nodo corrente, ho intenzione di andare 988 00:42:59,160 --> 00:43:04,090 avanti e punt, per così dire, e proprio restituire qualunque sia la risposta è di 989 00:43:04,090 --> 00:43:08,470 alla ricerca di n sul figlio sinistro di albero. 990 00:43:08,470 --> 00:43:11,370 Si noti ancora una volta, questa funzione è sufficiente aspetta una stella nodo, un 991 00:43:11,370 --> 00:43:12,780 puntatore a un nodo. 992 00:43:12,780 --> 00:43:17,360 Quindi sicuramente posso solo fare albero Freccia a sinistra, che porterà 993 00:43:17,360 --> 00:43:18,400 me ad un altro nodo. 994 00:43:18,400 --> 00:43:19,480 Ma che cos'è quel nodo? 995 00:43:19,480 --> 00:43:22,820 >> Ebbene, secondo questa dichiarazione, sinistra è solo un puntatore, perché così, 996 00:43:22,820 --> 00:43:27,090 significa che sto passando alla funzione di ricerca un puntatore diverso, cioè 997 00:43:27,090 --> 00:43:30,750 quello che rappresenta albero di mio figlio sinistro. 998 00:43:30,750 --> 00:43:36,040 Quindi in questo caso, il puntatore a 33, se questo è il nostro ingresso campione Nel frattempo, se 999 00:43:36,040 --> 00:43:40,740 n è maggiore del valore n alla nodo corrente nella struttura, quindi io sono 1000 00:43:40,740 --> 00:43:43,370 intenzione di andare avanti e di punt in altra direzione e dire, non mi 1001 00:43:43,370 --> 00:43:47,280 sapere se questo valore n è nell'albero, ma so che se lo è, è la mia 1002 00:43:47,280 --> 00:43:49,090 ramo di destra, per così dire. 1003 00:43:49,090 --> 00:43:53,120 Quindi fammi chiamare ricorsivamente di ricerca, passando nuovamente un n, ma passando un 1004 00:43:53,120 --> 00:43:54,580 puntatore a mio figlio destro. 1005 00:43:54,580 --> 00:44:00,020 >> In altre parole, se io sono attualmente a 55 e sto cercando 99, lo so che il 99 1006 00:44:00,020 --> 00:44:04,270 è più grande di 55, così come ho strappato i telefoni settimane libro fa e abbiamo 1007 00:44:04,270 --> 00:44:07,140 è andato a destra, allo stesso modo siamo intenzione di andare qui. 1008 00:44:07,140 --> 00:44:11,960 E io non so se è alla mia destra bambino, e non, 77 è lì, ma 1009 00:44:11,960 --> 00:44:13,210 Lo so che è in quella direzione. 1010 00:44:13,210 --> 00:44:18,770 Così chiamo ricerca sul mio figlio destro, 77, e lasciare che la figura di ricerca fuori dal 1011 00:44:18,770 --> 00:44:24,950 lì se 99 in questa arbitraria esempio è in realtà lì. 1012 00:44:24,950 --> 00:44:26,900 >> Altrimenti, qual è il caso finale? 1013 00:44:26,900 --> 00:44:28,620 Se albero è null è un caso. 1014 00:44:28,620 --> 00:44:31,890 Se n è minore del nodo attuale valore è un altro caso. 1015 00:44:31,890 --> 00:44:35,120 Se n è maggiore della corrente valore del nodo è un terzo caso. 1016 00:44:35,120 --> 00:44:38,250 Qual è il quarto e ultimo caso? 1017 00:44:38,250 --> 00:44:39,480 Penso che siamo fuori di casi, giusto? 1018 00:44:39,480 --> 00:44:44,690 Deve essere che n è nella nodo corrente che sono in. 1019 00:44:44,690 --> 00:44:49,640 >> Quindi, se io sto cercando 55 a questo punto nella storia, quel ramo della 1020 00:44:49,640 --> 00:44:51,780 albero sarebbe restituire true. 1021 00:44:51,780 --> 00:44:55,380 Quindi, ciò che è interessante è che abbiamo in realtà, a differenza di settimane passato, noi genere 1022 00:44:55,380 --> 00:44:56,740 di avere due casi base. 1023 00:44:56,740 --> 00:44:58,300 E loro non hanno a essere tutto in alto. 1024 00:44:58,300 --> 00:45:01,390 La parte superiore è un caso base perché se il albero è nullo, non c'è niente da fare. 1025 00:45:01,390 --> 00:45:03,410 Basta tornare un hard coded valore false. 1026 00:45:03,410 --> 00:45:07,400 >> Il ramo inferiore è una sorta di di default, per cui se abbiamo controllato per 1027 00:45:07,400 --> 00:45:11,550 nullo, abbiamo controllato se deve essere a sinistra, ma non dovrebbe essere, abbiamo 1028 00:45:11,550 --> 00:45:14,640 verificato se dovesse essere giusta, ma non dovrebbe essere, evidentemente deve essere 1029 00:45:14,640 --> 00:45:15,870 là dove siamo. 1030 00:45:15,870 --> 00:45:16,780 Questo è un caso base. 1031 00:45:16,780 --> 00:45:19,920 Quindi ci sono due casi ricorsivi ci intramezzato in mezzo. 1032 00:45:19,920 --> 00:45:21,630 Ma ho potuto scrivere questo in qualsiasi ordine. 1033 00:45:21,630 --> 00:45:24,520 Ho solo pensato che tipo di feltro naturale di controllare prima di un possibile errore, 1034 00:45:24,520 --> 00:45:28,340 quindi controllare a sinistra, poi a destra controllare, quindi scontato che sei al nodo 1035 00:45:28,340 --> 00:45:30,630 si sta effettivamente cercando. 1036 00:45:30,630 --> 00:45:36,240 >> Allora, perché questo potrebbe essere utile? 1037 00:45:36,240 --> 00:45:37,910 Così si scopre - 1038 00:45:37,910 --> 00:45:42,110 e fammi saltare a un teaser qui che è nel web. 1039 00:45:42,110 --> 00:45:44,920 Stiamo per iniziare a utilizzare non una linguaggio di programmazione in un primo momento, ma una 1040 00:45:44,920 --> 00:45:46,030 linguaggio di markup. 1041 00:45:46,030 --> 00:45:48,740 Un linguaggio di marcatura di essere uno che è simile nello spirito alla programmazione 1042 00:45:48,740 --> 00:45:51,715 linguaggio, ma non dà la capacità di esprimere te stesso logicamente. 1043 00:45:51,715 --> 00:45:55,070 Ti dà solo la possibilità di esprimere se stessi strutturalmente. 1044 00:45:55,070 --> 00:45:57,960 >> Dove vuoi mettere qualcosa sulla pagina, la pagina web? 1045 00:45:57,960 --> 00:45:59,200 Di che colore vuoi farlo? 1046 00:45:59,200 --> 00:46:00,950 Che dimensione del carattere vuoi farlo? 1047 00:46:00,950 --> 00:46:02,970 Quali parole che effettivamente vuole sulla pagina web? 1048 00:46:02,970 --> 00:46:04,060 Ecco, questo è un linguaggio di markup. 1049 00:46:04,060 --> 00:46:07,690 Ma poi si introducono molto rapidamente JavaScript, che è un vero e proprio 1050 00:46:07,690 --> 00:46:08,560 linguaggio di programmazione. 1051 00:46:08,560 --> 00:46:12,530 Molto simile sintatticamente in apparenza a C, ma si avrà un po 'di 1052 00:46:12,530 --> 00:46:15,200 bella, più potente, più funzionalità user friendly. 1053 00:46:15,200 --> 00:46:18,050 >> E una delle frustrazioni in questa punto nel semestre è che faremo 1054 00:46:18,050 --> 00:46:22,065 presto implementare ortografico in molti meno righe di codice con altri linguaggi 1055 00:46:22,065 --> 00:46:25,580 di C si concede, ma per la ragione di che presto capiamo. 1056 00:46:25,580 --> 00:46:27,750 Questo sarà il primo di tali pagine web. 1057 00:46:27,750 --> 00:46:30,120 Sarà completamente deludente, il primo che facciamo. 1058 00:46:30,120 --> 00:46:31,400 Sarà semplicemente dire ciao mondo. 1059 00:46:31,400 --> 00:46:34,010 Ma se l'avete mai visto prima, questo è HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Se vai a una determinata opzione di menu in più qualsiasi browser, su qualsiasi pagina web su 1062 00:46:39,310 --> 00:46:43,160 Internet, è possibile vedere il codice HTML che alcune persone hanno scritto al 1063 00:46:43,160 --> 00:46:44,400 creare quella pagina web. 1064 00:46:44,400 --> 00:46:47,850 E probabilmente non sembra breve o come pulito come questo. 1065 00:46:47,850 --> 00:46:51,400 Ma sarà seguire il modello di questi parentesi aperte e le barre e 1066 00:46:51,400 --> 00:46:53,660 lettere e potenzialmente numeri. 1067 00:46:53,660 --> 00:46:56,770 >> Io ho pensato di dare un occhiolino di quello che sarete in grado di fare 1068 00:46:56,770 --> 00:46:57,950 dopo aver preso CS50. 1069 00:46:57,950 --> 00:47:02,620 Lasciami andare a cs.harvard.edu / rob, homepage il nostro Rob Bowden. 1070 00:47:02,620 --> 00:47:06,080 Ha fatto questo per noi. 1071 00:47:06,080 --> 00:47:07,490 Così sarete presto in grado di farlo. 1072 00:47:07,490 --> 00:47:10,660 E inoltre, cosa si sente questa mattina - 1073 00:47:10,660 --> 00:47:12,480 quello che hai sentito questa mattina - 1074 00:47:12,480 --> 00:47:13,780 >> [CRICETO DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - Avrete modo essere in grado di fare questo. 1076 00:47:15,702 --> 00:47:16,790 Che ci attende il Mercoledì. 1077 00:47:16,790 --> 00:47:17,791 Ci vediamo allora. 1078 00:47:17,791 --> 00:47:22,950 >> [CRICETO DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID MALAN: Al prossimo CS50 - 1080 00:47:24,300 --> 00:47:31,670