第一篇：數據結構課程設計-哈夫曼編碼譯碼器

課 程 設 計

課程名稱_ _數據結構課程設計_ 題目名稱_ 哈夫曼編碼譯碼器_ 學生學院 專業班級 學 號 學生姓名 指導教師

2011 年

12月

23日

摘要：

在當今信息爆炸時代，如何采用有效的數據壓縮技術來節省數據文件的存儲空間和計算機網絡的傳送時間已越來越引起人們的重視。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。

關鍵字：

哈夫曼樹

編碼 解碼 數據壓縮技術 1

目

錄

摘要：.........................................................................................................1 關鍵字：.....................................................................................................1 第一章 需求分析......................................................................................3 第二章 數據結構定義及其操作實現......................................................3 第三章 程序設計及其實現......................................................................3 3.1 從文件讀入原文...........................................................................3 3.2 統計原文中各字符的權值.........................................................4 3.3 編碼..............................................................................................5 3.4

解碼............................................................................................6 3.5 主函數............................................................................................7 第四章 運行結果及其分析......................................................................8 第五章 問題及其解決方法....................................................................10 第六章 心得體會（設計總結）............................................................10 附錄——源程序......................................................................................11

1、頭文件.........................................................................................11

2、赫夫曼編碼算法........................................................................12

3、主函數.........................................................................................18 參

考

文

獻......................................................................................21

第一章 需求分析

1．問題要求：打開一篇英文文章，統計出每個字符出現的次數，然后以他們為權值，對每個字符進行編碼，編碼完成后對其編碼進行譯碼。2．程序運行環境：windows、visual c++或java等 3．要求：

a)輸入一篇英文文章，根據字符出現的次數給出哈夫曼編碼方式。b)對英文文章進行編碼；

c)對編碼進行譯碼核對正確性

第二章 數據結構定義及其操作實現

2.1 哈弗曼樹節點

typedef struct { unsigned int weight;unsigned int parent;unsigned int lchild;unsigned int rchild;}HuffTreeNode,*HuffTree;

2.2 字符-權值-編碼映射

typedef struct { char c;unsigned int weight;char *code;}CharMapNode,*CharMap;

第三章 程序設計及其實現

3.1 從文件讀入原文

void Huffman::ReadTextFromFile(char *filename){

} ifstream infile(filename);if(!infile){

} char c;while(infile.get(c)){ } text += c;cerr << “無法打開文件！” <

void Huffman::CountCharsWeight(){

if(text.empty())return;delete chars;if(chars!= NULL)int i = 0;n = 0;chars = new CharMapNode[2];chars[1].c = text[i];chars[1].weight = 1;++n;for(i = 1;i!= text.size();++i){ int j;

//遍歷當前字符表，如果已存在該字符，for(j = 1;j <= n;++j)權值+1

{

if(text[i] == chars[j].c){

++chars[j].weight;4

} }

break;

if(j > n)//該字符不存在，添加該字符

{

++n;

CharMap newchars = new CharMapNode[n + 1];

memcpy(newchars, chars, n * sizeof(CharMapNode));

delete chars;

chars = newchars;

chars[n].c = text[i];

chars[n].weight = 1;

} } } 3.3 編碼

void Huffman::MakeCharMap(){ if(n <= 1)

return;int m = 2 * n1, s1, s2);

huffTree[s1].parent = huffTree[s2].parent = i;

huffTree[i].lchild = s1;

huffTree[i].rchild = s2;

huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;}

//從葉子到根節點逆向求每個字符的哈弗曼編碼

char *cd = new char[n];//分配求編碼的工作空間（每個字符編碼結果最長n-1再加上'