哈夫曼編碼和譯碼的設(shè)計(jì)與實(shí)現(xiàn)

/算法和數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

哈夫曼編碼和譯碼的設(shè)計(jì)和實(shí)現(xiàn)1.問(wèn)題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道的利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都須要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站設(shè)計(jì)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。2.基本要求a.編/譯碼系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。（5）T：印哈夫曼樹(shù)（Treeprinting）。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式或廣義表）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫入文件TreePrint中。b.測(cè)試數(shù)據(jù)（1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“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程序的基本功能本程序可以對(duì)任何大小的字符型文件進(jìn)行Huffman編碼，生成一個(gè)編碼文件。并可以在程序運(yùn)行結(jié)束后的隨意時(shí)間對(duì)它解碼還原生成字符文件。即：先對(duì)一條電文進(jìn)行輸入，并實(shí)現(xiàn)Huffman編碼，然后對(duì)Huffman編碼生成的代碼串進(jìn)行譯碼，最終輸出電文數(shù)字3.2輸入/輸出形式當(dāng)進(jìn)行編碼時(shí)輸入為原字符文件文件名，當(dāng)程序運(yùn)行編碼完成之后輸入編碼文件名（默認(rèn)名為code.dll）。當(dāng)進(jìn)行譯碼時(shí)輸入為編碼文件名（默認(rèn)名為code.dll），從文件中讀取Huffman編碼樹(shù)后輸入字符文件的文件名。3.3測(cè)試數(shù)據(jù)要求本程序中測(cè)試數(shù)據(jù)主要為字符型文件。4．概要設(shè)計(jì)1.系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）哈弗曼樹(shù)編碼譯碼器哈弗曼樹(shù)編碼譯碼器編碼譯碼退出2．功能模塊說(shuō)明（1）.編碼：提示要編碼的文件文件名→讀取文件→以字母出現(xiàn)次數(shù)為權(quán)值建立哈弗曼樹(shù)→對(duì)文本進(jìn)行哈弗曼編碼并輸出編碼→提示將編碼保存的文件名→保存編碼文件；（2）.譯碼：提示輸入要譯碼的文件名→利用建立好的哈弗曼樹(shù)進(jìn)行譯碼→將譯碼輸出→提示保存譯碼文件的文件名→保存譯碼文件；（3）.退出：退出系統(tǒng)，程序運(yùn)行結(jié)束。5．詳細(xì)設(shè)計(jì)創(chuàng)建哈弗曼樹(shù)起先起先初始化哈夫曼鏈表且有2n-1個(gè)節(jié)點(diǎn)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結(jié)束編碼起先起先將字符存入哈夫曼編碼結(jié)構(gòu)體數(shù)組的字符單元中if(q==q->Parent->LChild)HC[i].code[--HC[i].start]='0'HC[i].code[--HC[i].start]='1'p=p->nextI=n時(shí)結(jié)束譯碼起先起先Root指向根節(jié)點(diǎn)P!=rootcode[i]=='0'p=p->LChildp=p->Rchildp->LChild==NULL&&p->RChild==NULLs[k++]=str[j]p=root結(jié)束6．調(diào)試分析1.從葉子節(jié)點(diǎn)起先向上遍歷二叉樹(shù),獲得哈夫曼編碼;

2.依據(jù)哈夫曼編碼遍歷哈夫曼樹(shù)直到葉子節(jié)點(diǎn),獲得譯碼3.算法的時(shí)間困難度分析：程序部分用雙循環(huán)嵌套結(jié)構(gòu)，時(shí)間困難度為O（n2）.4．算法的空間困難度分析：算法的空間困難度為O（n）5.程序須要反復(fù)調(diào)試，并且調(diào)試過(guò)程比較慢，須要有一個(gè)比較正確的調(diào)試方法，更須要我們有耐性7．用戶運(yùn)用說(shuō)明1.輸入字符的個(gè)數(shù)n2輸入n個(gè)字符和n個(gè)權(quán)值3選擇（1—5）操作可對(duì)huffman樹(shù)進(jìn)行編碼和譯碼以及huffman樹(shù)表的打印4退出系統(tǒng)8．測(cè)試結(jié)果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)/*構(gòu)造哈弗曼樹(shù)*/{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)/*對(duì)字符進(jìn)行編碼*/{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