Comment mettre en œuvre file d'attente de priorité dans la programmation en C?

J'ai besoin d'implémenter une file d'attente de priorité dans la programmation en C à l'aide seule liste liée.

Je n'ai pas une idée claire au sujet de la priorité de la file d'attente. J'ai cherché sur google mais n'ai pas bien compris ce que j'ai trouvé. Ma compréhension est que l'une des priorités de la file d'attente est une file d'attente dont les éléments sont classés par ordre de priorité. Les Insertions dans la liste sont positionnés dans la liste sur la base de l'élément priorités.

Permet de dire,nous avons scénario suivant. (Note : je suppose, valeur la plus élevée va de pair avec de plus forte priorité):

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

Si un autre élément doit être inséré, dire Element-->3 (priority=3) qui a une priorité plus élevée.

Je peux déplacer l'élément précédent, Element-->2 (priority=2), et insérer ce nouveau Element-->3 (priority=3) à la position 0 avec Element-->2 (priority=2) déplacé à la position 1 dans la liste.

Maintenant, la liste devient,

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

De même, sur la base de l'insertion, dois-je décaler tous les éléments dans la liste?

Est-ce correct?

So far So good -- avez-vous obtenu coincé avec votre mise en œuvre?
il suffit de parler,lorsqu'il a à opérer sur la liste, il prend l'élément avec la plus haute priorité à opérer sur...comment vous faites cela dépend si vous placez la priorité la plus élevée de l'élément à la liste avant ou vous placer dans le tas avant(si vous utilisez un segment de mémoire)...

OriginalL'auteur Dinesh | 2011-11-24

  1. 4

    Vous n'avez pas à "maj" de la liste, au lieu de cela lors de l'insertion de vous faire quelque chose comme ceci (pseudo-code):

    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

    Si votre liste est un pointeur vers la fin, vous pouvez ajouter un contrôle particulier pour une priorité plus basse qu'à la fin aussi.

    OriginalL'auteur Some programmer dude

  2. 4

    Je pense que vous êtes d'avoir des ennuis à cause d'une file d'attente de priorité devrait être mise en œuvre avec un tas arbre, pas une seule liste liée.

    Le tas, tout devient facile: toutes les opérations sont très bon marché: la mise à jour, la suppression et l'insertion dans le tas sont tous O(log n).

    OriginalL'auteur Anthony Blake

  3. 2

    Vous êtes OK avec les files d'attente de priorité. Mais...

    Une liste chaînée n'est pas un simple tableau.

    Chaque élément dans une liste chaînée est une référence à l'élément suivant. Vous pouvez insérer un élément l'un après l'autre en changeant juste les références de ces deux éléments.

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

    L'insertion de C entre A et B est réalisée par:

    1. changer NULL en C par ref to B
    2. changer ref to B dans Un ref to C

    OriginalL'auteur mouviciel

  4. 0

    Une file d'attente de priorité est un Type Abstrait de Données qui maintient essentiellement des éléments dans l'ordre de tri (croissant ou décroissant) sur certaines choisi clé. Comme mentionné par Anthony Blake, le segment de la mise en œuvre est la plus simple, la structure sous-jacente que vous utilisez est tout simplement un tableau et d'effectuer quelques manipulations centrée sur l'index du tableau.

    Si, pour une raison quelconque vous souhaitez mettre en œuvre à l'aide d'une seule liste liée, ci-dessous un code de démonstration pour effectuer triés insertion dans un endroit de la mode:

    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;
}

    }

    OriginalL'auteur Moses Xu

  5. 0

    Ok, je ne sais pas pourquoi vous en avez besoin en C. En C++, STL, il est disponible.

    Mais que vous le souhaitez voici le lien vers le code source de votre ask.

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

    OU

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

    Espère que cela aide.

    OriginalL'auteur Robel Sharma