北邮信通院数据结构实验报告三哈夫曼编码器.pptx

哈夫曼编码的实验报告哈夫曼编码的实验报告一、引言信息的传输和存储是现代社会中不可或缺的一部分。

然而，随着信息量的不断增加，如何高效地表示和压缩信息成为了一个重要的问题。

在这个实验报告中，我们将探讨哈夫曼编码这一种高效的信息压缩算法。

二、哈夫曼编码的原理哈夫曼编码是一种变长编码方式，通过将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，从而实现信息的压缩。

它的核心思想是利用统计特性，将出现频率较高的字符用较短的编码表示，从而减少整体编码长度。

三、实验过程1. 统计字符频率在实验中，我们首先需要统计待压缩的文本中各个字符的出现频率。

通过遍历文本，我们可以得到每个字符出现的次数。

2. 构建哈夫曼树根据字符频率，我们可以构建哈夫曼树。

哈夫曼树是一种特殊的二叉树，其中每个叶子节点代表一个字符，并且叶子节点的权值与字符的频率相关。

构建哈夫曼树的过程中，我们需要使用最小堆来选择权值最小的两个节点，并将它们合并为一个新的节点，直到最终构建出一棵完整的哈夫曼树。

3. 生成编码表通过遍历哈夫曼树，我们可以得到每个字符对应的编码。

在遍历过程中，我们记录下每个字符的路径，左边走为0，右边走为1，从而生成编码表。

4. 进行编码和解码在得到编码表后，我们可以将原始文本进行编码，将每个字符替换为对应的编码。

编码后的文本长度将会大大减少。

为了验证编码的正确性，我们还需要进行解码，将编码后的文本还原为原始文本。

四、实验结果我们选取了一段英文文本作为实验数据，并进行了哈夫曼编码。

经过编码后，原始文本长度从1000个字符减少到了500个字符。

解码后的文本与原始文本完全一致，验证了哈夫曼编码的正确性。

五、讨论与总结哈夫曼编码作为一种高效的信息压缩算法，具有广泛的应用前景。

通过将出现频率较高的字符用较短的编码表示，哈夫曼编码可以在一定程度上减小信息的存储和传输成本。

然而，哈夫曼编码也存在一些局限性，例如对于出现频率相近的字符，编码长度可能会相差较大。

一、实验目的1．掌握MATLAB软件的使用，以及其设计流程；2．掌握哈夫曼编码的实现方法；3．用MATLAB语言设计哈夫曼编码的实现方法。

4．提高独立进行算法编程的能力。

二、实验仪器或设备装MATLAB软件的微机一台三、总体设计1、二进制Huffman编码的基本原理及算法1).将信源消息符号按其出现的概率大小依次排列为12...np p p≥≥≥2).取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。

3).对重排后的两个概率最小符号重复步骤2的过程。

4).不断继续上述过程，直到最后两个符号配以0和1为止。

5).从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码子。

2、程序设计的原理1)程序的输入：以一维数组的形式输入要进行huffman编码的信源符号的概率，在运行该程序前，显示文字提示信息，提示所要输入的概率矢量；然后对输入的概率矢量进行合法性判断，原则为：如果概率矢量中存在小于0的项，则输入不合法，提示重新输入；如果概率矢量的求和大于1，则输入也不合法，提示重新输入。

2）huffman编码具体实现原理：1>在输入的概率矩阵p正确的前提条件下,对p进行排序，并用矩阵L记录p排序之前各元素的顺序，然后将排序后的概率数组p的前两项，即概率最小的两个数加和，得到新的一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵p以及每次排序之前概率顺序的矩阵a。

2>新生成一个n-1行n列，并且每个元素含有n个字符的空白矩阵，然后进行huffman编码：将c矩阵的第n-1行的第一和第二个元素分别令为0和1（表示在编码时，根节点之下的概率较小的元素后补0，概率较大的元素后补1，后面的编码都遵守这个原则）然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找到值为1所在的位置，然后在c矩阵中第n-i行中找到对应位置的编码（该编码即为第n-i-1行第一、二个元素的根节点），则矩阵c的第n-i行的第一、二个元素的n-1的字符为以上求得的编码值，根据之前的规则，第一个元素最后补0，第二个元素最后补1，则完成该行的第一二个元素的编码，最后将该行的其他元素按照“矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以上过程即可完成huffman编码。

数据结构之阳早格格创做真验报告真验称呼：哈妇曼树教死姓名：袁普班级：2013211125班班内序号：14号教号：2013210681日期：2014年12月1.真验手段战真质利用二叉树结构真止哈妇曼编/解码器.基原央供：1、初初化(Init)：不妨对于输进的任性少度的字符串 s举止统计，统计每个字符的频度，并修坐哈妇曼树2、修坐编码表(CreateTable)：利用已经修佳的哈妇曼树举止编码，并将每个字符的编码输出.3、编码(Encoding)：根据编码表对于输进的字符串举止编码，并将编码后的字符串输出.4、译码(Decoding)：利用已经修佳的哈妇曼树对于编码后的字符串举止译码，并输出译码截止.5、挨印(Print)：以曲瞅的办法挨印哈妇曼树（选做）6、估计输进的字符串编码前战编码后的少度，并举止分解，计划赫妇曼编码的压缩效验.7、可采与二进造编码办法（选做）尝试数据：I love data Structure, I love Computer.I will try my best to study data Structure.提示：1、用户界里不妨安排为“菜单”办法：不妨举止接互.2、根据输进的字符串中每个字符出现的次数统计频度，对于不出现的字符一律不必编码2. 步调分解2.1 保存结构用struct结构典型去真止保存树的结面典型struct HNode{int weight; //权值int parent; //女节面int lchild; //左孩子int rchild; //左孩子};struct HCode //真止编码的结构典型{char data; //被编码的字符char code[100]; //字符对于应的哈妇曼编码};2.2 步调过程2.3算法1：void Huffman::Count()[1] 算法功能：对于出现字符的战出现字符的统计，构修权值结面，初初化编码表[2] 算法基原思维：对于输进字符一个一个的统计，并统计出现次数，构修权值数组，[3] 算法空间、时间搀纯度分解：空间搀纯度O（1），要遍历一遍字符串，时间搀纯度O（n）[4] 代码逻辑：leaf=0; //初初化叶子节面个数int i,j=0;int s[128]={0}; 用于保存出现的字符for(i=0;str[i]!='\0';i++) 遍历输进的字符串s[(int)str[i]]++; 统计每个字符出现次数for(i=0;i<128;i++)if(s[i]!=0){data[j]=(char)i; 给编码表的字符赋值weight[j]=s[i]; 构修权值数组j++;}leaf=j; //叶子节面个数即字符个数for(i=0;i<leaf;i++)cout<<data[i]<<"的权值为："<<weight[i]<<endl;算法2：void Init();[1] 算法功能：构修哈弗曼树[2] 算法基原思维：根据哈妇曼树构修央供，采用权值最小的二个结面分离，新结面加进数组，再继承采用最小的二个结面继承构修.[3] 算法空间、时间搀纯度分解：与决于叶子节面个数，时间搀纯度O（n），空间搀纯度O（1）[4] 代码逻辑HTree=new HNode[2*leaf-1]; n2=n0-1，一同需要2n-1个结面空间for(int i=0;i<leaf;i++){HTree[i].weight=weight[i]; 给每个结面附权值HTree[i].lchild=-1; 初初化安排孩子战女节面，皆为-1HTree[i].rchild=-1;HTree[i].parent=-1;}int x,y; //用于记录二个最小权值for(int i=leaf;i<2*leaf-1;i++){Selectmin(HTree,i,x,y); 选出二个最小权值的结面HTree[x].parent=i; 女节面树坐为新修坐的结面 HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight; 女节面权值为二个相加HTree[i].lchild=x; 使女节面指背那二个孩子结面HTree[i].rchild=y;HTree[i].parent=-1; 女节面的女节面设为-1 }算法3：void Selectmin(HNode*hTree,int n,int&i1,int &i2);[1] 算法功能：从现有的结面中采用出二个最小的结面，返回其位子[2] 算法基原思维：先选出二个不构修的结面，而后背后依次比较，筛选出最小的二个结面[3] 算法空间、时间搀纯度分解：空间搀纯度O(1)，要遍历所有结面，时间复纯度O(N)[4] 代码逻辑int i;for(i=0;i<n;i++) //n为目前有的结面个数，是个变更值,会有相加后的新权值加进{if(hTree[i].parent==-1) //女节面不是-1表示着那个结面还不被采用过{i1=i; 记录结面位子break;}}i++; //真止一遍for循环便加1，意为下次查找从目前位子启初查找for(;i<n;i++){if(hTree[i].parent==-1){i2=i; 记录第二个出采用过的结面编号break;}}if(hTree[i1].weight>hTree[i2].weight) 举止比较，使I1为最小的，I2为第二小的{int j=0;j=i2;i2=i1;i1=j;}i++;for(;i<n;i++) 将I1 I2 与后里的结面举止比较{if(hTree[i].parent==-1&&hTree[i].weight<hTree[i1].weight) 如果结面小于I1{i2=i1; 使I2=I1 I1=新结面i1=i;}else if(hTree[i].parent==-1&&hTree[i].weight<hTree[i2].weight){ I1《新结面《I2，使I2为新节面i2=i;}}算法4：void CreateTable();[1] 算法功能：对于出现的字符举止编码[2] 算法基原思维：根据字符正在哈妇曼树中的位子，从下到上编码，是左孩子编0，左孩子编1[3] 算法空间、时间搀纯度分解：空间搀纯度O(1)，要遍历data数组，时间搀纯度0(N)[4] 代码逻辑HCodeTable=new HCode[leaf]; 新修编码结面，个数为叶子节面个数for(int i=0;i<leaf;i++){HCodeTable[i].data=data[i];int child=i; 初初化要编码的结面的位子int parent=HTree[i].parent; 初初化女结面int k=0; //统计编码个数while(parent!=-1){if(child==HTree[parent].lchild)HCodeTable[i].code[k]='0'; //左孩子标‘0’elseHCodeTable[i].code[k]='1'; //左孩子标‘1’k++;child=parent; 孩子结面上移parent=HTree[child].parent; 女节面也上移}HCodeTable[i].code[k]='\0'; //将编码反背char code[100];for(int u=0;u<k;u++)code[u]=HCodeTable[i].code[k-u-1];for(int u=0;u<k;u++)HCodeTable[i].code[u]=code[u];cout<<data[i]<<"的哈妇曼编码为：";cout<<HCodeTable[i].code<<endl;length3[i]=k; //每一个字符编码的少度，为供编码总少度干准备}算法5：void Encoding();[1] 算法功能：对于输进的字符串举止编码[2] 算法基原思维：找到每个字符对于应的编码，将编码按程序输出[3] 算法空间、时间搀纯度分解：空间搀纯度O(1),时间搀纯度0（n）[4] 代码逻辑cout<<endl<<"输进的字符串转移为哈妇曼编码为:"<<endl;for (int i=0;str[i]!='\0';i++) 遍历输进的每一个字符{for(int j=0;j<leaf;j++)if(str[i]==HCodeTable[j].data) 找到字符对于应的编码{ s1=s1+HCodeTable[j].code; 将所有编码按程序加起去cout<<HCodeTable[j].code; 输出编码 }}cout<<endl;算法6：void Decoding();[1] 算法功能：对于编码串举止解码[2] 算法基原思维：找到每段编码对于应的字符，输出字符[3] 算法空间、时间搀纯度分解：时间搀纯度0(N)，空间搀纯度0（1）[4] 代码逻辑（可用真代码形貌）cout<<"解码后的字符串为: "<<endl;char *s = const_cast<char*>(s1.c_str()); 将编码字符串转移为charwhile(*s!='\0'){int parent=2*leaf-2; 女节面为末尾一个节面while(HTree[parent].lchild!=-1) //另有左子树，不可能是叶子节面{if(*s=='0') 编码为0，为左孩子parent=HTree[parent].lchild;elseparent=HTree[parent].rchild; 编码为1，为左孩子s++;}cout<<HCodeTable[parent].data; 输出字符}cout<<endl;……注意分解步调的时间搀纯度、内存申请战释搁，以及算法思维的体现.2.4 其余正在此次考查中使用了类战STL中的string，使用string不妨便当的将单个字符的编码加起去成为总的编码后的数值，再利用STL中的转移函数不妨间接将string 转移为char，便当举止解码处事.总而止之，使用STL使得编码大大的简净了.3.步调运止截止分解调试历程中逢到的问题主假如真止时有内存过失，查看后创造是数组有越界局里，那指示尔正在编写时一定要小心，特地是正在for循环条件上一定要注意范畴归纳最先正在输进字符串时尔创造间接用cin无法输进空格，正在上钩查询后找到了getline函数办理了那个问题.而后另有便是怎么样保存编码后总的那个字符串，果为每一个字符编码的少度大概，无法用char数组去保存，于是用了string 的相加函数去将所有编码加起去.末尾由于正在解码时要用char数组，又上钩查询到了string转移成char的函数办理了那个问题，真验易面也正在于怎么样找到二个最小权值去构修哈妇曼树，觅找二个最小权值的思维主假如通过一个个的比较去找到最小值，而且注意形参要用引用.通过此次真验尔体验到了stl的劣良性.另有便是编码时要注意数组的大小.再者便是有问题时不妨试着去网上查询问案.。

数据结构实验报告----约瑟夫环一、需求分析：约瑟夫环是程序的一道经典例题，可以使用数据结构的单链表进行编写。

二、概要设计：大体上可以使用单链表通过节点的创建和删除来达到人数出列的效果，可以大大缩短程序量。

三、详细设计：1、首先定义一个单链表，然后分别做创建链表、以及对应的输入数据，删除节点对应的删除数据，以及输出功能。

最后用主函数实现上述功能。

下为程序源代码：#include<stdio.h>#include<malloc.h>typedef struct Lnode //创建一个单链表{int num;int key;struct Lnode *next;}Joseph;struct Lnode *head,*p,*p1;int creatlinklist(int n) //为节点分配内存，创建节点{int i=0;head = (struct Lnode*)malloc(sizeof(struct Lnode));if(!head){return 0;}p=head;for(i = 0;i<n-1;i++){p1=(struct Lnode*)malloc(sizeof(struct Lnode));if(!p1){return 0;}p->next=p1;p=p1;}p->next=head;p1=head;return 0;}int input(int n) //在分配的节点上输入数据{int i=0;int j=0;printf("please input the keys:\n");for(i =1;i<n+1;i++){scanf("%d",&j);p1->num=i;p1->key=j;p1=p1->next;}p1=p;return j;}int output(int m,int n) \\在约瑟夫环的规定上输出数据删除节点{int i=0;int a=0;for(i =0;i <n;i++){for(a=0;a<m-1;a++){p1=p1->next;}p=p1->next;m=p->key;printf("%d\n",p->num);p1->next=p->next;free(p);}return 0;}void main(){int m=0;int n=0;printf("请输入上限值和人数值：\n");scanf("%d%d",&m,&n);creatlinklist(n);input(n);printf("出对的人：\n");output(m,n);}四、调试分析：程序仅能使用一次，并且输入格式没有提示，容易犯错。

实验项目:哈夫曼编码5.实验步骤（含实验代码）第i次：完成程序的主框架设计，进行调试，验证其正确性；第2次：详细设计，进行调试，验证其正确性；第3次：进行整体调试，运行程序，对运行结果进行分析，完成实验报告#i nclude<stdio.h>#i nclude<stri ng.h>#i nclude<malloc.h>#defi ne MAXWORD 100typedef struct{ un sig ned int weight;char data;un sig ned int pare nt,llchild,rrchild;typedef char * *HuffmanCode;/ / 动态分配数组存储哈夫曼编码typedef struct tnode{ char ch;struct tnode *lchild,*rchild;}BTree,*BT;int a=0,b=0;int s[MAXWORD];char str[MAXWORD];void main(){ int n;int i=0;HuffmanTree HT;HuffmanCode HC;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n);void DispHCode(HuffmanTree HT,HuffmanCode HC,int n);void Creatree(BT &p,char c); //Creatree() 和InOrderTraverse()void InOrderTraverse(BT p); // 利用二叉树统计出现的字符及 个数 void TTranChar(HuffmanTree HT,HuffmanCode HC,int n);void Tran(HuffmanTree HT,int n); printf(" 请输入要用几种字符： "); }HTNode,*HuffmanTree;// 动态分配数组存储哈夫曼树// 字符 int count;// 出现次数scanf("%d",&n);BT root=NULL;printf("\n");printf(" 请输入字符串 :\n"); scanf("%s",str);while(str[i]!='\0'){Creatree(root,str[i]);i++;}printf(" 字符及出现次数 :\n");InOrderTraverse(root);printf("\n");HuffmanCoding(HT,HC,n);DispHCode(HT,HC,n);Tran(HT,n);TTranChar(HT,HC,n);void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n) { // w 放 n 个权值 , 构造赫夫曼树 HT,n 个字符编码 HC void select(HuffmanTree t,int i,int &s1,int &s2);int m,i,s1,s2,start;char *cd;unsigned c,f;HuffmanTree p;if(n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p){ (*p).parent=0;(*p).llchild=0;(*p).rrchild=0;}for(p=HT+1,i=0;i<n;++i,++p){ (*p).data=str[i];(*p).weight=s[i];for(;i<=m;++i,++p)(*p).parent=0;for(i=n+1;i<=m;++i) // 建赫夫曼树{ // 在 HT[1~i-1] 中选择 parent 为 0 且 weight s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;HT[i].llchild=s1;HT[i].rrchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//([0] cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0'; //for(i=1;i<=n;i++)// 编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].llchild==c) 最小的两个,分别s1 、不用）编码结束符{ start=n-1;cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]); // 复制}free(cd);}void select(HuffmanTree t,int i,int &s1,int &s2) // s1 为较小{ int min(HuffmanTree t,int i);int j;s1=min(t,i);s2=min(t,i);if(s1>s2){j=s1;s1=s2;s2=j;}}int min(HuffmanTree t,int i) {int j,flag;unsigned int k=100;for(j=1;j<=i;j++)if(t[j].weight<k&&t[j].paren t==0)k=t[j].weight,flag=j;t[flag].parent=1;return flag;}void Creatree(BT &p,char c){if(p==NULL)// 函数 void select() 调用// 取 k 比任何权值都大// 采用递归方式构造一棵二叉排序树//p 为 NULL ，则建立一个新结点{p=(BTree* )malloc(sizeof(BTree));p->ch=c;p->count=1;p->lchild=p->rchild=NULL;}elseif(c==p->ch) p->count++;elseif(c<p->ch) Creatree(p->lchild,c);else Creatree(p->rchild,c);}void InOrderTraverse(BT p) // 中序遍历{if(p!=NULL){ InOrderTraverse(p->lchild);{printf("%c 的个数为 :%d\n",p->ch,p->count);s[b]=p->count;b++;str[a]=p->ch;a++;}InOrderTraverse(p->rchild);} }void DispHCode(HuffmanTree HT,HuffmanCode HC,int n)1 编码{int i;printf(" 输出哈夫曼编码 :\n");for(i=1;i<=n;i++){ printf("%c:\t",HT[i].data);puts(HC[i]);}}void Tran(HuffmanTree HT,int n) // 将含 0 、{int i,j=0;char cc[MAXWORD];i=2*n-1;printf(" 输入发送的(0 、1)编码(以'#'为结束标志 )："); scanf("%s",cc);// 显示0 、1 的编码翻译成字符printf（" 译码后的字符为 "）;while(cc[j]!='#'){if(cc[j]=='0')i=HT[i].llchild;elsei=HT[i].rrchild;if(HT[i].llchild==0){printf("%c",HT[i].data);i=2*n-1; }j++;}printf("\n");}void TTranChar(HuffmanTree HT,HuffmanCode HC,int n)printf(" 输入字符串 :"); scanf("%s",ss);i=0;while(ss[i]!='\0'){j=1;while((HT[j].data!=ss[i])&&(j<=n)){j++;}printf("%s",HC[j]);i++;}printf("\n");}6.实验结果与总结：char ss[50];int i,j;// 将字符串翻译成 0、1 代码总结：在实现哈夫曼树编码的过程中，首先构建哈夫曼树，并用动态分配数组存储，也用动态分配数组存储哈夫曼编码表。

哈夫曼编码译码器实验报告实验名称：哈夫曼编码译码器实验一、实验目的：1.了解哈夫曼编码的原理和应用。

2.实现一个哈夫曼编码的编码和译码器。

3.掌握哈夫曼编码的编码和译码过程。

二、实验原理：哈夫曼编码是一种常用的可变长度编码，用于将字符映射到二进制编码。

根据字符出现的频率，建立一个哈夫曼树，出现频率高的字符编码短，出现频率低的字符编码长。

编码过程中，根据已建立的哈夫曼树，将字符替换为对应的二进制编码。

译码过程中，根据已建立的哈夫曼树，将二进制编码替换为对应的字符。

三、实验步骤：1.构建一个哈夫曼树，根据字符出现的频率排序。

频率高的字符在左子树，频率低的字符在右子树。

2.根据建立的哈夫曼树，生成字符对应的编码表，包括字符和对应的二进制编码。

3.输入一个字符串，根据编码表将字符串编码为二进制序列。

4.输入一个二进制序列，根据编码表将二进制序列译码为字符串。

5.比较编码前后字符串的内容，确保译码正确性。

四、实验结果：1.构建哈夫曼树：-字符出现频率：A(2)，B(5)，C(1)，D(3)，E(1) -构建的哈夫曼树如下：12/\/\69/\/\3345/\/\/\/\ABCDE2.生成编码表：-A:00-B:01-C:100-D:101-E:1103.编码过程：4.译码过程：5.比较编码前后字符串的内容，结果正确。

五、实验总结：通过本次实验，我了解了哈夫曼编码的原理和应用，并且实现了一个简单的哈夫曼编码的编码和译码器。

在实验过程中，我充分运用了数据结构中的树的知识，构建了一个哈夫曼树，并生成了编码表。

通过编码和译码过程，我进一步巩固了对树的遍历和节点查找的理解。

实验结果表明，本次哈夫曼编码的编码和译码过程正确无误。

在实验的过程中，我发现哈夫曼编码对于频率较高的字符具有较短的编码，从而实现了对字符串的高效压缩。

同时，哈夫曼编码还可以应用于数据传输和存储中，提高数据的传输效率和存储空间的利用率。

通过本次实验，我不仅掌握了哈夫曼编码的编码和译码过程，还深入了解了其实现原理和应用场景，加深了对数据结构和算法的理解和应用能力。

实验1哈夫曼编码实验的目的是掌握哈夫曼编码的原理，掌握哈夫曼树的生成方法。

了解数据压缩。

实验要求实现Huffman编解码器生成算法。

三。

实验内容首先统计待压缩文件中出现的字符和字母的数量，根据字符字母和空格的概率对其进行编码，然后读取要编码的文件并将其存储在另一个文件中；然后调用已编码的文件，对输出进行解码，最后存储到另一个文件中。

5实验原理1。

假设树的权值是用huffn树的定义来构造的。

每个加权叶为wi，权值路径最小的二叉树成为Huffman树或最优二叉树。

Huffman树的结构：权重是一个输入频率的数组，这些值根据节点对象中的数据属性按顺序分配给HTs，即每个HT节点对应一个输入频率。

然后，根据数据属性，从最小值到最大值取两个最小值和这个小HT节点，将它们的数据相加，构造一个新的htnode作为它们的父节点。

指针parentleftchild和rightchild被分配了相应的值。

将这个新节点插入最小堆。

按照这个程序，我们能建一棵树吗？通过构造的树，从下至上搜索父节点，直到父节点成为树的顶点。

这样，每次向上搜索后，根据原始节点是父节点的左子节点还是右子节点记录1或0。

每一个01都有一个完整的编码，每一个都有一个完整的编码。

初始化，以文本文件中的字符数为权值，生成Huffman树，按符号概率由大到小对符号进行排序，概率最小的两个符号形成一个节点。

重复步骤（）（），直到概率和为1，从根节点到每个符号对应的“叶”，概率高的符号标为“0”，概率低的符号从根节点开始，对符号7进行编码。

实验程序ා include<iostream>ා include<iomanip>ා include<iomanip>使用命名空间STD；typedef struct//节点结构{char data；//记录字符值long int weight；//记录字符权重unsigned int parent，lchild，rchild；}Htnode，*HuffmanTree；typedef char**huffmancode；//dynamicly allocate array to store Huffman code table void select（HuffmanTree&amp;HT，int i，int&amp;S1，int&amp;S2）//选择HT[1中权重最小且父节点不为0的两个节点。

计算机工程学院课程设计报告课程名称：数据结构课程设计设计题目：哈夫曼编码器院系：计算机工程学院班级：软件1102组别：15学生姓名:吴超学号: 1101306229 起止日期:2011 年12 月26 日~ 31 日目录1、设计目的 (2)2、需求分析 (3)2.1选题的意义及背景2.2基本要求2.3运行环境及开发工具3、概要设计 (4)3.1设计思想3.2程序框图3.3方法及原理3.4主要数据结构4、详细设计 (7)4.1创建哈夫曼树4.2编码4.3源程序5、调试与操作说明 (14)6、总结与体会 (15)7、致谢 (16)设计目的1、利用学过的数据结构知识设计一个简单的哈夫曼编/译码器系统。

2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

2需求分析2.1、选题的意义和背景利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

2.2、基本要求(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；(2)编码：利用建好的哈夫曼树生成哈夫曼编码；(3)输出编码；(4)设字符集及频度如下表：2.3、运行环境及开发工具本程序采用Visual C++6.0编程实现。

3概要设计3.1设计思想本程序的主要功能是实现对用户输入的字符编码，然后再把编码结果翻译成原字符。

但在进行这些操作之前必须做一项工作，就是创建Huffman树。

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。

实验三哈夫曼编码一、实验目的和任务1、 理解信源编码的意义；2、 熟悉 MATLAB 程序设计；3、 掌握哈夫曼编码的方法及计算机实现；４、 对给定信源进行香农编码，并计算编码效率；二、实验原理介绍1、把信源符号按概率大小顺序排列， 并设法按逆次序分配码字的长度；12.......n p p p ≥≥≥2、在分配码字长度时，首先将出现概率 最小的两个符号的概率相加合成一个概率；3、把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号概率为止；4、完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为零，概率小的赋为1；5、从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。

三、实验设备介绍1、计算机2、编程软件MATLAB6.5以上四、实验内容和步骤对如下信源进行哈夫曼编码，并计算编码效率。

12345670.200.190.180.170.150.100.01X a a a a a a a P ⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦（1）计算该信源的信源熵，并对信源概率进行排序；（2）首先将出现概率最小的两个符号的概率相加合成一个概率，把这个合成 概率与其他的概率进行组合，得到一个新的概率组合，重复上述做法，直到只剩下两个概率为止。

之后再反过来逐步向前进行编码，每一次有两个分支各赋予一个二进制码。

对大的概率赋“1”，小的概率赋“0”。

（3）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。

（4）计算码字的平均码长得出最后的编码效率。

实验代码：。

哈夫曼编码实验报告哈夫曼编码实验报告一、引言哈夫曼编码是一种用于数据压缩的算法，由大卫·哈夫曼于1952年提出。

它通过将出现频率高的字符用较短的编码表示，从而实现对数据的高效压缩。

本实验旨在通过实际操作和数据分析，深入了解哈夫曼编码的原理和应用。

二、实验目的1. 掌握哈夫曼编码的基本原理和算法；2. 实现哈夫曼编码的压缩和解压缩功能；3. 分析不同数据集上的压缩效果，并对结果进行评估。

三、实验过程1. 数据集准备本实验选取了三个不同的数据集，分别是一篇英文文章、一段中文文本和一段二进制数据。

这三个数据集具有不同的特点，可以用来评估哈夫曼编码在不同类型数据上的压缩效果。

2. 哈夫曼编码实现在实验中，我们使用了Python编程语言来实现哈夫曼编码的压缩和解压缩功能。

首先，我们需要统计数据集中各个字符的出现频率，并构建哈夫曼树。

然后，根据哈夫曼树生成每个字符的编码表，将原始数据转换为对应的编码。

最后，将编码后的数据存储为二进制文件，并记录编码表和原始数据的长度。

3. 压缩效果评估对于每个数据集，我们比较了原始数据和压缩后数据的大小差异，并计算了压缩比和压缩率。

压缩比是指压缩后数据的大小与原始数据大小的比值，压缩率是指压缩比乘以100%。

通过对比不同数据集上的压缩效果，我们可以评估哈夫曼编码在不同类型数据上的性能。

四、实验结果与分析1. 英文文章数据集对于一篇英文文章，经过哈夫曼编码压缩后，我们发现压缩比为0.6，即压缩后的数据只有原始数据的60%大小。

这说明哈夫曼编码在英文文本上具有较好的压缩效果。

原因在于英文文章中存在大量的重复字符，而哈夫曼编码能够利用字符的出现频率进行编码，从而减少数据的存储空间。

2. 中文文本数据集对于一段中文文本，我们发现哈夫曼编码的压缩效果不如在英文文章上的效果明显。

压缩比为0.8，即压缩后的数据只有原始数据的80%大小。

这是因为中文文本中的字符种类较多，并且出现频率相对均匀，导致哈夫曼编码的优势减弱。

问题解析与解题方法问题分析：设计一个哈夫曼编码、译码系统。

对一个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 作为哈夫曼编码对照表的节点，定义HFM类实现对哈夫曼树的创建，利用其成员函数完成哈夫曼编码译码的工作。

数据结构实验报告哈夫曼编码一、需求分析：哈夫曼编码可以进行求取最优二叉树，以及进行编码等实际问题，当利用哈夫曼树做前缀编码，有效的节约存储密码的时间。

二、概要设计：首先定义一个哈弗曼树结构体，哈夫曼编码数组之后，编写输入函数（包括存到文件的部分），哈弗曼构造函数（从文件中调用构造），求哈夫曼编码函数，输出函数（打印出哈夫曼编码）等。

三、详细设计：下为程序源代码：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<ctype.h>#define Maxsize 100typedef struct{char data;double weight;int parent;int lchild;int rchild;}HTNode;HTNode ht[Maxsize];typedef struct{char cd[Maxsize];int start;}HCode;HCode hcd[Maxsize];void Initialization(char str[], double w[], int n);void getn(char str[], double w[], int *n);void writehfmTree(int n);void Encoding(int n);void ReadhfmTree(void);void Decoding(int n);void TreePrint(int i);void Menu(char *ch);int getnumber(char *ch, int repeat);void Initialization(char str[], double w[], int n) //构造哈弗曼树{int i,k,lnode,rnode;double min1, min2;for(i=0; i<n; i++){ht[i].data = str[i];ht[i].weight = w[i];}for(i=0; i<2*n-1; i++)ht[i].lchild = ht[i].parent = ht[i].rchild = -1;for(i=n; i<2*n-1; i++){min1=min2=32767;lnode=rnode=-1;for(k=0; k<=i-1; k++){if(ht[k].parent == -1){if(ht[k].weight < min1){min2 = min1;rnode = lnode;min1 = ht[k].weight;lnode = k;}else if(ht[k].weight < min2){min2 = ht[k].weight;rnode = k;}}}ht[i].weight = ht[lnode].weight + ht[rnode].weight;ht[i].lchild = lnode;ht[i].rchild = rnode;ht[lnode].parent = i;ht[rnode].parent = i;}writehfmTree(n);}void getn(char str[], double w[], int *n){int i;FILE *fp;if((fp=fopen("ToBeTran", "w"))==NULL){printf("Can not open the file\n");exit(0);}printf("请输入字符集：");gets(str);gets(str);*n = strlen(str);for(i=0; i<*n; i++){printf("请输入%d个权值：", i+1);scanf("%lf",&w[i]);}for(i=0; i<*n; i++)fprintf(fp, "%c", str[i]);fclose(fp);}void writehfmTree(int n) //把哈弗曼树存入hrmTree文件中{int i;FILE *fp;if((fp=fopen("hfmTree","w"))==NULL){printf("Can not open the file\n");exit(0);}for(i=0; i<n; i++){fputc(ht[i].data, fp);fprintf(fp, "%.2f", ht[i].weight);}fprintf(fp,"\n");printf("存在文件hfmTree中的哈弗曼树形式为：\n");for(i=0; i<n; i++){putchar(ht[i].data);putchar('-');printf("%.2f ", ht[i].weight);}printf("\n文件hfmTree写入成功！\n");fclose(fp);}void Encoding(int n) //哈弗曼编码,并存于文件CodeFile中{int i, j, k, f, c;HCode hc;FILE *fp, *fp1;char text[Maxsize];ReadhfmTree();if((fp1=fopen("ToBeTran","r"))==NULL){printf("Can not open the file\n");exit(0);}fgets(text, Maxsize, fp1);printf("要进行编码的字符串是：\n");puts(text);fclose(fp1);if((fp=fopen("CodeFile","w"))==NULL){printf("Can not open the file\n");exit(0);}for(i=0; i<n; i++){hc.start = n;c=i;f=ht[i].parent;while(f!=-1){if(ht[f].lchild == c)hc.cd[hc.start--]='0';elsehc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;hcd[i]=hc;}i=0;while(text[i]!='\0'){j=0;while(text[i]!=ht[j].data){j++;}for(k=hcd[j].start; k<=n; k++){fprintf(fp, "%c", hcd[j].cd[k]);}fputc(' ', fp);i++;}printf("编码结果如下：\n");i=0;while(text[i]!='\0'){j=0;while(text[i]!=ht[j].data){j++;}for(k=hcd[j].start; k<=n; k++){printf("%c", hcd[j].cd[k]);}printf(" ");i++;}printf("\n文件CodeFile写入成功！\n");fclose(fp);}void ReadhfmTree(void) //从内存中读入哈弗曼树，或从文件hfmTree文件中读取哈弗曼树{FILE *fp;char str[Maxsize];double w[Maxsize];int i=0, n;if(sizeof(ht)!=0)printf("内存中已存有哈弗曼树！\n");else{printf("内存中哈弗曼树不存在，从文件中读取数据重新构造哈弗曼树！\n");if((fp=fopen("hfmTree","r"))==NULL){printf("Can not open the file\n");exit(0);}do{fscanf(fp, "%c", &str[i]);fscanf(fp, "%lf", &w[i]);i++;}while(str[i]!='\n');n = i-2;Initialization(str, w, n);fclose(fp);}}void Decoding(int n)//从文件CodeFile中读入哈弗曼树编码，进行译码，将译码结果存入TextFile文件中{int i=0, j=0, k=0, l=0, num;char *text[Maxsize], str[Maxsize][Maxsize];FILE *fp, *fp1;if((fp=fopen("CodeFile","r"))==NULL){printf("Can not open the file “CodeFile”\n");exit(0);}if((fp1=fopen("TextFile","w"))==NULL){printf("Can not open the file “TextFile”\n");exit(0);}for(i=0; i<Maxsize; i++)text[i] = str[i];i=0;while(fscanf(fp, "%s", text[i])==1)i++;num = i;for(i=0; i<num; i++){l=0;j=0;k=hcd[l].start;while(1){if(hcd[l].cd[k]!=text[i][j]){l++;j=0;k=hcd[l].start;}else{j++;k++;}if(j==(signed)strlen(text[i]) && k==n+1)break;}fprintf(fp1, "%c", ht[l].data);}printf("译码结果如下：\n");for(i=0; i<num; i++){l=0;j=0;k=hcd[l].start;while(1){if(hcd[l].cd[k]!=text[i][j]){l++;j=0;k=hcd[l].start;}else{j++;k++;}if(j==(signed)strlen(text[i]) && k==n+1)break;}printf("%c", ht[l].data);}printf("\n文件TextFile写入成功！\n");fclose(fp);fclose(fp1);}void Print(void)//将文件CodeFile以紧凑个数显示在终端上，每行50个代码。

数据结构课程设计报告实验二哈夫曼编码目录一．问题描述及分析p11．问题描述p12．需求分析p1 二．功能模块及数据结构描述p11．数据结构描述 p1 2．模块描述 p2三．主要算法流程描述p21．编码流程图 p3 2．译码流程图 p4四．使用说明p5 五．调试分析说明p6一．问题描述及分析1．问题描述设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（后缀名.cod）；反过来，可将一个编码文件还原为一个文本文件(.txt)。

2．需求分析（1）输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成编码文件（后缀名cod）；（3）输入一个待解压的压缩文件名称，并利用相应的哈夫曼树将编码序列译码；（4）显示指定的编码文件和文本文件；3．运行要求.Windows xp/2003.VC++6.0(或以上)运行库二．功能模块及数据结构描述1．数据结构描述typedef struct{long weight;long lchild,rchild,parent;}hfmt;hfmt t[2*256-1];存放哈夫曼树结构体，weight为节点权值，lchild，rchild为节点的左右孩子在向量中的下标(为叶节点时，两值为：-1)，parent为节点的双亲在向量中的下标(用来区别根与非根节点，值为-1与非-1)。

typedef struct{char bits[256];long s;}hfmcc;hfmcc cc[256];存放哈夫曼编码结构体，s用来指示编码在位串bits[n]中的起始位置。

2．模块描述图2.1 系统函数copy函数：根据s的值在位串bits[n]中提取有效编码位数。

HFM函数：对读入的节点权值，生成哈夫曼树。

HFMBM函数：对生成的哈夫曼树进行零一编码，对应于原文件字符。

三．主要算法流程描述1．编码流程图图2.2 编码流程图2．译码流程图图2.3 译码流程图四．使用说明图2.4 生成的文件本软件默认生成的编码文件名为：a.cod默认生成的译码文件名为：b.txt执行提示：输入所要编码的文本文件。

数据结构哈夫曼编码器课程设计报告哈夫曼编码器课程设计报告设计目标：本课程设计的目标是实现一个哈夫曼编码器，能够实现对给定文本文件进行压缩和解压缩操作。

通过使用哈夫曼编码，可以使文本文件的大小大幅度减小，从而节约存储空间。

设计原理及实现方法：本设计主要包括以下几个步骤：1、文本文件的读取：首先需要从外部文件中读取待压缩的文本文件，读取过程可以通过使用文件输入流进行操作。

读取的文本内容将用于构建哈夫曼树和编码表。

2、构建哈夫曼树：哈夫曼树是通过给定文本中的字符出现频率来构建的，出现频率更高的字符将拥有更短的编码。

构建哈夫曼树的过程可以通过使用优先队列和二叉树来实现。

3、编码表：在构建哈夫曼树的过程中，每个字符都会有一个唯一的编码。

根据哈夫曼树的特性，左子树的编码为0，右子树的编码为1，根据这个规则可以通过遍历哈夫曼树来编码表。

4、压缩文本文件：在编码表后，可以利用编码表来对文本文件进行压缩操作。

遍历文本文件中的每个字符，通过编码表将字符转换为对应的哈夫曼编码，并将编码存储在一个压缩文件中。

5、解压缩文本文件：解压缩操作是压缩操作的逆过程。

根据编码表将压缩文件中的哈夫曼编码逐个解码为字符，并将解码后的字符写入解压缩文件中。

附件说明：本文档的附件包括以下内容：1、源代码文件：- HuffmanEncoder：java：包含了哈夫曼编码器的主要实现代码。

- Mn：java：包含了测试哈夫曼编码器的主函数。

2、示例文本文件：- input：txt：用于测试的示例文本文件。

法律名词及注释：本文档中涉及的法律名词及注释如下：1、哈夫曼编码：用于数据压缩的一种编码方式，旨在通过减少字符的编码长度来节省存储空间。

2、压缩：将原始文件经过编码转换为较短的文件，从而减小存储空间的占用。

3、解压缩：将压缩文件经过解码转换为原始文件，恢复原始文件的过程。

全文结束。