Учебное пособие: Одномерные массивы

Учебное пособие: Одномерные массивы

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

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

Содержание

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 измерениям. Причем значения индексов могут изменяться от 0 до 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.1 Инициализация массива

Инициализация массива – это присваивание элементам массива начальных значений. Инициализацию массива можно выполнить на этапе описания массива, как это показано в п.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+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 представлен алгоритм и фрагменты программ вычисления суммы элементов массива.

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

Страницы: 1, 2, 3