На втором дне стажировки по DS и алгоритмам в Internity Foundation я узнал о важности массивов в структуре данных.
Массив представляет собой набор однородных (однотипных) элементов данных, хранящихся в смежных ячейках памяти. Например, если массив имеет тип «int», он может хранить только целые элементы и не может допускать элементы других типов, таких как double, float, char и т. д.
Представление памяти массива
На следующей диаграмме представлен массив целых чисел, состоящий из 12 элементов. Индекс массива начинается с 0, поэтому массив из 12 элементов имеет индексы от 0 до 11.
Зачем нам массив?
Массив особенно полезен, когда мы имеем дело с большим количеством переменных одного и того же типа. Например, допустим, мне нужно сохранить оценки по математике 100 учеников. Чтобы решить эту конкретную проблему, мне нужно либо создать 100 переменных типа int, либо создать массив типа int размером 100.
Очевидно, что второй вариант лучше, потому что отслеживать все 100 различных переменных — утомительная задача. С другой стороны, работать с массивом просто и легко, все 100 значений могут храниться в одном массиве с разными индексами (от 0 до 99).
Доступ к элементам массива
В этом примере у нас есть массив arr типа «int». Размер массива равен 10, что означает, что он может содержать 10 целочисленных значений. arr[0] будет первым элементом, arr[1] вторым и так далее. Здесь мы присваиваем значения только нескольким элементам массива. После этой программы я поделился выводом этой программы, который показывает, что значение элементов массива int по умолчанию равно 0. Элементы, которым не присвоено какое-либо значение, показывают свое значение как 0 (значение по умолчанию).
int main(){
int arr[] = {2,4,6,8,10,12};
int length_of_Array = sizeof(arr)/sizeof(arr[0]);
//printing size of array
cout<<length_of_Array<<endl;
//Accessing the array elements
cout<<arr[1]; //4
cout<<arr[4]; //10
}
Временная сложность массива
Давайте взглянем на временную сложность различных операций над массивами.
Преимущества и недостатки массивов
Преимущества
1. Чтение элемента массива просто и эффективно. Как показано в приведенной выше таблице, время чтения массива равно O(1) как в лучшем, так и в худшем случае. Это связано с тем, что любой элемент может быть мгновенно прочитан с использованием индексов (вычисление базового адреса за кулисами), без обхода всего массива.
2. Массив является основой других структур данных. Например, другие структуры данных, такие как LinkedList, Stack, Queue и т. д., реализованы с использованием массива.
3. Доступ ко всем элементам массива можно получить, используя одно имя (имя массива) вместе с индексом, который удобочитаем, удобен и эффективен, а не хранит эти элементы в разных-2 переменных.
Недостатки
1. При использовании массива нам необходимо принять решение о размере массива в начале, поэтому, если мы не знаем, сколько элементов мы собираемся хранить в массиве, это усложнит задачу.
2. Размер массива фиксирован, поэтому, если позже нам понадобится хранить в нем больше элементов, это невозможно сделать. С другой стороны, если мы храним меньше элементов, чем объявленный размер, оставшаяся выделенная память тратится впустую.
2D-массив
2D-массив известен как массив массивов и используется для представления матрицы элементов.
Массив массивов известен как двумерный массив. Двумерный (2D) массив в программировании на C также известен как матрица. Матрица может быть представлена в виде таблицы строк и столбцов. Прежде чем мы подробнее обсудим двумерный массив, давайте взглянем на следующую программу на C.
Пример простого двумерного (2D) массива
Пока не беспокойтесь о том, как инициализировать двумерный массив, мы обсудим эту часть позже. Эта программа демонстрирует, как сохранить элементы, введенные пользователем, в двумерный массив и как отобразить элементы двумерного массива.
#include<stdio.h>
int main(){
/* 2D array declaration*/
int disp[2][3];
/*Counter variables for the loop*/
int i, j;
for(i=0; i<2; i++) {
for(j=0;j<3;j++) {
printf("Enter value for disp[%d][%d]:", i, j);
scanf("%d", &disp[i][j]);
}
}
//Displaying array elements
printf("Two Dimensional array elements:\n");
for(i=0; i<2; i++) {
for(j=0;j<3;j++) {
printf("%d ", disp[i][j]);
if(j==2){
printf("\n");
}
}
}
return 0;
}
Вывод:
Enter value for disp[0][0]:1 Enter value for disp[0][1]:2 Enter value for disp[0][2]:3 Enter value for disp[1][0]:4 Enter value for disp[1][1]:5 Enter value for disp[1][2]:6 Two Dimensional array elements: 1 2 3 4 5 6
