ДАГ Lloyd: Так в CS50, мы рассмотрели много различных структур данных, правильно? Мы видели массивы, и связано списки, хэш-таблицы и, и пытается, стеки и очереди. Мы также узнаем немного о деревьях и кучи, но на самом деле это всего лишь конец тем, что вариации на тему. Там на самом деле это вид из четырех основных идей что все еще может сводиться к. Массивы, связанные списки, хэш-таблицы, и пытается. И, как я уже сказал, вариации на них, но это довольно много происходит обобщить все, что мы будем говорить о в этом классе с точки зрения С. Но как сделать это все мерой, верно? Мы говорили о плюсах и минусах каждого из них в отдельных видео на них, но есть много цифр получать бросил вокруг. Там очень много общего мысли получать разбросаны. Давайте попробуем и консолидации это в одном месте. Давайте взвешивать плюсы от минусы, и рассмотреть в состав которого данные может быть правильным данных структура вашей конкретной ситуации, независимо от вида данных, которые вы хранения. Вам не обязательно всегда должны использовать сверхбыструю вставки, удаления, и поиск из синтаксического дерева, если вы действительно не заботятся о вставки и удаления слишком. Если вам нужно просто быстро случайных доступа, может быть, массив, тем лучше. Итак, давайте перегонять, что. Давайте поговорим о каждом из четырех основных вида структур данных что мы говорили, и просто видеть, когда они могли бы быть хорошо, и когда они не могут быть так хорошо. Итак, давайте начнем с массивами. Так вставки, это своего рода плохо. 

Вносимые в конце массива в порядке, если мы строим массив, как мы идем. Но если нам нужно вставить элементы в середине, вспомните вставки сортировать, есть много сдвига, чтобы соответствовать элемент там. И поэтому, если мы собираемся, чтобы вставить где угодно, но в конце массива, это, наверное, не так уж велика. 

Аналогично, удаление, если мы не удаление с конца массива, это, вероятно, также не так здорово, если мы не хотим, чтобы оставить пустые пробелы, которые обычно мы не делаем. Мы хотим, чтобы удалить элемент, и потом вроде сделать это уютно снова. И так удаления элементов из массив, а также не столь велика. 

Поиск, однако, это здорово. У нас есть произвольный доступ, постоянная времени поиска. Мы просто скажем, семь, и мы идем массиву переселения семь. Мы говорим 20, с ходу в Массив переселение 20. Мы не должны повторять через. Это очень хорошо. 

Массивы также относительно легко сортировать. Каждый раз, когда мы говорили о сортировке Алгоритм, таких как выбор вида, сортировка вставками, пузырьковая сортировка, слияние сортировать, мы всегда использовали массивы, чтобы сделать это, потому что массивы довольно легко рода, по отношению к структурам данных мы видели до сих пор. 

Они также относительно невелик. Там не так много дополнительного пространства. Вы просто отложите ровно столько как вам нужно, чтобы держать ваши данные, и это довольно много его. Так они довольно малы и эффективной таким образом. Но другой недостаток, хотя, является то, что они не будут устранены в размере. Мы должны объявить, как именно большой, мы хотим наш массив, чтобы быть, и мы только один выстрел на него. Мы не можем расти и сжать его. 

Если мы должны расти или сжать его, мы нужно объявить совершенно новый массив, скопировать все элементы Первый массив во второй массив. И если мы просчитались, что раз мы должны сделать это снова. Не так здорово. Так массивы не дают нам гибкость чтобы иметь переменное количество элементов. 

С связанного списка, вставка довольно легко. Мы просто лавировать на фронте. Удаление также довольно легко. Мы должны найти элементы. Это включает некоторый поиск. 

Но как только вы нашли элемент Вы ищете, все, что вам нужно сделать, это изменить указатель, возможно два, если у вас есть связанный list-- вдвойне Связанный список, rather-- и тогда вы можете просто освободить узел. Вы не должны перекладывать все вокруг. Вы просто изменить два указателя, так что это довольно быстро. 

Поиск плохо, верно? Для того, чтобы нам найти элемент связанного списка, ли по отдельности или двойной связью, мы должны искать его линейным. Мы должны начать с самого начала и переместить конец, или начать в конце хода к началу. Мы не имеем произвольный доступ больше. Так что, если мы делаем Много поиска, может быть, связанный список не является совсем так хорошо для нас. 

Они также очень трудно разобраться, не так ли? Единственный способ вы можете действительно сортировки связанного списка для сортировки его, как вы построить его. Но если вы сортировать его, как вы не построить его, вы больше не принятия быстрых вставок больше. Вы не просто лавировать вещи на фронт. Вы должны найти правильное место, чтобы положить его, и тогда ваш вставки становится почти так же плохо как вставка в массив. Так связанные списки не так здорово для сортировки данных. 

Они также довольно небольшой, размер-мудрый. Двунаправленный список немного больше, чем по отдельности, связанных списков, который немного больше по сравнению с массивами, но это не огромное количество неиспользуемого пространства. Так что, если пространство в большом почете, но не очень интенсивным премиум, это может быть правильный путь. 

Хэш-таблицы. Вносимые в хэш-таблице довольно проста. Это двухступенчатый процесс. Во-первых, мы должны запустить наши данные через хэш-функция, чтобы получить хэш-код, а затем вставляем элемент в хеш-таблица в этой хэш-код расположения. 

Удаление, подобно связанного списка, легко, как только вы найдете элемент. Вы должны найти его первым, но потом, когда вы удалите его, вам просто нужно обменять пару указателей, если вы используете отдельный цепочки. Если вы используете зондирования, или если вы не с помощью цепочки на всех в хеш-таблицы, удаление на самом деле очень просто. Все, что вам нужно сделать, это хеш Данные, а затем перейти к этому месту. И если вы не есть какие-либо столкновений, Вы сможете удалить очень быстро. 

Теперь, поиск, где вещи получить немного сложнее. Это в среднем лучше, чем связанные списки. Если вы используете цепочки, Вы все еще есть связанный список, который означает, что вы по-прежнему имеют Поиск ущерб связанный список. Но потому, что вы принимать ваши связано Перечень и разделения его на 100 или 1000 или п элементов в вашей хэш-таблицы, вы связанные списки все одно п-размера. Они все значительно меньше. Вы н связанные списки вместо одного связанного списка размера п. 

И так постоянная этот реальный фактор, который мы обычно не говорить о сложности времени, его действительно фактически сделать разницу здесь. Так поиск по-прежнему линейный поиск, если вы используете цепочки, но длина списка Вы ищете через очень, очень короткий в сравнении. Опять же, если это ваши сортировка Цель здесь, хэш таблицы вероятно, не правильный путь. Просто используйте массив, если сортировка это действительно важно для вас. 

И они могут запустить гамму размеров. Трудно сказать, является ли хеш-таблица является маленький или большой, потому что это действительно зависит от насколько велик ваш хэш таблицы. Если вы только собираетесь быть хранения пять элементов в вашем хэш-таблицы, и у вас есть хэш-таблицу 10000 элементов в нем, вы, вероятно, тратить много места. Контраст быть Вы также можете есть очень компактные хэш-таблицы, но меньше ваша хэш-таблица получает, чем больше каждый из этих связанных списков получает. И поэтому на самом деле нет способа определить точно размер хеш-таблицы, но это, вероятно, безопасно сказать это вообще будет больше, чем связанный Список хранения те же данные, но меньше, чем синтаксического дерева. 

И пытается это четвертый из этих структур что мы говорим о. Вставка в синтаксического дерева является сложным. Там очень много динамических выделение памяти, особенно в начале, а вы начинаете строить. Но это постоянная времени. Это только человеческий фактор вот что делает его сложным. Имея столкнуться нулевой указатель, таНос пространство, туда, возможно, таНос пространство оттуда снова. Своего рода запугивания фактор указатели в динамическом распределении памяти является препятствием, чтобы очистить. Но как только вы очистили его, вставка на самом деле происходит довольно просто, и это, конечно, постоянная времени. 

Удаление легко. Все, что вам нужно сделать, это перейти вниз пара указателей и бесплатным узла, так что это довольно хорошо. Поиск также довольно быстро. Это только на основе длина ваших данных. Так что, если все ваши данные в пять символов строки, Например, вы храните пять символьные строки в Вашей синтаксического дерева, это займет всего пять шагов к найти то, что вы ищете. Пять просто постоянным фактором, так снова, вставка, удаление, поиск и здесь все время постоянной, эффективно. 

Другое дело, что ваш Trie является на самом деле вид уже отсортированы, верно? В силу того, как мы вставка элементов, перейдя по буквам из Ключ, или цифра за цифрой ключа, обычно, на ваш Trie заканчивается время вид сортируются, как вы строите его. Это на самом деле не делает смысл подумать о сортировке таким же образом, мы думаем о это с массивами, или связанные списки, или хэш-таблицы. Но в каком-то смысле, ваш Trie сортируется, как вы идете. 

Недостатком, конечно, является то, что Trie быстро становится огромным. Из каждой точки перехода, вы можете have-- если ваш ключ состоит из цифр, у вас есть 10 других места, которые вы можете пойти, что означает, что каждый узел содержит информацию о данных, которые вы хотите сохранить в этом узле, плюс 10 указателей. Что, по CS50 IDE, 80 байт. Так что, по крайней мере 80 байта для каждый узел, который вы создаете, и это даже не считая данных. И если ваши узлы письма вместо цифр, теперь у вас есть 26 указателей от каждого места. И 26 раз 8, вероятно, 200 байт, или что-то подобное. А у вас есть капитал и lowercase-- вы можете увидеть, где я собираюсь с этим, верно? Ваши узлы могут получить действительно большой, и поэтому Trie Сам, в целом, может получить действительно большой, слишком. Так что, если пространство на высоком премия по вашей системе, Trie не может быть правильным способом идти, даже если другие его преимущества вступают в игру. Я Дуг Ллойд. Это CS50.