LEC-26 (Материалы к лекциям)

7

В.А. Столярчук. “Моделирование систем”. Конспект лекций. Лекция №26

Лекция № 26

11.1.2. Использование связных списков при упаковке.

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

Номер строки i

Значение элемента a

Адрес следующей записи (нуль, если запись последняя) Р или 0

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

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

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

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

SI()

i

a

P

Вторая часть (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-й ячейки, то необходимые изменения в памяти могут быть представлены следующим образом:

Адреса			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-ой ячейки в списке, отражающем текущее состояние матрицы. Если вместо элемента a₃₃ ненулевым стал бы элемент a₁₃ (n-P, 3,5) и соответствующая ему запись хранилась (как и в предыдущем случае) начиная с ячейки 300, то мы имели бы:

Адреса			103		200	201	202	203	204		300	301	302
Текущее содержимое ячеек			200		2	0,5	203	4	1,5		-	-	-
Новое содержимое ячеек			300		2	0,5	203	4	1,5		1	3,5	200

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

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

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

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

Адреса		50		101	102	103		201	202	203		301	302	303
Текущее содержимое ячеек		101		-	-	201		-	-	0		-	-	-
Новое содержимое ячеек		301		-	-	201		-	-	0		-	-	101

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

11.2. Схемы, не использующие непосредственную адресацию (алгоритмические способы хранения разреженных матриц).

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

Хранение массивов, списков, стеков и очередей.

Как уже говорилось, массив – это простейшая структура данных. Примеры — А (I), В (I, J) и т. д. В массиве могут храниться просто числа. Другая возмож­ность: массив содержит указатели на элементы более сложной природы, хранящиеся в действительности где-то в другом месте. Все элементы массива доступны непосредственно за время, не зависящее от его размера. Однако следует иметь в виду, что ма­шинная память одномерна, а потому за использование двойных или кратных индексов приходится расплачиваться. Нужно за­метить также, что в машинах с виртуальной памятью массив может находиться на периферийном запоминающем устройстве и не быть легко доступным.

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

Линейный связный список — это последовательность ячеек, связанных в том или ином порядке. Каждая ячейка содержит элемент списка и указатель, сообщающий положение следующей ячейки. Например, предположим, что мы хотим хранить числа а, b, с и d в указанном порядке в массиве А (I). Схема хранения может выглядеть так (символом х отмечены несущественные для нас значения):

В массиве А (I) хранятся элементы списка, а в NEXT (I)— указатели позиций следующих элементов. Необходим еще ука­затель входа IP, показывающий расположение первого элемента. В данном случае он равен 5. В позиции 5 находим первый элемент А (5) — a, a NEXT (5) = 2 сообщает, что следующий элемент нужно искать в позиции 2, Этим путем можно просмотреть весь список. В последнюю ячейку должен быть помещен признак конца, указывающий окончание списка; в нашем примере таким признаком служит 0. Еще один способ состоит в том, чтобы хра­нить общее число элементов списка и с помощью этого числа опре­делять, когда список исчерпан. Пустой список удобно задавать, присваивая указателю входа значение, которое не может адресо­вать какую-либо позицию массивов, например неположительное число.

Элементы легко вставляются или удаляются в любом месте. Предположим, например, что между 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). В кольцевом списке элементы можно удалять или добавлять, не меняя порядка остальных, а свободные позиции связывать таким же образом, как в линейном списке.