2. Структура данных, классификация различных типов наборов данных.

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

Термин «структура данных» может иметь несколько близких, но тем не менее различных значений^[1]:

• Абстрактный тип данных;

• Реализация какого-либо абстрактного типа данных;

• Экземпляр типа данных, например, конкретный список;

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

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

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

При разработке программного обеспечения сложность реализации и качество работы программ существенно зависит от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопаснопереиспользоваться в различных приложениях. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода.

Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов(STL) языка C++.

Фундаментальными строительными блоками для большей части структур данных являются массивы, записи (struct в Си и record в Паскале), размеченные объединения (union в Си) и ссылки. Например, двусвязный список может быть построен с помощью записей и ссылок, где каждая запись (узел) будет хранить данные и ссылки на «левый» и «правый» узлы.

Типы данных бывают следующие:

Простые.

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

• Числовые. Хранятся числа. Могут применяться обычные арифметические операции.

  • Целочисленные: со знаком, то есть могут принимать как положительные, так и отрицательные значения; и без знака, то есть могут принимать только неотрицательные значения.

  • Вещественные: с запятой (то есть хранятся знак и цифры целой и дробной частей) и с плавающей запятой (то есть число приводится к виду m*b^e, где m —мантисса, b — основание показательной функции, e — показатель степени (порядок) (в англоязычной литературе экспонента), причём в нормальной форме0<=m<b, а в нормализованной форме 1<=m<b, e — целое число и хранятся знак и числа m и e).

  • Числа произвольной точности, обращение с которыми происходит посредством длинной арифметики. Примером языка с встроенной поддержкой таких типов является UBASIC, часто применяемый среди криптографов.

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

• Логический тип. Имеет два значения: истина и ложь, при троичной логике может иметь и третье значение — «не определено» (или «неизвестно»). Могут применяться логические операции. Используется в операторах ветвления и циклах. В некоторых языках является подтипом числового типа, при этом ложь=0, истина=1.

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

• Составные (сложные).

  • Массив. Является индексированным набором элементов одного типа. Наиболее популярны: одномерный массив — вектор (в случае чисел) или строковый тип (в случае символов), двумерный массив — матрица.

    • Строковый тип. Хранит строку символов. Аналогом сложения в строковой алгебре является конкатенация (прибавление одной строки в конец другой строки). В языках, близких к бинарному представлению данных, чаще рассматривается как массив символов, в языках более высокой абстракции зачастую выделяется в качестве простого.

  • Запись (структура). Набор различных элементов (полей записи), хранимый как единое целое. Возможен доступ к отдельным полям записи. Например, struct в C или record в Pascal.

  • Файловый тип. Хранит только однотипные значения, доступ к которым осуществляется только последовательно (файл с произвольным доступом, включённый в некоторые системы программирования, фактически является неявным массивом).

  • Класс.

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

  • Указатель. Хранит адрес в памяти компьютера, указывающий на какую-либо информацию, как правило — указатель на переменную.

  • Ссылка.