当前位置： 首页 > news >正文

大渡口网站建设网络营销推广及优化方案

news 2025/7/22 7:17:10
大渡口网站建设,网络营销推广及优化方案,优推宝可以做自己网站吗,石家庄城乡建设管理局网站哈夫曼树（最优二叉树） 1）基础概念 **路径：**从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。 **结点的路径长度：**两结点间路径上的分支数。 **树的路径长度：**从树根到每一个结点的路径…

哈夫曼树（最优二叉树）

1）基础概念

**路径：**从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

**结点的路径长度：**两结点间路径上的分支数。

在这里插入图片描述

**树的路径长度：**从树根到每一个结点的路径长度之和。记作：TL。

在这里插入图片描述

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。

**权：**将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

**结点的带权路径长度：**从根结点到该结点之间的路径长度与该结点的权的乘积。

**树的带权路径长度：**树中所有叶子结点的带权路径长度之和。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

2）构造哈夫曼树

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

顺序存储结构——一维结构数组

（1）定义结构

在这里插入图片描述

typedef struct {int weight; int parent, lch, rch;
}HTNode, * HuffmanTree;HuffmanTree H;
（2）步骤：

在这里插入图片描述
在这里插入图片描述

  1. 初始化HT [1…2n-1]：lch = rch = parent = 0；
  2. 输入初始几个叶子结点：置HT[1…n]的 weight 值；
  3. 进行以下n-1次合并，依次产生n-1个结点HT[i]，i = n + 1…2n-1：
    • 在HT[1…i-1]中选两个未被选过(从parent ==0 的结点中选)的weight最小的两个结点 HT[S1] 和 HT[S2]，s1、s2为两个最小结点下标；
    • 修改 HT[s1] 和 HT[s2] 的parent值：HT[s1].parent = i; HT[s2] .parent = i;
    • 修改新产生的HT[i]：
HT[i].weight = HT[s1].weight + HT[s2].weight;
HTli].Ich = s1; 
HT[i].rch = s2;

void CreatHuffmanTree(HuffmanTree& HT, int n) { //构造哈夫曼树--哈夫曼算法if (n <= 1) return;int m = 2 * n - 1; // 数组共2n-1个元素HT = new HTNode[m + 1]; // 动态分配内存，0号单元未用，HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i = 1; i <= m; ++i) {HT[i].lch = HT[i].rch = HT[i].parent = 0;}// 输入前n个元素的weight值cout << "请输入" << n << "个字符的频率：" << endl;for (int i = 1; i <= n; ++i) {cin >> HT[i].weight;}// 构建哈夫曼树for (int i = n + 1; i <= m; i++) {int s1, s2;Select(HT, i - 1, 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;}
}
（3）总代码：
权值为整数：
#include <iostream>
#include <limits.h>using namespace std;// 定义哈夫曼树节点结构
typedef struct {int weight;int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 选择两个双亲域为0且权值最小的结点
void Select(const HTNode* HT, int i, int& s1, int& s2) {s1 = s2 = -1;int min1 = INT_MAX, min2 = INT_MAX;for (int j = 1; j <= i; ++j) {if (HT[j].parent == 0 && HT[j].weight < min1) {min2 = min1;s2 = s1;min1 = HT[j].weight;s1 = j;}else if (HT[j].parent == 0 && HT[j].weight < min2) {min2 = HT[j].weight;s2 = j;}}
}void CreatHuffmanTree(HuffmanTree& HT, int n) { //构造哈夫曼树--哈夫曼算法if (n <= 1) return;int m = 2 * n - 1; // 数组共2n-1个元素HT = new HTNode[m + 1]; // 动态分配内存，0号单元未用，HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i = 1; i <= m; ++i) {HT[i].lch = HT[i].rch = HT[i].parent = 0;}// 输入前n个元素的weight值cout << "请输入" << n << "个字符的频率：" << endl;for (int i = 1; i <= n; ++i) {cin >> HT[i].weight;}// 构建哈夫曼树for (int i = n + 1; i <= m; i++) {int s1, s2;Select(HT, i - 1, 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;}
}int main() {int n;cout << "请输入叶子节点的数量：";cin >> n;HuffmanTree HT;CreatHuffmanTree(HT, n);// 打印哈夫曼树（示例）cout << "哈夫曼树构造完成，打印结果如下：" << endl;for (int i = 1; i < 2 * n; ++i) {cout << "Node " << i << ": Weight=" << HT[i].weight<< ", Parent=" << HT[i].parent<< ", Left Child=" << HT[i].lch<< ", Right Child=" << HT[i].rch << endl;}delete[] HT; // 释放动态分配的内存return 0;
}
权值为浮点数
#include <iostream>
#include <limits.h> // 如果不再使用 INT_MAX，可以不需要这个头文件using namespace std;// 定义哈夫曼树节点结构，将 weight 改为 double 类型
typedef struct {double weight;  // 权值改为 double 类型int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 选择两个双亲域为0且权值最小的结点
void Select(const HTNode* HT, int i, int& s1, int& s2) {s1 = s2 = -1;double min1 = DBL_MAX, min2 = DBL_MAX; // 使用 DBL_MAX 作为最大值初始化for (int j = 1; j <= i; ++j) {if (HT[j].parent == 0 && HT[j].weight < min1) {min2 = min1;s2 = s1;min1 = HT[j].weight;s1 = j;}else if (HT[j].parent == 0 && HT[j].weight < min2) {min2 = HT[j].weight;s2 = j;}}
}void CreatHuffmanTree(HuffmanTree& HT, int n) { //构造哈夫曼树--哈夫曼算法if (n <= 1) return;int m = 2 * n - 1; // 数组共2n-1个元素HT = new HTNode[m + 1]; // 动态分配内存，0号单元未用，HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i = 1; i <= m; ++i) {HT[i].lch = HT[i].rch = HT[i].parent = 0;HT[i].weight = 0.0; // 初始化 weight 为 0.0}// 输入前n个元素的weight值cout << "请输入" << n << "个字符的小数频率：" << endl;for (int i = 1; i <= n; ++i) {cin >> HT[i].weight;}// 构建哈夫曼树for (int i = n + 1; i <= m; i++) {int s1, s2;Select(HT, i - 1, 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;}
}int main() {int n;cout << "请输入叶子节点的数量：";cin >> n;HuffmanTree HT;CreatHuffmanTree(HT, n);// 打印哈夫曼树（示例）cout << "哈夫曼树构造完成，打印结果如下：" << endl;for (int i = 1; i <= 2 * n - 1; ++i) { // 注意这里应该是 2*n-1 而不是 2*ncout << "Node " << i << ": Weight=" << HT[i].weight<< ", Parent=" << HT[i].parent<< ", Left Child=" << HT[i].lch<< ", Right Child=" << HT[i].rch << endl;}delete[] HT; // 释放动态分配的内存return 0;
}
（4）运行结果：

在这里插入图片描述

3）哈夫曼编码

在远程通讯中，要将待传字符转换成由二进制的字符串：
在这里插入图片描述

若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。
在这里插入图片描述

问题1 ：什么样的前缀码能使得电文总长最短？

——哈夫曼编码

方法:

1、统计字符集中每个字符在电文中出现的平均概率（概率越大要求编码越短）。

2、利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树。 则概率越大的结点，路径越短。

3、在哈夫曼树的每个分支上标上0或1：

  • 结点的左分支标0，右分支桥 1。
  • 把从根到每个吐子的路径上的标号连接起来，作为该叶子代表的字符的编码。

在这里插入图片描述

问题2 ：为什么哈夫曼编码能够保证是前缀编码?

因为没有一片树叶是另一片树叶的祖先，所以每个叶结点的编码就不可能是其它叶结点编码的前缀。

问题 3 ：为什么哈夫曼编码能够保证字符编码总长最短?

因为哈夫曼树的带权路径长度最短，故字符编码的总长最短。

  • 性质1 哈夫曼编码是前缀码
  • 性质2 哈夫曼编码是最优前缀码
算法实现：
// 从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
void CreatHuffmanCode(const HuffmanTree& HT, HuffmanCode& HC, int n) {HC = new char*[n + 1]; // 分配n个字符编码的头指针数组char* cd = new char[n]; // 分配临时存放编码的动态数组空间cd[n - 1] = '\0'; // 编码结束符for (int i = 1; i <= n; ++i) {int start = n - 1;int c = i;int f = HT[i].parent;// 从叶子结点开始向上回溯，直到根结点while (f != 0) {--start;if (HT[f].lch == c)cd[start] = '0'; // 结点c是f的左孩子，则生成代码0elsecd[start] = '1'; // 结点c是f的右孩子，则生成代码1c = f;f = HT[f].parent;}// 计算编码长度并分配适当的空间int codeLength = n - start;HC[i] = new char[codeLength];strncpy(HC[i], &cd[start], codeLength);HC[i][codeLength - 1] = '\0'; // 确保字符串以空字符终止}delete[] cd; // 释放临时空间
}

strncpy(HC[i], &cd[start], codeLength);语句在C++中确实可以用于复制字符数组，但它有一些潜在的问题和局限性。特别是当你使用strncpy时，如果目标缓冲区没有足够的空间来包含源字符串加上终止空字符（\0），它不会自动添加终止空字符，这可能会导致后续操作出现问题。

此外，在现代C++中，更推荐使用std::string来处理字符串，因为它们更安全、更方便，并且可以避免手动管理内存的复杂性和风险。

// 从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
void CreatHuffmanCode(const HuffmanTree& HT, HuffmanCode& HC, int n) {HC.resize(n + 1); // 分配n个字符编码的空间for (int i = 1; i <= n; ++i) {string code = "";int c = i;int f = HT[i].parent;// 从叶子结点开始向上回溯，直到根结点while (f != 0) {if (HT[f].lch == c)code = '0' + code; // 结点c是f的左孩子，则生成代码0elsecode = '1' + code; // 结点c是f的右孩子，则生成代码1c = f;f = HT[f].parent;}HC[i] = code;}
}
总代码实现：

在这里插入图片描述

#include <iostream>
#include <cstring> // 用于 strcpy 和 strlen
#include <limits>  // 用于 std::numeric_limitsusing namespace std;// 定义哈夫曼树节点结构
typedef struct HTNode {double weight; // 权重改为 double 类型int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 定义哈夫曼编码结构
typedef char** HuffmanCode;// 选择两个双亲域为0且权值最小的结点
void Select(const HTNode* HT, int i, int& s1, int& s2) {s1 = s2 = -1;double min1 = numeric_limits<double>::max(), min2 = numeric_limits<double>::max();for (int j = 1; j <= i; ++j) {if (HT[j].parent == 0 && HT[j].weight < min1) {min2 = min1;s2 = s1;min1 = HT[j].weight;s1 = j;} else if (HT[j].parent == 0 && HT[j].weight < min2) {min2 = HT[j].weight;s2 = j;}}
}// 构造哈夫曼树--哈夫曼算法
void CreatHuffmanTree(HuffmanTree &HT, int n) {if (n <= 1) return;int m = 2 * n - 1; // 数组共2n-1个元素HT = new HTNode[m + 1]; // 动态分配内存，0号单元未用，HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i = 1; i <= m; ++i) {HT[i].lch = HT[i].rch = HT[i].parent = 0;HT[i].weight = 0.0; // 初始化权重为 0.0}// 输入前n个元素的weight值cout << "请输入" << n << "个字符的频率（浮点数）：" << endl;for (int i = 1; i <= n; ++i) {cin >> HT[i].weight;}// 构建哈夫曼树for (int i = n + 1; i <= m; i++) {int s1, s2;Select(HT, i - 1, 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;}
}// 从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n) {HC = new char*[n + 1]; // 分配n个字符编码的头指针数组char* cd = new char[n]; // 分配临时存放编码的动态数组空间cd[n - 1] = '\0'; // 编码结束符for (int i = 1; i <= n; ++i) {int start = n - 1;int c = i;int f = HT[i].parent;// 从叶子结点开始向上回溯，直到根结点while (f != 0) {--start;if (HT[f].lch == c)cd[start] = '0'; // 结点c是f的左孩子，则生成代码0elsecd[start] = '1'; // 结点c是f的右孩子，则生成代码1c = f;f = HT[f].parent;}// 计算编码长度并分配适当的空间int codeLength = n - start;HC[i] = new char[codeLength];strncpy(HC[i], &cd[start], codeLength);HC[i][codeLength - 1] = '\0'; // 确保字符串以空字符终止}delete[] cd; // 释放临时空间
}// 测试函数
int main() {int n;cout << "请输入叶子节点的数量：";cin >> n;HuffmanTree HT;CreatHuffmanTree(HT, n);HuffmanCode HC;CreatHuffmanCode(HT, HC, n);// 打印哈夫曼编码cout << "哈夫曼编码如下：" << endl;for (int i = 1; i <= n; ++i) {cout << "Character " << i << ": " << HC[i] << endl;}// 清理资源for (int i = 1; i <= n; ++i) {delete[] HC[i];}delete[] HC;delete[] HT;return 0;
}

改进后的代码：

#include <iostream>
#include <vector>
#include <string>
#include <limits>using namespace std;// 定义哈夫曼树节点结构
typedef struct HTNode {double weight; // 权重改为 double 类型int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 选择两个双亲域为0且权值最小的结点
void Select(const vector<HTNode>& HT, int i, int& s1, int& s2) {s1 = s2 = -1;double min1 = numeric_limits<double>::max(), min2 = numeric_limits<double>::max();for (int j = 1; j <= i; ++j) {if (HT[j].parent == 0 && HT[j].weight < min1) {min2 = min1;s2 = s1;min1 = HT[j].weight;s1 = j;} else if (HT[j].parent == 0 && HT[j].weight < min2) {min2 = HT[j].weight;s2 = j;}}
}// 构造哈夫曼树--哈夫曼算法
void CreatHuffmanTree(vector<HTNode>& HT, int n) {if (n <= 1) return;int m = 2 * n - 1; // 数组共2n-1个元素// 初始化2n-1个元素的lch、rch、parent为0，权重为0.0HT.resize(m + 1);for (int i = 1; i <= m; ++i) {HT[i] = {0.0, 0, 0, 0};}// 输入前n个元素的weight值cout << "请输入" << n << "个字符的频率（浮点数）：" << endl;for (int i = 1; i <= n; ++i) {cin >> HT[i].weight;}// 构建哈夫曼树for (int i = n + 1; i <= m; i++) {int s1, s2;Select(HT, i - 1, 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;}
}// 从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
void CreatHuffmanCode(const vector<HTNode>& HT, vector<string>& HC, int n) {HC.resize(n + 1); // 分配n个字符编码的空间for (int i = 1; i <= n; ++i) {string code = "";int c = i;int f = HT[i].parent;// 从叶子结点开始向上回溯，直到根结点while (f != 0) {if (HT[f].lch == c)code = '0' + code; // 结点c是f的左孩子，则生成代码0elsecode = '1' + code; // 结点c是f的右孩子，则生成代码1c = f;f = HT[f].parent;}HC[i] = code;}
}// 测试函数
int main() {int n;cout << "请输入叶子节点的数量：";cin >> n;vector<HTNode> HT;CreatHuffmanTree(HT, n);vector<string> HC;CreatHuffmanCode(HT, HC, n);// 打印哈夫曼编码cout << "哈夫曼编码如下：" << endl;for (int i = 1; i <= n; ++i) {cout << "Character " << i << ": " << HC[i] << endl;}return 0;
}

改进后：

#include <iostream>
#include <cstring> // 用于 strcpy 和 strlen
#include <limits>  // 用于 std::numeric_limitsusing namespace std;// 定义哈夫曼树节点结构
typedef struct HTNode {double weight; // 权重改为 double 类型int parent, lch, rch;
} HTNode;typedef HTNode* HuffmanTree;// 定义哈夫曼编码结构
typedef char** HuffmanCode;// 选择两个双亲域为0且权值最小的结点
void Select(const HTNode* HT, int i, int& s1, int& s2) {s1 = s2 = -1;double min1 = numeric_limits<double>::max(), min2 = numeric_limits<double>::max();for (int j = 1; j <= i; ++j) {if (HT[j].parent == 0 && HT[j].weight < min1) {min2 = min1;s2 = s1;min1 = HT[j].weight;s1 = j;} else if (HT[j].parent == 0 && HT[j].weight < min2) {min2 = HT[j].weight;s2 = j;}}
}// 构造哈夫曼树--哈夫曼算法
void CreatHuffmanTree(HuffmanTree &HT, int n) {if (n <= 1) return;int m = 2 * n - 1; // 数组共2n-1个元素HT = new HTNode[m + 1]; // 动态分配内存，0号单元未用，HT[m]表示根结点// 初始化2n-1个元素的lch、rch、parent为0for (int i = 1; i <= m; ++i) {HT[i].lch = HT[i].rch = HT[i].parent = 0;HT[i].weight = 0.0; // 初始化权重为 0.0}// 输入前n个元素的weight值cout << "请输入" << n << "个字符的频率）：" << endl;for (int i = 1; i <= n; ++i) {cin >> HT[i].weight;}// 构建哈夫曼树for (int i = n + 1; i <= m; i++) {int s1, s2;Select(HT, i - 1, 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;}
}// 从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n) {HC = new char*[n + 1]; // 分配n个字符编码的头指针数组for (int i = 1; i <= n; ++i) {string code = ""; // 使用string来构建编码int c = i;int f = HT[i].parent;// 从叶子结点开始向上回溯，直到根结点while (f != 0) {if (HT[f].lch == c)code = '0' + code; // 结点c是f的左孩子，则生成代码0elsecode = '1' + code; // 结点c是f的右孩子，则生成代码1c = f;f = HT[f].parent;}// 将string转换为C风格字符串并分配适当的空间HC[i] = new char[code.length() + 1];strcpy(HC[i], code.c_str());}
}// 测试函数
int main() {int n;cout << "请输入叶子节点的数量：";cin >> n;if (n <= 0) {cerr << "叶子节点数量必须大于0." << endl;return 1;}HuffmanTree HT;CreatHuffmanTree(HT, n);HuffmanCode HC;CreatHuffmanCode(HT, HC, n);// 打印哈夫曼编码cout << "哈夫曼编码如下：" << endl;for (int i = 1; i <= n; ++i) {cout << "Character " << i << ": " << HC[i] << endl;}// 清理资源for (int i = 1; i <= n; ++i) {delete[] HC[i];}delete[] HC;delete[] HT;return 0;
}
运行结果：

在这里插入图片描述

http://www.dt0577.cn/news/52344.html

相关文章：

  • 用discuz做行业网站网站关键词查询网址
  • 带网站的电话销售新人怎么找客户
  • 一流的邯郸网站建设做百度推广怎么做才能有电话
  • 南京做网站建设的公司排名公司网页制作模板
  • 门户网站优化报价简述网络营销的特点
  • 怎样免费建立网站百度关键词seo外包
  • 兼职做一篇微信的网站最新做做网站
  • 宁波正规网站建设方式郑州搜索引擎优化
  • 做服装外贸的网站设计网络推广优化方案
  • 网站服务器租用你的知识宝库今日头条新闻发布
  • 网站建设对于企业的必要性长沙市网站制作
  • 企业网站制作是什么seo网站内容优化有哪些
  • 计算机网络技术就业方向及前景东莞网络推广优化排名
  • 网站的主机选择网络营销推广平台
  • 网站设计联系电话国外网站推广公司
  • 电脑做科目一网站优化是什么意思
  • wordpress更换ssl证书成都seo优化公司
  • 个人网站有数量限制百度手机网页版入口
  • 温州网站建设免费服务株洲seo优化
  • 网站建设类公司排名百度关键词排名靠前
  • 服装商务网站建设策划书泰安seo排名
  • 作网站推广策略有哪些方法
  • 网站建设维护与网页设计济南市最新消息
  • 如何做网站 百度微信运营方案
  • 陕西省建设监理协会网站成绩查询阿里云模板建站
  • 淘宝网站建设百度官网app
  • 大兴模版网站建设公司长春关键词优化平台
  • 什么网站可以做pie chart怎么登录百度app
  • 政府网站建设服务公众号怎么推广和引流
  • windows卸载wordpress站长工具seo推广 站长工具查询