Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Понятия и виды структур данных и алгоритмов

Лекция



Привет, Вы узнаете о том , что такое структура данных и алгоритм, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое структура данных и алгоритм , настоятельно рекомендую прочитать все из категории Алгоритмизация и программирование. Структурное программирование. Язык C.

Что такое структуры данных и алгоритмы?

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

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

Не пугайтесь математики

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

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

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

Понятия и виды структур данных и алгоритмов

Понятия и виды структур данных и алгоритмов

Эта лекция дает общую картину структур данных и алгоритмов

Понятия и виды структур данных и алгоритмов


1 Что такое структуры данных?

Доступно множество определений.

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

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

Линейные конструкции . К этой категории относятся массив, список, очередь и стек. Каждый из них представляет собой коллекцию, в которой свои записи хранятся в линейной последовательности, и в которую записи могут быть добавлены или удалены по желанию. Они различаются ограничениями, которые они накладывают на то, как эти записи могут быть добавлены, удалены или доступны. Общие ограничения включают FIFO и LIFO.

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

Что такое абстрактные типы данных (ADT)?

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

Когда мы говорим «тип данных», мы часто ссылаемся на примитивные типы данных, встроенные в язык, такие как целые, вещественные, символьные и логические. Целое число, скорее всего, реализовано или представлено в компьютере четырьмя байтами. Однако, когда мы используем целые числа, мы совершенно не беспокоимся о его внутреннем представлении или о том, как эти операции реализуются компилятором в машинном коде. Кроме того, мы знаем, что даже когда мы запускаем нашу программу на другом компьютере, поведение целого числа не меняется, даже если его внутреннее представление может измениться. Что мы знаем, так это то, что мы можем использовать примитивные типы данных через их рабочий интерфейс - '+', '-', '*' и '/' для целых чисел. Примитивные типы данных были абстрактными записями.

Стек или очередь - это пример ADT. Как стеки, так и очереди могут быть реализованы с использованием массива. Также возможно реализовать стеки и очереди, используя связанные списки. Это демонстрирует «абстрактный» характер стеков и очередей: как их можно рассматривать отдельно от их реализации.

Применяя идею абстракции к структурам данных, у нас есть ADT для структур данных. С одной стороны, ADT четко разделяет интерфейс и реализацию , пользователь видит только интерфейс и, следовательно, не должен вмешиваться в реализацию. С другой стороны, если реализация ADT изменится, код, который использует ADT, не сломается, поскольку интерфейс останется прежним. Таким образом, абстракция делает код более надежным и простым в обслуживании . Более того, как только ADT построен, его можно использовать несколько раз в различных контекстах. Например, ADT списка может использоваться непосредственно в коде приложения или может использоваться для построения другого ADT, такого как стек.

Как мне выбрать правильные структуры данных?

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

2 Что такое алгоритм?

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

Классификация дизайнерских приемов :

  • Рекурсивный
  • Грубая сила
  • Разделяй и властвуй
  • В глубину
  • В ширину
  • Возврат
  • Жадный - локальный оптимальный
  • Ветвь и граница

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

Эффективность программы: время vs. пространство. Интересно знать, сколько определенного ресурса (например, времени или хранилища) требуется для данного алгоритма. Были разработаны методы для анализа алгоритмов , чтобы получить такие количественные ответы, такие как большая нотация O . Например, время, необходимое для обхода массива из n слотов, пропорционально n , и мы говорим, что время имеет порядок O ( n ). Однако для доступа к i- му элементу в массиве требуется только постоянное время, которое не зависит от размера массива, поэтому имеет порядок O (1).

Определения обозначения времени работы :

  • Общие функции, используемые при анализе:
    • Постоянная функция f ( n ) = C - Постоянный алгоритм не зависит от размера ввода.
    • Функция логарифмирования f ( n ) = log n - функция логарифмирования становится немного медленнее с ростом n.
    • Линейная функция f ( n ) = n - всякий раз, когда n удваивается, время работы увеличивается.
    • Функция N-Log-N f ( n ) = n log n - она ​​растет немного быстрее, чем линейная функция.
    • Квадратичная функция f ( n ) = n 2 - Каждый раз, когда n удваивается, время работы увеличивается в четыре раза.
    • Кубическая функция и другие многочлены
    • Экспоненциальная функция f ( n ) = b n
    • Факториальная функция f ( n ) = n !

Классификация алгоритмов в зависимости от ассимтотической сложности

  • О(1) – постоянные (проверка числа на четность или нечетность);
  • О(n) – линейные (find, search и др);
  • О(logn)– логарифмические(Двоичная сортировка)
  • О(nlogn)-квазилинейные(сортировка Шелла, Быстрая сортировка)
  • O(n 2 )-квадратичные
  • О(2 n )-экспоненциальные

Классификация алгоритмов по структуре:

  • Линейный (следование)
  • Разветвленный (ветвление, выбор, альтернатива)
  • Циклический (повтор)
  • Вспомогательный
  • Комбинированный

Понятия и виды структур данных и алгоритмов

Рис. Об этом говорит сайт https://intellect.icu . . Классификация способов представления алгоритмов

3. Структуры данных

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

Массив: массив - это структура данных на основе индекса, что означает, что на каждый элемент ссылается индекс. Массив содержит элементы того же типа данных.

Понятия и виды структур данных и алгоритмов

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

Понятия и виды структур данных и алгоритмов

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

Понятия и виды структур данных и алгоритмов

Двоичное дерево (бинарное дерево): двоичное дерево имеет 1 или 2 узла. Он может иметь как минимум нулевые узлы, что происходит, когда узлы имеют значения NULL.

Понятия и виды структур данных и алгоритмов

Дерево двоичного поиска: двоичное дерево поиска (BST) - это двоичное дерево. Левое поддерево содержит узлы, ключи которых меньше значения ключа узла, а правое поддерево содержит узлы, ключи которых больше или равны значению ключа узла. Более того, оба поддерева также являются деревьями двоичного поиска. Дерево двоичного поиска может эффективно извлекать данные.

Понятия и виды структур данных и алгоритмов

Матрица: Матрица - это двумерный массив. Он использует две строки и столбцы индексов для хранения данных.

Понятия и виды структур данных и алгоритмов

Граф: граф содержит набор узлов и ребер. Узлы также называются вершинами. Ребра используются для соединения узлов. Узлы используются для хранения и извлечения данных.

Понятия и виды структур данных и алгоритмов

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

Понятия и виды структур данных и алгоритмов

Очередь: очередь - это структура данных FIFO. В этой структуре новые элементы вставляются с одного конца, а существующие элементы удаляются с другого.

Понятия и виды структур данных и алгоритмов

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

Понятия и виды структур данных и алгоритмов

Min-Heap: Min-heap - это двоичное дерево. Это полно. Данные, хранящиеся в каждом узле, меньше, чем элементы данных, хранящиеся в его дочерних узлах.

Понятия и виды структур данных и алгоритмов

Trie: Trie - это дерево. В дереве каждый узел (кроме корневого) хранит один символ или цифру. Путем обхода дерева вниз от корневого узла к конкретному узлу n можно сформировать общий префикс символов или цифр, который также используется другими ветвями дерева.

Понятия и виды структур данных и алгоритмов

Суффиксное дерево: суффиксное дерево - это дерево, содержащее все суффиксы данного текста. Суффиксное дерево позволяет особенно быстро реализовать многие важные строковые операции.

Понятия и виды структур данных и алгоритмов

4. Коллекции Java

Структура коллекций Java - это набор типов коллекций, которые включены как часть ядра java. Он предоставляет API или методы, которые вы можете использовать напрямую для работы со структурами данных, такими как массивы, связанные списки, стеки, очереди, наборы и карты. Если вы освоите коллекцию java, это сэкономит вам массу времени и поможет решать сложные проблемы.

Понятия и виды структур данных и алгоритмов

ArrayList: класс ArrayList - это реализация интерфейса List с изменяемым размером массива. Он реализует все необязательные операции со списком и разрешает все элементы.

Понятия и виды структур данных и алгоритмов

Vector: Vector очень похож на ArrayList, но Vector синхронизирован и медленный. Это унаследованный класс, и теперь он совместим с коллекциями.
String: класс String используется для создания строк и управления ими.

Понятия и виды структур данных и алгоритмов

LinkedList: класс LinkedList - это реализация двусвязного списка интерфейса List и Deque. LinkedList хранит свои данные в виде списка элементов, и каждый элемент связан со своим предыдущим и следующим элементом.

Понятия и виды структур данных и алгоритмов

HashMap: HashMap - это класс коллекции, реализующий интерфейс карты. Он требует хэш-функции и использует методы hashCode () и equals (), чтобы помещать и извлекать элементы в коллекцию и из нее соответственно.

Понятия и виды структур данных и алгоритмов

Hashtable: класс Hashtable похож на HashMap. Он реализует словарь. Hashtable предоставляет перечисление своих ключей. Он не позволяет использовать null в качестве ключа или значения. Обратите внимание, что, поскольку HashMap был создан позже, это расширенная версия и улучшение Hashtable. Hashtable синхронизируется и работает медленнее. HashMap предпочтительнее Hashtable.
TreeMap: TreeMap реализует интерфейс SortedMap. Он сортируется в порядке возрастания ключей. Сложность операций - O (logn).

Понятия и виды структур данных и алгоритмов

LinkedHashMap: LinkedHashMap сохраняет порядок вставки. Сложность такая же, как у HashMap O (1).

Понятия и виды структур данных и алгоритмов

HashSet: класс HashSet реализует интерфейс Set. Повторяющиеся значения не допускаются. Его элементы не упорядочены. В HashSet разрешены элементы NULL.

Понятия и виды структур данных и алгоритмов

TreeSet: TreeSet реализован с использованием древовидной структуры. Элементы в TreeSet отсортированы. Сложность операций - O (logn).

Понятия и виды структур данных и алгоритмов

LinkedHashSet: LinkedHashSet поддерживает порядок вставки. Элементы сортируются в той же последовательности, в которой они были добавлены в набор. Сложность такая же, как у HashSet O (1).

Понятия и виды структур данных и алгоритмов

Stack: класс Stack расширяет класс Vector пятью операциями для поддержки LIFO (Last In First Out). Внутри стека есть указатель: TOP, который указывает на верхнюю часть элемента стека.

Понятия и виды структур данных и алгоритмов

PriorityQueue: Класс PriorityQueue - это реализация Queue, с каждым элементом которого связан приоритет. Элементы приоритетной очереди упорядочиваются в соответствии с их естественным порядком или компаратором, предоставляемым во время создания очереди.

Понятия и виды структур данных и алгоритмов

Разница между HashMap, LinkedHashMap и TreeMap

Понятия и виды структур данных и алгоритмов

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

HashMap

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

TreeMap

  • будет повторяться в соответствии с "natural ordering" ключей в соответствии с их compareTo() методом (или внешне поставляемым Comparator ). Кроме того, он реализует интерфейс SortedMap , который содержит методы, зависящие от этого порядка сортировки.
  • Заказанная и сортированная версия
  • на основе хэширования структур данных

LinkedHashMap

  • будет повторяться в том порядке, в котором записи были помещены в карту
  • Это упорядоченная версия реализации Карты
  • Основанный на связанном списке и структурах данных хэширования

HashTable

  • то же, что и карта hash
  • он не позволяет использовать null ключа и null значений

"Hashtable" - это общее название для карт на основе hash. В контексте Java API, Hashtable является устаревшим классом со времен Java 1.1 до того, как появилась платформа коллекций. Он больше не должен использоваться, потому что его API загроможден устаревшими методами, которые дублируют функциональность, а его методы синхронизированы (что может снизить производительность и вообще бесполезно). Используйте ConcurrentHashMap вместо Hashtable.

Понятия и виды структур данных и алгоритмов

Понятия и виды структур данных и алгоритмов

5. Алгоритмы

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

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

Понятия и виды структур данных и алгоритмов

Сортировка выбором: это наиболее интуитивно понятный, не обязательно эффективный. Найдите наименьший элемент с помощью линейной развертки и переместите его вперед (поменяв местами с передними элементами). Затем найдите второй самый маленький и переместите его, снова выполняя линейное сканирование. Продолжайте делать это, пока все элементы не будут на своих местах. Подходит для небольших файлов. O (n 2) среднее и худшее.

Понятия и виды структур данных и алгоритмов

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

Понятия и виды структур данных и алгоритмов

Поиск: поиск заключается в поиске контента на основе ключа. Есть линейный поиск и бинарный поиск .
Линейный поиск: линейный поиск - это метод поиска целевого значения в списке. Он последовательно проверяет каждый элемент списка на предмет целевого значения, пока не будет найдено совпадение или пока не будут найдены все элементы.

Понятия и виды структур данных и алгоритмов

Двоичный поиск: двоичный поиск - это эффективный алгоритм поиска элемента из упорядоченного списка элементов. Он работает путем многократного деления пополам той части списка, которая может содержать элемент; пока вы не сузите возможные местоположения до одного. Сложность снижается с O (n) до O (logn).

Понятия и виды структур данных и алгоритмов

Рекурсия: рекурсия - это метод компьютерного программирования, который функция или алгоритм вызывает сама себя. Он должен включать шаг с условием завершения. Когда условие выполнено, остальная часть каждого повторения обрабатывается от последнего вызванного до первого. Самая известная проблема, решаемая с помощью рекурсии, - это Факториальное число .
Факториал: Факториал числа n - это произведение всех положительных ненулевых чисел, меньших или равных n. Факториал числа n обозначается n !.

Понятия и виды структур данных и алгоритмов

Динамическое программирование: динамическое программирование - это метод решения сложной проблемы путем разбиения ее на набор более простых подзадач, решения каждой из этих подзадач только один раз и сохранения их решений. В следующий раз, когда возникает та же подзадача, выполняется поиск ранее вычисленного решения, тем самым экономя время вычислений за счет скромных затрат на пространство для хранения. Знаменитая проблема динамического программирования - числа Фибоначчи .
Числа Фибоначчи: это ряд чисел, в которых каждое число (число Фибоначчи) является суммой двух предыдущих чисел. Самый простой - это серии 1, 1, 2, 3, 5, 8 и т. Д.

Понятия и виды структур данных и алгоритмов

Разделяй и властвуй: алгоритм «разделяй и властвуй» работает путем рекурсивного разбиения проблемы на две или более подзадач одного и того же или родственного типа, пока они не станут достаточно простыми для непосредственного решения. Известные проблемы с использованием «разделяй и властвуй» - это сортировка слиянием и быстрая сортировка .
Сортировка слиянием: делит массив пополам, сортирует каждую из этих половин, а затем объединяет их вместе. К каждой из этих половин применяются одинаковые алгоритмы сортировки. В конце концов, он объединяет два одноэлементных массива. O (nlogn) средний и худший.

Понятия и виды структур данных и алгоритмов

Быстрая сортировка: выбирает случайный элемент и разбивает массив, все числа, меньшие, чем элемент разбиения, идут перед всеми элементами, которые больше его. Если мы несколько раз разбиваем массив вокруг элемента, массив в конечном итоге станет отсортированным. Но поскольку не гарантируется, что разделенный элемент является медианным, наша сортировка может быть очень медленной. O (nlogn) в среднем, O (n 2) в худшем.

Понятия и виды структур данных и алгоритмов

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

Понятия и виды структур данных и алгоритмов

Вау!! 😲 Ты еще не читал? Это зря!

Исследование, описанное в статье про структура данных и алгоритм, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое структура данных и алгоритм и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмизация и программирование. Структурное программирование. Язык C

создано: 2020-10-27
обновлено: 2021-12-13
132265



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Алгоритмизация и программирование. Структурное программирование. Язык C

Термины: Алгоритмизация и программирование. Структурное программирование. Язык C