哈夫曼编码数据结构c_数据结构哈夫曼树_数据结构哈夫曼树算法(2)

{

tree p=tr[i];

tr[i]=tr[c];

tr[c]=p;

}

if (tr[i].quanzhi

{

tree p=tr[i];

tr[i]=tr[c+1];

tr[c+1]=p;

}

}

//以下为通过最小值构造的新树

tr[youx].quanzhi=tr[c].quanzhi+tr[c+1].quanzhi;

tr[youx].you=&tr[c];//新树右孩子指向当前循环的最小值之一

tr[youx].zuo=&tr[c+1];//新树左孩子指向当前循环的最小值之一

youx++;//新树插入当前有效数据个数后面 并使有效数据个数+1

c=c+2;

}

}

void bianltree(tree *tr,char ch[])//哈夫曼编码

{

//通过遍历树，得到每个节点的编码

static int i=0;

if (!tr->min)//叶子节点

{

ch[i]='0';

i++;

bianltree(tr->zuo,ch);//左节点编码为'0'

ch[i]='1';

i++;

bianltree(tr->you,ch);//右节点编码为'1'

}

if (tr->min)

{

ch[i]='\0';//结束标记()

printf('%c %s \n',tr->date,ch);

hfm[hfmb].date=tr->date;

int j=0;

while(j!=i||i>10)

{

hfm[hfmb].bianm[j]=ch[j];

j++;

}//保存编码映射表

hfmb++;

}

i--;//递归走入右叶子节点时，取消当前赋值(当前必为左边叶子节点)

}

int _tmain(int argc, _TCHAR* argv[])

{

treetr[9]={{'a',true,5},{'b',true,2},{'c',true,9},{'d',true,3},{'e',true,6}};

// printf('%d \n',sizeof(tr)/sizeof(tree));

gettree(tr,9,5);

char ch[100];

//printf('%s\n',ch);

bianltree(&tr[8],ch);

return 0;

}

效果：

其中gettree()函数是构造哈夫曼过程，bianltree()是通过哈夫曼树编码过程，struct shfm

结构体是保存字符数据与它的哈夫曼编码的映射表，可用也可不用，这里之所以使用，是因为通过一次遍历就可得到所有元素的编码，以后要编码只需查表即可，以空间换时间。

下面介绍哈夫曼的应用举例：

通过上文的介绍，下面就介绍哈夫曼的实际运用。

本例的模拟效果是：通过传入一串字符串，返回该字符串的编码。并且通过传入一个有效的编码得到一个字符串！

下面给出完整代码，该代码基于上述代码之上进行修改，并优化上述代码。

// hfm.cpp : 定义控制台应用程序的入口点。

//

#include 'stdafx.h'

#include

////////////贵州民族大学///////////////

///////////编译环境vs2010//////////////

static int hfmb=0;

struct tree

{

char date;//数据

bool min;//叶子节点

int quanzhi;//权值

struct tree *zuo,*you;//左右孩子

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-27154-2.html