數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目： Huffman編碼與解碼 姓名： 學(xué)號(hào)： 院系：實(shí)驗(yàn)名稱(chēng)： Huffman編碼與解碼實(shí)驗(yàn)問(wèn)題描述： 本實(shí)驗(yàn)需要以菜單形式完成以下功能：1.輸入電文串2.統(tǒng)計(jì)電文串中各個(gè)字符及其出現(xiàn)的次數(shù)3.構(gòu)造哈弗曼樹(shù)4.進(jìn)行哈弗曼編碼5.將電文翻譯成比特流并打印出來(lái)6.將比特流還原成電文數(shù)據(jù)結(jié)構(gòu)的描述：邏輯結(jié)構(gòu)： 本實(shí)驗(yàn)可用二叉樹(shù)實(shí)現(xiàn)，其邏輯結(jié)構(gòu)為一對(duì)二的形式，即一個(gè)結(jié)點(diǎn)對(duì)應(yīng)兩個(gè)結(jié)點(diǎn)。在實(shí)驗(yàn)過(guò)程中我們也應(yīng)用到了棧的概念。存儲(chǔ)結(jié)構(gòu)： 使用結(jié)構(gòu)體來(lái)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)：typedef structint weight;int parent,lc,rc;HTNode,*HuffmanTree;typedef struct LNodechar *elem;int stacksize;int top;SqStack;在main函數(shù)里面定義一個(gè)哈弗曼樹(shù)并實(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)建哈弗曼樹(shù)，n用于存放num個(gè)權(quán)值。 2.void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);此函數(shù)用于在HT1,i-1中選擇parent為0且weight為最小的兩個(gè)結(jié)點(diǎn)，其 下標(biāo)分別為s1,s2.3. void HuffmanCoding(HuffmanTree HT,char *&HC,int n);此函數(shù)從哈弗曼樹(shù)HT上求得n 個(gè)葉子結(jié)點(diǎn)的哈弗曼編碼并存入數(shù)組HC中。4. void Coding(HuffmanTree HT,char *HC,int root,SqStack &S)；此函數(shù)用于哈弗曼編碼，先序遍歷哈弗曼樹(shù)HT，求得每個(gè)葉子結(jié)點(diǎn)的編碼字符串，存入數(shù)組HC，S為一個(gè)順序棧，用來(lái)記錄遍歷路徑，root是哈弗曼數(shù)組HT中根結(jié)點(diǎn)的位置下標(biāo)。5. void InitStack(SqStack &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,int n);此函數(shù)用于將比特流還原成電文。調(diào)試分析： 輸入任意一個(gè)字符串，如輸入welcometoustc:運(yùn)行結(jié)果如下：按照提示輸入任意一個(gè)或多個(gè)哈弗曼編碼，如輸入11111110101：結(jié)果正確。若輸入一個(gè)11111：結(jié)果正確。實(shí)驗(yàn)完成！實(shí)驗(yàn)體會(huì)和收獲：本次實(shí)驗(yàn)提高了對(duì)哈弗曼樹(shù)的認(rèn)識(shí)，同時(shí)加深了對(duì)二叉樹(shù)的理解，在棧的運(yùn)用上更加熟練，對(duì)數(shù)組的應(yīng)用也有了提高。源代碼：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>typedef structint weight;int parent,lc,rc;HTNode,*HuffmanTree;typedef struct LNodechar *elem;int stacksize;int top;SqStack;#define size 20void 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,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 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("請(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,nk);num+;k+;j+; printf("哈弗曼樹(shù):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=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 num)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 &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+;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;else if(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!=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(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,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;