数据结构课程设计哈夫曼编译器

small1= tree[j].weight; p2=p1; p1=j; } else

if(tree[j].weight

small2=tree[j].weight; p2=j; }

权值赋为两子节点权值之和

tree[p1].parent=i; //建立子节点与父节点间的对应关系，并将父节点

tree[p2].parent=i; tree[i].lchild=p1; tree[i].rchild=p2;

tree[i].weight=tree[p1].weight+tree[p2].weight; }

(2)编码模块 数据结构：

Code[]为定义在codetype类上的数组对象。 c为缓冲变量，其值为当前节点的下标值。 p为父节点的下标值。

Start为每个字符编码位串中第一个字符的起始位置。 对应代码段：

int c,p; //编码部分，c为当前节点编号，p为其父节点编号

for(i=0;i

Code[i].start=n; //start为编码位串的起始位置 Code[i].ch=tree[i].ch; c=i;

p=tree[i].parent; while(p!=0) {

Code[i].start--; Code=new Codetype[n]; for(i=0;i

Code[i]=new Codetype(); Code[i].bits=new Character[n]; }

. . .

if(tree[p].lchild==c) //向上回溯编码 Code[i].bits[Code[i].start]='0'; else

Code[i].bits[Code[i].start]='1'; c=p;

p=tree[p].parent; //将父节点作为下一轮循环的子节点 }

Code[i]=Code[i]; }

（3）译码模块 数据结构：

p为父节点编号。

t为待译码文件的字符数。

b[]为存放待译码文件容的数组。 ym存放译码结果。 对应代码段：

for(int q=0;q

if(b[q]=='0') p=tree[p].lchild; else

p=tree[p].rchild; if(tree[p].lchild==-1)

{

String ym=tree[p].ch.toString(); fw1.write(ym); p=m-1;}}

（4）字符统计模块 数据结构：

len为文章中的字符数。 a[i]为存放文章容的数组。

Ch[j]存放不同种类的字符,开始里面所有字符都为0值。 arr[]存放每种字符在文章中出现的次数。 对应代码段：

for(int i=0;i

for(int j=0;j

if(a[i]==ch[j])break;

else

if(j==n-1){ch[n-1]=a[i]; //若ch[]中找不到a[i]中存放的字符，则

将该种字符放到ch[]中。

若找到，则说明该种字符已被存入ch[]. n++;

break; }

. . .

}

for(int i=0;i

arr[j]++; //统计文章中每种字符的出现次数。 }

} //初始化ch[],存放字符种类

（5）Huffman类

public class Huffmantree {

public int weight; //weight为节点的权值

public int parent,lchild,rchild; //分别为当前节点的父节点，左、右子节点编号 public Character ch; //ch为节点名，即对应的字符。

public Huffmantree(){ //初始化，每个节点构成一个单节点树，权值为0。 }

weight=0; parent=0; lchild=-1; rchild=-1; ch='0';

(5)codetype类

public class Codetype { }}}

public Character bits[]; //一维数组，存放每个字符对应的编码位串 public int start; //start为每个字符位串的起始位置 public char ch; public Codetype(){

start=0; ch=0;

2.流程图

将文件容读入数组

. . .

统计文件中字符的种类和出现次数

建立哈夫曼树

哈夫曼树编码

将编码容写入数组和文件 对编码文件进行译码 五．调试与测试

分别输入多篇文章进行测试，文章字符数由少到多。

在程序编写过程中，要应用的数组较多，数组的使用使原本难于实现的算法变得简单易行。但因数组产生的问题也较多。编码时因存放文章及其频率的数组定义长度较短，不能给较长的文章编码。故要把相应数组长度改大一些。输出时会因为数组长度不匹配的问题出现空字符，也要做相应的调整。

测试文章：

1.su.fv,y,u ew gbu;i;fewiu!

2. When I was a little girl ,I dreamed to grow up. Because I think a child doesn't has freedom,and can't do anything by myself.

But now I have grow up,to my surprise,I feel more tired and have more responsibility.Though I can do something myself, I don't feel happy at all. I believe you also have the same thoughs with me. when every us was a child , we wanted to grow up, but when we became a older man,we don't have such nice life as wish. So whatever we are children or adults, we should try to make our life better, and make ourselves more happy. we should try our best to study hard, then we can let parents have good life, too!

do our best to do ourself ! Believe yourself ! You are the best!

. . .