Отчет по лабораторной работе №2 Полустатические структуры данных. Очереди. По дисциплине: Структуры и алгоритмы обработки данных Вариант: 02

Задание к лабораторной работе
Записать последовательность цифр в очередь в порядке возрастания. Ввести еще одно число и поместить его в очередь, не нарушая принципа упорядоченности элементов.

Схема решения.
Очередь реализуем двумя способами.
1. Очередь на базе массива.
Элементы очереди будем хранить в кольцевом массиве. Индекс первого и последнего элемента – как отдельные переменные head и tail. При этом head будет указывать на индекс первого элемента очереди, а tail – на индекс свободного места для вставки нового элемента. При извлечении элемента head увеличивается на единицу, при добавлении элемента новый элемент добавляется на место с индексом tail, а tail увеличивается на единицу. Увеличения на единицу производятся с учётом того, что массив кольцевой.
2. Очередь на базе линейного односвязного списка.
Будем хранить два указателя – на первый и последний элемент очереди. Указатели идут в порядке от первого к последнему элементу. При извлечении элемента мы можем легко получить следующий по указателю, при вставке мы ставим указатель с последнего элемента на новый и в качестве указателя на последний элемент храним указатель на новый только что добавленный элемент.

Задачу будем решать таким способом.
Нужно разделить список на две части (одна из них может быть пустой) и между ними вставить новый элемент. Учитывая, что список чисел у нас храниться в очереди, то будем делать так:
- если можно вставить новый элемент сразу в конец, то вставляем его и задача решена.
- если в конец вставить нельзя, то извлекаем элемент из очереди и заново его в очередь вставляем до тех пор, пока в конец нельзя будет вставить новый элемент. Как только можно вставить новый элемент, то вставляем его и извлекаем из очереди оставшийся кусок (поэлементно, конечно), который нарушает упорядоченность и вставляем его в очередь заново. Таким образом мы как бы произвели циклический сдвиг элементов очереди и за одно вставили новый элемент на нужное место.
При этом для решения задачи потребуются ещё две функции, возвращающие первый и последний элемент очереди, не извлекая их.

В архиве 3 файла: *.CPP ; *.EXE ; Отчет.
Уважаемый слушатель, дистанционного обучения,
Оценена Ваша работа по предмету: Структуры и алгоритмы обработки данных на ЭВМ*
Вид работы: Лабораторная работа 2
Оценка:Зачет
Дата оценки: 19.09.2011
Рецензия:Уважаемый ...................................,

Лебеденко Людмила Федоровна