大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
#includeusing namespace std;
class HufTree{public:
float weight = 0; // 权重
int parent = 0; // 双亲
int lchi = 0; // 左孩子
int rchi = 0; // 右孩子
void CreatHT(HufTree* &HT, int n); // 创建哈夫曼树方法
void Select(HufTree* &HT, int k, int &s1, int &s2); // 得到权重最小的次小的下标方法
char** Code(HufTree* HT, int n); //实现哈夫曼编码方法
};
void HufTree::CreatHT(HufTree* &HT, int n){int s1, s2; // 声明权重最小的下标s1和次小的下标s2
HT = new HufTree[2 * n]; // 定义数组长度,0号位置不用,所以数组长度定义为2n-1+1,2n+1为最终哈夫曼树的总结点数
// 输入每个结点的权重
for(int i = 1; i< n + 1; ++i){cout<< "请输入第 "<< i<< " 个结点的权重值:"<< endl;
cin >>HT[i].weight;
}
for(int i = n + 1; i< 2 * n; ++i){Select(HT, i - 1, s1, s2); // 选出权重最小的两个结点
HT[i].weight = HT[s1].weight + HT[s2].weight; // 结合两个小结点得到一个新结点
HT[i].lchi = s1; // 新结点的左孩子为s1
HT[i].rchi = s2; // 新结点的有孩子为s2
HT[s1].parent = i; // s1的双亲是i
HT[s2].parent = i; // s2的双亲是i
}
}
void HufTree::Select(HufTree* &HT, int k, int &s1, int &s2){// k为已有结点的长度加1(因为0号位置未使用)
float t = 100; // 初始化一个常数t
// 通过比较得出s1
for(int i = 1; i< k + 1; ++i){if(t >HT[i].weight && HT[i].parent == 0){s1 = i;
t = HT[i].weight;
}
}
t = 100; // 重新初始化t
// 通过跳过s1比较得到s2
for(int i = 1; i< k + 1; ++i){if(i == s1) continue;
if(t >= HT[i].weight && HT[i].parent == 0){s2 = i;
t = HT[i].weight;
}
}
}
char** HufTree::Code(HufTree* HT, int n){char** HC = new char* [n + 1]; // 声明一个二维字符数组,用以接收原数组需要编码的字符的编码
char* cd = new char[n]; // 声明一个一维字符数组用以储存
cd[n - 1] = '\0'; // cd数组的最后一位加上终止符
// 遍历原数组需要编码的每个字符
for(int i = 1; i< n + 1; ++i){int j = i; // j用于在while循环内实现从叶子结点找双亲
int k = n - 2; // k用于记录当前cd数组空的位置,由于从叶子结点找双亲的话编码顺序是反的,所以要从尾部开始存入0和1
while(HT[j].parent != 0){// 若当前结点的双亲为0,说明已遍历到根结点,遍历完毕
// 若该叶子的双亲结点的左孩子为该叶子结点,则cd数组计入0
if(HT[HT[j].parent].lchi == j){cd[k] = '0';
--k; // k指向cd数组的前一个位置
}
// 若该叶子的双亲结点的右孩子为该叶子结点,则cd数组计入1
if(HT[HT[j].parent].rchi == j){cd[k] = '1';
--k; // k指向cd数组的前一个位置
}
j = HT[j].parent; // 此时遍历的结点更新为当前结点的双亲
}
HC[i] = new char[n - k]; // 申请一个和当前cd数组一样大小的字符数组,另二维数组中的第i个一维数组指针指向该字符数组
strcpy(HC[i], &cd[k + 1]); // 将cd中包括k从k之后的所有字符复制给HC的第i个字符数组
}
delete [] cd; // 释放掉cd数组的空间
return HC; // 返回HC二维指针
}
int main()
{HufTree *a; // 实例化一个HufTree指针a
a->CreatHT(a, 7); // 调用a中的创建方法创建一棵哈夫曼树
char** p = a->Code(a, 7); // 实例化一个二维数组指针指向哈夫曼编码数组
// 打印二维数组
for(int i = 1; i< 8; ++i){for(int j = 0; j< 7; ++j){cout<< p[i][j];
}
cout<< endl;
}
delete a; // 释放掉a的空间
// 释放掉二维数组p中的指针指向的空间
for(int i = 0; i< 8; ++i){delete [] p[i];
}
delete [] p; // 释放掉指向二维数组p的空间
return 0;
}
实现创建包含7个元素的哈夫曼树以及输出其对应的哈夫曼编码。如有错误的地方,还请不吝赐教。
创新互联建站凭借在网站建设、网站推广领域领先的技术能力和多年的行业经验,为客户提供超值的营销型网站建设服务,我们始终认为:好的营销型网站就是好的业务员。我们已成功为企业单位、个人等客户提供了网站设计制作、网站设计服务,以良好的商业信誉,完善的服务及深厚的技术力量处于同行领先地位。你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧