1、算法與數據結構課程設計哈夫曼編碼和譯碼的設計與實現1.問題描述利用哈夫曼編碼進行通信可以大大提高信道的利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統。試為這樣的信息收發站設計一個哈夫曼碼的編/譯碼系統。2.基本要求a.編/譯碼系統應具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的

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

3、試數據（1）利用下面這道題中的數據調試程序。某系統在通信聯絡中只可能出現八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設計哈夫曼編碼。（2）用下表給出的字符集和頻度的實際統計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符 空格 A B C D E F G H I 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 V W X Y Z頻度 57 63 15 1 48 51 80 23 8

4、18 1 16 1 3需求分析3.1程序的基本功能本程序可以對任何大小的字符型文件進行Huffman編碼，生成一個編碼文件。并可以在程序運行結束后的任意時間對它解碼還原生成字符文件。即：先對一條電文進行輸入，并實現Huffman編碼，然后對Huffman編碼生成的代碼串進行譯碼，最后輸出電文數字3.2輸入/輸出形式當進行編碼時輸入為原字符文件文件名，當程序運行編碼完成之后輸入編碼文件名（默認名為code.dll）。當進行譯碼時輸入為編碼文件名（默認名為code.dll），從文件中讀取Huffman編碼樹后輸入字符文件的文件名。3.3測試數據要求本程序中測試數據主要為字符型文件。4概要設計1.系

5、統結構圖（功能模塊圖）哈弗曼樹編碼譯碼器編碼譯碼退出2功能模塊說明（1）.編碼：提示要編碼的文件文件名讀取文件以字母出現次數為權值建立哈弗曼樹對文本進行哈弗曼編碼并輸出編碼提示將編碼保存的文件名保存編碼文件；（2）.譯碼：提示輸入要譯碼的文件名利用建立好的哈弗曼樹進行譯碼將譯碼輸出提示保存譯碼文件的文件名保存譯碼文件；（3）.退出：退出系統，程序運行結束。5詳細設計創建哈弗曼樹開始初始化哈夫曼鏈表且有2n-1個節點i=1Iweight=countip=p-nextfor(i=n;iParent=HT2-Parent=pp-LChild=HT1p-RChild=HT2p-weight=HT1-w

6、eight+HT2-weight結束編碼開始將字符存入哈夫曼編碼結構體數組的字符單元中if(q=q-Parent-LChild)HCi.code-HCi.start=0HCi.code-HCi.start=1p=p-nextI=n 時結束譯碼開始Root指向根節點P!=rootcodei=0p=p-LChildp=p-Rchildp-LChild=NULL&p-RChild=NULLsk+=strjp=root結束6調試分析1.從葉子節點開始向上遍歷二叉樹,獲得哈夫曼編碼; 2.根據哈夫曼編碼遍歷哈夫曼樹直到葉子節點,獲得譯碼 3.算法的時間復雜度分析：程序部分用雙循環嵌套結構，時間復雜度為O

7、（n2）. 4算法的空間復雜度分析：算法的空間復雜度為O（n）5. 程序需要反復調試，并且調試過程比較慢，需要有一個比較正確的調試方法，更需要我們有耐心7用戶使用說明1.輸入字符的個數n 2輸入n個字符和n個權值3 選擇（15）操作可對huffman樹進行編碼和譯碼以及huffman樹表的打印4 退出系統8測試結果9附錄#include stdio.h#include stdlib.h#include string.h#define MAX 100struct HafNode int weight; int parent; char ch; int lchild; int rchild;*my

8、HaffTree;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.weights1) s2=s1; x2=x1; s1=myHaffTreej.weight; x1=j; else if(myHaffTreej.parent

9、=0&myHaffTreej.weights2) 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,c,f,i,j,k; char *cd; cd=(char *)malloc(n*sizeof(char); myHaffCode=(struct Coding *)malloc(n+1)

10、*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; for(j=start,k=0;jn;j+) myHaffCodei.bitk=cdj; k+; myHaffCodei.ch=myHaffTreei.ch; myHaffCodei.weight=myHaffTreei.weight; free(cd

11、);void print() printf(*n); printf(* *n); printf(* *n); printf(* welcome to huffman coding and codeprinting *n); printf(* *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 num

12、ber of words:n); scanf(%d,&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; for(i=n+1;i=m;i+

13、) 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); return n;void Caozuo_C(int m)/* 對字符進行編碼 */ int n,i,j; char stri

14、ng50,*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(int 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+

15、) 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); void Caozuo_T(int n) int i; printf(word equal leftchild rightchild prentsn); for(i=1;i=2*n-1;i+) printf(%c %d %d %d %dn,myHaffTreei.ch,myHaffTreei.weight,myHaffTreei.lchild,myHaffTreei.rchild,myHaffTreei.parent);main() int n; char char1; print(); n=Init(); while(1) pri