 |
Списковые структуры.
|
|
|
|
Полезный метод изучения строк – рассматривать строки как последовательность входящих в них подстрок. Например, Паскаль-программа – это строка, составленная из слов, пробелов и специальных символов. И мы знаем, что человеку будет крайне сложно в ней разобраться, если границы между синтаксическими единицами не будут выделены соответствующим образом. В данном случае важны и границы подстрок и порядок их появления и возможность изменения этого порядка.
Существует структура, представляющая из себя упорядоченный набор объектов, которая называется списком. Список записывается как последовательность, разделенная запятыми ограниченная угловыми скобками.
Например, для строки
†this is a list example†
список литералов
<†th†, †is †, †is †, †a †, †list example†>
предлагает нам вариант нарезки данной строки. Выражение Pascal произведет один и тот же OUTPUT, если будет использована данная строка или список, полученный в результате ее разбиения на подстроки.
WRITE(‘this is a list example’);
WRITE(‘th’, ‘is ‘, ‘is ‘, ‘a ‘, ‘list example’);
Спискам, как и строкам, могут быть присвоены имена, например:
L = <†th†, †is †, †is †, †a †, †list example†>
M = <†this is a list example†>
Приведенные списковые представления строк также являются строками, включая угловые скобки, маркеры границ строк, символы равенства и имена списков. Символы и слова даже в математике используются разными способами и в разных контекстах имеют разное значение. В нашем случае угловые скобки имеют совершенно другой смысл, чем при рассмотрении синтаксиса с помощью BNF.
Если элемент x находится в списке K, мы обозначаем факт как принадлежности списку как
|
|
|
x Î K, если список K не имеет ни одного вхождения объекта x, мы говорим, x Ï K.
Например, †is † Î L, но †is † Ï M.
Список L содержит пять подстрок, которые могут быть обозначены следующим образом:
L1 = †th†
L2 = †is †
L3 = †is †
L4 = †a †
L5 = †list example†
В то время M как содержит только одну строку
M1 = †this is a list example†
Мы будем использовать индексы для именования элементов списков, используя 1 для обозначения первого элемента и т.д. L можно назвать 5-список, M - 1-список. Список без элементов, 0-список, называется пустым списком и обозначается <>. Необходимо отличать список, содержащий в себе одну строку, от этой строки. Например, M – 1-список с первым и единственным элементом M1 и
M = <M1>, но M ¹ M1
Также необходимо иметь ввиду, что
<††> ¹ <>
потому что <††> это 1-спиоск, первый элемент которого пустая строка, а <> - 0-список и первый элемент там отсутствует.
Элементами списков могут быть не только строки, но и символы и другие списки. Например, список
C = <c, h, a, r, a, c, t, e, r>
Является списком символов и это не то же самое, что строка †character†
Следующий список является списком списков
<M, M> = <<†this is a list example†>, <†this is a list example†>>
где элементами 2-списка являются 1-списки М, рассмотренные выше.
Список может иметь элементы различных видов, например
Q = <A, <A>, †A†>
Содержит элементы, которые являются соответственно символом, списком и строкой.
Элемент данного списка Q2 содержит единственный элемент – символ A.
(Q2)1 = A
|
|
|
