Написать программу, которая строит дерево Хаффмана

@Anriuser · Регистрация: 18.10.2013

Студворк — интернет-сервис помощи студентам

Написать программу, которая строит дерево Хаффмана, записывает двоичные коды Хаффмана для
символов, определяет размер дерева (в битах и байтах), определяет размер входной и выходной
последовательности, делает вывод о степени компрессии (коэффициент сжатия).
5 5 5 5 5 5 5 5 5 5 5 5255 2 2 2 2 45 45 45 45 45198145 67 67 67 67 12 12 12 12.

Добавлено через 10 часов 44 минуты
помогите

Добавлено через 41 минуту
помогите

Добавлено через 19 минут
хелп народ

Добавлено через 9 минут
размер дерева ето конечное число на вершине, двоичные коды ето числа 0100 и так далее я так понимаю...
вывод о степени компрессии входную поделить на выходную вроде

Добавлено через 59 секунд
5 5 5 5 5 5 5 5 5 5 5 5255 2 2 2 2 45 45 45 45 45 198 145 67 67 67 67 12 12 12 12

вот входные даные

@andrey_f · 20.03.2015, 10:47

посмтотрите тут

@Anriuser · 22.03.2015, 19:41 **[ТС]**

Сообщение от dogg12

посмтотрите тут

да не, там почти ничегоне пишет

@tarasalk · 22.03.2015, 19:45

Сообщение от Anriuser

Никто не поможет можно закрывать тему

У вас вопросов нету потому что. А писать всю прогу конечно никому не хочется.

@Anriuser · 22.03.2015, 21:45 **[ТС]**

Сообщение от tarasalk

У вас вопросов нету потому что. А писать всю прогу конечно никому не хочется.

Не суть, дело в том что для некоторых ету программу за 15 мин, кто имел с таким дело уже

@Anriuser · 26.03.2015, 00:52 **[ТС]**

хм.... хотяб чтоб дерево строило и биты выводило бы норм также

@Prizrak86 · 26.03.2015, 00:54

час ночи, все спят

@Anriuser · 26.03.2015, 14:40 **[ТС]**

heh

@FesS92 · 26.03.2015, 15:21

Дерево Хаффмана может строится разными способами http://sernam.ru/book_sel.php?id=7
Вас интересует каноническое построение или любое?

Добавлено через 7 минут

Сообщение от Anriuser

определяет размер дерева (в битах и байтах)

Что значит "размер" дерева?
М.б. подразумевается длина дерева? Так это глубина самой длинной ветки.

Если общее количество элементов - так оно всегда одинаково и равно количеству символов в алфавите...

А байты могут получиться при просмотре самих структур хранения дерева - оно бессмысленно в данном контексте...

@Anriuser · 26.03.2015, 16:38 **[ТС]**

размер, ето конечная вершина дерева типа я так понимаю, например там вышло число 23 ето типо и есть размер както так

Добавлено через 5 минут
http://upload.wikimedia.org/wi... f_demo.gif вот пример построения

@FesS92 · 26.03.2015, 16:47

Сообщение от Anriuser

конечная вершина дерева

Если вы про корень дерева, то в российский учебниках он значит количество символов входящего сообщения

@Anriuser · 27.03.2015, 00:03 **[ТС]**

сслыка с вики типо вершина

Добавлено через 7 часов 9 минут
парни ето уже крайрний строк поможете?

@Anriuser · 27.03.2015, 03:30 **[ТС]**

Вообщем есть код, но он стоит не так как https://uk.wikipedia.org/wiki/... 0%BD%D0%B0.
Как переделать или же обьясните строится по исходнику Huffman-Code-CSharp-master.rar

Вот с етим уже хоть помогите как переделать по википедии или обьясните как он строит тут дерево...

@FesS92 · 27.03.2015, 09:54

Правильный алгоритм построения тут: http://habrahabr.ru/post/144200/

Там все подробно описано.

Сообщение от Anriuser

парни ето уже крайрний строк поможете?

Тут Вы правильно написали. Помочь Вам многие захотят, но писать полностью код желающих, видимо, не нашлось.

Задавайте конкретные вопросы, на них ответят.

@Anriuser · 27.03.2015, 10:02 **[ТС]**

так я и задал проверьте прогу выше прикрепил и обьясните как строится дерево, оно строится по другому

@FesS92 · 27.03.2015, 11:14

алгоритм построения дерева у Вас тут:

C#
1
2
3
4
5
6
7
8
9
10
11
12
public void getTreeFromList(List<HuffmanNode> nodeList)
{
    while (nodeList.Count > 1)  // 1 because a tree need 2 leaf to make a new parent.
    {
        HuffmanNode node1 = nodeList[0];    // Get the node of the first index of List,
        nodeList.RemoveAt(0);               // and delete it.
        HuffmanNode node2 = nodeList[0];    // Get the node of the first index of List,
        nodeList.RemoveAt(0);               // and delete it.
        nodeList.Add(new HuffmanNode(node1, node2));    // Sending the constructor to make a new Node from this nodes.
        nodeList.Sort();        // and sort it again according to frequency.
    }
}

Он построен по классическому алгоритму (ссылка на хабр или в учебнике).

Ваш вариант с википедии, честно говоря, мне не понятен (помните, кто википедию пишет?)...

Добавлено через 6 минут
Для заполнения кодов в узлах используется рекурсивная процедура обхода дерева:

C#
1
2
3
4
5
6
7
8
9
10
11
12
public void setCodeToTheTree(string code, HuffmanNode Nodes)
{
    if (Nodes == null)
        return;
    if (Nodes.leftTree == null && Nodes.rightTree == null)
    {
        Nodes.code = code;
        return;
    }
    setCodeToTheTree(code + "0", Nodes.leftTree);
    setCodeToTheTree(code + "1", Nodes.rightTree);
}

Добавлено через 6 минут
В-общем, программа, которую вы нашли, вполне работоспособна. Можете её сдавать)

Добавлено через 8 минут

Сообщение от Anriuser

определяет размер дерева (в битах и байтах), определяет размер входной и выходной
последовательности, делает вывод о степени компрессии (коэффициент сжатия).

Осталось только дописать)

@Anriuser · 27.03.2015, 12:30 **[ТС]**

И ка же )))

@FesS92 · 27.03.2015, 13:29

Я думаю, что размер дерева - длина самой большой ветки (или самый длинный код). Тут уж можете перейти в биты и байты...

Размер входной строки можно взять после загрузки файла. Размер выходной строки - после перекодирования (или сумма по всем символам: длина битового кода символа * количество повторений символа в исходной строке).
Степень компрессии: Размер выходной строки / Размер входной строки.

Добавлено через 33 минуты

Не по теме:

Алгоритм Хаффмана - очень интересный алгоритм, который не остался одной лишь теорией, а нашел применение в жизни.
Если вам нужно, чтобы за вас написали "лабу", чтобы просто сдать её - вы попали не на тот форум. Помочь разобраться, подсказать - это всегда пожалуйста.. Но думать должны вы.
Если вы не хотите думать, может быть вам не имеет смысла изучать такие дисциплины и стоит задуматься о правильности выбора своей специальности?

@Anriuser · 28.03.2015, 00:11 **[ТС]**

Сообщение от FesS92

написали "лабу"

А мне разве ктото помог тут и написал "лабу" ?

@Баир · 28.03.2015, 09:37

я кстати тему создал, тоже сейчас эту лабу делаю, потом в теме исходники выложу

Добавлено через 2 минуты
Dictionary - как по key изменить value

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312

	Написать программу, которая строит дерево Хаффмана 13.03.2015, 00:30. Показов 3721. Ответов 21 Метки нет (Все метки) Написать программу, которая строит дерево Хаффмана, записывает двоичные коды Хаффмана для символов, определяет размер дерева (в битах и байтах), определяет размер входной и выходной последовательности, делает вывод о степени компрессии (коэффициент сжатия). 5 5 5 5 5 5 5 5 5 5 5 5255 2 2 2 2 45 45 45 45 45198145 67 67 67 67 12 12 12 12. Добавлено через 10 часов 44 минуты помогите Добавлено через 41 минуту помогите Добавлено через 19 минут хелп народ Добавлено через 9 минут размер дерева ето конечное число на вершине, двоичные коды ето числа 0100 и так далее я так понимаю... вывод о степени компрессии входную поделить на выходную вроде Добавлено через 59 секунд 5 5 5 5 5 5 5 5 5 5 5 5255 2 2 2 2 45 45 45 45 45 198 145 67 67 67 67 12 12 12 12 вот входные даные 0

@andrey_f 884 / 537 / 228 Регистрация: 21.02.2011 Сообщений: 5,705
	20.03.2015, 10:47
	посмтотрите тут 0

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	26.03.2015, 00:52 [ТС]
	хм.... хотяб чтоб дерево строило и биты выводило бы норм также 0

@Prizrak86 52 / 52 / 18 Регистрация: 20.03.2015 Сообщений: 278
	26.03.2015, 00:54
	час ночи, все спят 0

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	26.03.2015, 14:40 [ТС]
	heh 0

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	26.03.2015, 16:38 [ТС]
	размер, ето конечная вершина дерева типа я так понимаю, например там вышло число 23 ето типо и есть размер както так Добавлено через 5 минут http://upload.wikimedia.org/wi... f_demo.gif вот пример построения 0

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	27.03.2015, 00:03 [ТС]
	сслыка с вики типо вершина Добавлено через 7 часов 9 минут парни ето уже крайрний строк поможете? 0

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	27.03.2015, 03:30 [ТС]
	Вообщем есть код, но он стоит не так как https://uk.wikipedia.org/wiki/... 0%BD%D0%B0. Как переделать или же обьясните строится по исходнику Huffman-Code-CSharp-master.rar Вот с етим уже хоть помогите как переделать по википедии или обьясните как он строит тут дерево... 0

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	27.03.2015, 10:02 [ТС]
	так я и задал проверьте прогу выше прикрепил и обьясните как строится дерево, оно строится по другому 0

@Anriuser 0 / 2 / 1 Регистрация: 18.10.2013 Сообщений: 312
	27.03.2015, 12:30 [ТС]
	И ка же ))) 0

@FesS92 48 / 48 / 10 Регистрация: 22.02.2012 Сообщений: 137
	27.03.2015, 13:29
	Я думаю, что размер дерева - длина самой большой ветки (или самый длинный код). Тут уж можете перейти в биты и байты... Размер входной строки можно взять после загрузки файла. Размер выходной строки - после перекодирования (или сумма по всем символам: длина битового кода символа * количество повторений символа в исходной строке). Степень компрессии: Размер выходной строки / Размер входной строки. Добавлено через 33 минуты Не по теме: Алгоритм Хаффмана - очень интересный алгоритм, который не остался одной лишь теорией, а нашел применение в жизни. Если вам нужно, чтобы за вас написали "лабу", чтобы просто сдать её - вы попали не на тот форум. Помочь разобраться, подсказать - это всегда пожалуйста.. Но думать должны вы. Если вы не хотите думать, может быть вам не имеет смысла изучать такие дисциплины и стоит задуматься о правильности выбора своей специальности? 0

@Баир 18 / 18 / 9 Регистрация: 23.02.2015 Сообщений: 86
	28.03.2015, 09:37
	я кстати тему создал, тоже сейчас эту лабу делаю, потом в теме исходники выложу Добавлено через 2 минуты Dictionary - как по key изменить value 0