Форум программистов, компьютерный форум CyberForum.ru

Код Хаффмана - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Связанные списки http://www.cyberforum.ru/cpp-beginners/thread1063417.html
Здравствуйте! Не очень сложное задание, но так как я начинающий, запуталась немного... особенно с указателями и ссылками. В общем задача такая. Пользователь вводит 10 чисел в связанный список, каждое число добавляется в конец. Затем просто вывести этот список. Прототипы функций дали такие void addToEnd(node* &last, int number) //это для добавления в конец void outp(node *glava) //это...
C++ перевод из си++ в паскаль for (int j = max(0, i - (n - m)); j <= i && j <= m; ++j) Как перевести эту строчку, а именно "j <= i && j <= m". http://www.cyberforum.ru/cpp-beginners/thread1063410.html
C++ Программно изменить шрифт в консоли
Раньше для вывода кириллицы в консоли я использовал setlocale, но недавно потребовалось, чтобы консоль и воспринимала кириллицу. Пошел к Google, нашел SetConcoleCP и SetConsoleOutputCP. Сложность в том, что данные методы работают только тогда, когда в консоли включен шрифт Lucida Console, но их вручную включать каждый раз неудобно. Снова пошел к Google и нашел статьи про недокументированные...
Настройка CodeBlock C++
Всем привет. Давно мучает вопрос относительно интерфейса Code::block. Как убрать отображение полного пути к открытому файлу с кодом из заголовка вкладки? Я имею в виду, как сделать так, чтобы текст названия вкладки отображал лишь название файла, а не полный путь к нему. Проблема возникла из-за файлов с длинным путем, так как при их открытии они своим названием занимают практически всю...
C++ Вычислить произведение положительных элементов строки матрицы http://www.cyberforum.ru/cpp-beginners/thread1063384.html
Вычислить произведение положительных элементов строки матрицы. При обнаружении 0 должно выдаваться сообщение «Обнаружен 0». Помогите решить. Заранее благодарен.
C++ errno 13 Почему при инициализации семафора возвращается ошибка? key2 = ftok(".", 'c'); int w = semget(key2, 1, IPC_CREAT); //отрабатывает без ошибок // возвращает идентификатор набора семафоров, связанный с аргументом key if ((semctl(w, 0, SETVAL, 2)) == (-1)) //установливаем начальное значение семафора { std::cout << "Ошибка semctl " << errno << std::endl; } подробнее

Показать сообщение отдельно
PhenixOfDoctor
1 / 1 / 0
Регистрация: 29.12.2013
Сообщений: 23
05.01.2014, 14:47     Код Хаффмана
Дорогие программисты, тут вышла одна проблемка с кодом Хаффмана. Я написал код Хаффмана для препода, а он попросил еще доделать его, добавив туда высчет вероятности(то есть, если в предложении какая нибудь буква встречается 2 раза, то нужно общее количество букв разделить на 2, если 3 раза,то на 3 и этот результат вывести на экран,чтобы было так:

буквы: вероятность: код Хаффмана:
а 0,33 110
б 0,11 010

чтобы вот так было,а как эт сделать,я хз вообще. Если не сложно,можете помочь?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <queue>
#include <map>
#include <climits> // for CHAR_BIT
#include <iterator>
#include <algorithm>
 
const int UniqueSymbols = 1 << CHAR_BIT;
const char* SampleString = "bep or!";
 
typedef std::vector<bool> HuffCode;
typedef std::map<char, HuffCode> HuffCodeMap;
 
class INode
{
public:
    const int f;
 
    virtual ~INode() {}
 
protected:
    INode(int f) : f(f) {}
};
 
class InternalNode : public INode
{
public:
    INode *const left;
    INode *const right;
 
    InternalNode(INode* c0, INode* c1) : INode(c0->f + c1->f), left(c0), right(c1) {}
    ~InternalNode()
    {
        delete left;
        delete right;
    }
};
 
class LeafNode : public INode
{
public:
    const char c;
 
    LeafNode(int f, char c) : INode(f), c(c) {}
};
 
struct NodeCmp
{
    bool operator()(const INode* lhs, const INode* rhs) const { return lhs->f > rhs->f; }
};
 
INode* BuildTree(const int (&frequencies)[UniqueSymbols])
{
    std::priority_queue<INode*, std::vector<INode*>, NodeCmp> trees;
 
    for (int i = 0; i < UniqueSymbols; ++i)
    {
        if(frequencies[i] != 0)
            trees.push(new LeafNode(frequencies[i], (char)i));
    }
    while (trees.size() > 1)
    {
        INode* childR = trees.top();
        trees.pop();
 
        INode* childL = trees.top();
        trees.pop();
 
        INode* parent = new InternalNode(childR, childL);
        trees.push(parent);
    }
    return trees.top();
}
 
void GenerateCodes(const INode* node, const HuffCode& prefix, HuffCodeMap& outCodes)
{
    if (const LeafNode* lf = dynamic_cast<const LeafNode*>(node))
    {
        outCodes[lf->c] = prefix;
    }
    else if (const InternalNode* in = dynamic_cast<const InternalNode*>(node))
    {
        HuffCode leftPrefix = prefix;
        leftPrefix.push_back(false);
        GenerateCodes(in->left, leftPrefix, outCodes);
 
        HuffCode rightPrefix = prefix;
        rightPrefix.push_back(true);
        GenerateCodes(in->right, rightPrefix, outCodes);
    }
}
 
int main()
{
    // Build frequency table
    int frequencies[UniqueSymbols] = {0};
    const char* ptr = SampleString;
    while (*ptr != '\0')
        ++frequencies[*ptr++];
 
    INode* root = BuildTree(frequencies);
 
    HuffCodeMap codes;
    GenerateCodes(root, HuffCode(), codes);
    delete root;
 
    for (HuffCodeMap::const_iterator it = codes.begin(); it != codes.end(); ++it)
    {
        std::cout << it->first << " ";
        std::copy(it->second.begin(), it->second.end(),
                  std::ostream_iterator<bool>(std::cout));
        std::cout << std::endl;
    }
    return 0;
}
Добавлено через 2 часа 41 минуту
ой,то есть не написал сам,а нашел код Хаффмана,прошу прощения=)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 21:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru