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

Текст из файла (страница 11)

a.SetLength(n); /* если длина массива больше, чем старая длина, массив переразмещается в памяти с сохранением старых значений; если меньше, то часть значений теряется (при этом сборка мусора происходит динамически)*/.

Диапазон индексов от 0 до N-1.

Кроме этого и в Java, и в C# обращение (индексация) обязательно являются динамически контролируемой величиной. Из соображений надежности отключить такие проверки нельзя (в безопасном коде).

Идеология современных ЯП такова: не нужно расширять базис, нужно развивать средства развития.

Рассмотрим, например, средства развития языка С++: понятие класса дополнено понятием перекрытия операций (overloading)(нельзя переопределять только операции ., .*, ->*, ?: ).

В языке С++ можно перекрывать операцию индексирования [ ].

При этом должно выполняться требование: местность операции (т.е. количество аргументов) должно быть точно такое же, что и в стандартной операции.

У операции индексирования два аргумента: а[l].

Операцию индексирования на языке С++ можно записывать и так:

operator[ ] (a,l), где а – объект, который индексируется, l – индексное выражение.

При этом а и l могут иметь произвольный тип данных, т.е. язык С++ фиксирует только количество аргументов операции, но не фиксирует их тип.

В языке Java понятие перекрытия на стандартные операции не распространяется..

И в языке Delphi, и в C# есть понятие индексатора: к классу можно добавить некоторую функцию, которая называется индексатор.

В частности, в C#

сlass Х {

…

this (T i) {…}

}

где Т – тип индекса.

В этом случае индексатор должен вернуть ссылку на элемент массива.

К элементам класса Х применима операция индексирования Х[e], где е – выражение

типа Т.

И в языке C#, и в Delphi можно писать массивы и контейнеры, в которых произвольная операция индексирования.

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

Проблема длины в С/С++ решается следующим образом.

Для массивов длина либо является статическим атрибутом, либо неизвестна вообще и она никак не учитывается.

Т.е., например, если описано int а [20]; то длина – статический атрибут. Если же описано void f(int а[]) (формальный параметр) либо конструкция extern int a[]; - длина неизвестна.

Для чего нужна длина компилятору С/С++? Только для распределения памяти.

Длина в языках С/С++ не может быть динамическим атрибутом.

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

Многомерные массивы.

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

Например, в языке С

int a[N1][N2];

а – это фактически одномерный массив элементов int, у которого число элементов N1* N2.

Возникает вопрос, каким образом в памяти многомерный массив отображается в одномерный? Есть две возможности: либо линеаризация по строкам, либо по столбцам.

Например, двумерный массив

1 2

3 4

по строкам будет располагаться как 1 2 3 4, по столбцам 1 3 2 4.

Заметим, что Fortran интерпретировал массивы именно по столбцам. Все остальные рассматриваемые ЯП интерпретируют линеаризацию по строкам.

В языке С допустимо int a[]; для двумерного массива int a[][] – недопустимо, т.к. компилятор не может линеаризовать адрес в одномерном массиве.

Линеаризация – сведение нескольких размерностей к одному индексу.

Какой адрес в одномерном массиве даст A[i][j], i=0..N1-1; j=0..N2-1 ?

Адрес (i ,j) преобразуется в линейный адрес i*N2+j, где N2 – число элементов в строке.

Поэтому

int a[][N2] ; //допустимо, т.к. можно вычислить индекс

int a[N1][] ; //недопустимо.

Рассмотрим многомерный массив int a[N1][N2][N3]

Тогда (i,j,k) -> i*N2*N3+j*N3+k.

Рассмотрим int a[N1]…[Nk].

Тогда (i1,…ik)->i1*N2*…*Nk + i2*N3*…*Nk + i(k-1)*Nk +ik.

Сейчас мы рассматривали прямоугольные массивы. Некоторые ЯП допускают ступенчатые массивы (например, C#). Чем ступенчатый массив отличается от линеаризованного? Линеаризованный массив – это последовательность элементов базового типа; ступенчатый массив – это массив, элементы которого являются ссылками.

Инициализация двумерного массива такова int [,]a={{1,2,3},{3,4,5}}.

Обращение к его элементам имеет вид: а[i][j], i = 0,1; j=0,1,2.

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

int[][]a = {new int[2],

new int [4],

new int[1]}

Эта запись означает, что массив а - вектор из трёх элементов; первый элемент есть ссылка на массив из 2 элементов, второй - из четырех, третий - из одного.

рис.

Т.е. это непрямоугольный (ступенчатый) массив.

В языках C# и Java подобные возможности можно промоделировать.

Сечения.

В языке PL1 можно было делать так.

Пусть А(20,30) - двумерный массив(матрица из 20 строк и 30 столбцов), тогда A(*,1) - это первый столбец массива А, т.е. а11,а21,...,а20,1.

Языки PL1 и Fortran позволяли делать произвольные вырезки ( т.е. вместо индекса можно было указывать как *, так и произвольный диапазон).

Например, A(*,2:4) - это матрица, образованная 2-м,3-м и 4-м столбцами исходной матрицы. Т.о., можно делать произвольные прямоугольные вырезки.

Сечения разрешены также и в языке Ада (можно делать сечения только последовательно размещенных элементов).Например, в одномерном массиве можно сделать сечение A(2:5);

Пункт 2 Записи (структуры)

Впервые понятие record (запись) появилось в работе Хоара 1967 года.

Фактически, запись - это ограничение видимости.

Идея записи - локализация имен переменных внутри структуры. На Pascal и Modula 2 запись выглядит так:

record

a,b,c:integer;

f:real;

end

К полям записи обращаемся следующим образом: объект-запсиь.имя_поля.

В языке С появилась операция доступа через указатель р->, где р - указатель на запись.

В языке Oberon операции разыменования нет, т.к. в этом языке указатель может указывать только на объекты типа запись.

Та же ситуация в языке Ада: р.имя_поля.

Чем же различаются языки с точки зрения записи? Практически ничем.

С математической точки зрения это выглядит так:

T1*...*Tn -> REC, где T1,...,Tn - типы данных.

Интересно, что в скриптовых (интерпретируемых) ЯП разница между массивом и записью стирается. Например, в Java-скрипт есть понятие записи. Пусть Х - запись; i,j - ее поля. Тогда можно писать X.i;X.j. Также есть понятие массива. В массиве можно индексировать элементы (например, a[1]).

Синтаксис скриптовых языков расширен следующим образом: можно писать X["i"]. Это означает, что, если Х - запись, то интерпретатор ищет в ней поле i и X["i"] эквивалентно X.i.

Разумеется, это удобно реализуется только на интерпретируемых ЯП. С точки зрения компиляции это не очень удобно, т.к. компилятор знает распределение памяти. Компилятор знает адрес Х, знает относительное смещение поля i, поэтому адрес объекта X.i компилятор легко вычислит.

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

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

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

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

В большинстве языков есть возможность прямого управления представлением соответствующих данных. Например, в языках С/С++ для целочисленных переменных типа запись допустимо int i:8; где 8 - количество битов, необходимых для представления числа.

В этом случае все переменные пакуются в машинное слово побитово.

Если int i:8; int j:3; int k:5;

то i - это первый байт числа,

j - это следующие 3 бита,

к - это остальные 5 битов.

В этом случае компилятор под всю структуру отведет ровно 16 битов.

Это сделано для максимальной эффективности хранения данных, доступа.

Если забыть про эффективность, то появляется возможность выбора.

Во-первых, можно сделать имена вычисляемыми (как описано выше).

Во-вторых, можно пойти дальше. В динамическом массиве разрешается пополнение полей элементов. Например, в Java-скрипт можно писать X[10]= е;

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

Тоже самое можно обобщить и на понятие записи: X["NAME"] = е;

Если в записи Х нет поля NAME, то оно добавляется, и в это поле заносится е.

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

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

Лекция 10

Записи и массивы.

Вспомним, что ТД определяется прежде всего операциями, которые можно выполнять с этим ТД.

Какая основная операция применима к массиву?

Это двуместная операция индексирования - операция от двух аргументов (массив и некоторое выражение) - М [l] или [ ](М, l)

Операция индексирования дает ссылку на тип элемента массива.

Пусть М - массив элементов типа Т, тогда М [l] дает Т &.

Какова основная операция, применимая к записям?

R.f или .(R, f). Эта операция тоже дает Т &.

В чем же разница записи и массива?

• Тип возвращаемого элемента для различных полей записи может быть разный; для массива это не так.

• (более существенное отличие) Связывание операции индексирования с соответствующими параметрами происходит динамически ( в отличие от операции доступа к элементу записи, которая происходит в современных ЯП статически).

Во всех языках, где есть массивы и записи, к ним применима операция присваивания.

В некоторых языках к массивам применимы операции сравнения (>,<,= =,!=).

Например, в языке Ада введено понятие сравнения записей и массивов.

Если записи принадлежат к одному типу, и ко всем полям этого типа применима операция сравнения, то операция сравнения применима и к самой записи.

То же самое верно и для массивов. Если массивы принадлежат одному и тому же типу, имеют одну и ту же длину, и к базовому типу массива применима операция сравнения, то операция сравнения применима и к массиву. Обычно в большинстве ЯП такой способ не употребляется.

Характеристики

Список файлов лекций