个人博客网站制作教程,wordpress必须安装php吗,创建网站的四个步骤是,国外网站怎么建设文章目录 一、最优装载问题1.1 问题表述1.2 代码编写 二、哈夫曼编码2.1 哈夫曼编码概述2.2 前缀码2.3 问题描述2.4 代码思路2.5 代码编写 一、最优装载问题
1.1 问题表述 1. 有一批集装箱要装上一艘载重量为 c c c 的轮船#xff0c;已知集装箱 i ( 1 ≤ i ≤ n ) i(1≤i≤… 文章目录 一、最优装载问题1.1 问题表述1.2 代码编写 二、哈夫曼编码2.1 哈夫曼编码概述2.2 前缀码2.3 问题描述2.4 代码思路2.5 代码编写 一、最优装载问题
1.1 问题表述 1. 有一批集装箱要装上一艘载重量为 c c c 的轮船已知集装箱 i ( 1 ≤ i ≤ n ) i(1≤i≤n) i(1≤i≤n) 的重量为 w i w_i wi。最优载问题要求在装载体积不受限制的情况下将尽可能多的集装箱装上轮船。 2. 贪心选择策略重量最轻者优先装载。 3. 算法思路将装船过程划分为多步选择每步装 1 1 1 个货箱每次从剩下的货箱中选择重量最轻的货箱。如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。
1.2 代码编写 算法时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) #includealgorithm
#includeiostream
using namespace std;int main(){int n; //定义货箱个数int c; //定义船的最大承载量cout输入货箱个数以及船的最大承载量endl;cinnc;cout输入每件货物的重量endl;int w[n]; //用数组填装货箱的重量for(int i0;in;i){cinw[i];}sort(w,wn); //快排将货箱的重量由小到大进行排序int temp0; //中间值int count0; //计数器for(int i0;in;i){temp temp w[i];if(tempc){count;}else{break;}}cout能装入货箱的最大数量为countendl;return 0;
}二、哈夫曼编码
2.1 哈夫曼编码概述 1. 哈夫曼编码是在电讯通信中的应用之一广泛地用于数据文件压缩的十分有效的编码方法其压缩率通常在20%90%之间。在电讯通信业务中通常用二进制编码来表示字母或其他字符并用这样的编码来表示字符序列。 2. 例如如果需传送的电文为 ‘ A B A C C D A ’ ‘ABACCDA’ ‘ABACCDA’它只用到四种字符用两位二进制编码便可分辨。假设 A , B , C , D A, B, C, D A,B,C,D 的编码分别为 00 , 01 , 10 , 11 00, 01,10, 11 00,01,10,11则上述电文便为 ‘ 00010010101100 ’ ‘00010010101100’ ‘00010010101100’共 14 位译码员按两位进行分组译码便可恢复原来的电文。
2.2 前缀码 1. 前缀码定义对每一个字符规定一个 0 , 1 0,1 0,1 串作为其代码并要求任一字符的代码都不是其它字符代码的前缀这种编码称为前缀码。
abcdef编码方式1010110011111011100编码方式20100011011 很容易发现当我们在用编码方式 2 2 2 时解码会出现问题例如 00110 00110 00110 既可以解码成 a a b b a aabba aabba也可以解码成 c f a cfa cfa解码结果不唯一编码方式不可行。 而用前缀码即编码的任意前缀不是其他编码则解码结果唯一编码方式可行。
2.3 问题描述 1. 如果要求得到最优的编码方式那不同的前缀码如何比较它们的优劣呢我们可以通过比较编码后二进制串的总长总长越短说明这种编码方式越优。而编码后二进制的总长依赖于待编码字符的频数。假设我们给出的带编码字符及其频数和两种不同的前缀码如下表所示。
abcdef频数(千次)4513121695前缀码1010110011111011100前缀码2110011011111001010 通过计算可知使用前缀码 1 1 1编码后二进制串的总长是 224000 224000 224000使用前缀码 2 2 2编码后二进制串的总长是 348000 348000 348000显然前缀码 1 1 1要优于前缀码 2 2 2。 2. 贪心策略出现频率较高的字符的编码较短出现频率较低的字符的编码较长。使用二叉树对其进行编码和解码。
2.4 代码思路 1. 给定编码字符集 C C C 及 C C C 中的任一字符 c c c 的出现频率 f ( c ) f(c) f(c)。 C C C 的一个前缀码编码方案对应一棵二叉树 T T T。字符 c c c 在树 T T T 中的深度记为 d T ( c ) d_T(c) dT(c)。定义该编码方式的平均码长为 2. 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T T T。算法以 n n n 个叶结点开始执行 n − 1 n-1 n−1 次合并运算后产生最终所要求的树 T T T。在哈夫曼树中编码字符集中每个字符 c c c的频率是 f ( c ) f(c) f(c)。以 f f f 为键值的优先队列 Q Q Q 在用做贪心选择时有效地确定当前要合并的两棵具有最小频率的树。一旦两棵具有最小频率的树合并后产生一棵新的树其频率和为合并的两棵树的频率之和并将新树加入 Q Q Q。
2.5 代码编写 算法时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) #includeiostream
using namespace std;#define MaxNode 200
#define MaxBit 100//节点,一般遵循左0右1
typedef struct
{double weight; //权重int parent; //父节点int lchild; //左孩子节点int rchild; //右孩子节点char value; //节点代表的字符
}hufnode;typedef struct
{int start; //开始指针,记录每个字母编码在数组里开始的位置int bit[10]; //存放赫夫曼编码
}hufbit;hufnode hujd[MaxNode];
hufbit hb[MaxBit];//初始化节点parent,lchild,rchild-1,weight0
void initNode()
{for (int i 0; i MaxNode; i){hujd[i].lchild -1;hujd[i].parent -1;hujd[i].rchild -1;hujd[i].weight 0;}
}//建立哈弗曼树
void creathuf(int n)
{int i;cout 请输入每个节点的字符和权值 endl;for (i 0; i n; i){cin hujd[i].value hujd[i].weight;}//定义两个变量m1和m2用来存储最小的两个未处理的权值以及两个变量x1和x2用来存储对应的最小权值的节点索引。double m1, m2;int x1, x2;for (int i 0; i n - 1; i){m1 m2 1000;x1 x2 0;for (int j 0; j n i; j){//找最小权值结点 if (hujd[j].weight m1 hujd[j].parent -1){m2 m1;x2 x1;m1 hujd[j].weight;x1 j;}//找第二最小权值结点 else if (hujd[j].weight m2 hujd[j].parent -1){m2 hujd[j].weight;x2 j;}}//创建一个新的父节点其左孩子为x1右孩子为x2 hujd[n i].weight m1 m2;hujd[n i].lchild x1;hujd[n i].rchild x2;hujd[x1].parent n i;hujd[x2].parent n i;}
}//编码
void tshuff(int n)
{//p用于保存当前节点的父节点的索引c用于保存当前节点的索引。int p, c;for (int i 0; i n; i){p hujd[i].parent; //获取当前节点的父节点索引并赋值给pc i; //获取当前节点的索引并赋值给chb[i].start n - 1; //将当前节点的起始位设置为n-1这可能意味着我们是从最右边开始编码的while (p ! -1) //当前节点不是根节点时进行循环{//如果当前节点是父节点的左孩子我们将起始位处的二进制位设为0并将起始位右移一位向树的左边移动if (hujd[p].lchild c){hb[i].bit[hb[i].start] 0;hb[i].start--;}//如果当前节点是父节点的右孩子我们将起始位处的二进制位设为1并将起始位右移一位向树的左边移动if (hujd[p].rchild c){hb[i].bit[hb[i].start] 1;hb[i].start--;}//将当前节点的索引赋值给p将父节点的索引赋值给c然后开始下一轮循环。//这个过程一直持续到p等于-1为止也就是说当我们到达树的根节点时循环就会结束。c p;p hujd[p].parent;}}
}void output(int n)
{for (int i 0; i n; i){cout hujd[i].value :;for (int j hb[i].start1; j n; j){cout hb[i].bit[j];}cout endl;}
}
int main()
{int n;cout 请输入有几个字符 endl;cin n;initNode();creathuf(n);tshuff(n);cout 编码方式为 endl; output(n);return 0;
}
