Стеки, очереди, деки

Содержание

Слайд 2

Стек – это последовательный список переменной длины, включение и исключение элементов

Стек – это последовательный список переменной длины, включение и исключение элементов

из которого производится только с одной стороны.
(англ. stack [stæk] — стопка, пачка)
Стеки иногда называют магазинами.
Для обозначения стеков часто используется аббревиатура LIFO
( last-in / first-out – «последний вошел – первый вышел»).
Стек используют для хранения элементов, доступных в вершине списка (top).
Структура стека аналогична стопке тарелок на полке буфета или стопке книг.
В этих примерах можно взять только верхний предмет, а добавить новый предмет можно, только положив его сверху.
В структуре стека важное место занимают операции добавления и удаления элементов:
Операция Push добавляет элемент в вершину стека.
Операция Pop удаляет элемент из стека.
Слайд 3

Абстрактное понятие стека допускает неопределенно большой список. Логически подносы в столовой

Абстрактное понятие стека допускает неопределенно большой список. Логически подносы в столовой

могут складываться бесконечно. В действительности подносы находятся на полке, а овощи нанизаны на коротких шампурах. Когда полка или шампур переполнены, мы не можем добавить (Push) еще один элемент в стек.
Стек достигает максимального количества элементов, которыми он может управлять. Эта ситуация поясняет значение условия полного стека (stack full). Другая крайность — вы не можете взять поднос с пустой полки. Условие пустого стека (stack empty) подразумевает, что вы не можете удалить (Pop) элемент.
Описание ADT Stack включает только условие пустого стека. Условие полного стека является уместным в том случае, если реализация содержит верхнюю границу размера стека.
Слайд 4

ADT Stack (абстрактный тип данных) Данные Список элементов с позицией top,

ADT Stack (абстрактный тип данных)
Данные
Список элементов с позицией top, указывающей на

вершину стека.
Операции
Конструктор
Начальные значения: Нет.
Процесс: Инициализация вершины стека.
StackEmpty
Вход: Нет
Предусловия: Нет
Процесс: Проверка, пустой ли стек.
Выход: Возвращать True, если стек пустой, иначе возвращать False.
Постусловия: Нет
Push
Вход: Элемент для стека.
Предусловия: Нет.
Процесс: Сохранение элемента в вершине стека.
Выход: Нет.
Постусловия: Стек имеет новый элемент в вершине.
Слайд 5

Pop Вход: Нет Предусловия: Стек не пустой. Процесс: Удаление элемента из

Pop
Вход: Нет
Предусловия: Стек не пустой.
Процесс: Удаление элемента из вершины стека.
Выход: Возвращать элемент из вершины

стека.
Постусловия: Элемент удаляется из вершины стека.
Peek
Вход: Нет.
Предусловия: Стек не пустой.
Процесс: Нахождение значения элемента в вершине стека.
Выход: Возвращать значение элемента из вершины стека.
Постусловия: Стек неизменный.
ClearStack
Вход: Нет.
Предусловия: Нет.
Процесс: Удаление всех элементов из стека и переустановка вершины стека.
Выход: Нет.
Постусловия: Стек переустановлен в начальные условия.
Конец ADT Stack
Слайд 6

LIFO (last-in/first-out – «последний вошел – первый вышел») При реализации стека

LIFO (last-in/first-out – «последний вошел – первый вышел»)
При реализации стека на

основе одномерного массива размер стека ограничен максимальным количеством элементов массива. При этом может возникнуть проблема переполнения.
Слайд 7

При реализации стека с помощью указателей размер стека ограничен доступным объемом

При реализации стека с помощью указателей размер стека ограничен доступным объемом

свободной памяти.
Графическая структура стека изображена на рисунке.
Слайд 8

Класс Stack Члены класса Stack включают список, индекс или указатель на

Класс Stack
Члены класса Stack включают список, индекс или указатель на вершину

стека и набор стековых операций.
Для хранения элементов стека используется массив.
В результате размер стека не может превысить количества элементов в массиве.
Объявление объекта типа Stack включает размер стека, который определяет максимальное количество элементов в списке.
Размер имеет значение по умолчанию MaxStackSize = 50.
Список (stacklist),
максимальное количе­ство элементов в стеке (size)
и индекс (top) являются закрытыми членами,
а операции — открытыми.
Слайд 9

Первоначально стек пуст и top = -1. Элементы вводятся в массив

Первоначально стек пуст и top = -1.
Элементы вводятся в массив

(функция Push) в возрастающем порядке индексов (top = 0, 1, 2)
и извлекаются из стека (функция Pop) в убывающем порядке индексов
(top = 2, 1, 0).
Например, следующий объект является стеком символов (DataType = char).
После нескольких операций Push/Pop индекс top = 2,
а элемент в вершине стека - это stacklist [top] = С.
Слайд 10

Спецификация класса Stack //ОБЪЯВЛЕНИЕ //#include //#include const int MaxStackSize = 50;

Спецификация класса Stack
//ОБЪЯВЛЕНИЕ
//#include
//#include
const int MaxStackSize = 50;
class Stack
{
private:

// закрытые данные-члены, массив стека и вершина (индекс)
DataType stacklist [MaxStackSize];
int top;
public: // конструктор; инициализирует вершину
Stack (void) ;
// операции модификации стека
void Push (const DataType& item);
DataType Pop (void) ;
void ClearStack (void);
// доступ к стеку
DataType Peek (void) const;
// методы проверки стека
int StackEmpty (void) const;
int StackFull (void) const; // реализация массива
};
Слайд 11

ОПИСАНИЕ спецификации Данные в стеке имеют тип DataType, который должен определяться

ОПИСАНИЕ спецификации
Данные в стеке имеют тип DataType, который должен определяться с

использованием оператора typedef.
Пользователь должен проверять, полный ли стек, перед попыткой поместить в него элемент и проверять, не пустой ли стек, перед извлечением данных из него.
Если предусловия для операции push или pop не удовлетворяются, печатается сообщение об ошибке и программа завершается.
StackEmpty возвращает 1(True), если стек пустой, и 0 (False) — в противном случае.
Используется StackEmpty, чтобы определить, может ли выполняться операция Pop.
StackFull возвращает l(True), если стек полный, и 0 (False) — в противном случае. Используется StackFull, чтобы определить, может ли выполняться опе­рация Push.
 ClearStack делает стек пустым, устанавливая top = -1. Этот метод позволяет использовать стек для других целей.
Слайд 12

Допустим, объявление стека и реализация содержатся в файле astack.h. typedef int

Допустим, объявление стека и реализация содержатся в файле astack.h.
typedef int DataType;
 …..
#include

astack.h; // включить описание класса Stack
……
Stack S; // объявить объект типа Stack
S.Push(10); // поместить в стек S значение 10
cout << S.Peek() << endl; // напечатать 10
// вытолкнуть 10 из стека и оставить стек пустым
if (!S.StackEmpty())
temp = S.Pop();
cout << temp << endl;
S.ClearStack(); //очистить стек
……
Слайд 13

Реализация класса Stack // инициализация вершины стека Stack::Stack (void) : top(-1)

Реализация класса Stack
// инициализация вершины стека
Stack::Stack (void) : top(-1) { }
//поместить

элемент в стек
void Stack::Push (const DataType& item)
{ // если стек полный, завершить выполнение программы
if (top == MaxStackSize-1)
{ cerr << "Переполнение стека!" << endl;
exit(1);
}
// увеличить индекс top и копировать item в массив stacklist
top++;
stacklist[top] = item;
}
Слайд 14

// взять элемент из стека DataType Stack::Pop (void) { DataType temp;

// взять элемент из стека
DataType Stack::Pop (void)
{ DataType temp;
// стек

пуст, завершить программу
if (top = = -1)
{ cerr << "Попытка обращения к пустому стеку! " << endl;
exit(1);
}
// считать элемент в вершине стека
temp = stacklist[top];
// уменьшить top и возвратить значение из вершины стека
top--;
return temp;
}
Слайд 15

// возвратить данные в вершине стека DataType Stack::Peek (void) const {

// возвратить данные в вершине стека
DataType Stack::Peek (void) const
{ //

если стек пуст, завершить программу
if (top = = - 1)
{cerr << "Попытка считать данные из пустого стека!" << endl;
exit(1);
}
return stacklist[top];
}
Слайд 16

Для защиты целостности стека класс предусматривает операции тестирования состояния стека. //

Для защиты целостности стека класс предусматривает операции тестирования состояния стека.
// тестирование

стека на наличие в нем данных
int Stack::StackEmpty(void) const
{
return (top = = -1);
}
// проверка, заполнен ли стек
int Stack::StackFull(void) const
{
return (top = = MaxStackSize-1);
}
// удалить все элементы из стека
void Stack::ClearStack(void)
{
top = -1;
}
Слайд 17

Пример применения Палиндромы. Когда DataType является типом char, приложение обрабатывает символьный

Пример применения
Палиндромы.
Когда DataType является типом char, приложение обрабатывает символьный стек.


Приложение определяет палиндромы, являющиеся строками, которые читаются одинаково в прямом и обратном порядке.
Пробелы не включаются.
Например, dad, sees являются палиндромами, a good — нет.
Слайд 18

#include // … typedef char DataType; // элементы стека - символы

#include
// …
 typedef char DataType; // элементы стека - символы
#include “astack.h"
// создает

новую строку
void Deblank (char *s, char *t)
{ // цикл до тех пор, пока не встретится NULL-символ
while (*s != NULL)
{ //если символ - не пробел, копировать в новую строку
if (*s != ‘ ‘ )
*t++ = *s;
s++; // передвинуться к следующем символу
}
*t = NULL; // добавить NULL в конец новой строки
}
Слайд 19

int main ( ) { const int True = 1, False

int main ( )
{
const int True = 1, False

= 0;
Stack S;
char palstr[80], destr[80], cr;
int i = 0;
int ispalin = 1; // полагаем, что строка - палиндром
cin.getline ( palstr,80,’\n ’); // считать в полную строку
Deblank( palstr, destr ); // удалить пробелы из строки и поместить результат в destr
i = 0; // поместить символы выражения без пробелов в стек
while ( destr[i] != 0)
{ S.Push ( destr[i] );
i++;
}
i = 0; // сравнение вершины стека с символами из оригинальной строки
while ( !S.StackEmpty( ) )
{сr= S. Pop ( ); // получить следующий символ из стека
if ( сr != destr [i] ) // если символы не совпадают, прервать цикл
{ ispalin = 0; // не палиндром
break;
}
i++;
}
if (ispalin)
cout << ispalin<<"\t"<< palstr<<" - palindrom" << "\n";
else
cout << ispalin<<"\t"< }
Слайд 20

Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники.

Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники.

Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур.
Предположим, имеется процедура A, которая вызывает процедуру B, а та в свою очередь - процедуру C.
Когда выполнение процедуры A дойдет до вызова B, процедура A приостанавливается и управление передается на входную точку процедуры B.
Когда B доходит до вызова C, приостанавливается B и управление передается на процедуру C. Когда заканчивается выполнение процедуры C, управление должно быть возвращено в B, причем в точку, следующую за вызовом C.
При завершении B управление должно возвращаться в A, в точку, следующую за вызовом B.
Правильную последовательность возвратов легко обеспечить, если при каждом вызове процедуры записывать адрес возврата в стек.
Так, когда процедура A вызывает процедуру B, в стек заносится адрес возврата в A; когда B вызывает C, в стек заносится адрес возврата в B.
Когда C заканчивается, адрес возврата выбирается из вершины стека - а это адрес возврата в B. Когда заканчивается B, в вершине стека находится адрес возврата в A, и возврат из B произойдет в A.
Слайд 21

Стек используется для размещения в нем локальных переменных процедур и иных

Стек используется для размещения в нем локальных переменных процедур и иных

программных блоков.
При каждой активизации процедуры память для ее локальных переменных выделяется в стеке; при завершении процедуры эта память освобождается.
Поскольку при вызовах процедур всегда строго соблюдается вложенность, то в вершине стека всегда находится память, содержащая локальные переменные активной в данный момент процедуры.
Этот прием делает возможной легкую реализацию рекурсивных процедур.
Когда процедура вызывает сама себя, то для всех ее локальных переменных выделяется новая память в стеке, и вложенный вызов работает с собственным представлением локальных переменных.
Когда вложенный вызов завершается, занимаемая его переменными область памяти в стеке освобождается и актуальным становится представление локальных переменных предыдущего уровня.
Слайд 22

В микропроцессорах семейства Intel, как и в большинстве современных процессорных архитектур,

В микропроцессорах семейства Intel, как и в большинстве современных процессорных архитектур,

поддерживается аппаратный стек.
Аппаратный стек расположен в ОЗУ, указатель стека содержится в паре специальных регистров - SS:SP, доступных для программиста.
Аппаратный стек расширяется в сторону уменьшения адресов, указатель его адресует первый свободный элемент.
Выполнение команд CALL и INT, а также аппаратных прерываний включает в себя запись в аппаратный стек адреса возврата.
Выполнение команд RET и IRET включает в себя выборку из аппаратного стека адреса возврата и передачу управления по этому адресу.
Пара команд - PUSH и POP - обеспечивает использование аппаратного стека для программного решения других задач.
Слайд 23

Очереди Очередь (queue) — структура данных типа «список», позволяющая добавлять элементы

Очереди
Очередь (queue) — структура данных типа «список», позволяющая добавлять элементы лишь

в конец списка, и извлекать их из его начала.
Очереди похожи на стеки.
Они также не дают доступа к произвольному элементу.
Дисциплина обслуживания FIFO (first-in/first-out) или FCFS - (first-come/first-served).
Слайд 24

Очереди часто используются в программах для реализации буфера, в который можно

Очереди часто используются в программах для реализации буфера, в который можно

положить элемент для последующей обработки, сохраняя порядок поступления.
Очередь применяется в компьютерном моделировании (например, моделирование очереди клиентов в банке).
Многопользовательские операционные системы поддерживают очереди программ, ожидающих выполнения, и заданий, ожидающих печати и т.д.
Слайд 25

Очередь может быть реализована двумя способами: на основе массивов и списками

Очередь может быть реализована двумя способами: на основе массивов и списками

при помощи указателей.
Начало очереди определяется первым элементом в очереди (front). Конец очереди – это место после его последнего элемента (rear). Эти позиции используются для вставки и удаления элементов очереди.
Подобно стеку, очередь сохраняет элементы параметризованного типа DataType. Подобно стеку, абстрактная очередь не ограничивает количество элементов ввода. Однако, если для реализации списка используется массив может возникнуть условие полной очереди.
Реализовать очередь на основе массивов можно двумя способами – линейной очередью и кольцевой очередью.
Слайд 26

Рассмотрим класс Queue - используется массив для сохранения списка элементов и

Рассмотрим класс Queue - используется массив для сохранения списка элементов и

определяет переменные, которые поддерживают позиции front и rear.
Так как для реализации списка используется массив, класс содержит метод Qfull для проверки, заполнен ли массив.
Этот метод будет не нужен, если очередь реализована связанным списком.
Параметризованный тип DataType позволяет очереди управлять различными типами данных.
Класс Queue содержит список (qlist), максимальный размер которого определяется константой MaxQSize.
Данное-член count содержит число элементов в очереди. Это значение также определяет, является ли очередь полной или пустой.
Очередь следует тестировать при помощи метода QEmpty перед удалением элемента и метода QFull перед вставкой новых данных для проверки, пуста ли очередь или заполнена.
Если предусловия для QInsert или QDelete нарушаются, программа печатает сообщение об ошибке и завершается.
Слайд 27

Спецификация класса Queue ОБЪЯВЛЕНИЕ #include … const int MaxQSize = 50;

Спецификация класса Queue
ОБЪЯВЛЕНИЕ
#include
…
const int MaxQSize = 50; // максимальный размер списка

очереди
class Queue
{
private:
int front, rear, count; // массив и параметры очереди
DataType qlist [MaxQSize];
public: Queue (void); // конструктор
// операции модификации очереди
void QInsert(const DataType& item); // item - вставляет в конец очереди
DataType QDelete(void); // удаляет и возвращает элемент в начале очереди
void ClearQueue(void);
// операции доступа
DataType QFront(void) const; // возвращает значение элемента в начале очереди
// методы тестирования очереди
int QLength(void) const;
int QEmpty(void) const;
int QFull(void) const;
};
Слайд 28

Пусть объявление очереди и реализация содержатся в файле aqueue.h. ПРИМЕР typedef

Пусть объявление очереди и реализация содержатся в файле aqueue.h.
ПРИМЕР
typedef int

DataType;
#include aqueue.h
….
Queue Q; //объявляем очередь
Q.QInsert(30); //вставляем 30 в очередь
Q.QInsert(70); //вставляем 70 в очередь
cout << Q.QLength() << endl; //печатает 2
cout << Q.QFront () << endl; //печатает 30
if (!Q.QEmpty( ))
cout << Q.QDelete( ); //печатает значение 30
cout << Q.QFront ( ) << endl; //печатает 70
Q.ClearQueue( ); //очистка очереди.
…
Слайд 29

Схема организации линейной очереди на основе массива Простейшая линейная очередь на

Схема организации линейной очереди на основе массива
Простейшая линейная очередь на основе

одномерного массива.
При исключении элемента из очереди все оставшиеся элементы данных должны смещаться вперед на одну позицию.
Начало очереди определяется первым клиентом в очереди. Конец очереди — это место непосредственно за последним элементом очереди. Когда очередь полна, клиенты должны идти к другой расчетной очереди.
Предположим, очередь ограничивается четырьмя клиентами.
Слайд 30

Вид 4: клиенты D, Е и F встают в очередь, заполняя

Вид 4: клиенты D, Е и F встают в очередь, заполняя

ее, а клиент G должен встать в другую очередь.
Данная модель не является эффективной.
Например, очередь содержит 1000 элементов.
Если один элемент удаляется из начала, тогда 999 элементов должны сместиться влево.
Реализация очереди, где вводится круговая модель - вместо сдвига элементов влево, когда один элемент удаляется, элементы очереди организованы логически в окружность.
Слайд 31

Кольцевая очередь является более эффективной. Элементы кольцевой очереди организованы логически в

Кольцевая очередь является более эффективной.
Элементы кольцевой очереди организованы логически в

окружность.
Переменная front всегда является местоположением первого элемента в очереди, и она продвигается по кругу(«по часовой стрелке») по мере выполнения удалений.
Переменная rear является местоположением, где происходит следующая вставка.
После вставки rear перемещается по кругу («по часовой стрелке») .
Переменная count поддерживает запись количества элементов в очереди, и если счетчик count равен значению MaxQSize, очередь заполнена.
Слайд 32

Круговая модель очереди Реализуем круговое движение, используя операцию остатка от деления:

Круговая модель очереди

Реализуем круговое движение, используя операцию остатка от деления:
Перемещение конца

очереди вперед: rear = (rear+1)%MaxQSize;
Перемещение начала вперед: front = (front+1)%MaxQSize;
Слайд 33

Используем целый массив qlist (размер = 4) из четырех элементов для

Используем целый массив qlist (размер = 4) из четырех элементов для

реализации круговой очереди.
Первоначально count = 0, и индексы front и rear имеют значение 0.
Последовательность вставок и удалений круговой очереди
Слайд 34

Конструктор Queue Конструктор инициализирует элементы данных front rear и count нулевыми

Конструктор Queue
Конструктор инициализирует элементы данных front rear и count нулевыми значениями.


Это задает пустую очередь.
Queue::Queue (void) : front(0), rear(0), count(0) { }
Операции класса Queue
Для работы с очередью предоставляется ограниченный набор операций, которые добавляют новый (метод QInsert) или удаляют (метод Qdelete) элемент.
Класс имеет также метод QFront, который позволяет делать выборку первого элемента очереди.
Слайд 35

Перед началом процесса вставки индекс rear указывает на следующую позицию в

Перед началом процесса вставки индекс rear указывает на следующую позицию в

списке.
Новый элемент помещается в это место, и переменная count увеличивается на 1.
qlist[rear] = item;
count++;
После помещения элемента в список индекс rear должен быть обновлен для указания на следующую позицию [Рис. (А)].
Так как мы используем круговую модель, вставка может появиться в конце массива (qlist[size-l]) с перемещением rear к началу списка [рис. (В)].
Вычисление выполняется с помощью оператора остатка (%).
rear = (rear+1) % MaxQSize;
Слайд 36

Qinsert // вставить item в круговую очередь void Queue::QInsert (const DataType&

Qinsert // вставить item в круговую очередь
void Queue::QInsert (const DataType&

item)
{ if (count = = MaxQSize) // закончить программу, если очередь заполнена
{ cerr << "Переполнение очереди!" << endl;
exit(l);
}
count++;
qlist[rear] = item;
rear = (rear+1) % MaxQSize;
}
Слайд 37

Операция QDelete удаляет элемент из начала очереди, позиции, на которую ссылается

Операция QDelete удаляет элемент из начала очереди, позиции, на которую ссылается

индекс front.
Процесс удаления начинается с копирования значения во временную переменную и уменьшения счетчика очереди.
item = qlist[front];
count --;
В круговой модели необходимо перенести front в позицию следующего элемента в списке, используя оператор остатка от деления (%) (рисунок далее).
front = (front + 1) % MaxQSize;
Значение из временной позиции становится возвращаемым значением.
Слайд 38

Qdelete // удалить элемент из начала очереди и возвратить его значение

Qdelete // удалить элемент из начала очереди и возвратить его значение


DataType Queue::QDelete(void)
{
DataType temp;
if (count = = MaxQSize) // если очередь пуста, закончить программу)
{cerr << "Удаление из пустой очереди!" << endl; exit(l); }
temp = qlist[front];
// уменьшить count на единицу продвинуть начало очереди
//и возвратить значение из начала
count--;
front = (front+1) % MaxQSize;
return temp;
}
Слайд 39

Реализация очереди с помощью указателей struct SQueue { int dann; SQueue

Реализация очереди с помощью указателей
struct SQueue { int dann;
SQueue

*next;
};
SQueue * front=NULL, * rear=NULL;
int k=0; // количество элементов очереди
Слайд 40

Очереди приоритетов (Ранее дано определение, что очередь — это структура данных,

Очереди приоритетов
(Ранее дано определение, что очередь — это структура данных, которая

обеспечивает FIFO-порядок элементов. Очередь удаляет самый «старый» элемент списка.)
Очередь приоритетов – это модифицированная версия очереди, в которой из списка удаляется элемент с высшим приоритетом.
Элементы в очереди приоритетов рассматриваются как пара «ключ-значение» (key-value pair), в которой ключ определяет уровень приоритета. Приоритет оценивается по некоторому внешнему критерию.
Очереди приоритетов находят применение в операционной системе, которая записывает процессы в список и затем выполняет их в порядке приоритета.
Например, большинство операционных систем присваивают более низкий, чем другим процессам, приоритет выполнению печати.
Приоритет 0 часто определяется как высший приоритет, а менее приоритетные имеют большее значение.
Слайд 41

Структура, называемая очередью приоритетов (priority queue), имеет опeрации PQInsert и PQDelete:

Структура, называемая очередью приоритетов (priority queue), имеет опeрации PQInsert и PQDelete:
PQInsert

просто вставляет элемент данных в список;
PQDelete удаляет из списка наиболее важный элемент (с высшим приоритетом), оцениваемый по некоторому внешнему критерию, который различает элементы в списке.
При удалении элемента из очереди приоритетов в списке может быть несколько элементов с одним и тем же уровнем приоритета.
Можно потребовать, чтобы эти элементы рассматривались как очередь, т.е. элементы с одним и тем же приоритетом обслуживались бы в порядке их поступления.
В ADT не делается никаких допущений по поводу порядка элементов с одним и тем же уровнем приоритета.
Слайд 42

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

Очередь приоритетов можно представить в виде нескольких очередей, где каждая очередь

используется для своего приоритета.
Слайд 43

ADT - очередь приоритетов описывается как список с операциями для добавления

ADT - очередь приоритетов описывается как список с операциями для добавления

или удаления элементов из списка.
Имеется серия операций, которая определяет длину списка и указывает, пуст ли список.
Существуют различные реализации очереди приоритетов.
Для очереди приоритетов рассмотрим Класс Pqueue.
Исполь­зуется параметр count и методы доступа к списку для вставки и удаления элементов.
Элементы, сохраняемые в массиве, имеют параметризованный тип DataType (чаще используются упорядоченные списки и динамические области для сохранения элементов в очереди приори­тетов).
Слайд 44

Спецификация класса PQueue ОБЪЯВЛЕНИЕ #include … const int MaxPQSize = 50;

Спецификация класса PQueue
ОБЪЯВЛЕНИЕ
#include
…
const int MaxPQSize = 50;
class PQueue
{ int

count; // массив очереди приоритетов и счетчик
DataType pqlist [ MaxPQSize ];
public:
PQueue (void); // конструктор
// операции, модифицирующие очередь приоритетов
void PQInsert(const DataType& item);
DataType PQDelete(void);
void ClearPQ(void);
// тестирующие методы
int PQEmpty(void) const;
int PQFull(void) const;
int PQLength(void) const;
};
Слайд 45

Метод PQDelete удаляет элемент с высшим приоритетом из списка. Полагаем, что

Метод PQDelete удаляет элемент с высшим приоритетом из списка.
Полагаем, что

элемент с высшим приоритетом — это элемент с наименьшим значением.
Наименьшее значение определяется с использованием оператора сравнения "<", который должен быть определен для DataType.
Пример
typedef int DataType;
…
PQueue PQ;
PQ.PQInsert(20);
PQ.PQInsert(10) ;
cout << PQ.PQLength( ) << endl; // печать 2
N= PQ.PQDelete(); // извлечь N = 10
…
Слайд 46

PQInsert // вставить элемент в очередь приоритетов void PQueue::PQInsert (const DataType&

PQInsert // вставить элемент в очередь приоритетов
void PQueue::PQInsert (const DataType& item)
{ //если

уже вcе элементы массива pqlist //использованы, завершить программу
if (count == MaxPQSize)
{ cerr << "Переполнение очереди приоритетов!" << endl;
exit(1);
}
// поместить элемент в конец списка и увеличить //count на единицу
pqlist[count] = item;
count++;
}
Слайд 47

PQDelete // удаляет элемент из очереди приоритетов и возвращает его значение

PQDelete // удаляет элемент из очереди приоритетов и возвращает его значение
DataType

PQueue::PQDelete(void)
{ DataType min;
int i, minindex = 0;
if (count > 0)
{ // найти минимальное значение и его индекс в массиве pqlist
min = pqlist[0];
// просмотреть остальные элементы изменяя минимум и его индекс
for (i = 1; i < count; i++)
if (pqlist[i] < min)
{// новый минимум в элементе pqlist[i]. новый индекс - i
min = pqlist[i];
minindex = i;
}
pqlist[minindex] = pqlist[count-1];
count--;
}
else //массив qlist пуст, завершить программу
{ cerr << "Удаление из пустой очереди приоритетов!" << endl; exit(1);}
return min;
}
Слайд 48

Операция PQInsert имеет время вычисления (порядок) О(1), так как она непосредственно

Операция PQInsert имеет время вычисления (порядок) О(1), так как она непосредственно

добавляет элемент в конец списка.
С другой стороны, операция PQDelete требует начального просмотра списка для определения минимального значения и его индекса.
Эта операция имеет время вычисления О(п), где n— это текущая длина очереди приоритетов.
Данное-член count содержит количество элементов в списке.
Это значение используется в реализации методов PQLength, PQEmpty и PQFull.
Слайд 49

Дек (от англ. deq - double ended queue, очередь с двумя

Дек (от англ. deq - double ended queue, очередь с двумя

концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка.
Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом.
Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди.
Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.
Операции над деком:
включение элемента справа;
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
определение размера;
очистка.
Дек проще всего реализовать с помощью двусвязного списка. Он позволяет просматривать, удалять и добавлять элементы в начало и в конец списка.

Деки

Слайд 50

Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо

Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо

реже, чем задачи, реализуемые на структуре стека или очереди.
Слайд 51

Вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.

Вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.
Однако,

в качестве примера такой системной поддержки можно привести организацию буфера ввода в языке REXX (REstructured eXtended eXecutor, произносится «рекс», интерпретируемый язык программирования, разработанный фирмой IBM).
В обычном режиме буфер ввода связан с клавиатурой и работает как FIFO-очередь.
Однако, в REXX имеется возможность назначить в качестве буфера ввода программный буфер и направить в него вывод программ и системных утилит.
В распоряжении программиста имеются операции QUEUE - запись строки в конец буфера и PULL - выборка строки из начала буфера.
Дополнительная операция PUSH - запись строки в начало буфера - превращает буфер в дек с ограниченным выходом.
Такая структура буфера ввода позволяет программировать на REXX весьма гибкую конвейерную обработку с направлением выхода одной программы на вход другой и модификацией перенаправляемого потока.
Слайд 52

В программных системах, обрабатывающих объекты сложной структуры, могут решаться разные подзадачи,

В программных системах, обрабатывающих объекты сложной структуры, могут решаться разные подзадачи,

каждая из которых требует, возможно, обработки не всего множества объектов, а лишь какого-то его подмножества.
Иногда возникают ситуации, когда имеется несколько разных списков, которые включают в свой состав одинаковые элементы.
В таком случае при использовании традиционных списков происходит многократное дублирование динамических переменных и нерациональное использование памяти.
Списки фактически используются не для хранения элементов данных, а для организации их в различные структуры.
Использование мультисписков позволяет упростить эту задачу.

Мультисписки

Слайд 53

Мультисписок состоит из элементов, содержащих такое число указателей, которое позволяет организовать

Мультисписок состоит из элементов, содержащих такое число указателей, которое позволяет организовать

их одновременно в виде нескольких различных списков.
За счет отсутствия дублирования данных память используется более рационально.
Слайд 54

Слайд 55

Для того чтобы при выборке каждого подмножества не выполнять полный просмотр

Для того чтобы при выборке каждого подмножества не выполнять полный просмотр

с отсеиванием записей, к требуемому подмножеству не относящихся, в каждую запись включаются дополнительные поля ссылок, каждое из которых связывает в линейный список элементы соответствующего подмножества.
В результате получается многосвязный список, или мультисписок, каждый элемент которого может входить одновременно в несколько односвязных списков.
К достоинствам мультисписков, помимо экономии памяти (при множестве списков информационная часть существует в единственном экземпляре),
следует отнести также целостность данных –
все подзадачи работают с одной и той же версией информационной части,
изменения в данных, сделанные одной подзадачей, немедленно становятся доступными для другой подзадачи.
Слайд 56

Каждая подзадача работает со своим подмножеством как с линейным списком, используя

Каждая подзадача работает со своим подмножеством как с линейным списком, используя

для этого определенное поле связок.
Специфика мультисписка проявляется только в операции исключения элемента из списка.
Исключение элемента из какого-либо одного списка еще не означает необходимости удаления элемента из памяти, так как элемент может оставаться в составе других списков.
Память должна освобождаться только в том случае, когда элемент уже не входит ни в один из частных списков мультисписка.
Обычно задача удаления упрощается тем, что один из частных списков является главным: в него обязательно входят все имеющиеся элементы.
Тогда исключение элемента из любого неглавного списка состоит только в переопределении указателей, но не в освобождении памяти.
Исключение же из главного списка требует не только освобождения памяти, но и переопределения указателей как в главном списке, так и во всех неглавных списках, в которые удаляемый элемент входил.
Слайд 57

Экономия памяти далеко не единственная причина, по которой применяют мультисписки. Многие

Экономия памяти далеко не единственная причина, по которой применяют мультисписки.
Многие

реальные структуры данных не сводятся к типовым структурам, а представляют собой некоторую комбинацию из них.
Причем комбинируются в мультисписках самые различные списки линейные и циклические, односвязные и двунаправленные.
Слайд 58

Часто в виде мультисписков представляют матрицы очень большой размерности, в которых

Часто в виде мультисписков представляют матрицы очень большой размерности, в которых

большинство элементов равны 0 (такие матрицы называются разреженными).
Мультисписки обеспечивают эффективное хранение таких структур в памяти: хранятся только те элементы, которые отличны от 0.
Каждый элемент входит в два списка: в список-строку и список-столбец.
Вся матрица представлена m + n списками, где m и n — соответственно число строк и число столбцов матрицы, каждый элемент хранит значение элемента матрицы и две ссылки: на следующий элемент в строке и на следующий элемент в столбце, указатели на начала этих списков хранятся в двух массивах.
Описание типа данных одного элемента матрицы-мультисписка аналогично описанию элемента-очереди или узла дерева.
Для описания матрицы потребуется два массива — массив указателей на первые элементы списков—строк и на первые элементы списков-столбцов.
Слайд 59

Слайд 60

Нелинейные разветвленные списки Нелинейным разветвленным списком является список, элементами которого могут

Нелинейные разветвленные списки

Нелинейным разветвленным списком является список, элементами которого могут

быть тоже списки.
(a,(b,c,d),e,(f,g))
( )
((a))
Схематическое представление разветвленного списка
- Предыдущая
С Новым годом и Рождеством. Администрация и Профком
Следующая -
Уравнения химических реакций

Похожие презентации

Презентация "Дисплейные технологии: сегодня и завтра" - скачать презентации по Информатике
Робот – фельдшер. Мобильная робототехника 14+
Особенности проведения первого этапа аккредитации в дистанционной форме
Component Enabler for .NET. Overview
Sociologia generale e dell’innovazione digitale
Проектирование программного комплекса для автоматизации деятельности автозаправочной станции
მონაცემთა ბაზები
MS Word. Интерфейс, элементы документа, начало работы с документом
Вставка объектов в текстовый документ
Разработка программного средства для автоматизации документооборота в системе клиент-банк
Представление чисел в компьютере. Неотрицательные числа
Системное программное обеспечение: антивирусные программы
Intro to AI Platform
Запрос и отчёты в базах данных
Теория принятия решений принятие оптимальных решений методами динамического программирования
Текстовый редактор word. 9-10 класс
База данных - основа информационной системы
«1С:Расчет квартплаты и бухгалтерия ЖКХ» для предприятий ЖКХ Сервис «Отраслевые решения 1С через Интернет»
Программирование задач с ветвлением
ИТ в гуманитарных исследованиях
Аттестационная работа. Образовательная программа. Создание мобильных приложений в App Inventor 2
Основы алгебры логики
Прикладное программное обеспечение
Простые типы данных языка Assembler. Сегмент данных
Мәліметтер қоры (МҚ)
Проектирование реляционной базы данных. Основные принципы проектирования
Creation of a regional political talk-show
Заключительный урок по информатике. Викторина. 10 класс
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть