учебное пособие. Часть1. Информатика

6.Эргономичность – дружественный интерфейс.

7.Читабельность.

8.Гибкость – возможность модификации и модернизации благодаря

структурированности и документированности программы.

8.Переносимость – возможность работать не только на том компьюте- ре, где разрабатывалась, но и на других, а также с небольшими модифика- циями в других операционных системах.

9.Удобство и простота сопровождения.

201

4.ОБРАБОТКА МАССИВОВ

Впрограммировании используется следующее определение массива: массив – это совокупность однотипных элементов данных.

Массив – не простой тип данных, а структурированный, т. е. имеет один или более компонент и построен на основе других типов. Компоненты массива называют элементами. Все элементы массива имеют общее имя. Об- ращение к конкретному элементу производится с помощью индекса. Важной отличительной чертой массива является однотипность элементов массива. В качестве типа используется любой простой или структурированный тип (т. е. возможна вложенность типов). В языке С++ количество элементов массиве фиксировано и определяется во время трансляции. Это является недостатком языка, поскольку не во всех задачах можно заранее определить количество элементов в массиве (возможность использования динамических массивов рассматривается в разд. 4.4).

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

Одномерные массивы имеют аналогию с таким понятием в математике, как вектор. Описание переменной типа массив в языке С++ задается сле-

дующим образом:

<тип> <идентификатор массива>[<t>];

Здесь <тип> – тип элементов массива (любой тип языка С++); <имя массива> – правильный идентификатор; <t> – количество элементов массива.

Ниже приведены примеры описания одномерных массивов:

int f[10] ; char mas[100] ; float b[5]

202

В языке программирования С++ индексы элементов массива изменяются от 0. Индекс последнего элемента на единицу меньше количества элементов в массиве. Размерность массива – величина произволь- ная, но суммарная длина внутреннего представления любого массива не может быть больше 65520 байт. Так как память выделяется под массив во время компиляции программы, границы изменения индексов должны быть константами, или константными выражениями.

Обращение к элементам массива осуществляется по их индексам:

f[1]=0;

mas[99]='a'; b[3]=1.13;

При обработке массивов возникают такие задачи, как ввод

элементов массива, нахождение суммы, произведения, среднего и т. д., поиск некоторого элемента в массиве, сортировка элементов

массива, вывод элементов масси- ва. Примеры программ и алго-

ритмов для решения типовых за- дач рассмотрены ниже.

На рис. 17 представлена

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

Программа приведена в примере

pr15.

//Пример pr15 #include <iostream> #include <stdlib> using namespace std; int main ()

n, sum;//Количество элементов в массиве и их сумма cout << "\nВведите число элементов массива:";

cin >> n;

// Формированиемассиваспомощьюдатчикаслучайныхчисел randomize (); //Инициализация датчика случайных чисел sum = 0;

for (i = 0; i<n; i++)

{

203

a[i] = random (10); sum = sum+a[i];

}

cout <<"Сформированный массив:\n"; for (i = 0; i<n; i++)

cout<< a[i] << ' '; cout<< "\n s = "<< sum ; return 0;

}

В приведенном примере в качестве исходных данных вводится размер массива. Использование константы N1 делает программу более универсаль- ной, позволяя работать с целочисленными массивами размерностью от 1 до 100. Если будет введено число, меньшее 1 и большее 100, то возникнет ошибка. В языке С++ принято для идентификаторов констант использовать заглавные буквы. Для формирования массива (во всех случаях, когда требу- ется перебор всех элементов массива) лучше всего подходит оператор цикла со счетчиком. В каждой итерации оператора цикла очередному элементу массива (индекс элемента является переменной цикла) присваивается псев- дослучайное число. Результатом работы программы является сформирован- ный массив и сумма элементов этого массива.

На рис. 18 приведена графическая схема алгоритма определения максимального элемента массива и замены его числом 100 (программа pr16).

//Пример pr16 #include <cstdio> using namespace std; int main ()

{

const int N1 = 100; //Максимальный размер массива int a[N1], // Mассив

i, //Индекс элемента массива

n, //Количество элементов в массиве imax; //Индекс максимального элемента

printf ("\nВведите число элементов массива:"); scanf ("%d",&n);

printf ("Введите элементы массива"); for ( i = 0; i<n ; i++ )

scanf ( "%d", &a[i] );

imax =0;//Пpедполагаем,чтопеpвыйэлементмаксимальный} //Если текущий элемент массива больше

204

int main ()

{

float a[N1], // Массив

d; // Дополнительнаяпеpеменнаядляобмена //местами двух элементов массива

printf ( "\n Введите число элементов массива:" ); scanf ( "%d", &n );

printf ( "Введите элементы массива: \n" ); for ( i = 0; i<n; i++ )

{

const int N1 = 100; // Максимальный размер массива int i, // Индекс элемента массива

n, // Количество элементов в массиве fl; // Флаг пеpестановок

printf ( "Введите %d-й элемент массива:", i+1 ); scanf ( "%f", &a[i] );

}

printf ( "\nИсходный массив: \n" ); for ( i = 0; i<n; i++ )

printf( "%7.2f", a[i] ); // Соpтиpовка

//В очередной раз просматриваем элементы массива for ( i = 0; i<n-1; i++ )

if ( a[i] > a[i+1] ) //Сравниваем два элемента { // и меняем их местами

d = a[i];

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

fl = 0; //Если был обмен, то флаг опускаем

}

}

while ( !fl ); //Если флаг не опускался, то массив //отсортирован

printf ( "\n Обpаботанный массив: \n" ); for ( i = 0; i<n; i++ )

printf ( "%7.2f", a[i] ); return 0;

}

206

ai ai+1

ai

ai ai+1

ai+1

Рис. 19. Алгоритм PR17

Основной цикл do while прекращает выполняться, когда значение переменной fl остается равной 1

после выполнения вложенного цикла for. Это происходит в том случае, если ни одну пару элементов не удается переставить, что указывает на то, что все элементы стоят на своих местах.

207

4.2. Массивы и указатели

Известно, что данные хранятся в ячейках памяти компьютера. Все ячейки памяти пронумерованы. Номера ячеек памяти называются адресами. Указатели используются для работы с адресами. Указатель – это некоторое символическое представление адреса. Это означает, что будем работать с пе-

ременными, хранящими эти адреса. Описываются такие переменные сле- дующим образом:

<тип> *<идентификатор>;

Такое описание синтаксически отличается от описания простой пере- менной только наличием знака * перед именем переменной. Как видно из описания, указатель всегда связывается с переменной какого-то определен- ного типа. Это позволяет определить, сколько байт памяти необходимо вы- делить по указанному адресу. В переменной типа указатель хранится адрес

первого байта, выделенного участка памяти:

int *ptr, *ptr1; float *p, *p1;

Над указателями можно выполнять следующие операции [6]:

• Одному указателю можно присвоить значение другого указателя, ес- ли они ссылаются на один и тот же тип:

ptr = ptr1; p1 = p;

• Значение указателя можно увеличить или уменьшить на константную величину:

ptr++;

ptr1 = ptr1-5; p1 = p1+2;

• На самом деле ptr увеличивается не на 1, а на столько, сколько байт занимает целое число. Пе- ременная ptr1 уменьшается на 5 умноженное на количество байт, выделяемых под целое число.

• Указателю можно присвоить значение адреса. Для получения адреса используется знакомый

значок &:

int a, *ptr; ptr = &a;

• Можно использовать операцию косвенной адресации. Эта операция обозначается значком * и позволяет получить доступ к значению переменной, на которую ссылается указатель:

int n = 12, *ptr, a ; ptr = &n;

а = *ptr;

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

• Можно получить разность двух указателей. Это используется чаще всего для указателей, ссы- лающихся на один и тот же массив.

Здесь следует обратить внимание на то, что символы * и & имеют разное назначение в зависимости от кон- текста, в котором они используются.

208

Очень часто в С++ при работе с массивами вместо индексов используются указатели. Преимущество ис- пользования указателей в массивах состоит в том, что арифметические операции над указателями выполня- ются быстрее, если мы работаем с подряд идущими элементами массива. Если выбор элементов случайный, то быстрее и нагляднее работа с индексами. Имя массива является указателем на первый элемент массива. Элементы массива располагаются в непрерывной области памяти. Эти два положения позволяют переме- щаться по элементам массива, используя указатель. Пусть:

int a[10], *ptr;

ptr=a;

тогда к пятому элементу массива можно обратиться:

a[4]

*(a+4)

*(ptr+4)

и все эти обращения будут равносильны.

Напишем программу из примера pr15 c использованием указателей.

//Пример pr15 с указателями int main()

{

const int N1 = 100; //Максимальный размер массива int a[N1], *ptr, //Указатель на элементы массива

n, s; //Количество элементов в массиве и их сумма printf ( "\n Введите число элементов массива:" ); scanf ( "%d", &n );

//Формированиемассиваспомощьюдатчикаслучайныхчисел randomize ();//Инициализация датчика случайных чисел for ( ptr = a; ptr-a < n; ptr++ )

*ptr = random (10);

printf ( "Полученный массив: \n" ); for ( ptr = a; ptr-a < n; ptr++ ) printf ( "%5d", *ptr );

s = 0; // Нахождение суммы for ( ptr = a; ptr-a < n; ptr++ )

s = s+*ptr;

printf ( "\n s= %5d", s ); return 0;

}

Начинающие программисты испытывают самую большую сложность при использовании операции косвенной адресации. Например, в заголовке первого оператора цикла записано prt = a. Это означает, что переменной prt типа указатель присваивается адрес нулевого элемента массива а. В теле цикла запи- сано *ptr = random(10). В этом случае переменной, хранящейся по адресу, на который указывает ptr, присваивается значение, полученное с датчика случайных чисел. Имя массива a как указатель на нулевой элемент массива является константой, а указатель prt является переменной. Разность prt – a дает по- рядковый номер элемента массива.

Составим программу с использованием указателей для примера pr16.

// Пример pr16 с указателями int main ()

{

const int N1 = 100; // Максимальный размер массива int a[N1], // Массив

209

*ptr, // Указатель на элементы массива n,//Количество элементов в массиве

*ptrmax; // Указатель на максимальный элемент printf ( "\n Введите число элементов массива:" ); scanf ( "%d", &n );

printf ( "Введите элементы массива" ); for ( ptr = a; ptr-a < n; ptr++ )

scanf ( "%d", ptr );

ptrmax =a;//Пpедполагаем,чтопеpвыйэлементмаксимальный for ( ptr = a; ptr-a < n; ptr++ )

if (*ptrmax < *ptr) ptrmax = ptr;

printf ( "\n Максимальный элемент =%d", *ptrmax ); printf ( "\n Обpаботанный массив:" );

for ( ptr = a; ptr-a < n; ptr++ ) printf ( "%5d", *ptr );

return 0;

}

Контрольные вопросы

1.Дайте определение массива.

2.Чем отличается индекс массива от элемента массива?

3.Чем отличается N1 от n в приведенных примерах программ?

4.Составьте фрагмент схемы алгоритма, соответствующий следующему фрагменту программы: for ( i = 0; i<n; i = i+2 ) k = k*a[i];

5.Что такое указатель?.

6.Как описываются указатели?

7.Какие операции можно выполнять над указателями?

8.Какую роль в приведенной в этом разделе программе сортировки одномерного массива играет переменная fl?

9.Напишите программу, которая сортирует одномерный массив следующим образом: находит наи- меньший элемент и меняет его местами с первым элементом массива. Cреди всех, кроме первого, снова на- ходит наименьший и ставит его на второе место и т. д.

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

Двумерные массивы имеют аналогию с таким понятием в матема- тике, как матрица. Двумерный массив – это одномерный массив, эле- ментами которого являются одномерные массивы (рис. 20).

210