![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Динамические структуры данных – очередь ⇐ ПредыдущаяСтр 5 из 5
Очередью называется динамическая структура данных, добавление компонента в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу: FIFO (First-In, First-Out) – первый вошел, первый вышел. Замечание. В очереди доступны два элемента (две позиции): начало очереди и конец очереди. Поместить компонент можно только в конец очереди, а взять элемент только из ее начала (рис. 4). Примером может служить обыкновенная очередь в магазине.
Обычно над очередью выполняется три операции: - начальное формирование очереди (запись первого компонента); - добавление компонента в очередь; - выборка компонента (удаление) из очереди.
Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель, первая из которых определяет начало очереди (ph), вторая - конец очереди (pk), третья – вспомогательная (px), для добавления нового компонента. Описание компонента очереди и переменных типа указатель имеет следующий вид: struct pointer { int d; pointer *p; }; pointer ph, pk, px;
Рассмотрим основные операции при работе с очередью.
1. Формирование очереди. Начальное формирование очереди выполняется несколькими операторами, позволяющим записать в очередь первый компонент: - выделение в динамической памяти места под первый компонент стека и запись адреса этого компонента в переменную ph: *ph = new pointer;
- запись в поле d некоторых данных – D1:
- запись в поле p нулевого адреса (NULL): ph-> p = NULL;
- установка указателя конца очереди (pk) на первый компонент очереди.
После формирования очереди указатели ph и pk указывают на один и то же компонент.
2. Добавление компонента в очередь. Добавление компонента в очередь осуществляется с конца очереди, при помощи дополнительного указателя – px: - выделение в динамической памяти места под новый компонент стека и запись адреса этого компонента в переменную px: *px = new pointer;
- запись в поле d указателя px некоторых данных – D2: px-> d = D2;
- запись в поле p, указателя px, нулевого адреса: px-> p = NULL;
- запись в поле p указателя pk адреса нового компонента, на который указывает переменная px pk-> p = px;
- запись в указатель pk адреса последнего компонента; pk = px;
Добавление последующих компонентов осуществляется аналогично.
3. Исключение компонентов из очереди. Для исключения компонента из очереди необходимо выполнить ряд операторов. Пусть к моменту выборки компонентов, в очередь записано три компонента. Исключение компонентов из очереди осуществляется из ее вершины.
- первый оператор осуществляет чтение данных из компонента – вершины очереди: data = ph-> d;
- смещение указателя на вершину стека (ph) на следующий компонент: ph =ph-> p;
Повторив, указанные выше, два действия мы получим последовательно доступ ко всем компонентам очереди. На практике эти два действия составляют тело цикла с предусловием (цикл while), в котором сначала проверяют условие (ph! = NULL), а затем, выполняют исключение компонента из стека.
Рассмотрим реализацию этих операций в виде соответствующих функций. Пример. Составить программу, которая формирует очередь, добавляет в него произвольное количество компонентов, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять целые числа. Ввод данных осуществляется до тех пор пока не введено число ноль (0).
#include < conio.h> #include < stdio.h> struct pointer //описание структуры компонента очереди { int d; pointer *p; };
pointer *formoth(int data); //форм. очереди void doboth (pointer **pk, int d); //добавление в очередь int iskoth (pointer **ph); //исключение из очереди
//основная функция void main() { clrscr(); int data; int i=1; //формирование очереди printf(" формирование очереди\n"); printf(" %d компонент -> ", i); scanf(" %d", & data);
pointer *ph = formoth (data); //указатель на начало списка pointer *pk = ph; //указатель конца списка
//добавление в очередь printf(" добавление в очередь\n"); do { i++; printf(" %d компонент -> ", i); scanf(" %d", & data); doboth (& pk, data); //добавление компонента } while (data! =0); //концом ввода является ноль
printf(" вывод очереди на экран: \n"); i=0; while (ph! = NULL) { i++; printf(" %d компонент -> %d\n", i, iskoth (& ph)); } getch(); }
//-------------------------------------- //формирование первого элемента pointer *formoth(int d) { pointer *px = new pointer; px-> d = d; px-> p = NULL; return px; } //добавление элемента void doboth (pointer **pk, int d) { pointer *px = new pointer; px-> d = d; px-> p = NULL; (*pk)-> p = px; (*pk) = px; } //--исключение из списка------------------- int iskoth (pointer **ph) { int d=(*ph)-> d; (*ph)=(*ph)-> p; return d; }
|