数据结构实验六报告_数据结构实验报告6

数据结构实验六报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告6”。

实验六报告

课程名称： 数据结构 实验名称：二叉树的应用

实验日期

2011/11/23

一、实验目的：

掌握赫夫曼二叉树的建立及赫夫曼编码的生成。

二、实验内容与要求：

根据给定的n个权值生成赫夫曼二叉树，输出赫夫曼编码。

三、数据结构设计

顺序表的存储结构，建立了二叉树的关系

Struct HTNode{

int weight;

unsigned int parent,lchild,rchild;};

四、算法设计

1、从数据中选择较小的两个数据元素

void Select(HTNode *HT, const int n, int &a, int &b){ //选择较小的两个元素

} int x,y;

x=y=0x7fff;for(int j=0;j

if(HT[j].parent==0)

if(HT[j].weight

2、建立赫夫曼树

void CreatHuff(HTNode *HT,int *p,const int n){

} int m=2*n-1;int i,a,b;for(i=0;i

Select(HT ,i,a,b);HT[a].parent=HT[b].parent=i;HT[i].weight=HT[a].weight+HT[b].weight;HT[i].lchild=a;HT[i].rchild=b;}

3、生成赫夫曼编码

void HuffCoding(HTNode *HT, Huffcode &HC, const int n){

//

}HC=new

char*[n+1];

char *code=new char[n];code[n-1]='';int i,j,p,k;for(i=0;i

} delete[] code;j=n-1;k=i;while(HT[k].parent){

p=HT[k].parent;if(HT[p].lchild==k)code[--j]='0';else code[--j]='1';k=p;} HC[i]=(char*)malloc((n-j)*sizeof(char));HC[i]=new char[n-j];strcpy(HC[i],&code[j]);

五、测试结果

测试数据一：

测试数据二：

六、心得体会

这次实验是在前面的实验基础之上，加上只用了顺序表的存储结构，所以比较简单。尽管实验内容少，但还是学到一些知识。首先学会了赫夫曼编码的简单实现，认识到其应用的实际价值。然后，学会了用指针数组，前面几次试验有过尝试，但没写成。这次实验最初也是用C++写的，但错误“无法解析的外部符号“public: void __thiscall HuffmanTree::HuffCoding(struct HTNode *,char * * &,int)”(?HuffCoding@HuffmanTree@@QAEXPAUHTNode@@AAPAPADH@Z)，该符号在函数_main 中被引用”改不过来，所以迫于无奈，只得稍微改成像C的代码。