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

数据结构课程设计报告

数据结构课程设计报告

哈 夫 曼 编 码 译 码 器

班级： 姓名： 学号： 完成时间：

第1页

数据结构课程设计报告

题目：哈夫曼编码译码器

【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编码译码系统。试为这样的通信端编写一个哈夫曼编码译码系统。 【基本功能】

一个完整的系统应具有以下功能： 初始化：输入一串字符（正文），计算不同字符（包括空格）的数目一级每种字符出现的频

率（以该种字符出现的次数作为其出现频率），根据权值建立哈夫曼树，输出每一种字符的哈夫曼编码。

编码：利用求出的哈夫曼编码，对该正文（字符串）进行编码，并输出。 译码：对于得到的一串哈夫曼编码，利用已求得的哈夫曼编码进行译码，将译出的正文输出。 【运行流程】

开始 初始化： 1、 输入正文 2、 统计字符出现次数并输出 3、 求出哈夫曼编码并输出 编码： 发送方利用得到的哈夫曼编码对正文进行编码，输出密文 译码： 接收方利用哈夫曼编码对密文进行译码，输出译后的字符串 是 是否继续 否 结束

第2页

数据结构课程设计报告

源程序：

//haffman.h

#include

struct HaffNode //哈夫曼的结点结构 {

int weight; char value; int flag; int parent; int leftchild; int rightchild; };

struct Code //存放哈夫曼编码的数据元素结构 {

char bit[MAXN]; char value; int start; int weight; };

void Haffman(int weight[],int n,HaffNode hafftree[],char str2[])//构造哈夫曼树 {

int j,m1,m2,x1,x2; //m1,m2是左右孩子的weight.x1,x2是左右孩子的仿真指针

for(int i=0;i<2*n-1;i++) //哈弗曼树的初始化，也就是将所有节点列出来，一边下面将他们一个一个构建入哈夫曼数中 {

if(i

hafftree[i].weight=weight[i]; hafftree[i].value=str2[i]; }

else hafftree[i].weight=0; hafftree[i].flag=0; hafftree[i].parent=0; hafftree[i].leftchild=-1; hafftree[i].rightchild=-1; }

for(i=0;i

m1=m2=MaxValue; x1=x2=0;

第3页

数据结构课程设计报告

for(j=0;j

if(hafftree[j].weight

m2=m1; //使得m1得到的比m2小 x2=x1;

m1=hafftree[j].weight; x1=j; }

else if(hafftree[j].weight

m2=hafftree[j].weight; x2=j; } }

hafftree[x1].parent=n+i; hafftree[x2].parent=n+i; hafftree[x1].flag=1; hafftree[x2].flag=1;

hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight; hafftree[n+i].leftchild=x1; hafftree[n+i].rightchild=x2; } }

void bianma(HaffNode hafftree[],int n,Code haffCode[],char str1[]) //编码功能 {

Code *cd=new Code; int child,parent;

for(int r=0;r

cd->start=n-1;

cd->weight=hafftree[r].weight; cd->value=str1[r]; child=r;

parent=hafftree[child].parent; while(parent!=0) {

if(hafftree[parent].leftchild==child)

cd->bit[cd->start]='0'; //左孩子结点为0 else

cd->bit[cd->start]='1'; //右孩子结点为1 cd->start--; child=parent;

第4页

数据结构课程设计报告

parent=hafftree[child].parent; }

for(int j=cd->start+1;jbit[j]; haffCode[r].start=cd->start; haffCode[r].weight=cd->weight; haffCode[r].value=cd->value; } }

void yima(HaffNode hafftree[],int n,string Enstr) //译码功能 { int root=2*n-2;

for(int i=0;i

if(Enstr[i]=='0'&&hafftree[root].leftchild!=-1) root=hafftree[root].leftchild;

else if(Enstr[i]=='1'&&hafftree[root].rightchild!=-1) root=hafftree[root].rightchild;

if(hafftree[root].leftchild==-1&&hafftree[root].rightchild==-1) { cout<

cout<

//haf.cpp

#include #include #include

const int MaxValue=100; const int MAXN=100; const int maxbit=100; using namespace std; #include\void main() {

int j=0;

第5页