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

Поиск наименьших двух элементов массива или алгоритм Хаффмана - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ C++ 11 конструктор переноса && http://www.cyberforum.ru/cpp-beginners/thread682076.html
Кто-нибудь может мне пояснить или дать ссылку на информацию о rvalue reference на русском языке, а то на английском что-то не всё могу понять.
C++ Найти сумму квадратов всех целых чисел от A до В включительно Помогите, может кто уже делал такие задачи? я ваще не дум дум. 1) Даны целые числа K>N(N>0).Вывести N раз число K. 2) Даны два числа A и B (A>B). Вывести в порядке убывания все целые числа, расположенные между A и B (не включая A и B), а также количество N этих чисел. 3) Даны два целых числа A и B (А<B). Найти сумму квадратов всех целых чисел от A до В включительно. 4) Дано целое число N(>0).... http://www.cyberforum.ru/cpp-beginners/thread682048.html
C++ Динамический массив с пользовательскими функциями
Задача: Массив unsignet int, найти количество 1, 2 и т.д в масиві Условия: Массив должен быть динамический. Через пользовательские функции. Код должен быть читабельным.
с клавиатуры вводится последовательность чисел C++
0-конец этой последовательности. Заменить все четные элементы последовательности на нечетные
C++ Симметричное шифрование http://www.cyberforum.ru/cpp-beginners/thread681999.html
Необходимо написать на языке C++ программу симметричного шифрования бинарных файлов. Шифрование должно выполняться в режиме CBC (chain block cipher). Программа должна использовать 8-и битный ключ и выполнять операции зашифрования и расшифрования указанного файла. Необходимо реализовать две функции с заданным интерфейсом: encryptCBC, decryptCBC. Список аргументов функций одинаковый: - buffer -...
C++ Программа, печатающая в консоли треугольники из звездочек Цель задания - чтобы программа вывела треугольники в консоль в таком виде, как показано на рисунке, т.е. рядом. Я справился с задачей, и у меня все работает, но хотелось бы знать, хорошо ли я использовал код или он кривоват? /* Мне лично нравится :) но иногда я что-то усложняю или делаю не так красиво, как можно было бы*/ #include <iostream> using namespace std; int main() { int i,j; подробнее

Показать сообщение отдельно
John Prick
778 / 711 / 131
Регистрация: 27.07.2012
Сообщений: 2,044
Завершенные тесты: 3
27.10.2012, 23:30
Решал как-то подобную задачу с деревом Хаффмана, там на сжатие данных была задача. Но может быть, поможет и тут.
Huffman.cpp
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
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
 
#include "File.h"
#include "Alphabet.h"
#include "Tree.h"
 
class TTotalBitsCounter
{
private:
    int counter;
public:
    TTotalBitsCounter(void) : counter(0) {}
    void operator()(const TAlpha & Alpha)
    {
        counter += Alpha.Code().size() * Alpha.Weight();
    }
    int Count(void) const { return counter; }
};
 
int main(void)
{
    setlocale(0, "rus");
    // Считываем файл весов
    int symbols = 0;
    int * weights = 0;
    bool success = LoadWeightsFromFile(weights, symbols);
    if (!success)
    {
        system("pause");
        return 0;
    }
    std::cout << "Количество символов: " << symbols << '\n';
    std::cout << "Веса символов: " << '\n';
    std::copy(weights, weights + symbols, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
 
    // Формируем алфавит (с задаными весами символов)
    TAlphabet alphabet;
    std::for_each(weights, weights + symbols, AlphaAppend(alphabet));
    // Копируем алфавит в список узлов
    THuffmanTree huffmanTree;
    for (TAlphabet::iterator i = alphabet.begin(); i != alphabet.end(); ++i)
        huffmanTree.push_back(new TAlphaNode(*i));
 
    while (huffmanTree.size() > 1)
    {
        // 1) находим 2 элемента с наименьшими весами
        TAlphaNode * min1 = FindMinWeightAndErase(huffmanTree);
        TAlphaNode * min2 = FindMinWeightAndErase(huffmanTree);
        // 2) Добавляем в список новый узел с суммарным весом найденных
        TAlphaNode * newNode = new TAlphaNode(
            TAlpha(min1->Alpha().Weight() + min2->Alpha().Weight(), 0)
            );
        newNode->setLeft(min1);
        newNode->setRight(min2);
        huffmanTree.push_back(newNode);
    }
    // обходим дерево (используя стек). когда находим конечный узел (символ алфавита),
    // устанавливаем его код Хаффмана
    THuffmanTreeStack stack;
    TAlphaNode * head = huffmanTree[0];
    while (head != 0)
    {
        if (head->Left() != 0)
        {
            stack.push(head->Right());
            head = head->Left();
        } else
        { // нашли конечный узел
            TAlphabet::iterator alpha = std::find(alphabet.begin(), alphabet.end(), head->Alpha());
            (*alpha).setCode(head->Alpha().Code());
            head = stack.pop();
        }
    }
 
    std::cout << "Коды символов: " << '\n';
    for (TAlphabet::iterator i = alphabet.begin(); i != alphabet.end(); ++i)
        std::cout << i->Alpha() << ":" << i->Code() << " ";
    std::cout << std::endl;
 
    int totalBits = std::for_each(alphabet.begin(), alphabet.end(), TTotalBitsCounter()).Count();
    std::cout << "Всего бит на текст: " << totalBits << '\n';
    WriteResult(totalBits);
 
    system("pause");
    return 0;
}

Alphabet.h
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
#ifndef ALPHABET_H
#define ALPHABET_H
 
#include <vector>
#include <string>
 
class TAlpha
{
private:
    int alpha;
    int weight;
    std::string huffmanCode;
public:
    explicit TAlpha(int W, int C = 1) : alpha(C), weight(W) {}
    TAlpha(const TAlpha & That) : alpha(That.alpha), weight(That.weight) {}
    bool operator==(const TAlpha & That) const { return (alpha == That.alpha); }
    bool operator==(const int & That) const { return (alpha == That); }
    int Weight(void) const { return weight; }
    int Alpha(void) const { return alpha; }
    const std::string & Code(void) const { return huffmanCode; }
    void incWeight(void) { ++weight; }
    void setCode(const std::string & Code) { huffmanCode = Code; }
    void insertCode(char Code) { huffmanCode.insert(0, 1, Code); }
};
 
typedef std::vector<TAlpha> TAlphabet;
 
class AlphaAppend
{
private:
    TAlphabet & alphabet;
    int alphaID;
public:
    AlphaAppend(TAlphabet & Alphabet) : alphabet(Alphabet), alphaID(1) {}
    void operator()(const int & Weight)
    {
        alphabet.push_back(TAlpha(Weight, alphaID));
        ++alphaID;
    }
};
 
#endif

Tree.h
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
#ifndef TREE_H
#define TREE_H
 
#include <vector>
#include "Alphabet.h"
 
class TAlphaNode
{
private:
    TAlpha alpha;
    TAlphaNode * left;
    TAlphaNode * right;
 
    void insertCode(char Code)
    {
        alpha.insertCode(Code);
        if (left)
            left->insertCode(Code);
        if (right)
            right->insertCode(Code);
    }
 
public:
    TAlphaNode(TAlpha & Alpha) : alpha(Alpha), left(0), right(0) {}
    TAlphaNode * Left(void) const { return left; }
    TAlphaNode * Right(void) const { return right; }
    const TAlpha & Alpha(void) const { return alpha; }
 
    void setLeft(TAlphaNode * Node) { left = Node; left->insertCode('0'); }
    void setRight(TAlphaNode * Node) { right = Node; right->insertCode('1'); }
 
};
 
bool AlphaWeightComp(const TAlphaNode * const A, const TAlphaNode * const B)
{
    return (A->Alpha().Weight() < B->Alpha().Weight());
}
 
typedef std::vector<TAlphaNode*> THuffmanTree;
 
TAlphaNode * FindMinWeightAndErase(THuffmanTree & tree)
{
    THuffmanTree::iterator min = std::min_element(tree.begin(), tree.end(), AlphaWeightComp);
    TAlphaNode * temp = *min;
    tree.erase(min);
    return temp;
}
 
class THuffmanTreeStack
{
private:
    typedef std::vector<TAlphaNode*> TStack;
    TStack stack;
public:
    void push(TAlphaNode * Node) { stack.push_back(Node); }
    TAlphaNode * pop(void)
    {
        if (stack.size() == 0)
            return 0;
        TAlphaNode * temp = stack.back();
        stack.pop_back();
        return temp;
    }
};
 
#endif

File.cpp
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
#include <iostream>
#include <fstream>
#include "File.h"
 
const int MaxNLength = 5; // число n записано от 1 до 4 символов + '\n'
const int MaxLetterLength = 11; // числа до 10^9 - 10 символов + ' '
 
// читает первую строчку - число n
int GetCountSymbols(std::ifstream & input)
{
    char * pStr = new char[MaxNLength];
    input.getline(pStr, MaxNLength);
    int a = atoi(pStr);
    delete [] pStr;
    return a;
}
// читает записанный в файле вес
int GetWeight(std::ifstream & input, const int EndPos)
{
    char str[MaxLetterLength];
    int currentPos = input.tellg();
 
    int i = 0;
    while ((i < MaxLetterLength) && (i + currentPos < EndPos))
    {
        input.get(str[i]);
        if ((str[i] == ' ') || (str[i] == '\n') ||
            (str[i] == '\r') || (str[i] == '\t'))
            break;
        ++i;
    }
    str[i + 1] = '\0';
    return atoi(str);
}
 
bool LoadWeightsFromFile(int *& text, int & symbols)
{
    std::ifstream input("huffman.in");
    if (!input.is_open())
    {
        std::cout << "Ошибка открытия файла!";
        return false;
    }
 
    input.seekg(0, std::ios::end);
    const int N = input.tellg();
    input.seekg(0, std::ios::beg);
 
    symbols = GetCountSymbols(input);
    text = new int[symbols];
    for (int i = 0; i < symbols; ++i)
        text[i] = GetWeight(input, N);
 
    input.close();
    return true;
}
 
bool WriteResult(const int TotalBits)
{
    std::ofstream output("huffman.out", std::ios::out);
    output << TotalBits;
    return true;
}

File.h
C++
1
2
3
4
5
6
7
8
9
#ifndef FILE_H
#define FILE_H
 
int GetCountSymbols(std::ifstream & input);
int GetWeight(std::ifstream & input, const int EndPos);
bool LoadWeightsFromFile(int *& text, int & symbols);
bool WriteResult(const int TotalBits);
 
#endif

Не судите строго за говнокод, делалось всё как-то и когда-то.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru