АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Хранение непрямоугольных массивов

Формулу (3.10) можно рассматривать как частный случай метода Айлифа (Iliffe), применимого и для непрямоугольных массивов. Рассмотрим этот метод на примере.

Пример 3.18. Представление непрямоугольного массива На рис. 3.12 справа показан трехмерный непрямоугольный массив T, размещенный в памяти при более быстром возрастании правого индекса.

Этот массив по своему строению аналогичен матрице Y из примера 3.16, но является трехмерным. Его можно представить себе в виде параллелепипеда, у которого некоторые углы “вырезаны”, причем неправильным бессистемным образом.

Обозначим индексы массива буквами i, j, k. Индекс i изменяется от 2 до 3. При i=2 индекс j пробегает значения от –1 до 1, а при i=3 индекс j изменяется уже в другом диапазоне: от 1 до 2. Пределы индекса k также зависят от значений других индексов, например, при i=2 и j=-1 индекс k изменяется от 1 до 2, а при i=2 и j=0 уже в другом диапазоне: от 0 до 2 и т.д.

Слева на рис. 3.12 изображены “ векторы Айлифа ”, образующие древовидную структуру ссылок для доступа к элементу массива троекратным применением формулы (3.9) подобно (3.10).

i j k

k=0 ┌ ─ ─ ┐

┌───→│ │

│ ├─────────┤

j │ │T[2,-1,1]│

┌─┬─┬─┐ │ ├─────────┤

-1│1│2│ ┼─┘ │T[2,-1,2]│

j=0 ├─┼─┼─┤ ├─────────┤

i ┌─→ 0│0│2│ ┼─────→│T[2, 0,0]│

┌─┬─┬─┐ ┌ ─ ─ ┐ │ ├─┼─┼─┤ ├─────────┤

T│2│3│ ┼───→0│ │ │ 1│1│1│ ┼─┐ │T[2, 0,1]│

└─┴─┴─┘ ├ ─ ─ ┤ │ └─┴─┴─┘ │ ├─────────┤

1│ │ │ └───→│T[2, 0,2]│

├──┬─┬─┤ │ ├─────────┤

2│-1│1│ ┼─┘ j ┌──→│T[2, 1,1]│

├──┼─┼─┤ ┌ ─ ─ ┐ │ ├─────────┤

3│ 1│2│ ┼────→0│ │ │ │T[3, 1,1]│

└──┴─┴─┘ ├─┬─┬─┤ │ ├─────────┤

1│1│2│ ┼──┘ │T[3, 1,2]│

├─┼─┼─┤ ├─────────┤

2│0│1│ ┼─────→│T[3, 2,0]│

└─┴─┴─┘ ├─────────┤

│T[3, 2,1]│

├─────────┤

Рис. 3.12. Векторы Айлифа для непрямоугольного массива

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

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

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

Векторы Айлифа можно рассматривать как еще один пример древовидной таблицы, отличающейся от дерева бинарного поиска (раздел 5.5). Ключом служит набор индексов. Каждый индекс образует как бы "цифру" ключа и такую таблицу можно назвать деревом цифрового поиска. Идею цифрового поиска можно применять и для текстового ключа, роль "цифр" которого играют его символы.

Разреженный массив, большинство элементов которого равны одному и тому же значению (например, 0) и лишь немногие "значащие" элементы отличаются от него, хранят в виде таблицы "значащих" элементов. Ключом служит набор индексов. Здесь могут быть удобными сети и списковые структуры.

В следующем разделе рассматриваются методы работы с другими нестандартными массивами, в частности, с упакованными массивами, хранимыми по несколько элементов в ячейке (см. также пример 1 из раздела 3.4).

Дата добавления: 2015-09-27 | Просмотры: 476 | Нарушение авторских прав