Основные алгоритмы преобразования одномерных массивов

Теоретическая часть

Алгоритм удаления элемента из массива

Блок-схема алгоритма удаления элемента с номером M из массива A, в котором N элементов выглядит следующим образом:

Соответствующий фрагмент текста программы на языке C++:

for (i=M;i<N–1;i++) A[i]=A[i+1];

N= N–1;

Алгоритм удаления из массива серии элементов с заданными номерами

Блок-схема алгоритма удаления серии элементов с номерами от M1 до M2 из массива A, в котором N элементов, выглядит следующим образом:

Соответствующий фрагмент текста программы на языке C++:

k=M2-M1+1;

for (i=M1;i<N–k:i++) A[i]=A[i+k];

N= N–k;

Алгоритм удаления из массива элементов с заданным значением

Блок-схема алгоритма удаления всех элементов, равных заданному значению X, из массива A, в котором N элементов, выглядит следующим образом:

Соответствующий фрагмент текста программы на языке С++:

i=1;

while (i<N)

{

if (A[i]==X)

{

for (j=i;j<N-1;j++) A[j]=A[j+1];

N=N-1;

}

else i=i+1;

}

Алгоритм копирования элементов массива в новый массив

Блок-схема алгоритма копирования элементов, удовлетворяющих заданному условию (в данном случае – элементов, значение которых больше, чем X), из массива A, в котором N элементов, в массив B выглядит следующим образом:

В результате массив B будет содержать K элементов.

Соответствующий фрагмент текста программы на языке C++:

K=0;

for (i=0;i<N;i++)

{

if (A[i]>X)

{

B[K]=A[i];

K=K+1;

}

}

Алгоритм вставки нового элемента в массив

Блок-схема алгоритма вставки элемента с номером M, равного X, в массив A, который содержит N элементов, выглядит следующим образом:

Соответствующий фрагмент текста программы на языке С++:

N=N+1;

for (i=N-1;i>M;i--) A[i]=A[i-1];

A[M]=X;

Алгоритм упорядочения элементов массива

Блок-схема алгоритма упорядочения по возрастанию элементов массива A, состоящего из N элементов, методом «пузырька» выглядит следующим образом:

Соответствующий фрагмент текста программы на языке C++:

for (i=1;i<N;i++)

for (j=1;j<=N-i;j++)

if (A[j-1] > A[j])

{

P=A[j];

A[j]=A[j-1];

A[j-1]=P;

}

Алгоритм упорядочения элементов массива по убыванию отличается только знаком в условии сравнения соседних элементов, в этом случае необходимо проверять A _j < A _j+1.

Алгоритм вставки элемента в упорядоченный массив

Блок-схема алгоритма вставки элемента, равного X, в упорядоченный массив A, который содержит N элементов, без нарушения упорядоченности массива выглядит следующим образом:

Соответствующий фрагмент текста программы на языке C++:

if (X>=A[N-1]) A[N]=X;

else {

K=0;

while (X>A[K])K=K+1;

for (i=N-1;i>=K;i--) A[i+1]=A[i];

A[K]=X;

}

N=N+1;

6.1.2 Пример составления алгоритма и программы на языке C++ для преобразования одномерного массива.

Задание: Дан массив действительных чисел F₁,...,F₄₀. Упорядочить в нем по возрастанию элементы, которые находятся между максимальным и минимальным элементами.

Решение.

Для работы с массивом F сначала необходимо сформировать его элементы. Выполним формирование элементов массива с помощью генератора случайных чисел rand(). Для обозначения размерности массива F введем переменную N. В цикле сразу после формирования элемента массива выполним вывод его на экран.

Далее в одном цикле выполним поиск максимального и минимального элементов массива Fmax и Fmin и их номеров nmax и nmin. Затем определим, какой из номеров меньше: nmax или nmin, меньший из номеров запомним в переменной k1, больший – в переменной k2. После этого упорядочим по возрастанию элементы от k1 до k2 по аналогии с сортировкой элементов массива от 1-го до N-го. При упорядочении элементов массива необходимо организовать 2 цикла. Внешний цикл всегда организовывается, начиная с 1 и выполняется число раз, на единицу меньшее количества сортируемых элементов (в случае сортировки всего массива из N элементов внешний цикл организовывался от 1 до N – 1). В данном случае необходимо упорядочить (k2 – k1 + 1) элементов. Поэтому внешний цикл необходимо организовать от 1 до k2 – k1. В качестве переменной внешнего цикла будем использовать переменную i. Поскольку необходимо упорядочить элементы с номерами от k1 до k2, внутренний цикл организуем, начиная с k1 до k2 – i (в случае сортировки всего массива из N элементов внутренний цикл организовывался от 1 до N – i). В качестве переменной внутреннего цикла будем использовать переменную j.

После упорядочения преобразованный массив F выведем на экран.

Блок-схема алгоритма решения данной задачи выглядит следующим образом:

Текст программы на языке C++ выглядит следующим образом:

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

int main()

{ float F[40],Fmax,Fmin,P;

int i,j,k1,k2,nmin,nmax,N;

clrscr();

randomize();

N=40;

printf("\nИсходный массив:\n");

for (i=0;i<N;i++)

{

F[i]=100.0*rand()/RAND_MAX-50;

printf("%8.2f",F[i]);

}

Fmax=-10000;

Fmin=10000;

for (i=0;i<N;i++)

{

if (F[i]>Fmax)

{

Fmax=F[i];

nmax=i;

}

if (F[i]<Fmin)

{

Fmin=F[i];

nmin=i;

}

}

printf("\n\nМаксимальный элемент номер %d равен %.2f",nmax,Fmax);

printf("\n Минимальный элемент номер %d равен %.2f",nmin,Fmin);

if (nmax>nmin)

{

k1=nmin;

k2=nmax;

}

else {

k2=nmin;

k1=nmax;

}

for (i=1;i<=k2-k1;i++)

for (j=k1;j<=k2-i;j++)

if (F[j]>F[j+1])

{

P=F[j];

F[j]=F[j+1];

F[j+1]=P;

}

printf("\nРезультат:\n");

for (i=0;i<N;i++) printf("%8.2f",F[i]);

getch();

return 0;

}

Результаты работы программы:

Исходный массив:

-47.34 0.30 -31.91 -17.82 38.40 7.93 -45.38 4.23 -6.69 28.25

23.55 35.54 19.14 11.13 18.54 -12.78 -34.82 42.40 -19.17 22.95

35.96 -41.60 48.42 -26.81 24.89 37.18 23.42 -37.94 20.87 -49.13

-20.49 -43.66 -15.52 13.65 31.19 -4.16 40.86 9.40 36.95 14.62

Максимальный элемент номер 22 равен 48.42

Минимальный элемент номер 29 равен -49.13

Результат:

-47.34 0.30 -31.91 -17.82 38.40 7.93 -45.38 4.23 -6.69 28.25

23.55 35.54 19.14 11.13 18.54 -12.78 -34.82 42.40 -19.17 22.95

35.96 -41.60 -49.13 -37.94 -26.81 20.87 23.42 24.89 37.18 48.42

-20.49 -43.66 -15.52 13.65 31.19 -4.16 40.86 9.40 36.95 14.62

Из результатов работы программы видно, что в преобразованном массиве элементы, начиная с 22 по 29, упорядочены по возрастанию.

Дата добавления: 2014-11-20