哈夫曼編碼譯碼系統(tǒng)

1、 數(shù) 據(jù) 結(jié) 構(gòu) 課 程 設(shè) 計(jì)6.5電文的編碼和譯碼姓 名: XXX院系: 計(jì)算機(jī)學(xué)院專 業(yè): 計(jì)算機(jī)科學(xué)與技術(shù)年 級(jí): 13級(jí)學(xué) 號(hào): E11314XXX指導(dǎo)教師:XXX2015年 10月 30 日目錄1.課程設(shè)計(jì)的目的32.需求分析33電文的編碼和譯碼的設(shè)計(jì)33.1概要設(shè)計(jì)33.1.1主界面設(shè)計(jì)33.1.2存儲(chǔ)結(jié)構(gòu)43.1.3系統(tǒng)功能設(shè)計(jì)43.2詳細(xì)設(shè)計(jì)43.2.1系統(tǒng)子程序及功能設(shè)計(jì)43.2.2數(shù)據(jù)類型定義63.2.3系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)73.3調(diào)試分析113.4用戶手冊(cè)124總結(jié)125、程序清單:(見附錄)127、程序運(yùn)行結(jié)果12附錄118 39 / 391.課程設(shè)計(jì)的目的(1)

2、熟練使用 C 語言編寫程序，解決實(shí)際問題;(2) 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力;(3) 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能;(4) 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力。2.需求分析(1) 為信息收發(fā)站寫一個(gè)哈夫曼編/譯碼系統(tǒng)。(2) 要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。(3) 要求可以將哈夫曼樹以樹狀或凹入法打印到屏幕。3電文的編碼和譯碼的設(shè)計(jì)3.1概要設(shè)計(jì)3.1.1主界面設(shè)計(jì)圖 1主界面，如圖1所示，包含初始化，編碼，譯碼，代碼文件，哈夫曼樹五個(gè)菜

3、單。其中，菜單1用來從終端讀入n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件中; 菜單2用來利用已建好的哈夫曼樹，對(duì)文件中或直接輸入的正文進(jìn)行編碼，然后將結(jié)果存入文件中，如果哈夫曼樹不在內(nèi)存可通過初始化或文件讀入到內(nèi)存；菜單3利用已建好的哈夫曼樹將文件中的代碼進(jìn)行譯碼，譯碼結(jié)果存入文件中，若哈夫曼樹不在內(nèi)存中，處理方式與菜單2相同；菜單4將編碼文件以緊湊格式顯示在終端上，每行50個(gè)代碼,同時(shí)將此字符形式的編碼寫入文件中；菜單5將已在內(nèi)存中的哈夫曼樹以凹入法顯示在終端上。3.1.2存儲(chǔ)結(jié)構(gòu)這里使用了4個(gè)結(jié)構(gòu)體。結(jié)構(gòu)體HTNode存放哈夫曼樹的結(jié)點(diǎn)，包含權(quán)值weight，以及父節(jié)點(diǎn)parent、

4、左孩子lchild、右孩子rchild所在位置。結(jié)構(gòu)體Huffmantree保存哈夫曼樹, 其中num是結(jié)點(diǎn)數(shù)，參與哈夫曼編碼的各個(gè)字符alphabet，hftree是HTNode類型存放構(gòu)建的哈夫曼樹的表，HCnum是每個(gè)字符編碼的長(zhǎng)度，HC是編碼字符數(shù)組。結(jié)構(gòu)體Text保存正文，其中num存放正文的長(zhǎng)度，content存放正文內(nèi)容。Code存放編碼結(jié)果，num是編碼長(zhǎng)度，bin是編碼內(nèi)容。3.1.3系統(tǒng)功能設(shè)計(jì)本系統(tǒng)的功能描述如下：1 可輸入字符和其對(duì)應(yīng)的權(quán)值，以構(gòu)建哈夫曼樹。2 可輸入或讀入正文，根據(jù)構(gòu)建的哈夫曼樹，對(duì)正文進(jìn)行編碼,若哈夫曼樹未存在，可從文件中讀入或者初始化輸入，若正文中

5、字符在哈夫曼樹中不存在，則會(huì)提示編碼出錯(cuò)。3 可讀入編碼文件，根據(jù)存在的哈夫曼樹，對(duì)文件進(jìn)行解碼，若哈夫曼樹不存在會(huì)進(jìn)行和2一樣的操作，若解碼時(shí)，編碼在哈夫曼樹中不存在，則提示解碼出錯(cuò)。4 可根據(jù)內(nèi)存中的哈夫曼樹用凹入表示法輸出樹形界面。3.2詳細(xì)設(shè)計(jì)3.2.1系統(tǒng)子程序及功能設(shè)計(jì)本系統(tǒng)設(shè)置32個(gè)函數(shù)，函數(shù)名及功能說明如下：void HufftreeInit(Huffmantree & H)/對(duì)結(jié)構(gòu)體Huffmantree初始化void HufftreeMalloc(Huffmantree & H,int num)/給結(jié)構(gòu)體Huffmantree分配空間void TextIni

6、t(Text & c)/結(jié)構(gòu)體Text初始化void TextMalloc(Text & c,int num)/給結(jié)構(gòu)體Text分配存儲(chǔ)空間void CodeInit(Code & co)/給結(jié)構(gòu)體code初始化void CodeMalloc(Code & co,int num)/給結(jié)構(gòu)體code分配存儲(chǔ)空間int inputselection(int n)/輸入菜單選擇，返回值為輸入的選項(xiàng)int TreeRead(Huffmantree &H)/讀取哈夫曼樹文件int TreeSave(Huffmantree H)/保存結(jié)構(gòu)體Huffmantreein

7、t TextSave(Text c)/保存結(jié)構(gòu)體Textint TextRead(Text &c)/讀取結(jié)構(gòu)體Textint CodeSave(Code & co)/保存結(jié)構(gòu)體Codeint CodeSave2(Code & co)/以緊湊形式保存結(jié)構(gòu)體Codeint CodeRead(Code & co)/讀取結(jié)構(gòu)體Codeint istrue()/判斷是否輸入了Yvoid exchange(int s)/交換s0和s1中的內(nèi)容void Select(HTNode HT,int i,int s)/找到parent為0且weight最小的兩個(gè)結(jié)點(diǎn),序號(hào)放在s0和

8、s1void Huffmancoding(Huffmantree &HT)/哈弗曼編碼int exist(Huffmantree HT,int index)/判斷HT.alphabetindex是否與其他結(jié)點(diǎn)重復(fù)void initialization(Huffmantree &HT)/初始化int encodingcourse()/編碼菜單void inputtext(Text &text)/輸入正文void encode(Huffmantree HT,Text text)/編碼保存至文件void encoding(Huffmantree &HT)/編碼菜單in

9、t decodingcourse()/解碼菜單char * substring(Code co,int beginning,int ending)/求子串，從beginning到endingvoid decode(Huffmantree HT)/解碼void decoding(Huffmantree &HT)/解碼菜單void print()/印代碼文件int maincourse()/主菜單void welcom()/歡迎界面void treeprinting(Huffmantree HT,int index,int level,char*filename,int fla)/凹入法印

10、哈夫曼樹void hfmtreeprinting(Huffmantree HT)/用凹入法印哈弗曼樹,包含文件輸入各主要函數(shù)之間的調(diào)用關(guān)系如下:(見下頁)主菜單Huffmancoding(Huffmantree &HT);TreeSave(Huffmantree H);initialization(Huffmantree &HT)inputtext(Text &text)encode(Huffmantree HT,Text text)TreeRead(Huffmantree &H)TextSave(Text c)TextRead(Text &c)Code

11、Save(Code & co)encoding(Huffmantree &HT)TreeRead(Huffmantree &H)decode(Huffmantree HT)CodeRead(Code & co)decoding(Huffmantree &HT)print()treeprinting()hfmtreeprinting(Huffmantree H)3.2.2數(shù)據(jù)類型定義struct HTNode/哈夫曼樹的結(jié)點(diǎn)Elemtype weight;int parent,lchild,rchild;struct Huffmantree/哈夫曼樹int

12、 num;char * alphabet;/字符數(shù)組HTNode * hftree;/結(jié)點(diǎn)數(shù)組int * HCnum;/每個(gè)字符對(duì)應(yīng)編碼的長(zhǎng)度BIN * * HC;/每個(gè)字符的編碼;struct Text/正文int num;/正文長(zhǎng)度char * content;/正文;struct Code/編碼，用字符型數(shù)字表示int num;/編碼長(zhǎng)度BIN * bin;/編碼;3.2.3系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)哈夫曼編碼:void exchange(int s)/交換s0和s1中的內(nèi)容int temp;temp=s0;s0=s1;s1=temp;void Select(HTNode HT,int i,

13、int s)/找到parent為0且weight最小的兩個(gè)結(jié)點(diǎn),序號(hào)放在s0和s1int j,flag=0;for(j=1;j<=i&&flag<2;j+)if(!HTj.parent)sflag+=j;if(HTs0.weight>HTs1.weight)exchange(s);for(;j<=i;j+)if(!HTj.parent)if(HTj.weight<HTs1.weight)/左子樹放較小值，右子樹放較大值s1=j;if(HTs0.weight>HTs1.weight)exchange(s);void Huffmancoding(

14、Huffmantree &HT)/哈弗曼編碼int m,i,start,f,n=HT.num;int s2;unsigned c;char * cd;m=2*n-1;for(i=n+1;i<=m;i+)Select(HT.hftree,i-1,s);HT.hftrees0.parent=i;HT.hftrees1.parent=i;HT.hftreei.lchild=s0;HT.hftreei.rchild=s1;HT.hftreei.parent=0;HT.hftreei.weight=HT.hftrees0.weight+HT.hftrees1.weight;cd=(char

15、 *)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;i+)start=n-1;for(c=i,f=HT.hftreei.parent;f!=0;c=f,f=HT.hftreef.parent)if(HT.hftreef.lchild=c) cd-start='0'else cd-start='1'HT.HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HT.HCi,&cdstart);HT.HCnumi=strlen(HT.HCi);free(cd

16、);給正文編碼:void encode(Huffmantree HT,Text text)/編碼保存至文件system("cls");Code c;cout<<"-n"cout<<" 正文編碼 n"cout<<"-n"if(HT.num=0)cout<<"哈夫曼樹不存在,請(qǐng)初始化或讀入后編碼!"<<endl;system("pause");return;if(text.num=0)cout<<"

17、正文不存在,請(qǐng)輸入或讀入正文后編碼!"<<endl;system("pause");return;char code26*N=0;for(int i=0;i<text.num;i+)/i<text.numfor(int j=1;j<=HT.num;j+)if(text.contenti=HT.alphabetj)break;if(j>HT.num)cout<<"編碼出錯(cuò)!"<<endl;system("pause");return;elsestrcat(code,H

18、T.HCj);CodeMalloc(c,strlen(code);strcpy(c.bin,code);cout<<"編碼結(jié)果為:"<<code<<endl;cout<<"編碼結(jié)果將保存到文件."<<endl;if(CodeSave(c)cout<<"保存成功!"<<endl;elsecout<<"保存失敗!"<<endl;system("pause");正文解碼：void decode(

19、Huffmantree HT)/解碼system("cls");cout<<"-n"cout<<" 讀取文件譯碼 n"cout<<"-n"if(HT.num=0)cout<<"哈夫曼樹不存在,請(qǐng)初始化或讀入后編碼!"<<endl;return;Code co;int flag,i,j,k;char * s;char temptextN+1;int textindex=0;cout<<"將從文件中讀取編碼."

20、;<<endl;CodeInit(co);if(CodeRead(co)co.binco.num=0;cout<<"讀取內(nèi)容為:"<<co.bin<<endl;cout<<"讀取成功!"<<endl;elsecout<<"讀取失敗!返回!"<<endl;return ;for(i=0;i<co.num;i=j+1)for(j=i;j<co.num;j+)flag=0;s=substring(co,i,j);for(k=1;k&l

21、t;=HT.num;k+)if(strcmp(s,HT.HCk)=0)flag=1;temptexttextindex+=HT.alphabetk;break;if(flag)break;if(j=co.num&&k>HT.num)cout<<"解碼出錯(cuò)!"<<endl;system("pause");return;temptexttextindex=0;cout<<"譯碼結(jié)果為:"<<temptext<<endl;cout<<"是

22、否保存譯碼結(jié)果到文件?"if(istrue()Text text;TextInit(text);text.num=strlen(temptext);TextMalloc(text,text.num);strcpy(text.content,temptext);if(TextSave(text)cout<<"保存成功!"<<endl;elsecout<<"保存失敗!"<<endl;elsecout<<"返回上級(jí)菜單!"<<endl;凹入法印哈夫曼樹：voi

23、d treeprinting(Huffmantree HT,int index,int level,char * filename,int flag)/凹入打印哈夫曼樹if(index<1|index>2*HT.num-1)return;ofstream outfile(filename,ios:app);for(int i=0;i<level;i+)if(flag)outfile<<" "cout<<" "if(index<=HT.num)if(HT.alphabetindex=' ')i

24、f(flag)outfile<<"blank"<<endl;/空格用blank表示cout<<"blank"<<endl;elsecout<<HT.alphabetindex<<endl;outfile<<HT.alphabetindex<<endl;elseif(flag)outfile<<(int)HT.hftreeindex.weight<<endl;cout<<(int)HT.hftreeindex.weight&l

25、t;<endl;if(HT.hftreeindex.rchild)treeprinting(HT,HT.hftreeindex.rchild,level+1,filename,1);/左右子樹深度相同if(HT.hftreeindex.lchild)treeprinting(HT,HT.hftreeindex.lchild,level+1,filename,1);if(flag)outfile.close();3.3調(diào)試分析測(cè)試數(shù)據(jù)及測(cè)試結(jié)果在7中有詳細(xì)給出，這里省略。算法分析：編碼函數(shù)中，每次都要將待編碼字符與正文字符比較，相當(dāng)于順序表查找，哈夫曼樹中有n個(gè)字符，時(shí)間復(fù)雜度為O(n2)

26、。解碼函數(shù)中，每次從編碼中取出一定長(zhǎng)的子串與哈夫曼編碼比較，逐漸增加子串長(zhǎng)度，直到找到相同子串，得到解碼后的字符。用凹入法打印哈夫曼樹，先輸出最頂端的結(jié)點(diǎn)，然后根據(jù)包含關(guān)系，將子樹的結(jié)點(diǎn)縮進(jìn)一定長(zhǎng)度，用遞歸調(diào)用實(shí)現(xiàn)該打印。調(diào)試中遇到的問題及解決方法：1. 空格的輸入。在C+中用cin輸入，空格作為截止符，無法正常輸入，于是改成了C語言的scanf函數(shù)，接收空格。2. 空格的讀入和保存。在C+中用outfile<<和infile>>的方式讀入或保存空格，功能類似于cin中的功能，即作為輸入輸出的截止符。無法正常保存和讀出。于是用二進(jìn)制讀入讀出字符，但這樣存在一個(gè)弊端：直接

27、打開保存的文件將無法直接查看其中的內(nèi)容，解決方法還有待改善。3. 當(dāng)同一個(gè)函數(shù)中同時(shí)存在puts與cout時(shí)，輸出會(huì)出錯(cuò)。于是一個(gè)函數(shù)中要么用C語言的輸入輸出和puts，要么只有cout函數(shù)。3.4用戶手冊(cè)1 本程序執(zhí)行文件為huffmancoding.exe。2 用戶進(jìn)入系統(tǒng)后可輸入相應(yīng)數(shù)字選擇菜單，本系統(tǒng)可實(shí)現(xiàn)哈夫曼樹的建立，以及利用哈夫曼編碼對(duì)字符進(jìn)行編碼、解碼的功能、哈夫曼樹的凹入法打印功能。3 運(yùn)行期間產(chǎn)生的哈夫曼樹建立、字符編碼、字符解碼、哈夫曼樹打印等中間結(jié)果均可保存在文件。4總結(jié)1. 關(guān)于哈夫曼編碼的思考：哈夫曼編碼冗余度很低，充分地縮小了存儲(chǔ)正文所需的存儲(chǔ)空間，方便傳輸。但從

28、本次實(shí)驗(yàn)來看，哈夫曼編碼在解碼時(shí)由于不知道到底多長(zhǎng)截取為一段來解碼成字符，需要一點(diǎn)一點(diǎn)地試。這次實(shí)驗(yàn)是從最小1比特截為一段，后面逐漸增加截取長(zhǎng)度，直到這個(gè)字符解碼成功。還可以優(yōu)化一點(diǎn)，先根據(jù)哈夫曼編碼的最短長(zhǎng)度，以最短長(zhǎng)度截取一段，然后逐漸增加，以降低運(yùn)行耗時(shí)。2. 關(guān)于調(diào)試過程中的感受：在以往的實(shí)驗(yàn)中，大都是用C語言完成實(shí)驗(yàn)，而這次為了使保存的文件不是亂碼，用了C+. 但因?yàn)榭崭竦膯栴}，直接保存有一定的問題，最終還是用了二進(jìn)制的方式保存，使程序能夠正常運(yùn)行。主要可能是因?yàn)閷?duì)文件的使用方式不太熟悉，以后還有待提高。除此之外，這次因?yàn)轳R虎給自己添了不少麻煩，浪費(fèi)了很多時(shí)間，是一次小小的教訓(xùn)。5、

29、程序清單:(見附錄)7、程序運(yùn)行結(jié)果主界面初始化：編碼：1. 從文件讀入哈夫曼樹2. 直接輸入正文3. 從文件讀入正文4. 正文編碼譯碼：2.正文譯碼印代碼文件：凹入法印哈夫曼樹附錄1#include <stdlib.h>#include <string.h>#include <iostream.h>#include <stdio.h>#include <fstream.h>#define Elemtype double#define BIN char#define N 500#define N2 100#define Tree 1/

30、1表示樹#define BeTran 2/2表示正文#define CoFile 3/3表示編碼后結(jié)果struct HTNode/哈夫曼樹的結(jié)點(diǎn)Elemtype weight;int parent,lchild,rchild;struct Huffmantree/哈夫曼樹int num;char * alphabet;HTNode * hftree;int * HCnum;BIN * * HC;struct Text/正文int num;char * content;struct Code/編碼，用字符型數(shù)字表示int num;BIN * bin;void HufftreeInit(Huffm

31、antree & H)/對(duì)結(jié)構(gòu)體Huffmantree初始化H.num=0;H.alphabet=NULL;H.hftree=NULL;H.hftree=NULL;void HufftreeMalloc(Huffmantree & H,int num)/給結(jié)構(gòu)體Huffmantree分配空間H.num=num;H.alphabet=(char *)malloc(H.num+1)*sizeof(char);H.hftree=(HTNode *)malloc(2*H.num*sizeof(HTNode);H.HC=(char * *)malloc(H.num+1)*sizeof(c

32、har *);H.HCnum=(int *)malloc(H.num+1)*sizeof(int);for(int i=1;i<=2*num-1;i+)H.hftreei.lchild=0;H.hftreei.parent=0;H.hftreei.rchild=0;H.hftreei.weight=0;void TextInit(Text & c)/結(jié)構(gòu)體Text初始化c.num=0;c.content=NULL;void TextMalloc(Text & c,int num)/給結(jié)構(gòu)體Text分配存儲(chǔ)空間c.num=num;c.content=(char *)mall

33、oc(sizeof(char)*(c.num+1);void CodeInit(Code & co)/給結(jié)構(gòu)體code分配存儲(chǔ)空間co.num=0;co.bin=NULL;void CodeMalloc(Code & co,int num)/給結(jié)構(gòu)體code分配存儲(chǔ)空間co.num=num;co.bin=(BIN *)malloc(co.num+1)*sizeof(BIN);int inputselection(int n)/輸入菜單選擇，返回值為輸入的選項(xiàng)int flag=0;char s100;doif(flag)cout<<"t 輸入非法,請(qǐng)重新輸入

34、:"elsecout<<"t 輸入數(shù)字0-"<<n<<"選擇:"flag=1;cin>>s;while(strlen(s)>1|s0-'0'<0|s0-'0'>n);return s0-'0'int TreeRead(Huffmantree &H)/讀取哈夫曼樹文件char filenameN2;cout<<"文件名稱為:"cin>>filename;ifstream infile

35、;int flag; infile.open(filename,ios:binary); if(!infile) infile.open("hfmTree.txt",ios:binary);if(!infile)cout<<filename<<"無法打開!"<<endl;return 0;elsecout<<"原"<<filename<<"無法被打開,默認(rèn)打開htmTree"<<endl; infile.read(char*)&am

36、p;flag,sizeof(int); /判斷flag是否為1，保存的是否為哈夫曼樹if(flag!=1)cout<<"讀取的數(shù)據(jù)格式不對(duì)!"<<endl; return 0;/讀取失敗infile.read(char*)&H.num,sizeof(int);HufftreeMalloc(H,H.num);/分配空間 for(int i=1;i<=H.num;i+)/讀取字母infile.read(char*)&H.alphabeti,sizeof(char);infile.read(char*)&H.HCnumi,si

37、zeof(int);H.HCi=(BIN *)malloc(sizeof(BIN)*(H.HCnumi+1);for(int j=0;j<H.HCnumi;j+)infile.read(char*)&H.HCij,sizeof(char);H.HCij=0; for(i=0;i<(2*H.num-1);i+)/讀取結(jié)構(gòu)體HTNodeinfile.read(char*)&H.hftreei.lchild,sizeof(int);infile.read(char*)&H.hftreei.parent,sizeof(int);infile.read(char*)&

38、amp;H.hftreei.rchild,sizeof(int);infile.read(char*)&H.hftreei.weight,sizeof(Elemtype); infile.close();return 1;int TreeSave(Huffmantree H)/保存結(jié)構(gòu)體Huffmantreechar filenameN2;int flag=1;cout<<"文件名稱為:"cin>>filename;ofstream outfile(filename,ios:binary); if(!outfile) cout<<

39、filename<<"無法打開!"<<endl;return 0; outfile.write(char*)&flag,sizeof(int); /表示文件存儲(chǔ)的是結(jié)構(gòu)體Huffmantreeoutfile.write(char*)&H.num,sizeof(int); for(int i=1;i<=H.num;i+)/保存字母outfile.write(char*)&H.alphabeti,sizeof(char);outfile.write(char*)&H.HCnumi,sizeof(int);for(un

40、signed j=0;j<strlen(H.HCi);j+)outfile.write(char*)&H.HCij,sizeof(char);for(i=1;i<=2*H.num-1;i+)/保存結(jié)構(gòu)體HTNodeoutfile.write(char*)&H.hftreei.lchild,sizeof(int);outfile.write(char*)&H.hftreei.parent,sizeof(int);outfile.write(char*)&H.hftreei.rchild,sizeof(int);outfile.write(char*)&

41、amp;H.hftreei.weight,sizeof(Elemtype); outfile.close(); return 1;int TextSave(Text c)/保存結(jié)構(gòu)體Textchar filenameN2;int flag=2;cout<<"文件名稱為:"cin>>filename;ofstream outfile;outfile.open(filename,ios:binary);if(!outfile)cout<<filename<<"無法打開!"<<endl;return

42、0;outfile.write(char*)&flag,sizeof(int);/保存的是正文outfile.write(char*)&c.num,sizeof(int);for(int i=0;i<c.num;i+)outfile.write(char*)&c.contenti,sizeof(char);outfile.close();return 1;int TextRead(Text &c)/讀取結(jié)構(gòu)體Textchar filenameN2;cout<<"文件名稱為:"cin>>filename;ifstr

43、eam infile;int flag;infile.open(filename,ios:binary);if(!infile)cout<<filename<<"無法打開!"<<endl;return 0;infile.read(char*)&flag,sizeof(int);if(flag!=2)cout<<"讀取的數(shù)據(jù)格式不對(duì)!" return 0;infile.read(char*)&c.num,sizeof(int);TextMalloc(c,c.num);for(int i=0;i

44、<c.num;i+)infile.read(char*)&c.contenti,sizeof(char);cout<<c.contenti;infile.close();return 1;int CodeSave(Code & co)/保存結(jié)構(gòu)體Codechar filenameN2;cout<<"文件名稱為:"cin>>filename;ofstream outfile;outfile.open(filename,ios:out);if(!outfile)cout<<filename<<&q

45、uot;無法打開!"<<endl;return 0;outfile<<3<<endl;outfile<<co.num<<endl;for(int i=0;i<co.num;i+)outfile<<co.bini<<" "outfile<<endl;outfile.close();return 1;int CodeSave2(Code & co)/以緊湊形式保存結(jié)構(gòu)體Codechar filenameN2;cout<<"文件名稱為:&q

46、uot;cin>>filename;ofstream outfile;outfile.open(filename,ios:out);if(!outfile)cout<<filename<<"無法打開!"<<endl;return 0;for(int i=0;i<co.num;i+)outfile<<co.bini;if(i+1)%50=0)outfile<<endl;outfile<<endl;outfile.close();return 1;int CodeRead(Code &am

47、p; co)/讀取結(jié)構(gòu)體Codechar filenameN2;cout<<"文件名稱為:"cin>>filename;ifstream infile;int flag=2233;infile.open(filename,ios:in);if(!infile)cout<<filename<<"無法打開!"<<endl;return 0;infile>>flag;if(flag!=3)cout<<"文件讀取格式不對(duì)!"<<endl;retur

48、n 0;infile>>co.num;CodeMalloc(co,co.num);for(int i=0;i<co.num;i+)infile>>co.bini;infile.close();return 1;int istrue()/判斷是否輸入了Ychar s100;int flag=0;cout<<"(輸入Y/y表示是,輸入N/n表示否):"doif(flag)cout<<endl<<"輸入非法,請(qǐng)重新輸入:"cin>>s;flag=1;while(strlen(s)&g

49、t;1|s0!='y'&&s0!='Y'&&s0!='n'&&s0!='N');if(s0='y'|s0='Y')return 1;elsereturn 0;void exchange(int s)/交換s0和s1中的內(nèi)容int temp;temp=s0;s0=s1;s1=temp;void Select(HTNode HT,int i,int s)/找到parent為0且weight最小的兩個(gè)結(jié)點(diǎn),序號(hào)放在s0和s1int j,flag=0;for(

50、j=1;j<=i&&flag<2;j+)if(!HTj.parent)sflag+=j;if(HTs0.weight>HTs1.weight)exchange(s);for(;j<=i;j+)if(!HTj.parent)if(HTj.weight<HTs1.weight)/左子樹放較小值，右子樹放較大值s1=j;if(HTs0.weight>HTs1.weight)exchange(s);void Huffmancoding(Huffmantree &HT)/哈弗曼編碼int m,i,start,f,n=HT.num;int s2;

51、int c;char * cd;m=2*n-1;for(i=n+1;i<=m;i+)Select(HT.hftree,i-1,s);HT.hftrees0.parent=i;HT.hftrees1.parent=i;HT.hftreei.lchild=s0;HT.hftreei.rchild=s1;HT.hftreei.parent=0;HT.hftreei.weight=HT.hftrees0.weight+HT.hftrees1.weight;cd=(char *)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;i+)st

52、art=n-1;for(c=i,f=HT.hftreei.parent;f!=0;c=f,f=HT.hftreef.parent)if(HT.hftreef.lchild=c) cd-start='0'else cd-start='1'HT.HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HT.HCi,&cdstart);HT.HCnumi=strlen(HT.HCi);free(cd);int exist(Huffmantree HT,int index)/判斷HT.alphabetindex是否與其他結(jié)點(diǎn)

53、重復(fù)for(int i=1;i<index;i+)if(HT.alphabeti=HT.alphabetindex)return 1;return 0;void initialization(Huffmantree &HT)/初始化system("cls");int num;int i;puts("-");puts(" 初 始 化 ");puts("-");printf("參與Huffman編碼的數(shù)目:");scanf("%d",&num);/輸入結(jié)點(diǎn)數(shù)

54、目if(num=0)puts("結(jié)點(diǎn)數(shù)目為0");getchar();system("pause");return;HufftreeInit(HT);HufftreeMalloc(HT,num);for(i=1;i<=num;i+)/輸入結(jié)點(diǎn)信息printf("請(qǐng)輸入第%d個(gè)字符及權(quán)值:",i);getchar();scanf("%c%lf",&HT.alphabeti,&HT.hftreei.weight);if(exist(HT,i)cout<<"該條記錄已存在,本次

55、輸入無效!"<<endl;i-;Huffmancoding(HT);/哈夫曼編碼printf("生成完成,是否保存到文件?");if(istrue()if(TreeSave(HT)puts("保存成功!");elseputs("保存失敗!");elseputs("返回上級(jí)菜單!");getchar();system("pause");int encodingcourse()/編碼菜單cout<<"tt -n"cout<<"tt 正文編碼 n"cout<<"tt -n"cout<<"ttt 1. 從文件讀入哈夫曼樹"<<endl;cout<<"