1

I am implementing a single linked list version of a QueueADT. Upon Queue creation, if the client gives us a compare function, we are to use that on inserting new data into the queue. If the client does not provide a compare function, we use standard queue insertion and just insert to the back of the queue.

I am having trouble with the logic of using the compare function to insert. We only know what the compare function returns.

compare( void*a, void*b)
//compare returns < 0 if a < b
//compare returns = 0 if a == b
//compare returns > 0 if a > b

I have your standard queue and linked node structures:

typedef struct queueStruct {
    Node *front;
    Node *rear;
    int count;
    int (*compare)(const void*, const void*);
};

typedef struct Node {
    void* value;
    struct Node *next;
}Node;

And here is my attempt at the insert function. I don't think the logic is correct, and would appreciate some insight or maybe even pseudocode for this!

void que_insert(queueStruct queue, void *data){
    //if the queue is empty
    if (que_empty(queue)){
        Node *node;
        node = malloc(sizeof(Node));
        node -> value = data;
        node -> next = NULL;
        queue->front  = node;
        queue->rear = node;
        queue->count++;
     }
     else{
        //if there is no comparison function, just use FIFO
        if (queue->compare == NULL){
            printf("Fifo\n");
            Node *node;
            node = malloc(sizeof(Node));
            node->value = data;
            node->next = NULL;
            queue->rear->next = node;
            queue->rear = node;
            queue->count++;

         }
         else{
            Node *temp;
            temp = queue->front;
            //if what we are adding is smaller than the head, then we found our new head
            if (queue->compare(data, temp->value) < 0){
                printf("Less Than 0\n");
                Node *node;
                node = malloc(sizeof(Node));
                node->value = data;
                node->next = queue->front;
                queue->front = node;
                queue->count++;
                return;
             }
             while (temp->next != NULL){
                if (queue->compare(data, temp->value)> 0){
                    printf("Greater than 0\n");
                    temp = temp->next;
                }
                else if (queue->compare(data, temp->value) ==  0){
                    printf("Equals 0\n");
                    Node *node;
                    node = malloc(sizeof(Node));
                    node->value = data;
                    node->next = temp->next;
                    temp->next = node;
                    queue->count++;
                    return;
                 }
             }
             //temp should be at the rear
             if (queue->compare(data, temp->value)> 0){
                printf("Adding to rear");
                Node *node;
                node = malloc(sizeof(Node));
                node->value = data;
                node->next = NULL;
              }
          }
     }
}

Testing:

Upon trying to insert the following data's into the queue:

42, 17, -12, 9982, 476, 2912, -22, 3291213, 7782

It seems that inserting these values works up until the last one, the program hangs at

inserting 7782
Greater than 0
Greater than 0
Greater than 0
Greater than 0
4

1 回答 1

2

第一的。如果您的比较需要严格的弱排序（它应该这样做），则不需要所有添加的比较器调用。这基本上意味着以下

if (compare(a,b) < 0) 
    then a is less than b
else if !(compare(b,a) < 0) 
    then a and b are equal
else b is less than a

这在标准库中很常用，因为一方面，它使得比较枚举必须更容易理解。它也只需要定义一个逻辑操作。“较少的”

正如我在一般评论中所说，合并新节点的分配位置。看来您的队列支持重复（它应该），因此无论您总是添加一个新节点，所以只需从一开始就创建它，然后专注于寻找它的去向。

最后，指向节点的指针将使您的插入更加简洁（事实上，我打赌您会发现它非常短）：

void que_insert(queueStruct* queue, void *data)
{
    // going to need this sooner or later
    Node *node = malloc(sizeof(*node));
    node->value = data;
    node->next = NULL;

    //if the queue is empty
    if (queue->count == 0)
    {
        queue->front = queue->rear = node;
        queue->count = 1;
    }

    // else not empty, but no comparator
    else if (queue->compare == NULL)
    {
        //if there is no comparison function, just use FIFO
        queue->rear->next = node;
        queue->rear = node;
        queue->count++;
    }

    // else not empty and we have a comparator
    else
    {   // walk over chain of node pointers until we  find a pointer 
        //  that references a node equal or greater than ours, or EOQ
        Node **pp = &queue->front;
        while (*pp && queue->compare((*pp)->value, data) < 0)
            pp = &(*pp)->next;

        // no more nodes means new rear. otherwise link mid-stream
        if (!*pp)
            queue->rear = node;
        else
            node->next = *pp;

        // either way, this is always done.
        *pp = node;
        queue->count++;
    }
}

这个怎么运作

我们使用指向节点的指针来保存我们正在检查的每个指针的地址，从头指针开始。这有几个优点。我们不需要跟踪指向节点的指针就可以访问它的“下一个”，因为我们已经通过地址获得了它。我们得到自动前端插入，因为我们从头指针地址开始，唯一必须考虑的是后端更新，仍然必须手动完成，但这很简单。

指针对指针的遍历可能看起来有点令人生畏，但它有一些奇妙的特性。没有指向节点的枚举器。您实际上使用列表中的指针作为枚举变量。不仅是它们的“值”，还有实际的指针和它们的值。您所做的只是更改您正在使用的指针，方法是更新指针指针中的地址，以反映您正在处理的列表（不仅仅是列表）中的哪个物理指针。当需要更改某些内容时，您不需要指向需要更改的“下一个”指针的节点的指针；你已经有了要修改的指针的地址，

我没有测试附加的代码，但它应该可以工作。只需确保您的初始queueStruct设置为零计数，前后指针均为 NULL。这（显然）很重要。

最后，我强烈建议使用调试器逐步完成此操作。没有什么可以替代“看到”在代码中飞来飞去的实际指针地址和值。一支铅笔和一张纸，上面有盒子，箭头到盒子，箭头到箭头到盒子也有助于理解算法。

于 2013-11-06T16:35:39.737 回答