📄 text5-2.cpp
字号:
#include<iostream>
#include<string.h>
#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>
using namespace std;
typedef struct FreOfCh{//用来存储用户输入的字符——频度集
char word;
int weight;
};
typedef struct {
int weight;
int parent,lchild,rchild;
char word;
int mark;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct codefilenode{//存入该文件的节点类型。实际上只是用来存贮在文件的一个媒介结构体
char word;
char* code;
};
#define STACK_INIT_STZE 100//存储空间初始分配量
#define STACKINCREMENT 50//存储空间分配增量
typedef struct{
HuffmanTree *base;
HuffmanTree *top;
int stacksize;//当前已分配的存储空间
}SqStack;
//===========================三级调用函数===========================
void InitStack(SqStack &S){//构造一个空栈
S.base=(HuffmanTree *)malloc(STACK_INIT_STZE*sizeof(HTNode));
//if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_STZE;
}//InitStack
void Push(SqStack &S,HuffmanTree e){//入栈
*S.top++=e;
}//Push
void Pop(SqStack &S,HuffmanTree &e){//出栈
//if(S.top==S.base)return ERROR;
e=*(S.top-1);
S.top=S.top-1;
}//Pop
//===================================二级调用函数==================================
int ReInitFileOfHuf(int &n){//建立用户输入字符频度集合，存入user文件中
//返回的值为用户输入字符的个数n
cout<<"请输入字符总个数 ！";
cin>>n;
struct FreOfCh *usr;
usr=new FreOfCh[n];
cout<<"请输入所有字符！";
char ch;int i=0;
ch=getchar();
ch=getchar();
while(i!=n){
usr[i].word=ch;
ch=getchar();
i++;
}
cout<<"请输入相应的权值！";
int m;
i=0;
cin>>m ;
cout<<"请确认信息"<<endl;
while(i!=n ){
usr[i].weight=m;
cout<<"字符: "<<usr[i].word<<" "<<"权值："<<usr[i].weight<<endl;
i++;if(i==n)break;
cin>>m;
}
FILE *fp;
fp = fopen("user", "w+");
if (!fp)
{
printf("Open file error！\n");
system("pause");
return -1;
}
//将结构体数据写入文件
for(int r=0;r!=n;r++){
fwrite(&usr[r], sizeof(FreOfCh), 1, fp);
}
free(usr);fclose(fp);
fp=fopen("user","r");
usr=new FreOfCh[n];
for(int r=0;r!=n;r++){
fread(&usr[r], sizeof(FreOfCh), 1, fp);
}
rewind(fp); //将指针移到文件头处
fclose(fp);free(usr);
return n;
}
int CreatHufTree_sys(HuffmanTree &HT,int &n){//w存放n个字符的权值
FILE *fp;
fp = fopen("sys", "r");//文件sys已经在main中初始化好了
if (!fp)
{
printf("Open file error！\n");
system("pause");
return -1;
}
struct FreOfCh *syst=(FreOfCh*)malloc(28*sizeof(FreOfCh));
syst[0].weight=0;syst[0].word=' ';
for(int r=1;r!=28;r++){
fread(&syst[r], sizeof(FreOfCh), 1, fp);
}
fclose(fp);
int s1,s2;
n=27;
int m=2*n-1;int i=0;HuffmanTree p=NULL;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1,p=HT+1;i<=n;++i,++p) {
p->weight=syst[i].weight;
p->parent=p->lchild=p->rchild=0;
p->word=syst[i].word;
p->mark=0;
}
for(;i<=m;++i,++p) {
p->weight=p->parent=p->lchild=p->rchild=0;
p->word=' ';
p->mark=0;
}
for(i=n+1;i<=m;++i){
//Select(HT,i-1,s1,s2);
int b=0,a=0,j=0,k=0,start=0,r=0,s=0;//a<k
for(k=1;k<=i-1;++k)//寻找第一个parent不为零的点
if(HT[k].parent==0) {
a=HT[k].weight;//a记录它的权值
r=k;//r记录它的位置
break;
}
if(k>i-1){cout<<"现在所有的节点都有parent";exit(0);}
for(k=k+1;k<=i-1;k++)//寻找第二个parent不为零的点
if(HT[k].parent==0){
start=k;s=k;//s记录它的位置
j=HT[k].weight;//j记录它的权值
break;
}
if(a>j){b=a;a=j;j=b;b=s;s=r;r=b;}//j始终是a和j中的大值，与之相对应s始终是权值为j的点所对应的位置
for(k=start+1;k<=n;k++){
if(HT[k].parent!=0) continue;
else if(HT[k].weight<j) {j=HT[k].weight;s=k;}
if(a>j) {b=a;a=j;j=b;}
}
s1=r;s2=s;//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;
}
fp = fopen("HufTree", "wb");//文件sys已经在main中初始化好了
if (!fp)
{
printf("Open file error！\n");
system("pause");
return -1;
}
for(int r=1;r!=m+1;r++){//存入文件HufTree文件中
fwrite(&HT[r], sizeof(HTNode), 1, fp);
}fclose(fp);free(HT);
return n;//n=27
}
void CreatHufTree_user(HuffmanTree &HT,int n){//w存放n个字符的权值
FILE *fp;
fp = fopen("user", "r");//文件user在ReInitFileOfHuf()中初始化好了
if (!fp)
{
printf("Open file error！\n");
system("pause");
return ;
}
struct FreOfCh *usr=(FreOfCh*)malloc((n+1)*sizeof(FreOfCh));
for(int r=1;r!=n+1;r++){
fread(&usr[r], sizeof(FreOfCh), 1, fp);
}
fclose(fp);
//打开
if(n<=1)return ;
int s1,s2;
int m=2*n-1;int i=0;
HuffmanTree p=NULL;
HuffmanTree q=NULL;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
HT[0].lchild=HT[0].parent=HT[0].rchild=HT[0].weight=0;HT[0].word=' ';
q=p=HT+1;
for(i=1;i<=n;++i,++p) {
p->weight=usr[i].weight;
p->parent=p->lchild=p->rchild=0;
p->word=usr[i].word;
}
for(;i<=m;++i,++p) {
p->weight=p->parent=p->lchild=p->rchild=0;
p->word=' ';
}
for(i=n+1;i<=m;++i){
//Select(q,i-1,s1,s2);
int b=0,a=0,j=0,k=0,start=0,r=0,s=0;//a<k
for(k=1;k<=i-1;++k)//寻找第一个parent为零的点
if(HT[k].parent==0) {
a=HT[k].weight;//a记录它的权值
r=k;//r记录它的位置
break;
}
if(k>i-1){cout<<"现在所有的节点都有parent";exit(0);}
for(k=k+1;k<=i-1;k++)//寻找第二个parent为零的点
if(HT[k].parent==0){
start=k;s=k;//s记录它的位置
j=HT[k].weight;//j记录它的权值
break;
}
if(a>j){b=a;a=j;j=b;b=s;s=r;r=b;}//j始终是a和j中的大值，与之相对应s始终是权值为j的点所对应的位置
for(k=start+1;k<=i-1;k++){
if(HT[k].parent!=0) continue;
else if(HT[k].weight<j) {j=HT[k].weight;s=k;}
if(a>j) {b=a;a=j;j=b;}
}
s1=r;s2=s;//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;
}
fp = fopen("HufTree", "wb");//文件sys已经在main中初始化好了
if (!fp)
{
printf("Open file error！\n");
system("pause");
return ;
}
for(int r=1;r!=m+1;r++){//存入文件HufTree文件中
fwrite(&HT[r], sizeof(HTNode),1,fp);
}
fclose(fp);free(usr);free(HT);
return ;
}
//=====================一级调度函数=========================================
int menu_select(){//菜单选择函数
int sn;
cout<<" 哈弗曼 编码--译码 系统 "<<endl;
cout<<"==============================================="<<endl;
cout<<" 1. 初始化 "<<endl;
cout<<" 2. 编码 "<<endl;
cout<<" 3. 译码 "<<endl;
cout<<" 4. 打印代码文件 "<<endl;
cout<<" 5. 打印haufman树 "<<endl;
cout<<" 0. 退出 "<<endl;
cout<<"==============================================="<<endl;
cout<<" 请选择0---5 ！ "<<endl;
for(;;){
//清理缓冲区
scanf_s("%d",&sn);
if(sn > 5 || sn < 0){
cout<<"输入错误！请重新输入0-----5 ！"<<endl;
break;
}
else
break;
}
return sn;
}//menu_select
void InitFileOfHuf(int &n) {//系统字符频度集合文件sys的建立
struct FreOfCh *syst=(FreOfCh*)malloc(28*sizeof(FreOfCh));
char word[27] ={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',' '};
int weight[27]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1,186};
for(int i=1;i!=28;i++){
syst[i].word=word[i-1];
syst[i].weight=weight[i-1];
}
FILE *fp;
fp = fopen("sys", "w");
if (!fp)
{
printf("Open file error！\n");
system("pause");
return ;
}
//将结构体数据写入文件
for(int r=1;r!=28;r++){
fwrite(&syst[r], sizeof(FreOfCh), 1, fp);
}
//从文件中读出结构体数据
rewind(fp); //将指针移到文件头处
fclose(fp);
free(syst);
n=27;
return;
}
void InitHufTree(HuffmanTree &HT,int &n){
int i=0;
cout<<" 1.重新输入字符集和频度"<<endl;
cout<<" 2.使用已经初始化好的测试数据 "<<endl;
for(;;){
cin>>i;
if(i==1){
ReInitFileOfHuf(n);//重新初始化；
CreatHufTree_user(HT, n);//调用建树函数
break;
}
else if(i==2){
CreatHufTree_sys(HT,n);//调用建树函数
break;
}else {cout<<" 输入出错 请输入1 或 2 ！"<<endl;break;}
}
return ;
}
void EnCoding(int n){
/*cout<<n;*/
HuffmanTree HT;
int m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
FILE *fp;
fp = fopen("HufTree", "rb");
if (!fp)
{
printf("Open file error！\n");
system("pause");
return ;
}
for(int r=1;r!=m+1;r++){
fread(&HT[r],sizeof(HTNode),1,fp);
}
fclose(fp);
HuffmanCode HC;
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
char*cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0';int start=1;int c=0, f=1;
for(int 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));
strcpy(HC[i],&cd[start]);
}
free(cd);
//存入TotalCodeFile中
fp = fopen("TotalCodeFile", "wb");
if (!fp)
{
printf("Open file error！\n");
system("pause");
return ;
}
codefilenode *CodeFileNode;
CodeFileNode=(codefilenode*)malloc((n+1)*sizeof(codefilenode));
for(int r=1;r<=n;r++){
CodeFileNode[r].word=HT[r].word;
CodeFileNode[r].code=HC[r];
}
free(HT);free(HC);
for(int r=1;r!=n+1;r++){
fwrite(&CodeFileNode[r],sizeof(codefilenode),1,fp);
}
fclose(fp);
//ToBeTran编译开始
fp = fopen("AimCodeFile", "wb");
if (!fp)
{
printf("Open file error！\n");
system("pause");
return ;
}
cin.sync();
cout<<"请输入要编码的的字符串（以#结束）"<<endl;
char ch;
scanf_s("%c",&ch);
cout<<"下面是编码结果(将存入AimCodeFile中)"<<endl;
while(ch!='#'){
for(c=1;c<=n;c++)
if(ch==CodeFileNode[c].word){
printf("%s",CodeFileNode[c].code);
fprintf(fp,"%s",CodeFileNode[c].code);//存入文件AimCodeFile中
break;
}
ch=getchar();
}
cout<<endl;
fclose(fp);
free(CodeFileNode);
cout<<"编码结束"<<endl;
return;
}
void Decoding(int n){
HuffmanTree HT;int m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
FILE *fp = fopen("HufTree", "rb");
if (!fp)
{
printf("Open file error！\n");
system("pause");
return ;
}
for(int i=1;i<=m;i++){
fread(&HT[i],sizeof(HTNode),1,fp);
}
fclose(fp);
fp = fopen("TextFile", "wb");
if (!fp)
{
printf("Open file error！\n");
system("pause");
return ;
}
cout<<"请输入需要译码的码串！（以#结束）"<<endl;
cin.sync() ;
char ch=getchar();
cout<<"下面是译码结果"<<endl;
while(ch!='#'){
if(ch=='0'){
m=HT[m].lchild;
if(HT[m].lchild==0 && HT[m].rchild==0){
cout<<HT[m].word;
fputc(HT[m].word,fp);
m=m=2*n-1;
}else {
}
}else{
m=HT[m].rchild;
if(HT[m].rchild==0 && HT[m].lchild==0){
cout<<HT[m].word;
fputc(HT[m].word,fp);
m=m=2*n-1;
}else{
}
}
ch=getchar();
}
fclose(fp);
cout<<endl<<"译码结束（存入TextFile中）"<<endl;
}//decoding()
void PrintfAimCodeFile(){
FILE *fp;
fp=fopen("AimCodeFile","rb");
if(!fp){
cout<<"Can't open the file";
return;
}
char ch=fgetc(fp);
int i;
while(ch!=EOF){
for(i=1;i!=51;i++){
cout<<ch;
ch=fgetc(fp);
}
cout<<endl;
}
fclose(fp);
}
void PrintHufTree(int n){
FILE *fp;int m=2*n-1;
fp=fopen("HufTree","rb");
if(!fp){cout<<"Can't open it";return;}
HuffmanTree HT,p,q;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(int i=1;i!=m+1;i++){
fread(&HT[i],sizeof(HTNode),1,fp);
}
fclose(fp);
p=HT+m;int r=0;
SqStack S;
InitStack(S);Push(S,p);
while(S.top!=S.base){
Pop(S,q);
if(q==HT+p->rchild) m=m+1;
for(int i=0;i!=m;i++)
cout<<"-";
cout<<q->word<<" "<<q->weight<<endl;
m--;//打印q
if(q->rchild){
q=HT+q->rchild;
Push(S,q);
r=q->parent;
q=HT+r;
q=HT+q->lchild;
Push(S,q);
}else m++;
}
return;
}
//===============================main()==================================
void main()
{
HuffmanTree HT;
int i=0,n=0;
InitFileOfHuf(n);
for(;;){
i=menu_select();
switch(i){
case 1:
cout<<" =========== 初 始 化 ============ "<<endl;
InitHufTree(HT,n);//初始化函数
break;
case 2:
cout<<" =========== 编 码 ============ "<<endl;
EnCoding(n);//编码函数，建立TotleCodeFile文件；利用TotleCodeFile给ToBeTran编码，存入CodeFile中
break;
case 3:
cout<<" =========== 译 码 ============ "<<endl;
Decoding(n);
break;
case 4:
cout<<" ============ 打印代码文件 ============= "<<endl;
PrintfAimCodeFile();//打印代码文件函数
break;
case 5:
cout<<" =========== 打印hufman树 =============="<<endl;
PrintHufTree(n);//打印hufman树函数
break;
case 0:
cout<<" 谢谢使用 再见！O(∩_∩)O ============="<<endl;
return;
}
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -