1

重複の可能性:
スキュー ヒープの C 実装

私は次の構造体を持っています:

typedef struct Task_t {
   float length;
   int value;
} task_t;

「値」を使用してこれらの構造体の束を保持するために、スキュー ヒープを使用しようとしています。したがって、最小の「値」を持つ構造体がルートになります。私のスキューヒープの実装は次のとおりです。

typedef struct node
{
int value;
struct node * root;
struct node * leftchild;
struct node * rightchild;
} Node;

typedef Node * skewHeap;

struct skewHeap
{
    struct node * root;
};
void skewHeapInit (struct skewHeap *sk)
{
    sk->root = 0;
}
void skewHeapAdd (struct skewHeap *sk)
{
    struct node *n = (struct node *) malloc(sizeof(struct node));
    struct node *s;
    assert(n != 0);
    n->value = 0;
    n->leftchild = 0;
    n->rightchild = 0;
    s->root = skewHeapMerge(s->root,n);
}

void skewHeapRemoveFirst (struct skewHeap *sk)
{
    struct node * n = sk->root;
    sk->root = skewHeapMerge(n->leftchild, n->rightchild);
    free(n);

}

struct node * skewHeapMerge(struct node *left, struct node *right)
{

    struct node *temp;

    if (left == NULL)
        return right;

    if (right == NULL)
        return left;

    if (left->value < right->value)
    {
        temp = left->leftchild;
        left->leftchild = skewHeapMerge(left->rightchild, right);
        left->rightchild = temp;
        return left;
     }
     else
     {
        temp = right->rightchild;
                right->rightchild = skewHeapMerge(right->leftchild, left);
        right->leftchild = temp;
        return right;
    }
}

私の問題は、このスキュー ヒープから構造体を正しく挿入および削除する方法がわからないことです。前もって感謝します。

4

1 に答える 1

1

valueヒープ内の各ノードに直接格納する代わりに、タスクへのポインターを格納します。挿入メソッドは、追加するタスクへのポインタを取る必要があります。ノード内のタスクにメモリを割り当て、関連するデータをコピーする必要があります。削除メソッドでこれを解放する必要があります。

例えば

typedef struct node
{
    Task_t *task;
    struct node *root;
    struct node *left;
    struct node *right;
} Node;

// your add should have passed in a value, because the only thing your code adds to the heap is zeros
void skewHeapAdd (struct skewHeap *sk, Task_t *task);

正直なところ、Task_t task;ポインターを使用する代わりに格納することもできます。これは、int と float しか含まれていないため、コピーのコストはそれほど高くありませんが、より一般的には、タスクへのポインターを使用する必要があります。あなたの場合、各ノードに明示的なルート ポインターがあるため、構造体へのポインターではなく実際の構造体を格納することで、さらに多くのメモリを浪費することになります。とにかくそれを取り除くことを強くお勧めします（それはエレガントでなく、まったく不要です）が、それにはコードのかなりの部分を書き直す必要があります。

于 2012-11-13T04:19:57.073 に答える