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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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];}

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

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

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

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

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

int mas[MAX_SIZE];

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

int n;

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

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

n

MAX_SIZE

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

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

Датчик случайных чисел (ДСЧ) – это программа, которая формирует псевдослучайное число. Простейший ДСЧ работает следующим образом:

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

2) Формируются числа х1 = дробная_часть (х0*К); х2 = дробная_часть (х1*К); и т. д.

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

В Си++ есть функция int rand() – возвращает псевдослучайное число из диапазона 0..RAND_MAX=32767, описание функции находится в файле <stdlib.h>.

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

#include<iostream.h> #include<stdlib.h> using namespace std; void main() { int a[100]; int n; cout<<”Enter the size of array:”;cin>>n; for(int i = 0; i < n; i++) {a[i]=rand()%100-50; cout<<a[i]<<” “; } }

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

1) Элементы массива можно обрабатывать по два элемента, двигаясь с обеих сторон массива к его середине:

int i = 0, j = n-1; while(i < j) {обработка a[i] и a[j]; i++; j--;}

 

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

for (i = 1; i < N; i ++) {обработка a[i] и a[i+1]}

 

3) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 2 (т. е. обрабатываются пары элементов a[1] и a[2], a[3] и a[4] и т. д.)

int i = 1; while (i < N-1) {обработка a[i] и a[i+1]; i+=2;}