哈弗曼树的问题,代码如下,求详细解释。答辩需要,但我一点也不懂,急求

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!"< 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();
}

2个回答

之前的问题如果满意,请先采纳。然后帮你看剩余的部分。

Deadwood_
Deadwood_ 谢谢你,我这是要答辩的题目,但不懂这些代码什么意思,能再详细一些吗,再不懂的我可以百度
3 年多之前 回复
 /*--------------------算法5.11 根据统计结果对各字符进行编码,并保存在Code.txt中------------------*/
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC)
{ int start;
char cd;
HC=new char[n+1]; //生成长度为n+1个字符的哈夫曼编码表
cd=new char[n]; //这里写错了吧,是char * cd
cd[n-1]='\0'; //最后一个字符设置为\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'; 。。输出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!"< 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();
}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
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(); }

新手哈弗曼树访问出错求大神改一下

#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();}

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

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

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; } ```

哈夫曼树的构造技巧以及权值问题

数据结构中树的权值最优问题,还有怎样构造哈夫曼树,求详细的解答,谢谢啦!

数据结构huffman编码树问题

以下是用于将树节点按权值插入forest数组的函数(权值小的在前),在调试中发现插入函数有问题,但编译器未报错。求大神指点,谢谢。 void insert(huffnode* temp) { curr=0; if(size==0) { nodearray[curr]=temp; size++; } else { while(temp->getweight()>=nodearray[curr]->getweight()) { curr++; } for(int i=size;i>curr;i--) { nodearray[i]=nodearray[i-1]; } nodearray[curr]=temp; delete temp; size++; } } 以下为调试时的代码 #include<iostream> #include<string.h> using namespace std; class huffnode { private: int weight; char it='#'; huffnode* lc; huffnode* rc; public: huffnode(char _it,int _weight) { it=_it;weight=_weight;lc=NULL;rc=NULL; } huffnode(huffnode* _lc,huffnode* _rc) { lc=_lc;rc=_rc; weight=lc->getweight()+rc->getweight(); } int getweight(){return weight;} bool isleaf() { if(it=='#') return false; else return true; } huffnode* getlc(){return lc;} huffnode* getrc(){return rc;} char getit(){return it;} }; class hufftree { private: huffnode* root; public: hufftree(huffnode* rt) { root=rt; } huffnode* getroot(){return root;} }; void inorder(huffnode* rt) { if(rt!=NULL) { inorder(rt->getlc()); cout<<rt->getit(); inorder(rt->getrc()); } } class forest { private: int size; int curr; int maxsize; huffnode** nodearray; public: forest(int m) { size=0;curr=0;maxsize=m;nodearray=new huffnode*[maxsize]; } void insert(huffnode* temp) { curr=0; if(size==0) { nodearray[curr]=temp; size++; } else { while(temp->getweight()>=nodearray[curr]->getweight()) { curr++; } for(int i=size;i>curr;i--) { nodearray[i]=nodearray[i-1]; } nodearray[curr]=temp; delete temp; size++; } } huffnode* remove() { huffnode* temp; temp=nodearray[0]; for(int i=0;i<size-1;i++) { nodearray[i]=nodearray[i+1]; } size--; return temp; } huffnode* makehuff() { while(size!=1) { huffnode* temp1; huffnode* temp2; temp1=remove(); temp2=remove(); huffnode* temp3= new huffnode(temp1,temp2); insert(temp3); } return nodearray[0]; } huffnode** getarray() { return nodearray; } }; int main() { int n; cin>>n; forest f(n); string _f[n]; for(int i=0;i<n;i++) { char it; int weight; cin>>it>>weight; //huffnode tempnode(it,weight); f.insert(new huffnode(it,weight)); _f[i]=it; cout<<_f[i]; } cout<<endl; for(int i=0;i<n;i++) { cout<<f.getarray()[i]->getit()<<f.getarray()[i]->getweight(); } 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; }

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)显示功能:以先序遍历的顺序显示建立好的哈夫曼树。显示哈夫曼编码和译码的结果。

哈弗曼树为什么第二个和第四个节点会交换,请帮忙看看代码

#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; }

构建一个哈弗曼树,并计算其带权路径长度

不知道是哪里出现了问题,运行结果不对,并且一点调试就直接结束了,麻烦大神们帮我看一下 ``` # 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; } ```

哈弗曼编码,从根到叶子,权值从数组为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 } } ```

怎样打印哈夫曼树,在运行的时候可以看到自己的哈夫曼树?

怎样将自己构建的哈夫曼树打印出来,运行时能够看到自己的树,用横线个竖线形成的树,求高手解答,有代码的话能不能贴出来看看,学习学习,谢谢!

关于写哈夫曼树的思路

哪位能给一个写哈夫曼树的思路啊。我想了好久都不会写,不知道怎么才能把自己输入的东西用哈夫曼树翻译出来。求帮助

数据结构哈弗曼编码,急急急急急急!

在记事本软件中,放入不小于1000个英文字符的文本,命名为source.txt。 编写过程,挑出文本中的不相同字符,输出文件列出每个字符的出现概率。 根据字符列表文件建立字符列表的哈夫曼编码本1 以哈夫曼编码本1为参照,将文本文件source.txt的内容转换为二进制码文件code.dat 以哈夫曼编码本1为参照,将二进制码文件code1.dat的内容解码为target.txt明文 编写函数,对比source.txt和 target.txt是否相同,不同则返回出现不同的位置点。 大学生的数据结构作业,求大神帮忙啊!

关于哈夫曼编码的c语言和高数的考题,请大神解答一下

哈夫曼编码是依据信源字符出现的概率大小来构造代码,对出现概率较大的信源字符,给予较短码长,而对于出现概率较小的信源字符,给予较长的码长,最后使得编码的平均码字最短。其的编码步骤如下:(1)将信源符号出现的概率按由大到小的顺序排列。(2)将两处最小的概率进行组合相加,形成一个新的概率。(3)将新出现的概率与未编码的字符一起重新排列。(4)重复步骤(2)、(3),直到出现的概率和为1。(5)分配代码。代码分配从最后一步开始反向进行,对最后两个概率一码。如此反向进行到开始概率排列。现给出信源符号及其概率如下:a为p(a),a1为0.5,a2为0.25,a3为0.125,a4为0.0625。要求:1求出其huffman编码?2求出其信息熵?3求出其平均码长。信息熵计算公式?![图片说明](https://img-ask.csdn.net/upload/201608/21/1471750909_899575.png)

这是一棵哈夫曼树,求大神解决

这是一棵哈夫曼树 存c++ 应该是select函数出错了 求助大神 谢谢 #include<iostream> using namespace std; const int Maxsize=7; struct element { int weight; int parent,lchild,rchild; }; void Select(element huffman[Maxsize],int &a,int &b) { int Fmax,Smax; if(huffman[0].weight>huffman[1].weight) { Fmax=1; Smax=0; } else { Fmax=0; Smax=1; } for(int i=2; i<Maxsize-1; i++) { if(huffman[Smax].weight<=huffman[i].weight) { } else { if(huffman[Fmax].weight<=huffman[i].weight) Smax=i; else { Smax=Fmax; Fmax=i; } } } a=Fmax; b=Smax; cout<<"**********i1="<<a<<"*******i2="<<b<<"***"<<endl; } void Print(element huffman[],int n) { cout<<"weight\t\t"<<"parent\t"<<"lchild\t"<<"rchild\t"<<endl; for(int i=0; i<2*n-1; i++) { cout<<huffman[i].weight<<"\t\t"<<huffman[i].parent<<"\t"; cout<<huffman[i].lchild<<"\t"<<huffman[i].rchild<<endl; } } void HuffmanTree(element Huffman[],int w[],int n) { int i1=0,i2=1; for(int i=0; i<2*n-1; i++) { Huffman[i].weight=0; Huffman[i].parent=-1; Huffman[i].lchild=-1; Huffman[i].rchild=-1; } for(int i=0; i<n; i++) Huffman[i].weight=w[i]; for(int k=n; k<2*n-1; k++) { Select(Huffman,i1,i2); cout<<"*****k="<<k<<endl; Huffman[i1].parent=k; Huffman[i2].parent=k; Huffman[k].weight=Huffman[i1].weight+Huffman[i2].weight; Huffman[k].lchild=i1; Huffman[k].rchild=i2; } } int main() { int n=4; element huffman[2*n-1]; int w[n]; for(int i=0; i<n; i++) cin>>w[i]; HuffmanTree(huffman,w,n); Print(huffman,n); return 0; }

哈弗曼进行译码的时候怎么最后得到的是原来编码前的短文顺序,跪求指点

哈弗曼进行译码的时候怎么最后得到的是原来编码前的短文顺序,跪求指点

哈夫曼树与哈夫曼编码

利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。 设计要求:从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各个字符进行哈夫曼编码,最后打印输出字符及对应的哈夫曼编码。

构造哈夫曼树,传回权值最小的两个数s2的值错误,输入各节点权值始终不变?

#include<iostream> #include<cstring> using namespace std; typedef char * HuffmanCode[]; typedef struct { int weight; int parent, lch, rch; }HTNode,*HuffmanTree; void Select(HuffmanTree &HT, int k, int &s1, int &s2) { int temp=HT[1].weight; for (int i = 1; i <= k; ++i) { if (HT[i].weight <= temp) s1 = i; else continue; } for (int j = 1; j <= k; ++j) { if ((HT[j].weight <= temp) && (HT[j].weight>=HT[s1].weight)) s2 = j; else continue; } } void CreatHuffmanTree(HuffmanTree &HT, int n) { int m; int s1, s2; if (n <= 1) return; m = 2 * n - 1; HT = new HTNode[m + 1];//0号单元未用,HT[m]表示根节点 for (int i = 1; i <= m; ++i) { HT[i].lch = 0; HT[i].rch = 0; HT[i].parent = 0; } for (int i = 1; i <= n; ++i) { cin >> HT[i].weight; } for (int i = n + 1; i <= m; ++i) { Select(HT, i - 1, s1, s2); //在HT[k](1≤k≤i-1)中选择两个其双亲域为0, // 且权值最小的结点, // 并返回它们在HT中的序号s1和s2 HT[s1].parent = i; HT[s2].parent = i; HT[i].lch = s1; HT[i].rch = s2; HT[i].weight = HT[s1].weight+HT[s2].weight; } }//构造哈夫曼树 void print(HuffmanTree HT, int n) { for (int i = 1; i <= 2*n-1; ++i) { cout << HT[i].weight<<" "<<HT[i].parent <<" "<< HT[i].lch << " "<< HT[i].rch << " "<< endl; } } void main() { HuffmanTree HT; int n; cin >> n; CreatHuffmanTree(HT, n); print(HT, n); }

在中国程序员是青春饭吗?

今年,我也32了 ,为了不给大家误导,咨询了猎头、圈内好友,以及年过35岁的几位老程序员……舍了老脸去揭人家伤疤……希望能给大家以帮助,记得帮我点赞哦。 目录: 你以为的人生 一次又一次的伤害 猎头界的真相 如何应对互联网行业的「中年危机」 一、你以为的人生 刚入行时,拿着傲人的工资,想着好好干,以为我们的人生是这样的: 等真到了那一天,你会发现,你的人生很可能是这样的: ...

程序员请照顾好自己,周末病魔差点一套带走我。

程序员在一个周末的时间,得了重病,差点当场去世,还好及时挽救回来了。

和黑客斗争的 6 天!

互联网公司工作,很难避免不和黑客们打交道,我呆过的两家互联网公司,几乎每月每天每分钟都有黑客在公司网站上扫描。有的是寻找 Sql 注入的缺口,有的是寻找线上服务器可能存在的漏洞,大部分都...

点沙成金:英特尔芯片制造全过程揭密

“亚马逊丛林里的蝴蝶扇动几下翅膀就可能引起两周后美国德州的一次飓风……” 这句人人皆知的话最初用来描述非线性系统中微小参数的变化所引起的系统极大变化。 而在更长的时间尺度内,我们所生活的这个世界就是这样一个异常复杂的非线性系统…… 水泥、穹顶、透视——关于时间与技艺的蝴蝶效应 公元前3000年,古埃及人将尼罗河中挖出的泥浆与纳特龙盐湖中的矿物盐混合,再掺入煅烧石灰石制成的石灰,由此得来了人...

上班一个月,后悔当初着急入职的选择了

最近有个老铁,告诉我说,上班一个月,后悔当初着急入职现在公司了。他之前在美图做手机研发,今年美图那边今年也有一波组织优化调整,他是其中一个,在协商离职后,当时捉急找工作上班,因为有房贷供着,不能没有收入来源。所以匆忙选了一家公司,实际上是一个大型外包公司,主要派遣给其他手机厂商做外包项目。**当时承诺待遇还不错,所以就立马入职去上班了。但是后面入职后,发现薪酬待遇这块并不是HR所说那样,那个HR自...

女程序员,为什么比男程序员少???

昨天看到一档综艺节目,讨论了两个话题:(1)中国学生的数学成绩,平均下来看,会比国外好?为什么?(2)男生的数学成绩,平均下来看,会比女生好?为什么?同时,我又联想到了一个技术圈经常讨...

副业收入是我做程序媛的3倍,工作外的B面人生是怎样的?

提到“程序员”,多数人脑海里首先想到的大约是:为人木讷、薪水超高、工作枯燥…… 然而,当离开工作岗位,撕去层层标签,脱下“程序员”这身外套,有的人生动又有趣,马上展现出了完全不同的A/B面人生! 不论是简单的爱好,还是正经的副业,他们都干得同样出色。偶尔,还能和程序员的特质结合,产生奇妙的“化学反应”。 @Charlotte:平日素颜示人,周末美妆博主 大家都以为程序媛也个个不修边幅,但我们也许...

如果你是老板,你会不会踢了这样的员工?

有个好朋友ZS,是技术总监,昨天问我:“有一个老下属,跟了我很多年,做事勤勤恳恳,主动性也很好。但随着公司的发展,他的进步速度,跟不上团队的步伐了,有点...

我入职阿里后,才知道原来简历这么写

私下里,有不少读者问我:“二哥,如何才能写出一份专业的技术简历呢?我总感觉自己写的简历太烂了,所以投了无数份,都石沉大海了。”说实话,我自己好多年没有写过简历了,但我认识的一个同行,他在阿里,给我说了一些他当年写简历的方法论,我感觉太牛逼了,实在是忍不住,就分享了出来,希望能够帮助到你。 01、简历的本质 作为简历的撰写者,你必须要搞清楚一点,简历的本质是什么,它就是为了来销售你的价值主张的。往深...

外包程序员的幸福生活

今天给你们讲述一个外包程序员的幸福生活。男主是Z哥,不是在外包公司上班的那种,是一名自由职业者,接外包项目自己干。接下来讲的都是真人真事。 先给大家介绍一下男主,Z哥,老程序员,是我十多年前的老同事,技术大牛,当过CTO,也创过业。因为我俩都爱好喝酒、踢球,再加上住的距离不算远,所以一直也断断续续的联系着,我对Z哥的状况也有大概了解。 Z哥几年前创业失败,后来他开始干起了外包,利用自己的技术能...

C++11:一些微小的变化(新的数据类型、template表达式内的空格、nullptr、std::nullptr_t)

本文介绍一些C++的两个新特性,它们虽然微小,但对你的编程十分重要 一、Template表达式内的空格 C++11标准之前建议在“在两个template表达式的闭符之间放一个空格”的要求已经过时了 例如: vector&lt;list&lt;int&gt; &gt;; //C++11之前 vector&lt;list&lt;int&gt;&gt;; //C++11 二、nullptr ...

优雅的替换if-else语句

场景 日常开发,if-else语句写的不少吧??当逻辑分支非常多的时候,if-else套了一层又一层,虽然业务功能倒是实现了,但是看起来是真的很不优雅,尤其是对于我这种有强迫症的程序"猿",看到这么多if-else,脑袋瓜子就嗡嗡的,总想着解锁新姿势:干掉过多的if-else!!!本文将介绍三板斧手段: 优先判断条件,条件不满足的,逻辑及时中断返回; 采用策略模式+工厂模式; 结合注解,锦...

深入剖析Springboot启动原理的底层源码,再也不怕面试官问了!

大家现在应该都对Springboot很熟悉,但是你对他的启动原理了解吗?

离职半年了,老东家又发 offer,回不回?

有小伙伴问松哥这个问题,他在上海某公司,在离职了几个月后,前公司的领导联系到他,希望他能够返聘回去,他很纠结要不要回去? 俗话说好马不吃回头草,但是这个小伙伴既然感到纠结了,我觉得至少说明了两个问题:1.曾经的公司还不错;2.现在的日子也不是很如意。否则应该就不会纠结了。 老实说,松哥之前也有过类似的经历,今天就来和小伙伴们聊聊回头草到底吃不吃。 首先一个基本观点,就是离职了也没必要和老东家弄的苦...

为什么你不想学习?只想玩?人是如何一步一步废掉的

不知道是不是只有我这样子,还是你们也有过类似的经历。 上学的时候总有很多光辉历史,学年名列前茅,或者单科目大佬,但是虽然慢慢地长大了,你开始懈怠了,开始废掉了。。。 什么?你说不知道具体的情况是怎么样的? 我来告诉你: 你常常潜意识里或者心理觉得,自己真正的生活或者奋斗还没有开始。总是幻想着自己还拥有大把时间,还有无限的可能,自己还能逆风翻盘,只不是自己还没开始罢了,自己以后肯定会变得特别厉害...

为什么程序员做外包会被瞧不起?

二哥,有个事想询问下您的意见,您觉得应届生值得去外包吗?公司虽然挺大的,中xx,但待遇感觉挺低,马上要报到,挺纠结的。

当HR压你价,说你只值7K,你该怎么回答?

当HR压你价,说你只值7K时,你可以流畅地回答,记住,是流畅,不能犹豫。 礼貌地说:“7K是吗?了解了。嗯~其实我对贵司的面试官印象很好。只不过,现在我的手头上已经有一份11K的offer。来面试,主要也是自己对贵司挺有兴趣的,所以过来看看……”(未完) 这段话主要是陪HR互诈的同时,从公司兴趣,公司职员印象上,都给予对方正面的肯定,既能提升HR的好感度,又能让谈判气氛融洽,为后面的发挥留足空间。...

面试:第十六章:Java中级开发(16k)

HashMap底层实现原理,红黑树,B+树,B树的结构原理 Spring的AOP和IOC是什么?它们常见的使用场景有哪些?Spring事务,事务的属性,传播行为,数据库隔离级别 Spring和SpringMVC,MyBatis以及SpringBoot的注解分别有哪些?SpringMVC的工作原理,SpringBoot框架的优点,MyBatis框架的优点 SpringCould组件有哪些,他们...

面试阿里p7,被按在地上摩擦,鬼知道我经历了什么?

面试阿里p7被问到的问题(当时我只知道第一个):@Conditional是做什么的?@Conditional多个条件是什么逻辑关系?条件判断在什么时候执...

面试了一个 31 岁程序员,让我有所触动,30岁以上的程序员该何去何从?

最近面试了一个31岁8年经验的程序猿,让我有点感慨,大龄程序猿该何去何从。

【阿里P6面经】二本,curd两年,疯狂复习,拿下阿里offer

二本的读者,在老东家不断学习,最后逆袭

大三实习生,字节跳动面经分享,已拿Offer

说实话,自己的算法,我一个不会,太难了吧

程序员垃圾简历长什么样?

已经连续五年参加大厂校招、社招的技术面试工作,简历看的不下于万份 这篇文章会用实例告诉你,什么是差的程序员简历! 疫情快要结束了,各个公司也都开始春招了,作为即将红遍大江南北的新晋UP主,那当然要为小伙伴们做点事(手动狗头)。 就在公众号里公开征简历,义务帮大家看,并一一点评。《启舰:春招在即,义务帮大家看看简历吧》 一石激起千层浪,三天收到两百多封简历。 花光了两个星期的所有空闲时...

《经典算法案例》01-08:如何使用质数设计扫雷(Minesweeper)游戏

我们都玩过Windows操作系统中的经典游戏扫雷(Minesweeper),如果把质数当作一颗雷,那么,表格中红色的数字哪些是雷(质数)?您能找出多少个呢?文中用列表的方式罗列了10000以内的自然数、质数(素数),6的倍数等,方便大家观察质数的分布规律及特性,以便对算法求解有指导意义。另外,判断质数是初学算法,理解算法重要性的一个非常好的案例。

《Oracle Java SE编程自学与面试指南》最佳学习路线图(2020最新版)

正确选择比瞎努力更重要!

面试官:你连SSO都不懂,就别来面试了

大厂竟然要考我SSO,卧槽。

微软为一人收购一公司?破解索尼程序、写黑客小说,看他彪悍的程序人生!...

作者 | 伍杏玲出品 | CSDN(ID:CSDNnews)格子衬衫、常掉发、双肩包、修电脑、加班多……这些似乎成了大众给程序员的固定标签。近几年流行的“跨界风”开始刷新人们对程序员的...

终于,月薪过5万了!

来看几个问题想不想月薪超过5万?想不想进入公司架构组?想不想成为项目组的负责人?想不想成为spring的高手,超越99%的对手?那么本文内容是你必须要掌握的。本文主要详解bean的生命...

我说我懂多线程,面试官立马给我发了offer

不小心拿了几个offer,有点烦

自从喜欢上了B站这12个UP主,我越来越觉得自己是个废柴了!

不怕告诉你,我自从喜欢上了这12个UP主,哔哩哔哩成为了我手机上最耗电的软件,几乎每天都会看,可是吧,看的越多,我就越觉得自己是个废柴,唉,老天不公啊,不信你看看…… 间接性踌躇满志,持续性混吃等死,都是因为你们……但是,自己的学习力在慢慢变强,这是不容忽视的,推荐给你们! 都说B站是个宝,可是有人不会挖啊,没事,今天咱挖好的送你一箩筐,首先啊,我在B站上最喜欢看这个家伙的视频了,为啥 ,咱撇...

立即提问
相关内容推荐