数据结构实验报告八—哈夫曼编译码

数据结构 实验报告 哈夫曼编/译码

问题描述：

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

(1) 从文件中读入字符集大小n，以及n个字符和n个权值。

(2) 构建哈夫曼树，对每个字符生成哈夫曼编码。

(3) 从文件中读入需编码的字符串，利用哈夫曼编码，对字符串进行编码，编

码结果保存在文件。

一、 需求分析：

（1）、根据输入的字符和字符的权值建立哈夫曼树。

（2）、字符的数目和字符的权值由用户自己设定。

（3）、根据建立的哈夫曼树进行，编码和译码操作。

二、概要设计 ：

1. 哈夫曼树的定义

typedef struct{

char letter; //存储字符

int weight; //存储字符的权值

int parent; //父亲

int lchild; //左孩子

int rchild; //右孩子

}HTNode,*HuffmanTree;

2. 算定义的存储结构

//本结构存储哈夫曼树、编码等，便于后面的操作进行

typedef struct

{

HuffmanTree HT;

//动态分配数组存储哈夫曼编码表

HuffmanCode HC;

//记录输入字符的长度，编码和译码用到

int len;

char *c;//存储输入的字符

}Huf;

数据结构 实验报告 哈夫曼编/译码

3. 一些操作函数

void setHuffmanTree(HuffmanTree &HT,char *str,int *w,int n) 建立哈夫曼树，str是存储输入字符的数组，w 是存储字符权值的数组，n为输入字符的数目

Huf setHuffmanCode(HuffmanTree &HT,HuffmanCode &HC,int n,char *s)

为哈夫曼树编码，HT是已经建立的哈夫曼树，HC用于存储编码，民为字符的数目，s是存储字符的数组

Huf Initialization()

初始化函数

void Encoding(Huf huf)

编码函数

void Decoding(Huf huf)

译码函数

void Print()

打印代码文件的函数

void Treeprinting(Huf huf)

打印哈夫曼树的函数

4. 主函数

void main(){

根据不同的选择，执行特定的函数，完成操作

}

三、详细设计

核心程序为哈夫曼树的构建，实现该功能时，通过不断调用selecte（在已有的结点中选择双亲结点值为0，且权值最小的两个结点）函数查找构造哈夫曼树中的各个子树的结点，直到所有这种结点全部用完，即一颗哈夫曼树即构造完成。

1、 建立哈夫曼树及求哈夫曼编码

//初始化操作，接受输入，调用函数setHuffmanTree，

//setHuffmanCode创建树并编码

Huf Initialization(){

HuffmanTree HT;

HuffmanCode HC;

char c[100];//存放输入的字符

int w[100];//存放字符的权值

int n;

cout<<"请输入字符的个数："<<endl;

cin>>n;

cout<<"请输入所有字符："<<endl;

gets(c);

数据结构 实验报告 哈夫曼编/译码

for(int i=1;i<=n;i++){

cout<<"请输入第"<<i<<"个字符的权值："<<endl;

cin>>w[i];

}

//将数组c中的元素向右移动一位

for(int j=n-1;j>=0;j--)

{

c[j+1]=c[j];

}

// 调用setHuffmanTree函数

setHuffmanTree(HT,c,w,n);

//调用setHuffmanCode函数

Huf huf=setHuffmanCode(HT,HC,n,c);

return huf;

}

//选择权值最小的两个结点

void Select(HuffmanTree &HT,int s,int &s1,int &s2){

int j, k, i;

j=k=10000;

s1=s2=0;

for(i=1;i<=s;i++){

if(HT[i].parent==0){

if(HT[i].weight<j){

k=j;s2=s1;

j=HT[i].weight;

s1=i;

}

else if(HT[i].weight<k){

k=HT[i].weight;

s2=i;

}

}

}

}

//创建哈夫曼树函数的具体实现

void setHuffmanTree(HuffmanTree &HT,char *str,int *w,int n)

{

HuffmanTree p;

int m,i,s1,s2; //s1,s2是权值最小的两个结点的序号

m = 2*n-1; //一棵有N个叶子节点的哈夫曼树共有2*N-1个结点 //动态定义长度，0号单元未使用

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

数据结构 实验报告 哈夫曼编/译码

//初始化

for(p=HT+1,i=1;i<=n;++i,++p){

p->letter = str[i]; p->weight = w[i];

(*p).parent = 0; p->lchild = 0; p->rchild = 0;

}

for(;i<=m;++i,++p){

p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; }

//建立哈夫曼树

for(i=n+1;i<=m;++i){

Select(HT,i-1,s1,s2); //此函数为自己定义用于选择出s1,s2 HT[s1].parent=i; HT[s2].parent=i;

HT[i].lchild=s1; HT[i].rchild=s2;

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

}

// 将哈夫曼树写入到文件hufTree.dat中

FILE *huftree;

huftree=fopen("hufTree.dat","rt");

if(huftree==NULL)

{ huftree=fopen("hufTree.dat","wt");

for(i=1;i<=m;i++)

fprintf(huftree,"%d %d %d %d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);//向文件中写入

rewind(huftree);

}

}

//从叶子到根结点逆向求每个字符的赫夫曼编码

Huf setHuffmanCode(HuffmanTree &HT,HuffmanCode &HC,int n,char *s){

Huf huf;

// 分配n个字符编码的头指针向量

huf.c=(char *)malloc((n+1)*sizeof(char));

//将以输入的字符存储在huf的c中

for(int j=1;j<=n;j++){

huf.c[j]=s[j];}

int start = 1; char *cd; int f,c,i;

//分配n个字符编码的头指针向量

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

//临时的编码存储，作用是分配求编码的工作空间

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

cd[n-1]='\0'; //编码结束符

//按已生成的哈夫曼树，逐个求哈夫曼编码并获得各个字符的哈夫曼编码 for(i=1;i<=n;++i){

start = n - 1; //编码结束符的位置

数据结构 实验报告 哈夫曼编/译码

//从叶子到根逆向求编码

for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) if(HT[f].lchild == c) cd[--start] = '0';

else cd[--start] = '1';

//为第i个字符编码分配空间

HC[i] = (char *)malloc((n - start) * sizeof(char)); //从cd复制编码（串）到HC

strcpy(HC[i], &cd[start]);

}

//将 …… 此处隐藏：8684字，全部文档内容请下载后查看。喜欢就下载吧 ……