Sckontakt.ru

Уроки онлайн
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Структуры данных в программировании

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

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

В 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-собеседование.

Структуры данных: общее понятие, реализация. Простейшие структуры данных: очередь, стек. Использование стека и обратная польская запись

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

«Алгоритмы + структуры данных = программы». Это — название книги Никлауса Вирта, знаменитого швейцарского специалиста по программированию, автора языков Паскаль , Модула-2, Оберон. С именем Вирта связано развитие структурного подхода к программированию. Н.Вирт известен также как блестящий педагог и автор классических учебников.

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

Общее понятие структуры данных

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

Структуры данных удобнее всего реализовывать в объектно-ориентированных языках. В них структуре данных соответствует класс , сами данные хранятся в переменных-членах класса (или доступ к данным осуществляется через переменные-члены), системе предписаний соответствует набор методов класса. Как правило, в объектно-ориентированных языках структуры данных реализуются в виде библиотеки стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL, или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java .

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

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

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

Структуры данных в программировании

1. Какие бывают данные и их структуры?

2. Как задаются структуры данных?

… Лучше, чтобы в 100 функциях

использовалась одна структура данных,

чем в 10 функциях — 10 структур

А. Дж. Перлис

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

Будем исходить из того представления, что структура данных – программная единица, позволяющая хранить и обрабатывать множество однотипных или логически связанных данных в вычислительной технике (https://ru.wikipedia.org/wiki/Структура_данных). Она формируется с помощью типов данных, ссылок и операций над ними в выбранном языке программирования.

3.1 Классификация структур данных

В языке Си различают следующие категории типов данных : базовые (или простые, основные, стандартные) типы данных и производные (или сложные, составные) типы данных. Основные типы данных представлены на рис. 3.1.

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

Рисунок 3.1 — Основные типы данных, применяемые в программировании

Указание типа данных четко определяет:

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

В си несколько основных базовых типов. Разделим их на две группы — целые и числа с плавающей точкой.

  • char — размер 1 байт. Всегда! Это нужно запомнить.
  • short — размер 2 байта
  • int — размер 4 байта
  • long — размер 4 байта
  • long long — размер 8 байт.

Здесь следует сделать замечание. Размер переменных в си не определён явно, как размер в байтах. В стандарте только указано, что


Список.


Двунаправленный список.

Рисунок 3.4 – Структуры данных «Однонаправленный и двунаправленный список»

Связанный список – это вариант обычного линейного списка, оптимизированный для операций добавления и удаления элементов. Оптимизация заключается в том, что элементы связанного списка не обязаны в памяти располагаться друг за другом. Порядок элементов определяется ссылкой на первый элемент (не обязан быть в самом начале выделенной для списка памяти) и последовательностью ссылок на остальные элементы списка.

Рисунок 3.5 – Структура данных «Связанный список»

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

struct spis *next; >; // Указатель на структуру

Здесь при описании указателя используем ещё не описанный объект struct spis *next , который будет служить ссылкой на последующий элемент списка. Самая последняя структура в списке никуда не указывает, т.е. поле next должно иметь значение NULL. Адрес начала (головы) списка хранится в переменной типа указатель *head. На текущую структуру будет указывать *p.

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

3.2.3 Стек

Стек – это динамическая линейная структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in first out, «последним пришёл — первым вышел»).

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

Пример задания стека :

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek). При проталкивании (push) указывается новый элемент, указывающий на элемент бывший до этого головой. Новый элемент теперь становится головным. При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент).

Читать еще:  Программирование на андроид для начинающих

Рисунок 3.6 – Структура данных «стек»

Рисунок 3.7 — Последовательное выполнение операций push 3, push 5, push 7, pop, pop, pop

3.2.4 Очередь

О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

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

Рисунок 3.8 – Структура данных «Очередь»

Очереди очень часто встречаются в реальной жизни, например, около банков или ресторанов быстрого обслуживания. Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от «store»— «сохранять», «retrieve» — «получать»). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение.

3.2.5 Дек

Дек – структура данных одновременно работает по двум способам организации данных: FIFO и LIFO. Поэтому ее допустимо отнести к отдельной программной единице, полученной в результате суммирования двух предыдущих видов структур данных.

Рисунок 3.9 – Структура данных «дек»

3.2.6 Хэш-таблица

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

Рисунок 3.10 – Структура данных «хэш – таблица»

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

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

Рисунок 3.11 — Телефонная книга на примере хэш-таблицы

3.2.7 Иерархические структуры данных

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

Деревья

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

Деревья – динамическая иерархическая структура данных, представленная единственным корневым узлом и его потомками. Максимальное количество потомков каждого узла и определяет размерность дерева. Отдельно выделяют двоичные или бинарные деревья, поскольку они используются в алгоритмах сортировки и поиска: каждый узел двоичного дерева поиска соответствует элементу из некоторого отсортированного набора, все его “левые” потомки – меньшим элементам, а все его “правые” потомки – большим элементам. Каждый узел в дереве однозначно идентифицируется последовательностью неповторяющихся узлов от корня и до него – путем. Длина пути и является уровнем узла в иерархии дерева. Для двоичных или бинарных деревьев выделяют следующие виды рекурсивного обхода всех его элементов (в фигурных скобках указан порядок посещения элементов каждого узла, начиная с корня): прямой или префиксный <узел, левое поддерево, правое поддерево>; обратный или постфиксный <левое поддерево, правое поддерево, узел>; симметричный или инфиксный
<левое поддерево, узел, правое поддерево>.

Пример представления дерева:

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


Рисунок 3.12 – Структура данных «дерево»

Иерархический список

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


Рисунок 3.13 – Структура данных «Иерархический список»

Примеры применения структур данных

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

Пример 3.2. Пример создания и просмотра односвязного списка (http://c.guti.ru/dstruktury.asp ).

Пример 3.3. Пример реализации структуры данных «стек».

Структуры данных в программировании

Небольшой дисклеймер. Эта статья рассчитана на повторение и/или изучение основных структур данных для собеседования на java developer позицию.
Ссылка на оригинал статьи от ex-Facebook и ex-Microsoft разработчика Fahim ul Haq

Никлаус Вирт, швейцарский ученый, в 1976 году написал книгу под названием «Алгоритмы + структуры данных = программы».

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

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

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

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

Структура данных, что это?

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

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

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

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

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

Обычно используемые структуры данных

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

  1. Массивы
  2. Стеки
  3. Очереди
  4. Связанные списки
  5. Деревья
  6. Графы/диаграммы
  7. Tries / попытки (это те же деревья, но в целях изучения лучше сделать на них отдельный акцент).
  8. Хэш таблицы
Читать еще:  Питон язык программирования с нуля

Массивы

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

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

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

  • Одномерные массивы (как показано выше)
  • Многомерные массивы (массивы массивов)

Основные операции с массивами

  • Insert-вставка элемента по заданному индексу
  • Get — возвращает элемент по указанному индексу
  • Delete-удаление элемента с заданным индексом
  • Size— получить общее количество элементов в массиве

Часто задаваемые вопросы на интервью по Массивам

  • Найти второй минимальный элемент массива
  • Первые неповторяющиеся целые числа в массиве
  • Объединить два отсортированных массива
  • Переставить положительные и отрицательные значения в массивах

Стеки/стопки

Мы все знакомы с известным вариантом отмены (Undo – ctrl+z прим. автора перевода) , который присутствует почти в каждом приложении. Когда-нибудь задумывались, как это работает? Идея: вы сохраняете предыдущие состояния вашей работы (которые ограничены определенным числом) в памяти в таком порядке, что последнее появляется первым. Это не может быть сделано только с помощью массивов. То есть это реализуется с помощью стека.

Реальным примером стопки (стека) может быть стопка книг, расположенных в вертикальном порядке. Чтобы получить книгу, которая находится где-то посередине, вам нужно будет удалить все книги, размещенные поверх нее. Вот как работает метод LIFO (Last In First Out).

Вот изображение стека, содержащего три элемента данных (1, 2 и 3), где 3 находится вверху и будет удален первым:

Основные операции стека:

  • Push-вставка элемента сверху
  • Pop — возвращает верхний элемент, после удаления из стека
  • isEmpty-возвращает true, если стек пуст
  • Top-возвращает верхний элемент без удаления из стека

Часто задаваемые вопросы интервью стека

  • Оценить постфиксного выражения с помощью стека
  • Сортировка значений в стеке
  • Проверка на скобки в выражении

Очередь

Подобно стеку, очередь-это еще одна линейная структура данных, которая хранит элемент последовательным образом. Единственное существенное различие между стеком и очередью заключается в том, что вместо использования метода LIFO очередь реализует метод FIFO, который является коротким для First in First Out.

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

Вот изображение из очереди с четырьмя элементами данных (1, 2, 3 и 4), где 1 находится на самом верху и будет удален первый:

  • Enqueue () – вставляет элемент в конец очереди
  • Dequeue () – удаляет элемент из начала очереди
  • isEmpty () – возвращает true, если очередь пуста
  • Top () – возвращает первый элемент очереди
  • Реализовать стек с помощью очереди
  • Обратного первые k элементов очереди
  • Генерировать двоичные числа от 1 до n, используя очередь

Связанные списки

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

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

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

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

Ниже перечислены типы связанных списков:

  • Однонаправленный Список (Однонаправленный)
  • Двунаправленный список (двунаправленный)

Основные операции связанного списка:

  • InsertAtEnd-вставляет данный элемент в конец связанного списка
  • InsertAtHead-вставка данного элемента в начало / начало связанного списка
  • Delete-удаление данного элемента из связанного списка
  • DeleteAtHead-удаление первого элемента связанного списка
  • Search-возвращает данный элемент из связанного списка
  • isEmpty-возвращает true, если связанный список пусто

Часто задаваемые вопросы интервью по связанному списку

  • Реверс связанного списка
  • Обнаружение цикла в связанном списке
  • Возвращает N-й узел из конца в связанном списке
  • Удаление дубликатов из связанного списка

Graphs

Граф-это набор узлов, которые соединены друг с другом в виде сети. Узлы также называются вершинами. Пара (x, y) называется ребром, что указывает на то, что вершина x связана с вершиной y. Ребро может содержать вес / стоимость, показывая, сколько затрат требуется для прохождения от вершины x до y.

  • неориентированный граф
  • ориентированный граф

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

  • Массив смежности
  • Список Смежности

Общие алгоритмы обхода графов:

  • Поиск По Ширине
  • Поиск по глубине

Часто задаваемые вопросы интервью Graph

  • Реализовать поиск по ширине и глубине
  • Проверьте, является ли график деревом или нет
  • Количество ребер в графе
  • Найти кратчайший путь между двумя вершинами

Деревья

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

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

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

Ниже перечислены типы деревьев:

  • N-ary дерево
  • сбалансированное дерево
  • бинарное дерево
  • Двоичное Дерево Поиска
  • Дерево AVL
  • Красное Черное Дерево
  • 2-3 дерево

Часто задаваемые вопросы интервью дерево

  • Найти высоту двоичного дерева
  • K-е максимальное значение в двоичном дереве поиска
  • Идентифицировать узлы на расстоянии ” k” от корня
  • Поискать предков данного узла в двоичном дереве

Попытка или Префиксные деревья

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

Вот иллюстрация того, как три слова “top”, “thus” и “their” хранятся в Trie:

Слова хранятся сверху вниз, где зеленые цветные узлы “p”, “s” и “r” указывают конец “top”, “thus” и “their” соответственно.

Часто задаваемые вопросы интервью:

  • Количество общее количество слов в Trie
  • Напечатать все слова, хранящиеся в боре
  • Элементов сортировка массива с помощью дерева
  • Форма слова из словаря с помощью Trie
  • Создание словаря T9

Хэш Таблицы

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

Хэш-таблицы обычно реализуются с использованием массивов.

Производительность структуры данных хэширования зависит от этих трех факторов:

  • функция хеширования
  • Размер хэш-таблицы
  • Способ Управления Столкновением

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

Часто задаваемые вопросы интервью хэширования

  • Найти симметричные пары в массиве
  • Проследить полный путь путешествия
  • Найти, является ли массив подмножеством другого массива
  • Проверьте, являются ли заданные массивы непересекающимися

Выше изложены 8 структур данных, которые помогут вам в прохождении собеседования 😉

Ссылка на основную публикацию
Adblock
detector