C言語実現ハフマン符号化(最小スタック、二叉木)

//       QT     
#include 
#include 
#include <string.h>

typedef struct HNode *Heap; /*        */
typedef struct SData myData;
typedef struct SData *HuffmanTree;
typedef struct Ans SAns;
struct Ans //       
{
    char ch; //     
    char *s; //      ,           
};
struct SData //        
{
    int freq; //          
    char ch; //        
    HuffmanTree Left, Right; //               
};
int i = 0; //                  ans     
struct HNode //      
{
    myData *Data; //        
    int Size;          //         
    int Capacity;      //       
};
typedef Heap MinHeap; //    

MinHeap CreateHeap(int MaxSize); //      
int IsFull(MinHeap H); //          
int Insert(MinHeap H, myData X); //          
int IsEmpty(MinHeap H); //          
myData DeleteMin(MinHeap H); //          ,      (   ' ')
char* MatchingString(char *s1, char *s2); //          s1 s2,       
char* TraversalHT(myData *d, char *s, SAns *SAnsP); //         ,             
void InsertSort(SAns *ans, int N); //     
char* binarySearch(SAns *ans, char ch, int end); //          

int main()
{
    MinHeap heap = CreateHeap(100);
    char ch;
    int freq;
    printf("         (  0)，        ， Ctrl+Z  
");
    while (scanf("%d %c", &freq, &ch) != EOF)
    {
        myData temp = { freq, ch, NULL, NULL };
        Insert(heap, temp); //             ,        
    }
    HuffmanTree T;
    const int size = heap->Size; //   const  size         
    SAns *ans = (SAns*)malloc(sizeof(SAns)*size);
    //                ,            ,           
    //        ,          
    //        size-1 ,                   
    //           heap->Data[0],   heap->Data[0]       
    for (int j = 1; j < size; j++)
    {
        T = (HuffmanTree)malloc(sizeof(myData));
        T->Left = (HuffmanTree)malloc(sizeof(myData));
        T->Right = (HuffmanTree)malloc(sizeof(myData));
        *T->Left = (DeleteMin(heap));
        *T->Right = (DeleteMin(heap));
        T->freq = T->Left->freq + T->Right->freq;
        Insert(heap, *T);
        // printf("%d
", heap->Data[1].freq); //      ,        ,         
    }
    TraversalHT(&heap->Data[1], "", ans); //       ,      ans      

//    for (int k = 0; k < size; k++) //   
//    {
//        printf("%c   %s
", ans[k].ch, ans[k].s);
//    }
//    printf("**********************
");

    InsertSort(ans, size); //  ans        ,           ch   

//    for (int k = 0; k < size; k++) //        
//    {
//        printf("%c   %s
", ans[k].ch, ans[k].s);
//    }

    printf("          ：");
    char str[100]; //            ,             
    while (scanf("%s", str) != EOF)
    {
        for (int w = 0; w < strlen(str); w++)
        {
            //   str,       ,              
            printf("%s", binarySearch(ans, str[w], size - 1));
        }
        printf("
");
        printf("          ：");
    }

    return 0;
}

char* binarySearch(SAns *ans, char ch, int end)
{
    //        ,         ...
    int mid;
    int beg = 0;
    while (end >= beg)
    {
        mid = (beg + end) / 2;
        if (ans[mid].ch > ch)
            beg = mid + 1;
        else if (ans[mid].ch < ch)
            end = mid - 1;
        else
            return ans[mid].s;
    }
    return NULL; //   warning
}

void InsertSort(SAns *ans, int N)
{
    //        ,         ...
    for (int p = 1; p < N; p++)
    {
        SAns temp = ans[p];
        int i;
        for (i = p; i > 0 && ((int)ans[i - 1].ch < (int)temp.ch); i--)
            ans[i] = ans[i - 1];
        ans[i] = temp;
    }
}

char* MatchingString(char *s1, char *s2)
{
    //        C    ,     string ,             s1 s2
    //           ,       t
    //       s1   t ,       strcat()   s2  t  ,  t
    char *t = (char*)malloc(strlen(s1) + strlen(s2) + 1);
    if (t == NULL)
        exit(1);
    strcpy(t, s1);
    strcat(t, s2);
    return t;
}

char* TraversalHT(myData *d, char *s, SAns *SAnsP)
{
    //      d, s, SAnsP,
    // d        , s                 ,
    // SAnsP                             
    if (d->Left) //  d     ,          ,       s        "0"
        TraversalHT(d->Left, MatchingString(s, "0"), SAnsP);
    else
    {
        //       ,          ,         ,        NULL      
        SAns temp = { d->ch, s };
        SAnsP[i] = temp;
        printf("  :   %c  %s
", d->ch, s);
        i++; //       +1
        return NULL;
    }
    if (d->Right) //  d     ,          ,       s        "1"
        TraversalHT(d->Right, MatchingString(s, "1"), SAnsP);
    return NULL; //   warning
}

MinHeap CreateHeap(int MaxSize)
{
    //      MaxSize      
    MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
    H->Data = (myData *)malloc((MaxSize + 1) * sizeof(myData));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0].freq = -1; //   "  "             ，      -1
    //               for         (...&&i>1)，       
    return H;
}

int IsFull(MinHeap H)
{
    return (H->Size == H->Capacity);
}

int Insert(MinHeap H, myData X)
{
    //    X     H，  H->Data[0]       
    int i;
    if (IsFull(H))
    {
        printf("     
");
        return 0;
    }
    i = ++H->Size; // i                 
    for (; H->Data[i / 2].freq > X.freq; i /= 2)
        H->Data[i] = H->Data[i / 2]; //   X，  i  X   
    H->Data[i] = X; //  X  
    return 1;
}

int IsEmpty(MinHeap H)
{
    return (H->Size == 0);
}

myData DeleteMin(MinHeap H)
{
    //     H           ，       
    int Parent, Child;
    myData MinItem, X;

    if (IsEmpty(H))
    {
        printf("      
");
        X.freq = -1;
        return X; //-1        
    }

    MinItem = H->Data[1]; //            
    //                          
    X = H->Data[H->Size--]; //           
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child)
    {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child].freq > H->Data[Child + 1].freq))
            Child++;  // Child           
        if (X.freq <= H->Data[Child].freq)
            break; //        
        else  //   X
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;

    return MinItem;
}

 
転載先:https://www.cnblogs.com/tornado549/p/10144211.html