Разряженные матрицы. Р. Тьюарсон (984138), страница 3
Текст из файла (страница 3)
Использование связных снискав ари упаковке Одним из способов хранении ненулевых элементов данной разреженной матрицы А является использование связных списков Каждому ненулевому элементу аи соответствует в памяти запись. Записи хранятся по столбцам— элементу аи будет соответствовать некоторая запись 1-го столбца матрицы (рис. 1.3.1) Каждая зались представляет собой упорядоченную тройку значений (1, а, р), где ! — номер строки, а — значение элемента а„и р — адрес следующего ненулевого элемента 1-го столбца.
Значение р равно нулю, если запись соответствует последнему ненулевому элементу столбца. Память для хранения всей матрицы состоит из.двух частей: ВС-памяти для начальных адресов столбцов и 51-памяти для записей. Первая часть (ВС) является массивом из н последовательно расположенных ячеек, содержащих адреса записей первых ненулевых элементов соответствующих столбцов. Например, 1-я ячейка ВС содержит адрес Я!(и) записи, соответствующей первому ненулевому элементу !'-го столбца (рис. 1.3,2).
Вторая часть (3!) состоит нз 1.3. Упакованная форма хранения 19 записей, связанных с ненулевыми элементами матрицы А. Так как матрица А содержит т ненулевых элементов и каждому из них соответствует запись, включающая три параметра, то Ы потребует для Пе хепх Рис. 1.3.1. Запись, соответствующая а своего хранения Зт ячеек, не обязательно непрерывно следующих друг за другом.
Таким образом, если мы применяем связные списки, то для хранения матрицы А в упакованной форме потребуется объем памяти в и-~ Зт ячеек. 312с1 3С Рнс. 1.3.2. Связный список в упакованной форме хранения. Главное преимушество такой схемы хранения заключается в том, что новые ненулевые элементы, образующиеся в столбцах в процессе вычислений, могут быть легко размещены в Ы. Для этого нет необходимости смещать все последующие элементы, как это имеет место в обычных схемах хранения, когда производится вставка нового элемента.
Более того, все записи в Ы не обязательно должны быть сосредоточены Гл. 1. Предварительнмв сведения в одной области памяти, а могут быть разбросаны по всей доступной оперативной памяти ЭВМ (группами ячеек, число которых кратно 3). Приведем простой пример, показывающий, каким образом появление нового ненулевого элемента влияет на ВС и 8!. Предположим, что аы —— ааа = О, пав = 0,5 и а4а — — 1,5. Пусть ВС размещается в памяти ЭВМ начиная со 101-й ячейки, а записи для ааа и аса начинаются с 200-й и 203-й ячеек соответственно.
Если в дальнейшем ааа вместо нуля принимает ненулевое значение (ркажем, 2,5) и запись для ааа должна быть размещена начиная с 300-й ячейки, то необходимые изменения в памяти могут быть представлены следующим образом: Адреса 103 200 201 202 203 204 300 301 302 Текущее содержи- 200 2 0,5 203 4 1,5 мос ячеек Новое содержи- 200 2 0,5 300 4 1,5 3 2,5 203 мос ячеек Таким образом, включение нового ненулевого эле. мента потребовало только изменения содержимого 202-й ячейки в списке, отражающем текущее состояние матрицы.
Если вместо элемента ам ненулевым стал бы элемент ам (пусть„например, 3,5) и соответствующая ему запись хранилась (как и в прсдыдущем случае) начиная с ячейки 300, то мы имели бы: Адрес 103 200 201 202 203 204 300 ЗО! 302 Текущее ' содер- 200 2 0,5 203 4 1,5 жимос ячеек Новое содержи- 300 2 0,5 203 4 1,5 1 3,5 200 мое ячеек Как видно, и в этом случае для того, чтобы включить новый ненулевой элемент, в исходном связном списке необходимо изменить только содержимое одной ячейки. 21 1.8. Упакованная форма яранвния Если в процессе вычислений некоторые ненулевые элементы становятся равными нулю, то ячейки памяти, занятые записями, соответствующими этим элементам, освобождаются и могут быть использованы для хранения записей новых ненулевых элементов.
Начальные адреса таких освободившихся записей можно хранить в памяти в виде связного списка свободных записей, для чего использовать третьи ячейки каждой записи. Только начальный адрес первой свободной записи должен где-нибудь запоминаться отдельно. Третья ячейка каждой свободной записи должна содержать адрес следующей свободной записи.
Если данная свободная запись является последней в списке свободных записей, то третья ячейка должна сод ржать нуль. Когда освобождается новая запись, она присоединяется к началу списка. Аналогично для включения в список записей новых ненулевых элементов используются свободные записи, расположенные в начале списка свободных записей. Рассмотрим два простых примера, иллюстрирующих изложенные выше методы. Предположим, что свободными являются две записи с начальными адресами 10! и 201 и мы хотим добавить к списку еще одну свободную запись с начальным адресом 301.
Если ячейка 50 содержит адрес первой свободной записи, то требуемые изменения в содержимом ячеек памяти могут быть представлены следующей таблицей: 50 101 102 !ОЗ 201 202 20З 301 302 ЗОЗ Адрес Текушеесодержи- 101 — — 201 — — 0 иое ячеек Новое содержи- 301 — — 201 — — 0 — — 101 иое ичеек С другой стороны, для хранения новой записи ис. пользуется первая снободная запись в списке, а именно ячейки 301, 302, 303.
Затем изменяется содержимое ячеек таким образом, чтобы оно соответствовало строке таблицы, помеченной «Текущеесодержимое ячеек». Гл. Х Предварительные сведения Иногда полезны упаковки, не использующие связных списков. Для них требуется меньшая память, но добавочный ненулевой элемент может вводиться только путем сдвига всех следующих за ним элементов на одну запись. Эти схемы пригодны в тех случаях, когда только небольшая часть матрицы в процессе вычисле.
ний может храниться в оперативной памяти ЭВМ, и поэтому потребовалось бы значительное время для ввода и вывода данных при обращении к внешней па. мяти. Ниже описываются четыре такие схемы и для первых трех показывается, каким образом хранится матрица Аз с ненулевыми элементами азь аа, азь ам, азз, ам и ань Последняя схема предназначена для симметричных матриц, и поэтому она отличается от сГре дыдущих. В первых трех схемах матрицы хранятся по столбцам, а в последней — по строкам. Схема 1 Каждому ненулевому элементу матрицы соответствует запись, занимающая две ячейки памяти.
Первая ячейка содержит номер строки, вторая — значение элемента. Нуль в первой ячейке означает конец данного столбца. Вторая ячейка в этом случае содержит номер следующего столбца. Нули в обеих ячейках указывают на конец массива, хранящего матрицу. Таким образом, общее число записей будет равно и+ ,'+т+1, из них и — для столбцов, т — для ненулевых элементов матрицы А и одна запись — для указания конца матрицы. Так как каждая запись использует две ячейки памяти, то для хранения матрицы А потребуется 2(и + т + 1) ячеек.
Матрица Ам для которой т = 7 и и = 5, будет храниться в виде массива (0,1; 2,а„; 4,ан, 0,2; б,ам; 0,3; 1эаи, З,азз', 0,4; 2, аз~', О, 5; 4, аез, 'О, 0). Схема 11 Информация о данной матрице хранится в трех массивах: ЧŠ— значений ненулевых элементов, )т1— индексов строк и С1Р— указателей индексов столбцов.
дЗ, упакованная форма хранения Элемент И(а) — а-й элемент массива И вЂ” содержит индекс строки 4х-го элемента ЧŠ— ЧЕ(а). Если первый ненулевой элемент 5-го столбца данной матрицы размещается в ЧЕ(1В), то (а хранится в 5-м элементе С!Р, т. е. С1Рф) = (а. Очевидно, ЧЕ и И состоят из т элементов, а С1Р из н элементов. Следовательно, эта схема требует общее число в 2т+н ячеек. Матрица Ае будет храниться следующим образом; ЧЕ=(ахь ам, а„, ам, ахз, а,4, а44), И=(2, 4, 5, 1, 3, 2, 4), С1Р=(1, 3, 4, 6, 7). Вышеизложенной схемой легко пользоваться.
Например, ам может быть найдено следующим образом. Так как С1Р(3) = 4, то И (4) даст индекс строки первого ненулевого элемента третьего столбца, Если ам ~ О, то И(4) или один из следующих за ним элементов И, предшествующих первому ненулевому элементу четвертого столбца, должен быть равен 3. В нашем случае И(5) = 3, так как ЧЕ(5) содержит азз. Схема Ш Каждому ненулевому элементу данной матрицы однозначно ставится в соответствие целое число Х(1, 1') вида й(1, 1)=ю'+(1 — 1)а, ап Ф О.
Хранение ненулевых элементов обеспечивается двумя массивами; ЧŠ— значений ненулевых элементов и 1Р, в каждом из которых содержится т элементов. В ЕР(а) находится А(1, 1),.соответствующее ам из ЧЕ(а), где а = 1, 2, ..., т. Матрица Ав хранится в виде ЧЕ=(аеь аи, анн анн ахь а,4, а44), 1.Р=(2, 4, 1О, 11, 13, 17, 24).
Исходная матрица может быть восстановлена по этой схеме хранения следующим образом. В,соответ. Гл. Л Предварительные сведения ствин с данным выше определением Л(», 1) является очевидным, что ( есть наименьшее целое число, боль- Л(», 0 шее илн равное ', и ! = Л (!', /) — (1 — 1) и. Например, если Л(», 1) =.Е.Р(5) = 13,тогда — ' Л(», !) и 13 = — и наименьшее целое число, большее или равное — будет 3. Следовательно, 1 = 3 н ! = Л(»,1)— Л(! 0 п — (1 — 1) п = 13 — 10 = 3.
Схема е е' Если А — симметричная матрица, в которой для всех ! 1 а!» — — О, !' — ! > О„ где О» намного меньше п и в общем случае может иметь различные значения для каждого », то такая матрица называется симметричной ленточной матриией с локально изменяющейся »иириной ленть!. Подробное описание ленточных матриц дано в равд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
