|
Абстрактный упорядоченный список для создания программ
Абстрактный упорядоченный список - очень распространенная структура данных, используемая программистами вместо баз данных. Это — примеры упорядоченных множеств. В каждом случае важен принцип, по которому упорядочивается список. Так, список продуктов, приведенный ранее, можно считать упорядоченным, если его записи соответствуют порядку, в котором продукты снимались с полок магазина, однако, если учитывать лишь названия продуктов, то список оказывается неупорядоченным.
Поддержка упорядоченных данных не сводится к их простой сортировке. Часто возникает необходимость вставить новый элемент в уже упорядоченный список. Кроме того, из упорядоченного списка иногда нужно удалить некий элемент.
Допустим, например, что в деканате хранятся списки студентов, перечисленных в алфавитном порядке. Регистратор должен вносить в них имена вновь поступивших студентов и удалять оттуда имена выпускников, причем эти операции не должны нарушать алфавитный порядок, установленный в этих списках.
Абстрактный упорядоченный список отличается от обычного абстрактного списка, поскольку вставка и удаление его элементов зависят от их значений, а не индексов. Например, операция sortedlInsert определяет позицию для вставки элемента newltem по его значению. Кроме того, у него есть новая операция, locatePosition, определяющая индекс любого элемента по заданному значению. В то же время операции sortedRetrieve и Indala совершенно аналогичны обе они извлекают заданный элемент по его индексу. Операция sortedRetrieve позволяет, например, написать другую функцию, извлекающую элемент из упорядоченного списка и выводящую его на экран.
Разработка абстрактных типов данных должна естественным образом развиваться на протяжении всего процесса решения задачи. В качестве примера рассмотрим задачу, в которой нужно определить даты всех праздников, которые будут отмечаться в текущем году. Таким образом, мы должны проанализировать каждый день в году и установить, является ли он праздничным. Одно из возможных решений этой задачи описывается следующим псевдокодом. Какие данные рассматриваются в задаче?
В этой задаче рассматриваются даты, состоящие из месяца, дня и года. Какие операции необходимо выполнить, чтобы решить поставленную задачу? Очевидно, нам нужно определить операции над датами как это делается, например для целых чисел. Анализируя приведенный псевдокод, легко увидеть, что нам потребуются следующие операции:
1. Определить дату первого дня заданного года.
2. Определить, предшествует ли одна дата другой.
3. Определить, является ли дата праздничной.
4. Определить дату следующего дня.
Какие операции необходимо выполнить, чтобы решить поставленую задачу?
Итак, абстрактные типы данных можно разрабатывать, идентифицируя данные и выбирая для них подходящие операции. Указанные операции используются для решения поставленной задачи независимо от деталей реализации.
|