数据结构哈夫曼树实验报告

大家好，欢迎来到IT知识分享网。

1. 实验目的及要求

目的：熟练掌握二叉树应用（Huffman编码）的基本算法实现；进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力

要求：(1).假设文档内容从键盘输入；

(2).设计哈夫曼算法的存储结构；

(3).设计哈夫曼编码和解码算法；

(4).分析使劲按复杂度和空间复杂度。

1. 实验步骤

1.实验问题分析

程序是通过利用二叉树结构实现哈夫曼编码和译码，并且程序需具有以下要求：

（1）初始化：能够让用户输入字符和相应字符的频度来初始化，并建立哈夫曼树。

（2）建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码进行输出，打印哈夫曼编码表。

（3）译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

运用哈夫曼算法的相关知识解决问题。以用户输入的字符作为需要编码的字符集合，每个字符对应的频度则作为该字符的权值，构造一棵哈夫曼编码树，规定哈弗曼编码树的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径组成的0和1的序列为需要加密字符的编码。

2.数据的存储结构设计：

（1）采用静态的三叉链表存放。

算法思想：头指针数组存储哈夫曼编码串，字符型指针用来存放临时的编码串；从叶子节点开始向上倒退，若其为它双亲节点的左孩子则编码标0，否则标1；直到根节点为止，最后把临时存储编码复制到对应的指针数组所指向的内存中。重复，直到所有的叶子节点都被编码完。

1. 设计一个结构体Element保存哈夫曼树中各结点的信息；

1. 实验内容

  伪代码：

1.用户输入需要编译的字符和该字符的权值;

2.构造哈夫曼算法。设计一个数组H保存哈夫曼树中各结点的信息;

3.数组H初始化，将所有结点的孩子域和双亲域的值初始化为-1;

4.数组H的前n个元素的权值给定值;

5.调用select函数选择权值最小的根结点进行合并，其下标分别为i1，i2;

6.将二叉树i1，i2合并为一棵新的二叉树;

7.共进行n-1次合并，直到剩下一棵二叉树，这棵二叉树就是哈夫曼树;

时间复杂度：

1.Select函数，时间复杂度O(n);

2.Reverse函数，时间复杂度O(n);

3.HuffmanTree函数，构造哈夫曼树，时间复杂度O(n!);

4.CreateCodeTable函数，构造和输出哈夫曼编码表，时间复杂度O(n);

5.Decode函数，解码，时间复杂度O(n)。

代码的实现如下：

#include<iostream>

#include<string>

#include<iomanip>

using namespace std;

struct Element

{

  char ch;

  int weight;

  int lchild, rchild, parent;

};

struct HCode

{

  char  data;

  char  code[100];

};

int Select(Element H[], int i)       //选择两个最小的

{

  int min = 11000;

  int min1;

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

  {

     if (H[k].weight<min && H[k].parent == -1)

     {

        min = H[k].weight;

        min1 = k;

     }

  }

  H[min1].parent = 1;

  return min1;

}

void Reverse(char c[])    //将字符串倒置

{

  int n = 0;

  char temp;

  while (c[n + 1] != '\0')

  {

     n++;

  }

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

  {

     temp = c[i];

     c[i] = c[n - i];

     c[n - i] = temp;

  }

}

void HuffmanTree(Element H[], int w[], int n)     //构造哈夫曼树

{

  int i1 = 0, i2 = 0;

  for (int i = 0; i<2 * n - 1; i++)

  {

     H[i].lchild = -1;

     H[i].parent = -1;

     H[i].rchild = -1;

  }

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

  {

     H[l].weight = w[l];

  }

  for (int k = n; k<2 * n - 1; k++)

  {

     int i1 = Select(H, k);

     int i2 = Select(H, k);

     if (i1>i2)

     {

        int temp;

        temp = i1;

        i1 = i2;

        i2 = temp;

     }

     H[i1].parent = k;

     H[i2].parent = k;

     H[k].weight = H[i1].weight + H[i2].weight;

     H[k].lchild = i1;

     H[k].rchild = i2;

  }

}

void CreateCodeTable(Element H[], HCode HC[], int n)      //输出哈弗曼编码表

{

  HC = new HCode[n];

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

  {

     HC[i].data = H[i].ch;

     int ic = i;

     int ip = H[i].parent;

     int k = 0;

     while (ip != -1)

     {

        if (ic == H[ip].lchild)   //左孩子标'0'

           HC[i].code[k] = '0';

        else

          HC[i].code[k] = '1';  //右孩子标'1'

        k++;

        ic = ip;

        ip = H[ic].parent;

     }

     HC[i].code[k] = '\0';

     Reverse(HC[i].code);

  }

  cout << setiosflags(ios::left)

     << setw(5) << "n"

     << setw(12) << "weight"

     << setw(12) << "LChild"

     << setw(12) << "RChild"

     << setw(12) << "parent"

     << setw(12) << "char"

     << setw(12) << "code"

     << endl;

  for (int i = 0; i<2 * n - 1; i++)

  {

     if (i<n)

     {

        cout << setiosflags(ios::left)

          << setw(5) << i

          << setw(12) << H[i].weight

          << setw(12) << H[i].lchild

          << setw(12) << H[i].rchild

          << setw(12) << H[i].parent

          << setw(12) << HC[i].data

          << setw(12) << HC[i].code

          << endl;

     }

     else

        cout << setiosflags(ios::left)

        << setw(5) << i

        << setw(12) << H[i].weight

        << setw(12) << H[i].lchild

        << setw(12) << H[i].rchild

        << setw(12) << H[i].parent

        << setw(12) << "\\0"

        << setw(12) << "\\0"

        << endl;

  }

}

void Decode(Element H[], HCode HC[], int n, char *s)    //解码函数

{

  cout << "解码数据为：";

  int i = 2 * (n - 1);      //根结点

  while (*s != '\0')

  {

     if (*s == '0')

        i = H[i].lchild;

     else

        i = H[i].rchild;

     if (H[i].lchild == -1)

     {

        cout << H[i].ch;

        i = 2 * n - 2;

     }

     s++;

  }

  cout << endl;

}

int main()

{

  Element H[20];

  HCode HC[20];

  int n;

  int select;

  while (1)

  {


     cin >> select;

     if (select == 0)  break;

     switch (select) {

     case 1:

     {

        cout << endl;

        cout << "请输入字符集大小：";

        cin >> n;

        cout << endl;

        char s;

        HCode HC[20];

        int e[20];

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

        {

          cout << "请输入第" << t + 1 << "个字符：";

          cin >> s;

          H[t].ch = s;

          HC[t].data = H[t].ch;

          cout << "请输入该字符的权值：";

          cin >> e[t];

          cout << endl;

        }

        HuffmanTree(H, e, n);


        break;

     }

     case 2:

        CreateCodeTable(H, HC, n);


        break;

     case 3:

     {

        cout << endl;

        cout << "请输入解码数据：";

        char s[200] = { '\0' };

        cin >> s;

        Decode(H, HC, n, s);


        break;

     }

     default:

        cout << "没有此选项,请重新选择！" << endl;

     }

  }

}

4.实验结果

5. 实验总结分析

通过这次实验，我进一步增强了对于哈夫曼算法的理解。构建哈夫曼树的关键在于找最小树﹔在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。同时，通过查阅资料，分析问题，解决问题，锻炼了实际操作时的动手能力。