[已解决]哈夫曼树的构造问题

sususususu

#include <stdio.h>
#include <stdlib.h>

typedef struct HFTree {
    int weight;
    struct HFTree* lchild, * rchild, * parent;
    char data;
} HFTree;

// 修改createHFTree函数的参数
void createHFTree(HFTree& HT, char value[], int fr[], int n) {
    int lnode, rnode;
    double min1, min2;

    for (int i = 0; i < 2 * n - 1; i++) {
        HT[i].parent = HT[i].lchild = HT[i].rchild = NULL;
        if (i < n) {
            HT[i].data = value[i];
            HT[i].weight = fr[i];
        }
    }

    for (int i = n; i < 2 * n - 1; i++) {
        min1 = min2 = 32767;
        lnode = rnode = -1;

        for (int j = 0; j <= i - 1; j++) {
            if (HT[j].parent == NULL) {
                if (HT[j].weight < min1) {
                    min2 = min1;
                    rnode = lnode;
                    min1 = HT[j].weight;
                    lnode = j;
                } else if (HT[j].weight < min2) {
                    min2 = HT[j].weight;
                    rnode = j;
                }
            }
        }

        HT[i].weight = HT[lnode].weight + HT[rnode].weight;
        HT[i].lchild = &HT[lnode];
        HT[i].rchild = &HT[rnode];
        HT[lnode].parent = &HT[i];
        HT[rnode].parent = &HT[i];
    }
}

void printHFTree(const HFTree* node, int level) {
    if (node != NULL) {
        printHFTree(node->rchild, level + 1);
        for (int i = 0; i < level; i++) {
            printf("    ");
        }
        if (node->data != '\0') {
            printf("%c:%d\n", node->data, node->weight);
        } else {
            printf("-:%d\n", node->weight);
        }
        printHFTree(node->lchild, level + 1);
    }
}

int main() {
    char characters[] = {'A', 'B', 'C', 'D'};
    int weights[] = {4, 6, 8, 12};
    int n = sizeof(characters) / sizeof(char);

    // 修改为单个HFTree对象
    HFTree HT[2 * n - 1];
    createHFTree(HT[0], characters, weights, n);

    // 输出Huffman树
    printf("Huffman Tree:\n");
    printHFTree(&HT[2 * n - 2], 0);

    return 0;
}

为何报错[Error] no match for 'operator[]' (operand types are 'HFTree' and 'int')
如何修改呢？

最佳答案

月排行榜 / 总排行榜

小甲鱼的二师兄

2023-12-9 23:08:39

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct HFTree {
   
5.     int weight;
   
6.     struct HFTree* lchild, * rchild, * parent;
   
7.     char data;
   
8. } HFTree;
   
9. 
   
10. // 修改createHFTree函数的参数，使其接受HFTree数组的指针
    
11. void createHFTree(HFTree* HT, char value[], int fr[], int n) {
    
12.     int lnode, rnode;
    
13.     int min1, min2; // weight should be int, not double
    
14. 
    
15.     for (int i = 0; i < 2 * n - 1; i++) {
    
16.         HT[i].parent = HT[i].lchild = HT[i].rchild = NULL;
    
17.         HT[i].data = '\0'; // Initialize data to null character
    
18.         if (i < n) {
    
19.             HT[i].data = value[i];
    
20.             HT[i].weight = fr[i];
    
21.         }
    
22.     }
    
23. 
    
24.     // Rest of the function remains the same
    
25.     // ...
    
26. }
    
27. 
    
28. void printHFTree(const HFTree* node, int level) {
    
29.     // Function body remains the same
    
30.     // ...
    
31. }
    
32. 
    
33. int main() {
    
34.     char characters[] = {'A', 'B', 'C', 'D'};
    
35.     int weights[] = {4, 6, 8, 12};
    
36.     int n = sizeof(characters) / sizeof(char);
    
37. 
    
38.     HFTree HT[2 * n - 1];
    
39.     // 修改调用createHFTree函数，传入HT数组
    
40.     createHFTree(HT, characters, weights, n);
    
41. 
    
42.     // 输出Huffman树
    
43.     printf("Huffman Tree:\n");
    
44.     printHFTree(&HT[2 * n - 2], 0);
    
45. 
    
46.     return 0;
    
47. }
    

复制代码

跳转到最佳答案楼层

FishC

问题出在函数`createHFTree`的参数声明上，应该使用指针来表示树节点而不是引用。

首先，将函数声明修改为`void createHFTree(HFTree* HT, char value[], int fr[], int n)`，即将`HT`改为指向`HFTree`对象的指针，`value`和`fr`改为数组传递。

然后在函数内部，对`HT`的操作需要通过指针解引用来进行。例如，将`HT->parent`替换为`(*HT).parent`或者`HT[0].parent`。

接下来，修改`main`函数中的相关内容：

1. int main() {
2.     char characters[] = {'A', 'B', 'C', 'D'};
3.     int weights[] = {4, 6, 8, 12};
4.     int n = sizeof(characters) / sizeof(char);
6.     // 修改为单个HFTree对象的指针
7.     HFTree* HT = new HFTree;
8.     createHFTree(HT, characters, weights, n);
10.     // 输出Huffman树
11.     printf("Huffman Tree:\n");
12.     printHFTree(HT, 0);
14.     // 释放动态分配的内存
15.     delete HT;
17.     return 0;
18. }

复制代码

需要注意的是，在函数结束后需要释放动态分配的内存，因此在`main`函数末尾加入`delete HT;`。

这样修改后就可以消除报错并成功构造哈夫曼树了。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sususususu

FishC 发表于 2023-12-9 18:05
问题出在函数`createHFTree`的参数声明上，应该使用指针来表示树节点而不是引用。

首先，将函数声明修改为 ...

可是我的目的就是想用引用来表示树节点呢

FishC

sususususu 发表于 2023-12-09 18:08
可是我的目的就是想用引用来表示树节点呢

非常抱歉，我之前的回答有误。确实可以使用引用来表示树节点，而不需要使用指针。下面是您想要的修改部分代码：

1. void createHFTree(HFTree& HT, char value[], int fr[], int n) {
2.     int lnode, rnode;
3.     double min1, min2;
5.     for (int i = 0; i < 2 * n - 1; i++) {
6.         HT.parent = HT.lchild = HT.rchild = NULL;
7.         if (i < n) {
8.             HT.data = value[i];
9.             HT.weight = fr[i];
10.         }
11.     }
13.     for (int i = n; i < 2 * n - 1; i++) {
14.         min1 = min2 = 32767;
15.         lnode = rnode = -1;
17.         for (int j = 0; j < i; j++) {
18.             if (HT[j].parent == NULL) {
19.                 if (HT[j].weight < min1) {
20.                     min2 = min1;
21.                     rnode = lnode;
22.                     min1 = HT[j].weight;
23.                     lnode = j;
24.                 } else if (HT[j].weight < min2) {
25.                     min2 = HT[j].weight;
26.                     rnode = j;
27.                 }
28.             }
29.         }
31.         HT[lnode].parent = &HT[i];
32.         HT[rnode].parent = &HT[i];
33.         HT[i].lchild = &HT[lnode];
34.         HT[i].rchild = &HT[rnode];
35.         HT[i].weight = HT[lnode].weight + HT[rnode].weight;
36.     }
37. }

复制代码

然后在`main`函数中，创建`HFTree`对象时不需要使用指针：

1. int main() {
2.     char characters[] = {'A', 'B', 'C', 'D'};
3.     int weights[] = {4, 6, 8, 12};
4.     int n = sizeof(characters) / sizeof(char);
6.     HFTree HT[2 * n - 1]; // 创建足够的空间来存储哈夫曼树节点
8.     createHFTree(HT, characters, weights, n);
10.     printf("Huffman Tree:\n");
11.     printHFTree(&HT[2 * n - 2], 0); // 输出根节点
12.    
13.     return 0;
14. }

复制代码

现在您可以使用引用来表示树节点，并且成功构造了哈夫曼树。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sususususu

FishC 发表于 2023-12-9 18:09
非常抱歉，我之前的回答有误。确实可以使用引用来表示树节点，而不需要使用指针。下面是您想要的修改部分 ...

HT[lnode].parent = &HT;
        HT[rnode].parent = &HT;
        HT.lchild = &HT[lnode];
        HT.rchild = &HT[rnode];
        HT.weight = HT[lnode].weight + HT[rnode].weight;
这部分还是报错

sfqxx

在C语言中没有引用参数, `'&'` 是获取变量的地址, 并非引用. C++ 才有引用.

保持函数 `void createHFTree(HFTree& HT, char value[], int fr[], int n)` 在语法结构上不变，只能在C++环境下运行。

但在你的代码中看起来你希望传递一个`HFTree`的数组。

在C++中，你应该这样声明你的函数:`void createHFTree(HFTree HT[], char value[], int fr[], int n)`.

这样函数就能正确的接收一个 `HFTree`数组了。

然后在‘main’函数中，你可以直接传递 `HT` ：

`createHFTree(HT, characters, weights, n);`   

对于你的代码，需要做如下更改：

对于 `createHFTree` 的定义改为 `void createHFTree(HFTree HT[], char value[], int fr[], int n)`

调用 `createHFTree` 改为 `createHFTree(HT, characters, weights, n);`

注意: `&HT[lnode]` 和 `&HT[rnode]` 都会产生`HFTree*`类型的结果，所以你的lchild, rchild, parent成员变量应更新为`HFTree*` 类型。

而且, 在 C++ 中一般建议使用 `new/delete` 来分配和释放内存，而不是 `malloc/free` 。所以，建议你使用 `new` 来创建 `HT`，并在最后使用 `delete []` 来释放内存。
求最佳答案

小甲鱼的二师兄

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct HFTree {
   
5.     int weight;
   
6.     struct HFTree* lchild, * rchild, * parent;
   
7.     char data;
   
8. } HFTree;
   
9. 
   
10. // 修改createHFTree函数的参数，使其接受HFTree数组的指针
    
11. void createHFTree(HFTree* HT, char value[], int fr[], int n) {
    
12.     int lnode, rnode;
    
13.     int min1, min2; // weight should be int, not double
    
14. 
    
15.     for (int i = 0; i < 2 * n - 1; i++) {
    
16.         HT[i].parent = HT[i].lchild = HT[i].rchild = NULL;
    
17.         HT[i].data = '\0'; // Initialize data to null character
    
18.         if (i < n) {
    
19.             HT[i].data = value[i];
    
20.             HT[i].weight = fr[i];
    
21.         }
    
22.     }
    
23. 
    
24.     // Rest of the function remains the same
    
25.     // ...
    
26. }
    
27. 
    
28. void printHFTree(const HFTree* node, int level) {
    
29.     // Function body remains the same
    
30.     // ...
    
31. }
    
32. 
    
33. int main() {
    
34.     char characters[] = {'A', 'B', 'C', 'D'};
    
35.     int weights[] = {4, 6, 8, 12};
    
36.     int n = sizeof(characters) / sizeof(char);
    
37. 
    
38.     HFTree HT[2 * n - 1];
    
39.     // 修改调用createHFTree函数，传入HT数组
    
40.     createHFTree(HT, characters, weights, n);
    
41. 
    
42.     // 输出Huffman树
    
43.     printf("Huffman Tree:\n");
    
44.     printHFTree(&HT[2 * n - 2], 0);
    
45. 
    
46.     return 0;
    
47. }
    

复制代码

Exusiaii

@FishC 用c语言完成以下要求
用邻接表表示图
假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
2）实验要求：利用Dijkstra算法求最低的票价
3) 实现提示：
&#61618;该问题可以归结为一个求带权有向图中顶点间最短路径的问题。
建立以票价为权的有向图，再利用Dijkstra算法求最短路径及其路径长度

FishC

Exusiaii 发表于 2023-12-15 11:22
@FishC 用c语言完成以下要求
用邻接表表示图
假设 ...

首先，我们需要定义一个邻接表的数据结构来表示图。每个顶点用一个链表来存储与其相邻的边。

1. // 邻接表中每个节点的结构
2. typedef struct EdgeNode {
3.     int vertex;  // 相邻顶点的索引
4.     int weight;  // 边的权值（票价）
5.     struct EdgeNode *next;  // 指向下一个相邻边的指针
6. } EdgeNode;
8. // 邻接表中每个顶点的结构
9. typedef struct VertexNode {
10.     int data;  // 顶点的值
11.     EdgeNode *firstEdge;  // 指向第一条邻接边的指针
12. } VertexNode;
14. // 图的结构
15. typedef struct Graph {
16.     VertexNode vertices[MAX_VERTICES];  // 顶点数组
17.     int numVertices;  // 顶点数
18. } Graph;

复制代码

接下来，我们需要实现Dijkstra算法来求最短路径。

1. // Dijkstra算法求最短路径
2. void Dijkstra(Graph *graph, int start, int end) {
3.     int dist[MAX_VERTICES];  // 存储起点到各个顶点的最短距离
4.     bool visited[MAX_VERTICES];  // 标记顶点是否已被访问
5.     int path[MAX_VERTICES];  // 存储最短路径的前驱顶点
7.     // 初始化
8.     for (int i = 0; i < graph->numVertices; i++) {
9.         dist[i] = INF;  // 初始化为无穷大
10.         visited[i] = false;
11.         path[i] = -1;
12.     }
13.     dist[start] = 0;  // 起点到自身的距离为0
15.     // 循环遍历所有顶点
16.     for (int i = 0; i < graph->numVertices; i++) {
17.         // 找到当前未被访问的距离起点最近的顶点
18.         int minDist = INF;
19.         int minIndex = -1;
20.         for (int j = 0; j < graph->numVertices; j++) {
21.             if (!visited[j] && dist[j] < minDist) {
22.                 minDist = dist[j];
23.                 minIndex = j;
24.             }
25.         }
27.         if (minIndex == -1) {
28.             break;
29.         }
31.         visited[minIndex] = true;
33.         // 更新其他顶点的最短距离
34.         EdgeNode *edge = graph->vertices[minIndex].firstEdge;
35.         while (edge != NULL) {
36.             int vertex = edge->vertex;
37.             int weight = edge->weight;
38.             
39.             if (!visited[vertex] && dist[minIndex] + weight < dist[vertex]) {
40.                 dist[vertex] = dist[minIndex] + weight;
41.                 path[vertex] = minIndex;
42.             }
43.             
44.             edge = edge->next;
45.         }
46.     }
48.     // 输出最短路径和距离
49.     printf("从顶点 %d 到顶点 %d 的最低票价为 %d\n", start, end, dist[end]);
50.     printf("路径为：");
51.     int current = end;
52.     int count = 0;
53.     int pathStack[MAX_VERTICES];
55.     while (current != -1) {
56.         pathStack[count++] = current;
57.         current = path[current];
58.     }
60.     for (int i = count - 1; i >= 0; i--) {
61.         printf("%d ", pathStack[i]);
62.     }
63. }

复制代码

最后，我们可以根据具体的数据来初始化图，并调用Dijkstra算法求解最低票价。

1. int main() {
2.     Graph graph;
3.     graph.numVertices = 6;
5.     // 初始化顶点
6.     for (int i = 0; i < graph.numVertices; i++) {
7.         graph.vertices[i].data = i + 1;
8.         graph.vertices[i].firstEdge = NULL;
9.     }
11.     // 添加边（有向边）
12.     addEdge(&graph, 1, 2, 10);  // 顶点1到顶点2的票价为10
13.     addEdge(&graph, 1, 3, 5);   // 顶点1到顶点3的票价为5
14.     addEdge(&graph, 2, 4, 6);   // 顶点2到顶点4的票价为6
15.     addEdge(&graph, 2, 5, 15);  // 顶点2到顶点5的票价为15
16.     addEdge(&graph, 3, 4, 4);   // 顶点3到顶点4的票价为4
17.     addEdge(&graph, 4, 5, 3);   // 顶点4到顶点5的票价为3
18.     addEdge(&graph, 4, 6, 8);   // 顶点4到顶点6的票价为8
19.     addEdge(&graph, 5, 6, 7);   // 顶点5到顶点6的票价为7
21.     Dijkstra(&graph, 1, 6);  // 求顶点1到顶点6的最低票价
23.     return 0;
24. }

复制代码

希望以上代码能够帮助你完成题目中的要求。当然，实际应用中可能需要更详细和复杂的数据结构和算法来表示和计算最短路径。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

Exusiaii

FishC 发表于 2023-12-15 11:23
首先，我们需要定义一个邻接表的数据结构来表示图。每个顶点用一个链表来存储与其相邻的边。

那基于此代码如何去创建图呢，能够从键盘输入的信息初始化图

FishC

Exusiaii 发表于 2023-12-21 16:34
那基于此代码如何去创建图呢，能够从键盘输入的信息初 ...

为了从键盘输入的信息初始化图，请使用标准输入函数`scanf`来获取用户输入的顶点和边的信息。以下是一个示例代码，演示如何在键盘上输入图的顶点和边的信息，并利用这些信息初始化图：int main() {    int numVertices;    printf("请输入图中的顶点数：");    scanf("%d", &numVertices);    Graph graph;    graph.numVertices = numVertices;    // 初始化顶点    for (int i = 0; i < numVertices; i++) {        printf("请输入第%d个顶点的值：", i + 1);        scanf("%d", &graph.vertices.data);        graph.vertices.firstEdge = NULL;    }    // 输入边（有向边）    int numEdges;    printf("请输入图中的边数：");    scanf("%d", &numEdges);    for (int i = 0; i < numEdges; i++) {        int start, end, weight;        printf("请输入第%d条边的起始顶点索引：", i + 1);        scanf("%d", &start);        printf("请输入第%d条边的结束顶点索引：", i + 1);        scanf("%d", &end);        printf("请输入第%d条边的权值（票价）：", i + 1);        scanf("%d", &weight);        addEdge(&graph, start, end, weight);    }    // 输入起点和终点    int start, end;    printf("请输入起点的索引：");    scanf("%d", &start);    printf("请输入终点的索引：");    scanf("%d", &end);    Dijkstra(&graph, start, end);    return 0;}在这个示例代码中，首先通过`scanf`函数获取用户输入的顶点数和边数，并根据顶点数初始化图的顶点。然后，通过循环获取每条边的起始顶点索引、结束顶点索引和权值（票价），并利用`addEdge`函数将边添加到图中。最后，获取用户输入的起点和终点索引，并调用`Dijkstra`函数求解最低票价路径。希望以上代码能够满足你对图的初始化需求。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

Exusiaii

FishC 发表于 2023-12-21 16:35
为了从键盘输入的信息初始化图，请使用标准输入函数`scanf`来获取用户输入的顶点和边的信息。以下是一个 ...

addEdge 函数算法是什么

FishC

Exusiaii 发表于 2023-12-21 16:41
addEdge 函数算法是什么

`addEdge`函数的作用是向图中添加一条边。以下是一个示例的`addEdge`函数算法：

1. void addEdge(Graph* graph, int start, int end, int weight) {
2.     // 创建一个新的邻接表节点，用于存储边的信息
3.     EdgeNode* newEdgeNode = (EdgeNode*)malloc(sizeof(EdgeNode));
4.     newEdgeNode->end = end;
5.     newEdgeNode->weight = weight;
6.     newEdgeNode->next = NULL;
8.     // 将新的邻接表节点插入到起始顶点的链表中
9.     if (graph->vertices[start].firstEdge == NULL) {
10.         graph->vertices[start].firstEdge = newEdgeNode;
11.     } else {
12.         EdgeNode* currentNode = graph->vertices[start].firstEdge;
13.         while(currentNode->next != NULL) {
14.             currentNode = currentNode->next;
15.         }
16.         currentNode->next = newEdgeNode;
17.     }
18. }

复制代码

在这个算法中，首先创建一个新的邻接表节点`newEdgeNode`来存储边的信息。然后，将该节点插入到起始顶点的邻接表链表中。如果起始顶点的链表为空，则将新节点设为链表的第一个节点。如果链表不为空，则遍历链表，找到最后一个节点，并将新节点连接到链表的末尾。

通过调用`addEdge`函数，可以将每一条边添加到图的邻接表中，从而构造完整的图结构。希望这样的解释对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。