Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.59/22: Рейтинг темы: голосов - 22, средняя оценка - 4.59
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
1

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

16.03.2019, 19:31. Просмотров 4159. Ответов 23
Метки нет (Все метки)

Всем привет, есть задание (на картинке)
Из него сделал все, но не пойму что требуется в последнем пункте про очередь с приоритетом. Как вообще это делается, погуглил и ничего не понял.. Прикреплю архив с библиотекой к теме, буду очень благодарен за скорую помощь
0
Вложения
Тип файла: zip Collection.zip (46.5 Кб, 6 просмотров)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.03.2019, 19:31
Ответы с готовыми решениями:

Очередь с приоритетом
Доброй ночи! Как создать очередь с приоритетом? Объясните пожалуйста. И еще один вопросик:...

Очередь с приоритетом сделать многопоточной
Добрый день. Есть реализованная очередь с приоритетом. Реализованы операции вставки, извлечения и...

Сделать очередь с приоритетом, которая бы работала с классом Message<TPriority, TContent>
Добрый день. Пытаюсь вот понять одну штуку. У меня есть некий класс - сообщение: public class...

Очередь с приоритетом. Элементы с наивысшим приоритетом ставятся в начало очереди, с наименьшим – в конец
Здравствуйте! имеется задание: создать очередь с приоритетом (у каждого элемента свой приоритет)....

23
Супер-модератор
Эксперт .NET
12416 / 10243 / 4259
Регистрация: 17.03.2014
Сообщений: 20,510
Записей в блоге: 1
16.03.2019, 20:25 2
MakcPletnev, не ленимся и перепечатываем текст задания на форум (в соответствии с п5.18 правил).
1
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
16.03.2019, 20:59  [ТС] 3
Нужна помощь с пунктом
· PriorityQueue<T>: IQueue<T> where T: IComparable – класс очереди с приоритетами объектов;
и если не сложно, то вкратце как и для чего это нужно

UPD: чуть исправил проект с библиотекой
Цитата Сообщение от Текст задания
Разработать библиотеку обобщенных классов для работы с ассоциативными множествами. В структуру классов входят как минимум:


· IStack<T>: IEnumerable<T> – базовый интерфейс для всех стеков;

методы:
void Push(T value);
void Clear();
T Pop();
T Peek();

свойства:
int Count;
bool isEmpty;

· StackException – класс, описывающий исключения, которые могут происходить в ходе работы cо стеком (также можно написать ряд наследников от StackException);

· ArrayStack<T>: IStack<T> – класс стека на основе массива;
· LinkedStack<T>: IStack<T> – класс стека на основе связанного списка;
-----------
· IQueue<T>: IEnumerable<T> – базовый интерфейс для всех очередей;

методы:
void Enqueue(T value);
void Clear();
T Dequeue();
T Peek();

свойства:
int Count;
bool isEmpty;

· ArrayQueue<T>: IQueue<T> – класс очереди на основе массива;

· LinkedQueue<T>: IQueue<T> – класс очереди на основе связанного списка;

· PriorityQueue<T>: IQueue<T> where T: IComparable – класс очереди с приоритетами объектов;

Также необходимо разработать серию примеров, демострирующих основные аспекты работы с данной библиотекой стеков и очередей.
0
Вложения
Тип файла: zip Collections.zip (33.1 Кб, 8 просмотров)
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
16.03.2019, 21:18  [ТС] 4
Storm23, может вы шарите в этом?)
0
Модератор
7698 / 5413 / 1551
Регистрация: 21.04.2018
Сообщений: 15,954
Записей в блоге: 2
16.03.2019, 21:32 5
Цитата Сообщение от MakcPletnev Посмотреть сообщение
но не пойму что требуется в последнем пункте про очередь с приоритетом. Как вообще это делается
Ну, судя по PriorityQueue<T>: IQueue<T> where T: IComparable
Объекты сортируются сначала по приоритету, потом по очерёдности поступления.

Но мне не понятно базовое наследование IStack<T>: IEnumerable<T> и IQueue<T>: IEnumerable<T>. Одни из основных методов для Стека и Очереди это Метод добавления в них новых элементов и Метод получения очередного элемента с его удалением.
Но IEnumerable не поддерживает изменение последовательности.

Или я чего-то не понимаю.
Или это крайне неудачный выбор для базовых интерфейсов.
1
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
16.03.2019, 22:47  [ТС] 6
Элд Хасп, рад бы и рассказать как и зачем, но я сам не знаю) Такое вот задание.. Я вообще не любитель выполнять бесполезные задачи для универа и самому реализовывать велосипед, когда люди уже давно все сделали.
0
Супер-модератор
Эксперт .NET
12416 / 10243 / 4259
Регистрация: 17.03.2014
Сообщений: 20,510
Записей в блоге: 1
16.03.2019, 23:16 7
Элд Хасп, IEnumerable для очередей вполне подходит. Для возможности перебрать содержимое коллекции без модификации. Стандартные коллекции Queue<T>, Stack<T> их тоже реализуют.
2
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
17.03.2019, 08:01  [ТС] 8
Может кто-то накидать пример? Не очень понимаю как работать вообще с where T: IComparable
0
Модератор
7698 / 5413 / 1551
Регистрация: 21.04.2018
Сообщений: 15,954
Записей в блоге: 2
17.03.2019, 10:28 9
Цитата Сообщение от MakcPletnev Посмотреть сообщение
Может кто-то накидать пример? Не очень понимаю как работать вообще с where T: IComparable
По идее, должно быть что-то подобное.
Если я правильно понял, то раз класс реализовывает два интерфейса, то сначала надо сравнить объекты между собой, а потом в порядке их поступления.
Добавление, объектов происходит в начало последовательности. Вывод из конца последовательности.
Если так, то:
C#
1
2
3
4
this.OrderBy(t => t); // Последовательность элементов
this.Append(t); // Добавление элемента в последовательность.
this.OrderBy(t => t).Last(); // Очередной элемент для вывода.
this.OrderBy(t => t).Take(this.Count()-1); // Последовательность после вывода очередного элемента
Для более более конкретного кода, нужна Ваша реализация основного интерфейса IQueue<T>: IEnumerable<T> – базовый интерфейс для всех очередей;

Добавлено через 28 минут
Для реализации удаления элемента из очереди, наверное, надо предусмотреть в базовом интерфейсе IQueue<T> метод удаления из очереди произвольного элемента Remove(T).

Добавлено через 1 час 16 минут
Ошибочка
C#
1
this.Prepend(t); // Добавление элемента в последовательность.
1
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
17.03.2019, 15:21  [ТС] 10
Элд Хасп, моя реализация в архиве прикреплена под 2 сообщением. Больше ничего не менял
0
Модератор
7698 / 5413 / 1551
Регистрация: 21.04.2018
Сообщений: 15,954
Записей в блоге: 2
17.03.2019, 17:42 11
Цитата Сообщение от MakcPletnev Посмотреть сообщение
моя реализация в архиве прикреплена под 2 сообщением
Блин! Код в теме выставляйте - у Вас же не мега проект!
Я пишу с телефона, чтобы Ваш проект открыть это так поизвращаться пришлось!

Если правильно понял Ваш код, то вот пример реализации.
Могут быть мелкие ошибки - всё таки с телефона пишу.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    public class PriorityQueue<T> : List<T>, IQueue<T> where T : IComparable
    {
        public bool IsEmpty => Count == 0;
 
        public T Dequeue()
        {
            T ret = Peek();
            Remove(ret);
            return ret;
        }
 
        public void Enqueue(T value) => Insert(0, value);
 
        public T Peek() => this.OrderBy(t => t).Last();
 
        // реализация интерфейса IEnumerable
        IEnumerator<T> IEnumerable<T>.GetEnumerator() => this.OrderBy(t => t).GetEnumerator();
 
    }
Добавлено через 12 минут
На счёт 14 строчки не уверен.
Может быть достаточно:
C#
14
       public T Peek() => this.Last();
Запустите и протестируйте.
1
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
17.03.2019, 23:23  [ТС] 12
Элд Хасп, буду знать) Извините) Спасибо, завтра попробую, отпищусь
0
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
18.03.2019, 17:38  [ТС] 13
Элд Хасп, а можно вопрос?) Как это собственно должно работать? Не особо уловил суть "приоритетов"

Добавлено через 1 минуту
Элд Хасп, Peek в случает int сортирует по возрастанию перед возвратом элемента. Странно, что GetEnumerator так не делает.. я вывожу очередь вот так
C#
1
2
3
4
5
foreach (var tmp in PriorityQueue)
                {
                    if ((int)tmp != 0)// если надо убрать нули
                        listBox5.Items.Add(tmp.ToString());
                }
при каждом изменении чищу listBox и вывожу заново, но в нем очередь не сортируется, хотя так же работает OrderBy
0
Модератор
7698 / 5413 / 1551
Регистрация: 21.04.2018
Сообщений: 15,954
Записей в блоге: 2
18.03.2019, 17:44 14
Цитата Сообщение от MakcPletnev Посмотреть сообщение
Как это собственно должно работать? Не особо уловил суть "приоритетов"
Так как по условию задачи IQueue<T> where T: IComparable, то приоритет определяется интерфейсом IComparable. Для числовых типов и string IComparable дефолтный (но можно переопределить), для кастомных типов надо явно реализовывать интерфейс.

По алгоритму, весь список сортируется от меньшего к большему значению - это и есть сортировка в порядке приоритета. Элементы с одинаковым приоритетом будут расположены в порядке их записи в очередь: новые ближе к началу, старые - к концу. Получается, что последний элемент списка (после сортировки по приоритету) имеет самый большой приоритет и он записан раньше всех с этим же приоритетом.
1
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
18.03.2019, 17:46  [ТС] 15
Элд Хасп, да я про это все читал. Просто не понятно, сам список выводится без сортировки, однако Peek отрабатывает верно
0
Модератор
7698 / 5413 / 1551
Регистрация: 21.04.2018
Сообщений: 15,954
Записей в блоге: 2
18.03.2019, 17:54 16
Цитата Сообщение от MakcPletnev Посмотреть сообщение
при каждом изменении чищу listBox и вывожу заново, но в нем очередь не сортируется, хотя так же работает OrderBy
Это потому, что переопределён GetEnumerator - 17 строка.
Сам же List не должен сортироваться, так как фактически индексы элементов в нём используются для определения очерёдности среди элементов с одинаковым приоритетом.

Так как по условию задачи IQueue<T>: IEnumerable<T>, то чтобы получить всю очередь надо использовать приведение
foreach (var tmp in (IEnumerable)PriorityQueue).

Также Вы неверно используете listBox. Вывод в ListBox списка делается так (два варианта):
C#
1
2
listBox5.DataSource = PriorityQueue;
listBox5.DataSource = (IEnumerable)PriorityQueue;
1
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
18.03.2019, 17:56  [ТС] 17
Элд Хасп, спасибо огромное)
0
Модератор
7698 / 5413 / 1551
Регистрация: 21.04.2018
Сообщений: 15,954
Записей в блоге: 2
18.03.2019, 17:59 18
Цитата Сообщение от MakcPletnev Посмотреть сообщение
Просто не понятно, сам список выводится без сортировки, однако Peek отрабатывает верно
PriorityQueue создан как наследник List<T>. У листа есть индексы, которые не трогаются и иду в порядке записи элементов. Элементы записанные раньше имеют более высокий индекс. Самый новый элемент имеет индекс 0.
Так же List<T> имеет интерфейс Ienumerable через который по условию задачи и должны работать методы с очередью. В этом интерфейсе переопределён метод GetEnumerator, поэтому Peek возвращает не последний по индексу элемент, а самый больший из элементов, если их несколько, то с самым большим индексом из них.
1
39 / 35 / 9
Регистрация: 01.02.2014
Сообщений: 813
18.03.2019, 18:01  [ТС] 19
Элд Хасп, странно кстати, но это не работает. Точнее работает, но не обновляется при изменении PriorityQueue. Хотя вроде должно, на сколько я понимаю. Даже если написать это под кнопкой и кликнуть дважды, то новые элементы не появятся (будет только то, что было при первом клике)

C#
1
listBox5.DataSource = PriorityQueue;
0
Alvin Seville
331 / 264 / 131
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 9
18.03.2019, 18:04 20
Цитата Сообщение от MakcPletnev Посмотреть сообщение
PriorityQueue<T>: IQueue<T> where T: IComparable
Объявили тип обобщённой очереди с элементами типа T, где T - это тип, который можно сравнивать (через .CompareTo).
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.03.2019, 18:04

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Очередь с приоритетом
Помогите, пожалуйста, создать из моего класса очередь с приоритетом(приоритетом является money). ...

Очередь с приоритетом
Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по...

Очередь с приоритетом
Может кто нибудь простыми словами объяснить что это за структура данных - очередь с приоритетом? И...

Очередь с приоритетом
Вообщем есть задание найти и описать проблему : Given a priority queue with the following...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.