问题描述
如图所示，共读出31个不同的字符，但26个小写字母外加“,”、“.”和“ ”应该只有29个呀？更重要的是，为什么打印至k则停止了，还有部分字母为什么不输出至频数表呢？代码如下，请多指教！
include <iostream>include<fstream>include <algorithm>using namespace std;
class HuffmanTree//构造霍夫曼树的类{public:unsigned int Weight, Parent, lChild, rChild;//四个属性：权重，父节点，左孩子，右孩子};typedef char **HuffmanCode;/*
从结点集合中选出权值最小的两个结点
将值分别赋给s1和s2*/
void Select(HuffmanTree HT, int Count, int s2, int *s1)//根据权重a[1:n]构造霍夫曼树,count为权重最大值{
unsigned int temp1 = 0;unsigned int temp2 = 0;unsigned int temp3;for (int i = 1; i <= Count; i++)//从权重小的开始{ if (HT[i].Parent == 0) {if (temp1 == 0){ temp1 = HT[i].Weight;//放入当前最小权重 (*s1) = i;}else{ if (temp2 == 0) {temp2 = HT[i].Weight;//放入当前次小的权重(*s2) = i;if (temp2<temp1)//规定左孩子权重比右孩子大，左temp2>右temp1{ temp3 = temp2; temp2 = temp1; temp1 = temp3; temp3 = (*s2); (*s2) = (*s1); (*s1) = temp3;} } else//第三次及之后的构造 {if (HT[i].Weight<temp1)//新权重比右孩子的权重还小，存为新的右孩子{ temp2 = temp1; temp1 = HT[i].Weight; (*s2) = (*s1); (*s1) = i;}if (HT[i].Weight>temp1&&HT[i].Weight<temp2){ temp2 = HT[i].Weight; (*s2) = i;} }} }}
}
//生成霍夫曼编码void HuffmanCoding(HuffmanTree * HT,
HuffmanCode * HC,int *Weight,int Count)
{
int i;int s1, s2;int TotalLength;char* cd;unsigned int c;unsigned int f;int start;if (Count <= 1) return;TotalLength = Count * 2 - 1;//节点个数HT = new HuffmanTree[(TotalLength + 1)*sizeof(HuffmanTree)];//创建霍夫曼树for (i = 1; i <= Count; i++)//遍历不同字符，生成叶子节点{ HT[i].Parent = 0; HT[i].rChild = 0; HT[i].lChild = 0; HT[i].Weight = (*Weight); Weight++;}for (i = Count + 1; i <= TotalLength; i++)//生成非叶子节点{ HT[i].Weight = 0; HT[i].Parent = 0; HT[i].lChild = 0; HT[i].rChild = 0;}//建造霍夫曼树for (i = Count + 1; i <= TotalLength; ++i){ Select(HT, i - 1, &s1, &s2); HT[s1].Parent = i; HT[s2].Parent = i;//左右孩子指向同一父节点 HT[i].lChild = s1;//左孩子为s1，权重小的 HT[i].rChild = s2; HT[i].Weight = HT[s1].Weight + HT[s2].Weight;//父节点权重为左右孩子权重之和}//输出霍夫曼编码(*HC) = (HuffmanCode)malloc((Count + 1)*sizeof(char*));cd = new char[Count*sizeof(char)];//存放编码cd[Count - 1] = ’0’;for (i = 1; i <= Count; ++i)//遍历不同字符{ start = Count - 1;//从下至上编码，从后往前编码 for (c = i, f = HT[i].Parent; f != 0; c = f, f = HT[f].Parent)//循环至根节点终止，每次循环辈分升高一次 {if (HT[f].lChild == c)//左0右1规则（） cd[--start] = ’0’;else cd[--start] = ’1’;(*HC)[i] = new char[(Count - start)*sizeof(char)];//存放霍夫曼编码strcpy_s((*HC)[i], strlen(&cd[start]) + 1, &cd[start]);//将生成的编码拷贝至霍夫曼编码中存放 }}//删除霍夫曼树及编码存放数组delete[] HT;delete[] cd;
}
//检测函数int LookFor(char *str, char letter, int count)//检测字符是否已在频数表中出现过，未出现时返回-1，出线出现过时返回在频数表中的位置{
int i;for (i = 0; i<count; i++){ if (str[i] == letter) return i;}return -1;
}
//生成字符、权重对应表void OutputWeight(const char *Data, int Length,//Lengh为输入字符串的长度
char **WhatLetter,int **Weight, int *Count)
{
int i;//构造频数表char* Letter = new char[Length];//存放各个字符int* LetterCount = new int[Length];//存放字符出现频率，即其权重int AllCount = 0;//统计不同字符的总数int Index;//索引号用于在频数表中查找字符int Sum = 0;float Persent = 0;for (i = 0; i<Length; i++)//遍历字符串{ if (i == 0) {Letter[0] = Data[i];LetterCount[0] = 1;AllCount++; } else {Index = LookFor(Letter, Data[i], AllCount);if (Index == -1)//频数表中无该字符，则在频数表中建立新空间存放对应字符{ Letter[AllCount] = Data[i];//字符存入频数表 LetterCount[AllCount] = 1;//自负对因频数加1 AllCount++;//不同字符数加1}else//频数表中已有该字符，其频数加1{ LetterCount[Index]++;} }}for (i = 0; i<AllCount; i++)//计算不同字符的总数{ Sum = Sum + LetterCount[i];}//构造频率字符对应表(*Weight) = new int[AllCount];//存放各字符的频率(*WhatLetter) = new char[AllCount];//存放各个字符for (i = 0; i<AllCount; i++)//遍历不同字符{ Persent = (float)LetterCount[i] / (float)Sum;//计算出现频率 (*Weight)[i] = (int)(100 * Persent); (*WhatLetter)[i] = Letter[i];}(*Count) = AllCount;//删去频数表delete[] Letter;delete[] LetterCount;
}
void main(){
HuffmanTree * HT = NULL;HuffmanCode HC;char *WhatLetter;int *Weight;int Count;ifstream ifle('input.txt');string s;while (ifle) s.push_back(ifle.get());transform(s.begin(), s.end(), s.begin(), tolower);//转小写const char* str = s.c_str();cout << str << endl;;OutputWeight(str, strlen(str), &WhatLetter, &Weight, &Count);//生成字符频率对应表HuffmanCoding(HT, &HC, Weight, Count);//由频率表生成霍夫曼编码cout << Count;cout << 'char freq code' << endl;for (int i = 0; i<Count; i++){ cout << WhatLetter[i] << ' '; cout << Weight[i] << '%t'; cout << HC[i + 1] << endl;}cout << Count << endl;cout << endl;
}
问题解答
回答1：共读出31个不同的字符，但26个小写字母外加“,”、“.”和“ ”应该只有29个呀？
还有 “-” 和 EOF
为什么打印至k则停止了
因为你SEGV了。你的程序在`cout << HC[i + 1] << endl;`这行丢SEGV。
