Теоретический минимум по Computer Science

Стеку и очереди следует отдавать предпочтение, когда гибкость, предоставляемая списком, не нужна. Использование более простого АТД гарантирует, что данные будут обрабатываться строгим и предсказуемым образом (по принципу FIFO или LIFO). Это также делает код яснее: зная, что переменная представляет собой стек, легче понять характер потоков данных на входе и выходе.

Сортированный список

Сортированный список (sorted list) бывает полезен, когда нужна постоянная упорядоченность элементов. В этих случаях вместо поиска правильной позиции перед каждой вставкой в список (и периодической сортировки его вручную) мы используем сортированный список. Что бы в него ни помещали, элементы всегда будут стоять по порядку. Ни одна из операций этого АТД не позволяет переупорядочить его элементы. Сортированный список поддерживает меньше операций, чем обычный:

• insert(e) — вставить элемент e в автоматически определяемую позицию в списке;

• delete(n) — удалить элемент, находящийся в позиции n;

• get(n): получить элемент, находящийся в позиции n.

Словарь (map) используется для хранения соответствий между двумя объектами: ключом key и значением value. Вы можете осуществить поиск по ключу и получить связанное с ним значение. Словарь хорошо подходит, например, для хранения идентификационных номеров пользователей в качестве ключей и полных имен в качестве значений. Такой словарь по заданному идентификационному номеру вернет связанное с ним имя. Существуют следующие операции для словарей:

• 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).

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

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

Связный список