压缩编码算法设计与实现实验报告.doc

压缩编码算法设计与实现实验报告 200927076 信息092班 王丽娟1、 实验目的：用C语言或C+（也可以是其他开发环境）编写一个实现Huffman编码的程序，理解对数据进行无损压缩的原理。2、 实验内容：设计一个有n个叶节点的huffman树，从终端读入n个叶节点的权值。设计出huffman编码的压缩算法，完成对n个节点的编码，并写出程序予以实现。3、 实验步骤及原理： 1、原理：Huffman算法的描述(1)初始化，根据符号权重的大小按由大到小顺序对符号进行排序。(2)把权重最小的两个符号组成一个节点，(3)重复步骤2，得到节点P2，P3，P4，形成一棵树。(4)从根节点开始顺着树枝到每个叶子分别写出每个符号的代码2、实验步骤：根据算法原理，设计程序流程，完成代码设计。首先，用户先输入一个数n，以实现n个叶节点的Huffman 树；之后，输入n个权值w1wn，注意是unsigned int型数值；然后，建立Huffman 树；最后，完成Huffman编码。4、 实验代码： #include #include #include #define MAX 0xFFFFFFFFtypedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char* HuffmanCode;int min(HuffmanTree t,int i) int j,flag; unsigned int k = MAX; for(j=1;j=i;j+) if(tj.parent=0&tj.weight s2) tmp = s1; s1 = s2; s2 = tmp; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,int &wpl) int m,i,s1,s2,start,j; unsigned int c,f; HuffmanTree p; char *cd; 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,+w) (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; 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); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(i=1;i1：); scanf(%d,&n); w=(int*)malloc(n*sizeof(int); printf(请依次输入%d个权值整型fd：n,n); for(i=0;i=n-1;i+) scanf(%d,w+i); HuffmanCoding(HT,HC,w,n,wpl); for(i=1;i=n;i+) printf(权值为%d的Huffman编码为：%sn,HTi.weight,HCi); printf(带权路径长度WPL=%dn,wpl); return 0;五、实验结果截图：六、实验心得：1.本次实验让我学会了用C语言编写一个实现Huffman编码的程序，并且对数据进行无损压缩的原理有了一定的了解。2.首先对huffman编码的压缩算法进行了设计，然后完成对n个节点的编码，并写出程序予以实现。3.在