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

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

3个回答

每次都取出最小的两个节点组成一个新节点,所以应该是右图而不是左图吧

比如这个怎么来的为什么建出来是第一个图不是第二个图片

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
哈夫曼树带权路径长度简便算法问题
各位大神应该知道一棵 哈夫曼树的带权路径长度=所有叶子节点的带权路径长度和 应该也知道还有另一种算法 哈夫曼树的带权路径长度=所有非叶子结点的权值和 ![图片说明](https://img-ask.csdn.net/upload/201604/04/1459752161_872418.jpg) 有谁能证明一下这个吗? 或者告诉我哪本书上有讲这个证明的?
构造哈夫曼树,传回权值最小的两个数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); }
关于写哈夫曼树的思路
哪位能给一个写哈夫曼树的思路啊。我想了好久都不会写,不知道怎么才能把自己输入的东西用哈夫曼树翻译出来。求帮助
哈夫曼树算法设计编码译码
求大神帮忙用C++语言写一个算法设计 1)从键盘上输入要进行哈夫曼编码的字符集和对应的权值。 2)构造哈夫曼树的算法 3)完成哈夫曼编码的算法 4)完成哈夫曼译码算法。 5)利用编译码算法,对给定的文本文件t1.txt的英语内容进行编码,保存到指定文件code1.txt中。然后再编写一个函数对code1.txt中的内容进行译码。 要求输入哈夫曼编码时,能输出对应的字符。跪求了 真的没法写啊 想不到思路发到我哦空间或者是1511437725@qq.com都行啊
怎样打印哈夫曼树,在运行的时候可以看到自己的哈夫曼树?
怎样将自己构建的哈夫曼树打印出来,运行时能够看到自己的树,用横线个竖线形成的树,求高手解答,有代码的话能不能贴出来看看,学习学习,谢谢!
哈夫曼树与哈夫曼编码
利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。 设计要求:从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各个字符进行哈夫曼编码,最后打印输出字符及对应的哈夫曼编码。
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)显示功能:以先序遍历的顺序显示建立好的哈夫曼树。显示哈夫曼编码和译码的结果。
哈夫曼编码 程序设计报告
这个报告该怎么写? 哈夫曼编码/译码器 问题描述: 给定的一组电文,设计该电文的哈夫曼编码。 基本要求: (1)从终端读入字符集大小 n,及 n 个字符和 m 个权值,建立哈夫曼树, 并将它存于文件 hfmtree。 (2)利用已建好的哈夫曼树对文件中的正文进行编码,然后将结果存入文 件 codefile。 (3)利用已建好的哈夫曼树将文件中的代码进行译码,结果存入文件 textfile。 (4)输入表示权值的整数,且整数之和不超过 100。
横向打印哈夫曼树的问题
已经存储在二维数组中的哈夫曼树。怎么以树的形式横向打印出来,就是有分支的那种。
构造哈夫曼树的小问题
完整程序在这里:http://wenku.baidu.com/view/dde580a9376baf1ffc4fadbf template <class T> class HfmTree :public BinaryTree<T> { public: operator T()const { return weight; } T getW(){ return weight; } void putW(const T& x){ weight = x; } void SetNull(){ root = NULL; } int CreateHfmTree(T w[], int n); private: T weight; }; template <class T> int HfmTree<T> ::CreateHfmTree(T w[], int n) { PrioQueue <HfmTree<T> > pq(n); HfmTree<T> x, y, z, zero; for (int i = 0; i<n; i++){ z.MakeTree(w[i], x, y); z.putW(w[i]);////////////////////////////// pq.Append(z); z.SetNull();/////////////////////////////// } for (int i = 1; i<n; i++){ pq.Serve(x); pq.Serve(y); z.MakeTree(x.getW() + y.getW(), x, y); z.putW(x.getW() + y.getW());///////////////// cout<<z<<endl; ///////////////////////////// pq.Append(z); z.SetNull(); ////////////////////////////////// } pq.Serve(z); z.PreOrder(Visit); return z; } 问题: 1.为什么两个for循环 每次都要执行z.SetNull(); ? 2.z.putW(w[i]); 每次循环都会给weight付一个值,但每次循环完一次后都会覆盖掉前一个weight,那么为什z.MakeTree(x.getW() + y.getW(), x, y)中 x.getW() 和 y.getW()还能识别出来呢? 3.为什么cout<<z<<endl; 能够执行? 对象 也能够被打印? ![图片说明](https://img-ask.csdn.net/upload/201508/16/1439723139_255692.png)
哈夫曼编码/译码系统要怎么写
【问题描述】 设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(压缩文件,后缀名.cod);反过来,可将一个压缩文件译码还原为一个文本文件(.txt)。 【基本要求】 (1) 输入一个待压缩的文本文件名,统计文本文件中各字符的个数作为权值,生成哈夫曼树; (2) 将文本文件利用哈夫曼树进行编码,生成压缩文件(后缀名cod), (3) 输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码; (4) 显示指定的压缩文件和文本文件; (5)界面友好,易与操作。采用菜单方式进行选择。 (6)把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算进行真正的数据压缩,并求压缩比。 (7)显示哈夫曼树; (8)使用汉字显示。
求一段可以打印哈夫曼树的代码,能够在执行时看到的,谢谢!!
求一段可以将我写的哈夫曼树打印出来的代码,谢谢!!我正在写一个huffman的编码和译码的程序可是不会写打印的,请大家帮忙
C++哈夫曼树压缩的问题
在利用哈夫曼树进行压缩时,建立好哈夫曼树,得到得到每个叶子节点中的字符编码之后,如何使用位运算将编码中的每个位(BIT)设置到一个char类型的位缓冲中,可能多个编码才能填满一个位缓冲,每填满一次,将位缓冲区以单个字节的形式写入文件。这涉及到哪方面的知识,谢谢
求教,哈夫曼树问题,感觉好难
大佬们,哈夫曼编码的问题,编码完毕后,下次不初始化,怎么从文件中读出哈夫曼树?怎么打印哈夫曼树?
一个程序,哈夫曼树的构造遍历打印,编码解码,缺少遍历和打印
#include <stdio.h> #include <string.h> /* 数组头文件 */ #include <conio.h> #define MAX 999 /* 定义长度 */ typedef struct{ /* 定义哈夫曼编码的结构数组 */ char data; int weight; /* 定义权值 */ int parent; int lchild; int rchild; }huffmannode; typedef struct{ /* 定义保存哈夫曼结构体 */ char bits[50]; int start; }huffmancode ; void main() { huffmannode ht[100]; /* 定义储存权值的空间 */ huffmancode cd[100]; char string[100]; /* 定义数组存储空间 */ char hcd[100]; int i,j,x,y,s1,s2,m1,m2,n,c,f,k; printf("please input the n ="); /* 输入字符的个数 */ scanf("%d",&n); printf("\n============================\n"); for(i=0;i<n;i++) { getchar(); /* 获得输入的字符 */ printf("please input the value :"); scanf("%c",&ht[i].data); /* 输入字符函数 */ printf("please input the weight:\n"); scanf("%d",&ht[i].weight); } printf("\n=============================\n"); 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++) { s1=s2=0; /* 初始化变量 */ m1=m2=MAX; for (j=0;j<i;j++) { if (ht[j].weight<m1 &&ht[j].parent==-1) /* 寻找无父结点的最小值 */ { m2=m1; s2=s1; m1=ht[j].weight; s1=j; /* 寻找当前最小值 */ } else if(ht[j].weight<m2 &&ht[j].parent==-1) /* 寻找无父结点的次小值 */ { m2=ht[j].weight; s2=j; } /* 寻找次小值 */ } ht[s1].parent=i; /* s1的父结点为i */ ht[s2].parent=i; ht[i].weight=m1+m2; /* 最小值的权值相加为i的权值 */ ht[i].lchild=s1; /* i的左子为s1 */ ht[i].rchild=s2; /* i的右子为s2 */ } for(i=0;i<n;i++) { cd[i].start=n; x=i; y=ht[x].parent; /* 记录父结点 */ while (y!=-1) { if (ht[y].lchild==x) cd[i].bits[cd[i].start]='0'; /* 给字符赋0值 */ else cd[i].bits[cd[i].start]='1'; /* 给字符赋1值 */ cd[i].start--; x=y; y=ht[y].parent; } } printf("\cout the huffmancode:\n"); for (i=0;i<n;i++) { printf("%c:",ht[i].data); /* 输出字符 */ for(j=cd[i].start;j<=n;j++){ printf("%c",cd[i].bits[j]); /* 输出字符的01代码 */ } printf("\n"); } printf("\n=============================\n"); printf("\n Please input the message:\n"); scanf("%s",string); /* 输入字符串 */ for(i=0;string[i]!='0';i++) { for(c=0;c<=n;c++) if(string[i]==ht[c].data) /* 寻找与输入字符相匹配的字母 */ { for(j=cd[c].start;j<=n;j++) printf("%c",cd[c].bits[j]); /* 输出字母代码 */ break; } } printf("\n=============================\n"); printf("Please input the HuffmanCode:\n"); scanf("%s",hcd); /* 输入0、1代码 */ f=2*n-2; for(i=0;hcd[i]!='\0';i++) { if(hcd[i]=='0') /* 判断输入为0,寻找左子 */ f=ht[f].lchild; else if(hcd[i]=='1') f=ht[f].rchild; /* 判断输入为1,寻找右子 */ if(f<n) { printf("%c",ht[f].data); /* 输出字符串 */ f=2*n-2; } } printf("\n"); getch(); }
哈夫曼树构造过程中出现乱码?
程序是根据用户输入的一些列字符及其对应的权值,生成哈夫曼树,再根据生成的哈夫曼树进行编码,在测试时,发现输出每个元素对应的哈夫曼编码时,总会出现一些乱码的文字,知道原因的网友点拨一些,谢谢。程序如下: ``` #include <iostream> #include<string> using namespace std; class HuffNode { public: char c; // 结点的字符 int weight; // 权值 int parent, lChild, rChild; // 左右孩子指针 }; class HuffTree { private: int Node_cnt=0; HuffNode* huff=NULL; string* HuffCode = NULL; public: HuffTree(int n, char* c, int* weights); // 创建Huffman树 ~HuffTree(); // 析构函数 void setNode_cnt(int cnt){ Node_cnt = cnt; } void select(int end, int& index1, int& index2); // 选出最小和次小叶子结点 void printHuffTree(); void setHuffCode(); void printHuffCode(); }; HuffTree::~HuffTree() { delete[] huff; delete[] HuffCode; } void HuffTree::printHuffCode() { for (int i = 0; i < Node_cnt; i++) { cout << huff[i].c << "的哈夫曼编码为:" << HuffCode[i] << endl; } } void HuffTree::setHuffCode() // 左孩子为0,右孩子为1 { HuffCode = new string[Node_cnt]; for (int i = 0; i < Node_cnt; i++) { int son, father; // 孩子指针和双亲指针 int cnt = 0; string str; son = i; father = huff[son].parent; while (father != -1) { if (huff[father].lChild == son) { str.append("0"); } else { str.append("1"); } son = father; // 孩子指针为当前双亲指针 father = huff[father].parent; // 双亲指针为当前双亲指针的双亲 } HuffCode[i] = new char[str.size()]; for (unsigned int j = 0; j < str.size(); j++) // 由于求哈夫曼编码时是从叶子结点一直找到树根,故编码为之前的逆序 { HuffCode[i][j] = str[str.size() - 1-j];// 逆序 } } } HuffTree::HuffTree(int n,char* ch,int* weights){ Node_cnt = n; huff = new HuffNode[2 * Node_cnt - 1]; for (int i = 0; i < Node_cnt; i++) // 初始化 { huff[i].c = ch[i]; huff[i].weight = weights[i]; huff[i].lChild = -1; huff[i].rChild = -1; huff[i].parent = -1; } for (int i = Node_cnt; i < Node_cnt * 2 - 1; i++) { int index1 = -1, index2 = -1; select(i - 1, index1, index2);// 选出最小和次小中间树结点索引 huff[index1].parent = i; huff[index2].parent = i; huff[i].weight = huff[index1].weight + huff[index2].weight; huff[i].lChild = index1; huff[i].rChild = index2; huff[i].parent = -1; } } void HuffTree::printHuffTree() { cout << "所建哈夫曼静态链表示如下:" << endl; cout << "位置\t" << "字符\t" << "权值\t" << "双亲\t" << "左孩子\t" << "右孩子\t" << endl; for (int i = 0; i < Node_cnt*2-1; i++) { cout << i << "\t" << huff[i].c << "\t" << huff[i].weight << "\t" << huff[i].parent << "\t" << huff[i].lChild << "\t" << huff[i].rChild << endl; } } void HuffTree::select(int end, int& index1, int& index2) { int min1=100000,min2 = 100000; // 设m1为最小值,m2为次小值 for (int j = 0; j <=end; j++) { if (huff[j].parent == -1) { if (huff[j].weight < min1) // 如果当前权值比最小值小 { index2 = index1; index1 = j; min2 = min1; min1 = huff[j].weight; } else if (huff[j].weight < min2) // 如果当前权值比次小值小 { min2 = huff[j].weight; index2 = j; } } } } int main() { int n; cout << "请输入树叶结点的个数(小于等于1结束):" << endl; cin >> n; if (n < 1) return 0; char chs[256]; int weights[256]; for (int i = 0; i < n; i++){ cout << "请输入第" << i+1 << "个字符及权值" << endl; cin >> chs[i] >> weights[i]; } HuffTree tree(n,chs,weights); tree.printHuffTree(); tree.setHuffCode(); tree.printHuffCode(); return 0; } ```
基于哈夫曼树的数据压缩算法
A 基于哈夫曼树的数据压缩算法 时间限制(C/C++):1000MS/3000MS 运行内存限制:65536KByte 总提交:445 测试通过:131 描述 输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入 多组数据,每组数据一行,为一个字符串(只考虑26个小写字母即可)。当输入字符串为“0”时,输入结束。 输出 每组数据输出2n+4行(n为输入串中字符类别的个数)。第一行为统计出来的字符出现频率(只输出存在的字符,格式为:字符:频度),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第二行至第2n行为哈夫曼树的存储结构的终态(形如教材139页表5.2(b),一行当中的数据用空格分隔)。第2n+2行为每个字符的哈夫曼编码(只输出存在的字符,格式为:字符:编码),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2n+3行为编码后的字符串,第2n+4行为解码后的字符串(与输入的字符串相同)。 样例输入 aaaaaaabbbbbccdddd aabccc 0 样例输出 a:7 b:5 c:2 d:4 1 7 7 0 0 2 5 6 0 0 3 2 5 0 0 4 4 5 0 0 5 6 6 3 4 6 11 7 2 5 7 18 0 1 6 a:0 b:10 c:110 d:111 00000001010101010110110111111111111 aaaaaaabbbbbccdddd a:2 b:1 c:3 1 2 4 0 0 2 1 4 0 0 3 3 5 0 0 4 3 5 2 1 5 6 0 3 4 a:11 b:10 c:0 111110000 aabccc
数据结构作业,三叉哈夫曼树的实现
这是我用二叉哈夫曼树代码改的,但是无法实现,首先是叶子节点和节点数没法表示,然后就算自己输入固定节点也无法正确实现,请问怎么实现三叉哈夫曼树呢 #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; typedef struct { unsigned int weight; //结点权值 unsigned int parent, lchild, rchild; //结点的父指针,左右孩子指针 }HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表 HuffmanTree HT; //哈夫曼树HT HuffmanCode HC; //哈夫曼编码表HC unsigned int *w; //w存放叶子结点权值 char * source_code;//source_code 存放原始码 void CreateHuffmanTree(HuffmanTree &, unsigned int*, int); //生成一棵哈夫曼树 void HuffmanCoding(HuffmanTree, HuffmanCode &, int); //对哈夫曼树进行编码 void PrintHuffmanCode(HuffmanCode, unsigned int*, int); //显示哈夫曼编码 void Select(HuffmanTree, int, int&, int&); //在数组中寻找权值最小的两个结点 int main() { int n, i; //n是哈夫曼树叶子结点数 char choose = 'y'; //用于选择程序是否退出 //程序解说 printf("本程序将演示构造哈夫曼树.\n"); printf("首先输入叶子结点数目.\n例如:2\n"); printf("然后输入原始码以及权值.\n"); printf("第1个原始码及其权值 :"); printf("a 5\n"); printf("第2个原始码及其权值 :"); printf("b 3\n"); printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n"); cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl; printf(" 5 a 1\n"); printf(" 3 b 0\n"); putchar('\n'); putchar('\n'); while (choose != 'N'&&choose != 'n') { printf("请输入叶子结点数目:"); scanf("%d", &n); //输入叶子结点数 if (n <= 1) { printf("该数不合理!\n"); continue; } w = (unsigned int*)malloc(n * sizeof(unsigned int)); //开辟空间存放权值 source_code = (char *)malloc(n * sizeof(char)); //开辟空间存放原始码 //printf("请输入各原始码以及权值 :\n"); for (i = 0; i < n; i++) { printf("第%d个原始码及其权值 :", i + 1); cin >> source_code[i]; //输入原始码 cin >> w[i]; //输入各叶子结点权值 } CreateHuffmanTree(HT, w, n); //生成哈夫曼树 HuffmanCoding(HT, HC, n); //进行哈夫曼编码 putchar('\n'); PrintHuffmanCode(HC, w, n); //显示哈夫曼编码 printf("哈夫曼树构造完毕,还要继续吗?(Y/N)"); scanf(" %c", &choose); } } void CreateHuffmanTree(HuffmanTree &HT, unsigned int *w, int n) {//w存放n个结点的权值,将构造一棵哈夫曼树HT int i, m; int s1, s2; HuffmanTree p; if (n <= 1) return; m = 2 * n - 1; //n个叶子结点的哈夫曼树,有2*n-1个结点 HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //开辟2*n各结点空间,0号单元不用 for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w) //进行初始化 { p->weight = *w; p->parent = 0; p->lchild = 0; p->rchild = 0; } for (; i <= m; ++i, ++p) { p->weight = 0; p->parent = 0; p->lchild = 0; p->rchild = 0; } for (i = n + 1; i <= m; ++i) //建哈夫曼树 { //从HT[1...i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 Select(HT, i - 1, s1, s2); HT[s1].parent = i; HT[s2].parent = i; //修改s1和s2结点的父指针parent HT[i].lchild = s1; HT[i].rchild = s2; //修改i结点的左右孩子指针 HT[i].weight = HT[s1].weight + HT[s2].weight; //修改权值 } } void HuffmanCoding(HuffmanTree HT, HuffmanCode &HC, int n) { //将有n个叶子结点的哈夫曼树HT进行编码, 所编的码存放在HC中 //方法是从叶子到根逆向求每个叶子结点的哈夫曼编码 int i, c, f, start; char *cd; HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //分配n个编码的头指针向量 cd = (char *)malloc(n * sizeof(char)); //开辟一个求编码的工作空间 cd[n - 1] = '\0'; //编码结束符 for (i = 1; i <= n; ++i) //逐个地求哈夫曼编码 { start = n - 1; //编码结束位置 for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) //从叶子到根逆向求编码 if (HT[f].lchild == c) cd[--start] = '0'; //若是左孩子编为'0' else cd[--start] = '1'; //若是右孩子编为'1' HC[i] = (char *)malloc((n - start) * sizeof(char)); //为第i个编码分配空间 strcpy(HC[i], &cd[start]); //将编码从cd复制到HC中 } free(cd); //释放工作空间 } void PrintHuffmanCode(HuffmanCode HC, unsigned int *w, int n) { //显示有n个叶子结点的哈夫曼树的编码表 int i; printf("哈夫曼编码如下 :\n"); putchar('\n'); cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl; for (i = 1; i <= n; i++) { printf(" %d", w[i - 1]); printf(" %3c\t ", source_code[i - 1]); puts(HC[i]); } printf("\n"); } void Select(HuffmanTree HT, int t, int&s1, int&s2) { //在HT[1...t]中选择parent不为0且权值最小的两个结点,其序号分别为s1和s2,s1存放最小的,s2存放次小的 int i = 0; int j = 0; int k = 0; int least = 0; int second = 0; for (i = 1; i <= t; i++) { if (HT[i].parent == 0) break; } for (j = i + 1; j <= t; j++) { if (HT[j].parent == 0) break; } if (HT[i].weight < HT[j].weight) { least = i; second = j; } else { least = j; second = i; } for (k = j + 1; k <= t; k++) { if (HT[k].parent == 0) { if (HT[k].weight < HT[least].weight) { second = least; least = k; } else if (HT[k].weight >= HT[least].weight && HT[k].weight < HT[second].weight) second = k; } } s1 = least; s2 = second; }
用c++构建一个哈夫曼树
输入字符个数,权值,打印哈夫曼树,编码和译码,源代码,可以用c-free运行的那种,求各位大神帮忙解答,要完整的代码拜托了
相见恨晚的超实用网站
相见恨晚的超实用网站 持续更新中。。。
Java学习的正确打开方式
在博主认为,对于入门级学习java的最佳学习方法莫过于视频+博客+书籍+总结,前三者博主将淋漓尽致地挥毫于这篇博客文章中,至于总结在于个人,实际上越到后面你会发现学习的最好方式就是阅读参考官方文档其次就是国内的书籍,博客次之,这又是一个层次了,这里暂时不提后面再谈。博主将为各位入门java保驾护航,各位只管冲鸭!!!上天是公平的,只要不辜负时间,时间自然不会辜负你。 何谓学习?博主所理解的学习,它是一个过程,是一个不断累积、不断沉淀、不断总结、善于传达自己的个人见解以及乐于分享的过程。
程序员必须掌握的核心算法有哪些?
由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,我稍微总结一下我学过的算法知识点,以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的,并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构,当然,我也会整理一些看过...
有哪些让程序员受益终生的建议
从业五年多,辗转两个大厂,出过书,创过业,从技术小白成长为基层管理,联合几个业内大牛回答下这个问题,希望能帮到大家,记得帮我点赞哦。 敲黑板!!!读了这篇文章,你将知道如何才能进大厂,如何实现财务自由,如何在工作中游刃有余,这篇文章很长,但绝对是精品,记得帮我点赞哦!!!! 一腔肺腑之言,能看进去多少,就看你自己了!!! 目录: 在校生篇: 为什么要尽量进大厂? 如何选择语言及方...
大学四年自学走来,这些私藏的实用工具/学习网站我贡献出来了
大学四年,看课本是不可能一直看课本的了,对于学习,特别是自学,善于搜索网上的一些资源来辅助,还是非常有必要的,下面我就把这几年私藏的各种资源,网站贡献出来给你们。主要有:电子书搜索、实用工具、在线视频学习网站、非视频学习网站、软件下载、面试/求职必备网站。 注意:文中提到的所有资源,文末我都给你整理好了,你们只管拿去,如果觉得不错,转发、分享就是最大的支持了。 一、电子书搜索 对于大部分程序员...
linux系列之常用运维命令整理笔录
本博客记录工作中需要的linux运维命令,大学时候开始接触linux,会一些基本操作,可是都没有整理起来,加上是做开发,不做运维,有些命令忘记了,所以现在整理成博客,当然vi,文件操作等就不介绍了,慢慢积累一些其它拓展的命令,博客不定时更新 free -m 其中:m表示兆,也可以用g,注意都要小写 Men:表示物理内存统计 total:表示物理内存总数(total=used+free) use...
比特币原理详解
一、什么是比特币 比特币是一种电子货币,是一种基于密码学的货币,在2008年11月1日由中本聪发表比特币白皮书,文中提出了一种去中心化的电子记账系统,我们平时的电子现金是银行来记账,因为银行的背后是国家信用。去中心化电子记账系统是参与者共同记账。比特币可以防止主权危机、信用风险。其好处不多做赘述,这一层面介绍的文章很多,本文主要从更深层的技术原理角度进行介绍。 二、问题引入 假设现有4个人...
程序员接私活怎样防止做完了不给钱?
首先跟大家说明一点,我们做 IT 类的外包开发,是非标品开发,所以很有可能在开发过程中会有这样那样的需求修改,而这种需求修改很容易造成扯皮,进而影响到费用支付,甚至出现做完了项目收不到钱的情况。 那么,怎么保证自己的薪酬安全呢? 我们在开工前,一定要做好一些证据方面的准备(也就是“讨薪”的理论依据),这其中最重要的就是需求文档和验收标准。一定要让需求方提供这两个文档资料作为开发的基础。之后开发...
网页实现一个简单的音乐播放器(大佬别看。(⊙﹏⊙))
今天闲着无事,就想写点东西。然后听了下歌,就打算写个播放器。 于是乎用h5 audio的加上js简单的播放器完工了。 演示地点演示 html代码如下` music 这个年纪 七月的风 音乐 ` 然后就是css`*{ margin: 0; padding: 0; text-decoration: none; list-...
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...
通俗易懂地给女朋友讲:线程池的内部原理
餐盘在灯光的照耀下格外晶莹洁白,女朋友拿起红酒杯轻轻地抿了一小口,对我说:“经常听你说线程池,到底线程池到底是个什么原理?”
《奇巧淫技》系列-python!!每天早上八点自动发送天气预报邮件到QQ邮箱
将代码部署服务器,每日早上定时获取到天气数据,并发送到邮箱。 也可以说是一个小型人工智障。 知识可以运用在不同地方,不一定非是天气预报。
经典算法(5)杨辉三角
杨辉三角 是经典算法,这篇博客对它的算法思想进行了讲解,并有完整的代码实现。
英特尔不为人知的 B 面
从 PC 时代至今,众人只知在 CPU、GPU、XPU、制程、工艺等战场中,英特尔在与同行硬件芯片制造商们的竞争中杀出重围,且在不断的成长进化中,成为全球知名的半导体公司。殊不知,在「刚硬」的背后,英特尔「柔性」的软件早已经做到了全方位的支持与支撑,并持续发挥独特的生态价值,推动产业合作共赢。 而对于这一不知人知的 B 面,很多人将其称之为英特尔隐形的翅膀,虽低调,但是影响力却不容小觑。 那么,在...
腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹?
昨天,有网友私信我,说去阿里面试,彻底的被打击到了。问了为什么网上大量使用ThreadLocal的源码都会加上private static?他被难住了,因为他从来都没有考虑过这个问题。无独有偶,今天笔者又发现有网友吐槽了一道腾讯的面试题,我们一起来看看。 腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹? 在互联网职场论坛,一名程序员发帖求助到。二面腾讯,其中一个算法题:64匹...
面试官:你连RESTful都不知道我怎么敢要你?
干货,2019 RESTful最贱实践
刷了几千道算法题,这些我私藏的刷题网站都在这里了!
遥想当年,机缘巧合入了 ACM 的坑,周边巨擘林立,从此过上了"天天被虐似死狗"的生活… 然而我是谁,我可是死狗中的战斗鸡,智力不够那刷题来凑,开始了夜以继日哼哧哼哧刷题的日子,从此"读题与提交齐飞, AC 与 WA 一色 ",我惊喜的发现被题虐既刺激又有快感,那一刻我泪流满面。这么好的事儿作为一个正直的人绝不能自己独享,经过激烈的颅内斗争,我决定把我私藏的十几个 T 的,阿不,十几个刷题网...
SQL-小白最佳入门sql查询一
不要偷偷的查询我的个人资料,即使你再喜欢我,也不要这样,真的不好;
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的使用等,会持续更新......
吐血推荐珍藏的Visual Studio Code插件
作为一名Java工程师,由于工作需要,最近一个月一直在写NodeJS,这种经历可以说是一部辛酸史了。好在有神器Visual Studio Code陪伴,让我的这段经历没有更加困难。眼看这段经历要告一段落了,今天就来给大家分享一下我常用的一些VSC的插件。 VSC的插件安装方法很简单,只需要点击左侧最下方的插件栏选项,然后就可以搜索你想要的插件了。 下面我们进入正题 Material Theme ...
实战:如何通过python requests库写一个抓取小网站图片的小爬虫
有点爱好的你,偶尔应该会看点图片文字,最近小网站经常崩溃消失,不如想一个办法本地化吧,把小照片珍藏起来! 首先,准备一个珍藏的小网站,然后就可以开始啦! 第一步 我们先写一个获取网站的url的链接,因为url常常是由page或者,其他元素构成,我们就把他分离出来,我找到的网站主页下有图片区 图片区内有标题页,一个标题里有10张照片大概 所以步骤是: 第一步:进入图片区的标题页 def getH...
“狗屁不通文章生成器”登顶GitHub热榜,分分钟写出万字形式主义大作
一、垃圾文字生成器介绍 最近在浏览GitHub的时候,发现了这样一个骨骼清奇的雷人项目,而且热度还特别高。 项目中文名:狗屁不通文章生成器 项目英文名:BullshitGenerator 根据作者的介绍,他是偶尔需要一些中文文字用于GUI开发时测试文本渲染,因此开发了这个废话生成器。但由于生成的废话实在是太过富于哲理,所以最近已经被小伙伴们给玩坏了。 他的文风可能是这样的: 你发现,...
程序员:我终于知道post和get的区别
是一个老生常谈的话题,然而随着不断的学习,对于以前的认识有很多误区,所以还是需要不断地总结的,学而时习之,不亦说乎
《程序人生》系列-这个程序员只用了20行代码就拿了冠军
你知道的越多,你不知道的越多 点赞再看,养成习惯GitHub上已经开源https://github.com/JavaFamily,有一线大厂面试点脑图,欢迎Star和完善 前言 这一期不算《吊打面试官》系列的,所有没前言我直接开始。 絮叨 本来应该是没有这期的,看过我上期的小伙伴应该是知道的嘛,双十一比较忙嘛,要值班又要去帮忙拍摄年会的视频素材,还得搞个程序员一天的Vlog,还要写BU...
加快推动区块链技术和产业创新发展,2019可信区块链峰会在京召开
11月8日,由中国信息通信研究院、中国通信标准化协会、中国互联网协会、可信区块链推进计划联合主办,科技行者协办的2019可信区块链峰会将在北京悠唐皇冠假日酒店开幕。   区块链技术被认为是继蒸汽机、电力、互联网之后,下一代颠覆性的核心技术。如果说蒸汽机释放了人类的生产力,电力解决了人类基本的生活需求,互联网彻底改变了信息传递的方式,区块链作为构造信任的技术有重要的价值。   1...
相关热词 c#委托 逆变与协变 c#新建一个项目 c#获取dll文件路径 c#子窗体调用主窗体事件 c# 拷贝目录 c# 调用cef 网页填表c#源代码 c#部署端口监听项目、 c#接口中的属性使用方法 c# 昨天
立即提问