Очередь, реализация при помощи списков и операции над ними

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ПО РАЗВИТИЮ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ МУХАММАДА АЛ-ХОРАЗМИЙ

САМОСТОЯТЕЛЬНАЯ РАБОТА №1

Тема: Очередь, реализация при помощи списков и операции над ними

Выполнил: Ахмаджанов Шахзод

Проверила: Надира Батировна

Группа: 420-19

Вариант: №4

ТАШКЕНТ 2020



План

1. Что такое очередь

2. Как создать очередь

3. Очередь с приоритетом

4. Связный список



1. Что такое очередь

Очередь -- это структура данных (список), которая построена по принципу LILO (last in -- last out: последним пришел -- последним вышел). В C++ уже есть готовый STL контейнер -- queue.

В очереди, если вы добавите элемент, который вошел самый первый, то он выйдет тоже самым первым. Получается, если вы добавите 4 элемента, то первый добавленный элемент выйдет первым. Чтобы понять принцип работы очереди вы можете представить себе магазинную очередь. И вы стоите посреди нее, чтобы вы оказались напротив кассы, сначала понадобится всех впереди стоящих людей обслужить. А вот для последнего человека в очереди нужно, чтобы кассир обслужил всех людей кроме него самого.

На рисунке сверху находятся 7 чисел: 2, 4, 7, 1, 4, 9, 10. Если нам понадобится их извлечь, то извлекать мы будем в таком же порядке как они находятся на рисунке! Так например чтобы извлечь число 4 нам понадобится сначала обслужить число 2, а потом уже и само число 4. Хотя в стеке присутствует функция peek() (она позволяет обратится к элементу по индексу, подробнее вот здесь), в шаблоне очереди невозможно обратится к определенному элементу. Но если вам нужно иметь доступ ко всем элементам очереди, то можете реализовать очередь через массив. Чуть ниже мы покажем как это сделать. Как создать очередь в С++? Если вы хотите использовать шаблон очереди в C++, то вам сначала нужно подключить библиотеку -- <queue>. Дальше для объявления очереди нужно воспользоваться конструкцией ниже.

queue <тип данных> <имя>;

· Сначала нам нужно написать слова queue.

· Дальше в <тип данных> мы должны указать тот тип, которым будем заполнять нашу очередь.

· И в конце нам остается только указать название очереди.

Вот пример правильного объявления:

queue <int> q;

Метод -- это та же самая функция, но она работает только с контейнерами STL. Например, очередь и стек. Для работы с очередью вам понадобится знать функции: push(), pop(), front(), back(), empty(). Кстати, если хотите узнать, как в C++ работают функции и как их правильно использовать в проекте, то можете узнать все это здесь.

1. Для добавления в очередь нового элемента нужно воспользоваться функцией -- push(). В круглых скобках должно находится значение, которое мы хотим добавить.

2. Если нам понадобилось удалить первый элемент нужно оперировать функцией pop(). В круглых скобках уже не чего не нужно указывать, но по правилам они в обязательном порядке должны присутствовать! Эти функции тоже не нуждаются в указании аргумента: empty(), back() и front().

3. Если вам понадобилось обратиться к первому элементу очереди, то вам понадобится функция front().

4. Чтобы обратиться к последнему элементу в очереди вам поможет функция back().

5. Чтобы узнать пуста ли очередь нужно воспользоваться функцией empty().

o Если ваша очередь пуста -- возвратит true.

o Если же в ней что-то есть -- возвратит false.

Ниже мы использовали все выше перечисленные методы:

2. Как создать очередь

Давайте посмотрим, как будет выглядеть консоль при запуске:

Создание очереди с помощью массива

Как мы говорили выше, очередь можно реализовать через массив. Обычно, если кто-то создает такую очередь, то массив называют queue. Мы бы также назвали массив, но это уже зарезервированное слова в C++. Поэтому его назовем так, как назвали выше шаблон очереди -- q. Для реализации нам понадобится создать две дополнительные переменные start и ends. start будет указывать на первый элемент очереди, a ends на последний элемент. Чтобы обратится к последнему элементу нам придется использовать эту конструкцию -- queue[ends]. Обращение к первому элементу будет выглядеть аналогично queue[start]. Если понадобится удалить элемент из очереди, то придется всего лишь уменьшить переменную start на один. «А как же проверить пуста ли очередь?» -- спросите вы. Для этого мы просто проверим условие start == ends:

1. Если результатом условия будет true, то очередь пуста.

2. Если же результат условия false, значит очередь чем-то заполнена.

Ниже находится живой пример создания такой очереди:



3. Очередь с приоритетом

Очередь с приоритетом (priority_queue) -- это обычная очередь, но в ней новый элемент добавляется в то место, чтобы очередь была отсортирована по убыванию.

Так самый большой элемент в приоритетной очереди будет стоять на первом месте. Для объявления шаблона очереди с приоритетом нужно использовать конструкцию ниже:

priority_queue <тип данных> <имя>;

· В начале нужно написать priority_queue.

· Потом в скобках указать тип данных, который будет находится в очереди.

· И конечно же в самом конце мы должны дать ей имя.

Для добавления элемента в очередь с приоритетом мы должны использовать функцию push(). Но чтобы обратится к первому элементу должны использоваться именно функция -- top() (как и в стеке). А не функция -- front().

Также нельзя использовать функцию back() для обращения к последнему элементу. Для приоритетной очереди она также не работает, как функция front().

Вот пример использования очереди с приоритетом в программе:

setlocale(LC_ALL,"rus");

priority_queue <int> priority_q; // объявляем приоритетную очередь

cout << "Введите 7 чисел: " << endl;

for (int j = 0; j < 7; j++) { int a; cin >> a;

priority_q.push(a); // добавляем элементы в очередь

}

// выводим первый

cout << "Первый элемент очереди: " << priority_q.top(); // элемент

Структура данных, представляющая собой конечное множество упорядоченных элементов (узлов), связанных друг с другом посредством указателей, называется связным списком. Каждый элемент связного списка содержит поле с данными, а также указатель (ссылку) на следующий и/или предыдущий элемент. Эта структура позволяет эффективно выполнять операции добавления и удаления элементов для любой позиции в последовательности. Причем это не потребует реорганизации структуры, которая бы потребовалась в массиве. Минусом связного списка, как и других структур типа «список», в сравнении его с массивом, является отсутствие возможности работать с данными в режиме произвольного доступа, т. е. список - структура последовательно доступа, в то время как массив - произвольного. Последний недостаток снижает эффективность ряда операций. По типу связности выделяют односвязные, двусвязные, XOR-связные, кольцевые и некоторые другие списки. Каждый узел односвязного (однонаправленного связного) списка содержит указатель на следующий узел. Из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Так получается своеобразный поток, текущий в одном направлении.

4. Связный список

Односвязный список

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

Двусвязный список

список очередь массив программа

Возможность двигаться как вперед, так и назад полезна для выполнения некоторых операций, но дополнительные указатели требуют задействования большего количества памяти, чем таковой необходимо в односвязном списке. Когда количество памяти, по каким-либо причинам, ограничено, тогда альтернативой двусвязному списку может послужить XOR-связный список. Последний использует логическую операцию XOR (исключающее «ИЛИ», строгая дизъюнкция), которая для двух переменных возвращает истину лишь при условии, что истинно только одно из них, а второе, соответственно, ложно. Таблица истинности операции:

a	b	a ? b
0	0	0
0	1	1
1	0	1
1	1	0

В качестве переменных a и b у нас выступают адреса (на следующий и предыдущий элемент), над которыми выполняется операция XOR, возвращающая реальный адрес следующего элемента.

XOR-связный список

Еще один вид связного списка - кольцевой список. В кольцевом односвязном списке последний элемент ссылается на первый. В случае двусвязного кольцевого списка - плюс к этому первый ссылается на последний. Таким образом, получается зацикленная структура.

Кольцевой список

Программная реализация списка.

На примере двусвязного списка, разберем принцип работы этой структуры данных. При реализации списка удобно использовать структуры (в Pascal - записи).

Общая форма описания узла двунаправленного связного списка и указателя на первый элемент списка:

struct имя_списка

{

информационное_поле_1;

информационное_поле_2;

…

информационное_поле_n;

указатель_на_следующий_элемент;

указатель_на_предыдущий_элемент;

};

имя_списка *указатель_на_голову_списка;

Пример:

struct DoubleList //описание узла списка

{

int data; //информационное поле

DoubleList *next; //указатель на следующий элемент

DoubleList *prev; //указатель на предыдущий элемент

};

DoubleList *head; //указатель на первый элемент списка

Теперь, предполагая, что описан узел и указатель на голову списка (см. пример выше), напишем функции обработки связного списка.

Добавление элемента.

Опишем функцию AddList, которая в качестве параметров принимает значение и адрес будущего узла, после чего создает его в списке:

void AddList(int value, int position)

{

DoubleList *node=new DoubleList; //создание нового элемента

node->data=value; //присвоение элементу значения

if (head==NULL) //если список пуст

{

node->next=node; //установка указателя next

node->prev=node; //установка указателя prev

head=node; //определяется голова списка

}

else

{

DoubleList *p=head;

for(int i=position; i>1; i--) p=p->next;

p->prev->next=node;

node->prev=p->prev;

node->next=p; //добавление элемента

p->prev=node;

}

cout<<"\nЭлемент добавлен...\n\n";

}

Удаление элемента.

Функция DeleteList для удаления элемента использует его адрес:

int DeleteList(int position)

{

if (head==NULL) { cout<<"\nСписок пуст\n\n"; return 0; }

if (head==head->next) //если это последний элемент в списке

{

delete head; //удаление элемента

head=NULL;

}

else

{

DoubleList *a=head;

for (int i=position; i>1; i--) a=a->next;

if (a==head) head=a->next;

a->prev->next=a->next; //удаление элемента

a->next->prev=a->prev;

delete a;

}

cout<<"\nЭлемент удален...\n\n";

}

Если список пуст, то выводится сообщение, извещающее об этом, и функция возвращается в место вызова.

Вывод списка.

Функция PrintList выводит на экран все элементы списка:

void PrintList()

{

if (head==NULL) cout<<"Список пуст\n";

else

{

DoubleList *a=head;

cout<<"\nЭлементы списка: ";

do

{

cout<<a->data<<" ";

a=a->next;

} while(a!=head); cout<<"\n\n";

}

}

Вывести список можно и посредством цикла, то есть итеративно.

Теперь соединим эти три функции в одной программе. Если в качестве языка использовался бы Pascal, то для функционирования программы (в нашем случае интерфейса двусвязного списка) пришлось, помимо функций (процедур), написать основной блок программы (begin…end), из которого вызывались бы подпрограммы. В C++ этим блоком является функция main. Программа, реализующая простой интерфейс двусвязного списка:

#include "stdafx.h"

#include <iostream>

using namespace std;

struct DoubleList //описание узла списка

{

int data; //информационное поле

DoubleList *next; //указатель на следующий элемент

DoubleList *prev; //указатель на предыдущий элемент

};

DoubleList *head; //указатель на первый элемент списка

//**********************ДОБАВЛЕНИЕ ЭЛЕМЕНТА**********************

void AddList(int value, int position)

{

DoubleList *node=new DoubleList; //создание нового элемента

node->data=value; //присвоение элементу значения

if (head==NULL) //если список пуст

{

node->next=node; //установка указателя next

node->prev=node; //установка указателя prev

head=node; //определяется голова списка

}

else

{

DoubleList *p=head;

for(int i=position; i>1; i--) p=p->next;

p->prev->next=node;

node->prev=p->prev;

node->next=p;

p->prev=node;

}

cout<<"\nЭлемент добавлен...\n\n";

}

//***********************УДАЛЕНИЕ ЭЛЕМЕНТА***********************

int DeleteList(int position)

{

if (head==NULL) { cout<<"\nСписок пуст\n\n"; return 0; }

if (head==head->next)

{

delete head;

head=NULL;

}

else

{

DoubleList *a=head;

for (int i=position; i>1; i--) a=a->next;

if (a==head) head=a->next;

a->prev->next=a->next;

a->next->prev=a->prev;

delete a;

}

cout<<"\nЭлемент удален...\n\n";

}

//*************************ВЫВОД СПИСКА*************************

void PrintList()

{

if (head==NULL) cout<<"\nСписок пуст\n\n";

else

{

DoubleList *a=head;

cout<<"\nЭлементы списка: ";

do

{

cout<<a->data<<" ";

a=a->next;

} while(a!=head); cout<<"\n\n";

}

}

//************************ГЛАВНАЯ ФУНКЦИЯ************************

void main()

{

setlocale(LC_ALL, "Rus");

int value, position, x;

do

{

cout<<"1. Добавить элемент"<<endl;

cout<<"2. Удалить элемент"<<endl;

cout<<"3. Вывести список"<<endl;

cout<<"0. Выйти"<<endl;

cout<<"\nНомер операции > "; cin>>x;

switch (x)

{

case 1:

cout<<"Значение > "; cin>>value;

cout<<"Позиция > "; cin>>position;

AddList(value, position); break;

case 2:

cout<<"Позиция > "; cin>>position;

DeleteList(position); break;

case 3: PrintList(); break;

}

} while (x!=0);

}

От программы требуется, чтобы она выполнялась до тех пор, пока не выполнен выход из цикла do функции main (для выхода из него пользователь должен ввести 0). По этой причине в конце функции main не был описан оператор, тормозящий программу.

Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно.

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

Размещено на Allbest.ru