Файл: КонспектЛекций__Основы C++.pdf

Сделать презентацию

Скачать файл (0,98Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 23.06.2021

Просмотров: 1677

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

6. Массивы

В языке Си/Си++ ,кроме базовых типов, разрешено вводить и использовать

производные типы, полученные на основе базовых. Стандарт языка определяет три
способа получения производных типов:

массив элементов заданного типа;

указатель на объект заданного типа;

функция, возвращающая значение заданного типа.

Массив – это упорядоченная последовательность переменных одного типа.

Каждому элементу массива отводится одна ячейка памяти. Элементы одного массива
занимают последовательно расположенные ячейки памяти. Все элементы имеют одно
имя - имя массива и отличаются индексами – порядковыми номерами в массиве.
Количество элементов в массиве называется его размером. Чтобы отвести в памяти
нужное количество ячеек для размещения массива, надо заранее знать его размер.
Резервирование памяти для массива выполняется на этапе компиляции программы.

6.1. Определение массива в Си/Си++

int a[100];//массив из 100 элементов целого типа
Операция sizeof(a) даст результат 400, т. е.100 элементов по 4 байта.
Элементы массива всегда нумеруются с 0.

…

Чтобы обратиться к элементу массива, надо указать имя массива и номер

элемента в массиве (индекс):

a[0] – индекс задается как константа,
a[55] – индекс задается как константа,
a[I] – индекс задается как переменная,
a[2*I] – индекс задается как выражение.

Элементы массива можно задавать при его определении:

int a[10]={1,2,3,4,5,6,7,8,9,10} ;

Операция sizeof(a) даст результат 40, т. е.10 элементов по 4 байта.

int a[10]={1,2,3,4,5};

Операция sizeof(a) даст результат 40, т. е.10 элементов по 4 байта. Если количество
начальных значений меньше, чем объявленная длина массива, то начальные элементы
массива получат только первые элементы.

int a[]={1,2,3,4,5};

Операция sizeof(a) даст результат 20, т. е.5 элементов по 4 байта. Длин массива
вычисляется компилятором по количеству значений, перечисленных при
инициализации.

6.2. Обработка одномерных массивов

При работе с массивами очень часто требуется одинаково обработать все

элементы или часть элементов массива. Для этого организуется перебор массива.

Перебор элементов массива характеризуется:

направлением перебора;

количеством одновременно обрабатываемых элементов;

характером изменения индексов.

По направлению перебора массивы обрабатывают :

слева направо (от начала массива к его концу);

справа налево (от конца массива к началу);

от обоих концов к середине.

Индексы могут меняться

линейно (с постоянным шагом);

нелинейно (с переменным шагом).

6.2.1. Перебор массива по одному элементу

Элементы можно перебирать:

Слева направо с шагом 1, используя цикл с параметром

for(int I=0;I<n;I++){обработка a[I];}
2)

Слева направо с шагом отличным от 1, используя цикл с параметром

for (int I=0;I<n;I+=step){обработка a[I];}
3)

Справа налево с шагом 1, используя цикл с параметром

for(int I=n-1;I>=0;I--){обработка a[I];}
4)

Справа налево с шагом отличным от 1, используя цикл с параметром

for (int I=n-1;I>=0;I-=step){обработка a[I];}

6.2.2 Формирование псевдо динамических массивов

При описании массива в программе надо обязательно указывать количество

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

Псевдо динамические массивы реализуются следующим образом:

при определении массива выделяется достаточно большое количество памяти:

const int MAX_SIZE=100;//именованная константа
int mas[MAX_SIZE];

пользователь вводит реальное количество элементов массива меньшее N.

int n;
cout<<”\nEnter the size of array<”<<MAX_SIZE<<”:”;cin>>n;

дальнейшая работа с массивом ограничивается заданной пользователем

размерностью n.

MAX_SIZE

Т. о. используется только часть массива.

6.2.3. Использование датчика случайных чисел для формирования

массива.

Датчик случайных чисел (ДСЧ) – это программа, которая формирует

псевдослучайное число. Простейший ДСЧ работает следующим образом:

Берется большое число К и произвольное

]

[



Формируются числа

=дробная_часть(

*К);

=дробная_часть(

*К); и т. д.

В результате получается последовательность чисел

,. . . беспорядочно

разбросанных по отрезку от 0 до 1. Их можно считать случайными, а точнее
псевдослучайными. Реальные ДСЧ реализуют более сложную функцию f(x).

В Си++ есть функция

int rand() – возвращает псевдослучайное число из диапазона 0..RAND_MAX=32767,

описание функции находится в файле <stdlib.h>.

Пример формирования и печати массива с помощью ДСЧ:

#include<iostream.h>

#include<stdlib.h>
void main()
{
int a[100];
int n;
cout<<”\nEnter the size of array:”;cin>>n;
for(int I=0;I<n;I++)
{a[I]=rand()%100-50;
cout<<a[I]<<” “;
}
}
В этой программе используется перебор массива по одному элементу слева

направо с шагом 1.

Задача 1
Найти максимальный элемент массива.
#include<iostream.h>
#include<stdlib.h>
void main()
{
int a[100];
int n;
cout<<”\nEnter the size of array:”;cin>>n;
for(int I=0;I<n;I++)
{a[I]=rand()%100-50;
cout<<a[I]<<” “;
}
int max=a[0];
for(I=1;I<n;I++)
if (a[I]>max)max=a[I];
cout<<”\nMax=”<<max”;
}
В этой программе также используется перебор массива по одному элементу

слева направо с шагом 1.

Задача 2

Найти сумму элементов массива с четными индексами.
#include<iostream.h>
#include<stdlib.h>
void main()
{
int a[100];
int n;
cout<<”\nEnter the size of

array:”;cin>>n;

for(int I=0;I<n;I++)
{a[I]=rand()%100-50;

Ввод массива

cout<<a[I]<<” “;
}
int Sum=0;
for(I=0;I<n;I+=2)
Sum+=a[I];//элементы с индексами

0, 2, 4… cout<<”\nSum=”<<Sum”;

}

//Второй способ
for(I=0;I<n;I++)
if(I%2==0)Sum+=a[I]; ];//элементы с

индексами 0, 2, 4…

cout<<”\nSum=”<<Sum”;

6.2.4. Перебор массива по два элемента

Элементы массива можно обрабатывать по два элемента, двигаясь с обеих сторон
массива к его середине:
int I=0, J=N-1;
while( I<J)

{обработка a[I] и a[J];I++;J--;}

Элементы массива можно обрабатывать по два элемента, двигаясь от начала к
концу с шагом 1(т. е. обрабатываются пары элементов a[1]и a[2], a[2]и a[3] и т. д.):
for (I=1;I<N;I++)
{обработка a[I] и a[I+1]}

Элементы массива можно обрабатывать по два элемента, двигаясь от начала к
концу с шагом 2 (т. е. обрабатываются пары элементов a[1]и a[2], a[3]и a[4] и т. д.)
int I=1;
while (I<N-1 )
{обработка a[I] и a[I+1];
I+=2;}

6.3. Классы задач по обработке массивов

К задачам 1 класса относятся задачи, в которых выполняется однотипная обработка
всех или указанных элементов массива.

К задачам 2 класса относятся задачи, в которых изменяется порядок следования
элементов массива.

К задачам 3 класса относятся задачи, в которых выполняется обработка нескольких
массивов или подмассивов одного массива. Массивы могут обрабатываться по одной
схеме – синхронная обработка или по разным схемам – асинхронная обработка
массивов.

К задачам 4 класса относятся задачи, в которых требуется отыскать первый элемент
массива, совпадающий с заданным значением – поисковые задачи в массиве.

6.3.1. Задачи 1-ого класса

Решение таких задач сводится к установлению того, как обрабатывается каждый

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

#include<iostream.h>
#include<stdlib.h>
void main()
{
int a[100];

int n;
cout<<”\nEnter the size of array:”;cin>>n;
for(int I=0;I<n;I++)
{a[I]=rand()%100-50;
cout<<a[I]<<” “;
}
int Sum=0;
for(I=0;I<n;I++)
Sum+=a[I];
Cout<<”Среднее арифметическое=”<<Sum/n”;
}

6.3.2. Задачи 2-ого класса

Обмен элементов внутри массива выполняется с использованием

вспомогательной переменной:
int R=a[I];a[I]=a[J]; a[J]:=R; // обмен a[I] и a[J] элементов массива.

Пример1.
Перевернуть массив.
//формирование массива
for(int i=0,j=n-1;i<j;i++,j--)
{int r=a[i];
a[i]=a[j];
a[j]=r;}
//вывод массива
Пример 2.
Поменять местами пары элементов в массиве: 1и2, 3 и 4, 5 и 6 и т. д.
for(int i=0;i<n-1;i+=2)
{int r=a[i];
a[i]=a[i+1];
a[i+1]=r;}
Пример 3.
Циклически сдвинуть массив на к элементов влево (вправо).

int k,i,t,r;

cout<<"\nK=?";cin>>k;

for(t=0;t<k;t++)

{

r=a[0];

for(int i=0;i<n-1;i++)

a[i]=a[i+1];

a[n-1]=r;

}

6.3.3. Задачи 3-ого класса

При синхронной обработке массивов индексы при переборе массивов меняются

одинаково.