#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);
}
'과거에 공부했던 것들(저장용) > 학부생' 카테고리의 다른 글
[AVR Studio](atmega 128) led shift control (0) | 2015.07.23 |
---|---|
Avr studio) atmega128 계산기 프로그램 _ 인터럽트 사용 (0) | 2015.07.23 |
Sudoku 정답이 맞는지 확인하는 프로그램 (0) | 2015.07.23 |
Sudoku 해결 프로그램 (0) | 2015.07.23 |
아이언돔 예측하기 (0) | 2015.07.23 |