1

我想使用链表创建一个队列。有很多算法可以做到这一点。但我很好奇的是如何制作相对优先级队列。

也许这种类型的队列有一个特殊的名称，但我不知道，而且我没有任何运气在谷歌上搜索解决方案。

无论如何，假设我有这个结构，它将代表我列表的节点。

struct Node {
    int value;
    Node* next;
}

如果我想创建一个优先级队列（其中值最小的元素是第一个），当我插入例如 5 7 1 8 2 时，我的列表应该如下所示：

1 -> 2 -> 5 -> 7 -> 8

实现这一点并不难。我想要做的是 - 当我插入第一个元素时，其他元素应该具有相对于前一个元素的值。因此，在我的示例中，列表/队列将包含以下值：

1 -> 1 -> 3 -> 2 -> 1

我不确定我将如何实现它？以下想法是否适用：

在节点结构中，我添加了另一个字段，它代表原始值。我找到了我要插入的节点的位置，就像我在创建普通链表时所做的那样，然后我只是说

temp->value = temp->originalValue - previous->originalValue;
4

2 回答 2

1

您需要在每个节点中存储额外的数据，或者是相对优先级，或者是“前一个”指针。由于每当删除节点时都需要更新下一个节点的相对优先级（如果没有 prev 指针如何做到这一点？），我建议使用“previous”指针：

struct Node {
    int value;
    Node* next;
    Node* prev;
}

然后一个函数可以评估相对优先级：

int relative_priority(Node* node) {
    if (node == NULL)
        return 0;
    if (node->prev == NULL)
        return node->value;
    return node->value - node->prev->value;
}

请注意，我使用的是 C，对于 C++，您需要将 NULL 替换为 0

于 2013-08-13T23:21:02.457 回答
0

您首先必须确定插入新节点的位置。这涉及减少目标值，调整其相对于列表中当前值的相对值。在插入点，你必须将前一个节点指向新节点，然后用新的相对值调整新节点前面的节点。

Node * create_node (int value, Node *next) { /* ... */ }

void insert_relative_priority_queue (Node **head, int value) {
    Node **prev = head, *cur;
    if (*head) {
        cur = *head;
        while (value > cur->value) {
            value -= cur->value;
            prev = &cur->next;
            cur = cur->next;
            if (cur == 0) break;
        }
        *prev = create_node(value, cur);
        if (cur) {
            cur->value -= value;
        }
    } else {
        *head = create_node(value, 0);
    }
}

当您从列表的前面删除时，您调整 new 的值head：

void remove_relative_priority_queue (Node **head) {
    if (*head) {
        Node *cur = *head;
        *head = cur->next;
        if (*head) {
            (*head)->value += cur->value;
        }
        free(cur);
    }
}
于 2013-08-13T23:37:12.080 回答