Пишу алгоритм сжатия текстового документа методами Хаффмана и Шеннона-Фано.
Уже почти все готово - т.е создается дерево, по нему создаются коды для каждого символа и с их помощью кодируется текст.
Осталось только как-то записать и прочитать дерево, по которому можно будет расшифровать сообщение..
Вот структура для Шеннона-Фано:
struct spisok//список
{
char ch;//символ
string code;//код
double k;//вероятность
spisok *next;
}*myspisok=NULL;
struct tree //дерево
{
tree *left,*right;
spisok *s;//содержит в себе список
}*mytree=NULL;
Поясню - у каждого элемента дерева есть список, у листа этот список состоит всего из одного элемента, он то и нужен.
По сути можно вообще удалить все списки кроме списка у дерева.
Структура для Хаффмана вроде попроще -
struct spisok { //список деревьев FailFish
char simvol;
string code;
int kol;
spisok *next;
spisok *prev;
spisok *left;
spisok *right;
}*head,*sortlist,*tree;
Тут *next и *prev не нужны, нужно записать, как я думаю, только simvol,*left,*right
Как это можно провернуть?
Функция расшифровки по дереву у меня такая -
for(int i=0;i<final_code.length();i++)
{
if (k==size)//как только количество символов в расшифрованном файле будет равно количеству символов в исходном
{
break;
}
if (t->left == NULL && t->right == NULL)//дошли до листа
{
fwrite(&(t->s->ch),sizeof(char),1,decrypted);//записываем символ из листа
cout<<t->s->ch;//выводим его
t=head;//поднимаемся назад к голове
k++;
}
if (final_code[i]=='1') t=t->right;//если 1 - идем вправо
else t=t->left;//иначе - влево
}
Простой
