huffman.cpp

数据结构经典算法的C语言实现 计算机专业数据结构课程实验

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

struct HTnode {
	double weight;
	char   c;
	HTnode *lchild;
	HTnode *rchild;
	HTnode *parent;
};  //结点型

typedef HTnode * HuffmanT;

struct CodeNode {
	char c;
	char *bit;               
};

typedef CodeNode * CodeTable;  

//生成空链表
void MAKENULL(HuffmanT &leaf) {
	leaf = new HTnode;
	leaf->weight = -1;
	leaf->lchild = leaf->rchild = leaf->parent = NULL;
}
//插入新结点
void INSERT(HuffmanT p, HuffmanT huf) {
	HuffmanT e = huf;
	HuffmanT q = huf;

	while ((huf != NULL) && (p->weight > huf->weight)) {
		q = huf;
		huf = huf->parent;
	}
	p->parent = q->parent;
	if (p->lchild == NULL)
		p->rchild = q->parent;
	q->parent = p;
	if (p->lchild == NULL)
		q->rchild = p;
}
//输入字符及权值（权值为正数），并按权值由大到小排列
HuffmanT HINPUT(int total) {
	int i;
	HuffmanT leaf = NULL;
	HuffmanT p = NULL;

	MAKENULL(leaf);

	for (i = 1;i <= total;i++) {
		p = new HTnode;
		p->lchild = p->rchild = p->rchild = NULL;
		cout<<"请输入"<<i<<"第个字符：";
		cin>>p->c;
		cout<<"请输入权值（正数）：";
		cin>>p->weight;

		INSERT(p, leaf);
	}
	return leaf;
}
//建立哈夫曼树
HuffmanT HUFFMAN(HuffmanT &leaf) {
	HuffmanT p = NULL;
	HuffmanT q = NULL;

	while (leaf->parent->parent != NULL) {
		p = new HTnode;
		p->weight = leaf->parent->weight + leaf->parent->parent->weight;
		p->lchild = leaf->parent;
		p->rchild = leaf->parent->parent;
		leaf->parent = leaf->parent->parent->parent;
		p->lchild->parent = p;
		p->rchild->parent = p;
		INSERT(p, leaf);
	}
	q = leaf;
	leaf = leaf->rchild;
	delete q;
	
	return p;
}
//创建哈夫曼编码表
CodeTable MAKETABLE(HuffmanT huf, HuffmanT leaf, int n) {
	int i = 1;
	int position;
	CodeTable table = NULL;
	char *p = NULL;
	HuffmanT q = NULL;

	p = (char *) malloc(n * sizeof(char));
	*(p + n - 1) = '\0';
	table = (CodeNode *) malloc( n * sizeof(CodeNode) );
	for (i = 0;i < n;i++) {
		(table + i)->c = leaf->c;
		position = n - 1;
		q = leaf;
		while (q->parent != NULL) {
			*(p + (--position)) = (q->parent->lchild == q)?'0':'1';
			q = q->parent;
		}
		(table + i)->bit = (char *) malloc((n - position) * sizeof(char));
		strcpy((table + i)->bit, (p + position));
		cout<<(table + i)->c;
		cout<<(table + i)->bit<<endl;
		leaf = leaf->rchild;
	}
	return table;
}
//编码函数
void MAKECODE(CodeTable table, int n) {
	char c;
	int i;

	cout<<"请输入要编码的字符串："<<endl;
	while ( (c = getchar()) !='\n' ) {
		for (i = 0; (i < n) && ( (table + i)->c != c ); i++);
		if ((table + i)->c != c)
			cout<<"输入错误！"<<c; 
		else
			cout<<(table + i)->bit<<" ";
	}
	cout<<endl;
}
//译码函数
void TRANSLATE(HuffmanT huf) {
	char c;
	HuffmanT p = huf;
	cout<<"请输入要译码的编码序列："<<endl;
	while ((c = getchar()) != '\n') {
		if (c == '0')
			p = p->lchild;
		else if (c == '1')
			p = p->rchild;
		else {
			cout<<"输入错误！"<<endl;
			while (getchar() != '\n');
			exit(0);
		}
		if (p->lchild == NULL) {
			cout<<p->c;
			p = huf;
		}
	}
	cout<<endl;
}
//输入译码字符串
HuffmanT HINPUT1(void) {
	char ch;
	int  a = 0, c = 0, t = 0, g = 0;
	HuffmanT leaf = NULL;
	HuffmanT p = NULL;

	cout<<"输入要进行统计的串(A,C,G,T)："<<endl;
	while ((ch = getchar()) != '\n') {
		switch(ch) {
			case 'A':
				a++;
				break;
			case 'C':
				c++;
				break;
			case 'T':
				t++;
				break;
			case 'G':
				g++;
				break;
			default:
				cout<<"请输入只含有A,C,G,T的字符串！"<<endl;
				break;
		}
	}
	MAKENULL(leaf);
	p = new HTnode;
	p->lchild = p->rchild = p->rchild = NULL;
	p->c = 'A';
	p->weight = (((double) a )/(a + c + t +g) );
	cout<<"A出现次数："<<a<<"	"<<"频率："<<p->weight<<endl;
	INSERT(p, leaf);
	p = new HTnode;
	p->lchild = p->rchild = p->rchild = NULL;
	p->c = 'C';
	p->weight = (((double) c)/(a + c + t +g) );
	cout<<"C出现次数："<<c<<"	"<<"频率："<<p->weight<<endl;
	INSERT(p, leaf);
	p = new HTnode;
	p->lchild = p->rchild = p->rchild = NULL;
	p->c = 'T';
	p->weight = ( ((double) t)/(a + c + t +g) );
	cout<<"T出现次数："<<t<<"	"<<"频率："<<p->weight<<endl;
	INSERT(p, leaf);
	p = new HTnode;
	p->lchild = p->rchild = p->rchild = NULL;
	p->c = 'G';
	p->weight = (((double) g)/(a + c + t +g) );
	cout<<"G出现次数："<<g<<"	"<<"频率："<<p->weight<<endl;
	INSERT(p, leaf);

	return leaf;
}

void main() {
	int total, i;
	char yn;
	HuffmanT huf = NULL;
	HuffmanT leaf = NULL;
	CodeTable table = NULL;
lable:	
	cout<<"欢迎使用本程序！请选择您要执行的操作："<<endl;
	cout<<"1.输入由A,C,G,T组成的字符串，按字符出现的频率将其编码"<<endl;
	cout<<"2.手动输入某些字符、权值及其出现的频率"<<endl;
	cin>>i;

	if(i == 1) {
		leaf = HINPUT1();
		total = 4;
	}
	else if(i == 2) {
		cout<<"共有多少个字符：";
		cin>>total;
		leaf = HINPUT(total);
	}
	else {
		cout<<"输入错误！请重新选择！"<<endl;
		goto lable;
	}
		
	huf = HUFFMAN(leaf);
	table = MAKETABLE(huf, leaf, total);

	MAKECODE(table, total);
	TRANSLATE(huf);
	
	cout<<"是否继续使用本程序？继续请按Y，退出请按N：";
	cin>>yn;
	if(yn == 'y' || yn == 'Y')
		goto lable;
}