C语言输入一组权值,例如5,6,2, 9, 7,8,构造一颗哈夫曼树,以直观的方式打印该哈夫曼树,并给出各个结点的编码值。二叉树的存储结构定义: typedef struct int weght;
int parent,lch, rch: *HuffmanTree;
输入一组权值,例如[5,6, 2, 9,7,8],构造一颗哈夫曼树,以直观的方式打印该哈夫曼树,可分以下层次: (1)创建哈夫曼树
(2)以左右孩 子的身份打印哈夫曼树
(3)以表格的形式打印哈夫曼树
(4)创建哈夫曼树,并以树的形式打印哈夫曼树
二叉树的应用(数据结构)
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- 赵4老师 2023-10-24 16:19关注
仅供参考:
#include <iostream> #include <string> using namespace std; struct huffTree { int parent; int lchild; int rchild; int weight; string flag; }; struct Lowest_node { char ch; int ch_num; }; void coding(int length,huffTree *tree,int n,int &a,int &b) { int i; int r,s; r=s=length; for (i=0;i<n;i++) { if (tree[i].weight<r && tree[i].parent==-1) { r=tree[i].weight; a=i; } } for (i=0;i<n;i++) { if (tree[i].weight<s && i!=a && tree[i].parent==-1) { s=tree[i].weight; b=i; } } } void frequency(string str) { int i,j; int length=str.length(); Lowest_node *node=new Lowest_node[length]; for (i=0;i<length;i++) node[i].ch_num=0; int char_type_num=0; for (i=0;i<length;i++) { for (j=0;j<char_type_num;j++) if (str[i]==node[j].ch || ('a'<=node[j].ch && node[j].ch<='z' && str[i]+32==node[j].ch)) break;// if (j<char_type_num) node[j].ch_num++; else { if ('A'<=str[i] && str[i] <= 'Z') node[j].ch=str[i]+32; else node[j].ch=str[i]; node[j].ch_num++; char_type_num++; } } for (i=0;i<char_type_num;i++) { for (j=i;j<char_type_num;j++) { if (node[j].ch_num<node[j+1].ch_num) { int temp; char ch_temp; temp=node[j].ch_num; ch_temp=node[j].ch; node[j].ch_num=node[j+1].ch_num; node[j].ch=node[j+1].ch; node[j+1].ch_num=temp; node[j+1].ch=ch_temp; } } } for (i=0;i<char_type_num;i++) cout<<"字符"<<node[i].ch<<"出现了"<<node[i].ch_num<<"次"<<endl; huffTree *huff=new huffTree[2*char_type_num-1]; huffTree temp; string *code=new string[2*char_type_num-1]; for (i=0;i<2*char_type_num-1;i++) { huff[i].lchild=-1; huff[i].parent=-1; huff[i].rchild=-1; huff[i].flag=-1; } for (j=0;j<char_type_num;j++) huff[j].weight=node[j].ch_num; int min1,min2; for (int k=char_type_num;k<2*char_type_num-1;k++) { coding(length,huff,k,min1,min2); huff[min1].parent=k; huff[min2].parent=k; huff[min1].flag="0"; huff[min2].flag="1"; huff[k].lchild=min1; huff[k].rchild=min2; huff[k].weight=huff[min1].weight+huff[min2].weight; } for (i=0;i<char_type_num;i++) { temp=huff[i]; while (1) { code[i]=temp.flag+code[i]; temp=huff[temp.parent]; if (temp.parent==-1) break;// } } cout<<"字符串的每个字符huffman编码为:"<<endl; for (i=0;i<char_type_num;i++) cout<<node[i].ch<<" "<<code[i]<<endl; cout<<"整个字符串的huffman编码为:"<<endl; for (i=0;i<length;i++) { //S? for (j=0;j<char_type_num;j++) { if (str[i]==node[j].ch) cout<<code[j]; } } delete[] node; node=NULL; delete[] huff; huff=NULL; delete[] code; code=NULL; } int main() { int length=0; string str; cout<<"请输入一个字符串:"; cin>>str; frequency(str); return 0; } //请输入一个字符串:2333abcde //字符3出现了3次 //字符2出现了1次 //字符a出现了1次 //字符b出现了1次 //字符c出现了1次 //字符d出现了1次 //字符e出现了1次 //字符串的每个字符huffman编码为: //3 11 //2 000 //a 001 //b 010 //c 011 //d 100 //e 101 //整个字符串的huffman编码为: //000111111001010011100101
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 mySQL5.7.34安装遇到的问题
- ¥15 结构功能耦合指标计算
- ¥20 visual studio中c语言用ODBC链接SQL SERVER
- ¥50 AI大模型精调(百度千帆、飞浆)
- ¥15 非科班怎么跑代码?如何导数据和调参
- ¥15 福州市的全人群死因监测点死亡原因报表
- ¥15 Altair EDEM中生成一个颗粒,并且各个方向没有初始速度
- ¥15 系统2008r2 装机配置推荐一下
- ¥15 悬赏Python-playwright部署在centos7上
- ¥15 psoc creator软件有没有人能远程安装啊