вторник, 16 ноября 2010 г.

Массив [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)


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

Комментариев нет:

Отправить комментарий