Как составить таблицу основных структур данных

Основные структуры данных. Матчасть. Азы

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

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

40+ лет спустя это уравнение все еще верно. И если вы самоучка и надолго в программировании пробегитесь по статье, можно по диагонали. Можно код кофе.

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

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

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

Какие бывают?

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

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

Основные структуры данных.

1. Массивы
2. Стеки
3. Очереди
4. Связанные списки
5. Графы
6. Деревья
7. Префиксные деревья
8. Хэш таблицы

Массивы

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

Изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).

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

Бывают

Одномерные, как показано выше.
Многомерные, массивы внутри массивов.

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

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

Вопросы

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

Стеки

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

Это не массивы. Это очередь. Придумал Алан Тюринг.

Примером стека может быть куча книг, расположенных в вертикальном порядке. Для того, чтобы получить книгу, которая где-то посередине, вам нужно будет удалить все книги, размещенные на ней. Так работает метод LIFO (Last In First Out). Функция «Отменить» в приложениях работает по LIFO.

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

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

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

Вопросы

• Реализовать очередь с помощью стека
• Сортировка значений в стеке
• Реализация двух стеков в массиве
• Реверс строки с помощью стека

Очереди

Подобно стекам, очередь — хранит элемент последовательным образом. Существенное отличие от стека – использование FIFO (First in First Out) вместо LIFO.

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

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

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

• Enqueue—) — вставляет элемент в конец очереди
• Dequeue () — удаляет элемент из начала очереди
• isEmpty () — возвращает значение true, если очередь пуста
• Top () — возвращает первый элемент очереди

Вопросы

• Реализовать cтек с помощью очереди
• Реверс первых N элементов очереди
• Генерация двоичных чисел от 1 до N с помощью очереди

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

Связанный список – массив где каждый элемент является отдельным объектом и состоит из двух элементов – данных и ссылки на следующий узел.

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

Бывают

Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.

1->2->3->4->NULL

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

NULL<-1<->2<->3->NULL

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

1->2->3->1

Самое частое, линейный однонаправленный список. Пример – файловая система.

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

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

Вопросы

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

Графы

Граф-это набор узлов (вершин), которые соединены друг с другом в виде сети ребрами (дугами).

Бывают

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

Встречаются в таких формах как

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

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

• Поиск в ширину – обход по уровням
• Поиск в глубину – обход по вершинам

Вопросы

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

Деревья

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

Древовидные структуры везде и всюду. Дерево скилов в играх знают все.

Простое дерево

Типы деревьев

• N дерево
• Сбалансированное дерево
• Бинарное дерево
• Дерево Бинарного Поиска
• AVL дерево
• 2-3-4 деревья

Бинарное дерево самое распространенное.

«Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. » — Procs

Три способа обхода дерева

• В прямом порядке (сверху вниз) — префиксная форма.
• В симметричном порядке (слева направо) — инфиксная форма.
• В обратном порядке (снизу вверх) — постфиксная форма.

Вопросы

• Найти высоту бинарного дерева
• Найти N наименьший элемент в двоичном дереве поиска
• Найти узлы на расстоянии N от корня
• Найти предков N узла в двоичном дереве

Trie ( префиксное деревое )

Разновидность дерева для строк, быстрый поиск. Словари. Т9.

Вот как такое дерево хранит слова «top», «thus» и «their».

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

Вопросы

• Подсчитать общее количество слов
• Вывести все слова
• Сортировка элементов массива с префиксного дерева
• Создание словаря T9

Хэш таблицы

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

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

По сути это массив, в котором ключ представлен в виде хеш-функции.

Эффективность хеширования зависит от

• Функции хеширования
• Размера хэш-таблицы
• Метода борьбы с коллизиями

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

Вопросы

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

Список ресурсов

• medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3
• www.geeksforgeeks.org/commonly-asked-data-structure-interview-questions-set-1
• prog-cpp.ru/data-list
• habr.com/post/267855
• habr.com/post/273687
• habr.com/post/150732
• ruhighload.com/%D0%A7%D1%82%D0%BE+%D1%82%D0%B0%D0%BA%D0%BE%D0%B5+%D1%85%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B+%D0%B8+%D0%BA%D0%B0%D0%BA+%D0%BE%D0%BD%D0%B8+%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%B0%D1%8E%D1%82
• ru.wikipedia.org

Вместо заключения

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

Спасибо, что прочли. Надеюсь не зря потратили время =)

PS: Прошу извинить, как оказалось, перевод статьи уже был тут и очень недавно, я проглядел.
Если интересно, вот она, спасибо Hokum, буду внимательнее.

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

• Связный список
• Стек
• Очередь
• Множество
• Map
• Хэш-таблица
• Двоичное дерево поиска
• Префиксное дерево
• Двоичная куча
• Граф
• Полезные ссылки

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

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

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

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

• Добавление элемента
• Удаление элемента
• Поиск элемента

Алгоритмическая сложность:

Алгоритм	Среднее значение	Худший случай
Поиск	O(n)	O(n)
Вставка	O(1)	O(1)
Удаление	O(1)	O(1)

Реализация на Python
Реализация на JavaScript

Стек

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

Стек организован по принципу LIFO (Last In First Out, «последним пришел — первым вышел») . Это значит, что последний элемент, который вы добавили в стек, первым выйдет из него.

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

• Добавление элемента (push)
• Удаление элемента (pop)
• Отображение содержимого стека (pip)

Алгоритмическая сложность:

Алгоритм	Среднее значение	Худший случай
Поиск	O(n)	O(n)
Вставка	O(1)	O(1)
Удаление	O(1)	O(1)

Реализация на Python
Реализация на JavaScript

Очередь

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

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

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

• Добавление элемента в конец (enqueue)
• Удаление первого элемента (dequeue)

Алгоритмическая сложность:

Алгоритм	Среднее значение	Худший случай
Поиск	O(n)	O(n)
Вставка	O(1)	O(1)
Удаление	O(1)	O(1)

Реализация на Python
Реализация на JavaScript

Множество

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

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

Реализация на Python
Реализация на JavaScript

Map

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

• Добавлять пары в коллекцию
• Удалять пары из коллекции
• Изменять существующей пары
• Искать значение, связанное с определенным ключом

Реализация на JavaScript

Хэш-таблица

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

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

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

Алгоритмическая сложность:

Алгоритм	Среднее значение	Худший случай
Поиск	O(1)	O(n)
Вставка	O(1)	O(n)
Удаление	O(1)	O(n)

Реализация на Python
Реализация на JavaScript

Двоичное дерево поиска

Дерево — структура данных, состоящая из узлов. Ей присущи следующие свойства:

• Каждое дерево имеет корневой узел (вверху)
• Корневой узел имеет 0 или более дочерних узлов
• Каждый дочерний узел имеет 0 или более дочерних узлов, и т.д.

У двоичного дерева поиска есть 2 дополнительных свойства:

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

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

Алгоритмическая сложность:

Алгоритм	Среднее значение	Худший случай
Поиск	O(log n)	O(n)
Вставка	O(log n)	O(n)
Удаление	O(log n)	O(n)

Реализация на Python
Реализация на JavaScript

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

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

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

Реализация на Python
Реализация на JavaScript

Двоичная куча

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

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

Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне.

Алгоритмическая сложность:

Алгоритм	Среднее значение	Худший случай
Поиск	O(n)	O(n)
Вставка	O(1)	O(log n)
Удаление	O(log n)	O(log n)

Реализация на Python
Реализация на JavaScript

Граф

Графы — совокупности узлов (вершин) и связей между ними (ребер). Также их называют сетями. По такому принципу устроены социальные сети: узлы — это люди, а ребра — их отношения.

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

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

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

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

Существуют специальные алгоритмы для просмотра ребер и вершин в графах — так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search) и поиск в глубину (depth-first search). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа.

Реализация матрицы смежности на Python
Реализация на JavaScript

Полезные ссылки

• Оригинал статьи
• Примеры реализации на Python

Основные структуры данных

1 Линейные структуры данных.

2 Табличные структуры данных.

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

4 Достоинства и недостатки различных
структур данных.

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

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

1 Линейные структуры данных

Примером линейной структуры данных
является список студентов, обучающихся
в группе

(журнал).

№ п/п Ф И О.

1. Беляков И.П

2. Иванов Л.В

3. Смирнова Г.В.

21. Яковлев С.П.

Линейные структуры данных
( или
списки) – это упорядоченные структуры,
в которых адрес элемента однозначно
определяется его номером.

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

Например,

Беляков И.П. * Иванов Л. В. * Смирнова
Г.В. * … * Яковлев С.П.

Если все элементы списка имеют равную
длину, то такие упрощенные списки
называют векторами данных. Работать
с ними более удобно.

2 Табличные структуры данных

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

Пример:

товар	цена	количество	сумма
телевизор	8000	2	16000
холодильник	14000	1	14000
электропечь	6000	4	24000

Элементы данных, принадлежащих табличной
структуре, также можно разместить
линейно с

использованием специальных разделителей
различных типов. Например:

товар * цена* количество* сумма #
телевизор * 8000 *2 * 16000 #холодильник
*14000 *14000 #электропечъ * 6000 *4* 24000

Если все элементы таблицы имеют равную
длину, то такие таблицы называются
матрицами.

Итак, табличные структуры данных —
это упорядоченные структуры, в
которых адрес элемента определяется
номером строки и номером столбца,
на пересечении которых находится
ячейка, содержащая искомый элемент

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

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

Номер курса: 1

Номер специальности: 061000

Номер группы: М-72

Номер студента в группе: 10

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

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

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

Например, маршрут для
установки ориентации печатного листа
в текстовом редакторе WORD
выглядит следующим образом Файл
—> параметры
страницы —>
Размер бумаги —>Ориентация.

4. Достоинства и недостатки различных
структур данных

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

Основным методом упорядочивания
является сортировка по какому-либо
признаку.

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

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

Иерархические структуры данных по фирме
сложнее, чем линейные и табличные, но
они не создают проблем с обновлением
данных. Недостатком иерархических
структур является относительная
трудоемкость записи адреса элемента
данных и сложность упорядочивания.
Методы упорядочивания в таких структурах
основываются на предварительной
индексации, которая заключается в
том , что каждому элементу данных
присваивается свой уникальный индекс
(номер),который можно использовать при
поиске, сортировке и т.п. После такой
индексации данные легко разыскиваются
по двоичному коду, связанного с ними
индекса. Одним из примеров индексации
является алфавитный указатель в конце
книги. Если данные хранятся в организованной
структуре, то каждый элемент данных
приобретает свой параметр, который
называется егоадресом. Работать с
упорядоченными данными удобнее, но за
это надо платить их размножением,
поскольку адреса элементов — это тоже
данные, которые также надо хранить и
обрабатывать. Главное, чтобы размер
адресных данных не становился больше,
чем размер самих данных, на которые
указывает адрес. Чтобы избежать такой
ситуации, используются специальные
методы организации хранения данных.

8

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

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

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

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

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

Массивы.

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

Пусть одномерный массив называется A, тогда для получения доступа к его i-ому элементу потребуется указать название массива и номер требуемого элемента: A[i]. Когда A – матрица, то она представляема в виде таблицы, доступ к элементам которой осуществляется по имени массива, а также номерам строки и столбца, на пересечении которых расположен элемент: A[i, j], где i – номер строки, j – номер столбца.

В разных языках программирования работа с массивами может в чем-то различаться, но основные принципы, как правило, везде одни. В языке Pascal, обращение к одномерному и двумерному массиву происходит точно так, как это показано выше, а, например, в C++ двумерный массив следует указывать так: A[i][j]. Элементы массива нумеруются поочередно. На то, с какого значения начинается нумерация, влияет язык программирования. Чаще всего этим значением является 0 или 1.

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

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

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

Списки.

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

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

В односвязном списке, приведенным выше, начальным элементом является Head list (голова списка [произвольное наименование]), а все остальное называется хвостом. Хвост списка составляют элементы, разделенные на две части: информационную (поле info) и указательную (поле next). В последнем элементе вместо указателя, содержится признак конца списка – nil.

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

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

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

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

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

Стек.

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

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

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

Если бы было, например 6 элементов, а вставить конкретный элемент требовалось также в пятую ячейку, то исключить бы пришлось уже два элемента.

Очередь.

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

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

Дек.

Дек (deque — double ended queue, «двухсторонняя очередь») – стек с двумя концами. Действительно, несмотря конкретный перевод, дек можно определять не только как двухстороннюю очередь, но и как стек, имеющий два конца. Это означает, что данный вид списка позволяет добавлять элементы в начало и в конец, и то же самое справедливо для операции извлечения.

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

Графы.

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

Граф – совокупность точек, соединенных линиями. Точки называются вершинами (узлами), а линии – ребрами (дугами).

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

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

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

Графы широко используются в структурах, созданных человеком, например в компьютерных и транспортных сетях, web-технологиях. Специальные способы представления позволяют использовать граф в информатике (в вычислительных машинах). Самые известные из них: «Матрица смежности», «Матрица инцидентности», «Список смежности», «Список рёбер». Два первых, как понятно из названия, для репрезентации графа используют матрицу, а два последних – список.

Деревья.

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

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

Узлы, не ссылающиеся ни на какие другие узлы, иначе говоря, ни имеющие потомков называются листьями (2, 3, 9), либо терминальными узлами. Элементы, расположенные между корневым узлом и листьями – промежуточные узлы (1, 1, 7, 8). Каждый узел дерева имеет только одного предка, или если он корневой, то не имеет ни одного.

Поддерево – часть дерева, включающая некоторый корневой узел и все его узлы-потомки. Так, например, на рисунке одно из поддеревьев включает корень 8 и элементы 2, 1, 9.

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

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