哈夫曼树实验报告心得体会（[急]求一个哈夫曼树的应用程序,要c的,最好有实验报告的!）

本文目录

• [急]求一个哈夫曼树的应用程序,要c的,最好有实验报告的!
• 1用递归实现二叉树的先序、中序、后序三种遍历2哈夫曼树问题
• 急求哈夫曼编码/译码器课程设计

[急]求一个哈夫曼树的应用程序,要c的,最好有实验报告的!

我编的一个哈夫曼树,你参考参考
#include 《stdio.h》
int m,z=0; /*code*/
int i=0,js; /*ecode*/
int e=53; /*ecode*/
typedef struct hf{
int l,r,p,w;}elem,*def;
/*----------初始化-set------------*/
set(def h){
int w={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
int i,j;
h=(def)malloc(55*sizeof(elem));
for(i=0;i《27;i++){
h;
h.p=0;}
for(i=27;i《54;i++){
h.w=0;}
return h;
}
/*-------------创建哈夫曼树-create-----------*/
create(def h){
FILE *fp;
int w1,w2;
int i1,i2;
int k=27,i,j;
fp=fopen("hafmtree.txt","w+");
w1=w2=2000;
i1=i2=0;
while(k《=52){
for(i=0;i《=k;i++){
if(h.p==0){
if(h.w《=w1){
w2=w1;w1=h.w;
i2=i1;i1=i;
}
else{
if(h.w《=w2)
{w2=h.w;i2=i;}
}
}
}
h.w=w1+w2;
h.p=k+1;
h.l=i1;
h.r=i2;
k++;
w2=w1=2000;
}
h.p=0;
for(j=1;j《54;j++){
fprintf(fp,"jiedian (%d): l--%d,r--%d,p--%d,w--%d\n",j,h.w);}
}
/*----------------编码-code-----------------*/
code(int n,def h){
int q=h.p; /*找父节点*/
if(n==h.l) /*判断左右孩子*/
m=1;
else
m=0;
z++;
if(q!=0) /*是否为根节点*/
{n=q;
code(n,h);
}
}
/*-----------------译码-ecode---------------*/
ecode(char ec,def h){
if(ec==’1’)
e=h.l;
else
if(ec==’0’&&ec!=’\n’)
e=h.r;
js=0;
return e;
}
/*------------------打印print-------------------*/
print(def h){
FILE *fp;
int a,n,i,j=256,x=0,y=256;
int s={0};
fp=fopen("treeprint.txt","w");
for(i=1;i《54;i++){
a=i;
while(h.p!=0){
if(a==h.l)
m=1;
else m=0;
a=h.p;
z++;
}
for(n=z-1;n》=0;n--){
j=j/2;
if(m==1)
y=y-j;
else
y=y+j;
x+=2;
}
/*if(s==0){*/
if(h.l==0)
s=i+95;
else
s=i;
z=0;
j=256;
x=0;y=256;
}
for(i=0;i《20;i++){
for(j=0;j《512;j++){
if(s!=0){
if(s》95)
fprintf(fp,"%c",s);
else fprintf(fp,"%d",s);
}
else fprintf(fp,"_");
}
fprintf(fp,"\n");
}
}
/*--------------main------------*/
main(){
/*+++++++++++++++定义各种变量++++++++++++++++++++++++*/
def h;
FILE *fp1,*fp2,*fp3,*fp,*fp5;
int n,j,k=0;
char ec;
char a;
/*++++++++++++++++读出tobetran中的字符++++++++++++++++++++++++*/
h=set(h); /*初始化*/
create(h); /*创建哈夫曼树*/
print(h);
fp3=fopen("tobetran.txt","r");
for(i=0;i《27;i++){
fscanf(fp3,"%c",&a);
}
/*===========将报文的编码写入codefile中去===================*/
fp1=fopen("codefile.txt","w+");
fp2=fopen("codefile.txt","r");
for(i=0;i《=26;i++){
if(a==’ ’) n=1;
else n=a-95;
code(n,h); /*编码*/
for(j=z-2;j》=0;j--){
fprintf(fp1,"%d",m);
}
fprintf(fp1,"\n");
z=0;
}
fclose(fp1);
/*==========将codefile中的编码翻译成字符，并写入textfile中===*/
j++;
fp=fopen("textfile.txt","w");
fp5=fopen("cprint.txt","w");
while(k==0){
fscanf(fp2,"%c",&ec);
e=ecode(ec,h);
if(h.l==0){
if(e!=1)
fprintf(fp,"%c",e+95);
else
fprintf(fp," ");
js=1;
}
if(js==1)
e=53;
/*-------每行50个写入cprint.txt--------*/
if(ec!=’\n’)
fprintf(fp5,"%c",ec);
j++;
if(j%50==0)
fprintf(fp5,"\n");
k=feof(fp2);
}
fclose(fp2);
fclose(fp);
}

1用递归实现二叉树的先序、中序、后序三种遍历2哈夫曼树问题

//在吗？ 我给你。另外我有自己的实验报告。
//里面有递归遍历，有迭代遍历。可以写文件，可以压缩编码。可以读文件。
//你不需要什么功能的话就删去相应的函数就行了。
//希望加分。
#include《iostream》
#include《fstream》
#include《iomanip》
#include《string》
using namespace std;
const int maxlen = 10000; //结点最大数目
const int maxlen2 = 260; //字符最大数目，叶节点最大数目
const int maxchar = 260; //字符最大数目
#define INTMAX 10000000; //大数，大于任意一个权值
struct CharSet //程序初始化时保存字符和结点的结构体。
{
char ch;
int weight;
};
struct HaffNode //哈夫曼树结点结构
{
int weight,parent,lchild,rchild;
char ch;
HaffNode() {weight=0; parent=lchild=rchild=-1; ch=’\n’;}
};
struct HaffCode //哈夫曼树字符编码信息结构
{
unsigned int bit; //通过位运算，用一个无符号整形来表示一串二进制编码。
int startb; //记录偏移量。
int weight;
char ch;
HaffCode() { bit=0; startb = -1; weight=0; ch=’\n’;}
HaffCode& operator=(HaffCode & obj) //重载赋值符号
{
bit=obj.bit; startb=obj.startb;
ch=obj.ch; weight=obj.weight;
return *this;
}
};
class HaffmanSystem
{
private:
CharSet cs; //保存初始化时的字符和权值信息。
HaffNode hn; //保存哈夫曼树结点信息。
HaffCode hc; //保存哈夫曼树字符编码信息。
HaffCode hc2; //索引散列。考虑到字符数少，以字符的十进制数作为下标保存和索引字符编码信息，时间为O(1);
int head; //根结点的数组下标。
int n;
int leafnum; //叶节点个数，字符个数。
public:
HaffmanSystem() {n=head=leafnum=0;}
void Haffman(); //哈夫曼树生成函数。
void InitisLization(); //初始化，调用Haffman();
void Encoding(); //对文件"ToBeTran"进行编码。
void Decoding(); //对文件"CodeFile"译码。
void Print(); //印代码至屏幕。
static void TreePrinting(int pos,int i,int child_flag,HaffmanSystem * p,ofstream & fop);
void TreePrinting(); //输出哈夫曼树图形到屏幕和文件，其中要调用静态实例函数完成递归功能。
void TreeFromFile(); //从文件中获取哈夫曼树。
};
void HaffmanSystem::InitisLization()
{
cout《《"字符集大小n,（去掉空格）："《《endl; //读入字符和权值信息。
cin》》n;
for(int i=0;i《n;i++)
{
cout《《"第"《《i+1《《"个字符和权值，用空格隔开：";
cin》》cs.weight;
}
cout《《"最后输入空格的权值(小于等于0表示空格不存在): "《《endl; //对空格特殊处理。
cin》》cs.weight;
cs.ch=’ ’;
if(cs.weight》0) n++;
this-》Haffman(); //调用哈夫曼树生成函数。
}
//哈夫曼树生成函数。
void HaffmanSystem::Haffman()
{
leafnum=n;
int i,j,m1,m2,k1,k2;
for(i=0;i《n;i++)
{
hn.weight;
hn.ch;
}
for(i=0;i《n-1;i++) //n-1个分支节点；
{
m1=m2=INTMAX; k1=k2=0;
for(j=0;j《n+i;j++)
{
if(m1》hn.parent==-1)
{
m2 = m1; k2 = k1;
m1 = hn.weight ; k1 = j;
}
else
if(m2》hn.parent==-1)
{
m2 = hn.weight; k2 = j;
}
}
hn.parent = n+i;
hn.weight;
hn.rchild = k2;
head = n+i;
}

int child,parent;
for(i=0;i《n;i++)
{
hc.weight;
child = i;
parent = hn.parent;
while(parent != -1)
{
if(hn.lchild == child)
{
++hc.startb;
}
else if(hn.rchild == child)
{
hc.startb);
}
child = parent;
parent = hn.parent;
}
hc2;
}
char choice=’N’;
cout《《"是否保存当前哈夫曼树进hfmTree.dat中？"《《endl;
cin》》choice;
if(choice==’y’||choice==’Y’) //把生成的哈弗曼树保存在文件hfmTree.dat中。
{
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);
if(!fop) {cout《《"打开文件错误，保存失败"《《endl; return ;}
fop.write((char*)&leafnum,sizeof(leafnum));
for(i=0;i《2*leafnum-1;i++)
{
fop.write((char*)&hn));
}
for(i=0;i《maxchar;i++)
{
fop.write((char*)&hc2));
}
fop.close();
cout《《"保存成功！"《《endl;
}
}
//编码函数。
void HaffmanSystem::Encoding()
{
if(leafnum==0) { TreeFromFile(); }
char ch;
int i,num=0,bitTemp, startTemp=-1, temp2=0;

ifstream fip2("ToBeTran.txt",ios::in);
if(!fip2){ cout《《"无法打开指定文件【ToBeTran.txt】！"《《endl; return ;}
while(fip2.get(ch)) { num++;}
fip2.close();

ofstream fop1("CodeFile.dat",ios::out|ios::trunc|ios::binary);
if(!fop1){ cout《《"无法打开指定文件【CodeFile.dat】！"《《endl; return ;}
ofstream fop2("CodePrin.txt",ios::out|ios::trunc);
if(!fop2){ cout《《"无法打开指定文件【CodePrin.txt】！"《《endl; return ;}
ifstream fip1("ToBeTran.txt",ios::in);
if(!fip1){ cout《《"无法打开指定文件【ToBeTran.txt】！"《《endl; return ;}
fop1.write((char*)& num,sizeof(num)); //先写入字符数量。
char bitBuf=0; //用一个字符空间来缓冲二进制数据，每凑满八位就写入编码文件。
cout《《"\n待编码文件【ToBeTran.txt】: ";
for(i=7;;i--)
{
if(i==-1)
{
//用一个字符空间bitBuf来缓冲二进制数据，每凑满八位就写入编码文件。
fop1.write((char*)& bitBuf,sizeof(bitBuf));
i=7; bitBuf=0;//初始字符，使之为二进制“00000000”;
}
if(startTemp《0)
{
if(num--《=0) break;
fip1.get(ch);
cout《《ch;
bitTemp = hc2.bit;
startTemp = hc2.startb;
}
//位运算，确定某位上是0还是1。
temp2 = (1 & bitTemp》》startTemp--);
if(temp2) fop2《《"1";
else fop2《《"0";
bitBuf = bitBuf | temp2《《i;
//还是位运算，把0或1与原字符相与得到新的编码信息。如00010000 | 1《《7 =10010000.
}
fop1.write((char*)& bitBuf,sizeof(bitBuf)); //把最后的一段写入文件。
fip1.close();
fop1.close(); //关闭文件流。
fop2.close();
cout《《"\n\n编码成功！"《《endl;
}
//译码函数。
void HaffmanSystem::Decoding()
{
if(leafnum==0) { TreeFromFile();}
ofstream fop("TextFile.txt",ios::out|ios::trunc);
if(!fop) {cout《《"无法打开指定文件"《《endl; return ;}
ifstream fip("CodeFile.dat",ios::in);
if(!fip) {cout《《"无法打开指定文件"《《endl; return ;}
char ch,bitBuf;
int num,bitTemp=-1, startTemp=-1;
int FLAG=0,parent=head;
fip.read((char*)& num,sizeof(num));
cout《《"译码结果： ";
for(int i=-1;num》0;i--)
{
if(i==-1)
{
fip.read((char*)& bitBuf,sizeof(bitBuf));
i=7;
}
//译码和编码一样，同样飘逸的位运算处理，可以节省时间和空间。
FLAG=(1《《i)&bitBuf
if(FLAG==0) //0向左
{
parent = hn.lchild;
}
else //1向右
{
parent = hn.rchild;
}
//自顶向下搜索，碰到叶节点就是所求结点字符。
if(hn.rchild==-1)
{
ch=hn.ch;
cout《《ch;
fop 《《ch;
parent = head;
num--;
}
}
cout《《endl;
fip.close();
fop.close();
cout《《"译码成功！"《《endl;
}
//打印编码函数。
void HaffmanSystem::Print()
{
ifstream fip("CodePrin.txt",ios::in);
if(!fip) {cout《《"无法打开指定文件"《《endl; return ;}
int j =0;
char ch;
cout《《"字符形式编码文件【CodePrin.txt】: ";
while(fip》》ch)
{
if(j%50==0) cout《《endl; //50个字符换行。
j++;
cout《《ch;
}
cout《《endl;
fip.close();
}
//输出哈夫曼树到屏幕和文件TreePrint.txt
void HaffmanSystem::TreePrinting()
{
if(leafnum==0) { TreeFromFile();}
ofstream fop("TreePtint.txt",ios::out|ios::trunc);
if(!fop) {cout《《"无法打开指定文件【TreePtint.txt】！"《《endl; return;}
cout《《"逆时针90度直观输出二叉树(括号里面是权值)：\n"《《endl;
fop 《《"逆时针90度直观输出二叉树(括号里面是权值)：\n"《《endl;
TreePrinting(head,1,2,this,fop); //fop传递一个文件流，用于在递归的各个层次对同一文件输出。
cout《《endl;
fop.close();
}
//输出函数，静态实现，方便递归调用。
void HaffmanSystem::TreePrinting(int pos,int i,int child_flag,HaffmanSystem * p,ofstream & fop)
{ //模仿课本输出二叉树。
if(pos》=0 && pos《=p-》head)
{
TreePrinting(p-》hn.rchild,i+1,1,p,fop);
for(int j=0; j《4*(i-1); j++) {cout《《" "; fop《《" ";}
if(child_flag==-1) {cout《《"\\"; fop《《"\\";}
else if(child_flag== 1) {cout《《"/"; fop《《"/";}
if(p-》hn.ch==’\n’) {cout《《"--NULL"《《endl; fop《《"--NULL"《《endl;}
else
{
cout《《"--"《《p-》hn.weight《《")"《《endl;
fop《《"--"《《p-》hn.weight《《")"《《endl;
}
TreePrinting(p-》hn.lchild,i+1,-1,p,fop);
}
}
void HaffmanSystem::TreeFromFile()
{
int i;
cout《《"哈夫曼树不在内存中，尝试从文件中读入哈夫曼树..."《《endl;
ifstream file;
file.open("hfmTree.dat",ios::in|ios::binary);
if(!file) {cout《《"无法打开指定文件【hfmTree.dat】！"《《endl; return ;}
if(file.eof()) {cout《《"哈夫曼树文件空，请初始化！"《《endl; return ;}
file.read((char*)&leafnum,sizeof(leafnum));
head=leafnum*2-2;
for(i=0;i《2*leafnum-1;i++)
{
file.read((char*)&hn));
}
for(i=0;i《=maxchar;i++)
{
file.read((char*)&hc2));
}
file.close();
}
//主函数.
int main()
{
HaffmanSystem * T = new HaffmanSystem();
char choice = ’Y’;
while(choice!=’0’)
{
cout《《"-------------------------------------------------------------------------------"《《endl;
cout《《std::left《《setw(12)《《" 1--初始化"《《setw(12)《《"2--编码 "《《setw(12)《《"3--译码 "《《setw(17)《《"4--印代码文件 "《《setw(15)《《"5--印哈夫曼树 "《《"0--退出"《《endl;
cout《《"-------------------------------------------------------------------------------"《《endl;
cout《《std::right《《setw(40)《《"操作： ";
cin》》choice;
switch(choice)
{
case ’0’: { cout《《"系统已经退出"《《endl; return 0;}
case ’1’: { T-》InitisLization(); break;}
case ’2’: { T-》Encoding(); break;}
case ’3’: { T-》Decoding(); break;}
case ’4’: { T-》Print(); break;}
case ’5’: { T-》TreePrinting(); break;}
default :break;
}
}
return 0;
}

急求哈夫曼编码/译码器课程设计

我给你个差不多的，你自己修改一下就可以用了
/************Huffman编码和译码****************/
#include《stdio.h》
#include《malloc.h》
#include《string.h》
#include《stdlib.h》
typedef struct
{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct
{
char ch;
char *chs;
}HuffmanCode;
typedef struct
{
char ch;
int weight;
}sw;
typedef struct
{
HuffmanTree HT;
HuffmanCode *HC;
}huf;
void select(HTNode * HT,int n,int *n1,int *n2)
{
int i=1; int n3;
while(HT.parent!=0)
i++;
*n1=i;
i++;
while(HT.parent!=0) i++;
*n2=i;
if(HT.weight)

for(i++;i《=n;i++)
{
if(HT.parent==0)
{ if(HT.weight)
*n1=i;
else if(HT.weight)
*n2=i;
}
}
}
huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)
{int m,i,s1,s2,start,c,f;
HuffmanTree p;
char *cd;
if(n《=1) return 0;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i《=n;i++,p++,w++)
for(;i《=m;i++,p++)
for(i=n+1;i《=m;i++)
{
select(HT,i-1,&s1,&s2);
HT.parent=i;
HT.rchild=s2;
HT.weight;
}
HC=(HuffmanCode *)malloc((n+1)*sizeof(char));
cd=(char *)malloc(n*sizeof(char));
cd=’\0’;
for(i=1;i《=n;i++)
{ start=n-1;
for(c=i,f=HT.parent)
if(HT=’0’;
else cd=’1’;
HC.ch;
HC.chs=(char*)malloc((n-start)*sizeof(char));
strcpy(HC);
printf("%c %-10s\n",HC.chs);
}
HUF-》HT=HT;
HUF-》HC=HC;
return HUF;
}
char * convert(char *chars,char *chars1,HuffmanCode *hc,int n)
{
char *p=chars; int i;
strcpy(chars1,"");

while(*p)
{
i=1; while(hc.ch!=*p&&i《=n) i++;
strcat(chars1,hc.chs); p++;
}
printf("the chars translate are:%s\n",chars1);
return chars1;
}
void transcode(HuffmanTree ht,char *chars2,char*chars3)
{
int i=1,p; char *q=chars2;char *r=chars3;

while(ht.parent!=0) i++;
p=i;

while(*q)
{
while(ht.lchild!=0 && *q)
{
if(*q==’0’)
p=ht.lchild;
else p=ht.rchild;
q++;
}
if(ht.lchild==0)
p=i;
}
*r=’\0’;
printf("the chars are:");
puts(chars3);

}
void input(int *n,sw *w)
{
int i;
printf("input the mount of char:");
scanf("%d",n);

for(i=1;i《=*n;i++,w++)
{printf("input the %dth char and weight:",i);
fflush(stdin);
scanf("%c%d",&w-》ch,&w-》weight);
}
}
void main(void)
{HTNode HT;
HuffmanCode HC,*hc;
HuffmanTree ht;
huf *HUF,huf2;
int n;
sw w;
char ch,inchar;
char *abc;
char *p=inchar;
input(&n,w);
HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);
printf("input chars to translate,ends of ’#’:");
fflush(stdin);//清除流,解决输入干扰
ch=getchar();
while(ch!=’#’)
{*p=ch;
p++;
ch=getchar();
}
*p=’\0’;
hc=HUF-》HC;
ht=HUF-》HT;
abc=convert(inchar,outchar,hc,n);
transcode(ht,abc,outchar);
}