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

2.1. Сведение

Как было сказано выше, размер массива является составной частью типа массива, но в определенных ситуациях он теряется и это делает тип массива в некотором смысле «неполноценным». Эта потеря называется сведение (decay, array-to-pointer decay). (Decay еще иногда переводится как разложение.) Суть сведения заключается в том, что почти в любом контексте массив преобразуется к указателю на первый элемент и информация о размере теряется. Исключениями являются оператор , оператор (взятия адреса) и инициализация ссылки на массив. Оператор рассматривался в разделе 1.2, указатели и ссылки на массивы будут подробно рассмотрены в разделе 4. Объявление с помощью ключевого слова также правильно определяет тип массива, без сведения.


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

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

Вот как сведение влияет на объявления функций. Функции

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

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

Для размера также надо использовать дополнительную переменную или использовать специальное соглашение для определения размера.

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

При конкретизации шаблона функции

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

Сведение вызывает дополнительные проблемы при использовании наследования. (В C ведь нет наследования.) Рассмотрим пример.

Следующий код компилируется без ошибок и предупреждений.

Но если , то в теле смещение элементов массива (кроме нулевого, конечно) будет определятся неправильно и, соответственно, почти всегда будет работать некорректно. Так что работать с массивами в полиморфном стиле, через указатель на базовый класс, нельзя.

Примеры

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

#include <conio.h>
#include <stdio.h>

#define ROWS 4
#define COLS 3

void main() {
	int a = 
		{{1, 4, 5}, 
		 {2, 6, 8}, 
		 {1, 0, 9}, 
		 {4, 2, 8}};
	int i, j, tmp, flag;

	do {
		flag = 0;
		for (i = 1; i < ROWS*COLS; i++) {
			if (a < a) {
				tmp = a;
				a = a;
				a = tmp;
				flag = 1;
			}
		}
	} while(flag);

	for (i = 0; i < ROWS; i++) {
		for (j = 0; j < COLS; j++) {
			printf("%3d", a);
		}
		printf("\n");
	}

	_getch();
}

Замечание: по стандарту явно такое поведение не определено, но косвенно должно поддерживаться.

2. Даны координаты x и y точки, полученные в ходе фотосъёмки. Известно, сколько кадров в секунду делала камера. Вычислить скорость в каждый момент времени и среднюю скорость за всё время.

#include <conio.h>
#include <stdio.h>
#include <math.h>

#define SIZE 10

void main() {
	float a = 
		{{1.03, 1.52, 2.11, 2.53, 3.08, 3.48,  3.98,  4.51,  5.02,  5.17}, 
	     {1.03, 2.45, 4.13, 5.64, 7.22, 8.73, 10.32, 11.75, 13.28, 14.87}};
	float velocity;
	float speed = 0.0;
	float vx, vy;
	float dt = 0.1;
	int i;

	for (i = 0; i < SIZE-1; i++) {
		vx = ( a - a ) / dt;
		vy = ( a - a ) / dt;
		velocity = sqrt(vx*vx + vy*vy);
		speed += velocity;
	}

	speed /= (float)(SIZE - 1);
	for (i = 1; i < SIZE; i++) {
		printf("v = %.3f m/s\n", i, velocity);
	}
	printf("mean velocity = %.3f", speed);
	_getch();
}

3. Массив используется как карта, где число 2 означает начало, а 3 — конец пути. Программа сначала находит координаты этих точек, после этого вычисляет расстояние Манхеттена (сколько нужно пройти по x и y от начала до конца) и расстояние по Евклиду (как гипотенузу прямоугольного треугольника).

#include <conio.h>
#include <stdio.h>
#include <math.h>

#define SIZE 5
#define START  2
#define FINISH 3

void main() {
	char field = {
		{0, 0, 0, 0, 0},
		{2, 0, 0, 0, 0},
		{0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0},
		{0, 0, 0, 0, 3}
	};
	unsigned i, j;
	unsigned x, y;
	char xFound = 0;
	int X, Y;
	char XFound = 0;
	unsigned manhattanDist;
	float euclidDist;

	for (i = 0; i < SIZE; i++) {
		for (j = 0; j < SIZE; j++) {
			if (field == START) {
				x = i;
				y = j;
				xFound = 1;
				if (XFound) {
					break;
				}
			}
			if (field == FINISH) {
				X = i;
				Y = j;
				XFound = 1;
				if (xFound) {
					break;
				}
			}
		}
		if (xFound && XFound) {
			break;
		}
	}
	if (!(xFound && XFound)) {
		printf("Error: corrupted data\n");
		getch();
		exit(1);
	}

	printf("(x,y) = %d, %d\n(X,Y)= %d, %d\n", x, y, X, Y);

	manhattanDist = abs((int)(x-X)) + abs((int)(y-Y));
	//тоже самое, что и sqrt((x-X)*(x-X)+(y-Y)*(y-Y))
	x -= X;
	y -= Y;
	euclidDist = sqrt((float)(x*x + y*y));
	printf("Manhattan dist. = %d\nEuclid dist. = %.3f", manhattanDist, euclidDist);
	getch();
}

4. Пользователь вводит 10 слов. Вывести слово с максимальной длиной. Программа внешне совершенно простая, единственная проблема — считывание и вывод слова. Так как слова храняться в двумерном массиве, то указатель на words — это начало нового слова. Также не забываем об ограничении на длину при вводе.

#include <conio.h>
#include <stdio.h>

#define SIZE 10
#define MAX_LENGTH 128

void main() {
	//Массив хранит 10 слов максимум по 128 символов
	char words;
	unsigned i, j, maxLength;
	//Так как длина слова ограничена 127 символами, то типа char хватит
	unsigned char counter;

	for (i = 0; i < SIZE; i++) {
		//Считываем слова. words - это символ, нам нужен
		//адрес, начиная с которого можно писать в массив
		fgets(&words, MAX_LENGTH - 1, stdin);
		j = 0;
		//Считаем длину слова
		while (words) {
			j++;
		}
		counter = j;
	}

	//Ищем слово с максимальной длиной
	maxLength = counter;
	j = 0;
	for (i = 1; i < SIZE; i++) {
		if (counter > maxLength) {
			maxLength = counter;
			j = i;
		}
	}

	//Выводим слово на печать. При выводе строки
	//необходимо передавать указатель
	printf("%s", &words);
	_getch();
}

Q&A

Всё ещё не понятно? – пиши вопросы на ящик

Динамические массивы

Динамические массивы в VBA Excel, в отличие от статических, объявляются без указания размерности:

1 2

PublicMassiv1()AsInteger

DimMassiv2()AsString

Такие массивы используются, когда заранее неизвестна размерность, которая определяется в процессе выполнения программы. Когда нужная размерность массива становится известна, она в VBA Excel переопределяется с помощью оператора ReDim:

1 2 3 4


PublicMassiv1()AsInteger

DimMassiv2()AsString

ReDimMassiv1(1To20)

ReDimMassiv2(3,5,4)

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

С помощью оператора ReDim невозможно изменить обычный массив, объявленный с заранее заданной размерностью. Попытка переопределить размерность такого массива вызовет ошибку компиляции с сообщением: Array already dimensioned (Массив уже измерен).

При переопределении размерности динамических массивов в VBA Excel теряются значения их элементов. Чтобы сохранить значения, используйте оператор Preserve:

1 2 3 4 5

DimMassiv1()AsString

——операторы——

ReDimMassiv1(5,2,3)

——операторы——

ReDimPreserveMassiv1(5,2,7)

Обратите внимание!Переопределить с оператором Preserve можно только последнюю размерность динамического массива. Это недоработка разработчиков, которая сохранилась и в VBA Excel 2016

Без оператора Preserve можно переопределить все размерности.

Многомерный массив

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

Общий синтаксис для объявления многомерного массива такой:

Пример с массивом трех измерений:

Если думать о трехмерном массиве как об одномерном, содержащем несколько двумерных, то его можно изобразить как список таблиц. Даже для массива threeArr такой вид будет довольно громоздким – 3 таблицы по 4 строки и 5 столбцов. Для примера представим только вторую таблицу (когда первый индекс равен 1, то есть threeArr):

21

22

23

24

25

26


27

28

29

30

31

32

33

34

35

36

37

38

39

40

Ячейка с координатами выделена подчеркиванием, ее значение присвоено переменной t124.

Как объявить двумерный массив в Java?

Вместо одной скобки вы будете использовать две, например, int [] [] — двумерный целочисленный массив. Определяется это следующим образом:

int[][] multiples = new int; // 2D integer array 4 строки и 2 столбца 
String[][] cities = new String; // 2D String array 3 строки и 3 столбца

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

int[][] wrong = new int[][]; // not OK, you must specify 1st dimension 
int[][] right = new int[];

Выражение выдаст ошибку «переменная должна предоставить либо выражения измерения, либо инициализатор массива» во время компиляции. С другой стороны, при заполнении, второе измерение является необязательным и даже если вы не укажете, компилятор не будет ругаться, как показано ниже:

String[][] myArray = new String[]; // OK 
String[][] yourArray = new String; // OK

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

class 
TwoDimensionalArray { public static void main(String[] args) {
String[][] salutation = {
{"Mr. ", "Mrs. ", "Ms. "},
{"Kumar"}
};
 // Mr. Kumar
System.out.println(salutation + salutation);
// Mrs. Kumar
System.out.println(salutation + salutation);
    }
}
The output from this program is: 
Mr. Kumar 
Mrs. Kumar

В этом примере вы можете видеть объявление двумерного массива, но его первая строка имеет 3 элемента, а вторая строка имеет только один элемент.

Вы можете получить доступ к элементам, используя оба индекса или только один индекс. Например, salutation представляет единственную строку в Java, в то время как salutation представляет одномерный.

Пока мы только что объявили и создали массив, но не инициализировали. Здесь можно увидеть значения по умолчанию для различных типов.

boolean[][] booleans = new boolean; 
System.out.println("booleans : " + booleans); 
byte[][] bytes = new byte; 
System.out.println("bytes : " + bytes); 
char[][] chars = new char; 
System.out.println("chars : " + (int)chars); 
short[][] shorts = new short; 
System.out.println("short : " + shorts); 
int[][] ints = new int; 
System.out.println("ints : " + ints); 
long[][] longs = new long; 
System.out.println("longs : " + longs); 
float[][] floats = new float; 
System.out.println("floats : " + floats); 
double[][] doubles = new double; 
System.out.println("doubles : " + doubles);
Object[][] objects = new Object; 
System.out.println("objects : " + objects); 
Output booleans : false bytes : 0 chars : 0 short : 0 ints : 0 longs : 0 floats : 0.0 doubles : 0.0 objects : null

Массив символов немного сложнее, потому что, если вы печатаете 0 как символ, он напечатает нулевой символ, и поэтому я использовал его целочисленное значение, приведя к int.

Реализация

Типовым способом реализации статического гомогенного (хранящего данные одного типа) массива является следующий :

  1. Под массив выделяется непрерывный блок памяти объёмом S*m1*m2*m3…mn, где S — размер одного элемента, а m1…mn — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).
  2. При обращении к элементу массива A[i1, i2, i3, …, in] адрес соответствующего элемента вычисляется как B+S*((…(i1p*m1+i2p)*m2+…+i(n-1)p)*mn-1+inp), где B — база (адрес начала блока памяти массива), ikp — значение k-го индекса, приведённое к целому с нулевым начальным смещением. Порядок следования индексов в формуле вычисления адреса может быть различным. Приведённый соответствует реализации в большинстве компиляторов языка Си; в Фортране порядок индексов противоположен).

Таким образом, адрес элемента с заданным набором индексов вычисляется так, что время доступа ко всем элементам массива одинаково. Примечание: Одинаковость времени доступа следует понимать как отсутствие теоретической зависимости времени доступа от положения элемента и размера массива. В действительности особенности аппаратной реализации конкретной вычислительной платформы могут дать определённый разброс времени доступа. Например, CAS-латентность ОЗУ приводит к увеличению времени доступа к данным, расположенным в другой колонке (странице) ОЗУ, по отношению к предыдущим считанным данным. В практике программирования такими тонкостями обычно пренебрегают, за редчайшими исключениями.

Первый элемент массива, в зависимости от языка программирования, может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для низкоуровневых языков программирования, хотя встречается и в языках высокого уровня, например, в том же Си. В ряде языков (Паскаль, Ада, Модула-2) диапазон индексов может определяться как произвольный диапазон значений любого типа данных, приводимого к целому, то есть целых чисел, символов, перечислений, даже логического типа (в последнем случае массив имеет два элемента, индексируемых значениями «Истина» и «Ложь»).

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

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

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

Многомерный массив

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

M = 2;//количество строк
N = 3;//количество столбцов
L = 5;//глубина ячейки
//инициализация основного массива
MNL = Новый Массив(M);
Для ИндM =  По MNL.ВГраница() Цикл
	//иницаилизация вложенного массива уровня N
	MNLИндM = Новый Массив(N);
	Для ИндN =  По MNLИндM.ВГраница() Цикл
		//инициализация вложенного массива уровня L
		MNLИндMИндN = Новый Массив(L);
		Для ИндL =  По MNLИндMИндN.ВГраница() Цикл
			MNLИндMИндNИндL = "" + ИндM + ИндN + ИндL;
		КонецЦикла;//ИндL
	КонецЦикла;//ИндN
КонецЦикла;//ИндM

Такой массив может хранить элементов. В нашем случае это 30. Для программного обращения к элементам трехмерного массива необходимо указывать имя массива, а также три индекса: первый — индекс строки, второй — индекс колонки, третий — индекс глубины:

MNL = 000
MNL1 = 001
MNL2 = 002
MNL3 = 003
MNL4 = 004
MNL1 = 010
MNL11 = 011
MNL12 = 012
MNL13 = 013
MNL14 = 014
...

Для программного перебора элементов трехмерного массива нам понадобится тройной цикл: первый по элементам основного массива, второй — по элементам вложенного массива уровня N и третий — по элементам вложенного массива уровня L:

//вывод элементов массива
Для ИндM =  По MNL.ВГраница() Цикл
	Для ИндN =  По MNLИндM.ВГраница() Цикл
		Для ИндL =  По MNLИндMИндN.ВГраница() Цикл
			Сообщить("MNL = " + MNLИндMИндNИндL);
		КонецЦикла;//ИндL
	КонецЦикла;//ИндN
КонецЦикла;//ИндM

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

  • Программная работа с массивами
  • Как создать массив структур?

Многомерные массивы Java, общий синтаксис

Многомерные массивы в курсе JavaRush

На JavaRush к «обычным» массивам приступают на 7 уровне квеста Java Syntax и далее по ходу курса они встречаются неоднократно. Иногда на протяжении курса попадаются задачи на двумерные массивы (или такие, которые можно решить с их помощью).

А ещё двумерные массивы использованы в движке игр специального раздела “Игры на JavaRush”. Если вы ещё там не были, загляните и создайте пару-тройку игр. К условиям прилагаются подробные инструкции, и это послужит прекрасной тренировкой навыков программирования.

Трёхмерный массив можно обнаружить в игре Space Invaders. Через него задаётся набор фреймов для анимации (и каждый из этих фреймов — двумерный массив). Если вы уже прошли квест JavaSyntax или просто уверенно себя чувствуете в программировании на Java, попробуйте написать собственную версию этой классической игры.

Использование количества элементов многомерного массива

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

  • Length: выдает количество ячеек во всем массиве (как если бы перемножить размеры его измерений). Возвращает int, и при работе с большими массивами может возникнуть ошибка, если общее число элементов превысит максимально допустимое значение типа int.
  • Для того чтобы узнать длину измерения многомерного массива используется GetLength с указанным номером измерения в скобках. Индексация измерений ведется с нуля, потому GetLength(0) выдаст длину первого измерения.
  • Рангом массива называют его мерность. Ранг хранится в свойстве Rank.

Пример:


С этим читают