哈夫曼編碼和譯碼的設計與實現(xiàn)

/算法和數(shù)據(jù)結構課程設計

哈夫曼編碼和譯碼的設計和實現(xiàn)1.問題描述利用哈夫曼編碼進行通信可以大大提高信道的利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都須要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站設計一個哈夫曼碼的編/譯碼系統(tǒng)。2.基本要求a.編/譯碼系統(tǒng)應具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。（5）T：印哈夫曼樹（Treeprinting）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式或廣義表）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。b.測試數(shù)據(jù)（1）利用下面這道題中的數(shù)據(jù)調試程序。某系統(tǒng)在通信聯(lián)絡中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設計哈夫曼編碼。（2）用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THISPROGRAMISMYFAVORITE”。字符空格

A

B

C

D

E

F

G

H

I

J

K

L

M頻度186

64

13

22

32103

21

15

47

57

1

5

32

20字符

N

O

P

Q

R

S

T

U

V

W

X

Y

Z頻度

57

63

15

1

48

51

80

23

8

18

1

16

13．需求分析3.1程序的基本功能本程序可以對任何大小的字符型文件進行Huffman編碼，生成一個編碼文件。并可以在程序運行結束后的隨意時間對它解碼還原生成字符文件。即：先對一條電文進行輸入，并實現(xiàn)Huffman編碼，然后對Huffman編碼生成的代碼串進行譯碼，最終輸出電文數(shù)字3.2輸入/輸出形式當進行編碼時輸入為原字符文件文件名，當程序運行編碼完成之后輸入編碼文件名（默認名為code.dll）。當進行譯碼時輸入為編碼文件名（默認名為code.dll），從文件中讀取Huffman編碼樹后輸入字符文件的文件名。3.3測試數(shù)據(jù)要求本程序中測試數(shù)據(jù)主要為字符型文件。4．概要設計1.系統(tǒng)結構圖（功能模塊圖）哈弗曼樹編碼譯碼器哈弗曼樹編碼譯碼器編碼譯碼退出2．功能模塊說明（1）.編碼：提示要編碼的文件文件名→讀取文件→以字母出現(xiàn)次數(shù)為權值建立哈弗曼樹→對文本進行哈弗曼編碼并輸出編碼→提示將編碼保存的文件名→保存編碼文件；（2）.譯碼：提示輸入要譯碼的文件名→利用建立好的哈弗曼樹進行譯碼→將譯碼輸出→提示保存譯碼文件的文件名→保存譯碼文件；（3）.退出：退出系統(tǒng)，程序運行結束。5．詳細設計創(chuàng)建哈弗曼樹起先起先初始化哈夫曼鏈表且有2n-1個節(jié)點i=1I<np->weight=count[i]p=p->nextfor(i=n;i<2*n-1;i++)HT1->Parent=HT2->Parent=pp->LChild=HT1p->RChild=HT2p->weight=HT1->weight+HT2->weight結束編碼起先起先將字符存入哈夫曼編碼結構體數(shù)組的字符單元中if(q==q->Parent->LChild)HC[i].code[--HC[i].start]='0'HC[i].code[--HC[i].start]='1'p=p->nextI=n時結束譯碼起先起先Root指向根節(jié)點P!=rootcode[i]=='0'p=p->LChildp=p->Rchildp->LChild==NULL&&p->RChild==NULLs[k++]=str[j]p=root結束6．調試分析1.從葉子節(jié)點起先向上遍歷二叉樹,獲得哈夫曼編碼;

2.依據(jù)哈夫曼編碼遍歷哈夫曼樹直到葉子節(jié)點,獲得譯碼3.算法的時間困難度分析：程序部分用雙循環(huán)嵌套結構，時間困難度為O（n2）.4．算法的空間困難度分析：算法的空間困難度為O（n）5.程序須要反復調試，并且調試過程比較慢，須要有一個比較正確的調試方法，更須要我們有耐性7．用戶運用說明1.輸入字符的個數(shù)n2輸入n個字符和n個權值3選擇（1—5）操作可對huffman樹進行編碼和譯碼以及huffman樹表的打印4退出系統(tǒng)8．測試結果9．附錄#include"stdio.h"#include"stdlib.h"#include"string.h"#defineMAX100structHafNode{intweight;intparent;charch;intlchild;intrchild;}*myHaffTree;structCoding{charbit[MAX];charch;intweight;}*myHaffCode;voidHaffman(intn)/*構造哈弗曼樹*/{inti,j,x1,x2,s1,s2;for(i=n+1;i<=2*n-1;i++){s1=s2=10000;x1=x2=0;for(j=1;j<=i-1;j++){if(myHaffTree[j].parent==0&&myHaffTree[j].weight<s1){s2=s1;x2=x1;s1=myHaffTree[j].weight;x1=j;}elseif(myHaffTree[j].parent==0&&myHaffTree[j].weight<s2){s2=myHaffTree[j].weight;x2=j;}}myHaffTree[x1].parent=i;myHaffTree[x2].parent=i;myHaffTree[i].weight=s1+s2;myHaffTree[i].lchild=x1;myHaffTree[i].rchild=x2;}}voidHaffmanCode(intn){intstart,c,f,i,j,k;char*cd;cd=(char*)malloc(n*sizeof(char));myHaffCode=(structCoding*)malloc((n+1)*sizeof(structCoding));cd[n-1]='\0';for(i=1;i<=n;++i){start=n-1;for(c=i,f=myHaffTree[i].parent;f!=0;c=f,f=myHaffTree[f].parent)if(myHaffTree[f].lchild==c)cd[--start]='0';elsecd[--start]='1';for(j=start,k=0;j<n;j++){myHaffCode[i].bit[k]=cd[j];k++;}myHaffCode[i].ch=myHaffTree[i].ch;myHaffCode[i].weight=myHaffTree[i].weight;}free(cd);}voidprint(){printf("*******************************************************************************\n");printf("**********\n");printf("**********\n");printf("*****welcometohuffmancodingandcodeprinting*****\n");printf("**********\n");printf("**********\n");printf("*****1.init2.coding3.codeprinting4.printthehuffman5.exit*****\n");printf("**********\n");printf("*******************************************************************************\n");}Init(){inti,n,m;printf("nowinit\n");printf("pleaseinputthenumberofwords:\n");scanf("%d",&n);m=2*n-1;myHaffTree=(structHafNode*)malloc(sizeof(structHafNode)*(m+1));for(i=1;i<=n;i++){printf("pleaseinputthewordandtheequal:\n");scanf("%s%d",&myHaffTree[i].ch,&myHaffTree[i].weight);myHaffTree[i].parent=0;myHaffTree[i].lchild=0;myHaffTree[i].rchild=0;}for(i=n+1;i<=m;i++){myHaffTree[i].ch='#';myHaffTree[i].lchild=0;myHaffTree[i].parent=0;myHaffTree[i].rchild=0;myHaffTree[i].weight=0;}Haffman(n);HaffmanCode(n);for(i=1;i<=n;i++){printf("%c%d",myHaffCode[i].ch,myHaffCode[i].weight);printf("\n");}printf("initsuccess!\n");returnn;}voidCaozuo_C(intm)/*對字符進行編碼*/{intn,i,j;charstring[50],*p;printf("pleaseinputthewords：\n");scanf("%s",string);n=strlen(string);for(i=1,p=string;i<=n;i++,p++){for(j=1;j<=m;j++)if(myHaffCode[j].ch==*p)printf("%s\n",myHaffCode[j].bit);}}voidCaozuo_D(intn){inti,c;charcode[1000],*p;printf("pleaseinputthecoding：\n");scanf("%s",code);for(p=code,c=2*n-1;*p!='\0';p++){if(*p=='0'){c=myHaffTree[c].lchild;if(myHaffTree[c].lchild==0){printf("%c",myHaffTree[c].ch);c=2*n-1;continue;}}elseif(*p=='1'){c=myHaffTree[c].rchild;if(myHaffTree[c].lchild==0){printf("%c",myHaffTree[c].ch);c=2*n-1;continue;}}}printf("\n");}voidCaozuo_T(intn){inti;printf("wordequalleftchildrightchildprents\n");for(i=1;i<=2*n-1;i++)printf("%c%d%d%d%d\n",myHaffTree[i].ch,myHaffTree[i].weight,myHaffTree[i].lchild,myHaffTree[i].rchild,myHaffTree[i].parent);}main(){intn;charchar1;print();n=Init();while(1){prin