Работа с динамической очередью. Dünaamiline järjekord. - презентация

1 Работа с динамической очередью. Dünaamiline järjekord.

2 Объявление очереди. Järjekorra deklareerimine. struct Solm //järjekorra üks sõlm { info; //andmed Solm *next; //järgmise elementi aadress }; Solm *Esim, *Viim; //esimese ja viimase //elemendi viidad

3 Очередь (FIFO first_in_first_out) – это линейная структура, в которой разрешается добавлять элементы в начало и удалять с конца. Järjekord (FIFO first_in_first_out) on lineaarne seotud nimistu, mille jaoks võib lisada element rea lõppu ning kustutada rea algusest й элемент esimene Последний viimane

4 Создание пустой очереди. Tühja järjekorra koostamine. Esim=Viim=NULL; EsimViim

5 Добавление первого элемента. Esimese elemendi lisamine. p=new Solm; p->info=andmed; p->next=NULL; Esim=Viim=p; P andmed NULL Esim Viim

6 Добавление очередного элемента в очередь. Järgmise elemendi lisamine. Viim->next=p; Viim=p; p=new Solm; p->info=andmed; p->next=NULL; P andmed NULL EsimViim

7 Удаление элемента из очереди. Elemendi kustutamine järjekorrast. p=Esim; NULL EsimViim Esim=p->next; delete p; p

8 Описание программы, реализующей работу с очередью. Programmi kirjeldamine. Функции (funktsioonid): -Проверка пустоты очереди (kas järjekord on tühi) -Добавление элемента (lisamine) -Удаление элемента (eemaldamine) -Удаление всех элементов из очереди (kõikide elementide eemaldamine) -Поиск элемента в очереди (elemendi otsimine) -Показать на экране значение элемента в начале очереди (esimese elemendi väljastamine ekraanile) -Показать на экране значения всех элементов в очереди (kõikide elementide väljastamine ekraanile) ülesanne

9 Проверка пустоты очереди Kas järjekord on tühi Функция должна возвращать true, если очередь пустая, и false, если очередь имеет хотя бы один элемент. Kui järjekord on tühi, funktsioon tagastab true. Kui järjekorras on elemendid, funktsioon tagastab false.

10 Добавление элемента. Lisamine. void QInsert( ); Функция добавляет новый в конец очереди. Funktsioon kirjutab oma parameetri järjekorra lõppu.

11 Удаление элемента. Eemaldamine. QDelete(); Функция удаляет элемент из очереди и возвращает значение этого элемента главной функции main(). Funktsioon eemaldab elemendi järjekorrast ja tagastab elemendi väärtust peafunktsioonile main().

12 Удаление всех элементов из очереди. Kõikide elementide eemaldamine. void ClearQueue(); В цикле пока очередь не опустеет удаляются все её элементы и указатели на начало и конец получают значение NULL. Tsüklis eemaldatakse kõik elemendid kuni järjekorras on elemendid. Kui järjekorras ei ole elemendi Esim = Viim = NULL.

13 Поиск элемента в очереди. Elemendi otsimine. int QFind( ); В цикле просматривается вся очередь на совпадение элементов с искомым значением. Если элемент найден, функция возвращает порядковый номер элемента. Если элемент не найден, функция возвращает 0 (нуль). Tsüklis vaadatakse järjekord ja otsitakse element. Kui element on järjekorras, funktsioon tagastab elemendi number. Kui element puudub, funktsioon tagastab 0 (nulli).

14 Показать на экране значение элемента в начале очереди. Esimese elemendi väljastamine ekraanile. QFront (); Функция возвращает значение первого элемента в очереди. Funktsioon tagastab esimese elemendi väärtust.

15 Показать на экране значения всех элементов в очереди. Kõikide elementide väljastamine ekraanile. void QPrint(); Функция выводит на экран все элементы очереди. Funktsioon väljastab järjekorra elementid.

16 Очереди приоритетов. Prioriteedi järjekorrad. Очереди приоритетов находят применение в операционной системе, которая записывает процессы в список, а затем выполняет их в порядке приоритетов. Järjekord kasutatakse operatsiooni süsteemis. OS kirjutab protsessid nimistusse ja väljakutsub neid järjekorra prioriteedi korras. Очередь – это структура данных, которая обеспечивает FIFO-порядок элементов. Järjekord on andmete struktuur, mis annab FIFO elemendite kord. Очередь удаляет самый старый элемент из списка. Järjekord kustutab kõige vanema elementi. Приложения часто требуют модифицированной версии памяти для очереди, в которой из списка удаляется элемент с высшим приоритетом. Programmid tihti nõuavad, et järjekorrast kustutakse kõrgema kvaliteetiga element.

17 Очереди приоритетов (продолжение). Prioriteedi järjekorrad. Задача 1 20 Задача 2 0 Задача 3 40 Задача 4 30 Задача 5 10 Порядок хранения задач. Ülesannete säilitamise kord. Порядок выполнения задач. Ülesannete väljakutsumise kord. Задача 2Задача 5Задача 1Задача 4Задача 3 В очереди могут находиться задачи с одним и тем же уровнем приоритета. В этом случае они должны вставать в очередь. Обслуживание таких задач должно выполняться в порядке их поступления. Kui järjekorras on ülesanned ühesugusega prioriteetidega, nad peavad järjekorras olema.

18 Заданиe. Ülesanne. 1. Составить программу, реализующую работу с очередью (см. Слайд 8) Koostada programmi, mis realiseerib töö järjekorraga (vaata Slaid 8)