问题:
多次修改程序,但总是出现分配出错问题,不知道怎么改善。
看了好几天,不知道怎么改。
错误截图:
代码功能是:
在一个txt文件里读取所有字符,统计出现的次数,并用赫夫曼编码显示。
代码:
头文件:
#ifndef HEADER_H_
#define HEADER_H_
//赫夫曼树
typedef struct
{
char ch;
int weight;
int parent, lchlld, rchild;
}HTNode,*HuffmanTree;
//赫夫曼编码表
typedef char** HuffmanCode;
typedef struct SqList
{
char ch;
int weight;
}SqList,*Sq;
//读取文件
int File_to_SQ(const char* filename, Sq& sql);
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, const Sq&SQ, int n);
void Weight_Select(const HuffmanTree& HT, int n, int& s1, int& s2);
#endif
方式实现源文件:
#include"header.h"
#include<iostream>
#include<stdlib.h>
void Weight_Select(const HuffmanTree& HT, int i, int& s1, int& s2)
{
s1 = s2 = 0;
for (int n = 1; n <= i; n++)
{
if (HT[n].parent == 0)
{
//两个 if 条件语句,只能执行一个,使得优先让s1成为最小值,
//让s2继承s1之前的值。
if (s1 == 0 || HT[n].weight < HT[s1].weight)
{
s2 = s1;
s1 = n;
}
else if (s2 == 0 || HT[n].weight < HT[s2].weight)
{
s2 = n;
}
}
}
}
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, const Sq&SQ, int n)
{
if (n <= 1)
return;
//赫夫曼树总结点数
int m;
m = 2 * n - 1;
int i;
HuffmanTree p;//移动指针
Sq ps;//创建移动指针
for (p = HT + 1, i = 0,ps=SQ+1; i < n; ++i, ++p, ++ps)
{
*p = { ps->ch,ps->weight,0,0,0 };
//charArr[i] = ps->ch;
}
//i=n
for (; i <= m; ++i, ++p)
{
//储存字符 权重 父节点 左子树 右子树
*p = { '\0',0,0,0,0 };
}
//最小值 第二最小值
int s1, s2;
//走到这步n至少等于2,m=2n-1
for (i = n + 1; i <= m; ++i)
{
//从HT+1到HT+i-1中寻找到parent==0的两个最小值下标
Weight_Select(HT, i - 1, s1, s2);
//两个最小值和i连接成夫结点与左右子树
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchlld = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
//生成赫夫曼编码
// HC = new char*[n];
//赫夫曼编码缓存
char* code = new char[n];
code[n-1] = '\0';
//HT[1] ~HT[n]
for (i = 1; i <=n; ++i)
{
int start = n - 1;
int c = i;
int p = HT[i].parent;
//从叶子结点向上直到根来得出赫夫曼编码
//叶子结点的父节点为根
while (p != 0)
{
if (HT[p].lchlld == c)
code[--start] = '0';
else
code[--start] = '1';
c = p;
p = HT[p].parent;
}
//为每个字符分配赫夫曼编码的储存空间
HC[i - 1] = new char[n- start];
//复制到对应赫夫曼编码表中
strcpy_s(HC[i - 1], n - start, &code[start]);
}
delete[] code;
code = NULL;
}
#include<fstream>
int File_to_SQ(const char* filename, Sq& sql)
{
using namespace std;
ifstream InFile;
InFile.open(filename);
if (!InFile.is_open())
{
exit(EXIT_FAILURE);
}
char ch;
int count=0;
while (InFile >> ch)
{
count = 1;
while (sql[count].ch!='\0' && ch != sql[count].ch)
count++;
if (sql[count].ch=='\0')
{
sql[count].ch = ch;
sql[count].weight = 1;
}
else
{
sql[count].weight++;
}
}
InFile.close();
return count;
}
main文件:
#include<iostream>
#include"header.h"
#define MAXSIZE 30
int main()
{
using namespace std;
//
Sq SqL = new SqList[MAXSIZE]();
int num=File_to_SQ("school-profile.txt", SqL);
int i;
//
//cout << "number:\n";
//int num;
//cin >> num;
////创建新数组
//Sq SqL=new SqList[num+1];
//Sq sqf;
//int i;
//cout << "character & weight:\n";
//for (i = 0,sqf=SqL+1; i < num; ++i,++sqf)
//{
// cout << "character: ";
// cin >> sqf->ch;
// cout << "weigth: ";
// cin >> sqf->weight;
//}
//
HuffmanTree HT=new HTNode[2*num];
HT[0]={0,0,0,0,0};
HuffmanCode HC=new char *[num];
HuffmanCoding(HT, HC, SqL, num);
for (i = 1; i <= 2 * num - 1; i++)
{
cout << HT[i].ch << "\t";
cout << HT[i].weight << "\t";
cout << HT[i].parent << '\t';
cout << HT[i].lchlld << '\t';
cout << HT[i].rchild << endl;
}
cout << "character\tweight\tcode\n";
for (i = 0; i < num; ++i)
{
cout << "\t" << HT[i + 1].ch;;
cout << "\t" << HT[i + 1].weight;
cout << "\t" << HC[i] << endl;
}
//销毁指针
for (i = 0; i < num; i++)
{
delete HC[i];
}
delete[] SqL;
delete[] HC;
delete[] HT;
return 0;
}