Лекция 06 (1160806), страница 4

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

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

корректно. Здесь сразу же в скобках после имени типа мы уточняем диапазон индексов. Теперь компилятор знает соответствующий диапазон индексов. Теперь это переменная типа TArr, которую можно передавать как формальный параметр. Мы можем описать

Y: TArr(1..11);

Z: TArr(0..20);

Теперь возникает вопрос: являются ли переменные X, Y, Z переменными одного типа? Ответ – да, являются, поскольку имя типа у них одинаковое. Поэтому их и можно передавать в процедуру Р. Но естественно, что атрибуты Length, FIRST, LAST для всех этих ОД зафиксированы в момент объявления. Т.е. атрибуты Length, FIRST, LAST, Range являются статическими атрибутами для ОД. Но для неограниченных типов, объектами которых могут быть формальные параметры, соответствующие атрибуты Length, FIRST, LAST являются квазистатическими потому, что естественно атрибуты Length, FIRST, LAST не меняются в ходе выполнения процедуры P , но от вызова к вызову они меняются. И они являются нестатическими, но они и не настоящими динамические – типичный пример квазистатического атрибута, т.е. атрибут, который сохраняет свое значение на период выполнения некоторого участка программы. В результате у нас имеется полная гибкость работы с массивом. И, кстати, решена еще одна проблема, а именно коль скоро переменные X, Y и Z относятся к одному типу, следовательно, их вроде бы можно присваивать. Как интерпретировать присваивание

Z:=X;

И вот тут как раз приходит на помощь концепция типов и подтипов. Считается, что все переменные, которые описаны, как переменные неограниченного типа, но с указанием ограничения, относятся к разным подтипам одного и того же типа. Данные одного типа можно присваивать друг другу, но если данные относятся к разным подтипам, то тогда при присваивании происходит квазистатический контроль. Это мы обсуждали, когда обсуждали концепцию диапазона. Если диапазон объявлен как подтип какого-то базового дискретного типа, то объекты двух диапазонов можно друг другу присваивать – они же относятся к одному ТД, но при этом происходит квазистатический контроль, т.е. компилятор подставляет проверки, которые проверяют корректность этого присваивания.

То же самое верно и для массивов, т.е. с точки зрения компилятора в таком присваивании проблем нет – это один и тот же тип, но при этом компилятор проверяет: совпадают ли у них диапазоны. Правило следующее: если ОД массива относятся к одному ТД, тогда присваивание разрешено, но только для массивов, которые совпадают по атрибуту длина. Следовательно, объекту Х можно присваивать объект Y, и наоборот, поскольку они имеют одну и ту же длину, а конкретно 11 элементов. А вот Z присваивать Y, и наоборот, Y присваивать Z нельзя. При этом, поскольку речь идет об ОД - переменных, а у переменных атрибут длина статический, то компилятор может его проверить. Однако, если у нас есть процедура Р, у которой два параметра

procedure P(p1, p2: inout TArr)

Спрашивается: можно ли присваивать эти массивы?

…

begin

p1:=p2;

Ответ: поскольку они принадлежат одному и тому же типу данных, эти объекты присваивать друг другу можно. Поскольку они могут относиться к разным подтипам, и компилятор не знает к каким именно подтипам они относятся, он вставит здесь квазистатическую проверку, что если длина р1 = длине р2, тогда присваивание проходит, в противном случае - нет. Это та же самая квазистатическая проверка, которая имеет место при присваивании переменных диапазонного типа данных. Все то же самое. Но с другой стороны проблемы и надежности и гибкости в языке Ада решены. Более того, создатели языка Ада даже несколько расширили концепцию массива, а именно: добавили понятие динамического массива, который правда, с точки зрения нашей терминологии, динамическим не является. Настоящие динамические массивы – это массивы в таких языках как Java или C#. А то, что называется динамическим массивом в языке Ада – это частный случай понятия, а именно мы говорили о том, что у всех ОД в языке Ада атрибут длина и связанные с ним атрибуты обязаны быть статическими. Они могут быть объектами неограниченного типа данных, но при этом мы обязаны указывать конкретное уточнение с помощью константных выражений. Для локальных массивов допускается, чтобы атрибут длина был динамическим. Иначе говоря, мы можем написать какую-то процедуру, у которой есть формальный параметр N типа INTEGER, и объявив в теле А локальную переменную х

procedure A(N: INTEGER)

x: array(1..N) of T

begin

end A;

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

4) Современные ЯП применяют другой подход. Настоящие динамические массивы (ненастоящие динамические массивы – это массивы в языке Ада, которые на самом деле являются квазистатическими) имеются в языках C#, Java. И, кстати, понятием динамического массива в стиле Java, C# наряду с массивом из Турбо Паскаль обладает также язык Delphi. В этих языках длина является динамическим атрибутом ОД. Т.е. с каждым массивом хранится его длина. Как говорилось ранее, все массивы от 0 до N-1, поэтому никаких других атрибутов, кроме длины массива с ним хранить не надо. Как уже было сказано, массивы в этих языках ссылочные. Все ссылочные объекты реально размещаются в динамической памяти, и поэтому это настоящие динамические массивы. Они и в динамической памяти размещаются и их длина может постоянно меняться. Например на языке C# вполне можно написать

char[]s= new char[10];

потом соответственно описать

char[]s1= new char[20];

поработать с элементами этого массива, например

s[0]= s1[1];

ну и поработав можно сделать так:

s1= s;

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

s1.SetLength(50);

Это похоже на массивы, скажем, языка С и языка С++, которые мы отводим в динамической памяти используя постоянно процедуру realloc, т.е. это действительно настоящие динамические массивы. Но как следствие они имеют ссылочную структуру, поэтому присваивание

s1:= s2;

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

s1 s2

s1 ссылалось на один массив, s2 на другой массив символьных значений, то после присваивания

s1 s2

Если на этот массив никто больше не указывал, то тогда этот массив помечается как удаленный, и уйдет из динамической памяти тогда, когда менеджер динамической памяти сочтет это нужным. В случае, если нам нужно действительно копировать объект массива, то у нас есть специальные методы. В C# есть метод, который побитово копирует одну структуру в другую, создавая новые элементы этой структуры, а в языке Java есть метод, который называется

s.Clone();

и в частности для любых объектов, не только для массивов, но и для объектов любого типа метод Clone отводит новую копию объекта s. Подробнее к проблеме копирования мы вернемся когда будем обсуждать концепцию класса, а сейчас просто отметим, что программист, который начинает работать на языках Java, Delphi и C# должен представлять себе ссылочную природу массивов: присваивание одного массива другому – это просто присваивание ссылок, никакого реального копирования информации не происходит.

Осталось только обсудить несколько дополнительных проблем, связанных с массивами. Какие еще навороты могут быть связаны с массивами? Т.е. первая проблема – это проблема самая главная – динамичности атрибута длина, которую мы как раз и обсуждали. Вторая проблема – это проблема индексов. Как мы видим современная тенденция такова, что атрибут длина становится полностью динамическим, а индексы, наоборот, упрощаются, от 0 до N-1.

И еще одна проблема, связанная с массивами – это многомерные массивы. Обычно многомерные массивы - это все равно сплошной кусок памяти, в котором массивы размешаются по строкам. Единственный язык, который не соблюдает этого правила, в котором массивы в памяти расположены по столбцам, это язык Фортран. Создатели Фортрана почему-то решили размещать по столбцам, но во всех остальных ЯП без исключения применяется вот такая схема

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

можем ли мы, вычленить из этой матрицы подматрицу? Например, можем ли мы взять отдельно строку этой матрицы, или столбец этой матрицы или какой-то прямоугольный элемент этой матрицы. Вот с точки зрения сечений из языков которые мы рассматривали, сечения в ограниченном виде существуют только в языке Ада. В Аде можно взять непрерывное сечение одномерного объекта. Если у нас массив описан А(0..10) мы можем написать нечто типа А(2..5) и это будет подмассив. Считается, что он является подтипом типа А, с такой уменьшенной длиной. Это частный случай сечения. Более мощные сечения есть в языке Фортран 90. Т.е. в Фортран 90 можно вычислять произвольные прямоугольные сечения, причем в массивах произвольной размерности. Т.е. можно из куба, например, выделить некоторое прямоугольное подмножество, но понятно, что это связано прежде всего с накладными расходами. Но т.к. основная структура данных в языке Фортране 90 - это массив, то создатели Фортрана 90 проигнорировали в данном случае проблему с эффективностью во имя удобства. В других же ЯП сечений как таковых нет.

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

int[ ] a= new int[20];

Вот пример двумерного массива

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

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