C 스큐 힙 구현

Question

C에서 스큐 힙을 구현하려고하지만 코드가 컴파일되지 않습니다. 나는 C에서 경험이 없으며 C에서 어떤 유형의 힙도 만들지 않았습니다. 그래서 나는 그것을 고치는 법을 모르며 누군가 제가 올바른 방향을 가리킬 수 있기를 바랍니다. 저는 skew heap에 대한 기사를 읽었습니다. 그리고 이것은 제가 지금까지 찾은 알고리즘을 사용하여 얻은 것입니다. 미리 감사드립니다.

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의 더 프로토 타입의 범위가 어디에서 없다 있음을 알려줍니다, 컴파일러 오류에 관한

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 

Answer 1

:

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

이

내가 지금 받고있어 컴파일 에러입니다 skewHeapAdd이 정의되어 있으므로 (컴파일러는 분명히 C89 모드로 작동하지만 다행히 경고합니다) 컴파일러는 return t로 암시 적 선언을 가정합니다 ype int은 skewHeapMerge입니다.

모든 함수에 대한 프로토 타입이 포함 된 헤더 파일과이 함수가 사용되거나 정의 된 *.c 파일에있는 #include 파일을 추가하여 컴파일러에서 함수 유형을 알고 있어야합니다. 광고 sk->root가 struct node*이지만 skewHeapMerge 의한 암시 적 선언, 그가 int을 반환 가정

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

에게 있어야

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 

여기 컴파일러는 skewHeapMerge의 정의는 암시 적 선언에서 하나 충돌 유형을 준다 찾습니다. 라인

if (left == NULL) 
    return *right; 

if (right == NULL) 
    return *left; 

입니다

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 

어디 right RESP를 반환해야한다. *right 대신 left을 입력하십시오. *left (나는 처음에 그것을 간과했다). 당신 free D 뒤에 n를 사용하는 경우

---

당신은 skewHeapRemoveFirst

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

에서 실수 있습니다. 그 함수에서 마지막 두 줄을 교환해야합니다.

그리고 메모리가 누수되는 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을 할당하므로 할당을 제거하십시오.