• set(key, value) — добавить элемент с заданным ключом и значением;
• delete(key) — удалить ключ key и связанное с ним значение;
• get(key) — получить значение, связанное с ключом key.
Множество
Множество (set) представляет неупорядоченные группы уникальных элементов, подобные математическим множествам, которые описаны в приложении III. Этот АТД используется, когда неважен порядок следования элементов либо когда нужно обеспечить уникальность элементов в группе. Стандартный набор операций для множества включает в себя:
• add(e) — добавить элемент в множество или вернуть ошибку, если элемент уже присутствует в множестве;
• list() — перечислить все элементы, присутствующие в множестве;
• delete(e) — удалить элемент из множества.
АТД для программиста — как приборная панель для водителя. Но давайте все-таки попробуем понять, как проложены провода за этой приборной панелью.
4.3. Структуры
Абстрактный тип данных лишь описывает, какие действия можно совершать с переменными конкретного типа. Он определяет список операций, но не объясняет, как они выполняются. Со структурами данных — обратная ситуация: они описывают, как данные организованы и как к ним получить доступ в памяти компьютера. Структуры данных обеспечивают реализацию АТД в модулях обработки данных.
Есть множество разных способов реализации АТД, потому что существуют самые разные структуры данных. Выбор реализации АТД, которая использует структуру данных, лучше соответствующую вашим потребностям, имеет существенное значение для создания эффективных компьютерных программ. Далее мы рассмотрим наиболее распространенные структуры данных и узнаем об их сильных и слабых сторонах.
Массив
Массив (array) — это самый простой способ хранения набора элементов в памяти компьютера. Он заключается в выделении единого пространства в памяти и последовательной записи в него ваших элементов. Конец последовательности отмечается специальным маркером NULL (рис. 4.1).
Рис. 4.1. Массив в памяти компьютера
Каждый объект в массиве занимает такой же объем памяти, что и любой другой. Представим массив, начинающийся с адреса ячейки памяти s, где каждый элемент занимает b байт. Чтобы получить n-й элемент, нужно извлечь b байт, начиная с позиции в памяти s + (b × n).
Это позволяет напрямую обращаться к любому элементу массива. Массив наиболее полезен для реализации стека, однако он может также использоваться для списков и очередей. Массивы легко программируются и имеют преимущество, позволяя мгновенно обращаться к любым элементам. Но есть у них и недостатки.
Может оказаться практически нецелесообразным выделять большие непрерывные блоки памяти. Если вам нужно наращивать массив, то в памяти может не оказаться смежного с ним достаточного большого пространства. Удаление элемента из середины массива сопряжено с определенными проблемами: вам придется сдвинуть все последующие элементы на одну позицию к началу либо отметить пространство памяти удаленного элемента как свободное. Ни один из этих вариантов не желателен. Аналогично вставка элемента внутрь массива вынудит вас сдвинуть все последующие элементы на одну позицию к концу.
Связный список
Cвязный список (linked list) позволяет хранить элементы в цепи ячеек, которые не обязательно должны находиться в последовательных адресах памяти. Память для ячеек выделяется по мере необходимости. Каждая ячейка имеет указатель, сообщающей об адресе следующей в цепи. Ячейка с пустым указателем (NULL) отмечает конец цепи (рис. 4.2).
Связные списки используются для реализации стеков, списков и очередей. При наращивании связного списка не возникает никаких проблем: любая ячейка может храниться в любой части памяти. Таким образом, размер списка ограничен только объемом имеющейся свободной памяти. Также не составит труда вставить элементы в середину списка или удалить их — достаточно просто изменить указатели ячеек (рис. 4.3).
Рис. 4.2. Связный список в памяти компьютера
Рис. 4.3. Добавление элемента между B и C. Удаление C
Связный список тоже имеет свои недостатки: мы не можем сразу получить n-й элемент. Сначала придется прочитать первую ячейку, извлечь из нее адрес второй ячейки, затем прочитать вторую ячейку, извлечь из нее указатель на следующую ячейку и т. д., пока мы не доберемся до n-й ячейки.
Кроме того, когда известен адрес всего одной ячейки, не так просто ее удалить или переместиться по списку назад. Не имея другой информации, нельзя узнать адрес предыдущей ячейки в цепи.
Двусвязный список
Двусвязный список (double linked list) — это связный список, где ячейки имеют два указателя: один на предыдущую ячейку, другой — на следующую (рис. 4.4).
Рис. 4.4. Двусвязный список в памяти компьютера
Он обладает тем же преимуществом, что и связный список: не требует предварительного выделения большого блока памяти, потому что пространство для новых ячеек может выделяться по мере необходимости. При этом дополнительные указатели позволяют двигаться по цепи ячеек вперед и назад. В таком случае, если известен адрес всего одной ячейки, мы сможем быстро ее удалить.
И тем не менее мы по-прежнему не имеем прямого доступа к n-му элементу. Кроме того, для поддержки двух указателей в каждой ячейке требуется более сложный код и больше памяти.
Массивы против связных списков
Языки программирования с богатым набором средств обычно включают встроенные реализации списка, очереди, стека и других АТД. Эти реализации часто основаны на некоторой стандартной структуре данных. Некоторые из них могут даже автоматически переключаться с одной структуры данных на другую во время выполнения программ, в зависимости от способа доступа к данным.
