Решение задач на динамические массивы

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

Динамическая память, называемая также "кучей", выделяется явно по запросу программы из ресурсов операционной системы и контролируется указателем. Она не инициализируется автоматически и должна быть явно освобождена. В отличие от статической и автоматической памяти динамическая память практически не ограничена (ограничена лишь размером оперативной памяти) и может динамически меняться в процессе работы программы. Выделим основные преимущества и недостатки динамического управления памятью.

Преимущества:

Недостатки:

Типичные ошибки при работе с динамической памятью

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

1) Попытка воспользоваться неинициализированным указателем.

float *pi;
*pi=3.14;//использование неинициализированного указателя

Если pi – глобальная переменная, то она автоматически инициализируется нулевым значением, т.е. имеет значение NULL. Разыменование нулевого указателя приводит к ошибке времени выполнения. Если pi – локальная переменная, то она по умолчанию не инициализируется, а поэтому содержит непредсказуемое значение. Это значение трактуется как адрес вещественной переменной, к которой осуществляется доступ. По чистой случайности может оказаться, что указатель pi содержит истинный адрес переменной программы, тогда значение переменной будет изменено, выполнение программы продолжится дальше, а факт изменения переменной непредсказуемым образом повлияет на дальнейшее выполнение программы.

2) "Висячие" указатели.

После освобождения динамической памяти указатель продолжает указывать на прежний адрес памяти. Такие указатели называются "висячими". Попытка записи по такому указателю не приводит к немедленной ошибке. Однако память, на которую он указывает, могла быть уже выделена другой динамической переменной, и попытка записи приведет к порче этой переменной.

int *p;
p= new int;
*p=55;
delete p; // указатель становится "висячим"
*p=8; // использование "висячего" указателя

Если после delete p; сразу написать p=NULL;, то в дальнейшем при попытке разыменовать нулевой указатель p возникнет исключение, что является более предпочтительным, чем скрытая ошибка изменения другой переменной. Данный прием следует иметь ввиду и после освобождения динамической переменной обнулять указатель:

delete p; 
p=NULL;

3) "Утечка" памяти.

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

Пример. Повторное выделение памяти.

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

int *p;
p= new int;
*p=55;
p= new int; 
//выделяется новый участок памяти под тот же указатель

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

function pp (int n) {  
  int *p;
  p= new int;
  *p=n;
}

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

4) Попытка освободить динамическую память, не выделенную ранее.

int *p;
delete p;

Вызов операции delete для неинициализированного указателя игнорируется, не приводя к генерации ошибки.

5) Попытка освободить нединамическую память.

int *p,i=55;
p=i;
delete p;

При вызове delete для нединамической переменной будет сгенерирована ошибка.

Проверка на выделение памяти

Существует единственное числовое значение, которое можно присвоить непосредственно указателю – это NULL. Нулевой адрес – особый, по этому адресу не может храниться ни одна переменная. То есть указатель, имеющий нулевое значение указывает в "никуда", к такому указателю нельзя применить оператор разыменования.

Библиотечные функции malloc (calloc) или оператор new используют функцию операционной системы для выделения памяти. Если затребованный размер памяти слишком большой (а также при попытке создать массив из нуля или отрицательного числа элементов), операционная система не будет выделять память и тогда функции или оператору вернет нулевое значение ( NULL ). Если это нулевое значение будет присвоено указателю, к которому впоследствии будет применен оператор разыменования или оператор обращения к элементу массива, то программа аварийно завершит работу с ошибкой "segmentation fault" (ошибка сегментации). Для того чтобы избежать таких ошибок необходимо сразу после выделения памяти проверить ее значение, которое возвращает функция или оператор. Проверку можно осуществить с помощью одного из условий: if (pi==NULL) или if (!pi). В случае если это значение равно NULL, выполнить какие-либо действия, например, вывести сообщение о невозможности выделения необходимого объема памяти.

Например:

int n=1000000000;
int *pi=new int[n];
if (pi==NULL) { // if (!pi)
  printf ("Требуемая память не выделена!");
  return;
}

Все рассмотренные функции по работе с динамической памятью могут выделять память размером не более одного сегмента, то есть не более 64K в 16-ти разрядных моделях и не более 4G в 32-х разрядных моделях памяти.

Многомерные динамические массивы

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

#include <stdlib.h> 
void main () { 
  long ***a; 
  int n, m, k, i, j,l; 
  scanf("%d", n); 
  scanf("%d", m); 
  scanf("%d", k); 
  //распределение памяти 
  a=(long ***) calloc(n,sizeof(long **)); 
  for (i=0; i<n; i++) { 
    a[i]=(long **) calloc(m,sizeof(long *)); 
    for (j=0; j<m; j++) {
      a[i][j]=(long *) calloc(k,sizeof(long)); 
      for (l=0; l<k; l++)
        a[i][j][l]=rand();
    }
  } 
. . . . . . . . . . . . 
  //освобождение памяти 
  for (i=0; i<n; i++) { 
    for (j=0; j<m; j++) 
      free (a[i][j]); 
    free (a[i]); 
  } 
  free (a); 
}

Приемы чтения и записи динамических массивов

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

Работа с двумерными динамическими массивами основана на двух следующих способах.

float **a; 
//это указатель на float *, или указатель на массив

A = (тип *) calloc(N*M, sizeof(тип));

A = (тип *) malloc(N*M*sizeof(тип));

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

Пример 1. Вычислить и запомнить средние арифметические значения положительных элементов каждой строки матрицы A(K,L). Имена входного и выходного файла задаются пользователем. Входной файл в первой строке содержит размерность матрицы, со второй строки задается сама матрица.

#include "stdafx.h"
#include <iostream>
using namespace std;
void input (int n,int m, int *mas, FILE *t);
void out (int n,int m,int *mas);
void outmas (int n, float *ml, FILE *g);
void work(int n, int m, int *mas, float *ml);

int _tmain(int argc, _TCHAR* argv[]) {
  int *mass,k,l;
  float *ml;
  float sr;
  char file1[10],file2[10];
  FILE *t,*g;
  printf("Введите имя входного файла: ");
  scanf("%s",file1);
  printf("Введите имя выходного файла: ");
  scanf("%s",file2);
  t=fopen(file1,"r");//открытие файла для чтения
  g=fopen(file2,"w");//открытие файла для записи
  fscanf(t,"%d",k);
  fscanf(t,"%d",l);
  mass=(int*)malloc(k*l*sizeof(int)); 
  //выделение памяти для массива 
  ml=(float*)malloc(k*sizeof(float)); 
  //выделение памяти для массива
  printf("\nМассив:\n");
  input(k,l,mass,t);
  out(k,l,mass);
  work(k,l,mass,ml);
  printf("\nСредние арифметические значения положительных 
          элементов каждой строки матрицы\n");
  outmas(k,ml,g);
  fclose(t);  //закрытие файла
  fclose(g); //закрытие файла 
  free(ml); //освобождение памяти
  free(mass); //освобождение памяти
  system("pause");
  return 0;
}

void input(int n, int m,int *mas, FILE *t){
  int i,j;
  for (i=0;i<n;i++)
    for (j=0;j<m;j++)
      fscanf(t,"%d",mas+i*m+j);
}
void out (int n,int m, int *mas){
  int i,j;
  for (i=0;i<n;i++) {
    for (j=0;j<m;j++)
      printf("%4d",mas[i*m+j]);
      printf("\n");
      }
}
void outmas (int n, float *ml, FILE *g){
  int i;
  for (i=0;i<n;i++) {
     printf("%6.2f\n",ml[i]);
     fprintf(g,"%6.2f\n",ml[i]);
     }
}
void work(int n, int m, int *mas, float *ml) {
  int i,j,kol;
  for (i=0;i<n;i++){
    ml[i]=0;
    kol=0;
    for (j=0;j<m;j++)
      if (mas[i*m+j]>0) {
        ml[i]+=mas[i*m+j];
        kol++;
      }
  if (kol>0) ml[i]/=kol;
  }
}

Поиск, перестановка и сортировка в динамических массивах

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

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

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

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

void Initialization(int **mas, int *k, int *l,int **vmas);
void Print(int *mas, int k, int l);
void Work(int *mas, int k, int l,int *vmas);
void FindMax(int *mas, int k, int l,int *vmas);
void Obmen(int *mas,int k,int l,int i,int q);
void Distraction(int *mas,int *vmas);

int _tmain(int argc, _TCHAR* argv[]) {
  int *mass, n, m, *vmass;
  Initialization(mass, n, m, vmass);
  cout << "Исходная матрица" << "\n";
  Print(mass, n, m);
  Work(mass, n, m, vmass);
  cout << "Преобразованная матрица" << "\n";
  Print(mass, n, m);
  Distraction(mass, vmass);
  system("pause");
  return 0;
}

void Initialization(int **mas, int *k, int *l,int **vmas){
  int i, j, a, b;
  cout << "Введите размерность матрицы:" << "\n";
  cout << "n = ";
  cin >> *k;
  cout << "m = ";
  cin >> *l;
  cout << "Введите границы генерации элементов 
           матрицы:"<<"\n";
  cout << "a = ";
  cin >> a;
  cout << "b = ";
  cin >> b;
  srand(time(NULL)*1000);
  *mas = new int[(*k)*(*l)];
  *vmas = new int[(*l)];
  for (i = 0; i < *k ; i++)
    for (j = 0; j < *l ; j++)
      (*mas)[i*(*l)+j] = rand()%(b-a)+a;
}

void Print(int *mas, int k, int l){
  int i, j;
  for (i = 0; i < k ; i++){
    for (j = 0; j < l ; j++)
      cout << mas[i*l+j] << "   ";
    cout << "\n";
  }
}

void Work(int *mas, int k, int l,int *vmas){
  int i, j, q, r;
  FindMax(mas, k, l, vmas);
  for( i=0; i < l; i++) { // i - номер текущего шага
    q=i;
    for( j=i+1; j < l; j++)
    //цикл выбора наименьшего максимального элемента
      if (vmas[j]<vmas[q]) 
        q=j;//q - индекс наименьшего максимального элемента
    r = vmas[q]; // меняем местами наименьший с vmas[i]
    vmas[q] = vmas[i]; 
    vmas[i] = r;  
    Obmen(mas, k, l, i, q);
    //меняем местами столбцы с номерами i и q матрицы mas 
  }
}

void FindMax(int *mas, int k, int l,int *vmas){
  int i, j;
  for (j = 0; j < l; j++){
    vmas[j] = mas[j];
    for (i = 1; i < k; i++)
      if (vmas[j] < mas[i*l+j]) 
        vmas[j] = mas[i*l+j];
  }  
}

void Obmen(int *mas,int k,int l,int i,int q){
  int j, r;
  for (j = 0; j < k; j++){
    r = mas[j*l+i];
    mas[j*l+i] = mas[j*l+q];
    mas[j*l+q] = r;
  }
}

void Distraction(int *mas,int *vmas){
  delete(vmas);
  delete(mas);
}

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

"Висячий" указатель – указатель на освобожденный блок динамической памяти; признак ошибочного использования динамической памяти.

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

Использование неинициализированного указателя – попытка обращения к неопределенному адресу памяти или к значению NULL; признак ошибочного использования динамической памяти.

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

Ошибки при работе с динамической памятью – приемы некорректной работы с динамической памятью, приводящие к выполнению логически неверных действий в программе.

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

Лабораторная работа 27. Решение задач на динамические массивы

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

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

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

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

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

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

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

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

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

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

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

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