1 00:00:00,000 --> 00:00:08,250 2 00:00:08,250 --> 00:00:12,680 >> JASON Hirschhorna: Dobrodošli svima Odsjek Seven. 3 00:00:12,680 --> 00:00:15,040 Mi smo u tjedan dana sedam tečaja. 4 00:00:15,040 --> 00:00:18,440 I ovaj nadolazeći četvrtak je noć vještica, tako sam ja 5 00:00:18,440 --> 00:00:21,420 odjeveni poput bundeve. 6 00:00:21,420 --> 00:00:23,460 Nisam mogla naginjati i staviti na moje cipele, pa je to razlog zašto sam 7 00:00:23,460 --> 00:00:25,660 Samo nosio čarape. 8 00:00:25,660 --> 00:00:29,220 Ja također ne nosim ništa u to, pa ne mogu ga skinuti ako je to 9 00:00:29,220 --> 00:00:29,950 odvlače pažnju na vas. 10 00:00:29,950 --> 00:00:31,860 Unaprijed se ispričavam zbog toga. 11 00:00:31,860 --> 00:00:33,170 Vi ne morate zamisliti što se događa. 12 00:00:33,170 --> 00:00:34,240 Ja sam nosio bokserice. 13 00:00:34,240 --> 00:00:36,170 Tako da je sve dobro. 14 00:00:36,170 --> 00:00:41,120 >> Imam dužu priču o tome zašto sam odjeven kao bundeve, ali ja ću se 15 00:00:41,120 --> 00:00:45,110 osim što se za kasnije u ovom poglavlju jer ja ne želim da biste započeli. 16 00:00:45,110 --> 00:00:47,720 Imamo puno uzbudljivih stvari ići preko ovog tjedna. 17 00:00:47,720 --> 00:00:51,810 Većina njih se odnose izravno na ovo tjedan Problem set, pravopisne pogreške. 18 00:00:51,810 --> 00:00:54,680 Mi ćemo se ide preko povezani popisi i hash tablice 19 00:00:54,680 --> 00:00:57,160 tijekom cijelog dijela. 20 00:00:57,160 --> 00:01:02,490 Stavio sam taj popis svaki tjedan, popis Sredstva za vas da vam pomoći s 21 00:01:02,490 --> 00:01:04,120 Materijal na ovoj stazi. 22 00:01:04,120 --> 00:01:07,600 Ako na gubitku ili ako u potrazi za neke više informacija, provjeriti jedan od 23 00:01:07,600 --> 00:01:09,930 ovi resursi. 24 00:01:09,930 --> 00:01:14,530 >> Opet, pset6 je pravopisne pogreške, ovotjedni pset. 25 00:01:14,530 --> 00:01:17,690 I ona također potiče, a ja potaknuti vas, da koriste neki drugi 26 00:01:17,690 --> 00:01:20,320 sredstva posebno za ovu pset. 27 00:01:20,320 --> 00:01:23,390 Konkretno, tri sam navedena na zaslonu - 28 00:01:23,390 --> 00:01:27,160 gdb, što smo bili upoznati s i bio koristeći za neko vrijeme sada, je 29 00:01:27,160 --> 00:01:29,270 će biti vrlo korisna ovaj tjedan. 30 00:01:29,270 --> 00:01:30,190 Zato sam stavio da je ovdje. 31 00:01:30,190 --> 00:01:32,910 No, kad god radite s C, trebali biste uvijek koristiti gdb se 32 00:01:32,910 --> 00:01:34,430 debug svoje programe. 33 00:01:34,430 --> 00:01:36,660 Ovaj tjedan također Valgrind. 34 00:01:36,660 --> 00:01:38,535 Zna li itko što Valgrind radi? 35 00:01:38,535 --> 00:01:42,184 36 00:01:42,184 --> 00:01:43,890 >> PUBLIKA: Ona provjerava curenje memorije? 37 00:01:43,890 --> 00:01:45,950 >> JASON Hirschhorna: Valgrind provjerava curenje memorije. 38 00:01:45,950 --> 00:01:49,970 Dakle, ako ste malloc nešto u Program, pitate za pamćenje. 39 00:01:49,970 --> 00:01:52,920 Na kraju svog programa, imate pisati slobodno o svemu što ste 40 00:01:52,920 --> 00:01:54,800 malloced dati pamćenje. 41 00:01:54,800 --> 00:01:58,420 Ako ne pisati besplatno na kraju i Vaš program dolazi do zaključka, 42 00:01:58,420 --> 00:02:00,000 sve će automatski biti oslobođen. 43 00:02:00,000 --> 00:02:02,340 I za male programe, to je nije neka velika stvar. 44 00:02:02,340 --> 00:02:05,250 Ali, ako ste pisanje duže trčanje program koji ne prekida, 45 00:02:05,250 --> 00:02:09,180 nu, u roku od par minuta ili A nekoliko sekundi, a zatim curenje memorije 46 00:02:09,180 --> 00:02:10,710 može postati ogroman posao. 47 00:02:10,710 --> 00:02:14,940 >> Tako je za pset6, očekuje se da ćete imati nula curenje memorije s 48 00:02:14,940 --> 00:02:15,910 vaš program. 49 00:02:15,910 --> 00:02:18,690 Za provjeru curenja memorije, pokrenuti Valgrind i to će vam dati neke lijepe 50 00:02:18,690 --> 00:02:21,190 Izlaz ostavljajući znate li ili ne sve je bilo besplatno. 51 00:02:21,190 --> 00:02:23,940 Mi ćemo vježbati s njim kasnije danas, nadam se. 52 00:02:23,940 --> 00:02:25,790 >> Konačno, razl naredbe. 53 00:02:25,790 --> 00:02:28,900 Nekada si nešto slično tome u pset5 s zavirite alat. 54 00:02:28,900 --> 00:02:30,780 Dopustio da izgledaju iznutra. 55 00:02:30,780 --> 00:02:33,400 Također se koristi diff, također, po Problem postaviti spec.. 56 00:02:33,400 --> 00:02:35,950 No, u koju dopušteno usporediti dvije datoteke. 57 00:02:35,950 --> 00:02:39,180 Ti bi mogao usporediti bitmap datoteku i info zaglavlja rješenje osoblja i 58 00:02:39,180 --> 00:02:42,200 Vaše rješenje u pset5 ako ste odabrali da ih koriste. 59 00:02:42,200 --> 00:02:44,030 Diff će vam omogućiti da to, kao što je dobro. 60 00:02:44,030 --> 00:02:48,620 Možete usporediti točan odgovor za Problem ovotjedni postavljen na vašem odgovoru 61 00:02:48,620 --> 00:02:52,210 i vidjeti ako to vodovima ili vidjeti gdje su pogreške. 62 00:02:52,210 --> 00:02:55,870 >> Dakle, to su tri dobre alati koji te bi trebao koristiti za ovaj tjedan, a 63 00:02:55,870 --> 00:02:58,130 svakako provjerite svoj program s ova tri alata 64 00:02:58,130 --> 00:03:00,520 prije okreće u. 65 00:03:00,520 --> 00:03:04,650 Opet, kao što sam spomenuo svaki tjedan, Ako imate bilo kakve povratne informacije za mene - i 66 00:03:04,650 --> 00:03:06,470 pozitivna i konstruktivna - 67 00:03:06,470 --> 00:03:09,930 slobodno glavu na web stranici na dnu ovog klizača 68 00:03:09,930 --> 00:03:11,270 a ulaz je tamo. 69 00:03:11,270 --> 00:03:13,440 Ja stvarno poštovati bilo i sve povratne informacije. 70 00:03:13,440 --> 00:03:17,360 A ako mi dati konkretne stvari koje Ja mogu učiniti za poboljšanje ili da sam 71 00:03:17,360 --> 00:03:21,350 dobro da bi me voljeli i dalje, ja to uzeti k srcu i 72 00:03:21,350 --> 00:03:24,040 jako truditi da slušaju na Vašoj poruci. 73 00:03:24,040 --> 00:03:27,720 Ne mogu obećati da ću učiniti sve, iako, kao što je nosio 74 00:03:27,720 --> 00:03:30,700 bundeva kostim svaki tjedan. 75 00:03:30,700 --> 00:03:34,020 >> Tako ćemo provesti najveći dio sekcija, kao što sam spomenuo, govori o 76 00:03:34,020 --> 00:03:37,240 povezane liste i hash tablice, koje će se izravno odnosi se na 77 00:03:37,240 --> 00:03:38,780 Problem postaviti ovaj tjedan. 78 00:03:38,780 --> 00:03:42,580 Povezane liste ćemo ići preko relativno brzo, jer smo proveli sajam zalogaj 79 00:03:42,580 --> 00:03:44,930 vrijeme ide preko njega u sekciji. 80 00:03:44,930 --> 00:03:48,680 I tako ćemo dobiti ravno u kodiranje probleme vezane za popise. 81 00:03:48,680 --> 00:03:52,740 I onda na kraju ćemo govoriti o Tablice i kako se oni odnose na to 82 00:03:52,740 --> 00:03:55,280 tjedan Problem postaviti. 83 00:03:55,280 --> 00:03:57,560 >> Vidjeli ste ovaj kod prije. 84 00:03:57,560 --> 00:04:02,730 To je rekonstruirati, a definiranje nešto novo zove čvor. 85 00:04:02,730 --> 00:04:10,660 A unutar čvorova je cijeli broj upravo ovdje i tamo je kazaljka na 86 00:04:10,660 --> 00:04:11,830 još jedan čvor. 87 00:04:11,830 --> 00:04:12,790 Vidjeli smo to i prije. 88 00:04:12,790 --> 00:04:14,830 To je dolazi za nekoliko tjedana sada. 89 00:04:14,830 --> 00:04:18,680 Ona kombinira goniča, koji smo bili rad s, i tvorevina, koje omogućuju 90 00:04:18,680 --> 00:04:22,079 us kombinirati dva različita stvari u jednu vrstu podataka. 91 00:04:22,079 --> 00:04:24,830 92 00:04:24,830 --> 00:04:26,490 >> Postoji mnogo događa na zaslonu. 93 00:04:26,490 --> 00:04:30,220 No, sve to treba biti relativno upoznati s vama. 94 00:04:30,220 --> 00:04:33,810 Na prvoj liniji, proglasi novi čvor. 95 00:04:33,810 --> 00:04:41,650 I onda u taj novi čvor, postavim broj u tom čvoru na jedan. 96 00:04:41,650 --> 00:04:44,950 Vidimo se na sljedećem retku radim printf naredbe, ali sam zasjenjene 97 00:04:44,950 --> 00:04:48,080 printf naredbe, jer stvarno Važan dio je ova linija ovdje - 98 00:04:48,080 --> 00:04:50,020 new_node.n. 99 00:04:50,020 --> 00:04:51,270 Što dot znači? 100 00:04:51,270 --> 00:04:53,810 101 00:04:53,810 --> 00:04:57,240 >> PUBLIKA: Idi na čvoru i procijeniti n vrijednost za njega. 102 00:04:57,240 --> 00:04:58,370 >> JASON Hirschhorna: To je točno u pravu. 103 00:04:58,370 --> 00:05:03,300 Dot znači pristupiti N Part ovog novog čvora. 104 00:05:03,300 --> 00:05:05,690 Ovaj sljedeći linija što radi? 105 00:05:05,690 --> 00:05:16,140 106 00:05:16,140 --> 00:05:17,050 Michael. 107 00:05:17,050 --> 00:05:21,910 >> Ivanković: To stvara još jedan čvor koji će ukazati na novi čvor. 108 00:05:21,910 --> 00:05:24,870 >> JASON Hirschhorna: Tako se to ne dogodi stvoriti novi čvor. 109 00:05:24,870 --> 00:05:26,120 On stvara što? 110 00:05:26,120 --> 00:05:28,300 111 00:05:28,300 --> 00:05:29,300 >> PUBLIKA: pointer. 112 00:05:29,300 --> 00:05:33,460 >> JASON Hirschhorna: pokazivač na čvor, kao što je navedeno od strane ove čvor * ovdje. 113 00:05:33,460 --> 00:05:34,800 Tako se stvara pokazivač na čvor. 114 00:05:34,800 --> 00:05:37,490 A koji čvor je to upućuju da, Michael? 115 00:05:37,490 --> 00:05:38,440 >> PUBLIKA: Novi čvor? 116 00:05:38,440 --> 00:05:39,240 >> JASON Hirschhorna: Novi čvor. 117 00:05:39,240 --> 00:05:43,020 I to pokazuje postoji jer smo dao mu adresu novog čvora. 118 00:05:43,020 --> 00:05:45,820 I sada, u ovom retku vidimo dva različita načina 119 00:05:45,820 --> 00:05:46,910 izražava istu stvar. 120 00:05:46,910 --> 00:05:49,650 I ja sam htjela istaknuti kako se oni Dvije stvari su isti. 121 00:05:49,650 --> 00:05:54,740 U prvoj liniji, mi dereference pointer. 122 00:05:54,740 --> 00:05:55,830 Dakle, idemo na čvoru. 123 00:05:55,830 --> 00:05:56,830 To znači da je ova zvijezda. 124 00:05:56,830 --> 00:05:57,930 Vidjeli smo da je prije nego što s pokazivača. 125 00:05:57,930 --> 00:05:59,280 Idi na tom čvoru. 126 00:05:59,280 --> 00:06:00,370 To je u zagradama. 127 00:06:00,370 --> 00:06:04,610 A onda pristupiti putem operatera dot n element tog čvora. 128 00:06:04,610 --> 00:06:08,430 >> Tako da je uzimanje sintaksu vidjeli smo ovdje i sada 129 00:06:08,430 --> 00:06:09,670 uporabe s pokazivačem. 130 00:06:09,670 --> 00:06:13,730 Naravno, ona dobiva u gužvi, ako pišeš one zagrade - 131 00:06:13,730 --> 00:06:14,940 da je star i da točka. 132 00:06:14,940 --> 00:06:16,220 Ona dobiva malo zauzet. 133 00:06:16,220 --> 00:06:18,500 Dakle, imamo neke sintaktičkc šećer. 134 00:06:18,500 --> 00:06:19,920 I ova linija upravo ovdje - 135 00:06:19,920 --> 00:06:21,170 ptr_node-> n. 136 00:06:21,170 --> 00:06:25,400 137 00:06:25,400 --> 00:06:28,000 To se isto točno stvar. 138 00:06:28,000 --> 00:06:30,840 Dakle, te dvije linije koda su ekvivalent i da će učiniti 139 00:06:30,840 --> 00:06:31,650 točno istu stvar. 140 00:06:31,650 --> 00:06:34,210 >> Ali htio sam ukazati onima prije idemo dalje, tako da razumijem 141 00:06:34,210 --> 00:06:39,000 da stvarno ova stvar ovdje je samo sintaktička šećer za dereferencing 142 00:06:39,000 --> 00:06:44,200 pokazivač, a zatim će se n dio tog Struct. 143 00:06:44,200 --> 00:06:45,525 Bilo kakva pitanja o ovom slajdu? 144 00:06:45,525 --> 00:06:53,020 145 00:06:53,020 --> 00:06:54,390 OK. 146 00:06:54,390 --> 00:06:58,510 >> Tako ćemo proći kroz nekoliko operacija koje možete raditi na 147 00:06:58,510 --> 00:06:59,730 povezane liste. 148 00:06:59,730 --> 00:07:05,770 Popis povezani, podsjetimo, je serija čvorovi koji ukazuju na jednu drugu. 149 00:07:05,770 --> 00:07:12,470 I mi općenito početi s pokazivačem zove glava, općenito, koji ukazuje na 150 00:07:12,470 --> 00:07:14,040 Prva stvar na popisu. 151 00:07:14,040 --> 00:07:18,900 Dakle, na prvoj liniji ovdje, mi imamo originalnu L prva. 152 00:07:18,900 --> 00:07:21,370 Tako da je stvar koju mogu zamisliti - to tekst ovdje možete misliti kako je 153 00:07:21,370 --> 00:07:23,560 Samo pointer smo pohranjeni negdje da bodovi 154 00:07:23,560 --> 00:07:24,670 na prvi element. 155 00:07:24,670 --> 00:07:27,500 I u ovom popisu povezanom imamo četiri čvorišta. 156 00:07:27,500 --> 00:07:29,530 Svaki čvor je velika kutija. 157 00:07:29,530 --> 00:07:33,430 Veći okvir unutar velike Kutija je cijeli dio. 158 00:07:33,430 --> 00:07:37,400 I onda imamo pokazivač dio. 159 00:07:37,400 --> 00:07:39,630 >> Ti okviri nisu izvučeni mjerilo jer koliko je velik 160 00:07:39,630 --> 00:07:42,320 cijeli broj u bajtovima? 161 00:07:42,320 --> 00:07:43,290 Koliko je velik sada? 162 00:07:43,290 --> 00:07:43,710 Četiri. 163 00:07:43,710 --> 00:07:45,470 A koliko je velika je kazaljka? 164 00:07:45,470 --> 00:07:45,940 Četiri. 165 00:07:45,940 --> 00:07:48,180 Pa stvarno, ako smo izvući to na ljestvici oba polja 166 00:07:48,180 --> 00:07:49,690 će biti iste veličine. 167 00:07:49,690 --> 00:07:52,870 U ovom slučaju, želimo umetnuti nešto u popis povezane. 168 00:07:52,870 --> 00:07:57,190 Tako možete vidjeti ovdje smo umetanja pet smo prošli kroz 169 00:07:57,190 --> 00:08:01,310 povezani popis, naći gdje je pet ide, a zatim ga umetnite. 170 00:08:01,310 --> 00:08:03,560 >> Idemo razbiti tu dolje i ići malo sporije. 171 00:08:03,560 --> 00:08:05,510 Idem ukazati na brodu. 172 00:08:05,510 --> 00:08:09,930 Dakle, mi imamo čvor pet koje koje smo stvorili u mallocs. 173 00:08:09,930 --> 00:08:11,190 Zašto se svi smijali? 174 00:08:11,190 --> 00:08:12,130 Šalim se. 175 00:08:12,130 --> 00:08:13,310 OK. 176 00:08:13,310 --> 00:08:14,820 Tako smo malloced pet. 177 00:08:14,820 --> 00:08:16,310 Napravili smo ovaj čvor negdje drugdje. 178 00:08:16,310 --> 00:08:17,740 Moramo ga spremni ići. 179 00:08:17,740 --> 00:08:20,130 Krećemo na prednjoj naš popis s dva. 180 00:08:20,130 --> 00:08:22,380 I želimo umetnuti u sortiraju modi. 181 00:08:22,380 --> 00:08:27,550 >> Dakle, ako vidimo dva i želimo staviti u pet godina, što nam je činiti kada smo vidjeli 182 00:08:27,550 --> 00:08:28,800 nešto manje od nas? 183 00:08:28,800 --> 00:08:31,850 184 00:08:31,850 --> 00:08:33,520 Što? 185 00:08:33,520 --> 00:08:36,750 Mi želimo umetnuti pet u ovo povezani popis, imajući to riješeno. 186 00:08:36,750 --> 00:08:37,520 Vidimo broj dva. 187 00:08:37,520 --> 00:08:38,769 Dakle, što nam je činiti? 188 00:08:38,769 --> 00:08:39,179 Marcus? 189 00:08:39,179 --> 00:08:40,679 >> PUBLIKA: Poziv pokazivač na sljedeći čvor. 190 00:08:40,679 --> 00:08:42,530 >> JASON Hirschhorna: A zašto ne idemo na sljedeći? 191 00:08:42,530 --> 00:08:45,970 >> PUBLIKA: Zato što je to Sljedeći čvor na popisu. 192 00:08:45,970 --> 00:08:48,310 A mi samo znamo da je drugo mjesto. 193 00:08:48,310 --> 00:08:50,410 >> JASON Hirschhorna: A pet je veća nego dvije, posebice. 194 00:08:50,410 --> 00:08:51,600 Zato želimo ga zadržati sortirani. 195 00:08:51,600 --> 00:08:52,730 Do pet je veća od dva. 196 00:08:52,730 --> 00:08:54,460 Tako smo prešli na sljedeći. 197 00:08:54,460 --> 00:08:55,240 I sada dolazimo do četiri. 198 00:08:55,240 --> 00:08:56,490 A što se događa kada dođemo do četiri? 199 00:08:56,490 --> 00:08:58,920 200 00:08:58,920 --> 00:09:00,310 >> Pet je veći od četiri. 201 00:09:00,310 --> 00:09:01,460 Tako smo zadržati ide. 202 00:09:01,460 --> 00:09:03,110 I sad smo na šest. 203 00:09:03,110 --> 00:09:04,360 A što mi vidimo u šest? 204 00:09:04,360 --> 00:09:08,672 205 00:09:08,672 --> 00:09:09,608 Da, Carlos? 206 00:09:09,608 --> 00:09:10,544 >> PUBLIKA: Šest je veći od pet. 207 00:09:10,544 --> 00:09:11,480 >> JASON Hirschhorna: Šest je veći od pet. 208 00:09:11,480 --> 00:09:13,660 Dakle, to je mjesto gdje želimo umetnuti pet. 209 00:09:13,660 --> 00:09:17,320 Ipak, imajte na umu da, ako smo samo jedan pokazivač ovdje - 210 00:09:17,320 --> 00:09:19,840 ovo je naš dodatni pokazivač da je poprijeko kroz popis. 211 00:09:19,840 --> 00:09:21,860 I mi smo ukazujući na šest. 212 00:09:21,860 --> 00:09:25,010 Mi smo zaboravili za što dolazi prije šest godina. 213 00:09:25,010 --> 00:09:29,130 Dakle, ako želimo umetnuti nešto u ovaj popis imajući to riješeno, što 214 00:09:29,130 --> 00:09:31,630 Vjerojatno je potrebno koliko upućuje? 215 00:09:31,630 --> 00:09:32,280 >> PUBLIKA: Dvije. 216 00:09:32,280 --> 00:09:32,920 >> JASON Hirschorn: Dvije. 217 00:09:32,920 --> 00:09:35,720 Jedan pratiti struje jedan i pratiti 218 00:09:35,720 --> 00:09:37,050 prethodni. 219 00:09:37,050 --> 00:09:38,450 To je samo popis pojedinačno povezani. 220 00:09:38,450 --> 00:09:39,670 To ide samo u jednom smjeru. 221 00:09:39,670 --> 00:09:43,220 Ako smo imali popis s dvostruko povezana, gdje sve što je ukazivao na stvar 222 00:09:43,220 --> 00:09:46,240 nakon toga i stvar prije njega, a zatim ne bi trebao to učiniti. 223 00:09:46,240 --> 00:09:49,350 No, u ovom slučaju ne želimo izgubiti evidenciju o tome što je bilo prije nas, u slučaju 224 00:09:49,350 --> 00:09:53,350 trebamo umetnuti pet negdje u sredini. 225 00:09:53,350 --> 00:09:55,610 Recimo da su umetanja devet. 226 00:09:55,610 --> 00:09:57,260 Što bi se dogodilo kada dobili smo na osam? 227 00:09:57,260 --> 00:10:01,860 228 00:10:01,860 --> 00:10:04,880 >> PUBLIKA: Morali bi dobiti taj nulta točka. 229 00:10:04,880 --> 00:10:07,820 Umjesto da nulta točka ne bi se dodati element, a zatim su 230 00:10:07,820 --> 00:10:09,216 je ukazati na devet. 231 00:10:09,216 --> 00:10:09,700 >> JASON Hirschorn: Točno. 232 00:10:09,700 --> 00:10:10,600 Tako smo dobili osam. 233 00:10:10,600 --> 00:10:13,140 Mi smo do kraja popisa, jer to se pokazuje na nulu. 234 00:10:13,140 --> 00:10:16,330 I sada, umjesto da se upućuju na null smo ga upućivati ​​na naš novi čvor. 235 00:10:16,330 --> 00:10:19,870 I mi smo postavili pokazivač u naš novi čvor na nulu. 236 00:10:19,870 --> 00:10:21,445 Da li itko ima bilo kakvih pitanja o umetanju? 237 00:10:21,445 --> 00:10:25,620 238 00:10:25,620 --> 00:10:28,100 Što ako ja ne brinuti se o vođenja popisa riješeno? 239 00:10:28,100 --> 00:10:31,701 240 00:10:31,701 --> 00:10:34,350 >> PUBLIKA: Držite ga na početak ili kraj. 241 00:10:34,350 --> 00:10:35,510 >> JASON Hirschorn: Držite ga na početak ili kraj. 242 00:10:35,510 --> 00:10:37,276 Koji smo trebali učiniti? 243 00:10:37,276 --> 00:10:38,770 Bobby? 244 00:10:38,770 --> 00:10:41,020 Zašto na kraju? 245 00:10:41,020 --> 00:10:43,250 >> Ivanković: Zbog početak je već popunjena. 246 00:10:43,250 --> 00:10:43,575 >> JASON Hirschorn: OK. 247 00:10:43,575 --> 00:10:44,360 Početak je već popunjena. 248 00:10:44,360 --> 00:10:46,090 Tko želi raspravljati protiv Bobbyja. 249 00:10:46,090 --> 00:10:47,290 Marcus. 250 00:10:47,290 --> 00:10:48,910 >> Ivanković: Pa vjerojatno želite staviti ga na početku, jer 251 00:10:48,910 --> 00:10:50,140 inače, ako ste ga stavili na kraj ne bi se 252 00:10:50,140 --> 00:10:51,835 prošli cijeli popis. 253 00:10:51,835 --> 00:10:52,990 >> JASON Hirschorn: Točno. 254 00:10:52,990 --> 00:10:57,970 Dakle, ako ćemo razmišljati o izvođenja, Trajanje umetanja na kraju 255 00:10:57,970 --> 00:11:00,110 biti n, veličina ova. 256 00:11:00,110 --> 00:11:03,080 Što je veliki O runtime umetanja na početku? 257 00:11:03,080 --> 00:11:04,170 Konstantna vrijeme. 258 00:11:04,170 --> 00:11:07,075 Dakle, ako vam nije stalo do vođenja nešto izdvojiti, puno bolje da se samo 259 00:11:07,075 --> 00:11:08,420 umetnite na početku ovog popisa. 260 00:11:08,420 --> 00:11:10,320 I to može biti učinjeno u stalnom vrijeme. 261 00:11:10,320 --> 00:11:13,900 262 00:11:13,900 --> 00:11:14,690 >> OK. 263 00:11:14,690 --> 00:11:18,870 Sljedeća operacija se naći, i koji drugi - smo formulirano to kao potragu. 264 00:11:18,870 --> 00:11:22,470 Ali ćemo gledati kroz povezani popis za neki objekt. 265 00:11:22,470 --> 00:11:26,000 Momci su vidjeli kod za tražiti prije u predavanju. 266 00:11:26,000 --> 00:11:29,490 Ali mi vrsta upravo je to učinio s umetanje, ili barem umetanje 267 00:11:29,490 --> 00:11:30,580 nešto izdvojiti. 268 00:11:30,580 --> 00:11:36,350 Možete gledati kroz, idući čvor po čvor, dok ne pronađete broj koji ste 269 00:11:36,350 --> 00:11:37,780 u potrazi za. 270 00:11:37,780 --> 00:11:39,670 Što će se dogoditi ako ne dođete kraj popisa? 271 00:11:39,670 --> 00:11:43,020 Recimo ja sam u potrazi za devet i ja do kraja popisa. 272 00:11:43,020 --> 00:11:44,270 Što nam je činiti? 273 00:11:44,270 --> 00:11:47,147 274 00:11:47,147 --> 00:11:48,110 >> Ivanković: Povratak lažna? 275 00:11:48,110 --> 00:11:48,690 >> JASON Hirschorn: Povratak lažna. 276 00:11:48,690 --> 00:11:49,960 Nismo ga pronašli. 277 00:11:49,960 --> 00:11:52,010 Ako do kraja popisa i niste pronašli broj ste 278 00:11:52,010 --> 00:11:54,170 u potrazi za, to nije tamo. 279 00:11:54,170 --> 00:11:55,420 Sva pitanja oko pronaći? 280 00:11:55,420 --> 00:11:59,530 281 00:11:59,530 --> 00:12:04,615 Ako je to bio sortirani popis, što bi biti različit za naše traženje? 282 00:12:04,615 --> 00:12:07,370 283 00:12:07,370 --> 00:12:08,103 Da. 284 00:12:08,103 --> 00:12:10,600 >> PUBLIKA: On će pronaći prve vrijednosti koja je veća od one 285 00:12:10,600 --> 00:12:12,390 tražiš i zatim se vratiti false. 286 00:12:12,390 --> 00:12:13,190 >> JASON Hirschorn: Točno. 287 00:12:13,190 --> 00:12:17,310 Dakle, ako je to sortirani popis, ako možemo doći do nešto što je veće od onoga što 288 00:12:17,310 --> 00:12:20,180 tražimo, mi ne trebaju zadržati ide na kraju popisa. 289 00:12:20,180 --> 00:12:24,060 Mi smo u tom trenutku može vratiti false jer nećemo ga naći. 290 00:12:24,060 --> 00:12:27,340 Pitanje je sada, mi smo govorili o čuvanje povezane liste razvrstani, 291 00:12:27,340 --> 00:12:28,180 držeći ih nerazvrstani. 292 00:12:28,180 --> 00:12:30,050 To će biti nešto što si Vjerojatno će se morati razmišljati o 293 00:12:30,050 --> 00:12:34,240 kada kodiranje problema postaviti pet ako odabrati hash tablicu s odvojenim 294 00:12:34,240 --> 00:12:36,360 ulančavanje pristup, koji ćemo govoriti o kasnije. 295 00:12:36,360 --> 00:12:41,400 >> No, je li to vrijedno zadržati popis sortirati, a zatim biti u mogućnosti da možda ima 296 00:12:41,400 --> 00:12:42,310 brže pretraga? 297 00:12:42,310 --> 00:12:47,220 Ili je bolje da brzo umetanje nešto u stalnom izvođenja, ali onda 298 00:12:47,220 --> 00:12:48,430 imati više traži? 299 00:12:48,430 --> 00:12:52,250 To je tradeoff tamo da vam ću odlučiti što je prikladnije 300 00:12:52,250 --> 00:12:53,590 za svoj specifičan problem. 301 00:12:53,590 --> 00:12:56,680 I tu nije nužno jedan apsolutno pravo odgovoriti. 302 00:12:56,680 --> 00:12:59,520 No, to je svakako odluka dobivate napraviti, a vjerojatno i dobro braniti 303 00:12:59,520 --> 00:13:05,270 da, recimo, komentar ili dva zašto ste izabrali jedan nad drugim. 304 00:13:05,270 --> 00:13:06,490 >> Konačno, brisanje. 305 00:13:06,490 --> 00:13:08,100 Vidjeli smo brisanja. 306 00:13:08,100 --> 00:13:09,180 To je slično kao da se traži. 307 00:13:09,180 --> 00:13:11,020 Tražimo elementa. 308 00:13:11,020 --> 00:13:12,390 Reci mi pokušavamo izbrisati šest. 309 00:13:12,390 --> 00:13:14,450 Tako smo pronašli šest ovdje. 310 00:13:14,450 --> 00:13:18,860 Ono što imamo kako bi bili sigurni smo to je da je sve što je ukazuje na 311 00:13:18,860 --> 00:13:21,220 šest - kao što smo vidjeli u koraku dvojica ovdje - 312 00:13:21,220 --> 00:13:26,500 bez obzira što se pokazuje na šest potrebe za preskočiti šest sada i biti promijenjen 313 00:13:26,500 --> 00:13:28,160 god šest upire prstom. 314 00:13:28,160 --> 00:13:31,410 Mi ne želimo da se ikada Orphan ostatak naš popis zaboravivši postaviti da 315 00:13:31,410 --> 00:13:32,960 natrag pointer. 316 00:13:32,960 --> 00:13:35,960 A onda ponekad, ovisno Na programu, oni će jednostavno 317 00:13:35,960 --> 00:13:37,380 izbrisali ovaj čvor cijelosti. 318 00:13:37,380 --> 00:13:40,135 Ponekad ćete se htjeti vratiti vrijednost koja je u ovom čvoru. 319 00:13:40,135 --> 00:13:42,490 Dakle to je kako brisanja djela. 320 00:13:42,490 --> 00:13:44,610 Bilo kakva pitanja na brisanje? 321 00:13:44,610 --> 00:13:51,280 322 00:13:51,280 --> 00:13:53,850 >> PUBLIKA: Dakle, ako idete za brisanje je, bi li samo koristiti besplatno, jer 323 00:13:53,850 --> 00:13:55,655 vjerojatno je malloced? 324 00:13:55,655 --> 00:13:57,976 >> JASON Hirschorn: Ako želite da se oslobodite nešto što je točno, a vi 325 00:13:57,976 --> 00:13:58,540 malloced ga. 326 00:13:58,540 --> 00:14:00,410 Reci mi htjeli vratiti tu vrijednost. 327 00:14:00,410 --> 00:14:04,010 Mogli bismo se vratili sa šest, a zatim besplatno ovaj čvor i poziv besplatno na njega. 328 00:14:04,010 --> 00:14:06,180 Ili ćemo vjerojatno bih nazvati bez prvog , a zatim se vratiti šest. 329 00:14:06,180 --> 00:14:11,210 330 00:14:11,210 --> 00:14:11,580 >> OK. 331 00:14:11,580 --> 00:14:14,010 Dakle, idemo dalje prakticirati kodiranja. 332 00:14:14,010 --> 00:14:16,090 Idemo to kod tri funkcije. 333 00:14:16,090 --> 00:14:18,260 Prvi se zove insert_node. 334 00:14:18,260 --> 00:14:22,170 Dakle imate kod koji sam ti e-poštom, a ako gledate to kasnije 335 00:14:22,170 --> 00:14:28,020 možete pristupiti kodu u linked.c na web stranici CS50. 336 00:14:28,020 --> 00:14:30,880 No, u linked.c, postoji neki Kostur kod koji je već 337 00:14:30,880 --> 00:14:32,280 napisano je za tebe. 338 00:14:32,280 --> 00:14:34,560 A tu je i par funkcija morate napisati. 339 00:14:34,560 --> 00:14:36,380 >> Prvo ćemo pisati insert_node. 340 00:14:36,380 --> 00:14:39,800 A što radi insert_node jest unosi cijeli broj. 341 00:14:39,800 --> 00:14:42,440 A ti daje cijeli broj u popisu povezana. 342 00:14:42,440 --> 00:14:45,470 A posebno, trebate da bi popis sortiran 343 00:14:45,470 --> 00:14:47,650 od najmanjih do najvećih. 344 00:14:47,650 --> 00:14:51,360 Isto tako, ne želim ulažite duplikate. 345 00:14:51,360 --> 00:14:54,600 Na kraju, kao što možete vidjeti insert_node vraća bool. 346 00:14:54,600 --> 00:14:57,140 Dakle, ti si trebao pustiti korisnik znati li je ili nije umetak 347 00:14:57,140 --> 00:15:00,800 uspješna po povratku istina ili laž. 348 00:15:00,800 --> 00:15:02,580 Na kraju ovog programa - 349 00:15:02,580 --> 00:15:05,750 i za ovu fazu ne treba brinuti o oslobađanju ništa. 350 00:15:05,750 --> 00:15:11,790 Dakle, sve što radite je uzimanje cijeli broj i ubacivanja u popisu. 351 00:15:11,790 --> 00:15:13,890 >> To je ono što ja tražim od tebe učiniti sada. 352 00:15:13,890 --> 00:15:17,620 Opet, u linked.c, koje svi imaju, je kod kostur. 353 00:15:17,620 --> 00:15:20,980 A ti bi trebao vidjeti prema dnu Uzorak funkciju deklaracija. 354 00:15:20,980 --> 00:15:27,390 No, prije odlaska u to kodiranja u C, vrlo sam Vam savjetujemo da ide 355 00:15:27,390 --> 00:15:29,330 kroz korake smo bili trenirao svaki tjedan. 356 00:15:29,330 --> 00:15:31,100 Već smo prošli Slika te. 357 00:15:31,100 --> 00:15:33,380 Tako da bi trebao imati neke razumijevanje kako se to radi. 358 00:15:33,380 --> 00:15:36,590 No, ja bih vas potaknuti da napiše Neki pseudocode prije ronjenja u. 359 00:15:36,590 --> 00:15:38,640 I mi ćemo ići preko pseudocode kao skupina. 360 00:15:38,640 --> 00:15:41,470 I onda nakon što ste napisali pseudocode, a jednom smo pisani naši 361 00:15:41,470 --> 00:15:45,850 pseudocode kao grupa, možete ulaziti u to kodiranje u C. 362 00:15:45,850 --> 00:15:49,980 >> Kao glava gore, funkcija insert_node je vjerojatno najzahtjevnijim od 363 00:15:49,980 --> 00:15:53,550 tri smo ćemo pisati, jer sam dodao neke dodatne ograničenja za 364 00:15:53,550 --> 00:15:57,190 Vaš programiranje, a naročito da nećeš umetnuti bilo 365 00:15:57,190 --> 00:15:59,880 duplikati i da je popis treba ostati sortirani. 366 00:15:59,880 --> 00:16:02,660 Dakle, ovo je ne-beznačajan Program što vam je potrebno za kodiranje. 367 00:16:02,660 --> 00:16:06,470 A zašto ne uzeti pet do sedam minuta samo da se radi o 368 00:16:06,470 --> 00:16:07,640 pseudocode i kod. 369 00:16:07,640 --> 00:16:09,460 A onda ćemo početi ide kao grupa. 370 00:16:09,460 --> 00:16:11,680 Opet, ako imate bilo kakvih pitanja samo digne ruku i ja ću doći oko. 371 00:16:11,680 --> 00:16:15,258 372 00:16:15,258 --> 00:16:16,508 . 373 00:16:16,508 --> 00:18:28,370 374 00:18:28,370 --> 00:18:30,120 >> Također smo općenito raditi to - 375 00:18:30,120 --> 00:18:32,070 ili ja ne izričito vam reći može raditi s ljudima. 376 00:18:32,070 --> 00:18:36,500 No, očito, vrlo sam Vam savjetujemo, Ako imate pitanja, pitajte 377 00:18:36,500 --> 00:18:39,840 Susjeda sjedi pored tebe ili čak i raditi s nekim 378 00:18:39,840 --> 00:18:40,510 drugo, ako želite. 379 00:18:40,510 --> 00:18:42,600 To ne mora biti pojedinac tiha djelatnost. 380 00:18:42,600 --> 00:20:11,770 381 00:20:11,770 --> 00:20:16,330 >> Počnimo s pisanjem neke pseudocode na brodu. 382 00:20:16,330 --> 00:20:19,395 Tko mi može dati prvu liniju pseudocode za ovaj program? 383 00:20:19,395 --> 00:20:22,240 384 00:20:22,240 --> 00:20:23,640 Za tu funkciju, a ne - insert_node. 385 00:20:23,640 --> 00:20:29,960 386 00:20:29,960 --> 00:20:31,830 Alden? 387 00:20:31,830 --> 00:20:36,560 >> PUBLIKA: Dakle, prva stvar koju sam učinio je stvoriti novi pokazivač na čvor i ja 388 00:20:36,560 --> 00:20:41,320 inicijaliziran da pokazuje na isti Ono što popis pokazuje da. 389 00:20:41,320 --> 00:20:41,550 >> JASON Hirschorn: OK. 390 00:20:41,550 --> 00:20:45,190 Dakle, ti si stvaranje novog pokazivač na popisu, a ne na čvoru. 391 00:20:45,190 --> 00:20:45,420 >> PUBLIKA: Točno. 392 00:20:45,420 --> 00:20:46,150 Da. 393 00:20:46,150 --> 00:20:46,540 >> JASON Hirschorn: OK. 394 00:20:46,540 --> 00:20:48,221 I onda ono što želimo učiniti? 395 00:20:48,221 --> 00:20:49,163 Ono što je nakon toga? 396 00:20:49,163 --> 00:20:50,105 Što o čvoru? 397 00:20:50,105 --> 00:20:51,050 Nemamo čvor. 398 00:20:51,050 --> 00:20:52,300 Mi samo imaju vrijednost. 399 00:20:52,300 --> 00:20:55,918 400 00:20:55,918 --> 00:20:58,890 Ako želimo umetnuti čvor, što nam je činiti trebate učiniti prije nego što možemo ni 401 00:20:58,890 --> 00:20:59,980 razmišljam o tome umetanjem? 402 00:20:59,980 --> 00:21:00,820 >> Publika: Oh, ispričavam se. 403 00:21:00,820 --> 00:21:02,160 moramo malloc prostor za čvor. 404 00:21:02,160 --> 00:21:02,455 >> JASON Hirschorn: Izvrsno. 405 00:21:02,455 --> 00:21:03,210 Učinimo - 406 00:21:03,210 --> 00:21:04,628 OK. 407 00:21:04,628 --> 00:21:06,065 Ne mogu doći da je visok. 408 00:21:06,065 --> 00:21:08,939 409 00:21:08,939 --> 00:21:09,897 OK. 410 00:21:09,897 --> 00:21:13,236 Mi ćemo ići prema dolje, a zatim koristimo dva stupca. 411 00:21:13,236 --> 00:21:13,732 Ja ne mogu ići tako - 412 00:21:13,732 --> 00:21:14,982 OK. 413 00:21:14,982 --> 00:21:23,660 414 00:21:23,660 --> 00:21:25,130 Stvaranje novog čvora. 415 00:21:25,130 --> 00:21:29,380 Možete napraviti još jedan pokazivač na popis ili se samo može koristiti popis kao što postoji. 416 00:21:29,380 --> 00:21:30,720 Zapravo ne trebate učiniti. 417 00:21:30,720 --> 00:21:31,750 >> Tako smo stvorili novi čvor. 418 00:21:31,750 --> 00:21:32,010 Velika. 419 00:21:32,010 --> 00:21:32,840 To je ono što mi radimo na prvom mjestu. 420 00:21:32,840 --> 00:21:34,870 Što je sljedeće? 421 00:21:34,870 --> 00:21:35,080 >> PUBLIKA: Čekajte. 422 00:21:35,080 --> 00:21:38,330 Trebamo stvoriti novi čvor sada ili trebamo čekati da se uvjerite da 423 00:21:38,330 --> 00:21:42,260 samo da nema kopije čvora na listi prije nego što smo ga stvorili? 424 00:21:42,260 --> 00:21:43,100 >> JASON Hirschorn: Dobro pitanje. 425 00:21:43,100 --> 00:21:47,770 Idemo drže da je za kasnije, jer Većina vremena mi ćemo biti stvaranje 426 00:21:47,770 --> 00:21:48,220 novi čvor. 427 00:21:48,220 --> 00:21:49,110 Tako ćemo zadržati ovdje. 428 00:21:49,110 --> 00:21:51,006 No, to je dobro pitanje. 429 00:21:51,006 --> 00:21:53,250 Ako smo ga stvorili i nađemo duplikat, što bi trebalo 430 00:21:53,250 --> 00:21:54,490 činimo prije povratka? 431 00:21:54,490 --> 00:21:55,190 >> PUBLIKA: Oslobodite ga. 432 00:21:55,190 --> 00:21:55,470 >> JASON Hirschorn: Da. 433 00:21:55,470 --> 00:21:56,500 Vjerojatno ga osloboditi. 434 00:21:56,500 --> 00:21:56,760 OK. 435 00:21:56,760 --> 00:21:59,850 Što nam je činiti nakon što smo stvoriti novi čvor? 436 00:21:59,850 --> 00:22:02,260 Annie? 437 00:22:02,260 --> 00:22:04,780 >> Ivanković: Mi smo stavili broj u čvoru? 438 00:22:04,780 --> 00:22:05,140 >> JASON Hirschorn: Točno. 439 00:22:05,140 --> 00:22:07,190 Mi smo stavili broj - mi malloc prostor. 440 00:22:07,190 --> 00:22:08,160 Ja ću ostaviti da sve kao jednu liniju. 441 00:22:08,160 --> 00:22:08,720 No, u pravu si. 442 00:22:08,720 --> 00:22:10,305 Malloc smo prostor, a zatim stavimo broj u. 443 00:22:10,305 --> 00:22:12,585 Možemo čak postaviti pokazivač dio toga na nulu. 444 00:22:12,585 --> 00:22:13,720 To je točno. 445 00:22:13,720 --> 00:22:17,400 A što je onda nakon toga? 446 00:22:17,400 --> 00:22:18,490 Došli smo ovu sliku na ploči. 447 00:22:18,490 --> 00:22:21,190 Dakle, što nam je činiti? 448 00:22:21,190 --> 00:22:22,680 >> Ivanković: Idemo po popisu. 449 00:22:22,680 --> 00:22:23,930 >> JASON Hirschorn: Prođite kroz popis. 450 00:22:23,930 --> 00:22:30,620 451 00:22:30,620 --> 00:22:31,100 OK. 452 00:22:31,100 --> 00:22:34,280 A što ćemo provjeriti na svakom čvoru. 453 00:22:34,280 --> 00:22:35,955 Kurt, što ćemo provjeriti za na svaki čvor? 454 00:22:35,955 --> 00:22:41,640 >> PUBLIKA: Pogledaj li n vrijednost čvor koji je veći od n vrijednosti 455 00:22:41,640 --> 00:22:43,070 našeg čvora. 456 00:22:43,070 --> 00:22:43,340 >> JASON Hirschorn: OK. 457 00:22:43,340 --> 00:22:44,280 Ja ću učiniti - 458 00:22:44,280 --> 00:22:45,855 Da, u redu. 459 00:22:45,855 --> 00:22:48,160 Tako da je n - 460 00:22:48,160 --> 00:22:59,040 Ja ću reći, ako je vrijednost veća od tog čvora, a zatim što nam je činiti? 461 00:22:59,040 --> 00:23:07,290 >> Ivanković: Pa, onda ćemo umetnite stvar neposredno prije toga. 462 00:23:07,290 --> 00:23:07,970 >> JASON Hirschorn: OK. 463 00:23:07,970 --> 00:23:09,410 Dakle, ako je veći od toga, onda želimo umetnuti. 464 00:23:09,410 --> 00:23:14,010 No, želimo ga umetnite neposredno prije jer mi također bi trebao biti 465 00:23:14,010 --> 00:23:16,070 praćenje, a zatim, od onoga što je bilo prije. 466 00:23:16,070 --> 00:23:22,690 Dakle, prije nego što uložite. 467 00:23:22,690 --> 00:23:25,120 Dakle, vjerojatno ćemo nešto propustili ranije. 468 00:23:25,120 --> 00:23:27,770 Vjerojatno ćemo morati biti čuvanje evidenciju o tome što se događa. 469 00:23:27,770 --> 00:23:28,460 No, mi ćemo se vratiti tamo. 470 00:23:28,460 --> 00:23:30,160 Dakle, što je vrijednost manja od? 471 00:23:30,160 --> 00:23:38,030 472 00:23:38,030 --> 00:23:39,710 Kurt, što nam je činiti ako je vrijednost je manja od? 473 00:23:39,710 --> 00:23:43,000 >> PUBLIKA: Onda samo zadržati ide osim ako je to posljednja. 474 00:23:43,000 --> 00:23:43,550 >> JASON Hirschorn: Sviđa mi se to. 475 00:23:43,550 --> 00:23:44,800 Dakle, ići na sljedeći čvor. 476 00:23:44,800 --> 00:23:47,410 477 00:23:47,410 --> 00:23:48,930 Osim ako je to posljednja - 478 00:23:48,930 --> 00:23:51,100 vjerojatno Provjeravamo za to u smislu stanja. 479 00:23:51,100 --> 00:23:54,870 Ali da, pored čvora. 480 00:23:54,870 --> 00:23:58,680 I to je sve preniska, pa ćemo preseliti ovamo. 481 00:23:58,680 --> 00:24:02,030 No, ako je - 482 00:24:02,030 --> 00:24:03,280 može svatko vidjeti? 483 00:24:03,280 --> 00:24:07,230 484 00:24:07,230 --> 00:24:11,610 Ako smo jednaki, što nam je činiti? 485 00:24:11,610 --> 00:24:15,740 Ako vrijednost pokušavamo umetanje jednaka vrijednosti tog čvora? 486 00:24:15,740 --> 00:24:16,320 Da? 487 00:24:16,320 --> 00:24:18,400 >> PUBLIKA: [nečujan]. 488 00:24:18,400 --> 00:24:18,850 >> JASON Hirschorn: Da. 489 00:24:18,850 --> 00:24:19,290 S obzirom na to - 490 00:24:19,290 --> 00:24:20,090 Marcus je u pravu. 491 00:24:20,090 --> 00:24:21,330 Mogli smo možda učinili nešto drugo. 492 00:24:21,330 --> 00:24:25,360 No, s obzirom da smo ga stvorili, ovdje trebamo osloboditi, a zatim se vratiti. 493 00:24:25,360 --> 00:24:26,774 Oh boy. 494 00:24:26,774 --> 00:24:30,080 Je li bolje? 495 00:24:30,080 --> 00:24:31,850 Kako ti se čini? 496 00:24:31,850 --> 00:24:33,100 OK. 497 00:24:33,100 --> 00:24:35,360 498 00:24:35,360 --> 00:24:37,640 Besplatno je i onda ono što radimo vratiti, [nečujan]? 499 00:24:37,640 --> 00:24:41,330 500 00:24:41,330 --> 00:24:44,110 OK. 501 00:24:44,110 --> 00:24:45,360 Jesmo li mi nedostaje ništa? 502 00:24:45,360 --> 00:24:53,500 503 00:24:53,500 --> 00:24:59,650 Pa gdje su mi praćenje od prethodnog čvora? 504 00:24:59,650 --> 00:25:02,370 >> Ivanković: Mislim da će to ići nakon što stvorite novi čvor. 505 00:25:02,370 --> 00:25:02,600 >> JASON Hirschorn: OK. 506 00:25:02,600 --> 00:25:03,940 Tako se na početku vjerojatno ćemo - 507 00:25:03,940 --> 00:25:07,175 Da, možemo stvoriti pokazivač na novo čvora, kao prethodni čvor pokazivač i 508 00:25:07,175 --> 00:25:09,600 trenutni čvor pointer. 509 00:25:09,600 --> 00:25:12,640 Tako ćemo umetnite da je ovdje. 510 00:25:12,640 --> 00:25:15,610 511 00:25:15,610 --> 00:25:26,900 Stvaranje struje i natrag upućuje na čvorove. 512 00:25:26,900 --> 00:25:28,955 Ali, kada ćemo prilagoditi te naputke? 513 00:25:28,955 --> 00:25:30,205 Gdje ćemo to učiniti u kodu? 514 00:25:30,205 --> 00:25:33,830 515 00:25:33,830 --> 00:25:34,160 Jeff? 516 00:25:34,160 --> 00:25:35,170 >> PUBLIKA: - uvjeti vrijednost? 517 00:25:35,170 --> 00:25:36,420 >> JASON Hirschorn: Koji jedan posebno? 518 00:25:36,420 --> 00:25:39,862 519 00:25:39,862 --> 00:25:40,720 >> Ivanković: Ja sam samo zbunjena. 520 00:25:40,720 --> 00:25:44,200 Ako je vrijednost veća od ovog čvora ne znači da želite otići 521 00:25:44,200 --> 00:25:45,320 na sljedeći čvor? 522 00:25:45,320 --> 00:25:49,515 >> JASON Hirschhorna: Dakle, ako je naša vrijednost veći od vrijednosti ovog čvora. 523 00:25:49,515 --> 00:25:52,130 >> Publika: Da, onda ste željeli ići dalje niz liniju, zar ne? 524 00:25:52,130 --> 00:25:52,590 >> JASON Hirschhorna: Točno. 525 00:25:52,590 --> 00:25:53,840 Dakle, mi ne ubacite ga ovdje. 526 00:25:53,840 --> 00:25:58,430 527 00:25:58,430 --> 00:26:03,240 Ako je vrijednost manja od tog čvora, a zatim idemo na sljedeći čvor - ili onda 528 00:26:03,240 --> 00:26:03,835 umetnite prije. 529 00:26:03,835 --> 00:26:05,966 >> Publika: Čekaj, što je ovo čvora i koja je vrijednost? 530 00:26:05,966 --> 00:26:08,510 531 00:26:08,510 --> 00:26:09,280 >> JASON Hirschhorna: Dobro pitanje. 532 00:26:09,280 --> 00:26:13,260 Vrijednost po ovoj definiciji funkcije je ono što mi daje. 533 00:26:13,260 --> 00:26:16,910 Tako je vrijednost broj mi dao. 534 00:26:16,910 --> 00:26:21,120 Dakle, ako je vrijednost manja od toga čvora, treba nam vremena za umetanje. 535 00:26:21,120 --> 00:26:24,575 Ako je vrijednost veća od ovog čvora idemo na sljedeći čvor. 536 00:26:24,575 --> 00:26:26,790 I natrag na izvornu pitanje, ipak, gdje je - 537 00:26:26,790 --> 00:26:29,060 >> Ivanković: Ako je vrijednost veća od ovog čvora. 538 00:26:29,060 --> 00:26:30,310 >> JASON Hirschhorna: I tako Što da radimo ovdje? 539 00:26:30,310 --> 00:26:36,790 540 00:26:36,790 --> 00:26:38,160 Sweet. 541 00:26:38,160 --> 00:26:38,860 To je točno. 542 00:26:38,860 --> 00:26:41,370 Samo ću napisati ažuriranje naputke. 543 00:26:41,370 --> 00:26:44,010 Ali da, s trenutne ti bi ga ažurirati 544 00:26:44,010 --> 00:26:46,080 ukazuju na sljedeću. 545 00:26:46,080 --> 00:26:47,330 Sve drugo što smo nestali? 546 00:26:47,330 --> 00:26:52,710 547 00:26:52,710 --> 00:26:54,940 Tako da ću upisati taj kod u gedit. 548 00:26:54,940 --> 00:26:58,375 I dok sam to učiniti, možete imati još par minuta da rade na kodiranje 549 00:26:58,375 --> 00:28:19,240 ovo u C 550 00:28:19,240 --> 00:28:20,940 >> Dakle, imam Unesite pseudocode. 551 00:28:20,940 --> 00:28:22,940 Quick note prije nego što započnete. 552 00:28:22,940 --> 00:28:25,560 Možda nismo u mogućnosti da u potpunosti ovo dovršiti u svemu 553 00:28:25,560 --> 00:28:27,300 tri od tih funkcija. 554 00:28:27,300 --> 00:28:30,630 Tu je točna rješenja za njih da ću e-mail na vas dečki 555 00:28:30,630 --> 00:28:33,730 Nakon dijelu, a to će biti objavljena na CS50.net. 556 00:28:33,730 --> 00:28:35,640 Dakle, ja ne savjetujemo vam da ići pogledati na dionicama. 557 00:28:35,640 --> 00:28:40,550 Ohrabrujem vas da se pokušate na svoj posjedovati, a zatim koristiti praksu 558 00:28:40,550 --> 00:28:41,760 Problemi Da biste provjerili svoje odgovore. 559 00:28:41,760 --> 00:28:47,070 To su sve bili dizajnirani da blisko odnose se i držati se onoga što 560 00:28:47,070 --> 00:28:48,400 morate raditi na problemu skupa. 561 00:28:48,400 --> 00:28:53,820 Dakle, ja ne potičemo vas da to vježbamo na svoju ruku, a zatim koristiti kod za 562 00:28:53,820 --> 00:28:54,660 provjerite svoje odgovore. 563 00:28:54,660 --> 00:28:57,060 Jer ja ne želim da se presele na hash tablice u nekom trenutku u odjeljku. 564 00:28:57,060 --> 00:28:58,150 Dakle, nismo mogli dobiti kroz sve to. 565 00:28:58,150 --> 00:28:59,960 No, mi ćemo učiniti što više možemo sada. 566 00:28:59,960 --> 00:29:00,370 >> OK. 567 00:29:00,370 --> 00:29:01,960 Počnimo. 568 00:29:01,960 --> 00:29:04,770 Asam, kako ćemo stvoriti novi čvor? 569 00:29:04,770 --> 00:29:06,810 >> PUBLIKA: Vi ne struct *. 570 00:29:06,810 --> 00:29:09,640 >> JASON Hirschhorna: Pa smo ima da se ovdje. 571 00:29:09,640 --> 00:29:10,040 Oh, ispričavam se. 572 00:29:10,040 --> 00:29:13,530 Govorili ste indetifikaciju *. 573 00:29:13,530 --> 00:29:17,260 >> Ivanković: I onda [? vrste?] čvor ili c čvor. 574 00:29:17,260 --> 00:29:17,780 >> JASON Hirschhorna: OK. 575 00:29:17,780 --> 00:29:19,740 Ja ću ga nazvati new_node tako da možemo ostati dosljedan. 576 00:29:19,740 --> 00:29:22,646 577 00:29:22,646 --> 00:29:33,180 >> Ivanković: I vi želite postaviti da na glavu, prvi čvor. 578 00:29:33,180 --> 00:29:33,580 >> JASON Hirschhorna: OK. 579 00:29:33,580 --> 00:29:37,290 Dakle, sada je to ukazivanje na - tako da je ovo nije stvorio novi čvor još. 580 00:29:37,290 --> 00:29:41,380 To samo pokazuje da prvi čvor u popisu. 581 00:29:41,380 --> 00:29:42,630 Kako stvoriti novi čvor? 582 00:29:42,630 --> 00:29:45,490 583 00:29:45,490 --> 00:29:48,070 Ako mi treba prostor za stvaranje novog čvora. 584 00:29:48,070 --> 00:29:49,230 Malloc. 585 00:29:49,230 --> 00:29:51,710 I koliko je velik? 586 00:29:51,710 --> 00:30:00,390 >> PUBLIKA: veličina struct. 587 00:30:00,390 --> 00:30:01,150 >> JASON Hirschhorna: veličina Struct. 588 00:30:01,150 --> 00:30:02,400 A što se rekonstruirati zove? 589 00:30:02,400 --> 00:30:09,670 590 00:30:09,670 --> 00:30:09,840 >> PUBLIKA: čvor? 591 00:30:09,840 --> 00:30:11,640 >> JASON Hirschhorna: čvor. 592 00:30:11,640 --> 00:30:17,640 Dakle malloc (sizeof (čvor)); daje nam prostora. 593 00:30:17,640 --> 00:30:19,740 A je to linija - 594 00:30:19,740 --> 00:30:21,740 jedna stvar je netočno na ovoj liniji. 595 00:30:21,740 --> 00:30:24,430 Je new_node pointer na struct? 596 00:30:24,430 --> 00:30:25,650 To je generički naziv. 597 00:30:25,650 --> 00:30:26,520 Što je to - 598 00:30:26,520 --> 00:30:27,450 čvora, točno. 599 00:30:27,450 --> 00:30:29,340 To je čvor *. 600 00:30:29,340 --> 00:30:33,010 I što nam je činiti odmah nakon smo malloc nešto, Asan? 601 00:30:33,010 --> 00:30:34,476 Što je prvo što nam je činiti? 602 00:30:34,476 --> 00:30:38,850 603 00:30:38,850 --> 00:30:40,320 Što ako to ne radi? 604 00:30:40,320 --> 00:30:42,430 >> Publika: Oh, provjerite je li to ukazuje na čvoru? 605 00:30:42,430 --> 00:30:43,310 >> JASON Hirschhorna: Točno. 606 00:30:43,310 --> 00:30:46,750 Dakle, ako ste new_node jednako dosegne null, što nam je činiti? 607 00:30:46,750 --> 00:30:51,650 608 00:30:51,650 --> 00:30:54,820 To vraća bool, ovu funkciju. 609 00:30:54,820 --> 00:30:57,760 Točno. 610 00:30:57,760 --> 00:30:58,450 Izgleda dobro. 611 00:30:58,450 --> 00:30:59,680 Bilo što dodati tamo? 612 00:30:59,680 --> 00:31:00,670 Mi ćemo dodati stvari na kraju. 613 00:31:00,670 --> 00:31:03,160 No, kako je do sada izgleda dobro. 614 00:31:03,160 --> 00:31:06,170 Stvaranje sadašnje i prijašnje naputke. 615 00:31:06,170 --> 00:31:08,650 Michael, kako mogu to učiniti? 616 00:31:08,650 --> 00:31:12,810 >> PUBLIKA: Ti bi napraviti čvor *. 617 00:31:12,810 --> 00:31:21,800 618 00:31:21,800 --> 00:31:25,502 Morao bi napraviti jedan ne za new_node ali za 619 00:31:25,502 --> 00:31:26,905 čvorovi već imamo. 620 00:31:26,905 --> 00:31:27,230 >> JASON Hirschhorna: OK. 621 00:31:27,230 --> 00:31:29,255 Dakle, trenutni čvor smo na. 622 00:31:29,255 --> 00:31:30,505 Nazvat ću to valuta. 623 00:31:30,505 --> 00:31:39,650 624 00:31:39,650 --> 00:31:39,770 U redu. 625 00:31:39,770 --> 00:31:41,620 Mi smo odlučili želimo zadržati dva, jer moramo znati 626 00:31:41,620 --> 00:31:42,870 ono što je prije njega. 627 00:31:42,870 --> 00:31:45,770 628 00:31:45,770 --> 00:31:47,020 Što im se inicijalizira na? 629 00:31:47,020 --> 00:31:49,874 630 00:31:49,874 --> 00:31:54,180 >> PUBLIKA: Njihova vrijednost u našem listu. 631 00:31:54,180 --> 00:31:58,090 >> JASON Hirschhorna: Dakle, što je Prva stvar na našem popisu? 632 00:31:58,090 --> 00:32:04,050 Ili kako znamo gdje na početku našeg popisa je? 633 00:32:04,050 --> 00:32:08,015 >> Ivanković: Nije li to prošlo u funkciji? 634 00:32:08,015 --> 00:32:08,466 >> JASON Hirschhorna: Točno. 635 00:32:08,466 --> 00:32:09,716 To je prošlo u redu ovdje. 636 00:32:09,716 --> 00:32:15,910 637 00:32:15,910 --> 00:32:18,980 Dakle, ako je prošlo u funkciji, početak popisa, što bismo mi 638 00:32:18,980 --> 00:32:21,270 postaviti struje jednaka? 639 00:32:21,270 --> 00:32:22,110 >> PUBLIKA: Popis. 640 00:32:22,110 --> 00:32:22,900 >> JASON Hirschhorna: Popis. 641 00:32:22,900 --> 00:32:24,090 To je točno. 642 00:32:24,090 --> 00:32:26,290 Sada ima adresu početak našeg popisa. 643 00:32:26,290 --> 00:32:28,450 A što je s prethodnih? 644 00:32:28,450 --> 00:32:31,920 >> PUBLIKA: Popis minus jedan? 645 00:32:31,920 --> 00:32:32,690 >> JASON Hirschhorna: Postoji ništa prije toga. 646 00:32:32,690 --> 00:32:34,580 Dakle, što možemo učiniti kako bi se pokazalo ništa? 647 00:32:34,580 --> 00:32:35,050 >> PUBLIKA: Null. 648 00:32:35,050 --> 00:32:35,450 >> JASON Hirschhorna: Da. 649 00:32:35,450 --> 00:32:37,950 To zvuči kao dobra ideja. 650 00:32:37,950 --> 00:32:38,360 Savršeno. 651 00:32:38,360 --> 00:32:39,630 Hvala Vam. 652 00:32:39,630 --> 00:32:42,850 Prođite kroz popis. 653 00:32:42,850 --> 00:32:45,490 Konstantin, koliko ćemo dugo proći kroz popis? 654 00:32:45,490 --> 00:32:49,010 >> Ivanković: Dok smo doći null. 655 00:32:49,010 --> 00:32:49,390 >> JASON Hirschhorna: OK. 656 00:32:49,390 --> 00:32:50,430 Dakle, ako, dok je, za petlju. 657 00:32:50,430 --> 00:32:52,200 Što da radimo? 658 00:32:52,200 --> 00:32:53,320 >> PUBLIKA: Možda za petlje? 659 00:32:53,320 --> 00:32:53,910 >> JASON Hirschhorna: Idemo raditi za petlju. 660 00:32:53,910 --> 00:32:55,870 OK. 661 00:32:55,870 --> 00:33:02,465 >> Ivanković: I mi reći - 662 00:33:02,465 --> 00:33:09,764 663 00:33:09,764 --> 00:33:13,390 do tekuće pokazivač nije jednak nuli. 664 00:33:13,390 --> 00:33:19,160 >> JASON Hirschhorna: Dakle, ako znamo stanje, kako možemo napisati petlju 665 00:33:19,160 --> 00:33:21,740 temelji off tom stanju. 666 00:33:21,740 --> 00:33:24,380 Kakav petlje trebamo koristiti? 667 00:33:24,380 --> 00:33:25,260 >> Ivanković: Dok. 668 00:33:25,260 --> 00:33:25,590 >> JASON Hirschhorna: Da. 669 00:33:25,590 --> 00:33:27,130 To ima više smisla na temelju off od onoga što je rekao. 670 00:33:27,130 --> 00:33:29,430 Ako mi samo želimo ići u smo da bi samo znam da je stvar, to bi 671 00:33:29,430 --> 00:33:31,680 smisla raditi while petlja. 672 00:33:31,680 --> 00:33:39,880 Iako trenutna ne odgovara null, Ako je vrijednost manja od ovog čvora. 673 00:33:39,880 --> 00:33:41,650 Akshar, daj mi tu liniju. 674 00:33:41,650 --> 00:33:48,810 675 00:33:48,810 --> 00:33:56,955 >> Ivanković: Ako trenutni-> n n manje od vrijednosti. 676 00:33:56,955 --> 00:34:00,170 677 00:34:00,170 --> 00:34:03,260 Ili obrnuto da. 678 00:34:03,260 --> 00:34:06,140 Prebacite taj nosač. 679 00:34:06,140 --> 00:34:06,620 >> JASON Hirschhorna: Žao mi je. 680 00:34:06,620 --> 00:34:08,760 >> Ivanković: Promjena nosača. 681 00:34:08,760 --> 00:34:10,914 >> JASON Hirschhorna: Dakle, ako je to veći od vrijednosti. 682 00:34:10,914 --> 00:34:18,719 683 00:34:18,719 --> 00:34:22,120 Budući da je zbunjujuće s komentirati gore, ja ću to učiniti. 684 00:34:22,120 --> 00:34:22,480 No, da. 685 00:34:22,480 --> 00:34:25,125 Ako je naša vrijednost je manje od toga čvora, što nam je činiti? 686 00:34:25,125 --> 00:34:25,540 Oh. 687 00:34:25,540 --> 00:34:26,710 Imam ga ovdje. 688 00:34:26,710 --> 00:34:27,960 Umetnite prije. 689 00:34:27,960 --> 00:34:32,080 690 00:34:32,080 --> 00:34:32,370 OK. 691 00:34:32,370 --> 00:34:33,933 Kako ćemo to učiniti? 692 00:34:33,933 --> 00:34:34,900 >> PUBLIKA: Je li to još uvijek ja? 693 00:34:34,900 --> 00:34:36,150 >> JASON Hirschhorna: Da. 694 00:34:36,150 --> 00:34:38,520 695 00:34:38,520 --> 00:34:39,770 >> PUBLIKA: Vi - 696 00:34:39,770 --> 00:34:42,909 697 00:34:42,909 --> 00:34:44,159 new_node-> next. 698 00:34:44,159 --> 00:34:46,770 699 00:34:46,770 --> 00:34:50,163 >> JASON Hirschhorna: Zato što je Hoće li to biti jednak? 700 00:34:50,163 --> 00:34:52,070 >> Ivanković: Bit će jednake struje. 701 00:34:52,070 --> 00:34:53,889 >> JASON Hirschhorna: Točno. 702 00:34:53,889 --> 00:34:55,730 I tako drugi - 703 00:34:55,730 --> 00:34:56,730 što još trebamo ažurirati? 704 00:34:56,730 --> 00:34:59,982 >> PUBLIKA: Provjerite je li prošlost jednako null. 705 00:34:59,982 --> 00:35:01,870 >> JASON Hirschhorna: Ako prev - 706 00:35:01,870 --> 00:35:03,730 pa ako pret jednaka null. 707 00:35:03,730 --> 00:35:05,990 >> Ivanković: To znači da će postati glava. 708 00:35:05,990 --> 00:35:06,780 >> JASON Hirschhorna: To znači da to je postalo glavu. 709 00:35:06,780 --> 00:35:07,620 Dakle, što nam je činiti? 710 00:35:07,620 --> 00:35:12,510 >> Ivanković: Mi radimo glavu jednaka new_node. 711 00:35:12,510 --> 00:35:16,690 >> JASON Hirschhorna: Voditelj jednako new_node. 712 00:35:16,690 --> 00:35:20,540 A zašto glavu ovdje, ne popis? 713 00:35:20,540 --> 00:35:24,940 >> Ivanković: Zbog glava je globalni varijabla koja je polazno mjesto. 714 00:35:24,940 --> 00:35:26,190 >> JASON Hirschhorna: Sweet. 715 00:35:26,190 --> 00:35:33,750 716 00:35:33,750 --> 00:35:34,170 OK. 717 00:35:34,170 --> 00:35:36,150 I - 718 00:35:36,150 --> 00:35:53,796 >> PUBLIKA: Onda još ne prev-> Sljedeći jednako new_node. 719 00:35:53,796 --> 00:35:55,080 A onda se vratite istina. 720 00:35:55,080 --> 00:35:59,560 721 00:35:59,560 --> 00:36:02,700 >> JASON Hirschhorna: Kamo postavili smo new_node kraj? 722 00:36:02,700 --> 00:36:04,850 >> PUBLIKA: Bih - 723 00:36:04,850 --> 00:36:06,180 Postavio sam da je na početku. 724 00:36:06,180 --> 00:36:07,430 >> JASON Hirschhorna: Pa što crta? 725 00:36:07,430 --> 00:36:10,000 726 00:36:10,000 --> 00:36:12,598 >> PUBLIKA: Nakon if ček ako je poznato. 727 00:36:12,598 --> 00:36:13,057 >> JASON Hirschhorna: Ovdje? 728 00:36:13,057 --> 00:36:18,335 >> Publika: Ja bih to new_node-> n jednaka vrijednosti. 729 00:36:18,335 --> 00:36:19,585 >> JASON Hirschhorna: Zvuči dobro. 730 00:36:19,585 --> 00:36:21,740 731 00:36:21,740 --> 00:36:25,090 Vjerojatno ima smisla - ne znamo Trebate znati što popis smo na 732 00:36:25,090 --> 00:36:26,280 jer mi smo samo bave s jednom popisu. 733 00:36:26,280 --> 00:36:29,560 Dakle, bolje funkciju deklaracija za to je samo da biste dobili osloboditi od ovaj 734 00:36:29,560 --> 00:36:34,360 cijelosti i samo stavite vrijednost u glavu. 735 00:36:34,360 --> 00:36:35,930 Mi čak ne trebate znati Popis onoga što smo u. 736 00:36:35,930 --> 00:36:39,140 Ali ja ću ga zadržati za sada i zatim ga promijeniti nakon ažuriranja 737 00:36:39,140 --> 00:36:42,590 dijapozitive i Kodeksa. 738 00:36:42,590 --> 00:36:44,980 Tako da izgleda dobro za sada. 739 00:36:44,980 --> 00:36:46,560 Ako vrijednost - tko može napraviti ovu liniju? 740 00:36:46,560 --> 00:36:47,810 Ako - 741 00:36:47,810 --> 00:36:52,240 742 00:36:52,240 --> 00:36:53,840 Što da radimo ovdje, Noah. 743 00:36:53,840 --> 00:36:57,890 744 00:36:57,890 --> 00:37:07,100 >> Ivanković: Ako je vrijednost veća nego valuta-> n - 745 00:37:07,100 --> 00:37:16,830 746 00:37:16,830 --> 00:37:18,240 >> JASON Hirschhorna: Kako napraviti idemo na sljedeći čvor? 747 00:37:18,240 --> 00:37:27,760 748 00:37:27,760 --> 00:37:30,530 >> PUBLIKA: Curr.Pharm.Des-> n jednak new_node. 749 00:37:30,530 --> 00:37:37,630 750 00:37:37,630 --> 00:37:39,195 >> JASON Hirschhorna: Tako je n što dio struct? 751 00:37:39,195 --> 00:37:43,065 752 00:37:43,065 --> 00:37:46,020 Cijeli broj. 753 00:37:46,020 --> 00:37:50,420 I new_node je pokazivač na čvor. 754 00:37:50,420 --> 00:37:51,880 Dakle, što je dio valuta trebamo ažurirati? 755 00:37:51,880 --> 00:38:03,900 756 00:38:03,900 --> 00:38:05,400 Ako ne nje, onda ono što je drugi dio? 757 00:38:05,400 --> 00:38:21,680 758 00:38:21,680 --> 00:38:22,810 Noah, što je drugi dio. 759 00:38:22,810 --> 00:38:23,570 >> Publika: Oh, naprijed. 760 00:38:23,570 --> 00:38:25,645 >> JASON Hirschhorna: Dalje, točno. 761 00:38:25,645 --> 00:38:26,410 Točno. 762 00:38:26,410 --> 00:38:28,770 Sljedeća je onaj pravi. 763 00:38:28,770 --> 00:38:31,540 I što još trebamo ažurirati, Noah? 764 00:38:31,540 --> 00:38:32,840 >> PUBLIKA: The pokazivače. 765 00:38:32,840 --> 00:38:34,840 >> JASON Hirschhorna: Tako ažuriramo struje. 766 00:38:34,840 --> 00:38:36,090 >> PUBLIKA: Prethodna-> next. 767 00:38:36,090 --> 00:38:48,160 768 00:38:48,160 --> 00:38:49,410 >> JASON Hirschhorna: Da. 769 00:38:49,410 --> 00:38:57,465 770 00:38:57,465 --> 00:38:58,370 OK, mi ćemo pauzirati. 771 00:38:58,370 --> 00:39:02,200 Tko nam može pomoći? 772 00:39:02,200 --> 00:39:03,385 Manu, što bi trebali učiniti? 773 00:39:03,385 --> 00:39:05,615 >> PUBLIKA: Moraš postaviti je jednak valuta-> Next. 774 00:39:05,615 --> 00:39:09,110 775 00:39:09,110 --> 00:39:11,630 No, to prije prethodne linije. 776 00:39:11,630 --> 00:39:12,880 >> JASON Hirschhorna: OK. 777 00:39:12,880 --> 00:39:16,590 778 00:39:16,590 --> 00:39:18,260 Bilo što drugo? 779 00:39:18,260 --> 00:39:19,170 Akshar. 780 00:39:19,170 --> 00:39:22,680 >> Ivanković: Ne mislim da si trebao promijeniti Curr-> next. 781 00:39:22,680 --> 00:39:29,270 Mislim da smo trebali učiniti valuta dosegne valuta-> next ići na sljedeći čvor. 782 00:39:29,270 --> 00:39:30,500 >> JASON Hirschhorna: Žao mi je, gdje? 783 00:39:30,500 --> 00:39:32,680 Na što crta? 784 00:39:32,680 --> 00:39:33,420 Ova linija? 785 00:39:33,420 --> 00:39:33,750 >> Publika: Da. 786 00:39:33,750 --> 00:39:35,745 Provjerite valuta jednaka valuta-> next. 787 00:39:35,745 --> 00:39:39,690 788 00:39:39,690 --> 00:39:43,360 >> JASON Hirschhorna: Pa to je točno jer struja 789 00:39:43,360 --> 00:39:45,220 pokazivač na čvor. 790 00:39:45,220 --> 00:39:48,550 I želimo ukazati na sljedećoj čvora što je sve trenutno 791 00:39:48,550 --> 00:39:49,930 Pokazao je. 792 00:39:49,930 --> 00:39:54,410 Valuta sebi ima naprijed. 793 00:39:54,410 --> 00:39:58,620 Ali, ako bismo se ažurirati curr.next, mi će biti ažuriranje stvarni znanje 794 00:39:58,620 --> 00:40:01,430 sama, a ne gdje je to pointer je pokazivao. 795 00:40:01,430 --> 00:40:02,680 Što o ovoj liniji, iako. 796 00:40:02,680 --> 00:40:05,160 797 00:40:05,160 --> 00:40:07,330 Avi? 798 00:40:07,330 --> 00:40:09,590 >> PUBLIKA: Prethodna-> next jednako valuta. 799 00:40:09,590 --> 00:40:12,500 800 00:40:12,500 --> 00:40:19,440 >> JASON Hirschhorna: Pa opet, ako je pret pokazivač na čvor, pret-> next je 801 00:40:19,440 --> 00:40:23,020 Stvarni pokazivač u čvor. 802 00:40:23,020 --> 00:40:27,190 Dakle, to bi se ažuriranje pokazivač na čvor valuta. 803 00:40:27,190 --> 00:40:28,570 Mi ne želimo da se ažurirati pokazivač na čvor. 804 00:40:28,570 --> 00:40:30,570 Želimo da se ažurirati natrag. 805 00:40:30,570 --> 00:40:31,850 Pa kako ćemo to učiniti? 806 00:40:31,850 --> 00:40:34,250 >> Ivanković: To bi samo biti prev. 807 00:40:34,250 --> 00:40:34,565 >> JASON Hirschhorna: Točno. 808 00:40:34,565 --> 00:40:35,560 Prošli je pokazivač na čvor. 809 00:40:35,560 --> 00:40:38,750 Sada smo ga mijenja na Nova pokazivač na čvor. 810 00:40:38,750 --> 00:40:40,830 OK Neka nas premjestiti prema dolje. 811 00:40:40,830 --> 00:40:41,940 Konačno, ovaj posljednji uvjet. 812 00:40:41,940 --> 00:40:44,896 Jeff, što mi radimo ovdje? 813 00:40:44,896 --> 00:40:47,515 >> Ivanković: Ako je vrijednost jednak akt-> n. 814 00:40:47,515 --> 00:40:51,030 815 00:40:51,030 --> 00:40:51,300 >> JASON Hirschhorna: Žao mi je. 816 00:40:51,300 --> 00:40:52,372 Ajme meni. 817 00:40:52,372 --> 00:40:54,330 Što? 818 00:40:54,330 --> 00:40:55,580 Vrijednost == valuta-> n. 819 00:40:55,580 --> 00:41:01,050 820 00:41:01,050 --> 00:41:02,300 Što nam je činiti? 821 00:41:02,300 --> 00:41:04,760 822 00:41:04,760 --> 00:41:10,950 >> PUBLIKA: Vi bi oslobodili našu new_node, a onda bih se vratiti false. 823 00:41:10,950 --> 00:41:21,410 824 00:41:21,410 --> 00:41:23,460 >> JASON Hirschhorna: To je ono što smo do sada napisano. 825 00:41:23,460 --> 00:41:25,710 Ima li itko išta dodati prije nego što ćemo napraviti? 826 00:41:25,710 --> 00:41:35,460 827 00:41:35,460 --> 00:41:35,710 OK. 828 00:41:35,710 --> 00:41:36,960 Idemo probati. 829 00:41:36,960 --> 00:41:44,180 830 00:41:44,180 --> 00:41:46,110 Kontrola može doći do kraja od ne-praznina funkcije. 831 00:41:46,110 --> 00:41:48,310 Avi, što se događa? 832 00:41:48,310 --> 00:41:51,380 >> PUBLIKA: Jeste li trebao staviti povrat istina izvan while petlje? 833 00:41:51,380 --> 00:41:53,900 834 00:41:53,900 --> 00:41:54,400 >> JASON Hirschhorna: Ne znam. 835 00:41:54,400 --> 00:41:54,780 Da li mi želimo? 836 00:41:54,780 --> 00:41:55,520 >> Ivanković: Nema veze. 837 00:41:55,520 --> 00:41:56,350 Ne. 838 00:41:56,350 --> 00:41:57,180 >> JASON Hirschhorna: Akshar? 839 00:41:57,180 --> 00:41:59,460 >> Ivanković: Mislim da je značilo da stavi povratak false na kraju 840 00:41:59,460 --> 00:42:02,230 while petlje. 841 00:42:02,230 --> 00:42:03,270 >> JASON Hirschhorna: Pa gdje želiš to ići? 842 00:42:03,270 --> 00:42:05,270 >> PUBLIKA: Poput izvan while petlje. 843 00:42:05,270 --> 00:42:08,800 Dakle, ako ste izašli iz while petlje to znači da ste došli do kraja i 844 00:42:08,800 --> 00:42:09,980 ništa se nije dogodilo. 845 00:42:09,980 --> 00:42:10,410 >> JASON Hirschhorna: OK. 846 00:42:10,410 --> 00:42:12,340 Dakle, što nam je činiti u ovdje? 847 00:42:12,340 --> 00:42:13,702 >> PUBLIKA: Vraćate lažna kao i tamo. 848 00:42:13,702 --> 00:42:15,040 >> JASON Hirschhorna: Oh, mi učinite to na oba mjesta? 849 00:42:15,040 --> 00:42:15,650 >> Publika: Da. 850 00:42:15,650 --> 00:42:16,900 >> JASON Hirschhorna: OK. 851 00:42:16,900 --> 00:42:24,840 852 00:42:24,840 --> 00:42:26,160 Hoćemo li ići? 853 00:42:26,160 --> 00:42:26,980 Ajme meni. 854 00:42:26,980 --> 00:42:27,290 Žao mi je. 855 00:42:27,290 --> 00:42:28,480 Ispričavam se na zaslonu. 856 00:42:28,480 --> 00:42:30,530 To je vrsta šiziti na nas. 857 00:42:30,530 --> 00:42:31,520 Dakle, odabrati opciju. 858 00:42:31,520 --> 00:42:35,260 Zero, po kodu, zatvara program. 859 00:42:35,260 --> 00:42:36,700 Jedan unosi nešto. 860 00:42:36,700 --> 00:42:37,990 Idemo umetnite tri. 861 00:42:37,990 --> 00:42:42,900 862 00:42:42,900 --> 00:42:45,380 Umetak nije bila uspješna. 863 00:42:45,380 --> 00:42:46,500 Idem isprintati. 864 00:42:46,500 --> 00:42:48,050 Ja nemam ništa. 865 00:42:48,050 --> 00:42:48,450 OK. 866 00:42:48,450 --> 00:42:50,250 Možda je to bio samo slučajnost. 867 00:42:50,250 --> 00:42:52,810 Umetnite jedan. 868 00:42:52,810 --> 00:42:55,770 Ne uspješna. 869 00:42:55,770 --> 00:42:57,470 OK. 870 00:42:57,470 --> 00:43:02,400 Trčimo preko GDB jako brzo provjeriti što se događa. 871 00:43:02,400 --> 00:43:06,055 >> Zapamti gdb. / Naziv vašeg Program nas dobiva u GDB. 872 00:43:06,055 --> 00:43:07,610 Je li to puno za nositi? 873 00:43:07,610 --> 00:43:08,560 Treperi? 874 00:43:08,560 --> 00:43:10,400 Vjerojatno. 875 00:43:10,400 --> 00:43:12,760 Zatvorite oči i uzeti neke duboke diše, ako se umorite 876 00:43:12,760 --> 00:43:13,580 gleda na to. 877 00:43:13,580 --> 00:43:14,200 Ja sam u GDB. 878 00:43:14,200 --> 00:43:15,830 Što je prvo što mi je činiti u GDB? 879 00:43:15,830 --> 00:43:17,050 Moramo shvatiti ono što se ovdje događa. 880 00:43:17,050 --> 00:43:17,310 Idemo vidjeti. 881 00:43:17,310 --> 00:43:21,650 Imamo šest minuta na slici što se događa. 882 00:43:21,650 --> 00:43:22,900 Break glavna. 883 00:43:22,900 --> 00:43:25,950 884 00:43:25,950 --> 00:43:28,130 I onda što da radim? 885 00:43:28,130 --> 00:43:29,180 Carlos? 886 00:43:29,180 --> 00:43:31,060 Run. 887 00:43:31,060 --> 00:43:32,250 OK. 888 00:43:32,250 --> 00:43:34,160 Idemo odaberite opciju. 889 00:43:34,160 --> 00:43:36,330 A što N čini? 890 00:43:36,330 --> 00:43:38,480 Next. 891 00:43:38,480 --> 00:43:38,950 Da. 892 00:43:38,950 --> 00:43:39,740 >> PUBLIKA: Jeste li se ne spominju - 893 00:43:39,740 --> 00:43:45,230 Zar nisi rekao da je glava, bilo je inicijalizira na nulu na početku. 894 00:43:45,230 --> 00:43:47,140 Ali mislio sam da si rekao da je u redu. 895 00:43:47,140 --> 00:43:50,040 896 00:43:50,040 --> 00:43:52,640 >> JASON Hirschhorna: Idemo - pogledajmo u GDB, a onda ćemo se vratiti. 897 00:43:52,640 --> 00:43:54,910 No, to zvuči kao da već imate neke ideje o tome što se događa. 898 00:43:54,910 --> 00:43:58,340 Na taj način želimo umetnuti nešto. 899 00:43:58,340 --> 00:43:59,390 OK. 900 00:43:59,390 --> 00:44:00,150 Mi smo umetnuli. 901 00:44:00,150 --> 00:44:00,770 Unesite int. 902 00:44:00,770 --> 00:44:01,990 Mi ćemo umetnuti tri. 903 00:44:01,990 --> 00:44:03,000 I onda sam na ovoj liniji. 904 00:44:03,000 --> 00:44:07,030 Kako mogu ići početi ispravljanje pogrešaka umetak poznat funkciju? 905 00:44:07,030 --> 00:44:08,280 Ajme meni. 906 00:44:08,280 --> 00:44:10,990 907 00:44:10,990 --> 00:44:12,240 To je puno. 908 00:44:12,240 --> 00:44:14,372 909 00:44:14,372 --> 00:44:16,445 Je li to izluđuje puno? 910 00:44:16,445 --> 00:44:19,696 911 00:44:19,696 --> 00:44:21,680 >> Publika: Oh, da je umro. 912 00:44:21,680 --> 00:44:22,930 >> JASON Hirschhorna: Upravo sam ga izvadio. 913 00:44:22,930 --> 00:44:27,364 914 00:44:27,364 --> 00:44:28,310 OK. 915 00:44:28,310 --> 00:44:29,560 >> PUBLIKA: Možda je to drugi kraj žice. 916 00:44:29,560 --> 00:44:37,000 917 00:44:37,000 --> 00:44:39,470 >> JASON Hirschhorna: Wow. 918 00:44:39,470 --> 00:44:42,330 Dakle, dno crta - 919 00:44:42,330 --> 00:44:43,470 Što ste rekli? 920 00:44:43,470 --> 00:44:46,040 >> PUBLIKA: Rekao sam ironija tehničku poteškoće u ovoj klasi. 921 00:44:46,040 --> 00:44:46,410 >> JASON Hirschhorna: Znam. 922 00:44:46,410 --> 00:44:48,660 Kad bih imala kontrolu nad tim dijelom. 923 00:44:48,660 --> 00:44:49,910 [Nečujan] 924 00:44:49,910 --> 00:44:54,430 925 00:44:54,430 --> 00:44:55,400 Zvuči sjajno. 926 00:44:55,400 --> 00:44:58,680 Zašto se vi, dečki početi razmišljati o ono što smo mogli učiniti u redu, 927 00:44:58,680 --> 00:45:01,140 , a mi ćemo se vratiti u 90 sekundi. 928 00:45:01,140 --> 00:46:18,160 929 00:46:18,160 --> 00:46:23,010 >> Avica, ja ću vas pitati kako to ide unutar insert_node to debug. 930 00:46:23,010 --> 00:46:28,940 931 00:46:28,940 --> 00:46:31,460 Dakle, ovo je mjesto gdje smo zadnji put stali. 932 00:46:31,460 --> 00:46:35,110 Kako mogu ući insert_node, Avica, ispitati što se događa? 933 00:46:35,110 --> 00:46:36,360 Što GDB naredba? 934 00:46:36,360 --> 00:46:41,050 935 00:46:41,050 --> 00:46:42,390 Break me ne bi unutra. 936 00:46:42,390 --> 00:46:46,200 937 00:46:46,200 --> 00:46:47,130 Da li Marquise znate? 938 00:46:47,130 --> 00:46:48,240 >> PUBLIKA: Što? 939 00:46:48,240 --> 00:46:51,780 >> JASON Hirschhorna: Što GDB naredba Koristim ići u ovu funkciju? 940 00:46:51,780 --> 00:46:52,070 >> PUBLIKA: korak? 941 00:46:52,070 --> 00:46:55,140 >> JASON Hirschhorna: Korak putem S. To mi unutra. 942 00:46:55,140 --> 00:46:55,476 OK. 943 00:46:55,476 --> 00:46:58,040 New_node mallocing neki prostor. 944 00:46:58,040 --> 00:46:59,120 To sve izgleda da je idući. 945 00:46:59,120 --> 00:47:00,370 Neka je ispitati new_node. 946 00:47:00,370 --> 00:47:03,270 947 00:47:03,270 --> 00:47:05,410 On je dobio neku memorijsku adresu. 948 00:47:05,410 --> 00:47:07,440 Pogledajmo - 949 00:47:07,440 --> 00:47:08,500 da je sve točno. 950 00:47:08,500 --> 00:47:12,220 Dakle, sve što je ovdje čini se raditi ispravno. 951 00:47:12,220 --> 00:47:14,530 >> PUBLIKA: Koja je razlika između P i zaslon? 952 00:47:14,530 --> 00:47:16,160 >> JASON Hirschhorna: P stoji za tisak. 953 00:47:16,160 --> 00:47:19,310 I tako me pitate što je Razlika između toga i ovo? 954 00:47:19,310 --> 00:47:22,330 U tom slučaju, ništa. 955 00:47:22,330 --> 00:47:26,960 No, općenito postoje neke razlike. 956 00:47:26,960 --> 00:47:28,220 A ti bi trebao izgledati u GDB priručniku. 957 00:47:28,220 --> 00:47:29,560 No, u tom slučaju, ništa. 958 00:47:29,560 --> 00:47:31,460 Mi imaju tendenciju da koriste otisak, iako je, zbog ne trebamo učiniti mnogo više nego 959 00:47:31,460 --> 00:47:33,960 ispisati jednu vrijednost. 960 00:47:33,960 --> 00:47:34,640 >> OK. 961 00:47:34,640 --> 00:47:40,300 Dakle, mi smo na liniji 80 našeg koda, postavljanje čvora * Curr jednak popisu. 962 00:47:40,300 --> 00:47:42,500 Neka nam ispisati valuta. 963 00:47:42,500 --> 00:47:45,260 964 00:47:45,260 --> 00:47:46,840 To je jednako popis. 965 00:47:46,840 --> 00:47:48,850 Sweet. 966 00:47:48,850 --> 00:47:49,340 Čekaj. 967 00:47:49,340 --> 00:47:50,590 Ona iznosi nešto. 968 00:47:50,590 --> 00:47:53,680 969 00:47:53,680 --> 00:47:56,190 To ne izgleda dobro. 970 00:47:56,190 --> 00:47:56,840 Tu smo. 971 00:47:56,840 --> 00:47:59,470 To je zato što je u GDB, zar ne, ako je to je linija ste na njemu 972 00:47:59,470 --> 00:48:00,330 još nije izvršena. 973 00:48:00,330 --> 00:48:03,100 Dakle, potrebno je zapravo tip uz izvršavanje crtu 974 00:48:03,100 --> 00:48:05,230 prije nego što vidim svoje rezultate. 975 00:48:05,230 --> 00:48:06,680 Dakle, tu smo. 976 00:48:06,680 --> 00:48:09,490 Upravo smo izvršiti ovu liniju, natrag jednaka null. 977 00:48:09,490 --> 00:48:13,590 Pa opet, ako ćemo ispisati natrag nećemo vidjeti ništa čudno. 978 00:48:13,590 --> 00:48:18,680 Ali ako mi zapravo izvršiti da crta, pa ćemo vidjeti 979 00:48:18,680 --> 00:48:20,380 da cijev radio. 980 00:48:20,380 --> 00:48:21,060 >> Dakle, imamo valuta. 981 00:48:21,060 --> 00:48:23,180 Oni su i dobra. 982 00:48:23,180 --> 00:48:24,010 Zar ne? 983 00:48:24,010 --> 00:48:28,130 Sada smo na ovoj liniji ovdje. 984 00:48:28,130 --> 00:48:29,310 Dok valuta nije jednak null. 985 00:48:29,310 --> 00:48:31,110 Pa, što to valuta jednaka? 986 00:48:31,110 --> 00:48:32,450 Upravo smo vidjeli da iznosio null. 987 00:48:32,450 --> 00:48:33,210 Ispisala smo. 988 00:48:33,210 --> 00:48:35,110 Ja ću ga ispisati ponovo. 989 00:48:35,110 --> 00:48:36,720 Tako je da while petlja će se izvršiti? 990 00:48:36,720 --> 00:48:37,270 >> Ivanković: Ne. 991 00:48:37,270 --> 00:48:39,790 >> JASON Hirschhorna: Pa kad sam upisali da linije, vidjet ćete skočio smo skroz 992 00:48:39,790 --> 00:48:41,390 dolje na dnu, povratak false. 993 00:48:41,390 --> 00:48:44,520 A onda ćemo se vratiti false i vratite se u naš program i 994 00:48:44,520 --> 00:48:48,020 na kraju isprintati, kao što smo vidjeli, umetak nije bio uspješan. 995 00:48:48,020 --> 00:48:51,010 Dakle, svatko tko ima bilo kakve ideje o tome što što trebate učiniti kako bi riješili ovaj? 996 00:48:51,010 --> 00:48:54,200 997 00:48:54,200 --> 00:48:57,570 Ja ću čekati dok ne vidim par ruku ići gore. 998 00:48:57,570 --> 00:48:58,830 Nismo izvršiti to. 999 00:48:58,830 --> 00:49:01,660 Imajte na umu, ovo je bio prvi put što smo radili. 1000 00:49:01,660 --> 00:49:02,430 Neću napraviti par. 1001 00:49:02,430 --> 00:49:03,670 Ja ću učiniti malo. 1002 00:49:03,670 --> 00:49:04,830 Zbog par znači dvoje. 1003 00:49:04,830 --> 00:49:07,620 Ja ću čekati za više od dva. 1004 00:49:07,620 --> 00:49:10,690 >> Prvi prvom stavljanju, Curr, po defaultu jednak null. 1005 00:49:10,690 --> 00:49:14,050 I ova petlja samo izvršava ako valuta nije null. 1006 00:49:14,050 --> 00:49:18,740 Pa kako mogu dobiti oko ovoga? 1007 00:49:18,740 --> 00:49:19,990 Ja vidim tri ruke. 1008 00:49:19,990 --> 00:49:28,490 1009 00:49:28,490 --> 00:49:29,780 Ja ću čekati za više od tri. 1010 00:49:29,780 --> 00:49:33,460 1011 00:49:33,460 --> 00:49:35,940 Marcus, što vi mislite? 1012 00:49:35,940 --> 00:49:37,730 >> Ivanković: Pa, ako je to potrebno da se izvršiti više od jednom, samo 1013 00:49:37,730 --> 00:49:39,948 ga promijeniti na do-while petlje. 1014 00:49:39,948 --> 00:49:41,250 >> JASON Hirschhorna: OK. 1015 00:49:41,250 --> 00:49:44,240 Hoće li to riješiti naš problem, iako? 1016 00:49:44,240 --> 00:49:47,750 >> Ivanković: U ovom slučaju ne radi Činjenica da je popis prazan. 1017 00:49:47,750 --> 00:49:52,150 Pa onda vjerojatno samo treba dodati izjavu da će, ako se petlja izlazi 1018 00:49:52,150 --> 00:49:55,312 onda morate biti na kraju Popis, na kojem vas uputiti 1019 00:49:55,312 --> 00:49:56,562 samo mogu umetnuti. 1020 00:49:56,562 --> 00:49:58,920 1021 00:49:58,920 --> 00:49:59,680 >> JASON Hirschhorna: Sviđa mi se to. 1022 00:49:59,680 --> 00:50:00,500 To ima smisla. 1023 00:50:00,500 --> 00:50:03,390 Ako petlje izlazi - 1024 00:50:03,390 --> 00:50:04,800 jer ćete se vratiti false ovdje. 1025 00:50:04,800 --> 00:50:08,220 Dakle, ako na petlji izlaza, onda smo na kraj popisa, ili možda 1026 00:50:08,220 --> 00:50:10,690 početak popisa, ako u njemu nema ničega to, što je isti kao i na kraju. 1027 00:50:10,690 --> 00:50:12,770 Dakle, sada želimo umetnuti Nešto je ovdje. 1028 00:50:12,770 --> 00:50:17,380 Pa kako se to kod izgleda, Marcus? 1029 00:50:17,380 --> 00:50:21,600 >> Ivanković: Ako ste već dobili čvor malloced, možete samo reći 1030 00:50:21,600 --> 00:50:25,400 new_node-> next jednako null, jer to mora biti na kraju. 1031 00:50:25,400 --> 00:50:27,510 Ili new_node-> next jednako null. 1032 00:50:27,510 --> 00:50:27,765 >> JASON Hirschhorna: OK. 1033 00:50:27,765 --> 00:50:28,190 Oprostite. 1034 00:50:28,190 --> 00:50:35,760 New_node-> next jednako null zato što smo na kraju. 1035 00:50:35,760 --> 00:50:36,460 To ne staviti ga u. 1036 00:50:36,460 --> 00:50:37,710 Kako ćemo to staviti na popisu? 1037 00:50:37,710 --> 00:50:46,130 1038 00:50:46,130 --> 00:50:46,460 Točno. 1039 00:50:46,460 --> 00:50:47,750 To je samo postavljanje jednaka. 1040 00:50:47,750 --> 00:50:50,940 No kako smo to zapravo stavite ga na popisu? 1041 00:50:50,940 --> 00:50:54,170 Što se upućuju na kraj popisa? 1042 00:50:54,170 --> 00:50:56,090 >> Ivanković: voditelj. 1043 00:50:56,090 --> 00:50:57,566 >> JASON Hirschhorna: Žao mi je? 1044 00:50:57,566 --> 00:50:59,440 >> PUBLIKA: Voditelj pokazuje na kraju liste. 1045 00:50:59,440 --> 00:51:01,480 >> JASON Hirschhorna: Ako ovdje nema ničega Popis, glava se upućuju na 1046 00:51:01,480 --> 00:51:04,170 kraj popisa. 1047 00:51:04,170 --> 00:51:06,920 Tako da ću raditi za Prvi umetanja. 1048 00:51:06,920 --> 00:51:09,810 Što ako postoji par stvari na popisu? 1049 00:51:09,810 --> 00:51:12,470 Nego što mi ne želimo postaviti glavu jednaka new_node. 1050 00:51:12,470 --> 00:51:13,790 Što želimo tamo raditi? 1051 00:51:13,790 --> 00:51:15,610 Da? 1052 00:51:15,610 --> 00:51:16,860 Vjerojatno natrag. 1053 00:51:16,860 --> 00:51:23,560 1054 00:51:23,560 --> 00:51:24,810 Hoće li to raditi? 1055 00:51:24,810 --> 00:51:28,950 1056 00:51:28,950 --> 00:51:33,050 Sjetite se da je samo natrag pokazivač na čvor. 1057 00:51:33,050 --> 00:51:34,770 I prethodni je lokalna varijabla. 1058 00:51:34,770 --> 00:51:38,080 Dakle, ova linija će postaviti lokalnu varijablu, natrag, jednak ili 1059 00:51:38,080 --> 00:51:39,380 pokazujući na taj novi čvor. 1060 00:51:39,380 --> 00:51:41,500 To nije zapravo će ga staviti u našem listu, iako. 1061 00:51:41,500 --> 00:51:44,330 Kako ćemo to staviti na našem popisu? 1062 00:51:44,330 --> 00:51:45,620 Akchar? 1063 00:51:45,620 --> 00:51:46,870 >> Ivanković: Mislim da ti napraviti trenutni-> next. 1064 00:51:46,870 --> 00:51:50,186 1065 00:51:50,186 --> 00:51:52,550 >> JASON Hirschhorna: OK. 1066 00:51:52,550 --> 00:51:54,010 valuta-> next. 1067 00:51:54,010 --> 00:51:58,768 Pa opet, jedini razlog zbog kojeg smo dolje ovdje je, što se sadašnja jednaka? 1068 00:51:58,768 --> 00:51:59,760 >> PUBLIKA: Jednako null. 1069 00:51:59,760 --> 00:52:01,790 >> JASON Hirschhorna: Pa što će se dogoditi ako nam je činiti nul-> next? 1070 00:52:01,790 --> 00:52:02,810 Što ćemo dobiti? 1071 00:52:02,810 --> 00:52:04,060 Mi ćemo dobiti grešku segmentaciju. 1072 00:52:04,060 --> 00:52:06,600 1073 00:52:06,600 --> 00:52:08,880 >> Ivanković: Do valuta jednaka null. 1074 00:52:08,880 --> 00:52:10,760 >> JASON Hirschhorna: To je ista stvar kao prev, ipak, jer postoji 1075 00:52:10,760 --> 00:52:12,820 područna promjenljiva smo postavljanje jednaka je ovaj novi čvor. 1076 00:52:12,820 --> 00:52:16,680 1077 00:52:16,680 --> 00:52:20,920 Vratimo se na našu sliku umetanja nešto. 1078 00:52:20,920 --> 00:52:25,500 Reci mi umetanja na kraju popisa, tako da upravo ovdje. 1079 00:52:25,500 --> 00:52:30,010 Imamo trenutni pokazivač koji je ukazujući na nulu i prethodne točke 1080 00:52:30,010 --> 00:52:32,800 koja upućuju na 8.. 1081 00:52:32,800 --> 00:52:35,330 Dakle, ono što mi je potrebno ažurirati, Avi? 1082 00:52:35,330 --> 00:52:36,680 >> PUBLIKA: Prethodna-> next? 1083 00:52:36,680 --> 00:52:41,980 >> JASON Hirschhorna: Prethodna-> next je ono želimo ažurirati, jer to 1084 00:52:41,980 --> 00:52:44,960 zapravo će ga stavite na kraj popisa. 1085 00:52:44,960 --> 00:52:47,220 Još uvijek imamo jednu grešku, ipak, da ćemo upasti u. 1086 00:52:47,220 --> 00:52:50,090 Što je to bug? 1087 00:52:50,090 --> 00:52:50,790 Da? 1088 00:52:50,790 --> 00:52:53,860 >> Ivanković: Bit će da se vrate netočno u ovom slučaju? 1089 00:52:53,860 --> 00:52:56,380 >> JASON Hirschhorna: Oh, je je će se vratiti false. 1090 00:52:56,380 --> 00:52:57,430 Ali postoji još jedan bug. 1091 00:52:57,430 --> 00:52:58,930 Dakle, mi ćemo morati staviti u povratku pravog. 1092 00:52:58,930 --> 00:53:01,370 >> PUBLIKA: Da li natrag dalje jednaka null na vrhu popisa? 1093 00:53:01,370 --> 00:53:03,645 >> JASON Hirschhorna: Pa natrag dalje jednaka null na samom početku. 1094 00:53:03,645 --> 00:53:07,480 1095 00:53:07,480 --> 00:53:10,440 Pa kako možemo prijeći preko toga? 1096 00:53:10,440 --> 00:53:10,950 Da? 1097 00:53:10,950 --> 00:53:15,280 >> Ivanković: Mislim da možete učiniti provjeriti Prije while petlja vidjeti je li to 1098 00:53:15,280 --> 00:53:16,610 Popis prazna. 1099 00:53:16,610 --> 00:53:17,000 >> JASON Hirschhorna: OK. 1100 00:53:17,000 --> 00:53:17,710 Dakle, idemo ovdje. 1101 00:53:17,710 --> 00:53:18,530 Da li ček. 1102 00:53:18,530 --> 00:53:19,380 Ako - 1103 00:53:19,380 --> 00:53:20,770 >> PUBLIKA: Dakle, ako glava jednaka jednaka null. 1104 00:53:20,770 --> 00:53:24,300 1105 00:53:24,300 --> 00:53:26,320 >> JASON Hirschhorna: Ako glava jednaka jednaka null - 1106 00:53:26,320 --> 00:53:27,790 koji će nam reći ako je prazan list. 1107 00:53:27,790 --> 00:53:31,090 >> Ivanković: I onda ste učiniti glava jednaka novo. 1108 00:53:31,090 --> 00:53:34,740 >> JASON Hirschhorna: Voditelj jednako new_node? 1109 00:53:34,740 --> 00:53:35,730 I što još trebamo učiniti? 1110 00:53:35,730 --> 00:53:37,020 >> Ivanković: I onda se vratite istina. 1111 00:53:37,020 --> 00:53:37,535 >> JASON Hirschhorna: Ne baš. 1112 00:53:37,535 --> 00:53:38,785 Nedostaje nam jedan korak. 1113 00:53:38,785 --> 00:53:41,590 1114 00:53:41,590 --> 00:53:43,710 >> PUBLIKA: New_node iduće treba ukazivati ​​na nulu. 1115 00:53:43,710 --> 00:53:44,570 >> JASON Hirschhorna: Točno, Alden. 1116 00:53:44,570 --> 00:53:46,600 A onda se možemo vratiti istinito. 1117 00:53:46,600 --> 00:53:47,560 OK. 1118 00:53:47,560 --> 00:53:51,630 No, to je još uvijek dobra ideja za napraviti stvari na kraju popisa, zar ne? 1119 00:53:51,630 --> 00:53:51,950 U redu. 1120 00:53:51,950 --> 00:53:54,450 Mi smo još uvijek zapravo mogli dobiti na kraju liste. 1121 00:53:54,450 --> 00:53:57,870 Tako je to kod redu ako smo na kraju popisa, a tu su i neke 1122 00:53:57,870 --> 00:53:59,120 stvari na popisu? 1123 00:53:59,120 --> 00:54:01,830 1124 00:54:01,830 --> 00:54:02,040 Zar ne? 1125 00:54:02,040 --> 00:54:03,540 Budući da još uvijek imamo Marcus ideju. 1126 00:54:03,540 --> 00:54:06,870 Mogli bismo izašli iz ove petlje, jer mi smo na kraju popisa. 1127 00:54:06,870 --> 00:54:09,308 Tako ćemo i dalje žele to kod ovdje dolje? 1128 00:54:09,308 --> 00:54:10,520 >> Publika: Da. 1129 00:54:10,520 --> 00:54:11,000 >> JASON Hirschhorna: Da. 1130 00:54:11,000 --> 00:54:14,190 I ono što mi je potrebno da se to promijeni kako bi? 1131 00:54:14,190 --> 00:54:15,440 Istina. 1132 00:54:15,440 --> 00:54:19,580 1133 00:54:19,580 --> 00:54:21,640 To zvuči dobro svima do sada? 1134 00:54:21,640 --> 00:54:22,420 Bilo tko imati bilo - 1135 00:54:22,420 --> 00:54:23,480 Avi, imate li što dodati? 1136 00:54:23,480 --> 00:54:23,920 >> Ivanković: Ne. 1137 00:54:23,920 --> 00:54:25,276 >> JASON Hirschhorna: OK. 1138 00:54:25,276 --> 00:54:27,010 Tako smo napravili par promjena. 1139 00:54:27,010 --> 00:54:29,540 Mi smo napravili ovu provjeriti prije nego što otišao je u prazno popisu. 1140 00:54:29,540 --> 00:54:31,790 Tako smo pobrinuti prazan popisu. 1141 00:54:31,790 --> 00:54:35,500 I tu smo se pobrinuo za umetanje nešto na kraju liste. 1142 00:54:35,500 --> 00:54:38,930 Dakle, čini se kao što je ovaj, dok loop preuzimanju brigu o stvarima između, 1143 00:54:38,930 --> 00:54:41,920 negdje u popisu ako su stvari na popisu. 1144 00:54:41,920 --> 00:54:42,280 >> OK. 1145 00:54:42,280 --> 00:54:44,310 Neka nam pokrenuti ovaj program. 1146 00:54:44,310 --> 00:54:50,170 1147 00:54:50,170 --> 00:54:50,755 Ne uspješna. 1148 00:54:50,755 --> 00:54:52,190 >> PUBLIKA: Nisi uspjeti. 1149 00:54:52,190 --> 00:54:53,940 >> JASON Hirschhorna: Oh, Nisam to napraviti. 1150 00:54:53,940 --> 00:54:56,250 Dobro pitanje, Michael. 1151 00:54:56,250 --> 00:54:57,500 Dodajmo make povezani. 1152 00:54:57,500 --> 00:55:01,590 1153 00:55:01,590 --> 00:55:04,830 Line 87 postoji greška. 1154 00:55:04,830 --> 00:55:05,420 Line 87. 1155 00:55:05,420 --> 00:55:06,600 Alden, to je linija koju mi ​​je dao. 1156 00:55:06,600 --> 00:55:08,962 Što ne valja? 1157 00:55:08,962 --> 00:55:10,710 >> Ivanković: To mora biti na nulu. 1158 00:55:10,710 --> 00:55:11,000 >> JASON Hirschhorna: Izvrsno. 1159 00:55:11,000 --> 00:55:11,630 Točno u pravu. 1160 00:55:11,630 --> 00:55:13,290 To bi trebao biti nula. 1161 00:55:13,290 --> 00:55:15,210 Idemo napraviti opet. 1162 00:55:15,210 --> 00:55:17,220 Sastaviti. 1163 00:55:17,220 --> 00:55:17,890 OK. 1164 00:55:17,890 --> 00:55:19,400 Idemo umetnite tri. 1165 00:55:19,400 --> 00:55:20,570 Umetak je uspješna. 1166 00:55:20,570 --> 00:55:21,660 Idemo ga isprintati. 1167 00:55:21,660 --> 00:55:23,590 Oh, kad bismo mogli provjeriti. 1168 00:55:23,590 --> 00:55:25,500 No, nismo učinili ispisati još funkciju. 1169 00:55:25,500 --> 00:55:27,840 Idemo ući nešto drugo. 1170 00:55:27,840 --> 00:55:29,090 Što bismo trebali ući? 1171 00:55:29,090 --> 00:55:31,120 1172 00:55:31,120 --> 00:55:31,940 >> PUBLIKA: Seven. 1173 00:55:31,940 --> 00:55:33,340 >> JASON Hirschhorna: Sedam? 1174 00:55:33,340 --> 00:55:34,590 >> Publika: Da. 1175 00:55:34,590 --> 00:55:38,680 1176 00:55:38,680 --> 00:55:39,780 >> JASON Hirschhorna: Imamo grešku SEG. 1177 00:55:39,780 --> 00:55:43,760 Tako smo dobili jedan, ali mi je jasno Ne mogu dobiti dva. 1178 00:55:43,760 --> 00:55:45,690 Bilo je 05:07. 1179 00:55:45,690 --> 00:55:48,370 Tako smo mogli debug to za tri minute. 1180 00:55:48,370 --> 00:55:51,240 Ali idem da nas ostaviti ovdje i prelazak na hash tablice. 1181 00:55:51,240 --> 00:55:54,290 Ali opet, odgovore za ovaj broj Ja ću ga na e-mail za vas u malo. 1182 00:55:54,290 --> 00:55:55,440 Mi smo vrlo blizu tome. 1183 00:55:55,440 --> 00:55:58,300 Vrlo Ohrabrujem vas shvatiti ono što se ovdje događa i to popraviti. 1184 00:55:58,300 --> 00:56:02,400 Dakle, ja ću vam e-mail ovaj kod kao i plus rješenje - 1185 00:56:02,400 --> 00:56:03,670 Vjerojatno kasnije rješenje. 1186 00:56:03,670 --> 00:56:05,110 Prvo ovaj broj. 1187 00:56:05,110 --> 00:56:08,290 >> Druga stvar koju želim učiniti prije nego što smo završila je nismo oslobodili ništa. 1188 00:56:08,290 --> 00:56:10,370 Dakle, želim vam pokazati što Valgrind izgleda. 1189 00:56:10,370 --> 00:56:14,310 Ako ćemo pokrenuti Valgrind granice Na našem programu. / povezani. 1190 00:56:14,310 --> 00:56:22,540 Opet, sukladno ovom klizača, što treba pokrenuti Valgrind s nekim vrstama 1191 00:56:22,540 --> 00:56:26,410 mogućnost, u ovom slučaju - Curenje-check = puni. 1192 00:56:26,410 --> 00:56:27,660 Tako ćemo pisati Valgrind - Curenje-check = puni. 1193 00:56:27,660 --> 00:56:31,910 1194 00:56:31,910 --> 00:56:35,080 Dakle, to će pokrenuti Valgrind na našem programu. 1195 00:56:35,080 --> 00:56:37,000 I sad program zapravo radi. 1196 00:56:37,000 --> 00:56:40,190 Tako ćemo ga pokrenuti baš kao i prije, staviti nešto u. 1197 00:56:40,190 --> 00:56:40,830 Ja ću staviti u tri. 1198 00:56:40,830 --> 00:56:41,790 To radi. 1199 00:56:41,790 --> 00:56:43,202 Neću se pokušati staviti u nečemu drugo, jer si mi ide na 1200 00:56:43,202 --> 00:56:44,710 dobiti SEG False na tom slučaju. 1201 00:56:44,710 --> 00:56:46,700 Tako ću i prestati. 1202 00:56:46,700 --> 00:56:50,160 >> I sad vidite ovdje curiti i hrpa sažetak. 1203 00:56:50,160 --> 00:56:52,310 Ovo su dobre stvari koje želite provjeriti. 1204 00:56:52,310 --> 00:56:56,780 Dakle hrpa sažetak - piše, u uporabi na izlazu - osam bajtova u jednom bloku. 1205 00:56:56,780 --> 00:56:58,370 To je jedan blok čvora smo malloced. 1206 00:56:58,370 --> 00:57:02,230 Michael, rekli ste prije čvor je osam ugriza jer ima cijeli broj 1207 00:57:02,230 --> 00:57:02,680 i pokazivač. 1208 00:57:02,680 --> 00:57:04,550 Dakle, to je naša čvor. 1209 00:57:04,550 --> 00:57:08,170 I onda je, kaže koristili smo malloc sedam puta, a mi oslobodili 1210 00:57:08,170 --> 00:57:08,940 nešto šest puta. 1211 00:57:08,940 --> 00:57:13,680 No, mi nikada ne zove slobodna, tako da nemam Ideja o čemu se govori. 1212 00:57:13,680 --> 00:57:18,490 >> No, dovoljno je reći da kada vaš Program traje, malloc se zove 1213 00:57:18,490 --> 00:57:20,330 u nekim drugim mjestima koje smo ne morate brinuti o tome. 1214 00:57:20,330 --> 00:57:22,460 Dakle malloc vjerojatno zvao u nekim mjestima. 1215 00:57:22,460 --> 00:57:24,480 Mi ne trebamo brinuti gdje. 1216 00:57:24,480 --> 00:57:26,240 Ali ovo je stvarno nas. 1217 00:57:26,240 --> 00:57:27,380 Ova prva linija nam. 1218 00:57:27,380 --> 00:57:28,320 Ostavili smo taj blok. 1219 00:57:28,320 --> 00:57:30,330 I možete vidjeti da je ovdje u sažetku curenja. 1220 00:57:30,330 --> 00:57:31,950 Još uvijek dostupna - 1221 00:57:31,950 --> 00:57:32,930 osam bajtova u jednom bloku. 1222 00:57:32,930 --> 00:57:34,100 To znači da je pamćenje - 1223 00:57:34,100 --> 00:57:35,730 smo procurila tog sjećanja. 1224 00:57:35,730 --> 00:57:37,570 Definitivno izgubili - 1225 00:57:37,570 --> 00:57:38,770 nešto što je izgubljeno zauvijek. 1226 00:57:38,770 --> 00:57:40,590 Općenito, nećete vidim ništa tamo. 1227 00:57:40,590 --> 00:57:44,780 Ipak dostupna je općenito gdje vidjet ćete stvari, gdje ćete željeti 1228 00:57:44,780 --> 00:57:48,900 gledati da se vidi što kod treba li su oslobođeni, ali ste zaboravili da se oslobodi. 1229 00:57:48,900 --> 00:57:53,170 >> A onda, ako to nije bio slučaj, ako smo učinili sve što je besplatno, 1230 00:57:53,170 --> 00:57:54,360 možemo provjeriti. 1231 00:57:54,360 --> 00:57:57,330 Ajmo pokrenuti program Ne stavljajući u ništa. 1232 00:57:57,330 --> 00:57:59,800 Vidjet ćete ovdje u upotrebi na izlazu - 1233 00:57:59,800 --> 00:58:01,310 nula bajtova u nula blokova. 1234 00:58:01,310 --> 00:58:06,310 To znači da smo imali više ničega kada je ovaj program izašao. 1235 00:58:06,310 --> 00:58:12,090 Dakle, prije uključivanja u pset6, pokrenuti Valgrind i pazite da ne morate 1236 00:58:12,090 --> 00:58:15,310 bilo memorije curi u svom programu. 1237 00:58:15,310 --> 00:58:17,910 Ako imate bilo kakvih pitanja s Valgrind, slobodno doprijeti. 1238 00:58:17,910 --> 00:58:18,700 No, to je način kako ste ga koristiti. 1239 00:58:18,700 --> 00:58:20,890 Vrlo jednostavno - vidjeti ako ima u uporabi na izlazu - 1240 00:58:20,890 --> 00:58:22,270 bilo bajtova u svim blokovima. 1241 00:58:22,270 --> 00:58:27,890 1242 00:58:27,890 --> 00:58:29,580 >> Tako smo radili na insert čvor. 1243 00:58:29,580 --> 00:58:33,840 Imao sam i druge dvije funkcije ovdje - ispis čvorova i besplatne čvorove. 1244 00:58:33,840 --> 00:58:37,780 Opet, to su funkcije koje će biti dobro za vas na praksi 1245 00:58:37,780 --> 00:58:40,990 jer oni će vam pomoći ne samo s testni vježbe, ali i 1246 00:58:40,990 --> 00:58:42,180 na problem postavljen. 1247 00:58:42,180 --> 00:58:44,230 Oni map na prilično usko stvari ti si idući u morati učiniti u 1248 00:58:44,230 --> 00:58:45,010 Problem postaviti. 1249 00:58:45,010 --> 00:58:47,640 Ali ja ne želim da se uvjerite Dotaknut ćemo o svemu. 1250 00:58:47,640 --> 00:58:50,400 I Tablice su od ključnog značaja za što radimo u ovom poglavlju 1251 00:58:50,400 --> 00:58:51,980 tjedan - ili u set problema. 1252 00:58:51,980 --> 00:58:55,200 >> Tako ćemo završiti poglavlje govori o hash tablice. 1253 00:58:55,200 --> 00:58:58,140 Ako primijetite sam napravio Malo hash tablicu. 1254 00:58:58,140 --> 00:59:00,020 To nije ono što mi govorimo o tome, međutim. 1255 00:59:00,020 --> 00:59:03,540 Radi se o drugačija vrsta hash tablica. 1256 00:59:03,540 --> 00:59:07,300 I u svojoj srži, a hash tablicu nije ništa više od 1257 00:59:07,300 --> 00:59:08,860 Niz plus hash funkcija. 1258 00:59:08,860 --> 00:59:11,150 Idemo razgovarati malo samo bi bili sigurni svatko razumije što je 1259 00:59:11,150 --> 00:59:12,110 hash funkcija. 1260 00:59:12,110 --> 00:59:15,420 A ja ti govorim sada da je to ništa više od dvije stvari - 1261 00:59:15,420 --> 00:59:18,590 polje i hash funkcija. 1262 00:59:18,590 --> 00:59:20,716 I ovdje su koraci kroz koji to radi. 1263 00:59:20,716 --> 00:59:31,560 1264 00:59:31,560 --> 00:59:32,810 >> Tu je naša polja. 1265 00:59:32,810 --> 00:59:38,460 1266 00:59:38,460 --> 00:59:39,460 Tu je naša funkcija. 1267 00:59:39,460 --> 00:59:43,180 Konkretno, funkcija raspršivanja je potrebno napraviti par stvari s tim. 1268 00:59:43,180 --> 00:59:45,040 Ja ću posebno razgovarati o tome je problem postaviti. 1269 00:59:45,040 --> 00:59:46,450 Vjerojatno će uzeti u nizu. 1270 00:59:46,450 --> 00:59:50,570 1271 00:59:50,570 --> 00:59:51,770 A što će to vratiti? 1272 00:59:51,770 --> 00:59:52,640 Koji tip podataka? 1273 00:59:52,640 --> 00:59:54,260 Alden? 1274 00:59:54,260 --> 00:59:55,760 Vratiti Vaš hash funkcija? 1275 00:59:55,760 --> 00:59:58,760 Cijeli broj. 1276 00:59:58,760 --> 01:00:01,700 Dakle, to je ono mljeveno meso Tablica se sastoji od - 1277 01:00:01,700 --> 01:00:05,430 stol u obliku niza i hash funkcija. 1278 01:00:05,430 --> 01:00:06,010 Kako to radi? 1279 01:00:06,010 --> 01:00:07,300 Ona radi u tri koraka. 1280 01:00:07,300 --> 01:00:08,740 Dajemo mu ključ. 1281 01:00:08,740 --> 01:00:11,470 U ovom slučaju, mi ćemo mu dati niz. 1282 01:00:11,470 --> 01:00:18,140 Pozivamo hash funkciju po korak jedan na ključu, a mi dobili vrijednost. 1283 01:00:18,140 --> 01:00:20,310 >> Naime, mi ćemo reći smo dobili cijeli broj. 1284 01:00:20,310 --> 01:00:25,630 Taj broj, tu su vrlo specifične ograničenja na ono da je cijeli broj može biti. 1285 01:00:25,630 --> 01:00:28,880 U ovom primjeru, naš niz je veličine tri. 1286 01:00:28,880 --> 01:00:32,330 Dakle, što se brojevi mogu biti da cijeli. 1287 01:00:32,330 --> 01:00:35,970 Što je raspon važećih vrijednosti za da broj, tip ovog povratnog 1288 01:00:35,970 --> 01:00:37,220 hash funkciju? 1289 01:00:37,220 --> 01:00:40,440 1290 01:00:40,440 --> 01:00:42,110 Nula, jedan i dva. 1291 01:00:42,110 --> 01:00:46,060 Točka hash funkcije je shvatiti mjesto u nizu 1292 01:00:46,060 --> 01:00:47,790 gdje je naš ključni ide. 1293 01:00:47,790 --> 01:00:51,290 Postoje samo tri moguća mjesta ovdje - 1294 01:00:51,290 --> 01:00:52,130 nijedan, jedan ili dva. 1295 01:00:52,130 --> 01:00:55,360 Dakle, ova funkcija bolji povratak nijedan, jedan ili dva. 1296 01:00:55,360 --> 01:00:58,740 Neki vrijedi indeksom u ovom polju. 1297 01:00:58,740 --> 01:01:02,770 >> A onda, ovisno o tome gdje se vraća, možete vidjeti postoji niz open 1298 01:01:02,770 --> 01:01:03,730 zagrada vrijednost. 1299 01:01:03,730 --> 01:01:05,800 To je mjesto gdje možemo staviti ključ. 1300 01:01:05,800 --> 01:01:11,280 Dakle bacamo u bundevu, ćemo izaći na nulu. 1301 01:01:11,280 --> 01:01:15,540 U polje zagrada 0, stavili smo bundevu. 1302 01:01:15,540 --> 01:01:21,070 Poklanjamo u mačaka, izađemo jedan. 1303 01:01:21,070 --> 01:01:24,110 Mi smo stavili mačka u jednom. 1304 01:01:24,110 --> 01:01:25,480 Mi smo stavili u pauka. 1305 01:01:25,480 --> 01:01:26,710 Mi smo dobili iz dva. 1306 01:01:26,710 --> 01:01:30,200 Mi smo stavili pauka u polje zagrada dva. 1307 01:01:30,200 --> 01:01:32,300 Bilo bi lijepo ako je to je radio tako. 1308 01:01:32,300 --> 01:01:35,570 No, na žalost, kao što ćemo vidjeti, to je malo složeniji. 1309 01:01:35,570 --> 01:01:37,570 >> Prije nego što smo se tamo, na sva pitanja o tome osnovni 1310 01:01:37,570 --> 01:01:38,820 set-up od hash tablice? 1311 01:01:38,820 --> 01:01:49,050 1312 01:01:49,050 --> 01:01:51,940 To je slika točno ono što mi je nacrtao na ploči. 1313 01:01:51,940 --> 01:01:55,420 No, budući da ga je nacrtao na ploči, ja neću ići u njega i dalje. 1314 01:01:55,420 --> 01:02:00,430 U osnovi tipke, magija crna kutija - ili u ovom slučaju, tirkizna kutija - od 1315 01:02:00,430 --> 01:02:02,410 hash funkcija stavlja ih u kante. 1316 01:02:02,410 --> 01:02:04,690 I u ovom primjeru smo Ne stavljajući ime. 1317 01:02:04,690 --> 01:02:07,880 Mi smo stavljanjem pripadajući telefon broj imena u kantu. 1318 01:02:07,880 --> 01:02:10,430 No, što bi mogao vrlo dobro samo stavi ime u kantu. 1319 01:02:10,430 --> 01:02:12,950 >> To je samo slika onoga mi je nacrtao na ploči. 1320 01:02:12,950 --> 01:02:14,460 Imamo potencijalne zamke, ipak. 1321 01:02:14,460 --> 01:02:17,470 A tu su i dva osobito slajdovi da želim ići preko. 1322 01:02:17,470 --> 01:02:20,230 Prvi je o tome hash funkcija. 1323 01:02:20,230 --> 01:02:22,620 Zato sam pitao pitanje, što čini dobru funkciju ljestve? 1324 01:02:22,620 --> 01:02:24,220 Dajem dva odgovora. 1325 01:02:24,220 --> 01:02:26,630 Prvi je da je deterministička. 1326 01:02:26,630 --> 01:02:29,660 U kontekstu hash funkcija, Što to znači? 1327 01:02:29,660 --> 01:02:37,840 1328 01:02:37,840 --> 01:02:39,282 Da? 1329 01:02:39,282 --> 01:02:42,850 >> Ivanković: To se može pronaći Indeks je u stalnom vrijeme? 1330 01:02:42,850 --> 01:02:43,810 >> JASON Hirschhorna: Da nije ono što to znači. 1331 01:02:43,810 --> 01:02:44,725 No, to je dobar pogodak. 1332 01:02:44,725 --> 01:02:46,100 Ima li još netko pogađati na što to znači? 1333 01:02:46,100 --> 01:02:47,780 To je dobra funkcija hash je deterministička? 1334 01:02:47,780 --> 01:02:48,280 Annie? 1335 01:02:48,280 --> 01:02:51,680 >> Ivanković: To ključ može se preslikati samo na jednom mjestu u hash tablicu. 1336 01:02:51,680 --> 01:02:53,070 >> JASON Hirschhorna: To je točno u pravu. 1337 01:02:53,070 --> 01:02:57,430 Svaki put kada se stavi u bundevu, to se uvijek vraća na nulu. 1338 01:02:57,430 --> 01:03:01,660 Ako ste stavili u bundevu i vaše mljeveno meso Funkcija vraća na nulu, ali ima 1339 01:03:01,660 --> 01:03:06,060 vjerojatnost povratka nešto još veći od nule - 1340 01:03:06,060 --> 01:03:09,280 pa možda to može vratiti jednu ponekad ili druga dva puta - 1341 01:03:09,280 --> 01:03:11,100 to nije dobro funkcija hash. 1342 01:03:11,100 --> 01:03:11,800 Vi ste upravo pravo. 1343 01:03:11,800 --> 01:03:15,680 Vaš hash funkcija trebala vratiti Isti broj točan, u ovom slučaju, jer 1344 01:03:15,680 --> 01:03:17,780 Isti točan niz. 1345 01:03:17,780 --> 01:03:22,210 >> Možda se vrati na isti točan cijeli broj za istu točnim nizu 1346 01:03:22,210 --> 01:03:24,430 bez obzira kapitalizacije. 1347 01:03:24,430 --> 01:03:27,980 No, u tom slučaju to je još uvijek deterministička jer više stvari 1348 01:03:27,980 --> 01:03:29,350 se preslikati na istu vrijednost. 1349 01:03:29,350 --> 01:03:30,170 To je u redu. 1350 01:03:30,170 --> 01:03:32,615 Tako dugo dok je samo jedan izlaz za određenu ulaz. 1351 01:03:32,615 --> 01:03:35,630 1352 01:03:35,630 --> 01:03:36,350 >> OK. 1353 01:03:36,350 --> 01:03:38,340 Druga stvar je da je vraća valjane indekse. 1354 01:03:38,340 --> 01:03:40,220 Doveli smo se da je i ranije. 1355 01:03:40,220 --> 01:03:41,860 Ovaj hash funkcija - 1356 01:03:41,860 --> 01:03:43,710 oh boy - 1357 01:03:43,710 --> 01:03:46,840 hash funkcija treba povratak valjane indekse. 1358 01:03:46,840 --> 01:03:47,740 Tako kažu - 1359 01:03:47,740 --> 01:03:48,990 Idemo natrag u ovom primjeru. 1360 01:03:48,990 --> 01:03:52,580 1361 01:03:52,580 --> 01:03:57,540 Moj hash funkcija broji do slova u riječi. 1362 01:03:57,540 --> 01:03:58,380 To je hash funkcija. 1363 01:03:58,380 --> 01:03:59,740 I vraća da cijeli broj. 1364 01:03:59,740 --> 01:04:04,280 Dakle, ako imam riječi A, to je će se vratiti jedan. 1365 01:04:04,280 --> 01:04:06,900 I to će se staviti ovdje. 1366 01:04:06,900 --> 01:04:09,430 Što ako sam stavio u riječi palicom? 1367 01:04:09,430 --> 01:04:11,310 To će se vratiti tri. 1368 01:04:11,310 --> 01:04:12,560 Odakle bat ide? 1369 01:04:12,560 --> 01:04:18,730 1370 01:04:18,730 --> 01:04:19,750 >> To se ne uklapa. 1371 01:04:19,750 --> 01:04:21,000 Ali, to treba da ide negdje. 1372 01:04:21,000 --> 01:04:23,340 Ovo je moja hash tablicu, nakon svega, i sve treba da ide negdje. 1373 01:04:23,340 --> 01:04:24,590 Pa gdje bi trebao ići šišmiša? 1374 01:04:24,590 --> 01:04:28,020 1375 01:04:28,020 --> 01:04:28,710 Bilo misli? 1376 01:04:28,710 --> 01:04:29,450 Pogodi? 1377 01:04:29,450 --> 01:04:30,280 Dobri nagađanja? 1378 01:04:30,280 --> 01:04:31,220 >> PUBLIKA: Zero. 1379 01:04:31,220 --> 01:04:32,120 >> JASON Hirschhorna: Zašto nula? 1380 01:04:32,120 --> 01:04:35,990 >> Ivanković: Zbog tri modulo tri nula? 1381 01:04:35,990 --> 01:04:38,620 >> JASON Hirschhorna: Tri modulo tri nula. 1382 01:04:38,620 --> 01:04:40,810 To je velika pretpostavka, i to je točno. 1383 01:04:40,810 --> 01:04:43,870 Dakle, u ovom slučaju to bi trebalo vjerojatno ići na nulu. 1384 01:04:43,870 --> 01:04:51,080 Dakle, dobar način da se osigura da se ovaj hash Funkcija vraća samo valjane indekse se 1385 01:04:51,080 --> 01:04:54,580 to modulo veličinom stola. 1386 01:04:54,580 --> 01:04:57,360 Ako modulo štogod ove povrate od tri, uvijek ćeš dobiti 1387 01:04:57,360 --> 01:05:00,930 nešto između nula, jedan, dva i. 1388 01:05:00,930 --> 01:05:05,160 A ako se to uvijek vraća sedam, a ti uvijek modulo trojica, ti si 1389 01:05:05,160 --> 01:05:06,030 Uvijek će dobiti istu stvar. 1390 01:05:06,030 --> 01:05:09,270 >> Dakle, to je još uvijek deterministička ako modulo. 1391 01:05:09,270 --> 01:05:11,420 No, to će se pobrinuti da Vam nikada dobiti nešto - 1392 01:05:11,420 --> 01:05:12,940 nevažeća industrija. 1393 01:05:12,940 --> 01:05:16,840 Općenito, to bi se trebalo dogoditi modulu unutar hash funkciji. 1394 01:05:16,840 --> 01:05:18,240 Dakle, ne morate brinuti o tome. 1395 01:05:18,240 --> 01:05:20,555 Vi samo mogu osigurati da to vrijedi s indeksom. 1396 01:05:20,555 --> 01:05:23,700 1397 01:05:23,700 --> 01:05:26,700 Bilo kakva pitanja na ovaj potencijalna zamka? 1398 01:05:26,700 --> 01:05:36,590 1399 01:05:36,590 --> 01:05:39,060 >> OK. 1400 01:05:39,060 --> 01:05:40,290 I tamo idemo. 1401 01:05:40,290 --> 01:05:42,890 Sljedeća potencijalna zamka, a ovo je velika stvar. 1402 01:05:42,890 --> 01:05:46,880 Što ako se dvije tipke Karta na istoj vrijednosti? 1403 01:05:46,880 --> 01:05:49,350 Dakle, postoje dva načina da se to srediti. 1404 01:05:49,350 --> 01:05:53,140 1405 01:05:53,140 --> 01:05:56,020 Prvi se zove linearni sondiranje, koji sam 1406 01:05:56,020 --> 01:05:57,300 neće ići preko. 1407 01:05:57,300 --> 01:06:01,120 No, trebali biste biti upoznati s načinom koji radi i što je to. 1408 01:06:01,120 --> 01:06:05,610 >> Drugi ću ići preko jer to je onaj koji su mnogi 1409 01:06:05,610 --> 01:06:08,290 ljudi će vjerojatno završiti odlučivanju za korištenje u njihov problem setu. 1410 01:06:08,290 --> 01:06:09,820 Naravno, ne morate se. 1411 01:06:09,820 --> 01:06:15,280 No, za rješavanje problema skupa, mnogi ljudi imaju tendenciju da se odlučite za stvaranje hash tablicu 1412 01:06:15,280 --> 01:06:17,950 sa zasebnim ulančavanje za provedbu njihov rječnik. 1413 01:06:17,950 --> 01:06:21,390 Tako ćemo ići preko onoga što to znači stvoriti hash tablicu s 1414 01:06:21,390 --> 01:06:23,890 odvojeno ulančavanje. 1415 01:06:23,890 --> 01:06:26,260 >> Zato sam stavio u bundevu. 1416 01:06:26,260 --> 01:06:29,560 On se vraća na nulu. 1417 01:06:29,560 --> 01:06:31,410 I sam stavio bundevu ovdje. 1418 01:06:31,410 --> 01:06:35,880 1419 01:06:35,880 --> 01:06:37,930 Onda sam stavio u - 1420 01:06:37,930 --> 01:06:39,922 ono što je još jedan Halloween-tematske stvar? 1421 01:06:39,922 --> 01:06:42,200 >> PUBLIKA: Candy. 1422 01:06:42,200 --> 01:06:42,770 >> JASON Hirschhorna: Candy! 1423 01:06:42,770 --> 01:06:43,910 To je jedan veliki. 1424 01:06:43,910 --> 01:06:47,760 Stavio sam u slatkišima i bombonima također mi daje nulu. 1425 01:06:47,760 --> 01:06:49,350 Što da radim? 1426 01:06:49,350 --> 01:06:51,940 Bilo koji ideja? 1427 01:06:51,940 --> 01:06:53,940 Zato što svi nekako znali ono odvojeno ulančavanje je. 1428 01:06:53,940 --> 01:06:55,190 Dakle, bilo koji ideja što da radim? 1429 01:06:55,190 --> 01:06:58,170 1430 01:06:58,170 --> 01:06:59,110 Da. 1431 01:06:59,110 --> 01:07:03,810 >> PUBLIKA: Stavljanje niz zapravo u hash tablicu. 1432 01:07:03,810 --> 01:07:08,910 >> JASON Hirschhorna: Pa idemo u nacrtati dobru ideju ovamo. 1433 01:07:08,910 --> 01:07:09,340 OK. 1434 01:07:09,340 --> 01:07:12,290 >> PUBLIKA: Jeste hashtable [Nečujan] 1435 01:07:12,290 --> 01:07:16,640 pokazivač koji upućuje na Početak popisu. 1436 01:07:16,640 --> 01:07:20,930 A onda su se bundeve biti prva vrijednost u tom povezanom popisu i slatkiša biti 1437 01:07:20,930 --> 01:07:22,800 Druga vrijednost u tom povezanom popisu. 1438 01:07:22,800 --> 01:07:23,420 >> JASON Hirschhorna: OK. 1439 01:07:23,420 --> 01:07:24,670 Marcus, koji je bio izvanredan. 1440 01:07:24,670 --> 01:07:26,160 Ja ću razbiti taj niz. 1441 01:07:26,160 --> 01:07:28,890 Marcus je rekao ne prebrisati bundevu. 1442 01:07:28,890 --> 01:07:30,660 To bi bilo loše. 1443 01:07:30,660 --> 01:07:33,640 Nemojte staviti slatkiše negdje drugdje. 1444 01:07:33,640 --> 01:07:35,390 Mi ćemo ih staviti i na nulu. 1445 01:07:35,390 --> 01:07:37,770 Ali ćemo se nositi s stavljajući ih na nulu 1446 01:07:37,770 --> 01:07:39,395 stvaranja popisa na nuli. 1447 01:07:39,395 --> 01:07:42,430 I mi ćemo stvoriti popis sve što se preslikava na nulu. 1448 01:07:42,430 --> 01:07:47,960 A najbolji način smo naučili stvoriti Popis koja može narasti i smanjiti 1449 01:07:47,960 --> 01:07:49,840 dinamički nije unutar još jedan niz. 1450 01:07:49,840 --> 01:07:51,510 Dakle, ne višedimenzionalni niz. 1451 01:07:51,510 --> 01:07:54,080 No, kako bi samo stvoriti popis povezana. 1452 01:07:54,080 --> 01:07:55,330 >> Dakle, ono što je on predložio - 1453 01:07:55,330 --> 01:07:57,950 1454 01:07:57,950 --> 01:07:59,200 Ja ću dobiti novi - 1455 01:07:59,200 --> 01:08:15,380 1456 01:08:15,380 --> 01:08:19,689 je stvoriti niz s pokazivače, Niz pokazivača. 1457 01:08:19,689 --> 01:08:20,580 OK. 1458 01:08:20,580 --> 01:08:24,180 Imate li ideju ili savjet što tip ovog pokazivače treba biti? 1459 01:08:24,180 --> 01:08:26,290 Marcus? 1460 01:08:26,290 --> 01:08:27,250 >> PUBLIKA: upućuje na - 1461 01:08:27,250 --> 01:08:28,609 >> JASON Hirschhorna: Zato što vam rekao Popis povezani, pa - 1462 01:08:28,609 --> 01:08:29,520 >> PUBLIKA: Čvor upućuje? 1463 01:08:29,520 --> 01:08:30,670 >> JASON Hirschhorna: Čvor naputke. 1464 01:08:30,670 --> 01:08:32,830 Ako se stvari u našem povezani Popis su čvorovi onda oni 1465 01:08:32,830 --> 01:08:34,370 trebao biti čvor naputke. 1466 01:08:34,370 --> 01:08:35,939 A što oni jednaki početku? 1467 01:08:35,939 --> 01:08:36,990 >> PUBLIKA: Null. 1468 01:08:36,990 --> 01:08:38,240 >> JASON Hirschhorna: Null. 1469 01:08:38,240 --> 01:08:44,540 1470 01:08:44,540 --> 01:08:46,080 Dakle, tu je naš prazna stvar. 1471 01:08:46,080 --> 01:08:47,170 Vraća bundeve nulu. 1472 01:08:47,170 --> 01:08:48,569 Što nam je činiti? 1473 01:08:48,569 --> 01:08:49,609 Šetnja me kroz njega? 1474 01:08:49,609 --> 01:08:50,810 Zapravo, Marcus već mi je dao. 1475 01:08:50,810 --> 01:08:52,439 Netko drugi me provesti kroz to. 1476 01:08:52,439 --> 01:08:54,760 Što nam je činiti kada smo - 1477 01:08:54,760 --> 01:08:56,609 ovo izgleda vrlo slično ono što smo upravo radili. 1478 01:08:56,609 --> 01:08:57,396 Avi. 1479 01:08:57,396 --> 01:08:59,090 >> Ivanković: Idem uzeti pogodak. 1480 01:08:59,090 --> 01:09:01,250 Dakle, kada ste dobili slatkiše. 1481 01:09:01,250 --> 01:09:01,640 >> JASON Hirschhorna: Da. 1482 01:09:01,640 --> 01:09:03,120 Pa, dobili smo bundevu. 1483 01:09:03,120 --> 01:09:03,870 Idemo naš prvi. 1484 01:09:03,870 --> 01:09:04,324 Imamo bundevu. 1485 01:09:04,324 --> 01:09:04,779 >> Ivanković: U redu. 1486 01:09:04,779 --> 01:09:05,880 Vraća bundeve nulu. 1487 01:09:05,880 --> 01:09:08,770 Znači li to staviti u to. 1488 01:09:08,770 --> 01:09:10,810 Ili zapravo, da ga stavi u popisu povezane. 1489 01:09:10,810 --> 01:09:13,550 >> JASON Hirschhorna: Kako nam je činiti stavite ga na popisu povezanom? 1490 01:09:13,550 --> 01:09:15,479 >> Publika: Oh, stvarna sintakse? 1491 01:09:15,479 --> 01:09:16,240 >> JASON Hirschhorna: Dovoljno je prošetati - 1492 01:09:16,240 --> 01:09:16,740 reći više. 1493 01:09:16,740 --> 01:09:19,310 Što nam je činiti? 1494 01:09:19,310 --> 01:09:22,100 >> PUBLIKA: Vi samo stavite je kao prvi čvor. 1495 01:09:22,100 --> 01:09:22,675 >> JASON Hirschhorna: OK. 1496 01:09:22,675 --> 01:09:29,069 Dakle, mi imamo čvor, bundeve. 1497 01:09:29,069 --> 01:09:31,560 I sad kako sam ga umetnite? 1498 01:09:31,560 --> 01:09:34,590 1499 01:09:34,590 --> 01:09:37,090 >> PUBLIKA: Vi dodijeliti da pokazivača. 1500 01:09:37,090 --> 01:09:37,970 >> JASON Hirschhorna: Koji pointer? 1501 01:09:37,970 --> 01:09:39,620 >> PUBLIKA: pointer na nuli. 1502 01:09:39,620 --> 01:09:41,420 >> JASON Hirschhorna: Pa gdje to upućuje? 1503 01:09:41,420 --> 01:09:42,810 >> PUBLIKA: Da nulu upravo sada. 1504 01:09:42,810 --> 01:09:43,529 >> JASON Hirschhorna: Pa, to ukazuje na nulu. 1505 01:09:43,529 --> 01:09:44,499 Ali sam stavljajući u bundevu. 1506 01:09:44,499 --> 01:09:46,053 Pa gdje bi trebao ukazati? 1507 01:09:46,053 --> 01:09:46,880 >> Publikom: bundeva. 1508 01:09:46,880 --> 01:09:47,399 >> JASON Hirschhorna: Da bundeve. 1509 01:09:47,399 --> 01:09:48,760 Točno. 1510 01:09:48,760 --> 01:09:50,010 Dakle, to ukazuje na bundeve. 1511 01:09:50,010 --> 01:09:52,500 1512 01:09:52,500 --> 01:09:54,250 A gdje je taj pointer u bundeve trenutku? 1513 01:09:54,250 --> 01:09:57,986 1514 01:09:57,986 --> 01:09:58,340 Na 1515 01:09:58,340 --> 01:09:58,590 >> PUBLIKA: Null. 1516 01:09:58,590 --> 01:09:59,210 >> JASON Hirschhorna: na nulu. 1517 01:09:59,210 --> 01:10:00,460 Točno. 1518 01:10:00,460 --> 01:10:03,570 1519 01:10:03,570 --> 01:10:05,140 Pa jednostavno umetnuti nešto u popisu povezane. 1520 01:10:05,140 --> 01:10:07,210 Upravo smo pisali ovaj kod za to. 1521 01:10:07,210 --> 01:10:09,520 Gotovo smo skoro ga dobio potpuno puknut. 1522 01:10:09,520 --> 01:10:10,790 Sada smo umetnuli slatkiše. 1523 01:10:10,790 --> 01:10:13,480 Naš candy također ide na nulu. 1524 01:10:13,480 --> 01:10:16,100 Dakle, što nam je činiti s bombonima? 1525 01:10:16,100 --> 01:10:18,790 >> Ivanković: To ovisi o tome hoće li ili Ne pokušavamo to riješiti. 1526 01:10:18,790 --> 01:10:19,640 >> JASON Hirschhorna: To je točno u pravu. 1527 01:10:19,640 --> 01:10:21,070 To ovisi o tome hoće li ili ne pokušavamo to riješiti. 1528 01:10:21,070 --> 01:10:22,660 Pretpostavimo da nismo će se to riješiti. 1529 01:10:22,660 --> 01:10:24,880 >> Ivanković: Pa onda, kao što smo razgovarali prije, to je najjednostavniji samo da ga stavi 1530 01:10:24,880 --> 01:10:28,590 odmah na početku, tako kazaljka s nula bodova do slatkiša. 1531 01:10:28,590 --> 01:10:29,020 >> JASON Hirschhorna: OK. 1532 01:10:29,020 --> 01:10:29,380 Držite se. 1533 01:10:29,380 --> 01:10:30,630 Dopustite mi stvorili slatkiše ovdje. 1534 01:10:30,630 --> 01:10:34,030 1535 01:10:34,030 --> 01:10:35,150 Dakle, ovo pokazivač - 1536 01:10:35,150 --> 01:10:37,590 >> Publika: Da, trebali sada se upućuju na slatkiše. 1537 01:10:37,590 --> 01:10:40,580 Tada su pokazivač iz candy točka na bundeve. 1538 01:10:40,580 --> 01:10:43,140 1539 01:10:43,140 --> 01:10:44,560 >> JASON Hirschhorna: Kao ovo? 1540 01:10:44,560 --> 01:10:47,380 I kažu mi imamo još jedan stvar mapirati na nulu? 1541 01:10:47,380 --> 01:10:48,660 >> Ivanković: Pa, vi samo učiniti istu stvar? 1542 01:10:48,660 --> 01:10:50,290 >> JASON Hirschhorna: Da li ista stvar. 1543 01:10:50,290 --> 01:10:53,700 Dakle, u ovom slučaju, ako to ne učinimo želim ga zadržati ga razvrstani 1544 01:10:53,700 --> 01:10:55,270 Zvuči prilično jednostavna. 1545 01:10:55,270 --> 01:10:59,920 Mi se pokazivač u indeksom dao našoj hash funkciji. 1546 01:10:59,920 --> 01:11:03,830 Imamo tu točku na naše nove čvora. 1547 01:11:03,830 --> 01:11:07,830 A onda je sve što je pokazivao ranije - 1548 01:11:07,830 --> 01:11:10,620 u ovom slučaju null, u Drugi slučaj bundeve - 1549 01:11:10,620 --> 01:11:15,310 da, bez obzira na to što ukazuje na ranije, dodamo u najbližu 1550 01:11:15,310 --> 01:11:17,810 naš novi čvor. 1551 01:11:17,810 --> 01:11:19,650 Mi smo nešto umetanja u početku. 1552 01:11:19,650 --> 01:11:22,900 U stvari je to puno jednostavnije nego pokušavajući zadržati popis sortiran. 1553 01:11:22,900 --> 01:11:25,340 Ali opet, u potrazi će biti složeniji ovdje. 1554 01:11:25,340 --> 01:11:28,300 Uvijek ćemo morati ići do kraja. 1555 01:11:28,300 --> 01:11:29,650 >> OK. 1556 01:11:29,650 --> 01:11:32,750 Sva pitanja o zasebnom ulančavanje? 1557 01:11:32,750 --> 01:11:34,690 Kako se to radi? 1558 01:11:34,690 --> 01:11:35,820 Molimo pitajte ih sada. 1559 01:11:35,820 --> 01:11:39,260 Stvarno želim da biste bili sigurni da svi Razumijem to, prije nego što krenete. 1560 01:11:39,260 --> 01:11:48,410 1561 01:11:48,410 --> 01:11:52,060 >> Ivanković: Zašto ste stavili bundevu i bombona u isto 1562 01:11:52,060 --> 01:11:54,108 dio hash tablice? 1563 01:11:54,108 --> 01:11:55,860 >> JASON Hirschhorna: Dobro pitanje. 1564 01:11:55,860 --> 01:11:59,140 Zašto smo ih staviti u isti dio hash tablice? 1565 01:11:59,140 --> 01:12:03,200 Pa, u tom slučaju naš hash funkcija se vraća na nulu za obojicu. 1566 01:12:03,200 --> 01:12:05,310 Zato što im je potrebno ići na nulu indeksom , jer je to mjesto gdje ćemo 1567 01:12:05,310 --> 01:12:07,420 potražite ih ako mi ikada želim ih gledati. 1568 01:12:07,420 --> 01:12:11,750 Opet, s linearnim pristupom sondiranja ne bismo ih stavili i na nulu. 1569 01:12:11,750 --> 01:12:13,900 No, u odvojenom lanca pristupa, ćemo ih i na nulu 1570 01:12:13,900 --> 01:12:16,620 a zatim napraviti popis od od nule. 1571 01:12:16,620 --> 01:12:20,140 >> A mi ne želimo da se prebrisati bundeve samo za to, jer onda ćemo 1572 01:12:20,140 --> 01:12:21,860 Pretpostavljamo da je bundeva Nikada umetnuta. 1573 01:12:21,860 --> 01:12:25,230 Ako smo samo zadržati jednu stvar u mjesto koje bi bilo loše. 1574 01:12:25,230 --> 01:12:28,590 Tada ne bi bilo šanse od nas ikad - 1575 01:12:28,590 --> 01:12:31,660 Ako smo ikada imali duplikat, onda smo samo bi izbrisali našu početnu vrijednost. 1576 01:12:31,660 --> 01:12:34,090 Dakle, to je razlog zašto smo napraviti ovaj pristup. 1577 01:12:34,090 --> 01:12:36,580 Ili je to razlog zašto smo izabrali - ali opet, mi izabrao poseban ulančavanje pristup, 1578 01:12:36,580 --> 01:12:39,670 koji postoje mnogi drugi pristupi nije mogao birati. 1579 01:12:39,670 --> 01:12:41,185 Je li to odgovor na vaše pitanje? 1580 01:12:41,185 --> 01:12:41,660 >> OK. 1581 01:12:41,660 --> 01:12:42,910 Carlos. 1582 01:12:42,910 --> 01:12:46,130 1583 01:12:46,130 --> 01:12:47,720 Linearni sondiranje će uključivati ​​- 1584 01:12:47,720 --> 01:12:51,913 ako smo našli sudar na nuli, mi će izgledati u sljedećem licu mjesta kako bi vidjeli je li 1585 01:12:51,913 --> 01:12:54,310 to je bio otvoren i staviti ga tamo. 1586 01:12:54,310 --> 01:12:57,320 I onda gledamo u sljedećem sportu i vidjeti ako to je bio otvoren i staviti ga tamo. 1587 01:12:57,320 --> 01:12:59,780 Tako ćemo naći sljedeći slobodni otvoren mjesto i staviti ga tamo. 1588 01:12:59,780 --> 01:13:02,580 1589 01:13:02,580 --> 01:13:03,890 Bilo koja druga pitanja? 1590 01:13:03,890 --> 01:13:05,370 Da, Avi. 1591 01:13:05,370 --> 01:13:07,490 >> PUBLIKA: Kao nastavak na to, Što misliš sljedećem licu mjesta? 1592 01:13:07,490 --> 01:13:10,250 U hash tablicu ili na popisu povezane. 1593 01:13:10,250 --> 01:13:12,100 >> JASON Hirschhorna: Za linearne programiranje, nema povezane liste. 1594 01:13:12,100 --> 01:13:13,400 Sljedeći mjesto na hash tablicu. 1595 01:13:13,400 --> 01:13:13,820 >> Ivanković: U redu. 1596 01:13:13,820 --> 01:13:17,570 Dakle hash tablica će biti inicijalizira na veličinu - 1597 01:13:17,570 --> 01:13:19,560 kao broj nizova da li su umetanjem? 1598 01:13:19,560 --> 01:13:22,170 >> JASON Hirschhorna: ti bi želim da to bude stvarno velika. 1599 01:13:22,170 --> 01:13:23,910 Da. 1600 01:13:23,910 --> 01:13:27,900 Ovdje je slika onoga što smo Upravo je nacrtao na ploči. 1601 01:13:27,900 --> 01:13:29,470 Opet, imamo sudar upravo ovdje. 1602 01:13:29,470 --> 01:13:30,710 na 152. 1603 01:13:30,710 --> 01:13:33,570 I vidjet ćete da je stvorio povezani Popis izvan nje. 1604 01:13:33,570 --> 01:13:38,200 1605 01:13:38,200 --> 01:13:41,850 Opet, hash tablicu zasebna ulančavanje pristup nije ona koju 1606 01:13:41,850 --> 01:13:45,590 morati uzeti za set problemi šest, ali je onaj koji puno 1607 01:13:45,590 --> 01:13:47,100 studenti imaju tendenciju da se. 1608 01:13:47,100 --> 01:13:51,140 Dakle, na to, idemo ukratko razgovarati Prije nego što krenete o problemu šest, 1609 01:13:51,140 --> 01:13:52,160 a onda ću podijeliti priču s vama. 1610 01:13:52,160 --> 01:13:55,120 Imamo tri minute. 1611 01:13:55,120 --> 01:13:55,750 >> Problem postaviti šest. 1612 01:13:55,750 --> 01:13:57,790 Imate četiri funkcije - 1613 01:13:57,790 --> 01:14:02,430 opterećenja, ček, veličina, i rasteretiti. 1614 01:14:02,430 --> 01:14:03,380 Load - 1615 01:14:03,380 --> 01:14:07,120 Pa, mi smo bili ide tijekom opterećenja tek sada. 1616 01:14:07,120 --> 01:14:09,330 Mi nacrtao teret na brodu. 1617 01:14:09,330 --> 01:14:13,230 A mi ni počeo kodiranja puno umetanje u popis povezane. 1618 01:14:13,230 --> 01:14:18,020 Dakle opterećenje ne mnogo više od ono što smo upravo radili. 1619 01:14:18,020 --> 01:14:21,070 >> Provjerite je nakon što su nešto učita. 1620 01:14:21,070 --> 01:14:22,580 To je isti proces kao ovaj. 1621 01:14:22,580 --> 01:14:26,845 Isti prva dva dijela gdje se bacaju nešto u hash funkcije 1622 01:14:26,845 --> 01:14:29,190 i dobiti svoju vrijednost. 1623 01:14:29,190 --> 01:14:30,700 Ali, sada nam nije umetnuti. 1624 01:14:30,700 --> 01:14:33,350 Sada smo u potrazi za njom. 1625 01:14:33,350 --> 01:14:37,130 Imam uzorak kod napisan za pronalaženje nešto u popisu povezana. 1626 01:14:37,130 --> 01:14:38,250 Ohrabrujem vas da praksa da. 1627 01:14:38,250 --> 01:14:43,000 Ali intuitivno pronalaženje nešto je prilično sličan umetanja nešto. 1628 01:14:43,000 --> 01:14:46,540 Doista, došli smo sliku o pronalaženju nešto u popisu povezanom, kreće 1629 01:14:46,540 --> 01:14:48,910 kroz sve što je dobio na kraju. 1630 01:14:48,910 --> 01:14:52,430 A ako je dobio na kraju i nije mogao ga naći, onda to ne postoji. 1631 01:14:52,430 --> 01:14:55,400 Tako da je ček, u biti. 1632 01:14:55,400 --> 01:14:57,030 >> Sljedeća je veličina. 1633 01:14:57,030 --> 01:14:57,910 Idemo preskočiti veličinu. 1634 01:14:57,910 --> 01:15:00,040 Konačno ste iskrcati. 1635 01:15:00,040 --> 01:15:02,890 Iskrcati jedan nismo izvučeni na brodu ili još kodirane. 1636 01:15:02,890 --> 01:15:05,990 No, ja Vam savjetujemo da pokušate to kodiranja u našem uzorka povezane s popisom primjer. 1637 01:15:05,990 --> 01:15:11,440 Ali iskrcati intuitivno sličan je besplatno - 1638 01:15:11,440 --> 01:15:14,010 ili mislim slična provjeriti. 1639 01:15:14,010 --> 01:15:17,350 Osim za sada svaki put idete putem, niste jednostavno provjerite da 1640 01:15:17,350 --> 01:15:19,090 vidjeti ako imate svoju vrijednost postoji. 1641 01:15:19,090 --> 01:15:22,490 Ali ste uzimajući da je čvor i ga osloboditi, u biti. 1642 01:15:22,490 --> 01:15:23,610 To je ono što ste izvadili pita za napraviti. 1643 01:15:23,610 --> 01:15:24,670 Besplatno je sve što ste malloced. 1644 01:15:24,670 --> 01:15:27,480 Tako da ideš kroz cijeli popis opet, prolazi kroz cijelu mljeveno meso 1645 01:15:27,480 --> 01:15:27,760 Tablica opet. 1646 01:15:27,760 --> 01:15:29,240 Ovaj put ne provjerite vidjeti što je tamo. 1647 01:15:29,240 --> 01:15:31,080 Samo osloboditi onoga što je tamo. 1648 01:15:31,080 --> 01:15:33,260 >> I na kraju veličina. 1649 01:15:33,260 --> 01:15:34,350 Veličina trebao biti proveden. 1650 01:15:34,350 --> 01:15:35,590 Ako ne provede veličinu - 1651 01:15:35,590 --> 01:15:36,250 Ja ću reći ovako. 1652 01:15:36,250 --> 01:15:39,740 Ako ne provede veličinu u točno jedna linija koda, uključujući 1653 01:15:39,740 --> 01:15:43,760 vratiti izjavu, koju su radi veličine pogrešno. 1654 01:15:43,760 --> 01:15:47,170 Na taj način osigurati veličinu, za puni dizajn boda, radite to u točno jednom 1655 01:15:47,170 --> 01:15:49,970 linija koda, uključujući Izjava povratak. 1656 01:15:49,970 --> 01:15:52,450 >> I ne spakirati još, Akchar. 1657 01:15:52,450 --> 01:15:53,700 Željni dabar. 1658 01:15:53,700 --> 01:15:55,820 1659 01:15:55,820 --> 01:16:01,300 Htio sam reći hvala vam dečki za dolazak na dijelu. 1660 01:16:01,300 --> 01:16:02,550 Imati sretan Halloween. 1661 01:16:02,550 --> 01:16:05,300 1662 01:16:05,300 --> 01:16:05,960 Ovo je moj kostim. 1663 01:16:05,960 --> 01:16:08,850 Ja ću se nositi ovo u četvrtak ako sam vas vidjeti u uredovno vrijeme. 1664 01:16:08,850 --> 01:16:14,640 A ako ste znatiželjni o tome nešto više pozadina kao da taj kostim, osjećam 1665 01:16:14,640 --> 01:16:19,135 slobodno provjeriti 2011 Odjel za priču o tome zašto sam 1666 01:16:19,135 --> 01:16:20,900 nosio kostim bundeve. 1667 01:16:20,900 --> 01:16:23,680 I to je tužna priča. 1668 01:16:23,680 --> 01:16:27,050 Dakle, pobrinite se da imate neki tkiva u blizini. 1669 01:16:27,050 --> 01:16:28,680 No, na to, ako imate bilo Pitanja ću staviti oko 1670 01:16:28,680 --> 01:16:29,960 izvan nakon dijelu. 1671 01:16:29,960 --> 01:16:31,510 Sretno na problemu postaviti šest. 1672 01:16:31,510 --> 01:16:33,540 I kao i uvijek, ako imate bilo pitanja, javite mi. 1673 01:16:33,540 --> 01:16:35,584