Как реализовать приоритетную очередь в C-программировании?

Question

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

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

Допустим, у нас следующий сценарий.(Примечание: я предполагаю, что более высокое значение идет с более высоким приоритетом):

Element-->2 (priority=2)  (Now in position 0)

Если необходимо вставить другой элемент, скажем Element-->3 (priority=3), который имеет более высокий приоритет.

Я могу двигатьсяпредыдущий элемент, Element-->2 (priority=2), и вставьте этот новый Element-->3 (priority=3) в позицию 0 с Element-->2 (priority=2), перемещенным в позицию 1.

Теперь список становится,

Element-->3 (priority=3) followed by Element-->2 (priority=2)

Точно так же, на основе вставки, я должен сдвинуть все элементы в списке?

Это правильно?

Answer 1

Вам не нужно «сдвигать» список, вместо этого при вставке вы делаете что-то вроде этого (псевдокод):

if new_node.priority > list.head.priority:
    new_node.next = list.head
    list.head = new_node
else:
    previous = null
    for current = list.head:
        if current.priority < node.priority:
            previous.next = node
            node.next = current
            break loop
        previous = current

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

Answer 2

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

Куча делает все проще - все операции очень дешевы: обновление, удаление и вставка в кучу - все O (log n).

Answer 3

У вас все в порядке с приоритетными очередями. Но ...

Связанный список не является простым массивом.

Каждый элемент в связанном списке имеет ссылку на следующий элемент. Вы можете вставить элемент за другим, просто изменив ссылки на эти два элемента.

+--------+
| item A |                           +--------+
+--------+     +--------+            | item C |
|ref to B|---->| item B |            +--------+
+--------+     +--------+            |  NULL  |
               |  NULL  |            +--------+
               +--------+

Вставка C между A и B выполняется:

1. изменение NULL в C на ref to B
2. изменение ref to B в A на ref to C

Answer 4

Очередь приоритетов - это абстрактный тип данных, который в основном сохраняет элементы в нем в отсортированном порядке (по возрастанию или по убыванию) по некоторому выбранному ключу.Как упомянул Энтони Блейк, реализация кучи - самая прямолинейная, используемая вами базовая структура - это просто массив, и вы выполняете некоторые манипуляции с центром в индексе массива.

Если по какой-то причине вы хотите реализовать с использованиемСписок из односвязных ссылок. Ниже приведен демонстрационный код для выполнения вставки с сортировкой на месте:

void sortedInsert(struct node **headRef,int data){
struct node *newnode=(struct node *)malloc(sizeof(struct node));
assert(newnode);
newnode->value=data;
newnode->next=NULL;

if(!(*headRef) || data<(*headRef)->value){
    newnode->next=*headRef;
    *headRef=newnode;
}else{
    struct node *prev=*headRef;

    while(prev->next && prev->next->value<data)
        prev=prev->next;

    struct node *temp=prev->next;
    prev->next=newnode;
    newnode->next=temp;
}

}

Answer 5

Хорошо, я не знаю, зачем вам это нужно в C. В C ++ STL он доступен.

Но, как вы хотите, здесь есть ссылка на исходный код вашего запроса.

http://matrixsust.blogspot.com/2011/11/basic-priority-queue-in-c.html

ИЛИ

http://www.indiastudychannel.com/projects/4870-Priority-queue-using-array.aspx

Надеюсь, это поможет.