Основные алгоритмы преобразования одномерных массивов.
Теоретическая часть
Алгоритм удаления элемента из массива
Блок-схема алгоритма удаления элемента с номером 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;
}
Алгоритм упорядочения элементов массива по убыванию отличается только знаком в условии сравнения соседних элементов, в этом случае необходимо проверять Aj < Aj+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++ для преобразования одномерного массива.
Задание: Дан массив действительных чисел F1,...,F40. Упорядочить в нем по возрастанию элементы, которые находятся между максимальным и минимальным элементами.
Решение.
Для работы с массивом 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, упорядочены по возрастанию.