Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 187

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 181 182 183 184 185 186 < 187 > 188 189 190 191 192 193 .. 316 >> Следующая

ип компонент.
9.3.
525
Если тип индексов всегда один и тот е (обчно отрезок целых неотрицательных, как в С/С++), то он может опускаться.
Массивы бывают статическими, динамическими и гибкими. Для статических массивов границ изменения индексов зада тся статически вычислимыми вра ениями (состояими из констант и переменных периода компиляции), для динамических массивов — выра ениями, значения которых должны быть вычислены до выполнения определения типа массивов. Про гибкие массивы говорят, что они имеют подвижные границы, т. е. такие, ко-торе могут изменяться в процессе оперирования с массивом.
одвиные границы чае всего указва тся специальнм слу ебнм словом. Если значение ниних границ всех массивов стандартизовано (в С/С++ это 0), оно опускается. В С/С++ задание верхней границы индекса массива — это указание границ безопасного обращения к элементам массива. В строгом смсле этого слова она границей не является, поскольку никакой оибки не будет, если индексное вра ение вйдет за указанный предел. оследнее в точности соответствует трактовке массивов как указателей на область памяти.
Массив есть таблично задаваемая функция, переводящая область индексов в область компонент. Если D — область изменения индексов (одномерная для векторов или многомерная в других случаях), а R — множество (область) значений компонент, то
M : D — R.
Точнее, это семейство функций, если иметь в виду возмо ность присваивать компоненте новое значение. Хоар эту операцию называет выборочным обновлением массива.
Как правило, в качестве имени этой функции (семейства функций) выби-ра т имя переменной типа массив.
Чтобы полностью специфицировать значение типа массив, нужно указать для каждого элемента D значение из R. Этот выбор делается независимо для каждого элемента массива. В результате
мощность^ — R) = мощность^)мощность('1)).
Таким образом, при представлении моделируемых объектов массивами зада тся все значения для всех индексов, тогда как это мо ет противоречить реальности (массив дней месяца).
526
ГЛАВА 9. СТРУКТУРЫ ДАННЫХ
е следует путать последнее с так называемыми разре еннми массивами, у которых для большинства элементов принимается стандартное значение (как правило, 0; пример — диагональная матрица), либо большинство элементов не используется (случаи, подобне дням месяца, — это издер -ки неадекватности абстрактной структуры конкретному содерани ). С абстрактной точки зрения разре енный массив ничем не отличается от обычного (чаще гибкого) массива. Поэтому было бы правильно (как в языке Java) не делать различий между ними при изображении массивов в программе. Различия появляются, когда выбираются представления массивов. Так, для диагональной матрицы (D) естественным представлением является вектор (Drep) со следующим доступом (i, j — индексные выражения):
D[i,j] = (i == j? Drep[i]: exception); Здесь exception — указание того, что с разными индексами D[i,j] употребляться не долна. Возмо но, что это присваивание в некоторых программах разумно трактовать как порождение новой матрицы (с тем же именем), но уже недиагональной.
ругой пример — симметричная матрица, котору , чтобы вдвое сократить расход памяти, стоит представлять вектором, содераим все элемент без дублирования (x — вра ение типа компоненты массива):
D[i,j] :
read(i,j) = (Sy (D,i,j )) =
if i > j then(Sy (D, j, i))
else(Sy (D rep,tf(i,j)); (9.4)
write(i, j,x) = (Sa(D, i,j) := x) =
if i>j then(SA(D,j,i) := x) else(SA(Drep, )) := x)
Здесь ip(i, j) — некоторая функция (зависящая от порядка, в котором представлены элементы матрице в векторе), которая вычисляет расположение того элемента матрицы (D) в векторе Drep.
В плане реализации доступа, смешивающего многомерные и линейные представления массивов, преуспел Фортран с его COMMON-блоками и оператором EQUIVALENCE.
аиболее распространенное представление массивов — такое, когда каждому элементу отводится одно или несколько машинных слов. Каждый элемент адресуется непосредственно. Это представление называется с андар -ным.
9.3. СТРУКТУРНЫЕ ТИПЫ
527
a
a[0]
a[1]
• • •
a[n]
Здесь и далее закраской выделена заполненная часть машинного слова; то, что осталось без закраски, — неинформативная часть (т. е. потери памяти).
Следующее представление называется представлением со свободной упаковкой:
a
a[0] a[1]
a[2] a[3]
...
a[n]
ковкой (см. рис. 9.5). Когда разрабатывается представление для массивов,
A 5]
A:
A[O] A[1] <
A[3] A[4]
A[6] A[7] J
' A 2]
A[n]
Рис. 9.5. Упакованное представление массива
компонента которых сами являются массивами, асто используется ссылочное представление (см. рис. 9.6).
В случаях разреженных и ассоциативных массивов нужно гораздо большее искусство выбора представлений. В обоих случаях надо учитывать, что со многими компонентами работа не производится. В случае разреженного массива к тому е заранее известно, что далеко не все компоненты массива фактически использу тся, а потому не ну но их хранить.
римером такого представления мо ет слу ить реетчатое представление (см. рис. 9.7).
Предыдущая << 1 .. 181 182 183 184 185 186 < 187 > 188 189 190 191 192 193 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100