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

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

В 1976 году швейцарец Никлаус Вирт опубликовал книгу «Алгоритмы и структуры данных». Несмотря на то, что после публикации этой книги уже прошло более 40 лет, работа Вирта «Алгоритмы и структуры данных» до сих чрезвычайно актуальна. Это обусловлено тем, что любой разработчик ПО должен прекрасно теоретические основы структур данных. Косвенно это подтверждается тем, что практически на любом ИТ-собеседовании возникает вопрос на данную тематику.

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

Структура базы данных представляет собой контейнер для хранения информация в заданной форме. Такая «компоновка» позволяет этой информации быть эффективной при выполнении одних операций и абсолютно бесполезной для решения других заданий. Главной задачей разработчика считается выбор наилучшего варианта структуры данных для решения определенной задачи.

Назначение структур данных

В IT-разработке именно данные считаются важнейшей сущностью. Для хранения этих данных в максимально организованном виде принято использовать именно структуры. Формат хранения зависит от задач программиста и типа данных. Это может быть заработная плата сотрудников, телефонный справочник, список покупок и т.д. Перечисленные данные могут размещаться в одной из 8 нижеописанных структур.

Самые востребованные структуры данных

Перед тем, как перейти к изучению всех известных структур хранения данных, вспомним их полный перечень:

  • стек;
  • массив;
  • очередь;
  • связный список;
  • дерево;
  • граф;
  • префиксное дерево;
  • хеш-таблица.

Массивы

Массивы считаются самой простой и востребованной структурой. Ниже приведен пример одномерного массива, состоящего из четырех элементов (1, 2, 3, 4).

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

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

Выше указан одномерный массив, но также существует его многомерный аналог. Простыми словами его можно назвать массивы массивов.

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

  • вставки;
  • извлечения нужного элемента по индексу;
  • удаления;
  • определения количества элементов в массиве.

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

  • Как найти минимальный элемент?
  • Как объединить 2 отсортированных массива?
  • Как поменять местами положительные и отрицательные значения?

Стеки

В любой современной программе есть опция «Отменить». Она считается одной из самых востребованных среди пользователей. Но далеко не все пользователи понимают, как работает эта опция.

Принцип работы «Отменить» заключается в том, что программа поочередно сохраняет предыдущие состояния таким образом, чтобы последнее сохраненное появлялось первым. Массивы не наделены таким функционалом, а потому для реализации работы этой опции принято использовать структуру данных стек.

Для понимания работы стека стоит привести самый тривиальный пример. Предположим, на столе одна на одной лежит куча тетрадок. Чтобы взять тетрадку из середины, необходимо удалить тетрадки, которые лежат сверху. Таким образом работаем принцип «последним пришел – первым ушел. В среде разработчиков этот принцип называется LIFO (Last In First Out).

Ниже приведен пример стека.

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

Элемент со значением «3» находится в самом верху. Следовательно, он будет удален первым.

Если говорить об операциях со стеками, то прежде всего нужно отметить:

  • вставку элемента в топ;
  • извлечение и последующее удаление верхнего элемента;
  • проверку на пустоту стека;
  • извлечение первого элемента.

На ИТ-собеседованиях программисту стоит быть готовым к таким вопросам:

  • Как отсортировать стек?
  • Как проверить соответствие скобок в выражении?

Очереди

Очередь – линейная структура данных, хранящая элементы в определенной последовательности. В очереди используется принцип «первым пришел – первым ушел» (FIFO).

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

Ниже приведен пример очереди, состоящей из 4 элементов.

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

В этом примере элемент со значением «1» находится в начале очереди. Следовательно, именно этот элемент первым выйдет из очереди.

К основным действиям с queue стоит отнести:

  • вставку в конец;
  • удаление первого элемента;
  • проверку на пустоту очереди;
  • извлечение первого элемента.

На собеседовании разработчика могут попросить:

  • создать стек посредством очереди;
  • сгенерировать двоичные числа посредством очереди.

Связный список

Создание структуры базы данных также предусматривает использование связных списков. Эта структура очень схожа с массивом. Но все-таки она отличается:

  • организацией;
  • принципом распределения памяти;
  • принцип выполнения операций Insert и Delete.

Связный список представляет собой сеть узлов, содержащих данные и указатель на следующей узел. В связном списке есть указатель на первый элемент (head). Если список будет пуст, head получит значение null.

Главной задачей связных списков является систем хранения файлов. Ниже приведен пример этой структуры:

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

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

  • вставка в начало или конец;
  • удаление первого или выбранного элемента;
  • поиск определенного элемента;
  • проверка на пустоту списка.

Во время собеседования разработчика могут попросить выполнить такие задания:

  • удалить дубликаты
  • развернуть список
  • получить заданный узел с конца списка.

Графы

Графы – это набор узлов, соединенных в виде сети. Пара узлов называется ребром, указывающим на то, что вершина одного узла соединена с вершиной другого.

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

Графы делятся на два типа – ориентированные и неориентированные. В программировании эта структура данных представлена в виде матрицы или списка смежности. Обход графов может осуществляться как в ширину, так и в длину.

Что касается наиболее популярных вопросов на собеседованиях, то разработчикам могут попросить выполнить такие задания:

  • реализация поиска;
  • определение количества ребер;
  • проверка на то является ли граф деревом.

Дерево

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

Именно эта структура используется для создания интеллектуальных машин.

Ниже приведен пример простого дерева:

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

Стоит добавить, что в программирование существует несколько видов деревьев:

  • N-арное;
  • сбалансированное;
  • бинарное;
  • AVL;
  • красно-черное;
  • 2-3;
  • бинарное дерево поиска.

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

  • определение высоты дерева;
  • поиск максимального значения;
  • поиск предков определенного узла.

Префиксное дерево

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

Ниже приведен пример префиксного дерева.

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

Объекты поиска указываются сверху вниз. Зеленым цветом выделены элементы, которые показывают конец каждого объекта поиска.

На ИТ-собеседованиях разработчику могут задать такие задания, связанные с префиксными деревьями:

  • создание словаря Т9;
  • определение общего количества элементов;
  • сортировка массива.

Хэш-таблица

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

Производительность хэш-таблиц зависит от следующих нюансов:

  • хеширования;
  • размера;
  • способа обработки коллекций.

Ниже приведен пример, в котором хэш отображается в массиве:

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

На ИТ-собеседовании разработчику могут быть заданы такие задания:

  • поиск симметричных пар;
  • определение того является ли определенный массив подмножеством другого;
  • проверка массивов на пересекаемость.

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



Теги:
0

Оставить своё мнение

Ваш e-mail не будет опубликован. Обязательные поля помечены *