huffman.cpp

一个多项式运算程序 实现多项式的加 减 乘除 乘方 积分 微分 混合运算 一个二叉树运算程序 实现二叉树的创建 复制 深度计算 和树形显示 一个哈夫曼算法的演示程序 实现对电文的编码 编码的输出

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<stdio.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MAXSIZE 50
#define TEXTSIZE 100
char buff[TEXTSIZE];

typedef struct{
	int weight;
	int lchild,rchild,parent;
	char data;
} HTNode;

typedef struct {
	HTNode *HTree;
	int root;
	int leafnum;
}HuffmanTree;
typedef struct stack{
	int data;
	struct stack *next;
} stack,* linkstack;
typedef struct
{
      char  *HCode;
	  char data;
} HuffmanCode,*linkHC;


/**************************************************************/
void push(linkstack &S,int e)
{   linkstack p;
	p=new stack;
	p->data=e;
	p->next=S;
	S=p;
}
/**************************************************************/
bool pop(linkstack &S,int &e)
{
	linkstack p;
	if(S)
	{
		p=S;
		S=S->next;
		e=p->data;
		delete p;
		return TRUE;
	}
	else return ERROR;
}
/*		********************************************************************			*/
int Stacklength(linkstack S)
{
	int lenth=0;
	linkstack p;
	p=S;
	while(p!=NULL)
	{
		lenth++;
		p=p->next;
	}
	return lenth;
}
/*		********************************************************************			*/
void Checkmin(HuffmanTree HT,int endpos,int &minpos)
{
	int i=1;
	while(1)
	{
		if(HT.HTree[i].parent==-1)
		{
			minpos=i;
			break;
		}
		i++;
	}// find proper postion for minpos

	i=1;
	while(i<=endpos&&HT.HTree[i].parent==-1)
	{
		if(HT.HTree[i].weight<HT.HTree[minpos].weight)
		{minpos=i;}
		i++;
	}//while
}//checkmin
/*		********************************************************************			*/
void StackTraverse(linkstack S,linkHC &HC)
{  
	int i;
	i=Stacklength(S);
    (*HC).HCode[i]='\0';
	linkstack p=S;

	while(p)
	{
		i--;
		(*HC).HCode[i]=p->data;
		p=p->next;
	}
}
/*		********************************************************************			*/
int Locate(linkHC HC,char ch)
{
	int i=0;
	while(HC[i].data!=ch)
	{
		i++;
	}
	return i;
}
/*		********************************************************************			*/
void Getsentences(char* &s,int* &w,int &n)//s 存放出现的字符 w存放出现的次数即权值 n时字符个数
{
	n=0;
	int j;
	int i=0;


	s=new char [21];
	for(i=0;i<=20;++i)
	{
		s[i]='\0';
	}
	w=new int [21];
	for(j=0;buff[j]!='#';++j)// j is position of buff ,i is current position in s[]  , n is length of s[]
	{
		i=1;// first node useless
		while(i<=n)
		{
			if(buff[j]==s[i])break;
            else i++;
		}
		if(i>n){
			s[i]=buff[j];
			w[i]=1;
			n++;
		}
		else w[i]++;
	}
}//getsentences
/*		********************************************************************			*/
void CreatHuffman(HuffmanTree &HT)
{
	char *s;
	int *w;
	int n,m,i,s1=0,s2=0;
	HTNode *p;

    Getsentences(s,w,n);
	m=2*n-1;
    HT.HTree=new HTNode[m+1];// first node wasted


	for(p=HT.HTree,p++,i=1,s++,w++;i<=n;++i,++s,++w,++p)
	{
		p->data=*s;
		p->weight=*w;
		p->parent=-1;
		p->lchild=-1;
		p->rchild=-1;
	}
	for(;i<=m;++i,++p)
	{
		p->data='\0';
		p->weight=0;
		p->parent=-1;
		p->lchild=-1;
		p->rchild=-1;
	}

	for(i=n+1;i<=m;++i)
	{
		Checkmin(HT,i-1,s1);
		HT.HTree[s1].parent=i;
		Checkmin(HT,i-1,s2);
        HT.HTree[s2].parent=i;
        HT.HTree[i].lchild=s1;
		HT.HTree[i].rchild=s2;
		HT.HTree[i].weight=HT.HTree[s1].weight+HT.HTree[s2].weight;
	}

	HT.root=m;
	HT.leafnum=n;
}//creat huffman
/*		********************************************************************			*/
void  Coding(HuffmanTree HT,int i, linkstack &S,linkHC &p,linkHC &HC)
{//HT是建好的树 s是栈 p是指向结构体HC单元的指针 初值是HC的首地址 HC是存放哈夫曼码的结构体数组
//每次p向下指一个单元 实现对HC.HCode[]的赋值操作。疑问：1.p的那项如果直接传HC就不行 每次HC++实现的是
//对整个数组地址的移动 2.p如果传入HC就不行 必须在上一级中将HC付给p 再将p传进来！？？？
	    
	    int e;
		if(HT.HTree[i].lchild==-1)
		{   //l=Stacklength(S);
			(*p).HCode=new char[Stacklength(S)+1];// set a place for the singal of the end  
			StackTraverse(S,p);
			(*p).data=HT.HTree[i].data;
		    p++;
		}
		else
		{ push(S,'0');
		Coding(HT,HT.HTree[i].lchild,S,p,HC);
		pop(S,e);
		push(S,'1');
		Coding(HT,HT.HTree[i].rchild,S,p,HC);
		pop(S,e);}
}//Coding
		
/*		********************************************************************			*/
void Creatcode(HuffmanTree HT,linkHC &HC,int n)// n is leafnum +1
{
	linkHC   p;
	linkstack S;
	HC=new HuffmanCode [n];// ONLY pointer can apply for space!
	p=HC;
	S=NULL;
	

	Coding(HT,HT.root,S,p,HC);
}
/*		********************************************************************			*/
void Showcode(linkHC HC,HuffmanTree HT)
{
	char c;
	int k=0,i;
	cout<<"请输入要显示的字符：\n";
	cin>>c;
	while(k<HT.leafnum && HC[k].data!=c)
	{
		k++;
	}
	if(k==HT.leafnum) cout<<"ERROR!";
	else 
	{
		cout<<HC[k].data;
	
	
		for(i=0;HC[k].HCode[i]!='\0';++i)
		{
		cout<<HC[k].HCode[i];
		}// 输出哈夫曼码
	}//else
}//showcode
/*		********************************************************************			*/
void Codetext(char *buff,FILE* &fp,linkHC HC)
{ 
	if(!(fp=fopen("huffmancode","w")))
	{
		cout<<"file open error!!";
	    return;
	}
    while(*buff!='#')
	{
		int pos;
		int i=0;
		pos=Locate(HC,*buff);
        while(HC[pos].HCode[i]!='\0')
		{
			fputc(HC[pos].HCode[i],fp);
			i++;
		}
		buff++;
	}//while

	fputc('\0',fp);//put end mark

	fclose(fp);
}
void Showtext(FILE* fp)
{
    if(!(fp=fopen("huffmancode","r")))
	{
		cout<<"file open error!!";
	    return;
	}
    //ch=fgetchar(fp)
	while(!feof(fp))
	{
		putchar(fgetc(fp));
	}
	fclose(fp);
}//
/*		********************************************************************			*/
void Recodetext(FILE *fp, HuffmanTree HT)
{
	 int pos=HT.root;
	 char ch;
	 ch=fgetc(fp);
	 while(ch!='\0')
	 {
		 
		 if(ch=='0') pos=HT.HTree[pos].lchild;
         else if(ch=='1') pos=HT.HTree[pos].rchild;
         if(HT.HTree[pos].lchild==-1) 
		 {
			 cout<<HT.HTree[pos].data;
			 pos=HT.root;
		 }
		 ch=fgetc(fp);

	 }
}
/*		********************************************************************			*/
void main()
{
	int i=0,k;
	HuffmanTree HT;
	linkHC HC;
	FILE *fp;

while(1)
{
    
	cout<<"-------------HUFFMAN CODE MACHINE---------------\n"
		<<"1 输入电文并创建哈夫曼树和创建哈夫曼编码\n"
		<<"2 输出指定字符的哈夫曼编码\n"
		<<"3 对电文进行哈夫曼编码\n"
		<<"4 显示电文的哈夫曼编码序列\n"
		<<"5 还原哈夫曼编码序列为原电文\n"
	    <<"0 退出\n";

        cin>>k;
	switch(k)
	{
	    case 1:
		{
			//cout<<"请输入电文,以 # 结束输入:\n";
			printf("请输入电文,以 # 结束输入\n");
		while(1)
			{
			    //scanf("%c",&buff[i]);
		        buff[i]=getchar();
	            if(buff[i]=='#') break;
		        i++;
			}//while
	
		
			CreatHuffman(HT);
			cout<<"哈弗曼树创建成功\n\n";
	
		    Creatcode(HT,HC,HT.leafnum+1);
		    cout<<"哈弗曼编码创建成功\n\n";
			break;
			
		}
		case 2:
			{
				Showcode(HC,HT);
				cout<<"\n";
				break;
			}
		case 3:
			{
				Codetext(buff,fp,HC);
				cout<<"电文哈夫曼编码创建成功\n\n";
				break;
			}
		case 4:
			{
				Showtext(fp);
				cout<<"\n";
 
				break ;
			}
		case 5:
			{
				if(!(fp=fopen("huffmancode","r+")))
				{
	 	              cout<<"file open error!!";
	                  return;
				}

                cout<<"还原的电文如下：\n";
				Recodetext(fp,HT);
				cout<<"\n";
				break;
			}
		case 0:
			{
				return;
			}
	}//swich
}//while
}//main