Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 55 стр.

            .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
                                    // элемента к сумме

                current=current->next;// переход на следующий
                                     // элемент списка
          }
          return s;
   }

    Задача 2. Пусть односвязный список содержит целые числа. Написать
функцию добавления нового элемента в список в заданную позицию. Эту же
функцию можно использовать для создания списка.
    При решении задачи можно выделить три частных случая добавления
элемента: вставка первого узла, вставка в середину и в конец списка. Если
происходит вставка первого узла, требуется изменить значение переменной
head. При вставке элемента в другую позицию требуется переместиться по
списку на элемент, предшествующий месту вставки. Например, если требует-
ся вставить элемент на пятую позицию, нужно переместиться на четвертый
узел списка. Затем перенаправить адреса согласно рис. 3.4.
    Пусть происходит вставка первого элемента. Сначала выделяем память
под хранение первого узла и его адрес записываем в переменную help
(рис. 3.3 а). Затем заносим в информационное поле нового узла значение key.
Теперь требуется связать новый узел со всем списком. Для этого в поле next
нового узла help заносим адрес прежнего первого элемента списка (head)
(рис. 3.3 б). Теперь осталось только изменить начало списка, т.е. head=help
(рис. 3.3 в). Заметим, что вставка пройдет корректно, даже если список был
пустым. В этом случае перед вставкой head=NULL. После вставки head бу-
дет ссылаться на новый элемент, а поле next примет значение NULL.
    При вставке элемента в середину (в конец) списка надо переместиться на
элемент, предшествующий месту вставки. Для этого заводим переменную
current, которая сначала хранит адрес первого элемента списка. В цикле
последовательно по цепочке сдвигаем ее значение на следующий элемент
(current=current->next). Это нужно делать до тех пор, пока не полу-
чим адрес элемента в нужной позиции (i=pos-1) или пока не закончится
список (в этом случае current=NULL). Если список закончится, то вставка
не производится. Если же остановка цикла произошла, когда current хра-
нит адрес существующего элемента списка, выполняем следующие действия.
Сначала выделяем память под хранение нового узла и его адрес записываем в
переменную help (рис. 3.4 а). Затем заносим в информационное поле нового
узла значение key. Теперь «встраиваем» новый элемент в середину списка.

                                      55