Способы структур описание данных

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

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

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

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

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

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

Переведено в Alconost

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

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

Зачем нужны структуры данных?

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

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

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

Наиболее распространенные структуры данных

Сначала давайте перечислим наиболее распространенные структуры данных, а затем разберем каждую по очереди:

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

Массивы

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

Здесь показан простой массив размером 4, содержащий элементы (1, 2, 3 и 4).

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

Существуют массивы двух типов:

• Одномерные (такие, как показанный выше)
• Многомерные (массивы, в которые вложены другие массивы)

Простейшие операции с массивами

Вопросы по массивам, часто задаваемые на собеседованиях

Стеки

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

Стек можно сравнить с высокой стопкой книг. Если вам нужна какая-то книга, лежащая около центра стопки, вам сначала придется снять все книги, лежащие выше. Именно так работает принцип LIFO (Последним пришел — первым вышел).

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

Простейшие операции со стеком:

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

Вопросы о стеке, часто задаваемые на собеседованиях

Очереди

Очередь, как и стек — это линейная структура данных, элементы в которой хранятся в последовательном порядке. Единственное существенное отличие между стеком и очередью заключается в том, что в очереди вместо LIFO действует принцип FIFO (Первым пришел — первым вышел).

Идеальный реалистичный пример очереди — это и есть очередь покупателей в билетную кассу. Новый покупатель становится в самый хвост очереди, а не в начало. Тот же, кто стоит в очереди первым, первым приобретет билет и первым ее покинет.

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

Простейшие операции с очередью

Вопросы об очередях, часто задаваемые на собеседованиях

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

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

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

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

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

Существуют такие типы связных списков:

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

Простейшие операции со связными списками:

Вопросы о связных списках, часто задаваемые на собеседованиях:

Графы

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

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

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

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

Распространенные алгоритмы обхода графа:

Вопросы о графах, часто задаваемые на собеседованиях:

Деревья

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

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

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

Существуют деревья следующих типов:

• N-арное дерево
• Сбалансированное дерево
• Двоичное дерево
• Двоичное дерево поиска
• АВЛ-дерево
• Красно-черное дерево
• 2—3 дерево

Из вышеперечисленных деревьев чаще всего используются двоичное дерево и двоичное дерево поиска.

Вопросы о деревьях, часто задаваемые на собеседованиях:

Найдите высоту двоичного дерева
Найдите k-ное максимальное значение в двоичном дереве поиска
Найдите узлы, расположенные на расстоянии “k” от корня
Найдите предков заданного узла в двоичном дереве

Бор, также именуемый «префиксное дерево» — это древовидная структура данных, которая особенно эффективна при решении задач на строки. Она обеспечивает быстрое извлечение данных и чаще всего применяется для поиска слов в словаре, автозавершений в поисковике и даже для IP-маршрутизации.

Вот как три слова «top» (верх), «thus» (следовательно), and «their» (их) хранятся в бору:

Слова располагаются в направлении сверху вниз, и зеленые узлы «p», «s» и «r» завершают, соответственно, слова «top», «thus» и «their».

Вопросы о борах, часто задаваемые на собеседованиях:

Хеш-таблица

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

Как правило, хеш-таблицы реализуются при помощи массивов.

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

• Хеш-функция
• Размер хеш-таблицы
• Метод обработки коллизий

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

Вопросы о хешировании, часто задаваемые на собеседованиях:

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

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

Удачи и интересного обучения! 🙂

Перевод статьи выполнен в Alconost.

Alconost занимается локализацией игр, приложений и сайтов на 68 языков. Переводчики-носители языка, лингвистическое тестирование, облачная платформа с API, непрерывная локализация, менеджеры проектов 24/7, любые форматы строковых ресурсов.

Мы также делаем рекламные и обучающие видеоролики — для сайтов, продающие, имиджевые, рекламные, обучающие, тизеры, эксплейнеры, трейлеры для Google Play и App Store.

Источник

Способы структур описание данных

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 байт.

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

char 3.1 — Размер целых чисел в Си

Тип	Размер,байт	Миним.значение	Максим.значение
unsigned char	1	0	255
signed char ( char )	1	-128	127
unsigned short	2	0	65535
signed short ( short )	2	-32768	32767
unsigned int ( unsigned )	4	0	4294967296
signed int ( int )	4	-2147483648	2147483647
unsigned long	4	0	4294967296
signed long ( long )	4	-2147483648	2147483647
unsigned long long	8	0	18446744073709551615
signed long long ( long long )	8	-9223372036854775808	9223372036854775807

Числа с плавающей точкой:

• float — 4 байта,
• long float — 8 байт
• double — 8 байт
• long double — 8 байт.

Таблица 3.2 — Размер типов с плавающей точкой

Тип	Размер,байт	Количество значащих знаков мантиссы	Миним. значение	Максим. значение
float	4	6-7	1.175494351 E – 38	3.402823466 E + 38
double	8	15-16	2.2250738585072014 E – 308	1.7976931348623158 E + 308
long double	10	—	3.4 E — 4932	3.4 E +4932

В стандарте только указано, что float Производные (пользовательские) типы данных и типы класса являются более сложными объектами, которые составляются непосредственно пользователями, а основой или их начинкой являются непосредственно базовые данные. Их представление рассмотрим в следующем разделе.

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

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

Рисунок 3.2 – Классификация структур данных

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

Таблица реляционной базы данных

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

3.2 Способы представления структур данных

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

3.2.1 Массивы

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

Рисунок 3.3 – Структура данных «Линейный массив»

Адрес(элемент(index)) = размер_ячейки * index.

Доступ к какому-либо из элементов массива осуществляется по имени и номеру (индексу) этого элемента. Количество индексов определяет размерность массива.

Т.е. массив — это контейнер, в котором можно располагать, извлекать данные (объекты). Давайте рассмотри, как обозначаются одномерные массивы:

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

Многомерные массивы так же часто используются, как и одномерные. Вообще, многомерные массивы — это массивы массивов. Т.е. каждый индексный номер содержит массив. Например, int i[2][4] = <<1,2,3,4>, <5,6,7,8>>, где мы создаем двумерный массив размером 2х4, т.е. 2 строчки по 4 элемента каждая.

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

3.2.2 Списки

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

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

Список.

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

Рисунок 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. Пример реализации структуры данных «стек».

Источник