/* 課題[3]哈夫曼編碼實現文件的壓縮功能 */
/* */
/* */
/*========================================*/
#include<stdio.h> //包含頭文件
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#include<iostream.h>
#define MAX_SINGLECODE 10 //單個字符最大碼長
#define MAX_STRING 10000 //要編碼的字符串的最大長度
#define MAX_CODESTRING 50000 //產生的二進制碼的最大長度
#define MAX_WORDS 1000 //要編碼的字符串中字符種數最大值
#define END_TREE 30000 //樹部分存儲的結束符
#define PATH 50 //路徑的最大字符
/*======數據結構定義部分======*/
/*哈夫曼樹結構定義，其中的next域用於鏈表的操作*/
typedef struct Huffmantree
{
char ch; //字符部分
int weight; //結點權值
int mark; //標記是否加入樹中
struct Huffmantree *parent,*lchild,*rchild,*next;
}HTNode,*LinkTree;
/*****編碼字典結構定義*****/
typedef struct //ch為字符值，code[]為該字符的哈夫曼編碼
{
char ch; //字符部分
char code[MAX_SINGLECODE]; //編碼部分
}CodeDictionary;
/*======子函數======*/
/*===================壓縮功能實現部分=====================*/
/*功能：讀取.TXT文件並將其中的字符中保存到string[]中*/
void readFile(char *string)
{
FILE *fp;
int i;
char ch; //記錄讀入的字符
char path[PATH]; //文本文件的讀路徑
cout<<"請輸入要壓縮的.txt文件地址：（無需擴展名）"<<endl;
gets(path);
if((fp=fopen(strcat(path,".txt"),"r"))==NULL) //只讀方式打開壹個文件
{
cout<<"\n路徑不正確！\n"<<endl;
getch();
return;
}
ch=fgetc(fp); //循環將文件內的字符輸入到數組string[]中
for(i=0;ch!=EOF;i++)
{
string[i]=ch;
ch=fgetc(fp);
}
string[i]='\0'; //數組末尾加上結束標誌'\o'
fclose(fp);
}
/*功能對string[]中的字符處理，將相同的舍去，並增加權值*/
LinkTree setWeight(char *string)
{
int i=0; //文件字符串下標
LinkTree tree; //頭指針
LinkTree ptr,beforeptr; //創建指針與其前驅
HTNode *node;
if((tree=(LinkTree)malloc(sizeof(HTNode)))==NULL)//創建鏈表的頭結點
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) //如果是第壹個非頭結點
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) //如果鏈表中某結點的字符與新結點的字符相同
{
ptr->weight++; //將該結點的權加壹
free(node);
}
else //將新結點插入鏈表後
{
node->next=beforeptr->next;
beforeptr->next=node;
}
}
}
return tree; //返回頭指針
}
/*功能：將鏈表中的含權字符按權的從小到大排列並輸入到壹鏈表*/
LinkTree sortNode(LinkTree tree)
{
LinkTree head; //頭指針
LinkTree ph,beforeph; //創建指針及其前驅
LinkTree pt;
if((head=(LinkTree)malloc(sizeof(HTNode)))==NULL)//創建新鏈表的頭結點
return NULL;
head->next=NULL;
ph=head;
beforeph=head;
while(tree->next)
{
pt=tree->next; //取被操作鏈表的頭結點
tree->next=pt->next;
pt->next=NULL;
ph=head->next;
beforeph=head;
if(head->next==NULL)
head->next=pt; //創建當前操作鏈表頭結點
else
{
while(ph&&ph->weight<pt->weight) //將被操作結點插入相應位置
{
ph=ph->next;
beforeph=beforeph->next;
}
pt->next=beforeph->next;
beforeph->next=pt;
}
}
free(tree); //釋放含權樹
return head; //返回排序後的頭指針
}
/*用排序後的鏈表建立哈夫曼樹*/
LinkTree createHTree(LinkTree tree)
{
LinkTree pt,q,beforept;
HTNode *newnode;
for(pt=tree->next,q=pt->next;pt!=NULL&&q!=NULL;pt=tree->next,q=pt->next)
//pt、q初值為頭結點後的兩個結點，即最小權結點
{
tree->next=q->next; //取出將最小的兩個結點
q->next=NULL;
pt->next=NULL;
if((newnode=(HTNode *)malloc(sizeof(HTNode)))==NULL)
//申請新結點作為哈夫曼樹的中間結點
return NULL;
newnode->next=NULL;
newnode->mark=0; //標記
newnode->lchild=pt; //取鏈表頭結點後的兩個結點作為新結點的左、右孩子
newnode->rchild=q;
pt->parent=newnode;
q->parent=newnode;
newnode->weight=pt->weight+q->weight; //權值等於孩子權值相加
pt=tree->next;
beforept=tree;
if(pt!=NULL&&pt->weight>=newnode->weight)
{
newnode->next=beforept->next; //將新結點插入原鏈表的相應位置
beforept->next=newnode;
}
else
{
while(pt!=NULL&&pt->weight<newnode->weight)//循環找出newnode結點的插入位置
{
pt=pt->next;
beforept=beforept->next;
}
newnode->next=beforept->next;
beforept->next=newnode;
}
}
return (tree->next);
}
/*對哈夫曼樹進行編碼,並將關鍵字保存如數組codedictionary[]中*/
void codeHTree(LinkTree tree,CodeDictionary *codedictionary)
{
int index=0,k=0;
char code[MAX_SINGLECODE]; //用於統計每個字符的哈夫曼編碼
LinkTree ptr=tree; //從樹的根結點開始
if(ptr==NULL)
{
cout<<"要壓縮的文件是空的!\n"<<endl;
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) //如果沒有左右孩子，即葉子結點
{
ptr->mark=1; //作標記，表明該字符已被編碼
code[index]='\0'; //編碼0-1字符串結束
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->rchild&&ptr->rchild->mark==0)
{
ptr=ptr->rchild;
code[index++]='1'; //右支路編碼為1
}
if(!ptr->lchild&&!ptr->rchild) //如果沒有左右孩子，即葉子結點
{
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)//如果左右孩子都已標記
{
ptr->mark=1;
ptr=tree;
index=0;
}
}
}
cout<<"\n"<<endl;
}
/*將整個字符串轉化為0-1的字符串*/
void compressString(char *string,CodeDictionary *codedictionary,char *codestring)
{
int i=0,j=0,k=0,m;
while(string[i]) //整個文件字符串沒結束時
{
while(string[i]!=codedictionary[j].ch&&j<MAX_WORDS)
//找與對應字符相同的字符
j++;
if(string[i]==codedictionary[j].ch) //如果找到與對應字符相同的字符
for(m=0;codedictionary[j].code[m];m++,k++)
codestring[k]=codedictionary[j].code[m];
j=0; //字典復位
i++;
}
codestring[k]='\0'; //標記結束
}
/*保存按權排列的鏈表和編碼後的字符串*/
void writeCode(LinkTree tree,char *string)
{
FILE *fp;
int i;
int weight; //記錄寫入的權值
char ch; //記錄寫入的字符
LinkTree p;
char path[PATH]; //0-1碼文件的寫路徑
cout<<"請輸入壓縮後的保存路徑及文件名：（無需擴展名）"<<endl;
gets(path);
if((fp=fopen(strcat(path,".wp"),"w+"))==NULL)
{
cout<<"\n文件路徑出錯！\n"<<endl;
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); //空出區分位，用於解碼時區分鏈表和編碼
/*0-1碼寫入文件後部分*/
for(i=1;string[i-1];i++)
{
if(string[i-1]=='1')
{
ch<<=1;
ch+=1;
}
if(string[i-1]=='0')
{
ch<<=1;
ch+=0;
}
if(i%8==0)
fputc(ch,fp);
}
cout<<"\n壓縮成功！\n"<<endl;
getch();
fclose(fp);
}
/*釋放哈夫曼樹所占用的空間*/
void deleteTree(LinkTree tree)
{
LinkTree ptr=tree;
if(ptr)
{
deleteTree(ptr->lchild); //第歸處理左子樹
deleteTree(ptr->rchild); //第歸處理右子樹
free(ptr); //釋放結點
}
}