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