Презентация - Абстрактный тип данных. Стек

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


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

Презентация содержит 44 слайда и доступна для скачивания в формате ppt. Размер скачиваемого файла: 159.00 KB

Просмотреть и скачать

Pic.1
Абстрактный тип данных стек Примеры использования абстрактного стека
Абстрактный тип данных стек Примеры использования абстрактного стека
Pic.2
Абстрактный тип данных Стек Стеком называется последовательность элементов одного и того же типа, к
Абстрактный тип данных Стек Стеком называется последовательность элементов одного и того же типа, к которой можно добавлять новые элементы и удалять элементы последовательности. Причем как добавление элементов, так и удаление элементов производится с одного и того же конца последовательности, называемого вершиной стека.
Pic.3
Операции со стеком Cоздание пустого стека Уничтожение стека Определение пуст ли стек Добавление ново
Операции со стеком Cоздание пустого стека Уничтожение стека Определение пуст ли стек Добавление нового элемента в стек Удаление верхнего элемента из стека Извлечение из стека значения верхнего элемента (вершины стека) без его удаления
Pic.4
Диаграмма абстрактного стека
Диаграмма абстрактного стека
Pic.5
Операции со стеком createStack() - создает пустой стек destroyStack ()– уничтожает стек isEmpty() –
Операции со стеком createStack() - создает пустой стек destroyStack ()– уничтожает стек isEmpty() – функция определения пустоты стека ли стек push(NewElement) – добавляет новый элемент NewElement в стек pop() – удаляет верхний элемент из стека getTop()– возвращает значение верхнего элемента (вершины стека) без его удаления
Pic.6
СТЕК
СТЕК
Pic.7
Реализация ограниченного стека в виде массива Размер массива определяет максимальное число элементов
Реализация ограниченного стека в виде массива Размер массива определяет максимальное число элементов в стеке Необходимо определить указатель top положения верхнего элемента При вставке элемента производится увеличение значения top на единицу При удалении элемента производится уменьшение значения top на единицу
Pic.8
Реализация ограниченного стека в виде массива Пусть TypeItem – тип элементов стека Max_size –максима
Реализация ограниченного стека в виде массива Пусть TypeItem – тип элементов стека Max_size –максимальный размер стека Stack [Max_size] –массив элементов стека top - указатель на вершину стека
Pic.9
Основные операции со стеком void createStack() { top=0;} void pop() {if ( top==0) cout<<’Стек
Основные операции со стеком void createStack() { top=0;} void pop() {if ( top==0) cout<<’Стек пуст’; else --top;} //конец функции pop void push(TypeItem NewItem) { if (top>=Max_size) cout<<’Стек полон’; else Stack[++top]=NewItem } //конец //функции push
Pic.10
Основные операции со стеком TypeItem getTop() {if (top==0) cout<<’Стек пуст’; else return (Sta
Основные операции со стеком TypeItem getTop() {if (top==0) cout<<’Стек пуст’; else return (Stack[top]; } int sEmpty() {return(top==0);} void destroyStack () { top=0;}
Pic.11
Ограниченный стек Еще одной реализацией ограниченного стека является описание стека с помощью динами
Ограниченный стек Еще одной реализацией ограниченного стека является описание стека с помощью динамического массива Достоинством этого метода является возможность выделения памяти по мере необходимости
Pic.12
Ограниченный стек Struct Stack { TypeItem *array; int count,max_size; }
Ограниченный стек Struct Stack { TypeItem *array; int count,max_size; }
Pic.13
Реализация стека в виде связного списка Пусть StackItemType – тип элементов стека // Узел стека Stru
Реализация стека в виде связного списка Пусть StackItemType – тип элементов стека // Узел стека Struct StackNode { StackItemType Item; StackNode * next; }; StackNode *top; // Указатель на первый элемент
Pic.14
Реализация стека в виде связного списка class Stack { public: // Конструкторы и деструкторы: // Конс
Реализация стека в виде связного списка class Stack { public: // Конструкторы и деструкторы: // Конструктор по умолчанию Stack(); // Конструктор копирования Stack(const Stack& aStack) ; // Деструктор ~Stack();
Pic.15
Реализация стека в виде связного списка // Операции над стеком: int isEmpty() const; void push(Stack
Реализация стека в виде связного списка // Операции над стеком: int isEmpty() const; void push(StackItemType newItem) void pop() void pop(StackItemType& stackTop) void getTop(StackItemType& stackTop ) const
Pic.16
Реализация стека в виде связного списка private: struct StackNode // Узел стека { StackItemType item
Реализация стека в виде связного списка private: struct StackNode // Узел стека { StackItemType item; //Данные, содержащиеся //в узле стека StackNode *next; // Указатель на следующий узел }; // end struct StackNode *top; // Указатель на первый элемент стека }; // Конец класса Stack
Pic.17
Конструкторы и деструкторы: Stack::Stack() : top(NULL) {} // Конец Конструктора по умолчанию Stack::
Конструкторы и деструкторы: Stack::Stack() : top(NULL) {} // Конец Конструктора по умолчанию Stack::Stack(const Stack& aStack) {//первый узел if (aStack. top == NULL) top=NULL; else { top = new StackNode; top->item = aStack. top->item;}
Pic.18
Конструкторы и деструкторы: //остальная часть списка StackNode *newPtr=top; for(StackNode *cur= aSta
Конструкторы и деструкторы: //остальная часть списка StackNode *newPtr=top; for(StackNode *cur= aStack. top->next; cur!=NULL; cur=cur->next) { newPtr->next=new StackNode; newPtr=newPtr->next; newPtr->item=cur->item; } newPtr->next=NULL; } } // Конец Конструктора копирования
Pic.19
Конструкторы и деструкторы: Stack::~Stack() { while(!isEmpty()) pop(); }
Конструкторы и деструкторы: Stack::~Stack() { while(!isEmpty()) pop(); }
Pic.20
Операции со стеком Stack::pop() { if (isEmpty()) cout<<“стек пуст”; else { StackNode *temp=top
Операции со стеком Stack::pop() { if (isEmpty()) cout<<“стек пуст”; else { StackNode *temp=top; top=top->next; temp->next=NULL; delete temp; } } // Конец функции pop
Pic.21
Операции со стеком Stack::pop(StackItemType & stackTop) { if (isEmpty()) cout<<“стек пуст”
Операции со стеком Stack::pop(StackItemType & stackTop) { if (isEmpty()) cout<<“стек пуст”; else { stackTop=top->item; StackNode *temp=top; top=top->next; temp->next=NULL; delete temp; } } // Конец функции pop
Pic.22
Операции со стеком Stack::push(StackItemType newItem) { StackNode *temp=new StackNode; temp->item
Операции со стеком Stack::push(StackItemType newItem) { StackNode *temp=new StackNode; temp->item=newItem; temp->next=top; top=temp } // Конец функции push
Pic.23
Операции со стеком int Stack::isEmpty() { return (top==NULL) } // Конец функции isEmpty viod Stack::
Операции со стеком int Stack::isEmpty() { return (top==NULL) } // Конец функции isEmpty viod Stack::getTop(StackItemType & stackTop) { if(isEmpty) cout<<‘стек пуст’; else stackTop=top->item; } // Конец функции getTop
Pic.24
Реализация стека в виде абстрактного списка class Stack { public: //Конструкторы и деструкторы ……………
Реализация стека в виде абстрактного списка class Stack { public: //Конструкторы и деструкторы ……………………………………. // Операции над стеком …………………………………… private: List L; // список элементов стека } // конец описания класса
Pic.25
Реализация стека в виде абстрактного списка Диаграмма класса Список
Реализация стека в виде абстрактного списка Диаграмма класса Список
Pic.26
Реализация стека в виде абстрактного списка Stack::Stack(const Stack& aStack): L(aStack. L) { };
Реализация стека в виде абстрактного списка Stack::Stack(const Stack& aStack): L(aStack. L) { }; Int Stack::isEmpty() const { return(L. isEmpty); }
Pic.27
Реализация стека в виде абстрактного списка Stack::push(StackItemType newItem) { L. insert(1,newItem
Реализация стека в виде абстрактного списка Stack::push(StackItemType newItem) { L. insert(1,newItem); }; void Stack::pop() { L. remove(1); }
Pic.28
Реализация стека в виде абстрактного списка Stack:: getTop(StackItemType& stackTop) { L. retriev
Реализация стека в виде абстрактного списка Stack:: getTop(StackItemType& stackTop) { L. retrieve(1,stackTop); }; void Stack::pop(StackItemType& stackTop) { L. retrieve(1,stackTop); L. remove(1); }
Pic.29
Алгебраические выражения Инфиксная запись выражений: каждый бинарный оператор помещается между своим
Алгебраические выражения Инфиксная запись выражений: каждый бинарный оператор помещается между своими операндами Префиксная запись выражений (Prefix): каждый бинарный оператор помещается перед своими операндами (Польская запись) Постфиксная запись выражений (Postfix): каждый бинарный оператор помещается после своих операндов (Обратная Польская запись)
Pic.30
Алгебраические выражения
Алгебраические выражения
Pic.31
Преобразование инфиксной формы в Prefix и Postfix Допустим, инфиксное выражение полностью заключено
Преобразование инфиксной формы в Prefix и Postfix Допустим, инфиксное выражение полностью заключено в скобки Преобразование в префиксную форму: каждый оператор перемещается на позицию соответствующей открывающейся скобки (перед операцией) Преобразование в постфиксную форму: каждый оператор перемещается на позицию соответствующей закрывающейся скобки (после операцией) Скобки убираются
Pic.32
Примеры Преобразование в префиксную форму: ( ( A + B ) * C ) + * *+ABC Преобразование в постфиксную
Примеры Преобразование в префиксную форму: ( ( A + B ) * C ) + * *+ABC Преобразование в постфиксную форму: ( ( A + B ) * C ) + * AB+C*
Pic.33
Преимущества префиксной и постфиксной форм записи Не нужны приоритеты операций, правила ассоциативно
Преимущества префиксной и постфиксной форм записи Не нужны приоритеты операций, правила ассоциативности, скобки Алгоритмы распознавания выражений и вычисления более просты
Pic.34
Вычисление постфиксных выражений Допустим необходимо вычислить выражение: 2*(3+4) Его постфиксная за
Вычисление постфиксных выражений Допустим необходимо вычислить выражение: 2*(3+4) Его постфиксная запись: 234+* Порядок выполнения операций: Помещаем в стек значения всех операндов, пока не встретим знак операции Выталкиваем из стека 2 операнда Производим с ними соответствующую операцию Результат помещаем в стек Повторяем операции до тех пор, пока не кончится строка символов
Pic.35
Пример (Функция Pop(op)- возвращает значение op из вершины стека и удаляет это значение из стека):
Пример (Функция Pop(op)- возвращает значение op из вершины стека и удаляет это значение из стека):
Pic.36
Псевдокод алгоритма Предположения: Строка содержит синтаксически правильное выражение Унарные операц
Псевдокод алгоритма Предположения: Строка содержит синтаксически правильное выражение Унарные операции и операции возведения в степень не используются Операнды задаются строчными буквами
Pic.37
Псевдокод алгоритма For (каждый символ ch в строке) { if (ch является операндом) // помещаем ch в ст
Псевдокод алгоритма For (каждый символ ch в строке) { if (ch является операндом) // помещаем ch в стек Push(ch); else { Opign=ch; Op2= getTop();Pop(); //извлекаем значение из вершины Op1= getTop(); Pop(); // и удаляем его // выполняем соответствующую операцию Result=Op1 Opsign Op2; // помещаем результат в стек Push(Result); }; // конец оператора if } // конец оператора For
Pic.38
Преобразование инфиксных выражение в постфиксные Будем использовать: Стек для хранения операций и ск
Преобразование инфиксных выражение в постфиксные Будем использовать: Стек для хранения операций и скобок Строку PostfixExp для формирования постфиксного выражения
Pic.39
Преобразование инфиксных выражение в постфиксные Алгоритм: Если встретился операнд – помещаем его в
Преобразование инфиксных выражение в постфиксные Алгоритм: Если встретился операнд – помещаем его в строку Если встретилась ‘(’ – помещаем в стек Если встретился оператор: Если стек пуст – помещаем оператор в стек Если стек не пуст – операторы более высокого приоритета выталкиваются и помещаются в строку, пока не встретится ‘(’ или оператор более низкого приоритета Если встретился символ ‘)’ , то все элементы выталкиваются из стека и помещаются в строку, пока не встретится соответствующая ‘(‘ Достигнув конца строки, все элементы стека добавляются в строку
Pic.40
Пример: A-(B+C*D)/F)
Пример: A-(B+C*D)/F)
Pic.41
Пример: A+B*(C/B+Z*(A+D))
Пример: A+B*(C/B+Z*(A+D))
Pic.42
Пример: A+B*(C/B+Z*(A+D))
Пример: A+B*(C/B+Z*(A+D))
Pic.43
Псевдокод алгоритма: For (для каждого символа в стрcке ch) { Swith (ch) { case operand: PostfixExp=
Псевдокод алгоритма: For (для каждого символа в стрcке ch) { Swith (ch) { case operand: PostfixExp= PostfixExp+ch; break; case ‘(‘: Push(ch); break; case ‘)’: While( ‘(‘) { PostfixExp= PostfixExp + getTop(); Pop(); };
Pic.44
Псевдокод алгоритма: case operator: While (!IsEmpty() и значение вершины != ‘(‘ и Приоритет ch не пр
Псевдокод алгоритма: case operator: While (!IsEmpty() и значение вершины != ‘(‘ и Приоритет ch не превосходит приоритета вершины) { PostfixExp= PostfixExp+getTop(); Pop(); } // конец While Push(ch); break; }// конец Swith; }// конец For While(! IsEmpty() ) { PostfixExp= PostfixExp + getTop(); Pop(); }; // конец While


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!