Как организовать побитовую запись?

Пытаюсь реализовать алгоритм Хаффмана, который будет сжимать текстовый файл. Уже построено дерево tree, у которого есть:
tree->simvol // char в котором хранится сам символ (например 'a')
tree->code // string, двоичный код для этого символа (например 1001)

Мне нужно написать функцию, которая пройдется по исходному файлу, и будет считывать каждый символ, сверяя его с символами в моем дереве, а найдя нужный - запишет в новый файл последовательность единиц и нулей(tree->code).

Трудность именно в побитовой записи, т.к я не совсем представляю, как ее организовать. Поясню - мне нужно, чтобы ,например, последовательность 10011110 занимала именно 8 бит, т.е единица или ноль занимали бы 1 бит, иначе сжатия не получится(если я просто вместо буквы "а" запишу "1001" как набор символов, а не битов).

void shifr(){
	ifstream myfile("file.txt");//открыли файл
	char ch;
	if (!myfile.is_open()) // если файл не открыт
     	   cout << "Файл не может быть открыт!\n"; // сообщить об этом
	else
	{
		while (myfile.get(ch))//проходимся посимвольно по всему текстовому файлу
		{
		find_char(ch);//находим нужный символ в дереве и записываем код этого символа в новый файл
		}	
		myfile.close();
	}
}

void find_char(spisok *&tree, char ch) {//рекурсивный обход дерева и поиск в нем символа
	if (tree->left==NULL && tree->right==NULL && tree->simvol==ch) {
		//???
		//вот тут нужно как-то записать код из tree->code в новый файл...
		//???
	}
	if (tree->left!=NULL) {
		find_char(tree->left,ch);
	}
	if (tree->right!=NULL) {
		find_char(tree->right,ch); 
	}
}
  • Вопрос задан
  • 5800 просмотров
Решения вопроса 2
Можно создать переменную типа char и переключать в ней отдельные биты с помощью побитового или
char result = 0;
// допустим, что код - 8 бит
for (char* x = tree->code, int y = 0; *x != '\0'; x++, y++)
    if (*x == '1')
        *x |= 1 << (8 - y);
Ответ написан
Комментировать
deadrime
@deadrime Автор вопроса
В общем очень много где искал и в итоге нашел несколько способов, хотя как по мне все они не особо удобные.
Надеюсь помогу кому-нибудь, а то сам довольно долго разбирался что да как.

Самая простая - создать структуру байта и описать в ней каждый бит.
Причем максимально верно, как я понял, так это сделать это через объединения, хотя я еще не совсем в этом разобрался.

struct Bits
{
    unsigned b0:1, b1:1, b2:1, b3:1, b4:1, b5:1, b6:1, b7:1;
};
union CBits
{
    Bits bits;
    unsigned char byte;
};


В этом случае записать 1 байт можно например вот так -

void write_bait(FILE* out, string code) { 
	CBits byte;
	byte.bits.b0=(code[0]=='1') ? 1:0;//тоже самое что и if(code[0]=='1') byte.bits.b0=1; else byte.bits.b0=0;
        .................
	byte.bits.b7= (code[7]=='1') ? 1:0;
	fwrite(&byte,sizeof(one_byte),1,out);
}


Второй способ - преобразовать массив boolean в unsigned char и "побитовым или" писать в нужный бит 1
Если я правильно понял - c = c | (1 << 7); - это запись в 7-й разряд, т.е
00000000
00000010
____________
00000010
и с = 2^7 = 128

а
(c & (1<<7)) != 0) - это проверка на 1 в 7-м разряде
т.е
00000111
00000010
___________
00000010
результат !=0, значит есть единица в 7-м разряде.

void BoolToByte(FILE *file, bool b[8])
{
    unsigned char c = 0;
    for (int i=0; i < 8; ++i)
        if (b[i])
		{
            c = c | (1 << i);
		}
    fwrite(&c,1,1,file);
    return;
}

и
void BoolFromByte(FILE *file, bool b[8])
{
	unsigned char c;
	fread(&c,1,1,file);
    for (int i=0; i < 8; ++i)
		if ((c & (1<<i)) != 0) b[i] = true;
}


Мне же удобно было держать коды в string , поэтому я переделал под нее -

void ToByte(FILE *file, string &b)
{
    unsigned char c = 0;
    for (int i=0; i < 8; ++i) 
		{
			if (b[i]=='1') 
			{
				c = c | (1 << i);
			}
		}
    fwrite(&c,1,1,file);
    return;
}

и
void FromByte(FILE *file , string &b)
{
	unsigned char c;
	fread(&c,1,1,file);
    for (int i=0; i < 8; ++i)
		if ((c & (1<<i)) != 0) b[i] = '1';	
}


Еще есть вариант, но я до него не дошел - это писать все непосредственно в буфер, а потом записывать весь буфер целиком, а не по байтам, как я.

В общем как-то так, поправьте меня, если где ошибся или можно улучшить/сократить функцию..
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
AtomKrieg
@AtomKrieg
Давай я поищу в Google за тебя
1) Пишите байты в vector<bool> (решение тривиально)
2) Пишите vector<bool> в файл (решение есть в интернете)
Ответ написан
Комментировать
@mikhail_404
И никогда не используйте
std::vector <bool>
alenacpp.blogspot.ru/2005/06/vector.html
Совет #18 (Мейерс)!
Можно, например, в инте все хранить или, на крайний случай, std::bitset.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы