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

                                 - 11 -

список B , который содержит все элементы списков      Ai ( i =1,..., n )   без
повторений (внутри каждого списка повторений нет).

    Задача 16. Слить три списка      А, B, С в один список М , где
А : 2, 7, 3, 5; B : 3, 11, 5; С : 7, 2.
     Список А записываем в М полностью, затем добавляем те элементы B ,
которых в А нет, потом элементы С , которых нет в А и B . Таким
образом, получим следующий список М : 2, 7, 3, 5, 11.
     Просматривать каждый раз список М , чтобы внести новый элемент,
нерационально. Поэтому вводится массив переключателей Y и переключатель
 p . Обычно p =1 .
     Число позиций массива переключателей должно быть равно
максимальному размаху сливаемых списков (в данной задаче 11). В начальный
момент во все позиции Y засылаем нули. Далее просматриваем первый из
сливаемых списков, и если очередной просматриваемый элемент равен i , то в
i -ю позицию массива переключателей засылается значение переключателя (то
есть 1). При просмотре каждого текущего элемента следующего списка (пусть
он равен j ) мы обращаемся к массиву переключателей и добавляем элемент j
в список M только в том случае, когда соответствующая позиция ”не
включена”, т.е. в позиции переключателя стоит ноль. Таким образом мы
просматриваем все списки.
     Для данной задачи массив переключателей будет следующим:
N позиции: 1 2 3 4 5 6 7 8 9 10 11
          Y : 0 0 0 0 0 0 0 0 0 0 0 в начальный момент
               0 1 1 0 1 0 1 0 0 0 0 после просмотра A
               0 1 1 0 1 0 1 0 0 0 1 после просмотра B
               0 1 1 0 1 0 1 0 0 0 1 после просмотра C
    3.1.3. Метод переменного переключателя (ПП)
    При обработке РМ приходится сливать несколько групп списков. В целях
экономии памяти используется только один массив переключателей (ЦМП),
число позиций которого равно порядку матрицы (или числу строк, или числу
столбцов).
    В соответствие с алгоритмом предыдущего пункта перед каждым новым
слиянием нужно было бы засылать во все позиции ЦМП нули, на что уходит
значительное число машинных операций. Для экономии вводят переменный
переключатель (ПП) p .
    Сначала    p =1 . Затем после каждого слияния группы списков p
увеличивается на единицу (т.е. p = p +1), что избавляет от необходимости
засылки нулей во все позиции ПП.