- 浏览: 32684 次
最新评论
#include<iostream>
#define MAX 1001
#define INF 999999
struct stuNode
{
int nLeftTree;
int nRightTree;
int nPd;
};
struct stuNo12
{
int No1;
int No2;
};
void vInput(int nArr[], int nN);
void vBuildTree(stuNode stuJD[],int nArr[],int nN);
stuNo12 getTwo(bool bUse[],int nArr[],int nN);
void vGetCode(stuNode str[],int nLength[],int nNode,int nDepth);
void vOut(int nArr[],int nLength[],int nN);
int main()
{
int nNum;
int nLe[2*MAX];
int nArrPD[2*MAX];
stuNode stuJD[2*MAX];
while(1==(scanf("%d",&nNum)))
{
vInput(nArrPD,nNum);
memset(stuJD,0,sizeof(stuJD));
vBuildTree(stuJD,nArrPD,nNum);
vGetCode(stuJD,nLe,2*nNum-1,0);
vOut(nArrPD,nLe,nNum);
}
return 0;
}
void vInput(int nArrPD[], int nN)
{
int i;
for(i=1;i<=nN;i++)
{
scanf("%d",&nArrPD[i]);
}
}
void vBuildTree(stuNode stuJD[],int nArr[],int nN)
{
int i;
int nCount;
bool bUse[2*MAX];
stuNo12 stuTwo;
for(i=1;i<=nN;i++)
{
bUse[i]=true;
bUse[i+nN]=false;
}
nCount=nN;
while(nCount<2*nN-1)
{
stuTwo=getTwo(bUse,nArr,nCount);
nCount++;
bUse[stuTwo.No1]=false;
bUse[stuTwo.No2]=false;
bUse[nCount]=true;
stuJD[nCount].nLeftTree=stuTwo.No1;
stuJD[nCount].nRightTree=stuTwo.No2;
nArr[nCount]=nArr[stuTwo.No1]+nArr[stuTwo.No2];
stuJD[nCount].nPd=nArr[nCount];
}
}
stuNo12 getTwo(bool bUse[],int nArr[],int nN)
{
int i;
int nTemp1;
int nTemp2;
stuNo12 stuRet;
nTemp1=INF;
nTemp2=INF;
stuRet.No1=1;
stuRet.No2=1;
for(i=1;i<=nN;i++)
{
if(bUse[i])
{
if(nTemp1>nArr[i])
{
nTemp2=nTemp1;
stuRet.No2=stuRet.No1;
nTemp1=nArr[i];
stuRet.No1=i;
}
else
{
if(nTemp2>nArr[i])
{
nTemp2=nArr[i];
stuRet.No2=i;
}
}
}
}
return stuRet;
}
void vGetCode(stuNode str[],int nLenth[],int nNode,int nDepth)
{
int nL,nR;
nL=str[nNode].nLeftTree;
if(nL!=0)
{
vGetCode(str,nLenth,nL,nDepth+1);
}
else
{
nLenth[nNode]=nDepth;
return;
}
nR=str[nNode].nRightTree;
if(nR!=0)
{
vGetCode(str,nLenth,nR,nDepth+1);
}
else
{
nLenth[nNode]=nDepth;
return;
}
}
void vOut(int nArr[],int nLength[],int nN)
{
int nAns;
int i;
nAns=0;
for(i=1;i<=nN;i++)
{
nAns+=nLength[i]*nArr[i];
}
printf("%d\n",nAns);
}
#define MAX 1001
#define INF 999999
struct stuNode
{
int nLeftTree;
int nRightTree;
int nPd;
};
struct stuNo12
{
int No1;
int No2;
};
void vInput(int nArr[], int nN);
void vBuildTree(stuNode stuJD[],int nArr[],int nN);
stuNo12 getTwo(bool bUse[],int nArr[],int nN);
void vGetCode(stuNode str[],int nLength[],int nNode,int nDepth);
void vOut(int nArr[],int nLength[],int nN);
int main()
{
int nNum;
int nLe[2*MAX];
int nArrPD[2*MAX];
stuNode stuJD[2*MAX];
while(1==(scanf("%d",&nNum)))
{
vInput(nArrPD,nNum);
memset(stuJD,0,sizeof(stuJD));
vBuildTree(stuJD,nArrPD,nNum);
vGetCode(stuJD,nLe,2*nNum-1,0);
vOut(nArrPD,nLe,nNum);
}
return 0;
}
void vInput(int nArrPD[], int nN)
{
int i;
for(i=1;i<=nN;i++)
{
scanf("%d",&nArrPD[i]);
}
}
void vBuildTree(stuNode stuJD[],int nArr[],int nN)
{
int i;
int nCount;
bool bUse[2*MAX];
stuNo12 stuTwo;
for(i=1;i<=nN;i++)
{
bUse[i]=true;
bUse[i+nN]=false;
}
nCount=nN;
while(nCount<2*nN-1)
{
stuTwo=getTwo(bUse,nArr,nCount);
nCount++;
bUse[stuTwo.No1]=false;
bUse[stuTwo.No2]=false;
bUse[nCount]=true;
stuJD[nCount].nLeftTree=stuTwo.No1;
stuJD[nCount].nRightTree=stuTwo.No2;
nArr[nCount]=nArr[stuTwo.No1]+nArr[stuTwo.No2];
stuJD[nCount].nPd=nArr[nCount];
}
}
stuNo12 getTwo(bool bUse[],int nArr[],int nN)
{
int i;
int nTemp1;
int nTemp2;
stuNo12 stuRet;
nTemp1=INF;
nTemp2=INF;
stuRet.No1=1;
stuRet.No2=1;
for(i=1;i<=nN;i++)
{
if(bUse[i])
{
if(nTemp1>nArr[i])
{
nTemp2=nTemp1;
stuRet.No2=stuRet.No1;
nTemp1=nArr[i];
stuRet.No1=i;
}
else
{
if(nTemp2>nArr[i])
{
nTemp2=nArr[i];
stuRet.No2=i;
}
}
}
}
return stuRet;
}
void vGetCode(stuNode str[],int nLenth[],int nNode,int nDepth)
{
int nL,nR;
nL=str[nNode].nLeftTree;
if(nL!=0)
{
vGetCode(str,nLenth,nL,nDepth+1);
}
else
{
nLenth[nNode]=nDepth;
return;
}
nR=str[nNode].nRightTree;
if(nR!=0)
{
vGetCode(str,nLenth,nR,nDepth+1);
}
else
{
nLenth[nNode]=nDepth;
return;
}
}
void vOut(int nArr[],int nLength[],int nN)
{
int nAns;
int i;
nAns=0;
for(i=1;i<=nN;i++)
{
nAns+=nLength[i]*nArr[i];
}
printf("%d\n",nAns);
}
发表评论
-
最大子段和
2012-01-05 13:59 779给出N个数字, 计算出最大的子段和。 Input 第一行给 ... -
最长不下降子序列长度
2012-01-05 13:55 1309对于序列(1, 7, 3, 5, 9, 4,,有它的一些不下降 ... -
求两字符串匹配的最长子序列
2012-01-05 13:52 1016如果两种特征序列的公共子序列越长表示越接近,现在请你帮助计算出 ... -
编辑距离问题
2012-01-05 13:48 658#include<iostream> #incl ... -
Kruskal最小生成树
2011-12-08 14:26 699#include<iostream> #inclu ... -
prime
2011-12-01 20:09 612#include<iostream> using ... -
哈弗曼编码
2011-11-28 10:43 1#include<iostream> #defi ... -
#贪心算法(零件加工)
2011-10-27 13:25 981#include<stdio.h> #includ ... -
众数问题
2011-10-20 14:57 789#include <stdio.h> #inclu ... -
输油管道问题
2011-10-13 14:45 599#include <stdio.h> #inclu ... -
幂的精确求值
2011-09-22 15:07 461#include<iostream> using ... -
大数加法
2011-09-22 12:56 606#include<iostream> #incl ... -
三姐妹之出题
2011-09-15 14:15 663#include<iostream> #incl ... -
最大子段和问题(分治)(##)
2011-09-08 21:31 665#include<stdio.h> #defin ... -
最大子段和问题(O(N^2))
2011-09-08 15:04 610#include<stdio.h> int a[ ... -
最大子段和问题(O(N^3))
2011-09-08 14:45 476#include<stdio.h> int a[ ...
相关推荐
哈弗曼编码与译码哈弗曼编码与译码哈弗曼编码与译码哈弗曼编码与译码哈弗曼编码与译码
哈弗曼编码译码 哈弗曼树的建立,编码 对26个大写英文字母以及空格键的编码,译码
哈弗曼编码哈弗曼编码哈弗曼编码哈弗曼编码哈弗曼编码
第一次输入:字母 及 权值 第二次输入部分字符串 输出 相应哈弗曼编码 第三次输入哈弗曼编码 输出 相应字符串 第四步 输入哈弗曼编码 输出相应字符
主要是哈弗曼编码的实现过程,就是建立哈弗曼编码的过程,只有源代码,但是源代码里面有解释。呵呵呵呵,希望对数据结构的学习者有帮助。
哈弗曼编码译码 c++实现 注释写得很详细
数据结构实习编的代码,构造哈弗曼树得到不同字符的哈弗曼编码,用编码一一代替原文件中的字符,得到压缩的效果
属于MFC在VC6.0下实现 哈弗曼编码 简单易懂……
采用静态的哈弗曼编码,可以实现对文件的压缩与解压,并且可以计算压缩、解压速度,压缩率等~
数据结构用c语言实现 哈弗曼编码与解码注意里面的输入形式否则会出错
将原文件进行哈弗曼编码后在利用哈弗曼编码进行压缩,建立哈弗曼树
哈弗曼编码代码及实验设计报告,专用与东华理工长江学院的 学子们,祝你们好运
哈弗曼编码code哈弗曼编码程序例子 哈弗曼编码code哈弗曼编码程序例子 哈弗曼编码code哈弗曼编码程序例子 哈弗曼编码code哈弗曼编码程序例子
哈弗曼编码
数据结构--哈弗曼编码实验报告 包含部分代码和程序运行后的截图
C++实现的哈弗曼问题解决,包括哈弗曼编码、译码等的代码实现
基于M进制哈弗曼编码解码程序 解码效率还不太理想
介绍压缩与解压缩编码的实例 运用了哈弗曼编码的相关知识
哈弗曼编码算法可用于压缩文件,这里实现了它,并生成了可执行文件!