Массив [Array]

[Все типы данных]

Рассматриваемые темы:
1. Что такое массив?
2. Как хранится массив в памяти компьютера?
3. Оценка сложности базовых операций

Итак что же такое массив? Определение в WikiPedia
Что важно отсюда вынести?
1) Элементы массива являются однотипными, т.е. занимают одинаковый размер в памяти.
2) Элементы находятся друг за дружкой.
3) Доступ к элементам осуществляется по индексу. Как следствие из 1) и 2) можно сказать, что этот доступ будет осуществляться за O(1).

После этих важных выводов рассмотрим тестовый класс Massiv, который поможет разобраться с некоторыми практическими вещами:
Massiv.h
Massiv.cpp
main.cpp

Если запустить проект, содержащий эти файлы, то выходной файл output.txt будет иметь вид:

1. 3 3 3 3 3
2. Address of 0 element is 3355376
3. Address of 1 element is 3355380
4. Address of 2 element is 3355384
5. Address of 3 element is 3355388
6. Address of 4 element is 3355392
7. 1
8. 1 3 3 3 3

* This source code was highlighted with Source Code Highlighter.

Адреса соседних элементов отличаются ровно на 4. На 4 байта. Это размер одного элемента.

Отсюда общий вывод:
_base    - адрес нулевого элемента.
elemSize – размер одного элемента в байтах
_base + i*elemSize – адрес i-ого элемента

Изменим значения нулевого и первого элемента рассматриваемого массива на 447707365 и на 1947081646 и проанализируем рисунок:
 
В дальнейшем будем стараться использоваться в качестве массива STL контейнер: vector

Алгоритмические сложности базовых операций:

1) Получение элемента по индексу	O(1)
2) Добавление элемента в конец	O(N) – перераспределение памяти, иначе O(1)
3) Добавление элемента в начало	O(N)
4) Добавление элемента в “середину”	O(N)
5) Удаление элемента с конца	O(1)
6) Удаление элемента с начала	O(N)
7) Удаление элемента с “середины”	O(N)

Задачи в тему (Программирование. Теоремы и задачи):
Темы “Массивы” и “Индуктивные функции”: