实验六 哈夫曼编码和译码的算法设计与实现

实验名称 实验日期 实验六 哈夫曼编码和译码的算法设计与实现

实验方案 实验操作 实验成绩 2012-04-22 实 验 信息系统设计与仿室 真室I 实验台号 34号 班级姓信工11-1BF 李煌名 峰

实验结果

一、实验目的

1、根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法； 2、编程实现哈夫曼编译码器； 3、掌握贪心算法的一般设计方法。

二、预习与参考

1、认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理; 2、设计和编制哈夫曼编译码器。 [参考数据类型或变量] typedef ElemType char； typedef struct node{ int w; int flag; ElemType c;

struct node *plink,*llink,*rlink;

char code[m]; }Node;

Node *num[n], *root; [参考子程序接口与功能描述]

void SetTree( NODE *root )

功能: 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树 void EnCode( Node *p )

功能: 利用已建好的哈夫曼树，对输入的正文进行编码

void DeCode( void )

功能: 利用已建好的哈夫曼树，将输入的代码进行译码

三、实验要求

上机实验时，一人一组，独立上机，熟练运用二叉树与贪心思想对数据进行压缩。

四、实验步骤

1、 设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止; 2、 设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止; 3、 设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止; 4、 将你的程序整理成功能模块存盘备用。 5、 将写的程序如下： #include #include #include #include

#define maxn 20 //最大结点数目 #define inf 0xfffffff //无穷大

typedef struct node {

double w; int flag; int c;

struct node *plink,*llink,*rlink; char code[maxn]; int codelen; node() //初始化节点 {

flag=0; llink=NULL; plink=NULL; rlink=NULL; codelen=0;

} }node;

node *num[2*maxn-1];//指针数组 int n;

void SetTree(node *&root)//从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树 {

int i,m,j;

scanf(\输入结点个数n for(i=0;i

num[i]=new node(); num[i]->c=i;

scanf(\输入结点的权值 } m=n;

double min1,min2;

int pos1=0,pos2=0;

for(i=0;i

min1=inf; min2=inf;

for(j=0;j

if(num[j]->flag==0) {

if(num[j]->w

min1=num[j]->w;

pos2=pos1;

pos1=j; }

else if(num[j]->w

min2=num[j]->w; pos2=j; } } }

num[pos1]->flag=1; //将pos1和pos2合并在新结点中，作为新节点的子节点

num[pos2]->flag=1;

num[n]=new node(); //新节点编号从n开始 num[n]->c=-1;

////添加代码，建立新结点n//// //建立新结点n

num[n]->w=num[pos1]->w+num[pos2]->w; num[n]->llink=num[pos1]; num[n]->rlink=num[pos2]; num[pos1]->plink=num[n]; num[pos2]->plink=num[n];

n++; }

root=num[n-1]; n=m; }

void EnCode(node *root,int deep,char code[]) //利用已建好的哈夫曼树，对输入的文本进行编码 {

int i;

if(root->c!=-1) {

for(i=0;i

root->code[i]=code[i]; }

root->codelen=deep; return; }

code[deep]='0'; //左节点编码为0 EnCode(root->llink,deep+1,code); code[deep]='1'; //右节点编码为1 EnCode(root->rlink,deep+1,code); }

void DeCode(node *root,char code[]) //利用已建好的哈夫曼树，对输入的代码进行译码 {

int i;

node *temproot=root;

int len=strlen(code); int ans[maxn],anslen=0; for(i=0;i

////添加代码，根据code[i]的值确定temproot的指向//// //根据code[i]的值确定temproot的指向

if(code[i]=='0')

temproot=temproot->llink;

else

temproot=temproot->rlink;

if(temproot->c!=-1) {

ans[anslen++]=temproot->c; temproot=root; }

if(temproot->llink==NULL && temproot->rlink==NULL) {

printf(\你输入的数据不存在于该哈弗曼树中!\\n\ return; }

}

printf(\输入数据的译码为：\\n\ for(i=0;i

printf(\ }

printf(\}

void print() {

int i,j; for(i=0;i

printf(\ for(j=0;jcodelen;j++)

printf(\

printf(\ } }

int main() {

freopen(\

SetTree(root); char code[maxn*maxn]; EnCode(root,0,code); print();

printf(\按上面的编码规则输入代码:\\n\node *root=NULL; root=new node();

freopen(\

scanf(\DeCode(root,code);

return 0; }

五、测试

输入 8

0.6 0.2 0.05 0.05 0.03 0.03 0.03 0.01 输出 0.6： 0 0.2： 10 0.05： 1100 0.05： 1111 0.03： 11010 0.03： 11011 0.03： 11101 0.01： 11100

六、实验报告要求

1、 阐述实验目的和实验内容; 2、 提交实验程序的功能模块; 3、 记录最终测试数据和测试结果。

七、心得

在实验中我掌握哈夫曼编码的二叉树结构表示方法。

本文来源：https://www.bwwdw.com/article/vkwo.html