搜档网
当前位置:搜档网 › 数据结构课程设计报告00378

数据结构课程设计报告00378

数据结构课程设计

《数据结构》课程设计报告设计题目:哈夫曼编/译码器

2014年12 月30 日

摘要

哈夫曼编码是根据字符的使用率的高低对字符进行不等长的编码,从而使使用率高的字符占用较少的空间,从而在传输的过程中大大提高了数据的空间传输效率。本设计采用二叉链表的存储结构,建立哈夫曼树;用递归调用的方式对哈夫曼树的节点进行编码,生成与字符对应的哈夫曼编码。本设计完全采用C++语言进行编程,并在XCode 6编译器上调试运行通过。本程序使用中文界面,并有相应的提示信息,便于操作和程序运行。

关键词:哈夫曼树;哈夫曼编码;递归调用;二叉链表

Abstract

Huffman coding is based on the level of usage of characters ranging from long coding, so that high usage rate of the characters occupy less storage space , in the course of transmission has greatly enhanced the efficiency of data transmission space. This design build the Huffman tree by using Binary Tree storage structure, encoded Huffman tree nodes by recursive calling, and the characters generate the corresponding Huffman coding. The procedure completely write with C++ language and has Chinese explanatory note. What’s more, it was debugged in XCode 6 debugger and run well. The whole procedure, with Chinese interface and the corresponding tips ,is convenient to run and easy to be operated.

Keywords: Huffman Tree; Huffman code; Recursive call; Binary List

目录

摘要 (1)

ABSTRACT (2)

一、问题描述(内容格式参考下面的描述,以下类似) (4)

1、问题描述: (4)

2、基本要求: (4)

二、需求分析 (4)

2.1设计目标 (4)

2.2设计思想 (4)

三、概要设计 (5)

3.1程序结构 (5)

3.2初始化算法: (5)

3.3编码算法: (5)

3.4译码算法: (5)

四、数据结构设计 (5)

五、算法设计 (6)

1、算法分析(必须要用语言进行描述) (6)

2、算法实现 (7)

六、程序测试与实现 (12)

1、主程序 (12)

2、测试数据 (14)

3、测试结果 (15)

生成哈夫曼树运行结果图: (15)

哈夫曼编码运行结果图: (16)

编码函数运行结果图: (16)

译码函数运行结果图: (16)

平均编码长度函数运行结果图: (16)

七、调试分析 (17)

程序调试的步骤: (17)

调试体会: (17)

八、遇到的问题及解决办法 (17)

九、心得体会 (17)

一、问题描述(内容格式参考下面的描述,以下类似)

1、问题描述:

利用哈夫曼编码进行信息通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。试写一个哈夫曼编/译码系统。

2、基本要求:

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

(1)初始化。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件中。

(2)编码。利用已建好的哈夫曼树对文件中的正文进行编码,然后将结果存入文件中。

(3)译码。利用已建好的哈夫曼树将文件中的代码进行译码,结果存入文件中。

(4)完成数据测试,要求编码字符不低于15个,编码文件的长度不低于50个字符。

(5)计算平均编码长度。

二、需求分析

2.1 设计目标

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

1)初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件Tree.out中。输出哈夫曼树,及各字符对应的编码。

2)输入(Input)。从终端读入需要编码的字符串s,将字符串s存入文件Orinigal.txt中。

3)编码(Encode)与译码(Decode)。

编码(Encode)。利用已建好的哈夫曼树(如不在内存,则从文件Tree.out 中读入),对文件Orinigal.txt中的正文进行编码,然后将结果存入文件CodeOrinigal.txt中。

译码(Decode)。利用已建好的哈夫曼树将文件CodeOrinigal.txt中的代码进行译码,结果存入文件TextFile中。

输出编码文件(Print)。将编码显示在终端上。同时将此字符形式的编码写入文件Code.out中。

4)打印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件Tree.out中。

5)计算编码平均长度。计算编码平均长度,并显示在屏幕上。

2.2 设计思想

哈夫曼编码(Huffman Coding)是一种编码方式,以哈夫曼树─即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这种方法是由David.A.Huffman发展起来的。例如,在英文中,e的出现概率很高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e 极有可能用一个位(bit)来表示,而z则可能花去25个位(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位。二者相比,e使用了一般编码的1/8的长

度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。

三、概要设计

3.1程序结构

3.2 初始化算法:

程序从文件data.in中获取26个英文字母以及对应的权值。

3.3 编码算法:

(1)对输入的一段欲编码的字符串进行统计各个字符出现的次数,并它们转化为权值{w1,w2,……,wN}构成n棵二叉树的集合F={T1,T2,……,Tn}把它们保存到结构体数组HT[n]中,其中{Ti是按它们的ASCⅡ码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。

(2)在HT[1..i]中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。

(3)哈夫曼树已经建立后,从叶子到根逆向求每一个字符的哈夫曼编码。

3.4 译码算法:

译码的过程是分解电文中字符串,从根出发,按字符'0',或'1'确定找左孩子或右孩子,直至叶子结点,便求的该子串相应字符并输出接着下一个字符。

四、数据结构设计

1.元素类型,结点类型,指针类型

struct element //哈夫曼树结点

{

char data; //数据域

int weight; //权值

int lchild, rchild, parent; //左孩子右孩子,父结点

int flag;

};

struct Code //编码

{

int bit[MaxSize]; //编码

int start; //开始位置

int weight; //权值

};

struct Encode //编码

{

string code; //编码

char data; //编码对应的值

int flag;

};

int w[MaxSize]; //存放权值的数组

int n; //n个字符

int root; //根结点

Code HuffCode[MaxCode]; //哈夫曼编码数组

Encode encode[MaxSize]; //编码数组

element huffmanTree[MaxSize]; //哈夫曼树结点

2.包含的函数

Huffman();

~Huffman(){}

void HuffmanTree(); //建立哈夫曼树

void Initialization(); //初始化程序

void PrintHuffman(element H[], element HH, int n); //打印哈夫曼树

void HuffmanCode(); //生成哈夫曼编码

void PrintCode(); //打印哈夫曼编码

void FileCode(); //文件输出哈夫曼编码

void FileHuffman(element H[], element HH, int n); //文件输出哈夫曼树

int getRoot(){ return root; } //获取根结点

void Code_length(); //计算平均编码长度

void EnCode(); //为文件编码

void ReadCode(); //读取字符以及对应的哈夫曼编码

void Decode(); //为编码文件译码

五、算法设计

1、算法分析(必须要用语言进行描述)

哈夫曼树

给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树,

权值较大的结点离根较近。

哈夫曼树的构造

一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算法,一般还要求以Ti的权值Wi的升序排列。)

二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。

三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。

四、重复二和三两步,直到集合F中只有一棵二叉树为止。

哈夫曼编码

哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

哈夫曼编码步骤:

哈夫曼树已经建立后,从叶子到根逆向求每一个字符的哈夫曼编码。

哈夫曼编码平均编码长度:

哈夫曼编码平均编码长度=每个字符的权值和该字符对应的哈夫曼编码的长度的乘积的和/权值的总和。

2、算法实现

1.哈夫曼树的建立:

void Huffman::HuffmanTree() //建立哈夫曼树

{

int i1, i2, m1, m2;

for (int i = 0; i < 2 * n - 1; i++) //初始化哈夫曼树

{

if (i < n)huffmanTree[i].weight = w[i];

else

{

huffmanTree[i].weight = 0;

huffmanTree[i].data = '/';

}

huffmanTree[i].parent = -1;

huffmanTree[i].lchild = -1;

huffmanTree[i].rchild = -1;

huffmanTree[i].flag = 0;

}

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

{

m1 = m2 = MaxValue;

i1 = i2 = 0;

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

{

if (huffmanTree[j].weight < m1 && huffmanTree[j].flag == 0)//查找最小权值m1和标号为x1;m2和x2为此最小

{

m2 = m1;

i2 = i1;

m1 = huffmanTree[j].weight;

i1 = j;

}

else if (huffmanTree[j].weight < m2 && huffmanTree[j].flag == 0)

{

m2 = huffmanTree[j].weight;

i2 = j;

}

}

huffmanTree[i1].flag = 1;

huffmanTree[i2].flag = 1;

huffmanTree[n + i].weight = huffmanTree[i1].weight + huffmanTree[i2].weight;

huffmanTree[i1].parent = n + i;

huffmanTree[i2].parent = n + i;

huffmanTree[n + i].lchild = i1;

huffmanTree[n + i].rchild = i2;

}

}

2.哈夫曼编码

void Huffman::HuffmanCode() //哈夫曼编码函数

{

Code cd[MaxCode];

int i, j, child, parent;

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

{

cd->start = n - 1;

cd->weight = huffmanTree[i].weight;

child = i;

parent = huffmanTree[child].parent;

while (parent != -1) //从叶子出发到根逆序得出哈夫曼编码

{

if (huffmanTree[parent].lchild == child)

cd->bit[cd->start] = 0;

else

cd->bit[cd->start] = 1;

cd->start--;

child = parent;

parent = huffmanTree[child].parent;

}

for (j = cd->start + 1; j < n; j++)

HuffCode[i].bit[j] = cd->bit[j];

HuffCode[i].start = cd->start + 1;

HuffCode[i].weight = cd->weight;

}

root = child;

}

3.编码函数

void Huffman::EnCode() //编码函数

{

string en[100];

int pos = 0, j;

int flag = 0;

char Original[MaxChar];

memset(Original,0,MaxChar);

ifstream ifile; //从文件中读取出原文

ifile.open("Original.in");

while(!ifile.eof())

{

ifile >> Original[pos];

pos++;

}

ifile.close();

cout << "原文如下:" << Original << endl;

//s = new string[pos];

for(int i = 0; i < n; i++) //遍历得出文件中字符对应的哈夫曼编码{

for(j = 0; j < pos; j++)

{

if(Original[j] == encode[i].data)

{

en[j] = encode[i].code;

flag++;

}

}

if (flag == pos)

break;

}

ofstream ofile;

ofile.open("CodeOriginal.out"); //将编译以后的编码写入文件中cout<<"经过编译后的字符串:";

for(int j = 0; j < pos; j++)

{

ofile << en[j];

cout << en[j];

}

cout<

}

4.译码函数

void Huffman::Decode()

{

int pos = 0, p = 0, f = 0;

string t;

char enco[10000];

char tmp[50]={'\0'};

memset(tmp, 0, 50);

ifstream ifile;

ifile.open("CodeOriginal.out");

while(!ifile.eof())

{

ifile >> enco[p];

p++;

}

cout<<"译文如下:";

for(int i = pos; i < p; i++)

{

tmp[f] = enco[i];

t=tmp;

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

{

if(t == encode[j].code)

{

cout<

pos = i+1;

memset(tmp, 0, 50);

f=-1;

break;

}

}

f++;

}

cout<

}

5.求平均编码长度

void Huffman::Code_length()

{

double res;

double sumWeight = 0 ,Codelength = 0;

double num = 0;

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

{

sumWeight = sumWeight + w[i];

}

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

{

num = 0;

for(int j = HuffCode[i].start; j < n; j++)

{

num++;

}

Codelength = Codelength + num * w[i];

}

res = Codelength/sumWeight;

cout << res <

}

3、算法流程图

六、程序测试与实现

1、主程序

void menu()

{

cout<<"**************************************************************"<

}

int main()

{

menu();

Huffman H;

int choose;

for(;;)

{

cout<<"请选择要执行的功能: ";

cin>>choose;

switch(choose)

{

case 1:

{

H.Initialization();

H.HuffmanTree();

H.HuffmanCode();

cout<<"各字符编码如下:"<

H.PrintCode();

H.FileCode();

cout<<"哈夫曼树如下:"<

H.PrintHuffman(H.huffmanTree, H.huffmanTree[H.getRoot()], 0);

H.FileHuffman(H.huffmanTree, H.huffmanTree[H.getRoot()], 0);

cout<<"文件已保存为Tree.out!"<

break;

}

case 2:

{

H.ReadCode();

H.EnCode();

break;

}

case 3:

{

H.Decode();

break;

}

case 4:

{

cout<<"平均编码长度为:";

H.Code_length();

break;

}

default:

break;

}

if(choose == 5)

break;

}

}

2、测试数据

ch=A Weight=64

ch=B Weight=13

ch=C Weight=22

ch=D Weight=32

ch=E Weight=143

ch=F Weight=21

ch=G Weight=15

ch=H Weight=41

ch=I Weight=57

ch=J Weight=12

ch=K Weight=5

ch=L Weight=1

ch=M Weight=20

ch=N Weight=57

ch=O Weight=66

ch=P Weight=15

ch=Q Weight=1

ch=R Weight=48

ch=S Weight=51

ch=T Weight=80

ch=U Weight=23

ch=V Weight=8

ch=W Weight=18

ch=X Weight=120

ch=Y Weight=16

ch=Z Weight=1

3、测试结果

生成哈夫曼树运行结果图:

哈夫曼编码运行结果图:

编码函数运行结果图:

译码函数运行结果图:

平均编码长度函数运行结果图:

七、调试分析

程序调试的步骤:

1)对各个模块函数进行单元调试,并测试模块间参数的传递与调用。

2)调试主函数和对其他模块函数的调用,并检验最后的输出结果。

调试体会:

1)对Huffman编码有了一个很好的认识,通过对Huffman编码的实现,对Huffman 编码有了具体的认识和实践,对二叉树又有了一个更新的认识。对文件有了一定的认识,可以进行简单的文件流操作。

2)算法的时间复杂度分析:程序部分用双循环嵌套结构,所以时间复杂度为O(n2).

3)算法的空间复杂度分析:算法的空间复杂度为O(n)。

八、遇到的问题及解决办法

程序运用了C++语言以及数据结构的核心思想,由于程序本身比较复杂,在调试实现的过程中花了大量的时间,在解决如何编码的时候,我遇到了很大的问题,经过多次测试后仍然不能实现,因此我参考了别人的结构,构建了一个新的结构体用来传输权值,才解决了这个问题。函数的核心代码是参考教材的思路。

九、心得体会

这次课程设计不仅让我熟悉了哈夫曼编码以及哈夫曼树,同时也是对自身耐心的磨练,因为在书上只有伪代码,而课程设计的代码却要自己一步一步的写出来。刚开始遇到了许多的困难,在查阅了大量资料以后,将困难一一克服。

在此次设计中收获颇多。对于设计过程的每一个步骤、每一个算法、每一次调试都对自己是一次考验。在试验中学习,在设计中找乐趣,在算法中求精炼,在调试中找不足。每一次出错都是一次考验,每一次正确的答案又都是一次动力,每一次成功又都是一次鼓励。

相关主题