Реферат: Одномерные массивы
В пособии дается понятие массива,правила описания массивов в программах на языке С. Рассматриваются основныеалгоритмы обработки одномерных массивов. Приводятся примеры программ на языке Сдля всех рассмотренных алгоритмов.
Для студентов техническихспециальностей дневной и заочной форм обучения.
Содержание
Содержание
1. Массивы в языке С
1.1. Понятие массива
1.2. Динамические массивы
2. Алгоритмы обработки одномерных массивов
2.1. Инициализация массива
2.2. Ввод – вывод одномерного массива
2.3. Перестановка двух элементов массива
2.4. Вычисление суммы элементов массива
2.5. Подсчет количества элементов массива, удовлетворяющихзаданному условию
2.6. Вычисление произведения элементов массива
2.7. Поиск элементов, обладающих заданным свойством
2.8 Поиск в упорядоченном массиве
2.9. Поиск минимального имаксимального элемента массива и его порядкового номера (индекса)
2.10. Копирование массивов
2.10 Формирование нового массива
Литература
Приложение
Примеры решения задач по обработке одномерных массивов
Задача 1. Вычисление сумм, количеств и произведений элементов массива
Задача2. Вычисление сумм,количеств и произведений элементов массива
1.Массивы в языке С
1.1 Понятие массиваМассив – это совокупность элементов одноготипа, имеющих одно имя и расположенных в памяти ПК вплотную друг к другу.Массивы могут состоять из арифметических данных, символов, строк, структур,указателей. Доступ к отдельным элементам массива осуществляется по именимассива и индексу (порядковому номеру) элемента.
При объявлении массива в программеопределяется имя массива, тип его элементов, размерностьи размер. Размерность или количество измерениймассива определяется количеством индексов при обращении к элементам массива.Массивы бывают одномерные, двухмерные, трехмерные и т.д… Размер массива– это количество его элементов по соответствующим размерностям. Общий видобъявления массива:
<имя_типа> <имя_массива>[k1] [k2] … [kn];
где k1, k2, …, kn –количество элементов массива – константы или константные выражения по 1, 2,…, n измерениям. Причем значения индексов могут изменяться от до ki– 1.
Такое объявление массива называют статическим,поскольку предельное количество его элементов известно заранее и оно уже неможет быть изменено в ходе выполнения программы. При работе с массивами необходимоследовать следующим правилам:
¨ современныетрансляторы языка Си не контролируют допустимость значений индексов, это долженделать программист;
¨ количество измерениймассива не ограничено;
¨ в памяти элементымассива располагаются так, что при переходе от элемента к элементу наиболеебыстро меняется самый правый индекс массива, т.е. матрица, например,располагается в памяти по строкам;
¨ имя массиваявляется указателем – константой на первый элемент массива;
¨ операций надмассивами в Си нет, поэтому пересылка элементов одного массива в другой можетбыть реализована только поэлементно с помощью цикла;
¨ над элементамимассива допускаются те же операции что и над простыми переменными того же типа;
¨ ввод/выводзначений элементов массива можно производить только поэлементно;
¨ начальныезначения элементам массива можно присвоить при объявлении массива.
Примеры объявления массивов:
int A [10]; //одномерный массивиз 10 целочисленных величин
float X [20]; //одномерныймассив из 20 вещественных величин
int a[5]={1, 2, 3, 4, 5}; //массив с инициализацией его элементов
int c[]={–1, 2, 0, –4, 5, –3, –5, –6,1}; // массив размерность которого 6определяется числом инициализирующихэлементов
Обращения к элементам одномерногомассива могут иметь вид: A[0], A[1], A[2],…A[9], A[2*3].
В Си нет массивов с переменнымиграницами. Но, если количество элементов массива известно до выполненияпрограммы, можно определить его как константу с помощью директивы #define,а затем использовать ее в качестве границы массива, например,
#define n 10;
Main ( )
{ int a[n], b[n]; // Объявление2–х одномерных массивов
Если количество элементов массиваопределяется в процессе выполнения программы, используют динамическоевыделение оперативной памяти компьютера.
1.2 Динамические массивыЕсли до начала работы программынеизвестно, сколько в массиве элементов, в программе используют динамическиемассивы. Память под них выделяется с помощью оператора new вовремя выполнения программы. Адрес начала массива хранится в переменной,называемой указателем. Например.
int n=20;
int *a = new int[n];
Здесь описан указатель aна целую величину, которому присваивается адрес начала непрерывной областидинамической памяти, выделенной с помощью оператора new.Выделяется столько памяти, сколько необходимо для хранения n величинтипа int. Величина n может быть переменной.
Примечание: Обнуление памяти при еевыделении не происходит. Инициализировать динамический массив нельзя.
Обращение к элементу динамическогомассива осуществляется также, как и к элементам обычного массива. Например: a[0],a[1], …, a[9].
Можно обратиться к элементу массивадругим способом: *(a+9), *(a+i), т.к. в переменной – указателе aхранится адрес начала массива. Для получения адреса, например, 9 – го егоэлемента к этому адресу прибавляется 9·sizeof(int) (9 умножитьна·длину элемента типа int), т.е. к начальному адресу aприбавляется смещение 9. Затем с помощью операции *(разадресации)выполняется выборка значения из указанной области памяти.
После использования массивавыделенная динамическая память освобождается с помощью опереатора: delete[ ] имя массива. Так например, для одномерного массива a:
delete [ ] a; .
Время «жизни» динамическогомассиваопределяется с момента выделениядинамической памяти до момента ее освобождения.
2.Алгоритмы обработки одномерных массивов 2.1 Инициализация массива
Инициализация массива – это присваивание элементам массиваначальных значений. Инициализацию массива можно выполнить на этапе описаниямассива, как это показано в п.1.1. Но в том случае, когда начальные значенияполучают лишь некоторые элементы массива, а остальные вычисляются в процессевыполнения программы, в программе записывают операторы присваивания. Например:
a[0]= –1; a[1]=1.1;
Присваивание всем элементам массиваодного и того же значения осуществляется в цикле. Например, чтобы всемэлементам массива a присвоить значение 0, можно воспользоватсяалгоритмом изображенный на рис. 2.1.
/>
for(i=0;i<n;i++)
a[i]=0;
// или с помощью цикла while
i=0;
while (i<n)
{
a[i]=0;
i=i+1;
}
Рисунок 2.1 Алгоритм и фрагментпрограммы инициализации массива
В представленном алгоритме всеэлементы массива в цикле последовательно инициализируются значением – 0.
2.2. Ввод – вывод одномерного массиваДля ввода n элементоводномерного массива, назовем его А, требуется организовать цикл,для ввода каждого i – го элемента, где i=0,1,2, …, n–1.Аналогичный цикл требуется организовать и для вывода элементов массива. Нарисунке 2.2 изображена графическая схема ввода и вывода элементов массива.
/>
/* Ввод – вывод статического массива*/
#include <stdio.h>
#define n 50;
void main()
{
int n,i;
float A[n];
puts(«Введите число элементов массива „);
scanf(“%d»,&n);
// Ввод массива
for (i=0; i<n; i++)
{ printf(«Введите число A[%2d]=»,i);
scanf("%f",&A[i]);
}
// Вывод массива
puts(«Массив A»);
for(i=0;i<n;i++)
printf("%6.3f ",A[i]);
printf("\n");
}
Рисунок 2.2 Алгоритм и программаввода – вывода статического массива
Ввод–вывод динамического массиваосуществляется по тому же алгоритму. Из приведенного ниже примера программыввода и вывода динамического массива видно, что отличие заключается лишь вописании массива.
/* Ввод – вывод динамического массива*/
#include <stdio.h>
void main()
{
int n,i;
puts(«Введите число элементовмассива a»);
scanf("%d",&n);
float *a=new float[n]; // Описаниединамического массва
// Ввод массива
for (i=0;i<n;i++)
{ printf(«Введите числоa[%2d]=»,i);
scanf("%f",a+i); // или scanf("%f",&a[i]);
}
// Вывод массива
puts(«Массив a»);
for(i=0;i<n;i++)
printf("%.3f ",*(a+i));// или printf("%.3f ",a[i]);
printf("\n");
delete[] a; //Освобождение памяти выделенной под массив
}
2.3 Перестановка двух элементовмассиваДля перестановки двух элементовмассива x[] с индексами k и m, необходимоиспользование дополнительной переменной (tmp), для хранения копииодного из элементов (рисунок 2.3 а), но можно обойтись и без использованиядополнительной переменной tmp. В этом случаи алгоритм перестановкиимеет следующий вид (рисунок 2.3 б).
В большинстве случаевпредпочтительнее использовать первый способ, поскольку он не содержитдополнительных вычислений, что особенно важно при перестановке вещественныхчисел.
/>
tmp=x[k];
x[k]=x[m];
x[m]=tmp;
/>
x[k]=x[k]+x[m];
x[m]=x[k]-x[m];
x[k]=x[k]-x[m];
(а)
(б)
Рисунок 2.3 Алгоритм и фрагментпрограммы перестановки двух элементов массива c использованием дополнительнойпеременной (а) и без нее (б)
Пример 2.1Переставить первый и последнийэлемент массива x[] местами. Количество элементов массива n.
РешениеВ С нумерация элементов массиваначинается с нуля, поэтому номер последнего элемента массива (n–1) .
1 способ: tmp=x[0]; x[0]=x[n-1]; x[n-1]=tmp;
2 способ: x[0]=x[0]+x[n-1]; x[n-1]=x[0]-x[n-1];x[0]=x[0]-x[n-1];
Пример 2.2Поменять местами заданный элемент массиваx[k] с последующим.
РешениеПри решении этой задачи необходимоучитывать, что если заданный элемент массива x[k] являетсяпоследним, то обмен выполнить не возможно, поскольку последующий элементотсутствует.
/>
if(k == n-1)
puts(«Обмен не возможен.»);
else
{
tmp=x[k];
x[k]=x[k+1];
x[k+1]=tmp;
}
Рисунок 2.4 Алгоритм и фрагмент программыперестановки заданного элемент массива x[k] с последующим
При перестановке с предыдущимэлементом, обмен невозможен если заданный элемент является первым (k=0).
2.4 Вычисление суммы элементовмассиваЧасто возникают задачи, требующиевычислить сумму всех или некоторых элементов массива, например, суммуэлементов, стоящих в массиве на заданных местах, или сумму элементов,удовлетворяющих некоторому условию (сумму только положительных элементов, суммуненулевых элементов второй половины массива и т.д.).
Пусть а[] – заданныймассив из n элементов. Сумма всех его элементов в математическойформе выглядит следующим образом:
/>(2.1)
Для вычисления суммы элементов частимассива, например, с in–го до ik–го. Следуетиспользовать формулу:
/>(2.2)
Очевидно, что формула (2.2)получается из формулы (2.1) при in=0 и ik=n–1.
Алгоритм вычисления суммы состоит вследующем:
1. установитьзначение переменой для накопления суммы (s) в нулевое значение (s=0);
2. в цикле изменяя iотin до ik вычислить суммуэлементовмассива по выражениию s=s+ai.
При первой итерации цикла (i=in)получим s=s+ain= 0+ ain. На второй (i=in+1)– s=s+ain+1= ain + ain+1 и т. д.На последней итерации цикла будем иметь s=s+aik= ain+ ain+1+…+ aik. Т.е. в цикле по параметру i«старое» значение s, содержащее накопленную сумму на предыдущейитерации, изменяется на значение ai. На рисунке 2.5 представленалгоритм и фрагменты программ вычисления суммы элементов массива.
/>
*/вычисление суммы элементов массива с in по ik
s=0;
for(i=in;i<ik;i++)
s=s+a[i]; // или s+=a[i]; или s+=*(a+i);
*/вычисление суммы всех элементов массива
s=0;
for(i=0;i<n;i++)
s+=a[i];
Рисунок 2.5 Графическая схема ифрагмент программы вычисления суммы элементов массива
Если в алгоритме (рисунок 2.5) вблоке 2 записать i=0, а блоке 3 – (i<n), то получим алгоритмвычисления суммы всех элементов массива.
Рассмотренный алгоритм вычислениясуммы, можно применить для вычисления суммы элементов, стоящих в массивена заданных местах (рисунок 2.6). В этом случаи шаг изменения параметрацикла определяется переменной step.
/>
/* с помощью цикла for */
s=0;
for(i=in;i<ik;i=i+step)
s+=a[i]; // или s=s+a[i];
/* с помощью цикла while */
s=0; i=in;
while (i<ik)
{
s+=a[i];
i=i+step;
}
Рисунок 2.6 Графическая схема ифрагмент программы вычисления суммы элементов массива стоящих на заданныхместах
Например, чтобы вычислить суммуэлементов, стоящих в массиве на четных местах, необходимо«заставить» i принимать значения 1, 3, 5, … (посколькунумерация элементов массива в С начинается с нуля т.е. элемент массива синдексом a[0] – первый элемент массива). Для этого достаточно вблоке 2 записать i=1, в блоке 3 – (i<n), а вблоке 5 записать i=i+2 (step=2). В программе наязыке С соответствующий фрагмент будет выглядеть следующим образом:
s=0;
for(i=1;i<n;i=i+2) // илиfor(i=1;i<n;i+=2)
s+=a[i]; // илиs=s+a[i];
Для вычисления суммы только техэлементов, которые удовлетворяют некоторому условию, необходимо валгоритме вычисления суммы (рисунок 2.6) блок 4 заменить на ветвление, котороеобеспечивает выполнение команды s=s+ai только тогда,когда условие выполнено для рассматриваемого элемента массива ai.В этом случаи алгоритм вычисления суммы примет следующий вид (рисунок 2.7).
/>
/* с помощью цикла for */
s=0;
for(i=in;i<ik;i+=step)
if( условие ) s+=a[i]; // или s=s+a[i];
/* с помощью цикла while */
s=0; i=in;
while (i<ik)
{
if( условие ) s+=a[i];
i=i+step;
}
Рисунок 2.7 Графическая схема ифрагмент программы вычисления суммы элементов массива стоящих на заданныхместах
Применим полученный алгоритм длявычисления суммы положительных элементов массива стоящих на нечетных местах.Для этого в блоке 2 запишем i=0, в блоке 3 (i<n),в 4 условие – (a[i]>0), а в блоке 6 изменение параметра цикла(step=2) i=i+2. Тогда соответствующий фрагментпрограммы можно записать в виде:
s=0;
for(i=0;i<n;i+=2)
if( a[i]>0 ) s+=a[i]; //или s=s+a[i];
Рассмотрим примеры использованиярассмотренных алгоритмов.
Пример 2.3.В одномерном массиве a размерностью n, вычислить сумму элементов массива,меньших заданного значения В и стоящих на местах, кратных трем.
Решение
Объединим алгоритмы ввода – выводамассива (рисунок 2.2) и вычисления суммы (рисунок 2.7). Для сокращения записи графическойсхемы алгоритма ввода и вывода массива, здесь и в дальнейшем используем простыеблоки вида:
/>
В алгоритме для вычисления искомойсуммы рассматриваются только те элементы, которые в массиве стоят на местах,кратных трем, при этом необходимо учитывать что нумерация элементов массива в Сначинается с нуля т.е. элемент массива с индексом a[0] это первыйэлемент массива. Таким образом, элементы стоящие на местах кратных трем – а2,а5, а8, …, индекс элемента массива(он же – параметр цикла) должен последовательно принимать значения 2, 5, 8, …,т.е. изменяться от 2 с шагом 3, что и достигается изменениями в блоках 2 и 6 алгоритма вычисления суммы (рисунок 2.7). Так в блоке 2запишем i=2, в блоке 3 (i<n), а в блоке 6 – (step=3)i=i+3. Для суммирования из рассмотренных элементов только тех,которые меньше заданного В, используется ветвление с условием аi<В(блок 4). Окончательный алгоритм вычисления суммы заданных элементов примет,следующий вид (рисунок 2.8). В задаче будем использовать динамический способзадания массива. В данном примере для обращения к элементам массиваиспользуются указатели. Как уже отмечалось в разделе 1.1, имя массива являетсяуказателем на его первый элемент.
/>
Используемые переменные:
n – число элементов массива;
a[] – динамический массив;
s – сумма элементов массива;
B – заданное число;
i – параметр цикла;
#include <stdio.h>
main()
{
int n,i;
float s, B;
puts(«Введите число элементов массива a»);
scanf("%d",&n);
float *a=new float[n];
for (i=0;i<n;i++)
{ printf(«Введите число a[%2d]=»,i);
scanf("%f",a+i);
}
puts(«Введите B»);
scanf("%f",&B);
s=0;
for(i=2;i<n;i+=3)
if(*(a+i)<B) s+=*(a+i);
puts(«Массив a»);
for(i=0;i<n;i++)
printf("%.1f ",*(a+i));
printf("\n");
printf(«Сумма чисел, меньших %.1f, стоящих на местах, кратных 3, равна %.2f\n»,B,s);
delete[] a; // освобождение памяти
return(0);
}
Рисунок 2.8 Графическая схема ипрограмма примера 2.3
2.5 Подсчет количества элементовмассива, удовлетворяющих заданному условиюПодсчет количества элементов массива,удовлетворяющих заданному условию, производится по алгоритмам, аналогичным вычислениюсуммы. Отличие заключается в том, что вместо добавления элемента массива к сумме,переменная – счетчик (k) увеличивается на единицу (k=k+1).Таким образом, если в графических схемах алгоритмов, рисунок 2.5–2.7, вместо s=0и s=s+ai записать k=0 и k=k+1,то получим алгоритмы подсчета количества элементов массива.
Пример 2.4.В одномерном массиве a размерностью n, вычислить количество элементов равныхзаданному числу B и стоящих на четных местах.
Решение.Графическая схема алгоритма решениязадачи и фрагмент программы изображена на рисунке. 2.9.
/>
/* с помощью цикла for */
k=0;
for(i=1;i<n;i+=2)
if(a[i]==b ) k++; // или k=k+1;
/* с помощью цикла while */
k=0; i=1;
while (i<n)
{
if(a[i]==b) k++;
i=i+2;
}
Рисунок 2.9 Графическая схема ипрограмма для примера 2.4
Следующий пример показывает, как в одномалгоритме находить сумму и количество элементов, удовлетворяющих заданному условию.
Пример 2.5.В одномерном массиве a размерностью n, вычислить среднее арифметическое положительныхэлементов второй половины массива, стоящих на нечетных местах.
РешениеСреднее арифметическое чисел (sr)– частное от деления их суммы (s) на их количество (k):sr=s/k, где k≠0. Таким образом, задачасводится к нахождению суммы и количества положительных элементов второйполовины массива, стоящих на нечетных местах. Для решения данной задачиприменим алгоритм, приведенный на рисунке 2.7, в соответствии с которым можнонайти сумму и количество части элементов массива (второй половины), удовлетворяющихзаданному условию (положительных элементов).
Определим номер in тогоэлемента, с которого будем просматривать элементы второй половины массива. Посколькупо условию задачи обрабатываются элементы стоящие на нечетных местах тоначальное значение in тоже должно быть четным (посколькунумерация элементов массива начинается с нуля). Значение переменной inможно определить по формуле (2.3) где пара квадратных скобок [ ]определяет операцию вычисления целой части числа:
/> (2.3)
Значение ik совпадает сn, поскольку массив надо просматривать до конца. Параметр цикла i(номер элемента массива) необходимо изменять с шагом 2, чтобы обеспечить четныезначения индекса (значения номеров элементов массива), т.е. i=i+2.Вычисление суммы и количества будем вычислять в одном цикле по параметру i,что значительно сократит алгоритм.
При вычислении среднегоарифметического sr=s/k необходимо избежать возможного деления наноль, поскольку если во второй половине массива на нечетных местах не окажетсяположительных элементов то k будет равным нулю. Например, длямассива X={2, 0, –6, 7, 9, 0, –14,–5, 0, –4, –32};n=11; in=[n/2]+1=6, в цикле по i будут просматриватьсятолько выделенные элементы, а среди них нет положительных чисел, поэтомупеременная k останется равной нулю. В графической схеме (рисунок2.10) для этой цели используется ветвление, в котором проверяется условие k=0.Если это условие выполнено, то выводится сообщение о том, что среднее значениене может быть вычислено, в противном случае вычисляется и выводится значение sr.
В приведенном ниже фрагментепрограммы четность [n/2] определяется по остатку от деления nна 2 с помощью операции % – определения остатка целочисленногоделения (примечание: результат операции целочисленный, т.к. nи 2 – целочисленные операнды).
Используемые переменные:
n – число элементов массива;
a[] – статический массив;
in – первый четный номер второй половины массива;
s – сумма элементов массива удовлетворяющих условию;
k – количество элементов массива удовлетворяющих условию;
sr – среднее значение элементов массива удовлетворяющих условию;
i – параметр цикла;
/>
#include <stdio.h>
main()
{
float a[20];
int n, i, in, k;
float s, sr;
puts(«Введите число элементов массива a»);
scanf("%d",&n);
for (i=0;i<n;i++)
{ printf(«Введите число a[%2d]=»,i);
scanf("%f",&a[i]);
}
if ((n/2)%2==0) in=n/2;
else in=n/2+1;
s=0; k=0;
for(i=in;i<n;i+=2)
if(a[i]>0) { s+=a[i]; k++;}
puts(«Массив a»);
for(i=0;i<n;i++)
printf(«a[%2d]=%6.2f \n», i, a[i]);
if (k==0)
puts(«Среднее арифметическое вычислить нельзя!»);
else
{
sr=s/k;
printf(«Среднее ариф. полож. элементов на нечетных. местах второй полов. массива =%6.3f\n», sr);
}
return(0);
}
Рисунок 2.10 Графическая схема ипрограмма для примера 2.5
2.6 Вычисление произведения элементовмассиваФормулы, по которым вычисляетсяпроизведение элементов массива, аналогичны формулам вычисления сумм:
/>, (2.4)
/>. (2.5)
Поэтому вычисление произведенияэлементов массива выполнятся по алгоритмам аналогичным вычислению суммы.Отличие заключается в том, что начальное значение произведения pдолжно быть равным 1, а в цикле по параметру i надовычислять p=p*ai. Таким образом, если в графических схемахалгоритмов, рисунок 2.5 – 2.7 вместо s=0 и s=s+aiзаписать p=1 и p=p*ai, то получималгоритмы вычисления произведения элементов массива.
Пример 2.6.В одномерном массиве a размерностью n, вычислить среднее геометрическоененулевых элементов массива.
РешениеСреднее геометрическое kэлементов массива – это корень степени k из произведения этихэлементов. Таким образом, сначала необходимо вычислить произведение Рненулевых элементов массива и их количество k, а затем среднеегеометрическое Sg по формуле:
/>. (2.6)
Например, если элементы массива равныA= {1, 0, 2, 4, 0} то – />/>
Графическая схема алгоритма решениязадачи изображена на рисунке 2.11. В приведенном алгоритме в цикле по i(блоки 5 – 9) помимо вычисления произведения вычисляется и количествоненулевых элементов массива. После цикла с помощью ветвления, проверяется, естьли в массиве ненулевые элементы (k>0 – условие наличия в массивененулевых элементов), в этом случае вычисляется и выводится среднеегеометрическое. В противном случае выводится сообщение "В массиве всеэлементы равны нулю". В программе переменные Р и Sgимеют вещественный тип двойной точности (double), т.к. произведениевещественных чисел может быть очень большим числом.
Используемые переменные:
n – число элементов массива;
a[] – статический массив;
P – произведение не нулевых элементов массива;
k – количество не нулевых элементов массива;
Sg – среднее геометрическое элементов массива;
i – параметр цикла;
/>
#include <stdio.h>
#include <math.h>
main()
{
float a[20];
int n, i, k;
double P, Sg;
puts(«Введите число элементов массива a»);
scanf("%d",&n);
for (i=0;i<n;i++)
{ printf(«Введите число a[%2d]=»,i);
scanf("%f",&a[i]);
}
P=1; k=0;
for(i=0;i<n;i++)
if(a[i]!=0) {P*=a[i]; k++;}
puts(«Массив a»);
for(i=0;i<n;i++)
printf(«a[%2d]=%6.2f \n», i, a[i]);
if(k>0)
{
if(P>0) Sg=powl(P,1.0/k);
else Sg= –powl(fabs(P),1.0/k);
printf(«Среднее геометрическое ненулевых элементов массива =%.4lf \n», Sg);
printf(«P=%.4lf k=%d \n», P, k);
}
else puts(«В массиве все элементы равны нулю! „);
return(0);
}
Рисунок 2.11 Графическая схема ипрограмма для примера 2.6
В программе для возведения Pв степень 1/k используется функция powl(основание, степень),первый аргумент которой может быть только положительным числом. Поэтому дляотрицательного P использовано выражение />, запись которого на языкеС имеет вид: –powl(fabs(P), 1.0/k).
2.7 Поиск элементов, обладающихзаданным свойствомПри поиске элементов, обладающихзаданным свойством, необязательно просматривать все элементы массива. Например,требуется определить, есть ли в массиве хотя бы один нулевой элемент. Для ответана этот вопрос, достаточно в цикле просматривать элементы массива до тех пор,пока не закончится массив или не встретится равный нулю элемент. Если,например, уже третий элемент равен нулю, то остальные элементы просматривать нетнеобходимости.
В таких случаях для просмотра массиваобычно используется оператор цикла while со сложным условием. Графическаясхема для рассматриваемого примера изображена на рисунке 2.12. После цикладостаточно проверить, чему равно i. Если окажется, что i=n,т.е. были просмотрены все элементы, то в массиве нет нулевых элементов.
/>
i=0;
while(i<n && a[i]!=0) i=i+1;
If(i == n)
puts(“В массиве нет нулевых элементов»);
else
puts(«В массиве есть нулевой элемент»);
Рисунок 2.12 Графическая схема и фрагментпрограммы поиска нулевого элемента в массиве
Встречаются задачи, в которыхтребуется не только определить, есть ли элемент, обладающим заданным свойствомв массиве, но и номер (индекс) такого элемента. Например, найти максимальныйэлемент в части массива, находящейся после последнего нуля. Решение задачи следуетначать с вычисления индекса последнего нулевого элемента. Для определенияиндекса самого правого элемента, обладающего заданным свойством, массив следуетпросматривать с конца до тех пор, пока не закончатся элементы и текущий элементне равен нулю (рисунок 2.13).
/>
i=n–1;
while(i>=0 && a[i]!=0) i=i–1;
If(i<0)
puts(«В массиве нет нулевых элементов»);
else
printf(«Индекс последнего нуля – %d \n», i);
Рисунок 2.13 Графическая схема ифрагмент программы поиска номера последнего нулевого элемента в массиве
Номер (индекс) первого встретившегосянулевого элемента можно узнать по значению параметра цикла i.Этот номер можно использовать в дальнейших вычислениях например как номерначального элемента для поиска максимума.
2.8 Поиск в упорядоченном массивеУпорядоченность элементов массивапозволяет значительно увеличить скорость его обработки, за счет снижения числапроверяемых элементов массива. В таких алгоритмах массив проверяется покавыполняется (или не выполняется) дополнительное условие, определяющее досрочныйвыход из цикла. Также при составлении алгоритма необходимо учитыватьвозрастающим или убывающим является проверяемый массив, что оказывает влияниена то как удобнее обрабатывать массив с начала или с конца. В общем случаиалгоритм обработки упорядоченного массива имеет следующий вид – рисунок 2.14.
/>
/>
(а)
(б)
Рисунок 2.14. Графический алгоритмобработки упорядоченного массива с перебором с начала (а), с конца (б)
Как видно из блок–схемы,дополнительное условие управляет досрочным выходом из цикла. Пока дополнительноеусловие истина и не конец массива i<n, цикл выполняется, кактолько одно из условий будет не выполнено происходит выход из цикла.
Пример 2.7В возрастающем одномерном массиве Xс количеством элементов n, определить есть ли число равное Aи на какой позиции оно находится, если числа A нет определитьместо на котором оно должно находиться чтобы не нарушить упорядоченностьмассива.
Решение
В данной задаче обработку массива будемпроводить с начала. Выход из цикла по дополнительному условию будет выполнен,если в массиве найден элемент больший либо равный A (k=1).Для индикации наличия в массиве элемента равного A, введемвспомогательную переменную f с начальным значением f=0.При обнаружении элемента A, переменная f=1. Дляопределения номера позиции числа A в массиве введемдополнительную переменную poz с начальным значением n,т.е. предполагая, что все элементы массива меньше A. Приобнаружении в массиве числа большего или равного A в переменной pozсохраняется его индекс – i. После выхода из цикла, по значениюпеременной f определяется наличие и место переменной Aв массиве. Описанный алгоритм поиска и программа представлены на рисунке 2.15.
Используемые переменные:
n – число элементов массива;
a[] – статический массив;
k– переменная для досрочного выхода из цикла при нахождении элемента большего или равного a;
f– вспомогательная переменная для индикации наличия в массиве числа равного a;
poz– номер элемента массива на котором должно находится число a;
i – параметр цикла;
/>
#include <stdio.h>
main()
{
int f, k, n, poz, i, x[10], a;
puts(«Введите число элементов массива:»);
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(«x[%2d]=»,i);
scanf("%d",&x[i]);
}
puts(«Введите число a:»);
scanf("%d",&a);
f=0; poz=n; k=0;
for(i=0;i<n&&k==0;i++)
{
if(x[i]>a) { poz=i;k=1;}
else
{
if(x[i]==a)
{poz=i; f=1; k=1;}
}
}
if(f==1)
printf(«В массиве есть число =%d, на позиции-%d\n», a, poz);
else
printf(«Число %d должно находиться на позиции-%d\n» ,a, poz);
for(i=0;i<n;i++)
printf(«x[%d]=%d\n»,i,x[i]);
return 0;
}
Рисунок 2.15. Графический алгоритм ипрограмма для примера 2.7
Описанный алгоритм можно дополнитьпредварительным сравнением последнего элемента массива X[n-1] с числом A, если X[n-1]=A– то заданное число находится напоследнем месте, а в случаи выполнения X[n-1]>A– то, число A должно находится в массиве напозиции n. Если ни одно из этих условий невыполнено, то это означает что необходимо выполнить поиск числа A в массиве.
2.9Поиск минимального и максимального элемента массива и его порядкового номера(индекса)
Пусть требуется найти минимальныйэлемент (min) и его индекс (n_min) во всем массиве(in=0и ik=n) или какой то его части (с in– го по ik – ый), в этом случаи алгоритм решения задачиможно записать так:
1. в качественачального значения переменной min выберем любой израссматриваемых элементов (обычно выбирают первый). Тогда min=ain,n_min= in;
2. затем в цикле по параметруi начиная со следующего элемента (i=in+1, …, ik)будем сравнивать элементы массива ai текущимминимальным min. Если окажется, что текущий (i – ый)элемент массива меньше минимального (ai < min), топеременная min принимает значение ai, а n_min– на i: min=ai, n_min=i.
Графическая схема алгоритма и фрагментпрограммы поиска минимального элемента в массиве приведены на рисунке 2.16.
/>
min=a[in];
n_min=in;
for(i=in+1; i<ik; i++)
if(a[i]<min)
{
min=a[i];
n_min=i;
}
Рисунок 2.16. Графический алгоритм ифрагмент программы поиска минимального элемента в массиве
Заметим, что при наличии в массивенескольких минимальных элементов, найден будет первый из них (самый левыйминимальный элемент) при просмотре массива слева направо. Если в неравенстве ai<min знак > поменять на знак ≥, то будет найденпоследний из них (самый правый минимальный элемент).
Для поиска максимального элемента maxи его индекса n_max используется аналогичный алгоритм, в котором сначаланадо принять max =ain, n_ max = in,вместо неравенства ai < min используется неравенствоai > max. В случаи выполнения условия ai> max записать в max =ai и в n_max= i.
Для поиска в массиве экстремума можноне использовать вспомогательную переменную min (max).В этом случаи минимальный элемент массива определяется только по его индексу n_min(n_max) (рисунок 2.17).
/>
/*поиск минимального элемента*/
n_min=in;
for(i=in+1; i<ik; i++)
if(a[i]<a[n_min])
n_min=i;
/*поиск максимального элемента*/
n_max=in;
for(i=in+1; i<ik; i++)
if(a[i]>a[n_max])
n_max=i;
Рисунок 2.17. Графический алгоритм ифрагмент программы поиска минимального элемента в массиве по его индексу
Пример использования рассмотренныхалгоритмов представлен в приложении 2.
2.10Копирование массивов
В ряде задач для организациидополнительных или промежуточных вычислений, требуется создание копии всегомассива или части его элементов. Для этого можно воспользоваться алгоритмомпредставленным на рисунке 2.18.
/>
k=0;
for(i=in;i<ik;i++)
{
y[k]=a[i];
k++;
}
Рисунок 2.18 Алгоритм и фрагментпрограммы создания копии массива
В зависимости от параметров inи ik, в массив y[ ] копируются элементы из исходногомассива a[ ]. Так для копирования всех элементов массива a[] необходимо задать in=, ik=n(n – количество элементов массива a[ ]). Прикопировании части массива, например с 3 по 9, принимаем in=2(посколькунумерация элементов массива в С++, начинается с нуля) и ik=9.
2.10 Формирование нового массиваВ задачах формирования нового массиватребуется создать массив из элементов существующего массива (массивов)удовлетворяющих заданному условию. В новый массив элементы заносятся,последовательно начиная с нулевого индекса. Максимально число элементов вформируемом массиве может достигать количества элементов в исходном массиве(массивах), минимальное значение равняется нулю. В этом случаи считается, чтоновый массив не сформирован.
При формировании новых массивовудобно использовать динамические массивы, поскольку число его элементов заранеене известно. Алгоритм создания нового массива схож с алгоритмом копирования(рисунок 2.19).
/>
k=0;
for(i=in;i<ik;i++)
{
if (условие)
{
y[k]=a[i];
k++;
}
}
Рисунок 2.19 Алгоритм и фрагментпрограммы формирования нового массива
Для последовательной записи элементовв новый массив используется дополнительная переменная k – счетчик элементов в новоммассиве. Начальное значение этой переменной принимается равной нулю,т.е считается что в новом массиве нет элементов. При обнаружении в исходноммассиве элемента удовлетворяющего заданному условию, его значение заносится вновый массив на позицию k, а после счетчик элементов увеличивается на единицу (k=k+1). Таким образом, после обработкивсего исходного массива по значению счетчика k можно определить, сформирован новыймассив (k>0) и сколько в нем элементов (k).
Пример 2.8Даны два одномерных массива X и Y. Необходимо сформировать массив Z из положительных элементов массива X стоящих на четных местах и элементовмассива Y больших первого элемента массива X.
массив одномерный программаалгоритм
РешениеЕсли число элементов массива X – n, а массива Y – m, то с учетом того, что из первогомассива выбираются элементы стоящие только на четных местах, максимальное числоэлементов в новом массиве Z может достигать m+n/2 элементов. Поэтому для массива Z с помощью оператора динамическоговыделения памяти (new) выделим m+[n/2] ячейки памяти ([n/2] – целая часть от деления). Начальноезначение счетчика элементов нового массива k принимается равным нулю.
При обработке массива X необходимо проверять толькоэлементы, стоящие на четных местах, т.е. параметр цикла i изменяется от in=1 до ik=nс шагом 2. Условиеотбора элементов из первого массива X[i]>0. При обработке массива Y учитываются все его элементы, т.е.параметр цикла i изменяется от in=0 до ik=mс шагом 1. Условиеотбора элементов из второго массива – Y[i]> X[0].
Описанный алгоритм формированиянового массива и программа представлены на рисунке 2.20.