1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> ZVUČNI 1: U redu, tako da smo se vratiti. 3 00:00:13,120 --> 00:00:14,480 Dobrodošli na CS50. 4 00:00:14,480 --> 00:00:16,510 Ovo je kraj tjedna sedam. 5 00:00:16,510 --> 00:00:20,200 Dakle podsjetiti da je posljednji put, počeli smo gleda na nešto sofisticiraniji 6 00:00:20,200 --> 00:00:21,100 strukture podataka. 7 00:00:21,100 --> 00:00:25,110 Budući da do sada, sve što smo imali jako na raspolaganju je to, niz. 8 00:00:25,110 --> 00:00:29,340 >> No, prije nego što bacite niz kako ne sve što je zanimljivo, što doista 9 00:00:29,340 --> 00:00:33,570 zapravo, ono što su neke od pluses ove jednostavne podataka 10 00:00:33,570 --> 00:00:34,560 struktura do sada? 11 00:00:34,560 --> 00:00:36,110 Što je to dobro? 12 00:00:36,110 --> 00:00:39,450 Do sada kao što smo vidjeli? 13 00:00:39,450 --> 00:00:42,540 Što ti imaš? 14 00:00:42,540 --> 00:00:44,028 Ništa. 15 00:00:44,028 --> 00:00:45,020 >> STUDENT: [nečujno]. 16 00:00:45,020 --> 00:00:45,395 >> ZVUČNI 1: Što je to? 17 00:00:45,395 --> 00:00:46,410 >> STUDENT: [nečujno]. 18 00:00:46,410 --> 00:00:47,000 >> ZVUČNI 1: Fiksna veličina. 19 00:00:47,000 --> 00:00:51,260 OK, pa zašto je fiksna veličina dobro ipak? 20 00:00:51,260 --> 00:00:53,180 >> STUDENT: [nečujno]. 21 00:00:53,180 --> 00:00:56,240 >> ZVUČNI 1: U redu, tako da je učinkovita u Osjećaj da mogu izdvojiti 22 00:00:56,240 --> 00:01:00,070 Fiksni iznos prostora, koji će, nadamo Upravo onoliko koliko 23 00:01:00,070 --> 00:01:01,180 Prostor kao što želite. 24 00:01:01,180 --> 00:01:02,720 Tako da bi mogao biti apsolutno plus. 25 00:01:02,720 --> 00:01:06,530 >> Što je još gore strana niz? 26 00:01:06,530 --> 00:01:07,610 Da? 27 00:01:07,610 --> 00:01:08,750 >> STUDENT: [nečujno]. 28 00:01:08,750 --> 00:01:09,550 >> ZVUČNI 1: All - žao? 29 00:01:09,550 --> 00:01:11,270 >> STUDENT: [nečujno]. 30 00:01:11,270 --> 00:01:13,620 >> ZVUČNI 1: Svi su kutije u memoriji ili jedna pored druge. 31 00:01:13,620 --> 00:01:15,220 I to je korisno - zašto? 32 00:01:15,220 --> 00:01:15,970 To je sasvim točno. 33 00:01:15,970 --> 00:01:18,611 Ali kako možemo iskoristiti tu istinu? 34 00:01:18,611 --> 00:01:21,500 >> STUDENT: [nečujno]. 35 00:01:21,500 --> 00:01:24,490 >> ZVUČNI 1: Točno, možemo pratiti gdje je sve samo znajući 36 00:01:24,490 --> 00:01:28,560 Prva adresa, odnosno adresa Prvi bajt taj komad memorije. 37 00:01:28,560 --> 00:01:30,420 Ili u slučaju niza, adresa prva 38 00:01:30,420 --> 00:01:31,460 char u tom nizu. 39 00:01:31,460 --> 00:01:33,330 A od tamo, možemo naći kraj niza. 40 00:01:33,330 --> 00:01:35,710 Možemo pronaći drugi element, Treći element, i tako dalje. 41 00:01:35,710 --> 00:01:38,740 >> I tako fancy način opisuje kako značajka je da nizovi nam 42 00:01:38,740 --> 00:01:40,020 s izravnim pristupom. 43 00:01:40,020 --> 00:01:44,330 Samo pomoću uglata zagrada oznake i broj, možete prijeći na 44 00:01:44,330 --> 00:01:48,070 određeni element u polju u konstantnom vremenu, big O 45 00:01:48,070 --> 00:01:49,810 jedne, da tako kažem. 46 00:01:49,810 --> 00:01:51,080 >> No, tu nije bilo neke mane. 47 00:01:51,080 --> 00:01:53,110 Što polje ne učiniti vrlo jednostavno? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Što je to nije dobro? 50 00:01:57,170 --> 00:01:58,810 >> STUDENT: [nečujno]. 51 00:01:58,810 --> 00:01:59,860 >> ZVUČNI 1: Što je to? 52 00:01:59,860 --> 00:02:00,530 >> STUDENT: [nečujno]. 53 00:02:00,530 --> 00:02:01,460 >> ZVUČNI 1: Širenje u veličini. 54 00:02:01,460 --> 00:02:04,800 Tako su Nedostaci polja su Upravo suprotno od onoga 55 00:02:04,800 --> 00:02:05,540 upsides se. 56 00:02:05,540 --> 00:02:07,610 Pa je jedan od nedostataka je da je fiksna veličina. 57 00:02:07,610 --> 00:02:09,400 Tako da stvarno ne mogu ga rastu. 58 00:02:09,400 --> 00:02:13,510 Možete preraspodijeliti veći komad memorije, a zatim premjestiti staru elemente 59 00:02:13,510 --> 00:02:14,460 u novi niz. 60 00:02:14,460 --> 00:02:18,060 A onda bez stara polje, za Primjerice, pomoću malloc ili sličnu 61 00:02:18,060 --> 00:02:21,180 Funkcija zove realloc, koji reallocates pamćenje. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, kao stranu, pokušava dobiti memorije koja je pored niza 63 00:02:25,490 --> 00:02:26,610 koje već imate. 64 00:02:26,610 --> 00:02:28,740 No, to bi moglo premjestiti stvari oko uopce. 65 00:02:28,740 --> 00:02:30,710 No, ukratko, to je skupo, zar ne? 66 00:02:30,710 --> 00:02:33,440 Jer, ako imate komad memorije ove veličine, ali stvarno želite jedan 67 00:02:33,440 --> 00:02:36,710 ove veličine, a vi želite sačuvati izvorni elementi, imate 68 00:02:36,710 --> 00:02:40,510 otprilike linearno vrijeme kopiranja koji se treba dogoditi s 69 00:02:40,510 --> 00:02:41,900 stara polje za novo. 70 00:02:41,900 --> 00:02:44,630 A stvarnost je molba operativnog Sustav opet i opet i 71 00:02:44,630 --> 00:02:48,340 opet za velike komade memorije može početi na trošak vam neko vrijeme kao dobro. 72 00:02:48,340 --> 00:02:52,250 Tako da je i blagoslov i prokletstvo u prikrilo, činjenicu da ti nizovi 73 00:02:52,250 --> 00:02:53,860 su fiksne veličine. 74 00:02:53,860 --> 00:02:56,790 Ali ako ćemo predstaviti nešto umjesto kao što je ovaj, koji smo nazvali linked 75 00:02:56,790 --> 00:03:00,580 Popis smo dobili nekoliko odlika i nekoliko loših strana i ovdje. 76 00:03:00,580 --> 00:03:05,780 >> Tako povezani popis je jednostavno podataka Struktura se sastoji od C tvorevina, u ovom 77 00:03:05,780 --> 00:03:09,850 slučaj, gdje je rekonstruirati, podsjetimo, samo je Spremnik jedne ili više specifičnih 78 00:03:09,850 --> 00:03:11,100 vrste varijabli. 79 00:03:11,100 --> 00:03:16,110 U ovom slučaju, ono što učinite vrste podataka Čini se da unutar struct da 80 00:03:16,110 --> 00:03:17,600 Posljednji put smo se naziva čvor? 81 00:03:17,600 --> 00:03:19,380 Svaka od tih pravokutnika je čvor. 82 00:03:19,380 --> 00:03:22,660 I svaki od manjih pravokutnika unutar nje je tip podataka. 83 00:03:22,660 --> 00:03:25,300 Koje vrste nije kažemo su u ponedjeljak? 84 00:03:25,300 --> 00:03:26,478 Da? 85 00:03:26,478 --> 00:03:27,870 >> STUDENT: [nečujno]. 86 00:03:27,870 --> 00:03:30,721 >> ZVUČNI 1: promjenjiva i pokazivač, ili točnije, int, za n, 87 00:03:30,721 --> 00:03:32,180 i kazaljke na dnu. 88 00:03:32,180 --> 00:03:35,360 Obje od onih dogoditi da se 32 bita, na Barem na računalu kao što je ovaj CS50 89 00:03:35,360 --> 00:03:37,980 Appliance, i tako su izvučeni podjednako u veličini. 90 00:03:37,980 --> 00:03:42,260 >> Dakle, ono što su pomoću pokazivača iako za očito? 91 00:03:42,260 --> 00:03:47,690 Zašto dodali ovaj strelicu sada kad su nizovi tako lijepo i čisto i jednostavno? 92 00:03:47,690 --> 00:03:50,460 Što je pokazivač radi za nas u svakom od tih čvorova? 93 00:03:50,460 --> 00:03:52,160 >> STUDENT: [nečujno]. 94 00:03:52,160 --> 00:03:52,465 >> ZVUČNI 1: Točno. 95 00:03:52,465 --> 00:03:54,120 To vam reći gdje je Sljedeći je. 96 00:03:54,120 --> 00:03:57,350 Tako sam vrsta koristiti analogiju koristite konac za sortiranje mjesta 97 00:03:57,350 --> 00:03:59,180 nit tih čvorova zajedno. 98 00:03:59,180 --> 00:04:01,760 A to je upravo ono što mi radimo s pokazivače jer svaki od tih 99 00:04:01,760 --> 00:04:06,360 komadi memorije ne mogu ili mogu biti susjednih, vratio se natrag na leđa 100 00:04:06,360 --> 00:04:09,500 unutar RAM-a, jer svaki put kad poziva malloc govoreći, daj mi dovoljno 101 00:04:09,500 --> 00:04:12,510 bajtova za novi čvor, to bi moglo biti ovdje i to bi moglo biti ovdje. 102 00:04:12,510 --> 00:04:13,120 To bi moglo biti ovdje. 103 00:04:13,120 --> 00:04:13,730 To bi moglo biti ovdje. 104 00:04:13,730 --> 00:04:14,640 Vi jednostavno ne razumijete. 105 00:04:14,640 --> 00:04:17,880 >> No, korištenje pokazivača na adrese ti čvorovi, možete ih bod 106 00:04:17,880 --> 00:04:22,370 zajedno na način koji izgleda vizualno kao popis, čak i ako su te stvari 107 00:04:22,370 --> 00:04:26,770 Svi raširi cijelom jednom ili Vaši dvije ili četiri svoje gigabajta RAM-a 108 00:04:26,770 --> 00:04:28,760 unutar svoje računalo. 109 00:04:28,760 --> 00:04:33,230 >> Dakle downside, a zatim, povezani popis je ono? 110 00:04:33,230 --> 00:04:34,670 Što je cijena koju smo očito plaćati? 111 00:04:34,670 --> 00:04:36,010 >> STUDENT: [nečujno]. 112 00:04:36,010 --> 00:04:36,920 >> ZVUČNI 1: Više mjesta, zar ne? 113 00:04:36,920 --> 00:04:39,340 Mi smo, u ovom slučaju, udvostručen je iznos prostora jer smo otišli 114 00:04:39,340 --> 00:04:43,500 od 32 bita za svaki čvor, za svaku int, tako da sada 64 bita, jer moramo 115 00:04:43,500 --> 00:04:45,050 držati oko pokazivača kao dobro. 116 00:04:45,050 --> 00:04:48,860 Možete dobiti više učinkovitosti ako vaš struct je veća od ove jednostavne stvari. 117 00:04:48,860 --> 00:04:52,020 Ako doista imate studenta unutar od kojih je nekoliko nizova za 118 00:04:52,020 --> 00:04:55,430 Ime i kuća, možda i ID broj, možda i neke druge stavke uopce. 119 00:04:55,430 --> 00:04:59,000 >> Dakle, ako imate dovoljno veliku struct, onda možda cijena od pokazivačem 120 00:04:59,000 --> 00:05:00,010 nije tako velika stvar. 121 00:05:00,010 --> 00:05:03,570 To je malo kornera u slučaju da je mi smo pohranu, kao jednostavna primitivna 122 00:05:03,570 --> 00:05:04,760 unutar povezanoj popisa. 123 00:05:04,760 --> 00:05:05,790 Ali stvar je ista. 124 00:05:05,790 --> 00:05:08,230 Ti si definitivno troše više memorije, ali ste dobivanje 125 00:05:08,230 --> 00:05:08,990 fleksibilnost. 126 00:05:08,990 --> 00:05:12,280 Jer sad ako želim dodati element na početku ovog popisa 127 00:05:12,280 --> 00:05:14,340 Moram izdvojiti novi čvor. 128 00:05:14,340 --> 00:05:17,180 I moram samo ažurirati onima Strelice nekako samo pomicanjem 129 00:05:17,180 --> 00:05:17,980 neke naputke oko. 130 00:05:17,980 --> 00:05:20,580 >> Ako želim da ubacite nešto u sredinu ljestvice, ja ne moram 131 00:05:20,580 --> 00:05:24,410 gurati sve na stranu kao što smo učinili u Posljednjih tjedana s našim volonterima koji su 132 00:05:24,410 --> 00:05:25,700 predstavljao niz. 133 00:05:25,700 --> 00:05:29,470 Ja samo mogu izdvojiti novi čvor i onda samo ukazati na strelice u 134 00:05:29,470 --> 00:05:32,290 različitim smjerovima, jer ona ne moraju ostati u stvarni 135 00:05:32,290 --> 00:05:35,670 memorije istina linije kao da sam nacrtana je ovdje na zaslonu. 136 00:05:35,670 --> 00:05:38,400 >> I onda na kraju, ako želite umetnuti nešto na kraju popisa, to je 137 00:05:38,400 --> 00:05:39,210 čak i lakše. 138 00:05:39,210 --> 00:05:43,320 To je vrsta proizvoljnog zapisu, ali 34 je pointer, uzeti pogodak. 139 00:05:43,320 --> 00:05:46,710 Što je vrijednost njegove pokazivač najviše vjerojatno izvući nešto kao stara 140 00:05:46,710 --> 00:05:47,700 Škola ima antenu? 141 00:05:47,700 --> 00:05:48,920 >> STUDENT: [nečujno]. 142 00:05:48,920 --> 00:05:49,900 >> ZVUČNI 1: To je vjerojatno null. 143 00:05:49,900 --> 00:05:52,710 I doista, to je jedna autora zastupljenost null. 144 00:05:52,710 --> 00:05:56,310 A to je zato što apsolutno null morate znati gdje je kraj linked 145 00:05:56,310 --> 00:06:00,050 Popis je, da ne bi i sljedeće slijedi i nakon ove strelice 146 00:06:00,050 --> 00:06:01,170 na neko smeće vrijednosti. 147 00:06:01,170 --> 00:06:06,230 Dakle null će značiti da ne postoji više čvorova desno od broja 34, 148 00:06:06,230 --> 00:06:07,200 u ovom slučaju. 149 00:06:07,200 --> 00:06:10,270 >> Dakle, mi predlažemo da možemo provesti ovaj čvor u kodu. 150 00:06:10,270 --> 00:06:12,130 I mi smo vidjeli ovakvu sintakse prije. 151 00:06:12,130 --> 00:06:15,090 Typedef jednostavno definira novi tip za nas, daje nam sinonim kao što je 152 00:06:15,090 --> 00:06:17,100 string je za char *. 153 00:06:17,100 --> 00:06:21,030 U ovom slučaju, to će nam dati stenogram notacija kako struct node 154 00:06:21,030 --> 00:06:24,010 može umjesto toga samo se zapisati kao čvor, što je mnogo čistiji. 155 00:06:24,010 --> 00:06:25,360 To je puno manje rječit. 156 00:06:25,360 --> 00:06:30,080 >> Unutar od čvora je očito int pod nazivom n, a zatim struct čvor * 157 00:06:30,080 --> 00:06:34,670 što znači da je točno ono što smo htjeli strelice značiti, pokazivač na drugo 158 00:06:34,670 --> 00:06:36,940 čvor isti tip podataka. 159 00:06:36,940 --> 00:06:40,300 I sam predložio da smo mogli provesti Nova funkcija kao što je ovaj, koji je u 160 00:06:40,300 --> 00:06:41,890 prvi pogled može činiti malo složeniji. 161 00:06:41,890 --> 00:06:43,330 No, da vidimo što se u kontekstu. 162 00:06:43,330 --> 00:06:45,480 >> Pusti me preko aparata ovdje. 163 00:06:45,480 --> 00:06:48,460 Dopustite mi otvoriti datoteku pod nazivom Popis nula dot h. 164 00:06:48,460 --> 00:06:53,950 I to samo da sadrži definiciju mi Vidjela sam maloprije za ove podatke 165 00:06:53,950 --> 00:06:55,390 Vrsta naziva čvor. 166 00:06:55,390 --> 00:06:57,350 Tako smo stavili da je u datoteku dot h. 167 00:06:57,350 --> 00:07:01,430 >> I kao na stranu, iako to program koji ste upravo vidjeti je 168 00:07:01,430 --> 00:07:05,410 nije sve što je složeno, to je istina Konvencija prilikom pisanja programa 169 00:07:05,410 --> 00:07:10,270 staviti stvari kao što su vrste podataka, da će se povući Konstante ponekad, unutar vašeg 170 00:07:10,270 --> 00:07:13,210 header file, a ne nužno u Vaš C datoteku, osobito kad vaše 171 00:07:13,210 --> 00:07:17,370 Programi dobiti veći i veći, tako da je znate gdje se mogu pogledati i za 172 00:07:17,370 --> 00:07:20,840 Dokumentacija u nekim slučajevima, ili za osnove kao što su to, 173 00:07:20,840 --> 00:07:22,360 definicija nekog tipa. 174 00:07:22,360 --> 00:07:25,680 >> Ako ja sada otvoriti popis nultu točku c, primijetiti nekoliko stvari. 175 00:07:25,680 --> 00:07:29,090 On uključuje nekoliko zaglavlje datoteke, najviše koje smo vidjeli prije. 176 00:07:29,090 --> 00:07:31,980 To uključuje vlastiti zaglavlje datoteke. 177 00:07:31,980 --> 00:07:35,200 >> I kao stranu, zašto je to bračni citati ovdje, za razliku od kuta 178 00:07:35,200 --> 00:07:38,340 nosači na liniju koja Ja sam istaknuo postoji? 179 00:07:38,340 --> 00:07:39,180 >> STUDENT: [nečujno]. 180 00:07:39,180 --> 00:07:40,460 >> ZVUČNI 1: Da, tako je lokalna datoteka. 181 00:07:40,460 --> 00:07:44,300 Dakle, ako je lokalni file od vlastite ovdje na liniji 15, primjerice, koristite 182 00:07:44,300 --> 00:07:46,570 dvostruke navodnike umjesto od kutnih zagrada. 183 00:07:46,570 --> 00:07:48,270 >> Sada je to vrsta zanimljiva. 184 00:07:48,270 --> 00:07:51,830 Obavijest da sam proglasio globalnom varijabla u ovom programu na liniji 18 185 00:07:51,830 --> 00:07:55,910 Prvi se zove, ideja da je ovo će biti pointer na prvi 186 00:07:55,910 --> 00:07:59,190 čvor u mom povezanom popisu, a ja sam inicijaliziraju se na nulu, jer sam 187 00:07:59,190 --> 00:08:02,310 Nije bilo dodijeljeno stvarna čvorovi samo još. 188 00:08:02,310 --> 00:08:07,570 >> Dakle, to predstavlja, slikovito, ono što smo Vidio maloprije na slici kao 189 00:08:07,570 --> 00:08:10,090 da je kazaljka na daleko lijevoj strani. 190 00:08:10,090 --> 00:08:12,260 Pa sad, da pokazivač nema strijelu. 191 00:08:12,260 --> 00:08:14,590 Ona umjesto da je samo null. 192 00:08:14,590 --> 00:08:17,880 No, on predstavlja ono što će biti adresa prva stvarna 193 00:08:17,880 --> 00:08:19,480 čvor u ovom popisu. 194 00:08:19,480 --> 00:08:22,120 Tako sam implementiran je globalni jer, kao što ćete vidjeti, sve ovo 195 00:08:22,120 --> 00:08:25,310 Program se provodi u životu povezani popis za mene. 196 00:08:25,310 --> 00:08:27,050 >> Sada sam dobio nekoliko prototipova ovdje. 197 00:08:27,050 --> 00:08:31,190 Odlučio sam provesti značajke kao što su brisanje, umetanje, pretraživanje i 198 00:08:31,190 --> 00:08:31,740 obuhvaćanje - 199 00:08:31,740 --> 00:08:35,210 Posljednji samo kao šetnja Popis, ispis njene elemente. 200 00:08:35,210 --> 00:08:36,750 A sad evo moj glavni rutinu. 201 00:08:36,750 --> 00:08:39,890 I nećemo trošiti previše vremena na to jer je to vrsta, nadamo 202 00:08:39,890 --> 00:08:41,780 stari šešir do sada. 203 00:08:41,780 --> 00:08:45,370 >> Ja ću učiniti sljedeće, dok je korisnik surađuje. 204 00:08:45,370 --> 00:08:47,300 Dakle, jednom, idem za ispis iz ovog izbornika. 205 00:08:47,300 --> 00:08:49,420 I ja sam ga oblikovati kao čisto kao što sam mogao. 206 00:08:49,420 --> 00:08:52,240 Ako korisnik upiše u jednoj, to znači da oni žele izbrisati nešto. 207 00:08:52,240 --> 00:08:54,560 Ako korisnik upiše u dva, to znači da oni žele staviti nešto. 208 00:08:54,560 --> 00:08:55,930 I tako dalje. 209 00:08:55,930 --> 00:08:58,270 Idem onda zatražiti onda za naredbe. 210 00:08:58,270 --> 00:08:59,300 A onda ću koristiti GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Dakle, ovo je stvarno jednostavan menuing sučelje gdje jednostavno morate tipkati 212 00:09:02,790 --> 00:09:05,270 broj preslikavanje jednog od tih naredbi. 213 00:09:05,270 --> 00:09:08,730 I sada imam lijep čist prekidač izjava da će se uključiti 214 00:09:08,730 --> 00:09:10,090 sve što korisnik unese 215 00:09:10,090 --> 00:09:12,180 A ako su upisali jedan, ja ću nazovite izbrisati i break. 216 00:09:12,180 --> 00:09:14,380 Ako su upisali dva, ja ću nazovite umetanje i break. 217 00:09:14,380 --> 00:09:16,490 >> I sad sam stavio obavijest jedni od ovih na istoj liniji. 218 00:09:16,490 --> 00:09:18,360 Ovo je samo stilska odluka. 219 00:09:18,360 --> 00:09:20,210 Obično smo vidjeli nešto kao što je ovaj. 220 00:09:20,210 --> 00:09:23,260 Ali sam odlučio da, iskreno rečeno, moj program Pogledao više čitati, jer 221 00:09:23,260 --> 00:09:25,980 to je bio samo četiri slučaja do samo ga navesti kao što je ovaj. 222 00:09:25,980 --> 00:09:28,360 Totalno legitimno korištenje stilu. 223 00:09:28,360 --> 00:09:31,480 I ja ću to učiniti, tako dugo dok korisnik nije upisali nulu, što sam 224 00:09:31,480 --> 00:09:33,910 odlučila će značiti žele prestati. 225 00:09:33,910 --> 00:09:36,630 >> Tako sada primijetiti što sam će to učiniti ovdje. 226 00:09:36,630 --> 00:09:38,650 Idem na slobodan popis očito. 227 00:09:38,650 --> 00:09:40,230 No, više o tome u samo trenutak. 228 00:09:40,230 --> 00:09:41,640 Neka prvi pokrenuti ovaj program. 229 00:09:41,640 --> 00:09:45,250 Pa neka mi napraviti veći terminal prozor, dot slash Lista 0. 230 00:09:45,250 --> 00:09:49,510 Ja ću ići naprijed i umetnite strane tipkanje dva, broj kao što je 50, a sada 231 00:09:49,510 --> 00:09:51,590 vidjet ćete popis je sada 50. 232 00:09:51,590 --> 00:09:53,380 I moj tekst jednostavno prebacite se malo. 233 00:09:53,380 --> 00:09:55,940 Tako sada primjetiti popis sadrži broj 50. 234 00:09:55,940 --> 00:09:58,220 >> Idemo napraviti još jedan umetak uzimanjem dva. 235 00:09:58,220 --> 00:10:01,630 Idemo upisati u broju kao jedan. 236 00:10:01,630 --> 00:10:03,940 Popis je sada jedan, nakon čega slijedi 50. 237 00:10:03,940 --> 00:10:06,020 Dakle, ovo je samo tekstualni prikaz popisa. 238 00:10:06,020 --> 00:10:10,550 I neka je umetnite još jedan broj kao broj 42, koji je izgledno 239 00:10:10,550 --> 00:10:14,620 će završiti u sredini, jer je Ovaj program posebno je vrsta 240 00:10:14,620 --> 00:10:16,320 elemente kao što im umetci. 241 00:10:16,320 --> 00:10:17,220 Tako da smo ga. 242 00:10:17,220 --> 00:10:20,730 Super jednostavan program koji bi mogao Apsolutno smo koristili niz, ali ja 243 00:10:20,730 --> 00:10:23,280 dogoditi da se pomoću povezanu popis samo tako mogu dinamički 244 00:10:23,280 --> 00:10:24,610 rasti i smanjivati. 245 00:10:24,610 --> 00:10:28,470 >> Tako ćemo pogledati za pretraživanje, ako sam pokrenuti naredbu tri, želim pretraživanje 246 00:10:28,470 --> 00:10:31,040 za, recimo, u broju 43. 247 00:10:31,040 --> 00:10:34,190 I ništa navodno je pronađena, jer sam dobio natrag nikakav odgovor. 248 00:10:34,190 --> 00:10:35,010 Tako ćemo to opet. 249 00:10:35,010 --> 00:10:35,690 Traži. 250 00:10:35,690 --> 00:10:39,520 Neka je potraga za 50, odnosno traženje u 42, koji ima nice 251 00:10:39,520 --> 00:10:40,850 malo suptilnije značenje. 252 00:10:40,850 --> 00:10:42,610 I sam pronašao smisao života tamo. 253 00:10:42,610 --> 00:10:44,990 Broj 42, ako ne znate reference, to Googleu. 254 00:10:44,990 --> 00:10:45,350 U redu. 255 00:10:45,350 --> 00:10:47,130 Dakle, ono što je ovaj program učinio za mene? 256 00:10:47,130 --> 00:10:50,660 To je samo dopustio da ubacite taj način daleko i potraga za elementima. 257 00:10:50,660 --> 00:10:53,650 >> Idemo brzo naprijed, a zatim, kako bi koji funkcioniraju smo pogledala 258 00:10:53,650 --> 00:10:55,360 u ponedjeljak je kao teaser. 259 00:10:55,360 --> 00:10:59,620 Dakle, ove funkcije, ja tvrdim, traži element u popisu tako da se prvo 260 00:10:59,620 --> 00:11:03,830 jedan, pitajući korisnika, a zatim pozivom GetInt doći do stvarnih int 261 00:11:03,830 --> 00:11:05,060 koju želite potražiti. 262 00:11:05,060 --> 00:11:06,460 >> Zatim primijetiti. 263 00:11:06,460 --> 00:11:10,690 Ja ću stvoriti privremenu varijablu u skladu 188. zove pokazivač - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 mogli su ga zvali ništa. 266 00:11:12,440 --> 00:11:16,140 I to je pointer na čvoru zato sam rekao čvora * postoji. 267 00:11:16,140 --> 00:11:19,900 I ja sam inicijalizacije da bude jednak prvi, tako da sam učinkovito imaju my 268 00:11:19,900 --> 00:11:22,860 prstom, da tako kažemo, na samom Prvi element popisa. 269 00:11:22,860 --> 00:11:27,460 Dakle, ako mi je desna ruka ovdje je PTR sam pokazujući na isto koji je prvi 270 00:11:27,460 --> 00:11:28,670 je pokazivao. 271 00:11:28,670 --> 00:11:31,430 >> Tako sada natrag u kodu, što će se dogoditi - 272 00:11:31,430 --> 00:11:35,070 to je čest paradigma kada iterating preko strukture kao 273 00:11:35,070 --> 00:11:35,970 povezani popis. 274 00:11:35,970 --> 00:11:40,410 Ja ću učiniti sljedeće dok Pokazivač nije jednak null Dakle, dok 275 00:11:40,410 --> 00:11:47,530 moj prst nije pokazivao neku null vrijednost, ako pointer strelica n jednak n. 276 00:11:47,530 --> 00:11:52,290 Mi ćemo primjetiti da je prvi n je ono korisnik upisao u po GetInts ovdje zovu. 277 00:11:52,290 --> 00:11:54,280 >> I pointer strelica n znači što? 278 00:11:54,280 --> 00:11:59,020 Pa ako se vratimo na slici ovdje, ako imam prst pokazujući na 279 00:11:59,020 --> 00:12:02,960 koji je prvi čvor koji sadrži devet, na Strelica u osnovi znači da je ići na 280 00:12:02,960 --> 00:12:08,860 čvora i iskoristite vrijednost na mjesto n, u ovom slučaju, polje podataka naziva n. 281 00:12:08,860 --> 00:12:14,120 >> Kao na stranu - a vidjeli smo ovaj par tjedana kada je netko pitao - 282 00:12:14,120 --> 00:12:18,840 Ova sintaksa je novo, ali to ne daj nam snage da mi 283 00:12:18,840 --> 00:12:20,040 nije već imate. 284 00:12:20,040 --> 00:12:25,325 Ono što je ovaj izraz jednak pomoću dot oznake i star par 285 00:12:25,325 --> 00:12:29,490 tjedana kada smo oguljen ovaj sloj malo prerano? 286 00:12:29,490 --> 00:12:31,780 >> STUDENT: [nečujno]. 287 00:12:31,780 --> 00:12:38,880 >> ZVUČNI 1: Točno, to je bio star, a onda bio star dot n, s 288 00:12:38,880 --> 00:12:41,930 zagrade ovdje, što izgleda, iskreno, mislim da je puno 289 00:12:41,930 --> 00:12:43,320 više zagonetan čitati. 290 00:12:43,320 --> 00:12:46,270 No zvijezda pointer, kao i uvijek, znači otići tamo. 291 00:12:46,270 --> 00:12:49,090 A kad ste tamo, koje podatke Polje želite pristupiti? 292 00:12:49,090 --> 00:12:52,730 Pa što koristite dot oznake za pristup Polje tvorevina podataka, i ja 293 00:12:52,730 --> 00:12:54,140 posebno želim n. 294 00:12:54,140 --> 00:12:56,240 >> Iskreno, ja bih rekao ovo samo je teže čitati. 295 00:12:56,240 --> 00:12:58,080 To je teže sjetiti gdje da su zagrade ide, 296 00:12:58,080 --> 00:12:59,030 zvijezda i sve to. 297 00:12:59,030 --> 00:13:02,150 Dakle, svijet donijela neke sintaktičke šećera, da se tako izrazim. 298 00:13:02,150 --> 00:13:04,740 Samo seksi način da se kaže, to je ekvivalent, a 299 00:13:04,740 --> 00:13:05,970 možda i intuitivnije. 300 00:13:05,970 --> 00:13:09,600 Ako je doista pointer pokazivač, strelica zapis znači otići tamo i naći 301 00:13:09,600 --> 00:13:11,890 polje u ovom slučaju zove n. 302 00:13:11,890 --> 00:13:13,660 >> Dakle, ako sam ga pronaći, primijetiti što mi je činiti. 303 00:13:13,660 --> 00:13:17,430 Ja jednostavno isprintati, otkrio sam posto, uključivanjem u vrijednosti za taj int. 304 00:13:17,430 --> 00:13:20,730 Pozivam spavati jednu sekundu samo da vrste pauze stvari na zaslonu za 305 00:13:20,730 --> 00:13:22,900 daju upute Drugi apsorbirati ono što se upravo dogodilo. 306 00:13:22,900 --> 00:13:24,290 A onda sam se probiti. 307 00:13:24,290 --> 00:13:26,330 Inače, što da radim? 308 00:13:26,330 --> 00:13:30,960 Ja ažurirali pokazivač na jednake Pokazivač strelicu pored. 309 00:13:30,960 --> 00:13:35,840 >> Dakle, samo da bude jasno, to znači ići postoji, koristeći moje stare škole zapis. 310 00:13:35,840 --> 00:13:39,580 Dakle, to samo znači da ide na sve što ste pokazujući na, koji je u vrlo 311 00:13:39,580 --> 00:13:43,660 Prvi slučaj je sam pokazujući na struct s devet u njemu. 312 00:13:43,660 --> 00:13:44,510 Tako sam otišao tamo. 313 00:13:44,510 --> 00:13:47,880 A onda dot oznake znači, dobili vrijednost na sljedeći. 314 00:13:47,880 --> 00:13:50,470 >> Ali vrijednost, iako je nacrtana kao uska, je samo broj. 315 00:13:50,470 --> 00:13:51,720 To je brojčana adresa. 316 00:13:51,720 --> 00:13:55,670 Dakle, ovo jedna linija koda, bilo napisano ovako više zagonetan 317 00:13:55,670 --> 00:14:00,190 način, ili kao što je ovaj, nešto više intuitivan način, samo znači mičem ruku 318 00:14:00,190 --> 00:14:03,460 od prvog čvora do sljedećeg, , a zatim sljedeći, a zatim 319 00:14:03,460 --> 00:14:05,320 Sljedeći jedan, i tako dalje. 320 00:14:05,320 --> 00:14:09,920 >> Tako nećemo razmišljati o drugima implementacije umetanje i brisanje 321 00:14:09,920 --> 00:14:14,030 i obuhvaćanje, prva dva od koji su prilično uključeni. 322 00:14:14,030 --> 00:14:17,010 I mislim da je to prilično lako dobiti izgubljen kada to rade verbalno. 323 00:14:17,010 --> 00:14:19,890 No, ono što možemo učiniti je da se ovdje pokušati utvrditi kako 324 00:14:19,890 --> 00:14:21,640 najbolje je to učiniti vizualno. 325 00:14:21,640 --> 00:14:24,800 Jer ja bih predložio da, ako smo želite umetnuti elemente u ovo 326 00:14:24,800 --> 00:14:26,680 postojeći popis, koji ima pet elemenata - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26, i 33 - 328 00:14:29,530 --> 00:14:33,300 ako su išli za provedbu ove u broj, moram razmisliti o tome kako ići 329 00:14:33,300 --> 00:14:34,160 o to. 330 00:14:34,160 --> 00:14:37,720 >> I ja bih predložio poduzimanje koraka beba pri čemu, u ovom slučaju mislim, ono se 331 00:14:37,720 --> 00:14:41,090 mogućih scenarija koji smo naići u cjelini? 332 00:14:41,090 --> 00:14:44,120 Pri provedbi umetak za linked Popis, to jednostavno dogodi da se 333 00:14:44,120 --> 00:14:46,090 specifičan primjer veličine pet. 334 00:14:46,090 --> 00:14:50,420 Pa ako želite umetnuti broj, vole reći broj jedan, a 335 00:14:50,420 --> 00:14:53,380 održavanje sortiraju bi, u kojoj Očito ne broj jedan morate 336 00:14:53,380 --> 00:14:55,686 ići u konkretnom primjeru? 337 00:14:55,686 --> 00:14:56,840 Na primjer na početku. 338 00:14:56,840 --> 00:15:00,030 >> No, ono što je zanimljivo je da je Ako želite umetnuti jedan u ovo 339 00:15:00,030 --> 00:15:04,100 Popis, ono treba posebna pointer biti ažurirana očito? 340 00:15:04,100 --> 00:15:04,610 Prvo. 341 00:15:04,610 --> 00:15:07,830 Dakle, ja bih rekao, ovo je prvi slučaj da smo možda želite uzeti u obzir, 342 00:15:07,830 --> 00:15:11,140 Scenarij uključuje ugurate početak popisa. 343 00:15:11,140 --> 00:15:15,400 >> Idemo ugrabiti off možda tako lako, pa čak i jednostavniji slučaj, relativno govoreći. 344 00:15:15,400 --> 00:15:18,110 Pretpostavimo da želite umetnuti Broj 35 u sortiraju bi. 345 00:15:18,110 --> 00:15:20,600 Očito spada tamo. 346 00:15:20,600 --> 00:15:25,320 Dakle, ono što je očito pokazivač će moraju biti ažurirana u tom scenariju? 347 00:15:25,320 --> 00:15:30,060 34 je pokazivač postane nije null ali adresa struct 348 00:15:30,060 --> 00:15:31,800 sadrži broj 35. 349 00:15:31,800 --> 00:15:32,750 Dakle, to je slučaj dvoje. 350 00:15:32,750 --> 00:15:36,190 Tako je već, ja sam nekako kvantiziranje koliko posla moram učiniti ovdje. 351 00:15:36,190 --> 00:15:39,880 >> I na kraju, očito srednje slučaj Doista, u sredini, ako želim 352 00:15:39,880 --> 00:15:45,870 ubacite nešto poput recimo 23, koji ide između 23 i 26 godina, a 353 00:15:45,870 --> 00:15:48,680 Sada se stvari malo više uključena, jer ono 354 00:15:48,680 --> 00:15:52,800 pokazivače treba mijenjati? 355 00:15:52,800 --> 00:15:56,680 Dakle, 22 očito treba mijenjati jer on se ne može ukazati na 26. više. 356 00:15:56,680 --> 00:16:00,320 On treba ukazati na novi čvor koji Morat ću izdvojiti pozivom 357 00:16:00,320 --> 00:16:01,770 malloc ili neki ekvivalent. 358 00:16:01,770 --> 00:16:05,990 >> Ali onda sam također potrebno da se novi čvor, 23 u ovom slučaju, imati svoj pokazivač 359 00:16:05,990 --> 00:16:07,870 pokazujući na koga? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 I tu će biti Redoslijed operacija ovdje. 362 00:16:10,380 --> 00:16:13,410 Jer ako ja to glupo, i ja , na primjer, na početku od 363 00:16:13,410 --> 00:16:16,040 popis, a moj cilj je da ubacite 23. 364 00:16:16,040 --> 00:16:18,610 I sam provjeriti, to pripadaju Ovdje, kod devet? 365 00:16:18,610 --> 00:16:18,950 Ne. 366 00:16:18,950 --> 00:16:20,670 Da li to pripada ovdje, uz 17? 367 00:16:20,670 --> 00:16:20,940 Ne. 368 00:16:20,940 --> 00:16:22,530 Znači li to spada ovdje pokraj 22.? 369 00:16:22,530 --> 00:16:23,300 Da. 370 00:16:23,300 --> 00:16:26,400 >> Sada, ako sam glupo ovdje, a ne promisli, mogao bih 371 00:16:26,400 --> 00:16:28,320 izdvojiti moj novi čvor za 23. 372 00:16:28,320 --> 00:16:32,080 Ja bi ažurirali pokazivač iz čvora zove 22, ukazujući 373 00:16:32,080 --> 00:16:33,080 je na novi čvor. 374 00:16:33,080 --> 00:16:36,140 I što onda moram ažurirati novi čvor je pointer biti? 375 00:16:36,140 --> 00:16:38,120 >> STUDENT: [nečujno]. 376 00:16:38,120 --> 00:16:38,385 >> ZVUČNI 1: Točno. 377 00:16:38,385 --> 00:16:39,710 Ukazujući na 26. 378 00:16:39,710 --> 00:16:45,590 Ali, k vragu, ako nisam već ažurirali 22 je pokazivač ukazati na ovom čovjeku, i 379 00:16:45,590 --> 00:16:48,260 sada imam siročadi, ostatak popisa, da se tako izrazim. 380 00:16:48,260 --> 00:16:52,140 Dakle, redoslijed operacija ovdje će biti važno. 381 00:16:52,140 --> 00:16:55,100 >> Za to sam mogao ukrasti, recimo, šest volontera. 382 00:16:55,100 --> 00:16:57,650 I neka je vidjeti ako mi to ne može učiniti vizualno, umjesto kod-mudar. 383 00:16:57,650 --> 00:16:59,330 I mi imamo neke lijepe stres loptice za vas danas. 384 00:16:59,330 --> 00:17:02,510 OK, o tome kako jedan, dva, u natrag - na kraju tamo. 385 00:17:02,510 --> 00:17:04,530 tri, četiri, obje dečki na kraju. 386 00:17:04,530 --> 00:17:05,579 I pet, šest. 387 00:17:05,579 --> 00:17:05,839 Svakako. 388 00:17:05,839 --> 00:17:06,450 Pet i šest. 389 00:17:06,450 --> 00:17:08,390 U redu, a mi ćemo doći da ti dečki sljedeći put. 390 00:17:08,390 --> 00:17:09,640 U redu, daj se. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> U redu, budući da ste ovdje prvi put, bi li htjeli biti onaj nezgodno 393 00:17:14,819 --> 00:17:16,119 u Google Glass ovdje? 394 00:17:16,119 --> 00:17:19,075 U redu, tako da, OK, staklo, snimanje videa. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 OK, ti si dobar to ići. 397 00:17:24,589 --> 00:17:27,950 >> U redu, pa ako ti dečki mogu doći Evo, ja sam unaprijed pripremljen 398 00:17:27,950 --> 00:17:30,110 neki brojevi. 399 00:17:30,110 --> 00:17:31,240 U redu, dođi ovamo. 400 00:17:31,240 --> 00:17:33,440 A zašto ne odeš malo dodatno na taj način. 401 00:17:33,440 --> 00:17:35,520 I da vidimo, što je vaše ime, s Google Glass? 402 00:17:35,520 --> 00:17:35,910 >> STUDENT: Ben. 403 00:17:35,910 --> 00:17:36,230 >> ZVUČNI 1: Ben? 404 00:17:36,230 --> 00:17:38,380 OK, Ben, što će biti prvi put, doslovno. 405 00:17:38,380 --> 00:17:40,580 Tako ćemo vam poslati na kraju faze. 406 00:17:40,580 --> 00:17:41,670 U redu, a vaše ime? 407 00:17:41,670 --> 00:17:41,990 >> STUDENT: Jason. 408 00:17:41,990 --> 00:17:44,530 >> ZVUČNI 1: Jason, OK vi ćete se broj devet. 409 00:17:44,530 --> 00:17:46,700 Dakle, ako želite slijediti Ben taj način. 410 00:17:46,700 --> 00:17:47,010 >> STUDENT: Jill. 411 00:17:47,010 --> 00:17:49,630 >> ZVUČNI 1: Jill, ti si idući u biti 17, koji, ako bih to učinio više 412 00:17:49,630 --> 00:17:51,260 inteligentno, ja bi upis na drugom kraju. 413 00:17:51,260 --> 00:17:52,370 Možete ići na taj način. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 A vi ste? 416 00:17:53,670 --> 00:17:53,980 >> STUDENT: Marija. 417 00:17:53,980 --> 00:17:56,130 >> ZVUČNI 1: Marija, vi ćete biti u 22. 418 00:17:56,130 --> 00:17:58,420 A tvoje ime je? 419 00:17:58,420 --> 00:17:58,810 >> STUDENT: Chris. 420 00:17:58,810 --> 00:18:00,100 >> ZVUČNI 1: Chris, vi ćete biti u 26. 421 00:18:00,100 --> 00:18:00,740 I onda na kraju. 422 00:18:00,740 --> 00:18:01,400 >> STUDENT: Diana. 423 00:18:01,400 --> 00:18:02,670 >> ZVUČNI 1: Diana, vi ćete biti u 34. 424 00:18:02,670 --> 00:18:03,920 Tako ste došli ovamo. 425 00:18:03,920 --> 00:18:06,360 >> U redu, tako da usavršite razvrstani Već naručiti. 426 00:18:06,360 --> 00:18:09,600 I idemo naprijed i to tako da možemo stvarno - 427 00:18:09,600 --> 00:18:11,720 Ben ti si samo vrsta potrazi van u nigdje ne postoji. 428 00:18:11,720 --> 00:18:15,670 U redu, tako da idemo naprijed i prikazati ovaj pomoću ruke, baš kao što sam bio, točno, 429 00:18:15,670 --> 00:18:16,250 što se događa. 430 00:18:16,250 --> 00:18:19,540 Dakle, ići naprijed i dati sebi stopu ili dvije od sebe. 431 00:18:19,540 --> 00:18:22,900 I ići naprijed i ukazati s jedne strane na tko bi trebali biti okrenuti 432 00:18:22,900 --> 00:18:23,470 na temelju toga. 433 00:18:23,470 --> 00:18:25,890 A ako ste null uperi ravno na pod. 434 00:18:25,890 --> 00:18:27,690 U redu, tako dobro. 435 00:18:27,690 --> 00:18:32,290 >> Tako sada imamo povezana popis, i neka mi predlažu da ću igrati ulogu 436 00:18:32,290 --> 00:18:35,110 PTR, pa neću gnjaviti Knjigovodstvena ovo oko. 437 00:18:35,110 --> 00:18:37,830 A onda - netko je glupo konvencije - možete nazvati ovo sve što želite - 438 00:18:37,830 --> 00:18:39,800 prethodnik pokazivač, pokazivač Pred - 439 00:18:39,800 --> 00:18:43,930 to je samo nadimak mi je dao u naš primjer koda s moje lijeve strane. 440 00:18:43,930 --> 00:18:47,240 S druge strane da će se vođenje evidenciju o tome tko je tko u 441 00:18:47,240 --> 00:18:48,400 nakon scenarija. 442 00:18:48,400 --> 00:18:52,390 >> Dakle pretpostavljam, prvo, želim trgati off da je prvi primjer umetanjem, kažu 443 00:18:52,390 --> 00:18:54,330 20, u popisu. 444 00:18:54,330 --> 00:18:57,160 Tako da ću morati nekoga na utjeloviti broj 20 za nas. 445 00:18:57,160 --> 00:18:58,950 Dakle, trebam nekoga malloc iz publike. 446 00:18:58,950 --> 00:18:59,380 Dođi gore. 447 00:18:59,380 --> 00:19:00,340 Koje je tvoje ime? 448 00:19:00,340 --> 00:19:01,300 >> STUDENT: Brian. 449 00:19:01,300 --> 00:19:05,270 >> ZVUČNI 1: Brian, u redu, tako da će biti čvor koji sadrži 20. 450 00:19:05,270 --> 00:19:06,810 U redu, dođi ovamo. 451 00:19:06,810 --> 00:19:10,025 I očito, u kojoj Brian ne pripadaju? 452 00:19:10,025 --> 00:19:12,190 Dakle, u sredini - zapravo, čekaj malo. 453 00:19:12,190 --> 00:19:13,420 Činimo to iz reda. 454 00:19:13,420 --> 00:19:17,170 Učinili smo to puno teže nego to treba biti na prvom mjestu. 455 00:19:17,170 --> 00:19:21,210 U redu, idemo u slobodnom Brian realloc i Brian su pet. 456 00:19:21,210 --> 00:19:23,680 >> U redu, tako da sada želimo umetnuti Brian i pet. 457 00:19:23,680 --> 00:19:25,960 Pa hajde ovamo pokraj Ben samo na trenutak. 458 00:19:25,960 --> 00:19:28,250 A ti vjerojatno može reći gdje je ova priča se događa. 459 00:19:28,250 --> 00:19:30,500 Ali neka je dobro razmisliti o tome Redoslijed operacija. 460 00:19:30,500 --> 00:19:32,880 I to je upravo ovaj vizualni koji će se postroje 461 00:19:32,880 --> 00:19:34,080 s tom primjeru koda. 462 00:19:34,080 --> 00:19:40,120 Dakle, ovdje sam PTR ukazujući na početku Ne, na Bena, per se, ali bez obzira na 463 00:19:40,120 --> 00:19:43,245 Cijenimo ga sadrži, što u ovom slučaju je - ono zoveš? 464 00:19:43,245 --> 00:19:43,670 >> STUDENT: Jason. 465 00:19:43,670 --> 00:19:47,350 >> ZVUČNI 1: Jason, tako i Ben i ja smo pokazujući na Jasona u ovom trenutku. 466 00:19:47,350 --> 00:19:49,700 Pa sad moram odrediti, gdje se Brian pripadaju? 467 00:19:49,700 --> 00:19:53,500 Dakle, jedino što imam pristup sada je njegov n podaci stavku. 468 00:19:53,500 --> 00:19:58,280 Dakle, idem provjeriti, je Brian manje od Jasona? 469 00:19:58,280 --> 00:19:59,770 Odgovor je istina. 470 00:19:59,770 --> 00:20:03,680 >> Dakle, ono što se sada treba dogoditi, u ispravnom redoslijedu? 471 00:20:03,680 --> 00:20:07,120 Trebam li ažurirati koliko pokazivače Ukupno je u ovoj priči? 472 00:20:07,120 --> 00:20:10,720 Gdje mi je ruka još uvijek je pokazivao Jason, a tvoja ruka - ako želite 473 00:20:10,720 --> 00:20:12,930 stavi svoju ruku kao što je, na neki način, sam Ne znam, Upitnik. 474 00:20:12,930 --> 00:20:14,070 OK, dobro. 475 00:20:14,070 --> 00:20:15,670 >> U redu, tako da imate nekoliko kandidata. 476 00:20:15,670 --> 00:20:20,500 Ili Ben ili ja ili Brian ili Jason ili svi drugi, koji 477 00:20:20,500 --> 00:20:21,370 pokazivače trebate promijeniti? 478 00:20:21,370 --> 00:20:23,260 Koliko je ukupno? 479 00:20:23,260 --> 00:20:24,080 >> U redu, tako da dvojica. 480 00:20:24,080 --> 00:20:27,090 Moj pokazivač zapravo ne smeta više jer ja sam samo privremeno. 481 00:20:27,090 --> 00:20:31,370 Tako da je ove dvije dečki, vjerojatno, i Ben i Brian. 482 00:20:31,370 --> 00:20:34,410 Pa neka mi predložiti da se ažurirati Ben, budući da je prvi put. 483 00:20:34,410 --> 00:20:36,350 Prvi element ovog popisa sada će se Brian. 484 00:20:36,350 --> 00:20:38,070 Dakle Ben točka na Briana. 485 00:20:38,070 --> 00:20:39,320 OK, što sad? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Tko dobiva ukazao na koga? 488 00:20:43,460 --> 00:20:44,710 >> STUDENT: [nečujno]. 489 00:20:44,710 --> 00:20:46,180 >> ZVUČNI 1: U redu, tako je Brian ukazati na Jasona. 490 00:20:46,180 --> 00:20:48,360 Ali sam izgubio pojam o tom pokazivač? 491 00:20:48,360 --> 00:20:49,980 Znam gdje je Jason? 492 00:20:49,980 --> 00:20:50,790 >> STUDENT: [nečujno]. 493 00:20:50,790 --> 00:20:52,620 >> ZVUČNI 1: radim, jer sam privremena pointer. 494 00:20:52,620 --> 00:20:55,110 A vjerojatno, ja se nisam promijenio ukazati na novi čvor. 495 00:20:55,110 --> 00:20:58,300 Dakle, mi jednostavno možete imati Brian točku po tko sam pokazujući na. 496 00:20:58,300 --> 00:20:59,000 I mi smo gotovi. 497 00:20:59,000 --> 00:21:01,890 Tako je jedan slučaj, uneseni u početak popisa. 498 00:21:01,890 --> 00:21:02,950 Dva su ključna koraka. 499 00:21:02,950 --> 00:21:06,750 Jedan, moramo ažurirati Bena, a zatim imamo i ažurirati Briana. 500 00:21:06,750 --> 00:21:09,230 I onda ja ne moram se gnjaviti traipsing kroz ostatak 501 00:21:09,230 --> 00:21:12,680 Popis, jer mi je već našao svoje položaj, jer je on pripadao 502 00:21:12,680 --> 00:21:14,080 lijevo od prvog elementa. 503 00:21:14,080 --> 00:21:15,400 >> U redu, tako da prilično jednostavan. 504 00:21:15,400 --> 00:21:18,110 Zapravo, osjeća se kao da smo gotovo što je ovo previše komplicirano. 505 00:21:18,110 --> 00:21:20,240 Tako ćemo sada trgati off kraj popisa, i vidjeti gdje je 506 00:21:20,240 --> 00:21:21,380 složenosti počinje. 507 00:21:21,380 --> 00:21:24,560 Dakle, ako sada, ja alloc iz publike. 508 00:21:24,560 --> 00:21:25,540 Svatko želi igrati 55? 509 00:21:25,540 --> 00:21:26,700 U redu, vidjela sam svoju ruku prvo. 510 00:21:26,700 --> 00:21:29,620 Dođi gore. 511 00:21:29,620 --> 00:21:30,030 Da. 512 00:21:30,030 --> 00:21:31,177 Koje je tvoje ime? 513 00:21:31,177 --> 00:21:32,310 >> STUDENT: [nečujno]. 514 00:21:32,310 --> 00:21:33,240 >> ZVUČNI 1: Habata. 515 00:21:33,240 --> 00:21:33,890 OK, daj se. 516 00:21:33,890 --> 00:21:35,730 Vi ćete biti broj 55. 517 00:21:35,730 --> 00:21:37,820 Tako da, naravno, pripadaju na kraju popisa. 518 00:21:37,820 --> 00:21:41,850 Tako ćemo ponovno simulacija sa mnom što PTR samo na trenutak. 519 00:21:41,850 --> 00:21:44,050 Tako sam prvi put idem ukazati na god Ben je pokazivao. 520 00:21:44,050 --> 00:21:45,900 Mi oboje upućuju sada na Briana. 521 00:21:45,900 --> 00:21:48,420 Tako da 55 je ne manje od pet. 522 00:21:48,420 --> 00:21:52,510 Pa ću ja ažurirati ukazujući na Brianovi sljedeći pokazivač, koji je 523 00:21:52,510 --> 00:21:54,450 Sada je, naravno, Jason. 524 00:21:54,450 --> 00:21:57,310 55 je ne manje od devet, tako Ja ću ažurirati PTR. 525 00:21:57,310 --> 00:21:58,890 Ja ću ažurirati PTR. 526 00:21:58,890 --> 00:22:02,290 Ja ću ažurirati PTR Ja ću ažurirati PTR. 527 00:22:02,290 --> 00:22:05,060 A ja ću se - hm, što je zoveš? 528 00:22:05,060 --> 00:22:05,560 >> STUDENT: Diana. 529 00:22:05,560 --> 00:22:09,190 >> ZVUČNI 1: Diana pokazuje, naravno, na null s njezine lijeve strane. 530 00:22:09,190 --> 00:22:13,030 Dakle, gdje se zapravo Habata pripadaju jasno? 531 00:22:13,030 --> 00:22:15,050 S lijeve strane, ovdje. 532 00:22:15,050 --> 00:22:19,460 Dakle, kako da znam da joj stavi ovdje Mislim da sam zeznuo. 533 00:22:19,460 --> 00:22:22,420 Jer, što je PTR umjetnost ovaj trenutak u vremenu? 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Dakle, iako je vizualno, možemo Očito vidjeti u svemu ovome 536 00:22:25,580 --> 00:22:26,610 Dečki ovdje na pozornici. 537 00:22:26,610 --> 00:22:29,680 Nisam pratila od prethodnih Osoba u popisu. 538 00:22:29,680 --> 00:22:33,210 Ja nemam prst ističući, u ovom slučaju, broj 34 čvora. 539 00:22:33,210 --> 00:22:34,760 >> Tako ćemo zapravo početi ovaj iznad. 540 00:22:34,760 --> 00:22:37,560 Pa sad ja zapravo trebam Drugi lokalni promjenjiva. 541 00:22:37,560 --> 00:22:40,980 I to je ono što ćete vidjeti u Stvarni broj uzorak C, gdje je kao idem, 542 00:22:40,980 --> 00:22:45,860 kad sam ažurirati moj desnu ruku do točke Jason, čime je Brian iza sebe, sam 543 00:22:45,860 --> 00:22:51,440 bolje početi koristiti lijevu ruku na ažurirati gdje sam bio, tako da kao idem 544 00:22:51,440 --> 00:22:52,700 kroz ovaj popis - 545 00:22:52,700 --> 00:22:55,040 više nespretno nego što sam namjeravao Sada ovdje vizualno - 546 00:22:55,040 --> 00:22:56,740 Ja ću doći do kraj popisa. 547 00:22:56,740 --> 00:23:00,020 >> Ova ruka je još uvijek null, što je prilično beskorisno, osim za označavanje 548 00:23:00,020 --> 00:23:02,980 Ja sam jasno na kraju popisa ali sada barem imam ovu 549 00:23:02,980 --> 00:23:08,270 prethodnik pointer pokazuje ovdje, pa Sada ono ruke i ono što je potrebno upućuje 550 00:23:08,270 --> 00:23:10,150 biti ažuriran? 551 00:23:10,150 --> 00:23:13,214 Čija ruka želite za preustroj prvi? 552 00:23:13,214 --> 00:23:15,190 >> STUDENT: [nečujno]. 553 00:23:15,190 --> 00:23:16,220 >> ZVUČNI 1: U redu, tako Dijane. 554 00:23:16,220 --> 00:23:21,110 Gdje želiš istaknuti Dianina lijeva kazaljka na? 555 00:23:21,110 --> 00:23:23,620 U 55 godina, vjerojatno, tako da je smo umetnuta postoji. 556 00:23:23,620 --> 00:23:25,560 A gdje bi trebao ići 55 pokazivač? 557 00:23:25,560 --> 00:23:27,000 Dolje, što predstavlja null. 558 00:23:27,000 --> 00:23:28,890 I moje ruke, u ovom trenutku, ne važno, jer oni su jednostavno 559 00:23:28,890 --> 00:23:30,070 privremene varijable. 560 00:23:30,070 --> 00:23:31,030 Dakle, sada smo gotovi. 561 00:23:31,030 --> 00:23:34,650 >> Dakle dodatni složenosti postoji - i nije da je teško provesti, 562 00:23:34,650 --> 00:23:38,660 ali moramo sekundarnu varijablu kako bi sigurni da je prije mičem pravo 563 00:23:38,660 --> 00:23:42,140 S druge strane, sam ažurirati vrijednost mi je lijeva S druge strane, Pred pokazivač u ovom slučaju, tako da 564 00:23:42,140 --> 00:23:45,860 da imam prateći pokazivač pratiti gdje sam bio. 565 00:23:45,860 --> 00:23:49,360 Sada su na stranu, ako ste mislili na ovo putem, to se osjeća kao da je 566 00:23:49,360 --> 00:23:51,490 malo neugodno da su zadržati pratite ove lijeve strane. 567 00:23:51,490 --> 00:23:54,015 >> Što bi drugo rješenje na ovaj problem bio? 568 00:23:54,015 --> 00:23:56,500 Ako imaš za redizajn podatke Struktura pričamo 569 00:23:56,500 --> 00:23:59,630 do sada? 570 00:23:59,630 --> 00:24:02,690 Ako je to samo vrsta osjeća malo neugodno da su, kao, dva pokazivače 571 00:24:02,690 --> 00:24:08,430 ide kroz popis, tko bi drugi mogao su, u idealnom svijetu, održava 572 00:24:08,430 --> 00:24:10,160 Informacije koje trebamo? 573 00:24:10,160 --> 00:24:11,360 Da? 574 00:24:11,360 --> 00:24:12,610 >> STUDENT: [nečujno]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> ZVUČNI 1: Točno. 577 00:24:16,150 --> 00:24:19,130 Točno tako da je zapravo zanimljiva klica ideje. 578 00:24:19,130 --> 00:24:22,470 A ova ideja o prethodnoj pokazivač, pokazuje na prethodni element. 579 00:24:22,470 --> 00:24:25,580 Što ako sam samo da je utjelovljena unutar samom popisu? 580 00:24:25,580 --> 00:24:27,810 I to će biti teško vizualizirati to bez svih papira 581 00:24:27,810 --> 00:24:28,830 pada na pod. 582 00:24:28,830 --> 00:24:31,860 Ali pretpostavimo da su ti dečki koristiti i njihovih ruku imati prethodna 583 00:24:31,860 --> 00:24:35,950 pokazivač, a pored pokazivač, čime se provedbi onoga što ćemo nazvati dvostruko 584 00:24:35,950 --> 00:24:36,830 povezani popis. 585 00:24:36,830 --> 00:24:41,090 To bi omogućilo mi je da vrsta unatrag puno lakše i bez mene, 586 00:24:41,090 --> 00:24:43,800 programer, da se zadrži pratili ručno - 587 00:24:43,800 --> 00:24:44,980 doista ručno - 588 00:24:44,980 --> 00:24:47,280 mjesta gdje sam bio prije na popisu. 589 00:24:47,280 --> 00:24:48,110 Dakle, nećemo to učiniti. 590 00:24:48,110 --> 00:24:50,950 Držat ćemo ga jednostavno zato jer je to će doći na cijenu, dvostruko 591 00:24:50,950 --> 00:24:53,450 puno prostora za pokazivače, ako želite drugu. 592 00:24:53,450 --> 00:24:55,760 Ali to je doista česta struktura podataka poznat kao 593 00:24:55,760 --> 00:24:57,410 dvostruko povezani popis. 594 00:24:57,410 --> 00:25:01,310 >> Idemo napraviti konačni primjer ovdje i staviti ovi momci iz njihove bijede. 595 00:25:01,310 --> 00:25:03,270 Dakle malloc 20. 596 00:25:03,270 --> 00:25:05,320 Hajde se iz prolaz tamo. 597 00:25:05,320 --> 00:25:06,280 U redu, što je vaše ime? 598 00:25:06,280 --> 00:25:07,440 >> STUDENT: [nečujno]. 599 00:25:07,440 --> 00:25:07,855 >> ZVUČNI 1: Žao mi je? 600 00:25:07,855 --> 00:25:08,480 >> STUDENT: [nečujno]. 601 00:25:08,480 --> 00:25:09,410 >> ZVUČNI 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK daj se. 603 00:25:10,230 --> 00:25:11,910 Ti će se 20. 604 00:25:11,910 --> 00:25:14,720 Vi očito će pripadaju između 17 i 22. 605 00:25:14,720 --> 00:25:16,150 Pa neka mi naučili svoju lekciju. 606 00:25:16,150 --> 00:25:18,150 Ja ću početi pokazivač pokazujući na Briana. 607 00:25:18,150 --> 00:25:21,190 A ja ću imati svoju lijevu ruku Samo ažurirajte Briana kao što sam premjestiti na 608 00:25:21,190 --> 00:25:23,600 Jason, provjera radi 20 manje od devet? 609 00:25:23,600 --> 00:25:24,060 Ne. 610 00:25:24,060 --> 00:25:25,430 Je 20 manje od 17? 611 00:25:25,430 --> 00:25:25,880 Ne. 612 00:25:25,880 --> 00:25:27,450 Je 20 manje od 22? 613 00:25:27,450 --> 00:25:28,440 Da. 614 00:25:28,440 --> 00:25:34,070 Dakle, što upućuje ili šake morati promijeniti gdje se pokazuje sada? 615 00:25:34,070 --> 00:25:37,070 >> Dakle, možemo napraviti 17 pokazujući na 20.. 616 00:25:37,070 --> 00:25:37,860 Dakle, to je u redu. 617 00:25:37,860 --> 00:25:40,080 Gdje želimo ukazati pokazivač sada? 618 00:25:40,080 --> 00:25:41,330 Na 22.. 619 00:25:41,330 --> 00:25:45,410 A znamo gdje je 22, opet hvala na moj privremenog pokazivač. 620 00:25:45,410 --> 00:25:46,760 Tako smo u redu tamo. 621 00:25:46,760 --> 00:25:49,440 Dakle, zbog ovog privremenog skladištenja Ja sam pratila gdje je svatko. 622 00:25:49,440 --> 00:25:55,055 A sada možete vizualno može ići u kojoj spadate, a sada trebamo 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 stres loptice, i krug pljeskom 624 00:25:58,410 --> 00:25:59,770 ovi dečki, ako smo mogli. 625 00:25:59,770 --> 00:26:00,410 Lijepo učinili. 626 00:26:00,410 --> 00:26:05,320 >> [PLJESAK] 627 00:26:05,320 --> 00:26:06,330 >> ZVUČNI 1: U redu. 628 00:26:06,330 --> 00:26:09,860 A možda bi komada papira, kao uspomena. 629 00:26:09,860 --> 00:26:15,930 >> U redu, tako da, vjeruj mi to je puno lakše prolaziti kroz koje s 630 00:26:15,930 --> 00:26:17,680 ljudi nego što je s aktualnom kodu. 631 00:26:17,680 --> 00:26:22,690 No, ono što ćete pronaći u samo trenutak Sada, je li to ista - Oh, hvala ti. 632 00:26:22,690 --> 00:26:23,630 Hvala vam - 633 00:26:23,630 --> 00:26:29,360 je da ćete uvidjeti da je iste podatke Struktura, povezani popis, može zapravo 634 00:26:29,360 --> 00:26:33,200 se koristiti kao građevinski blok još sofisticirane strukture podataka. 635 00:26:33,200 --> 00:26:37,620 >> I shvatite previše tema ovdje je da Apsolutno smo uveli više 636 00:26:37,620 --> 00:26:40,060 složenosti u provedbi ovog algoritma. 637 00:26:40,060 --> 00:26:43,940 Ubacivanje, a ako smo prošli kroz njega, brisanje i pretraživanje, je malo 638 00:26:43,940 --> 00:26:46,660 složeniji od njega bio s nizom. 639 00:26:46,660 --> 00:26:48,040 No, mi dobiti neke dinamizam. 640 00:26:48,040 --> 00:26:50,180 Mi smo dobili adaptivni strukturu podataka. 641 00:26:50,180 --> 00:26:54,010 >> Ali opet, plaćamo cijenu što neke Dodatni složenosti, kako u 642 00:26:54,010 --> 00:26:54,910 njegovu provedbu. 643 00:26:54,910 --> 00:26:56,750 I mi smo odustali slučajni pristup. 644 00:26:56,750 --> 00:27:00,450 A da budem iskren, ne postoji neki lijep očistite slajd Mogu vam dati da 645 00:27:00,450 --> 00:27:03,120 Ovdje piše da je razlog zašto povezani popis je bolje nego niz. 646 00:27:03,120 --> 00:27:04,100 I ostaviti ga na to. 647 00:27:04,100 --> 00:27:07,520 Budući da je tema ponovno pojavljivanje sada, čak i više u narednim tjednima, je 648 00:27:07,520 --> 00:27:10,200 da nije nužno točan odgovor. 649 00:27:10,200 --> 00:27:13,830 >> To je razlog zašto imamo zasebnu os dizajna za problematična setovima. 650 00:27:13,830 --> 00:27:17,700 To će biti vrlo osjetljiva na kontekst želite li koristiti ove podatke 651 00:27:17,700 --> 00:27:21,750 strukture ili da je jedan, i to će ovisi o tome što je važno za vas u smislu 652 00:27:21,750 --> 00:27:24,620 resursa i složenosti. 653 00:27:24,620 --> 00:27:28,830 >> No, dopustite mi predložiti da se idealni podataka Struktura, sveti gral, bio bi 654 00:27:28,830 --> 00:27:32,200 nešto što je stalno vremena, bez obzira na to koliko je stvari 655 00:27:32,200 --> 00:27:36,940 unutar njega, ne bi bilo iznenađujuće ako se struktura podataka vratio odgovore u 656 00:27:36,940 --> 00:27:37,920 stalno vrijeme. 657 00:27:37,920 --> 00:27:38,330 Da. 658 00:27:38,330 --> 00:27:40,110 Ova riječ je u svom velikom rječniku. 659 00:27:40,110 --> 00:27:41,550 Ili ne, to znači da je nema. 660 00:27:41,550 --> 00:27:43,270 Ili bilo koji takav problem postoji. 661 00:27:43,270 --> 00:27:46,360 Pa ćemo vidjeti, ako ne možemo barem uzeti jedan korak prema tome. 662 00:27:46,360 --> 00:27:50,190 >> Dopustite mi da predloži novu strukturu podataka koji može se koristiti za različite stvari, 663 00:27:50,190 --> 00:27:52,260 u ovom slučaju zove hash tablicu. 664 00:27:52,260 --> 00:27:55,590 I tako smo zapravo natrag pogledavši na polju, u ovom slučaju, i 665 00:27:55,590 --> 00:28:00,550 nešto samovoljno, ja sam izvući ovu hash tablicu kao polje s vrstom 666 00:28:00,550 --> 00:28:02,810 dvodimenzionalno polje - 667 00:28:02,810 --> 00:28:05,410 odnosno to je prikazano ovdje kao dva dimenzionalni niz - ali to je samo 668 00:28:05,410 --> 00:28:10,770 niz veličine 26, tako da ako se nazovite polje stol, stolni nosač 669 00:28:10,770 --> 00:28:12,440 nula pravokutnik na vrhu. 670 00:28:12,440 --> 00:28:15,090 Tablica nosač 25 je pravokutnik na dnu. 671 00:28:15,090 --> 00:28:18,620 A to je, kako sam mogao nacrtati podatke struktura u kojoj želim pohraniti 672 00:28:18,620 --> 00:28:19,790 Imena osoba. 673 00:28:19,790 --> 00:28:24,370 >> Tako, primjerice, i neću povući Cijela stvar ovdje na pretek, ako sam 674 00:28:24,370 --> 00:28:29,160 je ovaj niz, što ja sada idem nazovite hash tablicu, a to je opet 675 00:28:29,160 --> 00:28:31,360 Mjesto na nuli. 676 00:28:31,360 --> 00:28:34,840 Ovo ovdje je location jedan, i tako dalje. 677 00:28:34,840 --> 00:28:37,880 Ja tvrdim da želim koristiti ove podatke Struktura, radi rasprave, 678 00:28:37,880 --> 00:28:42,600 za pohranu imena ljudi, Alice i Bob i Charlie i ostali takvi nazivi. 679 00:28:42,600 --> 00:28:46,110 Tako da je to sada, kao počeci od, recimo, u rječniku 680 00:28:46,110 --> 00:28:47,520 s puno riječi. 681 00:28:47,520 --> 00:28:49,435 Oni se dogoditi da se imena u našem primjeru ovdje. 682 00:28:49,435 --> 00:28:52,560 I to je sve previše povezan, možda, provodi provjeru pravopisa, kao i mi 683 00:28:52,560 --> 00:28:54,400 Možda za postavljanje šest problema. 684 00:28:54,400 --> 00:28:59,300 >> Dakle, ako imamo niz ukupne veličine 26 , tako da je ovo 25. Mjesto 685 00:28:59,300 --> 00:29:03,390 na dnu, i tvrde da je Alice Prva riječ u rječniku 686 00:29:03,390 --> 00:29:07,260 imena koje se želim umetnuti u RAM, u ovu strukturu podataka, gdje su 687 00:29:07,260 --> 00:29:12,480 instinkt vam govori da je Alice-a Naziv bi trebao ići u tom polju? 688 00:29:12,480 --> 00:29:13,510 >> Imamo 26 opcija. 689 00:29:13,510 --> 00:29:14,990 Gdje želimo ju staviti? 690 00:29:14,990 --> 00:29:16,200 Mi joj želimo u zagradi nula, zar ne? 691 00:29:16,200 --> 00:29:18,280 Za Alice, nazovimo tu nulu. 692 00:29:18,280 --> 00:29:20,110 A B će biti jedan, i C će biti dva. 693 00:29:20,110 --> 00:29:22,600 Tako ćemo pisati Alice je ime ovdje. 694 00:29:22,600 --> 00:29:24,890 Ako smo onda ubacite Bob, njegov Ime će ići tamo. 695 00:29:24,890 --> 00:29:27,280 Charlie će ići tamo. 696 00:29:27,280 --> 00:29:30,500 I tako dalje dolje kroz ova struktura podataka. 697 00:29:30,500 --> 00:29:32,090 >> Ovo je divno struktura podataka. 698 00:29:32,090 --> 00:29:32,730 Zašto? 699 00:29:32,730 --> 00:29:37,460 Pa ono je vrijeme rada Umetanje ljudski ime u ovo 700 00:29:37,460 --> 00:29:39,850 Podaci o strukturi upravo sada? 701 00:29:39,850 --> 00:29:43,702 S obzirom da je ova tablica je proveden, doista, kao polje. 702 00:29:43,702 --> 00:29:44,940 Pa to je konstantna vrijeme. 703 00:29:44,940 --> 00:29:45,800 To bi jednog. 704 00:29:45,800 --> 00:29:46,360 Zašto? 705 00:29:46,360 --> 00:29:48,630 >> Pa kako ste utvrdili Alice kojoj pripada? 706 00:29:48,630 --> 00:29:51,000 Možete pogledati na koje slovo njenog imena? 707 00:29:51,000 --> 00:29:51,490 Prvi. 708 00:29:51,490 --> 00:29:54,350 I možete doći, ako je string, samo gleda na žici 709 00:29:54,350 --> 00:29:55,200 Nosač nuli. 710 00:29:55,200 --> 00:29:57,110 Dakle nultoga karakter niza. 711 00:29:57,110 --> 00:29:57,610 To je jednostavno. 712 00:29:57,610 --> 00:30:00,350 To smo učinili u kripto Raspored tjedna. 713 00:30:00,350 --> 00:30:05,310 I onda kada znate da je Alice Pismo je kapital, možemo oduzimati 714 00:30:05,310 --> 00:30:08,160 65 off ili grada A sama, koji nam daje nulu. 715 00:30:08,160 --> 00:30:10,940 Dakle, sada znamo da je Alice spada na mjestu nula. 716 00:30:10,940 --> 00:30:14,240 >> I dao pokazivač do tih podataka Struktura, neke vrste, koliko dugo traje 717 00:30:14,240 --> 00:30:18,840 to mi se pronaći mjesto nuli u niz? 718 00:30:18,840 --> 00:30:22,080 Samo jedan korak, pravo je vrijeme konstanta zbog slučajnog pristupa smo 719 00:30:22,080 --> 00:30:23,780 Predloženi je značajka niz. 720 00:30:23,780 --> 00:30:28,570 Tako je u kratkom, figuring out ono što indeksa Alice je ime, što je, u 721 00:30:28,570 --> 00:30:32,610 ovaj slučaj je, ili ćemo jednostavno riješiti da je na nulu, gdje je B je jedan i C je 722 00:30:32,610 --> 00:30:34,900 dva, računajući da se Vrijeme je konstanta. 723 00:30:34,900 --> 00:30:38,510 Samo moram gledati na svom prvom pismu, figuring out gdje je nula 724 00:30:38,510 --> 00:30:40,460 Niz je također konstantna vrijeme. 725 00:30:40,460 --> 00:30:42,140 Dakle, to je tehnički kao dva koraka sada. 726 00:30:42,140 --> 00:30:43,330 Ali to je uvijek konstantna. 727 00:30:43,330 --> 00:30:46,880 Dakle, mi zovemo taj veliki O jednog, pa smo umetnuta Alisa u ovoj tablici u 728 00:30:46,880 --> 00:30:48,440 stalno vrijeme. 729 00:30:48,440 --> 00:30:50,960 >> Ali, naravno, ja sam se naivna ovdje, zar ne? 730 00:30:50,960 --> 00:30:53,240 Što ako je Aaron u razredu? 731 00:30:53,240 --> 00:30:53,990 Ili Alicia? 732 00:30:53,990 --> 00:30:57,230 Ili bilo koji drugi nazivi počinju sa A. Gdje ćemo staviti 733 00:30:57,230 --> 00:31:00,800 ta osoba, zar ne? 734 00:31:00,800 --> 00:31:03,420 Mislim, upravo sada ima samo tri ljudi na stolu, pa možda smo 735 00:31:03,420 --> 00:31:07,490 treba staviti na mjesto Aarona nula jedan, dva, tri. 736 00:31:07,490 --> 00:31:09,480 >> Točno, mogao sam staviti ovdje. 737 00:31:09,480 --> 00:31:13,350 Ali onda, ako ćemo pokušati umetanje Davida u ovaj popis, u kojem nema Davida gdje? 738 00:31:13,350 --> 00:31:15,170 Sada naš sustav počne rješava prema dolje, zar ne? 739 00:31:15,170 --> 00:31:19,210 Jer sada je David završava ovdje ako je Aron je zapravo ovdje. 740 00:31:19,210 --> 00:31:23,060 I sad je cijela ova ideja da čist struktura podataka koje nam daje 741 00:31:23,060 --> 00:31:28,010 stalne vrijeme ubacivanja više nije stalno vrijeme, jer moram 742 00:31:28,010 --> 00:31:31,240 ček, oh, dovraga, netko je već na Alice mjesto. 743 00:31:31,240 --> 00:31:35,320 >> Dopustite mi da provjerite ostatak ove podatke Struktura, u potrazi za mjesto staviti 744 00:31:35,320 --> 00:31:37,130 netko poput Aaronovoj ime. 745 00:31:37,130 --> 00:31:39,390 I tako to previše počinje da se linearno vrijeme. 746 00:31:39,390 --> 00:31:42,710 Štoviše, ako se sada želite pronaći Aaron je u ovom strukturom podataka, a vi 747 00:31:42,710 --> 00:31:45,430 provjeriti i Aronov ime nije ovdje. 748 00:31:45,430 --> 00:31:47,960 U idealnom slučaju, samo bih rekao Aronu Ne u strukturu podataka. 749 00:31:47,960 --> 00:31:51,530 Ali ako to početak stvaranje prostora za Aaron tamo gdje je trebao biti D 750 00:31:51,530 --> 00:31:55,600 ili E, da, najgorem slučaju, morate provjeriti Cijela struktura podataka, u 751 00:31:55,600 --> 00:31:59,480 kojem slučaju to prerasta u nešto linearno u veličini stola. 752 00:31:59,480 --> 00:32:00,920 >> Pa dobro, ja ću to popraviti. 753 00:32:00,920 --> 00:32:04,200 Problem je što sam imala 26 elemenata u tom polju. 754 00:32:04,200 --> 00:32:05,000 Dopustite mi da ga promijeniti. 755 00:32:05,000 --> 00:32:06,010 Ups. 756 00:32:06,010 --> 00:32:10,600 Dopustite mi da ga promijeniti, tako da radije bude mjesta veličina 26 ukupno, primijetit dno 757 00:32:10,600 --> 00:32:12,720 Indeks će se promijeniti na n minus jedan. 758 00:32:12,720 --> 00:32:16,610 Ako 26 je očito premali za ljude ' imena, jer ima na tisuće 759 00:32:16,610 --> 00:32:20,830 Imena svijeta, hajdemo napraviti po 100 ili 1000 ili 10000. 760 00:32:20,830 --> 00:32:22,960 Ajmo izdvojiti puno više prostora. 761 00:32:22,960 --> 00:32:27,230 >> Pa to ne mora nužno smanjiti vjerojatnost da nećemo imati dva 762 00:32:27,230 --> 00:32:31,510 ljudi s imenima počevši, i tako, da ćeš pokušati staviti 763 00:32:31,510 --> 00:32:33,120 imena na mjesto nule još uvijek. 764 00:32:33,120 --> 00:32:36,850 Oni još uvijek će se sudariti, koji znači da smo još uvijek je potrebno rješenje staviti 765 00:32:36,850 --> 00:32:41,020 Alice i Aron i Alicia i druge nazivi počinju s A na drugom mjestu. 766 00:32:41,020 --> 00:32:43,460 No, koliko je problem je to? 767 00:32:43,460 --> 00:32:46,870 Koja je vjerojatnost da ima sudara u podacima 768 00:32:46,870 --> 00:32:48,240 struktura kao što je ovaj? 769 00:32:48,240 --> 00:32:52,570 >> Pa, neka mi - mi ćemo se vratiti na to pitanje ovdje. 770 00:32:52,570 --> 00:32:55,530 A pogledajte kako bismo mogli Prvi ga riješiti. 771 00:32:55,530 --> 00:32:58,480 Dopustite mi povući ovaj prijedlog ovdje. 772 00:32:58,480 --> 00:33:02,020 Ono što smo upravo opisali je algoritam, heuristička zove linearno 773 00:33:02,020 --> 00:33:05,030 sondiranje pri čemu, ako ste pokušali umetanje nešto ovdje u ove podatke 774 00:33:05,030 --> 00:33:08,920 struktura, koja se zove hash tablicu, i tu nema mjesta tamo, 775 00:33:08,920 --> 00:33:12,000 doista ispitati strukturu podataka ček, je li to dostupno? 776 00:33:12,000 --> 00:33:13,430 Je li to Dostupan je to dostupno? 777 00:33:13,430 --> 00:33:13,980 Je li to dostupno? 778 00:33:13,980 --> 00:33:17,550 I kad je konačno, umetanja ime koje ste prvotno namijenjen 779 00:33:17,550 --> 00:33:19,370 na drugom mjestu na toj lokaciji. 780 00:33:19,370 --> 00:33:23,360 No, u najgorem slučaju, samo mjesto može biti samo dno podataka 781 00:33:23,360 --> 00:33:25,090 struktura, sami kraj niza. 782 00:33:25,090 --> 00:33:30,130 >> Dakle, linearno sondiranje, u najgorem slučaju, prerasta u linearni algoritam gdje 783 00:33:30,130 --> 00:33:34,500 Aaron, ako se dogodi da se umeće posljednja u ovom strukturom podataka, mogao bi 784 00:33:34,500 --> 00:33:39,540 sudaraju s ovom prvom mjestu, ali onda na kraju od strane peh na samom kraju. 785 00:33:39,540 --> 00:33:43,940 Dakle, to nije stalna Vrijeme sveti gral za nas. 786 00:33:43,940 --> 00:33:47,650 Ovaj pristup umetanje elemenata u struktura podataka zove hash 787 00:33:47,650 --> 00:33:52,050 Tablica se ne čini da se stalno Vrijeme barem ne u općem slučaju. 788 00:33:52,050 --> 00:33:54,000 To može prenijeti u nešto linearno. 789 00:33:54,000 --> 00:33:56,970 >> Pa što ako smo riješili sudara nešto drugačije? 790 00:33:56,970 --> 00:34:00,740 Dakle, ovdje je sve sofisticiraniji pristup na ono što je još uvijek 791 00:34:00,740 --> 00:34:02,800 zove hash tablicu. 792 00:34:02,800 --> 00:34:05,890 I mljeveno meso, kao stranu, što Mislim da je indeks 793 00:34:05,890 --> 00:34:07,070 Ja tekstu ranije. 794 00:34:07,070 --> 00:34:09,810 Za hash nešto može biti misao kao glagol. 795 00:34:09,810 --> 00:34:13,690 >> Dakle, ako ste hash Alice je ime, hash funkciju, da tako kažemo, 796 00:34:13,690 --> 00:34:14,710 trebao vratiti broj. 797 00:34:14,710 --> 00:34:18,199 U ovom slučaju je nula, ako je ona spada u Mjesto na nuli, ako je jedan zaposlen na 798 00:34:18,199 --> 00:34:20,000 Mjesto jedan, i tako dalje. 799 00:34:20,000 --> 00:34:24,360 Dakle, moj hash funkcija je do sada bio super jednostavna, samo gleda 800 00:34:24,360 --> 00:34:26,159 prvo slovo u nečije ime. 801 00:34:26,159 --> 00:34:29,090 Ali hash funkcija uzima kao Ulaz neki komad podataka, 802 00:34:29,090 --> 00:34:30,210 string, int, što god. 803 00:34:30,210 --> 00:34:32,239 I to ispljune u pravilu donosi niz. 804 00:34:32,239 --> 00:34:35,739 A taj broj je gdje da se podaci Element pripada u strukturu podataka 805 00:34:35,739 --> 00:34:37,800 poznat ovdje kao hash tablicu. 806 00:34:37,800 --> 00:34:41,400 >> Dakle, samo intuitivno, to je malo drugačiji kontekst. 807 00:34:41,400 --> 00:34:44,170 To zapravo se odnosi na primjer uključuju rođendane, gdje 808 00:34:44,170 --> 00:34:46,850 Tu bi moglo biti čak 31 dana u mjesecu. 809 00:34:46,850 --> 00:34:52,239 No, ono što je ova osoba odlučiti učiniti u slučaju sudara? 810 00:34:52,239 --> 00:34:55,304 Kontekst sada se, ne sudar imena, ali sudar rođendane, 811 00:34:55,304 --> 00:35:00,760 ako dvije osobe imaju isti rođendan 2. listopada, na primjer. 812 00:35:00,760 --> 00:35:02,120 >> STUDENT: [nečujno]. 813 00:35:02,120 --> 00:35:05,010 >> ZVUČNI 1: Da, pa ovdje imamo dugovima povezanim listama. 814 00:35:05,010 --> 00:35:07,830 Tako to izgleda malo drugačije nego što smo to ranije nacrtao. 815 00:35:07,830 --> 00:35:10,790 Ali mi se čini da moraju niz na lijevoj strani. 816 00:35:10,790 --> 00:35:13,230 To je jedan indeks, jer nema poseban razlog. 817 00:35:13,230 --> 00:35:14,630 Ali to je još uvijek niz. 818 00:35:14,630 --> 00:35:16,160 To je niz pokazivača. 819 00:35:16,160 --> 00:35:20,670 A svaki od tih elemenata, a svaki od ti krugovi ili kose crte - Slash 820 00:35:20,670 --> 00:35:23,970 predstavlja null - svaki od tih pokazivače očito pokazuje da 821 00:35:23,970 --> 00:35:25,730 što je struktura podataka? 822 00:35:25,730 --> 00:35:26,890 Popis povezani. 823 00:35:26,890 --> 00:35:30,530 >> Tako sada imamo mogućnost za Teško kod u našem programu 824 00:35:30,530 --> 00:35:32,010 veličina tablice. 825 00:35:32,010 --> 00:35:35,360 U ovom slučaju, znamo da je nikada nije više od 31 dana u mjesecu. 826 00:35:35,360 --> 00:35:38,480 Dakle, teško kodiranje vrijednost kao 31. je razumni u tom kontekstu. 827 00:35:38,480 --> 00:35:42,700 U kontekstu imena, tvrdi kodiranja 26 Nije nerazumno da Narodna 828 00:35:42,700 --> 00:35:46,340 samo nazivi početi s, primjerice, abeceda uključuje do Z. 829 00:35:46,340 --> 00:35:50,180 >> Mi može strpati ih sve u tim podacima Struktura tako dugo dok, kada smo dobili 830 00:35:50,180 --> 00:35:55,330 sudara, mi ne stavi imena ovdje, smo, umjesto da od tih stanica 831 00:35:55,330 --> 00:36:00,270 ne kao nizovi sami, već kao upućuje na, primjerice, Alice. 832 00:36:00,270 --> 00:36:03,660 A onda je Alice može imati još jedan pokazivač na drugo ime počinje sa 833 00:36:03,660 --> 00:36:06,150 A. I Bob zapravo ide ovamo. 834 00:36:06,150 --> 00:36:10,850 >> A ako postoji drugi naziv počinje sa B, on završi tamo. 835 00:36:10,850 --> 00:36:15,070 I tako svaki od elemenata ove stol dva, ako smo ovu 836 00:36:15,070 --> 00:36:17,350 malo više pametno - 837 00:36:17,350 --> 00:36:18,125 dođi - 838 00:36:18,125 --> 00:36:22,950 Ako smo ovu malo više pametno, sada postaje adaptivna podatke 839 00:36:22,950 --> 00:36:27,720 struktura, u kojoj ne postoji ograničenje tvrdi o tome koliko elemente možete umetnuti 840 00:36:27,720 --> 00:36:30,700 u nju, jer ako imate sudara, to je u redu. 841 00:36:30,700 --> 00:36:34,690 Samo ići naprijed i dodati u ono što smo vidjeli malo prije bio 842 00:36:34,690 --> 00:36:38,290 poznat kao povezane liste. 843 00:36:38,290 --> 00:36:39,690 >> Pa neka je pauzu za samo trenutak. 844 00:36:39,690 --> 00:36:42,570 Koja je vjerojatnost sudara u prvom redu? 845 00:36:42,570 --> 00:36:45,480 Točno, možda sam više razmišljam, možda Ja sam preko inženjering ovaj problem, 846 00:36:45,480 --> 00:36:46,370 jer znaš što? 847 00:36:46,370 --> 00:36:49,070 Da, ja mogu smisliti proizvoljna Primjeri off vrhu moje glave poput 848 00:36:49,070 --> 00:36:52,870 Allison i Aaron, ali u stvarnosti, dao ravnomjerniji 849 00:36:52,870 --> 00:36:56,990 ulaza, to je neki slučajni ubacivanja u strukturu podataka, što je stvarno 850 00:36:56,990 --> 00:36:58,580 vjerojatnost sudara? 851 00:36:58,580 --> 00:37:01,670 Pa ispada, to je zapravo super visoka. 852 00:37:01,670 --> 00:37:03,850 Dopustite mi generalizirati ovo Problem je što je ovaj. 853 00:37:03,850 --> 00:37:08,890 >> Dakle, u prostoriji od n CS50 učenika, što je vjerojatnost da je barem 854 00:37:08,890 --> 00:37:11,010 dva učenika u sobi imaju isti rođendan? 855 00:37:11,010 --> 00:37:13,346 Tako da je ono što. Nekoliko Hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 ljudi ovdje i nekoliko sto ljudi kod kuće i danas. 857 00:37:16,790 --> 00:37:20,670 Dakle, ako ste htjeli da se zapitamo što je vjerojatnost dvije osobe 858 00:37:20,670 --> 00:37:23,930 U ovoj sobi ima isti rođendan, možemo to shvatiti. 859 00:37:23,930 --> 00:37:26,250 A ja tvrdim zapravo postoje dvije ljudi s istim rođendan. 860 00:37:26,250 --> 00:37:29,560 >> Na primjer, bilo tko ima danas rođendan? 861 00:37:29,560 --> 00:37:31,340 Jučer? 862 00:37:31,340 --> 00:37:32,590 Sutra? 863 00:37:32,590 --> 00:37:35,980 U redu, tako da se osjeća kao da ću se morati učiniti ovaj 363 ili tako više 864 00:37:35,980 --> 00:37:39,500 puta zapravo shvatiti Ako imamo sudar. 865 00:37:39,500 --> 00:37:42,350 Ili smo samo mogli to učiniti matematički umjesto dosadnog 866 00:37:42,350 --> 00:37:43,200 to. 867 00:37:43,200 --> 00:37:44,500 I predložiti sljedeće. 868 00:37:44,500 --> 00:37:48,740 >> Tako sam predložio da smo mogli modelirati Vjerojatnost da dvije osobe imaju 869 00:37:48,740 --> 00:37:55,320 Isti rođendan kao vjerojatnost od 1 minus vjerojatnost nitko ima 870 00:37:55,320 --> 00:37:56,290 isti rođendan. 871 00:37:56,290 --> 00:37:59,960 Dakle, da biste dobili ovaj, a to je samo fancy način pisanja ovog, za 872 00:37:59,960 --> 00:38:03,090 Prva osoba u sobi, on ili ona može imati jednu od moguće 873 00:38:03,090 --> 00:38:07,370 rođendana uz pretpostavku 365 dana u godini, s isprike osoba s 874 00:38:07,370 --> 00:38:08,760 29. veljače rođendan. 875 00:38:08,760 --> 00:38:13,470 >> Dakle, prva osoba u ovoj sobi je besplatan imati bilo koji broj rođendane 876 00:38:13,470 --> 00:38:18,280 od 365 mogućnosti, tako da mi ćemo to učiniti 365 podijeljeno sa 365, 877 00:38:18,280 --> 00:38:18,990 što je jedan. 878 00:38:18,990 --> 00:38:22,700 Sljedeća osoba u sobi, ako je cilj je izbjeći sudar, mogu samo 879 00:38:22,700 --> 00:38:26,460 ima njegov ili njezin rođendan o tome mnogi različiti mogući dana? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Dakle Drugi član u ovom izrazu je u biti radiš tu matematiku za nas 882 00:38:31,430 --> 00:38:33,460 oduzimanjem off jedan mogući dan. 883 00:38:33,460 --> 00:38:36,390 A onda sljedeći dan, sljedeći dan, Sljedeći dan do ukupnog broja 884 00:38:36,390 --> 00:38:38,100 ljudi u sobi. 885 00:38:38,100 --> 00:38:41,290 >> A ako smo onda razmislite, što je onda Vjerojatnost ne svi imaju 886 00:38:41,290 --> 00:38:45,265 jedinstvene rođendana, ali opet minus 1 da, ono što smo dobili je izraz 887 00:38:45,265 --> 00:38:47,810 koji može vrlo maštovito izgledati ovako. 888 00:38:47,810 --> 00:38:50,330 No, to je zanimljivije gledati na vizualno. 889 00:38:50,330 --> 00:38:55,120 To je shema gdje je na x-osi je broj ljudi u sobi, 890 00:38:55,120 --> 00:38:56,180 broj rođendane. 891 00:38:56,180 --> 00:38:59,840 Na y-osi je vjerojatnost od sudara, dvoje ljudi 892 00:38:59,840 --> 00:39:01,230 ima isti rođendan. 893 00:39:01,230 --> 00:39:05,020 >> I takeaway iz ove krivulje da čim dođete do nekih 40 894 00:39:05,020 --> 00:39:11,110 studentima, ti si se na 90% vjerojatnosti combinatorically od dva 895 00:39:11,110 --> 00:39:13,550 ljudi ili više imaju isti rođendan. 896 00:39:13,550 --> 00:39:18,600 A kad dođete do sviđa 58 ljudi to je gotovo 100% od priliku dva 897 00:39:18,600 --> 00:39:21,310 ljudi u sobi će imati Isti rođendan, iako postoji 898 00:39:21,310 --> 00:39:26,650 365 ili 366 moguće kante i samo 58 ljudi u sobi. 899 00:39:26,650 --> 00:39:29,900 Samo statistički vjerojatno ćete dobili sudara, koji se u kratkom 900 00:39:29,900 --> 00:39:31,810 motivira ovu raspravu. 901 00:39:31,810 --> 00:39:35,890 To čak i ako mi se sviđa ovdje, a početi s ovih lanaca, mi smo još uvijek 902 00:39:35,890 --> 00:39:36,950 će imati sudara. 903 00:39:36,950 --> 00:39:42,710 >> Tako da moli pitanje, što je Trošak radi umetanja i brisanja 904 00:39:42,710 --> 00:39:44,850 u strukture podataka kao što je ovaj? 905 00:39:44,850 --> 00:39:46,630 Pa neka mi predložiti - 906 00:39:46,630 --> 00:39:51,570 i neka mi se vratiti na zaslonu tijekom ovdje - ako smo n elemenata u 907 00:39:51,570 --> 00:39:56,330 popis pa ako nastojimo umetnuti n elemenata, a mi smo 908 00:39:56,330 --> 00:39:58,050 koliko je ukupno kante? 909 00:39:58,050 --> 00:40:03,450 Recimo 31 Ukupno kante u slučaju rođendane. 910 00:40:03,450 --> 00:40:09,240 Što je maksimalno trajanje jedne od tih lanaca potencijalno? 911 00:40:09,240 --> 00:40:12,670 >> Ako opet postoji 31 ​​moguće rođendana u određenom mjesecu. 912 00:40:12,670 --> 00:40:14,580 I mi smo samo nakupina svima - 913 00:40:14,580 --> 00:40:15,580 zapravo to je glupo primjer. 914 00:40:15,580 --> 00:40:16,960 Učinimo 26 umjesto. 915 00:40:16,960 --> 00:40:20,890 Dakle, ako su zapravo ljudi čija su imena početi s do Z, dajući 916 00:40:20,890 --> 00:40:22,780 nas 26 mogućnosti. 917 00:40:22,780 --> 00:40:25,920 I mi smo pomoću strukture podataka kao što su jednom smo upravo vidjeli, pri čemu smo 918 00:40:25,920 --> 00:40:30,210 niz pokazivača, od kojih svaki ukazuje na povezanoj liste, gdje je 919 00:40:30,210 --> 00:40:32,360 Prvi popis je svatko s imenom Alice. 920 00:40:32,360 --> 00:40:35,770 Drugi popis je svaka s ime počinje sa A, s početkom 921 00:40:35,770 --> 00:40:36,980 s B, i tako dalje. 922 00:40:36,980 --> 00:40:41,020 >> Što je vjerojatno duljina svakog od ti popisi ako pretpostavimo lijepo čisti 923 00:40:41,020 --> 00:40:45,410 distribucija imena kroz Z u cijeloj strukturi podataka? 924 00:40:45,410 --> 00:40:50,210 Tu je n ljudi u strukturi podataka podijeljeno 26., ako su lijepo 925 00:40:50,210 --> 00:40:52,110 rasporediti tijekom cijele struktura podataka. 926 00:40:52,110 --> 00:40:54,970 Tako da je duljina svakog od tih Lanci je n podijeljen 26.. 927 00:40:54,970 --> 00:40:57,380 No, u velikom O zapisu, što je to? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Što je to zapravo? 930 00:41:02,440 --> 00:41:04,150 Dakle, to je stvarno samo n, zar ne? 931 00:41:04,150 --> 00:41:06,620 Zato što smo rekli u prošlosti, uh kako ste podijeliti po 26 godina. 932 00:41:06,620 --> 00:41:08,710 Da, u stvarnosti to je brži. 933 00:41:08,710 --> 00:41:12,720 No, u teoriji, to nije bitno sve što brži. 934 00:41:12,720 --> 00:41:16,040 >> Dakle, mi se ne čini da se sve to puno bliže tom sveti gral. 935 00:41:16,040 --> 00:41:17,750 U stvari, to je samo linearno vrijeme. 936 00:41:17,750 --> 00:41:20,790 Zapravo, u ovom trenutku, zašto ne bismo samo koristiti jedan ogroman povezanog popisa? 937 00:41:20,790 --> 00:41:23,510 Zašto ne samo koristiti jedan veliki Niz za pohranu imena 938 00:41:23,510 --> 00:41:25,010 svi u prostoriji? 939 00:41:25,010 --> 00:41:28,280 Pa, postoji li još uvijek nešto uvjerljiv o hash tablicu? 940 00:41:28,280 --> 00:41:30,810 Ima li još nešto uvjerljiv o strukturi podataka 941 00:41:30,810 --> 00:41:33,940 da izgleda ovako? 942 00:41:33,940 --> 00:41:35,182 Ovo. 943 00:41:35,182 --> 00:41:37,050 >> STUDENT: [nečujno]. 944 00:41:37,050 --> 00:41:39,840 >> ZVUČNI 1: Točno, i opet ako je samo linearni vremenski algoritam, te 945 00:41:39,840 --> 00:41:42,780 linearni vremenski struktura podataka, zašto ne ja Samo pohraniti svačije ime u big 946 00:41:42,780 --> 00:41:44,210 polje, ili u velikom povezan popisu? 947 00:41:44,210 --> 00:41:47,010 I prestani raditi CS tako puno teže nego što treba biti? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Što je uvjerljiv o tome, čak i iako sam ga izgrebao out? 950 00:41:53,190 --> 00:41:54,930 >> STUDENT: [nečujno]. 951 00:41:54,930 --> 00:41:57,040 >> ZVUČNI 1: uguravanje nisu? 952 00:41:57,040 --> 00:41:58,140 Skupo više. 953 00:41:58,140 --> 00:42:03,390 Dakle ubacivanje potencijalno mogla dalje biti konstantna vrijeme, čak i ako vaše podatke 954 00:42:03,390 --> 00:42:07,910 struktura izgleda ovako, niz pokazivače, od kojih je svaki pokazuje na 955 00:42:07,910 --> 00:42:09,550 potencijalno linked list. 956 00:42:09,550 --> 00:42:15,220 Kako bi ste postigli konstantna Vrijeme umetanje imena? 957 00:42:15,220 --> 00:42:16,280 Staviti ga u prednjem, zar ne? 958 00:42:16,280 --> 00:42:19,290 >> Ako ćemo žrtvovati pogodak dizajn iz ranije, u kojoj smo htjeli zadržati 959 00:42:19,290 --> 00:42:22,650 svačija ime, primjerice, sortirati, ili sve od brojeva na pozornici razvrstani, 960 00:42:22,650 --> 00:42:25,020 Pretpostavimo da imamo nerazvrstani povezani popis. 961 00:42:25,020 --> 00:42:29,960 To košta samo nam jedan ili dva koraka, kao u slučaju Ben i Briana 962 00:42:29,960 --> 00:42:32,750 ranije, umetnuti element na početak popisa. 963 00:42:32,750 --> 00:42:36,090 Dakle, ako mi nije stalo sortiranja sve od nazivima koji počinju ili sve 964 00:42:36,090 --> 00:42:39,660 nazivi počinju sa B, možemo dalje postigla konstantna umetanje vrijeme. 965 00:42:39,660 --> 00:42:43,900 Sada se gleda Alice ili Bob ili bilo koje ime općenito je još uvijek ono? 966 00:42:43,900 --> 00:42:48,100 To je velika O n podijeljeno 26., u idealan slučaj u kojem su svi ravnomjerno 967 00:42:48,100 --> 00:42:51,190 distribuira, gdje je kao i mnogi ih jer postoji Z-, što je vjerojatno 968 00:42:51,190 --> 00:42:52,220 nerealno. 969 00:42:52,220 --> 00:42:53,880 Ali to je uvijek linearno. 970 00:42:53,880 --> 00:42:57,120 >> Ali ovdje smo došli natrag do točke od asimptotičke zapis bića 971 00:42:57,120 --> 00:42:58,600 teoretski istina. 972 00:42:58,600 --> 00:43:02,960 No, u stvarnom svijetu, ako ja tvrdim da je moj program može učiniti nešto 26 puta 973 00:43:02,960 --> 00:43:06,210 brže od tvoje, čiji je program ćete radije koristite? 974 00:43:06,210 --> 00:43:09,660 Tvoje ili moje, što je 26 puta brže? 975 00:43:09,660 --> 00:43:14,320 Realno, osoba čije je 26. puta brže, čak i ako je teorijski 976 00:43:14,320 --> 00:43:18,790 naši algoritmi izvoditi u isto asimptotičnu prikazivati ​​vrijeme. 977 00:43:18,790 --> 00:43:20,940 >> Dopustite mi da predlaže drugačije Rješenje uopce. 978 00:43:20,940 --> 00:43:24,380 A ako to ne blow your mind, smo iz strukture podataka. 979 00:43:24,380 --> 00:43:27,420 Dakle, to je to trie - 980 00:43:27,420 --> 00:43:28,520 vrsta glupo ime. 981 00:43:28,520 --> 00:43:32,880 Ona dolazi iz retrievals, a riječ precizirao trie, t-r-I-e, zbog 982 00:43:32,880 --> 00:43:34,450 Tečaj dohvat zvuči kao trie. 983 00:43:34,450 --> 00:43:36,580 Ali to je povijest od riječi trie. 984 00:43:36,580 --> 00:43:40,980 >> Dakle trie je doista neka vrsta drveta, i to je također igrati na tom riječju. 985 00:43:40,980 --> 00:43:46,330 I iako ne sasvim mogu vidjeti s ovim prikazom, trie je 986 00:43:46,330 --> 00:43:50,790 Stablo strukturiran, poput obiteljskog stabla s jedan predak na vrhu i puno 987 00:43:50,790 --> 00:43:54,530 unučadi i praunuci što je lišće na dnu. 988 00:43:54,530 --> 00:43:58,100 No, svaki čvor u trie je polje. 989 00:43:58,100 --> 00:44:00,680 I to je u niz - i neka je pojednostavljuju za trenutak - to je 990 00:44:00,680 --> 00:44:04,600 polje, u ovom slučaju, na veličinu 26, gdje je svaki čvor je opet niz veličine 991 00:44:04,600 --> 00:44:09,000 26, u kojoj se nultoga element u koji polje predstavlja, a posljednji 992 00:44:09,000 --> 00:44:11,810 element u svaki takav Niz predstavlja Z. 993 00:44:11,810 --> 00:44:15,520 >> Dakle, ja predlažem, a zatim, da su ti podaci Struktura, poznat kao trie, može biti 994 00:44:15,520 --> 00:44:17,600 Također se koristi za pohranu riječi. 995 00:44:17,600 --> 00:44:21,740 Vidjeli smo trenutak prije kako bismo mogli pohraniti riječi, ili u ovom slučaju imena, a mi 996 00:44:21,740 --> 00:44:25,440 ranije vidjeli kako možemo pohraniti brojeve, ali ako ćemo se usredotočiti na imena ili nizovi 997 00:44:25,440 --> 00:44:27,460 ovdje, ono što je zanimljivo primijetiti. 998 00:44:27,460 --> 00:44:32,210 Ja tvrdim da je ime Maxwell unutar ove strukture podataka. 999 00:44:32,210 --> 00:44:33,730 Gdje vidite Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> STUDENT: [nečujno]. 1001 00:44:35,140 --> 00:44:36,240 >> ZVUČNI 1: Na lijevoj strani. 1002 00:44:36,240 --> 00:44:39,910 Dakle, ono što je zanimljivo s ovim podacima Struktura je umjesto trgovine na 1003 00:44:39,910 --> 00:44:46,200 string M-A-X-W-E-L-L backslash nula, sve contiguously, što ste to učiniti umjesto 1004 00:44:46,200 --> 00:44:46,890 slijedi. 1005 00:44:46,890 --> 00:44:50,510 Ako je ovo trie kao i strukture podataka, svaki od čvorova čija je ponovno polje, 1006 00:44:50,510 --> 00:44:54,650 i želite pohraniti Maxwell, najprije Indeks pa je korijen u čvor, tako da 1007 00:44:54,650 --> 00:44:57,810 govoriti, najviši čvor, na licu mjesta M, desno, tako 1008 00:44:57,810 --> 00:44:59,160 otprilike u sredini. 1009 00:44:59,160 --> 00:45:03,740 A onda od tamo, slijedite pokazivač na dijete čvorova, da se tako izrazim. 1010 00:45:03,740 --> 00:45:06,150 Dakle, u smislu obiteljskog stabla, slijedite ga prema dolje. 1011 00:45:06,150 --> 00:45:09,030 I da vas dovesti do drugog čvora na lijevoj strani, koji je 1012 00:45:09,030 --> 00:45:10,540 samo još jedan niz. 1013 00:45:10,540 --> 00:45:14,710 >> A onda, ako želite pohraniti Maxwell, vam pokazivač koji predstavlja 1014 00:45:14,710 --> 00:45:16,430 , Što je ovaj ovdje. 1015 00:45:16,430 --> 00:45:17,840 Zatim idete na sljedeći čvor. 1016 00:45:17,840 --> 00:45:20,100 I napomena - to je razlog zašto je slika Malo obmanjuje - 1017 00:45:20,100 --> 00:45:21,990 ovaj čvor izgledaju super maleni. 1018 00:45:21,990 --> 00:45:26,050 No, s desne strane je ovo Y i Z. To je samo autor je odrezan 1019 00:45:26,050 --> 00:45:27,630 slika tako da možete zapravo vidjeti stvari. 1020 00:45:27,630 --> 00:45:30,400 Inače ovu sliku će biti jako široka. 1021 00:45:30,400 --> 00:45:36,180 Dakle, sada ste indeksa na mjesto X, a zatim W, A E, onda L, zatim L. Onda što je 1022 00:45:36,180 --> 00:45:37,380 znatiželja? 1023 00:45:37,380 --> 00:45:41,250 >> Pa, ako ćemo koristiti ovu vrstu new preuzmu kako pohraniti string u 1024 00:45:41,250 --> 00:45:44,500 struktura podataka, još uvijek je potrebno suštini prekrižite u podacima 1025 00:45:44,500 --> 00:45:47,250 struktura koja riječ završava ovdje. 1026 00:45:47,250 --> 00:45:50,830 Drugim riječima, svaki od tih čvorova nekako mora zapamtiti da smo 1027 00:45:50,830 --> 00:45:53,500 zapravo slijedi sve ove naputke i ostavljajući malo 1028 00:45:53,500 --> 00:45:58,370 prezla na dolje ovdje ove Struktura ukazati M-A-X-W-E-l-L 1029 00:45:58,370 --> 00:46:00,230 Upravo u tom strukture podataka. 1030 00:46:00,230 --> 00:46:02,040 >> Tako bismo mogli napraviti na sljedeći način. 1031 00:46:02,040 --> 00:46:06,810 Svaka od čvorova u slici samo mi pila ima jedan, niz veličine 27. 1032 00:46:06,810 --> 00:46:10,550 I to je sada 27, jer se u p postavili šest, mi zapravo ću ti apostrof, 1033 00:46:10,550 --> 00:46:13,590 tako da možemo imati nazive poput O'Reilly i drugi sa apostrofe. 1034 00:46:13,590 --> 00:46:14,820 No, ista ideja. 1035 00:46:14,820 --> 00:46:17,710 Svaki od tih elemenata u niz ukazuje na struct 1036 00:46:17,710 --> 00:46:19,320 čvora, pa samo čvor. 1037 00:46:19,320 --> 00:46:21,430 Dakle, ovo je jako podsjeća našeg povezanog popisa. 1038 00:46:21,430 --> 00:46:24,550 >> I onda imam Boolean, kojoj ću nazovite riječ, koja samo što će biti 1039 00:46:24,550 --> 00:46:29,120 Istina, ako riječ završava na ovo čvor u stablu. 1040 00:46:29,120 --> 00:46:32,870 To je učinkovito predstavlja malo Trokut smo vidjeli maloprije. 1041 00:46:32,870 --> 00:46:37,190 Dakle, ako je riječ završava na taj čvor u stabla, to polje će riječ biti istina, 1042 00:46:37,190 --> 00:46:41,990 koji je koncepcijski provjere off, ili mi smo izradu ovog trokuta, da postoji 1043 00:46:41,990 --> 00:46:44,080 je riječ ovdje. 1044 00:46:44,080 --> 00:46:45,120 >> Dakle, ovo je trie. 1045 00:46:45,120 --> 00:46:48,540 I sad je pitanje, što je njegova prikazivati ​​vrijeme? 1046 00:46:48,540 --> 00:46:49,930 Je li to veliki O n? 1047 00:46:49,930 --> 00:46:51,410 Je li to nešto drugo? 1048 00:46:51,410 --> 00:46:57,330 Pa, ako ste n imena u ove podatke Struktura, Maxwell-a samo jedan od 1049 00:46:57,330 --> 00:47:02,330 ih, što je dužina trajanja umetanja ili pronalaženje Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Što je trajanje umetanja Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Ako postoji n druga imena Već u tablici? 1053 00:47:11,740 --> 00:47:12,507 Da? 1054 00:47:12,507 --> 00:47:15,429 >> STUDENT: [nečujno]. 1055 00:47:15,429 --> 00:47:17,550 >> ZVUČNI 1: Da, to je duljina Ime je, zar ne? 1056 00:47:17,550 --> 00:47:24,420 Tako da M-a-X-W-e-l-l tako da se osjeća kao što je ovaj Algoritam je velika O od sedam. 1057 00:47:24,420 --> 00:47:26,580 Sada, naravno, ime će biti različite duljine. 1058 00:47:26,580 --> 00:47:27,380 Možda je to kratko ime. 1059 00:47:27,380 --> 00:47:28,600 Možda to nije ime. 1060 00:47:28,600 --> 00:47:33,390 No, ono što je ključno je da To je stalni broj. 1061 00:47:33,390 --> 00:47:36,810 A možda to zapravo nije konstantna, Ali Bog, ako je realno, u 1062 00:47:36,810 --> 00:47:41,570 rječnik, vjerojatno postoji neki limit o broju slova u 1063 00:47:41,570 --> 00:47:43,820 ime osobe u određenoj zemlji. 1064 00:47:43,820 --> 00:47:46,940 >> I tako možemo pretpostaviti da vrijednost je konstantna. 1065 00:47:46,940 --> 00:47:47,750 Ja ne znam što je to. 1066 00:47:47,750 --> 00:47:50,440 To je vjerojatno veći od mislimo da je. 1067 00:47:50,440 --> 00:47:52,720 Budući da uvijek postoji neki kutak Slučaj s ludim dugo ime. 1068 00:47:52,720 --> 00:47:56,360 Dakle, nazovimo ga k, ali to je još uvijek konstantna prilici, jer svaka 1069 00:47:56,360 --> 00:48:00,190 ime u svijetu, barem u određenoj zemlji, je da dužina ili 1070 00:48:00,190 --> 00:48:01,780 kraći, tako da je stalna. 1071 00:48:01,780 --> 00:48:04,490 No, kad smo rekli nešto veliko O konstantne vrijednosti, što je to 1072 00:48:04,490 --> 00:48:07,760 stvarno odgovara? 1073 00:48:07,760 --> 00:48:10,420 To je stvarno ista stvar kako kaže stalnu vrijeme. 1074 00:48:10,420 --> 00:48:11,530 >> Sada smo vrsta varanja, zar ne? 1075 00:48:11,530 --> 00:48:15,340 Mi smo vrsta utjecati neke teorije Ovdje je reći da je dobro, kako je od k 1076 00:48:15,340 --> 00:48:17,450 zapravo samo naručiti od jedne, i to je stalno vremena. 1077 00:48:17,450 --> 00:48:18,200 Ali to je stvarno. 1078 00:48:18,200 --> 00:48:22,550 Budući da je ključ uvid ovdje je da ako smo n imena već u to 1079 00:48:22,550 --> 00:48:26,010 struktura podataka, a mi insert Maxwell, je količina vremena koje je potrebno da nam 1080 00:48:26,010 --> 00:48:29,530 umetnite Maxwell uopće zahvaćena po tome koliko drugi ljudi 1081 00:48:29,530 --> 00:48:31,100 u strukturi podataka? 1082 00:48:31,100 --> 00:48:31,670 Ne čini se. 1083 00:48:31,670 --> 00:48:36,280 Ako sam imala milijardu više elemenata ove trie, a zatim umetnite Maxwell, je 1084 00:48:36,280 --> 00:48:38,650 on uopće utjecati? 1085 00:48:38,650 --> 00:48:39,050 Ne. 1086 00:48:39,050 --> 00:48:42,950 I to je za razliku od bilo kojeg od podataka dan Strukture koje smo vidjeli do sada, gdje je 1087 00:48:42,950 --> 00:48:46,820 vrijeme trajanja svog algoritma je posve neovisno o tome koliko 1088 00:48:46,820 --> 00:48:51,430 stvar je ili nije već u toj strukturi podataka. 1089 00:48:51,430 --> 00:48:54,650 >> I tako s tim pruža vam je sada Prilika za p set šest, što će 1090 00:48:54,650 --> 00:48:58,310 ponovno uključiti provedbu svom alat za provjeru pravopisa, čitanje u 150.000 1091 00:48:58,310 --> 00:49:01,050 Riječi, kako najbolje pohraniti da nije nužno očito. 1092 00:49:01,050 --> 00:49:04,030 I iako sam težio pronaći Sveti Gral, ja ne 1093 00:49:04,030 --> 00:49:05,330 tvrde da je trie. 1094 00:49:05,330 --> 00:49:09,810 U stvari, hash tablicu može vrlo dobro dokazati da će biti puno učinkovitiji. 1095 00:49:09,810 --> 00:49:10,830 Ali oni su samo - 1096 00:49:10,830 --> 00:49:14,620 to je samo jedan od dizajnerskih odluka ćete morati napraviti. 1097 00:49:14,620 --> 00:49:18,920 >> No, u zatvaranju uzmimo 50-ak sekundi za zaviriti u ono što se nalazi 1098 00:49:18,920 --> 00:49:22,190 uoči sljedećeg tjedna i dalje smo tranziciji iz ovog naredbenog retka 1099 00:49:22,190 --> 00:49:26,220 svijeta, ako C programe na stvari webu temelji i jezici poput PHP i 1100 00:49:26,220 --> 00:49:30,350 JavaScript i internet sama, protokole kao što su HTTP, što ste 1101 00:49:30,350 --> 00:49:32,870 uzeti zdravo za gotovo već godinama Sada, i upisali najviše svaki 1102 00:49:32,870 --> 00:49:34,440 dan, možda, ili vidjeli. 1103 00:49:34,440 --> 00:49:37,420 A mi ćemo početi guliti natrag slojevi što je internet. 1104 00:49:37,420 --> 00:49:40,650 A ono što je kod koji pozadini današnji alata. 1105 00:49:40,650 --> 00:49:43,230 Tako 50 sekundi ovog teaser ovdje. 1106 00:49:43,230 --> 00:49:46,570 Dajem vam ratnicima Net. 1107 00:49:46,570 --> 00:49:51,370 >> [Video reprodukciju] 1108 00:49:51,370 --> 00:49:56,764 >> -On je došao s porukom. 1109 00:49:56,764 --> 00:50:00,687 Uz protokola samo njegov. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 On je došao na svijet okrutne firewall, nemarne routera, i opasnosti daleko 1112 00:50:19,780 --> 00:50:22,600 gora od smrti. 1113 00:50:22,600 --> 00:50:23,590 On je brz. 1114 00:50:23,590 --> 00:50:25,300 On je jak. 1115 00:50:25,300 --> 00:50:27,700 On je TCPIP. 1116 00:50:27,700 --> 00:50:30,420 I on je dobio svoju adresu. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Ratnici Net. 1119 00:50:34,590 --> 00:50:35,290 >> [END video reprodukciju] 1120 00:50:35,290 --> 00:50:38,070 >> ZVUČNI 1: Tako je internet radit će od sljedećeg tjedna. 1121 00:50:38,070 --> 00:50:40,406