//**************************huffman.cpp**********************#include <iostream>#include <fstream> //for ofstream ifstream#include <limits>  //for numeric_limits<double>::max()#include <cstdlib> //for exit()#include <cstring> //for strlen(), strcpy(), strcmp()#include "huffman.h"using namespace std;void HuffmanTree::insert(const char &data, const double &wt) { //插入結點	if (2*currentSize-1 >= maxSize) //葉子結點為n的哈夫曼樹共有2n-1個結點		return;	arrayTree[currentSize].info=data;	arrayTree[currentSize].weight=wt;	currentSize++;}void HuffmanTree::reverse(char arr[]) { //反轉字符串	const int len=strlen(arr);	char *p;	p=new char[len+1];	strcpy(p, arr);	p[len]='\0';	int k=0;	for (int i=len-1; i>=0; i--) 		arr[i]=p[k++];	arr[len]='\0';	delete[] p;}int HuffmanTree::findPosition(const char &ch) const { //返回字符ch在arrayTree[]中的位置	for (int i=0; i<currentSize; i++)		if (arrayTree[i].info == ch)			return i;	return -1;}int HuffmanTree::getLongestCodeLength() const { //返回編碼數組codeArray[]長度最長的編碼的位置	if (currentSize == 0)		return -1;	int len=strlen(codeArray[0].ptr);	int i=1;	while (i < currentSize) {		int tmp=strlen(codeArray[i].ptr);		if (tmp > len)			len=tmp;		i++;	}	return len;}int HuffmanTree::isEqual(const char *s) const { //判斷s的編碼是否存在，若存在返回編碼在數組codeArray[]中的位置，否則返回-1	for (int i=0; i<currentSize; i++) 		if (strlen(s) == strlen(codeArray[i].ptr)) //可以去掉此行			if (strcmp(s, codeArray[i].ptr) == 0)				return i;	return -1;}	void HuffmanTree::print() { //打印編碼	int k=0;	while (k < currentSize) {		cout<<arrayTree[k].info<<'('<<arrayTree[k].weight<<"): "<<codeArray[k].ptr<<endl;		k++;	}}void HuffmanTree::createHuffmanTree() { //構造huffmanTree	int i=currentSize;	int k;	double wt1, wt2;	int lnode, rnode;	while (i < 2*currentSize-1) {		wt1=wt2=numeric_limits<double>::max();		k=0;		while (k < i) {			if (arrayTree[k].parent==-1) {				if (arrayTree[k].weight<wt1) {					wt2=wt1;					rnode=lnode;					wt1=arrayTree[k].weight;					lnode=k;				}				else if (arrayTree[k].weight<wt2) {					wt2=arrayTree[k].weight;					rnode=k;				} 			}			k++;		}		arrayTree[i].weight = arrayTree[lnode].weight+arrayTree[rnode].weight;		arrayTree[i].lchild=lnode;		arrayTree[i].rchild=rnode;		arrayTree[lnode].parent=arrayTree[rnode].parent=i;		i++;	}}			void HuffmanTree::createHuffmanCode() { //構造huffmanCode，即哈夫曼編碼	codeArray=new Code[currentSize];	int i=0;	int k, n, m;	while (i < currentSize) {		k = arrayTree[i].parent;		n=0;		m=i;		while (k!=-1 && k<currentSize*2-1) {			if (arrayTree[k].lchild==m) 				codeArray[i].ptr[n++]='0';			else if (arrayTree[k].rchild==m) 				codeArray[i].ptr[n++]='1';			m=k;			k=arrayTree[m].parent;		}		codeArray[i].ptr[n]='\0';		reverse(codeArray[i].ptr); //反轉字符串，使之變成正確的編碼		i++;	}}void HuffmanTree::run(const char *inFilename, const char *outFilename, const char *secondOutName) { //run函數的實現	//打開inFilename提供輸入	ifstream fileIn(inFilename, ios::in);	if (!fileIn) {		cerr<<"\""<<inFilename<<"\" could not open."<<endl;		exit(1);	}	char ch;	int pos;	//從文件中讀入字符，并統計各個字符個數	fileIn>>ch;	while (fileIn && !fileIn.eof()) {		pos = findPosition(ch);		if (pos != -1)			arrayTree[pos].weight++;		else 			insert(ch, 1);		fileIn>>ch;	}	createHuffmanTree(); //構造huffman樹	createHuffmanCode(); //對統計字符進行編碼	//打開outFilename提供輸出	ofstream fileOut(outFilename, ios::out);	if (!fileOut) {		cerr<<"\""<<outFilename<<"\" could not open."<<endl;		exit(1);	}	fileIn.clear(); //刷新輸入流, 注：ofstream沒有flush()方法，而ifstream則有flush()方法	fileIn.seekg(0, ios::beg);	//把從inFilename文件中的字符進行編碼，并寫入outFilename文件	fileIn>>ch;	while (fileIn && !fileIn.eof()) {		pos = findPosition(ch);		if (pos != -1)			fileOut<<codeArray[pos].ptr;		fileIn>>ch;	}	fileIn.close();	fileOut.close();	//打開outFilename, secondOutName，分別提供輸入輸出	fileIn.open(outFilename, ios::in);	fileOut.open(secondOutName, ios::out);	if (!fileIn || !fileOut) {		cerr<<"File could not open."<<endl;		exit(1);	}	//把outFileName文件中的編碼進行譯碼，并把譯碼結果寫入secondOutName文件	const int longestLen = getLongestCodeLength();	char *p = new char[longestLen+1];	int k=0;	fileIn>>ch;	while (fileIn && !fileIn.eof()) {		if (k < longestLen) {			p[k++]=ch;			p[k]='\0';			pos = isEqual(p);			if (pos != -1) {				fileOut<<arrayTree[pos].info;				k=0;			}		}		else {			cerr<<"The code is wrong."<<endl;			exit(1);		}		fileIn>>ch;	}	fileIn.close();	fileOut.close();}		//huffman.cpp end