C语言哈夫曼树编码及其解码
问题：
读取文件并对其中的数据进行哈夫曼树编码和解码
出现的问题：
用数据创建哈夫曼树并对哈夫曼树进行先序遍历的时候，出现程序崩溃，崩溃的原因我觉得莫名其妙
如图：
需求：
1.解决上述问题，将字符数据翻译为哈夫曼树编码
2.完成对解码部分的代码
代码：
#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
typedef struct TreeNode //定义树结点
{
int weight; //权值
int parent;
int lchild;
int rchild;
char ch;
}treenode;
typedef struct HuffmanTree //定义huffmantree，用数组表示树
{
treenode* data;
int length;
}huffmantree;
huffmantree* huffmantree_create(int weight[], int length, char character[])//huffmantree初始化
{
huffmantree* tree = (huffmantree*)malloc(sizeof(huffmantree));
tree->data = (treenode*)malloc(sizeof(treenode) * (2 * length - 1)); //n个元素，树中有2n-1个结点
tree->length = length;
for (int i = 0; i < length; i++)
{
tree->data[i].weight = weight[i];
tree->data[i].parent = 0;
tree->data[i].lchild = -1;
tree->data[i].rchild = -1;
tree->data[i].ch = character[i];
}
return tree;
}
int* selectMin(huffmantree* tree)//选择最小的两个结点
{
int min=10000, secmin=10000;
int minIndex, secminIndex;
for (int i = 0; i < tree->length; i++) //找到最小的结点的索引下标
{
if (tree->data[i].parent == 0)
{
if (tree->data[i].weight < min)
{
min = tree->data[i].weight;
minIndex = i;
}
}
}
for (int i = 0; i < tree->length; i++) //找到第二小的结点的索引下标
{
if (tree->data[i].parent == 0 && i != minIndex)
{
if (tree->data[i].weight < secmin)
{
secmin = tree->data[i].weight;
secminIndex = i;
}
}
}
int* res = (int*)malloc(sizeof(int) * 2); //返回两个数据，用int数组返回
res[0] = minIndex;
res[1] = secminIndex;
return res;
}
void createTree(huffmantree* tree) //建树
{
int min;
int secmin;
int* res;
for (int i = tree->length; i < tree->length * 2 - 1; i++)
{
res = selectMin(tree);
printf("%d %d\t", res[0], res[1]);
min = res[0];
secmin = res[1];
tree->data[i].weight = tree->data[min].weight + tree->data[secmin].weight;
tree->data[min].parent = i; //设置双亲结点
tree->data[secmin].parent = i;
tree->data[i].parent = 0;
tree->data[i].lchild = min; //设置孩子结点
tree->data[i].rchild = secmin;
tree->length++;
}
}
void preorder(huffmantree* tree,int index)
{
while (index != -1)
{
printf("%c %d\n", tree->data[index].ch, tree->data[index].weight);
preorder(tree, tree->data[index].lchild);
preorder(tree, tree->data[index].rchild);
}
}
int main()
{
FILE* fp;
char ch, str[100],character[100];
int length = 0, option, lengthchar = 0, weight[100];
fp = fopen("test3.txt", "r+");
if (fp == NULL)
{
printf("打开文件失败\n");
exit(0);
}
printf("打开文件成功\n");
ch = fgetc(fp);
while (ch != EOF)
{
str[length] = ch;
length++;
ch = fgetc(fp);
}
str[length] = '\0';
printf("该文件的数据为:");
puts(str);
printf("请问你是要对文件进行加密还是进行解密？(输入1为加密，输入2为解密)");
printf("我选择：");
scanf("%d", &option);
while (option != 1 && option != 2)
{
printf("你的输入有误，请重新输入！\n我选择：");
scanf("%d", &option);
}
if (option == 1) //对数据进行huffmantree编码
{
int status;
huffmantree* hftree;
for (int i = 0; i < length; i++) //先把str中的每一个字符都单列出来放进数组character
{
status = 0;
for (int t = 0; t < lengthchar; t++)
{
if (str[i] == character[t])
{
status = 1;
break;
}
}
if (status == 1)
continue;
character[lengthchar] = str[i];
lengthchar++;
}
character[lengthchar] = '\0';
printf("字符数组为:");
puts(character);
for (int i = 0; i < lengthchar; i++) //将权值数组归0
{
weight[i] = 0;
}
for (int i = 0; i < lengthchar; i++) //设置权值数组
{
for (int t = 0; t < length; t++)
{
if (str[t] == character[i]) //统计每个字符的出现次数
weight[i]++;
}
}
printf("权值数组为:");
for (int i = 0; i < lengthchar; i++)
printf("%d ", weight[i]);
printf("\n");
hftree = huffmantree_create(weight, lengthchar, character);
createTree(hftree);
preorder(hftree,hftree->length-1);
}
if (option == 2)//对huffmantree编码进行解码
{
}
fclose(fp);
return 0;
}
谢谢！
因为有某次调用selectMin()函数时没有进54行那个分支，导致secminIndex没有初始化就赋值给了res[1]
void createTree(huffmantree* tree) //建树
{
int min;
int secmin;
int* res;
int length = tree->length;
for (int i = length; i < length * 2 - 1; i++)
{
res = selectMin(tree);
printf("%d %d\t", res[0], res[1]);
min = res[0];
secmin = res[1];
tree->data[i].weight = tree->data[min].weight + tree->data[secmin].weight;
tree->data[min].parent = i; //设置双亲结点
tree->data[secmin].parent = i;
tree->data[i].parent = 0;
tree->data[i].lchild = min; //设置孩子结点
tree->data[i].rchild = secmin;
tree->length++;
free(res);
}
}
void preorder(huffmantree* tree,int index)
{
if (index != -1)
{
printf("%c %d\n", tree->data[index].ch, tree->data[index].weight);
preorder(tree, tree->data[index].lchild);
preorder(tree, tree->data[index].rchild);
}
}
38行赋值一下
int minIndex=0, secminIndex=0;
有些地方没赋值好，我改了一下你的代码
望采纳谢谢啦#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
typedef struct TreeNode //定义树结点
{
int weight; //权值
int parent;
int lchild;
int rchild;
char ch;
}treenode;
typedef struct HuffmanTree //定义huffmantree，用数组表示树
{
treenode* data;
int length;
}huffmantree;
huffmantree* huffmantree_create(int weight[], int length, char character[])//huffmantree初始化
{
huffmantree* tree = (huffmantree*)malloc(sizeof(huffmantree));
tree->data = (treenode*)malloc(sizeof(treenode) * (2 * length - 1)); //n个元素，树中有2n-1个结点
tree->length = length;
for (int i = 0; i < length; i++)
{
tree->data[i].weight = weight[i];
tree->data[i].parent = 0;
tree->data[i].lchild = -1;
tree->data[i].rchild = -1;
tree->data[i].ch = character[i];
}
return tree;
}
int* selectMin(huffmantree* tree)//选择最小的两个结点
{
int min=10000, secmin=10000;
int minIndex=0, secminIndex=0;
for (int i = 0; i < tree->length; i++) //找到最小的结点的索引下标
{
if (tree->data[i].parent == 0)
{
if (tree->data[i].weight < min)
{
min = tree->data[i].weight;
minIndex = i;
}
}
}
for (int i = 0; i < tree->length; i++) //找到第二小的结点的索引下标
{
if (tree->data[i].parent == 0 && i != minIndex)
{
if (tree->data[i].weight < secmin)
{
secmin = tree->data[i].weight;
secminIndex = i;
}
}
}
int* res = (int*)malloc(sizeof(int) * 2); //返回两个数据，用int数组返回
res[0] = minIndex;
res[1] = secminIndex;
return res;
}
void createTree(huffmantree* tree) //建树
{
int min;
int secmin;
int* res;
for (int i = tree->length; i < tree->length * 2 - 1; i++)
{
res = selectMin(tree);
printf("%d %d\t", res[0], res[1]);
min = res[0];
secmin = res[1];
tree->data[i].weight = tree->data[min].weight + tree->data[secmin].weight;
tree->data[min].parent = i; //设置双亲结点
tree->data[secmin].parent = i;
tree->data[i].parent = 0;
tree->data[i].lchild = min; //设置孩子结点
tree->data[i].rchild = secmin;
tree->length++;
}
}
void preorder(huffmantree* tree,int index)
{
while (index != -1)
{
printf("%c %d\n", tree->data[index].ch, tree->data[index].weight);
preorder(tree, tree->data[index].lchild);
preorder(tree, tree->data[index].rchild);
}
}
int main()
{
FILE* fp;
char ch, str[100],character[100];
int length = 0, option, lengthchar = 0, weight[100];
fp = fopen("test3.txt", "r+");
if (fp == NULL)
{
printf("打开文件失败\n");
exit(0);
}
printf("打开文件成功\n");
ch = fgetc(fp);
while (ch != EOF)
{
str[length] = ch;
length++;
ch = fgetc(fp);
}
str[length] = '\0';
printf("该文件的数据为:");
puts(str);
printf("请问你是要对文件进行加密还是进行解密？(输入1为加密，输入2为解密)");
printf("我选择：");
scanf("%d", &option);
while (option != 1 && option != 2)
{
printf("你的输入有误，请重新输入！\n我选择：");
scanf("%d", &option);
}
if (option == 1) //对数据进行huffmantree编码
{
int status;
huffmantree* hftree;
for (int i = 0; i < length; i++) //先把str中的每一个字符都单列出来放进数组character
{
status = 0;
for (int t = 0; t < lengthchar; t++)
{
if (str[i] == character[t])
{
status = 1;
break;
}
}
if (status == 1)
continue;
character[lengthchar] = str[i];
lengthchar++;
}
character[lengthchar] = '\0';
printf("字符数组为:");
puts(character);
for (int i = 0; i < lengthchar; i++) //将权值数组归0
{
weight[i] = 0;
}
for (int i = 0; i < lengthchar; i++) //设置权值数组
{
for (int t = 0; t < length; t++)
{
if (str[t] == character[i]) //统计每个字符的出现次数
weight[i]++;
}
}
printf("权值数组为:");
for (int i = 0; i < lengthchar; i++)
printf("%d ", weight[i]);
printf("\n");
hftree = huffmantree_create(weight, lengthchar, character);
createTree(hftree);
preorder(hftree,hftree->length-1);
}
if (option == 2)//对huffmantree编码进行解码
{
}
fclose(fp);
return 0;
}