//
#include <iostream.h>
#include <stdio.h>
#include <string.h>
const long wordnum = 1000;//最大不同單詞數
const long code_len = wordnum/10;
const long wordlen = 30;//單詞最長長度
const long codemax = 10000;//最大haffuman編碼長度
const long wordmax = 10000;//最大單詞數
//str類定義
class str
{
public:
str();
bool operator<(str obj);//運算符重載方便對str的排序使用二分搜索模板
bool operator>(str obj);
str operator=(char p[]);
str operator++(int);//重載後綴方式的＋＋
char *getword();
long getfre();
protected:
private:
char word[wordlen];
long frequence;
};
str::str()
{
frequence = 0;
}
//以下為重載str類中的運算符
bool str::operator<(str obj)
{
if(strcmp(word,obj.word) < 0)
return true;
else
return false;
}
bool str::operator>(str obj)
{
if(strcmp(word,obj.word) > 0)
return true;
else
return false;
}
str str::operator=(char p[])
{
strcpy(word,p);
return *this;
}
str str::operator++(int x)
{
frequence ++;
return *this;
}
char * str::getword()
{
return word;
}
long str::getfre()
{
return frequence;
}
//str類定義結束
//Node類定義
class Node
{
public:
Node();
bool operator<(Node obj);//運算符重載方便對Node的排序使用堆模板
bool operator<=(Node obj);
bool operator>(Node obj);
Node operator=(str obj);
Node operator+(Node &obj);
Node *leftp();//類外獲取指向當前節點的孩子的指針
Node *rightp();
char *getword(Node *p);//類外獲取節點信息
long getfrequence();
protected:
private:
char word[wordlen];
long frequence;
Node *left, *right;
};
Node::Node()
{
strcpy(word,"NULL");
left = NULL;
right = NULL;
}
//以下為重載Node類中的運算符
bool Node::operator<(Node obj)
{
if(frequence < obj.frequence)
return true;
else
return false;
}
bool Node::operator<=(Node obj)
{
if(frequence <= obj.frequence)
return true;
else
return false;
}
bool Node::operator>(Node obj)
{
if(frequence > obj.frequence)
return true;
else
return false;
}
Node Node::operator+(Node &obj)
{
Node sum;
sum.frequence = frequence + obj.frequence;//指針指向了NULL
sum.left = this;
sum.right = &obj;
return sum;
}
Node Node::operator=(str obj)
{
strcpy(word,obj.getword());
frequence = obj.getfre();
return *this;
}
Node * Node::leftp()
{
return left;
}
Node * Node::rightp()
{
return right;
}
char * Node::getword(Node *p)
{
return p->word;
}
long Node::getfrequence()
{
return frequence;
}
//Node類定義結束
//str類專門用於統計詞頻使用，Node則用於構造huffman樹，由於兩者使用的key不同，前者是word的字典序
//後者是詞頻，於是使用了兩個類來實現。
class huffman
{
public:
huffman();
template<typename entry>
friend bool binarysearch(entry list[wordnum],entry target,long bottom,long top,long &position);
template<typename entry>
friend void buidheap(entry a[wordnum], long number);
template<typename entry>
friend void heapify(entry a[wordnum], long high, long low);
template<typename entry>
friend void swap(entry a[wordnum], long i, long j);
bool Stat();
void Encode();
bool Decode(char code[]);
Node update(long end);
void produce_code();
void Inorder(Node *current, char currentcode[], long &num);
protected:
private:
Node SortedNode[wordnum];//從中產生huffman樹
char NodeCode[wordnum][wordnum/10];//相應編碼
Node root;
bool sign;//用於標記是否已經建立了huffman樹
long n;//葉子節點個數
};
huffman::huffman()
{
sign = false;
}
//二分用於統計詞頻
template<typename entry>
bool binarysearch(entry list[wordnum], entry target, long bottom, long top, long &position)
{
while(bottom <= top)
{
position = (bottom + top)/2;
if(list[position] < target)
bottom = position + 1;
else if(list[position] > target)
top = position - 1;
else
return true;
}
return false;
}
//建立最小堆及調整為最小堆
template<typename entry>
void swap(entry a[wordnum], long i, long j)
{
entry s;
s = a[i];
a[i] = a[j];
a[j] = s;
}
template<typename entry>
void buidheap(entry a[wordnum], long number)
{
long i ,j;
for(i = number/2; i >= 1; i--)
{
j = i;
while(j <= number/2)
{
if(a[j] > a[2*j] || (a[j] > a[2*j + 1] && 2*j + 1 <= number))
{
if(a[2*j] > a[2*j + 1] && 2*j + 1 <= number)
{
swap(a, j, 2*j+1);
j = 2*j + 1;
}
else
{
swap(a, j ,2*j);
j = 2*j;
}
}
else
break;
}
}
}
template<typename entry>
void heapify(entry a[wordnum], long high, long low)
{
long j = low;
while(j <= high/2)
{
if(a[j] > a[2*j] && a[j] > a[2*j + 1])
{
if(a[2*j] > a[2*j + 1] && 2*j + 1 <= high)
{
swap(a, j, 2*j+1);
j = 2*j + 1;
}
else if(2*j <= high)
{
swap(a, j, 2*j);
j = 2*j;
}
}
else if(a[j] <= a[2*j] && a[j] > a[2*j + 1] && 2*j + 1 <= high)
{
swap(a, j, 2*j+1);
j = 2*j + 1;
}
else if(a[j] <= a[2*j + 1] && a[j] > a[2*j] && 2*j <= high)
{
swap(a, j, 2*j);
j = 2*j;
}
else
break;
}
}
//詞頻統計函數Stat()
bool huffman::Stat()
{
long i,position;
char p[wordmax],*get;
str s[wordnum],current;
n = 0;
while(gets(p) != NULL && strcmp(p,"@") != 0)
{
get = strtok(p," ,.!/-:;?");
while(get != NULL)
{
current = get;
if(binarysearch(s,current,0,n,position) == true && n < wordnum - 1)
s[position] ++;
else
{
n ++;
if(n < wordnum - 1)
{
if(s[position] < current && current.getfre() < s[position].getfre())
position ++;
for(i = n; i >= position; i --)
s[i+1] = s[i];
s[position] = current;
s[position] ++;
}
}
get = strtok(NULL," ,.!/-:;?");
}
}
for(i = 1; i <= n && i < wordnum; i ++)
SortedNode[i] = s[i-1];
if(n < wordnum)
return true;
else
{
n = wordnum - 1;
return false;
}
}
//建立huffman樹函數
void huffman::Encode()
{
int i;
sign = true;
buidheap(SortedNode,n);
for(i = 1; i < n; i ++)
root = update(n-i+1);
}
Node huffman::update(long end)
{
Node *p,*q;
Node newNode;
p = new Node;
q = new Node;
*p = SortedNode[1];
swap(SortedNode,1,end);
heapify(SortedNode,end-1,1);//取出了壹個最小元，然後將堆進行了調整
*q = SortedNode[1];
newNode = *p + *q;
SortedNode[1] = newNode;
heapify(SortedNode,end-1,1);//又取出最小元，並且把新節點賦為SortedNode[1]，調整了堆
return SortedNode[1];
}
//解碼函數
bool huffman::Decode(char code[codemax])
{
int i;
Node *find = &root;
Node *l = NULL,*r = NULL;
bool flag = true;
if(sign == true)
{
for(i = 0; code[i] != '\0' && flag == true; i ++)
{
l = find->leftp();
r = find->rightp();
if(code[i] == '0' && l != NULL)
find = l;
else if(code[i] == '1' && r != NULL)
find = r;
else flag = false;
if(find->leftp() == NULL && find->rightp() == NULL)
{
printf("%s ",find->getword(find));
find = &root;
}
}
if(!((find->leftp() == NULL && find->rightp() == NULL) || find == &root))
{
cout << "There are some wrong codes in th input!" << endl;
flag = false;
}
}
else
flag = false;
return flag;
}
void huffman::Inorder(Node *current, char currentcode[], long &num)
{
Node *l, *r;
char cl[code_len], cr[code_len];
if(current != NULL)
{
l = current->leftp();
r = current->rightp();
strcpy(cl,currentcode);
strcat(cl,"0");
strcpy(cr,currentcode);
strcat(cr,"1");
Inorder(l, cl, num);
if(l == NULL && r == NULL)
{
SortedNode[num] = *current;
strcpy(NodeCode[num],currentcode);
num ++;
}
Inorder(r, cr, num);
}
}
void huffman::produce_code()//利用中序遍歷來得到相應的編碼
{
char current[code_len] = "";
long num = 1;
Inorder(&root, current,num);
for(long i = 1; i <= n; i ++)
{
cout << SortedNode[i].getword(&SortedNode[i]) << "----" << NodeCode[i]<<" " ;
if(i%3 == 0) cout << endl;
}
}
int main()
{
huffman test;
char code[codemax];
char order;
cout << "顯示編碼(Show)" << " "<< "解碼(Decode)" << " " <<"退出(Quit)" << endl;
cout << "Input the passage, to end with a single @ in a single line:" << endl;
test.Stat();
test.Encode();
cout << "Encoded!" << endl;
while(cin >> order)
{
if(order == 's' || order == 'S')
{
test.produce_code();
cout << "Produced!" << endl;
}
else if(order == 'd' || order == 'D')
{
cout << "Input the codes:" << endl;
cin >> code;
while(test.Decode(code))
cin >> code;
}
else if(order == 'q' || order == 'Q')
break;
}
return 0;
}