fbed99da

Работа со списком в стеке



Работа со списком в стеке

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

Система Mathematica предоставляет широкие возможности для операций со стеками:

  • Drop [list, n] — возвращает список list, из которого удалены первые п элементов;
  • Drop [list, -n] — возвращает список list с отброшенными последними п элементами;
  • Drop [list, {n}] — возвращает список list без n-го элемента;
  • Drop [list, {m, n}] — возвращает список list с отброшенными элементами от m-го до п-го;

  • Fold[f, x, list] — возвращает последний элемент из FoldList [f,x, list];
  • Last [list] — возвращает последний элемент списка list;
  • Rest [list] — возвращает список с уничтоженным первым элементом;
  • Take [list, n] — возвращает первые п элементов списка list;
  • Take [list, -n] — возвращает последние п элементов списка list;
  • Take [list, {m, n}] — возвращает элементы списка с порядковыми номерами от m до п.
Следующие примеры поясняют работу со стеком.

Ввод (In)

Вывод(Out)

Drop[{l

,2

,3

,4

,5},

2]

{3,

4,

5}

Drop [ { 1

,2

,3

,4

,5},

-2]

{1,

2,

3}

Drop [ { a

,b

,c

,d

,e>,

{2,4}]

(a,

e}

Last[{l

,2

,3

,4

,5}]

5

Rest[{l

,2

,3

,4

,5}]

{2,

3,

4, 5}

Take[{l

,2

,3

,4

,5},

2]

(1,

2}

Take [ { 1

,2

,a

,b

,c},

-2]

{b,

c}

Take [ { 1

,2

,3

,4

,5},

{2,4}]

{2,

3,

4}

Тривиальная процедура общения со стеком (ввести/вывести данные) ограничивает возможности стековых операций. Из житейского опыта мы знаем, что, проявив настойчивость, можно вставить тарелку и в середину стопки. Mathematica предоставляет ряд расширенных возможностей для работы со списками, выходящих за рамки обычных стековых операций.

Так, например, для расширения списка путем включения в него новых элементов используются следующие функции:

  • Append [list, element] — добавляет элемент в конец списка;
  • PreoendTlist.element1 — добавляет элемент в начало списка:
  • Insert [list, element, n] — вставляет элемент в позицию п (отсчет пози-ций.ведется с начала списка, а если число п отрицательное — то с конца). Данной функцией можно включать элемент в несколько позиций, указав каждую в фигурных скобках, взяв все перечисление в еще одни фигурные скобки и использовав его вместо п. При этом надо учитывать, что все позиции включаемых элементов определяются одновременно до начала расширения списка.
Следующие примеры иллюстрируют применение этих функций.

Ввод (In)

Вывод(Out)

1={1,2,3}

(1,

2,

3}

Append[l,e]

(1,

2,

3,

e}

Prepend[l,e]

{e,

1,

2,

3}

Insert[l,e,2]

{1,

e,

2,

3}

L={1, 2, 3, 4

, 5}

{1,

2,

3,

4, 5}

Insert [L, e,

-5]

(1,

e,

2,

3, 4, 5}

Insert [L, e,

{{1},{5}}]

(e,

1,

2,

3, 4, e, 5}

Обратите внимание на то, что в данном случае элементы списка — числа, тогда как вставляемый элемент имеет символьное значение е.

Следует отметить, что описанные для стека функции Drop и Rest позволяют удалить из списка последний или первый элемент. Функция Delete [list, i] позволяет удалить из списка произвольный i-й элемент. Если i>0, то отсчет удаленного элемента идет с начала списка, а если i<0 — с конца:

L:={1,2,3,4,5}

{Delete[L,l],Delete[L,3],Delete[L,5]}

{{2, 3, 4, 5}, {1, 2, 4, 5}, {1, 2, 3, 4}}

{Delete[L,-2],Delete[L,-5]}

{{1, 2, 3, 5}, (2, 3, 4, 5}}

Delete[{l,2,3,{a,b,c},4,5},2]

{1, 3, {a, b, c}, 4, 5}

Если элементом списка является список, то он фигурирует как один элемент. Можно, однако, удалить избранный элемент из элемента списка, указав в фигурных скобках вместо i номер элемента списка во внешнем списке и номер удаляемого элемента во внутреннем списке. Это иллюстрируют следующие примеры:

Delete[(1,2,3,{а,Ь,с},4,5},{4,3}]

{1, 2, 3, {а, b}, 4, 5}

Delete[{1,2,3,{а, b, с},4,5},{4,1}]

{1, 2, 3, {b, с}, 4, 5}

Наконец, с помощью функции Delete можно удалить несколько элементов списка, указав каждый из них в фигурных скобках и оформив это указание также в фигурных скобках:

Delete [ {1,2,3, {a, b, c} , 4, 5}, {{2}, {4} ,{ 5}}]

{1, 3, 5}

Следует иметь в виду, что некоторые функции удаляют в списках определенные элементы. Этот вопрос будет рассмотрен ниже.



Содержание раздела