Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Protected
|
|
fHead: pItem; // поле - указатель на вершину стека
fSize: Word; // поле - число элементов стека
Public
property Size: Word read fSize; // свойство - число элементов стека
procedure Push(v: tValue); // включение элемента со значением v
function Pop: tValue; // исключение верхнего элемента стека
function Empty: Boolean; // возвращение true, если стек пуст
function TopValue: tValue; // возвращение значения верхнего элемента
procedure Clear; // очистка стека
constructor Create; // конструктор - создание пустого стека
destructor Destroy; override; // деструктор - удаление стека
end; // tStack
Свойство Size доступно только для чтения. Конструктор Create выполняет операции fHead: =nil и fSize: =0. Деструктор Destroy вызывает метод Clear для удаления элементов стека из памяти. Метод Push включает элемент в вершину стека и увеличивает число элементов стека на 1. Метод Pop исключает элемент из вершины стека и уменьшает на 1 размер стека.
4. Реализация основных операций над стеком
Включение элемента со значением v в стек:
Одинарными линиями показаны связи в исходном состоянии стека, пунктирными – связи, устанавливаемые в процессе выполнения операции. Сначала организуется вспомогательная динамическая переменная с указателем NewItem типа pItem. В поле значения этой переменной записывается значение нового элемента стека, в поле ссылки – адрес верхнего элемента стека, на который указывала ранее переменная fHead. Затем указатель fHead получает значение адреса вновь созданного элемента стека.
Реализация метода включения элемента в стек:
procedure tStack.Push(v: tValue);
Var
NewItem: pItem; // указатель на новый элемент
Begin
NewItem: = New(pItem); // выделение памяти под новый элемент стека
NewItem^.Value: = v; // запись v в поле значения нового элемента
NewItem^.Next: = fHead; // fHead -> в поле ссылки нового элемента
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
fHead: = NewItem; // перемещение fHead на новый элемент
Inc(fSize); // увеличение числа элементов стека на 1
end; //procedure tStack.Push
Исключение элемента из стека. Сначала читается значение верхнего элемента стека. Затем в переменную DisItem типа pItem из указателя fHead переписывается адрес верхнего элемента стека. Указатель fHead перемещается на элемент стека, следующий за выталкиваемым, и освобождается занимаемая исключаемым элементом память. Схема исключения:
Реализация метода исключения элемента из стека:
function tStack.Pop: tValue;
// Исключение верхнего элемента из стека и возвращение его значения
Var
DisItem: pItem; // указатель на исключаемый элемент
Begin
Pop: = fHead^.Value; // чтение верхнего элемента стека
DisItem: = fHead; // получение адреса исключаемого элемента
fHead: = fHead^.Next; // перемещение вершины на следующий элемент
Dispose(DisItem); // удаление из памяти бывшего верхнего элемента
Dec(fSize); // уменьшение числа элементов стека на 1
end; // function tStack.Pop
Операция Pop неприменима к пустому стеку, поэтому перед ее выполнением необходимо проверять значение признака «стек пуст».
Выработка признака «стек пуст» выполняется следующим образом:
function tStack.Empty: Boolean;
// Возвращает Empty=True, если стек пуст
Begin
Empty: = fHead = nil;
end; // function tStack.Empty
5. Использование стека для преобразования
форм записи выражений.
В инфиксной записи операция разделяет два операнда, в постфиксной – операция следует за двумя операндами, в префиксной – операция предшествует двум операндам. Например:
| Инфиксная запись | Постфиксная запись | Префиксная запись |
| A+B | AB+ | +AB |
| A+B–C | AB+C– | +A–BC |
| A*B+C | AB*C+ | +*ABC |
| A+B*C | ABC*+ | +A*BC |
| (A+B)*C | AB+C* | *+ABC |
v Перевод из инфиксной формы записи выражения в постфиксную (польскую). Инфиксное выражение сканируется слева направо, и в зависимости от вида очередного элемента выражения выполняется одно из следующих действий:
| Элемент выражения | Действие |
| Открывающая скобка | Вталкивание элемента в стек. |
| Операнд | Запись элемента в постфиксную строку. |
| Закрывающая скобка | Выталкивание элементов из стека до первой открывающей скобки и запись их в постфиксную строку, затем выталкивание самой открывающей скобки без записи ее в постфиксную строку. Если перед выполнением этой операции стек оказался пустым, значит, для данной закрывающей скобки не было парной открывающей, т.е. возникла исключительная ситуация. |
| Операция | Если стек не пуст, и приоритет операции ниже (£), чем у верхней операции в стеке, то выталкивание элементов из стека до операции с меньшим приоритетом или до опустошения стека и запись их в постфиксную строку; в противном случае стек не изменяется. Затем вталкивание операции в стек. |
После просмотра выражения выталкиваются из стека и записываются в постфиксную строку все оставшиеся в стеке операции.
v Вычисление значения выражения по его постфиксной записи.
Постфиксное выражение сканируется слева направо и обрабатывается следующим образом:
| Элемент выражения | Действие |
| Операнд | Вталкивание элемента в стек |
| Операция | Выталкивание из стека двух элементов, выполнение операции с ними, запись результата в стек, если стек не пуст. |
v Перевод из инфиксной формы записи выражения в префиксную.
Инфиксное выражение сканируется справа налево, и префиксная строка строится также справа налево. Алгоритм преобразования такой же, как и при преобразовании в постфиксную форму, только открывающие скобки меняются на закрывающие и, наоборот, при определении приоритета операции «£» изменяется на «<», чтобы равноприоритетные операции выполнялись слева направо.
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.
Для новых пользователей первый месяц бесплатно. Зарегистрироваться в сервисе
v Вычисление значения выражения по его префиксной записи.
Алгоритм вычисления полностью совпадает с алгоритмом вычисления по постфиксной записи, но префиксная строка сканируется справа налево.
6. Очередь
Очередью называется упорядоченный набор элементов, которые могут исключаться с одного ее конца (называемого началом очереди), а включаться с другого конца (называемого концом очереди). Каждый элемент очереди характеризуется одним и тем же набором полей. Логическая структура очереди:
| Исключение | • | A | B | C | D | E | • | Включение |
| — | — | |||||||
| Начало | Конец |
Очередь функционирует по принципу FIFO (First In – First Out: «первым пришел – первым исключается»). В реальном мире имеется множество примеров очередей: очередь к кассе магазина, очередь задач, обрабатываемых вычислительной машиной. Каждый элемент очереди может содержать одно или несколько полей, число элементов в очереди не ограничено. Очередь, не содержащая ни одного элемента, называется пустой.
7. Операции над очередью
Над очередью q (от англ. queue – очередь) могут быть выполнены следующие операции:
1) включение нового элемента v в конец очереди – Insert (q, v);
2) исключение элемента из начала очереди – Remove (q) и возвращение его значения;
3) выработка признака «очередь пуста» – Empty (q);
4) считывание первого элемента без его удаления – HeadValue (q);
5) считывание последнего элемента очереди – RearValue (q);
6) определение числа элементов очереди Size (q);
8) очистка очереди – Clear (q).
Первые три операции над очередью являются основными. Операции Empty, Size, и Clear для очереди аналогичны соответствующим операциям для стека.
8. Дек
Деком (DEQ – от английского double ended queue, очередь с двумя концами) называется упорядоченный набор элементов, включение и исключение элементов в котором могут осуществляться с любого из двух его концов. Логическая структура дека:
| Включение Исключение | – • | A | B | C | D | E | – • | Исключение Включение |
| — | — | |||||||
| Начало | Конец |
Частные случаи дека – дек с ограниченным входом и дек с ограниченным выходом (включение или исключение элементов осуществляется только с одного из концов дека).
9. Операции над деком
Над деком d могут быть выполнены все операции, определенные для очереди q, а также добавляются две основные операции:
– включение элемента со значением v в начало дека – Push (d, v);
– исключение элемента из конца дека – Delete (d) и возвращение его в качестве значения функции.
10. Реализация очереди и дека
Реализация очереди (дека) с помощью динамических переменных:
При этом вводятся две переменные типа указателя на элемент очереди или дека: Head – на начало, Rear – на конец очереди или дека. В поле ссылки последнего элемента записывается значение nil.
Описание классов tQueue и tDEQ – наследников класса tStack – может быть следующим:
Type
// Описание класса tQueue
tQueue = class (tStack) // класс - очередь
|
|