第1个回答 2020-03-01
这是我们的作业题，自己写
的……（可能输入的格式跟你要的不一致，自己改一下）
注：1、
初始化创建哈夫曼树有三种选择，其中选择编译课本测试数据时和编译源文件是，调用的输入文件分别是：test.txt和input.txt；字母的哈夫曼编码都保存在文件：hmfTree.txt；
2、
用户自定义模式下，需要编码的文件内容保存在ToBeTran.txt中；课本测试数据和源文件代码分别保存在course.txt和sorse.txt中，在（1）中选择不同的选项，则在编码时调用相应的文件进行编码，编码结果保存在文件CodeFile.txt中。
3、
文件译码时，调用文件CodeFile.txt进行译码，得到的结果保存在文件TextFile.txt中。
4、
打印代码文件：调用CodeFile.txt，结果显示在终端并保存在文件CodePrin.txt中。
5、
打印哈夫曼树：用凹入表形式把哈夫曼树显示在终端，同时将它保存在文件TreePrint..txt中。
#include
<stdio.h>
#include<malloc.h>
#include
<string.h>
#include<fstream>
#include<iostream>
using
namespace
std;
typedef
struct
{
unsigned
int
weight;
char
ch1;
unsigned
int
parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef
char
**HuffmanCode;
typedef
struct
{
char
ch;
char
code[7];
}codenode,*code;
void
select(HuffmanTree
HT,int
n,int
&
s1,int
&s2){
//从哈夫曼树中选择出最小的两个节点
for(int
i=1;i<=n;i++)
if(!HT[i].parent){
s1=i;
break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i;
break;
}
if(HT[s1].weight-HT[s2].weight){
int
temp;
temp=s1;
s1=s2;
s2=temp;
}
for(i=1;i<=n;i++)
//对数组进行遍历，寻找最小的两个节点
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1;
s1=i;
}
else
if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}
void
prin(){
//终端输出选择菜单
cout<<"----------------------------------------------------\n\n"
<<"
∣
I---创建哈夫曼树
∣\n"
<<"
∣
∣\n"
<<"
∣
E---文件编码
∣\n"
<<"
∣
∣\n"
<<"
∣
D---文件译码
∣\n"
<<"
∣
∣\n"
<<"
∣
P---打印代码文件
∣\n"
<<"
∣
∣\n"
<<"
∣
T---印哈夫曼树
∣\n"
<<"
∣
∣\n"
<<"
∣
O---哈夫曼树的存储结构
∣\n"
<<"
∣
∣\n"
<<"
∣
Q---退出
∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
}
void
output
(HuffmanTree
th,int
n){
//输出哈夫曼树的存储结构
int
i=0;
cout<<"序号"<<"
"<<"字符"<<"
"<<"双亲"<<"
"<<"左孩子"<<"
"<<"右孩子"<<"
"<<"权值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<"
"<<th->ch1<<"
"<<th->parent<<"
"<<th->lchild<<"
"<<th->rchild<<"
"<<th->weight
<<endl;
}
}
void
initial(HuffmanTree
&HT,HuffmanCode
&HC,int
w[],int
&n,char
ch[],int
&k){
//创建哈夫曼树
cout<<"----------------------------------------------------\n\n"
<<"
∣
1---自定义
∣\n"
<<"
∣
∣\n"
<<"
∣
2---编码课本测试数据
∣\n"
<<"
∣
∣\n"
<<"
∣
3---编码源程序
∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
scanf("%d",&k);
if(k==1){
printf("输入需要编码的字符总数:
");
scanf("%d",&n);
printf("\n输入需要编码字符的权值:\n");
for(int
d=0;d<n;d++)
{
scanf("%d",&w[d]);
}
printf("\n输入需要编码的字符串:
");
scanf("%s",ch);
}
else
if(k==2){
ifstream
fin2
("test.txt");
fin2>>n;
for(int
d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else
if(k==3){
ifstream
fin1
("input.txt");
fin1>>n;
for(int
d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int
s1,s2,i,num=2*n-1;
HuffmanTree
p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1];
p->lchild=0;
p->parent=0;
p->rchild=0;
p->ch1
=ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0;
p->lchild=0;
p->parent=0;
p->rchild=0;
p->ch1
='$';
}
for(i=n+1;i<=num;i++){
select(HT,i-1,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;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char
*));
char
*
temp=(char
*)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int
start=n-1;
for(int
f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char
*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream
fout
("hfmTree.txt");
fout<<ch<<endl;
for(int
j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}
void
encoding(int
n,int
select){
//编码：对文件TobeTran.txt进行译码
char
a[100],b[100][20];
ifstream
fin
("hfmTree.txt");
fin>>a;
for(int
j=0;j<n;j++)
fin>>b[j];
fin.close();
ifstream
fin1
("course.txt");
ifstream
fin2
("sorse.txt");
ifstream
fin3
("ToBeTran.txt");
char
s[1000];
if(select==3)
fin2>>s;
else
if(select==2)
fin1>>s;
else
fin3>>s;
ofstream
fout
("CodeFile.txt");
while(s[0]!='\0'){
for(int
i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++
){
for(int
g=0;a[g]!=s[i];g++)
;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else
if(select==2)
fin1>>s;
else
fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}
void
decoding(HuffmanTree
ht,int
n){
//译码：对CodeFile.txt文件进行译码
ifstream
fin
("CodeFile.txt");
ofstream
fout
("TextFile.txt");
char
s[500];
fin>>s;
HuffmanTree
head=ht+2*n-1;
int
i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1')
head=ht+head->rchild;
else
if(s[i]=='0')
head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild)
==0)
{
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<'
'
;
i=0;
fin>>s;
}
fin.close();
fout.close();
}
void
Print(){
//打印代码文件，显示在终端，每行50个代码
ifstream
fin
("CodeFile.txt");
char
s[2000];
int
j=0;
int
i=1;
fin>>s;
ofstream
fout
("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}
void
printTree(
HuffmanTree
node,HuffmanTree
node1,
int
level
)
{
//打印哈夫曼树形（在参数的传递上，是文科给自己提出的意见才很好的解决了之后的操作难题^^）
if(
node
==
NULL
)
return;
if(
node1->rchild!=0)
{
printTree(
node,node+node1->rchild,
level
+
1
);
}
fstream
fout
;
fout.open
("TreePrint.txt",ios::in
|
ios::out|ios::ate);//这个挺有用的：在文件末尾加入内容
for(
int
i
=
0;
i
<
level;
i++
)
{
fout<<"|……";
printf(
"……");
}
fout<<node1->weight<<endl;
printf(
"%d\n",
node1->weight
);
if(
node1->lchild!=0
)
{
printTree(
node,node+node1->lchild,
level
+
1
);
}
fout.close();
}
void
main(){
int
select;
int
n;
char
ch[100];
int
w[100];
HuffmanTree
HT=NULL;
HuffmanCode
hc=NULL;
prin();
char
c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case
'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case
'E':
encoding(n,select);
prin();
break;
case
'D':
decoding(HT,n);
prin();
break;
case
'P':
Print();
prin();
break;
case
'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case
'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}
}
第2个回答 2008-12-15
#include<iostream>
#include<string>
using namespace std;
typedef struct
{
int weight;
int flag;
int parent;
int lchild;
int rchild;
}hnodetype;
typedef struct
{
int bit[10];
int start;
char leaf;
}hcodetype;
void huf(char cha[],int m[],int n)
{
int i,j,m1,m2,x1,x2,c,p;
hnodetype *huffnode=new hnodetype[2*n-1];
hcodetype *huffcode=new hcodetype[n],cd;
for(i=0;i<2*n-1;i++)
{
huffnode[i].weight=0;
huffnode[i].parent=0;
huffnode[i].flag=0;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
}
for(i=0;i<n;i++)
{
huffnode[i].weight=m[i];
huffcode[i].leaf=cha[i];
}
for(i=0;i<n-1;i++)
{
m1=m2=10000000;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(huffnode[j].weight<=m1&&huffnode[j].flag==0)
{
m2=m1;
x2=x1;
m1=huffnode[j].weight;
x1=j;
}
else if(huffnode[j].weight<=m2&&huffnode[j].flag==0)
{
m2=huffnode[j].weight;
x2=j;
}
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[x1].flag=1;
huffnode[x2].flag=1;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=huffnode[c].parent;
while(p!=0)
{
if(huffnode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
cout<<huffcode[i].leaf<<":";
for(j=cd.start+1;j<n;j++)
{
huffcode[i].bit[j]=cd.bit[j];
cout<<cd.bit[j];
}
cout<<endl;
huffcode[i].start=cd.start;
}
delete[] huffcode;
delete[] huffnode;
}
void main()
{
string str;
int i=0,j,n,m[100],h,k=0;
char cha[100];
cout<<"请输入一个字符串"<<endl;
cin>>str;
n=str.length();
cout<<"字符串总共有字符"<<n<<"个"<<endl;
for(i=0;i<n;i++)
{
j=0;h=0;
while(str[i]!=str[j])
j++;
if(j==i)
{
cha[k]=str[i];
cout<<"字符"<<cha[k]<<"出现";
}
else
continue;
for(j=i;j<n;j++)
{
if(str[i]==str[j])
h++;
}
cout<<h<<"次"<<endl;
m[k]=h;
k++;
}
cout<<"每个字符的哈夫曼编码是："<<endl;
huf(cha,m,k);
cin.get();
cin.get();
}