Форум программистов, компьютерный форум CyberForum.ru

Реализация алгоритма RLE - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.68
cflood
0 / 0 / 0
Регистрация: 24.06.2013
Сообщений: 37
25.06.2013, 19:31     Реализация алгоритма RLE #1
Есть задачка, надо реализовать две функции "закодировать" и "раскодировать" массив данных типа:

C++
1
char mass[] = {'a','a','a','a','c','b','b','k','b','b','b','b'};
В итоге нужно получить букву и количество её повторений, реализовать так сказать сжатие, например:

C++
1
{'a4','c1','b2','k1','b4'}
С С++ я работаю всего третий день, по этому многое еще непонятно, однако задача можно сказать реализована на 50%, получилось посчитать количество повторений у каждой из букв:
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
#include <iostream>
#include <stdio.h>
#include <tchar.h>
 
using namespace std;
 
void encode (char mass[], int size)
{
        int counter = 0;
        int recurring_count = 0;
        for (int i = 0; i < size; i++)
        {
            if (mass[i] != mass[i+1])
            {
                recurring_count++;
                cout << mass[i] << recurring_count; // вывод буквы и количества её повторений
                recurring_count = 0;
            } else {
                recurring_count++;
            }
        }
}
 
 
int main ()
{
        char data[] = {'a','a','a','a','c','b','b','k','b','b','b','b'};
        int size = sizeof(data)/sizeof(data[0]);
 
        encode(data, size);
        
        int wait;
        cin >> wait;
}
Проблему вызывает именно запись полученных данных в удобноиспользуемую форму, потому что mass[i] - char, а recurring_count - int.

Например на том же Javascript задачу удалось реализовать полностью за пару минут, с с++ мучаюсь второй день:
Javascript
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
<script>
 
function encode(data) {
    var recurring_count = 0;
    var encoded_mass = [];
    for (var i = 0; i < data.length; i++) {
        if (data[i] != data[i+1]) {
            recurring_count++;
            encoded_mass.push(data[i]+'.'+recurring_count); // как раз то место где в C++ использую для вывода cout
            recurring_count = 0;
        } else {
            recurring_count++;
        }
    }
    return encoded_mass;
}
 
function decode(data) {
    var decode_mass = [];
    for (var i = 0; i < data.length; i++) {
        var temp = data[i].split('.');
        
        for (var j = 0; j < temp[1]; j++) {
            decode_mass.push(temp[0]);
        }
    }
    return decode_mass;
 
}
 
var mass = ['a','a','a','a','c','b','b','k','b','b','b','b'];
var encode_result = encode(mass);
var decode_result = decode(encode_result);
alert(encode_result);
alert(decode_result);
 
</script>
Получается в функции encode на выходе мы имеем массив вида:
Код
буква.количество_повторений
буква.количество_повторений
буква.количество_повторений
буква.количество_повторений
Потом в decode разбиваем его при помощи split по символу "." и получаем массив где первый элемент буква, а второй количество повторений, ну и делаем из всего этого нужный нам первоначальный массив вида

Код
{'a','a','a','a','c','b','b','k','b','b','b','b'}
Подскажите пожалуйста как можно реализовать аналогичную задачу на C++.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.06.2013, 19:31     Реализация алгоритма RLE
Посмотрите здесь:

Реализация алгоритма C++
C++ реализация алгоритма кодирования
Реализация алгоритма Йена на С++ C++
C++ Реализация LCS алгоритма на с++
Реализация алгоритма FOREL C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
25.06.2013, 19:50     Реализация алгоритма RLE #2
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
void encode (char mass[], char* out, int size)
{
        int counter = 0;
        int recurring_count = 0;
        for (int i = 0; i < size-1; i++)
        {
            if (mass[i] != mass[i+1])
            {
                recurring_count++;
 
                out[counter++] = mass[i];
                out[counter++] = recurring_count+'0';
                //cout << mass[i] << recurring_count << '\n'; // вывод буквы и количества её повторений
                recurring_count = 0;
            } else {
                recurring_count++;
            }
        }
 
}
 
 
int main()
{
 
        char data[] = "qqqqwwwweerrrtr";
        int size = sizeof(data)/sizeof(data[0]);
 
 
        char * out = new char[size+1]();
 
        encode(data, out, size);
 
        std::cout << out;
 
        delete[] out;
 
    std::cin.get();
    return 0;
}
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,409
25.06.2013, 20:07     Реализация алгоритма RLE #3
Дело в том, что javascript - нетипизированный язык, а С++ строготипизированный.
'a' - char
'a1' - char[]
Вам надо из одномерного массива char получить двумерный (массив строк)
Вот по простому:
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
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
 
int main()
{
    char arr[] = {'a','a','a','a','c','b','b','k','b','b','b','b'};
    const int size = sizeof(arr); // узнаем размер массива
    int counter = 1;
 
    // узнаем количество переходов от одной буквы к другой
    for (int i=1; i < size; i++)
        if (arr[i-1] != arr[i])
            counter++; // увеличиваем счетчик
 
    // создаем новый массив под шифрованные данные
    char **newArr = new char*[counter];
    int equal = 1; // количество повторений буквы
    int index = 0; // индекс массива, в котором формируем новые
 
    // пробегаемся по массиву и заталкиваем значения
    for (int i=1; i < size; i++)
    {
        // если предыдущая буква неравна или буква последняя
        if (arr[i-1] != arr[i] || i == size - 1)
        {
            // узнаем размер необходимой строки (буква и её число повторений)
            int length = 2 + log10(equal);
            newArr[index] = new char[length + 1];
            // добавляем сначала букву, а затем число, преобразованное в char*
            // после сдвигаем индекс
            newArr[index][0] = arr[i-1];
            // записываем преобразованное число в 10-ричной системе в строку
            itoa(equal, &newArr[index++][1], 10);
            equal = 0;
        }
        equal++;
    }
 
    // выводим на экран результирующий массив
    for (int i=0; i < counter; i++)
    {
        std::cout << newArr[i] << std::endl;
        // освобождаем память
        delete [] newArr[i];
    }
    delete [] newArr;
}
cflood
0 / 0 / 0
Регистрация: 24.06.2013
Сообщений: 37
26.06.2013, 09:35  [ТС]     Реализация алгоритма RLE #4
Ребята благодарю за столь скорые ответы, покапаюсь

Добавлено через 13 часов 25 минут
Спасибо вам еще раз за помощь, хочу узнать еще кое что дописал decode:
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
#include <iostream>
#include <stdio.h>
#include <tchar.h>
 
using namespace std;
 
void encode (char mass[], char * out, int size)
{
        int counter = 0;
        int recurring_count = 0;
        for (int i = 0; i < size; i++)
        {
            if (mass[i] != mass[i+1])
            {
                recurring_count++;
                out[counter++] = mass[i];
                out[counter++] = recurring_count+'0';
                recurring_count = 0;
            } else {
                recurring_count++;
            }
        }
}
 
void decode (char mass[], char * out, int size)
{
        int counter = 0;
        for (int i = 0; i < size; i++)
        {
            if (i & 1)
            {
                int num = mass[i]-'0';
                for (int j = 0; j < num; j++) {
                    out[counter++] = mass[i-1];
                }
            }
        }
}
 
 
int main ()
{
        char data[] = {'a','a','a','a','a','c','b','b','c','c','g','k','b','b','b','b'};
        int size = sizeof(data)/sizeof(data[0]);
 
        char * encode_out = new char[size]();
        char * decode_out = new char[size]();
 
        encode(data, encode_out, size);
        cout << encode_out;
        cout << "\n";
        decode(encode_out, decode_out, size);
        cout << decode_out;
 
        int wait;
        cin >> wait;
}
Всё отлично только вот по какой-то, пока мне непонятной причине, в выводе я вижу следующее:

C++
1
2
a5c1b2c2g1k1b4
aaaaacbbccgkbbbb****ллллллллю|ю|
Подскажите из-за чего выдаёт эту лишнюю белиберду.
nxtech
77 / 59 / 2
Регистрация: 26.06.2013
Сообщений: 198
26.06.2013, 09:43     Реализация алгоритма RLE #5
Не разбирался особо, но видимо нет завершающего нуля в decode_out.
Попробуй дописать после char * decode_out = new char[size]();
decode_out[size-1] = '\0';

Добавлено через 3 минуты
И, по хорошему, стоит добавить в конце main
C++
1
2
3
delete[] encode_out;
delete[] decode_out;
return 0;
cflood
0 / 0 / 0
Регистрация: 24.06.2013
Сообщений: 37
26.06.2013, 09:43  [ТС]     Реализация алгоритма RLE #6
nxtech, каким образом можно это сделать? Например так?

C++
1
decode_out[size] = '\0'; //собственно сработало
Или можно сделать как нибудь по эстетичнее?
nxtech
77 / 59 / 2
Регистрация: 26.06.2013
Сообщений: 198
26.06.2013, 09:46     Реализация алгоритма RLE #7
Да так нормально. Можно тоже самое в decode сделать (для mass[]), возможно это эстетичнее
Недосмотрел. Это не правильно:
C++
1
decode_out[size] = '\0';
Нужно:
C++
1
decode_out[size-1] = '\0';
Иначе за границы массива выходишь, индекс с 0 начинается.
cflood
0 / 0 / 0
Регистрация: 24.06.2013
Сообщений: 37
26.06.2013, 09:54  [ТС]     Реализация алгоритма RLE #8
nxtech, да щас туда как раз и влепил это, спасибо

Добавлено через 7 минут
с size-1 кстати неработает
nxtech
77 / 59 / 2
Регистрация: 26.06.2013
Сообщений: 198
26.06.2013, 10:20     Реализация алгоритма RLE #9
Цитата Сообщение от cflood Посмотреть сообщение
nxtech, да щас туда как раз и влепил это, спасибо

Добавлено через 7 минут
с size-1 кстати неработает
Видимо потому, что вы не правильно вычисляете размер буфера:
C++
1
2
char data[] = {'a','a','a','a','a','c','b','b','c','c','g','k','b','b','b','b'};
int size = sizeof(data)/sizeof(data[0]);
Не учитывается место для завершающего нуля.
Нужно так:
C++
1
int size = sizeof(data)/sizeof(data[0]) + 1;
Но если вы измените size, тогда потребуется корректировка в индексов циклах в функциях encode и decode.

Если у вас размер буфера size, то последний элемент (для Си-строки это завершающий нуль) должен располагаться по индексу size-1. Иначе выход за пределы буфера и UB (неопределенное поведение).

Сейчас проверю

Добавлено через 11 минут
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
#include <iostream>
#include <stdio.h>
#include <tchar.h>
 
using namespace std;
 
void encode (char mass[], char * out, int size)
{
    int counter = 0;
    int recurring_count = 0;
    for (int i = 0; i < size; i++)
    {
        if (mass[i] != mass[i+1])
        {
            recurring_count++;
            out[counter++] = mass[i];
            out[counter++] = recurring_count+'0';
            recurring_count = 0;
        } else {
            recurring_count++;
        }
    }
}
 
void decode (char mass[], char * out, int size)
{
    int counter = 0;
    for (int i = 0; i < size; i++)
    {
        if (i & 1)
        {
            int num = mass[i]-'0';
            for (int j = 0; j < num; j++) {
                out[counter++] = mass[i-1];
            }
        }
    }
}
 
 
int main ()
{
    char data[] = {'a','a','a','a','a','c','b','b','c','c','g','k','b','b','b','b'};
    int size = sizeof(data)/sizeof(data[0]);
 
    // Выделяем буферы с учетом места для завершающего нуля.
    char * encode_out = new char[size + 1]();
    char * decode_out = new char[size + 1]();
 
    // Добавляем в конце буферов завершающие нули.
    encode_out[size] = '\0';
    decode_out[size] = '\0';
 
    encode(data, encode_out, size);
    cout << encode_out;
    cout << "\n";
    decode(encode_out, decode_out, size);
    cout << decode_out;
 
    int wait;
    cin >> wait;
 
    delete[] encode_out;
    delete[] decode_out;
 
    return 0;
}
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
26.06.2013, 10:26     Реализация алгоритма RLE #10
Цитата Сообщение от MrGluck Посмотреть сообщение
'a' - char
'a1' - char[]
ой ли? https://ideone.com/8mECc9
Для разъяснений: "multicharacter literal"
Цитата Сообщение от nxtech Посмотреть сообщение
Не учитывается место для завершающего нуля.
Почуйте разницу: https://ideone.com/wToZ0p
nxtech
77 / 59 / 2
Регистрация: 26.06.2013
Сообщений: 198
26.06.2013, 10:29     Реализация алгоритма RLE #11
Цитата Сообщение от Tulosba Посмотреть сообщение
ой ли? https://ideone.com/8mECc9
Для разъяснений: "multicharacter literal"

Почуйте разницу: https://ideone.com/wToZ0p
И?...
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
26.06.2013, 10:50     Реализация алгоритма RLE #12
Цитата Сообщение от nxtech Посмотреть сообщение
И?...
Если инициализируете массив char строкой, т.е. с двойными кавычками, то добавляется нуль-терминатор.
Если набором символов (одинарные кавычки), то не добавляется.
Или Вас что-то другое интересует?
nxtech
77 / 59 / 2
Регистрация: 26.06.2013
Сообщений: 198
26.06.2013, 10:54     Реализация алгоритма RLE #13
Ну, я об этом знал и даже указал, что место для завершающего нуля нет. Так что не понятно для чего вы мне все это указали.
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
26.06.2013, 10:59     Реализация алгоритма RLE #14
Хм-м. У Вас в примере инициализация списком символов:
Цитата Сообщение от nxtech Посмотреть сообщение
char data[] = {'a','a','a','a','a','c','b','b','c','c','g','k','b','b','b','b'}; int size = sizeof(data)/sizeof(data[0]);
А потом Вы говорите про какой-то завершающий нуль. Вот это для меня не ясно.
nxtech
77 / 59 / 2
Регистрация: 26.06.2013
Сообщений: 198
26.06.2013, 17:13     Реализация алгоритма RLE #15
Цитата Сообщение от Tulosba Посмотреть сообщение
А потом Вы говорите про какой-то завершающий нуль. Вот это для меня не ясно.
Tulosba, читать топик надо сначала и внимательно и будет вам ясность, а уже потом замечания раздавать.
Хочу вам сказать, что это не мой код, а ТС. А я уже его последний код помогаю исправить на более корректный с минимальными изменениями.
Про ваше замечание - я, по сути, на это ему и указал, что при таком определении (объявлении с инициализацией) нет завершающего нуля (просто массив char, а не Си-строка).
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
26.06.2013, 17:39     Реализация алгоритма RLE #16
Цитата Сообщение от nxtech Посмотреть сообщение
читать топик надо сначала и внимательно
Согласен Но сразу, всего не заметишь. Например, вот сейчас вижу у Вас в коде
Цитата Сообщение от nxtech Посмотреть сообщение
if (mass[i] != mass[i+1])
выход за пределы массива. Для проверки можно сделать минимальное исправление:
C++
1
int size = sizeof(data)/sizeof(data[0]) - 1; // Чтобы "элемент" за последним элементом совпадал
И посмотреть на результаты.
nxtech
77 / 59 / 2
Регистрация: 26.06.2013
Сообщений: 198
26.06.2013, 17:45     Реализация алгоритма RLE #17
Цитата Сообщение от Tulosba Посмотреть сообщение
Согласен Но сразу, всего не заметишь. Например, вот сейчас вижу у Вас в коде
выход за пределы массива. Для проверки можно сделать минимальное исправление:
C++
1
int size = sizeof(data)/sizeof(data[0]) - 1; // Чтобы "элемент" за последним элементом совпадал
И посмотреть на результаты.
Спасибо вам, сударь, за внимательность по отношению к коду. Это первое конструктивное замечание. Но только сейчас заметили!!!
Но спешу огорчить - код не мой, моих в нем пять с половиной строчек. На что я сразу обратил внимание, то и исправил. Повторяю, читайте внимательно топик, если хотите постебаться.
Tulosba
26.06.2013, 21:21
  #18

Не по теме:

@nxtech, могу и Вам дать совет: смотрите внимательнее на код, который копипастите.

nxtech
27.06.2013, 08:18
  #19

Не по теме:

@Tulosba, спасибо, учту. И вам совет, внимательнее читайте сообщения.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.06.2013, 09:57     Реализация алгоритма RLE
Еще ссылки по теме:

C++ Реализация алгоритма
C++ Реализация алгоритма Дейкстры
C++ Написать программу на основе алгоритма RLE (сжатие/восстановление массива)

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

Или воспользуйтесь поиском по форуму:
Catstail
Модератор
 Аватар для Catstail
21440 / 10225 / 1666
Регистрация: 12.02.2012
Сообщений: 17,100
27.06.2013, 09:57     Реализация алгоритма RLE #20
Цитата Сообщение от MrGluck Посмотреть сообщение
'a1' - char[]
- нет. Для C/C++ это запрещенная конструкция. Правильно "a1" - вот это действительно char[]
Yandex
Объявления
27.06.2013, 09:57     Реализация алгоритма RLE
Ответ Создать тему
Опции темы

Текущее время: 13:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru