Типы программных данных
Тип данных – определяет множество значений, набор операций, которые можно применять к таким значениям и способ реализации хранения значений и выполнения операций. Любые данные, которыми оперируют программы, относятся к определённым типам.
Процесс проверки и накладывания ограничений на типы используемых данных называется контролем типов или типизацией программных данных. Различают следующие виды типизации:
· Статическая типизация — контроль типов осуществляется при компиляции.
· Динамическая типизация — контроль типов осуществляется во время выполнения.
Контроль типов также может быть строгим и слабым.
· Строгая типизация — совместимость типов автоматически контролируется транслятором:
· Номинативная типизация — совместимость должна быть явно указана (наследована) при определении типа.
· Структурная типизация (англ. structural type system) — совместимость определяется структурой самого типа (типами элементов, из которых построен составной тип).
· Слабая типизация — совместимость типов никак транслятором не контролируется. В языках со слабой типизацией обычно используется подход, когда совместимость определяется и реализуется общим интерфейсом доступа к данным типа.
Типы данных бывают следующие:
· Простые.
o Перечислимый тип. Может хранить только те значения, которые прямо указаны в его описании.
o Числовые. Хранятся числа. Могут применяться обычные арифметические операции.
§ Целочисленные: со знаком, то есть могут принимать как положительные, так и отрицательные значения; и без знака, то есть могут принимать только неотрицательные значения.
§ Вещественные: с запятой (то есть хранятся знак и цифры целой и дробной частей) и с плавающей запятой (то есть число приводится к виду m*be, где m — мантисса, b — основание показательной функции, e — показатель степени (порядок), причём в нормированной форме 1<=m<b, e – целое число и хранятся знак и числа m и e).
o Символьный тип. Хранит один символ. Могут использоваться различные кодировки.
o Логический тип. Имеет два значения: истина и ложь. Могут применяться логические операции. Используется в операторах ветвления и циклах. В некоторых языках является подтипом числового типа, при этом ложь=0, истина=1.
o Множество. В основном совпадает с обычным математическим понятием множества. Допустимы стандартные операции с множествами и проверка на принадлежность элемента множеству. В некоторых языках рассматривается как составной тип.
· Составные (сложные).
o Массив. Является индексированным набором элементов одного типа. Одномерный массив — вектор, двумерный массив — матрица.
o Строковый тип. Хранит строку символов. Аналогом сложения в строковой алгебре является конкатенация (прибавление одной строки в конец другой строки). В языках, близких к бинарному представлению данных, чаще рассматривается как массив символов, в языках более высокой абстракции зачастую выделяется в качестве простого.
o Структура. Набор различных элементов (полей записи), хранимый как единое целое. Возможен доступ к отдельным полям записи. Например, struct в C.
o Файловый тип. Хранит только однотипные значения, доступ к которым осуществляется только последовательно (файл с произвольным доступом, включённый в некоторые системы программирования, фактически является неявным массивом).
o Класс.
· Другие типы данных. Такие типы данных представляют объекты компьютерного мира, то есть являются исключительно компьютерными терминами.
o Указатель. Хранит адрес в памяти компьютера, указывающий на какую-либо информацию, как правило — указатель на переменную.
o Ссылка.
Все данные можно разделить на статические и динамические.
Статическими данными называются такие, память под которые выделяется во время компиляции и сохраняется в течение всей работы программы.
Для динамических данных память распределяется в процессе выполнения программы. Использование динамических данных дает следующие преимущества
1) позволяет увеличить объем обрабатываемых данных;
2) если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации;
3) использование динамической памяти позволяет создавать структуры данных переменного размера.
Объединение простых данных в составные (структуры, классы) называется структуризацией данных. Структуризация данных позволяет упростить процесс программирования за счет применения средств и методов, разработанных непосредственно для работы с данными определенной структуры или класса.
Наиболее часто используемыми сложными структурами данных являются
· стек
· список
· очередь
· дерево
· сеть
Стек(англ. stack — стопка) – структура данных с методом доступа к элементам LIFO (англ. Last In – First Out, «последним пришел — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента, называемое также выталкивание (pop), возможно также только из вершины стека, при этом, второй сверху элемент становится верхним.
Список – это структура данных, состоящая из элементов одного типа, связанных между собой.
Различают
· однонаправленный список (каждый элемент списка имеет указатель на следующий за ним элемент, другими словами – хранит информацию о расположении следующего элемента, кроме того есть переменная, указывающая на первый элемент списка);
· двунаправленный список (каждый элемент списка имеет указатель на следующий за ним элемент и указатель и на предшествующий элемент, кроме того есть переменная, указывающая на первый элемент списка);
· циклический список (последний элемент списка содержит указатель, связывающий его с первым элементом).
Для реализации списка необходима реализация следующих методов:
· помещение элемента в конец списка;
· получение данных о элементе списка;
· перемещение по элементам списка;
· удаление элемента из списка.
Очередь – структура данных с дисциплиной доступа к элементам «первый пришёл – первый вышел» (FIFO, First In – First Out). Добавление элемента (принято обозначать словом enqueue – поставить в очередь) возможно лишь в конец очереди, выборка – только из начала очереди (что принято называть словом dequeue – убрать из очереди), при этом выбранный элемент из очереди удаляется.
Дерево– это связный граф (граф, между любой парой вершин которого существует по крайней мере один путь), не содержащий циклов. В дереве существует только по одному пути между парами вершин.
Граф – совокупность объектов со связями между ними.
Пример дерева
С понятием дерева связываются следующие определения
Узел – объект, над которым осуществляется обратотка.
Вершина (корень) – конечная цель, требующая решения.
Степень узла – количество исходящих дуг.
Концевой узел (лист) — узел со степенью 1.
Узел ветвления — неконцевой узел.
Уровень узла — длина пути от корня до узла.
Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
Сеть – структура данных, подобная иерархической (дерево), но отличающаяся от нее тем, что каждая запись может вступать в любое количество поименованных связей с другими записями как исходная или порожденная, или как то и другое.