#include "iostream" 
#include "iomanip" 
#include "string" 
#include"fstream"
using namespace std; 

#define MAX 256 
typedef string *STR; 

void InputData(string &s); 
void DeCode(); 

typedef struct Huffnode { 
unsigned weight; //權值 字符出現頻率 
bool in; // 是否加入Huffman樹 
int lchild,rchild; 
void Set(unsigned &w,int lc=-1,int rc=-1,bool in = false ) { 
weight = w; 
lchild = lc; 
rchild = rc; 
in = in; 
} 

Huffnode() { weight=0; in = false;lchild=-1;rchild=-1;} 
} *HuffTree; 

void GetCode(HuffTree &nodes,int &k,STR &Code,string &str,int i,int leafNum,unsigned *Ind) { 
if (k<leafNum) { 
Code[Ind[k]] = str.substr (0,i); 
return; 
} 
str[i] = '0'; 
GetCode(nodes,nodes[k].lchild ,Code,str,i+1,leafNum,Ind); 
str[i] = '1'; 
GetCode(nodes,nodes[k].rchild ,Code,str,i+1,leafNum,Ind); 
} 

void GetMin(HuffTree &nodes,int n,int &min1,int &min2) { //得到兩個最小節點下標 
unsigned min; 
for(int k=0;k<2;k++) { 
min = 99999; 
int t = 0; 
for(int i=0;i<n;i++) { 
if(nodes[i].in ) continue; 
if(nodes[i].weight < min) { 
min = nodes[i].weight; 
t = i; 
} 
} 
nodes[t].in = true; 
if(k==0) min1 = t; 
else min2 = t; 
} 
} 

void MakeTree(HuffTree &Node,unsigned *Wei,int &Num) { 
int i; 
for(i=0;i<Num;i++) Node[i].Set(Wei[i]); 
for(i=Num;i<2*Num-1;i++) { 
int m1,m2; 
GetMin(Node,i,m1,m2); 
unsigned w = Node[m1].weight+Node[m2].weight ; 
Node[i].Set(w,m1,m2); 
} 
} 

void HaffmanCoding(string &In,STR &Code,int &N) { 
unsigned Weight[MAX] = {0},Ind[MAX] = {0},Wei[MAX]; 
int i,Num = 0; 
for(i=0;i<N;i++) Weight[(In[i]+256)%256]++; 
for(i=0;i<MAX;i++) { 
if (Weight[i]) { 
Ind[Num] = i; //記錄Everynode (0~Num-1)所存之字符代碼 
Wei[Num++] = Weight[i]; 
} 
} 
HuffTree Node = new Huffnode [2*Num-1]; 
MakeTree(Node,Wei,Num); 
Code = new string[MAX]; 
string str; str.resize (MAX); 
int nod = 2*Num-2; 
GetCode(Node,nod,Code,str,0,Num,Ind); 
cout<<endl<<"The Codes is:\n"<<endl; 
cout<<"字符總數:"<<Num<<endl; 
cout<<setw(10)<<"字符:"<<setw(10)<<"頻度:"<<endl; 
for(i=0;i<Num;i++) cout <<setw(10)<</*(char)*/Ind[i]<<setw(10)<<Wei[i]<<endl; 
cout<<"\n碼符:"<<endl; 
for(i=0;i<N;i++) cout<<Code[(In[i]+256)%256];//<<" "; 
cout<<endl<<endl; 
} 

void EnCode() { 
string Input; 
string *Code; 
InputData(Input); 
int N = Input.length (); 
HaffmanCoding(Input,Code,N); 
} 



void InputData(string &s) { 
fstream out;
out.open("file.txt");
if(!out){
	cerr<<"can't be open"<<endl;
}
else{
char c;
while (out); 
out.get(c); 
 
while (c!='\n') s+=c; 
}
getchar();
} 

////////////////////////////////////////////////////////////////////// 

void DeCode() { 
int num,i; 
cout<<"輸入出現的字符數:"<<endl; 
cin>>num; 
cout<<"輸入每個字符對應的數字代碼(0-255)及其頻度:\n" 
<<"格式: [代碼][空格][頻度]:\n"<<endl; 
unsigned *Ind = new unsigned[num]; 
unsigned *Wei = new unsigned[num]; 
for(i=0;i<num;i++) cin>>Ind[i]>>Wei[i]; 
HuffTree Node = new Huffnode [2*num-1]; 
MakeTree(Node,Wei,num); 
cout<<"Input The Code You Want to DeCode:"<<endl; 
cout<<"Please Input The Code You Want to DeCode:\nPress 'A' & 'Enter' to Start:"<<endl; 
while (cin.get ()!='A'); 
cin.get (); 
cout<<"Start Input!!:"<<endl; 
char c; 
int k=2*num-2; 
string Out; 
while ((c=cin.get ())!='.') { 
if(k<num) { 
char s = (char)Ind[k]; 
Out += s; 
k=2*num-2; 
} 
if(c=='0') k = Node[k].lchild ; 
else if(c=='1') k = Node[k].rchild ; 
} 
cout<<"解碼結果:\n"<<endl; 
cout<<Out; 
cout<<endl; 

} 









#include<iostream>

#include<fstream>
#include<string> 
#include<vector> 
#pragma warning (disable:4786) 
using namespace std; 
void main() 
{ 
int i,j,m,n,q,a[2000],c[1000]; 
m=n=0; 
char *p; 
vector<string> s; 
char save[2000],str[10000],len[10000]; 
string str1,str2,str3[2000];
cout<<"***************文章分析器*******************"<<endl;
	cout<<"*                                          *"<<endl;
	cout<<"*[1]統計單詞個數并求個數最多單詞           *"<<endl;
	cout<<"*                                          *"<<endl;
	cout<<"*[2]赫夫曼編碼譯碼                         *"<<endl;
	cout<<"*                                          *"<<endl;
	cout<<"********************************************"<<endl;
	if(cin.get ()=='1') {
fstream in;
in.open("file.txt");
if(!in){
	cerr<<"the file is not existed"<<endl; //判斷文件是否能打開
}

else {
	

	for(i=0;i<100;i++) 
a[i]=0; 

while(in) 
{ 
in.getline(str,200); 
str1=str; 
if(str1=="$") 
break; 
s.push_back(str1); 
} 
for(i=0;i<s.size();i++) 
str2=str2+s[i]+" "; 
str2=str2+"\0"; 
strcpy(len,str2.c_str ()); 
p=len; 
cout<<"測試結果為："<<endl; 
while(*p!='\0') 
{ 
memset(save,0,20); 
q=0; 
i=0; 
while(!(isalpha(*p))&&*p!='\0') 
p++; 


while(isalnum(*p)) 
{ 
save[i]=*p; 
i++; 
p++; 
} 
for(j=0;j<n;j++) 
if(!(strcmp(save,str3[j].c_str()))) 
{ 
a[j]++; 
q=1; 
break; 
} 
if(q==0&&*p!='\0') 
{ 
str3[n]=save; 
a[n]++; 
n++; 

} 



} 
int max=a[0]; 
for(i=0;i<n;i++) 
if(max<a[i]) 
max=a[i]; 
for(i=0;i<n;i++) 
{ 
if(max==a[i]) 
{ 
c[m]=i; 
m++; 
} 
} 
for(i=0;i<n;i++) 
cout<<str3[i]<<"\t"<<"\t"<<"出現次數為："<<a[i]<<endl; 
cout<<"在這篇短文中出現頻率最高的為："<<endl; 
for(i=0;i<m;i++) 
cout<<"★★★"<<str3[c[i]]<<"★★★"<<endl; 
cout<<endl<<"他們出現的次數為："<<max<<endl;
}

	}
	
else
{

cout<<endl<<"[3]--編碼\n[4]--譯碼\n"<<endl;
if(cin.get ()=='3') { 
EnCode();
getchar();
} 
else if(cin.get()==4) {

DeCode(); 
cout<<endl;}
else
getchar();
getchar(); 



} 

	
	
	getchar();
	getchar();


}