Очередь, реализация при помощи списков и операции над ними
Download 180.59 Kb.
|
|
МИНИСТЕРСТВО ПО РАЗВИТИЮ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ МУХАММАДА АЛ-ХОРАЗМИЙ САМОСТОЯТЕЛЬНАЯ РАБОТА №1 Тема: Очередь, реализация при помощи списков и операции над ними Выполнил: Мадалиев Тохиржон Проверила: Ташпулатова Надира Батировна Группа: swd-208 ТАШКЕНТ 2023 План
Что такое очередь Как создать очередь Очередь с приоритетом Связный список 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 Метод — это та же самая функция, но она работает только с контейнерами STL. Например, очередь и стек. Для работы с очередью вам понадобится знать функции: push(), pop(), front(), back(), empty(). Кстати, если хотите узнать, как в C++ работают функции и как их правильно использовать в проекте, то можете узнать все это здесь. Для добавления в очередь нового элемента нужно воспользоваться функцией — push(). В круглых скобках должно находится значение, которое мы хотим добавить. Если нам понадобилось удалить первый элемент нужно оперировать функцией pop(). В круглых скобках уже не чего не нужно указывать, но по правилам они в обязательном порядке должны присутствовать! Эти функции тоже не нуждаются в указании аргумента: empty(), back() и front(). Если вам понадобилось обратиться к первому элементу очереди, то вам понадобится функция front(). Чтобы обратиться к последнему элементу в очереди вам поможет функция back(). Чтобы узнать пуста ли очередь нужно воспользоваться функцией empty(). Если ваша очередь пуста — возвратит true. Если же в ней что-то есть — возвратит false. Ниже мы использовали все выше перечисленные методы: 2. Как создать очередь Давайте посмотрим, как будет выглядеть консоль при запуске: Создание очереди с помощью массива Как мы говорили выше, очередь можно реализовать через массив. Обычно, если кто-то создает такую очередь, то массив называют queue. Мы бы также назвали массив, но это уже зарезервированное слова в C++. Поэтому его назовем так, как назвали выше шаблон очереди — q. Для реализации нам понадобится создать две дополнительные переменные start и ends. start будет указывать на первый элемент очереди, a ends на последний элемент. Чтобы обратится к последнему элементу нам придется использовать эту конструкцию — queue[ends]. Обращение к первому элементу будет выглядеть аналогично queue[start]. Если понадобится удалить элемент из очереди, то придется всего лишь уменьшить переменную start на один. «А как же проверить пуста ли очередь?» — спросите вы. Для этого мы просто проверим условие start == ends: Если результатом условия будет true, то очередь пуста. Если же результат условия false, значит очередь чем-то заполнена. Ниже находится живой пример создания такой очереди: 3. Очередь с приоритетом Очередь с приоритетом (priority_queue) — это обычная очередь, но в ней новый элемент добавляется в то место, чтобы очередь была отсортирована по убыванию. Так самый большой элемент в приоритетной очереди будет стоять на первом месте. Для объявления шаблона очереди с приоритетом нужно использовать конструкцию ниже: priority_queue <тип данных> <имя>; В начале нужно написать priority_queue. Потом в скобках указать тип данных, который будет находится в очереди. И конечно же в самом конце мы должны дать ей имя. Для добавления элемента в очередь с приоритетом мы должны использовать функцию push(). Но чтобы обратится к первому элементу должны использоваться именно функция — top() (как и в стеке). А не функция — front(). Также нельзя использовать функцию back() для обращения к последнему элементу. Для приоритетной очереди она также не работает, как функция front(). Вот пример использования очереди с приоритетом в программе: setlocale(LC_ALL,"rus"); priority_queue 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 у нас выступают адреса (на следующий и предыдущий элемент), над которыми выполняется операция XOR, возвращающая реальный адрес следующего элемента. XOR-связный список Еще один вид связного списка – кольцевой список. В кольцевом односвязном списке последний элемент ссылается на первый. В случае двусвязного кольцевого списка – плюс к этому первый ссылается на последний. Таким образом, получается зацикленная структура. Кольцевой список Download 180.59 Kb. Do'stlaringiz bilan baham: 
|