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