1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID MALAN: În regulă. 3 00:00:12,250 --> 00:00:13,860 Bine ati venit înapoi la CS50. 4 00:00:13,860 --> 00:00:16,190 Acesta este începutul săptămânii 8. 5 00:00:16,190 --> 00:00:21,320 Și amintesc că setul problema 5 încheiat cu un pic de o provocare. 6 00:00:21,320 --> 00:00:25,210 Deci, presupunând că ați recuperat toate de dvs. Fellows de predare și fotografii CA 7 00:00:25,210 --> 00:00:30,480 în fișierul card.raw, vă sunt eligibile pentru a găsi acum toate aceste persoane, și 8 00:00:30,480 --> 00:00:34,510 un câștigător norocos va pleca acasa cu unul de aceste lucruri, mișcarea salt 9 00:00:34,510 --> 00:00:37,450 dispozitiv pe care le puteți folosi pentru finală proiecte, de exemplu. 10 00:00:37,450 --> 00:00:39,860 >> Aceasta, în fiecare an, conduce la un pic de creepiness. 11 00:00:39,860 --> 00:00:43,480 Și deci ce m-am gândit face este cota cu voi unele dintre notele care au 12 00:00:43,480 --> 00:00:47,370 plecat înainte și înapoi peste lista personalului de întârziere. 13 00:00:47,370 --> 00:00:51,110 De exemplu, doar noaptea trecută, citat citatul, de la una din personalul 14 00:00:51,110 --> 00:00:55,000 membri, "am avut doar o bătaie elev la ușa mea pentru a face o fotografie cu mine. 15 00:00:55,000 --> 00:00:59,020 Stalkers, vă spun ", a început. destul de descriptiv și apoi ne-am mutat 16 00:00:59,020 --> 00:01:02,830 pe, o oră sau cam asa ceva mai târziu, "am avut o elev de așteptare pentru mine, după secțiunea 17 00:01:02,830 --> 00:01:06,080 și el a avut toate numele noastre și fotografii pe unele foi de hârtie. "În regulă. 18 00:01:06,080 --> 00:01:09,230 Deci organizat, dar nu tot ce înfiorător încă. 19 00:01:09,230 --> 00:01:12,520 >> Apoi, "am fost plecat din oras in acest weekend, și când m-am întors, era unul din 20 00:01:12,520 --> 00:01:12,630 meu 21 00:01:12,630 --> 00:01:16,740 dormitor. "[râsete] 22 00:01:16,740 --> 00:01:20,410 DAVID MALAN: Următorul citat dintr-un personal membru, "un elev a venit la casa mea de la 23 00:01:20,410 --> 00:01:25,330 Somerville la 4 dimineața asta. "Urmatorul personal, "am ajuns la hotel în San 24 00:01:25,330 --> 00:01:30,016 Francisco și un student a fost de așteptare pentru ma la lobby-ul cu trei DSLR. " 25 00:01:30,016 --> 00:01:31,510 Tip de aparat de fotografiat. 26 00:01:31,510 --> 00:01:34,980 "Eu nu sunt nici pe personal acest semestru, dar un elev a intrat în casa mea, această 27 00:01:34,980 --> 00:01:40,480 dimineață și a înregistrat totul cu Google sticlă "și apoi. în cele din urmă, 28 00:01:40,480 --> 00:01:43,650 "Cel puțin 12 de persoane au fost nerăbdare așteaptă pentru mine când am ieșit din mea 29 00:01:43,650 --> 00:01:44,800 limuzina, și apoi am 30 00:01:44,800 --> 00:01:46,970 sa trezit. "În regulă. 31 00:01:46,970 --> 00:01:57,690 Deci, printre fotografii, cum s-ar putea amintesc, sunt acest om aici, care te- 32 00:01:57,690 --> 00:02:01,850 s-ar putea, stiu ca Milo Banana, care locuiește cu Lauren Carvalho, capul nostru 33 00:02:01,850 --> 00:02:02,905 predare Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo Milo, vin aici băiete. 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 Țineți minte, el poartă Google Glass, așa vă vom arăta toate astea după. 38 00:02:12,230 --> 00:02:16,190 Deci, aceasta este Milo dacă doriți să să ia o fotografie cu el după aceea. 39 00:02:16,190 --> 00:02:18,240 Dacă doriți să se uite la publicul acolo. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Asta e filmarea bine. 42 00:02:20,200 --> 00:02:22,556 Ei bine, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, nu face asta. 44 00:02:23,941 --> 00:02:29,020 >> [Râsete] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Deci, un cuvânt, apoi pe ceea ce se află înainte, pentru că așa cum vom începe să tranziție, 47 00:02:34,550 --> 00:02:38,410 în această săptămână în mod specific, de la C, într-o Mediul linia de comandă a PHP și 48 00:02:38,410 --> 00:02:42,720 JavaScript si SQL si HTML și CSS în un mediu bazat pe web, vom fi 49 00:02:42,720 --> 00:02:44,490 echiparea vă cu toate mai multe cunoștințe pentru 50 00:02:44,490 --> 00:02:46,010 potențiale proiecte finale. 51 00:02:46,010 --> 00:02:49,240 Spre acest scop, cursul are o tradiție din organizarea de seminarii care 52 00:02:49,240 --> 00:02:50,950 sunt pe teme tangențiale la curs. 53 00:02:50,950 --> 00:02:54,330 Foarte mult legate de programare și de app de dezvoltare și așa mai departe, dar 54 00:02:54,330 --> 00:02:57,010 nu neapărat explorat de propria programa cursului. 55 00:02:57,010 --> 00:03:00,250 >> Deci, dacă ați putea fi interesat într-o singură sau mai mult de seminarii din acest an, 56 00:03:00,250 --> 00:03:02,530 înregistrați la cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Există seminarii mari la cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Și pe lista de până acum pentru acest an sunt Web Apps Amazing cu Ruby pe 59 00:03:10,620 --> 00:03:13,580 Șine, care este o alternativă Limba de PHP. 60 00:03:13,580 --> 00:03:14,900 Lingvistică Computațională. 61 00:03:14,900 --> 00:03:18,710 Introducere în iOS, care este platforma care este folosit pentru iPhone și 62 00:03:18,710 --> 00:03:19,850 dezvoltarea iPad. 63 00:03:19,850 --> 00:03:22,890 JavaScript pentru Web Apps, vom acoperi care, însă, în acest seminar, veti merge 64 00:03:22,890 --> 00:03:24,070 în mai multe detalii. 65 00:03:24,070 --> 00:03:27,390 >> Leap Motion, așa că vom avea de fapt, unele de prietenii nostri de la Leap Motion, 66 00:03:27,390 --> 00:03:29,160 compania in sine, ni se alature. 67 00:03:29,160 --> 00:03:31,800 Maine, de fapt, pentru a oferi un hands-on seminar, dacă 68 00:03:31,800 --> 00:03:33,320 de interes pentru tine. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, o tehnică alternativă pentru folosind JavaScript nu într-un browser, 70 00:03:38,770 --> 00:03:39,970 ci pe un server. 71 00:03:39,970 --> 00:03:42,110 Node.js, ceea ce este foarte mult în acest spirit, de asemenea. 72 00:03:42,110 --> 00:03:43,650 Elegant Android design. 73 00:03:43,650 --> 00:03:46,990 Android fiind o alternativă foarte populară pentru iOS și Windows Phone 74 00:03:46,990 --> 00:03:48,790 și alte platforme mobile. 75 00:03:48,790 --> 00:03:51,180 Și de securitate Web Active Defense. 76 00:03:51,180 --> 00:03:54,590 >> Deci, în fapt, dacă doriți să se angajeze în acest sens, permiteți-mi să 77 00:03:54,590 --> 00:03:55,840 face act de acest lucru. 78 00:03:55,840 --> 00:03:57,790 Suntem foarte fericiți să spun că prietenii nostri de la Leap 79 00:03:57,790 --> 00:03:59,140 Mișcare, care este o pornire - 80 00:03:59,140 --> 00:04:01,300 acest dispozitiv într-adevăr venit în urmă cu câteva luni - 81 00:04:01,300 --> 00:04:05,960 a donat gratie de 30 de astfel de dispozitive la clasa de cât mai mulți elevi, în cazul în care 82 00:04:05,960 --> 00:04:08,670 doriți să împrumute de hardware spre sfârșitul semestrului și-l utilizați pentru 83 00:04:08,670 --> 00:04:10,390 un proiect final efectiv. 84 00:04:10,390 --> 00:04:11,890 Ei sprijină un număr de limbi. 85 00:04:11,890 --> 00:04:16,040 Nici unul dintre ei C, nici unul dintre ei PHP, așa realiza una sau mai multe dintre aceste seminarii 86 00:04:16,040 --> 00:04:16,899 s-ar putea dovedi de interes. 87 00:04:16,899 --> 00:04:19,730 Și toate acestea vor fi filmate în cazul în care nu sunt în măsură 88 00:04:19,730 --> 00:04:21,380 pentru a participa în persoană. 89 00:04:21,380 --> 00:04:25,000 Programul fi anuntat prin e-mail ca am solidifica camere. 90 00:04:25,000 --> 00:04:28,460 >> Și, în fine, dacă te duci la projects.cs.50.net, acesta este un site web 91 00:04:28,460 --> 00:04:31,450 ne menține în fiecare an, pe care vă invităm oameni din comunitate, facultate, 92 00:04:31,450 --> 00:04:36,420 departamente, personal, și atât într-un exterior de la CS50 93 00:04:36,420 --> 00:04:37,730 propune idei de proiecte. 94 00:04:37,730 --> 00:04:39,050 Lucruri de interes pentru grupurile de studenți. 95 00:04:39,050 --> 00:04:40,600 Lucruri de interes pentru departamentele. 96 00:04:40,600 --> 00:04:43,990 Deci, nu întoarce acolo, dacă te lupți cu incertitudine cu privire la ceea ce 97 00:04:43,990 --> 00:04:46,700 te-ar dori să le rezolve. 98 00:04:46,700 --> 00:04:51,760 >> Deci, ultima dată când am introdus-o, fără îndoială, structura de date mai complex decât ne-am 99 00:04:51,760 --> 00:04:53,300 văzut în ultimele săptămâni. 100 00:04:53,300 --> 00:04:56,550 Am fost folosind tablouri destul de fericit ca un instrument util în cazul în care 101 00:04:56,550 --> 00:04:58,160 Structura de date simplist. 102 00:04:58,160 --> 00:05:00,570 Apoi am introdus acestea, care Desigur, sunt legate de liste. 103 00:05:00,570 --> 00:05:05,470 Și ceea ce a fost una dintre motivațiile pentru introducerea acestei structuri de date? 104 00:05:05,470 --> 00:05:06,930 Da? 105 00:05:06,930 --> 00:05:07,250 Ce-i asta? 106 00:05:07,250 --> 00:05:08,080 >> Audiența: dimensiunea dinamic. 107 00:05:08,080 --> 00:05:09,040 >> DAVID MALAN: dimensiunea dinamic. 108 00:05:09,040 --> 00:05:11,890 Deci, în timp ce în matrice, trebuie să știu dimensiunea sa, în avans, atunci când 109 00:05:11,890 --> 00:05:12,740 îl aloca. 110 00:05:12,740 --> 00:05:14,380 În lista de legat, tu nu faci Trebuie să știi că. 111 00:05:14,380 --> 00:05:17,610 Puteți doar malloc, sau, mai general, aloce o sumă suplimentară de 112 00:05:17,610 --> 00:05:20,720 nod, ca să spunem așa, în orice moment doriți să introduceți mai multe date. 113 00:05:20,720 --> 00:05:22,670 Și nodul nu are predeterminat sens. 114 00:05:22,670 --> 00:05:25,580 Este doar un termen generic care descrie un fel de container care suntem 115 00:05:25,580 --> 00:05:29,610 utilizarea în structura noastră de date pentru a stoca unele element de interes, care, în acest 116 00:05:29,610 --> 00:05:31,750 caz se întâmplă să fie întregi. 117 00:05:31,750 --> 00:05:33,160 >> Dar există întotdeauna un compromis. 118 00:05:33,160 --> 00:05:38,070 Așa că am obține dimensiuni dinamice de date structura, dar ce preț nu plătim? 119 00:05:38,070 --> 00:05:40,040 Care e dezavantajul de liste legate? 120 00:05:40,040 --> 00:05:41,006 Da? 121 00:05:41,006 --> 00:05:41,980 >> Audiența: necesită mai multă memorie. 122 00:05:41,980 --> 00:05:44,240 >> DAVID MALAN: Este nevoie de mai mult memorie, cum anume? 123 00:05:44,240 --> 00:05:46,440 >> Audiența: [inaudibil]. 124 00:05:46,440 --> 00:05:47,050 >> David MALAN: Exact. 125 00:05:47,050 --> 00:05:50,460 Deci, acum ne-am indicii inițierea memorie suplimentară pe care le anterior 126 00:05:50,460 --> 00:05:53,040 nu au nevoie, pentru că avantajul dintr-o serie, desigur, este faptul că 127 00:05:53,040 --> 00:05:54,860 totul e învecinate, înapoi la spate în spate, care 128 00:05:54,860 --> 00:05:56,380 vă oferă acces aleator. 129 00:05:56,380 --> 00:06:00,710 Pentru că doar prin utilizarea paranteză notație, sau mai multe punct de vedere tehnic indicatorul 130 00:06:00,710 --> 00:06:03,580 aritmetică, plus foarte simplu, puteți accesa orice 131 00:06:03,580 --> 00:06:05,700 elemente în timp constant. 132 00:06:05,700 --> 00:06:08,975 Și, de fapt, asta e un fel de aluzie la un alt pret pe care le plătim cu o 133 00:06:08,975 --> 00:06:09,760 Lista legate. 134 00:06:09,760 --> 00:06:13,890 >> Ce se întâmplă în timpul de funcționare a ceva de genul căutare, dacă vreau să 135 00:06:13,890 --> 00:06:17,270 găsi o anumită valoare și în interior a unei liste legate? 136 00:06:17,270 --> 00:06:20,290 Ce devine timpul de funcționare? 137 00:06:20,290 --> 00:06:21,560 O mare de n. 138 00:06:21,560 --> 00:06:24,060 Dacă este sortate? 139 00:06:24,060 --> 00:06:25,440 Ce se întâmplă dacă structura de date este sortat? 140 00:06:25,440 --> 00:06:28,640 Pot face mai bine decât mare O a n pentru căutare? 141 00:06:28,640 --> 00:06:31,700 Nu, pentru că în cel mai rău caz, s-ar putea foarte bine fi sortate, dar numărul 142 00:06:31,700 --> 00:06:32,950 sunteți în căutarea pentru a putea fi mare. 143 00:06:32,950 --> 00:06:35,370 Acesta ar putea fi numărul 100, care s-ar putea întâmpla să fie 144 00:06:35,370 --> 00:06:36,410 fel, la sfârșitul. 145 00:06:36,410 --> 00:06:39,950 Și pentru că puteți accesa doar un legat lista în această punere în aplicare de către 146 00:06:39,950 --> 00:06:42,690 mod de primul nod, ai încă un fel de noroc. 147 00:06:42,690 --> 00:06:47,450 Trebuie să traverseze totul de la început până la sfârșit, în scopul de a găsi 148 00:06:47,450 --> 00:06:49,150 că valoarea mare ca 100. 149 00:06:49,150 --> 00:06:51,350 Sau pentru a determina dacă este nici acolo. 150 00:06:51,350 --> 00:06:55,960 >> Deci, noi nu putem face ceea ce algoritm într-un datelor structura care arata ca aceasta? 151 00:06:55,960 --> 00:06:59,460 Noi nu putem face căutare binară, deoarece binar de căutare necesar pe care am avut 152 00:06:59,460 --> 00:07:00,740 acces aleator. 153 00:07:00,740 --> 00:07:04,500 Am putea sări doar de la locație la locație, fără a fi nevoie să urmeze 154 00:07:04,500 --> 00:07:07,080 aceste firimituri de pâine în formă din toate aceste indicii. 155 00:07:07,080 --> 00:07:08,300 >> Acum, cum am pune în aplicare acest lucru? 156 00:07:08,300 --> 00:07:12,830 Ei bine, dacă vom merge la ecranul aici, în cazul în care putem reimplementa rapid aceste date 157 00:07:12,830 --> 00:07:13,440 Structura - 158 00:07:13,440 --> 00:07:15,670 scrisul meu nu e tot ce mare aici, dar vom încerca. 159 00:07:15,670 --> 00:07:22,030 Struct astfel typedef, și ce am Vreau să numesc chestia asta aici? 160 00:07:22,030 --> 00:07:22,960 Nod. 161 00:07:22,960 --> 00:07:24,580 Deci ne intalnim început. 162 00:07:24,580 --> 00:07:27,860 Și acum, ceea ce trebuie să fie în interiorul structura de date pentru că individual 163 00:07:27,860 --> 00:07:28,430 Lista legat? 164 00:07:28,430 --> 00:07:29,950 Cât de multe domenii? 165 00:07:29,950 --> 00:07:30,450 >> Deci doi. 166 00:07:30,450 --> 00:07:31,570 Una dintre ele este destul de ușor. 167 00:07:31,570 --> 00:07:33,050 Deci, int n. 168 00:07:33,050 --> 00:07:35,930 Și am putea numi n orice ne dorim, dar ar trebui să fie un întreg, dacă suntem 169 00:07:35,930 --> 00:07:37,660 punerea în aplicare a unei liste legate de int. 170 00:07:37,660 --> 00:07:41,920 Și acum ce face a doua câmp trebuie să fie? 171 00:07:41,920 --> 00:07:43,460 Struct nod *. 172 00:07:43,460 --> 00:07:50,570 Deci, dacă am face struct nod *, și apoi am pot apela, de asemenea, acest lucru ce vreau eu, 173 00:07:50,570 --> 00:07:53,510 dar doar pentru a fi clar chem o viitoare, așa cum am făcut. 174 00:07:53,510 --> 00:07:55,270 Și apoi voi închide bretele mele buclat. 175 00:07:55,270 --> 00:08:00,700 >> Și acum, ca și data trecută, Am pus nodul aici. 176 00:08:00,700 --> 00:08:03,830 Dar dacă am declarat acest lucru este ca un nod, de ce am deranjat fiind atât de 177 00:08:03,830 --> 00:08:07,320 verbose aici, în struct declararea nod * viitor, spre deosebire de 178 00:08:07,320 --> 00:08:09,210 la doar nod * viitor? 179 00:08:09,210 --> 00:08:09,904 Da? 180 00:08:09,904 --> 00:08:12,810 >> Audiența: [inaudibil]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID MALAN: Exact. 182 00:08:14,050 --> 00:08:14,530 Exact. 183 00:08:14,530 --> 00:08:18,320 Deoarece C într-adevăr te duce literalmente și vede numai definiția nodului 184 00:08:18,320 --> 00:08:21,230 până aici, nu se poate consultați-l aici. 185 00:08:21,230 --> 00:08:24,760 Deci avem acest tip de preemptive declarația de aici, care este, desigur, 186 00:08:24,760 --> 00:08:25,390 mai detaliată. 187 00:08:25,390 --> 00:08:27,810 Struct nod, ceea ce înseamnă putem accesa acum 188 00:08:27,810 --> 00:08:29,760 interiorul structurii de date. 189 00:08:29,760 --> 00:08:33,370 >> Și, ca o paranteză, pentru că acest lucru este devenind un pic mai mult subiectiv acum, 190 00:08:33,370 --> 00:08:36,230 stele poate merge tehnic aici, se poate merge aici, se poate 191 00:08:36,230 --> 00:08:37,179 chiar du-te în mijloc. 192 00:08:37,179 --> 00:08:39,890 Am adoptat, în ghidul de stil pentru Desigur, Convenția de punere 193 00:08:39,890 --> 00:08:42,299 stele, în imediata vecinătate a datelor tip, care în acest caz, 194 00:08:42,299 --> 00:08:43,460 ar fi nod struct. 195 00:08:43,460 --> 00:08:46,620 Dar realiza într-o mulțime de manuale și referințe on-line, s-ar putea într-adevăr 196 00:08:46,620 --> 00:08:48,450 vezi-l pe partea cealaltă. 197 00:08:48,450 --> 00:08:52,200 Dar doar dau seama că ambele vor de fapt locul de muncă și ar trebui să fie pur și simplu 198 00:08:52,200 --> 00:08:52,970 consistent. 199 00:08:52,970 --> 00:08:53,580 >> Bine. 200 00:08:53,580 --> 00:08:55,630 Astfel că a fost declarația noastră de nod struct. 201 00:08:55,630 --> 00:08:59,430 Dar apoi am început să facem mai mult lucruri sofisticate. 202 00:08:59,430 --> 00:09:03,410 De exemplu, am decis să introducă ceva ca un tabel hash. 203 00:09:03,410 --> 00:09:08,160 Deci, aici este un tabel hash de dimensiune N, indexate de la 0 la stânga sus la n 204 00:09:08,160 --> 00:09:09,690 minus 1 în partea de jos stânga. 205 00:09:09,690 --> 00:09:11,640 Acest lucru ar putea fi un hash de masă pentru nimic. 206 00:09:11,640 --> 00:09:15,340 Dar ce fel de lucruri am vorbit despre utilizarea unui tabel hash pentru? 207 00:09:15,340 --> 00:09:18,370 Depozitarea ce? 208 00:09:18,370 --> 00:09:18,800 >> Nume. 209 00:09:18,800 --> 00:09:20,870 Am putea face nume ca am făcut data trecută. 210 00:09:20,870 --> 00:09:22,200 Și într-adevăr, puteți stoca nimic. 211 00:09:22,200 --> 00:09:24,640 Și vom vedea acest lucru din nou în PHP și JavaScript. 212 00:09:24,640 --> 00:09:28,550 Un tabel hash este un fel frumos de Elvețiană Armata cuțit care vă permite să stocați 213 00:09:28,550 --> 00:09:33,690 destul de mult tot ce vrei interiorul prin asocierea tastelor cu valori. 214 00:09:33,690 --> 00:09:34,770 Taste cu valori. 215 00:09:34,770 --> 00:09:37,800 >> Acum, în acest caz simplu, nostru Tastele sunt doar numere. 216 00:09:37,800 --> 00:09:40,380 Suntem implementarea unui hash masă ca o matrice. 217 00:09:40,380 --> 00:09:43,500 Și așa tastele sunt 0, 1, 2, și așa mai departe. 218 00:09:43,500 --> 00:09:47,200 Și astfel noi, ca oameni, a decis ultimul săptămână, că știți ce, dacă suntem 219 00:09:47,200 --> 00:09:50,410 merge la numele magazinului, hai să arbitrar, dar destul de rezonabil, 220 00:09:50,410 --> 00:09:54,680 presupune că Alice, un nume A, va fi doar indexat în 0. 221 00:09:54,680 --> 00:09:58,030 Și Bob, un nume B, vor fi indexate în 1, și așa mai departe. 222 00:09:58,030 --> 00:10:02,490 Așa că am avut o cartografiere între intrări, care sunt șiruri, iar distribuire 223 00:10:02,490 --> 00:10:04,560 depozite, care sunt numere. 224 00:10:04,560 --> 00:10:07,740 >> Astfel că procesul este, în general, cunoscut sub numele de o funcție hash, și puteți cu adevărat 225 00:10:07,740 --> 00:10:09,130 l pună în aplicare în cod. 226 00:10:09,130 --> 00:10:12,080 Dacă aș fi vrut să pună în aplicare o funcție hash care face exact ceea ce am 227 00:10:12,080 --> 00:10:17,070 doar descris la ultima oară, am putea declară o funcție care are, ca 228 00:10:17,070 --> 00:10:18,330 intrare, de exemplu - 229 00:10:18,330 --> 00:10:22,190 și să facă acest lucru pe acest Ecranul aici. 230 00:10:22,190 --> 00:10:26,180 Dacă aș fi vrut să pună în aplicare un hash funcție, am putea spune 231 00:10:26,180 --> 00:10:27,410 ceva de genul asta. 232 00:10:27,410 --> 00:10:29,030 >> O să se întoarcă un int. 233 00:10:29,030 --> 00:10:33,600 Acesta va fi numit hash, și este va accepta ca un argument de 234 00:10:33,600 --> 00:10:38,920 șir, sau putem fi mult mai buna acum, și spune char *, vom e numesc. 235 00:10:38,920 --> 00:10:43,840 Și apoi toate această funcție are de a face, în cele din urmă, se întoarce un întreg. 236 00:10:43,840 --> 00:10:45,990 Acum, cum se face că s-ar putea Nu fi atât de clar. 237 00:10:45,990 --> 00:10:49,510 Am de gând să pună în aplicare acest lucru fără nici o forma de verificarea erorilor chiar acum. 238 00:10:49,510 --> 00:10:55,740 Mă duc să spun orbește, întoarce tot ce este la s suport 0, minus, 239 00:10:55,740 --> 00:10:58,850 să spunem, capitala punct și virgulă. 240 00:10:58,850 --> 00:10:59,960 >> Complet rupt. 241 00:10:59,960 --> 00:11:02,620 Nu e perfect, deoarece unul, ceea ce în cazul în care s este nul? 242 00:11:02,620 --> 00:11:04,000 Lucruri rele se va întâmpla. 243 00:11:04,000 --> 00:11:07,940 Doi, ceea ce în cazul în care prima literă din acest Numele nu este o scrisoare de capital? 244 00:11:07,940 --> 00:11:09,860 Asta nu se va transforma în bine, fie. 245 00:11:09,860 --> 00:11:11,970 Ar putea fi o literă mică sau nu o scrisoare la toate. 246 00:11:11,970 --> 00:11:15,520 Deci, în totalitate loc de îmbunătățiri aici, dar aceasta este ideea de bază. 247 00:11:15,520 --> 00:11:19,010 >> Ceea ce am descris săptămâna trecută verbal ca doar un proces de cartografiere Alice a 248 00:11:19,010 --> 00:11:23,360 0 și Bob să 1 pot fi exprimate cu siguranță mai mult formulaically ca un C 249 00:11:23,360 --> 00:11:24,320 funcționa aici. 250 00:11:24,320 --> 00:11:28,630 Chemat din nou hash, are un șir ca intrare, și apoi într-un fel face ceva 251 00:11:28,630 --> 00:11:31,020 cu care de intrare pentru a produce o ieșire. 252 00:11:31,020 --> 00:11:34,130 Nu spre deosebire de nostru Descrierea cutie neagră pe care le-am facut de mult. 253 00:11:34,130 --> 00:11:36,550 Nu știu cum acest lucru ar putea fi lucru sub capota. 254 00:11:36,550 --> 00:11:40,120 >> Pentru set de probleme 6, una dintre provocările este pentru tine de a decide ce 255 00:11:40,120 --> 00:11:41,920 va fi funcția hash? 256 00:11:41,920 --> 00:11:45,760 Ce va fi in interiorul de care negru cutie, și probabil, va fi un 257 00:11:45,760 --> 00:11:50,380 mai interesant decât acest lucru, și cu siguranta mai predispuse la erori 258 00:11:50,380 --> 00:11:53,180 verificarea decât această special punere în aplicare. 259 00:11:53,180 --> 00:11:54,580 >> Dar pot apărea probleme, nu? 260 00:11:54,580 --> 00:11:57,760 Dacă avem o structură de date, cum ar fi acest unul, ceea ce este una din problemele 261 00:11:57,760 --> 00:12:01,600 puteți rula în timp ce vă introduceți mai multe și mai multe nume în 262 00:12:01,600 --> 00:12:02,880 tabela de dispersie? 263 00:12:02,880 --> 00:12:04,630 Ai coliziuni, corect? 264 00:12:04,630 --> 00:12:07,560 Ce se întâmplă dacă aveți Alice și Aaron, doi oameni ale căror nume sa întâmplat 265 00:12:07,560 --> 00:12:08,190 pentru a începe cu A? 266 00:12:08,190 --> 00:12:11,660 Care duce la intrebarea, unde pune de-al doilea astfel de nume? 267 00:12:11,660 --> 00:12:15,050 >> Ei bine, s-ar putea naivitate doar pune-l unde Bob face parte, dar apoi Bob este 268 00:12:15,050 --> 00:12:17,300 fel de înșurubat dacă încercați să inserați numele său viitor și 269 00:12:17,300 --> 00:12:18,240 nu e loc pentru el. 270 00:12:18,240 --> 00:12:21,400 Deci, s-ar putea pune Bob unde este Charlie, și vă puteți imagina acest lucru foarte repede 271 00:12:21,400 --> 00:12:23,020 descentralizarea într-un pic de mizerie. 272 00:12:23,020 --> 00:12:25,600 Ceva liniar, în cele din urmă, în cazul în care trebuie doar să caute totul 273 00:12:25,600 --> 00:12:28,190 în căutarea de Alice sau Bob sau Aaron sau Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Deci, în loc ne-am propus, în loc de doar liniar de sondare pentru spatii deschise 275 00:12:33,230 --> 00:12:36,450 și plopping numele acolo, ne- a propus o abordare crescator. 276 00:12:36,450 --> 00:12:41,740 Un tabel hash implementat încă cu o serie de indici, dar tipul de date de 277 00:12:41,740 --> 00:12:44,500 aceste indicii au fost acum indicii. 278 00:12:44,500 --> 00:12:47,360 Trimiteri la ce? 279 00:12:47,360 --> 00:12:48,730 Trimiteri la liste legate. 280 00:12:48,730 --> 00:12:53,330 >> Deoarece amintesc că o listă de legat este într-adevăr doar un pointer la un nod, și 281 00:12:53,330 --> 00:12:57,110 nod are un câmp de lângă, și că nodul are un câmp viitoare, și așa mai departe. 282 00:12:57,110 --> 00:13:00,690 Deci, vă puteți gândi acum de această matrice pe în partea din stânga a unui tabel hash ca 283 00:13:00,690 --> 00:13:01,820 ceea ce duce la o listă legată. 284 00:13:01,820 --> 00:13:07,000 Avantajul de care este dacă aveți un coliziune între Alice și Aaron, 285 00:13:07,000 --> 00:13:09,300 ce faci cu doua astfel de persoană? 286 00:13:09,300 --> 00:13:14,150 Atașați doar el sau ea pentru a scop, sau chiar la începutul 287 00:13:14,150 --> 00:13:15,490 din această listă legat. 288 00:13:15,490 --> 00:13:17,340 >> Și, de fapt, hai să Noodle prin că pentru doar o secundă. 289 00:13:17,340 --> 00:13:18,640 În cazul în care ar face mai mult sens? 290 00:13:18,640 --> 00:13:22,060 Dacă am introduce Alice și ea sfârșește la prima locatie, apoi încerc să 291 00:13:22,060 --> 00:13:25,310 inserați numele lui Aaron, și nu e în mod evident o coliziune, ar trebui să pună 292 00:13:25,310 --> 00:13:27,400 el la început listei legate? 293 00:13:27,400 --> 00:13:30,944 Asta e de la acea prima locație, sau la sfârșit? 294 00:13:30,944 --> 00:13:31,440 >> Audiența: [inaudibil]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID MALAN: OK. 296 00:13:31,990 --> 00:13:32,490 Am auzit început. 297 00:13:32,490 --> 00:13:33,903 De ce de la început? 298 00:13:33,903 --> 00:13:34,750 >> Audiența: [inaudibil]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID MALAN: OK. 300 00:13:34,940 --> 00:13:36,520 Este alfabetică, astfel că e frumos. 301 00:13:36,520 --> 00:13:37,330 Aceasta este o proprietate bun. 302 00:13:37,330 --> 00:13:39,335 Îmi va economisi ceva timp potențial. 303 00:13:39,335 --> 00:13:43,290 Nu va lasa-ma sa fac binar de căutare, dar eu ar putea fi capabil de a izbucni cel puțin 304 00:13:43,290 --> 00:13:47,340 de o buclă, dacă îmi dau seama, ei bine, eu sunt calea trecut au fost Aaron ar fi în acest 305 00:13:47,340 --> 00:13:48,310 sortat listă înlănțuită. 306 00:13:48,310 --> 00:13:50,360 Nu am să-mi pierd timpul în căutarea tot drumul până la sfârșit. 307 00:13:50,360 --> 00:13:51,530 Așa că e rezonabil. 308 00:13:51,530 --> 00:13:54,710 De ce altceva ar putea să doriți să inserați denumirea coliziunea 309 00:13:54,710 --> 00:13:56,660 începutul listei? 310 00:13:56,660 --> 00:13:57,397 Ce-i asta? 311 00:13:57,397 --> 00:13:58,680 >> Audiența: [inaudibil]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID MALAN: S-ar putea lua o lungă perioadă de timp pentru a ajunge la sfârșitul listei. 313 00:14:00,820 --> 00:14:02,490 Și, de fapt, mai mult și mai mult. 314 00:14:02,490 --> 00:14:04,920 Cele mai multe nume pe care le introduce acest începe cu A, cu atât mai mult că 315 00:14:04,920 --> 00:14:06,280 lanț este mergi la a lua. 316 00:14:06,280 --> 00:14:07,890 Mai mult ca legate Lista este mergi la a lua. 317 00:14:07,890 --> 00:14:09,420 Deci, tu ești cu adevărat doar pierzi timpul. 318 00:14:09,420 --> 00:14:14,070 Poate că e mai bine menținerea timp de inserare constant, Big O de 1, 319 00:14:14,070 --> 00:14:18,470 de a pune întotdeauna numele coliziune la la începutul listei legate, 320 00:14:18,470 --> 00:14:21,230 și nu îngrijorătoare la fel de mult de sortare. 321 00:14:21,230 --> 00:14:22,600 >> Care este cel mai bun răspuns? 322 00:14:22,600 --> 00:14:23,320 Este neclar. 323 00:14:23,320 --> 00:14:26,140 Este un fel de depinde de ceea ce distribuție este, ce model este 324 00:14:26,140 --> 00:14:27,850 de numele pe care îl inserați. 325 00:14:27,850 --> 00:14:29,430 Nu este necesar un răspuns evident. 326 00:14:29,430 --> 00:14:33,100 Dar aici sa, din nou, este o oportunitate de design. 327 00:14:33,100 --> 00:14:37,220 >> Așa că am apoi se uită la acest lucru, care este într-adevăr altă mare oportunitate 328 00:14:37,220 --> 00:14:38,180 pentru p-set 6. 329 00:14:38,180 --> 00:14:41,770 Și să realizeze, dacă nu ați făcut deja, Scufundă Zamyla în ambele, hash 330 00:14:41,770 --> 00:14:43,260 tabele și încearcă, mai în detaliu. 331 00:14:43,260 --> 00:14:45,630 Și walkthrough video este încorporate în p-set spec.. 332 00:14:45,630 --> 00:14:46,590 Acest lucru a fost un trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. Și ceea ce a fost interesant despre acest lucru a fost faptul că timpul de execuție 334 00:14:51,670 --> 00:14:59,510 de a căuta un nume, cum ar fi Maxwell ultima dată, a fost Big O de ce? 335 00:14:59,510 --> 00:15:01,040 Ce-i asta? 336 00:15:01,040 --> 00:15:01,920 >> Audiența: numărul de litere. 337 00:15:01,920 --> 00:15:02,550 >> DAVID MALAN: numărul de litere. 338 00:15:02,550 --> 00:15:03,210 Am auzit două lucruri. 339 00:15:03,210 --> 00:15:04,630 Numărul de litere și de constanta de timp. 340 00:15:04,630 --> 00:15:05,540 Deci, haideți să mergem cu primul. 341 00:15:05,540 --> 00:15:06,410 Numărul de litere. 342 00:15:06,410 --> 00:15:10,195 Ei bine, această structură de date, amintesc, este ca un copac, un copac de familie, fiecare dintre 343 00:15:10,195 --> 00:15:12,860 noduri ale caror sunt formate din matrice. 344 00:15:12,860 --> 00:15:16,300 Și aceste matrice sunt indicii pentru alte astfel de noduri, sau alte astfel de 345 00:15:16,300 --> 00:15:17,670 matrice în copac. 346 00:15:17,670 --> 00:15:22,890 >> Deci, dacă am vrut pentru a determina, atunci dacă Maxwell este aici, s-ar putea merge 347 00:15:22,890 --> 00:15:26,890 la prima matrice, la foarte de sus a copac, așa-numitul rădăcină, partea de sus a 348 00:15:26,890 --> 00:15:30,521 trie, și apoi urmați indicatorul m, apoi un indicator, atunci x, 349 00:15:30,521 --> 00:15:31,710 W, E, L, L. 350 00:15:31,710 --> 00:15:34,910 Și apoi, când am vedea unele simbol special, notate aici ca un triunghi. 351 00:15:34,910 --> 00:15:38,480 În cod, veți vedea ne-am propus să implementat ca un bool, doar spune da 352 00:15:38,480 --> 00:15:40,540 sau nu, un cuvânt se oprește aici. 353 00:15:40,540 --> 00:15:45,270 >> Ei bine, odată ce ne-am dus la M-A-X-W-E-L-L, se simte ca șapte, poate 354 00:15:45,270 --> 00:15:48,910 opt dacă vom merge cu un trecut, opt pași pentru a găsi Maxwell. 355 00:15:48,910 --> 00:15:53,050 Sau să-l K. apel, dar amintesc ultima timp, am susținut că în cazul în care nu există 356 00:15:53,050 --> 00:15:57,540 realist o lungime maximă pe o cuvânt, cum ar fi caractere de 40-unele de ciudat, un 357 00:15:57,540 --> 00:16:00,810 lungimea maximă implică o valoare constantă. 358 00:16:00,810 --> 00:16:05,770 Deci, într-adevăr, da, este punct de vedere tehnic mare O de 8 sau 7, sau într-adevăr mare, O, de K. Dar, 359 00:16:05,770 --> 00:16:09,420 în cazul în care există un plafon finit pe care K ar putea fi, este o constantă. 360 00:16:09,420 --> 00:16:12,080 Și așa este mare O a 1 la sfârșitul zilei. 361 00:16:12,080 --> 00:16:13,040 >> Nu în lumea reală. 362 00:16:13,040 --> 00:16:15,960 Nu atunci când începe de fapt, vizionarea ceas ca de funcționare programul dumneavoastră. 363 00:16:15,960 --> 00:16:20,690 Este absolut va fi un pic lent decât adevărat constantă 364 00:16:20,690 --> 00:16:21,840 timp cu un pas. 365 00:16:21,840 --> 00:16:25,540 O să fie șapte sau opt trepte, dar asta e mult, mult mai bine 366 00:16:25,540 --> 00:16:30,080 decât un algoritm ca mare O, de n care depinde de dimensiunea a ceea ce este în 367 00:16:30,080 --> 00:16:31,220 structură de date. 368 00:16:31,220 --> 00:16:34,970 >> Observați susul aici este să putem introduce un milion de nume mai mult în acest 369 00:16:34,970 --> 00:16:38,170 structura de date, dar cât de mult mai multe trepte este de gând să ne ia pentru a găsi 370 00:16:38,170 --> 00:16:40,480 Maxwell în acest caz? 371 00:16:40,480 --> 00:16:40,780 Nici unul. 372 00:16:40,780 --> 00:16:41,820 El e afectat. 373 00:16:41,820 --> 00:16:45,480 Și până în prezent, eu nu cred că l-am văzut un exemplu al unei structuri de date sau o 374 00:16:45,480 --> 00:16:48,560 algoritm care a fost complet neafectat de extern 375 00:16:48,560 --> 00:16:50,040 comportamente de genul asta. 376 00:16:50,040 --> 00:16:51,160 Dar acest lucru nu poate fi uimitor. 377 00:16:51,160 --> 00:16:52,900 Acest lucru nu poate fi singura soluție pentru p-set 378 00:16:52,900 --> 00:16:53,570 >> Și nu este. 379 00:16:53,570 --> 00:16:55,980 Acest lucru nu este neapărat de date Structura ar trebui sa ajunga, 380 00:16:55,980 --> 00:16:58,220 pentru ca tabele de dispersie, compromis. 381 00:16:58,220 --> 00:17:00,500 Care este prețul pe care îl plătiți aici? 382 00:17:00,500 --> 00:17:00,940 Memorie. 383 00:17:00,940 --> 00:17:02,890 Vreau să spun, aceasta este o atroce cantitate de memorie. 384 00:17:02,890 --> 00:17:05,569 Și nu se poate vedea destul de aici, deoarece autorul de această imagine 385 00:17:05,569 --> 00:17:09,420 evident trunchiat toate matrice, și nu vedem o mulțime de A și 386 00:17:09,420 --> 00:17:12,700 Lui B și lui C și a lui Q și lui Y și a lui Z in aceste tablouri. 387 00:17:12,700 --> 00:17:13,630 Dar ei sunt acolo. 388 00:17:13,630 --> 00:17:17,660 >> Fiecare dintre aceste noduri este o gamă întreagă de circa 26 sau mai mulți octeți, fiecare dintre 389 00:17:17,660 --> 00:17:19,170 ceea ce reprezintă o scrisoare. 390 00:17:19,170 --> 00:17:22,920 27, în cazul nostru, astfel încât să putem sprijini Apostrofuri în setul problema. 391 00:17:22,920 --> 00:17:27,030 Deci, această structură de date este într-adevăr, foarte dens și larg. 392 00:17:27,030 --> 00:17:30,880 Și că numai ar putea ajunge încetinirea lucrurile jos, sau cel puțin vă costă un 393 00:17:30,880 --> 00:17:32,240 mult mai mult spațiu. 394 00:17:32,240 --> 00:17:34,020 Dar, din nou, se pot trage comparații aici. 395 00:17:34,020 --> 00:17:39,190 >> Amintiți-o înapoi în timp, am realizat mult timp mai interesant de funcționare în sortarea 396 00:17:39,190 --> 00:17:42,880 atunci când vom folosi îmbinare fel, dar prețul am plătit pentru a realiza n log n pentru îmbinare 397 00:17:42,880 --> 00:17:46,930 un fel necesar pe care ne petrecem mai mult ce resurse? 398 00:17:46,930 --> 00:17:47,690 Mai mult spațiu. 399 00:17:47,690 --> 00:17:50,530 Am nevoie de o gamă secundară a copia persoane în, la fel ca 400 00:17:50,530 --> 00:17:51,620 am făcut aici, pe scenă. 401 00:17:51,620 --> 00:17:55,880 Deci, din nou, există câștigători clare, ci doar de design subiectiv 402 00:17:55,880 --> 00:17:57,710 deciziile să fie luate. 403 00:17:57,710 --> 00:17:58,060 >> Bine. 404 00:17:58,060 --> 00:17:59,130 Deci, ce zici de asta? 405 00:17:59,130 --> 00:18:02,050 Oricine recunoaște pe care D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Deci, trei dintre noi. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Deci, aceasta este pentru a lua masa Mather. 410 00:18:05,070 --> 00:18:09,650 Pun pariu ca toate sălile de mese au stive de tăvi de genul asta. 411 00:18:09,650 --> 00:18:11,950 Și aceasta este de fapt reprezentant de ceva ce am 412 00:18:11,950 --> 00:18:13,050 evident, văzut deja. 413 00:18:13,050 --> 00:18:14,850 L-am numit pur și simplu o stivă. 414 00:18:14,850 --> 00:18:18,970 Și stivă, în termeni de ta memoria calculatorului, este în cazul în care datele se 415 00:18:18,970 --> 00:18:20,460 în timp ce funcțiile sunt numite. 416 00:18:20,460 --> 00:18:23,410 >> De exemplu, ce fel de lucruri merg pe stiva în ceea ce privește 417 00:18:23,410 --> 00:18:27,420 layout-ul de memorie care le-am discutat în ultimele săptămâni? 418 00:18:27,420 --> 00:18:28,736 Ce-i asta? 419 00:18:28,736 --> 00:18:29,670 >> Audiența: Apeluri la funcții. 420 00:18:29,670 --> 00:18:30,260 >> DAVID MALAN: Îmi pare rău. 421 00:18:30,260 --> 00:18:31,210 >> Audiența: Apeluri la funcții. 422 00:18:31,210 --> 00:18:33,590 >> DAVID MALAN: Apeluri la funcții, dar în mod special, ceea ce este în interiorul fiecăruia dintre 423 00:18:33,590 --> 00:18:35,340 aceste cadre? 424 00:18:35,340 --> 00:18:37,220 Ce fel de lucruri? 425 00:18:37,220 --> 00:18:37,460 Da. 426 00:18:37,460 --> 00:18:38,500 Deci variabilele locale. 427 00:18:38,500 --> 00:18:43,080 Ori de câte ori am nevoie de unele de stocare locale, ca un argument, sau int i, sau Int 428 00:18:43,080 --> 00:18:45,940 temp, sau orice altceva locale variabilă este, am fost 429 00:18:45,940 --> 00:18:47,210 pune că pe stiva. 430 00:18:47,210 --> 00:18:49,610 Și am o stiva de apel, deoarece de ideea stratificare. 431 00:18:49,610 --> 00:18:52,940 Doar un fel de meciuri cu realitatea, conceptul acestuia. 432 00:18:52,940 --> 00:18:56,650 >> Dar se pare că o stivă poate, de asemenea, fi văzută ca o structură de date, o 433 00:18:56,650 --> 00:19:00,110 alternativă la o matrice, o alternativă la o listă legată. 434 00:19:00,110 --> 00:19:02,770 Ceva conceptual mai interesant care pot fi în continuare 435 00:19:02,770 --> 00:19:06,030 implementate folosind oricare dintre aceste lucruri, dar e un alt tip de 436 00:19:06,030 --> 00:19:09,140 structura de date de sprijin, într-adevăr, doar două operațiuni. 437 00:19:09,140 --> 00:19:11,000 Dar puteți adăuga la crescătorul caracteristici decât acestea. 438 00:19:11,000 --> 00:19:12,180 Dar acestea sunt elementele de bază - 439 00:19:12,180 --> 00:19:13,510 împinge și pop. 440 00:19:13,510 --> 00:19:19,240 >> Iar ideea cu un stack este că, dacă am au aici, cu sau fără Annenberg 441 00:19:19,240 --> 00:19:22,880 știind, o tavă de lângă ușă cu numărul 9 pe ea. 442 00:19:22,880 --> 00:19:23,870 Deci, doar un Int. 443 00:19:23,870 --> 00:19:26,990 Și vreau să împingă acest pe date structura, care în prezent este gol. 444 00:19:26,990 --> 00:19:28,790 Considera acest jos a stivei. 445 00:19:28,790 --> 00:19:33,150 Mi-ar împinge acest număr de 9 pe stivă, iar acum e chiar acolo. 446 00:19:33,150 --> 00:19:36,040 >> Dar cel mai interesant lucru despre o stivă este că dacă acum vreau să împingă 447 00:19:36,040 --> 00:19:40,210 o alta valoare, cum ar fi 17, și am împinge aceasta pe stiva, am de gând să fac 448 00:19:40,210 --> 00:19:43,290 singurul lucru intuitiv, Mă duc să-l pune chiar în cazul în care noi, oamenii, 449 00:19:43,290 --> 00:19:45,180 ar fi înclinați să-l pună, pe partea de sus. 450 00:19:45,180 --> 00:19:48,850 Dar ceea ce este interesant acum este, cum pot obține de la 9? 451 00:19:48,850 --> 00:19:50,670 Știi, eu nu fără un efort. 452 00:19:50,670 --> 00:19:54,070 >> Deci, ceea ce este interesant despre o stivă este că de proiectare, 453 00:19:54,070 --> 00:19:56,330 este o structură de date LIFO. 454 00:19:56,330 --> 00:19:59,680 Mod prostesc de a descrie ultimul, primul plecat. 455 00:19:59,680 --> 00:20:03,280 Astfel încât ultimul număr din în acest moment a fost de 17. 456 00:20:03,280 --> 00:20:07,540 Deci, dacă vreau să pop ceva off din stivă, acesta poate fi doar 17. 457 00:20:07,540 --> 00:20:11,890 Deci, există un ordin obligatoriu de operațiuni aici, unde ultimul element 458 00:20:11,890 --> 00:20:14,260 trebuie să fie în primul afară. 459 00:20:14,260 --> 00:20:16,440 Prin urmare, acronimul, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Deci, de ce ar fi acest lucru util? 461 00:20:19,160 --> 00:20:22,690 Sunt contextele în care te-ar Vreau o structură de date ca asta? 462 00:20:22,690 --> 00:20:24,810 Ei bine, a fost cu siguranță utilă în interiorul unui calculator. 463 00:20:24,810 --> 00:20:29,050 Sisteme de astfel de operare utilizat în mod clar acest lucru tip de structură de date pentru stive. 464 00:20:29,050 --> 00:20:32,800 Vom vedea, de asemenea, aceeași idee atunci când vine vorba de pagini web. 465 00:20:32,800 --> 00:20:35,890 Deci, în această săptămână și săptămâna viitoare și dincolo, și cum de a începe punerea în aplicare a web 466 00:20:35,890 --> 00:20:39,490 pagini într-un limbaj numit HTML, puteți folosi de fapt, o structură de date ca 467 00:20:39,490 --> 00:20:42,690 aceasta pentru a determina dacă pagina este formatat corect. 468 00:20:42,690 --> 00:20:47,170 Pentru că vom vedea toate paginile web urmeze un fel de ierarhie, o scobitură 469 00:20:47,170 --> 00:20:52,030 care va la sfârșitul zilei, fie, un structură arborescentă sub capota. 470 00:20:52,030 --> 00:20:53,620 Astfel mai mult pe faptul că, în doar un pic. 471 00:20:53,620 --> 00:20:56,560 >> Dar pentru acum, să propună pentru un clipă, cum am putea merge despre 472 00:20:56,560 --> 00:20:58,830 reprezentând ceea ce este o stivă? 473 00:20:58,830 --> 00:21:03,370 Permiteți-mi propun să implementăm o stiva cu codul ca aceasta. 474 00:21:03,370 --> 00:21:07,990 Deci, o stiva va avea în interiorul ei două lucruri, o matrice, numit tăvi, 475 00:21:07,990 --> 00:21:09,510 doar pentru a fi în concordanță cu demo-ul. 476 00:21:09,510 --> 00:21:12,660 Și fiecare dintre elementele din care matrice va fi un Int tip. 477 00:21:12,660 --> 00:21:14,740 Și capacitatea este probabil ce? 478 00:21:14,740 --> 00:21:18,796 Pentru că eu nu am scris definiție completă aici. 479 00:21:18,796 --> 00:21:21,535 >> Este, probabil, maxim dimensiunea de matrice. 480 00:21:21,535 --> 00:21:25,150 Și este, probabil, a declarat ca un obiect ascuțit definesc în partea de sus a fișierului, unele 481 00:21:25,150 --> 00:21:28,450 un fel de constant ca implicite de simpla capitalizare. 482 00:21:28,450 --> 00:21:32,250 Deci, undeva capacitate este definită ca dimensiunea maximă posibilă. 483 00:21:32,250 --> 00:21:35,590 Intre timp, în interiorul structurii datelor cunoscut ca o stivă va exista 484 00:21:35,590 --> 00:21:38,630 fie un întreg cunoscut doar pur și simplu ca dimensiune. 485 00:21:38,630 --> 00:21:43,400 >> Deci, dacă ar fi să reprezinte acest lucru acum pictural, să presupunem că această 486 00:21:43,400 --> 00:21:48,070 cutie neagră întreg reprezintă stack-ul meu. 487 00:21:48,070 --> 00:21:50,070 Interiorul este de două variabile. 488 00:21:50,070 --> 00:21:54,780 Așa că am de gând să atragă prima ca mărime. 489 00:21:54,780 --> 00:21:57,420 Și a doua am de gând să atragă ca un tablou. 490 00:21:57,420 --> 00:22:01,060 >> Dar, doar pentru a menține lucrurile ordonat, în mod normal mi-ar trage-o matrice ca 491 00:22:01,060 --> 00:22:04,910 acest lucru, dar este un fel de frumos dacă am corespund realității, sau 492 00:22:04,910 --> 00:22:06,230 potrivi cu modelul mental. 493 00:22:06,230 --> 00:22:12,880 Deci, lasă-mă în loc să atragă matrice vertical, care este doar, din nou, 494 00:22:12,880 --> 00:22:13,840 extrădare artist. 495 00:22:13,840 --> 00:22:16,610 Nu contează cu adevărat ceea ce este sub capota. 496 00:22:16,610 --> 00:22:20,350 Și vom spune că, în mod implicit, Capacitatea va fi de trei. 497 00:22:20,350 --> 00:22:23,480 Deci, acest lucru va fi locația 0, această va fi locația 1, această 498 00:22:23,480 --> 00:22:25,740 va fi locația 2. 499 00:22:25,740 --> 00:22:29,330 >> Dacă aș mitui cu o minge de stres, ar fi cineva vrea să vină și să rulați 500 00:22:29,330 --> 00:22:30,870 bord aici doar pentru o clipă? 501 00:22:30,870 --> 00:22:31,960 OK, a văzut mâna întâi. 502 00:22:31,960 --> 00:22:33,950 Hai sus. 503 00:22:33,950 --> 00:22:36,500 Bine. 504 00:22:36,500 --> 00:22:38,760 Deci, eu cred că este Steven. 505 00:22:38,760 --> 00:22:40,035 Hai sus. 506 00:22:40,035 --> 00:22:40,770 Bine. 507 00:22:40,770 --> 00:22:46,760 >> Dar să presupunem că acum suntem înapoi la inițială starea lumii în care am 508 00:22:46,760 --> 00:22:52,180 au declarat doar o stiva, și e va fi de capacitate trei. 509 00:22:52,180 --> 00:22:54,470 Dar dimensiunea nu a fost încă stabilită. 510 00:22:54,470 --> 00:22:56,100 Tăvi nu a fost încă stabilită. 511 00:22:56,100 --> 00:22:57,300 Deci, o serie de întrebări în primul rând. 512 00:22:57,300 --> 00:23:01,310 Și permiteți-mi să vă dau microfon, astfel încât să puteți participa mai activ în acest sens. 513 00:23:01,310 --> 00:23:05,190 >> Deci, ceea ce este în interiorul de dimensiuni în acest moment în timp, dacă tot am făcut este 514 00:23:05,190 --> 00:23:09,340 a declarat o stivă cu o linie de cod? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Nu prea mult. 516 00:23:10,100 --> 00:23:12,080 >> DAVID MALAN: OK, nu de mult. 517 00:23:12,080 --> 00:23:14,410 Nu știm ce este în interiorul de dimensiuni, nu știm ce e în interior 518 00:23:14,410 --> 00:23:16,330 din această matrice aici? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Doar cod aleatoriu, nu? 520 00:23:18,630 --> 00:23:20,220 Doar - 521 00:23:20,220 --> 00:23:23,230 >> DAVID MALAN: Da, am de gând să numesc cod, dar aleatoare - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Lucrurile. 523 00:23:23,820 --> 00:23:28,290 >> DAVID MALAN: Lucruri de genul aleatorie 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID MALAN: Bits, corect? 526 00:23:29,530 --> 00:23:31,190 Deci valori de gunoi, nu? 527 00:23:31,190 --> 00:23:33,470 Deci, permutări de 0 și 1 a lui. 528 00:23:33,470 --> 00:23:35,920 Resturi de utilizări anterioare din această memorie. 529 00:23:35,920 --> 00:23:38,150 Și nu știm cu adevărat ce valorile sunt, așa că de obicei le trage 530 00:23:38,150 --> 00:23:38,930 ca semne de întrebare. 531 00:23:38,930 --> 00:23:41,990 >> Deci, primul lucru pe care suntem probabil O să vrei să faci aici - 532 00:23:41,990 --> 00:23:46,630 și lasă-mă să dau acest domeniu interior de acolo un nume - tăvi. 533 00:23:46,630 --> 00:23:49,540 Ce ar trebui să probabil inițializa dimensiune a dacă vrem să 534 00:23:49,540 --> 00:23:51,040 începe să utilizați acest stiva? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Tava este sub 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID MALAN: Deci, OK. 537 00:23:53,910 --> 00:23:56,710 Pentru a fi clar, este declarată capacitatea în altă parte ca trei. 538 00:23:56,710 --> 00:23:58,570 Și asta e ceea ce am folosit să aloce matrice. 539 00:23:58,570 --> 00:24:03,535 Dimensiunea este de gând să se refere la cât de multe tăvi sunt în prezent pe stiva. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID MALAN: Deci, ar trebui să fie zero. 542 00:24:04,460 --> 00:24:07,760 Așa că mergeți mai departe, și cu orice deget, trage un zero în dimensiune. 543 00:24:07,760 --> 00:24:08,440 Bine. 544 00:24:08,440 --> 00:24:10,920 Deci, acum, ceea ce este în interiorul acestei aici, nu știm. 545 00:24:10,920 --> 00:24:12,160 Acestea sunt de fapt doar valori de gunoi. 546 00:24:12,160 --> 00:24:14,800 Deci, am putea desena semne de întrebare, dar Să păstrăm bord curat de acum 547 00:24:14,800 --> 00:24:16,300 pentru că nu contează ce-i acolo. 548 00:24:16,300 --> 00:24:19,130 Nu avem nevoie pentru a inițializa matrice la nimic, pentru că dacă noi știm că 549 00:24:19,130 --> 00:24:23,100 mărimea stivei este zero, bine, ne nu ar trebui să se uita la nimic din 550 00:24:23,100 --> 00:24:25,590 această matrice, oricum, la acest moment în timp. 551 00:24:25,590 --> 00:24:29,970 >> Deci, acum, să presupunem că am împinge numărul 9 pe stiva. 552 00:24:29,970 --> 00:24:33,750 Cum ar trebui să actualizeze structura de date în interiorul acestui cutie neagră? 553 00:24:33,750 --> 00:24:35,540 Ce valori trebuie să se schimbe? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: In - 555 00:24:36,200 --> 00:24:37,400 dimensiunea? 556 00:24:37,400 --> 00:24:37,650 >> DAVID MALAN: OK. 557 00:24:37,650 --> 00:24:38,770 Dimensiunea ar trebui să devină ce? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Dimensiunea ar fi una. 559 00:24:39,580 --> 00:24:39,870 >> DAVID MALAN: OK. 560 00:24:39,870 --> 00:24:41,110 Deci, dimensiunea ar trebui să devină una. 561 00:24:41,110 --> 00:24:42,540 Astfel, puteți face acest lucru în câteva moduri. 562 00:24:42,540 --> 00:24:46,920 Permiteți-mi să vă dau, acum dvs. deget este o gumă de șters. 563 00:24:46,920 --> 00:24:47,260 Bine. 564 00:24:47,260 --> 00:24:49,960 Apoi, acum degetul este o perie. 565 00:24:49,960 --> 00:24:50,330 Bine. 566 00:24:50,330 --> 00:24:52,820 Și acum ce altceva trebuie să se schimbe, evident, în structura de date? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Mergem la de jos în sus la 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID MALAN: 9. 569 00:24:57,760 --> 00:24:58,420 Bine, bine. 570 00:24:58,420 --> 00:25:01,550 Deci, încă nu contează ce e în locație unul sau doi, deoarece acestea sunt 571 00:25:01,550 --> 00:25:04,520 Valorile de gunoi, dar noi nu ar trebui să deranjeze caută acolo pentru că dimensiunea este 572 00:25:04,520 --> 00:25:07,540 ne spune că numai primul element este, de fapt legitim. 573 00:25:07,540 --> 00:25:10,400 Așa că acum am împinge 17 pe lista. 574 00:25:10,400 --> 00:25:11,830 Ce se întâmplă cu această imagine? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Deci, dimensiunea este de gând să meargă la două. 576 00:25:14,720 --> 00:25:15,300 >> DAVID MALAN: OK. 577 00:25:15,300 --> 00:25:16,070 Ești radieră - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Ești o radieră. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID MALAN: Esti o perie. 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 Și ce altceva? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: Și atunci noi - 586 00:25:22,600 --> 00:25:22,915 >> DAVID MALAN: Am împins 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Noi rămânem 17 pe partea de sus, așa - 588 00:25:24,760 --> 00:25:25,710 >> DAVID MALAN: Bine, bine. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - plasați-l în jos. 590 00:25:27,040 --> 00:25:27,530 >> DAVID MALAN: În regulă. 591 00:25:27,530 --> 00:25:27,940 Se face ușor. 592 00:25:27,940 --> 00:25:29,300 Eu nu am de gând să te ajute de data asta. 593 00:25:29,300 --> 00:25:30,510 Împinge 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Done. 595 00:25:31,720 --> 00:25:34,870 Devenind o radieră. 596 00:25:34,870 --> 00:25:37,340 Am devenit o perie. 597 00:25:37,340 --> 00:25:39,340 Și apoi eu sunt punerea 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID MALAN: 22. 599 00:25:40,100 --> 00:25:40,620 Excelent. 600 00:25:40,620 --> 00:25:41,380 Deci, o mai mult timp. 601 00:25:41,380 --> 00:25:44,280 Acum voi să împingă pe stiva 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh, Doamne. 604 00:25:50,278 --> 00:25:52,520 M-ai prins cu garda jos. 605 00:25:52,520 --> 00:25:53,703 >> DAVID MALAN: Nu ai vezi vine asta? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Nu am văzut asta venind. 607 00:25:55,930 --> 00:25:58,756 Am putea capacitate de re-inițială? 608 00:25:58,756 --> 00:25:59,790 >> DAVID MALAN: Asta este o întrebare bună. 609 00:25:59,790 --> 00:26:02,360 Așa că am un fel de noi vopsite într-un colț aici. 610 00:26:02,360 --> 00:26:06,740 Există într-adevăr nu este de bun pentru Steven pentru că am alocat această matrice 611 00:26:06,740 --> 00:26:09,130 static, ca să spunem așa, în interiorul din structura de date. 612 00:26:09,130 --> 00:26:12,170 Și am codat esență tare aceasta să fie de mărime trei. 613 00:26:12,170 --> 00:26:14,170 Deci nu se poate realoca adevărat. 614 00:26:14,170 --> 00:26:20,020 >> Am putea, dacă ne-am întors în, am redefinit tăvi pentru a fi un indicator care 615 00:26:20,020 --> 00:26:22,300 vom folosi apoi malloc în memoria mână la. 616 00:26:22,300 --> 00:26:25,050 Pentru că dacă ne-am memoria din heap prin malloc, am 617 00:26:25,050 --> 00:26:26,430 atunci s-ar putea elibera. 618 00:26:26,430 --> 00:26:29,630 Dar, înainte de eliberând-o, am putea realoca o bucată mai mare de memorie, 619 00:26:29,630 --> 00:26:31,330 actualiza indicatorul, și așa mai departe. 620 00:26:31,330 --> 00:26:33,500 Dar pentru acum, acest lucru este într-adevăr tot ce putem face. 621 00:26:33,500 --> 00:26:36,360 Apăsați și pop sunt probabil vor să aibă de a semnala o eroare. 622 00:26:36,360 --> 00:26:40,270 >> Deci, de exemplu, implementarea nostru de impuls ar putea reveni un bool care 623 00:26:40,270 --> 00:26:42,390 a revenit anterior adevărat, adevărat, adevărat. 624 00:26:42,390 --> 00:26:48,390 Dar a patra oară, se va avea pentru a reveni fals, de exemplu. 625 00:26:48,390 --> 00:26:48,540 Bine. 626 00:26:48,540 --> 00:26:49,540 Foarte bine facut. 627 00:26:49,540 --> 00:26:50,060 Felicitări. 628 00:26:50,060 --> 00:26:52,160 Ai câștigat mingea de stres azi. 629 00:26:52,160 --> 00:26:53,110 >> [Aplauze] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Mulțumesc. 631 00:26:54,382 --> 00:26:55,680 >> DAVID MALAN: Mulțumesc. 632 00:26:55,680 --> 00:26:59,740 OK, deci acest lucru nu pare a fi mult de un pas înainte, nu? 633 00:26:59,740 --> 00:27:01,410 Am descris această structură de date. 634 00:27:01,410 --> 00:27:02,320 A fost convingătoare, corect? 635 00:27:02,320 --> 00:27:03,200 Sisteme de operare place. 636 00:27:03,200 --> 00:27:06,360 Aparent web poate face uz de acest lucru, și alte aplicații încă. 637 00:27:06,360 --> 00:27:10,870 Dar ceea ce o limitare prost că suntem înapoi la fel de săptămână două limite 638 00:27:10,870 --> 00:27:12,880 unde ne-am fixat tablouri dimensiuni. 639 00:27:12,880 --> 00:27:15,010 >> Deci, există într-adevăr un cuplu de metode am putea rezolva aceasta. 640 00:27:15,010 --> 00:27:18,750 Am putea aloca dinamic matrice, Nu de greu de codificare ca am 641 00:27:18,750 --> 00:27:22,600 făcut aici, dar în loc să re-declararea acest lucru, doar pentru a fi clar, ca 642 00:27:22,600 --> 00:27:23,830 ceva de genul asta. 643 00:27:23,830 --> 00:27:29,040 Int * tăvi nu, decide pe o capacitate încă. 644 00:27:29,040 --> 00:27:35,460 Dar când am declara stivă în altă parte în codul meu, am putea numi apoi malloc, 645 00:27:35,460 --> 00:27:38,250 obține adresa de o bucată de memorie, și am putea atribui 646 00:27:38,250 --> 00:27:39,980 că adresa de tăvi. 647 00:27:39,980 --> 00:27:43,340 >> Și apoi, pentru că este doar o bucată de memorie, aș putea continua să utilizeze pătrat 648 00:27:43,340 --> 00:27:45,450 notație suport în mod obișnuit. 649 00:27:45,450 --> 00:27:49,020 Pentru că din nou, nu e un fel de acest echivalentul funcțional de matrice și 650 00:27:49,020 --> 00:27:50,820 bucăți de memorie care vin înapoi la malloc. 651 00:27:50,820 --> 00:27:53,090 Putem trata unul ca celălalt folosind aritmetica indicatorul sau 652 00:27:53,090 --> 00:27:54,440 notație suportul pătrat. 653 00:27:54,440 --> 00:27:55,660 Astfel că este o singură abordare. 654 00:27:55,660 --> 00:28:00,120 >> Dar cum altfel am putea să pună în aplicare această aceeași structură de date, eventual? 655 00:28:00,120 --> 00:28:00,280 Dreapta? 656 00:28:00,280 --> 00:28:04,530 Mă simt ca și cum tocmai am rezolvat această problema ca acum o săptămână. 657 00:28:04,530 --> 00:28:08,860 Care a fost soluția la această problemă că Steven a fugit în? 658 00:28:08,860 --> 00:28:10,370 Listele astfel legate, chiar. 659 00:28:10,370 --> 00:28:13,410 >> În cazul în care problema este că suntem pictura ne într-un colț de alocarea 660 00:28:13,410 --> 00:28:17,580 în avans, prea puțină memorie pe care le apoi de-a face într-un fel de, ei bine, 661 00:28:17,580 --> 00:28:19,880 de ce nu evita doar că emite cu totul? 662 00:28:19,880 --> 00:28:26,170 De ce nu declara doar tăvi pentru a fi un pointer la un nod, Ergo o lista inlantuita, 663 00:28:26,170 --> 00:28:30,740 și apoi pur și simplu aloca noduri noi de fiecare dată Steven necesar pentru a se potrivi o 664 00:28:30,740 --> 00:28:32,400 Numărul în structura de date. 665 00:28:32,400 --> 00:28:34,200 >> Deci, imaginea ar trebui să se schimbe. 666 00:28:34,200 --> 00:28:38,220 Nu va fi la fel de curat ca și simplu ca doar o serie de trei int. 667 00:28:38,220 --> 00:28:42,970 Acum o să fie un pointer la o struct, și că struct se va 668 00:28:42,970 --> 00:28:44,830 au un int și un pointer viitoare. 669 00:28:44,830 --> 00:28:47,670 Se va conduce prin care indicatorul la altul astfel struct să 670 00:28:47,670 --> 00:28:48,600 un alt astfel de struct. 671 00:28:48,600 --> 00:28:50,560 Deci, imaginea ar fi de fapt obține un Messier pic. 672 00:28:50,560 --> 00:28:52,950 Și ne-ar fi săgeți legarea totul împreună. 673 00:28:52,950 --> 00:28:55,280 >> Dar asta e bine, nu, pentru că am văzut cum să facă acest lucru. 674 00:28:55,280 --> 00:28:58,180 Și odată ce te confortabil implementarea ceva ca un legat 675 00:28:58,180 --> 00:29:01,450 Lista, care va trebui să faceți dacă aveți alege să pună în aplicare un tabel hash cu 676 00:29:01,450 --> 00:29:05,120 înlănțuirea separată pentru p-set 6, puteți să-l utilizați ca un bloc, sau un 677 00:29:05,120 --> 00:29:08,870 ingredient, sau în Scratch vorbesc, o Procedura, ceva ce ai pus, ai 678 00:29:08,870 --> 00:29:12,560 a creat propria piesa de puzzle pe care le puteți apoi reutilizarea. 679 00:29:12,560 --> 00:29:17,090 Compromisuri lucru, dar eventualele soluții pe care le-am văzut de fapt înainte. 680 00:29:17,090 --> 00:29:20,560 >> Deci, destul de des, veți vedea acest lucru în fiecare an sau doi când Apple lanseaza 681 00:29:20,560 --> 00:29:23,060 ceva nou, și toți oameni nebuni linie in afara de Apple 682 00:29:23,060 --> 00:29:27,050 magazin să cumpere marginal lor upgrade de pe hardware. 683 00:29:27,050 --> 00:29:30,420 Spun acest lucru, e OK, pentru că Eu sunt unul dintre acei oameni. 684 00:29:30,420 --> 00:29:35,140 Deci, ce fel de structuri de date s-ar putea reprezenta această realitate? 685 00:29:35,140 --> 00:29:36,980 >> Ei bine, haideți să o coadă, o linie de apel. 686 00:29:36,980 --> 00:29:40,270 Deci britanic ar numi ea de obicei o coadă oricum, asa ca este un nume frumos. 687 00:29:40,270 --> 00:29:44,960 Și cele două operații pe care o coadă sprijină vom numi un Puneți în coadă 688 00:29:44,960 --> 00:29:48,900 funcționare și o operație dequeue, care sunt similare în 689 00:29:48,900 --> 00:29:50,120 spirit pentru a împinge și pop. 690 00:29:50,120 --> 00:29:54,060 E doar un fel de diferit în convenție, ceea ce ne cheamă acestea. 691 00:29:54,060 --> 00:29:57,680 Dar a Puneți în coadă ceva înseamnă a adăuga sau se introduce la structura de date. 692 00:29:57,680 --> 00:29:59,570 Pentru a dequeue înseamnă să-l scoate. 693 00:29:59,570 --> 00:30:05,170 Dar întrucât o stivă a fost un date LIFO structura, o coadă este o premieră în, 694 00:30:05,170 --> 00:30:06,740 în primul rând în structura de date. 695 00:30:06,740 --> 00:30:10,050 >> Daca esti prima persoana din linie, va fi prima persoană pentru a obține 696 00:30:10,050 --> 00:30:12,420 de linie și cumpere noul dispozitiv. 697 00:30:12,420 --> 00:30:18,070 Imaginați-vă cât de supărat ar fi acești oameni daca Apple folosit în loc o stivă, pentru 698 00:30:18,070 --> 00:30:21,250 exemplu, pentru punerea în aplicare a cules din noua jucărie. 699 00:30:21,250 --> 00:30:24,310 Deci, cozile sens, cu siguranță, și ne putem gândi la tot felul de 700 00:30:24,310 --> 00:30:27,480 aplicații, probabil, pentru cozile, mai ales atunci când doriți corectitudine. 701 00:30:27,480 --> 00:30:30,040 Deci, cum am putea pune în aplicare aceste ca o structură de date? 702 00:30:30,040 --> 00:30:33,680 >> Ei bine, eu propun ca am putea Trebuie să facem în acest fel. 703 00:30:33,680 --> 00:30:35,225 Așa că am de gând să aibă acum numere. 704 00:30:35,225 --> 00:30:38,190 Deci, vom păstrați-l simplu și nu vorbesc în mod necesar din punct de vedere tăvi. 705 00:30:38,190 --> 00:30:40,220 Doar numerele care oamenii de ajuns. 706 00:30:40,220 --> 00:30:43,760 Capacitatea este de gând să, din nou, fixa numărul total de persoane care pot fi în 707 00:30:43,760 --> 00:30:46,900 această linie, ca de trei sau orice altă valoare. 708 00:30:46,900 --> 00:30:50,760 >> Dar eu propun ca am nevoie pentru a ține evidența nu numai de mărimea 709 00:30:50,760 --> 00:30:52,370 coadă, cât de multe lucruri sunt în ea. 710 00:30:52,370 --> 00:30:56,310 Deci dimensiunea este curent mărime, capacitate este dimensiunea maximă. 711 00:30:56,310 --> 00:30:58,540 Doar din nou, nomenclatura prin convenție. 712 00:30:58,540 --> 00:31:03,680 De ce am nevoie de un int suplimentare de interior de o coadă pentru a urmări care este în 713 00:31:03,680 --> 00:31:05,365 partea din față a liniei? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 De ce am nevoie pentru a face acest lucru, în acest caz? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Ei bine, ce este această imagine va schimba? 718 00:31:16,190 --> 00:31:19,280 Probabil că pot reutiliza mai de această imagine. 719 00:31:19,280 --> 00:31:21,480 Lasă-mă să merg mai departe și șterge ce e aici. 720 00:31:21,480 --> 00:31:24,580 Vom da acest lucru un ușor nume diferit aici. 721 00:31:24,580 --> 00:31:28,930 Să scăpăm de 17, să scăpăm din 9, să scăpăm de 3. 722 00:31:28,930 --> 00:31:30,410 Și haideți să adăugați un alt lucru. 723 00:31:30,410 --> 00:31:34,710 Eu propun ca am nevoie pentru a ține evidența frontală a listei, care este doar 724 00:31:34,710 --> 00:31:35,570 va fi un int la fel de bine. 725 00:31:35,570 --> 00:31:36,550 Și am de gând să-l păstrați simplu. 726 00:31:36,550 --> 00:31:37,740 Nici o lista inlantuita de acum. 727 00:31:37,740 --> 00:31:40,900 >> Vom admite că vom ciocni de această limită. 728 00:31:40,900 --> 00:31:43,720 Dar ceea ce vreau să văd întâmplat de data asta? 729 00:31:43,720 --> 00:31:47,240 Așa că aș merge mai departe și primul persoană vine în linie, și 730 00:31:47,240 --> 00:31:48,560 e numărul 9. 731 00:31:48,560 --> 00:31:49,680 Avem bile de stres. 732 00:31:49,680 --> 00:31:51,330 Pot să fure, să zicem, două sau trei persoane? 733 00:31:51,330 --> 00:31:52,690 Unu, doi, trei? 734 00:31:52,690 --> 00:31:53,120 Hai sus. 735 00:31:53,120 --> 00:31:56,022 Chiar din fata, deoarece vom face asta rapid. 736 00:31:56,022 --> 00:31:59,415 >> Fiecare dintre voi este acum de gând să fie un băiat ventilator în linie de la Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Tu nu va primi hardware-ul Apple la sfârșitul acestui totuși. 739 00:32:06,210 --> 00:32:06,500 Bine. 740 00:32:06,500 --> 00:32:09,430 Deci, tu ești numărul 9, tu esti numărul 17, numărul 22. 741 00:32:09,430 --> 00:32:12,130 Acestea sunt numere arbitrare, cum ar fi carduri de student sau fleacuri. 742 00:32:12,130 --> 00:32:14,550 Și într-o clipă, să începem pentru a începe adăugarea de lucruri. 743 00:32:14,550 --> 00:32:16,000 Și voi alerga la bord aici de data asta. 744 00:32:16,000 --> 00:32:19,570 >> Deci, în acest caz, am inițializat față de a fi - 745 00:32:19,570 --> 00:32:22,380 Eu de fapt, nu-mi pasă cu adevărat ceea ce față este, deoarece dimensiunea este zero. 746 00:32:22,380 --> 00:32:24,480 Deci, acest lucru s-ar putea la fel de bine doar fi un semn de întrebare. 747 00:32:24,480 --> 00:32:26,170 Acestea sunt toate semne de întrebare. 748 00:32:26,170 --> 00:32:29,880 Deci, acum vom începe pentru a vedea de fapt, unele oameni garnitură de până la magazin. 749 00:32:29,880 --> 00:32:33,320 >> Deci, în cazul în care numărul 9, tu ești primul acolo la 5 AM, mergeți mai departe și linia de sus, 750 00:32:33,320 --> 00:32:34,210 sau cu o noapte înainte. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Deci, acum 9 este aici. 753 00:32:35,940 --> 00:32:37,940 Deci 9 este în fața listă. 754 00:32:37,940 --> 00:32:41,440 Așa că am de gând să merg mai departe și să actualizeze dimensiunea acestor date actuale 755 00:32:41,440 --> 00:32:44,740 Structura sa nu fie 0 mai, ci să fie 1. 756 00:32:44,740 --> 00:32:47,630 Am de gând să pună 9 la fata de lista. 757 00:32:47,630 --> 00:32:51,020 Lasă-mă să merg mai departe și comuta pe ecran astfel încât să putem vedea trecutul ne aici. 758 00:32:51,020 --> 00:32:53,220 >> Și acum ce vreau pentru a pune în față? 759 00:32:53,220 --> 00:32:56,240 Voi urmări ca fata de coada chiar acum 760 00:32:56,240 --> 00:32:58,570 este la locația 0. 761 00:32:58,570 --> 00:33:00,510 Pentru că ceea ce se viitoare va întâmpla? 762 00:33:00,510 --> 00:33:03,000 Ei bine, să presupunem că acum am Puneți în coadă 17, de asemenea. 763 00:33:03,000 --> 00:33:04,510 Trăiește în linie acolo. 764 00:33:04,510 --> 00:33:07,060 Și din nou, un fel de ușă la Magazinul va fi aici. 765 00:33:07,060 --> 00:33:08,700 Așa că acum am adăugat 17. 766 00:33:08,700 --> 00:33:10,810 Și, chiar dacă acești oameni sunt blocarea ecran, care e OK, 767 00:33:10,810 --> 00:33:12,300 pentru că putem vedea aici. 768 00:33:12,300 --> 00:33:12,910 Scuze. 769 00:33:12,910 --> 00:33:13,810 >> Audiența: Ne putem muta - 770 00:33:13,810 --> 00:33:14,660 >> DAVID MALAN: Nu, e în regulă. 771 00:33:14,660 --> 00:33:16,000 Este foarte mare acolo. 772 00:33:16,000 --> 00:33:18,580 Deci, 17 este acum în interiorul cozii. 773 00:33:18,580 --> 00:33:21,332 Am nevoie de a actualiza care câmpurile acum, deși? 774 00:33:21,332 --> 00:33:23,210 OK, cu siguranta dimensiune. 775 00:33:23,210 --> 00:33:26,430 Și cum despre fata? 776 00:33:26,430 --> 00:33:27,040 OK, nu. 777 00:33:27,040 --> 00:33:30,200 Față nu trebuie să se schimbe, deoarece spre deosebire de o stivă, am 778 00:33:30,200 --> 00:33:31,370 doresc să mențină corectitudine. 779 00:33:31,370 --> 00:33:35,150 Deci, dacă 9 a venit în primul rând, dorim 9 să fie primul din linia 780 00:33:35,150 --> 00:33:36,420 și în magazin. 781 00:33:36,420 --> 00:33:37,220 >> De fapt, să vedem asta. 782 00:33:37,220 --> 00:33:42,235 Înainte de a introduce 22, să mergeți mai departe și dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Care e numele tău din nou? 784 00:33:42,970 --> 00:33:43,680 >> Audiența: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID MALAN: Jake se întâmplă să fie dequeued acum. 786 00:33:45,440 --> 00:33:48,050 Astfel încât să obțineți pentru a merge în magazin. 787 00:33:48,050 --> 00:33:49,880 Și pretinde că magazinul este acolo. 788 00:33:49,880 --> 00:33:51,970 Deci, acum ce are nevoie - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Ce trebuie să se întâmple acum? 790 00:33:53,400 --> 00:33:54,490 Decizie de design. 791 00:33:54,490 --> 00:33:56,825 Deci, nu un instinct rău, dar - Care e numele tău din nou? 792 00:33:56,825 --> 00:33:57,090 >> Audiența: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID MALAN: David. 794 00:33:57,500 --> 00:33:58,810 Deci, ce a făcut David? 795 00:33:58,810 --> 00:34:02,590 El a fost încercarea de a sorta a stabili datelor Structura și pentru a muta de la locația lui 796 00:34:02,590 --> 00:34:04,100 în fosta locație a lui Jake. 797 00:34:04,100 --> 00:34:06,740 Și asta e bine, dacă suntem dispuși să considere că aceasta este o 798 00:34:06,740 --> 00:34:08,199 detalii de implementare. 799 00:34:08,199 --> 00:34:11,100 Dar, mai întâi, să actualizeze datele Structura înainte de a face acest lucru. 800 00:34:11,100 --> 00:34:14,139 Pentru că nu-mi place ideea de toate oamenii deplasare în această linie. 801 00:34:14,139 --> 00:34:17,360 >> Nu e mare lucru dacă David o face cu un singur pas, dar, din nou, cred că înapoi la 802 00:34:17,360 --> 00:34:20,360 când am avut opt ​​voluntari de pe scenă și am făcut ca inserare 803 00:34:20,360 --> 00:34:22,600 fel, în cazul în care am avut de a începe mișcare toată lumea din jurul. 804 00:34:22,600 --> 00:34:23,790 Care a primit scump, nu? 805 00:34:23,790 --> 00:34:28,330 Asta mă face să mă piti despre Big O de n, O mare de n pătrat din nou. 806 00:34:28,330 --> 00:34:30,650 Nu se simte ca un rezultat ideal. 807 00:34:30,650 --> 00:34:32,080 >> Așa că haideți să actualizeze doar acest lucru. 808 00:34:32,080 --> 00:34:35,120 Astfel încât dimensiunea cozii nu mai este 2. 809 00:34:35,120 --> 00:34:37,090 Acum e pur și simplu 1. 810 00:34:37,090 --> 00:34:40,360 Dar pot actualiza acum ceva N-au actualizat înainte, 811 00:34:40,360 --> 00:34:41,130 fata de lista. 812 00:34:41,130 --> 00:34:45,420 Am putea spune doar, este că locația 1? 813 00:34:45,420 --> 00:34:49,770 Deci, acum avem valoare gunoi aici, Valoarea gunoi aici, și David în 814 00:34:49,770 --> 00:34:51,469 mijlocul de acest gunoi. 815 00:34:51,469 --> 00:34:54,980 Dar structura de date este încă intactă. 816 00:34:54,980 --> 00:34:58,540 >> Și, de fapt, nici măcar nu trebuie să schimba fostul numărul lui Jake 817 00:34:58,540 --> 00:35:00,460 9, pentru care îi pasă. 818 00:35:00,460 --> 00:35:04,470 Am suficiente informații acum în Dimensiunea că știu că sunt o persoană în 819 00:35:04,470 --> 00:35:05,030 această coadă. 820 00:35:05,030 --> 00:35:08,340 Și știu că acea persoană este la locația 1, nu 0. 821 00:35:08,340 --> 00:35:09,760 Eu nu contez. 822 00:35:09,760 --> 00:35:11,300 Deci 1, de asemenea. 823 00:35:11,300 --> 00:35:13,410 Deci, structura de date este încă OK. 824 00:35:13,410 --> 00:35:14,330 >> Ei bine, ce se întâmplă în continuare? 825 00:35:14,330 --> 00:35:15,010 Să Puneți în coadă - 826 00:35:15,010 --> 00:35:15,370 Care e numele tău? 827 00:35:15,370 --> 00:35:16,160 >> Audiența: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID MALAN: Callen. 829 00:35:16,580 --> 00:35:20,770 Să Puneți în coadă un Callen, și 22 este acum în coada de așteptare. 830 00:35:20,770 --> 00:35:22,300 Deci, acum ce trebuie să se schimbe aici? 831 00:35:22,300 --> 00:35:24,380 Fata nu este de gând să schimba, evident. 832 00:35:24,380 --> 00:35:27,160 Dimensiunea se va schimba pentru a fi din nou 2. 833 00:35:27,160 --> 00:35:31,590 22 și se termină aici, 9 este încă prezent, dar este în mod efectiv o 834 00:35:31,590 --> 00:35:32,600 Valoarea gunoi acum. 835 00:35:32,600 --> 00:35:35,910 E doar o rămășiță de Jake trecut. 836 00:35:35,910 --> 00:35:39,200 >> Deci, acum, ce se întâmplă dacă Am dequeue David? 837 00:35:39,200 --> 00:35:41,560 O ultimă operație, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Am putea schimba, dar eu propun Să face ca munca mai puțin posibil. 839 00:35:46,070 --> 00:35:50,280 Acum, structura mea de date se înapoi în mărime de la 2 la 1. 840 00:35:50,280 --> 00:35:53,730 Dar partea din fata a cozii acum devine 2. 841 00:35:53,730 --> 00:35:56,640 Nu am nevoie pentru a schimba aceste numere doar încă, pentru că sunt 842 00:35:56,640 --> 00:35:58,230 doar valorile de gunoi. 843 00:35:58,230 --> 00:35:59,720 >> Dar acum ce se întâmplă? 844 00:35:59,720 --> 00:36:03,280 Să presupunem că m-am Puneți în coadă, 26? 845 00:36:03,280 --> 00:36:05,890 Mă simt ca și cum mi-e locul aici. 846 00:36:05,890 --> 00:36:06,890 Deci, eu sunt enqueued. 847 00:36:06,890 --> 00:36:08,760 Asa ca am un fel de locul aici. 848 00:36:08,760 --> 00:36:11,300 Și, chiar dacă nu prea Apreciez acest lucru vizual pe scena, 849 00:36:11,300 --> 00:36:15,075 pentru că avem o mulțime de cameră, că ar trebui nu sta aici, de ce? 850 00:36:15,075 --> 00:36:16,290 >> Audiența: Ești în afara limitelor. 851 00:36:16,290 --> 00:36:16,370 >> DAVID MALAN: Corect. 852 00:36:16,370 --> 00:36:16,940 Sunt în afara limitelor. 853 00:36:16,940 --> 00:36:19,330 Am indexate dincolo de limitele acestei matrice. 854 00:36:19,330 --> 00:36:23,420 Am într-adevăr ar trebui să fie într-una din trei locatii posibile. 855 00:36:23,420 --> 00:36:25,150 Acum, unde e cel mai natural de a merge? 856 00:36:25,150 --> 00:36:27,760 Propun să leveraged o săptămână, un truc. 857 00:36:27,760 --> 00:36:30,150 Operatorul mod, procentual. 858 00:36:30,150 --> 00:36:36,850 Pentru că eu sunt punct de vedere tehnic în picioare la locație 3, dar eu 3 capacitate MOD, 859 00:36:36,850 --> 00:36:40,250 deci 3, un semn procent, 3 - 860 00:36:40,250 --> 00:36:40,970 Capacitatea este 3. 861 00:36:40,970 --> 00:36:41,720 Ce-i asta? 862 00:36:41,720 --> 00:36:43,700 Care este restul atunci când vă împărțiți 3 de 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Astfel că mă pune fost Jake a fost, care este, de fapt bine. 865 00:36:48,140 --> 00:36:50,370 Deci, acum punerii în aplicare de acest lucru se va 866 00:36:50,370 --> 00:36:51,250 fi un pic de o durere de cap. 867 00:36:51,250 --> 00:36:53,740 Este într-adevăr doar o singură linie de dureri de cap, de cod. 868 00:36:53,740 --> 00:36:56,580 Dar cel puțin acum nu e gunoi valoare aici, dar există două 869 00:36:56,580 --> 00:36:57,910 int legitime aici. 870 00:36:57,910 --> 00:37:04,160 Și eu susțin că acum am făcut exact ceea ce trebuie să facem, atât timp cât 871 00:37:04,160 --> 00:37:08,600 vom schimba ceea ce Jake valoare a fost să fie 26. 872 00:37:08,600 --> 00:37:12,110 >> Acum avem suficiente informații încă pentru a menține integritatea 873 00:37:12,110 --> 00:37:13,060 acestei structuri de date. 874 00:37:13,060 --> 00:37:17,160 Suntem încă un fel de noroc atunci când am doriți să inserați total de patru sau mai multe 875 00:37:17,160 --> 00:37:20,740 elemente, dar eu pot cel puțin să destul de utilizarea eficientă a acestei constante 876 00:37:20,740 --> 00:37:21,740 timp, de fapt. 877 00:37:21,740 --> 00:37:27,150 Nu trebuie să vă faceți griji cu privire la schimbarea toată lumea, ca înclinația lui David a fost. 878 00:37:27,150 --> 00:37:30,816 >> Orice întrebări cu privire la stive, sau acest coadă? 879 00:37:30,816 --> 00:37:32,184 >> Audiența: Este motivul aveți nevoie de mărime, astfel încât să știți 880 00:37:32,184 --> 00:37:34,010 în cazul în care să aibă o persoană? 881 00:37:34,010 --> 00:37:34,770 >> DAVID MALAN: Exact. 882 00:37:34,770 --> 00:37:38,230 Am nevoie să știu dimensiunea de matrice pentru că am nevoie să știu exact cum 883 00:37:38,230 --> 00:37:41,940 multe dintre aceste valori sunt legitime, și astfel încât să pot găsi în cazul în care pentru a pune 884 00:37:41,940 --> 00:37:42,800 Următoarea persoană. 885 00:37:42,800 --> 00:37:43,300 Exact. 886 00:37:43,300 --> 00:37:44,580 Dimensiunea este de - 887 00:37:44,580 --> 00:37:46,360 de fapt, nu am actualiza acest încă. 888 00:37:46,360 --> 00:37:48,380 M-am adăugat la 26. 889 00:37:48,380 --> 00:37:51,760 Dimensiunea este acum, nu 1, ci 2. 890 00:37:51,760 --> 00:37:57,780 Deci, acum acest lucru într-adevăr ajută-mă să găsesc cap de listă, care nu este 0, nu 891 00:37:57,780 --> 00:37:59,250 1, dar este 2. 892 00:37:59,250 --> 00:38:01,665 Partea din față a listei este într-adevăr numărul 22. 893 00:38:01,665 --> 00:38:05,120 Pentru că a venit în primul rând, așa că ar trebui să fi permisă în magazin înainte de mine, 894 00:38:05,120 --> 00:38:08,780 chiar dacă vizual stau mai aproape de magazin. 895 00:38:08,780 --> 00:38:09,220 >> În regulă? 896 00:38:09,220 --> 00:38:12,410 O rundă de aplauze pentru aceste baieti și le vom lăsa să iasă de acolo. 897 00:38:12,410 --> 00:38:17,090 >> [Aplauze] 898 00:38:17,090 --> 00:38:18,150 >> DAVID MALAN: aș putea să vă păstrați tava. 899 00:38:18,150 --> 00:38:20,760 Am putea vedea ce se întâmplă dacă vrei, dar poate că nu. 900 00:38:20,760 --> 00:38:21,590 Bine. 901 00:38:21,590 --> 00:38:25,380 Deci, ce facem acum noi ce facem? 902 00:38:25,380 --> 00:38:28,900 Ei bine, permiteți-mi să propun că există o alte câteva structuri de date am putea 903 00:38:28,900 --> 00:38:33,810 începe adăugarea la setul nostru instrument care va de fapt este destul, destul de relevant 904 00:38:33,810 --> 00:38:35,270 vom arunca cu capul în chestii web. 905 00:38:35,270 --> 00:38:38,150 Care din nou, are un fel de conexiune la copaci în formă de 906 00:38:38,150 --> 00:38:40,550 ceva numit DOM, documentul modelul de obiect. 907 00:38:40,550 --> 00:38:42,370 Dar vom vedea mai mult de că înainte de mult timp. 908 00:38:42,370 --> 00:38:46,260 >> Permiteți-mi să propun definitionally pe care le apel copac acum ceea ce s-ar putea, stiu ca 909 00:38:46,260 --> 00:38:48,820 mai mult de un arbore genealogic, în cazul în care au unele strămoș la 910 00:38:48,820 --> 00:38:49,790 rădăcinile copacului. 911 00:38:49,790 --> 00:38:54,480 Un matriarhatului patriarhal sau o la foarte de sus a copac. 912 00:38:54,480 --> 00:38:56,700 Fără partenerul de viață, în acest caz. 913 00:38:56,700 --> 00:39:00,940 Dar acum avem ceea ce vom numi copii, care sunt noduri care atârnă 914 00:39:00,940 --> 00:39:05,480 pe copil la stânga sau la dreapta copil, săgeți cum este descris aici. 915 00:39:05,480 --> 00:39:10,490 >> Cu alte cuvinte, într-o structură de date arbore în calculator, un copac are zero 916 00:39:10,490 --> 00:39:11,480 sau mai multe noduri. 917 00:39:11,480 --> 00:39:13,500 Dacă prezintă cel puțin un nod, care se numește rădăcină. 918 00:39:13,500 --> 00:39:15,700 Sunt lucruri pe care vizual ne trage în sus. 919 00:39:15,700 --> 00:39:20,280 Și că nod, la fel ca orice alt nod, poate au zero, unu, sau doi, sau trei, 920 00:39:20,280 --> 00:39:23,600 sau oricât de mulți copii Structura de date acceptă. 921 00:39:23,600 --> 00:39:29,150 În acest caz, rădăcină, stocarea valoarea unul, are doi copii, 2 și 3, 922 00:39:29,150 --> 00:39:33,020 așa că, în general, numim 2 stângă copil și 3 copilul dreapta. 923 00:39:33,020 --> 00:39:36,940 >> Și atunci când vom ajunge până la 5, 6, și 7, 6 ar putea fi numit copilul mijlociu. 924 00:39:36,940 --> 00:39:38,940 Dacă aveți patru copii, devine confuz. 925 00:39:38,940 --> 00:39:42,260 Deci, noi nu mai utilizați acest tip de comenzi rapide verbal. 926 00:39:42,260 --> 00:39:44,580 Dar este într-adevăr doar un arbore genealogic. 927 00:39:44,580 --> 00:39:48,880 Și frunzele aici sunt nodurile care ei nu au copii. 928 00:39:48,880 --> 00:39:52,540 Ei stau pe partea de jos a arborelui. 929 00:39:52,540 --> 00:39:56,940 >> Deci, cum am putea implementa un copac care are doar doi copii la maxim? 930 00:39:56,940 --> 00:39:58,410 Vom un arbore binar apel. 931 00:39:58,410 --> 00:40:00,960 Bi nou adică două, în acest caz, ca și cu binar. 932 00:40:00,960 --> 00:40:04,830 Și astfel se poate avea zero, unu, sau doi copii la maximum. 933 00:40:04,830 --> 00:40:08,650 >> O să propun ca vom pune în aplicare nodul pentru ca structură cu un n int, 934 00:40:08,650 --> 00:40:11,910 și apoi doi pointeri, unul numit a plecat, unul numit dreptate. 935 00:40:11,910 --> 00:40:14,830 Dar acestea sunt doar frumos convențiile arbitrare. 936 00:40:14,830 --> 00:40:18,170 Și ceea ce e frumos acum, mai ales dacă fel de luptat cu conceptual 937 00:40:18,170 --> 00:40:21,300 recursivitate, sau a crezut că nu era într-adevăr o soluție la nimic, 938 00:40:21,300 --> 00:40:23,120 mai ales dacă ai putea a alerga afară de memorie. 939 00:40:23,120 --> 00:40:26,600 Acum, că vorbim despre date Structuri si algoritmi care permit 940 00:40:26,600 --> 00:40:31,030 ne să traverseze și să le manipuleze, se dovedește că recursivitate se întoarce în 941 00:40:31,030 --> 00:40:34,240 o mult mai convingatoare dacă nu mod frumos. 942 00:40:34,240 --> 00:40:38,670 >> Deci, acest propun este aplicarea de o funcție de căutare. 943 00:40:38,670 --> 00:40:39,870 Având în vedere cele două intrări - 944 00:40:39,870 --> 00:40:41,570 deci cred că de acest lucru ca o cutie neagră. 945 00:40:41,570 --> 00:40:46,560 Având în vedere cele două intrări, n, int, și o pointer la un copac, un pointer la o 946 00:40:46,560 --> 00:40:50,020 nod, sau chiar la rădăcina unui copac, am susțin că această funcție poate returna 947 00:40:50,020 --> 00:40:53,530 adevărat sau fals, că valoarea n Este în interiorul acestui copac. 948 00:40:53,530 --> 00:40:55,210 >> Ce este în interiorul acestui cutie neagră? 949 00:40:55,210 --> 00:40:57,440 Ei bine, patru filiale. 950 00:40:57,440 --> 00:40:58,385 Primul doar verifică. 951 00:40:58,385 --> 00:41:00,490 Dacă copac este nul, doar întoarce false. 952 00:41:00,490 --> 00:41:04,580 Dacă nu există nod, nu exista nici n, nu există nici un număr, doar întoarce false. 953 00:41:04,580 --> 00:41:12,330 Dacă totuși, n, valoarea pe care o căutați pentru, este mai mică de copac săgeata n, și 954 00:41:12,330 --> 00:41:15,180 doar pentru a fi clar, ce înseamnă când Scriu copac și apoi săgeata 955 00:41:15,180 --> 00:41:18,150 notație, n? 956 00:41:18,150 --> 00:41:18,690 Exact. 957 00:41:18,690 --> 00:41:21,970 Aceasta înseamnă că dereference indicatorul numit copac. 958 00:41:21,970 --> 00:41:26,750 Du-te acolo, iar apoi obține în interiorul de care nodul și să obțină domeniul său numit n. 959 00:41:26,750 --> 00:41:30,810 Și apoi comparați n real, care a fost a trecut în căutare de ea. 960 00:41:30,810 --> 00:41:35,390 >> Deci, dacă n este mai mic, valoarea n în nodul copac în sine, ei bine, 961 00:41:35,390 --> 00:41:36,720 Ce înseamnă asta? 962 00:41:36,720 --> 00:41:40,690 Asta nu înseamnă nimic la prima vedere. 963 00:41:40,690 --> 00:41:40,900 Dreapta? 964 00:41:40,900 --> 00:41:45,560 La fel ca atunci când aveți o serie de valori, ar putea dori să se aplice binar 965 00:41:45,560 --> 00:41:48,290 căuta ca o formă de divizare și cuceri. 966 00:41:48,290 --> 00:41:51,790 Dar ceea ce presupunere am nevoie pentru a face pentru binar de căutare pentru a lucra la toate 967 00:41:51,790 --> 00:41:54,510 în cartea de telefon și exemplele anterioare? 968 00:41:54,510 --> 00:41:55,530 >> Cum să fie sortate. 969 00:41:55,530 --> 00:41:59,490 Deci, haideți să rafineze definiția de copac aici nu sa fie doar un copac, care poate 970 00:41:59,490 --> 00:42:00,880 avea orice număr de copii. 971 00:42:00,880 --> 00:42:04,700 Nu doar un arbore binar, care poate avea 0, 1, 2 sau maxim. 972 00:42:04,700 --> 00:42:09,700 Ci ca un arbore binar de căutare, sau BST, care este doar un mod fantezist de a spune o 973 00:42:09,700 --> 00:42:15,430 arbore binar astfel încât fiecare nod copil stânga, dacă este prezent, este 974 00:42:15,430 --> 00:42:16,830 mai puțin de nod. 975 00:42:16,830 --> 00:42:20,170 Și dreptul copilului la fiecare nod, dacă este prezent, este mai mare 976 00:42:20,170 --> 00:42:21,740 decât nodul în sine. 977 00:42:21,740 --> 00:42:25,200 >> Deci, cu alte cuvinte, dacă ar fi să atragă out copac, toate numerele sunt 978 00:42:25,200 --> 00:42:30,620 echilibrat cu grijă ca acest lucru, astfel încât, dacă aveți 55 ca rădăcină, 33 poate merge 979 00:42:30,620 --> 00:42:33,090 la stânga ei, pentru că este mai puțin de 55. 980 00:42:33,090 --> 00:42:36,430 77 pot merge la dreapta sa, deoarece este mai mare de 55. 981 00:42:36,430 --> 00:42:40,750 Dar acum observa, aceeași definiție, este o definiție recursivă verbal, 982 00:42:40,750 --> 00:42:42,600 trebuie să se aplice pentru 33. 983 00:42:42,600 --> 00:42:47,610 Copilului stânga 33 trebuie să fie mai mică decât aceasta, și dreptul copilului de 33, 44, trebuie să fie 984 00:42:47,610 --> 00:42:48,580 mai mare decât aceasta. 985 00:42:48,580 --> 00:42:51,670 >> Deci, acesta este un arbore binar de căutare, și Eu propun, folosind un pic de 986 00:42:51,670 --> 00:42:53,910 recursivitate, putem găsi acum n. 987 00:42:53,910 --> 00:42:59,160 Deci, dacă n este mai mic decât valoarea n care este nodul curent, am de gând să merg 988 00:42:59,160 --> 00:43:04,090 înainte și punt, ca să spunem așa, și doar reveni indiferent de răspunsul este de 989 00:43:04,090 --> 00:43:08,470 căutarea n pe copilului stânga copac. 990 00:43:08,470 --> 00:43:11,370 Observați din nou, această funcție doar se așteaptă la o stea nod, un 991 00:43:11,370 --> 00:43:12,780 pointer la un nod. 992 00:43:12,780 --> 00:43:17,360 Deci, cu siguranță, eu pot face doar copac săgeată la stânga, ceea ce va conduce 993 00:43:17,360 --> 00:43:18,400 ma la un alt nod. 994 00:43:18,400 --> 00:43:19,480 Dar ceea ce este că nodul? 995 00:43:19,480 --> 00:43:22,820 >> Ei bine, în conformitate cu această declarație, stânga este doar un pointer, astfel încât doar 996 00:43:22,820 --> 00:43:27,090 înseamnă Trec la funcția de căutare un pointer diferit, și anume 997 00:43:27,090 --> 00:43:30,750 cel care reprezintă copac copilul meu stâng a lui. 998 00:43:30,750 --> 00:43:36,040 Deci, în acest caz, indicatorul la 33, dacă acesta este introdus de nostru eșantion Între timp, în cazul în care 999 00:43:36,040 --> 00:43:40,740 n este mai mare decât valoarea n la nodul curent din arbore, atunci eu sunt 1000 00:43:40,740 --> 00:43:43,370 merge mai departe și punt în celălalt direcție și spun, eu nu fac 1001 00:43:43,370 --> 00:43:47,280 știu dacă această valoare n este în copac, dar știu că dacă este, e în jos meu 1002 00:43:47,280 --> 00:43:49,090 ramura dreapta, ca să spunem așa. 1003 00:43:49,090 --> 00:43:53,120 Deci, lasă-mă apel recursiv căutare, care trece un n din nou, dar care trece într-o 1004 00:43:53,120 --> 00:43:54,580 pointer la copilul meu drept. 1005 00:43:54,580 --> 00:44:00,020 >> Cu alte cuvinte, dacă sunt în prezent la 55 și eu sunt în căutarea de 99, eu știu că 99 1006 00:44:00,020 --> 00:44:04,270 este mai mare de 55, asa ca am rupt de săptămâni cartea de telefon în urmă și am 1007 00:44:04,270 --> 00:44:07,140 a mers bine, la fel suntem merge chiar aici. 1008 00:44:07,140 --> 00:44:11,960 Și nu știu dacă e la dreapta mea copil, și nu este, 77 este acolo, dar 1009 00:44:11,960 --> 00:44:13,210 Știu că e în acea direcție. 1010 00:44:13,210 --> 00:44:18,770 Deci, eu numesc căutare pe copilul meu drept, 77, și să figura căutare de la 1011 00:44:18,770 --> 00:44:24,950 există în cazul în care 99 în această arbitrară exemplu este de fapt acolo. 1012 00:44:24,950 --> 00:44:26,900 >> Altfel, ceea ce este cazul finale? 1013 00:44:26,900 --> 00:44:28,620 Dacă pomul este nul este un caz. 1014 00:44:28,620 --> 00:44:31,890 Dacă n este mai mic nodul curent Valoarea este un alt caz. 1015 00:44:31,890 --> 00:44:35,120 Dacă n este mai mare decât curentul Valoarea nodului este un al treilea caz. 1016 00:44:35,120 --> 00:44:38,250 Care este a patra și ultima situație? 1017 00:44:38,250 --> 00:44:39,480 Cred că suntem de cazuri, nu? 1018 00:44:39,480 --> 00:44:44,690 Trebuie să fie că n este în nodul curent, care sunt pe. 1019 00:44:44,690 --> 00:44:49,640 >> Deci, dacă eu sunt în căutarea pentru 55 la acest punct în poveste, ca ramură a 1020 00:44:49,640 --> 00:44:51,780 copac se va întoarce adevărat. 1021 00:44:51,780 --> 00:44:55,380 Deci, ce e interesant aici este că noi De fapt, spre deosebire de ultimele săptămâni, ne-am cam 1022 00:44:55,380 --> 00:44:56,740 a avea două cauze de bază. 1023 00:44:56,740 --> 00:44:58,300 Și ei nu trebuie să fie în partea de sus. 1024 00:44:58,300 --> 00:45:01,390 În partea de sus este un caz de bază, deoarece în cazul în care copac este nul, nu e nimic de făcut. 1025 00:45:01,390 --> 00:45:03,410 Doar întoarce o codat greu Valoarea de fals. 1026 00:45:03,410 --> 00:45:07,400 >> Ramura de jos este un fel de implicit, prin care dacă le-am verificat pentru 1027 00:45:07,400 --> 00:45:11,550 null, am verificat dacă ar trebui să fie a plecat, dar nu ar trebui să fie, ne-am 1028 00:45:11,550 --> 00:45:14,640 verificat dacă acesta ar trebui să fie corect, dar nu ar trebui să fie, în mod clar trebuie să fie 1029 00:45:14,640 --> 00:45:15,870 chiar unde suntem. 1030 00:45:15,870 --> 00:45:16,780 Asta e un caz de bază. 1031 00:45:16,780 --> 00:45:19,920 Deci, există două cazuri recursive sandwich în mijloc. 1032 00:45:19,920 --> 00:45:21,630 Dar am fi putut scrie aceasta, în orice ordine. 1033 00:45:21,630 --> 00:45:24,520 M-am gândit că un fel de simtit naturale pentru a verifica în primul rând pentru o posibilă eroare, 1034 00:45:24,520 --> 00:45:28,340 apoi verificați stânga, apoi verificați dreapta, apoi Presupun că sunteți la nodul 1035 00:45:28,340 --> 00:45:30,630 sunteți de fapt cautati. 1036 00:45:30,630 --> 00:45:36,240 >> Deci, de ce ar fi acest lucru util? 1037 00:45:36,240 --> 00:45:37,910 Deci, se dovedește - 1038 00:45:37,910 --> 00:45:42,110 și lasă-mă să sari la un teaser aici, că e în web. 1039 00:45:42,110 --> 00:45:44,920 Vom începe să utilizați nu o limbaj de programare la început, dar o 1040 00:45:44,920 --> 00:45:46,030 limbaj de marcare. 1041 00:45:46,030 --> 00:45:48,740 Un limbaj de marcare fiind unul care este similară în spirit de programare 1042 00:45:48,740 --> 00:45:51,715 limba, dar nu vă dau capacitatea de a te exprima în mod logic. 1043 00:45:51,715 --> 00:45:55,070 Este doar vă oferă posibilitatea de a te exprimi structural. 1044 00:45:55,070 --> 00:45:57,960 >> În cazul în care vrei să pui ceva pe pagina, pagina de web? 1045 00:45:57,960 --> 00:45:59,200 Ce culoare vrei să-l facă? 1046 00:45:59,200 --> 00:46:00,950 Ce dimensiunea fontului vrei să-l facă? 1047 00:46:00,950 --> 00:46:02,970 Ce cuvinte vă faceți de fapt doresc de pe pagina de web? 1048 00:46:02,970 --> 00:46:04,060 Deci, asta e un limbaj de marcare. 1049 00:46:04,060 --> 00:46:07,690 Dar atunci vom prezenta foarte repede JavaScript, care este un cu drepturi depline 1050 00:46:07,690 --> 00:46:08,560 limbaj de programare. 1051 00:46:08,560 --> 00:46:12,530 Foarte asemănătoare sintactic în aparență la C, dar va avea unele 1052 00:46:12,530 --> 00:46:15,200 frumos, mai puternic, mai caracteristici ușor de utilizat. 1053 00:46:15,200 --> 00:46:18,050 >> Și unul dintre frustrările în acest punct în semestrul este că vom 1054 00:46:18,050 --> 00:46:22,065 implementa în curând pronuntie în mult mai puține de linii de cod care utilizează alte limbi 1055 00:46:22,065 --> 00:46:25,580 decât C se permite, dar pentru motive de vom înțelege curând. 1056 00:46:25,580 --> 00:46:27,750 Aceasta va fi prima pagina web, cum ar. 1057 00:46:27,750 --> 00:46:30,120 Acesta va fi complet underwhelming, primul facem. 1058 00:46:30,120 --> 00:46:31,400 Acesta va spune pur și simplu, salut lume. 1059 00:46:31,400 --> 00:46:34,010 Dar dacă nu ați mai văzut-o înainte, aceasta este HTML, 1060 00:46:34,010 --> 00:46:35,670 Hypertext Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Dacă te duci la o anumită opțiune de meniu în cele mai multe orice browser, de pe orice pagina web pe 1062 00:46:39,310 --> 00:46:43,160 pe internet, puteți vedea HTML că unii oameni au scris la 1063 00:46:43,160 --> 00:46:44,400 crea acea pagină web. 1064 00:46:44,400 --> 00:46:47,850 Și, probabil, nu arata la fel scurt sau elegant ca acest lucru. 1065 00:46:47,850 --> 00:46:51,400 Dar va urma modelul de acestea paranteze deschise și slash și 1066 00:46:51,400 --> 00:46:53,660 litere și numere potențial. 1067 00:46:53,660 --> 00:46:56,770 >> M-am gândit să vă dau un teaser de ceea ce veți fi în stare să facă 1068 00:46:56,770 --> 00:46:57,950 după luarea CS50. 1069 00:46:57,950 --> 00:47:02,620 Lasă-mă să merg la cs.harvard.edu / Rob, pagina noastră Rob Bowden. 1070 00:47:02,620 --> 00:47:06,080 El a făcut acest lucru pentru noi. 1071 00:47:06,080 --> 00:47:07,490 Astfel încât veți fi în curând posibilitatea de a face acest lucru. 1072 00:47:07,490 --> 00:47:10,660 Și, de asemenea, ceea ce ai auzit în această dimineață - 1073 00:47:10,660 --> 00:47:12,480 ceea ce ai auzit în această dimineață - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER Dance Music] 1075 00:47:13,780 --> 00:47:15,702 >> - Vei fi în măsură să facă acest lucru. 1076 00:47:15,702 --> 00:47:16,790 Care ne așteaptă miercuri. 1077 00:47:16,790 --> 00:47:17,791 Ne veți vedea atunci. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER Dance Music] 1079 00:47:22,950 --> 00:47:24,300 DAVID MALAN: La următoarea CS50 - 1080 00:47:24,300 --> 00:47:31,670