数据结构实验报告--哈夫曼编译器.doc

资源描述

《数据结构》实验报告题目：专业：班级：组别：组长：完成日期：年月日评分依据及结果态度（A-D）规范性（A-D）完成度（A-D）总评（A-D）评语代码分工情况姓名工作内容实验报告分工情况姓名耿丽丽工作内容需求分析概要分析一、需求分析利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。本次设计要求对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。系统应具有如下的几个功能： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树 2、建立编码表(CreateTable):利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。 5、打印(Print)：以直观的方式打印哈夫曼树. 二、概要设计本程序的数据类型定义为 typedef struct{ int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char** HuffmanCode; //把字母和相应的权值放在一起 typedef struct { char ch; int wht; }WeNu; 所实现的功能函数如下 //统计叶子结点的权值 void CountWeight(char*str); //选择parent为0，且weight最小的两个节点序号为s1，s2 void Select(HuffmanTree HT,int len,int &s1,int &s2); // 构造哈夫曼树HT void CreatHuffmanTree(HuffmanTree &HT, int n) // 从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中 void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) //输出编码 void ShowCode(HuffmanTree HT, HuffmanCode HC, int n) //输出哈夫曼 void ShowHuffman(HuffmanTree HT, HuffmanCode HC, char *str) //输出字符串 void ShowStr(char *str) //选择解码方式 void DeCoding(); //主函数 void main(); 主要结构如图所示： CreatHuffmanTree ()构造哈夫曼树 CreatHuffmanCode ()构造哈夫曼编码输出字符串Str和解码调用DeCoding（）三、详细设计 1.统计字符频度自然语言描述：（1）取出字符串中的一个字符（2）遍历所有初始化的哈夫曼树结点（3）如果结点中有记录代表的字符且字符等于取出的字符，说明该字符的叶子存在，则将该结点的权值加1 （4）如果所有结点记录的字符均没有与取出的字符一致，说明该字符的叶子不存在，则将结点的字符记为取出字符，并将权重设为1 （5）重复以上步骤，直至字符串中所有字符全部遍历伪代码描述： 1. for(int i=0;i<length;i++) 1.1 for (int j=0;j<length;j++) 1.1.1if (WordStr[i]==HuffTree[j].word)//若字符已被统计，则增加权值即可 1.1.1.1 权重++; 1.1.1.2 break; 1.1.2 else if(!HuffTree[j].word)//否则需要一个新结点储存这个字符 1.1.2.1 HuffTree[j].word=WordStr[i]; 1.1.2.3 HuffTree[j].weight=1； 1.1.2.4break；时间复杂度O（N2），空间复杂度S（0） 2. 构造哈夫曼树：自然语言描述： (1) 选出权值最小的两个结点，其权值和作为其根结点的权值，最小的结点作为左子树； (2) 次小的做为右子树，不断将两棵子树合升为一棵树。重复及上述过程，直至所有结点全被遍历完。 3. 为每个叶子结点编码自然语言描述：（1）初始化一个字符数组Code暂存每个叶子节点的编码；（2）前序遍历哈夫曼树；（3）若结点左右子树都为-1，则将Code复制到编码的Code串，准备返回上一层，编码相位少一位，Code长度-1，返回；（4）否则按照从左到右的顺序前序遍历根结点的所有子树；（5）若访问左子树，则进入下一层，编码相位多一位，Code长度加1并将最后一位赋值为0，访问右子树，进入下一层，Code长度加1并将最后一位赋值为0。 4、编码自然语言描述：（1）定义字符串CodeStr储存编码（2）遍历输入字符串的每一个字符（3）对每一个字符，将其与HuffTree前n个叶子节点的word逐个比较，相同则将该节点的编码串Code连接到CodeStr。 5、译码自然语言描述：（1）从编码串CodeStr的第一个字符串开始于HuffTree的第一个节点的编码域第一个字符比较（2）相等则比较后面的字符（3）否则，从CodeStr第一个字符与HuffTree第二个结点的编码比较（4）重复上述过程，将CodeStr中的所有字符比较完毕四、调试分析 1.在写程序与调试的过程中，发现自己对于函数的调用与参数的传递的方面还是存在很多问题，从参数的类型等等方面都出现了很多问题。 2.关于这个程序的要求比较复杂，刚开始做的时候没有任何思路，最后分模块一点点的进行。 3．递归函数中的参数传递在给每个字符编码时，由于编码是从根结点开始，所以选用与前序遍历相似的递归遍历形式。其中需要一个字符型数组来记录路径和编码，由于递归一次才有一位编码，所以这个数组也要随着递归函数的进行而不断修改。开始时我们没有用指针最为参数而是直接将数组作为参数.结果发现每次调用递归函数时数组都是空。原来我用的是值传递，数组就算修改了也无法返回。这提醒了我们之后运用递归函数时如果需要某个变量随函数递归而修改时应该使用地址传递而并非值传递。心得体会：哈夫曼树又称做最优叉树，它是n个带权的叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。在n个带权的叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优二叉树。权值越大的结点离树根越近的二叉树才是最优叉树。哈夫曼树是根据字符出现的概率来构造平均长度最短的编码。它是-种变长的编码。在编码中，若各码字长度亚格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。哈夫曼树的应用非常广泛，在通信中，采用0.1的不同排列来表示不同的字符，而哈夫曼树在数据编码中的应用，若每个字符出现的频率相同，则可以采用等长的二进制编码，若频率不同，则可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是-种最优编码，在哈夫曼树中，规定往左编码为0,往右编码为1,则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。下一步的改进程序中多次使用了遍历数组或对数据进行逐个比对，循环的次数可以通过计算再减少，提高时间效率。五、用户守则请使用Windows系统来打开，平台为Visual Studio。要注意文本的打开方式和设置六、测试结果（及截图）七、附录（源代码）头文件 #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<stdio.h> #include<string.h> #include<cstring> using namespace std; #define NUM 26 typedef struct { char ch; int wht; }WeNu;//把字母和相应的权值放在一起 typedef struct { int weight; int parent, lchild, rchild; }HTNode, *HuffmanTree; typedef char **HuffmanCode; 源文件 //#include"weight.cpp" #include"Huffman.h" WeNu weight[NUM + 1]; void CountWeight(char*str) { for (int i = 1; i <= NUM; i++) { char cha = (char)(i + 96); weight[i].ch = cha;//////////////////////////////////////////简短代码——出过错 /*switch (i) { case 1: weight[1].ch = 'a'; break; case 2: weight[2].ch = 'b'; break; case 3: weight[3].ch = 'c'; break; case 4: weight[4].ch = 'd'; break; case 5: weight[5].ch = 'e'; break; case 6: weight[6].ch = 'f'; break; case 7: weight[7].ch = 'g'; break; case 8: weight[8].ch = 'h'; break; case 9: weight[9].ch = 'i'; break; case 10: weight[10].ch = 'j'; break; case 11: weight[11].ch = 'k'; break; case 12: weight[12].ch = 'l'; break; case 13: weight[13].ch = 'm'; break; case 14: weight[14].ch = 'n'; break; case 15: weight[15].ch = 'o'; break; case 16: weight[16].ch = 'p'; break; case 17: weight[17].ch = 'q'; break; case 18: weight[18].ch = 'r'; break; case 19: weight[19].ch = 's'; break; case 20: weight[20].ch = 't'; break; case 21: weight[21].ch = 'u'; break; case 22: weight[22].ch = 'v'; break; case 23: weight[23].ch = 'w'; break; case 24: weight[24].ch = 'x'; break; case 25: weight[25].ch = 'y'; break; case 26: weight[26].ch = 'z'; break; default: cout << "error!" << endl; }*/ weight[i].wht = 0; } int n = strlen(str); for (int i = 0; i < n; i++) { char c = str[i]; weight[((int)c) - 96].wht++;/////////////////////////////////////减短代码 //switch (c) { //case 'a': // weight[1].wht++; // break; //case 'b': // weight[2].wht++; // break; //case 'c': // weight[3].wht++; // break; //case 'd': // weight[4].wht++; // break; //case 'e': // weight[5].wht++; // break; //case 'f': // weight[6].wht++; // break; //case 'g': // weight[7].wht++; // break; //case 'h': // weight[8].wht++; // break; //case 'i': // weight[9].wht++; // break; //case 'j': // weight[10].wht++; // break; //case 'k': // weight[11].wht++; // break; //case 'l': // weight[12].wht++; // break; //case 'm': // weight[13].wht++; // break; //case 'n': // weight[14].wht++; // break; //case 'o': // weight[15].wht++; // break; //case 'p': // weight[16].wht++; // break; //case 'q': // weight[17].wht++; // break; //case 'r': // weight[18].wht++; // break; //case 's': // weight[19].wht++; // break; //case 't': // weight[20].wht++; // break; //case 'u': // weight[21].wht++; // break; //case 'v': // weight[22].wht++; // break; //case 'w': // weight[23].wht++; // break; //case 'x': // weight[24].wht++; // break; //case 'y': // weight[25].wht++; // break; //case 'z': // weight[26].wht++; // break; //default: // cout << "error!" << endl; /*}*/ } } void Select(HuffmanTree HT, int len, int &s1, int &s2) { int i, min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f;//先赋予最大值 for (i = 1; i <= len; i++) { if (HT[i].weight < min1&&HT[i].parent == 0) { min1 = HT[i].weight; s1 = i; } } int temp = HT[s1].weight;//将原值存放起来，然后先赋予最大值，防止s1被重复选择 HT[s1].weight = 0x3f3f3f3f; for (i = 1; i <= len; i++) { if (HT[i].weight < min2&&HT[i].parent == 0) { min2 = HT[i].weight; s2 = i; } } HT[s1].weight = temp;//恢复原来的值 } void CreatHuffmanTree(HuffmanTree &HT, int n) { //构造赫夫曼树HT int m, s1, s2, i; if (n <= 1) return; m = 2 * n - 1; HT = new HTNode[m + 1]; //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点 for (i = 1; i <= m; ++i) //将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0 { HT[i].parent = 0; HT[i].lchild = -(96 + i); HT[i].rchild = -(96 + i);//a的ASCII是97！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ } //cout << "请输入叶子结点的权值：\n"; for (i = 1; i <= n; ++i) //输入前n个单元中叶子结点的权值 HT[i].weight = weight[i].wht; /*――――――――――初始化工作结束，下面开始创建赫夫曼树――――――――――*/ for (i = n + 1; i <= m; ++i) { //通过n-1次的选择、删除、合并来创建赫夫曼树 Select(HT, i - 1, s1, s2); //在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点, // 并返回它们在HT中的序号s1和s2 HT[s1].parent = i; HT[s2].parent = i; //得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i HT[i].lchild = s1; HT[i].rchild = s2; //s1,s2分别作为i的左右孩子 HT[i].weight = HT[s1].weight + HT[s2].weight; //i 的权值为左右孩子权值之和 } //for } // CreatHuffmanTree void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) { //从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中 int i, start, c, f; HC = new char*[n + 1]; //分配n个字符编码的头指针矢量 char *cd = new char[n]; //分配临时存放编码的动态数组空间 cd[n - 1] = '\0'; //编码结束符 for (i = 1; i <= n; ++i) { //逐个字符求赫夫曼编码 start = n - 1; //start开始时指向最后，即编码结束符位置 c = i; f = HT[i].parent; //f指向结点c的双亲结点 while (f != 0) { //从叶子结点开始向上回溯，直到根结点 --start; //回溯一次start向前指一个位置 if (HT[f].lchild == c) cd[start] = '0'; //结点c是f的左孩子，则生成代码0 else cd[start] = '1'; //结点c是f的右孩子，则生成代码1 c = f; f = HT[f].parent; //继续向上回溯 } //求出第i个字符的编码 HC[i] = new char[n - start]; // 为第i 个字符编码分配空间 strcpy(HC[i], &cd[start]); //将求得的编码从临时空间cd复制到HC的当前行中 } delete cd; //释放临时空间 } void ShowCode(HuffmanTree HT, HuffmanCode HC, int n) { for (int i = 1; i <= n; i++) { cout << weight[i].ch << "(" << HT[i].weight << ")" << "编码为" << HC[i] << "\t\t\t"; if (i % 2 == 0) { printf("\n"); } } } void ShowHuffman(HuffmanTree HT, HuffmanCode HC, char *str) { int i = 0; while (str[i] != '\0') { char c = str[i]; cout << HC[((int)c) - 96];/////////////////////////////////////简短代码 /*switch (c) { case 'a': cout << HC[1]; break; case 'b': cout << HC[2]; break; case 'c': cout << HC[3]; break; case 'd': cout << HC[4]; break; case 'e': cout << HC[5]; break; case 'f': cout << HC[6]; break; case 'g': cout << HC[7]; break; case 'h': cout << HC[8]; break; case 'i': cout << HC[9]; break; case 'j': cout << HC[10]; break; case 'k': cout << HC[11]; break; case 'l': cout << HC[12]; break; case 'm': cout << HC[13]; break; case 'n': cout << HC[14]; break; case 'o': cout << HC[15]; break; case 'p': cout << HC[16]; break; case 'q': cout << HC[17]; break; case 'r': cout << HC[18]; break; case 's': cout << HC[19]; break; case 't': cout << HC[20]; break; case 'u': cout << HC[21]; break; case 'v': cout << HC[22]; break; case 'w': cout << HC[23]; break; case 'x': cout << HC[24]; break; case 'y': cout << HC[25]; break; case 'z': cout << HC[26]; break; default: cout << "error!" << endl;*/ /*}*/ i++; } } void ShowStr(char *str) { for (int i = 0; i < strlen(str); i++) { cout << str[i]; } cout << endl; } void DeCoding(HuffmanTree HT, char *str) {//解码 int n = strlen(str); int j = 2 * NUM - 1; for (int i = 0; i < n; i++) { if (str[i] == '0') { j = HT[j].lchild; if (HT[j].lchild < 0) { printf("%c", (-HT[j].lchild)); j = 2 * NUM - 1; } } else//str[i]=='1' { j = HT[j].rchild; if (HT[j].rchild < 0) { printf("%c", (-HT[j].rchild)); j = 2 * NUM - 1; } } } } void main() { HuffmanTree HT; HuffmanCode HC; char *str1 = { (char*)"qwetyughjkiopasfdadzxcvbnmjkfghsadtyuiodfgxcv" }; char *str2 = {(char*)"0100010001001101110001011110000111111001100010111011100111000"}; cout << "此字符串为："; ShowStr(str1); CountWeight(str1); CreatHuffmanTree(HT, NUM); CreatHuffmanCode(HT, HC, NUM); ShowCode(HT, HC, NUM); cout << "此字符串的Huffman编码为:\n"; ShowHuffman(HT, HC, str1); cout << endl; cout << "原始的Huffman为:\n"; ShowStr(str2); cout << "解码过后的字符串为:\n"; DeCoding(HT, str2); cout << endl; system("pause"); }

展开阅读全文