用c语言实现哈佛曼树的建立算法
即输入一个有n个叶结点的权值构造一棵哈夫曼树；（例如：n=8，权值为 5 297814 23319)
(1） 要求程序能够显示出哈夫曼树的构造过程，即每一步选出的两个最小值是谁，以他们做为左右子树构造一棵新的哈夫曼树之后，显示当前还有哪些权值。
(2） 程序要有良好的用户界面，且以与用户交互的方式运行。
实现哈夫曼算法的数据类型定义：
结点应存储四种信息：结点的权值、左右子树地址、及双亲结点地址
附上代码示例，望采纳。
#include <stdio.h>
#include <stdlib.h>
// 结点结构体
typedef struct Node {
int weight; // 权重
struct Node *left; // 左子树
struct Node *right; // 右子树
struct Node *parent; // 父结点
} Node;
// 创建叶子结点
Node* createLeaf(int weight) {
Node* leaf = (Node*)malloc(sizeof(Node));
leaf->weight = weight;
leaf->left = leaf->right = NULL;
return leaf;
}
// 选择最小的两个结点
void selectMin(Node* leaves[], int n, Node** first, Node** second) {
*first = *second = NULL;
for (int i = 0; i < n; i++) {
if (!*first || leaves[i]->weight < (*first)->weight)
*first = leaves[i];
}
for (int i = 0; i < n; i++) {
if (leaves[i] != *first && (!*second || leaves[i]->weight < (*second)->weight))
*second = leaves[i];
}
}
// 创建哈夫曼树
Node* createHuffman(int weights[], int n) {
Node* leaves[n];
for (int i = 0; i < n; i++) leaves[i] = createLeaf(weights[i]);
while (n > 1) {
Node *first, *second;
selectMin(leaves, n, &first, &second); //选择最小的两个结点
Node* parent = (Node*)malloc(sizeof(Node)); // 创建父结点
parent->left = first;
first->parent = parent;
parent->right = second;
second->parent = parent;
parent->weight = first->weight + second->weight;
// 更新leaves[]和n
for (int i = 0; i < n; i++) {
if (leaves[i] == first || leaves[i] == second) {
leaves[i] = parent;
break;
}
}
n--;
// 显示当前步骤选出的结点和剩余的结点
printf("选出%d和%d,构造父结点%d,剩余:", first->weight, second->weight, parent->weight);
for (int i = 0; i < n; i++) printf("%d ", leaves[i]->weight);
printf("\n");
}
return leaves[0];
}
int main() {
int weights[] = {5, 29, 7, 8, 14, 2, 13, 3, 19};
Node* huffman = createHuffman(weights, 9);
// 显示哈夫曼树的构造过程...
}
- 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/355884
- 这篇博客也不错, 你可以看下C语言中阶第四篇：分支与循环语句练习，求阶乘的多种方法（两层for循环求阶乘）、二分查找、字符串汇聚以及模拟用户登录
- 除此之外, 这篇博客: 数字三角形 给定一个由n行数字组成的数字三角形，试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大（每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数）。中的 给定一个由n行数字组成的数字三角形，试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大（每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数）。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
题目：
问题：
给定一个由n行数字组成的数字三角形，如下图所示：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大（每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数）。
输入：
第一行是数字三角形的行数，接下来 n 行是数字三角形中的数字。
比如：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出：
输出这个最大值。
这里只给出代码，步骤分析看链接：步骤详解代码实现：
代码注释的部分构成方法二#include<stdio.h> #include<math.h> #include <windows.h> #define N 5 int a[6][6]; int sum[6][6]; int sum_two[6]; int main() { int i,j; for (i=1;i<=5;i++) for (j=1;j<=i;j++) scanf("%d",&a[i][j]); for (i=1;i<6;i++) { sum[5][i] = a[5][i]; // sum_two[i] = a[5][i]; } for (i=5-1;i>=1;i--) for (j=1;j<=i;j++) { sum[i][j] = max(sum[i+1][j],sum[i+1][j+1]) + a[i][j]; //sum_two[j] = a[i][j] + max(sum_two[j],sum_two[j+1]); } for (i=1;i<6;i++) { for (j=1;j<=i;j++) printf("%3d",sum[i][j]); printf("\n"); } //printf("%d",sum_two[1]); return 0; }
回答部分参考、引用ChatGpt以便为您提供更准确的答案：
要解决这个问题，您可以在前端代码中使用绝对路径来引用后端返回的文件地址。具体的解决方案如下：
- 在前端代码中，将文件的URL地址设置为绝对路径，并指定后端的地址。例如：
// 假设后端返回的文件地址是 /media/aaa.pdf
const fileUrl = 'http://127.0.0.1:8000/media/aaa.pdf';
- 在前端页面中，使用该绝对路径来引用文件。例如，在Vue模板中使用
<a>标签展示链接：
<a :href="fileUrl" target="_blank">点击查看文件</a>
- 当前端运行时，浏览器会根据绝对路径
http://127.0.0.1:8000/media/aaa.pdf访问后端，并正确获取到文件内容。
通过以上步骤，您可以解决前端中引用后端文件时路径不正确的问题，确保能够正确访问到文件。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
typedef struct {
int weight;
int parent;
int left;
int right;
} Node;
Node* create_node(int weight) {
Node* node = (Node*)malloc(sizeof(Node));
node->weight = weight;
node->parent = -1;
node->left = -1;
node->right = -1;
return node;
}
void print_tree(Node* root, int level) {
if (root == NULL) return;
printf(" ");
for (int i = 0; i < level; i++) printf("--");
printf(" [%d] ", root->weight);
if (root->left != -1) print_tree(root->left, level + 1);
if (root->right != -1) print_tree(root->right, level + 1);
}
void find_min(Node** min, Node** node, int* count) {
int left = *count;
int right = *count + left + 1;
int min_index = left;
int min_weight = node[left]->weight;
int i;
for (i = left + 1; i <= right; i++) {
if (node[i]->weight < min_weight) {
min_index = i;
min_weight = node[i]->weight;
}
}
(*min) = node[min_index];
(*node) = node[left];
(*count) = left;
}
void build_tree(Node** tree, int* count, int n) {
Node* root = NULL;
Node* current = NULL;
Node* next = NULL;
int i;
for (i = n; i > *count; i--) find_min(&root, ¤t, count); // Find the minimum value and its parent node.
(*count)++; // Increase the count by one to point to the next value.
if ((*count) == n) return; // If there are no more values to process, return.
(*tree) = create_node(current->weight); // Create a new node with the current value's weight as its weight.
(*tree)->parent = current->parent; // Set the parent of the new node to the current value's parent.
(*tree)->left = current->left; // Set the left child of the new node to the current value's left child.
(*tree)->right = current->right; // Set the right child of the new node to the current value's right child.
(*count)++; // Increase the count by one to point to the next value.
build_tree(&next, count, n); // Recursively call this function to process the remaining values.
}
int main() {
int n, w[8], p[8], l[8], r[8]; // Arrays to store weights, parents, left children, and right children of each leaf node.
Node* tree = NULL; // Root of the binary heap.
Node* current = NULL; // Current node being processed.
Node* next = NULL; // Next node to be processed.
int count = 0; // Count of nodes in the heap.
pid_t child_pid; // Process ID of the child process.
int status; // Status of the child process.
FILE* input = fopen("input.txt", "r"); // Open input file for reading weights.
FILE* output = fopen("output.txt", "w"); // Open output file for writing tree structure.
fscanf(input, "%d", &n); // Read number of leaves from input file.
fscanf(input, "%d", &w[0]); // Read first leaf's weight from input file.
p[0] = w[0]; // Store first leaf's weight as its parent weight.
l[0] = w[0]; // Store first leaf's weight as its left child weight.
r[0] = w[0]; // Store first leaf's weight as its right child weight.
fscanf(input, "%d", &w[1]); // Read second leaf's weight from input file.
p[1] = w[1]; // Store second leaf's weight as its parent weight.
l[1] = w[1]; // Store second leaf's weight as its left child weight.
r[1] = w[1]; // Store second leaf's weight as its right child weight.
以下是用C语言实现哈夫曼树的建立算法的示例代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX_LEAF_NODE 100
typedef struct Node {
int weight;
int parent;
int left_child;
int right_child;
} Node;
void select_min_two(Node *nodes, int n, int *min1, int *min2) {
int i;
*min1 = -1;
*min2 = -1;
for (i = 0; i < n; i++) {
if (nodes[i].parent == -1) {
if (*min1 == -1 || nodes[i].weight < nodes[*min1].weight) {
*min2 = *min1;
*min1 = i;
} else if (*min2 == -1 || nodes[i].weight < nodes[*min2].weight) {
*min2 = i;
}
}
}
}
void build_huffman_tree(Node *nodes, int n) {
int i, min1, min2;
for (i = n; i < 2 * n - 1; i++) {
select_min_two(nodes, i, &min1, &min2);
nodes[min1].parent = i;
nodes[min2].parent = i;
nodes[i].left_child = min1;
nodes[i].right_child = min2;
nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
printf("Step %d: select %d and %d, merge to %d, weight=%d\n", i - n + 1, min1, min2, i, nodes[i].weight);
}
}
void print_huffman_tree(Node *nodes, int n) {
int i;
printf("Huffman tree:\n");
for (i = 0; i < 2 * n - 1; i++) {
printf("Node %d: weight=%d, parent=%d, left_child=%d, right_child=%d\n", i, nodes[i].weight, nodes[i].parent, nodes[i].left_child, nodes[i].right_child);
}
}
int main() {
int n = 8;
int weights[] = {5, 297814, 23319};
Node nodes[MAX_LEAF_NODE * 2 - 1];
int i;
for (i = 0; i < n; i++) {
nodes[i].weight = weights[i];
nodes[i].parent = -1;
nodes[i].left_child = -1;
nodes[i].right_child = -1;
}
build_huffman_tree(nodes, n);
print_huffman_tree(nodes, n);
return 0;
}
该代码中，我们使用Node结构体存储哈夫曼树的结点信息，包括权值、左右子树地址和双亲结点地址。在build_huffman_tree函数中，我们使用select_min_two函数选择权值最小的两个结点，并将它们合并成一个新的结点，并更新哈夫曼树的结构。在每一步合并操作完成后，我们都会打印出当前的步骤和合并的结点信息。在print_huffman_tree函数中，我们打印出整棵哈夫曼树的结点信息。
你可以将该代码复制到一个C文件中，然后使用编译器进行编译和运行。以下是用C语言实现哈夫曼树的建立算法的示例代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX_LEAF_NODE 100
typedef struct Node {
int weight;
int parent;
int left_child;
int right_child;
} Node;
void select_min_two(Node *nodes, int n, int *min1, int *min2) {
int i;
*min1 = -1;
*min2 = -1;
for (i = 0; i < n; i++) {
if (nodes[i].parent == -1) {
if (*min1 == -1 || nodes[i].weight < nodes[*min1].weight) {
*min2 = *min1;
*min1 = i;
} else if (*min2 == -1 || nodes[i].weight < nodes[*min2].weight) {
*min2 = i;
}
}
}
}
void build_huffman_tree(Node *nodes, int n) {
int i, min1, min2;
for (i = n; i < 2 * n - 1; i++) {
select_min_two(nodes, i, &min1, &min2);
nodes[min1].parent = i;
nodes[min2].parent = i;
nodes[i].left_child = min1;
nodes[i].right_child = min2;
nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
printf("Step %d: select %d and %d, merge to %d, weight=%d\n", i - n + 1, min1, min2, i, nodes[i].weight);
}
}
void print_huffman_tree(Node *nodes, int n) {
int i;
printf("Huffman tree:\n");
for (i = 0; i < 2 * n - 1; i++) {
printf("Node %d: weight=%d, parent=%d, left_child=%d, right_child=%d\n", i, nodes[i].weight, nodes[i].parent, nodes[i].left_child, nodes[i].right_child);
}
}
int main() {
int n = 8;
int weights[] = {5, 297814, 23319};
Node nodes[MAX_LEAF_NODE * 2 - 1];
int i;
for (i = 0; i < n; i++) {
nodes[i].weight = weights[i];
nodes[i].parent = -1;
nodes[i].left_child = -1;
nodes[i].right_child = -1;
}
build_huffman_tree(nodes, n);
print_huffman_tree(nodes, n);
return 0;
}
该代码中，我们使用Node结构体存储哈夫曼树的结点信息，包括权值、左右子树地址和双亲结点地址。在build_huffman_tree函数中，我们使用select_min_two函数选择权值最小的两个结点，并将它们合并成一个新的结点，并更新哈夫曼树的结构。在每一步合并操作完成后，我们都会打印出当前的步骤和合并的结点信息。在print_huffman_tree函数中，我们打印出整棵哈夫曼树的结点信息。
你可以将该代码复制到一个C文件中，然后使用编译器进行编译和运行。
运行结果：
Input n: 8
Input 8 weights: 5 29 7 8 14 2 33 19
sorted nodes: 2 5 7 8 14 19 29 33
new node 8: 7 (2, 5)
new node 9: 14 (7, 7)
new node 10: 22 (8, 14)
new node 11: 33 (14, 19)
new node 12: 51 (22, 29)
new node 13: 66 (33, 33)
new node 14: 117 (51, 66)
源代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 哈夫曼树结点
typedef struct huffman_node huffman_node_t;
struct huffman_node {
int id; // 结点id
int weight; // 权重
huffman_node_t *parent; // 父结点
huffman_node_t *lchild; // 左孩子
huffman_node_t *rchild; // 右孩子
huffman_node_t *next; // 下一个结点, 用于单链表排序
};
// 结点数组
static huffman_node_t *node_arr = NULL;
static int last_free_node = 0;
// 加一个节点到单链表中
huffman_node_t *push(huffman_node_t *head, huffman_node_t *node)
{
huffman_node_t *p = head;
node->next = NULL;
if (p == NULL) {
return node;
}
if (node->weight < p->weight) {
node->next = p;
return node;
}
while (p->next != NULL) {
if (node->weight < p->next->weight) {
node->next = p->next;
p->next = node;
return head;
}
p = p->next;
}
p->next = node;
return head;
}
// 从node_arr中获取一个新结点
huffman_node_t *new_node(int weight)
{
huffman_node_t *node = &node_arr[last_free_node];
node->id = last_free_node;
last_free_node++;
node->weight = weight;
node->parent = NULL;
node->lchild = NULL;
node->rchild = NULL;
node->next = NULL;
return node;
}
// 建立哈夫曼树, 输入排序链表, 返回哈夫曼树根结点
huffman_node_t *huffman_tree(huffman_node_t *head)
{
huffman_node_t *sort_head = head;
huffman_node_t *node1, *node2;
huffman_node_t *cur_node;
while (NULL != sort_head && NULL != sort_head->next) {
node1 = sort_head;
node2 = sort_head->next;
sort_head = node2->next;
// 生成新结点
cur_node = new_node(node1->weight + node2->weight);
cur_node->lchild = node1;
cur_node->rchild = node2;
node1->parent = cur_node;
node2->parent = cur_node;
printf("new node %d: %d (%d, %d)\n", cur_node->id, cur_node->weight, node1->weight, node2->weight);
// 插入排序链表
sort_head = push(sort_head, cur_node);
}
return sort_head;
}
// 主程序
int main(void)
{
int n;
int weight;
int i;
huffman_node_t *node;
huffman_node_t *head = NULL;
// 输入结点数n
printf("Input n: ");
scanf("%d", &n);
// 输入n个结点的权重
node_arr = (huffman_node_t *)malloc(sizeof(huffman_node_t) * n * 2);
printf("Input %d weights: ", n);
for (i = 0; i < n; ++i) {
scanf("%d", &weight);
node = new_node(weight);
head = push(head, node);
}
printf("sorted nodes: ");
node = head;
while (NULL != node) {
printf("%d ", node->weight);
node = node->next;
}
printf("\n");
// 建立哈夫曼树
node = huffman_tree(head);
return 0;
}
用 C 语言实现哈夫曼树的建立算法的代码示例，可以根据输入的叶子节点权值构造哈夫曼树，并显示构造的过程以及当前还有哪些权值。算法的实现过程中，定义了结点类型 Node，用于存储结点的权值、左右子树地址和双亲结点地址。然后通过堆排序的方式，将叶子节点权值从小到大排序，并依次选出两个权值最小的叶子节点，将它们作为新结点的左右子树，构造新的哈夫曼树。最终返回哈夫曼树的根节点。
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int weight; // 权值
struct node *left, *right, *parent; // 左右子树地址及双亲结点地址
} Node;
// 创建新结点
Node* createNode(int weight) {
Node *node = (Node*)malloc(sizeof(Node));
node->weight = weight;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return node;
}
// 交换两个结点
void swap(Node **a, Node **b) {
Node *tmp = *a;
*a = *b;
*b = tmp;
}
// 对结点数组进行堆排序（小根堆）
void heapSort(Node **nodes, int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
int min = i;
int left = i * 2 + 1;
int right = i * 2 + 2;
if (left < n && nodes[left]->weight < nodes[min]->weight) {
min = left;
}
if (right < n && nodes[right]->weight < nodes[min]->weight) {
min = right;
}
if (min != i) {
swap(&nodes[i], &nodes[min]);
}
}
for (int i = n - 1; i > 0; i--) {
swap(&nodes[0], &nodes[i]);
int min = 0;
int left = 1;
int right = 2;
while (left < i) {
if (right < i && nodes[right]->weight < nodes[left]->weight) {
if (nodes[right]->weight < nodes[min]->weight) {
min = right;
}
printf("选出权值为%d的结点和权值为%d的结点作为新结点的左右子树，构造新结点的权值为%d\n", nodes[right]->weight, nodes[min]->weight, nodes[right]->weight + nodes[min]->weight);
} else {
if (nodes[left]->weight < nodes[min]->weight) {
min = left;
}
printf("选出权值为%d的结点和权值为%d的结点作为新结点的左右子树，构造新结点的权值为%d\n", nodes[left]->weight, nodes[min]->weight, nodes[left]->weight + nodes[min]->weight);
}
left = min * 2 + 1;
right = min * 2 + 2;
}
}
}
// 构造哈夫曼树
Node* buildHuffmanTree(int *weights, int n) {
Node **nodes = (Node**)malloc(sizeof(Node*) * n);
for (int i = 0; i < n; i++) {
nodes[i] = createNode(weights[i]);
}
heapSort(nodes, n);
Node *root = NULL;
while (n > 1) {
Node *left = nodes[0];
Node *right = nodes[1];
Node *parent = createNode(left->weight + right->weight);
parent->left = left;
parent->right = right;
left->parent = parent;
right->parent = parent;
nodes[0] = parent;
nodes[1] = nodes[n - 1];
n--;
heapSort(nodes, n);
root = parent;
}
free(nodes);
return root;
}
// 打印哈夫曼树
void printHuffmanTree(Node *root) {
if (root != NULL) {
printf("%d", root->weight);
if (root->left != NULL || root->right != NULL) {
printf("(");
printHuffmanTree(root->left);
if (root->right != NULL) {
printf(",");
}
printHuffmanTree(root->right);
printf(")");
}
}
}
// 释放哈夫曼树的内存
void freeHuffmanTree(Node *root) {
if (root != NULL) {
freeHuffmanTree(root->left);
freeHuffmanTree(root->right);
free(root);
}
}
int main() {
int n = 8;
int weights[] = {5, 297814, 23319, 1234, 5678, 91011, 121314, 151617};
Node *root = buildHuffmanTree(weights, n);
printf("构造出的哈夫曼树为：\n");
printHuffmanTree(root);
printf("\n");
freeHuffmanTree(root);
return 0;
}
用c语言实现哈佛曼树的建立算法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef double DataType; //结点权值的数据类型
typedef struct HTNode //单个结点的信息
{
DataType weight; //权值
int parent; //父节点
int lc, rc; //左右孩子
}*HuffmanTree;
typedef char **HuffmanCode; //字符指针数组中存储的元素类型
//在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1的权值小于s2的权值
void Select(HuffmanTree& HT, int n, int& s1, int& s2)
{
int min;
//找第一个最小值
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0)
{
min = i;
break;
}
}
for (int i = min + 1; i <= n; i++)
{
if (HT[i].parent == 0 && HT[i].weight < HT[min].weight)
min = i;
}
s1 = min; //第一个最小值给s1
//找第二个最小值
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0 && i != s1)
{
min = i;
break;
}
}
for (int i = min + 1; i <= n; i++)
{
if (HT[i].parent == 0 && HT[i].weight < HT[min].weight&&i != s1)
min = i;
}
s2 = min; //第二个最小值给s2
}
//构建哈夫曼树
void CreateHuff(HuffmanTree& HT, DataType* w, int n)
{
int m = 2 * n - 1; //哈夫曼树总结点数
HT = (HuffmanTree)calloc(m + 1, sizeof(HTNode)); //开m+1个HTNode，因为下标为0的HTNode不存储数据
for (int i = 1; i <= n; i++)
{
HT[i].weight = w[i - 1]; //赋权值给n个叶子结点
}
for (int i = n + 1; i <= m; i++) //构建哈夫曼树
{
//选择权值最小的s1和s2，生成它们的父结点
int s1, s2;
Select(HT, i - 1, s1, s2); //在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1的权值小于s2的权值
HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权重是s1和s2的权重之和
HT[s1].parent = i; //s1的父亲是i
HT[s2].parent = i; //s2的父亲是i
HT[i].lc = s1; //左孩子是s1
HT[i].rc = s2; //右孩子是s2
}
//打印哈夫曼树中各结点之间的关系
printf("哈夫曼树为:>\n");
printf("下标 权值 父结点 左孩子 右孩子\n");
printf("0 \n");
for (int i = 1; i <= m; i++)
{
printf("%-4d %-6.2lf %-6d %-6d %-6d\n", i, HT[i].weight, HT[i].parent, HT[i].lc, HT[i].rc);
}
printf("\n");
}
//生成哈夫曼编码
void HuffCoding(HuffmanTree& HT, HuffmanCode& HC, int n)
{
HC = (HuffmanCode)malloc(sizeof(char*)*(n + 1)); //开n+1个空间，因为下标为0的空间不用
char* code = (char*)malloc(sizeof(char)*n); //辅助空间，编码最长为n(最长时，前n-1个用于存储数据，最后1个用于存放'\0')
code[n - 1] = '\0'; //辅助空间最后一个位置为'\0'
for (int i = 1; i <= n; i++)
{
int start = n - 1; //每次生成数据的哈夫曼编码之前，先将start指针指向'\0'
int c = i; //正在进行的第i个数据的编码
int p = HT[c].parent; //找到该数据的父结点
while (p) //直到父结点为0，即父结点为根结点时，停止
{
if (HT[p].lc == c) //如果该结点是其父结点的左孩子，则编码为0，否则为1
code[--start] = '0';
else
code[--start] = '1';
c = p; //继续往上进行编码
p = HT[c].parent; //c的父结点
}
HC[i] = (char*)malloc(sizeof(char)*(n - start)); //开辟用于存储编码的内存空间
strcpy(HC[i], &code[start]); //将编码拷贝到字符指针数组中的相应位置
}
free(code); //释放辅助空间
}
//主函数
int main()
{
int n = 0;
printf("请输入数据个数:>");
scanf("%d", &n);
DataType* w = (DataType*)malloc(sizeof(DataType)*n);
if (w == NULL)
{
printf("malloc fail\n");
exit(-1);
}
printf("请输入数据:>");
for (int i = 0; i < n; i++)
{
scanf("%lf", &w[i]);
}
HuffmanTree HT;
CreateHuff(HT, w, n); //构建哈夫曼树
HuffmanCode HC;
HuffCoding(HT, HC, n); //构建哈夫曼编码
for (int i = 1; i <= n; i++) //打印哈夫曼编码
{
printf("数据%.2lf的编码为:%s\n", HT[i].weight, HC[i]);
}
free(w);
return 0;
}
以下是使用C语言实现哈夫曼树建立算法的示例代码：
#include <stdio.h>
#include <stdlib.h>
// 定义哈夫曼树的结点结构
typedef struct Node {
int weight;
struct Node* left;
struct Node* right;
struct Node* parent;
} Node;
// 创建一个新的哈夫曼树结点
Node* createNode(int weight) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->weight = weight;
newNode->left = NULL;
newNode->right = NULL;
newNode->parent = NULL;
return newNode;
}
// 构建哈夫曼树
Node* buildHuffmanTree(int weights[], int n) {
// 创建n个叶子结点
Node** nodes = (Node**)malloc(n * sizeof(Node*));
for (int i = 0; i < n; i++) {
nodes[i] = createNode(weights[i]);
}
// 构建哈夫曼树
while (n > 1) {
// 找到权值最小的两个结点
int min1 = 0, min2 = 1;
if (nodes[min1]->weight > nodes[min2]->weight) {
int temp = min1;
min1 = min2;
min2 = temp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
// 创建新结点，将最小的两个结点作为左右子树
Node* newNode = createNode(nodes[min1]->weight + nodes[min2]->weight);
newNode->left = nodes[min1];
newNode->right = nodes[min2];
nodes[min1]->parent = newNode;
nodes[min2]->parent = newNode;
// 将新结点加入到结点数组中
nodes[min1] = newNode;
nodes[min2] = nodes[n - 1];
n--;
}
// 返回根结点
return nodes[0];
}
// 打印哈夫曼树的构造过程
void printHuffmanTree(Node* root) {
if (root == NULL) {
return;
}
printf("Weight: %d", root->weight);
if (root->parent != NULL) {
printf(", Parent: %d", root->parent->weight);
}
if (root->left != NULL) {
printf(", Left Child: %d", root->left->weight);
}
if (root->right != NULL) {
printf(", Right Child: %d", root->right->weight);
}
printf("\n");
printHuffmanTree(root->left);
printHuffmanTree(root->right);
}
int main() {
int weights[] = {5, 297814, 23319};
int n = sizeof(weights) / sizeof(weights[0]);
Node* root = buildHuffmanTree(weights, n);
printHuffmanTree(root);
return 0;
}
这段代码首先定义了一个哈夫曼树的结点结构，包括权值、左右子树地址和双亲结点地址。然后，通过createNode函数创建一个新的哈夫曼树结点。接下来，使用buildHuffmanTree函数根据给定的权值数组构建哈夫曼树。最后，使用printHuffmanTree函数打印哈夫曼树的构造过程。
在main函数中，我们给定了一个权值数组weights，并计算出数组的大小n。然后，调用buildHuffmanTree函数构建哈夫曼树，并将返回的根结点赋给root。最后，调用printHuffmanTree函数打印哈夫曼树的构造过程。
你可以根据自己的需求修改权值数组，并根据需要添加其他功能来满足题目的要求。
参考GPT：
#include <stdio.h>
#include <stdlib.h>
// 哈夫曼树结点定义
typedef struct Node {
int weight;
struct Node* left;
struct Node* right;
struct Node* parent;
} Node;
// 创建哈夫曼树
Node* createHuffmanTree(int* weights, int n) {
Node** nodes = (Node**)malloc(n * sizeof(Node*));
// 创建叶结点
for (int i = 0; i < n; i++) {
nodes[i] = (Node*)malloc(sizeof(Node));
nodes[i]->weight = weights[i];
nodes[i]->left = NULL;
nodes[i]->right = NULL;
nodes[i]->parent = NULL;
}
// 构造哈夫曼树
while (n > 1) {
int min1 = 0;
int min2 = 1;
// 找到权值最小的两个结点
if (nodes[min1]->weight > nodes[min2]->weight) {
int temp = min1;
min1 = min2;
min2 = temp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
// 创建新结点
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->weight = nodes[min1]->weight + nodes[min2]->weight;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
newNode->parent = NULL;
// 更新父结点
nodes[min1]->parent = newNode;
nodes[min2]->parent = newNode;
// 删除已合并的结点
nodes[min1] = newNode;
nodes[min2] = nodes[n - 1];
n--;
}
Node* huffmanTree = nodes[0];
free(nodes);
return huffmanTree;
}
// 打印哈夫曼树
void printHuffmanTree(Node* root) {
if (root == NULL) {
return;
}
printf("Weight: %d", root->weight);
if (root->parent != NULL) {
printf(", Parent: %d", root->parent->weight);
}
if (root->left != NULL) {
printf(", Left: %d", root->left->weight);
}
if (root->right != NULL) {
printf(", Right: %d", root->right->weight);
}
printf("\n");
printHuffmanTree(root->left);
printHuffmanTree(root->right);
}
int main() {
int n;
printf("Enter the number of leaf nodes: ");
scanf("%d", &n);
int* weights = (int*)malloc(n * sizeof(int));
printf("Enter the weights of leaf nodes: ");
for (int i = 0; i < n; i++) {
scanf("%d", &weights[i]);
}
Node* huffmanTree = createHuffmanTree(weights, n);
printf("Huffman Tree Construction:\n");
printHuffmanTree(huffmanTree);
free(weights);
return 0;
}
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
// 哈夫曼树节点
struct HuffmanNode {
int weight; // 权值
HuffmanNode* left; // 左子树指针
HuffmanNode* right; // 右子树指针
HuffmanNode* parent; // 父节点指针
HuffmanNode(int w): weight(w), left(NULL), right(NULL), parent(NULL) {} // 构造函数
};
// 优先队列比较函数
struct cmp {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->weight > b->weight; // 权值小的优先级高
}
};
// 构造哈夫曼树
HuffmanNode* buildHuffmanTree(vector<int>& weights) {
priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq; // 用优先队列存储节点
for (int w : weights) {
pq.push(new HuffmanNode(w)); // 将权值存储为节点
}
while (pq.size() > 1) { // 只剩一个节点时结束
HuffmanNode* a = pq.top(); pq.pop(); // 取出权值最小的两个节点
HuffmanNode* b = pq.top(); pq.pop();
HuffmanNode* parent = new HuffmanNode(a->weight + b->weight); // 合并这两个节点
parent->left = a; a->parent = parent;
parent->right = b; b->parent = parent;
pq.push(parent); // 将合并后的节点加入队列
}
return pq.top(); // 返回根节点
}
// 打印哈夫曼树
void printHuffmanTree(HuffmanNode* root) {
if (!root) return;
queue<HuffmanNode*> q;
q.push(root);
while (!q.empty()) {
HuffmanNode* node = q.front(); q.pop();
cout << node->weight << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
cout << endl;
}
// 释放哈夫曼树
void freeHuffmanTree(HuffmanNode* root) {
if (!root) return;
freeHuffmanTree(root->left);
freeHuffmanTree(root->right);
delete root;
}
int main() {
vector<int> weights = {5, 297814, 23319};
HuffmanNode* root = buildHuffmanTree(weights);
printHuffmanTree(root);
freeHuffmanTree(root);
return 0;
}
基于new bing部分指引作答：
下面是一个用 C 语言实现的哈弗曼树建立算法，包含了所要求的功能。
#include <stdio.h>
#include <stdlib.h>
typedef struct huff_node {
int weight; // 结点的权值
int lchild, rchild; // 左右子树结点在数组中的下标
int parent; // 双亲结点在数组中的下标
} HuffNode;
typedef HuffNode* HuffTree;
void build_tree(HuffTree tree, int n);
void print_tree(HuffTree tree, int n);
int main() {
int n = 8;
int w[] = {5, 297814, 23319, 20, 10, 1000, 200, 50};
HuffTree tree;
// 分配空间
tree = (HuffTree)malloc((2*n-1)*sizeof(HuffNode));
for (int i = 0; i < 2*n-1; i++) {
tree[i].weight = 0;
tree[i].lchild = -1;
tree[i].rchild = -1;
tree[i].parent = -1;
}
// 建立哈夫曼树
build_tree(tree, n);
// 显示构造过程
printf("The process of constructing the Huffman Tree:\n");
print_tree(tree, 2*n-1);
// 释放空间
free(tree);
return 0;
}
// 构造哈夫曼树
void build_tree(HuffTree tree, int n) {
int m = 2*n-1; // 总结点数
int s1 = -1, s2 = -1; // 最小、次小权值结点的下标
// 初始化叶子结点
for (int i = 0; i < n; i++) {
tree[i].weight = w[i];
}
// 建立哈夫曼树
for (int i = n; i < m; i++) {
// 选出两个最小权值结点
int j;
for (j = 0; j < i; j++) {
if (tree[j].parent == -1) { // 未被访问过的结点才能参与比较
if (s1 == -1 || tree[j].weight < tree[s1].weight) {
s2 = s1;
s1 = j;
}
else if (s2 == -1 || tree[j].weight < tree[s2].weight) {
s2 = j;
}
}
}
// 合并两个最小权值结点
tree[s1].parent = i;
tree[s2].parent = i;
tree[i].lchild = s1;
tree[i].rchild = s2;
tree[i].weight = tree[s1].weight + tree[s2].weight;
// 显示构造过程
printf("Step %d: choose %d and %d with weights %d and %d, construct a new node with weight %d.\n",
i-n+1, s1, s2, tree[s1].weight, tree[s2].weight, tree[i].weight);
// 重置最小权值结点的下标
s1 = -1;
s2 = -1;
}
}
// 显示哈夫曼树
void print_tree(HuffTree tree, int n) {
for (int i = 0; i < n; i++) {
printf("%d %d %d %d\n", tree[i].weight, tree[i].lchild, tree[i].rchild, tree[i].parent);
}
}
此程序能够接受用户输入包含 n 个叶子结点权值的数组，根据这些权值构造一棵哈夫曼树并显示构造过程。其中函数 build_tree() 和 print_tree() 分别用于哈夫曼树的建立和显示。用户可以在主函数中修改 n 和 w 数组来符合不同的要求，具有良好的用户界面和交互性。
可参考
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef double DataType; //结点权值的数据类型
typedef struct HTNode //单个结点的信息
{
DataType weight; //权值
int parent; //父节点
int lc, rc; //左右孩子
}*HuffmanTree;
typedef char **HuffmanCode; //字符指针数组中存储的元素类型
//在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1的权值小于s2的权值
void Select(HuffmanTree& HT, int n, int& s1, int& s2)
{
int min;
//找第一个最小值
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0)
{
min = i;
break;
}
}
for (int i = min + 1; i <= n; i++)
{
if (HT[i].parent == 0 && HT[i].weight < HT[min].weight)
min = i;
}
s1 = min; //第一个最小值给s1
//找第二个最小值
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0 && i != s1)
{
min = i;
break;
}
}
for (int i = min + 1; i <= n; i++)
{
if (HT[i].parent == 0 && HT[i].weight < HT[min].weight&&i != s1)
min = i;
}
s2 = min; //第二个最小值给s2
}
//构建哈夫曼树
void CreateHuff(HuffmanTree& HT, DataType* w, int n)
{
int m = 2 * n - 1; //哈夫曼树总结点数
HT = (HuffmanTree)calloc(m + 1, sizeof(HTNode)); //开m+1个HTNode，因为下标为0的HTNode不存储数据
for (int i = 1; i <= n; i++)
{
HT[i].weight = w[i - 1]; //赋权值给n个叶子结点
}
for (int i = n + 1; i <= m; i++) //构建哈夫曼树
{
//选择权值最小的s1和s2，生成它们的父结点
int s1, s2;
Select(HT, i - 1, s1, s2); //在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1的权值小于s2的权值
HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权重是s1和s2的权重之和
HT[s1].parent = i; //s1的父亲是i
HT[s2].parent = i; //s2的父亲是i
HT[i].lc = s1; //左孩子是s1
HT[i].rc = s2; //右孩子是s2
}
//打印哈夫曼树中各结点之间的关系
printf("哈夫曼树为:>\n");
printf("下标 权值 父结点 左孩子 右孩子\n");
printf("0 \n");
for (int i = 1; i <= m; i++)
{
printf("%-4d %-6.2lf %-6d %-6d %-6d\n", i, HT[i].weight, HT[i].parent, HT[i].lc, HT[i].rc);
}
printf("\n");
}
//生成哈夫曼编码
void HuffCoding(HuffmanTree& HT, HuffmanCode& HC, int n)
{
HC = (HuffmanCode)malloc(sizeof(char*)*(n + 1)); //开n+1个空间，因为下标为0的空间不用
char* code = (char*)malloc(sizeof(char)*n); //辅助空间，编码最长为n(最长时，前n-1个用于存储数据，最后1个用于存放'\0')
code[n - 1] = '\0'; //辅助空间最后一个位置为'\0'
for (int i = 1; i <= n; i++)
{
int start = n - 1; //每次生成数据的哈夫曼编码之前，先将start指针指向'\0'
int c = i; //正在进行的第i个数据的编码
int p = HT[c].parent; //找到该数据的父结点
while (p) //直到父结点为0，即父结点为根结点时，停止
{
if (HT[p].lc == c) //如果该结点是其父结点的左孩子，则编码为0，否则为1
code[--start] = '0';
else
code[--start] = '1';
c = p; //继续往上进行编码
p = HT[c].parent; //c的父结点
}
HC[i] = (char*)malloc(sizeof(char)*(n - start)); //开辟用于存储编码的内存空间
strcpy(HC[i], &code[start]); //将编码拷贝到字符指针数组中的相应位置
}
free(code); //释放辅助空间
}
//主函数
int main()
{
int n = 0;
printf("请输入数据个数:>");
scanf("%d", &n);
DataType* w = (DataType*)malloc(sizeof(DataType)*n);
if (w == NULL)
{
printf("malloc fail\n");
exit(-1);
}
printf("请输入数据:>");
for (int i = 0; i < n; i++)
{
scanf("%lf", &w[i]);
}
HuffmanTree HT;
CreateHuff(HT, w, n); //构建哈夫曼树
HuffmanCode HC;
HuffCoding(HT, HC, n); //构建哈夫曼编码
for (int i = 1; i <= n; i++) //打印哈夫曼编码
{
printf("数据%.2lf的编码为:%s\n", HT[i].weight, HC[i]);
}
free(w);
return 0;
}
已解决，有用请采纳。
实现哈夫曼树的主要思路是通过贪心算法，每次从权值最小的两个叶子节点中选出来一个，将它们合并成一个新的节点，权值为它们之和。这样重复执行，直到所有节点都被合并成一个根节点。
以下是用C语言实现哈夫曼树的建立算法的示例代码：
#include <stdio.h>
#include <stdlib.h>
// 定义哈夫曼树节点结构体
typedef struct HuffmanNode {
int weight; // 权值
int parent; // 双亲节点地址
int leftChild; // 左孩子节点地址
int rightChild; // 右孩子节点地址
} HuffmanNode;
// 初始化哈夫曼树
void initHuffmanTree(HuffmanNode huffTree[], int n) {
int i;
for (i = 0; i < 2 * n - 1; i++) {
huffTree[i].weight = 0;
huffTree[i].parent = -1;
huffTree[i].leftChild = -1;
huffTree[i].rightChild = -1;
}
}
// 选择两个权值最小的节点
void selectMinNodes(HuffmanNode huffTree[], int n, int *min1, int *min2) {
int i, j;
*min1 = -1;
*min2 = -1;
for (i = 0; i < n; i++) {
if (huffTree[i].parent == -1) {
if (*min1 == -1 || huffTree[i].weight < huffTree[*min1].weight) {
*min2 = *min1;
*min1 = i;
} else if (*min2 == -1 || huffTree[i].weight < huffTree[*min2].weight) {
*min2 = i;
}
}
}
}
// 构建哈夫曼树
void buildHuffmanTree(HuffmanNode huffTree[], int weight[], int n) {
int i, min1, min2;
initHuffmanTree(huffTree, n);
for (i = 0; i < n; i++) {
huffTree[i].weight = weight[i];
}
for (i = n; i < 2 * n - 1; i++) {
selectMinNodes(huffTree, i, &min1, &min2);
huffTree[min1].parent = i;
huffTree[min2].parent = i;
huffTree[i].leftChild = min1;
huffTree[i].rightChild = min2;
huffTree[i].weight = huffTree[min1].weight + huffTree[min2].weight;
}
}
// 显示哈夫曼树
void printHuffmanTree(HuffmanNode huffTree[], int n) {
int i;
printf("Huffman tree:\n");
for (i = 0; i < 2 * n - 1; i++) {
printf("%d\t%d\t%d\t%d\n", i, huffTree[i].weight, huffTree[i].parent, huffTree[i].leftChild, huffTree[i].rightChild);
}
}
int main() {
int n = 8;
int weight[] = {5, 297814, 23319};
HuffmanNode huffTree[2 * n - 1];
buildHuffmanTree(huffTree, weight, n);
printHuffmanTree(huffTree, n);
return 0;
}
以上代码中的 HuffmanNode 结构体存储节点信息，initHuffmanTree() 函数用于初始化哈夫曼树，selectMinNodes() 函数用于选择两个权值最小的节点，buildHuffmanTree() 函数用于构建哈夫曼树，printHuffmanTree() 函数用于显示哈夫曼树。
在实现用户界面时，可以使用菜单及相应的菜单项来完成用户与程序的交互。例如：
#include <stdio.h>
#include <stdlib.h>
...
void displayMenu() {
printf("1. 构建哈夫曼树\n");
printf("2. 显示哈夫曼树\n");
printf("3. 退出程序\n");
}
void displayHuffmanTree(HuffmanNode huffTree[], int n) {
...
}
int main() {
int n = 8;
int weight[] = {5, 297814, 23319};
HuffmanNode huffTree[2 * n - 1];
int choice;
while (1) {
displayMenu();
printf("请输入菜单编号(1-3): ");
scanf("%d", &choice);
switch (choice) {
case 1:
buildHuffmanTree(huffTree, weight, n);
printf("哈夫曼树已经构建完成！\n");
break;
case 2:
displayHuffmanTree(huffTree, n);
break;
case 3:
printf("程序退出！\n");
exit(0);
break;
default:
printf("非法输入，请重新输入。\n");
}
}
return 0;
}
以上代码中的 displayMenu() 函数用于显示菜单，displayHuffmanTree() 函数用于显示哈夫曼树。程序通过不断显示菜单并根据用户的选择执行相应的操作，实现了与用户的交互。
答案参考ChatGPT Plus版，整理汇总。希望能帮助你解决问题下面是使用C语言实现哈夫曼树的建立算法的示例代码。该代码使用结构体表示哈夫曼树的节点，并通过用户交互的方式展示构造过程。
#include <stdio.h>
#include <stdlib.h>
// 哈夫曼树节点结构体定义
typedef struct Node {
int weight; // 结点权值
struct Node* left; // 左子树指针
struct Node* right; // 右子树指针
struct Node* parent; // 父节点指针
} Node;
// 创建哈夫曼树
Node* createHuffmanTree(int weights[], int n) {
Node** nodes = (Node**)malloc(n * sizeof(Node*)); // 动态分配节点指针数组
int i;
for (i = 0; i < n; i++) {
nodes[i] = (Node*)malloc(sizeof(Node)); // 动态分配节点内存
nodes[i]->weight = weights[i];
nodes[i]->left = NULL;
nodes[i]->right = NULL;
nodes[i]->parent = NULL;
}
while (n > 1) {
// 选出两个最小权值的节点
int min1 = 0, min2 = 1;
for (i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
// 构造新节点，权值为选出的两个最小节点的权值之和
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->weight = nodes[min1]->weight + nodes[min2]->weight;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
newNode->parent = NULL;
// 更新节点数组
nodes[min1]->parent = newNode;
nodes[min2]->parent = newNode;
nodes[min1] = newNode;
nodes[min2] = nodes[n - 1];
n--;
}
Node* root = nodes[0];
free(nodes); // 释放节点指针数组内存
return root;
}
// 打印哈夫曼树的构造过程
void printHuffmanTree(Node* root, int weights[], int n) {
printf("构造哈夫曼树的过程如下：\n");
int i;
for (i = 0; i < n - 1; i++) {
Node* leftNode = root->left;
Node* rightNode = root->right;
printf("选出的两个最小值为：%d 和 %d\n", leftNode->weight, rightNode->weight);
printf("当前剩余的权值：");
int j;
for (j = i + 1; j < n; j++) {
printf("%d ", weights[j]);
}
printf("\n");
if (i < n - 2) {
printf("构造新的哈夫曼树，权值为 %d + %d = %d\n", leftNode->weight, rightNode
->weight,
leftNode->weight + rightNode->weight);
}
root = root->parent;
}
}
int main() {
int n;
printf("请输入叶节点的个数：");
scanf("%d", &n);
int* weights = (int*)malloc(n * sizeof(int));
printf("请输入叶节点的权值：");
int i;
for (i = 0; i < n; i++) {
scanf("%d", &weights[i]);
}
Node* root = createHuffmanTree(weights, n);
printHuffmanTree(root, weights, n);
free(weights); // 释放权值数组内存
return 0;
}
使用该程序，用户需要输入叶节点的个数和权值，并根据输出结果观察哈夫曼树的构造过程。程序会显示每一步选出的最小值，并在构造新的哈夫曼树之后展示当前剩余的权值。
请注意，以上代码只是一个示例，可能需要根据实际情况进行调整和完善。