我正在实现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("Fifon");
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 0n");
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 0n");
temp = temp->next;
}
else if (queue->compare(data, temp->value) == 0){
printf("Equals 0n");
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
第一。如果您的比较需要严格的弱排序（它应该如此），则不需要所有添加的比较器调用。这基本上意味着以下内容
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。这（显然）很重要。
最后，我强烈建议使用调试器逐步完成此操作。"看到"在代码中飞行的实际指针地址和值是无可替代的。一支铅笔和一张纸，上面有方框、箭头到方框、箭头到箭头到方框，也大大有助于理解算法。