Главная
Веб-редактирование и типографика
2. Языки программирования и их использование в информационных системах
Понятие типов данных: скалярные и структурированные, линейные и нелинейные структуры данных

Кто не делится найденным, подобен свету в дупле секвойи (древняя индейская пословица)

Версия для печати

Библиографическая запись: Понятие типов данных: скалярные и структурированные, линейные и нелинейные структуры данных. — Текст : электронный // Myfilology.ru – информационный филологический ресурс : [сайт]. – URL: https://myfilology.ru//165/yazyki-programmirovaniya-i-ix-ispolzovanie-v-informaczionnyx-sistemax/ponyatie-tipov-dannyx-skalyarnye-i-strukturirovannye-linejnye-i-nelinejnye-struktury-dannyx/ (дата обращения: 5.05.2024)

Понятие типов данных: скалярные и структурированные, линейные и нелинейные структуры данных

Содержание

Скалярные типы данных

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

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

Числовые

Числовые типы включают в себя следующие типы данных:

целый тип;
вещественный тип с плавающей точкой;
десятичный тип с фиксированной точкой.

Целый тип

Наиболее распространенным числовым элементарным типом является целый тип. В настоящее время многие компьютеры поддерживают несколько размеров целых чисел, и эти возможности должны быть реализованы в языках программирования. Например, в языке Ada можно использовать три типа целочисленных значений: short integer, integer и long integer, а в языке С — четыре: int, short long и char.

Вещественный тип с плавающей точкой

Вещественный тип с плавающей точкой включен практически во все языки программирования.

Спецификация. Вещественные числа с плавающей точкой обычно определяются одним атрибутом (real или float). Множество значений, которое можно представить с помощью вещественных чисел с плавающей точкой, определяется их точностью и диапазоном. Точность числа определяется числом разрядов мантиссы, а диапазон значений определяется диапазоном изменения экспоненты (от 10^-38 до 10⁺³⁸ для чисел обычной точности и от 10^-308 до 10⁺³⁰⁸ для чисел удвоенной точности). В некоторых языках точность, требуемая для представления вещественных чисел, может быть задана программистом количеством значащих цифр в десятичном представлении. Некоторые десятичные числа, например 0.1 или п, не могут быть точно представлены вещественными числами с плавающей точкой, т. к. они не могут быть представлены конечным набором двоичных цифр.

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

Десятичный тип с фиксированной точкой

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

Спецификация. Десятичное число с фиксированной точкой представляется как последовательность десятичных цифр фиксированной длины с десятичной точкой, разделяющей целую и дробную части числа. При объявлении десятичного типа с фиксированной точкой местоположение десятичной точки задается явно. Например, в языке PL/1 объявление переменной х, содержащей две цифры после десятичной точки, имеет следующий вид:

DECLARE X FIXED DECIMAL (10.2);

Логический тип

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

Логический тип данных состоит из объектов, которые могут принимать два значения: истина (true) и ложь (false ), причем false < true. Наиболее распространенными операциями для этого типа данных являются операции присваивания.

Символьный

Символьный тип позволяет создавать объекты данных, значениями которых является одиночный символ.

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

ПрисвОп : char₁ х char₂ → void

или

ПрисвОп : char₁ х char₂ → char₃

и сравнения:

CpaeOn : char₁ х char₂ → Boolean.

Указательный

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

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

1. Указатели могут ссылаться только на объекты данных одного типа. Такой подход используется в языках программирования, в которых применяется статический контроль и объявления типов (С, Pascal, Ada).
2. Указатели могут ссылаться на объекты данных любого типа в различные моменты выполнения программы. Такой способ используется в языках программирования, в которых реализован динамический контроль типов (например, Smalltalk). Значение типа объекта, на который производится ссылка в текущий момент времени, хранится в дескрипторе.

В некоторых языках (например, в С, C++, Pascal) указатели являются объектами данных, которые можно явно использовать в программе. При этом указатели могут быть как простыми переменными, так и компонентами сложных структур данных. В других языках (например, в Java) указатели являются частью скрытых структур данных, управляемых реализацией языка.

Над указателями определены следующие операции:

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

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

- операция присваивания. Значение одного указателя присваивается другому указателю. Спецификация операции присваивания имеет вид:

ПрисвОп : ptr₁ х ptr₂ → void

или

ПрисвОп : ptr₁ х ptr₂→ ptr₃,

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

СравОп : ptr₁ х ptr₂ → Boolean',

- бинарные арифметические операции (сложение, вычитание):

БинОп : ptr₁ х рtr₂ → ptr₃,

- унарные арифметические операции (инкремент и декремент):

УнарОп : ptr₁ → ptr₂.

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

Строки, массивы, множества, записи (структуры).

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

Символьные строки

Символьная строка — это объект данных, образованный последовательностью символов.

Различают символьные строки следующих видов:

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

Над строками определены следующие операции:

- операция присваивания:

ПрисвОп : string₁ х string₂ → void

или

ПрисвОп : string₁ х string₂ → string₃

- конкатенация (объединение) строк:

КонкСтр : string₁ х string₂ → string₃

- операции сравнения (СравОп): равно, не равно, больше, меньше, больше или равно, меньше или равно. Спецификация операций сравнения имеет вид:

СравОп : string₁ х string₂ → Boolean.

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

- выбор подстроки по указанной позиции первого символа и длине или по указанным позициям ее первого и последнего символов:

Выбор : string₁ х integer₁ х integer₂ → string₂

выбор подстроки на основе сопоставления с образцом:

ВыборОбр : string₁ х string₂ → integer₁, integer₂

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

Векторы (одномерные массивы)

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

Вектор характеризуется следующими атрибутами:

количество компонентов {размер) вектора. Задается явно целочисленным выражением или неявно путем задания диапазона изменения индекса;
тип данных компонентов;
список значений индексов. Обычно задается парой целых чисел, определяющих диапазон значений индекса. Может также задаваться неявно количеством компонентов вектора, при этом значение нижней границы индекса задается по умолчанию (0 или 1). Если диапазон значений индекса задается с помощью перечислимого типа, то значениями индекса могут быть только символьные константы.

Над векторами определены следующие операции:

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

Многомерные массивы

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

Многомерный массив характеризуется тем же набором атрибутов, что и вектор, но для массива требуется указывать диапазон изменения значений индекса (или их количество) для каждого измерения отдельно. Операция индексации для массива синтаксически представляется как имя массива и список индексов — по одному индексу для каждого измерения массива. Например, в языке программирования C++ элемент трехмерного массива А с индексами i, j, k представляется в виде А[i, j, k].

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

Записи

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

Запись характеризуется следующими атрибутами:

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

Типичным примером синтаксиса, используемого для объявления записей, является конструкция struct, используемая в языке С:

struct book
{ char name[20];
char title[50];
int year;
float price;
} child_book, my_book;

Это объявление определяет запись типа book, состоящую из четырех компонентов с именами name title year и price и переменные child_book и my_book этого типа.

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

Перечислимые типы

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

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

type colour = (white, red, green, blue, black);
var circle, square: colour;

Для объектов перечислимого типа определены следующие операции:

операции сравнения: равно, не равно, больше, меньше, больше или равно, меньше или равно;
операция присваивания;
операции succ и pred, которые для данного элемента перечисления определяют соответственно последующий и предыдущий элементы. Операция succ не применима к последнему элементу перечисления, а операция pred — к первому.

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

Реализация операций над объектами перечислимого типа выполняется с использованием встроенных операций над целыми числами.

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

По расположению элементов в памяти:

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

Нелинейные структуры данных

Многосвязные списки, деревья, графы.

Опалева Э. А., Самойленко В. П. Языки программирования и методы трансляции. — СПб.: БХВ-Петербург, 2005. — 480 с.
Себеста Р. У. Основные концепции языков программирования, 5-е изд. : Пер. с англ. — М .: Издательский дом “Вильямс". 2001. — 672 с.

25.04.2022, 1801 просмотр.