С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
21 / 21 / 3
Регистрация: 24.05.2014
Сообщений: 1,058
1

Алгоритм Хаффмана. Поле текущего элемента структуры изменяется уже после перехода на следующий

23.12.2019, 20:42. Показов 853. Ответов 9
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Для примера ввёл слово "слово", функция составления дерева сработала идеально, и выдала это. Однако функция MakeTable работает как-то не так, она создаёт таблицу
Л – 11
В – 11
С – 10
О – 0
А должна:
Л – 111
В – 110
С – 10
О – 0

При просмотре откладке я обнаружил странную вещь – после дохода до (tr->val != 0), в Л ложится код 111, однако после создания следующего столбца таблицы (table* New = new table;) и перехода к нему (tb = tb->next;), после удаления последнего символа из кода, новый код каким-то образом привязывается к Л и только потом отлипает. Почему так получается?
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
struct binary {
    bool val;
    binary* next;
    binary* perv;
};
binary* start;
 
void add(binary*& b, bool o) {
    binary* New = new binary;
    New->val = o; New->next = NULL;
    if (b) {
        b->next = New;
        New->perv = b;
        b = b->next;
    }
    else {
        b = New;
        start = b;
        b->perv = NULL;
    }
    b->next = NULL;
}
 
//====================================================================Таблица Хаффмана
struct table {
    binary code;
    unsigned char letter;
    table* next;
};
table* firsT; //Первая строка таблицы
 
void MakeTable(table*& tb, tree*& tr, int symbols_count) {
    binary* code = new binary; code = NULL;
        while (tr) {
            if (tr->right) {
                add(code, 1);
                tr = tr->right;
            }
            else
                if (tr->left) {
                    add(code, 0);
                    tr = tr->left;
                }
                else {
                    if (tr->val != 0) {
                        tb->code = *start; //firsT->letter = Л, firsT->code = 111
                        tb->letter = tr->val;
                        if (tr->parent) {
                            symbols_count--;
                            delLeave(tr, tr->parent->right); 
 
                            if (symbols_count != 0) {
                                table* New = new table;
                                tb->next = New;
                                tb = tb->next;
 
                                if (code->perv) { code = code->perv; code->next = NULL; } //firsT->letter = Л, firsT->code = 11
                                    else code = NULL;
 
                            }
                            else {
                                tb->next = NULL;
                            }
                        }
                        else { tr = NULL; clr(син); printf("Сверхъестественная ошибка: буква является корнем дерева");  clr();}
                    }
                    else {
                        if (tr->parent) {
                            delLeave(tr, tr->parent->right);
                            if (code->perv) { code = code->perv; code->next = NULL; }
                            else code = NULL;
                        }
                        else { tr = NULL;  }
                    }
                }
        }
    tb = firsT;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Блог
23.12.2019, 20:42
Ответы с готовыми решениями:

Алгоритм Хаффмана, реализация через структуры
Добрый день, помогите пожалуйста найти ошибку в построении кодов Хаффмана. использую следующие...

Изъять из списка L после каждого вхождения элемента E1 следующий элемент
Уважаемые мастера, прошу помощи в создании программы до динамическим структурам, т.к. вообще ничего...

Добавить поле из элемента управления в word файл с уже имеющейся инфой
Здравствуйте, помогите пожалуйста доработать код для того что бы он действовал и мог осуществлять ...

Не могу придумать алгоритм как сделать чтоб при нажатии на кнопку в поле едит (уже выведенному в нем числу)добавлялась е
Не могу придумать алгоритм как сделать чтоб при нажатии на кнопку Вutton1 в поле едит (уже...

9
21 / 21 / 3
Регистрация: 24.05.2014
Сообщений: 1,058
01.01.2020, 16:16  [ТС] 2
вопрос ещё актуален
0
85 / 34 / 20
Регистрация: 15.12.2019
Сообщений: 88
01.01.2020, 16:47 3
Мб, названия библиотек напишите, а то даже и не знаю как это проверять в ide.
0
21 / 21 / 3
Регистрация: 24.05.2014
Сообщений: 1,058
01.01.2020, 18:52  [ТС] 4
В данном кусочке кода не используются никаких библиотек. Я могу скинуть весь код, если нужно
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
01.01.2020, 19:49 5
Цитата Сообщение от Титан_1 Посмотреть сообщение
после удаления последнего символа из кода, новый код каким-то образом привязывается к Л
Если я правильно понял, у тебя используется один и тот же список для хранения кодов разных символов. Т.е. разные символы у тебя ссылаются на один и тот же список (или части этого списка). Соответственно, редактирование кода одного символа может неожиданно поменять код другого.

Первым делом перепиши свой код так, чтобы не было глобальных переменных start и firsT. Именно с их помощью ты в своем коде творишь какую-то фигню. Во вторых, копируй весь список с кодом, а не только его первый элемент (это я про твой tb->code = *start;).
0
199 / 155 / 45
Регистрация: 11.11.2019
Сообщений: 348
01.01.2020, 20:12 6
Строка 33 выделяете память и тут же обнуляете указатель
0
21 / 21 / 3
Регистрация: 24.05.2014
Сообщений: 1,058
01.01.2020, 20:17  [ТС] 7
nonedark2008, tb->code = *start; – это и есть копирование всего списка с кодом: *start указывает на первый элемент, у первого элемента храниться указатель на следующий и тд
struct table {
binary code;
– у каждого table есть свой binary. Если бы разные таблицы ссылались на один и тот же список, в выводе у меня бы всем символам показывался один и тот же код, но это не так
unsigned char letter;
table* next;

};
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
01.01.2020, 21:12 8
Цитата Сообщение от Титан_1 Посмотреть сообщение
это и есть копирование всего списка с кодом
Ты ошибаешься. В твоем примере tb->code->next и start->next будут указывать на один и тот же элемент списка. Если ты в этом элементе что-либо поменяешь, то он изменится и для start->next, и для tb->code->next. Так что тут нет никакого копирования всего списка.

Ну и как бонус: в твоем примере tb->code->next->perv будет указывать не на tb->code, а на start.

Добавлено через 7 минут
Цитата Сообщение от Титан_1 Посмотреть сообщение
Если бы разные таблицы ссылались на один и тот же список
Я и не говорю, что они ссылаются на один и тот же список. Я говорю, что твои списки местами ссылаются на одни и те же элементы.
0
21 / 21 / 3
Регистрация: 24.05.2014
Сообщений: 1,058
02.01.2020, 11:34  [ТС] 9
nonedark2008,
Цитата Сообщение от nonedark2008 Посмотреть сообщение
В твоем примере tb->code->next и start->next будут указывать на один и тот же элемент списка
Ну так и есть, start же указывает на начало списка

Очень странно, почему для "о" и "в" код правильный, а для "с" и "л" – нет. И раз уж tb->code->perv (на этапе, когда tr->val указывает на родителя "в", после удаления "л") прилипает к start, почему он отлипает от него после выполнения add(binary*& b, bool o)? Там на данном этапе b!=0 и, следовательно, со start ничего не происходит
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
02.01.2020, 12:20 10
Цитата Сообщение от Титан_1 Посмотреть сообщение
Ну так и есть, start же указывает на начало списка
Ну вот и получаешь то, что получаешь.
Вычислил ты код: code->1-1-1
Сохранил его для 'л'. Получил следующее:
Код
code->1-1-1
       /
'Л' ->1
При переходе к 'В' ты удаляешь у code хвост и дописываешь 0. Получаешь:
Код
'В' ->1
       \
code->1-1-0
       /
'Л' ->1
Там у тебя именно какая-то такая фигня происходит. Обработка следующих букв еще сильнее все испоганит. В подробности вдаваться не хочу.

Добавлено через 3 минуты
Цитата Сообщение от Титан_1 Посмотреть сообщение
Очень странно, почему для "о" и "в" код правильный, а для "с" и "л" – нет
Потому что твое дерево слишком примитивное, а твой алгоритм не портит ранее сохраненные коды длины 2.
1
02.01.2020, 12:20
BasicMan
Эксперт
19315 / 2622 / 84
Регистрация: 17.02.2009
Сообщений: 10,364
Блог
02.01.2020, 12:20
Помогаю со студенческими работами здесь

Создание кнопки для перехода на следующий монтажный кадр
Добрый день, уважаемые форумчане. Дело в том, что я не так хорошо знакома с ActionScript 3.0, но...

Как мне сделать чтобы после нахождения первого минимального элемента (напр mas[2;4]=4) следующий элемент начинал искаться с 4 строки ?
Ребят помогите плиз!! Дан массив например !! происходит поиск по массиву минимального элемента ...

Не изменяется IP домена уже 5 дней
Здравствуйте! Ситуация такая. Домен был настроен через одни NS-сервера. Сейчас приходится...

Постройте алгоритм и составьте программу, по которой будет реализован следующий сценарий:компьютер запрашивает номер дня недели, после ввода компьютер
Постройте алгоритм и составьте программу, по которой будет реализован следующий сценарий:компьютер...

Элементы структуры: неправильное значение после 10 элемента
При создании массива из собственной структуры, после 10 элемента, начинает неправильно заполняться...

На основе уже имеющегося списка создать новый, вставляя заданный элемент после каждого i-го элемента
Составить программу, которая на основе уже имеющегося списка создает новый, вставляя заданный...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru