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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Rebel123
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12
#1

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

27.10.2012, 22:40. Просмотров 1117. Ответов 12
Метки нет (Все метки)

Приветствую!

Дали задачу, сделать прогу в котором изначально есть массив из 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++ Найдите количество наименьших элементов массива
C++ Определить индексы и значения наибольших и наименьших по модулю элементов одномерного массива
Определить значения двух наименьших элементов вектора C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
27.10.2012, 22:55     Поиск наименьших двух элементов массива или алгоритм Хаффмана #2
Тут дерево надо строить. А не просто два наименьших элемента искать
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
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
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
27.10.2012, 23:06     Поиск наименьших двух элементов массива или алгоритм Хаффмана #5
сделай тег CPP /CPP, читается сейчас хуже, чем без тегов
Rebel123
1 / 1 / 0
Регистрация: 06.05.2012
Сообщений: 12
27.10.2012, 23:08  [ТС]     Поиск наименьших двух элементов массива или алгоритм Хаффмана #6
Точнее не следующий, а вообще, из всех элементов, если нету элемента больше или равен тому, к которому будет прибавляться (0,03), тогда дерево строится снова, берутся два наименьших.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 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
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
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
27.10.2012, 23:22     Поиск наименьших двух элементов массива или алгоритм Хаффмана #9
Цитата Сообщение от Rebel123 Посмотреть сообщение
P.P.S. не работал со структурами если честно =(
А зачем за Хаффмана взялся? Рановато.
Почитай эту тему.Хаффман с++
John Prick
764 / 697 / 126
Регистрация: 27.07.2012
Сообщений: 1,988
Завершенные тесты: 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
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
27.10.2012, 23:34     Поиск наименьших двух элементов массива или алгоритм Хаффмана #11
Цитата Сообщение от John Prick Посмотреть сообщение
Но может быть, поможет и тут.
Это так, но ТС говорил, что он даже структуры не знает. А тут классы...
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++
Вывести два наименьших числа из массива в N-элементов C++
подсчитать количество наибольших и наименьших элементов массива C++

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

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

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