Huffman 코딩 (구현한 부분까지)

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_ELEMENT 100

typedef struct heap

{

char ch;              //문자

int num;              //발생빈도

struct heap *left;

struct heap *right;

}Huff_node;

struct node

{

char ch;         //문자

int num;         // 발생빈도.

struct node *next;

};

struct element

{

char ch;

char *p;

};

//기록하고 남은 데이터가 저장되는 공간

int wbdata = 0;

//남은 데이터가 몇 비트인지 저장하는 변수

int remBit = 0;

int size;

struct node *head = 0;

Huff_node Huffman[MAX_ELEMENT];

struct node list[MAX_ELEMENT];

struct element who[MAX_ELEMENT];

int checkchar(char ch)             //ch를 확인해서 배열안에 있는값을 증가시킨다.

{

struct node *cur = head;

while (cur != 0)

{

if (ch == cur->ch)

{

cur->num = cur->num + 1;

return 1;

}

cur = cur->next;

}

return 0;

}

void add(char ch)

{

int num = 0;

num = checkchar(ch);

if (num == 1)        //리턴값을 받아와서 새로운것이 아니라 기존에 잇던것에 num만 증가시켰으면 return 시킨다.

{

return;

}

struct node *cur = head;

struct node *new = (struct node *) malloc(sizeof(struct node));

new->ch = ch;

new->num = 0;

new->next = 0; // 새로운 new 구조체를 초기화 시킨다.

if (head == 0)            //head가 비어있다면  new를 head에 입력하고 증가시킨다.

{

head = new;

new->num = new->num + 1;

return;

}

else                          //cur를 끝으로 옮겨서 그 옆에다가 새로운 것을 추가한다.

{

while (cur->next != 0)

{

cur = cur->next;

}

cur->next = new;

cur->num = cur->num + 1;

}

}

void printsll()

{

struct node *cur = head;

while (cur->next != NULL)

{

printf("%c %d\n", cur->ch, cur->num);

cur = cur->next;

}

printf("%c %d\n", cur->ch, cur->num);

}

void sortingSLL()

{

struct node *p, *q;

int tmp;

char word;

for (p = head; p; p = p->next)

{

for (q = p->next; q; q = q->next)

{

if (p->num > q->num) 

{

tmp = p->num;

p->num = q->num;

q->num = tmp;

word = p->ch;

p->ch = q->ch;

q->ch = word;

}

}

}

}

Huff_node* delete_min_heap()

{

int parent, child;

Huff_node *root = (Huff_node *)malloc(sizeof(Huff_node));

Huff_node temp;

root->ch = Huffman[1].ch;

root->num = Huffman[1].num;

root->left = Huffman[1].left;

root->right = Huffman[1].right;

temp = Huffman[size--];

parent = 1;

child = 2;

while (child <= size)

{

if ((child<  size) && (Huffman[child].num) > Huffman[child + 1].num)

{

child++;

}

if (temp.num <= Huffman[child].num)

{

break;

}

Huffman[parent] = Huffman[child];

parent = child;

child = child * 2;

}

Huffman[parent] = temp;

return root;

}

void init_inorder(Huff_node *node)

{

if (node == 0)

{

return;

}

init_inorder(node->left);

node->p = NULL;

init_inorder(node->right);

}

void inordertraversal(Huff_node *node, int length, char add_code, char *prev_code)

{

if (node == 0)

{

return;

}

if (add_code != NULL)

{

if (node->p == NULL)

{

node->p = (char *)malloc(sizeof(char)*(length + 1));

if (length == 1)

{

node->p[length - 1] = add_code;

node->p[length] = NULL;

}

else

{

strcpy(node->p, prev_code);

node->p[length - 1] = add_code;

node->p[length] = NULL;

}

}

}

inordertraversal(node->left, length + 1, '0', node->p);                 //왼쪽으로 가면 0

inordertraversal(node->right, length + 1, '1', node->p);               //오른쪽으로 가면 1 을 추가해준다.

}

void huffman_code()                                    //허프만 코드 제조기.

{

Huff_node *tree = &Huffman[1];

init_inorder(tree);

inordertraversal(tree, 0, NULL, NULL);

}

void insertHeap(Huff_node temp)

{

int i;

i = size++;

while ((i != 1) && (temp.num < Huffman[i / 2].num))

{

Huffman[i] = Huffman[i / 2];

i = i / 2;

}

Huffman[i] = temp;

}

void huffman_tree()

{

Huff_node *least_temp = (Huff_node *)malloc(sizeof(Huff_node));

Huff_node *least_temp2 = (Huff_node *)malloc(sizeof(Huff_node));

Huff_node temp;

least_temp = delete_min_heap();

least_temp2 = delete_min_heap();

temp.ch = NULL;

temp.num = least_temp->num + least_temp2->num;

temp.left = least_temp;

temp.right = least_temp2;

insertHeap(temp);

}

int main(void)

{

FILE *fp1 = fopen("data.txt", "rt"); {if (fp1 == NULL)exit(1); }

FILE *fp2 = fopen("output.txt", "wb");

unsigned char ch = 0;

unsigned int num = 0;

unsigned int len = 0;

unsigned long int position = 0;

while (1)

{

num = fscanf(fp1, "%c", &ch);

if (num == EOF)

{

break;

}

add(ch);

}

printf("sorting 전\n");

printsll();

printf("------------------------------------------------------------------\n");

sortingSLL();

printf("sorting 후\n");

printsll();

while (head != 0)

{

struct node *cur = head;

struct heap temp;

temp.ch = cur->ch;

temp.num = cur->num;

temp.left = temp.right = 0;

head = head->next;

free(cur);

insertHeap(temp);

}

while (size != 1)

{

huffman_tree();

}

huffman_code();

Huff_node *node = (Huff_node *)malloc(sizeof(Huff_node));

fclose(fp1);

fclose(fp2);

}