实验三哈夫曼编译器.zip

//#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) {//解码