数据结构第三次实验报告

数据结构实验报告

实验三 哈夫曼树实验

班级：_计2-1___ 姓名：_依力夏提江·艾买尔__ 学号：_12101020129_

实验目的：

熟悉非线性结构的特点 , 掌握非线性结构的存储方式及各种操作的实现方法，同时对自顶向下的程序设计方法、应用程序界面的设计、非线性结构的文件存储方法等方面的辑程技术进行训练。

问题描述：

利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。

基本要求：

一个完整的系统应具有以下功能：

（1） I： 初始化。从终端读入字符集大小 n ，及 n 个字符和 n 个权值，建立哈夫曼树，

并将其存于文件hfmtree中。

（2） C： 编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文

件tobetrans中的正文进行编码，然后将结果存入文件codefile中。

（3） D： 译码。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件

textfile中。

（4） P： 打印代码文件。将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时

将此字符形式的编码文件写入文件codeprint中。

（5） T：打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹凸表形式）显示

在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。

需求分析：（包括对问题的理解，解决问题的策略、方法描述）

本程序实现了使用赫夫曼编码压缩数据；输入一串字符串sourceCode——为方便理解，暂时要求字符串只包含大写字母和空格，如果你愿意，很容易就可以推广到所有的字符——计算出字符串中各个字母的权重，然后对其进行赫夫曼编码，输出赫夫曼树。将赫夫曼树的叶子结点存储到有序二叉树中，输出原字符串经压缩后得到的用’0’和’1’表示的新字符串destCode；然后利用赫夫曼树将字符串destCode进行译码，得到目标字符串objCode，比较objCode和sourceCode，发现完全一样！

编码译码成功！

最后销毁有序二叉树和赫夫曼树。

系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述） typedef char ElemType;//定

typedef struct sNode

{

double weight;

ElemType data;

} *Source;

typedef struct hNode

{

double weight;

ElemType data;

int lc, rc;

} *HuffmanTree;

typedef struct cNode

{

ElemType data;

string str;

struct cNode *lc, *rc;

} *Btree;

HuffmanTree CreateHuffmanTree(const Source w, int n);//创建一棵赫夫曼树

void BuildHeap(HuffmanTree t, int n); //构造一个二叉堆；小顶堆

void PercDown(HuffmanTree t, int pos, int n);//构造二叉堆的功能子函数

void DeleteMin(HuffmanTree t, int len); /*删除二叉堆的根，并通过上移使得新得到的序列仍为二叉堆*/

void InsertHfNode(HuffmanTree t, int len, struct hNode x); /*把x插入到原长度为len的二叉堆*/

void Preorder(HuffmanTree t, int p); //先序遍历赫夫曼树

void Postorder(Btree & t, HuffmanTree a, int n); /*后序遍历赫夫曼树，并记录叶子结点编码*/

bool InsertBtNode(Btree & t, Btree s); //向一个二叉排序树t中插入一个结点s

void Inorder(Btree t); //中序遍历二叉排序树

Btree Search(Btree p, ElemType data); //查找值为data的结点的递归算法

string Coding(string s, Btree t); /*利用记录了叶子结点编码的排序二叉树，对sourceCode进行编码，返回编码后的字符串*/

string Decode(string s, HuffmanTree hT); //利用赫夫曼树对destCode进行解码 void DestroyBTree(Btree & t); //销毁一棵二叉排序树

void DestroyHfmanTree(HuffmanTree & t, int n); //销毁一棵赫夫曼树

主函数：

int main()

{

string sourceCode;

getline(cin, sourceCode, ’\n’);

int n = sourceCode.size();

const int MAX = 27; //原码由26个大写字母加空格组成

Source w = new struct sNode[MAX];

//读取各个字母并初始化权重

w[MAX-1].data = ’ ’;

w[MAX-1].weight = 0;

for (int i=MAX-2; i>=0; i--)

{

w[i].data = ’A’ + i;

w[i].weight = 0; } //读取各个字母的权重 for (int i=0; i<n; i++) { if (sourceCode[i] == ’ ’) w[26].weight++; else w[sourceCode[i]-’A’].weight++; } //获取出现了的大写字母和空格 n = 0; for (int i=0; i<MAX; i++) { if (w[i].weight > 0) w[n++] = w[i]; } // //直接输入原码和权重 // for (int i=0; i<n; i++) // { // cin >> w[i].weight >> w[i].data; // } for (int i=0; i<n; i++) { cout << w[i].weight << " " << w[i].data << endl; } HuffmanTree hT = CreateHuffmanTree(w, n);//构造赫夫曼树 // for (int i=1; i<2*n; i++) // cout << hT[i].weight << " "; // cout << endl; //先序遍历赫夫曼树，并输出结点权重和叶子结点的data Preorder(hT, 1); cout << endl; //后序遍历赫夫曼树，并记录叶子结点编码 Btree bT = NULL; Postorder(bT, hT, n); //中序遍历记录了叶子结点编码的排序二叉树 Inorder(bT); //利用记录了叶子结点编码的排序二叉树，对sourceCode进行编码 string destCode = Coding(sourceCode, bT); cout << destCode << endl; //利用赫夫曼树对destCode进行解码 string objCode = Decode(destCode, hT); cout << objCode << endl;

DestroyBTree(bT); //销毁二叉排序树

//Inorder(bT); //再输出试试看

DestroyHfmanTree(hT, n); //销毁赫夫曼树

//Preorder(hT, 1); //再输出试试看

system("pause");

return 0;

}

调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）

构造哈夫曼非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。不过因为自己技术还不娴熟所以遇到了很多麻烦，而且也参考了别人的资源，下图输出方式安分布方式给出了哈夫曼树狗仔的过程！

测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）

基本操作的实现：（对各基本操作实现的描述）(后面可加页)

//创建一棵赫夫曼树

HuffmanTree CreateHuffmanTree(const Source w, int n)

{

HuffmanTree hT = new struct hNode[2*n]; //第一个结点不用

for (int i=0; i<n; i++)

{

hT[i+1].data = w[i].data;

hT[i+1].weight = w[i].weight;

hT[i+1].lc = hT[i+1].rc = 0;

}

BuildHeap(hT, n);//构造一个二叉堆；小顶堆

struct hNode add;

int left = n;

int right = n;

while (left > 1)

{

hT[++right] = hT[1];

add.weight = hT[1].weight;

add.lc = right; //存储左孩子下标

DeleteMin(hT, left--); hT[left+1] = hT[1]; add.weight += hT[1].weight; add.rc = left+1; //存储右孩子下标 DeleteMin(hT, left--); InsertHfNode(hT, ++left, add); //for (int i=1; i<=right; i++) // cout << hT[i].weight << " "; // cout << endl; // system("pause"); } return hT; } //构造一个二叉堆；小顶堆 void BuildHeap(HuffmanTree t, int len) { for (int i=len/2+len%2; i>0; i--) { PercDown(t, i, len); } } //构造二叉堆的功能子函数 void PercDown(HuffmanTree t, int pos, int len) { int child; struct hNode min = t[pos]; while (pos * 2 <= len) { child = pos * 2; if (child != len && t[child+1].weight < t[child].weight) child++; if (min.weight > t[child].weight) t[pos] = t[child]; else break; pos = child; } t[pos] = min; } //删除二叉堆的根，并通过上移使得新得到的序列仍为二叉堆 void DeleteMin(HuffmanTree t, int len) { struct hNode last = t[len--];//二叉堆的最后一个元素 int child, pos = 1;

while (pos * 2 <= len) //把二叉堆的某些元素往前移，使得新得到的序列仍为二叉堆 {

child = pos * 2;

if (child != len && t[child+1].weight < t[child].weight) //若i有右儿子，且右儿子小于左儿子，c指向右儿子

child++;

if (last.weight > t[child].weight) //若i的小儿子小于二叉堆的最后一个元素，把其移到i的位置

t[pos] = t[child];

else

break;

pos = child;

}

t[pos] = last; //把二叉堆的最后一个元素放到适当的空位，此时得到的序列仍为二叉堆 }

//把x插入到原长度为len的二叉堆

void InsertHfNode(HuffmanTree t, int len, struct hNode x)

{

int i;

for (i=len; i/2>0 && t[i/2].weight>x.weight; i/=2)

t[i] = t[i/2];

t[i] = x;

}

//后序遍历赫夫曼树，并记录叶子结点编码

void Postorder(Btree & t, HuffmanTree a, int n)

{

int *stack = new int[n];

int *tag = new int[n];

char *buf = new char[n];

bool flag = true;

int top = -1;

int p = 1;

while (a[p].lc > 0 || top >= 0)

{

while (a[p].lc > 0) //先一直寻找左孩子

{

flag = true; //此时p指向的是新叶子（未输出过的叶子）

stack[++top] = p; //结点入栈

p = a[p].lc;

tag[top] = 0; //表示右孩子没有被访问

buf[top] = ’0’; //左孩子标记’0’

}

if (flag) //如果p指向的是新叶子

{

// for (int i=0; i<=top; i++) // cout << buf[i]; // cout << endl; Btree s = new struct cNode; s->data = a[p].data; for (int i=0; i<=top; i++) s->str += buf[i]; s->lc = s->rc = NULL; if (!(InsertBtNode(t, s))) //插入一个结点s delete s; } if (top >= 0) //所有左孩子处理完毕后 { if (tag[top] == 0) //如果右孩子没有被访问 { flag = true; //此时p指向的是新叶子（未输出过的叶子） p = stack[top]; //读取栈顶元素，但不退栈 ，因为要先输出其右孩子结点 p = a[p].rc; tag[top] = 1; //表示右孩子被访问，下次直接退栈 buf[top] = ’1’; //右孩子标记’1’ } else //栈顶元素出栈 { flag = false; //此时p指向的是旧叶子（已输出过的叶子），不再输出 top--; } } } } //先序遍历赫夫曼树 void Preorder(HuffmanTree t, int p) { if (t == NULL) return; if (t[p].lc > 0) { cout << t[p].weight << endl; Preorder(t, t[p].lc); //遍历左子树 Preorder(t, t[p].rc); //遍历右子树 } else cout << t[p].weight << " " << t[p].data << endl; }

串

bool InsertBtNode(Btree & t, Btree s) { if (t == NULL) { t = s; return true; } else if (t->data > s->data) //把s所指结点插入到左子树中 return InsertBtNode(t->lc, s); else if (t->data < s->data) //把s所指结点插入到右子树中 return InsertBtNode(t->rc, s); else //若s->data等于b的根结点的数据域之值，则什么也不做 return false; } //中序遍历二叉排序树 void Inorder(Btree t) { if (t) { Inorder(t->lc); //遍历左子树 cout << t->data << " : " << t->str << endl; //输出该结点 Inorder(t->rc); //遍历右子树 } } //查找值为data的结点的递归算法 Btree Search(Btree p, ElemType data) { if (p == NULL || p->data == data) //空树或找到结点 return p; if (p->data > data) return Search(p->lc, data); //在左孩子中寻找 else return Search(p->rc, data); //在右孩子中寻找 } //利用记录了叶子结点编码的排序二叉树，对sourceCode进行编码，返回编码后的字符string Coding(string s, Btree t) { Btree p = NULL; string dest; for (int i=0; i<s.size(); i++) { p = Search(t, s[i]);

{ dest += p->str; //dest += ’ ’; } } return dest; } //利用赫夫曼树对destCode进行解码 string Decode(string s, HuffmanTree hT) { string dest; int p = 1; int i = 0; while (i < s.size()) { while (hT[p].lc > 0)//非叶子结点 { if (s[i++] == ’0’) p = hT[p].lc; //向左结点前进 else p = hT[p].rc; //向右结点前进 } dest += hT[p].data; //存储叶子结点 p = 1; } return dest; } //销毁一棵二叉排序树 void DestroyBTree(Btree & t) { if (t != NULL) { DestroyBTree(t->lc); DestroyBTree(t->rc); delete t; t = NULL; } } //销毁一棵赫夫曼树 void DestroyHfmanTree(HuffmanTree & t, int n) { for (int i=n-1; i>=0; i--) {

} t = NULL; }

本文来源：https://www.bwwdw.com/article/gere.html