Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
40 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
332.00 kB
Просмотров:
72
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Структура данных ОЧЕРЕДЬ](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img0.jpg)
Содержание слайда: Структура данных ОЧЕРЕДЬ
Структура данных ОЧЕРЕДЬ
Очередь – линейный список, в котором извле-чение данных происходит из начала, а доба-вление – в конец списка.
Очередь организована по принципу FIFO (First In, First Out) – первым вошел, первым выйдет.
Работа с очередью реализуется при помощи динамических структур, для которых необхо-димо выделение и освобождение памяти.
№2 слайд![Простой пример очередь в](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img1.jpg)
Содержание слайда: Простой пример – очередь в кассу, если очереди нет, обслуживаешься сразу, иначе, становишься в ее конец.
Простой пример – очередь в кассу, если очереди нет, обслуживаешься сразу, иначе, становишься в ее конец.
Последовательно обслуживаются стоящие в на-чале очереди.
В течение дня очередь то увеличивается, то уменьшается и может отсутствовать.
Очереди организуются в виде односвязных или двухсвязных списков, в зависимости от коли-чества связей (указателей) в адресной части элемента структуры.
№3 слайд![Односвязный список очередь](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img2.jpg)
Содержание слайда: Односвязный список (очередь)
Односвязный список (очередь)
Шаблон структуры, информационная часть (ИЧ) которого – целое число:
struct Spis1 { // Или TList1
int info;
Spis1 *next;
};
При организации очереди обычно используют два указателя
Spis1 *begin, *end;
begin и end – указатели на начало и конец.
№4 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img3.jpg)
№5 слайд![Основные операции с очередью](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img4.jpg)
Содержание слайда: Основные операции с очередью:
Основные операции с очередью:
– формирование очереди;
– добавление нового элемента в конец очереди;
– удаление элемента из начала очереди;
– обработка элементов (просмотр, поиск и др.);
– освобождение памяти, занятой очередью.
№6 слайд![Формирование очереди состоит](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img5.jpg)
Содержание слайда: Формирование очереди состоит из двух этапов: создание первого элемента, добавление нового элемента в конец.
Формирование очереди состоит из двух этапов: создание первого элемента, добавление нового элемента в конец.
Создание первого элемента
1. Ввод информации для первого элемента (например, целое число i );
2. Захват памяти, используя текущий указатель:
t = new Spis1;
формируется конкретный адрес (А1) для первого элемента;
№7 слайд![. Формирование информационной](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img6.jpg)
Содержание слайда: 3. Формирование информационной части:
3. Формирование информационной части:
t -> info = i; (обозначим i1 )
4. В адресную часть записываем NULL:
t -> next = NULL;
5. Указатели начала и конца очереди устанавли-ваем на созданный элемент t :
begin = end = t;
На этом этапе получим следующее:
№8 слайд![Добавление элемента в очередь](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img7.jpg)
Содержание слайда: Добавление элемента в очередь
Добавление элемента в очередь
Рассмотрим добавление только для второго элемента.
1. Ввод информации для текущего (второго) элемента – значение i .
2. Захват памяти под текущий элемент:
t = new Spis1; (адрес A2)
3. Формирование информационной части (i2):
t -> info = i;
4. В адресную часть заносим NULL, т.к. этот элемент становится последним:
t -> next = NULL;
№9 слайд![. Элемент добавляется в](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img8.jpg)
Содержание слайда: 5. Элемент добавляется в конец, поэтому в адресную часть бывшего последнего элемента end заносим адрес созданного:
5. Элемент добавляется в конец, поэтому в адресную часть бывшего последнего элемента end заносим адрес созданного:
end -> next = t;
бывший последний элемент становится пред-последним.
6. Переставляем указатель end последнего элемента на добавленный:
end = t;
Обратите внимание, что пункты 1 – 4 обоих этапов идентичны.
№10 слайд![В результате получим В](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img9.jpg)
Содержание слайда: В результате получим
В результате получим
№11 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img10.jpg)
№12 слайд![Иначе добавляем элемент в](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img11.jpg)
Содержание слайда: // Иначе добавляем элемент в конец
// Иначе добавляем элемент в конец
else { (*e) -> next = t;
*e = t;
}
}
В функцию передаются адреса указателей, чтобы при изменении обеспечить их возврат в точку вызова.
Обращение к данной функции
Create (&begin, &end, in);
№13 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img12.jpg)
№14 слайд![В функцию передаются В](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img13.jpg)
Содержание слайда: В функцию передаются:
В функцию передаются:
адрес указателя на начало списка, чтобы при его изменении обеспечить возврат в точку вызова;
значение указателя на конец списка, измененное значение которого возвращается в точку вызо-ва оператором return e ;
значение ранее введенной ИЧ in.
Обращение к функции в этом случае :
end = Create (&begin, end, in);
№15 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img14.jpg)
№16 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img15.jpg)
№17 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img16.jpg)
№18 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img17.jpg)
№19 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img18.jpg)
№20 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img19.jpg)
№21 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img20.jpg)
№22 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img21.jpg)
№23 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img22.jpg)
№24 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img23.jpg)
№25 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img24.jpg)
№26 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img25.jpg)
№27 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img26.jpg)
№28 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img27.jpg)
№29 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img28.jpg)
№30 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img29.jpg)
№31 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img30.jpg)
№32 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img31.jpg)
№33 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img32.jpg)
№34 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img33.jpg)
№35 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img34.jpg)
№36 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img35.jpg)
№37 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img36.jpg)
№38 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img37.jpg)
№39 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img38.jpg)
№40 слайд![](/documents_6/f13ad8b1ad5a4e24c26c1b791bc7b6d6/img39.jpg)