150

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

ID: 60587
Дата закачки: 03 Января 2012
Продавец: evgeniidavydov (Напишите, если есть вопросы)
    Посмотреть другие работы этого продавца

Тип работы: Работа Лабораторная
Форматы файлов: Исполняемые фалы (EXE), Microsoft Word, VisualC++
Сдано в учебном заведении: СибГУТИ

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

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

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


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

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

Размер файла: 50 Кбайт
Фаил: (.rar)
-------------------
Обратите внимание, что преподаватели часто переставляют варианты и меняют исходные данные!
Если вы хотите, чтобы работа точно соответствовала, смотрите исходные данные. Если их нет, обратитесь к продавцу или к нам в тех. поддержку.
Имейте ввиду, что согласно гарантии возврата средств, мы не возвращаем деньги если вариант окажется не тот.
-------------------

Скачать

Добавить в корзину

Занесено в корзину

    Скачано: 2         Коментариев: 0

Есть вопросы? Посмотри часто задаваемые вопросы и ответы на них.
Опять не то? Мы можем помочь сделать!

Некоторые похожие работы:

К сожалению, точных предложений нет. Рекомендуем воспользоваться поиском по базе.