- •21. Основные понятия структурного программирования. Идентификаторы. Переменные и константы. Тип данных. Выражения. Инструкция присваивания. Теорема о структурировании. Базовые управляющие структуры.
- •Константы
- •Переменные
- •1. Добавление звена в начало списка
- •2. Удаление звена из начала списка
- •Операция над строками Создание строк
- •Преобразования строк
- •Очередь fifo
- •27. Сортировка. Спецификация задачи сортировки. Простые алгоритмы сортировки массивов: пузырьковая сортировка, сортировки простым обменом, вставкой и слиянием.
- •Псевдокод
- •Анализ алгоритма
- •Псевдокод
- •Работа с типизированными файлами
- •Работа с нетипизированными файлами
- •29. Указатели и динамическое распределение памяти. Понятие указателя. Виды указателей. Динамическое и статическое распределение памяти. Разадресация и разыменование. Проблемы использования указателей.
- •31. Свойства классов. Доступ к членам класса. Статические члены классов. Массивы объектов классов. Указатель объекта класса на себя. Дружественные функции. Перегрузка операторов.
- •33. Обобщенное программирование. Шаблоны функций и классов. Параметры шаблона. Специализация шаблона. Создание объектов на основе шаблона класса. Примеры.
- •Параметры шаблонов
- •Специализация и создание объектов
- •Примеры
Очередь fifo
Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO.
Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение.
[Статическая реализация очереди на основе массива]
При представлении очереди вектором в статической памяти в дополнение к обычным для дескриптора вектора параметрам в нем должны находиться два указателя: на начало очереди (на первый элемент в очереди) и на ее конец (первый свободный элемент в очереди). При включении элемента в очередь элемент записывается по адресу, определяемому указателем на конец, после чего этот указатель увеличивается на единицу. При исключении элемента из очереди выбирается элемент, адресуемый указателем на начало, после чего этот указатель уменьшается на единицу.
Очевидно, что со временем указатель на конец при очередном включении элемента достигнет верхней границы той области памяти, которая выделена для очереди. Однако, если операции включения чередовались с операциями исключения элементов, то в начальной части отведенной под очередь памяти имеется свободное место. Для того, чтобы места, занимаемые исключенными элементами, могли быть повторно использованы, очередь замыкается в кольцо: указатели (на начало и на конец), достигнув конца выделенной области памяти, переключаются на ее начало. Такая организация очереди в памяти называется кольцевой очередью. Возможны, конечно, и другие варианты организации: например, всякий раз, когда указатель конца достигнет верхней границы памяти, сдвигать все непустые элементы очереди к началу области памяти, но как этот, так и другие варианты требуют перемещения в памяти элементов очереди и менее эффективны, чем кольцевая очередь.
В исходном состоянии указатели на начало и на конец указывают на начало области памяти. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди. Если в процессе работы с кольцевой очередью число операций включения превышает число операций исключения, то может возникнуть ситуация, в которой указатель конца "догонит" указатель начала. Это ситуация заполненной очереди, но если в этой ситуации указатели сравняются, эта ситуация будет неотличима от ситуации пустой очереди. Для различения этих двух ситуаций к кольцевой очереди предъявляется требование, чтобы между указателем конца и указателем начала оставался "зазор" из свободных элементов. Когда этот "зазор" сокращается до одного элемента, очередь считается заполненной и дальнейшие попытки записи в нее блокируются. Очистка очереди сводится к записи одного и того же (не обязательно начального) значения в оба указателя. Определение размера состоит в вычислении разности указателей с учетом кольцевой природы очереди.
Пример класса простейшей очереди:
class Queue : public Data // Класс очереди.
{
const size_t m_Size; // Размер очереди в блоках (константа).
TPObject m_pBegin; // Начало очереди.
TPObject m_pEnd; // Конец очереди.
public:
Queue(const size_t = 1); // Конструктор (единый).
~Queue() { delete[] m_pBegin; }
void Push(const TObject); // Добавление объекта в очередь.
TObject Pop(); // Получение объекта из очереди.
};
Queue::Queue(const size_t Size)
: m_Size(Size)
{
if (!m_Size)
{
cout << "Ошибка! Неверный размер очереди." << endl;
exit(-4);
}
if (!(m_pBegin = m_pEnd = new TObject[m_Size]))
{
cout << "Ошибка! Недостаточно памяти." << endl;
exit(-1);
}
}
void Queue::Push(const TObject Ob) // Помещение в очередь.
{
// Проверка наличия свободных блоков в очереди.
if (m_pEnd < m_pBegin + m_Size)
*(m_pEnd++) = Ob; // Запись объекта.
else
{
cout << "Ошибка! Очередь заполнена." << endl;
exit(-2);
}
}
TObject Queue::Pop() // Взятие из очереди.
{
// Проверка наличия объектов в очереди.
if (m_pEnd > m_pBegin)
{
TObject Temp(*m_pBegin); // Чтение объекта.
for (TPObject p = m_pBegin; p < m_pEnd; ++p) *p = *(p+1);
--m_pEnd;
return Temp;
}
else
{
cout << "Ошибка! Очередь пуста." << endl;
exit(-3);
}
}
В главной функции иллюстрируется работа со стеком и с очередью:
void main()
{
cout << "Создание структур данных ..." << endl;
Data *arpSD[3];
arpSD[0] = new Stack(4);
arpSD[1] = new Queue(6);
arpSD[2] = new Stack(3);
// Запись символов в структуры данных.
arpSD[0] -> Push('a'); arpSD[0] -> Push('b');
arpSD[1] -> Push('c'); arpSD[1] -> Push('d'); arpSD[1] -> Push('e');
arpSD[2] -> Push('f'); arpSD[2] -> Push('g'); arpSD[2] -> Push('h');
// Чтение символов из структур данных и удаление структур из памяти.
size_t i;
cout << "Чтение из них данных ..." << endl;
for (i = 0; i < 3; ++i)
{
cout << "Из " << i << "-й структуры взят символ: ";
cout << arpSD[i] -> Pop() << '.' << endl;
delete arpSD[i];
}
}