以正确的顺序添加元素到Priority Que（ADT） [英] Adding elements in correct order to Priority Que (ADT)

问题描述

我将优先级QUE作为双向链表实现。我的结构：

I am implementing Priority QUE as a doubly linked list. My structs:

typedef int kintyr;

typedef struct qElem {
    struct qElem *prv;          
    kintyr *dat;                    
    int *priority;
}qElem;


typedef struct que {
    qElem *fr,*bk;              
    int cnt;                    
}que;

这是我创建空PQ和插入元素的功能：

And this is my functions to create empty PQ, and to insert elements:

que *qNew()
{
    que *q = malloc(sizeof(*q));

if (q==NULL)
    return NULL;

q->fr = NULL;
q->bk = NULL;
q->cnt = 0;


qFault = 0;
return q;
}

que *qEnq(que *q, kintyr *x, int *prrt)
{
    que *zn=q;
    qFault = 0;
    if (q == NULL)
    {
        qFault = 1;
        return q;
    }
    if (qCHKf(q) == 1)
    {
        qFault = 3;
        return q;
    }
    qElem *new = malloc(sizeof(*new));
    new->prv = NULL;
    new->dat = x;
    new->priority=prrt;

    if (q->fr == NULL || q->fr->priority>prrt  ) 
    {
        new->prv=q->fr;
        q->fr = new;

    }
    else
    {
        que *tempas=q;
        while(tempas->fr->prv!=NULL && tempas->fr->priority<=prrt)
            tempas=tempas->fr;

        new->prv=tempas->fr;
        tempas->fr=new;
    } 
        q->cnt++;
        return q;

}

如果我添加优先级为7，然后是4，然后是5的元素，则效果很好。



4-> 5-> 7

但是如果我添加优先级为7的元素，那么6然后是8.看来：



6-> 8-> 7

您有什么想法我该如何解决？

It works good if I add for example elements with priority 7, then 4, then 5.

4->5->7
But if I add element with priority 7, then 6, then 8. It appears:

6->8->7
Do you have any ideas how can I fix that?

推荐答案

您已将优先级成员定义为指向int的指针。你可能想把它定义为一个int。出于这个原因，比较

You have defined the priority member as a pointer to int. You probably meant to define it just as an int. For that reason the comparison in

if (q->fr == NULL || q->fr->priority>prrt  )

失败。您正在比较指针（地址）而不是值。要么优先使用int，要么在比较时取消引用指针：

fails. You are comparing the pointers (addresses) instead of the values. Either make priority an int, or dereference the pointer when comparing:

if (q->fr == NULL || *q->fr->priority > *prrt )

同样适用于while语句中的比较。



除此之外你的实现还有其他一些缺点：



- 你永远不会更新你的bk指针双向链表

- 您应该为队列对象本身和队列节点使用不同的结构。否则，每个队列节点都包含一个剩余计数器。

- 如果您希望稍后将代码升级到C ++，请不要将new关键字用于变量名。

The same applied to the comparison in the while statement.

Besides that your implementation has several other weaknesses:

- You never update the bk pointer of your doubly linked list
- You should use different structures for the queue object itself and the queue nodes. Otherwise, every queue node contains a surplus counter.
- If you want to have a later chance of upgrading your code to C++, don't use the new keyword for variable names.

这篇关于以正确的顺序添加元素到Priority Que（ADT）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！