1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Мусиц плаиинг] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> ДАВИД Малан: Ово је ЦС50. 5 00:00:14,010 --> 00:00:18,090 А ово је и почетак и енд-- као литералли-- скоро крај 6 00:00:18,090 --> 00:00:18,825 од недеље шест. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Мислио сам да поделим помало смешне чињенице. 9 00:00:22,640 --> 00:00:25,370 Ја сам извукао ово из Подаци прошлогодишњег семестра сет. 10 00:00:25,370 --> 00:00:29,710 Ви се сећате да смо вас на сваки стр скуп образац ако сте гледали на мрежи 11 00:00:29,710 --> 00:00:31,580 или ако сте присуствовали лично. 12 00:00:31,580 --> 00:00:33,020 А ту су подаци. 13 00:00:33,020 --> 00:00:34,710 Дакле, данас је веома предвидљив. 14 00:00:34,710 --> 00:00:37,126 Али смо хтели да проведемо мало времена са тобом ипак. 15 00:00:37,126 --> 00:00:40,599 Да ли би ико желео да претпоставити зашто је то граф је тако Јагги, горе доле, горе доле, 16 00:00:40,599 --> 00:00:41,265 тако доследно? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Шта сваки од врхова и корита представљају? 19 00:00:45,130 --> 00:00:46,005 >> ПУБЛИКА: [неразумљиво] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 ДАВИД Малан: Заиста. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 И још забавно, не дај Боже, држимо једно предавање у петак 24 00:00:55,480 --> 00:00:58,960 на почетку семестра, то је оно што смо видели да се дешава. 25 00:00:58,960 --> 00:01:03,430 Тако да данас, ми учествују у мало више о структурама података. 26 00:01:03,430 --> 00:01:06,660 И да вам више добар ментални модел за проблеме у пет, 27 00:01:06,660 --> 00:01:07,450 која је сада ван. 28 00:01:07,450 --> 00:01:10,817 Грешке, при чему, ћемо рука коју текстуалну датотеку око 100.000 29 00:01:10,817 --> 00:01:12,650 Плус енглеске речи, и ћеш имати 30 00:01:12,650 --> 00:01:17,770 да смислим како да паметно их учита у меморију, у РАМ, користећи неке податке 31 00:01:17,770 --> 00:01:19,330 Структура по вашем избору. 32 00:01:19,330 --> 00:01:22,470 >> Сада један такав структура података могао да буде, али вероватно не би требало да буде, 33 00:01:22,470 --> 00:01:25,630 прилично поједностављено линкед лист, које смо увели прошли пут. 34 00:01:25,630 --> 00:01:29,220 И линкед лист имао најмање једна предност у односу на низ. 35 00:01:29,220 --> 00:01:32,096 Шта је једна предност линкед лист вероватно? 36 00:01:32,096 --> 00:01:32,950 >> ПУБЛИКА: Уношење. 37 00:01:32,950 --> 00:01:33,908 >> ДАВИД Малан: Уношење. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Шта сте под тим мислили? 40 00:01:35,196 --> 00:01:37,872 >> ПУБЛИКА: било где дуж Листа [неразумљиво]. 41 00:01:37,872 --> 00:01:38,770 >> ДАВИД Малан: Добро. 42 00:01:38,770 --> 00:01:42,090 Тако да можете да убаците елемент где год желите у средини листе 43 00:01:42,090 --> 00:01:45,490 без схуффле ништа, које смо закључили, у нашем сортирање 44 00:01:45,490 --> 00:01:47,630 дискусије, није нужно добра ствар, 45 00:01:47,630 --> 00:01:51,200 јер је потребно време да се ствари крећу све те људи лево или десно. 46 00:01:51,200 --> 00:01:55,540 И тако са повезане листе, можете Само издвојити са маллоц, нови чвор, 47 00:01:55,540 --> 00:01:58,385 а потом ажурирати неколико поинтерс-- два, три операције мак-- 48 00:01:58,385 --> 00:02:01,480 и ми смо у стању да некога слот нигде у листи. 49 00:02:01,480 --> 00:02:03,550 >> Шта друго је предност о повезане листе? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Да? 52 00:02:05,659 --> 00:02:06,534 >> ПУБЛИКА: [неразумљиво] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 ДАВИД Малан: Савршено. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Савршено. 57 00:02:11,090 --> 00:02:12,070 То је заиста динамичан. 58 00:02:12,070 --> 00:02:15,100 А да ти не чињење, унапред, до неке фиксне величине 59 00:02:15,100 --> 00:02:18,750 комад меморије, као да би се да са низа, Тхе Упсиде оф којих 60 00:02:18,750 --> 00:02:22,455 је да можете доделити чворова само потражња тиме користи само онолико простора 61 00:02:22,455 --> 00:02:23,330 као што сте стварно потребно. 62 00:02:23,330 --> 00:02:26,830 Насупрот низа, да би могао Случајно издвојити премало. 63 00:02:26,830 --> 00:02:28,871 А онда се само иде да се бол у врату 64 00:02:28,871 --> 00:02:32,440 прерасподелу нову већу низ, цопи све више, ослободи старог низ, 65 00:02:32,440 --> 00:02:33,990 а затим преместите својим послом. 66 00:02:33,990 --> 00:02:37,479 Или још горе, можда издвоји пут више меморије него што заиста потребно, 67 00:02:37,479 --> 00:02:40,520 па ћеш имати веома слабо насељене низ, да тако кажем. 68 00:02:40,520 --> 00:02:44,350 >> Дакле, повезана листа даје ово Предности динамичност и флексибилност 69 00:02:44,350 --> 00:02:46,080 са умецима и брисања. 70 00:02:46,080 --> 00:02:48,000 Али сигурно мора бити плаћена цена. 71 00:02:48,000 --> 00:02:50,000 У ствари, једна од тема истражили на квизу нула 72 00:02:50,000 --> 00:02:52,430 је пар на уступке смо видели до сада. 73 00:02:52,430 --> 00:02:56,161 Дакле, шта је цена плаћена или Лоша повезане листе? 74 00:02:56,161 --> 00:02:56,660 Да. 75 00:02:56,660 --> 00:02:57,560 >> ПУБЛИКА: Не директног приступа. 76 00:02:57,560 --> 00:02:58,809 >> ДАВИД Малан: Нема директног приступа. 77 00:02:58,809 --> 00:02:59,540 Али кога је брига? 78 00:02:59,540 --> 00:03:01,546 Рандом аццесс не звучи убедљиво. 79 00:03:01,546 --> 00:03:02,421 >> ПУБЛИКА: [неразумљиво] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 ДАВИД Малан: Тачно. 82 00:03:05,740 --> 00:03:07,580 Ако желите да имате одређена алгоритхм-- 83 00:03:07,580 --> 00:03:10,170 и пусти ме заправо предлаже бинарни претрага посебно, којој 84 00:03:10,170 --> 00:03:12,600 је једна смо користили доста бит-- Ако немате случајан приступ, 85 00:03:12,600 --> 00:03:15,516 Ви не можете то урадити Једноставна математика налажења попут средњег елемента 86 00:03:15,516 --> 00:03:16,530 и скакање право на њу. 87 00:03:16,530 --> 00:03:20,239 Уместо тога морају да почну у прва елемент и линеарно претраживање од лева 88 00:03:20,239 --> 00:03:22,780 на десно ако желите да пронађете средње или било који други елемент. 89 00:03:22,780 --> 00:03:24,410 >> ПУБЛИКА: Вероватно се више меморије. 90 00:03:24,410 --> 00:03:25,040 >> ДАВИД Малан: потребно је више меморије. 91 00:03:25,040 --> 00:03:27,464 Где је тај додатни коштају из меморије? 92 00:03:27,464 --> 00:03:28,339 >> ПУБЛИКА: [неразумљиво] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 ДАВИД Малан: Тачно. 95 00:03:33,440 --> 00:03:35,679 У том случају овде, имали смо повезана листа за целих бројева, 96 00:03:35,679 --> 00:03:37,470 а ипак смо дуплирање количина меморије 97 00:03:37,470 --> 00:03:39,680 морамо по и чување ових савета. 98 00:03:39,680 --> 00:03:42,090 Сада мање велику ствар као Ваши Структуре гет већи 99 00:03:42,090 --> 00:03:45,320 а ви чување није број, али Можда студент или неки други предмет. 100 00:03:45,320 --> 00:03:46,880 Али поента сигурно остаје. 101 00:03:46,880 --> 00:03:49,421 И тако број операција на повезаним листама су се звали 102 00:03:49,421 --> 00:03:50,570 били Биг О на н-- линеарни. 103 00:03:50,570 --> 00:03:54,730 Ствари као што су убацивање или претреса или брисање у случају елемент 104 00:03:54,730 --> 00:03:57,720 Десило се да на самом крају списак било да је сортирана или не. 105 00:03:57,720 --> 00:04:01,167 >> Понекад можете имати среће и па ниже границе на овим пословима 106 00:04:01,167 --> 00:04:04,250 може такође бити константна времена ако си увек гледа у првом елементу, 107 00:04:04,250 --> 00:04:05,070 на пример. 108 00:04:05,070 --> 00:04:09,360 Али на крају, обећао ми да се постигне Свети грал 109 00:04:09,360 --> 00:04:12,630 структура података, или неке апроксимације него, 110 00:04:12,630 --> 00:04:14,290 путем константне времена. 111 00:04:14,290 --> 00:04:17,579 Можемо ли наћи елементе или додати елементе или уклањање елемената са листе? 112 00:04:17,579 --> 00:04:19,059 Видећемо ускоро. 113 00:04:19,059 --> 00:04:21,100 И испоставило се да је један механизама смо 114 00:04:21,100 --> 00:04:23,464 ће почети да користе и данас, годишња потрошња у п сет пет, 115 00:04:23,464 --> 00:04:24,630 је заправо прилично познато. 116 00:04:24,630 --> 00:04:27,430 На пример, ако је ово гомила испитних књига, од којих 117 00:04:27,430 --> 00:04:29,660 има ученик прво име и презиме на њој, 118 00:04:29,660 --> 00:04:31,820 и ја их покупити из на крају испита, 119 00:04:31,820 --> 00:04:33,746 и они су сви прилично много у случајним редоследом, 120 00:04:33,746 --> 00:04:36,370 и ми желимо да идемо око сортирања Ови испити тако да када оцењује 121 00:04:36,370 --> 00:04:38,661 то је само много лакше и брже да их предају натраг 122 00:04:38,661 --> 00:04:40,030 студентима по абецедном реду. 123 00:04:40,030 --> 00:04:42,770 Шта би твој инстикт се за гомилу испита оваквим? 124 00:04:42,770 --> 00:04:45,019 >> Па, ако сте попут мене, можда ћете видети да је ово м, 125 00:04:45,019 --> 00:04:48,505 па ћу некако стави ово у, Ако је ово је мој сто или мој спрат, где 126 00:04:48,505 --> 00:04:50,650 Ја ширење ствари оут-- или моје низ стварно-- 127 00:04:50,650 --> 00:04:52,210 Можда ставио све МС тамо. 128 00:04:52,210 --> 00:04:52,710 Ох. 129 00:04:52,710 --> 00:04:55,020 Ево О Тако сам могао пут АС овде. 130 00:04:55,020 --> 00:04:55,520 Ох. 131 00:04:55,520 --> 00:04:57,980 Ево још једног О идем ставити то овде. 132 00:04:57,980 --> 00:05:02,490 Ево, З. Ево је још једна М. и тако Можда почети израду гомиле овако. 133 00:05:02,490 --> 00:05:06,620 А онда можда бих ићи у касније и на неки начин веома изненадило-ЛИ Сортирај 134 00:05:06,620 --> 00:05:07,710 појединачне шипова. 135 00:05:07,710 --> 00:05:11,300 Али поента је да би изгледала на улазу да сам руку 136 00:05:11,300 --> 00:05:14,016 и ја би мало израчунати Одлука на основу те улаза. 137 00:05:14,016 --> 00:05:15,640 Ако се почиње са, га ставио тамо. 138 00:05:15,640 --> 00:05:18,980 Ако се почиње са З, ставите га преко тамо, и све између. 139 00:05:18,980 --> 00:05:22,730 >> Дакле, ово је техника која је генерално познати као хасхинг-- Х-А-С-Х-- 140 00:05:22,730 --> 00:05:26,550 који обично значи узимање у улаз и коришћење ИНПУТ израчунати 141 00:05:26,550 --> 00:05:30,940 вредност, генерално број и то број је индекс у складиште 142 00:05:30,940 --> 00:05:32,260 контејнер, као низа. 143 00:05:32,260 --> 00:05:35,490 Другим речима, ја можда има хасх функција, као ја у мојој глави, 144 00:05:35,490 --> 00:05:37,940 да ако видим да је неко Назив који почиње, 145 00:05:37,940 --> 00:05:40,190 Ја ћу се карта која на нулу у мојој глави. 146 00:05:40,190 --> 00:05:44,160 И ако видим некога са З, ја сам ће карта која до 25. у мојој глави 147 00:05:44,160 --> 00:05:46,220 а затим ставити у последњи највише гомила. 148 00:05:46,220 --> 00:05:50,990 >> Сада, ако мислите о томе да не мој мозак али Ц програм, какве бројке 149 00:05:50,990 --> 00:05:53,170 се ослоните на постизање тог истог резултата? 150 00:05:53,170 --> 00:05:55,594 Другим речима, ако вам имао АСЦИИ цхарацтер, 151 00:05:55,594 --> 00:05:57,510 како одредити шта кашика да га ставите у? 152 00:05:57,510 --> 00:05:59,801 Вероватно не желите да ставите га у кофу 65, који 153 00:05:59,801 --> 00:06:01,840 би било тамо без икаквог разлога. 154 00:06:01,840 --> 00:06:04,320 Где желиш да ставим у смислу његове АСЦИИ вредности? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Где желите да урадите са својим АСЦИИ вриједност смислити паметнији кашиком 157 00:06:08,920 --> 00:06:09,480 да га ставите у? 158 00:06:09,480 --> 00:06:10,206 >> ПУБЛИКА: Минус А. 159 00:06:10,206 --> 00:06:10,956 >> ДАВИД Малан: Да. 160 00:06:10,956 --> 00:06:13,190 Дакле минус или минус конкретно 65 ако је 161 00:06:13,190 --> 00:06:18,240 О капитала или 98 ако то мала слова. 162 00:06:18,240 --> 00:06:21,300 И да би нас омогућити да, веома једноставно и врло аритметички, 163 00:06:21,300 --> 00:06:23,260 ставити нешто у канту тако. 164 00:06:23,260 --> 00:06:26,010 Тако испада да у ствари радимо и ово чак и уз квизове. 165 00:06:26,010 --> 00:06:29,051 >> Дакле, можда се сећате сте заокружили ваше Име демонстратор је на насловној страни. 166 00:06:29,051 --> 00:06:32,270 И имена ТФ биле су организоване у ове колоне по абецедном реду, 167 00:06:32,270 --> 00:06:34,400 Па, веровали или не, када сви 80 ПЛУС нас 168 00:06:34,400 --> 00:06:37,800 окупили друга ноћ разред, последњи корак у нашем процесу оцењивања 169 00:06:37,800 --> 00:06:41,830 је да се емитују квизове у велики простор пода на [неразумљиво] 170 00:06:41,830 --> 00:06:45,110 и да постави свачијим квизове се у потпуно налогу својих ТФ-их 171 00:06:45,110 --> 00:06:47,700 Имена на поклопцу, јер онда је много лакше за нас 172 00:06:47,700 --> 00:06:51,290 да тражи кроз тај користећи линеарну претраживање или нека врста интелигенције 173 00:06:51,290 --> 00:06:54,050 за ТФ да нађете њену или својих ученика тестовима. 174 00:06:54,050 --> 00:06:56,060 >> Дакле, та идеја о хеширање да ћете видети је 175 00:06:56,060 --> 00:07:00,520 веома моћан је заправо прилично уобичајена и веома интуитиван, 176 00:07:00,520 --> 00:07:03,000 слично можда деле и цонкуер је у недељу нула. 177 00:07:03,000 --> 00:07:05,250 Ја брзо напред у Хацкатхон Пре пар година. 178 00:07:05,250 --> 00:07:08,040 То је био и Замила пар Остали студенти особље греетинг 179 00:07:08,040 --> 00:07:09,030 како су дошли. 180 00:07:09,030 --> 00:07:12,680 И ми смо имали гомилу савијања столови постоје са именима. 181 00:07:12,680 --> 00:07:15,380 А имали смо име ознаке организовани са као и преко тамо 182 00:07:15,380 --> 00:07:16,690 а Зс тамо. 183 00:07:16,690 --> 00:07:20,350 И тако један од веома паметно Поздрав ово написао као упутства 184 00:07:20,350 --> 00:07:21,030 за дан. 185 00:07:21,030 --> 00:07:24,480 И у 12. недељи семестра ове све је савршено логично и свима 186 00:07:24,480 --> 00:07:25,310 знао шта да радим. 187 00:07:25,310 --> 00:07:27,900 Али кад год сам куеуед на исти начин, 188 00:07:27,900 --> 00:07:30,272 сте имплементацију Исти појам хашиша. 189 00:07:30,272 --> 00:07:31,730 Па хајде да га мало озваничи. 190 00:07:31,730 --> 00:07:32,890 Ево низ. 191 00:07:32,890 --> 00:07:36,820 Је привукло да буде мало широка само да прикаже, визуелно, 192 00:07:36,820 --> 00:07:38,920 да би ми ставили жице у овако нешто. 193 00:07:38,920 --> 00:07:41,970 А ово је низ јасно величине 26 укупно. 194 00:07:41,970 --> 00:07:43,935 А ствар се зове Табела произвољно. 195 00:07:43,935 --> 00:07:48,930 Али ово је само уметника излагање шта може бити хасх табела. 196 00:07:48,930 --> 00:07:52,799 >> Дакле хасх табела сада ће се бити виши ниво структура података. 197 00:07:52,799 --> 00:07:54,840 На крају дана ћемо ускоро видети да сте 198 00:07:54,840 --> 00:07:58,700 може имплементирати хеш табели, која је много као цхецк-ин лине 199 00:07:58,700 --> 00:08:02,059 на Хацкатхон много као што је овај сто за сортирање испит књига. 200 00:08:02,059 --> 00:08:03,850 Али хасх сто је врста овог високог нивоа 201 00:08:03,850 --> 00:08:08,250 Концепт да користи низ испод капуљача да га спроведу, 202 00:08:08,250 --> 00:08:11,890 или би могло користити листу дужине, или чак можда неке друге структуре података. 203 00:08:11,890 --> 00:08:15,590 И сада када је тхеме-- узимање неке од ових основних састојака 204 00:08:15,590 --> 00:08:18,310 као низ и овој згради блок сада на листи дужине 205 00:08:18,310 --> 00:08:21,740 и видимо шта још можемо да градимо на врху оних, као што састојака 206 00:08:21,740 --> 00:08:26,550 у рецепту, што више занимљиво и корисно коначни резултати. 207 00:08:26,550 --> 00:08:28,680 >> Тако је и са хеш табели бисмо могли да га спроведе 208 00:08:28,680 --> 00:08:32,540 у меморији сликовито овако, али Како би то заиста бити кодирани горе? 209 00:08:32,540 --> 00:08:33,789 Па, можда јер једноставно је то. 210 00:08:33,789 --> 00:08:38,270 Уколико капацитети у свим капе, само неки цонстант-- на пример 26, 211 00:08:38,270 --> 00:08:42,030 за 26 слова у алпхабет-- Можда зовем вариабле сто, 212 00:08:42,030 --> 00:08:45,630 и ја могу да тврдим да ћу се стави цхар звезде унутра, или стринг. 213 00:08:45,630 --> 00:08:49,880 Дакле, то је једноставно као ово ако желе да спроведу хеш табели. 214 00:08:49,880 --> 00:08:51,490 А ипак, то је заиста само низ. 215 00:08:51,490 --> 00:08:53,198 Али опет, хасх сто је сада оно што ћемо 216 00:08:53,198 --> 00:08:57,470 позовите апстрактни тип података, то је само врста концептуалног раслојавања на врху 217 00:08:57,470 --> 00:09:00,780 нечега више земаљском Сада се свиђа низ. 218 00:09:00,780 --> 00:09:02,960 >> Сада, како да идемо о решавању проблема? 219 00:09:02,960 --> 00:09:06,980 Па, раније сам имала тај луксуз да имају довољно простора табеле овде 220 00:09:06,980 --> 00:09:09,460 тако да сам могао ставити квизови нигде сам хтео. 221 00:09:09,460 --> 00:09:10,620 Како да одемо одавде. 222 00:09:10,620 --> 00:09:12,100 Зс Можда иду овде. 223 00:09:12,100 --> 00:09:13,230 МС можда иду овде. 224 00:09:13,230 --> 00:09:14,740 И онда сам имао неку додатни простор. 225 00:09:14,740 --> 00:09:18,740 Али ово је мало варалица права сада, јер ове табеле, ако стварно 226 00:09:18,740 --> 00:09:22,720 пало на памет као низ, само ће бити од неке фиксне величине. 227 00:09:22,720 --> 00:09:25,380 >> Технички, ако повучем до квизу другог студента 228 00:09:25,380 --> 00:09:28,490 и види, ох, та особа је име почиње са А такође, 229 00:09:28,490 --> 00:09:30,980 Ја сам хтео да га ставим тамо. 230 00:09:30,980 --> 00:09:34,740 Али чим сам га ставио тамо, ако Ова табела заиста представља низ, 231 00:09:34,740 --> 00:09:37,840 Ја ћу бити најважнији или цлобберинг Ко год квиз овог ученика је. 232 00:09:37,840 --> 00:09:38,340 Зар не? 233 00:09:38,340 --> 00:09:41,972 Ако је ово низ, само једна ствар може ићи у сваком од ових ћелија или елемената. 234 00:09:41,972 --> 00:09:43,680 И тако ја некако имам да бираш. 235 00:09:43,680 --> 00:09:45,735 >> Сада раније некако варао и урадио ово или ја 236 00:09:45,735 --> 00:09:47,526 некако сложен њих изнад другога. 237 00:09:47,526 --> 00:09:49,170 Али то неће летети у коду. 238 00:09:49,170 --> 00:09:52,260 Па где сам могао ставити Други ученик чије име 239 00:09:52,260 --> 00:09:54,964 је да све што сам имала је ово доступно Табела простор? 240 00:09:54,964 --> 00:09:57,880 И ја сам користио три слота и ИТ Изгледа као да је само неколико других. 241 00:09:57,880 --> 00:09:58,959 Шта би ти урадио? 242 00:09:58,959 --> 00:09:59,834 ПУБЛИКА: [неразумљиво] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 ДАВИД Малан: Да. 245 00:10:01,315 --> 00:10:02,370 Можда хајде да буде једноставно. 246 00:10:02,370 --> 00:10:02,660 Зар не? 247 00:10:02,660 --> 00:10:04,243 То не одговара где желим да га ставим. 248 00:10:04,243 --> 00:10:07,450 Дакле, ја ћу да га ставим Технички где Б ће ићи. 249 00:10:07,450 --> 00:10:09,932 Сада, наравно, ја почињем да се сликам у ћошак. 250 00:10:09,932 --> 00:10:11,890 Ако дођем до студента чије име је заправо Б, 251 00:10:11,890 --> 00:10:14,840 Сада Б биће померен мало напред, као што се може догодити, Иеп, 252 00:10:14,840 --> 00:10:17,530 ако је Б, сада мора да иде овде. 253 00:10:17,530 --> 00:10:20,180 >> И то веома брзо могао да постане проблематично, 254 00:10:20,180 --> 00:10:23,850 али је техника која заправо је означена као линеарни прескок, 255 00:10:23,850 --> 00:10:26,650 при чему само у обзир ваше арраи да буду дуж линије. 256 00:10:26,650 --> 00:10:29,680 А ти некако пробе или прегледати сваки расположиви елемент 257 00:10:29,680 --> 00:10:31,360 потрази за доступном месту. 258 00:10:31,360 --> 00:10:34,010 И чим нађете један, ти га баци тамо. 259 00:10:34,010 --> 00:10:38,390 >> Сада, цена се сада плаћа за ово решење је шта? 260 00:10:38,390 --> 00:10:41,300 Имамо одређену величину низ, а кад убаците имена 261 00:10:41,300 --> 00:10:44,059 у њега, бар у почетку, што је руннинг време убацивања 262 00:10:44,059 --> 00:10:46,350 за стављање ученичких квизови у правим кашике? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Биг О чега? 265 00:10:50,002 --> 00:10:51,147 >> ПУБЛИКА: н. 266 00:10:51,147 --> 00:10:52,480 ДАВИД Малан: Чуо сам Биг О н. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Није истина. 269 00:10:54,300 --> 00:10:56,490 Али ми ћемо задиркују Апарт Зашто се само тренутак. 270 00:10:56,490 --> 00:10:57,702 Шта друго може да буде? 271 00:10:57,702 --> 00:10:58,755 >> ПУБЛИКА: [неразумљиво] 272 00:10:58,755 --> 00:11:00,380 ДАВИД Малан: И дозволите ми да то урадим визуелно. 273 00:11:00,380 --> 00:11:04,720 Претпостављам да је ово писмо С. 274 00:11:04,720 --> 00:11:05,604 >> ПУБЛИКА: То је један. 275 00:11:05,604 --> 00:11:06,520 ДАВИД Малан: То је један. 276 00:11:06,520 --> 00:11:06,710 Зар не? 277 00:11:06,710 --> 00:11:08,950 То је низ, који значи да имамо случајан приступ. 278 00:11:08,950 --> 00:11:11,790 И ако мислимо ово као нуле и то као 25, 279 00:11:11,790 --> 00:11:13,800 и ми схватамо да, Ох, овде је мој улаз С, 280 00:11:13,800 --> 00:11:16,350 Ја свакако могу претворити С, АСЦИИ знак, 281 00:11:16,350 --> 00:11:18,540 на одговарајућим бројем између нула и 25 282 00:11:18,540 --> 00:11:20,910 и онда одмах ставите га тамо где припада. 283 00:11:20,910 --> 00:11:26,120 >> Али, наравно, чим стигнем у Друга особа која се зове или Б или Ц 284 00:11:26,120 --> 00:11:29,300 на крају, ако сам се користи линеарни прескок као мој решење, 285 00:11:29,300 --> 00:11:31,360 руннинг време убацивање у најгорем случају 286 00:11:31,360 --> 00:11:33,120 заправо ће да се пренесе у шта? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 И ја сам чуо овде правилно рано. 289 00:11:36,045 --> 00:11:36,920 ПУБЛИКА: [неразумљиво] 290 00:11:36,920 --> 00:11:41,620 ДАВИД Малан: Дакле, то је заиста једном н имате довољно велики скуп података. 291 00:11:41,620 --> 00:11:44,410 Дакле, с једне стране, ако Ваш низ је довољно велики 292 00:11:44,410 --> 00:11:48,287 и ваши подаци су ретки довољно, добили прелепу сталну пут. 293 00:11:48,287 --> 00:11:50,620 Али чим почнете све више и више елемената, 294 00:11:50,620 --> 00:11:53,200 и само статистички добијате више људи са словом 295 00:11:53,200 --> 00:11:56,030 Као њихово име или слово Б, то потенцијално могао 296 00:11:56,030 --> 00:11:57,900 пренесе у нешто линеарно. 297 00:11:57,900 --> 00:11:59,640 Дакле, не баш савршен. 298 00:11:59,640 --> 00:12:00,690 Тако да смо могли боље? 299 00:12:00,690 --> 00:12:03,210 >> Па, шта је наш решење пре Вхен Ве 300 00:12:03,210 --> 00:12:06,820 Желим да имају више од динамичности нешто попут низа дозвољено? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 ПУБЛИКА: [неразумљиво] 303 00:12:08,960 --> 00:12:10,030 ДАВИД Малан: Шта смо представити? 304 00:12:10,030 --> 00:12:10,530 Да. 305 00:12:10,530 --> 00:12:11,430 Дакле, повезана листа. 306 00:12:11,430 --> 00:12:14,430 Па, хајде да видимо шта повезан Листа може да уради за нас, уместо. 307 00:12:14,430 --> 00:12:17,630 Па, дозволите ми да предлажем да нацртати слику на следећи начин. 308 00:12:17,630 --> 00:12:19,620 Сада је ово другачије Слика од примера 309 00:12:19,620 --> 00:12:24,750 из другог текста, заправо, да се је заправо користи низ величине 31. 310 00:12:24,750 --> 00:12:28,220 И овај аутор једноставно одлучили да размотре жице 311 00:12:28,220 --> 00:12:32,430 а не на основу имена те особе, али на основу њихових Биртхдатес. 312 00:12:32,430 --> 00:12:35,680 Без обзира на месецу, они схватили Ако сте рођени на први месец 313 00:12:35,680 --> 00:12:39,580 или 31. у месецу, аутор ће хасх основу те вредности, 314 00:12:39,580 --> 00:12:44,154 како би проширила имена напоље мало више од 26 тачака може да дозволи. 315 00:12:44,154 --> 00:12:47,320 И можда је мало више униформа него иде са словима абецеде, 316 00:12:47,320 --> 00:12:50,236 јер наравно, вероватно постоји више људи у свету са именима 317 00:12:50,236 --> 00:12:54,020 које почињу са него сигурно неки други слова азбуке. 318 00:12:54,020 --> 00:12:56,380 Дакле, можда је мало равномерније, претпостављајући 319 00:12:56,380 --> 00:12:58,640 равномернија беба широм месец дана. 320 00:12:58,640 --> 00:12:59,990 >> Али, наравно, то је још увек несавршен. 321 00:12:59,990 --> 00:13:00,370 Зар не? 322 00:13:00,370 --> 00:13:01,370 Имамо судара. 323 00:13:01,370 --> 00:13:04,680 Више људи на ово структура података и даље 324 00:13:04,680 --> 00:13:08,432 имају исту датум рођења најмање ви сте без обзира на месецу. 325 00:13:08,432 --> 00:13:09,640 Али шта је аутор урадио? 326 00:13:09,640 --> 00:13:13,427 Па, изгледа да имамо низ Са леве стране повучене вертикално, 327 00:13:13,427 --> 00:13:15,010 али то је само уметника излагање. 328 00:13:15,010 --> 00:13:18,009 Није битно шта смеру драв низ, ипак је низ. 329 00:13:18,009 --> 00:13:20,225 Шта је ово низ наизглед? 330 00:13:20,225 --> 00:13:21,500 >> ПУБЛИКА: повезане листе. 331 00:13:21,500 --> 00:13:21,650 >> ДАВИД Малан: Да. 332 00:13:21,650 --> 00:13:23,490 Изгледа као да је низ повезане листе. 333 00:13:23,490 --> 00:13:26,490 Дакле, поново, до овог становишта врсту коришћења ових структура података сада 334 00:13:26,490 --> 00:13:28,550 као састојци за више занимљивих решења, 335 00:13:28,550 --> 00:13:30,862 апсолутно може да фундаментална, као низ, 336 00:13:30,862 --> 00:13:33,320 а онда се нешто више Интересантно као повезане листе 337 00:13:33,320 --> 00:13:36,660 па чак и да их комбинујете у још занимљивији структура података. 338 00:13:36,660 --> 00:13:39,630 И заиста, и ово би може назвати хеш табели, 339 00:13:39,630 --> 00:13:42,610 при чему је низ Заиста хасх табела, 340 00:13:42,610 --> 00:13:45,600 али да хасх табела има ланци, да тако кажем, 341 00:13:45,600 --> 00:13:50,220 која може да расте или смањити на основу број елемената желите да убаците. 342 00:13:50,220 --> 00:13:52,990 >> Сада, у складу са тим, шта је време ради сада? 343 00:13:52,990 --> 00:13:58,030 Ако желим да убаците неког чији рођендан је 31. октобар, 344 00:13:58,030 --> 00:13:59,040 где се он или она оде? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 У реду. 347 00:14:01,030 --> 00:14:02,819 На самом дну, где пише 31. 348 00:14:02,819 --> 00:14:03,610 И то је савршено. 349 00:14:03,610 --> 00:14:05,060 То је био константан време. 350 00:14:05,060 --> 00:14:08,760 Али, шта ако нађемо неког другог чији је рођендан, хајде да видимо, 351 00:14:08,760 --> 00:14:10,950 Октобар, новембар, децембар 31? 352 00:14:10,950 --> 00:14:12,790 Где је он или она ће ићи? 353 00:14:12,790 --> 00:14:13,290 Иста ствар. 354 00:14:13,290 --> 00:14:13,970 Тво Степ ипак. 355 00:14:13,970 --> 00:14:15,303 То је константна мада, зар не? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 У реду. 358 00:14:16,860 --> 00:14:17,840 У овом тренутку је. 359 00:14:17,840 --> 00:14:20,570 Али у општем случају, Што више људи саберемо, 360 00:14:20,570 --> 00:14:23,790 пробабилистицалли, идемо да се све више судара. 361 00:14:23,790 --> 00:14:26,820 >> Сада ово је мало боље јер техницки 362 00:14:26,820 --> 00:14:34,580 Сада моји ланци могу бити у најгори случај Колико дуго? 363 00:14:34,580 --> 00:14:38,890 Ако сам инсерт н људе у ово више софистицирана структура података, н људи, 364 00:14:38,890 --> 00:14:41,080 У најгорем случају то ће бити н. 365 00:14:41,080 --> 00:14:41,815 Зашто? 366 00:14:41,815 --> 00:14:43,332 >> ПУБЛИКА: Јер ако сви има исти рођендан, 367 00:14:43,332 --> 00:14:44,545 они ће бити једна линија. 368 00:14:44,545 --> 00:14:45,420 ДАВИД Малан: Савршено. 369 00:14:45,420 --> 00:14:47,480 То може бити мало неприродно, али заиста у најгорем случају, 370 00:14:47,480 --> 00:14:50,117 ако свако има исти рођендан, имајући у виду улаза имате, 371 00:14:50,117 --> 00:14:51,950 ћеш имати масовно дугог ланца. 372 00:14:51,950 --> 00:14:54,241 И тако, можете га је назвати хасх табеле, али стварно је 373 00:14:54,241 --> 00:14:56,810 само масивна повезана листа са много изгубљеног простора. 374 00:14:56,810 --> 00:15:00,460 Али генерално, ако претпоставимо да најмање рођендани су униформ-- 375 00:15:00,460 --> 00:15:01,750 а вероватно није. 376 00:15:01,750 --> 00:15:02,587 Правим то. 377 00:15:02,587 --> 00:15:04,420 Али ако претпоставимо, за ради дискусије 378 00:15:04,420 --> 00:15:07,717 да су, затим у теорији, уколико ово је вертикална заступљеност 379 00:15:07,717 --> 00:15:11,050 низа, па онда надам се да си ће добити ланце који су, знате, 380 00:15:11,050 --> 00:15:15,880 отприлике исте дужине где сваки од ово представља дан у месецу. 381 00:15:15,880 --> 00:15:19,930 >> Сада ако има 31 дана у месецу, то значи да моје време рада стварно 382 00:15:19,930 --> 00:15:25,230 је Биг О од н преко 31, који осећа боље него линеарни. 383 00:15:25,230 --> 00:15:27,950 Али оно што је био један од наших Обавезе пар недеља 384 00:15:27,950 --> 00:15:31,145 Пре кад год је дошло до изражавања руннинг тиме алгоритма? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Само само погледајте високог реда року. 387 00:15:35,190 --> 00:15:35,690 Зар не? 388 00:15:35,690 --> 00:15:37,400 31 је дефинитивно помоћи. 389 00:15:37,400 --> 00:15:39,610 Али то је још увек велика о н. 390 00:15:39,610 --> 00:15:41,730 Али једна од тема проблема сет пет 391 00:15:41,730 --> 00:15:43,950 ће бити признају да апсолутно, 392 00:15:43,950 --> 00:15:47,320 асимптотикески, теоретски Ова структура података 393 00:15:47,320 --> 00:15:50,470 није ништа боље него само једна масивна линкед лист. 394 00:15:50,470 --> 00:15:53,550 И заиста, у најгорем случају, ова хасх табела може пренијети у то. 395 00:15:53,550 --> 00:15:57,620 >> Али у стварном свету, са нама људи да сопственим ПЦ или ПЦ или како год 396 00:15:57,620 --> 00:16:01,240 и трче стварни свет програме на стварним подацима, 397 00:16:01,240 --> 00:16:03,260 који алгоритам ћеш да волите? 398 00:16:03,260 --> 00:16:09,180 Онај који има крајње кораке или онај који је н подељен 31 корака 399 00:16:09,180 --> 00:16:12,900 наћи неки комад података или да потражите неке информације? 400 00:16:12,900 --> 00:16:16,580 Мислим, апсолутно 31 марки разлика у стварном свету. 401 00:16:16,580 --> 00:16:18,540 То је 31 пута брже. 402 00:16:18,540 --> 00:16:20,880 И ми људи су свакако ће ценити то. 403 00:16:20,880 --> 00:16:23,004 >> Тако схвате дихотомију тамо између ствари 404 00:16:23,004 --> 00:16:25,920 говоримо о стварима теоретски и асимптотски које дефинитивно 405 00:16:25,920 --> 00:16:28,760 има вредност као што смо видели, али у стварном свету, 406 00:16:28,760 --> 00:16:32,930 Ако вам је стало само што Хуман срећан за опште улаза, 407 00:16:32,930 --> 00:16:36,010 можда врло добро желе да прихвате чињеница да, да, ово је линеарна, 408 00:16:36,010 --> 00:16:38,360 али је 31 пута бржи него што може бити линеарна. 409 00:16:38,360 --> 00:16:41,610 И још боље, ми не само да нешто произвољно као датум рођења, 410 00:16:41,610 --> 00:16:44,030 бисмо могли провести мало више времена и памети 411 00:16:44,030 --> 00:16:47,140 и размислите о томе шта бисмо могли да урадимо, дато име особе и можда 412 00:16:47,140 --> 00:16:50,130 њихова рођења комбиновати онима састојци да схватим нешто 413 00:16:50,130 --> 00:16:52,720 то је заиста више униформу и мање Јагги, 414 00:16:52,720 --> 00:16:56,250 такорећи од овој слици Тренутно сугерише да би могло бити. 415 00:16:56,250 --> 00:16:57,750 Како можемо имплементирати ово код? 416 00:16:57,750 --> 00:17:00,280 Па, дозволите ми да предлажем да позајмимо мало синтаксу смо 417 00:17:00,280 --> 00:17:01,799 користи неколико пута до сада. 418 00:17:01,799 --> 00:17:03,590 И ја ћу да се дефинише чвор, што опет 419 00:17:03,590 --> 00:17:06,812 је генерички термин за само неке контејнер за неку структуру података. 420 00:17:06,812 --> 00:17:09,020 Ја ћу да предложим да низ иде тамо. 421 00:17:09,020 --> 00:17:11,369 Али ми ћемо почети узимање они помоћним точковима сада. 422 00:17:11,369 --> 00:17:13,230 >> Нема више ЦС50 библиотека Заиста, осим ако не желиш 423 00:17:13,230 --> 00:17:15,230 да га користите за ваш финале Пројекат, који је у реду, 424 00:17:15,230 --> 00:17:18,569 али сада ћемо да повуче завесе и кажу да је то само цхар звезда. 425 00:17:18,569 --> 00:17:22,069 Дакле, реч тамо ће бити назив у питању те особе. 426 00:17:22,069 --> 00:17:25,079 И сада имам везу Овде на следећи чвор 427 00:17:25,079 --> 00:17:28,170 тако да они представљају сваки од чворова 428 00:17:28,170 --> 00:17:30,950 у ланцу, потенцијално, од повезане листе. 429 00:17:30,950 --> 00:17:34,090 >> А сад како ја изјављујем хасх сама сто? 430 00:17:34,090 --> 00:17:36,660 Како да проглашавам овај целу структуру? 431 00:17:36,660 --> 00:17:40,960 Па, стварно, баш као да се користи показивач на само први елемент листе 432 00:17:40,960 --> 00:17:44,510 раније, на сличан начин могу само да кажем Треба ми само гомилу показивача 433 00:17:44,510 --> 00:17:46,270 да спроведе целу хасх табели. 434 00:17:46,270 --> 00:17:49,484 Ја ћу имати низ позвао сто за хасх табели. 435 00:17:49,484 --> 00:17:50,900 То ће бити од величине капацитета. 436 00:17:50,900 --> 00:17:52,525 То је колико елемената може да стане у њега. 437 00:17:52,525 --> 00:17:56,180 И сваки од тих елемената у овој низ ће бити звезда чвор. 438 00:17:56,180 --> 00:17:56,810 Зашто? 439 00:17:56,810 --> 00:18:00,160 Па, по овој слици, шта ћу спровођење хасх табеле као 440 00:18:00,160 --> 00:18:04,330 ефикасно у само почетак Овај низ који смо вертикално дравн, 441 00:18:04,330 --> 00:18:06,820 Сваки од чије квадрата представља показивач. 442 00:18:06,820 --> 00:18:09,170 Да они који имају косе црте кроз њих су само нулл. 443 00:18:09,170 --> 00:18:11,410 А оне које имају стрелице иду на десно 444 00:18:11,410 --> 00:18:16,140 су стварни показивачи стварним чворова, ерго почетак повезане листе. 445 00:18:16,140 --> 00:18:19,050 >> Па ево, онда, како бисмо могли имплементирају хасх табелу која 446 00:18:19,050 --> 00:18:21,580 спроводи посебан цхаининг. 447 00:18:21,580 --> 00:18:22,840 Сада можемо да урадимо боље? 448 00:18:22,840 --> 00:18:25,632 У реду, обећао последњи пут можемо постићи константна времена. 449 00:18:25,632 --> 00:18:27,381 А ја сам те некако дала Цонстант пут овде, 450 00:18:27,381 --> 00:18:29,850 али тада је рекао да баш Цонстант пут јер је још увек 451 00:18:29,850 --> 00:18:31,890 зависи од укупне број елемената 452 00:18:31,890 --> 00:18:34,500 сте уноса у структура података. 453 00:18:34,500 --> 00:18:35,980 Али претпоставимо да смо ово урадили. 454 00:18:35,980 --> 00:18:39,550 Дозволите ми да се вратим на екран овде. 455 00:18:39,550 --> 00:18:44,520 Дозволите ми да пројектује ово овде, јасно екран, и претпостављам да сам то учинио. 456 00:18:44,520 --> 00:18:49,300 Претпоставимо Хтео сам да убаците име Давен у у моју структуру података. 457 00:18:49,300 --> 00:18:52,100 >> Зато желим да убаците стринг Давен у структуру података. 458 00:18:52,100 --> 00:18:54,370 Шта ако ја не користим хасх табеле, али ја користим 459 00:18:54,370 --> 00:18:56,980 нешто што је више налик дрво као породично стабло, где 460 00:18:56,980 --> 00:18:59,670 имате неки корен у врха и потом чворови и лишће 461 00:18:59,670 --> 00:19:01,440 да иду доле и споља. 462 00:19:01,440 --> 00:19:04,450 Претпоставимо онда, да сам Желим да убаците Давен с 463 00:19:04,450 --> 00:19:06,430 у оно што је тренутно празна листа. 464 00:19:06,430 --> 00:19:09,780 Ја ћу да урадите следеће: Ја сам ће створити чвор у овој породици 465 00:19:09,780 --> 00:19:15,170 Трее налик структура података која изгледа као мали овога, сваки од којих 466 00:19:15,170 --> 00:19:19,640 правоугаоника је, рецимо, за сада 26 елемената у њему. 467 00:19:19,640 --> 00:19:21,650 И сваки од ћелија у овом низу иде 468 00:19:21,650 --> 00:19:23,470 да представља слово абецеде. 469 00:19:23,470 --> 00:19:28,190 >> Конкретно, ја ћу третирати Ово је, затим Б, па Ц, затим Д, 470 00:19:28,190 --> 00:19:29,310 овај овде. 471 00:19:29,310 --> 00:19:32,940 Дакле, ово ће ефикасно представљају слово Д. 472 00:19:32,940 --> 00:19:36,040 Али да убаците све Давен је име морам да урадим нешто. 473 00:19:36,040 --> 00:19:37,840 Тако да прво идем да размотре, да се тако изразим. 474 00:19:37,840 --> 00:19:41,049 Идем да погледам прво слово у Давен с којима је очигледно Д, 475 00:19:41,049 --> 00:19:42,840 и ја ћу да издвоји чвор који изгледа 476 00:19:42,840 --> 00:19:45,570 овако-- велику правоугаоник велики Довољно да се опреми целу абецеду. 477 00:19:45,570 --> 00:19:47,140 >> Сада Д врши. 478 00:19:47,140 --> 00:19:49,720 Сада А. Д--В-Е-Н је циљ. 479 00:19:49,720 --> 00:19:51,220 Па сад шта ћу да урадим је ово. 480 00:19:51,220 --> 00:19:54,027 Чим сам почео обавештење Д нема Поинтер тамо. 481 00:19:54,027 --> 00:19:56,860 То је вредности за смеће у овом тренутку, или можда то инитиализе нулл. 482 00:19:56,860 --> 00:19:59,630 Али дозволите ми да наставим са Ова идеја о изградњи дрво. 483 00:19:59,630 --> 00:20:04,260 Дозволите ми да издвоје још један од ових чворови који има 26 елемената у њему. 484 00:20:04,260 --> 00:20:05,150 >> И знате шта? 485 00:20:05,150 --> 00:20:09,130 Ако је ово само чвор у меморији који Ја створио са маллоц, користећи градитеља 486 00:20:09,130 --> 00:20:11,240 као што ћемо ускоро видети, Ја ћу да урадим ово-- 487 00:20:11,240 --> 00:20:14,450 Ја ћу да скренем стрелу из Оно што представља Д доле 488 00:20:14,450 --> 00:20:15,860 на овом новом чвору. 489 00:20:15,860 --> 00:20:19,240 А сада, прво следећа писмо у име Давен је, 490 00:20:19,240 --> 00:20:24,150 В-- Д-В-- ћу ићи напред и извући други чвор овако, 491 00:20:24,150 --> 00:20:30,150 при чему су В елементи овде, што ћемо извући за инстанце-- Упс. 492 00:20:30,150 --> 00:20:31,020 Нећемо извући тамо. 493 00:20:31,020 --> 00:20:31,936 То ће ићи овде. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Онда ћемо Сматрамо да је ово В. 496 00:20:35,712 --> 00:20:44,920 А онда овде ћемо индексу доле из В у шта ћемо размотрити Е. 497 00:20:44,920 --> 00:20:50,100 А онда одатле ћемо иди имати један од ових чворова овде. 498 00:20:50,100 --> 00:20:52,930 А сада имамо одговорити на то питање. 499 00:20:52,930 --> 00:20:57,840 Морам да некако указује на то да смо на крају низа Давен. 500 00:20:57,840 --> 00:20:59,490 Тако да сам могао вратити га на НУЛЛ. 501 00:20:59,490 --> 00:21:02,670 >> Али шта ако имамо Давен је име и презиме и, који 502 00:21:02,670 --> 00:21:04,280 је, као што смо рекли, Давенпорт? 503 00:21:04,280 --> 00:21:06,970 Па шта ако је Давен заправо подниз, 504 00:21:06,970 --> 00:21:08,960 префикс много дужег низа? 505 00:21:08,960 --> 00:21:11,450 Не можемо само стално кажу ништа не иде 506 00:21:11,450 --> 00:21:14,410 да одем тамо, јер смо могли Никада убаците неку реч као Давенпорт 507 00:21:14,410 --> 00:21:15,840 у овом структура података 508 00:21:15,840 --> 00:21:19,560 >> Дакле, шта можемо да урадимо уместо је третира сваки од ових елемената 509 00:21:19,560 --> 00:21:22,170 као можда има два елементи у њима. 510 00:21:22,170 --> 00:21:24,810 Један је показивач, заиста, као што сам радила. 511 00:21:24,810 --> 00:21:27,100 Тако да сваки од тих кутија није само једна ћелија. 512 00:21:27,100 --> 00:21:29,855 Али, шта ако врх --виберите-- дно један је 513 00:21:29,855 --> 00:21:32,230 ће бити нула, јер је нема Девенпорт још. 514 00:21:32,230 --> 00:21:34,197 Шта ако неко врх је нека посебна вредност? 515 00:21:34,197 --> 00:21:36,530 И то ће бити мало тешко је ово величина драв. 516 00:21:36,530 --> 00:21:38,130 Али, претпоставимо да је само ознака потврде. 517 00:21:38,130 --> 00:21:38,920 Проверите. 518 00:21:38,920 --> 00:21:44,230 Д--В-Е-Н је стринг у овој структури података. 519 00:21:44,230 --> 00:21:48,350 >> У међувремену, ако бих имала више простора овде, ја могу да урадим П-О-Р-Т, 520 00:21:48,350 --> 00:21:52,650 и ја могла ставити чек у чвор која има слово Т на самом крају. 521 00:21:52,650 --> 00:21:55,460 Дакле, ово је масовно комплекс изгледају структуре података. 522 00:21:55,460 --> 00:21:57,210 И мој рукопис свакако не помаже. 523 00:21:57,210 --> 00:22:00,043 Али, ако сам хтео да убаците нешто друго, размотримо шта ћемо урадити. 524 00:22:00,043 --> 00:22:03,370 Ако бисмо желели да стави Давида у, ћемо пратити исту логику, Д-А-В, 525 00:22:03,370 --> 00:22:08,802 али сада морам да кажем у следећа Не елеменат из Е, али од И до Д. 526 00:22:08,802 --> 00:22:10,760 Тако да ће бити више чворова у овом дрвету. 527 00:22:10,760 --> 00:22:12,325 Ми ћемо имати више позива маллоц. 528 00:22:12,325 --> 00:22:14,700 Али ја не желим да збрка изображениа. 529 00:22:14,700 --> 00:22:17,710 Па хајде да погледамо, уместо једном који је био пре-формулисана 530 00:22:17,710 --> 00:22:21,810 овако са не тачка, тачка, тачке, али само скраћени низови. 531 00:22:21,810 --> 00:22:23,950 Али сваки од чворова на овом дрвету овде 532 00:22:23,950 --> 00:22:26,700 представља исти ствар-- низ Реј величине 26. 533 00:22:26,700 --> 00:22:28,860 >> Или, ако желимо да будемо стварно правилно сада, шта 534 00:22:28,860 --> 00:22:30,790 Ако неко име као Апостропхе, хајдемо 535 00:22:30,790 --> 00:22:35,560 претпостављају да сваки чвор заправо има Као 27 индекса у њој, а не само 26. 536 00:22:35,560 --> 00:22:42,020 Дакле, ово сад ће бити дата Структура зове трие-- Т-Р-И-Е. 537 00:22:42,020 --> 00:22:46,120 Трие, која је наводно историјски паметан назив за дрво 538 00:22:46,120 --> 00:22:49,040 који је оптимизован за проналажење, што наравно, 539 00:22:49,040 --> 00:22:50,870 је написано са И-е, тако да је Трие. 540 00:22:50,870 --> 00:22:52,710 Али то је историја Трие. 541 00:22:52,710 --> 00:22:55,860 >> Дакле, ово дрво Трие попут података Структура као породично стабло 542 00:22:55,860 --> 00:22:57,510 да на крају се понаша као да је. 543 00:22:57,510 --> 00:23:00,890 И ту је само још један пример гомила имена других људи. 544 00:23:00,890 --> 00:23:03,540 Али питање сад при руци је оно што су 545 00:23:03,540 --> 00:23:08,070 добили смо увођењем вероватно више компликована структура података, и један, 546 00:23:08,070 --> 00:23:09,870 искрено, који користи много меморије. 547 00:23:09,870 --> 00:23:11,703 >> Јер иако, у овом тренутку, ја сам само 548 00:23:11,703 --> 00:23:15,050 коришћењем Д'с показивач и И В и Ес и НС, 549 00:23:15,050 --> 00:23:16,700 Губим се паклени много меморије. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Али, где проводим једног ресурса, Склон сам да не добију неки други. 552 00:23:22,660 --> 00:23:26,020 Дакле, ако сам проводим више простора, шта је вероватно нада? 553 00:23:26,020 --> 00:23:27,407 Да ја проводим мање шта? 554 00:23:27,407 --> 00:23:28,240 ПУБЛИКА: Мање времена. 555 00:23:28,240 --> 00:23:28,990 ДАВИД Малан: Време. 556 00:23:28,990 --> 00:23:30,320 Зашто би то било? 557 00:23:30,320 --> 00:23:33,880 Па, шта је уметање време, у смислу сада Биг О, 558 00:23:33,880 --> 00:23:37,660 од имена као Давен или Давенпорт или Давид? 559 00:23:37,660 --> 00:23:39,340 Па, Давен је пет корака. 560 00:23:39,340 --> 00:23:42,350 Давенпорт би девет корака, тако да би било још неколико корака. 561 00:23:42,350 --> 00:23:44,250 Давид би бити пет корака као добро. 562 00:23:44,250 --> 00:23:47,230 Дакле, то су бетон бројеви, али сигурно има 563 00:23:47,230 --> 00:23:49,550 горња граница дужина нечијег имена. 564 00:23:49,550 --> 00:23:52,240 И заиста, у проблему комплета пет спецификације, 565 00:23:52,240 --> 00:23:54,050 ћемо предложити да је то нешто 566 00:23:54,050 --> 00:23:55,470 То је 40-ак-нека карактера. 567 00:23:55,470 --> 00:23:58,180 >> Реално, нико нема бескрајно дуго име, 568 00:23:58,180 --> 00:24:01,542 што ће рећи да је дужина име или дужина низа бисмо могли 569 00:24:01,542 --> 00:24:03,750 имају одређени стање Структура је вероватно шта? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 То је константа. 572 00:24:06,250 --> 00:24:06,430 Зар не? 573 00:24:06,430 --> 00:24:09,310 То може бити велика као константа 40-нешто, али је константан. 574 00:24:09,310 --> 00:24:13,752 И то нема зависност колико друга имена су у тој структури података. 575 00:24:13,752 --> 00:24:15,460 Другим речима, ако Желео сам да убаците 576 00:24:15,460 --> 00:24:20,540 Колтон или Габријел или Роб или Замила или Алисон или Белинда или било којим другим имена 577 00:24:20,540 --> 00:24:23,940 од запослених у овом података Структура је руннинг тиме 578 00:24:23,940 --> 00:24:26,750 убацивања друга имена ће бити на свим угроженим 579 00:24:26,750 --> 00:24:30,220 по томе колико и друге елементе У структури података Већ? 580 00:24:30,220 --> 00:24:31,040 Није. 581 00:24:31,040 --> 00:24:31,540 Зар не? 582 00:24:31,540 --> 00:24:36,150 Јер смо ефикасно користимо Овај вишеслојни хасх табела. 583 00:24:36,150 --> 00:24:38,280 А руннинг време било који од ових операција 584 00:24:38,280 --> 00:24:41,510 не зависи од броја елементи који су у структури података 585 00:24:41,510 --> 00:24:43,090 или да се евентуално ће бити у структури података, 586 00:24:43,090 --> 00:24:44,714 али на дужини шта конкретно? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Стринг је убачена, који не чине 589 00:24:49,200 --> 00:24:52,580 Тхис асимптотикески Цонстант времена-- готово Биг О једног. 590 00:24:52,580 --> 00:24:54,720 И искрено, само у стварни свет, ово 591 00:24:54,720 --> 00:24:58,380 значи уметање име Давен је потребно Као пет корака, односно девет Давенпорт 592 00:24:58,380 --> 00:25:00,100 кораци, или Давид пет корака. 593 00:25:00,100 --> 00:25:03,071 То је прилично проклето мали Руннинг Тимес. 594 00:25:03,071 --> 00:25:05,320 И, заиста, то је врло добро, посебно када 595 00:25:05,320 --> 00:25:08,126 није зависи од укупне број елемената у ту. 596 00:25:08,126 --> 00:25:10,500 Дакле, како да примењују овај врста објекта у коду? 597 00:25:10,500 --> 00:25:12,900 То је мало више комплекс, али и даље је 598 00:25:12,900 --> 00:25:15,050 само примена Основни градивни блокови. 599 00:25:15,050 --> 00:25:17,830 Идем да редефинише САД чвор на следећи начин: 600 00:25:17,830 --> 00:25:21,100 боол назвао ворд-- и ово може назвати било шта. 601 00:25:21,100 --> 00:25:23,970 Али боол представља оно што сам нацртао као потврде. 602 00:25:23,970 --> 00:25:24,490 Да. 603 00:25:24,490 --> 00:25:26,720 Ово је крај низа у овој структури података. 604 00:25:26,720 --> 00:25:30,702 >> И, наравно, звезда чвор тамо се односи на децу. 605 00:25:30,702 --> 00:25:32,410 И заиста, баш као и породично стабло, ви 606 00:25:32,410 --> 00:25:34,370 би размотрити чворове које су висиле 607 00:25:34,370 --> 00:25:36,920 дна неких родитеља елемент буду деца. 608 00:25:36,920 --> 00:25:40,510 Па деца ће се бити низ од 27, 27. један 609 00:25:40,510 --> 00:25:41,680 Само што за призивање. 610 00:25:41,680 --> 00:25:43,390 Идемо на сортирање посебног случају да. 611 00:25:43,390 --> 00:25:45,400 Тако да можете имати сигуран имена са апострофа. 612 00:25:45,400 --> 00:25:47,399 Можда чак и цртица требало иди тамо, али ћете 613 00:25:47,399 --> 00:25:50,330 види у п сет 5 ми само неге о писмима и апострофа. 614 00:25:50,330 --> 00:25:52,990 >> И онда како ви представник Сама структура података? 615 00:25:52,990 --> 00:25:56,454 Како се представљају корен овог Трие, да тако кажем? 616 00:25:56,454 --> 00:25:59,620 Па, баш као са повезане листе, ви треба показивач на први елемент. 617 00:25:59,620 --> 00:26:04,270 Са Трие треба само један Поинтер на корен ове Трие. 618 00:26:04,270 --> 00:26:07,290 А одатле можете хасх Ваш начин дубље и дубље 619 00:26:07,290 --> 00:26:10,460 на сваком другом чвору у структури. 620 00:26:10,460 --> 00:26:13,440 Дакле, једноставно са њима могу бити ми представљамо ту градитеља. 621 00:26:13,440 --> 00:26:15,877 >> Сада Меанвхиле-- О, питање. 622 00:26:15,877 --> 00:26:17,220 >> ПУБЛИКА: Шта је боол реч? 623 00:26:17,220 --> 00:26:20,490 >> ДАВИД Малан: Боол реч само овај Ц инкарнација 624 00:26:20,490 --> 00:26:22,920 онога што је описано у овој кутији овде, када је 625 00:26:22,920 --> 00:26:26,000 Почео сам да поделе сваке од елементи на два дела арраи је. 626 00:26:26,000 --> 00:26:27,600 Један је показивач на следећи чвор. 627 00:26:27,600 --> 00:26:30,280 Други мора бити нешто као поље за потврду 628 00:26:30,280 --> 00:26:33,770 да кажем да, ту је Реч Давен то се завршава овде, 629 00:26:33,770 --> 00:26:35,610 јер не желимо, У овом тренутку, Дејв. 630 00:26:35,610 --> 00:26:39,320 >> Иако је Дејв ће бити легитимна реч, он није у Трие 631 00:26:39,320 --> 00:26:39,830 још. 632 00:26:39,830 --> 00:26:40,950 И Д није реч. 633 00:26:40,950 --> 00:26:42,770 И Д-није реч или име. 634 00:26:42,770 --> 00:26:45,020 Дакле, ознаци указује само једном вас 635 00:26:45,020 --> 00:26:48,190 хит Ово је чвор Претходни пут карактера 636 00:26:48,190 --> 00:26:50,700 заправо стринг који сте уметнута. 637 00:26:50,700 --> 00:26:53,660 Тако да је све инт тамо ради за нас. 638 00:26:53,660 --> 00:26:55,500 >> Има ли још питања на покушаја? 639 00:26:55,500 --> 00:26:56,215 Да. 640 00:26:56,215 --> 00:26:58,035 >> ПУБЛИКА: Шта је преклапања? 641 00:26:58,035 --> 00:26:59,945 Шта ако имате Дејв и Давен? 642 00:26:59,945 --> 00:27:00,820 ДАВИД Малан: Савршено. 643 00:27:00,820 --> 00:27:02,580 Шта ако имате Дејв и Давен? 644 00:27:02,580 --> 00:27:06,240 Дакле, ако смо убацили, кажу надимак, фор Давид-- Даве-- Д-А-В-Е? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 То је заправо супер једноставна. 647 00:27:08,700 --> 00:27:10,325 Тако да само ћемо предузети четири корака. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 Д-А-В-Е. И шта ја имам да радим кад сам ударио ту четврту чвор? 650 00:27:15,847 --> 00:27:16,680 Само да проверим. 651 00:27:16,680 --> 00:27:18,000 Већ смо да кренемо. 652 00:27:18,000 --> 00:27:18,840 Доне. 653 00:27:18,840 --> 00:27:19,750 Четири корака. 654 00:27:19,750 --> 00:27:21,590 Константна време асимптотски. 655 00:27:21,590 --> 00:27:26,300 И сада смо рекли да оба Даве и Давен су жице у структури. 656 00:27:26,300 --> 00:27:27,710 Дакле, није проблем. 657 00:27:27,710 --> 00:27:30,200 И приметили како присуство од Давен није успео 658 00:27:30,200 --> 00:27:34,750 предузме више времена или мање Време за Дејв и обрнуто. 659 00:27:34,750 --> 00:27:36,000 >> Дакле, шта друго да радимо сада? 660 00:27:36,000 --> 00:27:40,680 Ми смо користили ову метафору раније носача каблова представља нешто. 661 00:27:40,680 --> 00:27:43,380 Али се испоставља да стек каблова заправо 662 00:27:43,380 --> 00:27:47,187 показна другог апстрактног података тип-- виши ниво структуре података 663 00:27:47,187 --> 00:27:49,770 да је на крају дана је само као низ или повезане листе 664 00:27:49,770 --> 00:27:50,970 или нешто више земаљски. 665 00:27:50,970 --> 00:27:53,270 Али то је још занимљиво концептуални концепт. 666 00:27:53,270 --> 00:27:56,440 Стек, као што ови траис овде у Матхер, 667 00:27:56,440 --> 00:27:58,750 се генерално називају Само да-- рис. 668 00:27:58,750 --> 00:28:02,540 >> И у ову врсту структуре података имате два оператионс-- 669 00:28:02,540 --> 00:28:05,880 имате један по имену погурати додајући нешто стека, 670 00:28:05,880 --> 00:28:08,320 као стављање другог послужавник назад на врх стека. 671 00:28:08,320 --> 00:28:11,350 И онда поп, који вам значи узети врхунски фиоке ОФФ. 672 00:28:11,350 --> 00:28:16,210 Али оно што је кључно у вези је да стек она има ту необичну карактеристику. 673 00:28:16,210 --> 00:28:19,560 Као и штаба трпезарији су преуређења лежишта за следећи оброк, 674 00:28:19,560 --> 00:28:21,380 шта ће бити Истина о томе како ученици 675 00:28:21,380 --> 00:28:22,856 интеракцију са овом структуром података? 676 00:28:22,856 --> 00:28:24,480 ПУБЛИКА: Они ће поп једнократно. 677 00:28:24,480 --> 00:28:26,550 ДАВИД Малан: Иду у поп једнократно, надам се врх. 678 00:28:26,550 --> 00:28:28,910 У супротном то је само мало глупо да иде све до дна. 679 00:28:28,910 --> 00:28:29,070 Зар не? 680 00:28:29,070 --> 00:28:31,620 Структура података не дозвољава баш да бар зграбите дно фиоке 681 00:28:31,620 --> 00:28:32,520 лако. 682 00:28:32,520 --> 00:28:35,040 Тако да је ово занимљиво имовине на стацк 683 00:28:35,040 --> 00:28:39,730 да последња ставка у је ће бити први напоље. 684 00:28:39,730 --> 00:28:43,400 И компјутерски научници зову Овај ЛИФО-- траје у, прво се. 685 00:28:43,400 --> 00:28:45,540 И она заправо нема интересантних апликација. 686 00:28:45,540 --> 00:28:50,090 Није нужно као очигледно као неки други, али може, заиста, бити користан, 687 00:28:50,090 --> 00:28:54,040 а може, заиста, бити имплементиран у неколико различитих начина. 688 00:28:54,040 --> 00:28:58,550 >> Дакле један, и заправо, нека ми не да зарони у то. 689 00:28:58,550 --> 00:28:59,860 Хајде да уместо тога ово. 690 00:28:59,860 --> 00:29:03,700 Погледајмо онај који је скоро Иста идеја, али то је мало праведније. 691 00:29:03,700 --> 00:29:04,200 Зар не? 692 00:29:04,200 --> 00:29:07,560 Ако сте један од тих навијачких дечака или девојке које стварно воли Аппле Продуцтс 693 00:29:07,560 --> 00:29:10,130 Пробудили сте се и у 3:00 да се построје у некој продавници 694 00:29:10,130 --> 00:29:14,150 да бисте добили најновију иПхоне, ти можда чекању овако. 695 00:29:14,150 --> 00:29:15,800 >> Сада ред је врло намерно зове. 696 00:29:15,800 --> 00:29:18,190 То је ред, јер ту је неки правичност томе. 697 00:29:18,190 --> 00:29:18,690 Зар не? 698 00:29:18,690 --> 00:29:21,690 То би некако сисао ако немаш Имам тамо први на Аппле Сторе 699 00:29:21,690 --> 00:29:25,700 али ти си ефективно Најнижи траи јер запослени у Аппле тада 700 00:29:25,700 --> 00:29:28,189 поп последња особа која заправо сам у реду. 701 00:29:28,189 --> 00:29:31,230 Дакле, димњацима и редовима, иако функционално су некако на саме-- 702 00:29:31,230 --> 00:29:33,105 то је само збирка ресурса је то 703 00:29:33,105 --> 00:29:36,210 ће расти и схринк-- тамо се Ово правичност аспект на њега, 704 00:29:36,210 --> 00:29:39,634 барем у стварном свету, где су операције вежбате 705 00:29:39,634 --> 00:29:40,800 фундаментално другачија. 706 00:29:40,800 --> 00:29:43,360 Стацк-- ред ратхер-- се каже да има 707 00:29:43,360 --> 00:29:45,320 две операције: н реду и Д ред. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Или можете их назвати било који број ствари. 710 00:29:48,090 --> 00:29:50,770 Али ви само желите да снимите Идеја да неко додаје 711 00:29:50,770 --> 00:29:53,230 а један је на крају одузимања. 712 00:29:53,230 --> 00:29:58,840 >> Сада испод хаубе, и стек и ред се може спровести како? 713 00:29:58,840 --> 00:30:01,390 Нећемо улазити у коду то зато што виши ниво 714 00:30:01,390 --> 00:30:03,387 Идеја је некако више очигледно. 715 00:30:03,387 --> 00:30:04,470 Мислим, шта људи радим? 716 00:30:04,470 --> 00:30:07,030 Ако сам ја прва особа на Аппле Сторе и то је предња врата, 717 00:30:07,030 --> 00:30:08,130 знате, ја ћу да стојим овде. 718 00:30:08,130 --> 00:30:09,750 А следећа особа је ће стајати овде. 719 00:30:09,750 --> 00:30:11,500 А следећа особа је ће стајати овде. 720 00:30:11,500 --> 00:30:13,792 Па шта структура података даје себи на ред? 721 00:30:13,792 --> 00:30:14,542 >> ПУБЛИКА: ред. 722 00:30:14,542 --> 00:30:15,667 ДАВИД Малан: Па, ред. 723 00:30:15,667 --> 00:30:16,390 Наравно. 724 00:30:16,390 --> 00:30:16,920 Шта друго? 725 00:30:16,920 --> 00:30:17,600 >> ПУБЛИКА: линкед лист. 726 00:30:17,600 --> 00:30:18,990 >> ДАВИД Малан: линкед список можете имплементирати. 727 00:30:18,990 --> 00:30:22,500 И повезана листа је лепо, јер тада може произвољно дуго расте насупрот 728 00:30:22,500 --> 00:30:24,880 да имају неки фиксни број људи у продавници. 729 00:30:24,880 --> 00:30:27,030 Али, можда фиксни број места је легитимна. 730 00:30:27,030 --> 00:30:30,350 Јер, ако они имају само као 20 Аппле првог дана, можда 731 00:30:30,350 --> 00:30:33,930 они само треба низ величине 20 да представља тај ред, који 732 00:30:33,930 --> 00:30:37,070 тек сада рећи када почнемо разговор О овим проблемима вишег нивоа, 733 00:30:37,070 --> 00:30:38,890 можете имплементирати у било ком броју начина. 734 00:30:38,890 --> 00:30:42,030 И ту је вероватно само да бити компромис у простору и времену 735 00:30:42,030 --> 00:30:43,950 или само у својој сложености кода. 736 00:30:43,950 --> 00:30:45,380 >> Шта о стацк? 737 00:30:45,380 --> 00:30:48,190 Па, стек, смо такође видели могао бити само ове тацне. 738 00:30:48,190 --> 00:30:50,007 А ти би могао реализовати овај низ. 739 00:30:50,007 --> 00:30:53,090 Али у неком тренутку ако користите низ, шта ће се догодити са тацне 740 00:30:53,090 --> 00:30:54,173 Ви покушавате да спустим? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 У реду. 743 00:30:55,670 --> 00:30:57,490 Идеш само моћи да иде тако високо. 744 00:30:57,490 --> 00:31:00,156 И мислим да у Матхер су заправо удубљењем у тај отвор. 745 00:31:00,156 --> 00:31:01,950 Дакле заиста, то је готово као Матхер користи 746 00:31:01,950 --> 00:31:03,783 низ фиксне величине, јер можете само да 747 00:31:03,783 --> 00:31:08,302 фит толико каблова у тај отвор у зид доле колена људи. 748 00:31:08,302 --> 00:31:10,010 И тако то би могло бити рекао да је низ, 749 00:31:10,010 --> 00:31:14,300 али свакако могли да применимо општије са повезане листе. 750 00:31:14,300 --> 00:31:16,390 >> Па, шта је са другом структуром података? 751 00:31:16,390 --> 00:31:18,760 Дозволите ми подићи један други визуелни овде. 752 00:31:18,760 --> 00:31:24,710 Нешто слично како о овоме овде? 753 00:31:24,710 --> 00:31:28,920 Зашто би то било корисно да нема нешто као фенси као Трие, који 754 00:31:28,920 --> 00:31:32,370 смо видели имали ове веома широке чворова, од којих је сваки у низу? 755 00:31:32,370 --> 00:31:35,740 Али, шта ако радимо нешто Једноставно, као стара школа породично стабло, 756 00:31:35,740 --> 00:31:38,110 Сваки чији чворови овде је само чување број. 757 00:31:38,110 --> 00:31:42,180 Уместо имена или потомка је само чување број овако. 758 00:31:42,180 --> 00:31:45,250 >> Па, жаргон користимо у структуре података је и покушава 759 00:31:45,250 --> 00:31:49,510 и дрвеће, где Трие, опет, није само онај чија чворови су низови, 760 00:31:49,510 --> 00:31:51,680 је још увек оно што можете користите из основној школи 761 00:31:51,680 --> 00:31:53,860 када је породицу трее-- лишће и корен 762 00:31:53,860 --> 00:31:57,250 стабла и деце родитељ и браћа и сестре њихове. 763 00:31:57,250 --> 00:32:03,670 И можемо провести дрво, на пример, као једноставно као ово. 764 00:32:03,670 --> 00:32:07,420 Трее, ако као чвор, један од ови кругови који има број, 765 00:32:07,420 --> 00:32:09,947 то неће имати један показивач, али две. 766 00:32:09,947 --> 00:32:11,780 И чим сте додали други показивач, ти 767 00:32:11,780 --> 00:32:13,905 могу заправо сада направити Сортирај дводимензионалног података 768 00:32:13,905 --> 00:32:14,780 структуре у меморији. 769 00:32:14,780 --> 00:32:16,660 Слично као дводимензионални Арраи, можете 770 00:32:16,660 --> 00:32:18,904 имају врсту дводимензионални повезаних листи, али оне 771 00:32:18,904 --> 00:32:20,820 који следе образац где нема циклуса. 772 00:32:20,820 --> 00:32:24,487 То је заиста дрво са једним деда пут овде, а онда 773 00:32:24,487 --> 00:32:27,320 неки родитељи и деца и унуци и праунуци. 774 00:32:27,320 --> 00:32:28,370 и тако даље. 775 00:32:28,370 --> 00:32:32,390 >> Али оно што је заиста згодно о томе превише, Само да вас задиркује са мало кода, 776 00:32:32,390 --> 00:32:35,370 рецалл рецурсион од неко време назад, при чему 777 00:32:35,370 --> 00:32:38,220 пишете функцију која се зове. 778 00:32:38,220 --> 00:32:41,140 Ово је лепа прилика да спроведе нешто 779 00:32:41,140 --> 00:32:42,920 као рекурзије, јер сматрам да. 780 00:32:42,920 --> 00:32:43,860 >> Ово је дрво. 781 00:32:43,860 --> 00:32:48,040 И ја сам био мало Анални начином Ставио сам целих бројева на улицу. 782 00:32:48,040 --> 00:32:51,020 Толико да има посебан назовете бинарни претраживање дрво. 783 00:32:51,020 --> 00:32:53,460 Сада смо чули бинарни претраживање, али да ли можете 784 00:32:53,460 --> 00:32:55,180 раде уназад од имена је ова ствар? 785 00:32:55,180 --> 00:32:59,280 Шта је образац како сам убаци целих бројева у овом дрвету? 786 00:32:59,280 --> 00:33:00,696 То није произвољно. 787 00:33:00,696 --> 00:33:01,570 Постоји нека образац. 788 00:33:01,570 --> 00:33:02,090 Да. 789 00:33:02,090 --> 00:33:03,370 >> ПУБЛИКА: мањих лево. 790 00:33:03,370 --> 00:33:03,690 >> ДАВИД Малан: Да. 791 00:33:03,690 --> 00:33:05,062 Мање су на левој страни. 792 00:33:05,062 --> 00:33:06,270 Већи оне су са десне стране. 793 00:33:06,270 --> 00:33:12,940 Тако да прави изјава родитељ је већа од његове леве дете, 794 00:33:12,940 --> 00:33:14,850 али мање од десној детета. 795 00:33:14,850 --> 00:33:17,750 Као и да је чак и сама рецурсиве вербално дефиниција 796 00:33:17,750 --> 00:33:20,500 јер можете да примените да Иста логика се сваком чвору 797 00:33:20,500 --> 00:33:23,080 и само дно се, база случају ако 798 00:33:23,080 --> 00:33:25,740 ће, када ударио једног од лишће, да тако кажем, 799 00:33:25,740 --> 00:33:28,580 где одсуство нема деце и даље. 800 00:33:28,580 --> 00:33:30,614 >> Сада како да нађете број 44? 801 00:33:30,614 --> 00:33:32,280 Ти би почети у корену и кажу, хм. 802 00:33:32,280 --> 00:33:35,690 55 није 44 Зато желим да идем Право или да Желим да идем лево? 803 00:33:35,690 --> 00:33:37,190 Па, очигледно хоћеш да идеш лево. 804 00:33:37,190 --> 00:33:40,060 Па то је као на телефону Књига пример у бинарном потрази 805 00:33:40,060 --> 00:33:41,099 уопште. 806 00:33:41,099 --> 00:33:43,390 Али ми њено спровођење Сада мало динамички 807 00:33:43,390 --> 00:33:45,339 него низ може да дозволи. 808 00:33:45,339 --> 00:33:48,130 И, у ствари, ако желите да погледате у коду, на први поглед сигуран. 809 00:33:48,130 --> 00:33:49,671 Изгледа као гомила линија. 810 00:33:49,671 --> 00:33:51,220 Али то је дивно једноставно. 811 00:33:51,220 --> 00:33:54,490 Ако желите да спроведе функције позвао претрага чија је сврха у животу 812 00:33:54,490 --> 00:33:57,290 је да тражи вредност попут н, цео број, 813 00:33:57,290 --> 00:34:01,756 а ви прошли у једном поинтер-- показивач на чвор корена, 814 00:34:01,756 --> 00:34:04,380 Уместо тога, од тог дрвета из којих можете да приступите све друго, 815 00:34:04,380 --> 00:34:08,850 приметили како искрено можете имплементирати логику. 816 00:34:08,850 --> 00:34:10,880 Ако дрво нулл, очигледно није ту. 817 00:34:10,880 --> 00:34:11,880 Хајде само ретурн. 818 00:34:11,880 --> 00:34:12,000 Зар не? 819 00:34:12,000 --> 00:34:14,040 Ако га предате ништа, тамо нема ништа. 820 00:34:14,040 --> 00:34:17,900 >> Елсе, ако је н мање од Трее стрелица н-- сада арров н 821 00:34:17,900 --> 00:34:20,670 сјећате смо увели супер кратко неки дан, 822 00:34:20,670 --> 00:34:25,100 а то само значи де референца на показивач и погледате поље зове н. 823 00:34:25,100 --> 00:34:27,690 Значи, тамо и погледај на терену зове н. 824 00:34:27,690 --> 00:34:33,810 Дакле, ако н, вредност сте дали, мање од вредности на дрвећу цео број, 825 00:34:33,810 --> 00:34:35,449 где желите да идете? 826 00:34:35,449 --> 00:34:36,389 Лево. 827 00:34:36,389 --> 00:34:37,780 >> Дакле, приметио рекурзију. 828 00:34:37,780 --> 00:34:39,860 Ја ретурнинг-- није истина. 829 00:34:39,860 --> 00:34:40,989 Није лажна. 830 00:34:40,989 --> 00:34:45,670 Враћам без обзира на одговор је од позива до себе, пролазећи 831 00:34:45,670 --> 00:34:50,100 опет н, која је сувишан, али оно што је мало другачије? 832 00:34:50,100 --> 00:34:51,989 Како ја што је проблем мање? 833 00:34:51,989 --> 00:34:54,920 Ја сам пролази у као други аргумент, није корен дрвета, 834 00:34:54,920 --> 00:34:59,616 али левица дете у овом случају. 835 00:34:59,616 --> 00:35:00,990 Тако да сам пролази левом детета. 836 00:35:00,990 --> 00:35:04,720 >> У међувремену, ако је н већи од чвор Ја тренутно гледам, 837 00:35:04,720 --> 00:35:06,690 Ја претраживање десне стране. 838 00:35:06,690 --> 00:35:10,880 Елсе, ако дрво није нулл, и ако елемент није лево 839 00:35:10,880 --> 00:35:13,240 а није у праву, што је предивно случај? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Ми смо заправо смо нашли у чвор питање, па се враћамо истина. 842 00:35:18,440 --> 00:35:21,490 >> Тако да смо управо загребали површину Неки од ових структура података. 843 00:35:21,490 --> 00:35:24,370 У проблема сет пет ви ћете Истражите ове још даље, 844 00:35:24,370 --> 00:35:27,250 а ви ћете добити ваш дизајн избор како да о овоме. 845 00:35:27,250 --> 00:35:30,250 Оно што бих желео да закључи је само 30 секунда теасер 846 00:35:30,250 --> 00:35:32,080 шта чека следеће недеље и шире. 847 00:35:32,080 --> 00:35:35,390 >> Као што смо срећу бегин-- да би могао мислим-- нашу транзицију полако 848 00:35:35,390 --> 00:35:38,680 из света Ц и ниже детаљи имплементације нивоу, 849 00:35:38,680 --> 00:35:42,090 у свету у коме можемо узети за готово да неко други има коначно 850 00:35:42,090 --> 00:35:44,010 спроводи ових података структуре за нас, 851 00:35:44,010 --> 00:35:47,570 и ми ћемо почети да разумемо стварни свет средства спровођења 852 00:35:47,570 --> 00:35:50,560 Програми веб-басед и сајтови генерално 853 00:35:50,560 --> 00:35:52,910 и веома безбедности импликације које смо само ми 854 00:35:52,910 --> 00:35:54,850 почели да огребете површину. 855 00:35:54,850 --> 00:35:57,320 Ево шта нас чека у данима који долазе. 856 00:35:57,320 --> 00:36:00,480 >> [ВИДЕО РЕПРОДУКЦИЈА] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> Он је дошао са поруком, са протоколом све своје. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Он је дошао у свет суровог фиревалл, немаран рутери, 861 00:36:30,894 --> 00:36:33,368 и опасности далеко горе од смрти. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Он је брз. 864 00:36:36,236 --> 00:36:37,980 Он је јак. 865 00:36:37,980 --> 00:36:42,830 Он је ТЦП / ИП, а он има своју адресу. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Варриорс мреже." 868 00:36:48,074 --> 00:36:49,660 [ЕНД ВИДЕО РЕПРОДУКЦИЈА] 869 00:36:49,660 --> 00:36:50,910 ДАВИД Малан: Цоминг следеће недеље. 870 00:36:50,910 --> 00:36:51,880 Ми ћемо се онда видети. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [ВИДЕО РЕПРОДУКЦИЈА] 873 00:36:56,060 --> 00:36:59,240 -А Сада, "Дееп Тхоугхтс" од Давен Фарнхам. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -Давид Увек почиње предавања са, "У реду." 876 00:37:05,820 --> 00:37:08,750 Зашто не, "Ево решења овонедељној проблема сет " 877 00:37:08,750 --> 00:37:12,180 или "Дајемо све вас?" 878 00:37:12,180 --> 00:37:13,380 [Лаугхинг] 879 00:37:13,380 --> 00:37:15,530 [ЕНД ВИДЕО РЕПРОДУКЦИЈА]