问题:
1.在程序运行过程中,赫夫曼编码表动态分配时,会触发断点,内存分配出问题。
2.原以为是自己代码出错,修改后还是不能运行,于是用朋友的电脑运行,结果一次成功,并没有问题。
3.但到现在在自己的编译器上仍然无法运行。
问题截图:
然后,我在上面写了一个类似的char ** 动态分配,也显示没错,没任何问题。
可一旦运行到加断点的那一步,就会报错,难道是编译器问题?
代码:
头文件:
typedef struct {
int weight;//结点权重
int parent, lchild, rchild;//父亲结点,左子树,右子树
}HTNode,*HuffmanTree;//动态分配数组储存赫夫曼树
typedef char** HuffmanCode;//动态分配数组储存赫夫曼编码表
//
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, int n);
//选择出储存的n个字符中所占权重最小的两位,并返回到s1,s2中
//其中s1,s2是在HT中,从1到n中的HTNode序号
void Weight_Select(HuffmanTree& HT, int i, int& s1, int& s2);
void Weight_Select_DF(HuffmanTree& HT, int i, int& s1, int& s2);
//赫夫曼编码解码
//大概思路:
/*
根据编码进入赫夫曼树进行遍历,直到末端,然后将权重读出。
*/
void HuffmanCoD(HuffmanCode& HC, HuffmanTree& HT, int n);
#endif
赫夫曼编码实现:
void HuffmanCoding(HuffmanTree& HT, HuffmanCode &HC, int* w, int n)
{
////测试
//char** a = new char* [n+1];
//a[0] = new char[10]();
//char ma[] = "avc";
//strcpy(a[0], ma);
//a[1] = new char[2]();
//int k = sizeof(a);
//w存放n个字符的权值,构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC.
if (n <= 1)
return;
int m;//n个字符都储存在赫夫曼树的末端,为叶子结点,故需要的结点数为m。
m = 2 * n - 1;
HT = new HTNode;//分配空间
int i;
HuffmanTree p;//创建移动结构指针
for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w)
{
//在内存中移动指针指向的内存
*p = { *w,0,0,0 };
}
//i此时为n+1,将所有字符全部都储存了,从1开始到n,储存了n个字符
for (; i <= m; ++i, ++p)
{
//用移动结构指针将创建赫夫曼数所需结点数全部初始化
*p = { 0,0,0,0 };
}
int s1, s2;
//下标s1,s2,代表含义最小值,第二最小值
for (i = n + 1; i <= m; ++i)
{
//从HT+1到HT+i-1中寻找到parent==0的两个最小值下标
Weight_Select(HT, i - 1, s1, s2);
//两个最小值成为一个结点的左右子树
HT[s1].parent = i; HT[s2].parent = i;
//将结点与子树连接。
HT[i].lchild = s1; HT[i].rchild = s2;
//将权重相加得到结点权重
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
//chat gpt 版本
//从叶子到根逆向求每个字符的赫夫曼编码
HC = new char* [n + 1];//分配空间
////内存缓冲区
//char* buffer = new char[n * n + 1];
char* cd = new char[n];
cd[n - 1] = '\0';//编码结束符
for (i = 1; i <= n; ++i)
{
int start = n - 1; //从叶子开始走到根,下标指向当前结点
for (int c = i, f = HT[c].parent; f != 0; c = f, f = HT[c].parent)
{ //如果c结点是它父亲结点的左孩子,则对应编码的最后一位为0
//否则,对应编码的最后一位为1
if (HT[f].lchild == c)
cd[--start] = '0';
else
cd[--start] = '1';
}
//动态分配每个字符的编码
int size = n - start;
// --报错地方--:
HC[i] = new char [size];
strcpy(HC[i], &cd[start]);
//delete[] cd;
}
delete[] cd;
//delete[] buffer;//释放空间}
}
主函数:
int main()
{
using namespace std;
HuffmanTree HT;
HuffmanCode HC;
int num;
cout << "输入叶子数量:\n";
cin >> num;
int* w=new int [num];
cout << "输入叶子结点权重值:\n";
for (int m = 0; m < num; m++)
{
cin >> w[m];
}
//得到树HT 和 HC
HuffmanCoding(HT, HC, w, num);
//输出霍夫曼树
cout << "weigth\t" << "parent\tlchild\trchild";
for (int i = 1; i <= 2 * num - 1; ++i)
{
cout << endl;
cout << HT[i].weight << '\t'
<< HT[i].parent << '\t'
<< HT[i].lchild << '\t'
<< HT[i].rchild;
}
cout << "\nweigth\t" << "HuffmanCode\n";
for (int i = 1; i <= num; ++i)
{
cout << HT[i].weight << '\t' << HC[i] << endl;
}
delete HT;
delete[] HC;
return 0;
}
困扰好久了,无法解决。