1 00:00:00,000 --> 00:00:03,423 >> [MUSIC SPILLE] 2 00:00:03,423 --> 00:00:05,380 3 00:00:05,380 --> 00:00:08,210 >> ANDI PENG: Velkommen til uke 6 av delen. 4 00:00:08,210 --> 00:00:11,620 Vi avvek fra vår standard § tid tirsdag 5 00:00:11,620 --> 00:00:14,130 ettermiddag til denne herlige søndag morgen. 6 00:00:14,130 --> 00:00:17,330 Takk for alle som kom til meg i dag, men seriøst, 7 00:00:17,330 --> 00:00:18,170 en runde med applaus. 8 00:00:18,170 --> 00:00:20,600 >> Det er en ganske stor innsats. 9 00:00:20,600 --> 00:00:23,600 Jeg nesten ikke selv gjøre det opp i tide, men det var OK. 10 00:00:23,600 --> 00:00:27,520 Så jeg vet at alle dere har nettopp gjort det til quiz. 11 00:00:27,520 --> 00:00:30,370 Først av alt, velkommen til baksiden av det. 12 00:00:30,370 --> 00:00:32,917 >> Dernest vil vi snakke om det. 13 00:00:32,917 --> 00:00:34,000 Vi skal snakke om det quiz. 14 00:00:34,000 --> 00:00:35,700 Vi skal snakke om hvordan du gjør i klassen. 15 00:00:35,700 --> 00:00:36,550 Du vil være i orden. 16 00:00:36,550 --> 00:00:39,080 Jeg har dine quizzer for du på slutten av her, 17 00:00:39,080 --> 00:00:42,120 så hvis dere ønsker å ta en ser på det, helt greit. 18 00:00:42,120 --> 00:00:46,590 >> Så raskt før vi begynner, jo agenda for i dag er som følger. 19 00:00:46,590 --> 00:00:48,430 Som du kan se, er vi utgangspunktet rask avfyring 20 00:00:48,430 --> 00:00:52,120 gjennom en hel haug med datastrukturer virkelig, virkelig, virkelig raskt. 21 00:00:52,120 --> 00:00:54,380 Så som sådan, vil det ikke være super interaktiv dag. 22 00:00:54,380 --> 00:00:59,620 Det vil bare være meg slags rope Ting som du, og hvis jeg forvirre deg, 23 00:00:59,620 --> 00:01:02,680 hvis jeg går for fort, gi meg beskjed. 24 00:01:02,680 --> 00:01:05,200 De er bare ulike data strukturer, og som en del 25 00:01:05,200 --> 00:01:07,070 av PSet for dette kommende uke, vil du 26 00:01:07,070 --> 00:01:10,340 bli bedt om å gjennomføre en av dem, kanskje to av them-- to av dem 27 00:01:10,340 --> 00:01:12,319 i PSet. 28 00:01:12,319 --> 00:01:14,610 OK, så jeg skal bare starte med noen kunngjøringer. 29 00:01:14,610 --> 00:01:19,070 Vi vil gå over stabler og køer flere i dybde enn det vi gjorde før quizen. 30 00:01:19,070 --> 00:01:20,990 Vi vil gå over linket liste opp igjen, nok en gang, 31 00:01:20,990 --> 00:01:23,899 mer i dybden enn hva vi hadde før quizen. 32 00:01:23,899 --> 00:01:26,440 Og så får vi snakke om hasj tabeller, trær og prøver, som 33 00:01:26,440 --> 00:01:28,890 er alle ganske nødvendig for PSet. 34 00:01:28,890 --> 00:01:32,925 Og så får vi gå over noen nyttige tips for pset5. 35 00:01:32,925 --> 00:01:37,360 >> OK, så quiz 0. 36 00:01:37,360 --> 00:01:41,090 Gjennomsnittlig var 58%. 37 00:01:41,090 --> 00:01:45,370 Det var svært lav, og så dere alle gjorde det veldig, veldig godt i samsvar 38 00:01:45,370 --> 00:01:46,510 med denne. 39 00:01:46,510 --> 00:01:49,970 >> Ganske mye, er tommelfingerregel hvis du er i løpet av et standardavvik av middelverdien 40 00:01:49,970 --> 00:01:52,990 spesielt siden vi er i en mindre comfy delen, er du helt fint. 41 00:01:52,990 --> 00:01:54,120 Du er på rett spor. 42 00:01:54,120 --> 00:01:55,190 Livet er godt. 43 00:01:55,190 --> 00:01:58,952 >> Jeg vet det er skummelt å tenke på at Jeg fikk som en 40% på denne quizen. 44 00:01:58,952 --> 00:02:00,160 Jeg kommer til å mislykkes denne klassen. 45 00:02:00,160 --> 00:02:02,243 Jeg lover deg, du er ikke kommer til å mislykkes klassen. 46 00:02:02,243 --> 00:02:03,680 Du er helt greit. 47 00:02:03,680 --> 00:02:06,850 >> For de av dere som fikk over middelverdien, imponerende, imponerende, 48 00:02:06,850 --> 00:02:08,780 lignende, seriøst godt gjort. 49 00:02:08,780 --> 00:02:09,689 Jeg har dem med meg. 50 00:02:09,689 --> 00:02:11,730 Føl deg fri til å komme og hente dem på slutten av delen. 51 00:02:11,730 --> 00:02:14,520 Gi meg beskjed hvis du har noen problemer, spørsmål med dem. 52 00:02:14,520 --> 00:02:17,204 Hvis vi legger opp poengsummen din galt, gi oss beskjed. 53 00:02:17,204 --> 00:02:21,240 >> OK, så pset5, er dette en virkelig merkelig uke for Yale i den forstand 54 00:02:21,240 --> 00:02:24,240 at vår PSet skyldes Onsdag på middag inkludert 55 00:02:24,240 --> 00:02:27,317 late dager, så det er faktisk teoretisk grunn tirsdag midt på dagen. 56 00:02:27,317 --> 00:02:29,150 Sannsynligvis ingen ferdig på tirsdag midt på dagen. 57 00:02:29,150 --> 00:02:30,830 Det er helt greit. 58 00:02:30,830 --> 00:02:33,700 Vi kommer til å ha kontortid i kveld samt mandag kveld. 59 00:02:33,700 --> 00:02:36,810 Og alle delene av denne uken vil faktisk bli omgjort til workshops, 60 00:02:36,810 --> 00:02:38,800 så gjerne stikke innom noen del du vil, 61 00:02:38,800 --> 00:02:42,810 og de vil være slags mini-PSet workshops for hjelp på det. 62 00:02:42,810 --> 00:02:45,620 Så som sådan, er dette den eneste delen hvor vi undervisningsmateriell. 63 00:02:45,620 --> 00:02:49,220 Alle de andre delene vil være fokus utelukkende på hjelp for PSet. 64 00:02:49,220 --> 00:02:50,146 Yeah? 65 00:02:50,146 --> 00:02:52,000 >> PUBLIKUM: Hvor er kontortiden? 66 00:02:52,000 --> 00:02:56,120 >> ANDI PENG: Arbeidstid tonight-- oh, godt spørsmål. 67 00:02:56,120 --> 00:03:00,580 Jeg tror kontortiden i kveld er i Teal eller på Commons. 68 00:03:00,580 --> 00:03:02,984 Hvis du sjekker på nettet CS50 og du går til arbeidstid, 69 00:03:02,984 --> 00:03:05,650 det bør være en tidsplan som forteller deg hvor alle av dem er. 70 00:03:05,650 --> 00:03:07,954 >> Jeg vet heller i kveld eller i morgen er blågrønn, 71 00:03:07,954 --> 00:03:10,120 og jeg tror vi kan ha commons for den andre natten. 72 00:03:10,120 --> 00:03:11,020 Jeg er ikke sikker. 73 00:03:11,020 --> 00:03:11,700 Godt spørsmål. 74 00:03:11,700 --> 00:03:14,430 Sjekk på CS50. 75 00:03:14,430 --> 00:03:18,780 >> Cool, spørsmål om plan for de neste som tre dager? 76 00:03:18,780 --> 00:03:21,690 Jeg lover dere liker David sagt, dette er toppen av bakken. 77 00:03:21,690 --> 00:03:23,050 Dere er nesten der. 78 00:03:23,050 --> 00:03:24,644 Bare tre dager. 79 00:03:24,644 --> 00:03:26,310 Komme dit, og da vil vi alle komme ned. 80 00:03:26,310 --> 00:03:28,114 Vi vil ha en fin CS-fri pause. 81 00:03:28,114 --> 00:03:28,780 Velkommen tilbake. 82 00:03:28,780 --> 00:03:30,779 Vi vil dykke inn i web programmering og utvikling, 83 00:03:30,779 --> 00:03:35,150 ting som er veldig morsomt sammen til noen av de andre psets. 84 00:03:35,150 --> 00:03:37,974 Og det vil være chill, og vi vil ha mye moro. 85 00:03:37,974 --> 00:03:38,890 Vi vil ha mer godteri. 86 00:03:38,890 --> 00:03:39,730 Sorry for godteri. 87 00:03:39,730 --> 00:03:40,945 Jeg glemte godteri. 88 00:03:40,945 --> 00:03:43,310 Det var en grov morgen. 89 00:03:43,310 --> 00:03:46,340 Så dere er nesten der, og jeg er veldig stolt av dere. 90 00:03:46,340 --> 00:03:49,570 >> OK, stabler så. 91 00:03:49,570 --> 00:03:53,331 Som elsket spørsmålet om Jack og hans klær på quiz? 92 00:03:53,331 --> 00:03:53,830 Ingen? 93 00:03:53,830 --> 00:03:56,500 OK, det er fint. 94 00:03:56,500 --> 00:04:00,200 >> Så egentlig som du kan Bildet Jack, denne fyren her, 95 00:04:00,200 --> 00:04:03,350 elsker å ta klær ut av toppen av stabelen, 96 00:04:03,350 --> 00:04:05,750 og han setter den tilbake på bunken etter at han er ferdig. 97 00:04:05,750 --> 00:04:07,600 Så på denne måten, han aldri synes å være å få 98 00:04:07,600 --> 00:04:10,090 til bunnen av stable i klærne hans. 99 00:04:10,090 --> 00:04:12,600 Så denne typen beskriver den grunnleggende datastruktur 100 00:04:12,600 --> 00:04:16,610 av hvordan en stabel er implementert. 101 00:04:16,610 --> 00:04:20,060 >> I hovedsak tenker på en stable som noen stakk av gjenstander 102 00:04:20,060 --> 00:04:24,900 hvor du setter ting på toppen, og så du pop dem ut fra toppen. 103 00:04:24,900 --> 00:04:28,600 Så LIFO er akronym vi liker å use-- Sist inn, først ut. 104 00:04:28,600 --> 00:04:32,480 Og så til sist i toppen av stack er den første som kommer ut. 105 00:04:32,480 --> 00:04:34,260 Og så de to begrepene vi liker å assosiere 106 00:04:34,260 --> 00:04:36,190 med som kalles push og pop. 107 00:04:36,190 --> 00:04:39,790 Når du trykker på noe på stable, og du pop den opp igjen. 108 00:04:39,790 --> 00:04:43,422 >> Og så jeg antar dette er litt av en abstrakt begrep for de av dere 109 00:04:43,422 --> 00:04:45,630 som ønsker å se ut som en Selve gjennomføringen av denne 110 00:04:45,630 --> 00:04:46,740 i den virkelige verden. 111 00:04:46,740 --> 00:04:50,170 Hvor mange av dere har skrevet et essay kanskje som en time før det var grunn, 112 00:04:50,170 --> 00:04:54,510 og du ved et uhell slettet en enorm del av det, som ved et uhell? 113 00:04:54,510 --> 00:04:58,560 Og så hva kontrollen gjør vi bruker for å sette den tilbake? 114 00:04:58,560 --> 00:05:00,030 Kontroll-Z, ja? 115 00:05:00,030 --> 00:05:03,640 Kontroll-Z, slik at mengden av tider at Ctrl-Z har reddet livet mitt, 116 00:05:03,640 --> 00:05:08,820 har reddet meg i ræva, hver gang som er innført gjennom en stabel. 117 00:05:08,820 --> 00:05:13,020 >> I hovedsak all informasjon det er i Word-dokumentet, 118 00:05:13,020 --> 00:05:15,080 det blir presset og spratt på vilje. 119 00:05:15,080 --> 00:05:19,460 Og så egentlig når du slette noe, pop du den opp igjen. 120 00:05:19,460 --> 00:05:22,820 Og så hvis du trenger det på igjen, du skyve det, som er det Ctrl-C gjør. 121 00:05:22,820 --> 00:05:26,770 Og så virkelige verden funksjon av hvor enkelt datastruktur 122 00:05:26,770 --> 00:05:28,690 kan hjelpe med hverdagen. 123 00:05:28,690 --> 00:05:31,710 124 00:05:31,710 --> 00:05:40,150 >> Så en struct er den måten at vi faktisk lage en stabel. 125 00:05:40,150 --> 00:05:44,720 Vi skriver definere struct, og deretter Vi kaller det stable på bunnen. 126 00:05:44,720 --> 00:05:47,440 Og innen stabelen, vi har to parametere 127 00:05:47,440 --> 00:05:51,580 at vi kan egentlig manipulere, så vi har røye stjerners strenger kapasitet. 128 00:05:51,580 --> 00:05:55,150 >> Alt som den gjør er å skape en matrise 129 00:05:55,150 --> 00:05:58,835 at vi kan lagre hva du vil som vi kan bestemme sin kapasitet. 130 00:05:58,835 --> 00:06:01,990 Kapasiteten er bare maks mengde elementer vi kan sette inn i denne matrisen. 131 00:06:01,990 --> 00:06:05,660 int størrelse er telleren som holder oversikt over hvor mange elementer er for tiden 132 00:06:05,660 --> 00:06:07,850 i stabelen. 133 00:06:07,850 --> 00:06:11,860 Så da kan vi holde styr på, A, både hvor stor selve stabelen er, 134 00:06:11,860 --> 00:06:14,850 og B, hvor mye av dette stack vi fylt fordi vi ikke ønsker 135 00:06:14,850 --> 00:06:18,800 å renne over hva som vår kapasitet er. 136 00:06:18,800 --> 00:06:24,340 >> Så for eksempel, denne herlige Spørsmålet var på quiz. 137 00:06:24,340 --> 00:06:28,160 Hovedsak hvordan skal vi presse på toppen av en stabel. 138 00:06:28,160 --> 00:06:28,830 Ganske enkel. 139 00:06:28,830 --> 00:06:30,621 Hvis du ser på det, vi vil gå gjennom dette. 140 00:06:30,621 --> 00:06:32,640 Hvis [uhørbart] size-- Husk, når du 141 00:06:32,640 --> 00:06:35,300 vil ha tilgang til alle parameter innen en struct, 142 00:06:35,300 --> 00:06:40,320 du navnet på struct.parameter. 143 00:06:40,320 --> 00:06:42,720 >> I dette tilfelle s er navnet på vår stabelen. 144 00:06:42,720 --> 00:06:46,230 Vi ønsker å få tilgang til størrelse av det, så vi gjør s.size. 145 00:06:46,230 --> 00:06:50,280 Så så lenge størrelsen er ikke lik kapasitet eller så lenge 146 00:06:50,280 --> 00:06:52,940 som det er mindre enn kapasiteten, enten ville fungere her. 147 00:06:52,940 --> 00:06:57,180 >> Du vil ha tilgang til innsiden av stabelen din, så s.strings, 148 00:06:57,180 --> 00:07:00,790 og du kommer til å sette det nye nummeret som du ønsker å sette inn i det. 149 00:07:00,790 --> 00:07:05,030 La oss bare si at vi vil ønske å Sett int n på stakken, 150 00:07:05,030 --> 00:07:08,905 vi kunne gjøre s.strings, parentes, tilsvarer s.size n. 151 00:07:08,905 --> 00:07:11,030 Fordi størrelsen er der vi for tiden er i stakken 152 00:07:11,030 --> 00:07:14,590 hvis vi kommer til å presse den på, vi bare tilgang til 153 00:07:14,590 --> 00:07:17,370 hvor størrelsen er, desto nåværende fylde av stabelen, 154 00:07:17,370 --> 00:07:21,729 og vi skyver int n på den. 155 00:07:21,729 --> 00:07:24,770 Og så ønsker vi å sørge for at vi også økes størrelsen på n, 156 00:07:24,770 --> 00:07:27,436 slik at vi kan holde styr på vi har lagt til en ekstra ting å stabelen. 157 00:07:27,436 --> 00:07:29,660 Nå har vi en større størrelse. 158 00:07:29,660 --> 00:07:33,196 Betyr dette her være fornuftig å alle, hvor logisk det fungerer? 159 00:07:33,196 --> 00:07:34,160 Det var litt rask. 160 00:07:34,160 --> 00:07:39,535 161 00:07:39,535 --> 00:07:42,160 PUBLIKUM: Kan du gå over de s.stringss.strings [s.size] igjen? 162 00:07:42,160 --> 00:07:45,808 ANDI PENG: Jada, så hva gjør s.size tiden gi oss? 163 00:07:45,808 --> 00:07:47,440 PUBLIKUM: Det er den nåværende størrelse. 164 00:07:47,440 --> 00:07:50,890 ANDI PENG: Akkurat, så det gjeldende indeksen at vår størrelse er på, 165 00:07:50,890 --> 00:07:57,780 og så vi ønsker å sette den nye tall at vi ønsker å sette inn i s.size. 166 00:07:57,780 --> 00:07:58,760 Gir det mening? 167 00:07:58,760 --> 00:08:01,110 Fordi s.strings, alt som er er navnet på matrisen. 168 00:08:01,110 --> 00:08:03,510 Alt er det er tilgang til utvalg innen vår struct, 169 00:08:03,510 --> 00:08:06,030 og så hvis vi ønsker å plassere n til at indeksen, 170 00:08:06,030 --> 00:08:09,651 Vi kan bare få tilgang til det ved hjelp av brak s.size. 171 00:08:09,651 --> 00:08:10,150 Kjølig. 172 00:08:10,150 --> 00:08:13,580 173 00:08:13,580 --> 00:08:18,916 >> Greit, pop, pseudo jeg det ut for dere, men lignende konsept. 174 00:08:18,916 --> 00:08:19,790 Gir det mening? 175 00:08:19,790 --> 00:08:22,310 Hvis størrelsen er større enn null, så du 176 00:08:22,310 --> 00:08:25,350 vet at du vil ta noe ut fordi hvis størrelse ikke er 177 00:08:25,350 --> 00:08:27,620 større enn null, så du har ingenting i bunken. 178 00:08:27,620 --> 00:08:29,840 >> Slik at du bare ønsker å kjøre denne koden, kan det bare 179 00:08:29,840 --> 00:08:32,320 pop hvis det er noe å pop. 180 00:08:32,320 --> 00:08:35,830 Så hvis størrelse er større enn 0, vi minus størrelse. 181 00:08:35,830 --> 00:08:40,020 Vi minske størrelsen og deretter returnere hva er på innsiden av det fordi 182 00:08:40,020 --> 00:08:42,710 ved popping, vi ønsker å tilgang uansett er lagret 183 00:08:42,710 --> 00:08:45,694 i indeksen på toppen av stabelen. 184 00:08:45,694 --> 00:08:46,610 Alt fornuftig? 185 00:08:46,610 --> 00:08:49,693 Hvis jeg gjorde dere skrive dette ut, ville dere være i stand til å skrive det ut? 186 00:08:49,693 --> 00:08:52,029 187 00:08:52,029 --> 00:08:53,570 OK, kan dere leke seg med det. 188 00:08:53,570 --> 00:08:55,252 Ingen grunn til bekymring dersom du ikke får det. 189 00:08:55,252 --> 00:08:57,460 Vi har ikke tid til å kode det ut i dag fordi vi har 190 00:08:57,460 --> 00:08:59,959 fikk mye av disse strukturene å gå gjennom, men i hovedsak 191 00:08:59,959 --> 00:09:02,214 pseudokode, veldig, veldig lik presse. 192 00:09:02,214 --> 00:09:03,380 Bare følg langs logikk. 193 00:09:03,380 --> 00:09:06,092 Sørg for at du får tilgang til alle funksjonene i struct riktig. 194 00:09:06,092 --> 00:09:06,574 Yeah? 195 00:09:06,574 --> 00:09:09,282 >> PUBLIKUM: Vil disse lysbilder og dette hele greia være opp i dag-ish? 196 00:09:09,282 --> 00:09:11,586 ANDI PENG: Alltid, Jepp. 197 00:09:11,586 --> 00:09:13,710 Jeg kommer til å prøve å sette dette opp som en time etter. 198 00:09:13,710 --> 00:09:16,626 Jeg vil sende David, vil David prøver å sette den opp som en time etter dette. 199 00:09:16,626 --> 00:09:20,040 200 00:09:20,040 --> 00:09:25,470 >> OK, så da flytter vi inn i denne andre nydelig datastruktur som kalles en kø. 201 00:09:25,470 --> 00:09:30,140 Som dere kan se her, en køen, for britene blant oss, 202 00:09:30,140 --> 00:09:32,010 alt er det er en linje. 203 00:09:32,010 --> 00:09:34,680 Derfor i motsetning til hva du tror en stabel er, 204 00:09:34,680 --> 00:09:37,750 en kø er akkurat hva logisk tror du det er. 205 00:09:37,750 --> 00:09:41,914 Det er holdt av reglene i FIFO, som er først inn, først ut. 206 00:09:41,914 --> 00:09:43,705 Hvis du er den første en i linjen, er du 207 00:09:43,705 --> 00:09:46,230 den første som kommer ut av linjen. 208 00:09:46,230 --> 00:09:49,680 >> Så det vi liker å kalle dette er dequeueing og enqueueing. 209 00:09:49,680 --> 00:09:52,380 Hvis vi ønsker å legge til noe til vår kø, Enqueue vi. 210 00:09:52,380 --> 00:09:55,690 Hvis vi ønsker å dequeue, eller ta noe bort, dequeue vi. 211 00:09:55,690 --> 00:10:03,350 >> Så samme forstand at vi er på en måte skape fast størrelse elementer som vi 212 00:10:03,350 --> 00:10:06,500 kan lagre visse ting, men vi kan også 213 00:10:06,500 --> 00:10:10,100 endre hvor vi plasserer parametere innsiden av dem 214 00:10:10,100 --> 00:10:13,140 basert på hvilken type funksjonaliteten vi ønsker. 215 00:10:13,140 --> 00:10:16,700 Så stabler, ønsket vi den siste en, N for å være den første ut. 216 00:10:16,700 --> 00:10:19,800 Køen er vi ønsker det første i å være den første ut. 217 00:10:19,800 --> 00:10:22,510 218 00:10:22,510 --> 00:10:26,710 >> Så struct-type definere, som du kan se, 219 00:10:26,710 --> 00:10:29,470 det er litt annerledes fra hva stabelen var 220 00:10:29,470 --> 00:10:33,120 fordi ikke bare har vi å holde Sporet etter størrelse er for tiden, 221 00:10:33,120 --> 00:10:37,420 vi ønsker også å holde styr på hodet samt hvor vi er nå. 222 00:10:37,420 --> 00:10:39,580 Så jeg tror det er lettere hvis jeg tegne dette opp. 223 00:10:39,580 --> 00:10:53,270 Så la oss forestille vi har fått en kø, så la oss si at hodet er rett her. 224 00:10:53,270 --> 00:10:55,811 225 00:10:55,811 --> 00:10:58,310 Lederen av linjen, la oss bare si at er der i dag, 226 00:10:58,310 --> 00:11:01,809 og vi ønsker å sette inn noe inn i køen. 227 00:11:01,809 --> 00:11:04,350 Jeg kommer til å ringe størrelse hovedsak er det samme som hale, 228 00:11:04,350 --> 00:11:06,314 slutten av hvor køen er. 229 00:11:06,314 --> 00:11:07,730 La oss bare si størrelsen er rett her. 230 00:11:07,730 --> 00:11:14,380 231 00:11:14,380 --> 00:11:18,400 >> Så hvordan gjør man feasibly sette noe inn i en kø? 232 00:11:18,400 --> 00:11:21,000 233 00:11:21,000 --> 00:11:24,130 Hva indeksen gjør vi ønsker å plassere hvor vi ønsker å sette inn. 234 00:11:24,130 --> 00:11:29,320 Hvis dette er begynnelsen på din kø og dette er slutten av det 235 00:11:29,320 --> 00:11:31,860 eller størrelsen på den, der gjør vi ønsker å legge til neste objekt? 236 00:11:31,860 --> 00:11:32,920 >> PUBLIKUM: [uhørbart] 237 00:11:32,920 --> 00:11:35,920 ANDI PENG: Akkurat, du vil legge det avhengig av har du skrevet det. 238 00:11:35,920 --> 00:11:37,840 Enten dette er tomt eller som er blank. 239 00:11:37,840 --> 00:11:42,630 Så du ønsker å legge det sannsynligvis her fordi hvis størrelsen er-- 240 00:11:42,630 --> 00:11:50,540 om disse er alle fulle, vil du å legge det her, ikke sant? 241 00:11:50,540 --> 00:11:57,150 >> Og så det er, mens veldig, veldig enkelt, ikke helt alltid riktig 242 00:11:57,150 --> 00:12:00,690 fordi den største forskjellen mellom en kø og en stabel 243 00:12:00,690 --> 00:12:04,350 er at den kan køen faktisk manipuleres 244 00:12:04,350 --> 00:12:06,980 slik at hode endringer avhengig av hvor du vil 245 00:12:06,980 --> 00:12:08,650 I begynnelsen av køen for å starte. 246 00:12:08,650 --> 00:12:11,900 Og som et resultat, halen også kommer til å endre seg. 247 00:12:11,900 --> 00:12:14,770 Og så ta en titt på denne koden akkurat nå. 248 00:12:14,770 --> 00:12:18,620 Som dere ble også bedt om å skrive ut på quiz, enqueue. 249 00:12:18,620 --> 00:12:22,580 Kanskje vi skal snakke gjennom hvorfor svaret var hva det var. 250 00:12:22,580 --> 00:12:26,790 >> Jeg kunne ikke helt passer denne linjen på en, men i hovedsak dette stykke kode 251 00:12:26,790 --> 00:12:29,030 bør være på en linje. 252 00:12:29,030 --> 00:12:30,140 Tilbring som 30 sekunder. 253 00:12:30,140 --> 00:12:33,000 Ta en titt, og se hvorfor dette er måten som det er. 254 00:12:33,000 --> 00:12:50,030 255 00:12:50,030 --> 00:12:55,420 >> Veldig, veldig lik struct, veldig, veldig tilsvarende struktur som den forrige 256 00:12:55,420 --> 00:12:58,090 stable bortsett kanskje en kodelinje. 257 00:12:58,090 --> 00:13:01,190 Og at en linje med kode bestemmer funksjonalitet. 258 00:13:01,190 --> 00:13:03,900 Og det som virkelig skiller en kø fra en stabel. 259 00:13:03,900 --> 00:13:18,510 260 00:13:18,510 --> 00:13:22,010 >> Alle som ønsker å ta et stikk på å forklare hvorfor du har 261 00:13:22,010 --> 00:13:24,980 fikk dette komplisert ting her inne? 262 00:13:24,980 --> 00:13:27,845 Vi ser avkastningen av vår fantastisk venn modulus. 263 00:13:27,845 --> 00:13:31,020 Som dere vil snart komme å gjenkjenne i programmering, 264 00:13:31,020 --> 00:13:34,910 nesten når du trenger noe å vikle rundt noe, 265 00:13:34,910 --> 00:13:36,850 modulus kommer til å være måten å gjøre det. 266 00:13:36,850 --> 00:13:40,510 Så å vite det, er det noen som vil ha for å prøve å forklare at kodelinje? 267 00:13:40,510 --> 00:13:44,060 268 00:13:44,060 --> 00:13:47,507 Ja, alle svarene er akseptert og velkommen. 269 00:13:47,507 --> 00:13:48,840 PUBLIKUM: Snakker du til meg? 270 00:13:48,840 --> 00:13:49,506 ANDI PENG: Yeah. 271 00:13:49,506 --> 00:13:56,200 PUBLIKUM: Å, nei sorry. 272 00:13:56,200 --> 00:14:00,250 ANDI PENG: OK, så la oss gå gjennom denne koden. 273 00:14:00,250 --> 00:14:03,642 Så når du prøver å legge noe på en kø, 274 00:14:03,642 --> 00:14:08,510 i den vakre tilfelle at hodet skjer å være her, er det veldig lett for oss 275 00:14:08,510 --> 00:14:10,960 å bare gå til slutten sette inn noe, ikke sant? 276 00:14:10,960 --> 00:14:14,690 Men hele poenget med en kø er at hodet kan faktisk dynamisk 277 00:14:14,690 --> 00:14:17,280 endres avhengig av hvor vi Vil starten av vår q for å være, 278 00:14:17,280 --> 00:14:19,880 og som sådan, halen også kommer til å endre seg. 279 00:14:19,880 --> 00:14:31,100 >> Og så forestille seg at dette ikke var kø, men dette var køen. 280 00:14:31,100 --> 00:14:37,900 281 00:14:37,900 --> 00:14:39,330 La oss si at hodet er rett her. 282 00:14:39,330 --> 00:14:54,900 283 00:14:54,900 --> 00:14:56,980 La oss si at vår kø så ut som dette. 284 00:14:56,980 --> 00:15:00,190 Hvis vi ønsket å skifte der begynnelsen av linjen er, 285 00:15:00,190 --> 00:15:03,400 la oss si at vi flyttet hodet på denne måten og størrelser her. 286 00:15:03,400 --> 00:15:07,100 >> Nå ønsker vi å legge noe til denne køen, men som dere kan se, 287 00:15:07,100 --> 00:15:11,150 det er ikke så enkelt som å bare legge til hva er etter størrelsen 288 00:15:11,150 --> 00:15:13,630 fordi da vi kjører ut av grensene av våre faktiske utvalg. 289 00:15:13,630 --> 00:15:16,190 Hvor vi ønsker å virkelig legge til er her. 290 00:15:16,190 --> 00:15:18,610 Det er det fine med en kø kommer det oss, visuelt det 291 00:15:18,610 --> 00:15:22,380 ser ut som linjen går som dette, men når de lagres i en datastruktur, 292 00:15:22,380 --> 00:15:29,370 de som gir det som en syklus. 293 00:15:29,370 --> 00:15:32,360 Det brytes slags rundt til fronten på samme måte 294 00:15:32,360 --> 00:15:34,780 som en linje kan også pakke rundt avhengig av hvor du 295 00:15:34,780 --> 00:15:36,279 vil begynnelsen av linjen for å være. 296 00:15:36,279 --> 00:15:38,630 Og så hvis vi tar en se ned her, la oss 297 00:15:38,630 --> 00:15:40,880 si at vi ønsket å lage en funksjon kalt enqueue. 298 00:15:40,880 --> 00:15:43,980 Vi ønsket å legge til int n til at q. 299 00:15:43,980 --> 00:15:49,250 Hvis q.size q-- vi kaller at våre data structure-- hvis våre queue.size ikke 300 00:15:49,250 --> 00:15:52,520 lik kapasitet eller hvis det er mindre enn kapasiteten, 301 00:15:52,520 --> 00:15:55,120 q.strings er rekke innenfor vår q. 302 00:15:55,120 --> 00:15:58,380 Vi kommer til å sette som lik q.heads, 303 00:15:58,380 --> 00:16:02,730 som er rett her, pluss q.size modulus av kapasiteten, som 304 00:16:02,730 --> 00:16:04,290 vikle oss tilbake rundt her. 305 00:16:04,290 --> 00:16:08,040 >> Så i dette eksempelet, index av hodet er en, ikke sant? 306 00:16:08,040 --> 00:16:11,480 Indeksen for størrelse er 0, 1, 2, 3, 4. 307 00:16:11,480 --> 00:16:19,500 Så vi kan gjøre en pluss fire modulus av vår kapasitet som er fem. 308 00:16:19,500 --> 00:16:20,920 Hva betyr det å gi oss? 309 00:16:20,920 --> 00:16:23,270 Hva er indeksen som kommer ut av dette? 310 00:16:23,270 --> 00:16:24,080 >> PUBLIKUM: 0. 311 00:16:24,080 --> 00:16:27,870 >> ANDI PENG: 0, som skjer for å være akkurat her, 312 00:16:27,870 --> 00:16:30,640 og så vi ønsker å kunne å sette inn her. 313 00:16:30,640 --> 00:16:34,730 Og så denne ligningen her slag for bare fungerer med noen tall 314 00:16:34,730 --> 00:16:36,750 avhengig av hvor hode og din størrelse er. 315 00:16:36,750 --> 00:16:38,541 Hvis du vet hva de ting er, vet du 316 00:16:38,541 --> 00:16:43,170 akkurat der du vil sette inn hva er etter din køen. 317 00:16:43,170 --> 00:16:44,640 Betyr det fornuftig for alle? 318 00:16:44,640 --> 00:16:48,560 >> Jeg vet slag av en hjerne teaser spesielt siden dette 319 00:16:48,560 --> 00:16:50,512 kom i kjølvannet av din quiz. 320 00:16:50,512 --> 00:16:52,220 Men forhåpentligvis alle nå kan forstå 321 00:16:52,220 --> 00:16:57,800 hvorfor denne løsningen eller dette Funksjonen er slik som det er. 322 00:16:57,800 --> 00:16:59,840 Alle som litt uklar på det? 323 00:16:59,840 --> 00:17:03,471 324 00:17:03,471 --> 00:17:03,970 OK. 325 00:17:03,970 --> 00:17:07,109 326 00:17:07,109 --> 00:17:09,970 >> Og så nå, hvis du ønsket å dequeue, dette 327 00:17:09,970 --> 00:17:15,240 er der hodet ville være skiftende fordi hvis vi skulle dequeue, 328 00:17:15,240 --> 00:17:17,030 vi ikke ta av på slutten av q. 329 00:17:17,030 --> 00:17:19,130 Vi ønsker å ta av hodet, ikke sant? 330 00:17:19,130 --> 00:17:24,260 Så som et resultat, er hodet kommer til å endre, og det er derfor når du Enqueue, 331 00:17:24,260 --> 00:17:26,800 du er nødt til å holde styr på hvor hodet og størrelse 332 00:17:26,800 --> 00:17:29,450 skal være i stand til å sette i riktig posisjon. 333 00:17:29,450 --> 00:17:32,740 >> Og så når du dequeue, Jeg har også pseudo det ut. 334 00:17:32,740 --> 00:17:35,480 Gjerne hvis du vil å forsøke koding ut dette. 335 00:17:35,480 --> 00:17:36,980 Du ønsker å bevege hodet, ikke sant? 336 00:17:36,980 --> 00:17:39,320 Hvis jeg ønsket å dequeue, jeg ville flytte hodet over. 337 00:17:39,320 --> 00:17:40,800 Dette ville være leder. 338 00:17:40,800 --> 00:17:45,617 >> Og vår nåværende størrelse ville trekker fordi vi ikke lenger 339 00:17:45,617 --> 00:17:46,950 har fire elementer i tabellen. 340 00:17:46,950 --> 00:17:51,370 Vi har bare tre, og da ønsker vi å returnere det som var lagret inne 341 00:17:51,370 --> 00:17:56,260 av hodet fordi vi ønsker å ta dette verdi ut så meget lik stabelen. 342 00:17:56,260 --> 00:17:58,010 Bare du tar fra et annet sted, 343 00:17:58,010 --> 00:18:01,770 og du må overføre pekeren til annet sted som et resultat. 344 00:18:01,770 --> 00:18:03,890 Logisk, alle følge? 345 00:18:03,890 --> 00:18:05,690 Flott. 346 00:18:05,690 --> 00:18:10,156 >> OK, så vi kommer til å snakke litt mer i dybden om lenkede lister 347 00:18:10,156 --> 00:18:13,280 fordi de vil være veldig, veldig verdifull for deg i løpet av denne uken 348 00:18:13,280 --> 00:18:14,964 psets. 349 00:18:14,964 --> 00:18:17,130 Lenkede lister, som dere kan huske, alt de er 350 00:18:17,130 --> 00:18:22,570 er noder som er noder av visse verdier av både en verdi og en peker 351 00:18:22,570 --> 00:18:26,290 som er knyttet sammen av disse pekere. 352 00:18:26,290 --> 00:18:29,880 Og så struct om hvordan skaper vi en node her er vi 353 00:18:29,880 --> 00:18:33,569 har int n, som er hva verdien i en butikk eller streng n 354 00:18:33,569 --> 00:18:35,610 eller hva du vil kaller det, røye stjerne n. 355 00:18:35,610 --> 00:18:41,482 Struct node stjernen, som er pekeren som du ønsker å ha i hver node, 356 00:18:41,482 --> 00:18:43,690 du kommer til å ha det pekeren peker mot neste. 357 00:18:43,690 --> 00:18:48,207 358 00:18:48,207 --> 00:18:50,040 Du vil ha hodet av en lenket liste som er 359 00:18:50,040 --> 00:18:53,140 kommer til å peke til resten av verdiene så videre og så videre 360 00:18:53,140 --> 00:18:55,290 til du til slutt kommer til enden. 361 00:18:55,290 --> 00:18:58,040 Og denne siste noden er bare skal ikke ha en peker. 362 00:18:58,040 --> 00:18:59,952 Det kommer til å peke på null, og at når er 363 00:18:59,952 --> 00:19:01,910 du vet at du har truffet slutten av lenket liste 364 00:19:01,910 --> 00:19:04,076 er når din siste pekeren peker ikke til noe. 365 00:19:04,076 --> 00:19:06,670 366 00:19:06,670 --> 00:19:10,990 >> Så vi kommer til å gå litt mer i dybden om hvordan en ville muligens 367 00:19:10,990 --> 00:19:12,400 søke en lenket liste. 368 00:19:12,400 --> 00:19:15,460 Husk hva er noen av de ulempene med de koblede lister 369 00:19:15,460 --> 00:19:19,340 vers en rekke angående søk. 370 00:19:19,340 --> 00:19:22,565 En rekke du kan binært søk, men hvorfor kan du ikke gjøre det i en lenket liste? 371 00:19:22,565 --> 00:19:26,834 372 00:19:26,834 --> 00:19:30,320 >> PUBLIKUM: Fordi de er alle koblet til, men du ikke helt vet hvor 373 00:19:30,320 --> 00:19:31,330 [Uhørbart]. 374 00:19:31,330 --> 00:19:34,600 >> ANDI PENG: Ja, akkurat så husk at glansen av en matrise 375 00:19:34,600 --> 00:19:37,190 var det faktum at vi hadde random access memory der 376 00:19:37,190 --> 00:19:41,580 hvis jeg ville verdien fra indeks seks, kunne jeg bare si indeksen seks, 377 00:19:41,580 --> 00:19:42,407 gi meg denne verdien. 378 00:19:42,407 --> 00:19:45,240 Og det er fordi arrays er sortert i en sammenhengende plass minne 379 00:19:45,240 --> 00:19:48,020 på ett sted, mens slags lenkede lister 380 00:19:48,020 --> 00:19:52,820 er tilfeldig ispedd rundt, og den eneste måten du kan finne en 381 00:19:52,820 --> 00:19:56,890 er gjennom en peker som forteller deg adressen til der at neste node er. 382 00:19:56,890 --> 00:20:00,290 >> Og så som et resultat, er den eneste måten å søke gjennom en lenket liste 383 00:20:00,290 --> 00:20:01,560 er lineær søk. 384 00:20:01,560 --> 00:20:05,890 Fordi jeg ikke vet nøyaktig hvor 12. verdi i lenket liste er, 385 00:20:05,890 --> 00:20:08,780 Jeg må krysse helhet av at lenket liste én 386 00:20:08,780 --> 00:20:12,450 etter én fra hodet til den første noden, til den andre node, til den tredje node, 387 00:20:12,450 --> 00:20:17,690 helt ned før jeg endelig får til hvor som node jeg leter etter er. 388 00:20:17,690 --> 00:20:22,110 Og så i denne forstand, søk på en lenket liste er alltid n. 389 00:20:22,110 --> 00:20:23,040 Det er alltid n. 390 00:20:23,040 --> 00:20:25,690 Det er alltid i lineær tid. 391 00:20:25,690 --> 00:20:28,470 >> Og så koden der vi gjennomføre dette, og dette 392 00:20:28,470 --> 00:20:32,620 er litt nytt for dere siden dere Gutta har egentlig ikke snakket om eller noen gang 393 00:20:32,620 --> 00:20:35,000 sett tips i hvordan du søke gjennom pekere, 394 00:20:35,000 --> 00:20:37,670 så vi vil gå gjennom dette veldig, veldig sakte. 395 00:20:37,670 --> 00:20:40,200 Så bool søk, høyre, La oss forestille vi ønsker 396 00:20:40,200 --> 00:20:42,820 for å lage en funksjon kalt søk som returnerer true 397 00:20:42,820 --> 00:20:46,820 hvis du har funnet en verdi inne i linket liste, og den returnerer false ellers. 398 00:20:46,820 --> 00:20:50,030 Node stjerne listen er i dag bare pekeren 399 00:20:50,030 --> 00:20:52,960 til det første elementet i lenket liste. 400 00:20:52,960 --> 00:20:56,700 int n er den verdien som du er søker etter på den listen. 401 00:20:56,700 --> 00:20:58,770 >> Så node stjerners pekeren lik listen. 402 00:20:58,770 --> 00:21:00,970 Det betyr at vi er innstillingen og skape en peker 403 00:21:00,970 --> 00:21:03,592 til den første noden innsiden av listen. 404 00:21:03,592 --> 00:21:04,300 Alle med meg? 405 00:21:04,300 --> 00:21:06,530 Så hvis vi skulle gå tilbake her, ville jeg ha 406 00:21:06,530 --> 00:21:13,850 initialisert en peker som peker til hodet av hva den listen er. 407 00:21:13,850 --> 00:21:18,600 >> Og så når du kommer ned hit, mens pekeren ikke er lik null, 408 00:21:18,600 --> 00:21:22,160 slik at sløyfen er der vi kommer til å være i ettertid traversering 409 00:21:22,160 --> 00:21:25,940 resten av vår liste fordi det skjer når pekeren er lik null? 410 00:21:25,940 --> 00:21:27,550 Vi vet at vi have-- 411 00:21:27,550 --> 00:21:28,450 >> PUBLIKUM: [uhørbart] 412 00:21:28,450 --> 00:21:31,491 >> ANDI PENG: Akkurat, så vi vet at vi har nådd slutten av listen, ikke sant? 413 00:21:31,491 --> 00:21:34,470 Hvis du går tilbake hit, hver node skal peke til en annen node 414 00:21:34,470 --> 00:21:36,550 og så videre og så videre til du treffer til slutt 415 00:21:36,550 --> 00:21:41,589 halen av din lenket liste, som har en peker som bare 416 00:21:41,589 --> 00:21:43,130 peker ikke noe annet sted enn ingen. 417 00:21:43,130 --> 00:21:47,510 Og så du i utgangspunktet vet at listen er der fortsatt opp 418 00:21:47,510 --> 00:21:50,900 inntil pekeren ikke lik null fordi når den er lik null, 419 00:21:50,900 --> 00:21:53,310 du vet at det er ingen flere ting. 420 00:21:53,310 --> 00:21:56,930 >> Så det er loopen der vi er kommer til å ha selve søket. 421 00:21:56,930 --> 00:22:01,690 Og hvis pointer-- ser du den slags pilen funksjon der? 422 00:22:01,690 --> 00:22:06,930 Så hvis pekeren peker til n, hvis pekeren på n er lik lik n, 423 00:22:06,930 --> 00:22:09,180 så det betyr at hvis pekeren at du er 424 00:22:09,180 --> 00:22:13,420 søker etter på slutten av hvert node er faktisk lik verdien 425 00:22:13,420 --> 00:22:15,990 du leter etter, så du ønsker å returnere true. 426 00:22:15,990 --> 00:22:19,280 Så i utgangspunktet, hvis du er på en node som har verdien du leter etter, 427 00:22:19,280 --> 00:22:23,550 du vet at du har vært i stand til å søke. 428 00:22:23,550 --> 00:22:27,150 >> Ellers vil du sette pekeren til neste node. 429 00:22:27,150 --> 00:22:28,850 Det er hva den linjen her gjør. 430 00:22:28,850 --> 00:22:31,750 Pointer tilsvarer markøren ved siden av. 431 00:22:31,750 --> 00:22:33,360 Alle se hvordan det fungerer? 432 00:22:33,360 --> 00:22:36,580 >> Og egentlig du kommer til å like traversere helheten av listen 433 00:22:36,580 --> 00:22:41,920 nullstilling pekeren hver gang før du til slutt treffer slutten av listen. 434 00:22:41,920 --> 00:22:45,030 Og du vet at det er ingen flere noder å søke gjennom, 435 00:22:45,030 --> 00:22:47,999 og deretter kan du returnere false fordi du vet det, oh, vel, 436 00:22:47,999 --> 00:22:50,540 hvis jeg har vært i stand til å søke gjennom helheten av listen. 437 00:22:50,540 --> 00:22:54,530 Hvis du er i dette eksempelet, hvis jeg ville for å lete etter den verdi på 10, 438 00:22:54,530 --> 00:22:57,250 og jeg starter på hodet, og Jeg søker hele veien ned, 439 00:22:57,250 --> 00:23:00,550 og jeg til slutt fikk til dette, noe som en peker som peker til null, 440 00:23:00,550 --> 00:23:04,415 Jeg vet det, crap, tror jeg 10 er ikke i denne listen fordi jeg kunne ikke finne den. 441 00:23:04,415 --> 00:23:06,520 Og jeg er på slutten av listen. 442 00:23:06,520 --> 00:23:11,040 Og i så fall vet du Jeg kommer til å returnere false. 443 00:23:11,040 --> 00:23:12,900 >> La det trekke inn i en liten bit. 444 00:23:12,900 --> 00:23:17,350 Dette vil være ganske viktig for din PSet. 445 00:23:17,350 --> 00:23:21,140 Logikken i det er veldig enkelt, kanskje syntaktisk bare gjennomføre det. 446 00:23:21,140 --> 00:23:23,365 Dere ønsker å gjøre sikker på at du forstår. 447 00:23:23,365 --> 00:23:25,870 448 00:23:25,870 --> 00:23:27,650 Kjølig. 449 00:23:27,650 --> 00:23:32,560 >> OK, så hvordan vi ville være innsetting noder, høyre, 450 00:23:32,560 --> 00:23:35,380 i en liste fordi huske hva er hva av fordelene 451 00:23:35,380 --> 00:23:39,230 ved å ha en lenket liste versus en rekke i form av lagring? 452 00:23:39,230 --> 00:23:41,110 >> PUBLIKUM: Det er dynamisk, så det er lettere to-- 453 00:23:41,110 --> 00:23:43,180 >> ANDI PENG: Akkurat, så det er dynamisk, noe som 454 00:23:43,180 --> 00:23:46,880 betyr at det kan ekspandere og krympe avhengig av brukerens behov. 455 00:23:46,880 --> 00:23:56,570 Og så, i denne forstand, vi trenger ikke å kaste bort unødvendig minne fordi jeg 456 00:23:56,570 --> 00:24:00,850 hvis jeg ikke vet hvor mange verdier jeg ønsker til butikken, betyr det ikke gir mening for meg 457 00:24:00,850 --> 00:24:04,310 for å lage en matrise, fordi hvis jeg ønsker å lagre 10 verdier 458 00:24:04,310 --> 00:24:08,380 og jeg skaper en rekke 1000, det er mye bortkastet hukommelse, tildelt. 459 00:24:08,380 --> 00:24:11,180 Det er derfor vi ønsker å bruke en koblet liste for å være i stand til dynamisk 460 00:24:11,180 --> 00:24:13,860 endre eller krympe vår størrelse. 461 00:24:13,860 --> 00:24:17,040 >> Og så gjør innsetting litt mer komplisert. 462 00:24:17,040 --> 00:24:20,810 Siden vi ikke kan tilfeldig tilgang elementer den måten at vi ville av en matrise. 463 00:24:20,810 --> 00:24:24,270 Hvis jeg ønsker å sette inn et element i den syvende indeksen, 464 00:24:24,270 --> 00:24:26,930 Jeg kan bare sette det i den syvende indeksen. 465 00:24:26,930 --> 00:24:30,020 På en lenket liste, det gjør det ikke helt fungerer like lett, 466 00:24:30,020 --> 00:24:34,947 og så hvis vi ønsket å sette inn den ene her i lenket liste, 467 00:24:34,947 --> 00:24:36,280 visuelt, er det veldig lett å se. 468 00:24:36,280 --> 00:24:39,363 Vi ønsker bare å sette det rett der, helt i begynnelsen av listen, 469 00:24:39,363 --> 00:24:40,840 rett etter hodet. 470 00:24:40,840 --> 00:24:44,579 >> Men på hvilken måte må vi overføre pekerne er litt convoluted 471 00:24:44,579 --> 00:24:47,620 eller, logisk, det er fornuftig, men du vil være sikker på at du har det 472 00:24:47,620 --> 00:24:50,250 helt ned fordi det siste du ønsker 473 00:24:50,250 --> 00:24:52,990 er å tildele en peker til måte som vi gjør her. 474 00:24:52,990 --> 00:24:58,170 Hvis du dereference den pekeren fra hodet til en, 475 00:24:58,170 --> 00:25:01,086 da plutselig den resten av lenket liste 476 00:25:01,086 --> 00:25:04,680 er tapt fordi du har faktisk ikke opprettet en midlertidig noe. 477 00:25:04,680 --> 00:25:06,220 Det er pekt på to. 478 00:25:06,220 --> 00:25:10,080 Hvis du overfører pekeren, deretter Resten av listen er helt tapt. 479 00:25:10,080 --> 00:25:13,310 Så du ønsker å være veldig, veldig forsiktig her 480 00:25:13,310 --> 00:25:17,010 først tildele pekeren fra hva du 481 00:25:17,010 --> 00:25:20,150 vil sette inn dit du ønsker, og deretter 482 00:25:20,150 --> 00:25:22,710 kan dereference resten av listen. 483 00:25:22,710 --> 00:25:25,250 >> Så dette gjelder for uansett hvor du prøver å sette inn. 484 00:25:25,250 --> 00:25:27,520 Hvis du ønsker å sette på hode, hvis du ønsker å svare på her, 485 00:25:27,520 --> 00:25:29,455 Hvis du ønsker å sette på Til slutt, vel, til slutt jeg 486 00:25:29,455 --> 00:25:30,910 antar du ville bare har ingen pekeren, men du 487 00:25:30,910 --> 00:25:33,830 vil være sikker på at du ikke mister resten av listen. 488 00:25:33,830 --> 00:25:36,640 Du ønsker alltid å sørge for at den nye noden peker 489 00:25:36,640 --> 00:25:39,330 mot hva du vil sette inn, 490 00:25:39,330 --> 00:25:42,170 og deretter kan du legge til kjeding på. 491 00:25:42,170 --> 00:25:43,330 Alle klare? 492 00:25:43,330 --> 00:25:45,427 >> Dette kommer til å være en av de virkelige problemene. 493 00:25:45,427 --> 00:25:48,010 En av de fleste store problemer du kommer til å ha på din PSet 494 00:25:48,010 --> 00:25:51,340 er at du kommer til å prøve å lage en lenket liste og sette inn ting 495 00:25:51,340 --> 00:25:53,340 men da bare miste resten av lenket liste. 496 00:25:53,340 --> 00:25:54,900 Og du kommer til å være som, jeg vet ikke hvorfor dette skjer? 497 00:25:54,900 --> 00:25:58,040 Og det er en smerte å gå gjennom og søke alle dine pekere. 498 00:25:58,040 --> 00:26:02,100 >> Og jeg garanterer deg på denne PSet, skrive og tegne disse nodene ut 499 00:26:02,100 --> 00:26:03,344 vil være veldig, veldig nyttig. 500 00:26:03,344 --> 00:26:06,010 Så du kan helt holde styr hvor alle dine pekere er, 501 00:26:06,010 --> 00:26:08,540 hva som går galt, hvor alle noder er, 502 00:26:08,540 --> 00:26:12,660 hva du må gjøre for å få tilgang til eller sette inn eller slette eller noen av dem. 503 00:26:12,660 --> 00:26:14,550 Alle gode med det? 504 00:26:14,550 --> 00:26:15,050 Kjølig. 505 00:26:15,050 --> 00:26:19,300 506 00:26:19,300 --> 00:26:22,600 >> Så hvis vi ønsket å se på koden? 507 00:26:22,600 --> 00:26:24,470 Å, jeg vet ikke om vi kan se the-- OK, så 508 00:26:24,470 --> 00:26:27,940 på toppen alt er det er en funksjon oppkalt innsats der vi ønsker 509 00:26:27,940 --> 00:26:31,365 å sette int n inn i lenket liste. 510 00:26:31,365 --> 00:26:32,740 Vi kommer til å gå gjennom dette. 511 00:26:32,740 --> 00:26:34,770 Det er mye kode, mye ny syntaks. 512 00:26:34,770 --> 00:26:36,220 Vi vil være OK. 513 00:26:36,220 --> 00:26:39,120 >> Så opp på toppen, når Vi ønsker å skape noe 514 00:26:39,120 --> 00:26:42,380 Hva trenger vi å gjøre, spesielt hvis du vil den skal ikke lagres på stakken 515 00:26:42,380 --> 00:26:43,920 men i haugen? 516 00:26:43,920 --> 00:26:45,460 Vi går til en malloc, ikke sant? 517 00:26:45,460 --> 00:26:48,240 Så vi kommer til å lage en peker. 518 00:26:48,240 --> 00:26:52,074 Node, pekeren, nye likemenn malloc på størrelse med en node 519 00:26:52,074 --> 00:26:53,740 fordi vi ønsker at node som skal opprettes. 520 00:26:53,740 --> 00:26:56,720 Vi vil mengden minne om at en node tar opp 521 00:26:56,720 --> 00:26:59,300 å bli tildelt for opprettelse av den nye noden. 522 00:26:59,300 --> 00:27:02,270 >> Og så skal vi sjekke se om nye likemenn er lik null. 523 00:27:02,270 --> 00:27:03,370 Husk hva vi sa? 524 00:27:03,370 --> 00:27:06,470 Uansett hva du malloc, hva må du alltid gjøre? 525 00:27:06,470 --> 00:27:09,490 Du må alltid sjekke for å se hvorvidt det er null. 526 00:27:09,490 --> 00:27:13,620 >> For eksempel, hvis operativsystemet systemet var helt full, 527 00:27:13,620 --> 00:27:17,060 hvis du hadde ikke mer minne på alt og du prøver å malloc, 528 00:27:17,060 --> 00:27:18,410 det vil returnere null for deg. 529 00:27:18,410 --> 00:27:21,094 Og så hvis du prøver å bruke det når det ble peker til null, 530 00:27:21,094 --> 00:27:23,260 du kommer ikke til å kunne å få tilgang til denne informasjonen. 531 00:27:23,260 --> 00:27:27,010 Og så som sådan, ønsket vi å gjøre sikker på at når du mallocing, 532 00:27:27,010 --> 00:27:30,500 du alltid sjekke for å se om som minnet gitt til deg er null. 533 00:27:30,500 --> 00:27:33,670 Og hvis det ikke er det, så vi kan flytte videre med resten av koden vår. 534 00:27:33,670 --> 00:27:36,140 >> Så vi kommer til å initialisere ny node. 535 00:27:36,140 --> 00:27:39,050 Vi kommer til å gjøre nye n er lik n. 536 00:27:39,050 --> 00:27:42,390 Og så skal vi gjøre satt ny pekeren på nytt 537 00:27:42,390 --> 00:27:46,900 til null fordi akkurat nå har vi ikke vil ha noe for det å peke på. 538 00:27:46,900 --> 00:27:48,755 Vi har ingen anelse om hvor det kommer til å sette deg, 539 00:27:48,755 --> 00:27:50,630 og hvis vi ønsker å setter den på hodet, 540 00:27:50,630 --> 00:27:53,820 da kan vi overføre pekeren til hodet. 541 00:27:53,820 --> 00:27:58,530 Har alle følge logikken hvor det skjer? 542 00:27:58,530 --> 00:28:02,502 >> Alt vi gjør er å skape en ny node, sette pekeren til null, 543 00:28:02,502 --> 00:28:04,210 og deretter reassigning den til hodet om vi 544 00:28:04,210 --> 00:28:06,320 vet vi ønsker å sette det på hodet. 545 00:28:06,320 --> 00:28:09,420 Og deretter hodet skal peke mot at ny node. 546 00:28:09,420 --> 00:28:11,060 Alle OK med det? 547 00:28:11,060 --> 00:28:12,380 >> Så det er en to-trinns prosess. 548 00:28:12,380 --> 00:28:14,760 Du må først assign uansett hva du oppretter. 549 00:28:14,760 --> 00:28:18,260 Satt som peker til referanse, og deretter 550 00:28:18,260 --> 00:28:21,400 kan slags dereference den første pekeren 551 00:28:21,400 --> 00:28:22,972 og peker mot den nye noden. 552 00:28:22,972 --> 00:28:25,680 Uansett hvor du ønsker å sette inn det, at logikken kommer til å holde sant. 553 00:28:25,680 --> 00:28:27,530 >> Det er litt som å tildele midlertidige variabler. 554 00:28:27,530 --> 00:28:28,700 Husk, du har å sørge for at du 555 00:28:28,700 --> 00:28:30,346 ikke mister oversikten over hvis du bytter. 556 00:28:30,346 --> 00:28:33,470 Du ønsker å være sikker på at du har en midlertidig variabel den slags holder 557 00:28:33,470 --> 00:28:35,620 rede på hvor den tingen er lagret slik at du 558 00:28:35,620 --> 00:28:41,190 mister ikke noen verdi i løpet som å rote rundt med den. 559 00:28:41,190 --> 00:28:42,710 >> OK, så koden vil være her. 560 00:28:42,710 --> 00:28:45,020 Dere se etter delen. 561 00:28:45,020 --> 00:28:48,060 Det vil være der. 562 00:28:48,060 --> 00:28:50,280 >> Så jeg antar hvordan fungerer Dette avviker hvis vi ønsket 563 00:28:50,280 --> 00:28:52,300 å sette inn i midten eller slutten? 564 00:28:52,300 --> 00:28:57,892 Er det noen som har en idé om hva som er den pseudokode som den logiske referanse 565 00:28:57,892 --> 00:29:00,350 at vi ville ta hvis vi ønsket for å sette det i midten? 566 00:29:00,350 --> 00:29:03,391 Så hvis vi ønsket å sette det på hode, er alt vi gjør opprette en ny node. 567 00:29:03,391 --> 00:29:06,311 Vi setter pekeren over at ny node til hva hodet, 568 00:29:06,311 --> 00:29:08,310 og da vi satt på hodet til den nye noden, ikke sant? 569 00:29:08,310 --> 00:29:11,560 Hvis vi ønsket å sette det inn i midten av listen, hva ville vi gjøre? 570 00:29:11,560 --> 00:29:14,108 571 00:29:14,108 --> 00:29:16,110 >> PUBLIKUM: Det ville fortsatt være en lignende prosess 572 00:29:16,110 --> 00:29:19,114 som å tildele pekeren og deretter tildele at pekeren, 573 00:29:19,114 --> 00:29:20,530 men vi måtte finne der. 574 00:29:20,530 --> 00:29:23,560 >> ANDI PENG: Akkurat, så nøyaktig den samme prosessen bortsett fra at du 575 00:29:23,560 --> 00:29:27,820 må finne hvor akkurat du ønsker at nye pekeren til å gå inn, 576 00:29:27,820 --> 00:29:44,790 så hvis jeg ønsker å sette inn midt knyttet list-- OK, 577 00:29:44,790 --> 00:29:46,370 la oss si det er vår lenket liste. 578 00:29:46,370 --> 00:29:49,500 Hvis vi ønsker å sette det akkurat her, vi kommer til å opprette en ny node. 579 00:29:49,500 --> 00:29:50,520 Vi kommer til malloc. 580 00:29:50,520 --> 00:29:52,220 Vi kommer til å opprette en ny node. 581 00:29:52,220 --> 00:29:55,940 Vi kommer til å tildele pekeren over denne noden her. 582 00:29:55,940 --> 00:29:58,335 >> Men problemet som avviker fra der hodet er 583 00:29:58,335 --> 00:30:00,490 er at vi visste nøyaktig hvor hodet er. 584 00:30:00,490 --> 00:30:01,930 Det var rett på det første, ikke sant? 585 00:30:01,930 --> 00:30:04,870 Men her er vi nødt til å holde styr av hvor vi setter det inn. 586 00:30:04,870 --> 00:30:07,930 Hvis vi setter inn våre node her har vi 587 00:30:07,930 --> 00:30:12,270 å sørge for at man tidligere til denne noden 588 00:30:12,270 --> 00:30:14,172 er den som tilordner pekeren. 589 00:30:14,172 --> 00:30:16,380 Så da har du til slags holde styr på to ting. 590 00:30:16,380 --> 00:30:19,420 Hvis du holde oversikt over hvor dette node for tiden er å sette inn. 591 00:30:19,420 --> 00:30:23,280 Du må også holde styr på hvor den forrige noden som du ser på 592 00:30:23,280 --> 00:30:24,340 var også der. 593 00:30:24,340 --> 00:30:25,830 Alle gode med det? 594 00:30:25,830 --> 00:30:26,500 OK. 595 00:30:26,500 --> 00:30:28,000 >> Hva med å sette inn på slutten? 596 00:30:28,000 --> 00:30:34,220 Hvis jeg ønsket å legge det her-- hvis jeg ønsket å legge til en ny node til slutten av en liste, 597 00:30:34,220 --> 00:30:37,009 hvordan kan jeg gå om du gjør det? 598 00:30:37,009 --> 00:30:39,300 PUBLIKUM: Så i dag, den siste ens pekte på null. 599 00:30:39,300 --> 00:30:40,960 ANDI PENG: Yeah. 600 00:30:40,960 --> 00:30:43,560 Akkurat, så dette tiden peker å vite, 601 00:30:43,560 --> 00:30:46,720 og så jeg antar, i denne forstand, er det svært enkelt å legge til på slutten av en liste. 602 00:30:46,720 --> 00:30:51,810 Alt du trenger å gjøre er å sette det lik null, og deretter boom. 603 00:30:51,810 --> 00:30:53,070 Akkurat der, veldig lett. 604 00:30:53,070 --> 00:30:53,960 Veldig enkelt. 605 00:30:53,960 --> 00:30:56,430 >> Svært lik den hodet, men logisk deg 606 00:30:56,430 --> 00:30:59,690 vil være sikker på at trinnene du tar mot å gjøre noe av dette, 607 00:30:59,690 --> 00:31:01,500 du følger med. 608 00:31:01,500 --> 00:31:04,420 Det er veldig lett å, i midten av koden din, bli fanget opp på, 609 00:31:04,420 --> 00:31:05,671 Å, jeg har fått så mange tips. 610 00:31:05,671 --> 00:31:07,461 Jeg vet ikke hvor noe peker til. 611 00:31:07,461 --> 00:31:09,170 Jeg vet ikke engang hvilken node jeg er på. 612 00:31:09,170 --> 00:31:11,490 Hva er det som skjer? 613 00:31:11,490 --> 00:31:13,620 >> Slappe av, roe ned, ta et dypt åndedrag. 614 00:31:13,620 --> 00:31:15,530 Trekke ut lenket liste. 615 00:31:15,530 --> 00:31:18,800 Hvis du sier, vet jeg hvor Jeg trenger å sette dette inn i 616 00:31:18,800 --> 00:31:22,970 og jeg vet akkurat hvordan du skal overføre min pekere, mye, mye enklere å fore 617 00:31:22,970 --> 00:31:27,200 out-- mye, mye enklere å ikke gå seg vill i de bugs av koden din. 618 00:31:27,200 --> 00:31:29,410 Alle OK med det? 619 00:31:29,410 --> 00:31:31,380 OK. 620 00:31:31,380 --> 00:31:35,120 >> Så jeg antar et konsept som vi ikke har egentlig snakket om før nå, 621 00:31:35,120 --> 00:31:38,131 og jeg antar du sannsynligvis ikke vil møte mye yet-- 622 00:31:38,131 --> 00:31:40,880 det er litt av et avansert concept-- er at vi faktisk har en data 623 00:31:40,880 --> 00:31:43,900 struktur kalt en dobbelt lenket liste. 624 00:31:43,900 --> 00:31:46,390 Så som dere kan se, alt vi gjør er å skape 625 00:31:46,390 --> 00:31:50,400 en faktisk verdi, en ekstra pekeren på hver av våre noder 626 00:31:50,400 --> 00:31:52,660 som også peker til foregående noden. 627 00:31:52,660 --> 00:31:58,170 Så ikke bare har vi vår noder peker til den neste. 628 00:31:58,170 --> 00:32:01,430 De peker også på den forrige. 629 00:32:01,430 --> 00:32:04,310 Jeg kommer til å ignorere disse to akkurat nå. 630 00:32:04,310 --> 00:32:06,740 >> Så da har du en kjede som kan flytte begge veier, 631 00:32:06,740 --> 00:32:09,630 og da er det litt enklere til logisk følge med. 632 00:32:09,630 --> 00:32:11,896 Som her, i stedet for holde styr på, oh, jeg 633 00:32:11,896 --> 00:32:14,520 må vite at denne noden er den som jeg har til å overføre, 634 00:32:14,520 --> 00:32:17,532 Jeg kan bare gå her og bare trekke den forrige. 635 00:32:17,532 --> 00:32:19,490 Da vet jeg nøyaktig hvor det er, og du 636 00:32:19,490 --> 00:32:21,130 trenger ikke å krysse helheten i lenket liste. 637 00:32:21,130 --> 00:32:22,180 Det er litt enklere. 638 00:32:22,180 --> 00:32:24,960 >> Men som sådan, har du dobbelt mengden av pekere, 639 00:32:24,960 --> 00:32:26,960 det er dobbelt så mye minne. 640 00:32:26,960 --> 00:32:28,950 Det er en masse tips for å holde styr på. 641 00:32:28,950 --> 00:32:32,140 Det er litt mer komplisert, men det er litt mer brukervennlig avhengig 642 00:32:32,140 --> 00:32:34,080 på hva du prøver å oppnå. 643 00:32:34,080 --> 00:32:36,910 >> Så denne type data struktur helt eksisterer, 644 00:32:36,910 --> 00:32:40,280 og strukturen for er meget, meget enkel bortsett fra alt du har er, 645 00:32:40,280 --> 00:32:43,850 i stedet for bare en peker til neste, du har også en peker til tidligere. 646 00:32:43,850 --> 00:32:45,940 Det er hele forskjellen var. 647 00:32:45,940 --> 00:32:47,740 Alle gode med det? 648 00:32:47,740 --> 00:32:48,240 Kjølig. 649 00:32:48,240 --> 00:32:50,940 650 00:32:50,940 --> 00:32:53,280 >> Greit, så nå er jeg å virkelig tilbringe trolig 651 00:32:53,280 --> 00:32:56,870 som 15 til 20 minutter eller bulk av resten av tiden i seksjonen 652 00:32:56,870 --> 00:32:58,360 snakker om hash tabeller. 653 00:32:58,360 --> 00:33:02,590 Hvor mange av dere har lest pset5 spec? 654 00:33:02,590 --> 00:33:03,620 Greit, bra. 655 00:33:03,620 --> 00:33:06,160 Som er høyere enn 50% av normalt. 656 00:33:06,160 --> 00:33:07,560 Det er greit. 657 00:33:07,560 --> 00:33:10,345 >> Så som dere vil se, du er utfordring i pset5 658 00:33:10,345 --> 00:33:16,790 vil være å implementere en ordbok hvor du laster løpet 140.000 ord 659 00:33:16,790 --> 00:33:20,610 at vi gir deg og stavekontroll det mot all teksten. 660 00:33:20,610 --> 00:33:22,580 Vi gir deg tilfeldig biter av litteratur. 661 00:33:22,580 --> 00:33:23,520 Vi vil gi deg The Odyssey. 662 00:33:23,520 --> 00:33:24,561 Vi vil gi deg Iliaden. 663 00:33:24,561 --> 00:33:26,350 Vi vil gi deg Austin Powers. 664 00:33:26,350 --> 00:33:28,220 >> Og din utfordring vil være å stavekontroll 665 00:33:28,220 --> 00:33:31,760 hvert eneste ord i alt av disse ordbøker 666 00:33:31,760 --> 00:33:34,960 hovedsak med vår stavekontroll. 667 00:33:34,960 --> 00:33:38,620 Og så er det noen få deler å skape denne PSet, 668 00:33:38,620 --> 00:33:41,970 første du ønsker å være stand til å faktisk laste 669 00:33:41,970 --> 00:33:43,970 alle ordene i din ordbok, og deretter 670 00:33:43,970 --> 00:33:45,530 vil kunne stavekontroll dem alle. 671 00:33:45,530 --> 00:33:48,780 Og så som sådan, du kommer til å kreve en datastruktur som kan gjøre dette raskt 672 00:33:48,780 --> 00:33:50,790 og effektivt og dynamisk. 673 00:33:50,790 --> 00:33:52,900 >> Så jeg antar det enkleste Måten å gjøre dette, du 674 00:33:52,900 --> 00:33:55,010 vil trolig skape en matrise, ikke sant? 675 00:33:55,010 --> 00:33:58,910 Den enkleste måten for lagring er du kan skape en rekke 140.000 ord 676 00:33:58,910 --> 00:34:03,400 og bare plassere dem alle der og deretter krysse dem av binære søk 677 00:34:03,400 --> 00:34:06,780 eller ved valg eller not-- beklager det er sortering. 678 00:34:06,780 --> 00:34:10,729 Du kan sortere dem og deretter krysse dem av binære søk eller bare lineær søk 679 00:34:10,729 --> 00:34:13,730 og bare siste ord, men tar en stor mengde minne, 680 00:34:13,730 --> 00:34:15,190 og det er ikke veldig effektivt. 681 00:34:15,190 --> 00:34:18,350 >> Og så vi kommer til å starte snakker om måter å gjøre 682 00:34:18,350 --> 00:34:20,110 vår løpende tid mer effektiv. 683 00:34:20,110 --> 00:34:23,190 Og vårt mål er å få konstant tid der 684 00:34:23,190 --> 00:34:25,810 det er nesten som arrays, hvor du har øyeblikkelig tilgang. 685 00:34:25,810 --> 00:34:28,560 Hvis jeg ønsket å søke etter noe, Jeg ønsker å være i stand til å bare, 686 00:34:28,560 --> 00:34:30,810 boom, synes det er nøyaktig, og trekk den ut. 687 00:34:30,810 --> 00:34:34,100 Og slik at en struktur der vi vil være å bli svært tett 688 00:34:34,100 --> 00:34:37,569 å kunne få tilgang til konstant gang, denne hellige gral 689 00:34:37,569 --> 00:34:41,370 i programmering av konstant gang kalles en hash table. 690 00:34:41,370 --> 00:34:45,370 Og så David tidligere nevnt [Uhørbart] litt i foredraget 691 00:34:45,370 --> 00:34:49,100 men vi kommer til å virkelig dykk i dyp denne uken 692 00:34:49,100 --> 00:34:51,780 på en brikke som er om hvordan en hash table fungerer. 693 00:34:51,780 --> 00:34:53,949 >> Så den måten at en hash bord verk, f.eks 694 00:34:53,949 --> 00:35:00,230 hvis jeg ønsket å lagre en haug med ord, en haug med ord i det engelske språket, 695 00:35:00,230 --> 00:35:02,940 Jeg kan teoretisk sette banan, eple, kiwi, mango, par, 696 00:35:02,940 --> 00:35:04,980 og cantaloupe alle på bare en matrise. 697 00:35:04,980 --> 00:35:07,044 De kunne alle passer inn og bli finne. 698 00:35:07,044 --> 00:35:09,210 Det ville være litt vondt å søke gjennom og tilgang, 699 00:35:09,210 --> 00:35:12,920 men den enklere måte å gjøre dette på er at vi kan skape faktisk en struktur 700 00:35:12,920 --> 00:35:15,680 kalles en hash tabell der vi hasj. 701 00:35:15,680 --> 00:35:19,880 Vi kjører alle våre nøkler gjennom en hash-funksjon, en ligning, 702 00:35:19,880 --> 00:35:22,600 som gjør dem alle inn en slags verdi 703 00:35:22,600 --> 00:35:28,740 at da kan vi lagre på hovedsak en rekke lenket liste. 704 00:35:28,740 --> 00:35:32,570 >> Og så her, hvis vi ønsket å lagre engelske ord, 705 00:35:32,570 --> 00:35:37,250 vi kunne potensielt bare, det gjør jeg ikke vet, slår alle de første bokstavene 706 00:35:37,250 --> 00:35:39,630 inn i noen form for et tall. 707 00:35:39,630 --> 00:35:43,140 Og så, for eksempel hvis jeg ønsket En å være synonymt med apple-- 708 00:35:43,140 --> 00:35:47,460 eller med indeks fra 0, og B for å være synonymt med en, 709 00:35:47,460 --> 00:35:51,030 vi kan ha 26 oppføringer som bare kan lagre 710 00:35:51,030 --> 00:35:53,610 alle bokstavene i alfabetet at vi vil begynne med. 711 00:35:53,610 --> 00:35:56,130 Og så kan vi ha eple på indeksen fra 0. 712 00:35:56,130 --> 00:35:59,160 Vi kan ha banan på indeksen for 1, cantaloupe på indeksen på 2, 713 00:35:59,160 --> 00:36:00,540 og så videre og så videre. 714 00:36:00,540 --> 00:36:04,460 Og dermed hvis jeg ønsket å søke min hash table og tilgang eple, 715 00:36:04,460 --> 00:36:07,560 Jeg vet apple starter med en A, og jeg vet nøyaktig 716 00:36:07,560 --> 00:36:10,860 at det må være og hash bord på indeks 0 fordi 717 00:36:10,860 --> 00:36:13,620 av den tidligere tildelte funksjon. 718 00:36:13,620 --> 00:36:16,572 >> Så jeg vet ikke, vi er et brukerprogram der 719 00:36:16,572 --> 00:36:18,780 vil du bli belastet med arbitrarily-- ikke vilkårlig, 720 00:36:18,780 --> 00:36:22,530 med å prøve å ettertenksomt tenke på gode ligninger 721 00:36:22,530 --> 00:36:25,460 å være i stand til å spre ut alle dine verdier 722 00:36:25,460 --> 00:36:29,370 på en måte de enkelt kan få tilgang det senere med som en ligning 723 00:36:29,370 --> 00:36:31,130 at du selv vet. 724 00:36:31,130 --> 00:36:35,210 Så i den forstand hvis jeg ønsket å gå til mango, jeg vet, oh, det begynner med m. 725 00:36:35,210 --> 00:36:37,134 Det må være den indeks over 12. 726 00:36:37,134 --> 00:36:38,800 Jeg trenger ikke å søke gjennom alt. 727 00:36:38,800 --> 00:36:42,080 Jeg vet exactly-- jeg kunne bare gå til indeks over 12 og trekk det ut. 728 00:36:42,080 --> 00:36:45,520 >> Alle klar på hvordan en hash table funksjon fungerer? 729 00:36:45,520 --> 00:36:48,380 Det er slags bare en mer kompleks matrise. 730 00:36:48,380 --> 00:36:50,010 Det er alt det er. 731 00:36:50,010 --> 00:36:51,630 OK. 732 00:36:51,630 --> 00:36:57,690 >> Så jeg antar vi kjører inn dette nummeret av hva 733 00:36:57,690 --> 00:37:06,390 skjer hvis du har flere ting som gir deg den samme indeksen? 734 00:37:06,390 --> 00:37:10,570 Så sier vår funksjon, alt det gjorde var å ta det første brev 735 00:37:10,570 --> 00:37:14,490 og slå den inn i en respektive 0 til 25 indeksen. 736 00:37:14,490 --> 00:37:17,137 Det er helt greit hvis du har bare en av hver. 737 00:37:17,137 --> 00:37:18,970 Men det andre du starte ha mer, er du 738 00:37:18,970 --> 00:37:20,910 kommer til å ha det som kalles en kollisjon. 739 00:37:20,910 --> 00:37:25,580 >> Så hvis jeg prøver å sette inn begrave i en hash tabell som allerede har banan på den, 740 00:37:25,580 --> 00:37:27,870 hva som skal skje når du prøver å sette inn det? 741 00:37:27,870 --> 00:37:30,930 Dårlige ting fordi banan finnes allerede i indeksen 742 00:37:30,930 --> 00:37:33,800 som du ønsker å lagre den i. 743 00:37:33,800 --> 00:37:35,560 Berry slags er, ah, hva gjør jeg? 744 00:37:35,560 --> 00:37:37,080 Jeg vet ikke hvor du skal gå. 745 00:37:37,080 --> 00:37:38,410 Hvordan løser jeg dette? 746 00:37:38,410 --> 00:37:41,150 >> Og så dere vil slags ser vi gjøre dette vanskelig ting 747 00:37:41,150 --> 00:37:44,810 der vi kan slags faktisk lage lenket liste i våre rekker. 748 00:37:44,810 --> 00:37:46,840 Og så den enkleste måten å tenke på dette, 749 00:37:46,840 --> 00:37:50,830 alle hash table er en rekke knyttet lister. 750 00:37:50,830 --> 00:37:55,670 Og så, i den forstand, har du denne vakre rekke pekere, 751 00:37:55,670 --> 00:37:58,740 og deretter hver pekeren denne verdien, ved at indeksen, 752 00:37:58,740 --> 00:38:00,740 faktisk kan peke på andre ting. 753 00:38:00,740 --> 00:38:05,720 Og så har du alle disse separat kjeder kommer ut av ett stort utvalg. 754 00:38:05,720 --> 00:38:07,960 >> Og så her, hvis jeg ønsket å sette inn bær, 755 00:38:07,960 --> 00:38:11,220 Jeg vet, OK, jeg kommer til innspill det gjennom min hash-funksjon. 756 00:38:11,220 --> 00:38:15,070 Jeg kommer til å ende opp med indeks over 1, og så kommer jeg til å være i stand til å ha 757 00:38:15,070 --> 00:38:20,410 bare en mindre undergruppe av denne gigantiske 140 000 ord ordbok. 758 00:38:20,410 --> 00:38:24,220 Og så kan jeg bare se gjennom 1/26 av det. 759 00:38:24,220 --> 00:38:27,910 >> Og så da kan jeg bare sette bær enten før eller etter banan 760 00:38:27,910 --> 00:38:28,820 i denne saken? 761 00:38:28,820 --> 00:38:29,700 Etter, ikke sant? 762 00:38:29,700 --> 00:38:33,920 Og så kommer du til å ønske å Sett denne noden etter banan, 763 00:38:33,920 --> 00:38:36,667 og så kommer du til å sette inn på halen av det lenket liste. 764 00:38:36,667 --> 00:38:38,500 Jeg kommer til å gå tilbake til dette forrige lysbilde, 765 00:38:38,500 --> 00:38:40,680 så dere kan se hvordan hash funksjonen fungerer. 766 00:38:40,680 --> 00:38:43,980 >> Så hash funksjon er denne ligningen at du kjører slags dine innspill 767 00:38:43,980 --> 00:38:46,940 gjennom å få det index du ønsker å tildele den mot. 768 00:38:46,940 --> 00:38:51,130 Og så, i dette eksempelet, ville alt vi å gjøre var å ta det første brevet, 769 00:38:51,130 --> 00:38:55,890 slå den inn i en indeks, så vi kan lagre det i vår hash-funksjon. 770 00:38:55,890 --> 00:39:00,160 Alt vi gjør her er at vi er konvertere den første bokstaven. 771 00:39:00,160 --> 00:39:04,770 Så keykey [0] er bare den første bokstaven av hva strengen vi har, 772 00:39:04,770 --> 00:39:05,720 vi kjører i. 773 00:39:05,720 --> 00:39:09,740 Vi konverterer det til øvre og vi trekke av store bokstaver A, 774 00:39:09,740 --> 00:39:11,740 så alt som gjør gir oss et tall 775 00:39:11,740 --> 00:39:13,670 hvor vi kan hasj våre verdier på. 776 00:39:13,670 --> 00:39:16,550 >> Og så skal vi tilbake hash modulus SIZE. 777 00:39:16,550 --> 00:39:19,340 Være veldig, veldig forsiktig fordi teoretisk her 778 00:39:19,340 --> 00:39:21,870 din hash-verdi kan være uendelig. 779 00:39:21,870 --> 00:39:23,660 Det kunne bare gå videre og videre og videre. 780 00:39:23,660 --> 00:39:26,080 Det kan være noen virkelig, virkelig stor verdi, 781 00:39:26,080 --> 00:39:29,849 men fordi hash tabell som du har laget bare har 26 indekser, 782 00:39:29,849 --> 00:39:31,890 du vil være sikker på din modulusing slik at du 783 00:39:31,890 --> 00:39:33,848 ikke run-- det er det samme ting som queue-- 784 00:39:33,848 --> 00:39:36,320 slik at du ikke går av bunnen av hash-funksjon. 785 00:39:36,320 --> 00:39:39,210 >> Du ønsker å vikle den tilbake rundt på samme måte i [uhørbart] når 786 00:39:39,210 --> 00:39:41,750 du hadde som en veldig, svært stor bokstav, du 787 00:39:41,750 --> 00:39:43,740 visste ikke at det skal bare kjøre på slutten. 788 00:39:43,740 --> 00:39:46,948 Samme her, vil du sørge for at den kjører ikke på slutten av innpakning 789 00:39:46,948 --> 00:39:48,330 rundt til toppen av bordet. 790 00:39:48,330 --> 00:39:50,530 Så dette er bare en svært enkel hash funksjon. 791 00:39:50,530 --> 00:39:56,570 Alt som gjorde var å ta det første brev av hva våre innspill var 792 00:39:56,570 --> 00:40:01,660 og slå den inn i en indeks som vi kunne sette inn vår hash table. 793 00:40:01,660 --> 00:40:05,450 >> Ja, og så som jeg sa tidligere, den måten at vi kan løse kollisjoner 794 00:40:05,450 --> 00:40:09,330 i vår hash tabeller har, det vi kaller, kjeding. 795 00:40:09,330 --> 00:40:13,860 Så hvis du prøver å sette inn flere ord som begynner med det samme, 796 00:40:13,860 --> 00:40:16,145 du kommer til å ha en hash-verdi. 797 00:40:16,145 --> 00:40:18,770 Avokado og eple, hvis du har kjøre det gjennom vår hash-funksjon, 798 00:40:18,770 --> 00:40:21,450 kommer til å gi deg samme nummer, antall 0. 799 00:40:21,450 --> 00:40:24,550 Og så måten vi løser det er at vi kan faktisk slags koble dem 800 00:40:24,550 --> 00:40:27,010 sammen via lenkede lister. 801 00:40:27,010 --> 00:40:29,600 >> Og så i denne forstand, dere kan se kind 802 00:40:29,600 --> 00:40:32,640 av hvordan datastrukturer som vi har vært å sette tidligere 803 00:40:32,640 --> 00:40:35,870 som en rosin lenket liste slag av kan komme sammen til én. 804 00:40:35,870 --> 00:40:38,860 Og så kan du opprette langt mer effektive datastrukturer 805 00:40:38,860 --> 00:40:43,350 som kan håndtere større mengder data, som dynamisk endre størrelse avhengig 806 00:40:43,350 --> 00:40:44,870 på dine behov. 807 00:40:44,870 --> 00:40:45,620 Alle klare? 808 00:40:45,620 --> 00:40:47,580 Alle slags klar på hva som skjer her? 809 00:40:47,580 --> 00:40:52,110 >> Hvis jeg ønsket å insert-- hva som er en frukt som starter med, vet jeg ikke, 810 00:40:52,110 --> 00:40:54,726 B, annet enn bær, banan. 811 00:40:54,726 --> 00:40:55,710 >> PUBLIKUM: Blackberry. 812 00:40:55,710 --> 00:40:57,910 >> ANDI PENG: Blackberry, bjørnebær. 813 00:40:57,910 --> 00:41:00,530 Hvor kommer bjørnebær gå her? 814 00:41:00,530 --> 00:41:04,251 Vel, vi faktisk ikke har sortert dette ennå, men teoretisk 815 00:41:04,251 --> 00:41:06,250 hvis vi ønsket å ha dette i alfabetisk rekkefølge, 816 00:41:06,250 --> 00:41:07,944 hvor skal blackberry gå? 817 00:41:07,944 --> 00:41:09,210 >> PUBLIKUM: [uhørbart] 818 00:41:09,210 --> 00:41:11,100 >> ANDI PENG: Nøyaktig etter her, ikke sant? 819 00:41:11,100 --> 00:41:14,950 Men siden det er svært vanskelig å reorder-- Jeg antar det er opp til dere. 820 00:41:14,950 --> 00:41:17,920 Dere kan helt implementere hva du vil. 821 00:41:17,920 --> 00:41:20,730 Jo mer effektivt å gjøre dette kanskje 822 00:41:20,730 --> 00:41:24,570 ville være å sortere linket listen i alfabetisk rekkefølge, 823 00:41:24,570 --> 00:41:26,520 og så når du er setter ting, vil du 824 00:41:26,520 --> 00:41:28,632 å være sikker på å sette dem i alfabetisk rekkefølge 825 00:41:28,632 --> 00:41:30,590 slik at så når du er prøver å søke dem, 826 00:41:30,590 --> 00:41:32,410 du trenger ikke å krysse alt. 827 00:41:32,410 --> 00:41:35,290 Du vet nøyaktig hvor det er, og det er lettere. 828 00:41:35,290 --> 00:41:39,100 >> Men hvis du på en måte har ting ispedd tilfeldig, 829 00:41:39,100 --> 00:41:41,420 du fortsatt kommer til å ha å krysse det anyways. 830 00:41:41,420 --> 00:41:44,990 Og så hvis jeg ønsket å bare Sett bjørnebær her 831 00:41:44,990 --> 00:41:47,470 og jeg ønsket å søke etter det, jeg vet, oh, bjørnebær 832 00:41:47,470 --> 00:41:52,012 må starte med indeks på 1, så jeg vet umiddelbart bare søke på en. 833 00:41:52,012 --> 00:41:53,970 Og så kan jeg slags traversere lenket liste 834 00:41:53,970 --> 00:41:56,120 før jeg kommer til Blackberry, og then-- ja? 835 00:41:56,120 --> 00:41:59,550 >> PUBLIKUM: Hvis du prøver å create-- Jeg antar at dette er en veldig enkel hash 836 00:41:59,550 --> 00:42:00,050 funksjon. 837 00:42:00,050 --> 00:42:02,835 Og hvis vi ønsket å gjøre flere lag av det som, 838 00:42:02,835 --> 00:42:05,870 OK, vi ønsker å skille seg i som alle de alfabetiske bokstaver 839 00:42:05,870 --> 00:42:09,040 og deretter igjen å like et annet sett av alfabetiske bokstaver i det, 840 00:42:09,040 --> 00:42:11,715 vi setter som en hash tabell i en hash table, 841 00:42:11,715 --> 00:42:13,256 eller som en funksjon innenfor en funksjon? 842 00:42:13,256 --> 00:42:14,880 Eller er at-- 843 00:42:14,880 --> 00:42:17,510 >> ANDI PENG: Så din hash function-- din hash table 844 00:42:17,510 --> 00:42:19,360 kan være så stor som du vil ha det til. 845 00:42:19,360 --> 00:42:21,930 Så i denne forstand, tenkte jeg det var veldig enkelt, veldig 846 00:42:21,930 --> 00:42:25,320 enkelt for meg å bare liksom basert på bokstavene i det første ordet. 847 00:42:25,320 --> 00:42:28,690 Og så det er bare 26 alternativer. 848 00:42:28,690 --> 00:42:32,650 Jeg kan bare få 26 alternativer fra 0-25 fordi de kan bare 849 00:42:32,650 --> 00:42:36,510 starte fra A til Z. Men hvis du ønsket for å legge til, kanskje, mer kompleksitet 850 00:42:36,510 --> 00:42:39,260 eller raskere kjøretid til din hash table, du absolutt 851 00:42:39,260 --> 00:42:40,760 kan gjøre alle slags ting. 852 00:42:40,760 --> 00:42:43,330 Du kan lage din egen ligning som gir deg 853 00:42:43,330 --> 00:42:48,000 mer distribusjon i din ord, så når du søker, 854 00:42:48,000 --> 00:42:49,300 det kommer til å være raskere. 855 00:42:49,300 --> 00:42:52,100 >> Det er helt opp til dere hvordan du ønsker å implementere det. 856 00:42:52,100 --> 00:42:55,140 Tenk på det som bare bøtter. 857 00:42:55,140 --> 00:42:57,376 Hvis jeg ønsket å ha 26 bøtter, jeg kommer 858 00:42:57,376 --> 00:42:59,420 å sortere ting i disse bøtter. 859 00:42:59,420 --> 00:43:02,980 Men jeg kommer til å ha en haug ting i hver bøtte, 860 00:43:02,980 --> 00:43:05,890 så hvis du ønsker å gjøre det raskere og mer effektivt, 861 00:43:05,890 --> 00:43:07,190 la meg få hundre bøtter. 862 00:43:07,190 --> 00:43:09,290 >> Men da må du regne ut en måte å sortere ting slik at de er 863 00:43:09,290 --> 00:43:11,040 i riktig bøtte bør de være i. 864 00:43:11,040 --> 00:43:13,331 Men så når du faktisk ønsker å se på det bøtte, 865 00:43:13,331 --> 00:43:16,410 det er mye raskere fordi det er mindre ting i hver bøtte. 866 00:43:16,410 --> 00:43:20,250 Og så, ja, det er faktisk Trikset for dere i pset5 867 00:43:20,250 --> 00:43:22,360 er at du vil være utfordret til å bare lage 868 00:43:22,360 --> 00:43:26,170 det som er den mest effektive funksjon du kan tenke på å være 869 00:43:26,170 --> 00:43:28,520 i stand til å lagre og sjekke disse verdiene. 870 00:43:28,520 --> 00:43:30,840 >> Helt opp til dere men du ønsker å gjøre det, 871 00:43:30,840 --> 00:43:32,229 men det er et veldig godt poeng. 872 00:43:32,229 --> 00:43:34,520 At den type logikk deg ønsker å begynne å tenke på 873 00:43:34,520 --> 00:43:37,236 er, vel, hvorfor ikke jeg gjøre flere bøtter. 874 00:43:37,236 --> 00:43:39,527 Og så må jeg søke mindre ting, og så kanskje jeg 875 00:43:39,527 --> 00:43:41,640 har en annen hash-funksjon. 876 00:43:41,640 --> 00:43:45,500 >> Ja, det er mange måter å gjøre dette PSet, noen er raskere enn andre. 877 00:43:45,500 --> 00:43:50,630 Jeg er helt kommer til å bare se hvordan raskt var de raskeste dere vil 878 00:43:50,630 --> 00:43:55,170 kunne få funksjoner skal fungere. 879 00:43:55,170 --> 00:43:58,176 OK, alle bra på CHAINING og hash tabeller? 880 00:43:58,176 --> 00:44:00,800 Det er faktisk som en veldig enkel konsept hvis du tenker på det. 881 00:44:00,800 --> 00:44:05,160 Alt er det er å skille hva innganger er i bøtter, 882 00:44:05,160 --> 00:44:10,670 sortere dem, og deretter søke på viser at det er forbundet med. 883 00:44:10,670 --> 00:44:11,852 >> Kjølig. 884 00:44:11,852 --> 00:44:18,160 Greit, nå har vi en annen type av datastruktur som kalles et tre. 885 00:44:18,160 --> 00:44:20,850 La oss gå videre og snakke om prøver som er tydelig forskjellig, 886 00:44:20,850 --> 00:44:22,330 men i samme kategori. 887 00:44:22,330 --> 00:44:29,010 I hovedsak er alle et tre i stedet organisere data i lineær måte 888 00:44:29,010 --> 00:44:32,560 som en hash table does-- deg vet, det har en topp og en bunn 889 00:44:32,560 --> 00:44:37,900 og deretter du slags kobling av av det-- en Treet har en topp som du kaller det rot, 890 00:44:37,900 --> 00:44:40,220 og da er det har blader hele veien rundt. 891 00:44:40,220 --> 00:44:42,390 >> Og så alt du trenger her er bare toppen node 892 00:44:42,390 --> 00:44:45,980 som peker til andre noder, som peker til flere noder, og så videre og så videre. 893 00:44:45,980 --> 00:44:48,130 Og så må du bare splitte grener. 894 00:44:48,130 --> 00:44:53,255 Det er bare en annen måte å organisere data, og fordi vi kaller det et tre, 895 00:44:53,255 --> 00:44:56,270 dere just-- det er bare modellert ut til å se ut som et tre. 896 00:44:56,270 --> 00:44:57,670 Det er derfor vi kaller det trær. 897 00:44:57,670 --> 00:44:59,370 >> Hash table ser ut som et bord. 898 00:44:59,370 --> 00:45:01,310 Et tre bare ser ut som et tre. 899 00:45:01,310 --> 00:45:03,300 Alt er det er en egen måte å organisere noder 900 00:45:03,300 --> 00:45:06,020 avhengig av hva dine behov er. 901 00:45:06,020 --> 00:45:11,810 >> Så har du en rot og da har du blader. 902 00:45:11,810 --> 00:45:15,380 Den måten at vi kan spesielt tenker på det er et binært tre, 903 00:45:15,380 --> 00:45:18,150 et binært tre er bare en bestemt type av et tre 904 00:45:18,150 --> 00:45:22,450 hvor hver node bare poeng til, på max, to andre noder. 905 00:45:22,450 --> 00:45:25,434 Og så her har du tydelig symmetri i treet 906 00:45:25,434 --> 00:45:28,600 som gjør det lettere å slags se på hvilke verdier du er fordi da 907 00:45:28,600 --> 00:45:30,150 har alltid en venstre eller høyre. 908 00:45:30,150 --> 00:45:33,150 Det er aldri som en venstre tredjedel fra venstre eller en fjerde fra venstre. 909 00:45:33,150 --> 00:45:36,358 Det er bare du har en venstre og en høyre og du kan søke en av de to. 910 00:45:36,358 --> 00:45:38,980 Og så hvorfor er dette nyttig? 911 00:45:38,980 --> 00:45:40,980 Den måte som dette er nyttig er hvis du leter 912 00:45:40,980 --> 00:45:42,890 å søke gjennom verdier, ikke sant? 913 00:45:42,890 --> 00:45:45,640 Snarere enn å implementere binære Søk i en feil array, 914 00:45:45,640 --> 00:45:49,260 hvis du ønsket å være i stand til å sette noder og ta bort noder på vilje og også 915 00:45:49,260 --> 00:45:52,185 bevare søk kapasiteter på binære søk. 916 00:45:52,185 --> 00:45:54,560 Så på denne måten, er vi på en måte tricking-- husker da vi 917 00:45:54,560 --> 00:45:56,530 sa lenkede lister kan ikke binære søk? 918 00:45:56,530 --> 00:46:01,700 Vi slags lage en datastruktur at triks som i arbeids. 919 00:46:01,700 --> 00:46:05,034 >> Og så fordi lenkede lister er lineær, de bare koble den ene etter den andre. 920 00:46:05,034 --> 00:46:06,950 Vi kan slags ha forskjellige slags pekere 921 00:46:06,950 --> 00:46:09,408 som peker til forskjellige noder som kan hjelpe oss med søket. 922 00:46:09,408 --> 00:46:12,590 Og så her, hvis jeg ønsket å har et binært søketre, 923 00:46:12,590 --> 00:46:14,090 Jeg vet at mitt mellomnavn hvis 55. 924 00:46:14,090 --> 00:46:18,280 Jeg skal bare lage den som mitt mellomnavn, som min rot, 925 00:46:18,280 --> 00:46:20,770 og så kommer jeg til å ha verdier spinne ut av det. 926 00:46:20,770 --> 00:46:25,610 >> Så her, hvis jeg skal søke etter verdien av 66, kan jeg begynne på 55. 927 00:46:25,610 --> 00:46:27,310 Det er 66 større enn 55? 928 00:46:27,310 --> 00:46:30,970 Ja, det er, så jeg vet jeg mus søke Jeg n høyre peker av dette treet. 929 00:46:30,970 --> 00:46:32,440 Jeg går til 77. 930 00:46:32,440 --> 00:46:35,367 OK, er 66 mindre enn eller større enn 77? 931 00:46:35,367 --> 00:46:37,950 Det er mindre enn, så du vet, oh, som må være den venstre noden. 932 00:46:37,950 --> 00:46:41,410 >> Og så her vi er slags bevare alle de store tingene om matriser, 933 00:46:41,410 --> 00:46:44,420 slik som dynamisk skalering av gjenstander, som er 934 00:46:44,420 --> 00:46:49,530 i stand til å sette inn og slette på vilje, uten å måtte bekymre seg om fast 935 00:46:49,530 --> 00:46:50,370 mengde plass. 936 00:46:50,370 --> 00:46:52,820 Vi har fortsatt bevare alle de fantastiske tingene 937 00:46:52,820 --> 00:46:57,140 samtidig være i stand til å bevare log og søk tidspunktet for binære søk 938 00:46:57,140 --> 00:47:00,450 at vi var bare tidligere stand til å få en setning. 939 00:47:00,450 --> 00:47:06,310 >> Cool datastruktur, type komplisert å implementere, noden. 940 00:47:06,310 --> 00:47:08,311 Som du kan se, alt det er struct av noden 941 00:47:08,311 --> 00:47:10,143 er at du har en venstre og en høyre peker. 942 00:47:10,143 --> 00:47:11,044 Det er alt det er. 943 00:47:11,044 --> 00:47:12,960 Så i stedet for bare å ha en x eller et foregående. 944 00:47:12,960 --> 00:47:15,920 Du har en venstre eller høyre, og deretter du kan slags koble dem sammen 945 00:47:15,920 --> 00:47:16,836 men du så ønsker. 946 00:47:16,836 --> 00:47:21,080 947 00:47:21,080 --> 00:47:24,270 >> OK, vi faktisk kommer bare ta noen få minutter. 948 00:47:24,270 --> 00:47:25,790 Så vi kommer til å dra tilbake hit. 949 00:47:25,790 --> 00:47:28,270 Som jeg sa tidligere, Jeg slags forklart 950 00:47:28,270 --> 00:47:31,520 logikken bak hvordan vi vil søke gjennom dette. 951 00:47:31,520 --> 00:47:33,860 Vi kommer til å prøve pseudocoding dette ut for å se 952 00:47:33,860 --> 00:47:38,000 hvis vi kan slags bruke samme logikk binære søk 953 00:47:38,000 --> 00:47:40,055 til en annen type datastruktur. 954 00:47:40,055 --> 00:47:45,049 Hvis dere ønsker å ta ut et par minutter å bare tenke på dette. 955 00:47:45,049 --> 00:48:45,927 956 00:48:45,927 --> 00:48:46,925 OK. 957 00:48:46,925 --> 00:48:51,407 Greit, jeg kommer til å faktisk bare gi deg the-- nei, 958 00:48:51,407 --> 00:48:52,990 vi skal snakke om pseudo først. 959 00:48:52,990 --> 00:48:56,580 Så er det noen som vil ha å gi et stikk på hva 960 00:48:56,580 --> 00:49:02,100 det første du vil gjøre når du starter opp søking er? 961 00:49:02,100 --> 00:49:04,460 Hvis vi leter etter verdien av 66, hva er 962 00:49:04,460 --> 00:49:07,940 det første vi vil gjøre hvis vi ønsker til binær søke dette treet? 963 00:49:07,940 --> 00:49:10,760 >> PUBLIKUM: Du ønsker å se rett og se til venstre og se [uhørbart] 964 00:49:10,760 --> 00:49:11,230 større antall. 965 00:49:11,230 --> 00:49:12,271 >> ANDI PENG: Ja, akkurat. 966 00:49:12,271 --> 00:49:15,350 Så du kommer til å se på rot. 967 00:49:15,350 --> 00:49:18,180 Det er mange måter du kan ringe det dine foreldre node folk sier. 968 00:49:18,180 --> 00:49:21,317 Jeg liker å si rot fordi det er som roten av treet. 969 00:49:21,317 --> 00:49:23,400 Du kommer til å se på root node, og du er 970 00:49:23,400 --> 00:49:26,940 kommer til å se er 66 større eller mindre enn 55. 971 00:49:26,940 --> 00:49:30,360 Og hvis det er større enn, vel, det er større enn, der vi ønsker å se? 972 00:49:30,360 --> 00:49:32,000 Hvor ønsker vi å søke nå, ikke sant? 973 00:49:32,000 --> 00:49:34,340 Vi ønsker å søke på høyre halvdel av dette treet. 974 00:49:34,340 --> 00:49:38,390 >> Så vi har, praktisk, en peker som peker til høyre. 975 00:49:38,390 --> 00:49:44,325 Og så da kan vi sette vår nye rot til 77. 976 00:49:44,325 --> 00:49:46,450 Vi kan bare gå dit pekeren peker. 977 00:49:46,450 --> 00:49:49,100 Vel, oh, her vi starter på 77, og vi kan bare 978 00:49:49,100 --> 00:49:51,172 gjøre dette rekursivt igjen og igjen. 979 00:49:51,172 --> 00:49:52,880 På denne måten, du snill av har en funksjon. 980 00:49:52,880 --> 00:49:57,430 Du har en måte å søke som du kan bare gjenta om og om igjen og om igjen, 981 00:49:57,430 --> 00:50:02,720 avhengig av hvor du ønsker å se til du til slutt får til verdien 982 00:50:02,720 --> 00:50:04,730 at du søker etter. 983 00:50:04,730 --> 00:50:05,230 Gir mening? 984 00:50:05,230 --> 00:50:07,800 >> Jeg er i ferd med å vise deg den faktiske kode, og det er mye kode. 985 00:50:07,800 --> 00:50:08,674 Du trenger ikke å frik ut. 986 00:50:08,674 --> 00:50:09,910 Vi skal snakke gjennom det. 987 00:50:09,910 --> 00:50:13,410 988 00:50:13,410 --> 00:50:14,020 >> Faktisk ikke. 989 00:50:14,020 --> 00:50:15,061 Det var bare pseudokode. 990 00:50:15,061 --> 00:50:17,860 OK, det var bare pseudo, som er litt komplisert, 991 00:50:17,860 --> 00:50:19,751 men det er helt greit. 992 00:50:19,751 --> 00:50:21,000 Alle følge med her? 993 00:50:21,000 --> 00:50:24,260 Hvis roten er null, retur falsk fordi det betyr 994 00:50:24,260 --> 00:50:26,850 du trenger ikke engang noe der. 995 00:50:26,850 --> 00:50:31,376 >> Hvis root n er verdien, så hvis det skjer for å være den du ser på, 996 00:50:31,376 --> 00:50:34,000 så du kommer til å returnere true fordi du vet at du har funnet det. 997 00:50:34,000 --> 00:50:36,250 Men hvis verdien er mindre enn roten av n, er du 998 00:50:36,250 --> 00:50:38,332 kommer til å søke venstre barn eller venstre blad, 999 00:50:38,332 --> 00:50:39,540 hva du vil kalle det. 1000 00:50:39,540 --> 00:50:41,750 Og hvis verdien er større enn roten du kommer til å søke på riktig treet, 1001 00:50:41,750 --> 00:50:44,610 så bare kjør funksjonen gjennom søk på nytt. 1002 00:50:44,610 --> 00:50:48,037 >> Og hvis roten er null, at det betyr at du har nådd slutten? 1003 00:50:48,037 --> 00:50:50,120 Det betyr at du ikke har noen mer flere blader for å søke, 1004 00:50:50,120 --> 00:50:52,230 da vet du, oh, jeg antar det ikke er her 1005 00:50:52,230 --> 00:50:55,063 fordi etter at jeg har sett gjennom hele greia og det er ikke her, 1006 00:50:55,063 --> 00:50:56,930 det bare ikke kan være her. 1007 00:50:56,930 --> 00:50:58,350 >> Betyr det fornuftig for alle? 1008 00:50:58,350 --> 00:51:03,230 Så det er som binær søk bevare egenskapene til lenkede lister. 1009 00:51:03,230 --> 00:51:09,200 Kult, og så den andre typen av data struktur dere 1010 00:51:09,200 --> 00:51:13,180 kan prøve å implementere på ditt PSet, trenger du bare å velge én metode. 1011 00:51:13,180 --> 00:51:19,430 Men kanskje en alternativ metode for å hash tabellen er det vi kaller en trie. 1012 00:51:19,430 --> 00:51:24,080 >> Alt en trie er er en bestemt type tre som 1013 00:51:24,080 --> 00:51:28,600 har verdier som går til andre verdier. 1014 00:51:28,600 --> 00:51:31,450 Så i stedet for å ha en binær tre i den forstand at bare ett 1015 00:51:31,450 --> 00:51:35,940 ting kan peke på to, kan du ha en ting peker på mange, mange ting. 1016 00:51:35,940 --> 00:51:39,450 Du har egentlig arrays innsiden av der du lagrer 1017 00:51:39,450 --> 00:51:41,790 pekere som peker til andre arrays. 1018 00:51:41,790 --> 00:51:45,210 1019 00:51:45,210 --> 00:51:49,460 >> Så noden av hvordan vi ville definere en trie 1020 00:51:49,460 --> 00:51:52,590 er vi ønsker å ha en Boolean, c ord, ikke sant? 1021 00:51:52,590 --> 00:51:54,920 Så noden er boolsk som sant eller usant, 1022 00:51:54,920 --> 00:51:58,490 først av alt på hodet av som matrise, er dette et ord? 1023 00:51:58,490 --> 00:52:03,620 Dernest, du vil ha tips til hvilken resten av dem er. 1024 00:52:03,620 --> 00:52:07,470 Litt komplisert, litt abstrakt, men Jeg vil forklare hva det betyr. 1025 00:52:07,470 --> 00:52:13,800 >> Så her, på toppen, hvis du har en rekke erklært allerede 1026 00:52:13,800 --> 00:52:17,040 en node der du har en boolsk verdien som er lagret på forsiden 1027 00:52:17,040 --> 00:52:19,490 som forteller deg er dette et ord? 1028 00:52:19,490 --> 00:52:20,520 Er ikke dette et ord? 1029 00:52:20,520 --> 00:52:23,240 Og så har du resten av matrise som 1030 00:52:23,240 --> 00:52:26,040 faktisk lagrer all mulighetene for hva det kunne være. 1031 00:52:26,040 --> 00:52:28,660 Så, for eksempel, i likhet på toppen har du 1032 00:52:28,660 --> 00:52:32,140 den første som sier sant eller usant, ja eller nei, dette er et ord. 1033 00:52:32,140 --> 00:52:38,130 >> Og da har du 0 til 26 av bokstavene som du kan lagre. 1034 00:52:38,130 --> 00:52:42,790 Hvis jeg ønsket å søke her for bat, jeg går til toppen 1035 00:52:42,790 --> 00:52:49,200 og jeg ser for B. Jeg finner B i min array, og så jeg vet, OK, er B et ord? 1036 00:52:49,200 --> 00:52:53,010 B er ikke et ord, slik at dermed Jeg må fortsette å søke. 1037 00:52:53,010 --> 00:52:56,410 Jeg går fra B, og jeg ser til peker på at B peker mot 1038 00:52:56,410 --> 00:53:00,900 og jeg ser en annen utvalg av informasjon, samme struktur som vi hadde før. 1039 00:53:00,900 --> 00:53:05,240 >> Og her-- oh, den neste brev i [uhørbart] er A. 1040 00:53:05,240 --> 00:53:07,210 Så vi ser i denne matrisen. 1041 00:53:07,210 --> 00:53:10,860 Vi finner den åttende verdi, og deretter vi se å se, oh, 1042 00:53:10,860 --> 00:53:12,840 hei, er det et ord, er B-A et ord? 1043 00:53:12,840 --> 00:53:13,807 Det er ikke et ord. 1044 00:53:13,807 --> 00:53:14,890 Vi er nødt til å holde utkikk. 1045 00:53:14,890 --> 00:53:17,850 >> Og så så vi ser hvor pekeren av A-poeng, 1046 00:53:17,850 --> 00:53:21,130 og den peker på en annen måte i som vi har mer verdi lagret. 1047 00:53:21,130 --> 00:53:24,150 Og til slutt, vi kommer til å B-A-T, som er et ord. 1048 00:53:24,150 --> 00:53:25,970 Og så neste gang du ser, du kommer 1049 00:53:25,970 --> 00:53:30,850 å ha det sjekk av, ja, dette boolsk funksjon er sant. 1050 00:53:30,850 --> 00:53:35,450 Og så i den forstand vi er snille ved å ha et tre med matriser. 1051 00:53:35,450 --> 00:53:39,890 >> Så da du kan slags søke ned. 1052 00:53:39,890 --> 00:53:43,650 Heller enn en funksjon, og hashing tilordne verdier ved lenket liste, 1053 00:53:43,650 --> 00:53:49,190 du kan bare gjennomføre en trie som søker downwords. 1054 00:53:49,190 --> 00:53:50,850 Virkelig, virkelig komplisert ting. 1055 00:53:50,850 --> 00:53:54,060 Ikke lett å tenke på fordi jeg liker spytter så mange datastrukturer ut 1056 00:53:54,060 --> 00:53:58,710 på deg, men gjør alle slags forstå hvordan logikken i dette fungerer? 1057 00:53:58,710 --> 00:54:01,920 >> Ok kult. 1058 00:54:01,920 --> 00:54:05,600 So B-A-T, og deretter du kommer til å søke. 1059 00:54:05,600 --> 00:54:07,940 Neste gang du kommer å se, oh, hey, det er sant, 1060 00:54:07,940 --> 00:54:09,273 dermed jeg vet at dette må være et ord. 1061 00:54:09,273 --> 00:54:12,030 1062 00:54:12,030 --> 00:54:13,770 >> Samme for dyrehagen. 1063 00:54:13,770 --> 00:54:17,960 Så her er tingen akkurat nå, hvis vi ønsket å søke etter zoo, akkurat nå, 1064 00:54:17,960 --> 00:54:20,780 tiden zoo er ikke en ord i vår ordbok 1065 00:54:20,780 --> 00:54:25,300 fordi, som dere kan se, utgangspunktet at vi har en boolsk 1066 00:54:25,300 --> 00:54:28,590 return true ligger i enden av zoom. 1067 00:54:28,590 --> 00:54:30,430 Vi har Z-O-O-M. 1068 00:54:30,430 --> 00:54:33,900 >> Og så her, vi trenger faktisk ikke ordet, zoo, i vår ordliste 1069 00:54:33,900 --> 00:54:36,070 fordi denne boksen ikke er merket. 1070 00:54:36,070 --> 00:54:39,540 Slik at maskinen ikke vet at zoo er et ord 1071 00:54:39,540 --> 00:54:42,430 fordi den måten at vi har lagret det, bare en zoom her 1072 00:54:42,430 --> 00:54:44,920 faktisk har en boolsk verdi som er blitt slått sant. 1073 00:54:44,920 --> 00:54:49,380 Så hvis vi ønsker å sette inn ord, zoo, i vår ordbok, 1074 00:54:49,380 --> 00:54:51,770 hvordan ville vi gå om du gjør det? 1075 00:54:51,770 --> 00:54:55,960 Hva må vi gjøre for å sikre at våre datamaskinen vet at Z-O-O er et ord 1076 00:54:55,960 --> 00:54:58,130 og ikke det første ordet er Z-O-O-M? 1077 00:54:58,130 --> 00:54:59,360 >> PUBLIKUM: [uhørbart] 1078 00:54:59,360 --> 00:55:01,450 >> ANDI PENG: Akkurat, vi vil være sikker på at dette 1079 00:55:01,450 --> 00:55:07,890 her, er at boolsk verdi krysset av at det er sant. 1080 00:55:07,890 --> 00:55:13,297 Z-O-O, så vi kommer til å sjekke det, slik at vi vet nøyaktig, hei, er zoo et ord. 1081 00:55:13,297 --> 00:55:15,380 Jeg kommer til å fortelle datamaskin at det er et ord så 1082 00:55:15,380 --> 00:55:18,000 at når datamaskinen sjekker, den vet at zoo er et ord. 1083 00:55:18,000 --> 00:55:21,269 >> Fordi huske alle disse dataene strukturer, er det veldig lett for oss 1084 00:55:21,269 --> 00:55:22,310 å si, oh, er bat et ord. 1085 00:55:22,310 --> 00:55:22,851 Zoo er et ord. 1086 00:55:22,851 --> 00:55:23,611 Zoom er et ord. 1087 00:55:23,611 --> 00:55:25,860 Men når du bygger den, datamaskinen har ingen anelse. 1088 00:55:25,860 --> 00:55:28,619 >> Så må du fortelle det akkurat på hvilket punkt er dette et ord? 1089 00:55:28,619 --> 00:55:29,910 På hvilket tidspunkt er det ikke et ord? 1090 00:55:29,910 --> 00:55:31,784 Og på hvilket punkt gjør jeg trenger å søke ting, 1091 00:55:31,784 --> 00:55:34,000 og på hvilket tidspunkt må jeg gå videre? 1092 00:55:34,000 --> 00:55:37,010 Alle klar av det? 1093 00:55:37,010 --> 00:55:39,540 Kjølig. 1094 00:55:39,540 --> 00:55:42,530 >> Og så så kommer Problemet med hvordan ville vi 1095 00:55:42,530 --> 00:55:45,560 gå om å sette inn noe det er faktisk ikke det? 1096 00:55:45,560 --> 00:55:49,090 Så la oss bare si at vi ønsker å sette inn ordet, bad, inn i vårt trie. 1097 00:55:49,090 --> 00:55:53,589 Som dere kan se ut som i dag alt vi har nå er B-A-T, 1098 00:55:53,589 --> 00:55:55,630 og denne nye datastrukturen der hadde en halvliter som 1099 00:55:55,630 --> 00:55:59,740 pekte på null fordi vi antar at, åh, det er ingen ord etter B-A-T, 1100 00:55:59,740 --> 00:56:02,530 hvorfor trenger vi å holde ha ting etter at T. 1101 00:56:02,530 --> 00:56:06,581 >> Men problemet oppstår hvis vi gjør du ønsker å ha et ord som kommer etter 1102 00:56:06,581 --> 00:56:07,080 T-tallet. 1103 00:56:07,080 --> 00:56:09,500 Hvis du har badekar, er du kommer til å ønske en H høyre. 1104 00:56:09,500 --> 00:56:13,290 Og så måten vi kommer til å gjøre det på er vi kommer til å opprette en egen node. 1105 00:56:13,290 --> 00:56:16,840 Vi er ikke tildele det beløpet minne for denne nye array, 1106 00:56:16,840 --> 00:56:20,720 og vi kommer til å overføre pekere. 1107 00:56:20,720 --> 00:56:22,947 >> Vi kommer til å tildele H, Først av alt, dette null, 1108 00:56:22,947 --> 00:56:24,030 vi kommer til å bli kvitt. 1109 00:56:24,030 --> 00:56:26,590 Vi kommer til å ha de H peke nedover. 1110 00:56:26,590 --> 00:56:30,600 Hvis vi ser en H, vi vil ha det å gå til et annet sted. 1111 00:56:30,600 --> 00:56:33,910 >> I her, kan vi da krysse av ja. 1112 00:56:33,910 --> 00:56:38,170 Hvis vi treffer en H etter T, oh, da vet vi at dette er et ord. 1113 00:56:38,170 --> 00:56:41,110 Den boolske kommer til å returnere sann. 1114 00:56:41,110 --> 00:56:42,950 Alle klare på hvordan det skjedde? 1115 00:56:42,950 --> 00:56:45,110 OK. 1116 00:56:45,110 --> 00:56:47,214 >> Så egentlig, alle disse datastrukturer 1117 00:56:47,214 --> 00:56:50,130 at vi har gått over i dag, har jeg gått over dem virkelig, virkelig raskt 1118 00:56:50,130 --> 00:56:52,192 og ikke i for mye detalj, og det er OK. 1119 00:56:52,192 --> 00:56:53,900 Når du begynner å rote med det, vil du være 1120 00:56:53,900 --> 00:56:55,733 holde styr på hvor alle pekere er, 1121 00:56:55,733 --> 00:56:58,060 hva som skjer i ditt datastrukturer, et cetera. 1122 00:56:58,060 --> 00:56:59,810 De vil være svært nyttig, og det er opp til deg 1123 00:56:59,810 --> 00:57:03,890 gutta å helt finne ut hvordan du ønsker å gjennomføre ting. 1124 00:57:03,890 --> 00:57:07,650 >> Og så pset4, av 5-- oh, er det galt. 1125 00:57:07,650 --> 00:57:10,140 Pset5 er feilstavinger. 1126 00:57:10,140 --> 00:57:13,710 Som jeg sa tidligere, du kommer til, en gang igjen, last ned kildekoden fra oss. 1127 00:57:13,710 --> 00:57:16,210 Det kommer til å være tre hoved ting du skal laste ned. 1128 00:57:16,210 --> 00:57:18,470 Du vil laste ned ordbøker, kers og tekster. 1129 00:57:18,470 --> 00:57:21,660 >> Alle disse tingene er er enten ordbøker av ord 1130 00:57:21,660 --> 00:57:25,190 at vi ønsker å sjekke eller test av informasjon 1131 00:57:25,190 --> 00:57:26,930 at vi vil at du skal stave sjekk. 1132 00:57:26,930 --> 00:57:29,670 Og så ordbøker gir vi deg kommer 1133 00:57:29,670 --> 00:57:34,870 for å gi deg faktiske ordene som vi ønsker du lagre liksom på en måte som er 1134 00:57:34,870 --> 00:57:36,530 mer effektiv enn en matrise. 1135 00:57:36,530 --> 00:57:38,470 Og så er tekstene kommer til å være det vi er 1136 00:57:38,470 --> 00:57:43,900 ber deg om å stave sjekke at alle ordene er det virkelige ord. 1137 00:57:43,900 --> 00:57:47,970 >> Og så tre blokker av programmer som vi vil gi deg 1138 00:57:47,970 --> 00:57:51,130 kalles dictionary.c, dictionary.h, og speller.c. 1139 00:57:51,130 --> 00:57:56,500 Og så alt dictionary.c gjør er hva du blir bedt om å gjennomføre. 1140 00:57:56,500 --> 00:57:57,880 Den laster ord. 1141 00:57:57,880 --> 00:58:02,000 Det stave sjekker dem, og det gjør at at alt er satt inn riktig. 1142 00:58:02,000 --> 00:58:05,180 >> diction.h er bare en bibliotekfilen som erklærer alle disse funksjonene. 1143 00:58:05,180 --> 00:58:07,650 Og speller.c, kommer vi til å gi deg. 1144 00:58:07,650 --> 00:58:09,290 Du trenger ikke å endre noe av det. 1145 00:58:09,290 --> 00:58:14,290 All speller.c gjør er å ta det, laster det, kontrollerer hastigheten av den, 1146 00:58:14,290 --> 00:58:19,190 tester benchmark som hvordan raskt du klarer å gjøre ting. 1147 00:58:19,190 --> 00:58:20,410 >> Det er en stavekontroll. 1148 00:58:20,410 --> 00:58:23,920 Bare ikke rotet med det, men gjøre at du forstår hva det gjør. 1149 00:58:23,920 --> 00:58:28,090 Vi bruker en funksjon kalt getrusage at tester ytelsen til spell 1150 00:58:28,090 --> 00:58:28,590 kontrolløren. 1151 00:58:28,590 --> 00:58:32,200 Alt den gjør er i utgangspunktet teste tidspunktet for alt i ordboken, 1152 00:58:32,200 --> 00:58:33,680 så sørg for at du forstår det. 1153 00:58:33,680 --> 00:58:36,660 Vær forsiktig med å ikke rote med det eller ellers ting vil ikke kjøre skikkelig. 1154 00:58:36,660 --> 00:58:39,740 1155 00:58:39,740 --> 00:58:44,170 >> Og mesteparten av denne utfordringen er for dere å virkelig endre dictionary.c. 1156 00:58:44,170 --> 00:58:48,526 Vi kommer til å gi deg 140.000 ord i en ordbok. 1157 00:58:48,526 --> 00:58:50,900 Vi kommer til å gi deg en tekst fil som har disse ordene, 1158 00:58:50,900 --> 00:58:54,840 og vi vil at du skal være i stand til å organisere dem inn i en hash tabell eller en trie 1159 00:58:54,840 --> 00:58:58,140 fordi når vi ber deg om å stave check-- tenk hvis du er spell 1160 00:58:58,140 --> 00:59:00,690 sjekke ut Homers Odysseen. 1161 00:59:00,690 --> 00:59:03,010 Det er som dette stor, stor test. 1162 00:59:03,010 --> 00:59:05,190 >> Tenk om hver enkelt Ordet du måtte se 1163 00:59:05,190 --> 00:59:08,100 gjennom en rekke 140.000 verdier. 1164 00:59:08,100 --> 00:59:10,350 Det ville ta en evighet for maskinen å kjøre. 1165 00:59:10,350 --> 00:59:14,490 Det er derfor vi ønsker å organisere vår data til mer effektive datastrukturer 1166 00:59:14,490 --> 00:59:17,270 for eksempel en hash tabell eller en trie. 1167 00:59:17,270 --> 00:59:20,700 Og så dere kan kind av når du søker tilgang 1168 00:59:20,700 --> 00:59:22,570 ting lettere og raskere. 1169 00:59:22,570 --> 00:59:24,934 >> Og så vær forsiktig med å løse kollisjoner. 1170 00:59:24,934 --> 00:59:27,350 Du kommer til å få en haug av ord som starter med A. 1171 00:59:27,350 --> 00:59:29,957 Du kommer til å få en haug ord som starter med B. Inntil du 1172 00:59:29,957 --> 00:59:31,290 Gutta hvordan du ønsker å løse det. 1173 00:59:31,290 --> 00:59:34,144 Kanskje det er mer effektiv hash-funksjon 1174 00:59:34,144 --> 00:59:36,810 enn bare den første bokstaven i noe, og slik at det er opp til deg 1175 00:59:36,810 --> 00:59:38,190 Gutta til slags gjøre hva du vil. 1176 00:59:38,190 --> 00:59:40,148 >> Kanskje du ønsker å legge til alle bokstavene sammen. 1177 00:59:40,148 --> 00:59:43,410 Kanskje du vil like å gjøre rare ting å redegjøre antall bokstaver, 1178 00:59:43,410 --> 00:59:43,970 samme det. 1179 00:59:43,970 --> 00:59:45,386 Opp til dere hvordan dere ønsker å gjøre. 1180 00:59:45,386 --> 00:59:49,262 Hvis du ønsker å gjøre en hash table, hvis du ønsker å prøve en trie, helt opp til deg. 1181 00:59:49,262 --> 00:59:52,470 Jeg vil advare deg på forhånd at trie er vanligvis litt vanskeligere 1182 00:59:52,470 --> 00:59:54,520 bare fordi det er mye flere tips for å holde styr på. 1183 00:59:54,520 --> 00:59:55,645 Men helt opp til dere. 1184 00:59:55,645 --> 00:59:58,742 Det er langt mer effektiv i de fleste tilfeller. 1185 00:59:58,742 --> 01:00:01,450 Du ønsker å virkelig være i stand til å holde styr på alle dine pekere. 1186 01:00:01,450 --> 01:00:03,850 Som gjør det samme som jeg gjorde her. 1187 01:00:03,850 --> 01:00:06,871 Når du prøver å sette inn verdier inn i en hash tabell eller slette, 1188 01:00:06,871 --> 01:00:08,620 forsikre deg om at du er virkelig holde styr 1189 01:00:08,620 --> 01:00:11,860 hvor alt er fordi det er veldig lett for hvis jeg er 1190 01:00:11,860 --> 01:00:14,727 prøver å sette inn som ordet, andy. 1191 01:00:14,727 --> 01:00:16,810 La oss bare si at det er en ekte ord, ord, andy, 1192 01:00:16,810 --> 01:00:19,640 inn i en gigantisk liste over A ord. 1193 01:00:19,640 --> 01:00:22,450 >> Hvis jeg bare tilfeldigvis overføre en peker feil, oops, 1194 01:00:22,450 --> 01:00:24,940 det går helheten av resten av mitt lenket liste. 1195 01:00:24,940 --> 01:00:26,897 Nå er det eneste ordet jeg har er andy, og nå 1196 01:00:26,897 --> 01:00:29,230 alle de andre ordene i ordboken ha gått tapt. 1197 01:00:29,230 --> 01:00:31,370 Og så du vil være sikker på at du holde oversikt over alle dine pekere 1198 01:00:31,370 --> 01:00:33,661 eller annet du kommer til å få store problemer i koden din. 1199 01:00:33,661 --> 01:00:35,840 Trekke ut ting nøye steg for steg. 1200 01:00:35,840 --> 01:00:37,870 Det gjør det mye lettere å tenke på. 1201 01:00:37,870 --> 01:00:40,910 >> Og til slutt, vil du være i stand til å teste ytelsen til programmet 1202 01:00:40,910 --> 01:00:41,618 på den store bord. 1203 01:00:41,618 --> 01:00:43,710 Hvis dere tar en se på CS50 akkurat nå, 1204 01:00:43,710 --> 01:00:45,210 vi har det som kalles den store bord. 1205 01:00:45,210 --> 01:00:50,200 Det er poengsummen ark med den raskeste stavekontroll ganger på tvers av alle CS50 1206 01:00:50,200 --> 01:00:55,720 akkurat nå, tror jeg toppen som 10 ganger jeg tror åtte av dem er ansatte. 1207 01:00:55,720 --> 01:00:57,960 Vi ønsker dere å slå oss. 1208 01:00:57,960 --> 01:01:00,870 >> Alle av oss prøvde å implementere den raskeste koden som mulig. 1209 01:01:00,870 --> 01:01:04,880 Vi ønsker dere å prøve å utfordre oss og implementere raskere enn alle oss 1210 01:01:04,880 --> 01:01:05,550 kan. 1211 01:01:05,550 --> 01:01:07,970 Og så dette er virkelig første gang at vi er 1212 01:01:07,970 --> 01:01:12,680 spør dere til å gjøre en PSet som du virkelig kan gjøre uansett metode 1213 01:01:12,680 --> 01:01:13,760 du vil. 1214 01:01:13,760 --> 01:01:17,730 >> Jeg alltid sier, dette er mer beslektet til en real-life løsning, ikke sant? 1215 01:01:17,730 --> 01:01:19,550 Jeg sier hei, jeg trenger deg til å gjøre dette. 1216 01:01:19,550 --> 01:01:21,380 Bygge et program som gjør dette for meg. 1217 01:01:21,380 --> 01:01:22,630 Gjør det slik du vil. 1218 01:01:22,630 --> 01:01:24,271 Jeg bare vet at jeg ønsker å faste. 1219 01:01:24,271 --> 01:01:25,770 Det er din utfordring for denne uken. 1220 01:01:25,770 --> 01:01:27,531 Dere skal vi for å gi deg en oppgave. 1221 01:01:27,531 --> 01:01:29,030 Vi kommer til å gi deg en utfordring. 1222 01:01:29,030 --> 01:01:31,559 Og så er det opp til dere å fullstendig bare finne ut 1223 01:01:31,559 --> 01:01:34,100 hva er den raskeste og mest effektiv måte å gjennomføre dette. 1224 01:01:34,100 --> 01:01:34,600 Yeah? 1225 01:01:34,600 --> 01:01:37,476 >> PUBLIKUM: Er vi lov til hvis ønsket å forske raskere måter 1226 01:01:37,476 --> 01:01:40,821 å gjøre hash tabeller på nettet, kan vi gjøre det og sitere andres koden? 1227 01:01:40,821 --> 01:01:42,070 ANDI PENG: Ja, helt greit. 1228 01:01:42,070 --> 01:01:44,320 Så hvis dere lese spec, det er en linje 1229 01:01:44,320 --> 01:01:48,310 i spec som sier dere er helt gratis å forske hash 1230 01:01:48,310 --> 01:01:51,070 funksjonene på hva er noen av de raskere hash funksjoner 1231 01:01:51,070 --> 01:01:54,720 å kjøre gjennom ting som lenge du sitere denne koden. 1232 01:01:54,720 --> 01:01:57,220 Så noen mennesker har allerede funnet ut raske måter 1233 01:01:57,220 --> 01:02:00,250 av å gjøre stavekontroller, for fort måter å lagre informasjon. 1234 01:02:00,250 --> 01:02:02,750 Helt opp til dere hvis dere ønsker å bare ta det, ikke sant? 1235 01:02:02,750 --> 01:02:04,045 Sørg for at du siterer. 1236 01:02:04,045 --> 01:02:06,170 Utfordringen her egentlig at vi prøver å teste 1237 01:02:06,170 --> 01:02:09,750 er å sørge for at du vet veien rundt pekere. 1238 01:02:09,750 --> 01:02:12,700 Så langt du implementere selve hash-funksjon 1239 01:02:12,700 --> 01:02:15,070 og kommer opp med lignende regnestykket til å gjøre det, 1240 01:02:15,070 --> 01:02:17,570 dere kan undersøke hva metoder online dere ønsker. 1241 01:02:17,570 --> 01:02:17,996 Yeah? 1242 01:02:17,996 --> 01:02:19,700 >> PUBLIKUM: Kan vi sitere bare ved hjelp av [uhørbart]? 1243 01:02:19,700 --> 01:02:20,120 >> ANDI PENG: Yeah. 1244 01:02:20,120 --> 01:02:22,328 Du kan bare, i kommentaren din, Du kan sitere liker, oh, 1245 01:02:22,328 --> 01:02:26,127 tatt fra yada, yada, yada, hash-funksjon. 1246 01:02:26,127 --> 01:02:27,210 Alle som har noen spørsmål? 1247 01:02:27,210 --> 01:02:29,694 Vi har faktisk breezed gjennom seksjonen i dag. 1248 01:02:29,694 --> 01:02:31,610 Jeg vil være her oppe til svare på spørsmål også. 1249 01:02:31,610 --> 01:02:36,570 >> Også, som jeg sa, kontor timer i kveld og i morgen. 1250 01:02:36,570 --> 01:02:40,307 Spec denne uken er faktisk super enkelt og super kort til å lese. 1251 01:02:40,307 --> 01:02:43,140 Jeg foreslår at du tar en titt, bare lese gjennom helheten av det. 1252 01:02:43,140 --> 01:02:45,730 >> Og Zamyla faktisk leder deg gjennom hver av funksjonene 1253 01:02:45,730 --> 01:02:49,796 du trenger for å implementere, og så det er veldig, veldig klart hvordan du gjør alt. 1254 01:02:49,796 --> 01:02:51,920 Bare for å sikre at du er holde styr på pekere. 1255 01:02:51,920 --> 01:02:53,650 Dette er en svært utfordrende PSet. 1256 01:02:53,650 --> 01:02:56,744 >> Det er ikke utfordrende fordi liker, oh, begrepene er så mye mer 1257 01:02:56,744 --> 01:02:59,160 vanskelig, eller du må lære så mye ny syntaks veien 1258 01:02:59,160 --> 01:03:00,650 at du gjorde for den siste PSet. 1259 01:03:00,650 --> 01:03:03,320 Dette PSet er vanskelig fordi det er så mange tips, 1260 01:03:03,320 --> 01:03:06,980 og da er det veldig, veldig lett å en gang du har en feil i koden din ikke kunne 1261 01:03:06,980 --> 01:03:08,315 å finne hvor som feilen er. 1262 01:03:08,315 --> 01:03:13,200 >> Og så fullstendig og absolutt tro på deg gutta å kunne slå vår [uhørbart] 1263 01:03:13,200 --> 01:03:13,700 stavemåter. 1264 01:03:13,700 --> 01:03:16,640 Jeg har faktisk ikke noe skriftlig gruve ennå, men jeg er i ferd med å skrive mine. 1265 01:03:16,640 --> 01:03:19,070 Så mens du skriver yours, jeg skal skrive mine. 1266 01:03:19,070 --> 01:03:21,070 Jeg kommer til å prøve å gjøre min raskere enn din. 1267 01:03:21,070 --> 01:03:23,940 Vi får se hvem som har den raskeste. 1268 01:03:23,940 --> 01:03:27,340 >> Og ja, jeg vil se alle dere her på tirsdag. 1269 01:03:27,340 --> 01:03:29,510 Jeg vil kjøre en slags som en PSet verksted. 1270 01:03:29,510 --> 01:03:32,640 Alle seksjonene denne uke er PSet workshops, 1271 01:03:32,640 --> 01:03:36,690 så dere har mange muligheter om hjelp, kontortiden som alltid, 1272 01:03:36,690 --> 01:03:41,330 og jeg ser virkelig frem til har lest alle dine gutta "kode. 1273 01:03:41,330 --> 01:03:44,160 Jeg har quizer opp her hvis du Gutta ønsker å komme og hente dem. 1274 01:03:44,160 --> 01:03:45,880 Det er alt. 1275 01:03:45,880 --> 01:03:48,180