一、實驗名稱

HuffmanTree 編碼的實現

二、實驗目的：

1．掌握二叉樹的定義；

2．掌握哈夫曼樹和哈夫曼編碼算法的實現。刪除等。

三、實驗內容：

實現一個哈夫曼編碼系統，系統包括以下功能：

(1) 字符信息統計：讀取待編碼的源文件SourceFile.txt，統計出現的字符及其頻率。

(2) 建立哈夫曼樹：根據統計結果建立哈夫曼樹。

(3) 建立哈夫曼碼表：利用得到的哈夫曼樹，將各字符對應的編碼表保存在文件Code.txt中。

(4) 對源文件進行編碼：根據哈夫曼碼表，將SourceFile.txt中的字符轉換成相應的編碼文件ResultFile.txt。

//博主鑒于txt文件，內容可以由操作者自己輸入，所以在代碼中并沒有體現出讀文件的功能，有能力的操作者可以自己編碼。

實現提示：

(1) 字符信息統計：

假設源文件SourceFile.txt中的字符只有大小寫英文字母（同一個字母的大小寫看作一個字符），則字符統計算法的實現過程可以歸納為：先定義一個含有26個元素的整形數組，用來存儲各個字母出現的次數，最后還要排除其中出現次數為0的數組元素。

(2) 建立哈夫曼樹：參考教材算法5.10，補充函數Select的實現。

//本文章中有兩個select函數，一個是答主自己寫的，一個是另一位博主的，如有侵權，本文章立馬刪除。

(3) 建立哈夫曼碼表：參考教材算法5.11，將編譯表HC中的內容寫到文件Code.txt中。

(4) 對源文件進行編碼：依次讀入文件SourceFile.txt中的字符 c，在編碼表 HC 中找到此字符，將字符c轉換為編碼表中存放的編碼串，寫入編碼文件ResultFile.txt中，直到所有的字符處理完畢為止。

//本文章中提到的教材為清華大學嚴蔚敏版以類C語言為基礎的《數據結構》

選做內容:

完成譯碼功能：對任意一個給定的由01組成的文件，根據哈夫曼碼表翻譯成由字符組成的源文件。

提示：

對文件進行譯碼的過程必須借助于哈夫曼樹。具體過程是：依次讀入文件的二進制碼，從哈夫曼樹的根結點（即HT[m]）出發，若當前讀入0，則走向左孩子，否則走向右孩子。一旦到達某一葉子HT[i]時便譯出相應的字符編碼HC[i]。然后重新從根出發繼續譯碼，直至文件結束。

實驗要求：

(1) 程序要具在一定的健壯性，即當輸入數據非法時，程序也能適當地做出反應。

(2) 程序要添加適當的注釋，程序的書寫要采用縮進格式。

四、實驗的源代碼

<HuffmanTree.h>

#pragma once #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #define MAX 65534 typedef struct {int weight;int parent, lchild, rchild; }HTNode,*HuffmanTree;typedef char** HuffmanCode;//為后續創建一個指針數組準備void CreateHuffmanTree(HuffmanTree& HT, int n);void Select(HuffmanTree HT, int m, int &s1, int &s2);void PrintHuffmanTree(HuffmanTree HT, int n);void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n);void ReadInput(int* count, char ch);void PrintWeight(int* count);void CreateHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n);void OutputHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n);

<HuffmanTree.cpp>

#include "HuffmanTree.h"//void Select(HuffmanTree HT, int m, int& s1, int& s2) { // int i = 0; // int* num = new int[m+1]; // for (i = 1; i <= m; i++) { // if (HT[i].parent == 0) // num[i] = HT[i].weight; // } // for (i = 1; i <= m; i++) { // s1 = 1; // if (num[i] < num[s1]) { // s1 = i; // } // }//查找權值最小的 // for (i = 1; (i <= m)&&(i!=s1); i++) { // s2 = 1; // if (num[i] < num[s2]) { // s2 = i; // } // }//查找權值第2小的 // delete num;//刪除臨時數組； //}void Select(HuffmanTree HT, int n, int& s1, int& s2) {int i;s1 = s2 = 0;for (i = 1; i <= n; i++) {if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && s2 != 0) {if (HT[i].weight < HT[s1].weight) {s2 = s1; s1 = i;}else s2 = i;}if ((s1 == 0 || s2 == 0) && HT[i].parent == 0) {if (s1 == 0) s1 = i;else if (s2 == 0) {if (HT[i].weight < HT[s1].weight) {s2 = s1; s1 = i;}else s2 = i;}}}if (s1 > s2) {i = s1; s1 = s2; s2 = i;} }void CreateHuffmanCode(HuffmanTree HT, HuffmanCode& HC,int n) {HC = new char* [n + 1];//HC是一個指針數組的名稱，數組里的每一個指針指向每個字符串開頭；char* cd = new char[n];//cd是一個一維數組，用來存放當前讀到的字符的編碼cd[n - 1] = '\0';//倒序記錄。int i = 0;for (i = 1; i <= n; i++) {int start = n - 1;int c = i;int f = HT[i].parent;while (f != 0) {--start;if (HT[f].lchild == c)cd[start] = '0';//結點c是f的左孩子，則生成編碼0elsecd[start] = '1';c = f;f = HT[f].parent;//繼續向上回溯}//求出第i個字符的編碼HC[i] = new char[n - start];//為第i個字符編碼分配空間strcpy(HC[i], &cd[start]);//將求得的編碼從臨時空間cd復制到HC的當前行中}delete cd;//釋放臨時空間cd }void CreateHuffmanTree(HuffmanTree& HT, int n) {if (n <= 1) return;int m = 2 * n - 1;int s1 = 0;int s2 = 0;HT = new HTNode[m + 1];//0號單元不用，所以動態分配m+1個單元，HT[m]表示根節點int i = 0;for (i = 1; i <= m; i++) {//將1~m號單元中的雙親，左孩子，右孩子下標置為0；HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;HT[i].weight = 0;}for (i = 1; i <= n; i++) {printf("請輸入第%d個葉子節點的權值：",i);scanf("%d", &HT[i].weight);}for (i = n + 1; i <= m; ++i) {//通過n-1次的選擇，刪除，合并來創建哈夫曼樹Select(HT, i - 1, s1, s2);//在HT[k](1<=k<=i-1)中選擇兩個其雙親域為0且權值最小的結點，并返回他們//在HT中的序號s1和s2HT[s1].parent = i;HT[s2].parent = i;//得到新節點i,從森林中刪除s1,s2將s1和s2的雙親域由0改成i；HT[i].lchild = s1;HT[i].rchild = s2;//s1和s2分別作為i的左右孩子；HT[i].weight = HT[s1].weight + HT[s2].weight;//i的權值為左右孩子權值之和}}void PrintHuffmanTree(HuffmanTree HT,int n) {int i = 0;int m = 2*n - 1;printf("HT初態:\n 結點 weight parent lchild rchild");for (i = 1; i <= m; i++)printf("\n%4d%8d%8d%8d%8d", i, HT[i].weight,HT[i].parent, HT[i].lchild, HT[i].rchild); }void ReadInput(int* count, char ch) {printf("請輸入你的文章：\n");while ((ch = getchar()) != EOF) {if (ch == 'a' || ch == 'A')count[1]++;else if (ch == 'b' || ch == 'B')count[2]++;else if (ch == 'c' || ch == 'C')count[3]++;else if (ch == 'd' || ch == 'D')count[4]++;else if (ch == 'e' || ch == 'E')count[5]++;else if (ch == 'f' || ch == 'F')count[6]++;else if (ch == 'g' || ch == 'G')count[7]++;else if (ch == 'h' || ch == 'H')count[8]++;else if (ch == 'i' || ch == 'I')count[9]++;else if (ch == 'j' || ch == 'J')count[10]++;else if (ch == 'k' || ch == 'K')count[11]++;else if (ch == 'l' || ch == 'L')count[12]++;else if (ch == 'm' || ch == 'M')count[13]++;else if (ch == 'n' || ch == 'N')count[14]++;else if (ch == 'o' || ch == 'O')count[15]++;else if (ch == 'p' || ch == 'P')count[16]++;else if (ch == 'q' || ch == 'Q')count[17]++;else if (ch == 'r' || ch == 'R')count[18]++;else if (ch == 's' || ch == 'S')count[19]++;else if (ch == 't' || ch == 'T')count[20]++;else if (ch == 'u' || ch == 'U')count[21]++;else if (ch == 'v' || ch == 'V')count[22]++;else if (ch == 'w' || ch == 'W')count[23]++;else if (ch == 'x' || ch == 'X')count[24]++;else if (ch == 'y' || ch == 'Y')count[25]++;else if (ch == 'z' || ch == 'Z')count[26]++;} }void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) {int i;printf("\nnumber---weight---huffman code\n");for (i = 1; i <= n; i++)printf(" %d %d %s\n", i, HT[i].weight, HC[i]); }void PrintWeight(int* count) {int i = 0;int sum = 0;for (i = 1; i < 27; i++) {if (count[i] != 0) {sum++;printf(" %d %c或%c %d\n", sum, 65 + i - 1, 97 + i - 1, count[i]);}} }

<test.cpp>

#include "HuffmanTree.h" int main() {int n = 0;char ch = 0;int count[27] = { 0 };ReadInput(count, ch);printf("\n------位次------字母------權值\n");PrintWeight(count);printf("請輸入準備構建的HuffmanTree的節點數：\n");scanf("%d", &n);HuffmanTree HT=NULL;CreateHuffmanTree(HT, n);PrintHuffmanTree(HT, n);HuffmanCode HC;CreateHuffmanCode(HT, HC, n);PrintHuffmanCode(HT, HC, n);return 0; }

五、總結與反思

如果只有一個或者沒有字符，則沒有編碼的必要，直接return。注意，這里是void類型的函數，return 后面不加東西，表示退出函數。設置一個指針p來進行對數據的錄入。其實只用*HT也是可以的，但每次進行指針的操作之后，就得進行HT–的循環來回到第一個存儲單位，時間復雜度就會大大增加。在設置一個指針時，先讓指針指向NULL，再將指針賦予其他值。文章中只能含有26個大小寫字母，逗號，空格，句號這55種常用字符。其余的符號太多,未寫進程序。文章不能太長，因為我默認所有字符的權值不超過2000，Huffman編碼長度不超過6位1.將所有結點放入集合 K。若集合 K 中剩余結點大于 2 個，則取出其中權值最小的兩個結點，構造他們同時為某個新節點的左右兒子，該新節點是他們共同的雙親結點，設定它的權值為其兩個兒子結點的權值和。并將該父親結點放入集合 K。重復步驟。若集合 K 中僅剩余一個結點，該結點即為構造出的哈夫曼樹數的根結點， 所有構造得到的中間結點(即哈夫曼樹上非葉子結點)的權值和即為該哈夫曼樹的帶權路徑和。為了方便快捷高效率的求得集合 K 中權值最小的兩個元素，我們需要使用堆數據結構。它可以以 O（logn）的復雜度取得 n 個元素中的最小元素。

總結

以上是生活随笔為你收集整理的AHU HuffmanTree编码数据结构实验的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。