键盘输入n值创建赫夫曼树代码
时间: 2023-06-06 08:07:45 浏览: 56
好的,以下是键盘输入n值创建赫夫曼树的代码示例:
```
#include <stdio.h>
#include <stdlib.h>
struct node {
int freq;
char symbol;
struct node *left;
struct node *right;
};
struct heap {
int size;
int capacity;
struct node **array;
};
struct node *new_node(int freq, char symbol) {
struct node *temp = (struct node*) malloc(sizeof(struct node));
temp->freq = freq;
temp->symbol = symbol;
temp->left = NULL;
temp->right = NULL;
return temp;
}
struct heap *create_heap(int capacity) {
struct heap *new_heap = (struct heap*) malloc(sizeof(struct heap));
new_heap->size = 0;
new_heap->capacity = capacity;
new_heap->array = (struct node**) malloc(capacity * sizeof(struct node*));
return new_heap;
}
void swap_nodes(struct node **a, struct node **b) {
struct node *temp = *a;
*a = *b;
*b = temp;
}
void min_heapify(struct heap *min_heap, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < min_heap->size && min_heap->array[left]->freq < min_heap->array[smallest]->freq) {
smallest = left;
}
if (right < min_heap->size && min_heap->array[right]->freq < min_heap->array[smallest]->freq) {
smallest = right;
}
if (smallest != index) {
swap_nodes(&min_heap->array[index], &min_heap->array[smallest]);
min_heapify(min_heap, smallest);
}
}
int is_size_one(struct heap *min_heap) {
return (min_heap->size == 1);
}
struct node *extract_min(struct heap *min_heap) {
struct node *min_node = min_heap->array[0];
min_heap->array[0] = min_heap->array[min_heap->size - 1];
min_heap->size--;
min_heapify(min_heap, 0);
return min_node;
}
void insert_min_heap(struct heap *min_heap, struct node *node) {
min_heap->size++;
int index = min_heap->size - 1;
while (index && node->freq < min_heap->array[(index - 1) / 2]->freq) {
min_heap->array[index] = min_heap->array[(index - 1) / 2];
index = (index - 1) / 2;
}
min_heap->array[index] = node;
}
void build_heap(struct heap *min_heap) {
int n = min_heap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; i--) {
min_heapify(min_heap, i);
}
}
void print_codes(struct node *root, int arr[], int top) {
if (root->left) {
arr[top] = 0;
print_codes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
print_codes(root->right, arr, top + 1);
}
if (!(root->left) && !(root->right)) {
printf("%c: ", root->symbol);
int i;
for (i = 0; i < top; i++) {
printf("%d", arr[i]);
}
printf("\n");
}
}
void huffman_codes(char data[], int freq[], int size) {
struct node *left, *right, *top;
struct heap *min_heap = create_heap(size);
int i;
for (i = 0; i < size; i++) {
insert_min_heap(min_heap, new_node(freq[i], data[i]));
}
build_heap(min_heap);
while (!is_size_one(min_heap)) {
left = extract_min(min_heap);
right = extract_min(min_heap);
top = new_node(left->freq + right->freq, '$');
top->left = left;
top->right = right;
insert_min_heap(min_heap, top);
}
int arr[100], top = 0;
print_codes(extract_min(min_heap), arr, top);
}
int main() {
int n, i;
printf("Enter the number of characters: ");
scanf("%d", &n);
char data[n];
int freq[n];
printf("Enter the characters and their frequencies:\n");
for (i = 0; i < n; i++) {
scanf(" %c %d", &data[i], &freq[i]);
}
huffman_codes(data, freq, n);
return 0;
}
```
希望能对你有所帮助!
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)
![](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)
![](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)