Указатели и матрицы

Сказанное выше для одномерных массивов можно распространить на двумерные массивы. Пусть объявлена статическая матрица: const n=6, k=10; float M[n][k]; Этим самым мы объявили не один, а n константных указателей: M[0] или &M[0][0] — адрес начала 0-й строки, M[1] или &M[1][0] — адрес начала 1-й строки, и т. д., M[n-1] или &M[n-1][0] — адрес начала (n-1)-й строки. Как и для одномерного массива, это константные указатели, и их менять нельзя. Поэтому такая перестановка двух строк с номерами i и j с помощью указателей недопустима:

float *q; q=M[i]; M[i]=M[j]; M[j]=q;

Если первое присваивание правильно, то второе и третье присваивания ошибочны, так как каждый из константных указателей (M[i] и M[j]) менять нельзя, то есть их нельзя, например, использовать слева в операторе присваивания.

Замечание. Позже (глава 2) будет показано, как такие перестановки строк сделать, используя вспомогательный массив указателей.

Преимуществом языка С++ по сравнению с другими языками (например, Pascal), является следующая удобная для практического использования возможность. Функцию обработки одномерного массива можно использовать при работе с частью матрицы. Например, описанную в предыдущем пункте функцию сортировки одномерного массива можно вызвать, передав в качестве фактического параметра адрес какого-нибудь элемента матрицы. Рассмотрим следующие упражнения.

1) for (int i=0; i<n; i++) MySort(M[i], k);

— сортировка всех k элементов каждой строки независимо одна от другой.Это же можно записать и так:

for (int i=0; i<n; i++) MySort(&M[i][0], k);

В качестве фактического параметра передаём адрес начала i -й строки матрицы и количество участвующих в сортировке элементов.

2) for (int i=0; i<n; i+=2) MySort(M[i], 2*k);

— сначала сортируется 0-я и 1-я строки матрицы вместе как один одномерный массив размерности 2*k. Затем аналогично сортируем 2-ю и 3-ю строки и т.д., и, наконец, (n-2)- ю и (n-1)- ю строки. Предполагается, что n — чётное. При этом существенно используется, что элементы статической матрицы в памяти располагаются непрерывно по строкам. После последнего элемента i- й строки следует первый элемент (i+1)- й строки. Заметим, что этот цикл будет правильно работать, если в матрице чётное количество строк.В качестве упражнения внести изменения в этот фрагмент, чтобы он правильно работал и для нечётного n.

3) for (int i=0; i<n; i++) MySort(&M[i][k/2], k/2);

— в каждойстроке матрицы в сортировке участвуют последние k/2 элементов строки. Предполагается, что k — чётное. В качестве упражнения внести изменения в этот фрагмент таким образом, чтобы в случае, если k — нечётное, сортировались последние k/2+1 элементов строки. Например, если k=15, должны сортироваться последние 8 элементов.

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

Пусть описана функция:

int MyFun (int *x, int n)

{ По некоторому алгоритму для одномерного массива x размерности n получаем и возвращаем некоторый параметр (например, сумму чисел с некоторым условием) в виде одного целого числа. }

Как эту функцию использовать для получения и (или) вывода этого же параметра для всей матрицы (одного целого числа), объявленной так:

const n=4,m=6; int A[n][m];?

Выберите правильные варианты ответов:

1) int Res; Res=MyFun (&A[0][0], n); cout<<Res;

2) int Res; Res=MyFun (A[0], m); cout<<Res;

3) int Res; Res=MyFun (A[0], m*n); cout<<Res;

4) cout<< MyFun (&A[0][0], n*m);

Решение. В первом варианте будет обработано 4 первых (из шести) числа первой с 0-м номером строки матрицы. Так как &A[0][0] и A[0] для матрицы — это адрес её начала, то есть адрес элемента A[0][0], то во втором варианте будут проанализированы m=6 элементов той же первой с 0-м номером строки матрицы. Поэтому правильными будут третий и четвёртый варианты, в которых найденный в функции параметр будет получен для m*n элементов матрицы, начиная с A[0][0], то есть с самого начала матрицы. Заметим, что так как второй параметр функции — это целое число, то m*n и n*m — это одно и тоже значение, то есть общее количество элементов матрицы.

Так как элементы столбца располагаются в памяти не рядом друг с другом, как строки, а на опредлённом расстоянии, то для обработки столбца матрицы этот метод неприменим. Для этого можно, как это делается в языке Pascal и при обработке строк, скопировать столбец в дополнительный одномерный массив и передать его в функцию в качестве фактического параметра. Если функция не просто получает параметр (MyFun), а преобразовывает одномерный массив, например, сортирует его (MySort), то преобразованный с помощью функции одномерный массив обратно копируем на место столбца матрицы. Напомним, что обработка матрицы по столбцам неэффективна.

§2. Динамические одномерные массивы (+)

Массивы с фиксированной размерностью, заданной в виде константы, названные в первом семестре статические, обладают рядом недостатков. Во-первых, в качестве размерности можно использовать только константу. А как быть, если количество элементов массива необходимо, например, ввести или вычислить? Ещё один недостаток таких массивов в том, что память для них выделяется на этапе компиляции и остаётся занятой за функцией (или блоком) на всё время их выполнения до выхода из них.

Эти и некоторые другие недостатки статических массивов исправляют так называемые динамические массивы.

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

1) В качестве его размерности можно, как и для статического массива, по-прежнему объявить и использовать константу: const nс=10. Но эффективнее для этого использовать переменную, например, unsigned n. Необходимо её определить одним из известных способов: ввести, вычислить по некоторому алгоритму, задать случайным образом и т.п.

2) Объявляем указатель на такой массив:

тип_элементов_массива *указатель;

например,

float *ard;

3) Из приведенного выше объявления массива ещё не видно, будем ли мы создавать массив ard или в переменной ard будет адрес одной ячейки для вещественного числа. Это зависит от формата использования операции new. При создании массива она имеет следующий синтаксис:

идентификатор_массива =new тип_элементов_массива[размерность];

Для нашего примера

ard=new float[n];

Что делает эта операция? Во-первых, в динамической памяти выделяется непрерывный участок для размещения массива указанной в квадратных (а не в круглых) скобках размерности, элементы которого будут иметь указанный тип. Кроме этого, операция возвращает адрес начала массива, то есть адрес его первого элемента. После выполнения операции прсваивания этот адрес будет значением переменной ard.

Третий пункт можно объединить со вторым: float *ard= new float[n]; Но в отличие от статического инициализацию динамического массива одновременно с объявлением выполнять нельзя. Поэтому следующая запись

float *ard= new float[n]={1.1,2.2, -30.3,-44};

приведёт к ошибке.

4) Ячейки для элементов динамического одномерного массива располагаются в оперативной памяти подряд. Поэтому работа с ним выполняется, как и для статического одномерного массива, двумя способами. Доступ к элементам динамического массива можно осуществлять с помощью явного указания индексов, как это было в первом семестре. Например, для ввода массива, как и раньше, можно записать: for (int i=0; i<n; i++) cin>>ard[i]; Кроме этого, динамические одномерные массивы, как и статические, можно обрабатывать, используя операции над указателями (см. гл. 2).

5) В отличие от статического массива адрес динамического можно менять. Но это нужно делать с осторожностью, чтобы не “потерять” адрес его начала. Этот адрес понадобится для освобождения занятой массивом памяти и, возможно, для других целей. Это выполняется с помощью операции delete, синтаксис которой для динамического массива следующий:

delete [] переменная_указатель;

Например,

delete [] ard;

освобождает всю память, выделенную для массива ard. Освободить память для части массива, указав в квадратных скобках выражение, невозможно. В квадратных скобках ничего не записывается.

Если delete “забыли” написать, то ошибки не будет. Но при работе с динамической памятью, особенно с массивами, память, выделенную с помощью new, рекомендуется всегда освобождать, используя delete. Дело в том, что при выходе из блока полученный с помощью new указатель уничтожается, но память автоматически не освобождается, т.е. остаётся распределённой, занятой. Поэтому к ней обратиться невозможно. Поэтому на этапе, когда эта память не нужна, или при выходе из блока или функции она должна быть явно освобождена.

Из приведенных пяти этапов самым сложным и трудоёмким, но в тоже время наиболее творческим по-прежнему, как и для статических массивов, остаётся четвёртый, так как он связан с разработкой алгоритма решения задачи. Остальные этапы в меньшей степени зависят от конкретной задачи и являются почти стандартными. С другой стороны, если отлажена программа для статического одномерного массива, то запрограммированный алгоритм можно использовать для динамического одномерного массива, внеся небольшие дополнения (см. этапы 1, 2, 3, 5).

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

П р и м е р. (+)

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

const Nmax=20;

/* Наибольшая размерность массива, которая используется в конструкторе для контроля передаваемой в класс размерности. */

class DinArr

{

/* Реальная размерность массива в виде переменной, а не константы. */

unsigned n;

/*Объявляем указатель на динамический массив. */

float *DA;

/* Метод для перестановки двух чисел. Можно использовать только внутри класса, так как по умолчанию атрибут доступа private. В качестве формальных параметров используем указатели на вещественные числа. Подробности см. далее в 3.1 главы 2. */

void Change(float *x, float* y)

{ float t; t=*x; *x=*y; *y=t;};

public:

DinArr(int size)

{

/* Во время выполнения (а не компиляции) программы при объявлении объекта (при его создании) вызывается этот конструктор. С его помощью определяем размерность массива n с элементарным контролем. С помощью операции new резервируем память для n элементов массива и адрес начала этой выделенной области памяти присваиваем переменной указателю DA. */

if (size<1 || size>Nmax) n=Nmax / 2; else n=size;

DA=new float [n];

}

// Метод для ввода массива

void MyDef()

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

cin>>DA[i];

}

// Вывод массива

void Show()

{ cout<<endl;

for(int i=0; i<n; i++) printf("%5.2f ",DA[i]);

cout<<endl;

}

/* Булевская функция, возвращающая true или false в зависимости от того, является ли массив “симметричным” относительно “центра” */

bool Simm()

{for (int i=0;i<n/2; i++)

if (DA[i]-DA[n-1-i]) return false;

return true;

}

/* Метод, который “переворачивает” массив, т.е. меняет местами первый элемент с последним, второй с предпоследним и т. д. */

void Rev()

{for (int i=0;i<n/2; i++)

Change(&DA[i], &DA[n-1-i]);

}

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

~DinArr()

{

/* Выводим текст, чтобы убедиться, что конструктор выполнялся. */

cout<<"\nThe destructor deletes array\n";

getch();

/* Освобождаем память, выделенную для динамического массива. */

delete []DA;

}

};

int main(int argc, char* argv[])

{ // randomize;

// DinArr ObjArr(random(Nmax)); или