数据结构—赫夫曼编码实验报告（包含运行结果截图）.doc

赫夫曼编码实验报告一、 问题描述：设计一个程序，通过赫夫曼树求得赫夫曼编码。二、 需求分析（1）用户输入权值的个数。输入的各字符的权值为整形int。 （2）输出的形式为整型。（3）程序执行可使用户在输入一列数值后，可得到由这些权值所得到的编码。（4）测试数据：输入权值个数为4，依次是：7 5 2 4；输出结果为：0，10，110，111。三、 概要设计1.抽象数据类型：ADT BinaryTree数据对象 D：D是具有相同特性的数据元素的集合。数据关系 R：若 D=，则R=，称BinaryTree为空二叉树；若 D，则R=H，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-root,则存在D-root=D1,Dr,且D1Dr=；（3）若D1，则D1中存在唯一的元素X1，属于H，且存在D1上的关系H1包含于H；若Dr中存在唯一的元素Xr，属于H，且存在Dr上的关系Hr包含于H；H=,H1,Hr；（4）（D1，H1）是一棵符合本定义的二叉树，称为根的左子树，（Dr，Hr）是一棵符合本定义的二叉树，称为根的又子树。基本操作P： CreateHuffmanTree（&HT,）; 初始条件：给出HuffmanTree的定义。 操作结果：构造HuffmanTree。 HuffmanCoding(HuffmanTreeHT,HuffmanCode&HC) 初始条件：HT存在。 操作结果：得出编码HC。 PrintHuffmanCode(HuffmanTreeHT,HuffmanCodeHC) 初始条件：HT，HC存在。 操作结果：显示字符与其对应的编码。 四、 详细设计1.赫夫曼树和赫夫曼编码的存储表示typedef struct char data; /结点字符 int weight; /结点权值 int parent,lchild,rchild; /父子结点 HTNode,HuffmanTree;typedef char * *HuffmanCode;2.返回赫夫曼树t的前i个结点中权值最小的树的根节点序号，函数select调用 int min(HuffmanTree &t,int i)int j,m;int UINT_MAX;unsigned int k=UINT_MAX;for(j=2;j=i;j+)if(tj.weightk&tj.parent=0) k=tj.weight; m=j; tm.parent=1; return m;3. 在赫夫曼树t的前i个结点中选择2个权值最小的树的根结点序号，s1为其中序号（权值）较小的void Select(HuffmanTree HT, int m, int& s1, int& s2) int i; s1 = s2 = 1; for(i=1; i=m; i+) if (HTi.parent=0) s1=i; break; for(i=i+1; iHTi.weight) s1=i; for(i=1; i=m; i+) if(HTi.parent=0&i!=s1) s2=i; break; for(i=i+1; i=m; i+) if(HTi.parent=0 & HTi.weightHTs2.weight & i!=s1) s2=i; 4.求赫夫曼编码算法void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n)unsigned f;int m,i,s1,s2;unsigned c;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).parent=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个权值(整