#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define MAXSIZE 100  //所能編譯字符最大個(gè)數(shù)
#define NULL 0
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define OK 1
#define INFINITY  1000000 //最大權(quán)值

typedef char TElemType;
typedef int  Status;
typedef char** HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表
typedef char* huffmanCode;



struct Data{
 TElemType  data;
 int w;//權(quán)值
};





typedef struct {
 TElemType data ;//儲(chǔ)存信息字符類型
 unsigned int weight;//權(quán)值
 unsigned int parent, lchild, rchild;//左右孩子及雙親儲(chǔ)存位置
} HTNode, *HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹


void    InitData(struct Data *m,int n){
 m=(struct Data*)malloc((n+1)*sizeof(Data));
 for( int i=1;i<=n;++i){
  m[i].w=0;
   m[i].data=NULL;
 }
}


//定義 Select函數(shù)
void Select(HuffmanTree HT,int n,int &s1,int &s2){

	int i;
	int k1=INFINITY ;//始終記錄較小的權(quán)值
	for( i=n;i>=1;--i){
		if(!HT[i].parent){
			if(HT[i].weight<=k1) {
				s1=i;
				k1=HT[i].weight;
				//printf("%d",s1);
			}//if
		}//if
	}//for

	//printf("\n");


    int k2=INFINITY ;//始終記錄較小的權(quán)值
	for(int j=1;j<=n;++j){
		if(!HT[j].parent&&j!=s1){
			if(HT[j].weight<=k2) {
				k2=HT[j].weight;
				s2=j;
				//printf("%d",s2);
			}
		}
	}
}




Status Huffmacoding( HuffmanTree &HT,HuffmanCode &HC,struct Data  w[],  int n ){
 //w存放n個(gè)字符的權(quán)值，構(gòu)造赫夫曼樹HT，并求出n個(gè)字符的編碼HC
	int m,i,s1,s2;
    HuffmanTree  p;
    if (n<=1) return ERROR;
    m=2*n-1; //需2*n-1個(gè)節(jié)點(diǎn)儲(chǔ)存結(jié)點(diǎn)信息及結(jié)點(diǎn)之間的關(guān)系
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號(hào)單元未用 
    for (p=HT+1, i=1; i<=n; ++i,++p){//初始化貯存n個(gè)字符的結(jié)點(diǎn)
		p->data = w[i].data;
	    p->weight=w[i].w;
		p->parent=0;
	    p->lchild=0;
		p->rchild=0;
	}
    for (; i<=m;++i,++p){ //初始化其余的儲(chǔ)存節(jié)點(diǎn)關(guān)系的n-1個(gè)結(jié)點(diǎn)
		p->data = NULL;
		p->weight=0;
	    p->parent=0;
		p->lchild=0;
	    p->rchild=0;
	}

 //開始構(gòu)造赫夫曼樹
 for (i=n+1; i<=m; ++i) {
 //在HT[1...i-1]選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)為s1和s2
 Select(HT,i-1,s1,s2);
 //printf("%d,%d",s1,s2);
 HT[s1].parent=i; HT[s2].parent=i;
 HT[i].lchild=s1;  HT[i].rchild=s2;
 HT[i].weight=HT[s1].weight+HT[s2].weight;
    } //for 
 //從葉子到根逆向求每個(gè)字符的赫夫曼編碼
 HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個(gè)字符編碼的頭指針向量
    char*  cd;
	int    f;
    cd = (char*)malloc(n*sizeof(char));//分配求編碼的工作空間
    cd[n-1]='\0';   //編碼結(jié)束符            
    for (i=1; i<=n; i++)  {               //逐個(gè)字符求編碼
 int start = n-1 ;//編碼結(jié)束符位置，最深的一個(gè)葉子結(jié)點(diǎn)需n-1個(gè)編碼
 int c=i; 
 while (f=HT[c].parent) {
     if (HT[f].lchild==c) cd[--start]='0';
     else cd[--start] = '1';
     c=f; 
 } //while
 HC[i] = (char*)malloc((n-start)*sizeof(char));//為第i個(gè)字符編碼分配 空間
 strcpy(HC[i],&cd[start]);  //從cd復(fù)制編碼到HC
    } 
    free(cd);   //釋放工作空間  
} //HuffmanCoding


//譯碼函數(shù) 
Status hfDecoding( HuffmanTree HT,char * cd,char *ccd,int n){
 int i=0;
 int m=2*n-1;//根節(jié)點(diǎn)位置
 int k=0;//記錄ccd中位置
 int p=m;
 ccd=(char*)malloc(256*sizeof(char));//為譯碼申請(qǐng)存儲(chǔ)空間
 int temp=TRUE;//結(jié)束循環(huán)標(biāo)志
 while(temp){
	 if(!HT[p].lchild && !HT[p].rchild ) {
		 ccd[k++]=HT[p].data;  // 將譯出碼保存到ccd
		 p=m;//使其又從根結(jié)點(diǎn)尋找]
		 if(cd[i]=='\0') temp=FALSE;//跳出循環(huán)
	 }//if
	 else {	if(cd[i]=='\0') {
		 printf("給出譯碼錯(cuò)誤！");
		 return ERROR;
	 }//當(dāng)字符串為空或者當(dāng)最后的數(shù)據(jù)串不能組成一個(gè)字母
	   if(((cd[i]=='0') && !HT[p].lchild)||((cd[i]=='1') && !HT[p].rchild)) {
		 printf("給出譯碼錯(cuò)誤！");
		 return ERROR; 
	   }//給出的碼串不正確，不能譯碼。
				if (cd[i]=='0') p=HT[p].lchild ;
				else p=HT[p].rchild;
				i++;
	 }//else
 }//while
	 ccd[k]='\0';//
	 printf("譯碼為：%s",ccd);
	  return OK;	 }




//定義main函數(shù)
void main(){
 int n;// 儲(chǔ)存字符個(gè)數(shù)
  printf("用戶需編譯的字符個(gè)數(shù)為:");
  scanf("%d",&n);
  printf("請(qǐng)逐個(gè)輸入字符及權(quán)值，并以逗號(hào)隔開 ");
     struct Data M[MAXSIZE];
     InitData(M,n);	
	 printf("\n");
  for(int i=1;i<=n;i++){
	 
   printf("輸入第%d個(gè)數(shù)據(jù):",i) ;
   fflush(stdin);//清除緩沖區(qū)數(shù)據(jù)
 
   scanf("%c,%d",&M[i].data,&M[i].w);

  }
  HuffmanTree HT;
  HuffmanCode HC;
  Huffmacoding(HT,HC,M,n);
  printf("sign------weight------parent------lchild------rchild");
  printf("\n");
  for(int j=1;j<=2*n-1;++j){
  printf("%-12c%-13d%-13d%-13d%-13d",HT[j].data,HT[j].weight,
	  HT[j].parent,HT[j].lchild,HT[j].rchild);
      printf("\n");
  }
  printf("\n");
  printf("各個(gè)字符赫夫曼編碼為:\n");
  for(j=1;j<=n;++j){
	  printf("%c:  %s\n",HT[j].data,HC[j]);
}
printf("請(qǐng)用戶輸入需譯碼的數(shù)據(jù)串：");
  char cd[100];
  char *p;
  p=cd;
  scanf("%s",p);
  char *ccd;//儲(chǔ)存譯碼
hfDecoding(HT,p,ccd,n);

 

//  scanf("%s",&cd);
//  hfDecoding(HT,cd,ccd,n);
}