включение, исключение и просмотр элементов всегда начинается с первого или
последнего звеньев.Такие списки имеют специальные названия и свои особенности обработки.
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Лекция 13. C++. Стек. Очередь
Содержание
- 1. Лекция 13. C++. Стек. Очередь
- 2. План.Стек.ОпределениеОперации обработки стека.ПримерыОчередь.ОпределениеОперации обработки очереди.Примеры
- 3. Для моделирования реальных процессов часто используются линейные
- 4. Стек.Определение 1.Стек – однонаправленный список, в котором
- 5. headэлемент nэлемент n-1…элемент 1NULLheadэлемент n-1…элемент 1NULLУдаление элементаheadэлемент n+1элемент n…элемент 1NULLВставка элемента
- 6. Основные операции над стекомФормирование стекаВключение звена в
- 7. Функция добавления звена в стекФункция должна иметь
- 8. stek *vstek (stek *ns, int x){ stek *tmp1;
- 9. Функция удаления звена из стека Функция должна
- 10. stek *izsteka (stek *ns){ struct stek *tmp1; tmp1 = ns; if (ns == NULL) //при нулевом указателе вершины cout
- 11. ОчередьОпределение 2Очередь – однонаправленный список, в котором
- 12. headэлемент 1элемент 2…элемент nNULLheadэлемент 2…элемент nNULLУдаление элементаheadэлемент 1элемент 2…элемент nВставка элементаendsэлемент n+1NULLendsends
- 13. Основные операции над очередьюНачальная установка очередиВключение звена
- 14. Функция добавления звена в очередьФункция должна иметь
- 15. void vochered (och **no, och **ko, int
- 16. Функция удаления звена из очередиФункция должна проверить
- 17. void izochered (och **no){ och *tmp1; if (*no == NULL) cout next; delete tmp1; }}
- 18. Пример 1. Условие задачи.Текстовый файл состоит из
- 19. struct node { char num; struct node *next;};struct node
- 20. clrscr(); f1 = fopen(“t.dat”, “r”); //открываем файл для
- 21. while (head != NULL) //пока очередь не
- 22. ИтогиМы рассмотрели:Понятие стека и функции работы с нимПонятие очереди и функции работы с очередью
- 23. Скачать презентанцию
План.Стек.ОпределениеОперации обработки стека.ПримерыОчередь.ОпределениеОперации обработки очереди.Примеры
Слайды и текст этой презентации
Слайд 2План.
Стек.
Определение
Операции обработки стека.
Примеры
Очередь.
Определение
Операции обработки очереди.
Примеры
Слайд 3Для моделирования реальных процессов часто используются линейные списки, в которых
Такие списки имеют специальные названия и свои особенности обработки.
Слайд 4Стек.
Определение 1.
Стек – однонаправленный список, в котором все включения и
удаления выполняются с конца списка.
В стеке с помощью некоторой ссылки
доступно единственное звено, называемое вершиной стека.Стек организован по принципу LIFO (last in – first out)
Слайд 5head
элемент n
элемент n-1
…
элемент 1
NULL
head
элемент n-1
…
элемент 1
NULL
Удаление элемента
head
элемент n+1
элемент n
…
элемент 1
NULL
Вставка
элемента
Слайд 6Основные операции над стеком
Формирование стека
Включение звена в стек
Обработка элементов стека
Удаление
звена
В начале работы стек пуст, т.е. значением указателя стека является
ссылка NULL.
Слайд 7Функция добавления звена в стек
Функция должна иметь два параметра: имя
стека и имя элемента, добавляемого в стек. Функция создает новое
звено и делает его вершиной стека.Опишем звено стека.
struct stek {
int data;
struct stek *next;
};
Слайд 8stek *vstek (stek *ns, int x)
{
stek *tmp1; // вспомогательный указатель
tmp1
= new struct stek; /*выделяем память под новый элемент стека*/
tmp1
-> data = x; // задаем значениеtmp1 -> next = ns; /*добавляем новый элемент в вершину стека*/
ns = tmp1;
return ns; //возвращаем новое значение вершины
}
Слайд 9Функция удаления звена из стека
Функция должна проверить наличие элементов
в стеке, и если стек пуст сообщить об этом. Если
стек не пуст удаляем его вершину.Описание звена стека остается тем же, что и для функции добавления звена.
Слайд 10stek *izsteka (stek *ns)
{
struct stek *tmp1;
tmp1 = ns;
if (ns ==
NULL) //при нулевом указателе вершины
cout
элемент” << tmp -> data;ns = tmp1 -> next; //вершина - следующий элемент
delete tmp1; // освобождаем память
}
return ns;
}
Слайд 11Очередь
Определение 2
Очередь – однонаправленный список, в котором все удаления производятся
в начале списка, а все добавления – в конце списка.
Очередь
организована по принципу (FIFO – first in – first out)Для организации очереди требуется два указателя – на конец и на начало списка.
Слайд 12head
элемент 1
элемент 2
…
элемент n
NULL
head
элемент 2
…
элемент n
NULL
Удаление элемента
head
элемент 1
элемент 2
…
элемент n
Вставка
элемента
ends
элемент n+1
NULL
ends
ends
Слайд 13Основные операции над очередью
Начальная установка очереди
Включение звена в очередь
Удаление звена
из очереди
В начале работы очередь пуста, т.е. значениями указателей на
начало и конец очереди является ссылка NULL.
Слайд 14Функция добавления звена в очередь
Функция должна иметь три параметра: указатель
на начало, указатель на конец и данные, добавляемые в очередь.
Функция создает новое звено и добавляет его к очереди. Если очередь пуста, то первый элемент является и последнимОпишем звено очереди.
struct och {
int data;
struct och *next;
};
struct och *head=NULL, *ends=NULL, *tmp=NULL;
Слайд 15void 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Функция удаления звена из очереди
Функция должна проверить наличие элементов в
очереди, и если очередь пуста сообщить об этом. Если очередь
не пуста удаляем звено из начала очереди.Описание звена очереди остается тем же, что и для функции добавления звена.
Слайд 17void izochered (och **no)
{
och *tmp1;
if (*no == NULL)
cout
пуста”
else
{
tmp1 = (*no);
*no = (*no) -> next;
delete tmp1;
}
}
Слайд 18Пример 1.
Условие задачи.
Текстовый файл состоит из русских букв и
оканчивается точкой. Составить программу, которая сначала напечатает все согласные буквы
в порядке их следования, затем все гласные в том же порядке.Используем очередь для временного хранения гласных. Согласные буквы печатаем сразу по мере чтения файла. А затем печатаем гласные буквы из очереди.
Слайд 19struct 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 clrscr();
f1 = fopen(“t.dat”, “r”); //открываем файл для чтения
while (!feof(f1))
{
fscanf(f1, “%c”,
&c); /*считываем очередной символ в переменную с*/
for (j=0; j
//перебор символов строки fif (c == f[j]) t++; //если символ в строке есть
if (t == 0)
cout << c << “ “; //вывод символа
else
voch (&head, &ends, c) //вводим символ в очередь
}
Слайд 21 while (head != NULL) //пока очередь не пуста
{
cout
-> num; /*вывод элемента на экран*/
izoch (&head); /* удаление звена
из очереди*/}
getch();
}
Слайд 22Итоги
Мы рассмотрели:
Понятие стека и функции работы с ним
Понятие очереди и
функции работы с очередью
