ПРОСТЫЕ СТРУКТУРЫ ДАННЫХ

 

ПРОСТЫЕ СТРУКТУРЫ ДАННЫХ

зовыми структурами. Эти структуры служат основой для построения более сложных структур. В языках программирования простые струк- туры описываются простыми (базовыми) типами. К таким типам отно-

Числовые типы

Целые типы

объектов, являющихся дискретными по своей природе (т.е. счетное число объектов). ПРЕДСТАВЛЕНИЕ В ПАМЯТИ. Для представления чисел со знаком в

Вещественные типы

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

Операции над числовыми типами

Над числовыми типами, как и над всеми другими, возможны

прежде всего четыре основных операции: создание, уничтожение, вы-

бор, обновление. Специфические операции над числовыми типами -

хорошо известные всем арифметические операции: сложение, вычита-

ние, умножение, деление. Операция возведения в степень в некото-

рых языках также является базовой и обозначается специальным сим-

волом или комбинацией символов (^ - в BASIC, ** - в PL/1), в дру-

гих - выполняется встроенными функциями (pow в C).

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

полняется для целых и вещественных чисел. При делении целых чисел

дробная часть результата отбрасывается, как бы близка к 1 она ни

была. В связи с этим в языке PASCAL имеются даже разные обозначе-

ния для деления вещественных и целых чисел - операции "/" и

"div" соответственно. В других языках оба вида деления обознача-

ются одинаково, а тип деления определяется типом операндов. Для

целых операндов возможна еще одна операция - остаток от деления -

("mod" - в PASCAL, "%" - в C).

Еще одна группа операций над числовыми типами - операции

сравнения: "равно", "не равно", "больше", "меньше" и т.п. Сущест-

венно, что хотя операндами этих операций являются данные числовых

типов, результат их имеет логический тип - "истина" или "ложь".

Говоря об операциях сравнения, следует обратить внимание на осо-

бенность выполнения сравнений на равенство/неравенство веществен-

ных чисел. Поскольку эти числа представляются в памяти с некото-

рой (не абсолютной) точностью, сравнения их не всегда могут быть

абсолютно достоверны.

Поскольку одни и те же операции допустимы для разных число-

вых типов, возникает проблема арифметических выражений со смеше-

нием типов. Это создает некоторые неудобства для программистов,

так как в реальных задачах выражения со смешанными типами встре-

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

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

ваются такие выражения в разных языках по-разному. В языке PL/1,

например, все операнды выражения приводятся к одному типу - к ти-

пу той переменной, в которую будет записан результат, а затем уже

выражение вычисляется. В языке же C преобразование типов выполня-

ется в процессе вычисления выражения, при выполнении каждой от-

дельной операции, без учета других операций; каждая операция вы-

числяется с точностью самого точного участвующего в ней операнда.

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

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

Битовые типы

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

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

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

Символьный тип

рого предопределенного множества. В большинстве современных пер- сональных ЭВМ этим множеством является ASCII (American Standard Code for Information Intechange - американский стандартный код

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

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

Интервальный тип

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

Указатели

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

Физическая структура указателя

ратной архитектуры вычислительной системы. Рассмотрим в качестве примера структуру адреса в микропроцессоре i8086. Машинное слово этого процессора имеет размер 16 двоичных

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

типизированными и нетипизированными. При объявлении типизированного указателя определяется и тип объекта в памяти, адресуемого этим указателем. Так например, объ-

Операции над указателями.

Основными операциями, в которых участвуют указатели являются

присваивание, получение адреса, выборка.

Присваивание является двухместной операцией, оба операнда

которой - указатели. Как и для других типов, операция присваива-

ния копирует значение одного указателя в другой, в результате оба

указателя будут содержать один и тот же адрес памяти. Если оба

указателя, участвующие в операции присваивания типизированные, то

оба они должны указывать на объекты одного и того же типа.

Операция получения адреса - одноместная, ее операнд может

иметь любой тип, результатом является типизированный (в соответс-

твии с типом операнда) указатель, содержащий адрес объекта-опе-

ранда.

Операция выборки - одноместная, ее операндом является типи-

зированный (обязательно!) указатель, результат - данные, выбран-

ные из памяти по адресу, заданному операндом. Тип результата оп-

ределяется типом указателя-операнда.

Перечисленных операций достаточно для решения задач приклад-

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

пустимых в языке Pascal, этим и ограничивается. Системное прог-

раммирование требует более гибкой работы с адресами, поэтому в

языке C доступны также операции адресной арифметики, которые опи-

сываются ниже.

К указателю можно прибавить целое число или вычесть из него

целое число. Поскольку память имеет линейную структуру, прибавле-

ние к адресу числа даст нам адрес области памяти, смещенной на

это число байт (или других единиц измерения) относительно исход-

ного адреса. Результат операций "указатель + целое", "указатель -

целое" имеет тип "указатель".

Можно вычесть один указатель из другого (оба указателя-опе-

ранда при этом должны иметь одинаковый тип). Результат такого вы-

читания будет иметь тип целого числа со знаком. Его значение по-

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

отстоит от другого в памяти.

Отметим, что сложение указателей не имеет смысла. Поскольку

программа разрабатывается в относительных адресах и при разных

своих выполнениях может размещаться в разных областях памяти,

сумма двух адресов в программе будет давать разные результаты при

разных выполнениях. Смещение же объектов внутри программы друг

относительно друга не зависит от адреса загрузки программы, поэ-

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

такая операция является допустимой.

Операции адресной арифметики выполняются только над типизи-

рованными указателями. Единицей измерения в адресной арифметике

является размер объекта, который указателем адресуется. Так, если

переменная ipt определена как указатель на целое число (int

*ipt), то выражение ipt+1 даст адрес, больший не на 1, а на коли-

чество байт в целом числе (в MS DOS - 2). Вычитание указателей

также дает в результате не количество байт, а количество объектов

данного типа, помещающихся в памяти между двумя адресами. Это

справедливо как для указателей на простые типы, так и для указа-

телей на сложные объекты, размеры которых составляют десятки,

сотни и более байт.

В связи с имеющимися в языке C расширенными средствами рабо-

ты с указателями, следует упомянуть и о разных представлениях

указателей в этом языке. В C указатели любого типа могут быть

ближними (near) и дальними (far) или (huge). Эта дифференциация

связана с физической структурой адреса в i8086, которая была

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

текущем сегменте, для представления такого указателя достаточно

одного 16-разрядного слова. Дальние указатели представляются дву-

мя 16-разрядными словами - сегментом и смещением. Разница между

far или huge указателями состоит в том, что для первых адресная

арифметика работает только со смещением, не затрагивая сегментную

часть адреса, таким образом, операции адресной арифметики могут

изменять адрес в диапазоне не более 64 Кбайт; для вторых - в ад-

ресной арифметике участвует и сегментная часть, таким образом,

предел изменения адреса - 1 Мбайт.

Впрочем, это различие в представлении указателей имеется

только в системах программирования, работающих в среде MS DOS, в

современных же операционных системах, поддерживающих виртуальную

адресацию, различий между указателями нет, все указатели можно

считать гигантскими.