haffuman.cpp

自己写的一个8皇后程序,能给出所有的可行解

//代码部份
#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct{
	int weight;
	int parent,lchild,rchild;
}HTNode, *HuffmanTree;
struct word
{
	char chara;
	int num;
}characters[100];
typedef char * *HuffmanCode;
char *codebuf; 
HuffmanTree HT; HuffmanCode HC;
 

//****************
void select(HuffmanTree HT,int n, int &s1,int &s2)
{HuffmanTree p;int temp=10000; int i; p=HT;p++;
 for(i=1;i<=n;i++,p++){
	 if(!p->parent){
		 if(p->weight<temp){
			 temp=p->weight;s1=i;
		 }
	 }
 }
 temp=10000;p=HT;p++;
 for(i=1;i<=n;i++,p++){
	if(!p->parent){
		if(i!=s1){
			if(p->weight<temp){temp=p->weight;s2=i;}
		}
	}
	}if(s1>s2){temp=s1;s1=s2;s2=temp;}
}
//********huffman编码函数*****************
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{int m;int i,start,c,f; char *cd;int s1,s2;
 if(n<=1)return;
 m=2*n-1;
 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));HuffmanTree p=HT;p++;
 for(i=1;i<=n;i++,p++,w++){p->weight=*w;p->parent=p->lchild=p->rchild=0;}
 for(;i<=m;i++,p++)p->weight=p->parent=p->lchild=p->rchild=0;
 for(i=n+1;i<=m;i++){
	 select(HT,i-1,s1,s2);
	 HT[s1].parent=i;HT[s2].parent=i;
	 HT[i].lchild=s1;HT[i].rchild=s2;
	 HT[i].weight=HT[s1].weight+HT[s2].weight;
 }
 HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
 cd=(char *)malloc(n*sizeof(char));
 cd[n-1]='\0';
 for(i=1;i<=n;i++){
	 start=n-1;
	 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
		 if(HT[f].lchild==c)cd[--start]='0';
		 else cd[--start]='1';}
	 HC[i]=(char *)malloc((n-start)*sizeof(char));
	 strcpy(HC[i],&cd[start]);
 }
 free(cd);
}
//***************节点编码打印函数********************
 void printHuffman(HuffmanTree HT,HuffmanCode HC,struct word *w,int n)
{
	int i;
	for(i=1;i<=n;i++)
	{	printf("结点: ");
printf("%c",w[i-1].chara);
printf("		编码:");
printf("%s",HC[i]);
printf(" \n");
}
}

//************字符串输入函数*******************
 void inpute(int n)
 {char *newbase;
   int i=0;int k;int length=0;
   char ch;
   codebuf=(char *)malloc(500*sizeof(char));
   scanf("%c",&ch);
   while(ch!='#'){
	   for(i=0;i<n;i++){    
		   if(characters[i].chara==ch)break;
	   }
	   for(k=0;k<strlen(HC[i+1]);k++){
		   if(length>=500){
			   newbase=(char *)realloc(codebuf,(length+40)*sizeof(char));}
		   codebuf[length++]=HC[i+1][k];
	   }
	   scanf("%c",&ch);
   }
   codebuf[length]='\0';
   printf("译码后的信息:\n");
   printf("%s",codebuf);
 }


//************译码函数*******************
void Huffman_uncoding(HuffmanTree HT,HuffmanCode HC,int n)
{int f,c;char *p;char code;
 
 p=codebuf;
 while(*p!='\0'){
	 f=2*n-1;
	 while(HT[f].lchild){
		 code=*p++;
	     if(code=='1'){c=HT[f].rchild;f=HT[f].rchild;}
	     else{c=HT[f].lchild;f=HT[f].lchild;}
	 }printf("%c",characters[f-1].chara);
 }
 printf("\n");

}


//***********主函数****************
void main(void)
{FILE *fp;
int i,j,n,temp,diff=0;
int number=0; 
int flag=0;
char ch; char filename[20];
printf("\n请输入要编码的文件\n");
printf("1.对已有文件编码选择1。\n");
printf("2.新建文件选择2\n");
printf("3.对已有文件修改选择3\n");
printf("请选择(1,2,3)");
int change;
scanf("%d",&change);                                    // 对三种情况的文件输入
switch(change){
   case 1:printf("请输入文件名称\n");                    //第一种：文件已经存在
	   scanf("%s",filename);
	   break;
   case 2:printf("请输入文件名称\n");                     //第二种：新建文件
	   scanf("%s",filename);
	   fp=fopen(filename,"w");
	   if(!fp){
		   printf("Cannot open file\n");
	   }
	   printf("请输入文件内容并以'#'结束\n");
	   ch=getchar();
	   while(ch!='#'){
		   fputc(ch,fp);
		   ch=getchar();
	   }
	   fclose(fp);
	   break;
   case 3:printf("请输入文件名称(文件必须存在)\n");       //第三种：增加文件内容
	   scanf("%s",filename);
	   if((fp=fopen(filename,"a"))==NULL){
		   printf("Cannot open file\n");
	   }
	   printf("请输入要增加的内容，以'#'结束\n");
	   ch=getchar();
	   while(ch!='#'){
		   fputc(ch,fp);
		   ch=getchar();
	   }
	   fclose(fp);
	   break;
   default:break;
}
char all[1000];                                        //统计字符在文件出现的频率，即权值
char copy[1000];
char tend; 
int *w;         
fp=fopen(filename,"r");
if(!fp)
{printf("couldn't open the file");
}
ch=fgetc(fp);
while(ch!=EOF)
{  all[number]=ch;
   number++;
   ch=fgetc(fp);
}
fclose(fp);
for(i=0;i<100;i++)
characters[i].num=0;
int k=0;
for(i=0;i<=number;i++)
{   flag=0;
    temp=i;
	tend=all[i];
	for(j=0;j<temp;j++)
	{
		if(tend==all[j])
		{ flag=1;
		break;}
	}
     if(flag==1)
		 continue;
	   copy[k++]=tend;
	   }
diff=k-2;
for(n=0;n<=diff;n++)
characters[n].chara=copy[n];
for(i=0;i<=diff;i++)
{
	tend=characters[i].chara;
	temp=i;
	for(j=0;j<=number;j++)
		if(tend==all[j])
			characters[i].num++;
}

w=(int *)malloc((k-1)*sizeof(int));
for(i=0;i<(k-1);i++)
  w[i]=characters[i].num;

 HuffmanCoding(HT,HC,w,k-1);

 printf("\n各字符串编码如下：\n");

 printHuffman(HT,HC,characters,k-1);

 printf("\n...下面为译码程序....\n");

 printf("请输入要编码的字符串以'#'结束\n");
 inpute(k-2);

 printf("\n对信息译码后输出如下：\n");
 Huffman_uncoding(HT,HC,k-1);

 printf("\n 统计，编码，译码完成...\n");

}