baseoperator.cpp

哈夫曼编_译码器,编码器的实现元代码,数据结构和算法的课程设计,很不错的!

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include "ctype.h"
#include <stdio.h>
#include "SaveType.h"
#include "BaseOperator.h"
#include<conio.h>


//BaseOperator.cp                                                                                                     
                                                           //选择两个顶点最小的函数
//————————————————————————————————————————————

void Selete(HuffmanTree HT,int i,int &s1,int &s2){
	int j,k;
	for(k=1;k<=i;k++){
		if(HT[k].parent==0) {s1=k;break;}
	}
	for(j=1;j<=i;j++){
		if(HT[j].parent==0){
			if(HT[s1].weight >HT[j].weight) s1=j;   //找到最小的一个结点
		}
	}
	for(k=1;k<=i;k++){
		if(HT[k].parent==0 && k!=s1) {s2=k;break;}
	}
	for(j=1;j<=i;j++){
		if(HT[j].parent==0 && j!=s1){
			if(HT[s2].weight>HT[j].weight) s2=j;   //找到最小的一个结点
		}
	}
}

   //初始化，
void Huffman::InitHuffmanTree(HuffmanTree &HT,int n){
	int i,m;
	HuffmanTree p;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));   //0号单元未用
	for(p=HT,p++,i=1;i<=m;i++,p++){
		p->data='*';
		p->weight=p->parent=p->lchild=p->rchild=0;
	}
}
                                                                       //建立哈夫曼编码存储结构
//————————————————————————————————————————————————
void Huffman::CreatHuffmanTree(HuffmanTree &HT,int n){
	//w存放n个字符的权值（均>0），构造哈夫曼树HT
	int i,j=0,m;
	int s1,s2;
	HuffmanTree p;
    m=2*n-1;

	for(p=HT,p++,i=1;i<=n;i++,p++){
		if(j==2) {system("cls");j=0;}
		cout<<"请输入字符及其权值！"<<endl;
		cout<<"字符 "<<i<<"为： ";cin>>p->data;cout<<endl;//p->data=getche();cout<<endl;
		if('a'<=p->data&&p->data<='z')    //如果输入的是小写字母，将它们转变为大写字母
			p->data=p->data-('a'-'A');
loop:
		cout<<"其权值为：";cin>>p->weight;cout<<endl;
		if(p->weight<0){
			cout<<"你输入的权值超出范围，请重新输入!"<<endl;
			goto loop;
		}
		p->parent =p->lchild=p->rchild=0;
		j++;
	}


	for(i=n+1;i<=m;i++){
		//在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2
		Selete(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 ;
	}
}


                                       //编码：：将要传送的报文编码，然后将结果存入文件CodeFile中
//————————————————————————————————————————————————
void Huffman::HuffmanEnconding(HuffmanTree HT,int n){
	char ch1;
	SaveType savetype;
	FILE *fp,*fp1;
	int i,j,m;
	int flag;
	int start,f;
	unsigned int c;
	char ch[100];
	char *cd;
	HuffmanCode HC;
	
loop:system("cls");   //清屏
	cout<<endl;cout<<endl;cout<<endl;
	cout<<"                     请输入一串字符，每次不要超过100个！"<<endl;cout<<endl;
	gets(ch);                         //输入字符串
	m=strlen(ch);                     //计算字符串的长度

	HC=(HuffmanCode)malloc((m+1)*sizeof(char *));      //分配n个字符编码的头指针向量
	cd=(char *)malloc(m*sizeof(char));                //分配求编码的工作空间
	cd[m-1]='\0';
	for(i=0;i<m;i++){
		start=m-1;
		ch1=ch[i];             //得到字符串中的第i个字符
		if('a'<=ch1 && ch1<='z')       //如果输入的是小写字母，将它们转变为大写字母
			ch1=ch1-('a'-'A');
		for(j=1;j<=n;j++)      //在哈夫曼树中找到字符ch1所在的位置j
			if(ch1==HT[j].data) break;

			for(c=j,f=HT[j].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));      //为第i个字符编码分配空间
			strcpy(HC[i],&cd[start]);                          //从cd复制编码（串）到HC
	}


		fp=fopen("CodeFile.text","w+");          //创建该文件
		fclose(fp);
		if(!(fp1=fopen("AllCodeFile.text","a"))){
			fp1=fopen("AllCodeFile.text","w+");
			fclose(fp1);
		}
loop1:
	flag=0;   system("cls");     //清屏
	cout<<endl;cout<<endl;
	cout<<"                    你要输入的字符串结束了吗？Y/N"<<endl;
	cin>>ch1;
	switch(ch1){
	case 'Y':
	case 'y': {  flag=1;
		         savetype.SaveCode(m,HC,flag);
				 if(flag==1) goto loop;
		         else break;
			  }
	case 'N':
	case 'n':{  flag=0;
		        savetype.SaveCode(m,HC,flag);          //保存编码
	            if(flag==1)	goto loop;
				else break;
			 }
	default: goto loop1;
	}
}

                                     //译码：：将文件CodeFile中的代码进行译码，然后保存到TextFile
//————————————————————————————————————————————————
void Huffman::HuffmanDeconding(HuffmanTree HT,int n){
	 FILE *fp,*fp1;
	 SaveType savetype;
     int i,m;
	 int c;
	 char ch,ch1;

     m=2*n-1;
	 for(i=n+1;i<=m;i++) if(HT[i].parent ==0) break;    //找寻根结点的位置i.*/

	 fp=fopen("CodeFile.text","r");     	//打开传送过来的代码文件，准备译码

     fp1=fopen("TextFile.text","w+");       //为译码打开文件“TextFile.text”，并置为空
	 fclose(fp1);

//读入数据
     ch=fgetc(fp);
	 while(ch!=EOF){
		 c=i;
		 while(HT[c].data=='*'){
			 if(ch=='0') c=HT[c].lchild;
			 else if(ch=='1') c=HT[c].rchild;
			 ch=fgetc(fp);
		 }
		ch1=HT[c].data;
        savetype.SaveWord(ch1);            //保存译码后的数据
	}
	 fclose(fp);
	 return;
}
//——————————————————————————————————————————
//将二叉树的结果村入二进制文件中
void Huffman::SaveHuffmanTree(HuffmanTree HT,int n){
	FILE *fp;
	int i,m;
	m=2*n-1;
	fp=fopen("TreeCode.exe","wb+");
	for(i=1;i<=m;i++){
		fwrite(&HT[i],sizeof(struct HTNode),1,fp);
	}
	fclose(fp);
	return;
}

                                                   //保存树的图形结构！！！！ 

//建立二叉链表树  
//——————————————————————————————————————————                                               
void CreatTree(HuffmanTree HT,int i,BSTree &T){
	BSTree p,p1;
	int j,k;
    T->data=HT[i].data;

	if(HT[i].lchild==0) {T->lchild=NULL;T->rchild=NULL;}
	else{
		p=(BSTree)malloc(sizeof(BSTNode));
		j=HT[i].lchild;
		T->lchild=p;
		CreatTree(HT,j,p);

		p1=(BSTree)malloc(sizeof(BSTNode));
		k=HT[i].rchild;
		T->rchild=p1;
		CreatTree(HT,k,p1);
	}
	return;
}

//用树的形式打印哈夫曼树
//————————————————————————————————————————————
void PrintHuffmanTree( BSTree T, int i )
{

	if( T->rchild )
	{
		PrintHuffmanTree( T->rchild, i+1 );
	}
	int j = 0;
	for( j = 1; j <= i; j++ )  //打印i个空格以表示出层次
	{
		cout<<"       ";
	}
	cout<<T->data; cout<<endl; //打印T元素,换行
	if( T->lchild )
	{
		PrintHuffmanTree( T->lchild, i+1 );
	}
}//PrintAVL()

//——————————————————————————————————————————
void Huffman::SaveTreePrint(HuffmanTree HT,int n){
	int i,m;
	BSTree T;
	m=2*n-1;
	for(i=n+1;i<=m;i++)
		if(HT[i].parent==0) break;      //找到头结点的位置 "i"

	T=(BSTree)malloc(sizeof(BSTNode));
	T->data='*';T->lchild=T->rchild =NULL;    //初始化T；
	CreatTree(HT,i,T);
	i=0;
	PrintHuffmanTree(T,i);
	return;
}