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