94

Доступ к отдельному элементу массива осуществляется с помощью индекса. Индекс описывает позицию элемента внутри массива. В C++ первый элемент массива всегда имеет нулевой индекс. Поскольку массив sample со-

держит 10 элементов, его индексы изменяются от 0 до 9. Чтобы получить доступ к элементу массива по индексу, достаточно указать нужный номер элемента в квадратных скобках. Так, первым элементом массива sample является sample[0], а последним – sample[9]. Например, следующая программа помещает в массив sample числа от 0 до 9.

#include <stdio.h> void main(void)

{

int sample[10]; // Эта инструкция резервирует область

//памяти для 10 элементов типа int.

//Помещаемвмассивзначения. for(int i=0; i<10; i++) sample[i]=i;

//Отображаеммассив.

for(int k=0; k<10; k++) printf(" %d", sample[k])

}

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

int i[7];

for(int j=0; j<7; j++) i[j] = j;

массив i будет выглядеть так

10.4. Методика составления программ поиска и сортировки

10.4.1. Задача поиска

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

Пример. Найти наибольшее из данных n чисел. Сформируем массив x[n], в котором размещены эти числа. Введем новую переменную, например, z, которая должна получить значение, равное наибольшему из рассматриваемых чисел. Особое внимание следует уделить выбору начального значения z.

95

Необходимо предусмотреть, чтобы в процессе поиска начальное значение z по крайней мере один раз было заменено числом из массива x. В некоторых случаях заранее указать такое значение z затруднительно, поэтому в качестве начального значения принимается первый элемент массива х[0], а циклическая работа алгоритма начинается со второго элемента массива. Именно по этому принципу построен следующий фрагмент программы поиска максимального элемента массива:

int n=10, z, j, x[10];

. . .

z=x[0]; j=0; for(int i=1; i<n; i++)

if(z<x[i]) { z=x[i]; j=i; }

В результате вычислений переменная z получит значение, равное наибольшему числу в массиве x.

10.4.2. Задача сортировки и упорядочения массива

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

Пример. Дан массив a[n]. Необходимо переставить этот массив таким образом, чтобы элементы массива были размещены в порядке возрастания их величины. Ход решения этой задачи следующий:

1.В исходном массиве a отыскать наименьший по величине элемент. Запомнить номер этого элемента.

2.Найденный элемент поменять местами с первым элементом масси-

ва.

3.Повторить поиск наименьшего элемента в массиве со второго до n- го элемента.

4.Новый наименьший элемент поменять местами со вторым элементом массива.

5.Этапы 3 и 4 повторить с уменьшающимся остатком массива до полного упорядочения массива.

Рассматриваемая задача решается с помощью следующего фрагмента программы:

for(int i=0; i<n-1; i++) { z=a[i];

k=i;