Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата

L нет позиции р, то результат выполнения этого оператора не определён.

LOCATE(x, L). Эта функция возвращает позицию объекта х в списке L.если в списке объект х встречается несколько раз, то возвращается позиция первого от начала списка объекта х. Если объекта х нет в списке L, то возвращается END(L).

RETRIEVE(p, L). Эта функция возвращает элемент, который стоит в позиции р в списке L. Результат не определён, если p = END(L) или в списке L нет позиции p. Элементы должны быть одного типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.

DELETE(p, L). этот оператор удаляет элемент в позиции p списка L. Так, если список L состоит из элементов a1, a2, …, an, то после выполнения этого оператора он будет иметь вид a1, a2, …, ap-1, ap+1, …, an.

Результат не определён, если в списке L нет позиции p или p = END(L).

NEXT(p, L) и PREVIOUS(p, L). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции p в списке L.если р – последняя позиция в списке L, то NEXT(p, L) = END(L). Функция NEXT не определена, когда p = END(L). Функция PREVIOUS не определена, если p =

1. Обе функции не определены, если в списке L нет позиции p.

MAKENULL(L). Эта функция делает список L пустым и возвращает позицию

END(L).

FIRST(L). Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция END(L).

8. PRINTLIST(L). Печатает элементы списка L в порядке их расположения.

Стеки.

Стек – это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Стеки также иногда называют «магазинами», а в английской литературе для обозначения стеков ещё используется аббревиатура LIFO (last-in-first- out – последний вошел – первый вышел). Интуитивными моделями стека могут служить колода карт на столе при игре в покер, книги, сложенные в стопку, или стопка тарелок на полке буфета; во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний. Абстрактные типы данных семейства STAK (Стек) обычно используют следующие пять операторов.

MAKENULL(S). Делает стек S пустым.

TOP(S). Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIEVE(FIRST(S), S).

POP(S). Удаляет из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S),

S). Иногда этот оператор реализуется в виде функции, возвращающей удаляемый элемент.

PUSH(x, S). Вставляет элемент x в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т.д. В терминах общих операторов списка данный оператор можно записать как INSERT(x, FIRST(S), S).

EMPTY(S). Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.

Очереди.

Другой специальный тип списка – очередь (queue), где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют «списками типа FIFO»

(аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел – первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Кроме того, различна устоявшаяся терминология для стеков и очередей. Для работы с очередями будут использоваться следующие операторы.

MAKENULL(Q) очищает очередь Q, делая её пустой.

FRONT(Q) – функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как

RETRIEVE(FIRST(Q), Q).

Рекомендуем скачать другие рефераты по теме: реферат китай курсовые работы, бесплатные шпаргалки по праву.





Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата