Что состоят в том, чтобы очень хорошо знать самые полезные структуры данных? [закрытый]

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

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

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

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

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

Они структура данных и их implementaion avalable в библиотеке STL в C++. Другие языки также имеют свои собственные реализации. После того как Вы знаете эти структуры основных данных и несколько их изменений (очередь, стек, приоритетные очереди) & что-то об алгоритмах поиска, я сказал бы, что основы будут хорошо покрыты.

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

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

кроме того, массивы меньше: Вы сохраняете слово на элемент наверху плюс издержки на выделение (который является, вероятно, по крайней мере двумя словами: один для размера и один для next-in-free-list указателя).

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

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

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

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

я узнал о графиках от Руководство по проектированию Алгоритма , который рекомендовался Steve Yegge в сообщение в блоге .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сортировка с объединением Quicksort

Bubblesort

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

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