Способы хранения и представления разреженных матриц, операции над ними. Блатов И.А - 23 стр.

                                  - 23 -

  На входе дана матрица    A(n ×m) в неупорядоченном РСФ. На выходе
                     T
  должны получить A - транспонированную матрицу, заданную в РСФ.
   З а м е ч а н и е. Если задано строчное представление матрицы А , то его
                                                             T
  можно рассматривать как столбцовое представление A и наоборот,
  поэтому задача транспонирования А сводится к нахождению РСТФ
  матрицы А .
  Если просматривать массивы «в лоб», то это очень неэффективно. Поэтому
  вводятся m целых и m вещественных списков длины n и m – указателей
  первой свободной позиции каждого списка. В начальный момент времени
  все списки пустые, т.е. первая свободная позиция каждого списка – первая.
  На практике списки организуются непосредственно в массивах JAT и
  ANT , а указатели первой свободной позиции каждого списка – в IAT .
  Таким образом, дополнительной памяти не требуется, и перемещение
  данных в памяти машины сведено к минимуму.

                           Алгоритм
  С помощью массивов      JA и IA          просматриваем по порядку   строки
  матрицы А .
  1. i =1 .
2. С помощью IA определяем, в каких позициях JA содержится описание
   i -й строки матрицы А .
3. Просматриваем содержимое i -й строки в JA и для каждого j (где j -
   столбцовый индекс просматриваемого элемента) добавляем число i в
   первую свободную позицию j -го целого списка, увеличивая при этом
   указатель первой свободной позиции списка на единицу. В
   соответствующую позицию         j -го вещественного списка добавляем
   соответствующий элемент списка АN .
4. i =i +1.
5. Объединяем по порядку их нумерации вещественные и целые списки,
   получаем списки JAT и ANT . Список IAT получается с помощью
   подсчета числа элементов заполняемых списков.
  Замечания
1. С помощью этого алгоритма получается упорядоченное представление
   транспонированной матрицы даже в том случае, если представление
   исходной матрицы было неупорядоченным.
2. Применение данного алгоритма к матрице А дважды позволяет получить
   из неупорядоченного РСФ матрицы А её упорядоченное представление.
  Задача 25. Транспонировать матрицу А из задачи 22 (номер списка – это
  номер столбца).
   вещественные списки               целые списки