Презентация на тему: Лекция 13. C++. Стек. Очередь

Лекция 13. C++. Стек. Очередь.
План.
Лекция 13. C++. Стек. Очередь.
Стек.
Лекция 13. C++. Стек. Очередь.
Основные операции над стеком
Функция добавления звена в стек
Лекция 13. C++. Стек. Очередь.
Функция удаления звена из стека
Лекция 13. C++. Стек. Очередь.
Очередь
Лекция 13. C++. Стек. Очередь.
Основные операции над очередью
Функция добавления звена в очередь
Лекция 13. C++. Стек. Очередь.
Функция удаления звена из очереди
Лекция 13. C++. Стек. Очередь.
Пример 1.
Лекция 13. C++. Стек. Очередь.
Лекция 13. C++. Стек. Очередь.
Лекция 13. C++. Стек. Очередь.
Итоги
1/22
Средняя оценка: 4.4/5 (всего оценок: 58)
Код скопирован в буфер обмена
Скачать (91 Кб)
1

Первый слайд презентации: Лекция 13. C++. Стек. Очередь

Визуальное программирование. Ст. преп. М.А. Сокольская

Изображение слайда
2

Слайд 2: План

2 2 План. Стек. Определение Операции обработки стека. Примеры Очередь. Определение Операции обработки очереди. Примеры

Изображение слайда
3

Слайд 3

3 Для моделирования реальных процессов часто используются линейные списки, в которых включение, исключение и просмотр элементов всегда начинается с первого или последнего звеньев. Такие списки имеют специальные названия и свои особенности обработки.

Изображение слайда
4

Слайд 4: Стек

4 Стек. Определение 1. Стек – однонаправленный список, в котором все включения и удаления выполняются с конца списка. В стеке с помощью некоторой ссылки доступно единственное звено, называемое вершиной стека. Стек организован по принципу LIFO (last in – first out)

Изображение слайда
5

Слайд 5

5 head элемент n элемент n -1 … элемент 1 NULL head элемент n -1 … элемент 1 NULL Удаление элемента head элемент n +1 элемент n … элемент 1 NULL Вставка элемента

Изображение слайда
6

Слайд 6: Основные операции над стеком

6 Основные операции над стеком Формирование стека Включение звена в стек Обработка элементов стека Удаление звена В начале работы стек пуст, т.е. значением указателя стека является ссылка NULL.

Изображение слайда
7

Слайд 7: Функция добавления звена в стек

7 Функция добавления звена в стек Функция должна иметь два параметра: имя стека и имя элемента, добавляемого в стек. Функция создает новое звено и делает его вершиной стека. Опишем звено стека. struct stek { int data; struct stek *next; } ;

Изображение слайда
8

Слайд 8

8 stek *vstek (stek *ns, int x) { stek *tmp1; // вспомогательный указатель tmp1 = new struct stek; /* выделяем память под новый элемент стека* / tmp1 -> data = x; // задаем значение tmp1 -> next = ns; /* добавляем новый элемент в вершину стека */ ns = tmp1; return ns; // возвращаем новое значение вершины }

Изображение слайда
9

Слайд 9: Функция удаления звена из стека

9 Функция удаления звена из стека Функция должна проверить наличие элементов в стеке, и если стек пуст сообщить об этом. Если стек не пуст удаляем его вершину. Описание звена стека остается тем же, что и для функции добавления звена.

Изображение слайда
10

Слайд 10

10 stek * izsteka (stek *ns) { struct stek *tmp1; tmp1 = ns; if (ns == NULL) // при нулевом указателе вершины cout << “ Стек пуст! ”; else { cout << “ Удаляем элемент ” << tmp -> data; ns = tmp1 -> next; // вершина - следующий элемент delete tmp1; // освобождаем память } return ns; }

Изображение слайда
11

Слайд 11: Очередь

11 Очередь Определение 2 Очередь – однонаправленный список, в котором все удаления производятся в начале списка, а все добавления – в конце списка. Очередь организована по принципу ( FIFO – first in – first out ) Для организации очереди требуется два указателя – на конец и на начало списка.

Изображение слайда
12

Слайд 12

12 head элемент 1 элемент 2 … элемент n NULL head элемент 2 … элемент n NULL Удаление элемента head элемент 1 элемент 2 … элемент n Вставка элемента ends элемент n+1 NULL ends ends

Изображение слайда
13

Слайд 13: Основные операции над очередью

13 Основные операции над очередью Начальная установка очереди Включение звена в очередь Удаление звена из очереди В начале работы очередь пуста, т.е. значениями указателей на начало и конец очереди является ссылка NULL.

Изображение слайда
14

Слайд 14: Функция добавления звена в очередь

14 Функция добавления звена в очередь Функция должна иметь три параметра: указатель на начало, указатель на конец и данные, добавляемые в очередь. Функция создает новое звено и добавляет его к очереди. Если очередь пуста, то первый элемент является и последним Опишем звено очереди. struct och { int data; struct och *next; } ; struct och *head=NULL, *ends=NULL, *tmp=NULL;

Изображение слайда
15

Слайд 15

15 void vochered (och **no, och **ko, int x) { struct och *tmp1; tmp1 = new struct och; tmp1 -> data = x; tmp1 -> next = NULL; if ((*no)==NULL) { (*no) = tmp1; (*ko) = tmp1; } else { (*ko) -> next = tmp1; (*ko) = tmp1; } }

Изображение слайда
16

Слайд 16: Функция удаления звена из очереди

16 Функция удаления звена из очереди Функция должна проверить наличие элементов в очереди, и если очередь пуста сообщить об этом. Если очередь не пуста удаляем звено из начала очереди. Описание звена очереди остается тем же, что и для функции добавления звена.

Изображение слайда
17

Слайд 17

17 void izochered (och **no) { och *tmp1; if (*no == NULL) cout << “ Очередь пуста ” else { tmp1 = (*no); *no = (*no) -> next; delete tmp1; } }

Изображение слайда
18

Слайд 18: Пример 1

18 Пример 1. Условие задачи. Текстовый файл состоит из русских букв и оканчивается точкой. Составить программу, которая сначала напечатает все согласные буквы в порядке их следования, затем все гласные в том же порядке. Используем очередь для временного хранения гласных. Согласные буквы печатаем сразу по мере чтения файла. А затем печатаем гласные буквы из очереди.

Изображение слайда
19

Слайд 19

19 struct node { char num; struct node *next; }; struct node *head=NULL, *ends=NULL; void voch (node **no, node** ko, char k); // описание функций void izoch (node **no); void main () { int i, t=0; char c; char f[10] = {‘ а ’,’ е ’,’ о ’,’ и ’,’ у ’,’ ы ’,’ э ’,’ ю ’,’ я ’}; FILE *f1;

Изображение слайда
20

Слайд 20

20 clrscr(); f1 = fopen(“t.dat”, “r”); // открываем файл для чтения while (!feof(f1)) { fscanf(f1, “%c”, &c); / *считываем очередной символ в переменную с* / for (j=0; j<strlen(f); j++) // перебор символов строки f if (c == f[j]) t++; // если символ в строке есть if (t == 0) cout << c << “ “; // вывод символа else voch (&head, &ends, c) // вводим символ в очередь }

Изображение слайда
21

Слайд 21

21 while (head != NULL) // пока очередь не пуста { cout << head -> num; / *вывод элемента на экран* / izoch (&head); /* удаление звена из очереди */ } getch(); }

Изображение слайда
22

Последний слайд презентации: Лекция 13. C++. Стек. Очередь: Итоги

22 22 Итоги Мы рассмотрели : Понятие стека и функции работы с ним Понятие очереди и функции работы с очередью

Изображение слайда