#include<iostream>
using namespace std;
#define MAX 1001
#define INF 99999999
struct stuTreeNode
{
int nFr;
int nLeft;
int nRight;
};
struct stuNodeTow
{
int nA;
int nB;
};
void vInputNode(int nN,int nNode[],bool bVist[]);
void vBuildTree(int nN,int nNode[],bool bVist[],stuTreeNode stuTree[]);
stuNodeTow stuGetAB(int nC,int nNode[],bool bVist[]);
void vGetCode(int nHaCode[],stuTreeNode stuTree[],int nRoot,int nDepth);
void vOutputSum(int nN,int nNode[],int nHaCode[]);
int main()
{
int nNum;
int nFrNode[2*MAX];
int nCode[2*MAX];
bool bIsVist[2*MAX];
stuTreeNode stuTree[2*MAX];
while(1 == scanf("%d",&nNum))
{
vInputNode(nNum,nFrNode,bIsVist);
memset(stuTree,0,sizeof(stuTree));
vBuildTree(nNum,nFrNode,bIsVist,stuTree);
vGetCode(nCode,stuTree,2*nNum-1,0);
vOutputSum(nNum,nFrNode,nCode);
}
return 0;
}
void vInputNode(int nN,int nNode[],bool bVist[])
{
int i;
for(i=1;i<=nN;i++)
{
scanf("%d",&nNode[i]);
bVist[i] = true;
bVist[i+nN] = false;
}
}
void vBuildTree(int nN,int nNode[],bool bVist[],stuTreeNode stuTree[])
{
int nCount;
stuNodeTow stuNodeAB;
nCount = nN;
while(nCount < 2*nN-1)
{
stuNodeAB = stuGetAB(nCount,nNode,bVist);
nCount ++;//相加后节点值的下标
bVist[nCount] = true;//相加后节点值为新节点
bVist[stuNodeAB.nA] = false;//已访问
bVist[stuNodeAB.nB] = false;//已访问
stuTree[nCount].nLeft = stuNodeAB.nA //下标赋值给左子树
stuTree[nCount].nRight = stuNodeAB.nB;
nNode[nCount] = nNode[stuNodeAB.nA] + nNode[stuNodeAB.nB];//当前值最小两节点的和
stuTree[nCount].nFr = nNode[nCount];
}
}
//遍历所有没有用到过的节点,查找最小的两个节点,返回其下标
stuNodeTow stuGetAB(int nC,int nNode[],bool bVist[])
{
int i;
stuNodeTow stuAB;
int nTemp1,nTemp2;
nTemp1 = INF;
nTemp2 = INF;
stuAB.nA = 1;
stuAB.nB = 1;
for(i=1;i<=nC;i++)
{
if(bVist[i])
{
if(nNode[i] < nTemp1)
{
nTemp2 = nTemp1;
stuAB.nB = stuAB.nA;
nTemp1 = nNode[i];
stuAB.nA = i;
}
else
if(nNode[i] < nTemp2)
{
nTemp2 = nNode[i];
stuAB.nB = i;
}
}
}
return stuAB;
}
void vGetCode(int nHaCode[],stuTreeNode stuTree[],int nRoot,int nDepth)
{
int nL,nR;
nL = stuTree[nRoot].nLeft;
if(nL != 0)
{
vGetCode(nHaCode,stuTree,nL,nDepth+1);
}
else
{
nHaCode[nRoot] = nDepth;
return ;
}
nR = stuTree[nRoot].nRight;
if(nL != 0)
{
vGetCode(nHaCode,stuTree,nR,nDepth+1);
}
else
{
nHaCode[nRoot] = nDepth;
return ;
}
}
void vOutputSum(int nN,int nNode[],int nHaCode[])
{
int i;
int nAns;
nAns = 0;
for(i=1;i<=nN;i++)
{
nAns += nHaCode[i]*nNode[i];
}
printf("%d\n",&nAns);
}
分享到:
相关推荐
0023算法笔记——【贪心算法】哈夫曼编码问题--16页.pdf
它用C语言详细地介绍了哈弗曼编码的贪心算法的设计步骤及数据描述。
本程序是VS2010下的源程序,可直接运行。...本程序实现了通过读取文件中关于字符的相关说明数据来初始化相关变量,最后采用贪心算法的思想编程实现哈夫曼编码的求解。最终输出各个字符的哈弗曼编码值。
这是根据算法设计与分析的课程实验而编写的代码,完全可以使用,欢迎大家下载。
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...
贪心算法——哈夫曼编码课堂分享PPT
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。资源为哈夫曼编码可执行文件
Python编写的,利用贪心算法解决活动安排、哈夫曼编码、背包问题、最电路径、最优装载、最小生成树等问题
哈夫曼编码算法是通过使用字符在文件中出现的频率表来构造最优前缀码的贪心算法。所谓前缀码,即是任一字符的编码都不是其他字符编码的前缀。哈夫曼算法以自底向上的方式,将各字符(n个)存在叶节点中,通过n-1次...
c语言实现哈夫曼编码,并求平均码长 c语言实现哈夫曼编码,并求平均码长
1.哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率,求各个字符的哈夫曼编码方案。
介绍贪心算法的一般步骤: 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解,得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 二. 贪心算法适合解决...
全都是自己写的,都能跑出来 实打实写的哦~ 仅供参考 最重要的还是自己理解 1.实现哈夫曼编码的贪心算法。 2.学会分析哈夫曼编码的算法复杂性。 预览地址:
哈夫曼编码的C#实现 字母表:a,b,c,d,e,f 关键字序列:45,13,12,16,9,5 以上是测试数据
java算法分析与设计之哈夫曼编码源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,尤其...
哈夫曼编码实现文本文件的压缩,可作为数据压缩作业的参考
哈夫曼编码 贪心算法.docx哈夫曼编码 贪心算法.docx
哈夫曼编码 贪心算法.pdf哈夫曼编码 贪心算法.pdf
哈夫曼编码PPT课件.pptx
【贪心算法】哈夫曼编码.doc