1 00:00:00,000 --> 00:00:08,250 2 00:00:08,250 --> 00:00:12,680 >> JASON Hirschhorn: Добре дошли на всички на секция Seven. 3 00:00:12,680 --> 00:00:15,040 Ние сме в седем седмици на курса. 4 00:00:15,040 --> 00:00:18,440 И това предстоящия четвъртък е Хелоуин, така че аз съм 5 00:00:18,440 --> 00:00:21,420 облечен като тиква. 6 00:00:21,420 --> 00:00:23,460 Не можех да се навежда и да постави на обувките ми, така че защо аз съм 7 00:00:23,460 --> 00:00:25,660 просто облечен чорапи. 8 00:00:25,660 --> 00:00:29,220 Аз също не нося нищо под това, така че аз не мога да го свалиш, ако това е 9 00:00:29,220 --> 00:00:29,950 отвлича за вас. 10 00:00:29,950 --> 00:00:31,860 Предварително се извинявам за това. 11 00:00:31,860 --> 00:00:33,170 Не е нужно да си представите какво става. 12 00:00:33,170 --> 00:00:34,240 Аз съм облечен боксьори. 13 00:00:34,240 --> 00:00:36,170 Така че всичко е наред. 14 00:00:36,170 --> 00:00:41,120 >> Имам дълга история за това защо аз съм облечен като тиква, но аз отивам да 15 00:00:41,120 --> 00:00:45,110 освен, че за по-късно в този раздел защото аз искам да започна. 16 00:00:45,110 --> 00:00:47,720 Ние имаме много вълнуващи неща за да премине през тази седмица. 17 00:00:47,720 --> 00:00:51,810 Повечето от тях са пряко свързани с този Седмица проблем набор, правописни грешки. 18 00:00:51,810 --> 00:00:54,680 Отиваме да ходи над свързан списъци и хеш таблици 19 00:00:54,680 --> 00:00:57,160 за целия участък. 20 00:00:57,160 --> 00:01:02,490 Сложих този списък на всяка седмица, списък на ресурси, за да ви помогне с 21 00:01:02,490 --> 00:01:04,120 Материалите в този курс. 22 00:01:04,120 --> 00:01:07,600 Ако на загуба или ако търсите за някои повече информация, вижте един от 23 00:01:07,600 --> 00:01:09,930 тези ресурси. 24 00:01:09,930 --> 00:01:14,530 >> Отново, pset6 е правописни грешки, PSET тази седмица. 25 00:01:14,530 --> 00:01:17,690 И тя също така ви съветва, и аз Насърчавам ви да използвате някои други 26 00:01:17,690 --> 00:01:20,320 ресурси, специално за тази PSET. 27 00:01:20,320 --> 00:01:23,390 По-специално, на три съм изброени на екрана - 28 00:01:23,390 --> 00:01:27,160 GDB, които ние сме били запознати с и е като за известно време сега, е 29 00:01:27,160 --> 00:01:29,270 ще бъде много полезна тази седмица. 30 00:01:29,270 --> 00:01:30,190 Така че сложих, че до тук. 31 00:01:30,190 --> 00:01:32,910 Но всеки път, когато работите с C, винаги трябва да се използва GDB да 32 00:01:32,910 --> 00:01:34,430 коригиране на грешки в програмите. 33 00:01:34,430 --> 00:01:36,660 Тази седмица също valgrind. 34 00:01:36,660 --> 00:01:38,535 Някой знае ли какво valgrind прави? 35 00:01:38,535 --> 00:01:42,184 36 00:01:42,184 --> 00:01:43,890 >> ПУБЛИКАТА: Тя проверява за изтичане на памет? 37 00:01:43,890 --> 00:01:45,950 >> JASON Hirschhorn: Valgrind проверки за изтичане на памет. 38 00:01:45,950 --> 00:01:49,970 Така че, ако изчистване нещо в програма, питаш за памет. 39 00:01:49,970 --> 00:01:52,920 В края на вашата програма, вие имате да пишат свободно на всичко, което сте 40 00:01:52,920 --> 00:01:54,800 malloced да даде паметта обратно. 41 00:01:54,800 --> 00:01:58,420 Ако не пиша безплатно в края и вашата програма идва до заключение, 42 00:01:58,420 --> 00:02:00,000 Всичко ще автоматично бъдат освободени. 43 00:02:00,000 --> 00:02:02,340 И за малки програми, това е Не е кой знае какво. 44 00:02:02,340 --> 00:02:05,250 Но ако сте написването на дълго бягане програма, която не се откажат, 45 00:02:05,250 --> 00:02:09,180 задължително, след няколко минути или няколко секунди, след това изтичане на памет 46 00:02:09,180 --> 00:02:10,710 може да се превърне в огромна сделка. 47 00:02:10,710 --> 00:02:14,940 >> Така че за pset6, очакването е, че ще имате нула изтичане на памет с 48 00:02:14,940 --> 00:02:15,910 Вашата програма. 49 00:02:15,910 --> 00:02:18,690 За да проверите за изтичане на памет, стартирайте valgrind и това ще ви даде някой хубав 50 00:02:18,690 --> 00:02:21,190 изход позволи да знаете дали или не всичко е безплатно. 51 00:02:21,190 --> 00:02:23,940 Ние ще практикуват с него по-късно днес, да се надяваме. 52 00:02:23,940 --> 00:02:25,790 >> Накрая, командата разл. 53 00:02:25,790 --> 00:02:28,900 Използвали сте нещо подобно, за да го в pset5 с инструмента поглед. 54 00:02:28,900 --> 00:02:30,780 Позволени ли да гледам вътре. 55 00:02:30,780 --> 00:02:33,400 Можете също така да се използва разл също на проблема избран спец.. 56 00:02:33,400 --> 00:02:35,950 Но в теб се оставя да сравни два файла. 57 00:02:35,950 --> 00:02:39,180 Може да се сравни растерна графика файл и Информация за заглавки разтвор на персонала и 58 00:02:39,180 --> 00:02:42,200 вашето решение в pset5 ако вие избрахте да го използвам. 59 00:02:42,200 --> 00:02:44,030 Diff ще ви позволи да направите това, както добре. 60 00:02:44,030 --> 00:02:48,620 Можете да сравните верния отговор за проблем тази седмица, за да настроите вашия отговор 61 00:02:48,620 --> 00:02:52,210 и да видим дали тя линии нагоре или вижте къде е грешката. 62 00:02:52,210 --> 00:02:55,870 >> Така че тези, които са три добри инструменти, които Вие трябва да използвате за тази седмица, и 63 00:02:55,870 --> 00:02:58,130 Определено проверите вашата програма с тези три инструмента 64 00:02:58,130 --> 00:03:00,520 преди да го включите инча 65 00:03:00,520 --> 00:03:04,650 Отново, както споменах всяка седмица, ако имате някакви отзиви за мен - и двете 66 00:03:04,650 --> 00:03:06,470 позитивна и конструктивна - 67 00:03:06,470 --> 00:03:09,930 Чувствайте се свободни да се отправят към уебсайта в долната част на този слайд 68 00:03:09,930 --> 00:03:11,270 и въвеждане там. 69 00:03:11,270 --> 00:03:13,440 Аз наистина оценявам всяко и всички обратна връзка. 70 00:03:13,440 --> 00:03:17,360 И ако ми дадете конкретни неща, които Мога да направя, за да се подобри или че аз съм 71 00:03:17,360 --> 00:03:21,350 справя добре, че ще ме искали да продължи, аз взема това присърце и 72 00:03:21,350 --> 00:03:24,040 наистина се опита трудно да се слуша за вашето мнение. 73 00:03:24,040 --> 00:03:27,720 Не мога да обещая, че ще направя всичко, все пак, като носеше 74 00:03:27,720 --> 00:03:30,700 тиквени костюм всяка седмица. 75 00:03:30,700 --> 00:03:34,020 >> Така че ние ще прекарват по-голямата част от раздел, както споменах, говорим за 76 00:03:34,020 --> 00:03:37,240 свързани списъци и хеш таблици, които ще бъде директно приложим към общия 77 00:03:37,240 --> 00:03:38,780 проблем зададете тази седмица. 78 00:03:38,780 --> 00:03:42,580 Свързани списъци ще излизат над относително бързо, защото сме прекарали справедлив малко 79 00:03:42,580 --> 00:03:44,930 от време става над него в раздел. 80 00:03:44,930 --> 00:03:48,680 И така, ние ще се заемем направо в кодиране проблеми за свързани списъци. 81 00:03:48,680 --> 00:03:52,740 И тогава в края ние ще говорим за хеш таблици и как те се прилагат за този 82 00:03:52,740 --> 00:03:55,280 проблем седмица настроен. 83 00:03:55,280 --> 00:03:57,560 >> Вие сте виждали този код преди. 84 00:03:57,560 --> 00:04:02,730 Това е структура, и е определяне нещо ново нарича възел. 85 00:04:02,730 --> 00:04:10,660 И в възел има число точно тук и там е указател към 86 00:04:10,660 --> 00:04:11,830 друг възел. 87 00:04:11,830 --> 00:04:12,790 Виждали сме това и преди. 88 00:04:12,790 --> 00:04:14,830 Това е идва за няколко седмици насам. 89 00:04:14,830 --> 00:04:18,680 Той съчетава указатели, които сме били работа с и structs, които позволяват 90 00:04:18,680 --> 00:04:22,079 ни да комбинирате две различни неща в един тип данни. 91 00:04:22,079 --> 00:04:24,830 92 00:04:24,830 --> 00:04:26,490 >> Има много неща се случват на екрана. 93 00:04:26,490 --> 00:04:30,220 Но всичко това трябва да бъде относително запознати с вас. 94 00:04:30,220 --> 00:04:33,810 На първия ред, ние обяви нов възел. 95 00:04:33,810 --> 00:04:41,650 И тогава вътре в тази нова възел, задам цяло число в този възел към едно. 96 00:04:41,650 --> 00:04:44,950 Ние виждаме на следващия ред Правя ФОРМАТ командване, но аз съм в сив цвят 97 00:04:44,950 --> 00:04:48,080 командата ФОРМАТ защото наистина Важна част е тази линия тук - 98 00:04:48,080 --> 00:04:50,020 new_node.n. 99 00:04:50,020 --> 00:04:51,270 Какво означава точката предвид? 100 00:04:51,270 --> 00:04:53,810 101 00:04:53,810 --> 00:04:57,240 >> ПУБЛИКАТА: Отиди до възела и оценка п стойност за него. 102 00:04:57,240 --> 00:04:58,370 >> JASON Hirschhorn: Това е точно така. 103 00:04:58,370 --> 00:05:03,300 Dot означава достъп до п част на този нов възел. 104 00:05:03,300 --> 00:05:05,690 Това следващия ред какво прави? 105 00:05:05,690 --> 00:05:16,140 106 00:05:16,140 --> 00:05:17,050 Майкъл. 107 00:05:17,050 --> 00:05:21,910 >> ПУБЛИКАТА: Той създава друг възел който ще сочи към новия възел. 108 00:05:21,910 --> 00:05:24,870 >> JASON Hirschhorn: Така че това не е така създаване на нов възел. 109 00:05:24,870 --> 00:05:26,120 Той създава какво? 110 00:05:26,120 --> 00:05:28,300 111 00:05:28,300 --> 00:05:29,300 >> Аудитория: A показалка. 112 00:05:29,300 --> 00:05:33,460 >> JASON Hirschhorn: A показалеца на една възлова точка, както е посочено от този възел * тук. 113 00:05:33,460 --> 00:05:34,800 Така той създава указател към възел. 114 00:05:34,800 --> 00:05:37,490 И кой възел е тя сочеше да, Майкъл? 115 00:05:37,490 --> 00:05:38,440 >> ПУБЛИКАТА: New възел? 116 00:05:38,440 --> 00:05:39,240 >> JASON Hirschhorn: New възел. 117 00:05:39,240 --> 00:05:43,020 И това сочи там, защото сме го е дал адреса на нов възел. 118 00:05:43,020 --> 00:05:45,820 И сега, в този ред ние виждаме два различни начина на 119 00:05:45,820 --> 00:05:46,910 изразяване на едно и също нещо. 120 00:05:46,910 --> 00:05:49,650 И аз исках да подчертая, как тези две неща са еднакви. 121 00:05:49,650 --> 00:05:54,740 В първия ред, ние сочените показалеца. 122 00:05:54,740 --> 00:05:55,830 Така че отиваме към възела. 123 00:05:55,830 --> 00:05:56,830 Ето какво означава тази звезда. 124 00:05:56,830 --> 00:05:57,930 Виждали сме, че преди с указатели. 125 00:05:57,930 --> 00:05:59,280 Отиди на този възел. 126 00:05:59,280 --> 00:06:00,370 Това е в скоби. 127 00:06:00,370 --> 00:06:04,610 И тогава достъп чрез оператора точка н елемент на този възел. 128 00:06:04,610 --> 00:06:08,430 >> Така че това е като синтаксиса видяхме точно тук и сега 129 00:06:08,430 --> 00:06:09,670 го използвате с показалец. 130 00:06:09,670 --> 00:06:13,730 Разбира се, той получава малко зает, ако пишеш тези скоби - 131 00:06:13,730 --> 00:06:14,940 тази звезда и тази точка. 132 00:06:14,940 --> 00:06:16,220 Той получава малко зает. 133 00:06:16,220 --> 00:06:18,500 Така че ние имаме някаква синтактична захар. 134 00:06:18,500 --> 00:06:19,920 И тази линия точно тук - 135 00:06:19,920 --> 00:06:21,170 ptr_node-> п. 136 00:06:21,170 --> 00:06:25,400 137 00:06:25,400 --> 00:06:28,000 Това прави същото нещо точно. 138 00:06:28,000 --> 00:06:30,840 Така че тези два реда код са еквивалент и ще направя 139 00:06:30,840 --> 00:06:31,650 точно същото нещо. 140 00:06:31,650 --> 00:06:34,210 >> Но аз исках да посоча тези от преди да отиде по-нататък, така че да се разбере 141 00:06:34,210 --> 00:06:39,000 че наистина това нещо точно тук е синтактична захар за dereferencing 142 00:06:39,000 --> 00:06:44,200 показалеца и след това ще н част от тази структура. 143 00:06:44,200 --> 00:06:45,525 Всякакви въпроси за този кадър? 144 00:06:45,525 --> 00:06:53,020 145 00:06:53,020 --> 00:06:54,390 OK. 146 00:06:54,390 --> 00:06:58,510 >> Така че ние ще мине през няколко на операции, които можете да направите, за 147 00:06:58,510 --> 00:06:59,730 свързани списъци. 148 00:06:59,730 --> 00:07:05,770 A свързан списък, изземване, е поредица от възли, които сочат един към друг. 149 00:07:05,770 --> 00:07:12,470 И ние обикновено започват с показалец наречен главата, обикновено, който сочи към 150 00:07:12,470 --> 00:07:14,040 Първото нещо в списъка. 151 00:07:14,040 --> 00:07:18,900 Така че, на първа линия тук, ние Разполагаме със оригиналната L първото. 152 00:07:18,900 --> 00:07:21,370 Така че нещо, което можете да се сетите - това текст точно тук можеш да се сетиш като 153 00:07:21,370 --> 00:07:23,560 само показалеца сме съхраняват някъде, че точки 154 00:07:23,560 --> 00:07:24,670 на първия елемент. 155 00:07:24,670 --> 00:07:27,500 И в този свързан списък имаме четири възли. 156 00:07:27,500 --> 00:07:29,530 Всеки възел е голяма кутия. 157 00:07:29,530 --> 00:07:33,430 Колкото по-голям прозорец вътре в големите кутия е цялата част. 158 00:07:33,430 --> 00:07:37,400 И тогава имаме показалка част. 159 00:07:37,400 --> 00:07:39,630 >> Тези кутии не са привлечени от мащаб, защото колко голям е 160 00:07:39,630 --> 00:07:42,320 цяло число в байтове? 161 00:07:42,320 --> 00:07:43,290 Колко голям сега? 162 00:07:43,290 --> 00:07:43,710 Four. 163 00:07:43,710 --> 00:07:45,470 И колко голяма е указател? 164 00:07:45,470 --> 00:07:45,940 Four. 165 00:07:45,940 --> 00:07:48,180 Така че наистина, ако трябва да се направи това, за да мащабирате двете кутии 166 00:07:48,180 --> 00:07:49,690 ще бъде със същия размер. 167 00:07:49,690 --> 00:07:52,870 В този случай, ние искаме да вмъкнете нещо в свързан списък. 168 00:07:52,870 --> 00:07:57,190 Така че можете да видите тук сме вмъкване Ние траверса през пет на 169 00:07:57,190 --> 00:08:01,310 свързан списък, да намерите, където пет отива, и след това да я поставите. 170 00:08:01,310 --> 00:08:03,560 >> Да се ​​прекъсне, че надолу и отидете малко по-бавно. 171 00:08:03,560 --> 00:08:05,510 Отивам да сочи към дъската. 172 00:08:05,510 --> 00:08:09,930 Така че ние имаме нашия възел пет че ние сме създали в mallocs. 173 00:08:09,930 --> 00:08:11,190 Защо всички се смеят? 174 00:08:11,190 --> 00:08:12,130 Шегувам се. 175 00:08:12,130 --> 00:08:13,310 OK. 176 00:08:13,310 --> 00:08:14,820 Така че ние сме malloced пет. 177 00:08:14,820 --> 00:08:16,310 Ние създадохме този възел някъде другаде. 178 00:08:16,310 --> 00:08:17,740 Ние имаме готовност да отида. 179 00:08:17,740 --> 00:08:20,130 Започваме в предната част нашия списък с две. 180 00:08:20,130 --> 00:08:22,380 И ние искаме да вмъкнете в сортиран мода. 181 00:08:22,380 --> 00:08:27,550 >> Така че, ако ние виждаме две, а ние искаме да се сложи в пет, какво ще правим, когато видим 182 00:08:27,550 --> 00:08:28,800 нещо по-малко от нас? 183 00:08:28,800 --> 00:08:31,850 184 00:08:31,850 --> 00:08:33,520 Какво? 185 00:08:33,520 --> 00:08:36,750 Искаме да вмъкнете пет в тази свързан списък, като ги сортират. 186 00:08:36,750 --> 00:08:37,520 Виждаме номер две. 187 00:08:37,520 --> 00:08:38,769 И така, какво ще правим? 188 00:08:38,769 --> 00:08:39,179 Marcus? 189 00:08:39,179 --> 00:08:40,679 >> ПУБЛИКАТА: Обадете се на показалеца на следващия възел. 190 00:08:40,679 --> 00:08:42,530 >> JASON Hirschhorn: И защо правим отиваме към следващия? 191 00:08:42,530 --> 00:08:45,970 >> ПУБЛИКАТА: Защото това е следващия възел в списъка. 192 00:08:45,970 --> 00:08:48,310 И ние знаем само, че на друго място. 193 00:08:48,310 --> 00:08:50,410 >> JASON Hirschhorn: И пет е по-голяма от две, по-специално. 194 00:08:50,410 --> 00:08:51,600 Тъй като ние искаме да я държи сортирани. 195 00:08:51,600 --> 00:08:52,730 Така пет е по-голямо от две. 196 00:08:52,730 --> 00:08:54,460 Така че ние се премине към следващия. 197 00:08:54,460 --> 00:08:55,240 И сега стигаме до четири. 198 00:08:55,240 --> 00:08:56,490 И какво се случва, когато достигнем четири? 199 00:08:56,490 --> 00:08:58,920 200 00:08:58,920 --> 00:09:00,310 >> Пет е по-голям от четири. 201 00:09:00,310 --> 00:09:01,460 Така че ние продължаваме. 202 00:09:01,460 --> 00:09:03,110 И сега сме на шест. 203 00:09:03,110 --> 00:09:04,360 И какво виждаме в шест? 204 00:09:04,360 --> 00:09:08,672 205 00:09:08,672 --> 00:09:09,608 Да, Карлос? 206 00:09:09,608 --> 00:09:10,544 >> ПУБЛИКАТА: Six е по-голям от пет. 207 00:09:10,544 --> 00:09:11,480 >> JASON Hirschhorn: Six е по-голяма от пет. 208 00:09:11,480 --> 00:09:13,660 Така че това е мястото, където ние искаме да вмъкнете пет. 209 00:09:13,660 --> 00:09:17,320 Все пак, имайте предвид, че ако ние имат само една показалка тук - 210 00:09:17,320 --> 00:09:19,840 това е нашата допълнително указател, който е преминаващи през списъка. 211 00:09:19,840 --> 00:09:21,860 И ние, сочещи към шест. 212 00:09:21,860 --> 00:09:25,010 Ние сме загубили следите какво идва преди шест. 213 00:09:25,010 --> 00:09:29,130 Така че, ако искаме да поставите нещо в този списък да бъдат пазени подредени, ние 214 00:09:29,130 --> 00:09:31,630 вероятно трябва колко указатели? 215 00:09:31,630 --> 00:09:32,280 >> ПУБЛИКАТА: Two. 216 00:09:32,280 --> 00:09:32,920 >> JASON HIRSCHORN: Two. 217 00:09:32,920 --> 00:09:35,720 One, за да следите на тока един и една, за да следите на 218 00:09:35,720 --> 00:09:37,050 предишната. 219 00:09:37,050 --> 00:09:38,450 Това е само поединично свързан списък. 220 00:09:38,450 --> 00:09:39,670 Той отива само една посока. 221 00:09:39,670 --> 00:09:43,220 Ако имахме двойно свързан списък, където всичко сочеше към нещо 222 00:09:43,220 --> 00:09:46,240 след него и нещо пред нея, а след това ние няма да се наложи да го направя. 223 00:09:46,240 --> 00:09:49,350 Но в този случай, ние не искаме да загубим следите на това, което са били преди нас, в случай 224 00:09:49,350 --> 00:09:53,350 ние трябва да поставите пет някъде в средата. 225 00:09:53,350 --> 00:09:55,610 Кажете ни поставяте девет. 226 00:09:55,610 --> 00:09:57,260 Какво ще се случи, когато стигнахме до осем? 227 00:09:57,260 --> 00:10:01,860 228 00:10:01,860 --> 00:10:04,880 >> ПУБЛИКАТА: Вие ще трябва да получи, че нулевата точка. 229 00:10:04,880 --> 00:10:07,820 Вместо да се налага нулевата точка ще трябва да добавят елемент и след това да 230 00:10:07,820 --> 00:10:09,216 го насочите към девет. 231 00:10:09,216 --> 00:10:09,700 >> JASON HIRSCHORN: Точно така. 232 00:10:09,700 --> 00:10:10,600 Така получаваме осем. 233 00:10:10,600 --> 00:10:13,140 Стигаме до края на списъка, защото това сочи към нула. 234 00:10:13,140 --> 00:10:16,330 И сега, вместо да се налага да го насочите към нищожна имаме го насочите към нашия нов възел. 235 00:10:16,330 --> 00:10:19,870 И ние настроите курсора в нашият нов възел към нула. 236 00:10:19,870 --> 00:10:21,445 Дали някой има някакви въпроси относно поставянето? 237 00:10:21,445 --> 00:10:25,620 238 00:10:25,620 --> 00:10:28,100 Какво става, ако не се грижи за актуализирането на списъка подредени? 239 00:10:28,100 --> 00:10:31,701 240 00:10:31,701 --> 00:10:34,350 >> ПУБЛИКАТА: тя Придържайте в началото или в края. 241 00:10:34,350 --> 00:10:35,510 >> JASON HIRSCHORN: тя Придържайте се към в началото или в края. 242 00:10:35,510 --> 00:10:37,276 Кой трябва да направим? 243 00:10:37,276 --> 00:10:38,770 Боби? 244 00:10:38,770 --> 00:10:41,020 Защо в края? 245 00:10:41,020 --> 00:10:43,250 >> ПУБЛИКАТА: Защото началото вече е запълнена. 246 00:10:43,250 --> 00:10:43,575 >> JASON HIRSCHORN: OK. 247 00:10:43,575 --> 00:10:44,360 Началото е вече запълнени. 248 00:10:44,360 --> 00:10:46,090 Кой иска да се спори срещу Боби. 249 00:10:46,090 --> 00:10:47,290 Marcus. 250 00:10:47,290 --> 00:10:48,910 >> ПУБЛИКАТА: Ами вие може би искате да го залепите в началото, защото 251 00:10:48,910 --> 00:10:50,140 в противен случай, ако го сложите в края на краищата вие ще трябва да 252 00:10:50,140 --> 00:10:51,835 прекосяват целия списък. 253 00:10:51,835 --> 00:10:52,990 >> JASON HIRSCHORN: Точно така. 254 00:10:52,990 --> 00:10:57,970 Така че, ако мислим по време на работа, на Времетраене на вмъкване в края 255 00:10:57,970 --> 00:11:00,110 ще бъде N, размерът на това. 256 00:11:00,110 --> 00:11:03,080 Каква е голямата O време на работа на вмъкване в началото? 257 00:11:03,080 --> 00:11:04,170 Constant време. 258 00:11:04,170 --> 00:11:07,075 Така че, ако не ви е грижа за запазване на нещо, подредени, много по-добре просто да си 259 00:11:07,075 --> 00:11:08,420 поставите в началото на този списък. 260 00:11:08,420 --> 00:11:10,320 И това може да бъде направено в константно време. 261 00:11:10,320 --> 00:11:13,900 262 00:11:13,900 --> 00:11:14,690 >> OK. 263 00:11:14,690 --> 00:11:18,870 Следваща операция се намери, кой друг - сме изразил това като търсене. 264 00:11:18,870 --> 00:11:22,470 Но ние ще разгледаме през свързан списък за някакъв предмет. 265 00:11:22,470 --> 00:11:26,000 Вие, момчета, са видели код за търси преди в лекция. 266 00:11:26,000 --> 00:11:29,490 Но ние някак просто го направих с вмъкнете, или най-малко вмъкване 267 00:11:29,490 --> 00:11:30,580 нещо подредени. 268 00:11:30,580 --> 00:11:36,350 Можете да потърсите чрез, ще възел от възел, докато не се намери номера, който сте 269 00:11:36,350 --> 00:11:37,780 търсите. 270 00:11:37,780 --> 00:11:39,670 Какво се случва, ако достигнете на края на списъка? 271 00:11:39,670 --> 00:11:43,020 Кажете Търся девет и аз стигнат до края на списъка. 272 00:11:43,020 --> 00:11:44,270 Какво ще правим? 273 00:11:44,270 --> 00:11:47,147 274 00:11:47,147 --> 00:11:48,110 >> ПУБЛИКАТА: Завръщане невярно? 275 00:11:48,110 --> 00:11:48,690 >> JASON HIRSCHORN: връщане фалшиви. 276 00:11:48,690 --> 00:11:49,960 Ние не го намери. 277 00:11:49,960 --> 00:11:52,010 Ако стигнете до края на списъка и не сте намерили номера, който сте 278 00:11:52,010 --> 00:11:54,170 търсите, не е там. 279 00:11:54,170 --> 00:11:55,420 Всякакви въпроси за намиране? 280 00:11:55,420 --> 00:11:59,530 281 00:11:59,530 --> 00:12:04,615 Ако това е сортиран списък, какво би да бъде различен за нашия търсенето? 282 00:12:04,615 --> 00:12:07,370 283 00:12:07,370 --> 00:12:08,103 Да. 284 00:12:08,103 --> 00:12:10,600 >> ПУБЛИКАТА: Би намерите първата стойност това е по-голям от този 285 00:12:10,600 --> 00:12:12,390 , което търсите и след това връщане фалшиви. 286 00:12:12,390 --> 00:12:13,190 >> JASON HIRSCHORN: Точно така. 287 00:12:13,190 --> 00:12:17,310 Така че, ако това е сортиран списък, ако искаме да стигнем до нещо, което е по-голямо от това, което 288 00:12:17,310 --> 00:12:20,180 търсим, ние не трябва да продължавай до края на списъка. 289 00:12:20,180 --> 00:12:24,060 Ние можем в този момент връщане фалшиви защото ние няма да го намерите. 290 00:12:24,060 --> 00:12:27,340 Въпросът е сега, ние сме говорили за водене свързани списъци подредени, 291 00:12:27,340 --> 00:12:28,180 поддържането им несортиран. 292 00:12:28,180 --> 00:12:30,050 Това ще бъде нещо, което сте вероятно ще трябва да се мисли за 293 00:12:30,050 --> 00:12:34,240 при кодиране проблем зададете пет, ако изберем хеш таблица с отделен 294 00:12:34,240 --> 00:12:36,360 верижното подход, който ние ще говорим за това по-късно. 295 00:12:36,360 --> 00:12:41,400 >> Но то си струва да се запази списъкът сортирани и след това да бъде в състояние да може да има 296 00:12:41,400 --> 00:12:42,310 бързи търсения? 297 00:12:42,310 --> 00:12:47,220 Или е по-добре бързо да вмъкнете нещо в постоянна по време на работа, но след това 298 00:12:47,220 --> 00:12:48,430 Трябва вече да търсите? 299 00:12:48,430 --> 00:12:52,250 Това е компромис точно там, че вие се да се реши кое е по-подходящо 300 00:12:52,250 --> 00:12:53,590 за вашия конкретен проблем. 301 00:12:53,590 --> 00:12:56,680 И там не е непременно едно абсолютно правилен отговор. 302 00:12:56,680 --> 00:12:59,520 Но със сигурност това е решение, вие получавате да се направи, и вероятно е добре да защитава 303 00:12:59,520 --> 00:13:05,270 че, да речем, коментар или две защо вие избрахте една върху друга. 304 00:13:05,270 --> 00:13:06,490 >> Накрая, изтриване. 305 00:13:06,490 --> 00:13:08,100 Виждали сме изтриване. 306 00:13:08,100 --> 00:13:09,180 Той е подобен на търсенето. 307 00:13:09,180 --> 00:13:11,020 За елемента Ние с нетърпение. 308 00:13:11,020 --> 00:13:12,390 Да кажем, че се опитвате да изтриете шест. 309 00:13:12,390 --> 00:13:14,450 Така ние откриваме шест точно тук. 310 00:13:14,450 --> 00:13:18,860 Това, което ние трябва да сме сигурни, че направите, е, че каквото и да се посочи 311 00:13:18,860 --> 00:13:21,220 шест - както виждаме в стъпка две тук - 312 00:13:21,220 --> 00:13:26,500 каквото и да сочи на шест нужди на пропуснете шест сега и да се промени, за да 313 00:13:26,500 --> 00:13:28,160 каквото и шест сочи. 314 00:13:28,160 --> 00:13:31,410 Ние не искаме да някога сираци в останалата част от нашия списък, забравяйки, че за да зададете 315 00:13:31,410 --> 00:13:32,960 предишния показалка. 316 00:13:32,960 --> 00:13:35,960 И след това понякога, в зависимост на програмата, те просто ще 317 00:13:35,960 --> 00:13:37,380 изтриете този възел изцяло. 318 00:13:37,380 --> 00:13:40,135 Понякога вие ще искате да се върнете стойността, която е в този възел. 319 00:13:40,135 --> 00:13:42,490 Така че това е начина, изтриване произведения. 320 00:13:42,490 --> 00:13:44,610 Всякакви въпроси за изтриване? 321 00:13:44,610 --> 00:13:51,280 322 00:13:51,280 --> 00:13:53,850 >> ПУБЛИКАТА: Така че, ако ти започваш да се изтрие това, бихте ли просто да използвате безплатно, защото 323 00:13:53,850 --> 00:13:55,655 вероятно е malloced? 324 00:13:55,655 --> 00:13:57,976 >> JASON HIRSCHORN: Ако искате да освободите нещо, което е точно така и вие 325 00:13:57,976 --> 00:13:58,540 тя malloced. 326 00:13:58,540 --> 00:14:00,410 Да кажем, че иска да се върне тази стойност. 327 00:14:00,410 --> 00:14:04,010 Ние може да върне шест и след това безплатно този възел и безплатен разговор върху него. 328 00:14:04,010 --> 00:14:06,180 Или най-вероятно ще се обадиш безплатно първи и след това се върнете шест. 329 00:14:06,180 --> 00:14:11,210 330 00:14:11,210 --> 00:14:11,580 >> OK. 331 00:14:11,580 --> 00:14:14,010 Така че, нека продължим да практикуват кодиране. 332 00:14:14,010 --> 00:14:16,090 Отиваме да се кодира три функции. 333 00:14:16,090 --> 00:14:18,260 Първият се нарича insert_node. 334 00:14:18,260 --> 00:14:22,170 Така че имате код, който аз ви емайл, и ако гледате това по-късно 335 00:14:22,170 --> 00:14:28,020 можете да получите достъп до кода в linked.c на интернет страницата на CS50. 336 00:14:28,020 --> 00:14:30,880 Но в linked.c, има някои скелет код, който вече е 337 00:14:30,880 --> 00:14:32,280 е написана за вас. 338 00:14:32,280 --> 00:14:34,560 И след това има няколко функции Вие трябва да напишете. 339 00:14:34,560 --> 00:14:36,380 >> Първо отиваме в напиши insert_node. 340 00:14:36,380 --> 00:14:39,800 И какво прави insert_node т.е. вмъква число. 341 00:14:39,800 --> 00:14:42,440 И ти даде цялото число в свързан списък. 342 00:14:42,440 --> 00:14:45,470 И по-специално, което трябва да актуализира списъка сортирано 343 00:14:45,470 --> 00:14:47,650 от най-малкия до най-големия. 344 00:14:47,650 --> 00:14:51,360 Също така, вие не искате да пъхайте никакви дубликати. 345 00:14:51,360 --> 00:14:54,600 И накрая, както можете да видите insert_node връща булев. 346 00:14:54,600 --> 00:14:57,140 Така че би трябвало да позволи на потребителите да знаят, дали вложката е или не 347 00:14:57,140 --> 00:15:00,800 успешно чрез връщане вярно или невярно. 348 00:15:00,800 --> 00:15:02,580 В края на тази програма - 349 00:15:02,580 --> 00:15:05,750 и за този етап не е нужно да се притеснявате за освобождаването нищо. 350 00:15:05,750 --> 00:15:11,790 Така че всичко, което правим, е като цяло число и да го поставите в списък. 351 00:15:11,790 --> 00:15:13,890 >> Това е, което аз те моля да направиш сега. 352 00:15:13,890 --> 00:15:17,620 Отново, в linked.c, която ви Всички имаме, е кода на скелет. 353 00:15:17,620 --> 00:15:20,980 И вие трябва да видите към дъното Декларацията функция на пробата. 354 00:15:20,980 --> 00:15:27,390 Въпреки това, преди да отиде в това кодиране в C, аз силно ви препоръчваме да отидете 355 00:15:27,390 --> 00:15:29,330 през стъпките, ние сме били практикуване на всяка седмица. 356 00:15:29,330 --> 00:15:31,100 Ние вече сме преминали през снимка на това. 357 00:15:31,100 --> 00:15:33,380 Така че трябва да има някакво разбиране за това как работи това. 358 00:15:33,380 --> 00:15:36,590 Но бих искал да ви насърча да напишете някои pseudocode преди гмуркане инча 359 00:15:36,590 --> 00:15:38,640 И ние ще отидем pseudocode като група. 360 00:15:38,640 --> 00:15:41,470 И след това, след като сте написали pseudocode, и след като сме написали нашата 361 00:15:41,470 --> 00:15:45,850 pseudocode като група, можете да навлизам в кодиране в C. 362 00:15:45,850 --> 00:15:49,980 >> Както главите, функцията insert_node е може би най-трудните от 363 00:15:49,980 --> 00:15:53,550 тримата отиваме да пиша, защото аз добавя някои допълнителни ограничения за 364 00:15:53,550 --> 00:15:57,190 програмирането, по-специално, че вие няма да вмъкнете всеки 365 00:15:57,190 --> 00:15:59,880 дубликати и че списъкът трябва да остане сортирани. 366 00:15:59,880 --> 00:16:02,660 Така че това е не-тривиално програма че трябва да се кодира. 367 00:16:02,660 --> 00:16:06,470 И защо не си вземеш 5-7 минути само за да се работи по 368 00:16:06,470 --> 00:16:07,640 pseudocode и кода. 369 00:16:07,640 --> 00:16:09,460 И тогава ние ще започнем става като група. 370 00:16:09,460 --> 00:16:11,680 Отново, ако имате някакви въпроси, просто вдигнете ръката си и аз ще дойда на мача. 371 00:16:11,680 --> 00:16:15,258 372 00:16:15,258 --> 00:16:16,508 . 373 00:16:16,508 --> 00:18:28,370 374 00:18:28,370 --> 00:18:30,120 >> Ние също така по принцип правят тези - 375 00:18:30,120 --> 00:18:32,070 или аз не изрично ви кажа може да работи с хора. 376 00:18:32,070 --> 00:18:36,500 Но очевидно, аз силно Ви препоръчваме, ако имате въпроси, да поиска от 377 00:18:36,500 --> 00:18:39,840 съсед седи до вас или дори да работя с някой 378 00:18:39,840 --> 00:18:40,510 иначе, ако искате да. 379 00:18:40,510 --> 00:18:42,600 Това не трябва да бъде индивидуално тиха дейност. 380 00:18:42,600 --> 00:20:11,770 381 00:20:11,770 --> 00:20:16,330 >> Нека да започнем с писането на някои pseudocode на дъската. 382 00:20:16,330 --> 00:20:19,395 Кой може да ми даде на първа линия на pseudocode за тази програма? 383 00:20:19,395 --> 00:20:22,240 384 00:20:22,240 --> 00:20:23,640 За тази функция, а - insert_node. 385 00:20:23,640 --> 00:20:29,960 386 00:20:29,960 --> 00:20:31,830 Алдън? 387 00:20:31,830 --> 00:20:36,560 >> ПУБЛИКАТА: Така че първото нещо, което направих беше създадете нов указател към възела и I 388 00:20:36,560 --> 00:20:41,320 инициализира го насочите към една и съща нещо, че този списък е предната. 389 00:20:41,320 --> 00:20:41,550 >> JASON HIRSCHORN: OK. 390 00:20:41,550 --> 00:20:45,190 Значи вие създавате нов показалец в списъка не към възела. 391 00:20:45,190 --> 00:20:45,420 >> ПУБЛИКАТА: Точно така. 392 00:20:45,420 --> 00:20:46,150 Да. 393 00:20:46,150 --> 00:20:46,540 >> JASON HIRSCHORN: OK. 394 00:20:46,540 --> 00:20:48,221 И след това какво искаме да направим? 395 00:20:48,221 --> 00:20:49,163 Какво след това? 396 00:20:49,163 --> 00:20:50,105 Ами възел? 397 00:20:50,105 --> 00:20:51,050 Ние не разполагаме с един възел. 398 00:20:51,050 --> 00:20:52,300 Ние просто имат стойност. 399 00:20:52,300 --> 00:20:55,918 400 00:20:55,918 --> 00:20:58,890 Ако искаме да вмъкнете възел, това, което правим трябва да направите първо, преди да можем дори 401 00:20:58,890 --> 00:20:59,980 мисля за да го поставите? 402 00:20:59,980 --> 00:21:00,820 >> ПУБЛИКАТА: О, съжалявам. 403 00:21:00,820 --> 00:21:02,160 ние трябва да се изчистване пространство за един възел. 404 00:21:02,160 --> 00:21:02,455 >> JASON HIRSCHORN: Отлично. 405 00:21:02,455 --> 00:21:03,210 Нека да направим - 406 00:21:03,210 --> 00:21:04,628 OK. 407 00:21:04,628 --> 00:21:06,065 Не може да се достигне до това високо. 408 00:21:06,065 --> 00:21:08,939 409 00:21:08,939 --> 00:21:09,897 OK. 410 00:21:09,897 --> 00:21:13,236 Отиваме да слезем, и след това ние използваме две колони. 411 00:21:13,236 --> 00:21:13,732 Аз не мога да отида, че - 412 00:21:13,732 --> 00:21:14,982 OK. 413 00:21:14,982 --> 00:21:23,660 414 00:21:23,660 --> 00:21:25,130 Създаване на нов възел. 415 00:21:25,130 --> 00:21:29,380 Можете да създадете друг показалеца да се изброят или можете просто да използвате списък, тъй като съществува. 416 00:21:29,380 --> 00:21:30,720 Вие наистина не трябва да правиш това. 417 00:21:30,720 --> 00:21:31,750 >> Така че ние създаваме нов възел. 418 00:21:31,750 --> 00:21:32,010 Чудесно. 419 00:21:32,010 --> 00:21:32,840 Това е, което правим на първо място. 420 00:21:32,840 --> 00:21:34,870 Каква е следващата? 421 00:21:34,870 --> 00:21:35,080 >> ПУБЛИКАТА: Изчакайте. 422 00:21:35,080 --> 00:21:38,330 Трябва ли да се създаде нов възел сега или трябва да чакаме, за да се уверите, че 423 00:21:38,330 --> 00:21:42,260 няма никакви дубликати на възела в списъка, преди да я създадете? 424 00:21:42,260 --> 00:21:43,100 >> JASON HIRSCHORN: Добър въпрос. 425 00:21:43,100 --> 00:21:47,770 Да твърдим, че за по-късно, тъй като мнозинство от времето ще бъде създаването на 426 00:21:47,770 --> 00:21:48,220 нов възел. 427 00:21:48,220 --> 00:21:49,110 Така че ние ще продължаваме, че тук. 428 00:21:49,110 --> 00:21:51,006 Но това е добър въпрос. 429 00:21:51,006 --> 00:21:53,250 Ако можем да го създадем и ние намираме дубликат, какво трябва 430 00:21:53,250 --> 00:21:54,490 правим преди да се върне? 431 00:21:54,490 --> 00:21:55,190 >> ПУБЛИКАТА: то безплатно. 432 00:21:55,190 --> 00:21:55,470 >> JASON HIRSCHORN: Да. 433 00:21:55,470 --> 00:21:56,500 Вероятно го освободи. 434 00:21:56,500 --> 00:21:56,760 OK. 435 00:21:56,760 --> 00:21:59,850 Какво ще правим след като сме създаване на нов възел? 436 00:21:59,850 --> 00:22:02,260 Ани? 437 00:22:02,260 --> 00:22:04,780 >> ПУБЛИКАТА: Слагаме брой в възел? 438 00:22:04,780 --> 00:22:05,140 >> JASON HIRSCHORN: Точно така. 439 00:22:05,140 --> 00:22:07,190 Ние поставяме броя - ние изчистване пространство. 440 00:22:07,190 --> 00:22:08,160 Отивам да напуснат тази всичко като една линия. 441 00:22:08,160 --> 00:22:08,720 Но ти си прав. 442 00:22:08,720 --> 00:22:10,305 Ние изчистване пространство, а след това ние поставяме броя инча 443 00:22:10,305 --> 00:22:12,585 Ние дори да настроите курсора част от него нула. 444 00:22:12,585 --> 00:22:13,720 Това е точно така. 445 00:22:13,720 --> 00:22:17,400 И тогава какво да кажем след това? 446 00:22:17,400 --> 00:22:18,490 Ние извади тази снимка на дъската. 447 00:22:18,490 --> 00:22:21,190 И така, какво ще правим? 448 00:22:21,190 --> 00:22:22,680 >> ПУБЛИКАТА: Отиваме в списъка. 449 00:22:22,680 --> 00:22:23,930 >> JASON HIRSCHORN: Преминете през списъка. 450 00:22:23,930 --> 00:22:30,620 451 00:22:30,620 --> 00:22:31,100 OK. 452 00:22:31,100 --> 00:22:34,280 И какво ще се проверява за най-всеки възел. 453 00:22:34,280 --> 00:22:35,955 Кърт, какво ще покажат в продължение на всеки възел? 454 00:22:35,955 --> 00:22:41,640 >> ПУБЛИКАТА: Виж дали стойността на п на този възел е по-голяма от стойността на п 455 00:22:41,640 --> 00:22:43,070 на нашия възел. 456 00:22:43,070 --> 00:22:43,340 >> JASON HIRSCHORN: OK. 457 00:22:43,340 --> 00:22:44,280 Отивам да се направи - 458 00:22:44,280 --> 00:22:45,855 Да, OK. 459 00:22:45,855 --> 00:22:48,160 Така че това е п - 460 00:22:48,160 --> 00:22:59,040 Отивам да се каже, ако стойността е по-голяма от този възел, тогава какво ще правим? 461 00:22:59,040 --> 00:23:07,290 >> ПУБЛИКАТА: Е, тогава ние вмъкнете нещото точно преди това. 462 00:23:07,290 --> 00:23:07,970 >> JASON HIRSCHORN: OK. 463 00:23:07,970 --> 00:23:09,410 Така че, ако това е по-голяма от тази, След това ние искаме да вмъкнете. 464 00:23:09,410 --> 00:23:14,010 Но ние искаме да го поставите точно преди защото ние също ще трябва да бъде 465 00:23:14,010 --> 00:23:16,070 следенето, а след това, от това, което беше преди. 466 00:23:16,070 --> 00:23:22,690 Така че, преди да вмъкнете. 467 00:23:22,690 --> 00:23:25,120 Така че ние вероятно пропуснал нещо по-рано. 468 00:23:25,120 --> 00:23:27,770 Ние вероятно трябва да се поддържа следите какво се случва. 469 00:23:27,770 --> 00:23:28,460 Но ние ще се върнем там. 470 00:23:28,460 --> 00:23:30,160 Така че каква стойност е по-малко от? 471 00:23:30,160 --> 00:23:38,030 472 00:23:38,030 --> 00:23:39,710 Кърт, какво ще правим, ако стойност е по-малко от? 473 00:23:39,710 --> 00:23:43,000 >> ПУБЛИКАТА: Тогава просто продължавай освен ако това е последният. 474 00:23:43,000 --> 00:23:43,550 >> JASON HIRSCHORN: Това ми харесва. 475 00:23:43,550 --> 00:23:44,800 Така че отидете на следващия възел. 476 00:23:44,800 --> 00:23:47,410 477 00:23:47,410 --> 00:23:48,930 Освен ако това е последният - 478 00:23:48,930 --> 00:23:51,100 Вероятно сме проверка за това в условията на състояние. 479 00:23:51,100 --> 00:23:54,870 Но да, следващия възел. 480 00:23:54,870 --> 00:23:58,680 И това става прекалено ниско, така че ние ще се премести тук. 481 00:23:58,680 --> 00:24:02,030 Но ако - 482 00:24:02,030 --> 00:24:03,280 Всеки ли може да видите това? 483 00:24:03,280 --> 00:24:07,230 484 00:24:07,230 --> 00:24:11,610 Ако сме равни, какво ще правим? 485 00:24:11,610 --> 00:24:15,740 Ако стойността, която се опитвате да вмъкнете е равна на стойността на този възел? 486 00:24:15,740 --> 00:24:16,320 Да? 487 00:24:16,320 --> 00:24:18,400 >> ПУБЛИКАТА: [недоловим]. 488 00:24:18,400 --> 00:24:18,850 >> JASON HIRSCHORN: Да. 489 00:24:18,850 --> 00:24:19,290 Като се има предвид това - 490 00:24:19,290 --> 00:24:20,090 Маркъс е прав. 491 00:24:20,090 --> 00:24:21,330 Бихме могли да са може би направил нещо по-различно. 492 00:24:21,330 --> 00:24:25,360 Но имайки предвид, че сме го създали, тук ние трябва да освободим и след това се върнете. 493 00:24:25,360 --> 00:24:26,774 О, момче. 494 00:24:26,774 --> 00:24:30,080 Така по-добре? 495 00:24:30,080 --> 00:24:31,850 Как е това? 496 00:24:31,850 --> 00:24:33,100 OK. 497 00:24:33,100 --> 00:24:35,360 498 00:24:35,360 --> 00:24:37,640 Свободна и тогава какво правим се върне, [недоловим]? 499 00:24:37,640 --> 00:24:41,330 500 00:24:41,330 --> 00:24:44,110 OK. 501 00:24:44,110 --> 00:24:45,360 Да не пропускаме нещо? 502 00:24:45,360 --> 00:24:53,500 503 00:24:53,500 --> 00:24:59,650 И така, къде сме следенето на предварително възел? 504 00:24:59,650 --> 00:25:02,370 >> ПУБЛИКАТА: Мисля, че ще отида след създаване на нов възел. 505 00:25:02,370 --> 00:25:02,600 >> JASON HIRSCHORN: OK. 506 00:25:02,600 --> 00:25:03,940 Така че в началото ние ще вероятно - 507 00:25:03,940 --> 00:25:07,175 Да, ние можем да създадем указател към нов възел, като предишния показалеца възел и 508 00:25:07,175 --> 00:25:09,600 текущ показалка възел. 509 00:25:09,600 --> 00:25:12,640 Така че нека да вмъкнете, че тук. 510 00:25:12,640 --> 00:25:15,610 511 00:25:15,610 --> 00:25:26,900 Създаване на текущата и предходната указатели към възли. 512 00:25:26,900 --> 00:25:28,955 Но кога ще коригира тези насоки? 513 00:25:28,955 --> 00:25:30,205 Когато правим това в кода? 514 00:25:30,205 --> 00:25:33,830 515 00:25:33,830 --> 00:25:34,160 Джеф? 516 00:25:34,160 --> 00:25:35,170 >> ПУБЛИКАТА: - условия стойност? 517 00:25:35,170 --> 00:25:36,420 >> JASON HIRSCHORN: Кои един по-специално? 518 00:25:36,420 --> 00:25:39,862 519 00:25:39,862 --> 00:25:40,720 >> ПУБЛИКАТА: Аз съм просто объркан. 520 00:25:40,720 --> 00:25:44,200 Ако е по-голяма от тази възлова точка, не искаш да кажеш, че искаш да отидеш 521 00:25:44,200 --> 00:25:45,320 на следващия възел? 522 00:25:45,320 --> 00:25:49,515 >> JASON Hirschhorn: Така че, ако нашата стойност е по-голяма от стойността на този възел. 523 00:25:49,515 --> 00:25:52,130 >> Публика: Да, тогава вие ще искате да отиде по-надолу по линията, нали? 524 00:25:52,130 --> 00:25:52,590 >> JASON Hirschhorn: Точно така. 525 00:25:52,590 --> 00:25:53,840 Така че ние не го поставете тук. 526 00:25:53,840 --> 00:25:58,430 527 00:25:58,430 --> 00:26:03,240 Ако стойността е по-малко от този възел, тогава отиваме към следващия възел - или тогава ние 528 00:26:03,240 --> 00:26:03,835 вмъкнете преди. 529 00:26:03,835 --> 00:26:05,966 >> ПУБЛИКАТА: Изчакайте, който е тази възел и което е стойност? 530 00:26:05,966 --> 00:26:08,510 531 00:26:08,510 --> 00:26:09,280 >> JASON Hirschhorn: Добър въпрос. 532 00:26:09,280 --> 00:26:13,260 Стойност на тази дефиниция на функция е това, което е дал. 533 00:26:13,260 --> 00:26:16,910 Така стойност е броят не ни дават. 534 00:26:16,910 --> 00:26:21,120 Така че, ако стойността е по-малка от тази възел, имаме нужда от време, за да вмъкнете. 535 00:26:21,120 --> 00:26:24,575 Ако е по-голяма от тази възлова точка, отиваме към следващия възел. 536 00:26:24,575 --> 00:26:26,790 И обратно към първоначалния въпрос, обаче, когато - 537 00:26:26,790 --> 00:26:29,060 >> ПУБЛИКАТА: Ако стойността е по-голяма от този възел. 538 00:26:29,060 --> 00:26:30,310 >> JASON Hirschhorn: И така, какво правим тук? 539 00:26:30,310 --> 00:26:36,790 540 00:26:36,790 --> 00:26:38,160 Sweet. 541 00:26:38,160 --> 00:26:38,860 Това е правилно. 542 00:26:38,860 --> 00:26:41,370 Аз съм просто ще да пиша актуализиране указатели. 543 00:26:41,370 --> 00:26:44,010 Но да, с ток една бихте го актуализира до 544 00:26:44,010 --> 00:26:46,080 сочи към следващия. 545 00:26:46,080 --> 00:26:47,330 Нещо друго, което ти липсва? 546 00:26:47,330 --> 00:26:52,710 547 00:26:52,710 --> 00:26:54,940 Така че аз отивам да въведете този код в Gedit. 548 00:26:54,940 --> 00:26:58,375 И докато аз правя това, можете да имате още няколко минути, за да работят на кодиране 549 00:26:58,375 --> 00:28:19,240 това в C. 550 00:28:19,240 --> 00:28:20,940 >> Така че аз имам принос за pseudocode. 551 00:28:20,940 --> 00:28:22,940 Един бърз бележка, преди да можем да започнем. 552 00:28:22,940 --> 00:28:25,560 Ние може да не е в състояние напълно да довърша това във всички 553 00:28:25,560 --> 00:28:27,300 три от тези функции. 554 00:28:27,300 --> 00:28:30,630 Има правилни решения за тях че аз ще имейл до вас момчета 555 00:28:30,630 --> 00:28:33,730 След раздел, и тя ще бъде публикуван на CS50.net. 556 00:28:33,730 --> 00:28:35,640 Така че аз не ви препоръчваме да отидете погледнете разделите. 557 00:28:35,640 --> 00:28:40,550 Препоръчвам ви да опитате тези на вашия притежавате, и след това да използвате практиката 558 00:28:40,550 --> 00:28:41,760 проблеми, за да проверите вашите отговори. 559 00:28:41,760 --> 00:28:47,070 Те всички са били предназначени за тясно се отнасят до и да се придържат към това, което 560 00:28:47,070 --> 00:28:48,400 което трябва да направите на снимачната проблем. 561 00:28:48,400 --> 00:28:53,820 Така че аз ви насърчавам да практикува тази на собствения си и след това да използвате кода за 562 00:28:53,820 --> 00:28:54,660 проверите вашите отговори. 563 00:28:54,660 --> 00:28:57,060 Защото аз не искам да се премине към хеш таблици в някакъв момент в секцията. 564 00:28:57,060 --> 00:28:58,150 Така че ние не може да получи през всичко това. 565 00:28:58,150 --> 00:28:59,960 Но ние ще направим колкото можем сега. 566 00:28:59,960 --> 00:29:00,370 >> OK. 567 00:29:00,370 --> 00:29:01,960 Нека да започнем. 568 00:29:01,960 --> 00:29:04,770 Asam, как да създадете нов възел? 569 00:29:04,770 --> 00:29:06,810 >> ПУБЛИКАТА: Нали STRUCT *. 570 00:29:06,810 --> 00:29:09,640 >> JASON Hirschhorn: Така че ние са, че до тук. 571 00:29:09,640 --> 00:29:10,040 О, съжалявам. 572 00:29:10,040 --> 00:29:13,530 Вие казвахте структура *. 573 00:29:13,530 --> 00:29:17,260 >> ПУБЛИКАТА: И тогава [? вид?] възел или в възел. 574 00:29:17,260 --> 00:29:17,780 >> JASON Hirschhorn: OK. 575 00:29:17,780 --> 00:29:19,740 Отивам да го наричат ​​new_node така че ние може да остане последователна. 576 00:29:19,740 --> 00:29:22,646 577 00:29:22,646 --> 00:29:33,180 >> ПУБЛИКАТА: И вие искате да зададете, че с глава, на първия възел. 578 00:29:33,180 --> 00:29:33,580 >> JASON Hirschhorn: OK. 579 00:29:33,580 --> 00:29:37,290 Така че сега това, сочеща - така че това все още не е създаден нов възел. 580 00:29:37,290 --> 00:29:41,380 Това е просто сочещи към първи възел в списъка. 581 00:29:41,380 --> 00:29:42,630 Как да създадете нов възел? 582 00:29:42,630 --> 00:29:45,490 583 00:29:45,490 --> 00:29:48,070 Ако имам нужда от пространство, за да създадете нов възел. 584 00:29:48,070 --> 00:29:49,230 Изчистване. 585 00:29:49,230 --> 00:29:51,710 И колко е голям? 586 00:29:51,710 --> 00:30:00,390 >> ПУБЛИКАТА: Размерът на структурата. 587 00:30:00,390 --> 00:30:01,150 >> JASON Hirschhorn: The размер на структурата. 588 00:30:01,150 --> 00:30:02,400 И това, което се нарича структура? 589 00:30:02,400 --> 00:30:09,670 590 00:30:09,670 --> 00:30:09,840 >> ПУБЛИКАТА: Node? 591 00:30:09,840 --> 00:30:11,640 >> JASON Hirschhorn: Node. 592 00:30:11,640 --> 00:30:17,640 Така изчистване (sizeof (възел)); ни дава пространство. 593 00:30:17,640 --> 00:30:19,740 И е тази линия - 594 00:30:19,740 --> 00:30:21,740 едно нещо е неправилно в тази линия. 595 00:30:21,740 --> 00:30:24,430 Дали new_node указател към структура? 596 00:30:24,430 --> 00:30:25,650 Това е родово име. 597 00:30:25,650 --> 00:30:26,520 Какво е това - 598 00:30:26,520 --> 00:30:27,450 възел, точно така. 599 00:30:27,450 --> 00:30:29,340 Това е възел *. 600 00:30:29,340 --> 00:30:33,010 И какво ще правим веднага след ние изчистване нещо, Асан? 601 00:30:33,010 --> 00:30:34,476 Кое е първото нещо, което правим? 602 00:30:34,476 --> 00:30:38,850 603 00:30:38,850 --> 00:30:40,320 Какво става, ако тя не работи? 604 00:30:40,320 --> 00:30:42,430 >> ПУБЛИКАТА: О, проверете дали точки на възловата точка? 605 00:30:42,430 --> 00:30:43,310 >> JASON Hirschhorn: Точно така. 606 00:30:43,310 --> 00:30:46,750 Така че, ако new_node равнява на равни нищожна, какво ще правим? 607 00:30:46,750 --> 00:30:51,650 608 00:30:51,650 --> 00:30:54,820 Това връща булев, тази функция. 609 00:30:54,820 --> 00:30:57,760 Точно така. 610 00:30:57,760 --> 00:30:58,450 Изглежда добре. 611 00:30:58,450 --> 00:30:59,680 Нещо да добавите там? 612 00:30:59,680 --> 00:31:00,670 Ние ще добавим неща в края. 613 00:31:00,670 --> 00:31:03,160 Но това засега изглежда добре. 614 00:31:03,160 --> 00:31:06,170 Създаване на настоящите и предишните указатели. 615 00:31:06,170 --> 00:31:08,650 Майкъл, как мога да направя това? 616 00:31:08,650 --> 00:31:12,810 >> Публика: Ти нямаше да имаш да направим възел *. 617 00:31:12,810 --> 00:31:21,800 618 00:31:21,800 --> 00:31:25,502 Вие ще трябва да не се направи една за new_node но за 619 00:31:25,502 --> 00:31:26,905 възли, които вече имат. 620 00:31:26,905 --> 00:31:27,230 >> JASON Hirschhorn: OK. 621 00:31:27,230 --> 00:31:29,255 Така текущия възел сме на. 622 00:31:29,255 --> 00:31:30,505 Ще се обадя, че Curr. 623 00:31:30,505 --> 00:31:39,650 624 00:31:39,650 --> 00:31:39,770 Добре. 625 00:31:39,770 --> 00:31:41,620 Решихме, които искате да запазите два, защото ние трябва да знаем 626 00:31:41,620 --> 00:31:42,870 това, което е пред него. 627 00:31:42,870 --> 00:31:45,770 628 00:31:45,770 --> 00:31:47,020 Какво те се инициализира с? 629 00:31:47,020 --> 00:31:49,874 630 00:31:49,874 --> 00:31:54,180 >> ПУБЛИКАТА: стойността им в нашия списък. 631 00:31:54,180 --> 00:31:58,090 >> JASON Hirschhorn: Така че това, което е най- Първото нещо, което в нашия списък? 632 00:31:58,090 --> 00:32:04,050 Или как да знаем, когато началото на нашия списък е? 633 00:32:04,050 --> 00:32:08,015 >> ПУБЛИКАТА: Не е ли мина в функцията? 634 00:32:08,015 --> 00:32:08,466 >> JASON Hirschhorn: Точно така. 635 00:32:08,466 --> 00:32:09,716 Той е приет в точно тук. 636 00:32:09,716 --> 00:32:15,910 637 00:32:15,910 --> 00:32:18,980 Така че, ако това е преминал на функцията, начало на списъка, какво трябва да 638 00:32:18,980 --> 00:32:21,270 настроите ток, равен на? 639 00:32:21,270 --> 00:32:22,110 >> ПУБЛИКАТА: List. 640 00:32:22,110 --> 00:32:22,900 >> JASON Hirschhorn: List. 641 00:32:22,900 --> 00:32:24,090 Това е точно така. 642 00:32:24,090 --> 00:32:26,290 Сега има адрес на началото на нашия списък. 643 00:32:26,290 --> 00:32:28,450 А какво да кажем за предишния? 644 00:32:28,450 --> 00:32:31,920 >> ПУБЛИКАТА: Списък минус едно? 645 00:32:31,920 --> 00:32:32,690 >> JASON Hirschhorn: Има нищо преди него. 646 00:32:32,690 --> 00:32:34,580 И така, какво можем да направим, за да означава нищо? 647 00:32:34,580 --> 00:32:35,050 >> ПУБЛИКАТА: Null. 648 00:32:35,050 --> 00:32:35,450 >> JASON Hirschhorn: Да. 649 00:32:35,450 --> 00:32:37,950 Това звучи като добра идея. 650 00:32:37,950 --> 00:32:38,360 Perfect. 651 00:32:38,360 --> 00:32:39,630 Благодаря. 652 00:32:39,630 --> 00:32:42,850 Преминете през списъка. 653 00:32:42,850 --> 00:32:45,490 Константин, колко време ще да мине през списъка? 654 00:32:45,490 --> 00:32:49,010 >> ПУБЛИКАТА: докато стигнем нищожна. 655 00:32:49,010 --> 00:32:49,390 >> JASON Hirschhorn: OK. 656 00:32:49,390 --> 00:32:50,430 Така че, ако, докато, за контур. 657 00:32:50,430 --> 00:32:52,200 Какво правим? 658 00:32:52,200 --> 00:32:53,320 >> ПУБЛИКАТА: Може би за цикъл? 659 00:32:53,320 --> 00:32:53,910 >> JASON Hirschhorn: Да го направим за линия. 660 00:32:53,910 --> 00:32:55,870 OK. 661 00:32:55,870 --> 00:33:02,465 >> ПУБЛИКАТА: И ние кажем - 662 00:33:02,465 --> 00:33:09,764 663 00:33:09,764 --> 00:33:13,390 до текущата показалеца не е равно на нула. 664 00:33:13,390 --> 00:33:19,160 >> JASON Hirschhorn: Така че, ако ние знаем състояние, как да пишем една линия 665 00:33:19,160 --> 00:33:21,740 на базата на разстояние това условие. 666 00:33:21,740 --> 00:33:24,380 Какъв вид на една линия трябва да използвам? 667 00:33:24,380 --> 00:33:25,260 >> ПУБЛИКАТА: Докато. 668 00:33:25,260 --> 00:33:25,590 >> JASON Hirschhorn: Да. 669 00:33:25,590 --> 00:33:27,130 Това прави повече смисъл, базирани на разстояние от това, което каза. 670 00:33:27,130 --> 00:33:29,430 Ако просто искате да отидете в него ние ще Просто знам, че нещо, то ще направи 671 00:33:29,430 --> 00:33:31,680 смисъл да се направи, докато контур. 672 00:33:31,680 --> 00:33:39,880 Докато сегашната не е равно на нула, , ако стойността е по-малко от този възел. 673 00:33:39,880 --> 00:33:41,650 Akshar, дай ми тази линия. 674 00:33:41,650 --> 00:33:48,810 675 00:33:48,810 --> 00:33:56,955 >> ПУБЛИКАТА: Ако текущата-> н п по-малко от стойността. 676 00:33:56,955 --> 00:34:00,170 677 00:34:00,170 --> 00:34:03,260 Или обратно това. 678 00:34:03,260 --> 00:34:06,140 Превключете че скоба. 679 00:34:06,140 --> 00:34:06,620 >> JASON Hirschhorn: Съжалявам. 680 00:34:06,620 --> 00:34:08,760 >> ПУБЛИКАТА: Промяна на скобата. 681 00:34:08,760 --> 00:34:10,914 >> JASON Hirschhorn: Така че, ако това е по-голяма от стойността. 682 00:34:10,914 --> 00:34:18,719 683 00:34:18,719 --> 00:34:22,120 Защото това е объркващо с коментар по-горе, аз ще го направя. 684 00:34:22,120 --> 00:34:22,480 Но да. 685 00:34:22,480 --> 00:34:25,125 Ако нашата стойност е по-малка от тази възел, какво ще правим? 686 00:34:25,125 --> 00:34:25,540 Oh. 687 00:34:25,540 --> 00:34:26,710 Аз го имам точно тук. 688 00:34:26,710 --> 00:34:27,960 Поставете преди. 689 00:34:27,960 --> 00:34:32,080 690 00:34:32,080 --> 00:34:32,370 OK. 691 00:34:32,370 --> 00:34:33,933 Как правим това? 692 00:34:33,933 --> 00:34:34,900 >> ПУБЛИКАТА: Дали тя все още ме? 693 00:34:34,900 --> 00:34:36,150 >> JASON Hirschhorn: Да. 694 00:34:36,150 --> 00:34:38,520 695 00:34:38,520 --> 00:34:39,770 >> ПУБЛИКАТА: You - 696 00:34:39,770 --> 00:34:42,909 697 00:34:42,909 --> 00:34:44,159 new_node-> следващия. 698 00:34:44,159 --> 00:34:46,770 699 00:34:46,770 --> 00:34:50,163 >> JASON Hirschhorn: Така че това, което е че ще е равно? 700 00:34:50,163 --> 00:34:52,070 >> ПУБЛИКАТА: Ще равен ток. 701 00:34:52,070 --> 00:34:53,889 >> JASON Hirschhorn: Точно така. 702 00:34:53,889 --> 00:34:55,730 И така, от друга - 703 00:34:55,730 --> 00:34:56,730 какво друго имаме нужда да се актуализира? 704 00:34:56,730 --> 00:34:59,982 >> ПУБЛИКАТА: Проверете дали покрай равнява нула. 705 00:34:59,982 --> 00:35:01,870 >> JASON Hirschhorn: Ако Предишна - 706 00:35:01,870 --> 00:35:03,730 така че ако предишна равнява нула. 707 00:35:03,730 --> 00:35:05,990 >> ПУБЛИКАТА: Това означава, че ще да се превърне в главата. 708 00:35:05,990 --> 00:35:06,780 >> JASON Hirschhorn: Това означава тя се превърна в главата. 709 00:35:06,780 --> 00:35:07,620 Тогава какво ще правим? 710 00:35:07,620 --> 00:35:12,510 >> ПУБЛИКАТА: Правим главата равнява new_node. 711 00:35:12,510 --> 00:35:16,690 >> JASON Hirschhorn: Head равнява new_node. 712 00:35:16,690 --> 00:35:20,540 И защо се отправят тук, не се изброят? 713 00:35:20,540 --> 00:35:24,940 >> ПУБЛИКАТА: Защото главата е глобална променлива, която е изходен място. 714 00:35:24,940 --> 00:35:26,190 >> JASON Hirschhorn: Sweet. 715 00:35:26,190 --> 00:35:33,750 716 00:35:33,750 --> 00:35:34,170 OK. 717 00:35:34,170 --> 00:35:36,150 И - 718 00:35:36,150 --> 00:35:53,796 >> ПУБЛИКАТА: Тогава се друго предишна-> Следващата равнява new_node. 719 00:35:53,796 --> 00:35:55,080 И след това се върнете вярно. 720 00:35:55,080 --> 00:35:59,560 721 00:35:59,560 --> 00:36:02,700 >> JASON Hirschhorn: Къде тръгнахме край new_node? 722 00:36:02,700 --> 00:36:04,850 >> ПУБЛИКАТА: Бих - 723 00:36:04,850 --> 00:36:06,180 Задам, че в началото. 724 00:36:06,180 --> 00:36:07,430 >> JASON Hirschhorn: Така че това, което линия? 725 00:36:07,430 --> 00:36:10,000 726 00:36:10,000 --> 00:36:12,598 >> ПУБЛИКАТА: След ако изявление проверка, ако това е известно. 727 00:36:12,598 --> 00:36:13,057 >> JASON Hirschhorn: Точно тук? 728 00:36:13,057 --> 00:36:18,335 >> ПУБЛИКАТА: Бих направил new_node-> н се равнява на стойността. 729 00:36:18,335 --> 00:36:19,585 >> JASON Hirschhorn: Звучи добре. 730 00:36:19,585 --> 00:36:21,740 731 00:36:21,740 --> 00:36:25,090 Вероятно има смисъл - ние не правим Трябва да знам какво списък сме на 732 00:36:25,090 --> 00:36:26,280 защото ние сме само сделки с един списък. 733 00:36:26,280 --> 00:36:29,560 Така че по-добре функцията декларация за това е само за да се отърве от този 734 00:36:29,560 --> 00:36:34,360 изцяло и просто поставете стойност в главата. 735 00:36:34,360 --> 00:36:35,930 Ние дори не трябва да знаете какво списък сме вътре 736 00:36:35,930 --> 00:36:39,140 Но аз ще го запази за сега и след това го променя при актуализирането 737 00:36:39,140 --> 00:36:42,590 слайдовете и кода. 738 00:36:42,590 --> 00:36:44,980 Така че изглежда добре за сега. 739 00:36:44,980 --> 00:36:46,560 Ако стойност - който може да направи тази линия? 740 00:36:46,560 --> 00:36:47,810 Ако - 741 00:36:47,810 --> 00:36:52,240 742 00:36:52,240 --> 00:36:53,840 какво ще правим тук, Ноа. 743 00:36:53,840 --> 00:36:57,890 744 00:36:57,890 --> 00:37:07,100 >> ПУБЛИКАТА: Ако стойността е по-голяма от Curr-> N - 745 00:37:07,100 --> 00:37:16,830 746 00:37:16,830 --> 00:37:18,240 >> JASON Hirschhorn: Как да отиваме към следващия възел? 747 00:37:18,240 --> 00:37:27,760 748 00:37:27,760 --> 00:37:30,530 >> ПУБЛИКАТА: Curr-> н е равна на new_node. 749 00:37:30,530 --> 00:37:37,630 750 00:37:37,630 --> 00:37:39,195 >> JASON Hirschhorn: Значи п е каква част от структурата? 751 00:37:39,195 --> 00:37:43,065 752 00:37:43,065 --> 00:37:46,020 Цялото число. 753 00:37:46,020 --> 00:37:50,420 И new_node е указател към възел. 754 00:37:50,420 --> 00:37:51,880 Така че това, което част от Curr трябва да актуализираме? 755 00:37:51,880 --> 00:38:03,900 756 00:38:03,900 --> 00:38:05,400 Ако не п, тогава това, което е другата част? 757 00:38:05,400 --> 00:38:21,680 758 00:38:21,680 --> 00:38:22,810 Ной, което е другата част. 759 00:38:22,810 --> 00:38:23,570 >> ПУБЛИКАТА: О, следващия. 760 00:38:23,570 --> 00:38:25,645 >> JASON Hirschhorn: Next, точно така. 761 00:38:25,645 --> 00:38:26,410 Точно така. 762 00:38:26,410 --> 00:38:28,770 В непосредствена близост е най-подходящия. 763 00:38:28,770 --> 00:38:31,540 И какво друго ни е нужно да се актуализира, Ноа? 764 00:38:31,540 --> 00:38:32,840 >> ПУБЛИКАТА: Указателите. 765 00:38:32,840 --> 00:38:34,840 >> JASON Hirschhorn: So ние актуализира ток. 766 00:38:34,840 --> 00:38:36,090 >> ПУБЛИКАТА: Пред-> следващия. 767 00:38:36,090 --> 00:38:48,160 768 00:38:48,160 --> 00:38:49,410 >> JASON Hirschhorn: Да. 769 00:38:49,410 --> 00:38:57,465 770 00:38:57,465 --> 00:38:58,370 ОК, ние ще пауза. 771 00:38:58,370 --> 00:39:02,200 Кой може да ни помогне тук? 772 00:39:02,200 --> 00:39:03,385 Manu, какво да правим? 773 00:39:03,385 --> 00:39:05,615 >> Публика: Трябва да зададете то равно на Curr-> следващия. 774 00:39:05,615 --> 00:39:09,110 775 00:39:09,110 --> 00:39:11,630 Но направи това преди предишния ред. 776 00:39:11,630 --> 00:39:12,880 >> JASON Hirschhorn: OK. 777 00:39:12,880 --> 00:39:16,590 778 00:39:16,590 --> 00:39:18,260 Нещо друго? 779 00:39:18,260 --> 00:39:19,170 Akshar. 780 00:39:19,170 --> 00:39:22,680 >> ПУБЛИКАТА: Аз не мисля, че ти си означаваше да се промени Curr-> следващия. 781 00:39:22,680 --> 00:39:29,270 Мисля, че трябваше да направя Curr равни Curr-> следващия да отидете на следващия възел. 782 00:39:29,270 --> 00:39:30,500 >> JASON Hirschhorn: Толкова съжалявам, къде? 783 00:39:30,500 --> 00:39:32,680 На каква линия? 784 00:39:32,680 --> 00:39:33,420 Тази линия? 785 00:39:33,420 --> 00:39:33,750 >> Публика: Да. 786 00:39:33,750 --> 00:39:35,745 Уверете се равнява Curr Curr-> следващия. 787 00:39:35,745 --> 00:39:39,690 788 00:39:39,690 --> 00:39:43,360 >> JASON Hirschhorn: Така че това е правилното защото сегашната е 789 00:39:43,360 --> 00:39:45,220 указател към възел. 790 00:39:45,220 --> 00:39:48,550 И ние искаме тя да сочи към следващия възел на това, което в момента става все 791 00:39:48,550 --> 00:39:49,930 посочи. 792 00:39:49,930 --> 00:39:54,410 Самата Curr има следваща. 793 00:39:54,410 --> 00:39:58,620 Но ако трябва да се актуализира curr.next, ние ще се актуализира действителната бележката 794 00:39:58,620 --> 00:40:01,430 себе си не, когато този показалеца сочеше. 795 00:40:01,430 --> 00:40:02,680 Какво ще кажете за тази линия, все пак. 796 00:40:02,680 --> 00:40:05,160 797 00:40:05,160 --> 00:40:07,330 Ави? 798 00:40:07,330 --> 00:40:09,590 >> ПУБЛИКАТА: Пред-> следващия равнява Curr. 799 00:40:09,590 --> 00:40:12,500 800 00:40:12,500 --> 00:40:19,440 >> JASON Hirschhorn: Така че отново, ако предх е указател към възел, предишна ал-> След това е 801 00:40:19,440 --> 00:40:23,020 действителната указател в възел. 802 00:40:23,020 --> 00:40:27,190 Така че това ще се актуализира показалеца в възел Curr. 803 00:40:27,190 --> 00:40:28,570 Ние не искаме да се актуализира указател в възел. 804 00:40:28,570 --> 00:40:30,570 Искаме да актуализира предишна. 805 00:40:30,570 --> 00:40:31,850 Е, как да го направим? 806 00:40:31,850 --> 00:40:34,250 >> ПУБЛИКАТА: Той просто ще бъде предх. 807 00:40:34,250 --> 00:40:34,565 >> JASON Hirschhorn: Точно така. 808 00:40:34,565 --> 00:40:35,560 Предишна е указател към възел. 809 00:40:35,560 --> 00:40:38,750 Сега ние сме го сменят с по- нов показалец към възел. 810 00:40:38,750 --> 00:40:40,830 OK Нека се движи надолу. 811 00:40:40,830 --> 00:40:41,940 Накрая, последното условие. 812 00:40:41,940 --> 00:40:44,896 Джеф, какво правим тук? 813 00:40:44,896 --> 00:40:47,515 >> ПУБЛИКАТА: Ако стойността е равна Curr-> п. 814 00:40:47,515 --> 00:40:51,030 815 00:40:51,030 --> 00:40:51,300 >> JASON Hirschhorn: Съжалявам. 816 00:40:51,300 --> 00:40:52,372 О, Боже мой. 817 00:40:52,372 --> 00:40:54,330 Какво? 818 00:40:54,330 --> 00:40:55,580 Стойност == Curr-> п. 819 00:40:55,580 --> 00:41:01,050 820 00:41:01,050 --> 00:41:02,300 Какво ще правим? 821 00:41:02,300 --> 00:41:04,760 822 00:41:04,760 --> 00:41:10,950 >> ПУБЛИКАТА: Ще освободим нашата new_node, и тогава ще се върне фалшиви. 823 00:41:10,950 --> 00:41:21,410 824 00:41:21,410 --> 00:41:23,460 >> JASON Hirschhorn: Това е, което сме написали досега. 825 00:41:23,460 --> 00:41:25,710 Дали някой има нещо да добавите преди да направим? 826 00:41:25,710 --> 00:41:35,460 827 00:41:35,460 --> 00:41:35,710 OK. 828 00:41:35,710 --> 00:41:36,960 Нека да опитаме. 829 00:41:36,960 --> 00:41:44,180 830 00:41:44,180 --> 00:41:46,110 Контролът може да стигнат до края на не-нищожен функция. 831 00:41:46,110 --> 00:41:48,310 Ави, какво става? 832 00:41:48,310 --> 00:41:51,380 >> ПУБЛИКАТА: трябва ли да се сложи връщане Вярно извън примката, докато? 833 00:41:51,380 --> 00:41:53,900 834 00:41:53,900 --> 00:41:54,400 >> JASON Hirschhorn: Не знам. 835 00:41:54,400 --> 00:41:54,780 Искаш ли да се? 836 00:41:54,780 --> 00:41:55,520 >> ПУБЛИКАТА: Няма значение. 837 00:41:55,520 --> 00:41:56,350 Не. 838 00:41:56,350 --> 00:41:57,180 >> JASON Hirschhorn: Akshar? 839 00:41:57,180 --> 00:41:59,460 >> ПУБЛИКАТА: Мисля, че трябваше да сложи връщане фалшиви в края 840 00:41:59,460 --> 00:42:02,230 на линия време. 841 00:42:02,230 --> 00:42:03,270 >> JASON Hirschhorn: Е, къде искаш да отидеш? 842 00:42:03,270 --> 00:42:05,270 >> ПУБЛИКАТА: Подобно извън контура време. 843 00:42:05,270 --> 00:42:08,800 Така че, ако излезете от примката, докато това означава, че че сте достигнали до края и 844 00:42:08,800 --> 00:42:09,980 нищо не се е случило. 845 00:42:09,980 --> 00:42:10,410 >> JASON Hirschhorn: OK. 846 00:42:10,410 --> 00:42:12,340 И така, какво ще правим тук? 847 00:42:12,340 --> 00:42:13,702 >> АУДИТОРИЯ: Връщате фалшива там. 848 00:42:13,702 --> 00:42:15,040 >> JASON Hirschhorn: О, ние го направи и на двете места? 849 00:42:15,040 --> 00:42:15,650 >> Публика: Да. 850 00:42:15,650 --> 00:42:16,900 >> JASON Hirschhorn: OK. 851 00:42:16,900 --> 00:42:24,840 852 00:42:24,840 --> 00:42:26,160 Трябва ли да отида? 853 00:42:26,160 --> 00:42:26,980 О, Боже мой. 854 00:42:26,980 --> 00:42:27,290 Съжалявам. 855 00:42:27,290 --> 00:42:28,480 Извинявам се за екрана. 856 00:42:28,480 --> 00:42:30,530 Това е нещо откача върху нас. 857 00:42:30,530 --> 00:42:31,520 Така че изберете опция. 858 00:42:31,520 --> 00:42:35,260 Нула, на кода, се затваря програмата. 859 00:42:35,260 --> 00:42:36,700 Един вмъква нещо. 860 00:42:36,700 --> 00:42:37,990 Нека да вмъкнете три. 861 00:42:37,990 --> 00:42:42,900 862 00:42:42,900 --> 00:42:45,380 Вложката не е била успешна. 863 00:42:45,380 --> 00:42:46,500 Отивам да разпечатате. 864 00:42:46,500 --> 00:42:48,050 Аз нямам нищо. 865 00:42:48,050 --> 00:42:48,450 OK. 866 00:42:48,450 --> 00:42:50,250 Може би това е просто случайност. 867 00:42:50,250 --> 00:42:52,810 Поставете единия. 868 00:42:52,810 --> 00:42:55,770 Не е успешна. 869 00:42:55,770 --> 00:42:57,470 OK. 870 00:42:57,470 --> 00:43:02,400 Нека да тече през GDB наистина бързо да провери какво се случва. 871 00:43:02,400 --> 00:43:06,055 >> Запомни GDB. / Името на вашия програмата ни попадне в GDB. 872 00:43:06,055 --> 00:43:07,610 Това да не е много, за да се справят? 873 00:43:07,610 --> 00:43:08,560 В мига? 874 00:43:08,560 --> 00:43:10,400 Вероятно. 875 00:43:10,400 --> 00:43:12,760 Затворете очи и поемете някакъв дълбок диша, ако ви омръзне 876 00:43:12,760 --> 00:43:13,580 на проблемите в него. 877 00:43:13,580 --> 00:43:14,200 Аз съм в GDB. 878 00:43:14,200 --> 00:43:15,830 Кое е първото нещо, което правя в GDB? 879 00:43:15,830 --> 00:43:17,050 Трябва да разбера какво става тук. 880 00:43:17,050 --> 00:43:17,310 Нека да видим. 881 00:43:17,310 --> 00:43:21,650 Ние имаме шест минути до фигура какво става. 882 00:43:21,650 --> 00:43:22,900 Пробив главната. 883 00:43:22,900 --> 00:43:25,950 884 00:43:25,950 --> 00:43:28,130 И тогава какво да правя? 885 00:43:28,130 --> 00:43:29,180 Карлос? 886 00:43:29,180 --> 00:43:31,060 Изпълни. 887 00:43:31,060 --> 00:43:32,250 OK. 888 00:43:32,250 --> 00:43:34,160 Нека да изберете опция. 889 00:43:34,160 --> 00:43:36,330 И какво общо има N направя? 890 00:43:36,330 --> 00:43:38,480 Next. 891 00:43:38,480 --> 00:43:38,950 Да. 892 00:43:38,950 --> 00:43:39,740 >> ПУБЛИКАТА: Още не споменавате - 893 00:43:39,740 --> 00:43:45,230 не ми каза, че главата, че е инициализира с нула в началото. 894 00:43:45,230 --> 00:43:47,140 Но аз мислех, че каза, че е ОК. 895 00:43:47,140 --> 00:43:50,040 896 00:43:50,040 --> 00:43:52,640 >> JASON Hirschhorn: Да вървим - нека да разгледаме в GDB, а след това ще се върнем. 897 00:43:52,640 --> 00:43:54,910 Но това звучи като вече имате някои идеи за това какво се случва. 898 00:43:54,910 --> 00:43:58,340 Така че ние искаме да вмъкнете нещо. 899 00:43:58,340 --> 00:43:59,390 OK. 900 00:43:59,390 --> 00:44:00,150 Ние сме вмъкнете. 901 00:44:00,150 --> 00:44:00,770 Моля въведете вътр. 902 00:44:00,770 --> 00:44:01,990 Ние ще вмъкнете три. 903 00:44:01,990 --> 00:44:03,000 И тогава аз съм по тази линия. 904 00:44:03,000 --> 00:44:07,030 Как мога да отида да започне отстраняване на грешки вложката известна функция? 905 00:44:07,030 --> 00:44:08,280 О, Боже мой. 906 00:44:08,280 --> 00:44:10,990 907 00:44:10,990 --> 00:44:12,240 Това е много. 908 00:44:12,240 --> 00:44:14,372 909 00:44:14,372 --> 00:44:16,445 Е, че откачам много? 910 00:44:16,445 --> 00:44:19,696 911 00:44:19,696 --> 00:44:21,680 >> ПУБЛИКАТА: О, тя почина. 912 00:44:21,680 --> 00:44:22,930 >> JASON Hirschhorn: Току-що го извади. 913 00:44:22,930 --> 00:44:27,364 914 00:44:27,364 --> 00:44:28,310 OK. 915 00:44:28,310 --> 00:44:29,560 >> ПУБЛИКАТА: Може би това е другия край на жицата. 916 00:44:29,560 --> 00:44:37,000 917 00:44:37,000 --> 00:44:39,470 >> JASON Hirschhorn: Уау. 918 00:44:39,470 --> 00:44:42,330 Така че най-долния ред - 919 00:44:42,330 --> 00:44:43,470 това, което казахте? 920 00:44:43,470 --> 00:44:46,040 >> ПУБЛИКАТА: Казах иронията на техническата трудности в този клас. 921 00:44:46,040 --> 00:44:46,410 >> JASON Hirschhorn: Знам. 922 00:44:46,410 --> 00:44:48,660 Ако само имах контрол върху тази част. 923 00:44:48,660 --> 00:44:49,910 [Недоловим] 924 00:44:49,910 --> 00:44:54,430 925 00:44:54,430 --> 00:44:55,400 Това звучи страхотно. 926 00:44:55,400 --> 00:44:58,680 Защо не започнеш да мислиш за момчета това, което би могъл да направи грешен, 927 00:44:58,680 --> 00:45:01,140 и ние ще се върнем в 90 секунди. 928 00:45:01,140 --> 00:46:18,160 929 00:46:18,160 --> 00:46:23,010 >> Avica, аз отивам да ви попитам как да отида вътре insert_node да го развенчава. 930 00:46:23,010 --> 00:46:28,940 931 00:46:28,940 --> 00:46:31,460 Така че това е мястото, където последно бяхме стигнали. 932 00:46:31,460 --> 00:46:35,110 Как мога да вляза вътре insert_node, Avica, да се проучи какво се случва? 933 00:46:35,110 --> 00:46:36,360 Какво GDB команда? 934 00:46:36,360 --> 00:46:41,050 935 00:46:41,050 --> 00:46:42,390 Break не ще ме отведе вътре. 936 00:46:42,390 --> 00:46:46,200 937 00:46:46,200 --> 00:46:47,130 Знае ли Marquise? 938 00:46:47,130 --> 00:46:48,240 >> ПУБЛИКАТА: Какво? 939 00:46:48,240 --> 00:46:51,780 >> JASON Hirschhorn: Какво команда GDB Да използвам за да влезем вътре тази функция? 940 00:46:51,780 --> 00:46:52,070 >> ПУБЛИКАТА: Стъпка? 941 00:46:52,070 --> 00:46:55,140 >> JASON Hirschhorn: Стъпка чрез S. Това ме отвежда вътре. 942 00:46:55,140 --> 00:46:55,476 OK. 943 00:46:55,476 --> 00:46:58,040 New_node mallocing малко пространство. 944 00:46:58,040 --> 00:46:59,120 Всичко това изглежда като това продължава. 945 00:46:59,120 --> 00:47:00,370 Нека да разгледаме new_node. 946 00:47:00,370 --> 00:47:03,270 947 00:47:03,270 --> 00:47:05,410 Тя има някакъв адрес от паметта. 948 00:47:05,410 --> 00:47:07,440 Да проверим - 949 00:47:07,440 --> 00:47:08,500 това е всичко правилно. 950 00:47:08,500 --> 00:47:12,220 Така че тук всичко изглежда да се работи правилно. 951 00:47:12,220 --> 00:47:14,530 >> ПУБЛИКАТА: Каква е разликата между P и дисплей? 952 00:47:14,530 --> 00:47:16,160 >> JASON Hirschhorn: P щандове за печат. 953 00:47:16,160 --> 00:47:19,310 И така, вие ме питате какъв е разлика между това и това? 954 00:47:19,310 --> 00:47:22,330 В този случай, нищо. 955 00:47:22,330 --> 00:47:26,960 Но като цяло има някои различия. 956 00:47:26,960 --> 00:47:28,220 И вие трябва да погледнете в ръководството GDB. 957 00:47:28,220 --> 00:47:29,560 Но в този случай, нищо. 958 00:47:29,560 --> 00:47:31,460 Склонни сме да се използва за печат, все пак, защото ние не трябва да се направи много повече, отколкото 959 00:47:31,460 --> 00:47:33,960 отпечатате само една стойност. 960 00:47:33,960 --> 00:47:34,640 >> OK. 961 00:47:34,640 --> 00:47:40,300 Така че ние сме на линия 80 от нашия код, създаване възел * Curr равна на списък. 962 00:47:40,300 --> 00:47:42,500 Нека да разпечатате Curr. 963 00:47:42,500 --> 00:47:45,260 964 00:47:45,260 --> 00:47:46,840 Това се равнява на списък. 965 00:47:46,840 --> 00:47:48,850 Sweet. 966 00:47:48,850 --> 00:47:49,340 Изчакайте. 967 00:47:49,340 --> 00:47:50,590 Това се равнява на нещо. 968 00:47:50,590 --> 00:47:53,680 969 00:47:53,680 --> 00:47:56,190 Това не изглежда правилно. 970 00:47:56,190 --> 00:47:56,840 Ето. 971 00:47:56,840 --> 00:47:59,470 Това е така, защото в GDB, нали, ако това е линията, която си върху него 972 00:47:59,470 --> 00:48:00,330 все още не се изпълнява. 973 00:48:00,330 --> 00:48:03,100 Така че ще трябва наистина да въведете до изпълнение на линия 974 00:48:03,100 --> 00:48:05,230 преди да види резултатите от нея. 975 00:48:05,230 --> 00:48:06,680 Така че ние сме тук. 976 00:48:06,680 --> 00:48:09,490 Ние просто изпълнява този ред, предишния равнява на нула. 977 00:48:09,490 --> 00:48:13,590 Така че отново, ако ние отпечатате предишния няма да видим нищо странно. 978 00:48:13,590 --> 00:48:18,680 Но ако ние действително изпълнява тази линия, след това ще видим 979 00:48:18,680 --> 00:48:20,380 че тази линия е работил. 980 00:48:20,380 --> 00:48:21,060 >> Така че ние имаме Curr. 981 00:48:21,060 --> 00:48:23,180 Това са както добре. 982 00:48:23,180 --> 00:48:24,010 Нали така? 983 00:48:24,010 --> 00:48:28,130 Сега сме по тази линия тук. 984 00:48:28,130 --> 00:48:29,310 Докато Curr не прави равен нула. 985 00:48:29,310 --> 00:48:31,110 Е, какво прави Curr равен? 986 00:48:31,110 --> 00:48:32,450 Ние току-що видях, че се равнява на нула. 987 00:48:32,450 --> 00:48:33,210 Ние го отпечатва. 988 00:48:33,210 --> 00:48:35,110 Ще го разпечатате отново. 989 00:48:35,110 --> 00:48:36,720 Така е, че докато линия ще се изпълни? 990 00:48:36,720 --> 00:48:37,270 >> Публиката: Не. 991 00:48:37,270 --> 00:48:39,790 >> JASON Hirschhorn: Така че, когато написах, че линия, вие виждате, ние скочи целия път 992 00:48:39,790 --> 00:48:41,390 надолу към дъното, връщане фалшиви. 993 00:48:41,390 --> 00:48:44,520 И тогава ние ще се върне фалшиви и се върнете към програмата ни и 994 00:48:44,520 --> 00:48:48,020 в крайна сметка разпечатате, като видяхме, вложката не е била успешна. 995 00:48:48,020 --> 00:48:51,010 Така че, някой има някакви идеи за това какво ние трябва да направя, за да поправя това? 996 00:48:51,010 --> 00:48:54,200 997 00:48:54,200 --> 00:48:57,570 Отивам да се изчака, докато не видя Няколко ръце нагоре. 998 00:48:57,570 --> 00:48:58,830 Ние не изпълни това. 999 00:48:58,830 --> 00:49:01,660 Имайте предвид, че това е първият нещо, което правехме. 1000 00:49:01,660 --> 00:49:02,430 Аз няма да направя една двойка. 1001 00:49:02,430 --> 00:49:03,670 Отивам да направя няколко. 1002 00:49:03,670 --> 00:49:04,830 Защото няколко означава две. 1003 00:49:04,830 --> 00:49:07,620 Аз ще чакам за повече от две. 1004 00:49:07,620 --> 00:49:10,690 >> Първият включва, Curr, по подразбиране е равно на нула. 1005 00:49:10,690 --> 00:49:14,050 И този цикъл тя изпълнява само ако Curr не е нищожна. 1006 00:49:14,050 --> 00:49:18,740 И така, как мога да получа около това? 1007 00:49:18,740 --> 00:49:19,990 Виждам три ръце. 1008 00:49:19,990 --> 00:49:28,490 1009 00:49:28,490 --> 00:49:29,780 Аз ще чакам за повече от три. 1010 00:49:29,780 --> 00:49:33,460 1011 00:49:33,460 --> 00:49:35,940 Маркъс, какво мислиш? 1012 00:49:35,940 --> 00:49:37,730 >> ПУБЛИКАТА: Е, ако имате нужда от него, за да изпълнява повече от веднъж, просто 1013 00:49:37,730 --> 00:49:39,948 го смените с по-Do-а линия. 1014 00:49:39,948 --> 00:49:41,250 >> JASON Hirschhorn: OK. 1015 00:49:41,250 --> 00:49:44,240 Това ще реши нашия проблем, все пак? 1016 00:49:44,240 --> 00:49:47,750 >> ПУБЛИКАТА: В този случай не поради факта, че списъкът е празен. 1017 00:49:47,750 --> 00:49:52,150 Така че, най-вероятно просто трябва да добавите изявление, че ако контур изходи 1018 00:49:52,150 --> 00:49:55,312 тогава ще трябва да бъде в края на списъка, в който да ви насочи 1019 00:49:55,312 --> 00:49:56,562 може просто да го вмъкнете. 1020 00:49:56,562 --> 00:49:58,920 1021 00:49:58,920 --> 00:49:59,680 >> JASON Hirschhorn: Това ми харесва. 1022 00:49:59,680 --> 00:50:00,500 Това има смисъл. 1023 00:50:00,500 --> 00:50:03,390 Ако веригата излиза - 1024 00:50:03,390 --> 00:50:04,800 защото тя ще се върне фалшиви тук. 1025 00:50:04,800 --> 00:50:08,220 Така че, ако контур изходи, тогава ние сме в В края на списъка, или може би най- 1026 00:50:08,220 --> 00:50:10,690 начало на списък, ако няма нищо в това, което е същото като на края. 1027 00:50:10,690 --> 00:50:12,770 Така че сега ние искаме да вмъкнете нещо тук. 1028 00:50:12,770 --> 00:50:17,380 И така, как този код изглежда, Маркъс? 1029 00:50:17,380 --> 00:50:21,600 >> ПУБЛИКАТА: Ако вече имам възел malloced, бихте могли просто да се каже, 1030 00:50:21,600 --> 00:50:25,400 new_node-> следващия равнява на нула, защото тя трябва да бъде в края. 1031 00:50:25,400 --> 00:50:27,510 Или new_node-> следващия равнява на нула. 1032 00:50:27,510 --> 00:50:27,765 >> JASON Hirschhorn: OK. 1033 00:50:27,765 --> 00:50:28,190 Извинете. 1034 00:50:28,190 --> 00:50:35,760 New_node-> следващия равнява на нула защото сме в края. 1035 00:50:35,760 --> 00:50:36,460 Това не го инча 1036 00:50:36,460 --> 00:50:37,710 Как да го сложи в списъка? 1037 00:50:37,710 --> 00:50:46,130 1038 00:50:46,130 --> 00:50:46,460 Точно така. 1039 00:50:46,460 --> 00:50:47,750 Това е просто да я оставяте равно на. 1040 00:50:47,750 --> 00:50:50,940 Не как правим всъщност го постави в списъка? 1041 00:50:50,940 --> 00:50:54,170 Какво сочи към край на списъка? 1042 00:50:54,170 --> 00:50:56,090 >> ПУБЛИКАТА: Head. 1043 00:50:56,090 --> 00:50:57,566 >> JASON Hirschhorn: Моля? 1044 00:50:57,566 --> 00:50:59,440 >> ПУБЛИКАТА: Head сочи на края на списъка. 1045 00:50:59,440 --> 00:51:01,480 >> JASON Hirschhorn: Ако няма нищо в списъка, главата е насочена към 1046 00:51:01,480 --> 00:51:04,170 край на списъка. 1047 00:51:04,170 --> 00:51:06,920 Така, че ще работи за първо вмъкване. 1048 00:51:06,920 --> 00:51:09,810 Какво ще кажете, ако има няколко неща в списъка? 1049 00:51:09,810 --> 00:51:12,470 Than ние не искаме да се създаде оглави равна на new_node. 1050 00:51:12,470 --> 00:51:13,790 Какво искаме да правим там? 1051 00:51:13,790 --> 00:51:15,610 Да? 1052 00:51:15,610 --> 00:51:16,860 Вероятно предишния. 1053 00:51:16,860 --> 00:51:23,560 1054 00:51:23,560 --> 00:51:24,810 Ще стане ли? 1055 00:51:24,810 --> 00:51:28,950 1056 00:51:28,950 --> 00:51:33,050 Спомнете си, че предишната е просто указател към възел. 1057 00:51:33,050 --> 00:51:34,770 И предишния е локална променлива. 1058 00:51:34,770 --> 00:51:38,080 Така че тази линия ще създаде локална променлива, предишния, равна на или 1059 00:51:38,080 --> 00:51:39,380 сочещи към този нов възел. 1060 00:51:39,380 --> 00:51:41,500 Това всъщност няма да го сложи в нашия списък, все пак. 1061 00:51:41,500 --> 00:51:44,330 Как да го сложи в нашия списък? 1062 00:51:44,330 --> 00:51:45,620 Akchar? 1063 00:51:45,620 --> 00:51:46,870 >> ПУБЛИКАТА: Мисля, че ти направи ток-> следващия. 1064 00:51:46,870 --> 00:51:50,186 1065 00:51:50,186 --> 00:51:52,550 >> JASON Hirschhorn: OK. 1066 00:51:52,550 --> 00:51:54,010 Curr-> следващия. 1067 00:51:54,010 --> 00:51:58,768 Така че отново, че единствената причина, че сме надолу тук е, какво прави ток, равен? 1068 00:51:58,768 --> 00:51:59,760 >> ПУБЛИКАТА: равно нула. 1069 00:51:59,760 --> 00:52:01,790 >> JASON Hirschhorn: И какво от това ще стане, ако ние направим нула-> следващия? 1070 00:52:01,790 --> 00:52:02,810 Какво ще получите? 1071 00:52:02,810 --> 00:52:04,060 Ще получите грешка сегментация. 1072 00:52:04,060 --> 00:52:06,600 1073 00:52:06,600 --> 00:52:08,880 >> ПУБЛИКАТА: Do Curr равнява нула. 1074 00:52:08,880 --> 00:52:10,760 >> JASON Hirschhorn: Това е едно и също нещо както пред, все пак, защото има 1075 00:52:10,760 --> 00:52:12,820 локална променлива сме настройка равен на този нов възел. 1076 00:52:12,820 --> 00:52:16,680 1077 00:52:16,680 --> 00:52:20,920 Нека да се върнем към нашата картина поставяне на нещо. 1078 00:52:20,920 --> 00:52:25,500 Да кажем, че си поставяте в края на списъка, така че точно тук. 1079 00:52:25,500 --> 00:52:30,010 Имаме ток указател, който е сочещи към нула и предишна точка 1080 00:52:30,010 --> 00:52:32,800 че да сочи на 8. 1081 00:52:32,800 --> 00:52:35,330 Така че това, което ни е нужно, за да се актуализира, Ави? 1082 00:52:35,330 --> 00:52:36,680 >> ПУБЛИКАТА: Previous-> следващия? 1083 00:52:36,680 --> 00:52:41,980 >> JASON Hirschhorn: Previous-> следващия е това, което ние искаме да се актуализира, защото това 1084 00:52:41,980 --> 00:52:44,960 действително ще го вмъкнете в на края на списъка. 1085 00:52:44,960 --> 00:52:47,220 Имаме още един бъг, все пак, че ние ще тичам в. 1086 00:52:47,220 --> 00:52:50,090 Какъв е този бъг? 1087 00:52:50,090 --> 00:52:50,790 Да? 1088 00:52:50,790 --> 00:52:53,860 >> ПУБЛИКАТА: Ще се върнете невярно в този случай? 1089 00:52:53,860 --> 00:52:56,380 >> JASON Hirschhorn: О, се ще се върне фалшиви. 1090 00:52:56,380 --> 00:52:57,430 Но има и друг бъг. 1091 00:52:57,430 --> 00:52:58,930 Така че ние ще трябва да се сложи в замяна вярно. 1092 00:52:58,930 --> 00:53:01,370 >> ПУБЛИКАТА: Има ли още предишния равен нищожна в горната част на списъка? 1093 00:53:01,370 --> 00:53:03,645 >> JASON Hirschhorn: Значи предишния още е равно на нула в самото начало. 1094 00:53:03,645 --> 00:53:07,480 1095 00:53:07,480 --> 00:53:10,440 Така че как можем да получим над това? 1096 00:53:10,440 --> 00:53:10,950 Да? 1097 00:53:10,950 --> 00:53:15,280 >> ПУБЛИКАТА: Мисля, че можете да направите проверка преди цикъла време, за да видим дали това е 1098 00:53:15,280 --> 00:53:16,610 празен списък. 1099 00:53:16,610 --> 00:53:17,000 >> JASON Hirschhorn: OK. 1100 00:53:17,000 --> 00:53:17,710 Така че нека да отидете тук. 1101 00:53:17,710 --> 00:53:18,530 Направете проверка. 1102 00:53:18,530 --> 00:53:19,380 Ако - 1103 00:53:19,380 --> 00:53:20,770 >> ПУБЛИКАТА: Така че, ако главата равнява се равнява на нула. 1104 00:53:20,770 --> 00:53:24,300 1105 00:53:24,300 --> 00:53:26,320 >> JASON Hirschhorn: Ако главата равнява се равнява на нула - 1106 00:53:26,320 --> 00:53:27,790 че ще ни каже дали е празен списък. 1107 00:53:27,790 --> 00:53:31,090 >> ПУБЛИКАТА: И тогава вие направи главата равнява ново. 1108 00:53:31,090 --> 00:53:34,740 >> JASON Hirschhorn: Head равнява new_node? 1109 00:53:34,740 --> 00:53:35,730 И какво друго трябва да направим? 1110 00:53:35,730 --> 00:53:37,020 >> ПУБЛИКАТА: И след това се върнете вярно. 1111 00:53:37,020 --> 00:53:37,535 >> JASON Hirschhorn: Не съвсем. 1112 00:53:37,535 --> 00:53:38,785 Ние пропускаме една стъпка. 1113 00:53:38,785 --> 00:53:41,590 1114 00:53:41,590 --> 00:53:43,710 >> ПУБЛИКАТА: New_node следващия трябва да сочи към нула. 1115 00:53:43,710 --> 00:53:44,570 >> JASON Hirschhorn: Точно така, Алдън. 1116 00:53:44,570 --> 00:53:46,600 И тогава можем да се върнем вярно. 1117 00:53:46,600 --> 00:53:47,560 OK. 1118 00:53:47,560 --> 00:53:51,630 Но тя все още е добра идея да се правят неща, в края на списъка, нали? 1119 00:53:51,630 --> 00:53:51,950 Добре. 1120 00:53:51,950 --> 00:53:54,450 Ние все още може да се получи в действителност на края на списъка. 1121 00:53:54,450 --> 00:53:57,870 Така е този код глоба, ако ние сме в края на списъка и там са някои 1122 00:53:57,870 --> 00:53:59,120 неща в списъка? 1123 00:53:59,120 --> 00:54:01,830 1124 00:54:01,830 --> 00:54:02,040 Нали така? 1125 00:54:02,040 --> 00:54:03,540 Защото ние все още имаме идея Маркъс. 1126 00:54:03,540 --> 00:54:06,870 Бихме могли да излезете от този цикъл, защото ние сме в края на списъка. 1127 00:54:06,870 --> 00:54:09,308 Така че ние все още искаме това кодира тук? 1128 00:54:09,308 --> 00:54:10,520 >> Публика: Да. 1129 00:54:10,520 --> 00:54:11,000 >> JASON Hirschhorn: Да. 1130 00:54:11,000 --> 00:54:14,190 И това, което ни е нужно, за да се промени това, за да? 1131 00:54:14,190 --> 00:54:15,440 True. 1132 00:54:15,440 --> 00:54:19,580 1133 00:54:19,580 --> 00:54:21,640 Това звучи добре за всички досега? 1134 00:54:21,640 --> 00:54:22,420 Някой да има такива - 1135 00:54:22,420 --> 00:54:23,480 Ави, имате ли нещо да добавите? 1136 00:54:23,480 --> 00:54:23,920 >> Публиката: Не. 1137 00:54:23,920 --> 00:54:25,276 >> JASON Hirschhorn: OK. 1138 00:54:25,276 --> 00:54:27,010 Така че ние сме направили няколко промени. 1139 00:54:27,010 --> 00:54:29,540 Ние сме направили тази проверка, преди да отиде в за празен списък. 1140 00:54:29,540 --> 00:54:31,790 Така че ние сме се погрижили празен списък. 1141 00:54:31,790 --> 00:54:35,500 И тук ние се грижи за вмъкване нещо в края на списъка. 1142 00:54:35,500 --> 00:54:38,930 Така изглежда, че тази линия, докато поемането грижат за нещата между тях, 1143 00:54:38,930 --> 00:54:41,920 някъде в списъка, ако има неща в списъка. 1144 00:54:41,920 --> 00:54:42,280 >> OK. 1145 00:54:42,280 --> 00:54:44,310 Нека да се кандидатира отново тази програма. 1146 00:54:44,310 --> 00:54:50,170 1147 00:54:50,170 --> 00:54:50,755 Не е успешна. 1148 00:54:50,755 --> 00:54:52,190 >> Публика: Ти не го направи. 1149 00:54:52,190 --> 00:54:53,940 >> JASON Hirschhorn: О, Аз не го направи. 1150 00:54:53,940 --> 00:54:56,250 Добър въпрос, Майкъл. 1151 00:54:56,250 --> 00:54:57,500 Да добавим марка свързани. 1152 00:54:57,500 --> 00:55:01,590 1153 00:55:01,590 --> 00:55:04,830 Line 87 има грешка. 1154 00:55:04,830 --> 00:55:05,420 Линия 87. 1155 00:55:05,420 --> 00:55:06,600 Алдън, това е линията, която ми даде. 1156 00:55:06,600 --> 00:55:08,962 Какво не е наред? 1157 00:55:08,962 --> 00:55:10,710 >> ПУБЛИКАТА: Тя трябва да бъде да се присвоява. 1158 00:55:10,710 --> 00:55:11,000 >> JASON Hirschhorn: Отлично. 1159 00:55:11,000 --> 00:55:11,630 Точно така. 1160 00:55:11,630 --> 00:55:13,290 Тя трябва да бъде нула. 1161 00:55:13,290 --> 00:55:15,210 Да направим отново. 1162 00:55:15,210 --> 00:55:17,220 Compile. 1163 00:55:17,220 --> 00:55:17,890 OK. 1164 00:55:17,890 --> 00:55:19,400 Нека да вмъкнете три. 1165 00:55:19,400 --> 00:55:20,570 Вложката е била успешна. 1166 00:55:20,570 --> 00:55:21,660 Нека да го разпечатате. 1167 00:55:21,660 --> 00:55:23,590 О, ако само можехме да се провери. 1168 00:55:23,590 --> 00:55:25,500 Но ние не сме направили отпечатате функция все още. 1169 00:55:25,500 --> 00:55:27,840 Нека да въведете нещо друго. 1170 00:55:27,840 --> 00:55:29,090 Какво трябва да въведа? 1171 00:55:29,090 --> 00:55:31,120 1172 00:55:31,120 --> 00:55:31,940 >> ПУБЛИКАТА: Seven. 1173 00:55:31,940 --> 00:55:33,340 >> JASON Hirschhorn: Седем? 1174 00:55:33,340 --> 00:55:34,590 >> Публика: Да. 1175 00:55:34,590 --> 00:55:38,680 1176 00:55:38,680 --> 00:55:39,780 >> JASON Hirschhorn: Нямаме вина за сегмента. 1177 00:55:39,780 --> 00:55:43,760 Така че ние имаме един, но ние ясно не могат да получат два. 1178 00:55:43,760 --> 00:55:45,690 Това е 05:07. 1179 00:55:45,690 --> 00:55:48,370 Така че бихме могли да развенчава тази в продължение на три минути. 1180 00:55:48,370 --> 00:55:51,240 Но аз отивам да ни остави тук и преминете към хеш таблици. 1181 00:55:51,240 --> 00:55:54,290 Но отново, отговорите за този код Аз ще го имейл до вас след малко. 1182 00:55:54,290 --> 00:55:55,440 Ние сме много близо до него. 1183 00:55:55,440 --> 00:55:58,300 Аз силно ви препоръчваме да разбера какво става тук и да я поправи. 1184 00:55:58,300 --> 00:56:02,400 Така че аз ще ви изпратим имейл, този код като добре плюс решение - 1185 00:56:02,400 --> 00:56:03,670 вероятно разтвора по-късно. 1186 00:56:03,670 --> 00:56:05,110 Първо този код. 1187 00:56:05,110 --> 00:56:08,290 >> Другото нещо, което искам да направя, преди да сме Финалът е, че не сме освободени нищо. 1188 00:56:08,290 --> 00:56:10,370 Така че аз искам да ви покажа това, което valgrind изглежда. 1189 00:56:10,370 --> 00:56:14,310 Ако бягаме valgrind граници на нашата програма,. / свързани. 1190 00:56:14,310 --> 00:56:22,540 Пак според този слайд, ние би трябвало да работи valgrind с някакъв вид 1191 00:56:22,540 --> 00:56:26,410 вариант, в този случай - Теч-проверка = пълна. 1192 00:56:26,410 --> 00:56:27,660 Така че нека да напише valgrind - Теч-проверка = пълна. 1193 00:56:27,660 --> 00:56:31,910 1194 00:56:31,910 --> 00:56:35,080 Така че това ще продължи valgrind на нашата програма. 1195 00:56:35,080 --> 00:56:37,000 И сега програмата действително работи. 1196 00:56:37,000 --> 00:56:40,190 Така че ние ще го изпълним точно като преди, сложи нещо инча 1197 00:56:40,190 --> 00:56:40,830 Отивам да се постави в три. 1198 00:56:40,830 --> 00:56:41,790 Това работи. 1199 00:56:41,790 --> 00:56:43,202 Аз няма да се опита да сложи в нещо друг, защото ние ще 1200 00:56:43,202 --> 00:56:44,710 получите SEG невярно в този случай. 1201 00:56:44,710 --> 00:56:46,700 Така че аз съм просто ще се откажат. 1202 00:56:46,700 --> 00:56:50,160 >> А сега да те видя тук течове и обобщение купчина. 1203 00:56:50,160 --> 00:56:52,310 Това са най-добрите неща, които , който искате да проверите. 1204 00:56:52,310 --> 00:56:56,780 Така че обобщението купчина - тя казва, в употреба при излизане - осем байта в един блок. 1205 00:56:56,780 --> 00:56:58,370 Това един блок е възел ние malloced. 1206 00:56:58,370 --> 00:57:02,230 Майкъл, ти каза преди един възел е осем ухапвания, защото има число 1207 00:57:02,230 --> 00:57:02,680 и показалеца. 1208 00:57:02,680 --> 00:57:04,550 Така че това е нашата възел. 1209 00:57:04,550 --> 00:57:08,170 И тогава се казва, че ние използва изчистване седем пъти и сме освободени 1210 00:57:08,170 --> 00:57:08,940 нещо шест пъти. 1211 00:57:08,940 --> 00:57:13,680 Но ние никога не нарича свободен, така че аз нямам представа какво се говори. 1212 00:57:13,680 --> 00:57:18,490 >> Но достатъчно е да се каже, че когато вашият програмата работи, изчистване се нарича 1213 00:57:18,490 --> 00:57:20,330 в някои други места, които ние не е нужно да се притесняваш. 1214 00:57:20,330 --> 00:57:22,460 Така изчистване вероятно се нарича в някои места. 1215 00:57:22,460 --> 00:57:24,480 Ние не трябва да се притеснявате къде. 1216 00:57:24,480 --> 00:57:26,240 Но това е наистина ни. 1217 00:57:26,240 --> 00:57:27,380 Тази първа линия нас. 1218 00:57:27,380 --> 00:57:28,320 Оставихме този блок. 1219 00:57:28,320 --> 00:57:30,330 И вие можете да видите, че тук в резюмето на теч. 1220 00:57:30,330 --> 00:57:31,950 И все пак постижимо - 1221 00:57:31,950 --> 00:57:32,930 осем байта в един блок. 1222 00:57:32,930 --> 00:57:34,100 Това означава, че паметта - 1223 00:57:34,100 --> 00:57:35,730 ние са протекли, че паметта. 1224 00:57:35,730 --> 00:57:37,570 Определено загубил - 1225 00:57:37,570 --> 00:57:38,770 нещо се губи завинаги. 1226 00:57:38,770 --> 00:57:40,590 Като цяло, няма да го направиш виждам нищо там. 1227 00:57:40,590 --> 00:57:44,780 Все пак е достъпен обикновено когато ще видите неща, в които вие ще искате 1228 00:57:44,780 --> 00:57:48,900 да гледам да се види какво код трябва да ви са освободени, но сте забравили да се освободи. 1229 00:57:48,900 --> 00:57:53,170 >> И след това, ако това не е така, ако сме направили всичко безплатно, 1230 00:57:53,170 --> 00:57:54,360 ние може да се провери това. 1231 00:57:54,360 --> 00:57:57,330 Нека просто да стартирате програмата да не се поставят в нищо. 1232 00:57:57,330 --> 00:57:59,800 Ще видите тук в употреба на излизане - 1233 00:57:59,800 --> 00:58:01,310 нулеви байтове в нулеви блокове. 1234 00:58:01,310 --> 00:58:06,310 Това означава, че му е останало нищо кога тази програма излезе. 1235 00:58:06,310 --> 00:58:12,090 Така че, преди да се обърне в pset6, бягай valgrind и се уверете, че не е нужно 1236 00:58:12,090 --> 00:58:15,310 всяко изтичане на памет във вашата програма. 1237 00:58:15,310 --> 00:58:17,910 Ако имате някакви въпроси с valgrind, Чувствайте се свободни да се достигне. 1238 00:58:17,910 --> 00:58:18,700 Но това е как да го използвате. 1239 00:58:18,700 --> 00:58:20,890 Много просто - виж, ако има в употреба на изход - 1240 00:58:20,890 --> 00:58:22,270 всички байтове във всички блокове. 1241 00:58:22,270 --> 00:58:27,890 1242 00:58:27,890 --> 00:58:29,580 >> Така че ние се работи върху вложка възел. 1243 00:58:29,580 --> 00:58:33,840 Имах две други функции тук - отпечатате възли и безплатни възли. 1244 00:58:33,840 --> 00:58:37,780 Отново, това са функции, които са ще бъде добре за вас да практикуват 1245 00:58:37,780 --> 00:58:40,990 защото те ще ви помогне не само с тези примерни упражнения, но също 1246 00:58:40,990 --> 00:58:42,180 на проблема избран. 1247 00:58:42,180 --> 00:58:44,230 Те картата на доста тясно за неща ти започваш да се наложи да се направи в 1248 00:58:44,230 --> 00:58:45,010 проблем настроен. 1249 00:58:45,010 --> 00:58:47,640 Но аз искам да се уверете, че докосваме върху всичко. 1250 00:58:47,640 --> 00:58:50,400 И хеш таблици са също от решаващо значение за какво правим в този раздел 1251 00:58:50,400 --> 00:58:51,980 седмица - или в комплекта проблем. 1252 00:58:51,980 --> 00:58:55,200 >> Така че ние ще завърши частта Говорим за хеш таблици. 1253 00:58:55,200 --> 00:58:58,140 Ако забележите, че направих малко хеш таблица. 1254 00:58:58,140 --> 00:59:00,020 Това не е това, което ние говорим за, обаче. 1255 00:59:00,020 --> 00:59:03,540 Ние говорим за различен тип хеш таблици. 1256 00:59:03,540 --> 00:59:07,300 И в ядрото си, хеш таблица не е нищо повече от един 1257 00:59:07,300 --> 00:59:08,860 масив плюс хеш функция. 1258 00:59:08,860 --> 00:59:11,150 Ние ще говорим за малко, само за да се уверете, че всеки разбира това, което 1259 00:59:11,150 --> 00:59:12,110 хеш функция е. 1260 00:59:12,110 --> 00:59:15,420 И аз ви казвам сега, че това е нищо повече от две неща - 1261 00:59:15,420 --> 00:59:18,590 масив и хеш функция. 1262 00:59:18,590 --> 00:59:20,716 И тук са стъпките, през които това работи. 1263 00:59:20,716 --> 00:59:31,560 1264 00:59:31,560 --> 00:59:32,810 >> Ето го нашия масив. 1265 00:59:32,810 --> 00:59:38,460 1266 00:59:38,460 --> 00:59:39,460 Там е нашата функция. 1267 00:59:39,460 --> 00:59:43,180 По-специално, хеш функции трябва да направите няколко неща с това. 1268 00:59:43,180 --> 00:59:45,040 Отивам да говоря конкретно за този проблем настроен. 1269 00:59:45,040 --> 00:59:46,450 Това вероятно ще предприеме в низ. 1270 00:59:46,450 --> 00:59:50,570 1271 00:59:50,570 --> 00:59:51,770 И това, което е тя ще се върне? 1272 00:59:51,770 --> 00:59:52,640 Какъв тип данни? 1273 00:59:52,640 --> 00:59:54,260 Алдън? 1274 00:59:54,260 --> 00:59:55,760 Вашият хеш функция се върне? 1275 00:59:55,760 --> 00:59:58,760 Едно цяло число. 1276 00:59:58,760 --> 01:00:01,700 Така че това е, което хеша таблица се състои от - 1277 01:00:01,700 --> 01:00:05,430 маса под формата на масив и хеш функция. 1278 01:00:05,430 --> 01:00:06,010 Как става това? 1279 01:00:06,010 --> 01:00:07,300 Тя работи в три стъпки. 1280 01:00:07,300 --> 01:00:08,740 Ние го даде ключ. 1281 01:00:08,740 --> 01:00:11,470 В този случай, ние ще го дам низ. 1282 01:00:11,470 --> 01:00:18,140 Ние наричаме функцията за сегментиране на една стъпка на ключа и получаваме стойност. 1283 01:00:18,140 --> 01:00:20,310 >> По-специално, ние ще кажем, стигнем цяло число. 1284 01:00:20,310 --> 01:00:25,630 Това число, има много специфичен ограничения за това какво може да бъде, че число. 1285 01:00:25,630 --> 01:00:28,880 В този пример, нашата масив е с размер на три. 1286 01:00:28,880 --> 01:00:32,330 И какво от това, че номера може да бъде цяло число. 1287 01:00:32,330 --> 01:00:35,970 Какъв е обхватът на валидните стойности за това число, вида замяна на това 1288 01:00:35,970 --> 01:00:37,220 хеш функция? 1289 01:00:37,220 --> 01:00:40,440 1290 01:00:40,440 --> 01:00:42,110 Нула, едно и две. 1291 01:00:42,110 --> 01:00:46,060 Точката на хеш функция е да разбера място в масива 1292 01:00:46,060 --> 01:00:47,790 където нашият ключ се случва. 1293 01:00:47,790 --> 01:00:51,290 Има възможност са само три места тук - 1294 01:00:51,290 --> 01:00:52,130 нула, един, или два. 1295 01:00:52,130 --> 01:00:55,360 Така че тази функция по-добра възвръщаемост нула, един, или два. 1296 01:00:55,360 --> 01:00:58,740 Някои валиден indice в този масив. 1297 01:00:58,740 --> 01:01:02,770 >> И след това в зависимост от това къде се връща, можете да видите, че има редица отворени 1298 01:01:02,770 --> 01:01:03,730 попадне стойността на. 1299 01:01:03,730 --> 01:01:05,800 Това е мястото, където ще се постави ключа. 1300 01:01:05,800 --> 01:01:11,280 Така че ние се хвърлят в тиквата, ще излезем на нула. 1301 01:01:11,280 --> 01:01:15,540 В масив скоба 0, ние поставяме тиква. 1302 01:01:15,540 --> 01:01:21,070 Ние хвърлят в котки, ще се измъкнем един. 1303 01:01:21,070 --> 01:01:24,110 Ние събрахме на една котка. 1304 01:01:24,110 --> 01:01:25,480 Ние поставяме в паяк. 1305 01:01:25,480 --> 01:01:26,710 Ние се измъкнем две. 1306 01:01:26,710 --> 01:01:30,200 Ние поставяме паяк през масив скоба две. 1307 01:01:30,200 --> 01:01:32,300 Това би било толкова хубаво, ако тя работи по този начин. 1308 01:01:32,300 --> 01:01:35,570 Но за съжаление, както ще видим, това е малко по-сложно. 1309 01:01:35,570 --> 01:01:37,570 >> Преди да стигнем до там, някакви въпроси за основния 1310 01:01:37,570 --> 01:01:38,820 създаване на хеш таблица? 1311 01:01:38,820 --> 01:01:49,050 1312 01:01:49,050 --> 01:01:51,940 Това е образ на точно това, което привлече на дъската. 1313 01:01:51,940 --> 01:01:55,420 Но тъй като ние го привлече на дъската, аз аз няма да навлизам в детайли. 1314 01:01:55,420 --> 01:02:00,430 По същество, ключове, на магия черна кутия - или в този случай, Тийл кутия - на 1315 01:02:00,430 --> 01:02:02,410 хеш функция ги поставя в кофи. 1316 01:02:02,410 --> 01:02:04,690 И в този пример, че сме да не се поставят името. 1317 01:02:04,690 --> 01:02:07,880 Ние поставяме свързания телефон номер на името в кофата. 1318 01:02:07,880 --> 01:02:10,430 Но бихте могли много добре просто постави името в кофата. 1319 01:02:10,430 --> 01:02:12,950 >> Това е само една снимка на това, което начертахме на дъската. 1320 01:02:12,950 --> 01:02:14,460 Имаме потенциални клопки, все пак. 1321 01:02:14,460 --> 01:02:17,470 И там са две по-специално пързалки, че искам да отида. 1322 01:02:17,470 --> 01:02:20,230 Първият от тях е за хеш функция. 1323 01:02:20,230 --> 01:02:22,620 Така че аз зададох въпроса, какво прави добра хеш функция? 1324 01:02:22,620 --> 01:02:24,220 Дам два отговора. 1325 01:02:24,220 --> 01:02:26,630 Първата е, че това е детерминирана. 1326 01:02:26,630 --> 01:02:29,660 В контекста на хеш функции какво означава това? 1327 01:02:29,660 --> 01:02:37,840 1328 01:02:37,840 --> 01:02:39,282 Да? 1329 01:02:39,282 --> 01:02:42,850 >> ПУБЛИКАТА: Тя може да намерите най- индекс в константно време? 1330 01:02:42,850 --> 01:02:43,810 >> JASON Hirschhorn: Това Не е това, което означава. 1331 01:02:43,810 --> 01:02:44,725 Но това е едно добро предположение. 1332 01:02:44,725 --> 01:02:46,100 Някой друг да има предположение какво означава това? 1333 01:02:46,100 --> 01:02:47,780 Това е добра хеш функция е детерминирана? 1334 01:02:47,780 --> 01:02:48,280 Ани? 1335 01:02:48,280 --> 01:02:51,680 >> ПУБЛИКАТА: Това е ключ може да се картографира само за едно място в хеш таблицата. 1336 01:02:51,680 --> 01:02:53,070 >> JASON Hirschhorn: Това е точно така. 1337 01:02:53,070 --> 01:02:57,430 Всеки път, когато ви постави в тиква, тя винаги се връща нула. 1338 01:02:57,430 --> 01:03:01,660 Ако сложите в тиква и си хеш Функцията връща нула, но има 1339 01:03:01,660 --> 01:03:06,060 вероятност за връщане нещо още по-голяма от нула - 1340 01:03:06,060 --> 01:03:09,280 така че може би тя може да се върне един понякога или други два пъти - 1341 01:03:09,280 --> 01:03:11,100 че не е добра хеш функция. 1342 01:03:11,100 --> 01:03:11,800 Ти си точно така. 1343 01:03:11,800 --> 01:03:15,680 Вашият хеш функция трябва да върне същото точно число, в този случай, за 1344 01:03:15,680 --> 01:03:17,780 точно същата низ. 1345 01:03:17,780 --> 01:03:22,210 >> Може би тя се връща по същия точната число за точно същата низ 1346 01:03:22,210 --> 01:03:24,430 независимо от капитализация. 1347 01:03:24,430 --> 01:03:27,980 Но в този случай това е все още детерминирана, понеже повече неща 1348 01:03:27,980 --> 01:03:29,350 се нанася върху една и съща стойност. 1349 01:03:29,350 --> 01:03:30,170 Това е добре. 1350 01:03:30,170 --> 01:03:32,615 Докато има само един изход за дадена суровина. 1351 01:03:32,615 --> 01:03:35,630 1352 01:03:35,630 --> 01:03:36,350 >> OK. 1353 01:03:36,350 --> 01:03:38,340 Второто нещо е, че тя връща валидни индекси. 1354 01:03:38,340 --> 01:03:40,220 Ние възпитан, че по-рано. 1355 01:03:40,220 --> 01:03:41,860 Този хеш функция - 1356 01:03:41,860 --> 01:03:43,710 ох момче - 1357 01:03:43,710 --> 01:03:46,840 хеш функция трябва върнете валидни индекси. 1358 01:03:46,840 --> 01:03:47,740 Така казват - 1359 01:03:47,740 --> 01:03:48,990 нека се върнем на този пример. 1360 01:03:48,990 --> 01:03:52,580 1361 01:03:52,580 --> 01:03:57,540 My хеш функция брои буквите в думата. 1362 01:03:57,540 --> 01:03:58,380 Това е функцията за сегментиране. 1363 01:03:58,380 --> 01:03:59,740 И се връща, че число. 1364 01:03:59,740 --> 01:04:04,280 Така че, ако аз имам думата А, това е ще се върне един. 1365 01:04:04,280 --> 01:04:06,900 И това ще сложи точно тук. 1366 01:04:06,900 --> 01:04:09,430 Какво ако сложа в думата прилеп? 1367 01:04:09,430 --> 01:04:11,310 Той ще се върне три. 1368 01:04:11,310 --> 01:04:12,560 Откъде идва прилеп отидете? 1369 01:04:12,560 --> 01:04:18,730 1370 01:04:18,730 --> 01:04:19,750 >> Тя не се вписва. 1371 01:04:19,750 --> 01:04:21,000 Но той трябва да отида някъде. 1372 01:04:21,000 --> 01:04:23,340 Това е моят хеш таблица в края на краищата, и всичко трябва да отида някъде. 1373 01:04:23,340 --> 01:04:24,590 И така, къде трябва да отида прилеп? 1374 01:04:24,590 --> 01:04:28,020 1375 01:04:28,020 --> 01:04:28,710 Някакви идеи? 1376 01:04:28,710 --> 01:04:29,450 Предположения? 1377 01:04:29,450 --> 01:04:30,280 Добри предположения? 1378 01:04:30,280 --> 01:04:31,220 >> ПУБЛИКАТА: Нула. 1379 01:04:31,220 --> 01:04:32,120 >> JASON Hirschhorn: Защо нула? 1380 01:04:32,120 --> 01:04:35,990 >> ПУБЛИКАТА: Защото три по модул три е равно на нула? 1381 01:04:35,990 --> 01:04:38,620 >> JASON Hirschhorn: Three по модул три е равно на нула. 1382 01:04:38,620 --> 01:04:40,810 Това е голямо предположение, и това е вярно. 1383 01:04:40,810 --> 01:04:43,870 Така че в този случай той трябва да вероятно отидете на нула. 1384 01:04:43,870 --> 01:04:51,080 Така че по-добър начин да се гарантира, че тази хеш Функцията връща само валидни индекси се 1385 01:04:51,080 --> 01:04:54,580 да го по модул от размера на таблицата. 1386 01:04:54,580 --> 01:04:57,360 Ако имате каквито и да е по модул тази възвръщаемост от три, вие винаги ще получите 1387 01:04:57,360 --> 01:05:00,930 нещо средно между нула, едно, а две. 1388 01:05:00,930 --> 01:05:05,160 И ако това винаги се връща седем, и винаги по модул от три, ти си 1389 01:05:05,160 --> 01:05:06,030 Винаги ще получите едно и също нещо. 1390 01:05:06,030 --> 01:05:09,270 >> Така че тя все още е детерминирана ако по модул. 1391 01:05:09,270 --> 01:05:11,420 Но това ще гарантира, че никога няма да получите нещо - 1392 01:05:11,420 --> 01:05:12,940 невалиден индустрия. 1393 01:05:12,940 --> 01:05:16,840 Като цяло, че модул трябва да се случи вътре в хеш функция. 1394 01:05:16,840 --> 01:05:18,240 Така че не е нужно да се притеснявате за това. 1395 01:05:18,240 --> 01:05:20,555 Можете просто да се гарантира, че това е валидно indice. 1396 01:05:20,555 --> 01:05:23,700 1397 01:05:23,700 --> 01:05:26,700 Всякакви въпроси за тази потенциален капан? 1398 01:05:26,700 --> 01:05:36,590 1399 01:05:36,590 --> 01:05:39,060 >> OK. 1400 01:05:39,060 --> 01:05:40,290 И ето. 1401 01:05:40,290 --> 01:05:42,890 Следваща потенциален капан, и това е най-голямата. 1402 01:05:42,890 --> 01:05:46,880 Какво става, ако два ключа на картата на същата стойност? 1403 01:05:46,880 --> 01:05:49,350 Така че има два начина да се справим с това. 1404 01:05:49,350 --> 01:05:53,140 1405 01:05:53,140 --> 01:05:56,020 Първият от тях се нарича линеен сондиране, което съм 1406 01:05:56,020 --> 01:05:57,300 Няма да отида. 1407 01:05:57,300 --> 01:06:01,120 Но трябва да сте запознати с това как който работи и какво е това. 1408 01:06:01,120 --> 01:06:05,610 >> Вторият аз отивам да отидем защото това е тази, която много 1409 01:06:05,610 --> 01:06:08,290 хората вероятно ще приключи до вземането на решение да се използват в техен проблем набор. 1410 01:06:08,290 --> 01:06:09,820 Разбира се, че не е нужно да. 1411 01:06:09,820 --> 01:06:15,280 Но за набора проблем, много хора са склонни да избират дали да се създаде хеш таблица 1412 01:06:15,280 --> 01:06:17,950 с отделен верижното да приложат техния речник. 1413 01:06:17,950 --> 01:06:21,390 Така че ние ще отидем над това, което означава, че да се създаде хеш таблица с 1414 01:06:21,390 --> 01:06:23,890 отделна верижното. 1415 01:06:23,890 --> 01:06:26,260 >> Така че сложих в тиква. 1416 01:06:26,260 --> 01:06:29,560 Тя връща нула. 1417 01:06:29,560 --> 01:06:31,410 И сложих тиква тук. 1418 01:06:31,410 --> 01:06:35,880 1419 01:06:35,880 --> 01:06:37,930 След това сложих в - 1420 01:06:37,930 --> 01:06:39,922 това, което е още един Хелоуин-тематични нещо? 1421 01:06:39,922 --> 01:06:42,200 >> ПУБЛИКАТА: Candy. 1422 01:06:42,200 --> 01:06:42,770 >> JASON Hirschhorn: Candy! 1423 01:06:42,770 --> 01:06:43,910 Това е страхотно. 1424 01:06:43,910 --> 01:06:47,760 Сложих в бонбони и бонбони също ми дава нула. 1425 01:06:47,760 --> 01:06:49,350 Какво да правя? 1426 01:06:49,350 --> 01:06:51,940 Някакви идеи? 1427 01:06:51,940 --> 01:06:53,940 Защото всички видове знам какво е отделен верижното. 1428 01:06:53,940 --> 01:06:55,190 Така че някакви идеи какво да правя? 1429 01:06:55,190 --> 01:06:58,170 1430 01:06:58,170 --> 01:06:59,110 Да. 1431 01:06:59,110 --> 01:07:03,810 >> ПУБЛИКАТА: Поставянето на низ всъщност в хеш таблицата. 1432 01:07:03,810 --> 01:07:08,910 >> JASON Hirschhorn: Така че ние ще привлече добра идея тук. 1433 01:07:08,910 --> 01:07:09,340 OK. 1434 01:07:09,340 --> 01:07:12,290 >> ПУБЛИКАТА: Нека Hashtable [Недоловим] 1435 01:07:12,290 --> 01:07:16,640 показалеца, който сочи към началото на списъка. 1436 01:07:16,640 --> 01:07:20,930 И след това са тиква бъде първата стойност в тази свързан списък и бонбони бъде 1437 01:07:20,930 --> 01:07:22,800 втората стойност в този свързан списък. 1438 01:07:22,800 --> 01:07:23,420 >> JASON Hirschhorn: OK. 1439 01:07:23,420 --> 01:07:24,670 Marcus, това беше изключително. 1440 01:07:24,670 --> 01:07:26,160 Отивам да се прекъсне, че надолу. 1441 01:07:26,160 --> 01:07:28,890 Marcus казва не презапишете тиква. 1442 01:07:28,890 --> 01:07:30,660 Това би било лошо. 1443 01:07:30,660 --> 01:07:33,640 Не поставяйте бонбони някъде другаде. 1444 01:07:33,640 --> 01:07:35,390 Отиваме, за да ги сложи както на нула. 1445 01:07:35,390 --> 01:07:37,770 Но ние ще се справим с което ги излага на нула 1446 01:07:37,770 --> 01:07:39,395 създаване на списък на нула. 1447 01:07:39,395 --> 01:07:42,430 И ние отиваме да се създаде списък на всичко, което преобразува до нула. 1448 01:07:42,430 --> 01:07:47,960 И най-добрият начин сме се научили да се създаде списък, който може да расте и да се намалят 1449 01:07:47,960 --> 01:07:49,840 динамично не е в друг масив. 1450 01:07:49,840 --> 01:07:51,510 Така че не е многомерен масив. 1451 01:07:51,510 --> 01:07:54,080 Но просто да се създаде свързан списък. 1452 01:07:54,080 --> 01:07:55,330 >> Така че това, което той предложи - 1453 01:07:55,330 --> 01:07:57,950 1454 01:07:57,950 --> 01:07:59,200 Ще получите нова - 1455 01:07:59,200 --> 01:08:15,380 1456 01:08:15,380 --> 01:08:19,689 е да се създаде масив с указатели, масив от указатели. 1457 01:08:19,689 --> 01:08:20,580 OK. 1458 01:08:20,580 --> 01:08:24,180 Някаква идея или намек какво вида на тази указатели трябва да бъде? 1459 01:08:24,180 --> 01:08:26,290 Marcus? 1460 01:08:26,290 --> 01:08:27,250 >> ПУБЛИКАТА: указатели към - 1461 01:08:27,250 --> 01:08:28,609 >> JASON Hirschhorn: Защото каза свързан списък, така че - 1462 01:08:28,609 --> 01:08:29,520 >> ПУБЛИКАТА: указатели на възлите? 1463 01:08:29,520 --> 01:08:30,670 >> JASON Hirschhorn: указатели на възлите. 1464 01:08:30,670 --> 01:08:32,830 Ако нещата в нашата обвързана списък са възли тогава те 1465 01:08:32,830 --> 01:08:34,370 трябва да бъде възел указатели. 1466 01:08:34,370 --> 01:08:35,939 И какво те се равнява първоначално? 1467 01:08:35,939 --> 01:08:36,990 >> ПУБЛИКАТА: Null. 1468 01:08:36,990 --> 01:08:38,240 >> JASON Hirschhorn: Null. 1469 01:08:38,240 --> 01:08:44,540 1470 01:08:44,540 --> 01:08:46,080 Така че там е нашето празно нещо. 1471 01:08:46,080 --> 01:08:47,170 Тиквени връща нула. 1472 01:08:47,170 --> 01:08:48,569 Какво ще правим? 1473 01:08:48,569 --> 01:08:49,609 Разходка с мен чрез него? 1474 01:08:49,609 --> 01:08:50,810 Всъщност, Marcus вече ми даде. 1475 01:08:50,810 --> 01:08:52,439 Някой друг ме минеш през нея. 1476 01:08:52,439 --> 01:08:54,760 Какво правим, когато ние - 1477 01:08:54,760 --> 01:08:56,609 това изглежда много подобен на това, което ние просто правим. 1478 01:08:56,609 --> 01:08:57,396 Ави. 1479 01:08:57,396 --> 01:08:59,090 >> ПУБЛИКАТА: Отивам да взема предположение. 1480 01:08:59,090 --> 01:09:01,250 Така че, когато можете да получите бонбони. 1481 01:09:01,250 --> 01:09:01,640 >> JASON Hirschhorn: Да. 1482 01:09:01,640 --> 01:09:03,120 Е, имаме тиква. 1483 01:09:03,120 --> 01:09:03,870 Нека да вземем първия милион. 1484 01:09:03,870 --> 01:09:04,324 Имаме тиква. 1485 01:09:04,324 --> 01:09:04,779 >> ПУБЛИКАТА: OK. 1486 01:09:04,779 --> 01:09:05,880 Тиквени връща нула. 1487 01:09:05,880 --> 01:09:08,770 Така че да го поставите в това. 1488 01:09:08,770 --> 01:09:10,810 Или всъщност, да я поставите в свързан списък. 1489 01:09:10,810 --> 01:09:13,550 >> JASON Hirschhorn: Как правим я оплете в свързан списък? 1490 01:09:13,550 --> 01:09:15,479 >> ПУБЛИКАТА: О, действителната синтаксис? 1491 01:09:15,479 --> 01:09:16,240 >> JASON Hirschhorn: Просто върви - 1492 01:09:16,240 --> 01:09:16,740 да кажем нещо повече. 1493 01:09:16,740 --> 01:09:19,310 Какво ще правим? 1494 01:09:19,310 --> 01:09:22,100 >> Публика: Ти просто поставете че като първия възел. 1495 01:09:22,100 --> 01:09:22,675 >> JASON Hirschhorn: OK. 1496 01:09:22,675 --> 01:09:29,069 Така че ние имаме нашия възел, тиква. 1497 01:09:29,069 --> 01:09:31,560 И сега как да го поставите? 1498 01:09:31,560 --> 01:09:34,590 1499 01:09:34,590 --> 01:09:37,090 >> ПУБЛИКАТА: Вие определяте то към показалеца. 1500 01:09:37,090 --> 01:09:37,970 >> JASON Hirschhorn: Кои показалка? 1501 01:09:37,970 --> 01:09:39,620 >> ПУБЛИКАТА: Показалецът на нула. 1502 01:09:39,620 --> 01:09:41,420 >> JASON Hirschhorn: Е, къде прави този момент? 1503 01:09:41,420 --> 01:09:42,810 >> Публика: Да присвоява точно сега. 1504 01:09:42,810 --> 01:09:43,529 >> JASON Hirschhorn: Е, тя посочи към нула. 1505 01:09:43,529 --> 01:09:44,499 Но аз съм като в тиква. 1506 01:09:44,499 --> 01:09:46,053 Така че, когато трябва да го насочите? 1507 01:09:46,053 --> 01:09:46,880 >> Публика: Да тиква. 1508 01:09:46,880 --> 01:09:47,399 >> JASON Hirschhorn: Да тиква. 1509 01:09:47,399 --> 01:09:48,760 Точно така. 1510 01:09:48,760 --> 01:09:50,010 Така че това говори за тиква. 1511 01:09:50,010 --> 01:09:52,500 1512 01:09:52,500 --> 01:09:54,250 И къде е този указател в тиква точка? 1513 01:09:54,250 --> 01:09:57,986 1514 01:09:57,986 --> 01:09:58,340 За 1515 01:09:58,340 --> 01:09:58,590 >> ПУБЛИКАТА: Null. 1516 01:09:58,590 --> 01:09:59,210 >> JASON Hirschhorn: За нула. 1517 01:09:59,210 --> 01:10:00,460 Точно така. 1518 01:10:00,460 --> 01:10:03,570 1519 01:10:03,570 --> 01:10:05,140 Така че ние просто добавя нещо в свързан списък. 1520 01:10:05,140 --> 01:10:07,210 Ние току-що написах този код, за да направите това. 1521 01:10:07,210 --> 01:10:09,520 Почти ние почти го напълно смахнат. 1522 01:10:09,520 --> 01:10:10,790 Сега поставете бонбони. 1523 01:10:10,790 --> 01:10:13,480 Нашата бонбони също отива към нула. 1524 01:10:13,480 --> 01:10:16,100 И така, какво ще правим с бонбони? 1525 01:10:16,100 --> 01:10:18,790 >> ПУБЛИКАТА: Това зависи от това дали Не се опитваме да го оправи. 1526 01:10:18,790 --> 01:10:19,640 >> JASON Hirschhorn: Това е точно така. 1527 01:10:19,640 --> 01:10:21,070 Тя зависи от това дали или не ние се опитваме да го оправи. 1528 01:10:21,070 --> 01:10:22,660 Да предположим, че не сме ще го оправи. 1529 01:10:22,660 --> 01:10:24,880 >> ПУБЛИКАТА: Ами тогава, както ние обсъдихме и преди, най-простата си, само за да го сложи 1530 01:10:24,880 --> 01:10:28,590 още в самото начало, така че показалецът от нула точки за бонбони. 1531 01:10:28,590 --> 01:10:29,020 >> JASON Hirschhorn: OK. 1532 01:10:29,020 --> 01:10:29,380 Дръж се. 1533 01:10:29,380 --> 01:10:30,630 Нека създадем бонбони точно тук. 1534 01:10:30,630 --> 01:10:34,030 1535 01:10:34,030 --> 01:10:35,150 Така че този указател - 1536 01:10:35,150 --> 01:10:37,590 >> Публика: Да, сега следва да се посочи бонбони. 1537 01:10:37,590 --> 01:10:40,580 След това имате показалеца от бонбони точка за тиква. 1538 01:10:40,580 --> 01:10:43,140 1539 01:10:43,140 --> 01:10:44,560 >> JASON Hirschhorn: Така ли? 1540 01:10:44,560 --> 01:10:47,380 И казват, че имам още нещо за карта до нула? 1541 01:10:47,380 --> 01:10:48,660 >> ПУБЛИКАТА: Ами, просто направи същото нещо? 1542 01:10:48,660 --> 01:10:50,290 >> JASON Hirschhorn: Направете същото нещо. 1543 01:10:50,290 --> 01:10:53,700 Така че в този случай, ако не го направим искате да запазите това го сортирано 1544 01:10:53,700 --> 01:10:55,270 звучи доста просто. 1545 01:10:55,270 --> 01:10:59,920 Ние приемаме показалеца в indice дадена от нашия хеш функция. 1546 01:10:59,920 --> 01:11:03,830 Ние имаме този момент в нашия нов възел. 1547 01:11:03,830 --> 01:11:07,830 И след това каквото и да се посочи до преди това - 1548 01:11:07,830 --> 01:11:10,620 в този случай нула в вторият случай тиква - 1549 01:11:10,620 --> 01:11:15,310 че, каквото и да е, сочещи към по-рано, ние добавяме в най-близките 1550 01:11:15,310 --> 01:11:17,810 нашия нов възел. 1551 01:11:17,810 --> 01:11:19,650 Ще поставите нещо в началото. 1552 01:11:19,650 --> 01:11:22,900 В действителност това е много по-просто, отколкото опитвайки се да запази в списъка подредени. 1553 01:11:22,900 --> 01:11:25,340 Но отново, търсенето ще бъде по-сложно от тук. 1554 01:11:25,340 --> 01:11:28,300 Ние винаги ще трябва да отида до края. 1555 01:11:28,300 --> 01:11:29,650 >> OK. 1556 01:11:29,650 --> 01:11:32,750 Всякакви въпроси за отделни верижното? 1557 01:11:32,750 --> 01:11:34,690 Как работи това? 1558 01:11:34,690 --> 01:11:35,820 Моля, да ги питам сега. 1559 01:11:35,820 --> 01:11:39,260 Аз наистина искам да се уверете, че всички разберем това, преди да се отправите. 1560 01:11:39,260 --> 01:11:48,410 1561 01:11:48,410 --> 01:11:52,060 >> ПУБЛИКАТА: Защо ви постави тиква и бонбони в същото 1562 01:11:52,060 --> 01:11:54,108 част от хеш таблицата? 1563 01:11:54,108 --> 01:11:55,860 >> JASON Hirschhorn: Добър въпрос. 1564 01:11:55,860 --> 01:11:59,140 Защо ние да ги постави в същата част от хеш таблицата? 1565 01:11:59,140 --> 01:12:03,200 Е, в този случай нашата хеш функция връща нула за тях двамата. 1566 01:12:03,200 --> 01:12:05,310 Така че те трябва да отидат в indice нула защото това е мястото, където отиваме да 1567 01:12:05,310 --> 01:12:07,420 за да ги гледам, ако ние някога искам да ги гледам. 1568 01:12:07,420 --> 01:12:11,750 Отново, с подход линейни сондиране ние няма да ги пуснат едновременно на нула. 1569 01:12:11,750 --> 01:12:13,900 Но в подхода отделна верига, ние ще ги постави както на нула 1570 01:12:13,900 --> 01:12:16,620 и след това да създадете списък на разстояние от нула. 1571 01:12:16,620 --> 01:12:20,140 >> И ние не искаме да презапишете тиква просто за това, защото след това ще 1572 01:12:20,140 --> 01:12:21,860 приемем, че тиква е Никога не добавя. 1573 01:12:21,860 --> 01:12:25,230 Ако ние просто държа едно нещо в място, което би било лошо. 1574 01:12:25,230 --> 01:12:28,590 Тогава няма да има шанс от нас някога - 1575 01:12:28,590 --> 01:12:31,660 ако някога сте имали два екземпляра, тогава ние просто ще изтрие нашата първоначална стойност. 1576 01:12:31,660 --> 01:12:34,090 Така че това е защо правим този подход. 1577 01:12:34,090 --> 01:12:36,580 Или това е защо ние избрахме - но отново, ние изберете отделен подход верижното, 1578 01:12:36,580 --> 01:12:39,670 който има много други подходи човек може да избере. 1579 01:12:39,670 --> 01:12:41,185 Това отговаря ли на въпроса ти? 1580 01:12:41,185 --> 01:12:41,660 >> OK. 1581 01:12:41,660 --> 01:12:42,910 Карлос. 1582 01:12:42,910 --> 01:12:46,130 1583 01:12:46,130 --> 01:12:47,720 Linear сондиране ще включва - 1584 01:12:47,720 --> 01:12:51,913 ако ние открихме сблъсък на нула, ние ще изглежда в следващата място, за да се види дали 1585 01:12:51,913 --> 01:12:54,310 тя беше отворена и го сложи там. 1586 01:12:54,310 --> 01:12:57,320 И тогава ние с нетърпение в следващия спорта и да видим дали това е била отворена и го сложи там. 1587 01:12:57,320 --> 01:12:59,780 Така ние откриваме следващия наличен отворено място и го сложи там. 1588 01:12:59,780 --> 01:13:02,580 1589 01:13:02,580 --> 01:13:03,890 Някакви други въпроси? 1590 01:13:03,890 --> 01:13:05,370 Да, Ави. 1591 01:13:05,370 --> 01:13:07,490 >> ПУБЛИКАТА: Като продължение на тази, какво искаш да кажеш с следващото място? 1592 01:13:07,490 --> 01:13:10,250 В таблицата хашиш или в свързан списък. 1593 01:13:10,250 --> 01:13:12,100 >> JASON Hirschhorn: За линеен програмиране, не са свързани списъци. 1594 01:13:12,100 --> 01:13:13,400 Следващото място на хеш таблицата. 1595 01:13:13,400 --> 01:13:13,820 >> ПУБЛИКАТА: OK. 1596 01:13:13,820 --> 01:13:17,570 Така че хеш таблицата ще бъде инициализира с размера - 1597 01:13:17,570 --> 01:13:19,560 като броят на низове че си поставяте? 1598 01:13:19,560 --> 01:13:22,170 >> JASON Hirschhorn: Може би искам тя да бъде наистина голям. 1599 01:13:22,170 --> 01:13:23,910 Да. 1600 01:13:23,910 --> 01:13:27,900 Ето една снимка на това, което ние просто извади на дъската. 1601 01:13:27,900 --> 01:13:29,470 Отново имаме сблъсък точно тук. 1602 01:13:29,470 --> 01:13:30,710 на 152. 1603 01:13:30,710 --> 01:13:33,570 И ще видите, ние създадохме свързан списък на разстояние от него. 1604 01:13:33,570 --> 01:13:38,200 1605 01:13:38,200 --> 01:13:41,850 Отново, хеш таблица отделна навързването подход не е ли едно 1606 01:13:41,850 --> 01:13:45,590 трябва да се вземат за определени проблеми шест но е, че много от 1607 01:13:45,590 --> 01:13:47,100 студентите са склонни да се вземат. 1608 01:13:47,100 --> 01:13:51,140 Така че на тази бележка, нека поговорим накратко преди да се отправите за проблем шест, 1609 01:13:51,140 --> 01:13:52,160 и след това аз ще споделя една история с вас. 1610 01:13:52,160 --> 01:13:55,120 Имаме три минути. 1611 01:13:55,120 --> 01:13:55,750 >> Проблем създаде шест. 1612 01:13:55,750 --> 01:13:57,790 Имате четири функции - 1613 01:13:57,790 --> 01:14:02,430 натоварване, проверка, размер и разтоварване. 1614 01:14:02,430 --> 01:14:03,380 Load - 1615 01:14:03,380 --> 01:14:07,120 добре, ние сме били става над натоварване точно сега. 1616 01:14:07,120 --> 01:14:09,330 Ние привлече натоварване на дъската. 1617 01:14:09,330 --> 01:14:13,230 И ние дори започна кодиране много поставите в свързан списък. 1618 01:14:13,230 --> 01:14:18,020 Така че натоварването не е много повече от това, което току-що сте били прави. 1619 01:14:18,020 --> 01:14:21,070 >> Проверка е след като имате нещо зареден. 1620 01:14:21,070 --> 01:14:22,580 Това е един и същ процес, тъй като това. 1621 01:14:22,580 --> 01:14:26,845 Същите първите две части, където можете да хвърлят нещо в хеш функция 1622 01:14:26,845 --> 01:14:29,190 и да получите стойността си. 1623 01:14:29,190 --> 01:14:30,700 Но сега ние не сме го поставите. 1624 01:14:30,700 --> 01:14:33,350 Сега ние не търсим за него. 1625 01:14:33,350 --> 01:14:37,130 Имам примерен код, написан за намиране нещо в свързан списък. 1626 01:14:37,130 --> 01:14:38,250 Насърчавам ви да практикуват това. 1627 01:14:38,250 --> 01:14:43,000 Но интуитивно намери нещо доста сходен с вмъкване нещо. 1628 01:14:43,000 --> 01:14:46,540 В действителност, ние нарисува картина за намиране на нещо в свързан списък, движейки 1629 01:14:46,540 --> 01:14:48,910 чрез, докато не стигнах до края. 1630 01:14:48,910 --> 01:14:52,430 И ако имаш до края и не можах го намерите, то не е там. 1631 01:14:52,430 --> 01:14:55,400 Така че това е проверка по същество. 1632 01:14:55,400 --> 01:14:57,030 >> След това е размер. 1633 01:14:57,030 --> 01:14:57,910 Нека прескочим размер. 1634 01:14:57,910 --> 01:15:00,040 Най-накрая сте се разтоварят. 1635 01:15:00,040 --> 01:15:02,890 Разтоварете е едно ние не са изготвили върху дъската или още кодирани. 1636 01:15:02,890 --> 01:15:05,990 Но аз ви насърчавам да се опита да го кодиране в нашата извадка свързан списък например. 1637 01:15:05,990 --> 01:15:11,440 Но разтоварят интуитивно е подобен на свободно - 1638 01:15:11,440 --> 01:15:14,010 или искам да кажа е подобна, за да проверите. 1639 01:15:14,010 --> 01:15:17,350 С изключение на сега всеки път, когато започваш чрез, вие не просто проверка, за да 1640 01:15:17,350 --> 01:15:19,090 виж, ако имате стойност там. 1641 01:15:19,090 --> 01:15:22,490 Но вие приемате този възел и го освободят, по същество. 1642 01:15:22,490 --> 01:15:23,610 Това е, което разтовари иска от вас да направите. 1643 01:15:23,610 --> 01:15:24,670 Free всичко, което сте malloced. 1644 01:15:24,670 --> 01:15:27,480 Така че ти започваш през целия списък отново, преминавайки през целия хеш 1645 01:15:27,480 --> 01:15:27,760 маса отново. 1646 01:15:27,760 --> 01:15:29,240 Този път не проверяват за да видите какво е там. 1647 01:15:29,240 --> 01:15:31,080 Просто освободи това, което е там. 1648 01:15:31,080 --> 01:15:33,260 >> И накрая размер. 1649 01:15:33,260 --> 01:15:34,350 Размер трябва да бъдат приложени. 1650 01:15:34,350 --> 01:15:35,590 Ако не се приложи размер - 1651 01:15:35,590 --> 01:15:36,250 Ще го кажа по този начин. 1652 01:15:36,250 --> 01:15:39,740 Ако не се приложи размер в точно един ред код, включително 1653 01:15:39,740 --> 01:15:43,760 върнете изявление, вие сте правите размер неправилно. 1654 01:15:43,760 --> 01:15:47,170 Така че се уверете, че размера, за пълна проектантска точки, което го прави по абсолютно един 1655 01:15:47,170 --> 01:15:49,970 ред с код, в това число изявлението замяна. 1656 01:15:49,970 --> 01:15:52,450 >> И не опаковам още, Akchar. 1657 01:15:52,450 --> 01:15:53,700 Нетърпелив бобър. 1658 01:15:53,700 --> 01:15:55,820 1659 01:15:55,820 --> 01:16:01,300 Исках да кажа, благодаря ви момчета за идване в раздел. 1660 01:16:01,300 --> 01:16:02,550 Имате Happy Halloween. 1661 01:16:02,550 --> 01:16:05,300 1662 01:16:05,300 --> 01:16:05,960 Това е моят костюм. 1663 01:16:05,960 --> 01:16:08,850 Ще бъде облечен тази в четвъртък ако те видя в работно време. 1664 01:16:08,850 --> 01:16:14,640 И ако сте любопитни за някои по- фон като на този костюм, се чувстват 1665 01:16:14,640 --> 01:16:19,135 безплатно да проверите 2011 раздел за една история за това, защо съм 1666 01:16:19,135 --> 01:16:20,900 носенето на тиква костюм. 1667 01:16:20,900 --> 01:16:23,680 И това е една тъжна история. 1668 01:16:23,680 --> 01:16:27,050 Така че се уверете, че имате близките някои тъкани. 1669 01:16:27,050 --> 01:16:28,680 Но по този въпрос, ако имате някакви въпроси, аз ще се придържаме около 1670 01:16:28,680 --> 01:16:29,960 извън след раздел. 1671 01:16:29,960 --> 01:16:31,510 Успех на проблема определя шест. 1672 01:16:31,510 --> 01:16:33,540 И както винаги, ако имате някакви въпроси, да ме уведомите. 1673 01:16:33,540 --> 01:16:35,584