Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Многомерные массивы, массивы указателей, динамические массивыМногомерный массив в соответствии с синтаксисом языка - массив массивов, т.е. массив, элементами которого служат массивы. Определение многомерного массива в общем случае должно содержать сведение о типе, размерности и количествах элементов каждой размерности: 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. Схема имитации двухмерного динамического массива с помощью массива указателей и набора одномерных массивов
|