Структуры данных и эффективность алгоритмов. 4

• Название: Структуры данных и эффективность алгоритмов. 4
• Анкор: lekt1_sd4_1.doc
• Дата: 28.07.2018
• Размер: 2.32 Mb.
• Имя файла: lekt1_sd4_1.doc
• Тип: Документы; #22130
• страница: 10 из 15

Последовательность (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) и линейный список (linearlist) ограничения на доступ обеспечивают неразрушающее чтение, поэтому особое значение имеет (производная) операция просмотра последовательности.

Ограничения на доступ к элементам последовательности естественно отражаются на семантике основных операций. Последовательный доступ основан на понятии текущая позиция и допускает доступ (перемещение, навигацию) к одному (или к обоим) из концов последовательности и к соседней позиции (слева, справа или к обеим) относительно текущей. Место применения основных операций в этом случае обычно привязывается к текущей позиции. Прямой (позиционный, произвольный) доступ основан на глобальном понятии позиция элемента в последовательности и обеспечивает непосредственный доступ к элементу, если известна его позиция. Например, в АТД динамический вектор (dynamicarray, vector), позиция – это индекс элемента. Но в других реализациях других видов последовательностей идентификатор позиции может быть реализован иначе.

Понятия «номер» и «позиция» элемента – близкие, но могут не совпадать:

• 
  Номер - это собственно порядковый номер элемента в последовательности. Но порядковый номер элемента изменяется в результате выполнения операций вставки и удаления предшествующих элементов, это создает ряд неудобств в идентификации элементов последовательности.
  
• 
  Позиция - аналогична порядковому номеру в том смысле, что для элемента в заданной позиции позволяет говорить о предшествующем и следующем элементе последовательности (и их позиции). Но значение позиции элемента не изменяется в результате выполнения операций вставки и удаления предшествующих элементов, поэтому значение позиции элемента можно сохранить и использовать для доступа к этому элементу в будущем. Например, в реализации последовательности связным списком понятие «позиция» может быть представлено указателем на элемент, а в других реализациях может быть представлено идентификатором другого вида, специально поддерживаемым реализацией.
  

Для АТД «Последовательность» представляют интерес дополнительные операции вида: сцепить две последовательности, расцепить на две последовательности. Например, в АТД строка (string) такого вида операции фактически являются основными.

Для различных видов АТД «Последовательность» достижима различающаяся эффективность реализации различных операций. Например, если реализация предлагает эффективный прямой доступ к элементам последовательности, то скорее всего – время выполнения операции вставки в середине последовательности оставляет желать лучшего. Различные виды (и реализации) АТД «Последовательность» выдвигают программисту различные предложения и по составу операций и по эффективности их реализации. А потому в практике программирования обычно больший интерес представляют не столько универсальные варианты этого (как и других) АТД, а скорее специализированные, и программист должен проводить соответствующий выбор с учетом их использования в решении задач предметной области.