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

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

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

4、k &S,char e);此函數(shù)為進(jìn)棧操作。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:運(yùn)行結(jié)果如下：習(xí),習(xí),習(xí),習(xí),習(xí),習(xí),習(xí),習(xí),習(xí),次次次次次次次次次現(xiàn)現(xiàn)現(xiàn)現(xiàn)現(xiàn)現(xiàn)現(xiàn)現(xiàn)現(xiàn)rrrrrr出出出出出出出出

5、出O4XXXXXX于: TOC o 1-5 h z 4164io12141&16is哈弗曼編碼： bl : 1110 e : 911 1 : 1111 E : 180 : 101 n - 000 t : 119 LL : 001 S : 010該電文的哈弗景編碼為： 11100111111100101000011110101001010110100 請輸入哈弗曼編碼：按照提示輸入任意一個或多個哈弗曼編碼，如輸入11111110101 :請輸入哈弗景編碼:11111110101 1U0結(jié)果正確。若輸入一個11111 :請輸入哈弗景編碼,11111mi?結(jié)果正確。實(shí)驗(yàn)完成

6、！實(shí)驗(yàn)體會和收獲:本次實(shí)驗(yàn)提高了對哈弗曼樹的認(rèn)識，同時加深了對二叉樹的理解，在棧的運(yùn)用上 更加熟練，對數(shù)組的應(yīng)用也有了提高。源代碼：#include#include#include#includetypedef structint weight;int parent,lc,rc;HTNode,*HuffmanTree;typedef struct LNode char *elem;int stacksize;int top;SqStack;#define size 20void HuffTree(HuffmanTree &HT,int n,int mun);void Select(Huffma

7、nTree &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 Recove

8、r(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=stringj;i=i；while(stringi)if(stringi=ak)stringi =

9、#;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,ai,HCi);printf(n該電文的哈弗曼編碼為:n);i=

10、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)*sizeof(HTNode);for(i = 1;i =

11、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.parent=0)s1=k;k+;

12、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;elseif(HTk.weight = HTs1.weight&k!=s1&k!二s2) s2=k;void HuffmanCoding(HuffmanTree HT,char *&HC,int n)SqStack S;InitStack(S);HC=(c

13、har*)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);Pop(S,0

14、);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,in

15、t 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 +