用C++实现Huffman文件编码和解码（2 总结）
这个是代码是昨天写完的，一开始的时候还出了点小bug，这个bug在晚上去吃饭的路上想明白的，回来更改之后运行立刻完成最后一步，大获成功。
简单说下huffman编码和文件压缩主要的技术。
Huffman编码，解码：
I 创建Huffman树
II 根据Huffman树实现编码，并将编码结果和要编码的数据建立映射关系。III Huffman解码，也就是根据获取的Huffman码来逆向获取解码信息，而且你从解压文件中一次性获取的数据是一个很长的字符串，没有预处理好的成段字符串式Huffman码。1
I 首先，如何创建Huffman树？
在这个我在前天的那篇文章中简单的提了一下，现在好好说一下。如果你不知道什么是Huffman树，请google之~
对于获取到的文件，首先要做的就是，建立一个长度为256的int数组，全部置零，然后以字节流的形式读取文件，并对字节流中的字节出现次数进行统计，方法就是以字节数值为数组偏移地址，对应的数组元素进行+1操作。另外这里需要提一下的就是，用于存储文件字节流的缓冲区最好是unsigned char类型，因为这样能直接使用，如果是char的，在转化为int类型的时候，一旦数值大于127，因为补码问题，你就直接乘上了通往未知数值的高铁~
完成统计之后，将这个数组中出现次数不为0的元素添加对应大小的二叉树节点数组中，然后以出现次数为Key值，进行排序。
在排序完成之后，就能开始构建Huffman树了。操作如下：
1 如果数组中元素个数不为1，将前两个元素构造为一个临时节点的子树，此时临时节点的Key值为两个元素Key值之和，然后删除数组中的第一个元素（从
数组中删除），再将临时节点赋值给当前数组的第一个元素。
（其实就是将前两个元素添加到一个临时节点的左右根节点，然后在原数组中删除这两个元素，接着再将这个临时节点插入到数组头部，充当新的节点。上面的那段描述我觉得说的不是很清楚，但是那个是我在代码中发现的一个可以优化的地方，减少了一个元素的删除操作）
2 此时数组依据key值的排序很有可能已经不再有序，而又因为仅有一个乱序元素，所以专门设计了一个函数，一次完成排序，效率，应该是最高的了。重复1
这样当数组中只有1个元素的时候，就是Huffman树的根节点了。
这样，Huffman树的构造就完成了。我上面说的可能不是很清楚，你看了之后
可能会有疑问，所以我在这贴下部分代码，你可以看一下，就是这么简单，而且很巧妙。
Huffman树节点，一开始就是一个Struct，但是因为涉及到了STL，所以添
加了方法
1struct HaffmanStruct
2 {
3//a small structure
4 HaffmanStruct():val(0),ncounts(0),lNext(NULL),rNext(NULL){} 5bool operator < (HaffmanStruct &);
6bool operator > (HaffmanStruct &);
7void Reset();
8 unsigned char val;
9 unsigned int ncounts;
10char HuffmanCode[254];
11//used for tree
12 HaffmanStruct * lNext;
13 HaffmanStruct * rNext;
14 };
给他一个数组，他给你一颗Huffman树
1void HuffManEncode(vector
2 {
3 HaffmanStruct ValidStruct;//temporary struct
4//Analysis
5while(vecValidNumberArray.size() != 1)
6 {
7 ValidStruct.Reset();
8 ValidStruct.ncounts = vecValidNumberArray[0].ncounts + vecValidNumberArray[1].ncounts;
9 ValidStruct.lNext = new HaffmanStruct;
10 *ValidStruct.lNext = vecValidNumberArray[0];
11 ValidStruct.rNext = new HaffmanStruct;
12 *ValidStruct.rNext = vecValidNumberArray[1];
13 vecValidNumberArray.erase(vecValidNumberArray.begin());
14 vecValidNumberArray[0] = ValidStruct;
15 SingleSort(&vecValidNumberArray[0], vecValidNumberArray.size(), 0);
16 }
17 }
以上就是Huffman树构造的全部过程。
II 根据Huffman树获取Huffman编码
对树最有效的访问方式就是遍历，而遍历有两种方式：深度优先遍历和广度优先遍历。不过学过Huffman编码的人都知道，Huffman的编码，必须使用深度优先遍历，你懂得~
我在此默认的模式是，左树为0，右树为1.而这个遍历函数需要使用一个编码缓冲区和输出目标，以及深度探测。于是乎，一个参数好多的递归函数新鲜出炉了，昨天才被我正式造出来。
1 template
2void ErgodicTree(T & Root, char* szStr, int nDeep, string pStrArray[]) 3 {
4if(Root.lNext == NULL && Root.rNext == NULL)
5 pStrArray[Root.val] = szStr;
6 szStr[nDeep] = '0';
7if(Root.lNext != NULL)
8 ErgodicTree(*Root.lNext, szStr, nDeep + 1, pStrArray);
9 szStr[nDeep] = '1';
10if(Root.rNext != NULL)
11 ErgodicTree(*Root.rNext, szStr, nDeep + 1, pStrArray);
12 szStr[nDeep] = 0;
13 }
需要注意的是，编码和解码的递归函数是不一样的，在这专门提一下，因为编码是一次性遍历完成全部的节点，而解码是每次只遍历到叶子节点。
可以看到，每次向下传递参数的时候，左树就置'0'，右树就置'1'，返回的时候必须清零。这样下一级函数会获取的结果，并且根据Deep的值对应置位，上级函数函数的乞讨递归也不会受到影响。代码写的很简单，但是其实很细致。
一旦访问到了叶子节点，就直接输出，这里写的也很巧妙，也就是在这里，获取到了Huffman编码，输出到对应的string数组中。
这样，就完成了Huffman编码。
III Huffman解码
用Huffman解码之前，你获取到的是一个很长的，内容是'0'和'1'的字符串。在我的代码中，这个字符串的长度是1024.
其实Huffman的解码实现起来也很简单，但是，存在细节性问题。
比如：从递归函数中获取返回值、下次解码的偏移地址、字符串访问已经到头了，但是解码失败（你想想这个问题出现的圆心），此时字符串中还剩下几个未解码的字符。
这些都是相当细节性的问题，另外文件中一般有n多个1024长度的以上的字节数，如何承上启下也是问题。
这一切，都在下面这段代码中解决：
1char Buffer[128];
2char DecodeBuffer[1056];//增加了八个缓冲字节
3 DWORD dwReadByte;
4 DWORD dwFlag = 1;
5 DWORD dwDeep = 0;
6char tmpchar;
7int EffectiveBufferSize = 0;
8int nLeftNumberInBuffer = 0;
9char szSmallBuffer[2] = {0};
10
11//创建解压文件
12 HANDLE hDeCompressionFile =
QuickCreateFile("C:\\DCRecord.txt");
13 assert(hDeCompressionFile != INVALID_HANDLE_VALUE);
14
15while(1)
16 {
17int i = 0;
18 dwReadByte = ReadHuffCodeFromFile(hHuffFile, Buffer, 128); 19if(dwReadByte == 0)
20break;
21 EffectiveBufferSize = ReadBitToBuffer(Buffer,
(int)dwReadByte, DecodeBuffer + nLeftNumberInBuffer, 1024);
22 EffectiveBufferSize += nLeftNumberInBuffer;
23//TextFileFunction(DecodeBuffer, 1024);
24for(i = 0;(i + dwDeep) < EffectiveBufferSize;i += dwDeep)
25 {
26 dwDeep = 0;
27 tmpchar = DecodeHuffman(&vecHuffmanArray[0], DecodeBuffer + i, EffectiveBufferSize - i, dwDeep, dwFlag);
28if(dwFlag == 1)
29 {
30 szSmallBuffer[0] = tmpchar;
31 WriteBufferIntoFileNormally(hDeCompressionFile, szSmallBuffer, 1);
32 }
33else
34 {
35 dwFlag = 1;
36break;
37 }
38 }
39 nLeftNumberInBuffer = EffectiveBufferSize - i;
40 memcpy(DecodeBuffer, DecodeBuffer + i, nLeftNumberInBuffer);
41 }
这段代码中对于这种问题完成的很好，我上面说的在晚上去吃饭的路上就是想明白了实现承上启下那个问题的。
大致步骤如下：
要注意到参数Deep是引用值，是会修改原值的。这个值同时是递归时使用的字符串偏移地址，这个地址所在的值，决定了下一级是向左子树走还是向右走的方向。也就是根据字符串数据来访问Huffman树，一旦访问到叶子节点，就表明
此次的解码完成了，返回这个对应值。虽然是递归调用，但是每一级递归调用只有一条通路选择，所以返回值具有可传递性。
完成一段字符串的解码之后，此时的Deep参数就已经是访问过的字符串个数了，就能用于下一次解码的地址偏移，能够用于循环代码操作。
另外还有个问题就是，我从获取的huffman解码整条字符串，都是8的倍数（因为下级函数时将一个字节的8位数据按位解读，写入字符串），所以到最后的一
段字符串解码失败很正常，因为这段字符串码不完全。此时就需要将这段字符码移到首部，然后与下一次读出来的字符码进行拼接。你可以注意到，我的代码中，
一般都是在for循环中直接声明int i，但是在这里却是在while循环外声明
的i，就是为了实现拼接，使得解码操作能够传递下去。如果一次性创建一个很
大很大的缓冲区把整个文件都读进来，我只能说：图样图森破。
具体的操作就看代码吧，我写的时候是有点小纠结的，但是写完了一看，呵呵，就这么简单。
这样，解码也就完成了。
最后说一下文件操作。
首先写文件有一块很重要的就是，需要写一个文件头。而且是一个变长的文件头。文件头主要内容：（不涉及文件夹）
1 文件原名，以及后缀
2 需要编码的数据的数据个数
3 存在的字符和该字符出现的次数
上面的2 3其实就是把构造Huffman树最基础的数组存入文件中，这样解压文件就能根据文件头来构造Huffman树，从而实现解码了。为此我专门写了一个负责文件头的函数。而且这里有个注意事项就是，写文件的时候，要把排好序的数组写进去，这样解压文件就不需要再次进行排序了，能省则省嘛。
查看文件头数据：
这个是我以前水平还很烂很烂的时候写的一个查看程序，最可笑的就是，我这缓冲区用的是一个CString，现在看看，真是荒唐可笑。
不过现在对于小文件，还是能看一看的。你能看到，前几个都是1的，就是int 数据，只有出现1次的字符。后面出现的次数逐渐增加。
再往下拉的话，就是各种乱码了，都是按字节解释起来乱七八糟的东西了。
其实编码解码的文件操作这块，我觉得应该算是计算机中，对最小数据单元的操作了，绝对没有比这更小的了。因为要做的是根据编码结果一位一位的将数据写到char变量中，而在读文件这块，也是整块的读内存，然后按位解析字节，获取到以字节为单位的解码数据。
这块我就贴这几个函数，用于从字节到位，和从位到字节的操作。这活，还真的是挺细致的。记得我昨天调代码的时候，还专门调试这几个函数，因为当时解码出来的是乱码，然后我对照写文件前的Huffman码，还真的找到了问题所在。Byte to Bit
1void SetByteBit(char * ByteAddr, int Val, int BitAddr)
2 {
3int TmpVal = -1;
4int tmpval = 1;
5 tmpval <<= BitAddr;
6if(Val == 0)
7 {
8 TmpVal ^= tmpval;
9 *ByteAddr &= TmpVal;
10 }
11else
12 {
13 *ByteAddr |= tmpval;
14 }
15 }
16/*
17将huffman码按位写入文件
18*/
19void WriteByteToFile(HANDLE hFile, const char * lpszHuffCode, int Mode)
20 {
21if(hFile == INVALID_HANDLE_VALUE)
22return;
23
24static int snBytePointer = 0;
25static int snBitPointer = 0;
26static char WriteBuffer[512];
27 DWORD wfCounter = 0;//写缓冲区指针
28int nLength = 0;
29if(lpszHuffCode != NULL)
30 nLength = strlen(lpszHuffCode);
31
32if(Mode == 1)
33 {
34 WriteFile(hFile, WriteBuffer, snBytePointer + !!snBitPointer, &wfCounter, NULL);
35 snBytePointer = 0;
36 snBitPointer = 0;
37 wfCounter = 0;
38return;
39 }
40
41for(int i = 0;i < nLength;\
42 ++snBitPointer >= 8?(snBytePointer ++,snBitPointer =
0):snBitPointer,i ++)
43 {
44if(snBytePointer > 511)
45 {
46 WriteFile(hFile, WriteBuffer, 512, &wfCounter, NULL);
47 snBytePointer = 0;
48 }
49 SetByteBit(&WriteBuffer[snBytePointer], lpszHuffCode[i] - '0',snBitPointer);
50 }
51 }
Bit to Byte
1/*
2ReadByteBit Function
32013 10 05
4*/
5
6void ReadBitFromByte(const char Byte, char * buf = NULL)
7 {
8if(buf == NULL)
9return;
10int nTmpVal = 1;
11int nAndResult;
12for(int i = 0;i < 8;++ i)
13 {
14 nTmpVal <<= i;
15 nAndResult = nTmpVal & Byte;
16 buf[i] = '0' + !!nAndResult;
17 nTmpVal = 1;//this is prrety important
18 }
19 }
20/*
21还是写中文注释吧
22这个函数是用于将从文件读出来的二进制信息取出来，并存放到字符串中。23返回值就是读出来的位数的长度
24*/
25
26int ReadBitToBuffer(const char * ReadBuf, int nByteNumber,char * OutputBuf, int nOBufLength)
27 {
28if(nOBufLength < nByteNumber * 8)
29return0;
30for(int i = 0;i < nByteNumber;i ++)
31 {
32 ReadBitFromByte(ReadBuf[i], OutputBuf + 8 * i);
33 }
34return nByteNumber * 8;
35 }
刚才看了看自己写的一部分代码，感觉，还真的感觉到了代码中有不少自己的努力和智慧。
代码就不全贴了，内容就这么多，都是最基础的操作。不过此番之后，我觉得，我已经有能力编写压缩文件程序了，至少数据压缩存储这一块，我有了最基础的技术。
目录 一、摘要 (3) 二、题目 (3) 三、实验目的 (3) 四、实验原理 (3) 五、需求分析 (4) 5.1实验要求 (4) 5.2实验内容 (4) 六、概要设计 (4) 6.1所实现的功能函数 (4) 6.2主函数 (5) 6.3 系统结构图 (6) 七、详细设计和编码 (6) 八、运行结果 (12) 九、总结 (15) 9.1调试分析 (15) 9.2 心得体会 (15) 参考文献 (16)
一、摘要 二、题目 哈夫曼树的编码与译码 三、实验目的 （1）熟悉对哈夫曼的应用以及构造方法，熟悉对树的构造方式的应用； （2）进一步掌握哈夫曼树的含义； （3）掌握哈夫曼树的结构特征，以及各种存储结构的特点以及使用范围； （4）熟练掌握哈夫曼树的建立和哈夫曼编码方法； （5）提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法； （6）掌握一种计算机语言，可以进行数据算法的设计。 四、实验原理 哈夫曼（Huffman）编码属于长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下： （1）初始化，根据富豪概率的大小按由大到小顺序对符号进行排序； （2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和； （3）重复第（2）步，直到形成一个符号为止（树），其概率最后等于1； （4）从编码树的根开始回溯到原始的符号，并将每一下分支赋值1，上分支赋值0； 译码的过程是分解电文中字符串，从根出发，按字符“0”或者“1”确定找做孩 子或右孩子，直至叶子节点，便求得该子串相应的字符。
哈夫曼编码译码系统 一、需求分析 1、程序的基本功能： ①构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符以及n个对应的权 值，建立哈夫曼树；利用已将建好的哈弗曼树求每个叶结点的哈夫曼编码，并保存。 ②编码：利用已构造的哈弗曼编码对“明文”文件中的正文进行编码，然后将结果存 入“密文”文件中。 ③译码：将“密文”文件中的0、1代码序列进行译码。 ④打印“密文”文件：将文件以紧凑格式显示在终端上，同时，将此字符形式的编码 保存。 ⑤打印哈夫曼树:将已在内存中的哈夫曼以凹入表形式显示在终端上。 2、输入输出要求： ①从键盘接收字符集大小n、以及n个字符和n个权值； ②构造哈夫曼树：将HFMTree数组中的各个位置的各个域都添上相关的值，并将结构 体数组存入文件HTree.txt中。 ③打印哈夫曼树：从HFMTree数组读取相关的结点信息，以凹入表方式将各个结点画 出来； ④构造哈夫曼编码：先从文件HTree.txt中读入相关的字符信息进行哈夫曼编码，将字 符与其对应的编码存入文件HNode.txt中； ⑤编码：利用已构造的哈夫曼树对文件进行编码，打印结果，并将结果存入新建文件 中； ⑥译码：将密文文件中的内容利用HNode.txt中建立的编码规则进行翻译，打印结果， 并将结果存入新建文件中。 3、测试数据： 输入叶子结点个数为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，且字符集与权值集合一一对应。 二、概要设计 1、抽象数据类型的定义： ①采用静态链表作为哈夫曼树的存储结构； ②求哈夫曼编码时使用一维数组HCode作为哈夫曼编码信息的存储。 2、主模块的流程及各子模块的主要功能： ①int main() { 主菜单； swich语句结构选择； return 0; } ②in_park() { 输入车牌号； 若停车场已满，停入便道中，否则停入停车场； } ③output()
信息论与编码理论习题 答案 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】
第二章 信息量和熵 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的信息速 率。 解：同步信息均相同，不含信息，因此 每个码字的信息量为 2?8log =2?3=6 bit 因此，信息速率为 6?1000=6000 bit/s 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。问各得到多少信息 量。 解：(1) 可能的组合为 {1，6},{2，5},{3，4},{4，3},{5，2},{6，1} )(a p =366=6 1 得到的信息量 =) (1 log a p =6log = bit (2) 可能的唯一，为 {6，6} )(b p =361 得到的信息量=) (1 log b p =36log = bit 经过充分洗牌后的一副扑克（52张），问： (a) 任何一种特定的排列所给出的信息量是多少？ (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？ 解：(a) )(a p =! 521 信息量=) (1 log a p =!52log = bit (b) ? ??????花色任选种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C = bit 随机掷3颗骰子，X 表示第一颗骰子的结果，Y 表示第一和第二颗骰子的点数之和， Z 表示3颗骰子的点数之和，试求)|(Y Z H 、)|(Y X H 、),|(Y X Z H 、 )|,(Y Z X H 、)|(X Z H 。
1 String 类的用法 public class SetStringValue { /** * @param args */ public static void main(String[] args) { String str1=new String("Java是当今最流行的编程语言之一");//截取数组 String str2="java是优秀的技术"; char[] szStr={'H','e','l','l','o',',','j','a','v','a'}; String str3=String.copyValueOf(szStr);//复制数组，所有数组。 String str4=String.copyValueOf(szStr,6,4);//所取数组，开始位置，所取个数 System.out.println(str1); System.out.println(str2); System.out.println(str3); System.out.println(str4); // TODO Auto-generated method stub } } 2 public class StringPool { /** * @param args */ public static void main(String[] args) { String str1="Good!"; String str2="Good!"; String str3=new String("Good!"); if(str1==str2)//判断地址是否相同 { System.out.println("str1=str2");//地址相同则输出相等
数据结构课程设计设计题目：哈夫曼树编码译码
目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) （1）其主要流程图如图1-1所示。 (3) （2）设计包含的几个方面 (4) 第四章详细设计 (4) （1）①哈夫曼树的存储结构描述为： (4) （2）哈弗曼编码 (5) （3）哈弗曼译码 (7) （4）主函数 (8) （5）显示部分源程序： (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录： (12)
在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。
《数据结构》课程设计上机实习报告 课设题目Huffman编码和解码 班级 学生姓名 学号 指导教师 时间2015.12-2015.1
一、设计目的 1.进一步熟悉C语言开发环境，熟悉用C语言完成一个应用程序的设计过程，掌握有关编辑、调试和整合程序的方法和技巧。 2.通过此设计，了解《数据结构》课程中霍夫曼编码的的有关内容，明确其操作，熟悉其设计，同时学习到有关位向量的内容，对文件掌握加深 二、设计内容 Huffman编码与解码 (必做)（Huffman编码、二叉树） [问题描述] 对一篇英文文章（大于2000个英文字符），统计各字符出现的次 数，实现Huffman编码，以及对编码结果的解码。 [基本要求] （1）输出每个字符出现的次数和编码，其中求最小权值要求用堆实 现。 （2）在Huffman编码后，要将编码表和英文文章编码结果保存到文 件中，编码结果必须是二进制形式，即0 1的信息用比特位表示，不 能用字符’0’和’1’表示。 （3）提供读编码文件生成原文件的功能。 三、数据结构说明 在该程序中我仅仅使用了两个结构体来完成编码，用位域来实现bite流存储：const int MAXSIZE=300;//定义一次分配的Huffman储存单词最大量为500 const int OVERFLOW = 0; const int ERROR = 0; const int LineCountNum=500; typedef struct WordCount {
char Word;//存放字符 int freq; int parent , lchild , rchild;//存放亲子节点位置 int place;//用来保存第一次堆排序后，建立霍夫曼表前的相对位置 char *HuffmanCode;//存放霍夫曼编码 }WordCount , *WC;//存放单词结点的结构体 typedef struct HuffmanTree { WC w; int Number;//存储有多少数据存入 }HuffmanTree , *HTree; typedef struct { unsigned int a:1; }bite;//设置位段，存储一个bite //**************操作函数声明*********** void InitHuffmanTree(HTree &H);//初始化霍夫曼树 void HeapSort(WC &W , int Number , int choice);//堆排序核心函数 void HeapAdjust(WC &W , int down , int up , int choice);//堆排序调整函数,实现两种排序 void HuffmanCoding(HTree &H , WC &HT); //求霍夫曼树和霍夫曼编码表 void ShowHuffmanTree(HTree H);//输出霍夫曼树 void Select(WC &W , int i , int &s1 , int &s2);//选择1-i-1之间最小的两个数，且parent为0，用s1,s2返回 void GetTheDeCode(HTree H);//将编码结果写入函数 void PutTheDeCode(FILE *fp1 , FILE *fp2);//将编码结果解码得到文章 void CountTheWord(HTree &H , FILE *fp);//记录单词权值 void ShowTheEassy(FILE *wp);//展示文章 四、详细设计 1.首先我给出了编码和解码的菜单供其选择 2.在编码功能中，我先通过CountTheWord（）函数进行单词权值记录，然后 进入编码功能，值得一提的是，编码时我给堆排序设计了两种排序形式——对权值的排序和对位置的排序，以达到选择两个最小的权值结点的最优时间复杂度的目的，此功能通过switch实现，但要给编码结构体中放置一个place 空间，这也从侧面反映了时间和空间矛盾的地方(值得一提的是，有些编码并不可见且有特殊含义，如换行符，所以将字符放入文件中时，并不对其进行处理，读出是进行顺序读出) 3.编码结束后将编码结果，对应字符分别存放在文件中，然后对整篇文章进行 编码
C++中的string类 前言:string的角色 1string使用 1.1充分使用string操作符 1.2眼花缭乱的string find函数 1.3string insert,replace,erase2string和C风格字符串 3string和Charactor Traits 4string建议 5小结 6附录前言:string的角色 C++语言是个十分优秀的语言，但优秀并不表示完美。还是有许多人不愿意使用C或者C++，为什么？原因众多，其中之一就是C/C++的文本处理功能太麻烦，用起来很不方便。以前没有接触过其他语言时，每当别人这么说，我总是不屑一顾，认为他们根本就没有领会C++的精华，或者不太懂C++，现在我接触perl,php,和Shell脚本以后，开始理解了以前为什么有人说C++文本处理不方便了。 举例来说，如果文本格式是：用户名电话号码，文件名name.txt Tom23245332 Jenny22231231 Heny22183942 Tom23245332 ... 现在我们需要对用户名排序，且只输出不同的姓名。 那么在shell编程中，可以这样用： awk'{print$1}'name.txt|sort|uniq 简单吧？ 如果使用C/C++就麻烦了，他需要做以下工作： 先打开文件，检测文件是否打开，如果失败，则退出。 声明一个足够大得二维字符数组或者一个字符指针数组 读入一行到字符空间 然后分析一行的结构，找到空格，存入字符数组中。 关闭文件 写一个排序函数，或者使用写一个比较函数，使用qsort排序 遍历数组，比较是否有相同的，如果有，则要删除，copy... 输出信息 你可以用C++或者C语言去实现这个流程。如果一个人的主要工作就是处理这种
#include"stdafx.h" #include"stdio.h" #include"conio.h" #include
附录二 表1. 传真用的修正霍夫曼编码表 构造码 64 11011 0000001111 960 011010100 0000001110011 128 10010 000011001000 1024 011010101 0000001110100 192 010111 000011001001 1088 011010110 0000001110101 256 0110111 000001011011 1152 011010111 0000001110110 320 00110110 000000110011 1216 011011000 0000001110111 384 00110111 000000110100 1280 011011001 0000001010010 448 01100100 000000110101 1344 011011010 0000001010011 512 01100101 0000001101100 1448 011011011 0000001010100 576 01101000 0000001101101 1472 010011000 0000001010101 640 01100111 0000001001010 1536 010011001 0000001011010 704 011001100 0000001001011 1600 010011010 0000001011011 768 011001101 0000001001100 1664 011000 0000001100100 832 011010010 0000001001101 1728 010011011 0000001100101 896 011010011 0000001110010 EOL 000000000001 000000000001 结尾码 游程长度 白游程编码 黑游程编码 游程长度白游程编码 黑游程编码 0 00110101 0000110111 32 000111011 000001101010 1 000111 010 33 00010010 000001101011 2 0111 11 34 00010011 000011010010 3 1000 10 35 00010100 000011010011 4 1011 011 36 00010101 000011010100 5 1100 0011 37 00010110 000011010101 6 1110 0010 38 00010111 000011010110 7 1111 00011 39 00101000 000011010111 8 10011 000101 40 00101001 000001101100 9 10100 000100 41 00101010 000001101101 10 00111 0000100 42 00101011 000011011010 11 01000 0000101 43 00101100 000011011011 12 001000 0000111 44 00101101 000001010100 13 000011 00000100 45 00000100 000001010101 14 110100 00000111 46 00000101 000001010110 15 110101 000011000 47 00001010 000001010111 16 101010 0000010111 48 00001011 000001100100 17 101011 0000011000 49 01010010 000001100101 18 0100111 0000001000 50 01010011 000001010010 19 0001100 00001100111 51 01010100 000001010011 20 0001000 00001101000 52 01010101 000000100100 21 0010111 00001101100 53 00100100 000000110111 22 0000011 00000110111 54 00100101 000000111000 23 0000100 00000101000 55 01011000 000000100111 24 0101000 00000010111 56 01011001 000000101000 25 0101011 00000011000 57 01011010 000001011000 26 0010011 000011001010 58 01011011 000001011001 27 0100100 000011001011 59 01001010 000000101011 28 0011000 000011001100 60 01001011 000000101100 29 00000010 000011001101 61 00110010 000001011010 30 00000011 000001101000 62 00110011 000001100110 31 00011010 000001101001 63 00110100 000001100111 205
#include
这个是string类的使用教程,可以参考一下 之所以抛弃char*的字符串而选用C++标准程序库中的string类，是因为他和前者比较起来，不必担心内存是否足够、字符串长度等等，而且作为一个类出现，他集成的操作函数足以完成我们大多数情况下(甚至是100%)的需要。我们可以用= 进行赋值操作，== 进行比较，+ 做串联（是不是很简单?）。我们尽可以把它看成是C++的基本数据类型。 好了，进入正题……… 首先，为了在我们的程序中使用string类型，我们必须包含头文件。如下：#include //注意这里不是string.h string.h是C字符串头文件 1．声明一个C++字符串 声明一个字符串变量很简单： string Str; 这样我们就声明了一个字符串变量，但既然是一个类，就有构造函数和析构函数。上面的声明没有传入参数，所以就直接使用了string的默认的构造函数，这个函数所作的就是把Str初始化为一个空字符串。String类的构造函数和析构函数如下： a) string s; //生成一个空字符串s b) string s(str) //拷贝构造函数生成str的复制品 c) string s(str,stridx) //将字符串str内“始于位置stridx”的部分当作字符串的初值 d) string s(str,stridx,strlen) //将字符串str内“始于stridx且长度顶多strlen”的部分作为字符串的初值 e) string s(cstr) //将C字符串作为s的初值 f) string s(chars,chars_len) //将C字符串前chars_len个字符作为字符串s 的初值。 g) string s(num,c) //生成一个字符串，包含num个c字符 h) string s(beg,end) //以区间beg;end(不包含end)内的字符作为字符串s的初值 i) s.~string() //销毁所有字符，释放内存 都很简单，我就不解释了。 2．字符串操作函数 这里是C++字符串的重点，我先把各种操作函数罗列出来，不喜欢把所有函数都看完的人可以在这里找自己喜欢的函数，再到后面看他的详细解释。 a) =,assign() //赋以新值 b) swap() //交换两个字符串的内容 c) +=,append(),push_back() //在尾部添加字符 d) insert() //插入字符 e) erase() //删除字符 f) clear() //删除全部字符 g) replace() //替换字符 h) + //串联字符串 i) ==,!=,<,<=,>,>=,compare() //比较字符串 j) size(),length() //返回字符数量
哈夫曼树编码 #include
} if (j==t->total) { t->arr[t->total].ch = text[i]; t->arr[t->total].weight = 1; t->total ++; } } printf("char frequence\n"); for (i=0; i
霍夫曼编码 霍夫曼编码(Huffman Coding)是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。1952年，David A. Huffman在麻省理工攻读博士时所提出一种编码方法，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。 该方法完全依据字符出现概率来构造异字头的平均长度最短的 码字，有时称之为最佳编码，一般就叫作Huffman编码。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。1951年，霍夫曼和他 在MIT信息论的同学需要选择是完成学期报告还是期末考试。 导师Robert M. Fano给他们的学期报告的题目是，查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。 霍夫曼（Huffman）编码是一种统计编码。属于无损（lossless）压缩编码。
以霍夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 ←根据给定数据集中各元素所出现的频率来压缩数据的 一种统计压缩编码方法。这些元素(如字母)出现的次数越 多，其编码的位数就越少。 ←广泛用在JPEG, MPEG, H.2X等各种信息编码标准中。霍夫曼编码的步骤 霍夫曼编码的具体步骤如下： １）将信源符号的概率按减小的顺序排队。 ２）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在上部，直到最后变成概率１。 3）将每对组合的上边一个指定为1，下边一个指定为0（或相反）。４）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。 信源熵的定义： 概率空间中每个事件所含有的自信息量的数学期望称信源熵或简称熵(entropy)，记为： 例：现有一个由5个不同符号组成的30个符号的字 符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长
本文作者：黄邦勇帅(编著)(原名：黄勇) 本文是学习C++的附加内容，主要介绍了C++中的string类的各种成员函数，及成员函数的功能与作用，是作为学习C++的参考使用的。 本文内容完全属于个人见解与参考文现的作者无关，其中难免有误解之处，望指出更正 本文使用的是x86机器(主流计算机都是x86机器)，windows xp操作系统，VC++2010编译器进行讲解的。 本文内容完全属于个人见解与参考文现的作者无关，限于水平有限，其中难免有误解之处，望指出更正。 声明：禁止抄袭，复印，转载本文，本文作者拥有完全版权。 主要参考文献： 1、C++.Primer.Plus.第五版.中文版[美]Stephen Prata著孙建春韦强译人民邮电出版社 2005年5月 2、C++.Primer第四版.中文版 Stanley B.Lippman、Barbara E.Moo、Josee Lajoie著李师贤、蒋爱军等译人民邮电出版社 2006年3月 3、C++.Primer第三版.中文版 Stanley B.Lippman、Josee Lajoie著潘爱民、张丽等译中国电力版社 2002年5月 第19部分 string类专题(共9页) (2016-7-15 修订版) 1、string类用于处理字符串，用于代替使用不方便的C风格字符串，使用string类表示的字符串我们可以像处理普通 变量那样处理字符串，因此可以对string类表示的字符串进行直接的相加，比较，赋值等操作，比如string s1=”abc”,s2=”def”;则s1=s1+s2;结果s1=”abcdef”；s1=s2;则结果s1=”def” 等，C风格字符串只能使用内置的库函数进行这些操作，使用很不方便，比如char c1[]=”abc”; char c2[]=”def”;则c1=c2;错误，不能改变数组的地址，c1>c2比较的是两个指针的地址而不是字符的大小；c1+c2;错误，这是把两个指针的地址相加而不是把两个字符数组相加。 2、string对象创建的字符串的最大特点是：可以自动调整对象大小以适应所需的字符串，string对象能存储的最大字符 数由string类的静态常量string::npos设定，通常是最大的unsigned int值。 一、string类的原型 1、要使用string类需要包含string头文件。 2、string是一个模板类，因此它具有类和模板的特性，也就是说string类有构造函数、重载的操作符、成员函数等， 因为string是模板类，因此应建一个模板类具体实例化版本的对象才能使用，然后通过对象调用成员函数使用类。 3、记住string s;创建的s是一个类的对象，而不是字符串字面值，他们是两种不同的类型。 4、string类是模板类basic_string类的char特化体版本使用typedef命名后的别名，wstring类是模板类basic_string的 wchar特体化版本使用typedef命名后的别名。 5、basic_string类的原型为(重点)： template
Huffman编码的matlab实现 一、信源编码介绍 为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。 既然信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。当然，这些都是广义的信源编码。 一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个：①使序列中的各个符号尽可能地互相独立；②使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性，后者称为概率均匀化。 信源编码的一般问题可以表述如下： 信源编码 若某信源的输出为长度等于M的符号序列集合式中符号A为信源符号表，它包含着K个不同的符号，A={ɑk|k=1,…,K}，这个信源至多可以输出K M个不同的符号序列。记‖U‖=KM。所谓对这个信源的输出 信源编码 进行编码，就是用一个新的符号表B的符号序列集合V来表示信源输出的符号序列集合U。若V的各个序列的长度等于 N，即式中新的符号表B共含L个符号，B={b l|l=1,…,L}。它总共可以编出L N个不同的码字。类似地,记‖V‖=LN。为了使信源的每个输出符号序列都能分配到一个独特的码字与之对应，至少应满足关系‖V‖=L N≥‖U‖=KM或者N/M≥log K/log L 下面的几个编码定理，提供了解决这个矛盾的方法。它们既能改善信息载荷效率，又能保证码字唯一可译。 离散无记忆信源的定长编码定理 对于任意给定的ε>0，只要满足条件N/M≥(H(U)+ε)/log L 那么，当M足够大时，上述编码几乎没有失真;反之,若这个条件不满足，就不可能实现无失真的编码。式中H(U)是信源输出序列的符号熵。 信源编码 通常，信源的符号熵H(U) 二章-信息量和熵习题解 2.1 莫尔斯电报系统中，若采用点长为0.2s ，1划长为0.4s ，且点和划出现的概率分别为2/3和1/3，试求它的信息速率(bits/s)。 解: 平均每个符号长为: 15 44.0312.032=?+?秒 每个符号的熵为9183.03log 3 123log 32=?+?比特/符号 所以，信息速率为444.34159183.0=?比特/秒 2.2 一个8元编码系统，其码长为3，每个码字的第一个符号都相同(用于同步)，若每秒产生1000个码字，试求其信息速率(bits ／s)。 解: 同步信号均相同不含信息,其余认为等概,每个码字的信息量为 3*2=6 比特； 所以，信息速率为600010006=?比特/秒 2.3 掷一对无偏的骰子，若告诉你得到的总的点数为：(a ) 7；(b ) 12。 试问各得到了多少信息量? 解: (a)一对骰子总点数为7的概率是 36 6 所以，得到的信息量为 585.2)36 6(log 2= 比特 (b) 一对骰子总点数为12的概率是36 1 所以，得到的信息量为 17.5361log 2= 比特 2.4 经过充分洗牌后的一付扑克(含52张牌)，试问： (a) 任何一种特定排列所给出的信息量是多少? (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量? 解: (a)任一特定排列的概率为! 521, 所以，给出的信息量为 58.225!521log 2 =- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 1313 1313525213!44A C ?= 所以，得到的信息量为 21.134 log 1313522=C 比特. 2.5 设有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点 出现时所给出的信息量，并求掷一次平均得到的信息量。 解:易证每次出现i 点的概率为 21i ,所以 比特比特 比特 比特 比特 比特 比特 398.221 log 21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21 log )(2612=-==============-==∑=i i X H x I x I x I x I x I x I i i i x I i 2.6 园丁植树一行，若有3棵白杨、4棵白桦和5棵梧桐。设这12棵树可随机地排列， 且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关 于树的排列的信息? 解: 可能有的排列总数为 27720! 5!4!3!12= 没有两棵梧桐树相邻的排列数可如下图求得， Y X Y X Y X Y X Y X Y X Y X Y 图中X 表示白杨或白桦，它有???? ??37种排法，Y 表示梧桐树可以栽种的位置，它有? ??? ??58种排法， 所以共有???? ??58*??? ? ??37=1960种排法保证没有两棵梧桐树相邻， 因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为1960log 27720log 22-=3.822 比特 2.7 某校入学考试中有1/4考生被录取，3/4考生未被录取。被录取的考生中有50%来 自本市，而落榜考生中有10％来自本市，所有本市的考生都学过英语，而外地落榜考生中以及被录取的外地考生中都有40%学过英语。 (a) 当己知考生来自本市时，给出多少关于考生是否被录取的信息?信息与编码理论课后习题答案
相关主题
文本预览