6CAD-CAE-22 Хранение матриц (1014141), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Еще один способ состоит в том, чтобы хра­нить общее число элементов списка и с помощью этого числа опре­делять, когда список исчерпан. Пустой список удобно задавать, присваивая указателю входа значение, которое не может адресо­вать какую-либо позицию массивов, например неположительное число.

Элементы легко вставляются или удаляются в любом месте. Предположим, например, что между b и с нужно вставить число е. Предположим еще, что известно: ячейка 3 пуста, a b находится в позиции 2. Следующая процедура выполняет требуемую опе­рацию:

А (3) ← e

NEXT (3) ←NEXT (2)

NEXT (2) ← 3

Процедура удаления элемента (скажем, с из позиции 7 исходного связного списка) еще проще: NEXT (2) ← NEXT (7)

Разумеется, для выполнения этой процедуры необходимо знать, что элемент, предшествующий с, расположен в позиции 2, так что фактически она удаляет «элемент, следующий за b », а не сам с. Если нужно вставить или удалить элемент в самом на­чале списка, следует переопределить указатель входа. Вставка или удаление элементов не изменяет порядка, в котором хранятся остальные элементы.

Если список хранится в массиве, важно иметь информацию о свободных позициях последнего. Обычно их также связывают в список, что требует еще одного указателя входа. Очевидно, что оба списка не пересекаются и потому могут быть хранимы в одних и тех же массивах. Нижеследующая структура данных получится, если связать свободные позиции в нашем примере (IE — указа­тель входа для нового списка):

позиция	1	2	3	4	5	6	7	8
A(I)		b		d	a		c
NEXT(I)	3	7	6	0	2	8	4	0
IP	5
IE	1
Признак конца	0

Процедуры вставки или удаления элемента теперь несколько усложняются (просмотреть их самостоятельно).

Связный список становится кольцевым связным списком, если в его последнюю позицию вместо признака конца поместить указатель на начальную позицию. У кольцевого списка нет ни начала, ни конца, но он все же требует хранимого отдельно ука­зателя входа, который теперь может указывать на любую занятую позицию. В нашем примере было бы NEXT (4) = 5, так что а следует за d; указатель входа мог бы иметь значение 7, что соот­ветствовало бы списку с, d, a, b. Кольцевые списки не требуют признака конца. Окончание списка распознается благодаря тому, что 7 — значение указателя входа — повторяется в NEXT (2). В кольцевом списке элементы можно удалять или добавлять, не меняя порядка остальных, а свободные позиции связывать таким же образом, как в линейном списке.

Двунаправленный связный список, линейный или кольцевой, получится, если ввести еще массив, содержащий для каждой ячейки адрес предыдущей ячейки. Двунаправленный список можно просматривать в обоих направлениях; он имеет то достоин­ство, что можно вставить или удалить элемент, не зная позиции предыдущего элемента. Линейный двунаправленный список тре­бует двух указателей входа: один указывает начало списка, дру­гой — его конец. Для кольцевого двунаправленного списка до­статочно одного указателя входа. Свободные позиции двунаправ­ленного списка можно связать между собой, хотя для этой цели редко бывает нужен новый двунаправленный список.

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

Очередь — это список элементов, хранимых в последовательных позициях, причем включение элементов производится через на­чало очереди, а исключение — через ее конец. Для указания позиций начала и конца очереди используются два указателя. Пустая очередь опознается благодаря тому, что для нее значение указателя конца на единицу больше значения указателя начала. Для очереди с единственным элементом зна­чения обоих указателей совпадают. Если участок памяти, отве­денный для хранения очереди, исчерпан, то новые элементы можно записывать в начало этого участка, закольцевав тем самым оче­редь; при этом начало очереди не должно пересекаться с ее концом. Все описанные схемы хранения опираются на массив как един­ственную структуру данных, поддерживаемую Фортраном. Эле­гантные свойства связных списков можно эффективно реализо­вать, используя и такую структуру данных, как запись, допускае­мую, например, языками Паскаль и Алгол. В этом случае не требуется косвенной адресации и память может распределяться динамически ценой некоторых системных затрат памяти.

Теперь рассмотрим связные списки с непосредственной адресацией

Каждому ненулевому элементу a_ij. соответствует в памяти запись. Записи хранятся по столбцам - элементу a_ij. будет соответствовать некоторая запись j-го столбца матрицы.

Каждая запись представляет собой упорядоченную тройку значений (i, a, Р ),

где i - номер строки, a - значение элемента a_ij и P - адрес следующего ненулевого элемента j-го столбца. Значение P=0, если запись соответствует последнему ненулевому элементу столбца. Память для хранения всей матрицы состоит из двух частей:

ВС - памяти для начальных адресов столбцов и SI-памяти для записей. Первая часть (ВС) является массивом из n последовательно расположенных ячеек, содержащих адреса записей первых ненулевых элементов соответствующих столбцов.

Например, j-я ячейка ВС содержит адрес SI() записи, соответствующий первому ненулевому элементу j-го столбца.

Вторая часть (SI) состоит из записей, связанных с ненулевыми элементами матрицы А. Так как матрица А содержит  ненулевых элементов и каждому из них соответствует запись, включающая три параметра, то SI потребует для своего хранения 3 ячеек, не обязательно непрерывно следующих друг за другом. Таким образом, если мы применяем связные списки, то для хранения матрицы А в упакованной форме потребуется объем памяти в n+3 ячеек.

Главное преимущество такой схемы хранения заключается в том, что новые ненулевые элементы, образующиеся в столбцах в процессе вычислений, могут быть легко размещены в SI. Для этого нет необходимости смещать все последующие элементы, как это имеет место в обычных схемах хранения, когда производится вставка нового элемента.

Более того, все записи в SI не обязательно должны быть сосредоточены в одной области памяти, и могут быть разбросаны по всей доступной оперативной памяти ЭВМ группами ячеек, число которых кратно 3. Приведем простой пример, показывающий, каким образом появление нового ненулевого элемента влияет на ВС и SI.

Пусть a₁₃=0 a₂₃=0,5 a₃₃=0 a₄₃=1,5

Пусть ВС размещается в памяти ЭВМ, начиная с 101 ячейки, а записи для a₂₃ и a₄₃ начинаются с 200 и 203 ячейки соответственно.

Если в дальнейшем a₃₃ вместо нуля принимает ненулевое значение (скажем, 2,5) и запись для a₃₃ должна быть размещена, начиная с 300-й ячейки, то необходимые изменения в памяти могут быть представлены следующим образом:

Таким образом, включение нового ненулевого элемента потребовало только изменения содержимого 202-ой ячейки в списке, отражающем текущее состояние матрицы. Если вместо элемента a₃₃ ненулевым стал бы элемент a₁₃ (n-P, 3,5) и соответствующая ему запись хранилась (как и в предыдущем случае) начиная с ячейки 300, то мы имели бы:

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

Характеристики

Список файлов лекций