Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

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

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Представление типов данных и операции над ними в языке Pascal




 

В языках программирования простые структуры описываются простыми (базовыми) типами. К таким типам относятся: числовые, битовые, логические, символьные, перечисляемые, интервальные, указатели.

К числовому типу данных в языке Pascal относятся целые и вещественные числа. С помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т.е. счетное число объектов). В памяти компьютеров такие объекты хранятся отдельно в виде знака и значения. Обычно для знака отводится старший бит двоичного числа, затем следует запись его значения. Причем для отрицательных чисел значение хранится в обратном или дополнительном коде. Это облегчает выполнение операции вычитания, которая сводится к операции простого арифметического сложения. В таблице 1 приведены целые типы данных языка Pascal с указанием размера памяти для их внутреннего представления и диапазона возможных значений.

 

Таблица 1. Целые типы языка Pascal

Тип Диапазон значений Машинное представление
shortint -128..127 8 бит, со знаком
integer -32768..32767 16 бит, со знаком
longint -2147483648..2147483647 32 бита, со знаком
byte 0..255 8 бит, без знака
word 0..65535 16 бит, без знака
comp -2^63+1..2^63-1 64 бита, со знаком

 

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

Формат для представления чисел с плавающей точкой содержит одно или два поля фиксированной длины для знаков. Количество позиций для значащих цифр различно в разных ЭВМ, но существует общий формат, приведенный на рис. 2. a, в соответствии с которым запись вещественного числа содержит в общем случае поля мантиссы, порядка и знаков мантиссы и порядка. Введение характеристики (рис. 2, б) избавляет от необходимости выделять один бит для знака порядка и упрощает выполнение операций сравнения (<, >, <=, >=) и арифметических операций над вещественными числами. Тогда при сложении или вычитании чисел с плавающей точкой для того, чтобы выровнять операнды, требуется сдвиг влево или вправо мантиссы числа.

 

а) с порядком

Знак числа Порядок Знак порядка   Мантисса

б) с характеристикой

 

Знак числа Характеристика Мантисса  

 

Рис. 2 – Форматы представления вещественных чисел

 

Таким образом, для представления вещественных чисел в памяти ЭВМ порядок p вещественного числа представляется в виде характеристики x путем добавления смещения (старшего бита порядка):

 

x = 2 n –1 + k + p,

где:

n – число бит, отведенных для характеристики,

p – порядок числа,

k – поправочный коэффициент фирмы IBM, равный +1 для real и –1 для форматов single, double, extended.

Формулы для вычисления характеристики и количества бит, необходимых для ее хранения, приведены в табл. 2.

 

Табл. 2. Вещественные типы данных языка PASCAL

Тип Характеристика Количество бит на характеристику
real x = 27 + p + 1  
single x = 27 + p – 1  
double x = 210 + p – 1  
extended x = 214 + p – 1  

 

Для увеличения количества значащих цифр в представлении числа и исключения переполнения при умножении мантиссу обычно подвергают нормализации. Нормализация означает, что мантисса (назовем ее F), кроме случая, когда F = 0, должна находиться в интервале 1 ≤ F < 2. В памяти машины для данных типа real, single, double старший бит не хранится (т.к. он всегда равен единице), т.е. является «скрытым» и используется для увеличения порядка в форматах single или для хранения знака в формате real.

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

 

Табл. 3. Диапазоны значений вещественных типов языка PASCAL

Тип Диапазон значений Значащие цифры Размер, байт
real 2,9*10-39..1,7*1038 11–12  
single 1,4*10-45..3,4*1038 7–8  
double 4,9*10-324..1,8*10308 15–16  
extended 3,1*10-4944..1,2*104932 19–20  

 

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

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

Еще одна группа операций над числовыми типами – операции сравнения: «равно», «не равно», «больше», «меньше». Их результат имеет логический тип: «истина» или «ложь». Поскольку вещественные числа представляются в памяти с некоторой точностью, сравнения их на равенство/неравенство не всегда могут быть абсолютно достоверны.

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

Значениями логического типа BOOLEAN может быть одна из предварительно объявленных констант false (ложь) или true (истина). Данные логического типа занимают одно машинное слово. При этом значению false соответствует нулевое значение, а значению true соответствует любое ненулевое значение. Над логическими типами возможны операции булевой алгебры: НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor). В этих операциях операнды логического типа рассматриваются как единое целое вне зависимости от битового состава их внутреннего представления. Кроме того, следует помнить, что результаты логического типа получаются при сравнении данных любых типов.

Значением символьного типа char являются символы из некоторого предопределенного множества. Ранее большую популярность получил стандарт ASCII (American Standard Code for Information Intechange – стандартный американский код для обмена информацией), задающий множество из 256 разных символов, упорядоченных определенным образом. Набор ASCII содержит символы заглавных и строчных букв, цифр и других символов, включая специальные управляющие символы. Допускаются некоторые отклонения от стандарта ASCII, в частности, при наличии соответствующей системной поддержки это множество может содержать буквы русского алфавита.

Значение символьного типа char занимает в памяти 1 байт и представляет один символ из таблицы ASCII. Например, символ «1» имеет ASCII код 49, следовательно, машинное представление будет выглядеть следующим образом: 00110001.

Таблица ASCII включают в себя буквенные символы только латинского алфавита. Символы национальных алфавитов занимают «свободные места» в таблицах кодов и, таким образом, одна таблица может поддерживать только один национальный алфавит. Этот недостаток может быть исправлен с помощью кодировки UNICODE. В UNICODE каждый символ кодируется двумя байтами, что обеспечивает более 64 тыс. возможных кодовых комбинаций и дает возможность иметь единую таблицу кодов, включающую в себя все национальные алфавиты.

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

 

Указатели

 

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

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

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

Физическая структура указателей. Физическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы. Например, в процессоре i8086 эффективный адрес имеет размер 20 двоичных разрядов, что позволяет адресовать до 1 Мбайт памяти. При этом он состоит из двух частей: сегмента и смещения. В микропроцессоре i386 обе компоненты адреса 32-разрядные; в процессорах семейства S/390 адрес представляется в виде 31-разрядного смещения в одном из 19 адресных пространств; в процессоре Power PC 620 одним 64-разрядным словом может адресоваться вся как оперативная, так и внешняя память.

Все без исключения модели современных процессоров аппаратно выполняют динамическую трансляцию адресов и совместно с операционными системами обеспечивают работу программ в виртуальной памяти. Программа разрабатывается и выполняется в некоторой виртуальной памяти, адреса в которой линейно изменяются от 0 до некоторого максимального значения. Виртуальный адрес представляет собой число – номер ячейки в виртуальном адресном пространстве. Преобразование виртуального адреса в реальный выполняется аппаратно при каждом обращении по виртуальному адресу. Это преобразование происходит совершенно прозрачно для программиста, поэтому структуру виртуального адреса можно считать и его же физической структурой. Виртуальный адрес представляет собой целое число без знака. Большинство современных систем обеспечивают 32-разрядный адрес, позволяющий адресовать до 4 Гбайт памяти, однако активно внедряются системы с 64-разрядными адресами.

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

 

Var ipt: ^integer; cpt: ^char;

 

означают, что переменная ipt представляет собой адрес области памяти, в которой хранится целое число, а cpt – адрес области памяти, в которой хранится символ. Хотя физическая структура адреса не зависит от типа и значения данных, хранящихся по этому адресу, компилятор считает указатели ipt и cpt, имеющими разный тип, и в Pascal оператор:

 

cpt:= ipt;

 

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

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

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

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

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

Операция выборки – одноместная, ее операндом является типизированный указатель, результат – данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда.

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

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

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

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

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

Лекция 2

План лекции:

1. Открытое хеширование данных.

2. Закрытое хеширование данных.

3. Алгоритмы работы с хеш-таблицами методами открытой адресации.

 

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

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных