数据结构程序设计作业——《哈夫曼编码》

数据结构实验报告

题 目 哈夫曼编码

学生姓名 王某某 专业班级 测控120X班 学 号 U2012XXXXX

1 问题描述

输入一字符串，以字符串中各字符出现的频数为权值构造哈夫曼编码。然后输入一0—1序列，根据生成的哈夫曼编码解码序列。

2 算法描述

（1）哈夫曼树的表示

设计哈夫曼树的结构体（htnode），其中包含权重、左右孩子、父母和要编码的字符。用这个结构体（htnode）定义个哈夫曼数组（hfmt[]）。 迷宫定义如下： typedef struct {

int weight; int lchild; int rchild; int parent; char key; }htnode;

typedef htnode hfmt[MAXLEN];

（2）对原始字符进行编码 初始化哈夫曼树（inithfmt）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。 并显示出每个字符的编码。

1.void inithfmt(hfmt t)//对结构体进行初始化 2.void inputweight(hfmt t)//输入函数

3.void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数 4.void creathfmt(hfmt t)//创建哈夫曼树的函数 5.void phfmnode(hfmt t)//对字符进行初始编码

（3）对用户输入的字符进行编码

- 1 -

void encoding(hfmt t)//对用户输入的电文进行编码 {

char r[1000];//用来存储输入的字符串 int i,j;

printf(\请输入需要编码的字符:\ gets(r);

printf(\编码结果为:\ for(j=0;r[j]!='\\0';j++) for(i=0;i

if(r[j]==t[i].key) hfmtpath(t,i,j); printf(\}

（4）对用户输入的字符进行编码

void decoding(hfmt t)//对用户输入的密文进行译码 {

char r[100]; int i,j,len;

j=2*n-2;//j初始从树的根节点开始 printf(\请输入需要译码的字符串:\ gets(r); len=strlen(r);

printf(\译码的结果是:\ for(i=0;i

if(r[i]=='0') {

j=t[j].lchild; if(t[j].lchild==-1)

- 2 -

{

printf(\ j=2*n-2; } }

else if(r[i]=='1') {

j=t[j].rchild; if(t[j].rchild==-1) {

printf(\ j=2*n-2; } } }

printf(\}

3 程序设计流程图

- 3 -