實習報告(三)
題目:哈弗曼編解碼器
班級:計算機***班姓名:史丹丹學號:09052204 完成日期:2011.1.3
1、需求分析
1、 i:初始化。從終端讀入字符集大小n,已經n個字元和n個權值,建立哈弗曼樹,並將它存於檔案hlfmtree中。
2、 e:編碼。利用已經建好的哈弗曼樹對檔案tobetran中的正文進行編碼然後將結果存入檔案codefile中。
3、 d:解碼。利用已經建好的哈弗曼樹將檔案codefile中的**進行解碼,結果儲存在檔案textfile中。
4、 p:印**檔案。將檔案codefile以緊湊格式顯示在終端上,每行50個**。同時將此字元形式的編碼檔案寫入codeprin中。
5、 t:印哈弗曼樹。將已在記憶體的哈弗曼樹以直觀的方式顯示在終端上,同時將次字元形式的哈弗曼樹寫入檔案treeprint中。
二、概要設計
1、資料型別定義為
哈弗曼樹:
typedef structhtnode,*huffmantree;
哈弗曼編碼:
typedef char **huffmancode;
2、基本操作:
void select(huffmantree ht,int n,int & s1,int &s2)
void initial(huffmantree &ht,huffmancode &hc,int w,int &n,char ch,int &k)
void encoding(int n,int select)
void decoding(huffmantree ht,int n)
void output (huffmantree th,int n)
void prin()
void print()
void printtree( huffmantree node,huffmantree node1, int level )
本程式包含以下模組:
(1)主程式模組:
void main()
(2)各功能模組——對哈弗曼樹的各項操作
各模組的呼叫關係:
主程式 ↓
各功能模組
三、詳細設計
#include
#include
#include
#include
#include
using namespace std;
#define ok 1;
typedef struct
htnode,*huffmantree動態分配陣列儲存赫夫曼數
typedef char * *huffmancode動態分配陣列儲存赫夫曼編碼表
void select(huffmantree ht,int t,int &s1,int &s2)
// 從赫夫曼數中選出最小的兩個節點
for( i=1;i <= t ;i++ ) }
void prin終端輸出選擇選單
cout< <<" ∣ i---建立哈夫曼樹 ∣\n"
<<" ∣ ∣\n"
<<" ∣ e---檔案編碼 ∣\n"
<<" ∣ ∣\n"
<<" ∣ d---檔案解碼 ∣\n"
<<" ∣ ∣\n"
<<" ∣ p---列印**檔案 ∣\n"
<<" ∣ ∣\n"
<<" ∣ t---列印哈夫曼樹 ∣\n"
<<" ∣ ∣\n"
<<" ∣ q---退出 ∣\n"
<<"\nn\n";
} int initialization(int n,huffmantree &ht,huffmancode &hc,int w[50],char shuju[50])
// 構造赫夫曼數ht,並求出n個字元的赫夫曼編碼hc
int m,i;
m=2*n-1節點數
ht=(huffmantree)malloc((m+1)*sizeof(htnode0號單元未用
huffmantree p;
if(!(hfmtree=fopen("hfmtree.txt","w")))
for(p=ht+1,i=1;i<=n;++i,++p)
for(;i<=m;++i,++p)
for(i=n+1;i<=m;++i) //建赫夫曼樹
//---從葉子到根逆向求每個字元的赫夫曼編碼
hc=(huffmancode)malloc((n+1)*sizeof(char *));
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i逐個字元求赫夫曼編碼
hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(hc[i],&cd[start串複製
fputc(ht[i].infor,hfmtree);
fputc('\t',hfmtree);
fputs(hc[i],hfmtree);
fputc('\n',hfmtree);
}free(cd釋放工作區間
fclose(hfmtree);
return ok;
}int encoding(char zifu[50],huffmancode &hc) //對檔案tobetran進行編碼
if(!(codefile=fopen("codefile.txt","w")))
char ch;
ch=fgetc(tobetran);
while(ch!=eof)
fputs(hc[i],codefile);
ch=fgetc(tobetran);
}fclose(tobetran);
fclose(codefile);
return ok;
}int decoding(int n,huffmantree &ht對檔案codefile.txt進行解碼
if(!(codefile=fopen("codefile.txt","r")))
哈弗曼樹實驗報告
實驗四哈夫曼樹及其的應用 一 實驗目的 1 在二叉樹基本操作的基礎上,掌握對二叉樹的一些其它操作的具體實現方法。2.掌握構造哈夫曼樹以及哈夫曼編碼的方法。3 熟練掌握哈夫曼樹 最優二叉樹 特徵及其應用 二 實驗內容 哈夫曼樹和哈夫曼編碼 從終端輸入若干個字元,統計 或指定 字元出現的頻率,將字元出現...
實驗四哈夫曼樹及其的應用
一 實驗目的 1 在二叉樹基本操作的基礎上,掌握對二叉樹的一些其它操作的具體現方法.2.掌握構造哈夫曼樹以及哈夫曼編碼的方法.3 熟練掌握哈夫曼樹 最優二叉樹 特徵及其應用.二 實驗內容 哈夫曼樹和哈夫曼編碼 從終端輸入若干個字元,統計 或指定 字元出現的頻率,將字元出現的頻率作為結點的權值,建立哈...
用動態規劃演算法解決哈弗曼編碼問題
1 實驗目的 用動態規劃演算法解決哈弗曼編碼問題。2 實驗要求 輸入字元的個數和字元的編號及相應頻率,輸出其相應編碼,並寫出其壓縮率。3 程式清單 include include include using namespace std int mecou 定義全域性變數計碼長 class huffm...