Занятие № 3

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

Понятие типа данных

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

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

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

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

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

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

Тем самым, определение нового уточненного типа может иметь вид (пример из языка Модула-2):

 
TYPE T = [c1..c2]

Перечисляемый тип состоит из конечного числа упорядоченных именованных значений.

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

Поскольку значения типа задаются путем перечисления, каждому значению можно однозначно сопоставить натуральное число от 1 до n, где n – число значений перечисляемого типа.

КОНСТРУИРУЕМЫЕ типы данных

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

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

К наиболее распространенным конструируемым типам относятся: массив, запись , запись с вариантами и множество.

УКАЗАТЕЛИ

Понятиеуказателяв языках программирования является абстракцией понятия машинного адреса.

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

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

Динамическое распределение памяти и списки

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

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

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