Многомерные массивы, массивы указателей, динамические массивы

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

type имя_массива[K1][K2]… [ KN];

type – допустимый тип (основной или производный); имя_массива – идентификатор; N – размерность массива, К – количество в массиве элементов размерности К -1 каждый. Например: long Array[4][3][6];

Трехмерный массив Array состоит из четырех элементов, каждый из которых – двухмерный массив с размерами 3х6. Язык Си++ гарантирует, что в памяти компьютера элементы массива будут размещаться последовательно друг за другом в порядке возрастания самого правого индекса, т. е. самый младший адрес имеет элемент Array[0][0][0], затем идёт Array[0][0][1], Array[0][0][2], …, Array[0][0][5] далее

Array[0][1][0], Array[0][1][1], …, Array[0][1][5], далее Array[0][2][0], …, Array[0][2][5] заканчивается первый и далее начинается второй элемент двухмерного массива с размерами 3х6 Array[1][0][0], Array[1][0][1] и т. д.

С учётом порядка расположения в памяти элементов многомерного массива нужно размещать начальные значения его элементов в списке инициализации.

Так long Array[4][3][6] = {0,1,2,3,4,5,6,7,8,9}; такая запись означает, что начальные значения получат первые десять элементов массива Array, т.е.

Array[0][0][0] = = 0, Array[0][0][1] = =1, Array[0][0][2]= = 2, Array[0][0][3] = =3, Array[0][0][4] = = 4, Array[0][0][5] = = 5, Array[0][1][0] = = 6, Array[0][1][1] = = 7, Array[0][1][2] = = 8, Array[0][1][3] = = 9. Остальные элементы массива Array остались не инициализированными.

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

long A[4][5][6] = { {{0}},

{ {100}, {110, 111} },

{ {200}, {210}, {220, 221, 222}} };

так задаётся только некоторое значения его элементов:

А[0][0][0] = = 0

А[1][0][0]== 100, А[1][1][0] == 110, А[1][1][1] == 111

А[2][0][0] = = 200, А[2][1][0] = = 210,

А[2][2][0]== 220, А[2][2][1] == 221, А[2][2][2] == 222

Остальные элементы массива явно не инициализируются.

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

float matrix [][5] = { {1}, (2}, {3} };

формирует массив matrix с размерами 3х5, но не определяет явно начальных значений всех его элементов. Оператор

cout «"\n sizeof(matrix) = "«sizeof(matrix); /*выведет на экран: sizeof(matrix)=60*/

Начальные значения получают только

matrix[0][0] = 1

matrix[1][0] = 2

matrix[2][0] = 3

Как и в случае одномерных массивов, доступ к элементам многомерных массивов возможен с помощью индексированных переменных и с помощью указателей. Возможно объединение обоих способов в одном выражении. Чтобы не допускать ошибок при обращении к элементам многомерных массивов с помощью указателей, нужно помнить, что при добавлении целой величины к указателю его внутреннее значение изменяется на "длину" элемента соответствующего типа. Имя массива всегда константа-указатель. Для массива, определенного как type ar [N] [M] [L], ar - указатель, поставленный в соответствие элементам типа type [M] [L]. Добавление 1 к указателю ar приводит к изменению значения адреса на величину sizeof(type) * M * L.

Именно поэтому выражение * (ar + 1) есть адрес элемента ar[l], т.е. указатель на массив меньшей размерности, отстоящий от начала массива (&ar[0]), на размер одного элемента type[M] [L]. Сказанное иллюстрирует следующая программа:

//Программа 5.5

#include "stdafx.h"

#include <iostream>

void main(){

int b[3][2][4] = {0, 1, 2, 3,

10, 11, 12, 13,

100, 101, 102, 103,

110, 111, 112, 113,

200, 201, 202, 203,

210, 211, 212, 213,

};

// Адрес массива b[][][]

std::cout << "\nb = " << b;

// Адрес массива b[0][][]

std::cout << "\n*b = " << *b;

// Адрес массива b[0][0][]

std::cout << "\n**b = " << **b;

// Элемент b[0][0][0]

std::cout << "\n***b ="<< ***b;

// Адрес массива b[1][][]

std::cout << "\n*(b + 1) = " << *(b + 1);

// Адрес массива b[2][][]

std::cout << "\n*(b +2) = " << *(b + 2);

// Адрес массива b[0][1][]:

std::cout << "\n*(*b + 1) = " << *(*b + 1);

std::cout << "\n*(*(*(b + 1) + 1) + 1) = " <<*(*(*(b + 1) + 1) + 1);

std::cout << "\n*(b[l][l]+ 1) = " << *(b[1][1] + 1);

//Элемент b[2][0] [0];

std::cout<< "\n*(b[l] + 1)[1] = " << *(b[1] + 1)[1];

getchar();

}

Результаты выполнения программы:

b = 0x8d880fd0

*b = 0x8d880fd0

**b = 0x8d880fd0

***b = 0

*(b + 1) = 0x8d880fe0

*(b + 2) = 0x8d880ff0

*(*b + 1) = 0x8d880fd8

*(*(*(b + 1) + 1) + 1) = 111

*(b[1][1] + 1) = 111

*(b[1] + 1) [1] = 200

В программе доступ к элементам многомерного массива осуществляется с помощью операций с указателями. В общем случае для трехмерного массива индексированный элемент b[i] [j] [k] соответствует выражению *(*(* (b + i) + j) + k). В нашем примере:

*(*<*(b + 1) + 1) + 1) == b[1][1][1] ==111

Допустимо в одном выражении комбинировать обе формы доступа к элементам многомерного массива:

*(b[1][1] + 1) == 111

Как бы ни был указан путь доступа к элементу многомерного массива, внутренняя адресная арифметика, используемая компилятором, всегда предусматривает действия с конкретными числовыми значениями адресов. Компилятор всегда реализует доступ к элементам массива с помощью указателей и операции разыменования. Если в программе использована, например, такая индексированная переменная: ar[i][j][k], принадлежащая массиву type ar[N][M][L], где N, M, L - целые положительные константы, то последовательность действий компилятора такова:

· выбирается адрес начала массива, т.е. целочисленное значение указателя ar, равное (unsigned long)ar;

· добавляется смещение i * (М * L) * sizeof(type) для вычисления начального адреса i-го массива с размерами M на L, входящего в исходный трехмерный массив;

· добавляется смещение для вычисления начального адреса j-й строки (одномерный массив), включающей L элементов. Теперь смещение равно (i * (М * L) + j * L) * sizeof (type);

· добавляется смещение для получения адреса k-го элемента в строке, т.е. получается адрес (unsigned long) (i * (M * L) + j * L + k) * sizeof(type);

· применяется разыменование, т.е. обеспечивается доступ к содержимому элемента по его адресу: * ((unsigned long) (i * (м * l) + j * l + k)).

Массивы указателей. Синтаксис языка Си++ в отношении указателей непротиворечив, но весьма далек от ясности. Для понимания, что же определено с помощью набора звездочек, скобок и имен типов, приходится аккуратно применять синтаксические правила, учитывающие последовательность выполнения операций. Например, следующее определение

int array[6];/*вводит массив указателей на объекты типа int. Имя массива array, он состоит из шести элементов, тип каждого int. Определение*/

int (*ptr)[6]; /*вводит указатель ptr на массив из шести элементов, каждый из которых имеет тип int. Таким образом, выражение (array + 1) соответствует перемещению в памяти на sizeof (int) байтов от начала массива (т.е. на длину указателя типа int). Если прибавить 1 к ptr, то адрес изменится на величину sizeof (int[6]), т.е. на 12 байт при двухбайтовом представлении данных типа int.*/

Эта возможность создавать массивы* указателей порождает интересные следствия, которые удобно рассмотреть в контексте многомерных массивов.

По определению массива, его элементы должны быть однотипными и одного "размера". Предположим, что мы хотим определить массив для представления списка фамилий (учеников класса, сотрудников фирмы и т.п.). Если определять его как двухмерный массив элементов типа char, то в определении для элементов массива необходимо задать предельные размеры каждого из двух индексов. Таким образом, "прямолинейное" определение массива для хранения списка фамилий может быть таким:

char spisok[25][20];

Для примера здесь предполагается, что количество фамилий в списке не более 25 и что длина каждой фамилии не превышает 19 сим­волов (букв). После такого определения или с помощью инициализа­ции в самом определении в элементы spisok[0], spisok[l],... можно занести конкретные фамилии, представленные в виде строк. Размеры так определенного массива всегда фиксированы.

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

char spisok[][20] = { "Иванов", "Петров", "Сидоров" };

Теперь в массиве spisok только 3 элемента, каждый из них длиной 20 элементов типа char (рис. 5.2).

Рис. 5.2. Двухмерный массив char spisok [ 3 ] [20 ] и одномерный массив указателей char *pointer[3], инициализированные одинаковыми строками

 

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

В противоположность этому при определении и инициализации теми же символьными строками одномерного массива указателей типа char* память распределяется гораздо рациональнее:

char *pointer [] = { "Иванов", "Петров", "Сидоров" };

Для указателей массива pointer, в котором при таком определении 3 элемента и каждый является указателем-переменной типа char *, выделяется всего 3*sizeof (char *) байтов. Кроме того, компилятор размещает в памяти три строковые константы "Иванов" (7 байт), "Петров" (7 байт), "Сидоров" (8 байт), а их адреса становятся значениями элементов pointer[0], pointer[1], pointer[2]. Сказанное иллюстрирует рис. 5.2.

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

//Программа 5.6

#include "stdafx.h"

#include <iostream>

void main (){

char *pointer []={"Ivanov", "Petrov", "Cidorov", "Antonov"};

int i, j;

char* temp;

int iNumberOfElement = 4;

for(i = 0; i < iNumberOfElement; i++) std::cout<<"\n\n"<< pointer [i];/*Печать исходного массива*/

//Сортировка по алвавиту

for(i = 0; i < iNumberOfElement -1; i++)

for(j = iNumberOfElement-1; j>i;j--){

if(strcmp(pointer [j], pointer [j-1]) <0){

temp = pointer [j]; // Меняем местами указатели

pointer [j] = pointer [j-1];

pointer [j-1] = temp;

}

}

std::cout<<"\n\n\n";/*Печать отсортированного массива */

for(i = 0; i < iNumberOfElement; i++) std::cout<<"\n "<< pointer [i];

getchar();

}

 

Накладными расходами при этой "косвенной" сортировке списков объектов является требование к памяти, необходимой для массива указателей. Выигрыш - существенное ускорение сортировки.

 

Массивы динамической памяти. В соответствии с синтаксисом операция new при использовании с массивами имеет следующий формат:

new тип_массива

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

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

long (*1р)[2][4]; // Определили указатель

1р = new long[3][2][4]; // Выделили память для массива

В данном примере использован указатель на объекты в виде двухмерных массивов, каждый из которых имеет фиксированные размеры 2х4 и содержит элементы типа long. В определении указателя следует обратить внимание на круглые скобки, без которых обойтись нельзя. После выполнения приведенных операторов указатель 1р становится средством доступа к участку динамической памяти с размерами 3 ´ 2 ´ 4 ´ sizeof (long) байтов. В отличие от имени массива (имени у этого массива из примера нет) указатель 1р есть переменная, что позволяет изменять его значение и тем самым, например, перемещаться по элементам массива.

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

delete [] 1р;

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

Выделение и освобождение памяти для массива

//Программа 5.7

#include "stdafx.h"

#include <iostream>

void main(){

long (*lp) [2][4];

lp = new long [3][2][4];

std::cout<< "\n";

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

std::cout << "\n";

for (int j = 0; j < 2; j++)

for (int k = 0; k < 4; k++) {

lp[i][j][k] = i + j + k;

std::cout<<'\t'<< lp[i][j][k];

}

}

getchar();

delete [] lp;

}

Результаты выполнения программы:

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

new long[] // Ошибка, размер неизвестен

new long[][2][4] // Ошибка, размер неизвестен

new long[3][][4] // Ошибка, размер неизвестен

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

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

Единичная диагональная матрица с изменяемым порядком

//Программа 5.8

#include "stdafx.h"

#include <iostream> // Для ввода-вывода

void main(){

int n; // Порядок матрицы

std::cout<< "\nInput order of matrix: ";

std::cin>> n; // Определяются размеры массива

float **matr; // Указатель для массива указателей

matr = new float *[n]; // Массив указателей float *

if (matr == NULL){

std::cout<< "He создан динамический массив!";

return; // Завершение программы

}

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

// Строка-массив значений типа float:

matr[i] = new float[n];

if (matr[i] == NULL){

std::cout<< "He создан динамический массив!";

return; // Завершение программы

}

for (int j = 0; j < n; j++) // Заполнение матрицы

// Формирование нулевых элементов

if (i!= j) matr[i][j] = 0; else

// Формирование единичной диагонали:

matr[i][j] = 1;

}

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

std::cout<< "\n row" << (i + 1) << ":";// Цикл печати элементов строки:

for (int j = 0; j < n; j++)std::cout<< "\t" << matr[i][j];

}

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

delete matr[i]; delete[]matr;

getchar();

}

Результаты выполнения:

Введите размер матрицы: 5 <Enter>

Строка 1: 10000

Строка 2: 01000

Строка 3: 00100

Строка 4: 00010

Строка 5: 00001

На рис. 5.3 изображена схема взаимосвязи (n - 1) - одномерных массивов, из n элементов каждый. Эти (n - 1) массивов совместно имитируют квадратную матрицу с изменяемыми размерами, формируемую в программе.

Рис. 5.3. Схема имитации двухмерного динамического массива с помощью массива указателей и набора одномерных массивов

 

ПРОЕКТНЫЕ ЗАДАНИЯ К МОДУЛЮ

1. Напишите программу, вычисляющую такое значение n, при котором значение предела вычислялось бы с точностью до 3-го знака после запятой.

2. Напишите программу, сортирующую в алфавитном порядке десять произвольных букв, введенных с клавиатуры.

3. Напишите программу, сортирующую по возрастанию пять действительных чисел, введенных с клавиатуры.

4. Напишите программу, вычисляющую факториал числа.

5. Напишите программу, вычисляющую корни квадратного уравнения a0x2+a1x+a2=0 (коэффициенты a0, a1, a2 задаются пользователем с клавиатуры).

6. Напишите функцию, конвертирующую содержимое строки, состоящей из прописных букв в строчные и наоборот.

7. Напишите функцию, которая подсчитывает количество гласных и согласных в строке.

8. Напишите функцию, которая подсчитывает количество букв и цифр в строке.

9. Напишите функцию, которая подсчитывает число прописных и строчных букв в строке.

10. Напишите функцию, которая сравнивает две строки, и если они совпадают, то возвращает единицу (истину), в противном случае ноль (ложь).

11. Напишите функцию, которая сортирует строку по алфавиту.

12. Напишите функцию, которая шифрует текстовый файл путем замены значения символа с помощью выражения symbol = F(symbol), где F() - функция (например, значение символа С заменяется на С=С^0xFF).

 

ТЕСТЫ РУБЕЖНОГО КОНТРОЛЯ

1. Блок это

a) Оператор, заканчивающийся точкой с запятой

b) Несколько операторов, заключенных в фигурные скобки

c) Несколько операторов, заключённых в фигурные скобки, среди которых имеются определения или описания

2. Какие из перечисленных операторов не являются операторами выбора (условия)

a) If(выражение) {} else{}

b) Switch(выражение) {}

c) Выражение1? выражение2: выражение 3;

3. Какой из перечисленных ниже операторов цикла, является оператором с постусловием

a) Do{} while(выражение);

b) While(выражение){}

c) For(выражение1; выражение2; выражение3) {}

4. Какой из операторов передачи управления используется для выхода из функции

a) Goto

b) Break

c) Return

d) Continue

5. Какое утверждение ложно

a) С помощью оператора goto нельзя входить во внутрь тела цикла

b) С помощью оператора goto нельзя входить внутрь условного оператора

c) С помощью оператора goto нельзя входить внутрь блока, обходя инициализацию.

6. Какое утверждение истино

a) Оператор break передаёт управление за пределы всех вложенных циклов

b) Оператор break передаёт управление за пределы цикла

c) Оператор break передаёт управление за пределы тела функции

7. Какое утверждение истино

a) Оператор continue заставляет сделать цикл следующую итерацию

b) Оператор continue заставляет начать выполнение цикла заново

c) Оператор continue позволяет продолжить выполнение текущей итерации

8. Какое утверждение ложно

a) Над указателями определена операция умножение

b) Над указателями определена операция сложения

c) Над указателями определена операция декремента

9. Для какого указателя определена операция преобразования типа по умолчанию

a) Int*

b) Double*

c) Void*

10. Результатом выполнения операции & над объектом является

a) Получение адреса объекта

b) Получение значения хранящегося в объекте

c) Переход по адресу, хранящемуся в объекте

11. При прибавлении к указателю (typy*) единицы его значение изменяется на

a) 1

b) 2

c) sizeof(type)

12. К какому указателю нельзя применять операцию доступа по адресу (*)

a) Long double*

b) Obj*

c) Void*

13. Какое значение вернёт операция sizeof(char*)

a) 1

b) 2

c) 4

14. Какое значение вернёт операция sizeof(s), если s определено как long s[4]

a) 4

b) 8

c) 16

15. Как в языке Си++ интерпретируется операция имя_массива_типа_typy [i]

a) *(имя_массива + индекс)

b) *(имя_массива + индекс*sizeof(type))

c) *(имя_массива *sizeof(type)+ индекс)

16. Как размещаются в памяти элементы многомерного массива

a) Последовательно друг за другом в порядке возрастания самого правого индекса

b) Последовательно друг за другом в порядке возрастания самого левого индекса

17. С помощью какой операции создаются динамические объекты

a) С помощью операции new

b) C помощью определения локального объекта

c) C помощью определения глобального объекта

18. Время существования динамического объекта

a) С момента определения до конца блока

b) Во всей программе

c) До вызова оператора delete c указателем на объект

 

Таблица правильных ответов

№ Вопроса	Правильный ответ	№ Вопроса	Правильный ответ
	с		a
	с		c
	a		c
	c		c
	c		c
	b		b
	a		a
	a		a
	c		c

 

Квалиметрическая оценка

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

от 85 до 100% - это отлично;

от 70 до 84% - это хорошо;

от 55 до 69% - это удовлетворительно;

менее 55% - это не удовлетворительно.

 

Список Литературы

1. В.В. Подбельский Язык Си++: Учебное пособие. - 5-е изд. - М.: Финансы и статистика, 2000. - 560с. ил.

2. Ален И. Голуб. Си и Си++ правила программирования. - М.: БИНОМ, 1996. - 272с.

3. Бьерн Страуструп Язык программирования Си++. 3-е изд. /Пер. с англ. - СПб.; М.: «Невский диалект» - «Издательство БИНОМ», 1999. - 991с. ил.

 

Модуль 3

Целью данного модуля является изложение и закрепление студентами материала касающегося применения функций в языке Си++

 

 

ФУНКЦИИ, УКАЗАТЕЛИ, ССЫЛКИ

Ранее в лекциях уже приводился материал по функциям, поэтому многие понятия в новой главе уже знакомы учащимся.