数据结构(C++版)哈弗曼 编码

问题描述:利用哈夫曼编码进行信息通讯可以大大提高信道的利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码;在接受端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码编码/译码系统。
基本要求:根据某字符文件统计字符出现频度,构造Huffman 树,编制Huffman编码,并将给定字符文件编码,生成编码文件;再将给定编码文件解码,生成字符文件(要求按二进制位表示编码)。
提高要求:改进Huffman编码,产生两种以上的编码方案,对同一组测试数据,用不同的编码方案编码,并从文件长度、算法复杂度等方面进行比较分析。
测试数据:找一个英文文档文件或中文文档文件。
用C++来编写,能实现基本要求和提高要求的。

c++

2个回答

#include
using namespace std;
HuffmanTree::HuffmanTree() //初始化空树
{
Node=NULL; //将树结点初始化为空
Info=NULL; //将字符数组初始化为空
LeafNum=0; //将叶子数初始化为0
}
HuffmanTree::~HuffmanTree() //析构函数
{
delete[] Node; //释放结点空间
delete[] Info; //释放字符存储空间
}
/////////////////////////////////////////
//初始化函数
void HuffmanTree::Initialization(int WeightNum)

{
int i,j,pos1,pos2,max1,max2;
Node=new HuffmanNode[2*WeightNum-1]; //为哈夫曼树所需的结点申请空间

Info=new char[2*WeightNum-1];
for(i=0;i {
cout cin>>Info[i];
cout<<"请输入该字符的权值或频度";
cin>>Node[i].weight; //输入权值
Node[i].parent=-1; //为根结点
Node[i].lchild=-1; //无左孩子
Node[i].rchild=-1; //无右孩子
}
//这里构造出weightnum个带权结点

for(i=WeightNum;i {
pos1=-1;
pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号
max1=32767; //32767为整型数的最大值
max2=32767;
for(j=0;j if(Node[j].parent==-1)
if(Node[j].weight {
max2=max1; //原最小值变为次小值
max1=Node[j].weight; //存放最小值
pos2=pos1; //修改次小值所在单元编号
pos1=j; //修改最小值所在单元编号
}
else
if(Node[j].weight {
max2=Node[j].weight; //存放次小值
pos2=j; //修改次小值所在的单元编号
}
Node[pos1].parent=i; //修改父亲位置
Node[pos2].parent=i;
Node[i].lchild=pos1; //修改儿子位置
Node[i].rchild=pos2;
Node[i].parent=-1; //表示新结点应该是根结点
Node[i].weight=Node[pos1].weight+Node[pos2].weight;
}
LeafNum=WeightNum;
char ch;
cout cin>>ch;
if(ch=='y'||ch=='Y')
{
ofstream fop; //以二进制方式打开hfmTree.dat文件,并当重新运行时覆盖原文件
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);
if(fop.fail()) //文件打开失败
cout<<"文件打开失败!\n";
fop.write((char*)&WeightNum,sizeof(WeightNum)); //写入WeightNum
for(i=0;i {
fop.write((char*)&Info[i],sizeof(Info[i]));
flush(cout);
}
for(i=0;i {
fop.write((char*)&Node[i],sizeof(Node[i]));
flush(cout);
}
fop.close(); //关闭文件
}
cout }
//编码函数
void HuffmanTree::Encoder()
{
if(Node==NULL)
{
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in); //以二进制方式打开hfmTree.dat文件
if(fip.fail()) //文件打开失败
{
cout return; //结束本函数
}
fip.read((char*)&LeafNum,sizeof(LeafNum)); //读取叶子数
Info=new char[LeafNum];
Node=new HuffmanNode[2*LeafNum-1];
for(int i=0;i fip.read((char*)&Info[i],sizeof(Info[i]));
for(int i=0;i fip.read((char*)&Node[i],sizeof(Node[i]));
}
char *Tree; //用于存储需编码内容
int i=0,num;
char Choose;
cout cin>>Choose;
if(Choose=='1') //读取文件ToBeTran.txt
{
ifstream fip1("ToBeTran.txt");
if(fip1.fail()) //文件不存在
{
cout<<"文件打开失败!\n";
return; //结束本函数
}
char ch;
int k=0;
while(fip1.get(ch))

{
k++;

}
fip1.close();

Tree=new char[k+1];
ifstream fip2("ToBeTran.txt");
k=0;
while(fip2.get(ch))
{
Tree[k]=ch; //读取文件内容,并存到Tree中
k++;
}
fip2.close();
Tree[k]='\0'; //结束标志
cout<<"需编码内容为:";
cout<<Tree<<endl;
} //if(Choose=='2')
else

{
string tree;

cin.ignore();
cout<<"请输入需要编码的内容(可输入任意长,结束时请按2下回车):\n";
getline(cin,tree,'\n'); //输入任意长字符串,

while(tree[i]!='\0')
i++;
num=i; //计算tree长度
i=0;
Tree=new char[num+1];
while(tree[i]!='\0') //将tree中的字符转存到Tree中
{
Tree[i]=tree[i];
i++;
}
Tree[i]='\0'; //结束标志符
}
ofstream fop("CodeFile.dat",ios::trunc);

i=0;
int k=0;
char *code;
code=new char[LeafNum]; //为所产生编码分配容量为LeafNum的存储空间

while(Tree[k]!='\0') //对每一个字符编码
{
int j,start=0;
for(i=0;i<LeafNum;i++)
if(Info[i]==Tree[k])

break;
j=i;
while(Node[j].parent!=-1) //结点j非树根
{
j=Node[j].parent; //求结点j的双亲结点
if(Node[j].lchild==i) //是左子树,则生成代码0
code[start++]='0';
else

code[start++]='1'; //是右子树,则生成代码1
i=j;
}
code[start]='\0'; //置串结束符

for(i=0;i<start/2;i++) //对二进制序列进行逆置
{
j=code[i];
code[i]=code[start-i-1];
code[start-i-1]=j;
}
i=0;
while(code[i]!='\0') //存储代码
{
fop<<code[i];
i++;
}
k++;
}
fop.close();
cout<<"编码完成!且存到文件CodeFile.dat中!\n\n";
}

/////////////////////////////////////////////////////////////////////////////
//解码函数

void HuffmanTree::Decoder()
{
int i=0,k=0;
int j=LeafNum*2-1-1;

char* BitStr;

ifstream fip1("CodeFile.dat"); //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码
if(fip1.fail())

{
cout<< "请先编码!\n";
return;
}
cout<<"经译码,原内容为:";
char ch;
while(fip1.get(ch))

{
k++;

}
fip1.close();

BitStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
{
BitStr[k]=ch; //读取文件内容
k++;
}
fip2.close();

BitStr[k]='\0'; //结束标志符
if(Node==NULL) //还未建哈夫曼树
{
cout<<"请先编码!\n";
return;
}
ofstream fop("TextFile.dat"); //将字符形式的编码文件写入文件CodePrin中
while(BitStr[i]!='\0')
{
if(BitStr[i]=='0')
j=Node[j].lchild; //往左走
else
j=Node[j].rchild; //往右走
if(Node[j].rchild==-1) //到达叶子结点
{
cout<<Info[j]; //输出叶子结点对应的字符
j=LeafNum*2-1-1;

fop<<Info[j]; //存入文件
}

i++;
}
fop.close();
cout<<"\n译码成功且已存到文件TextFile.dat中!\n\n";
}

//////////////////////////////////////////////////////////////////////////////////////////
//输出编码函数

void HuffmanTree::Print()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");

ofstream fop("CodePrin.dat");

if(fip.fail())
{
cout<<"没有文件,请先编码!\n";
return;
}
while(fip.get(ch))
{
cout<<ch; //读取文件内容
fop<<ch; //存到文件中
if(i==50)

{
cout<<endl;
i=0;
}
i++;
}
cout<<endl;
fip.close(); //关闭CodeFile.dat文件
fop.close(); //关闭CodePrin.dat文件

}
//输出哈夫曼树

void HuffmanTree::TreePrinting()
{
if(Node==NULL)

{
cout<<"请先建立哈夫曼树!\n";
return;
}
ofstream fop("TreePrint.dat");
cout<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n";
fop<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n";
int i;
for(i=(2*LeafNum-2);i>LeafNum-1;i--)

{
cout< fop }
for(;i>=0;i--)
{
cout<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
fop<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
}
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
数据结构(C++版)哈弗曼 编码
问题描述:利用哈夫曼编码进行信息通讯可以大大提高信道的利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码;在接受端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码编码/译码系统。 基本要求:根据某字符文件统计字符出现频度,构造Huffman 树,编制Huffman编码,并将给定字符文件编码,生成编码文件;再将给定编码文件解码,生成字符文件(要求按二进制位表示编码)。 提高要求:改进Huffman编码,产生两种以上的编码方案,对同一组测试数据,用不同的编码方案编码,并从文件长度、算法复杂度等方面进行比较分析。 测试数据:找一个英文文档文件或中文文档文件。 用C++来编写,能实现基本要求和提高要求的。
数据结构哈弗曼编码,急急急急急急!
在记事本软件中,放入不小于1000个英文字符的文本,命名为source.txt。 编写过程,挑出文本中的不相同字符,输出文件列出每个字符的出现概率。 根据字符列表文件建立字符列表的哈夫曼编码本1 以哈夫曼编码本1为参照,将文本文件source.txt的内容转换为二进制码文件code.dat 以哈夫曼编码本1为参照,将二进制码文件code1.dat的内容解码为target.txt明文 编写函数,对比source.txt和 target.txt是否相同,不同则返回出现不同的位置点。 大学生的数据结构作业,求大神帮忙啊!
C语言哈弗曼树编码,求大神帮我改一下
这是原题和代码,有些错误,运行不出来,求大神帮我改改 实现一个哈夫曼编码系统,系统包括以下功能: (1) 字符信息统计:读取待编码的源文件SourceFile.txt,统计出现的字符及其频率。 (2) 建立哈夫曼树:根据统计结果建立哈夫曼树。 (3) 建立哈夫曼码表:利用得到的哈夫曼树,将各字符对应的编码表保存在文件Code.txt中。 (4) 对源文件进行编码:根据哈夫曼码表,将SourceFile.txt中的字符转换成相应的编码文件ResultFile.txt。 代码 #include<stdio.h> #include<fstream> #include<iostream> using namespace std; int Count(int cou[]) //计算输入的字母的个数 { std fstream SourceFile; char word; char letter[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'}; // fstream SourceFile; SourceFile.open("SourceFile.txt",ios::in); if (!SourceFile) { cout<<"Can't open0 this file"<<endl; } while (!SourceFile.eof()) { SourceFile.get(word); if (word>='A'&&word<='Z') { word=word+32; } int i=word-96; cou[i]++; } SourceFile.close(); cout<<"letter"<<'\t'<<'\t'<<"频率为"<<endl; for (int j=1;j<=26;j++) { if (cou[j]!=0) { cout<<letter[j]<<'\t'<<'\t'<<cou[j]<<endl; } } cout<<"读入完事儿!"<<endl; return 0; } /*-----------选择HT中双亲域为0的权值最小的两个结点--------------*/ void Select(HuffmanTree HT,int i,int &s1,int &s2) { //选择两个最小值,将他们的位序输出到s1,s2 int m=0,k=0; for(k=1;k<=n;++k) //得到第一个父节点为零的节点 { if(0==HT[k].parent) { m=HT[k].weight; s1=k; break; } } for(;k<=n;++k) //得到最小值 { if(0==HT[k].parent && HT[k].weight<m) { m=HT[k].weight; s1=k; } } for(k=1;k<=n;++k) //得到第二个父节点为零的节点 { if(k!=s1 && 0==HT[k].parent) { m=HT[k].weight; s2=k; break; } } for(;k<=n;++k) //求得次小元 { if(0==HT[k].parent && k!=s1 && HT[k].weight<m) { m=HT[k].weight; s2=k; } } }//Select /*---------算法5.10 根据统计结果建立Huffman树-----------*/ void CreatHuffmanTree(HuffmanTree &HT,int cou[]) { if(n<=1) return; int m=2*n-1; HT=new HTNode[m+1]; //0 号单元未用,所以需要动态分配m+1个单元,HT[m]表示根节点 int s1=0,s2=0; // for(int i=1;i<=m;i++) //初始化HuffmanTree 将1~m单元中的双亲,左右孩子的下标初始化为0 { HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; } for(i=1;i<=n;i++) //输入叶节点的权值 HT[i].weight=cou[i-1]; for(i=n+1;i<=m;i++) { Select(HT,i,s1,s2); //选择HT中两个双亲域为0且权值最小的两个节点的序号s1和s2 HT[s1].parent=i; HT[s2].parent=i; //标记其双亲结点为HT[i] HT[i].lchild=s1; HT[i].rchild=s2; //HT[s1]和HT[s2]作为HT[i]的左右孩子 HT[i].weight=HT[s1].weight+HT[s2].weight; //HT[i]的权值为左右孩子权值之和 } cout<<"huffmantree构造完成"<<endl; } /*--------------------算法5.11 根据统计结果对各字符进行编码,并保存在Code.txt中------------------*/ void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC) { int start; char *cd; HC=new char*[n+1]; cd=new char[n]; cd[n-1]='\0'; int i,c,f; for (i=1;i<=n;++i) { start=n-1; c=i;f=HT[i].parent; while(f!=0){ --start; if (HT[f].lchild==c) cd[start]='0'; else cd[start]='1'; c=f; f=HT[f].parent; } HC[i]=new char[n-start]; strcpy(HC[i],&cd[start]); } delete cd; cout<<"HuffmanCode创建完毕"<<endl; } /*----------对SourceFile.txt进行编码,并保存在ResultFile.txt中-----------*/ void Code(HuffmanTree &HT,HuffmanCode &HC) { string alph; ifstream infile("SourceFile.txt"); if(!infile){ cout<<"Cannot open this file!"<<endl; exit(1); } infile>>alph; infile.close(); ofstream outfile; outfile.open("ResultFile.txt"); if(!outfile) cout<<"cannot open the file!"<<endl; else{ for(int i=0;i<alph.length();i++){ int j=alph[i]-97; for(int k=1;k<=n;k++){ if(HT[k].weight==cou[j]) outfile<<HC[k]; } } } cout<<"huffman编码完成"<<endl; outfile.close(); }
C++哈夫曼编码译码器设计与实现并对哈夫曼树进行先序遍历。
现在就是差一个先序遍历的要求没有做到 ``` #include<stdio.h> #include<string.h> #include<stdlib.h> //树结点定义 typedef struct { int weight; int parent; int lchild; int rchild; }HTNode,*HuffmanTree; static char N[100];//用于保存正文 //哈弗曼编码,char型二级指针 typedef char **HuffmanCode; //封装最小权结点和次小权结点 typedef struct { int s1; int s2; }MinCode; //函数声明 void Error(char *message); HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n); MinCode Select(HuffmanTree HT,int n); //当输入1个结点时的错误提示 void Error(char *message) { fprintf(stderr,"Error:%s\n",message); //根据指定的格式,向输出流写入数据 exit(1); } //构造哈夫曼树HT,编码存放在HC中,w为权值,n为结点个数 HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n) { int i,s1=0,s2=0; HuffmanTree p; char *cd; int f,c,start,m; MinCode min; if(n<=1) { Error("Code too small!");//只有一个结点不进行编码,直接exit(1)退出。 } m=2*n-1;//哈弗曼编码需要开辟的结点大小为2n-1 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟哈夫曼树结点空间 m+1 ,动态内存分配。 //初始化n个叶子结点,w[0] = 0,main函数已赋值 for(p=HT,i=0;i<=n;i++,p++,w++) { p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } //将n-1个非叶子结点的初始化 for(;i<=m;i++,p++) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } //构造哈夫曼树 for(i=n+1;i<=m;i++) { min=Select(HT,i-1);//找出最小和次小的两个结点 s1=min.s1 ; //最小结点下标 s2=min.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; } //打印哈弗曼树 printf("HT List:\n"); printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n"); for(i=1;i<=m;i++) { printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); } //从叶子结点到根节点求每个字符的哈弗曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char *));//为哈弗曼编码动态分配空间 cd[n-1]='\0';//如:3个结点编码最长为2。cd[3-1] = '\0'; //求叶子结点的哈弗曼编码 for(i=1;i<=n;i++) { start=n-1; //定义左子树为0,右子树为1 /* 从最下面的1号节点开始往顶部编码(逆序存放),然后编码2号节点,3号...... */ 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'; } //为第i个字符分配编码空间 HC[i]=(char *)malloc((n-start)*sizeof(char *)); //将当前求出结点的哈弗曼编码复制到HC strcpy(HC[i],&cd[start]); } free(cd); return HC; } MinCode Select(HuffmanTree HT,int n) { int min,secmin; int temp = 0; int i,s1,s2,tempi = 0; MinCode code ; s1=1; s2=1; min = 9999; //找出权值最小的结点,下标保存在s1中 for(i=1;i<=n;i++) { if(HT[i].weight<min && HT[i].parent==0) { min=HT[i].weight; s1=i; } } secmin = 9999; //找出权值次小的结点,下标保存在s2中 for(i=1;i<=n;i++) { if((HT[i].weight<secmin) && (i!=s1) && HT[i].parent==0) { secmin=HT[i].weight; s2=i; } } //放进封装中 code.s1=s1; code.s2=s2; return code; } void HuffmanTranslateCoding(HuffmanTree HT, int n,char* ch) {//译码过程 int m=2*n-1; int i,j=0; printf("After Translation:"); while(ch[j]!='\0')//ch[]:你输入的要译码的0101010串 { i=m; while(0 != HT[i].lchild && 0 != HT[i].rchild)//从顶部找到最下面 { if('0' == ch[j])//0 往左子树走 { i=HT[i].lchild; } else//1 往右子树走 { i=HT[i].rchild; } ++j;//下一个路径 } printf("%c",N[i-1]);//打印出来 } printf("\n"); } void main() { HuffmanTree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,n; char tran[100]; printf("Input N(char):"); gets(N); fflush(stdin); n = strlen(N); w=(int *)malloc((n+1)*sizeof(int *));//开辟n+1个长度的int指针空间 w[0]=0; printf("Enter weight:\n"); //输入结点权值 for(i=1;i<=n;i++) { printf("w[%d]=",i); scanf("%d",&w[i]); } fflush(stdin); //清空输入缓冲区 //构造哈夫曼树HT,编码存放在HC中,w为权值,n为结点个数 HC=HuffmanCoding(HT,HC,w,n); //输出哈弗曼编码 printf("HuffmanCode:\n"); printf("Number\t\tWeight\t\tCode\n"); for(i=1;i<=n;i++) { printf("%c\t\t%d\t\t%s\n",N[i-1],w[i],HC[i]); } fflush(stdin); //译码过程 printf("Input HuffmanTranslateCoding:"); gets(tran); HuffmanTranslateCoding(HT, n, tran); return; } ```题目要求:九、哈夫曼编码译码器设计与实现 编写程序设计哈夫曼编码译码器。 (1)根据输入的权值建立哈夫曼树。 (2)对建立好的哈夫曼树进行先序遍历。 (3)利用建好的哈夫曼树生成哈夫曼编码,并显示生成的各字符的哈夫曼编码。 (4)根据输入的字符进行译码。 (5)显示功能:以先序遍历的顺序显示建立好的哈夫曼树。显示哈夫曼编码和译码的结果。
C++用哈弗曼编码实现压缩,编码文件比原文件大是怎么回事,怎么能实现压缩,代码如下,求修改
``` #include<iostream> #include<fstream> #include<string> using namespace std; struct HuffmanNode //树结点类定义 { int weight; //权值 int parent; //双亲 int lchild,rchild; //左右孩子 }; class HuffmanTree //哈夫曼树类定义 { private: struct HuffmanNode *Node; //哈夫曼树中结点的存储结构 char *Info; //用来保存各字符信息的字符数组 int LeafNum; //树中的叶子结点总数 public: HuffmanTree(); //构造函数 ~HuffmanTree(); //析构函数 void Initialization(int WeightNum); //初始化函数 void Encoder(); //编码函数,生成哈夫曼编码 void Decoder(); //译码函数,对二进制串进行译码 void Print(); //输出编码 void TreePrinting(); //输出哈夫曼树 }; HuffmanTree::HuffmanTree() //初始化空树 { Node=NULL; //将树结点初始化为空 Info=NULL; //将字符数组初始化为空 LeafNum=0; //将叶子数初始化为0 } HuffmanTree::~HuffmanTree() //析构函数 { delete[] Node; //释放结点空间 delete[] Info; //释放字符存储空间 } //初始化函数 void HuffmanTree::Initialization(int WeightNum) { int i,j,pos1,pos2,max1,max2; Node=new HuffmanNode[2*WeightNum-1]; //为哈夫曼树所需的结点申请空间 Info=new char[2*WeightNum-1]; for(i=0;i<WeightNum;i++) //先构造weightnum个点 { cout<<"请输入第"<<i+1<<"个字符值"; cin>>Info[i]; cout<<"请输入该字符的权值或频度"; cin>>Node[i].weight; //输入权值 Node[i].parent=-1; //为根结点 Node[i].lchild=-1; //无左孩子 Node[i].rchild=-1; //无右孩子 } //这里构造出weightnum个带权结点 for(i=WeightNum;i<2*WeightNum-1;i++) { pos1=-1; pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号 max1=32767; //32767为整型数的最大值 max2=32767; for(j=0;j<i;j++) if(Node[j].parent==-1) if(Node[j].weight<max1) { max2=max1; //原最小值变为次小值 max1=Node[j].weight; //存放最小值 pos2=pos1; //修改次小值所在单元编号 pos1=j; //修改最小值所在单元编号 } else if(Node[j].weight<max2) { max2=Node[j].weight; //存放次小值 pos2=j; //修改次小值所在的单元编号 } Node[pos1].parent=i; //修改父亲位置 Node[pos2].parent=i; Node[i].lchild=pos1; //修改儿子位置 Node[i].rchild=pos2; Node[i].parent=-1; //表示新结点应该是根结点 Node[i].weight=Node[pos1].weight+Node[pos2].weight; } LeafNum=WeightNum; char ch; cout<<"是否要替换原来文件(y/n):"; cin>>ch; if(ch=='y'||ch=='Y') { ofstream fop; //以二进制方式打开hfmTree.dat文件,并当重新运行时覆盖原文件 fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); if(fop.fail()) //文件打开失败 cout<<"文件打开失败!\n"; fop.write((char*)&WeightNum,sizeof(WeightNum)); //写入WeightNum for(i=0;i<WeightNum;i++) //把各字符信息写入文件 { fop.write((char*)&Info[i],sizeof(Info[i])); flush(cout); } for(i=0;i<2*WeightNum-1;i++) //把各节点内容写入文件 { fop.write((char*)&Node[i],sizeof(Node[i])); flush(cout); } fop.close(); //关闭文件 } cout<<"哈夫曼树已构造完成。\n"; } //编码函数 void HuffmanTree::Encoder() { if(Node==NULL) { ifstream fip; fip.open("hfmTree.dat",ios::binary|ios::in); //以二进制方式打开hfmTree.dat文件 if(fip.fail()) //文件打开失败 { cout<<"文件打开失败!\n"; return; //结束本函数 } fip.read((char*)&LeafNum,sizeof(LeafNum)); //读取叶子数 Info=new char[LeafNum]; Node=new HuffmanNode[2*LeafNum-1]; for(int i=0;i<LeafNum;i++) //读取字符信息 fip.read((char*)&Info[i],sizeof(Info[i])); for(int i=0;i<2*LeafNum-1;i++) //读取结点信息 fip.read((char*)&Node[i],sizeof(Node[i])); } char *Tree; //用于存储需编码内容 int i=0,num; char Choose; cout<<"从文件中读取内容的请选择1,需要重新输入的请选择2:"; cin>>Choose; if(Choose=='1') //读取文件ToBeTran.txt { ifstream fip1("ToBeTran.txt"); if(fip1.fail()) //文件不存在 { cout<<"文件打开失败!\n"; return; //结束本函数 } char ch; int k=0; while(fip1.get(ch)) { k++; } fip1.close(); Tree=new char[k+1]; ifstream fip2("ToBeTran.txt"); k=0; while(fip2.get(ch)) { Tree[k]=ch; //读取文件内容,并存到Tree中 k++; } fip2.close(); Tree[k]='\0'; //结束标志 cout<<"需编码内容为:"<<Tree<<endl; } //if(Choose=='2') else { string tree; cin.ignore(); cout<<"请输入需要编码的内容(可输入任意长,结束时请按2下回车):\n"; getline(cin,tree,'\n'); //输入任意长字符串, while(tree[i]!='\0') i++; num=i; //计算tree长度 i=0; Tree=new char[num+1]; while(tree[i]!='\0') //将tree中的字符转存到Tree中 { Tree[i]=tree[i]; i++; } Tree[i]='\0'; //结束标志符 } ofstream fop("CodeFile.dat",ios::trunc); i=0; int k=0; char *code; code=new char[LeafNum]; //为所产生编码分配容量为LeafNum的存储空间 while(Tree[k]!='\0') //对每一个字符编码 { int j,start=0; for(i=0;i<LeafNum;i++) if(Info[i]==Tree[k]) break; j=i; while(Node[j].parent!=-1) //结点j非树根 { j=Node[j].parent; //求结点j的双亲结点 if(Node[j].lchild==i) //是左子树,则生成代码0 code[start++]='0'; else code[start++]='1'; //是右子树,则生成代码1 i=j; } code[start]='\0'; //置串结束符 for(i=0;i<start/2;i++) //对二进制序列进行逆置 { j=code[i]; code[i]=code[start-i-1]; code[start-i-1]=j; } i=0; while(code[i]!='\0') //存储代码 { fop<<code[i]; i++; } k++; } fop.close(); cout<<"编码完成!且存到文件CodeFile.dat中!\n\n"; } //解码函数 void HuffmanTree::Decoder() { int i=0,k=0; int j=LeafNum*2-1-1; char* BitStr; ifstream fip1("CodeFile.dat"); //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码 if(fip1.fail()) { cout<< "请先编码!\n"; return; } cout<<"经译码,原内容为:"; char ch; while(fip1.get(ch)) { k++; } fip1.close(); BitStr=new char[k+1]; ifstream fip2("CodeFile.dat"); k=0; while(fip2.get(ch)) { BitStr[k]=ch; //读取文件内容 k++; } fip2.close(); BitStr[k]='\0'; //结束标志符 if(Node==NULL) //还未建哈夫曼树 { cout<<"请先编码!\n"; return; } ofstream fop("TextFile.dat"); //将字符形式的编码文件写入文件CodePrin中 while(BitStr[i]!='\0') { if(BitStr[i]=='0') j=Node[j].lchild; //往左走 else j=Node[j].rchild; //往右走 if(Node[j].rchild==-1) //到达叶子结点 { cout<<Info[j]; //输出叶子结点对应的字符 j=LeafNum*2-1-1; fop<<Info[j]; //存入文件 } i++; } fop.close(); cout<<"\n译码成功且已存到文件TextFile.dat中!\n\n"; } //输出编码函数 void HuffmanTree::Print() { char ch; int i=1; ifstream fip("CodeFile.dat"); ofstream fop("CodePrin.dat"); if(fip.fail()) { cout<<"没有文件,请先编码!\n"; return; } while(fip.get(ch)) { cout<<ch; //读取文件内容 fop<<ch; //存到文件中 if(i==50) { cout<<endl; i=0; } i++; } cout<<endl; fip.close(); //关闭CodeFile.dat文件 fop.close(); //关闭CodePrin.dat文件 } //输出哈夫曼树 void HuffmanTree::TreePrinting() { if(Node==NULL) { cout<<"请先建立哈夫曼树!\n"; return; } ofstream fop("TreePrint.dat"); cout<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n"; fop<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n"; int i; for(i=(2*LeafNum-2);i>LeafNum-1;i--) { cout<<i<<"("<<Node[i].weight<<")"<<"--1--" <<Node[i].lchild<<"("<<Node[Node[i].lchild].weight<<")"<<"--0--" <<Node[i].rchild<<"("<<Node[Node[i].rchild].weight<<")"<<endl; fop<<i<<"("<<Node[i].weight<<")"<<"--1--" <<Node[i].lchild<<"("<<Node[Node[i].lchild].weight<<")"<<"--0--" <<Node[i].rchild<<"("<<Node[Node[i].rchild].weight<<")"<<endl; } for(;i>=0;i--) { cout<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n"; fop<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n"; } } int main() { cout<<"~~~~~~~~~~~~~welcome to Huffman encodrding&decoding system ~~~~~~~~~~~~~~~~~~~~\n\n"; cout<<"You can choose 1--6 options:\n"; cout<<"(1)初始化 \n"; cout<<"(2) 编码\n"; cout<<"(3) 译码\n"; cout<<"(4) 输出编码\n"; cout<<"(5) 输出哈弗曼树\n"; cout<<"(6) Byebye~!\n\n"; HuffmanTree HT; int weight; int choice; int OK=0; while ( !OK ) { cout<<"Please input your option (1--6):"; cin>> choice; switch( choice) { case 1: cout<<"Please input your code lenth"<<endl; cin>>weight; HT.Initialization(weight); break; case 2: HT.Encoder(); break; case 3: HT.Decoder(); break; case 4: HT.Print();break; case 5: HT.TreePrinting();break; case 6: cout<<"\n***********Thanks for Using!***********\n"; OK=1; break; return 0; } cout<<"(1)初始化\n"; cout<<"(2)编码\n"; cout<<"(3)译码\n"; cout<<"(4)打印哈弗曼编码\n"; cout<<"(5)打印哈弗曼树\n"; cout<<"(6) Byebye~!\n\n"; } return 0; } ```
修改程序:信源编解码(c语言)
修改程序:问题1。源文件source文本空间太长汉字太多无法运行2,未按频度要求排序 问题描述: 信源编解码是通信系统的重要组成部分。本实验旨在通过程序设计实现基于哈夫曼编码的信源编解码算法。程序具备以下功能: 对于给定的源文档 SourceDoc.txt, 1) 统计其中所有字符的频度(某字符的频度等于其出现的总次数除以总字符数) , 包括字母(区分大小写) 、标点符号及格式控制符(空格、回车等) 。 2) 按频度统计结果生成哈夫曼编码码表。 3) 基于哈夫曼码表进行编码,生成对应的二进制码流,并输出到文件 Encode.dat。 4) 对二进制码流进行哈夫曼解码,把结果输出到文件 DecodeDoc.txt。 5) 判断DecodeDoc.txt与SourceDoc.txt内容是否一致,以 验证编解码系统的正确性。 要求: 1) 用 C 语言实现。 2) 用子函数实现各功能模块。 3) 输出文件 Statistic.txt,包含的信息有:按频度大小排序的字符表,及各字符出现 的次数、频度及哈夫曼编码。 4) 应至少包含链表、二叉树的数据结构。 5) 不能用冒泡排序算法。 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<sys/stat.h> #include<sys/types.h> #include<fcntl.h> #include<unistd.h> #include<errno.h> #define N 10000 int count = 0; //每增加一个新的字符, count增加1, 可表示a中的字符种类数, 也即哈夫曼树叶子点个数 /*定义哈夫曼树结构体*/ typedef struct HuffmanTree{ int weight; int parent; int Lchild; int Rchild; }HuffmanTree[2*N]; /*定义储存字符及其出现次数的结构体*/ typedef struct DifferentCharacter{ char char_date; int num; //相同字符出现的次数 char a_code[100]; //每种字符对应的编码 }difcha[N]; /*在一定范围内选择两个weight最小的结点, 并将两个结点的序号赋给s1, s2*/ void select_two(HuffmanTree ht, int j, int *s1, int *s2) { int i = 1, temp; int min1 = 0, min2 = 0; while( (ht[i].parent != 0) && (i <= j) ) i++; *s1 = i; min1 = ht[i++].weight; while( (ht[i].parent != 0) && (i <= j) ) i++; *s2 = i; min2 = ht[i++].weight; if(min1 > min2){ temp = min1; min1 = min2; min2 = temp; } for(; i <= j; i++){ //遍历parent不为0的结点 if(ht[i].parent != 0) continue; if(ht[i].weight <= min1){ min2 = min1; min1 = ht[i].weight; *s2 = *s1; *s1 = i; } else if( (ht[i].weight < min2) && (ht[i].weight > min1) ) { min2 = ht[i].weight; *s2 = i; } } } /*建哈夫曼树*/ void EstHuffmanTree(HuffmanTree ht, int *w, int n){ int i; int s1 = 0, s2 = 0; for(i = 1; i <= n; i++){ //初始化哈夫曼树, 前n个单元存放叶子点 ht[i].weight = w[i]; ht[i].parent = 0; ht[i].Lchild = 0; ht[i].Rchild = 0; } for(i = n+1; i <= 2*n-1; i++){ //后n-1个单元存放非叶子点 ht[i].weight = 0; ht[i].parent = 0; ht[i].Lchild = 0; ht[i].Rchild = 0; } for(i = n+1; i <= 2*n-1; i++){ select_two(ht, i-1, &s1, &s2); //创建非叶子点, 建立哈夫曼树, 每次在ht[1]~ht[i-1]范围内选两个最小的weight结点,并将其序号赋给s1, s2 ht[i].weight = ht[s1].weight + ht[s2].weight; ht[i].Lchild = s1; ht[i].Rchild = s2; ht[s1].parent = i; ht[s2].parent = i; } //哈夫曼树建立完毕 } /*求哈弗曼编码*/ void CrtHuffmanCode(HuffmanTree ht, char **hcd, int n){ int start = 0, c = 0, p = 0, i; char *cd = (char*)malloc(n*sizeof(char)); //分配求当前编码的工作空间 cd[n-1] = '\0'; //从左向右存放编码 for(i = 1; i <= n; i++) { start = n-1; //初始化编码起始指针 c = i; p = ht[i].parent; while(p != 0){ start--; if(ht[p].Lchild == c) cd[start] = '0'; //左分支标0 else cd[start] = '1'; //右分支标1 c = p; //向上倒推 p = ht[c].parent; } hcd[i] = (char*)malloc((n-start)*sizeof(char)); strcpy(hcd[i], &cd[start]); } free(cd); } /*自定义错误处理函数*/ void my_err(char *err_string, int line){ printf("Line %d:\n", line); perror(err_string); exit(1); } /*从 buf_read 中统计每个字符出现的次数,将次数作为该字符的权值*/ void Statistics(difcha a, char *buf_read){ int i, j = 0; for(i = 0; i < strlen(buf_read) ; i++){ //对buf_read中的字符遍历 for(j = 0; j < count; j++){ //检查是否是新的字符 if(a[j].char_date == buf_read[i]){ a[j].num++; //若是旧字符, 则num++; break; } } if(j == count){ //若是新字符, 则记录到a中, 且对应的num++ a[count].char_date = buf_read[i]; a[count].num++; count++; //更新count } } } /*从 SourceDoc.txt 读取数据到 buf_read */ void ReadFile(char *pathName, char *buf_read){ int fd_date; int len = 0; if( (fd_date = open(pathName, O_RDWR)) < 0) //以读写方式打开SourceDoc.txt文件 my_err("open SourceDoc.txt", __LINE__); if(lseek(fd_date, 0, SEEK_END) < 0) //获取文件长度,并保持文件读写指针在文件开始处 my_err("lseek", __LINE__); if( (len = lseek(fd_date, 0, SEEK_CUR)) < 0 ) my_err("lseek", __LINE__); if(lseek(fd_date, 0, SEEK_SET) < 0) my_err("lseek", __LINE__); if(read(fd_date, buf_read, len) > len) //从SourceDoc.txt中读取内容 my_err("read SourceDoc.txt", __LINE__); } /*将 buf_code 写入 Encode.dat 中*/ void WriteFile(char *pathName, char *buf_code){ int fd_code; if((fd_code = open(pathName, O_CREAT|O_TRUNC|O_RDWR, S_IRWXU)) < 0) //创建Encode.dat文件 my_err("open Encode.dat", __LINE__); if( write(fd_code, buf_code, strlen(buf_code)) != strlen(buf_code) ) //将 buf_code 写入Encode.dat my_err("write Encode.dat", __LINE__); } /*主函数*/ void main(){ char buf_read[N] = {'\0'}; char buf_code[N] = {'\0'}; char buf_yima[N] = {'\0'}; char *hcd[N]; char temp[50] = {'\0'}; difcha a; int i, j, n, k = 0, m = 0; int w[N] = {0}; HuffmanTree ht; ReadFile("SourceDoc.txt", buf_read); Statistics(a, buf_read); for(i = 0; i < count; i++) w[i+1] = a[i].num; EstHuffmanTree(ht, w, count); //建HuffmanTree CrtHuffmanCode(ht, hcd, count); //对树中字符进行编码 for(i = 1; i <= count; i++) //将每个字符对应的编码存入结构体 a 中 strcpy(a[i-1].a_code, hcd[i]); FILE *fp1; fp1=fopen("Statistic.txt","w"); for(i = 0; i < count; i++) //查看每个字符的权值和对应的编码 fprintf(fp1,"%c %d %s\n", a[i].char_date, a[i].num, a[i].a_code); fclose(fp1); for(i = 0; i < strlen(buf_read) ; i++){ //遍历 buf_read, 给 SourceDoc.txt 中每个字符匹配编码, 存入 buf_code 中 for(j = 0; j < count; j++){ if(buf_read[i] == a[j].char_date){ strcat(buf_code, a[j].a_code); break; } } if(j == count) //匹配异常 printf("Unknown Character: %c\n", buf_read[i]); } WriteFile("Encode.dat", buf_code); //将 buf_code 写入 Encode.dat 中 ReadFile("Encode.dat", buf_read); //从 Encode.dat 中读取全部编码 n = strlen(buf_read); for(i = 0; i < n; i++){ //为 Encode.dat 中的编码匹配字符 temp[k++] = buf_read[i]; for(j = 0; j < count; j++){ if(strcmp(temp, a[j].a_code) == 0){ buf_yima[m++] = a[j].char_date; break; } } if(j < count){ //匹配成功, 对 temp 初始化 for(;k > 0; k--) temp[k] = '\0'; } } FILE *fp2; fp2=fopen("DecodeDoc.txt","w"); fprintf(fp2,"%s", buf_yima); fclose(fp2); }
哈弗曼编码,从根到叶子,权值从数组为0开始,会出问题,以下代码,知道问题出现在下标为0的权值无法编码
``` while(p1) { if(HT[p1].weight==0) //向左 { HT[p1].weight=1; if(HT[p1].lchild!=0) { p1=HT[p1].lchild; printf("p1为%d \n",p1); cd[cdlen]='0'; cdlen++; } else if(HT[p1].lchild==0&&HT[p1].rchild==0) //登记叶子结点的字符编码 { HC[p1]=(char *)malloc(cdlen*sizeof(char)); cd[cdlen]='\0'; strcpy(HC[p1],cd); //复制编码串 printf("HC的值%s\n",HC[p1]); } } else if(HT[p1].weight==1) //向右 { HT[p1].weight=2; if(HT[p1].rchild!=0) { p1=HT[p1].rchild; cd[cdlen]='1'; cdlen++; } } else //HT[p1].weight==2,退回 { HT[p1].weight=0; p1=HT[p1].parent; --cdlen; //退到父节点,编码长度减1 } } ```
哈弗曼进行译码的时候怎么最后得到的是原来编码前的短文顺序,跪求指点
哈弗曼进行译码的时候怎么最后得到的是原来编码前的短文顺序,跪求指点
跪求大神 帮忙,这段关于哈夫曼编码 的程序着实看不懂啊。。。。。。。
struct Codetype{//哈弗曼编码数据类型 char *bits;//编码流-数组,n为为哈夫曼树中叶子结点的数目,编码的长度不可能超过n int start;//编码实际在编码流数组里的开始位置 }; Codetype *HuffmanCode(hufmtree *tree){//哈弗曼编码的生成 int i,j,p,k; Codetype *code; if(tree==NULL) return NULL; code=(Codetype*)malloc(tree->n*sizeof(Codetype));//把tree的n个叶子节点生成哈夫曼码 for(i=0;i<tree->n;i++) { printf("%c",tree->node[i].data);//打印字符信息 code[i].bits=(char*)malloc(tree->n*sizeof(char)); code[i].start=tree->n-1; j=i; p=tree->node[i].parent; while(p!=-1){ if(tree->node[p].lchild==j) code[i].bits[code[i].start]='0'; else code[i].bits[code[i].start]='1'; code[i].start--; j=p; p=tree->node[p].parent; } for(k=code[i].start+1;k<tree->n;k++)//打印字符编码 printf("%c",code[i].bits[k]); printf("\n"); } return code; }
新手哈弗曼树访问出错求大神改一下
#include<iostream>#include"stdio.h"#include<string>#include<conio.h>#include<fstream>#include <vector>using namespace std;const int Ml = 10;const int Mv = 10;const int Mn = Ml * 2 - 1;const int Mb = 100;typedef struct { string s; int weight; int parent; int lchild; int rchild; string code;}HNodeType;struct assist{ int weight; int num; };HNodeType *HaffmanTree(int n, HNodeType HuffNode[]){ int i, j, N; N = n; for (i = 0; i<2 * n - 1; i++){ /*HuffNode[i].s = '0';*/ HuffNode[i].weight = 0; HuffNode[i].parent = -1; HuffNode[i].lchild = -1; HuffNode[i].rchild = -1; HuffNode[i].code = '1'; } cout << "请输入" << n << "个权值:" << endl; for (i = 0; i<n; i++){ cin >> HuffNode[i].weight; //输入n个叶子结点的权值 } ofstream outfile; outfile.open("e:\\hftree.dat"); if (!outfile){ cerr << "打开文件失败!" << endl; return 0; } cout << "请输入" << n << "个字符:" << endl; string str; getchar(); getline(cin, str,'\n'); for (i = 0; i < n; i++){ HuffNode[i].s = str[i]; } outfile << str; outfile.close(); int temp; string temp2; for (j = 0; j < n - 1; j++){ for (i = 0; i < n - 1; i++){ if (HuffNode[i].weight<HuffNode[i + 1].weight){ temp = HuffNode[i].weight; HuffNode[i].weight = HuffNode[i + 1].weight; HuffNode[i + 1].weight = temp; temp2 = HuffNode[i].s; HuffNode[i].s = HuffNode[i + 1].s; HuffNode[i + 1].s = temp2; } } } for (i = 0; i < n - 1; i++)//code赋值 {HuffNode[i].code = '0';} //------------------------------------------------------------------------------------ assist a[Mn]; int m; assist temp3; for (m = 0; m<n - 1; m++){ a[m].weight = HuffNode[m].weight; a[m].num = m; } while (m>=1){ HuffNode[n].weight = a[m].weight + a[m - 1].weight; HuffNode[n].lchild = a[m - 1].num; HuffNode[n].rchild = a[m].num; HuffNode[a[m].num].parent = n; HuffNode[a[m - 1].num].parent = n; m--; a[m].weight = HuffNode[n].weight; a[m].num = n; n++; for (j = 0; j <= m; j++){ for (i = 0; i <= m; i++){ if (a[i].weight < a[i + 1].weight){ temp3 = a[i]; a[i] = a[i + 1]; a[i + 1] = temp3; } } } } //-------------------------------------------------------------------------------- /*for (i = n - 1; i > 0; i--, n++){ HuffNode[n].weight = HuffNode[n - 1].weight + HuffNode[i - 1].weight; HuffNode[n].rchild = n - 1; HuffNode[n].lchild = i - 1; HuffNode[n - 1].parent = n; HuffNode[i - 1].parent = n; }*/ cout << "哈弗曼树结构:" << endl; for (i = 0; i < 7; i++) cout << HuffNode[i].code << '\t' << HuffNode[i].s << '\t' << HuffNode[i].weight << '\t' << HuffNode[i].lchild << '\t' << HuffNode[i].rchild << '\t' << HuffNode[i].parent << endl; return HuffNode;}void Hfcode(HNodeType a[],int n){ vector <string> cd(n);//叶子节点编码 int i = 0; while (i != n){ int b = 1; int j = a[0].parent; while(b<=i){ j = a[j].rchild; cd[i] += a[j].code; b++; } if(a[j].lchild!=-1) cd[i] += '0'; else cd[i] += '1'; i++; } ofstream outfile; outfile.open("e:\\hfcode.dat"); if (!outfile){ cerr << "打开文件失败!" << endl; } for (i = 0; i < n; i++){ outfile << cd[i]; } outfile.close();}void Translate(HNodeType a[],int n){ ifstream infile; string ss; infile.open("e:\\hfcode.dat"); infile >> ss; //cout << ss; infile.close(); cout << '\n' << "从e:\\hfcode.dat中获取编码串为:" << ss << ",将其译码:" << '\n' << endl; cout << "字符编码" << '\t' << "译码" << endl; int i = 0, m = ss.size(), j = a[0].parent; while (i<m-1){ cout << ss[i]; if (ss[i] == '0'){ j = a[j].lchild; cout <<'\t'<<'\t'; cout << a[j].s << endl; j=a[0].parent; } if (ss[i] == '1'){ j = a[j].rchild; if (a[j].rchild==-1){ cout << '\t' << '\t'; cout << a[j].s << endl; } } i++; }}int main(){ int n; cout << "输入叶子节点的个数" << endl; cin >> n; HNodeType HuffNode[Mn]; HaffmanTree(n, HuffNode); Hfcode(HuffNode, n); Translate(HuffNode,n); _getch();}
哈弗曼树的问题,代码如下,求详细解释。答辩需要,但我一点也不懂,急求
int Count(int cou[]) //计算输入的字母的个数 { char word; char letter[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'}; fstream SourceFile; SourceFile.open("SourceFile.txt",ios::in); //从SourceFile.txt读取 if (!SourceFile) { cout<<"Can't open this file"<<endl; } while (!SourceFile.eof())//循环直到文件结束 { SourceFile.get(word); if (word>='A'&&word<='Z')//如果是大写字母,统一转换为小写 { word=word+32;//32是 'a' - 'A' ascii差 } int i=word-96;// 96是'a'的ascii cou[i]++; // cou保存你对应字母的统计数字,+1 } SourceFile.close();//关闭文件 cout<<"letter"<<'\t'<<'\t'<<"频率为"<<endl;//输出 for (int j=1;j<=26;j++)//依次输出a~z字符的出现频率 { if (cou[j]!=0)//如果没有这个字母出现,就不输出 { cout<<letter[j]<<'\t'<<'\t'<<cou[j]<<endl; //letter[j]可以用 (char)('A' + i) 代替 } } cout<<"读入完事儿!"<<endl; return 0; } /*-----------选择HT中双亲域为0的权值最小的两个结点--------------*/ void Select(HuffmanTree HT,int i,int &s1,int &s2) //自定义函数 { //选择两个最小值,将他们的位序输出到s1,s2 int m=0,k=0; for(k=1;k<=n;++k) //得到第一个父节点为零的节点,++k先自加,再运算 { if(0==HT[k].parent) { m=HT[k].weight; s1=k; break; } } for(;k<=n;++k) //得到最小值 { if(0==HT[k].parent && HT[k].weight<m) //权<m { m=HT[k].weight; s1=k; } } for(k=1;k<=n;++k) //得到第二个父节点为零的节点 { if(k!=s1 && 0==HT[k].parent) { m=HT[k].weight; s2=k; break; } } for(;k<=n;++k) //求得次小元 { if(0==HT[k].parent && k!=s1 && HT[k].weight<m) { m=HT[k].weight; s2=k; } } }//Select /*---------算法5.10 根据统计结果建立Huffman树-----------*/ void CreatHuffmanTree(HuffmanTree &HT,int cou[]) { if(n<=1) return; int m=2*n-1; HT=new HTNode[m+1]; //0 号单元未用,所以需要动态分配m+1个单元,HT[m]表示根节点 int s1=0,s2=0; // for(int i=1;i<=m;i++) //初始化HuffmanTree 将1~m单元中的双亲,左右孩子的下标初始化为0 { HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; } for(i=1;i<=n;i++) //输入叶节点的权值 HT[i].weight=cou[i-1]; for(i=n+1;i<=m;i++) { Select(HT,i,s1,s2); //选择HT中两个双亲域为0且权值最小的两个节点的序号s1和s2 HT[s1].parent=i; HT[s2].parent=i; //标记其双亲结点为HT[i] HT[i].lchild=s1; HT[i].rchild=s2; //HT[s1]和HT[s2]作为HT[i]的左右孩子 HT[i].weight=HT[s1].weight+HT[s2].weight; //HT[i]的权值为左右孩子权值之和 } cout<<"huffmantree构造完成"<<endl; } /*--------------------算法5.11 根据统计结果对各字符进行编码,并保存在Code.txt中------------------*/ void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC) { int start; char *cd; HC=new char*[n+1]; cd=new char[n]; cd[n-1]='\0'; int i,c,f; for (i=1;i<=n;++i) { start=n-1; c=i;f=HT[i].parent; while(f!=0){ --start; if (HT[f].lchild==c) cd[start]='0'; else cd[start]='1'; c=f; f=HT[f].parent; } HC[i]=new char[n-start]; strcpy(HC[i],&cd[start]); } delete cd; cout<<"HuffmanCode创建完毕"<<endl; } /*----------对SourceFile.txt进行编码,并保存在ResultFile.txt中-----------*/ void Code(HuffmanTree &HT,HuffmanCode &HC) { string alph; ifstream infile("SourceFile.txt"); if(!infile){ cout<<"Cannot open this file!"<<endl; exit(1); } infile>>alph; infile.close(); ofstream outfile; outfile.open("ResultFile.txt"); if(!outfile) cout<<"cannot open the file!"<<endl; else{ for(int i=0;i<alph.length();i++){ int j=alph[i]-97; for(int k=1;k<=n;k++){ if(HT[k].weight==cou[j]) outfile<<HC[k]; } } } cout<<"huffman编码完成"<<endl; outfile.close(); }
学校程序设计实习 刚学了几天MFC 调试的时候出现了错误
![图片说明](https://img-ask.csdn.net/upload/201607/11/1468249717_447162.png) 主要是制作哈弗曼树的窗口 想利用文件在对话框上显示,其它函数里这样用没错,一到这个函数就出错了,而且这个文件只在这个函数中使用了,我是小小白 求大神不吝指教 void printNodeCode(HTNode htnode[], HTCode htcode[], int n) //输出每个结点的编码 { int i,k; int num = 0; FILE *fp = fopen("printNodeCode.txt","w"); for (i = 0; i<=n; i++) { //逐个输出字符对应的哈弗曼编码 // printf("%c:", htnode[i].data); //输出字符 fprintf(fp,"%c:",htnode[i].data);//将编码读入printNodeCode.txt for (k = htcode[i].start; k <= n; k++) { // printf("%c", htcode[i].code[k]); //输出编码 fprintf(fp,"%c",htcode[i].code[k]);//将编码读入printNodeCode.txt } fprintf(fp,"\n");//将编码读入printNodeCode.txt // cout<<endl; } cout<<endl; fclose(fp); }
构建一个哈弗曼树,并计算其带权路径长度
不知道是哪里出现了问题,运行结果不对,并且一点调试就直接结束了,麻烦大神们帮我看一下 ``` # include <stdio.h> static int h = 0; typedef struct tree { char data; int quan; bool min; struct tree* zuo; struct tree* you; }tree; struct hafmman { char data; char lujing[11]; }hafu[100]; void gettree(tree* a,int shij,int youx) { int c = 0; tree temp; if (youx*2-1 != shij) { printf("请输入合法参数"); return; } while (youx!=shij) { for (int i=c;i<shij;++i) { if (a[c].quan>a[i].quan) { temp = a[i]; a[i] = a[c]; a[c] = temp; } if (a[c+1].quan>a[i].quan) { temp = a[i]; a[i] = a[c+1]; a[c+1] = temp; } } a[youx].quan = a[c].quan + a[c+1].quan; a[youx].zuo = &a[c]; a[youx].you = &a[c+1]; youx++; c=c+2; } } int bianltree(tree * tr,char* ch,int deep) { static int i = 0; int j = 0; int sum = 0; if (!tr->min) { ch[i++] = '0'; sum += bianltree(tr->zuo,ch,deep+1); ch[i++] = '1'; sum += bianltree(tr->you,ch,deep+1); } if (tr->min) { ch[i] = '\0'; printf("%c : %s",tr->data,ch); hafu[h].data = tr->data; while (i!=j || i>10) { hafu[h].lujing[j] = ch[j]; j++; } h++; i--; sum = tr->quan * deep; } return sum; } int main () { tree a[9] = {{'a',5,true},{'b',4,true},{'c',2,true},{'d',6,true},{'e',2,true}}; gettree(a,9,5); char ch[100]; int sum = bianltree(&a[8],ch,0); printf("%d",sum); return 0; } ```
哈弗曼树为什么第二个和第四个节点会交换,请帮忙看看代码
#include<iostream> using namespace std; typedef struct { int Weight; bool paixflag; bool flag; int par; int lch; int rch; }HuffNode,*pHuffNode; typedef struct { int n; int root; HuffNode *Huf; }HuffTree,*pHuffTree; HuffTree * InitHuffman(int w[],int n){ if(n<0) return NULL; HuffTree *Tree = new HuffTree(); Tree->n = n; Tree->Huf = new HuffNode[2*n-1]; for(int i=0;i<2*n-1;i++){ Tree->Huf[i].flag = 0; Tree->Huf[i].lch = -1; Tree->Huf[i].rch = -1; Tree->Huf[i].par = -1; Tree->Huf[i].Weight = (i<n)?w[i]:999999; } return Tree; } void GetSmallTwo(HuffNode *Num,int n,int &m1,int &m2){//每次取得新数组的两个flag为0的最小值 for(int i=0;i<2*n-1;i++){ for(int j=i+1;j<2*n-1;j++){ if(Num[i].Weight>Num[j].Weight){ int temp = Num[i].Weight; Num[i].Weight = Num[j].Weight; Num[j].Weight = temp; } } } for(int i=0;i<2*n-1;i++){ if(Num[i].flag==0){ m1 = Num[i].Weight; m2 = Num[i+1].Weight; break; } } } HuffTree* CreateHuffman(int w[],int n){ HuffTree *HTree = InitHuffman(w,n); int i = 0,j = 0,m1 = 0,m2 = 0,x1,x2; for(i=0;i<n-1;i++){ GetSmallTwo(HTree->Huf,n,m1,m2); x1 = 0;x2 = 0; for(j=0;j<n+i;j++){ if(!HTree->Huf[j].flag){ if(HTree->Huf[j].Weight==m1){ x1 = j; cout<<endl<<"x1-->"<<x1<<endl; }else if(HTree->Huf[j].Weight==m2){ x2 = j; cout<<endl<<"x2-->"<<x2<<endl; } } } HTree->Huf[x1].par = n+i; HTree->Huf[x2].par = n+i; HTree->Huf[x2].flag = 1; HTree->Huf[x1].flag = 1; HTree->Huf[n+i].Weight = HTree->Huf[x1].Weight+HTree->Huf[x2].Weight; HTree->Huf[n+i].lch = x1; HTree->Huf[n+i].rch = x2; } return HTree; } int main(){ int num[7] = {3,1,7,5}; HuffTree *Tree = /*InitHuffman(num,10);//*/CreateHuffman(num,4); cout<<"[K]"<<"Weight "<<"LRCHIL "<<"RRCHIL "<<"PARENT "<<"flag "<<endl; for(int i=0;i<7;i++){ cout<<"["<<i<<"] "<<Tree->Huf[i].Weight<<" "<<Tree->Huf[i].lch<<" "<<Tree->Huf[i].rch<<" "<<Tree->Huf[i].par<<" "<<Tree->Huf[i].flag<<endl; } /*for(int i=0;i<10;i++){ cout<<cout<<"HTree->Huf["<<i<<"].Weight-->"<<Tree->Huf[i].Weight<<endl; cout<<i<<"--->flag"<<Tree->Huf[i].flag<<endl; cout<<i<<"--->son"<<Tree->Huf[i].lch<<endl; } int m1,m2; GetSmallTwo(Tree->Huf,10,m1,m2); cout<<m1<<" "<<m2<<endl; GetSmallTwo(Tree->Huf,10,m1,m2); cout<<m1<<" "<<m2<<endl; GetSmallTwo(Tree->Huf,10,m1,m2); cout<<m1<<" "<<m2<<endl; GetSmallTwo(Tree->Huf,10,m1,m2); cout<<m1<<" "<<m2<<endl; GetSmallTwo(Tree->Huf,10,m1,m2); cout<<m1<<" "<<m2<<endl; for(int i=0;i<10;i++){ cout<<cout<<"HTree->Huf["<<i<<"].Weight-->"<<Tree->Huf[i].Weight<<endl; cout<<i<<"--->flag"<<Tree->Huf[i].flag<<endl; cout<<i<<"--->son"<<Tree->Huf[i].lch<<endl; }*/ system("pause"); return 0; }
下面的这段代码什么意思,帮忙看一下,谢谢!!!
``` void BianMa(MyTreeNode* mtns[]) { MyTreeNode* curr; string codes; char* code = new char[size]; for (int i = 0; i < size; i++) { code[i] = '2'; } for (int i = 0; i < size; i++) { int j = 1; cout<<mtns[i]->data<<"的哈弗曼编码为:"; curr = mtns[i]; while (curr->isfather == true) { curr = curr->father; if (curr->isfather == true){ code[j++] = curr->code; } } code[0] = mtns[i]->code; //cout<<mtns[i]->code<<endl; /*for (int k = j-1; k >= 0; k--) { if (code[k] != '2'){ cout<<code[k]<<" "; } }*/ char c[j]; //cout<<endl<<j<<endl; int count = 0; for (int l = j-1; l >=0; l--) { if (code[l] != '2') { c[count++] = code[l]; //cout<<code[l]<<endl; } } for (int x = 0; x < j; x++) { mtns[i]->codes += c[x]; } cout<<mtns[i]->codes<<endl; cout<<endl; } } ``` 帮忙解释一下这段代码什么意思,请大家帮帮忙,谢谢,感激不尽!!!!
C/C++ char类型指针数组输入问题
# C/C++ char类型指针数组输入问题 数据结构课程设计,要求从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上。 程序代码如下: ```cpp #include <iostream> #include <string.h> #define N 50 #define M 2*N-1 #define MAX 100 using namespace std; typedef struct { char data[5]; int weight; int parent; int lchild; int rchild; }HTNode; typedef struct { char cd[N]; int start; }HCode; void CreatHT(HTNode ht[], int n) { int i,k,lnode,rnode; int min1,min2; for (i=0; i<2*n-1; i++) { ht[i].parent=ht[i].lchild=ht[i].rchild=-1; } for (i=n; i<2*n-1; i++) { min1=min2=32767; lnode=rnode=-1; for (k=0; k<=i-1; k++) { if (ht[k].parent==-1) { if (ht[k].weight<min1) { min2=min1; rnode=lnode; min1=ht[k].weight; lnode=k; } else if (ht[k].weight<min2) { min2=ht[k].weight; rnode=k; } } } ht[lnode].parent=i; ht[rnode].parent=1; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode; ht[i].rchild=rnode; } } void CreatHCode(HTNode ht[], HCode hcd[], int n) { int i,f,c; HCode hc; for (i=0; i<n; i++) { hc.start=n; c=i; f=ht[i].parent; while (f!=-1) { if (ht[f].lchild==c) { hc.cd[hc.start--]='0'; } else { hc.cd[hc.start--]='1'; } c=f; f=ht[f].parent; } hc.start++; hcd[i]=hc; } } void DispHCode(HTNode ht[], HCode hcd[], int n) { int i,k; int sum=0,m=0,j; printf("输出哈弗曼编码:\n"); for (i=0; i<n; i++) { j=0; printf(" %s:\t", ht[i].data); for (k=hcd[i].start; k<=n; k++) { printf("%c", hcd[i].cd[k]); j++; } m+=ht[i].weight; sum+=ht[i].weight*j; } printf("\n平均长度=%g\n", 1.0*sum/m); } int main(int argc, const char * argv[]) { // insert code here... int n,i; char *str[MAX];//这里定义了一个指针数组存放哈夫曼编码 int fnum[MAX]; HTNode ht[M]; HCode hcd[N]; printf("输如字符集大小:"); scanf("%d", &n); printf("输入%d个字符:", n); for (i=0; i<n; i++) { scanf("%s", str[i]);//这里的输入应该如何修改? } printf("输入%d个权值:", n); for (i=0; i<n; i++) { scanf("%d", &fnum[i]); } for (i=0; i<n; i++) { strcpy(ht[i].data, str[i]); ht[i].weight=fnum[i]; } CreatHT(ht, n); CreatHCode(ht, hcd, n); DispHCode(ht, hcd, n); return 1; } ``` 有问题的地方已在主函数中注释,其他的函数都是哈夫曼树的基本算法。 困扰许久求大佬解决!
计算输入字母的个数,代码如下,求详细解释
int Count(int cou[]) //计算输入的字母的个数 { char word; char letter[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'}; fstream SourceFile; SourceFile.open("SourceFile.txt",ios::in); if (!SourceFile) { cout<<"Can't open this file"<<endl; } while (!SourceFile.eof()) { SourceFile.get(word); if (word>='A'&&word<='Z') { word=word+32; } int i=word-96; cou[i]++; } SourceFile.close(); cout<<"letter"<<'\t'<<'\t'<<"频率为"<<endl; for (int j=1;j<=26;j++) { if (cou[j]!=0) { cout<<letter[j]<<'\t'<<'\t'<<cou[j]<<endl; } } cout<<"读入完事儿!"<<endl; return 0; }
代码运行有问题怎么解决
#include <iostream> #include <string> #include <queue> #include <map> using namespace std; /** * @brief 哈弗曼结点 * 记录了哈弗曼树结点的数据、权重及左右儿子 */ struct HTNode { char data; HTNode *lc, *rc; int w; /** 节点构造函数 */ HTNode(char _d, int _w, HTNode *_l = NULL, HTNode *_r = NULL) { data = _d; w = _w; lc = _l; rc = _r; } /** 节点拷贝构造函数 */ HTNode(const HTNode &h) { data = h.data; lc = h.lc; rc = h.rc; w = h.w; } /** 用于优先队列比较的运算符重载 */ friend bool operator < (const HTNode &a, const HTNode &b) { return a.w > b.w; } }; /** 哈弗曼树叶子节点数、各叶子结点数据及权重 */ /** 权值从Lolita小说中抽样取出 */ const char ch[] = { 10, 32, 33, 37, 40, 41, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 161, 164, 166, 168, 170, 173, 174, 175, 176, 177, 180, 186, 255, '\r', '\0' }; const int fnum[] = { 2970, 99537, 265, 1, 496, 494, 9032, 1185, 5064, 108, 180, 132, 99, 105, 82, 64, 62, 77, 126, 296, 556, 548, 818, 443, 543, 435, 225, 271, 260, 797, 3487, 158, 50, 1053, 589, 498, 332, 316, 61, 276, 724, 855, 54, 293, 543, 11, 185, 11, 25, 26, 42416, 7856, 12699, 23670, 61127, 10229, 10651, 27912, 32809, 510, 4475, 23812, 13993, 34096, 38387, 9619, 500, 30592, 30504, 42377, 14571, 4790, 11114, 769, 10394, 611, 1, 4397, 12, 71, 117, 1234, 81, 5, 852, 1116, 1109, 1, 3, 1, 2970 }; const int n = 91; /** 优先队列 */ priority_queue<HTNode> pq; /** 哈弗曼编码映射 */ map<string, char> dcode; map<char, string> ecode; /** 根节点以及总权重+边长 */ HTNode *root; int sum = 0; /** 初始化叶节点,并加入到优先队列中 */ void Init() { for(int i = 0; i < n; i++) { HTNode p(ch[i], fnum[i]); pq.push(p); } } /** 建立哈夫曼树 */ void CreateHT() { HTNode *lmin, *rmin; /** 当队列中不止一个元素时 */ while(!pq.empty() && 1 != pq.size()) { /** 取队首两个元素(权值最小) */ lmin = new HTNode(pq.top()); pq.pop(); rmin = new HTNode(pq.top()); pq.pop(); /** 合并元素重新入队 */ HTNode p(0, lmin->w + rmin->w, lmin, rmin); pq.push(p); } if(!pq.empty()) { /** 根节点 */ root = new HTNode(pq.top()); pq.pop(); } } /** 创建哈夫曼编码 */ void CreateHTCode(HTNode *p, string str) { if(!p) return; if(0 != p->data) { /** 若是叶节点,则记录此节点的编码值 */ dcode[str] = p->data; ecode[p->data] = str; sum += (str.length() * p->w); return; } CreateHTCode(p->lc, str + "0"); CreateHTCode(p->rc, str + "1"); } /** 显示哈夫曼编码 */ void DispCode() { printf("输出哈弗曼编码:\n"); for(int i = 0; i < n; i++) { printf("\t'%c':\t%s\n", ch[i], ecode[ch[i]].c_str()); } printf("平均长度:%.5lf\n", double(sum) / double(root->w)); } /** 释放哈夫曼树 */ void Release(HTNode *p) { if(!p) return; Release(p->lc); Release(p->rc); delete p; } /** 输出压缩文 */ void putEncode(FILE *fp, char *buf) { unsigned char code = 0; for(int i = 0; i < 8; i++) code = (code << 1) + (buf[i] - '0'); fwrite(&code, sizeof(unsigned char), 1, fp); } /** 判断是否在字符串内 */ bool instr(char c, const char str[]) { for(int i = 0; i < strlen(str); i++) if(c == str[i]) return true; return false; } /** 压缩文件 */ void Encode() { FILE *OF; FILE *IF; char ifn[255]; const char ofn[] = "Encode.txt"; char buf[9]; int cnt = 0, newcnt = 0; printf("Input the filename: "); scanf("%s", ifn); IF = fopen(ifn, "rb"); if(!IF) { printf("Wrong file.\n"); return; } OF = fopen(ofn, "wb+"); if(!OF) { printf("Wrong file.\n"); } /** 开始读文件 */ memset(buf, 0, sizeof(buf)); while(!feof(IF)) { unsigned char c; fread(&c, sizeof(unsigned char), 1, IF); if(instr(c, ch)); else c = ' '; for(int i = 0; i < ecode[c].length(); i++) { buf[strlen(buf)] = ecode[c][i]; if(8 == strlen(buf)) { newcnt++; putEncode(OF, buf); memset(buf, 0, sizeof(buf)); } } cnt++; } cnt--; if(0 != strlen(buf)) { for(int i = strlen(buf); i < 8; i++) buf[i] = '0'; putEncode(OF, buf); } fwrite(&cnt, 4, 1, OF); fclose(IF); fclose(OF); printf("压缩成功!压缩率:%.2f%c\n", (((double)newcnt + 4.0f) / (double)cnt) * 100, '%'); } /** 补0 */ void putZeros(char *buf) { char tmpbuf[9]; memset(tmpbuf, 0, sizeof(tmpbuf)); if(8 != strlen(buf)) { for(int i = 0; i < 8 - strlen(buf); i++) tmpbuf[i] = '0'; strcat(tmpbuf, buf); strcpy(buf, tmpbuf); } } /** 解压缩 */ void Decode() { char buf[256]; char oldbuf[9]; const char ifn[] = "Encode.txt"; const char ofn[] = "Decode.txt"; FILE *IF = fopen(ifn, "rb"); if(!IF) { printf("Wrong file.\n"); return; } FILE *OF = fopen(ofn, "wb+"); if(!OF) { printf("Wrong file.\n"); return; } int tot, cnt = 0; fseek(IF, -4L, SEEK_END); fread(&tot, 4, 1, IF); fseek(IF, 0L, SEEK_SET); memset(buf, 0, sizeof(buf)); while(true) { if(cnt == tot) break; unsigned char c; fread(&c, sizeof(unsigned char), 1, IF); itoa(c, oldbuf, 2); putZeros(oldbuf); for(int i = 0; i < 8; i++) { if(cnt == tot) break; buf[strlen(buf)] = oldbuf[i]; if(dcode.end() != dcode.find(string(buf))) { fwrite(&dcode[string(buf)], sizeof(char), 1, OF); memset(buf, 0, sizeof(buf)); cnt++; } } } fclose(IF); fclose(OF); printf("解压成功!文件名Decode.txt。\n"); } int main() { Init(); CreateHT(); CreateHTCode(root, ""); DispCode(); Encode(); Decode(); Release(root); system("pause"); return 0; }
下面的错误怎么改啊,请大家帮帮我,我刚开始写,写不好啊。耐心看一下,谢谢!!
``` #include <iostream> #include <string> #define MAX 100 using namespace std; class HTNode { public: int weight; string data; int f; HTNode* father; HTNode* lchild; HTNode* rchild; string code; HTNode() { weight=0; data='0'; code='0'; f=0; father=NULL; lchild=NULL; rchild=NULL; } void SetChild (HTNode* lchild, HTNode* rchild) { this->lchild = lchild; this->rchild = rchild; } void SetF(int f) { this->f = f; } void SetFather(HTNode* father) { this->father = father; } }; void SelectMin(HTNode*ht[], int*a1,int*a2) { int min1=0; int min2=0; for(int i=0;i<2*MAX-1;i++) { if(ht[min1]->weight>ht[i]->weight) min1=i; } min2=min1+1; for(int i=0;i<2*MAX-1;i++) { if(ht[min2]->weight>ht[i]->weight) min2=i; } *a1=min1; *a2=min2; } void Printtree(HTNode* root, int n) { if (root==NULL) return; for (int i=0;i<n;i++) { cout<<" "; } if (root->f==1) { cout<<"|_"; } else { cout<<" "; } cout<<root->data<<endl; Printtree(root->lchild, n+2); Printtree(root->rchild, n+2); } void Bianma(HTNode*ht[]) { HTNode* curr; string* code = new string[MAX]; for (int i = 0; i < MAX ; i++) { code[i] = '2'; } for (int i = 0; i < MAX; i++) { int j = 1; cout<<ht[i]->data<<"的哈弗曼编码为:"; curr = ht[i]; while (curr->f==1) { curr=curr->father; if (curr->f==1){ code[j++]=curr->code; } } code[0] = ht[i]->code; string c[j]; int count = 0; for (int l = j-1; l >=0; l--) { if (code[l]!= '2') { c[count++] = code[l]; } } for (int x = 0; x < j; x++) { ht[i]->code += c[x]; } cout<<ht[i]->code<<endl; cout<<endl; } } void FanYi(HTNode* ht[]) { string code; string test = ""; HTNode* curr; HTNode* root; cout<<"请输入编码:"<<endl; cin>>code; int n = code.length(); string* cs = new string[n]; code.copy(cs, n, 0); for (int i = 0; i < MAX*2-1; i++) { if (ht[i]->f == 0) { root = ht[i]; } } curr = root; for (int i = 0; i < n; i++) { if (cs[i] == '0' && curr->lchild != NULL) { curr = curr->lchild; test += '0'; } else if (cs[i] == '1') { curr = curr->rchild; test += '1'; } if (curr->lchild == NULL || curr->rchild == NULL) { curr = root; for (int i = 0; i < MAX; i++) { if (ht[i]->code == test) { cout<<ht[i]->data; test = ""; } } } } cout<<endl; } void GouJian(string* s, int* n) { int a1, a2, m; m = 2*MAX-1; HTNode* ht[2*MAX-1]; for (int i=0;i<MAX;i++) { ht[i] = new HTNode(s[i], n[i]); } for (int i=MAX;i<2*MAX-1;i++) { ht[i] = new HTNode('0'); } for (int i = 0; i < MAX-1; i++) { SelectMin(ht, &a1, &a2); ht[MAX+i]->weight = ht[a1]->weight + ht[a2]->weight; if (ht[a1]->weight <= ht[a2]->weight) { ht[MAX+i]->SetChild(ht[a1], ht[a2]); ht[a1]->code = '0'; ht[a2]->code = '1'; } else { ht[MAX+i]->SetChild(ht[a2], ht[a1]); ht[a1]->code = '1'; ht[a2]->code = '0'; } ht[a1]->SetF(1); ht[a2]->SetF(1); ht[a1]->SetFather(ht[MAX+i]); ht[a2]->SetFather(ht[MAX+i]); for (int i=0;i<2*MAX-1;i++) { cout<<ht[i]->weight<<" "; } cout<<endl; } cout<<"您输入的哈夫曼树为:"<<endl<<endl; for (int i = 0;i<2*MAX-1;i++) { if (ht[i]->father == 0) { Printtree(ht[i], MAX); cout<<endl; } } cout<<"根据系统分析,有以下结论:"<<endl; Bianma(ht); cout<<endl; FanYi(ht); } ``` 错误信息 error: no matching function for call to `std::basic_string<char, std::char_traits<char>, std::allocator<char> >::copy(std::string*&, int&, int)' error: no match for 'operator!=' in '*((+(((unsigned int)l) * 4u)) + code) != '2' error: no matching function for call to `HTNode::HTNode(char)'
相见恨晚的超实用网站
相见恨晚的超实用网站 持续更新中。。。
Java学习的正确打开方式
在博主认为,对于入门级学习java的最佳学习方法莫过于视频+博客+书籍+总结,前三者博主将淋漓尽致地挥毫于这篇博客文章中,至于总结在于个人,实际上越到后面你会发现学习的最好方式就是阅读参考官方文档其次就是国内的书籍,博客次之,这又是一个层次了,这里暂时不提后面再谈。博主将为各位入门java保驾护航,各位只管冲鸭!!!上天是公平的,只要不辜负时间,时间自然不会辜负你。 何谓学习?博主所理解的学习,它是一个过程,是一个不断累积、不断沉淀、不断总结、善于传达自己的个人见解以及乐于分享的过程。
程序员必须掌握的核心算法有哪些?
由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,我稍微总结一下我学过的算法知识点,以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的,并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构,当然,我也会整理一些看过...
大学四年自学走来,这些私藏的实用工具/学习网站我贡献出来了
大学四年,看课本是不可能一直看课本的了,对于学习,特别是自学,善于搜索网上的一些资源来辅助,还是非常有必要的,下面我就把这几年私藏的各种资源,网站贡献出来给你们。主要有:电子书搜索、实用工具、在线视频学习网站、非视频学习网站、软件下载、面试/求职必备网站。 注意:文中提到的所有资源,文末我都给你整理好了,你们只管拿去,如果觉得不错,转发、分享就是最大的支持了。 一、电子书搜索 对于大部分程序员...
linux系列之常用运维命令整理笔录
本博客记录工作中需要的linux运维命令,大学时候开始接触linux,会一些基本操作,可是都没有整理起来,加上是做开发,不做运维,有些命令忘记了,所以现在整理成博客,当然vi,文件操作等就不介绍了,慢慢积累一些其它拓展的命令,博客不定时更新 free -m 其中:m表示兆,也可以用g,注意都要小写 Men:表示物理内存统计 total:表示物理内存总数(total=used+free) use...
比特币原理详解
一、什么是比特币 比特币是一种电子货币,是一种基于密码学的货币,在2008年11月1日由中本聪发表比特币白皮书,文中提出了一种去中心化的电子记账系统,我们平时的电子现金是银行来记账,因为银行的背后是国家信用。去中心化电子记账系统是参与者共同记账。比特币可以防止主权危机、信用风险。其好处不多做赘述,这一层面介绍的文章很多,本文主要从更深层的技术原理角度进行介绍。 二、问题引入 假设现有4个人...
python学习方法总结(内附python全套学习资料)
不要再问我python好不好学了 我之前做过半年少儿编程老师,一个小学四年级的小孩子都能在我的教学下独立完成python游戏,植物大战僵尸简单版,如果要肯花时间,接下来的网络开发也不是问题,人工智能也可以学个调包也没啥问题。。。。。所以python真的是想学就一定能学会的!!!! --------------------华丽的分割线-------------------------------- ...
兼职程序员一般可以从什么平台接私活?
这个问题我进行了系统性的总结,以下将进行言简意赅的说明和渠道提供,希望对各位小猿/小媛们有帮助~ 根据我们的经验,程序员兼职主要分为三种:兼职职位众包、项目整包和自由职业者驻场。 所谓的兼职职位众包,指的是需求方这边有自有工程师配合,只需要某个职位的工程师开发某个模块的项目。比如开发一个 app,后端接口有人开发,但是缺少 iOS 前端开发工程师,那么他们就会发布一个职位招聘前端,来配合公司一...
网页实现一个简单的音乐播放器(大佬别看。(⊙﹏⊙))
今天闲着无事,就想写点东西。然后听了下歌,就打算写个播放器。 于是乎用h5 audio的加上js简单的播放器完工了。 演示地点演示 html代码如下` music 这个年纪 七月的风 音乐 ` 然后就是css`*{ margin: 0; padding: 0; text-decoration: none; list-...
JAVA 基础练习题
第一题 1.查看以下代码,并写出结果 public class Test01 { public static void main(String[] args) { int i1 = 5; boolean result = (i1++ &gt; 5) &amp;&amp; (++i1 &gt; 4); System.out.println(result); Sy...
Python十大装B语法
Python 是一种代表简单思想的语言,其语法相对简单,很容易上手。不过,如果就此小视 Python 语法的精妙和深邃,那就大错特错了。本文精心筛选了最能展现 Python 语法之精妙的十个知识点,并附上详细的实例代码。如能在实战中融会贯通、灵活使用,必将使代码更为精炼、高效,同时也会极大提升代码B格,使之看上去更老练,读起来更优雅。
数据库优化 - SQL优化
以实际SQL入手,带你一步一步走上SQL优化之路!
2019年11月中国大陆编程语言排行榜
2019年11月2日,我统计了某招聘网站,获得有效程序员招聘数据9万条。针对招聘信息,提取编程语言关键字,并统计如下: 编程语言比例 rank pl_ percentage 1 java 33.62% 2 cpp 16.42% 3 c_sharp 12.82% 4 javascript 12.31% 5 python 7.93% 6 go 7.25% 7 p...
通俗易懂地给女朋友讲:线程池的内部原理
餐盘在灯光的照耀下格外晶莹洁白,女朋友拿起红酒杯轻轻地抿了一小口,对我说:“经常听你说线程池,到底线程池到底是个什么原理?”
C++知识点 —— 整合(持续更新中)
本文记录自己在自学C++过程中不同于C的一些知识点,适合于有C语言基础的同学阅读。如果纰漏,欢迎回复指正 目录 第一部分 基础知识 一、HelloWorld与命名空间 二、引用和引用参数 2.1引用的定义 2.2 将引用用作函数参数 2.3 将引用用于类对象 2.4 引用和继承 2.5 何时使用引用参数 2.6 引用和指针的区别 三、内联函数 四、默认参数的...
《奇巧淫技》系列-python!!每天早上八点自动发送天气预报邮件到QQ邮箱
将代码部署服务器,每日早上定时获取到天气数据,并发送到邮箱。 也可以说是一个小型人工智障。 知识可以运用在不同地方,不一定非是天气预报。
经典算法(5)杨辉三角
杨辉三角 是经典算法,这篇博客对它的算法思想进行了讲解,并有完整的代码实现。
Python实例大全(基于Python3.7.4)
博客说明: 这是自己写的有关python语言的一篇综合博客。 只作为知识广度和编程技巧学习,不过于追究学习深度,点到即止、会用即可。 主要是基础语句,如三大控制语句(顺序、分支、循环),随机数的生成,数据类型的区分和使用; 也会涉及常用的算法和数据结构,以及面试题相关经验; 主体部分是针对python的数据挖掘和数据分析,主要先攻爬虫方向:正则表达式匹配,常用数据清洗办法,scrapy及其他爬虫框架,数据存储方式及其实现; 最后还会粗略涉及人工智能领域,玩转大数据与云计算、进行相关的预测和分析。
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
昨天,有网友私信我,说去阿里面试,彻底的被打击到了。问了为什么网上大量使用ThreadLocal的源码都会加上private static?他被难住了,因为他从来都没有考虑过这个问题。无独有偶,今天笔者又发现有网友吐槽了一道腾讯的面试题,我们一起来看看。 腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹? 在互联网职场论坛,一名程序员发帖求助到。二面腾讯,其中一个算法题:64匹...
面试官:你连RESTful都不知道我怎么敢要你?
干货,2019 RESTful最贱实践
机械转行java自学经历,零基础学java,血泪总结的干货
机械转行java自学经历,零基础学java,血泪总结的干货 据说,再恩爱的夫妻,一生中都有100次想离婚的念头和50次想掐死对方的冲动。 求职路上亦是如此,打开这篇文章,相信你也有转行的想法。和身边的朋友聊过,入职后的他们,或多或少对现在的职位都有些不满,都有过转行的冲动。 可他们只是想,而我真的这样做了。 下面就介绍下我转行的血泪史。 我为什么要转行 高中复读了一年,考了个双非院校的机械。当时...
刷了几千道算法题,这些我私藏的刷题网站都在这里了!
遥想当年,机缘巧合入了 ACM 的坑,周边巨擘林立,从此过上了"天天被虐似死狗"的生活… 然而我是谁,我可是死狗中的战斗鸡,智力不够那刷题来凑,开始了夜以继日哼哧哼哧刷题的日子,从此"读题与提交齐飞, AC 与 WA 一色 ",我惊喜的发现被题虐既刺激又有快感,那一刻我泪流满面。这么好的事儿作为一个正直的人绝不能自己独享,经过激烈的颅内斗争,我决定把我私藏的十几个 T 的,阿不,十几个刷题网...
为啥国人偏爱Mybatis,而老外喜欢Hibernate/JPA呢?
关于SQL和ORM的争论,永远都不会终止,我也一直在思考这个问题。昨天又跟群里的小伙伴进行了一番讨论,感触还是有一些,于是就有了今天这篇文。 声明:本文不会下关于Mybatis和JPA两个持久层框架哪个更好这样的结论。只是摆事实,讲道理,所以,请各位看官勿喷。 一、事件起因 关于Mybatis和JPA孰优孰劣的问题,争论已经很多年了。一直也没有结论,毕竟每个人的喜好和习惯是大不相同的。我也看...
【Linux系统编程】Linux信号列表
00. 目录 文章目录00. 目录01. Linux信号编号02. 信号简介03. 特殊信号04. 附录 01. Linux信号编号 在 Linux 下,每个信号的名字都以字符 SIG 开头,每个信号和一个数字编码相对应,在头文件 signum.h 中,这些信号都被定义为正整数。信号名定义路径:/usr/include/i386-linux-gnu/bits/signum.h 要想查看这些信号和...
JavaScript 为什么能活到现在?
作者 | 司徒正美 责编 |郭芮 出品 | CSDN(ID:CSDNnews) JavaScript能发展到现在的程度已经经历不少的坎坷,早产带来的某些缺陷是永久性的,因此浏览器才有禁用JavaScript的选项。甚至在jQuery时代有人问出这样的问题,jQuery与JavaScript哪个快?在Babel.js出来之前,发明一门全新的语言代码代替JavaScript...
项目中的if else太多了,该怎么重构?
介绍 最近跟着公司的大佬开发了一款IM系统,类似QQ和微信哈,就是聊天软件。我们有一部分业务逻辑是这样的 if (msgType = "文本") { // dosomething } else if(msgType = "图片") { // doshomething } else if(msgType = "视频") { // doshomething } else { // doshom...
致 Python 初学者
欢迎来到“Python进阶”专栏!来到这里的每一位同学,应该大致上学习了很多 Python 的基础知识,正在努力成长的过程中。在此期间,一定遇到了很多的困惑,对未来的学习方向感到迷茫。我非常理解你们所面临的处境。我从2007年开始接触 python 这门编程语言,从2009年开始单一使用 python 应对所有的开发工作,直至今天。回顾自己的学习过程,也曾经遇到过无数的困难,也曾经迷茫过、困惑过。开办这个专栏,正是为了帮助像我当年一样困惑的 Python 初学者走出困境、快速成长。希望我的经验能真正帮到你
Python 编程开发 实用经验和技巧
Python是一门很灵活的语言,也有很多实用的方法,有时候实现一个功能可以用多种方法实现,我这里总结了一些常用的方法和技巧,包括小数保留指定位小数、判断变量的数据类型、类方法@classmethod、制表符中文对齐、遍历字典、datetime.timedelta的使用等,会持续更新......
借助AI力量,谷歌解开生命奥秘?
全文共4484字,预计学习时长8分钟 Paweł Czerwiński发布在 Unsplash上的原图 假如疾病不复存在会发生什么?如果我们能像大自然一样迅速获取能量又会发生什么?要是我们能够在极短时间内循环塑料、废油、或其它的一些物质呢?如果人类能够解开生命的奥秘,那么以上这些想象将在未来成为现实。人工智能企业DeepMind的数据科学分析师日前在此领域有了重大发现。以下为具体内容:...
吐血推荐珍藏的Visual Studio Code插件
作为一名Java工程师,由于工作需要,最近一个月一直在写NodeJS,这种经历可以说是一部辛酸史了。好在有神器Visual Studio Code陪伴,让我的这段经历没有更加困难。眼看这段经历要告一段落了,今天就来给大家分享一下我常用的一些VSC的插件。 VSC的插件安装方法很简单,只需要点击左侧最下方的插件栏选项,然后就可以搜索你想要的插件了。 下面我们进入正题 Material Theme ...
“狗屁不通文章生成器”登顶GitHub热榜,分分钟写出万字形式主义大作
一、垃圾文字生成器介绍 最近在浏览GitHub的时候,发现了这样一个骨骼清奇的雷人项目,而且热度还特别高。 项目中文名:狗屁不通文章生成器 项目英文名:BullshitGenerator 根据作者的介绍,他是偶尔需要一些中文文字用于GUI开发时测试文本渲染,因此开发了这个废话生成器。但由于生成的废话实在是太过富于哲理,所以最近已经被小伙伴们给玩坏了。 他的文风可能是这样的: 你发现,...
相关热词 c#中dns类 c#合并的excel c# implicit c#怎么保留3个小数点 c# 串口通信、 网络调试助手c# c# 泛型比较大小 c#解压分卷问题 c#启动居中 c# 逻辑或运算符
立即提问