|
ДОМ
|
Информационные технологии |
Структуры данных |
1. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ 3. СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ 4. ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ 5. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ return_links(); ?> |
2. ПРОСТЫЕ СТРУКТУРЫ ДАННЫХПростые структуры данных называют также примитивными или базовыми структурами. Эти структуры служат основой для построения более сложных структур. В языках программирования простые структуры описываются простыми (базовыми) типами. К таким типам относятся: числовые, битовые, логические, символьные, перечисляемые, интервальные, указатели. В дальнейшем изложении мы ориентируемся в основном на язык PASCAL и его реализации в среде MS DOS. Структура простых типов PASCAL приведена на рис 2.1 (через запятую указан размер памяти в байтах, требуемый для размещения данных соответствующего типа). В других языках программирования набор простых типов может несколько отличаться от указанного. Размер же памяти, необходимый для данных того или иного типа, может быть разным не только в разных языках программирования, но и в разных реализациях одного и того же языка. 2.1. Числовые типы2.1.1. Целые типыС помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т.е. счетное число объектов). Представление в памяти. Например, +10 и -15 в двоичном виде можно представить так:
Отметим, что по соглашению 0 используется для представления знака плюс и 1 - для минуса. Такое представление удобно для программистов т.к. легко воспринимается, но не является экономичным. Если требуется сложить или вычесть два числа, то для решения вопроса о том, какие действия следует при этом предпринять, надо сначала определить знак каждого числа. Например, сложение чисел +6 и -7 на самом деле подразумевает операцию вычитания, а вычитание -6 из +7 операцию сложения. Для анализа знакового бита требуется особая схема и, кроме того, при представлении числа в виде знака и величины необходимы отдельные устройства для сложения и вычитания, т.е., если положительное и отрицательные числа представлены в прямом коде, операции над кодами знаков выполняются раздельно. Поэтому представление чисел в виде знака и значения не нашло широкого применения. В то же время, при помощи обратного и дополнительного кодов, используемых для представления отрицательных чисел, операция вычитания (алгебраического сложения) сводится к операции простого арифметического сложения. При этом операция сложения распространяется и на разряды знаков, рассматриваемых как разряды целой части числа. Именно поэтому для представления целых чисел со знаком применяется дополнительный код. Дополнительный код отрицательного числа формируется по следующим правилам:
Например, для числа -33 в формате integer:
1000000000100001 прямой код
0111111111011110 обратный код
+_______________1
1111111111011111 дополнительный код
Для положительных чисел прямой, обратный и дополнительный коды одинаковы. Аналогично представляются целые числа в формате shortint, longint, comp. При разработке программ на этапе выбора типа данных важно знать диапазон целых величин, которые могут храниться в n разрядах памяти. В соответствии с алгоритмом преобразования двоичных чисел в десятичные, формула суммирования для n разрядов имеет вид:
n-1
2^0 + 2^1 + 2^3 + ... + 2^(n-1), или СУММА (2^i) = 2^n - 1.
i=0
При n-битовом хранении числа в дополнительном коде первый бит выражает знак целого числа. Поэтому положительные числа представляются в диапазоне от 0 до 1*2^0 + 1*2^1 +...+ 1*2^(n-2) или от 0 до 2^(n-1) - 1. Все другие конфигурации битов выражают отрицательные числа в диапазоне от -2^(n-1) до -1. Таким образом, можно сказать, что число N может храниться в n разрядах памяти, если его значение находится в диапазоне:
-2^(n-1) <= N <= 2^(n-1) - 1.
Таблица 2.1 Иными словами, диапазон возможных значений целых типов зависит от их внутреннего представления, которое может занимать 1, 2 или 4 байта. В таблице 2.1 приводится перечень целых типов, размер памяти для их внутреннего представления в битах, диапазон возможных значений. Машинное представление беззнаковых типов. К беззнаковым типам в PASCAL относятся типы BYTE и WORD. Формат машинного представления чисел типа BYTE приведен на рис 2.2. а).
Например: 1). Машинное представление числа 45:
45=2^5+2^3+2^2+2^0 = 00101101
2). Машинное представление границ диапазона
допустимых значений чисел 0 и 255:
0: 00000000; 255: 11111111.
Формат машинного представления чисел типа WORD приведен на рис. 2.2. б).
Например: 1). Машинное представление числа 258:
257=2^8+2^1 = 00000010 00000001.
2). Машинное представление границ:
0: 00000000 00000000; 65535: 11111111 11111111.
Машинное представление чисел со знаком. Для представления чисел со знаком определены следующие типы SHORTINT, INTEGER, LONGINT. В приведенных типах числа хранятся в дополнительном ко- де. Напомним, что дополнительный код положительных чисел совпадает с прямым кодом. Формат машинного представления чисел типа SHORTINT приведен на рис 2.3. а) где s-знаковый разряд числа. Для положительных чисел s=0, для отрицательных s=1.
Например, машинное представление чисел в формате shortint:
1). 0: 00000000;
2). +127: 01111111;
3). -128: 10000000.
Формат машинного представления чисел типа INTEGER приведен на рис 2.3. б). Например:
1). +32765: 11111101 01111111;
2). -32765: 00000011 10000000;
3). -47: 11010001 11111111.
Машинное представление границ диапазона допустимых значений:
4). -32768: 00000000 10000000;
5). 32767: 11111111 01111111.
Формат машинного представления чисел типа LONGINT приведен на рис 2.3. в). Например, представление чисел в формате longint:
1). +89 01011001 00000000 00000000 00000000;
2). -89 10100111 11111111 11111111 11111111.
Машинное представление данных типа COMP. . 0 Тип COMP предназначен для работы с большими целыми числами (см. таблицу 2.1). Поэтому числа данного типа представляются в памяти в соответствии с правилами представления целых чисел со знаком - в дополнительном коде. Но для удобства пользователей при вводе и выводе значений чисел в этом формате допускается использование формы записи чисел характерных для вещественных чисел (в виде мантиссы и порядка).
Например: машинное представление чисел в формате COMP:
+512 0..0 00000010 0..0 0..0 0..0 0..0 0..0 0..0
-512 0..0 11111110 1..1 1..1 1..1 1..1 1..1 1..1
2.1.2. Вещественные типыВ отличии от порядковых типов (все целые, символьный, логический), значения которых всегда сопоставляются с рядом целых чисел и, следовательно, представляются в памяти машины абсолютно точно, значение вещественных типов определяет число лишь с некоторой конечной точностью, зависящей от внутреннего формата вещественного числа. Представление вещественных чисел в памяти. В некоторых областях вычислений требуются очень большие или весьма малые действительные числа. Для получения большей точности применяют запись чисел с плавающей точкой. Запись числа в формате с плавающей точкой является весьма эффективным средством представления очень больших и весьма малых вещественных чисел при условии, что они содержат ограниченное число значащих цифр, и, следовательно, не все вещественные числа могут быть представлены в памяти. Обычно число используемых при вычислениях значащих цифр таково, что для большинства задач ошибки округления пренебрежимо малы. Формат для представления чисел с плавающей точкой содержит одно или два поля фиксированной длины для знаков. Количество позиций для значащих цифр различно в разных ЭВМ, но существует, тем не менее, общий формат, приведенный на рисунке 2.5 а). В соответствии с этой записью формат вещественного числа содержит в общем случае поля мантиссы, порядка и знаков мантиссы и порядка. Однако, чаще вместо порядка используется характеристика, получающаяся прибавлением к порядку такого смещения, чтобы характеристика была всегда положительный. При этом имеет место формат представления вещественных чисел такой, как на рис 2.5 б). Введение характеристики избавляет от необходимости выделять один бит для знака порядка и упрощает выполнение операций сравнения (<,>,<=,>=) и арифметических операций над вещественными числами. Так, при сложении или вычитании чисел с плавающей точкой для того, чтобы выровнять операнды, требуется сдвиг влево или вправо мантиссы числа. Сдвиг можно осуществить с помощью единственного счетчика, в который сначала заносится положительное чис- ло, уменьшающееся затем до тех пор, пока не будет выполнено требуемое число сдвигов. Таким образом, для представления вещественных чисел в памяти ЭВМ порядок p вещественного числа представляется в виде характеристики путем добавления смещения (старшего бита порядка):
Х = 2^(n-1) + k + p, (2.1)
где:
Формулы для вычисления характеристики и количество бит, необходимых для ее хранения, приведены в таблице 2.2.
Таблица 2.2 Следующим компонентом представляемого в машине числа с плавающей точкой является мантисса. Для увеличения количества значащих цифр в представлении числа и исключения переполнения при умножении мантиссу обычно подвергают нормализации. Нормализация означает, что мантисса (назовем ее F), кроме случая, когда F=0, должна находиться в интервале
R^(-1) <= F < 1.
Для двоичной системы счисления R=2. Тогда в связи с тем, что 2^(-1) <= F < 1, ненулевая мантисса любого хранимого числа с плавающей точкой должна начинаться с двоичной единицы. В этом и заключается одно из достоинств двоичной формы представления числа с плавающей точкой. Поскольку процесс нормализации создает дробь, первый бит которой равен 1, в структуре некоторых машин эта еди- ница учитывается, однако не записывается в мантиссу. Эту единицу часто называют скрытой единицей, а получающийся дополнительный бит используют для увеличения точности представления чисел или их диапазона. Приведенный метод нормализации является классическим методом, при котором результат нормализации представляется в виде правильной дроби, т.е. с единицей после точки и нулем в целой части числа. Но нормализацию мантиссы можно выполнить по разному. В IBM PC нормализованная мантисса содержит свой старший бит слева от точки. Иными словами нормализованная мантисса в IBM PC принадлежит интервалу 1 <= F < 2. В памяти машины для данных типа real, single, double этот бит не хранится, т.е. является "скрытым" и используется для увеличения порядка в форматах single или для хранения знака в формате real. Для положительных и отрицательных чисел нормализованная мантисса в памяти представлена в прямом коде. Первый, старший, бит в представлении чисел в формате с плавающей точкой является знаковым, и по принятому соглашению нуль обозначает положительное число, а единица - отрицательное. Число бит для хранения мантиссы и порядка зависит от типа вещественного числа. Суммарное количество байтов, диапазоны допустимых значений чисел вещественных типов, а также количество значащих цифр после запятой в представлении чисел приведены в таблице 2.3.
Таблица 2.3 Алгоритм формирования машинного представления вещественного числа в памяти ЭВМ Алгоритм формирования состоит из следующих пунктов:
Машинное представление данных типа REAL
Формат машинного представления данных типа REAL следующий:
мл. байт ст. байт
а: 7 0 15 8 23 16 31 24 39 32 47 40
x....x м....м м....м м....м м....м sм...м
б: 7 0 -32 -39 -24 -31 -16 -23 -8 -15 -1 -7
где:
Например: 1). Десятичное число 15.375; в двоичной системе счисления 1111.011;
результат нормализации 1.111011*2^3; р=3.
Учитывая отбрасывание неявной единицы и сдвиг порядка, получаем: s=0; х=2^7+1+3=2^7+2^2=132; в двоичной системе счисления х=10000100; м=1110110...0; машинное представление числа:
10000100 00000000 00000000 00000000 00000000 01110110
2). Десятичное число -0.5; аналогичные выкладки дают: нормализованную мантиссу: 1.00...0; машинное представление числа:
10000000 00000000 00000000 00000000 00000000 10000000
3). Десятичное число -25.75; аналогично: нормализованная мантисса: 1.10011100...0; машинное представление числа:
10000101 00000000 00000000 00000000 00000000 11001110
4). Число 0.0; Машинное представление числа:
00000000 00000000 00000000 00000000 00000000 00000000
5). Числа верхней и нижней границ положительного диапазона
~1.7*10^38 -
11111111 11111111 11111111 11111111 11111111 01111111
~2.9*10^(-35) -
00000001 00000000 00000000 00000000 00000000 00000000
Машинное представление данных типа SINGLE Формат машинного представления данных типа SINGLE следующий:
мл. байт ст. байт
7 0 15 8 23 22 16 31 30 24 - номера разрядов памяти
м....м м....м х м...м s х...х
-16 -23 -8 -15 0 -1 -7 7 1 - показатели степеней разрядов
мантиссы и характеристики
где:
Например: 1). Число -15.375; в двоичной системе счисления -1111.011;
нормализованное двоичное число -1.111011*2^3; р=3.
Учитывая отбрасывание неявной единицы и сдвиг порядка, получаем: s=1; х=2^7-1+3=2^7+2^1=130; в двоичной системе счисления х=10000010; м=1110110...0; машинное представление числа в формате SINGLE: 00000000 00000000 01110110 11000001 2). Число -0.1875; в двоичной системе счисления -0.0011;
нормализованное двоичное число -1.1*2^(-3); р=-3.
Учитывая отбрасывание неявной единицы и сдвиг порядка, получаем: s=1; х=2^7-1-3=2^7-2^2; в двоичной системе счисления х=01111100; м=100...0; машинное представление числа в формате SINGLE: 00000000 00000000 01000000 10111110 3). Десятичное число 4.5; аналогичные выкладки дают нормализованную мантиссу: 1.00100...0; машинное представление числа:
00000000 00000000 10010000 01000000
4). Значения верхней и нижней границ чисел отрицательного диапазона ~-3.4*10^38 - 11111111 11111111 01111111 11111111 ~-.4*10^(-45) - 00000001 00000000 00000000 10000000 Машинное представление данных типа DOUBLE Формат машинного представления данных типа DOUBLE следующий: мл.байт ст.байт 7 0 15 8 23 16 31 24 39 32 47 40 55 52 51 48 63 56 м...м м...м м...м м...м м...м м...м х..х м...м s x..x -44 -50 -37 -43 -29 -36 -21 -28 -13 -20 -5 -12 3 0 -1 -4 10 4 где:
Например: 1). Число 15.375; в двоичной системе счисления 1111.011;
результат нормализации 1.111011*2^3; р=3.
Учитывая отбрасывание скрытой единицы и сдвиг порядка, получаем: s=0; x=2^10-1+3=2^10+2^1=1026; в двоичной системе счисления х=10000000010; m=1110110...0; машинное представление числа в формате DOUBLE:
0 00000000 00000000 00000000 00000000 31
32 00000000 11000000 00101110 01000000 63
2). Десятичное число 0.0375; в двоичной системе счисления 0.011;
результат нормализации 1.1*2^(-2); р=-2.
Учитывая отбрасывание скрытой единицы и сдвиг порядка, получаем: s=0; x=2^10-2^1-2^0=2^10-3; машинное представление числа в формате DOUBLE:
0 00000000 00000000 00000000 00000000 31
32 00000000 00000000 11011000 00111111 63
3). Десятичное число 2.5; аналогичные выкладки дают нормализованную мантиссу: 1.0100...0; машинное представление числа 2.5:
00000000 00000000 00000000 00000000
00000000 00000000 00000100 01000000
4). Значения верхней и нижней границ диапазона положительных чисел:
~1.8*10^308 - 11111111 11111111 11111111 11111111
11111111 11111111 11101111 01111111
~4.9*10^(-324) - 00000001 00000000 00000000 00000000
00000000 00000000 00000000 00000000
Символ ~ обозначает приближенное значение числа. Машинное представление данных типа EXTENDED Формат машинного представления данных типа EXTENDED следующий: мл.байт ст. байт 7 0 15 8 23 16 31 24 39 32 47 40 55 48 63 56 71 64 79 72 м..м м..м м..м м..м м..м м..м м..м м..м х..х sх..х -56-63-48-55-40-47-32-39-24-31-16-23-8 -15 0 -7 7 0 14 8 где:
Например: 1). Число -15.375; в двоичной системе счисления -1111.011;
после нормализации -1.111011*2^3; р=3.
Учитывая присутствие скрытой единицы и сдвиг порядка, получаем: s=1; х=2^14-1+3=2^14+2^1=16386; Машинное представление данного числа в формате EXTENDED: 0..0 0..0 0..0 0..0 0..0 0..0 0..0 11110110 00000010 11000000 2). Число 1.0; аналогичные выкладки дают
нормализованную мантиссу: 1.0...0;
машинное представление числа 1.0:
0..0 0..0 0..0 0..0 0..0 0..0 0..0 10000000 11111111 00111111
3). Значения верхней и нижней границ диапазона положительных чисел (символом * помечены разряды, значения которых при данной характеристике не идентифицируются т. е. их значения не влияют на значение мантиссы):
~1.2*10^4932 - ******** ******** 11111111 11111111 11111111
11111111 11111111 11111111 11111111 011111111
~3.1*10^4944 - ******** ******** 00000001 00000000 000000000
00000000 00000000 00000000 00000001 000000000
2.1.3. Десятичные типы Десятичные типы не поддерживаются языком PASCAL, но имеются в некоторых других языках, например, COBOL, PL/1. Эти типы приме няются для внутримашинного представления таких данных, которые в первую очередь должны храниться в вычислительной системе и выдаваться пользователю по требованию, и лишь во вторую очередь - обрабатываться (служить операндами вычислительных операций). Неслучайно эти типы впервые появились в языке COBOL, ориентированном на обработку экономической информации: в большинстве задач этой сферы важно прежде всего хранить и находить информацию, а ее преобразование выполняется сравнительно редко и сводится к простейшим арифметическим операциям. Архитектура некоторых вычислительных систем (например, IBM System/390) предусматривает команды, работающие с десятичным представлением чисел, хотя эти команды и выполняются гораздо медленнее, чем команды двоичной арифметики. В других архитектурах операции с десятичными числами моделируются программно. К десятичным типам относятся: десятичный тип с фиксированной точкой и тип шаблона. Десятичный тип с фиксированной точкой. В языке PL/1 десятичный тип с фиксированной точкой описывается в программе, как: DECIMAL FIXED (m.d) или DECIMAL FIXED (m). Первое описание означает, что данное представляется в виде числа, состоящего из m десятичных цифр, из которых d цифр расположены после десятичной точки. Второе - целое число из m десятичных цифр. Следует подчеркнуть, что в любом случае число десятичных цифр в числе фиксировано. Внутримашинное представление целых чисел и чисел с дробной частью одинаково. Для последних положение десятичной точки запоминается компилятором и учитывается им при трансляции операций, в которых участвуют десятичные числа с фиксированной точкой. Внутримашинное представление данного типа носит название десятичного упакованного формата. Примеры представления чисел в таком формате приведены на рис. 2.6. Каждая десятичная цифра числа занимает полбайта (4 двоичных разряда) и представляется в этом полубайте ее двоичным кодом. Еще полбайта занимает знак числа, который представляется двоичным кодом 1010 - знак "+" или 1011 - знак "-". Представление занимает целое число байт и при необходимости дополняется ведущим нулем. Тип шаблона. В языке PL/1 тип шаблона описывается в программе, как: PICTURE '9...9'. Это означает, что данное представляет собой целое число, содержащее столько цифр, сколько девяток указано в описании. Внутримашинное представление этого типа, так называемый десятичный зонный формат, весьма близок к такому представлению данных, которое удобно пользователю: каждая десятичная цифра представляется байтом: содержащим код символа соответствующей цифры. В IBM System/390, которая аппаратно поддерживает зонный формат, применяется символьный код EBCDIC, в котором код символа цифры содержит в старшем полубайте код 1111, а в младшем - двоичный код цифры числа. Знак не входит в общее число цифр в числе, для представления знака в старшем полубайте последней цифры числа код 1111 заменяется на 1010 - знак "+" или 1011 - знак "-". Примеры представления чисел в зонном формате приведены на рис.2.7. 2.1.4. Операции над числовыми типамиНад числовыми типами, как и над всеми другими, возможны прежде всего четыре основных операции: создание, уничтожение, выбор, обновление. Специфические операции над числовыми типами - хорошо известные всем арифметические операции: сложение, вычитание, умножение, деление. Операция возведения в степень в некоторых языках также является базовой и обозначается специальным символом или комбинацией символов (^ - в BASIC, ** - в PL/1), в дру- гих - выполняется встроенными функциями (pow в C). Обратим внимание на то, что операция деления по-разному выполняется для целых и вещественных чисел. При делении целых чисел дробная часть результата отбрасывается, как бы близка к 1 она ни была. В связи с этим в языке PASCAL имеются даже разные обозначения для деления вещественных и целых чисел - операции "/" и "div" соответственно. В других языках оба вида деления обозначаются одинаково, а тип деления определяется типом операндов. Для целых операндов возможна еще одна операция - остаток от деления - ("mod" - в PASCAL, "%" - в C). Еще одна группа операций над числовыми типами - операции сравнения: "равно", "не равно", "больше", "меньше" и т.п. Существенно, что хотя операндами этих операций являются данные числовых типов, результат их имеет логический тип - "истина" или "ложь".Говоря об операциях сравнения, следует обратить внимание на особенность выполнения сравнений на равенство/неравенство вещественных чисел. Поскольку эти числа представляются в памяти с некоторой (не абсолютной) точностью, сравнения их не всегда могут быть абсолютно достоверны. Поскольку одни и те же операции допустимы для разных числовых типов, возникает проблема арифметических выражений со смешением типов. Это создает некоторые неудобства для программистов, так как в реальных задачах выражения со смешанными типами встречаются довольно часто. Поэтому большинство языков допускает выражения, операнды которых имеют разные числовые типы, но обрабаты- ваются такие выражения в разных языках по-разному. В языке PL/1, например, все операнды выражения приводятся к одному типу - к типу той переменной, в которую будет записан результат, а затем уже выражение вычисляется. В языке же C преобразование типов выполняется в процессе вычисления выражения, при выполнении каждой отдельной операции, без учета других операций; каждая операция вычисляется с точностью самого точного участвующего в ней операнда. Программист, использующий выражения со смешением типов, должен точно знать правила их вычисления для выбранного языка. 2.2. Битовые типыПредставление битовых типов. В ряде задач может потребоваться работа с отдельными двоичными разрядами данных. Чаще всего такие задачи возникают в системном программировании, когда, например, отдельный разряд связан с состоянием отдельного аппаратного переключателя или отдельной шины передачи данных и т.п. Данные такого типа представляются в виде набора битов, упакованных в байты или слова, и не связанных друг с другом. Операции над такими данными обеспечивают доступ к выбранному биту данного. В языке PASCAL роль битовых типов выполняют беззнаковые целые типы byte и word. Над этими типами помимо операций, характерных для числовых типов, допускаются и побитовые операции. Аналогичным образом роль битовых типов играют беззнаковые целые и в языке C. В языке PL/1 существует специальный тип данных - строка битов, объявляемый в программе, как: BIT(n). Данные этого типа представляют собой последовательность бит длиною n. Строка битов занимает целое число байт в памяти и при необходимости дополняется справа нулями. Операции над битовыми типами. Над битовыми типами возможны три группы специфических операций: операции булевой алгебры, операции сдвигов, операции сравнения. Операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor). Эти операции и по названию, и по смыслу похожи на операции над логическими операндами, но отличие в их применении к битовым операндам состоит в том, что операции выполняются над отдельными разрядами операндов. Так операция НЕ состоит в том, что каждый разряд операнда изменяет значение на противоположный. Выполнение операции, например, ИЛИ над двумя битовыми операндами состоит в том, что выполняется ИЛИ между первым разрядом первого операнда и первым разрядом второго операнда, это дает первый разряд результата; затем выполняется ИЛИ между вторым разрядом первого операнда и вторым разрядом второго, получается второй разряд результата и т.д. Ниже даны примеры выполнения побитовых логических операций:
а). x = 01101100 в). x = 01101100
not x = 10010011 y = 11001110
x and y = 01001100
б). x = 01101100 г). x = 01101100
y = 11001110 y = 11001110
x or y = 11101110 x xor y = 10100010
В некоторых языках (PASCAL) побитовые логические операции обозначаются так же, как и операции над логическими операндами и распознаются по типу операндов. В других языках (C) для побитовых и общих логических операций используются разные обозначения. В третьих (PL/1) - побитовые операции реализуются встроенными функциями языка. Операции сдвигов выполняют смещение двоичного кода на заданное количество разрядов влево или вправо. Из трех возможных типов сдвига (арифметический, логический, циклический) в языках программирования обычно реализуется только логический (например, операциями shr, shl в PASCAL). В операциях сравнения битовые данные интерпретируются как целые без знака, и сравнение выполняется как сравнение целых чисел. Битовые строки в языке PL/1 - более общий тип данных, к которому применимы также операции над строковыми данными, рассматриваемые в главе 4. 2.3. Логический типЗначениями логического типа BOOLEAN может быть одна из предварительно объявленных констант false (ложь) или true (истина). Данные логического типа занимают один байт памяти. При этом значению false соответствует нулевое значение байта, а значению true соответствует любое ненулевое значение байта. Например: false всегда в машинном представлении: 00000000; true может выглядеть таким образом: 00000001 или 00010001 или 10000000. Однако следует иметь в виду, что при выполнении операции присваивания переменной логического типа значения true, в соответствующее поле памяти всегда записывается код 00000001. Над логическими типами возможны операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor) - последняя реализована для логического типа не во всех языках. В этих операциях операнды логического типа рассматриваются как единое целое - вне зависимости от битового состава их внутреннего представления. Кроме того, следует помнить, что результаты логического типа получаются при сравнении данных любых типов. Интересно, что в языке C данные логического типа отсутствуют, их функции выполняют данные числовых типов, чаще всего - типа int. В логических выражениях операнд любого числового типа, имеющий нулевое значение, рассматривается как "ложь", а ненулевое - как "истина". Результатами логического типа являются целые числа 0 (ложь) или 1 (истина). 2.4. Символьный типЗначением символьного типа char являются символы из некоторого предопределенного множества. В большинстве современных персональных ЭВМ этим множеством является ASCII (American Standard Code for Information Intechange - американский стандартный код для обмена информацией). Это множество состоит из 256 разных символов, упорядоченных определенным образом и содержит символы заг- лавных и строчных букв, цифр и других символов, включая специальные управляющие символы. Допускается некоторые отклонения от стандарта ASCII, в частности, при наличии соответствующей системной поддержки это множество может содержать буквы русского алфавита. Порядковые номера ( кодировку) можно узнать в соответствующих разделах технических описаний. Значение символьного типа char занимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы. Например: символ "1" имеет ASCII код 49, следовательно машинное представление будет выглядеть следующим образом: 00110001. ASCII, однако, не является единственно возможным множеством. Другим достаточно широко используемым множеством является код EBCDIC (Extended Binary Coded Decimal Interchange Code - расширенный двоично-кодированный десятичный код обмена), применяемый в системах IBM средней и большой мощности. В EBCDIC код символа также занимает один байт, но с иной кодировкой, чем в ASCII. И ASCII, и EBCDIC включают в себя буквенные символы только латинского алфавита. Символы национальных алфавитов занимают "свободные места" в таблицах кодов и, таким образом, одна таблица может поддерживать только один национальный алфавит. Этот недостаток преодолен во множестве UNICODE, которое находит все большее распространение прежде всего в UNIX-ориентированных системах. В UNICODE каждый символ кодируется двумя байтами, что обеспечивает более 64 тыс. возможных кодовых комбинаций и дает возможность иметь единую таблицу кодов, включающую в себя все национальные алфавиты. UNICODE, безусловно, является перспективным, однако, повсеместный переход к двухбайтным кодам символов может вызвать необходимость переделки значительной части существующего программного обеспечения. Специфические операции над символьными типами - только операции сравнения. При сравнении коды символов рассматриваются как целые числа без знака. Кодовые таблицы строятся так, что результаты сравнения подчиняются лексикографическим правилам: символы, занимающие в алфавите места с меньшими номерами, имеют меньшие коды, чем символы, занимающие места с большими номерами. В основном символьный тип данных используется как базовый для построения интегрированного типа "строка символов", рассматриваемого в гл.4. 2.5. Перечислимый типЛогическая структура. Перечислимый тип представляет собой упорядоченный тип данных, определяемый программистом, т.е. программист перечисляет все значения, которые может принимать переменная этого типа. Значения являются неповторяющимися в пределах программы идентификаторами, количество которых не может быть больше 256, например,
type color=(red,blue,green);
work_day=(mo,tu,we,th,fr);
winter_day=(december,january,february);
Машинное представление. Для переменной перечислимого типа выделяется один байт, в который записывается порядковый номер присваиваемого значения. Порядковый номер определяется из описаного типа, причЯм нумерация начинается с 0. Имена из списка перечислимого типа являются константами, например,
var B,С:color;
begin B:=bluе; (* B=1 *)
C:=green; (* С=2 *)
Write(ord(B):4,ord(C):4); end.
После выполнения данного фрагмента программы на экран будут выданы цифры 1 и 2. Содержимое памяти для переменных B И C при этом следующее: В - 00000001; С - 00000010. Операции. На физическом уровне над переменными перечислимого типа определены операции создания, уничтожения, выбора, обновления. При этом выполняется определение порядкового номера идентификатора по его значению и, наоборот, по номеру идентификатораего значение. На логическом уровне переменные перечислимого типа могут быть использованы только в выражениях булевского типа и в операциях сравнения; при этом сравниваются порядковые номера значений. 2.6. Интервальный типЛогическая структура. Один из способов образования новых типов из уже существующих - ограничение допустимого диапазона значений некоторого стандартного скалярного типа или рамок описанного перечислимого типа. Это ограничение определяется заданием минимального и максимального значений диапазона. При этом изменяется диапазон допустимых значений по отношению к базовому типу, но представление в памяти полностью соответствует базовому типу. Машинное представление. Данные интервального типа могут храниться в зависимости от верхней и нижней границ интервала независимо от входящего в этот предел количества значений в виде, представленном в таблице 2.4. Для данных интервального типа требуется память размером один, два или четыре байта, например,
var A: 220..250; (* Занимает 1 байт *)
В: 2221..2226; (* Занимает 2 байта *)
C: 'A'..'K'; (* Занимает 1 байт *)
begin A:=240; C:='C'; B:=2222; end.
После выполнения данной программы содержимое памяти будет следующим: A - 11110000; C - 01000011; B - 10101110 00001000. Операции. На физическом уровне над переменными интервального типа определены операции создания, уничтожения, выбора, обновления. Дополнительные операции определены базовым типом элементов интервального типа.
Таблица 2.4 Примечание: запись chr(ord(0)) в таблице следует понимать как: символ с кодом 0. А) Интервальный тип от символьного: определение кода символа и, наоборот, символа по его коду. Пусть задана переменная типа tz:'d'..'h'. Данной переменной присвоено значение 'e'. Байт памяти отведенный под эту переменную будет хранить ASCII-код буквы 'e' т.е. 01100101 (в 10-ом представлении 101). Б) Интервальный тип от перечислимого: определение порядкового номера идентификатора по его значению и, наоборот, по номеру идентификатора - его значение. На логическом уровне все операции, разрешенные для данных базового типа, возможны и для данных соответствующих интервальных типов. 2.7. УказателиТип указателя представляет собой адрес ячейки памяти (в подавляющем большинстве современных вычислительных систем размер ячейки - минимальной адресуемой единицы памяти - составляет один байт). При программировании на низком уровне - в машинных кодах, на языке Ассемблера и на языке C, который специально ориентирован на системных программистов, работа с адресами составляет значительную часть программных кодов. При решении прикладных задач с использованием языков высокого уровня наиболее частые случаи, когда программисту могут понадобиться указатели, следующие: 1) При необходимости представить одну и ту же область памяти, а следовательно, одни и те же физические данные, как данные разной логической структуры. В этом случае в программе вводятся два или более указателей, которые содержат адрес одной и той же области памяти, но имеют разный тип (см.ниже). Обращаясь к этой области памяти по тому или иному указателю, программист обрабатывает ее содержимое как данные того или иного типа. 2) При работе с динамическими структурами данных,что более важно. Память под такие структуры выделяется в ходе выполнения программы, стандартные процедуры/функции выделения памяти возвращают адрес выделенной области памяти - указатель на нее. К содержимому динамически выделенной области памяти программист может обращаться только через такой указатель. 2.7.1. Физическая структура указателяФизическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы. Рассмотрим в качестве примера структуру адреса в микропроцессоре i8086. Машинное слово этого процессора имеет размер 16 двоичных разрядов. Если использовать представление адреса в одном слове, то можно адресовать 64 Кбайт памяти, что явно недостаточно для сколько-нибудь серьезного программного изделия. Поэтому адрес представляется в виде двух 16-разрядных слов - сегмента и смещения. Сегментная часть адреса загружается в один из специальных сегментных регистров (в i8086 таких регистров 4). При обращении по адресу задается идентификатор сегментного регистра и 16-битное смещение. Полный физический (эффективный) адрес получается следующим образом. Сегментная часть адреса сдвигается на 4 разряда влево, освободившиеся слева разряды заполняются нулями, к полученному таким образом коду прибавляется смещение, как показано на рис. 2.8. Полученный эффективный адрес имеет размер 20 двоичных разрядов, таким образом, он позволяет адресовать до 1 Мбайт памяти. Еще раз повторим, что физическая структура адреса принципиально различна для разных аппаратных архитектур. Так, например, в микропроцессоре i386 обе компоненты адреса 32-разрядные; в процессорах семейства S/390 адрес представляется в виде 31-разрядного смещения в одном из 19 адресных пространств, в процессоре Power PC 620 одним 64-разрядным словом может адресоваться вся как оперативная, так и внешняя память. Операционная система MS DOS была разработана именно для процессора i8086 и использует описанную структуру адреса даже, когда выполняется на более совершенных процессорах. Однако, это сегодня единственная операционная система, в среде которой программист может работать с адресами в реальной памяти и с физической структурой адреса. Все без исключения современные модели процессоров аппаратно выполняют так называемую динамическую трансляцию адресов и совместно с современными операционными системами обеспечивают работу программ в виртуальной (кажущейся) памяти. Программа разрабатывается и выполняется в некоторой виртуальной памяти, адреса в которой линейно изменяются от 0 до некоторого максимального значения. Виртуальный адрес представляет собой число - номер ячейки в виртуальном адресном пространстве. Преобразование виртуального адреса в реальный производится аппаратно при каждом обращении по виртуальному адресу. Это преобразование выполняется совершенно незаметно (прозрачно) для программиста, поэтому в современных системах программист может считать физической структурой адреса структуру виртуального адреса. Виртуальный же адрес представляет собой целое число без знака. В разных вычислительных системах может различаться разрядность этого числа. Большинство современных систем обеспечивают 32-разрядный адрес, позволяющий адресовать до 4 Гбайт памяти, но уже существуют системы с 48 и даже 64-разрядными адресами. 2.7.2. Представление указателей в языках программированияВ программе на языке высокого уровня указатели могут быть типизированными и нетипизированными. При объявлении типизированного указателя определяется и тип объекта в памяти, адресуемого этим указателем. Так например, объявления в языке PASCAL: Var ipt : ^integer; cpt : ^char; или в языке C: int *ipt; char *cpt; означают, что переменная ipt представляет собой адрес области памяти, в которой хранится целое число, а cpt - адрес области памяти, в которой хранится символ. Хотя физическая структура адреса не зависит от типа и значения данных, хранящихся по этому адресу, компилятор считает указатели ipt и cpt имеющими разный тип, и в Pascal оператор: cpt := ipt; будет расценен компилятором как ошибочный (компилятор C для аналогичного оператора присваивания ограничится предупреждением). Таким образом, когда речь идет об указателях типизированных, правильнее говорить не о едином типе данных "указатель", а о целом семействе типов: "указатель на целое", "указатель на символ" и т.д. Могут быть указатели и на более сложные, интегрированные структуры данных, и указатели на указатели. Нетипизированный указатель - тип pointer в Pascal или void * в C - служит для представления адреса, по которому содержатся данные неизвестного типа. Работа с нетипизированными указателями существенно ограничена, они могут использоваться только для сохранения адреса, обращение по адресу, задаваемому нетипизированным указателем, невозможно. 2.7.3. Операции над указателями.Основными операциями, в которых участвуют указатели являются присваивание, получение адреса, выборка. Присваивание является двухместной операцией, оба операнда которой - указатели. Как и для других типов, операция присваивания копирует значение одного указателя в другой, в результате оба указателя будут содержать один и тот же адрес памяти. Если оба указателя, участвующие в операции присваивания типизированные, то оба они должны указывать на объекты одного и того же типа. Операция получения адреса - одноместная, ее операнд может иметь любой тип, результатом является типизированный (в соответствии с типом операнда) указатель, содержащий адрес объекта-операнда. Операция выборки - одноместная, ее операндом является типизированный (обязательно!) указатель, результат - данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда. Перечисленных операций достаточно для решения задач прикладного программирования поэтому набор операций над указателями, допустимых в языке 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, в современных же операционных системах, поддерживающих виртуальную адресацию, различий между указателями нет, все указатели можно считать гигантскими. |
Copyright © Eugene, 2007 |
