西工大數(shù)據(jù)結(jié)構(gòu)報告 哈夫曼樹編碼譯碼

1、數(shù)據(jù)結(jié)構(gòu)實驗報告一實驗題目編寫一個程序，實現(xiàn)哈夫曼樹的編碼和譯碼。二程序設(shè)計 (一) 需求分析1需要編寫這樣一個程序，有以下功能：（1）能夠輸出不同英文字母所代表的權(quán)值；（2）能夠根據(jù)輸入結(jié)點的字母的權(quán)值，生成哈夫曼樹，并得到每個結(jié)點的哈夫曼編碼；（3）能夠在功能2的基礎(chǔ)上，將輸入的哈夫曼編碼翻譯為字母。2.程序運行步驟：（1）開始；（2）選擇要實現(xiàn)的運算：1.輸出字母與權(quán)值的對應(yīng)關(guān)系表 2.將字符編譯為哈夫曼樹 3.將哈夫曼樹譯碼；（3）選擇運算后，程序輸出運算結(jié)果；（4）結(jié)束。（二）概要設(shè)計程序模塊及思想：1.主函數(shù)主函數(shù)包括定義變量和算法兩部分。算法由switch-case結(jié)構(gòu)構(gòu)成。Ca

2、se有三種情況：（1） 輸出權(quán)值表；（2） 哈夫曼樹的編碼：（1） 輸入要編碼的字母；（2） 以表格形式輸出哈夫曼樹；（3） 輸出每個字符的哈夫曼編碼；（4） 結(jié)束；（3） 哈弗曼樹的譯碼：（1） 建立哈夫曼樹：（1）輸入要編碼的字母；（2）以表格形式輸出哈夫曼樹；（3）輸出每個字符的哈夫曼編碼；（4）結(jié)束； （2） 將哈夫曼編碼翻譯為字母： （1）輸入哈弗曼編碼； （2）輸出翻譯結(jié)果； （3）結(jié)束；（3）結(jié)束。2基本操作。typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; 操作結(jié)果：動態(tài)分配數(shù)組儲

3、存哈夫曼樹。typedef char *HuffmanCode;操作結(jié)果：動態(tài)分配數(shù)組儲存哈夫曼編碼表。void Error(char *message);操作結(jié)果：輸出錯誤的原因。void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n); 操作結(jié)果：對字母進(jìn)行哈夫曼樹的編碼。void Select(HuffmanTree &HT, int n,int *s1,int *s2);操作結(jié)果：選擇多個節(jié)點中權(quán)值最小的兩個結(jié)點 void Decoding(HuffmanTree HT,char Ch,

4、char letter,int n);操作結(jié)果：將存在在已知哈夫曼樹中的哈夫曼編碼翻譯為字母。（三）詳細(xì)設(shè)計1結(jié)構(gòu)體定義typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; 操作結(jié)果：動態(tài)分配數(shù)組儲存哈夫曼樹。typedef char *HuffmanCode;操作結(jié)果：動態(tài)分配數(shù)組儲存哈夫曼編碼表。2.每個模塊的分析：（1） 主程序模塊：int main() HuffmanTree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,j,n,a; cha

5、r letter100,code500; /初始化 char 、str1='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V'

6、,'W','X','Y','Z', str2='a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','

7、u','v','w','x','y','z' int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /權(quán)值表 printf("請選擇要進(jìn)行的操作：1.顯示權(quán)值表 2.將字符編碼 3.翻譯哈夫曼碼 n"); scanf("%d",&a); switch(a) case 1: for(i=1;i<=26;i+) /輸出權(quán)值表 printf(&q

8、uot;%c %c %dtt",str1i-1,str2i-1,fnumi-1); printf("n");break; case 2: printf("請輸入要編碼的電文：n"); scanf("n"); gets(letter); n=strlen(letter); w=( int *)malloc(n+1)*sizeof( int *); /創(chuàng)建n+1個單元儲存字母的權(quán)值 w0=0; for(i=1;i<=n;i+) if(letteri-1>64 && letteri-1<91) j

9、=1; while (letteri-1!=str1j-1) +j; wi=fnumj-1; /w儲存每個字母的權(quán)值if(letteri-1>96 && letteri-1<123)j=1;while (letteri-1!=str2j-1) +j; wi=fnumj-1; /w儲存每個字母的權(quán)值 HuffmanCoding(HT,HC,w,n); /建立哈夫曼樹，并輸出 printf("HuffmanCode如下所示:n"); printf("NumberttLetterttWeightttCoden"); for(i=1;

10、i<=n;i+) /依次輸出編號，字母，權(quán)值，和哈夫曼編碼 printf("%dtt",i); printf("%ctt",letteri-1); printf("%dtt%sn",wi,HCi); / printf("n"); break; case 3: printf("先輸入一個拉丁字符串：n"); scanf("n"); gets(letter); n=strlen(letter); w=( int *)malloc(n+1)*sizeof( int *); /

11、創(chuàng)建n+1個單元儲存字母的權(quán)值 w0=0; for(i=1;i<=n;i+) if(letteri-1>64 && letteri-1<91) j=1; while (letteri-1!=str1j-1) +j; wi=fnumj-1; /w儲存每個字母的權(quán)值 if(letteri-1>96 && letteri-1<123)j=1;while (letteri-1!=str2j-1) +j; wi=fnumj-1; /w儲存每個字母的權(quán)值 HuffmanCoding(HT,HC,w,n); /建立哈夫曼樹，并輸出 printf(

12、"HuffmanCode如下所示:n"); printf("NumberttLetterttWeightttCoden"); for(i=1;i<=n;i+) printf("%dtt",i); printf("%ctt",letteri-1); printf("%dtt%sn",wi,HCi); /依次輸出編號，字母，權(quán)值，和哈夫曼編碼; printf("請輸入要翻譯的哈夫曼編碼：n"); gets(code); /根據(jù)先前的哈夫曼編碼表，輸入哈夫曼編碼 Decodi

13、ng(HT,code,letter,n); /哈夫曼編碼譯為字母 printf("n"); break; return 0; （2）基本操作函數(shù)：（1）輸出錯誤的原因void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1); /輸出出現(xiàn)錯誤的原因（2）建哈夫曼樹函數(shù)void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n) /w存放n個字符的權(quán)值，構(gòu)造哈夫曼樹HT，并求出n個字符的哈

14、夫曼編碼HC int i,s1,s2; HuffmanTree p; char *cd; int f,c,start,m; if(n<=1) Error("輸入數(shù)據(jù)太少!"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0號單元未用for(p=HT,i=0;i<=n;i+,p+,w+) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; for(;i<=m;i+,p+) p->weight=0; p->

15、parent=0; p->lchild=0; p->rchild=0; for(i=n+1;i<=m;i+) /建立哈夫曼樹 /在哈夫曼樹中選擇parent為零且weight最小的兩個結(jié)點，其序號分別為s1和s2。Select(HT,i-1,&s1,&s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight= HTs1.weight + HTs2.weight; printf("HT List:n"); printf("Numberttw

16、eightttparentttlchildttrchildn"); /輸出序號，權(quán)值，父節(jié)點，左孩子和右孩子 for(i=1;i<=m;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); /從葉子到根逆向求每個字符的哈夫曼編碼 HC=(HuffmanCode)malloc(n+1) * sizeof(char *); /分配n個字符編碼的頭指針 cd=(char *)malloc(n* sizeof(char *); /分配求編碼的工作空間 cdn-

17、1='0' /編碼結(jié)束符 for(i=1;i<=n;i+) /逐個字符求哈夫曼編碼 start=n-1; /編碼結(jié)束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /從葉子向根逆向求編碼 if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char *); /為第i個字符編碼分配空間 strcpy(HCi,&cdstart); /從Cd復(fù)制字符串到HC free(cd);

18、/釋放空間 （3）選擇權(quán)值最小的兩個結(jié)點void Select(HuffmanTree &HT,int num,int *s1,int *s2) /變量：哈夫曼樹，節(jié)點數(shù)，兩個指針int i; for(i=1;i<=num;i+)if(HTi.parent=0)*s1=i; break; /S1指向頭結(jié)點for(i=1;i<=num;i+)if(HTi.parent=0)if(HT*s1.weight>HTi.weight)*s1=i; /s1指向權(quán)值最小的結(jié)點 for(i=1;i<=num;i+) if(i=*s1) continue; else if(HTi

19、.parent=0)*s2=i; break;for(i=1;i<=num;i+)if(HTi.parent=0) if(i=*s1) continue; else if(HT*s2.weight>=HTi.weight) *s2=i; /s2指向次小結(jié)點 （4）譯碼函數(shù)。void Decoding(HuffmanTree HT,char Ch,char letter,int n) /已知哈夫曼樹，一個用以儲存編碼的字符數(shù)組，一個用以儲存譯碼的字符數(shù)組，和輸入字符串的長度 int leave; char *p; p=Ch;printf("譯碼結(jié)果如下：n");

20、while(*p!='0') leave=2*n-1; /剩余空間為2*n-1 while(HTleave.lchild!=0) /左孩子存在時 if(*p='0') leave=HTleave.lchild; /如果哈夫曼編碼為0，是左孩子 else leave=HTleave.rchild; /否則是右孩子 p+; /指向下一節(jié)點 printf("%c",letterleave-1); /輸出譯碼結(jié)果 printf("n");四程序使用說明及測試結(jié)果程序使用和測試的截圖如下：1.顯示權(quán)值表2.將字符編為哈夫曼碼3.將哈

21、夫曼樹譯碼。五）、實驗總結(jié)(實驗心得)1.你在編程過程中花時多少？ 答：從設(shè)計到編寫，從調(diào)試到完成，直至最終完成實驗報告一共用了約八個小時。2.多少時間在紙上設(shè)計？答：兩個小時。3.多少時間上機輸入和調(diào)試？答：四個多小時。4.多少時間在思考問題？答：設(shè)計前就思考，直至完成報告，十多個小時。5.遇到了哪些難題？又是怎么克服的？答：1.知識掌握不熟練?？朔椒ǎ赫J(rèn)真閱讀教科書及有關(guān)資料中的相關(guān)知識。 2.算法編不出來或錯誤百出。解決方法：借鑒課本和有關(guān)資料中的算法，自己努力思考編寫，向同學(xué)學(xué)習(xí)。算法出現(xiàn)錯誤，慢慢調(diào)試，發(fā)現(xiàn)錯誤并不斷改進(jìn)，直到完成程序編寫。6.你的收獲有哪些？答：首先，我對哈夫曼書

22、樹的知識有了更多了解，破除了錯誤的認(rèn)識。其次，通過這次作業(yè)，我掌握了幾種與哈夫曼樹有關(guān)的算法。最后，我還溫習(xí)了有關(guān)C語言的許多知識。 參考文獻(xiàn)：【1】嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu) 清華大學(xué)出版社【2】朱明方 吳及數(shù)據(jù)結(jié)構(gòu)與算法教程人民郵電出版社附：完整程序#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode;

23、void Error(char *message); void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n); void Select(HuffmanTree &HT, int n,int *s1,int *s2); void Decoding(HuffmanTree HT,char Ch,char letter,int n); void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1); v

24、oid HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n) /建哈夫曼樹函數(shù) int i,s1,s2; HuffmanTree p; char *cd; int f,c,start,m; if(n<=1) Error("輸入數(shù)據(jù)太少!"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT,i=0;i<=n;i+,p+,w+) p->weight=*w; p->parent=0; p->

25、;lchild=0; p->rchild=0; for(;i<=m;i+,p+) p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; for(i=n+1;i<=m;i+) Select(HT,i-1,&s1,&s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight= HTs1.weight + HTs2.weight; printf("HT List:n"); print

26、f("Numberttweightttparentttlchildttrchildn"); for(i=1;i<=m;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); HC=(HuffmanCode)malloc(n+1) * sizeof(char *); cd=(char *)malloc(n* sizeof(char *); cdn-1='0' for(i=1;i<=n;i+) start=n-1; for(c

27、=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char *); strcpy(HCi,&cdstart); free(cd); void Select(HuffmanTree &HT,int num,int *s1,int *s2) /選擇權(quán)值最小的兩個結(jié)點int i; for(i=1;i<=num;i+)if(HTi.parent=0)*s1=

28、i; break;for(i=1;i<=num;i+)if(HTi.parent=0)if(HT*s1.weight>HTi.weight)*s1=i; /從首到尾找出權(quán)值最小的 for(i=1;i<=num;i+) if(i=*s1) continue; else if(HTi.parent=0)*s2=i; break;for(i=1;i<=num;i+)if(HTi.parent=0) if(i=*s1) continue; else if(HT*s2.weight>=HTi.weight) *s2=i;void Decoding(HuffmanTree H

29、T,char Ch,char letter,int n) /譯碼函數(shù) int leave; char *p; p=Ch;printf("譯碼結(jié)果如下：n"); while(*p!='0') leave=2*n-1; while(HTleave.lchild!=0) if(*p='0')leave=HTleave.lchild; else leave=HTleave.rchild; p+; printf("%c",letterleave-1); printf("n");int main() Huffman

30、Tree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,j,n,a; char letter100,code500; char str1='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q',&

31、#39;R','S','T','U','V','W','X','Y','Z', str2='a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p&

32、#39;,'q','r','s','t','u','v','w','x','y','z' /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; printf("請選擇要進(jìn)行的操作：1.顯示權(quán)值表 2.將字符編碼 3.翻譯哈夫曼碼 n"); scanf("%d",&a

33、); switch(a) case 1: for(i=1;i<=26;i+) printf("%c %c %dtt",str1i-1,str2i-1,fnumi-1); printf("n");break; case 2: printf("請輸入要編碼的電文：n"); scanf("n"); gets(letter); n=strlen(letter); w=( int *)malloc(n+1)*sizeof( int *); w0=0; for(i=1;i<=n;i+) if(letteri-1>64 && letteri-1<91) j=1; wh