1 00:00:00,000 --> 00:00:08,250 2 00:00:08,250 --> 00:00:12,680 >> Джейсон Хиршхорн: Приветствую всех в разделе 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 >> Джейсон Хиршхорн: 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 Разница позволит вам сделать это, а также. 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 Она сочетает в себе указатели, которые мы посещали работы с, и структуры, которые позволяют 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 >> Джейсон Хиршхорн: Это Совершенно верно. 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 >> Джейсон Хиршхорн: Так это не создать новый узел. 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 >> АУДИТОРИЯ: Указатель. 112 00:05:29,300 --> 00:05:33,460 >> Джейсон Хиршхорн: указатель на узел, как указано этом узел * здесь. 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 >> АУДИТОРИЯ: Новый узел? 116 00:05:38,440 --> 00:05:39,240 >> Джейсон Хиршхорн: Новый узел. 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 что действительно эта вещь прямо здесь является просто синтаксический сахар для разыменования 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 ОК. 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 Связанный список, напомним, представляет собой серию узлов, которые указывают на другом. 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 Четыре. 163 00:07:43,710 --> 00:07:45,470 И, насколько большой это указатель? 164 00:07:45,470 --> 00:07:45,940 Четыре. 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 ОК. 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 Маркус? 189 00:08:39,179 --> 00:08:40,679 >> АУДИТОРИЯ: Позвоните указатель к следующему узлу. 190 00:08:40,679 --> 00:08:42,530 >> Джейсон Хиршхорн: И почему мы идем к следующему? 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 >> Джейсон Хиршхорн: И пять больше, чем два, в частности. 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 >> АУДИТОРИЯ: Шесть больше пяти. 207 00:09:10,544 --> 00:09:11,480 >> Джейсон Хиршхорн: Шесть является больше пяти. 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 >> АУДИТОРИЯ: Два. 216 00:09:32,280 --> 00:09:32,920 >> Джейсон Хиршхорн: Два. 217 00:09:32,920 --> 00:09:35,720 Один отслеживать тока один и один, чтобы отслеживать 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 >> Джейсон Хиршхорн: Совершенно верно. 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 >> Джейсон Хиршхорн: Придерживайтесь его на начало или конец. 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 >> Джейсон Хиршхорн: ОК. 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 Маркус. 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 >> Джейсон Хиршхорн: Совершенно верно. 254 00:10:52,990 --> 00:10:57,970 Так что, если мы думаем о выполнения, Время работы, включив в конце 255 00:10:57,970 --> 00:11:00,110 бы н, размер этого. 256 00:11:00,110 --> 00:11:03,080 Что такое большое O выполнения вставки в начале? 257 00:11:03,080 --> 00:11:04,170 Постоянное время. 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 >> ОК. 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 Скажи я ищу девяти и I дойдете до конца списка. 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 >> Джейсон Хиршхорн: Вернуться ложным. 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 >> Джейсон Хиршхорн: Совершенно верно. 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 >> Джейсон Хиршхорн: Если вы хотите, чтобы освободить то, что совершенно верно, и вы 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 >> ОК. 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 Тем не менее, прежде чем в его кодирования в С, я настоятельно рекомендую вам пойти 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 Но я хотел бы призвать вас, чтобы написать некоторые псевдокод, прежде чем погрузиться дюйма 359 00:15:36,590 --> 00:15:38,640 И мы собираемся перейти на псевдокод как группа. 360 00:15:38,640 --> 00:15:41,470 А потом, как только вы написали псевдокод, и как только мы написали наш 361 00:15:41,470 --> 00:15:45,850 псевдокод как группа, вы можете идти в кодирования его в С. 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 И почему бы вам не взять 6:55 минут только, чтобы получить работу на 368 00:16:06,470 --> 00:16:07,640 псевдокод и код. 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 >> Давайте начнем с написания некоторых псевдокод на доске. 382 00:20:16,330 --> 00:20:19,395 Кто может дать мне первую линию псевдокод для этой программы? 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 >> Джейсон Хиршхорн: ОК. 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 >> Джейсон Хиршхорн: ОК. 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 мы должны Malloc пространство для узла. 404 00:21:02,160 --> 00:21:02,455 >> Джейсон Хиршхорн: Отлично. 405 00:21:02,455 --> 00:21:03,210 Давайте сделаем - 406 00:21:03,210 --> 00:21:04,628 ОК. 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 ОК. 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 ОК. 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 >> Джейсон Хиршхорн: Хороший вопрос. 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 >> Джейсон Хиршхорн: Да. 433 00:21:55,470 --> 00:21:56,500 Наверное освободить его. 434 00:21:56,500 --> 00:21:56,760 ОК. 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 >> Джейсон Хиршхорн: Совершенно верно. 439 00:22:05,140 --> 00:22:07,190 Мы, число - мы Malloc пространство. 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 Мы Malloc пробел, а затем мы ставим номер дюйма 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 >> Джейсон Хиршхорн: Пройтись по списку. 450 00:22:23,930 --> 00:22:30,620 451 00:22:30,620 --> 00:22:31,100 ОК. 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 >> Джейсон Хиршхорн: ОК. 457 00:22:43,340 --> 00:22:44,280 Я собираюсь сделать - 458 00:22:44,280 --> 00:22:45,855 да, хорошо. 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 >> Джейсон Хиршхорн: ОК. 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 >> Джейсон Хиршхорн: Мне это нравится. 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 >> Джейсон Хиршхорн: Да. 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 ОК. 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 ОК. 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 >> Джейсон Хиршхорн: ОК. 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 >> Джейсон Хиршхорн: Какие один, в частности? 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 >> Джейсон Хиршхорн: Так что, если наша значение больше, чем значение этого узла. 523 00:25:49,515 --> 00:25:52,130 >> АУДИТОРИЯ: Да, то вы хотели бы идти дальше по линии, не так ли? 524 00:25:52,130 --> 00:25:52,590 >> Джейсон Хиршхорн: Верно. 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 >> Джейсон Хиршхорн: Хороший вопрос. 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 >> Джейсон Хиршхорн: И так что нам делать здесь? 539 00:26:30,310 --> 00:26:36,790 540 00:26:36,790 --> 00:26:38,160 Сладкий. 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 это в С. 550 00:28:19,240 --> 00:28:20,940 >> Так что я свой вклад псевдокод. 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 >> ОК. 567 00:29:00,370 --> 00:29:01,960 Начнем. 568 00:29:01,960 --> 00:29:04,770 Асам, как мы создаем новый узел? 569 00:29:04,770 --> 00:29:06,810 >> АУДИТОРИЯ: Вы структуры *. 570 00:29:06,810 --> 00:29:09,640 >> Джейсон Хиршхорн: Таким образом, мы есть, что здесь. 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 >> Джейсон Хиршхорн: ОК. 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 >> Джейсон Хиршхорн: ОК. 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 Malloc. 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 >> Джейсон Хиршхорн: размер структуры. 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 >> АУДИТОРИЯ: Узел? 591 00:30:09,840 --> 00:30:11,640 >> Джейсон Хиршхорн: Узел. 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 И что же нам делать сразу после мы Malloc что-то, Асан? 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 >> Джейсон Хиршхорн: Совершенно верно. 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 >> Джейсон Хиршхорн: ОК. 621 00:31:27,230 --> 00:31:29,255 Таким образом, текущий узел мы на. 622 00:31:29,255 --> 00:31:30,505 Я позвоню, что ин. 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 >> Джейсон Хиршхорн: Так в чем же Первое, что в нашем списке? 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 >> Джейсон Хиршхорн: Верно. 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 >> АУДИТОРИЯ: Список. 640 00:32:22,110 --> 00:32:22,900 >> Джейсон Хиршхорн: Список. 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 >> Джейсон Хиршхорн: Там в ничего перед ним. 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 >> Джейсон Хиршхорн: Да. 649 00:32:35,450 --> 00:32:37,950 Это звучит как хорошая идея. 650 00:32:37,950 --> 00:32:38,360 Прекрасно. 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 >> Джейсон Хиршхорн: ОК. 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 >> Джейсон Хиршхорн: Давайте сделаем цикл. 660 00:32:53,910 --> 00:32:55,870 ОК. 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 до текущего указателя не равен NULL. 664 00:33:13,390 --> 00:33:19,160 >> Джейсон Хиршхорн: Так что, если мы знаем, что состояние, как мы можем написать цикл 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 >> Джейсон Хиршхорн: Да. 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 В то время как ток не равен NULL, если значение меньше этого узла. 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 >> Джейсон Хиршхорн: Извините. 680 00:34:06,620 --> 00:34:08,760 >> АУДИТОРИЯ: Измените кронштейн. 681 00:34:08,760 --> 00:34:10,914 >> Джейсон Хиршхорн: Так что, если это больше, чем значение. 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 О. 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 ОК. 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 >> Джейсон Хиршхорн: Да. 694 00:34:36,150 --> 00:34:38,520 695 00:34:38,520 --> 00:34:39,770 >> АУДИТОРИЯ: Вы - 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 >> Джейсон Хиршхорн: Так в чем что собирается равняться? 700 00:34:50,163 --> 00:34:52,070 >> АУДИТОРИЯ: Это будет равной тока. 701 00:34:52,070 --> 00:34:53,889 >> Джейсон Хиршхорн: Совершенно верно. 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 >> Джейсон Хиршхорн: Если предыдущая - 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 >> Джейсон Хиршхорн: Это означает это стать главой. 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 >> Джейсон Хиршхорн: Руководитель равна 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 >> Джейсон Хиршхорн: Сладкий. 715 00:35:26,190 --> 00:35:33,750 716 00:35:33,750 --> 00:35:34,170 ОК. 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 >> Джейсон Хиршхорн: Куда мы устанавливаем 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 >> Джейсон Хиршхорн: Так что линия? 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 >> Джейсон Хиршхорн: Прямо здесь? 728 00:36:13,057 --> 00:36:18,335 >> АУДИТОРИЯ: я сделаю new_node-> п равна стоимости. 729 00:36:18,335 --> 00:36:19,585 >> Джейсон Хиршхорн: Звучит хорошо. 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 >> АУДИТОРИЯ: Если значение больше чем вал-> п - 745 00:37:07,100 --> 00:37:16,830 746 00:37:16,830 --> 00:37:18,240 >> Джейсон Хиршхорн: Как сделать мы идем к следующему узлу? 747 00:37:18,240 --> 00:37:27,760 748 00:37:27,760 --> 00:37:30,530 >> АУДИТОРИЯ: Керр-> п равна new_node. 749 00:37:30,530 --> 00:37:37,630 750 00:37:37,630 --> 00:37:39,195 >> Джейсон Хиршхорн: Так п какая часть структуры? 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 Так что часть тек мы должны обновить? 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 >> Джейсон Хиршхорн: Далее, точно. 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 >> Джейсон Хиршхорн: Так мы обновили ток. 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 >> Джейсон Хиршхорн: Да. 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 Ману, что мы должны делать? 773 00:39:03,385 --> 00:39:05,615 >> АУДИТОРИЯ: Вы должны установить его равным тек-> следующий. 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 >> Джейсон Хиршхорн: ОК. 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 Я думаю, вы в виду, чтобы сделать вал равных вал-> Далее для перехода к следующему узлу. 782 00:39:29,270 --> 00:39:30,500 >> Джейсон Хиршхорн: Так жаль, где? 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 Сделать вал равна вал-> следующая. 787 00:39:35,745 --> 00:39:39,690 788 00:39:39,690 --> 00:39:43,360 >> Джейсон Хиршхорн: Так вот правильно поскольку в настоящее время является 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 Сам Керр имеет следующий. 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 >> АУДИТОРИЯ: Предыдущая-> следующая равна ин. 799 00:40:09,590 --> 00:40:12,500 800 00:40:12,500 --> 00:40:19,440 >> Джейсон Хиршхорн: Итак, еще раз, если пред является указатель на узел, пред-> следующий является 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 >> Джейсон Хиршхорн: Верно. 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 ОК Давайте двигаться вниз. 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 >> АУДИТОРИЯ: Если значение равна вал-> п. 814 00:40:47,515 --> 00:40:51,030 815 00:40:51,030 --> 00:40:51,300 >> Джейсон Хиршхорн: Извините. 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 Значение == вал-> п. 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 >> Джейсон Хиршхорн: Это то, что мы написали до сих пор. 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 ОК. 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 >> Джейсон Хиршхорн: Я не знаю. 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 >> Джейсон Хиршхорн: 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 >> Джейсон Хиршхорн: Так где Вы хотите, чтобы это пошло? 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 >> Джейсон Хиршхорн: ОК. 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 >> Джейсон Хиршхорн: О, мы сделать это в обоих местах? 849 00:42:15,040 --> 00:42:15,650 >> АУДИТОРИЯ: Да. 850 00:42:15,650 --> 00:42:16,900 >> Джейсон Хиршхорн: ОК. 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 ОК. 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 ОК. 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 ОК. 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 Следующая. 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 >> Джейсон Хиршхорн: Поехали - давайте посмотрим в 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 ОК. 900 00:43:59,390 --> 00:44:00,150 Мы вставить. 901 00:44:00,150 --> 00:44:00,770 Пожалуйста, введите Int. 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 >> Джейсон Хиршхорн: Я просто вытащил его. 913 00:44:22,930 --> 00:44:27,364 914 00:44:27,364 --> 00:44:28,310 ОК. 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 >> Джейсон Хиршхорн: Ничего себе. 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 >> Джейсон Хиршхорн: Я знаю. 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 Перерыв не возьмет меня внутри. 936 00:46:42,390 --> 00:46:46,200 937 00:46:46,200 --> 00:46:47,130 Знает ли маркиза? 938 00:46:47,130 --> 00:46:48,240 >> АУДИТОРИЯ: Что? 939 00:46:48,240 --> 00:46:51,780 >> Джейсон Хиршхорн: Какая команда GDB Я использую, чтобы зайти внутрь этой функции? 940 00:46:51,780 --> 00:46:52,070 >> АУДИТОРИЯ: Шаг? 941 00:46:52,070 --> 00:46:55,140 >> Джейсон Хиршхорн: Шаг через С. Это берет меня внутри. 942 00:46:55,140 --> 00:46:55,476 ОК. 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 >> АУДИТОРИЯ: В чем разница между Р и дисплея? 952 00:47:14,530 --> 00:47:16,160 >> Джейсон Хиршхорн: Р обозначает для печати. 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 >> ОК. 961 00:47:34,640 --> 00:47:40,300 Таким образом, мы находимся на линии 80 нашего кода, установка узла * Curr равную списка. 962 00:47:40,300 --> 00:47:42,500 Давайте распечатать ин. 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 Сладкий. 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 >> Поэтому у нас есть ин. 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 В то время как вал не равен NULL. 985 00:48:29,310 --> 00:48:31,110 Ну, что делает вал равны? 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 >> Джейсон Хиршхорн: Так что, когда я набрал, что линия, вы видите, мы вскочили на всем пути 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 >> Первый вставка, вал, по умолчанию равна нулю. 1005 00:49:10,690 --> 00:49:14,050 И этот цикл выполняется только если вал не является нулевым. 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 изменить его на сделай время цикла. 1014 00:49:39,948 --> 00:49:41,250 >> Джейсон Хиршхорн: ОК. 1015 00:49:41,250 --> 00:49:44,240 Будет ли это решить нашу проблему, хотя? 1016 00:49:44,240 --> 00:49:47,750 >> не AUDIENCE: В этом случае нет из-за тот факт, что список пуст. 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 >> Джейсон Хиршхорн: Мне это нравится. 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 >> Джейсон Хиршхорн: ОК. 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 >> АУДИТОРИЯ: зав. 1043 00:50:56,090 --> 00:50:57,566 >> Джейсон Хиршхорн: Извините? 1044 00:50:57,566 --> 00:50:59,440 >> АУДИТОРИЯ: руководитель указывает в конце списка. 1045 00:50:59,440 --> 00:51:01,480 >> Джейсон Хиршхорн: Если нет ничего в список, голова указывая на 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 Чем мы не хотим, чтобы установить возглавить равно 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 >> Зала: Я думаю, что вы сделать текущий-> Next. 1064 00:51:46,870 --> 00:51:50,186 1065 00:51:50,186 --> 00:51:52,550 >> Джейсон Хиршхорн: ОК. 1066 00:51:52,550 --> 00:51:54,010 вал-> следующая. 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 >> Джейсон Хиршхорн: И так, что произойдет, если мы делаем нуль-> дальше? 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 вал равна нулю. 1074 00:52:08,880 --> 00:52:10,760 >> Джейсон Хиршхорн: Это то же самое, как предыдущая, хотя, потому что есть 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 >> АУДИТОРИЯ: Предыдущий-> дальше? 1083 00:52:36,680 --> 00:52:41,980 >> Джейсон Хиршхорн: Предыдущий-> следующая является то, что мы хотим обновить, потому что 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 >> Джейсон Хиршхорн: О, это будет собирается вернуться ложным. 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 >> Джейсон Хиршхорн: Так предыдущая еще равна нуль в самом начале. 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 >> Джейсон Хиршхорн: ОК. 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 >> Джейсон Хиршхорн: Если голова равна равна нуль - 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 >> Джейсон Хиршхорн: Руководитель равна 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 >> Джейсон Хиршхорн: Не совсем. 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 >> Джейсон Хиршхорн: Точно, Олден. 1116 00:53:44,570 --> 00:53:46,600 И тогда мы сможем вернуться верно. 1117 00:53:46,600 --> 00:53:47,560 ОК. 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 >> Джейсон Хиршхорн: Да. 1130 00:54:11,000 --> 00:54:14,190 И то, что нам нужно изменить это? 1131 00:54:14,190 --> 00:54:15,440 Правда. 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 >> Джейсон Хиршхорн: ОК. 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 >> ОК. 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 >> Джейсон Хиршхорн: О, Я не делал это. 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 Линия 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 >> Джейсон Хиршхорн: Отлично. 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 Компиляция. 1163 00:55:17,220 --> 00:55:17,890 ОК. 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 >> АУДИТОРИЯ: Семь. 1173 00:55:31,940 --> 00:55:33,340 >> Джейсон Хиршхорн: Семь? 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 >> Джейсон Хиршхорн: У нас есть неисправность сегм. 1177 00:55:39,780 --> 00:55:43,760 Таким образом, мы получили один, но мы четко не может получить два. 1178 00:55:43,760 --> 00:55:45,690 Это 5: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 получить сегм ложным в этом случае. 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 >> Джейсон Хиршхорн: Это не то, что это значит. 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 >> Джейсон Хиршхорн: Это Совершенно верно. 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 >> ОК. 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 Мой хэш-функция подсчитывает буквы в слове. 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 >> Джейсон Хиршхорн: Почему нулю? 1380 01:04:32,120 --> 01:04:35,990 >> АУДИТОРИЯ: Потому что три модулю три равна нулю? 1381 01:04:35,990 --> 01:04:38,620 >> Джейсон Хиршхорн: Три модулю три равна нулю. 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 >> ОК. 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 >> АУДИТОРИЯ: Конфеты. 1422 01:06:42,200 --> 01:06:42,770 >> Джейсон Хиршхорн: Конфеты! 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 >> Джейсон Хиршхорн: Таким образом, мы собираемся привлечь хорошую идею здесь. 1433 01:07:08,910 --> 01:07:09,340 ОК. 1434 01:07:09,340 --> 01:07:12,290 >> АУДИТОРИЯ: Есть хэш-таблице [Неразборчиво] 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 >> Джейсон Хиршхорн: ОК. 1439 01:07:23,420 --> 01:07:24,670 Маркус, который был замечательным. 1440 01:07:24,670 --> 01:07:26,160 Я собираюсь разрушить это. 1441 01:07:26,160 --> 01:07:28,890 Маркус говорю, не перезаписать тыкву. 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 ОК. 1458 01:08:20,580 --> 01:08:24,180 Любая идея или намек, что тип этого указателей должно быть? 1459 01:08:24,180 --> 01:08:26,290 Маркус? 1460 01:08:26,290 --> 01:08:27,250 >> АУДИТОРИЯ: Указатели на - 1461 01:08:27,250 --> 01:08:28,609 >> Джейсон Хиршхорн: Потому что вам сказал связанный список, а значит - 1462 01:08:28,609 --> 01:08:29,520 >> АУДИТОРИЯ: Node указатели? 1463 01:08:29,520 --> 01:08:30,670 >> Джейсон Хиршхорн: Node указатели. 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 >> Джейсон Хиршхорн: 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 На самом деле, Маркус уже дал мне. 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 >> Джейсон Хиршхорн: Да. 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 >> АУДИТОРИЯ: ОК. 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 >> Джейсон Хиршхорн: Как мы положить его в связанном списке? 1490 01:09:13,550 --> 01:09:15,479 >> АУДИТОРИЯ: О, фактический синтаксис? 1491 01:09:15,479 --> 01:09:16,240 >> Джейсон Хиршхорн: Просто ходить - 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 >> Джейсон Хиршхорн: ОК. 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 >> Джейсон Хиршхорн: Какие указатель? 1501 01:09:37,970 --> 01:09:39,620 >> АУДИТОРИЯ: Указатель на нуле. 1502 01:09:39,620 --> 01:09:41,420 >> Джейсон Хиршхорн: Так где делает это смысл? 1503 01:09:41,420 --> 01:09:42,810 >> АУДИТОРИЯ: Чтобы обнулить прямо сейчас. 1504 01:09:42,810 --> 01:09:43,529 >> Джейсон Хиршхорн: Ну, это указывает на нуль. 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 >> Джейсон Хиршхорн: Для тыквы. 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 >> Джейсон Хиршхорн: Чтобы обнулить. 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 >> Джейсон Хиршхорн: Это Совершенно верно. 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 >> Джейсон Хиршхорн: ОК. 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 >> Джейсон Хиршхорн: Как что? 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 >> Джейсон Хиршхорн: Сделайте то же самое. 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 >> ОК. 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 >> Джейсон Хиршхорн: Хороший вопрос. 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 >> ОК. 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 Линейный зондирования будет включать - 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 >> Джейсон Хиршхорн: Для линейных программирование, не связанные списки. 1594 01:13:12,100 --> 01:13:13,400 На следующий пятно на хэш-таблице. 1595 01:13:13,400 --> 01:13:13,820 >> АУДИТОРИЯ: ОК. 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 >> Джейсон Хиршхорн: Вы бы хочу, чтобы это действительно большой. 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 Нагрузка - 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 Бесплатный все, что вы 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