1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [MUSIC JOC] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: În regulă. 5 00:00:12,900 --> 00:00:14,600 Toată lumea bun venit înapoi la pct. 6 00:00:14,600 --> 00:00:18,660 Sper că toate sunt cu succes recuperate de la quiz-ul 7 00:00:18,660 --> 00:00:19,510 de săptămâna trecută. 8 00:00:19,510 --> 00:00:22,564 Știu că e un pic nebun uneori. 9 00:00:22,564 --> 00:00:25,230 Așa cum spuneam mai înainte, dacă ești în abaterea standard, 10 00:00:25,230 --> 00:00:28,188 nu vă faceți griji despre asta, mai ales pentru o secțiune mai puțin confortabil. 11 00:00:28,188 --> 00:00:30,230 Asta e despre unde ar trebui să fie. 12 00:00:30,230 --> 00:00:32,850 >> Dacă ai făcut mare, atunci minunat. 13 00:00:32,850 --> 00:00:33,650 Kudos pentru tine. 14 00:00:33,650 --> 00:00:36,149 Și dacă vă simțiți ca ai nevoie un pic mai mult ajutor, vă rugăm să 15 00:00:36,149 --> 00:00:38,140 nu ezitați să ajungă la la oricare dintre TFS. 16 00:00:38,140 --> 00:00:40,030 Suntem cu toții aici pentru a ajuta. 17 00:00:40,030 --> 00:00:40,960 >> De aceea ne-am preda. 18 00:00:40,960 --> 00:00:44,550 De asta sunt aici în fiecare luni pentru tine tipi și la birou ore în zilele de joi. 19 00:00:44,550 --> 00:00:48,130 Deci, vă rugăm să nu ezitați să să-mi spuneți dacă sunteți îngrijorat de ceva 20 00:00:48,130 --> 00:00:52,450 sau dacă e ceva pe testul de pe care doriți într-adevăr să le abordeze. 21 00:00:52,450 --> 00:00:56,940 >> Astfel, agenda de astăzi este Totul despre structuri de date. 22 00:00:56,940 --> 00:01:01,520 Unele dintre acestea sunt doar de gând să fie doar pentru a vă familiariza cu acestea. 23 00:01:01,520 --> 00:01:04,870 Nu aveți dreptul să pună în aplicare vreodată le în această clasă. 24 00:01:04,870 --> 00:01:08,690 Unele dintre ele va fi, ca pentru PSET ta abecedar. 25 00:01:08,690 --> 00:01:11,380 >> Vei avea alegerea ta între tabele de dispersie și încearcă. 26 00:01:11,380 --> 00:01:13,680 Deci, vom fi cu siguranta merge peste ele. 27 00:01:13,680 --> 00:01:18,690 O să fi cu siguranta mai mult de natură de o secțiune de nivel înalt astăzi, deși, 28 00:01:18,690 --> 00:01:22,630 pentru că există o mulțime de ei, și în cazul în care ne-am dus în detaliile de implementare 29 00:01:22,630 --> 00:01:26,490 pe toate acestea, nu ne-ar chiar obține prin liste postat 30 00:01:26,490 --> 00:01:28,520 și poate un pic de tabele de dispersie. 31 00:01:28,520 --> 00:01:31,200 >> Astfel încât să poarte cu mine. 32 00:01:31,200 --> 00:01:33,530 Noi nu vom face la fel de mult codificare acest timp. 33 00:01:33,530 --> 00:01:36,870 Dacă aveți orice întrebări despre ea sau vrei să-l vadă pus în aplicare 34 00:01:36,870 --> 00:01:39,260 sau încercați să-l pentru tine, Vă recomandăm cu siguranta 35 00:01:39,260 --> 00:01:44,250 O să study.cs50.net, care include exemple de toate acestea. 36 00:01:44,250 --> 00:01:46,400 Va avea PowerPoints mele cu notele pe care le 37 00:01:46,400 --> 00:01:50,860 tind să folosească, precum și unele de programare exerciții, în special pentru lucruri 38 00:01:50,860 --> 00:01:55,250 cum ar fi liste legate și binar copaci stive și indicii. 39 00:01:55,250 --> 00:01:59,590 Deci, puțin mai înalt nivel, care ar fi frumos pentru voi. 40 00:01:59,590 --> 00:02:01,320 >> Deci, cu asta, vom începe. 41 00:02:01,320 --> 00:02:03,060 Și, de asemenea, teste yes--. 42 00:02:03,060 --> 00:02:06,550 Cred ca majoritatea dintre voi care sunt în pct meu avea teste tale, 43 00:02:06,550 --> 00:02:12,060 dar oricine vine în sau dintr-un motiv pe care nu, sunt chiar aici în față. 44 00:02:12,060 --> 00:02:12,740 >> Deci, legate de liste. 45 00:02:12,740 --> 00:02:15,650 Știu că acest tip de trecut în spate, înainte de testul tău. 46 00:02:15,650 --> 00:02:17,940 Asta a fost o săptămână înainte că am aflat despre acest lucru. 47 00:02:17,940 --> 00:02:21,040 Dar, în acest caz, vom doar du-te un pic mai mult în profunzime. 48 00:02:21,040 --> 00:02:25,900 >> Deci, de ce am putea alege un Lista postat pe un tablou? 49 00:02:25,900 --> 00:02:27,130 Ce le deosebește? 50 00:02:27,130 --> 00:02:27,630 Da? 51 00:02:27,630 --> 00:02:30,464 >> Audiența: puteti extinde o legătură afișat față de dimensiune fixă ​​o serie de. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Corect. 53 00:02:31,171 --> 00:02:33,970 O matrice a stabilit mărimea întrucât o Lista de legat are o dimensiune variabilă. 54 00:02:33,970 --> 00:02:36,970 Deci, dacă nu știm cum mult ne-am dori pentru a stoca, 55 00:02:36,970 --> 00:02:39,880 o listă legat ne ofera o mare mod de a face acest lucru pentru că putem pur și simplu 56 00:02:39,880 --> 00:02:43,730 adauga un alt nod și se adaugă la un alt nod și se adaugă pe un alt nod. 57 00:02:43,730 --> 00:02:45,750 Dar ceea ce ar putea fi un compromis? 58 00:02:45,750 --> 00:02:49,521 Are cineva aminte de trade-off între tablouri și liste postat? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> Audiența: Trebuie sa du-te prin tot drumul 61 00:02:51,460 --> 00:02:53,738 prin listă legată găsi un element într-o listă. 62 00:02:53,738 --> 00:02:55,570 Într-o matrice, puteți găsi doar un element. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Corect. 64 00:02:56,278 --> 00:02:57,120 Deci, cu arrays-- 65 00:02:57,120 --> 00:02:58,500 >> Audiența: [inaudibil]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: Cu tablouri, avem ceea ce se numește acces aleator. 67 00:03:01,090 --> 00:03:04,820 Înseamnă că, dacă vrem ceea ce este vreodată cincilea punct a unei liste 68 00:03:04,820 --> 00:03:07,230 sau al cincilea punct de nostru matrice, putem doar să-l apuca. 69 00:03:07,230 --> 00:03:10,440 Daca este o listă legată, avem pentru a itera prin, nu? 70 00:03:10,440 --> 00:03:14,020 Deci accesarea unui element din o matrice este constanta de timp, 71 00:03:14,020 --> 00:03:19,530 întrucât cu o listă legat ea ar fi cel mai probabil sa fie timp liniar, deoarece poate 72 00:03:19,530 --> 00:03:21,370 elementul nostru este tot drumul la sfârșitul anului. 73 00:03:21,370 --> 00:03:23,446 Trebuie să căutați prin toate. 74 00:03:23,446 --> 00:03:25,320 Deci, cu toate aceste date Structurile le vom 75 00:03:25,320 --> 00:03:29,330 pentru a petrece un pic mai mult timp pe, Care sunt plusurile si negative. 76 00:03:29,330 --> 00:03:31,480 Când s-ar putea vrem să utilizați una peste alta? 77 00:03:31,480 --> 00:03:34,970 Și asta e un fel de lucru mai mare pentru a ține departe. 78 00:03:34,970 --> 00:03:40,140 >> Deci, avem aici definiție a unui nod. 79 00:03:40,140 --> 00:03:43,040 E ca și cum un element în Lista noastră legată, nu? 80 00:03:43,040 --> 00:03:46,180 Deci suntem toți familiarizați cu structs noastre typedef, 81 00:03:46,180 --> 00:03:47,980 care ne-am dus peste în comentariu ultimul timp. 82 00:03:47,980 --> 00:03:53,180 A fost practic doar crearea de un alt tip de date pe care le-ar putea folosi. 83 00:03:53,180 --> 00:03:57,930 >> Și în acest caz, e un nod care va organiza unele întreg în. 84 00:03:57,930 --> 00:04:00,210 Și atunci ce e de-a doua parte aici? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Oricine? 87 00:04:05,677 --> 00:04:06,680 >> Audiența: [inaudibil]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Da. 89 00:04:07,020 --> 00:04:08,400 Este un pointer la nodul următor. 90 00:04:08,400 --> 00:04:12,610 Deci, acest lucru ar trebui să fie de fapt aici. 91 00:04:12,610 --> 00:04:18,790 Acesta este un pointer de tip nod la următorul lucru. 92 00:04:18,790 --> 00:04:22,410 Și asta e ceea ce ei cuprinde nod nostru. 93 00:04:22,410 --> 00:04:24,060 Rece. 94 00:04:24,060 --> 00:04:29,390 >> În regulă, deci cu căutare, așa cum am fost doar că înainte de mână, dacă ești 95 00:04:29,390 --> 00:04:31,840 de gând să caute prin, trebuie sa repeta de fapt 96 00:04:31,840 --> 00:04:33,660 prin lista de legat. 97 00:04:33,660 --> 00:04:38,530 Deci, dacă ne uităm la numărul 9, ne-ar incepe de la capul nostru 98 00:04:38,530 --> 00:04:41,520 și care ne arată la început din lista noastră de legat, nu? 99 00:04:41,520 --> 00:04:44,600 Și noi spunem, OK, face acest lucru nod conține numărul 9? 100 00:04:44,600 --> 00:04:45,690 Nu? 101 00:04:45,690 --> 00:04:47,500 >> Bine, du-te la următorul. 102 00:04:47,500 --> 00:04:48,312 Urmareste-l. 103 00:04:48,312 --> 00:04:49,520 Nu conține numărul 9? 104 00:04:49,520 --> 00:04:50,570 Nu. 105 00:04:50,570 --> 00:04:51,550 Urmați următoarea. 106 00:04:51,550 --> 00:04:55,490 >> Deci, avem de a repeta de fapt prin lista noastră de legat. 107 00:04:55,490 --> 00:05:00,070 Nu putem merge direct la unde 9 este. 108 00:05:00,070 --> 00:05:05,860 Și dacă vreți de fapt să a se vedea unii pseudo-cod acolo. 109 00:05:05,860 --> 00:05:10,420 Avem o funcție de căutare aici care ia in-- ceea ce nu-l ia în? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Ce părere ai? 112 00:05:14,320 --> 00:05:15,960 O atât de ușor. 113 00:05:15,960 --> 00:05:17,784 Ce este aceasta? 114 00:05:17,784 --> 00:05:18,700 Audiența: [inaudibil]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: Numărul căutăm. 116 00:05:20,366 --> 00:05:20,980 Dreapta? 117 00:05:20,980 --> 00:05:22,875 Și ce ar corespunde asta? 118 00:05:22,875 --> 00:05:25,020 Este un pointer la? 119 00:05:25,020 --> 00:05:26,000 >> Audiența: Un nod. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: Un nod la lista care ne uitam la, dreapta? 121 00:05:28,980 --> 00:05:33,700 Deci, avem unele noduri sunt pointer aici. 122 00:05:33,700 --> 00:05:37,240 Acesta este un punct care va de fapt repeta prin lista noastră. 123 00:05:37,240 --> 00:05:39,630 Ne-am propus aceasta egală cu lista pentru că asta e doar 124 00:05:39,630 --> 00:05:44,380 stabilind-o egală cu începe din lista noastră legată. 125 00:05:44,380 --> 00:05:50,660 >> Și în timp ce nu e NULL, în timp ce mai avem încă lucruri în lista noastră, 126 00:05:50,660 --> 00:05:55,580 verificați pentru a vedea dacă acel nod are numărul căutăm. 127 00:05:55,580 --> 00:05:57,740 Întoarcere adevărat. 128 00:05:57,740 --> 00:06:01,070 În caz contrar, actualizare, corect? 129 00:06:01,070 --> 00:06:04,870 >> Dacă este NULL, ne-am ieși nostru în timp ce buclă și return false 130 00:06:04,870 --> 00:06:08,340 pentru că asta înseamnă că nu l-am găsit. 131 00:06:08,340 --> 00:06:11,048 Are toată lumea primi cum functioneaza? 132 00:06:11,048 --> 00:06:11,548 OK. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Deci, cu inserție, voi au trei moduri diferite. 135 00:06:20,260 --> 00:06:25,250 Aveți posibilitatea să adauge, puteți adăuga și aveți posibilitatea să inserați în asortate. 136 00:06:25,250 --> 00:06:28,215 În acest caz, suntem de gând să faci o pune prefix. 137 00:06:28,215 --> 00:06:33,380 Stie cineva cum cei trei cazuri s-ar putea diferi? 138 00:06:33,380 --> 00:06:36,920 >> Astfel Prefixeaza înseamnă că ai pus se la partea din față a listei. 139 00:06:36,920 --> 00:06:39,770 Deci, aceasta ar însemna că, indiferent de ce nodul este, indiferent de 140 00:06:39,770 --> 00:06:43,160 ce valoarea este, te duci să-l pună chiar aici în față, OK? 141 00:06:43,160 --> 00:06:45,160 O să fie primul element din lista ta. 142 00:06:45,160 --> 00:06:49,510 >> Dacă îl adăugați, va pentru a merge la partea din spate a listei. 143 00:06:49,510 --> 00:06:54,010 Și introduceți în asortate înseamnă că ești va pune de fapt în locul 144 00:06:54,010 --> 00:06:57,700 în cazul în care se păstrează lista de legat sortate. 145 00:06:57,700 --> 00:07:00,810 Din nou, modul în care utilizați cei care și atunci când utilizați 146 00:07:00,810 --> 00:07:02,530 le va varia în funcție de cazul dumneavoastră. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 În cazul în care nu are nevoie să fi sortate, Prefixeaza tinde 149 00:07:07,750 --> 00:07:10,460 a fi ceea ce majoritatea oamenilor utilizați pentru că tu nu faci 150 00:07:10,460 --> 00:07:15,680 trebuie să treacă prin întreaga listă pentru a găsi sfârșitul adauga, nu? 151 00:07:15,680 --> 00:07:17,720 Puteți să-l lipi imediat. 152 00:07:17,720 --> 00:07:21,930 >> Deci, vom merge printr-o inserție 1 chiar acum. 153 00:07:21,930 --> 00:07:26,360 Deci, un lucru pe care am de gând să Recomand cu privire la acest PSET 154 00:07:26,360 --> 00:07:29,820 este de a atrage lucrurile, ca întotdeauna. 155 00:07:29,820 --> 00:07:35,130 Este foarte important să vă actualizați indicii dvs. în ordinea corectă 156 00:07:35,130 --> 00:07:38,620 pentru că dacă le actualizați usor de ordine, 157 00:07:38,620 --> 00:07:42,210 vei pune a pierde părți din lista ta. 158 00:07:42,210 --> 00:07:49,680 >> Deci, de exemplu, în acest caz, suntem spune capul la doar punctul 1. 159 00:07:49,680 --> 00:07:56,070 Dacă ne-am face asta fără a salva acest 1, 160 00:07:56,070 --> 00:07:58,570 nu avem nici o idee despre ceea ce 1 ar trebui să indice acum 161 00:07:58,570 --> 00:08:02,490 pentru că ne-am pierdut ceea ce capul de subliniat. 162 00:08:02,490 --> 00:08:05,530 Deci, un singur lucru să-și amintească când faci un Prefixeaza 163 00:08:05,530 --> 00:08:09,630 este de a salva ceea ce puncte de cap de la primul, 164 00:08:09,630 --> 00:08:15,210 apoi le retrocedeze, și apoi să actualizeze ce noul nod ar trebui să indice. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 În acest caz, aceasta este o modalitate de a face acest lucru. 167 00:08:22,560 --> 00:08:25,440 >> Deci, dacă am fi făcut-o în acest fel în cazul în care ne-am realocat cap, 168 00:08:25,440 --> 00:08:30,320 ne-am pierde practic nostru Întreaga listă, nu? 169 00:08:30,320 --> 00:08:38,000 O modalitate de a face acest lucru este de a avea un punct de următor, iar apoi au punctul cap la 1. 170 00:08:38,000 --> 00:08:42,650 Sau poti face un fel de depozitarea temporară, pe care am vorbit despre. 171 00:08:42,650 --> 00:08:45,670 >> Dar realocarea ta indicii în ordinea corectă 172 00:08:45,670 --> 00:08:48,750 va fi foarte, foarte important pentru acest PSET. 173 00:08:48,750 --> 00:08:53,140 În caz contrar, vei avea un hash tabel sau o încercare care este doar de gând să fie 174 00:08:53,140 --> 00:08:56,014 doar o parte din cuvintele pe care le doresc și apoi Mmhmm ​​you're--? 175 00:08:56,014 --> 00:08:58,930 Audiența: Care a fost temporar lucru de stocare vorbeai despre? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: stocarea temporară. 177 00:09:00,305 --> 00:09:02,760 Deci, practic un alt fel ai putea face acest lucru 178 00:09:02,760 --> 00:09:07,650 se păstra capul de ceva, cum ar fi depozitați-l variabila temporar. 179 00:09:07,650 --> 00:09:11,250 Aloca la 1 și apoi actualizați 1 de la punctul 180 00:09:11,250 --> 00:09:13,830 la orice cap de folosit pentru a indica. 181 00:09:13,830 --> 00:09:16,920 În acest fel este, evident, mai elegant pentru că 182 00:09:16,920 --> 00:09:20,770 nu au nevoie de o valoare temporar, dar oferind doar un alt mod de a face acest lucru. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 Și noi, de fapt nu au un cod pentru acest lucru. 185 00:09:25,790 --> 00:09:28,080 Deci, pentru lista legate, noi de fapt, au un cod. 186 00:09:28,080 --> 00:09:31,930 Deci, se introduce aici, acest lucru este precedarea. 187 00:09:31,930 --> 00:09:34,290 Deci, aceasta intră în cap. 188 00:09:34,290 --> 00:09:38,820 >> Deci, primul lucru, aveți nevoie pentru a a crea noua nod, desigur, 189 00:09:38,820 --> 00:09:40,790 și verificați pentru NULL. 190 00:09:40,790 --> 00:09:43,250 Intotdeauna bine. 191 00:09:43,250 --> 00:09:47,840 Și atunci ai nevoie pentru a atribui valori. 192 00:09:47,840 --> 00:09:51,260 Ori de câte ori creați un nou nod, tu Nu știu ce se indică spre viitor, 193 00:09:51,260 --> 00:09:54,560 astfel încât pe care doriți să-l inițializa la NULL. 194 00:09:54,560 --> 00:09:58,760 În cazul în care se pune indică spre ceva altfel, acesta devine realocată și e bine. 195 00:09:58,760 --> 00:10:00,740 În cazul în care e primul lucru în listă, de care are nevoie 196 00:10:00,740 --> 00:10:04,270 să indice NULL deoarece că la scos de pe lista. 197 00:10:04,270 --> 00:10:12,410 >> Deci, atunci să-l introduceți, vom vedea aici ne sunt atribuirea următoarea valoare a nodului noastre 198 00:10:12,410 --> 00:10:17,380 a fi orice cap este, care este ceea ce am avut aici. 199 00:10:17,380 --> 00:10:19,930 Asta e ceea ce am făcut. 200 00:10:19,930 --> 00:10:25,820 Și apoi ne atribuirea cap la litera la noul nostru nod, pentru că amintiți-vă, 201 00:10:25,820 --> 00:10:31,090 noi este un pointer la un nod, și asta este exact ceea ce este șeful. 202 00:10:31,090 --> 00:10:34,370 Tocmai de aceea noi au această săgeată accessor. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Rece? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> Audiența: Nu trebuie să ne inițializa nou alături de NULL în primul rând, 207 00:10:41,100 --> 00:10:44,240 sau putem doar inițializa la cap? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: New next trebuie să fie NULL pentru a începe 209 00:10:48,210 --> 00:10:53,760 pentru că nu știi în cazul în care va fi. 210 00:10:53,760 --> 00:10:56,100 De asemenea, acest este un fel de la fel ca o paradigmă. 211 00:10:56,100 --> 00:10:59,900 Poti seta o egală cu NULL doar pentru a face -vă că toate bazele sunt acoperite 212 00:10:59,900 --> 00:11:04,070 înainte de a face orice schimbare de astfel încât esti mereu garantat că va 213 00:11:04,070 --> 00:11:08,880 fie îndreptată către o anumită valoare versus ca o valoare de gunoi. 214 00:11:08,880 --> 00:11:12,210 Pentru că, da, am atribui în mod automat nouă următoare, 215 00:11:12,210 --> 00:11:15,420 dar e mai mult ca o bune practici pentru a inițializa 216 00:11:15,420 --> 00:11:19,270 în acest fel și apoi realocați. 217 00:11:19,270 --> 00:11:23,420 >> OK, deci de două ori legate de listele de acum. 218 00:11:23,420 --> 00:11:24,601 Ce credem noi? 219 00:11:24,601 --> 00:11:26,350 Ce este diferit cu postat de două ori liste? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Deci, în listele noastre legate, putem muta doar într-o singură direcție, nu? 222 00:11:34,300 --> 00:11:35,270 Avem doar urmator. 223 00:11:35,270 --> 00:11:36,760 Putem merge doar înainte. 224 00:11:36,760 --> 00:11:40,300 >> Cu o listă de două ori legate, De asemenea, ne putem muta înapoi. 225 00:11:40,300 --> 00:11:44,810 Deci avem nu numai Numărul de pe care ne-o dorim pentru a stoca, 226 00:11:44,810 --> 00:11:50,110 avem în cazul în care se indică următor și unde tocmai am venit de la. 227 00:11:50,110 --> 00:11:52,865 Deci, aceasta permite unele traversal mai bine. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Noduri astfel de două ori legate, foarte asemănătoare, nu? 230 00:12:01,240 --> 00:12:05,000 Singura diferență este acum ne au un viitor și o anterior. 231 00:12:05,000 --> 00:12:06,235 E singura diferență. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Deci, dacă ar fi să adauge sau append-- noi nu au nici un cod pentru asta here-- 234 00:12:14,790 --> 00:12:17,830 dar dacă ar fi să încercați și introduceți-l, cel mai important lucru 235 00:12:17,830 --> 00:12:19,980 este de care aveți nevoie pentru a face -vă că atribuirea 236 00:12:19,980 --> 00:12:23,360 atât anterior și dumneavoastră următor pointer corect. 237 00:12:23,360 --> 00:12:29,010 Deci, în acest caz, ar trebui să nu numai inițializa următor, 238 00:12:29,010 --> 00:12:31,820 ați inițializat anterior. 239 00:12:31,820 --> 00:12:36,960 Dacă suntem în fruntea listei, ne-am ar face nu numai cu capul egal nou, 240 00:12:36,960 --> 00:12:41,750 dar ar trebui noul nostru precedent punctul de cap, nu? 241 00:12:41,750 --> 00:12:43,380 >> Asta e singura diferență. 242 00:12:43,380 --> 00:12:47,200 Și dacă vrei mai mult practică cu acestea cu liste postat, cu inserarea, 243 00:12:47,200 --> 00:12:49,900 cu ștergerea, cu inserție într-o listă asortate, 244 00:12:49,900 --> 00:12:52,670 vă rugăm să verificați study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Există o grămadă de exerciții mari. 246 00:12:54,870 --> 00:12:55,870 Am foarte recomanda-le. 247 00:12:55,870 --> 00:12:59,210 Aș vrea să avem timp pentru a merge prin intermediul lor dar există o mulțime de structuri de date 248 00:12:59,210 --> 00:13:01,530 pentru a obține prin intermediul. 249 00:13:01,530 --> 00:13:02,650 >> OK, deci tabele de dispersie. 250 00:13:02,650 --> 00:13:07,070 Aceasta este, probabil, cel mai bit util pentru PSET ta 251 00:13:07,070 --> 00:13:11,090 aici pentru că ai de gând să fie de punere în aplicare una dintre acestea, sau o încercare. 252 00:13:11,090 --> 00:13:12,200 Îmi place foarte mult tabele de dispersie. 253 00:13:12,200 --> 00:13:13,110 Sunt destul de rece. 254 00:13:13,110 --> 00:13:17,080 >> Deci, practic ceea ce ce se întâmplă este o tabelă de dispersie 255 00:13:17,080 --> 00:13:22,050 este atunci când într-adevăr avem nevoie rapid inserare, ștergere, și de căutare. 256 00:13:22,050 --> 00:13:25,010 Acestea sunt lucrurile pe care suntem prioritate într-un tabel hash. 257 00:13:25,010 --> 00:13:29,500 Ei pot obține destul de mare, dar așa cum vom vedea cu nereușite, 258 00:13:29,500 --> 00:13:33,040 sunt lucruri care sunt mult mai mari. 259 00:13:33,040 --> 00:13:38,330 >> Dar, practic, toate un hash masă este o funcție hash 260 00:13:38,330 --> 00:13:47,215 care vă spune ce găleată pentru a pune fiecare a datelor, fiecare dintre elementele dvs. în. 261 00:13:47,215 --> 00:13:51,140 Un mod simplu de a gândi al unui tabel hash este faptul că este doar găleți de lucruri, 262 00:13:51,140 --> 00:13:51,770 dreapta? 263 00:13:51,770 --> 00:13:59,720 Deci, atunci când sunt sortarea lucruri de la fel ca prima literă a numelui lor, 264 00:13:59,720 --> 00:14:01,820 asta e un fel de tabel hash. 265 00:14:01,820 --> 00:14:06,180 >> Deci, voi, dacă ar fi să grup este în grupuri de cel care începe numele lui 266 00:14:06,180 --> 00:14:11,670 cu un peste de aici, sau oricine e ziua de nastere este în lunile ianuarie, februarie, martie, 267 00:14:11,670 --> 00:14:15,220 indiferent, care este efectiv crearea unui tabel hash. 268 00:14:15,220 --> 00:14:18,120 E doar crearea de pistoane care să sortați elementele dvs. 269 00:14:18,120 --> 00:14:19,520 astfel încât să puteți găsi mai ușor. 270 00:14:19,520 --> 00:14:22,300 Deci, în acest fel, atunci când am nevoie pentru a găsi unul dintre voi, 271 00:14:22,300 --> 00:14:24,680 Nu trebuie să căutați prin fiecare dintre numele voastre. 272 00:14:24,680 --> 00:14:29,490 Pot fi ca, oh, știu că Ziua de nastere Danielle este in-- 273 00:14:29,490 --> 00:14:30,240 Audiența: --April. 274 00:14:30,240 --> 00:14:30,948 SPEAKER 1: Aprilie. 275 00:14:30,948 --> 00:14:33,120 Așa că mă uit în aprilie meu găleată, și cu puțin noroc, 276 00:14:33,120 --> 00:14:38,270 ea va fi singura acolo și timpul meu a fost constant în acest sens, 277 00:14:38,270 --> 00:14:41,230 întrucât dacă am să uite printr-o grămadă de oameni, 278 00:14:41,230 --> 00:14:43,090 o să dureze mult mai mult. 279 00:14:43,090 --> 00:14:45,830 Deci, tabele de dispersie sunt într-adevăr doar găleți. 280 00:14:45,830 --> 00:14:48,630 Modalitate ușoară de a ne gândim la ei. 281 00:14:48,630 --> 00:14:52,930 >> Deci, un lucru foarte important despre un tabel hash este o funcție hash. 282 00:14:52,930 --> 00:14:58,140 Deci, lucrurile pe care tocmai am vorbit despre, cum ar fi prima scrisoare de prenumele dvs. 283 00:14:58,140 --> 00:15:01,450 sau lună ziua ta de nastere, acestea sunt idei care 284 00:15:01,450 --> 00:15:03,070 într-adevăr corelate cu o funcție hash. 285 00:15:03,070 --> 00:15:08,900 E doar un mod de a decide care tu cupă element de bază ajungând în, OK? 286 00:15:08,900 --> 00:15:14,850 Deci, pentru acest PSET, poti sa te uiti în sus destul de mult orice funcție hash doriți. 287 00:15:14,850 --> 00:15:16,030 >> Nu trebuie sa fii propriul tau. 288 00:15:16,030 --> 00:15:21,140 Există unele foarte cool afară acolo că face tot felul de matematica nebun. 289 00:15:21,140 --> 00:15:25,170 Și dacă doriți pentru a face spellchecker super rapid, 290 00:15:25,170 --> 00:15:27,620 Mi-ar siguranta uita-te într-una din cele. 291 00:15:27,620 --> 00:15:32,390 >> Dar există, de asemenea, cele simple, cum ar fi de calcul 292 00:15:32,390 --> 00:15:39,010 suma cuvinte, cum ar fi fiecare literă are un număr. 293 00:15:39,010 --> 00:15:39,940 Calcula suma. 294 00:15:39,940 --> 00:15:42,230 Care determină găleată. 295 00:15:42,230 --> 00:15:45,430 Ei au, de asemenea, cei care ușor sunt la fel ca toate din aici, 296 00:15:45,430 --> 00:15:47,050 toate B e aici. 297 00:15:47,050 --> 00:15:48,920 Oricare dintre cele. 298 00:15:48,920 --> 00:15:55,770 >> Practic, doar vă spune care index matrice elementul tau ar trebui să meargă în. 299 00:15:55,770 --> 00:15:58,690 Doar decide bucket-- totul este o funcție hash este. 300 00:15:58,690 --> 00:16:04,180 Deci, aici avem un exemplu care este doar prima literă a șirului 301 00:16:04,180 --> 00:16:05,900 care tocmai am vorbit despre. 302 00:16:05,900 --> 00:16:11,900 >> Deci, aveți unele hash că e doar prima literă a ta string minus A, 303 00:16:11,900 --> 00:16:16,090 care vă va oferi o număr între 0 și 25. 304 00:16:16,090 --> 00:16:20,790 Și ce doriți să faceți este să asigurați-vă că aceasta reprezintă 305 00:16:20,790 --> 00:16:24,110 dimensiunea hash-ul table-- cât de multe cupe există. 306 00:16:24,110 --> 00:16:25,860 Cu multe dintre acestea funcții hash, sunt 307 00:16:25,860 --> 00:16:31,630 va fi întoarce valori care s-ar putea fi cu mult mai mare decât numărul de cupe 308 00:16:31,630 --> 00:16:33,610 că aveți de fapt în tabel hash, 309 00:16:33,610 --> 00:16:37,240 astfel încât aveți nevoie pentru a face sigur și Mod de cei. 310 00:16:37,240 --> 00:16:42,190 În caz contrar, se va spune, oh, ar trebui să fie în găleată 5000 311 00:16:42,190 --> 00:16:46,040 dar ai doar 30 pistoane din masa ta de dispersie. 312 00:16:46,040 --> 00:16:49,360 Și, desigur, știm cu toții că e va duce la unele erori nebun. 313 00:16:49,360 --> 00:16:52,870 Deci, asigurați-vă că Mod de către mărime din masa ta hash. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Rece. 316 00:16:58,930 --> 00:17:00,506 Astfel de coliziuni. 317 00:17:00,506 --> 00:17:02,620 E toată lumea bine până acum? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> Audiența: De ce ar fi a reveni astfel de o valoare masiv? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: În funcție de algoritmul că funcția hash juca. 321 00:17:09,210 --> 00:17:12,270 Unii dintre ei se va face multiplicare nebun. 322 00:17:12,270 --> 00:17:16,270 Și este vorba de asistent o distribuție uniformă, 323 00:17:16,270 --> 00:17:18,490 astfel încât acestea să fac ceva într-adevăr lucruri nebunești uneori. 324 00:17:18,490 --> 00:17:20,960 Asta e tot. 325 00:17:20,960 --> 00:17:22,140 Altceva? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Astfel de coliziuni. 328 00:17:24,480 --> 00:17:29,270 Practic, așa cum am spus mai devreme, în cel mai bun caz, 329 00:17:29,270 --> 00:17:32,040 orice găleată mă uit în e Va trebui un singur lucru, 330 00:17:32,040 --> 00:17:34,160 așa că nu trebuie să se uite la toate, nu? 331 00:17:34,160 --> 00:17:37,040 Eu fie Știu că e acolo sau e Nu, și asta e ceea ce ne dorim cu adevarat. 332 00:17:37,040 --> 00:17:43,960 Dar dacă avem zeci de mii de puncte de date și mai mică decât cea număr 333 00:17:43,960 --> 00:17:48,700 de cupe, vom avea coliziuni în cazul în care în cele din urmă ceva 334 00:17:48,700 --> 00:17:54,210 va trebui să se încheie cu un găleată care are deja un element. 335 00:17:54,210 --> 00:17:57,390 >> Deci, întrebarea este, ce facem în acest caz? 336 00:17:57,390 --> 00:17:58,480 Ce facem? 337 00:17:58,480 --> 00:17:59,300 Avem deja ceva acolo? 338 00:17:59,300 --> 00:18:00,060 Nu ne-am arunca afară? 339 00:18:00,060 --> 00:18:00,700 >> Nu. 340 00:18:00,700 --> 00:18:01,980 Noi trebuie să ținem amândoi. 341 00:18:01,980 --> 00:18:06,400 Deci, modul în care ne-am de obicei face asta este ceea ce? 342 00:18:06,400 --> 00:18:08,400 Care este structura de date ne-am vorbit despre? 343 00:18:08,400 --> 00:18:09,316 Audiența: Lista de legat. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: O listă legat. 345 00:18:10,500 --> 00:18:16,640 Așa că acum, în loc de fiecare dintre acestea Cupe cu doar un element, 346 00:18:16,640 --> 00:18:24,020 aceasta va conține o listă legată de elementele care au fost distribuit în ea. 347 00:18:24,020 --> 00:18:27,588 OK, nu toată lumea un fel de a obține această idee? 348 00:18:27,588 --> 00:18:30,546 Pentru că nu am putut avea un tablou pentru că nu știm cât de multe lucruri 349 00:18:30,546 --> 00:18:31,730 vor fi acolo. 350 00:18:31,730 --> 00:18:36,540 O listă legată ne permite să au doar numărul exact care 351 00:18:36,540 --> 00:18:38,465 sunt distribuit în acea găleată, nu? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Deci, liniar palpare este practic această idee, 354 00:18:50,500 --> 00:18:52,300 este un mod de a face cu o coliziune. 355 00:18:52,300 --> 00:18:58,010 Ce puteți face este în cazul în care, în acest caz, boabe a fost distribuit în 1 356 00:18:58,010 --> 00:19:01,130 și avem deja ceva acolo, doar 357 00:19:01,130 --> 00:19:04,840 menține merge în jos până la veți găsi un slot gol. 358 00:19:04,840 --> 00:19:06,370 Asta e un fel să-l ocupe. 359 00:19:06,370 --> 00:19:09,020 Un alt mod de a gestiona este cu ceea ce tocmai am 360 00:19:09,020 --> 00:19:12,280 called-- legată Lista este numit înlănțuire. 361 00:19:12,280 --> 00:19:20,510 >> Deci, această idee funcționează în cazul în care masa ta hash crezi 362 00:19:20,510 --> 00:19:24,150 este mult mai mare decât datele stabilite sau dacă 363 00:19:24,150 --> 00:19:28,870 doriți să încercați și pentru a minimiza înlănțuirea până când este absolut necesar. 364 00:19:28,870 --> 00:19:34,050 Deci, un lucru este liniar palpare înseamnă, evident, 365 00:19:34,050 --> 00:19:37,290 că funcția hash nu este la fel de util 366 00:19:37,290 --> 00:19:42,200 pentru că ai de gând să ajunge cu ajutorul funcția hash, ajunge la un punct, 367 00:19:42,200 --> 00:19:46,400 tu Linear sonda până la un loc care este disponibil. 368 00:19:46,400 --> 00:19:49,670 Dar acum, desigur, nimic altceva care se termină acolo sus, 369 00:19:49,670 --> 00:19:52,050 ai de gând să trebuie să caută chiar mai jos. 370 00:19:52,050 --> 00:19:55,650 >> Și există o mult mai mult cheltuieli de căutare care 371 00:19:55,650 --> 00:19:59,820 merge în introducerea unui element din tabelul hash acum, nu? 372 00:19:59,820 --> 00:20:05,640 Și acum, când te duci și să încercați și de a găsi bacă din nou, ai de gând să-l hash, 373 00:20:05,640 --> 00:20:07,742 și-l va spune, oh, uita-te la găleată 1, 374 00:20:07,742 --> 00:20:09,700 și nu va fi în găleată 1, deci ești 375 00:20:09,700 --> 00:20:11,970 Va trebui să traverseze prin restul de acestea. 376 00:20:11,970 --> 00:20:17,720 Deci, este uneori util, dar în cele mai multe cazuri, 377 00:20:17,720 --> 00:20:22,660 vom spune că înlănțuirii este ceea ce vrei sa faci. 378 00:20:22,660 --> 00:20:25,520 >> Așa că am vorbit despre acest lucru mai devreme. 379 00:20:25,520 --> 00:20:27,812 Am un pic înainte de mine. 380 00:20:27,812 --> 00:20:33,560 Dar înlănțuirea este, în principiu faptul că fiecare compartiment în tabel hash 381 00:20:33,560 --> 00:20:36,120 este doar o listă legat. 382 00:20:36,120 --> 00:20:39,660 >> Deci, un alt mod, sau mai tehnic Astfel, să se gândească la un tabel hash 383 00:20:39,660 --> 00:20:44,490 este că este doar o matrice de liste legate, care 384 00:20:44,490 --> 00:20:49,330 atunci când scrii în dicționarul ta și încerci să-l încarce, 385 00:20:49,330 --> 00:20:52,070 gândire de ea ca o serie de liste postat 386 00:20:52,070 --> 00:20:54,390 va face mult mai ușor pentru tine pentru a inițializa. 387 00:20:54,390 --> 00:20:57,680 >> Audiența: Deci tabelă de dispersie are o dimensiune predeterminată, 388 00:20:57,680 --> 00:20:58,980 ca un [inaudibil] de cupe? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Corect. 390 00:20:59,220 --> 00:21:01,655 Deci, ea are un anumit număr de găleți pe care le determine-- 391 00:21:01,655 --> 00:21:03,530 care voi ar trebui nu ezitați să se joace cu. 392 00:21:03,530 --> 00:21:05,269 Ea poate fi destul de cool pentru a vedea ce se întâmplă 393 00:21:05,269 --> 00:21:06,810 cum ai schimba numărul dvs. de pistoane. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Dar da, are un setați numărul de compartimente. 396 00:21:11,510 --> 00:21:15,360 Ce vă permite pentru a se potrivi la fel de multe elemente ca ai nevoie 397 00:21:15,360 --> 00:21:19,350 este această înlănțuire separat tu unde au legat liste în fiecare compartiment. 398 00:21:19,350 --> 00:21:22,850 Asta înseamnă că masa ta de dispersie va fi exact la dimensiune 399 00:21:22,850 --> 00:21:25,440 că ai nevoie de ea să fie, nu? 400 00:21:25,440 --> 00:21:27,358 Asta e ideea de liste legate. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Rece. 403 00:21:32,480 --> 00:21:38,780 >> Astfel încât toată lumea în regulă acolo? 404 00:21:38,780 --> 00:21:39,801 Bine. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Ce sa întâmplat? 407 00:21:41,860 --> 00:21:42,960 Într-adevăr acum. 408 00:21:42,960 --> 00:21:45,250 Ghici cineva mă omoară. 409 00:21:45,250 --> 00:21:52,060 >> OK vom intra în incearca, care sunt un pic nebun. 410 00:21:52,060 --> 00:21:53,140 Îmi place tabele de dispersie. 411 00:21:53,140 --> 00:21:54,460 Cred că sunt foarte cool. 412 00:21:54,460 --> 00:21:56,710 Încercări sunt cool, prea. 413 00:21:56,710 --> 00:21:59,590 >> Deci, nimeni nu amintesc ce o încercați este? 414 00:21:59,590 --> 00:22:01,740 Tu ar trebui să fi mers peste l scurt în curs? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Îți amintești fel de cum funcționează? 417 00:22:06,377 --> 00:22:08,460 Audiența: Eu doar din cap că ne-am dus peste el. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: Noi mergem peste el. 419 00:22:09,626 --> 00:22:13,100 OK, suntem într-adevăr de gând să meargă peste acum este ceea ce spunem. 420 00:22:13,100 --> 00:22:14,860 >> Audiența: Asta-i pentru un copac regăsire. 421 00:22:14,860 --> 00:22:15,280 >> SPEAKER 1: Da. 422 00:22:15,280 --> 00:22:16,196 Este un copac regăsire. 423 00:22:16,196 --> 00:22:16,960 Minunat. 424 00:22:16,960 --> 00:22:23,610 Deci, un lucru de observat aici este că noi se uita la caractere individuale 425 00:22:23,610 --> 00:22:24,480 aici, nu? 426 00:22:24,480 --> 00:22:29,710 >> Deci, înainte cu funcția noastră hash, ne-am s-au uitat la cuvintele ca un întreg, 427 00:22:29,710 --> 00:22:32,270 iar acum suntem în căutarea mai mult la personajele, nu? 428 00:22:32,270 --> 00:22:38,380 Deci avem Maxwell aici și Mendel. 429 00:22:38,380 --> 00:22:47,840 Deci, practic un try-- un mod de a gândi despre acest lucru este faptul că fiecare nivel aici 430 00:22:47,840 --> 00:22:49,000 este o serie de litere. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Deci, aceasta este nodul rădăcină aici, nu? 433 00:22:55,790 --> 00:23:01,980 Acest lucru are toate caracterele din alfabet pentru începutul fiecărui cuvânt. 434 00:23:01,980 --> 00:23:06,480 >> Și ce doriți să faceți este să să zicem, OK, avem un cuvânt M. 435 00:23:06,480 --> 00:23:10,590 Ne vom uita pentru Maxwell, așa vom merge la M. și M puncte la un întreg 436 00:23:10,590 --> 00:23:14,800 alte o matrice în care fiecare cuvânt, atâta timp cât există 437 00:23:14,800 --> 00:23:17,044 este un cuvânt care are un ca a doua literă, 438 00:23:17,044 --> 00:23:19,460 atâta timp cât nu există un cuvânt care are B ca a doua literă, 439 00:23:19,460 --> 00:23:24,630 aceasta va avea un pointer merge într-o anumită matrice următor. 440 00:23:24,630 --> 00:23:29,290 >> Probabil nu e un cuvânt că MP ceva, 441 00:23:29,290 --> 00:23:32,980 astfel încât în ​​poziția P în acest matrice, ar fi doar NULL. 442 00:23:32,980 --> 00:23:38,840 S-ar spune, OK, nu există nici un cuvânt care a urmat M de un P, OK? 443 00:23:38,840 --> 00:23:43,100 Deci, dacă ne gândim la asta, fiecare unul dintre aceste lucruri mai mici 444 00:23:43,100 --> 00:23:47,990 este de fapt una dintre acestea rețele mari de la A prin Z. 445 00:23:47,990 --> 00:23:55,064 Deci, ceea ce ar putea fi unul dintre lucrurile care este un fel de rambursare de un try? 446 00:23:55,064 --> 00:23:56,500 >> Audiența: O mulțime de memorie. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: Este o tona de memorie, nu? 448 00:23:59,940 --> 00:24:08,750 Fiecare dintre aceste blocuri aici reprezinta 26 de spații, 26 element de matrice. 449 00:24:08,750 --> 00:24:13,680 Deci, încearcă primi incredibil de spațiu grele. 450 00:24:13,680 --> 00:24:17,100 >> Dar ele sunt foarte rapide. 451 00:24:17,100 --> 00:24:22,540 Deci, incredibil de rapid, dar într-adevăr spațiu ineficiente. 452 00:24:22,540 --> 00:24:24,810 Un fel de trebuie sa dau din care una doriți. 453 00:24:24,810 --> 00:24:29,470 Acestea sunt foarte misto pentru PSET ta, dar o fac să ia o mulțime de memorie, 454 00:24:29,470 --> 00:24:30,290 astfel încât să compromis. 455 00:24:30,290 --> 00:24:31,480 Da? 456 00:24:31,480 --> 00:24:34,300 >> Audiența: Ar fi posibil să înființeze un try și apoi 457 00:24:34,300 --> 00:24:37,967 Odată ce aveți toate date în ea pe care le need-- 458 00:24:37,967 --> 00:24:39,550 Nu știu dacă asta ar avea sens. 459 00:24:39,550 --> 00:24:42,200 Am fost a scăpa de toate De caractere NULL, dar apoi 460 00:24:42,200 --> 00:24:42,910 tu nu ar fi în măsură să indice them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Încă nevoie de ele. 462 00:24:43,275 --> 00:24:44,854 >> Audiența: - la fel de fiecare dată. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Da. 464 00:24:45,520 --> 00:24:50,460 Ai nevoie de caractere NULL pentru a permite știi dacă nu e un cuvânt acolo. 465 00:24:50,460 --> 00:24:52,040 Ben ai avea ceva ce vrei? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 În regulă, deci vom pentru a merge un pic mai mult 468 00:24:54,581 --> 00:24:58,920 în detaliu tehnic din spatele o încerca și de a lucra printr-un exemplu. 469 00:24:58,920 --> 00:25:01,490 >> OK, deci acest lucru este același lucru. 470 00:25:01,490 --> 00:25:06,290 Întrucât într-o listă legată, principalul nostru un fel de-- ce e cuvântul vreau? - 471 00:25:06,290 --> 00:25:08,350 cum ar fi construirea bloc a fost un nod. 472 00:25:08,350 --> 00:25:12,280 Într-o încercare, avem, de asemenea, un nod, dar este definită în mod diferit. 473 00:25:12,280 --> 00:25:17,000 >> Deci avem ceva bool că reprezintă dacă un cuvânt de fapt 474 00:25:17,000 --> 00:25:23,530 există în această locație, și apoi avem unele matrice here-- sau, mai degrabă, 475 00:25:23,530 --> 00:25:27,840 acest lucru este un pointer la o matrice de 27 de caractere. 476 00:25:27,840 --> 00:25:33,339 Și acest lucru este de, în acest caz, acest 27-- Sunt sigur că toți sunt ca, așteptați, 477 00:25:33,339 --> 00:25:34,880 există 26 de litere din alfabet. 478 00:25:34,880 --> 00:25:36,010 De ce avem 27? 479 00:25:36,010 --> 00:25:37,870 >> Deci, în funcție de fel să pună în aplicare acest lucru, 480 00:25:37,870 --> 00:25:43,240 aceasta este de la un PSET care permis de apostrofuri. 481 00:25:43,240 --> 00:25:46,010 Deci, de aceea cel suplimentar. 482 00:25:46,010 --> 00:25:50,500 Veți avea, de asemenea, în unele cazuri terminator nul 483 00:25:50,500 --> 00:25:53,230 este inclusă ca unul dintre cele de caractere care este permis să fie, 484 00:25:53,230 --> 00:25:56,120 și că e modul în care acestea verifică la a se vedea dacă Finalul al cuvântului. 485 00:25:56,120 --> 00:26:01,340 Dacă sunteți interesat, a verifica afară Video de Kevin pe study.cs50, 486 00:26:01,340 --> 00:26:04,790 precum Wikipedia are unele resurse bune de acolo. 487 00:26:04,790 --> 00:26:09,000 >> Dar vom trece prin doar un fel de modul în care ar putea lucra printr-o încercare 488 00:26:09,000 --> 00:26:11,010 te dacă ești dat unul. 489 00:26:11,010 --> 00:26:16,230 Deci, avem un super-simplu aici are cuvintele "Liliacul" si "zoom" în ele. 490 00:26:16,230 --> 00:26:18,920 Și, după cum vom vedea aici, acest mic spațiu aici 491 00:26:18,920 --> 00:26:22,560 reprezintă bool noastră că spune, da, aceasta este un cuvânt. 492 00:26:22,560 --> 00:26:27,060 Iar apoi acest lucru are noastră rețele de caractere, nu? 493 00:26:27,060 --> 00:26:33,480 >> Așa că am de gând să treacă prin găsirea "bat" în această încercare. 494 00:26:33,480 --> 00:26:38,340 Deci, începe în partea de sus, dreapta? 495 00:26:38,340 --> 00:26:46,290 Și știm că b corespunde doilea indice, al doilea element 496 00:26:46,290 --> 00:26:47,840 în această matrice, pentru că a și b. 497 00:26:47,840 --> 00:26:51,340 Deci aproximativ doua. 498 00:26:51,340 --> 00:26:58,820 >> Și se spune, OK, rece, rezultă că în matrice următor, pentru că dacă ne amintim, 499 00:26:58,820 --> 00:27:02,160 nu e ca fiecare dintre acestea conține de fapt elementul. 500 00:27:02,160 --> 00:27:07,110 Fiecare dintre aceste matrice conține un pointer, nu? 501 00:27:07,110 --> 00:27:10,030 Este o distincție importantă de a face. 502 00:27:10,030 --> 00:27:13,450 >> Știu că acest lucru se întâmplă pentru be-- încercări sunt într-adevăr greu pentru a ajunge pe prima dată, 503 00:27:13,450 --> 00:27:15,241 astfel încât, chiar dacă acest lucru este a doua sau a treia oară 504 00:27:15,241 --> 00:27:18,370 și este încă natură de a părea dificil, 505 00:27:18,370 --> 00:27:21,199 Promit dacă te duci ceas scurt din nou mâine, 506 00:27:21,199 --> 00:27:22,740 se va face, probabil, mult mai mult sens. 507 00:27:22,740 --> 00:27:23,890 Este nevoie de o mulțime de digerat. 508 00:27:23,890 --> 00:27:27,800 Încă uneori sunt cum ar fi, așteptați, ceea ce este o încercare? 509 00:27:27,800 --> 00:27:29,080 Cum folosesc acest lucru? 510 00:27:29,080 --> 00:27:33,880 >> Așa că ne-am b, în ​​acest caz, care este al doilea indexul nostru. 511 00:27:33,880 --> 00:27:40,240 Dacă am avea, să zicem, C sau d sau orice altă scrisoare, 512 00:27:40,240 --> 00:27:45,810 trebuie să ne harta înapoi la index din oferta noastră, care valabil pentru. 513 00:27:45,810 --> 00:27:56,930 Așa că ne-ar lua ca rchar și ne-am scade de pe o so hartă în 0 și 25. 514 00:27:56,930 --> 00:27:58,728 Toată lumea bine cum ne Harta personajele noastre? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Deci, mergem la cea de a doua și noi a se vedea că, da, nu este la NULL. 517 00:28:05,980 --> 00:28:07,780 Ne putem trece la această matrice următor. 518 00:28:07,780 --> 00:28:12,300 Așa că mergem la această matrice următor aici. 519 00:28:12,300 --> 00:28:15,500 >> Și noi spunem, OK, acum am nevoie pentru a vedea dacă a este aici. 520 00:28:15,500 --> 00:28:18,590 Este nul sau nu-l de fapt, merge mai departe? 521 00:28:18,590 --> 00:28:21,880 Deci, un fapt se misca transmite în această matrice. 522 00:28:21,880 --> 00:28:24,570 Și noi spunem, OK, t este ultima noastră scrisoare. 523 00:28:24,570 --> 00:28:27,580 Deci, vom merge la t la pagina de index. 524 00:28:27,580 --> 00:28:30,120 Și apoi vom merge mai departe pentru că există un altul. 525 00:28:30,120 --> 00:28:38,340 Și aceasta se spune în esență că, da, se spune că există un cuvânt here-- 526 00:28:38,340 --> 00:28:41,750 că, dacă urmați această cale, ați ajuns 527 00:28:41,750 --> 00:28:43,210 la un cuvânt, pe care știm că este "bat". 528 00:28:43,210 --> 00:28:43,800 Da? 529 00:28:43,800 --> 00:28:46,770 >> Audiența: Este standard, pentru a avea acea ca index 0 și apoi au un fel de 1 530 00:28:46,770 --> 00:28:47,660 sau de a avea la sfârșitul anului? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: Nu. 532 00:28:48,243 --> 00:28:55,360 Deci, dacă ne uităm înapoi la noastre declarație aici, e un bool, 533 00:28:55,360 --> 00:28:59,490 asa ca este elementul său în nodul dumneavoastră. 534 00:28:59,490 --> 00:29:03,331 Deci, nu e parte a tabloului. 535 00:29:03,331 --> 00:29:03,830 Rece. 536 00:29:03,830 --> 00:29:08,370 Așa că atunci când ne-am duce la cuvânt și suntem în această matrice, ceea ce vrem să facem 537 00:29:08,370 --> 00:29:12,807 este sa faci o verificare este aceasta un cuvânt. 538 00:29:12,807 --> 00:29:14,390 Și în acest caz, s-ar întoarce da. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Deci, pe această notă, știm că "zoo" - stim ca oamenii care "zoo" este un cuvânt, 541 00:29:24,090 --> 00:29:24,820 dreapta? 542 00:29:24,820 --> 00:29:28,990 Dar se încerca aici să spun, nu, nu e. 543 00:29:28,990 --> 00:29:33,980 Și s-ar spune că pentru că noi nu l-au desemnat ca un cuvânt aici. 544 00:29:33,980 --> 00:29:40,440 Chiar dacă putem traversa până la această matrice, 545 00:29:40,440 --> 00:29:43,890 aceasta incercare ar spune că, nu, grădină zoologică nu este în dicționar ta 546 00:29:43,890 --> 00:29:47,070 pentru că noi nu avem desemnat-o ca atare. 547 00:29:47,070 --> 00:29:52,870 >> Deci, un mod de a face that-- oh, îmi pare rău, asta. 548 00:29:52,870 --> 00:29:59,450 Deci, în acest caz, "grădină zoologică" nu este un cuvânt, dar este în încercare noastră. 549 00:29:59,450 --> 00:30:05,690 Dar în aceasta, spune ne-o dorim introduce cuvântul "baie", ceea ce se întâmplă 550 00:30:05,690 --> 00:30:08,260 Este urmăm through-- b, o, t. 551 00:30:08,260 --> 00:30:11,820 Suntem în această matrice, și vom merge pentru a căuta h. 552 00:30:11,820 --> 00:30:15,220 >> In acest caz, atunci când ne uita-te la indicatorul de la ore, 553 00:30:15,220 --> 00:30:17,890 e arătând spre NULL, OK? 554 00:30:17,890 --> 00:30:20,780 Deci, dacă nu este în mod explicit arătând spre o altă matrice, 555 00:30:20,780 --> 00:30:25,000 voi presupune că toți indicii în această matrice sunt orientate la null. 556 00:30:25,000 --> 00:30:28,270 Deci, în acest caz, h este îndreptat la null astfel încât nu putem face nimic, 557 00:30:28,270 --> 00:30:31,540 asa ca ar reveni, de asemenea, fals, "baie" nu este aici. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Deci, acum suntem de fapt de gând să treacă prin 560 00:30:35,810 --> 00:30:39,790 cum ne-ar spune de fapt că "zoo" este în try noastră. 561 00:30:39,790 --> 00:30:42,920 Cum putem introduce "zoo", în try nostru? 562 00:30:42,920 --> 00:30:47,810 Deci, în același mod în care am început cu Lista noastră legată, vom începe de la rădăcină. 563 00:30:47,810 --> 00:30:50,600 Dacă aveți dubii, încep de la rădăcina acestor lucruri. 564 00:30:50,600 --> 00:30:53,330 >> Și vom spune, OK, z. 565 00:30:53,330 --> 00:30:55,650 z există în acest sens, și-l face. 566 00:30:55,650 --> 00:30:58,370 Deci a trece la următoarea matrice, OK? 567 00:30:58,370 --> 00:31:01,482 Și apoi pe cea următoare, spunem, OK, nu există o? 568 00:31:01,482 --> 00:31:03,000 Ea face. 569 00:31:03,000 --> 00:31:04,330 Acest lucru din nou. 570 00:31:04,330 --> 00:31:08,670 >> Și așa mai departe unul următoarea noastră, ne-am spus, OK, "grădină zoologică" există deja aici. 571 00:31:08,670 --> 00:31:12,440 Tot ce trebuie să faceți este să stabiliți acest egal de adevărat, că există un cuvânt acolo. 572 00:31:12,440 --> 00:31:15,260 Dacă ai fi urmat tot până la înainte de acel moment, 573 00:31:15,260 --> 00:31:17,030 este un cuvânt, așa că setați-o egală cu astfel de. 574 00:31:17,030 --> 00:31:17,530 Da? 575 00:31:17,530 --> 00:31:22,550 >> Audiența: Deci nu asta înseamnă că "ba" este un cuvânt de asemenea? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: Nu. 577 00:31:24,120 --> 00:31:28,870 Deci, în acest caz, "ba", ne-ar ajunge de aici, ne-ar spune că este un cuvânt, 578 00:31:28,870 --> 00:31:31,590 și ar fi tot nu. 579 00:31:31,590 --> 00:31:32,822 OK? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> Audiența: Deci, odată ce este un cuvânt și tu spui da, atunci aceasta 582 00:31:36,360 --> 00:31:38,380 va conține pentru a merge la m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: Deci asta are de a face aplice: sunteți de încărcare acest lucru în. 584 00:31:42,260 --> 00:31:43,640 Tu spui "zoo" este un cuvânt. 585 00:31:43,640 --> 00:31:47,020 Când te duci la check-- cum ar fi, spune ce vrei să spui, 586 00:31:47,020 --> 00:31:49,400 nu "zoo", există în acest dicționar? 587 00:31:49,400 --> 00:31:54,200 Esti doar de gând pentru a căuta "zoo", și apoi verificați pentru a vedea dacă e un cuvânt. 588 00:31:54,200 --> 00:31:57,291 Niciodată nu o să se mute până la m pentru că nu e 589 00:31:57,291 --> 00:31:58,290 ceea ce căutați. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Deci, dacă am vrut de fapt să add "baie" în această încercare, 592 00:32:08,070 --> 00:32:11,390 ne-ar face același lucru așa cum am făcut cu "zoo", 593 00:32:11,390 --> 00:32:15,380 cu excepția am vedea că, atunci când ne-am încerca și să obțină la h, aceasta nu există. 594 00:32:15,380 --> 00:32:20,090 Deci, vă puteți gândi la acest lucru ca încercarea pentru a adăuga un nou nod într-o listă legată, 595 00:32:20,090 --> 00:32:27,210 așa că va trebui să adăugați un alt unul dintre aceste tablouri, cum ar fi așa. 596 00:32:27,210 --> 00:32:35,670 Și atunci ce facem este doar ne-am stabilit h element al acestei matrice arătând spre aceasta. 597 00:32:35,670 --> 00:32:39,430 >> Și apoi ce am vrea să facem aici? 598 00:32:39,430 --> 00:32:43,110 Adaugă-l egal cu adevărat pentru că este un cuvânt. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Rece. 601 00:32:48,150 --> 00:32:48,700 Știu. 602 00:32:48,700 --> 00:32:51,170 Încercări nu sunt cele mai interesante. 603 00:32:51,170 --> 00:32:54,250 Crede-mă, știu. 604 00:32:54,250 --> 00:32:58,040 >> Deci, un singur lucru pentru a realiza cu nereușite, I-am spus, sunt foarte eficiente. 605 00:32:58,040 --> 00:33:00,080 Așa că le-am văzut ei să ia o tona de spațiu. 606 00:33:00,080 --> 00:33:01,370 Sunt un fel de confuzie. 607 00:33:01,370 --> 00:33:03,367 Deci, de ce ne-ar folosi vreodată astea? 608 00:33:03,367 --> 00:33:05,450 Noi folosim aceste, deoarece acestea sunt incredibil de eficient. 609 00:33:05,450 --> 00:33:08,130 >> Deci, dacă sunteți vreodată în căutarea un cuvânt, ești doar 610 00:33:08,130 --> 00:33:10,450 delimitată de lungimea cuvântului. 611 00:33:10,450 --> 00:33:15,210 Deci, dacă sunteți în căutarea pentru o cuvânt care este de lungime cinci, 612 00:33:15,210 --> 00:33:20,940 esti doar vreodată va trebui să face din cel mult cinci comparații, OK? 613 00:33:20,940 --> 00:33:25,780 Deci, ea face practic o constantă. 614 00:33:25,780 --> 00:33:29,150 La fel ca și inserție de căutare sunt, practic, timp constant. 615 00:33:29,150 --> 00:33:33,750 >> Deci, dacă puteți obține vreodată ceva în timp constant, 616 00:33:33,750 --> 00:33:35,150 asta e la fel de bun ca acesta devine. 617 00:33:35,150 --> 00:33:37,990 Nu se poate obține mai bine decât constanta de timp pentru aceste lucruri. 618 00:33:37,990 --> 00:33:43,150 Astfel că este unul dintre plusuri imense de încercări. 619 00:33:43,150 --> 00:33:46,780 >> Dar aceasta este o mulțime de spațiu. 620 00:33:46,780 --> 00:33:50,380 Deci ai un fel de trebuie să decidă ceea ce este mai important pentru tine. 621 00:33:50,380 --> 00:33:54,700 Și pe computerele de astăzi, spațiu care un try poate dura până 622 00:33:54,700 --> 00:33:57,740 poate că nu afectează tu asta de mult, dar poate 623 00:33:57,740 --> 00:34:01,350 ai de a face cu ceva care are mult, mult mai multe lucruri, 624 00:34:01,350 --> 00:34:02,810 și o încercare pur și simplu nu este rezonabil. 625 00:34:02,810 --> 00:34:03,000 Da? 626 00:34:03,000 --> 00:34:05,610 >> Audiența: Stai, astfel încât să aveți 26 litere în fiecare singur? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Da, ai 26. 629 00:34:08,570 --> 00:34:16,984 Ai ceva este să îi trimită cuvânt și apoi Ai 26 de indicii din fiecare. 630 00:34:16,984 --> 00:34:17,775 Și ei point-- 631 00:34:17,775 --> 00:34:20,280 >> Audiența: Și fiecare 26, nu fiecare dintre acestea are 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Da. 633 00:34:21,500 --> 00:34:27,460 Și de aceea, după cum puteți a se vedea, se extinde destul de rapid. 634 00:34:27,460 --> 00:34:28,130 Bine. 635 00:34:28,130 --> 00:34:32,524 Deci, vom intra în copaci, care Mă simt ca este mai ușor și, probabil, va 636 00:34:32,524 --> 00:34:36,150 fie un răgaz drăguț de încercări acolo. 637 00:34:36,150 --> 00:34:39,620 Deci, sperăm, cele mai multe dintre voi au văzut un copac înainte. 638 00:34:39,620 --> 00:34:41,820 Nu ca destul de cei din afara, pe care am 639 00:34:41,820 --> 00:34:44,340 Nu știu dacă cineva a mers în aer liber recent. 640 00:34:44,340 --> 00:34:49,230 M-am dus de mere cules acest week-end, și oh, Doamne, că a fost frumos. 641 00:34:49,230 --> 00:34:52,250 Nu știam frunze ar putea arăta că destul de. 642 00:34:52,250 --> 00:34:53,610 >> Deci, aceasta este doar un copac, nu? 643 00:34:53,610 --> 00:34:56,790 E doar un nod, și-l indică o grămadă de alte noduri. 644 00:34:56,790 --> 00:34:59,570 După cum vedeți aici, aceasta este un fel de temă recurentă. 645 00:34:59,570 --> 00:35:03,720 Nodurile ce indică spre noduri este un fel de esența multe structuri de date. 646 00:35:03,720 --> 00:35:06,670 Este doar depinde de modul în care le-au punctul de reciproc 647 00:35:06,670 --> 00:35:08,600 și cum o traversa prin ele și cum o 648 00:35:08,600 --> 00:35:14,500 introduce lucruri care determină diferite de caracteristicile lor. 649 00:35:14,500 --> 00:35:17,600 >> Deci, doar câteva terminologie, pe care l-am folosit înainte. 650 00:35:17,600 --> 00:35:20,010 Deci, radacina este tot ce este la foarte sus. 651 00:35:20,010 --> 00:35:21,200 este în cazul în care vom începe mereu. 652 00:35:21,200 --> 00:35:23,610 Vă puteți gândi la ea ca și cap de asemenea. 653 00:35:23,610 --> 00:35:28,750 Dar pentru copaci, avem tendința de a se referă la ea ca rădăcină. 654 00:35:28,750 --> 00:35:32,820 >> Nimic here-- de jos la foarte, foarte bottom-- 655 00:35:32,820 --> 00:35:34,500 sunt considerate frunze. 656 00:35:34,500 --> 00:35:37,210 Deci, merge împreună cu Toată chestia copac, nu? 657 00:35:37,210 --> 00:35:39,860 Frunzele sunt la marginile copac. 658 00:35:39,860 --> 00:35:45,820 >> Și apoi avem, de asemenea, o pereche de termeni pentru a vorbi despre noduri în legătură 659 00:35:45,820 --> 00:35:46,680 între ele. 660 00:35:46,680 --> 00:35:49,700 Deci avem mamă, copii și frați. 661 00:35:49,700 --> 00:35:56,260 Deci, în acest caz, 3 este mamă de 5, 6, și 7. 662 00:35:56,260 --> 00:36:00,370 Deci, părintele este tot ce este un pas mai sus, indiferent de ce te 663 00:36:00,370 --> 00:36:02,940 referindu-se la, asa ca ca un arbore genealogic. 664 00:36:02,940 --> 00:36:07,090 Sperăm că acest lucru este tot un pic pic mai intuitiv decat încearcă. 665 00:36:07,090 --> 00:36:10,970 >> Fratii sunt orice, care au În același părinte, nu? 666 00:36:10,970 --> 00:36:13,470 Sunt la același nivel aici. 667 00:36:13,470 --> 00:36:16,960 Și apoi, așa cum am fost spune, copiii sunt doar 668 00:36:16,960 --> 00:36:22,630 ceea ce este un pas mai jos nodul în cauză, OK? 669 00:36:22,630 --> 00:36:23,470 Rece. 670 00:36:23,470 --> 00:36:25,610 Deci, un arbore binar. 671 00:36:25,610 --> 00:36:31,450 Poate hazarda cineva o presupunere pe unul dintre caracteristicile arborele binar? 672 00:36:31,450 --> 00:36:32,770 >> Audiența: Max două frunze. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Corect. 674 00:36:33,478 --> 00:36:34,640 Deci maxim de două frunze. 675 00:36:34,640 --> 00:36:39,730 Deci, în acest o înainte, am avut aceasta care a avut trei, dar într-un arbore binar, 676 00:36:39,730 --> 00:36:45,000 Ai un maxim de două copii per părinte, nu? 677 00:36:45,000 --> 00:36:46,970 Nu e un alt caracteristică interesantă. 678 00:36:46,970 --> 00:36:51,550 Stie cineva asta? 679 00:36:51,550 --> 00:36:52,620 Arbore binar. 680 00:36:52,620 --> 00:37:00,350 >> Deci, un arbore binar va avea tot pe the-- acesta nu este sorted-- 681 00:37:00,350 --> 00:37:05,320 dar într-un arbore binar sortate, tot pe dreapta 682 00:37:05,320 --> 00:37:08,530 este mai mare decât părintele, și tot pe stânga 683 00:37:08,530 --> 00:37:10,035 este mai mică decât mamă. 684 00:37:10,035 --> 00:37:15,690 Și că a fost un test întrebare înainte, atât de bine să știu. 685 00:37:15,690 --> 00:37:19,500 Deci, modul în care ne definim acest lucru, din nou, avem un alt nod. 686 00:37:19,500 --> 00:37:21,880 Acest lucru arata foarte similar cu ce? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 De două ori 689 00:37:28,836 --> 00:37:29,320 >> Audiența: Linked liste 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: O listă dublă legătură, nu? 691 00:37:31,100 --> 00:37:33,690 Deci, dacă am înlocui această cu precedent și următor, 692 00:37:33,690 --> 00:37:35,670 acest lucru ar fi o listă de două ori legat. 693 00:37:35,670 --> 00:37:40,125 Dar, în acest caz, suntem de fapt au la stânga și la dreapta și asta e tot. 694 00:37:40,125 --> 00:37:41,500 În caz contrar, e exact la fel. 695 00:37:41,500 --> 00:37:43,374 Încă mai avem elementul ce căutați, 696 00:37:43,374 --> 00:37:45,988 și trebuie doar doi pointeri merge la orice urmează. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Da, arbore de căutare, astfel binar. 699 00:37:51,870 --> 00:37:57,665 Dacă observăm, totul pe aici este mai mare than-- 700 00:37:57,665 --> 00:37:59,850 sau totul imediat spre dreapta aici 701 00:37:59,850 --> 00:38:02,840 este mai mare de, tot aici este mai mică. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Deci, dacă ar fi să caute prin ea, ar trebui să arate foarte aproape de căutare binare 704 00:38:14,000 --> 00:38:14,910 aici, nu? 705 00:38:14,910 --> 00:38:17,640 Cu excepția loc de a privi la jumătate matrice, 706 00:38:17,640 --> 00:38:21,720 suntem doar cauți fie la stânga lateral sau în partea dreaptă a copacului. 707 00:38:21,720 --> 00:38:24,850 Deci, ea devine un pic mai simplu, cred. 708 00:38:24,850 --> 00:38:29,300 >> Deci, în cazul în care rădăcină este NULL, în mod evident, este doar fals. 709 00:38:29,300 --> 00:38:33,470 Și dacă e acolo, evident că e adevărat. 710 00:38:33,470 --> 00:38:35,320 Dacă este mai mică, căutăm stânga. 711 00:38:35,320 --> 00:38:37,070 Dacă este mai mare decât, căutăm dreapta. 712 00:38:37,070 --> 00:38:39,890 E exact ca și căutare binară, doar o structură de date diferită 713 00:38:39,890 --> 00:38:40,600 pe care îl utilizăm. 714 00:38:40,600 --> 00:38:42,790 În loc de o matrice, e doar un arbore binar. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, stive. 717 00:38:48,090 --> 00:38:51,550 Și, de asemenea, se pare că ar putea avea un pic de timp. 718 00:38:51,550 --> 00:38:54,460 Dacă da, eu sunt fericit să merg peste toate astea din nou. 719 00:38:54,460 --> 00:38:56,856 OK, așa stive. 720 00:38:56,856 --> 00:39:02,695 Are cineva aminte ce stacks-- orice caracteristici ale unui stivă? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, deci cele mai multe dintre noi, cred, mânca în mese halls-- 723 00:39:10,400 --> 00:39:13,100 la fel de mult ca noi nu le place să. 724 00:39:13,100 --> 00:39:16,900 Dar, evident, vă puteți gândi la o stivă literalmente la fel cum o stivă de tăvi 725 00:39:16,900 --> 00:39:18,460 sau un teanc de lucruri. 726 00:39:18,460 --> 00:39:21,820 Și ceea ce este important să realizeze este că e 727 00:39:21,820 --> 00:39:26,850 something-- caracteristica pe care o numim aceasta by-- este LIFO. 728 00:39:26,850 --> 00:39:28,450 Stie cineva ce înseamnă asta? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> Audiența: trecută intrat, primul ieșit. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: pe dreapta, ultimul intrat, primul ieșit. 732 00:39:32,250 --> 00:39:36,585 Deci, dacă știm, dacă suntem stivuire lucruri sus, cel mai ușor lucru pentru a apuca off-- 733 00:39:36,585 --> 00:39:39,570 și, poate, singurul lucru pe care îl putem apuca de off dacă stack noastră este enough-- mare 734 00:39:39,570 --> 00:39:40,850 este acel element top. 735 00:39:40,850 --> 00:39:43,460 Deci, tot ce a fost pus pe last-- așa cum vedem aici, 736 00:39:43,460 --> 00:39:46,370 tot ce a fost împins pe cel mai recently-- este 737 00:39:46,370 --> 00:39:51,160 Va fi primul lucru pe care noi pop off, OK? 738 00:39:51,160 --> 00:39:56,324 >> Deci, ceea ce avem aici este un alt struct typedef. 739 00:39:56,324 --> 00:39:58,740 Acest lucru este într-adevăr doar ca o Crash Course în structura de date, 740 00:39:58,740 --> 00:40:01,650 deci există o mulțime aruncat la voi. 741 00:40:01,650 --> 00:40:02,540 Știu. 742 00:40:02,540 --> 00:40:04,970 Deci, încă o struct. 743 00:40:04,970 --> 00:40:06,740 Yay pentru structuri. 744 00:40:06,740 --> 00:40:16,660 >> Și în acest caz, e un pointer la o serie care are o anumită capacitate. 745 00:40:16,660 --> 00:40:20,830 Deci, acest lucru reprezintă stivă nostru aici, ca și oferta noastră reală 746 00:40:20,830 --> 00:40:22,520 care a deține elemente noastre. 747 00:40:22,520 --> 00:40:24,850 Și apoi aici avem o dimensiune. 748 00:40:24,850 --> 00:40:31,170 >> Și de obicei, doriți să le păstrați urmări cât de mare stack-ul tău este 749 00:40:31,170 --> 00:40:36,180 pentru că ceea ce se întâmplă, pentru a permite să faci este dacă știți dimensiunea, 750 00:40:36,180 --> 00:40:39,170 vă permite să spun, OK, sunt eu la capacitate? 751 00:40:39,170 --> 00:40:40,570 Pot să adaug ceva mai mult? 752 00:40:40,570 --> 00:40:44,650 Și este, de asemenea, vă spune în cazul în care partea de sus a stack-ul tău 753 00:40:44,650 --> 00:40:48,180 este ca să știi ce ai poate lua de fapt oprit. 754 00:40:48,180 --> 00:40:51,760 Și că de fapt de gând să fi un pic mai clar aici. 755 00:40:51,760 --> 00:40:57,350 >> Deci, pentru împinge, un singur lucru, dacă au fost vreodată la punerea în aplicare a împinge, 756 00:40:57,350 --> 00:41:01,330 așa cum spuneam, dumneavoastră stack are o dimensiune limitată, nu? 757 00:41:01,330 --> 00:41:03,990 Oferta noastră a avut o anumită capacitate. 758 00:41:03,990 --> 00:41:04,910 E un tablou. 759 00:41:04,910 --> 00:41:08,930 Este o dimensiune fixă, așa că trebuie să asigurați-vă că nu suntem inscrie mai mult 760 00:41:08,930 --> 00:41:11,950 în oferta noastră decât noi de fapt, au spațiu pentru. 761 00:41:11,950 --> 00:41:16,900 >> Deci, atunci când creați o apăsare funcția, primul lucru pe care îl faci este să zicem, OK, 762 00:41:16,900 --> 00:41:18,570 nu am spatiu in stiva mea? 763 00:41:18,570 --> 00:41:23,330 Pentru că dacă nu o fac, îmi pare rău, Nu pot stoca elementul tau. 764 00:41:23,330 --> 00:41:28,980 Dacă o fac, atunci doriți să memorați se la partea de sus a stivei, nu? 765 00:41:28,980 --> 00:41:31,325 >> Și acesta este motivul pentru care avem pentru a urmări dimensiunea noastră. 766 00:41:31,325 --> 00:41:35,290 Dacă nu vom ține cont de dimensiunea noastră, nu știm unde să-l puneți. 767 00:41:35,290 --> 00:41:39,035 Nu știm cât de multe lucruri sunt în oferta noastră deja. 768 00:41:39,035 --> 00:41:41,410 Ca și în mod evident, există modalități că poate ai putea-o face. 769 00:41:41,410 --> 00:41:44,610 Ai putea inițializa totul pentru a NULL și apoi verificați pentru cele mai recente NULL, 770 00:41:44,610 --> 00:41:47,950 dar un lucru mult mai ușor pe lângă să spun, OK, ține evidența dimensiune. 771 00:41:47,950 --> 00:41:51,840 Ca și cum Știu că am patru elemente în matrice mea, astfel încât următorul lucru 772 00:41:51,840 --> 00:41:55,930 că ne-am pus pe, suntem va stoca cel index 4. 773 00:41:55,930 --> 00:42:00,940 Și apoi, desigur, acest lucru înseamnă că ați împins cu succes ceva 774 00:42:00,940 --> 00:42:03,320 pe stack-ul tău, vă doresc să crească dimensiunea 775 00:42:03,320 --> 00:42:08,880 astfel încât să știi unde ești atât de pe care le poate împinge mai multe lucruri pe. 776 00:42:08,880 --> 00:42:12,730 >> Deci, dacă noi încercăm să pop ceva de pe stivă, 777 00:42:12,730 --> 00:42:16,072 ceea ce ar putea fi primul lucru pe care ne-o dorim pentru a verifica? 778 00:42:16,072 --> 00:42:18,030 Pe care încercați să luați ceva de pe stack-ul tău. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Ești sigur că există ceva din stack-ul tău? 781 00:42:24,781 --> 00:42:25,280 Nu. 782 00:42:25,280 --> 00:42:26,894 Deci, ceea ce am putea să doriți să verificați? 783 00:42:26,894 --> 00:42:27,810 >> Audiența: [inaudibil]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Verificați pentru dimensiunea? 785 00:42:29,880 --> 00:42:31,840 Mărime. 786 00:42:31,840 --> 00:42:38,520 Așa că vrem să verificați pentru a vedea dacă dimensiunea noastră este mai mare de 0, OK? 787 00:42:38,520 --> 00:42:44,970 Și dacă este, atunci vrem să scadă harta noastră de 0 și să se întoarcă asta. 788 00:42:44,970 --> 00:42:45,840 De ce? 789 00:42:45,840 --> 00:42:49,950 >> În primul eram împingerea, l-am împins 790 00:42:49,950 --> 00:42:52,460 într-o formă mărime și dimensiune, apoi actualizate. 791 00:42:52,460 --> 00:42:57,850 În acest caz, vom decrementare dimensiune și apoi luați-l, jumulire aceasta 792 00:42:57,850 --> 00:42:58,952 din oferta noastră. 793 00:42:58,952 --> 00:42:59,826 De ce am putea face asta? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Deci, dacă am un singur lucru pe stivă mea, ceea ce ar fi mărimea mea la acel moment? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> Și în cazul în care este elementul 1 depozitat? 798 00:43:15,180 --> 00:43:17,621 La ce indicele? 799 00:43:17,621 --> 00:43:18,120 Audiența: 0. 800 00:43:18,120 --> 00:43:19,060 SPEAKER 1: 0. 801 00:43:19,060 --> 00:43:22,800 Deci, în acest caz, ne vom întotdeauna trebuie să vă sure-- 802 00:43:22,800 --> 00:43:27,630 în loc de a se întoarce mărime minus 1, pentru că noi 803 00:43:27,630 --> 00:43:31,730 știu că elementul nostru este O să fie păstrat la 1 mai 804 00:43:31,730 --> 00:43:34,705 indiferent de dimensiunea noastră este, acest doar are grijă de ea. 805 00:43:34,705 --> 00:43:36,080 Este un mod ceva mai elegant. 806 00:43:36,080 --> 00:43:41,220 Și ne-am decrementa doar nostru dimensiune și apoi să se întoarcă dimensiune. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> Audiența: Cred că doar în general, de ce ar fi această structură de date 809 00:43:45,300 --> 00:43:47,800 fi benefică? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: Depinde de context ta. 811 00:43:50,660 --> 00:43:57,420 Deci, pentru o parte din teorie, dacă lucrați aplice: OK, 812 00:43:57,420 --> 00:44:02,750 lasă-mă să văd dacă există un singur benefic care este benefic pentru mai mult de afara 813 00:44:02,750 --> 00:44:05,420 de CS. 814 00:44:05,420 --> 00:44:15,780 Cu stive, în orice moment aveți nevoie pentru a urmări ceva care 815 00:44:15,780 --> 00:44:20,456 este cel mai recent adăugată este atunci când ai de gând să doriți să utilizați o stivă. 816 00:44:20,456 --> 00:44:24,770 >> Și nu pot să cred că de o bună exemplu de asta chiar acum. 817 00:44:24,770 --> 00:44:29,955 Dar ori de câte ori cele mai recente lucru este cel mai important pentru tine, 818 00:44:29,955 --> 00:44:31,705 că, atunci când o stivă va fi util. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Încerc să mă gândesc dacă nu e unul bun pentru aceasta. 821 00:44:39,330 --> 00:44:43,720 Dacă mă gândesc la un exemplu bun în următorii 20 de minute, vă voi spune cu siguranta. 822 00:44:43,720 --> 00:44:49,455 >> Dar, in general, dacă e ceva, cum am spus cel mai mult, în cazul în care cele mai recente 823 00:44:49,455 --> 00:44:52,470 este cel mai important, care este în cazul în care un teanc intră în joc. 824 00:44:52,470 --> 00:44:58,860 Întrucât cozile sunt un fel de opusul. 825 00:44:58,860 --> 00:44:59,870 Și toate micile câinii. 826 00:44:59,870 --> 00:45:00,890 Nu e mare, nu? 827 00:45:00,890 --> 00:45:03,299 Mă simt ca și cum am ar trebui doar un videoclip iepuras 828 00:45:03,299 --> 00:45:05,090 chiar în mijlocul de secțiune pentru voi 829 00:45:05,090 --> 00:45:08,870 pentru că aceasta este o secțiune intens. 830 00:45:08,870 --> 00:45:10,480 >> Deci, o listă de așteptare. 831 00:45:10,480 --> 00:45:12,710 Practic o coadă este ca o linie. 832 00:45:12,710 --> 00:45:15,780 Voi Sunt sigur că această utilizare de zi cu zi, la fel ca în sălile de mese. 833 00:45:15,780 --> 00:45:18,160 Deci, noi trebuie să mergem în și de a lua tăvi noastre, sunt 834 00:45:18,160 --> 00:45:21,260 -vă că trebuie să aștepte în linie pentru înregistrare sau pentru a obține mancarea. 835 00:45:21,260 --> 00:45:24,650 >> Deci, diferența aici este că aceasta este FIFO. 836 00:45:24,650 --> 00:45:30,090 Deci, dacă LIFO a fost ultimul intrat, primul Out, FIFO este primul intrat, primul ieșit. 837 00:45:30,090 --> 00:45:33,400 Deci, acest lucru este în cazul în care orice ai pune pe primul este cel mai important. 838 00:45:33,400 --> 00:45:35,540 Deci, dacă ați fost de așteptare într-un line-- puteți 839 00:45:35,540 --> 00:45:39,130 imaginați-vă, dacă te-ai dus la du-te noul iPhone 840 00:45:39,130 --> 00:45:42,800 și a fost o stivă în cazul în care Ultima persoană în conformitate luat-o în primul rând, 841 00:45:42,800 --> 00:45:44,160 oameni ar ucide unii pe alții. 842 00:45:44,160 --> 00:45:49,800 >> Așa că FIFO, suntem cu toții foarte familiar cu în lumea reală aici, 843 00:45:49,800 --> 00:45:54,930 și totul are de a face cu efectiv un fel de a recrea tot această linie 844 00:45:54,930 --> 00:45:56,900 și structura de așteptare. 845 00:45:56,900 --> 00:46:02,390 Deci, în timp ce cu stiva, ne-am împinge și pop. 846 00:46:02,390 --> 00:46:06,440 Cu o coada, avem Puneți în coadă și dequeue. 847 00:46:06,440 --> 00:46:10,910 Deci, Puneți în coadă înseamnă în esență pune-l pe spate, 848 00:46:10,910 --> 00:46:13,680 și mijloace dequeue ia off de la partea din față. 849 00:46:13,680 --> 00:46:18,680 Deci, structura noastră de date este o pic mai complicat. 850 00:46:18,680 --> 00:46:21,060 Avem un al doilea lucru pentru a ține evidența. 851 00:46:21,060 --> 00:46:25,950 >> Deci, fără cap, aceasta este exact un stack, nu? 852 00:46:25,950 --> 00:46:27,900 Aceasta este aceeași structură ca și o stivă. 853 00:46:27,900 --> 00:46:32,480 Singurul lucru diferit acum e că au acest cap, care ce crezi 854 00:46:32,480 --> 00:46:34,272 se va urmări? 855 00:46:34,272 --> 00:46:35,510 >> Audiența: Prima. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: dreapta, primul lucru pe care am pus în. 857 00:46:38,685 --> 00:46:41,130 Șeful coadă noastre. 858 00:46:41,130 --> 00:46:42,240 Cine e pe primul loc în linie. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Bine, deci dacă facem Puneți în coadă. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Din nou, cu oricare dintre aceste structuri de date, 863 00:46:55,920 --> 00:46:59,760 deoarece avem de a face cu o serie, avem nevoie pentru a verifica dacă avem spațiu. 864 00:46:59,760 --> 00:47:03,290 >> Aceasta este un fel de-mi spui voi, dacă deschideți un fișier, 865 00:47:03,290 --> 00:47:04,760 aveți nevoie pentru a verifica nul. 866 00:47:04,760 --> 00:47:08,330 Cu oricare dintre aceste stive și cozile, aveți nevoie 867 00:47:08,330 --> 00:47:13,420 pentru a vedea dacă există spațiu pentru că suntem de-a face cu o matrice dimensiune fixă, 868 00:47:13,420 --> 00:47:16,030 așa cum vom vedea here-- 0, 1 tot de până la 5. 869 00:47:16,030 --> 00:47:20,690 Deci, ceea ce facem în acest caz este de verificare pentru a vedea dacă mai avem spațiu. 870 00:47:20,690 --> 00:47:23,110 Este dimensiunea noastră mai mică capacitate? 871 00:47:23,110 --> 00:47:28,480 >> Dacă este așa, trebuie să-l păstra la coada și ne-am fi actualizat dimensiunea noastră. 872 00:47:28,480 --> 00:47:30,250 Deci, ceea ce ar putea fi coada în acest caz? 873 00:47:30,250 --> 00:47:32,360 Nu e scris în mod explicit. 874 00:47:32,360 --> 00:47:33,380 Cum am păstra? 875 00:47:33,380 --> 00:47:34,928 Care ar fi coada? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Așa că haideți să se plimbe prin acest exemplu. 878 00:47:40,190 --> 00:47:44,590 Deci, aceasta este o matrice de dimensiune 6, nu? 879 00:47:44,590 --> 00:47:49,220 Și avem acum, dimensiunea noastră este de 5. 880 00:47:49,220 --> 00:47:55,240 Și când ne-am pus-o în, va pentru a intra în a cincea index, dreapta? 881 00:47:55,240 --> 00:47:57,030 Deci, păstra la coadă. 882 00:47:57,030 --> 00:48:05,600 >> Un alt mod de a scrie coadă ar fi doar fi oferta noastră la index de mărime, nu? 883 00:48:05,600 --> 00:48:07,560 Aceasta este dimensiunea de 5. 884 00:48:07,560 --> 00:48:11,490 Următorul lucru este de gând să meargă în 5. 885 00:48:11,490 --> 00:48:12,296 Rece? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Ea devine puțin mai complicat când vom începe încurcați cu capul. 888 00:48:16,350 --> 00:48:17,060 Da? 889 00:48:17,060 --> 00:48:20,090 >> Audiența: Asta înseamnă că noi ar fi declarat o matrice care 890 00:48:20,090 --> 00:48:23,880 a fost de cinci elemente de lung și apoi vom adăuga pe ea? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: Nu. 892 00:48:24,730 --> 00:48:27,560 Deci, în acest caz, aceasta este o stivă. 893 00:48:27,560 --> 00:48:31,760 Acest lucru ar fi declarat ca o serie de dimensiune 6. 894 00:48:31,760 --> 00:48:37,120 Și în acest caz, ne vom au doar un singur stângă spațiu. 895 00:48:37,120 --> 00:48:42,720 >> OK, deci un lucru este în acest caz, în cazul în care capul nostru este de la 0, 896 00:48:42,720 --> 00:48:45,270 atunci ne-am putea adauga la dimensiune. 897 00:48:45,270 --> 00:48:51,020 Dar devine un pic mai complicat pentru că, de fapt, ei 898 00:48:51,020 --> 00:48:52,840 nu au un diapozitiv pentru aceasta, așa că am de gând 899 00:48:52,840 --> 00:48:56,670 să elaboreze o, pentru că nu e destul de simplu, odată ce 900 00:48:56,670 --> 00:48:59,230 începe a scăpa de lucruri. 901 00:48:59,230 --> 00:49:03,920 Deci, în timp ce cu o stivă doar tu vreodată 902 00:49:03,920 --> 00:49:08,920 să vă faceți griji despre ceea ce dimensiunea este atunci când adăugați ceva mai departe, 903 00:49:08,920 --> 00:49:15,710 cu o coada, de asemenea, aveți nevoie pentru a face vă că capul este reprezentat, 904 00:49:15,710 --> 00:49:20,760 pentru că un lucru misto despre cozile este că, dacă nu ești la capacitate, 905 00:49:20,760 --> 00:49:23,040 puteți face de fapt se înfășoare în jurul. 906 00:49:23,040 --> 00:49:28,810 >> OK, deci o thing-- oh, acest lucru este creta teribil. 907 00:49:28,810 --> 00:49:31,815 Un lucru să ia în considerare este cazul. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Vom face doar cinci. 910 00:49:37,140 --> 00:49:41,810 OK, deci vom spune capul este aici. 911 00:49:41,810 --> 00:49:46,140 Aceasta este 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> Capul e acolo, și vă rugăm să aveți lucruri în ele. 913 00:49:54,210 --> 00:49:58,340 Și dorim să adăugăm ceva în, nu? 914 00:49:58,340 --> 00:50:01,170 Deci, lucru de care avem nevoie pentru a știu este că șeful este întotdeauna 915 00:50:01,170 --> 00:50:05,620 de gând să se mute în acest fel și apoi buclă înapoi în jurul, OK? 916 00:50:05,620 --> 00:50:10,190 >> Deci, această coadă are spațiu, nu? 917 00:50:10,190 --> 00:50:13,950 Ea are spațiu în încă de la început, un fel de opusul acest lucru. 918 00:50:13,950 --> 00:50:17,920 Deci, ceea ce trebuie să faceți este să ne nevoie pentru a calcula coada. 919 00:50:17,920 --> 00:50:20,530 Dacă știți că dumneavoastră cap nu sa mutat, coada 920 00:50:20,530 --> 00:50:24,630 este doar matrice la indicele de mărime. 921 00:50:24,630 --> 00:50:30,000 >> Dar, în realitate, dacă utilizați o coadă, capul este, probabil, în curs de actualizare. 922 00:50:30,000 --> 00:50:33,890 Deci, ceea ce trebuie să faceți este să calcula de fapt coada. 923 00:50:33,890 --> 00:50:39,990 Deci, ceea ce facem noi este această formulă aici, pe care am de gând să te lăsa 924 00:50:39,990 --> 00:50:42,680 baieti ne gândim, și atunci vom vorbi despre asta. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Deci, aceasta este capacitatea. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Deci, aceasta va fi de fapt vă oferă o modalitate de a face acest lucru. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Pentru că în acest caz, ce? 931 00:51:04,330 --> 00:51:09,205 Capul nostru este de la 1, Dimensiune noastră este 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Dacă ne Mod că de 5, ajungem 0, care este în cazul în care ar trebui să ne input-l. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Deci, atunci, în cazul următor, dacă ar fi să facem acest lucru, 936 00:51:26,080 --> 00:51:33,390 spunem, OK, hai să dequeue ceva. 937 00:51:33,390 --> 00:51:34,390 Am dequeue aceasta. 938 00:51:34,390 --> 00:51:37,740 Ne scoate acest element, nu? 939 00:51:37,740 --> 00:51:47,930 >> Și acum capul nostru este îndreptat aici, și dorim să adăugăm un alt lucru. 940 00:51:47,930 --> 00:51:52,470 Aceasta este de fapt din spate a liniei noastre, nu? 941 00:51:52,470 --> 00:51:55,450 Cozile se poate încadra în jurul valorii de matrice. 942 00:51:55,450 --> 00:51:57,310 Asta e una dintre principalele diferențe. 943 00:51:57,310 --> 00:51:58,780 Stive, nu poți face acest lucru. 944 00:51:58,780 --> 00:52:01,140 >> Cu cozile, puteți pentru că tot ce contează 945 00:52:01,140 --> 00:52:03,940 este ca stii ce S-a adăugat cel mai recent. 946 00:52:03,940 --> 00:52:10,650 Din moment ce totul va fi adăugat la această direcție spre stânga, în acest caz, 947 00:52:10,650 --> 00:52:16,480 și apoi înfășurați în jurul, puteți continua punerea în elemente noi 948 00:52:16,480 --> 00:52:18,830 în partea din față a șirului pentru că nu e adevărat 949 00:52:18,830 --> 00:52:20,640 partea frontală a tabloului mai. 950 00:52:20,640 --> 00:52:26,320 Vă puteți gândi de la începutul matrice ca în cazul în care capul este de fapt. 951 00:52:26,320 --> 00:52:29,710 >> Deci, această formulă este modul în care ai calcula coada ta. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Are care face sens? 954 00:52:35,610 --> 00:52:36,110 OK. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK, dequeue, iar apoi voi avea 10 minute 957 00:52:44,040 --> 00:52:48,840 să-mi pună întrebări clarificarea ce vrei, pentru că știu că e nebun. 958 00:52:48,840 --> 00:52:51,980 >> În regulă, deci în aceeași way-- Nu știu dacă voi observa, 959 00:52:51,980 --> 00:52:53,450 dar CS este despre toate modelele. 960 00:52:53,450 --> 00:52:57,370 Lucrurile sunt destul de mult același, doar cu trucuri mici. 961 00:52:57,370 --> 00:52:58,950 Deci, același lucru aici. 962 00:52:58,950 --> 00:53:04,040 Avem nevoie pentru a verifica pentru a vedea dacă suntem de fapt au ceva în coadă noastră, nu? 963 00:53:04,040 --> 00:53:05,960 Spune, OK, este dimensiunea noastră mai mare decât 0? 964 00:53:05,960 --> 00:53:06,730 Rece. 965 00:53:06,730 --> 00:53:10,690 >> Dacă da, atunci ne-am muta capul nostru, care este ceea ce am demonstrat aici. 966 00:53:10,690 --> 00:53:13,870 Noi actualizăm capul nostru să fie una mai mult. 967 00:53:13,870 --> 00:53:18,390 Și apoi ne-am decrementa nostru mărime și să se întoarcă elementul. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Nu este mult mai concret cod pe study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 și am foarte recomanda merg prin ea, dacă aveți timp, 971 00:53:29,440 --> 00:53:30,980 chiar dacă e doar un cod pseudo. 972 00:53:30,980 --> 00:53:35,980 Și dacă vreți să vorbim prin intermediul că cu mine unu la unu, vă rog să mă lăsați 973 00:53:35,980 --> 00:53:37,500 știu. 974 00:53:37,500 --> 00:53:38,770 Aș fi fericit să. 975 00:53:38,770 --> 00:53:42,720 Structuri de date, în cazul în care luați CS 124, veți 976 00:53:42,720 --> 00:53:47,830 stiu ca structuri de date devin foarte distracție și acest lucru este doar începutul. 977 00:53:47,830 --> 00:53:50,350 >> Așa că știu că e greu. 978 00:53:50,350 --> 00:53:51,300 E în regulă. 979 00:53:51,300 --> 00:53:52,410 Noi luptăm. 980 00:53:52,410 --> 00:53:53,630 Eu încă o fac. 981 00:53:53,630 --> 00:53:56,660 Deci, nu vă faceți griji prea mult despre asta. 982 00:53:56,660 --> 00:54:02,390 >> Dar asta este, în principiu ta Crash Course in structuri de date. 983 00:54:02,390 --> 00:54:03,400 Știu că e foarte mult. 984 00:54:03,400 --> 00:54:06,860 Este ceva pe care noi ar dori să meargă din nou? 985 00:54:06,860 --> 00:54:09,400 Orice vrem să vorbim prin intermediul? 986 00:54:09,400 --> 00:54:10,060 Da? 987 00:54:10,060 --> 00:54:16,525 >> Audiența: În acest exemplu, așa Coada este nou la 0 peste asta? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Da. 989 00:54:17,150 --> 00:54:18,230 Audiența: OK. 990 00:54:18,230 --> 00:54:24,220 Deci, apoi trece prin, ai avea un plus de 4 or-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Deci tu spuneai, atunci când vrem să mergem fac asta din nou? 992 00:54:27,671 --> 00:54:28,296 Audiența: Da. 993 00:54:28,296 --> 00:54:38,290 Deci, dacă ați fost imaginind out-- în cazul în care sunt tu calcularea coada de la asta? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Deci coada a fost in-- am schimbat acest lucru. 995 00:54:44,260 --> 00:54:52,010 Deci, în acest exemplu de aici, aceasta a fost matrice ne uitam la, OK? 996 00:54:52,010 --> 00:54:54,670 Deci avem lucruri în 1, 2, 3, 4 și. 997 00:54:54,670 --> 00:55:05,850 Deci avem capul nostru este egal cu 1 la acest punct, iar dimensiunea noastră este egal cu 4 998 00:55:05,850 --> 00:55:07,050 în acest moment, nu? 999 00:55:07,050 --> 00:55:08,960 >> Sunteți cu toții de acord că e cazul? 1000 00:55:08,960 --> 00:55:14,620 Deci, vom face capul plus dimensiunea, care ne dă 5, iar apoi am Mod de 5. 1001 00:55:14,620 --> 00:55:20,690 Primim 0, ceea ce ne spune că 0 este în cazul în care este coada noastră, unde avem spațiu. 1002 00:55:20,690 --> 00:55:22,010 >> Audiența: Ce este un capac? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: Capacitatea. 1004 00:55:23,520 --> 00:55:24,020 Scuze. 1005 00:55:24,020 --> 00:55:29,640 Astfel că este dimensiunea matrice dumneavoastră. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Da? 1008 00:55:36,047 --> 00:55:39,210 >> Audiența: [inaudibil] înainte ne întoarcem elementul? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Deci, ne-am muta capul sau a reveni în acest moment? 1010 00:55:46,270 --> 00:55:52,680 Deci, dacă ne mișcăm unul, descrește dimensiunea? 1011 00:55:52,680 --> 00:55:54,150 Stai. 1012 00:55:54,150 --> 00:55:55,770 Am uitat cu siguranta un alt. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Nu face nimic. 1015 00:56:01,990 --> 00:56:04,980 Nu există o altă formulă. 1016 00:56:04,980 --> 00:56:09,980 Da, v-ar dori să se întoarcă cap și apoi mutați-l înapoi. 1017 00:56:09,980 --> 00:56:13,270 >> Audiența: OK, pentru că în acest punct, capul era la 0, 1018 00:56:13,270 --> 00:56:18,452 și apoi doriți să reveniți index 0 și apoi face cap 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Corect. 1020 00:56:19,870 --> 00:56:22,820 Cred că e un alt cu formula un fel de acest lucru. 1021 00:56:22,820 --> 00:56:26,970 Eu nu-l au pe partea de sus capul meu ca Nu vreau să vă dau o greșit. 1022 00:56:26,970 --> 00:56:35,470 Dar cred că e perfect valabil la să zicem, OK, păstra acest element-- indiferent 1023 00:56:35,470 --> 00:56:40,759 element de capul lui este-- decrementa ta dimensiune, mutați capul peste, și retur 1024 00:56:40,759 --> 00:56:41,800 indiferent de acest element este. 1025 00:56:41,800 --> 00:56:44,760 Asta e perfect valabil. 1026 00:56:44,760 --> 00:56:45,260 OK. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Mă simt ca și cum acest lucru nu este ca most-- nu ești 1029 00:56:53,560 --> 00:56:55,740 O să ieși de aici cum ar fi, da, știu încercări. 1030 00:56:55,740 --> 00:56:56,880 Am tot primit. 1031 00:56:56,880 --> 00:56:57,670 Asta e OK. 1032 00:56:57,670 --> 00:57:00,200 Promit. 1033 00:57:00,200 --> 00:57:05,240 Dar structurile de date sunt ceva care este nevoie de o mulțime de timp să te obișnuiești. 1034 00:57:05,240 --> 00:57:10,010 Probabil una dintre cele mai grele lucruri, cred că, în cursul. 1035 00:57:10,010 --> 00:57:15,330 >> Deci, cu siguranta nevoie de repetiție și caută at-- I 1036 00:57:15,330 --> 00:57:20,050 Nu știu cu adevărat liste postat până când am făcut-o mult prea mult cu ei, 1037 00:57:20,050 --> 00:57:22,550 în același fel în care nu am făcut- înțeleg cu adevărat indicii 1038 00:57:22,550 --> 00:57:27,040 până l-am avut să-l predea pentru doi ani și face propriile mele psets cu ea. 1039 00:57:27,040 --> 00:57:28,990 Este nevoie de o mulțime de repetare și de timp. 1040 00:57:28,990 --> 00:57:32,600 Și în cele din urmă, se va fel de click. 1041 00:57:32,600 --> 00:57:36,320 >> Dar, în același timp, dacă aveți un fel de o înțelegere nivel ridicat de ceea ce 1042 00:57:36,320 --> 00:57:39,321 acestea fac, argumente pro și cons-- care este ceea ce 1043 00:57:39,321 --> 00:57:41,820 am într-adevăr tendința de a sublinia, în special în cursul intro. 1044 00:57:41,820 --> 00:57:45,511 Cum ar fi, de ce ne-ar folosi o să încercați pe un tablou? 1045 00:57:45,511 --> 00:57:48,010 Cum ar fi, care sunt pozitive și negative ale fiecăruia dintre aceste? 1046 00:57:48,010 --> 00:57:51,610 >> Și înțelegerea compromisuri între fiecare dintre aceste structuri 1047 00:57:51,610 --> 00:57:54,910 este ceea ce este mult mai important acum. 1048 00:57:54,910 --> 00:57:58,140 S-ar putea fi unul nebun întrebare sau două care este 1049 00:57:58,140 --> 00:58:03,710 O să vă rog să pună în aplicare împingere sau punerea în aplicare a pop sau Puneți în coadă și dequeue. 1050 00:58:03,710 --> 00:58:07,340 Dar pentru cea mai mare parte, cu care înțelegere de nivel superior și mai mult 1051 00:58:07,340 --> 00:58:09,710 de o înțelegere intuitivă este mai important decât în ​​realitate 1052 00:58:09,710 --> 00:58:11,250 fiind capabil să-l pună în aplicare. 1053 00:58:11,250 --> 00:58:14,880 >> Ar fi într-adevăr minunat dacă toți ar putea ieși și du-te să pună în aplicare un eseu, 1054 00:58:14,880 --> 00:58:19,720 dar am înțeles că nu e neapărat lucrul cel mai rezonabil chiar acum. 1055 00:58:19,720 --> 00:58:23,370 Dar puteți în PSET ta, dacă vrei a, iar apoi vei primi practică, 1056 00:58:23,370 --> 00:58:27,200 și atunci poate veți într-adevăr înțeleg. 1057 00:58:27,200 --> 00:58:27,940 Da? 1058 00:58:27,940 --> 00:58:30,440 >> Audiența: OK, deci care sunt cele noi menite să folosească în PSET? 1059 00:58:30,440 --> 00:58:31,916 Nu am nevoie de a utiliza unul dintre ei? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Da. 1061 00:58:32,540 --> 00:58:34,199 Deci, aveți alegerea ta. 1062 00:58:34,199 --> 00:58:36,740 Cred că în acest caz, putem vorbesc despre PSET un pic 1063 00:58:36,740 --> 00:58:40,480 pentru că am alergat prin acestea. 1064 00:58:40,480 --> 00:58:47,779 Deci, în PSET dumneavoastră, aveți dumneavoastră alegerea de încercări sau tabele de dispersie. 1065 00:58:47,779 --> 00:58:49,570 Unii oameni vor încerca și de a folosi filtre floare, 1066 00:58:49,570 --> 00:58:51,840 dar cei punct de vedere tehnic nu sunt corecte. 1067 00:58:51,840 --> 00:58:55,804 Din cauza naturii lor probabilistic, ei da rezultate fals pozitive, uneori. 1068 00:58:55,804 --> 00:58:57,095 Sunt privire rece în, totuși. 1069 00:58:57,095 --> 00:58:59,030 Va recomand cu caldura excelentă la ei, cel puțin. 1070 00:58:59,030 --> 00:59:03,260 Dar există posibilitatea alegerii între o tabelă de dispersie și o încercare. 1071 00:59:03,260 --> 00:59:06,660 Și care va fi în cazul în care încărcați în dicționarul ta. 1072 00:59:06,660 --> 00:59:09,230 >> Și veți avea nevoie pentru a alege funcția hash, 1073 00:59:09,230 --> 00:59:13,420 va trebui să alegeți câte pistoane ai, și aceasta va varia. 1074 00:59:13,420 --> 00:59:17,440 Ca și în cazul în care aveți mai multe găleți, Poate o să ruleze mai rapid. 1075 00:59:17,440 --> 00:59:22,790 Dar poate că îți pierzi o mulțime de spațiu în acest fel, deși. 1076 00:59:22,790 --> 00:59:26,320 Trebuie să-l dau seama. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> Audiența: Ai spus mai înainte că putem folosi alte funcții hash, 1079 00:59:29,875 --> 00:59:31,750 că noi nu trebuie să a crea o funcție hash? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Da, dreapta. 1081 00:59:32,666 --> 00:59:38,150 Deci, literalmente pentru funcția hash, cum ar fi google "funcție hash" 1082 00:59:38,150 --> 00:59:40,770 și căutați pentru unele misto. 1083 00:59:40,770 --> 00:59:43,250 Nu sunt de așteptat pentru a construi propriile funcții hash. 1084 00:59:43,250 --> 00:59:46,100 Oamenii petrec lor teze cu privire la aceste lucruri. 1085 00:59:46,100 --> 00:59:50,250 >> Deci, nu vă faceți griji cu privire la construirea propriu. 1086 00:59:50,250 --> 00:59:53,350 Găsi online, pentru a începe cu. 1087 00:59:53,350 --> 00:59:56,120 Unele dintre ele trebuie să manipula un pic 1088 00:59:56,120 --> 00:59:59,430 să se asigure că tipurile de returnare se potrivesc și fleacuri, astfel încât la început, 1089 00:59:59,430 --> 01:00:02,420 Mi-ar recomanda, folosind ceva într-adevăr ușor că poate doar 1090 01:00:02,420 --> 01:00:04,680 hash pe prima literă. 1091 01:00:04,680 --> 01:00:08,760 Și apoi o dată aveți că de lucru, încorporează o funcție hash cooler. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> Audiența: Ar fi un încerca să fie sau eficient dar doar mai greu de, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Deci o încercare, cred eu, este intuitiv greu să pună în aplicare 1095 01:00:15,880 --> 01:00:18,310 dar este foarte rapid. 1096 01:00:18,310 --> 01:00:20,620 Cu toate acestea, ocupă mai mult spațiu. 1097 01:00:20,620 --> 01:00:25,270 Din nou, puteți optimiza atât a celor din moduri diferite și există modalități sa-- 1098 01:00:25,270 --> 01:00:26,770 Audiența: Cât suntem clasificate pe asta? 1099 01:00:26,770 --> 01:00:27,540 Are matter-- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Deci gradate mod normal. 1101 01:00:29,164 --> 01:00:31,330 Vei fi clasificate pe design. 1102 01:00:31,330 --> 01:00:36,020 Indiferent de modul faci, vrei sa asigurați-vă că este la fel de elegant ca se poate 1103 01:00:36,020 --> 01:00:38,610 și la fel de eficient ca se poate. 1104 01:00:38,610 --> 01:00:41,950 Dar dacă alegeți o încercare sau hash masă, atâta timp cât funcționează, 1105 01:00:41,950 --> 01:00:45,350 suntem fericiti cu asta. 1106 01:00:45,350 --> 01:00:48,370 Și dacă utilizați ceva care hash pe prima literă, e în regulă, 1107 01:00:48,370 --> 01:00:51,410 ca poate ca-design înțelept. 1108 01:00:51,410 --> 01:00:53,410 Suntem, de asemenea, atingerea punct în acest semester-- 1109 01:00:53,410 --> 01:00:55,340 Nu știu dacă baieti noticed-- daca esti 1110 01:00:55,340 --> 01:00:58,780 clasele PSET refuza un pic din cauza designului și fleacuri, 1111 01:00:58,780 --> 01:00:59,900 asta e foarte bine. 1112 01:00:59,900 --> 01:01:02,960 Se ajunge la un punct în cazul în care dumneavoastră Programele devin mai complicate. 1113 01:01:02,960 --> 01:01:04,830 Există mai multe locuri vă puteți îmbunătăți pe. 1114 01:01:04,830 --> 01:01:06,370 >> Deci, este perfect normal. 1115 01:01:06,370 --> 01:01:08,810 Nu e ca esti face mai rău pe PSET ta. 1116 01:01:08,810 --> 01:01:11,885 E doar suntem a fi mai greu de pe tine acum. 1117 01:01:11,885 --> 01:01:13,732 Deci, toată lumea se simte. 1118 01:01:13,732 --> 01:01:14,940 Am sortat toate psets tale. 1119 01:01:14,940 --> 01:01:16,490 Știu că toată lumea se simte ea. 1120 01:01:16,490 --> 01:01:19,600 >> Deci, nu fi îngrijorat de asta. 1121 01:01:19,600 --> 01:01:23,580 Și dacă aveți întrebări despre psets anterioare sau moduri în care puteți îmbunătăți, 1122 01:01:23,580 --> 01:01:27,760 Eu încerc să comenteze specificul locuri, dar, uneori, e târziu 1123 01:01:27,760 --> 01:01:30,840 și eu obosesc. 1124 01:01:30,840 --> 01:01:34,885 Există și alte lucruri despre structuri de date? 1125 01:01:34,885 --> 01:01:37,510 Sunt sigur că voi nu prea vreau să mai vorbesc despre ele, 1126 01:01:37,510 --> 01:01:42,650 dar dacă există, sunt fericit să du-te peste ei, precum și orice 1127 01:01:42,650 --> 01:01:45,580 de la prelegere acest dribleze săptămână sau săptămâna trecută. 1128 01:01:45,580 --> 01:01:51,580 >> Știu că săptămâna trecută a fost tot comentariu, așa poate am sarit peste unele recenzie 1129 01:01:51,580 --> 01:01:54,190 de la curs. 1130 01:01:54,190 --> 01:01:58,230 Orice alte întrebări pot răspunde? 1131 01:01:58,230 --> 01:01:59,350 OK, în regulă. 1132 01:01:59,350 --> 01:02:02,400 Ei bine, voi ieși 15 minute mai devreme. 1133 01:02:02,400 --> 01:02:08,370 >> Sper că acest lucru a fost semi-ajutor, cel puțin, și Eu vă voi vedea voi săptămâna viitoare, 1134 01:02:08,370 --> 01:02:12,150 sau orelor de joi. 1135 01:02:12,150 --> 01:02:15,285 Există cereri de snacks-uri pentru săptămâna viitoare, e chestia? 1136 01:02:15,285 --> 01:02:17,459 Pentru că am uitat bomboane astăzi. 1137 01:02:17,459 --> 01:02:19,750 Și am adus bomboane trecut săptămână, dar a fost Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 deci nu erau ca șase persoane care a avut patru pungi de bomboane pentru ei înșiși. 1139 01:02:25,400 --> 01:02:28,820 Eu pot aduce starbursts din nou, dacă doriți. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 OK, sună bine. 1142 01:02:32,250 --> 01:02:35,050 Ai o zi mare, băieți. 1143 01:02:35,050 --> 01:02:39,510