Решение задач с использованием массивов

Цель работы

Освоение методов работы с массивами на языке С++; получение навыков работы с указа­телями.

 

Подготовка к работе

При подготовке к работе следует изучить методы организации пользовательских типов. Необходимо ознакомиться с основными предопределёнными типами данных «Указатель», «Вектор», а также научиться использовать переменные типа «Ссылка» [лекции 9, 10].

 

Теоретическая часть.

Если требуется работать с группой величин одного типа, их располагают в памяти последовательно и дают им общее имя, а различают по порядковому номеру. Такая последовательность однотипных величин называется массивом (вектором).

Двумерный массив (матрица) представляется в С++, как вектор, состоящий из векторов. Для его описания указываются в квадратных скобках две размерности. Первый индекс матрицы всегда воспринимается как номер строки, второй – как номер столбца. Матрица располагается в памяти также в одном участке памяти, но построчно, т.е. сначала располагаются элементы нулевой строки (или вектор, представляющий собой нулевую строку), затем – первой, после – третьей и т.д. Если массив определяется с помощью операторов описания, то его размерности должны быть константами или константными выражениями.

При просмотре массива от начала в первую очередь изменяется самый правый индекс (цикл, организованный по этому индексу, самый внутренний), в последнюю очередь изменяется самый левый индекс (цикл, организованный по этому индексу, внешний)

Каждый индекс может изменяться от 0 до значения соответствующей размерности, уменьшенной на единицу.

К элементу массива можно обратиться

- явно, т.е. указать после имени массива его порядковый номер в векторе или номер строки и столбца, в которых находится элемент матрицы;

- посредством указателя.

Указатели - особый тип данных, предназначенные для хранения адреса в па­мяти. В языке C определены два вида указателей: указатели на объект без определенного типа- void*; указатели на объекты определенного типа.

Указатели на объекты определенного типа бывают также двух видов: указатели константы и указатели переменные. Указатели переменные определяются в операторах объявления с по­мощью символа “*”, помещенного перед идентификатором указателя. Например:

int*p;

long a,*c;,

где int* - тип указатель на некоторую переменную типа int; p - идентификатор указателя на пе­ременную; c - идентификатор указателя на некоторую переменную типа (long*).

Инициализация указателя выполняется с помощью оператора взятия адреса - “&”. Так если в теле программы встретился оператор объявления “long L;”, тогда использования опе­ратора- &L даст в результате адрес размещенного в памяти значения переменной L. Ини­циализация указа­телей может быть выполнена в разделе оператора объявления

long L,*a=&L,G,*p; // a указывает на L.

p=&G; // p указывает на G

 

Особое место занимает указатель значение которого равно 0 - null. Этот указатель исполь­зу­ется в качестве специального флага условия. Например: при работе с динамическими пе­ре­менными исчерпана свободная память; конец динамической структуры данных (списка, стека, дерева).

При работе с указателями, как видно, часто используется операция взятия адреса -“&”. По­этому необходимо знать, хотя они и очевидные, ограничения накладываемые на эту опера­цию. Эти ограничения следующие: нельзя определить адрес символической константы; нельзя оп­ределить адрес арифметического выражения; нельзя определить адрес переменной, описанной как register.

Операция разыменования - одноместная операция (‘*’) с тем же приоритетом и ассоциа­тив­ностью справа налево, что и другие одноместные операции. Смысл этой операции со­стоит в переходе от указателя к значению на который он указывает. Таким образом, если в программе имеется объявление

int a,*p; // p - указатель на int

a=1;

.........

p=&a;

то выражение

++*p; // *p=*p+1; или a=a+1; (a=2)

т.е. означает - увеличить значение переменной целого типа a на единицу.

Как видно, из вышеописанного примера, унарная операция разыменования -‘*’, исполь­зуе­мая в теле программы, идентифицируется компилятором по наличию соответствующего объяв­ления указателя.

При программировании с использованием переменных типа указатель необходимо обращать особое внимание на порядок выполнения действий. Например:

*p++; // соответствует *(p+1) или (*p)++

++*p; // *p=*p+1

 

Применение меха­низма указате­лей основано на использовании факта, что имя вектора является указателем - константой, рав­ной адресу начала вектора - первого байта первого элемента вектора (arr1==&arr1[0]). В результате этого, используя операцию разыменования “*” можно обес­печить доступ к лю­бому элементу вектора. Так, эквивалентны будут обращения к i-му эле­менту вектора с исполь­зованием индекса - arr1[i] и ссылки *(arr1+i),поскольку (arr1+i)==&arr1[i].

Обращение к элементам многомерных векторов также может производится как классическим спосо­бом - путем указания значений индексов, например,

V[1][2]=3;,

так и с использованием механизма указателей

*(*(V+1)+2)=3; // *(V[1]+2)=3; или V[1][2]=3.

В данном случае сначала следует обратиться к первой строке массива, т.е. к одномерному массиву V[1]. Для этого надо прибавить к адресу начала массива (V) смещение, равное номеру строки, и выполнить разыменование: (V+1). При сложении указателя с константой учитывается длина адресуемого элемента, т.е. 1 * (5 * sizeof(int)), поскольку элементом является строка, состоящая из 5 элементов типа int.

Далее требуется обратиться ко второму элементу полученного массива. Для получения его адреса опять применяется сложение указателя с константой (т.е. 2 * sizeof(int)), а затем применяется операция разыменования для получения значения элемента: *(*(V+1)+2).

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

- операции new;

- функции malloc (устаревший способ).

Адрес начала такого массива хранится в переменной, называемой указателем. Например:

int n=10; // количество элементов в векторе, м.б. и переменной

int *a = new int[n]; /* описание указателя на целую величину,

которому присваивается адрес начала непрерывной области динамической памяти, необходимой для хранения n величин типа int*/

double *b = (double *)malloc(n * sizeof (double));

/* для выделения памяти под n элементов типа double с использованием функции malloc */

...

int n;

const int m=5;

cin>>n:

int **b = (int **) new int [n][m]; /* b – указатель на указатель, поэтому перед присвоением требуется выполнить преобразование типа ((int **)) */

int (*a)[m] = new int [n][m]; /* a – указатель на массив из m элементов типа int */

...

int n_str, n_stl;

cout<<”введите кол-во строк и столбцов:”;

cin>>n_str>>n_stl;

int **d = new int *[n_str];

for (int i=0; i<n_str; i++)

d[i] = new int [n_stl]; // самый универсальный способ

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

Если динамический массив в какой-то момент работы программы перестает быть нужным и мы собираемся впоследствии использовать эту память повторно, необходимо освободить ее с помощью операции delete[], например:

delete [] a; // размерность массива не указывается!

Рассмотрим пару примеров обработки массивов.

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

Алгоритм следующий. Для вычисления среднего арифметического требуется найти общую сумму элементов массива, после чего разделить ее на их количество. Порядок просмотра массива (по строкам или столбцам) роли не играет. Определение количества положительных элементов каждой строки требует просмотра матрицы по строкам. Обе величины вычисляются при одном просмотре матрицы. Блок-схема алгоритма приведена на рисунке 1.

#include <iostream.h>

#include <iomanip.h>

void main(){

const int n_str=10, n_stl=20; // кол-во строк и столбцов

int a[n_str][n_stl];

int i, j;

cout<<”Введите элементы масива:”<<endl;

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

for(j=0; j<n_stl; j++) cin>>a[i][j];

for(i=0; i<n_str; i++){

for(j=0; j<n_stl; j++) cout<<setw(4)<<a[i][j]<<” “;

cout<<endl; // вывод матрицы на экран

}

int kol_vo;

float S=0.;

for(i=0; i<n_str; i++){

kol_vo = 0;

for(j=0; j<n_stl; j++){

S+=a[i][j];

if (a[i][j] > 0) kol_vo++;

}

cout<<”Строка:”<<i<<”Кол-во:”<<kol_vo<<endl;

}

S /= n_str * n_stl;

cout<<”Среднее арифметическое:”<<S<<endl;

}

 

 

 

 

n=10 m=20

 

 

 

 

k=k+1

Да

 

Нет

 

 

Рис.2. Блок-схема алгоритма решения задачи.

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

В программе следует обратить внимание на два момента:

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

- Место инициализации суммы и количества. Сумма обнуляется перед циклом просмотра всей матрицы, а количество положительных элементов – перед циклом просмотра очередной строки, поскольку для каждой строки его вычисление начинается заново. Операторы инициализации накапливаемых в цикле величин лучше записывать непосредственно перед циклом, в котором они вычисляются.

После ввода значений предусмотрен их контрольный вывод на экран. Для того, чтобы элементы матрицы располагались один под другим, используется манипулятор setw(), устанавливающий для очередного выводимого значения ширину поля в четыре символа. Для использования манипулятора необходимо подключить к программе заголовочный файл <iomanip.h>. Каждая строка матрицы начинается с новой строчки (выводится символ перевода строки endl).

 

2. Пример программы вычисляющей сумму элементов главной диагонали матрицы

#include<stdio.h>

void main()

{int V[ ][3]={1,2,3,

4,5,6,

7,8,9}

int i, s1, s2; s1=0; s2=0;

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

s1+=V[i][i]; // обращение явное

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

s2+=*(*(V+i)+i); // обращение через указатель

printf(“s1=%d, s2=%d “,s1,s2);

}

Задание.

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

Обращение к элементам массива произведите как классическим способом, так и посредством указателя.

Измените блок ввода элементов массива, попробовав ввод с клавиатуры (интерактивный ввод) и с использованием генератора случайных чисел. После отладки эти варианты ввода оставьте в программе, «забив» комментариями.

 

5. Требования к отчету по лабораторной работе:

Отчет должен содержать:

1) блок-схему алгоритма задачи;

2) распечатку или текст программы с комментариями;

3) результаты работы программы.

 

Варианты заданий.

 

Исходные числовые данные выбираются произвольно.

1. Вычислить сумму положительных и количество отрицательных элементов многомерного вектора v[5][5].

2. Заданы два вектора X и Y длиной по десять элементов. Трактуя их как координаты то­чек плоскости, вычислить расстояние между ними.

3. Задан вектор X[20]. Положительные числа переписать в массив Y, а отрицательные в массив W.

4. Поменять местами минимальный и максимальный элементы главной диагонали мат­рицы (многомерного вектора v[5][5]).

5. В векторе из 20 элементов переставить элементы так, чтобы сначала располагались все отрицательные элементы, а затем все остальные элементы, без нарушения порядка их следования.

6. В целочисленной квадратной матрице (многомерном векторе v[5][5]) определить но­мера строк (значение векторов указателей на векторы), все элементы которых чётные, найти суммы элементов этих строк.

7. Найти произведение двух матриц (многомерных векторов) 5x6 и 6x5 элементов.

8. В многомерном векторе 4x6 элементов найти минимальный элемент и его индексы.

9. В матрице (многомерном векторе) 4x6 элементов поменять местами столбцы, содержа­щие минимальный и максимальный элементы. Учесть особенности языка. С++.

10. Отсортировать элементы третьей строки матрицы (многомерного вектора) 5x6 элемен­тов по возрастанию значений. Учесть особенности языка С++.

11. В многомерном векторе V[4][5] элементов заменить нулём максимальный и единицей максимальный элементы.

12. Заменить отрицательные элементы многомерного вектора V[4][5] нулями и найти и их количество.

13. В векторе V[23] поменять местами максимальный и минимальный элементы.

14. В векторе V[23] есть одинаковые числа. Найти количество наиболее часто встречаю­щихся одинаковых чисел.

15. Найти сумму трёх многомерных векторов размером 4x6 элементов.

16. В векторе V[23] найти произведение положительных элементов, стоящих на чётных местах, и количество всех отрицательных элементов.

17. В векторе V[23] найти среднее арифметическое всех отрицательных и среднее геомет­рическое положительных чисел.

18. В каждой строке матрицы (вектора указателей на векторы) V[4][5] найти количество элементов, делящихся на три, и записать их в вектор.

19. Отсортировать элементы главной диагонали матрицы (многомерного вектора) 6x6 эле­ментов по не убыванию.

20. В векторе V[23] найти максимальный элемент и вывести все числа, расположенные до него, в одной строке, а числа расположенные после него, в другой строке.

21. Заполнить квадратную матрицу (многомерный вектор) 8x8 элементов единицами в шахматном порядке.

22. Найти сумму чётных элементов многомерного вектора V[4][4], расположенных ниже главной диагонали.

23. Найти произведение положительных элементов второй строки (вектора) матрицы (многомерного вектора) V[4][4] и количество всех отрицательных элементов.

24. Все встречающиеся более одного раза элементы вектора V[25] переписать в другой вектор.

25. В векторе V[23] числа, находящиеся между максимальным и минимальным элементами поместить в другой вектор.

26. Даны два вектора G[15] и H[10]. Сформировать вектор, состоящий из одинаковых эле­ментов этих векторов.

27. Найти сумму нечётных элементов многомерного вектора V[4][4], расположенных выше главной диагонали.

28. Отсортировать элементы побочной диагонали матрицы (многомерного вектора) 6x6 элементов по возрастанию.

29. Поменять местами заданные в диалоге строки матрицы (многомерного вектора).

30. Возвести в квадрат все отрицательные элементы многомерного вектора B[6][6] и из­влечь корень из всех положительных.

 

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

1. Какие формы доступа к элементам массива предусмотрены синтаксисом языка С++?

2. Какие предусмотрены способы инициализации векторов?

3. Какой размерности могут быть вектора?

4. Могут ли быть объявлены массивы без указания количества элементов?

5. Может ли массив содержать элементы различных типов?

6. Предусмотрен ли контроль количества элементов массива?

7. Какая связь между массивами и указателями?

8. В чем отличие ссылки от указателя?

9. Чем отличается указатель-константа от указателя-переменной?

 

 

Лабораторная работа №3.