哈夫曼编码程序设计

时间：2021-11-08 19:48:10 资料我要投稿

哈夫曼编码程序设计

算法与数据结构课程设计

哈夫曼编码/译码器设计

学生姓名：学号：

专业：（计算机科学与技术）年级：（大二）指导教师：（汪洋）

2009年6月19日

哈夫曼编码/译码器

问题描述：

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道）每端都需要一个完整的编/译码系统。试为这样/译码系统。

基本要求：

I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

P：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。

T：打印哈夫曼树（Tree printing）。将已在中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

大体解题思路:

（1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值{w1,w2,……，wN}构成n棵二叉树的集合F={T1,T2,……，Tn}把它们保存到结构体数组HT[n]中,其中{Ti是按它们的ASCⅡ码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。

（2）在HT[1..i]中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。

（3）哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。

概要设计：

实现的功能：1.查看原文（showpassage()），2.字符统计(showdetail())，

3.哈夫曼编码并输出内容(HuffmanCoding(HT,HC,30,w))，4.输出整篇文章的码字(printcode())，5.求最小权值(minweight())，6.最码字进行解码(decode())，7.测试解码(testdecode())，8.推出(break)。

（1）定义结构体HTNOde,*HuffmanTree;typedefchar**HuffmanCode;

定义堆结构体RedType;定义全局变量；

（2）编程序：测试编码(void testdecode())；解码(void decode)；求最

小权值(void minweight())；打印码字(void printcode())；堆排序(void HeapAdjust(SqList&L,int s,int

m))

；

哈

夫

曼

编

码

(void

HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,float *w,int n ))；输出个字符的次数比例(void showdetail())；输出原英文文章并做统计(void showpassage())；

（3）主函数

详细设计：（1）定义结构体

1.哈夫曼结构体 typedef struct {

float weight;

unsigned int parent, lchild, rchild; }HTNode, *HuffmanTree; typedef char **HuffmanCode ; 2.堆结构体 typedef struct {

float key; //关键字项

int otherinfo; //其他数据项（此题目中用不到）

}RedType;

typedef struct {

RedType r[MAXSIZE+1]; //r[0]闲置用作哨兵 int length; //顺序表长度 }SqList;

3.定义全局变量

HuffmanTree HT; //赫夫曼树 HuffmanCode HC; //码值

FILE *fp, *fp1, *fp2; int a[30] = {0}; float b[30];

float *w; //权（2）程序代码

1.测试解码（可以输入一个不正确的二进制码串） void testdecode() {

char str[200]; //存放自己输入的码子 int p, p1, i; //解码的线索 char ch; 内):\n");

gets(str);

printf("以上码子解码后为:\n");

p = 59; //最初令p为树根整数，p由根顺着树枝一直到树叶

i = 0; ch = str[i++]; while (ch!='\0') {

printf("\n请根据以上各个字符的编码输入一串二进制码字(200个以

查 !\n");

{

if (ch == '0') {

p = HT[p].lchild; } {

p = HT[p].rchild; } else {

printf("\n你输入了'0','1'之外的字符，无法正确译码，请检 return ; //直接结束 }

ch = str[i++]; //下一个码字不断的取下一个

else if(ch == '1')

}

if(p

switch (p) {

case 27 : printf(",");

break;

case 28 : printf("."); break;

case 29 : printf(" "); break;

case 30 : printf("\n"); break;

}

p1 = p; //让p1记住p p = 59; //这里p要重置为59，因为经过上面的程序p已经变化了，不重置为1则HT[p].lchild!=0||HT[p].rchild!=0所以for语句无法进行!!!!

} //while循环 if (p1 > 30)

printf("\n以上正确译出了前面的字符，由于你输入的二进制码不完整，最后一位字符无法译出，请检查!\n");

}

2.下面是解码 void decode() { int p; char ch;

printf("\n\n对码子解码后的如下:\n"); fp1 = fopen("bianma.txt","r"); if(!fp1) { printf("can not open this file!\n"); exit(0);

}

p = 59; 个非零整数，p由根顺着树枝一直到树叶

ch = fgetc(fp1); fp2 = fopen("jiema.txt","w"); if (!fp2) {

printf("can not open this file!\n");

//最初令p为任意一

exit(0);

}

while (ch!=EOF) { for ( ; HT[p].lchild!=0||HT[p].rchild!=0 ; ) 下一个

{ if (ch == '0') {

p = HT[p].lchild; }

else {

p = HT[p].rchild;

}

ch = fgetc(fp1); } switch (p) {

case 27 : printf(","); fprintf(fp2,","); break;

case 28 : printf("."); fprintf(fp2, "."); break;

case 29 : printf(" ");

fprintf(fp2, " "); break;

case 30 : printf("\n");

fprintf(fp2, "\n");

break;

//下一个码字不断的取

default : printf("%c", p+96);

fprintf(fp2, "%c", p+96);

} p = 59; //这里p要重置为59，因为经过上面的程序p已经变化了，不重置为1则HT[p].lchild!=0||HT[p].rchild!=0所以for语句无法进行!!!!

} //while循环 printf("\n"); fprintf(fp2, "\n"); fclose(fp1); fclose(fp2); }

3.求最小权值 void minweight() {

float Weight = 0; int i;

for (i = 0 ; i

Weight = Weight + strlen(HC[i+1])*b[i]; printf("最小权值是:%f\n",Weight); }

4.打印码子 void printcode() { char ch;

fp = fopen("Huffman.txt","r"); if (!fp) {

printf("can not open this file!\n"); }

fp1 = fopen("bianma.txt","w");

exit(0);

if (!fp1) { printf("can not open this file!\n"); exit(0);

}

printf("\n原英文文章经编码后如下:\n"); ch = fgetc(fp); while (ch!=EOF) {

if (ch > 96 && ch

printf("%s", HC[ch-96]);

fputs(HC[ch-96], fp1); ch = fgetc(fp); continue; }

if (ch > 64 && ch

fputs(HC[ch-64], fp1); ch = fgetc(fp); continue; } if (ch == ',')

{ printf("%s", HC[27]); fputs(HC[27], fp1); ch = fgetc(fp);

continue; } if (ch == '.')

{

//小写字母 //输出到文件里面 //大小字母 //输出到文件里面

printf("%s", HC[28]); f第一文库网puts(HC[28], fp1); ch = fgetc(fp); continue;

} {

if (ch == ' ')

printf("%s", HC[29]); fputs(HC[29], fp1); ch = fgetc(fp); continue;

} {

if (ch == '\n')

printf("%s", HC[30]); fputs(HC[30], fp1); ch = fgetc(fp); continue;

}

printf("\n\n"); fclose(fp); fclose(fp1); } 5.堆排序

void HeapAdjust(SqList &L, int s, int m) {

RedType rc; int j; rc = L.r[s];

for (j = 2 * s ; j

{

if (j L.r[j+1].key) //即使等于也不要动，不用加1

++j; break; if (rc.key

}

L.r[s] = rc;

}

void select(HuffmanTree t, int i, int &s1, int &s2)

{ //此函数被调用一次则就用堆排序选择两个最小的赋给s1和s2

SqList L;

RedType rc;

int j, k, n = 1;

L.length = 0;

for (j = 1 ; j

{ if (t[j].parent!=0)

continue;

L.r[n].key = t[j].weight; //赋值好,用堆排序

}

for (k = L.length/2 ; k > 0 ; --k)

HeapAdjust(L,k,L.length);

s1 = L.r[1].otherinfo; //最小的选出来了！

/***把最小的换到最下面***/

rc = L.r[1];

L.r[n].otherinfo = j; //存放序号,j是一直在加一的，n++; L.length++; //这样写很巧妙的循环一次加1，但是n不是的只有在符合条件的情况下才加1

L.r[1] = L.r[L.length]; //此次的select函数，进行堆排序的只有L.length 个（parent！=0的没有在里面），所以这里是L.length而不是i

L.r[L.length] = rc;

HeapAdjust(L,1,L.length-1);

s2 = L.r[1].otherinfo; //次小的选出来了(这里当输入1 4 2 8四个数时，第一次选出的s1=1,s2=3是对的，但第二次选出的s1=5，但s2是随机数)

}

6.赫夫曼编码

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *w, int n) // 算法6.12

{ // w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的'赫夫曼编码HC

int m, i, s1, s2, start, k;

unsigned c, f;

HuffmanTree p;

char *cd;

if (n

return;

m = 2 * n - 1;

w = (float *)malloc(30*sizeof(float));

for (i = 0 ; i

*(w+i) = b[i];

HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用 for (p = HT + 1, i = 1 ; i

{

(*p).weight = *w;

(*p).parent = 0;

(*p).lchild = 0;

(*p).rchild = 0;

for (i = n + 1 ; i

(*p).parent=0;

for (i = n + 1 ; i

{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2

select(HT, i-1, s1, s2);

HT[s1].parent = i;

HT[s2].parent = i; //最小的和次小的双亲已经不为0了，下次就不在它两中间找最小的和次小的了。

HT[i].lchild = s1;

HT[i].rchild = s2;

HT[i].weight = HT[s1].weight + HT[s2].weight;

} //建立赫夫曼树也容易，关键是select这个子函数!!! printf("赫夫曼树如下表:\n") ;

printf("__________________________________________________________________\n")

\n");

for(k = 1 ; k

{

if (k

printf("|___%2d____|__%c

和%c__|__%f__|____%2d____|____%2d____|____%2d____|\n",k,k+64,k+96,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);

if (k == 27)

printf("|___%2d____|___,____|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);

if (k == 28)

printf("|___%2d____|___.____|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);

if (k == 29)

printf("|___%2d____|__

[k].parent,HT[k].lchild,HT[k].rchild);

if (k == 30)

printf("|___%2d____|__

[k].parent,HT[k].lchild,HT[k].rchild);

if (k > 30)

printf("|___%2d____|________|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);

}

printf("\n") ;

HC = (HuffmanCode)malloc((n+1)*sizeof(char*));

cd = (char*)malloc(n*sizeof(char));

cd[n-1] = '\0';

for (i = 1 ; i

{

start = n-1; //这里f=HT[f].parent是很巧妙的!!! for (c = i, f = HT[i].parent ; f!=0 ; c = f, f = HT[f].parent)//f=HT[i].parent f!=0是结束条件，所有的编码最后都要回到HT[m],而只有HT[m]的parent是0!!!

// 从叶子到根逆向求编码 if (HT[f].lchild==c) //c是左孩子则码值是0 cd[--start] = '0'; //这样逆着输，当我们正序输出的时候就恰好是想要的编码了!!!

else

空格__|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT换行__|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT

cd[--start] = '1';

HC[i] = (char*)malloc((n-start)*sizeof(char));

// 为第i个字符编码分配空间 strcpy(HC[i],&cd[start]); //从cd复制编码(串)到HC，这里的&cd[start]是一个地址

}

free(cd); // 释放工作空间 printf("经赫夫曼编码后码值如下:\n");

for (i = 1 ; i

{

printf("%c和%c---->%f---->", i+64, i+96, HT[i].weight);

puts(HC[i]);

}

printf(" , ---->%f---->%s\n", HT[27].weight, HC[27]);

printf(" . ---->%f---->%s\n", HT[28].weight, HC[28]);

printf("空格---->%f---->%s\n", HT[29].weight, HC[29]);

printf("换行---->%f---->%s\n", HT[30].weight, HC[30]);

}

7.输出各个字符的次数，比例

void showdetail()

{

int i;

printf("此英文文章中各个字母,个数，比例如下表:\n");

printf("____________________________________________\n"); printf("|__字母__|_____个数_____|_______比例_______|\n");

for (i = 0 ; i

printf("|__%c和%c__|_____%3d______|_____%f_____|\n", i+97, i+65, a[i], b[i]);

printf("|___,____|_____%3d______|_____%f_____|\n", a[26], b[26]); printf("|___.____|_____%3d______|_____%f_____|\n", a[27], b[27]); printf("|__空格__|_____%3d______|_____%f_____|\n", a[28], b[28]);

printf("|__换行__|_____%3d______|_____%f_____|\n", a[29], b[29]); printf("\n");

}

8.输出原英文文章，并做统计

void showpassage()

{

float count = 0;

int i;

char ch;

{

printf("can not open Huffman.txt !\n"); exit(0); fp = fopen("Huffman.txt","r"); if (!fp)

}

printf("要编码的文章如下:\n");

ch = fgetc(fp);

while (ch!=EOF)

{

putchar(ch); //把要编码的文章输入到屏幕中 if (ch >= 'a' && ch

{

a[ch-'a']++;

count+=1;

}

if (ch >= 'A' && ch

count+=1;

}

if (ch == ',')

元 a[26]++; //逗号放在27号单元 a[27]++; //句号放在28号单元 a[28]++; //空格符放在29号单元 a[29]++; //换行符放在30号单 if (ch == '.') if (ch == ' ') if (ch == '\n')

ch = fgetc(fp); //a[]的零号单元放a

}

printf("\n\n");

}

（3）主函数

void main()

{

char c;

char s[200]=" 1.查看原文.\n 2.字符统计.\n 3.赫夫曼编码并输出内容.\n 4.输出整篇文章的码字.\n 5.求最小权值.\n 6.对码子进行解码.\n 7.测试解码.\n 8.退出.\n";

printf("\n\n");

printf("******************************************************\n");

printf("

**\n");

printf(" ** 说明:本程序只对英文文章的52个大小写字母，逗号，句 **\n");

printf(" ** 号，空格符，换行符进行赫夫曼编码，并且大小写字母不 **\n");

printf(" ** 区分，其它字符因为出现的概率太低，for (i = 0 ; i

故本程序没有考虑 **\n");

printf(" ** ，各个字符出现的频率对应他们的权值，解码时可能与原 **\n");

printf(" ** 文有少量的失真，希望用户理解和支持，谢谢! **\n");

printf("** **\n");

printf("********************************************************\n");

printf("\n\n");

printf("******************************************************\n");

printf(" * 注意:必须按顺序先进行1，2，3项的操作,否则会有错误! *\n");

printf(" * 当1,2,3项顺次进行完后可以任意选择这8种操作. *\n");

printf("******************************************************\n");

printf("请认真阅读以上注意的内容，如果已经读完请按任意键开始操作:\n");

c=getch();

system("cls");

{

printf("\n请选择你要的操作:\n\n");

puts(s);

c=getch();

switch (c)

{

case '1' : showpassage(); //这里必须先按 break; //1，2，3先按顺序进行1，2，3的操作，否则有问题顺序操作完后，则可以任意选择这8项操作

case '2' : showdetail(); break; break; break; break; break; break; case '3' : HuffmanCoding(HT, HC, w, 30); case '4' : printcode(); case '5' : minweight(); case '6' : decode(); case '7' : testdecode(); case '8' : break; printf("请输入正确的选项!\n"); } default : putch(7);

}while(c!='8');

printf("\n\nBye Bye ^_^ .!\n\n");

}

调试分析：

1. 在堆定义中RedType r[MAXSIZE+1],r[0]闲置用作哨兵；

2. 在测试解码中（p

switch (p)后P重置59是因为因为经过上面的程序p已经变化了，不重置为1则HT[p].lchild!=0||HT[p].rchild!=0所以for语句无法进行!!!!

3. 在解码void decode()中最初令p为任意一个非零整数，p由根顺着树枝一直到树叶; switch (p)后p要重置为59，因为经过上面的程序p已经变化了，不重置为1则HT[p].lchild!=0||HT[p].rchild!=0所以for语句无法进行!!!!

4. 堆排序void HeapAdjust(SqList &L, int s, int m) 中 if (j

L.r[j].key > L.r[j+1].key) //即使等于也不要动，不用加1；if (rc.key

5. void select(HuffmanTree t, int i, int &s1, int &s2)

//此函数被调用一次则就用堆排序选择两个最小的赋给s1和s2