Последовательность (Sequence). [13 гл.4,5,11.1; 7 п.2.1-4; 3 гл.3-4; 4 п.10.1-3.]
Бесконечная
(конечная) последовательность
формально определяется как функция,
областью определения которой является
множество положительных целых чисел:
f(i)=
,
.
Во многих случаях индексирование
последовательности более удобно начинать
с нуля; тогда областью определения /
будет множество целых неотрицательных
чисел. Аналогично определим конечную
последовательность или список как
функцию, областью определения которой
является множество {1, 2, ...,
}.
Концепция последовательности, в которой элементы следуют друг за другом, в программировании является фундаментальной. Последовательность встречается в построковом выводе кода компьютерной программы, где порядок команд определяет выполняемые программой действия. Последовательность сетевых пакетов составляет сообщение электронной почты, поскольку сообщение будет иметь смысл только при приеме пакетов в той же последовательности, в которой они отправлены. Последовательности представляют такие важные отношения между объектами, как «следующий» и «предыдущий». Кроме того, последовательности зачастую используются для реализации других структур данных, то есть они представляют собой блоки, на которых базируется проектирование таких структур.
Множество возможных значений – конечные последовательности элементов одинакового типа.
Набор операций:
Вставить элемент в последовательность.
Удалить элемент из последовательности.
Посмотреть – функция, возвращающая значение элемента последовательности.
Разновидности этого вида АТД различаются способом доступа к элементам последовательности и ограничениями на место вставки и удаления элементов.
Для АТД этого вида стек (stack), очередь (queue) и дек (deque от Double Ended Queue - двусторонняя очередь) характерно разрушающее чтение, т.к. доступ к элементам (для всех трех операций) ограничен одним из концов последовательности и операцию «посмотреть другой элемент» можно выполнить, только удалив мешающие этому элементы. Для АТД вектор(array, vector), файл (file) и линейный список (linear list) ограничения на доступ обеспечивают неразрушающее чтение, поэтому особое значение имеет (производная) операция просмотра последовательности.
Ограничения на доступ к элементам последовательности естественно отражаются на семантике основных операций. Последовательный доступ основан на понятии текущая позиция и допускает доступ (перемещение, навигацию) к одному (или к обоим) из концов последовательности и к соседней позиции (слева, справа или к обеим) относительно текущей. Место применения основных операций в этом случае обычно привязывается к текущей позиции. Прямой (позиционный, произвольный) доступ основан на глобальном понятии позиция элемента в последовательности и обеспечивает непосредственный доступ к элементу, если известна его позиция. Например, в АТД динамический вектор (dynamic array, vector), позиция – это индекс элемента. Но в других реализациях других видов последовательностей идентификатор позиции может быть реализован иначе.
Понятия «номер» и «позиция» элемента – близкие, но могут не совпадать:
Номер - это собственно порядковый номер элемента в последовательности. Но порядковый номер элемента изменяется в результате выполнения операций вставки и удаления предшествующих элементов, это создает ряд неудобств в идентификации элементов последовательности.
Позиция - аналогична порядковому номеру в том смысле, что для элемента в заданной позиции позволяет говорить о предшествующем и следующем элементе последовательности (и их позиции). Но значение позиции элемента не изменяется в результате выполнения операций вставки и удаления предшествующих элементов, поэтому значение позиции элемента можно сохранить и использовать для доступа к этому элементу в будущем. Например, в реализации последовательности связным списком понятие «позиция» может быть представлено указателем на элемент, а в других реализациях может быть представлено идентификатором другого вида, специально поддерживаемым реализацией.
Для АТД «Последовательность» представляют интерес дополнительные операции вида: сцепить две последовательности, расцепить на две последовательности. Например, в АТД строка (string) такого вида операции фактически являются основными.
Для различных видов АТД «Последовательность» достижима различающаяся эффективность реализации различных операций. Например, если реализация предлагает эффективный прямой доступ к элементам последовательности, то скорее всего – время выполнения операции вставки в середине последовательности оставляет желать лучшего. Различные виды (и реализации) АТД «Последовательность» выдвигают программисту различные предложения и по составу операций и по эффективности их реализации. А потому в практике программирования обычно больший интерес представляют не столько универсальные варианты этого (как и других) АТД, а скорее специализированные, и программист должен проводить соответствующий выбор с учетом их использования в решении задач предметной области.