2023年數(shù)據(jù)結(jié)構(gòu)哈夫曼樹的實(shí)驗(yàn)報(bào)告

軟件學(xué)院設(shè)計(jì)性實(shí)驗(yàn)報(bào)告

專業(yè)：網(wǎng)絡(luò)工程年級(jí)/班級(jí)：2023—2023學(xué)年第一學(xué)期

課程名稱數(shù)據(jù)結(jié)構(gòu)指導(dǎo)教師

本組成員

學(xué)號(hào)姓名

實(shí)驗(yàn)地點(diǎn)實(shí)驗(yàn)時(shí)間

項(xiàng)目名稱哈夫曼編/譯碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)類型設(shè)計(jì)性

、實(shí)驗(yàn)?zāi)康?/p>

理解哈夫曼樹的特性及其應(yīng)用；在對(duì)哈夫曼樹進(jìn)行理解的基礎(chǔ)上，構(gòu)造哈夫曼樹，并用

構(gòu)造的哈夫曼樹進(jìn)行編碼和譯碼;通過該實(shí)驗(yàn)，使學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用有更深層次的理解。

二、實(shí)驗(yàn)儀器或設(shè)備

學(xué)院提供公共機(jī)房,1臺(tái)/學(xué)生微型計(jì)算機(jī)。

三、總體設(shè)計(jì)（設(shè)計(jì)原理、設(shè)計(jì)方案及流程等）

1.問題描述：

運(yùn)用哈夫曼編碼進(jìn)行通信可以大大提高信道運(yùn)用率，縮短信息傳輸時(shí)間，減少傳輸成本。

但是，這規(guī)定在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接受端將傳來的數(shù)據(jù)進(jìn)行

譯碼（解碼）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系

統(tǒng)。試為這樣的信息收發(fā)站設(shè)計(jì)一個(gè)哈夫曼編/譯碼系統(tǒng)。

2.一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：

1）初始化（Initia1zation）.從數(shù)據(jù)文獻(xiàn)DataFile.dat中讀入字符及每個(gè)字符的

權(quán)值，建立哈夫曼樹HuffTree;

2）編碼（EnCoding）。用已建好的哈夫曼樹，對(duì)文獻(xiàn)ToBeTran.dat中的文本進(jìn)行編

碼形成報(bào)文，將報(bào)文寫在文獻(xiàn)Code,txt中；

3）譯碼（Decoding）。運(yùn)用已建好的哈夫曼樹,對(duì)文獻(xiàn)CodeFi1e.dat中的代碼進(jìn)行

解碼形成原文，結(jié)果存入文獻(xiàn)Textfile.txt中；

4）輸出（Output）:輸出DataFile.dat中出現(xiàn)的字符以及各字符出現(xiàn)的頻度（或概率）；

輸出ToBeTran.dat及其報(bào)文Code.txt；輸出CodeFile.dat及其原文Textfi1e.txt;

規(guī)定:所設(shè)計(jì)的系統(tǒng)應(yīng)能在程序執(zhí)行的過程中,根據(jù)實(shí)際情況（不同的輸入）建立DataFile.da

t、ToBeTran.dat和CodeFi1e.dat三個(gè)文獻(xiàn)，以保證系統(tǒng)的通用性。

四、實(shí)驗(yàn)環(huán)節(jié)(涉及重要環(huán)節(jié)、代碼分析等)

1)編寫C語言程序

#inc1ude<string.h>

#inc1ude<malloc.h>

#include<stdio.h>

Sinc1ude<iostream.h>

#include<math.h>

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

typedefstruct

(

?chardata;

intweight;

ointparent,1child,rchi1d;

}HTNode,"HuffmanTree;

typedefchar*nCode；

voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&H

C,char*d,int*w,intn)〃構(gòu)造哈弗曼函數(shù)HT,構(gòu)造編碼HC

voidselect(HuffmanTreeHT,intn,int&sl,int&

S2);

eintm,c,f,j;

HuffmanTreep;

inti,s1,s2,start；

char*cd;

m=2^n-l；//m為結(jié)點(diǎn)數(shù)，n為葉子數(shù)

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

叩=HT;

叩++;

for(i=1;i<=n;i++,p++)//將葉子的

值輸入HT中

(

p->data=d[i]；//={*d,*w,0,0,0};

p->weight=w[i];

gp—>parent=0；

op->lchild=0；

gp->rchild=0;

)

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

={，tf,0,0,0,0)

(

中->data=';

p—>weight=0；

°p—>parent=0；

p->1child=0;

^>p->rchild=O;

6S1=1;

s2=2；

for(i=n+l;i<=m;i++)〃構(gòu)建哈夫曼樹

°{

。se1ect(HT,i-1,s1,s2);

HT[i].Ichiid=sl;

HT[i].rchi1d=s2；

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

~>HT[s1].parent=i；

HT[s2].parent=i;

oHC=(HuffmanCode)malloc((n+1)*sizeof(HuffmanTree));

//開辟空間，編碼

??cd=(char*)malloc(n*sizeof(char));

cd[nT]='\0'；

for(i=l;iV=n;++i)

。{

?start=n-l;

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)

。(

bif(HT[f].lchild==c)

ocd[---start]=，O';

else

cd[-start]=,1

eHC[i]=(char*)malloc((n-start)*sizeof(char))；

strcpy(HC[i],&cd[start]);

。printf(〃％c的編碼是："，HT[i]);

。puts(HC[i])；

free(cd)；

}

voidselect(HuffmanTreeHT,intn,int&sl,int&s2)

//求最小兩數(shù)

(

einti,t;

os1=1；

，s2=2;

owhile(HT[s1].parent!=0)

sl++;

owhile((HT[s2].parent!=0)I(sl==s2))

8s2++;

/*for(i=l;i<=n;i++)

b{

if(HTLsi].weight>HT[i].weight&&HT[i].pa

rent==0&&s2!=i)

osl=i;

if(HT[s1].weight>HT[s2].weight)

{

bt=Sl；

sl=s2;

s2=t;

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

(

if(sl!=i)

2{

。if(HT[s2].weight>HT[i].weight&&HT[i].parent==0)

3s2=i;

i

“*/

for(i=l;i<=n；i++)

o(

if(si!=i&&i!=s2)

6{

if(HT[i].weight<HT[si].weight&&HT

[i].parent==0&&i!=s2)

oif(HT[sl].weight<HT[s2].weight)s2=s1;

sl=i;

ge1se

gif(HT[i].weight<HT[s2].weight&&HT[i].parent==O&&sl!

=i)匕s2=i;

。}

)

voidtrans1ation(HuffmanTreeHT,intnum)

(

charstrE20];

。inti,t=num;

叩rintf(〃請輸入由?；?組成的編碼：〃)；

ocin>>str;

〃t=HT；//t為樹的指向各節(jié)點(diǎn)的指針

6for(i=0;i<(str1en(str))；i++)

b{

if(str[i]=='0')

at=HT[t].Ichild；

比1se

<>if(str[i]==，17)

gt=HT[t].rchild;

oelse

81

8printf（〃編碼輸入錯(cuò)誤"）；

。break;

0

if(!(HTLt].lchild&&HT[t].rchild))

(

gprintfHT[t].data);

8t=num;

a)

)

printf(〃\n〃)；

)

voidmain()

(

?voidHuffmanCoding(HuffmanTree&HT,HuffmanCode

&HC,chard[],intw[],intn);

?voidtranslation(HuffmanTreeHT,intnum);

HuffmanTreeHT=NULL;

HuffmanCodeHC=NULL;

?>chardata,n,*p,*d;

int*w,wei,i,num；

printf("pleaseintputcharacternumber：");

oscanf("%d〃，&n);

od=(char*)ma1loc((n+l)*sizeof(char))；

ow=(int^)ma1loc((n+l)*sizeof(int));

printf（"請輸入Huffman樹中的字符：\n"）;

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

*{

。cin>>data;

d[i]=data;

)

fiprintf("請輸入為d次位權(quán)\n:",n);

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

6(

~cin?wei;

w[i]=wei;

?)

num=2*n—1;

HuffmanCoding(HT,HC,d,w,n)：

translation(HT,num);

)

2)程序分析

此實(shí)驗(yàn)是構(gòu)造哈夫曼樹，求出哈夫曼編碼然后輸出

構(gòu)造哈夫曼樹的算法操作時(shí)選出兩棵根節(jié)點(diǎn)的權(quán)值最小的一顆樹的左右

子樹，且置新樹的根節(jié)點(diǎn)的權(quán)值為其左右子樹上根節(jié)點(diǎn)的權(quán)值之和，根據(jù)哈

夫曼樹求出帶權(quán)途徑的算法操作是用遞歸調(diào)用的方法。

在此實(shí)驗(yàn)的操作過程中要注意構(gòu)造哈夫曼樹的方法，由于在此操作的過程中

用的的指針變量特別多，容易混淆。

3)運(yùn)營結(jié)果舉例

,"C:\Users\fzl\Documents\TencentFiles\1125653O39\FileRecv\Debug\llq^§^.exe*［回

pleaseintputcharacternunber：?

請輸入fman樹巾的字符：

1

3

-

-

2

3

4

5

6

z曰110

12,.vf

-1

J0

i-