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