數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈弗曼編碼譯碼器

1、安徽省巢湖學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程設(shè)計(jì)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 哈弗曼編碼、譯碼器 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班級 10計(jì)本2班 學(xué)號 10012080 姓名 聯(lián)系方式 指導(dǎo)教師 20 11 年 12 月 29 日一實(shí)驗(yàn)?zāi)康木毩?xí)樹和哈夫曼樹的有關(guān)操作，和各個(gè)算法程序，理解哈夫曼樹的編碼和譯碼二實(shí)驗(yàn)環(huán)境 microsoft visual c+三、問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編

2、碼/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼編碼的編碼/譯碼器。四、需求分析（1）初始化;從終端輸入字符集的大小n，以及n個(gè)字符和n個(gè)權(quán)值建立哈夫曼樹。 （2）輸出哈夫曼樹，及各字符對應(yīng)的編碼。 （3）編碼：利用建好的哈夫曼樹，對輸入的待發(fā)送電文進(jìn)行編碼。同時(shí)輸入原文及編碼串。 （4）譯碼：利用建好的哈夫曼樹，對輸入的已接收電文進(jìn)行譯碼。同時(shí)輸入編碼串及原文。五、概要設(shè)計(jì)#include <iostream.h>#include <iomanip.h>#include <string.h>#include <malloc.h>#include

3、<stdio.h>/typedef int telemtype;const int uint_max=1000;char str50;typedef struct int weight,k; int parent,lchild,rchild;htnode,* huffmantree;typedef char *huffmancode;/-全局變量-huffmantree ht;huffmancode hc;int w50,i,j,n;char z50;int flag=0; int numb=0/ -求哈夫曼編碼- struct cou char data; int count;c

4、ou50;int min(huffmantree t,int i) / 函數(shù)void select()調(diào)用 int j,flag; int k=uint_max; / 取k為不小于可能的值,即k為最大的權(quán)值1000 for(j=1;j<=i;j+) if(tj.weight<k&&tj.parent=0) k=tj.weight,flag=j; tflag.parent=1; return flag;/-slect函數(shù)-void select(huffmantree t,int i,int &s1,int &s2) / s1為最小的兩個(gè)值中序號小的那

5、個(gè) int j; s1=min(t,i); s2=min(t,i); if(s1>s2) j=s1; s1=s2; s2=j; / -算法6.12-void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n) / w存放n個(gè)字符的權(quán)值(均>0),構(gòu)造哈夫曼樹ht,并求出n個(gè)字符的哈夫曼編碼hc int m,i,s1,s2,start; /unsigned c,f; int c,f; huffmantree p; char *cd; if(n<=1) return;/檢測結(jié)點(diǎn)數(shù)是否可以構(gòu)成樹 m

6、=2*n-1; ht=(huffmantree)malloc(m+1)*sizeof(htnode); / 0號單元未用 for(p=ht+1,i=1;i<=n;+i,+p,+w) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; for(;i<=m;+i,+p) p->parent=0; for(i=n+1;i<=m;+i) / 建哈夫曼樹 / 在ht1i-1中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn),其序號分別為s1和s2 select(ht,i-1,s1,s2); hts1.p

7、arent=hts2.parent=i; hti.lchild=s1; hti.rchild=s2; hti.weight=hts1.weight+hts2.weight; / 從葉子到根逆向求每個(gè)字符的哈夫曼編碼 hc=(huffmancode)malloc(n+1)*sizeof(char*); / 分配n個(gè)字符編碼的頭指針向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求編碼的工作空間 cdn-1='0' / 編碼結(jié)束符 for(i=1;i<=n;i+) / 逐個(gè)字符求哈夫曼編碼 start=n-1; / 編碼結(jié)束符位置 f

8、or(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個(gè)字符編碼分配空間 strcpy(hci,&cdstart); / 從cd復(fù)制編碼(串)到hc free(cd); / 釋放工作空間/- 獲取報(bào)文并寫入文件-int inputcode() /cout<<"請輸入你想要編碼的字符"

9、;<<endl; file *tobetran; if(tobetran=fopen("tobetran.txt","w")=null) cout<<"不能打開文件"<<endl; return 0; cout<<"請輸入你想要編碼的字符"<<endl; gets(str); fputs(str,tobetran); cout<<"獲取報(bào)文成功"<<endl; fclose(tobetran); return s

10、trlen(str);/-初始化哈夫曼鏈表-void initialization() int a,k,flag,len; a=0; len=inputcode(); for(i=0;i<len;i+) k=0;flag=1; coui-a.data=stri; coui-a.count=1; while(i>k) if(stri=strk) a+;為實(shí)現(xiàn)上述程序功能，應(yīng)以指針存儲(chǔ)結(jié)點(diǎn)。為此，需要定義一個(gè)抽象數(shù)據(jù)類型。1. 抽象數(shù)據(jù)類型定義為：adt huffmantree數(shù)據(jù)對象：d=ai| aicharset,i=1,2,n, n0數(shù)據(jù)關(guān)系：r=< ai-1, ai &g

11、t; ai-1, aid, ai-1<ai ,i=2，3，n基本操作p：huffmantree(); 構(gòu)造函數(shù) huffmantree(); 析構(gòu)函數(shù)initialization(int weightnum);操作結(jié)果：構(gòu)造哈夫曼樹。encoder()初始條件：哈夫曼樹已存在或者哈夫曼樹已存到文件中。操作結(jié)果：對字符串進(jìn)行編碼decoder();初始條件：哈夫曼樹已存在且已編碼。操作結(jié)果：對二進(jìn)制串進(jìn)行譯碼print()初始條件：編碼文件已存在。操作結(jié)果：把已保存好的編碼文件顯示在屏幕2.本程序包含三個(gè)模塊：1)主程序模塊：void main() 初始化；do 接受命令； 處理命令；wh

12、ile(“命令”=”退出”)2)、建樹模塊實(shí)現(xiàn)定義的抽象數(shù)據(jù)類型3)、編/譯碼模塊實(shí)現(xiàn)字符串的編/譯碼六、源程序#include<iostream>#include<fstream>#include<iomanip>#include<stdlib.h>using namespace std;# define maxn 100/初始設(shè)定的最大結(jié)點(diǎn)數(shù)# define maxc 1000/最大編碼長度 # define impossibleweight 10000/結(jié)點(diǎn)不可能達(dá)到的權(quán)值 # define n 26/字符集的個(gè)數(shù)/-哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu)類型

13、定義-typedef struct /定義哈夫曼樹各結(jié)點(diǎn) int weight;/權(quán)值 int parent;/雙親結(jié)點(diǎn)下標(biāo) int lchild;/左孩子結(jié)點(diǎn)下標(biāo) int rchild;/右孩子結(jié)點(diǎn)下標(biāo)htnode,*huffmantree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedef char*huffmancode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表 /-全局變量- huffmantree ht;huffmancode hc;int *w;/權(quán)值數(shù)組 /const int n=26;/字符集的個(gè)數(shù) char *info;/字符值數(shù)組 int flag=0;/初始化標(biāo)記 /* /初始化函數(shù)/函數(shù)功

14、能： 從終端讀入字符集大小n , 以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmtree中/函數(shù)參數(shù)： /向量ht的前n個(gè)分量表示葉子結(jié)點(diǎn)，最后一個(gè)分量表示根結(jié)點(diǎn)，各字符的編碼長度不等，所以按實(shí)際長度動(dòng)態(tài)分配空間void select(huffmantree t,int i,int &s1,int &s2) /s1為最小的兩個(gè)值中序號最小的那個(gè) int j; int k=impossibleweight;/k的初值為不可能達(dá)到的最大權(quán)值 for(j=1;j<=i;j+) if(tj.weight<k&&tj.parent=0) k=tj.

15、weight; s1=j; ts1.parent=1; k=impossibleweight; for(j=1;j<=i;j+) if(tj.weight<k&&tj.parent=0) k=tj.weight; s2=j; ts2.parent=1;void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int num)/w存放n個(gè)字符的權(quán)值（均>0），構(gòu)造哈夫曼樹ht，并求出n個(gè)字符的哈弗曼編碼hc int i,m,c,s1,s2,start,f; huffmantree p; c

16、har* cd; if(num<=1) return; m=2*num-1;/m為結(jié)點(diǎn)數(shù)，一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)，可以存儲(chǔ)在一個(gè)大小為2n-1的一維數(shù)組中 ht=(huffmantree)malloc(m+1)*sizeof(htnode);/0號單元未用 /-初始化哈弗曼樹- for(p=ht+1,i=1;i<=num;i+,p+,w+) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; for(i=num+1;i<=m;i+,p+) p->weight=0; p-

17、>parent=0; p->lchild=0; p->rchild=0; /-建哈夫曼樹- for(i=num+1;i<=m;i+) select(ht,i-1,s1,s2);/在ht1.i-1選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號分別為s1和s2 hts1.parent=i; hts2.parent=i; hti.lchild=s1; hti.rchild=s2;/左孩子權(quán)值小，右孩子權(quán)值大 hti.weight=hts1.weight+hts2.weight; /-從葉子到根逆向求每個(gè)字符的哈弗曼編碼- hc=(huffmancode)malloc

18、(num+1)*sizeof(char *);/指針數(shù)組:分配n個(gè)字符編碼的頭指針向量 cd=(char*)malloc(n*sizeof(char*);/分配求編碼的工作空間 cdn-1='0'/編碼結(jié)束符 for(i=1;i<=n;i+)/逐個(gè)字符求哈弗曼編碼 start=n-1;/編碼結(jié)束符位置 for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)/從葉子到跟逆向求哈弗曼編碼 if(htf.lchild=c) cd-start='0'/判斷是左孩子還是右孩子(左為0右為1) else cd-start='1&

19、#39; hci=(char*)malloc(num-start)*sizeof(char*);/按所需長度分配空間 int j,h; strcpy(hci,&cdstart); free(cd);/*初始化函數(shù)*void initialization() flag=1;/標(biāo)記為已初始化 int i; w=(int*)malloc(n*sizeof(int);/為26個(gè)字符權(quán)值分配空間 info=(char*)malloc(n*sizeof(char);/為26個(gè)字符分配空間 ifstream infile("abc.txt",ios:in); if(!infile

20、) cerr<<"打開失敗"<<endl; exit(1); for(i=0;i<n;i+) infile>>infoi; infile>>wi; infile.close(); cout<<"讀入字符成功！"<<endl; huffmancoding(ht,hc,w,n); /-打印編碼- cout<<"依次顯示各個(gè)字符的值,權(quán)值或頻度,編碼如下"<<endl; cout<<"字符"<<s

21、etw(6)<<"權(quán)值"<<setw(11)<<"編碼"<<endl; for(i=0;i<n;i+) cout<<setw(3)<<infoi; cout<<setw(6)<<wi<<setw(12)<<hci+1<<endl; /-將建好的哈夫曼樹寫入文件- cout<<"下面將哈夫曼樹寫入文件"<<endl; ofstream outfile("hfmtree

22、.txt",ios:out); if(!outfile) cerr<<"打開失敗"<<endl; exit(1); for(i=0;i<n;i+,w+) outfile<<infoi<<" " outfile<<wi<<" " outfile<<hci+1<<" " outfile.close(); cout<<"已經(jīng)將字符與對應(yīng)的權(quán)值，編碼寫入根目錄下文件hfmtree.txt&q

23、uot;<<endl;/*輸入待編碼字符函數(shù)* void input() char string100; ofstream outfile("tobetran.txt",ios:out); if(!outfile) cerr<<"打開失敗"<<endl; exit(1); cout<<"請輸入你想要編碼的字符串(字符個(gè)數(shù)應(yīng)小于100),以#結(jié)束"<<endl; cin>>string; for(int i=0;stringi!='0'i+) if(

24、stringi='0') break; outfile<<stringi; cout<<"獲取報(bào)文成功"<<endl; outfile.close(); cout<<"-"<<"已經(jīng)將報(bào)文存入根目錄下的tobetran.txt文件"<<endl;/*編碼函數(shù)* void encoding() int i,j; char*string; string=(char*)malloc(maxn*sizeof(char); cout<<"

25、;下面對根目錄下的tobetran.txt文件中的字符進(jìn)行編碼"<<endl; ifstream infile("tobetran.txt",ios:in); if(!infile) cerr<<"打開失敗"<<endl; exit(1); for(i=0;i<100;i+) infile>>stringi; for(i=0;i<100;i+)if(stringi!='#') cout<<stringi;else break; infile.close();

26、 ofstream outfile("codefile.txt",ios:out); if(!outfile) cerr<<"打開失敗"<<endl; exit(1); for(i=0;stringi!='#'i+) for(j=0;j<n;j+) if(stringi=infoj) outfile<<hcj+1; outfile<<'#' outfile.close(); free(string); cout<<"編碼完成-" cout

27、<<"編碼已寫入根目錄下的文件codefile.txt中"<<endl; /*譯碼函數(shù)* void decoding() int j=0,i; char *code; code=(char*)malloc(maxc*sizeof(char); char*string; string=(char*)malloc(maxn*sizeof(char); cout<<"下面對根目錄下的codefile.txt文件中的代碼進(jìn)行譯碼"<<endl; ifstream infile("codefile.txt&

28、quot;,ios:in); if(!infile) cerr<<"打開失敗"<<endl; exit(1); for( i=0;i<maxc;i+) infile>>codei; if(codei!='#') cout<<codei; else break; infile.close(); int m=2*n-1; for(i=0;codei-1!='#'i+) if(htm.lchild=0) stringj=infom-1; j+; m=2*n-1; i-; else if(code

29、i='1') m=htm.rchild; else if(codei='0') m=htm.lchild; stringj='#' ofstream outfile("textfile.txt",ios:out); if(!outfile) cerr<<"打開失敗"<<endl; exit(1); cout<<"的譯碼為-"<<endl; for( i=0;stringi!='#'i+) outfile<<str

30、ingi; cout<<stringi; outfile<<'#' outfile.close(); cout<<"-譯碼完成-"<<endl; cout<<"譯碼結(jié)果已寫入根目錄下的文件textfile.txt中"<<endl; free(code); free(string); /*打印編碼函數(shù)*void code_printing() int i; char *code; code=(char*)malloc(maxc*sizeof(char); cout<

31、;<"下面打印根目錄下文件codefile.txt中的編碼"<<endl; ifstream infile("codefile.txt",ios:in); if(!infile) cerr<<"打開失敗"<<endl; exit(1); for( i=0;i<maxc;i+) infile>>codei; if(codei!='#') cout<<codei; else break; infile.close(); cout<<endl

32、; ofstream outfile("codeprin.txt",ios:out); if(!outfile) cerr<<"打開失敗"<<endl; exit(1); for(i=0;codei!='#'i+) outfile<<codei; outfile.close(); free(code); cout<<"-打印結(jié)束-"<<endl; cout<<"該字符形式的編碼文件已寫入文件codeprin.txt中"<&

33、lt;endl;/*打印哈夫曼樹函數(shù)*int numb=0;void coprint(huffmantree start,huffmantree ht) /start=ht+26這是一個(gè)遞歸算法 if(start!=ht) ofstream outfile("treeprint.txt",ios:out); if(!outfile) cerr<<"打開失敗"<<endl; exit(1); numb+; /number=0 該變量為已被聲明為全局變量 coprint(ht+start->rchild,ht); /遞歸先序遍歷

34、 cout<<setw(5*numb)<<start->weight<<endl; /if(start->rchild=0) cout<<infostart-ht-1<<endl; outfile<<start->weight; coprint(ht+start->lchild,ht); numb-; outfile.close(); void tree_printing(huffmantree ht,int num) huffmantree p; p=ht+2*num-1; /p=ht+26 co

35、ut<<"下面打印赫夫曼樹"<<endl; coprint(p,ht); /p=ht+26 cout<<"打印工作結(jié)束"<<endl;/*主函數(shù)*int main() char choice; do cout<<"*哈弗曼編/譯碼器系統(tǒng)*"<<endl; cout<<"請選擇您所需功能："<<endl; cout<<"<i>:初始化哈弗曼樹"<<endl; cout<<"<w>:輸入待編碼字符串"<<endl; cout<<"<e>:利用已建好的哈