1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [Glazbom] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: U redu. 5 00:00:12,900 --> 00:00:14,600 Svatko dobrodošli natrag u odjeljku. 6 00:00:14,600 --> 00:00:18,660 Nadam se da su svi uspješno oporavio od kviza 7 00:00:18,660 --> 00:00:19,510 od prošlog tjedna. 8 00:00:19,510 --> 00:00:22,564 Znam da je malo luda vremena na vrijeme. 9 00:00:22,564 --> 00:00:25,230 Kao što sam rekao prije, ako ste unutar standardne devijacije, 10 00:00:25,230 --> 00:00:28,188 stvarno ne brinite o tome, pogotovo za manje udoban dijelu. 11 00:00:28,188 --> 00:00:30,230 To je otprilike gdje bi trebali biti. 12 00:00:30,230 --> 00:00:32,850 >> Ako jeste super, onda super. 13 00:00:32,850 --> 00:00:33,650 Čast da vas. 14 00:00:33,650 --> 00:00:36,149 A ako se osjećate kao da je potrebno malo više pomoći, molimo 15 00:00:36,149 --> 00:00:38,140 slobodno doći na bilo koji od TFS. 16 00:00:38,140 --> 00:00:40,030 Svi smo ovdje da vam pomognemo. 17 00:00:40,030 --> 00:00:40,960 >> Zato učimo. 18 00:00:40,960 --> 00:00:44,550 Zato sam ovdje svaki ponedjeljak za vas momci i na uredu sati četvrtkom. 19 00:00:44,550 --> 00:00:48,130 Dakle, slobodno javite mi Ako ste zabrinuti o bilo čemu 20 00:00:48,130 --> 00:00:52,450 ili ako postoji išta na kvizu da li stvarno želite baviti. 21 00:00:52,450 --> 00:00:56,940 >> Dakle, program za danas je sve o strukturama podataka. 22 00:00:56,940 --> 00:01:01,520 Neki od njih su samo će biti samo da bi ste upoznati s tim. 23 00:01:01,520 --> 00:01:04,870 Ne smijete nikada provoditi oni u ovoj klasi. 24 00:01:04,870 --> 00:01:08,690 Neki od njih ćete, kao što je za svoj bukvar pset. 25 00:01:08,690 --> 00:01:11,380 >> Vi ćete imati svoj izbor između hash tablica i pokušaja. 26 00:01:11,380 --> 00:01:13,680 Tako smo definitivno ćemo se ide preko njih. 27 00:01:13,680 --> 00:01:18,690 To će biti definitivno više vrsta od razine dijelu visokog danas, ipak, 28 00:01:18,690 --> 00:01:22,630 jer postoji puno njih, a ako smo išli u detalje provedbe 29 00:01:22,630 --> 00:01:26,490 na sve to, mi ne bi čak i dobiti kroz povezanim popisima 30 00:01:26,490 --> 00:01:28,520 i možda malo hash tablica. 31 00:01:28,520 --> 00:01:31,200 >> Dakle nose sa mnom. 32 00:01:31,200 --> 00:01:33,530 Nećemo se radi koliko kodiranja ovaj put. 33 00:01:33,530 --> 00:01:36,870 Ako imate bilo kakvih pitanja o tome ili ako želite vidjeti provodi 34 00:01:36,870 --> 00:01:39,260 ili ga isprobali, Ja svakako preporučujemo 35 00:01:39,260 --> 00:01:44,250 će study.cs50.net, koji ima primjera sve to. 36 00:01:44,250 --> 00:01:46,400 To će imati svoje PowerPoints s bilješkama koje smo 37 00:01:46,400 --> 00:01:50,860 imaju tendenciju da koriste kao neki programiranje vježbe, pogotovo za stvari 38 00:01:50,860 --> 00:01:55,250 kao što povezanim popisima i binarnom drveće hrpe i mehanizme. 39 00:01:55,250 --> 00:01:59,590 Pa malo više na visokoj razini, što može biti lijepo za vas dečki. 40 00:01:59,590 --> 00:02:01,320 >> Dakle, s tim ćemo početi. 41 00:02:01,320 --> 00:02:03,060 I također, yes-- kvizova. 42 00:02:03,060 --> 00:02:06,550 Mislim da većina vas koji su u moj poglavlje ima svoje kvizove, 43 00:02:06,550 --> 00:02:12,060 ali tko dolazi u ili nekog razloga ne, oni su upravo ovdje u prednjem. 44 00:02:12,060 --> 00:02:12,740 >> Tako povezane liste. 45 00:02:12,740 --> 00:02:15,650 Znam ovu vrstu ide Sigurnosno prije kviza. 46 00:02:15,650 --> 00:02:17,940 To je bilo prije tjedan dana koje smo naučili o tome. 47 00:02:17,940 --> 00:02:21,040 No, u ovom slučaju, samo ćemo idu malo više u dubinu. 48 00:02:21,040 --> 00:02:25,900 >> Pa zašto bismo mogli odabrati povezani popis preko niza? 49 00:02:25,900 --> 00:02:27,130 Ono što ih razlikuje? 50 00:02:27,130 --> 00:02:27,630 Da? 51 00:02:27,630 --> 00:02:30,464 >> PUBLIKA: možete proširiti povezan popis u odnosu na niz je fiksne veličine. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Točno. 53 00:02:31,171 --> 00:02:33,970 Niz je fiksna veličina, dok povezani popis ima promjenjivu veličinu. 54 00:02:33,970 --> 00:02:36,970 Dakle, ako ne znamo kako koliko želimo pohraniti, 55 00:02:36,970 --> 00:02:39,880 Popis povezani daje nam velika način da to učinite, jer možemo samo 56 00:02:39,880 --> 00:02:43,730 dodaj na drugom čvoru i dodati na još jedan čvor i dodati na drugom čvoru. 57 00:02:43,730 --> 00:02:45,750 No, ono što bi moglo biti trade-off? 58 00:02:45,750 --> 00:02:49,521 Se bilo tko sjetiti trade-off između polja i povezane liste? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> PUBLIKA: Morate proći kroz sve način 61 00:02:51,460 --> 00:02:53,738 po popisu povezan naći element u popisu. 62 00:02:53,738 --> 00:02:55,570 U nizu, možete samo pronaći element. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Točno. 64 00:02:56,278 --> 00:02:57,120 Tako je s arrays-- 65 00:02:57,120 --> 00:02:58,500 >> PUBLIKA: [nečujan]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: S polja, imamo ono što se naziva izravnim pristupom. 67 00:03:01,090 --> 00:03:04,820 Znači da, ako želimo ono što je ikada peta točka popisa 68 00:03:04,820 --> 00:03:07,230 ili peta točka našeg polje, mi samo možemo ga zgrabiti. 69 00:03:07,230 --> 00:03:10,440 Ako je popis povezani, imamo za prolazak kroz, zar ne? 70 00:03:10,440 --> 00:03:14,020 Dakle, pristup element u Niz je konstanta vrijeme, 71 00:03:14,020 --> 00:03:19,530 dok je s popisa povezan To bi najvjerojatnije biti linearno vrijeme, jer možda 72 00:03:19,530 --> 00:03:21,370 naš element je sve na kraju. 73 00:03:21,370 --> 00:03:23,446 Moramo tražiti kroz sve. 74 00:03:23,446 --> 00:03:25,320 Dakle, sa svim tim podacima strukture idemo 75 00:03:25,320 --> 00:03:29,330 treba provesti malo više vremena na, što su plusa i negative. 76 00:03:29,330 --> 00:03:31,480 Kad možda želimo koristiti jedan nad drugim? 77 00:03:31,480 --> 00:03:34,970 I to je vrsta veća stvar oduzeti. 78 00:03:34,970 --> 00:03:40,140 >> Tako imamo ovdje definicija čvora. 79 00:03:40,140 --> 00:03:43,040 To je kao jedan element u naš popis povezani, zar ne? 80 00:03:43,040 --> 00:03:46,180 Tako smo svi upoznati s našim typedef konstrukt, 81 00:03:46,180 --> 00:03:47,980 koji smo otišli više u pregledu prošli put. 82 00:03:47,980 --> 00:03:53,180 To je zapravo samo stvaranje druga vrsta podataka koje smo mogli koristiti. 83 00:03:53,180 --> 00:03:57,930 >> I u ovom slučaju, to je neki čvor koje će održati neki broj u. 84 00:03:57,930 --> 00:04:00,210 I što onda je drugi dio ovdje? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Svatko? 87 00:04:05,677 --> 00:04:06,680 >> PUBLIKA: [nečujan]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Da. 89 00:04:07,020 --> 00:04:08,400 To je kazaljka na sljedeći čvor. 90 00:04:08,400 --> 00:04:12,610 Dakle, to bi zapravo trebao biti ovdje. 91 00:04:12,610 --> 00:04:18,790 To je pokazivač tipa čvor na sljedeću stvar. 92 00:04:18,790 --> 00:04:22,410 I to je ono što oni obuhvaća naše čvor. 93 00:04:22,410 --> 00:04:24,060 Cool. 94 00:04:24,060 --> 00:04:29,390 >> U redu, u potrazi, kao što smo bili Upravo govoreći prije ruke, ako ste 95 00:04:29,390 --> 00:04:31,840 ide pretraživanje, morate se zapravo ponoviti 96 00:04:31,840 --> 00:04:33,660 kroz popis povezane. 97 00:04:33,660 --> 00:04:38,530 Dakle, ako smo u potrazi za broj 9, mi bi početi u našoj glavi 98 00:04:38,530 --> 00:04:41,520 i to nas upućuje na početku našeg popisa povezani, zar ne? 99 00:04:41,520 --> 00:04:44,600 A mi kažemo, u redu, to čini čvor sadrže broj 9? 100 00:04:44,600 --> 00:04:45,690 Ne? 101 00:04:45,690 --> 00:04:47,500 >> U redu, idite na sljedeću. 102 00:04:47,500 --> 00:04:48,312 Slijedite ga. 103 00:04:48,312 --> 00:04:49,520 Sadrži li broj 9? 104 00:04:49,520 --> 00:04:50,570 Ne. 105 00:04:50,570 --> 00:04:51,550 Slijedite sljedeći. 106 00:04:51,550 --> 00:04:55,490 >> Dakle, moramo se zapravo ponoviti kroz naše liste povezane. 107 00:04:55,490 --> 00:05:00,070 Ne možemo samo ići izravno na kojoj 9. 108 00:05:00,070 --> 00:05:05,860 A ako ti dečki zapravo žele vidjeti neke pseudo-koda tamo gore. 109 00:05:05,860 --> 00:05:10,420 Imamo neku funkciju pretraživanja ovdje koji traje in-- ono što je potrebno u? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Što ti misliš? 112 00:05:14,320 --> 00:05:15,960 Tako lako. 113 00:05:15,960 --> 00:05:17,784 Što je ovo? 114 00:05:17,784 --> 00:05:18,700 PUBLIKA: [nečujan]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: Broj tražimo. 116 00:05:20,366 --> 00:05:20,980 Pravo? 117 00:05:20,980 --> 00:05:22,875 A što bi to odgovarati? 118 00:05:22,875 --> 00:05:25,020 To je pokazivač? 119 00:05:25,020 --> 00:05:26,000 >> PUBLIKA: čvor. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: čvor na popis da gledamo, zar ne? 121 00:05:28,980 --> 00:05:33,700 Dakle, imamo neke čvorovi su kazaljke ovdje. 122 00:05:33,700 --> 00:05:37,240 To je točka koja će se zapravo ponoviti kroz naše liste. 123 00:05:37,240 --> 00:05:39,630 Mi ga postaviti jednaka popis jer to je samo 124 00:05:39,630 --> 00:05:44,380 postavljanje je jednaka početak našeg popisa povezane. 125 00:05:44,380 --> 00:05:50,660 >> I dok to nije NULL, dok je još uvijek imamo stvari u našem listu, 126 00:05:50,660 --> 00:05:55,580 provjerite je li taj čvor ima Broj tražimo. 127 00:05:55,580 --> 00:05:57,740 Povratak istina. 128 00:05:57,740 --> 00:06:01,070 Inače, ažurirati ga, zar ne? 129 00:06:01,070 --> 00:06:04,870 >> Ako je NULL, izađemo iz naše while petlja i povratak lažna 130 00:06:04,870 --> 00:06:08,340 jer to znači da nismo ga pronašli. 131 00:06:08,340 --> 00:06:11,048 Da li su svi dobili kako se to radi? 132 00:06:11,048 --> 00:06:11,548 U redu. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Tako je s umetanja, što imaju tri različita načina. 135 00:06:20,260 --> 00:06:25,250 Možete prepend, možete dodati i možete umetnuti u ponekog. 136 00:06:25,250 --> 00:06:28,215 U ovom slučaju, mi smo će napraviti prepend. 137 00:06:28,215 --> 00:06:33,380 Se bilo tko znati kako one tri slučaja mogao razlikovati? 138 00:06:33,380 --> 00:06:36,920 >> Tako prepend znači da ste stavili je na prednjoj strani popisa. 139 00:06:36,920 --> 00:06:39,770 Dakle, to bi značilo da bez obzira što je vaš čvor je, bez obzira na 140 00:06:39,770 --> 00:06:43,160 što je vrijednost, idete da ga upravo ovdje ispred, u redu? 141 00:06:43,160 --> 00:06:45,160 To će biti prvi element u svoj popis. 142 00:06:45,160 --> 00:06:49,510 >> Ako ga dodati, to će ići na stražnjoj strani popisa. 143 00:06:49,510 --> 00:06:54,010 I umetnuti u ponekog znači da ste će staviti stvari na mjesto 144 00:06:54,010 --> 00:06:57,700 gdje se čuva vaš popis povezani razvrstani. 145 00:06:57,700 --> 00:07:00,810 Opet, kako se koristiti one i kada koristite 146 00:07:00,810 --> 00:07:02,530 njih će varirati ovisno o vašem slučaju. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Ako to ne treba biti razvrstani, prepend teži 149 00:07:07,750 --> 00:07:10,460 da bude ono što većina ljudi koristiti, jer vi ne 150 00:07:10,460 --> 00:07:15,680 moraju proći kroz cijeli popis pronaći kraj da ga dodati na, zar ne? 151 00:07:15,680 --> 00:07:17,720 Vi samo možete ga staviti u pravu. 152 00:07:17,720 --> 00:07:21,930 >> Tako ćemo proći Umetanje 1 upravo sada. 153 00:07:21,930 --> 00:07:26,360 Dakle, jedna stvar koju ću Preporučujemo na ovoj pset 154 00:07:26,360 --> 00:07:29,820 je izvući stvari, kao i uvijek. 155 00:07:29,820 --> 00:07:35,130 To je vrlo važno da ažurirate svoje naputke u ispravnom redoslijedu 156 00:07:35,130 --> 00:07:38,620 jer ako ih ažurirati malo izvan reda, 157 00:07:38,620 --> 00:07:42,210 ti ćeš završiti gubi dijelove svog popisa. 158 00:07:42,210 --> 00:07:49,680 >> Tako na primjer, u ovom slučaju, mi smo govoreći glavu na samo točka na 1. 159 00:07:49,680 --> 00:07:56,070 Ako mi samo to bez spremanja ovaj 1, 160 00:07:56,070 --> 00:07:58,570 nemamo pojma što 1. treba ukazati sada 161 00:07:58,570 --> 00:08:02,490 jer smo izgubili ono što Glava je ukazao na. 162 00:08:02,490 --> 00:08:05,530 Dakle, jedna stvar koju treba zapamtiti kada radite prepend 163 00:08:05,530 --> 00:08:09,630 je spasiti što se glava ukazuje na prvom, 164 00:08:09,630 --> 00:08:15,210 zatim ga preraspodijeliti, a zatim ažurirati što je vaš novi čvor trebao ukazati. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 U ovom slučaju, to je jedan od načina da to učinite. 167 00:08:22,560 --> 00:08:25,440 >> Dakle, ako smo to učinili na taj način gdje smo samo rasporediti glavu, 168 00:08:25,440 --> 00:08:30,320 gubimo osnovi našu stranicu cijeli popis, zar ne? 169 00:08:30,320 --> 00:08:38,000 Jedan od načina da to učinite je da se 1 bod za Sljedeći, a zatim su glave točku na 1. 170 00:08:38,000 --> 00:08:42,650 Ili možete učiniti vrsta kao privremenog skladištenja, što sam govorio o tome. 171 00:08:42,650 --> 00:08:45,670 >> Ali prenamjene vaš upućuje u ispravnom redoslijedu 172 00:08:45,670 --> 00:08:48,750 će biti vrlo, vrlo važno za ovaj pset. 173 00:08:48,750 --> 00:08:53,140 Inače, ti ćeš imati mljeveno meso tablice ili pokušati to samo će biti 174 00:08:53,140 --> 00:08:56,014 samo dio riječi koje Želite a zatim you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 PUBLIKA: Što je privremena pohranu stvar koju su razgovarali? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: privremeno skladištenje. 177 00:09:00,305 --> 00:09:02,760 Tako je u osnovi jedan način na koji možete to učiniti 178 00:09:02,760 --> 00:09:07,650 je pohraniti glavu nešto, kao što su pohraniti ga na privremenu varijablu. 179 00:09:07,650 --> 00:09:11,250 Dodijeliti na 1 i zatim ažurirati 1 do točke 180 00:09:11,250 --> 00:09:13,830 što god glava koristi ukazati. 181 00:09:13,830 --> 00:09:16,920 Na taj način je očito više elegantan, jer vas 182 00:09:16,920 --> 00:09:20,770 ne trebaju privremenu vrijednost, ali Upravo nudi još jedan način da to učinite. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 A mi zapravo nemamo neki kod za to. 185 00:09:25,790 --> 00:09:28,080 Tako povezani popisu, mi zapravo imaju neki kod. 186 00:09:28,080 --> 00:09:31,930 Dakle stavite ovdje, ovo je prepending. 187 00:09:31,930 --> 00:09:34,290 Dakle, ovaj ga ulazi u glavu. 188 00:09:34,290 --> 00:09:38,820 >> Dakle, prva stvar koju trebate stvoriti novi čvor, naravno, 189 00:09:38,820 --> 00:09:40,790 i provjerite NULL. 190 00:09:40,790 --> 00:09:43,250 Uvijek dobro. 191 00:09:43,250 --> 00:09:47,840 A onda morate dodijeliti vrijednosti. 192 00:09:47,840 --> 00:09:51,260 Kad god stvoriti novi čvor, te ne znam što to pokazuje na sljedeći, 193 00:09:51,260 --> 00:09:54,560 tako da ga želite inicijalizirati na nulu. 194 00:09:54,560 --> 00:09:58,760 Ako to ne završiti upućuje na nešto drugo, ona dobiva rasporediti i to je u redu. 195 00:09:58,760 --> 00:10:00,740 Ako je to prva stvar na popisu, to treba 196 00:10:00,740 --> 00:10:04,270 ukazati na nulu, jer to je kraj popisa. 197 00:10:04,270 --> 00:10:12,410 >> Pa onda da ga ubacite, vidimo ovdje pripisuju sljedeći vrijednost našeg čvora 198 00:10:12,410 --> 00:10:17,380 da se sve što je glava, što je ono što smo imali ovdje. 199 00:10:17,380 --> 00:10:19,930 To je ono što smo mi napravili. 200 00:10:19,930 --> 00:10:25,820 A onda smo dodjeljivanje glave do točke na naš novi čvor, jer zapamtite, 201 00:10:25,820 --> 00:10:31,090 Novi je neki pointer na čvoru, i to je upravo ono što je glava. 202 00:10:31,090 --> 00:10:34,370 To je upravo razlog zašto smo ima tu strelicu Accessor. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Cool? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> PUBLIKA: Moramo li inicijalizirati nove Dalje da NULL prvi, 207 00:10:41,100 --> 00:10:44,240 ili možemo samo ga resetirali na glavu? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: Novi iduće treba biti NULL za početak 209 00:10:48,210 --> 00:10:53,760 jer ne znate gdje će biti. 210 00:10:53,760 --> 00:10:56,100 Također, ova je vrsta Baš kao paradigmu. 211 00:10:56,100 --> 00:10:59,900 Možete ga postaviti jednak NULL samo da bi sigurni da su svi vaši kladionica 212 00:10:59,900 --> 00:11:04,070 prije nego što učinite bilo preraspodjelu tako da ti si uvijek zajamčeno da će 213 00:11:04,070 --> 00:11:08,880 se ukazuje na određenu vrijednost u odnosu poput vrijednosti smeća. 214 00:11:08,880 --> 00:11:12,210 Jer, da, mi dodijeliti Novi iduće automatski, 215 00:11:12,210 --> 00:11:15,420 ali to je više kao dobra praksa za inicijalizaciju 216 00:11:15,420 --> 00:11:19,270 na taj način, a zatim preraspodijeliti. 217 00:11:19,270 --> 00:11:23,420 >> U redu, tako da dvostruko povezani popisi sada. 218 00:11:23,420 --> 00:11:24,601 Što mi mislimo? 219 00:11:24,601 --> 00:11:26,350 Ono što je drugačije s dvostruko povezani liste? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Dakle, u našim povezanim popisima, možemo pomicati samo u jednom smjeru, zar ne? 222 00:11:34,300 --> 00:11:35,270 Imamo samo sljedeći. 223 00:11:35,270 --> 00:11:36,760 Možemo samo ići naprijed. 224 00:11:36,760 --> 00:11:40,300 >> S popisa dvostruko povezana, možemo pomaknuti unatrag. 225 00:11:40,300 --> 00:11:44,810 Dakle, imamo ne samo broj koji želimo pohraniti, 226 00:11:44,810 --> 00:11:50,110 imamo gdje se ukazuje na sljedeći i gdje smo upravo došli. 227 00:11:50,110 --> 00:11:52,865 Dakle, to omogućuje neki bolji obuhvaćanje. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Dakle, dvostruko povezani čvorovi, Vrlo slično, zar ne? 230 00:12:01,240 --> 00:12:05,000 Jedina razlika je sad imaju sljedeća i prethodna. 231 00:12:05,000 --> 00:12:06,235 To je jedina razlika. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Dakle, ako bismo prepend ili append-- smo nemaju kod za ovo gore here-- 234 00:12:14,790 --> 00:12:17,830 ali ako ste bili pokušati umetnite ga, važnu stvar 235 00:12:17,830 --> 00:12:19,980 je li potrebno napraviti jeste li dodjeljivanje 236 00:12:19,980 --> 00:12:23,360 i svoje prethodne i vaši Sljedeći pokazivač ispravno. 237 00:12:23,360 --> 00:12:29,010 Dakle, u ovom slučaju, što bi ne samo inicijalizirati iduće, 238 00:12:29,010 --> 00:12:31,820 što inicijalizirati prethodna. 239 00:12:31,820 --> 00:12:36,960 Ako smo na čelu popisa, mi bi ne samo glava jednaka nova, 240 00:12:36,960 --> 00:12:41,750 ali naš novi prethodna trebao ukazuju na glavu, zar ne? 241 00:12:41,750 --> 00:12:43,380 >> To je jedina razlika. 242 00:12:43,380 --> 00:12:47,200 A ako želite više prakse s te s povezanim popisima, s umetanje, 243 00:12:47,200 --> 00:12:49,900 s brisanjem, s umetkom u assorted popis, 244 00:12:49,900 --> 00:12:52,670 molimo provjerite study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Postoji hrpa velikih vježbi. 246 00:12:54,870 --> 00:12:55,870 Ja visoko preporučiti ih. 247 00:12:55,870 --> 00:12:59,210 Volio bih da smo imali vremena proći kroz njih ali ima puno strukture podataka 248 00:12:59,210 --> 00:13:01,530 da se kroz. 249 00:13:01,530 --> 00:13:02,650 >> U redu, tako da hash tablice. 250 00:13:02,650 --> 00:13:07,070 Ovo je vjerojatno najviše korisne bitni za vaš pset 251 00:13:07,070 --> 00:13:11,090 ovdje, jer ti ćeš biti provedbe jednog od njih, ili probati. 252 00:13:11,090 --> 00:13:12,200 Volim hash tablice. 253 00:13:12,200 --> 00:13:13,110 Oni su prilično cool. 254 00:13:13,110 --> 00:13:17,080 >> Tako je u osnovi ono što događa je hash tablicu 255 00:13:17,080 --> 00:13:22,050 je kada smo stvarno treba brze umetanje, brisanje i pretraživanje. 256 00:13:22,050 --> 00:13:25,010 To su stvari koje smo prioriteta u hash tablici. 257 00:13:25,010 --> 00:13:29,500 Oni mogu biti prilično velika, ali kao što ćemo vidjeti pokušaja, 258 00:13:29,500 --> 00:13:33,040 postoje stvari koje su mnogo veći. 259 00:13:33,040 --> 00:13:38,330 >> Ali u osnovi, sve ljestve stol je hash funkcija 260 00:13:38,330 --> 00:13:47,215 da vam kaže što kantu staviti svaki vaših podataka, svaki od svojih elemenata. 261 00:13:47,215 --> 00:13:51,140 Jednostavan način da razmišljaju o hash tablicu je da je samo kante stvari, 262 00:13:51,140 --> 00:13:51,770 zar ne? 263 00:13:51,770 --> 00:13:59,720 Dakle, kada ste sortiranje stvari koje kao prvo slovo svog imena, 264 00:13:59,720 --> 00:14:01,820 to je vrsta kao što su hash tablicu. 265 00:14:01,820 --> 00:14:06,180 >> Dakle, ako su za skupinu vi je u skupinama tko ime počinje 266 00:14:06,180 --> 00:14:11,670 s ovamo, ili tko je rođendan je u siječnju, veljači, ožujku, 267 00:14:11,670 --> 00:14:15,220 što god da je učinkovito stvarajući hash tablicu. 268 00:14:15,220 --> 00:14:18,120 To je samo stvaranje kante koje li sortirati elemente u 269 00:14:18,120 --> 00:14:19,520 tako da možete pronaći ih lakše. 270 00:14:19,520 --> 00:14:22,300 Dakle, ovaj put, kada mi je potrebno pronaći jedan od vas, 271 00:14:22,300 --> 00:14:24,680 Ja ne moram tražiti kroz svaki od vaših imena. 272 00:14:24,680 --> 00:14:29,490 Mogu biti kao, oh, znam da Danielle rođendan je in-- 273 00:14:29,490 --> 00:14:30,240 PUBLIKA: --April. 274 00:14:30,240 --> 00:14:30,948 Zvučnik 1: travanj. 275 00:14:30,948 --> 00:14:33,120 Tako sam gledati u mom travnja kanta, i uz malo sreće, 276 00:14:33,120 --> 00:14:38,270 ona će biti samo jedan u postoji i moje vrijeme je bio konstanta u tom smislu, 277 00:14:38,270 --> 00:14:41,230 a ako moram gledati kroz cijelu hrpa ljudi, 278 00:14:41,230 --> 00:14:43,090 to će potrajati mnogo duže. 279 00:14:43,090 --> 00:14:45,830 Dakle, hash tablice su stvarno samo kante. 280 00:14:45,830 --> 00:14:48,630 Jednostavan način da misle o njima. 281 00:14:48,630 --> 00:14:52,930 >> Dakle, vrlo važna stvar o hash tablica hash funkcija. 282 00:14:52,930 --> 00:14:58,140 Dakle, ono što sam upravo govorio, kao što su Vaše prvo slovo svoje ime 283 00:14:58,140 --> 00:15:01,450 ili vaš rođendan mjeseca, To su ideje koje 284 00:15:01,450 --> 00:15:03,070 stvarno korelira s hash funkcije. 285 00:15:03,070 --> 00:15:08,900 To je samo način odlučivanja koji Bucket ste elementa ide u, u redu? 286 00:15:08,900 --> 00:15:14,850 Tako je za ovu pset, možete pogledati prilično mnogo bilo hash funkcija želite. 287 00:15:14,850 --> 00:15:16,030 >> Ne moraju biti svoj. 288 00:15:16,030 --> 00:15:21,140 Postoje neke stvarno cool one iz ima koji radimo sve vrste lude matematici. 289 00:15:21,140 --> 00:15:25,170 A ako želite napraviti svoj spellchecker super brzi, 290 00:15:25,170 --> 00:15:27,620 Ja bih svakako gledati u jednu od njih. 291 00:15:27,620 --> 00:15:32,390 >> No, tu su i one jednostavne, poput računati 292 00:15:32,390 --> 00:15:39,010 zbroj riječi, kao što su svako slovo ima broj. 293 00:15:39,010 --> 00:15:39,940 Izračunaj sumu. 294 00:15:39,940 --> 00:15:42,230 To određuje kantu. 295 00:15:42,230 --> 00:15:45,430 Oni također imaju one lako da su baš kao i svi ovdje, 296 00:15:45,430 --> 00:15:47,050 sve B je ovdje. 297 00:15:47,050 --> 00:15:48,920 Bilo koji od njih. 298 00:15:48,920 --> 00:15:55,770 >> U osnovi, to samo govori što Indeks lepezu svoga elementa treba ići u. 299 00:15:55,770 --> 00:15:58,690 Samo odlučivanju bucket-- to je sve hash funkcija. 300 00:15:58,690 --> 00:16:04,180 Dakle, ovdje imamo primjer koji je Samo prvo slovo niza 301 00:16:04,180 --> 00:16:05,900 da sam samo pričaju. 302 00:16:05,900 --> 00:16:11,900 >> Dakle, imate neke mljeveno meso to je samo Prvo slovo vašeg gudački minus A, 303 00:16:11,900 --> 00:16:16,090 koji će vam dati neke broj između 0 i 25. 304 00:16:16,090 --> 00:16:20,790 A ono što želite učiniti je pobrinite se da to predstavlja 305 00:16:20,790 --> 00:16:24,110 veličina vašeg mljeveno meso table-- koliko kante postoje. 306 00:16:24,110 --> 00:16:25,860 Uz mnoge od tih hash funkcije, oni su 307 00:16:25,860 --> 00:16:31,630 će se vraćaju vrijednosti koje bi moglo biti daleko iznad broja kante 308 00:16:31,630 --> 00:16:33,610 da zapravo imaju u svom hash tablici, 309 00:16:33,610 --> 00:16:37,240 tako da je potrebno napraviti je li i mod oni. 310 00:16:37,240 --> 00:16:42,190 Inače, to će reći, Oh, to bi trebalo biti u kantu 5000 311 00:16:42,190 --> 00:16:46,040 ali imate samo 30 kante u vašem hash tablici. 312 00:16:46,040 --> 00:16:49,360 I naravno, svi znamo da je će rezultirati u nekim ludim pogreške. 313 00:16:49,360 --> 00:16:52,870 Dakle, pobrinite se da mod po veličina vašeg hash tablice. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Cool. 316 00:16:58,930 --> 00:17:00,506 Tako sudara. 317 00:17:00,506 --> 00:17:02,620 Je li sve dobro do sada? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> PUBLIKA: Zašto bi povratak takav masivan vrijednost? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: Ovisno o algoritmu da je vaš hash funkcija koristi. 321 00:17:09,210 --> 00:17:12,270 Neki od njih će učiniti luda množenja. 322 00:17:12,270 --> 00:17:16,270 I to je sve o uzimajući čak i distribucije, 323 00:17:16,270 --> 00:17:18,490 pa oni su neki stvarno lude stvari ponekad. 324 00:17:18,490 --> 00:17:20,960 To je sve. 325 00:17:20,960 --> 00:17:22,140 Bilo što drugo? 326 00:17:22,140 --> 00:17:22,829 U redu. 327 00:17:22,829 --> 00:17:24,480 >> Tako sudara. 328 00:17:24,480 --> 00:17:29,270 Uglavnom, kao što sam rekao ranije, U najboljem slučaju, 329 00:17:29,270 --> 00:17:32,040 bilo kantu gledam je će imati jednu stvar, 330 00:17:32,040 --> 00:17:34,160 tako da ne moram gledati na sve, zar ne? 331 00:17:34,160 --> 00:17:37,040 Ja ni znati da je tamo ili je to ne, i to je ono što stvarno želite. 332 00:17:37,040 --> 00:17:43,960 Ali ako imamo na desetke tisuća Točke podataka i manje od tog broja 333 00:17:43,960 --> 00:17:48,700 žlica, ćemo imati sudari gdje na kraju nesto 334 00:17:48,700 --> 00:17:54,210 će morati završiti u Kanta koja već ima jedan element. 335 00:17:54,210 --> 00:17:57,390 >> Dakle, pitanje je, što radimo u tom slučaju? 336 00:17:57,390 --> 00:17:58,480 Što nam je činiti? 337 00:17:58,480 --> 00:17:59,300 Mi već imamo nešto tamo? 338 00:17:59,300 --> 00:18:00,060 Nemojte mi samo ga izbaciti? 339 00:18:00,060 --> 00:18:00,700 >> Ne. 340 00:18:00,700 --> 00:18:01,980 Moramo zadržati obojicu. 341 00:18:01,980 --> 00:18:06,400 Dakle, način na koji smo obično to je ono? 342 00:18:06,400 --> 00:18:08,400 Kakva je struktura podataka samo smo razgovarali o tome? 343 00:18:08,400 --> 00:18:09,316 PUBLIKA: Vezana lista. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: Popis povezani. 345 00:18:10,500 --> 00:18:16,640 Tako sada, umjesto da svaki od njih kante samo ima jedan element, 346 00:18:16,640 --> 00:18:24,020 to će sadržavati povezano popis elementi koji su raspršene u nju. 347 00:18:24,020 --> 00:18:27,588 OK, ne svi vrsta dobiti tu ideju? 348 00:18:27,588 --> 00:18:30,546 Budući da nismo mogli imati niz jer mi ne znamo kako mnoge stvari 349 00:18:30,546 --> 00:18:31,730 će biti tamo. 350 00:18:31,730 --> 00:18:36,540 Popis povezani omogućuje nam da imaju samo točan broj koji 351 00:18:36,540 --> 00:18:38,465 su raspršene u tu kantu, zar ne? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Dakle linearno sondiranja je osnovi to idea-- 354 00:18:50,500 --> 00:18:52,300 to je jedan od načina da se bave sudara. 355 00:18:52,300 --> 00:18:58,010 Ono što možete učiniti je li, u ovom Slučaj, bobica je raspršen u 1 356 00:18:58,010 --> 00:19:01,130 a već imamo nešto postoji, samo 357 00:19:01,130 --> 00:19:04,840 zadržati ide prema dolje dok nađete prazan utor. 358 00:19:04,840 --> 00:19:06,370 To je jedan od načina da ga obrađuju. 359 00:19:06,370 --> 00:19:09,020 Drugi način da obrađuju što je s onim što smo upravo 360 00:19:09,020 --> 00:19:12,280 called-- povezan Popis naziva ulančavanje. 361 00:19:12,280 --> 00:19:20,510 >> Dakle, ova ideja funkcionira, ako Vaš hash tablicu mislite 362 00:19:20,510 --> 00:19:24,150 je mnogo veći od Vaši podaci postaviti ili ako vas 363 00:19:24,150 --> 00:19:28,870 želite probati i minimizirati ulančavanje dok je to neophodno. 364 00:19:28,870 --> 00:19:34,050 Dakle, jedna stvar je linearna sondiranja očito znači 365 00:19:34,050 --> 00:19:37,290 da je vaš hash funkcije nije baš tako korisna 366 00:19:37,290 --> 00:19:42,200 jer ćeš završiti pomoću Vaš hash funkcija, uzimajući do točke, 367 00:19:42,200 --> 00:19:46,400 što Linearna probe do neko mjesto koje je na raspolaganju. 368 00:19:46,400 --> 00:19:49,670 Ali sada, naravno, ništa ostalo što se završava tamo, 369 00:19:49,670 --> 00:19:52,050 ti si idući u morati traži još dalje. 370 00:19:52,050 --> 00:19:55,650 >> A tu je puno više Rashodi za pretraživanje koji 371 00:19:55,650 --> 00:19:59,820 ide u unos element u svom hash tablicu sada, zar ne? 372 00:19:59,820 --> 00:20:05,640 I sada kada idete i pokušati naći bobica opet, ti ćeš ga hash, 373 00:20:05,640 --> 00:20:07,742 a to će reći: oh, gledati u kantu 1, 374 00:20:07,742 --> 00:20:09,700 i to neće biti u kantu 1, tako da ste 375 00:20:09,700 --> 00:20:11,970 će morati proći kroz ostatak njih. 376 00:20:11,970 --> 00:20:17,720 Tako da je ponekad korisno, a u većini slučajeva, 377 00:20:17,720 --> 00:20:22,660 ćemo reći da ulančavanje je ono što želite učiniti. 378 00:20:22,660 --> 00:20:25,520 >> Tako smo razgovarali o tome i ranije. 379 00:20:25,520 --> 00:20:27,812 Imam malo ispred sebe. 380 00:20:27,812 --> 00:20:33,560 Ali ulančavanje je u osnovi da svaka kanta u vašem hash tablici 381 00:20:33,560 --> 00:20:36,120 je samo popis povezani. 382 00:20:36,120 --> 00:20:39,660 >> Dakle drugi način, ili više tehničkih način, razmišljati o hash tablicu 383 00:20:39,660 --> 00:20:44,490 je da je to samo niz povezanih popisima, koji 384 00:20:44,490 --> 00:20:49,330 kada pišete svoj rječnik a vi pokušavate učitati, 385 00:20:49,330 --> 00:20:52,070 razmišljam o tome kako je niz povezanih popisa 386 00:20:52,070 --> 00:20:54,390 učinit će to puno lakše za vas pokrenuti. 387 00:20:54,390 --> 00:20:57,680 >> PUBLIKA: Pa hash tablicu ima unaprijed određenu veličinu, 388 00:20:57,680 --> 00:20:58,980 kao [nečujan] iz kante? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Točno. 390 00:20:59,220 --> 00:21:01,655 Tako da ima određeni broj kante koje determine-- 391 00:21:01,655 --> 00:21:03,530 koji ti dečki trebali slobodno igrati. 392 00:21:03,530 --> 00:21:05,269 To može biti prilično cool da vidi što se događa 393 00:21:05,269 --> 00:21:06,810 kao što promijeniti svoj broj kante. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Ali da, to je postaviti broj kante. 396 00:21:11,510 --> 00:21:15,360 Ono što vam omogućuje da stane kao mnogi elementi kao što je potrebno 397 00:21:15,360 --> 00:21:19,350 je to zasebna ulančavanje gdje vas su povezane liste u svakoj ćeliji. 398 00:21:19,350 --> 00:21:22,850 To znači da svoj hash tablicu će biti točno veličine 399 00:21:22,850 --> 00:21:25,440 da to treba biti, zar ne? 400 00:21:25,440 --> 00:21:27,358 To je cijela točka povezanih liste. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Cool. 403 00:21:32,480 --> 00:21:38,780 >> Dakle, svatko ima redu? 404 00:21:38,780 --> 00:21:39,801 U redu. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Što se upravo dogodilo? 407 00:21:41,860 --> 00:21:42,960 Stvarno je sada. 408 00:21:42,960 --> 00:21:45,250 Pogodite netko me ubija. 409 00:21:45,250 --> 00:21:52,060 >> OK ćemo ići u pokušaja, koji su malo ludi. 410 00:21:52,060 --> 00:21:53,140 Volim hash tablice. 411 00:21:53,140 --> 00:21:54,460 Mislim da su stvarno cool. 412 00:21:54,460 --> 00:21:56,710 Pokušava su cool, previše. 413 00:21:56,710 --> 00:21:59,590 >> Tako se bilo tko sjetiti što je probati? 414 00:21:59,590 --> 00:22:01,740 Trebali su otišli preko je kratko predavanje? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Sjećate li se takav kako se to radi? 417 00:22:06,377 --> 00:22:08,460 PUBLIKA: Ja sam samo površno da smo išli preko njega. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: Mi ne idu preko njega. 419 00:22:09,626 --> 00:22:13,100 U redu, mi stvarno ćemo ići preko njega je ono što govoriš. 420 00:22:13,100 --> 00:22:14,860 >> PUBLIKA: To je za dohvat stabla. 421 00:22:14,860 --> 00:22:15,280 >> SPEAKER 1: Da. 422 00:22:15,280 --> 00:22:16,196 To je pronalaženje stablo. 423 00:22:16,196 --> 00:22:16,960 Strašan. 424 00:22:16,960 --> 00:22:23,610 Dakle, jedna stvar za primijetiti je da smo gleda na pojedine likove 425 00:22:23,610 --> 00:22:24,480 ovdje, zar ne? 426 00:22:24,480 --> 00:22:29,710 >> Dakle, prije nego s našim hash funkcije, mi gledali riječi u cjelini, 427 00:22:29,710 --> 00:22:32,270 a sada tražimo više na likove, zar ne? 428 00:22:32,270 --> 00:22:38,380 Dakle, imamo Maxwell ovamo i Mendel. 429 00:22:38,380 --> 00:22:47,840 Tako je u osnovi try-- način razmišljanja je o tome da je svaka razina ovdje 430 00:22:47,840 --> 00:22:49,000 je niz pisama. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Dakle, ovo je vaša root čvor ovdje, zar ne? 433 00:22:55,790 --> 00:23:01,980 To je sve likove abeceda za početak svaku riječ. 434 00:23:01,980 --> 00:23:06,480 >> A ono što želite učiniti je recimo, u redu, imamo neke M riječ. 435 00:23:06,480 --> 00:23:10,590 Idemo tražiti Maxwell, tako idemo na M. i M poena na cijeli 436 00:23:10,590 --> 00:23:14,800 Drugi niz u kojem svaki riječi, dok god postoji 437 00:23:14,800 --> 00:23:17,044 je riječ koja ima kao drugo slovo, 438 00:23:17,044 --> 00:23:19,460 dok god postoji riječ koja ima B kao drugi pismu, 439 00:23:19,460 --> 00:23:24,630 to će imati pokazivač ide na neki sljedeći niz. 440 00:23:24,630 --> 00:23:29,290 >> Tu je vjerojatno nije Riječ koja MP nešto, 441 00:23:29,290 --> 00:23:32,980 pa na P položaju u to polje, to će samo biti NULL. 442 00:23:32,980 --> 00:23:38,840 To će reći, u redu, ne postoji riječ da je M slijedi P, u redu? 443 00:23:38,840 --> 00:23:43,100 Dakle, ako mislimo o tome, svaku jedan od tih manjih stvari 444 00:23:43,100 --> 00:23:47,990 zapravo je jedan od tih velika polja od A do Z. 445 00:23:47,990 --> 00:23:55,064 Dakle, što bi moglo biti jedna od stvari to je vrsta carine probati? 446 00:23:55,064 --> 00:23:56,500 >> PUBLIKA: puno memorije. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: To je tonu memorije, zar ne? 448 00:23:59,940 --> 00:24:08,750 Svaki od tih blokova ovdje predstavlja 26 mjesta, 26 elementa niz. 449 00:24:08,750 --> 00:24:13,680 Tako pokušava dobiti nevjerojatno prostor teška. 450 00:24:13,680 --> 00:24:17,100 >> No, oni su vrlo brzo. 451 00:24:17,100 --> 00:24:22,540 Dakle, nevjerojatno brzo, ali stvarno prostor neučinkovita. 452 00:24:22,540 --> 00:24:24,810 Vrsta moraju shvatiti iz koje želite. 453 00:24:24,810 --> 00:24:29,470 To su stvarno super za vaše pset, ali oni ne zauzimaju puno memorije, 454 00:24:29,470 --> 00:24:30,290 tako da se trgovina off. 455 00:24:30,290 --> 00:24:31,480 Da? 456 00:24:31,480 --> 00:24:34,300 >> PUBLIKA: Bi li bilo moguće postaviti probati, a zatim 457 00:24:34,300 --> 00:24:37,967 nakon što su svi podaci u njemu da need-- 458 00:24:37,967 --> 00:24:39,550 Ne znam je li to bi imalo smisla. 459 00:24:39,550 --> 00:24:42,200 Bio sam uzimajući osloboditi od svega NULL likovi, ali onda 460 00:24:42,200 --> 00:24:42,910 da ne bi bio u stanju indeks them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Još uvijek ih je potrebno. 462 00:24:43,275 --> 00:24:44,854 >> PUBLIKA: - na isti način svaki put. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Da. 464 00:24:45,520 --> 00:24:50,460 Morate se nulta znakove pustiti znaš ako nije riječ tamo. 465 00:24:50,460 --> 00:24:52,040 Ben si imate nešto što želite? 466 00:24:52,040 --> 00:24:52,540 U redu. 467 00:24:52,540 --> 00:24:54,581 U redu, idemo ići malo više 468 00:24:54,581 --> 00:24:58,920 u tehničke detalje iza probati i raditi kroz primjer. 469 00:24:58,920 --> 00:25:01,490 >> U redu, tako da je to ista stvar. 470 00:25:01,490 --> 00:25:06,290 Dok je u popisu povezane, naš glavni vrsta of-- što je riječ želim? - 471 00:25:06,290 --> 00:25:08,350 kao što je izgradnja blok bio čvor. 472 00:25:08,350 --> 00:25:12,280 U pokušaju, imamo i čvor, ali je definirana drugačije. 473 00:25:12,280 --> 00:25:17,000 >> Dakle, imamo neke bool da predstavlja li riječ zapravo 474 00:25:17,000 --> 00:25:23,530 postoji na ovom mjestu, a zatim imamo neku niz here-- odnosno, 475 00:25:23,530 --> 00:25:27,840 ovo je pokazivač Niz od 27 znakova. 476 00:25:27,840 --> 00:25:33,339 A to je za, u ovom slučaju, to 27-- Siguran sam da ste svi kao, čekaj, 477 00:25:33,339 --> 00:25:34,880 ima 26 slova abecede. 478 00:25:34,880 --> 00:25:36,010 Zašto imamo 27? 479 00:25:36,010 --> 00:25:37,870 >> Dakle, ovisno o Način na koji provesti ovo, 480 00:25:37,870 --> 00:25:43,240 To je od pset da dopušteno za apostrofe. 481 00:25:43,240 --> 00:25:46,010 Pa to je zato dodatni jedan. 482 00:25:46,010 --> 00:25:50,500 Također ćete imati u nekim slučajevi null terminator 483 00:25:50,500 --> 00:25:53,230 uključen kao jedan od likovi koji to smiju biti, 484 00:25:53,230 --> 00:25:56,120 a to je kako su provjeriti je li to kraj riječi. 485 00:25:56,120 --> 00:26:01,340 Ako ste zainteresirani, check out Kevin video na study.cs50, 486 00:26:01,340 --> 00:26:04,790 kao i Wikipedia ima neke dobre resurse tamo. 487 00:26:04,790 --> 00:26:09,000 >> Ali ćemo proći samo vrsta kako biste mogli raditi kroz probati 488 00:26:09,000 --> 00:26:11,010 ako si dao jedan. 489 00:26:11,010 --> 00:26:16,230 Dakle, imamo super jednostavan jedan ovdje ima riječi "palicu" i "zoom" u njima. 490 00:26:16,230 --> 00:26:18,920 I kao što vidimo ovdje, ovaj mali prostor ovdje 491 00:26:18,920 --> 00:26:22,560 predstavlja našu bool da kaže, da, ovo je riječ. 492 00:26:22,560 --> 00:26:27,060 A onda ovaj je naš nizovi znakova, zar ne? 493 00:26:27,060 --> 00:26:33,480 >> Tako ćemo proći pronalaženje "šišmiša" u tom pokušaju. 494 00:26:33,480 --> 00:26:38,340 Dakle, početi na vrhu, zar ne? 495 00:26:38,340 --> 00:26:46,290 A mi znamo da je b odgovara Drugi indeks, drugi element 496 00:26:46,290 --> 00:26:47,840 U ovom nizu, jer i b. 497 00:26:47,840 --> 00:26:51,340 Tako otprilike drugi. 498 00:26:51,340 --> 00:26:58,820 >> I to kaže, OK, super, proizlazi da se u Sljedeći niz, jer ako se sjetimo, 499 00:26:58,820 --> 00:27:02,160 to ne znači da je svaki od tih zapravo sadrži element. 500 00:27:02,160 --> 00:27:07,110 Svaki od tih polja sadrži pokazivač, zar ne? 501 00:27:07,110 --> 00:27:10,030 To je važna razlika napraviti. 502 00:27:10,030 --> 00:27:13,450 >> Znam da će ovo be-- pokušava se stvarno je teško dobiti na prvi put, 503 00:27:13,450 --> 00:27:15,241 pa čak i ako je to drugi ili treći put 504 00:27:15,241 --> 00:27:18,370 i to je još uvijek vrsta od činilo teško, 505 00:27:18,370 --> 00:27:21,199 Obećajem, ako idete gledati Ukratko ponovno sutra, 506 00:27:21,199 --> 00:27:22,740 vjerojatno će napraviti puno više smisla. 507 00:27:22,740 --> 00:27:23,890 Potrebno je mnogo da probaviti. 508 00:27:23,890 --> 00:27:27,800 Ja još uvijek ponekad sam kao, čekaj, što je probati? 509 00:27:27,800 --> 00:27:29,080 Kako koristiti ovaj? 510 00:27:29,080 --> 00:27:33,880 >> Tako smo b u ovom slučaju, što je naš drugi indeks. 511 00:27:33,880 --> 00:27:40,240 Ako smo imali, recimo, c ili d ili bilo koji drugi pismo, 512 00:27:40,240 --> 00:27:45,810 moramo mapirati taj leđa indeksa našeg polja da to odgovara. 513 00:27:45,810 --> 00:27:56,930 Dakle, mi bi kao rchar a mi samo oduzmite off to preslikati na 0-25. 514 00:27:56,930 --> 00:27:58,728 Svi su dobri koliko smo mi map naše znakove? 515 00:27:58,728 --> 00:28:00,440 U redu. 516 00:28:00,440 --> 00:28:05,980 >> Dakle, idemo na drugom i mi vidim da, da, to je da ne NULL. 517 00:28:05,980 --> 00:28:07,780 Možemo prijeći na ovom sljedeći niz. 518 00:28:07,780 --> 00:28:12,300 Dakle, idemo na ovom sljedeći niz ovdje. 519 00:28:12,300 --> 00:28:15,500 >> A mi kažemo, OK, sada smo trebate vidjeti ako je ovdje. 520 00:28:15,500 --> 00:28:18,590 Je null ili to radi zapravo krenuti naprijed? 521 00:28:18,590 --> 00:28:21,880 Tako zapravo kreće proslijediti u ovom nizu. 522 00:28:21,880 --> 00:28:24,570 A mi kažemo, u redu, t je naš zadnji pismo. 523 00:28:24,570 --> 00:28:27,580 Dakle, idemo na t na indeksu. 524 00:28:27,580 --> 00:28:30,120 A onda ćemo krenuti naprijed jer ima još jedan. 525 00:28:30,120 --> 00:28:38,340 A to se kaže da je u osnovi, da, ona kaže da je riječ here-- 526 00:28:38,340 --> 00:28:41,750 da ako slijedite ovaj put, došli ste 527 00:28:41,750 --> 00:28:43,210 u riječi, što znamo da je "šišmiša". 528 00:28:43,210 --> 00:28:43,800 Da? 529 00:28:43,800 --> 00:28:46,770 >> PUBLIKA: Je li standardni da se taj kao što je indeks 0, a zatim imaju neku vrstu na 1 530 00:28:46,770 --> 00:28:47,660 ili da su na kraju? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: Ne 532 00:28:48,243 --> 00:28:55,360 Dakle, ako se osvrnemo na našem Deklaracija ovdje, to je bool, 533 00:28:55,360 --> 00:28:59,490 tako da je njezin vlastiti element u vašem čvor. 534 00:28:59,490 --> 00:29:03,331 Dakle, to nije dio polja. 535 00:29:03,331 --> 00:29:03,830 Cool. 536 00:29:03,830 --> 00:29:08,370 Dakle, kada smo završili našu riječ, a mi smo na ovom polju, ono što želite učiniti 537 00:29:08,370 --> 00:29:12,807 je napraviti provjeru je to riječ. 538 00:29:12,807 --> 00:29:14,390 I u ovom slučaju, to će se vratiti da. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Dakle, na toj bilješci, znamo da je "zoološki vrt" - znamo što je ljude da "zoo" je riječ, 541 00:29:24,090 --> 00:29:24,820 zar ne? 542 00:29:24,820 --> 00:29:28,990 Ali se probati ovdje bi kažu, ne, to nije. 543 00:29:28,990 --> 00:29:33,980 I to bi se reći da je zbog toga mi nisu ga označen kao riječ ovdje. 544 00:29:33,980 --> 00:29:40,440 Iako možemo proći do tog niza, 545 00:29:40,440 --> 00:29:43,890 to probati bih da, ne, Zoološki vrt nije u svom rječniku 546 00:29:43,890 --> 00:29:47,070 jer nemamo je označen kao takav. 547 00:29:47,070 --> 00:29:52,870 >> Tako je jedan način da to učinite that-- oh, oprostite, ovo je jedan. 548 00:29:52,870 --> 00:29:59,450 Dakle, u ovom slučaju, "zoološki vrt" nije riječi, ali to je u našem pokušaju. 549 00:29:59,450 --> 00:30:05,690 No, u tom jednom, reci mi to želimo uvedu riječ "kupka", što će se dogoditi 550 00:30:05,690 --> 00:30:08,260 je slijedimo through-- B, A, t. 551 00:30:08,260 --> 00:30:11,820 Mi smo u tom nizu, a idemo tražiti h. 552 00:30:11,820 --> 00:30:15,220 >> U ovom slučaju, kada se pogledajte pokazivača na sat, 553 00:30:15,220 --> 00:30:17,890 to ukazuje na NULL, u redu? 554 00:30:17,890 --> 00:30:20,780 Dakle, osim ako je to izričito ukazujući na drugom polju, 555 00:30:20,780 --> 00:30:25,000 pretpostavimo da su sve upućuje U tom nizu ukazuju na nulu. 556 00:30:25,000 --> 00:30:28,270 Dakle, u ovom slučaju, h se ukazuje na nulu tako da ne možemo ništa učiniti, 557 00:30:28,270 --> 00:30:31,540 tako da bi također vratiti netočno, "kupka" nije ovdje. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Dakle, sada smo zapravo će proći 560 00:30:35,810 --> 00:30:39,790 Kako bismo zapravo reći da je "zoološki vrt" je u našem pokušaju. 561 00:30:39,790 --> 00:30:42,920 Kako umetnuti "zoološki vrt" u našem pokušaju? 562 00:30:42,920 --> 00:30:47,810 Dakle, na isti način na koji smo započeli naš popis povezani, počinjemo u korijenu. 563 00:30:47,810 --> 00:30:50,600 Kada su u nedoumici, započeti u Korijen tih stvari. 564 00:30:50,600 --> 00:30:53,330 >> A mi ćemo reći: OK, z. 565 00:30:53,330 --> 00:30:55,650 z postoji u tome, a on ne. 566 00:30:55,650 --> 00:30:58,370 Tako ste se kreće na Vaš sljedeći niz, u redu? 567 00:30:58,370 --> 00:31:01,482 A onda se na sljedeći, kažemo, u redu, ne o postoji? 568 00:31:01,482 --> 00:31:03,000 To čini. 569 00:31:03,000 --> 00:31:04,330 To opet. 570 00:31:04,330 --> 00:31:08,670 >> I tako dalje naš sljedeći smo rekao, U redu, "zoo" već postoji ovdje. 571 00:31:08,670 --> 00:31:12,440 Sve što trebate učiniti je postavljena jednaka da istina, da je riječ tamo. 572 00:31:12,440 --> 00:31:15,260 Ako ste slijedili sve do prije tog trenutka, 573 00:31:15,260 --> 00:31:17,030 to je riječ, pa samo postavljen je jednaka kao. 574 00:31:17,030 --> 00:31:17,530 Da? 575 00:31:17,530 --> 00:31:22,550 >> PUBLIKA: Tako to radi znači da "ba" je riječ također? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: Ne 577 00:31:24,120 --> 00:31:28,870 Dakle, u ovom slučaju, "ba", dobili bismo ovdje, rekli bismo da je riječ, 578 00:31:28,870 --> 00:31:31,590 i to će i dalje biti. 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 >> PUBLIKA: Dakle, nakon što je to riječ i reći da, onda je to 582 00:31:36,360 --> 00:31:38,380 sadržavat će ići na m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: Pa to ima veze with-- ste učitava to. 584 00:31:42,260 --> 00:31:43,640 Kažete "zoo" je riječ. 585 00:31:43,640 --> 00:31:47,020 Kad idete na check-- kao što su, kažu želiš reći, 586 00:31:47,020 --> 00:31:49,400 ne "zoološki vrt" postoje u ovom rječniku? 587 00:31:49,400 --> 00:31:54,200 Vi ste samo ide tražiti "zoološki vrt" a zatim provjerite da li je riječ. 588 00:31:54,200 --> 00:31:57,291 Nikada nećete premjestiti do m jer to nije 589 00:31:57,291 --> 00:31:58,290 ono što tražite. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Dakle, ako mi zapravo htjeli dodati "kupka" u tom pokušaju, 592 00:32:08,070 --> 00:32:11,390 bismo napraviti istu stvar kao što smo učinili s "zoološki vrt" 593 00:32:11,390 --> 00:32:15,380 osim bismo vidjeti da kad smo pokušati doći do h, to ne postoji. 594 00:32:15,380 --> 00:32:20,090 Dakle, možete misliti kako je to težak dodati novi čvor u popis povezana, 595 00:32:20,090 --> 00:32:27,210 tako da bi trebao dodati još jedan jedan od tih polja, kao što je tako. 596 00:32:27,210 --> 00:32:35,670 I onda ono što radimo je da samo postavite h element ovog niza upućuju na to. 597 00:32:35,670 --> 00:32:39,430 >> I onda ono što bismo htjeli raditi ovdje? 598 00:32:39,430 --> 00:32:43,110 Dodaj to jednako vrijedi jer je riječ. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Cool. 601 00:32:48,150 --> 00:32:48,700 Znam. 602 00:32:48,700 --> 00:32:51,170 Pokušava nisu najuzbudljiviji. 603 00:32:51,170 --> 00:32:54,250 Vjeruj mi, znam. 604 00:32:54,250 --> 00:32:58,040 >> Dakle, jedna stvar je shvatiti s pokušaja, Rekao sam, oni su jako učinkovit. 605 00:32:58,040 --> 00:33:00,080 Tako smo vidjeli zauzimaju tona prostora. 606 00:33:00,080 --> 00:33:01,370 Oni vrsta zbunjujuće. 607 00:33:01,370 --> 00:33:03,367 Pa zašto bi mi ikada koristiti ove? 608 00:33:03,367 --> 00:33:05,450 Mi koristimo to, jer oni su nevjerojatno učinkovit. 609 00:33:05,450 --> 00:33:08,130 >> Dakle, ako ste ikada tražiš do riječi, vi ste samo 610 00:33:08,130 --> 00:33:10,450 Omeđen duljinu riječi. 611 00:33:10,450 --> 00:33:15,210 Dakle, ako ste u potrazi za Riječ koja je dužine pet, 612 00:33:15,210 --> 00:33:20,940 ti si samo ikada morati bi najviše pet usporedbe, u redu? 613 00:33:20,940 --> 00:33:25,780 Dakle, čini to u osnovi konstantna. 614 00:33:25,780 --> 00:33:29,150 Poput umetanja i pretraživanja su u osnovi vremenska konstanta. 615 00:33:29,150 --> 00:33:33,750 >> Dakle, ako ste ikada može dobiti nešto u stalnom vremenu, 616 00:33:33,750 --> 00:33:35,150 to je kao dobar kao Internet dobiva. 617 00:33:35,150 --> 00:33:37,990 Ne može bolje od konstanta vrijeme za takve stvari. 618 00:33:37,990 --> 00:33:43,150 Tako da je jedan od ogromne pluseve od pokušaja. 619 00:33:43,150 --> 00:33:46,780 >> Ali, to je puno prostora. 620 00:33:46,780 --> 00:33:50,380 Dakle, vrsta morati odlučiti ono što je važnije za vas. 621 00:33:50,380 --> 00:33:54,700 A na današnjim računalima, Prostor koji pokušaj može potrajati 622 00:33:54,700 --> 00:33:57,740 Možda ne utječe ste toliko, ali možda 623 00:33:57,740 --> 00:34:01,350 imate posla s nečim koji je daleko, daleko više stvari, 624 00:34:01,350 --> 00:34:02,810 i pokušati jednostavno nije razumno. 625 00:34:02,810 --> 00:34:03,000 Da? 626 00:34:03,000 --> 00:34:05,610 >> PUBLIKA: Čekaj, pa imate 26 slova u svakog pojedinca? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Da, imate 26. 629 00:34:08,570 --> 00:34:16,984 Imate neki je riječ marker i onda imate 26 upućuje na svakoga. 630 00:34:16,984 --> 00:34:17,775 I oni point-- 631 00:34:17,775 --> 00:34:20,280 >> PUBLIKA: I svaki 26, oni svaki ima 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Da. 633 00:34:21,500 --> 00:34:27,460 I zato, kao što možete vidi, ona širi vrlo brzo. 634 00:34:27,460 --> 00:34:28,130 U redu. 635 00:34:28,130 --> 00:34:32,524 Tako ćemo dobiti u stabala, koja Osjećam se sviđa je lakše i vjerojatno će 636 00:34:32,524 --> 00:34:36,150 biti lijepi mali predah od pokušaja tamo. 637 00:34:36,150 --> 00:34:39,620 Dakle, nadam se većina vas Vidio stablo prije. 638 00:34:39,620 --> 00:34:41,820 Ne sviđa lijepa one izvan, koje sam 639 00:34:41,820 --> 00:34:44,340 Ne znam je li itko otišao je nedavno otvorenom. 640 00:34:44,340 --> 00:34:49,230 Otišao sam u berbu jabuka, ovaj vikend, i oh moj Bože, bilo je lijepo. 641 00:34:49,230 --> 00:34:52,250 Nisam znao lišće moglo izgledati da je lijepa. 642 00:34:52,250 --> 00:34:53,610 >> Dakle, ovo je samo stablo, zar ne? 643 00:34:53,610 --> 00:34:56,790 To je samo neki čvor, i to ukazuje na hrpu drugih čvorova. 644 00:34:56,790 --> 00:34:59,570 Kao što vidite ovdje, ovo je vrsta ponavljajućih temu. 645 00:34:59,570 --> 00:35:03,720 Čvorovi ukazuje na čvorove je vrsta suština mnogih struktura podataka. 646 00:35:03,720 --> 00:35:06,670 To samo ovisi o tome kako ćemo ih upućuju jedni drugima 647 00:35:06,670 --> 00:35:08,600 i kako smo prošli kroz njih i kako smo 648 00:35:08,600 --> 00:35:14,500 umetati stvari koje određuje njihove različite karakteristike. 649 00:35:14,500 --> 00:35:17,600 >> Dakle, samo su neki terminologiju, što sam se prije. 650 00:35:17,600 --> 00:35:20,010 Dakle, korijen je ono što je na samom vrhu. 651 00:35:20,010 --> 00:35:21,200 To je mjesto gdje smo uvijek početi. 652 00:35:21,200 --> 00:35:23,610 Možete misliti o njemu kao glavi također. 653 00:35:23,610 --> 00:35:28,750 Ali za drveće, skloni smo odnosi se na to što je u korijenu. 654 00:35:28,750 --> 00:35:32,820 >> Sve u donjem here-- na vrlo, vrlo bottom-- 655 00:35:32,820 --> 00:35:34,500 smatraju lišće. 656 00:35:34,500 --> 00:35:37,210 Tako to ide zajedno s cijela stabla stvar, zar ne? 657 00:35:37,210 --> 00:35:39,860 Listovi su na rubu svog stabla. 658 00:35:39,860 --> 00:35:45,820 >> A onda imamo i nekoliko Uvjeti za razgovor o čvorova u odnosu 659 00:35:45,820 --> 00:35:46,680 međusobno. 660 00:35:46,680 --> 00:35:49,700 Tako imamo roditelja, djeca, braća i sestre. 661 00:35:49,700 --> 00:35:56,260 Dakle, u ovom slučaju, 3 roditelj 5, 6 i 7. 662 00:35:56,260 --> 00:36:00,370 Dakle, roditelj je ono što je jedan korak naprijed što god da ste 663 00:36:00,370 --> 00:36:02,940 pozivajući se, pa samo poput obiteljskog stabla. 664 00:36:02,940 --> 00:36:07,090 Nadajmo se, to je sve pomalo malo više intuitivno nego pokušaja. 665 00:36:07,090 --> 00:36:10,970 >> Braća i sestre su bilo koje imaju Isto roditelj, zar ne? 666 00:36:10,970 --> 00:36:13,470 Oni su na istoj razini ovdje. 667 00:36:13,470 --> 00:36:16,960 A onda, kao što sam bio govoreći, djeca su samo 668 00:36:16,960 --> 00:36:22,630 sve što je jedan korak u nastavku čvor u pitanju, u redu? 669 00:36:22,630 --> 00:36:23,470 Cool. 670 00:36:23,470 --> 00:36:25,610 Dakle, binarno stablo. 671 00:36:25,610 --> 00:36:31,450 Može li itko nasumice pogađati na jednom od karakteristike binarnom stablu? 672 00:36:31,450 --> 00:36:32,770 >> PUBLIKA: Max dva lista. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Točno. 674 00:36:33,478 --> 00:36:34,640 Dakle, max dva lista. 675 00:36:34,640 --> 00:36:39,730 Tako je u ovom jednom prije, imali smo tu jednu koji je imao tri, ali u binarnom stablu, 676 00:36:39,730 --> 00:36:45,000 imate max dva Djeca po roditelja, zar ne? 677 00:36:45,000 --> 00:36:46,970 Postoji još jedan Zanimljivo obilježje. 678 00:36:46,970 --> 00:36:51,550 Zna li netko to? 679 00:36:51,550 --> 00:36:52,620 Binarno stablo. 680 00:36:52,620 --> 00:37:00,350 >> Dakle, binarno stablo će imati sve na the-- ovo nije sorted-- 681 00:37:00,350 --> 00:37:05,320 ali u sortirane binarnom stablu, sve na desnoj strani 682 00:37:05,320 --> 00:37:08,530 veća od roditelja, i sve na lijevoj 683 00:37:08,530 --> 00:37:10,035 manja od roditelja. 684 00:37:10,035 --> 00:37:15,690 I to je bio kviz Pitanje prije, pa je dobro znati. 685 00:37:15,690 --> 00:37:19,500 Dakle, način na koji smo definirali to, opet, imamo još jedan čvor. 686 00:37:19,500 --> 00:37:21,880 To izgleda vrlo slično kao što? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Dvostruko 689 00:37:28,836 --> 00:37:29,320 >> PUBLIKA: Povezani popisi 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: Popis dvostruka povezani, zar ne? 691 00:37:31,100 --> 00:37:33,690 Dakle, ako bismo zamijenili ovo uz prethodni i sljedeći, 692 00:37:33,690 --> 00:37:35,670 to će biti popis dvostruko povezani. 693 00:37:35,670 --> 00:37:40,125 No, u ovom slučaju, mi zapravo ima lijevo i desno i to je to. 694 00:37:40,125 --> 00:37:41,500 Inače, to je točno isto. 695 00:37:41,500 --> 00:37:43,374 Mi još uvijek imamo element tražiš, 696 00:37:43,374 --> 00:37:45,988 a vi samo dvije upućuje ide na sve što je sljedeće. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Da, tako binarno pretraživanje stablo. 699 00:37:51,870 --> 00:37:57,665 Ako primijetite, sve na ovdje je veći than-- 700 00:37:57,665 --> 00:37:59,850 ili je sve odmah da upravo ovdje 701 00:37:59,850 --> 00:38:02,840 je veći od svega, Ovdje je manje od. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Dakle, ako smo bili na pretraživanje ga, trebao izgledati vrlo blizu binarnom pretraživanje 704 00:38:14,000 --> 00:38:14,910 ovdje, zar ne? 705 00:38:14,910 --> 00:38:17,640 Osim umjesto da gleda na pola polja, 706 00:38:17,640 --> 00:38:21,720 samo mi se gleda na bilo lijevo strana ili desna strana stabla. 707 00:38:21,720 --> 00:38:24,850 Tako se dobiva malo jednostavnije, mislim. 708 00:38:24,850 --> 00:38:29,300 >> Dakle, ako je vaš korijen je NULL, Očito je to samo lažna. 709 00:38:29,300 --> 00:38:33,470 A ako je tamo, očito je to istina. 710 00:38:33,470 --> 00:38:35,320 Ako je manje od, tražimo lijevu. 711 00:38:35,320 --> 00:38:37,070 Ako je veći od, tražimo pravo. 712 00:38:37,070 --> 00:38:39,890 To je točno kao binarni pretraživanje, Samo različite strukture podataka 713 00:38:39,890 --> 00:38:40,600 da smo putem. 714 00:38:40,600 --> 00:38:42,790 Umjesto niza, to je samo binarno stablo. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> U redu, gomila. 717 00:38:48,090 --> 00:38:51,550 I također, to izgleda kao mi možda ima malo vremena. 718 00:38:51,550 --> 00:38:54,460 Ako to učinimo, ja sam sretna da ide više bilo to opet. 719 00:38:54,460 --> 00:38:56,856 U redu, tako da gomila. 720 00:38:56,856 --> 00:39:02,695 Se bilo tko sjetiti što stacks-- sve karakteristike stog? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> U redu, tako da većina nas, mislim, jesti u blagovaonicu halls-- 723 00:39:10,400 --> 00:39:13,100 koliko smo možda željeli. 724 00:39:13,100 --> 00:39:16,900 No, očito, možete misliti na stog doslovno samo kao hrpu pladnjeva 725 00:39:16,900 --> 00:39:18,460 ili snop stvari. 726 00:39:18,460 --> 00:39:21,820 I ono što je važno shvatiti je da je 727 00:39:21,820 --> 00:39:26,850 something-- karakteristika da ga zovu by-- je LIFO. 728 00:39:26,850 --> 00:39:28,450 Zna li netko što to znači? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> PUBLIKA: posljednji u, prvi van. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: Pravo, trajati u, prvi van. 732 00:39:32,250 --> 00:39:36,585 Dakle, ako znamo, ako smo slaganje stvari gore, najjednostavnija stvar da zgrabite off-- 733 00:39:36,585 --> 00:39:39,570 a možda i jedino što možemo zgrabiti isključiti ako naš stog je velika enough-- 734 00:39:39,570 --> 00:39:40,850 je da je vrh elementa. 735 00:39:40,850 --> 00:39:43,460 Dakle, sve što je stavljen na last-- kao što vidimo ovdje, 736 00:39:43,460 --> 00:39:46,370 god je gurnula na većini recently-- je 737 00:39:46,370 --> 00:39:51,160 će biti prvi Ono što mi pući, u redu? 738 00:39:51,160 --> 00:39:56,324 >> Dakle, ono što imamo ovdje još jedna typedef struct. 739 00:39:56,324 --> 00:39:58,740 Ovo je stvarno baš kao pad tečaja u strukturi podataka, 740 00:39:58,740 --> 00:40:01,650 tako da je puno bačena na vas dečki. 741 00:40:01,650 --> 00:40:02,540 Znam. 742 00:40:02,540 --> 00:40:04,970 Dakle, još jedan struct. 743 00:40:04,970 --> 00:40:06,740 Jupi za strukture. 744 00:40:06,740 --> 00:40:16,660 >> I u ovom slučaju, to je neki pointer na niz koji ima neki kapacitet. 745 00:40:16,660 --> 00:40:20,830 Dakle, to predstavlja našu stog Ovdje, kao i našeg stvarnog niz 746 00:40:20,830 --> 00:40:22,520 koja drži naše elemente. 747 00:40:22,520 --> 00:40:24,850 A onda ovdje imamo neku veličinu. 748 00:40:24,850 --> 00:40:31,170 >> I obično, želite zadržati trag koliko je velik vaš stog 749 00:40:31,170 --> 00:40:36,180 jer ono što se događa kako bi se omogućilo što trebate učiniti je, ako znate veličina, 750 00:40:36,180 --> 00:40:39,170 to vam reći, OK, ja sam u svojstvu? 751 00:40:39,170 --> 00:40:40,570 Mogu li dodati nešto više? 752 00:40:40,570 --> 00:40:44,650 I to također govori gdje je vrh stacka 753 00:40:44,650 --> 00:40:48,180 tako da znate što vas zapravo može poletjeti. 754 00:40:48,180 --> 00:40:51,760 I to je zapravo ide biti malo više jasno ovdje. 755 00:40:51,760 --> 00:40:57,350 >> Tako je za guranje, jedna stvar, ako vas ikada provesti gurati, 756 00:40:57,350 --> 00:41:01,330 kao što sam rekao, vaš stog ima ograničenu veličinu, zar ne? 757 00:41:01,330 --> 00:41:03,990 Naš niz je neki kapacitet. 758 00:41:03,990 --> 00:41:04,910 To je niz. 759 00:41:04,910 --> 00:41:08,930 To je fiksna veličina, tako da ćemo morati pobrinite se da nećemo više stavljajući 760 00:41:08,930 --> 00:41:11,950 u naš niz od nas zapravo imaju prostor za. 761 00:41:11,950 --> 00:41:16,900 >> Dakle, kada ste stvaranje gurati funkcija, prva stvar koju trebate učiniti je recimo, u redu, 762 00:41:16,900 --> 00:41:18,570 imam prostor u mom stog? 763 00:41:18,570 --> 00:41:23,330 Jer ako ne, ispričavam se, Ne mogu spremiti svoj element. 764 00:41:23,330 --> 00:41:28,980 Ako radim, onda želite pohraniti je na vrhu dimnjaka, zar ne? 765 00:41:28,980 --> 00:41:31,325 >> I to je razlog zašto smo pratiti naše veličine. 766 00:41:31,325 --> 00:41:35,290 Ako ne pratiti naše veličine, ne znamo gdje da ga stavi. 767 00:41:35,290 --> 00:41:39,035 Mi ne znamo kako mnoge stvari su već naše ponude. 768 00:41:39,035 --> 00:41:41,410 Kao i očito postoje načini da možda bi mogao to učiniti. 769 00:41:41,410 --> 00:41:44,610 Ti bi mogao inicijalizirati sve na nulu a zatim provjeriti najnovije NULL, 770 00:41:44,610 --> 00:41:47,950 ali mnogo lakše stvar je samo reći, OK, pratiti veličine. 771 00:41:47,950 --> 00:41:51,840 Kao što ja znam imam četiri elementa u mom nizu, tako da sljedeća stvar 772 00:41:51,840 --> 00:41:55,930 koje smo stavili na, mi smo namjeravate pohraniti na indeks 4. 773 00:41:55,930 --> 00:42:00,940 I onda, naravno, to znači da je ste uspješno gura nešto 774 00:42:00,940 --> 00:42:03,320 na čipova, što žele povećati veličinu 775 00:42:03,320 --> 00:42:08,880 tako da znate gdje ste tako da možete gurnuti više stvari dalje. 776 00:42:08,880 --> 00:42:12,730 >> Dakle, ako mi pokušavamo pop nešto izvan dimnjaka, 777 00:42:12,730 --> 00:42:16,072 što bi moglo biti prva stvar da želimo provjeriti? 778 00:42:16,072 --> 00:42:18,030 Pokušavaš uzeti nešto izvan čipova. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Jeste li sigurni da postoji nešto u vašem stog? 781 00:42:24,781 --> 00:42:25,280 Ne. 782 00:42:25,280 --> 00:42:26,894 Pa što bi moglo želimo provjeriti? 783 00:42:26,894 --> 00:42:27,810 >> PUBLIKA: [nečujan]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Provjerite veličinu? 785 00:42:29,880 --> 00:42:31,840 Veličina. 786 00:42:31,840 --> 00:42:38,520 Dakle, želimo provjeriti da li naša veličina je veća od 0, u redu? 787 00:42:38,520 --> 00:42:44,970 A ako je, onda želimo smanjiti naša veličina za 0 i povratak to. 788 00:42:44,970 --> 00:42:45,840 Zašto? 789 00:42:45,840 --> 00:42:49,950 >> U prvoj smo guranje, gurnuo mi 790 00:42:49,950 --> 00:42:52,460 na veličinu i zatim obnovljeno veličini. 791 00:42:52,460 --> 00:42:57,850 U ovom slučaju, mi smo se smanjuje veličinu a zatim ga polijetanje, to čupanja 792 00:42:57,850 --> 00:42:58,952 iz naše ponude. 793 00:42:58,952 --> 00:42:59,826 Zašto bismo mogli to učiniti? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Dakle, ako ja imam jednu stvar na mom stog, što bi bilo moje veličine u tom trenutku? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> A gdje je element 1 pohranjene? 798 00:43:15,180 --> 00:43:17,621 U ono indeks? 799 00:43:17,621 --> 00:43:18,120 PUBLIKA: 0. 800 00:43:18,120 --> 00:43:19,060 SPEAKER 1: 0. 801 00:43:19,060 --> 00:43:22,800 Dakle, u ovom slučaju, mi Uvijek trebate napraviti sure-- 802 00:43:22,800 --> 00:43:27,630 umjesto povratka Veličina minus 1, jer mi 803 00:43:27,630 --> 00:43:31,730 znamo da je naš element će se čuva na 1 manje 804 00:43:31,730 --> 00:43:34,705 bez obzira na naša veličina, to samo se brine o njoj. 805 00:43:34,705 --> 00:43:36,080 To je nešto više elegantan način. 806 00:43:36,080 --> 00:43:41,220 A mi samo umanjuje našu stranicu Veličina, a zatim se vratiti veličinu. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> PUBLIKA: Valjda samo u cjelini, zašto bi ova struktura podataka 809 00:43:45,300 --> 00:43:47,800 biti koristan? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: To ovisi o vašem kontekstu. 811 00:43:50,660 --> 00:43:57,420 Tako da za neke teorije, ako radite with-- redu, 812 00:43:57,420 --> 00:44:02,750 daj da vidim postoji li jedan koristan koji je koristan za više od vani 813 00:44:02,750 --> 00:44:05,420 CS. 814 00:44:05,420 --> 00:44:15,780 S dimnjaka, u bilo koje vrijeme vam je potrebno pratiti nešto što 815 00:44:15,780 --> 00:44:20,456 je nedavno dodao je kada idete da želite koristiti hrpu. 816 00:44:20,456 --> 00:44:24,770 >> A ja ne mogu misliti na dobro Primjer za to upravo sada. 817 00:44:24,770 --> 00:44:29,955 No, kad god najnovije što je najvažnije za vas, 818 00:44:29,955 --> 00:44:31,705 to je kad snop će biti korisna. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Pokušavam da ako postoji dobar za to. 821 00:44:39,330 --> 00:44:43,720 Ako mislim dobar primjer u sljedećoj 20 minuta, ja definitivno će vam reći. 822 00:44:43,720 --> 00:44:49,455 >> No sve u svemu, ako postoji nešto, kao što sam rekao većina, gdje je najnovija 823 00:44:49,455 --> 00:44:52,470 je najvažnije, da je gdje je snop dolazi u igru. 824 00:44:52,470 --> 00:44:58,860 Dok redovima su vrsta suprotno. 825 00:44:58,860 --> 00:44:59,870 I svi su mali psi. 826 00:44:59,870 --> 00:45:00,890 Nije li to sjajno, zar ne? 827 00:45:00,890 --> 00:45:03,299 Osjećam se kao da sam trebao samo imaju zeko videozapis 828 00:45:03,299 --> 00:45:05,090 desno u sredini dio za vas dečki 829 00:45:05,090 --> 00:45:08,870 jer ovo je intenzivna poglavlje. 830 00:45:08,870 --> 00:45:10,480 >> Dakle, red. 831 00:45:10,480 --> 00:45:12,710 Uglavnom red je poput linije. 832 00:45:12,710 --> 00:45:15,780 Vi Siguran sam da upotreba ove svakodnevice, baš kao u našim blagovaona dvoranama. 833 00:45:15,780 --> 00:45:18,160 Dakle, moramo ići u i dobiti naše ladice, ja sam 834 00:45:18,160 --> 00:45:21,260 sigurni morate čekati u redu ukrasti ili dobiti hranu. 835 00:45:21,260 --> 00:45:24,650 >> Dakle, razlika ovdje je da je to FIFO. 836 00:45:24,650 --> 00:45:30,090 Dakle, ako LIFO bio posljednji u prvom out, FIFO je prvi u, prvi van. 837 00:45:30,090 --> 00:45:33,400 Dakle, ovo je mjesto gdje god ste stavili na prvom je najvažniji. 838 00:45:33,400 --> 00:45:35,540 Dakle, ako ste bili na čekanju u line-- može vas 839 00:45:35,540 --> 00:45:39,130 zamislite da ste otišli u ići dobiti novi iPhone 840 00:45:39,130 --> 00:45:42,800 i to je bio dimnjak, gdje Posljednja osoba u skladu je dobio prvi, 841 00:45:42,800 --> 00:45:44,160 ljudi bi se međusobno ubijaju. 842 00:45:44,160 --> 00:45:49,800 >> Dakle FIFO, svi smo dobro upoznati sa u stvarnom svijetu ovdje, 843 00:45:49,800 --> 00:45:54,930 i sve to ima veze s zapravo vrsta ponovno cijelu ovu liniju 844 00:45:54,930 --> 00:45:56,900 i čekanjem strukturu. 845 00:45:56,900 --> 00:46:02,390 Dakle, dok je s stog, moramo gurati i pop. 846 00:46:02,390 --> 00:46:06,440 Uz red, imamo Postavi u red i dequeue. 847 00:46:06,440 --> 00:46:10,910 Tako u red osnovi znači stavio ga na leđa, 848 00:46:10,910 --> 00:46:13,680 i dequeue sredstva potrajati off sprijeda. 849 00:46:13,680 --> 00:46:18,680 Tako je naša struktura podataka malo više komplicirano. 850 00:46:18,680 --> 00:46:21,060 Imamo drugu stvar za praćenje. 851 00:46:21,060 --> 00:46:25,950 >> Dakle, bez glave, to Upravo stog, zar ne? 852 00:46:25,950 --> 00:46:27,900 To je ista struktura kao stog. 853 00:46:27,900 --> 00:46:32,480 Jedino što sada drugačije je što ima tu glavu, što što mislite 854 00:46:32,480 --> 00:46:34,272 će pratiti? 855 00:46:34,272 --> 00:46:35,510 >> PUBLIKA: Prvi. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Pravo, Prva stvar koju smo stavili u. 857 00:46:38,685 --> 00:46:41,130 Glava našeg red. 858 00:46:41,130 --> 00:46:42,240 Tko je prvi u redu. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 U redu, pa ako radimo u red. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Opet, s bilo kojim od ove strukture podataka, 863 00:46:55,920 --> 00:46:59,760 jer smo koja se bavi nizom, moramo provjeriti da li imamo prostora. 864 00:46:59,760 --> 00:47:03,290 >> To je vrsta kao što mi govori ti dečki, ako otvorite datoteku, 865 00:47:03,290 --> 00:47:04,760 trebate provjeriti null. 866 00:47:04,760 --> 00:47:08,330 Uz bilo koji od tih dimnjaka a redovi, trebate 867 00:47:08,330 --> 00:47:13,420 da li postoji prostor jer smo bavi fiksnom veličine polja, 868 00:47:13,420 --> 00:47:16,030 kao što smo vidjeli here-- 0, 1 sve do 5. 869 00:47:16,030 --> 00:47:20,690 Dakle, što nam je činiti u tom slučaju je provjera da li još uvijek imamo prostora. 870 00:47:20,690 --> 00:47:23,110 Je li naša veličina manje od kapaciteta? 871 00:47:23,110 --> 00:47:28,480 >> Ako je tako, moramo ga pohraniti u rep i ažuriramo našu veličinu. 872 00:47:28,480 --> 00:47:30,250 Dakle, što bi rep se u ovom slučaju? 873 00:47:30,250 --> 00:47:32,360 To nije izrijekom napisano van. 874 00:47:32,360 --> 00:47:33,380 Kako bismo to pohraniti? 875 00:47:33,380 --> 00:47:34,928 Što će biti rep? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Tako ćemo prošetati kroz ovaj primjer. 878 00:47:40,190 --> 00:47:44,590 Dakle, ovo je niz veličine 6, zar ne? 879 00:47:44,590 --> 00:47:49,220 I mi smo upravo sada, naša veličina je 5. 880 00:47:49,220 --> 00:47:55,240 A kad smo ga stavili u, to se događa ići u peti indeksa, zar ne? 881 00:47:55,240 --> 00:47:57,030 Dakle pohraniti na repu. 882 00:47:57,030 --> 00:48:05,600 >> Drugi način napisati rep bi samo biti naš polje na indeksu veličini, zar ne? 883 00:48:05,600 --> 00:48:07,560 To je veličina 5. 884 00:48:07,560 --> 00:48:11,490 Sljedeća stvar će ići u 5. 885 00:48:11,490 --> 00:48:12,296 Cool? 886 00:48:12,296 --> 00:48:13,290 U redu. 887 00:48:13,290 --> 00:48:16,350 Ona dobiva nešto složeniji kada počnemo petljaju s glave. 888 00:48:16,350 --> 00:48:17,060 Da? 889 00:48:17,060 --> 00:48:20,090 >> PUBLIKA: Znači li to da smo bi proglasio niz koji 890 00:48:20,090 --> 00:48:23,880 Bio pet elemenata dug i onda mi dodajemo na njega? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: Ne 892 00:48:24,730 --> 00:48:27,560 Dakle, u ovom slučaju, to je dimnjak. 893 00:48:27,560 --> 00:48:31,760 To će biti proglašen kao niz veličine 6. 894 00:48:31,760 --> 00:48:37,120 I u ovom slučaju, mi samo jedno mjesto ulijevo. 895 00:48:37,120 --> 00:48:42,720 >> U redu, tako da jedna stvar je u tome slučaj, ako je naša glava je na 0, 896 00:48:42,720 --> 00:48:45,270 onda mi samo možemo ga dodati na veličinu. 897 00:48:45,270 --> 00:48:51,020 Ali to dobiva malo trickier jer zapravo, oni 898 00:48:51,020 --> 00:48:52,840 nemaju slajd za to, pa ću 899 00:48:52,840 --> 00:48:56,670 nacrtati jedan, jer to nije vrlo je jednostavno jednom vas 900 00:48:56,670 --> 00:48:59,230 početi uzimajući osloboditi od stvari. 901 00:48:59,230 --> 00:49:03,920 Dakle, dok je s hrpom imate samo ikada 902 00:49:03,920 --> 00:49:08,920 brinuti o tome što je veličina kada dodajete nešto na, 903 00:49:08,920 --> 00:49:15,710 uz red također je potrebno napraviti sigurni da je vaša glava činili, 904 00:49:15,710 --> 00:49:20,760 jer je super stvar o redovima je da ako niste na kapacitet, 905 00:49:20,760 --> 00:49:23,040 što zapravo može učiniti zaokrenuti. 906 00:49:23,040 --> 00:49:28,810 >> U redu, tako da jednu stvar oh, ovo je strašno krede. 907 00:49:28,810 --> 00:49:31,815 Jedna stvar koju treba uzeti u obzir je slučaj. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Samo ćemo napraviti pet. 910 00:49:37,140 --> 00:49:41,810 U redu, tako da ćemo kažu glava ovdje. 911 00:49:41,810 --> 00:49:46,140 To je 0, 1, 2, 3, 4, 912 00:49:46,140 --> 00:49:54,210 >> Glava je tamo, i molimo se stvari u njima. 913 00:49:54,210 --> 00:49:58,340 I želimo dodati nešto, zar ne? 914 00:49:58,340 --> 00:50:01,170 Dakle, ono što trebamo znam je da je glava uvijek 915 00:50:01,170 --> 00:50:05,620 će se premjestiti na taj način i onda povratna petlja oko, u redu? 916 00:50:05,620 --> 00:50:10,190 >> Tako je ovaj red ima mjesta, zar ne? 917 00:50:10,190 --> 00:50:13,950 To je prostor u samom početku, vrsta suprotno od toga. 918 00:50:13,950 --> 00:50:17,920 Dakle, ono što trebamo učiniti je da potrebno je izračunati rep. 919 00:50:17,920 --> 00:50:20,530 Ako znate da je vaš Glava nije preselio, rep 920 00:50:20,530 --> 00:50:24,630 je samo tvoj niz, na Indeks veličine. 921 00:50:24,630 --> 00:50:30,000 >> No, u stvarnosti, ako koristite red, glavu vjerojatno se ažurira. 922 00:50:30,000 --> 00:50:33,890 Dakle, ono što trebate učiniti je zapravo izračunati rep. 923 00:50:33,890 --> 00:50:39,990 Dakle, ono što mi radimo je ova formula ovdje, što ću vas pustiti 924 00:50:39,990 --> 00:50:42,680 Dečki razmišljaju o, i onda ćemo razgovarati o tome. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Dakle, to je kapacitet. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Dakle, to će zapravo vam dati način da to učinite. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Budući da u ovom slučaju, što? 931 00:51:04,330 --> 00:51:09,205 Naša glava je na 1, naša veličina je 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Ako mod koji je za 5, dobivamo 0, što je gdje smo trebali ga unijeti. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Pa onda u sljedećem slučaju, ako smo to učinili, 936 00:51:26,080 --> 00:51:33,390 kažemo, u redu, neka je dequeue nešto. 937 00:51:33,390 --> 00:51:34,390 Mi dequeue to. 938 00:51:34,390 --> 00:51:37,740 Mi se ovaj element, zar ne? 939 00:51:37,740 --> 00:51:47,930 >> A sada naša glava pokazuje ovdje, i želimo dodati još jedna stvar. 940 00:51:47,930 --> 00:51:52,470 To je u osnovi natrag na našu liniju, zar ne? 941 00:51:52,470 --> 00:51:55,450 Redovi može omotati oko polja. 942 00:51:55,450 --> 00:51:57,310 To je jedan od glavnih razlika. 943 00:51:57,310 --> 00:51:58,780 Hrpe, ne možete to učiniti. 944 00:51:58,780 --> 00:52:01,140 >> Uz redova, možete jer sve što je bitno 945 00:52:01,140 --> 00:52:03,940 je da znate što je nedavno dodao je. 946 00:52:03,940 --> 00:52:10,650 Budući da sve ide kako treba dodati u to lijevi smjer, u ovom slučaju, 947 00:52:10,650 --> 00:52:16,480 a zatim zaokrenuti, možete nastavljaju stavljanjem u novim elementima 948 00:52:16,480 --> 00:52:18,830 na prednjem dijelu polja jer to zapravo nije 949 00:52:18,830 --> 00:52:20,640 Prednji dio niza više. 950 00:52:20,640 --> 00:52:26,320 Možete misliti na početak Niz kao gdje ti je glava zapravo jest. 951 00:52:26,320 --> 00:52:29,710 >> Dakle, ova formula je kako je izračunati svoj rep. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Da li to smisla? 954 00:52:35,610 --> 00:52:36,110 U redu. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 U redu, dequeue, a zatim vi imate 10 minuta 957 00:52:44,040 --> 00:52:48,840 mi postavljati pitanja razjasnili želite, jer znam da je lud. 958 00:52:48,840 --> 00:52:51,980 >> U redu, tako da u istom way-- Ja ne znam je li vi primijetili, 959 00:52:51,980 --> 00:52:53,450 ali CS je sve o obrascima. 960 00:52:53,450 --> 00:52:57,370 Stvari su prilično mnogo Isto, samo sa sitnim ugađanje. 961 00:52:57,370 --> 00:52:58,950 Dakle, ista stvar ovdje. 962 00:52:58,950 --> 00:53:04,040 Moramo provjeriti da li smo zapravo ima nešto u našem redu, zar ne? 963 00:53:04,040 --> 00:53:05,960 Recimo, u redu, naš je veličina veća od 0? 964 00:53:05,960 --> 00:53:06,730 Cool. 965 00:53:06,730 --> 00:53:10,690 >> Ako to učinimo, onda ćemo premjestiti naše glave, što je ono što sam upravo ovdje pokazao. 966 00:53:10,690 --> 00:53:13,870 Mi ažurirati svoju glavu da se još jedan. 967 00:53:13,870 --> 00:53:18,390 I onda mi umanjuje naše Veličina i vratiti element. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Tu je puno konkretniji kod na study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 i ja visoko preporučiti ide kroz nju, ako imate vremena, 971 00:53:29,440 --> 00:53:30,980 čak i ako je samo pseudo-koda. 972 00:53:30,980 --> 00:53:35,980 A ako vi želite razgovarati putem da je sa mnom jedan na jedan, javite mi 973 00:53:35,980 --> 00:53:37,500 znate. 974 00:53:37,500 --> 00:53:38,770 Bio bih sretan da. 975 00:53:38,770 --> 00:53:42,720 Strukture podataka, ukoliko uzmete CS 124, vi ćete 976 00:53:42,720 --> 00:53:47,830 znam da strukture podataka dobiti vrlo zabavna i to je tek početak. 977 00:53:47,830 --> 00:53:50,350 >> Tako da znam da je teško. 978 00:53:50,350 --> 00:53:51,300 To je u redu. 979 00:53:51,300 --> 00:53:52,410 Mi se bore. 980 00:53:52,410 --> 00:53:53,630 I danas je tako. 981 00:53:53,630 --> 00:53:56,660 Dakle, ne brinite previše o tome. 982 00:53:56,660 --> 00:54:02,390 >> Ali to je u osnovi vaš pad tečaja u strukturama podataka. 983 00:54:02,390 --> 00:54:03,400 Znam da je to puno. 984 00:54:03,400 --> 00:54:06,860 Postoji li nešto što bismo željeli ići ispočetka? 985 00:54:06,860 --> 00:54:09,400 Sve što želimo razgovarati putem? 986 00:54:09,400 --> 00:54:10,060 Da? 987 00:54:10,060 --> 00:54:16,525 >> PUBLIKA: Na tom primjeru, tako Novi rep je na 0 nad tim? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Da. 989 00:54:17,150 --> 00:54:18,230 PUBLIKA: U redu. 990 00:54:18,230 --> 00:54:24,220 Pa onda prolazi kroz, ne bi se 1 plus 4 or-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Znači li rekli, kada želimo ići to učiniti opet? 992 00:54:27,671 --> 00:54:28,296 PUBLIKA: Da. 993 00:54:28,296 --> 00:54:38,290 Dakle, ako ste bili figuring out-- gdje su što izračuna rep s time što? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Pa rep Bio in-- sam to mijenja. 995 00:54:44,260 --> 00:54:52,010 Dakle, u ovom primjeru ovdje, ovo je bio Niz gledamo, u redu? 996 00:54:52,010 --> 00:54:54,670 Dakle, imamo stvari u 1, 2, 3 i 4. 997 00:54:54,670 --> 00:55:05,850 Dakle, mi imamo glava jednaka 1 na ovom trenutku, a naša veličina je jednaka 4 998 00:55:05,850 --> 00:55:07,050 u ovom trenutku, zar ne? 999 00:55:07,050 --> 00:55:08,960 >> Vi svi se slažu da je to slučaj? 1000 00:55:08,960 --> 00:55:14,620 Dakle, radimo na glavu plus veličine, što daje nam 5, a onda smo mod za 5. 1001 00:55:14,620 --> 00:55:20,690 Mi smo dobili 0, što nam govori da je 0 Gdje je naš rep, gdje imamo prostora. 1002 00:55:20,690 --> 00:55:22,010 >> PUBLIKA: Koja je kapa? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: kapacitet. 1004 00:55:23,520 --> 00:55:24,020 Oprostite. 1005 00:55:24,020 --> 00:55:29,640 Tako da je veličina vašeg polja. 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 >> PUBLIKA: [nečujan] prije vraćamo element? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Tako se krećemo glavu ili vratiti trenutak? 1010 00:55:46,270 --> 00:55:52,680 Dakle, ako se krećemo jedan, umanjuje veličinu? 1011 00:55:52,680 --> 00:55:54,150 Držite se. 1012 00:55:54,150 --> 00:55:55,770 Ja definitivno zaboravio drugu. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Nema veze. 1015 00:56:01,990 --> 00:56:04,980 Ne postoji jedna formula. 1016 00:56:04,980 --> 00:56:09,980 Da, ti bi htio da se vrate glavu, a zatim ga premjestiti natrag. 1017 00:56:09,980 --> 00:56:13,270 >> PUBLIKA: OK, jer se na taj točka, glava je bila na 0, 1018 00:56:13,270 --> 00:56:18,452 a zatim se želite vratiti indeks 0, a zatim bi glavu 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Točno. 1020 00:56:19,870 --> 00:56:22,820 Mislim da postoji još jedan Formula vrsta kao što je ovaj. 1021 00:56:22,820 --> 00:56:26,970 Ja ga nemate na vrhu moje glave kao Ne želim da vam krivi jedan. 1022 00:56:26,970 --> 00:56:35,470 Ali mislim da je savršeno valjana za recimo, u redu, spremite ovaj element-- god 1023 00:56:35,470 --> 00:56:40,759 Glava je element koji is-- opadanje svoje veličinu, premjestiti glavu iznad i povratak 1024 00:56:40,759 --> 00:56:41,800 što god to element. 1025 00:56:41,800 --> 00:56:44,760 To je savršeno valjana. 1026 00:56:44,760 --> 00:56:45,260 U redu. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Osjećam se kao da to nije kao most-- niste 1029 00:56:53,560 --> 00:56:55,740 će izaći odavde kao, da, znam pokušaja. 1030 00:56:55,740 --> 00:56:56,880 Sam dobio sve. 1031 00:56:56,880 --> 00:56:57,670 To je u redu. 1032 00:56:57,670 --> 00:57:00,200 Obećavam. 1033 00:57:00,200 --> 00:57:05,240 No, strukture podataka su nešto što je potrebno puno vremena da se navikne. 1034 00:57:05,240 --> 00:57:10,010 Vjerojatno jedan od najtežih stvari, mislim, u tijeku. 1035 00:57:10,010 --> 00:57:15,330 >> Dakle, to je definitivno potrebno ponavljanje i gleda at-- I 1036 00:57:15,330 --> 00:57:20,050 zapravo nije znao povezane liste dok sam previše s njima, 1037 00:57:20,050 --> 00:57:22,550 na isti način na koji nisam stvarno shvatiti upućuje 1038 00:57:22,550 --> 00:57:27,040 dok sam ga morao učiti za dvoje godine i to moje vlastite psets s njim. 1039 00:57:27,040 --> 00:57:28,990 Potrebno je puno vremena i ponavljanja. 1040 00:57:28,990 --> 00:57:32,600 I na kraju, to će vrsta kliknuti. 1041 00:57:32,600 --> 00:57:36,320 >> No, u međuvremenu, ako imate kakav od razumijevanja visokoj razini onoga 1042 00:57:36,320 --> 00:57:39,321 to učiniti, njihovi pro cons-- i što je što 1043 00:57:39,321 --> 00:57:41,820 mi stvarno imaju tendenciju naglasiti, posebno u intro tijeku. 1044 00:57:41,820 --> 00:57:45,511 Kao, zašto bi mi koristimo probati preko niza? 1045 00:57:45,511 --> 00:57:48,010 Kao što su pozitivci i negativa svake od njih? 1046 00:57:48,010 --> 00:57:51,610 >> I razumijevanje ustupke između svakog od ovih konstrukcija 1047 00:57:51,610 --> 00:57:54,910 je ono što je puno važnije upravo sada. 1048 00:57:54,910 --> 00:57:58,140 Tu može biti jedan ludi Pitanje ili dva koji je 1049 00:57:58,140 --> 00:58:03,710 će vas pitati za provedbu gurati ili provedbu pop ili u red i dequeue. 1050 00:58:03,710 --> 00:58:07,340 No, za najveći dio, da ima viša razina razumijevanja i više 1051 00:58:07,340 --> 00:58:09,710 više intuitivno razumijevanje je važniji nego zapravo 1052 00:58:09,710 --> 00:58:11,250 biti u mogućnosti da ga provede. 1053 00:58:11,250 --> 00:58:14,880 >> Bilo bi stvarno super ako sve vas mogao izaći i otići provesti probati, 1054 00:58:14,880 --> 00:58:19,720 ali razumijemo to nije nužno većina razumnih stvar upravo sada. 1055 00:58:19,720 --> 00:58:23,370 No, možete u svom pset, ako želite da, i onda ćete dobiti praksu, 1056 00:58:23,370 --> 00:58:27,200 a onda možda ćete stvarno ga razumijem. 1057 00:58:27,200 --> 00:58:27,940 Da? 1058 00:58:27,940 --> 00:58:30,440 >> PUBLIKA: U redu, tako da one koje su što znači da se koristi u pset? 1059 00:58:30,440 --> 00:58:31,916 Trebam li koristiti jedan od njih? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Da. 1061 00:58:32,540 --> 00:58:34,199 Dakle, imate svoj izbor. 1062 00:58:34,199 --> 00:58:36,740 Mislim da u ovom slučaju, možemo govoriti o pset malo 1063 00:58:36,740 --> 00:58:40,480 jer sam prošao kroz to. 1064 00:58:40,480 --> 00:58:47,779 Tako je u svom pset, imate svoj Izbor pokušaja ili hash tablice. 1065 00:58:47,779 --> 00:58:49,570 Neki ljudi će pokušati i koristiti cvatu filtere, 1066 00:58:49,570 --> 00:58:51,840 ali oni tehnički nisu točne. 1067 00:58:51,840 --> 00:58:55,804 Zbog njihove probabilističkoj prirode, daju neistinit ponekad. 1068 00:58:55,804 --> 00:58:57,095 Oni su super pogled u, iako. 1069 00:58:57,095 --> 00:58:59,030 Preporučujemo potrazi na njih najmanje. 1070 00:58:59,030 --> 00:59:03,260 No, imate izbor između hash stol i probati. 1071 00:59:03,260 --> 00:59:06,660 I to će biti tamo gdje ulažete u svom rječniku. 1072 00:59:06,660 --> 00:59:09,230 >> A vi ćete morati odabrati Vaš hash funkcija, 1073 00:59:09,230 --> 00:59:13,420 morate odabrati koliko kante imate, a to će se razlikovati. 1074 00:59:13,420 --> 00:59:17,440 Kao i ako imate više kante, možda će se izvoditi brže. 1075 00:59:17,440 --> 00:59:22,790 No, možda ste gubit puno prostora na taj način, iako. 1076 00:59:22,790 --> 00:59:26,320 Morate to shvatiti. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> PUBLIKA: Rekli ste prije toga možemo koristiti i druge hash funkcije, 1079 00:59:29,875 --> 00:59:31,750 da mi ne moramo stvoriti hash funkciju? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Da, u pravu. 1081 00:59:32,666 --> 00:59:38,150 Dakle, doslovno za svoj hash funkcije, kao što je google "hash funkcija" 1082 00:59:38,150 --> 00:59:40,770 i tražiti neke cool one. 1083 00:59:40,770 --> 00:59:43,250 Ne očekuje se graditi vlastiti hash funkcije. 1084 00:59:43,250 --> 00:59:46,100 Ljudi troše svoje Teze o tim stvarima. 1085 00:59:46,100 --> 00:59:50,250 >> Dakle, ne brinite o izgradnji vlastite. 1086 00:59:50,250 --> 00:59:53,350 Pronađite jedan online za početak. 1087 00:59:53,350 --> 00:59:56,120 Neki od njih morate manipuliraju malo 1088 00:59:56,120 --> 00:59:59,430 kako bi bili sigurni tipovi povratak podudaraju i sitnica, pa je u početku, 1089 00:59:59,430 --> 01:00:02,420 Ja bih preporučio nešto pomoću stvarno lako da možda jednostavno 1090 01:00:02,420 --> 01:00:04,680 hashes na prvom pismu. 1091 01:00:04,680 --> 01:00:08,760 I onda nakon što su taj rad, sjedinjavanje hladnije funkciju hash. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> PUBLIKA: Biste pokušati biti ili učinkovita, ali samo teže, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Pa pokušaj, mislim, intuitivno je teško provesti 1095 01:00:15,880 --> 01:00:18,310 ali je vrlo brzo. 1096 01:00:18,310 --> 01:00:20,620 Međutim, zauzima više prostora. 1097 01:00:20,620 --> 01:00:25,270 Opet, možete optimizirati i onih u različite načine i postoje načini to-- 1098 01:00:25,270 --> 01:00:26,770 PUBLIKA: Kako smo polaže na to? 1099 01:00:26,770 --> 01:00:27,540 Da li to matter-- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Znači ocjenjuju normalan način. 1101 01:00:29,164 --> 01:00:31,330 Ti ćeš se polaže na dizajn. 1102 01:00:31,330 --> 01:00:36,020 Koji god način radite, želite uvjerite se da je kao elegantan kao što može biti 1103 01:00:36,020 --> 01:00:38,610 te kao učinkovito kao što može biti. 1104 01:00:38,610 --> 01:00:41,950 Ali, ako se odlučite probati ili mljeveno meso stol, dok to radi, 1105 01:00:41,950 --> 01:00:45,350 smo sretni s tim. 1106 01:00:45,350 --> 01:00:48,370 A ako koristite nešto što hashes na prvom pismu, to je u redu, 1107 01:00:48,370 --> 01:00:51,410 kao što možda kao dizajn-mudar. 1108 01:00:51,410 --> 01:00:53,410 Mi smo također dosežu točka u ovom semester-- 1109 01:00:53,410 --> 01:00:55,340 Ja ne znam je li vama Dečki noticed-- ako ste 1110 01:00:55,340 --> 01:00:58,780 pset razreda odbiti malo zbog dizajna i sitnica, 1111 01:00:58,780 --> 01:00:59,900 to je savršeno u redu. 1112 01:00:59,900 --> 01:01:02,960 To je sve do točke u kojoj je vaš Programi su sve složeniji. 1113 01:01:02,960 --> 01:01:04,830 Postoji više mjesta možete poboljšati. 1114 01:01:04,830 --> 01:01:06,370 >> Tako da je sasvim normalno. 1115 01:01:06,370 --> 01:01:08,810 To ne znači da ste radiš gore na vašem pset. 1116 01:01:08,810 --> 01:01:11,885 To je jednostavno smo se teže na vas sada. 1117 01:01:11,885 --> 01:01:13,732 Dakle, svatko je to osjećaj. 1118 01:01:13,732 --> 01:01:14,940 Upravo sam polaže sve svoje psets. 1119 01:01:14,940 --> 01:01:16,490 Znam da svi to osjećaj. 1120 01:01:16,490 --> 01:01:19,600 >> Zato nemojte biti zabrinuti zbog toga. 1121 01:01:19,600 --> 01:01:23,580 A ako imate bilo kakvih pitanja o prethodna psets ili načina na koje možete poboljšati, 1122 01:01:23,580 --> 01:01:27,760 Pokušavam i komentirati specifične mjestima, ali ponekad je kasno 1123 01:01:27,760 --> 01:01:30,840 i ja dobiti umorna. 1124 01:01:30,840 --> 01:01:34,885 Ima li kakvih drugih stvari oko strukture podataka? 1125 01:01:34,885 --> 01:01:37,510 Siguran sam da ti dečki stvarno ne želim govoriti o njima više, 1126 01:01:37,510 --> 01:01:42,650 ali ako postoje, ja sam sretan ide preko njih, kao i sve 1127 01:01:42,650 --> 01:01:45,580 od predavanja ovu prošlom tjedan ili prošli tjedan. 1128 01:01:45,580 --> 01:01:51,580 >> Znam prošli tjedan je sve pregled, tako da možda smo preskočili neke pregled 1129 01:01:51,580 --> 01:01:54,190 od predavanja. 1130 01:01:54,190 --> 01:01:58,230 Ima li još pitanja mogu odgovoriti? 1131 01:01:58,230 --> 01:01:59,350 U redu, u redu. 1132 01:01:59,350 --> 01:02:02,400 Pa, ti dečki izaći 15 minuta ranije. 1133 01:02:02,400 --> 01:02:08,370 >> Nadam se da je to bio polu-korisno barem, i ja ću vas vidjeti dečki sljedeći tjedan, 1134 01:02:08,370 --> 01:02:12,150 ili četvrtak radno vrijeme. 1135 01:02:12,150 --> 01:02:15,285 Postoje zahtjevi za grickalice za sljedeći tjedan, to je stvar? 1136 01:02:15,285 --> 01:02:17,459 Budući da sam zaboravio slatkiše danas. 1137 01:02:17,459 --> 01:02:19,750 I ja sam donio slatkiše posljednju tjedan, ali to je Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 tako da su bili poput šest ljudi koji imao četiri vreće slatkiša za sebe. 1139 01:02:25,400 --> 01:02:28,820 Ja mogu donijeti zvjezdana prašina opet, ako vam se sviđa. 1140 01:02:28,820 --> 01:02:29,580 Zvjezdana prašina? 1141 01:02:29,580 --> 01:02:32,250 OK, zvuči dobro. 1142 01:02:32,250 --> 01:02:35,050 Imati veliki dan, momci. 1143 01:02:35,050 --> 01:02:39,510