Формирование очереди
Первоначальное формирование очереди осуществляется в два этапа.
Формирование очереди
Первоначальное формирование очереди осуществляется в два этапа.
Этап 1. Первоначальное формирование очереди
Этот этап заключается в создании первого элемента, для которого адресная часть должна быть нулевой (NULL). Для этого нужно:
1) ввести информацию для первого элемента (для простоты - это какое-то целое положительное число – значение переменной i);
2) захватить, используя рабочий указатель память под первый элемент:
t = new Spis;
сформирован конкретный адрес (А1) для первого элемента;
3) в информационную часть заносим введенную с клавиатуры информацию:
t -> info = i; ( обозначим ее как i1 )
4) в адресную часть заносим NULL:
t -> Next = NULL;
5) указателям на начало и на конец очереди присваиваем значение t:
begin = end = t;
Этап 2. Формирование элементов очереди, начиная с первого
Рассмотрим только для второго элемента, а ниже обобщим для произвольного числа элементов.
1. Начало бесконечного цикла while (1), окончанием которого будет отрицательное число.
2. Ввод информации для текущего элемента - значение i .
3. Если значение не подходит, т.е. i<0 - завершение цикла (break).
4. Иначе захватываем память под текущий элемент:
t = new Spis;
5. Формируем информационную часть (для второго элемента введенное значение обозначим i2):
t -> info=i;
6. В адресную часть созданного элемента (текущего) - NULL, т.к. этот элемент теперь последний:
t -> Next = NULL;
7. Элемент добавляется в конец очереди, поэтому в адресную часть последнего элемента end ->Next вместо NULL заносим адрес созданного:
end -> Next = t;
бывший последний элемент теперь стал предпоследним.
8. Переставляем указатель последнего элемента на добавленный:
end = t;
9. Конец цикла
Алгоритм добавления нового элемента
1. Захватываем память под новый элемент структуры.
2. Устанавливаем на него через указатель конца очереди указатель теперь уже предпоследнего элемента:
end -> Next = t;
3. Считываем данные и заносим в информационную часть.
4. Записываем в адресную часть NULL.
5. Устанавливаем на новый элемент указатель конца очереди.
Алгоритм удаления первого элемента из очереди
Имеем непустую очередь (можно организовать проверку указателей на NULL).
1. Устанавливаем текущий указатель на начало очереди: t = begin;
2. Обрабатываем информационную часть первого элемента очереди, например, печатаем.
3. Указатель на начало очереди переставляем на следующий (2-ой) элемент
begin = begin->Next;
4. Освобождаем память, захваченную под 1-ый элемент: delete t;
5. Выводим сообщение, например, «Элемент удален!».
Алгоритм просмотра очереди
1. Устанавливаем текущий указатель на начало очереди: t = begin;
2. Начало цикла, выполняющегося пока t != NULL (работает, пока не дойдем до конца очереди).
3. Информационную часть текущего элемента t->info выводим на печать.
4. Переставляем текущий указатель на следующий элемент очереди:
t = t -> Next;
5. Конец цикла.
Алгоритм установки указателя на нужный элемент очереди
1. Ввести номер нужного элемента k.
2. Устанавливаем текущий указатель на начало очереди: t = begin;
3. Начало цикла: перебор элементов от i=1 до i<k с шагом 1.
4. Переставляем текущий указатель на следующий элемент очереди:
t = t -> Next;
5. Конец цикла.
В итоге t будет указывать на начало k-го элемента очереди.
Варианты заданий
1. Создать очередь из случайных целых чисел. Найти минимальный элемент и сделать его первым.
2. Создать две очереди из случайных целых чисел. В первой найти максимальный элемент и за ним вставить элементы второй очереди.
3. Создать очередь из случайных целых чисел. Удалить из списка все элементы, находящиеся между максимальным и минимальным.
4. Упорядочить элементы очереди случайных целых чисел в порядке возрастания методом “пузырька”, когда можно переставлять местами только два соседних элемента (см. л.р.7).
5. Создать очередь из случайных целых чисел. Удалить из списка все элементы, находящиеся до максимального элемента и минимальным.
6. Создать очередь из случайных целых чисел. Удалить из списка все элементы, находящиеся до минимального элента.
7. Создать очередь из случайных целых чисел. Из элементов, расположенных между максимальным и минимальным создать первое кольцо. Остальные элементы должны составить второе кольцо.
8. Создать очередь из случайных целых, положительных и отрицательных чисел. Из этого списка образовать два списка, первый из которого должен содержать отрицательные числа, а второй – положительные. Элементы списков не должны перемещаться в памяти.
9. Создать очередь из случайных целых чисел. Удалить из списка все элементы, находящиеся после максимального элемента.
10. Создать два списка из случайных целых чисел. Вместо элементов первого списка, заключенных между максимальным и минимальным, вставить второй список.
11. Создать очередь из случайных целых чисел. Удалить из списка элементы с повторяющимися более одного раза значениями.
12. Создать очередь и поменять в нем элементы с максимальным и минимальным значениями, при этом элементы не должны перемещаться в памяти.
13. Создать очередь из случайных целых чисел. Удалить из списка все элементы, находящиеся после минимальнного.
14. Создать очередь из случайных чисел. Преобразовать его в кольцо. Предусмотреть возможность движения по кольцу в обе стороны с отображением места положения текущего элемента.
15. Создать очередь из случайных целых чисел. Удалить из списка все элементы, находящиеся между максимальным и минимальным.
Контрольные вопросы
1. Что представляет из себя динамическая структура данных «очередь»?
2. Как сформировать очередь из к элементов?
3. Как просмотреть непустую очередь?
4. Как добавить элемент в очередь?
5. Как удалить элемент из очереди?