2.7.1. Физическая структура указателя
Машинное слово этого процессора имеет размер 16 двоичных разрядов. Если использовать представление адреса в одном слове, то можно адресовать 64 Кбайт памяти, что явно недостаточно для сколько-нибудь серьезного программного изделия. Поэтому адрес представляется в виде двух 16-разрядных слов - сегмента и смещения. Сегментная часть адреса загружается в один из специальных сегментных регистров (в i8086 таких регистров 4). При обращении по адресу задается идентификатор сегментного регистра и 16-битное смещение. Полный физический (эффективный) адрес получается следующим образом. Сегментная часть адреса сдвигается на 4 разряда влево, освободившиеся слева разряды заполняются нулями, к полученному таким образом коду прибавляется смещение. Полученный эффективный адрес имеет размер 20 двоичных разрядов, таким образом, он позволяет адресовать до 1 Мбайт памяти.
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. Операции над указателями. Основными операциями, в которых участвуют указатели являются присваивание, получение адреса, выборка. Присваивание является двухместной операцией, оба операнда которой - указатели. Как и для других типов, операция присваивания копирует значение одного указателя в другой, в результате оба указателя будут содержать один и тот же адрес памяти. Если оба указателя, участвующие в операции присваивания типизированные, то оба они должны указывать на объекты одного и того же типа. Операция получения адреса - одноместная, ее операнд может иметь любой тип, результатом является типизированный (в соответствии с типом операнда) указатель, содержащий адрес объекта-операнда. Операция выборки - одноместная, ее операндом является типизированный (обязательно!) указатель, результат - данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда.
К указателю можно прибавить целое число или вычесть из него целое число. Поскольку память имеет линейную структуру, прибавление к адресу числа даст нам адрес области памяти, смещенной на это число байт (или других единиц измерения) относительно исходного адреса. Результат операций "указатель + целое", "указатель - целое" имеет тип "указатель". Можно вычесть один указатель из другого (оба указателя-операнда при этом должны иметь одинаковый тип). Результат такого вычитания будет иметь тип целого числа со знаком. Его значение показывает на сколько байт (или других единиц измерения) один адрес отстоит от другого в памяти.
Отметим, что сложение указателей не имеет смысла. Поскольку программа разрабатывается в относительных адресах и при разных своих выполнениях может размещаться в разных областях памяти, сумма двух адресов в программе будет давать разные результаты при разных выполнениях. Смещение же объектов внутри программы друг относительно друга не зависит от адреса загрузки программы, поэтому результат операции вычитания указателей будет постоянным, и такая операция является допустимой.
Операции адресной арифметики выполняются только над типизированными указателями. Единицей измерения в адресной арифметике является размер объекта, который указателем адресуется. Так, если переменная ipt определена как указатель на целое число (int *ipt), то выражение ipt+1 даст адрес, больший не на 1, а на количество байт в целом числе. Вычитание указателей также дает в результате не количество байт, а количество объектов данного типа, помещающихся в памяти между двумя адресами. Это справедливо как для указателей на простые типы, так и для указателей на сложные объекты, размеры которых составляют десятки, сотни и более байт.
В связи с имеющимися в языке C расширенными средствами работы с указателями, следует упомянуть и о разных представлениях указателей в этом языке. В C указатели любого типа могут быть ближними (near) и дальними (far) или (huge). Эта дифференциация связана с физической структурой адреса в i8086, которая была рассмотрена выше. Ближние указатели представляют собой смещение в текущем сегменте, для представления такого указателя достаточно одного 16-разрядного слова. Дальние указатели представляются двумя 16-разрядными словами - сегментом и смещением. Разница между far или huge указателями состоит в том, что для первых адресная арифметика работает только со смещением, не затрагивая сегментную часть адреса, таким образом, операции адресной арифметики могут изменять адрес в диапазоне не более 64 Кбайт; для вторых - в адресной арифметике участвует и сегментная часть, таким образом, предел изменения адреса - 1 Мбайт.
Векторы
Логическая структура.
Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени вектора и номеру требуемого элемента.
Машинное представление. Адресация элементов структур.
Элементы вектора размещаются в памяти в подряд расположенных ячейках памяти. Под элемент вектора выделяется количество байт памяти, определяемое базовым типом элемента этого вектора. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом. Размер памяти для хранения вектора определяется произведением длины слота на число элементов.
В языках программирования вектор представляется одномерным массивом с синтаксисом описания вида (PASCAL):
<Имя> : array [n..k] of <тип>;
где n-номер первого элемента, k-номер последнего элемента. Представление в памяти вектора будет такое, как показано на рис. 3.1.
где @ Имя -адрес
вектора или, что тоже самое, адрес первого
элемента вектора,
Sizeof(тип)-размер слота (количество байтов памяти для записи одного элемента вектора), (k-n)*Sizeof(тип) - относительный адрес элемента с номером k, или, что тоже самое, смещение элемента с номером k.
В языках, где память распределяется до выполнения программы на этапе компиляции (C, PASCAL, FORTRAN), при описании типа вектора граничные значения индексов должны определены. В языках, где память может распределяться динамически (ALGOL, PL/1), значения индексов могут быть заданы во время выполнения программы.
Количество байтов непрерывной области памяти, занятых одновременно вектором, определяется по формуле:
ByteSise = ( k - n + 1 ) * Sizeof (тип)
Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу. Смещение i-ого элемента вектора определяется по формуле:
ByteNumer = ( i- n ) * Sizeof (тип),
а адрес его: @ ByteNumber = @ имя + ByteNumber.
где @ имя - адрес первого элемента вектора.
Например:
var МAS: array [ 5..10 ] of word.
Базовый тип элемента вектора - Word требует 2 байта, поэтому на каждый элемент вектора выделяется по два байта. Тогда таблица 3.1 смещений элементов вектора относительно @Mas выглядит так:
|
Смещение (байт) |
+ 0 |
+ 2 |
+ 4 |
+ 6 |
+ 8 |
+ 10 |
|
Идентификатор поля |
MAS[5] |
MAS[6] |
MAS[7] |
MAS[8] |
MAS[9] |
MAS[10] |
Этот вектор будет занимать в памяти: (10-5+1)*2 = 12 байт. Смещение к элементу вектора с номером 8: (8-5)*2 = 6 Адрес элемента с номером 8: @ MAS + 6.
При доступе к вектору задается имя вектора и номер элемента вектора. Таким образом, адрес i-го элемента может быть вычислен как:
@Имя[i] = @Имя + i*Sizeof(тип) - n*Sizeof(тип) (3.1)
Это вычисление не может быть выполнено на этапе компиляции, так как значение переменной i в это время еще неизвестно. Следовательно, вычисление адреса элемента должно производиться на этапе выполнения программы при каждом обращении к элементу вектора. Но для этого на этапе выполнения, во-первых, должны быть известны параметры формулы (3.1): @Имя Sizeof(тип), n, а во-вторых, при каждом обращении должны выполняться две операции умножения и две - сложения. Преобразовав формулу (3.1) в формулу (3.2),
@Имя[i] = A0 + i*Sizeof(тип) -- (3.2)
A0 = @Имя - n*Sizeof(тип) --
сократим число хранимых параметров до двух, а число операций - до одного умножения и одного сложения, так как значение A0 может быть вычислено на этапе компиляции и сохранено вместе с Sizeof(тип) в дескрипторе вектора. Обычно в дескрипторе вектора сохраняются и граничные значения индексов. При каждом обращении к элементу вектора заданное значение сравнивается с граничными и программа аварийно завершается, если заданный индекс выходит за допустимые пределы.
Массивы.
Логическая структура. Массив - такая структура данных, которая характеризуется:
фиксированным набором элементов одного и того же типа;
каждый элемент имеет уникальный набор значений индексов;
количество индексов определяют мерность массива, например, два индекса - двумерный массив, три индекса - трехмерный массив, один индекс - одномерный массив или вектор;
обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента.
Другое определение: массив - это вектор, каждый элемент которого - вектор. Синтаксис описания массива представляется в виде:
<Имя> : Array [n1..k1] [n2..k2] .. [nn..kn] of < Тип >. Для случая двумерного массива:
Mas2D : Array [n1..k1] [n2..k2] of <Тип>, или
Mas2D : Array [n1..k1 , n2..k2] of <Тип>
Физическая структура Физическая структура - это размещение элементов массива в памяти ЭВМ. Для случая двумерного массива, состоящего из (k1-n1+1) строк и (k2-n2+1) столбцов физическая структура представлена на рис. 3.3.
Многомерные массивы хранятся в непрерывной области памяти. Размер слота определяется базовым типом элемента массива. Количество элементов массива и размер слота определяют размер памяти для хранения массива. Принцип распределения элементов массива в памяти определен языком программирования. Так в PASCAL элементы распределяются - по строкам - изменение индексов выполняется в направлении справа налево. Адресом массива является адрес первого байта начального компонента массива.
Операции Важнейшая операция физического уровня над массивом - доступ к заданному элементу. Как только реализован доступ к элементу, над ним может быть выполнена любая операция, имеющая смысл для того типа данных, которому соответствует элемент. Преобразование логической структуры в физическую называется процессом линеаризации, в ходе которого многомерная логическая структура массива преобразуется в одномерную физическую структуру.
Одно из определений массива гласит, что это вектор, каждый элемент которого - вектор. Некоторые языки программирования позволяют выделить из многомерного массива одно или несколько измерений и рассматривать их как массив меньшей мерности. Например, если в PL/1-программе объявлен двумерный массив: DECLARE A(10,10) BINARY FIXED; то выражение: A[*,I] - будет обращаться к одномерному массиву, состоящему из элементов: A(1,I), A(2,I),...,A(10,I).
Символ-джокер "*" означает, что выбираются все элементы массива по тому измерению, которому соответствует заданный джокером индекс
К операциям логического уровня над массивами необходимо отнести такие как сортировка массива, поиск элемента по ключу. Наиболее распространенные алгоритмы поиска и сортировок будут рассмотрены в данной главе ниже.
Специальные массивы. На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объеме памяти может быть недостаточно. К таким массивам относятся симметричные и разреженные массивы.
Симметричные массивы. Двумерный массив, в котором количество строк равно количеству столбцов называется квадратной матрицей. Квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называется симметричной. Если матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не n^2, а лишь n*(n+1)/2 еЯ элементов. Иными словами, в памяти необходимо представить только верхний (включая и диагональ) треугольник квадратной логической структуры. Доступ к треугольному массиву организуется таким образом, чтобы можно было обращаться к любому элементу исходной логической структуры, в том числе и к элементам, значения которых хотя и не представлены в памяти, но могут быть определены на основе значений симметричных им элементов.
На практике для работы с симметричной матрицей разрабатываются процедуры для:
а) преобразования индексов матрицы в индекс вектора,
б) формирования вектора и записи в него элементов верхнего треугольника элементов исходной матрицы.
в) получения значения элемента матрицы из ее упакованного представления. При таком подходе обращение к элементам исходной матрицы выполняется опосредованно, через указанные функции.
Разреженные массивы. Разреженный массив - массив, большинство элементов которого равны между собой, так что хранить в памяти достаточно лишь небольшое число значений отличных от основного (фонового) значения остальных элементов.
Различают два типа разреженных массивов:
1) массивы, в которых местоположения элементов со значениями отличными от фонового, могут быть математически описаны;
2) массивы со случайным расположением элементов.
Разреженные массивы со случайным расположением элементов. К данному типу массивов относятся массивы, у которых местоположения элементов со значениями отличными от фонового, не могут быть математически описаны, т. е. в их расположении нет какой-либо закономерности.
Ё 0 0 6 0 9 0 0 Ё
Ё 2 0 0 7 8 0 4 Ё
Ё10 0 0 0 0 0 0 Ё
Ё 0 0 12 0 0 0 0 Ё
Ё 0 0 0 3 0 0 5 Ё
Пусть есть матрица А размерности 5*7, в которой из 35 элементов только 10 отличны от нуля.
Представление разреженным матриц методом последовательного размещения.
Один из основных способов хранения подобных разреженных матриц заключается в запоминании ненулевых элементов в одномерном массиве и идентификации каждого элемента массива индексами строки и столбца, как это показано на рис. 3.5 а).
Доступ к элементу массива A с индексами i и j выполняется выборкой индекса i из вектора ROW, индекса j из вектора COLUM и значения элемента из вектора A. Слева указан индекс k векторов наибольшеее значение, которого определяется количеством нефоновых элементов. Отметим, что элементы массива обязательно запоминаются в порядке возрастания номеров строк.
Более эффективное представление, с точки зрения требований к памяти и времени доступа к строкам матрицы, показано на рис.3.5.б). Вектор ROW уменьшнен, количество его элементов соответствует числу строк исходного массива A, содержащих нефоновые элементы. Этот вектор получен из вектора ROW рис. 3.5.а) так, что его i-й элемент является индексом k для первого нефонового элемента i-ой строки.
Представление разреженных матриц методом связанных структур.
Множества.
Числовые множества Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char и производные от них типы.
Физическая структура. Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Т.о. максимальное число элементов множества 256, а данные типа множество могут занимать не более 32-ух байт. Число байтов, выделяемых для данных типа множество, вычисляется по формуле: ByteSize = (max div 8)-(min div 8) + 1, где max и min - верхняя и нижняя границы базового типа данного множества.
Номер байта для конкретного элемента Е вычисляется по формуле:
ByteNumber = (E div 8)-(min div 8),
номер бита внутри этого байта по формуле:
BitNumber = E mod 8
{===== Программный пример 3.3 =====}
const max=255; min=0; E=13;
var S : set of byte;
ByteSize, ByteNumb, BitNumb : byte;
begin
S:=[]; { обнулениемножества }
S:=S+[E]; { запись числа в множество }
ByteSize:=(max div 8)-(min div 8)+1;
Bytenumb:=(E div 8)-(min div 8);
BitNumb:=E mod 8;
writeln(bytesize); { наэкране 32 }
writeln(bytenumb); { наэкране 1 }
writeln(bitnumb); { наэкране 5 }
end.
Числовые множества, Символьные множества
Символьные множества хранятся в памяти также как и числовые множества. Разница лишь в том, что хранятся не числа, а коды ASCII символов.
Например, S : set of char; S:=['A','C'];
В этом случае представление множества S в памяти выглядит следующим образом :
@S+0 - 00000000 . . . . . .
. . . . . . @S+31 - 00000000
@S+8 - 00001010
Множество из элементов перечислимого типа Множество, базовым типом которого есть перечислимый тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит от количества элементов в перечислимом типе.
Пример:
Type
Video=(MDA,CGA,HGC,EGA,EGAm,VGA,VGAm,SVGA,PGA,XGA);
Var
S : set of Video;
В памяти будет занимать : ByteSize = (9 div 8)-(0 div 8)+1=2 байта При этом память для переменной S будет распределена как показано на рис. 3.8.
Множество от интервального типа Множество, базовым типом которого есть интервальный тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит от количества элементов, входящих в объявленный интервал.
Например,
type S=10..17;
var I:set of S;
Это не значит, что первый элемент будет начинаться с 10-того или 0-ого бита, как может показаться на первый взгляд. Как видно из формулы вычисления смещения внутри байта 10 mod 8 = 2, смещение первого элемента множества I начнЯтся со второго бита. И, хотя множество этого интервала свободно могло поместиться в один байт, оно займЯт (17 div 8)-(10 div 8)+1 = 2 байта.
В памяти это множество имеет представление как на рис. 3.9.
Для конструирования множеств интервальный тип самый экономичный, т.к. занимает память в зависимости от заданных границ.
Операции над множествами
Пусть S1, S2, S3 : set of byte , Над этими множествами определены следующие специфические операции:
1) Объединение множеств: S2+S3. Результатом является множество, содержащее элементы обоих исходных множеств.
2) Пересечение множеств: S2*S3. Результатом является множество, содержащее общие элементы обоих исходных множеств.
3) Проверка на вхождение элемента в множество: a in S1. Результатом этой операции является значение логического типа - true, если элемент a входит в множество S1, false - в противном случае.