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

Группы анаграмм в строке - C++

Восстановить пароль Регистрация
 
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
19.11.2012, 13:49     Группы анаграмм в строке #1
Всем доброго времени суток.
Я в С++ начинающий.
Есть задача, которую не получается написать; не получается скорее по причине отсутствия нужных знаний... Пожалуйста, если кому-то не лень, объясните, как можно написать попроще. Искал на форуме подобную задачу, но решения сложны для понимания, да и задачи совсем не аналогичные.

Постановка задачи:
В строке найти все группы слов-анаграмм (слова, получаемые одно из другого перестановкой букв, например: автор, отвар, товар; кот, кто, ток – две группы анаграмм).
Присутствуют входной и выходной файлы. В первом записана строка со словами, разделёнными пробелом.
В выходной файл нужно вывести группы анаграмм; каждую группу в отдельную строку.

Пример:
в файле infile лежит строка:
секта автор рост весточка аскет товар сигара трос тесак отвар качество сорт месть ток свет сетка трос
после выполнения содержимое файла outfile будет таким:
секта аскет тесак сетка
автор товар отвар
рост трос сорт
весточка качество
Объясните, как это можно реализовать, пожалуйста. Буду благодарен.
Либо просто пошагово объясните этот код (не мой; не до конца понимаю его), если так будет легче (сомневаюсь думаю, у меня появится куча дополнительных вопросов).
C++ (Qt)
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define MAXLINE   1000   /* максимальная длина строки */
#define MAXWORDS  100    /* максимальное количество слов */
 
int CheckCharsLine(const char *l, const char *set); 
 
/* ищет анаграммы в файле
   и записывает их в ряд в другой файл */
main()    
{
    FILE *ifp, *ofp;
    char line[1000], *dup;
    char *words[100], *p, **w, **cur;
    long nwords, i, j;
    int first, printed;
    enum { NO, YES };
    const char *iname = "infile",
               *oname = "outfile";
    
    ifp = fopen(iname, "r");
    ofp = fopen(oname, "w");
    if (!(ifp && ofp)) {
        fprintf(stderr, "error: files" "\n");
        return 1;
    }
    
    if (!fgets(line, sizeof line, ifp)) {
        fprintf(stderr, "error: no line" "\n");
        return 2;
    }
    
    if (!(dup = malloc(strlen(line)+1))) {  
        fprintf(stderr, "error: memory" "\n");
        return 3;
    }    
        
    strcpy(dup, line);
    
    for (p = strtok(dup, " "), w = words; 
         p;
         p = strtok(NULL, " "))
        *w++ = p;
    
#if 1  
    printf("%s", line);
    printf("%ld" "\n", nwords);
#endif    
    
    for (cur = words, i = 0; i < nwords; i++, cur++) {
        first = YES;
        printed = NO;
        for (w = cur+1, j = i+1; j < nwords-1; j++, w++)
            if (CheckCharsLine(*w, *cur) > 0) {
                if (first == YES) {
                    fprintf(ofp, "%s" " ", *cur);
                    first = NO;
                }    
                fprintf(ofp, "%s" " ", *w);
                *w = '\0';
                printed = YES;
            }    
        if (printed == YES)
            putc('\n', ofp);
    }
    
    free(dup);
    
    fclose(ifp);
    fclose(ofp);
    
    return 0;
}
 
/* CheckCharsLine:  проверяет состоит ли l
                    только из символов в set */
int CheckCharsLine(const char *l, const char *set)
{
    const char *t;
    
    if (!(l && set && *l && *set))
        return EOF;
    for (t = set; *t; t++)
        if (!strchr(l, *t))
            return 0;
    for ( ; *l; l++)
        if (!strchr(set, *l))
            return 0;
    return 1;
}
Добавлено через 18 часов 44 минуты
Кто-нибудь может помочь?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BRcr
 Аватар для BRcr
4003 / 2292 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
19.11.2012, 16:07     Группы анаграмм в строке #2
Вот ленивое решение на основе внутренней сортировки по ключам в классе multimap. Нам остается только создать уникальный идентификатор анаграммы - то бишь просто отсортировать буквы в слове(если сортировать буквы в словах-анаграммах, всегда получим строчку одного и того же вида).
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
    fstream file_in( "in.txt", ios_base::in ), file_out( "out.txt", ios_base::out ); // открываем файлы с соответствующими режимами
    multimap <string, string> ana_map; // набор пар типа pair<string, string>, с возможностью дубликации ключей
    string str, sorted_str;
 
    if ( !file_in.is_open( ) || !file_out.is_open( ) ) { // если какой-либо из файлов не открыт - ошибка и завершение программы
        cout << "error opening files\n\n";
        system( "pause" );
        return -1;
    }
    while ( !file_in.eof( ) ) { // заполняем ana_map из потока file_in
        file_in >> str; // слова, разделенные пробелом, по одному помещаются в str
        sorted_str = str;
        sort( sorted_str.begin( ), sorted_str.end( ) ); // сортируем буквы в строчке sorted_str по возрастанию
        ana_map.insert( pair <string, string> ( sorted_str, str ) ); // вставляем пару строчек в ana_map, где ключом служит сортированная строчка, а значением - исходное слово; простая форма записи типа "ana_map[sorted_str] = str;" у меня не компилируется по причине отсутствия оператора + в данном шаблоне multimap для типа string - хз почему, да и бог с ним
    }
    str = ana_map.begin( )->first;
    for ( multimap <string, string> ::iterator it = ana_map.begin( ); it != ana_map.end( ); ++it ) { // проходим циклом по всем парам в ana_map последовательно, так как они отсортированы внутри по ключу, остается только отсечь лишнее и вывести все остальное :)
        if ( ana_map.count( it->first ) > 1 ) { // отсекаем ключи, встречающиеся один раз
            if ( str != it->first && file_out.tellp( ) ) { // разделяем наборы анаграмм по строчкам: если текущий ключ не равен предыдущему И фокус вывода НЕ находится в начале файла, то выводим в файл перенос строки
                file_out << endl;
            }
            file_out << it->second << " ";
            str = it->first;
        }
    }
    file_in.close( );
    file_out.close( );
Файл in.txt:
Код
секта автор рост весточка аскет товар сигара трос тесак отвар качество сорт месть ток свет сетка трос
Файл out.txt:
Код
весточка качество 
автор товар отвар 
секта аскет тесак сетка 
рост трос сорт трос
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
19.11.2012, 17:43  [ТС]     Группы анаграмм в строке #3
1. Что должно быть в include? (я в с++ начинающий, по коду пока понять не могу; пробовал подключать всё подряд известное мне #include <iostream> #include <fstream> #include <stdio.h> #include <string> #include <string.h> #include <stdlib.h>, пишет много интересного... привожу журнал компиляции:
Кликните здесь для просмотра всего текста
Компилятор: Default compiler
Выполнение g++.exe...
g++.exe "C:\Users\Delmellor\Desktop\erh\reht.cpp" -o "C:\Users\Delmellor\Desktop\erh\reht.exe" -I"C:\Dev-Cpp\lib\gcc\mingw32\3.4.2\include" -I"C:\Dev-Cpp\include\c++\3.4.2\backward" -I"C:\Dev-Cpp\include\c++\3.4.2\mingw32" -I"C:\Dev-Cpp\include\c++\3.4.2" -I"C:\Dev-Cpp\include" -L"C:\Dev-Cpp\lib"
C:\Users\Delmellor\Desktop\erh\reht.cpp:8: error: `fstream' does not name a type

C:\Users\Delmellor\Desktop\erh\reht.cpp:9: error: expected constructor, destructor, or type conversion before '<' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:9: error: expected `,' or `;' before '<' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:10: error: `string' does not name a type

C:\Users\Delmellor\Desktop\erh\reht.cpp:12: error: expected unqualified-id before "if"

C:\Users\Delmellor\Desktop\erh\reht.cpp:12: error: expected `,' or `;' before "if"

C:\Users\Delmellor\Desktop\erh\reht.cpp:17: error: expected unqualified-id before "while"

C:\Users\Delmellor\Desktop\erh\reht.cpp:17: error: expected `,' or `;' before "while"

C:\Users\Delmellor\Desktop\erh\reht.cpp:24: error: expected constructor, destructor, or type conversion before '=' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:24: error: expected `,' or `;' before '=' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:25: error: expected unqualified-id before "for"

C:\Users\Delmellor\Desktop\erh\reht.cpp:25: error: expected `,' or `;' before "for"

C:\Users\Delmellor\Desktop\erh\reht.cpp:25: error: expected constructor, destructor, or type conversion before '!=' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:25: error: expected `,' or `;' before '!=' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:25: error: expected unqualified-id before '++' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:25: error: expected `,' or `;' before '++' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:34: error: expected constructor, destructor, or type conversion before '.' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:34: error: expected `,' or `;' before '.' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:35: error: expected constructor, destructor, or type conversion before '.' token

C:\Users\Delmellor\Desktop\erh\reht.cpp:35: error: expected `,' or `;' before '.' token

Выполнение завершено.


Как видите, работаю с Dev-C++ 4.9.9.2 ; Подскажите, что нужно добавить, чтобы работало.

2. Как начинающий, пока слабо представляю, что такое классы, ключи и т.п... ну это я почитаю; если будут вопросы - обращусь.
BRcr
 Аватар для BRcr
4003 / 2292 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
19.11.2012, 17:52     Группы анаграмм в строке #4
Инклуды:
C++
1
2
3
4
#include <map>
#include <string>
#include <fstream>
#include <iostream>
Не опознает у тебя string и fstream. Напиши в самом начале функции main указание пространства имен - using namespace std;
Где в Dev-C++ функция system() или ее аналог - не знаю, пошарь по справке или исключи ее из кода.
Delmellor
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
26.11.2012, 09:43  [ТС]     Группы анаграмм в строке #5
Спасибо Вам большое, Владимир. Всё понятно, кроме одной вещи... Не нашёл конкретную информацию об операции -> в multimap в программе.. Объясните, пожалуйста, как в классе multimap она работает.

И ещё. Вот строки идут через пробел.. а как программа понимает, что через пробел их нужно считывать?
и ещё кое-что.. как переписать программу, чтобы были доступны и другие разделители? запятая, точка с запятой, тире?

Буду очень благодарен.
BRcr
 Аватар для BRcr
4003 / 2292 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
26.11.2012, 20:40     Группы анаграмм в строке #6
Multimap содержит массив шаблонных структур типа pair - в данном случае pair <string, string> - и массив указателей на них. Метод begin() возвращает первый элемент этого массива указателей - он, как и любой другой элемент этого массива, может служить итератором для последовательного доступа ко всем элементам. В итоге итератор it содержит в себе указатель на какой-либо экземпляр структур pair внутри multimap, и применяя к нему оператор ->, мы получаем непосредственный доступ к содержимому данной структуры, например, к полям first и second.
Цитата Сообщение от Delmellor Посмотреть сообщение
И ещё. Вот строки идут через пробел.. а как программа понимает, что через пробел их нужно считывать?
Так уж реализованы потоки - пробел является разделителем по умолчанию.
Цитата Сообщение от Delmellor Посмотреть сообщение
как переписать программу, чтобы были доступны и другие разделители?
Вот так.
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
    fstream file_in( "in.txt", ios_base::in ), file_out( "out.txt", ios_base::out ); // открываем файлы с соответствующими режимами
    multimap <string, string> ana_map; // набор пар типа pair<string, string>, с возможностью дубликации ключей
    string str, sorted_str;
 
    if ( !file_in.is_open( ) || !file_out.is_open( ) ) { // если какой-либо из файлов не открыт - ошибка и завершение программы
        cout << "error opening files\n\n";
        system( "pause" );
        return -1;
    }
 
    typedef ctype <TCHAR> ctype_tchar;
    size_t const size = ctype_tchar::table_size;
    // ctype_tchar::mask table[ctype_tchar::table_size] = {ctype_tchar::mask( )};  <--- по идее, так правильней, относительно типа char, но, во-первых, как ни бейся, у меня выпадает ошибка constant expression requared, а во-вторых, нас ведь может больше интересовать wchar_t
    ctype_tchar::mask table[256] = {ctype_tchar::mask( )}; // создаем таблицу масок символов
    table[static_cast <size_t> ( ' ' )] = ctype_tchar::space; // модифицируем маску интересующих нас символов, ассоциируя их с пробелом
    table[static_cast <size_t> ( ',' )] = ctype_tchar::space;
    table[static_cast <size_t> ( '-' )] = ctype_tchar::space;
    table[static_cast <size_t> ( ';' )] = ctype_tchar::space;
    file_in.imbue( locale( file_in.getloc( ), new ctype_tchar( table ) ) ); // модифицируем локаль потока, добавляя созданные нами маски - все, поток будет считать пробелом любой указанный нами символ и соответственно будет обрабатывать его как разделитель
 
    while ( !file_in.eof( ) ) { // заполняем ana_map из потока file_in
        file_in >> str;         // слова, разделенные пробелом, по одному помещаются в str
        sorted_str = str;
        sort( sorted_str.begin( ), sorted_str.end( ) ); // сортируем буквы в строчке sorted_str по возрастанию
        ana_map.insert( pair <string, string> ( sorted_str, str ) ); // вставляем пару строчек в ana_map, где ключом служит сортированная строчка, а значением - исходное слово; простая форма записи типа "ana_map[sorted_str] = str;" у меня не компилируется по причине отсутствия оператора + в данном шаблоне multimap для типа string - хз почему, да и бог с ним
    }
    str = ana_map.begin( )->first;
    for ( multimap <string, string> ::iterator it = ana_map.begin( ); it != ana_map.end( ); ++it ) { // проходим циклом по всем парам в ana_map последовательно, так как они отсортированы внутри по ключу, остается только отсечь лишнее и вывести все остальное :)
        if ( ana_map.count( it->first ) > 1 ) { // отсекаем ключи, встречающиеся один раз
            if ( str != it->first && file_out.tellp( ) ) { // разделяем наборы анаграмм по строчкам: если текущий ключ не равен предыдущему И фокус вывода НЕ находится в начале файла, то выводим в файл перенос строки
                file_out << endl;
            }
            file_out << it->second << " ";
            str = it->first;
        }
    }
    file_in.close( );
    file_out.close( );
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
24.12.2013, 14:57     Группы анаграмм в строке #7
Подскажите, а функция sort(); как будет реализована? может у кого есть она?)
BRcr
 Аватар для BRcr
4003 / 2292 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
24.12.2013, 23:14     Группы анаграмм в строке #8
Будет реализована где или когда? Это раз.
В библиотеке stl есть она очень даже давно - это два.

Ну, и на добавку, нынешняя реализация, вероятно, выглядит как-то так - Как реализована сортировка в STL.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.12.2013, 07:51     Группы анаграмм в строке
Еще ссылки по теме:

Строка: Поиск анаграмм C++
Задана строка. Подсчитать количество символов арифметических операций (*, +, -, /) в заданной строке и дополнить строку слово шифра группы C++
В строке удалить все заданные группы букв C++

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

Или воспользуйтесь поиском по форуму:
kpoxaa
70 / 31 / 1
Регистрация: 03.08.2012
Сообщений: 446
25.12.2013, 07:51     Группы анаграмм в строке #9
Если она есть, то не подхватила почему-то... спасибо!!
Yandex
Объявления
25.12.2013, 07:51     Группы анаграмм в строке
Ответ Создать тему
Опции темы

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