哈夫曼树上机实验报告

霍夫曼树

实验目的:

掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。

基本要求:

熟练掌握树的操作。

程序实现:

程序第一遍统计原数据中各字符出现的频率,利用得到的频率值创建哈夫曼树,并把树的信息保存起来,以便解压时创建同样的哈夫曼树进行解压;第二遍,根据第一遍扫描得到的哈夫曼树进行编码,并把编码后的码字存储。

要点分析:

题目中涉及的主要知识点:

1、本程序参考霍夫曼算法(由给定的权值构造赫夫曼树):

(1)由给定的n个权值{w0, w1, w2, „, wn-1},构造具有n棵二叉树的集合F ={T0, T1, T2, „, Tn-1},其中每一棵二叉树Ti只有一个带有权值wi的根结点,其左、右子树均为空。

(2)重复以下步骤, 直到F中仅剩下一棵树为止:① 在F中选取两

棵根结点的权值最小的二叉树, 做为左、右子树构造一棵 新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。② 在F中删去这两棵二叉树。③ 把新的二叉树加入F。

2、用构造赫夫曼树以完成赫夫曼编码:把d1,d2,„, dn 作为叶子结

点,把w1,w2,„,wn作为叶子结点 的权,构造赫夫曼树。在赫夫曼树中结点的左分支赋0,右 分支赋1,从根结点到叶子结点的路径上的数字拼接起来就 是这个叶子结点字符的编码。

3、译码的过程是分解电文中的字符串,从根出发,按字符‘0’或‘1’确定找左孩子或右孩子,直至叶子节点,便求得该子串相应的字符。 心得体会:

通过本次实验,我熟练掌握了结构体、指针及二叉树的生成、遍历等操作,掌握了霍夫曼编码和译码的原理,熟练掌握树的操作,尤其是对霍夫曼树有了更深刻的理解。同时,在编写代码的过程中方,对字符串的相关知识进行了回顾。

代码

#include

#include

#include

typedef struct

{

int weight;

int parent,lchild,rchild;

int sign;

}HTNode,*HuffmanTree;

typedef char * *HuffmanCode;

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char *s); void select(HuffmanTree &HT,int i,int &s1,int &s2);

void creatHuffmanTree(int *w,char *s,char *r);

void pr(HuffmanCode &HC,char r[],char s,char a[]);

void HuffmanYM(HuffmanCode &HC,char r[],char a[],int n,HuffmanTree &HT); void HuffmanPass(HuffmanCode &HC,char r[],int n,HuffmanTree &HT);

int main()

{

char s[100];

char r[100];

char a[100]="a";

int w[100];

int n,p;

HuffmanTree HT;

HuffmanCode HC;

printf("请输入进行编码的字符串\n");

scanf("%s",s);

p=strlen(s);

if(p!=1)creatHuffmanTree(w,s,r);

printf("进行编码......\n");

if(p!=1)

HuffmanCoding(HT,HC,w,strlen(r)-1,r);

else printf("%c的霍夫曼编码是: %c\n",s[0],'0');

printf("霍夫曼码序列为:\n");

if(p!=1)

for(int i=0;i

pr(HC,r,s[i],a);

printf("\n");

n=strlen(r)-1;

if(p==1)printf("0\n");

printf("霍夫曼编码进行译码:\n");

if(p==1)

printf("%c",s[0]);

else HuffmanYM(HC,r,a,n,HT);

printf("\n");

printf("先序遍历输出叶子节点\n");

if(p==1)

{

printf("%c\n",s[0]);

}

else HuffmanPass(HC,r,n,HT);

return 0;

}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w[],int n,char s[]) {

int s1,s2,f,c;

int m,i,l;

int start;

char cd[101];

if(n

l=strlen(s);

m=2*n-1;

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

HT[0].weight=10000;

for (i=1;i

{

HT[i].weight=w[i-1];

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

HT[i].sign=0;

}

for(;i

{

HT[i].weight=0;

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

HT[i].sign=0;

}

for(i=n+1;i

{

select(HT,i-1,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;

}

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

cd[n-1]='\0';

for(i=1;i

{

start=n;

c=i;

for(f=HT[i].parent;f!=0;f=HT[f].parent)

{

if(HT[f].lchild==c)

{

start--;

cd[start]='0';

}

else

{

start--;

cd[start]='1';

}

c=f;

}

HC[i]=(char *)malloc((n-start)*sizeof(char));

for(int a=0;a

{

HC[i][a]=cd[start+a];

}

HC[i][a]='\0';

printf("%c的霍夫曼编码是: %s\n",s[i],HC[i]);

}

}

void select(HuffmanTree &HT,int i,int &s1,int &s2)

{

s1=0;

s2=0;

for(int j=1;j

{

if(HT[j].parent==0)

if(HT[j].weight

s1=j;

else continue;

}

else continue;

}

for(j=1;j

{

if(j==s1)continue;

else

if(HT[j].parent==0)

{

if(HT[j].weight

s2=j;

else continue;

}

else continue;

}

}

void creatHuffmanTree(int w[],char s[],char r[])

{

int g=1;

int q=0;

r[0]='0';

r[1]=s[0];

w[0]=1;

for(int e=1;e

{

for(int k=1;k

{

if(r[k]==s[e])

{

w[k-1]++;

q=1;

}

else continue;

}

if(q==0)

{

r[++g]=s[e];

w[g-1]=1;

q=0;

}

r[++g]='\0';

}

void pr(HuffmanCode &HC,char r[],char s,char a[])

{

for(int i=1;i

{

if(r[i]==s)

{

printf("%s",HC[i]);

strcat(a,HC[i]);

}

else continue;

}

}

void HuffmanYM(HuffmanCode &HC,char r[],char a[],int n,HuffmanTree &HT) {

int e=strlen(a);

int k=0;

int f=2*n-1;

char b[10]="1";

for(int j=1;j

{

if(HT[f].lchild!=0||HT[f].rchild!=0)

{

b[k]=a[j];

k++;

if(a[j]=='1')

f=HT[f].rchild;

else if(a[j]=='0')

f=HT[f].lchild;

}

else

{

for(int s=1;s

{

if(strcmp(HC[s],b)==0)

{

printf("%c",r[s]);

break;

}

else continue;

}

for(int u=0;u

b[u]='\0';

k=0;

f=2*n-1;

j=j-1;

}

}

}

void HuffmanPass(HuffmanCode &HC,char r[],int n,HuffmanTree &HT) {

int f,k=0;

char b[10]="a";

f=2*n-1;

HT[f].sign=0;

if(HT[f].lchild==0&&HT[f].rchild==0)

return;

do

{

if(HT[f].lchild==0&&HT[f].rchild==0)

{

for(int s=1;s

{

if(strcmp(HC[s],b)==0)

{

printf("%c",r[s]);

break;

}

else continue;

}

b[k--]='\0';

HT[f].sign=2;

f=HT[f].parent;

}

if(HT[f].sign==0)

{

b[k]='0';

HT[f].sign++;

f=HT[f].lchild;

k++;

}

else

if(HT[f].sign==1)

{

b[k]='1';

HT[f].sign++;

f=HT[f].rchild; k++;

}

else

if(HT[f].sign==2) {

f=HT[f].parent; b[k--]='\0'; }

}while(f!=0);

printf("%\n");

}


相关内容

  • 数据结构课程设计题目

    数据结构课程设计题目 以下8个题目任选其一. 1.排序算法比较 利用随机函数产生30000个随机整数,利用插入排序.起泡排序.选择排序.快速排序.堆排序.归并排序等排序方法进行排序,并且 (1)统计每一种排序上机所花费的时间. (2)统计在 ...


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

    <数据结构> 课程设计报告 题目:哈夫曼编码的实现 专业:软件工程 班级:软件0901 学号:091203111 姓名:管 向 华 任课教师:殷 新 春 2010 年 12 月 26 日 目 录 一.问题描述 二.需求分析 三. ...


  • 数据结构教学大纲

    数据结构教学大纲 (56学时) 一.课程性质.适用专业及层次 本课程是我院计算机专业的一门综合性的专业基础课.主要介绍如何合理地组织数据.有效地存储和处理数据,正确地设计算法以及对算法的分析和评价.通过本课程的学习,使学生深透地理解数据结构 ...


  • [数据结构]课程教学大纲

    <数据结构>课程教学大纲--2012版 一.课程基本信息 课程名称:数据结构 英文名称:Data Structure 课程编码: 11107C/11207C 课程类别:专业主干课 总学时: 64学时(含实验16学时) 总学分: ...


  • 2015课程设计题目

    题目:以下21个题目任选其一,标明限选1人的题目只能有一个人选做,未特别标注的题目可以2个人选同一题目,但是要求题目相同的同学独立完成自己选作的题目. 1. Joseph环(限选1人) [问题描述] 编号是1,2,„„,n的n个人按照顺时针 ...


  • 多媒体技术及应用参考答案

    参考答案 第1章 一.填空题 1. JPEG多灰度静态图像数字压缩编码 MPEG运动图像压缩标准 CCITT H.261 64kbps视像编码方式 2. 主机和多媒体部件 3. 视频叠加卡 视频转换卡 视频采集卡 图像加速卡 压缩/解压卡 ...


  • 哈夫曼编码实验报告

    哈夫曼编码器实验报告 学院:计算机学院 班级:计科 姓名:王宇宏 学号: 0801班 04081027(27) 一.实验目的 练习树和哈夫曼树的有关操作,和各个算法程序,理解哈夫曼树的编码和译码 二.实验环境 Microsoft visua ...


  • 图像格式转换实验报告

    实验1 图像格式转换实验报告 学 号: 姓 班 级: 一.实验目的 掌握两种以上图像的格式,重点掌握BMP 图像格式. 二.实验原理: 1.JPEG 文件的解码过程. ①.读入文件的相关信息 按照上述的JPEG 文件数据存储方式,把要解码的 ...


  • C语言-哈夫曼编码实验报告

    福 建 工 程 学 院 课程设计 课 程: 数据结构 题 目: 哈夫曼编码和译码 专 业: 信息管理信息系统 班 级: 座 号: 15号 姓 名: 林左权 2011年 6月 27日 实验题目:哈夫曼编码和译码 一.要解决的问题 利用哈夫曼编 ...