哈夫曼.txt

哈夫曼编码和译码,数据结构课程设计的作品

#include "string.h"
#include "malloc.h"
#include "ctype.h"
#include "limits.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "process.h"
#include "iostream.h"

#define  OK 1
#define  OVERFLOW -2
typedef  int  Status;
typedef  int  ElemType;
typedef struct
{
	ElemType *elem;
	int  length;
}Sqlist;

typedef struct
{
    unsigned int weight;
    unsigned int parent ,lchild,rchild;
}HTNode, *HuffmanTree;// 动态分配数组存储赫夫曼树

typedef char **HuffmanCode;//动态分配存储数组的赫夫曼编码表

ST(FILE *fp)
{
	int a=0;
	char ch;
	
	while((ch=fgetc(fp))!=EOF)
	{
	
		if(ch=32 || ch<=127)
			a++;
	}

	return a;
}

Status CreateFile(Sqlist &L,Sqlist &T)
{
	char ch;
	int n,m=0,j;
    static int i;
	FILE *fp;
	if((fp=fopen("D:\\zf.txt","r"))==NULL)
	{
		printf("不能打开文件\n");
		exit(0);
	}
	
    n=ST(fp);
    fclose(fp);
    L.elem=(ElemType*)malloc(n*sizeof(ElemType));
    T.elem=(ElemType*)malloc(n*sizeof(ElemType));
    if(!L.elem&&!T.elem)
		exit(OVERFLOW);
    L.length=n;
   	T.length=0;
    if((fp=fopen("D:\\zf.txt","r"))==NULL)
	{
		printf("不能打开文件\n");
		exit(0);
	}
   	while((ch=fgetc(fp))!=EOF)
	{
	
		if(ch=32 || ch<=127)
		{	
			L.elem[i]=ch;
		        i++;
		}
	}
	fclose(fp);
    for(i=0;i<L.length;i++)
      printf("%c",L.elem[i]);
    cout<<endl;
    for(i=0;i<L.length;i++)
	{
	  int m=1,flag=0,c;
	  c=L.elem[i];
  	  for(j=i+1;j<L.length;j++)
	  {
		if(c==L.elem[j] && c0)
		{
			L.elem[j]=0;
			m++;
			flag=1;
		}
		else;
	  }
	  if(flag)
		  T.elem[T.length++]=m;
          else if(c0)
                  T.elem[T.length++]=m;
          else;
	}
    for(i=0;i<T.length;i++)
	  printf("%d",T.elem[i]);
    cout<<endl;
	return OK;
}
					
int min(HuffmanTree t, int i)
{ 
    int j, flag;
    unsigned int k=INT_MAX;//取K为不小于的可能值
    for(j=1;j<=i;j++) 
      if(t[j].weight<k &&t[j].parent==0)//t[j]是素、树的根结点
        k=t[j].weight, flag=j;
    t[flag].parent=1; //给选中的根结点的双亲赋1，避免第二次查找该结点
    return flag;
}
void select( HuffmanTree t,int i ,int &a,int &b)
{ //在i个结点中选择两个权值最小的树的根结点，s1为其中序号小的那个
    int j;
    a=min(t,i);
    b=min(t,i);
    if(ab)
	{
      j=a;
      a=b;
      b=j;
	}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, Sqlist T)
{
    int m,n,i,a,b;
    unsigned c,cdlen;
    HuffmanTree p;
    char *cd;
    n=T.length;
    if(n<=1)
    return;
    m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用 
    for(p=HT+1,i=1;i<=n;++i,++p)
	{
      (*p).weight=T.elem[i-1];
      (*p).parent=0;
      (*p).lchild=0;
      (*p).rchild=0;
	}
    for(;i<=m;++i,++p)
      (*p).parent=0;
    for(i=n+1;i<=m;i++)//建立
	{//在HT[1--I-1]中选择parent为0的且weight最小的两个结点，其序号分别为s1,s2
      select(HT,i-1,a,b);
      HT[a].parent=i;
      HT[b].parent=i;
      HT[i].lchild=a;
      HT[i].rchild=b;
      HT[i].weight=HT[a].weight+HT[b].weight;
	}
     //以下为无栈非递归遍历
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
     //分配n个字符的头指针向量（[0]不用）
    cd=(char*)malloc(n*sizeof(char));//分配求编码的工作区间
    c=m;
    cdlen=0;
    for(i=1;i<=m;++i)
      HT[i].weight=0;//
    while(c)
	{
      if(HT[c].weight==0)
	  {//向左
        HT[c].weight=1;
		{
          if(HT[c].lchild!=0)
		  {
            c=HT[c].lchild;
            cd[cdlen++]='0';
		  }
          else if(HT[c].rchild==0)
		  {
            //登记叶子结点的字符编码
            HC[c]=(char *)malloc((cdlen+1)*sizeof(char));
            cd[cdlen]='\0';
            strcpy(HC[c],cd);//复制编码
		  }
		}
	  }
      else if(HT[c].weight==1)
	  {// 向右
        HT[c].weight=2;
        if(HT[c].rchild!=0)
		{
           c=HT[c].rchild;
           cd[cdlen++]='1';
		}
	   }
       else
	   {
        //HT[c].weight==2,退回
        HT[c].weight=0;
        c=HT[c].parent;
        --cdlen;//退到父结点编码长度减一
	   }
	  }
      free(cd);
}
void CreateCoding(HuffmanCode HC,Sqlist L)
{ 
	int i;
	char ch;
    static int a;
	FILE *fp,*fp1;
	
	if((fp=fopen("D:\\mn.txt","w"))==NULL)
	{
		printf("不能建立mn.txt文件\n");
		exit(0);
	}
    if((fp1=fopen("D:\\zf.txt","r"))==NULL)
	{
		printf("不能打开文件\n");
		exit(0);
	}

  
	while((ch=fgetc(fp1))!=EOF)
	{
       a=0;  
	   for(i=0;i<L.length;i++)
        if(L.elem[i]0)
		{
			a++;
		    if(ch==L.elem[i])
			{
              puts(HC[a]);
		      fputs(HC[a],fp);
			}
		}	
	}
	fclose(fp1);
	fclose(fp);
}

void Transnate(HuffmanTree HT,Sqlist T,Sqlist L)
{
	
	char ch;
	FILE *fp;
	int n,i;	
    static int	p;
	if((fp=fopen("D:\\mn.txt","r"))==NULL)
	{
		printf("不能打开mn.txt文件\n");
		exit(0);
	}
	n=T.length;
	p=2*n-1;
	
	while((ch=fgetc(fp))!=EOF)
	{  
		if(ch=='0')
	    	p=HT[p].lchild;		
		if(ch=='1')
			p=HT[p].rchild;					
		if(HT[p].lchild==0)
		{
		    int t=0;
			for(i=0;i<L.length;i++)
			{
				if(L.elem[i]0)
				{					
					t++;
					if(t==p)		
						printf("%c",L.elem[i]);
				}	         
			}
          p=2*n-1;
		}          
	}
}

int scan()
{
	int d;
	printf(" 请按顺序依次进行操作\n");
	printf("1.统计文章中每个英文字母的个数\n");
	printf("2.对每个字符进行编码并输出编码值\n");
    printf("3.创建文件存储需译码的二进制字符串\n");
    printf("4.进行译码输出对应的译码值\n");
	printf("0.推出.......\n");
	cin d;
	return d;
}

void main()
{ 
	
	HuffmanTree HT;
         HuffmanCode HC;
         Sqlist L,T;
	int i;
	int quit=0;
	while(!quit)
	switch(scan())
	{	
		case 1:CreateFile(L,T);break;
		case 2:HuffmanCoding(HT,HC,T);
			 
			 for(i=1;i<=T.length;i++)
             puts(HC[i]);break;
		case 3:CreateCoding( HC, L);break;
        case 4:Transnate(HT,T,L);break;
		case 0:quit;
	}
}