1

Cでスキューヒープを実装しようとしていますが、コードがコンパイルされません。私はCの経験があまりなく、Cでヒープを作成したことはありません。そのため、修正方法がわかりません。誰かが私に正しい方向を示してくれることを願っています。私はスキューヒープに関する記事を読んでいますが、これは私がオンラインで見つけたアルゴリズムを使用してこれまでに得たものです。前もって感謝します。

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

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));
    assert(n != 0);
    n->value = 0;
    n->leftchild = 0;
    n->rightchild = 0;
    line 185. s->root = skewHeapMerge(s->root, n);
}

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

line 196. struct node * skewHeapMerge(struct node *left, struct node *right)
{
    struct node *temp = (struct node *) malloc(sizeof(struct node));

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

これらは私が現在得ているコンパイルエラーです：

program.c: In function ‘skewHeapAdd’:
program.c:185: warning: implicit declaration of function ‘skewHeapMerge’
program.c:185: warning: assignment makes pointer from integer without a cast
program.c: In function ‘skewHeapRemoveFirst’:
program.c:191: warning: assignment makes pointer from integer without a cast
program.c: At top level:
program.c:196: error: conflicting types for ‘skewHeapMerge’
program.c:185: note: previous implicit declaration of ‘skewHeapMerge’ was here
program.c: In function ‘skewHeapMerge’:
program.c:202: error: incompatible types when returning type ‘struct node’ but ‘struct   node *’ was expected
program.c:205: error: incompatible types when returning type ‘struct node’ but ‘struct node *’ was expected
4

1 に答える 1

1

コンパイラエラーについては、

program.c: In function ‘skewHeapAdd’:
program.c:185: warning: implicit declaration of function ‘skewHeapMerge’
program.c:185: warning: assignment makes pointer from integer without a cast

のプロトタイプが定義さskewHeapMergeれているスコープ内にないことを示しますskewHeapAdd。したがって（コンパイラは明らかにC89モードで動作しますが、ありがたいことに警告します）、コンパイラは。の戻り型intを持つ暗黙の宣言を想定していskewHeapMergeます。

すべての関数のプロトタイプと、これらの関数が使用または定義され#includeているすべての*.cファイルにヘッダーファイルを追加して、コンパイラーが関数のタイプを認識できるようにします。

program.c: In function ‘skewHeapRemoveFirst’:
program.c:191: warning: assignment makes pointer from integer without a cast

それはラインでなければなりません

sk->root = skewHeapMerge(n->leftchild, n->rightchild);

ここsk->rootで、はですがstruct node*、の暗黙の宣言によりskewHeapMerge、はを返すと想定されintます。

program.c: At top level:
program.c:196: error: conflicting types for ‘skewHeapMerge’
program.c:185: note: previous implicit declaration of ‘skewHeapMerge’ was here

ここでコンパイラは、の定義がskewHeapMerge暗黙の宣言からの型と競合する型を与えることを検出します。

program.c: In function ‘skewHeapMerge’:
program.c:202: error: incompatible types when returning type ‘struct node’ but ‘struct   node *’ was expected
program.c:205: error: incompatible types when returning type ‘struct node’ but ‘struct node *’ was expected

それはラインのためです

if (left == NULL) 
    return *right;

if (right == NULL) 
    return *left;

あなたがそれぞれを返す必要がある場所right。leftそれぞれの代わりに*right。*left（私は最初はそれを見落としていました）。

あなたは間違いを犯していますskewHeapRemoveFirst

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

nあなたがそれをした後にあなたが使うところfree。その関数の最後の2行を交換する必要があります。

そしてでskewHeapMerge

struct node * skewHeapMerge(struct node *left, struct node *right)
{
    struct node *temp = (struct node *) malloc(sizeof(struct node));

    if (left == NULL)
        return *right;

    if (right == NULL)
        return *left;

メモリリークが発生しています。tempが使用されている場合は、left->leftchildまたはに割り当てるため、割り当てを削除しright->rightchildます。

于 2012-11-12T23:34:56.203 に答える