>

( 다음 반복 을 참조하십시오.)

Java에서 C로 피보나치 힙 구현을 재 작성했습니다.

fibonacci_heap.h:

#ifndef FIBONACCI_HEAP_H
#define FIBONACCI_HEAP_H
#include <stdbool.h>
#include <stdlib.h>
#ifdef  __cplusplus
extern "C" {
#endif
    typedef struct fibonacci_heap_t fibonacci_heap_t;
    /***************************************************************************
    * Allocates a new, empty heap with given degree.                           *
    ***************************************************************************/  
    fibonacci_heap_t* fibonacci_heap_t_alloc(size_t initial_capacity,
                                   float load_factor,
                                   size_t (*p_hash_function)(void*),
                                   bool (*p_equals_function)(void*, void*),
                                   int (*p_priority_compare_function)(void*, 
                                                                      void*));
    /***************************************************************************
    * Adds a new element and its priority to the heap only if it is not        *
    * already present.                                                         *
    ***************************************************************************/  
    bool fibonacci_heap_t_add(fibonacci_heap_t* p_heap, 
                              void* p_element, 
                              void* p_priority);
    /***************************************************************************
    * Attempts to assign a higher priority to the element. Return true only    *       
    * if the structure of the heap changed due to this call.                   * 
    ***************************************************************************/  
    bool fibonacci_heap_t_decrease_key(fibonacci_heap_t* p_heap, 
                                       void* p_element, 
                                       void* p_priority);
    /***************************************************************************
    * Return true only if the element is in the heap.                          * 
    ***************************************************************************/  
    bool fibonacci_heap_t_contains_key(fibonacci_heap_t* p_heap, 
                                       void* p_element);
    /***************************************************************************
    * Removes the highest priority element and returns it.                     * 
    ***************************************************************************/  
    void* fibonacci_heap_t_extract_min(fibonacci_heap_t* p_heap);
    /***************************************************************************
    * Returns the highest priority element without removing it.                * 
    ***************************************************************************/  
    void* fibonacci_heap_t_min(fibonacci_heap_t* p_heap);
    /***************************************************************************
    * Returns the size of this heap.                                           * 
    ***************************************************************************/  
    int fibonacci_heap_t_size(fibonacci_heap_t* p_heap);
    /***************************************************************************
    * Drops all the contents of the heap. Only internal structures are         *
    * deallocated; the user is responsible for memory-managing the contents.   * 
    ***************************************************************************/  
    void fibonacci_heap_t_clear(fibonacci_heap_t* p_heap);
    /***************************************************************************
    * Checks that the heap maintains the min-heap property.                    *
    ***************************************************************************/  
    bool fibonacci_heap_t_is_healthy(fibonacci_heap_t* p_heap);
    /***************************************************************************
    * Deallocates the entire heap with its internal structures. The client     *
    * programmer must, however, memory-manage the contents.                    * 
    ***************************************************************************/  
    void fibonacci_heap_t_free(fibonacci_heap_t* p_heap);
#ifdef  __cplusplus
}
#endif
#endif  /* HEAP_H */

fibonacci_heap.c:

#include "fibonacci_heap.h"
#include "unordered_map.h"
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
static const double LOG_PHI = 0.4813;
static const size_t DEFAULT_NODE_ARRAY_CAPACITY = 16;
typedef struct fibonacci_heap_node_t {
    void*                         p_element;
    void*                         p_priority;
    struct fibonacci_heap_node_t* p_parent;
    struct fibonacci_heap_node_t* p_left;
    struct fibonacci_heap_node_t* p_right;
    struct fibonacci_heap_node_t* p_child;
    size_t                        degree;
    bool                          marked;
} fibonacci_heap_node_t;
typedef struct fibonacci_heap_t {
    unordered_map_t*        p_node_map;
    fibonacci_heap_node_t*  p_minimum_node;
    fibonacci_heap_node_t** p_node_array;
    size_t                  node_array_capacity;
    size_t                (*p_hash_function)(void*);
    bool                  (*p_equals_function)(void*, void*);
    int                   (*p_key_compare_function)(void*, void*);
} fibonacci_heap_t;
static fibonacci_heap_node_t* fibonacci_heap_node_t_alloc(void* p_element, 
                                                          void* p_priority) {
    fibonacci_heap_node_t* p_node = malloc(sizeof(fibonacci_heap_node_t));
    if (!p_node) 
    {
        return NULL;
    }
    p_node->p_element  = p_element;
    p_node->p_priority = p_priority;
    p_node->p_parent   = NULL;
    p_node->p_left     = p_node;
    p_node->p_right    = p_node;
    p_node->p_child    = NULL;
    p_node->degree     = 0U;
    p_node->marked     = false;
    return p_node;
}
fibonacci_heap_t* 
fibonacci_heap_t_alloc(size_t map_initial_capacity,
                       float load_factor,
                       size_t (*p_hash_function)(void*),
                       bool (*p_equals_function)(void*, void*),
                       int (*p_key_compare_function)(void*, void*))
{
    fibonacci_heap_t* p_ret;
    if (!p_hash_function)        return NULL;
    if (!p_equals_function)      return NULL;
    if (!p_key_compare_function) return NULL;
    p_ret = malloc(sizeof(fibonacci_heap_t));
    if (!p_ret) return NULL;
    p_ret->p_node_array = malloc(sizeof(fibonacci_heap_node_t*) *
                                 DEFAULT_NODE_ARRAY_CAPACITY);
    if (!p_ret->p_node_array) 
    {
        free(p_ret);
        return NULL;
    }
    p_ret->node_array_capacity = DEFAULT_NODE_ARRAY_CAPACITY;
    p_ret->p_node_map = unordered_map_t_alloc(map_initial_capacity, 
                                              load_factor, 
                                              p_hash_function, 
                                              p_equals_function);
    if (!p_ret->p_node_map)
    {
        free(p_ret->p_node_array);
        free(p_ret);
        return NULL;
    }
    p_ret->p_minimum_node         = NULL;
    p_ret->p_hash_function        = p_hash_function;
    p_ret->p_equals_function      = p_equals_function;
    p_ret->p_key_compare_function = p_key_compare_function;
    return p_ret;
}
bool fibonacci_heap_t_add(fibonacci_heap_t* p_heap, 
                          void* p_element, 
                          void* p_priority) 
{
    fibonacci_heap_node_t* p_node;
    if (!p_heap) return false;
    if (unordered_map_t_contains_key(p_heap->p_node_map, 
                                     p_element))
    {
        /*printf("Element fail: %d\n", p_element);*/
        return false;
    }
    p_node = fibonacci_heap_node_t_alloc(p_element, p_priority);
    if (!p_node) return false;
    if (p_heap->p_minimum_node)
    {
        p_node->p_left = p_heap->p_minimum_node;
        p_node->p_right = p_heap->p_minimum_node->p_right;
        p_heap->p_minimum_node->p_right = p_node;
        p_node->p_right->p_left = p_node;
        if (p_heap->p_key_compare_function(p_priority, 
                                           p_heap->p_minimum_node->p_priority) < 0) 
        {
            p_heap->p_minimum_node = p_node;
        }
    } 
    else p_heap->p_minimum_node = p_node;
    unordered_map_t_put(p_heap->p_node_map, p_element, p_node);
    return true;
}
static void cut(fibonacci_heap_t* p_heap,
                fibonacci_heap_node_t* x, 
                fibonacci_heap_node_t* y)
{
    x->p_left->p_right = x->p_right;
    x->p_right->p_left = x->p_left;
    y->degree--;
    if (y->p_child == x) 
    {
        y->p_child = x->p_right;
    }
    if (y->degree == 0) 
    {
        y->p_child = NULL;
    }
    x->p_left = p_heap->p_minimum_node;
    x->p_right = p_heap->p_minimum_node->p_right;
    p_heap->p_minimum_node->p_right = x;
    x->p_right->p_left = x;
    x->p_parent = NULL;
    x->marked = false;
}
static void cascading_cut(fibonacci_heap_t* p_heap, fibonacci_heap_node_t* y)
{
    fibonacci_heap_node_t* z = y->p_parent;
    if (z)
    {
        if (y->marked)
        {
            cut(p_heap, y, z);
            cascading_cut(p_heap, z);
        }
        else 
        {
            y->marked = true;
        }
    }
}
bool fibonacci_heap_t_decrease_key(fibonacci_heap_t* p_heap, 
                                   void* p_element, 
                                   void* p_priority)
{
    fibonacci_heap_node_t* x;
    fibonacci_heap_node_t* y;
    if (!p_heap) return false;
    x = unordered_map_t_get(p_heap->p_node_map, p_element);
    if (!x) return false;
    if (p_heap->p_key_compare_function(x->p_priority, p_priority) <= 0)
    {
        /* Cannot improve priority of the input element. */
        return false;
    }
    x->p_priority = p_priority;
    y = x->p_parent;
    if (y && p_heap->p_key_compare_function(x->p_priority, y->p_priority) < 0) 
    {
        cut(p_heap, x, y);
        cascading_cut(p_heap, y);
    }
    if (p_heap->p_key_compare_function(x->p_priority, p_heap->p_minimum_node->p_priority) < 0)
    {
        p_heap->p_minimum_node = x;
    }
    return true;
}
static bool check_array(fibonacci_heap_t* p_heap, size_t size)
{
    if (p_heap->node_array_capacity < size) 
    {
        free(p_heap->p_node_array);
        p_heap->p_node_array = malloc(sizeof(fibonacci_heap_t*) * size);
        if (!p_heap->p_node_array) 
        {
            return false;
        }
        p_heap->node_array_capacity = size;
        return true;
    } 
    else 
    {
        return true;
    }
}
static void link(fibonacci_heap_node_t* y, fibonacci_heap_node_t* x)
{
    y->p_left->p_right = y->p_right;
    y->p_right->p_left = y->p_left;
    y->p_parent = x;
    if (!x->p_child)
    {
        x->p_child = y;
        y->p_right = y;
        y->p_left = y;
    }
    else
    {
        y->p_left = x->p_child;
        y->p_right = x->p_child->p_right;
        x->p_child->p_right = y;
        y->p_right->p_left = y;
    }
    x->degree++;
    y->marked = false;
}
static void consolidate(fibonacci_heap_t* p_heap)
{
    size_t array_size = 
            (size_t)(floor
                      (log
                        (unordered_map_t_size(p_heap->p_node_map)) 
                      / LOG_PHI)) + 1;
    size_t number_of_roots;
    size_t degree;
    size_t i;
    fibonacci_heap_node_t* x;
    fibonacci_heap_node_t* y;
    fibonacci_heap_node_t* tmp;
    fibonacci_heap_node_t* next;
    check_array(p_heap, array_size);
    /* Set the internal node array components to NULL. */
    memset(p_heap->p_node_array, 
           0, 
           array_size * sizeof(fibonacci_heap_node_t*));
    number_of_roots = 0;
    x = p_heap->p_minimum_node;
    if (x) 
    {
        ++number_of_roots;
        x = x->p_right;
        while (x != p_heap->p_minimum_node)
        {
            ++number_of_roots;
            x = x->p_right;
        }
    }
    while (number_of_roots > 0) 
    {
        degree = x->degree;
        next = x->p_right;
        while(true)
        {
            y = p_heap->p_node_array[degree];
            if (!y) break;
            if (p_heap->p_key_compare_function(x->p_priority, 
                                               y->p_priority) > 0) 
            {
                tmp = y;
                y = x;
                x = tmp;
            }
            link(y, x);
            p_heap->p_node_array[degree] = NULL;
            ++degree;
        }
        p_heap->p_node_array[degree] = x;
        x = next;
        --number_of_roots;
    }
    p_heap->p_minimum_node = NULL;
    for (i = 0; i < array_size; ++i) 
    {
        y = p_heap->p_node_array[i];
        if (!y) continue;
        if (p_heap->p_minimum_node) 
        {
            y->p_left->p_right = y->p_right;
            y->p_right->p_left = y->p_left;
            y->p_left = p_heap->p_minimum_node;
            y->p_right = p_heap->p_minimum_node->p_right;
            p_heap->p_minimum_node->p_right = y;
            y->p_right->p_left = y;
            if (p_heap->p_key_compare_function(
                   y->p_priority, 
                   p_heap->p_minimum_node->p_priority) < 0)
            {
                p_heap->p_minimum_node = y;
            }
        }
        else
        {
            p_heap->p_minimum_node = y;
        }
    }
}
void* fibonacci_heap_t_extract_min(fibonacci_heap_t* p_heap)
{
    fibonacci_heap_node_t* z;
    fibonacci_heap_node_t* x;
    fibonacci_heap_node_t* tmp_right;
    fibonacci_heap_node_t* node_to_free;
    void* p_ret;
    size_t number_of_children;
    if (!p_heap) return NULL;
    z = p_heap->p_minimum_node;
    if (!z) return NULL; /* Heap is empty. */
    number_of_children = z->degree;
    x = z->p_child;
    while (number_of_children > 0) 
    {
        tmp_right = x->p_right;
        x->p_left->p_right = x->p_right;
        x->p_right->p_left = x->p_left;
        x->p_left = p_heap->p_minimum_node;
        x->p_right = p_heap->p_minimum_node->p_right;
        p_heap->p_minimum_node->p_right = x;
        x->p_right->p_left = x;
        x->p_parent = NULL;
        x = tmp_right;
        --number_of_children;
    }
    z->p_left->p_right = z->p_right;
    z->p_right->p_left = z->p_left;
    p_ret = p_heap->p_minimum_node->p_element;
    if (z == z->p_right)
    {
        node_to_free = p_heap->p_minimum_node;
        p_heap->p_minimum_node = NULL;
    }
    else 
    {
        node_to_free = p_heap->p_minimum_node;
        p_heap->p_minimum_node = z->p_right;
//        puts("Before consolidate");
        consolidate(p_heap);
//        puts("After  consolidate");
    }
    unordered_map_t_remove(p_heap->p_node_map, p_ret);
    free(node_to_free);
    return p_ret;
}
void fibonacci_heap_t_free(fibonacci_heap_t* p_heap)
{
    if (!p_heap) 
    {
        return;
    }
    if (p_heap->p_node_array) 
    {
        free(p_heap->p_node_array);
    }
    if (p_heap->p_node_map)
    {
        unordered_map_t_free(p_heap->p_node_map);
    }
    free(p_heap);
}

bool fibonacci_heap_t_contains_key(fibonacci_heap_t* p_heap, void* p_element)
{
    if (!p_heap) return false;
    return unordered_map_t_contains_key(p_heap->p_node_map, p_element);
}
void* fibonacci_heap_t_min(fibonacci_heap_t* p_heap)
{
    if (!p_heap)                return NULL;
    if (p_heap->p_minimum_node) return p_heap->p_minimum_node->p_element;
    return NULL;
}
int fibonacci_heap_t_size(fibonacci_heap_t* p_heap)
{
    if (!p_heap) return 0;
    return unordered_map_t_size(p_heap->p_node_map);
}
static void clear_nodes_impl(fibonacci_heap_node_t* node)
{
    fibonacci_heap_node_t* current;
    fibonacci_heap_node_t* next_sibling;
    if (!node->p_child) 
    {
        free(node);
        return;
    }
    current = node->p_child;
    while (true) 
    {
        next_sibling = current->p_right;
        clear_nodes_impl(current);
        current = next_sibling;
        if (current == node->p_child)
        {
            free(node);
            return;
        }
    }
}
void fibonacci_heap_t_clear(fibonacci_heap_t* p_heap)
{
    fibonacci_heap_node_t* current;
    if (!p_heap) return;
    if (!p_heap->p_minimum_node) return;
    current = p_heap->p_minimum_node;
    while (true)
    {
        clear_nodes_impl(current);
        current = current->p_right;
        if (current == p_heap->p_minimum_node) break;
    }
    unordered_map_t_clear(p_heap->p_node_map);
}
static bool tree_is_healthy(fibonacci_heap_t* p_heap,
                            fibonacci_heap_node_t* node)
{
    fibonacci_heap_node_t* begin;
    if (!node)          return true;
    begin = node;
    while (true) 
    {
        if (p_heap->p_key_compare_function(node->p_priority, 
                                           node->p_parent->p_priority) < 0) 
        {
            return false;
        }
        if (!tree_is_healthy(p_heap, node)) return false;
        begin = begin->p_right;
        if (begin == node) return false;
    }
    return true;
}
static bool check_root_list(fibonacci_heap_t* p_heap)
{
    fibonacci_heap_node_t* current = p_heap->p_minimum_node;
    while (true)
    {
        if (p_heap->
                p_key_compare_function(current->p_priority,
                                       p_heap->p_minimum_node->p_priority) < 0) 
        {
            return false;
        }
        current = current->p_right;
        if (current == p_heap->p_minimum_node) return true;
    }
}
bool fibonacci_heap_t_is_healthy(fibonacci_heap_t* p_heap)
{
    fibonacci_heap_node_t* root;
    if (!p_heap) return false;
    if (!p_heap->p_minimum_node) return true;
    /* Check that in the root list, 'minimum_node' points to the node
       with largest priority. 
     */
    if (!check_root_list(p_heap)) return false;
    root = p_heap->p_minimum_node;
    /* Check that all trees are min-heap ordered: the priority of any child is
     * not higher than the priority of its parent. */
    while (root)
    {
        if (!tree_is_healthy(p_heap, root->p_child))
        {
            return false;
        }
        root = root->p_right;
        if (root == p_heap->p_minimum_node) return true;
    }
}

(시연에 필요한 모든 것을 찾을 수 있습니다 여기 .

전문적인 환경에서 C 코드를 작성한 경험이 없기 때문에 다음과 같은 질문 목록을 만들었습니다.

<올>
  • 나는 _t 를 들었다  접두사는 POSIX의 데이터 유형을 위해 예약되어 있습니다. 식별자가 형식 이름인지 확인하려면 어떻게해야합니까?
  • p_ 로 포인터 변수를 앞에 추가해도 괜찮습니까? ?
  • (오류가 아닙니다!) 컴파일 (clang)은 관련 경고의 긴 목록을 제공합니다. 이 프로그램은 "작동"하지만 제거하고 싶습니다.
  • 중괄호를 사용하는 가장 좋은 방법은 무엇입니까?
  • "단축"변수를 사용해야합니까? 예를 들어, my_list   data->db->...->list 대신 .
  • 메모리 누수 가능성을 발견 할 수 있습니까?
  • 기억 나는 것을 말 해주세요.
    • 답변 # 1

      질문과 관련하여 :

      <올>

      struct 접미사의 실제 이점은 없습니다   _t 를 가진 유형  -단지 혼란을 더합니다.

      p_ 로 모든 포인터를 접두사로 사용  모든 혼란이 많은 접두사를 도입하고 이제 모든 식별자가 동일한 접두사로 시작하므로 코드를 읽기 어렵게 만듭니다. 이는 일반적으로 실제 변수 이름을 식별하기 전에 두뇌가 더 많은 작업을 수행하고 더 많은 문자를 읽어야 함을 의미합니다.

      Errm, 그럼 고치세요 :). "오류로 취급 경고"를 설정하십시오 (clang에서는 -Werror 입니다).  flag)-문제를 해결하기위한 좋은 인센티브를 제공합니다.

      가장 좋은 방법은 일관되게 사용하는 것입니다. 그래서 이것은 :

      와이즈 비즈 와이즈 비즈

      기본 브레이싱 스타일이므로 다음과 같아야합니다.

      범위에서 두 번 이상 사용 된 경우, 로컬 변수를 사용하여 긴 역 참조 시퀀스의 값을 저장하는 것이 좋습니다. } else p_heap->p_minimum_node = p_node; 와 같은 것이지만  추상화가 옳지 않다는 것을 나타내는 약간의 코드 냄새 일 것입니다.

      코드를 살펴보면 괜찮아 보입니다. 그러나 확실하다면 : 단위 테스트를 작성하고 valgrind와 같은 도구를 사용하여 메모리 누수를 확인하십시오. Cpputest와 같은 일부 단위 테스트 프레임 워크에는 메모리 검사 기능이 내장되어있어 편리합니다.

      아래 참조

      <시간>

      다른 것들 :

      <올>

      } else { p_heap->p_minimum_node = p_node; } 부터  구현 파일에만 국한되며 data->db->...->list 로 단축 될 수 있습니다.  -이렇게하면 몇 줄이 다소 짧아집니다.

      의견에서 언급 한 바와 같이 : 이미 fibonacci_heap_node_t 가 있습니다   heap_node 를 위해  헤더에-구현에 넣지 마십시오.

      와이즈 비즈  리턴 값을 보유 할 변수의 이름이 typedef 로 잘못 지정되었습니다.  -힙을 반환하므로 이름을 지정하는 가장 좋은 방법은 fibonacci_heap_t 입니다. .

      fibonacci_heap_t_alloc   p_ret 를 반환  다양한 시나리오에서 사용 가능합니다.

      <올>

      프로그래머 오류 (힙 포인터로 전달됨 : heap )

      메모리 할당 실패

      요소가 이미 힙에 존재합니다 (완벽 할 수 있음)

      처음 두 개는 치명적일 수 있으며 세 번째 만 예상되는 상황입니다. fibonacci_heap_t_add 라인을 따라 자체 오류 코드를 구현하는 것이 좋습니다. false  그리고 NULL . 적절한 경우 (예 : 공개 인터페이스 방법) 오류 코드를 반환하도록 메소드를 변경하십시오.

      errno  배열의 크기를 특정 크기로 조정하는 메소드의 이름이 매우 나쁜 것 같습니다. 또한 당신은 perror 를 고려할 수도 있습니다 .

      와이즈 비즈  나는 strerror 를 다루기 위해 논리를 바꿀 것입니다.  사례를 먼저 작성하고 표준 사례를 다음과 같이 기본 리턴 라인으로 사용하십시오.

      check_array
      
      

      realloc

  • 이전 performance - 두 정수의 공약수를 반환
  • 다음 python - 콘텐츠 페이지가 제공되면 모든 검색 구문을 포함하는 가장 짧은 스 니펫을 결정하십시오 (순서 필요 없음)