Как реализовать очередь приоритетов с использованием отсортированного связанного списка?

#c# #data-structures #queue #linked-list

#c# #структуры данных #очередь #связанный список

Вопрос:

я хочу реализовать это на c #, у меня есть готовый класс связанного списка, но проблема возникает, когда я сортирую класс, используя этот метод сортировки. Как я могу присвоить приоритет элементам, чтобы элемент с наивысшим приоритетом удалялся из очереди первым.

         public void Sort()
   {
       ListNode current=first;
       int temp;

       for (int i = 0; i < counter; i  )
       {
           while (current.Next != null)
           {

               if (current.Data > current.Next.Data)
               {
                   temp = current.Data;
                   current.Data = current.Next.Data;
                   current.Next.Data = current.Data;
               }
               current = current.Next;
           }
       }
   }

1. Вы сказали, что возникает проблема; вы собираетесь рассказать нам, в чем проблема? Связанный список не является подходящей структурой данных для очереди приоритетов в первую очередь. Используйте кучу.

2. проблема в том, что этот метод сортировки работает плохо, вторые последние и последние элементы в списке не сортировались.

3. Хорошо, можете ли вы привести нам пример списка, который не сортируется правильно? Кроме того, каково значение «счетчика»?

4. 6,5,4,3,2,1 после сортировки 1,2,3,4,5,5 amp; счетчик = 6

5. Хорошо, итак, пройдитесь по коду в отладчике и следите за каждым шагом. В списке будет 6, пока в какой-то момент не останется 6 и не будет двух 5. Вероятно, в этом и заключается ошибка.

Ответ №1:

Чтобы немного проанализировать ваш код:

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

Это только гарантирует, что наибольшее значение станет последним элементом. И только после того, как вы исправите часть подкачки:

 if (current.Data > current.Next.Data)
{
  temp = current.Data;
  current.Data = current.Next.Data;
  current.Next.Data = temp;
}

Ответ №2:

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

Rgds GJ

1. В подпрограмме, которая вставляет новый элемент, вы говорите while (current.next != null amp;amp; new . данные> текущие.данные) текущий = текущий.следующий. Итак, вы переходите по списку к нужной точке, после чего вставляете новый элемент между current и current.next . таким образом, ваш список всегда будет отсортирован.