数据结构第三次实验报告

数据结构实验报告实验三哈夫曼树实验班级：_计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编码译码成功！最后销毁有序二叉树和赫夫曼树。系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）typedefcharElemType;//定

typedefstructsNode

{

doubleweight;

ElemTypedata;

}*Source;

typedefstructhNode

{

doubleweight;

ElemTypedata;

intlc,rc;

}*HuffmanTree;

typedefstructcNode

{

ElemTypedata;

stringstr;

structcNode*lc,*rc;

}*Btree;

HuffmanTreeCreateHuffmanTree(constSourcew,intn);//创建一棵赫夫曼树

voidBuildHeap(HuffmanTreet,intn);//构造一个二叉堆；小顶堆

voidPercDown(HuffmanTreet,intpos,intn);//构造二叉堆的功能子函数

voidDeleteMin(HuffmanTreet,intlen);/*删除二叉堆的根，并通过上移使得新得到的序列仍为二叉堆*/

voidInsertHfNode(HuffmanTreet,intlen,structhNodex);/*把x插入到原长度为len的二叉堆*/

voidPreorder(HuffmanTreet,intp);//先序遍历赫夫曼树

voidPostorder(Btree&t,HuffmanTreea,intn);/*后序遍历赫夫曼树，并记录叶子结点编码*/

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

voidInorder(Btreet);//中序遍历二叉排序树

BtreeSearch(Btreep,ElemTypedata);//查找值为data的结点的递归算法

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

stringDecode(strings,HuffmanTreehT);//利用赫夫曼树对destCode进行解码

voidDestroyBTree(Btree&t);//销毁一棵二叉排序树

voidDestroyHfmanTree(HuffmanTree&t,intn);//销毁一棵赫夫曼树主函数：intmain()

{

stringsourceCode;

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

intn=sourceCode.size();

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

Sourcew=newstructsNode[MAX];

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

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

w[MAX-1].weight=0;

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

{

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

w[i].weight=0;

}

//读取各个字母的权重

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

{

if(sourceCode[i]==’’)

w[26].weight++;

else

w[sourceCode[i]-’A’].weight++;

}

//获取出现了的大写字母和空格

n=0;

for(inti=0;i<MAX;i++)

{

if(w[i].weight>0)

w[n++]=w[i];

}

////直接输入原码和权重

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

//{

//cin>>w[i].weight>>w[i].data;

//}

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

{

cout<<w[i].weight<<""<<w[i].data<<endl;

}

HuffmanTreehT=CreateHuffmanTree(w,n);//构造赫夫曼树

//for(inti=1;i<2*n;i++)

//cout<<hT[i].weight<<"";

//cout<<endl;

//先序遍历赫夫曼树，并输出结点权重和叶子结点的data

Preorder(hT,1);

cout<<endl;

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

BtreebT=NULL;

Postorder(bT,hT,n);

//中序遍历记录了叶子结点编码的排序二叉树

Inorder(bT);

//利用记录了叶子结点编码的排序二叉树，对sourceCode进行编码

stringdestCode=Coding(sourceCode,bT);

cout<<destCode<<endl;

//利用赫夫曼树对destCode进行解码

stringobjCode=Decode(destCode,hT);

cout<<objCode<<endl;

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

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

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

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

system("pause");

return0;

}调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）构造哈夫曼非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。不过因为自己技术还不娴熟所以遇到了很多麻烦，而且也参考了别人的资源，下图输出方式安分布方式给出了哈夫曼树狗仔的过程！测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）基本操作的实现：（对各基本操作实现的描述）(后面可加页)//创建一棵赫夫曼树

HuffmanTreeCreateHuffmanTree(constSourcew,intn)

{

HuffmanTreehT=newstructhNode[2*n];//第一个结点不用

for(inti=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);//构造一个二叉堆；小顶堆

structhNodeadd;

intleft=n;

intright=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(inti=1;i<=right;i++)

//cout<<hT[i].weight<<"";

//cout<<endl;

//system("pause");

}

returnhT;

}

//构造一个二叉堆；小顶堆

voidBuildHeap(HuffmanTreet,intlen)

{

for(inti=len/2+len%2;i>0;i--)

{

PercDown(t,i,len);

}

}

//构造二叉堆的功能子函数

voidPercDown(HuffmanTreet,intpos,intlen)

{

intchild;

structhNodemin=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;

}

//删除二叉堆的根，并通过上移使得新得到的序列仍为二叉堆

voidDeleteMin(HuffmanTreet,intlen)

{

structhNodelast=t[len--];//二叉堆的最后一个元素

intchild,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的二叉堆

voidInsertHfNode(HuffmanTreet,intlen,structhNodex)

{

inti;

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

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

t[i]=x;

}

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

voidPostorder(Btree&t,HuffmanTreea,intn)

{

int*stack=newint[n];

int*tag=newint[n];

char*buf=newchar[n];

boolflag=true;

inttop=-1;

intp=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指向的是新叶子

{

//cout<<a[p].data<<":";//输出叶子结点

//for(inti=0;i<=top;i++)

//cout<<buf[i];

//cout<<endl;

Btrees=newstructcNode;

s->data=a[p].data;

for(inti=0;i<=top;i++)

s->str+=buf[i];

s->lc=s->rc=NULL;

if(!(InsertBtNode(t,s)))//插入一个结点s

deletes;

}

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--;

}

}

}

}

//先序遍历赫夫曼树

voidPreorder(HuffmanTreet,intp)

{

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;

}

//向一个二叉排序树t中插入一个结点s

boolInsertBtNode(Btree&t,Btrees)

{

if(t==NULL)

{

t=s;

returntrue;

}

elseif(t->data>s->data)//把s所指结点插入到左子树中

returnInsertBtNode(t->lc,s);

elseif(t->data<s->data)//把s所指结点插入到右子树中

returnInsertBtNode(t->rc,s);

else//若s->data等于b的根结点的数据域之值，则什么也不做

returnfalse;

}

//中序遍历二叉排序树

voidInorder(Btreet)

{

i