1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [Muusika mängimine] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: Olgu. 5 00:00:12,900 --> 00:00:14,600 Igaühel on hea meel tagasi lõik. 6 00:00:14,600 --> 00:00:18,660 Loodan, et te kõik olete edukalt toibunud oma viktoriin 7 00:00:18,660 --> 00:00:19,510 eelmisel nädalal. 8 00:00:19,510 --> 00:00:22,564 Tean, et see on natuke hull aegadel. 9 00:00:22,564 --> 00:00:25,230 Nagu ma ütlesin enne, kui sa oled jooksul standardhälve, 10 00:00:25,230 --> 00:00:28,188 tõesti ei muretse selle pärast, eriti jaoks vähem mugav sektsioonis. 11 00:00:28,188 --> 00:00:30,230 See, kui sa peaksid olema. 12 00:00:30,230 --> 00:00:32,850 >> Kui sa tegid hästi, siis awesome. 13 00:00:32,850 --> 00:00:33,650 Kiitus teile. 14 00:00:33,650 --> 00:00:36,149 Ja kui sa tunne, mida vaja natuke rohkem abi, palun 15 00:00:36,149 --> 00:00:38,140 julgelt jõuda läbi ükskõik TF. 16 00:00:38,140 --> 00:00:40,030 Me kõik oleme siin, et aidata. 17 00:00:40,030 --> 00:00:40,960 >> Sellepärast me õpetame. 18 00:00:40,960 --> 00:00:44,550 Sellepärast ma olen siin igal esmaspäeval teile poisid ja tööajal neljapäeviti. 19 00:00:44,550 --> 00:00:48,130 Nii et palun andke mulle teada kui olete mures midagi 20 00:00:48,130 --> 00:00:52,450 või kui seal on midagi viktoriin et sa tõesti tahaks tegeleda. 21 00:00:52,450 --> 00:00:56,940 >> Nii päevakorda täna kõike andmestruktuurid. 22 00:00:56,940 --> 00:01:01,520 Mõned neist on lihtsalt saab olema lihtsalt sulle tutvustatakse neid. 23 00:01:01,520 --> 00:01:04,870 Sa ei pruugi kunagi ellu neid selles klassis. 24 00:01:04,870 --> 00:01:08,690 Mõned neist te, nagu teie speller pset. 25 00:01:08,690 --> 00:01:11,380 >> Sa pead oma valikut vahel hash tabeleid ja proovib. 26 00:01:11,380 --> 00:01:13,680 Nii et me kindlasti läheb üle need. 27 00:01:13,680 --> 00:01:18,690 See saab olema kindlasti mitu liiki kõrgetasemelise lõik täna, kuigi 28 00:01:18,690 --> 00:01:22,630 sest seal on palju neid, ja kui meil läks rakendamise üksikasjad 29 00:01:22,630 --> 00:01:26,490 kõik need, me ei teeks isegi läbi saama ahelloendid 30 00:01:26,490 --> 00:01:28,520 ja võib-olla natuke hash tabeleid. 31 00:01:28,520 --> 00:01:31,200 >> Nii kannavad minuga. 32 00:01:31,200 --> 00:01:33,530 Me ei kavatse tegema nii palju kodeerimise seekord. 33 00:01:33,530 --> 00:01:36,870 Kui teil on küsimusi selle kohta või sa tahad seda näha rakendatud 34 00:01:36,870 --> 00:01:39,260 või proovida seda ise, Ma kindlasti soovitada 35 00:01:39,260 --> 00:01:44,250 läheb study.cs50.net, mis on näited kõiki neid. 36 00:01:44,250 --> 00:01:46,400 See on teil minu Powerpoint koos lisades, et me 37 00:01:46,400 --> 00:01:50,860 kalduvad kasutama samuti mõned programmeerimine harjutused, eriti asjad 38 00:01:50,860 --> 00:01:55,250 nagu ahelloendid ja binaarne puud korstnad ja märguannetele. 39 00:01:55,250 --> 00:01:59,590 Nii et veidi kõrge tase, mis oleks tore kutid. 40 00:01:59,590 --> 00:02:01,320 >> Nii, et me alustada. 41 00:02:01,320 --> 00:02:03,060 Ja ka yes-- viktoriine. 42 00:02:03,060 --> 00:02:06,550 Ma arvan, et enamik teist, kes on minu jaos on teie viktoriinid 43 00:02:06,550 --> 00:02:12,060 kuid keegi tuleb, või mingil põhjusel sa ei, nad on siin ees. 44 00:02:12,060 --> 00:02:12,740 >> Nii ahelloendid. 45 00:02:12,740 --> 00:02:15,650 Ma tean, et selline läheb tagasi enne viktoriini. 46 00:02:15,650 --> 00:02:17,940 See oli nädal enne et me saime selle. 47 00:02:17,940 --> 00:02:21,040 Aga sel juhul, me lihtsalt minna natuke põhjalikumalt. 48 00:02:21,040 --> 00:02:25,900 >> Nii et miks võiks me valime seotud nimekirja üle massiivi? 49 00:02:25,900 --> 00:02:27,130 Mis eristab neid? 50 00:02:27,130 --> 00:02:27,630 Jah? 51 00:02:27,630 --> 00:02:30,464 >> Sihtrühm: võib samuti laiendada seotud list versus massiiv on fikseeritud suurus. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Õigus. 53 00:02:31,171 --> 00:02:33,970 Massiiv on fikseeritud suurus arvestades seotud nimekirja on muutuv suurus. 54 00:02:33,970 --> 00:02:36,970 Nii et kui me ei tea, kuidas palju me tahame säilitada, 55 00:02:36,970 --> 00:02:39,880 ahelloend annab meile suur viis seda teha, sest me ei saa lihtsalt 56 00:02:39,880 --> 00:02:43,730 lisada teise sõlme ja lisada kohta teise sõlme ja lisada teise sõlme. 57 00:02:43,730 --> 00:02:45,750 Aga milline võiks olla kompromiss? 58 00:02:45,750 --> 00:02:49,521 Kas keegi mäletab, kompromiss vahel massiivid ja ahelloendid? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> Sihtrühm: Sa pead läbida kogu tee 61 00:02:51,460 --> 00:02:53,738 kaudu seotud nimekirja leida element nimekirja. 62 00:02:53,738 --> 00:02:55,570 Massiivi, saate lihtsalt leida element. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Õigus. 64 00:02:56,278 --> 00:02:57,120 Nii arrays-- 65 00:02:57,120 --> 00:02:58,500 >> Sihtrühm: [kuuldamatu]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: Mis massiivid meil mida nimetatakse muutmälu. 67 00:03:01,090 --> 00:03:04,820 Tähendab, et kui me tahame, mis on kunagi viies koht nimekiri 68 00:03:04,820 --> 00:03:07,230 või viies koht meie massiiv, saame lihtsalt haarata. 69 00:03:07,230 --> 00:03:10,440 Kui see on seotud nimekirja, meil itereerima läbi, eks? 70 00:03:10,440 --> 00:03:14,020 Nii tutvumise element massiiv on konstantne ajal 71 00:03:14,020 --> 00:03:19,530 arvestades, ahelloend see oleks tõenäoliselt lineaarne aeg, sest võib-olla 72 00:03:19,530 --> 00:03:21,370 Meie element on kogu tee lõpus. 73 00:03:21,370 --> 00:03:23,446 Meil on otsida kõike. 74 00:03:23,446 --> 00:03:25,320 Nii et kõik need andmed struktuuride me läheme 75 00:03:25,320 --> 00:03:29,330 kulutama veidi rohkem aega, Millised on plussid ja negatiivid. 76 00:03:29,330 --> 00:03:31,480 Kui pruugi me tahame kasutada ühte teisele? 77 00:03:31,480 --> 00:03:34,970 Ja see on omamoodi suurem asi ära võtta. 78 00:03:34,970 --> 00:03:40,140 >> Nii et meil on siin mõiste sõlme. 79 00:03:40,140 --> 00:03:43,040 See on nagu üks element meie seotud nimekirja, eks? 80 00:03:43,040 --> 00:03:46,180 Nii et me oleme kõik tuttavad meie typedef structs, 81 00:03:46,180 --> 00:03:47,980 mis me läksime üle läbivaatamine viimast korda. 82 00:03:47,980 --> 00:03:53,180 See oli põhimõtteliselt ainult luua teise andmetüübi et saaksime kasutada. 83 00:03:53,180 --> 00:03:57,930 >> Ja sel juhul, see on mingi sõlme et hoiab mõned täisarv. 84 00:03:57,930 --> 00:04:00,210 Ja mis siis on teine ​​osa siin? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Keegi? 87 00:04:05,677 --> 00:04:06,680 >> Sihtrühm: [kuuldamatu]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Jah. 89 00:04:07,020 --> 00:04:08,400 See on kursor järgmisele sõlme. 90 00:04:08,400 --> 00:04:12,610 Nii et see peaks tegelikult olema siin. 91 00:04:12,610 --> 00:04:18,790 See on viit tüüpi sõlme järgmine asi. 92 00:04:18,790 --> 00:04:22,410 Ja see, mida nad hõlmab meie sõlme. 93 00:04:22,410 --> 00:04:24,060 Külm. 94 00:04:24,060 --> 00:04:29,390 >> Olgu, nii otsingumootori, nagu me olime lihtsalt ütlen enne küljest, kui sa oled 95 00:04:29,390 --> 00:04:31,840 läheb läbi otsida, sa pead tegelikult itereerima 96 00:04:31,840 --> 00:04:33,660 läbi oma seotud nimekirja. 97 00:04:33,660 --> 00:04:38,530 Nii et kui me otsime arv 9, me hakkaks meie peas 98 00:04:38,530 --> 00:04:41,520 ja mis juhib meid alguses meie seotud nimekirja, eks? 99 00:04:41,520 --> 00:04:44,600 Ja me ütleme, OK, kas see sõlme sisaldama number 9? 100 00:04:44,600 --> 00:04:45,690 Ei? 101 00:04:45,690 --> 00:04:47,500 >> Olgu, minge järgmise üks. 102 00:04:47,500 --> 00:04:48,312 Jälgi seda. 103 00:04:48,312 --> 00:04:49,520 Kas see sisaldab number 9? 104 00:04:49,520 --> 00:04:50,570 Ei. 105 00:04:50,570 --> 00:04:51,550 Jälgi järgmise üks. 106 00:04:51,550 --> 00:04:55,490 >> Nii et me peame tegelikult itereerima meie seotud nimekirja. 107 00:04:55,490 --> 00:05:00,070 Me ei saa lihtsalt minna otse, kui 9 on. 108 00:05:00,070 --> 00:05:05,860 Ja kui te poisid tegelikult tahavad vaata mõned pseudo-kood seal. 109 00:05:05,860 --> 00:05:10,420 Meil on mõned allalaadimisfunktsioon siin mis võtab in-- mida see võtta? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Mis sa arvad? 112 00:05:14,320 --> 00:05:15,960 Nii lihtne. 113 00:05:15,960 --> 00:05:17,784 Mis see on? 114 00:05:17,784 --> 00:05:18,700 Sihtrühm: [kuuldamatu]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: number otsime. 116 00:05:20,366 --> 00:05:20,980 Õigus? 117 00:05:20,980 --> 00:05:22,875 Ja milline oleks see vastama? 118 00:05:22,875 --> 00:05:25,020 See on kursor? 119 00:05:25,020 --> 00:05:26,000 >> Sihtrühm: sõlme. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: sõlme nimekirja et me vaatame, eks? 121 00:05:28,980 --> 00:05:33,700 Nii et meil on mõned sõlmed on pointer siin. 122 00:05:33,700 --> 00:05:37,240 See on punkt, mis läheb tegelikult kordavad meie nimekirja. 123 00:05:37,240 --> 00:05:39,630 Seame see võrdne nimekirja sest see on just 124 00:05:39,630 --> 00:05:44,380 millega see võrdne alustada meie seotud nimekirja. 125 00:05:44,380 --> 00:05:50,660 >> Ja kuigi see ei ole NULL, kui meil on veel asju meie nimekirjas, 126 00:05:50,660 --> 00:05:55,580 kontrollige, kas see sõlm on arvu me otsime. 127 00:05:55,580 --> 00:05:57,740 Tagasi tõsi. 128 00:05:57,740 --> 00:06:01,070 Vastasel korral ajakohastab seda, eks? 129 00:06:01,070 --> 00:06:04,870 >> Kui see on NULL, me väljuda meie samas silmus ja tagasi vale 130 00:06:04,870 --> 00:06:08,340 sest see tähendab, et me ei ole leidnud. 131 00:06:08,340 --> 00:06:11,048 Kas igaüks saada, kuidas see toimib? 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 >> Nii sisestamist, siis on kolm erinevat viisi. 135 00:06:20,260 --> 00:06:25,250 Võite ülaloleva, saate lisada ja te saate lisada assortii. 136 00:06:25,250 --> 00:06:28,215 Sel juhul me oleme kavatse teha ülaloleva. 137 00:06:28,215 --> 00:06:33,380 Kas keegi teab, kuidas need kolmel juhul võivad olla erinevad? 138 00:06:33,380 --> 00:06:36,920 >> Nii ülaloleva tähendab, et paned see on ees oma nimekirja. 139 00:06:36,920 --> 00:06:39,770 Nii et see tähendaks, et ükskõik mida teie sõlm on, ükskõik, 140 00:06:39,770 --> 00:06:43,160 milline väärtus on, sa lähed pane see siin ees, eks? 141 00:06:43,160 --> 00:06:45,160 See saab olema esimene element nimekirjas. 142 00:06:45,160 --> 00:06:49,510 >> Kui lisada seda, et see läheb minna tagasi oma nimekirja. 143 00:06:49,510 --> 00:06:54,010 Ja lisada assortii tähendab, et sa oled panevad tegelikult paika 144 00:06:54,010 --> 00:06:57,700 kus ta hoiab oma seotud nimekirja sorteerida. 145 00:06:57,700 --> 00:07:00,810 Jällegi, kuidas kasutada neid ja kui te kasutate 146 00:07:00,810 --> 00:07:02,530 need varieeruvad sõltuvalt teie puhul. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Kui seda ei ole vaja sorteerida, ülaloleva kipub 149 00:07:07,750 --> 00:07:10,460 olema, mida enamik inimesi kasutada, sest teil ei ole 150 00:07:10,460 --> 00:07:15,680 läbima kogu nimekirja leida end lisada seda, eks? 151 00:07:15,680 --> 00:07:17,720 Sa võid jääda see õigus. 152 00:07:17,720 --> 00:07:21,930 >> Nii et me läheme läbi sisestamise 1 kohe. 153 00:07:21,930 --> 00:07:26,360 Nii et üks asi, mida ma lähen väga soovitada selle pset 154 00:07:26,360 --> 00:07:29,820 on juhtida asju teha, nagu alati. 155 00:07:29,820 --> 00:07:35,130 See on väga oluline, et teil uuendada Sinu suunanäitajaks õiges järjekorras 156 00:07:35,130 --> 00:07:38,620 sest kui sa neid uuendada veidi rikkis, 157 00:07:38,620 --> 00:07:42,210 sa lähed lõpuks kaotanud osa oma nimekirja. 158 00:07:42,210 --> 00:07:49,680 >> Nii näiteks, sel juhul oleme räägib pea lihtsalt punkt 1. 159 00:07:49,680 --> 00:07:56,070 Kui me just seda, et salvestamata see 1 160 00:07:56,070 --> 00:07:58,570 me ei tea, mida 1 tuleks viidata nüüd 161 00:07:58,570 --> 00:08:02,490 sest me oleme kaotanud, mida pea osutas. 162 00:08:02,490 --> 00:08:05,530 Nii et üks asi on meeles pidada kui sa teed ülaloleva 163 00:08:05,530 --> 00:08:09,630 on päästa mis head punktid esimene, 164 00:08:09,630 --> 00:08:15,210 siis ümber jaotada see ja seejärel ajakohastada mida teie uus sõlm tuleks viidata. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 Sel juhul see on üks viis seda teha. 167 00:08:22,560 --> 00:08:25,440 >> Nii et kui me oleksime teinud seda nii kus me lihtsalt ümber jaotada pea, 168 00:08:25,440 --> 00:08:30,320 me kaotame põhiliselt meie kogu nimekiri, eks? 169 00:08:30,320 --> 00:08:38,000 Üks viis seda teha on, et 1 punkt Järgmine, ja siis on pea punktist 1. 170 00:08:38,000 --> 00:08:42,650 Või saate teha selline nagu ajutine ladustamine, mis ma rääkisin. 171 00:08:42,650 --> 00:08:45,670 >> Aga ümberjagamise oma suunanäitajaks õiges järjekorras 172 00:08:45,670 --> 00:08:48,750 saab olema väga, väga oluline, et see pset. 173 00:08:48,750 --> 00:08:53,140 Muidu sa lähed on hash tabeli või proovida, mis on lihtsalt saab olema 174 00:08:53,140 --> 00:08:56,014 ainult osa sõnad, mida te tahad ja siis you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 Sihtrühm: Mis oli ajutine ladustamise asi, mida sa rääkisid? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: ajutine ladustamine. 177 00:09:00,305 --> 00:09:02,760 Nii et põhimõtteliselt veel kuidas sa võiksid seda teha 178 00:09:02,760 --> 00:09:07,650 on hoida pea midagi, nagu pange see ajutine muutuja. 179 00:09:07,650 --> 00:09:11,250 Määra see 1 ja seejärel värskendage 1 punkti 180 00:09:11,250 --> 00:09:13,830 mis iganes pea kasutada osutada. 181 00:09:13,830 --> 00:09:16,920 Nii on ilmselt rohkem elegantne, sest sa 182 00:09:16,920 --> 00:09:20,770 ei pea ajutise väärtust, kuid lihtsalt pakkuda veel üks võimalus seda teha. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 Ja me tegelikult ei ole mõned koodi selle eest. 185 00:09:25,790 --> 00:09:28,080 Nii ahelloend me tegelikult on mingi kood. 186 00:09:28,080 --> 00:09:31,930 Nii lisada siin, see on lisades nende ette. 187 00:09:31,930 --> 00:09:34,290 Nii et see sisestab selle juht. 188 00:09:34,290 --> 00:09:38,820 >> Nii et esimene asi, mida vaja luua endale sõlme, muidugi, 189 00:09:38,820 --> 00:09:40,790 ja kontrollige NULL. 190 00:09:40,790 --> 00:09:43,250 Alati hea. 191 00:09:43,250 --> 00:09:47,840 Ja siis pead määrama väärtused. 192 00:09:47,840 --> 00:09:51,260 Iga kord, kui loote uue sõlme, siis ei tea, mida see osutab teisele, 193 00:09:51,260 --> 00:09:54,560 nii soovid täita see tühjaks. 194 00:09:54,560 --> 00:09:58,760 Kui see lõpuks osutades midagi muud, siis saab ümber jaotada ja see on hea. 195 00:09:58,760 --> 00:10:00,740 Kui see on esimene asi, nimekirjas, tuleb 196 00:10:00,740 --> 00:10:04,270 juhtida tühjaks, sest see on loendi lõppu. 197 00:10:04,270 --> 00:10:12,410 >> Siis lisada see näeme siin on määrates järgmise väärtus meie sõlme 198 00:10:12,410 --> 00:10:17,380 olla mis iganes pea, mis on see, mis meil oli siin. 199 00:10:17,380 --> 00:10:19,930 See, mida me just tegid. 200 00:10:19,930 --> 00:10:25,820 Ja siis me määrates pea punkti meie uus sõlm, sest mäletan, 201 00:10:25,820 --> 00:10:31,090 Uus on mõned osuti tipu ja see on täpselt see, mida head on. 202 00:10:31,090 --> 00:10:34,370 See on täpselt, miks me on see nool Juurdepääsumeetodid. 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 >> Sihtrühm: Kas me peame initsialiseerida uus kõrval NULL esimene, 207 00:10:41,100 --> 00:10:44,240 või saame lihtsalt initsialiseerida see pea? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: Uus järgmine peab olema NULL alustada 209 00:10:48,210 --> 00:10:53,760 sest sa ei tea, kus see saab olema. 210 00:10:53,760 --> 00:10:56,100 Ka see on selline lihtsalt meeldib paradigma. 211 00:10:56,100 --> 00:10:59,900 Sa seadsid ta võrdne NULL lihtsalt teha Veenduge, et kõik teie alused on hõlmatud 212 00:10:59,900 --> 00:11:04,070 Enne tee midagi sihtotstarbe et sa oled alati tagatud, et see 213 00:11:04,070 --> 00:11:08,880 osutades, mille väärtus versus nagu prügi väärtus. 214 00:11:08,880 --> 00:11:12,210 Sest, jah, anname uus järgmisel automaatselt, 215 00:11:12,210 --> 00:11:15,420 aga see on rohkem nagu Hea tava initsialiseerida see 216 00:11:15,420 --> 00:11:19,270 niimoodi ja siis ümber jaotada. 217 00:11:19,270 --> 00:11:23,420 >> OK, nii et kahekordselt ahelloendid nüüd. 218 00:11:23,420 --> 00:11:24,601 Mida me arvame? 219 00:11:24,601 --> 00:11:26,350 Mis on erinev kahekordselt ahelloendid? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Nii et meie ahelloendid, saame liikuda ainult ühes suunas, eks? 222 00:11:34,300 --> 00:11:35,270 Meil on ainult järgmine. 223 00:11:35,270 --> 00:11:36,760 Me saame minna ainult edasi. 224 00:11:36,760 --> 00:11:40,300 >> Mis kahekordselt seotud nimekirja, saame ka tagasi liikuda. 225 00:11:40,300 --> 00:11:44,810 Nii et me ei ole mitte ainult number, et me tahame säilitada, 226 00:11:44,810 --> 00:11:50,110 meil on, kus ta märgib, et järgmisel ja kus me lihtsalt tulid. 227 00:11:50,110 --> 00:11:52,865 Nii võimaldab see mõned paremad läbipääsusüsteemid. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Nii kahekordselt seotud sõlmed, väga sarnased, eks? 230 00:12:01,240 --> 00:12:05,000 Ainus erinevus on see nüüd on järgmine ja eelmine. 231 00:12:05,000 --> 00:12:06,235 See on ainus erinevus. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Nii et kui me ülaloleva või append-- me ei ole mingit kood selle üles siin-- 234 00:12:14,790 --> 00:12:17,830 aga kui sul proovida ja sisestada, seda tähtsam 235 00:12:17,830 --> 00:12:19,980 on teil on vaja teha et olete määrates 236 00:12:19,980 --> 00:12:23,360 nii oma eelmise ja oma Järgmine pointer õigesti. 237 00:12:23,360 --> 00:12:29,010 Nii et antud juhul, siis oleks mitte ainult initsialiseerida kõrval, 238 00:12:29,010 --> 00:12:31,820 sa initsialiseerida eelmine. 239 00:12:31,820 --> 00:12:36,960 Kui me eesotsas nimekirja, me ei oleks ainult pea võrdne uue, 240 00:12:36,960 --> 00:12:41,750 aga meie uus eelmisel peaks juhtida pea, eks? 241 00:12:41,750 --> 00:12:43,380 >> See on ainus erinevus. 242 00:12:43,380 --> 00:12:47,200 Ja kui sa tahad rohkem praktikat need lingitud nimekirjad, mille paigaldamisel 243 00:12:47,200 --> 00:12:49,900 kustutamist, kus insert arvesse assortii nimekirja 244 00:12:49,900 --> 00:12:52,670 palun vaadake study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Seal on hunnik suurepäraseid harjutusi. 246 00:12:54,870 --> 00:12:55,870 Ma väga soovitada neile. 247 00:12:55,870 --> 00:12:59,210 Soovin, et meil oli aega minna nende kaudu kuid seal on palju andmestruktuurid 248 00:12:59,210 --> 00:13:01,530 läbi saama. 249 00:13:01,530 --> 00:13:02,650 >> OK, nii et hash tabeleid. 250 00:13:02,650 --> 00:13:07,070 See on tõenäoliselt kõige kasulikku bitti oma pset 251 00:13:07,070 --> 00:13:11,090 siin, sest sa lähed olema rakendamise üks neist, või proovida. 252 00:13:11,090 --> 00:13:12,200 Ma tõesti nagu hash tabeleid. 253 00:13:12,200 --> 00:13:13,110 Nad on päris lahe. 254 00:13:13,110 --> 00:13:17,080 >> Ühesõnaga, mida juhtub, on hash tabelit 255 00:13:17,080 --> 00:13:22,050 on see, kui me tegelikult vajame kiiret lisamise, kustutamise ja otsimise. 256 00:13:22,050 --> 00:13:25,010 Need on asjad, mida me oleme prioriteediks on hash tabelis. 257 00:13:25,010 --> 00:13:29,500 Nad saavad päris suur, kuid nagu me näeme, kus katseid 258 00:13:29,500 --> 00:13:33,040 on asju, mis on palju suuremad. 259 00:13:33,040 --> 00:13:38,330 >> Aga põhimõtteliselt on kõik hash Tabelis on räsifunktsioon 260 00:13:38,330 --> 00:13:47,215 mis ütleb teile, mida kopp panna iga Teie andmed iga oma elementi. 261 00:13:47,215 --> 00:13:51,140 Lihtne võimalus mõelda hash tabelit on see, et see on lihtsalt ämbrid asju, 262 00:13:51,140 --> 00:13:51,770 õige? 263 00:13:51,770 --> 00:13:59,720 Nii et kui te sorteerimine asju nagu esimene täht tema nime, 264 00:13:59,720 --> 00:14:01,820 see on selline nagu hash tabelis. 265 00:14:01,820 --> 00:14:06,180 >> Nii et kui ma rühm kutid on rühmadesse kes on nimi algab 266 00:14:06,180 --> 00:14:11,670 koos siin, või kes iganes sünnipäev on jaanuaris, veebruaris, märtsis, 267 00:14:11,670 --> 00:14:15,220 mis iganes, mis on tõhusalt luua hash tabelis. 268 00:14:15,220 --> 00:14:18,120 See on lihtsalt luua ämbrid et sa saad oma elemendid 269 00:14:18,120 --> 00:14:19,520 nii et võite leida neile lihtsamaks. 270 00:14:19,520 --> 00:14:22,300 Nii et sel viisil kui ma vajan leida üks teist, 271 00:14:22,300 --> 00:14:24,680 Ma ei pea otsima läbi iga oma nime. 272 00:14:24,680 --> 00:14:29,490 Ma võin olla nagu, oh, ma tean, et Danielle sünnipäev on in-- 273 00:14:29,490 --> 00:14:30,240 Sihtrühm: --April. 274 00:14:30,240 --> 00:14:30,948 SPEAKER 1: aprillis. 275 00:14:30,948 --> 00:14:33,120 Nii et ma vaatan minu aprill kopp, ja õnne, 276 00:14:33,120 --> 00:14:38,270 ta pead olema ainuke sinna ja minu ajal oli pidev selles mõttes, 277 00:14:38,270 --> 00:14:41,230 arvestades, et kui ma pean vaatama läbi terve hulk inimesi, 278 00:14:41,230 --> 00:14:43,090 see läheb palju kauem aega. 279 00:14:43,090 --> 00:14:45,830 Nii hash tabelid on tõesti ainult ämbrid. 280 00:14:45,830 --> 00:14:48,630 Lihtne võimalus mõelda neid. 281 00:14:48,630 --> 00:14:52,930 >> Seega on väga oluline asi hash tabel on hash funktsiooni. 282 00:14:52,930 --> 00:14:58,140 Nii et asi, mida ma lihtsalt rääkisime, nagu oma esimese kirja oma eesnimi 283 00:14:58,140 --> 00:15:01,450 või oma sünnipäeva kuul Need on ideed, mis 284 00:15:01,450 --> 00:15:03,070 tõesti korreleeruvad hash funktsiooni. 285 00:15:03,070 --> 00:15:08,900 See on lihtsalt viis, kuidas otsustada, mis kopp oled element läheb, eks? 286 00:15:08,900 --> 00:15:14,850 Nii see pset, võid otsida päris palju tahes hash funktsiooni, kui soovite. 287 00:15:14,850 --> 00:15:16,030 >> Ei pea olema oma. 288 00:15:16,030 --> 00:15:21,140 On mõned väga lahe ones out seal, et teha igasuguseid hull matemaatika. 289 00:15:21,140 --> 00:15:25,170 Ja kui sa tahad teha oma õigekirja super kiire, 290 00:15:25,170 --> 00:15:27,620 Ma tahaksin kindlasti vaata ühte nendest. 291 00:15:27,620 --> 00:15:32,390 >> Kuid on ka lihtsaid, nagu arvutama 292 00:15:32,390 --> 00:15:39,010 summa sõnadega, nagu iga täht on mitmeid. 293 00:15:39,010 --> 00:15:39,940 Arvuta summa. 294 00:15:39,940 --> 00:15:42,230 See määrab ämber. 295 00:15:42,230 --> 00:15:45,430 Neil on ka lihtne need, mis on nagu kõik on siin, 296 00:15:45,430 --> 00:15:47,050 kõik B on siin. 297 00:15:47,050 --> 00:15:48,920 Iga üks neist. 298 00:15:48,920 --> 00:15:55,770 >> Põhimõtteliselt, see lihtsalt ütleb, milline massiivi indeks element peaks minema. 299 00:15:55,770 --> 00:15:58,690 Lihtsalt otsustada bucket-- see kõik räsifunktsioon on. 300 00:15:58,690 --> 00:16:04,180 Nii et siin on meil tegemist näitega, mis on lihtsalt esimene täht string 301 00:16:04,180 --> 00:16:05,900 et ma lihtsalt räägin. 302 00:16:05,900 --> 00:16:11,900 >> Nii et teil on mõned hash see on alles esitäht oma string miinus, 303 00:16:11,900 --> 00:16:16,090 mis annab teile mõned number vahemikus 0 ja 25. 304 00:16:16,090 --> 00:16:20,790 Ja mida sa tahad teha, on veenduge, et see on 305 00:16:20,790 --> 00:16:24,110 suurust oma hash table-- kui palju ämbrid on. 306 00:16:24,110 --> 00:16:25,860 Paljude nende räsifunktsioonid, nad 307 00:16:25,860 --> 00:16:31,630 kavatse naasta väärtusi, mis võiksid olema palju suurem hulk ämbrid 308 00:16:31,630 --> 00:16:33,610 et sa tegelikult Teie hash tabelit, 309 00:16:33,610 --> 00:16:37,240 nii et sa pead tegema kindel ja mod need. 310 00:16:37,240 --> 00:16:42,190 Vastasel juhul läheb öelda, oh, see peaks olema ämber 5000 311 00:16:42,190 --> 00:16:46,040 aga sul on ainult 30 ämbrid oma hash tabelis. 312 00:16:46,040 --> 00:16:49,360 Ja muidugi, me kõik teame, mis on läheb kaasa mõned hull vigu. 313 00:16:49,360 --> 00:16:52,870 Seega veenduge, mod poolt suurust oma hash tabelis. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Külm. 316 00:16:58,930 --> 00:17:00,506 Nii kokkupõrkeid. 317 00:17:00,506 --> 00:17:02,620 Kas kõik head nii palju? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> Sihtrühm: Miks seda tagasi sellise suure raha? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: Sõltuvalt algoritmi et teie hash funktsiooni kasutab. 321 00:17:09,210 --> 00:17:12,270 Mõned neist teevad hull paljunemist. 322 00:17:12,270 --> 00:17:16,270 Ja see kõik on umbes saada ühtlane jaotus, 323 00:17:16,270 --> 00:17:18,490 nii nad teha mõned tõesti hull asju mõnikord. 324 00:17:18,490 --> 00:17:20,960 See on kõik. 325 00:17:20,960 --> 00:17:22,140 Veel midagi? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Nii kokkupõrkeid. 328 00:17:24,480 --> 00:17:29,270 Põhimõtteliselt, nagu ma juba ütlesin, parimal juhul stsenaariumi 329 00:17:29,270 --> 00:17:32,040 iga ämber vaatan on läheb on üks asi, 330 00:17:32,040 --> 00:17:34,160 nii et ma ei pea vaatama kõik, eks? 331 00:17:34,160 --> 00:17:37,040 Ma kas tead, et see on või on ei, ja see, mida me tegelikult tahame. 332 00:17:37,040 --> 00:17:43,960 Aga kui meil on kümneid tuhandeid andmepunkti ja väiksem number 333 00:17:43,960 --> 00:17:48,700 kopad, me lähed on kokkupõrked, kus lõpuks midagi 334 00:17:48,700 --> 00:17:54,210 läheb on sattuda kopp, mis on juba element. 335 00:17:54,210 --> 00:17:57,390 >> Seega on küsimus selles, mida me teeme sel juhul? 336 00:17:57,390 --> 00:17:58,480 Mida me teeme? 337 00:17:58,480 --> 00:17:59,300 Meil on juba midagi seal? 338 00:17:59,300 --> 00:18:00,060 Kas me lihtsalt visata see välja? 339 00:18:00,060 --> 00:18:00,700 >> Ei. 340 00:18:00,700 --> 00:18:01,980 Me peame neid mõlemaid. 341 00:18:01,980 --> 00:18:06,400 Niisiis, kuidas me tavaliselt teha, mis on mis? 342 00:18:06,400 --> 00:18:08,400 Mis on andmestruktuur me lihtsalt rääkisime? 343 00:18:08,400 --> 00:18:09,316 Sihtrühm: seotud nimekirja. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: seotud nimekirja. 345 00:18:10,500 --> 00:18:16,640 Nüüd, selle asemel iga ämbrid lihtsalt on üks element, 346 00:18:16,640 --> 00:18:24,020 see saab sisaldada seotud nimekirja elemendid, mis olid räsitud ta. 347 00:18:24,020 --> 00:18:27,588 OK, ei igaüks omamoodi saada, et idee? 348 00:18:27,588 --> 00:18:30,546 Kuna me ei saanud massiivi sest me ei tea, kui palju 349 00:18:30,546 --> 00:18:31,730 ei kavatse olla seal. 350 00:18:31,730 --> 00:18:36,540 Ahelloend võimaldab meil just täpne arv, mis 351 00:18:36,540 --> 00:18:38,465 on räsitud sellesse ämbrisse, eks? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Nii lineaarne Mõõtmine toimub põhimõtteliselt see idea-- 354 00:18:50,500 --> 00:18:52,300 see on üks võimalus tegeleda kokkupõrget. 355 00:18:52,300 --> 00:18:58,010 Mida saab teha, on see, kui selles juhul marja oli räsitud arvesse 1 356 00:18:58,010 --> 00:19:01,130 ja meil on juba midagi seal, sa lihtsalt 357 00:19:01,130 --> 00:19:04,840 Jätkab alla, kuni leiad tühja pesa. 358 00:19:04,840 --> 00:19:06,370 See on üks viis, kuidas sellega hakkama. 359 00:19:06,370 --> 00:19:09,020 Teine viis lahendada see on, mida me lihtsalt 360 00:19:09,020 --> 00:19:12,280 nimetaks seotud nimekiri nimetatakse ühendamine. 361 00:19:12,280 --> 00:19:20,510 >> Nii et see idee töötab, kui Sinu hash tabelit te arvate 362 00:19:20,510 --> 00:19:24,150 on palju suurem kui Oma andmete määrata või kui te 363 00:19:24,150 --> 00:19:28,870 tahan proovida ja minimeerida ühendamine kuni see on absoluutselt vajalik. 364 00:19:28,870 --> 00:19:34,050 Nii et üks asi on lineaarne katsetamine tähendab ilmselt 365 00:19:34,050 --> 00:19:37,290 et teie räsifunktsioon ei ole päris nii kasulik 366 00:19:37,290 --> 00:19:42,200 sest sa lähed lõpuks kasutavad Sinu hash funktsiooni, saada kuni punktini, 367 00:19:42,200 --> 00:19:46,400 sa lineaarne sondi alla Mõnes kohas, mis on saadaval. 368 00:19:46,400 --> 00:19:49,670 Aga nüüd muidugi midagi muud, mis jõuab sinna, 369 00:19:49,670 --> 00:19:52,050 sa lähed pea Otsige veelgi allapoole. 370 00:19:52,050 --> 00:19:55,650 >> Ja seal on palju rohkem otsi kulu, mis 371 00:19:55,650 --> 00:19:59,820 läheb sisestanud element Teie hash tabelit nüüd, eks? 372 00:19:59,820 --> 00:20:05,640 Ja nüüd, kui lähete ja püüda leida mari jälle sa lähed hash see, 373 00:20:05,640 --> 00:20:07,742 ja see läheb öelda, oh, vaata ämber 1 374 00:20:07,742 --> 00:20:09,700 ja ta ei kavatse olla kopp 1, nii et sa oled 375 00:20:09,700 --> 00:20:11,970 läheb on läbida kogu ülejäänud neid. 376 00:20:11,970 --> 00:20:17,720 Nii et see on mõnikord kasulik, kuid enamikel juhtudel 377 00:20:17,720 --> 00:20:22,660 me ei kavatse öelda, et ühendamine on see, mida sa teha tahad. 378 00:20:22,660 --> 00:20:25,520 >> Nii et me rääkisime sellest juba varem. 379 00:20:25,520 --> 00:20:27,812 Sain veidi enne ise. 380 00:20:27,812 --> 00:20:33,560 Aga ühendamine toimub põhiliselt, et iga ämber teie hash tabelit 381 00:20:33,560 --> 00:20:36,120 on lihtsalt seotud nimekirja. 382 00:20:36,120 --> 00:20:39,660 >> Nii et veel üks viis või rohkem tehnilisi Nii et mõtle hash tabelit 383 00:20:39,660 --> 00:20:44,490 on see, et see on lihtsalt massiivi Seotud nimekirjad, mis 384 00:20:44,490 --> 00:20:49,330 kui sa kirjutad oma sõnastik ja sa üritad seda laadida, 385 00:20:49,330 --> 00:20:52,070 mõtled seda massiivi ahelloendid 386 00:20:52,070 --> 00:20:54,390 on palju lihtsam teile käivitumist. 387 00:20:54,390 --> 00:20:57,680 >> Sihtrühm: Nii hash tabelit on määratud mõõtmetega, 388 00:20:57,680 --> 00:20:58,980 nagu [kuuldamatu] kopad? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Õigus. 390 00:20:59,220 --> 00:21:01,655 Seega on teatud arv ämbrid, et sa determine-- 391 00:21:01,655 --> 00:21:03,530 mis te poisid peaks vabalt mängida. 392 00:21:03,530 --> 00:21:05,269 See võib olla päris lahe et näha, mis juhtub, 393 00:21:05,269 --> 00:21:06,810 kui muudad arv ämbrid. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Aga jah, see on määratud arv ämbrid. 396 00:21:11,510 --> 00:21:15,360 Mis saab sobitada nii palju elemente, mida vajate 397 00:21:15,360 --> 00:21:19,350 on see eraldi ühendamine, kus sa on seotud nimekirjade iga ämber. 398 00:21:19,350 --> 00:21:22,850 See tähendab, et teie hash tabelit on täpselt suurust 399 00:21:22,850 --> 00:21:25,440 et sa pead seda, eks? 400 00:21:25,440 --> 00:21:27,358 See on mõte, mis on seotud nimekirju. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Külm. 403 00:21:32,480 --> 00:21:38,780 >> Nii et igaüks OK seal? 404 00:21:38,780 --> 00:21:39,801 Hea küll. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Mis siis juhtus? 407 00:21:41,860 --> 00:21:42,960 Tõesti kohe. 408 00:21:42,960 --> 00:21:45,250 Guess keegi tapab mind. 409 00:21:45,250 --> 00:21:52,060 >> OK me ei kavatse minna katseid, mis on natuke hull. 410 00:21:52,060 --> 00:21:53,140 Mulle meeldib hash tabeleid. 411 00:21:53,140 --> 00:21:54,460 Ma arvan, et nad on tõesti lahe. 412 00:21:54,460 --> 00:21:56,710 Katseid on lahe ka. 413 00:21:56,710 --> 00:21:59,590 >> Nii et keegi ei mäleta, mida proovida on? 414 00:21:59,590 --> 00:22:01,740 Sa oleks pidanud üle ta lühidalt loengu? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Kas mäletate, millist, kuidas see toimib? 417 00:22:06,377 --> 00:22:08,460 Sihtrühm: Ma lihtsalt noogutab et me ei lähe üle. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: Me ei lähe üle. 419 00:22:09,626 --> 00:22:13,100 OK, me tõesti minna selle üle nüüd on see, mida me ütleme. 420 00:22:13,100 --> 00:22:14,860 >> Sihtrühm: See on ette ülekanne puu. 421 00:22:14,860 --> 00:22:15,280 >> SPEAKER 1: Jah. 422 00:22:15,280 --> 00:22:16,196 See on ülekanne puu. 423 00:22:16,196 --> 00:22:16,960 Awesome. 424 00:22:16,960 --> 00:22:23,610 Nii et üks asi, mida tähele on see, et me otsivad üksikute märkide 425 00:22:23,610 --> 00:22:24,480 siin, eks? 426 00:22:24,480 --> 00:22:29,710 >> Nii et enne meie hash funktsiooni, me vaatasid sõnad tervikuna 427 00:22:29,710 --> 00:22:32,270 ja nüüd me otsime rohkem kell tegelased, eks? 428 00:22:32,270 --> 00:22:38,380 Nii et meil on Maxwell siia ja Mendel. 429 00:22:38,380 --> 00:22:47,840 Nii et põhimõtteliselt try-- võimalus mõelda on see, et igal tasandil siia 430 00:22:47,840 --> 00:22:49,000 on hulgaliselt kirju. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Nii et see on sinu juurtipust siin, eks? 433 00:22:55,790 --> 00:23:01,980 See on kõik tegelased tähestiku algusest iga sõna. 434 00:23:01,980 --> 00:23:06,480 >> Ja mida sa tahad teha, on ütleme, OK, meil on mõned M sõna. 435 00:23:06,480 --> 00:23:10,590 Me läheme otsima Maxwell, nii läheme M. Ja M punkte tervikuna 436 00:23:10,590 --> 00:23:14,800 teiste massiivi, kus iga Sõna, niikaua kui seal 437 00:23:14,800 --> 00:23:17,044 on sõna, mis on kui teise kirja, 438 00:23:17,044 --> 00:23:19,460 nii kaua, kui seal on sõna, mis on B Teine täht 439 00:23:19,460 --> 00:23:24,630 see on pointer läheb mõnele järgmisele massiivi. 440 00:23:24,630 --> 00:23:29,290 >> Seal ilmselt ei ole Sõna, mis MP midagi, 441 00:23:29,290 --> 00:23:32,980 nii et P positsiooni selles massiiv, see oleks lihtsalt NULL. 442 00:23:32,980 --> 00:23:38,840 See tähendab, OK, ei ole sõna mis on M, millele järgneb P, OK? 443 00:23:38,840 --> 00:23:43,100 Nii et kui me mõtleme selle peale, iga üks neist väiksemad asjad 444 00:23:43,100 --> 00:23:47,990 on tegelikult üks neist suur massiivide abil Z. 445 00:23:47,990 --> 00:23:55,064 Niisiis, milline võiks olla üks neist asjadest mis on omamoodi puuduseks proovida? 446 00:23:55,064 --> 00:23:56,500 >> Sihtrühm: palju mälu. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: See on ton mälu, eks? 448 00:23:59,940 --> 00:24:08,750 Igaüks neist plokid siit moodustab 26 ruumid, 26 elementi massiivi. 449 00:24:08,750 --> 00:24:13,680 Nii püüab saada uskumatult ruumi raske. 450 00:24:13,680 --> 00:24:17,100 >> Aga nad on väga kiire. 451 00:24:17,100 --> 00:24:22,540 Nii uskumatult kiire, kuid tõesti ruumi ebaefektiivne. 452 00:24:22,540 --> 00:24:24,810 Kind of pead mõtlema milline neist sa tahad. 453 00:24:24,810 --> 00:24:29,470 Need on väga lahe oma pset, kuid nad võtavad palju mälu, 454 00:24:29,470 --> 00:24:30,290 nii et sa kaubelda välja. 455 00:24:30,290 --> 00:24:31,480 Jah? 456 00:24:31,480 --> 00:24:34,300 >> Sihtrühm: Kas oleks võimalik luua proovida ja siis 457 00:24:34,300 --> 00:24:37,967 kui sul on kõik andmeid, et te need-- 458 00:24:37,967 --> 00:24:39,550 Ma ei tea, kas see oleks mõistlik. 459 00:24:39,550 --> 00:24:42,200 Olin vabanemiseks kõik NULL märki, kuid siis 460 00:24:42,200 --> 00:24:42,910 siis ei oleks võimalik indeks them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Sul on vaja veel neid. 462 00:24:43,275 --> 00:24:44,854 >> Sihtrühm: - samal viisil iga kord. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Jah. 464 00:24:45,520 --> 00:24:50,460 Sa pead NULL märki lasta sa tead, kui seal ei ole sõnagi seal. 465 00:24:50,460 --> 00:24:52,040 Ben ei teil on midagi, mida sa tahad? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 Olgu, nii et me läheme minna natuke rohkem 468 00:24:54,581 --> 00:24:58,920 arvesse tehnilisi üksikasju taga proovige ja töö kaudu näiteks. 469 00:24:58,920 --> 00:25:01,490 >> OK, nii et see on sama asi. 470 00:25:01,490 --> 00:25:06,290 Arvestades ahelloend meie peamised liiki of-- mida see sõna ma tahan? - 471 00:25:06,290 --> 00:25:08,350 nagu hoone plokk oli sõlme. 472 00:25:08,350 --> 00:25:12,280 In proovida, meil on ka sõlme, aga see on määratletud erinevalt. 473 00:25:12,280 --> 00:25:17,000 >> Nii et meil on mõned bool et tähistab, kas sõna tegelikult 474 00:25:17,000 --> 00:25:23,530 olemas selle asukoha ja seejärel meil on mõned massiivi siin-- või pigem 475 00:25:23,530 --> 00:25:27,840 see on viit massiivi 27 tähemärki. 476 00:25:27,840 --> 00:25:33,339 Ja see on antud juhul see 27-- ma olen kindel, et te kõik on nagu, oota 477 00:25:33,339 --> 00:25:34,880 on 26 tähte tähestikus. 478 00:25:34,880 --> 00:25:36,010 Miks meil on 27? 479 00:25:36,010 --> 00:25:37,870 >> Nii et sõltuvalt kuidas sa rakendada seda, 480 00:25:37,870 --> 00:25:43,240 see on pset et lubatud ülakomad. 481 00:25:43,240 --> 00:25:46,010 Nii et miks ekstra üks. 482 00:25:46,010 --> 00:25:50,500 Sul on ka mõnes juhul null terminaator 483 00:25:50,500 --> 00:25:53,230 sisaldub üks märki, et see on lubatud olla, 484 00:25:53,230 --> 00:25:56,120 ja see, kuidas nad kontrollivad, et kas see on lõpuks sõna. 485 00:25:56,120 --> 00:26:01,340 Kui olete huvitatud, vaadake Kevin video study.cs50, 486 00:26:01,340 --> 00:26:04,790 samuti Wikipedia on mõned head vahendid olemas. 487 00:26:04,790 --> 00:26:09,000 >> Aga me läheme läbi lihtsalt selline kuidas te võiks töötada läbi proovida 488 00:26:09,000 --> 00:26:11,010 kui sa oled andnud üks. 489 00:26:11,010 --> 00:26:16,230 Nii et meil on super lihtne siin, et on sõnad "nahkhiir" ja "zoom" neid. 490 00:26:16,230 --> 00:26:18,920 Ja nagu me näeme siin, see väike ruum siin 491 00:26:18,920 --> 00:26:22,560 esindab meie bool et ütleb: jah, see on sõna. 492 00:26:22,560 --> 00:26:27,060 Ja siis see on meie massiive tegelased, eks? 493 00:26:27,060 --> 00:26:33,480 >> Nii et me ei lähe läbi leidmise "nahkhiir" selles proovida. 494 00:26:33,480 --> 00:26:38,340 Nii algab ülaosas, eks? 495 00:26:38,340 --> 00:26:46,290 Ja me teame, et b vastab teine ​​indeks, teine ​​osa 496 00:26:46,290 --> 00:26:47,840 Käesoleva massiiv, sest ja b. 497 00:26:47,840 --> 00:26:51,340 Nii umbes teine. 498 00:26:51,340 --> 00:26:58,820 >> Ja ta ütleb, OK, lahe, jälgida, et arvesse Järgmise massiiv, sest kui me mäletame, 499 00:26:58,820 --> 00:27:02,160 see ei ole, et kõik need tegelikult sisaldavad elementi. 500 00:27:02,160 --> 00:27:07,110 Igaüks neist massiivid sisaldab pointer, eks? 501 00:27:07,110 --> 00:27:10,030 See on oluline vahet teha. 502 00:27:10,030 --> 00:27:13,450 >> Tean, et see on- üritab on tõesti raske saada esimest korda 503 00:27:13,450 --> 00:27:15,241 nii et isegi kui see on teist või kolmandat korda 504 00:27:15,241 --> 00:27:18,370 ja see on ikka omamoodi näilisest raske, 505 00:27:18,370 --> 00:27:21,199 Ma luban, kui sa lähed vaatama lühike uuesti homme, 506 00:27:21,199 --> 00:27:22,740 see ilmselt teha palju mõttekam. 507 00:27:22,740 --> 00:27:23,890 See võtab palju seedida. 508 00:27:23,890 --> 00:27:27,800 Ma ikka mõnikord olen nagu, oota, mis on proovida? 509 00:27:27,800 --> 00:27:29,080 Kuidas seda kasutada? 510 00:27:29,080 --> 00:27:33,880 >> Nii oleme b antud juhul mis on meie teine ​​indeks. 511 00:27:33,880 --> 00:27:40,240 Kui meil oleks, ütleme, c või d või muu kirja, 512 00:27:40,240 --> 00:27:45,810 meil on vaja kaarti, et tagasi indeks meie massiivi, mis vastab. 513 00:27:45,810 --> 00:27:56,930 Nii et me võtaks nagu rchar ja me lihtsalt lahutama ära kaardistada see 0 kuni 25. 514 00:27:56,930 --> 00:27:58,728 Kõik hea, kuidas me map meie iseloomu? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Nii et läheme teine ​​ja me näeme, et jah, see ei ole NULL. 517 00:28:05,980 --> 00:28:07,780 Me saame liikuda edasi selle kõrval massiivi. 518 00:28:07,780 --> 00:28:12,300 Nii et me läheme selle kõrval massiivi siin. 519 00:28:12,300 --> 00:28:15,500 >> Ja me ütleme, OK, nüüd peate mõtlema, kas on siin. 520 00:28:15,500 --> 00:28:18,590 Kas null või teeb seda tegelikult edasi liikuda? 521 00:28:18,590 --> 00:28:21,880 Nii et tegelikult liigub edastada selles massiivi. 522 00:28:21,880 --> 00:28:24,570 Ja me ütleme, OK, t on meie viimane täht. 523 00:28:24,570 --> 00:28:27,580 Nii et me läheme t indeks. 524 00:28:27,580 --> 00:28:30,120 Ja siis me liigume edasi sest seal on veel üks. 525 00:28:30,120 --> 00:28:38,340 Ja see ütleb sisuliselt, et jah, ta ütleb, et on olemas sõna siin-- 526 00:28:38,340 --> 00:28:41,750 et kui te järgite seda tee, olete jõudnud 527 00:28:41,750 --> 00:28:43,210 on sõna, mida me teame, on "nahkhiir". 528 00:28:43,210 --> 00:28:43,800 Jah? 529 00:28:43,800 --> 00:28:46,770 >> Sihtrühm: Kas see standard on, et kui indeks 0 ja siis on mingi 1 530 00:28:46,770 --> 00:28:47,660 või on lõpus? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: No. 532 00:28:48,243 --> 00:28:55,360 Nii et kui me vaatame tagasi meie avaldus siin, see on tõeväärtus, 533 00:28:55,360 --> 00:28:59,490 nii et see on oma osa teie sõlme. 534 00:28:59,490 --> 00:29:03,331 Nii see ei ole osa massiivi. 535 00:29:03,331 --> 00:29:03,830 Külm. 536 00:29:03,830 --> 00:29:08,370 Nii et kui me lõpetame oma sõna ja me oleme See massiiv, mida me tahame teha, 537 00:29:08,370 --> 00:29:12,807 on teha tšeki on see sõna. 538 00:29:12,807 --> 00:29:14,390 Ja sel juhul oleks tagasi jah. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Nii et selle teadmiseks, me teame, et "loomaaed" - me teame, kui inimesed, et "loomaaed" on sõna, 541 00:29:24,090 --> 00:29:24,820 õige? 542 00:29:24,820 --> 00:29:28,990 Aga kas proovida oleks siin öelda, ei, see ei ole. 543 00:29:28,990 --> 00:29:33,980 Ja see oleks öelda, et kuna me kes ei ole määranud seda sõna siin. 544 00:29:33,980 --> 00:29:40,440 Kuigi me võime läbida kuni see massiiv, 545 00:29:40,440 --> 00:29:43,890 seda proovida ütleksin, et ei, Loomaaia ei ole teie sõnastik 546 00:29:43,890 --> 00:29:47,070 sest meil ei ole määratud seda sellisena. 547 00:29:47,070 --> 00:29:52,870 >> Nii et üks võimalus seda teha selle-- oh, vabandust, see üks. 548 00:29:52,870 --> 00:29:59,450 Nii selles asjas "zoo" ei ole sõna, kuid see on meie proovida. 549 00:29:59,450 --> 00:30:05,690 Aga see, ütleme, et me tahame seda kasutusele sõna "vann", mis juhtub, 550 00:30:05,690 --> 00:30:08,260 on me järgime through-- b, t. 551 00:30:08,260 --> 00:30:11,820 Me oleme selles massiiv, ja läheme otsida h. 552 00:30:11,820 --> 00:30:15,220 >> Sellisel juhul, kui me vaadata osuti h, 553 00:30:15,220 --> 00:30:17,890 see osutab NULL, OK? 554 00:30:17,890 --> 00:30:20,780 Nii et kui see on selgesõnaliselt osutades teise massiiv, 555 00:30:20,780 --> 00:30:25,000 sa eeldada, et kõik viidad Selles massiiv on suunatud tühjaks. 556 00:30:25,000 --> 00:30:28,270 Nii et antud juhul h osutab tühjaks, et me ei saa midagi teha, 557 00:30:28,270 --> 00:30:31,540 nii et see oleks ka tagasi vale, "vanni" ei ole siin. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Nii et nüüd oleme tegelikult lähe läbi 560 00:30:35,810 --> 00:30:39,790 kuidas me tegelikult öelda et "loomaaed" on meie proovida. 561 00:30:39,790 --> 00:30:42,920 Kuidas lisada "loomaaed" meie proovida? 562 00:30:42,920 --> 00:30:47,810 Nii samamoodi, alustasime meie seotud nimekirja, hakkame keskmes. 563 00:30:47,810 --> 00:30:50,600 Kahtluse korral alustada juur neid asju. 564 00:30:50,600 --> 00:30:53,330 >> Ja me ütleme, OK, z. 565 00:30:53,330 --> 00:30:55,650 z olemas selles, ja see teeb. 566 00:30:55,650 --> 00:30:58,370 Nii et te liikudes edasi oma järgmise massiiv, OK? 567 00:30:58,370 --> 00:31:01,482 Ja siis järgmise üks, ütleme, OK, ei o olemas? 568 00:31:01,482 --> 00:31:03,000 See teeb. 569 00:31:03,000 --> 00:31:04,330 Seegi. 570 00:31:04,330 --> 00:31:08,670 >> Ja nii meie kõrval üks, me oleme öelnud, OK, "loomaaed" on juba olemas siin. 571 00:31:08,670 --> 00:31:12,440 Kõik me peame tegema, on seatud see võrdne tõsi, et seal on sõna seal. 572 00:31:12,440 --> 00:31:15,260 Kui teil on järginud kõik kuni enne seda, 573 00:31:15,260 --> 00:31:17,030 see on sõna, lihtsalt seada võrdsustatud. 574 00:31:17,030 --> 00:31:17,530 Jah? 575 00:31:17,530 --> 00:31:22,550 >> Sihtrühm: Nii et siis kas see tähenda, et "ba" on sõna ka? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: No. 577 00:31:24,120 --> 00:31:28,870 Nii et antud juhul "ba" saaksime siin me ütleks, on see sõna, 578 00:31:28,870 --> 00:31:31,590 ja oleks see siiski ei ole. 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 >> Sihtrühm: Nii et kui teil on see sõna ja te ütlete jah, siis 582 00:31:36,360 --> 00:31:38,380 sisaldab minna m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: Nii see on, mida teha with-- sa laadimisel sisse. 584 00:31:42,260 --> 00:31:43,640 Sa ütled "loomaaed" on sõna. 585 00:31:43,640 --> 00:31:47,020 Kui te lähete kontroll-- nagu, ütleme sa tahad öelda, 586 00:31:47,020 --> 00:31:49,400 ei "loomaaed" on olemas selles sõnastikku? 587 00:31:49,400 --> 00:31:54,200 Sa oled ainult kavatse otsida "loomaaias" ja siis vaadata, kas see on sõna. 588 00:31:54,200 --> 00:31:57,291 Sa ei saa kunagi liikuda kuni m, sest see ei ole 589 00:31:57,291 --> 00:31:58,290 mida te otsite. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Nii et kui me tegelikult tahtsime lisada "vann" sellesse proovida, 592 00:32:08,070 --> 00:32:11,390 me teeks sama asja nagu tegime "loomaaias" 593 00:32:11,390 --> 00:32:15,380 välja näeksime, et kui me proovida ja saada h, seda ei ole olemas. 594 00:32:15,380 --> 00:32:20,090 Nii et sa ei mõtle seda püüdnud lisada uue sõlme seotud nimekirja, 595 00:32:20,090 --> 00:32:27,210 nii et meil oleks vaja lisada veel üks neist massiivid, nagu nii. 596 00:32:27,210 --> 00:32:35,670 Ja siis see, mida me teha, on meil lihtsalt seada h element käesoleva array juhtides seda. 597 00:32:35,670 --> 00:32:39,430 >> Ja mis siis oleks me tahame teha siin? 598 00:32:39,430 --> 00:32:43,110 Lisa see võrdne tõsi sest see sõna. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Külm. 601 00:32:48,150 --> 00:32:48,700 Ma tean. 602 00:32:48,700 --> 00:32:51,170 Katseid ei ole kõige põnevam. 603 00:32:51,170 --> 00:32:54,250 Usu mind, ma tean. 604 00:32:54,250 --> 00:32:58,040 >> Nii et üks asi, mida mõistame katseid Ma ütlesin, et nad on väga tõhus. 605 00:32:58,040 --> 00:33:00,080 Nii et me oleme näinud neid asuda ton ruumi. 606 00:33:00,080 --> 00:33:01,370 Nad omamoodi segane. 607 00:33:01,370 --> 00:33:03,367 Miks peaks me kunagi kasuta neid? 608 00:33:03,367 --> 00:33:05,450 Me kasutame neid, sest nad on uskumatult tõhus. 609 00:33:05,450 --> 00:33:08,130 >> Seega, kui olete kunagi otsin üles sõna, siis on ainult 610 00:33:08,130 --> 00:33:10,450 piirneb pikkus sõna. 611 00:33:10,450 --> 00:33:15,210 Nii et kui te otsite Sõna, mis on pikkus viis, 612 00:33:15,210 --> 00:33:20,940 sa oled ainult kunagi pea teha kõige rohkem viis võrdlused, OK? 613 00:33:20,940 --> 00:33:25,780 Seega muudab põhimõtteliselt konstantne. 614 00:33:25,780 --> 00:33:29,150 Nagu sisestamise ja otsing Põhimõtteliselt on konstantne aega. 615 00:33:29,150 --> 00:33:33,750 >> Nii et kui te ei saa kunagi saada midagi pidevas ajal 616 00:33:33,750 --> 00:33:35,150 see on nii hea, kui see läheb. 617 00:33:35,150 --> 00:33:37,990 Sa ei saa parem kui konstantne ajas neid asju. 618 00:33:37,990 --> 00:33:43,150 Nii et on üks suur plussid proovib. 619 00:33:43,150 --> 00:33:46,780 >> Aga see on palju ruumi. 620 00:33:46,780 --> 00:33:50,380 Nii et sa selline pead otsustama Mis on sulle olulisem. 621 00:33:50,380 --> 00:33:54,700 Ja tänapäeva arvutid ruumi, et proovida võib kuluda kuni 622 00:33:54,700 --> 00:33:57,740 võibolla ei mõjuta teile, et palju, aga võib-olla 623 00:33:57,740 --> 00:34:01,350 sa oled tegelevad millegi mis on palju, palju rohkem asju, 624 00:34:01,350 --> 00:34:02,810 ja proovida lihtsalt ei ole mõistlik. 625 00:34:02,810 --> 00:34:03,000 Jah? 626 00:34:03,000 --> 00:34:05,610 >> Sihtrühm: Oota, nii et teil on 26 tähed iga üks? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: mmhmm. 628 00:34:07,440 --> 00:34:08,570 Jah, teil on 26. 629 00:34:08,570 --> 00:34:16,984 Teil on on sõna marker ja siis teil on 26 viiteid iga üks. 630 00:34:16,984 --> 00:34:17,775 Ja nad point-- 631 00:34:17,775 --> 00:34:20,280 >> Sihtrühm: Ja iga 26, nad on kummalgi 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Jah. 633 00:34:21,500 --> 00:34:27,460 Ja sellepärast, kui saate vaata avardab see üsna kiiresti. 634 00:34:27,460 --> 00:34:28,130 Hea küll. 635 00:34:28,130 --> 00:34:32,524 Nii et me ei kavatse sattuda puud, mis Ma tunnen, et on lihtsam, arvatavasti 636 00:34:32,524 --> 00:34:36,150 kena väike hingetõmbeaeg alates üritab seal. 637 00:34:36,150 --> 00:34:39,620 Loodetavasti enamik teist näinud puu enne. 638 00:34:39,620 --> 00:34:41,820 Mitte nagu päris need väljaspool, mida ma 639 00:34:41,820 --> 00:34:44,340 ei tea, kas keegi läks õues hiljuti. 640 00:34:44,340 --> 00:34:49,230 Läksin apple korjamine sel nädalavahetusel, ja oh heldust, see oli ilus. 641 00:34:49,230 --> 00:34:52,250 Ma ei teadnud, lehed võiks vaadata, et päris. 642 00:34:52,250 --> 00:34:53,610 >> Nii et see on lihtsalt puu, eks? 643 00:34:53,610 --> 00:34:56,790 See on lihtsalt mõned sõlme, ja see märgib, et hunnik muid tippe. 644 00:34:56,790 --> 00:34:59,570 Nagu näete siin, on see selline korduv teema. 645 00:34:59,570 --> 00:35:03,720 Sõlmed osutades sõlmed on selline sisuliselt palju andmestruktuurid. 646 00:35:03,720 --> 00:35:06,670 See lihtsalt sõltub sellest, kuidas me lasta osutavad üksteisele 647 00:35:06,670 --> 00:35:08,600 ja kuidas me läbida nende kaudu ja kuidas me 648 00:35:08,600 --> 00:35:14,500 lisada asju, mis määrab Erinevate omaduste tõttu. 649 00:35:14,500 --> 00:35:17,600 >> Nii lihtsalt mõned mõisted, mis ma olen varem kasutanud. 650 00:35:17,600 --> 00:35:20,010 Nii et juur on kõik, mis on tipus. 651 00:35:20,010 --> 00:35:21,200 see on koht, kus me alati alustada. 652 00:35:21,200 --> 00:35:23,610 Sa ei mõtle seda kui head ka. 653 00:35:23,610 --> 00:35:28,750 Aga puud, kaldume nimetavad seda root. 654 00:35:28,750 --> 00:35:32,820 >> Midagi allosas siin-- on väga bottom-- 655 00:35:32,820 --> 00:35:34,500 on lugeda lehtedest. 656 00:35:34,500 --> 00:35:37,210 Seega läheb koos Kogu puu asi, eks? 657 00:35:37,210 --> 00:35:39,860 Lehed on servades oma puu. 658 00:35:39,860 --> 00:35:45,820 >> Ja siis on meil ka paar mõttes rääkida sõlmede suhtes 659 00:35:45,820 --> 00:35:46,680 üksteisele. 660 00:35:46,680 --> 00:35:49,700 Nii et meil on vanem, laste ja õdede-vendadega. 661 00:35:49,700 --> 00:35:56,260 Nii antud juhul 3 on vanem 5, 6 ja 7. 662 00:35:56,260 --> 00:36:00,370 Nii et vanem on kõik, mis on üks samm eespool iganes sa oled 663 00:36:00,370 --> 00:36:02,940 viidates, lihtsalt nagu sugupuu. 664 00:36:02,940 --> 00:36:07,090 Loodan, et see kõik on veidi natuke rohkem intuitiivne kui proovib. 665 00:36:07,090 --> 00:36:10,970 >> Õed-vennad on need, mis on sama emaettevõtja, eks? 666 00:36:10,970 --> 00:36:13,470 Nad on samal tasemel siin. 667 00:36:13,470 --> 00:36:16,960 Ja siis, kui ma olin öeldes: lapsed on lihtsalt 668 00:36:16,960 --> 00:36:22,630 kõik, mis on üks samm allapoole sõlme küsimus, eks? 669 00:36:22,630 --> 00:36:23,470 Külm. 670 00:36:23,470 --> 00:36:25,610 Nii Binääripuu. 671 00:36:25,610 --> 00:36:31,450 Kas keegi ohtu arvan ühel omadused kahendpuu? 672 00:36:31,450 --> 00:36:32,770 >> Sihtrühm: Max kaks lehte. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Õigus. 674 00:36:33,478 --> 00:36:34,640 Nii et max kaks lehte. 675 00:36:34,640 --> 00:36:39,730 Nii et see enne oli meil see mis oli kolm, kuid Binääripuu, 676 00:36:39,730 --> 00:36:45,000 sul on max kaks laste vanema kohta, eks? 677 00:36:45,000 --> 00:36:46,970 Seal on teine huvitav omadus. 678 00:36:46,970 --> 00:36:51,550 Kas keegi teab, mis? 679 00:36:51,550 --> 00:36:52,620 Kahendpuud. 680 00:36:52,620 --> 00:37:00,350 >> Nii Binääripuu on kõik, kohta the-- ei ole see sorted-- 681 00:37:00,350 --> 00:37:05,320 kuid järjestatud kahendpuu, kõik paremal 682 00:37:05,320 --> 00:37:08,530 on suurem kui vanem, ja kõik vasakul 683 00:37:08,530 --> 00:37:10,035 on väiksem kui vanem. 684 00:37:10,035 --> 00:37:15,690 Ja see on olnud viktoriin küsimus enne, nii hea teada. 685 00:37:15,690 --> 00:37:19,500 Niisiis, kuidas me defineerime seda, uuesti, meil on veel üks sõlm. 686 00:37:19,500 --> 00:37:21,880 See tundub väga sarnane sellega, mida? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Kahekordselt 689 00:37:28,836 --> 00:37:29,320 >> Sihtrühm: ahelloendid 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: kahekordse seotud nimekirja, eks? 691 00:37:31,100 --> 00:37:33,690 Nii et kui me asendada see eelmise ja järgmise, 692 00:37:33,690 --> 00:37:35,670 see oleks kahekordselt seotud nimekirja. 693 00:37:35,670 --> 00:37:40,125 Kuid antud juhul me tegelikult on vasakule ja paremale ja see on kõik. 694 00:37:40,125 --> 00:37:41,500 Muidu on täpselt sama. 695 00:37:41,500 --> 00:37:43,374 Meil on veel element otsite, 696 00:37:43,374 --> 00:37:45,988 ja sa lihtsalt pead kahe viiteid läheb kõike, mis on järgmine. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Jah, nii kahendotsingupuu. 699 00:37:51,870 --> 00:37:57,665 Kui märkame, kõike siin on suurem than-- 700 00:37:57,665 --> 00:37:59,850 või kõike kohe paremale siin 701 00:37:59,850 --> 00:38:02,840 on suurem kui kõik, Siit on alla. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Nii et kui me otsida, siis peaks vaatama väga lähedal binaarne otsing 704 00:38:14,000 --> 00:38:14,910 siin, eks? 705 00:38:14,910 --> 00:38:17,640 Välja asemel otsin poole massiiv, 706 00:38:17,640 --> 00:38:21,720 me lihtsalt vaadata kas vasakule pool või paremal pool puud. 707 00:38:21,720 --> 00:38:24,850 Nii et see läheb veidi lihtsam, ma arvan. 708 00:38:24,850 --> 00:38:29,300 >> Seega, kui teie juur on NULL, ilmselt see on lihtsalt vale. 709 00:38:29,300 --> 00:38:33,470 Ja kui see on olemas, ilmselt see on tõsi. 710 00:38:33,470 --> 00:38:35,320 Kui see on väiksem kui me otsida vasakule. 711 00:38:35,320 --> 00:38:37,070 Kui see on suurem kui Otsime õige. 712 00:38:37,070 --> 00:38:39,890 See on täpselt nagu binaarne otsing, lihtsalt erinev andmestruktuur 713 00:38:39,890 --> 00:38:40,600 et me kasutame. 714 00:38:40,600 --> 00:38:42,790 Selle asemel, massiiv, see on lihtsalt Binääripuu. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, korstnad. 717 00:38:48,090 --> 00:38:51,550 Ja ka see näeb välja nagu me Võib-olla veidi aega. 718 00:38:51,550 --> 00:38:54,460 Kui me seda teeme, ma olen õnnelik, et minna üle kõik see uuesti. 719 00:38:54,460 --> 00:38:56,856 OK, nii et korstnad. 720 00:38:56,856 --> 00:39:02,695 Kas keegi mäletab, mida stacks-- mis tahes omadusi korstna? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, nii et enamik meist, ma arvan, süüa söögitoas halls-- 723 00:39:10,400 --> 00:39:13,100 nii palju kui me ei meeldi. 724 00:39:13,100 --> 00:39:16,900 Aga ilmselt sa ei mõtle virna sõna otseses mõttes nagu virna 725 00:39:16,900 --> 00:39:18,460 või virna asju. 726 00:39:18,460 --> 00:39:21,820 Ja mis oluline mõistma, et see on 727 00:39:21,820 --> 00:39:26,850 midagi-- iseloomulik et me nimetame seda by-- on LIFO. 728 00:39:26,850 --> 00:39:28,450 Kas keegi teab, mis see tähendab? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> Sihtrühm: viimane esimene välja. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: Õigus, kesta sisse, esimesena välja. 732 00:39:32,250 --> 00:39:36,585 Nii et kui me teame, kui me virnastamine asjad üles, kõige lihtsam asi haarata off-- 733 00:39:36,585 --> 00:39:39,570 ja võib-olla ainus asi, mida saab haarata välja, kui meie stack on suur loomult- 734 00:39:39,570 --> 00:39:40,850 on see, et ülemine element. 735 00:39:40,850 --> 00:39:43,460 Mida iganes pandi last-- nagu me näeme siin, 736 00:39:43,460 --> 00:39:46,370 mis iganes suruti kõige recently-- on 737 00:39:46,370 --> 00:39:51,160 saab olema esimene asi, mida me pop välja, OK? 738 00:39:51,160 --> 00:39:56,324 >> Mis meil siin on, teine ​​typedef struktuure. 739 00:39:56,324 --> 00:39:58,740 See on tõesti lihtsalt meeldib kiirkursuse andmestruktuur, 740 00:39:58,740 --> 00:40:01,650 nii seal on palju visatakse sind poisid. 741 00:40:01,650 --> 00:40:02,540 Ma tean. 742 00:40:02,540 --> 00:40:04,970 Nii et veel üks struct. 743 00:40:04,970 --> 00:40:06,740 Jee struktuuridele. 744 00:40:06,740 --> 00:40:16,660 >> Ja sel juhul, see on mingi pointer array, mis on mingil määral. 745 00:40:16,660 --> 00:40:20,830 Nii et see on meie korstnat siin, nagu meie tegelik massiivi 746 00:40:20,830 --> 00:40:22,520 mis hoiab meie elemente. 747 00:40:22,520 --> 00:40:24,850 Ja siis on meil siin mõned suurusest. 748 00:40:24,850 --> 00:40:31,170 >> Ja tavaliselt, mida soovite säilitada jälgida, kuidas suur teie stack on 749 00:40:31,170 --> 00:40:36,180 sest mis see saab lubada sul teha on, kui sa tead, suurus, 750 00:40:36,180 --> 00:40:39,170 see võimaldab teil öelda, OK, ma olen võimsuste? 751 00:40:39,170 --> 00:40:40,570 Kas ma saan midagi enamat? 752 00:40:40,570 --> 00:40:44,650 Ja see näitab ka, kus peal oma korstnat 753 00:40:44,650 --> 00:40:48,180 on, et sa tead, mida sa võib tegelikult startida. 754 00:40:48,180 --> 00:40:51,760 Ja see on tegelikult läheb olla natuke selgemaks siin. 755 00:40:51,760 --> 00:40:57,350 >> Nii push üks asi, kui sa olid kunagi rakendada lükkama, 756 00:40:57,350 --> 00:41:01,330 kui ma olin lihtsalt öeldes oma stack on piiratud suurusega, eks? 757 00:41:01,330 --> 00:41:03,990 Meie massiiv oli mingil määral. 758 00:41:03,990 --> 00:41:04,910 See on massiiv. 759 00:41:04,910 --> 00:41:08,930 See on kindla suurusega, nii et me peame veenduda, et me ei lase enam 760 00:41:08,930 --> 00:41:11,950 meie massiivi kui me tegelikult on ruumi. 761 00:41:11,950 --> 00:41:16,900 >> Nii et kui loote push funktsioon, esimene asi, mida teha, on öelda, OK, 762 00:41:16,900 --> 00:41:18,570 mul on ruumi minu stack? 763 00:41:18,570 --> 00:41:23,330 Sest kui ma seda ei tee, kahju, Ma ei saa salvestada element. 764 00:41:23,330 --> 00:41:28,980 Kui ma teen, siis soovite salvestada see ülaosas virna, eks? 765 00:41:28,980 --> 00:41:31,325 >> Ja see on põhjus, miks meil on jälgida meie suurus. 766 00:41:31,325 --> 00:41:35,290 Kui me ei jälgida oma suurusest, me ei tea, kuhu panna see. 767 00:41:35,290 --> 00:41:39,035 Me ei tea, kui palju on meie massiiv juba. 768 00:41:39,035 --> 00:41:41,410 Nagu ilmselt olemas viise et äkki sa võiksid seda teha. 769 00:41:41,410 --> 00:41:44,610 Sa võid initsialiseerida kõik NULL ja siis vaadata viimaseid NULL, 770 00:41:44,610 --> 00:41:47,950 kuid palju lihtsam asi on lihtsalt öelda, OK, jälgida suurus. 771 00:41:47,950 --> 00:41:51,840 Nagu ma tean, et mul on neli elementi minu massiiv, nii et järgmine asi 772 00:41:51,840 --> 00:41:55,930 et me panna, me oleme kavatse hoida indeksiga 4. 773 00:41:55,930 --> 00:42:00,940 Ja siis loomulikult tähendab see, et olete edukalt surunud midagi 774 00:42:00,940 --> 00:42:03,320 peale oma korstnat, siis tahad, et seda suurendada 775 00:42:03,320 --> 00:42:08,880 nii et sa tead, kus sa oled nii et saate suruda rohkem asju. 776 00:42:08,880 --> 00:42:12,730 >> Nii et kui me püüame pop midagi ära pinu 777 00:42:12,730 --> 00:42:16,072 milline võiks olla esimene asi, et me tahame, et kontrollida? 778 00:42:16,072 --> 00:42:18,030 Sa oled püüdnud võtta midagi välja oma korstnat. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Oled kindel, et seal on midagi oma korstnat? 781 00:42:24,781 --> 00:42:25,280 Ei. 782 00:42:25,280 --> 00:42:26,894 Mis võiks me tahame vaadata? 783 00:42:26,894 --> 00:42:27,810 >> Sihtrühm: [kuuldamatu]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Kontrollige suurus? 785 00:42:29,880 --> 00:42:31,840 Size. 786 00:42:31,840 --> 00:42:38,520 Nii et me tahame vaadata, kui Meie suurus on suurem kui 0, OK? 787 00:42:38,520 --> 00:42:44,970 Ja kui on, siis me tahame vähendada Meie suurus 0 ja tagastab selle. 788 00:42:44,970 --> 00:42:45,840 Miks? 789 00:42:45,840 --> 00:42:49,950 >> Esimesel üks olime lükates, oleme surunud ta 790 00:42:49,950 --> 00:42:52,460 peale suurus ja seejärel ajakohastada suurus. 791 00:42:52,460 --> 00:42:57,850 Sel juhul me decrementing suurus ja siis võta seda maha, kitkumise see 792 00:42:57,850 --> 00:42:58,952 meie massiivi. 793 00:42:58,952 --> 00:42:59,826 Miks võiks me seda teeme? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Nii et kui mul on üks asi, minu stack, milline oleks minu suurus sel hetkel? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> Ja kus on element 1 säilitatakse? 798 00:43:15,180 --> 00:43:17,621 Millisel indeks? 799 00:43:17,621 --> 00:43:18,120 Sihtrühm: 0. 800 00:43:18,120 --> 00:43:19,060 SPEAKER 1: 0. 801 00:43:19,060 --> 00:43:22,800 Nii antud juhul me alati on vaja teha sure-- 802 00:43:22,800 --> 00:43:27,630 tagasipöördumise asemel suurus miinus 1, sest me 803 00:43:27,630 --> 00:43:31,730 teame, et meie element on läheb ladustatakse 1 vähem 804 00:43:31,730 --> 00:43:34,705 mis tahes meie suurus on see lihtsalt hoolitseb ta. 805 00:43:34,705 --> 00:43:36,080 See on veidi rohkem elegantne viis. 806 00:43:36,080 --> 00:43:41,220 Ja me lihtsalt kahandab meie suurus ja siis tagasi suurusest. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> Sihtrühm: Ma arvan, et lihtsalt üldiselt Miks see andmestruktuur 809 00:43:45,300 --> 00:43:47,800 olla kasulik? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: See sõltub kontekstist. 811 00:43:50,660 --> 00:43:57,420 Nii mõned teoreetiliselt kui te töötate with-- OK, 812 00:43:57,420 --> 00:44:02,750 las ma vaatan, kas on kasulik üks mis on kasulik rohkem kui väljaspool 813 00:44:02,750 --> 00:44:05,420 CS. 814 00:44:05,420 --> 00:44:15,780 Mis korstnad, iga kord, kui on vaja jälgida midagi, 815 00:44:15,780 --> 00:44:20,456 on hiljuti lisatud on siis, kui sa lähed soovite kasutada virna. 816 00:44:20,456 --> 00:44:24,770 >> Ja ma ei mõtle hea näiteks, et just nüüd. 817 00:44:24,770 --> 00:44:29,955 Aga kui viimased asi on kõige tähtsam, 818 00:44:29,955 --> 00:44:31,705 see on, kui pakk saab olema kasulik. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Püüan mõelda kui seal on hea selle eest. 821 00:44:39,330 --> 00:44:43,720 Kui ma arvan, et on hea näide järgmises 20 minutit, siis ma kindlasti öelda. 822 00:44:43,720 --> 00:44:49,455 >> Aga üldiselt, kui seal on midagi, nagu ma ütlesin enamik, kus viimase 823 00:44:49,455 --> 00:44:52,470 Kõige tähtsam on, et on kus korstna hakkavad. 824 00:44:52,470 --> 00:44:58,860 Arvestades järjekorrad on omamoodi vastupidine. 825 00:44:58,860 --> 00:44:59,870 Ja kõik väikesed koerad. 826 00:44:59,870 --> 00:45:00,890 Kas see ei ole suur, eks? 827 00:45:00,890 --> 00:45:03,299 Ma tunnen nagu ma peaks lihtsalt jänes video 828 00:45:03,299 --> 00:45:05,090 õigus keset lõik kutid 829 00:45:05,090 --> 00:45:08,870 sest see on intensiivne sektsioonis. 830 00:45:08,870 --> 00:45:10,480 >> Nii järjekorda. 831 00:45:10,480 --> 00:45:12,710 Põhimõtteliselt järjekord on nagu joon. 832 00:45:12,710 --> 00:45:15,780 Kutid ma olen kindel, kasutavad seda iga päev, Just nagu meie söögisaali. 833 00:45:15,780 --> 00:45:18,160 Nii et me peame minema ja saada meie plaate, ma olen 834 00:45:18,160 --> 00:45:21,260 Kindlasti olete ootama kooskõlas kaevukook või saada oma toitu. 835 00:45:21,260 --> 00:45:24,650 >> Nii et siin midagi on, et see on FIFO. 836 00:45:24,650 --> 00:45:30,090 Nii et kui LIFO oli viimane esimene välja, FIFO on esimene, first out. 837 00:45:30,090 --> 00:45:33,400 Nii et see on koht, kus iganes sa panna esimesel on teie kõige olulisem. 838 00:45:33,400 --> 00:45:35,540 Nii et kui sa ootasid in LINE sa saad 839 00:45:35,540 --> 00:45:39,130 kujutage ette, kui sa läksid mine saada uus iPhone 840 00:45:39,130 --> 00:45:42,800 ja see oli virna, kus viimane inimene liin sai see esimene, 841 00:45:42,800 --> 00:45:44,160 inimesed tapavad üksteist. 842 00:45:44,160 --> 00:45:49,800 >> Nii FIFO, me oleme kõik väga hästi koos reaalses maailmas siin 843 00:45:49,800 --> 00:45:54,930 ja see kõik on pistmist tegelikult liiki taasloomine kogu see rida 844 00:45:54,930 --> 00:45:56,900 ja järjekordi struktuuri. 845 00:45:56,900 --> 00:46:02,390 Nii et koos virna, meil push ja pop. 846 00:46:02,390 --> 00:46:06,440 Mis järjekorras on meil Lisa järjekorda ja dequeue. 847 00:46:06,440 --> 00:46:10,910 Nii Lisa järjekorda tähendab põhimõtteliselt asetab selle tagasi, 848 00:46:10,910 --> 00:46:13,680 ja dequeue abil võtta välja eestpoolt. 849 00:46:13,680 --> 00:46:18,680 Nii et meie andmestruktuur natuke keeruline. 850 00:46:18,680 --> 00:46:21,060 Meil on teine ​​asi, mida jälgida. 851 00:46:21,060 --> 00:46:25,950 >> Nii et ilma pea, see Just korstna, eks? 852 00:46:25,950 --> 00:46:27,900 See on sama struktuur virna. 853 00:46:27,900 --> 00:46:32,480 Ainuke asi on nüüd muutunud on me on see pea, mida mida sa arvad 854 00:46:32,480 --> 00:46:34,272 läheb silma peal hoida? 855 00:46:34,272 --> 00:46:35,510 >> Sihtrühm: esimene. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Õigus, Esimene asi, mida me panna. 857 00:46:38,685 --> 00:46:41,130 Pea oma järjekorda. 858 00:46:41,130 --> 00:46:42,240 Kes on esimene rida. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Olgu, nii et kui me teeme Lisa järjekorda. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Jällegi ühegi Nende andmestruktuuride 863 00:46:55,920 --> 00:46:59,760 kuna me tegeleme massiiv, peame kontrollima, kas meil on ruumi. 864 00:46:59,760 --> 00:47:03,290 >> See on selline nagu mina ütlen kutid, kui avate faili 865 00:47:03,290 --> 00:47:04,760 peate kontrollima for null. 866 00:47:04,760 --> 00:47:08,330 Mis tahes kõnealuse korstnad ja järjekorrad, peate 867 00:47:08,330 --> 00:47:13,420 et näha, kas seal on ruumi, sest me oleme tegelevad fikseeritud suurusega massiiv, 868 00:47:13,420 --> 00:47:16,030 nagu me näeme siin-- 0, 1 kõik kuni 5. 869 00:47:16,030 --> 00:47:20,690 Niisiis, mida me teeme, et asi on kontrolli et näha, kas meil on veel ruumi. 870 00:47:20,690 --> 00:47:23,110 Kas meie suurus on väiksem kui võimsus? 871 00:47:23,110 --> 00:47:28,480 >> Kui jah, siis on meil vaja seda saba ja me uuendada meie suurus. 872 00:47:28,480 --> 00:47:30,250 Mida võib saba olla sel juhul? 873 00:47:30,250 --> 00:47:32,360 See ei ole selgelt välja kirjutatud. 874 00:47:32,360 --> 00:47:33,380 Kuidas me seda säilitada? 875 00:47:33,380 --> 00:47:34,928 Mida saba olla? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Nii et olgem kõndida läbi selle näite. 878 00:47:40,190 --> 00:47:44,590 Nii et see on massiivi suurus 6, eks? 879 00:47:44,590 --> 00:47:49,220 Ja meil on just nüüd, meie suurus on 5. 880 00:47:49,220 --> 00:47:55,240 Ja kui me pane see, et see läheb minna viienda indeks, eks? 881 00:47:55,240 --> 00:47:57,030 Nii et hoidke juures saba. 882 00:47:57,030 --> 00:48:05,600 >> Teine viis kirjutada saba oleks lihtsalt meie reaga indeks suurus, eks? 883 00:48:05,600 --> 00:48:07,560 See on suurus 5. 884 00:48:07,560 --> 00:48:11,490 Järgmine asi läheb minema 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 Läheb veidi keerulisem kui hakkame jama peas. 888 00:48:16,350 --> 00:48:17,060 Jah? 889 00:48:17,060 --> 00:48:20,090 >> Sihtrühm: Kas see tähendab, et me oleks deklareeritud massiivi 890 00:48:20,090 --> 00:48:23,880 oli viis elementi pikk ja siis lisame selle peale? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: No. 892 00:48:24,730 --> 00:48:27,560 Nii antud juhul on see virna. 893 00:48:27,560 --> 00:48:31,760 See tuleb deklareerida kui massiivi suurus 6. 894 00:48:31,760 --> 00:48:37,120 Ja sel juhul me lihtsalt ühe sammu vasakule. 895 00:48:37,120 --> 00:48:42,720 >> OK, nii et üks asi on selles juhul, kui meie juht on 0, 896 00:48:42,720 --> 00:48:45,270 siis me lihtsalt lisada seda suurust. 897 00:48:45,270 --> 00:48:51,020 Aga see läheb veidi keerukam sest tegelikult nad 898 00:48:51,020 --> 00:48:52,840 ei ole slaid selle eest, et ma lähen 899 00:48:52,840 --> 00:48:56,670 juhtida, sest see ei ole päris nii lihtne, kui sa 900 00:48:56,670 --> 00:48:59,230 alustada vabaneda asjadest. 901 00:48:59,230 --> 00:49:03,920 Nii et koos virna teil on ainult kunagi 902 00:49:03,920 --> 00:49:08,920 muretsema, mida suurus on kui sa oled lisades midagi, 903 00:49:08,920 --> 00:49:15,710 koos järjekorras pead ka tegema Veenduge, et teie pea on arvele võetud, 904 00:49:15,710 --> 00:49:20,760 sest lahe asi järjekorrad on see, et kui sa ei ole suutlikkust, 905 00:49:20,760 --> 00:49:23,040 tegelikult võite teha seda ümbritsev. 906 00:49:23,040 --> 00:49:28,810 >> OK, nii et üks asi-- oh, see on kohutav kriit. 907 00:49:28,810 --> 00:49:31,815 Üks asi, mida kaaluda on. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Me lihtsalt teha viis. 910 00:49:37,140 --> 00:49:41,810 OK, nii et me ei kavatse öelda pea on siin. 911 00:49:41,810 --> 00:49:46,140 See on 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> Pea on olemas, ja palun, on asju neile. 913 00:49:54,210 --> 00:49:58,340 Ja tahame lisada midagi, eks? 914 00:49:58,340 --> 00:50:01,170 Nii et asi, mida me peame tean, on see, et pea on alati 915 00:50:01,170 --> 00:50:05,620 Liigutatav nii ja siis loop tagasi umbes, eks? 916 00:50:05,620 --> 00:50:10,190 >> Nii et see järjekord on ruumi, eks? 917 00:50:10,190 --> 00:50:13,950 See on ruum, algusest peale, omamoodi vastand. 918 00:50:13,950 --> 00:50:17,920 Niisiis, mida me peame tegema, on meil vaja arvutada saba. 919 00:50:17,920 --> 00:50:20,530 Kui te teate, et teie juht ei ole teinud, saba 920 00:50:20,530 --> 00:50:24,630 on lihtsalt oma reaga indeks suurus. 921 00:50:24,630 --> 00:50:30,000 >> Aga tegelikult, kui te kasutate järjekorda, su pea on vist uuendatakse. 922 00:50:30,000 --> 00:50:33,890 Nii et mida sa pead tegema, on tegelikult arvutada saba. 923 00:50:33,890 --> 00:50:39,990 Niisiis, mida me teeme, on see valem siin, mis ma teile 924 00:50:39,990 --> 00:50:42,680 poisid mõtlevad, ja siis me räägime sellest. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Nii et see on võimsust. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Nii see tegelikult teile, kuidas seda teha. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Kuna antud juhul, siis mida? 931 00:51:04,330 --> 00:51:09,205 Meie peakontor on 1, meie suurus on 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Kui me mod, et 5, saame 0, mis on koht, kus me peaksime sisend ta. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Nii et siis järgmisel juhul Kui me seda teha, 936 00:51:26,080 --> 00:51:33,390 ütleme, OK, lähme dequeue midagi. 937 00:51:33,390 --> 00:51:34,390 Me dequeue see. 938 00:51:34,390 --> 00:51:37,740 Võtame välja see osa, eks? 939 00:51:37,740 --> 00:51:47,930 >> Ja nüüd meie pea on suunaga siia ja me tahame lisada teise asi. 940 00:51:47,930 --> 00:51:52,470 See on põhiliselt tagasi meie rida, eks? 941 00:51:52,470 --> 00:51:55,450 Järjekorrad võivad ümbritsev massiiv. 942 00:51:55,450 --> 00:51:57,310 See on üks peamisi erinevusi. 943 00:51:57,310 --> 00:51:58,780 Korstnad, sa ei saa seda teha. 944 00:51:58,780 --> 00:52:01,140 >> Mis järjekorrad, saate sest kõik, mis loeb 945 00:52:01,140 --> 00:52:03,940 on see, et sa tead, mida viimati oli lisatud. 946 00:52:03,940 --> 00:52:10,650 Kuna kõik läheb lisada Selle vastassuunaliseks suunas, käesoleval juhul 947 00:52:10,650 --> 00:52:16,480 ja siis murtakse, saate jätkata kasutusele uusi elemente 948 00:52:16,480 --> 00:52:18,830 ees massiivi sest see ei ole tõesti 949 00:52:18,830 --> 00:52:20,640 ees massiivi enam. 950 00:52:20,640 --> 00:52:26,320 Sa ei mõtle alguses massiivi kus oma peaga tegelikult on. 951 00:52:26,320 --> 00:52:29,710 >> Nii et see valem on see, kuidas sa arvutada oma saba. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Kas see on mõistlik? 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 ja seejärel kutid on 10 minutit, 957 00:52:44,040 --> 00:52:48,840 minu käest küsida ükskõik selgitavaid küsimusi sa tahad, sest ma tean, et see on hull. 958 00:52:48,840 --> 00:52:51,980 >> Olgu, nii sama way-- Ma ei tea, kas kutid märganud, 959 00:52:51,980 --> 00:52:53,450 aga CS on kõike mustrid. 960 00:52:53,450 --> 00:52:57,370 Asjad on päris palju sama, just pisikeste lisasid. 961 00:52:57,370 --> 00:52:58,950 Nii et sama asi siin. 962 00:52:58,950 --> 00:53:04,040 Meil on vaja vaadata, kui me tegelikult on midagi meie järjekorda, eks? 963 00:53:04,040 --> 00:53:05,960 Ütle, OK, on ​​meie suurus on suurem kui 0? 964 00:53:05,960 --> 00:53:06,730 Külm. 965 00:53:06,730 --> 00:53:10,690 >> Kui me seda teeme, siis me liigume meie peas, mis on see, mida ma siin näidatud. 966 00:53:10,690 --> 00:53:13,870 Me uuendada meie pea olema üks rohkem. 967 00:53:13,870 --> 00:53:18,390 Ja siis me kahandab meie suurus ja tagastab element. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Seal on palju konkreetsem kood study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 ja ma väga soovitada kavatse kaudu, kui teil on aega, 971 00:53:29,440 --> 00:53:30,980 isegi kui see on lihtsalt pseudo-koodi. 972 00:53:30,980 --> 00:53:35,980 Ja kui te tahate rääkida läbi mis minuga üks ühele, siis palun andke mulle 973 00:53:35,980 --> 00:53:37,500 tean. 974 00:53:37,500 --> 00:53:38,770 Ma oleksin hea meelega. 975 00:53:38,770 --> 00:53:42,720 Andmestruktuuride, kui te võtate CS 124, saate 976 00:53:42,720 --> 00:53:47,830 tean, et andmestruktuurid saada väga lõbus ja see on alles algus. 977 00:53:47,830 --> 00:53:50,350 >> Nii et ma tean, et see on raske. 978 00:53:50,350 --> 00:53:51,300 See on OK. 979 00:53:51,300 --> 00:53:52,410 Me vaeva. 980 00:53:52,410 --> 00:53:53,630 Ma ikka teha. 981 00:53:53,630 --> 00:53:56,660 Nii et ärge muretsege liiga palju seda. 982 00:53:56,660 --> 00:54:02,390 >> Aga see on põhimõtteliselt oma kiirkursuse andmestruktuurid. 983 00:54:02,390 --> 00:54:03,400 Ma tean, et see on palju. 984 00:54:03,400 --> 00:54:06,860 Kas on midagi, mida me tahaks minna jälle? 985 00:54:06,860 --> 00:54:09,400 Midagi me tahame rääkida läbi? 986 00:54:09,400 --> 00:54:10,060 Jah? 987 00:54:10,060 --> 00:54:16,525 >> Sihtrühm: Sest et näiteks nii uus saba on 0 üle on? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Jah. 989 00:54:17,150 --> 00:54:18,230 Sihtrühm: OK. 990 00:54:18,230 --> 00:54:24,220 Siis läheb läbi, soovid on 1 pluss 4 või-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Nii et sa ütlesid, kui me tahame minna seda uuesti? 992 00:54:27,671 --> 00:54:28,296 Sihtrühm: Jah. 993 00:54:28,296 --> 00:54:38,290 Nii et kui sa olid viinud out-- kus on sa arvutamise saba on? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Nii saba oli in-- muutsin seda. 995 00:54:44,260 --> 00:54:52,010 Nii selles näites siin, see oli massiivi me vaatame, OK? 996 00:54:52,010 --> 00:54:54,670 Nii et meil on asjad 1, 2, 3 ja 4. 997 00:54:54,670 --> 00:55:05,850 Nii et meil on meie peas on võrdne 1 juures Sel hetkel, ja meie suurus on kuni 4 998 00:55:05,850 --> 00:55:07,050 Sel hetkel, eks? 999 00:55:07,050 --> 00:55:08,960 >> Te kõik ühel meelel selles on asi? 1000 00:55:08,960 --> 00:55:14,620 Nii et me teeme head, pluss suurus, mis annab meile 5 ja siis mod 5. 1001 00:55:14,620 --> 00:55:20,690 Me saame 0, mis ütleb meile, et 0 on kus on meie saba, kus meil on ruumi. 1002 00:55:20,690 --> 00:55:22,010 >> Sihtrühm: Mis on kork? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: võimsus. 1004 00:55:23,520 --> 00:55:24,020 Vabandust. 1005 00:55:24,020 --> 00:55:29,640 Nii et on suurus oma massiivi. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Jah? 1008 00:55:36,047 --> 00:55:39,210 >> Sihtrühm: [kuuldamatu] enne naaseme element? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Nii et me liigume pea või tagastab hetkel? 1010 00:55:46,270 --> 00:55:52,680 Nii et kui me liigume ühe, aland suurus? 1011 00:55:52,680 --> 00:55:54,150 Oota. 1012 00:55:54,150 --> 00:55:55,770 Ma kindlasti unustasin veel. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Pole viga. 1015 00:56:01,990 --> 00:56:04,980 Ei ole veel valemit. 1016 00:56:04,980 --> 00:56:09,980 Jah, sa tahaksid tagasi pea ja seejärel liigutada tagasi. 1017 00:56:09,980 --> 00:56:13,270 >> Sihtrühm: OK, sest sel punkt, pea oli 0, 1018 00:56:13,270 --> 00:56:18,452 ja siis tahavad tagasi indeks 0 ja seejärel teha peaga 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Õigus. 1020 00:56:19,870 --> 00:56:22,820 Ma arvan, et seal on teine valem selline nagu see. 1021 00:56:22,820 --> 00:56:26,970 Ma ei ole seda peal mu pea Ma ei taha, et sulle vale. 1022 00:56:26,970 --> 00:56:35,470 Aga ma arvan, et see on täiesti kehtib kuni ütleme, OK, hoidke element-- iganes 1023 00:56:35,470 --> 00:56:40,759 pea on element on-- aland oma suurus, liikuda oma pea üle ja tagastamine 1024 00:56:40,759 --> 00:56:41,800 mis iganes see element on. 1025 00:56:41,800 --> 00:56:44,760 See on täiesti õige. 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 Ma tunnen, et see ei ole nagu most-- sa ei ole 1029 00:56:53,560 --> 00:56:55,740 läheb käima siit nagu jah, ma tean, et proovib. 1030 00:56:55,740 --> 00:56:56,880 Ma sain selle kõik. 1031 00:56:56,880 --> 00:56:57,670 See on OK. 1032 00:56:57,670 --> 00:57:00,200 Ma luban. 1033 00:57:00,200 --> 00:57:05,240 Aga andmestruktuurid on midagi, see võtab palju aega, et harjuda. 1034 00:57:05,240 --> 00:57:10,010 Ilmselt üks raskemaid asju, ma arvan, et muidugi. 1035 00:57:10,010 --> 00:57:15,330 >> Nii see kindlasti võtab kordamine ja otsin at-- I 1036 00:57:15,330 --> 00:57:20,050 ei tea ahelloendid kuni tegin liiga palju neid, 1037 00:57:20,050 --> 00:57:22,550 samamoodi, et ma ei teinud seda tõesti aru viiteid 1038 00:57:22,550 --> 00:57:27,040 kuni ma olen olnud seda õpetada kaks aastat ja teha oma psets ta. 1039 00:57:27,040 --> 00:57:28,990 See võtab palju kordamist ja aega. 1040 00:57:28,990 --> 00:57:32,600 Ja lõpuks, siis millist nuppu. 1041 00:57:32,600 --> 00:57:36,320 >> Kuid samal ajal, kui teil on omamoodi kõrgetasemelise arusaam sellest, mida 1042 00:57:36,320 --> 00:57:39,321 need teevad, nende plusse ja cons-- mis on see, mida 1043 00:57:39,321 --> 00:57:41,820 me tõesti kipuvad rõhutama, eriti intro muidugi. 1044 00:57:41,820 --> 00:57:45,511 Nagu, miks me kasutame proovida üle massiivi? 1045 00:57:45,511 --> 00:57:48,010 Like, millised on positiivsed ja negatiivid iga nimetatud? 1046 00:57:48,010 --> 00:57:51,610 >> Ja mõista kompromissid omavahel nende struktuuride 1047 00:57:51,610 --> 00:57:54,910 on see, mis on palju olulisem just nüüd. 1048 00:57:54,910 --> 00:57:58,140 Tegemist võib olla üks hull Küsimus või kaks, mis on 1049 00:57:58,140 --> 00:58:03,710 küsin teilt rakendada push või rakendada pop või Lisa järjekorda ja dequeue. 1050 00:58:03,710 --> 00:58:07,340 Aga enamasti, millel on mis kõrgema taseme mõistmist ja rohkem 1051 00:58:07,340 --> 00:58:09,710 intuitiivne haarata on tähtsam kui tegelikult 1052 00:58:09,710 --> 00:58:11,250 on võimalik seda rakendada. 1053 00:58:11,250 --> 00:58:14,880 >> See oleks tõesti fantastiline, kui te kõik võiks minna välja ja lähevad rakendada proovida, 1054 00:58:14,880 --> 00:58:19,720 kuid me mõistame, et see ei ole tingimata kõige mõistlikum asi kohe. 1055 00:58:19,720 --> 00:58:23,370 Aga sa võid oma pset, kui soovite üles ja siis saad tavadele 1056 00:58:23,370 --> 00:58:27,200 ja siis äkki saate tõesti aru. 1057 00:58:27,200 --> 00:58:27,940 Jah? 1058 00:58:27,940 --> 00:58:30,440 >> Sihtrühm: OK, siis millised on meil mõeldud kasutamiseks pset? 1059 00:58:30,440 --> 00:58:31,916 Kas mul on vaja kasutada üks neist? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Jah. 1061 00:58:32,540 --> 00:58:34,199 Nii et teil on oma valik. 1062 00:58:34,199 --> 00:58:36,740 Ma arvan, et sel juhul saame räägime pset natuke 1063 00:58:36,740 --> 00:58:40,480 sest ma jooksin läbi nende. 1064 00:58:40,480 --> 00:58:47,779 Nii et teie pset, kui olete oma valik üritab või hash tabeleid. 1065 00:58:47,779 --> 00:58:49,570 Mõned inimesed püüavad ja kasutada õitsema filtrid 1066 00:58:49,570 --> 00:58:51,840 kuid need on tehniliselt ei ole õige. 1067 00:58:51,840 --> 00:58:55,804 Kuna nende tõenäosuslik iseloom, nad annavad valepositiivseid mõnikord. 1068 00:58:55,804 --> 00:58:57,095 Nad on lahe uurima, kuigi. 1069 00:58:57,095 --> 00:58:59,030 Soovitame otsin neid vähemalt. 1070 00:58:59,030 --> 00:59:03,260 Aga sa pead oma valikut vahel hash tabelit ja proovida. 1071 00:59:03,260 --> 00:59:06,660 Ja see saab olema, kui laete oma sõnastikku. 1072 00:59:06,660 --> 00:59:09,230 >> Ja sa pead valima Sinu räsifunktsioon 1073 00:59:09,230 --> 00:59:13,420 peate valida mitu kopad sul on, ja see on erinev. 1074 00:59:13,420 --> 00:59:17,440 Nagu siis, kui teil on rohkem ämbrid, äkki see saab töötada kiiremini. 1075 00:59:17,440 --> 00:59:22,790 Aga võib-olla sa raiskad palju ruumi, et kuidas küll. 1076 00:59:22,790 --> 00:59:26,320 Sa pead aru saada. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> Sihtrühm: Sa ütlesid enne, et saame kasutada teiste räsifunktsioonid, 1079 00:59:29,875 --> 00:59:31,750 et me ei pea luua hash funktsiooni? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Jah, muidugi. 1081 00:59:32,666 --> 00:59:38,150 Nii et sõna otseses mõttes oma räsifunktsioon nagu google "hash funktsiooni" 1082 00:59:38,150 --> 00:59:40,770 ning otsida mõned lahedad ones. 1083 00:59:40,770 --> 00:59:43,250 Sa ei tohiks ehitada oma hash funktsiooni. 1084 00:59:43,250 --> 00:59:46,100 Inimesed veedavad teesi neid asju. 1085 00:59:46,100 --> 00:59:50,250 >> Nii et ärge muretsege hoone oma. 1086 00:59:50,250 --> 00:59:53,350 Leia ühe online alustada. 1087 00:59:53,350 --> 00:59:56,120 Mõned neist pead manipuleerida natuke 1088 00:59:56,120 --> 00:59:59,430 veenduda, tagastamise tüüpi mängu üles ja tühi-tähi, nii alguses, 1089 00:59:59,430 --> 01:00:02,420 Ma soovitaks midagi väga lihtne, et võib-olla ainult 1090 01:00:02,420 --> 01:00:04,680 hashes esimene täht. 1091 01:00:04,680 --> 01:00:08,760 Ja siis, kui sul on, et töö, sisaldavad jahedam hash funktsiooni. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> Sihtrühm: Kas proovida olla või tõhus vaid lihtsalt raskem, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Nii et proovida, ma arvan, on intuitiivselt raske rakendada 1095 01:00:15,880 --> 01:00:18,310 kuid on väga kiire. 1096 01:00:18,310 --> 01:00:20,620 Siiski võtab rohkem ruumi. 1097 01:00:20,620 --> 01:00:25,270 Jällegi saate optimeerida nii need, erineval viisil ja on võimalusi mina-- 1098 01:00:25,270 --> 01:00:26,770 Sihtrühm: Kuidas me sorteeritud selles küsimuses? 1099 01:00:26,770 --> 01:00:27,540 Kas see matter-- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Nii et te sorteeritud tavalisel viisil. 1101 01:00:29,164 --> 01:00:31,330 Sa lähed liigitatakse disaini. 1102 01:00:31,330 --> 01:00:36,020 Ükskõik kuidas sa teed, sa tahad veenduge, et see on nii elegantne kui võimalik 1103 01:00:36,020 --> 01:00:38,610 ja nii tõhus kui võimalik. 1104 01:00:38,610 --> 01:00:41,950 Aga kui te otsustate proovida või hash tabelis, kui see töötab, 1105 01:00:41,950 --> 01:00:45,350 me oleme õnnelikud, et. 1106 01:00:45,350 --> 01:00:48,370 Ja kui te kasutate midagi, et hashes esimene täht, see on hea, 1107 01:00:48,370 --> 01:00:51,410 nagu võibolla nagu disain tark. 1108 01:00:51,410 --> 01:00:53,410 Me jõudes ka punkt selles semester-- 1109 01:00:53,410 --> 01:00:55,340 Ma ei tea, kas te poisid noticed-- kui sa oled 1110 01:00:55,340 --> 01:00:58,780 pset klassid väheneb natuke sest disaini ja tühi-tähi, 1111 01:00:58,780 --> 01:00:59,900 see on täiesti trahvi. 1112 01:00:59,900 --> 01:01:02,960 Läheb punktini, kus oma programmid saavad keerulisem. 1113 01:01:02,960 --> 01:01:04,830 On enam kohtades saab parandada. 1114 01:01:04,830 --> 01:01:06,370 >> Nii et see on täiesti normaalne. 1115 01:01:06,370 --> 01:01:08,810 See ei ole, et sa oled teeb hullemaks oma pset. 1116 01:01:08,810 --> 01:01:11,885 See on lihtsalt meil on raskem nüüd. 1117 01:01:11,885 --> 01:01:13,732 Nii et igaüks end tunneb seda. 1118 01:01:13,732 --> 01:01:14,940 Ma lihtsalt liigitada kõik oma psets. 1119 01:01:14,940 --> 01:01:16,490 Ma tean, et igaüks tunneb seda. 1120 01:01:16,490 --> 01:01:19,600 >> Nii et ei muretse, et. 1121 01:01:19,600 --> 01:01:23,580 Ja kui teil on küsimusi selle kohta, enne psets või kuidas saab parandada, 1122 01:01:23,580 --> 01:01:27,760 Ma püüan ja kommenteerida konkreetseid kohad, kuid mõnikord on see hilja 1123 01:01:27,760 --> 01:01:30,840 ja ma ei väsi. 1124 01:01:30,840 --> 01:01:34,885 Kas on muid asju umbes andmestruktuuride? 1125 01:01:34,885 --> 01:01:37,510 Ma olen kindel, et te poisid tõesti ei tahan rääkida neid enam, 1126 01:01:37,510 --> 01:01:42,650 kuid kui on, ma olen õnnelik, et minna üle neile, kui ka midagi 1127 01:01:42,650 --> 01:01:45,580 alates loeng möödunud nädalal või eelmisel nädalal. 1128 01:01:45,580 --> 01:01:51,580 >> Ma tean, et eelmisel nädalal oli kõik arvustused, nii me võib-olla vahele üle mõned läbi 1129 01:01:51,580 --> 01:01:54,190 alates loeng. 1130 01:01:54,190 --> 01:01:58,230 Muid küsimusi võin vastata? 1131 01:01:58,230 --> 01:01:59,350 OK, eks. 1132 01:01:59,350 --> 01:02:02,400 Noh, kutid välja tulla 15 minutit varem. 1133 01:02:02,400 --> 01:02:08,370 >> Loodan, et see oli pooleldi kasulik vähemalt ja ma näen kutid järgmisel nädalal 1134 01:02:08,370 --> 01:02:12,150 või neljapäev tööajal. 1135 01:02:12,150 --> 01:02:15,285 Kas taotlused suupisted Järgmise nädala, see on asi? 1136 01:02:15,285 --> 01:02:17,459 Sest ma unustasin kommi täna. 1137 01:02:17,459 --> 01:02:19,750 Ja ma tõin kommid viimase nädalas, kuid see oli Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 nii oli nagu kuus inimest, kes oli neli kotti kommi ise. 1139 01:02:25,400 --> 01:02:28,820 Võin tuua Starbursts uuesti, kui soovite. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 OK, kõlab hästi. 1142 01:02:32,250 --> 01:02:35,050 Ilusat päeva, poisid. 1143 01:02:35,050 --> 01:02:39,510