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

1、.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：Huffman編碼與解碼：學(xué)號(hào)：院系：.實(shí)驗(yàn)名稱：Huffman 編碼與解碼實(shí)驗(yàn)問題描述：本實(shí)驗(yàn)需要以菜單形式完成以下功能：1.輸入電文串2.統(tǒng)計(jì)電文串中各個(gè)字符及其出現(xiàn)的次數(shù)3.構(gòu)造哈弗曼樹4.進(jìn)行哈弗曼編碼5.將電文翻譯成比特流并打印出來6.將比特流還原成電文數(shù)據(jù)結(jié)構(gòu)的描述：邏輯結(jié)構(gòu)：本實(shí)驗(yàn)可用二叉樹實(shí)現(xiàn)，其邏輯結(jié)構(gòu)為一對(duì)二的形式，即一個(gè)結(jié)點(diǎn)對(duì)應(yīng)兩個(gè)結(jié)點(diǎn)。在實(shí)驗(yàn)過程中我們也應(yīng)用到了棧的概念。存儲(chǔ)結(jié)構(gòu)：使用結(jié)構(gòu)體來對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)：typedef weight;int parent,lc,rc;HTNode,*HuffmanTree;typed

2、ef struct LNodechar *elem;int stacksize;int top;SqStack;在 main 函數(shù)里面定義一個(gè)哈弗曼樹并實(shí)現(xiàn)上述各種功能。程序結(jié)構(gòu)的描述：本次實(shí)驗(yàn)一共構(gòu)造了10 個(gè)函數(shù)：1.void HuffTree(HuffmanTree &HT,int n,int mun);此函數(shù)根據(jù)給定的mun 個(gè)權(quán)值構(gòu)建哈弗曼樹，n用于存放 num 個(gè)權(quán)值。2.void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);此函數(shù)用于在 HT1,i-1 中選擇 parent 為 0 且 w

3、eight 為最小的兩個(gè)結(jié)點(diǎn)， 其下標(biāo)分別為 s1,s2.3.void HuffmanCoding(HuffmanTree HT,char *&HC,int n);此函數(shù)從哈弗曼樹HT 上求得n 個(gè)葉子結(jié)點(diǎn)的哈弗曼編碼并存入數(shù)組HC中。4.void Coding(HuffmanTree HT,char *HC,int root,SqStack &S) ；.此函數(shù)用于哈弗曼編碼，先序遍歷哈弗曼樹HT，求得每個(gè)葉子結(jié)點(diǎn)的編碼字符串，存入數(shù)組HC，S 為一個(gè)順序棧，用來記錄遍歷路徑，root 是哈弗曼數(shù)組 HT 中根結(jié)點(diǎn)的位置下標(biāo)。5.void InitStack(SqStack &

4、amp;S);此函數(shù)用于初始化一個(gè)棧。6.void Pop(SqStack &S,char e);此函數(shù)為出棧操作。7.void Push(SqStack &S,char e);此函數(shù)為進(jìn)棧操作。8.int StackLength(SqStack S);此函數(shù)用于求棧長(zhǎng)，返回一個(gè)int 型的值。9.int Find(char a,char s,int num);此函數(shù)用于查找字符a 在電文串中的位置。10.int Recover(HuffmanTree HT,char *HC,char string,char a,char b,intn);此函數(shù)用于將比特流還原成電文。調(diào)試分析

5、：輸入任意一個(gè)字符串，如輸入welcometoustc: 運(yùn)行結(jié)果如下：.按照提示輸入任意一個(gè)或多個(gè)哈弗曼編碼，如輸入11111110101 ：結(jié)果正確。若輸入一個(gè)11111 ：結(jié)果正確。.實(shí)驗(yàn)完成！實(shí)驗(yàn)體會(huì)和收獲：本次實(shí)驗(yàn)提高了對(duì)哈弗曼樹的認(rèn)識(shí)，同時(shí)加深了對(duì)二叉樹的理解， 在棧的運(yùn)用上更加熟練，對(duì)數(shù)組的應(yīng)用也有了提高。源代碼：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>typedef structint weight;int parent,lc,r

6、c;HTNode,*HuffmanTree;typedef struct LNodechar *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,c

7、har *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,nsize=0,j=0,k=1,num=0;cha

8、r stringsize=0,msize=0,asize=0,bsize=0;char* HC;HuffmanTree HT;printf(" 請(qǐng)輸入電文串 :n");scanf("%s",string);strcpy(m,string);while(stringj)if(stringj!='#') ak=stringj;.i=j;while(stringi)if(stringi=ak)stringi='#'nk+;i+;if(nk!=0)printf(" 該電文中字符 %c出現(xiàn)次數(shù)為 %dn",ak,

9、nk);num+;k+;j+;printf(" 哈弗曼樹 :n");HuffTree(HT,n,num);for(i=1;i<=2*num-1;i+)printf("%dt%dt%dt%dn",HTi.weight,HTi.parent,HTi.lc,HTi.rc);.printf(" 哈弗曼編碼 :n");HuffmanCoding(HT,HC,num);for(i=1;i<=num;i+)printf("%c : %sn",ai,HCi);printf("n 該電文的哈弗曼編碼為 :n&q

10、uot;);i=0;while(stringi)printf("%s",HCFind(mi+,a,num);printf("n 請(qǐng)輸入哈弗曼編碼： n");scanf("%s",string);if(Recover(HT,HC,string,a,b,num) printf("%sn",b);else printf(" 代碼有誤 !n");system("pause");return 0;void HuffTree(HuffmanTree &HT,int n,int n

11、um)int i,m,s1,s2;m=2*num-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);.for(i=1;i<=m;i+)HTi.weight=i<=num?ni:0;HTi.lc=HTi.rc=HTi.parent=0;for(i=num+1;i<=m;i+)Select(HT,num,i,s1,s2);HTi.lc=s1;HTi.rc=s2;HTi.weight=HTs1.weight+HTs2.weight;HTs1.parent=HTs2.parent=i;void Select(HuffmanTree &H

12、T,int n,int i,int &s1,int &s2)int k,t;s1=s2=-1;k=1;while(s1=-1)if(HTk.parent=0).s1=k;k+;k=1;while(s2=-1|s2=s1)if(HTk.parent=0)s2=k;k+;if(HTs2.weight<HTs1.weight)t=s2;s2=s1;s1=t;for(k=1;k<i;k+)if(HTk.parent=0)if(HTk.weight<HTs1.weight&&k!=s1&&k!=s2)s2=s1;s1=k;.elseif(

13、HTk.weight<HTs2.weight&&HTk.weight>=HTs1.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!

14、=0)if(HTroot.lc=0).Push(S,'0');HCroot=(char*)malloc(StackLength(S);strcpy(HCroot,S.elem);Pop(S,'0');Push(S,'0');Coding(HT,HC,HTroot.lc,S);Pop(S,'0');Push(S,'1');Coding(HT,HC,HTroot.rc,S);Pop(S,'0');void InitStack(SqStack &S)S.elem=(char *)malloc(si

15、ze*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.elemS.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=si) return

16、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 ssize;k=2*n-1;while(stringi)if(!HTk.lc&&!HTk.rc)if(stringi='0') sj='0'k=2*n-1;t=1;j=0;if(stringi='1')sj='0'k=2*n-1;t=1;j=0;for(h=1;h<=n;h+)if(!strcmp(HCh,s)bm+=ah;elseif(stringi='0') k=HTk.lc;sj+='0'.if(stringi='1')k=HTk.rc;s