编码器源程序.txt

很不错的信息论与编码课程设计论文

//编码程序
//运行正常！
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#include "iostream.h"

////////////////////////////////
typedef struct //存放权值字母的结构体
{
char c;
int weight;
}cell,*good; 
///////////////////////////////
////////////////////////////////
typedef struct   //哈夫曼树结构体
{
 int  weight;
 int  parent,lchild,rchild;

} HTNode ,*HuffmanTree;
////////////////////////////////////

typedef char ** HuffmanCode;//存放哈夫曼编码的二级指针

/////////////////////////////////// 
 int minimum(HuffmanTree tree,int i)
 {   // 返回权值最小的树的根结点
   int j,tag;
   int k=10000; 
   for(j=1;j<=i;j++)
     if(tree[j].weight<k&&tree[j].parent==0) 
       k=tree[j].weight,tag=j;
   tree[tag].parent=1; //根结点的双亲赋1
   return tag;
 }
////////////////////////////////////////////////////////////////////
 ///////////////////////////////////////////////////////////////////
 void find(HuffmanTree t,int i,int *s1,int *s2)
 { // 在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个
   int j;
   *s1=minimum(t,i);
   *s2=minimum(t,i);
   if(*s1>*s2)
   {
     j=*s1;
     *s1=*s2;
     *s2=j;
   }
 }
//////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *&w,int n)//求字符的赫夫曼编码HC
{                        // w存放n个字符的权值(均>0)，HT为构造的赫夫曼树
   HuffmanTree hfm;
   char *cd;
   int m=2*n-1;
   *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
   int i;
   /////////////////////////////////////////初始化
   for(hfm=*HT+1,i=1;i<=n;++i,++hfm,++w)
   {
     (*hfm).weight=*w;
     (*hfm).parent=0;
     (*hfm).lchild=0;
     (*hfm).rchild=0;
   }
   for(;i<=m;++i,++hfm)
     (*hfm).parent=0;
   //////////////////////////////////////////

   *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//堆首暂不使用
   int s1,s2;
   for(i=n+1;i<=m;++i) //建哈夫曼树
   { 
     find(*HT,i-1,&s1,&s2);
     (*HT)[s1].parent=(*HT)[s2].parent=i;
     (*HT)[i].lchild=s1;
     (*HT)[i].rchild=s2;
     (*HT)[i].weight=(*HT)[s2].weight+(*HT)[s1].weight;
   }
    
  //////////////////////////////////////////////////根反向求字符的赫夫曼编码
   int x,start;
   int k;
   cd=(char*)malloc(n*sizeof(char));
   cd[n-1]='\0';//串尾结束符号
   for(i=1;i<=n;i++)
   {    //求每个字符的赫夫曼编码
     start=n-1;  //存放编码终止的位置 
     for(x=i,k=(*HT)[i].parent;k!=0;x=k,k=(*HT)[k].parent)
       if((*HT)[k].lchild==x)
         cd[--start]='0';
       else
         cd[--start]='1';
     (*HC)[i]=(char*)malloc((n-start)*sizeof(char));//分配堆空间
     strcpy((*HC)[i],&cd[start]); 
   }
      free(cd); //释放堆空间
 }
 
//查找m中是否出现过字符a,有则返回它的下标，没有则返回-1
     int search(char a,char *m,int z)
	 {  
		int j=0;
	  while(j<z-1)
	  {
	  if(m[j]==a)
	  return j;  //有就返回它在m或者w中的下标（w,m中一样） 
	  j++;
	  }
	  return -1;//没有就返回-1
	 }
//////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////
 /*生成将要发送的二进制字符串：
  包括字符种类数，字符的ASCII码,字符的哈夫曼代码，间隔标记符，哈夫曼编码串*/
 
	 void code(char *p,int *&w,char *&m,int &n)//进行编码 
  { 
     ///////////////////////////////////////////////////////////以下代码求权值
	  
	  m=(char *)malloc(sizeof(char)); //生成堆空间存放出现的字母
      w=(int *)malloc(sizeof(int));  //存放字母对应的权值，其下标与上面m下标对应
	  int i=0,k,z=1;
	  while(*(p+i)!='\0')
	{
      if(z==1)//k==-1 用于后面if语句的条件判断，表示没有出现
		  k=-1;
	  else
	 k=search(*(p+i),m,z);//查找，若出现字符m则返回其下标，否则返回-1（表示没有）
	 if(k==-1)//如果没有就加入该字符
	 { z++;
	  m=(char *)realloc(m,z*sizeof(char));
	  w=(int *)realloc(w,z*sizeof(int));   //w存放对应字符的权值
	  m[z-2]=*(p+i);
	  m[z-1]='\0';//最后一个赋'\0'
	  w[z-2]=1;//对应权值赋1
	 }
	 else  //有就在权值上加1
      w[k]++;
    i++;
	}
	 n=z-2;//共n+1个字符（不包括\0）,序号0—n，第 n+1为\0
	
	  cout<<"字符"<<"   "<<"权值"<<endl;
	 for(int l=0;l<n+1;l++)
     cout<<m[l]<<"         "<<w[l]<<endl;
   
//////////////////////////////////////////////////////////构建哈夫曼树
    HuffmanTree HT;  
    HuffmanCode HC;
	
	HuffmanCoding(&HT,&HC,w,n+1);//调用哈夫曼编码的函数
	int zz,length,totle;//下标
    char *t;//后面用来存放核心字符串编码
    i=1;  
    totle=strlen(HC[1])+1;
	t=(char *)malloc(totle*sizeof(char));
	t[0]='\0';
    strcpy(t,HC[1]);
    while(*(p+i)!='\0')
	  {
	  zz=search(*(p+i),m,n+2);
	  length=strlen(HC[zz+1]);
	  totle+=length;
	  t=(char *)realloc(t,totle*sizeof(char));
	  strcat(t,HC[zz+1]);//将字符编码串连接到原来的后面
	  i++;
	  }
 
  
//////////////////////////////////////////////////////存放字符种类数
     char * ok=(char *)malloc(16*sizeof(char));
     ok[0]='\0';
     char *guodu=(char *)malloc(8*sizeof(char));//中间变量指针
	 guodu[0]='\0';//存放字母
	 itoa(n+1,ok,2);//字符种类个数存入,ok后面还有几个小空间未用！ 
     strcat(ok,"00000001");

////////////////////////////////////////////////存放字母的ASC码对应二进制字符串
	 int n1=16;//表示ok现在存放的字符串长度
	 for(i=0;i<n+1;i++)
	 {
		 itoa(m[i],guodu,2);//字母转化为二进制然后存入guodu中
         ok=(char *)realloc(ok,(n1+strlen(guodu)+8)*sizeof(char));//////////
		 n1+=strlen(guodu)+8;//////////
		 strcat(ok,guodu);//输入字母代码
         strcat(ok,"00000001");//字母之间用00000001隔开
	 }
	 free(guodu);//释放堆空间

/////////////////////////////////////////////////存放哈夫曼码
      for(i=0;i<n+1;i++)
	  {
	    ok=(char *)realloc(ok,(n1+strlen(HC[i+1])+8)*sizeof(char));/////////////
		n1+=strlen(HC[i+1])+8;
		strcat(ok,HC[i+1]);//输入单字符对应的编码（编码出错了）
		strcat(ok,"00000001");//要改进，用第一个编码来间隔，前面对应加入该码长度
	  }

/////////////////////////////////////////////////存放字符串哈夫曼编码
	  ok=(char *)realloc(ok,n1+strlen(t)*sizeof(char));
	  strcat(ok,t);//输入字符串编码
      
////////////////////////////////////////////////写入文件
	  FILE *fp;
	  if((fp=fopen("字符串的二进制编码.txt","wt+"))==NULL)
  {
  printf("error!");
  exit(-1);
  }
     fwrite(ok,strlen(ok)+1,1,fp);  
	 fclose(fp);
	 free(ok);//释放堆空间
  }
/////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////
  void main()
 {
   int *w,n;
   char *m;//存放出现字符的字符串
   char p[256];//存入输入的字符串(若为文件则可指向它)
   printf("请输入一串字符串:");
   gets(p);//输入要传输的字符串，字母的权值将在后面进行统计
   FILE *fp3; //新建文本文件，并对其操作
	  if((fp3=fopen("输入的（要进行传输的）字符串.txt","wt+"))==NULL)
  {
  printf("error!");
  exit(-1);
  }
   fwrite(p,sizeof(char),strlen(p)+1,fp3); 
   fclose(fp3);
   system("输入的（要进行传输的）字符串.txt");//打开该文本文件
   code(p,w,m,n);//编码函数
 }