当前位置：文档之家 › Huffman编码与译码-数据结构设计性实验

Huffman编码与译码-数据结构设计性实验

  • 格式：doc
  • 大小：184.00 KB
  • 文档页数：10

数据结构设计性实验Huffman编码与译码学号2009120302 28姓名张德武班级信息092设计性实验—Huffman 编码与译码一．实验目的：在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman 树的建立方法，Huffman 编码的方法，进而设计出Huffman 译码算法，并编程实现。

二、实验要求：在6学时以内，制作出能够实现基于26个英文字母的任意字符串的编译码。

写出技术工作报告并附源程序。

三．实验内容及任务：1．设字符集为26个英文字母，其出现频度如下表所示。

2．建Huffman 树； 3．利用所建Huffman 树对任一字符串文件进行编码——即设计一个Huffman 编码器；4．对任一字符串文件的编码进行译码——即设计一个Huffman 译码器。

实现步骤：1．数据存储结构设计； 2．操作模块设计； 3．建树算法设计； 4．编码器设计；5． 译码器设计；四． 算法设计1． 数据结构霍夫曼树的节点结构 typedef struct {51 48 1 15 63 57 20 32 5 1频度z y x w v u t 字符11611882380频度p 21 f q15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符int weight;int flag;int parent;int leftChild;int rightChild;} HaffNode;霍夫曼编码的结构typedef struct {unsigned int bit[MaxN];int start;int weight;}Code;2.设计构造霍夫曼树的算法：void Haffman(int weight[],int n,HaffNode haffTree[]){int i,j,m1,m2,x1,x2;for(i=0;i<2*n-1;i++){if(i<n)haffTree[i].weight=weight[i];elsehaffTree[i].weight=0;haffTree[i].parent=-1;haffTree[i].flag=0;haffTree[i].leftChild=-1;haffTree[i].rightChild=-1;}for(i=0;i<n-1;i++){m1=m2=MaxValue;x1=x2=0;for(j=0;j<n+i;j++){if(haffTree[j].weight<m1&&haffTree[j].flag==0){m2=m1;x2=x1;m1=haffTree[j].weight;x1=j;}else if(haffTree[j].weight<m2&&haffTree[j].flag==0){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;}}3.设计编码的算法：void HaffCode(HaffNode haffTree[],int n,Code haffCode[]) {Code *cd=(Code *)malloc(sizeof(Code));int i,j,child,parent;for(i=0;i<n;i++){cd->start=n-1;cd->weight=haffTree[i].weight;child=i;parent=haffTree[child].parent;while(parent!=-1){if(haffTree[parent].leftChild==child)cd->bit[cd->start]=0;elsecd->bit[cd->start]=1;cd->start--;child=parent;parent=haffTree[child].parent;}for(j=cd->start+1;j<n;j++)haffCode[i].bit[j]=cd->bit[j];haffCode[i].start=cd->start+1;haffCode[i].weight=cd->weight;}}以上算法都包含在haffman.h的头文件中4主函数的设计#include <stdio.h>#include <stdlib.h>#define MaxValue 10000#define MaxBit 10#define MaxN 100#include "haffMan.h"void main(){int i,j,k,n=27;chars[]={'','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s',' t','u','v','w','x','y','z'};intweight[]={187,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,13 ,1,16,1};HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n+1));Code *myHaffCode=(Code *)malloc(sizeof(Code)*n);if(n>MaxN){printf("给出的n越界,修改MaxN");exit(0);}Haffman(weight,n,myHaffTree);HaffCode(myHaffTree,n,myHaffCode);for(i=0;i<n;i++){printf("字符是%c 权数=%d 霍夫曼编码= ",s[i],myHaffCode[i].weight);for(j=myHaffCode[i].start;j<n;j++)printf("%d",myHaffCode[i].bit[j]);printf("\n");}}实验结果：实验总结：通过本次实验首先学习了霍夫曼树及其编码，接着分析写出了建立霍夫曼树和计算霍夫曼编码算法的代码，在huffman编码当中虽出现许多错误但通过了进一步的学习都可以学习改正,基本上可以实现Huffman编码算法的实现与编程应用实验代码#include <stdlib.h>#include <iostream.h>#include <stdio.h>#include <string.h>#define OVERFLOW -1typedef struct{char letter;float weight;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char * *HuffmanCode;void Select(HuffmanTree &HT,int i,int &s1,int &s2) {int j, k;for(k = 1; k < i; k++){if(HT[k].parent != NULL)continue;s1 = k;break;}for(j = 1; j < i; j++){if(HT[j].parent != NULL)continue;if(HT[j].weight < HT[s1].weight)s1 = j;}for(k = 1; k <= i; k++){if(HT[k].parent != NULL || k == s1)continue;s2 = k;break;}for(j = 1; j < i; j++){if(HT[j].parent != NULL)continue;if(HT[j].weight <= HT[s2].weight && j != s1)s2 = j;}}void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *zi,float *w,int n) {HuffmanTree p;int m,i,s1,s2,f,r;int Istart = 1;char *cd;if(n <= 1)return;m = 2*n-1;if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))exit(OVERFLOW);for(p=HT+1,i=1;i<=n;++i,++zi,++p,++w){p->parent = NULL;p->letter = *zi;p->lchild = NULL;p->rchild = NULL;p->weight = *w;}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);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=(char*)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;++i){Istart = n - 1;for(r= i, f = HT[i].parent; f != 0; r= f, f = HT[f].parent)if(HT[f].lchild == r)cd[--Istart] = '0';elsecd[--Istart] = '1';HC[i] = (char *)malloc((n - Istart) * sizeof(char));strcpy(HC[i], &cd[Istart]);}free(cd);}void main(){HuffmanTree HT;HuffmanCode HC;int i,j,yu;char c[100];charzi[27]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R' ,'S','T','U','V','W','X','Y','Z',' '};float w[27]={8.19 ,1.47 ,3.83 , 3.91 , 12.25 , 2.26 , 1.71, 4.57 , 7.10 , 0.14 ,0.41 , 3.77 ,3.34 ,7.06, 7.26 , 2.89 , 0.09 , 6.85 , 6.36 ,9.41, 2.58 ,1.09 ,1.59 , 0.21 , 1.58 ,0.08 ,9.11};HuffmanCoding(HT,HC,zi,w,29);cout<<endl;cout<<"char weight huffmancode "<<endl;for(i=1;i<=27;i++)cout<<HT[i].letter<<" "<<HT[i].weight<<" "<<HC[i]<<endl; printf("please input the text:");gets(c);printf("The code is:");for(i=0; i<strlen(c); i++){if(c[i]!=' ')printf("%s",HC[(c[i] - 'A' + 1)]); elseprintf("%s",HC[27]);}cout<<endl;cout<<"Enter the code:";cin>>c;j=strlen(c);yu=57;i=1;cout<<"The text is:";while(i <= j){while(HT[yu].lchild != 0){if(c[i-1] == '0'){yu = HT[yu].lchild;i++;continue;}if(c[i-1]== '1'){yu=HT[yu].rchild;i++;continue;}}cout<<HT[yu].letter;yu = 57;}cout<<endl;}。

合集下载

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

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

问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。

对于双工通信（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试设计一个哈夫曼编码系统。

基本要求：(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，且权值最小的两个结点）函数查找构造哈夫曼树中的各个子树的结点，直到所有这种结点全部用完，即一颗哈夫曼树即构造完成。

数据结构实验实验报告Huffman赫夫曼编码及应用

数据结构实验实验报告Huffman赫夫曼编码及应用

实验报告课程名称：数据结构实验名称：赫夫曼编码及应用院（系）：计算机与通信工程学院专业班级：计算机科学与技术姓名：学号：指导教师：2020 年 5 月12 日一、实验目的掌握赫夫曼树和赫夫曼编码的基本思想和算法的程序实现。

二、实验内容及要求1、任务描述a.提取原始文件中的数据（包括中文、英文或其他字符），根据数据出现的频率为权重，b.构建Huffman编码表；c.根据Huffman编码表对原始文件进行加密，得到加密文件并保存到硬盘上；d.将加密文件进行解密，得到解码文件并保存点硬盘上；e.比对原始文件和解码文件的一致性，得出是否一致的结论。

2、主要数据类型与变量a.对Huffman树采用双亲孩子表示法，便于在加密与解密时的操作。

typedef struct Huffman* HuffmanTree;struct Huffman{unsigned int weight; //权值unsigned int p, l, r;//双亲，左右孩子};b．对文本中出现的所有字符用链表进行存储。

typedef struct statistics* List;struct statistics {char str; //存储此字符int Frequency; //出现的频率（次数）string FinalNum; //Huffman编码struct statistics* Next;};3、算法或程序模块对读取到的文本进行逐字符遍历，统计每个字符出现的次数，并记录在创建的链表中。

借助Huffman树结构，生成结构数组，先存储在文本中出现的所有字符以及它们出现的频率（即权值），当作树的叶子节点。

再根据叶子节点生成它们的双亲节点，同样存入Huffman树中。

在完成对Huffman树的创建与存储之后，根据树节点的双亲节点域以及孩子节点域，生成每个字符的Huffman编码，并存入该字符所在链表节点的FinalNum域。

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

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

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)对原文进行编码：void code(char *c)根据报文找到原文：void decoding(char *zifu)3. 详细设计核心技术分析：1：构建哈夫曼树及生成哈夫曼编码：根据每个字符权值不同，根据最优二叉树的构建方法，递归生成哈夫曼树，并且用数组存放哈夫曼树。

数据结构哈夫曼树编码及译码的实现实验报告

数据结构哈夫曼树编码及译码的实现实验报告

实验：哈夫曼树编码及译码的实现一．实验题目给定字符集的HUFFMANN编码与解码，这里的字符集及其字符频数自己定义，要求输出个字符集的哈夫曼编码及给定的字符串的哈夫曼码及译码结果。

二．实验原理首先规定构建哈夫曼树，然后进行哈夫曼树的编码，接着设计函数进行字符串的编码过程，最后进行哈夫曼编码的译码。

首先定义一个结构体，这个结构体定义时尽可能的大，用来存放左右的变量，再定义一个地址空间，用于存放数组，数组中每个元素为之前定义的结构体。

输入n个字符及其权值。

构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为：1.首先将地址空间初始化，将ht[0…n-1]中所有的结点里的指针都设置为空，并且将权值设置为0.2.输入:读入n个叶子的权值存于向量的前n个分量中。

它们是初始森林中n个孤立的根结点上的权值。

3.合并:对森林中的树共进行n-1次合并，所产生的新结点依次放入向量ht的第i个分量中。

每次合并分两步：①在当前森林ht[0…i-1]的所有结点中，选取权最小和次小的两个根结点[s1]和 [s2]作为合并对象，这里0≤s1，s2≤i-1。

②将根为ht[s1]和ht[s2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点ht[i]。

具体操作：将ht[s1]和ht[s2]的parent置为i，将ht[i]的lchild和rchild分别置为s1和s2 .新结点ht[i]的权值置为ht[s1]和ht[s2]的权值之和。

4.哈夫曼的编码：约定左子为0，右子为1，则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。

当用户输入字母时。

就在已经找好编码的编码结构体中去查找该字母。

查到该字母就打印所存的哈夫曼编码。

接着就是完成用户输入0、1代码时把代码转成字母的功能。

这是从树的头结点向下查找，如果当前用户输入的0、1串中是0则就走向该结点的左子。

如果是1这就走向该结点的右结点，重复上面步骤。