c语言函数CrHuffmanTree,huffman编码C语言实验报告.docx

语言函数CrHuffmanTree,huffman编码C语言实验报告.docx"/>

c语言函数CrHuffmanTree,huffman编码C语言实验报告.docx

Huffman编码

数学系 李一鹏 P 第五组

实验题目：huffman编码

实验目的：熟悉二叉树操作，掌握huffman编码思想。

实验内容：

任盈盈要传授给令狐冲读心大法，她深色庄重地递给令狐冲一张貌似剑谱的那啥。令狐冲一看，蒙了，这……这是啥？擦，01010001101010111010101001010010101011101110？任盈盈说，其实人类内心的微小波动都可以通过读心术转化为0和1，只是人类会想得太多，我们如果需要迅速辨认出别人所想，必先有一个简单的01序列。令狐冲很想知道小师妹在想些什么，但是…令狐冲的脑袋你懂的，请大家编一个程序满足这人渣男主吧…

算法思想：

先把每个结点以树的形式储存在数组中，每次选择两个权值最小的两颗树合并成一个树加入数组，操作时只需要判断父结点是否为空即可判断其是否可合并。

程序清单：

#include

#include

#define new1 (ht*)malloc(sizeof(ht))

typedef struct huffmantree{

char data;

int weight;

struct huffmantree *left,*right,*parent;

}ht;

char s[20],a[128][128],b[128];

int maxdepth;

ht *huffmancreate(){//创建huffman树

ht *p[256],*p1,*p2;FILE *f1;int c[128]={0},k=0,j,i,min1,min2;char d;

f1=fopen("article.txt","r");

while(1){d=fgetc(f1);if(feof(f1))break;c[d]++;}//统计字符数目

fclose(f1);

for(i=0;i<128;i++)//生成n个叶结点

if(c[i]){

p[k]=new1;

p[k]->weight=c[i];

p[k]->data=i;

p[k]->left=0;

p[k]->right=0;

p[k]->parent=0;

k++;

}

for(i=k;i<=2*(k-1);i++){//生成根结点和n-2个枝结点

p[i]=new1;

p[i]->parent=0;

p[i]->data=6;//枝结点和根结点用黑桃表示

min2=min1=32767;

for(j=0;j

if(!p[j]->parent)

if(p[j]->weight

min2=min1;p2=p1;

min1=p[j]->weight;p1=p[j];

}else if(p[j]->weight

min2=p[j]->weight;p2=p[j];

}

p[i]->left=p1;p[i]->right=p2;

p1->parent=p[i];p2->parent=p[i];

p[i]->weight=min1+min2;

}

return p[i-1];//返回根结点

}

void fwh(ht *p,int i){//用递归进行huffman编码

int j;char c;

if(p->left){

s[i]=48;fwh(p->left,i+1);

s[i]=49;fwh(p->right,i+1);

}else{

putchar(p->data);putchar(9);//输出结点名

c=p->data;

b[c]=i;

for(j=0;j

putchar(10);

}

}

void depth(int i,ht *p){//求一棵树的深度

if(p){

if(i>maxdepth)maxdepth=i;

depth(i+1,p->left);

depth(i+1,p->right);

}

}

int forwardspace(ht *p){//求最左边结点到左屏幕的空格数

int i,fs;

for(i=0;p;p=p->left)i++;

for(fs=0;i

return fs;

}

void writeln(ht*p){//输出树

int i,a[20],pow2[20],front,rear,fs,nowd,nown,num[200],d[2