设计一个哈夫曼编码、译码系统

#include
#include
#include
#include
#include

//typedef int TElemType;
const int UINT_MAX = 1000;

typedef struct
{
int weight;
int parent, lchild, rchild;
} HTNode, *HuffmanTree;

typedef char **HuffmanCode;

//-----------全局变量-----------------------
HuffmanTree HT;
HuffmanCode HC;
int *w, i, j, n;
char *z;
int flag = 0;
int numb = 0;
// -----------------求赫夫曼编码-----------------------

int min(HuffmanTree t, int i)
{
// 函数void select()调用
int j, flag;
int k = UINT_MAX; // 取k为不小于可能的值
for (j = 1; j <= i; j++)
if (t[j].weight < k && t[j].parent == 0)
k = t[j].weight, flag = j;
t[flag].parent = 1;
return flag;
}

//--------------------slect函数----------------------
void select(HuffmanTree t, int i, int &s1, int &s2)
{
// s1为最小的两个值中序号小的那个
int j;
s1 = min(t, i);
s2 = min(t, i);
if (s1 > s2)
{
j = s1;
s1 = s2;
s2 = j;
}
}

// --------------算法6.12--------------------------
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
int m, i, s1, s2, start;
//unsigned c,f;
int c, f;
HuffmanTree p;
char *cd;
if (n <= 1)
return ;
//检测结点数是否可以构成树
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m + 1) *sizeof(HTNode)); // 0号单元未用
for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w)
{
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for (; i <= m; ++i, ++p)
p->parent = 0;
for (i = n + 1; i <= m; ++i)
// 建赫夫曼树
{
// 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT, i - 1, s1, s2);
HT[s1].parent = HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
// 从叶子到根逆向求每个字符的赫夫曼编码
HC = (HuffmanCode)malloc((n + 1) *sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
cd = (char*)malloc(n *sizeof(char)); // 分配求编码的工作空间
cd[n - 1] = '\0'; // 编码结束符
for (i = 1; i <= n; i++)
{
// 逐个字符求赫夫曼编码
start = n - 1; // 编码结束符位置
for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
// 从叶子到根逆向求编码
if (HT[f].lchild == c)
cd[--start] = '0';
else
cd[--start] = '1';
HC[i] = (char*)malloc((n - start) *sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}

//--------------初始化赫夫曼链表---------------------------------
void Initialization()
{
flag = 1;
int num;
int num2;
cout << "下面初始化赫夫曼链表" << endl << "数请输入结点的个n：";
cin >> num;
n = num;
w = (int*)malloc(n *sizeof(int));
z = (char*)malloc(n *sizeof(char));
cout << "\n请依次输入" << n << "个字符(字符型)\n注意:必须以回车结束：" <<
endl;
char base[2];
for (i = 0; i < n; i++)
{
cout << "第" << i + 1 << "个字符:" << endl;
gets(base);
*(z + i) = *base;
}
for (i = 0; i <= n - 1; i++)
{
cout << setw(6) << *(z + i);
}
cout << "\n请依次输入" << n << "个权值(\n注意:必须以回车结束)：" << endl;
for (i = 0; i <= n - 1; i++)
{
cout << endl << "第" << i + 1 << "个字符的权值:";
cin >> num2;
*(w + i) = num2;
}
HuffmanCoding(HT, HC, w, n);
//------------------------打印编码-------------------------------------------
cout << "字符对应的编码为:" << endl;
for (i = 1; i <= n; i++)
{
//cout<<"字符"<<*(z+i-1)<<"的编码";
puts(HC[i]);
}
//--------------------------将赫夫曼编码写入文件------------------------
cout << "下面将赫夫曼编码写入文件" << endl << "...................." << endl;

FILE *htmTree;
char r[] =
{
' ', '\0'
};
if ((htmTree = fopen("htmTree.txt", "w")) == NULL)
{
cout << "can not open file" << endl;
return ;
}

fputs(z, htmTree);
for (i = 0; i < n + 1; i++)
{
fprintf(htmTree, "%6d", *(w + i));
fputs(r, htmTree);
}
for (i = 1; i <= n; i++)
{
fputs(HC[i], htmTree);
fputs(r, htmTree);
}
fclose(htmTree);
cout << "已将字符与对应编码写入根目录下文件htmTree.txt中" << endl << endl;
}

//---------------------获取报文并写入文件---------------------------------

void InputCode()
{
//cout<<"请输入你想要编码的字符"< FILE *tobetran;
char str[100];
if ((tobetran = fopen("tobetran.txt", "w")) == NULL)
{
cout << "不能打开文件" << endl;
return ;
}
cout << "请输入你想要编码的字符" << endl;
gets(str);
fputs(str, tobetran);
cout << "获取报文成功" << endl;
fclose(tobetran);
}

//---------------------编码函数---------------------------------
void Encoding()
{
cout << "下面对目录下文件tobetran.txt中的字符进行编码" << endl;

FILE *tobetran, *codefile;

if ((tobetran = fopen("tobetran.txt", "rb")) == NULL)
{
cout << "不能打开文件" << endl;
}
if ((codefile = fopen("codefile.txt", "wb")) == NULL)
{
cout << "不能打开文件" << endl;
}

char *tran;
i = 99;
tran = (char*)malloc(100 *sizeof(char));

while (i == 99)
{
if (fgets(tran, 100, tobetran) == NULL)
{
cout << "不能打开文件" << endl;
break;
}
for (i = 0; *(tran + i) != '\0'; i++)
{
for (j = 0; j <= n; j++)
{
if (*(z + j - 1) == *(tran + i))
{
fputs(HC[j], codefile);
if (j > n)
{
cout << "字符错误，无法编码!" << endl;
break;
}
}
}
}
}
cout << "编码工作完成" << endl << "编码写入目录下的codefile.txt中" << endl <<
endl;
fclose(tobetran);
fclose(codefile);
free(tran);
}

//-----------------译码函数---------------------------------
void Decoding()
{

cout << "下面对根目录下文件codefile.txt中的字符进行译码" << endl;
FILE *codef, *txtfile;
if ((txtfile = fopen("Textfile.txt", "w")) == NULL)
{
cout << "不能打开文件" << endl;
}
//txtfile=fopen("Textfile.txt","w");
if ((codef = fopen("codefile.txt", "r")) == NULL)
{
cout << "不能打开文件" << endl;
}
//codef=fopen("codefile.txt","r");
char *work, *work2, i2;
int i4 = 0, i, i3;
unsigned long length = 10000;
work = (char*)malloc(length *sizeof(char));
fgets(work, length, codef);
work2 = (char*)malloc(length *sizeof(char));
i3 = 2 * n - 1;
for (i = 0; *(work + i - 1) != '\0'; i++)
{
i2 = *(work + i);
if (HT[i3].lchild == 0)
{
*(work2 + i4) = *(z + i3 - 1);
i4++;
i3 = 2 * n - 1;
i--;
}
else if (i2 == '0')
i3 = HT[i3].lchild;
else if (i2 == '1')
i3 = HT[i3].rchild;
}
*(work2 + i4) = '\0';
fputs(work2, txtfile);
cout << "译码完成" << endl << "内容写入根目录下的文件txtfile.txt中" << endl
<< endl;
cout << work2;
free(work);
free(work2);
fclose(txtfile);
fclose(codef);

}

//-----------------------打印编码的函数----------------------
void Code_printing()
{
cout << "下面打印根目录下文件CodePrin.txt中编码字符" << endl;
FILE *CodePrin, *codefile;
if ((CodePrin = fopen("CodePrin.txt", "w")) == NULL)
{
cout << "不能打开文件" << endl;
return ;
}
if ((codefile = fopen("codefile.txt", "r")) == NULL)
{
cout << "不能打开文件" << endl;
return ;
}

char *work3;
work3 = (char*)malloc(51 *sizeof(char));
do
{
if (fgets(work3, 51, codefile) == NULL)
{
cout << "不能读取文件" << endl;
break;
}
fputs(work3, CodePrin);
puts(work3);
}
while (strlen(work3) == 50);
free(work3);

/* int iNum=2,num=2;
while((num=fscanf(codefile,"%d",iNum))!=NULL)
{
printf("%d",iNum);
fprintf(CodePrin,"%d",iNum);
}
*/
cout << "打印工作结束" << endl << endl;
fclose(CodePrin);
fclose(codefile);
}

//------------------------打印赫夫曼树的函数-----------------------
void coprint(HuffmanTree start, HuffmanTree HT)
{

if (start != HT)
{
FILE *TreePrint;

if ((TreePrint = fopen("TreePrint.txt", "a")) == NULL)
{
cout << "创建文件失败" << endl;
return ;
}

numb++; //该变量为已被声明为全局变量
coprint(HT + start->rchild, HT);
cout << setw(5 *numb) << start->weight << endl;

fprintf(TreePrint, "%d\n", start->weight);
coprint(HT + start->lchild, HT);
numb--;
fclose(TreePrint);
}
}

void Tree_printing(HuffmanTree HT, int w)
{
HuffmanTree p;
p = HT + w;
cout << "下面打印赫夫曼树" << endl;
coprint(p, HT);
cout << "打印工作结束" << endl;
}

/*//------------------------------tongjipindu
void tongji(HuffmanTree &HT, HuffmanCode &HC)
{
char str[254], st[254];
int cnt[27];
// char *p;
int temp[27], k;
for (int i = 1; i <= 26; i++)
{
temp[i] = 0;
}
flag = 1;
char base;
int n = 0; //总数
cout << "请输入字符串：" << endl;
while (1)
{
cin >> base;
if (base != '\0')
{
st[n] = base;
n++;
}
else
st[n] = '\0';
break;
}
for (int t = 0; st[t] != '\0'; t++)
{
if (st[t] >= 'A' && st[t] <= 'Z')
{
k = st[t] - 64;
temp[k]++;

}
}
j = 0;
for (i = 1, j = 0; i <= 26; i++)
{
if (temp[i] != 0)
{
j++;
str[j] = i + 64;
cnt[j] = temp[i];
}
}
w = (int*)malloc(n *sizeof(int)); //pindu
z = (char*)malloc(n *sizeof(char)); //zifu
z = str;
w = cnt;
for (t = 1; t <= n; t++)
{
cout << "字符:" << str[t] << " 频度:" << cnt[t] << endl;
}

// char base[2];

// for(i=0;i<=n-1;i++)
// {
// cout< // }

// cin>>num2;
// *(w+i)=num2;

HuffmanCoding(HT, HC, w, n);
//------------------------打印编码-------------------------------------------
cout << "字符对应的编码为:" << endl;
for (i = 1; i <= n; i++)
{
//cout<<"字符"<<*(z+i-1)<<"的编码";
puts(HC[i]);
}
//--------------------------将赫夫曼编码写入文件------------------------
cout << "下面将赫夫曼编码写入文件" << endl << "...................." << endl;

FILE *htmTree;
char r[] =
{
' ', '\0'
};
if ((htmTree = fopen("htmTree.txt", "w")) == NULL)
{
cout << "can not open file" << endl;
return ;
}

fputs(z, htmTree);
for (i = 0; i < n + 1; i++)
{
fprintf(htmTree, "%6d", *(w + i));
fputs(r, htmTree);
}
for (i = 1; i <= n; i++)
{
fputs(HC[i], htmTree);
fputs(r, htmTree);
}
fclose(htmTree);
cout << "已将字符与对应编码写入根目录下文件htmTree.txt中" << endl << endl;
}*/

//------------------------主函数------------------------------------
void main()
{
char choice;
while (choice != 'q')
{
cout << "\n******************************" << endl;
cout << " 欢迎使用赫夫曼编码解码系统" << endl;
cout << "******************************" << endl;
cout << "(1)要初始化赫夫曼链表请输入'i'" << endl;
cout << "(2)输入要编码的字符'w'" << endl;
cout << "(3)要编码请输入'e'" << endl;
cout << "(4)要译码请输入'd'" << endl;
cout << "(5)要打印编码请输入'p'" << endl;
cout << "(6)要打印赫夫曼树请输入't'" << endl;
cout << "(7)要离开请输入'q'" << endl;
//cout << "(8)统计频度'a'" << endl;
// if(flag==0)cout<<"\n请先初始化赫夫曼链表,输入'i'"< cin >> choice;
switch (choice)
{
case 'i':
Initialization();
break;
case 'w':
InputCode();
break;
case 'e':
Encoding();
break;
case 'd':
Decoding();
break;
case 'p':
Code_printing();
break;
case 't':
Tree_printing(HT, 2 *n - 1);
break;
case 'q':
break;
// case 'a':
// tongji(HT, HC);
default:
cout << "input error" << endl;
}

}
free(z);
free(w);
free(HT);
}