写出可以运行的C语言代码,代码的目的是构造最优二叉树,使用标准输入和输出流,让程序从控制台读取输入并输出结果。要求输入包括字符集C[],字符集对应的频率表p[],字符个数n;输出为得到最优二叉树的结点表T[]和各字符霍夫曼编码。
时间: 2024-02-21 07:58:24 浏览: 69
以下是一个可以构造最优二叉树的C语言代码,使用标准输入和输出流:
```
#include <stdio.h>
#include <stdlib.h>
struct node
{
int freq;
char c;
struct node *left, *right;
};
struct node* newNode(char c, int freq)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->left = NULL;
node->right = NULL;
node->c = c;
node->freq = freq;
return node;
}
void swap(struct node **a, struct node **b)
{
struct node *temp = *a;
*a = *b;
*b = temp;
}
void minHeapify(struct node **arr, int i, int n)
{
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left]->freq < arr[smallest]->freq)
smallest = left;
if (right < n && arr[right]->freq < arr[smallest]->freq)
smallest = right;
if (smallest != i)
{
swap(&arr[i], &arr[smallest]);
minHeapify(arr, smallest, n);
}
}
void buildMinHeap(struct node **arr, int n)
{
int i;
for (i = n / 2 - 1; i >= 0; --i)
minHeapify(arr, i, n);
}
struct node* extractMin(struct node **arr, int *n)
{
struct node* temp = arr[0];
arr[0] = arr[*n - 1];
--*n;
minHeapify(arr, 0, *n);
return temp;
}
void insert(struct node **arr, int *n, struct node* node)
{
++*n;
int i = *n - 1;
while (i && node->freq < arr[(i - 1) / 2]->freq)
{
arr[i] = arr[(i - 1) / 2];
i = (i - 1) / 2;
}
arr[i] = node;
}
struct node* buildHuffmanTree(char c[], int freq[], int n)
{
struct node *left, *right, *top;
int i;
int size = n;
struct node **arr = (struct node**)malloc(sizeof(struct node*) * n);
for (i = 0; i < n; ++i)
arr[i] = newNode(c[i], freq[i]);
buildMinHeap(arr, n);
while (size > 1)
{
left = extractMin(arr, &size);
right = extractMin(arr, &size);
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insert(arr, &size, top);
}
return extractMin(arr, &size);
}
void printCodes(struct node* root, int arr[], int top)
{
if (root->left)
{
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right)
{
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (!root->left && !root->right)
{
printf("%c: ", root->c);
int i;
for (i = 0; i < top; ++i)
printf("%d", arr[i]);
printf("\n");
}
}
void HuffmanCodes(char c[], int freq[], int n)
{
struct node* root = buildHuffmanTree(c, freq, n);
int arr[100], top = 0;
printCodes(root, arr, top);
}
int main()
{
char c[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int freq[] = {5, 9, 12, 13, 16, 45};
int n = sizeof(c) / sizeof(c[0]);
HuffmanCodes(c, freq, n);
return 0;
}
```
在这个代码中,我们首先定义了一个节点结构体,包括字符c、字符频率freq、左右子节点left和right。然后我们定义了一些辅助函数,比如newNode、swap、minHeapify、buildMinHeap、extractMin、insert和buildHuffmanTree。这些函数用于构建哈夫曼树。最后,我们定义了一个打印哈夫曼编码的函数printCodes和一个主函数,用于测试和运行代码。
在主函数中,我们声明了一个字符集数组c、一个字符集对应的频率表freq和字符个数n。然后,我们调用HuffmanCodes函数来构建哈夫曼树并打印哈夫曼编码。
您可以将输入信息设置为从控制台读取,然后将输出信息输出到控制台。
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231044955.png)
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)