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

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

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

11.2.1 Схемы хранения для матриц общего вида

Пусть дана матрица А₅ общего вида с ненулевыми элементами.

a₂₁ , a₄₁ , a₅₂ , a₁₃ , a_{33 ,} а₂₄, a₄₅

В последующих трех схемах матрицы хранятся по столбцам.

Схема 1 Каждому ненулевому элементу матрицы соответствует запись, занимающая две ячейки памяти. Первая ячейка содержит номер строки, вторая - значение элемента. Нуль в первой ячейке означает конец данного столбца. Нули в обеих ячейках указываются на конец массива, хранящего матрицу. Таким образом, общее число записей равно n+  +1, из них n - для столбцов,  - для ненулевых элементов матрицы А и одна запись - для указания конца матрицы. Так как каждая запись использует две ячейки памяти, то для хранения матрицы А потребуется 2(n++1), ячеек. Матрица А₅, для которой =7 и n=5 будет храниться в виде массива.

0, 1, 2, a₂₁ , 4, a₄₁ , 0, 2, 5, a_52, 0, 3, 1, a₁₃ , 3, a₃₃ ,0, 4, 2, a₂₄, 0, 5, 4, a₄₅, 0, 0

Схема 2. Информация о данной матрице хранится в трех массивах:

VE- значений ненулевых элементов,

RI - индексов строк

и CIP -указателей индексов столбцов.

Элемент RI() (- элемент массива RI) - cодержит индекс строки -го элемента VE - VE( ). Если первый ненулевой элемент  - го столбца данной матрицы размещается в VE (t_), то t_ хранится в  -м элементе CIP, т.е.

CIP( )= t_. Очевидно, VE и RI состоят из  элементов, а CIP из n элементов. Следовательно, эта схема требует общее число в 2+n ячеек.

Матрица А₅ будет храниться следующим образом:

VE=( a₂₁ , a₄₁ , a_52, a₁₃ , a₃₃, a₂₄, a₄₅ )

RI=(2, 4, 5, 1, 3, 2, 4)

CIP=(1, 3, 4, 6,7) (Указатель индекса столбцов)

Вышеизложенной схемой легко пользоваться. Например, a₃₃ может быть найдено следующим образом. Так как CIP(3)=4, RI(4)) даст индекс строки первого ненулевого элемента третьего столбца.

Если a₃₃0, RI(4) или один из следующих за ним элементов RI, предшествующих первому ненулевому элементу четвертого столбца, должен быть равен 3. В нашем случае RI(5) =3, так как VE(5) cодержит a₃₃.

Схема 3. Каждому ненулевому элементу данной матрицы однозначно ставится в соответствие целое число (i,j) вида:

(i,j)=i+(j-1)n a_ij0

Хранение ненулевых элементов обеспечивается двумя массивами:

VE- значений ненулевых элементов и LD , в каждом из которых содержится  элементов. (Память, понятно, потребуется 2 ячеек)

В LD() находится (i,j), соответствующее a_ij из VE(), где  =1, 2, ...,  .

Матрица А₅ хранится в виде:

VE=( a₂₁ , a_41, a₅₂ , a₁₃, a₃₃, a_24, a₄₅)

LD=(2, 4, 10, 11, 13, 17, 24)

Исходная матрица может быть восстановлена по этой схеме хранения следующим образом. В соответствии с данным выше определением (i,j) является очевидным, что j есть наименьшее целое число, большее ли равное и i= (i,j)-(j-1)n.

Например, если (i,j)=LD.(5)=13, тогда и наименьшее целое число, большее или равное будет 3.

Следовательно: j=3 и i=2(i,j)-(j-1)n=13-10=3.