哈夫曼编码

哈夫曼编码译码系统

一、需求分析

1、程序的基本功能：

①构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符以及n个对应的权

值，建立哈夫曼树；利用已将建好的哈弗曼树求每个叶结点的哈夫曼编码，并保存。

②编码：利用已构造的哈弗曼编码对“明文”文件中的正文进行编码，然后将结果存

入“密文”文件中。

③译码：将“密文”文件中的0、1代码序列进行译码。

④打印“密文”文件：将文件以紧凑格式显示在终端上，同时，将此字符形式的编码

保存。

⑤打印哈夫曼树:将已在内存中的哈夫曼以凹入表形式显示在终端上。

2、输入输出要求：

①从键盘接收字符集大小n、以及n个字符和n个权值；

②构造哈夫曼树：将HFMTree数组中的各个位置的各个域都添上相关的值，并将结构

体数组存入文件HTree.txt中。

③打印哈夫曼树：从HFMTree数组读取相关的结点信息，以凹入表方式将各个结点画

出来；

④构造哈夫曼编码：先从文件HTree.txt中读入相关的字符信息进行哈夫曼编码，将字

符与其对应的编码存入文件HNode.txt中；

⑤编码：利用已构造的哈夫曼树对文件进行编码，打印结果，并将结果存入新建文件

中；

⑥译码：将密文文件中的内容利用HNode.txt中建立的编码规则进行翻译，打印结果，

并将结果存入新建文件中。

3、测试数据：

输入叶子结点个数为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，且字符集与权值集合一一对应。

二、概要设计

1、抽象数据类型的定义：

①采用静态链表作为哈夫曼树的存储结构；

②求哈夫曼编码时使用一维数组HCode作为哈夫曼编码信息的存储。

2、主模块的流程及各子模块的主要功能：

①int main()

{

主菜单；

swich语句结构选择；

return 0;

}

②in_park()

{

输入车牌号；

若停车场已满，停入便道中，否则停入停车场；

}

③output()

{

输入所要离开车辆的车牌号，以及离开时间；

停在便道内的第一辆车进入停车场；

}

③show_car()

{

依次显示停车场内的车辆信息；

}

show_queue()

{

依次显示便道内的车辆信息；

}

3、模块之间的层次关系：

主函数

Creat output show_car show_queue

judge

三、详细设计

1、定义的相关数据类型：

①哈夫曼树结点：

typedef struct

{

int weight;

int park;

int lchild;

int rchild;

char ch;

}

②哈弗曼编码结点：

typedef struct

{

Car Park[MAX_PARK];

int top;

}ParkStack;

2、函数的调用关系：

main

in_park output show_car show_queue

judge

四、调试分析

调试中遇到的问题及对问题的解决方法：

⑴遇到的问题：

①编码时最后一位总是多出一位数字；

②编码时出现无限循环；

⑵解决方法：

①改变构造哈夫曼树时的循环条件；

②改变构造哈夫曼编码的循环条件；

五、使用说明及测试结果

1、使用说明：

①进入主菜单，选择所要进行的操作；

②构造哈夫曼树：输入叶结点个数，及其字符与权值；

③选择显示哈夫曼树，哈夫曼树以凹入表形式显示；

④选择构造哈夫曼编码，即构造哈夫曼编码，若成功，则显示成功；

⑤选择编码：选择进行键盘输入或者从文件中获取。

2、测试结果：

停车场容量为5，连续有7辆车到来，牌照号分别为f001、f002、f003、f004、f005、f006、f007，前5辆车进入停车场1-5号车位，第6、7辆车停入便道的1、2号位置上。牌照号为f003的车辆从停车场开走后，f006从便道进入停车场，便道上只剩f007。

六、伪码算法

#include

#include

#include

#include

#include

#include

#include "stdlib.h"

#define N 4

#define MAXVSLUE 1000

typedef struct

{

char letter;

int weight;

int parent;

int lchild;

int rchild;

}HNodeType;

HNodeType HNode[2*N-1];

#define MAXBIT 10

typedef struct

{

char bit[MAXBIT];

int start;

}HCodeType;

HCodeType HCode[N];

void Creat_HuffMtree(HNodeType HFMTree[],int n) ; /* 构造哈夫曼

树*/

void HaffmanConde(HNodeType HFMTree[], HCodeType HuffCode[]);

void Display();

void makecode1(char s[MAXVSLUE]);

void makecode2(char s[MAXVSLUE]);

void yicode1();

void yicode2();

void Dis1();

void Dis2();

void printing(int root,int length);

void main()

{

cout<<"*****************************欢迎进入编译器系统********************************"<

Display();

for(;;)

{

char ch;

char c=getch();

if(c=='4')

break;

switch(c)

{

case '1':

Dis2();

ch=getch();

switch(ch)

{

case '1':

Creat_HuffMtree(HNode,N) ;

HaffmanConde(HNode,HCode);

break;

case '2':

cout<<"此哈夫曼树的凹入法表示为"<

printing(2*N-2,0);

break;

}

Display();

break;

case '2':

Dis1();

ch=getch();

char s[MAXVSLUE];

switch(ch)

{

case '1':

makecode1(s);

break;

case '2':

makecode2(s);

break;

}

Display();

break;

case '3':

Dis1();

ch=getch();

switch(ch)

{

case '1':

yicode1();

break;

case '2':

yicode2();

break;

}

Display();

break;

}

}

}

void Creat_HuffMtree(HNodeType HFMTree[],int n) /* 构造哈夫曼

树*/

{

/*构造的哈夫曼树存储于HFMTree[]， n为叶子结点的个数*/

int m1,x1,m2,x2; /* x1和x2存储最小和次小权值，m1和m2存储其

位置*/

int i,j;

for(i=0;i<2*n-1;i++) /* HFMTree初始化*/

{

HFMTree[i].weight=0;

HFMTree[i].parent=-1;

HFMTree[i].lchild=-1;

HFMTree[i].rchild=-1;

}

for(i=0;i

HFMTree[i].letter=NULL;

cout<<"依次输入"<

{

cout<<"输入"<

cin>>HFMTree[i].letter;

cout<<"输入"<

cin>>HFMTree[i].weight;

} /* 出入n个叶子结点的权值，设为整型*/

for(i=0;i

{

x1=x2=MAXVSLUE;

m1=m2=0;

for(j=0;j

{

if(HFMTree[j].parent==-1 && HFMTree

[j].weight

{

/*找出根结点具有最小和此最小权值的两棵

树*/

x2=x1;

m2=m1;

x1=HFMTree[j].weight;

m1=j;

}

else if(HFMTree[j].parent==-1 && HFMTree

[j].weight

{

x2=HFMTree[j].weight;

m2=j;

}

}

/*将找出的两棵子树合并成一棵树*/

HFMTree[m1].parent=n+i;

HFMTree[m2].parent=n+i;

HFMTree[n+i].weight=HFMTree[m1].weight+HFMTree[m2].weight;

HFMTree[n+i].letter='z'-i;

HFMTree[n+i].lchild=m1;

HFMTree[n+i].rchild=m2;

HFMTree[n+i].parent=-1;

}

FILE *fptr;

if((fptr=fopen("HTree.txt","w"))!=NULL)

{

fprintf(fptr, " letter weigth lchild rchild

parent\n");

for(i=0;i<2*N-1;i++ )

fprintf(fptr, "%d %c %d %d

%d %d\n" ,i,HFMTree[i].letter,HFMTree[i].weight, HFMTree [i].lchild,HFMTree[i].rchild,HFMTree[i].parent );

}

else

printf("文件打开失败");

fclose(fptr);

printf(" letter weigth lchild rchild parent\n"); for(i=0;i<2*N-1;i++ )

printf("%d %c %d %d %d

%d\n" ,i,HFMTree[i].letter,HFMTree[i].weight, HFMTree

[i].lchild,HFMTree[i].rchild,HFMTree[i].parent );

}

void HaffmanConde(HNodeType HFMTree[], HCodeType HUffCode[]) {

FILE *fptr1,*fptr2;

fptr1=fopen("HTree.txt","a");

if(fptr1==NULL)

printf("文件打开失败");

HCodeType cd;

int i,j,c,p;

for(i=0;i

{

cd.start=MAXBIT-1;

c=i;

fscanf(fptr1 ," %d%d%d%d",&HFMTree[i].weight,&HFMTree

[i].lchild,&HFMTree[i].rchild,&HFMTree[i].parent );

p=HFMTree[c].parent;

while(p!=-1)

{

if(HFMTree[p].lchild==c)

cd.bit[cd.start]=0;

else cd.bit[cd.start]=1;

cd.start--;

c=p;

p=HFMTree[c].parent;

}

for(j=cd.start+1;j

HUffCode[i].bit[j]=cd.bit[j];

HUffCode[i].start=cd.start+1;

}

fclose(fptr1);

printf("字符权值代码\n");

if((fptr2=fopen("HNode.txt","w"))!=NULL)

{

for(i=0;i

{

fprintf(fptr2,"%c ",HFMTree[i].letter);

printf("%c ",HFMTree[i].letter);

printf("%d ",HFMTree[i].weight);

for(j=HUffCode[i].start;j

fprintf(fptr2,"%d",HUffCode[i].bit[j]);

for(j=HUffCode[i].start;j

printf("%d",HUffCode[i].bit[j]);

printf("\n");

fprintf(fptr2,"\n");

}

}

else

printf("文件打开失败");

fclose(fptr2);

}

void makecode1(char s[MAXVSLUE])

{

FILE *ptr;

int i,m;

char file[20];

printf("\n输入要编码的文件名 \n");

cin>>file;

ptr=fopen(file,"r");

if(ptr==NULL)

printf("文件打开失败");

for(i=0;i

s[i]=NULL;

fgets(s,MAXVSLUE,ptr);

int n,j;

printf("输入保存密文的文件名");

cin>>file;

ptr=fopen(file,"w");

n=strlen(s);

for(i=0;i

{

for(j=0;j

if(s[i]==HNode[j].letter)

break;

for(m=HCode[j].start;m

{

fprintf(ptr,"%d",HCode[j].bit[m]);

printf("%d",HCode[j].bit[m]);

}

}

fclose(ptr);

printf("\n");

}

void makecode2(char s[MAXVSLUE])

{

char file[100];

FILE *ptr;

int n,i,j,m;

printf("输入要编码的字符串：");

scanf("%s",s);

n=strlen(s);

for(i=0;i

{

for(j=0;j

if(s[i]==HNode[j].letter)

break;

for(m=HCode[j].start;m

printf("%d",HCode[j].bit[m]);

}

printf("\n输入保存密文的文件名"); cin>>file;

ptr=fopen(file,"w");

n=strlen(s);

for(i=0;i

{

for(j=0;j

if(s[i]==HNode[j].letter)

break;

for(m=HCode[j].start;m

{

fprintf(ptr,"%d",HCode[j].bit[m]);

}

}

fclose(ptr);

printf("\n");

printf("\n");

}

void yicode1()

{

int i,c=2*N-2;

char s[MAXVSLUE];

char file[100];

for(i=0;i

s[i]=NULL;

char ch[2]={0};

FILE *ptr;

printf("输入要译码的文件名");

cin>>file;

ptr=fopen(file,"r");

if(ptr==NULL)

printf("文件打开失败");

ch[0]=fgetc(ptr);

while(ch[0]!=EOF)

{

strcat(s,ch);

ch[0]=fgetc(ptr);

}

fclose(ptr);

printf("输入保存译文的文件名");

cin>>file;

ptr=fopen(file,"w");

if(ptr==NULL)

printf("文件打开失败");

i=0;

while(s[i]!=NULL)

{

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

{

c=HNode[c].lchild;

if(HNode[c].lchild==-1 && HNode[c].rchild==

-1)

{

printf("%c",HNode[c].letter);

fprintf(ptr,"%c",HNode[c].letter);

c=2*N-2;

}

}

else if(s[i]=='1')

{

c=HNode[c].rchild;

if(HNode[c].lchild==-1 && HNode[c].rchild==

-1)

{

printf("%c",HNode[c].letter);

fprintf(ptr,"%c",HNode[c].letter);

c=2*N-2;

}

}

i++;

}

printf("译码成功, 密文在%s文件中\n",file);

fclose(ptr);

}

void yicode2()

{

char file[100];

FILE *ptr;

int i,c=2*N-2;

char s[MAXVSLUE];

for(i=0;i

s[i]=NULL;

printf("输入密文");

scanf("%s",s);

i=0;

while(s[i]!=NULL)

{

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

{

c=HNode[c].lchild;

if(HNode[c].lchild==-1 && HNode[c].rchild==

-1)

{

printf("%c",HNode[c].letter);

c=2*N-2;

}

}

else if(s[i]=='1')

哈夫曼编码译码系统实验报告,数据结构课程设计报告

v .. . .. 安徽大学 数据结构课程设计报告项目名称：哈弗曼编/译码系统的设计 与实现 姓名：鉏飞祥 学号：E21414018 专业：软件工程 完成日期 2016/7/4 计算机科学与技术学院

1 .需求分析 1.1问题描述 ?问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。 1.2基本要求 (1)输入的形式和输入值的范围； (2)输出的形式； (3)程序所能达到的功能。 1.基本要求 （1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree； （2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中； （3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中； （4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data

及其原文Textfile.txt； 2. 概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 (1)数据结构 哈夫曼树的节点 struct huff { int weight; int parent; int l; int r; }; 哈夫曼编码的存储 struct huff *hufftree; (2)程序模块 选择1到i-1中parent为0且权值最小的两个下标 void Select(struct huff *HT, int n, int &s1, int &s2) 构建哈夫曼树： void huffmancoding(struct huff *ht,int *w,int n)

哈夫曼编码译码

哈夫曼编码/译码 一、【实验内容】 【问题描述】 利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统. 【基本要求】：一个完整的系统应以下功能: (1) I. 初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存放在文件hfmTree中. (2) E. 编码(Encoding)。利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中. (3) D. 译码(Decoding)。利用已建好的哈夫曼树,对传输到达的Cod eFile中的数据代码进行译码,将译码结果存入文件TextFile中. (4) P. 印文件代码(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePri n中。 (5) T. 印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

测试数据： (1) 利用教科书例6-2中的数据调试程序。 (2) 用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”.。 字符 A B C D E F G H I J K L M 频数 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频数 57 63 15 1 48 51 80 23 8 18 1 1 6 1 二、实验目的 树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.

哈夫曼编码译码器

哈夫曼编码译码器

哈夫曼编码译码器 学院班级: 信息工程学院软件1501 指导教师: 朱俊武 小组成员: 刘洋蒋佳烨冀若含 本人学号: 151303107 报告书写: 冀若含 学生成绩:

目录 一、总体介绍·····························03-04 二、详细设计·····························04-11 三、运行测试·····························11-12 四、课设总结·····························13-13 五、附录代码·····························13-19

一、总体介绍 1.1任务概述 我们小组做了两个版本，其中一个为文件操作版，另一个为键盘操作版。两个版本都实现了哈夫曼编码/译码操做。我主要负责的是构造哈夫曼树，给出各个字符的哈夫曼编码，加密操做，整个键盘操作版系统的代码重组、编辑。开发的过程中使用了Codelite、Dev、Vc等软件。参考书籍为《数据结构》（c语言版）。 其中文件操作版的具体实现为： ○1能够实现对26个小写字母外加空格进行哈夫曼编码，并能够对一整篇文章（有小写字母和空格组成）进行加密，生成密码文件。最后根据生成的密码翻译出原文并存档。 ○2在使用程序时，使用者只需要对ToBetran文件进行原文的输入（使用小写字母或空格），加密和解密功能由程序自主来完成。 ○3程序运行的过程中会输出进行编码的26个小写字母和空格（字符型），并输出其对应的权值（整型）。还输出字符的编码及生成的密文。最后输出解密后的原文。 键盘操作版为： ○1要求从键盘输入字符集和字符的权值，大部分字符均可输入，需要各个字符的权值不能相同。 ○2利用输入的权值建立哈夫曼树，得到每个字符的前缀编码。 ○3输入字符串，程序对其进行加密。 ○4输入密文（1010101……………..）对密文进行解密。

哈夫曼编码译码问题

《数据结构》课程设计报告题目——哈夫曼编码译码问题 班级： 学号： 姓名： 时间：

一、设计目的与内容 1．设计目的 熟悉对哈夫曼编码的应用以及构造方法，熟悉对树的存储方式的应用。 2．设计内容： 任务：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一哈夫曼编/译码系统。 要求： 1）初始化：从终端输入字符集的大小n，以及n个字符和n个权值，建立哈夫曼树。 2）输出哈夫曼树，及各字符对应的编码。 3）编码：利用建好的哈夫曼树，对输入的待发送电文进行编码。同时输入原文及编码串。4）译码：利用建好的哈夫曼树，对输入的已接收电文进行译码。同时输入编码串及原文。 二、算法的基本思想 算法的主要思路是： （1）定义结构体存储赫夫曼树的结点类型 （2）定义函数strcpy(char *S1,char *S2)将字符串S2复制到S1 （3）定义函数Select(HuffmanTree HT,int t,int &s1,int &s2)在HT[1]到HT[t-1]中找出权值最小的两个S1和S2 （4）定义函数HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n)根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中 （5）定义函数InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[],int &n )初始化赫夫曼数，要求用户输入字符和相应权值 （6）定义函数Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch[])根据赫夫曼编码将用户指定的文件中的字符编成相应的编码,并将所得编码存储到用户指定文件 （7）定义函数Decoding(HuffmanTree HT, char ch[] , int n)对指定的存储由赫夫曼编码表示的信息的文件进行译码，翻译成相应的字符表示，并存储到指定文件 （8）定义函数ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[], int &n)从文件读取赫夫曼树 （9）定义主函数main()实现相应的功能 三、测试数据 首先运行程序： 请输入你要选择的功能 1.初始化 2.编码 3.译码 4.退出 1

哈夫曼编码译码系统实验报告,数据结构课程设计

安徽大学 数据结构课程设计报告项目名称：哈弗曼编/译码系统的设计 与实现 姓名：鉏飞祥 学号：E21414018 专业：软件工程 完成日期 2016/7/4 计算机科学与技术学院

1 .需求分析 1.1问题描述 ?问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。 1.2基本要求 (1) 输入的形式和输入值的范围； (2) 输出的形式； (3) 程序所能达到的功能。 1.基本要求 （1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree； （2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中； （3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data 中的代码进行解码形成原文，结果存入文件Textfile.txt中； （4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data 及其原文Textfile.txt； 2. 概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 (1)数据结构 哈夫曼树的节点 struct huff

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

沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：实现哈夫曼编码和译码器 院（系）：计算机学院 专业：计算机科学与技术 班级：24010102 学号：2012040101082 姓名：尹伟和 指导教师：徐蕾

此页为任务书

目录 1.题目分析 (1) 1.1.题目重述 (1) 1.1.1.系统功能需求分析 (1) 2.程序设计 (2) 2.1.系统功能模块说明 (2) 2.1.1.系统功能模块结构 (2) 2.1.2.系统模块功能说明 (3) 2.2.数据结构说明 (3) 2.2.1.结构体定义说明 (3) 2.2.2.哈夫曼树 (4) 2.2.3.字符-哈夫曼编码对照表 (4) 2.3.函数说明 (4) 3.算法描述 (6) 3.1.哈夫曼树的构建 (6) 3.2.字符-哈夫曼编码对照表 (6) 3.3.编码 (6) 3.4.译码 (7) 4.程序测试 (9) 4.1.字符集输入 (9) 4.2.编码测试 (10) 4.3.译码测试 (11) 参考文献 (13) 附录（程序清单） (14)

沈阳航空航天大学课程设计报告 1.题目分析 1.1.题目重述 本次课程设计的目标是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码器需要根据用户输入的字符集及相应字符出现的频率，对字符集所包含的字符进行哈夫曼编码。同时，作为编码器需要其对用户提供的明文字符串进行编码，使明文字符串变为二进制密文；作为译码器需要对用户提供的二进制密文进行译码，使二进制密文变为字符明文。 1.1.1.系统功能需求分析 通过对课程设计的题目分析，可以得出哈夫曼编码和译码器的功能需求，需求如下： 1)读取用户输入的字符集和相应字符出现的频率； 2)根据用户输入构建哈夫曼树； 3)根据哈夫曼树构建字符-哈夫曼编码对照表； 4)根据字符-哈夫曼编码对照表对明文字符串进行编码； 5)根据哈夫曼树对二进制密文进行译码。

哈夫曼编码资料

哈夫曼编码译码系统 一、需求分析 1、程序的基本功能： ①构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符以及n个对应的权 值，建立哈夫曼树；利用已将建好的哈弗曼树求每个叶结点的哈夫曼编码，并保存。 ②编码：利用已构造的哈弗曼编码对“明文”文件中的正文进行编码，然后将结果存 入“密文”文件中。 ③译码：将“密文”文件中的0、1代码序列进行译码。 ④打印“密文”文件：将文件以紧凑格式显示在终端上，同时，将此字符形式的编码 保存。 ⑤打印哈夫曼树:将已在内存中的哈夫曼以凹入表形式显示在终端上。 2、输入输出要求： ①从键盘接收字符集大小n、以及n个字符和n个权值； ②构造哈夫曼树：将HFMTree数组中的各个位置的各个域都添上相关的值，并将结构 体数组存入文件HTree.txt中。 ③打印哈夫曼树：从HFMTree数组读取相关的结点信息，以凹入表方式将各个结点画 出来； ④构造哈夫曼编码：先从文件HTree.txt中读入相关的字符信息进行哈夫曼编码，将字 符与其对应的编码存入文件HNode.txt中； ⑤编码：利用已构造的哈夫曼树对文件进行编码，打印结果，并将结果存入新建文件 中； ⑥译码：将密文文件中的内容利用HNode.txt中建立的编码规则进行翻译，打印结果， 并将结果存入新建文件中。 3、测试数据： 输入叶子结点个数为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，且字符集与权值集合一一对应。 二、概要设计 1、抽象数据类型的定义： ①采用静态链表作为哈夫曼树的存储结构； ②求哈夫曼编码时使用一维数组HCode作为哈夫曼编码信息的存储。 2、主模块的流程及各子模块的主要功能： ①int main() { 主菜单； swich语句结构选择； return 0; } ②in_park() { 输入车牌号； 若停车场已满，停入便道中，否则停入停车场； } ③output()

哈夫曼编码和译码系统

通达学院 算法与数据结构程序设计 题目：哈夫曼编码和译码系统 专业 学生姓名 班级学号 指导教师 指导单位 日期

教师评语 同学出勤率(满勤、较高、一般，较低)，学习态度(端正、较端正、一般、较差)，程序设计基础（好、较好、一般、较差），演示程序(已经、没有)达到了基本要求，算法设计（好、较好、一般），界面友好程度（好、较好、一般），答辩过程中回答问题（准确、较准确、错误率较高），撰写报告格式(规范、一般)、内容（丰满、简单）、表述(清晰、一般、不清楚)，（圆满、较好、基本)完成了课题任务。 教师签名： 年月日 成绩评定 备注

一、题目要求： 题 目 ：哈夫曼编码和译码系统 基本要求： (1) 能输入字符集和各字符频度建立哈夫曼树； (2) 产生各字符的哈夫曼编码，并进行解码。 提高要求： (1) 能设计出简捷易操作的窗口界面； (2) 编码和译码存储在文件中。 二、需求分析： 2.1基本思想 根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是: (1) 初始化:由给定的n 个权值{w 1, w 2,…, w n }构造n 棵只有一个根结点的二叉树,从而得到一个二叉树集合F={ T 1,T 2,…,T n }; (2) 选取与合并:在F 中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和; (3) 删除与加入:在F 中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到F 中; (4) 重复(2)、(3)两步,当集合F 中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树. 2.2存储结构 在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为2，根据二叉树的性质可知,具有n 个叶子结点的哈夫曼树共有2n-1个结点,其中有n-1个非叶子结点,它们是在n-1次的合并过程中生成的.为了便于选取根结点权值最小的二叉树以及合并操作,设置一个数组HuffmanNode[2n-1]保存哈夫曼树中各结点的信息,数组元素的结点结构如图所示. 图 哈夫曼树的结点结构 其中: weight parent lchild rchild i nf

哈夫曼编码算法实现完整版

实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include #include #include #include typedef struct{ char data; int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char * * HuffmanCode; void Select(HuffmanTree &HT,int n,int m) {HuffmanTree p=HT; int tmp; for(int j=n+1;j<=m;j++) {int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x<=j-1;x++) { if(p[x].parent==0&&p[x].weights2) //将选出的两个节点中的序号较小的始终赋给s1 { tmp=s1; s1=s2; s2=tmp;} p[s1].parent=j;

(完整word版)哈夫曼编码和译码的设计与实现

算法与数据结构课程设计 哈夫曼编码和译码的设计与实现 1.问题描述 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼码的编/译码系统。

2.基本要求 a.编/译码系统应具有以下功能： （1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 （2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将 结果存入文件CodeFile中。 （3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 （4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin 中。 （5）T：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式或广义表）显示在终端上，同时将此字符形 式的哈夫曼树写入文件TreePrint中。 b.测试数据 （1）利用下面这道题中的数据调试程序。 某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。 （2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。 字符空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度57 63 15 1 48 51 80 23 8 18 1 16 1 3．需求分析 3.1程序的基本功能 本程序可以对任何大小的字符型文件进行Huffman编码，生成一个编码文件。并可以在程序运行结束后的任意时间对它解码还原生成字符文件。即：先对一条电文进行输入，并实现Huffman编码，然后对Huffman编码生成的代码串进行译码，最后输出电文数字

哈夫曼编码译码器---课程设计报告

目录 目录 (2) 1课程设计的目的和意义 (3) 2需求分析 (4) 3概要设计 (4) 4详细设计 (8) ￥ 5调试分析和测试结果 (11) 6总结 (12) 7致谢 (13) 8附录 (13) 参考文献 (20) .

| ; 1 课程设计目的与意义 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。 作为计算机专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。 （ 在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们

可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。 2 需求分析 课题：哈夫曼编码译码器 ) 问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。问题补充：1. 从硬盘的一个文件里读出一段英语文章； 2. 统计这篇文章中的每个字符出现的次数； 3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储 结构的初态和终态进行输出； 4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破 译。 具体介绍：在本课题中，我们在硬盘中预先建立一个文档，在里面编辑一篇文章。然后运行程序，调用函数读出该文章，显示在界面；再调用函数对该文章的字符种类进行统计，并对每个字符的出现次数进行统计，并且在界面上显示；然后以每个字符出现次数作为权值，调用函数构建哈夫曼树；并调用函数将哈夫曼的存储结构的初态和终态进行输出。然后调用函数对哈夫曼树进行编码，调用函数将编码写入文件；再调用对编码进行译码，再输出至界面。至此，整个工作就完成了 3 概要设计。

哈夫曼编码

《数据结构》实验报告4 年级2012级学号201202024061 姓名王冠文成绩 专业计算机科学与技术实验地点电教楼303 指导教师杨丽 实验日期月日 实验项目哈夫曼编码 一、实验目的 根据最优二叉树构造哈夫曼编码利用哈夫曼树很容易求出给定字符集及其概率分布的最优前缀码。哈夫曼编码正是一种应用非常广泛，本次试验通过设计一个算法，体会和掌握哈夫曼编码要点。 二、实验问题描述 已知每一个字符出现的频率，构造哈夫曼树，并设计哈夫曼编码。 三、实验步骤 1、实验问题分 给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子T[i]为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码。 2、构思算法 3、功能函数设计 4、编写程序并运行调试 四、实验结果（程序）及分析 #include #include #include #include #define MAX_CHAR_KINDS 128 #define MAX_NUM 1000 typedef struct TreeNode { int weight; char data; char bin; struct TreeNode *parent; struct TreeNode *lChild, *rChild; } TreeNode; typedef struct { char data; char code[MAX_CHAR_KINDS]; } Code; void InverseStr(char *str) {

哈夫曼编码译码器实验报告免费

哈夫曼编码译码器实验报告(免费)

————————————————————————————————作者：————————————————————————————————日期：

问题解析与解题方法 问题分析： 设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。 （1）从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）； （2）统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；（3）根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码； （4）将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf）（5）用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；（6）进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。 根据上述过程可以知道该编码译码器的关键在于字符统计和哈夫曼树的创建以及解码。 哈夫曼树的理论创建过程如下： 一、构成初始集合 对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合 F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结 点，它的左右子树均为空。 二、选取左右子树 在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二 叉树的根结点的权值为其左右子树的根结点的权值之和。 三、删除左右子树 从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步， 重复二和三两步，直到集合F中只有一棵二叉树为止。 因此，有如下分析： 1.我们需要一个功能函数对ASCII码的初始化并需要一个数组来保存它们； 2.定义代表森林的数组，在创建哈夫曼树的过程当中保存被选中的字符，即给定报文 中出现的字符,模拟哈夫曼树选取和删除左右子树的过程； 3.自底而上地创建哈夫曼树，保存根的地址和每个叶节点的地址，即字符的地址，然 后自底而上检索，首尾对换调整为哈夫曼树实现哈弗曼编码； 4.从哈弗曼编码文件当中读入字符，根据当前字符为0或者1的状况访问左子树或者 右孩子，实现解码； 5.使用文件读写操作哈夫曼编码和解码结果的写入； 解题方法： 结构体、数组、类的定义： 1.定义结构体类型的signode 作为哈夫曼树的节点，定义结构体类型的hufnode 作为

0023算法笔记——【贪心算法】哈夫曼编码问题

0023算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。

译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为d T(c)。d T(c)也是字符c的前缀码长。则平均码长定义为：

哈夫曼编码译码系统

《数据结构》课程设计——赫夫曼编码/译码器设计 指导教师：孙树森、周维达 班级：09数媒（2）班 学号：E09700227 姓名：曾焕凯

数据结构课程设计报告书 一、实验目的 1、提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法。 2、熟悉掌握一门计算机语言，可以进行数据算法的设计。 二、实验原理 1、哈夫曼树的定义： 假设有n 个权值，试构造一颗有n 个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树； 2、哈夫曼树的构造： weight 为输入的频率数组，把其中的值赋给依次建立的HT Node 对象中的data 属性，即每一个HT Node 对应一个输入的频率。然后根据data 属性按从小到大顺序排序，每次从data 取出两个最小和此次小的HT Node，将他们的data 相加，构造出新的HTNode 作为他们的父节点，指针parent，leftchild，rightchild 赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent 为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1 或0，这样，每个频率都会有一个01 编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。 三、实验步骤

先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码。 然后读入要编码的文件，编码后存入另一个文件； 接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。 具体步骤： 1.初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树； 2.根据符号概率的大小按由大到小顺序对符号进行排序； 3.把概率最小的两个符号组成一个节点； 4.重复步骤2. 3 ，直到概率和为1； 5.从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”； 6.从根节点开始，对符号进行编码； 7.译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。 四、实验结果与分析 哈夫曼编码是动态变长编码，临时建立概率统计表和编码树。概率小的码比较长，概率小的码比较长。概率大的码短，这样把一篇文件编码后，就会压缩许多。 从树的角度看，哈夫曼编码方式是尽量把短码都利用上。首先，把一阶节点全都用上，如果码字不够时，然后，再从某个节点伸出若干枝，引出二阶节点作为码字，以此类推，显然所得码长最短，再根据建立的概率统计表合理分布和放置，使其平均码长最短就可以得到最佳码。 实验截图:

哈夫曼编码译码系统课程设计实验报告(含源代码C++_C语言)

目录 摘要………………………………………………………………………..………………II Abstract …………………………………………………………………………..………... II 第一章课题描述 (1) 1.1 问题描述 (1) 1.2 需求分析…………………………………………………..…………………………… 1 1.3 程序设计目标…………………………………………………………………………… 第二章设计简介及设计方案论述 (2) 2.1 设计简介 (2) 2.2 设计方案论述 (2) 2.3 概要设计 (2) 第三章详细设计 (4) 3.1 哈夫曼树 (4) 3.2哈夫曼算 法 (4) 3.2.1基本思 想 (4) 3.2.2存储结 构 (4)

3.3 哈夫曼编码 (5) 3.4 文件I/O 流 (6) 3.4.1 文件流 (6) 3.4.2 文件的打开与关闭 (7) 3.4.3 文件的读写 (7) 3..5 C语言文件处理方式…………………………………………………………………… 第四章设计结果及分析 (8) 4.1 设计系统功能 (8) 4.2 进行系统测试 (8) 总结 (13) 致谢 (14) 参考文献 (15) 附录主要程序代码 (16) 摘要 在这个信息高速发展的时代，每时每刻都在进行着大量信息的传递，到处都离不开信息，它贯穿在人们日常的生活生产之中，对人们的影响日趋扩大,而利用哈夫曼编码

进行通信则可以大大提高信道利用率，缩短信息传输时间，降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润，这也是信息时代发展的趋势所在。本课程设计的目的是使学生学会分析待加工处理数据的特性，以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。学生在学习数据结构和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和创造性的思维方法，增强分析问题和解决问题的能力。此次设计的哈夫曼编码译码系统，实现对给定报文的编码和译码，并且任意输入报文可以实现频数的统计,建立哈夫曼树以及编码译码的功能。这是一个拥有完备功能的系统程序，对将所学到的知识运用到实践中,具有很好的学习和研究价值. 关键词：信息；通讯；编码；译码；程序 Abstract This is a date that information speeding highly development and transmit

哈夫曼编码译码器数据结构C语言

一、需求分析 目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二级制的字符组成的字符串。例如，假设需传送的电文为“ABACCDA ”，它只有4种字符，只需两个字符的串，便可以分辨。假设A 、B 、C 、D 、的编码分别为00,01,10和11，则上述7个字符的电文便为“00010010101100”，总长14位，对方接受时，可按二位一分进行译码。 当然，在传送电文时，希望总长尽可能地短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。如果设计A 、B 、C 、D 的编码分别为0,00,1,01，则上述7个字符的电文可转换成总长为9的字符串“000011010”。但是，这样的电文无法翻译，例如传送过去的字符串中前4个字符的字串“0000”就可以有很多种译法，或是“AAAA ”或者“BB ”，或者“ABA ”等。因此，若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。 然而，如何进行前缀编码就是利用哈夫曼树来做，也就有了现在的哈夫曼编码和译码。 二、概要设计 利用哈夫曼树编/译码 （一）、建立哈夫曼树 （二）、对哈夫曼树进行编码 （三）、输出对应字符的编码 （四）、译码过程 主要代码实现： struct code //结构体的定义 { char a; int w; int parent; int lchild; int rchild; }; void creation(code *p,int n,int m); //建立哈夫曼树 void coding(code *p,int n); //编码 void display(code *p,int n,int m); //输出函数 void translate(char **hc,code *p,int n); //译码 三、 详细设计 （一）、建立哈夫曼树 a b c d 1 2 3 4 5 * * * 6 7 a b * c * a b * c * d * 序号： 字符： 权值： 1 2 3 4 3 6 10 a b * 1 2 1 2 3 3 1 2 3 3 6 4 10 3 6 图3-1 图3-2 图3-3

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

数据结构实验报告 ―― 实验五简单哈夫曼编/ 译码的设计与实现本实验的目的是通过对简单哈夫曼编/ 译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现。 一、【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/ 码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n ，以及n 个字符和n 个权值，建立哈夫曼树，并将它存于文件nodedata.dat 中。 2 、编码。 利用已建好的哈夫曼树（如不在内存，则从文件nodedata.dat 中读入），对文件中的正文进行编码，然后将结果存入文件code.dat 中。 3 、译码。利用已建好的哈夫曼树将文件code.dat 中的代码进行译码，结果存入文件textfile.dat 中。 4、打印编码规则。 即字符与编码的一一对应关系。 二、【数据结构设计】 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组HuffNode 保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n 个叶子结点的哈夫曼树共有2n-1 个结点，所以数组HuffNode 的大小设置为2n-1 ，描述结点的数据类型为：typedef struct { int weight;// 结点权值 int parent; int lchild; int rchild; char inf; }HNodeType; 2 、求哈夫曼编码时使用一维结构数组HuffCode 作为哈夫曼编码信息的存储。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0 、1 序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： #define MAXBIT 10 typedef struct

数据结构课程设计哈夫曼编码译码器.doc

题目一：哈夫曼编码与译码 一、任务 设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。 要求： 1) 将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) ； 2) 初始化：键盘输入字符集统计字符权值、自定义26个字符和26个权值、统计文件中一篇英文文章中26个字母，建立哈夫曼树； 3) 编码：利用建好的哈夫曼树生成哈夫曼编码； 4) 输出编码（首先实现屏幕输出，然后实现文件输出）； 5）译码（键盘接收编码进行译码、文件读入编码进行译码）； 6) 界面优化设计。 二、流程图 主菜单 1.建立字符权值 2.建立并输出 哈夫曼树 3.建立并查看 哈弗曼编码 4.编码与译码0.退出系统 1.从键盘输入字符集统计 2.从文件读入字 符集统计权值 3.自定义字符及 权值 0.返回上级菜单输出哈夫曼树并保存 至文件“哈夫曼树。t xt” 输出哈夫曼编码并保存至文 件“哈夫曼编码。txt 1.编码 2.译码0.返回上级 菜单 1.从键盘输入字 符集进行编码 2.从文件读入字 符集进行编码 1.从键盘输入编 码进行译码 2.从文件读入编 码进行译码 0.返回上级菜单0.返回上级菜单

三、代码分解 //头文件 #include #include #include #include #define N 1000 #define M 2*N-1 #define MAXcode 6000 //函数声明 void count(CHar &ch,HTNode ht[]); void editHCode(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); //编码函数 void printyima(HTNode ht[],HCode hcd[],int n,char bianma[]); //译码函数void creatHT(HTNode ht[],int n); void CreateHCode (HTNode ht[],HCode hcd[],int n); void DispHCode(HTNode ht[],HCode hcd[],int n); void input_key(CHar &ch); void input_file(CHar &ch); void input_cw(HTNode ht[]); void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); void bianma2(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]); void yima2(HTNode ht[],HCode hcd[],int n,char bianma[]); void creat_cw(); void bianmacaidan(); void yimacaidan(); void bianmayima(); int caidan(); //结构体 typedef struct {