哈夫曼树
#include<stdio.h>#include<stdlib.h>
#include<string.h>
#define N 30
#define MAX 2*N-1
typedef struct HMtree
{
double weight;
char s;
int parent, rchild, lchild;
}HMtree,HM;
void select(HM ht, int x, int* m1, int* m2)//找出森林中全职最小的两个
{
double min1 = 999;
double min2 = 999;
int j;
for (j = 1; j <= x; j++)
{
if (ht.weight < min1 && ht.parent == 0)
{
min1 = ht.weight;
*m1 = j;
}
}
int k;
for (k = 1; k <= x; k++)
{
if (ht.weight < min2 && k != *m1 && ht.parent == 0)
{
min2 = ht.weight;
*m2 = k;
}
}
}
//构建哈夫曼树
void CreatHM(HM ht, int n)
{
int i;
for(i=n+1;i<=2*n-1;i++)
{
int m1, m2;
select(ht, i - 1, &m1, &m2);
ht.weight = ht.weight + ht.weight;
ht.lchild = m1;
ht.rchild = m2;
ht.parent = 0;
ht.parent = i;
ht.parent = i;
}
}
//哈夫曼编码
void HMcoding(HM ht, char** hc, int n)
{
char* cd = (char*)malloc(n * sizeof(char));
cd = '\0';
int now = 1;
int p = 0;
int start;
int i = 0;
while (i < n)
{
start = n - 1;
now = i + 1;
p = ht.parent;
while (p != 0)
{
start--;
if (ht.lchild == now)
{
cd = '0';
}
else {
cd = '1';
}
now = p;
p = ht.parent;
}
hc = (char*)malloc((n - start) * sizeof(char));
strcpy(hc, &cd);
i++;
}
}
//先序打印
void dayin(HM ht, char** hc, int index)
{
if (index >= 1)
{
if (ht.lchild == 0 && ht.rchild)
{
printf("%c:%s\n", ht.s, hc);
return;
}
dayin(ht, hc, ht.lchild);
dayin(ht, hc, ht.rchild);
}
}
//在生成的树里查找目标
void chaHM(HM ht, int n,char* pwd)
{
printf("original:");
int len = strlen(pwd);
int i = 0;
int node = 2 * n - 1;
while (i < len)
{
if (pwd == '0')
{
node = ht.lchild;
i++;
if (ht.lchild == 0 && ht.rchild == 0)
{
printf("%c", ht.s);
node = 2 * n - 1;
}
}
if (pwd == '1')
{
node = ht.rchild;
i++;
if (ht.lchild == 0 && ht.rchild == 0)
{
printf("%c", ht.s);
node = 2 * n - 1;
}
}
}
}
int main()
{
HM ht;
int n;//字符个数
scanf("%d", &n);
getchar();
char* hc;
int i;
for (i = 1; i <= n; i++)
{
scanf("%c%lf", &ht.s, &ht.weight);
getchar();
ht.lchild = 0;
ht.rchild = 0;
ht.parent = 0;
}
char pwd;
scanf("%s", pwd);
CreatHM(ht, n);
HMcoding(ht,hc,n);
dayin(ht, hc, 2 * n - 1);
chaHM(ht, n, pwd);
}
我的问题是为什么没有对应每个字符的编码的输出，是函数哪里出问题了吗？
您的代码中存在几个问题，可能导致没有对应每个字符的编码输出。以下是我发现的一些问题和相应的解决方案：
1. **`HMcoding`函数中的内存分配问题**：
在`HMcoding`函数中，您为`cd`分配了`n * sizeof(char)`大小的内存，但实际需要的内存应该是`n + 1`，因为字符串的结尾需要一个空字符`'\0'`。
```c
char* cd = (char*)malloc((n + 1) * sizeof(char)); // 修改这里
```
2. **`HMcoding`函数中的字符串复制问题**：
在复制编码到`hc`时，您应该使用`strncpy`来确保正确复制字符串，并且要设置目标字符串的结束符。
```c
strncpy(hc, &cd, n - start);
hc = '\0'; // 确保字符串正确结束
```
3. **`HMcoding`函数中的逻辑问题**：
您的`HMcoding`函数逻辑似乎有误。您应该从叶子节点开始构建编码，而不是从根节点开始。此外，您需要为每个字符分配一个编码，而不是只分配一个。
4. **`dayin`函数的实现问题**：
您的`dayin`函数似乎是想实现先序遍历打印哈夫曼树，但是实现有误。您需要一个递归函数来正确地打印每个节点的值和对应的编码。
5. **`chaHM`函数中的逻辑问题**：
在`chaHM`函数中，当找到叶子节点时，您应该继续打印字符，直到遍历完整个密码串。
6. **`main`函数中的`hc`数组初始化问题**：
您需要为`hc`数组的每个元素分配足够的内存，以存储可能的最长编码。
7. **`main`函数中的输入问题**：
在读取字符和权重后，您使用了`getchar()`来消耗换行符，这在某些情况下可能会导致问题。确保输入格式正确，并且`getchar()`的使用是恰当的。
8. **编码的打印**：
您需要在构建完哈夫曼树和编码后，打印出每个字符对应的编码。
本帖最后由 小甲鱼的二师兄 于 2025-1-17 19:04 编辑
主要问题出在 dayin 函数的实现中。
在判断叶子节点时存在逻辑错误，导致没有正确打印字符的编码。
修复后的完整代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 30
#define MAX 2 * N - 1
typedef struct HMtree {
double weight;
char s;
int parent, rchild, lchild;
} HMtree, HM;
void selectMin(HM ht, int x, int* m1, int* m2) {
double min1 = 999;
double min2 = 999;
int j;
for (j = 1; j <= x; j++) {
if (ht.weight < min1 && ht.parent == 0) {
min1 = ht.weight;
*m1 = j;
}
}
int k;
for (k = 1; k <= x; k++) {
if (ht.weight < min2 && k != *m1 && ht.parent == 0) {
min2 = ht.weight;
*m2 = k;
}
}
}
// 构建哈夫曼树
void CreatHM(HM ht, int n) {
int i;
for (i = n + 1; i <= 2 * n - 1; i++) {
int m1, m2;
selectMin(ht, i - 1, &m1, &m2);
ht.weight = ht.weight + ht.weight;
ht.lchild = m1;
ht.rchild = m2;
ht.parent = 0;
ht.parent = i;
ht.parent = i;
}
}
// 哈夫曼编码
void HMcoding(HM ht, char** hc, int n) {
char* cd = (char*)malloc(n * sizeof(char));
cd = '\0';
int now = 1;
int p = 0;
int start;
int i = 0;
while (i < n) {
start = n - 1;
now = i + 1;
p = ht.parent;
while (p != 0) {
start--;
if (ht.lchild == now) {
cd = '0';
} else {
cd = '1';
}
now = p;
p = ht.parent;
}
hc = (char*)malloc((n - start + 1) * sizeof(char)); // 改为从 0 开始
strcpy(hc, &cd);
i++;
}
free(cd);
}
// 先序打印
void dayin(HM ht, char** hc, int index) {
if (index >= 1) {
if (ht.lchild == 0 && ht.rchild == 0) { // 叶子节点
printf("%c:%s\n", ht.s, hc); // 索引从 0 开始
return;
}
// 遍历左子树
dayin(ht, hc, ht.lchild);
// 遍历右子树
dayin(ht, hc, ht.rchild);
}
}
// 在生成的树里查找目标
void chaHM(HM ht, int n, char* pwd) {
printf("original:");
int len = strlen(pwd);
int i = 0;
int node = 2 * n - 1;
while (i < len) {
if (pwd == '0') {
node = ht.lchild;
i++;
if (ht.lchild == 0 && ht.rchild == 0) { // 到达叶子节点
printf("%c", ht.s);
node = 2 * n - 1;
}
} else if (pwd == '1') {
node = ht.rchild;
i++;
if (ht.lchild == 0 && ht.rchild == 0) { // 到达叶子节点
printf("%c", ht.s);
node = 2 * n - 1;
}
} else { // 非法输入
printf("\nError: Invalid character in encoded string.\n");
return;
}
}
printf("\n");
}
int main() {
HM ht;
int n; // 字符个数
printf("Enter the number of characters:\n");
scanf("%d", &n);
getchar();
char* hc; // 动态调整大小，索引从 0 开始
int i;
printf("Enter characters and their weights (format: <char> <weight>):\n");
for (i = 1; i <= n; i++) {
scanf("%c %lf", &ht.s, &ht.weight);
getchar();
ht.lchild = 0;
ht.rchild = 0;
ht.parent = 0;
}
char pwd;
printf("Enter the encoded string:\n");
scanf("%s", pwd);
CreatHM(ht, n);
HMcoding(ht, hc, n);
printf("Huffman Codes:\n");
dayin(ht, hc, 2 * n - 1);
chaHM(ht, n, pwd);
// 释放动态分配的内存
for (i = 0; i < n; i++) {
free(hc);
}
return 0;
}
页:
[1]