СТРУКТУРЫ ДАННЫХ Лектор Спиричева Наталия Рахматулловна Ст. преподаватель каф

Информационных технологий

основные типы данных

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

на ЯВУ

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

float - вещественный;
double - вещественный двойной точности;
void -

не имеющий значения.

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

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

unsigned
signed
short
long

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

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

ФУНДАМЕНТАЛЬНЫЕ ТИПЫ ДАННЫХ

значений. Эти значения можно определенным образом упорядочить (отсюда – название

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

К порядковым типам кроме логического можно также применять функции:
--X – возвращает предыдущее значение порядкового типа;
++Х - возвращает следующее значение порядкового типа.

ФУНДАМЕНТАЛЬНЫЕ ТИПЫ ДАННЫХ

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

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

ФУНДАМЕНТАЛЬНЫЕ ТИПЫ ДАННЫХ

объектов, являющихся дискретными по своей природе (т.е. счетное число объектов).

Числовые

типы

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

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

Например: +10 и -15 в двоичном виде можно представить так:
+10 0 0001010
- 15 1 0001111

0 - используется для представления знака плюс
1 - для минуса.

Целые типы

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

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

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

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

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

Например: для числа -33 в формате short
1000000000100001 прямой код .
0111111111011110 обратный код
+_____________ _1
1111111111011111 дополнительный код

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

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

целые типы с приставкой unsigned (беззнаковый).

Формат машинного представления чисел типа

unsigned char такое же, как и у char.
Например:
1). Машинное представление числа 45:
45=25+23+22+20 = 00101101
2). Машинное представление границ диапазона допустимых значений чисел 0 и 255:
0: 00000000; 255: 11111111.

тип unsigned char

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

7

0

числа 258:
257=28+21 = 00000001 00000010.
2). Машинное представление границ:
0:

00000000 00000000; 65535: 11111111 11111111



тип unsigned short

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

7 0 15 8

SHORT, INT, LONG, LONG LONG. В приведенных типах числа хранятся

в дополнительном коде.

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

машинное представление чисел в формате sHORT
1). +32765: 11111101 0111111
2). - 32765: 00000011 10000000;
3). -47: 11010001

машинное представление чисел в формате CHAR:
1). 0: 00000000;
2). +127: 01111111;
3). - 128: 10000000.

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

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

Перевод чисел из одной системы счисления в другую

в двоичную.
0.24310 0.00111112.
Проверка:
0.0011111 = 0*2-1+0*2-2+1*2-3+1*2-4+1*2-5+1*2-6+1*2-7= 0,2421875

2). Перевести целое число

164 из десятичной системы счисления в двоичную систему.
16410 101001002
Проверка:
10100100=1*27+0*26+1*25+0*24+0*23+1*22+0*21+0*20=128+32+4=164.

При переводе смешанных чисел целая и дробная части числа переводятся отдельно.

Перевод чисел из одной системы счисления в другую

областях вычислений требуются очень большие или весьма малые действительные числа.

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

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

точкой содержит одно или два поля фиксированной длины для знаков.

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

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

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

положительной.

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

для знака порядка и упрощает выполнение операций сравнения (,=) и

арифметических операций над вещественными числами. Так, при сложении или вычитании чисел с плавающей точкой для того, чтобы выровнять операнды, требуется сдвиг влево или вправо мантиссы числа. Сдвиг можно осуществить с помощью единственного счетчика, в который сначала заносится положительное число, уменьшающееся затем до тех пор, пока не будет выполнено требуемое число сдвигов.
Таким образом, для представления вещественных чисел в памяти ЭВМ порядок p вещественного числа представляется в виде характеристики путем добавления смещения (старшего бита порядка):
Х = 2n-1 + k + p, где n - число бит, отведенных для характеристики,
p - порядок числа,
k - поправочный коэффициент фирмы IBM

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

с плавающей точкой является мантисса. Для увеличения количества значащих цифр

в представлении числа и исключения переполнения при умножении мантиссу обычно подвергают нормализации. Нормализация означает, что мантисса (назовем ее F), кроме случая, когда F = 0, должна находиться в интервале R-1 <= F < 1.
Для двоичной системы счисления R = 2. Тогда в связи с тем, что 2-1 <= F < 1, ненулевая мантисса любого хранимого числа с плавающей точкой должна начинаться с двоичной единицы. В этом и заключается одно из достоинств двоичной формы представления числа с плавающей точкой. Поскольку процесс нормализации создает дробь, первый бит которой равен 1, в структуре некоторых машин эта единица учитывается, однако не записывается в мантиссу. Эту единицу часто называют скрытой единицей, а получающийся дополнительный бит используют для увеличения точности представления чисел или их диапазона.

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

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

Двоичное число нормализуется. При этом для

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

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

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

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

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

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

DOUBLE:
7
0
15
8
23
16
31
24
39
32
47
40
55
52
51
48
63
56
- знаковый разряд
- характеристика
- нормализованная мантисса
44
-50
37
-43
29
21
-36
-28
-13
-20
-5
3
-12
0
-1
-4
10
4

таких данных, которые в первую очередь должны храниться в вычислительной

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

Десятичные типы

тип с фиксированной точкой описывается в программе, как:
DECIMAL FIXED (m.d)

или DECIMAL FIXED (m). Первое описание означает, что данное представляется в виде числа, состоящего из m десятичных цифр, из которых d цифр расположены после десятичной точки. Второе - целое число из m десятичных цифр. Следует подчеркнуть, что в любом случае число десятичных цифр в числе фиксировано. Внутримашинное представление целых чисел и чисел с дробной частью одинаково. Для последних положение десятичной точки запоминается компилятором и учитывается им при трансляции операций, в которых участвуют десятичные числа с фиксированной точкой.

Десятичные типы

(4 двоичных разряда) и представляется в этом полубайте ее двоичным

кодом. Еще полбайта занимает знак числа, который представляется двоичным кодом 1010 - знак "+" или 1011 - знак "-". Представление занимает целое число байт и при необходимости дополняется ведущим нулем.

Десятичные типы

в C# является тип decimal, предназначенный для использования в денежных

вычислениях. В типе decimal для представления значений, находящихся в диапазоне от 1Е-28 до 7.9Е+28, используется 128 битов. Помним, что в обычных арифметических вычислениях, производимых над числами с плавающей точкой, неоднократные округления значений приводят к неточному результату. Тип данных decimal устраняет ошибки, возникающие при округлении, и может представлять числа с точностью до 28 десятичных разрядов (а в некоторых случаях и до 29 разрядов). Эта способность представлять десятичные значения без ошибок округления особенно полезна, когда рассчитываются финансы.

Тип decimal C#

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

выбор, обновление. Специфические операции над числовыми типами - хорошо известные всем арифметические операции: сложение, вычитание, умножение, деление. Операция возведения в степень в некоторых языках также является базовой и обозначается специальным символом или комбинацией символов (^ - в BASIC, ** - в PL/1), в других - выполняется встроенными функциями (pow в C). В языке Pascal возведение в степень выполняется с помощью функций Exp и Ln.

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

деления по-разному выполняется для целых и вещественных чисел. При делении

целых чисел дробная часть результата отбрасывается, как бы близка к 1 она ни была. В связи с этим в языке PASCAL имеются даже разные обозначения для деления вещественных и целых чисел - операции "/" и "div" соответственно. В других языках оба вида деления обозначаются одинаково, а тип деления определяется типом операндов. Для целых операндов возможна еще одна операция - остаток от деления - ("mod" - в PASCAL, "%" - в C). Еще одна группа операций над числовыми типами - операции сравнения: "равно", "не равно", "больше", "меньше" и т.п. Существенно, что хотя операндами этих операций являются данные числовых типов, результат их имеет логический тип - "истина" или "ложь".
Говоря об операциях сравнения, следует обратить внимание на особенность выполнения сравнений на равенство/неравенство вещественных чисел. Поскольку эти числа представляются в памяти с некоторой (не абсолютной) точностью, сравнения их не всегда могут быть абсолютно достоверны.

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

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

задачи возникают в системном программировании, когда, например, отдельный разряд связан с состоянием отдельного аппаратного переключателя или отдельной шины передачи данных и т.п. Данные такого типа представляются в виде набора битов, упакованных в байты или слова и не связанных друг с другом. Операции над такими данными обеспечивают доступ к выбранному биту данного. В языке PASCAL роль битовых типов выполняют беззнаковые целые типы byte и word. Над этими типами помимо операций, характерных для числовых типов, допускаются и побитовые операции. Аналогичным образом роль битовых типов играют беззнаковые целые и в языке C.
В языке PL/1 существует специальный тип данных - строка битов, объявляемый в программе, как: BIT(n).
Данные этого типа представляют собой последовательность бит длиною n. Строка битов занимает целое число байт в памяти и при необходимости дополняется справа нулями.

Битовые типы

три группы специфических операций:
операции булевой алгебры
операции сдвигов
операции сравнения

Операции булевой

алгебры - НЕ (!), ИЛИ (|), И (&), исключающее ИЛИ (^).

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

Битовые типы

в). x = 01101100

not x = 10010011 y = 11001110
x & y = 01001100


б). x = 01101100 г). x = 01101100
y = 11001110 y = 11001110
x | y = 11101110 x ^ y = 10100010

Битовые типы

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

типов сдвига (арифметический, логический, циклический) в языках программирования обычно реализуется только логический (например, операциями << и >> в языке C ).

В операциях сравнения битовые данные интерпретируются как целые без знака, и сравнение выполняется как сравнение целых чисел. Битовые строки в языке PL/1 - более общий тип данных, к которому применимы также операции над строковыми данными.

Битовые типы

одна из предварительно объявленных констант false (ложь) или true (истина).

Данные логического типа занимают один байт памяти. При этом значению false соответствует нулевое значение байта, а значению true соответствует любое ненулевое значение байта.
Например:
false всегда в машинном представлении: 00000000;
true может выглядеть таким образом: 00000001 или 00010001 или 10000000.

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

алгебры - НЕ (!), ИЛИ ( || ), И (

&& ), исключающее ИЛИ ( ^). В этих операциях операнды логического типа рассматриваются как единое целое - вне зависимости от битового состава их внутреннего представления.
Кроме того, следует помнить, что результаты логического типа получаются при сравнении данных любых типов.

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

из некоторого предопределенного множества. В большинстве современных персональных ЭВМ этим

множеством является ASCII (American Standard Code for Information Intechange - американский стандартный код для обмена информацией). Это множество состоит из 256 разных символов, упорядоченных определенным образом, и содержит символы заглавных и строчных букв, цифр и других символов, включая специальные управляющие символы. Допускаются некоторые отклонения от стандарта ASCII, в частности, при наличии соответствующей системной поддержки это множество может содержать буквы русского алфавита. Порядковые номера (кодировку) можно узнать в соответствующих разделах технических описаний.
Значение символьного типа char занимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы. Например: символ "1" имеет ASCII код 49, следовательно, машинное представление будет выглядеть следующим образом: 00110001.

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

множеством. Другим достаточно широко используемым множеством является код EBCDIC (Extended

Binary Coded Decimal Interchange Code - расширенный двоично-кодированный десятичный код обмена), применяемый в системах IBM средней и большой мощности. В EBCDIC код символа также занимает один байт, но с иной кодировкой, чем в ASCII.
И ASCII, и EBCDIC включают в себя буквенные символы только латинского алфавита. Символы национальных алфавитов занимают "свободные места" в таблицах кодов, и, таким образом, одна таблица может поддерживать только один национальный алфавит. Этот недостаток преодолен во множестве UNICODE, которое находит все большее распространение прежде всего в UNIX-ориентированных системах. В UNICODE каждый символ кодируется двумя байтами, что обеспечивает более 64 тыс. (216) возможных кодовых комбинаций и дает возможность иметь единую таблицу кодов, включающую в себя все национальные алфавиты. UNICODE, безусловно, является перспективным, однако, повсеместный переход к двухбайтным кодам символов может вызвать необходимость переделки значительной части существующего программного обеспечения.

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

только операции сравнения. При сравнении коды символов рассматриваются как целые

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

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

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

этого типа. Значения являются неповторяющимися в пределах программы идентификаторами, количество которых не может быть больше 2 147 483 647.
Например:
- enum color{red,blue,green};
- enum work_day{mo,tu,we,th,fr};
- enum winter_day{december,january,february};

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

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

определяется из описанного типа, причём нумерация начинается с 0. Имена из списка перечислимого типа являются константами
Например:
- color B,С;
- B:=bluе; (* B=1 *)
- C:=green; (* С=2 *)
- printf(“B- %d C- %d”, B, C); - выдаст на экран: B- 1 C- 2

После выполнения данного фрагмента программы на экран будут выданы цифры 1 и 2. Содержимое памяти для переменных B И C при этом следующее: В - 00000001;
С – 00000010

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

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

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

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

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

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

Интервальный тип языка PASCAL

верхней и нижней границ интервала независимо от входящего в этот

предел количества значений в виде. Для данных интервального типа требуется память размером один, два или четыре байта
Например.
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.

Интервальный тип языка PASCAL

создания, уничтожения, выбора, обновления. Дополнительные операции определены базовым типом элементов

интервального типа.
А). Интервальный тип от символьного: определение кода символа и, наоборот, символа по его коду.
Пусть задана переменная типа tz:'d'..'h'. Данной переменной присвоено значение 'e'. Байт памяти, отведенный под эту переменную, будет хранить ASCII-код буквы 'e', т.е. 01100101 (в 10-м представлении 101).

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

Интервальный тип языка PASCAL

ячеек для хранения информации – байтов, каждый их которых имеет

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

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

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

Указатели

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

указатели, следующие:
1) при необходимости представить одну и ту же область памяти, а следовательно, одни и те же физические данные, как данные разной логической структуры. В этом случае в программе вводятся два или более указателей, которые содержат адрес одной и той же области памяти, но имеют разный тип. Обращаясь к этой области памяти по тому или иному указателю, программист обрабатывает ее содержимое как данные того или иного типа;
2) при работе с динамическими структурами данных, что более важно. Память под такие структуры выделяется в ходе выполнения программы, стандартные функции выделения памяти возвращают адрес выделенной области памяти - указатель на нее. К содержимому динамически выделенной области памяти программист может обращаться только через такой указатель.

Указатели

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

При объявлении типизированного указателя определяется и тип объекта в памяти, адресуемого этим указателем.
Так, например, объявления в языке PASCAL:
Var ipt : ^integer; cpt : ^char;
или в языке C:
int* ipt; char* cpt;
означают, что переменная ipt представляет собой адрес области памяти, в которой хранится целое число, а cpt - адрес области памяти, в которой хранится символ.

Указатели

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

считает указатели ipt и cpt имеющими разный тип, и в Pascal оператор
cpt := ipt;
будет расценен компилятором как ошибочный (компилятор C для аналогичного оператора присваивания, в случае явного приведения типов, ограничится предупреждением).

Таким образом, когда речь идет об указателях типизированных, правильнее говорить не о едином типе данных "указатель", а о целом семействе типов: "указатель на целое", "указатель на символ" и т.д. Могут быть указатели и на более сложные, интегрированные структуры данных, и указатели на указатели.

Указатели

или void * в C, служит для представления адреса, по

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

Указатели

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

операцией, оба операнда которой - указатели. Как и для других типов, операция присваивания копирует значение одного указателя в другой, в результате оба указателя будут содержать один и тот же адрес памяти. Если оба указателя, участвующие в операции присваивания, типизированные, то оба они должны указывать на объекты одного и того же типа.
Операция получения адреса - одноместная, ее операнд может иметь любой тип, результатом является типизированный (в соответствии с типом операнда) указатель, содержащий адрес объекта-операнда.
Операция разыменования - одноместная, ее операндом является типизированный (обязательно!) указатель, результат - данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда.

Указатели

адресной арифметики

К указателю

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

Указатели

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

который указателем адресуется. Так, если переменная ipt определена как указатель на целое число (int *ipt), то выражение ipt+1 даст адрес, больший не на 1, а на количество байт в целом числе (в MS DOS - 2). Вычитание указателей также дает в результате не количество байт, а количество объектов данного типа, помещающихся в памяти между двумя адресами. Это справедливо как для указателей на простые типы, так и для указателей на сложные объекты, размеры которых составляют десятки, сотни и более байт.

Указатели

представляются целые отрицательные числа в памяти компьютера?

Каковы особенности представления вещественных

чисел?

Какие основные операции выполняются над фундаментальными типами данных?

КОНТРОЛЬНЫЕ ВОПРОСЫ