1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [Musikken afspilles] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: Okay. 5 00:00:12,900 --> 00:00:14,600 Alle velkommen tilbage til afsnittet. 6 00:00:14,600 --> 00:00:18,660 Jeg håber du alle er med succes inddrives fra din quiz 7 00:00:18,660 --> 00:00:19,510 fra sidste uge. 8 00:00:19,510 --> 00:00:22,564 Jeg ved det er en lille smule skør til tider. 9 00:00:22,564 --> 00:00:25,230 Som jeg sagde før, hvis du er inden for standardafvigelsen, 10 00:00:25,230 --> 00:00:28,188 egentlig ikke bekymre dig om det, især for en mindre behagelig sektion. 11 00:00:28,188 --> 00:00:30,230 Det handler om, hvor du skal være. 12 00:00:30,230 --> 00:00:32,850 >> Hvis du gjorde stor, så awesome. 13 00:00:32,850 --> 00:00:33,650 Kudos til dig. 14 00:00:33,650 --> 00:00:36,149 Og hvis du føler at du har brug for lidt mere hjælp, kan du 15 00:00:36,149 --> 00:00:38,140 velkommen til at nå ud til nogen af ​​TFS. 16 00:00:38,140 --> 00:00:40,030 Vi er alle her for at hjælpe. 17 00:00:40,030 --> 00:00:40,960 >> Det er derfor, vi underviser. 18 00:00:40,960 --> 00:00:44,550 Det er derfor, jeg er her hver mandag for dig fyre og på kontoret timer om torsdagen. 19 00:00:44,550 --> 00:00:48,130 Så er du velkommen til at lade mig vide hvis du er bekymret om noget 20 00:00:48,130 --> 00:00:52,450 eller hvis der er noget på quiz at du virkelig gerne vil tage fat på. 21 00:00:52,450 --> 00:00:56,940 >> Så dagsordenen for i dag er Alt om datastrukturer. 22 00:00:56,940 --> 00:01:01,520 Nogle af disse er bare at være lige at få dig fortrolig med disse. 23 00:01:01,520 --> 00:01:04,870 Du må aldrig gennemføre dem i denne klasse. 24 00:01:04,870 --> 00:01:08,690 Nogle af dem du vil, lignende for din speller pset. 25 00:01:08,690 --> 00:01:11,380 >> Du har dit valg mellem hash tabeller og forsøger. 26 00:01:11,380 --> 00:01:13,680 Så vi vil helt sikkert være at gå over dem. 27 00:01:13,680 --> 00:01:18,690 Det kommer til at være absolut mere af naturalier af høj sektion niveau i dag, selv om, 28 00:01:18,690 --> 00:01:22,630 fordi der er en masse af dem, og hvis vi gik i detaljer med gennemførelsen 29 00:01:22,630 --> 00:01:26,490 på alle disse, ville vi ikke selv komme igennem hægtede lister 30 00:01:26,490 --> 00:01:28,520 og måske en lille smule hash-tabeller. 31 00:01:28,520 --> 00:01:31,200 >> Så bær over med mig. 32 00:01:31,200 --> 00:01:33,530 Vi kommer ikke til at gøre så meget som koder dette tidspunkt. 33 00:01:33,530 --> 00:01:36,870 Hvis du har spørgsmål om det eller du ønsker at se det gennemført 34 00:01:36,870 --> 00:01:39,260 eller prøv det selv, Jeg helt klart anbefale 35 00:01:39,260 --> 00:01:44,250 vil study.cs50.net, som har eksempler på alle disse. 36 00:01:44,250 --> 00:01:46,400 Det vil have mine PowerPoints med de noter, vi 37 00:01:46,400 --> 00:01:50,860 tendens til at bruge samt nogle programmering øvelser, især for ting 38 00:01:50,860 --> 00:01:55,250 ligesom hægtede lister og binær træer stakke og køer. 39 00:01:55,250 --> 00:01:59,590 Så lidt mere højt niveau, som kunne være rart for jer. 40 00:01:59,590 --> 00:02:01,320 >> Så med dette, vil vi komme i gang. 41 00:02:01,320 --> 00:02:03,060 Og også, yes-- quizzer. 42 00:02:03,060 --> 00:02:06,550 Jeg tror de fleste af jer, der er i min afdeling har dine quizzer, 43 00:02:06,550 --> 00:02:12,060 men nogen kommer i eller anden grund ikke gør det, de er lige her i front. 44 00:02:12,060 --> 00:02:12,740 >> Så hægtede lister. 45 00:02:12,740 --> 00:02:15,650 Jeg kender denne slags går at sikkerhedskopiere før din quiz. 46 00:02:15,650 --> 00:02:17,940 Det var ugen før at vi lærte om dette. 47 00:02:17,940 --> 00:02:21,040 Men i dette tilfælde, vil vi blot gå lidt mere i dybden. 48 00:02:21,040 --> 00:02:25,900 >> Så hvorfor kan vi vælge en sammenkædet liste over en array? 49 00:02:25,900 --> 00:02:27,130 Hvad adskiller dem? 50 00:02:27,130 --> 00:02:27,630 Ja? 51 00:02:27,630 --> 00:02:30,464 >> PUBLIKUM: Du kan udvide en sammenkædet listen versus et array er fast størrelse. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Right. 53 00:02:31,171 --> 00:02:33,970 Et array har fast størrelse mens en linket liste har en variabel størrelse. 54 00:02:33,970 --> 00:02:36,970 Så hvis vi ikke ved, hvordan meget vi ønsker at gemme, 55 00:02:36,970 --> 00:02:39,880 en sammenkædet liste giver os en stor måde at gøre det, fordi vi kan bare 56 00:02:39,880 --> 00:02:43,730 tilføje en anden node og tilføje et andet knudepunkt og tilføje en anden node. 57 00:02:43,730 --> 00:02:45,750 Men hvad der kunne være et trade-off? 58 00:02:45,750 --> 00:02:49,521 Er der nogen der kan huske det trade-off mellem arrays og hægtede lister? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> PUBLIKUM: Du er nødt til gå igennem hele vejen 61 00:02:51,460 --> 00:02:53,738 gennem linkede liste finde et element i en liste. 62 00:02:53,738 --> 00:02:55,570 I et array, kan du bare finde et element. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Right. 64 00:02:56,278 --> 00:02:57,120 Så med arrays-- 65 00:02:57,120 --> 00:02:58,500 >> PUBLIKUM: [uhørligt]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: Med arrays, vi har hvad der kaldes random access. 67 00:03:01,090 --> 00:03:04,820 Betyder, at hvis vi ønsker, hvad er nogensinde femte punkt af en liste 68 00:03:04,820 --> 00:03:07,230 eller det femte punkt i vores array, kan vi bare få fat i det. 69 00:03:07,230 --> 00:03:10,440 Hvis det er en linket liste, vi har at gentage gennem, right? 70 00:03:10,440 --> 00:03:14,020 Så at få adgang til et element i et array er konstant tid, 71 00:03:14,020 --> 00:03:19,530 hvorimod med en sammenkædet liste ville det sandsynligvis være lineær tid, fordi måske 72 00:03:19,530 --> 00:03:21,370 vores element er hele vejen i slutningen. 73 00:03:21,370 --> 00:03:23,446 Vi er nødt til at søge gennem alt. 74 00:03:23,446 --> 00:03:25,320 Så med alle disse data strukturer vi kommer 75 00:03:25,320 --> 00:03:29,330 at bruge lidt mere tid på, hvad er plusser og negativer. 76 00:03:29,330 --> 00:03:31,480 Hvornår kan vi ønsker at bruge den ene over den anden? 77 00:03:31,480 --> 00:03:34,970 Og det er sådan det større ting at tage væk. 78 00:03:34,970 --> 00:03:40,140 >> Så vi har her definition af et knudepunkt. 79 00:03:40,140 --> 00:03:43,040 Det er ligesom et element i vores linkede liste, right? 80 00:03:43,040 --> 00:03:46,180 Så vi er alle bekendt med vores typedef structs, 81 00:03:46,180 --> 00:03:47,980 som vi gik over bedømmelsesudvalg sidste gang. 82 00:03:47,980 --> 00:03:53,180 Det var dybest set blot at skabe en anden datatype, som vi kunne bruge. 83 00:03:53,180 --> 00:03:57,930 >> Og i dette tilfælde, det er nogle node der vil holde nogle heltal i. 84 00:03:57,930 --> 00:04:00,210 Og hvad er så den anden del her? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Anyone? 87 00:04:05,677 --> 00:04:06,680 >> PUBLIKUM: [uhørligt]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Ja. 89 00:04:07,020 --> 00:04:08,400 Det er en pointer til det næste knudepunkt. 90 00:04:08,400 --> 00:04:12,610 Så dette burde faktisk være her oppe. 91 00:04:12,610 --> 00:04:18,790 Dette er en henvisning af typen node til den næste ting. 92 00:04:18,790 --> 00:04:22,410 Og det er, hvad de omfatter vores node. 93 00:04:22,410 --> 00:04:24,060 Cool. 94 00:04:24,060 --> 00:04:29,390 >> Okay, så med søgning, som vi var bare at sige før hånd, hvis du er 95 00:04:29,390 --> 00:04:31,840 kommer til at søge igennem, du er nødt til rent faktisk at gentage 96 00:04:31,840 --> 00:04:33,660 gennem din linkede liste. 97 00:04:33,660 --> 00:04:38,530 Så hvis vi leder efter det antal 9, vil vi starte på vores hoved 98 00:04:38,530 --> 00:04:41,520 og som peger os i begyndelsen af vores linkede liste, right? 99 00:04:41,520 --> 00:04:44,600 Og vi siger, OK, gør dette node indeholder nummer 9? 100 00:04:44,600 --> 00:04:45,690 Nej? 101 00:04:45,690 --> 00:04:47,500 >> Okay, gå til den næste. 102 00:04:47,500 --> 00:04:48,312 Følg det. 103 00:04:48,312 --> 00:04:49,520 Indeholder det nummer 9? 104 00:04:49,520 --> 00:04:50,570 Nej. 105 00:04:50,570 --> 00:04:51,550 Følg den næste. 106 00:04:51,550 --> 00:04:55,490 >> Så vi er nødt til rent faktisk at gentage gennem vores linkede liste. 107 00:04:55,490 --> 00:05:00,070 Vi kan ikke bare gå direkte til, hvor 9 er. 108 00:05:00,070 --> 00:05:05,860 Og hvis du fyre rent faktisk ønsker at se nogle pseudo-kode deroppe. 109 00:05:05,860 --> 00:05:10,420 Vi har nogle søgefunktionen her der tager in-- hvad tager det i? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Hvad mener du? 112 00:05:14,320 --> 00:05:15,960 Så let. 113 00:05:15,960 --> 00:05:17,784 Hvad er dette? 114 00:05:17,784 --> 00:05:18,700 PUBLIKUM: [uhørligt]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: Antallet, vi leder efter. 116 00:05:20,366 --> 00:05:20,980 Right? 117 00:05:20,980 --> 00:05:22,875 Og hvad ville det svare til? 118 00:05:22,875 --> 00:05:25,020 Det er en pointer til? 119 00:05:25,020 --> 00:05:26,000 >> PUBLIKUM: En node. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: A node til listen at vi kigger på, right? 121 00:05:28,980 --> 00:05:33,700 Så vi har nogle knuder er pointer her. 122 00:05:33,700 --> 00:05:37,240 Det er et punkt, der kommer til faktisk gentage gennem vores liste. 123 00:05:37,240 --> 00:05:39,630 Vi sætter det lige at liste fordi det er bare 124 00:05:39,630 --> 00:05:44,380 sætte den lig med start af vores linkede liste. 125 00:05:44,380 --> 00:05:50,660 >> Og mens det ikke er NULL, mens vi stadig har ting i vores liste, 126 00:05:50,660 --> 00:05:55,580 kontrollere, om denne knude har det nummer, vi leder efter. 127 00:05:55,580 --> 00:05:57,740 Returnere sandt. 128 00:05:57,740 --> 00:06:01,070 Ellers opdatere det, right? 129 00:06:01,070 --> 00:06:04,870 >> Hvis det er NULL, vi afslutte vores mens loop og return false 130 00:06:04,870 --> 00:06:08,340 fordi det betyder, at vi ikke har fundet det. 131 00:06:08,340 --> 00:06:11,048 Skal alle få, hvordan det fungerer? 132 00:06:11,048 --> 00:06:11,548 OK. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Så med indsættelse, du have tre forskellige måder. 135 00:06:20,260 --> 00:06:25,250 Du kan tilføjes i begyndelsen, du kan føje og du kan indsætte i assorteret. 136 00:06:25,250 --> 00:06:28,215 I dette tilfælde er vi kommer til at gøre en prepend. 137 00:06:28,215 --> 00:06:33,380 Er der nogen vide, hvordan de tre tilfælde kan afvige? 138 00:06:33,380 --> 00:06:36,920 >> Så prepend betyder, at du lægger det på forsiden af ​​din liste. 139 00:06:36,920 --> 00:06:39,770 Så ville det betyde, at uanset hvad din node er, uanset 140 00:06:39,770 --> 00:06:43,160 hvad værdien er, er du nødt at sætte det her i front, OK? 141 00:06:43,160 --> 00:06:45,160 Det kommer til at være den første element på din liste. 142 00:06:45,160 --> 00:06:49,510 >> Hvis du vedhæfte det, går det at gå til bagsiden af ​​din liste. 143 00:06:49,510 --> 00:06:54,010 Og indsætte i assorterede betyder, at du vil sætte faktisk til stedet 144 00:06:54,010 --> 00:06:57,700 hvor det holder din linkede liste sorteres. 145 00:06:57,700 --> 00:07:00,810 Igen, hvordan du bruger dem, og når du bruger 146 00:07:00,810 --> 00:07:02,530 dem vil variere afhængigt af din sag. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Hvis det ikke er nødvendigt at sorteres, prepend tendens 149 00:07:07,750 --> 00:07:10,460 at være, hvad de fleste mennesker bruge, fordi du ikke 150 00:07:10,460 --> 00:07:15,680 nødt til at gå igennem hele listen at finde enden for at tilføje det på, right? 151 00:07:15,680 --> 00:07:17,720 Du kan bare holde det ret i. 152 00:07:17,720 --> 00:07:21,930 >> Så vi vil gå gennem en indsættelse 1 lige nu. 153 00:07:21,930 --> 00:07:26,360 Så én ting, jeg har tænkt mig at anbefaler på denne pset 154 00:07:26,360 --> 00:07:29,820 er at trække tingene ud, som altid. 155 00:07:29,820 --> 00:07:35,130 Det er meget vigtigt, at du opdaterer dine pejlemærker i den rigtige rækkefølge 156 00:07:35,130 --> 00:07:38,620 fordi hvis du opdaterer dem lidt ud af orden, 157 00:07:38,620 --> 00:07:42,210 du kommer til at ende op miste dele af din liste. 158 00:07:42,210 --> 00:07:49,680 >> Så for eksempel, i dette tilfælde, er vi fortæller hovedet til blot punkt 1. 159 00:07:49,680 --> 00:07:56,070 Hvis vi bare gør det uden at gemme denne 1, 160 00:07:56,070 --> 00:07:58,570 vi har ingen idé om, hvad 1 skal pege på nu 161 00:07:58,570 --> 00:08:02,490 fordi vi har mistet, hvad hovedet pegede på. 162 00:08:02,490 --> 00:08:05,530 Så én ting at huske når du laver en prepend 163 00:08:05,530 --> 00:08:09,630 er at spare, hvad hoved peger på første, 164 00:08:09,630 --> 00:08:15,210 derefter videreoverdrage dem, og derefter opdatere hvad din nye node skal pege på. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 I dette tilfælde, dette er en måde at gøre det. 167 00:08:22,560 --> 00:08:25,440 >> Så hvis vi havde gjort det på denne måde hvor vi netop genindtrådt hoved, 168 00:08:25,440 --> 00:08:30,320 vi mister dybest set vores hele listen, right? 169 00:08:30,320 --> 00:08:38,000 En måde at gøre det på er at have 1 point til næste, og så har hoved punkt 1. 170 00:08:38,000 --> 00:08:42,650 Eller du kan gøre lidt ligesom midlertidig oplagring, som jeg talte om. 171 00:08:42,650 --> 00:08:45,670 >> Men omfordeling din pejlemærker i den rigtige rækkefølge 172 00:08:45,670 --> 00:08:48,750 kommer til at være meget, meget vigtigt for denne pset. 173 00:08:48,750 --> 00:08:53,140 Ellers er du nødt til at have en hash tabel eller en prøve, der er bare kommer til at være 174 00:08:53,140 --> 00:08:56,014 kun en del af de ord, du ønsker, og derefter you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 PUBLIKUM: Hvad var den midlertidige opbevaring ting, du talte om? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: midlertidig opbevaring. 177 00:09:00,305 --> 00:09:02,760 Så dybest set en anden måde du kan gøre dette 178 00:09:02,760 --> 00:09:07,650 er lagre lederen af ​​noget, ligesom gemme det midlertidigt variabel. 179 00:09:07,650 --> 00:09:11,250 Tildele den til 1 og derefter opdatere 1 til punkt 180 00:09:11,250 --> 00:09:13,830 til uanset hoved bruges til at pege på. 181 00:09:13,830 --> 00:09:16,920 Denne måde er naturligvis mere elegant, fordi du 182 00:09:16,920 --> 00:09:20,770 behøver ikke en midlertidig værdi, men bare tilbyde en anden måde at gøre det. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 Og vi har faktisk noget kode til dette. 185 00:09:25,790 --> 00:09:28,080 Så for linkede liste, vi faktisk har nogle kode. 186 00:09:28,080 --> 00:09:31,930 Så indsætte her, er dette prepending. 187 00:09:31,930 --> 00:09:34,290 Så dette ind i det ved hovedet. 188 00:09:34,290 --> 00:09:38,820 >> Så første ting, du skal oprette din nye node, selvfølgelig, 189 00:09:38,820 --> 00:09:40,790 og tjekke for NULL. 190 00:09:40,790 --> 00:09:43,250 Altid godt. 191 00:09:43,250 --> 00:09:47,840 Og så er du nødt til at tildele værdier. 192 00:09:47,840 --> 00:09:51,260 Når du opretter en ny node, du ved ikke, hvad det er at pege på næste, 193 00:09:51,260 --> 00:09:54,560 så du ønsker at initialisere den til NULL. 194 00:09:54,560 --> 00:09:58,760 Hvis det ikke ender peger på noget andet, det bliver omfordelt, og det er fint. 195 00:09:58,760 --> 00:10:00,740 Hvis det er den første ting på listen, er det nødvendigt 196 00:10:00,740 --> 00:10:04,270 at pege på NULL, fordi det er slutningen af ​​listen. 197 00:10:04,270 --> 00:10:12,410 >> Så for at indsætte det, vi ser her vi tildeler den næste værdi af vores node 198 00:10:12,410 --> 00:10:17,380 at være, hvad hovedet er hvilket er, hvad vi havde her. 199 00:10:17,380 --> 00:10:19,930 Det er hvad vi lige gjorde. 200 00:10:19,930 --> 00:10:25,820 Og så er vi tildele hoved til punkt til vores nye knudepunkt, fordi huske, 201 00:10:25,820 --> 00:10:31,090 ny er nogle pointer til et knudepunkt, og det er præcis, hvad hovedet er. 202 00:10:31,090 --> 00:10:34,370 Det er præcis derfor, vi har denne pil tilb. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Cool? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> PUBLIKUM: Skal vi initialisere ny næste NULL første, 207 00:10:41,100 --> 00:10:44,240 eller kan vi bare initialisere den til hovedet? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: Ny næste skal være NULL til at starte 209 00:10:48,210 --> 00:10:53,760 fordi du ikke kender hvor det kommer til at være. 210 00:10:53,760 --> 00:10:56,100 Også dette er slags ligesom et paradigme. 211 00:10:56,100 --> 00:10:59,900 Du sætter det lig med NULL bare for at gøre sikker på, at alle dine baser er dækket 212 00:10:59,900 --> 00:11:04,070 før du gør nogen omplacering, således at er du altid garanteret, at den vil 213 00:11:04,070 --> 00:11:08,880 pege på en bestemt værdi versus ligesom en garbage værdi. 214 00:11:08,880 --> 00:11:12,210 Fordi, ja, vi tildeler ny næste automatisk, 215 00:11:12,210 --> 00:11:15,420 men det er mere ligesom en god praksis at initialisere det 216 00:11:15,420 --> 00:11:19,270 på den måde og derefter overflytte. 217 00:11:19,270 --> 00:11:23,420 >> OK, så dobbelt hægtede lister nu. 218 00:11:23,420 --> 00:11:24,601 Hvad mener vi? 219 00:11:24,601 --> 00:11:26,350 Hvad er anderledes med dobbelt hægtede lister? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Så i vores hægtede lister, vi kan kun bevæge sig i én retning, right? 222 00:11:34,300 --> 00:11:35,270 Vi har kun næste. 223 00:11:35,270 --> 00:11:36,760 Vi kan kun gå fremad. 224 00:11:36,760 --> 00:11:40,300 >> Med en dobbelt sammenkædet liste, Vi kan også bevæge sig baglæns. 225 00:11:40,300 --> 00:11:44,810 Så vi har ikke kun nummer, som vi ønsker at gemme, 226 00:11:44,810 --> 00:11:50,110 vi har hvor den peger på næste og hvor vi bare kom fra. 227 00:11:50,110 --> 00:11:52,865 Så det giver mulighed for nogle bedre traversal. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Så dobbelt forbundne knudepunkter, meget ens, right? 230 00:12:01,240 --> 00:12:05,000 Eneste forskel er nu vi har en næste og foregående. 231 00:12:05,000 --> 00:12:06,235 Det er den eneste forskel. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Så hvis vi skulle tilføjes i begyndelsen eller append-- vi ikke har nogen kode for denne op her-- 234 00:12:14,790 --> 00:12:17,830 men hvis du skulle prøve og indsætte det, det vigtigste 235 00:12:17,830 --> 00:12:19,980 er du nødt til at gøre sikker på du tildele 236 00:12:19,980 --> 00:12:23,360 både din tidligere og din næste pointer korrekt. 237 00:12:23,360 --> 00:12:29,010 Så i dette tilfælde, ville du ikke kun initialisere næste, 238 00:12:29,010 --> 00:12:31,820 du initialiserer tidligere. 239 00:12:31,820 --> 00:12:36,960 Hvis vi er i spidsen af ​​listen, vi ville ikke kun gøre hoved lige nye, 240 00:12:36,960 --> 00:12:41,750 men vores nye tidligere skulle peger på hovedet, right? 241 00:12:41,750 --> 00:12:43,380 >> Det er den eneste forskel. 242 00:12:43,380 --> 00:12:47,200 Og hvis du ønsker mere praksis med disse med hægtede lister, med indsættelse, 243 00:12:47,200 --> 00:12:49,900 med at slette, med indsats ind i et velassorteret liste 244 00:12:49,900 --> 00:12:52,670 Venligst tjek study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Der er en masse store øvelser. 246 00:12:54,870 --> 00:12:55,870 Jeg kan varmt anbefale dem. 247 00:12:55,870 --> 00:12:59,210 Jeg ville ønske, vi havde tid til at gå igennem dem men der er en masse af datastrukturer 248 00:12:59,210 --> 00:13:01,530 at komme igennem. 249 00:13:01,530 --> 00:13:02,650 >> OK, så hash-tabeller. 250 00:13:02,650 --> 00:13:07,070 Dette er sandsynligvis den mest nyttige bit for din pset 251 00:13:07,070 --> 00:13:11,090 her, fordi du vil være gennemføre en af ​​disse, eller en prøve. 252 00:13:11,090 --> 00:13:12,200 Jeg kan virkelig godt lide hash-tabeller. 253 00:13:12,200 --> 00:13:13,110 De er pretty cool. 254 00:13:13,110 --> 00:13:17,080 >> Så dybest set, hvad sker, er en hash tabel 255 00:13:17,080 --> 00:13:22,050 er, når vi virkelig har brug for hurtig indsættelse, sletning og opslag. 256 00:13:22,050 --> 00:13:25,010 Det er de ting, som vi er prioritering i en hash tabel. 257 00:13:25,010 --> 00:13:29,500 De kan få temmelig store, men som vi skal se med forsøg, 258 00:13:29,500 --> 00:13:33,040 Der er ting, der er meget større. 259 00:13:33,040 --> 00:13:38,330 >> Men dybest set, alle en hash tabel er en hash-funktion 260 00:13:38,330 --> 00:13:47,215 der fortæller dig, hvilken spand til at sætte hver af dine data, hver af dine elementer i. 261 00:13:47,215 --> 00:13:51,140 En enkel måde at tænke på en hash tabel er, at det er bare spande af ting, 262 00:13:51,140 --> 00:13:51,770 højre? 263 00:13:51,770 --> 00:13:59,720 Så når du sorterer tingene ved ligesom det første bogstav i deres navn, 264 00:13:59,720 --> 00:14:01,820 det er lidt ligesom en hash tabel. 265 00:14:01,820 --> 00:14:06,180 >> Så hvis jeg var til gruppe, du fyre er i grupper af hvem navn starter 266 00:14:06,180 --> 00:14:11,670 med A herovre, eller hvem har fødselsdag er i januar, februar, marts, 267 00:14:11,670 --> 00:14:15,220 uanset hvad, det er effektivt skabe en hash tabel. 268 00:14:15,220 --> 00:14:18,120 Det er bare at skabe spande som du sortere dine elementer i 269 00:14:18,120 --> 00:14:19,520 så du kan finde dem lettere. 270 00:14:19,520 --> 00:14:22,300 Så på denne måde, når jeg har brug for at finde en af ​​jer, 271 00:14:22,300 --> 00:14:24,680 Jeg behøver ikke at søge gennem hver af dine navne. 272 00:14:24,680 --> 00:14:29,490 Jeg kan være ligesom, åh, jeg ved, at Danielle fødselsdag er in-- 273 00:14:29,490 --> 00:14:30,240 PUBLIKUM: --April. 274 00:14:30,240 --> 00:14:30,948 SPEAKER 1: April. 275 00:14:30,948 --> 00:14:33,120 Så jeg ser i min April spand, og med lidt held, 276 00:14:33,120 --> 00:14:38,270 hun vil være den eneste i der, og min tid var konstant i den forstand, 277 00:14:38,270 --> 00:14:41,230 hvorimod hvis jeg nødt til at se gennem en hel masse mennesker, 278 00:14:41,230 --> 00:14:43,090 det kommer til at tage meget længere tid. 279 00:14:43,090 --> 00:14:45,830 Så hash tabeller er egentlig bare spande. 280 00:14:45,830 --> 00:14:48,630 Nem måde at tænke på dem. 281 00:14:48,630 --> 00:14:52,930 >> Så en meget vigtig ting om en hash tabel er en hash-funktion. 282 00:14:52,930 --> 00:14:58,140 Så de ting, jeg lige talt om, ligesom dit første bogstav i dit fornavn 283 00:14:58,140 --> 00:15:01,450 eller din fødselsdag måned, disse ideer, 284 00:15:01,450 --> 00:15:03,070 virkelig korrelere til en hash-funktion. 285 00:15:03,070 --> 00:15:08,900 Det er bare en måde at afgøre hvilke spand, du element går ind, OK? 286 00:15:08,900 --> 00:15:14,850 Så for denne pset, kan du slå op temmelig meget enhver hash funktion, du ønsker. 287 00:15:14,850 --> 00:15:16,030 >> Behøver ikke at være din egen. 288 00:15:16,030 --> 00:15:21,140 Der er nogle virkelig cool dem ud der at gøre alle mulige skøre matematik. 289 00:15:21,140 --> 00:15:25,170 Og hvis du ønsker at gøre dit stavekontrollen super hurtig, 290 00:15:25,170 --> 00:15:27,620 Jeg ville helt sikkert se på en af ​​dem. 291 00:15:27,620 --> 00:15:32,390 >> Men der er også den simple dem, ligesom beregne 292 00:15:32,390 --> 00:15:39,010 summen af ​​de ord, som hvert bogstav har en række. 293 00:15:39,010 --> 00:15:39,940 Beregne summen. 294 00:15:39,940 --> 00:15:42,230 Der afgør spanden. 295 00:15:42,230 --> 00:15:45,430 De har også de nemme dem, er ligesom alle A'er her, 296 00:15:45,430 --> 00:15:47,050 alle B er her. 297 00:15:47,050 --> 00:15:48,920 Enhver en af ​​dem. 298 00:15:48,920 --> 00:15:55,770 >> Dybest set, det bare fortæller dig, hvilke arrayindeks dit element skal gå ind. 299 00:15:55,770 --> 00:15:58,690 Bare afgøre bucket-- det hele er en hash-funktion er. 300 00:15:58,690 --> 00:16:04,180 Så her har vi et eksempel, som er bare det første bogstav i strengen 301 00:16:04,180 --> 00:16:05,900 at jeg bare taler om. 302 00:16:05,900 --> 00:16:11,900 >> Så du har nogle hash det er bare første bogstav i din streng minus A, 303 00:16:11,900 --> 00:16:16,090 som vil give dig nogle tal mellem 0 og 25. 304 00:16:16,090 --> 00:16:20,790 Og hvad du ønsker at gøre, er sørge for, at dette repræsenterer 305 00:16:20,790 --> 00:16:24,110 størrelsen af ​​din hash table-- hvor mange spande der er. 306 00:16:24,110 --> 00:16:25,860 Med mange af disse hashfunktioner, de er 307 00:16:25,860 --> 00:16:31,630 vil være tilbage værdier, der kan være langt over det antal spande 308 00:16:31,630 --> 00:16:33,610 at du rent faktisk har i din hash tabel, 309 00:16:33,610 --> 00:16:37,240 så du behøver at gøre sikker og MOD af dem. 310 00:16:37,240 --> 00:16:42,190 Ellers går det til at sige, oh, bør det være i spand 5.000 311 00:16:42,190 --> 00:16:46,040 men du har kun 30 spande i din hash tabellen. 312 00:16:46,040 --> 00:16:49,360 Og selvfølgelig, vi alle ved, det er kommer til at resultere i nogle vanvittige fejl. 313 00:16:49,360 --> 00:16:52,870 Så sørg for at Mod ved størrelsen på din hash tabellen. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Cool. 316 00:16:58,930 --> 00:17:00,506 Så kollisioner. 317 00:17:00,506 --> 00:17:02,620 Er alle godt hidtil? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> PUBLIKUM: Hvorfor ville det returnere en sådan massiv værdi? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: Afhængigt af algoritmen at din hash funktion bruger. 321 00:17:09,210 --> 00:17:12,270 Nogle af dem vil gøre crazy multiplikation. 322 00:17:12,270 --> 00:17:16,270 Og det handler om at få en jævn fordeling, 323 00:17:16,270 --> 00:17:18,490 så de gør nogle virkelig skøre ting undertiden. 324 00:17:18,490 --> 00:17:20,960 Det er alt. 325 00:17:20,960 --> 00:17:22,140 Noget andet? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Så kollisioner. 328 00:17:24,480 --> 00:17:29,270 Dybest set, som jeg sagde tidligere, i bedste fald, 329 00:17:29,270 --> 00:17:32,040 enhver spand jeg ser ind i, er vil have en ting, 330 00:17:32,040 --> 00:17:34,160 så jeg ikke behøver at se på alle, right? 331 00:17:34,160 --> 00:17:37,040 Jeg enten ved, det er der, eller det er ikke, og det er, hvad vi virkelig ønsker. 332 00:17:37,040 --> 00:17:43,960 Men hvis vi har titusinder af datapunkter og mindre end dette antal 333 00:17:43,960 --> 00:17:48,700 af spande, vi kommer til at have kollisioner, hvor tiden noget 334 00:17:48,700 --> 00:17:54,210 er nødt til at ende i en spand, der allerede har et element. 335 00:17:54,210 --> 00:17:57,390 >> Så spørgsmålet er, hvad gør vi i dette tilfælde? 336 00:17:57,390 --> 00:17:58,480 Hvad gør vi? 337 00:17:58,480 --> 00:17:59,300 Vi har allerede noget der? 338 00:17:59,300 --> 00:18:00,060 Skal vi bare smide det ud? 339 00:18:00,060 --> 00:18:00,700 >> Nej. 340 00:18:00,700 --> 00:18:01,980 Vi er nødt til at holde dem begge. 341 00:18:01,980 --> 00:18:06,400 Så den måde, at vi typisk gør, der er hvad? 342 00:18:06,400 --> 00:18:08,400 Hvad er datastrukturen vi netop talt om? 343 00:18:08,400 --> 00:18:09,316 PUBLIKUM: Linked listen. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: En linkede liste. 345 00:18:10,500 --> 00:18:16,640 Så nu, i stedet for hver af disse spande bare at have et element, 346 00:18:16,640 --> 00:18:24,020 det kommer til at indeholde en sammenkædet liste over de elementer, der blev hashed ind i det. 347 00:18:24,020 --> 00:18:27,588 OK, er alle slags få den idé? 348 00:18:27,588 --> 00:18:30,546 Fordi vi ikke kunne få et array fordi vi ikke ved, hvordan mange ting 349 00:18:30,546 --> 00:18:31,730 kommer til at være der. 350 00:18:31,730 --> 00:18:36,540 En linket liste giver os mulighed for har netop det nøjagtige antal, der 351 00:18:36,540 --> 00:18:38,465 er hashet i den spand, right? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Så lineær sondering er dybest set dette idea-- 354 00:18:50,500 --> 00:18:52,300 det er en måde at beskæftige sig med en kollision. 355 00:18:52,300 --> 00:18:58,010 Hvad du kan gøre er, hvis, i dette tilfælde, bær blev makulerede i 1 356 00:18:58,010 --> 00:19:01,130 og vi har allerede noget der, du bare 357 00:19:01,130 --> 00:19:04,840 holde gå ned, indtil du finde en tom slot. 358 00:19:04,840 --> 00:19:06,370 Det er en måde at håndtere det. 359 00:19:06,370 --> 00:19:09,020 Den anden måde at håndtere det er med det, vi lige 360 00:19:09,020 --> 00:19:12,280 called-- den linkede listen kaldes chaining. 361 00:19:12,280 --> 00:19:20,510 >> Så denne idé virker, hvis din hashtabel du tror 362 00:19:20,510 --> 00:19:24,150 er meget større end dine data sæt, eller hvis du 363 00:19:24,150 --> 00:19:28,870 ønsker at forsøge at minimere kæde indtil det er absolut nødvendigt. 364 00:19:28,870 --> 00:19:34,050 Så én ting er lineær sondering betyder naturligvis 365 00:19:34,050 --> 00:19:37,290 at din hash funktion er ikke helt så nyttig 366 00:19:37,290 --> 00:19:42,200 fordi du vil ender med at bruge din hash-funktionen, at komme til et punkt, 367 00:19:42,200 --> 00:19:46,400 du lineær sonde ned til et sted, der er til rådighed. 368 00:19:46,400 --> 00:19:49,670 Men nu, selvfølgelig, noget andet, der ender der, 369 00:19:49,670 --> 00:19:52,050 du er nødt til at søge endnu længere nede. 370 00:19:52,050 --> 00:19:55,650 >> Og der er meget mere Søg udgift, 371 00:19:55,650 --> 00:19:59,820 går i indtastning af en element i din hash tabellen nu, right? 372 00:19:59,820 --> 00:20:05,640 Og nu når du gå og forsøge at finde bær igen, er du nødt til hash det, 373 00:20:05,640 --> 00:20:07,742 og det kommer til at sige, åh, kigge i spand 1, 374 00:20:07,742 --> 00:20:09,700 og det kommer ikke til at være i spand 1, så du er 375 00:20:09,700 --> 00:20:11,970 nødt til at krydse gennem resten af ​​disse. 376 00:20:11,970 --> 00:20:17,720 Så det er til tider nyttigt, men i de fleste tilfælde 377 00:20:17,720 --> 00:20:22,660 vi kommer til at sige, at chaining er, hvad du ønsker at gøre. 378 00:20:22,660 --> 00:20:25,520 >> Så vi talte om det tidligere. 379 00:20:25,520 --> 00:20:27,812 Jeg fik lidt foran mig. 380 00:20:27,812 --> 00:20:33,560 Men chaining er dybest set at hver spand i din hashtabel 381 00:20:33,560 --> 00:20:36,120 er blot en linket liste. 382 00:20:36,120 --> 00:20:39,660 >> Så en anden måde, eller mere teknisk måde at tænke på en hash tabel 383 00:20:39,660 --> 00:20:44,490 er, at det er bare et array af hægtede lister, som 384 00:20:44,490 --> 00:20:49,330 når du skriver din ordbog og du forsøger at indlæse den, 385 00:20:49,330 --> 00:20:52,070 tænker på det som en vifte af hægtede lister 386 00:20:52,070 --> 00:20:54,390 vil gøre det meget nemmere for dig at klargøre. 387 00:20:54,390 --> 00:20:57,680 >> PUBLIKUM: Så hashtabel har en forudbestemt størrelse, 388 00:20:57,680 --> 00:20:58,980 ligesom en [uhørligt] spande? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Right. 390 00:20:59,220 --> 00:21:01,655 Så det har et bestemt antal spande, som du determine-- 391 00:21:01,655 --> 00:21:03,530 som du fyre bør velkommen til at spille med. 392 00:21:03,530 --> 00:21:05,269 Det kan være temmelig cool at se hvad der sker 393 00:21:05,269 --> 00:21:06,810 som du ændrer din antal spande. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Men ja, det har en sæt antal spande. 396 00:21:11,510 --> 00:21:15,360 Hvad giver dig mulighed for at passe så mange elementer, som du har brug for 397 00:21:15,360 --> 00:21:19,350 er dette særskilt kæde, hvor du har knyttet lister i hver spand. 398 00:21:19,350 --> 00:21:22,850 Det betyder, at din hash tabel vil være nøjagtig størrelse 399 00:21:22,850 --> 00:21:25,440 at du har brug for det at være, ikke? 400 00:21:25,440 --> 00:21:27,358 Det er hele pointen i hægtede lister. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Cool. 403 00:21:32,480 --> 00:21:38,780 >> Så alle OK der? 404 00:21:38,780 --> 00:21:39,801 Ok. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Hvad skete der lige? 407 00:21:41,860 --> 00:21:42,960 Virkelig nu. 408 00:21:42,960 --> 00:21:45,250 Gæt nogen har at dræbe mig. 409 00:21:45,250 --> 00:21:52,060 >> OK, vi kommer til at gå ind i lande, som er lidt skør. 410 00:21:52,060 --> 00:21:53,140 Jeg kan lide hash-tabeller. 411 00:21:53,140 --> 00:21:54,460 Jeg tror, ​​de er virkelig cool. 412 00:21:54,460 --> 00:21:56,710 Lande er cool, også. 413 00:21:56,710 --> 00:21:59,590 >> Så er der nogen huske, hvad en prøve er? 414 00:21:59,590 --> 00:22:01,740 Du skulle have gået over det kortvarigt i forelæsning? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Kan du huske slags hvordan det virker? 417 00:22:06,377 --> 00:22:08,460 PUBLIKUM: Jeg er bare nikker at vi gik over det. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: Vi går over det. 419 00:22:09,626 --> 00:22:13,100 OK, vi virkelig kommer til at gå over det nu, hvad vi siger. 420 00:22:13,100 --> 00:22:14,860 >> PUBLIKUM: Det er for en hentning træ. 421 00:22:14,860 --> 00:22:15,280 >> SPEAKER 1: Ja. 422 00:22:15,280 --> 00:22:16,196 Det er en hentning træ. 423 00:22:16,196 --> 00:22:16,960 Awesome. 424 00:22:16,960 --> 00:22:23,610 Så én ting at bemærke her er, at vi kigger på enkelte tegn 425 00:22:23,610 --> 00:22:24,480 her, ikke? 426 00:22:24,480 --> 00:22:29,710 >> Så før med vores hash-funktion, vi ledte på ord som en helhed, 427 00:22:29,710 --> 00:22:32,270 og nu ser vi mere på de tegn, right? 428 00:22:32,270 --> 00:22:38,380 Så vi har Maxwell herovre og Mendel. 429 00:22:38,380 --> 00:22:47,840 Så dybest set en try-- en måde at tænke om dette er, at hvert niveau her 430 00:22:47,840 --> 00:22:49,000 er en vifte af bogstaver. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Så dette er din root node her, right? 433 00:22:55,790 --> 00:23:01,980 Det har alle de tegn i det alfabet til starten af ​​hvert ord. 434 00:23:01,980 --> 00:23:06,480 >> Og hvad du ønsker at gøre, er siger, OK, vi har nogle M ord. 435 00:23:06,480 --> 00:23:10,590 Vi kommer til at kigge efter Maxwell, så vi gå til M. og M peger på en hel 436 00:23:10,590 --> 00:23:14,800 andet en række, hvor hver ord, så længe der 437 00:23:14,800 --> 00:23:17,044 er et ord, der har en som det andet bogstav, 438 00:23:17,044 --> 00:23:19,460 så længe der er et ord, har B som den anden skrivelse, 439 00:23:19,460 --> 00:23:24,630 det vil have en pointer gå til nogle næste array. 440 00:23:24,630 --> 00:23:29,290 >> Der er sandsynligvis ikke en ord, MP noget, 441 00:23:29,290 --> 00:23:32,980 så på P position i dette array, ville det bare være NULL. 442 00:23:32,980 --> 00:23:38,840 Det ville sige, OK, er der ingen ord der har M efterfulgt af en P, OK? 443 00:23:38,840 --> 00:23:43,100 Så hvis vi tænker over det, hver en af ​​disse mindre ting 444 00:23:43,100 --> 00:23:47,990 er faktisk en af ​​disse store arrays fra A til Z. 445 00:23:47,990 --> 00:23:55,064 Så hvad kunne være en af ​​de ting det er lidt af en ulempe ved en chance? 446 00:23:55,064 --> 00:23:56,500 >> PUBLIKUM: En masse hukommelse. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: Det er et ton af hukommelse, right? 448 00:23:59,940 --> 00:24:08,750 Hver af disse blokke her repræsenterer 26 rum, 26 element array. 449 00:24:08,750 --> 00:24:13,680 Så forsøger få utroligt space tung. 450 00:24:13,680 --> 00:24:17,100 >> Men de er meget hurtige. 451 00:24:17,100 --> 00:24:22,540 Så utroligt hurtigt, men virkelig plads ineffektiv. 452 00:24:22,540 --> 00:24:24,810 Kind of nødt til at regne ud af hvilken en du ønsker. 453 00:24:24,810 --> 00:24:29,470 Disse er virkelig cool for din pset, men de tager en masse hukommelse, 454 00:24:29,470 --> 00:24:30,290 så du handler ud. 455 00:24:30,290 --> 00:24:31,480 Ja? 456 00:24:31,480 --> 00:24:34,300 >> PUBLIKUM: Vil det være muligt at oprette en prøve og derefter 457 00:24:34,300 --> 00:24:37,967 Når du har alle de data i det, at du need-- 458 00:24:37,967 --> 00:24:39,550 Jeg ved ikke, om det ville give mening. 459 00:24:39,550 --> 00:24:42,200 Jeg var at slippe af med alle de NULL tegn, men så 460 00:24:42,200 --> 00:24:42,910 ville du ikke være i stand til at indeksere them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Du har stadig brug for dem. 462 00:24:43,275 --> 00:24:44,854 >> AUDIENCE: - på samme måde hver gang. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Ja. 464 00:24:45,520 --> 00:24:50,460 Du skal bruge NULL tegn til at lade du vide, hvis der er ikke et ord der. 465 00:24:50,460 --> 00:24:52,040 Ben havde du noget, du ønsker? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 Okay, så det vil vi at gå lidt mere 468 00:24:54,581 --> 00:24:58,920 ind i de tekniske detaljer bag prøve og arbejde gennem et eksempel. 469 00:24:58,920 --> 00:25:01,490 >> OK, så dette er den samme ting. 470 00:25:01,490 --> 00:25:06,290 Mens det i en linket liste, vores vigtigste slags of-- hvad er det ord, jeg ønsker? - 471 00:25:06,290 --> 00:25:08,350 ligesom at bygge blok var en node. 472 00:25:08,350 --> 00:25:12,280 I en prøve, har vi også en node, men det er defineret anderledes. 473 00:25:12,280 --> 00:25:17,000 >> Så vi har nogle bool som repræsenterer, om et ord faktisk 474 00:25:17,000 --> 00:25:23,530 findes på dette sted, og derefter vi har nogle matrix her-- eller rettere, 475 00:25:23,530 --> 00:25:27,840 dette er en pointer til en array af 27 tegn. 476 00:25:27,840 --> 00:25:33,339 Og dette er for, i dette tilfælde er 27-- Jeg er sikker på alle du er ligesom, vent, 477 00:25:33,339 --> 00:25:34,880 der er 26 bogstaver i alfabetet. 478 00:25:34,880 --> 00:25:36,010 Hvorfor har vi 27? 479 00:25:36,010 --> 00:25:37,870 >> Så afhængigt af måde du implementerer denne, 480 00:25:37,870 --> 00:25:43,240 dette er fra en pset der tilladt for apostrof. 481 00:25:43,240 --> 00:25:46,010 Så det er derfor den ekstra én. 482 00:25:46,010 --> 00:25:50,500 Du vil også have nogle tilfælde null-terminator 483 00:25:50,500 --> 00:25:53,230 indgår som en af ​​de tegn, som det er tilladt at være, 484 00:25:53,230 --> 00:25:56,120 og det er, hvordan de kontrollerer for se, om det er slutningen af ​​ordet. 485 00:25:56,120 --> 00:26:01,340 Hvis du er interesseret, så tjek Kevins video på study.cs50, 486 00:26:01,340 --> 00:26:04,790 samt Wikipedia har nogle gode ressourcer der. 487 00:26:04,790 --> 00:26:09,000 >> Men vi kommer til at gå igennem lige slags af, hvordan du kan arbejde gennem en prøve 488 00:26:09,000 --> 00:26:11,010 hvis du er givet en. 489 00:26:11,010 --> 00:26:16,230 Så vi har en super enkel en her, at har ordene "bat" og "zoom" i dem. 490 00:26:16,230 --> 00:26:18,920 Og som vi ser op her, denne lidt plads her 491 00:26:18,920 --> 00:26:22,560 repræsenterer vores bool som siger, ja, det er et ord. 492 00:26:22,560 --> 00:26:27,060 Og så har vores arrays af tegn, right? 493 00:26:27,060 --> 00:26:33,480 >> Så vi kommer til at gå igennem finde "bat" i denne prøve. 494 00:26:33,480 --> 00:26:38,340 Så begynder i toppen, right? 495 00:26:38,340 --> 00:26:46,290 Og vi ved, at B svarer til andet indeks, det andet element 496 00:26:46,290 --> 00:26:47,840 i dette array, fordi a og b. 497 00:26:47,840 --> 00:26:51,340 Så omtrent den anden. 498 00:26:51,340 --> 00:26:58,820 >> Og det siger, OK, cool, følge det ind næste array, fordi hvis vi husker, 499 00:26:58,820 --> 00:27:02,160 det er ikke, at hver af disse faktisk indeholder elementet. 500 00:27:02,160 --> 00:27:07,110 Hver enkelt af disse arrays indeholder en pointer, right? 501 00:27:07,110 --> 00:27:10,030 Det er en vigtig forskel at gøre. 502 00:27:10,030 --> 00:27:13,450 >> Jeg ved, at dette kommer til at være-- lande er virkelig svært at komme på den første gang, 503 00:27:13,450 --> 00:27:15,241 så selvom det er den anden eller tredje gang 504 00:27:15,241 --> 00:27:18,370 og det er stadig slags af tilsyneladende vanskeligt, 505 00:27:18,370 --> 00:27:21,199 Jeg lover, hvis du går watch kort igen i morgen, 506 00:27:21,199 --> 00:27:22,740 det vil sandsynligvis gøre en masse mere mening. 507 00:27:22,740 --> 00:27:23,890 Det tager en masse at fordøje. 508 00:27:23,890 --> 00:27:27,800 Jeg har stadig nogle gange er lignende, vent, hvad er en chance? 509 00:27:27,800 --> 00:27:29,080 Hvordan kan jeg bruge dette? 510 00:27:29,080 --> 00:27:33,880 >> Så vi har b i denne sag, som er vores andet indeks. 511 00:27:33,880 --> 00:27:40,240 Hvis vi havde, siger, c eller d eller ethvert andet brev, 512 00:27:40,240 --> 00:27:45,810 vi har brug for at kortlægge det tilbage til indekset vores array, der svarer til. 513 00:27:45,810 --> 00:27:56,930 Så vi vil tage ligesom rchar og vi bare trække off en at kortlægge det ind fra 0 til 25. 514 00:27:56,930 --> 00:27:58,728 Alle godt, hvordan vi kortlægge vores karakterer? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Så vi går til den anden, og vi se, at ja, det er ikke til NULL. 517 00:28:05,980 --> 00:28:07,780 Vi kan gå videre til den næste array. 518 00:28:07,780 --> 00:28:12,300 Så vi går videre til den næste række her. 519 00:28:12,300 --> 00:28:15,500 >> Og vi siger, OK, nu vi nødt til at se, hvis en er her. 520 00:28:15,500 --> 00:28:18,590 Er en null eller gør det faktisk bevæge sig fremad? 521 00:28:18,590 --> 00:28:21,880 Så en egentlig bevæger sig sende i dette array. 522 00:28:21,880 --> 00:28:24,570 Og vi siger, OK, t er vores sidste bogstav. 523 00:28:24,570 --> 00:28:27,580 Så går vi til t ved indekset. 524 00:28:27,580 --> 00:28:30,120 Og så bevæger vi os fremad fordi der er en anden. 525 00:28:30,120 --> 00:28:38,340 Og denne ene siger dybest set, at ja, det siger, at der er et ord her-- 526 00:28:38,340 --> 00:28:41,750 at hvis du følger dette sti, har du ankom 527 00:28:41,750 --> 00:28:43,210 på et ord, som vi ved er "bat". 528 00:28:43,210 --> 00:28:43,800 Ja? 529 00:28:43,800 --> 00:28:46,770 >> PUBLIKUM: Er det standard at have den som indeks 0 og derefter har en slags 1 530 00:28:46,770 --> 00:28:47,660 eller at have i slutningen? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: Nej. 532 00:28:48,243 --> 00:28:55,360 Så hvis vi ser tilbage på vores erklæring her, det er en bool, 533 00:28:55,360 --> 00:28:59,490 så det er eget element i node. 534 00:28:59,490 --> 00:29:03,331 Så det er ikke en del af array'et. 535 00:29:03,331 --> 00:29:03,830 Cool. 536 00:29:03,830 --> 00:29:08,370 Så når vi er færdig med vores ord, og vi er på dette array, hvad vi ønsker at gøre 537 00:29:08,370 --> 00:29:12,807 er at gøre en check, er dette et ord. 538 00:29:12,807 --> 00:29:14,390 Og i dette tilfælde, ville det vende tilbage ja. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Så på dette notat, vi ved, at "zoo" - vi kender som mennesker, at "zoo" er et ord, 541 00:29:24,090 --> 00:29:24,820 højre? 542 00:29:24,820 --> 00:29:28,990 Men prøv her ville sige, nej, det er ikke. 543 00:29:28,990 --> 00:29:33,980 Og det vil sige, at fordi vi ikke har udpeget det som et ord her. 544 00:29:33,980 --> 00:29:40,440 Selvom vi kan krydse igennem til dette array, 545 00:29:40,440 --> 00:29:43,890 denne prøve vil sige, at nej, zoo er ikke i din ordbog 546 00:29:43,890 --> 00:29:47,070 fordi vi ikke har udpeget det som sådan. 547 00:29:47,070 --> 00:29:52,870 >> Så en måde at gøre at-- Åh, undskyld, denne ene. 548 00:29:52,870 --> 00:29:59,450 Så i dette tilfælde, "zoo" er ikke et ord, men det er i vores prøve. 549 00:29:59,450 --> 00:30:05,690 Men i denne ene, siger vi ønsker det indføre ordet "bad", hvad der sker 550 00:30:05,690 --> 00:30:08,260 er vi følge through-- b, a, t. 551 00:30:08,260 --> 00:30:11,820 Vi er i dette array, og vi gå for at søge efter h. 552 00:30:11,820 --> 00:30:15,220 >> I dette tilfælde, hvor vi se på markøren på h, 553 00:30:15,220 --> 00:30:17,890 det peger på NULL, OK? 554 00:30:17,890 --> 00:30:20,780 Så medmindre det er udtrykkeligt peger på et andet array, 555 00:30:20,780 --> 00:30:25,000 du antage, at alle de pejlemærker i denne række peger til null. 556 00:30:25,000 --> 00:30:28,270 Så i dette tilfælde er h peger til null så vi kan ikke gøre noget, 557 00:30:28,270 --> 00:30:31,540 så det ville også vende tilbage falsk, "bad" ikke er her. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Så nu er vi faktisk vil gå igennem 560 00:30:35,810 --> 00:30:39,790 hvordan ville vi faktisk sige at "zoo" er i vores prøve. 561 00:30:39,790 --> 00:30:42,920 Hvordan kan vi indsætter "zoo" ind i vores chance? 562 00:30:42,920 --> 00:30:47,810 Så på samme måde, som vi startede med vores linkede liste, vi starter ved roden. 563 00:30:47,810 --> 00:30:50,600 Når du er i tvivl, skal du starte på roden af ​​disse ting. 564 00:30:50,600 --> 00:30:53,330 >> Og vi vil sige, OK, z. 565 00:30:53,330 --> 00:30:55,650 z findes i dette, og det gør det. 566 00:30:55,650 --> 00:30:58,370 Så du går videre til din næste array, OK? 567 00:30:58,370 --> 00:31:01,482 Og så på den næste, vi siger, OK, går o eksisterer? 568 00:31:01,482 --> 00:31:03,000 Det gør det. 569 00:31:03,000 --> 00:31:04,330 Dette igen. 570 00:31:04,330 --> 00:31:08,670 >> Og så på vores næste, vi har sagt, OK, der allerede eksisterer "zoo" her. 571 00:31:08,670 --> 00:31:12,440 Alt, hvad vi behøver at gøre, er at sætte dette lig til sand, at der er et ord der. 572 00:31:12,440 --> 00:31:15,260 Hvis du havde fulgt alt op til før dette punkt, 573 00:31:15,260 --> 00:31:17,030 Det er et ord, så bare sætte den lig med sådanne. 574 00:31:17,030 --> 00:31:17,530 Ja? 575 00:31:17,530 --> 00:31:22,550 >> PUBLIKUM: Så gør det betyder, at "ba" er et ord også? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: Nej. 577 00:31:24,120 --> 00:31:28,870 Så i dette tilfælde, "ba" vi ville få her, ville vi sige, er det et ord, 578 00:31:28,870 --> 00:31:31,590 og det ville stadig være nej. 579 00:31:31,590 --> 00:31:32,822 OK? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> PUBLIKUM: Så når du er det en ord og du siger ja, så er det 582 00:31:36,360 --> 00:31:38,380 vil indeholde for at gå til m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: Så det har at gøre med-- du lægger det i. 584 00:31:42,260 --> 00:31:43,640 Du siger "zoo" er et ord. 585 00:31:43,640 --> 00:31:47,020 Når du går til check-- lignende, siger du ønsker at sige, 586 00:31:47,020 --> 00:31:49,400 betyder "zoo" eksistere i denne ordbog? 587 00:31:49,400 --> 00:31:54,200 Du kun vil søge efter "zoo" og derefter kontrollere, om det er et ord. 588 00:31:54,200 --> 00:31:57,291 Du aldrig kommer til at flytte igennem til m, fordi det er ikke 589 00:31:57,291 --> 00:31:58,290 hvad du leder efter. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Så hvis vi faktisk ønskede at tilføj "bad" i denne prøve, 592 00:32:08,070 --> 00:32:11,390 vi ville gøre det samme som vi gjorde med "zoo" 593 00:32:11,390 --> 00:32:15,380 bortset fra at vi ville se, at når vi prøv og få til h, betyder det ikke eksisterer. 594 00:32:15,380 --> 00:32:20,090 Så du kan tænke på dette som et forsøg at tilføje en ny knude i en linket liste, 595 00:32:20,090 --> 00:32:27,210 så ville vi nødt til at tilføje en anden en af ​​disse arrays, som så. 596 00:32:27,210 --> 00:32:35,670 Og så hvad vi gør, er vi bare indstille h element i denne matrix peger på dette. 597 00:32:35,670 --> 00:32:39,430 >> Og så hvad ville vi ønsker at gøre her? 598 00:32:39,430 --> 00:32:43,110 Tilføj lig med sand fordi det er et ord. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Cool. 601 00:32:48,150 --> 00:32:48,700 Jeg kender. 602 00:32:48,700 --> 00:32:51,170 Lande er ikke det mest spændende. 603 00:32:51,170 --> 00:32:54,250 Tro mig, jeg kender. 604 00:32:54,250 --> 00:32:58,040 >> Så én ting at indse med forsøg, Jeg sagde, de er meget effektive. 605 00:32:58,040 --> 00:33:00,080 Så vi har set de tage et ton af plads. 606 00:33:00,080 --> 00:33:01,370 De er slags forvirrende. 607 00:33:01,370 --> 00:33:03,367 Så hvorfor skulle vi nogensinde bruge disse? 608 00:33:03,367 --> 00:33:05,450 Vi bruger disse, fordi de er utrolig effektiv. 609 00:33:05,450 --> 00:33:08,130 >> Så hvis du nogensinde søger et ord op, er du kun 610 00:33:08,130 --> 00:33:10,450 afgrænset af længden af ​​ordet. 611 00:33:10,450 --> 00:33:15,210 Så hvis du leder efter en ord, der er af længde fem, 612 00:33:15,210 --> 00:33:20,940 du kun nogensinde nødt til at gøre på de fleste fem sammenligninger, OK? 613 00:33:20,940 --> 00:33:25,780 Så det gør det dybest set en konstant. 614 00:33:25,780 --> 00:33:29,150 Ligesom indsættelse og opslag er stort set konstant tid. 615 00:33:29,150 --> 00:33:33,750 >> Så hvis du nogensinde kan få noget i konstant tid, 616 00:33:33,750 --> 00:33:35,150 det er så godt, som det får. 617 00:33:35,150 --> 00:33:37,990 Du kan ikke få bedre end konstant tid til disse ting. 618 00:33:37,990 --> 00:33:43,150 Så er en af ​​de store plusser af prøver. 619 00:33:43,150 --> 00:33:46,780 >> Men det er en masse plads. 620 00:33:46,780 --> 00:33:50,380 Så du slags nødt til at beslutte hvad er mere vigtigt for dig. 621 00:33:50,380 --> 00:33:54,700 Og på nutidens computere, den plads, som en prøve kan tage op 622 00:33:54,700 --> 00:33:57,740 måske ikke påvirker dig så meget, men måske 623 00:33:57,740 --> 00:34:01,350 du har at gøre med noget der har langt, langt flere ting, 624 00:34:01,350 --> 00:34:02,810 og en prøve er bare ikke rimeligt. 625 00:34:02,810 --> 00:34:03,000 Ja? 626 00:34:03,000 --> 00:34:05,610 >> PUBLIKUM: Vent, så du har 26 bogstaver i hver enkelt? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Ja, du har 26. 629 00:34:08,570 --> 00:34:16,984 Du har nogle er ord markør og derefter du har 26 pejlemærker i hver enkelt. 630 00:34:16,984 --> 00:34:17,775 Og de er point-- 631 00:34:17,775 --> 00:34:20,280 >> PUBLIKUM: Og hver 26, har de hver især har 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Ja. 633 00:34:21,500 --> 00:34:27,460 Og det er derfor, som du kan se, udvider ganske hurtigt. 634 00:34:27,460 --> 00:34:28,130 Ok. 635 00:34:28,130 --> 00:34:32,524 Så vi kommer til at komme ind i træer, som Jeg har lyst er lettere og vil sandsynligvis 636 00:34:32,524 --> 00:34:36,150 være en dejlig lille udsættelse fra forsøg der. 637 00:34:36,150 --> 00:34:39,620 Så forhåbentlig de fleste af jer har set et træ før. 638 00:34:39,620 --> 00:34:41,820 Ikke ligesom den smukke dem udenfor, som jeg 639 00:34:41,820 --> 00:34:44,340 ved ikke, om nogen gik udenfor for nylig. 640 00:34:44,340 --> 00:34:49,230 Jeg gik apple plukke denne weekend, og Åh min gosh, det var smukt. 641 00:34:49,230 --> 00:34:52,250 Jeg vidste ikke blade kunne se, at stort. 642 00:34:52,250 --> 00:34:53,610 >> Så dette er blot et træ, right? 643 00:34:53,610 --> 00:34:56,790 Det er blot nogle node, og det peger på en masse andre noder. 644 00:34:56,790 --> 00:34:59,570 Som du kan se her, det er slags et tilbagevendende tema. 645 00:34:59,570 --> 00:35:03,720 Nodes, der peger på noder er slags essensen af ​​mange datastrukturer. 646 00:35:03,720 --> 00:35:06,670 Det bare afhænger af, hvordan vi få dem pege på hinanden 647 00:35:06,670 --> 00:35:08,600 og hvordan vi krydse gennem dem, og hvordan vi 648 00:35:08,600 --> 00:35:14,500 indsætte ting, der bestemmer deres forskellige karakteristika. 649 00:35:14,500 --> 00:35:17,600 >> Så blot nogle terminologi, som jeg har brugt før. 650 00:35:17,600 --> 00:35:20,010 Så rod er, hvad der er helt i top. 651 00:35:20,010 --> 00:35:21,200 det er, hvor vi altid starte. 652 00:35:21,200 --> 00:35:23,610 Du kan tænke på det som også hovedet. 653 00:35:23,610 --> 00:35:28,750 Men for træer, er vi tilbøjelige til at henviser til det som roden. 654 00:35:28,750 --> 00:35:32,820 >> Noget ved bunden her-- på den meget, meget bottom-- 655 00:35:32,820 --> 00:35:34,500 betragtes blade. 656 00:35:34,500 --> 00:35:37,210 Så det går sammen med den hele træet ting, right? 657 00:35:37,210 --> 00:35:39,860 Blade er på kanten af ​​dit træ. 658 00:35:39,860 --> 00:35:45,820 >> Og så har vi også et par vilkår for at tale om knuder i relation 659 00:35:45,820 --> 00:35:46,680 til hinanden. 660 00:35:46,680 --> 00:35:49,700 Så vi har forælder, børn og søskende. 661 00:35:49,700 --> 00:35:56,260 Så i dette tilfælde, 3 er forælder af 5, 6 og 7. 662 00:35:56,260 --> 00:36:00,370 Så forældrene er, hvad der er ét trin ovenfor hvad du er 663 00:36:00,370 --> 00:36:02,940 henvise til, så bare ligesom et stamtræ. 664 00:36:02,940 --> 00:36:07,090 Forhåbentlig, dette er alle lidt lidt mere intuitiv end forsøger. 665 00:36:07,090 --> 00:36:10,970 >> Søskende er nogen, der har den samme forælder, right? 666 00:36:10,970 --> 00:36:13,470 De er på samme niveau her. 667 00:36:13,470 --> 00:36:16,960 Og så, som jeg var siger, børn er bare 668 00:36:16,960 --> 00:36:22,630 hvad er et trin under den pågældende knude, OK? 669 00:36:22,630 --> 00:36:23,470 Cool. 670 00:36:23,470 --> 00:36:25,610 Så et binært træ. 671 00:36:25,610 --> 00:36:31,450 Kan nogen gætte på en af karakteristika binært træ? 672 00:36:31,450 --> 00:36:32,770 >> PUBLIKUM: Max to blade. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Right. 674 00:36:33,478 --> 00:36:34,640 Så max to blade. 675 00:36:34,640 --> 00:36:39,730 Så i dette en før, vi havde denne ene der havde tre, men i et binært træ, 676 00:36:39,730 --> 00:36:45,000 du har en max to børn per forælder, right? 677 00:36:45,000 --> 00:36:46,970 Der er en anden interessant egenskab. 678 00:36:46,970 --> 00:36:51,550 Er der nogen der kender det? 679 00:36:51,550 --> 00:36:52,620 Binært træ. 680 00:36:52,620 --> 00:37:00,350 >> Så et binært træ vil have alt på til-- denne ene ikke er sorted-- 681 00:37:00,350 --> 00:37:05,320 men i en sorteret binært træ, alt på højre 682 00:37:05,320 --> 00:37:08,530 er større end den forælder, og alt til venstre 683 00:37:08,530 --> 00:37:10,035 er mindre end forælder. 684 00:37:10,035 --> 00:37:15,690 Og der har været en quiz spørgsmål før, så godt at vide. 685 00:37:15,690 --> 00:37:19,500 Så den måde, vi definerer det, igen, har vi en anden node. 686 00:37:19,500 --> 00:37:21,880 Dette ligner meget hvad? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Dobbelt 689 00:37:28,836 --> 00:37:29,320 >> Publikum: Linked lister 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: Et dobbelt linket liste, right? 691 00:37:31,100 --> 00:37:33,690 Så hvis vi erstatte dette med forrige og næste, 692 00:37:33,690 --> 00:37:35,670 dette ville være en dobbelt linket liste. 693 00:37:35,670 --> 00:37:40,125 Men i dette tilfælde, vi faktisk har venstre og højre og det er det. 694 00:37:40,125 --> 00:37:41,500 Ellers er det nøjagtig det samme. 695 00:37:41,500 --> 00:37:43,374 Vi har stadig element du leder efter, 696 00:37:43,374 --> 00:37:45,988 og du skal blot to pointers går til, hvad der bliver det næste. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Yeah, så binær søgning træ. 699 00:37:51,870 --> 00:37:57,665 Hvis vi opdager, alt på lige her er større than-- 700 00:37:57,665 --> 00:37:59,850 eller alt straks til højre her 701 00:37:59,850 --> 00:38:02,840 er større end, alt her er mindre end. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Så hvis vi skulle til at søge gennem det skal se meget tæt på binær søgning 704 00:38:14,000 --> 00:38:14,910 her, ikke? 705 00:38:14,910 --> 00:38:17,640 Undtagen i stedet for at kigge til halv array, 706 00:38:17,640 --> 00:38:21,720 vi er bare at kigge på enten den venstre side eller højre side af træet. 707 00:38:21,720 --> 00:38:24,850 Så det bliver lidt nemmere, tror jeg. 708 00:38:24,850 --> 00:38:29,300 >> Så hvis din rod er NULL, selvfølgelig er det bare falsk. 709 00:38:29,300 --> 00:38:33,470 Og hvis det er der, det er naturligvis sandt. 710 00:38:33,470 --> 00:38:35,320 Hvis det er mindre end, søger vi til venstre. 711 00:38:35,320 --> 00:38:37,070 Hvis det er større end, vi søger til højre. 712 00:38:37,070 --> 00:38:39,890 Det er præcis ligesom binær søgning, bare en anden datastruktur 713 00:38:39,890 --> 00:38:40,600 at vi bruger. 714 00:38:40,600 --> 00:38:42,790 I stedet for en matrix, det er bare et binært træ. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, stakke. 717 00:38:48,090 --> 00:38:51,550 Og også, det ligner vi har måske en lille smule tid. 718 00:38:51,550 --> 00:38:54,460 Hvis vi gør det, er jeg glad for at gå over nogen af ​​dette igen. 719 00:38:54,460 --> 00:38:56,856 OK, så stakke. 720 00:38:56,856 --> 00:39:02,695 Er der nogen der kan huske hvad stacks-- eventuelle karakteristika for en stak? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, så de fleste af os, tror jeg, spise i spisesalen halls-- 723 00:39:10,400 --> 00:39:13,100 så meget, som vi ikke kan lide at. 724 00:39:13,100 --> 00:39:16,900 Men det er klart, kan du tænke på en stak bogstavelig talt lige som en stabel af bakker 725 00:39:16,900 --> 00:39:18,460 eller en stak ting. 726 00:39:18,460 --> 00:39:21,820 Og hvad der er vigtigt at indse, er, at det er 727 00:39:21,820 --> 00:39:26,850 something-- den karakteristiske at vi kalder det by-- er LIFO. 728 00:39:26,850 --> 00:39:28,450 Er der nogen vide, hvad det står for? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> PUBLIKUM: Sidste ind, først ud. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: Right, sidst ind, først ud. 732 00:39:32,250 --> 00:39:36,585 Så hvis vi ved, hvis vi stable ting op, at det nemmeste grab off-- 733 00:39:36,585 --> 00:39:39,570 og måske det eneste, vi kan få fat i fra, hvis vores stack er stor enough-- 734 00:39:39,570 --> 00:39:40,850 er, at top element. 735 00:39:40,850 --> 00:39:43,460 Så uanset var sat på last-- som vi ser her, 736 00:39:43,460 --> 00:39:46,370 hvad blev skubbet på de fleste recently-- er 737 00:39:46,370 --> 00:39:51,160 vil være den første ting, som vi pop off, OK? 738 00:39:51,160 --> 00:39:56,324 >> Så hvad vi har her er andet typedef struct. 739 00:39:56,324 --> 00:39:58,740 Dette er egentlig bare gerne have en lynkursus i datastruktur, 740 00:39:58,740 --> 00:40:01,650 så der er en masse smidt på jer. 741 00:40:01,650 --> 00:40:02,540 Jeg kender. 742 00:40:02,540 --> 00:40:04,970 Så endnu en struct. 743 00:40:04,970 --> 00:40:06,740 Yay for strukturer. 744 00:40:06,740 --> 00:40:16,660 >> Og i dette tilfælde, det er nogle pointer til et array, der har en vis kapacitet. 745 00:40:16,660 --> 00:40:20,830 Så det repræsenterer vores stack her, ligesom vores faktiske matrix 746 00:40:20,830 --> 00:40:22,520 at der holder vores elementer. 747 00:40:22,520 --> 00:40:24,850 Og så har vi her nogle størrelse. 748 00:40:24,850 --> 00:40:31,170 >> Og typisk, du vil beholde styr på, hvor stor din stack er 749 00:40:31,170 --> 00:40:36,180 fordi hvad det kommer til at tillade du skal gøre er, hvis du kender størrelsen, 750 00:40:36,180 --> 00:40:39,170 det giver dig mulighed for at sige, OK, er jeg ved kapacitet? 751 00:40:39,170 --> 00:40:40,570 Kan jeg tilføje noget mere? 752 00:40:40,570 --> 00:40:44,650 Og det fortæller dig også hvor toppen af ​​din stack 753 00:40:44,650 --> 00:40:48,180 er så du ved hvad du kan faktisk tage af. 754 00:40:48,180 --> 00:40:51,760 Og der er faktisk kommer til at være lidt mere klar her. 755 00:40:51,760 --> 00:40:57,350 >> Så for skub, en ting, hvis du nogensinde at gennemføre skubbe, 756 00:40:57,350 --> 00:41:01,330 da jeg var bare at sige, din stakken har en begrænset størrelse, right? 757 00:41:01,330 --> 00:41:03,990 Vores vifte havde nogle kapacitet. 758 00:41:03,990 --> 00:41:04,910 Det er et array. 759 00:41:04,910 --> 00:41:08,930 Det er en fast størrelse, så vi er nødt til sørge for, at vi ikke putter mere 760 00:41:08,930 --> 00:41:11,950 ind i vores matrix, end vi faktisk har plads til. 761 00:41:11,950 --> 00:41:16,900 >> Så når du opretter en push funktion, første ting du skal gøre er at sige, OK, 762 00:41:16,900 --> 00:41:18,570 har jeg plads i min stak? 763 00:41:18,570 --> 00:41:23,330 Fordi hvis jeg ikke gør det, undskyld, Jeg kan ikke gemme dit element. 764 00:41:23,330 --> 00:41:28,980 Hvis jeg gør, så du ønsker at gemme det på toppen af ​​stakken, right? 765 00:41:28,980 --> 00:41:31,325 >> Og det er derfor, vi har at holde styr på vores størrelse. 766 00:41:31,325 --> 00:41:35,290 Hvis vi ikke holde styr på vores størrelse, vi ved ikke, hvor at sætte det. 767 00:41:35,290 --> 00:41:39,035 Vi ved ikke, hvor mange ting er i vores matrix allerede. 768 00:41:39,035 --> 00:41:41,410 Ligesom der er naturligvis måder at måske du kunne gøre det. 769 00:41:41,410 --> 00:41:44,610 Du kunne initialisere alt NULL og derefter søge efter den seneste NULL, 770 00:41:44,610 --> 00:41:47,950 men en meget lettere ting er lige at sige, OK, holde styr på størrelse. 771 00:41:47,950 --> 00:41:51,840 Ligesom jeg ved, jeg har fire elementer i mit array, så den næste ting 772 00:41:51,840 --> 00:41:55,930 at vi lægger på, er vi skal opbevares ved indeks 4. 773 00:41:55,930 --> 00:42:00,940 Og så, selvfølgelig, betyder det, at du med held har skubbet noget 774 00:42:00,940 --> 00:42:03,320 på din stack, du ønsker at øge størrelsen 775 00:42:03,320 --> 00:42:08,880 så du ved, hvor du er så at du kan presse flere ting på. 776 00:42:08,880 --> 00:42:12,730 >> Så hvis vi forsøger at pop noget fra stakken, 777 00:42:12,730 --> 00:42:16,072 hvad der kunne være det første, at vi ønsker at kontrollere for? 778 00:42:16,072 --> 00:42:18,030 Du forsøger at tage noget fra din stak. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Er du sikker på der er noget i din stak? 781 00:42:24,781 --> 00:42:25,280 Nej. 782 00:42:25,280 --> 00:42:26,894 Så hvad kunne vi ønsker at kontrollere? 783 00:42:26,894 --> 00:42:27,810 >> PUBLIKUM: [uhørligt]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Kontroller, om størrelsen? 785 00:42:29,880 --> 00:42:31,840 Størrelse. 786 00:42:31,840 --> 00:42:38,520 Så vi ønsker at kontrollere at se, om vores størrelse er større end 0, OK? 787 00:42:38,520 --> 00:42:44,970 Og hvis det er, så ønsker vi at falde vores størrelse med 0 og returnere det. 788 00:42:44,970 --> 00:42:45,840 Hvorfor? 789 00:42:45,840 --> 00:42:49,950 >> I den første var vi skubbe, vi pressede det 790 00:42:49,950 --> 00:42:52,460 på størrelse og opdateres derefter størrelse. 791 00:42:52,460 --> 00:42:57,850 I dette tilfælde, vi dekrementering størrelse og derefter at tage det ud, plukning det 792 00:42:57,850 --> 00:42:58,952 fra vores array. 793 00:42:58,952 --> 00:42:59,826 Hvorfor kunne vi gøre det? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Så hvis jeg har én ting på min stak, hvad der ville være min størrelse på det tidspunkt? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> Og hvor er element 1 opbevares? 798 00:43:15,180 --> 00:43:17,621 På hvilket indeks? 799 00:43:17,621 --> 00:43:18,120 PUBLIKUM: 0. 800 00:43:18,120 --> 00:43:19,060 SPEAKER 1: 0. 801 00:43:19,060 --> 00:43:22,800 Så i dette tilfælde, vi altid nødt til at gøre sure-- 802 00:43:22,800 --> 00:43:27,630 stedet for at returnere størrelse minus 1, fordi vi 803 00:43:27,630 --> 00:43:31,730 ved, at vores element er skal oplagres på en mindre 804 00:43:31,730 --> 00:43:34,705 uanset vores størrelse er, at dette bare tager sig af det. 805 00:43:34,705 --> 00:43:36,080 Det er en lidt mere elegant måde. 806 00:43:36,080 --> 00:43:41,220 Og vi bare formindske vores størrelse og derefter vende tilbage størrelse. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> PUBLIKUM: Jeg gætter bare i almindelighed, hvorfor skulle denne datastruktur 809 00:43:45,300 --> 00:43:47,800 være gavnligt? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: Det afhænger af din kontekst. 811 00:43:50,660 --> 00:43:57,420 Så for nogle af de teorier, hvis du arbejder med-- OK, 812 00:43:57,420 --> 00:44:02,750 Lad mig se, om der er en gavnlig én som er gavnlig for mere end uden 813 00:44:02,750 --> 00:44:05,420 CS. 814 00:44:05,420 --> 00:44:15,780 Med stakke, når som helst du har brug for at holde styr på noget, 815 00:44:15,780 --> 00:44:20,456 er den mest nylig tilføjet er, når du vil ønsker at bruge en stak. 816 00:44:20,456 --> 00:44:24,770 >> Og jeg kan ikke tænke på en god eksempel på det lige nu. 817 00:44:24,770 --> 00:44:29,955 Men når den seneste ting er vigtigst for dig, 818 00:44:29,955 --> 00:44:31,705 det er, når en stak vil være nyttig. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Jeg forsøger at tænke, hvis der er et godt for dette. 821 00:44:39,330 --> 00:44:43,720 Hvis jeg tænker på et godt eksempel i den næste 20 minutter vil jeg helt sikkert fortælle dig. 822 00:44:43,720 --> 00:44:49,455 >> Men samlet, hvis der er noget, ligesom jeg sagde de fleste, hvor seneste 823 00:44:49,455 --> 00:44:52,470 er vigtigst, der er hvor en stabel kommer i spil. 824 00:44:52,470 --> 00:44:58,860 Ud fra følgende betragtninger køer er slags det modsatte. 825 00:44:58,860 --> 00:44:59,870 Og alle de små hunde. 826 00:44:59,870 --> 00:45:00,890 Er dette ikke det store, right? 827 00:45:00,890 --> 00:45:03,299 Jeg føler, at jeg skulle bare have en kanin video 828 00:45:03,299 --> 00:45:05,090 lige i midten af sektion for jer 829 00:45:05,090 --> 00:45:08,870 fordi det er en intens sektion. 830 00:45:08,870 --> 00:45:10,480 >> Så en kø. 831 00:45:10,480 --> 00:45:12,710 Dybest set en kø er ligesom en linje. 832 00:45:12,710 --> 00:45:15,780 Du fyre jeg er sikker på, brug denne hverdag, ligesom i vore spisesale. 833 00:45:15,780 --> 00:45:18,160 Så vi nødt til at gå i og få vores bakker, jeg er 834 00:45:18,160 --> 00:45:21,260 sikker på at du er nødt til at vente i linje stryge eller få din mad. 835 00:45:21,260 --> 00:45:24,650 >> Så forskellen her er, at dette er FIFO. 836 00:45:24,650 --> 00:45:30,090 Så hvis LIFO sidst var i første ud, FIFO er først ind, først ud. 837 00:45:30,090 --> 00:45:33,400 Så det er her, hvad du lægger på første er din vigtigste. 838 00:45:33,400 --> 00:45:35,540 Så hvis du ventede i en line-- kan du 839 00:45:35,540 --> 00:45:39,130 tænk hvis du gik til gå få den nye iPhone 840 00:45:39,130 --> 00:45:42,800 og det var en stak, hvor sidste person på linje fik det første, 841 00:45:42,800 --> 00:45:44,160 folk ville dræbe hinanden. 842 00:45:44,160 --> 00:45:49,800 >> Så FIFO, vi er alle meget velkendte med i den virkelige verden her, 843 00:45:49,800 --> 00:45:54,930 og det hele har at gøre med faktisk slags genskabe hele denne linje 844 00:45:54,930 --> 00:45:56,900 og kø struktur. 845 00:45:56,900 --> 00:46:02,390 Så der med stakken, vi har push og pop. 846 00:46:02,390 --> 00:46:06,440 Med en kø, har vi enqueue og dequeue. 847 00:46:06,440 --> 00:46:10,910 Så enqueue dybest set betyder sætte det på ryggen, 848 00:46:10,910 --> 00:46:13,680 og dequeue midler tage off forfra. 849 00:46:13,680 --> 00:46:18,680 Så vores datastruktur er en lidt mere kompliceret. 850 00:46:18,680 --> 00:46:21,060 Vi har en anden ting at holde styr på. 851 00:46:21,060 --> 00:46:25,950 >> Så uden hoved, dette er netop en stak, right? 852 00:46:25,950 --> 00:46:27,900 Dette er den samme struktur som en stak. 853 00:46:27,900 --> 00:46:32,480 Det eneste anderledes nu er vi har denne hovedet, som hvad tror du 854 00:46:32,480 --> 00:46:34,272 kommer til at holde styr på? 855 00:46:34,272 --> 00:46:35,510 >> PUBLIKUM: Den første. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Right, den første ting, vi sætter i. 857 00:46:38,685 --> 00:46:41,130 Lederen af ​​vores kø. 858 00:46:41,130 --> 00:46:42,240 Hvem er først i køen. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Okay, så hvis vi gør enqueue. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Igen med nogen af disse datastrukturer, 863 00:46:55,920 --> 00:46:59,760 da vi har at gøre med et array, vi nødt til at tjekke, om vi har plads. 864 00:46:59,760 --> 00:47:03,290 >> Det er lidt ligesom mig fortælle du fyre, hvis du åbner en fil, 865 00:47:03,290 --> 00:47:04,760 du nødt til at tjekke for null. 866 00:47:04,760 --> 00:47:08,330 Med nogen af ​​disse stakke og køer, du har brug for 867 00:47:08,330 --> 00:47:13,420 at se, om der er plads, fordi vi er beskæftiger sig med en fast størrelse array, 868 00:47:13,420 --> 00:47:16,030 som vi ser her-- 0, 1 alt op til 5. 869 00:47:16,030 --> 00:47:20,690 Så hvad vi gør i dette tilfælde er kontrol at se, om vi stadig har plads. 870 00:47:20,690 --> 00:47:23,110 Er vores størrelse mindre end kapaciteten? 871 00:47:23,110 --> 00:47:28,480 >> Hvis det er tilfældet, er vi nødt til at gemme det på halen og vi opdaterer vores størrelse. 872 00:47:28,480 --> 00:47:30,250 Så hvad kunne halen være i dette tilfælde? 873 00:47:30,250 --> 00:47:32,360 Det er ikke udtrykkeligt skrevet ud. 874 00:47:32,360 --> 00:47:33,380 Hvordan ville vi gemme det? 875 00:47:33,380 --> 00:47:34,928 Hvad ville halen være? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Så lad os gå gennem dette eksempel. 878 00:47:40,190 --> 00:47:44,590 Så dette er en vifte af størrelse 6, right? 879 00:47:44,590 --> 00:47:49,220 Og vi har lige nu, vores størrelse er 5. 880 00:47:49,220 --> 00:47:55,240 Og når vi sætter det i, går det at gå ind i femte indeks, right? 881 00:47:55,240 --> 00:47:57,030 Så opbevares ved halen. 882 00:47:57,030 --> 00:48:05,600 >> En anden måde at skrive hale vil blot være vores udvalg på indeks af størrelse, right? 883 00:48:05,600 --> 00:48:07,560 Dette er størrelse 5. 884 00:48:07,560 --> 00:48:11,490 Næste ting kommer til at gå ind i 5. 885 00:48:11,490 --> 00:48:12,296 Cool? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Det bliver lidt mere kompliceret når vi begynder at rode med hovedet. 888 00:48:16,350 --> 00:48:17,060 Ja? 889 00:48:17,060 --> 00:48:20,090 >> PUBLIKUM: Betyder det, at vi ville have erklæret en array, 890 00:48:20,090 --> 00:48:23,880 var fem elementer lang og så vi tilføjer på det? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: Nej. 892 00:48:24,730 --> 00:48:27,560 Så i dette tilfælde, er dette en stak. 893 00:48:27,560 --> 00:48:31,760 Dette ville blive erklæret som en vifte af størrelse 6. 894 00:48:31,760 --> 00:48:37,120 Og i dette tilfælde, vi bare har én plads til venstre. 895 00:48:37,120 --> 00:48:42,720 >> OK, så én ting er i denne tilfælde, hvis vores hoved er på 0, 896 00:48:42,720 --> 00:48:45,270 så vi bare kan tilføje den på størrelse. 897 00:48:45,270 --> 00:48:51,020 Men det bliver lidt tricky fordi faktisk, de 898 00:48:51,020 --> 00:48:52,840 ikke har en slide for dette, så jeg har tænkt mig 899 00:48:52,840 --> 00:48:56,670 at tegne en, fordi det ikke er helt så enkel, når du 900 00:48:56,670 --> 00:48:59,230 begynde at slippe af med ting. 901 00:48:59,230 --> 00:49:03,920 Så der med en stak du kun nogensinde har 902 00:49:03,920 --> 00:49:08,920 at bekymre sig om, hvad størrelse er når du tilføjer noget på, 903 00:49:08,920 --> 00:49:15,710 med en kø, du også nødt til at gøre sikker på, at dit hoved er tegnede sig for, 904 00:49:15,710 --> 00:49:20,760 fordi en cool ting om køer er, at hvis du ikke er på kapacitet, 905 00:49:20,760 --> 00:49:23,040 du kan faktisk gøre det wrap around. 906 00:49:23,040 --> 00:49:28,810 >> OK, så man thing-- åh, dette er forfærdeligt kridt. 907 00:49:28,810 --> 00:49:31,815 Én ting at overveje, er tilfældet. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Vi vil bare gøre fem. 910 00:49:37,140 --> 00:49:41,810 OK, så vi kommer til at siger hovedet er her. 911 00:49:41,810 --> 00:49:46,140 Dette er 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> Hovedet er der, og skal du have ting i dem. 913 00:49:54,210 --> 00:49:58,340 Og vi ønsker at tilføje noget i, right? 914 00:49:58,340 --> 00:50:01,170 Så de ting, vi er nødt til at ved er, at hovedet er altid 915 00:50:01,170 --> 00:50:05,620 kommer til at flytte denne måde og derefter løkke tilbage omkring, OK? 916 00:50:05,620 --> 00:50:10,190 >> Så denne kø har et areal, right? 917 00:50:10,190 --> 00:50:13,950 Det har plads i begyndelsen, form for det modsatte af dette. 918 00:50:13,950 --> 00:50:17,920 Så hvad vi skal gøre, er vi nødt til at beregne halen. 919 00:50:17,920 --> 00:50:20,530 Hvis du ved, at din hoved har ikke flyttet, hale 920 00:50:20,530 --> 00:50:24,630 er bare dit array på indekset af størrelse. 921 00:50:24,630 --> 00:50:30,000 >> Men i virkeligheden, hvis du bruger en kø, dit hoved er sandsynligvis at blive opdateret. 922 00:50:30,000 --> 00:50:33,890 Så hvad du behøver at gøre er faktisk beregne halen. 923 00:50:33,890 --> 00:50:39,990 Så hvad vi gør, er denne formel her, som jeg har tænkt mig at lade dig 924 00:50:39,990 --> 00:50:42,680 fyre tænker over, og så vil vi tale om det. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Så dette er kapacitet. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Så dette vil faktisk give dig en måde at gøre det. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Fordi der i dette tilfælde, hvad? 931 00:51:04,330 --> 00:51:09,205 Vores hoved er på 1, vores størrelse er 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Hvis vi mod, der med 5, får vi 0, som er, hvor vi skal skrive den. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Så i den næste sag, hvis vi skulle gøre det, 936 00:51:26,080 --> 00:51:33,390 vi siger, OK, lad os dequeue noget. 937 00:51:33,390 --> 00:51:34,390 Vi dequeue dette. 938 00:51:34,390 --> 00:51:37,740 Vi tager ud dette element, right? 939 00:51:37,740 --> 00:51:47,930 >> Og nu er vores hoved peger her, og vi ønsker at tilføje i en anden ting. 940 00:51:47,930 --> 00:51:52,470 Dette er dybest set den bagsiden af ​​vores linje, right? 941 00:51:52,470 --> 00:51:55,450 Køer kan wrap omkring opstillingen. 942 00:51:55,450 --> 00:51:57,310 Det er en af ​​de væsentligste forskelle. 943 00:51:57,310 --> 00:51:58,780 Stakke, kan du ikke gøre dette. 944 00:51:58,780 --> 00:52:01,140 >> Med køer, kan du fordi alt, der betyder noget 945 00:52:01,140 --> 00:52:03,940 er, at du ved, hvad blev senest tilføjede. 946 00:52:03,940 --> 00:52:10,650 Da alt vil blive tilføjet i denne mod venstre retning, i dette tilfælde, 947 00:52:10,650 --> 00:52:16,480 og derefter wrap rundt, kan du fortsætte sætte i nye elementer 948 00:52:16,480 --> 00:52:18,830 på forsiden af ​​grupperingen fordi det ikke er virkelig 949 00:52:18,830 --> 00:52:20,640 forsiden af ​​grupperingen længere. 950 00:52:20,640 --> 00:52:26,320 Du kan tænke på begyndelsen af array som hvor dit hoved rent faktisk er. 951 00:52:26,320 --> 00:52:29,710 >> Så denne formel er, hvordan du beregne din hale. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Giver det mening? 954 00:52:35,610 --> 00:52:36,110 OK. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK, dequeue, og derefter du fyre har 10 minutter 957 00:52:44,040 --> 00:52:48,840 til at stille mig opklarende spørgsmål du ønsker, fordi jeg ved, det er vanvittigt. 958 00:52:48,840 --> 00:52:51,980 >> Okay, så i samme way-- Jeg ved ikke, hvis du fyre har bemærket, 959 00:52:51,980 --> 00:52:53,450 men CS handler om mønstre. 960 00:52:53,450 --> 00:52:57,370 Ting er temmelig samme, bare med små tweaks. 961 00:52:57,370 --> 00:52:58,950 Så samme ting her. 962 00:52:58,950 --> 00:53:04,040 Vi er nødt til at tjekke for at se, om vi rent faktisk har noget i vores kø, right? 963 00:53:04,040 --> 00:53:05,960 Sige, OK, er vores størrelse større end 0? 964 00:53:05,960 --> 00:53:06,730 Cool. 965 00:53:06,730 --> 00:53:10,690 >> Hvis vi gør, så vi flytter vores hoved, som er, hvad jeg lige demonstreret her. 966 00:53:10,690 --> 00:53:13,870 Vi opdaterer vores hoved til at være en mere. 967 00:53:13,870 --> 00:53:18,390 Og så har vi formindske vores størrelse og returnere elementet. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Der er meget mere konkret kode på study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 og jeg anbefaler stærkt går igennem det, hvis du har tid, 971 00:53:29,440 --> 00:53:30,980 selvom det er bare en pseudo-kode. 972 00:53:30,980 --> 00:53:35,980 Og hvis du fyre ønsker at tale igennem at med mig en på én, så lad mig venligst 973 00:53:35,980 --> 00:53:37,500 vide. 974 00:53:37,500 --> 00:53:38,770 Jeg ville være glad for. 975 00:53:38,770 --> 00:53:42,720 Datastrukturer, hvis du tager CS 124, vil du 976 00:53:42,720 --> 00:53:47,830 ved, at datastrukturer få meget sjov og dette er netop begyndt. 977 00:53:47,830 --> 00:53:50,350 >> Så jeg ved, det er svært. 978 00:53:50,350 --> 00:53:51,300 Det er OK. 979 00:53:51,300 --> 00:53:52,410 Vi kæmper. 980 00:53:52,410 --> 00:53:53,630 Jeg gør det stadig. 981 00:53:53,630 --> 00:53:56,660 Så du skal ikke bekymre dig for meget om det. 982 00:53:56,660 --> 00:54:02,390 >> Men det er dybest set din lynkursus i datastrukturer. 983 00:54:02,390 --> 00:54:03,400 Jeg ved, det er en masse. 984 00:54:03,400 --> 00:54:06,860 Er der noget, vi vil gerne gå igen? 985 00:54:06,860 --> 00:54:09,400 Noget vi ønsker at tale igennem? 986 00:54:09,400 --> 00:54:10,060 Ja? 987 00:54:10,060 --> 00:54:16,525 >> PUBLIKUM: For dette eksempel, så den nye hale er på 0 over det? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Ja. 989 00:54:17,150 --> 00:54:18,230 PUBLIKUM: OK. 990 00:54:18,230 --> 00:54:24,220 Så går igennem, du ville have 1 plus 4 eller-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Så du sagde, når vi ønsker at gå gøre det igen? 992 00:54:27,671 --> 00:54:28,296 PUBLIKUM: Ja. 993 00:54:28,296 --> 00:54:38,290 Så hvis du var at regne out-- hvor er du beregne halen fra i det? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Så halen var in-- Jeg har ændret dette. 995 00:54:44,260 --> 00:54:52,010 Så i dette eksempel her, det var array vi kigger på, OK? 996 00:54:52,010 --> 00:54:54,670 Så vi har ting i 1, 2, 3 og 4. 997 00:54:54,670 --> 00:55:05,850 Så vi har vores hoved er lig med 1 på dette punkt, og vores størrelse er lig med 4 998 00:55:05,850 --> 00:55:07,050 på dette tidspunkt, right? 999 00:55:07,050 --> 00:55:08,960 >> Du er alle enige om at det er tilfældet? 1000 00:55:08,960 --> 00:55:14,620 Så vi gør hovedet plus størrelse, som giver os 5 og derefter vi mod ved 5. 1001 00:55:14,620 --> 00:55:20,690 Vi får 0, hvilket fortæller os, at 0 er hvor er vores hale, hvor vi har plads. 1002 00:55:20,690 --> 00:55:22,010 >> PUBLIKUM: Hvad er en cap? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: kapacitet. 1004 00:55:23,520 --> 00:55:24,020 Undskyld. 1005 00:55:24,020 --> 00:55:29,640 Så det er størrelsen af ​​din array. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Ja? 1008 00:55:36,047 --> 00:55:39,210 >> PUBLIKUM: [uhørligt] før vi returnere element? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Så vi flytter hoved eller returnere det øjeblik? 1010 00:55:46,270 --> 00:55:52,680 Så hvis vi flytter en, formindske størrelsen? 1011 00:55:52,680 --> 00:55:54,150 Hold på. 1012 00:55:54,150 --> 00:55:55,770 Jeg helt sikkert har glemt en anden. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Pyt. 1015 00:56:01,990 --> 00:56:04,980 Der er ikke en anden formel. 1016 00:56:04,980 --> 00:56:09,980 Yeah, ville du ønsker at vende tilbage hovedet og derefter flytte det tilbage. 1017 00:56:09,980 --> 00:56:13,270 >> PUBLIKUM: OK, fordi der på dette punkt, lederen var på 0, 1018 00:56:13,270 --> 00:56:18,452 og du derefter ønsker at vende tilbage indeks 0 og derefter foretage head 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Right. 1020 00:56:19,870 --> 00:56:22,820 Jeg tror, ​​der er en anden formel slags som denne. 1021 00:56:22,820 --> 00:56:26,970 Jeg har ikke det på toppen mit hoved som Jeg ønsker ikke at give dig den forkerte. 1022 00:56:26,970 --> 00:56:35,470 Men jeg tror, ​​det er helt i orden at sige, OK, gemme denne element-- uanset 1023 00:56:35,470 --> 00:56:40,759 hovedets element is-- formindske din størrelse, flytte dit hoved over, og returnering 1024 00:56:40,759 --> 00:56:41,800 uanset det element er. 1025 00:56:41,800 --> 00:56:44,760 Det er helt gyldig. 1026 00:56:44,760 --> 00:56:45,260 OK. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Jeg mener ligesom dette ikke er ligesom most-- du ikke er 1029 00:56:53,560 --> 00:56:55,740 kommer til at gå ud af her ligesom, ja, jeg ved forsøg. 1030 00:56:55,740 --> 00:56:56,880 Jeg fik det hele. 1031 00:56:56,880 --> 00:56:57,670 Det er OK. 1032 00:56:57,670 --> 00:57:00,200 Jeg lover. 1033 00:57:00,200 --> 00:57:05,240 Men datastrukturer er noget, det tager en masse tid til at vænne sig til. 1034 00:57:05,240 --> 00:57:10,010 Sandsynligvis en af ​​de hårdest ting, tror jeg, i løbet. 1035 00:57:10,010 --> 00:57:15,330 >> Så det absolut tager repetition og leder at-- jeg 1036 00:57:15,330 --> 00:57:20,050 vidste virkelig hægtede lister indtil jeg gjorde alt for meget med dem, 1037 00:57:20,050 --> 00:57:22,550 på samme måde, som jeg gjorde ikke rigtig forstå pointers 1038 00:57:22,550 --> 00:57:27,040 indtil jeg har haft til at undervise i det for to år og gøre mine egne psets med det. 1039 00:57:27,040 --> 00:57:28,990 Det tager en masse af gentagelse og tid. 1040 00:57:28,990 --> 00:57:32,600 Og i sidste ende, vil den slags klik. 1041 00:57:32,600 --> 00:57:36,320 >> Men i mellemtiden, hvis du har slags et højt niveau forståelse af, hvad 1042 00:57:36,320 --> 00:57:39,321 disse gør, deres fordele og cons-- hvilket er hvad 1043 00:57:39,321 --> 00:57:41,820 vi virkelig har en tendens til at understrege, især i intro kursus. 1044 00:57:41,820 --> 00:57:45,511 Ligesom, hvorfor skulle vi bruge en prøve over et array? 1045 00:57:45,511 --> 00:57:48,010 Ligesom, hvad er de positive og negativer af hver af disse? 1046 00:57:48,010 --> 00:57:51,610 >> Og forstå trade-offs mellem hver af disse strukturer 1047 00:57:51,610 --> 00:57:54,910 er, hvad der er meget mere vigtigt lige nu. 1048 00:57:54,910 --> 00:57:58,140 Der kan være en skør spørgsmål eller to, der er 1049 00:57:58,140 --> 00:58:03,710 vil bede dig om at implementere skubbe eller implementere pop eller enqueue og dequeue. 1050 00:58:03,710 --> 00:58:07,340 Men for det meste, der har det højere forståelse niveau og mere 1051 00:58:07,340 --> 00:58:09,710 af en intuitiv forståelse er vigtigere end faktisk 1052 00:58:09,710 --> 00:58:11,250 være i stand til at gennemføre den. 1053 00:58:11,250 --> 00:58:14,880 >> Det ville være virkelig fedt, hvis alle jer kunne gå ud og gå gennemføre en prøve, 1054 00:58:14,880 --> 00:58:19,720 men vi forstår, det er ikke nødvendigvis den mest fornuftige ting lige nu. 1055 00:58:19,720 --> 00:58:23,370 Men du kan i din pset, hvis du ønsker til, og så får du praksis, 1056 00:58:23,370 --> 00:58:27,200 og så måske vil du rigtig forstå det. 1057 00:58:27,200 --> 00:58:27,940 Ja? 1058 00:58:27,940 --> 00:58:30,440 >> PUBLIKUM: OK, så, hvilke der er vi betød at bruge i pset? 1059 00:58:30,440 --> 00:58:31,916 Behøver jeg at bruge en af ​​dem? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Ja. 1061 00:58:32,540 --> 00:58:34,199 Så har du dit valg. 1062 00:58:34,199 --> 00:58:36,740 Jeg gætter i dette tilfælde, kan vi tale om pset en lille smule 1063 00:58:36,740 --> 00:58:40,480 fordi jeg kørte gennem disse. 1064 00:58:40,480 --> 00:58:47,779 Så i din pset, har du din valg af lande eller hash-tabeller. 1065 00:58:47,779 --> 00:58:49,570 Nogle mennesker vil forsøge og bruge bloom filtre, 1066 00:58:49,570 --> 00:58:51,840 men dem, der teknisk ikke er korrekte. 1067 00:58:51,840 --> 00:58:55,804 På grund af deres sandsynlighedstekniske, de giver falske positiver tider. 1068 00:58:55,804 --> 00:58:57,095 De er cool look ind, selv om. 1069 00:58:57,095 --> 00:58:59,030 Kan varmt anbefale at kigge på dem mindst. 1070 00:58:59,030 --> 00:59:03,260 Men du har dit valg mellem en hash tabel og en prøve. 1071 00:59:03,260 --> 00:59:06,660 Og det kommer til at være der, hvor du lægger i din ordbog. 1072 00:59:06,660 --> 00:59:09,230 >> Og du bliver nødt til at vælge din hash-funktionen, 1073 00:59:09,230 --> 00:59:13,420 du bliver nødt til at vælge, hvor mange skovle du har, og den vil variere. 1074 00:59:13,420 --> 00:59:17,440 Ligesom hvis du har flere spande, måske det vil køre hurtigere. 1075 00:59:17,440 --> 00:59:22,790 Men måske du spilder en masser af plads på den måde, selv om. 1076 00:59:22,790 --> 00:59:26,320 Du er nødt til at regne det ud. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> PUBLIKUM: Du sagde før, at vi kan bruge andre hashfunktioner, 1079 00:59:29,875 --> 00:59:31,750 at vi ikke behøver at skabe en hash-funktion? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Ja, til højre. 1081 00:59:32,666 --> 00:59:38,150 Så bogstaveligt til din hash funktion, ligesom google "hash-funktion" 1082 00:59:38,150 --> 00:59:40,770 og kigge efter nogle seje dem. 1083 00:59:40,770 --> 00:59:43,250 Du er ikke forventes at bygge dine egne hashfunktioner. 1084 00:59:43,250 --> 00:59:46,100 Folk bruger deres Teser om disse ting. 1085 00:59:46,100 --> 00:59:50,250 >> Så du skal ikke bekymre dig om at bygge din egen. 1086 00:59:50,250 --> 00:59:53,350 Find et online til at begynde med. 1087 00:59:53,350 --> 00:59:56,120 Nogle af dem er du nødt til manipulere en lille smule 1088 00:59:56,120 --> 00:59:59,430 for at sikre tilbagevenden typer matche op og whatnot, så i begyndelsen, 1089 00:59:59,430 --> 01:00:02,420 Jeg vil anbefale at bruge noget virkelig nemt at måske bare 1090 01:00:02,420 --> 01:00:04,680 hashes på det første bogstav. 1091 01:00:04,680 --> 01:00:08,760 Og så når du har at arbejde, inkorporerer en køler hash-funktionen. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> PUBLIKUM: Ville en prøve være eller effektiv, men blot sværere at, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Så en prøve, tror jeg, er intuitivt svært at gennemføre 1095 01:00:15,880 --> 01:00:18,310 men er meget hurtig. 1096 01:00:18,310 --> 01:00:20,620 Dog fylder mere. 1097 01:00:20,620 --> 01:00:25,270 Igen, kan du optimere både af dem i forskellige måder og der er måder at-- 1098 01:00:25,270 --> 01:00:26,770 PUBLIKUM: Hvordan skal vi gradueres på dette? 1099 01:00:26,770 --> 01:00:27,540 Er det matter-- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Så du gradueret normal måde. 1101 01:00:29,164 --> 01:00:31,330 Du kommer til at blive gradueret på design. 1102 01:00:31,330 --> 01:00:36,020 Uanset hvordan du gør det, du ønsker at sørg for at det er så elegant, som det kan være 1103 01:00:36,020 --> 01:00:38,610 og så effektivt som det kan være. 1104 01:00:38,610 --> 01:00:41,950 Men hvis du vælger en prøve eller hash bord, så længe det fungerer, 1105 01:00:41,950 --> 01:00:45,350 vi er tilfreds med at. 1106 01:00:45,350 --> 01:00:48,370 Og hvis du bruger noget, der hashes på det første bogstav, det er fint, 1107 01:00:48,370 --> 01:00:51,410 som måske lignende design-wise. 1108 01:00:51,410 --> 01:00:53,410 Vi er også at nå punkt i denne semester-- 1109 01:00:53,410 --> 01:00:55,340 Jeg ved ikke, om du fyre noticed-- hvis du er 1110 01:00:55,340 --> 01:00:58,780 pset kvaliteter falde en lille smule på grund af design og whatnot, 1111 01:00:58,780 --> 01:00:59,900 det er helt fint. 1112 01:00:59,900 --> 01:01:02,960 Det bliver til et punkt, hvor din programmer bliver mere kompliceret. 1113 01:01:02,960 --> 01:01:04,830 Der er flere steder du kan forbedre på. 1114 01:01:04,830 --> 01:01:06,370 >> Så det er helt normalt. 1115 01:01:06,370 --> 01:01:08,810 Det er ikke, at du er klarer sig dårligere på din pset. 1116 01:01:08,810 --> 01:01:11,885 Det er bare vi bliver hårdere på dig nu. 1117 01:01:11,885 --> 01:01:13,732 Så alles føler det. 1118 01:01:13,732 --> 01:01:14,940 Jeg har lige gradueret alle dine psets. 1119 01:01:14,940 --> 01:01:16,490 Jeg kender alle føler det. 1120 01:01:16,490 --> 01:01:19,600 >> Så du skal ikke være bekymret over det. 1121 01:01:19,600 --> 01:01:23,580 Og hvis du har spørgsmål om forudgående psets eller måder, du kan forbedre, 1122 01:01:23,580 --> 01:01:27,760 Jeg prøver og kommentere den specifikke steder, men nogle gange er det for sent 1123 01:01:27,760 --> 01:01:30,840 og jeg bliver træt. 1124 01:01:30,840 --> 01:01:34,885 Er der andre ting om datastrukturer? 1125 01:01:34,885 --> 01:01:37,510 Jeg er sikker på, du fyre ikke rigtig ønsker at tale om dem længere, 1126 01:01:37,510 --> 01:01:42,650 men hvis der er, er jeg glad for at gå over dem, samt noget 1127 01:01:42,650 --> 01:01:45,580 fra forelæsning denne fortid uge eller sidste uge. 1128 01:01:45,580 --> 01:01:51,580 >> Jeg kender i sidste uge var alle gennemgang, så vi kan have sprunget over nogle anmeldelse 1129 01:01:51,580 --> 01:01:54,190 fra forelæsning. 1130 01:01:54,190 --> 01:01:58,230 Alle andre spørgsmål kan jeg svare? 1131 01:01:58,230 --> 01:01:59,350 OK, okay. 1132 01:01:59,350 --> 01:02:02,400 Nå, jer komme ud 15 minutter tidligt. 1133 01:02:02,400 --> 01:02:08,370 >> Jeg håber, dette var semi-nyttige mindste og jeg vil se jer i næste uge, 1134 01:02:08,370 --> 01:02:12,150 eller torsdag kontortid. 1135 01:02:12,150 --> 01:02:15,285 Er der anmodninger om snacks til næste uge, det er de ting? 1136 01:02:15,285 --> 01:02:17,459 Fordi jeg glemte slik i dag. 1137 01:02:17,459 --> 01:02:19,750 Og jeg bragte slik sidste uge, men det var Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 så der var ligesom seks personer, der havde fire sække med slik til sig selv. 1139 01:02:25,400 --> 01:02:28,820 Jeg kan bringe starbursts igen, hvis du kan lide. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 OK, lyder godt. 1142 01:02:32,250 --> 01:02:35,050 Hav en god dag, gutter. 1143 01:02:35,050 --> 01:02:39,510