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

Псевдоалгоритм Хаффмана - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Непонятный синтаксис http://www.cyberforum.ru/cpp-beginners/thread368282.html
Вот есть обявление. sp<DataSource> source; sp<DataSource> это что? Спасибо!
C++ База данных для приемной комиссии института. Нужно составить простенькую программу с базой данных для приемной комиссии института. Выручайте... Она не должна быть какой - то мудреной. Это домашнее задание. Но в ней должна быть какая то графическая оболочка. Желательно описать что за что там отвечает. Просто с языком я не знаком. Базу данных я потом сам составлю. Я там должен буду вводить ФИО, телефон, курс, и группу на которую зачислен... http://www.cyberforum.ru/cpp-beginners/thread368271.html
C++ Нужны коментарии ко коду.
Все доброго времени! Такой вопрос, есть код, работает исправно, что делает тоже ясно. Часть я уже прокоментил, но с большей частью траблы.( Прокоментируйте кажду строку что б докладно понимать какая строка что делает и зачем. Очень признателен! std::ifstream ifile("read.txt");//Считывание с файла. std::ofstream ofile("write.txt");//Запись в файл. if(ifile.is_open()){ ...
C++ Как грамотно удалить элементы в векторе?
for (vector<fileResult>::iterator p = listExp.begin(); p != listExp.end();p++) { if (p->select) listExp.erase(p); } делаю так. fileResult - структура. fileResult listExp; p->select - некоторое поле в структуре ,Если оно true. То из вектора надо удалить этот элемент.
C++ не могу найти ошибку в поиске по массиву структур http://www.cyberforum.ru/cpp-beginners/thread368243.html
Здравствуйте. Дали задание: Дан массив структур. Каждая структура содержит информацию о книгах в библиотеке (придумать 5 полей структуры). Создать свои пользовательские функции. Первая из них осуществляет поиск информации по введенному запросу. Вторая - выводит результат на экран. Реализовать, используя указатели на массив структур. На этапе написания поиска информации по введёному запросу...
C++ Кеш процессора Задание Написать программу, многократно выполняющую чтение элементов массива заданного размера. Элементы массива должны представлять собой связный циклический список, в котором значение очередного элемента представляет собой номер следующего. Тип элементов массива: 4-байтовый целый. Построить графики зависимости среднего времени обращения к элементу массива от числа фрагментов N. Использовать... подробнее

Показать сообщение отдельно
nikola166
8 / 8 / 0
Регистрация: 18.03.2010
Сообщений: 142

Псевдоалгоритм Хаффмана - C++

18.10.2011, 15:05. Просмотров 932. Ответов 2
Метки (Все метки)

есть алгоритм

n – количество символов исходного алфавита
P – массив вероятностей, упорядоченных по убыванию
C – матрица элементарных кодов
L – массив длин кодовых слов
Huffman (n,P)
IF (n=2) C [1,1]:= 0, L [1]:= 1
C [2,1]:=1, L [2]:=1
ELSE q:= P [n-1]+P [n]
j:= Up (n,q) (поиск и вставка суммы)
Huffman (n-1,P)
Down (n,j) (достраивание кодов)
FI

Функция Up (n,q) находит в массиве P место, куда вставить число q, и вставляет его, сдвигая вниз остальные элементы.

DO (i=n-1, n-2,…,2)
IF (P [i-1]≤q) P [i]:=P [i-1]
ELSE j:=i
OD
FI
OD
P [j]:= q

Процедура Down (n,j) формирует кодовые слова.

S:= C [j,*] (запоминание j-той строки матрицы элем. кодов в массив S)
L:= L[j]
DO (i=j,…,n-2)
C [i,*]:= C[i+1,*] (сдвиг вверх строк матрицы С)
L [i]:=L [i+1]
OD
C [n-1,*]:= S, C [n,*]:= S (восстановление префикса кодовых слов из м-ва S)
C [n-1,L+1]:=0
C [n,L+1]:=1
L [n-1]:=L+1
L [n]:=L+1
Здесь я понимаю все кроме процедуры Down(n,j)
т.е конкретно
C [n-1,L+1]:=0
C [n,L+1]:=1
как такое можно написать если L- массив

Добавлено через 1 час 16 минут
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
class A
{
 
 
 
 
 
    double[] P1 = { 0.062, 0.014, 0.038, 0.013, 0.025, 0.072, 0.072, 0.007, 0.016, 0.062, 0.010, 0.028, 0.035, 0.026, 0.053, 0.090, 0.023, 0.040, 0.045, 0.053, 0.021, 0.002, 0.009, 0.004, 0.012, 0.006, 0.003, 0.014, 0.003, 0.014, 0.003, 0.006, 0.018 };
    char[] Alpha = { 'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ё', 'Ж', 'З', 'И', 'Й', 'К', 'Л', 'М', 'Н', 'О', 'П', 'Р', 'С', 'Т', 'У', 'Ф', 'Х', 'Ц', 'Ч', 'Ш', 'Щ', 'Ъ', 'Ы', 'Ь', 'Э', 'Ю', 'Я' };
 
    string[] Res = new string[33];
   
 
 
    public void Sort()
    {
        for (int i = 0; i < P1.Length; i++)
        {
            for (int j = 0; j < P1.Length - i - 1; j++)
            {
                if (P1[j] < P1[j + 1])
                {
                    char temp2;
                    double temp1 = 0;
 
                    temp1 = P1[j];
                    temp2 = Alpha[j];
                    P1[j] = P1[j + 1];
                    Alpha[j] = Alpha[j + 1];
                    P1[j + 1] = temp1;
                    Alpha[j + 1] = temp2;
 
                }
            }
        }
    }
 
    public void Down(int n, int j)
    {
        string S;
        //S:= C [j,*]  //запоминание j-той строки матрицы элем. кодов в массив S) 
        S = Res[j];
        for (int i = j; i <= n - 2; i++)
        {
           
            Res[i] = Res[i + 1]; //(сдвиг вверх строк матрицы С)
 
        }
      
        Res[n - 1] = S;
      
        Res[n] = S;
        Res[n - 1] += Convert.ToString(0);
        Res[n] += Convert.ToString(1);
        
 
    }
   
    public int Up(int n, double q)
    {
       
        int j = 0;
 
        for (int i = n - 1; i >= 2; i--)
        {
            if (P1[i - 1] <= q)
                P1[i] = P1[i - 1];
            else
                j = i;
        }
        P1[j] = q;
        return j;
 
    }
    public void Haff(int n, double[] P)
    {
      
        double q;
        if (n == 2)
        {
            Res[1] += Convert.ToString(0);
            Res[2] += Convert.ToString(1);
 
        }
        else
        {
            q = Convert.ToDouble(P[n - 1]) + Convert.ToDouble(P[n]);
           int j= Up(n, q);
            Haff(n - 1,P);
            Down(n,j);
 
        }
    }
    public static void Main()
    {
 
        A ob = new A();
        ob.Sort();
         ob.Haff(32,ob.P1);
        
        for (int i = 0; i < 33; i++)
        {
 
          Console.WriteLine(ob.Alpha[i] + " " + ob.Res[i]);
            
         
 
 
        }
 
    }
}
в чем тут ошибка, вроде все по алгоритму а строит не то что надо, а надо чтобы построил коды для алфавита

Добавлено через 2 минуты
можно на С++ переписать, но здесь разницы никакой
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru