AOP_Tom1 (1021736), страница 85
Текст из файла (страница 85)
Например, рассмотрим <ледую- шую матрицу размера т х и: А[1, Ц А[2,Ц А[1,2] ... А[1,п] А[2,2] ... А[2,п] А[гп,Ц А[т,2] . А[т,п] В этом двумерном массиве каждый узел А [у, А] принадлежит двум линейным спискам: списку "строки у" А[],Ц,А[1,2],...,А[],п] и списку "столбца Й" А[],Й], А[2,А].....А[т, А]. Такие ортогональные списки строк и столбцов и образуют двумерную структуру матрицы. Аналогичные замечания относятся и к многомерным массивам данных. (2) ЬОС(А[1.К]) = во + агЗ+ агК, где ао, аг и аг — константы. Рассмотрим более общий случай: предположим, что имеется четырехмерный массив элементов длиной в одно слово Ц[1,Л,К,Ь], где 0 < 1 < 2, 0 < Л < 4, 0 < К < 10, 0 < Т.
< 2. Память следовало бы распределить таким образом, чтобы (3) ЬОС(ЦЕ1, Т,К.Т ]) = ао + аг1+ агЛ+ азК+ аэЬ. Это значит, что изменение 1, Л, К или Ь сразу же приведет к вычислению изменения адреса элемента Ц[1,З,К,Ь]. Наиболее естественный (и наиболее распространенный) способ распределения памяти заключается в упорядочении элементов согласно лексикографическому порядку их индексов (упр. 1.2.1 — 15(д)), который иногда называют "упорядочение по строкам": ЦЕО„О,О,О], ЦЕО,О.О,Ц, ЦЕ0,0,0,2], Ц[0,0,1,0], Ц[0,0,1,1], ..., Ц[0.0.10,2], ЦЕО,Т,О,О],, Ц[0,4,10,2], ЦП,О,О,О], ..., () Е2,4,10,2]. Нетрудно видеть, что этот порядок удовлетворяет требованиям (3) и может быть выражен так: 1ОС(ЦП,.Т,К,Ь]) = ТОС(ЦЕО,О,О,О])+1651+331+ ЗК+1..
(4) Вообще, А-мерный массив с элементами А Пг,1г,...,Тг] длиной с слов при 0<1г <с(ы 0<1г<Нг,, 0<1г <Но может храниться в памяти в виде ЬОС(А Пг, 1г, 1г] ) = Т.ОС(А[0,0,...,03) +с(с~г+1)... (Ну, .+1)1г+ +с(Иг+1)1г г+с1г = ЬОС(АЕО,О,...,О]) + ~~ а„1„ (5) 1(г(г где а„ = с Ц (Н, + 1) (6) тсзйь Для доказательства этой формулы заметим, что а, †э объем памяти, необходимой для хранения части массива АП, „ ..., 1„, Л,~,, ...,Лг], где 1ы ..., 1„ †константы, а Т„эы...,ЗА изменяются для всех 0 < Л,+г < ат,+ы, 0 < Зг < аг. Следовательно, по определению лексикографического порядка адрес АПм..., 1ь] будет изменяться точно на эту величину при изменении 1„на единицу. Формулы (5) и (6) соответствуют значению числа 1~ 1г... 1ь в системе счисления со смешанным основанием (ппхефгаойх ппшЪег эуггеш).
Например, для массива Т1МЕ[ТТ,Р,Н,М,Я] с 0 < Н < 4, 0 < Р < 7 0 < Н < 24, 0 < М < 60 и 0 < Я < 60 адрес элемента ТХМЕЕН,Р„Н,М,Я] будет равен адресу ТТМЕ[0,0,0,0,0] плюс величина "Н недель + Р дней + Н часов + М минут + Я секунд" в секундах. Конечно, массив с Последовательное распределение. Когда массив хранится по последовашельно расположенным адресам, память обычно распределяется так, чтобы 2 419 200 элементамн может понадобиться только для очень экзотического приложения. Традиционный метод хранения массивов обычно подходит только для массива с полностью прямоугольной структурой, в которой все элементы А[1г,1г,...,1ь] имеют индексы в независимых диапазонах 1г < 1г < иг, 1г < 1г < иг, 1ь < 1ь < иы В упр.
2 показано, как можно адаптировать формулы (5) и (б), когда нижние границы (1ы 4,...,1ь) не равны (О, О,..., 0). Однако во многих случаях массив не является прямоугольным. Чаще всего он представляет собой шреугольную маглрицу, в которой хранятся только элементы АЦ,Й], например, для 0 < А < у < и: А[0,0] А[1,0] А[1, Ц (7) А[п,О] А[п„ц ... АЕп,п] Как правило, известно, что все остальные элементы матрицы равны нулю или А[),А] = АЕА,)], так что достаточно хранить в памяти всего лишь около половины всех элементов матрицы. Для хранения нижней треугольной матрицы (7) в г (и+ 1)(я+ 2) последовательных позициях памяти следует отказаться от линейного распределения памяти (2) и использовать распределение в виде (8) ВОС(А[Я,К]) = по+ Л(Л) + Уг(К), где Д и г'г — функции одной переменной.
(Константа ао может быть включена в функцию ~~ или 6.) Если способ адресации имеет вид (8), доступ к произвольному элементу А Е), й] можно достаточно легко осуществить с помощью двух (очень коротких) вспомогательных таблиц со значениями ~~ и уг. К тому же эти функции потребуется вычислить только один раз. Причем лексикографнческий порядок индексов массива (7) удовлетворяет условию (8), а для элементов длиной в одно слово получим простую формулу 10С(А[Я,К]) = 1ОС(А[0,0]) + + К. .)(1+ 1) 2 (9) Однако существует более эффективный способ хранения треугольных матриц одного и того же размера.
Предположим, что нужно сохранить две матрицы А [], Й] н В[),к], где 0 < к < ] < п, Тогда их можно свести к одной матрице с[у, А], где 0 < у < п, 0 < )г < п + 1, используя условие (10) В[,,А] =СЕВ,,л ц. Таким образом, получим СЕО,О] С[О,Ц С[0,2] ... С[О, +Ц В[п,О] В[п, Ц А[0,0] В[0,0] В[1,0] АП,О] А[1,Ц В[1, Ц С[1,0] СЕ1,ц С[1,2] ..С[1,п+ц В[п,п] С[п,О] С(п,ц С[п,2] ..С[п,п+ц А[п,О] А[п,ц А[п,2] в (и + 1)(п + 2) Так, две треугольные матрицы могут быть компактно упакованы ячейках памяти с линейной адресацией типа (2). Обобщение треугольных матриц для больших измерений называется тетраэдральным массивом (ье1гайеЫшь ассар).
Рассмотрение этой интересной темы продолжается в упр. б — 8. Типичные приемы программирования при работе с последовательно адресуемымн массивами описаны в упр. 1.3.2 — 10 и в двух ответах к данному упражнению. Особенно интересными в этих программах являются фундаментальные методы эффективного обхода строк и столбцов, а также использование последовательных стеков. ьь Женщина, 2Ь год, карие глаза, темные волосы Мужчина, 24 года, карие глаза, темные волосы Женшина, 22 года, зеленые глаза, светлые волосы Мужчина, 28 лет, сеетло-карие глаза, светлые волосы Женщина, 22 года, голубые глазе„рыжие колосы Женщина, 2! год, голубые глаза, светлые волосы РИВИОИ 161 Риььвои161 Риавои 161 РЕИЗОВ[31 Риивои 121 РВВВОВ111 Рис.
13. Каждый узел находится в четырех различных списках. В качестве примера использования связанного распределения памяти для прямоугольных списков рассмотрим раэреэьсенные матрицы (ярагяе та1гзсея) (т. е, матрицы большого размера, в которых большинство элементов равно нулю). Назначение задачи — организовать работу с такими структурами, как с обычной матрицей, Связанное распределение. Связанное распределение памяти прекрасно подходит и для представления многомерных массивов данных.' Вообще, узлы могут содержать й полей связи, по одному для каждого списка, которому принадлежит этот узел. Связанное распределение памяти обычно используется в <шучаях, когда массивы данных не строго прямоугольны.
В качестве примера рассмотрим список, в котором каждый узел представляет описание некоторого человека, с четырьмя полями связи для обозначения: пола ЯЕХ, возраста АСЕ, цвета глаз ЕХЕЯ и цвета волос НА1й. Например с помощью полей ЕУЕЯ связываются узлы с одним цветом глаз и т. д. (рис. 13). Тогда нетрудно представить эффективный алгоритм вставки в этот список узлов с описаниями новых людей. Операция удаления в такой структуре будет выполняться гораздо медленнее, но ее эффективность можно повысить, используя двансды связанные списки.
В таком случае можно представить алгоритмы с разной степенью эффективности для выполнения, например, таких запросов: "Найти всех голубоглазых блондинок в возрасте от 21 до 23 лет" (см. упр. 9 н 10). Подобного рода задачи, в которых узлы одного списка могут принадлежать нескольким другим спискам, встречаются довольно часто. Действительно, описанная в предыдущем разделе модель работы лифта содержит узлы, которые находятся сразу в двух списках: ЦНЕЯЕ и ЧАХь. но достичь при этом большой экономии времени и пространства в памяти за счет исключения из нее равных нулю элементов. Один способ организации произвольного доступа к элементам атой матрицы заключается в использовании методов хранения т и извлечения данных, которые описаны в главе 6, т.
е. поиск элемента А[у „кз выполняется на основе ключа "[1, /с]". суп1ествует, однако, еще один способ работы с разреженными матрицами, который часто более предпочтителен, поскольку он точнее соответствует структуре матрицы. Именно этот метод будет рассмотрен ниже. Рассматриваемое здесь представление состоит из циклически связанных списков, т. е. циклически связанных строк и столбцов. Каждый узел матрицы имеет длину в три слова н содержит пять полей: Здесь ВОЧ и СОŠ— индексы, обозначающие строку и столбец узла; ЧАŠ— значение, хранимое в элементе матрицы; АЛЕЕТ н ОР— связи со следующим ненулевым элементом стева в строке или сверху в столбце соответственно.
Для каждой строки и каждого столбца заданы заголовки списков ВАЯЕВОМ [П н ВАЯЕСОЕ[у3 соответственно. Эти узлы идентифицируются благодаря следующим условиям: С01.(1ОС[ВАЯЕВОЧ[з])) < 0 и ВОУ[ЕОС[ВАЯЕСОЕ[Д)) < О. Как обычно, в циклическом списке ссылка ЕЕРТ в строке ВАЯЕВОМ[П является ад- ресом крайнего справа значения в этой строке, а ссылка УР в строке ВАЯЕСОЕ [13 указывает на последнее значение в столбце. Например, матрица 50 0 0 0 10 0 20 0 0 0 0 0 — 30 0 — 60 5 [12) при таких условиях будет иметь вид, приведенный на рис. 14. При использовании метода последовательного распределения памяти для матрицы размера 200 х 200 потребуется 40 000 слов, что гораздо больше размера оперативной памяти большинства компьютеров.
Но для представления умеренно разреженной матрицы размера 200 х 200 с помощью описанного выше способа в оперативной памяти компьютера М11 потребуется только 4 000 гтов (см, упр, 11). При этом время доступа к произвольному элементу А [1, Ц также будет вполне приемлемым, если в каждой строке н каждом столбце содержится немного ненулевых (или неодинаковых) элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
