数据结构+哈夫曼编码+实验报告

实验报告

一、实验目的

掌握哈夫曼树及其应用。

二、实验内容

利用哈夫曼算法，构造最优二叉树，然后对构造好的二叉树的叶子结点进行前缀编码。

三、实验步骤

（1）审清题意，分析并理出解决问题的基本思路。（2） 根据基本思路，设计好程序的算法。 （3）根据算法编写源程序。（4） 在计算机上编译程序，检验程序的可运行性

数据结构设计：

// 赫夫曼树和赫夫曼编码的存储结构

typedef struct // 结点的结构，在教科书第147页 { unsigned int weight; // 结点的权值

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树

typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) // 算法6.12

{ // w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int start; unsigned f;

// 以下是从叶子到根逆向求每个字符的赫夫曼编码 int m,i,s1,s2; unsigned c;

HuffmanTree p; char *cd;

if(n<=1) // 叶子结点数不大于n

return;

m=2*n-1; // n个叶子结点的赫夫曼树共有m个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用

for(p=HT+1,i=1;i<=n;++i,++p,++w) // 从1号单元开始到n号单元，给叶子结点赋值 { // p的初值指向1号单元 (*p).weight=*w; // 赋权值

(*p).parent=0; // 双亲域为空(是根结点)

(*p).lchild=0; // 左右孩子为空(是叶子结点，即单结点树) (*p).rchild=0;

}

for(;i<=m;++i,++p) // i从n+1到m

(*p).parent=0; // 其余结点的双亲域初值为0 for(i=n+1;i<=m;++i) // 建赫夫曼树

{ // 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2);

HT[s1].parent=HT[s2].parent=i; // i号单元是s1和s2的双亲

HT[i].lchild=s1; // i号单元的左右孩子分别是s1和s2 HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight; // i号单元的权值是s1和s2的权值之和 }

HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); // 分配n个字符编码的头指针向量([0]不用)

cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间 cd[n-1]='\\0'; // 编码结束符

for(i=1;i<=n;i++)

{ // 逐个字符求赫夫曼编码 start=n-1; // 编码结束符位置

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) // 从叶子到根逆向求编码 if(HT[f].lchild==c) // c是其双亲的左孩子 cd[--start]='0'; // 由叶子向根赋值'0'

else // c是其双亲的右孩子

cd[--start]='1'; // 由叶子向根赋值'1'

HC[i]=(char*)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间 strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC }

free(cd); // 释放工作空间 }

源代码：

#include // 字符串函数头文件 #include // 字符函数头文件 #include // malloc()等 #include // INT_MAX等

#include // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等 #include // atoi()，exit()

#include // eof()

#include // 数学函数头文件，包括floor()，ceil()，abs()等

#include // ftime()

#include // 提供宏va_start，va_arg和va_end，用于存取变长参数表 // 函数结果状态代码。在教科书第10页 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

typedef int Status; // Status是函数的类型，其值是函数结果状态代码，如OK等

typedef int Boolean; // Boolean是布尔类型，其值是TRUE或FALSE，第7、8章用到

// 赫夫曼树和赫夫曼编码的存储结构

typedef struct // 结点的结构，在教科书第147页 { unsigned int weight; // 结点的权值

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树

typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表

int min(HuffmanTree t,int i)

{ // 返回赫夫曼树t的前i个结点中权值最小的树的根结点序号，函数select()调用 int j,m;

unsigned int k; // k存最小权值，初值取为不小于可能的值(无符号整型最大值) for(j=1;j<=i;j++) // 对于前i个结点

if(t[j].parent==0) // t[j]的权值小于k，又是树的根结点 { k=t[j].weight; // t[j]的权值赋给k m=j; // 序号赋给m

}

t[m].parent=1; // 给选中的根结点的双亲赋非零值，避免第2次查找该结点 return m; // 返回权值最小的根结点的序号 }

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

{ // 在赫夫曼树t的前i个结点中选择2个权值最小的树的根结点序号，s1为其中序号(权

值)较小的

int j;

s1=min(t,i); // 权值最小的根结点序号 s2=min(t,i); // 权值第2小的根结点序号

if(s1>s2) // s1的序号大于s2的 { // 交换

j=s1;

s1=s2; // s1是权值最小的2个中序号较小的 s2=j; // s2是权值最小的2个中序号较小的 } }

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) // 算法6.12

{ // w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int start;

unsigned f;

// 以下是从叶子到根逆向求每个字符的赫夫曼编码 int m,i,s1,s2; unsigned c; HuffmanTree p;

char *cd;

if(n<=1) // 叶子结点数不大于n

return;

m=2*n-1; // n个叶子结点的赫夫曼树共有m个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用

for(p=HT+1,i=1;i<=n;++i,++p,++w) // 从1号单元开始到n号单元，给叶子结点赋值 { // p的初值指向1号单元

(*p).weight=*w; // 赋权值

(*p).parent=0; // 双亲域为空(是根结点)

(*p).lchild=0; // 左右孩子为空(是叶子结点，即单结点树) (*p).rchild=0;

}

for(;i<=m;++i,++p) // i从n+1到m

(*p).parent=0; // 其余结点的双亲域初值为0

for(i=n+1;i<=m;++i) // 建赫夫曼树

{ // 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2);

HT[s1].parent=HT[s2].parent=i; // i号单元是s1和s2的双亲 HT[i].lchild=s1; // i号单元的左右孩子分别是s1和s2