하프 만 트 리 (코드 구현)

앞에서 우 리 는 하프 만 트 리 의 이론 적 실현 을 소 개 했 고 구체 적 인 코드 실현 을 소개 했다.
우 리 는 먼저 하프 만 트 리 노드 의 데이터 구 조 를 정의 합 니 다.

struct haffManTreeNode //        
{
    char symbol;          //     
    int weight;        //  
    haffManTreeNode* lChild;
    haffManTreeNode* rChild;
};

struct haffManTreeRoot  //    ，         
{
    haffManTreeNode* next;
};

haffManTreeNode* initHaffManTreeNode(char symbol,int weight)
{
//        
    haffManTreeNode* tree = new haffManTreeNode;
    tree->lChild = NULL;
    tree->rChild = NULL;
    tree->symbol = symbol;
    tree->weight = weight;
    return tree;
}

나무 노드 가 생 긴 후에 우 리 는 서로 다른 노드 의 가중치 를 저장 하고 그들 을 정렬 시 켜 이 노드 로 우리 의 하프 만 나 무 를 구성 해 야 한다.

struct haffManQueue  //       
{
    haffManTreeNode* tree;   //         
    int weight;               //     
    haffManQueue* next;
};

struct haffManQueueHead  //    ，       ，      
{
    int size;
    haffManQueue* next;
};

haffManQueue* initQueue()
{
//       
    haffManQueue* queue = new haffManQueue;
    queue->weight = 0;
    queue->tree = NULL;
    queue->next = NULL;
    return queue;
}

가장 기본 적 인 데이터 구 조 를 정의 한 후에 우 리 는 하나의 배열 을 얻어 텍스트 의 단일 문자 출현 횟수 (가중치) 를 저장 해 야 한다. 여기 서 우 리 는 배열 아래 표 시 를 이용 하여 이 기능 을 실현 해 야 한다.

void getWeight(string& str,int (&weight)[256])
{
//   ，        ，      
// ：（1）           ，             
//（2）          256 ，          
    for(int i=0;i <= 255;i++)
    {
//     
        weight[i] = 0;
    }
    int count = str.length();
    for(int i=0;i < count;i++)
    {
//  ascii           
        weight[ (char)str[i] ]++;
    }
}

그 다음 에 우 리 는 이 가중치 배열 을 가지 게 되 었 다. 그러면 우리 에 게 필요 한 것 은 하 프 만 트 리 의 구축 과정 에 따라 코드 를 실현 하 는 것 이다.

//       ，      。。。        
// ：  ，      head   ，                  
void insertQueue(haffManQueueHead* (&head),haffManQueue* (&inserter),haffManQueue* (&address))
{
    // address      inserter  ， address NULL，         
    if(address == NULL)
    {
        inserter->next = head->next;
        head->next = inserter;
    }
    else if(address->next == NULL)
    {
        address->next = inserter;
    }
    else
    {
        inserter->next = address->next;
        address->next = inserter;
    }
}

//      ，              
haffManQueue* getQueueItem(haffManQueueHead* (&head))
{
    if(head->size == 0)
    {
        return NULL;
    }
    haffManQueue* temp = head->next;
    head->next = head->next->next;
    head->size--;
    return temp;
}

//     ，       
haffManQueueHead* initHaffManQueue(int (&weight)[256])
{
//    
    haffManQueueHead* head = new haffManQueueHead;
    head->next = NULL;
    head->size = 0;

    for(int i=0;i <= 255;i++)
    {
        if(weight[i] != 0)
        {
            if(head->size == 0)
            {
//          ，        
                haffManQueue* queue = initQueue();
                queue->tree = initHaffManTreeNode((char)i,weight[i]);
                queue->weight = queue->tree->weight;

                head->next = queue;
                head->size++;
            }
            else
            {
                haffManQueue* queue = initQueue();
                queue->tree = initHaffManTreeNode((char)i,weight[i]);
                queue->weight = queue->tree->weight;

//      ，      
                haffManQueue* temp = head->next;
//            ，       ，           
                haffManQueue* preNode = NULL;   

                while(queue->weight > temp->weight && temp != NULL)
                {
                    preNode = temp;
                    temp = temp->next;
                }
                insertQueue(head,queue,preNode);
                head->size++;
            }
        }
    }
    return head;
}

//          ，               
haffManTreeRoot* creataHaffManTree(haffManQueueHead* (&head))
{
//           
    haffManTreeRoot* root = new haffManTreeRoot;
    root->next = NULL;
    if(head->size == 0)
    {
        return root;
    }
    else
    {
        while(head->size != 1)
        {
//        ，    
            haffManQueue* lChild = getQueueItem(head);
            haffManQueue* rChild = getQueueItem(head);

            haffManQueue* newNode = initQueue();
// '\0'，          ，           
            newNode->tree = initHaffManTree('\0',lChild->weight+rChild->weight);
//             
            newNode->tree->lChild = lChild->tree;
            newNode->tree->rChild = rChild->tree;
            newNode->weight = newNode->tree->weight;

//       ，  
            if(head->size == 0)
            {
                head->next = newNode;
                head->size++;
            }
            else
            {
                haffManQueue* temp = head->next;
                haffManQueue* preNode = NULL;

                while(newNode->weight > temp->weight && temp != NULL)
                {
                    preNode = temp;
                    temp = temp->next;
                }
                insertQueue(head,newNode,preNode);
                head->size++;
            }
        }
    }
    root->next = head->next->tree;
    return root;
}

이것 이 바로 내 개인 적 으로 하프 만 나무의 실현 과정 에 관 한 것 이다.