Непейвода Н.Н. Программирование. Раздел 4

Непейвода Н.Н. Программирование. Страница 422

Чтобы полностью специфицировать значение типа массив, нужно ука­зать для каждого элемента В значение из К. Этот выбор делается независимо для каждого элемента массива. В результате

Таким образом, при представлении моделируемых объектов массивами за­даются все значения для всех индексов, тогда как это может противоречить реальности (массив дней месяца).

Не следует путать последнее с так называемыми разреженными мас­сивами, у которых для большинства элементов принимается стандартное значение (как правило, 0; пример — диагональная матрица), либо большин­ство элементов не используется (случаи, подобные дням месяца, — это из­держки неадекватности абстрактной структуры конкретному содержанию).

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

Примером такого представления может служить решетчатое представле­ние (см. рис. 9.7).

Примером представления, подходящего для ассоциативных массивов, яв­ляется ключевое представление, когда по индексу вычисляется ключ, а уже по ключу размещается значение (см. рис. 9.8). Здесь двойная стрелка озна­чает один из вариантов представления записи

(<ключ, если для него есть компоненту К\),

которая в ключевом представлении заменяет исходный компонент разрежен­ного массива.

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

выбор нужной компоненты в новом наборе (логически это снова массив, но уже плотный) и

извлечение К^ из записи (второе поле).

Старый индекс для такого представления называется ключом, а порядковые номера компонентов нового набора — индексами записей нового набора.

При ключевом доступе возникает задача контроля целостности: в но­вом наборе не должны появляться записи с одинаковыми ключами, и нуж­но контролировать, не нарушается ли упорядоченность ключей. Ключевое представление можно рассматривать как следующий, по отношению к ис­ходному массиву, уровень абстракции (более нижний, реализационный), ко­торый, в свою очередь, допускает различные реализации двухступенчатого доступа. Указанная запись может представляться стандартным способом, со свободной упаковкой (реже) или с использованием ссылок (очень часто). С учетом упорядоченности ключей (обычное свойство для ассоциативных массивов — см. выше) целесообразно предложить организацию индексов, приспособленную для дихотомического поиска. Здесь возможны варианты:

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета &quot;Ангара-А5В&quot; в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие &quot;Крокодилы&quot;

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама