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

相対的な優先度または「前の」ポインタのいずれかで、各ノードに余分なデータを保存する必要があります。次のノードの相対的な優先度は、ノードが削除されるたびに更新する必要があるため (前のポインターなしでそれを行うには?)、「前の」ポインターをお勧めします。

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 に答える