Размещено на http://www.allbest.ru/

В пособии дается понятие массива, правила описания массивов в программах на языке С. Рассматриваются основные алгоритмы обработки одномерных массивов. Приводятся примеры программ на языке С для всех рассмотренных алгоритмов.

Для студентов технических специальностей дневной и заочной форм обучения.

Содержание

• Содержание
• 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. Массивы в языке С

Обращение к элементу динамического массива осуществляется также, как и к элементам обычного массива. Например: a[0], a[1], …, a[9].

Можно обратиться к элементу массива другим способом: *(a+9), *(a+i), т.к. в переменной - указателе a хранится адрес начала массива. Для получения адреса, например, 9 - го его элемента к этому адресу прибавляется 9·sizeof(int) (9 умножить на·длину элемента типа int), т.е. к начальному адресу a прибавляется смещение 9. Затем с помощью операции *(разадресации) выполняется выборка значения из указанной области памяти.

После использования массива выделенная динамическая память освобождается с помощью опереатора: delete [ ] имя массива. Так например, для одномерного массива a:

delete [ ] a; .

Время "жизни" динамического массива определяется с момента выделения динамической памяти до момента ее освобождения.

2. Алгоритмы обработки одномерных массивов

Инициализация массива - это присваивание элементам массива начальных значений. Инициализацию массива можно выполнить на этапе описания массива, как это показано в п.1.1. Но в том случае, когда начальные значения получают лишь некоторые элементы массива, а остальные вычисляются в процессе выполнения программы, в программе записывают операторы присваивания. Например:

a[0]= -1; a[1]=1.1;

Присваивание всем элементам массива одного и того же значения осуществляется в цикле. Например, чтобы всем элементам массива a присвоить значение 0, можно воспользоватся алгоритмом изображенный на рис. 2.1.

Рисунок 2.1 Алгоритм и фрагмент программы инициализации массива

В представленном алгоритме все элементы массива в цикле последовательно инициализируются значением - 0.

2.2. Ввод - вывод одномерного массива

Для ввода n элементов одномерного массива, назовем его А, требуется организовать цикл, для ввода каждого i - го элемента, где i=0,1,2, …, n-1. Аналогичный цикл требуется организовать и для вывода элементов массива. На рисунке 2.2 изображена графическая схема ввода и вывода элементов массива.

Рисунок 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 б).

В большинстве случаев предпочтительнее использовать первый способ, поскольку он не содержит дополнительных вычислений, что особенно важно при перестановке вещественных чисел.

Рисунок 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] является последним, то обмен выполнить не возможно, поскольку последующий элемент отсутствует.

Рисунок 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+a_i.

При первой итерации цикла (i=in) получим s=s+a_in= 0+ a_in. На второй (i=in+1) - s=s+a_in+1= a_in + a_in+1 и т. д. На последней итерации цикла будем иметь s=s+a_ik= a_in + a_in+1+…+ a_ik. Т.е. в цикле по параметру i "старое" значение s, содержащее накопленную сумму на предыдущей итерации, изменяется на значение a_i. На рисунке 2.5 представлен алгоритм и фрагменты программ вычисления суммы элементов массива.

Рисунок 2.5 Графическая схема и фрагмент программы вычисления суммы элементов массива

Если в алгоритме (рисунок 2.5) в блоке 2 записать i=0, а блоке 3 - (i<n), то получим алгоритм вычисления суммы всех элементов массива.

Рассмотренный алгоритм вычисления суммы, можно применить для вычисления суммы элементов, стоящих в массиве на заданных местах (рисунок 2.6). В этом случаи шаг изменения параметра цикла определяется переменной 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+a_i только тогда, когда условие выполнено для рассматриваемого элемента массива a_i. В этом случаи алгоритм вычисления суммы примет следующий вид (рисунок 2.7).

Рисунок 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 с шагом 3, что и достигается изменениями в блоках 2 и 6 алгоритма вычисления суммы (рисунок 2.7). Так в блоке 2 запишем i=2, в блоке 3 (i<n), а в блоке 6 - (step=3) i=i+3. Для суммирования из рассмотренных элементов только тех, которые меньше заданного В, используется ветвление с условием а_i<В (блок 4). Окончательный алгоритм вычисления суммы заданных элементов примет, следующий вид (рисунок 2.8). В задаче будем использовать динамический способ задания массива. В данном примере для обращения к элементам массива используются указатели. Как уже отмечалось в разделе 1.1, имя массива является указателем на его первый элемент.

Рисунок 2.8 Графическая схема и программа примера 2.3

2.5 Подсчет количества элементов массива, удовлетворяющих заданному условию

Подсчет количества элементов массива, удовлетворяющих заданному условию, производится по алгоритмам, аналогичным вычислению суммы. Отличие заключается в том, что вместо добавления элемента массива к сумме, переменная - счетчик (k) увеличивается на единицу (k=k+1). Таким образом, если в графических схемах алгоритмов, рисунок 2.5-2.7, вместо s=0 и s=s+a_i записать k=0 и k=k+1, то получим алгоритмы подсчета количества элементов массива.

Пример 2.4.

В одномерном массиве a размерностью n, вычислить количество элементов равных заданному числу B и стоящих на четных местах.

Решение.

Графическая схема алгоритма решения задачи и фрагмент программы изображена на рисунке. 2.9.

Рисунок 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 - целочисленные операнды).

Рисунок 2.10 Графическая схема и программа для примера 2.5

2.6 Вычисление произведения элементов массива

Формулы, по которым вычисляется произведение элементов массива, аналогичны формулам вычисления сумм:

, (2.4)

. (2.5)

Поэтому вычисление произведения элементов массива выполнятся по алгоритмам аналогичным вычислению суммы. Отличие заключается в том, что начальное значение произведения p должно быть равным 1, а в цикле по параметру i надо вычислять p=p*a_i. Таким образом, если в графических схемах алгоритмов, рисунок 2.5 - 2.7 вместо s=0 и s=s+a_i записать p=1 и p=p*a_i, то получим алгоритмы вычисления произведения элементов массива.

Пример 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), т.к. произведение вещественных чисел может быть очень большим числом.

Рисунок 2.11 Графическая схема и программа для примера 2.6

В программе для возведения P в степень 1/k используется функция powl(основание, степень), первый аргумент которой может быть только положительным числом. Поэтому для отрицательного P использовано выражение , запись которого на языке С имеет вид: -powl(fabs(P), 1.0/k).

2.7 Поиск элементов, обладающих заданным свойством

При поиске элементов, обладающих заданным свойством, необязательно просматривать все элементы массива. Например, требуется определить, есть ли в массиве хотя бы один нулевой элемент. Для ответа на этот вопрос, достаточно в цикле просматривать элементы массива до тех пор, пока не закончится массив или не встретится равный нулю элемент. Если, например, уже третий элемент равен нулю, то остальные элементы просматривать нет необходимости.

В таких случаях для просмотра массива обычно используется оператор цикла while со сложным условием. Графическая схема для рассматриваемого примера изображена на рисунке 2.12. После цикла достаточно проверить, чему равно i. Если окажется, что i=n, т.е. были просмотрены все элементы, то в массиве нет нулевых элементов.

Рисунок 2.12 Графическая схема и фрагмент программы поиска нулевого элемента в массиве

Встречаются задачи, в которых требуется не только определить, есть ли элемент, обладающим заданным свойством в массиве, но и номер (индекс) такого элемента. Например, найти максимальный элемент в части массива, находящейся после последнего нуля. Решение задачи следует начать с вычисления индекса последнего нулевого элемента. Для определения индекса самого правого элемента, обладающего заданным свойством, массив следует просматривать с конца до тех пор, пока не закончатся элементы и текущий элемент не равен нулю (рисунок 2.13).

Рисунок 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.

Рисунок 2.15. Графический алгоритм и программа для примера 2.7

Описанный алгоритм можно дополнить предварительным сравнением последнего элемента массива X[n-1] с числом A, если X[n-1]=A - то заданное число находится на последнем месте, а в случаи выполнения X[n-1]>A - то, число A должно находится в массиве на позиции n. Если ни одно из этих условий не выполнено, то это означает что необходимо выполнить поиск числа A в массиве.

2.9 Поиск минимального и максимального элемента массива и его порядкового номера (индекса)