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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：23 大?。?88.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-哈夫曼編碼譯碼器_第1頁

已閱讀1頁，還剩22頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　課程設(shè) 計　　課程名稱_ _數(shù)據(jù)結(jié)構(gòu)課程設(shè)計_ 　　題目名稱_ 哈夫曼編碼譯碼器_ 　　學(xué)生學(xué)院 　　專業(yè)班級

2、 　　學(xué) 號 　　學(xué)生姓名 　　指導(dǎo)教師 　　2011 年 12月 23日

3、　　摘要：　　在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。　　關(guān)鍵字：

4、　　哈夫曼樹編碼解碼數(shù)據(jù)壓縮技術(shù)　　目錄　　摘要：1　　關(guān)鍵字：1　　第一章需求分析3</p

5、>　　第二章數(shù)據(jù)結(jié)構(gòu)定義及其操作實現(xiàn)3　　第三章程序設(shè)計及其實現(xiàn)3　　3.1 從文件讀入原文3　　3.2 統(tǒng)計原文中各字符的權(quán)值4　　3.3 編碼5

6、;　　3.4 解碼6　　3.5 主函數(shù)7　　第四章運行結(jié)果及其分析8　　第五章問題及其解決方法10　　第六章心得體會（設(shè)計總結(jié)）10　　附錄——源程序11</p&g

7、t;　　1、頭文件11　　2、赫夫曼編碼算法12　　3、主函數(shù)18　　參考文獻21　　需求分析</p&g

8、t;　　1．問題要求：打開一篇英文文章，統(tǒng)計出每個字符出現(xiàn)的次數(shù)，然后以他們?yōu)闄?quán)值，對每個字符進行編碼，編碼完成后對其編碼進行譯碼。　　程序運行環(huán)境：windows、visual c++或java等　　要求：　　輸入一篇英文文章，根據(jù)字符出現(xiàn)的次數(shù)給出哈

9、夫曼編碼方式。　　對英文文章進行編碼；　　對編碼進行譯碼核對正確性　　數(shù)據(jù)結(jié)構(gòu)定義及其操作實現(xiàn)　　2.1 哈弗曼樹節(jié)點　　typedef struct 　　{</b

10、>　　unsigned int weight;　　unsigned int parent;　　unsigned int lchild;　　unsigned int rchild;　　}HuffTreeNode,*HuffTr

11、ee;　　2.2 字符-權(quán)值-編碼映射　　typedef struct　　{　　char c;　　unsigned int weight;</p&g

12、t;　　char *code;　　}CharMapNode,*CharMap;　　程序設(shè)計及其實現(xiàn)　　3.1 從文件讀入原文　　void Huffman::ReadTextFromFile(char *filen

13、ame)　　{　　ifstream infile(filename);　　if(!infile)　　{　　cerr << "無法打開

14、文件！" <<endl;　　return;　　}　　char c;　　while(infile.get(c))&

15、lt;p>　　{　　text += c;　　}　　} 　　3.2 統(tǒng)計原文中各字符的權(quán)值　　void Huf

16、fman::CountCharsWeight()　　{　　if (text.empty())　　return;　　if (chars != NULL)

17、delete chars;　　int i = 0;　　n = 0;　　chars = new CharMapNode[2];　　chars[1].c = text[i];　　chars[1].

18、weight = 1;　　++n;　　for (i = 1; i != text.size(); ++i)　　{　　int j;<

19、;p>　　for (j = 1; j <= n; ++j)//遍歷當(dāng)前字符表，如果已存在該字符，權(quán)值+1　　{　　if (text[i] == chars[j].c)　　{　　++c

20、hars[j].weight;　　break;　　}　　}　　if (j > n)//該字符不存在，添加該字符<p&g

21、t;　　{　　++n;　　CharMap newchars = new CharMapNode[n + 1];　　memcpy(newchars, chars, n * sizeof(CharMapNode));&

22、lt;p>　　delete chars;　　chars = newchars;　　chars[n].c = text[i];　　chars[n].weight = 1;　　}<b&

23、gt;　　}　　}　　3.3 編碼　　void Huffman::MakeCharMap()　　{<p&g

24、t;　　if (n <= 1)　　return;　　int m = 2 * n - 1;//哈弗曼樹所需節(jié)點數(shù)　　huffTree = new HuffTreeNode[m+1];//0號單元未使用

25、//初始化　　int i;　　for (i = 1; i <= n; ++i)　　{　　huffTree[i].weight = chars[i].weight;<

26、/p>　　huffTree[i].parent = 0;　　huffTree[i].lchild = 0;　　huffTree[i].rchild = 0;　　}　　for (i = n + 1; i &l

27、t;= m; ++i)　　{　　huffTree[i].weight = 0;　　huffTree[i].parent = 0;　　huffTree[i].lchild = 0;　　huffT

28、ree[i].rchild = 0;　　}　　//建哈弗曼樹　　for (i = n + 1; i <= m; ++i)　　{&

29、lt;p>　　int s1,s2;　　select(i - 1, s1, s2);　　huffTree[s1].parent = huffTree[s2].parent = i;　　huffTree[i].lchild = s1;　　huffTree[i].rchi

30、ld = s2;　　huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;　　}　　//從葉子到根節(jié)點逆向求每個字符的哈弗曼編碼　　char *cd = new

31、char[n];//分配求編碼的工作空間（每個字符編碼結(jié)果最長n-1再加上'\0'）　　cd[n-1] = '\0';//編碼結(jié)束符　　for(i = 1; i <= n; ++i)//逐個字符求哈弗曼編碼　　{</p&

32、gt;　　int start = n - 1;　　int c,f;　　//從葉子到根逆向求編碼　　for (c = i, f = huffTree[i].parent; f != 0; c = f, f = huffTree[f].parent)<

33、/p>　　{　　if (huffTree[f].lchild == c)//左孩子編碼為0　　cd[--start] = '0';　　else//右孩子編碼為1　　cd[--

34、start] = '1';　　}　　chars[i].code = new char[n - start];//為第i個字符編碼分配空間　　strcpy(chars[i].code,&cd[start]);&

35、lt;b>　　}　　delete cd;　　}　　3.4 解碼　　void Huffman::Decode()<b&g

36、t;　　{　　text = "";　　string::size_type i,count;　　for (i = 0; i < code.size(); i += count)　　{<

37、/p>　　//每個字符的編碼結(jié)果最長n-1，從1至n-1依次嘗試　　for (count = 1; count < n; ++count)　　{　　for (int j = 1; j <= n; ++j)<

38、p>　　if (code.substr(i, count) == chars[j].code)　　{　　text += chars[j].c;　　goto next;　　}

39、;　　}　　next:　　;　　}　　}

40、　　3.5 主函數(shù)　　int main()　　{　　cout << " ********************************************************

41、****" << endl;　　cout << " * *" << endl;　　cout << " *

42、哈夫曼編碼譯碼器 *" << endl;　　cout << " * 1、打開一篇英文文章或輸入一篇文章 *"<< endl;　　cout << " *

43、 2、根據(jù)字符出現(xiàn)的次數(shù)以他們?yōu)闄?quán)值給出哈夫曼編碼方式 *" << endl;　　cout << " * 3、對英文文章進行編碼 *" << endl;　　cout << "

44、 * 4、對編碼進行譯碼核對正確性 *" << endl;　　cout << " * *" << endl;<p&

45、gt;　　cout << " ************************************************************" << endl<<endl;　　system("pause");　　cout << endl;</

46、p>　　Huffman huffman;　　huffman.ReadTextFromFile("text.txt");　　cout << "程序自動統(tǒng)計字符和權(quán)值" << endl;　　huffman.CountChars

47、Weight();　　cout << endl;　　cout << "字符及對應(yīng)權(quán)值：" << endl;　　huffman.PrintCharWeight();　　cout << endl;</p

48、>　　system("pause");　　cout << endl;　　huffman.MakeCharMap();　　cout << "字符及對應(yīng)編碼：" << endl;<p&

49、gt;　　huffman.PrintCharCode();　　cout << endl;　　system("pause");　　cout << endl;　　cout << "對原文進行編碼："

50、<< endl;　　cout << "原文：" << endl;　　huffman.PrintText();　　huffman.Encode();　　cout << endl;&l

51、t;p>　　cout << "編碼：" << endl;　　huffman.PrintCode();　　huffman.SaveCodeToFile("code.txt");　　cout << endl;&l

52、t;p>　　system("pause");　　cout << endl;　　cout << "對編碼進行解碼：" << endl;　　huffman.ReadCodeFromFile("code.txt");&

53、lt;/p>　　cout << "編碼：" << endl;　　huffman.PrintCode();　　huffman.Decode();　　cout << endl;　　cout &

54、lt;< "原文：" << endl;　　huffman.PrintText();　　huffman.SaveTextToFile("resulttext.txt");　　cout << endl;&l

55、t;b>　　return 0;　　}　　運行結(jié)果及其分析　　本次測試是先建立一個名為test.txt的文本文檔，內(nèi)容為：This is my HuffmanCoding.

56、　　運行程序，結(jié)果如圖：　　問題及其解決方法　　編碼不熟練，經(jīng)常出現(xiàn)漏符號或多符號，多次調(diào)試改正　　C++不熟練，讀取保存文件出錯，回歸課本，改正代碼　　心得體會（設(shè)計總結(jié)）　　在課程設(shè)計過程

57、中，我們每個人選擇一個課題，認真研究，根據(jù)課堂講授內(nèi)容，借助書本，自己動手實踐。這樣不但有助于我們消化課堂所講解的內(nèi)容，還可以增強我們的獨立思考能力和動手能力；通過編寫實驗代碼和調(diào)試運行，我們可以逐步積累調(diào)試C程序的經(jīng)驗并逐漸培養(yǎng)我們的編程能力、用計算機解決實際問題的能力。　　在課程設(shè)計過程中，我們不但有自己的獨立思考，還借助各種參考文獻來幫助我們完成系統(tǒng)。更為重要的是，我們同學(xué)之間加強了交流，

58、在對問題的認識方面可以交換不同的意見。　　數(shù)據(jù)結(jié)構(gòu)課程具有比較強的理論性，同時也具有較強的可應(yīng)用性和實踐性。課程設(shè)計是一個重要的教學(xué)環(huán)節(jié)。我們在一般情況下都能夠重視實驗環(huán)節(jié)，但是容易忽略實驗的總結(jié)，忽略實驗報告的撰寫。通過這次實驗讓我們明白：作為一名大學(xué)生必須嚴(yán)格訓(xùn)練分析總結(jié)能力、書面表達能力。需要逐步培養(yǎng)書寫科學(xué)實驗報告以及科技論文的能力。只有這樣，我們的綜合素質(zhì)才會有好的提高。</p&

59、gt;　　附錄——源程序　　頭文件　　// Huffman.h　　#pragma once　　#endif // _MSC_VER > 1000

60、　　#include <string>　　/***********************數(shù)據(jù)結(jié)構(gòu)***********************/　　//哈弗曼樹節(jié)點　　typedef struct &l

61、t;b>　　{　　unsigned int weight;　　unsigned int parent;　　unsigned int lchild;　　unsigned int rchild;　　}Huff

62、TreeNode,*HuffTree;　　//字符-權(quán)值-編碼映射　　typedef struct　　{　　char c;　　unsigned int w

63、eight;　　char *code;　　}CharMapNode,*CharMap;　　/*************************類定義****************************/　　class Huffman <

64、p>　　{　　private:　　void select(int n, int &s1, int &s2);　　HuffTree huffTree;//哈弗曼樹　　Char

65、Map chars;//字符表　　int n;//字符數(shù)　　std::string text;//原文　　std::string code;//編碼　　public:

66、void InputCharsWeight();　　void CountCharsWeight();　　void Decode();　　void ReadTextFromFile(char *filename);　　void ReadCodeFromFile(char *

67、filename);　　void SaveTextToFile(char *filename);　　void SaveCodeToFile(char *filename);　　void PrintCode();　　void MakeCharMap();

68、　　void PrintText();　　void PrintCharCode();　　void PrintCharWeight();　　void SetCharMap(CharMap m, int number);　　void Encode();

69、　　Huffman();　　virtual ~Huffman();　　};　　赫夫曼編碼算法　　// Huffman.cpp<

70、;p>　　#include "Huffman.h"　　#include <iostream>　　#include <fstream>　　using namespace std;　　Huffman::Huffman()<

71、;/p>　　{　　huffTree = NULL;　　chars = NULL;　　n = 0;　　}&l

72、t;p>　　Huffman::~Huffman()　　{　　}　　void Huffman::Encode()　　{<p&

73、gt;　　code = "";　　for (string::size_type i = 0; i != text.size(); ++i)　　{　　for (int j = 1; j <= n; ++j)

74、if (chars[j].c == text[i])　　code += chars[j].code;　　}　　}　　void Huffman::SetCharMap(CharMap m, int

75、number)　　{　　chars = m;　　n = number;　　}　　void Huffman::select(int n, int &

76、s1, int &s2)　　{　　s1 = s2 = 0;　　for (int i = 1; i <= n; ++i)　　{　　if (hu

77、ffTree[i].parent != 0)　　continue;　　if (s1 == 0)　　s1 = i;　　else if (s2 == 0)&l

78、t;b>　　{　　if (huffTree[i].weight < huffTree[s1].weight)　　{　　s2 = s1;　　s1 =

79、 i;　　}　　else　　s2 = i;　　}<b

80、>　　else　　{　　if (huffTree[i].weight < huffTree[s1].weight)　　{　　s2 = s1;<

81、;/b>　　s1 = i;　　}　　else if (huffTree[i].weight < huffTree[s2].weight)　　s2 = i;</b

82、>　　}　　}　　}　　void Huffman::PrintCharWeight()　　{

83、　　for (int i = 1; i <= n; ++i)　　{　　switch (chars[i].c)　　{　　case

84、'\t':　　cout << "\\t";　　break;　　case '\n':　　cout << "\\n";

85、　　break;　　default:　　cout << chars[i].c;　　break;　　}</

86、b>　　cout << "——" << chars[i].weight << endl;　　}　　}　　void Huffman::P

87、rintCharCode()　　{　　for (int i = 1; i <= n; ++i)　　{　　switch (chars[i].c)<

88、;b>　　{　　case '\t':　　cout << "\\t";　　break;　　case '\n':<p&

89、gt;　　cout << "\\n";　　break;　　default:　　cout << chars[i].c;　　break;&

90、lt;/b>　　}　　cout << "——" << chars[i].code << endl;　　}　　}<

91、;/b>　　void Huffman::PrintText()　　{　　cout << text << endl;　　}

92、void Huffman::PrintCode()　　{　　cout << code << endl;　　}　　void Huffman::MakeCharMap()<

93、;/p>　　{　　if (n <= 1)　　return;　　int m = 2 * n - 1;　　huffTree = new HuffTreeNode[

94、m+1];　　int i;　　for (i = 1; i <= n; ++i)　　{　　huffTree[i].weight = chars[i].weight;&

95、lt;p>　　huffTree[i].parent = 0;　　huffTree[i].lchild = 0;　　huffTree[i].rchild = 0;　　}　　for (i = n + 1; i <= m; ++

96、i)　　{　　huffTree[i].weight = 0;　　huffTree[i].parent = 0;　　huffTree[i].lchild = 0;　　huffTree[i].rc

97、hild = 0;　　}　　for (i = n + 1; i <= m; ++i)　　{　　int s1,s2;　　select(i - 1, s

98、1, s2);　　huffTree[s1].parent = huffTree[s2].parent = i;　　huffTree[i].lchild = s1;　　huffTree[i].rchild = s2;　　huffTree[i].weight = huffTr

99、ee[s1].weight + huffTree[s2].weight;　　}　　char *cd = new char[n];　　cd[n-1] = '\0';　　for(i = 1; i <= n;

100、++i)　　{　　int start = n - 1;　　int c,f;　　for (c = i, f = huffTree[i].parent; f != 0; c = f, f = hu

101、ffTree[f].parent)　　{　　if (huffTree[f].lchild == c)　　cd[--start] = '0';　　else　　cd

102、[--start] = '1';　　}　　chars[i].code = new char[n - start];　　strcpy(chars[i].code,&cd[start]);　　}&

103、lt;/b>　　delete cd;　　}　　void Huffman::ReadTextFromFile(char *filename)　　{

104、ifstream infile(filename);　　if(!infile)　　{　　cerr << "無法打開文件！" <<endl;　　return;</b&g

105、t;　　}　　char c;　　while(infile.get(c))　　{　　text += c;</p&

106、gt;　　}　　}　　void Huffman::SaveCodeToFile(char *filename)　　{　　ofstream

107、 outfile(filename);　　if (!outfile)　　{　　cerr << "保存文件出錯！" << endl;　　return;&l

108、t;/p>　　}　　outfile << code;　　}　　void Huffman::ReadCodeFromFile(char *filename)&

109、lt;b>　　{　　ifstream infile(filename);　　if (!infile)　　{　　cerr << "無法打開文件！" <<endl;&l

110、t;/p>　　return;　　}　　infile >> code;　　}　　void Huffman::Decode

111、()　　{　　text = "";　　string::size_type i,count;　　for (i = 0; i < code.size(); i += count)<p

112、>　　{　　for (count = 1; count < n; ++count)　　{　　for (int j = 1; j <= n; ++j)　　if (code.subs

113、tr(i, count) == chars[j].code)　　{　　text += chars[j].c;　　goto next;　　}

114、;　　}　　next:　　;　　}　　}　　void Hu

115、ffman::CountCharsWeight()　　{　　if (text.empty())　　return;　　if (chars != NULL)

116、　delete chars;　　int i = 0;　　n = 0;　　chars = new CharMapNode[2];　　chars[1].c = text[i];　　chars[1]

117、.weight = 1;　　++n;　　for (i = 1; i != text.size(); ++i)　　{　　int j;&l

118、t;p>　　for (j = 1; j <= n; ++j)　　{　　if (text[i] == chars[j].c)　　{　　++chars[j].weight;</p&

119、gt;　　break;　　}　　}　　if (j > n)　　{&

120、lt;p>　　++n;　　CharMap newchars = new CharMapNode[n + 1];　　memcpy(newchars, chars, n * sizeof(CharMapNode));　　delete chars;&l

121、t;p>　　chars = newchars;　　chars[n].c = text[i];　　chars[n].weight = 1;　　}　　}

122、　　}　　void Huffman::SaveTextToFile(char *filename)　　{　　ofstream outfile(filename);　　if (!outfile)&l

123、t;/p>　　{　　cerr << "保存文件出錯！" << endl;　　return;　　}<

124、p>　　outfile << text;　　}　　主函數(shù)　　//main.cpp　　#include <iostream>

125、　#include "Huffman.h"　　using namespace std;　　int main()　　{　　cout << " *********************

126、***************************************" << endl;　　cout << " * *" << endl;　　cout &l

127、t;< " * 哈夫曼編碼譯碼器 *" << endl;　　cout << " * 1、打開一篇英文文章或輸入一篇文章 *"<< endl;<

128、;p>　　cout << " * 2、根據(jù)字符出現(xiàn)的次數(shù)以他們?yōu)闄?quán)值給出哈夫曼編碼方式 *" << endl;　　cout << " * 3、對英文文章進行編碼 *" << endl;

129、　　cout << " * 4、對編碼進行譯碼核對正確性 *" << endl;　　cout << " * *&quo

130、t; << endl;　　cout << " ************************************************************" << endl<<endl;　　system("pause");

131、　　cout << endl;　　Huffman huffman;　　huffman.ReadTextFromFile("text.txt");　　cout << "程序自動統(tǒng)計字符和權(quán)值" << endl;</p

132、>　　huffman.CountCharsWeight();　　cout << endl;　　cout << "字符及對應(yīng)權(quán)值：" << endl;　　huffman.PrintCharWeight();&

133、lt;p>　　cout << endl;　　system("pause");　　cout << endl;　　huffman.MakeCharMap();　　cout << "字符及對應(yīng)編碼：&quo

134、t; << endl;　　huffman.PrintCharCode();　　cout << endl;　　system("pause");　　cout << endl;

135、cout << "對原文進行編碼：" << endl;　　cout << "原文：" << endl;　　huffman.PrintText();　　huffman.Encode();

136、　　cout << endl;　　cout << "編碼：" << endl;　　huffman.PrintCode();　　huffman.SaveCodeToFile("code.txt");

137、　　cout << endl;　　system("pause");　　cout << endl;　　cout << "對編碼進行解碼：" << endl;　　huffman.ReadC

138、odeFromFile("code.txt");　　cout << "編碼：" << endl;　　huffman.PrintCode();　　huffman.Decode();　　cout <<

139、 endl;　　cout << "原文：" << endl;　　huffman.PrintText();　　huffman.SaveTextToFile("resulttext.txt");　　cout &l

140、t;< endl;　　return 0;　　}　　參考文獻　　[1] 嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)(C語言版)，清華大學(xué)出版社，2007　　[2]

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載