JavaScript 클립보드로 복사하기

1. include<stdio.h>
2. include<string.h>
3. include<stdlib.h>
4. define SZ 256

struct node {

  char c;
  int freq;
  struct node* left;
  struct node* right;

};

struct node *Heap[SZ]; int last_idx = 0; int frequency[SZ] = { 0 }; // frequency of each ASCll code char codeBuf[1000]; int codeidx = -1; char *SymCode[SZ];

void swap(int x, int y); void Add_To_Heap(struct node* v); int Which_Is_Smaller(int idx); struct node *Del_From_Heap(); void traverse(struct node* n, char code); void Encoding(char *fName); void Decoding(char *fName);

void swap(int x, int y) {//x번째 노드와 y번째 노드의 자리를 바꿔주는 함수

  struct node *temp = Heap[x];
  //임시 공간에 x번째 노드를 저장한다.
  Heap[x] = Heap[y];
  //x번째 공간에 y번째 노드를 넘겨준다.
  Heap[y] = temp;
  //y번째 공간에 x번째 노드를 넘겨준다.

  //따라서, 자리가 바뀜을 알 수 있다.

}

void Add_To_Heap(struct node* v) {//Heap에 노드를 추가하는 함수

if (last_idx == SZ - 1)

  {//처음 0 자리는 비워둬야 하므로 -1을 한다.

return;

  }
  

  //Heap은 트리를 저장할 공간이다.
  last_idx++;
  //Hdap의 마지막 인덱스 값을 증가시킨다.(새 노드를 추가하기 위해)

  Heap[last_idx] = v;
  //마지막 Heap공간에 새로운 노드 v를 추가한다.

  int me = last_idx;
  //현재 값이 저장된 공간은 마지막 Heap공간이다.

  int p = me / 2;
  //부모 노드는 현재값을 반으로 나눈 공간에 존재한다.

  while (1)
  {

if (p < 1) { //부모가 0이 될 수 있다.(자식이 1인 경우 : 현재 노드가 첫 노드인 경우) return; //함수를 끝낸다. }

if (Heap[me]->freq >= Heap[p]->freq) { //현재 노드의 빈도수가 부모노드의 빈도수보다 크면, return;//잘 정렬된 것이므로 함수를 끝낸다. }

     else
     {//그 외의 경우는 부모와 자식 노드의 빈도수대로 정리 되지 않았으므로,
        swap(me, p);	//부모와 자식 노드의 자리를 바꾸어 준 후,
        me = p;		//부모의 idx를 자식에게 넘겨준다.
        p = me / 2;	//자식의 부모는 다시 반으로 나눈 값이다.
     }
  }

}

int Which_Is_Smaller(int idx) { int left = 2 * idx; //부모에 2를 곱하면 왼쪽 자식의 위치가 나온다. int right = left + 1; //왼쪽자식에 1을 더하면 오른쪽 자식의 위치가 나온다.

if (left > last_idx) // 무자식일 때 return -1; //-1을 return해준다.

else if (right <= last_idx) //오른쪽이 마지막 값보다 작거나 같으면 { if (Heap[left]->freq < Heap[right]->freq) //왼쪽이 오른쪽보다 작으면 return left; //왼쪽을 return해준다

else //오른쪽이 왼쪽보다 작으면 return right; //오른쪽을 return해준다. }

else //무자식도 아니고 오른쪽 값이 마지막값보다 작거나 같지도 않으면 return left; //왼쪽을 return해준다. }

struct node *Del_From_Heap() {//빈도수가 작은 순서대로 Heap으로부터 노드를 제거하는 함수 //반환값은 지워진 노드이다.

if (last_idx < 1) { //마지막 idx가 1보다 작으면 Heap에 저장된 노드가 없으므로 return 0; //0을 반환한다.

  }

  struct node *retVal = Heap[1];
  //지울 노드를 반환할 값으로 저장한다.

  Heap[1] = Heap[last_idx];
  //마지막에 있는 노드를 처음 공간으로 올린다.

  last_idx--;
  //마지막 노드를 옮겼으므로, idx를 감소시킨다.

  int me = 1;
  //현재 가리키는 값은 첫번째 노드이다.

  while (1)
  {
     int child = Which_Is_Smaller(me);

//which_is_smaller은 작은 노드가 있는 idx를 반환한다.

if (child < 0) { //현재 노드가 0보다 작은 경우는 노드가 없는 경우이다. break; }

     else
     {//노드가 존재할 때,

if (Heap[me]->freq <= Heap[child]->freq) { //현재 노드가 자식노드보다 빈도수 작은 경우 break; //잘 정렬되었으므로 while을 탈출한다. }

        else
        {	//현재 노드가 자식노드보다 빈도수 크면,
           swap(me, child);

//빈도수 작은 노드와 부모노드의 자리를 바꿔 다시 Heap을 정렬한다.

           me = child;

//자리를 바꾼 후, 자식의 idx를 넘겨받아 다시 정렬하도록 한다.

        }

     }
  }
  return retVal;
  //지운 노드를 반환한다. -->더한 노드를 생성하기 위해

}

void traverse(struct node* n, char code) //왼쪽과 오른쪽 값에 0과 1을 부여하는 함수 //허프만 트리를 만드는 함수 { codeidx++; codeBuf[codeidx] = code; codeBuf[codeidx + 1] = 0; // string으로 끝내게 하기 위해서 NULL을 넣어준다. if (n->left == 0 && n->right == 0) //맨 마지막 노드이면 { printf("%c -> %s : %d\n", n->c, codeBuf, n->freq);

//허프만 트리를 만드는 형식 char *hufCode = (char*)malloc(strlen(codeBuf) + 1); strcpy(hufCode, codeBuf); SymCode[(int)n->c] = hufCode; }

else //왼쪽이나 오른쪽에 값이 있다면 { traverse(n->left, '0'); //재귀함수, 왼쪽으로 내려가므로 0 traverse(n->right, '1'); //재귀함수, 오른쪽으로 내려가므로 1 } codeBuf[codeidx] = 0; //현재 코드 버프에 있는 데이터를 지워준다. 위의 재귀함수에서 넣은 0은 char 0이고 여기서 넣는 0은 NULL할 때의 0이기 때문에 재귀함수를 통하여 넣은 0은 NULL역할을 하지 않는다. codeidx--; //codeidx의 값을 하나 줄인다. return; }

void just_traverse(struct node* n, char code) // Decoding debug {

  codeidx++;
  codeBuf[codeidx] = code;
  codeBuf[codeidx + 1] = 0; // null point of string
  if (n->left == 0 && n->right == 0)
  {
     printf("%c -> %s\n", n->c, codeBuf);
  }

  else
  {
     just_traverse(n->left, '0');
     just_traverse(n->right, '1');
  }
  codeBuf[codeidx] = 0;
  codeidx--;
  return;

}

void Encoding(char *fName) {

  FILE *f;
  f = fopen("initial_huf.txt", "rt");

  if (f == 0)
  {
     printf("No such file");
     return;
  }

  char buf[1001] = { 0 }; // text read by 100 byte

  while (1)
  {
     char *c = fgets(buf, 1000, f);

     if (c == 0) // text read is done
     {
        break;
     }

     int len = strlen(buf); // for last string of text

     for (int i = 0; i < len; i++)
     {
        frequency[buf[i]]++;
     }
  }
  fclose(f);

  for (int i = 0; i < SZ; i++)
  {
     if (frequency[i] < 1) // 빈도수가 출현된 문자를 Add
     {
        continue;         // 카운트가 안된or 입력이 안된 문자는 생략된다
     }

     struct node* cur = (struct node*)malloc(sizeof(struct node));
     cur->c = (char)i;
     cur->freq = frequency[i];
     cur->left = 0;
     cur->right = 0;
     Add_To_Heap(cur);
  }
  ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  struct node* first;
  struct node* second;

  while (1) // Mean Heap -> Huffman Tree
  {
     first = Del_From_Heap();
     second = Del_From_Heap();

     if (second == 0) // root node of Huffman Tree
     {
        break;
     }

     struct node* temp = (struct node*)malloc(sizeof(struct node));
     temp->freq = first->freq + second->freq;
     temp->left = first;
     temp->right = second;
     Add_To_Heap(temp); // 우선순위 순으로 sort
  }
  //first is root node

  //SymCode init
  memset(SymCode, 0, sizeof(SymCode));

  traverse(first->left, '0');
  traverse(first->right, '1');

  int NumOfSym = 0;

  //SymCode의 문자와 허프만 코드 출력
  for (int i = 0; i < SZ; i++)
  {
     if (SymCode[i] != 0)
     {
        NumOfSym++;
        printf("SymCode %c -> %s\n", (char)i, SymCode[i]);
     }
  }

  printf("number of symbol is %d\n", NumOfSym);

  //파일에 기록

  //1.encoded 파일 생성 use Fname
  char outputFileName[100];
  char *period = strchr(fName, (int)'.');
  strncpy(outputFileName, fName, (int)(period - fName)); // outputFileName = altruism
  outputFileName[(int)(period - fName)] = 0; // altruism + null
  strcat(outputFileName, ".encoded"); //altruism.encoded
  printf("ouput is %s\n", outputFileName);

  FILE *fout = 0;
  fout = fopen("output_huf.txt", "wb");

  if (fout != 0)
  {
     fwrite(&NumOfSym, sizeof(NumOfSym), 1, fout); // 전체 심볼의 개수

     char wBuf[1000];
     for (int i = 0; i < SZ; i++)
     {
        if (SymCode[i] != 0)
        {
           //문자 + 길이 + 코드
           wBuf[0] = (char)i;
           wBuf[1] = (char)strlen(SymCode[i]);
           strcpy(&wBuf[2], SymCode[i]);
           fwrite(wBuf, sizeof(char), 2 + strlen(SymCode[i]), fout);
        }
     }

     // text encoding file contents
     FILE *fin; // txt reopen
     fin = fopen("initial_huf.txt", "rt");

     if (fin == 0)
     {
        printf("No such file");
        return;
     }

     else
     {
        int loc;
        loc = ftell(fout); //wb의 끝

        if (fseek(fout, 4, SEEK_CUR) != 0)
        {
           printf("Failed to move file pointer\n");
           fclose(fout);
           fclose(fin);
           return;
        }

        char bitBuf[1001]; // bit stream save
        int bitBufidx = 0; // 현재 stream svae location 
        int bitShiftCount = 7;
        int totalBit = 0;
        char flag = 0; // 0 == 기록할것 없음
                    // 1 == 있음

                    //bitbuf init
        memset(bitBuf, 0, 1000);

        while (fgets(buf, 1000, fin) != 0)
        {
           int len = strlen(buf);
           for (int i = 0; i < len; i++)
           {
              char * huffmanCode = SymCode[(int)buf[i]];
              for (int j = 0; j < strlen(huffmanCode); j++)
              {
                 char val = 0;

                 if (huffmanCode[j] == '0')
                 {
                    val = 0;
                 }

                 else if (huffmanCode[j] == '1')
                 {
                    val = 1;
                 }

                 else
                 {
                    printf("CIRITICAL ERROR\n");
                 }

                 val = val << bitShiftCount;
                 bitShiftCount--;

                 bitBuf[bitBufidx] |= val;
                 flag = 1;

                 totalBit++;
                 if (bitShiftCount < 0)
                 {
                    bitShiftCount = 7;
                    bitBufidx++;
                    if (bitBufidx >= 1000)
                    {
                       fwrite(bitBuf, 1, 1000, fout);
                       flag = 0;
                       bitBufidx = 0;
                       memset(bitBuf, 0, 1000);
                    }
                 }
              }
           }
        }

        if (flag == 1) // last string
        {
           fwrite(bitBuf, 1, bitBufidx + 1, fout);
        }

        if (fseek(fout, loc, SEEK_SET) == 0)
        {
           fwrite(&totalBit, sizeof(totalBit), 1, fout);
        }

        else
        {
           printf("unable to record total number of bit\n");
        }

        fclose(fin);
     }

     fclose(fout);
  }

  else
  {
     printf("Error : unable to open\n", outputFileName);
  }

}

void Decoding(char *fName) {

  struct node *Hufroot = 0;
  Hufroot = (struct node*)malloc(sizeof(struct node));
  Hufroot->left = Hufroot->right = 0;
  struct node *cur = Hufroot;

  FILE *af;
  af = fopen("final_han.txt", "rb");

  if (af == 0)
  {
     printf("Error : unable to open %s\n", fName);
     return;
  }

  else
  {
     //Tree 복구
     int num; // amount of symbol
     int cnt = 0;

     fread(&num, sizeof(int), 1, af);
     printf("Number of symbol : %d\n", num);

     while (cnt < num)
     {
        char c; // ASCll
        fread(&c, sizeof(char), 1, af);

        char n; // length
        fread(&n, sizeof(char), 1, af);

        //printf("%c %d ", c, n);

        for (int i = 0; i < n; i++)
        {
           char code; // Huffman code
           fread(&code, sizeof(char), 1, af);

           if (code == '0')
           {
              if (cur->left == 0)
              {
                 cur->left = (struct node*)malloc(sizeof(struct node));
                 cur->left->left = 0;
                 cur->left->right = 0;
              }
              cur = cur->left;
           }

           else if (code == '1')
           {
              if (cur->right == 0)
              {
                 cur->right = (struct node*)malloc(sizeof(struct node));
                 cur->right->left = 0;
                 cur->right->right = 0;
              }
              cur = cur->right;
           }

           else // only has 0 or 1
           {
              printf("CRITICAL ERROR\n");
              return;
           }
           //printf("%c", code);
        }
        //printf("\n");

        cur->c = c;
        cur = Hufroot;
        cnt++;
     }
     printf("\n\n\n");

     //codebuf[]
     codeidx = -1;
     //just_traverse(Hufroot->left, '0');
     //just_traverse(Hufroot->right, '1');
  }

  int num_Bits;
  int finished = 0;
  char contents;

  FILE *fout = fopen("altruism.txt", "wt");
  fread(&num_Bits, sizeof(int), 1, af);

  while (1)
  {
     fread(&contents, sizeof(char), 1, af);

     for (int i = 0; i < 8; i++)
     {
        if ((contents & 0x80) == 0)
        {
           cur = cur->left;
        }
        else
        {
           cur = cur->right;
        }
        if (cur->left == 0 && cur->right == 0)
        {
           printf("%c", cur->c);
           fputc(cur->c, fout);
           cur = Hufroot;
        }
        num_Bits--;
        if (num_Bits == 0)
        {
           finished = 1;
           break;
        }
     }
  }

}

int main() {

  Encoding("initial_huf.txt");
  Decoding("output_huf.txt");
  return  0;

}