哈弗曼编码问题

一、数据类型

//哈夫曼树结点类型

typedef struct huffman_node {

//结点权值，只有叶结点权值有意义 int w;

//结点对应字符，只有叶结点有字符 char c;

//结点编码，只有叶结点有意义 char code[10];

struct huffman_node *lchild; struct huffman_node *rchild; }huffnode_t;

//链表中存储数据元素类型，实际为huffman树结点首地址 typedef huffnode_t *data_t;

//链表的结点数据类型 typedef struct node {

data_t data;

struct node *next; }linknode_t;

//队列头数据类型 typedef struct {

linknode_t *front; linknode_t *rear; }linkqueue_t;

头文件程序：

#ifndef _HEAD_H_ #define _HEAD_H_

#include #include #include

//哈夫曼树结点类型

typedef struct huffman_node

{

//结点权值，只有叶结点权值有意义 int w;

//结点对应字符，只有叶结点有字符 char c;

//结点编码，只有叶结点有意义 char code[10];

struct huffman_node *lchild; struct huffman_node *rchild; }huffnode_t;

//链表中存储数据元素类型，实际为huffman树结点首地址 typedef huffnode_t *data_t;

//链表的结点数据类型 typedef struct node {

data_t data;

struct node *next; }linknode_t;

//队列头数据类型 typedef struct {

linknode_t *front; linknode_t *rear; }linkqueue_t;

//队列操作

extern linkqueue_t *create_empty_linkqueue(); extern int is_empty_linkqueue(linkqueue_t *q);

extern int enter_linkqueue(linkqueue_t *q,data_t data); extern data_t delete_linkqueue(linkqueue_t *q);

#endif

主程序：

#include \"head.h\"

#define M 4

#define MAX 100

#define A 0 #define B 1

#define C 2 #define D 3

huffnode_t *alloc_huffman_node(char c,int w) {/*{{{*/

huffnode_t *root = NULL;

root = (huffnode_t *)malloc(sizeof(huffnode_t)); memset(root,0,sizeof(huffnode_t));

root->c = c; root->w = w;

root->lchild = root->rchild = NULL;

return root; }/*}}}*/

//链式队列的有序入队：链表的有序插入，更新队列尾指针 int enter_order_linkqueue(linkqueue_t *q,data_t data) {/*{{{*/

linknode_t *temp = NULL; linknode_t *p = q->front;

temp = (linknode_t *)malloc(sizeof(linknode_t)); temp->data = data;

while(p->next && p->next->data->w < data->w) {

p = p->next; }

//新结点如果在链表尾插入 if(p->next == NULL) {

//更新尾指针 q->rear = temp; }

temp->next = p->next; p->next = temp;

return 0; }/*}}}*/

int print_linklist(linknode_t *head) {/*{{{*/

linknode_t *p = head->next;

while(p) {

printf(\"(%c:%d) \

p = p->next; }

putchar('\\n');

return 0; }/*}}}*/

linkqueue_t *create_huffman_queue(int freq[],int n) {/*{{{*/

//1.创建空队列

//2.循环创建哈夫曼结点

// huffnode_t *alloc_huffman_node(char c,int w); //3.有序入队

// int enter_order_linkqueue(linkqueue_t *q,data_t data); //4.输出队列中所有结点数据

// int print_linklist(linknode_t *head); //5.返回huffman队列首地址

linkqueue_t *q = NULL; huffnode_t *root = NULL; int i = 0;

q = create_empty_linkqueue();

for(i = 0;i < n;i++) {

root = alloc_huffman_node('A' + i,freq[i]);

enter_order_linkqueue(q,root); }

print_linklist(q->front);

return q; }/*}}}*/

int is_one_node(linkqueue_t *q) {

return q->front->next == q->rear; }

huffnode_t *create_huffman_tree(linkqueue_t *q) {/*{{{*/

//1.循环判断队列是否只有一个结点

//2.如果是则创建结束，将最后一个结点出队，函数执行结束 //3.如果不是，出队两次，先出队是左孩子，后出队为右孩子

//4.分配一个新的huffman树结点，字符为'\\0'，权值为两个子结点权值和

//5.让新结点lchild保存左孩子首地址，rchild保存右孩子首地址，构成一棵新的二叉树 //6.将新二叉树根结点以有序方式入队 //7.重复1~6

//循环结点返回huffman树首地址

huffnode_t *ltree = NULL,*rtree = NULL; huffnode_t *root = NULL;

while(!is_one_node(q)) {

ltree = delete_linkqueue(q); rtree = delete_linkqueue(q);

root = alloc_huffman_node('\\0',ltree->w + rtree->w); root->lchild = ltree; root->rchild = rtree;

enter_order_linkqueue(q,root); }

return delete_linkqueue(q); }/*}}}*/

// A B C D char *code_addr[M];

int level_travel(huffnode_t *root) {/*{{{*/

linkqueue_t *q = NULL; huffnode_t *tmp = NULL; char *addr = NULL;

q = create_empty_linkqueue();

enter_linkqueue(q,root);

while(!is_empty_linkqueue(q)) {

tmp = delete_linkqueue(q);

printf(\"(%c:%d) \

if(tmp->lchild != NULL) {

strcpy(tmp->lchild->code,tmp->code); strcat(tmp->lchild->code,\"0\");

enter_order_linkqueue(q,tmp->lchild); }

if(tmp->rchild != NULL) {

strcpy(tmp->rchild->code,tmp->code); strcat(tmp->rchild->code,\"1\");

enter_order_linkqueue(q,tmp->rchild); }

if(tmp->lchild == NULL && tmp->rchild == NULL) {

addr = tmp->code;

switch(tmp->c) {

case 'A':

code_addr[A] = addr; break; case 'B':

code_addr[B] = addr; break; case 'C':

code_addr[C] = addr; break; case 'D':

code_addr[D] = addr; break; } } }

putchar('\\n');

return 0; }/*}}}*/

int compress(char *p,char encode[]) {/*{{{*/

while(*p) {

switch(*p) {

case 'A':

strcat(encode,code_addr[A]); break; case 'B':

strcat(encode,code_addr[B]); break; case 'C':

strcat(encode,code_addr[C]); break; case 'D':

strcat(encode,code_addr[D]); break; } p++; }

return 0; }/*}}}*/

int count_freq(char *p,int freq[]) {/*{{{*/

while(*p) {

switch(*p) {

case 'A':

freq[A]++; break; case 'B':

freq[B]++; break; case 'C':

freq[C]++; break; case 'D':

freq[D]++; break; }

p++; }

return 0; }/*}}}*/

void uncompress(char *p,huffnode_t *root) {

huffnode_t *p_node = root;

while(*p) {

if(*p == '0') {

p_node = p_node->lchild; }

if(*p == '1') {

p_node = p_node->rchild; }

if(p_node->lchild == NULL && p_node->rchild == NULL) {

printf(\"%c\ p_node = root; }

p++; }

putchar('\\n');

return ; }

int main()

{

// A B C D

int freq[M] = {0};// = {7,2,4,5}; linkqueue_t *q = NULL; huffnode_t *root = NULL; int i = 0;

char buf[MAX] = \"AAAABBAAACCDDCCDDD\"; char encode[MAX] = {0};

printf(\"Input strings:\"); scanf(\"%99[ABCD]\

/*puts(buf);*/

count_freq(buf,freq);

for(i = 0;i < M;i++) {

printf(\"%c:%d\\n\ }

//构造哈夫曼队列 create_huffman_queue() q = create_huffman_queue(freq,M);

//构造哈夫曼树

root = create_huffman_tree(q);

//层次遍历

level_travel(root);

for(i = 0;i < M;i++) {

printf(\"%c:%s\\n\ }

puts(\"-----------------------compress-----------------------\"); puts(buf);

compress(buf,encode); puts(encode);

puts(\"=====================uncompress==========================\"); uncompress(encode,root);

return 0;

}

Makefile程序：

OBJS := linkqueue.o huffman.o CC = gcc

CFLAGS = -Wall -g CPPFLAGS = -I.

vpath linkqueue.c ../../jun11/ballclock/

a.out:$(OBJS) $(CC) $(CFLAGS) $^ -o $@

$(OBJS):head.h

.PHONY:clean

clean: $(RM) a.out $(OBJS)