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

Поиск анаграмм - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 40, средняя оценка - 4.73
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
16.10.2011, 02:01     Поиск анаграмм #1
Доброй ночи!
Такая задачка... Возможно многим знакома по Золотому байту. Я в самом начале изучения С++ и до конца не могу разобраться.
Есть файл "in.txt" с каким-либо списком слов (до 10000). Одна строка - одно слово.
Нужно найти все анаграммы и вывести их в файл "out.txt".
Например во входном файле:
kot
polet
tok
leto
teplo
kto
zima

Тогда на выходе:
kot
tok
kto
polet
teplo

Примерно так...
Во время первого считывания файла я определяю кол-во строк. Затем создаю массив строк.
Далее сортирую буквы в словах.
Это сделал. Вроде и дальше понимаю путь (с помощью strcmp ищем дубликаты). Но на деле не получается. Не пойму , как обратно отсортировать. Или какой другой алгоритм нужен. И как в файл записать... Классы не использовать.
Посмотрите код и помогите пожалуйста.
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
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<iostream>
#include <cstdlib>
#include<stdio.h>
#include <iomanip>
#include<cctype>
#include<cstring>
using namespace std;
void BubbleSort1(char[],int);
int main()
{
    setlocale(LC_ALL,"rus");
    FILE *file;
    char str[255];
    int N,M=0;
    if((file=fopen("in.txt", "r"))!=NULL)
    {
    do
        {
            fgets(str,255,file);
            M++;
        } while(!feof(file));
        fclose(file);
    }
    else
    {
        cout<<"File not found"<<endl;
    }
    char **mas = new char*[M];
    for(int i=0;i<M;i++)
    {
        mas[i]=new char[255];
    }
    if((file=fopen("in.txt", "r"))!=NULL)
    {
        for(int i=0;i<M;i++)
        {
            fgets(mas[i],255,file);
        }
        fclose(file);
    }
    else
    {
        cout<<"Error";
    }
    for(int i=0;i<M;i++)
    {
        cout<<mas[i];
    }
    cout<<"\n\n";
    for(int i=0;i<M;i++)
    {
        N=strlen(mas[i]);
        BubbleSort1(mas[i],N);
    }
    for(int i=0; i<M-1; i++)
    {
        cout<<mas[i];
    }
    cout<<"\n\n";
    for(int i=0;i<M;i++)
    {
        char*y=mas[i];
        for(int j=i+1;j<M;j++)
        {
            if(strcmp(y,mas[j])==0)
            {
                cout<<y;
            }
        }
    }
    cout<<endl;
    system("pause");
    return 0;
}
void BubbleSort1(char*mas,int M)
{
    bool sort=true;
    while(sort)
    {
        sort=false;
        for(int i=0;i<M-1;i++)
        {
            if(mas[i]>mas[i+1])
            {
                int x=mas[i];
                mas[i]=mas[i+1];
                mas[i+1]=x;
                sort=true;
            }
        }
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,657
17.10.2011, 18:08     Поиск анаграмм #21
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
68
69
70
71
72
73
74
/////////////////////////////////////////////////////////////////////////////////////////
//Есть файл "in.txt" с каким-либо списком слов (до 10000). Одна строка - одно слово.
//Нужно найти все анаграммы и вывести их в файл "out.txt".
//Например во входном файле:
//kot
//polet
//tok
//leto
//teplo
//kto
//zima
//
//Тогда на выходе:
//kot
//tok
//kto
//polet
//teplo
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
typedef std::set<char>  T_char_set;
/////////////////////////////////////////////////////////////////////////////////////////
struct T_anagrams_less : public std::binary_function<const T_str&, const T_str&, bool>
{
    bool operator() 
        (
            const T_str&  A,
            const T_str&  B
        )
    {
        return      T_char_set( A.begin(), A.end() )
                <   T_char_set( B.begin(), B.end() );
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::multiset<T_str, T_anagrams_less>  T_anagrams;
/////////////////////////////////////////////////////////////////////////////////////////
void  find_anagrams
    (
        const T_str&  ifilename,
        const T_str&  ofilename
    )
{
    std::ifstream   ifile( ifilename.c_str() );    
    T_anagrams      anagrams;
 
    std::copy
        (
            std::istream_iterator<T_str>(ifile),
            std::istream_iterator<T_str>(),
            std::inserter( anagrams, anagrams.begin() )      
        );
 
    std::ofstream   ofile( ofilename.c_str() );
    for(T_anagrams::const_iterator  anagr_it = anagrams.begin();
        anagr_it != anagrams.end(); ++anagr_it)
    {
        if(anagrams.count(*anagr_it) == 1) continue;
        ofile << *anagr_it
              << std::endl;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{    
    find_anagrams("in.txt", "out.txt");
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
17.10.2011, 20:48  [ТС]     Поиск анаграмм #22
Всем спасибо!
Есть такой вопрос... А можно ли вообще написать эту программу по тому алгоритму, который я описывал в начале?
А то он у меня не получается.
Ваши решения , конечно, намного красивей и изящней.
Просто интересует можно ли это в принципе. И если можно то как...
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,657
17.10.2011, 22:50     Поиск анаграмм #23
Пардон, в мою программу вкралась ошибка. Вот так правильно:
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
68
69
70
71
72
73
74
/////////////////////////////////////////////////////////////////////////////////////////
//Есть файл "in.txt" с каким-либо списком слов (до 10000). Одна строка - одно слово.
//Нужно найти все анаграммы и вывести их в файл "out.txt".
//Например во входном файле:
//kot
//polet
//tok
//leto
//teplo
//kto
//zima
//
//Тогда на выходе:
//kot
//tok
//kto
//polet
//teplo
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string             T_str;
typedef std::multiset<char>     T_char_multiset;
/////////////////////////////////////////////////////////////////////////////////////////
struct T_anagrams_less : public std::binary_function<const T_str&, const T_str&, bool>
{
    bool operator() 
        (
            const T_str&  A,
            const T_str&  B
        )
    {
        return      T_char_multiset( A.begin(), A.end() )
                <   T_char_multiset( B.begin(), B.end() );
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::multiset<T_str, T_anagrams_less>  T_anagrams;
/////////////////////////////////////////////////////////////////////////////////////////
void  find_anagrams
    (
        const T_str&  ifilename,
        const T_str&  ofilename
    )
{
    std::ifstream   ifile( ifilename.c_str() );    
    T_anagrams      anagrams;
 
    std::copy
        (
            std::istream_iterator<T_str>(ifile),
            std::istream_iterator<T_str>(),
            std::inserter( anagrams, anagrams.begin() )      
        );
 
    std::ofstream   ofile( ofilename.c_str() );
    for(T_anagrams::const_iterator  anagr_it = anagrams.begin();
        anagr_it != anagrams.end(); ++anagr_it)
    {
        if(anagrams.count(*anagr_it) == 1) continue;
        ofile << *anagr_it
              << std::endl;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{    
    find_anagrams("in.txt", "out.txt");
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.03.2012, 13:06     Поиск анаграмм
Еще ссылки по теме:

C++ Поиск символа не могу переделать под поиск сочетания символов
Поиск пикселя и поиск изображения на экране C++
Поиск числа в двумерном массиве (бинарный поиск) C++

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

Или воспользуйтесь поиском по форуму:
isaak
101 / 38 / 9
Регистрация: 17.10.2010
Сообщений: 634
09.03.2012, 13:06     Поиск анаграмм #24
Подскажите пожалуйста как исправить ошибки, чтобы компилятор не ругался:

1 IntelliSense: namespace "std" has no member "istream_iterator" c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 37 18 Searching anagram
2 IntelliSense: type name is not allowed c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 37 35 Searching anagram
3 IntelliSense: namespace "std" has no member "istream_iterator" c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 38 18 Searching anagram
4 IntelliSense: type name is not allowed c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 38 35 Searching anagram
5 IntelliSense: expected an expression c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 38 42 Searching anagram
6 IntelliSense: namespace "std" has no member "inserter" c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 39 18 Searching anagram

Заранее огромное спасибо!!!!
Yandex
Объявления
09.03.2012, 13:06     Поиск анаграмм
Ответ Создать тему
Опции темы

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