c - 基于比较函数插入链表队列

Question

我正在实现 QueueADT 的单链表版本。创建队列后，如果客户端给我们一个比较函数，我们将使用它来将新数据插入队列。如果客户端没有提供比较功能，我们使用标准的队列插入，直接插入到队列的后面。

我在使用比较函数插入的逻辑上遇到了问题。我们只知道比较函数返回什么。

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

我有你的标准队列和链接节点结构:

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

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

这是我对插入功能的尝试。我不认为逻辑是正确的，并且希望对此有一些见解甚至伪代码!

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

测试:

尝试将以下数据插入队列时:

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

似乎插入这些值一直到最后一个，程序卡在

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

Answer 1

首先。如果您的比较需要严格的弱排序(它应该)，则不需要所有添加的比较器调用。这本质上意味着以下内容

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

工作原理

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

指针到指针的遍历乍看起来有点令人生畏，但它有一些奇妙的特性。没有指向节点的枚举器。您实际上是在使用列表中的指针 作为您的枚举变量。不仅仅是它们的“值”，还有实际指针和它们的值。您所做的就是通过更新指针到指针中的地址来更改您正在使用的指针，以反射(reflect)列表中的物理指针(不仅仅是到您正在处理的列表)。当需要更改某些内容时，您不需要指向需要更改的“下一个”指针的节点的指针；您已经有了要修改的指针的地址，因此可以立即修改。

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

最后，我强烈建议使用调试器单步执行此操作。没有什么可以替代“看到”通过代码的实际指针地址和值。一支铅笔和一张带有方框、箭头到方框以及箭头到箭头到方框的纸也有助于理解算法。