2024年哈夫曼编码实验报告

数据构造试验汇报试验规定运用二叉树构造实現哈夫曼编/解码器。基本规定：初始化(Init)：可以對输入的任意長度的字符串s進行记录，记录每個字符的频度，并建立哈夫曼树建立编码表(CreateTable)：运用已經建好的哈夫曼树進行编码，并将每個字符的编码输出。编码(Encoding)：根据编码表對输入的字符串進行编码，并将编码後的字符串输出。译码(Decoding)：运用已經建好的哈夫曼树對编码後的字符串進行译码，并输出译码成果。打印(Print)：以直观的方式打印哈夫曼树（选作）计算输入的字符串编码前和编码後的長度，并進行分析，讨论哈夫曼编码的压缩效果。并用IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.進行测试。2.程序分析哈夫曼树結點的存储构造包括双亲域parent，左子树lchild，右子树rchild，尚有字符word，权重weight，编码code對顾客输入的信息進行记录，将每個字符作為哈夫曼树的叶子結點。记录每個字符出現的次数作為叶子的权重，记录次数可以根据每個字符不一样的ASCII码，根据叶子結點的权重建立一种哈夫曼树。建立每個叶子的编码從根結點開始，规定通往左子树途径记為0，通往右子树途径记為1。由于编码规定從根結點開始，因此需要前序遍历哈夫曼树，故编码過程是此前序遍历二叉树為基础的。同步注意递归函数中能否直接對結點的编码域進行操作。编码信息只要遍历字符串中每個字符，從哈夫曼树中找到對应的叶子結點，获得對应的编码。最终再将所有找到的编码连接起来即可。译码则是将编码串從左到右逐位鉴别，直到确定一种字符。這就是哈夫曼树的逆過程。遍历编码串，從哈夫曼树中找到對应的叶子結點，获得對应的字符再将找到的字符连接起来即可。2.1存储构造哈夫曼树結點存储构造parentlchildrchildwordweightcodeparentlchildrchildwordweightcode2.2关键算法分析1.记录字符频度自然語言描述：取出字符串中的一种字符遍历所有初始化的哈夫曼树結點假如結點中有记录代表的字符且字符等于取出的字符，阐明该字符的叶子存在，则将该結點的权值加1假如所有結點记录的字符均没有与取出的字符一致，阐明该字符的叶子不存在，则将結點的字符记為取出字符，并将权重设為1反复以上环节，直至字符串中所有字符所有遍历伪代码描述：1.for(inti=0;i<length;i++) 1.1for(intj=0;j<length;j++) 1.1.1if(WordStr[i]==HuffTree[j].word)//若字符已被记录，则增長权值即可 1.1.1.1权重++; 1.1.1.2break; 1.1.2elseif(!HuffTree[j].word)//否则需要一种新結點储存這個字符 1.1.2.1HuffTree[j].word=WordStr[i]; 1.1.2.2HuffTree[j].weight=1; 1.1.2.3叶子結點個数++; 1.1.2.4break;時间复杂度O(n2)，空间复杂度S(0)2.构造哈夫曼树自然語言描述：选出权值最小的两個結點，其权值和作為其根結點的权值，最小的結點作為左子树，次小的作為右子树，不停将两棵子树合并為一棵树。反复上述過程，直至所有結點全被遍历完伪代码描述：1.intleaves=n;2.for(intj=n;j<2*n-1;j++) 2.1intj1=0;intj2=0; 2.2Select(HuffTree,leaves,j,j1,j2);//选出两個权值最小結點 2.3HuffTree[j1].parent=j;HuffTree[j2].parent=j; 2.4HuffTree[j].weight=HuffTree[j1].weight+HuffTree[j2].weight;//根結點权值等于两個結點权值和 2.5HuffTree[j].lchild=j1;HuffTree[j].rchild=j2;//左子树為权值最小，右子树权值次小 2.6叶子数--;時间复杂度O(n)，空间复杂度S(2)3.為每個叶子結點编码自然語言描述：初始化一种字符数组Code暂存每個叶子結點的编码。前序遍历哈夫曼树若結點左右子树都為-1，则将code复制到编码的code串，准备返回上一层，编码對应少一位，code長度減1，返回否则按照從左到右的次序前序遍历根結點的所有子树若访問左子树，则進入下一层，编码對应多一位，code長度加1并将最终一位赋0；访問右子树，進入下一层，code長度加1并将最终一位赋為0伪代码描述：1.if結點左右孩子均為-1 1.1.将Code复制到huffTree的code 1.2.return; 1.3.否则 1.3.1.if結點左子树存在1.3.1.1.Code長度增一 1.3.1.2.Code最终一位赋0； 1.3.1.3.访問左子树； 1.3.1.4.层数減一； 1.3.2.If結點右子树存在1.3.2.1.Code長度增一 1.3.2.2.Code最终一位赋1； 1.3.2.3.访問右子树； 1.3.2.4.层数減一；算法時间复杂度O(n2)，空间复杂度S(60)4.编码自然語言描述：定义字符串CodeStr储存编码遍历输入字符串的每一种字符對每一种字符，将其与HuffTree前n個叶子結點的word逐一比较，相似则将该結點的编码串code连接到CodeStr的末尾遍历結束後，输出CodeStr伪代码描述：while(字符串字符不為0)while（叶子結點word不為空）if（字符等于word中的字符）1.1.1.1strcat(CodeStr,code); 1.1.1.2.break;2.cout<<CodeStr<<endl;算法時间复杂度O(n2)，空间复杂度S(2)5.译码自然語言描述：從编码串CodeStr的第一种字符開始与HuffTree第一种結點的编码域第一种字符比较相等则继续比较背面的字符否则，從CodeStr第一种字符与HuffTree第二個結點的编码比较反复上述過程，将CodeStr中的所有字符比较完毕伪代码描述：1.在CodeStr和huffTree.code中设比较的起始下標i和j2.遍历数组huffTree2.1.循环至CodeStr或huffTree.code所有的字符均比较完2.1.1.假如CodeStr[i]=huffTree[k].code，继续比较下一种字符，否则2.1.2.将i和j回溯，跳出该层循环2.2假如huffTree[k].code全比较完，输出huffTree[k].word。否则取huffTree下一种結點继续循环本趟匹配開始位置i主串CodeStr回溯。。。。。huffTree[k+1]huffTree[k]j回溯時间复杂度O(n2)，空间复杂度S(3)3.程序运行成果開始開始菜單界面,选择菜單界面,选择123456退出程序有关程序重新编码解码器编码表编码器退出程序有关程序重新编码解码器编码表编码器输出编码输出程序信息输入要编码的信息输出要编码的信息输出编码输出程序信息输入要编码的信息输出要编码的信息输入要编码的信息任意键操作输出翻译出的信息输出编码的成果输出编码表任意键操作输出翻译出的信息输出编码的成果输出编码表输出编码的成果任意键操作任意键操作任意键操作任意键操作任意键操作任意键操作任意键操作任意键操作結束結束测试条件：問題规模n的数量级為1。测试内容：IlovedataStructure,IloveComputer.IwilltrymybesttostudydataStructure.测试結论：测试的功能有：建立哈夫曼树、對每個字符進行编码、對信息字符串進行编码、對编码串進行译码，重新進行编码。各项功能均能正常运行。界面的跳转也能实現。编码前信息總長度為664bits，编码後的長度為339bits。由于哈夫曼编码采用不等長编码，有效缩短了编码長度，节省了空间。4.總結调试時出現的問題及处理的措施递归函数中的参数传递在給每個字符编码時，