cout<<endl; //перевод строки перед переходом к новой строке матрицы
}
Если требуется найти минимальный среди элементов квадратной матрицы, лежащих ниже главной диагонали, можно использовать следующий фрагмент программы:
Рассмотрим другой пример. Допустим, необходимо подсчитать сумму элементов побочной диагонали квадратной матрицы: Прежде всего необходимо правильно определить закономерность, выделяющую элементы побочной диагонали среди всех других элементов матрицы. Если для матрицы NxN выписать все элементы побочной диагонали с их индексами:
mas[0][N-1], mas[1][N-2],…, mas[N-2][1], mas[N-1][0],
то можно заметить закономерность: в i-й строке элемент побочной диагонали находится в N-i-1 строке. После того, как такая закономерность найдена (а эта задача при поиске решения зачастую становится одной из самых, с одной стороны, сложных, а с другой – творческих), составить алгоритм и код программы нетрудно. Хотя никогда не стоить забывать об эффективности реализации. Можно перебирать все элементы матрицы и обирать для суммирования только элементы, удовлетворяющие условию:
const int N=5;
double mas[M][M], Sum=0;
for (int i=0; i<M; i++)
for(int j=0;j<N; j++)
if(i==N-j-1)
Sum+=mas[i][j];
cout<<”Сумма элементов побочной диагонали матрицы:”<<Sum;
Такая реализация будет работать, но она избыточна по количеству перебираемых и сравниваемых элементов. Эффективнее будет сразу проходить только по элементам побочной диагонали, поскольку она имеет линейную природу:
const int N=5;
double mas[M][M], Sum=0;
for (int i=0; i<M; i++)
Sum+=mas[i][N-i-1];
cout<<”Сумма элементов побочной диагонали матрицы:”<<Sum;
Динамическое выделение памяти под двумерные массивы может оказаться актуальным по тем же причинами, которые перечислялись для одномерного случая: не всегда заранее известен размер массива. Первый способ выделения памяти под двумерный массив предполагает использование указателя на массив:
тип (* идентификатор) [константное_выражение]
Объект такого типа может адресовать целиком элементы двумерного массива – массивы одномерные. Память под двумерный массив выделяется следующим образом:
int (*ptm)[5]; //указатель на массив из 5-ти целых чисел
int n;
cin>>n;
ptm=new int [n][5]; //выделяем память под массив из n строк и 5-ти столбцов
for (int i=0;i<n;i++)
for (int j=0;j<5;j++)
ptm[i][j] =random(100); //обращение к элементам массива
…
delete [] ptm;
У рассмотренного примера один недостаток – нельзя варьировать количество столбцов в динамически создаваемой матрице, оно всегда должно быть равно 5 для совместимости по типу с указателем ptm. Количество строк в массиве при этом можно задавать с использованием переменной.
На языке Си выделение и освобождение памяти подобным образом можно осуществить с помощью кода:
typedef double (*arr2d)[5]; //новый тип данных – указатель на
// двумерный массив
arr2d m;
m=(arr2d)malloc(n*5*sizeof(double)); //выделение памяти под
//массив типа double из n строк и 5 столбцов
//работа с массивом
for(int i=0;i<n;i++)
for(j=0;j<5;j++)
m[i][j]=rand()/100.0;
for(int i=0;i<n;i++)
{for(j=0;j<5;j++)
printf("%lf\t", m[i][j]);
printf("\n");
}
free(m); //освобождение памяти
Динамический массив с переменным количеством как строк, так и столбцов можно эмулировать с использованием нескольких одномерных динамических массивов:
double ** m;
int N, K;
cout<<”Введите количество строк матрицы”;
cin>>N;
cout<<”Введите количество столбцов матрицы”;
cin>>K;
mas=new double*[N]; //выделяем память под массив указателей
for (int i=0;i<N;i++)
mas[i]=new double[K]; //выделяем память под i-ю “строку” матрицы
for (i=0; i<N;i++)
for (j=0;j<K;j++)
mas[i][j]=rand(); //обращение к элементам матрицы
Как выглядит определенный в последнем примере «двумерный массив» в памяти можно увидеть на рис. 8. Сначала выделяется память под массив из N указателей, каждый из которых будет адресовать одномерный массив, играющий роль соответствующей строки матрицы. Затем выделяется память под сами строки-одномерные массивы. Несмотря на то, что они могут не располагаться в памяти подряд, как строки настоящего двумерного массива, логическая структура матрицы будет поддерживаться и обращение m[i][j] предоставит доступ к j-му элементу массива, имитирующего i-ю строку матрицы. В этом нетрудно убедиться, если принять во внимание, что выражение m[i][j] преобразуется компилятором в *(*(m+i)+j).
Рис.8. Динамический двумерный массив в памяти программы
Динамический массив можно удалить из памяти в тот момент, когда пропадает необходимость в нем. Для массива, изображенного на рис. 8 это можно сделать с использованием следующего фрагмента кода:
for (int i=0; i<N; i++)
delete [] m[i];//освобождаем память из-под строк массива
delete [] m; //освобождаем память из-под массива указателей
При использовании языка Си вместо операций new и delete необходимо использовать функции malloc(calloc).
int N, K;//N и K – количество строк и столбцов матрицы
double **m; //указатель для массива указателей
//выделение динамической памяти под массив указателей
m = (double **) malloc(N*sizeof(double *));
for (int i=0; i<N; i++)
//выделение динамической памяти для массивов значений строк матрицы
m[i] = (float *) malloc(m*sizeof(double));
//работа с массивом
for (int i=0; i<N; i++)
for (int j=0; j<K; j++)
m[i][j]=(double)rand();
…
//освобождение памяти выделенной под массив
for (int i=0; i<n; i++)
free (m[i]);
free (m);
Разговор о массивах, способах их определения и манипуляции его содержимым в языке Си++ был бы неполным без упоминания классов библиотеки STL. Эта библиотека в настоящее время стала частью стандарта языка Си++ и представляет собой набор контейнеров, разработанных согласно принципам объектно-ориентированного программирования, описывающих поведение таких программных объектов, как массив, двусвязный список, дек, множество, очередь и др., а также вспомогательных классов и функций для доступа к содержимому контейнеров. Подробное описание этой библиотеки выходит за рамки настоящих указаний, тем более что знакомство с ней требует освоение объектно-ориентированной парадигмы программирования. Однако, примеры базовых средств работы с массивами средствами объектов библиотеки STL определят новые ориентиры в изучении рассматриваемой темы.
Для работы с динамическими массивами библиотека STL предлагает шаблон класса vector, который можно конкретизировать для требуемого типа данных. Сам контейнер vector предлагает ряд методов для изменения свойств вектора (вставка новых и удаление имеющихся элементов, изменение размера вектора, изменение значений элементов). Ряд операций над вектором (сортировка, нахождение минимума и максимума, поиск элементов по значению, слияние массивов, перестановки по заданным алгоритмам и др.) можно выполнить с использованием обобщенных алгоритмов. Рассмотрим пример работы с массивом с использованием контейнера vector.
#include <vector> //библиотека контейнера vector
#include <algorithm> //библиотека обобщенных алгоритмов
#include <iostream>
using namespace std;
int main()
{
vector <int> vec(20); //объявляем массив из 20 целых чисел
for (int i=0;i<vec. size();i++)
vec[i]=rand(); //заполняем масив случайными числами
sort(vec.begin(),vec.end()); //сортируем содержимое массива от
//начальной (vec.begin()) до конечной (vec.end()) позиции
for (int i=0;i<vec. size();i++)
cout<<vec[i]<<' '; //выводим содержимое массива на экран
vec.erase(vec.begin()+5,vec.begin()+10); //удаляем элементы
//массива с 5-го по 9-й
cout<<vec.size()<<'\n'; //теперь размер массива - 15 элементов
vec.pop_back(); //удалить последний элемент массива
vec.push_back(1); //добавить в конец массива элемент со значением 1
//находим макимальный элемент массива
cout<<"Максимальный элемент
массива"<<*max_element(vec. begin(), vec. end());
//меняем порядок следования элементов массива с 5-го по 9-й
reverse(vec. begin()+5,vec. begin()+10);
for (int i=0;i<vec. size();i++)
cout<<vec[i]<<' '; //выводим содержимое массива на экран
return 0;
}
Безусловно, на данном этапе изучения языка программирования Си++ не все детали последнего листинга могут быть понятны. Однако, можно уловить основный смысл примера – большинство алгоритмов, рассмотренных ранее в настоящих указаниях, эффективно реализованы в библиотеке STL в виде готовых функций, и задачей программиста становится правильное использование функций в программе для решения практических задач. Более подробно с возможностями библиотеки STL можно познакомиться в [7].
После знакомства с подобными высокоуровневыми средствами работы с массивами очень важно помнить, что базовые знания о массивах и алгоритмах их обработки, рассмотренные в настоящих указаниях не являются устаревшим рудиментом, эхом прошлых веков. Знания того, по каким алгоритмам работают те или стандартные функции позволит сделать более осознанный выбор в случае, когда для решения задачи есть несколько инструментов. Представления о том, что происходит в памяти при определении статического или динамического массива помогут быстрее решение в нестандартной ситуации, для которой не предусмотрено заранее заготовленной функции в той или иной библиотеке. Наконец, библиотеки функций и классов тоже пишут программисты и, не имея представления о базовых принципах работы массивов, невозможно подняться на высокий уровень абстракции для самостоятельной реализации подобных программных объектов.
Контрольные вопросы
1. Дайте определение массива?
2. В каких случаях в программах необходимо использовать массивы?.
3. Как определяется статический одномерный массив в языке Си?
4. Что такое динамический массив? Как он определяется в программах на языках Си и Си++? Сравните свойства динамического и статического массивов.
5. Как осуществляется начальная инициализация одномерного статического массива на языке Си?
6.В чем состоит сортировка массива? Опишите принцип работы одного из алгоритмов сортировки (по заданию преподавателя).
7.Каковы критерии эффективности работы алгоритмов сортировки? Что можно сказать об эффективности работы алгоритма сортировки «пузырьком»?
8.Что такое динамические массивы? В чем их достоинства по сравнению со статическим? Как выделяется память под динамические массивы?
9. Как определяются статические двумерные массивы в языке Си? Как можно осуществить начальную инициализацию их элементов?
10. Какие способы динамического выделения массивов в языках Си и Си++ Вы знаете? В чем их особенности?
Порядок выполнения работы
1. Ознакомьтесь с теоретическими основами использования массивов в программах на языках Си и Си++ в настоящих указаниях и конспектах лекций.
2. Получите вариант задания у преподавателя.
3. Составьте алгоритм решения задачи согласно варианту задания, оформите его в графической форме.
4. Используя разработанный алгоритм, напишите программу.
5. Отладьте разработанную программу и покажите результаты работы программы преподавателю.
6. Составьте отчет по лабораторной работе.
7. Отчитайте работу преподавателю.
Содержание отчета
Отчет по лабораторной работе должен содержать следующие сведения:
- название и цель работы;
- вариант задания;
- графическую схему алгоритма решения задачи;
- листинг разработанной программы с комментариями;
- результаты работы программы
Пример выполнения лабораторной работы.
1.В массиве целых чисел из n элементов перемножить элементы, лежащие между минимальным и максимальным.
Код программы:
#include <iostream>
#include <windows. h>
using namespace std;
int main()
{
const int n=10;
int i, k,l;
double m[n];
for(i=0;i<n;i++)
cin>>m[i];
double sum=0,t; //sum – сумма элементов между
//минимальным и максимальным
int imin,imax; //номер минимального и максимального элементов
//массива
imin=imax=0;
for(i=l;i<n;i++)
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
