// 赫夫曼.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream> 
#include <string> 
using namespace std; 
int a[100]; // 用來存放編碼的數組 
int maxsize(0); // 用來記錄編碼的長度 
static int count; // 用來記錄字符的長度 
int number(0); //存放字符串的長度 
class node // 存放字符和字符頻率 
{ 
public: 
int sign; 
char ch; 
int frequence; 
node():frequence(0),sign(0){} 
node(char x,int f=0){ch=x;frequence=f;} 
operator =(node n){ch=n.ch;frequence=n.frequence;} 
}; 


int len(char ch[])// 用來求字符串的長度 
{ 
int i(0),num(0); 
while(ch[i]!=NULL) 
{ 
num++; 
i++; 
} 
number=num; 
return num; 
} 
//=------------------------------------------- 

//--------------------------------------------------以下是編碼類------------------------------------- 

//-------------------------------------------------- 
class hufftree; 

class huffnode 
{friend class hufftree; 
public: 
huffnode *next,*leftchild,*rightchild,*parent; 
int code[100]; 
int data; 
char ch; 
huffnode(huffnode * pnext=NULL,huffnode*left=NULL,huffnode*right=NULL) 
{next=pnext;leftchild=left;rightchild=right;} 


huffnode(int item,char a,huffnode *pnext=NULL,huffnode*left=NULL,huffnode*right=NULL) 
{data=item;next=pnext;ch=a;leftchild=left;rightchild=right;} 
}; 





class hufftree 
{ 

public: 
node array[100]; 
huffnode *head,*listhead,*huffroot; 


hufftree() 
{huffnode *newnode=new huffnode(); 

head=newnode; 
head->next=NULL;} 



void Insert(int x,char a)//===--------------------------插入函數------------------------- 
{ 
huffnode *p,*pre; 
p=head->next; 
if(p==NULL) 
{ 
huffnode *newnode=new huffnode(x,a,NULL,NULL,NULL); 
head->next=newnode; 
huffroot=newnode; 

} 
else 
{ 
huffnode *newnode=new huffnode(x,a,NULL,NULL,NULL); 
while(p) 
{ 
pre=p; 
p=p->next; 
} 
pre->next=newnode; 
huffroot=newnode; 
} 

} 



void connect(huffnode *p) // 將所有的HUFFMAN樹的葉子結點鏈成一個單鏈表 
{ 
huffnode *t=head,*pre; 
while(t) 
{ 
pre=t; 
t=t->next; 
} 
pre->next=p; 
p->next=NULL; 
} 


huffnode * Min()/// -------------------------------求頻率最小的那個接點 
{ 
if(head->next==NULL){cout<<"No element!.."<<endl;} 
else 

{ 

int min(1000); 
huffnode *p=head->next; 
huffnode *t; 
while(p!=NULL) 
{ 
if(min>p->data) 
{ 
min=p->data; 
t=p; 

} 
p=p->next; 
} 


delet(t); 

return t; 
} 
} 


void Frequence(char line[])// 求每個字符的頻率 
{ 
char ch[100]; 
for(int x=0;x<len(ch);x++) 
{ 
ch[x]=line[x]; 
} 
int j(0),length(0); 
int i,k; 

int size=len(ch); 

for(k=0;k<size;k++) 
{ 
if(ch[k]!=NULL) 
{ 
array[j].ch=ch[k]; 
for( i=0;i<size;i++) 
{ 
if(ch[i]!=NULL) 
{ 
if(array[j].ch==ch[i]) 
{ 
++array[j].frequence; 
ch[i]=NULL; 
} 
} 
} 
j++; 
} 
} 
length=j; 
count=length; 
cout<<"length="<<length<<endl; 
for(i=0;i<length;i++) 
{ 
cout<<"The"<<i<<"th char is "<<array[i].ch<<" The frequence is "<<array[i].frequence<<endl; 

} 

} 
void Sethufftree()//--------------------------------造樹problem---------------------------------------- 
{ 
huffnode* pt=head->next; 
while(pt) 
{ 
huffnode *p=Min(); 
huffnode *t=Min(); 
if(t==NULL) 
{ 
Insert((p->data),NULL); 
} 

else 
{ 
Insert((p->data+t->data),NULL); 
} 
huffroot->leftchild=p; 
huffroot->rightchild=t; 
p->parent=huffroot; 
if(t!=NULL) 
{ 
t->parent=huffroot; 
} 
pt=head->next->next; 
if(pt==NULL) 
{ 
huffroot->parent=pt; 
head->next=NULL; 
} 
} 
} 


void Inorder(huffnode *r)//---------------------------huffmantree 的中序遍歷------------------- 
{ 


if(r!=NULL) 
{ 
Inorder(r->leftchild); 
cout<<r->data; 
if(r->leftchild==NULL && r->rightchild==NULL) 
{ 


connect(r); 

cout<<r->ch; 
} 
cout<<endl; 
Inorder(r->rightchild); 
} 
} 

void output()//-------------------------------------輸出函數----------------------------------- 
{ 
huffnode *p=head->next;//-----------------------------有頭接點-------------------------------------- 
while(p) 
{ 
cout<<p->ch<<" "<<p->data<<endl; 
p=p->next; 
} 
} 


void delet(huffnode * p) //-----------------------這里只斷開指針,并沒有真正的刪除------------- 
{ 
huffnode *t=head->next,*pre=head; 
if(t==NULL){cout<<"All of the elements have been deleted!.."<<endl;exit(1);} 
else 
{ 
while(t!=p) 
{ 
pre=t; 

t=t->next; 

} 
pre->next=p->next; 
} 
} 



void huffcode() // 構造huffman編碼 
{ 
huffnode *p=head->next,*t; 

while(p!=NULL) 
{ int i=99; 
t=p; 

while(t->parent!=NULL) 
{ 
if(t->parent->leftchild==t) 
{ 
p->code[i]=0; 
i--; 
} 
else 
{ 
p->code[i]=1; 
i--; 
} 
t=t->parent; 
} 
p=p->next; 

} 

} 

void outputcode()//-----------------------------------------------輸出編碼-------------------- 
{ 
huffnode *p=head->next; 
int j(0); 
while(p) 
{ 
cout<<"\nThe char "<<p->ch<<" 's huffman code is "; 
for(int i=0;i<100;i++) 
{ 
if(p->code[i]==0 || p->code[i]==1) 
{ 
cout<<p->code[i]; 
a[j]=p->code[i]; 
j++; 
} 

} 

p=p->next; 
} 
maxsize=j; 
} 


void sortcode() 
{ 
for(int m=0;m<count;m++) 
{ 
huffnode *p=head->next; 
while(p) 
{ 

if(array[m].ch==p->ch) 
{ 
cout<<"\nThe char "<<p->ch<<" 's huffman code is "; 
for(int i=0;i<100;i++) 
{ 
if(p->code[i]==0 || p->code[i]==1) 
{ 
cout<<p->code[i]; 
} 
} 
} 
p=p->next; 
} 
} 
} 

void Incode(char cha[]) 
{ 
int j(0); 
cout<<"NUmber "<<len(cha)<<endl; 
for(int k=0;k<number;k++) 
{cout<<cha[k];} 



for(int m=0;m<number;m++) 
{ 
huffnode *p=head->next; 
while(p) 
{ 

if(cha[m]==p->ch) 
{ 
cout<<"\nThe char "<<p->ch<<" 's huffman code is "; 
for(int i=0;i<100;i++) 
{ 
if(p->code[i]==0 || p->code[i]==1) 
{ 
cout<<p->code[i]; 
a[j]=p->code[i]; 
j++; 
} 
} 
} 
p=p->next; 
} 
} 
maxsize=j; 

} 
void transcode() // 進行譯碼 
{ 
huffnode *p=huffroot; 
int i(0); 
cout<<"\nAfter translating, the code is: "; 
while(p) 
{ 
if(a[i]==0) 
{ 
p=p->leftchild; 
} 
else 
{ 
p=p->rightchild; 
} 
if(p->leftchild==NULL && p->rightchild==NULL) 
{ 
cout<<p->ch; 
p=huffroot; 

} 
i++; 
if(i>=maxsize)break; 
} 
} 


}; 








void main() //主函數 
{ 
char ch[100]; 
cout<<"Input the char "; 
cin.getline(ch,sizeof(ch)); 
hufftree list ; 
list.Frequence(ch); 
for( int i=0;i<count;i++) 
{ 

list.Insert(list.array[i].frequence,list.array[i].ch); 
} 


list.output(); 

cout<<"Finish output!...."<<endl; 

list.Sethufftree(); 
list.Inorder(list.huffroot); 

cout<<"This is the result of after connecting"<<endl; 
list.output(); 
list.huffcode(); 
list.sortcode(); 
//cin.getline(ch,sizeof(ch)); 
list.Incode(ch); 
list.transcode(); 
cout<<endl; 
for(int j=0;j<=maxsize;j++) 
cout<<a[j]; 

cout<<endl; 

cout<<"There are "<<__LINE__<<" lines in this programm"<<endl; 
}