2023年数据结构实验报告哈夫曼树

数据结构实验报告

实验题目：Huffman编码与解码

姓名:

学号:

院系:

实验名称：

Huffman编码与解码实验

问题描述：

本实验需要以菜单形式完毕以下功能：

1.输入电文串

2.记录电文串中各个字符及其出现的次数

3.构造哈弗曼树

4.进行哈弗曼编码

5.将电文翻译成比特流并打印出来

6.将比特流还原成电文

数据结构的描述：

逻辑结构：

本实验可用二叉树实现,其逻辑结构为一对二的形式，即一个结点相应两个结

点。在实验过程中我们也应用到了栈的概念。

存储结构：

使用结构体来对数据进行存储：

typedefstruct

(

intweight;

intparent,1c,rc;

}HTNode,*HuffmanTree;

typedefstructLNode

ochar*elem;

。intstacksize；

©inttop;

}SqStack;

在main函数里面定义一个哈弗曼树并实现上述各种功能。

程序结构的描述：

本次实验一共构造了1()个函数：

l.voidHuffTree(HuffmanTree&HT,intn[],intmun);

此函数根据给定的mun个权值构建哈弗曼树，n口用于存放num个权值。

2.voidSelect(HuffmanTree&HT,intn,inti,int&sljnt&s2);

此函数用于在中选择parent为0且weight为最小的两个结点,

其下标分别为sl,s2.

3.voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn);

此函数从哈弗曼树HT上求得n个叶子结点的哈弗曼编码并存入数组HC

中。

4.voidCoding(IIuffmanTreeHT,char**HC,introot,Sq

Stack&S)；

此函数用于哈弗曼编码，先序遍历哈弗曼树H1；求得每个叶子结点的编码字

符串，存入数组HC,S为一个顺序栈，用来记录遍历途径，root是哈弗曼数组HT

中根结点的位置下标。

5.voidInitStack(SqStack&S)；

此函数用于初始化一个栈。

6.voidPop(SqStack&S,chare)；

此函数为出栈操作。

7.voidPush(SqStack&S,chare)；

此函数为进栈操作。

8.intStackLength(SqStackS)；

此函数用于求栈长，返回一个int型的值。

9.intFind(chara,chars[],intnum);

此函数用于查找字符a在电文串中的位置。

10.intRecover(HuffmanTreeH[char**HC,charstring[],chara

[],charb[],intn);

此函数用于将比特流还原成电文。

调试分析：

输入任意一个字符串，如输入welcometoustc:运营结果如下：

清

天:

c

数

出

次

现—

0m文

we该

et出

w"Ft

口*

数

出

次

现

文

该eG-

*

数

出

次

现—

文

该

口l

数

出

次

口

现

文

亥c

口

数

出

次

现

文

亥oI

*"F

出

次

数

现

文

该

口n-

出

次

数

出

t现

文

该

口

出

数

次

u现

文

该

s

出

次

数

现

文

该

申

树

曼

限

41645

416710

5171112

8171314

1301516

哈弗曼编码:

3：1110

B：011

1：1111

C：100

0：101

n:000

t：110

a：001

S：010

该电文的哈弗曼编码为：

11100111111100101000011110101001010110100

请输入哈弗曼编码：

按照提醒输入任意一个或多个哈弗曼编码，如输入:

请输入哈弗曼编码:

11111110101

Luo

结果对的。

若输入一个11111:

请输入哈弗曼编码:

11111

代码有误?

结果对的。

实验完毕!

实验体会和收获：

本次实验提高了对哈弗曼树的结识，同时加深了对二叉树的理解，在栈的运用上

更加纯熟,对数组的应用也有了提高。

源代码:

#inc1ude<stdio.h>

itinc1ude<std1ib.h>

#inc1ude<ma11oc.h>

#include<string.h>

typedefstruct

。intweight;

intparent,1c,rc；

}HTNode,HuffmanTree;

typedefstructLNode

(

char*elem;

intstacksize;

einttop;

}SqStack;

#definesize20

voidHuffTree(HuffmanTree&HTjntn[],intmun)；

voidSelect(HuffmanTree&HT,intnjntiJnt&sl,int&s2)；

voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn)；

voidCoding(HuffmanTreeHf；char**HC,introotzSqStack&S);

voidInitStack(SqStack&S);

voidPop(SqStack&S,chare)；

voidPush(SqStack&S,chare);

intStackLength(SqStackS)；

intFind(chara,chars[],intnum);

intRecover(HuffmanTreeHl；char**HC,charstring[],chara

[],charb[]Jntn);

intmain()

6inti=0,nLsize]={0},j=O,k=l,num=0；

ocharstring[size]={0},m[size]={0},a[size]={0},b[size]={0};

char**HC;

3HuffmanTreeHT；

printf(“请输入电文串:\n")；

scanf(n%s”，string)；

strcpy(m,string);

whi1e(string[j])

(

。if(string[j]!='#')a[k]=string[j];

i=j；

。whi1e(string[i])

。{

jif(string[i]==a[k])

0b{

sstring[1]='#';

oon[k]++;

0)

。i++；

4

。if(n[k]!=0)

00{

printf(“该电文中字符％c出现次数为％d\n",a[k]zn[k])；

b3num++；

k++；

)

°j++；

0}

printf("哈弗曼树:\n")；

HuffTree(HT,n,num);

for(i=l；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“)；

3HuffmanCoding(H[HC,num);

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

(

。printf("%c:%s\nn,a[i],HC[i])；

。}

叩rintf(n\n该电文的哈弗曼编码为:\n”);

。i=0;

。whi1e(string[i])

printf("%su,HC[Find(m[i++],a,num)]);

Printf(H\n请输入哈弗曼编码:\n");

scanf("%s”户tring)；

if(Recover(H^HC^tring,a,b,num))printf("%s\n",b)；

®e1seprintf("代码有误!\n");

。system("pause");

oreturn0;

)

voidHuffTree(HuffmanTree&HTJntn[],intnum)

inti,m,sl,s2；

bm=2*num-l;

。HT=(HuffmanTree)malloc((m+l)*sizeof(HTNode))；

for(i=l;i<=m;i++)

。{

.weight=i<=num?n[i]:0;

HT[i].lc=HT[i].rc=HT[i].parent=0;

°}

efor(i=num+l；i<=m;i++)

(

oSelect(H]num,i,sl,s2)；

。HT[i].lc=sl;

—HT[i].rc=s2;

HT[i].weight=HT[sl].weight+HT[s2].weight;

。HT[si].parent=HT[s2].parent=i；

°}

}

voidSelect(HuffmanTree&HTJntn,inti,int&sl,int&s2)

(

。intk,t;

sl=s2=-l；

。k=1;

owhile(sl==-1)

(

。if(HT[k].parent==O)

3°3sl=k；

k++;

b}

bk=1;

while(s2==-l||s2==sl)

(

。if(HT[k].parent==0)

os2=k;

。k++;

0)

if(HT[s2].weight<HT[si].weight)

°{

。t=s2;s2=s1；sl=t;

。}

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

。{

if(HT[k].parent==O)

°{

if(HT[k].weight<HT[sl].weight&&k!=sl&&k!=s2)

00{

obbs2=sl;

。sl=k;

6}

e。e1seif(HT[k].weight<HT[s2].weight&&HT[k].weight>=HT[si].we

ight&&k!=sl&&k!=s2)s2=k；

}

)

}

voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn)

{

SqStackS；

。InitStack(S);

。HC=(char**)maIIoc((n+1)*sizeof(char*));

Coding(HT,HC,2*n・l,S);

)

voidCoding(HuffmanTreeHT,char**HCJntroot,SqStack&S)

(

if(root!=0)

o一f(HT[root].1c==0)

(

Push(S,'\0')；

。。HC[root]=(char*)ma1loc((StackLength(S)))；

strcpy(HC[root],S.elem)；

oopop(S/\0');

oo|

。Push(S/O')；

oCoding(HT,HC,HT[root].1c,S);

»Pop(S,'\0');

。Push(S/1')；

。Coding(HT,HC,HT[root].rc,S)；

。Pop(S,'\0');

}

)

voidInitStack(SqStack&S)

(

。S.e1em=(char*)malloc(size*sizeof(char));

S.stacksize=size；

S.top=-l;

)

voidPush(SqStack&Szchare)

(

oS.elem[++S.top]=e;

}

voidPop(SqStack&S,chare)

(

if(S.top==-l)return;

e=S.elem[S.top-]；

。return；

)

intStackLength(SqStackS)

(

。if(S.top==-l)return(0);

。return(S.top);

}

intFind(chara,chars[],intnum)

。inti;

for(i=l;i<=num;i++)

oif(a==s[i])returni;

。return0；

}

intRecover(HuffmanTreeHT,char**HC,charstring[],chara[],

charbL],intn)

(

inti=0,j=0,k,m=0,t=0,h=0；

ochars[size];

。k=2*n—1；

whi1e(string[i])

(

f