Good day. I'm trying to implement a Huffman algorithm. The tree is built correctly, but it displays several bytes more than it should. I can not find an error. Tell me please.
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct Tree_t {//дерево char data; int weight; char str[256]; struct Tree_t *left; struct Tree_t *right; }tree; typedef struct code_t { //структура для вывода дерева. unsigned long long code; int len; }code_s; unsigned char codes[256]; //для составления кода, во время обхода int all_len;//не используется unsigned char last_code; //сам код int len_last_code; //длина последнего кода (для write_bit) FILE *fout = fopen("out.txt", "wb"); int global;//для отладки typedef struct queue_t { //Эта структура для слияния tree *tree; struct queue_t *next; }queue; tree *merge(tree *l, tree *r) { //слияние деревьев tree *new_tr = (tree*)calloc(1, sizeof(tree)); new_tr->weight = l->weight + r->weight; new_tr->left = l; new_tr->right = r; return new_tr; } queue *enqueue(queue *head, tree *tree_t) { //добавление элемента в очередь с приоритетом queue *first, *second; queue *new_el = (queue*)calloc(1, sizeof(queue)); new_el->tree = tree_t; new_el->next = NULL; if (head == NULL) return new_el; first = head; second = head->next; if (new_el->tree->weight <= first->tree->weight) { new_el->next = first; return new_el; } else { while (second) { if (new_el->tree->weight <= second->tree->weight) break; first = second; second = first->next; } first->next = new_el; new_el->next = second; return head; } } queue *build_haff_tree(queue *head) { //Строим дерево Хаффмана. Голову возвращаем, т.к. она может меняться в процессе queue *first = NULL, *second = NULL, *new_head = NULL; queue *tmp = head; tree *buf; first = tmp; second = tmp->next; new_head = second->next; buf = merge(first->tree, second->tree); head = enqueue(new_head, buf); free(first); free(second); //Удаляем элементы, которые уже вхоядт в новое дерево return head; } queue *create_start_tree(int *ascii, queue *head) { //создаем начальное дерево int i = 0; for (i = 0; i <= 255; i++) { if (ascii[i] != 0) { tree *new_tr = (tree*)calloc(1, sizeof(tree)); new_tr->data = i; new_tr->weight = ascii[i]; head = enqueue(head, new_tr); } } return head; } void clear_tree(tree *tree) {//удаление дерева if (tree == NULL) { return; } clear_tree(tree->left); clear_tree(tree->right); free(tree); } void input_ascii(FILE *fin, int *ascii) { //заполняем таблицу частоты while (!feof(fin)) { ascii[fgetc(fin)]++; } } void input_code_len(char **ascii, char *ascii_len) { //заполняем таблицу длины кодов for (int i = 0; i < 256; i++) { if (ascii[i] != NULL) ascii_len[i] = strlen(ascii[i]); } } void write_bit(code_s code, unsigned char sumbol) {//записываем дерево int i = 0; unsigned char out_bit = 0; unsigned char out_sumbol = 0; if (len_last_code != 0) i = len_last_code; out_bit = (128 >> (code.len + len_last_code)); while (i <= code.len + len_last_code) { i++; if (i == 8) { out_sumbol = out_bit | last_code; fprintf(fout, "%c", out_sumbol); code.len = code.len - (8 - len_last_code); len_last_code = 0; i = 0; out_bit = 0; out_bit = (128 >> (code.len + len_last_code)); global++; } } out_sumbol = out_bit | (sumbol >> i); fprintf(fout, "%c", out_sumbol); last_code = (sumbol << (8 - i)); len_last_code = i; global++; return; } void write_tree_haffman(tree *tree, FILE *tree_out, char **ascii, code_s code) { //Составляем таблицу и записываем дерево в файл if ((tree->left == NULL) && (tree->right == NULL)) { tree->weight = strlen(tree->str); codes[tree->data] = code.code; if (codes[tree->data] != codes[0]) write_bit(code, tree->data); return; } else { code_s c = code; c.code = (1 << c.len); c.len++; all_len++; strcpy(tree->left->str, tree->str); ascii[tree->left->data] = tree->left->str; tree->weight = strlen(tree->str); tree->left->str[tree->weight] = '0'; write_tree_haffman(tree->left, tree_out, ascii, c); strcpy(tree->right->str, tree->str); ascii[tree->right->data] = tree->right->str; tree->right->str[tree->weight] = '1'; write_tree_haffman(tree->right, tree_out, ascii, c); } } void print_text(FILE *fin, FILE *fout, char **ascii, char *ascii_len) { //переводим текст в код хаффмана char c; int last_len = 0; unsigned char out = 0; char *tmp; while (fscanf(fin, "%c", &c) != -1) { tmp = ascii[c]; for (int j = 0; j < ascii_len[c]; j++) { last_len++; if (tmp[j] == '1') out = out | (1 << (8 - last_len)); if (last_len == 8) { fprintf(fout, "%c", out); out = 0; last_len = 0; } } } } int main() { int ascii[260] = { 0 }; char *ascii_code[260] = { NULL }; char len_code[260] = { 0 }; char c = 0; queue *head = NULL; queue *tmp_head = NULL; tree *tree_h = NULL; code_s code; code.code = 0; code.len = 0; global = 0; FILE *fin = fopen("in.txt", "rb"); fscanf(fin, "%c", &c); input_ascii(fin, ascii); //заполняем массив частоты элементов head = create_start_tree(ascii, head); //создаем первые узлы и кидаем их в очередь с их приоритетом tmp_head = head; while (head->next != NULL) head = build_haff_tree(head); //создаем дерево Хаффмана tree_h = head->tree; tree_h->str[0] = 0; fseek(fin, 2, SEEK_SET); write_tree_haffman(tree_h, fout, ascii_code, code); if (len_last_code != 0) fprintf(fout, "%c", last_code); input_code_len(ascii_code, len_code); //print_text(fin, fout, ascii_code, len_code); fclose(fin); fclose(fout); return 0; } 