《數(shù)據(jù)結(jié)構(gòu)實驗報告(哈夫曼樹)》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)實驗報告(哈夫曼樹)（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

4、&S,char e);此函數(shù)為出棧操作。7. void Push(SqStack &S,char e);此函數(shù)為進棧操作。8. int StackLength(SqStack S);此函數(shù)用于求棧長，返回一個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,int n);此函數(shù)用于將比特流還原成電文。調(diào)試分析： 輸入任意一個字符串，如輸入welcometoustc:運行結(jié)果如下：按照提示輸入任

5、意一個或多個哈弗曼編碼，如輸入11111110101：結(jié)果正確。若輸入一個11111：結(jié)果正確。實驗完成！實驗體會和收獲：本次實驗提高了對哈弗曼樹的認識，同時加深了對二叉樹的理解，在棧的運用上更加熟練，對數(shù)組的應(yīng)用也有了提高。源代碼：#include#include#include#includetypedef structint weight;int parent,lc,rc;HTNode,*HuffmanTree;typedef struct LNodechar *elem;int stacksize;int top;SqStack;#define size 20void HuffTree

6、(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(SqS

7、tack 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;char stringsize=0,msize=0,asize=0,bsize=0;char* HC;HuffmanTree HT;printf(請輸入電文串:n);scanf(%s,string);strcpy(m,string);while(stringj)if(stringj!=#) ak=st

8、ringj;i=j;while(stringi)if(stringi=ak)stringi=#;nk+;i+;if(nk!=0) printf(該電文中字符%c出現(xiàn)次數(shù)為%dn,ak,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,a

9、i,HCi);printf(n該電文的哈弗曼編碼為:n);i=0;while(stringi) printf(%s,HCFind(mi+,a,num);printf(n請輸入哈弗曼編碼：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 num)int i,m,s1,s2;m=2*num-1;HT=(HuffmanTree)malloc(m+1)*s

10、izeof(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 &HT,int n,int i,int &s1,int &s2)int k,t;s1=s2=-1;k=1;while(s1=-1)if(HTk.par

11、ent=0)s1=k;k+;k=1;while(s2=-1|s2=s1)if(HTk.parent=0)s2=k;k+;if(HTs2.weightHTs1.weight) t=s2;s2=s1;s1=t;for(k=1;ki;k+)if(HTk.parent=0)if(HTk.weightHTs1.weight&k!=s1&k!=s2) s2=s1;s1=k;else if(HTk.weight=HTs1.weight&k!=s1&k!=s2) s2=k;void HuffmanCoding(HuffmanTree HT,char *&HC,int n)SqStack S;InitStack

12、(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(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

13、);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.elemS.top-;return;int StackLength(SqStack S)if(S.top=-1) return(0);return(S.top);int Find(char a,char s

14、,int num)int i;for(i=1;i=num;i+)if(a=si) 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 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;sj=1;j+;t=0;if(!t)i+;if(!HTk.lc&!HTk.rc)if(stringi-1=0) sj=0;k=2*n-1;j=0;if(stringi-1=1) sj=0;k=2*n-1;t=1;j=0;for(h=1;h=n;h+)if(!strcmp(HCh,s) bm+=ah;bm=0;if(k=2*n-1) return 1;else return 0;