Двумерные динамические массивы

Цель лекции: изучить объявление, выделение и освобождение памяти под двумерные динамические массивы, обращение к элементам, научиться решать задачи с использованием двумерных динамических массивов на языке C++.

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

Динамическим массивом называют массив с переменным размером, то есть количество элементов может изменяться во время выполнения программы.

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

Объявление двумерных динамических массивов

Под объявлением двумерного динамического массива понимают объявление двойного указателя, то есть объявление указателя на указатель.

Синтаксис:

Тип ** ИмяМассива;

ИмяМассива – идентификатор массива, то есть имя двойного указателя для выделяемого блока памяти.

Тип – тип элементов объявляемого динамического массива. Элементами динамического массива не могут быть функции и элементы типа void.

Например:

int **a; 
float **m;

Выделение памяти под двумерный динамический массив

При формировании двумерного динамического массива сначала выделяется память для массива указателей на одномерные массивы, а затем в цикле с параметром выделяется память под одномерные массивы. На рис 26.1 представлена схема динамической области памяти, выделенной под двумерный массив.

При работе с динамической памятью в языке С++ существует 2 способа выделения памяти под двумерный динамический массив.

1) при помощи операции new, которая позволяет выделить в динамической памяти участок для размещения массива соответствующего типа, но не позволяет его инициализировать.

Синтаксис выделения памяти под массив указателей:

ИмяМассива = new Тип * [ВыражениеТипаКонстанты];

Синтаксис выделения памяти для массива значений:

ИмяМассива[ЗначениеИндекса] = new Тип [ВыражениеТипа
Константы];

ИмяМассива – идентификатор массива, то есть имя двойного указателя для выделяемого блока памяти.

Тип – тип указателя на массив.

ВыражениеТипаКонстанты – задает количество элементов (размерность) массива. Выражение константного типа вычисляется на этапе компиляции.

Например:

int n, m;//n и m – количество строк и столбцов матрицы 
float **matr; //указатель для массива указателей
matr = new float * [n]; //выделение динамической памяти 
                          под массив указателей
for (int i=0; i<n; i++)
  matr[i] = new float [m]; //выделение динамической памяти 
                           для массива значений

При выделении динамической памяти размеры массивов должны быть полностью определены.

2) при помощи библиотечной функции malloc (calloc), которая предназначена для выделения динамической памяти.

Синтаксис выделения памяти под массив указателей:

ИмяМассива = (Тип **) malloc(N*sizeof(Тип *));

или

ИмяМассива = (Тип **) calloc(N, sizeof(Тип *));

Синтаксис выделения памяти для массива значений:

ИмяМассива[ЗначениеИндекса]=(Тип*)malloc(M*sizeof(Тип));

или

ИмяМассива[ЗначениеИндекса]=(Тип*)calloc(M,sizeof(Тип));

ИмяМассива – идентификатор массива, то есть имя двойного указателя для выделяемого блока памяти.

Тип – тип указателя на массив.

N – количество строк массива;

M – количество столбцов массива.

Например:

int n, m;//n и m – количество строк и столбцов матрицы 
float **matr; //указатель для массива указателей
matr = (float **) malloc(n*sizeof(float *)); 
//выделение динамической памяти под массив указателей
for (int i=0; i<n; i++)
  matr[i] = (float *) malloc(m*sizeof(float));
  //выделение динамической памяти для массива значений

Так как функция malloc (calloc) возвращает нетипизированный указатель void *, то необходимо выполнять его преобразование в указатель объявленного типа.

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

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

Освобождение памяти, выделенной под двумерный динамический массив, также осуществляется 2 способами.

1) при помощи операции delete, которая освобождает участок памяти ранее выделенной операцией new.

Синтаксис освобождения памяти, выделенной для массива значений:

delete ИмяМассива [ЗначениеИндекса];

Синтаксис освобождения памяти, выделенной под массив указателей:

delete [] ИмяМассива;

ИмяМассива – идентификатор массива, то есть имя двойного указателя для выделяемого блока памяти.

Например:

for (int i=0; i<n; i++)
  delete matr [i]; 
   //освобождает память, выделенную для массива значений 
delete [] matr;
//освобождает память, выделенную под массив указателей

Квадратные скобки [] означают, что освобождается память, занятая всеми элементами массива, а не только первым.

2) при помощи библиотечной функции free, которая предназначена для освобождения динамической памяти.

Синтаксис освобождения памяти, выделенной для массива значений:

free (ИмяМассива[ЗначениеИндекса]);

Синтаксис освобождения памяти, выделенной под массив указателей:

free (ИмяМассива);

ИмяМассива – идентификатор массива, то есть имя двойного указателя для выделяемого блока памяти.

Например:

for (int i=0; i<n; i++)
  free (matr[i]); 
   //освобождает память, выделенную для массива значений 
free (matr);
//освобождает память, выделенную под массив указателей

Обращение к элементам двумерного динамического массива

Адресация элементов динамического массива осуществляется с помощью индексированного имени.

Синтаксис:

ИмяМассива[ВыражениеТипаКонстанты][ВыражениеТипаКонстанты];

или

ИмяМассива[ЗначениеИндекса][ЗначениеИндекса];

Например:

mas[5][7] – индекс задается как константа,

sl[i][j] – индекс задается как переменная,

array[4*p][p+5] – индекс задается как выражение.

Пример 1. Сформируйте и выведите на экран единичную матрицу с целыми элементами, вводя ее порядок с клавиатуры.

#include "stdafx.h"
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[]){
  int n,i,j;
  int **matr;//указатель для массива указателей
  cout << "Input matrix order:";
  cin >> n;
  matr = new int *[n];
  //выделение памяти под массив указателей
  for(i=0; i<n; i++){
    matr[i] = new int[n];
    //выделение памяти для массива значений
    for (j=0; j<n; j++) //заполнение матрицы
      matr[i][j] = (i==j ? 1 : 0);
  }
  cout << "Result: ";
  for(i=0; i<n; i++){
    cout << "\n";
    for (j=0; j<n; j++)
      cout << " " << matr[i][j];
    delete matr[i];
    //освобождение памяти из-под массива значений
  }
  delete [] matr; 
  //освобождение памяти из-под массива указателей
  system("pause");
  return 0;
}

Пример 2. Вычислить сумму элементов, лежащих на диагоналях матрицы N x N (обратить внимание на четность-нечетность числа N ). Размер массива должен задаваться пользователем с клавиатуры.

#include "stdafx.h"
#include <iostream>
using namespace std;
#include <time.h>
void gen (int nn,int a, int b,int ***mas); 
//объявление функции генерации массива
int summa(int nn, int **mas);
/*объявление функции вычисления суммы заданных элементов массива*/
void out (int nn,int **mas);
//объявление функции вывода массива 

int _tmain(int argc, _TCHAR* argv[]){
  int **mass, n;
  int s;
  printf("Введите n: ");
  scanf("%d",n);
  printf("\nГенерация массива \n");
  gen(n,0,10,mass);
  s=summa(n,mass);
  out(n,mass);
  printf("\nСумма элементов = %d",s);
  system("pause");
  return 0;
}

void gen(int nn, int a, int b, int ***mas){ 
  //функция генерации массива 
  int i,j;
  srand(time(NULL)*1000);
  *mas=(int**)malloc(nn*sizeof(int*)); 
  for (i=0;i<nn;i++){
    (*mas)[i]=(int*)malloc(nn*sizeof(int)); 
    for (j=0;j<nn;j++)
      (*mas)[i][j]=rand()%(b-a)+a;
  }
} 

int summa(int nn, int **mas) {
  //функция вычисления суммы элементов диагоналей
  int i,j, sum=0;
  for (i=0;i<nn;i++)
    for (j=0;j<nn;j++) {
      if ((i==j) || (i==nn-j-1)) { 
        //нахождение элементов диагоналей
        sum+=mas[i][j];  
        //суммирование элементов диагоналей
      }
    }
  return sum;
}

void out (int nn,int **mas){ 
  //функция вывода массива
  int i,j;
  for (i=0;i<nn;i++) {
    for (j=0;j<nn;j++) 
      printf("%4d",mas[i][j]);
    printf("\n");  
    free (mas[i]);
    }
  free (mas);
}

В языке С++ предусмотрено использование указателя вида ***mass. В данном примере в функцию генерации массива передается не адрес указателя, а его значение. Передача фактического параметра при вызове функции осуществляется через определение адреса указателя **mass.

Ключевые термины

Двумерный динамический массив – это двумерный массив, расположенный в динамической памяти.

Динамический массив – это массив, размер которого заранее не фиксирован и может меняться во время исполнения программы.

Значение указателя на двумерный динамический массив – это адрес массива указателей на одномерные массивы или адрес выделяемой области динамической памяти, если двумерный массив представляется как одномерный.

Тип двумерного динамического массива – это тип элементов массива.

Указатель на двумерный динамический массив – это указатель на массив указателей на одномерные массивы или на начало выделяемого участка динамической памяти, если двумерный массив представляется как одномерный.

Краткие итоги

Лабораторная работа 26. Двумерные динамические массивы

Цель работы: изучить объявление, выделение и освобождение памяти под двумерные динамические массивы, обращение к элементам, научиться решать задачи с использованием двумерных динамических массивов на языке C++.

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 26.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Указания к выполнению работы.

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

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

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