Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.03.2019, 05:26   #1
rzjanin
Новичок
Джуниор
 
Регистрация: 10.03.2019
Сообщений: 2
По умолчанию Хаффман - реализацию дерева Хаффмана - код к олимпиадных задачам

Код:
#include <bits/stdc++.h>
using namespace std;
  string basik;
string c( int value, int bts)
{
    bool found = false;
        string res;
    const int bits = bts;
    bool sk = false;
    for (int cb = bits - 1; cb  >= 0; cb--)
    {
        if ((value & (1 << cb )) != 0)
        {
            if (!found)
                found = true;
            res += '1';
        }
        else
        {
                res += '0';
        }
    }

    return res;
}
void printImage(string s) {
    int k = 1;
for (int i = 0; i < s.size(); i++) {

    cout << s[i];
    if (k%100 == 0 && k !=5100)
        cout << endl;
    k++;
  }

}
void getImage() {
    for (int i = 0; i < 51; i++){
        string x;
        cin >> x;
        basik+=x;
   }
}

class Node
{
	public:
	 int a;
	 string c;
	 Node *left, *right;
	 Node(){left=right=NULL;}
	 Node(Node *L, Node *R)
	 {  left =  L;
	    right = R;
	    a = L->a + R->a;  }
};
struct oversort
{
    bool operator()(const Node* l, const Node* r) const { return l->a < r->a; }
};
vector<bool> code;
int bistrtoint(char *x) {
    int ans = (int)strtol(x, NULL, 2);
    return ans;
}
map<string,vector<bool> > table;
void build(Node *rt)
{
    if (rt->left!=NULL)
                      { code.push_back(0);
                      build(rt->left);}
    if (rt->right!=NULL)
                       { code.push_back(1);
                       build(rt->right);}
    if (rt->left==NULL && rt->right==NULL) table[rt->c]=code;
    code.pop_back();
}
string dec(string &str, map<vector<bool>, string> &table1)
{
	string out = "";
	vector<bool> code;
	for (int i = 0; i < str.length(); i++)
	{
		code.push_back(str[i] == '0' ? false : true);
		if (table1.count(code))
		{
			out += table1[ code ];
			code.clear();
		}
	}
	return out;
}
string er (string x, int n) {
  x.erase(x.begin(),x.end()-x.size()+n);
  return x;
}
string strght(string s) {
     while (s.size()!=5100) {
        s.erase(s.begin() + s.size()-1, s.end());
   }
   return s;
}
int main() {
  int mode;
  cin >> mode;
  if (!mode) {
  int minsize = 1e9;
  string best;
  getImage();
  int bestval = 0;
    for (int val = 4; val <=20; val++) {
 string  s=basik;
  while (s.size()%val!=0)
    s+='0';
  vector<string> strvallist;
 map<string,int>often;
   for (int i = 0; i < s.size(); i+=val) {
    string c;
    for (int j = i; j< i+val;j++)
        c+=s[j];
    strvallist.push_back(c);
    often[c]++;
   }
   list<Node*> t;
   map<string,int>::iterator itr;
   for( itr=often.begin(); itr!=often.end(); ++itr)
   {
      Node *p = new Node;
      p->c = itr->first;
      p->a = itr->second;
      t.push_back(p);
      }
     bool manychar = true;
     if (t.size()==1)
       manychar = false;
while (t.size()!=1)
  {
     t.sort(oversort());
     Node *SonL = t.front();
     t.pop_front();
     Node *SonR = t.front();
     t.pop_front();
     Node *parent = new Node(SonL,SonR);
     t.push_back(parent);

  }
if (manychar){
  Node *root = t.front();
   build(root);
} else {
   vector<bool> tempc;
   tempc.push_back(0);
   table[strvallist[0]] = tempc;
}
   map<string, vector<bool> >::iterator it;
 vector<bool>::iterator ii;
 string tablecode = "";
 int sizetablecode = 0;
 for (it = table.begin(); it != table.end(); it++)
 {
     sizetablecode++;
  tablecode += it->first;
  string temp = "";
  int kount = 0;
  for (ii = table[it->first].begin(); ii != table[it->first].end(); ii++) {
   int t = (*ii);
   kount++;
   temp += t+'0';
  }
  tablecode += c(kount,4);
  tablecode += temp;
 }

  map<string, vector<bool> >::iterator iii;
  map<string,int>::iterator iof = often.begin();
  cout << endl << endl << val << endl;
  for (iii = table.begin(); iii != table.end(); iii++) {
    cout << iii->first << " : ";
     vector<bool>::iterator i;
   for (i = table[iii->first].begin(); i != table[iii->first].end(); i++)
     cout << *i;
   cout << " : " << iof->second;
   iof ++;
    cout << endl;
  }
 cout << endl << endl << endl;

 tablecode = c(val,5) + c(sizetablecode,12) + tablecode;
   string out = "";
	for (int i = 0; i < strvallist.size(); i++)
		for (int j = 0; j < table[strvallist[i]].size(); j++)
		{
			out += table[strvallist[i]][j] + '0';
		}
    string encodeds = out;
    int siz = out.size();
   map<vector<bool>, string> inverse;
	for (map<string, vector<bool> >::iterator i = table.begin(); i != table.end(); i++)
		inverse[i->second] = i->first;
	out = dec(out, inverse);
    string result = tablecode + encodeds;
table.clear();
if (result.size() < minsize) {
    minsize = result.size();
    best = result;
    bestval = val;
}
cout << endl << val << " " <<  often.size() << " " << siz << " " << tablecode.size() << endl;
code.clear();
    }
    cout << best;
    cout << endl << endl << endl << best.size() << " " << bestval  << endl;
  }
  else {
  string s;
  cin >> s;
  map<vector<bool>, string> vocabulary;
  char sizevalstring[8];
  string tempstr;
   for (int i = 0; i < 5; i++)  {
    tempstr+= s[i];
   }
   for (int i = 0; i < 5; i++)
    sizevalstring[i] = tempstr[i];
     int sizeval = bistrtoint(sizevalstring);
  s = er(s,5);
   char sizetabs[12];
   for (int i = 0; i < 12; i++)  {
    sizetabs[i] = s[i];
   }
   int sizetab = bistrtoint(sizetabs);
   s.erase(s.begin(), s.end()-s.size() + 12 );
  int j = 0;
  while (j < sizetab) {
    j++;
    string val = "";
     for (int i = 0; i < sizeval; i++)
       val += s[i];
    s = er(s, sizeval);
    char keysizes[9];
    for (int i = 0; i < 4; i++)  {
      keysizes[i] = s[i];
    }
    int keysize = bistrtoint(keysizes);
    s = er(s,4);
    string key = "";
    for (int i = 0; i < keysize; i++)
        key+=s[i];
    s = er(s,keysize);
    vector<bool> cod;
    for (int i = 0; i < key.size();i++){
        cod.push_back(key[i]-'0');
    }
    vocabulary[cod] = val;
  }
	s = dec(s, vocabulary);
	int k = 1;
  s = strght(s);
  printImage(s);
  }
	return 0;
}

Последний раз редактировалось Serge_Bliznykov; 10.03.2019 в 10:34.
rzjanin вне форума Ответить с цитированием
Старый 10.03.2019, 06:05   #2
Alar
Александр
Администратор
 
Аватар для Alar
 
Регистрация: 28.10.2006
Сообщений: 17,758
По умолчанию

В чём вопрос?

тег [code] убрал

так как в коде есть

out += table1[code];

и всё сбивается
Alar вне форума Ответить с цитированием
Старый 10.03.2019, 10:35   #3
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

тег [CODE] вернул
Serge_Bliznykov вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Коптеры - код к олимпиадных задачам - задача на составление конфигурации квадрокоптеров rzjanin Общие вопросы C/C++ 1 10.03.2019 06:08
(Pascal ABC) Алгоритм Хаффмана: создание дерева и кодов символов Abdelliamo Помощь студентам 1 14.12.2016 10:22
Несколько олимпиадных задач MooNDeaR Свободное общение 6 11.03.2012 07:18
Хаффман. stas45rus Помощь студентам 1 02.02.2012 13:12