北邮信通院数据结构实验报告三哈夫曼编码器 - 图文 

.

{

int parent = 2*n-2;

//根结点在HTree中的下标

while (HTree[parent].LChild!=-1) //如果不是叶子结点 {

if (*s=='0') else

parent = HTree[parent].RChild; parent = HTree[parent].LChild;

}

}

}

s++;

*d = HCodeTable[parent].data; d++;

时间复杂度为O（n）

2.3 其他

（1）哈夫曼树的输出是以凹入表示法来实现的，具体算法如下： void Huffman::Print(int i, int m) { if (HTree[i].LChild == -1) cout<

.

.

（2）统计字符頻数时，利用字符的ASCII码进行计数统计，调用了cin.get()函数

3. 程序运行

程序框图： 开始

输入要编码的字符串

统计字符頻数

生成哈夫曼树

创建编码表

生成编码串

解码 结束

程序源代码：

#include #include using namespace std;

.

.

struct HNode {

int weight; //结点权值 int parent; //双亲指针 int LChild; //左孩子指针 int RChild ; //右孩子指针 };

struct HCode {

char data;

char code[100]; };

class Huffman {

private:

HNode* HTree; //Huffman树 HCode* HCodeTable; //Huffman编码表 char str[1024]; //输入的原始字符串 char l[256]; //叶子节点对应的字符

int a[256]; //记录每个出现的字符的个数 public:

int n; //叶子节点数

void Init(); //初始化 void CreateHTree(); //创建huffman树 void CreateCodeTable(); //创建编码表 void PrintTable();

void Encode(char *d); //编码 void Decode(char *s, char *d); //解码

void Print(int i,int m); //打印Huffman树

void SelectMin( HNode *hTree,int n, int &i1, int &i2);//找出最小的两个权值

void Reverse(char* s); //逆序

void Compare(char*d); //比较压缩大小 ~ Huffman(); //析构 };

void Huffman::Init() {

int nNum[256]= {0}; //记录每一个字符出现的次数 int ch = cin.get(); int i=0;

while((ch!='\\r') && (ch!='\\n'))

.

.

{ nNum[ch]++; //统计字符出现的次数 str[i++] = ch; //记录原始字符串 ch = cin.get(); //读取下一个字符 }

str[i]='\\0'; n = 0;

for ( i=0;i<256;i++) { if (nNum[i]>0) //若nNum[i]==0，字符未出现 { l[n] = (char)i; a[n] = nNum[i]; n++; } } }

void Huffman::CreateHTree() {

HTree = new HNode [2*n-1]; //根据权重数组a[0..n-1] 初始化Huffman树

for (int j = 0; j < n; j++) { HTree[j].weight = a[j]; HTree[j].LChild = HTree[j].RChild = HTree[j].parent = -1; }

int x,y;

for (int i = n; i < 2*n-1; i++) //开始建Huffman树 { SelectMin( HTree, i, x, y); //从1~i中选出两个权值最小的结点 HTree[x].parent = HTree[y].parent = i; HTree[i].weight = HTree[x].weight+ HTree[y].weight; HTree[i].LChild = x; HTree[i].RChild = y; HTree[i].parent = -1; } }

void Huffman::SelectMin( HNode *hTree,int n, int &i1, int &i2 ) {

int i;

//找一个比较值的起始值 for(i=0; i

.

.

{ if(hTree[i].parent==-1 )

{ i1=i; break; } } i++;

for( ; i

{ if(hTree[i].parent==-1 )

{ i2=i; break; } }

if(hTree[i1].weight>hTree[i2].weight) //i1指向最小的 { int j=i2; i2=i1; i1 = j; } //开始找最小的两个 i++;

for( ; i

{ if(hTree[i].parent==-1

&& hTree[i].weight < hTree[i1].weight ) { i2=i1; i1 = i; } else if( hTree[i].parent==-1

&& hTree[i].weight < hTree[i2].weight) { i2=i; } } }

void Huffman::Print(int i, int m) {

if (HTree[i].LChild == -1) cout<

')<

void Huffman::CreateCodeTable() {

HCodeTable = new HCode[n]; //生成编码表 for (int i=0;i

int parent = HTree[i].parent; //当前结点的父结点编号 int k=0;

while(parent!=-1) {

.