6.cpp

输入任意长度字符串 实现对字符串每个字符的 huffman编 输出字符的编码 输出编码后的字符串 实现编码后字符串的反编码 输出反编码后的字符串

#include <iostream>
#include <string>
using namespace std;

typedef  char ElementType;

int CountOutputBinary = 0;

class Node 
{
public:
	int weight;	//权
	ElementType element;//编码的字符
	Node* pLeft;
	Node* pRight;
	
	bool IsLeaf;	//标记是否为叶节点（含有编码的字符）
	int code;	//（如果是叶节点才有效）对应内部编码（二进制逆向写所对应数值）
	int depth;//（如果是叶节点才有效）对应深度（二进制逆向写所对应数值）
	Node()
	{
		code =0;
		depth =0;

		pRight=NULL;
		pLeft =NULL;
		
		weight=0;
		element=0;
		IsLeaf = true;
	}
	void displayBinaryCode() //显示二进制编码（当为叶结点是有效）
	{
		int i,j;
		for (i=4,j=2;j<=depth;i<<=1,j++)
		{
			
			if (code&i)
				putchar('1');
			else
				putchar('0');
		}
	}
	~Node()
	{

	}
};


class CountList
{
private:
	void inflate()	//当容量不足时，自行加倍
	{
		int newCapicity=capacity<<1;
		char* newList = new char[newCapicity];
		int* newCount = new int[newCapicity];
		int i;
		for (i=0;i<capacity;i++)
		{
			newList[i]=list[i];
			newCount[i]=count[i];

		}
		capacity = newCapicity;
		delete[] list;
		delete[] count;
		list = newList;
		count = newCount;
	}
	bool hasEncodeString;
	
	int* sStringLength;
public:
	int capacity;
	int size;
	ElementType* list;
	int* count;

	int* codes;
	int* depths;
	
	CountList()
	{
		hasEncodeString = false;
		
		size=0;
		capacity=100;
		list = new ElementType[100];
		count = new int[100];
		
	}

	~CountList()
	{
		delete[] list;
		delete[] count;
		delete[] codes;
		delete[] depths;
	}

	void add(ElementType element)
	{
		int i = find(element);
		if (i==size)
		{
			if (size==capacity)
			{
				inflate();
			}
			list[size]=element;
			count[size]=1;
			size++;
		}
		else
		{
			list[i]=element;
			count[i]++;
		}
	}
	int find(ElementType element) //查找相应被编码字符在本list中的索引，若为size表示不存在于其中
	{
		int i;
		for (i=0;i<size;i++)
		{
			if (list[i]==element)
			{
				break;
			}
		}
		return i;
	}
	void prepareCode()	//编码前，为相关数组申请空间
	{
		codes = new int[capacity];
		depths = new int[capacity];
	}
	void displayCode(ElementType element) //表示查找
	{
		int index = find(element);
		if (index>=size)
		{
			return;
		}
		int code = codes[index];
		int depth = depths[index];
		int i,j;
		//code可以看作所要求的huffman编码的二进制逆向时的数值
		for (i=4,j=2;j<=depth;i<<=1,j++)
		{

			if ((CountOutputBinary++%8)==0)	//每8个1/0输出一个空格
				putchar(' ');
			
			
			if (code&i)//若code（二进制）的第i位为1时为真
				putchar('1');
			else
				putchar('0');
		}
	}
}; 

/*Priority Queue*/
class PriorityQueue 
{
private:
	Node** heap;
	int number;
	int totalSize;
	int deleteIndex; 
		//标记可存放被从最小堆中删除的下标
	void BuildHeap(CountList& cList)
	{
		int i;
		heap[0] = new Node();
		for (i=1;i<=number;i++)
		{
			heap[i] = new Node();
			heap[i]->element = cList.list[i-1];
			heap[i]->weight = cList.count[i-1];
		
		}
		for (i=number/2;i>0;i--)
		{
			PercolateDown(i);
		}
	}
	void PercolateDown (int index)
	{
		Node* lastNode = heap[index];
		int i, child;
		for ( i = index; i*2<=number; i = child)
		{
			child=i*2;
			if (child!=number && heap[child+1]->weight<heap[child]->weight)
			{
				child++;
			}
			if ( lastNode->weight > heap[child]->weight )
			{
				heap[i] = heap[child];
			}
			else
				break;
		}
		heap[i]= lastNode;
	}
public:
	bool hasBeenCoded; //标记是否已经被编码
	
	PriorityQueue (CountList& cList)
	{
		hasBeenCoded = false;
		number = cList.size;
		totalSize = number*2;
		deleteIndex = number*2-1;
		heap = new Node*[number*2];
		int i;
		for (i=0;i<totalSize;i++)
		{
			heap[i]=NULL;
		}
		BuildHeap(cList);
	}
	~PriorityQueue(){
		int i;
		for (i=0;i<totalSize;i++)
		{
			delete heap[i];
		}
		delete[] heap;
	}
	void displayCoding()
	{
		if ( hasBeenCoded == true)
		{
			int i;
			Node* pNode;
			for (i=1;i<totalSize;i++)
			{
				pNode = heap[i];
				if (pNode!=NULL && pNode->IsLeaf == true)
				{
					cout<<pNode->element<<'\t';
					pNode->displayBinaryCode();
					cout<<endl;
				}	
			}
		}
	}
	
	Node* DeleteMin()
	{
		int i, child;
		Node* minNode;
		Node* lastNode;
		if (number == 0)
		{
			return NULL;
		}
		heap[deleteIndex--] = heap[1]; //被deleteMin的项转移到deleteIndex所在位置，而不被删除
		minNode = heap[1];
		lastNode = heap[number--];
		for ( i = 1; i*2<=number; i = child)
		{
			child=i*2;
			if (child!=number && heap[child+1]->weight<heap[child]->weight)
			{
				child++;
			}
			if ( lastNode->weight > heap[child]->weight )
			{
				heap[i] = heap[child];
			}
			else
				break;
		}
		heap[i]= lastNode;
		lastNode = NULL;
		return minNode;
	}
	void insert(Node* newNode)
	{
		int i;
		for (i=++number; heap[i/2]->weight > newNode->weight; i/=2)
		{
			heap[i]=heap[i/2];
		}
		heap[i]=newNode;
	}
	Node* getRoot()
	{
		return heap[1];
	}
};

class Huffman
{
private:
	PriorityQueue* priQueue;
	Node* pRoot;
	CountList* relatedCList;
public:
	Huffman(CountList& cList)
	{
		relatedCList = &cList;
		priQueue = new PriorityQueue(cList);
		Node* pNode;
		int i;
		for(i=1;i<cList.size;i++)
		{
			pNode = new Node();
			pNode->pLeft = priQueue->DeleteMin();
			pNode->pRight = priQueue->DeleteMin();
			pNode->IsLeaf = false;
			pNode->weight = pNode->pLeft->weight + pNode->pRight->weight;
			priQueue->insert(pNode);
		}
		pRoot = priQueue->getRoot();
	}
	~Huffman()
	{
		delete priQueue;
	}
 	
	void generateCoding(){      ///根据已有的ｈｕｆｆｍａｎ树生成可各字符的编码（内部的code）
	
		if (priQueue->hasBeenCoded==false)
		{
			priQueue->hasBeenCoded =true;
			generateCode(pRoot,0,0,0);
		}
		priQueue->displayCoding();
		cout<<endl;
	}
	void generateCode(Node* pNode, int LeftOrRight, int depth, int value) //生成内部编码的迭代版本
	{
		if (LeftOrRight==1)
		{
			value+=(2<<depth);	
		}
		depth++;
		if (pNode!=NULL)
		{
			if (pNode->IsLeaf == true)
			{	
				relatedCList->codes[relatedCList->find(pNode->element)] = value;
				relatedCList->depths[relatedCList->find(pNode->element)] = depth;
				pNode->code = value;
				pNode->depth = depth;
			}
			else
			{
				generateCode(pNode->pLeft, 0, depth, value);
				generateCode(pNode->pRight,1, depth, value); 
			}
			
		}
		
	}
	void encodeBinaryString(string strToBeEncoded){// 解压缩主函数，输入（只含有'1'，'0'的字符串)
		int i;
		Node* pNode = pRoot;
		for (i=0;i<strToBeEncoded.length();i++)
		{
			if (strToBeEncoded[i]=='1')
			{
				pNode = pNode->pRight;
			}
			else if (strToBeEncoded[i]=='0')
			{
				pNode = pNode->pLeft;
			}
			else
			{
				cout<<"ERROR INPUT!"<<endl;
				return;
			}
			if(pNode->IsLeaf == true)
			{
				cout<<pNode->element;
				pNode = pRoot;
			}
		}
	}
};



int main()
{
	string strIn;
	CountList cList;
	cout<<"请输入字符串"<<endl;
	cin>>strIn;
	int i;
	for (i=0;i<strIn.length();i++)
	{
		cList.add( (strIn[i]) );
	}
	cList.prepareCode();
	Huffman huffCoder(cList);
	huffCoder.generateCoding();
	string strEncode;


	cout<<"Compressed string (binary):"<<endl;

	for (i=0;i<strIn.length();i++)
	{
		cList.displayCode(strIn[i]);
	}
	cout<<endl;

	cout<<"Input the binary code to be encoded:"<<endl;
	cin>>strEncode;

	

	huffCoder.encodeBinaryString(strEncode);
	cout<<endl;

	return 0;
}