数据结构实验报告(哈夫曼树).doc

数据结构实验报告

实验题目： Huffman编码与解码

姓名：
学号：
院系：

实验名称：
Huffman编码与解码实验
问题描述：
本实验需要以菜单形式完成以下功能：
1.输入电文串
2.统计电文串中各个字符及其出现的次数
3.构造哈弗曼树
4.进行哈弗曼编码
5.将电文翻译成比特流并打印出来
6.将比特流还原成电文
数据结构的描述：
逻辑结构：
本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。
存储结构：
使用结构体来对数据进行存储：
typedef struct
{
int weight;
int parent,lc,rc;
}HTNode,*HuffmanTree;

typedef struct LNode
{
char *elem;
int stacksize;
int top;
}SqStack;
在main函数里面定义一个哈弗曼树并实现上述各种功能。
程序结构的描述：
本次实验一共构造了10个函数：
1. void HuffTree(HuffmanTree &HT,int n[],int mun);
此函数根据给定的mun个权值构建哈弗曼树，n[]用于存放num个权值。
2.void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);
此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点，其 下标分别为s1,s2.
3. void HuffmanCoding(HuffmanTree HT,char **&HC,int n);
此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。
4. void Coding(HuffmanTree HT,char **HC,int root,SqStack &S)；
此函数用于哈弗曼编码，先序遍历哈弗曼树HT，求得每个叶子结点的编码字符串，存入数组HC，S为一个顺序栈，用来记录遍历路径，root是哈弗曼数组HT中根结点的位置下标。
5. void InitStack(SqStack &S);
此函数用于初始化一个栈。
6. void Pop(SqStack &S,char e);
此函数为出栈操作。
7. void Push(SqStack &S,char e);
此函数为进栈操作。
8. int StackLength(SqStack S);
此函数用于求栈长，返回一个int型的值。
9. int Find(char a,char s[],int num);
此函数用于查找字符a在电文串中的位置。
10. int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n);
此函数用于将比特流还原成电文。
调试分析：
输入任意一个字符串，如输入welcometoustc:运行结果如下：

按照提示输入任意一个或多个哈弗曼编码，如输入11111110101：

结果正确。
若输入一个11111：

结果正确。
实验完成！
实验体会和收获：
本次实验提高了对哈弗曼树的认识，同时加深了对二叉树的理解，在栈的运用上更加熟练，对数组的应用也有了提高。
源代码：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
typedef struct
{
int weight;
int parent,lc,rc;
}HTNode,*HuffmanTree;

typedef struct LNode
{
char *elem;
int stacksize;
int top;
}SqStack;

#define size 20
void HuffTree(HuffmanTree &HT,int n[],int mun);
void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);
void HuffmanCoding(HuffmanTree HT,char **&HC,int n);
void Coding(HuffmanTree HT,char **HC,int root,SqStack &S);
void InitStack(SqStack &S);
void Pop(SqStack &S,char e);
void Push(SqStack &S,char e);
int StackLength(SqStack S);
int Find(char a,char s[],int num);
int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n);
int main()
{
int i=0,n[size]={0},j=0,k=1,num=0;
char string[size]={0},m[size]={0},a[size]={0},b[size]={0};
char** HC;
HuffmanTree HT;
printf("请输入电文串:\n");
scanf("%s",string);
strcpy(m,string);
while(string[j])
{
if(string[j]!='#') a[k]=string[j];
i=j;
while(string[i])
{
if(string[i]==a[k])
{
string[i]='#';
n[k]++;
}
i++;
}
if(n[k]!=0)
{
printf("该电文中字符%c出现次数为%d\n",a[k],n[k]);
num++;
k++;
}
j++;
}
printf("哈弗曼树:\n");
HuffTree(HT,n,num);
for(i=1;i<=2*num-1;i++) printf("%d\t%d\t%d\t%d\n",HT[i].weight,HT[i].parent,HT[i].lc,HT[i].rc);
printf("哈弗曼编码:\n");
HuffmanCoding(HT,HC,num);
for(i=1;i<=num;i++)
{
printf("%c : %s\n",a[i],HC[i]);
}
printf("\n该电文的哈弗曼编码为:\n");
i=0;
while(string[i])
printf("%s",HC[Find(m[i++],a,num)]);
printf("\n请输入哈弗曼编码：\n");
scanf("%s",string);
if(Recover(HT,HC,string,a,b,num)) printf("%s\n",b);
else printf("代码有误!\n");
system("pause");
return 0;
}
void HuffTree(HuffmanTree &HT,int n[],int num)
{
int i,m,s1,s2;
m=2*num-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=m;i++)
{
HT[i].weight=i<=num?n[i]:0;
HT[i].lc=HT[i].rc=HT[i].parent=0;
}
for(i=num+1;i<=m;i++)
{
Select(HT,num,i,s1,s2);
HT[i].lc=s1;
HT[i].rc=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
HT[s1].parent=HT[s2].parent=i;
}
}
void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2)
{
int k,t;
s1=s2=-1;
k=1;
while(s1==-1)
{
if(HT[k].parent==0)
s1=k;
k++;
}
k=1;
while(s2==-1||s2==s1)
{
if(HT[k].parent==0)
s2=k;
k++;
}
if(HT[s2].weight<HT[s1].weight)
{
t=s2;s2=s1;s1=t;
}
for(k=1;k<i;k++)
{
if(HT[k].parent==0)
{
if(HT[k].weight<HT[s1].weight&&k!=s1&&k!=s2)
{
s2=s1;
s1=k;
}
else if(HT[k].weight<HT[s2].weight&&HT[k].weight>=HT[s1].weight&&k!=s1&&k!=s2) s2=k;
}

}
}
void HuffmanCoding(HuffmanTree HT,char **&HC,int n)
{
SqStack S;
InitStack(S);
HC=(char**)malloc((n+1)*sizeof(char*));
Coding(HT,HC,2*n-1,S);
}

void Coding(HuffmanTree HT,char **HC,int root,SqStack &S)
{
if(root!=0)
{
if(HT[root].lc==0)
{
Push(S,'\0');
HC[root]=(char*)malloc((StackLength(S)));
strcpy(HC[root],S.elem);
Pop(S,'\0');
}
Push(S,'0');
Coding(HT,HC,HT[root].lc,S);
Pop(S,'\0');
Push(S,'1');
Coding(HT,HC,HT[root].rc,S);
Pop(S,'\0');
}
}
void InitStack(SqStack &S)
{
S.elem=(char *)malloc(size*sizeof(char));
S.stacksize=size;
S.top=-1;
}
void Push(SqStack &S,char e)
{
S.elem[++S.top]=e;
}
void Pop(SqStack &S,char e)
{
if(S.top==-1) return;
e=S.elem[S.top--];
return;
}
int StackLength(SqStack S)
{
if(S.top==-1) return(0);
return(S.top);
}
int Find(char a,char s[],int num)
{
int i;
for(i=1;i<=num;i++)
if(a==s[i]) return i;
return 0;
}

int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n)
{
int i=0,j=0,k,m=0,t=0,h=0;
char s[size];
k=2*n-1;
while(string[i])
{
if(!HT[k].lc&&!HT[k].rc)
{
if(string[i]=='0') {s[j]='\0';k=2*n-1;t=1;j=0;}
if(string[i]=='1')
{
s[j]='\0';
k=2*n-1;
t=1;
j=0;
}
for(h=1;h<=n;h++)
if(!strcmp(HC[h],s))
b[m++]=a[h];
}
else
{
if(string[i]=='0') {k=HT[k].lc;s[j++]='0';}
if(string[i]=='1')
{
k=HT[k].rc;
s[j]='1';
j++;
}
t=0;
}
if(!t)
i++;
}
if(!HT[k].lc&&!HT[k].rc)
{
if(string[i-1]=='0') {s[j]='\0';k=2*n-1;j=0;}
if(string[i-1]=='1')
{
s[j]='\0';
k=2*n-1;
t=1;
j=0;
}
for(h=1;h<=n;h++)
if(!strcmp(HC[h],s))
b[m++]=a[h];
}
b[m]='\0';
if(k==2*n-1) return 1;
else return 0;
}