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

1、算法與數(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）。利用已建好的

2、哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。（5）T：印哈夫曼樹（Tree printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式或廣義表）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。b.測

3、試數(shù)據(jù)（1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(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)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符 空格  A   B   C   D   E   F   G   H   I 

4、  J   K   L   M頻度 186   64  13  22  32 103  21  15  47  57  1   5   32  20字符  N    O   P   Q   R   S   T   U&#

5、160;  V   W   X   Y   Z頻度  57   63  15  1   48  51  80  23  8   18  1   16  1 3需求分析3.1程序的基本功能本程序可以對任何大小的字符型文件進行Huffman編碼，生成一個編碼文件。并可以在程序運行結束后的任意時間對它解碼還原生成字符文件。即：先對一條電文進行輸

6、入，并實現(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ù)為權值建立哈弗曼樹對文本進行哈弗曼編碼并輸出編碼提示將編碼保存的文件名保存編碼文

7、件；（2）.譯碼：提示輸入要譯碼的文件名利用建立好的哈弗曼樹進行譯碼將譯碼輸出提示保存譯碼文件的文件名保存譯碼文件；（3）.退出：退出系統(tǒng)，程序運行結束。5詳細設計創(chuàng)建哈弗曼樹開始初始化哈夫曼鏈表且有2n-1個節(jié)點i=1I<np->weight=countip=p->nextfor(i=n;i<2*n-1;i+)HT1->Parent=HT2->Parent=pp->LChild=HT1p->RChild=HT2p->weight=HT1->weight+HT2->weight結束編碼開始將字符存入哈夫曼編碼結構體數(shù)組的字符單元

8、中if(q=q->Parent->LChild)HCi.code-HCi.start='0'HCi.code-HCi.start='1'p=p->nextI=n 時結束譯碼開始Root指向根節(jié)點P!=rootcodei='0'p=p->LChildp=p->Rchildp->LChild=NULL&&p->RChild=NULLsk+=strjp=root結束6調(diào)試分析1.從葉子節(jié)點開始向上遍歷二叉樹,獲得哈夫曼編碼; 2.根據(jù)哈夫曼編碼遍歷哈夫曼樹直到葉子節(jié)點,獲得譯碼 3.算法的時間復

9、雜度分析：程序部分用雙循環(huán)嵌套結構，時間復雜度為O（n2）. 4算法的空間復雜度分析：算法的空間復雜度為O（n）5. 程序需要反復調(diào)試，并且調(diào)試過程比較慢，需要有一個比較正確的調(diào)試方法，更需要我們有耐心7用戶使用說明1.輸入字符的個數(shù)n 2輸入n個字符和n個權值3 選擇（15）操作可對huffman樹進行編碼和譯碼以及huffman樹表的打印4 退出系統(tǒng)8測試結果9附錄#include "stdio.h"#include "stdlib.h"#include "string.h"#define MAX 100struct HafNod

10、e int weight; int parent; char ch; int lchild; int rchild;*myHaffTree;struct Coding char bitMAX; char ch; int weight;*myHaffCode;void Haffman(int n)/* 構造哈弗曼樹 */ int i,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(myHaffTreej.parent=0&&myHaffTreej.w

11、eight<s1) s2=s1; x2=x1; s1=myHaffTreej.weight; x1=j; else if(myHaffTreej.parent=0&&myHaffTreej.weight<s2) s2=myHaffTreej.weight; x2=j; myHaffTreex1.parent=i; myHaffTreex2.parent=i; myHaffTreei.weight=s1+s2; myHaffTreei.lchild=x1; myHaffTreei.rchild=x2; void HaffmanCode(int n) int start

12、,c,f,i,j,k; char *cd; cd=(char *)malloc(n*sizeof(char); myHaffCode=(struct Coding *)malloc(n+1)*sizeof(struct Coding); cdn-1='0' for(i=1;i<=n;+i) start=n-1; for(c=i,f=myHaffTreei.parent;f!=0;c=f,f=myHaffTreef.parent) if(myHaffTreef.lchild=c) cd-start='0' else cd-start='1'

13、for(j=start,k=0;j<n;j+) myHaffCodei.bitk=cdj; k+; myHaffCodei.ch=myHaffTreei.ch; myHaffCodei.weight=myHaffTreei.weight; free(cd);void print() printf("*n"); printf("* *n"); printf("* *n"); printf("* welcome to huffman coding and codeprinting *n"); printf(&qu

14、ot;* *n"); printf("* *n"); printf("*1.init 2.coding 3.codeprinting 4.print the huffman 5.exit *n"); printf("* *n"); printf("*n");Init() int i,n,m; printf("now initn"); printf("please input the number of words:n"); scanf("%d",

15、&n); m=2*n-1; myHaffTree=(struct HafNode *)malloc(sizeof(struct HafNode)*(m+1); for(i=1;i<=n;i+) printf("please input the word and the equal:n"); scanf("%s%d",&myHaffTreei.ch,&myHaffTreei.weight); myHaffTreei.parent=0; myHaffTreei.lchild=0; myHaffTreei.rchild=0; fo

16、r(i=n+1;i<=m;i+) myHaffTreei.ch ='#' myHaffTreei.lchild=0; myHaffTreei.parent=0; myHaffTreei.rchild=0; myHaffTreei.weight=0; Haffman(n); HaffmanCode(n); for(i=1;i<=n;i+) printf("%c %d",myHaffCodei.ch,myHaffCodei.weight); printf("n"); printf("init success!n"

17、;); return n;void Caozuo_C(int m)/* 對字符進行編碼 */ int n,i,j; char string50,*p; printf("please input the words：n"); scanf("%s",string); n=strlen(string); for(i=1,p=string;i<=n;i+,p+) for(j=1;j<=m;j+) if(myHaffCodej.ch=*p) printf("%sn",myHaffCodej.bit); void Caozuo_D(i

18、nt n) int i,c; char code1000,*p; printf("please input the coding：n"); scanf("%s",code); for(p=code,c=2*n-1;*p!='0'p+) if(*p='0') c=myHaffTreec.lchild; if(myHaffTreec.lchild=0) printf("%c",myHaffTreec.ch); c=2*n-1; continue; else if(*p='1') c=myHaffTreec.rchild; if(myHaffTreec.lchild=0) printf("%c",myHaffTreec.ch); c=2*n-1; continue; printf("n")