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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Rebel123
 Аватар для Rebel123
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12
27.10.2012, 22:40     Поиск наименьших двух элементов массива или алгоритм Хаффмана #1
Приветствую!

Дали задачу, сделать прогу в котором изначально есть массив из 12 элементов a1, a2...an с разными вероятностями, общая сумма которых составляет единицу. Нужно сделать следующее:

1. Вывести массив (я использую StringGrid) (сделано)
2. Упорядочить массив по убыванию (сделано)
3. Построить кодовое дерево по методу Хаффмана

То есть, как сделать, чтобы из уже отсортированного массива программа брала 2 наименьших элемента и прибавляла их между собой? При этом ak-1 <= ak, где ak-1 = a7 (0,02), ak = а1(0,04). То есть,
п.1. Выбираем две буквы aK и aK-1 с минимальными вероятностя-
ми p(aK-1) и p(aK).
п.2. Полагаем, что последний символ буквы aК равен «1», а по-
следний символ буквы aК-1 – «0».
тем самым получим D-ичный код для каждого элемента присваивая 0 или 1.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.10.2012, 22:40     Поиск наименьших двух элементов массива или алгоритм Хаффмана
Посмотрите здесь:

C++ Алгоритм Хаффмана
Алгоритм Хаффмана C++
C++ Алгоритм Хаффмана
C++ Найдите количество наименьших элементов массива
C++ Определить индексы и значения наибольших и наименьших по модулю элементов одномерного массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.10.2012, 22:55     Поиск наименьших двух элементов массива или алгоритм Хаффмана #2
Тут дерево надо строить. А не просто два наименьших элемента искать
Rebel123
 Аватар для Rebel123
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12
27.10.2012, 22:57  [ТС]     Поиск наименьших двух элементов массива или алгоритм Хаффмана #3
Наработки по коду:

Код
//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
#include "Unit2.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)
{
        float a[12] = {0.17, 0.04, 0.06, 0.08, 0.15, 0.12, 0.07, 0.02, 0.01, 0.10, 0.11, 0.07};
        int i;
        for (i = 0; i < 12; i++)
                Gr->Cells[0][i] = Format("%f", ARRAYOFCONST((a[i])));
        Button2->Visible = True;
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)
{
    float a[12] = {0.17, 0.04, 0.06, 0.08, 0.15, 0.12, 0.07, 0.02, 0.01, 0.10, 0.11, 0.07}, tmp;
    int i, j;
    int const size = sizeof(a) / sizeof(*a);
    for(i = 0; i < size; ++i)
    {
        tmp = a[i];
        for(j = i - 1; j >= 0 && a[j] < tmp; --j)
        {
            a[j + 1] = a[j];
        }
        a[j + 1] = tmp;
    }
    for(i = 0; i < size; ++i)
    {
        Gr->Cells[1][i] = Format("%f", ARRAYOFCONST((a[i])));
    }
    Button3->Visible = True;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button3Click(TObject *Sender)
{
Form2->Show();
}
//---------------------------------------------------------------------------
По нажатию на первую кнопку происходить вывод элементов массива, по второй кнопке - сортировка по убыванию.
По третьей кнопке - новая форма с новым StringGrid где должно построится кодовое (двоичное) дерево по методу Хаффмана.

P.S. прикрепил пример построения кодового дерева по Хаффману
Миниатюры
Поиск наименьших двух элементов массива или алгоритм Хаффмана  
Rebel123
 Аватар для Rebel123
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12
27.10.2012, 23:00  [ТС]     Поиск наименьших двух элементов массива или алгоритм Хаффмана #4
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Тут дерево надо строить. А не просто два наименьших элемента искать
по коду Хаффмана так и получается, что между собой прибавляются два наименьших, к примеру как в моем случае: a9=0,01 + a8=0,02 = 0,03. Далее программа должна вести поиск или что-то в этом роде, и если следующий наименьший элемент меньше чем 0,03, тогда дерево строится по новому.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.10.2012, 23:06     Поиск наименьших двух элементов массива или алгоритм Хаффмана #5
сделай тег CPP /CPP, читается сейчас хуже, чем без тегов
Rebel123
 Аватар для Rebel123
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12
27.10.2012, 23:08  [ТС]     Поиск наименьших двух элементов массива или алгоритм Хаффмана #6
Точнее не следующий, а вообще, из всех элементов, если нету элемента больше или равен тому, к которому будет прибавляться (0,03), тогда дерево строится снова, берутся два наименьших.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.10.2012, 23:12     Поиск наименьших двух элементов массива или алгоритм Хаффмана #7
сделай тег CPP /CPP, читается сейчас хуже, чем без тегов
Во-первых отсортируй массив. Насколько я понял это
C++
1
2
3
4
5
6
7
8
9
for(i = 0; i < size; ++i)
    {
        tmp = a[i];
        for(j = i - 1; j >= 0 && a[j] < tmp; --j)
        {
            a[j + 1] = a[j];
        }
        a[j + 1] = tmp;
    }
что-то какая-то подозрительная сортировка. Она работает?
Во-вторых, тебе нужно определить как ты будешь хранить дерево Хаффмана.
Никаких структур данных для этого я у тебя не увидел. Поэтому
Определяй
C
1
2
3
4
5
struct node{
  float a;
  struct node* left;
  struct node* right;
}root[12];
Это точно в школе изучают?
Rebel123
 Аватар для Rebel123
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12
27.10.2012, 23:14  [ТС]     Поиск наименьших двух элементов массива или алгоритм Хаффмана #8
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
//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1.h"
#include "Unit2.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button1Click(TObject *Sender)
{
        float a[12] = {0.17, 0.04, 0.06, 0.08, 0.15, 0.12, 0.07, 0.02, 0.01, 0.10, 0.11, 0.07};
        int i;
        for (i = 0; i < 12; i++)
                Gr->Cells[0][i] = Format("%f", ARRAYOFCONST((a[i])));
        Button2->Visible = True;
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button2Click(TObject *Sender)
{
    float a[12] = {0.17, 0.04, 0.06, 0.08, 0.15, 0.12, 0.07, 0.02, 0.01, 0.10, 0.11, 0.07}, tmp;
    int i, j;
    int const size = sizeof(a) / sizeof(*a);
    for(i = 0; i < size; ++i)
    {
        tmp = a[i];
        for(j = i - 1; j >= 0 && a[j] < tmp; --j)
        {
            a[j + 1] = a[j];
        }
        a[j + 1] = tmp;
    }
    for(i = 0; i < size; ++i)
    {
        Gr->Cells[1][i] = Format("%f", ARRAYOFCONST((a[i])));
    }
    Button3->Visible = True;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button3Click(TObject *Sender)
{
Form2->Show();
}
//---------------------------------------------------------------------------
Вот, прикрепил уже построенное дерево по моему примеру.

Да, сортировка работает.

P.S. проект прикреплю на всякие
P.P.S. не работал со структурами если честно =(
Миниатюры
Поиск наименьших двух элементов массива или алгоритм Хаффмана  
Вложения
Тип файла: zip huffman porjусе.zip (607.9 Кб, 8 просмотров)
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.10.2012, 23:22     Поиск наименьших двух элементов массива или алгоритм Хаффмана #9
Цитата Сообщение от Rebel123 Посмотреть сообщение
P.P.S. не работал со структурами если честно =(
А зачем за Хаффмана взялся? Рановато.
Почитай эту тему.Хаффман с++
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
27.10.2012, 23:30     Поиск наименьших двух элементов массива или алгоритм Хаффмана #10
Решал как-то подобную задачу с деревом Хаффмана, там на сжатие данных была задача. Но может быть, поможет и тут.
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

Не судите строго за говнокод, делалось всё как-то и когда-то.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.10.2012, 23:34     Поиск наименьших двух элементов массива или алгоритм Хаффмана #11
Цитата Сообщение от John Prick Посмотреть сообщение
Но может быть, поможет и тут.
Это так, но ТС говорил, что он даже структуры не знает. А тут классы...
Rebel123
 Аватар для Rebel123
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12
27.10.2012, 23:39  [ТС]     Поиск наименьших двух элементов массива или алгоритм Хаффмана #12
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А зачем за Хаффмана взялся? Рановато.
Почитай эту тему.Хаффман с++
Хм...задумка схожая, но не могли бы вы подсказать более детально что именно взять оттуда для моего случая? Впринципе, можно было и в текстовый документ элементы загнать

Это так, но ТС говорил, что он даже структуры не знает. А тут классы...
Структуры почитать и понять не проблема, а вижу тут классы)) но это уж совсем на выходные остаются)), времени до понедельника просто, не успею с классами.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.10.2012, 23:47     Поиск наименьших двух элементов массива или алгоритм Хаффмана
Еще ссылки по теме:

Определить значения двух наименьших элементов вектора C++
C++ Алгоритм Хаффмана
C++ Канонический алгоритм Хаффмана

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
John Prick
754 / 687 / 123
Регистрация: 27.07.2012
Сообщений: 1,974
Завершенные тесты: 3
27.10.2012, 23:47     Поиск наименьших двух элементов массива или алгоритм Хаффмана #13
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
ТС говорил, что он даже структуры не знает. А тут классы...
Да, там классы и немного STL. Но может быть, понятнее станет сам принцип формирования дерева. Там даже пару комментариев есть.
Yandex
Объявления
27.10.2012, 23:47     Поиск наименьших двух элементов массива или алгоритм Хаффмана
Ответ Создать тему
Опции темы

Текущее время: 06:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru