Каковы наиболее полезные структуры данных, чтобы знать наизнанку?

Ответ 1

Одна из структур данных, которые я использую наиболее (вне векторов, конечно), является Hashtable. Его единственный выбор, если вам нужно искать большое количество данных в O (1) раз, это означает, что время поиска не растет по мере увеличения размера коллекции.

Ловушка заключается в том, что время вставки и удаления больше, чем на других строках данных, и вам нужно иметь какой-то ключ для поиска коллекции. Каждый элемент должен иметь ключ. Алгоритм берет ключ каждого элемента и вычисляет хэш-код, который указывает слот в хеш-таблице, в которой нужно искать. Затем, в зависимости от реализации, он либо следует за списком предметов, которые упали на это ведро, чтобы найти ваш предмет или он ищет соседние ведра. Размер hastable является определяющим для эффективности хэша, который сильно зависит от количества столкновений хэш-кодов между ключами.

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

С# имеет большую реализацию с Dictionary<keytype, valuetype> и даже имеет HybridDictionary, который решает внутренне, когда использовать хеш-таблицу или вектор. Любая хорошая книга программирования описывает это, но вы будете хорошо обслуживаться википедией: http://en.wikipedia.org/wiki/Hashtable

Ответ 2

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

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

список ссылок - очень полезно для поддержания списка данных, которые удаляются и вставляются часто, но очень медленны для повторения и поиска. например, свободные/использованные списки на страницах памяти

деревья - базовая структура, которая составляет основу более сложных структур. Существует много форм этой структуры. Обеспечивает время поиска в журналах, когда дерево хранится в сортировке. Преимущества для больших элементов данных, таких как словари. Бинарные /AVL и красно-черные деревья являются наиболее распространенными.

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

Эти структуры данных и их реализация доступны в библиотеке STL в С++. Другие языки также имеют свои собственные реализации. Когда вы узнаете эти основные структуры данных и несколько их вариантов (очередь, стек, приоритетные очереди) и что-то о алгоритмах поиска, я бы сказал, что основы будут хорошо освещены.

Ответ 3

Я довольно часто использую ассоциативный массив, в основном массивы со строкой в ​​качестве индекса.

Ответ 4

Связанные списки/дважды связанные списки/другие варианты

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

Преимущества связанных списков в том, что они очень дешевы для добавления/удаления узлов. В отличие от массивов или структур данных, которые используют массив в ядре, они не требуют перераспределения большего объема памяти при расширении.

Недостатки в том, что они вообще не работают хорошо для поиска. Что бы искать O (1) в массиве O (n) для связанного списка.

Как и все структуры, связанные списки идеальны только при определенных условиях. Но используемые в нужное время, они очень мощные.

Ответ 5

Мне нравятся бинарные деревья. Особенно вариант Splay-Tree. Это несколько похоже на самобалансирующееся двоичное дерево, но также адаптируется к шаблону использования приложения. Вы почти никогда не сталкиваетесь с худшим поведением O (n).

Хорошим бонусом является то, что они также легче писать и нуждаются в меньшем количестве кода, чем другие самобалансирующиеся двоичные деревья. Это одна из моих любимых структур данных, потому что она на практике настолько невероятно хороша на практике.

http://en.wikipedia.org/wiki/Splay_tree

Ответ 6

Я очень часто использую массивы в сочетании с структурой управления "foreach", чтобы перебирать элементы. Раньше я использовал массивы с числовым индексом и "for (i = 1; я < n; я ++)". Я обнаружил, что переключение через массивы с помощью "foreach" вместо явного числового индекса обеспечивает более общее и читаемое решение.

Ответ 7

Преимущества связанных списков в том, что они очень дешевы для добавления/удаления узлов. В отличие от массивов [...] они не требуют перераспределения памяти при расширении.

Если у вас есть массив, и вы удваиваете размер распределения каждый раз, когда вы его заполняете, вы будете амортизированы O (1). Кроме того, циклическое перемещение по всем элементам массива, скорее всего, будет более быстрым (во время стены), чем переключение по связанному списку из-за эффектов кеширования (если вы не выделите ссылки в больших кусках и не будете слишком много обходите с ними).

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

Ответ 8

Графы представляют собой очень мощную пропущенную структуру данных.

Много проблем можно решить, построив график, моделирующий вашу проблему, а затем используя хорошо известный алгоритм на графике. Некоторые примеры обработки естественного языка (соединительные узлы с краем веса могут представлять, насколько вероятно одно слово, чтобы следовать другому) видеоигр (использовать графики для определения кратчайших путей для символов ИИ) и топологии сети.

Я узнал о графиках из "Руководство по разработке алгоритмов" , которое было рекомендовано Стивом Егге в сообщение в блоге.

Ответ 9

Этот пост слишком расплывчатый. Существует множество структур данных: массивы, словари и т.д. Каждая структура данных может использоваться для решения различных задач.

Было бы гораздо более продуктивно задавать DS для конкретной проблемы.

Ответ 10

Это немного похоже на вопрос, какие инструменты в наборе инструментов плотника лучше всего научиться использовать. Каждый из них хорош для определенного типа работы, и вам необходимо изучить основные (карты, списки, сумки, наборы и т.д.) Одинаково.

Ответ 11

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

Ответ 12

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

Ответ 13

Я не думаю, что здесь есть общий ответ. Он должен быть ограничен некоторым вариантом использования. Например, в моей более чем 10-летней карьере программиста/менеджера я никогда не использовал бинарные деревья. Я сомневаюсь, что это означает, что бинарные деревья не полезны, но в ядре и в встроенном мире связанный список, вероятно, подходит лучше.
Фактически, когда я думаю об исключении нескольких исключений, я использовал только простые связанные списки.
И тогда даже во встроенных он, вероятно, не единственная используемая структура. Я живу в мире аппаратных протоколов низкого уровня, вероятно, "вверх по холму" больше используемых структур данных...

Ответ 14

Для базовой оценки вы должны знать несколько абстрактных типов данных (набор, словарь, упорядоченный список, очередь, стек и т.д.) и несколько способов реализации каждого из них с их относительными компромиссами.

Это, вероятно, потребует от вас понимания массивов, связанных списков (одиночных и двойных связей), хеш-таблиц, двоичных деревьев поиска (с некоторым пониманием простых эвристик балансировки) и двоичных куч. Знайте их наизнанку, и вы пройдете долгий путь к пониманию более сложных и интересных структур данных. Плюс, если вы внедрили все из них, у вас будет готовая библиотека, которую вы понимаете для проектов программирования (хотя, очевидно, для более продуктивного кода больше подходят более жесткие библиотеки, такие как Boost или что-то еще.)

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

Ответ 15

Quicksort

Mergesort

Bubblesort

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