Конспект лекций по программированию для начинающих. Гладков В.П. - 166 стр.

                                      168

часть массива называется подмассивом. Методы работы с подмассивами совпадают
с методами работы с несколькими массивами.
    Пример 11.30. В заданном одномерном массиве все нулевые элементы
переписать в конец массива. Например, для массива a={1,0,2,3,0,4,5,0,0,0,6}
должен получиться результат a={1,2,3,4,5,6,0,0,0,0,0}.
    Решение. Можно воспользоваться услугами вспомогательного массива, в
который вначале перепишем ненулевые элементы (вспомним пример 11.26),
оставшуюся часть вспомогательного массива заполним нулями. Чтобы закончить
решение, останется переписать содержимое вспомогательного массива в исходный
массив. Соответствующий вариант решения приведен ниже. Здесь а - исходный
массив, i - индекс массива а, b - вспомогательный массив, j - его индекс.
Размерность обоих массивов - n.
    j:=1; { указывает номер первой свободной позиции в массиве b }
    { переписываем все ненулевые элементы из b в а }
    for i:=1 to n do
       if a[i]<>0 then begin b[j]:=a[i]; j:=j+1 end;
    { заполняем остаток массива b нулями }
    for i:=j to n do b[i]:=0;
    { переписываем массив b в а }
    a:=b.
    Проанализируем полученное решение. Главным его недостатком является
использование вспомогательного массива - нерациональное использование
оперативной памяти компьютера. Попробуем обойтись без него. В данном случае
можно записывать ненулевые элементы в начало исходного массива. Место записи
элемента указывает переменная j, которая передвигается по массиву только после
записи ненулевого элемента. При найденном нуле значение переменной j не
изменяется. Переменная i будет указывать на проверяемый элемент массива.
Получается, что для одного массива используются два индекса: индекс i
перебирает элементы массива а как входного (исходного), а индекс j - как
выходного. В этом алгоритме результат получается сразу в массиве а, не нужно
тратить       время      на   переписывание        из вспомогательного алгоритма.
Соответствующий вариант программы приведен ниже:
    j:=1;
    for i:=1 to n do
       if a[i]<>0 then begin a[j]:=a[i]; j:=j+1 end;
    for i:=j to n do a[i]:=0.
    Упражнения:
    1. Проведите трассировку предложенных в предыдущем примере алгоритмов.
Постройте для них систему тестов.
    2. Постройте алгоритм для переписывания всех нулей одномерного массива в
его начало. Используйте идеи рассмотренного примера.
    Пример 11.31. Задан одномерный массив. Нужно преобразовать его так, чтобы
все элементы, большие k, разместились в конце массива, а меньшие или равные k в
начале.