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