/* 哈夫曼樹編碼壓縮程序 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h> 
#define MAX_SINGLECODE_LEN 10 //單個(gè)字符最大碼長(zhǎng)
#define MAX_STRING_LEN 1000 //要編碼的字符串的最大長(zhǎng)度
#define MAX_CODESTRING_LEN 10000 //產(chǎn)生的二進(jìn)制碼的最大長(zhǎng)度
#define MAX_WORDS 1000 //要編碼的字符串中字符種數(shù)最大值
#define END_TREE 30000 //樹部分存儲(chǔ)的結(jié)束符
#define PATH_LEN 50 //路徑串最大長(zhǎng)度 
/*****哈夫曼樹結(jié)構(gòu)定義*****/
typedef struct Huffmantree
{
char ch; //字符部分
int weight; //結(jié)點(diǎn)權(quán)值
int mark; //標(biāo)記是否加入樹中
struct Huffmantree *parent,*lchild,*rchild,*next;
}HTNode,*LinkTree; 
/*****編碼字典結(jié)構(gòu)定義*****/
typedef struct
{
char ch; //字符部分
char code[MAX_SINGLECODE_LEN]; //編碼部分
}CodeDictionary; 
/*********函數(shù)聲明*********/
LinkTree setWeight(char *);
LinkTree sortNode(LinkTree);
LinkTree createHTree(LinkTree);
void codeHTree(LinkTree,CodeDictionary *);
void decodeHTree(LinkTree,char *,char *);
void deleteNode(LinkTree);
void compressString(char *s,CodeDictionary *,char *);
void readFile(char *);
void writeFile(char *);
void readCode(LinkTree,char *);
void writeCode(LinkTree,char *);
void menu(); 
/**
*主函數(shù)
*輸入：空
*返回：空
*/
void main(void)
{
char choice; //菜單選擇變量
char string[MAX_STRING_LEN]; //保存從文件中讀取的內(nèi)容
LinkTree temp; //保存賦了權(quán)值的表
LinkTree ht; //保存排序后的表
LinkTree htcopy,tempcopy; //表備份
LinkTree htree; //保存哈夫曼樹
LinkTree ptr=NULL;
CodeDictionary codedictionary[MAX_WORDS];//編碼字典
char codestring[MAX_CODESTRING_LEN]; //保存0-1形的代碼串 
char codestring2[MAX_CODESTRING_LEN];//保存0-1形的代碼串
LinkTree ht2; //保存讀取的樹
LinkTree htree2; //保存排序后的表
char filestring[MAX_STRING_LEN]; //解碼后要寫入文件中的內(nèi)容 
if((ht2=(LinkTree)malloc(sizeof(HTNode)))==NULL)//創(chuàng)建鏈表的頭結(jié)點(diǎn)
{
printf("內(nèi)存不足！");
getch();
exit(0);
}
ht2->next=NULL; 
while(1)
{
menu(); //調(diào)入主菜單
choice=getch(); //讀入用戶選項(xiàng)
switch(choice) //判斷用戶選擇
{
case 'c':
case 'C':
printf("\n您選擇了壓縮文件模式:\n\n");
readFile(string); //讀取要編碼的文件（字符串）
temp=setWeight(string); //得到有權(quán)值的表
tempcopy=setWeight(string);
ht=sortNode(temp); //按權(quán)值排序后的表
htcopy=sortNode(tempcopy); //用于記錄解碼樹
htree=createHTree(ht); //得到哈夫曼樹
codeHTree(htree,codedictionary);//哈夫曼編碼
compressString(string,codedictionary,codestring);//壓縮為0-1碼
writeCode(htcopy,codestring); //將解碼樹和0-1碼保存 
deleteNode(htree); //釋放空間*/
break;
case 'u':
case 'U':
printf("您選擇了解壓縮文件模式:\n\n");
readCode(ht2,codestring2); //讀取要解碼的0-1碼
htree2=createHTree(ht2); //得到哈夫曼樹
codeHTree(htree2,codedictionary);//哈夫曼編碼
decodeHTree(htree2,codestring2,filestring); //解碼
writeFile(filestring); //將解碼文件保存
deleteNode(htree2); //釋放空間
break;
case 'e':
case 'E':
exit(0); //退出程序
}
}
}/**
*整理輸入的字符串，求出每個(gè)字符在數(shù)組中出現(xiàn)的次數(shù)，作為權(quán)值
*輸入：（字符型指針）字符串的地址
*返回：（哈夫曼結(jié)點(diǎn)指針）含權(quán)鏈表的首地址
*/
LinkTree setWeight(char *string)
{
int i=0; //文件字符串下標(biāo)
LinkTree tree; //頭指針
LinkTree ptr,beforeptr; //創(chuàng)建指針與其前驅(qū)
HTNode *node;

if((tree=(LinkTree)malloc(sizeof(HTNode)))==NULL)//創(chuàng)建鏈表的頭結(jié)點(diǎn)
return NULL;
tree->next=NULL;

for(i=0;string[i]!='\0';i++)
{ 
ptr=tree;
beforeptr=tree;

if((node=(HTNode *)malloc(sizeof(HTNode)))==NULL)
return NULL;
node->next=NULL;
node->parent=NULL;
node->lchild=NULL;
node->rchild=NULL;
node->mark=0;
node->ch=string[i];
node->weight=1;

if(tree->next==NULL) //如果是第一個(gè)非頭結(jié)點(diǎn)
tree->next=node;
else
{ 
ptr=tree->next;
while(ptr&&ptr->ch!=node->ch) //查找相同字符
{ 
ptr=ptr->next;
beforeptr=beforeptr->next;
}
if(ptr&&ptr->ch==node->ch) //如果鏈表中某結(jié)點(diǎn)的字符與新結(jié)點(diǎn)的字符相同
{ 
ptr->weight++; //將該結(jié)點(diǎn)的權(quán)加一 
free(node); 
}
else //將新結(jié)點(diǎn)插入鏈表后
{ 
node->next=beforeptr->next;
beforeptr->next=node;
}
}
}
return tree; //返回頭指針
} 
/**
*將整理完的字符串（帶權(quán)鏈表）按出現(xiàn)次數(shù)從小到大的順序排列
*輸入：（哈夫曼結(jié)點(diǎn)指針）要排序的表頭地址
*返回：（哈夫曼結(jié)點(diǎn)指針）排序后的表頭地址
*/
LinkTree sortNode(LinkTree tree)
{ 
LinkTree head; //頭指針
LinkTree ph,beforeph; //創(chuàng)建指針及其前驅(qū)
LinkTree pt;

if((head=(LinkTree)malloc(sizeof(HTNode)))==NULL)//創(chuàng)建新鏈表的頭結(jié)點(diǎn)
return NULL;
head->next=NULL;

ph=head;
beforeph=head;

while(tree->next)
{ 
pt=tree->next; //取被*作鏈表的頭結(jié)點(diǎn)
tree->next=pt->next;
pt->next=NULL;

ph=head->next;
beforeph=head;

if(head->next==NULL)
head->next=pt; //創(chuàng)建當(dāng)前*作鏈表頭結(jié)點(diǎn)
else
{
while(ph&&ph->weight<pt->weight) //將被*作結(jié)點(diǎn)插入相應(yīng)位置
{ 
ph=ph->next;
beforeph=beforeph->next;
}
pt->next=beforeph->next;
beforeph->next=pt;
}
}
free(tree);
return head; //返回排序后的頭指針
} 
/**
*用排完序的字符串建立哈夫曼樹
*輸入：（哈夫曼結(jié)點(diǎn)指針）要建立哈夫曼樹的地址
*返回：（哈夫曼結(jié)點(diǎn)指針）建立后的哈夫曼樹地址
*/
LinkTree createHTree(LinkTree tree)
{ 
LinkTree p,q,beforep;
HTNode *newnode;

for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next)
//p、q初值為頭結(jié)點(diǎn)后的兩個(gè)結(jié)點(diǎn)，即最小權(quán)結(jié)點(diǎn)
{
tree->next=q->next;
q->next=NULL;
p->next=NULL;

if((newnode=(HTNode *)malloc(sizeof(HTNode)))==NULL)
//申請(qǐng)新結(jié)點(diǎn)作為哈夫曼樹的中間結(jié)點(diǎn)
return NULL;
newnode->next=NULL;
newnode->mark=0;

newnode->lchild=p; //取鏈表頭結(jié)點(diǎn)后的兩個(gè)結(jié)點(diǎn)作為新結(jié)點(diǎn)的左、右孩子
newnode->rchild=q;
p->parent=newnode;
q->parent=newnode;
newnode->weight=p->weight+q->weight; //權(quán)值相加

p=tree->next;
beforep=tree;

if(p!=NULL&&p->weight>=newnode->weight)
{
newnode->next=beforep->next; //將新結(jié)點(diǎn)插入原鏈表的相應(yīng)位置
beforep->next=newnode; 
}
else
{
while(p!=NULL&&p->weight<newnode->weight)
{ 
p=p->next;
beforep=beforep->next;
}
newnode->next=beforep->next;
beforep->next=newnode;
}
}
return (tree->next);
} 
/**
*對(duì)哈夫曼樹進(jìn)行編碼
*輸入：（哈夫曼結(jié)點(diǎn)指針）要編碼的哈夫曼樹地址
* （編碼字典類型指針）存放字典的首地址
*返回：空
*/
void codeHTree(LinkTree tree,CodeDictionary *codedictionary)
{ 
int index=0,k=0;
char code[MAX_SINGLECODE_LEN]; //用于統(tǒng)計(jì)每個(gè)字符的哈夫曼編碼
LinkTree ptr=tree; //從樹的根結(jié)點(diǎn)開始 
if(ptr==NULL)
{
printf("要壓縮的文件是空的!\n");
exit(0);
}
else
{
while(ptr->lchild&&ptr->rchild&&ptr->mark==0)
{
while(ptr->lchild&&ptr->lchild->mark==0)
{
code[index++]='0'; //左支路編碼為0
ptr=ptr->lchild;
if(!ptr->lchild&&!ptr->rchild) //如果沒有左右孩子，即葉子結(jié)點(diǎn)
{
ptr->mark=1; //作標(biāo)記，表明該字符已被編碼
code[index]='\0'; //編碼0-1字符串結(jié)束
codedictionary[k].ch=ptr->ch;//給字典賦字符值
for(index=0;code[index]!='\0';index++)
codedictionary[k].code[index]=code[index];//給字典賦碼值
codedictionary[k].code[index]='\0';
k++;
ptr=tree; //指針復(fù)位
index=0;
}
}
if(ptr->rchild&&ptr->rchild->mark==0)
{
ptr=ptr->rchild;
code[index++]='1'; //右支路編碼為1
}
if(!ptr->lchild&&!ptr->rchild) //如果沒有左右孩子，即葉子結(jié)點(diǎn)
{
ptr->mark=1;
code[index++]='\0';
codedictionary[k].ch=ptr->ch; //給字典賦字符值
for(index=0;code[index]!='\0';index++)
codedictionary[k].code[index]=code[index];//給字典賦碼值
codedictionary[k].code[index]='\0';
k++;
ptr=tree;
index=0;
}
if(ptr->lchild->mark==1&&ptr->rchild->mark==1)//如果左右孩子都已標(biāo)記
{
ptr->mark=1;
ptr=tree;
index=0;
}
}
}
printf("\n");
} 
/**
*解碼，即將0-1碼轉(zhuǎn)化為字符串
*輸入：（哈夫曼結(jié)點(diǎn)指針）編碼樹的地址
* （字符型指針）要解碼的0-1字符串地址
* （字符型指針）解碼后的字符串地址
*返回：空
*/
void decodeHTree(LinkTree tree,char *code,char *filestring)
{ 
int i=0,j=0,k=0;
char *char0_1;
LinkTree ptr=tree;
char0_1=(char *)malloc(MAX_SINGLECODE_LEN); //此數(shù)組用于統(tǒng)計(jì)輸入的0-1序列

printf("預(yù)覽解壓后的字符：\n");
for(j=0,ptr=tree;code[i]!='\0'&&ptr->lchild&&ptr->rchild;j=0,ptr=tree)
{
for(j=0;code[i]!='\0'&&ptr->lchild&&ptr->rchild;j++,i++)
{
if(code[i]=='0')
{ 
ptr=ptr->lchild;
char0_1[j]='0'; 
}
if(code[i]=='1')
{
ptr=ptr->rchild;
char0_1[j]='1';
}
} 
if(!ptr->lchild&&!ptr->rchild)
{
printf("%c",ptr->ch); //顯示解壓后的字符
filestring[k++]=ptr->ch; //將字符逐一保存到字符串里
}
if(code[i]=='\0'&&ptr->lchild&&ptr->rchild)
{ 
char0_1[j]='\0';
printf("\n沒有與最后的幾個(gè)0-1序列：%s相匹配的字符!\n",char0_1);
return;
}
}
printf("\n\n");
filestring[k]='\0';
free(char0_1);
} 
/**
*釋放哈夫曼樹所占用的空間
*輸入：（哈夫曼結(jié)點(diǎn)指針）要釋放的結(jié)點(diǎn)地址
*返回：空
*/
void deleteNode(LinkTree tree)
{ 
LinkTree ptr=tree;
if(ptr)
{ 
deleteNode(ptr->lchild);
deleteNode(ptr->rchild);
free(ptr);
}
} 
/**
*將整個(gè)字符串轉(zhuǎn)化為0-1的字符串
*輸入：（字符型指針）待轉(zhuǎn)化的字符串首地址
* （編碼字典類型指針）字典首地址
* （字符型指針）接收0-1碼串的首地址
*返回：空
*/
void compressString(char *string,CodeDictionary *codedictionary,char *codestring)
{
int i=0,j=0,k=0,m; 
while(string[i]) //整個(gè)文件字符串沒結(jié)束時(shí)
{
while(string[i]!=codedictionary[j].ch&&j<MAX_WORDS)
//找與對(duì)應(yīng)字符相同的字符
j++;
if(string[i]==codedictionary[j].ch) //如果找到與對(duì)應(yīng)字符相同的字符
for(m=0;codedictionary[j].code[m];m++,k++)
codestring[k]=codedictionary[j].code[m];
j=0; //字典復(fù)位
i++;
}
codestring[k]='\0';
} 
/**
*把指定文件讀到字符串中
*輸入：（字符型指針）待接收文件的字符串地址
*返回：空
*/
void readFile(char *string)
{
FILE *fp;
int i;
char ch; //記錄讀入的字符
char path[PATH_LEN]; //文本文件的讀路徑 
printf("請(qǐng)輸入要壓縮的文本文件地址：（無需擴(kuò)展名）");
gets(path);
if((fp=fopen(strcat(path,".txt"),"r"))==NULL)
{
printf("\n路徑不正確！\n");
getch();
return;
} 
ch=fgetc(fp);
for(i=0;ch!=EOF;i++)
{
string[i]=ch;
ch=fgetc(fp);
}
string[i]='\0';
fclose(fp);
} 
/**
*保存編碼后的解碼樹和字符串
*輸入：（哈夫曼結(jié)點(diǎn)指針）解碼樹的地址
* （字符型指針）要保存的0-1碼串首地址
*返回：空
*/
void writeCode(LinkTree tree,char *string)
{
FILE *fp;
int i;
int weight; //記錄寫入的權(quán)值
char ch; //記錄寫入的字符
LinkTree p;
char path[PATH_LEN]; //0-1碼文件的寫路徑 
printf("請(qǐng)輸入壓縮后的保存路徑及文件名：（無需擴(kuò)展名）");
gets(path);
if((fp=fopen(strcat(path,".yxy"),"w+"))==NULL)
{
printf("\n文件路徑出錯(cuò)！\n");
getch();
return;
}
p=tree->next; 
/*解碼樹部分寫入文件前部分*/
do
{
ch=p->ch;
weight=p->weight;
fprintf(fp,"%c%d",ch,weight);
p=p->next;
}while(p);
fprintf(fp,"%c%d",'^',END_TREE); 
fseek(fp,sizeof(char),1); //空出區(qū)分位

/*0-1碼寫入文件后部分*/
for(i=0;string[i];i++)
{
ch=string[i];
fputc(ch,fp);
}
printf("\n壓縮成功！\n");
getch();
fclose(fp);
} 
/**
*讀取編碼后的0-1字符串
*輸入：（哈夫曼結(jié)點(diǎn)指針）解碼樹的地址
* （字符型指針）要接收的0-1碼串首地址
*返回：空
*/
void readCode(LinkTree tree,char *string)
{ 
FILE *fp;
int i;
int weight; //記錄讀入的權(quán)值
char ch; //記錄讀入的字符
LinkTree ptr,beforeptr;
char path[PATH_LEN]; //0-1碼文件的讀路徑 
printf("請(qǐng)輸入要解壓的文件路徑及文件名：（無需擴(kuò)展名）");
gets(path);
if((fp=fopen(strcat(path,".yxy"),"r"))==NULL)
{
printf("\n文件路徑出錯(cuò)！\n");
getch();
return;
}
beforeptr=tree; 
/*從文件前部分讀出解碼樹*/
fscanf(fp,"%c%d",&ch,&weight);
while(weight!=END_TREE)
{
if((ptr=(LinkTree)malloc(sizeof(HTNode)))==NULL)
{
printf("內(nèi)存不足！");
getch();
exit(1); //錯(cuò)誤出口
}
ptr->ch=ch;
ptr->weight=weight;
ptr->lchild=NULL;
ptr->rchild=NULL;
ptr->parent=NULL;
ptr->mark=0;
beforeptr->next=ptr;
beforeptr=ptr;
fscanf(fp,"%c%d",&ch,&weight);
}
beforeptr->next=NULL; 
fseek(fp,sizeof(char),1); //文件指針定位

/*從文件后部分讀出0-1碼*/
ch=fgetc(fp);
for(i=0;ch!=EOF;i++)
{
string[i]=ch;
ch=fgetc(fp);
}
string[i]='\0';
fclose(fp);
} 
/**
*保存解碼后的文件
*輸入：（字符型指針）解碼后的字符串地址
*返回：空
*/
void writeFile(char *string)
{
FILE *fp;
char ch; //記錄寫入的字符
int i;
char path[PATH_LEN]; //文本文件的寫路徑 
printf("請(qǐng)輸入解壓后的保存路徑及文件名：（無需擴(kuò)展名）");
gets(path);
if((fp=fopen(strcat(path,".txt"),"w+"))==NULL)
{
printf("\n文件路徑出錯(cuò)！\n");
getch();
return;
} 
for(i=0;string[i];i++)
{
ch=string[i];
fputc(ch,fp);
}
printf("\n解壓成功！\n");
getch();
fclose(fp);
} 
/**
*顯示主菜單
*輸入：空
*返回：空
*/
void menu()
{
printf("\n\n\n\n\n\n");
printf("\t\t -----** 歡迎使用WINYXY壓縮工具 **-----");
printf("\n\n\n");
printf("\t\t\t\t<c> 壓 縮\n\n");
printf("\t\t\t\t<u> 解 壓\n\n");
printf("\t\t\t\t<e> 退 出\n\n");
printf("\n\n請(qǐng)按鍵選擇：\n");
printf("\n\n\n\n\n\n");
}