Дерево хаффмана — c

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд
Загрузка...

Вопрос:


Добрый день. Пытаюсь реализовать алгоритм Хаффмана. Дерево строится правильно, однако выводит на несколько байт больше, чем должно. Не могу найти ошибку. Подскажите, пожалуйста.

    #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;
}

Автор вопроса: Lark

Источник

Вам также может быть интересно:

Использование вложенных маршрутов в React Router — javascript reactjs react-router
Вопрос: Для организации маршрутов в приложении использую React Router. <Route path="/" component={...}> <IndexRoute component={...}/> <Route path="user/:userId" component={...}> ...
Как с помощью Retrofit 2.0 отправить данные в JSON на сервер и получить ответ? — java android retrofit
Вопрос: Только начал читать про Retrofit 2.0 до этого использовал HttpURLConnection. Как я работаю с HttpURLConnection, формирую Json перевожу его в byte, ставлю header в ...
Не приходят push уведомления. FCM — android firebase android-notification
Вопрос: Появилась необходимость реализовать push уведомления. Прописал в манифесте сервис: <service android:name=".MyFirebaseMessagingService"> <intent-filter> ...
Принцип браузерной игры в линукс терминале — java linux terminal
Вопрос: Наткнулся на Java библиотеку CHARVA. И хотел бы уточнить у знающих людей, возможно ли на основе данной библиотеки сделать программу по принципу браузерной игры, но ...
Мерцание заблокированного экрана при выключенной подсветке в Debian 8 Gnome 3 — linux debian экран
Вопрос: На ноутбуке с Debian 8 Jessie и Gnome 3 имеется следующая проблема. При выключенном заблокированном экране сквозь него можно наблюдать, как весь экран становится белым, ...
Создание WCF клиента на готовый SOAP web сервер — c# wcf
Вопрос: Доброго времени суток. Появилась задача опрашивать web сервер с клиента на котором планируется написать WCF клиентскую часть. Информации про сервер очень мало (не знаю платформу ...
Безопасно ли удалить файл логов general_log.txt? — mysql
Вопрос: При выполнении запроса со вставкой данных большого объёма SQLyog начал вылетать с ошибкой: not enough memory application terminated В связи с этим я решила ...
Callback функции создания таблицы mysql в nodejs — mysql node.js callback
Вопрос: Есть функция, которая при запуске создает базу даных, function showDb() { pool.query("show databases like 'bt' ",function (err, ...
Как создать Adapter с неограниченным количеством строк и с неограниченным разным количеством столбцов в каждой строке — java android
Вопрос: Как создать Adapter с неограниченным количеством строк и с неограниченным разным количеством столбцов в каждой строке Автор вопроса: Salut Amigo Источник
Не могу передать байтовый массив в контроллер — c# asp.net-mvc entity-framework
Вопрос: У меня изображения храняться в бд в формате байтового массива, через форич отлично все выводит, но когда я хочу открыть страницу для работы с ...
proguard release error — java android mvp
Вопрос: Включил в проекте proguard, apk собирается, все хорошо, но приложение не работает) Proguard-rules.pro -keepattributes InnerClasses -keepattributes EnclosingMethod -keepattributes *Annotation* -dontoptimize # Keep Butterknife -keep class butterknife.** { *; } -dontwarn butterknife.internal.** -keep ...
Не отрабатывает page:update — javascript ruby-on-rails
Вопрос: Есть мой учебный проект на ruby. Делаю редактирование объектов с помощью JS. Сейчас работает так: Редактирую первый раз - всё нормально. Не обновляя страницу, ...
Как найти определенный символ в строке и удалить значение после него (и вместе с ним) Jquery — javascript html jquery
Вопрос: Здравствуйте, есть определенный набор строк, типа "L / Красный / 12345", как можно на странице найти их, и вырезать из них все что находится ...
Почему не работает wildcard module declaration? — typescript
Вопрос: Почему не работает такой способ декларации: declare module "*!text" {} ? Цель - использовать контент файла в переменной: import layout = require("/js/views/layouts/wnd.html!text"); или так: import layout from "/js/views/layouts/wnd.html!text"; Если ...
Как прервать 3rd-party код? — c# многопоточность .net-core
Вопрос: Есть 3rd-party код из библиотеки который "зависает" в ожидании где-то в работе с сетью. CancellationToken поддержки нет, таймаутов нет. Запускаю я его через: Task.Run(() => ...

Оставьте ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *