Основы программирования



              

Массив как базовая структура - часть 2


Например, поиск элемента в массиве, если его элементы не упорядочены, невозможно реализовать эффективно: нельзя изобрести ничего лучшего, кроме последовательного перебора элементов. В случае упорядоченного хранения элементов можно использовать эффективный бинарный поиск, но затруднения возникают при добавлении или удалении элементов в середине массива и приводят к массовым операциям, т.е. операциям, время выполнения которых зависит от числа элементов структуры. От этих недостатков удается избавиться, реализуя множество элементов на базе сбалансированных деревьев или хеш-функции.

Есть и другие причины, по которым необходимо использовать более сложные, чем массивы, структуры данных. Логика многих задач требует организации определенного порядка доступа к данным. Например, в случае очереди элементы можно добавлять только в конец, а забирать только из начала очереди; в стеке доступны лишь элементы в вершине стека, в списке — элементы до и за указателем.

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




Содержание  Назад  Вперед